Differential D21363 Diff 50889 src/repository/graph/ArcanistCommitGraphSetQuery.php

Changeset View

Standalone View

src/repository/graph/ArcanistCommitGraphSetQuery.php

This file was added.

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


				}