dart/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) {
    if (node.thisParameter != null) {
      markAsSeen(node.thisParameter);
    }
    node.parameters.forEach(markAsSeen);
    if (node.body != null) {
      doInOptionalScope(node.thisParameter, node,
          () => doInScope(node.parameters, node, () => visit(node.body)));
    }
  }

  @override
  visitConstructorDefinition(ConstructorDefinition node) {
    if (node.thisParameter != null) {
      markAsSeen(node.thisParameter);
    }
    node.parameters.forEach(markAsSeen);
    doInScope(node.parameters, node, () {
      if (node.initializers != null) node.initializers.forEach(visit);
      if (node.body != null) {
        doInOptionalScope(node.thisParameter, node, () => visit(node.body));
      }
    });
  }

  doInOptionalScope(Parameter parameter, Node node, action) {
    return (parameter == null)
        ? action()
        : doInScope([parameter], node, action);
  }

  @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);
  }

}