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 @@ +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 @@ +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 @@ +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 @@ +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 @@ +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 @@ +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 @@ +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 @@ +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 @@ +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 @@ +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 @@ +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\S+)>(?P\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 @@ +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 @@ +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( + '**%s**', + $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('%%s', $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( - '%s', - pht('No Revision')); - } else { - $status = $revision_ref->getStatusDisplayName(); - - $ansi_color = $revision_ref->getStatusANSIColor(); - if ($ansi_color) { - $status = tsprintf( - sprintf('%%s', $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); + } + }