public function newReachForWaypoints(array $waypoints) {
$graph = $this->getGraph();
$partition = array_fuse($this->hashes);
foreach ($waypoints as $hash) {
$waypoint_reach[$hash] = $this->newReachFromHash($hash);
}
$stack = array();
foreach ($this->getHeads() as $hash) {
$stack[] = $graph->getNode($hash);
$reach[$hash] = $this->newReachFromHash($hash);
}
// Find nodes with multiple children which need to wait until all of their
// children have been reached before they can be painted.
$wait = array();
foreach ($partition as $hash) {
$node = $graph->getNode($hash);
$children = $node->getChildNodes();
if (count($children) < 2) {
// If the node has one or fewer children, we can paint it as soon
// as we reach it.
continue;
}
// Discard children which aren't in the partition.
$need = array();
foreach ($children as $child_node) {
$child_hash = $child_node->getCommitHash();
if (!isset($partition[$child_hash])) {
continue;
}
$need[] = $child_hash;
}
$need_count = count($need);
if ($need_count < 2) {
// If we have one or fewer children in the partition, we can paint
// as soon as we reach the node.
continue;
}
$wait[$node->getCommitHash()] = $need_count;
}
while ($stack) {
$node = array_pop($stack);
$node_hash = $node->getCommitHash();
if (isset($waypoint_reach[$node_hash])) {
$node_reach = $waypoint_reach[$node_hash];
} else {
$node_reach = $reach[$node_hash];
}
foreach ($node->getParentNodes() as $parent_node) {
$parent_hash = $parent_node->getCommitHash();
if (isset($reach[$parent_hash])) {
$reach[$parent_hash] = $this->newReach(
$reach[$parent_hash],
$node_reach);
continue;
}
$reach[$parent_hash] = $node_reach;
if (isset($wait[$parent_hash])) {
$wait[$parent_hash]--;
if ($wait[$parent_hash]) {
continue;
}
}
$stack[] = $parent_node;
}
}
return id(new ArcanistCommitGraphReach())
->setPartition($this)
->setReach($reach);
}
private function newReachFromHash($hash) {
return array($hash => $hash);
}
private function newReach($u, $v) {
return $u + $v;
}
public function testGraphReach() {
$this->assertGraphReach(
array('E'),
pht('Simple Graph'),
array('E'),
array('E'),
'A',
'A>B B>C C>D D>E');
}
private function assertGraphReach(
$expect, $name, $heads, $waypoints, $src, $corpus) {
$graph = new ArcanistCommitGraph();
$query = id(new ArcanistSimpleCommitGraphQuery())
->setGraph($graph);
$query->setCorpus($corpus)->execute();
$partitions = $graph->newPartitionQuery()
->withHeads($heads)
->execute();
$this->assertEqual(
1,
count($partitions),
pht('Expected one partition for reach test "%s".', $name));
$partition = head($partitions);
$reach = $partition->newReachForWaypoints($waypoints);
$this->assertEqual(
$expect,
$reach->getReachForHash($src),
pht('Reachability of "%s"', $name));
}