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)); }