// Copyright (c) 2012, 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.

part of js;

abstract class NodeVisitor<T> {
  T visitProgram(Program node);

  T visitBlock(Block node);
  T visitExpressionStatement(ExpressionStatement node);
  T visitEmptyStatement(EmptyStatement node);
  T visitIf(If node);
  T visitFor(For node);
  T visitForIn(ForIn node);
  T visitWhile(While node);
  T visitDo(Do node);
  T visitContinue(Continue node);
  T visitBreak(Break node);
  T visitReturn(Return node);
  T visitThrow(Throw node);
  T visitTry(Try node);
  T visitCatch(Catch node);
  T visitSwitch(Switch node);
  T visitCase(Case node);
  T visitDefault(Default node);
  T visitFunctionDeclaration(FunctionDeclaration node);
  T visitLabeledStatement(LabeledStatement node);
  T visitLiteralStatement(LiteralStatement node);

  T visitLiteralExpression(LiteralExpression node);
  T visitVariableDeclarationList(VariableDeclarationList node);
  T visitSequence(Sequence node);
  T visitAssignment(Assignment node);
  T visitVariableInitialization(VariableInitialization node);
  T visitConditional(Conditional cond);
  T visitNew(New node);
  T visitCall(Call node);
  T visitBinary(Binary node);
  T visitPrefix(Prefix node);
  T visitPostfix(Postfix node);

  T visitVariableUse(VariableUse node);
  T visitThis(This node);
  T visitVariableDeclaration(VariableDeclaration node);
  T visitParameter(Parameter node);
  T visitAccess(PropertyAccess node);

  T visitNamedFunction(NamedFunction node);
  T visitFun(Fun node);

  T visitLiteralBool(LiteralBool node);
  T visitLiteralString(LiteralString node);
  T visitLiteralNumber(LiteralNumber node);
  T visitLiteralNull(LiteralNull node);

  T visitArrayInitializer(ArrayInitializer node);
  T visitArrayElement(ArrayElement node);
  T visitObjectInitializer(ObjectInitializer node);
  T visitProperty(Property node);
  T visitRegExpLiteral(RegExpLiteral node);

  T visitComment(Comment node);
}

class BaseVisitor<T> implements NodeVisitor<T> {
  T visitNode(Node node) {
    node.visitChildren(this);
    return null;
  }

  T visitProgram(Program node) => visitNode(node);

  T visitStatement(Statement node) => visitNode(node);
  T visitLoop(Loop node) => visitStatement(node);
  T visitJump(Statement node) => visitStatement(node);

  T visitBlock(Block node) => visitStatement(node);
  T visitExpressionStatement(ExpressionStatement node)
      => visitStatement(node);
  T visitEmptyStatement(EmptyStatement node) => visitStatement(node);
  T visitIf(If node) => visitStatement(node);
  T visitFor(For node) => visitLoop(node);
  T visitForIn(ForIn node) => visitLoop(node);
  T visitWhile(While node) => visitLoop(node);
  T visitDo(Do node) => visitLoop(node);
  T visitContinue(Continue node) => visitJump(node);
  T visitBreak(Break node) => visitJump(node);
  T visitReturn(Return node) => visitJump(node);
  T visitThrow(Throw node) => visitJump(node);
  T visitTry(Try node) => visitStatement(node);
  T visitSwitch(Switch node) => visitStatement(node);
  T visitFunctionDeclaration(FunctionDeclaration node)
      => visitStatement(node);
  T visitLabeledStatement(LabeledStatement node) => visitStatement(node);
  T visitLiteralStatement(LiteralStatement node) => visitStatement(node);

  T visitCatch(Catch node) => visitNode(node);
  T visitCase(Case node) => visitNode(node);
  T visitDefault(Default node) => visitNode(node);

  T visitExpression(Expression node) => visitNode(node);
  T visitVariableReference(VariableReference node) => visitExpression(node);

  T visitLiteralExpression(LiteralExpression node) => visitExpression(node);
  T visitVariableDeclarationList(VariableDeclarationList node)
      => visitExpression(node);
  T visitSequence(Sequence node) => visitExpression(node);
  T visitAssignment(Assignment node) => visitExpression(node);
  T visitVariableInitialization(VariableInitialization node) {
    if (node.value != null) {
      visitAssignment(node);
    } else {
      visitExpression(node);
    }
  }
  T visitConditional(Conditional node) => visitExpression(node);
  T visitNew(New node) => visitExpression(node);
  T visitCall(Call node) => visitExpression(node);
  T visitBinary(Binary node) => visitCall(node);
  T visitPrefix(Prefix node) => visitCall(node);
  T visitPostfix(Postfix node) => visitCall(node);
  T visitAccess(PropertyAccess node) => visitExpression(node);

  T visitVariableUse(VariableUse node) => visitVariableReference(node);
  T visitVariableDeclaration(VariableDeclaration node)
      => visitVariableReference(node);
  T visitParameter(Parameter node) => visitVariableDeclaration(node);
  T visitThis(This node) => visitParameter(node);

  T visitNamedFunction(NamedFunction node) => visitExpression(node);
  T visitFun(Fun node) => visitExpression(node);

  T visitLiteral(Literal node) => visitExpression(node);

  T visitLiteralBool(LiteralBool node) => visitLiteral(node);
  T visitLiteralString(LiteralString node) => visitLiteral(node);
  T visitLiteralNumber(LiteralNumber node) => visitLiteral(node);
  T visitLiteralNull(LiteralNull node) => visitLiteral(node);

