content: // Copyright (c) 2013, 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 tracer;
  
  import 'dart:async' show EventSink;
  
  import 'ssa.dart';
  import '../js_backend/js_backend.dart';
  import '../dart2jslib.dart';
  
  const bool GENERATE_SSA_TRACE = false;
  const String SSA_TRACE_FILTER = null;
  
  class HTracer extends HGraphVisitor implements Tracer {
    Compiler compiler;
    JavaScriptItemCompilationContext context;
    int indent = 0;
    final EventSink<String> output;
    final bool enabled = GENERATE_SSA_TRACE;
    bool traceActive = false;
  
    HTracer(this.output);
  
    void close() {
      if (enabled) output.close();
    }
  
    void traceCompilation(String methodName,
                          JavaScriptItemCompilationContext compilationContext,
                          Compiler compiler) {
      if (!enabled) return;
      this.context = compilationContext;
      this.compiler = compiler;
      traceActive =
          SSA_TRACE_FILTER == null || methodName.contains(SSA_TRACE_FILTER);
      if (!traceActive) return;
      tag("compilation", () {
        printProperty("name", methodName);
        printProperty("method", methodName);
        printProperty("date", new DateTime.now().millisecondsSinceEpoch);
      });
    }
  
    void traceGraph(String name, HGraph graph) {
      if (!traceActive) return;
      tag("cfg", () {
        printProperty("name", name);
        visitDominatorTree(graph);
      });
    }
  
    void addPredecessors(HBasicBlock block) {
      if (block.predecessors.isEmpty) {
        printEmptyProperty("predecessors");
      } else {
        addIndent();
        add("predecessors");
        for (HBasicBlock predecessor in block.predecessors) {
          add(' "B${predecessor.id}"');
        }
        add("\n");
      }
    }
  
    void addSuccessors(HBasicBlock block) {
      if (block.successors.isEmpty) {
        printEmptyProperty("successors");
      } else {
        addIndent();
        add("successors");
        for (HBasicBlock successor in block.successors) {
          add(' "B${successor.id}"');
        }
        add("\n");
      }
    }
  
    void addInstructions(HInstructionStringifier stringifier,
                         HInstructionList list) {
      for (HInstruction instruction = list.first;
           instruction != null;
           instruction = instruction.next) {
        int bci = 0;
        int uses = instruction.usedBy.length;
        String changes = instruction.sideEffects.hasSideEffects() ? '!' : ' ';
        String depends = instruction.sideEffects.dependsOnSomething() ? '?' : '';
        addIndent();
        String temporaryId = stringifier.temporaryId(instruction);
        String instructionString = stringifier.visit(instruction);
        add("$bci $uses $temporaryId $instructionString $changes $depends <|@\n");
      }
    }
  
    void visitBasicBlock(HBasicBlock block) {
      HInstructionStringifier stringifier =
          new HInstructionStringifier(context, block, compiler);
      assert(block.id != null);
      tag("block", () {
        printProperty("name", "B${block.id}");
        printProperty("from_bci", -1);
        printProperty("to_bci", -1);
        addPredecessors(block);
        addSuccessors(block);
        printEmptyProperty("xhandlers");
        printEmptyProperty("flags");
        if (block.dominator != null) {
          printProperty("dominator", "B${block.dominator.id}");
        }
        tag("states", () {
          tag("locals", () {
            printProperty("size", 0);
            printProperty("method", "None");
            block.forEachPhi((phi) {
              String phiId = stringifier.temporaryId(phi);
              StringBuffer inputIds = new StringBuffer();
              for (int i = 0; i < phi.inputs.length; i++) {
                inputIds.write(stringifier.temporaryId(phi.inputs[i]));
                inputIds.write(" ");
              }
              println("${phi.id} $phiId [ $inputIds]");
            });
          });
        });
        tag("HIR", () {
          addInstructions(stringifier, block.phis);
          addInstructions(stringifier, block);
        });
      });
    }
  
    void tag(String tagName, Function f) {
      println("begin_$tagName");
      indent++;
      f();
      indent--;
      println("end_$tagName");
    }
  
    void println(String string) {
      addIndent();
      add(string);
      add("\n");
    }
  
    void printEmptyProperty(String propertyName) {
      println(propertyName);
    }
  
    void printProperty(String propertyName, var value) {
      if (value is num) {
        println("$propertyName $value");
      } else {
        println('$propertyName "$value"');
      }
    }
  
    void add(String string) {
      output.add(string);
    }
  
    void addIndent() {
      for (int i = 0; i < indent; i++) {
        add("  ");
      }
    }
  }
  
  class HInstructionStringifier implements HVisitor<String> {
    final Compiler compiler;
    final JavaScriptItemCompilationContext context;
    final HBasicBlock currentBlock;
  
    HInstructionStringifier(this.context, this.currentBlock, this.compiler);
  
    visit(HInstruction node) => '${node.accept(this)} ${node.instructionType}';
  
    String temporaryId(HInstruction instruction) {
      String prefix;
      if (instruction.isNull()) {
        prefix = 'u';
      } else if (instruction.isConflicting()) {
        prefix = 'c';
      } else if (instruction.isExtendableArray(compiler)) {
        prefix = 'e';
      } else if (instruction.isFixedArray(compiler)) {
        prefix = 'f';
      } else if (instruction.isMutableArray(compiler)) {
        prefix = 'm';
      } else if (instruction.isReadableArray(compiler)) {
        prefix = 'a';
      } else if (instruction.isString(compiler)) {
        prefix = 's';
      } else if (instruction.isIndexablePrimitive(compiler)) {
        prefix = 'r';
      } else if (instruction.isBoolean(compiler)) {
        prefix = 'b';
      } else if (instruction.isInteger(compiler)) {
        prefix = 'i';
      } else if (instruction.isDouble(compiler)) {
        prefix = 'd';
      } else if (instruction.isNumber(compiler)) {
        prefix = 'n';
      } else if (instruction.instructionType.containsAll(compiler)) {
        prefix = 'v';
      } else {
        prefix = 'U';
      }
      return "$prefix${instruction.id}";
    }
  
    String visitBoolify(HBoolify node) {
      return "Boolify: ${temporaryId(node.inputs[0])}";
    }
  
    String handleInvokeBinary(HInvokeBinary node, String op) {
      String left = temporaryId(node.left);
      String right= temporaryId(node.right);
      return '$left $op $right';
    }
  
    String visitAdd(HAdd node) => handleInvokeBinary(node, '+');
  
    String visitBitAnd(HBitAnd node) => handleInvokeBinary(node, '&');
  
    String visitBitNot(HBitNot node) {
      String operand = temporaryId(node.operand);
      return "~$operand";
    }
  
    String visitBitOr(HBitOr node) => handleInvokeBinary(node, '|');
  
    String visitBitXor(HBitXor node) => handleInvokeBinary(node, '^');
  
    String visitBoundsCheck(HBoundsCheck node) {
      String lengthId = temporaryId(node.length);
      String indexId = temporaryId(node.index);
      return "Bounds check: length = $lengthId, index = $indexId";
    }
  
    String visitBreak(HBreak node) {
      HBasicBlock target = currentBlock.successors[0];
      if (node.label != null) {
        return "Break ${node.label.labelName}: (B${target.id})";
      }
      return "Break: (B${target.id})";
    }
  
    String visitConstant(HConstant constant) => "Constant ${constant.constant}";
  
    String visitContinue(HContinue node) {
      HBasicBlock target = currentBlock.successors[0];
      if (node.label != null) {
        return "Continue ${node.label.labelName}: (B${target.id})";
      }
      return "Continue: (B${target.id})";
    }
  
    String visitDivide(HDivide node) => handleInvokeBinary(node, '/');
  
    String visitExit(HExit node) => "exit";
  
    String visitFieldGet(HFieldGet node) {
      if (node.isNullCheck) {
        return 'null check on ${temporaryId(node.receiver)}';
      }
      String fieldName = node.element.name;
      return 'field get ${temporaryId(node.receiver)}.$fieldName';
    }
  
    String visitFieldSet(HFieldSet node) {
      String valueId = temporaryId(node.value);
      String fieldName = node.element.name;
      return 'field set ${temporaryId(node.receiver)}.$fieldName to $valueId';
    }
  
    String visitLocalGet(HLocalGet node) {
      String localName = node.element.name;
      return 'local get ${temporaryId(node.local)}.$localName';
    }
  
    String visitLocalSet(HLocalSet node) {
      String valueId = temporaryId(node.value);
      String localName = node.element.name;
      return 'local set ${temporaryId(node.local)}.$localName to $valueId';
    }
  
    String visitGoto(HGoto node) {
      HBasicBlock target = currentBlock.successors[0];
      return "Goto: (B${target.id})";
    }
  
    String visitGreater(HGreater node) => handleInvokeBinary(node, '>');
    String visitGreaterEqual(HGreaterEqual node) {
      handleInvokeBinary(node, '>=');
    }
    String visitIdentity(HIdentity node) => handleInvokeBinary(node, '===');
  
    String visitIf(HIf node) {
      HBasicBlock thenBlock = currentBlock.successors[0];
      HBasicBlock elseBlock = currentBlock.successors[1];
      String conditionId = temporaryId(node.inputs[0]);
      return "If ($conditionId): (B${thenBlock.id}) else (B${elseBlock.id})";
    }
  
    String visitGenericInvoke(String invokeType, String functionName,
                              List<HInstruction> arguments) {
      StringBuffer argumentsString = new StringBuffer();
      for (int i = 0; i < arguments.length; i++) {
        if (i != 0) argumentsString.write(", ");
        argumentsString.write(temporaryId(arguments[i]));
      }
      return "$invokeType: $functionName($argumentsString)";
    }
  
    String visitIndex(HIndex node) {
      String receiver = temporaryId(node.receiver);
      String index = temporaryId(node.index);
      return "Index: $receiver[$index]";
    }
  
    String visitIndexAssign(HIndexAssign node) {
      String receiver = temporaryId(node.receiver);
      String index = temporaryId(node.index);
      String value = temporaryId(node.value);
      return "IndexAssign: $receiver[$index] = $value";
    }
  
    String visitInterceptor(HInterceptor node) {
      String value = temporaryId(node.inputs[0]);
      return "Intercept: $value";
    }
  
    String visitInvokeClosure(HInvokeClosure node)
        => visitInvokeDynamic(node, "closure");
  
    String visitInvokeDynamic(HInvokeDynamic invoke, String kind) {
      String receiver = temporaryId(invoke.receiver);
      String name = invoke.selector.name;
      String target = "($kind) $receiver.$name";
      int offset = HInvoke.ARGUMENTS_OFFSET;
      List arguments = invoke.inputs.sublist(offset);
      return visitGenericInvoke("Invoke", target, arguments);
    }
  
    String visitInvokeDynamicMethod(HInvokeDynamicMethod node)
        => visitInvokeDynamic(node, "method");
    String visitInvokeDynamicGetter(HInvokeDynamicGetter node)
        => visitInvokeDynamic(node, "get");
    String visitInvokeDynamicSetter(HInvokeDynamicSetter node)
        => visitInvokeDynamic(node, "set");
  
    String visitInvokeStatic(HInvokeStatic invoke) {
      String target = invoke.element.name;
      return visitGenericInvoke("Invoke", target, invoke.inputs);
    }
  
    String visitInvokeSuper(HInvokeSuper invoke) {
      String target = invoke.element.name;
      return visitGenericInvoke("Invoke super", target, invoke.inputs);
    }
  
    String visitInvokeConstructorBody(HInvokeConstructorBody invoke) {
      String target = invoke.element.name;
      return visitGenericInvoke("Invoke constructor body", target, invoke.inputs);
    }
  
    String visitForeign(HForeign foreign) {
      return visitGenericInvoke("Foreign", "${foreign.codeAst}", foreign.inputs);
    }
  
    String visitForeignNew(HForeignNew node) {
      return visitGenericInvoke("New",
                                "${node.element.name}",
                                node.inputs);
    }
  
    String visitLess(HLess node) => handleInvokeBinary(node, '<');
    String visitLessEqual(HLessEqual node) => handleInvokeBinary(node, '<=');
  
    String visitLiteralList(HLiteralList node) {
      StringBuffer elementsString = new StringBuffer();
      for (int i = 0; i < node.inputs.length; i++) {
        if (i != 0) elementsString.write(", ");
        elementsString.write(temporaryId(node.inputs[i]));
      }
      return "Literal list: [$elementsString]";
    }
  
    String visitLoopBranch(HLoopBranch branch) {
      HBasicBlock bodyBlock = currentBlock.successors[0];
      HBasicBlock exitBlock = currentBlock.successors[1];
      String conditionId = temporaryId(branch.inputs[0]);
      return "While ($conditionId): (B${bodyBlock.id}) then (B${exitBlock.id})";
    }
  
    String visitMultiply(HMultiply node) => handleInvokeBinary(node, '*');
  
    String visitNegate(HNegate node) {
      String operand = temporaryId(node.operand);
      return "-$operand";
    }
  
    String visitNot(HNot node) => "Not: ${temporaryId(node.inputs[0])}";
  
    String visitParameterValue(HParameterValue node) {
      return "p${node.sourceElement.name}";
    }
  
    String visitLocalValue(HLocalValue node) {
      return "l${node.sourceElement.name}";
    }
  
    String visitPhi(HPhi phi) {
      StringBuffer buffer = new StringBuffer();
      buffer.write("Phi(");
      for (int i = 0; i < phi.inputs.length; i++) {
        if (i > 0) buffer.write(", ");
        buffer.write(temporaryId(phi.inputs[i]));
      }
      buffer.write(")");
      return buffer.toString();
    }
  
    String visitReturn(HReturn node) => "Return ${temporaryId(node.inputs[0])}";
  
    String visitShiftLeft(HShiftLeft node) => handleInvokeBinary(node, '<<');
  
    String visitStatic(HStatic node)
        => "Static ${node.element.name}";
  
    String visitLazyStatic(HLazyStatic node)
        => "LazyStatic ${node.element.name}";
  
    String visitOneShotInterceptor(HOneShotInterceptor node)
        => visitInvokeDynamic(node, "one shot interceptor");
  
    String visitStaticStore(HStaticStore node) {
      String lhs = node.element.name;
      return "Static $lhs = ${temporaryId(node.inputs[0])}";
    }
  
    String visitStringConcat(HStringConcat node) {
      var leftId = temporaryId(node.left);
      var rightId = temporaryId(node.right);
      return "StringConcat: $leftId + $rightId";
    }
  
    String visitStringify(HStringify node) {
      return "Stringify: ${node.inputs[0]}";
    }
  
    String visitSubtract(HSubtract node) => handleInvokeBinary(node, '-');
  
    String visitSwitch(HSwitch node) {
      StringBuffer buf = new StringBuffer();
      buf.write("Switch: (");
      buf.write(temporaryId(node.inputs[0]));
      buf.write(") ");
      for (int i = 1; i < node.inputs.length; i++) {
        buf.write(temporaryId(node.inputs[i]));
        buf.write(": B");
        buf.write(node.block.successors[i - 1].id);
        buf.write(", ");
      }
      buf.write("default: B");
      buf.write(node.block.successors.last.id);
      return buf.toString();
    }
  
    String visitThis(HThis node) => "this";
  
    String visitThrow(HThrow node) => "Throw ${temporaryId(node.inputs[0])}";
  
    String visitThrowExpression(HThrowExpression node) {
      return "ThrowExpression ${temporaryId(node.inputs[0])}";
    }
  
    String visitExitTry(HExitTry node) {
      return "Exit try";
    }
  
    String visitTry(HTry node) {
      List<HBasicBlock> successors = currentBlock.successors;
      String tryBlock = 'B${successors[0].id}';
      String catchBlock = 'none';
      if (node.catchBlock != null) {
        catchBlock = 'B${successors[1].id}';
      }
  
      String finallyBlock = 'none';
      if (node.finallyBlock != null) {
        finallyBlock = 'B${node.finallyBlock.id}';
      }
  
      return "Try: $tryBlock, Catch: $catchBlock, Finally: $finallyBlock, "
          "Join: B${successors.last.id}";
    }
  
    String visitIs(HIs node) {
      String type = node.typeExpression.toString();
      return "TypeTest: ${temporaryId(node.expression)} is $type";
    }
  
    String visitTypeConversion(HTypeConversion node) {
      assert(node.inputs.length <= 2);
      String otherInput = (node.inputs.length == 2)
          ? temporaryId(node.inputs[1])
          : '';
      return "TypeConversion: ${temporaryId(node.checkedInput)} to "
        "${node.instructionType} $otherInput";
    }
  
    String visitTypeKnown(HTypeKnown node) {
      assert(node.inputs.length == 1);
      return "TypeKnown: ${temporaryId(node.checkedInput)} is ${node.knownType}";
    }
  
    String visitRangeConversion(HRangeConversion node) {
      return "RangeConversion: ${node.checkedInput}";
    }
  }
  