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',
@@ -331,6 +342,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',
@@ -465,6 +477,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',
@@ -1137,6 +1150,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',
@@ -1242,6 +1265,7 @@
'ArcanistGeneratedLinterTestCase' => 'ArcanistLinterTestCase',
'ArcanistGetConfigWorkflow' => 'ArcanistWorkflow',
'ArcanistGitAPI' => 'ArcanistRepositoryAPI',
+ 'ArcanistGitCommitGraphQuery' => 'ArcanistCommitGraphQuery',
'ArcanistGitCommitMessageHardpointQuery' => 'ArcanistWorkflowGitHardpointQuery',
'ArcanistGitCommitSymbolCommitHardpointQuery' => 'ArcanistWorkflowGitHardpointQuery',
'ArcanistGitLandEngine' => 'ArcanistLandEngine',
@@ -1362,6 +1386,7 @@
'ArcanistMarkerRef' => 'ArcanistRef',
'ArcanistMarkersWorkflow' => 'ArcanistArcWorkflow',
'ArcanistMercurialAPI' => 'ArcanistRepositoryAPI',
+ 'ArcanistMercurialCommitGraphQuery' => 'ArcanistCommitGraphQuery',
'ArcanistMercurialCommitMessageHardpointQuery' => 'ArcanistWorkflowMercurialHardpointQuery',
'ArcanistMercurialLandEngine' => 'ArcanistLandEngine',
'ArcanistMercurialLocalState' => 'ArcanistRepositoryLocalState',
@@ -1498,6 +1523,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
@@ -1816,4 +1816,8 @@
return $hashes;
}
+ 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
@@ -1031,4 +1031,8 @@
$uri);
}
+ 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,10 +795,19 @@
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 getNormalizedURI($uri) {
$normalized_uri = $this->newNormalizedURI($uri);
return $normalized_uri->getNormalizedURI();
@@ -815,4 +825,13 @@
return array();
}
+ 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/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();
- $table = id(new PhutilConsoleTable())
- ->setShowHeader(false)
- ->addColumn('active')
- ->addColumn('name')
- ->addColumn('status')
- ->addColumn('description');
+ list($sets, $partition_vector) = $this->sortSets(
+ $graph,
+ $sets,
+ $markers);
- $rows = array();
- foreach ($states as $state) {
- $marker_ref = $state['marker'];
- $state_ref = $state['state'];
- $revision_ref = null;
- $commit_ref = $marker_ref->getCommitRef();
+ $partition_sets[$partition_key] = $sets;
+ $partition_vectors[$partition_key] = $partition_vector;
+ }
- $marker_name = tsprintf('**%s**', $marker_ref->getName());
+ $partition_vectors = msortv($partition_vectors, 'getSelf');
+ $partitions = array_select_keys(
+ $partitions,
+ array_keys($partition_vectors));
- 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);
- }
+ $partition_lists = array();
+ foreach ($partitions as $partition_key => $partition) {
+ $sets = $partition_sets[$partition_key];
+
+ $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');
- return 0;
+ foreach ($partition_lists as $row_lists) {
+ foreach ($row_lists as $row_list) {
+ foreach ($row_list as $row) {
+ $grid->newRow($row);
+ }
+ }
+ }
+
+ echo tsprintf('%s', $grid->drawGrid());
}
final protected function hasMarkerTypeSupport($marker_type) {
@@ -115,4 +173,130 @@
return isset($types[$marker_type]);
}
+ private function getTailHashes() {
+ $api = $this->getRepositoryAPI();
+ return $api->getPublishedCommitHashes();
+ }
+
+ 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);
+ }
+
}