Differential D21363 Diff 50851 src/repository/graph/ArcanistCommitGraphPartitionQuery.php

Changeset View

Standalone View

src/repository/graph/ArcanistCommitGraphPartitionQuery.php

This file was added.

				<?php

				final class ArcanistCommitGraphPartitionQuery
				extends Phobject {

				private $graph;
				private $heads;
				private $hashes;

				public function setGraph(ArcanistCommitGraph $graph) {
				$this->graph = $graph;
				return $this;
				}

				public function getGraph() {
				return $this->graph;
				}

				public function withHeads(array $heads) {
				$this->heads = $heads;
				return $this;
				}

				public function withHashes(array $hashes) {
				$this->hashes = $hashes;
				return $this;
				}

				public function execute() {
				$graph = $this->getGraph();

				$heads = $this->heads;
				$heads = array_fuse($heads);
				if (!$heads) {
				throw new Exception(pht('Partition query requires heads.'));
				}

				$waypoints = $heads;

				$stack = array();
				$partitions = array();
				$partition_identities = array();
				$n = 0;
				foreach ($heads as $hash) {
				$node = $graph->getNode($hash);

				if (!$node) {
				echo "TODO: WARNING: Bad hash {$hash}\n";
				continue;
				}

				$partitions[$hash] = $n;
				$partition_identities[$n] = array($n => $n);
				$n++;

				$stack[] = $node;
				}

				$scope = null;
				if ($this->hashes) {
				$scope = array_fuse($this->hashes);
				}

				$leaves = array();
				while ($stack) {
				$node = array_pop($stack);

				$node_hash = $node->getCommitHash();
				$node_partition = $partition_identities[$partitions[$node_hash]];

				$saw_parent = false;
				foreach ($node->getParentNodes() as $parent) {
				$parent_hash = $parent->getCommitHash();

				if ($scope !== null) {
				if (!isset($scope[$parent_hash])) {
				continue;
				}
				}

				$saw_parent = true;

				if (isset($partitions[$parent_hash])) {
				$parent_partition = $partition_identities[$partitions[$parent_hash]];

				// If we've reached this node from a child, it clearly is not a
				// head.
				unset($heads[$parent_hash]);

				// If we've reached a node which is already part of another
				// partition, we can stop following it and merge the partitions.

				$new_partition = $node_partition + $parent_partition;
				ksort($new_partition);

				if ($node_partition !== $new_partition) {
				foreach ($node_partition as $partition_id) {
				$partition_identities[$partition_id] = $new_partition;
				}
				}

				if ($parent_partition !== $new_partition) {
				foreach ($parent_partition as $partition_id) {
				$partition_identities[$partition_id] = $new_partition;
				}
				}
				continue;
				} else {
				$partitions[$parent_hash] = $partitions[$node_hash];
				}

				$stack[] = $parent;
				}

				if (!$saw_parent) {
				$leaves[$node_hash] = true;
				}
				}

				$partition_lists = array();
				$partition_heads = array();
				$partition_waypoints = array();
				$partition_leaves = array();
				foreach ($partitions as $hash => $partition) {
				$partition = reset($partition_identities[$partition]);
				$partition_lists[$partition][] = $hash;
				if (isset($heads[$hash])) {
				$partition_heads[$partition][] = $hash;
				}
				if (isset($waypoints[$hash])) {
				$partition_waypoints[$partition][] = $hash;
				}
				if (isset($leaves[$hash])) {
				$partition_leaves[$partition][] = $hash;
				}
				}

				$results = array();
				foreach ($partition_lists as $partition_id => $partition_list) {
				$partition_set = array_fuse($partition_list);

				$results[] = id(new ArcanistCommitGraphPartition())
				->setGraph($graph)
				->setHashes($partition_set)
				->setHeads($partition_heads[$partition_id])
				->setWaypoints($partition_waypoints[$partition_id])
				->setTails($partition_leaves[$partition_id]);
				}

				return $results;
				}

				}