Tool for visualizing type inference graph.

pkg/compiler/lib/src/inferrer/type_graph_dump.dart

Index: pkg/compiler/lib/src/inferrer/type_graph_dump.dart
diff --git a/pkg/compiler/lib/src/inferrer/type_graph_dump.dart b/pkg/compiler/lib/src/inferrer/type_graph_dump.dart
new file mode 100644
index 0000000000000000000000000000000000000000..a3520a0f983855542b7f4b651d0e033f83617a9e
--- /dev/null
+++ b/pkg/compiler/lib/src/inferrer/type_graph_dump.dart
@@ -0,0 +1,445 @@
+// Copyright (c) 2016, the Dart project authors.  Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+library dart2js.inferrer.type_graph_dump;
+
+import 'dart:async';
+import 'type_graph_nodes.dart';
+import 'type_graph_inferrer.dart';
+import '../elements/elements.dart';
+import '../types/types.dart';
+
+/// Dumps the type inference graph in Graphviz Dot format into the `typegraph`
+/// subfolder of the current working directory. Each function body is dumped in
+/// a separate file.
+///
+/// The resulting .dot files must be processed using the Graphviz `dot` command,
+/// which can be obtained from `http://www.graphviz.org`, or installed using
+/// most package managers (search for `graphviz` or `dot`).
+///
+/// Example commands:
+///
+///     dot -Tpng -O typegraph/main.dot
+///     open typegraph/main.dot.png
+///
+///     dot -Tpng -O typegraph/dart._internal.Sort._dualPivotQuicksort.dot
+///     open typegraph/dart._internal.Sort._dualPivotQuicksort.dot.png
+///
+class TypeGraphDump {
+  static const String outputDir = 'typegraph';
+
+  final TypeGraphInferrerEngine inferrer;
+  final Map<TypeInformation, Set<TypeInformation>> assignmentsBeforeAnalysis
+      = <TypeInformation, Set<TypeInformation>>{};
+  final Map<TypeInformation, Set<TypeInformation>> assignmentsBeforeTracing
+      = <TypeInformation, Set<TypeInformation>>{};
+  final Set<String> usedFilenames = new Set<String>();
+
+  TypeGraphDump(this.inferrer);
+
+  /// Take a copy of the assignment set for each node, since that may change
+  /// during the analysis.
+  void beforeAnalysis() {
+    for (TypeInformation node in inferrer.types.allTypes) {
+      Set<TypeInformation> copy = node.assignments.toSet();
+      if (!copy.isEmpty) {
+        assignmentsBeforeAnalysis[node] = copy;
+      }
+    }
+  }
+
+  /// Like [beforeAnalysis], takes a copy of the assignment sets.
+  void beforeTracing() {
+    for (TypeInformation node in inferrer.types.allTypes) {
+      Set<TypeInformation> copy = node.assignments.toSet();
+      if (!copy.isEmpty) {
+        assignmentsBeforeTracing[node] = copy;
+      }
+    }
+  }
+
+  /// Dumps the entire graph.
+  void afterAnalysis() {
+    // Group all the type nodes by their context member.
+    Map<Element, List<TypeInformation>> nodes =
+        <Element, List<TypeInformation>>{};
+    for (TypeInformation node in inferrer.types.allTypes) {
+      if (node.contextMember != null) {
+        nodes.putIfAbsent(node.contextMember, () => <TypeInformation>[])
+             .add(node);
+      }
+    }
+    // Print every group separately.
+    for (Element element in nodes.keys) {
+      EventSink<String> output;
+      try {
+        String name = filenameFromElement(element);
+        output = inferrer.compiler.outputProvider('$outputDir/$name', 'dot');
+        _GraphGenerator visitor = new _GraphGenerator(this, element, output);
+        for (TypeInformation node in nodes[element]) {
+          node.accept(visitor);
+        }
+        visitor.addMissingNodes();
+        visitor.finish();
+      } finally {
+        if (output != null) {
+          output.close();
+        }
+      }
+    }
+  }
+
+  /// Returns the filename (without extension) in which to dump the type
+  /// graph for [element].
+  ///
+  /// Will never return the a given filename more than once, even if called with
+  /// the same element.
+  String filenameFromElement(Element element) {
+    // The toString method of elements include characters that are unsuitable
+    // for URIs and file systems.
+    List<String> parts = <String>[];
+    parts.add(element.library?.libraryName);
+    parts.add(element.enclosingClass?.name);
+    Element namedElement = element is LocalElement
+        ? element.executableContext
+        : element;
+    if (namedElement.isGetter) {
+      parts.add('get-${namedElement.name}');
+    } else if (namedElement.isSetter) {
+      parts.add('set-${namedElement.name}');
+    } else if (namedElement.isConstructor) {
+      if (namedElement.name.isEmpty) {
+        parts.add('-constructor');
+      } else {
+        parts.add(namedElement.name);
+      }
+    } else if (namedElement.isOperator) {
+      parts.add(Elements.operatorNameToIdentifier(namedElement.name)
+          .replaceAll(r'$', '-'));
+    } else {
+      parts.add(namedElement.name);
+    }
+    if (namedElement != element) {
+      if (element.name.isEmpty) {
+        parts.add('anon${element.sourcePosition.begin}');
+      } else {
+        parts.add(element.name);
+      }
+    }
+    String filename = parts.where((x) => x != null && x != '').join('.');
+    if (usedFilenames.add(filename)) return filename;
+    // The filename has already been used by another method. Append a serial
+    // number to ensure we don't overwrite it.
+    int serialNumber = 2;
+    while (!usedFilenames.add('$filename-$serialNumber')) {
+      ++serialNumber;
+    }
+    return '$filename-$serialNumber';
+  }
+}
+
+/// Builds the Graphviz Dot file for one function body.
+class _GraphGenerator extends TypeInformationVisitor {
+  final TypeGraphDump global;
+  final Set<TypeInformation> seen = new Set<TypeInformation>();
+  final List<TypeInformation> worklist = new List<TypeInformation>();
+  final Map<TypeInformation, int> nodeId = <TypeInformation, int>{};
+  int usedIds = 0;
+  final EventSink<String> output;
+  final Element element;
+  TypeInformation returnValue;
+
+  _GraphGenerator(this.global, this.element, this.output) {
+    returnValue = global.inferrer.types.getInferredTypeOf(element);
+    getNode(returnValue); // Ensure return value is part of graph.
+    append('digraph {');
+  }
+
+  void finish() {
+    append('}');
+  }
+
+  /// Ensures that all nodes which have been referenced are generated.
+  ///
+  /// Sometimes an input to a TypeInformation node does not belong to the same
+  /// function body, and the graph looks confusing if they are missing.
+  void addMissingNodes() {
+    while (worklist.isNotEmpty) {
+      TypeInformation node = worklist.removeLast();
+      assert(nodeId.containsKey(node));
+      if (seen.contains(node)) continue;
+      node.accept(this);
+    }
+  }
+
+  void append(String string) {
+    output..add(string)..add('\n');
+  }
+
+  String shorten(String text) {
+    if (text.length > 40) {
+      return text.substring(0, 19) + '...' + text.substring(text.length - 18);
+    }
+    return text;
+  }
+
+  int getFreshId() => ++usedIds;
+
+  /// Obtains a unique ID for the node representing [info].
+  String getNode(TypeInformation info) {
+    int id = nodeId.putIfAbsent(info, () {
+      worklist.add(info); // Ensure that the referenced node is generated.
+      return getFreshId();
+    });
+    return '$id';
+  }
+
+  final RegExp escapeRegexp = new RegExp('["{}<>|]');
+
+  /// Escapes characters in [text] so it can be used as part of a label.
+  String escapeLabel(String text) {
+    return text.replaceAllMapped(escapeRegexp, (m) => '\\${m.group(0)}');
+  }
+
+  /// Creates an edge from [src] to [dst].
+  ///
+  /// If [dst] is a record type node, [port] may refer to one of the fields
+  /// defined in that record (e.g. `obj`, `arg0`, `arg1`, etc)
+  void addEdge(TypeInformation src,
+               TypeInformation dst,
+               {String port,
+                String color: 'black'}) {
+    if (isExternal(src) && isExternal(dst)) {
+      return; // Do not add edges between external nodes.
+    }
+    String dstText = getNode(dst);
+    if (port != null) {
+      dstText += ':$port';
+    }
+    if (src is ConcreteTypeInformation) {
+      // Concrete types can have a huge number of uses which will flood the
+      // graph with very long hard-to-follow edges. Copy the concrete nodes
+      // for every use to enhance readability.
+      int id = getFreshId();
+      String type = escapeLabel('${formatType(src.type)}');
+      String text = 'Concrete';
+      String label = '{$text|<returnType> $type}';
+      append('$id [shape=record,style=dotted,label="$label"]');
+      append('$id -> $dstText [color="$color"]');
+    } else {
+      append('${getNode(src)}:returnType -> $dstText [color="$color"]');
+    }
+  }
+
+  // Some graphs are flooded by a huge number of phi and narrow nodes.
+  // We color the nodes so the "interesting" nodes stand out more.
+  static const String defaultNodeColor = '#eeffee';
+  static const String phiColor = '#eeffff';
+  static const String narrowColor = phiColor;
+  static const String callColor = '#ffffee';
+
+  // Colors for edges based on whether they were added or removed during the
+  // analysis.
+  static const String unchangedEdge = 'black';
+  static const String addedEdge = 'green4';
+  static const String removedEdge = 'red3';
+  static const String temporaryEdge = 'orange'; // Added and then removed again.
+
+  bool isExternal(TypeInformation node) {
+    return node != returnValue && node.contextMember != element;
+  }
+
+  String getStyleForNode(TypeInformation node, String color) {
+    return isExternal(node)
+        ? 'style=dotted'
+        : 'style=filled,fillcolor="$color"';
+  }
+
+  /// Adds details that are not specific to a subclass of [TypeInformation].
+  String appendDetails(TypeInformation node, String text) {
+    if (node == returnValue) {
+      return '$text\n(return value)';
+    }
+    if (node.contextMember != null && node.contextMember != element) {
+      return '$text\n(from ${node.contextMember})';
+    }
+    return text;
+  }
+
+  /// Creates a node for [node] displaying the given [text] in its box.
+  ///
+  /// [inputs] specify named inputs to the node. If omitted, edges will be
+  /// based on [node.assignments].
+  void addNode(TypeInformation node,
+               String text,
+               {String color: defaultNodeColor,
+                Map<String, TypeInformation> inputs}) {
+    seen.add(node);
+    String style = getStyleForNode(node, color);
+    text = appendDetails(node, text);
+    text = escapeLabel(text);
+    String id = getNode(node);
+    String returnType = escapeLabel(formatType(node.type));
+    if (inputs != null) {
+      Iterable<String> keys = inputs.keys.where((key) => inputs[key] != null);
+      String header = keys.map((key) => '<a$key> $key').join('|');
+      String label = '{{$header}|$text|<returnType> $returnType}';
+      append('$id [shape=record,label="$label",$style]');
+      for (String key in keys) {
+        addEdge(inputs[key], node, port: 'a$key');
+      }
+    } else {
+      String label = '{$text|<returnType> $returnType}';
+      append('$id [shape=record,label="$label",$style]');
+      // Add assignment edges. Color the edges based on whether they were
+      // added, removed, temporary, or unchanged.
+      var originalSet = global.assignmentsBeforeAnalysis[node] ?? const [];
+      var tracerSet = global.assignmentsBeforeTracing[node] ?? const [];
+      var currentSet = node.assignments.toSet();
+      for (TypeInformation assignment in currentSet) {
+        String color = originalSet.contains(assignment)
+            ? unchangedEdge
+            : addedEdge;
+        addEdge(assignment, node, color: color);
+      }
+      for (TypeInformation assignment in originalSet) {
+        if (!currentSet.contains(assignment)) {
+          addEdge(assignment, node, color: removedEdge);
+        }
+      }
+      for (TypeInformation assignment in tracerSet) {
+        if (!currentSet.contains(assignment) &&
+            !originalSet.contains(assignment)) {
+          addEdge(assignment, node, color: temporaryEdge);
+        }
+      }
+    }
+  }
+
+  void visitNarrowTypeInformation(NarrowTypeInformation info) {
+    addNode(info, 'Narrow\n${formatType(info.typeAnnotation)}',
+        color: narrowColor);
+  }
+
+  void visitPhiElementTypeInformation(PhiElementTypeInformation info) {
+    addNode(info, 'Phi ${info.variable?.name ?? ''}', color: phiColor);
+  }
+
+  void visitElementInContainerTypeInformation(
+      ElementInContainerTypeInformation info) {
+    addNode(info, 'ElementInContainer');
+  }
+
+  void visitKeyInMapTypeInformation(KeyInMapTypeInformation info) {
+    addNode(info, 'KeyInMap');
+  }
+
+  void visitValueInMapTypeInformation(ValueInMapTypeInformation info) {
+    addNode(info, 'ValueInMap');
+  }
+
+  void visitListTypeInformation(ListTypeInformation info) {
+    addNode(info, 'List');
+  }
+
+  void visitMapTypeInformation(MapTypeInformation info) {
+    addNode(info, 'Map');
+  }
+
+  void visitConcreteTypeInformation(ConcreteTypeInformation info) {
+    addNode(info, 'Concrete');
+  }
+
+  void visitStringLiteralTypeInformation(StringLiteralTypeInformation info) {
+    String text = shorten(info.value.slowToString()).replaceAll('\n','\\n');
+    addNode(info, 'StringLiteral\n"$text"');
+  }
+
+  void visitBoolLiteralTypeInformation(BoolLiteralTypeInformation info) {
+    addNode(info, 'BoolLiteral\n${info.value}');
+  }
+
+  void handleCall(CallSiteTypeInformation info, String text, Map inputs) {
+    String sourceCode = shorten('${info.call}');
+    text = '$text\n$sourceCode';
+    if (info.arguments != null) {
+      for (int i = 0; i < info.arguments.positional.length; ++i) {
+        inputs['arg$i'] = info.arguments.positional[i];
+      }
+      for (String argName in info.arguments.named.keys) {
+        inputs[argName] = info.arguments.named[argName];
+      }
+    }
+    addNode(info, text, color: callColor, inputs: inputs);
+  }
+
+  void visitClosureCallSiteTypeInformation(ClosureCallSiteTypeInformation info) {
+    handleCall(info, 'ClosureCallSite', {});
+  }
+
+  void visitStaticCallSiteTypeInformation(StaticCallSiteTypeInformation info) {
+    handleCall(info, 'StaticCallSite', {});
+  }
+
+  void visitDynamicCallSiteTypeInformation(DynamicCallSiteTypeInformation info) {
+    handleCall(info, 'DynamicCallSite', {
+      'obj': info.receiver
+    });
+  }
+
+  void visitMemberTypeInformation(MemberTypeInformation info) {
+    addNode(info, 'Member\n${info.element}');
+  }
+
+  void visitParameterTypeInformation(ParameterTypeInformation info) {
+    addNode(info, 'Parameter ${info.element?.name ?? ''}');
+  }
+
+  void visitClosureTypeInformation(ClosureTypeInformation info) {
+    String text = shorten('${info.node}');
+    addNode(info, 'Closure\n$text');
+  }
+
+  void visitAwaitTypeInformation(AwaitTypeInformation info) {
+    String text = shorten('${info.node}');
+    addNode(info, 'Await\n$text');
+  }
+}
+
+/// Convert the given TypeMask to a compact string format.
+///
+/// The default format is too verbose for the graph format since long strings
+/// create oblong nodes that obstruct the graph layout.
+String formatType(TypeMask type) {
+  if (type is FlatTypeMask) {
+    // TODO(asgerf): Disambiguate classes whose name is not unique. Using the
+    //     library name for all classes is not a good idea, since library names
+    //     can be really long and mess up the layout.
+    // Capitalize Null to emphasize that it's the null type mask and not
+    // a null value we accidentally printed out.
+    if (type.isEmptyOrNull) return type.isNullable ? 'Null' : 'Empty';
+    String nullFlag = type.isNullable ? '?' : '';
+    String subFlag = type.isExact ? '' : type.isSubclass ? '+' : '*';
+    return '${type.base.name}$nullFlag$subFlag';
+  }
+  if (type is UnionTypeMask) {
+    return type.disjointMasks.map(formatType).join(' | ');
+  }
+  if (type is ContainerTypeMask) {
+    String container = formatType(type.forwardTo);
+    String member = formatType(type.elementType);
+    return '$container<$member>';
+  }
+  if (type is MapTypeMask) {
+    String container = formatType(type.forwardTo);
+    String key = formatType(type.keyType);
+    String value = formatType(type.valueType);
+    return '$container<$key,$value>';
+  }
+  if (type is ValueTypeMask) {
+    String baseType = formatType(type.forwardTo);
+    String value = type.value.toStructuredString();
+    return '$baseType=$value';
+  }
+  return '$type'; // Fall back on toString if not supported here.
+}