RevisionTreeIndex.php in Multiversion 8

Namespace

Drupal\multiversion\Entity\Index

File

src/Entity/Index/RevisionTreeIndex.php

<?php

namespace Drupal\multiversion\Entity\Index;

use Drupal\Core\Entity\ContentEntityInterface;
use Drupal\Core\KeyValueStore\KeyValueFactoryInterface;
use Drupal\multiversion\Entity\Workspace;
use Drupal\multiversion\Workspace\WorkspaceManagerInterface;
use Fhaculty\Graph\Graph;

/**
 * The revision tree index.
 *
 * @todo: {@link https://www.drupal.org/node/2597444 Consider caching once/if
 * rev and rev tree indices are merged.}
 */
class RevisionTreeIndex implements RevisionTreeIndexInterface {

  /**
   * The key value factory service.
   *
   * @var \Drupal\Core\KeyValueStore\KeyValueFactoryInterface
   */
  protected $keyValueFactory;

  /**
   * The workspace manager service.
   *
   * @var \Drupal\multiversion\Workspace\WorkspaceManagerInterface
   */
  protected $workspaceManager;

  /**
   * The index factory service.
   *
   * @var \Drupal\multiversion\Entity\Index\MultiversionIndexFactory
   */
  protected $indexFactory;

  /**
   * The workspace ID.
   *
   * @var string
   */
  protected $workspaceId;

  /**
   * Constructs the Revision Tree Index.
   *
   * @param \Drupal\Core\KeyValueStore\KeyValueFactoryInterface $key_value_factory
   *   The key value factory service.
   * @param \Drupal\multiversion\Workspace\WorkspaceManagerInterface $workspace_manager
   *   The workspace manager service.
   * @param \Drupal\multiversion\Entity\Index\MultiversionIndexFactory $index_factory
   *   The index factory service.
   */
  public function __construct(KeyValueFactoryInterface $key_value_factory, WorkspaceManagerInterface $workspace_manager, MultiversionIndexFactory $index_factory) {
    $this->keyValueFactory = $key_value_factory;
    $this->workspaceManager = $workspace_manager;
    $this->indexFactory = $index_factory;
  }

  /**
   * {@inheritdoc}
   */
  public function useWorkspace($id) {
    $this->workspaceId = $id;
    return $this;
  }

  /**
   * {@inheritdoc}
   */
  public function getTree($uuid) {
    $values = $this
      ->buildTree($uuid);
    return $values['tree'];
  }

  /**
   * {@inheritdoc}
   */
  public function getGraph($uuid) {
    $tree = $this
      ->getTree($uuid);
    $graph = new Graph();
    $rev_ids = [];
    $this
      ->storeNodesId($tree, $rev_ids);
    $vertices = $this
      ->generateVertices($graph, $rev_ids);
    $this
      ->generateEdges($vertices, $tree);
    return $graph;
  }

  /**
   * Helper function to store all revision IDs in an array.
   *
   * @param array $tree
   *   An associative array containing information about tree.
   * @param array $revision_ids
   *   An array to store all revision ID.
   */
  protected function storeNodesId(array $tree, array &$revision_ids) {
    foreach ($tree as $value) {
      $current_id = $value['#rev'];
      $revision_ids[$current_id] = $current_id;
      if (count($value['children'])) {
        $this
          ->storeNodesId($value['children'], $revision_ids);
      }
    }
  }

  /**
   * Helper function to create Edges between parent and children.
   *
   * @param array $revisions_array
   *   Associative array containing graph nodes.
   * @param array $tree
   *   Associative array containing tree structure.
   * @param int $parent
   *   Parent vertex Id.
   */
  protected function generateEdges(array $revisions_array, array $tree, $parent = -1) {
    foreach ($tree as $item) {
      $current_id = $item['#rev'];
      if ($parent != -1) {
        $revisions_array[$parent]
          ->createEdgeTo($revisions_array[$current_id]);
      }
      if (count($item['children'])) {
        $this
          ->generateEdges($revisions_array, $item['children'], $current_id);
      }
    }
  }

  /**
   * Generates vertices for Graph.
   *
   * @param Graph $graph
   *   A graph object.
   * @param array $revision_ids
   *   The revision ids to generate vertices for.
   *
   * @return array
   *   An array of vertices.
   */
  protected function generateVertices(Graph $graph, array $revision_ids) {
    foreach ($revision_ids as $id) {
      $ids[] = $id;
    }
    return $graph
      ->createVertices($ids)
      ->getMap();
  }