  T visitArrayInitializer(ArrayInitializer node) => visitExpression(node);
  T visitArrayElement(ArrayElement node) => visitNode(node);
  T visitObjectInitializer(ObjectInitializer node) => visitExpression(node);
  T visitProperty(Property node) => visitNode(node);
  T visitRegExpLiteral(RegExpLiteral node) => visitExpression(node);

  // Ignore comments by default.
  T visitComment(Comment node) {}
}

abstract class Node {
  var sourcePosition;
  var endSourcePosition;

  accept(NodeVisitor visitor);
  void visitChildren(NodeVisitor visitor);

  VariableUse asVariableUse() => null;

  Statement toStatement() {
    throw new UnsupportedError('toStatement');
  }
}

class Program extends Node {
  final List<Statement> body;
  Program(this.body);

  accept(NodeVisitor visitor) => visitor.visitProgram(this);
  void visitChildren(NodeVisitor visitor) {
    for (Statement statement in body) statement.accept(visitor);
  }
}

abstract class Statement extends Node {
  Statement toStatement() => this;
}

class Block extends Statement {
  final List<Statement> statements;
  Block(this.statements);
  Block.empty() : this.statements = <Statement>[];

  accept(NodeVisitor visitor) => visitor.visitBlock(this);
  void visitChildren(NodeVisitor visitor) {
    for (Statement statement in statements) statement.accept(visitor);
  }
}

class ExpressionStatement extends Statement {
  final Expression expression;
  ExpressionStatement(this.expression);

  accept(NodeVisitor visitor) => visitor.visitExpressionStatement(this);
  void visitChildren(NodeVisitor visitor) { expression.accept(visitor); }
}

class EmptyStatement extends Statement {
  EmptyStatement();

  accept(NodeVisitor visitor) => visitor.visitEmptyStatement(this);
  void visitChildren(NodeVisitor visitor) {}
}

class If extends Statement {
  final Expression condition;
  final Node then;
  final Node otherwise;

  If(this.condition, this.then, this.otherwise);
  If.noElse(this.condition, this.then) : this.otherwise = new EmptyStatement();

  bool get hasElse => otherwise is !EmptyStatement;

  accept(NodeVisitor visitor) => visitor.visitIf(this);

  void visitChildren(NodeVisitor visitor) {
    condition.accept(visitor);
    then.accept(visitor);
    otherwise.accept(visitor);
  }
}

abstract class Loop extends Statement {
  final Statement body;
  Loop(this.body);
}

class For extends Loop {
  final Expression init;
  final Expression condition;
  final Expression update;

  For(this.init, this.condition, this.update, Statement body) : super(body);

  accept(NodeVisitor visitor) => visitor.visitFor(this);

  void visitChildren(NodeVisitor visitor) {
    if (init != null) init.accept(visitor);
    if (condition != null) condition.accept(visitor);
    if (update != null) update.accept(visitor);
    body.accept(visitor);
  }
}

class ForIn extends Loop {
  // Note that [VariableDeclarationList] is a subclass of [Expression].
  // Therefore we can type the leftHandSide as [Expression].
  final Expression leftHandSide;
  final Expression object;

  ForIn(this.leftHandSide, this.object, Statement body) : super(body);

  accept(NodeVisitor visitor) => visitor.visitForIn(this);

  void visitChildren(NodeVisitor visitor) {
    leftHandSide.accept(visitor);
    object.accept(visitor);
    body.accept(visitor);
  }
}

class While extends Loop {
  final Node condition;

  While(this.condition, Statement body) : super(body);

  accept(NodeVisitor visitor) => visitor.visitWhile(this);

  void visitChildren(NodeVisitor visitor) {
    condition.accept(visitor);
    body.accept(visitor);
  }
}

class Do extends Loop {
  final Expression condition;

  Do(Statement body, this.condition) : super(body);

  accept(NodeVisitor visitor) => visitor.visitDo(this);

  void visitChildren(NodeVisitor visitor) {
    body.accept(visitor);
    condition.accept(visitor);
  }
}

class Continue extends Statement {
  final String targetLabel;  // Can be null.

  Continue(this.targetLabel);

  accept(NodeVisitor visitor) => visitor.visitContinue(this);
  void visitChildren(NodeVisitor visitor) {}
}

class Break extends Statement {
  final String targetLabel;  // Can be null.

  Break(this.targetLabel);

  accept(NodeVisitor visitor) => visitor.visitBreak(this);
  void visitChildren(NodeVisitor visitor) {}
}

class Return extends Statement {
  final Expression value;  // Can be null.

  Return([this.value = null]);

  accept(NodeVisitor visitor) => visitor.visitReturn(this);

  void visitChildren(NodeVisitor visitor) {
    if (value != null) value.accept(visitor);
  }
}

class Throw extends Statement {
  final Expression expression;

  Throw(this.expression);

  accept(NodeVisitor visitor) => visitor.visitThrow(this);

  void visitChildren(NodeVisitor visitor) {
    expression.accept(visitor);
  }
}

class Try extends Statement {
  final Block body;
  final Catch catchPart;  // Can be null if [finallyPart] is non-null.
  final Block finallyPart;  // Can be null if [catchPart] is non-null.

  Try(this.body, this.catchPart, this.finallyPart) {
    assert(catchPart != null || finallyPart != null);
  }

  accept(NodeVisitor visitor) => visitor.visitTry(this);

  void visitChildren(NodeVisitor visitor) {
    body.accept(visitor);
    if (catchPart != null) catchPart.accept(visitor);
    if (finallyPart != null) finallyPart.accept(visitor);
  }
}

class Catch extends Node {
  final VariableDeclaration declaration;
  final Block body;

  Catch(this.declaration, this.body);

