Skylark: implemented 'break' and 'continue'

Fixes #233.
https://github.com/google/bazel/issues/233

--
MOS_MIGRATED_REVID=95632067

5 files changed, 285 insertions, 14 deletions

diff --git a/src/main/java/com/google/devtools/build/lib/syntax/FlowStatement.java b/src/main/java/com/google/devtools/build/lib/syntax/FlowStatement.java
new file mode 100644
index 0000000000..127b366dea
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/syntax/FlowStatement.java
@@ -0,0 +1,86 @@
+// Copyright 2014 Google Inc. All rights reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+package com.google.devtools.build.lib.syntax;
+
+/**
+ * A class for flow statements (e.g. break and continue)
+ */
+public final class FlowStatement extends Statement {
+
+  public static final FlowStatement BREAK = new FlowStatement("break", true);
+  public static final FlowStatement CONTINUE = new FlowStatement("continue", false);
+
+  private final String name;
+  private final FlowException ex;
+
+  /**
+   *
+   * @param name The label of the statement (either break or continue)
+   * @param terminateLoop Determines whether the enclosing loop should be terminated completely
+   *        (break)
+   */
+  protected FlowStatement(String name, boolean terminateLoop) {
+    this.name = name;
+    this.ex = new FlowException(terminateLoop);
+  }
+
+  @Override
+  void exec(Environment env) throws EvalException {
+    throw ex;
+  }
+
+  @Override
+  void validate(ValidationEnvironment env) throws EvalException {
+    if (!env.isInsideLoop()) {
+      throw new EvalException(getLocation(), name + " statement must be inside a for loop");
+    }
+  }
+
+  @Override
+  public String toString() {
+    return name;
+  }
+
+  @Override
+  public void accept(SyntaxTreeVisitor visitor) {
+    visitor.visit(this);
+  }
+
+  /**
+   * An exception that signals changes in the control flow (e.g. break or continue)
+   */
+  class FlowException extends EvalException {
+    private final boolean terminateLoop;
+
+    /**
+     *
+     * @param terminateLoop Determines whether the enclosing loop should be terminated completely
+     *        (break)
+     */
+    public FlowException(boolean terminateLoop) {
+      super(FlowStatement.this.getLocation(), "FlowException with terminateLoop = "
+          + terminateLoop);
+      this.terminateLoop = terminateLoop;
+    }
+
+    /**
+     * Returns whether the enclosing loop should be terminated completely (break)
+     *
+     * @return {@code True} for 'break', {@code false} for 'continue'
+     */
+    public boolean mustTerminateLoop() {
+      return terminateLoop;
+    }
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/ForStatement.java b/src/main/java/com/google/devtools/build/lib/syntax/ForStatement.java
index 054b21f1e6..1660ce1e15 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/ForStatement.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/ForStatement.java
@@ -15,6 +15,7 @@ package com.google.devtools.build.lib.syntax;
 
 import com.google.common.base.Preconditions;
 import com.google.common.collect.ImmutableList;
+import com.google.devtools.build.lib.syntax.FlowStatement.FlowException;
 
 import java.util.List;
 
@@ -63,11 +64,20 @@ public final class ForStatement extends Statement {
     int i = 0;
     for (Object it : ImmutableList.copyOf(col)) {
       variable.assign(env, getLocation(), it);
-      for (Statement stmt : block) {
-        stmt.exec(env);
+
+      try {
+        for (Statement stmt : block) {
+          stmt.exec(env);
+        }
+      } catch (FlowException ex) {
+        if (ex.mustTerminateLoop()) {
+          return;
+        }
       }
+
       i++;
     }
+    
     // TODO(bazel-team): This should not happen if every collection is immutable.
     if (i != EvalUtils.size(col)) {
       throw new EvalException(getLocation(),
@@ -83,14 +93,20 @@ public final class ForStatement extends Statement {
   @Override
   void validate(ValidationEnvironment env) throws EvalException {
     if (env.isTopLevel()) {
-      throw new EvalException(getLocation(),
-          "'For' is not allowed as a top level statement");
+      throw new EvalException(getLocation(), "'For' is not allowed as a top level statement");
     }
-    // TODO(bazel-team): validate variable. Maybe make it temporarily readonly.
-    collection.validate(env);
-    variable.validate(env, getLocation());
-    for (Statement stmt : block) {
-      stmt.validate(env);
+    env.enterLoop();
+
+    try {
+      // TODO(bazel-team): validate variable. Maybe make it temporarily readonly.
+      collection.validate(env);
+      variable.validate(env, getLocation());
+
+      for (Statement stmt : block) {
+        stmt.validate(env);
+      }
+    } finally {
+      env.exitLoop(getLocation());
     }
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/Parser.java b/src/main/java/com/google/devtools/build/lib/syntax/Parser.java
index c2642597a3..71277a0b4c 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/Parser.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/Parser.java
@@ -336,7 +336,7 @@ class Parser {
 
   // Keywords that exist in Python and that we don't parse.
   private static final EnumSet<TokenKind> FORBIDDEN_KEYWORDS =
-      EnumSet.of(TokenKind.AS, TokenKind.ASSERT, TokenKind.BREAK, TokenKind.CONTINUE,
+      EnumSet.of(TokenKind.AS, TokenKind.ASSERT, 
           TokenKind.DEL, TokenKind.EXCEPT, TokenKind.FINALLY, TokenKind.FROM, TokenKind.GLOBAL,
           TokenKind.IMPORT, TokenKind.IS, TokenKind.LAMBDA, TokenKind.NONLOCAL, TokenKind.RAISE,
           TokenKind.TRY, TokenKind.WITH, TokenKind.WHILE, TokenKind.YIELD);
@@ -1154,6 +1154,7 @@ class Parser {
   //     small_stmt ::= assign_stmt
   //                  | expr
   //                  | RETURN expr
+  //                  | flow_stmt
   //     assign_stmt ::= expr ('=' | augassign) expr
   //     augassign ::= ('+=' )
   // Note that these are in Python, but not implemented here (at least for now):
@@ -1171,6 +1172,8 @@ class Parser {
     int start = token.left;
     if (token.kind == TokenKind.RETURN) {
       return parseReturnStatement();
+    } else if (token.kind == TokenKind.BREAK || token.kind == TokenKind.CONTINUE)   {
+      return parseFlowStatement(token.kind);
     }
     Expression expression = parseExpression();
     if (token.kind == TokenKind.EQUALS) {
@@ -1408,6 +1411,12 @@ class Parser {
     }
   }
 
+  // flow_stmt ::= break_stmt | continue_stmt
+  private FlowStatement parseFlowStatement(TokenKind kind) {
+    expect(kind);
+    return (kind == TokenKind.BREAK) ? FlowStatement.BREAK : FlowStatement.CONTINUE;
+  }
+  
   // return_stmt ::= RETURN expr
   private ReturnStatement parseReturnStatement() {
     int start = token.left;
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/ValidationEnvironment.java b/src/main/java/com/google/devtools/build/lib/syntax/ValidationEnvironment.java
index a615d67b47..7aedca2c82 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/ValidationEnvironment.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/ValidationEnvironment.java
@@ -47,6 +47,12 @@ public class ValidationEnvironment {
 
   // Whether this validation environment is not modified therefore clonable or not.
   private boolean clonable;
+  
+  /**
+   * Tracks the number of nested for loops that contain the statement that is currently being
+   * validated
+   */
+  private int loopCount = 0;
 
   public ValidationEnvironment(Set<String> builtinVariables) {
     parent = null;
@@ -174,4 +180,33 @@ public class ValidationEnvironment {
       statement.validate(this);
     }
   }
+
+  /**
+   * Returns whether the current statement is inside a for loop (either in this environment or one
+   * of its parents)
+   *
+   * @return True if the current statement is inside a for loop
+   */
+  public boolean isInsideLoop() {
+    return (loopCount > 0);
+  }
+  
+  /**
+   * Signals that the block of a for loop was entered
+   */
+  public void enterLoop()   {
+    ++loopCount;
+  }
+  
+  /**
+   * Signals that the block of a for loop was left
+   *
+   * @param location The current location
+   * @throws EvalException If there was no corresponding call to
+   *         {@code ValidationEnvironment#enterLoop}
+   */
+  public void exitLoop(Location location) throws EvalException {
+    Preconditions.checkState(loopCount > 0);
+    --loopCount;
+  }
 }
diff --git a/src/test/java/com/google/devtools/build/lib/syntax/SkylarkEvaluationTest.java b/src/test/java/com/google/devtools/build/lib/syntax/SkylarkEvaluationTest.java
index 43e5ac84df..3dcbb9d4d2 100644
--- a/src/test/java/com/google/devtools/build/lib/syntax/SkylarkEvaluationTest.java
+++ b/src/test/java/com/google/devtools/build/lib/syntax/SkylarkEvaluationTest.java
@@ -248,7 +248,7 @@ public class SkylarkEvaluationTest extends EvaluationTest {
         "  for i in ['hello', ' ', 'world']:",
         "    s = s + i",
         "  return s",
-        "s = foo()\n");
+        "s = foo()");
     assertEquals("hello world", lookup("s"));
   }
 
@@ -260,7 +260,7 @@ public class SkylarkEvaluationTest extends EvaluationTest {
         "  for i in 'abc':",
         "    s = s + [i]",
         "  return s",
-        "s = foo()\n");
+        "s = foo()");
     assertThat((Iterable<Object>) lookup("s")).containsExactly("a", "b", "c").inOrder();
   }
 
@@ -273,7 +273,7 @@ public class SkylarkEvaluationTest extends EvaluationTest {
         "    s = s + i",
         "    d = ['d', 'e', 'f']",  // check that we use the old list
         "  return s",
-        "s = foo()\n");
+        "s = foo()");
     assertEquals("abc", lookup("s"));
   }
 
@@ -296,7 +296,7 @@ public class SkylarkEvaluationTest extends EvaluationTest {
     checkEvalError("type 'int' is not iterable",
         "def func():",
         "  for i in mock.value_of('1'): a = i",
-        "func()\n");
+        "func()");
 
   }
 
@@ -334,6 +334,131 @@ public class SkylarkEvaluationTest extends EvaluationTest {
   }
 
   @Test
+  public void testForLoopBreak() throws Exception {
+    simpleFlowTest("break", 1);
+  }
+  
+  @Test
+  public void testForLoopContinue() throws Exception {
+    simpleFlowTest("continue", 10);
+  }
+  
+  @SuppressWarnings("unchecked")
+  private void simpleFlowTest(String statement, int expected) throws Exception {
+    eval("def foo():",
+        "  s = 0",
+        "  hit = 0", 
+        "  for i in range(0, 10):", 
+        "    s = s + 1", 
+        "    " + statement + "", 
+        "    hit = 1", 
+        "  return [s, hit]", 
+        "x = foo()");
+    assertThat((Iterable<Object>) lookup("x")).containsExactly(expected, 0).inOrder();
+  }
+  
+  @Test 
+  public void testForLoopBreakFromDeeperBlock() throws Exception {
+    flowFromDeeperBlock("break", 1);
+    flowFromNestedBlocks("break", 29);
+  }
+  
+  @Test 
+  public void testForLoopContinueFromDeeperBlock() throws Exception {
+    flowFromDeeperBlock("continue", 5);
+    flowFromNestedBlocks("continue", 39);
+  }
+  
+  private void flowFromDeeperBlock(String statement, int expected) throws Exception {
+    eval("def foo():",
+        "   s = 0", 
+        "   for i in range(0, 10):", 
+        "       if i % 2 != 0:", 
+        "           " + statement + "",
+        "       s = s + 1", 
+        "   return s", 
+        "x = foo()");
+    assertThat(lookup("x")).isEqualTo(expected);
+  }
+  
+  private void flowFromNestedBlocks(String statement, int expected) throws Exception {
+    eval("def foo2():",
+        "   s = 0", 
+        "   for i in range(1, 41):", 
+        "       if i % 2 == 0:", 
+        "           if i % 3 == 0:",
+        "               if i % 5 == 0:", 
+        "                   " + statement + "",
+        "       s = s + 1", 
+        "   return s", 
+        "y = foo2()");
+    assertThat(lookup("y")).isEqualTo(expected);
+  }
+
+  @Test
+  public void testNestedForLoopsMultipleBreaks() throws Exception {
+    nestedLoopsTest("break", 2, 6, 6);
+  }
+
+  @Test
+  public void testNestedForLoopsMultipleContinues() throws Exception {
+    nestedLoopsTest("continue", 4, 20, 20);
+  }
+
+  @SuppressWarnings("unchecked")
+  private void nestedLoopsTest(String statement, Integer outerExpected, int firstExpected,
+      int secondExpected) throws Exception {
+    eval("def foo():",
+        "   outer = 0",
+        "   first = 0",
+        "   second = 0",
+        "   for i in range(0, 5):",
+        "       for j in range(0, 5):",
+        "           if j == 2:", 
+        "               " + statement + "",
+        "           first = first + 1",
+        "       for k in range(0, 5):",
+        "           if k == 2:", 
+        "               " + statement + "",
+        "           second = second + 1",
+        "       if i == 2:",
+        "           " + statement + "",
+        "       outer = outer + 1",
+        "   return [outer, first, second]",
+        "x = foo()");
+    assertThat((Iterable<Object>) lookup("x"))
+        .containsExactly(outerExpected, firstExpected, secondExpected).inOrder();
+  }
+  
+  @Test
+  public void testForLoopBreakError() throws Exception {
+    flowStatementInsideFunction("break");
+    flowStatementAfterLoop("break");
+  }
+
+  @Test
+  public void testForLoopContinueError() throws Exception {
+    flowStatementInsideFunction("continue");
+    flowStatementAfterLoop("continue");
+  }
+
+  private void flowStatementInsideFunction(String statement) throws Exception {
+    checkEvalErrorContains(statement + " statement must be inside a for loop", 
+        "def foo():",
+        "  " + statement + "", 
+        "x = foo()");
+  }
+  
+  private void flowStatementAfterLoop(String statement) throws Exception  {
+    checkEvalErrorContains(statement + " statement must be inside a for loop", 
+        "def foo2():",
+        "   for i in range(0, 3):",
+        "      pass",
+        "   " + statement + "", 
+        "y = foo2()");
+  }
+  
+  @Test
   public void testNoneAssignment() throws Exception {
     eval("def foo(x=None):",
         "  x = 1",