src/main/java/com/google/devtools/build/lib/query2/query/output/GraphOutputWriter.java

// Copyright 2020 The Bazel Authors. All rights reserved.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//    http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
package com.google.devtools.build.lib.query2.query.output;

import static com.google.common.collect.ImmutableList.toImmutableList;
import static java.nio.charset.StandardCharsets.UTF_8;

import com.google.common.collect.ImmutableList;
import com.google.common.collect.ImmutableSet;
import com.google.common.collect.Iterables;
import com.google.common.collect.Ordering;
import com.google.devtools.build.lib.cmdline.Label;
import com.google.devtools.build.lib.collect.EquivalenceRelation;
import com.google.devtools.build.lib.graph.Digraph;
import com.google.devtools.build.lib.graph.DotOutputVisitor;
import com.google.devtools.build.lib.graph.LabelSerializer;
import com.google.devtools.build.lib.graph.Node;
import com.google.devtools.build.lib.packages.LabelPrinter;
import com.google.devtools.build.lib.packages.Target;
import java.io.OutputStream;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.Optional;
import java.util.Set;
import javax.annotation.Nullable;

/**
 * Generic logic for writing query expression results to <a
 * href="http://graphviz.org/doc/info/lang.html">GraphViz</a> format.
 *
 * <p>This can be used by any query implementation that can provide results as a {@link Digraph}.
 */
public final class GraphOutputWriter<T> {
  /** Interface for reading the contents of a {@link Digraph} {@link Node}. */
  public interface NodeReader<T> {
    /**
     * Returns the label to associate with a GraphViz node.
     *
     * <p>This is not the same as a build {@link Label}. This is just the text associated with a
     * node in a GraphViz graph.
     */
    String getLabel(Node<T> node, LabelPrinter labelPrinter);

    /** Returns a comparator for the build graph nodes that form the payloads of GraphViz nodes. */
    Comparator<T> comparator();
  }

  private final NodeReader<T> nodeReader;
  private final String lineTerminator;
  private final boolean sortLabels;
  private final int maxLabelSize;
  private final int maxConditionalEdges;
  private final boolean mergeEquivalentNodes;
  private final Ordering<Node<T>> nodeComparator;
  private final LabelPrinter labelPrinter;

  private static final int RESERVED_LABEL_CHARS = "\\n...and 9999999 more items".length();

  /**
   * Constructors a new writer.
   *
   * @param nodeReader {@link NodeReader} for reading node content
   * @param lineTerminator line string terminator
   * @param sortLabels if true, output nodes in sorted order with {@link NodeReader#comparator})
   * @param maxLabelSize maximum characters in label output. Longer labels are truncated. -1 means
   *     no limit.
   * @param maxConditionalEdges maximum number of {@code select() conditional labels} to show on
   *     each edge. -1 means no limit. 0 means no labels.
   * @param mergeEquivalentNodes if true, topologically equivalent nodes are merged together as
   *     multiple labels in the same node. This condenses the graph. For example, given graph {@code
   *     (nodes=[A, B, C], edges=[A->B, A->C]) }, the output has two nodes: "A" and "B,C".
   */
  public GraphOutputWriter(
      NodeReader<T> nodeReader,
      String lineTerminator,
      boolean sortLabels,
      int maxLabelSize,
      int maxConditionalEdges,
      boolean mergeEquivalentNodes,
      LabelPrinter labelPrinter) {
    this.nodeReader = nodeReader;
    this.lineTerminator = lineTerminator;
    this.sortLabels = sortLabels;
    this.maxLabelSize = maxLabelSize;
    this.maxConditionalEdges = maxConditionalEdges;
    this.mergeEquivalentNodes = mergeEquivalentNodes;
    this.labelPrinter = labelPrinter;
    nodeComparator = Ordering.from(nodeReader.comparator()).onResultOf(Node::getLabel);
  }

  /**
   * Writes the given graph.
   *
   * @param graph build graph to write
   * @param conditionalEdges edges corresponding to select()s (see {@link ConditionalEdges})
   * @param out output stream to write to
   */
  public void write(
      Digraph<T> graph, @Nullable ConditionalEdges conditionalEdges, OutputStream out) {
    PrintWriter printWriter = new PrintWriter(new OutputStreamWriter(out, UTF_8));
    if (mergeEquivalentNodes) {
      outputFactored(graph, conditionalEdges, printWriter);
    } else {
      outputUnfactored(graph, conditionalEdges, printWriter);
    }
  }

