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.empty());
+    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 env;
+  final Continuation continuation;
+  Label label;
+
+  State(this.env, this.label, this.continuation);
+  State.fromEnvironment(Environment env, State s)

[Dmitry Stefantsov, 2017/04/03 14:17:20]

It's probably nitpicking, but 'fromEnvironment' looks more like
'withEnvironment' for me, as in the phrase "copy this state with this
environment". Same for 'fromContinuation' below. Please feel free to ignore this
comment :)

[zhivkag, 2017/04/03 14:32:30]

Done.

+      : this(env, s.label, s.continuation);
+
+  State.fromContinuation(Continuation cont, State s)
+      : this(s.env, s.label, cont);
+
+  State.empty()
+      : this(new Environment.empty(), new Label.empty(),
+            const Continuation.empty());
+
+  void addLabel(Statement s) {
+    label = new Label(s, continuation, label);
+  }
+
+  Label lookupLabel(LabeledStatement s) {
+    return label.lookupLabel(s);
+  }
+}
+
+/// Represent the continuation for execution of statement.
+class Continuation {
+  final Statement statement;
+  final State state;
+
+  Continuation(this.statement, this.state);
+  const Continuation.empty()
+      : statement = null,
+        state = null;
+}
+
+/// Represents a labeled statement, the corresponding continuation and the
+/// enclosing labeled statement.

[Dmitry Stefantsov, 2017/04/03 14:17:20]

Maybe "labeled statement" ==> "label"?

[zhivkag, 2017/04/03 14:32:30]

Done.

+class Label {
+  final LabeledStatement statement;
+  final Continuation continuation;
+  final Label label;

[Dmitry Stefantsov, 2017/04/03 14:17:20]

Maybe "label" ==> "enclosingLabel"?

[zhivkag, 2017/04/03 14:32:30]

Done.

+
+  Label(this.statement, this.continuation, this.label);
+  Label.empty()
+      : statement = null,
+        continuation = new Continuation.empty(),
+        label = null;
+
+  Label lookupLabel(LabeledStatement s) {
+    if (identical(s, statement)) return this;
+    return label.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 (!identical(continuation, const Continuation.empty())) {
+      continuation = exec(continuation.statement, continuation.state);
+    }
+  }
 
-  defaultStatement(Statement node, env) {
+  Continuation exec(Statement statement, cont) => statement.accept1(this, cont);

[Dmitry Stefantsov, 2017/04/03 14:17:20]

From the code below it looks like "cont" should be replaced with "state" here.

[zhivkag, 2017/04/03 14:32:31]

Indeed, I have missed to rename this (and some others) from the previous patches
- thanks!

+  Value eval(Expression expression, env) => evaluator.eval(expression, env);
+
+  Continuation defaultStatement(Statement node, cont) {
     throw notImplemented(
         m: "Execution is not implemented for statement:\n$node ");
   }
 
-  visitInvalidStatement(InvalidStatement node, env) {
+  Continuation visitInvalidStatement(InvalidStatement node, cont) {
     throw "Invalid statement at ${node.location}";
   }
 
-  visitExpressionStatement(ExpressionStatement node, env) {
-    return eval(node.expression, env);
+  Continuation visitExpressionStatement(ExpressionStatement node, state) {
+    eval(node.expression, state.env);
+    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) {
+    // Block statement introduces a new environment.
+    Environment blockEnv = new Environment(state.env);
+    State blockState = new State.fromEnvironment(blockEnv, state);
+    Continuation cont;
+    for (Statement s in node.statements.reversed) {
+      cont = new Continuation(s, blockState);
+      blockState = new State.fromContinuation(cont, blockState);
     }
+    return cont != null ? cont : state.continuation;
   }
 
-  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.env).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) {
+    state.addLabel(node);
+    return new Continuation(node.body, state);
+  }
+
+  Continuation visitBreakStatement(BreakStatement node, state) {
+    return state.lookupLabel(node.target).continuation;
+  }
+
+  Continuation visitWhileStatement(WhileStatement node, state) {
+    Value cond = eval(node.condition, state.env).toBoolean();
+    if (identical(Value.trueInstance, cond)) {
+      // Add continuation for the While statement to the linked list.
+      Continuation c = new Continuation(node, state);
+      // Continuation for the body of the loop.
+      return new Continuation(node.body, new State.fromContinuation(c, state));
+    }
+    return state.continuation;
+  }
+
+  Continuation visitDoStatement(DoStatement node, state) {
+    WhileStatement whileStatement =
+        new WhileStatement(node.condition, node.body);
+    Continuation c = new Continuation(whileStatement, state);
+    return new Continuation(node.body, new State.fromContinuation(c, state));
+  }
+
+  Continuation visitVariableDeclaration(VariableDeclaration node, state) {
     Value value = node.initializer != null
-        ? eval(node.initializer, env)
+        ? eval(node.initializer, state.env)
         : Value.nullInstance;
-    env.expand(node, value);
+    state.env.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');
 }