  accept(NodeVisitor visitor) => visitor.visitCatch(this);

  void visitChildren(NodeVisitor visitor) {
    declaration.accept(visitor);
    body.accept(visitor);
  }
}

class Switch extends Statement {
  final Expression key;
  final List<SwitchClause> cases;

  Switch(this.key, this.cases);

  accept(NodeVisitor visitor) => visitor.visitSwitch(this);

  void visitChildren(NodeVisitor visitor) {
    key.accept(visitor);
    for (SwitchClause clause in cases) clause.accept(visitor);
  }
}

abstract class SwitchClause extends Node {
  final Block body;

  SwitchClause(this.body);
}

class Case extends SwitchClause {
  final Expression expression;

  Case(this.expression, Block body) : super(body);

  accept(NodeVisitor visitor) => visitor.visitCase(this);

  void visitChildren(NodeVisitor visitor) {
    expression.accept(visitor);
    body.accept(visitor);
  }
}

class Default extends SwitchClause {
  Default(Block body) : super(body);

  accept(NodeVisitor visitor) => visitor.visitDefault(this);

  void visitChildren(NodeVisitor visitor) {
    body.accept(visitor);
  }
}

class FunctionDeclaration extends Statement {
  final VariableDeclaration name;
  final Fun function;

  FunctionDeclaration(this.name, this.function);

  accept(NodeVisitor visitor) => visitor.visitFunctionDeclaration(this);

  void visitChildren(NodeVisitor visitor) {
    name.accept(visitor);
    function.accept(visitor);
  }
}

class LabeledStatement extends Statement {
  final String label;
  final Statement body;

  LabeledStatement(this.label, this.body);

  accept(NodeVisitor visitor) => visitor.visitLabeledStatement(this);

  void visitChildren(NodeVisitor visitor) {
    body.accept(visitor);
  }
}

class LiteralStatement extends Statement {
  final String code;

  LiteralStatement(this.code);

  accept(NodeVisitor visitor) => visitor.visitLiteralStatement(this);
  void visitChildren(NodeVisitor visitor) { }
}

abstract class Expression extends Node {
  int get precedenceLevel;

  Call callWith(List<Expression> arguments) => new Call(this, arguments);

  New newWith(List<Expression> arguments) => new New(this, arguments);

  PropertyAccess operator [](expression) {
    if (expression is Expression) {
      return new PropertyAccess(this, expression);
    } else if (expression is int) {
      return new PropertyAccess.indexed(this, expression);
    } else if (expression is String) {
      return new PropertyAccess.field(this, expression);
    } else {
      throw new ArgumentError('Expected an int, String, or Expression');
    }
  }

  Statement toStatement() => new ExpressionStatement(this);

  Call call([expression]) {
    List<Expression> arguments;
    if (expression == null) {
      arguments = <Expression>[];
    } else if (expression is List) {
      arguments = expression.map(js.toExpression).toList();
    } else {
      arguments = <Expression>[js.toExpression(expression)];
    }
    return callWith(arguments);
  }

  Expression equals(expression) => binary('==', expression);

  Expression strictEquals(expression) => binary('===', expression);

  Expression notEquals(expression) => binary('!=', expression);

  Expression operator +(expression) => binary('+', expression);

  Expression operator -(expression) => binary('-', expression);

  Expression operator &(expression) => binary('&', expression);

  Expression operator <(expression) => binary('<', expression);

  Expression operator >(expression) => binary('>', expression);

  Expression operator >=(expression) => binary('>=', expression);

  Expression binary(String operator, expression) {
    return new Binary(operator, this, js.toExpression(expression));
  }

  Expression assign(expression) {
    return new Assignment(this, js.toExpression(expression));
  }

  Expression update(String operator, expression) {
    return new Assignment.compound(this, operator, js.toExpression(expression));
  }

  Expression get plusPlus => new Postfix('++', this);

  Prefix get typeof => new Prefix('typeof', this);

  Prefix get not => new Prefix('!', this);
}

class LiteralExpression extends Expression {
  final String template;
  final List<Expression> inputs;

  LiteralExpression(this.template) : inputs = const [];
  LiteralExpression.withData(this.template, this.inputs);

  accept(NodeVisitor visitor) => visitor.visitLiteralExpression(this);

  void visitChildren(NodeVisitor visitor) {
    for (Expression expr in inputs) expr.accept(visitor);
  }

  // Code that uses JS must take care of operator precedences, and
  // put parenthesis if needed.
  int get precedenceLevel => PRIMARY;
}

/**
 * [VariableDeclarationList] is a subclass of [Expression] to simplify the
 * AST.
 */
class VariableDeclarationList extends Expression {
  final List<VariableInitialization> declarations;

  VariableDeclarationList(this.declarations);

  accept(NodeVisitor visitor) => visitor.visitVariableDeclarationList(this);

  void visitChildren(NodeVisitor visitor) {
    for (VariableInitialization declaration in declarations) {
      declaration.accept(visitor);
    }
  }

  int get precedenceLevel => EXPRESSION;
}

class Sequence extends Expression {
  final List<Expression> expressions;

  Sequence(this.expressions);

  accept(NodeVisitor visitor) => visitor.visitSequence(this);

  void visitChildren(NodeVisitor visitor) {
    for (Expression expr in expressions) expr.accept(visitor);
  }

  int get precedenceLevel => EXPRESSION;
}

class Assignment extends Expression {
  final Expression leftHandSide;
  // Null, if the assignment is not compound.
  final VariableReference compoundTarget;
  final Expression value;  // May be null, for [VariableInitialization]s.