  private void outputUnfactored(
      Digraph<T> graph, @Nullable ConditionalEdges conditionalEdges, PrintWriter out) {
    graph.visitNodesBeforeEdges(
        new DotOutputVisitor<T>(out, node -> nodeReader.getLabel(node, labelPrinter)) {
          @Override
          public void beginVisit() {
            super.beginVisit();
            // TODO(bazel-team): (2009) make this the default in Digraph.
            out.printf("  node [shape=box];%s", lineTerminator);
          }

          @Override
          public void visitEdge(Node<T> lhs, Node<T> rhs) {
            super.visitEdge(lhs, rhs);
            String outputLabel =
                getConditionsGraphLabel(
                    ImmutableSet.of(lhs), ImmutableSet.of(rhs), conditionalEdges);
            if (!outputLabel.isEmpty()) {
              out.printf("  [label=\"%s\"];\n", outputLabel);
            }
          }
        },
        sortLabels ? nodeReader.comparator() : null);
  }

  /**
   * Given {@code collectionOfUnorderedSets}, a collection of sets of nodes, returns a collection of
   * sets with the same elements as {@code collectionOfUnorderedSets} but with a stable iteration
   * order within each set given by the target ordering, and the collection ordered by the same
   * induced order.
   */
  private Collection<Set<Node<T>>> orderPartition(
      Collection<Set<Node<T>>> collectionOfUnorderedSets) {
    List<Set<Node<T>>> result = new ArrayList<>();
    for (Set<Node<T>> part : collectionOfUnorderedSets) {
      List<Node<T>> toSort = new ArrayList<>(part);
      Collections.sort(toSort, nodeComparator);
      result.add(ImmutableSet.copyOf(toSort));
    }
    Collections.sort(result, nodeComparator.lexicographical());
    return result;
  }

  private void outputFactored(
      Digraph<T> graph, ConditionalEdges conditionalEdges, PrintWriter out) {

    Collection<Set<Node<T>>> partition = partitionFactored(graph);
    if (sortLabels) {
      partition = orderPartition(partition);
    }

    Digraph<Set<Node<T>>> factoredGraph = graph.createImageUnderPartition(partition);

    // Concatenate the labels of all topologically-equivalent nodes.
    LabelSerializer<Set<Node<T>>> labelSerializer =
        node -> {
          int actualLimit = maxLabelSize - RESERVED_LABEL_CHARS;
          boolean firstItem = true;
          StringBuilder buf = new StringBuilder();
          int count = 0;
          for (Node<T> eqNode : node.getLabel()) {
            String labelString = nodeReader.getLabel(eqNode, labelPrinter);
            if (!firstItem) {
              buf.append("\\n");

              // Use -1 to denote no limit, as it is easier than trying to pass MAX_INT on the
              // cmdline
              if (maxLabelSize != -1 && (buf.length() + labelString.length() > actualLimit)) {
                buf.append("...and ");
                buf.append(node.getLabel().size() - count);
                buf.append(" more items");
                break;
              }
            }

            buf.append(labelString);
            count++;
            firstItem = false;
          }
          return buf.toString();
        };

    factoredGraph.visitNodesBeforeEdges(
        new DotOutputVisitor<Set<Node<T>>>(out, labelSerializer) {
          @Override
          public void beginVisit() {
            super.beginVisit();
            // TODO(bazel-team): (2009) make this the default in Digraph.
            out.println("  node [shape=box];");
          }

          @Override
          public void visitEdge(Node<Set<Node<T>>> lhs, Node<Set<Node<T>>> rhs) {
            super.visitEdge(lhs, rhs);

            String outputLabel =
                getConditionsGraphLabel(lhs.getLabel(), rhs.getLabel(), conditionalEdges);
            if (!outputLabel.isEmpty()) {
              out.printf("  [label=\"%s\"];\n", outputLabel);
            }
          }
        },
        sortLabels ? nodeComparator.lexicographical() : null);
  }

