Implement flow control with breaks

pkg/kernel/lib/interpreter/interpreter.dart

 // Copyright (c) 2017, 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 kernel.interpreter;
 
 import '../ast.dart';
 import '../ast.dart' as ast show Class;
 
 class NotImplemented {
   String message;
 
   NotImplemented(this.message);
 
   String toString() => message;
 }
 
 class Interpreter {
   Program program;
   StatementExecuter visitor = new StatementExecuter();
-  Environment env = new Environment.empty();
 
   Interpreter(this.program);
 
   void run() {
     assert(program.libraries.isEmpty);
     Procedure mainMethod = program.mainMethod;
     Statement statementBlock = mainMethod.function.body;
-    visitor.exec(statementBlock, env);
+    Continuation cont = new Continuation(statementBlock, new State.initial());
+    visitor.trampolinedExecution(cont);
   }
 }
 
-class InvalidExpressionError {
-  InvalidExpression expression;
-
-  InvalidExpressionError(this.expression);
-
-  String toString() =>
-      'Invalid expression at ${expression.location.toString()}';
-}
-
 class Binding {
   final VariableDeclaration variable;
   Value value;
 
   Binding(this.variable, this.value);
 }
 
 class Environment {
   final List<Binding> bindings = <Binding>[];
   final Environment parent;
@@ skipping 24 matching lines @@
     assert(contains(variable));
     lookupBinding(variable).value = value;
   }
 
   void expand(VariableDeclaration variable, Value value) {
     assert(!contains(variable));
     bindings.add(new Binding(variable, value));
   }
 }
 
+/// Evaluate expressions.
 class Evaluator extends ExpressionVisitor1<Value> {
   Value eval(Expression expr, Environment env) => expr.accept1(this, env);
 
   Value defaultExpression(Expression node, env) {
     throw new NotImplemented('Evaluation for expressions of type '
         '${node.runtimeType} is not implemented.');
   }
 
   Value visitInvalidExpression1(InvalidExpression node, env) {
-    throw new InvalidExpressionError(node);
+    throw 'Invalid expression at ${node.location.toString()}';
   }
 
   Value visitVariableGet(VariableGet node, env) {
     return env.lookup(node.variable);
   }
 
   Value visitVariableSet(VariableSet node, env) {
     return env.assign(node.variable, eval(node.value, env));
   }
 
@@ skipping 111 matching lines @@
   Value visitNullLiteral(NullLiteral node, env) => Value.nullInstance;
 
   Value visitLet(Let node, env) {
     var value = eval(node.variable.initializer, env);
     var letEnv = new Environment(env);
     letEnv.expand(node.variable, value);
     return eval(node.body, letEnv);
   }
 }
 
+/// Represents a state which consists of current environment, continuation to be
+/// applied and the current label.
+class State {
+  final Environment environment;
+  final Label labels;
+  final Continuation continuation;
+
+  State(this.environment, this.labels, this.continuation);
+  State.initial() : this(new Environment.empty(), null, null);
+
+  State withEnvironment(Environment env) {
+    return new State(env, labels, continuation);
+  }
+
+  State withBreak(Statement stmt) {
+    return new State(
+        environment, new Label(stmt, continuation, labels), continuation);
+  }
+
+  State withContinuation(Continuation cont) {
+    return new State(environment, labels, cont);
+  }
+
+  Label lookupLabel(LabeledStatement s) {
+    assert(labels != null);
+    return labels.lookupLabel(s);
+  }
+}
+
+/// Represent the continuation for execution of statement.
+class Continuation {
+  final Statement statement;
+  final State state;
+
+  Continuation(this.statement, this.state);
+}
+
+/// Represents a labeled statement, the corresponding continuation and the
+/// enclosing label.
+class Label {
+  final LabeledStatement statement;
+  final Continuation continuation;
+  final Label enclosingLabel;
+
+  Label(this.statement, this.continuation, this.enclosingLabel);
+
+  Label lookupLabel(LabeledStatement s) {
+    if (identical(s, statement)) return this;
+    assert(enclosingLabel != null);
+    return enclosingLabel.lookupLabel(s);
+  }
+}
+
 /// Executes statements.
