reach.php
ActivePublic
Actions

Authored by epriestley on Jun 15 2020, 3:15 PM.

Tags

None

Referenced Files

	F7590594: reach.php
	Jun 17 2020, 2:50 PM

	F7583159: reach.php
	Jun 15 2020, 3:15 PM

Subscribers

None

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

Event Timeline

epriestley created this paste.Jun 15 2020, 3:15 PM

epriestley mentioned this in T9898: `git branch --contains X` has cost in the realm of O(commits * branches).

epriestley edited the content of this paste. (Show Details)Jun 17 2020, 2:50 PM

reach.phpActivePublicActions

Event Timeline

reach.php
ActivePublic
Actions