  /**
   * Partitions the graph into equivalence classes of topologically equivalent nodes.
   *
   * <p>Algorithm: Visit each node, comparing children with each other based on the eq relation to
   * put them into their eq classes. Compare top-level nodes as well as though they were children of
   * a fake root node.
   *
   * <p>Invariant: Two nodes are in the same equivalence class -> they have the same parents (and
   * children).
   *
   * <p>Contrapositive: If two nodes do not have the same parents (or children) -> they are not in
   * the same equivalence class.
   *
   * <p>Because of the contrapositive, we only need to compare children nodes of each parent node
   * (rather than each node with every other node). This allows us to significantly reduce the
   * number of comparisons between nodes.
   *
   * @param graph the graph to partition.
   * @return a collection of equivalence classes (sets of nodes).
   */
  private ImmutableList<Set<Node<T>>> partitionFactored(Digraph<T> graph) {
    // Two nodes are equivalent iff they have the same successors and predecessors.
    EquivalenceRelation<Node<T>> equivalenceRelation =
        (x, y) -> {
          if (Objects.equals(x, y)) {
            return 0;
          }

          if (x.numPredecessors() != y.numPredecessors()
              || x.numSuccessors() != y.numSuccessors()) {
            return -1;
          }

          Set<Node<T>> xpred = new HashSet<>(x.getPredecessors());
          Set<Node<T>> ypred = new HashSet<>(y.getPredecessors());
          if (!xpred.equals(ypred)) {
            return -1;
          }

          Set<Node<T>> xsucc = new HashSet<>(x.getSuccessors());
          Set<Node<T>> ysucc = new HashSet<>(y.getSuccessors());
          if (!xsucc.equals(ysucc)) {
            return -1;
          }

          return 0;
        };

    // Keep a map of equivalence classes that each node belongs to, so that we know whether a node
    // already belongs to one.
    HashMap<Node<T>, Set<Node<T>>> eqClasses = new HashMap<>();
    ArrayDeque<Node<T>> queue = new ArrayDeque<>(graph.getRoots());
    Set<Node<T>> enqueued = new HashSet<>(graph.getRoots());

    // Top-level nodes need to be compared amongst each other because they can form an equivalence
    // class amongst themselves too.
    processSuccessors(ImmutableList.copyOf(queue), eqClasses, equivalenceRelation);

    while (!queue.isEmpty()) {
      Node<T> node = queue.removeFirst();
      List<Node<T>> successors = new ArrayList<>(node.getSuccessors());
      processSuccessors(successors, eqClasses, equivalenceRelation);
      for (Node<T> child : node.getSuccessors()) {
        // We don't want the queue to grow to O(E); also, there is no need to visit children twice.
        if (!enqueued.contains(child)) {
          queue.add(child);
          enqueued.add(child);
        }
      }
    }

    return eqClasses.values().stream().distinct().collect(toImmutableList());
  }

  /**
   * Compares a list of successors of a parent node amongst each other and adds them to their
   * equivalence classes.
   *
   * @param successors list of successors to compare.
   * @param eqClasses map containing the equivalence class that a node belongs to.
   * @param equivalenceRelation the equivalence relation by which the equivalence classes are *
   *     defined.
   */
  private void processSuccessors(
      List<Node<T>> successors,
      Map<Node<T>, Set<Node<T>>> eqClasses,
      EquivalenceRelation<Node<T>> equivalenceRelation) {
    int numSuccessors = successors.size();

    for (int i = 0; i < numSuccessors; i++) {
      Node<T> child = successors.get(i);
      if (eqClasses.containsKey(child)) {
        // This child has already been added to an equivalence class, there is no need to compare
        // because all members in that equivalence class would have already been added.
        continue;
      }

      // Put the child in its own equivalence class and compare with its siblings.
      Set<Node<T>> eqClass = new HashSet<>();
      eqClass.add(child);
      eqClasses.put(child, eqClass);

      // Start at i+1, since j <= i has already been checked.
      for (int j = i + 1; j < numSuccessors; j++) {
        Node<T> sibling = successors.get(j);
        if (eqClasses.containsKey(sibling)) {
          // The sibling has already been added to another equivalence class, no need to compare.
          continue;
        }

        // This is expensive, so we want to minimize this as much as possible.
        if (equivalenceRelation.compare(child, sibling) == 0) {
          eqClass.add(sibling);
          eqClasses.put(sibling, eqClass);
        }
      }
    }
  }

  private String getConditionsGraphLabel(
      Iterable<Node<T>> lhs, Iterable<Node<T>> rhs, ConditionalEdges conditionalEdges) {
    StringBuilder buf = new StringBuilder();
    if (conditionalEdges == null || maxConditionalEdges == 0) {
      return buf.toString();
    }

    Set<Label> annotatedLabels = new HashSet<>();
    for (Node<T> src : lhs) {
      Label srcLabel = ((Target) src.getLabel()).getLabel();
      for (Node<T> dest : rhs) {
        Label destLabel = ((Target) dest.getLabel()).getLabel();
        Optional<Set<Label>> conditions = conditionalEdges.get(srcLabel, destLabel);
        if (conditions.isPresent()) {
          boolean firstItem = true;

          int limit =
              (maxConditionalEdges == -1) ? conditions.get().size() : (maxConditionalEdges - 1);

          for (Label conditionLabel : Iterables.limit(conditions.get(), limit)) {
            if (!annotatedLabels.add(conditionLabel)) {
              // duplicate label; skip.
              continue;
            }

            if (!firstItem) {
              buf.append("\\n");
            }

            buf.append(conditionLabel.getCanonicalForm());
            firstItem = false;
          }
          if (conditions.get().size() > limit) {
            buf.append("...");
          }
        }
      }
    }
    return buf.toString();
  }
}