-class StatementExecuter extends StatementVisitor1 {
+///
+/// Execution of a statement completes in one of the following ways:
+/// - it completes normally, in which case the execution proceeds to applying
+/// the next continuation
+/// - it breaks with a label, in which case the corresponding continuation is
+/// returned and applied
+/// - it returns with or without value, TBD
+/// - it throws, TBD
+class StatementExecuter extends StatementVisitor1<Continuation> {
   Evaluator evaluator = new Evaluator();
 
-  exec(Statement statement, env) => statement.accept1(this, env);
-  eval(Expression expression, env) => evaluator.eval(expression, env);
+  void trampolinedExecution(Continuation continuation) {
+    while (continuation != null) {
+      continuation = exec(continuation.statement, continuation.state);
+    }
+  }
 
-  defaultStatement(Statement node, env) {
+  Continuation exec(Statement statement, state) =>
+      statement.accept1(this, state);
+  Value eval(Expression expression, env) => evaluator.eval(expression, env);
+
+  Continuation defaultStatement(Statement node, state) {
     throw notImplemented(
         m: "Execution is not implemented for statement:\n$node ");
   }
 
-  visitInvalidStatement(InvalidStatement node, env) {
+  Continuation visitInvalidStatement(InvalidStatement node, state) {
     throw "Invalid statement at ${node.location}";
   }
 
-  visitExpressionStatement(ExpressionStatement node, env) {
-    return eval(node.expression, env);
+  Continuation visitExpressionStatement(ExpressionStatement node, state) {
+    eval(node.expression, state.environment);
+    return state.continuation;
   }
 
-  visitBlock(Block node, env) {
-    Environment blockEnv = new Environment(env);
-    for (Statement s in node.statements) {
-      exec(s, blockEnv);
+  Continuation visitBlock(Block node, state) {
+    if (node.statements.isEmpty) {
+      return state.continuation;
     }
+    State blockState =
+        state.withEnvironment(new Environment(state.environment));
+    Continuation cont = state.continuation;
+    for (Statement s in node.statements.reversed) {
+      cont = new Continuation(s, blockState.withContinuation(cont));
+    }
+    return cont;
   }
 
-  visitEmptyStatement(EmptyStatement node, env) {}
-
-  visitIfStatement(IfStatement node, env) {
-    Value condition = eval(node.condition, env).toBoolean();
-    if (identical(Value.trueInstance, condition)) {
-      exec(node.then, env);
-    } else {
-      exec(node.otherwise, env);
-    }
+  Continuation visitEmptyStatement(EmptyStatement node, state) {
+    return state.continuation;
   }
 
-  visitVariableDeclaration(VariableDeclaration node, env) {
+  Continuation visitIfStatement(IfStatement node, state) {
+    Value cond = eval(node.condition, state.environment).toBoolean();
+    if (identical(Value.trueInstance, cond)) {
+      return new Continuation(node.then, state);
+    } else if (node.otherwise != null) {
+      return new Continuation(node.otherwise, state);
+    }
+    return state.continuation;
+  }
+
+  Continuation visitLabeledStatement(LabeledStatement node, state) {
+    return new Continuation(node.body, state.withBreak(node));
+  }
+
+  Continuation visitBreakStatement(BreakStatement node, state) {
+    return state.lookupLabel(node.target).continuation;
+  }
+
+  Continuation visitWhileStatement(WhileStatement node, state) {
+    Value cond = eval(node.condition, state.environment).toBoolean();
+    if (identical(Value.trueInstance, cond)) {
+      // Add continuation for the While statement to the linked list.
+      Continuation cont = new Continuation(node, state);
+      // Continuation for the body of the loop.
+      return new Continuation(node.body, state.withContinuation(cont));
+    }
+    return state.continuation;
+  }
+
+  Continuation visitDoStatement(DoStatement node, state) {
+    WhileStatement whileStatement =
+        new WhileStatement(node.condition, node.body);
+    Continuation cont = new Continuation(whileStatement, state);
+    return new Continuation(node.body, state.withContinuation(cont));
+  }
+
+  Continuation visitVariableDeclaration(VariableDeclaration node, state) {
     Value value = node.initializer != null
-        ? eval(node.initializer, env)
+        ? eval(node.initializer, state.environment)
         : Value.nullInstance;
-    env.expand(node, value);
+    state.environment.expand(node, value);
+    return state.continuation;
   }
 }
 
 typedef Value Getter(Value receiver);
 typedef void Setter(Value receiver, Value value);
 
-// TODO(zhivkag): Change misleading name.
-// This is representation of a class in the interpreter, not a declaration.
 class Class {
   static final Map<Reference, Class> _classes = <Reference, Class>{};
 
   Class superclass;
   List<Field> instanceFields = <Field>[];
   List<Field> staticFields = <Field>[];
   // Implicit getters and setters for instance Fields.
   Map<Name, Getter> getters = <Name, Getter>{};
   Map<Name, Setter> setters = <Name, Setter>{};
   // The initializers of static fields are evaluated the first time the field
@@ skipping 203 matching lines @@
 
 class NullValue extends LiteralValue {
   Object get value => null;
 
   const NullValue();
 }
 
 notImplemented({String m, Object obj}) {
   throw new NotImplemented(m ?? 'Evaluation for $obj is not implemented');
 }