D21363.id50851.diff
No OneTemporary
Actions

Size

64 KB

Referenced Files

None

Subscribers

None

D21363.id50851.diff
View Options

	diff --git a/src/__phutil_library_map__.php b/src/__phutil_library_map__.php
	--- a/src/__phutil_library_map__.php
	+++ b/src/__phutil_library_map__.php
	@@ -106,6 +106,16 @@
	'ArcanistCommentSpacingXHPASTLinterRule' => 'lint/linter/xhpast/rules/ArcanistCommentSpacingXHPASTLinterRule.php',
	'ArcanistCommentStyleXHPASTLinterRule' => 'lint/linter/xhpast/rules/ArcanistCommentStyleXHPASTLinterRule.php',
	'ArcanistCommentStyleXHPASTLinterRuleTestCase' => 'lint/linter/xhpast/rules/__tests__/ArcanistCommentStyleXHPASTLinterRuleTestCase.php',
	+ 'ArcanistCommitGraph' => 'repository/graph/ArcanistCommitGraph.php',
	+ 'ArcanistCommitGraphPartition' => 'repository/graph/ArcanistCommitGraphPartition.php',
	+ 'ArcanistCommitGraphPartitionQuery' => 'repository/graph/ArcanistCommitGraphPartitionQuery.php',
	+ 'ArcanistCommitGraphQuery' => 'repository/graph/query/ArcanistCommitGraphQuery.php',
	+ 'ArcanistCommitGraphSet' => 'repository/graph/ArcanistCommitGraphSet.php',
	+ 'ArcanistCommitGraphSetQuery' => 'repository/graph/ArcanistCommitGraphSetQuery.php',
	+ 'ArcanistCommitGraphSetTreeView' => 'repository/graph/view/ArcanistCommitGraphSetTreeView.php',
	+ 'ArcanistCommitGraphSetView' => 'repository/graph/view/ArcanistCommitGraphSetView.php',
	+ 'ArcanistCommitGraphTestCase' => 'repository/graph/__tests__/ArcanistCommitGraphTestCase.php',
	+ 'ArcanistCommitNode' => 'repository/graph/ArcanistCommitNode.php',
	'ArcanistCommitRef' => 'ref/commit/ArcanistCommitRef.php',
	'ArcanistCommitSymbolRef' => 'ref/commit/ArcanistCommitSymbolRef.php',
	'ArcanistCommitSymbolRefInspector' => 'ref/commit/ArcanistCommitSymbolRefInspector.php',
	@@ -211,6 +221,7 @@
	'ArcanistGeneratedLinterTestCase' => 'lint/linter/__tests__/ArcanistGeneratedLinterTestCase.php',
	'ArcanistGetConfigWorkflow' => 'workflow/ArcanistGetConfigWorkflow.php',
	'ArcanistGitAPI' => 'repository/api/ArcanistGitAPI.php',
	+ 'ArcanistGitCommitGraphQuery' => 'repository/graph/query/ArcanistGitCommitGraphQuery.php',
	'ArcanistGitCommitMessageHardpointQuery' => 'query/ArcanistGitCommitMessageHardpointQuery.php',
	'ArcanistGitCommitSymbolCommitHardpointQuery' => 'ref/commit/ArcanistGitCommitSymbolCommitHardpointQuery.php',
	'ArcanistGitLandEngine' => 'land/engine/ArcanistGitLandEngine.php',
	@@ -329,6 +340,7 @@
	'ArcanistMarkerRef' => 'repository/marker/ArcanistMarkerRef.php',
	'ArcanistMarkersWorkflow' => 'workflow/ArcanistMarkersWorkflow.php',
	'ArcanistMercurialAPI' => 'repository/api/ArcanistMercurialAPI.php',
	+ 'ArcanistMercurialCommitGraphQuery' => 'repository/graph/query/ArcanistMercurialCommitGraphQuery.php',
	'ArcanistMercurialCommitMessageHardpointQuery' => 'query/ArcanistMercurialCommitMessageHardpointQuery.php',
	'ArcanistMercurialLandEngine' => 'land/engine/ArcanistMercurialLandEngine.php',
	'ArcanistMercurialLocalState' => 'repository/state/ArcanistMercurialLocalState.php',
	@@ -459,6 +471,7 @@
	'ArcanistSetting' => 'configuration/ArcanistSetting.php',
	'ArcanistSettings' => 'configuration/ArcanistSettings.php',
	'ArcanistShellCompleteWorkflow' => 'toolset/workflow/ArcanistShellCompleteWorkflow.php',
	+ 'ArcanistSimpleCommitGraphQuery' => 'repository/graph/query/ArcanistSimpleCommitGraphQuery.php',
	'ArcanistSimpleSymbolHardpointQuery' => 'ref/simple/ArcanistSimpleSymbolHardpointQuery.php',
	'ArcanistSimpleSymbolRef' => 'ref/simple/ArcanistSimpleSymbolRef.php',
	'ArcanistSimpleSymbolRefInspector' => 'ref/simple/ArcanistSimpleSymbolRefInspector.php',
	@@ -925,6 +938,8 @@
	'mpull' => 'utils/utils.php',
	'msort' => 'utils/utils.php',
	'msortv' => 'utils/utils.php',
	+ 'msortv_internal' => 'utils/utils.php',
	+ 'msortv_natural' => 'utils/utils.php',
	'newv' => 'utils/utils.php',
	'nonempty' => 'utils/utils.php',
	'phlog' => 'error/phlog.php',
	@@ -1128,6 +1143,16 @@
	'ArcanistCommentSpacingXHPASTLinterRule' => 'ArcanistXHPASTLinterRule',
	'ArcanistCommentStyleXHPASTLinterRule' => 'ArcanistXHPASTLinterRule',
	'ArcanistCommentStyleXHPASTLinterRuleTestCase' => 'ArcanistXHPASTLinterRuleTestCase',
	+ 'ArcanistCommitGraph' => 'Phobject',
	+ 'ArcanistCommitGraphPartition' => 'Phobject',
	+ 'ArcanistCommitGraphPartitionQuery' => 'Phobject',
	+ 'ArcanistCommitGraphQuery' => 'Phobject',
	+ 'ArcanistCommitGraphSet' => 'Phobject',
	+ 'ArcanistCommitGraphSetQuery' => 'Phobject',
	+ 'ArcanistCommitGraphSetTreeView' => 'Phobject',
	+ 'ArcanistCommitGraphSetView' => 'Phobject',
	+ 'ArcanistCommitGraphTestCase' => 'PhutilTestCase',
	+ 'ArcanistCommitNode' => 'Phobject',
	'ArcanistCommitRef' => 'ArcanistRef',
	'ArcanistCommitSymbolRef' => 'ArcanistSymbolRef',
	'ArcanistCommitSymbolRefInspector' => 'ArcanistRefInspector',
	@@ -1233,6 +1258,7 @@
	'ArcanistGeneratedLinterTestCase' => 'ArcanistLinterTestCase',
	'ArcanistGetConfigWorkflow' => 'ArcanistWorkflow',
	'ArcanistGitAPI' => 'ArcanistRepositoryAPI',
	+ 'ArcanistGitCommitGraphQuery' => 'ArcanistCommitGraphQuery',
	'ArcanistGitCommitMessageHardpointQuery' => 'ArcanistWorkflowGitHardpointQuery',
	'ArcanistGitCommitSymbolCommitHardpointQuery' => 'ArcanistWorkflowGitHardpointQuery',
	'ArcanistGitLandEngine' => 'ArcanistLandEngine',
	@@ -1351,6 +1377,7 @@
	'ArcanistMarkerRef' => 'ArcanistRef',
	'ArcanistMarkersWorkflow' => 'ArcanistArcWorkflow',
	'ArcanistMercurialAPI' => 'ArcanistRepositoryAPI',
	+ 'ArcanistMercurialCommitGraphQuery' => 'ArcanistCommitGraphQuery',
	'ArcanistMercurialCommitMessageHardpointQuery' => 'ArcanistWorkflowMercurialHardpointQuery',
	'ArcanistMercurialLandEngine' => 'ArcanistLandEngine',
	'ArcanistMercurialLocalState' => 'ArcanistRepositoryLocalState',
	@@ -1483,6 +1510,7 @@
	'ArcanistSetting' => 'Phobject',
	'ArcanistSettings' => 'Phobject',
	'ArcanistShellCompleteWorkflow' => 'ArcanistWorkflow',
	+ 'ArcanistSimpleCommitGraphQuery' => 'ArcanistCommitGraphQuery',
	'ArcanistSimpleSymbolHardpointQuery' => 'ArcanistRuntimeHardpointQuery',
	'ArcanistSimpleSymbolRef' => 'ArcanistSymbolRef',
	'ArcanistSimpleSymbolRefInspector' => 'ArcanistRefInspector',
	diff --git a/src/repository/api/ArcanistGitAPI.php b/src/repository/api/ArcanistGitAPI.php
	--- a/src/repository/api/ArcanistGitAPI.php
	+++ b/src/repository/api/ArcanistGitAPI.php
	@@ -1763,4 +1763,8 @@
	return new ArcanistGitRepositoryMarkerQuery();
	}

	+ protected function newCommitGraphQueryTemplate() {
	+ return new ArcanistGitCommitGraphQuery();
	+ }
	+
	}
	diff --git a/src/repository/api/ArcanistMercurialAPI.php b/src/repository/api/ArcanistMercurialAPI.php
	--- a/src/repository/api/ArcanistMercurialAPI.php
	+++ b/src/repository/api/ArcanistMercurialAPI.php
	@@ -1026,4 +1026,8 @@
	);
	}

	+ protected function newCommitGraphQueryTemplate() {
	+ return new ArcanistMercurialCommitGraphQuery();
	+ }
	+
	}
	diff --git a/src/repository/api/ArcanistRepositoryAPI.php b/src/repository/api/ArcanistRepositoryAPI.php
	--- a/src/repository/api/ArcanistRepositoryAPI.php
	+++ b/src/repository/api/ArcanistRepositoryAPI.php
	@@ -42,6 +42,7 @@
	private $runtime;
	private $currentWorkingCopyStateRef = false;
	private $currentCommitRef = false;
	+ private $graph;

	abstract public function getSourceControlSystemName();

	@@ -794,8 +795,25 @@
	throw new PhutilMethodNotImplementedException();
	}

	+ final public function newCommitGraphQuery() {
	+ return id($this->newCommitGraphQueryTemplate());
	+ }
	+
	+ protected function newCommitGraphQueryTemplate() {
	+ throw new PhutilMethodNotImplementedException();
	+ }
	+
	final public function getDisplayHash($hash) {
	return substr($hash, 0, 12);
	}

	+ final public function getGraph() {
	+ if (!$this->graph) {
	+ $this->graph = id(new ArcanistCommitGraph())
	+ ->setRepositoryAPI($this);
	+ }
	+
	+ return $this->graph;
	+ }
	+
	}
	diff --git a/src/repository/graph/ArcanistCommitGraph.php b/src/repository/graph/ArcanistCommitGraph.php
	new file mode 100644
	--- /dev/null
	+++ b/src/repository/graph/ArcanistCommitGraph.php
	@@ -0,0 +1,55 @@
	+<?php
	+
	+final class ArcanistCommitGraph
	+ extends Phobject {
	+
	+ private $repositoryAPI;
	+ private $nodes = array();
	+
	+ public function setRepositoryAPI(ArcanistRepositoryAPI $api) {
	+ $this->repositoryAPI = $api;
	+ return $this;
	+ }
	+
	+ public function getRepositoryAPI() {
	+ return $this->repositoryAPI;
	+ }
	+
	+ public function getNode($hash) {
	+ if (isset($this->nodes[$hash])) {
	+ return $this->nodes[$hash];
	+ } else {
	+ return null;
	+ }
	+ }
	+
	+ public function getNodes() {
	+ return $this->nodes;
	+ }
	+
	+ public function newQuery() {
	+ $api = $this->getRepositoryAPI();
	+ return $api->newCommitGraphQuery()
	+ ->setGraph($this);
	+ }
	+
	+ public function newNode($hash) {
	+ if (isset($this->nodes[$hash])) {
	+ throw new Exception(
	+ pht(
	+ 'Graph already has a node "%s"!',
	+ $hash));
	+ }
	+
	+ $this->nodes[$hash] = id(new ArcanistCommitNode())
	+ ->setCommitHash($hash);
	+
	+ return $this->nodes[$hash];
	+ }
	+
	+ public function newPartitionQuery() {
	+ return id(new ArcanistCommitGraphPartitionQuery())
	+ ->setGraph($this);
	+ }
	+
	+}
	diff --git a/src/repository/graph/ArcanistCommitGraphPartition.php b/src/repository/graph/ArcanistCommitGraphPartition.php
	new file mode 100644
	--- /dev/null
	+++ b/src/repository/graph/ArcanistCommitGraphPartition.php
	@@ -0,0 +1,62 @@
	+<?php
	+
	+final class ArcanistCommitGraphPartition
	+ extends Phobject {
	+
	+ private $graph;
	+ private $hashes = array();
	+ private $heads = array();
	+ private $tails = array();
	+ private $waypoints = array();
	+
	+ public function setGraph(ArcanistCommitGraph $graph) {
	+ $this->graph = $graph;
	+ return $this;
	+ }
	+
	+ public function getGraph() {
	+ return $this->graph;
	+ }
	+
	+ public function setHashes(array $hashes) {
	+ $this->hashes = $hashes;
	+ return $this;
	+ }
	+
	+ public function getHashes() {
	+ return $this->hashes;
	+ }
	+
	+ public function setHeads(array $heads) {
	+ $this->heads = $heads;
	+ return $this;
	+ }
	+
	+ public function getHeads() {
	+ return $this->heads;
	+ }
	+
	+ public function setTails($tails) {
	+ $this->tails = $tails;
	+ return $this;
	+ }
	+
	+ public function getTails() {
	+ return $this->tails;
	+ }
	+
	+ public function setWaypoints($waypoints) {
	+ $this->waypoints = $waypoints;
	+ return $this;
	+ }
	+
	+ public function getWaypoints() {
	+ return $this->waypoints;
	+ }
	+
	+ public function newSetQuery() {
	+ return id(new ArcanistCommitGraphSetQuery())
	+ ->setPartition($this);
	+ }
	+
	+}
	diff --git a/src/repository/graph/ArcanistCommitGraphPartitionQuery.php b/src/repository/graph/ArcanistCommitGraphPartitionQuery.php
	new file mode 100644
	--- /dev/null
	+++ b/src/repository/graph/ArcanistCommitGraphPartitionQuery.php
	@@ -0,0 +1,153 @@
	+<?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;
	+ }
	+
	+}
	diff --git a/src/repository/graph/ArcanistCommitGraphSet.php b/src/repository/graph/ArcanistCommitGraphSet.php
	new file mode 100644
	--- /dev/null
	+++ b/src/repository/graph/ArcanistCommitGraphSet.php
	@@ -0,0 +1,97 @@
	+<?php
	+
	+final class ArcanistCommitGraphSet
	+ extends Phobject {
	+
	+ private $setID;
	+ private $color;
	+ private $hashes;
	+ private $parentHashes;
	+ private $childHashes;
	+ private $parentSets;
	+ private $childSets;
	+ private $displayDepth;
	+ private $displayChildSets;
	+
	+ public function setColor($color) {
	+ $this->color = $color;
	+ return $this;
	+ }
	+
	+ public function getColor() {
	+ return $this->color;
	+ }
	+
	+ public function setHashes($hashes) {
	+ $this->hashes = $hashes;
	+ return $this;
	+ }
	+
	+ public function getHashes() {
	+ return $this->hashes;
	+ }
	+
	+ public function setSetID($set_id) {
	+ $this->setID = $set_id;
	+ return $this;
	+ }
	+
	+ public function getSetID() {
	+ return $this->setID;
	+ }
	+
	+ public function setParentHashes($parent_hashes) {
	+ $this->parentHashes = $parent_hashes;
	+ return $this;
	+ }
	+
	+ public function getParentHashes() {
	+ return $this->parentHashes;
	+ }
	+
	+ public function setChildHashes($child_hashes) {
	+ $this->childHashes = $child_hashes;
	+ return $this;
	+ }
	+
	+ public function getChildHashes() {
	+ return $this->childHashes;
	+ }
	+
	+ public function setParentSets($parent_sets) {
	+ $this->parentSets = $parent_sets;
	+ return $this;
	+ }
	+
	+ public function getParentSets() {
	+ return $this->parentSets;
	+ }
	+
	+ public function setChildSets($child_sets) {
	+ $this->childSets = $child_sets;
	+ return $this;
	+ }
	+
	+ public function getChildSets() {
	+ return $this->childSets;
	+ }
	+
	+ public function setDisplayDepth($display_depth) {
	+ $this->displayDepth = $display_depth;
	+ return $this;
	+ }
	+
	+ public function getDisplayDepth() {
	+ return $this->displayDepth;
	+ }
	+
	+ public function setDisplayChildSets(array $display_child_sets) {
	+ $this->displayChildSets = $display_child_sets;
	+ return $this;
	+ }
	+
	+ public function getDisplayChildSets() {
	+ return $this->displayChildSets;
	+ }
	+
	+}
	diff --git a/src/repository/graph/ArcanistCommitGraphSetQuery.php b/src/repository/graph/ArcanistCommitGraphSetQuery.php
	new file mode 100644
	--- /dev/null
	+++ b/src/repository/graph/ArcanistCommitGraphSetQuery.php
	@@ -0,0 +1,305 @@
	+<?php
	+
	+final class ArcanistCommitGraphSetQuery
	+ extends Phobject {
	+
	+ private $partition;
	+ private $waypointMap;
	+ private $visitedDisplaySets;
	+
	+ public function setPartition($partition) {
	+ $this->partition = $partition;
	+ return $this;
	+ }
	+
	+ public function getPartition() {
	+ return $this->partition;
	+ }
	+
	+ public function setWaypointMap(array $waypoint_map) {
	+ $this->waypointMap = $waypoint_map;
	+ return $this;
	+ }
	+
	+ public function getWaypointMap() {
	+ return $this->waypointMap;
	+ }
	+
	+ public function execute() {
	+ $partition = $this->getPartition();
	+ $graph = $partition->getGraph();
	+
	+ $waypoint_color = array();
	+ $color = array();
	+
	+ $waypoints = $this->getWaypointMap();
	+ foreach ($waypoints as $waypoint => $colors) {
	+ // TODO: Validate that "$waypoint" is in the partition.
	+ // TODO: Validate that "$colors" is a list of scalars.
	+ $waypoint_color[$waypoint] = $this->newColorFromRaw($colors);
	+ }
	+
	+ $stack = array();
	+
	+ $hashes = $partition->getTails();
	+ foreach ($hashes as $hash) {
	+ $stack[] = $graph->getNode($hash);
	+
	+ if (isset($waypoint_color[$hash])) {
	+ $color[$hash] = $waypoint_color[$hash];
	+ } else {
	+ $color[$hash] = true;
	+ }
	+ }
	+
	+ $partition_map = $partition->getHashes();
	+
	+ $wait = array();
	+ foreach ($partition_map as $hash) {
	+ $node = $graph->getNode($hash);
	+
	+ $incoming = $node->getParentNodes();
	+ if (count($incoming) < 2) {
	+ // If the node has one or fewer incoming edges, we can paint it as soon
	+ // as we reach it.
	+ continue;
	+ }
	+
	+ // Discard incoming edges which aren't in the partition.
	+ $need = array();
	+ foreach ($incoming as $incoming_node) {
	+ $incoming_hash = $incoming_node->getCommitHash();
	+
	+ if (!isset($partition_map[$incoming_hash])) {
	+ continue;
	+ }
	+
	+ $need[] = $incoming_hash;
	+ }
	+
	+ $need_count = count($need);
	+ if ($need_count < 2) {
	+ // If we have one or fewer incoming edges in the partition, we can
	+ // paint as soon as we reach the node.
	+ continue;
	+ }
	+
	+ $wait[$hash] = $need_count;
	+ }
	+
	+ while ($stack) {
	+ $node = array_pop($stack);
	+ $node_hash = $node->getCommitHash();
	+
	+ $node_color = $color[$node_hash];
	+
	+ $outgoing_nodes = $node->getChildNodes();
	+
	+ foreach ($outgoing_nodes as $outgoing_node) {
	+ $outgoing_hash = $outgoing_node->getCommitHash();
	+
	+ if (isset($waypoint_color[$outgoing_hash])) {
	+ $color[$outgoing_hash] = $waypoint_color[$outgoing_hash];
	+ } else if (isset($color[$outgoing_hash])) {
	+ $color[$outgoing_hash] = $this->newColorFromColors(
	+ $color[$outgoing_hash],
	+ $node_color);
	+ } else {
	+ $color[$outgoing_hash] = $node_color;
	+ }
	+
	+ if (isset($wait[$outgoing_hash])) {
	+ $wait[$outgoing_hash]--;
	+ if ($wait[$outgoing_hash]) {
	+ continue;
	+ }
	+ unset($wait[$outgoing_hash]);
	+ }
	+
	+ $stack[] = $outgoing_node;
	+ }
	+ }
	+
	+ if ($wait) {
	+ throw new Exception(
	+ pht(
	+ 'Did not reach every wait node??'));
	+ }
	+
	+ // Now, we've colored the entire graph. Collect contiguous pieces of it
	+ // with the same color into sets.
	+
	+ static $set_n = 1;
	+
	+ $seen = array();
	+ $sets = array();
	+ foreach ($color as $hash => $node_color) {
	+ if (isset($seen[$hash])) {
	+ continue;
	+ }
	+
	+ $seen[$hash] = true;
	+
	+ $in_set = array();
	+ $in_set[$hash] = true;
	+
	+ $stack = array();
	+ $stack[] = $graph->getNode($hash);
	+
	+ while ($stack) {
	+ $node = array_pop($stack);
	+ $node_hash = $node->getCommitHash();
	+
	+ $nearby = array();
	+ foreach ($node->getParentNodes() as $nearby_node) {
	+ $nearby[] = $nearby_node;
	+ }
	+ foreach ($node->getChildNodes() as $nearby_node) {
	+ $nearby[] = $nearby_node;
	+ }
	+
	+ foreach ($nearby as $nearby_node) {
	+ $nearby_hash = $nearby_node->getCommitHash();
	+
	+ if (isset($seen[$nearby_hash])) {
	+ continue;
	+ }
	+
	+ if (idx($color, $nearby_hash) !== $node_color) {
	+ continue;
	+ }
	+
	+ $seen[$nearby_hash] = true;
	+ $in_set[$nearby_hash] = true;
	+ $stack[] = $nearby_node;
	+ }
	+ }
	+
	+ $set = id(new ArcanistCommitGraphSet())
	+ ->setSetID($set_n++)
	+ ->setColor($node_color)
	+ ->setHashes(array_keys($in_set));
	+
	+ $sets[] = $set;
	+ }
	+
	+ $set_map = array();
	+ foreach ($sets as $set) {
	+ foreach ($set->getHashes() as $hash) {
	+ $set_map[$hash] = $set;
	+ }
	+ }
	+
	+ foreach ($sets as $set) {
	+ $parents = array();
	+ $children = array();
	+
	+ foreach ($set->getHashes() as $hash) {
	+ $node = $graph->getNode($hash);
	+
	+ foreach ($node->getParentNodes() as $edge => $ignored) {
	+ if (isset($set_map[$edge])) {
	+ if ($set_map[$edge] === $set) {
	+ continue;
	+ }
	+ }
	+
	+ $parents[$edge] = true;
	+ }
	+
	+ foreach ($node->getChildNodes() as $edge => $ignored) {
	+ if (isset($set_map[$edge])) {
	+ if ($set_map[$edge] === $set) {
	+ continue;
	+ }
	+ }
	+
	+ $children[$edge] = true;
	+ }
	+
	+ $parent_sets = array();
	+ foreach ($parents as $edge => $ignored) {
	+ if (!isset($set_map[$edge])) {
	+ continue;
	+ }
	+
	+ $adjacent_set = $set_map[$edge];
	+ $parent_sets[$adjacent_set->getSetID()] = $adjacent_set;
	+ }
	+
	+ $child_sets = array();
	+ foreach ($children as $edge => $ignored) {
	+ if (!isset($set_map[$edge])) {
	+ continue;
	+ }
	+
	+ $adjacent_set = $set_map[$edge];
	+ $child_sets[$adjacent_set->getSetID()] = $adjacent_set;
	+ }
	+ }
	+
	+ $set
	+ ->setParentHashes(array_keys($parents))
	+ ->setChildHashes(array_keys($children))
	+ ->setParentSets($parent_sets)
	+ ->setChildSets($child_sets);
	+ }
	+
	+ $this->buildDisplayLayout($sets);
	+
	+ return $sets;
	+ }
	+
	+ private function newColorFromRaw($color) {
	+ return array_fuse($color);
	+ }
	+
	+ private function newColorFromColors($u, $v) {
	+ if ($u === true) {
	+ return $v;
	+ }
	+
	+ if ($v === true) {
	+ return $u;
	+ }
	+
	+ return $u + $v;
	+ }
	+
	+ private function buildDisplayLayout(array $sets) {
	+ $this->visitedDisplaySets = array();
	+ foreach ($sets as $set) {
	+ if (!$set->getParentSets()) {
	+ $this->visitDisplaySet($set);
	+ }
	+ }
	+ }
	+
	+ private function visitDisplaySet(ArcanistCommitGraphSet $set) {
	+ // If at least one parent has not been visited yet, don't visit this
	+ // set. We want to put the set at the deepest depth it is reachable
	+ // from.
	+ foreach ($set->getParentSets() as $parent_id => $parent_set) {
	+ if (!isset($this->visitedDisplaySets[$parent_id])) {
	+ return false;
	+ }
	+ }
	+
	+ $set_id = $set->getSetID();
	+ $this->visitedDisplaySets[$set_id] = true;
	+
	+ $display_children = array();
	+ foreach ($set->getChildSets() as $child_id => $child_set) {
	+ $visited = $this->visitDisplaySet($child_set);
	+ if ($visited) {
	+ $display_children[$child_id] = $child_set;
	+ }
	+ }
	+
	+ $set->setDisplayChildSets($display_children);
	+
	+ return true;
	+ }
	+
	+
	+}
	diff --git a/src/repository/graph/ArcanistCommitNode.php b/src/repository/graph/ArcanistCommitNode.php
	new file mode 100644
	--- /dev/null
	+++ b/src/repository/graph/ArcanistCommitNode.php
	@@ -0,0 +1,78 @@
	+<?php
	+
	+final class ArcanistCommitNode
	+ extends Phobject {
	+
	+ private $commitHash;
	+ private $childNodes = array();
	+ private $parentNodes = array();
	+ private $commitRef;
	+ private $commitMessage;
	+ private $commitEpoch;
	+
	+ public function setCommitHash($commit_hash) {
	+ $this->commitHash = $commit_hash;
	+ return $this;
	+ }
	+
	+ public function getCommitHash() {
	+ return $this->commitHash;
	+ }
	+
	+ public function addChildNode(ArcanistCommitNode $node) {
	+ $this->childNodes[$node->getCommitHash()] = $node;
	+ return $this;
	+ }
	+
	+ public function setChildNodes(array $nodes) {
	+ $this->childNodes = $nodes;
	+ return $this;
	+ }
	+
	+ public function getChildNodes() {
	+ return $this->childNodes;
	+ }
	+
	+ public function addParentNode(ArcanistCommitNode $node) {
	+ $this->parentNodes[$node->getCommitHash()] = $node;
	+ return $this;
	+ }
	+
	+ public function setParentNodes(array $nodes) {
	+ $this->parentNodes = $nodes;
	+ return $this;
	+ }
	+
	+ public function getParentNodes() {
	+ return $this->parentNodes;
	+ }
	+
	+ public function setCommitMessage($commit_message) {
	+ $this->commitMessage = $commit_message;
	+ return $this;
	+ }
	+
	+ public function getCommitMessage() {
	+ return $this->commitMessage;
	+ }
	+
	+ public function getCommitRef() {
	+ if ($this->commitRef === null) {
	+ $this->commitRef = id(new ArcanistCommitRef())
	+ ->setCommitHash($this->getCommitHash())
	+ ->attachMessage($this->getCommitMessage());
	+ }
	+
	+ return $this->commitRef;
	+ }
	+
	+ public function setCommitEpoch($commit_epoch) {
	+ $this->commitEpoch = $commit_epoch;
	+ return $this;
	+ }
	+
	+ public function getCommitEpoch() {
	+ return $this->commitEpoch;
	+ }
	+
	+}
	diff --git a/src/repository/graph/__tests__/ArcanistCommitGraphTestCase.php b/src/repository/graph/__tests__/ArcanistCommitGraphTestCase.php
	new file mode 100644
	--- /dev/null
	+++ b/src/repository/graph/__tests__/ArcanistCommitGraphTestCase.php
	@@ -0,0 +1,56 @@
	+<?php
	+
	+final class ArcanistCommitGraphTestCase
	+ extends PhutilTestCase {
	+
	+ public function testGraphQuery() {
	+ $this->assertPartitionCount(
	+ 1,
	+ pht('Simple Graph'),
	+ array('D'),
	+ 'A>B B>C C>D');
	+
	+ $this->assertPartitionCount(
	+ 1,
	+ pht('Multiple Heads'),
	+ array('D', 'E'),
	+ 'A>B B>C C>D C>E');
	+
	+ $this->assertPartitionCount(
	+ 1,
	+ pht('Disjoint Graph, One Head'),
	+ array('B'),
	+ 'A>B C>D');
	+
	+ $this->assertPartitionCount(
	+ 2,
	+ pht('Disjoint Graph, Two Heads'),
	+ array('B', 'D'),
	+ 'A>B C>D');
	+
	+ $this->assertPartitionCount(
	+ 1,
	+ pht('Complex Graph'),
	+ array('A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K'),
	+ 'A>B B>C B>D B>E E>F E>G E>H C>H A>I C>I B>J J>K I>K');
	+ }
	+
	+ private function assertPartitionCount($expect, $name, $heads, $corpus) {
	+ $graph = new ArcanistCommitGraph();
	+
	+ $query = id(new ArcanistSimpleCommitGraphQuery())
	+ ->setGraph($graph);
	+
	+ $query->setCorpus($corpus)->execute();
	+
	+ $partitions = $graph->newPartitionQuery()
	+ ->withHeads($heads)
	+ ->execute();
	+
	+ $this->assertEqual(
	+ $expect,
	+ count($partitions),
	+ pht('Partition Count for "%s"', $name));
	+ }
	+
	+}
	diff --git a/src/repository/graph/query/ArcanistCommitGraphQuery.php b/src/repository/graph/query/ArcanistCommitGraphQuery.php
	new file mode 100644
	--- /dev/null
	+++ b/src/repository/graph/query/ArcanistCommitGraphQuery.php
	@@ -0,0 +1,69 @@
	+<?php
	+
	+abstract class ArcanistCommitGraphQuery
	+ extends Phobject {
	+
	+ private $graph;
	+ private $headHashes;
	+ private $tailHashes;
	+ private $exactHashes;
	+ private $stopAtGCA;
	+ private $limit;
	+
	+ final public function setGraph(ArcanistCommitGraph $graph) {
	+ $this->graph = $graph;
	+ return $this;
	+ }
	+
	+ final public function getGraph() {
	+ return $this->graph;
	+ }
	+
	+ final public function withHeadHashes(array $hashes) {
	+ $this->headHashes = $hashes;
	+ return $this;
	+ }
	+
	+ final protected function getHeadHashes() {
	+ return $this->headHashes;
	+ }
	+
	+ final public function withTailHashes(array $hashes) {
	+ $this->tailHashes = $hashes;
	+ return $this;
	+ }
	+
	+ final protected function getTailHashes() {
	+ return $this->tailHashes;
	+ }
	+
	+ final public function withExactHashes(array $hashes) {
	+ $this->exactHashes = $hashes;
	+ return $this;
	+ }
	+
	+ final protected function getExactHashes() {
	+ return $this->exactHashes;
	+ }
	+
	+ final public function withStopAtGCA($stop_gca) {
	+ $this->stopAtGCA = $stop_gca;
	+ return $this;
	+ }
	+
	+ final public function setLimit($limit) {
	+ $this->limit = $limit;
	+ return $this;
	+ }
	+
	+ final protected function getLimit() {
	+ return $this->limit;
	+ }
	+
	+ final public function getRepositoryAPI() {
	+ return $this->getGraph()->getRepositoryAPI();
	+ }
	+
	+ abstract public function execute();
	+
	+}
	diff --git a/src/repository/graph/query/ArcanistGitCommitGraphQuery.php b/src/repository/graph/query/ArcanistGitCommitGraphQuery.php
	new file mode 100644
	--- /dev/null
	+++ b/src/repository/graph/query/ArcanistGitCommitGraphQuery.php
	@@ -0,0 +1,150 @@
	+<?php
	+
	+final class ArcanistGitCommitGraphQuery
	+ extends ArcanistCommitGraphQuery {
	+
	+ private $queryFuture;
	+ private $seen = array();
	+
	+ public function execute() {
	+ $this->beginExecute();
	+ $this->continueExecute();
	+
	+ return $this->seen;
	+ }
	+
	+ protected function beginExecute() {
	+ $head_hashes = $this->getHeadHashes();
	+ $exact_hashes = $this->getExactHashes();
	+
	+ if (!$head_hashes && !$exact_hashes) {
	+ throw new Exception(pht('Need head hashes or exact hashes!'));
	+ }
	+
	+ $api = $this->getRepositoryAPI();
	+
	+ $refs = array();
	+ if ($head_hashes !== null) {
	+ foreach ($head_hashes as $hash) {
	+ $refs[] = $hash;
	+ }
	+ }
	+
	+ $tail_hashes = $this->getTailHashes();
	+ if ($tail_hashes !== null) {
	+ foreach ($tail_hashes as $tail_hash) {
	+ $refs[] = sprintf('^%s^@', $tail_hash);
	+ }
	+ }
	+
	+ if ($exact_hashes !== null) {
	+ if (count($exact_hashes) > 1) {
	+ // If "A" is a parent of "B" and we search for exact hashes ["A", "B"],
	+ // the exclusion rule generated by "^B^@" is stronger than the inclusion
	+ // rule generated by "A" and we don't get "A" in the result set.
	+ throw new Exception(
	+ pht(
	+ 'TODO: Multiple exact hashes not supported under Git.'));
	+ }
	+ foreach ($exact_hashes as $exact_hash) {
	+ $refs[] = $exact_hash;
	+ $refs[] = sprintf('^%s^@', $exact_hash);
	+ }
	+ }
	+
	+ $refs[] = '--';
	+ $refs = implode("\n", $refs)."\n";
	+
	+ $fields = array(
	+ '%e',
	+ '%H',
	+ '%P',
	+ '%ct',
	+ '%B',
	+ );
	+
	+ $format = implode('%x02', $fields).'%x01';
	+
	+ $future = $api->newFuture(
	+ 'log --format=%s --stdin',
	+ $format);
	+ $future->write($refs);
	+ $future->setResolveOnError(true);
	+ $future->start();
	+
	+ $lines = id(new LinesOfALargeExecFuture($future))
	+ ->setDelimiter("\1");
	+ $lines->rewind();
	+
	+ $this->queryFuture = $lines;
	+ }
	+
	+ protected function continueExecute() {
	+ $graph = $this->getGraph();
	+ $limit = $this->getLimit();
	+
	+ $lines = $this->queryFuture;
	+
	+ while (true) {
	+ if (!$lines->valid()) {
	+ return false;
	+ }
	+
	+ $line = $lines->current();
	+ $lines->next();
	+
	+ if ($line === "\n") {
	+ continue;
	+ }
	+
	+ $fields = explode("\2", $line);
	+
	+ if (count($fields) !== 5) {
	+ throw new Exception(
	+ pht(
	+ 'Failed to split line "%s" from "git log".',
	+ $line));
	+ }
	+
	+ list($encoding, $hash, $parents, $commit_epoch, $message) = $fields;
	+
	+ // TODO: Handle encoding, see DiffusionLowLevelCommitQuery.
	+
	+ $node = $graph->getNode($hash);
	+ if (!$node) {
	+ $node = $graph->newNode($hash);
	+ }
	+
	+ $this->seen[$hash] = $node;
	+
	+ $node
	+ ->setCommitMessage($message)
	+ ->setCommitEpoch((int)$commit_epoch);
	+
	+ if (strlen($parents)) {
	+ $parents = explode(' ', $parents);
	+
	+ $parent_nodes = array();
	+ foreach ($parents as $parent) {
	+ $parent_node = $graph->getNode($parent);
	+ if (!$parent_node) {
	+ $parent_node = $graph->newNode($parent);
	+ }
	+
	+ $parent_nodes[$parent] = $parent_node;
	+ $parent_node->addChildNode($node);
	+ }
	+ $node->setParentNodes($parent_nodes);
	+ } else {
	+ $parents = array();
	+ }
	+
	+ if ($limit) {
	+ if (count($this->seen) >= $limit) {
	+ break;
	+ }
	+ }
	+ }
	+ }
	+
	+}
	diff --git a/src/repository/graph/query/ArcanistMercurialCommitGraphQuery.php b/src/repository/graph/query/ArcanistMercurialCommitGraphQuery.php
	new file mode 100644
	--- /dev/null
	+++ b/src/repository/graph/query/ArcanistMercurialCommitGraphQuery.php
	@@ -0,0 +1,180 @@
	+<?php
	+
	+final class ArcanistMercurialCommitGraphQuery
	+ extends ArcanistCommitGraphQuery {
	+
	+ private $seen = array();
	+ private $queryFuture;
	+
	+ public function execute() {
	+ $this->beginExecute();
	+ $this->continueExecute();
	+
	+ return $this->seen;
	+ }
	+
	+ protected function beginExecute() {
	+ $head_hashes = $this->getHeadHashes();
	+ $exact_hashes = $this->getExactHashes();
	+
	+ if (!$head_hashes && !$exact_hashes) {
	+ throw new Exception(pht('Need head hashes or exact hashes!'));
	+ }
	+
	+ $api = $this->getRepositoryAPI();
	+
	+ $revsets = array();
	+ if ($head_hashes !== null) {
	+ $revs = array();
	+ foreach ($head_hashes as $hash) {
	+ $revs[] = hgsprintf(
	+ 'ancestors(%s)',
	+ $hash);
	+ }
	+ $revsets[] = $this->joinOrRevsets($revs);
	+ }
	+
	+ $tail_hashes = $this->getTailHashes();
	+ if ($tail_hashes !== null) {
	+ $revs = array();
	+ foreach ($tail_hashes as $tail_hash) {
	+ $revs[] = hgsprintf(
	+ 'descendants(%s)',
	+ $tail_hash);
	+ }
	+ $revsets[] = $this->joinOrRevsets($revs);
	+ }
	+
	+ if ($revsets) {
	+ $revsets = array(
	+ $this->joinAndRevsets($revs),
	+ );
	+ }
	+
	+ if ($exact_hashes !== null) {
	+ $revs = array();
	+ foreach ($exact_hashes as $exact_hash) {
	+ $revs[] = hgsprintf(
	+ '%s',
	+ $exact_hash);
	+ }
	+ $revsets[] = array(
	+ $this->joinOrRevsets($revs),
	+ );
	+ }
	+
	+ $revsets = $this->joinOrRevsets($revs);
	+
	+ $fields = array(
	+ '', // Placeholder for "encoding".
	+ '{node}',
	+ '{parents}',
	+ '{date\|rfc822date}',
	+ '{description\|utf8}',
	+ );
	+
	+ $template = implode("\2", $fields)."\1";
	+
	+ $future = $api->newFuture(
	+ 'log --rev %s --template %s --',
	+ $revsets,
	+ $template);
	+ $future->setResolveOnError(true);
	+ $future->start();
	+
	+ $lines = id(new LinesOfALargeExecFuture($future))
	+ ->setDelimiter("\1");
	+ $lines->rewind();
	+
	+ $this->queryFuture = $lines;
	+ }
	+
	+ protected function continueExecute() {
	+ $graph = $this->getGraph();
	+ $lines = $this->queryFuture;
	+ $limit = $this->getLimit();
	+ while (true) {
	+ if (!$lines->valid()) {
	+ return false;
	+ }
	+
	+ $line = $lines->current();
	+ $lines->next();
	+
	+ if ($line === "\n") {
	+ continue;
	+ }
	+
	+ $fields = explode("\2", $line);
	+
	+ if (count($fields) !== 5) {
	+ throw new Exception(
	+ pht(
	+ 'Failed to split line "%s" from "git log".',
	+ $line));
	+ }
	+
	+ list($encoding, $hash, $parents, $commit_epoch, $message) = $fields;
	+
	+ $node = $graph->getNode($hash);
	+ if (!$node) {
	+ $node = $graph->newNode($hash);
	+ }
	+
	+ $this->seen[$hash] = $node;
	+
	+ $node
	+ ->setCommitMessage($message)
	+ ->setCommitEpoch((int)strtotime($commit_epoch));
	+
	+ if (strlen($parents)) {
	+ $parents = explode(' ', $parents);
	+
	+ $parent_nodes = array();
	+ foreach ($parents as $parent) {
	+ $parent_node = $graph->getNode($parent);
	+ if (!$parent_node) {
	+ $parent_node = $graph->newNode($parent);
	+ }
	+
	+ $parent_nodes[$parent] = $parent_node;
	+ $parent_node->addChildNode($node);
	+ }
	+ $node->setParentNodes($parent_nodes);
	+ } else {
	+ $parents = array();
	+ }
	+
	+ if ($limit) {
	+ if (count($this->seen) >= $limit) {
	+ break;
	+ }
	+ }
	+ }
	+ }
	+
	+ private function joinOrRevsets(array $revsets) {
	+ return $this->joinRevsets($revsets, false);
	+ }
	+
	+ private function joinAndRevsets(array $revsets) {
	+ return $this->joinRevsets($revsets, true);
	+ }
	+
	+ private function joinRevsets(array $revsets, $is_and) {
	+ if (!$revsets) {
	+ return array();
	+ }
	+
	+ if (count($revsets) === 1) {
	+ return head($revsets);
	+ }
	+
	+ if ($is_and) {
	+ return '('.implode(' and ', $revsets).')';
	+ } else {
	+ return '('.implode(' or ', $revsets).')';
	+ }
	+ }
	+
	+}
	diff --git a/src/repository/graph/query/ArcanistSimpleCommitGraphQuery.php b/src/repository/graph/query/ArcanistSimpleCommitGraphQuery.php
	new file mode 100644
	--- /dev/null
	+++ b/src/repository/graph/query/ArcanistSimpleCommitGraphQuery.php
	@@ -0,0 +1,50 @@
	+<?php
	+
	+final class ArcanistSimpleCommitGraphQuery
	+ extends ArcanistCommitGraphQuery {
	+
	+ private $corpus;
	+
	+ public function setCorpus($corpus) {
	+ $this->corpus = $corpus;
	+ return $this;
	+ }
	+
	+ public function getCorpus() {
	+ return $this->corpus;
	+ }
	+
	+ public function execute() {
	+ $graph = $this->getGraph();
	+ $corpus = $this->getCorpus();
	+
	+ $edges = preg_split('(\s+)', trim($corpus));
	+ foreach ($edges as $edge) {
	+ $matches = null;
	+ $ok = preg_match('(^(?P<parent>\S+)>(?P<child>\S+)\z)', $edge, $matches);
	+ if (!$ok) {
	+ throw new Exception(
	+ pht(
	+ 'Failed to match SimpleCommitGraph directive "%s".',
	+ $edge));
	+ }
	+
	+ $parent = $matches['parent'];
	+ $child = $matches['child'];
	+
	+ $pnode = $graph->getNode($parent);
	+ if (!$pnode) {
	+ $pnode = $graph->newNode($parent);
	+ }
	+
	+ $cnode = $graph->getNode($child);
	+ if (!$cnode) {
	+ $cnode = $graph->newNode($child);
	+ }
	+
	+ $cnode->addParentNode($pnode);
	+ $pnode->addChildNode($cnode);
	+ }
	+ }
	+
	+}
	diff --git a/src/repository/graph/view/ArcanistCommitGraphSetTreeView.php b/src/repository/graph/view/ArcanistCommitGraphSetTreeView.php
	new file mode 100644
	--- /dev/null
	+++ b/src/repository/graph/view/ArcanistCommitGraphSetTreeView.php
	@@ -0,0 +1,147 @@
	+<?php
	+
	+final class ArcanistCommitGraphSetTreeView
	+ extends Phobject {
	+
	+ private $repositoryAPI;
	+ private $rootSet;
	+ private $markers;
	+ private $markerGroups;
	+ private $stateRefs;
	+ private $setViews;
	+
	+ public function setRootSet($root_set) {
	+ $this->rootSet = $root_set;
	+ return $this;
	+ }
	+
	+ public function getRootSet() {
	+ return $this->rootSet;
	+ }
	+
	+ public function setMarkers($markers) {
	+ $this->markers = $markers;
	+ $this->markerGroups = mgroup($markers, 'getCommitHash');
	+ return $this;
	+ }
	+
	+ public function getMarkers() {
	+ return $this->markers;
	+ }
	+
	+ public function setStateRefs($state_refs) {
	+ $this->stateRefs = $state_refs;
	+ return $this;
	+ }
	+
	+ public function getStateRefs() {
	+ return $this->stateRefs;
	+ }
	+
	+ public function setRepositoryAPI($repository_api) {
	+ $this->repositoryAPI = $repository_api;
	+ return $this;
	+ }
	+
	+ public function getRepositoryAPI() {
	+ return $this->repositoryAPI;
	+ }
	+
	+ public function draw() {
	+ $set = $this->getRootSet();
	+
	+ $this->setViews = array();
	+ $view_root = $this->newSetViews($set);
	+ $view_list = $this->setViews;
	+
	+ foreach ($view_list as $view) {
	+ $parent_view = $view->getParentView();
	+ if ($parent_view) {
	+ $depth = $parent_view->getViewDepth() + 1;
	+ } else {
	+ $depth = 0;
	+ }
	+ $view->setViewDepth($depth);
	+ }
	+
	+ $api = $this->getRepositoryAPI();
	+
	+ foreach ($view_list as $view) {
	+ $view_set = $view->getSet();
	+ $hashes = $view_set->getHashes();
	+
	+ $commit_refs = $this->getCommitRefs($hashes);
	+ $revision_refs = $this->getRevisionRefs(head($hashes));
	+ $marker_refs = $this->getMarkerRefs($hashes);
	+
	+ $view
	+ ->setRepositoryAPI($api)
	+ ->setCommitRefs($commit_refs)
	+ ->setRevisionRefs($revision_refs)
	+ ->setMarkerRefs($marker_refs);
	+ }
	+
	+ $rows = array();
	+ foreach ($view_list as $view) {
	+ $rows[] = $view->newCellViews();
	+ }
	+
	+ return $rows;
	+ }
	+
	+ private function newSetViews(ArcanistCommitGraphSet $set) {
	+ $set_view = $this->newSetView($set);
	+
	+ $this->setViews[] = $set_view;
	+
	+ foreach ($set->getDisplayChildSets() as $child_set) {
	+ $child_view = $this->newSetViews($child_set);
	+ $child_view->setParentView($set_view);
	+ $set_view->addChildView($child_view);
	+ }
	+
	+ return $set_view;
	+ }
	+
	+ private function newSetView(ArcanistCommitGraphSet $set) {
	+ return id(new ArcanistCommitGraphSetView())
	+ ->setSet($set);
	+ }
	+
	+ private function getStateRef($hash) {
	+ $state_refs = $this->getStateRefs();
	+
	+ if (!isset($state_refs[$hash])) {
	+ throw new Exception(
	+ pht(
	+ 'Found no state ref for hash "%s".',
	+ $hash));
	+ }
	+
	+ return $state_refs[$hash];
	+ }
	+
	+ private function getRevisionRefs($hash) {
	+ $state_ref = $this->getStateRef($hash);
	+ return $state_ref->getRevisionRefs();
	+ }
	+
	+ private function getCommitRefs(array $hashes) {
	+ $results = array();
	+ foreach ($hashes as $hash) {
	+ $state_ref = $this->getStateRef($hash);
	+ $results[$hash] = $state_ref->getCommitRef();
	+ }
	+
	+ return $results;
	+ }
	+
	+ private function getMarkerRefs(array $hashes) {
	+ $results = array();
	+ foreach ($hashes as $hash) {
	+ $results[$hash] = idx($this->markerGroups, $hash, array());
	+ }
	+ return $results;
	+ }
	+
	+}
	diff --git a/src/repository/graph/view/ArcanistCommitGraphSetView.php b/src/repository/graph/view/ArcanistCommitGraphSetView.php
	new file mode 100644
	--- /dev/null
	+++ b/src/repository/graph/view/ArcanistCommitGraphSetView.php
	@@ -0,0 +1,407 @@
	+<?php
	+
	+final class ArcanistCommitGraphSetView
	+ extends Phobject {
	+
	+ private $repositoryAPI;
	+ private $set;
	+ private $parentView;
	+ private $childViews = array();
	+ private $commitRefs;
	+ private $revisionRefs;
	+ private $markerRefs;
	+ private $viewDepth;
	+
	+ public function setRepositoryAPI(ArcanistRepositoryAPI $repository_api) {
	+ $this->repositoryAPI = $repository_api;
	+ return $this;
	+ }
	+
	+ public function getRepositoryAPI() {
	+ return $this->repositoryAPI;
	+ }
	+
	+ public function setSet(ArcanistCommitGraphSet $set) {
	+ $this->set = $set;
	+ return $this;
	+ }
	+
	+ public function getSet() {
	+ return $this->set;
	+ }
	+
	+ public function setParentView(ArcanistCommitGraphSetView $parent_view) {
	+ $this->parentView = $parent_view;
	+ return $this;
	+ }
	+
	+ public function getParentView() {
	+ return $this->parentView;
	+ }
	+
	+ public function addChildView(ArcanistCommitGraphSetView $child_view) {
	+ $this->childViews[] = $child_view;
	+ return $this;
	+ }
	+
	+ public function setChildViews(array $child_views) {
	+ assert_instances_of($child_views, __CLASS__);
	+ $this->childViews = $child_views;
	+ return $this;
	+ }
	+
	+ public function getChildViews() {
	+ return $this->childViews;
	+ }
	+
	+ public function setCommitRefs($commit_refs) {
	+ $this->commitRefs = $commit_refs;
	+ return $this;
	+ }
	+
	+ public function getCommitRefs() {
	+ return $this->commitRefs;
	+ }
	+
	+ public function setRevisionRefs($revision_refs) {
	+ $this->revisionRefs = $revision_refs;
	+ return $this;
	+ }
	+
	+ public function getRevisionRefs() {
	+ return $this->revisionRefs;
	+ }
	+
	+ public function setMarkerRefs($marker_refs) {
	+ $this->markerRefs = $marker_refs;
	+ return $this;
	+ }
	+
	+ public function getMarkerRefs() {
	+ return $this->markerRefs;
	+ }
	+
	+ public function setViewDepth($view_depth) {
	+ $this->viewDepth = $view_depth;
	+ return $this;
	+ }
	+
	+ public function getViewDepth() {
	+ return $this->viewDepth;
	+ }
	+
	+ public function newCellViews() {
	+ $set = $this->getSet();
	+ $api = $this->getRepositoryAPI();
	+
	+ $commit_refs = $this->getCommitRefs();
	+ $revision_refs = $this->getRevisionRefs();
	+ $marker_refs = $this->getMarkerRefs();
	+
	+ $merge_strings = array();
	+ foreach ($revision_refs as $revision_ref) {
	+ $summary = $revision_ref->getName();
	+ $merge_key = substr($summary, 0, 32);
	+ $merge_key = phutil_utf8_strtolower($merge_key);
	+
	+ $merge_strings[$merge_key][] = $revision_ref;
	+ }
	+
	+ $merge_map = array();
	+ foreach ($commit_refs as $commit_ref) {
	+ $summary = $commit_ref->getSummary();
	+
	+ $merge_with = null;
	+ if (count($revision_refs) === 1) {
	+ $merge_with = head($revision_refs);
	+ } else {
	+ $merge_key = substr($summary, 0, 32);
	+ $merge_key = phutil_utf8_strtolower($merge_key);
	+ if (isset($merge_strings[$merge_key])) {
	+ $merge_refs = $merge_strings[$merge_key];
	+ if (count($merge_refs) === 1) {
	+ $merge_with = head($merge_refs);
	+ }
	+ }
	+ }
	+
	+ if ($merge_with) {
	+ $revision_phid = $merge_with->getPHID();
	+ $merge_map[$revision_phid][] = $commit_ref;
	+ }
	+ }
	+
	+ $revision_map = mpull($revision_refs, null, 'getPHID');
	+
	+ $result_map = array();
	+ foreach ($merge_map as $merge_phid => $merge_refs) {
	+ if (count($merge_refs) !== 1) {
	+ continue;
	+ }
	+
	+ $merge_ref = head($merge_refs);
	+ $commit_hash = $merge_ref->getCommitHash();
	+
	+ $result_map[$commit_hash] = $revision_map[$merge_phid];
	+ }
	+
	+ $object_layout = array();
	+
	+ $merged_map = array_flip(mpull($result_map, 'getPHID'));
	+ foreach ($revision_refs as $revision_ref) {
	+ $revision_phid = $revision_ref->getPHID();
	+ if (isset($merged_map[$revision_phid])) {
	+ continue;
	+ }
	+
	+ $object_layout[] = array(
	+ 'revision' => $revision_ref,
	+ );
	+ }
	+
	+ foreach ($commit_refs as $commit_ref) {
	+ $commit_hash = $commit_ref->getCommitHash();
	+ $revision_ref = idx($result_map, $commit_hash);
	+
	+ $object_layout[] = array(
	+ 'commit' => $commit_ref,
	+ 'revision' => $revision_ref,
	+ );
	+ }
	+
	+ $marker_layout = array();
	+ foreach ($object_layout as $layout) {
	+ $commit_ref = idx($layout, 'commit');
	+ if (!$commit_ref) {
	+ $marker_layout[] = $layout;
	+ continue;
	+ }
	+
	+ $commit_hash = $commit_ref->getCommitHash();
	+ $markers = idx($marker_refs, $commit_hash);
	+ if (!$markers) {
	+ $marker_layout[] = $layout;
	+ continue;
	+ }
	+
	+ $head_marker = array_shift($markers);
	+ $layout['marker'] = $head_marker;
	+ $marker_layout[] = $layout;
	+
	+ if (!$markers) {
	+ continue;
	+ }
	+
	+ foreach ($markers as $marker) {
	+ $marker_layout[] = array(
	+ 'marker' => $marker,
	+ );
	+ }
	+ }
	+
	+ $marker_view = $this->drawMarkerCell($marker_layout);
	+ $commits_view = $this->drawCommitsCell($marker_layout);
	+ $status_view = $this->drawStatusCell($marker_layout);
	+ $revisions_view = $this->drawRevisionsCell($marker_layout);
	+ $messages_view = $this->drawMessagesCell($marker_layout);
	+
	+ return array(
	+ id(new ArcanistGridCell())
	+ ->setKey('marker')
	+ ->setContent($marker_view),
	+ id(new ArcanistGridCell())
	+ ->setKey('commits')
	+ ->setContent($commits_view),
	+ id(new ArcanistGridCell())
	+ ->setKey('status')
	+ ->setContent($status_view),
	+ id(new ArcanistGridCell())
	+ ->setKey('revisions')
	+ ->setContent($revisions_view),
	+ id(new ArcanistGridCell())
	+ ->setKey('messages')
	+ ->setContent($messages_view),
	+ );
	+ }
	+
	+ private function drawMarkerCell(array $items) {
	+ $api = $this->getRepositoryAPI();
	+ $depth = $this->getViewDepth();
	+
	+ $marker_refs = $this->getMarkerRefs();
	+ $commit_refs = $this->getCommitRefs();
	+
	+ if (count($commit_refs) === 1) {
	+ $commit_ref = head($commit_refs);
	+
	+ $commit_hash = $commit_ref->getCommitHash();
	+ $commit_hash = tsprintf(
	+ '%s',
	+ substr($commit_hash, 0, 7));
	+
	+ $commit_label = $commit_hash;
	+ } else {
	+ $min = head($commit_refs);
	+ $max = last($commit_refs);
	+ $commit_label = tsprintf(
	+ '%s..%s',
	+ substr($min->getCommitHash(), 0, 7),
	+ substr($max->getCommitHash(), 0, 7));
	+ }
	+
	+ // TODO: Make this a function of terminal width?
	+
	+ $max_depth = 25;
	+ if ($depth <= $max_depth) {
	+ $indent = str_repeat(' ', ($depth * 2));
	+ } else {
	+ $more = ' ... ';
	+ $indent = str_repeat(' ', ($max_depth * 2) - strlen($more)).$more;
	+ }
	+ $indent .= '- ';
	+
	+ $empty_indent = str_repeat(' ', strlen($indent));
	+
	+ $is_first = true;
	+ $cell = array();
	+ foreach ($items as $item) {
	+ $marker_ref = idx($item, 'marker');
	+
	+ if ($marker_ref) {
	+ if ($marker_ref->getIsActive()) {
	+ $label = tsprintf(
	+ '<bg:green>%s</bg>',
	+ $marker_ref->getName());
	+ } else {
	+ $label = tsprintf(
	+ '%s',
	+ $marker_ref->getName());
	+ }
	+ } else if ($is_first) {
	+ $label = $commit_label;
	+ } else {
	+ $label = '';
	+ }
	+
	+ if ($is_first) {
	+ $indent_text = $indent;
	+ } else {
	+ $indent_text = $empty_indent;
	+ }
	+
	+ $cell[] = tsprintf(
	+ "%s%s\n",
	+ $indent_text,
	+ $label);
	+
	+ $is_first = false;
	+ }
	+
	+ return $cell;
	+ }
	+
	+ private function drawCommitsCell(array $items) {
	+ $cell = array();
	+ foreach ($items as $item) {
	+ $commit_ref = idx($item, 'commit');
	+ if (!$commit_ref) {
	+ $cell[] = tsprintf("\n");
	+ continue;
	+ }
	+
	+ $commit_label = $this->drawCommitLabel($commit_ref);
	+ $cell[] = tsprintf("%s\n", $commit_label);
	+ }
	+
	+ return $cell;
	+ }
	+
	+ private function drawCommitLabel(ArcanistCommitRef $commit_ref) {
	+ $api = $this->getRepositoryAPI();
	+
	+ $hash = $commit_ref->getCommitHash();
	+ $hash = substr($hash, 0, 7);
	+
	+ return tsprintf('%s', $hash);
	+ }
	+
	+ private function drawRevisionsCell(array $items) {
	+ $cell = array();
	+
	+ foreach ($items as $item) {
	+ $revision_ref = idx($item, 'revision');
	+ if (!$revision_ref) {
	+ $cell[] = tsprintf("\n");
	+ continue;
	+ }
	+ $revision_label = $this->drawRevisionLabel($revision_ref);
	+ $cell[] = tsprintf("%s\n", $revision_label);
	+ }
	+
	+ return $cell;
	+ }
	+
	+ private function drawRevisionLabel(ArcanistRevisionRef $revision_ref) {
	+ $api = $this->getRepositoryAPI();
	+
	+ $monogram = $revision_ref->getMonogram();
	+
	+ return tsprintf('%s', $monogram);
	+ }
	+
	+ private function drawMessagesCell(array $items) {
	+ $cell = array();
	+
	+ foreach ($items as $item) {
	+ $revision_ref = idx($item, 'revision');
	+ if ($revision_ref) {
	+ $cell[] = tsprintf("%s\n", $revision_ref->getName());
	+ continue;
	+ }
	+
	+ $commit_ref = idx($item, 'commit');
	+ if ($commit_ref) {
	+ $cell[] = tsprintf("%s\n", $commit_ref->getSummary());
	+ continue;
	+ }
	+
	+ $cell[] = tsprintf("\n");
	+ }
	+
	+ return $cell;
	+ }
	+
	+ private function drawStatusCell(array $items) {
	+ $cell = array();
	+
	+ foreach ($items as $item) {
	+ $revision_ref = idx($item, 'revision');
	+
	+ if (!$revision_ref) {
	+ $cell[] = tsprintf("\n");
	+ continue;
	+ }
	+
	+ $revision_label = $this->drawRevisionStatus($revision_ref);
	+ $cell[] = tsprintf("%s\n", $revision_label);
	+ }
	+
	+ return $cell;
	+ }
	+
	+
	+ private function drawRevisionStatus(ArcanistRevisionRef $revision_ref) {
	+ $status = $revision_ref->getStatusDisplayName();
	+
	+ $ansi_color = $revision_ref->getStatusANSIColor();
	+ if ($ansi_color) {
	+ $status = tsprintf(
	+ sprintf('<fg:%s>%%s</fg>', $ansi_color),
	+ $status);
	+ }
	+
	+ return tsprintf('%s', $status);
	+ }
	+
	+
	+}
	diff --git a/src/utils/utils.php b/src/utils/utils.php
	--- a/src/utils/utils.php
	+++ b/src/utils/utils.php
	@@ -433,6 +433,14 @@
	* @return list Objects ordered by the vectors.
	*/
	function msortv(array $list, $method) {
	+ return msortv_internal($list, $method, SORT_STRING);
	+}
	+
	+function msortv_natural(array $list, $method) {
	+ return msortv_internal($list, $method, SORT_NATURAL \| SORT_FLAG_CASE);
	+}
	+
	+function msortv_internal(array $list, $method, $flags) {
	$surrogate = mpull($list, $method);

	$index = 0;
	@@ -455,7 +463,7 @@
	$surrogate[$key] = (string)$value;
	}

	- asort($surrogate, SORT_STRING);
	+ asort($surrogate, $flags);

	$result = array();
	foreach ($surrogate as $key => $value) {
	diff --git a/src/workflow/ArcanistMarkersWorkflow.php b/src/workflow/ArcanistMarkersWorkflow.php
	--- a/src/workflow/ArcanistMarkersWorkflow.php
	+++ b/src/workflow/ArcanistMarkersWorkflow.php
	@@ -3,6 +3,8 @@
	abstract class ArcanistMarkersWorkflow
	extends ArcanistArcWorkflow {

	+ private $nodes;
	+
	abstract protected function getWorkflowMarkerType();

	public function runWorkflow() {
	@@ -14,96 +16,152 @@
	->withMarkerTypes(array($marker_type))
	->execute();

	- $states = array();
	- foreach ($markers as $marker) {
	+ $tail_hashes = $this->getTailHashes();
	+
	+ $heads = mpull($markers, 'getCommitHash');
	+
	+ $graph = $api->getGraph();
	+ $limit = 1000;
	+
	+ $query = $graph->newQuery()
	+ ->withHeadHashes($heads)
	+ ->setLimit($limit + 1);
	+
	+ if ($tail_hashes) {
	+ $query->withTailHashes($tail_hashes);
	+ }
	+
	+ $nodes = $query->execute();
	+
	+ if (count($nodes) > $limit) {
	+
	+ // TODO: Show what we can.
	+
	+ throw new PhutilArgumentUsageException(
	+ pht(
	+ 'Found more than %s unpublished commits which are ancestors of '.
	+ 'heads.',
	+ new PhutilNumber($limit)));
	+ }
	+
	+ // We may have some markers which point at commits which are already
	+ // published. These markers won't be reached by following heads backwards
	+ // until we reach published commits.
	+
	+ // Load these markers exactly so they don't vanish in the output.
	+
	+ // TODO: Mark these sets as published.
	+
	+ $disjoint_heads = array();
	+ foreach ($heads as $head) {
	+ if (!isset($nodes[$head])) {
	+ $disjoint_heads[] = $head;
	+ }
	+ }
	+
	+ if ($disjoint_heads) {
	+
	+ // TODO: Git currently can not query for more than one exact hash at a
	+ // time.
	+
	+ foreach ($disjoint_heads as $disjoint_head) {
	+ $disjoint_nodes = $graph->newQuery()
	+ ->withExactHashes(array($disjoint_head))
	+ ->execute();
	+
	+ $nodes += $disjoint_nodes;
	+ }
	+ }
	+
	+ $state_refs = array();
	+ foreach ($nodes as $node) {
	+ $commit_ref = $node->getCommitRef();
	+
	$state_ref = id(new ArcanistWorkingCopyStateRef())
	- ->setCommitRef($marker->getCommitRef());
	+ ->setCommitRef($commit_ref);

	- $states[] = array(
	- 'marker' => $marker,
	- 'state' => $state_ref,
	- );
	+ $state_refs[$node->getCommitHash()] = $state_ref;
	}

	$this->loadHardpoints(
	- ipull($states, 'state'),
	+ $state_refs,
	ArcanistWorkingCopyStateRef::HARDPOINT_REVISIONREFS);

	- $vectors = array();
	- foreach ($states as $key => $state) {
	- $marker_ref = $state['marker'];
	- $state_ref = $state['state'];
	-
	- $vector = id(new PhutilSortVector())
	- ->addInt($marker_ref->getIsActive() ? 1 : 0)
	- ->addInt($marker_ref->getEpoch());
	+ $partitions = $graph->newPartitionQuery()
	+ ->withHeads($heads)
	+ ->withHashes(array_keys($nodes))
	+ ->execute();

	- $vectors[$key] = $vector;
	+ $revision_refs = array();
	+ foreach ($state_refs as $hash => $state_ref) {
	+ $revision_ids = mpull($state_ref->getRevisionRefs(), 'getID');
	+ $revision_refs[$hash] = array_fuse($revision_ids);
	}

	- $vectors = msortv($vectors, 'getSelf');
	- $states = array_select_keys($states, array_keys($vectors));
	+ $partition_sets = array();
	+ $partition_vectors = array();
	+ foreach ($partitions as $partition_key => $partition) {
	+ $sets = $partition->newSetQuery()
	+ ->setWaypointMap($revision_refs)
	+ ->execute();
	+
	+ list($sets, $partition_vector) = $this->sortSets(
	+ $graph,
	+ $sets,
	+ $markers);

	- $table = id(new PhutilConsoleTable())
	- ->setShowHeader(false)
	- ->addColumn('active')
	- ->addColumn('name')
	- ->addColumn('status')
	- ->addColumn('description');
	+ $partition_sets[$partition_key] = $sets;
	+ $partition_vectors[$partition_key] = $partition_vector;
	+ }

	- $rows = array();
	- foreach ($states as $state) {
	- $marker_ref = $state['marker'];
	- $state_ref = $state['state'];
	- $revision_ref = null;
	- $commit_ref = $marker_ref->getCommitRef();
	+ $partition_vectors = msortv($partition_vectors, 'getSelf');
	+ $partitions = array_select_keys(
	+ $partitions,
	+ array_keys($partition_vectors));

	- $marker_name = tsprintf('%s', $marker_ref->getName());
	+ $partition_lists = array();
	+ foreach ($partitions as $partition_key => $partition) {
	+ $sets = $partition_sets[$partition_key];

	- if ($state_ref->hasAmbiguousRevisionRefs()) {
	- $status = pht('Ambiguous');
	- } else {
	- $revision_ref = $state_ref->getRevisionRef();
	- if (!$revision_ref) {
	- $status = tsprintf(
	- '<fg:blue>%s</fg>',
	- pht('No Revision'));
	- } else {
	- $status = $revision_ref->getStatusDisplayName();
	-
	- $ansi_color = $revision_ref->getStatusANSIColor();
	- if ($ansi_color) {
	- $status = tsprintf(
	- sprintf('<fg:%s>%%s</fg>', $ansi_color),
	- $status);
	- }
	+ $roots = array();
	+ foreach ($sets as $set) {
	+ if (!$set->getParentSets()) {
	+ $roots[] = $set;
	}
	}

	- if ($revision_ref) {
	- $description = $revision_ref->getFullName();
	- } else {
	- $description = $commit_ref->getSummary();
	- }
	+ // TODO: When no parent of a set is in the node list, we should render
	+ // a marker showing that the commit sequence is historic.

	- if ($marker_ref->getIsActive()) {
	- $active_mark = '*';
	- } else {
	- $active_mark = ' ';
	+ $row_lists = array();
	+ foreach ($roots as $set) {
	+ $view = id(new ArcanistCommitGraphSetTreeView())
	+ ->setRepositoryAPI($api)
	+ ->setRootSet($set)
	+ ->setMarkers($markers)
	+ ->setStateRefs($state_refs);
	+
	+ $row_lists[] = $view->draw();
	}
	- $is_active = tsprintf(' %s ', $active_mark);
	-
	- $rows[] = array(
	- 'active' => $is_active,
	- 'name' => $marker_name,
	- 'status' => $status,
	- 'description' => $description,
	- );
	+ $partition_lists[] = $row_lists;
	}

	- $table->drawRows($rows);
	+ $grid = id(new ArcanistGridView());
	+ $grid->newColumn('marker');
	+ $grid->newColumn('commits');
	+ $grid->newColumn('status');
	+ $grid->newColumn('revisions');
	+ $grid->newColumn('messages');
	+
	+ foreach ($partition_lists as $row_lists) {
	+ foreach ($row_lists as $row_list) {
	+ foreach ($row_list as $row) {
	+ $grid->newRow($row);
	+ }
	+ }
	+ }

	- return 0;
	+ echo tsprintf('%s', $grid->drawGrid());
	}

	final protected function hasMarkerTypeSupport($marker_type) {
	@@ -115,4 +173,144 @@
	return isset($types[$marker_type]);
	}

	+ private function getTailHashes() {
	+ $api = $this->getRepositoryAPI();
	+
	+ // TODO: This should be more sophisticated, and use all of the same rules
	+ // that "land" uses.
	+
	+ // TODO: We should examine the remote refs, not the local refs, so you can
	+ // (for example) develop on master.
	+
	+ $names = array('master', 'default');
	+
	+ $markers = $api->newMarkerRefQuery()
	+ ->withMarkerTypes(array(ArcanistMarkerRef::TYPE_BRANCH))
	+ ->withNames($names)
	+ ->execute();
	+
	+ return mpull($markers, 'getCommitHash');
	+ }
	+
	+ private function sortSets(
	+ ArcanistCommitGraph $graph,
	+ array $sets,
	+ array $markers) {
	+
	+ $marker_groups = mgroup($markers, 'getCommitHash');
	+ $sets = mpull($sets, null, 'getSetID');
	+
	+ $active_markers = array();
	+ foreach ($sets as $set_id => $set) {
	+ foreach ($set->getHashes() as $hash) {
	+ $markers = idx($marker_groups, $hash, array());
	+
	+ $has_active = false;
	+ foreach ($markers as $marker) {
	+ if ($marker->getIsActive()) {
	+ $has_active = true;
	+ break;
	+ }
	+ }
	+
	+ if ($has_active) {
	+ $active_markers[$set_id] = $set;
	+ break;
	+ }
	+ }
	+ }
	+
	+ $stack = array_select_keys($sets, array_keys($active_markers));
	+ while ($stack) {
	+ $cursor = array_pop($stack);
	+ foreach ($cursor->getParentSets() as $parent_id => $parent) {
	+ if (isset($active_markers[$parent_id])) {
	+ continue;
	+ }
	+ $active_markers[$parent_id] = $parent;
	+ $stack[] = $parent;
	+ }
	+ }
	+
	+ $partition_epoch = 0;
	+ $partition_names = array();
	+
	+ $vectors = array();
	+ foreach ($sets as $set_id => $set) {
	+ if (isset($active_markers[$set_id])) {
	+ $has_active = 1;
	+ } else {
	+ $has_active = 0;
	+ }
	+
	+ $max_epoch = 0;
	+ $marker_names = array();
	+ foreach ($set->getHashes() as $hash) {
	+ $node = $graph->getNode($hash);
	+ $max_epoch = max($max_epoch, $node->getCommitEpoch());
	+
	+ $markers = idx($marker_groups, $hash, array());
	+ foreach ($markers as $marker) {
	+ $marker_names[] = $marker->getName();
	+ }
	+ }
	+
	+ $partition_epoch = max($partition_epoch, $max_epoch);
	+
	+ if ($marker_names) {
	+ $has_markers = 1;
	+ natcasesort($marker_names);
	+ $max_name = last($marker_names);
	+
	+ $partition_names[] = $max_name;
	+ } else {
	+ $has_markers = 0;
	+ $max_name = '';
	+ }
	+
	+
	+ $vector = id(new PhutilSortVector())
	+ ->addInt($has_active)
	+ ->addInt($max_epoch)
	+ ->addInt($has_markers)
	+ ->addString($max_name);
	+
	+ $vectors[$set_id] = $vector;
	+ }
	+
	+ $vectors = msortv_natural($vectors, 'getSelf');
	+ $vector_keys = array_keys($vectors);
	+
	+ foreach ($sets as $set_id => $set) {
	+ $child_sets = $set->getDisplayChildSets();
	+ $child_sets = array_select_keys($child_sets, $vector_keys);
	+ $set->setDisplayChildSets($child_sets);
	+ }
	+
	+ $sets = array_select_keys($sets, $vector_keys);
	+
	+ if ($active_markers) {
	+ $any_active = true;
	+ } else {
	+ $any_active = false;
	+ }
	+
	+ if ($partition_names) {
	+ $has_markers = 1;
	+ natcasesort($partition_names);
	+ $partition_name = last($partition_names);
	+ } else {
	+ $has_markers = 0;
	+ $partition_name = '';
	+ }
	+
	+ $partition_vector = id(new PhutilSortVector())
	+ ->addInt($any_active)
	+ ->addInt($partition_epoch)
	+ ->addInt($has_markers)
	+ ->addString($partition_name);
	+
	+ return array($sets, $partition_vector);
	+ }
	+
	}

File Metadata

Mime Type: text/plain
Expires: Sat, Mar 15, 1:50 PM (2 w, 5 d ago)
Storage Engine: amazon-s3
Storage Format: Encrypted (AES-256-CBC)
Storage Handle: phabricator/secure/k3/nv/5uybw53nkkdqfsqf
Default Alt Text: D21363.id50851.diff (64 KB)

D21363.id50851.diffNo OneTemporaryActions

D21363.id50851.diffView Options

File Metadata

Event Timeline

D21363.id50851.diff
No OneTemporary
Actions

D21363.id50851.diff
View Options