diff --git a/core/lib/Drupal/Core/Entity/ContentEntityStorageBase.php b/core/lib/Drupal/Core/Entity/ContentEntityStorageBase.php index d6c69304f8..be0a39dd29 100644 --- a/core/lib/Drupal/Core/Entity/ContentEntityStorageBase.php +++ b/core/lib/Drupal/Core/Entity/ContentEntityStorageBase.php @@ -2,6 +2,7 @@ namespace Drupal\Core\Entity; +use Drupal\Component\Graph\Graph; use Drupal\Core\Cache\Cache; use Drupal\Core\Cache\CacheBackendInterface; use Drupal\Core\Cache\MemoryCache\MemoryCacheInterface; @@ -44,6 +45,13 @@ */ protected $latestRevisionIds = []; + /** + * An array containing the ancestor IDs of each revision, keyed by entity ID. + * + * @var array + */ + protected $ancestorIds = []; + /** * Constructs a ContentEntityStorageBase object. * @@ -401,6 +409,90 @@ public function getLatestTranslationAffectedRevisionId($entity_id, $langcode) { return $this->latestRevisionIds[$entity_id][$langcode]; } + /** + * {@inheritdoc} + */ + public function getLowestCommonAncestor(RevisionableInterface $entity, $first_revision_id, $second_revision_id) { + $ancestors = &$this->ancestorIds[$entity->id()]; + + if (empty($ancestors)) { + $revision_parents = $this->getAllRevisionParents($entity); + + $graph = []; + foreach ($revision_parents as $revision_id => $info) { + if ($parent_id = $info['parent_id']) { + $graph[$revision_id]['edges'][$parent_id] = TRUE; + } + + if ($merge_parent_id = $info['merge_parent_id']) { + $graph[$revision_id]['edges'][$merge_parent_id] = TRUE; + } + } + + $revision_graph = (new Graph($graph))->searchAndSort(); + foreach (array_keys($revision_parents) as $revision_id) { + $graph_paths = isset($revision_graph[$revision_id]['paths']) ? array_keys($revision_graph[$revision_id]['paths']) : []; + // We store "ancestors and self" IDs, so we need to add the current + // revision ID to the list. + $ancestors[$revision_id] = array_merge([$revision_id => $revision_id], $graph_paths); + } + + // Free up memory early. + $revision_graph = NULL; + $graph = NULL; + } + + if (!isset($ancestors[$first_revision_id])) { + throw new \InvalidArgumentException("The specified revision ($first_revision_id) does not exist."); + } + if (!isset($ancestors[$second_revision_id])) { + throw new \InvalidArgumentException("The specified revision ($second_revision_id) does not exist."); + } + if (empty($ancestors[$first_revision_id]) || empty($ancestors[$second_revision_id])) { + return NULL; + } + + $common_ancestors = array_intersect($ancestors[$first_revision_id], $ancestors[$second_revision_id]); + // The ancestors are ordered by ascending weight, so the lowest common + // ancestor is the first element of the array. + return reset($common_ancestors); + } + + /** + * Retrieves a list of revision parents for a given entity. + * + * @param \Drupal\Core\Entity\RevisionableInterface $entity + * An entity entity object. + * + * @return array + * A multi-dimensional array keyed by revision ID, containing an array with + * the following structure: + * - id: The revision ID; + * - parent_id: The parent revision ID; + * - merge_parent_id: The merge parent revision ID. + */ + protected function getAllRevisionParents(RevisionableInterface $entity) { + $revision_key = $this->entityType->getKey('revision'); + $revision_parent_key = $this->entityType->getRevisionMetadataKey('revision_parent'); + + $result = $this->getQuery() + ->condition($this->idKey, $entity->id(), '=') + ->sort($revision_key, 'ASC') + ->allRevisions() + ->execute(); + + $revision_parents = []; + foreach ($this->loadMultipleRevisions(array_keys($result)) as $revision_id => $revision) { + $revision_parents[$revision_id] = [ + 'id' => $revision_id, + 'parent_id' => $revision->{$revision_parent_key}->target_id, + 'merge_parent_id' => $revision->{$revision_parent_key}->merge_target_id, + ]; + } + + return $revision_parents; + } + /** * {@inheritdoc} */ diff --git a/core/lib/Drupal/Core/Entity/RevisionableStorageInterface.php b/core/lib/Drupal/Core/Entity/RevisionableStorageInterface.php index d23808b1b6..5199e2eabc 100644 --- a/core/lib/Drupal/Core/Entity/RevisionableStorageInterface.php +++ b/core/lib/Drupal/Core/Entity/RevisionableStorageInterface.php @@ -65,4 +65,20 @@ public function deleteRevision($revision_id); */ public function getLatestRevisionId($entity_id); + /** + * Gets the lowest common ancestor of two revision IDs. + * + * @param \Drupal\Core\Entity\RevisionableInterface $entity + * An entity which contains at least two revisions. + * @param int|string $first_revision_id + * The first revision ID. + * @param int|string $second_revision_id + * The second revision ID. + * + * @return int|string|null + * The lowest common ancestor of the two revisions, or NULL if couldn't be + * found. + */ + public function getLowestCommonAncestor(RevisionableInterface $entity, $first_revision_id, $second_revision_id); + } diff --git a/core/lib/Drupal/Core/Entity/Sql/SqlContentEntityStorage.php b/core/lib/Drupal/Core/Entity/Sql/SqlContentEntityStorage.php index 7edc4f6307..2dee9798ba 100644 --- a/core/lib/Drupal/Core/Entity/Sql/SqlContentEntityStorage.php +++ b/core/lib/Drupal/Core/Entity/Sql/SqlContentEntityStorage.php @@ -17,6 +17,7 @@ use Drupal\Core\Entity\EntityStorageException; use Drupal\Core\Entity\EntityTypeInterface; use Drupal\Core\Entity\Query\QueryInterface; +use Drupal\Core\Entity\RevisionableInterface; use Drupal\Core\Entity\Schema\DynamicallyFieldableEntityStorageSchemaInterface; use Drupal\Core\Field\FieldDefinitionInterface; use Drupal\Core\Field\FieldStorageDefinitionInterface; @@ -1363,6 +1364,30 @@ protected function deleteRevisionFromDedicatedTables(ContentEntityInterface $ent } } + /** + * {@inheritdoc} + */ + protected function getAllRevisionParents(RevisionableInterface $entity) { + $table_mapping = $this->getTableMapping(); + + $revision_tree_table = $table_mapping->getFieldTableName($this->entityType->getRevisionMetadataKey('revision_parent')); + $field_columns = $table_mapping->getColumnNames($this->entityType->getKey('id')); + $id_column = reset($field_columns); + $field_columns = $table_mapping->getColumnNames($this->entityType->getKey('revision')); + $revision_id_column = reset($field_columns); + $parent_revision_id_column = $table_mapping->getColumnNames($this->entityType->getRevisionMetadataKey('revision_parent'))['target_id']; + $merge_revision_id_column = $table_mapping->getColumnNames($this->entityType->getRevisionMetadataKey('revision_parent'))['merge_target_id']; + + $query = $this->database->select($revision_tree_table, 't'); + $query->condition($id_column, $entity->id(), '='); + $query->addField('t', $revision_id_column, 'id'); + $query->addField('t', $parent_revision_id_column, 'parent_id'); + $query->addField('t', $merge_revision_id_column, 'merge_parent_id'); + $query->orderBy($revision_id_column, 'ASC'); + + return $query->execute()->fetchAllAssoc('id', \PDO::FETCH_ASSOC); + } + /** * {@inheritdoc} */ diff --git a/core/tests/Drupal/KernelTests/Core/Entity/EntityRevisionTreeTest.php b/core/tests/Drupal/KernelTests/Core/Entity/EntityRevisionTreeTest.php new file mode 100644 index 0000000000..4932ecba23 --- /dev/null +++ b/core/tests/Drupal/KernelTests/Core/Entity/EntityRevisionTreeTest.php @@ -0,0 +1,124 @@ +installEntitySchema('entity_test_rev'); + + $this->storage = \Drupal::entityTypeManager()->getStorage('entity_test_rev'); + } + + /** + * @covers \Drupal\Core\Entity\ContentEntityStorageBase::getLowestCommonAncestor + */ + public function testGetLowestCommonAncestor() { + // Create a complex revision graph: + // + // 3 -- 4 -- 5 -- 8 + // / / \ + // 1 -- 2 -- 6 -- 7 ------ 9 --- 16 + // \ / + // 10 -- 11 ------ 15 + // \ / + // 12 -- 13 -- 14 + // + $revisions_graph = [ + 1 => [NULL, NULL], + 2 => [1, NULL], + 3 => [2, NULL], + 4 => [3, NULL], + 5 => [4, 7], + 6 => [2, NULL], + 7 => [6, NULL], + 8 => [5, NULL], + 9 => [8, 7], + 10 => [6, NULL], + 11 => [10, NULL], + 12 => [10, NULL], + 13 => [12, NULL], + 14 => [13, NULL], + 15 => [11, 14], + 16 => [9, 15], + ]; + $entity = $this->storage->create(['revision_id' => 1]); + $entity->save(); + foreach ($revisions_graph as $revision_id => $parents) { + $this->createRevision($entity, $revision_id, $parents[0], $parents[1]); + } + + // And test the following cases for finding the lowest common ancestor. + $test_cases = [ + '1 - 2' => 1, + '2 - 3' => 2, + '2 - 4' => 2, + '6 - 4' => 2, + '6 - 5' => 6, + '7 - 5' => 7, + '7 - 8' => 7, + '7 - 9' => 7, + '16 - 8' => 8, + '10 - 7' => 6, + '11 - 7' => 6, + '13 - 4' => 2, + '13 - 5' => 6, + '13 - 9' => 6, + '13 - 11' => 10, + '13 - 15' => 13, + '14 - 16' => 14, + '14 - 8' => 6, + '15 - 8' => 6, + '15 - 9' => 6, + '15 - 4' => 2, + '15 - 5' => 6, + '16 - 5' => 5, + ]; + foreach ($test_cases as $key => $expected_lca) { + list($revision_a, $revision_b) = explode(' - ', $key); + $lca = $this->storage->getLowestCommonAncestor($entity, $revision_a, $revision_b); + + $this->assertEquals($expected_lca, $lca); + } + } + + /** + * Creates a revision for the test entity type. + * + * @param \Drupal\Core\Entity\RevisionableInterface $entity + * A revision entity object. + * @param int $revision_id + * The ID of the revision that will be created. + * @param int $parent_revision_id + * The parent ID of the revision that will be created. + * @param int $merge_revision_id + * The merge parent ID of the revision that will be created. + */ + protected function createRevision(RevisionableInterface $entity, $revision_id, $parent_revision_id, $merge_revision_id) { + $revision = $this->storage->createRevision($entity); + $revision->revision_id->value = $revision_id; + $revision->revision_parent->target_id = $parent_revision_id; + $revision->revision_parent->merge_target_id = $merge_revision_id; + $revision->save(); + } + +}