Implement flow control with breaks

pkg/kernel/lib/interpreter/interpreter.dart

Index: pkg/kernel/lib/interpreter/interpreter.dart
diff --git a/pkg/kernel/lib/interpreter/interpreter.dart b/pkg/kernel/lib/interpreter/interpreter.dart
index a64fe581f12f7be928f4f34308138c6a63545c48..879ca3567176f3cee04eb1c76c09ccf07f1d3575 100644
--- a/pkg/kernel/lib/interpreter/interpreter.dart
+++ b/pkg/kernel/lib/interpreter/interpreter.dart
@@ -17,7 +17,6 @@ class NotImplemented {
 class Interpreter {
   Program program;
   StatementExecuter visitor = new StatementExecuter();
-  Environment env = new Environment.empty();
 
   Interpreter(this.program);
 
@@ -25,19 +24,11 @@ class Interpreter {
     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;
@@ -82,6 +73,7 @@ class Environment {
   }
 }
 
+/// Evaluate expressions.
 class Evaluator extends ExpressionVisitor1<Value> {
   Value eval(Expression expr, Environment env) => expr.accept1(this, env);
 
@@ -91,7 +83,7 @@ class Evaluator extends ExpressionVisitor1<Value> {
   }
 
   Value visitInvalidExpression1(InvalidExpression node, env) {
-    throw new InvalidExpressionError(node);
+    throw 'Invalid expression at ${node.location.toString()}';
   }
 
   Value visitVariableGet(VariableGet node, env) {
@@ -223,57 +215,163 @@ class Evaluator extends ExpressionVisitor1<Value> {
   }
 }
 
+/// 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) {}
+  Continuation visitEmptyStatement(EmptyStatement node, state) {
+    return state.continuation;
+  }
 
-  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 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));
   }
 
-  visitVariableDeclaration(VariableDeclaration node, env) {
+  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>{};