Integrity checker for CPS and Tree IR.

pkg/compiler/lib/src/tree_ir/tree_ir_integrity.dart

+library tree_ir.integrity;
+
+import 'tree_ir_nodes.dart';
+
+/// Performs integrity checks on the tree_ir.
+///
+/// Should only be run for debugging purposes, not in production.
+///
+/// - Reference counts on variables and labels must match be actual
+///   number of references.
+/// - Labels must be in scope when referenced.
+/// - Breaks must target a [LabeledStatement].
+/// - Continues must target a [Loop].
+///
+class CheckTreeIntegrity extends RecursiveVisitor {
+  ExecutableDefinition topLevelNode;
+
+  Map<Variable, int> varReads = <Variable, int>{};
+  Map<Variable, int> varWrites = <Variable, int>{};
+  Map<Label, int> labelUses = <Label, int>{};
+  Map<Label, JumpTarget> label2declaration = <Label, JumpTarget>{};
+
+  void write(Variable variable) {
+    varWrites.putIfAbsent(variable, () => 0);
+    varWrites[variable]++;
+  }
+
+  void read(Variable variable) {
+    varReads.putIfAbsent(variable, () => 0);
+    varReads[variable]++;
+  }
+
+  visitVariableUse(VariableUse node) {
+    read(node.variable);
+  }
+
+  visitAssign(Assign node) {
+    write(node.variable);
+    visitExpression(node.definition);
+    visitStatement(node.next);
+  }
+
+  visitTry(Try node) {
+    node.catchParameters.forEach(write);
+    visitStatement(node.tryBody);
+    visitStatement(node.catchBody);
+  }
+
+  visitFunctionDefinition(FunctionDefinition node) {
+    node.parameters.forEach(write);
+    if (node.body != null) visitStatement(node.body);
+  }
+
+  visitFunctionDeclaration(FunctionDeclaration node) {
+    write(node.variable);
+    visitFunctionDefinition(node.definition);
+    visitStatement(node.next);
+  }
+
+  visitJumpTargetBody(JumpTarget target) {
+    Label label = target.label;
+    if (label2declaration.containsKey(label)) {
+      error('Duplicate declaration of label $label');
+    }
+    label2declaration[label] = target;
+    labelUses[label] = 0;
+    visitStatement(target.body);
+    label2declaration.remove(target);
+
+    if (labelUses[label] != label.useCount) {
+      error('Label $label has ${labelUses[label]} uses '
+            'but its reference count is ${label.useCount}');
+    }
+  }
+
+  visitLabeledStatement(LabeledStatement node) {
+    visitJumpTargetBody(node);
+    visitStatement(node.next);
+  }
+
+  visitWhileTrue(WhileTrue node) {
+    visitJumpTargetBody(node);
+  }
+
+  visitWhileCondition(WhileCondition node) {
+    visitExpression(node.condition);
+    visitJumpTargetBody(node);
+    visitStatement(node.next);
+  }
+
+  visitBreak(Break node) {
+    if (!label2declaration.containsKey(node.target)) {
+      error('Break to label that is not in scope');
+    }
+    if (label2declaration[node.target] is! LabeledStatement) {
+      error('Break to non-labeled statement ${label2declaration[node.target]}');
+    }
+    labelUses[node.target]++;
+  }
+
+  visitContinue(Continue node) {
+    if (!label2declaration.containsKey(node.target)) {
+      error('Continue to label that is not in scope');
+    }
+    if (label2declaration[node.target] is! Loop) {
+      error('Continue to non-loop statement ${label2declaration[node.target]}');
+    }
+    labelUses[node.target]++;
+  }
+
+  dynamic error(String message) {
+    throw 'Tree IR integrity violation in ${topLevelNode.element}:\n$message';
+  }
+
+  void check(ExecutableDefinition node) {
+    topLevelNode = node;
+    visitExecutableDefinition(node);
+
+    // Verify reference counters for all variables.
+    List<Variable> seenVariables = new List<Variable>();
+    seenVariables.addAll(varReads.keys);
+    seenVariables.addAll(varWrites.keys);
+    for (Variable variable in seenVariables) {
+      int reads = varReads.putIfAbsent(variable, () => 0);
+      int writes = varWrites.putIfAbsent(variable, () => 0);
+      if (reads != variable.readCount || writes != variable.writeCount) {
+        error('Invalid reference count for ${variable.element}:\n'
+              '- Variable has $reads reads and $writes writes\n'
+              '- Reference count is ${variable.readCount} reads and '
+              '${variable.writeCount} writes');
+      }
+    }
+  }
+
+}
+