  /**
   * {@inheritdoc}
   */
  public function updateTree(ContentEntityInterface $entity, array $branch = []) {
    if ($entity
      ->getEntityType()
      ->get('workspace') === FALSE) {
      $this
        ->keyValueStore($entity
        ->uuid(), 0)
        ->setMultiple($branch);
    }
    else {
      $this
        ->keyValueStore($entity
        ->uuid())
        ->setMultiple($branch);
    }
    return $this;
  }

  /**
   * {@inheritdoc}
   *
   * @todo: {@link https://www.drupal.org/node/2597422 The revision tree also
   * contain missing revisions. We need a better way to count.}
   */
  public function countRevs($uuid) {
    $values = $this
      ->buildTree($uuid);
    return count($values['default_branch']);
  }

  /**
   * {@inheritdoc}
   */
  public function getDefaultRevision($uuid) {
    $values = $this
      ->buildTree($uuid);
    return $values['default_rev']['#rev'];
  }

  /**
   * {@inheritdoc}
   */
  public function getDefaultBranch($uuid) {
    $values = $this
      ->buildTree($uuid);
    return $values['default_branch'];
  }

  /**
   * {@inheritdoc}
   */
  public function getOpenRevisions($uuid) {
    $revs = [];
    $values = $this
      ->buildTree($uuid);
    foreach ($values['open_revs'] as $rev => $element) {
      $revs[$rev] = $element['#rev_info']['status'];
    }
    return $revs;
  }

  /**
   * {@inheritdoc}
   */
  public function getConflicts($uuid) {
    $revs = [];
    $values = $this
      ->buildTree($uuid);
    foreach ($values['conflicts'] as $rev => $element) {
      $revs[$rev] = $element['#rev_info']['status'];
    }
    return $revs;
  }

  /**
   * {@inheritdoc}
   */
  public static function sortRevisions(array $a, array $b) {
    $a_deleted = $a['#rev_info']['status'] == 'deleted' ? TRUE : FALSE;
    $b_deleted = $b['#rev_info']['status'] == 'deleted' ? TRUE : FALSE;

    // The goal is to sort winning revision candidates from low to high. The
    // criteria are:
    // 1. Non-deleted always win over deleted.
    // 2. When IDs match, higher ASCII sort on revision hash wins.
    // 3. Otherwise, the highest ID wins.
    if ($a_deleted && !$b_deleted) {
      return 1;
    }
    elseif (!$a_deleted && $b_deleted) {
      return -1;
    }
    list($a_id) = explode('-', $a['#rev']);
    list($b_id) = explode('-', $b['#rev']);
    if ($a_id === $b_id) {
      return $a['#rev'] < $b['#rev'] ? 1 : -1;
    }
    else {
      return $a_id < $b_id ? 1 : -1;
    }
  }

  /**
   * {@inheritdoc}
   */
  public static function sortTree(array &$tree) {

    // Sort all tree elements according to the algorithm before recursing.
    usort($tree, [
      __CLASS__,
      'sortRevisions',
    ]);
    foreach ($tree as &$element) {
      if (!empty($element['children'])) {
        self::sortTree($element['children']);
      }
    }
  }

  /**
   * @param string $uuid
   *   The UUID for get the key value store for.
   * @param int|null $workspace_id
   *   The workspace to get the key value store for.
   *
   * @return \Drupal\Core\KeyValueStore\KeyValueStoreInterface
   *   The key value store.
   */
  protected function keyValueStore($uuid, $workspace_id = NULL) {
    if (!is_numeric($workspace_id)) {
      $workspace_id = $this
        ->getWorkspaceId();
    }
    return $this->keyValueFactory
      ->get("multiversion.entity_index.rev.tree.{$workspace_id}.{$uuid}");
  }

  /**
   * Helper method to build the revision tree.
   */
  protected function buildTree($uuid) {
    $revs = $this
      ->keyValueStore($uuid)
      ->getAll();
    if (!$revs) {
      $revs = $this
        ->keyValueStore($uuid, 0)
        ->getAll();
    }

    // Build the keys to fetch from the rev index.
    $keys = [];
    foreach (array_keys($revs) as $rev) {
      $keys[] = "{$uuid}:{$rev}";
    }
    $workspace = Workspace::load($this
      ->getWorkspaceId());
    $revs_info = $this->indexFactory
      ->get('multiversion.entity_index.rev', $workspace)
      ->getMultiple($keys);
    return self::doBuildTree($uuid, $revs, $revs_info);
  }