  Assignment(this.leftHandSide, this.value) : compoundTarget = null;
  Assignment.compound(this.leftHandSide, String op, this.value)
      : compoundTarget = new VariableUse(op);

  int get precedenceLevel => ASSIGNMENT;

  bool get isCompound => compoundTarget != null;
  String get op => compoundTarget == null ? null : compoundTarget.name;

  accept(NodeVisitor visitor) => visitor.visitAssignment(this);

  void visitChildren(NodeVisitor visitor) {
    leftHandSide.accept(visitor);
    if (compoundTarget != null) compoundTarget.accept(visitor);
    if (value != null) value.accept(visitor);
  }
}

class VariableInitialization extends Assignment {
  /** [value] may be null. */
  VariableInitialization(VariableDeclaration declaration, Expression value)
      : super(declaration, value);

  VariableDeclaration get declaration => leftHandSide;

  accept(NodeVisitor visitor) => visitor.visitVariableInitialization(this);
}

class Conditional extends Expression {
  final Expression condition;
  final Expression then;
  final Expression otherwise;

  Conditional(this.condition, this.then, this.otherwise);

  accept(NodeVisitor visitor) => visitor.visitConditional(this);

  void visitChildren(NodeVisitor visitor) {
    condition.accept(visitor);
    then.accept(visitor);
    otherwise.accept(visitor);
  }

  int get precedenceLevel => ASSIGNMENT;
}

class Call extends Expression {
  Expression target;
  List<Expression> arguments;

  Call(this.target, this.arguments);

  accept(NodeVisitor visitor) => visitor.visitCall(this);

  void visitChildren(NodeVisitor visitor) {
    target.accept(visitor);
    for (Expression arg in arguments) arg.accept(visitor);
  }

  int get precedenceLevel => CALL;
}

class New extends Call {
  New(Expression cls, List<Expression> arguments) : super(cls, arguments);

  accept(NodeVisitor visitor) => visitor.visitNew(this);
}

class Binary extends Call {
  Binary(String op, Expression left, Expression right)
      : super(new VariableUse(op), <Expression>[left, right]);

  String get op {
    VariableUse use = target;
    return use.name;
  }

  Expression get left => arguments[0];
  Expression get right => arguments[1];

  accept(NodeVisitor visitor) => visitor.visitBinary(this);

  int get precedenceLevel {
    // TODO(floitsch): switch to constant map.
    switch (op) {
      case "*":
      case "/":
      case "%":
        return MULTIPLICATIVE;
      case "+":
      case "-":
        return ADDITIVE;
      case "<<":
      case ">>":
      case ">>>":
        return SHIFT;
      case "<":
      case ">":
      case "<=":
      case ">=":
      case "instanceof":
      case "in":
        return RELATIONAL;
      case "==":
      case "===":
      case "!=":
      case "!==":
        return EQUALITY;
      case "&":
        return BIT_AND;
      case "^":
        return BIT_XOR;
      case "|":
        return BIT_OR;
      case "&&":
        return LOGICAL_AND;
      case "||":
        return LOGICAL_OR;
      default:
        throw new leg.CompilerCancelledException(
            "Internal Error: Unhandled binary operator: $op");
    }
  }
}

class Prefix extends Call {
  Prefix(String op, Expression arg)
      : super(new VariableUse(op), <Expression>[arg]);

  String get op => (target as VariableUse).name;
  Expression get argument => arguments[0];

  accept(NodeVisitor visitor) => visitor.visitPrefix(this);

  int get precedenceLevel => UNARY;
}

class Postfix extends Call {
  Postfix(String op, Expression arg)
      : super(new VariableUse(op), <Expression>[arg]);

  String get op => (target as VariableUse).name;
  Expression get argument => arguments[0];

  accept(NodeVisitor visitor) => visitor.visitPostfix(this);

  int get precedenceLevel => UNARY;
}

abstract class VariableReference extends Expression {
  final String name;

  // We treat operators as if they were special functions. They can thus be
  // referenced like other variables.
  VariableReference(this.name);

  accept(NodeVisitor visitor);
  int get precedenceLevel => PRIMARY;
  void visitChildren(NodeVisitor visitor) {}
}

class VariableUse extends VariableReference {
  VariableUse(String name) : super(name);

  accept(NodeVisitor visitor) => visitor.visitVariableUse(this);

  VariableUse asVariableUse() => this;
}

class VariableDeclaration extends VariableReference {
  VariableDeclaration(String name) : super(name);

  accept(NodeVisitor visitor) => visitor.visitVariableDeclaration(this);
}

class Parameter extends VariableDeclaration {
  Parameter(String id) : super(id);

  accept(NodeVisitor visitor) => visitor.visitParameter(this);
}

class This extends Parameter {
  This() : super("this");

  accept(NodeVisitor visitor) => visitor.visitThis(this);
}

class NamedFunction extends Expression {
  final VariableDeclaration name;
  final Fun function;

  NamedFunction(this.name, this.function);

  accept(NodeVisitor visitor) => visitor.visitNamedFunction(this);

  void visitChildren(NodeVisitor visitor) {
    name.accept(visitor);
    function.accept(visitor);
  }

  int get precedenceLevel => CALL;
}

class Fun extends Expression {
  final List<Parameter> params;
  final Block body;

  Fun(this.params, this.body);

  accept(NodeVisitor visitor) => visitor.visitFun(this);

  void visitChildren(NodeVisitor visitor) {
    for (Parameter param in params) param.accept(visitor);
    body.accept(visitor);
  }

  int get precedenceLevel => CALL;
}

class PropertyAccess extends Expression {
  final Expression receiver;
  final Expression selector;

