Viewing File: /home/ubuntu/code_review/arcanist/src/repository/graph/ArcanistCommitGraphSetQuery.php

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


}