  /**
   * Recursive helper method to build the revision tree.
   *
   * @return array
   *   Returns an array containing the built tree, open revisions, default
   *   revision, default branch and conflicts.
   *
   * @todo: {@link https://www.drupal.org/node/2597430 Implement
   * 'deleted_conflicts'.}
   */
  protected static function doBuildTree($uuid, $revs, $revs_info, $parse = 0, &$tree = [], &$open_revs = [], &$conflicts = []) {
    foreach ($revs as $rev => $parent_revs) {
      foreach ($parent_revs as $parent_rev) {
        if ($rev == 0) {
          continue;
        }
        if ($parent_rev == $parse) {

          // Avoid bad data to cause endless loops.
          // @todo: {@link https://www.drupal.org/node/2597434 Needs test.}
          if ($rev == $parse) {
            throw new \InvalidArgumentException('Child and parent revision can not be the same value.');
          }

          // Build an element structure compatible with Drupal's Render API.
          $i = count($tree);
          $tree[$i] = [
            '#type' => 'rev',
            '#uuid' => $uuid,
            '#rev' => $rev,
            '#rev_info' => [
              'status' => isset($revs_info["{$uuid}:{$rev}"]['status']) ? $revs_info["{$uuid}:{$rev}"]['status'] : 'missing',
              'default' => FALSE,
              'open_rev' => FALSE,
              'conflict' => FALSE,
            ],
            'children' => [],
          ];

          // Recurse down through the children.
          self::doBuildTree($uuid, $revs, $revs_info, $rev, $tree[$i]['children'], $open_revs, $conflicts);

          // Find open revisions and conflicts. Only revisions with no children,
          // and that are not missing can be an open revision or a conflict.
          if (empty($tree[$i]['children']) && $tree[$i]['#rev_info']['status'] != 'missing') {
            $tree[$i]['#rev_info']['open_rev'] = TRUE;
            $open_revs[$rev] = $tree[$i];

            // All open revisions, except deleted and default revisions, are
            // conflicts by definition. We will revert the conflict flag when we
            // find the default revision later on.
            if ($tree[$i]['#rev_info']['status'] != 'deleted') {
              $tree[$i]['#rev_info']['conflict'] = TRUE;
              $conflicts[$rev] = $tree[$i];
            }
          }
        }
      }
    }

    // Now when the full tree is built we'll find the default revision and
    // its branch.
    if ($parse == 0) {
      $default_rev = 0;
      uasort($open_revs, [
        __CLASS__,
        'sortRevisions',
      ]);
      $default_rev = reset($open_revs);

      // Remove the default revision from the conflicts array and sort it.
      unset($conflicts[$default_rev['#rev']]);
      uasort($conflicts, [
        __CLASS__,
        'sortRevisions',
      ]);

      // Update the default revision in the tree and sort it.
      self::updateDefaultRevision($tree, $default_rev);
      self::sortTree($tree);

      // Find the branch of the default revision.
      $default_branch = [];
      $rev = $default_rev['#rev'];
      while ($rev != 0) {
        $default_branch[$rev] = isset($revs_info["{$uuid}:{$rev}"]['status']) ? $revs_info["{$uuid}:{$rev}"]['status'] : 'missing';

        // Only the first parent gets included in the default branch.
        $rev = $revs[$rev][0];
      }
      return [
        'tree' => $tree,
        'default_rev' => $default_rev,
        'default_branch' => array_reverse($default_branch),
        'open_revs' => $open_revs,
        'conflicts' => $conflicts,
      ];
    }
  }

  /**
   * Helper method to update the default revision.
   */
  protected static function updateDefaultRevision(&$tree, $default_rev) {

    // @todo: {@link https://www.drupal.org/node/2597442 We can temporarily
    // flip the sort to find the default rev earlier.}
    foreach ($tree as &$element) {
      if (isset($element['#rev']) && $element['#rev'] == $default_rev['#rev']) {
        $element['#rev_info']['default'] = TRUE;
        $element['#rev_info']['conflict'] = FALSE;
        break;
      }
      if (!empty($element['children'])) {
        self::updateDefaultRevision($element['children'], $default_rev);
      }
    }
  }

  /**
   * Helper method to get the workspace ID to query.
   */
  protected function getWorkspaceId() {
    return $this->workspaceId ?: $this->workspaceManager
      ->getActiveWorkspaceId();
  }

}

Classes

Name	Description
RevisionTreeIndex	The revision tree index.