  PropertyAccess(this.receiver, this.selector);
  PropertyAccess.field(this.receiver, String fieldName)
      : selector = new LiteralString("'$fieldName'");
  PropertyAccess.indexed(this.receiver, int index)
      : selector = new LiteralNumber('$index');

  accept(NodeVisitor visitor) => visitor.visitAccess(this);

  void visitChildren(NodeVisitor visitor) {
    receiver.accept(visitor);
    selector.accept(visitor);
  }

  int get precedenceLevel => CALL;
}

abstract class Literal extends Expression {
  void visitChildren(NodeVisitor visitor) {}

  int get precedenceLevel => PRIMARY;
}

class LiteralBool extends Literal {
  final bool value;

  LiteralBool(this.value);

  accept(NodeVisitor visitor) => visitor.visitLiteralBool(this);
  // [visitChildren] inherited from [Literal].
}

class LiteralNull extends Literal {
  LiteralNull();

  accept(NodeVisitor visitor) => visitor.visitLiteralNull(this);
}

class LiteralString extends Literal {
  final String value;

  LiteralString(this.value);

  accept(NodeVisitor visitor) => visitor.visitLiteralString(this);
}

class LiteralNumber extends Literal {
  final String value;

  LiteralNumber(this.value);

  accept(NodeVisitor visitor) => visitor.visitLiteralNumber(this);
}

class ArrayInitializer extends Expression {
  final int length;
  // We represent the array as sparse list of elements. Each element knows its
  // position in the array.
  final List<ArrayElement> elements;

  ArrayInitializer(this.length, this.elements);

  factory ArrayInitializer.from(Iterable<Expression> expressions) =>
      new ArrayInitializer(expressions.length, _convert(expressions));

  accept(NodeVisitor visitor) => visitor.visitArrayInitializer(this);

  void visitChildren(NodeVisitor visitor) {
    for (ArrayElement element in elements) element.accept(visitor);
  }

  int get precedenceLevel => PRIMARY;

  static List<ArrayElement> _convert(Iterable<Expression> expressions) {
    int index = 0;
    return expressions.map(
        (expression) => new ArrayElement(index++, expression))
        .toList();
  }
}

/**
 * An expression inside an [ArrayInitializer]. An [ArrayElement] knows
 * its position in the containing [ArrayInitializer].
 */
class ArrayElement extends Node {
  int index;
  Expression value;

  ArrayElement(this.index, this.value);

  accept(NodeVisitor visitor) => visitor.visitArrayElement(this);

  void visitChildren(NodeVisitor visitor) {
    value.accept(visitor);
  }
}

class ObjectInitializer extends Expression {
  List<Property> properties;

  ObjectInitializer(this.properties);

  accept(NodeVisitor visitor) => visitor.visitObjectInitializer(this);

  void visitChildren(NodeVisitor visitor) {
    for (Property init in properties) init.accept(visitor);
  }

  int get precedenceLevel => PRIMARY;
}

class Property extends Node {
  Literal name;
  Expression value;

  Property(this.name, this.value);

  accept(NodeVisitor visitor) => visitor.visitProperty(this);

  void visitChildren(NodeVisitor visitor) {
    name.accept(visitor);
    value.accept(visitor);
  }
}

/**
 * [RegExpLiteral]s, despite being called "Literal", are not inheriting from
 * [Literal]. Indeed, regular expressions in JavaScript have a side-effect and
 * are thus not in the same category as numbers or strings.
 */
class RegExpLiteral extends Expression {
  /** Contains the pattern and the flags.*/
  String pattern;

  RegExpLiteral(this.pattern);

  accept(NodeVisitor visitor) => visitor.visitRegExpLiteral(this);
  void visitChildren(NodeVisitor visitor) {}

  int get precedenceLevel => PRIMARY;
}

/**
 * A comment.
 *
 * Extends [Statement] so we can add comments before statements in
 * [Block] and [Program].
 */
class Comment extends Statement {
  final String comment;

  Comment(this.comment);

  accept(NodeVisitor visitor) => visitor.visitComment(this);

  void visitChildren(NodeVisitor visitor) {}
}

class JsBuilder {
  const JsBuilder();

  Expression operator [](String source) {
    return new MiniJsParser(source).expression();
  }

  // TODO(ahe): Remove this method.
  Binary equals(Expression left, Expression right) {
    return new Binary('==', left, right);
  }

  // TODO(ahe): Remove this method.
  Binary strictEquals(Expression left, Expression right) {
    return new Binary('===', left, right);
  }

  LiteralString string(String value) => new LiteralString('"$value"');

  If if_(condition, thenPart, [elsePart]) {
    condition = toExpression(condition);
    return (elsePart == null)
        ? new If.noElse(condition, toStatement(thenPart))
        : new If(condition, toStatement(thenPart), toStatement(elsePart));
  }

  Return return_([value]) {
    return new Return(value == null ? null : toExpression(value));
  }

  Block block(statement) {
    if (statement is Block) {
      return statement;
    } else if (statement is List) {
      return new Block(statement.map(toStatement).toList());
    } else {
      return new Block(<Statement>[toStatement(statement)]);
    }
  }

  Fun fun(parameters, body) {
    Parameter toParameter(parameter) {
      if (parameter is String) {
        return new Parameter(parameter);
      } else if (parameter is Parameter) {
        return parameter;
      } else {
        throw new ArgumentError('parameter should be a String or a Parameter');
      }
    }
    if (parameters is! List) {
      parameters = [parameters];
    }
    return new Fun(parameters.map(toParameter).toList(), block(body));
  }

