Compile for loops with break/continue to byte code

--
MOS_MIGRATED_REVID=107389651

5 files changed, 226 insertions, 17 deletions

diff --git a/src/main/java/com/google/devtools/build/lib/syntax/ExpressionStatement.java b/src/main/java/com/google/devtools/build/lib/syntax/ExpressionStatement.java
index 3f15d03d51..5c9a03aded 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/ExpressionStatement.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/ExpressionStatement.java
@@ -14,6 +14,13 @@
 
 package com.google.devtools.build.lib.syntax;
 
+import com.google.common.base.Optional;
+import com.google.devtools.build.lib.syntax.compiler.DebugInfo;
+import com.google.devtools.build.lib.syntax.compiler.LoopLabels;
+import com.google.devtools.build.lib.syntax.compiler.VariableScope;
+
+import net.bytebuddy.implementation.bytecode.ByteCodeAppender;
+
 /**
  * Syntax node for a function call statement. Used for build rules.
  */
@@ -48,4 +55,11 @@ public final class ExpressionStatement extends Statement {
   void validate(ValidationEnvironment env) throws EvalException {
     expr.validate(env);
   }
+
+  @Override
+  ByteCodeAppender compile(
+      VariableScope scope, Optional<LoopLabels> loopLabels, DebugInfo debugInfo)
+          throws EvalException {
+    return expr.compile(scope, debugInfo);
+  }
 }
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
index 29a62bb27c..6a3eb6877d 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/FlowStatement.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/FlowStatement.java
@@ -13,6 +13,15 @@
 // limitations under the License.
 package com.google.devtools.build.lib.syntax;
 
+import com.google.common.base.Optional;
+import com.google.common.base.Preconditions;
+import com.google.devtools.build.lib.syntax.compiler.DebugInfo;
+import com.google.devtools.build.lib.syntax.compiler.Jump;
+import com.google.devtools.build.lib.syntax.compiler.LoopLabels;
+import com.google.devtools.build.lib.syntax.compiler.VariableScope;
+
+import net.bytebuddy.implementation.bytecode.ByteCodeAppender;
+
 /**
  * A class for flow statements (e.g. break and continue)
  */
@@ -26,16 +35,14 @@ public final class FlowStatement extends Statement {
     private Kind(String name) {
       this.name = name;
     }
-  };
+  }
 
   private final Kind kind;
   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)
