Integrity checker for CPS and Tree IR.

pkg/compiler/lib/src/cps_ir/cps_ir_integrity.dart

+library dart2js.cps_ir_integrity;
+
+import 'cps_ir_nodes.dart';
+import 'cps_ir_nodes_sexpr.dart';
+import '../tracer.dart' as tracer;
+
+/// Dump S-expressions on error if the tracer is enabled.
+///
+/// Technically this has nothing to do with the tracer, but if you want one
+/// enabled, you typically want the other as well, so we use the same flag.
+const bool ENABLE_DUMP = tracer.TRACE_FILTER_PATTERN != null;
+
+/// Performs integrity checks on the CPS IR.
+///
+/// To be run for debugging purposes, not for use in production.
+///
+/// The following integrity checks are performed:
+///
+/// - References are in scope of their definitions.
+/// - Recursive Continuations and InvokeContinuations are marked as recursive.
+/// - InvokeContinuations have the same arity as their target.
+/// - Reference chains are valid doubly-linked lists.
+/// - Reference chains contain exactly the references that are in the IR.
+/// - Each definition object occurs only once in the IR (no redeclaring).
+/// - Each reference object occurs only once in the IR (no sharing).
+///
+class CheckCpsIntegrity extends RecursiveVisitor {
+
+  ExecutableDefinition topLevelNode;
+
+  Set<Definition> seenDefinitions = new Set<Definition>();
+  Map<Definition, Set<Reference>> seenReferences =
+      <Definition, Set<Reference>>{};
+
+  Map<Definition, Node> bindings = <Definition, Node>{};
+  Set<Continuation> insideContinuations = new Set<Continuation>();
+
+  doInScope(Iterable<Definition> defs, Node binding, action()) {
+    for (Definition def in defs) {
+      bindings[def] = binding;
+    }
+    action();
+    for (Definition def in defs) {
+      bindings.remove(def);
+    }
+  }
+
+  void markAsSeen(Definition def) {
+    if (!seenDefinitions.add(def)) {
+      error('Redeclared $def', def);
+    }
+    seenReferences[def] = new Set<Reference>();
+  }
+
+  @override
+  visitLetCont(LetCont node) {
+    // Analyze each continuation separately without the others in scope.
+    for (Continuation continuation in node.continuations) {
+      // We always consider a continuation to be in scope of itself.
+      // The isRecursive flag is checked explicitly to give more useful
+      // error messages.
+      doInScope([continuation], node, () => visit(continuation));
+    }
+    // Analyze the body with all continuations in scope.
+    doInScope(node.continuations, node, () => visit(node.body));
+  }
+
+  @override
+  visitContinuation(Continuation node) {
+    markAsSeen(node);
+    if (node.isReturnContinuation) {
+      error('Non-return continuation missing body', node);
+    }
+    node.parameters.forEach(markAsSeen);
+    insideContinuations.add(node);
+    doInScope(node.parameters, node, () => visit(node.body));
+    insideContinuations.remove(node);
+  }
+
+  @override
+  visitRunnableBody(RunnableBody node) {
+    markAsSeen(node.returnContinuation);
+    if (!node.returnContinuation.isReturnContinuation) {
+      error('Return continuation with a body', node);
+    }
+    doInScope([node.returnContinuation], node, () => visit(node.body));
+  }
+
+  @override
+  visitLetPrim(LetPrim node) {
+    markAsSeen(node.primitive);
+    visit(node.primitive);
+    doInScope([node.primitive], node, () => visit(node.body));
+  }
+
+  @override
+  visitLetMutable(LetMutable node) {
+    markAsSeen(node.variable);
+    processReference(node.value);
+    doInScope([node.variable], node, () => visit(node.body));
+  }
+
+  @override
+  visitFunctionDefinition(FunctionDefinition node) {
+    node.parameters.forEach(markAsSeen);
+    if (node.body != null) {
+      doInScope(node.parameters, node, () => visit(node.body));
+    }
+  }
+
+  @override
+  visitConstructorDefinition(ConstructorDefinition node) {
+    node.parameters.forEach(markAsSeen);
+    doInScope(node.parameters, node, () {
+      if (node.initializers != null) node.initializers.forEach(visit);
+      if (node.body != null) visit(node.body);
+    });
+  }
+
+  @override
+  visitDeclareFunction(DeclareFunction node) {
+    markAsSeen(node.variable);
+    doInScope([node.variable], node, () {
+      visit(node.definition);
+      visit(node.body);
+    });
+  }
+
+  @override
+  processReference(Reference reference) {
+    if (!bindings.containsKey(reference.definition)) {
+      error('Referenced out of scope: ${reference.definition}', reference);
+    }
+    if (!seenReferences[reference.definition].add(reference)) {
+      error('Duplicate use of Reference to ${reference.definition}', reference);
+    }
+  }
+
+  @override
+  processInvokeContinuation(InvokeContinuation node) {
+    Continuation target = node.continuation.definition;
+    if (node.isRecursive && !insideContinuations.contains(target)) {
+      error('Non-recursive InvokeContinuation marked as recursive', node);
+    }
+    if (!node.isRecursive && insideContinuations.contains(target)) {
+      error('Recursive InvokeContinuation marked as non-recursive', node);
+    }
+    if (node.isRecursive && !target.isRecursive) {
+      error('Recursive Continuation was not marked as recursive', node);
+    }
+    if (node.arguments.length != target.parameters.length) {
+      error('Arity mismatch in InvokeContinuation', node);
+    }
+  }
+
+  void checkReferenceChain(Definition def) {
+    Set<Reference> chainedReferences = new Set<Reference>();
+    Reference prev = null;
+    for (Reference ref = def.firstRef; ref != null; ref = ref.next) {
+      if (ref.definition != def) {
+        error('Reference in chain for $def points to ${ref.definition}', def);
+      }
+      if (ref.previous != prev) {
+        error('Broken .previous link in reference to $def', def);
+      }
+      prev = ref;
+      if (!chainedReferences.add(ref)) {
+        error('Cyclic reference chain for $def', def);
+      }
+    }
+    if (!chainedReferences.containsAll(seenReferences[def])) {
+      error('Seen reference to $def not in reference chain', def);
+    }
+    if (!seenReferences[def].containsAll(chainedReferences)) {
+      error('Reference chain for $def contains orphaned references', def);
+    }
+  }
+
+  error(String message, node) {
+    String sexpr;
+    if (ENABLE_DUMP) {
+      try {
+        Decorator decorator = (n, String s) => n == node ? '**$s**' : s;
+        sexpr = new SExpressionStringifier(decorator).visit(topLevelNode);
+      } catch (e) {
+        sexpr = '(Exception thrown by SExpressionStringifier: $e)';
+      }
+    } else {
+      sexpr = '(Set DUMP_IR flag to enable)';
+    }
+    throw 'CPS integrity violation in ${topLevelNode.element}:\n'
+          '$message\n\n'
+          'SExpr dump (offending node marked with **):\n\n'
+          '$sexpr\n';
+  }
+
+  void check(ExecutableDefinition node) {
+    topLevelNode = node;
+    visit(node);
+
+    // Check this last, so out-of-scope references are not classified as
+    // a broken reference chain.
+    seenDefinitions.forEach(checkReferenceChain);
+  }
+
+}