  Assignment assign(Expression leftHandSide, Expression value) {
    return new Assignment(leftHandSide, value);
  }

  Expression undefined() => new Prefix('void', new LiteralNumber('0'));

  VariableDeclarationList defineVar(String name, [initializer]) {
    if (initializer != null) {
      initializer = toExpression(initializer);
    }
    var declaration = new VariableDeclaration(name);
    var initialization = [new VariableInitialization(declaration, initializer)];
    return new VariableDeclarationList(initialization);
  }

  Statement toStatement(statement) {
    if (statement is List) {
      return new Block(statement.map(toStatement).toList());
    } else if (statement is Node) {
      return statement.toStatement();
    } else {
      throw new ArgumentError('statement');
    }
  }

  Expression toExpression(expression) {
    if (expression is Expression) {
      return expression;
    } else if (expression is String) {
      return this[expression];
    } else if (expression is num) {
      return new LiteralNumber('$expression');
    } else if (expression is bool) {
      return new LiteralBool(expression);
    } else if (expression is Map) {
      if (!expression.isEmpty) {
        throw new ArgumentError('expression should be an empty Map');
      }
      return new ObjectInitializer([]);
    } else {
      throw new ArgumentError('expression should be an Expression, '
                              'a String, a num, a bool, or a Map');
    }
  }

  ForIn forIn(String name, object, statement) {
    return new ForIn(defineVar(name),
                     toExpression(object),
                     toStatement(statement));
  }

  For for_(init, condition, update, statement) {
    return new For(
        toExpression(init), toExpression(condition), toExpression(update),
        toStatement(statement));
  }

  Try try_(body, {catchPart, finallyPart}) {
    if (catchPart != null) catchPart = toStatement(catchPart);
    if (finallyPart != null) finallyPart = toStatement(finallyPart);
    return new Try(toStatement(body), catchPart, finallyPart);
  }

  Comment comment(String text) => new Comment(text);
}

const JsBuilder js = const JsBuilder();

LiteralString string(String value) => js.string(value);

class MiniJsParserError {
  MiniJsParserError(this.parser, this.message) { }

  MiniJsParser parser;
  String message;

  String toString() {
    var codes =
        new List.fixedLength(parser.lastPosition, fill: charCodes.$SPACE);
    var spaces = new String.fromCharCodes(codes);
    return "Error in MiniJsParser:\n${parser.src}\n$spaces^\n$spaces$message\n";
  }
}

/// Mini JavaScript parser for tiny snippets of code that we want to make into
/// AST nodes.  Handles:
/// * identifiers.
/// * dot access.
/// * method calls.
/// * [] access.
/// * array, string, boolean, null and numeric literals (no hex).
/// * most operators.
/// * brackets.
/// * var declarations.
/// Notable things it can't do yet include:
/// * operator precedence.
/// * non-empty object literals.
/// * throw, return.
/// * statements, including any flow control (if, while, for, etc.)
/// * the 'in' keyword.
///
/// It's a fairly standard recursive descent parser.
///
/// Literal strings are passed through to the final JS source code unchanged,
/// including the choice of surrounding quotes, so if you parse
/// r'var x = "foo\n\"bar\""' you will end up with
///   var x = "foo\n\"bar\"" in the final program.  String literals are
/// restricted to a small subset of the full set of allowed JS escapes in order
/// to get early errors for unintentional escape sequences without complicating
/// this parser unneccessarily.
class MiniJsParser {
  MiniJsParser(this.src)
      : lastCategory = NONE,
        lastToken = null,
        lastPosition = 0,
        position = 0 {
    getSymbol();
  }

  int lastCategory;
  String lastToken;
  int lastPosition;
  int position;
  String src;

  static const NONE = -1;
  static const ALPHA = 0;
  static const NUMERIC = 1;
  static const STRING = 2;
  static const SYMBOL = 3;
  static const RELATION = 4;
  static const DOT = 5;
  static const LPAREN = 6;
  static const RPAREN = 7;
  static const LBRACE = 8;
  static const RBRACE = 9;
  static const LSQUARE = 10;
  static const RSQUARE = 11;
  static const COMMA = 12;
  static const QUERY = 13;
  static const COLON = 14;
  static const OTHER = 15;

  // Make sure that ]] is two symbols.
  bool singleCharCategory(int category) => category >= DOT;

  static String categoryToString(int cat) {
    switch (cat) {
      case NONE: return "NONE";
      case ALPHA: return "ALPHA";
      case NUMERIC: return "NUMERIC";
      case SYMBOL: return "SYMBOL";
      case RELATION: return "RELATION";
      case DOT: return "DOT";
      case LPAREN: return "LPAREN";
      case RPAREN: return "RPAREN";
      case LBRACE: return "LBRACE";
      case RBRACE: return "RBRACE";
      case RSQUARE: return "RSQUARE";
      case STRING: return "STRING";
      case COMMA: return "COMMA";
      case QUERY: return "QUERY";
      case COLON: return "COLON";
      case OTHER: return "OTHER";
    }
    return "Unknown: $cat";
  }