+   * @param kind The label of the statement (either break or continue)
    */
   public FlowStatement(Kind kind) {
     this.kind = kind;
@@ -68,17 +75,19 @@ public final class FlowStatement extends Statement {
     visitor.visit(this);
   }
 
+  @Override
+  ByteCodeAppender compile(
+      VariableScope scope, Optional<LoopLabels> loopLabels, DebugInfo debugInfo) {
+    Preconditions.checkArgument(loopLabels.isPresent(), "break/continue not within loop");
+    return new ByteCodeAppender.Simple(Jump.to(loopLabels.get().labelFor(kind)));
+  }
+
   /**
    * An exception that signals changes in the control flow (e.g. break or continue)
    */
   class FlowException extends EvalException {
     private final Kind kind;
 
-    /**
-     *
-     * @param terminateLoop Determines whether the enclosing loop should be terminated completely
-     *        (break)
-     */
     public FlowException(Kind kind) {
       super(FlowStatement.this.getLocation(), "FlowException with kind = " + kind.name);
       this.kind = kind;
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 a75ff70091..41415ac0ca 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
@@ -13,10 +13,31 @@
 // limitations under the License.
 package com.google.devtools.build.lib.syntax;
 
+import static com.google.devtools.build.lib.syntax.compiler.ByteCodeUtils.append;
+
+import com.google.common.base.Optional;
 import com.google.common.base.Preconditions;
 import com.google.common.collect.ImmutableList;
 import com.google.devtools.build.lib.syntax.FlowStatement.FlowException;
-
+import com.google.devtools.build.lib.syntax.compiler.ByteCodeMethodCalls;
+import com.google.devtools.build.lib.syntax.compiler.ByteCodeUtils;
+import com.google.devtools.build.lib.syntax.compiler.DebugInfo;
+import com.google.devtools.build.lib.syntax.compiler.DebugInfo.AstAccessors;
+import com.google.devtools.build.lib.syntax.compiler.IntegerVariableIncrease;
+import com.google.devtools.build.lib.syntax.compiler.Jump;
+import com.google.devtools.build.lib.syntax.compiler.Jump.PrimitiveComparison;
+import com.google.devtools.build.lib.syntax.compiler.LabelAdder;
+import com.google.devtools.build.lib.syntax.compiler.LoopLabels;
+import com.google.devtools.build.lib.syntax.compiler.Variable.InternalVariable;
+import com.google.devtools.build.lib.syntax.compiler.VariableScope;
+
+import net.bytebuddy.description.type.TypeDescription;
+import net.bytebuddy.implementation.bytecode.ByteCodeAppender;
+import net.bytebuddy.implementation.bytecode.Duplication;
+import net.bytebuddy.implementation.bytecode.constant.IntegerConstant;
+
+import java.util.ArrayList;
+import java.util.Iterator;
 import java.util.List;
 
 /**
@@ -80,11 +101,24 @@ public final class ForStatement extends Statement {
 
       i++;
     }
-    
-    // TODO(bazel-team): This should not happen if every collection is immutable.
-    if (i != EvalUtils.size(col)) {
-      throw new EvalException(getLocation(),
-          String.format("Cannot modify '%s' during during iteration.", collection.toString()));
+
+    checkConcurrentModification(col, i, this);
+  }
+
+  /**
+   * Check for concurrent modification by comparing the size of the original, possibly modified,
+   * collection against the size counted during evaluation.
+   *
+   * <p>public for reflection access by compiler and invocation by compiled code
+   */
+  public static void checkConcurrentModification(
+      Iterable<?> collection, int countedSize, ASTNode forStatement) throws EvalException {
+    if (countedSize != EvalUtils.size(collection)) {
+      throw new EvalException(
+          forStatement.getLocation(),
+          String.format(
+              "Cannot modify '%s' during iteration.",
+              ((ForStatement) forStatement).collection.toString()));
     }
   }
 
@@ -112,4 +146,69 @@ public final class ForStatement extends Statement {
       env.exitLoop(getLocation());
     }
   }
+
+  @Override
+  ByteCodeAppender compile(
+      VariableScope scope, Optional<LoopLabels> outerLoopLabels, DebugInfo debugInfo)
+          throws EvalException {
+    AstAccessors debugAccessors = debugInfo.add(this);
+    List<ByteCodeAppender> code = new ArrayList<>();
+    InternalVariable originalIterable =
+        scope.freshVariable(new TypeDescription.ForLoadedType(Iterable.class));
+    InternalVariable iterator =
+        scope.freshVariable(new TypeDescription.ForLoadedType(Iterator.class));
+    // compute the collection and get it on the stack and transform it to the right type
+    code.add(collection.compile(scope, debugInfo));
+    append(code, debugAccessors.loadLocation, EvalUtils.toIterable, Duplication.SINGLE);
+    // save it for later concurrent modification check
+    code.add(originalIterable.store());
+    append(code,
+        ByteCodeMethodCalls.BCImmutableList.copyOf,
+        ByteCodeMethodCalls.BCImmutableList.iterator);
+    code.add(iterator.store());
+    // for counting the size during the loop
+    InternalVariable sizeCounterVariable =
+        scope.freshVariable(new TypeDescription.ForLoadedType(int.class));
+    LabelAdder loopHeader = new LabelAdder();
+    LabelAdder loopBody = new LabelAdder();
+    LabelAdder breakLoop = new LabelAdder();
+    // for passing on the labels for continue/break statements
+    Optional<LoopLabels> loopLabels = LoopLabels.of(loopHeader.getLabel(), breakLoop.getLabel());
+    append(
+        code,
+        // initialize loop counter
+        IntegerConstant.ZERO);
+    code.add(sizeCounterVariable.store());
+    append(code, Jump.to(loopHeader), loopBody, iterator.load());
+    append(code, ByteCodeMethodCalls.BCIterator.next);
+    // store current element into l-value
+    code.add(variable.compileAssignment(this, debugAccessors, scope));
+    // compile code for the body
+    for (Statement statement : block) {
+      append(code, new IntegerVariableIncrease(sizeCounterVariable, 1));
+      code.add(statement.compile(scope, loopLabels, debugInfo));
+    }
+    // compile code for the loop header
+    append(
+        code,
+        loopHeader,
+        iterator.load(),
+        ByteCodeMethodCalls.BCIterator.hasNext,
+        // falls through to end of loop if hasNext() was false, otherwise jumps back
+        Jump.ifIntOperandToZero(PrimitiveComparison.NOT_EQUAL).to(loopBody));
+    append(
+        code,
+        breakLoop,
+        // load arguments for checkConcurrentModification and call it
+        originalIterable.load(),
+        sizeCounterVariable.load(),
+        debugAccessors.loadAstNode,
+        ByteCodeUtils.invoke(
+            ForStatement.class,
+            "checkConcurrentModification",
+            Iterable.class,
+            int.class,
+            ASTNode.class));
+    return ByteCodeUtils.compoundAppender(code);
+  }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/compiler/ByteCodeMethodCalls.java b/src/main/java/com/google/devtools/build/lib/syntax/compiler/ByteCodeMethodCalls.java
index 5027610e29..55e9cc1bf6 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/compiler/ByteCodeMethodCalls.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/compiler/ByteCodeMethodCalls.java
@@ -18,6 +18,8 @@ import com.google.common.collect.ImmutableMap;
 
 import net.bytebuddy.implementation.bytecode.StackManipulation;
 
+import java.util.Iterator;
+import java.util.List;
 import java.util.Map;
 
 /**
@@ -31,6 +33,14 @@ import java.util.Map;
 public class ByteCodeMethodCalls {
 
   /**
+   * Byte code invocations for {@link Object}.
+   */
+  public static class BCObject {
+    public static final StackManipulation equals =
+        ByteCodeUtils.invoke(Object.class, "equals", Object.class);
+  }
+
+  /**
    * Byte code invocations for {@link Boolean}.
    */
   public static class BCBoolean {
@@ -67,15 +77,24 @@ public class ByteCodeMethodCalls {
     public static final StackManipulation builder =
         ByteCodeUtils.invoke(ImmutableList.class, "builder");
 
+    public static final StackManipulation copyOf =
+        ByteCodeUtils.invoke(ImmutableList.class, "copyOf", Iterable.class);
+
+    public static final StackManipulation iterator =
+        ByteCodeUtils.invoke(ImmutableList.class, "iterator");
+
     /**
-     * Byte code invocations for {@link com.google.common.collect.ImmutableList.Builder}.
-     */
+    * Byte code invocations for {@link ImmutableList.Builder}.
+    */
     public static class Builder {
       public static final StackManipulation build =
           ByteCodeUtils.invoke(ImmutableList.Builder.class, "build");
 
       public static final StackManipulation add =
           ByteCodeUtils.invoke(ImmutableList.Builder.class, "add", Object.class);
+
+      public static final StackManipulation addAll =
+          ByteCodeUtils.invoke(ImmutableList.Builder.class, "addAll", Iterable.class);
     }
   }
 
@@ -86,4 +105,22 @@ public class ByteCodeMethodCalls {
     public static final StackManipulation valueOf =
         ByteCodeUtils.invoke(Integer.class, "valueOf", int.class);
   }
+
+  /**
+   * Byte code invocations for {@link Iterator}.
+   */
+  public static class BCIterator {
+
+    public static final StackManipulation hasNext = ByteCodeUtils.invoke(Iterator.class, "hasNext");
+
+    public static final StackManipulation next = ByteCodeUtils.invoke(Iterator.class, "next");
+  }
+
+  /**
+   * Byte code invocations for {@link List}.
+   */
+  public static class BCList {
+    public static final StackManipulation add =
+        ByteCodeUtils.invoke(List.class, "add", Object.class);
+  }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/compiler/IntegerVariableIncrease.java b/src/main/java/com/google/devtools/build/lib/syntax/compiler/IntegerVariableIncrease.java
new file mode 100644
index 0000000000..bcdad916b5
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/syntax/compiler/IntegerVariableIncrease.java
@@ -0,0 +1,50 @@
+// Copyright 2015 The Bazel Authors. 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.compiler;
+
+import net.bytebuddy.implementation.Implementation.Context;
+import net.bytebuddy.implementation.bytecode.StackManipulation;
+
+import org.objectweb.asm.MethodVisitor;
+
+/**
+ * A {@link StackManipulation} that increases a given integer variable of the method by a given
+ * amount.
+ */
+public final class IntegerVariableIncrease implements StackManipulation {
+
+  private final Variable variable;
+  private final int increment;
+
+  public IntegerVariableIncrease(Variable variable, int increment) {
+    this.variable = variable;
+    this.increment = increment;
+  }
+
+  @Override
+  public Size apply(MethodVisitor methodVisitor, Context implementationContext) {
+    methodVisitor.visitIincInsn(variable.index, increment);
+    return new Size(0, 0);
+  }
+
+  @Override
+  public boolean isValid() {
+    return true;
+  }
+
+  @Override
+  public String toString() {
+    return "IntInc(" + variable.index + ", " + increment + ")";
+  }
+}