  static const CATEGORIES = const <int>[
      OTHER, OTHER, OTHER, OTHER, OTHER, OTHER, OTHER, OTHER,       // 0-7
      OTHER, OTHER, OTHER, OTHER, OTHER, OTHER, OTHER, OTHER,       // 8-15
      OTHER, OTHER, OTHER, OTHER, OTHER, OTHER, OTHER, OTHER,       // 16-23
      OTHER, OTHER, OTHER, OTHER, OTHER, OTHER, OTHER, OTHER,       // 24-31
      OTHER, RELATION, OTHER, OTHER, ALPHA, SYMBOL, SYMBOL, OTHER,  //  !"#$%&´
      LPAREN, RPAREN, SYMBOL, SYMBOL, COMMA, SYMBOL, DOT, SYMBOL,   // ()*+,-./
      NUMERIC, NUMERIC, NUMERIC, NUMERIC, NUMERIC,                  // 01234
      NUMERIC, NUMERIC, NUMERIC, NUMERIC, NUMERIC,                  // 56789
      COLON, OTHER, RELATION, RELATION, RELATION, QUERY, OTHER,     // :;<=>?@
      ALPHA, ALPHA, ALPHA, ALPHA, ALPHA, ALPHA, ALPHA, ALPHA,       // ABCDEFGH
      ALPHA, ALPHA, ALPHA, ALPHA, ALPHA, ALPHA, ALPHA, ALPHA,       // IJKLMNOP
      ALPHA, ALPHA, ALPHA, ALPHA, ALPHA, ALPHA, ALPHA, ALPHA,       // QRSTUVWX
      ALPHA, ALPHA, LSQUARE, OTHER, RSQUARE, SYMBOL, ALPHA, OTHER,  // YZ[\]^_'
      ALPHA, ALPHA, ALPHA, ALPHA, ALPHA, ALPHA, ALPHA, ALPHA,       // abcdefgh
      ALPHA, ALPHA, ALPHA, ALPHA, ALPHA, ALPHA, ALPHA, ALPHA,       // ijklmnop
      ALPHA, ALPHA, ALPHA, ALPHA, ALPHA, ALPHA, ALPHA, ALPHA,       // qrstuvwx
      ALPHA, ALPHA, LBRACE, SYMBOL, RBRACE, SYMBOL];                // yz{|}~

  static final BINARY_OPERATORS = [
      '+', '-', '*', '/', '%', '^', '|', '&', '||', '&&',
      '<<', '>>', '+=', '-=', '*=', '/=', '^=', '|=', '&=', '<<=', '>>=',
      '=', '!=', '==', '!==', '===', '<', '<=', '>=', '>'].toSet();
  static final UNARY_OPERATORS = ['++', '--', '+', '-', '~', '!'].toSet();

  // For sanity we only allow \\, \', \" and \n in string literals.
  static final STRING_LITERAL_PATTERN =
      new RegExp('^[\'"](?:[^\\\\]|\\\\[\\\\n\'"])*[\'"]\$');

  static int category(int code) {
    if (code >= CATEGORIES.length) return OTHER;
    return CATEGORIES[code];
  }

  void getSymbol() {
    while (position < src.length &&
           src.codeUnitAt(position) == charCodes.$SPACE) {
      position++;
    }
    if (position == src.length) {
      lastCategory = NONE;
      lastToken = null;
      lastPosition = position;
      return;
    }
    int code = src.codeUnitAt(position);
    lastPosition = position;
    if (code == charCodes.$SQ || code == charCodes.$DQ) {
      int currentCode;
      do {
        position++;
        if (position >= src.length) {
          throw new MiniJsParserError(this, "Unterminated string");
        }
        currentCode = src.codeUnitAt(position);
        if (currentCode == charCodes.$BACKSLASH) {
          if (++position >= src.length) {
            throw new MiniJsParserError(this, "Unterminated string");
          }
        }
      } while (currentCode != code);
      lastCategory = STRING;
      position++;
      lastToken = src.substring(lastPosition, position);
      if (!STRING_LITERAL_PATTERN.hasMatch(lastToken)) {
        throw new MiniJsParserError(
            this,
            "Only escapes allowed in string literals are \\, \', \" and \n");
      }
    } else {
      int cat = category(src.codeUnitAt(position));
      int newCat;
      do {
        position++;
        if (position == src.length) break;
        newCat = category(src.codeUnitAt(position));
      } while (!singleCharCategory(cat) &&
               (cat == newCat ||
                (cat == ALPHA && newCat == NUMERIC) ||    // eg. level42.
                (cat == NUMERIC && newCat == DOT) ||      // eg. 3.1415
                (cat == SYMBOL && newCat == RELATION)));  // eg. +=.
      lastCategory = cat;
      lastToken = src.substring(lastPosition, position);
      if (cat == NUMERIC) {
        double.parse(lastToken, (_) {
          throw new MiniJsParserError(this, "Unparseable number");
        });
      } else if (cat == SYMBOL || cat == RELATION) {
        if (!BINARY_OPERATORS.contains(lastToken) &&
            !UNARY_OPERATORS.contains(lastToken)) {
          throw new MiniJsParserError(this, "Unknown operator");
        }
      }
    }
  }

  void expectCategory(int cat) {
    if (cat != lastCategory) {
      throw new MiniJsParserError(this, "Expected ${categoryToString(cat)}");
    }
    getSymbol();
  }

  bool acceptCategory(int cat) {
    if (cat == lastCategory) {
      getSymbol();
      return true;
    }
    return false;
  }

  bool acceptString(String string) {
    if (lastToken == string) {
      getSymbol();
      return true;
    }
    return false;
  }

  Expression parsePrimary() {
    String last = lastToken;
    if (acceptCategory(ALPHA)) {
      if (last == "true") {
        return new LiteralBool(true);
      } else if (last == "false") {
        return new LiteralBool(false);
      } else if (last == "null") {
        return new LiteralNull();
      } else {
        return new VariableUse(last);
      }
    } else if (acceptCategory(LPAREN)) {
      Expression expression = parseExpression();
      expectCategory(RPAREN);
      return expression;
    } else if (acceptCategory(STRING)) {
      return new LiteralString(last);
    } else if (acceptCategory(NUMERIC)) {
      return new LiteralNumber(last);
    } else if (acceptCategory(LBRACE)) {
      expectCategory(RBRACE);
      return new ObjectInitializer([]);
    } else if (acceptCategory(LSQUARE)) {
      var values = <ArrayElement>[];
      if (!acceptCategory(RSQUARE)) {
        do {
          values.add(new ArrayElement(values.length, parseExpression()));
        } while (acceptCategory(COMMA));
        expectCategory(RSQUARE);
      }
      return new ArrayInitializer(values.length, values);
    } else {
      throw new MiniJsParserError(this, "Expected primary expression");
    }
  }

  Expression parseMember() {
    Expression receiver = parsePrimary();
    while (true) {
      if (acceptCategory(DOT)) {
        String identifier = lastToken;
        expectCategory(ALPHA);
        receiver = new PropertyAccess.field(receiver, identifier);
      } else if (acceptCategory(LSQUARE)) {
        Expression inBraces = parseExpression();
        expectCategory(RSQUARE);
        receiver = new PropertyAccess(receiver, inBraces);
      } else {
        return receiver;
      }
    }
  }

  Expression parseCall() {
    bool constructor = acceptString("new");
    Expression receiver = parseMember();
    if (acceptCategory(LPAREN)) {
      final arguments = <Expression>[];
      if (!acceptCategory(RPAREN)) {
        while (true) {
          Expression argument = parseExpression();
          arguments.add(argument);
          if (acceptCategory(RPAREN)) break;
          expectCategory(COMMA);
        }
      }
      return constructor ?
             new New(receiver, arguments) :
             new Call(receiver, arguments);
    } else {
      if (constructor) {
        // JS allows new without (), but we don't.
        throw new MiniJsParserError(this, "Parentheses are required for new");
      }
      return receiver;
    }
  }

  Expression parsePostfix() {
    Expression expression = parseCall();
    String operator = lastToken;
    if (lastCategory == SYMBOL && (acceptString("++") || acceptString("--"))) {
      return new Postfix(operator, expression);
    }
    return expression;
  }

  Expression parseUnary() {
    String operator = lastToken;
    if (lastCategory == ALPHA) {
     if (acceptString("typeof") || acceptString("void") ||
         acceptString("delete")) {
        return new Prefix(operator, parsePostfix());
     }
    } else if (lastCategory == SYMBOL) {
      if (acceptString("~") || acceptString("-") || acceptString("++") ||
          acceptString("--") || acceptString("+")) {
        return new Prefix(operator, parsePostfix());
      }
    } else if (acceptString("!")) {
      return new Prefix(operator, parsePostfix());
    }
    return parsePostfix();
  }

  Expression parseBinary() {
    // Since we don't handle precedence we don't allow two different symbols
    // without parentheses.
    Expression lhs = parseUnary();
    String firstSymbol = lastToken;
    while (true) {
      String symbol = lastToken;
      if (!acceptCategory(SYMBOL)) return lhs;
      if (!BINARY_OPERATORS.contains(symbol)) {
        throw new MiniJsParserError(this, "Unknown binary operator");
      }
      if (symbol != firstSymbol) {
        throw new MiniJsParserError(
            this, "Mixed $firstSymbol and $symbol operators without ()");
      }
      Expression rhs = parseUnary();
      if (symbol.endsWith("=")) {
        // +=, -=, *= etc.
        lhs = new Assignment.compound(lhs,
                                      symbol.substring(0, symbol.length - 1),
                                      rhs);
      } else {
        lhs = new Binary(symbol, lhs, rhs);
      }
    }
  }

  Expression parseRelation() {
    Expression lhs = parseBinary();
    String relation = lastToken;
    // The lexer returns "=" as a relational operator because it looks a bit
    // like ==, <=, etc.  But we don't want to handle it here (that would give
    // it the wrong prescedence), so we just return if we see it.
    if (relation == "=" || !acceptCategory(RELATION)) return lhs;
    Expression rhs = parseBinary();
    if (relation == "<<=" || relation == ">>=") {
      return new Assignment.compound(lhs,
                                     relation.substring(0, relation.length - 1),
                                     rhs);
    } else {
      // Regular binary operation.
      return new Binary(relation, lhs, rhs);
    }
  }

  Expression parseConditional() {
    Expression lhs = parseRelation();
    if (!acceptCategory(QUERY)) return lhs;
    Expression ifTrue = parseAssignment();
    expectCategory(COLON);
    Expression ifFalse = parseAssignment();
    return new Conditional(lhs, ifTrue, ifFalse);
  }


  Expression parseAssignment() {
    Expression lhs = parseConditional();
    if (acceptString("=")) {
      return new Assignment(lhs, parseAssignment());
    }
    return lhs;
  }

  Expression parseExpression() => parseAssignment();

  Expression parseVarDeclarationOrExpression() {
    if (acceptString("var")) {
      var initialization = [];
      do {
        String variable = lastToken;
        expectCategory(ALPHA);
        Expression initializer = null;
        if (acceptString("=")) {
          initializer = parseExpression();
        }
        var declaration = new VariableDeclaration(variable);
        initialization.add(
            new VariableInitialization(declaration, initializer));
      } while (acceptCategory(COMMA));
      return new VariableDeclarationList(initialization);
    } else {
      return parseExpression();
    }
  }

  Expression expression() {
    Expression expression = parseVarDeclarationOrExpression();
    if (lastCategory != NONE || position != src.length) {
      throw new MiniJsParserError(
          this, "Unparsed junk: ${categoryToString(lastCategory)}");
    }
    return expression;
  }
}