Clarify Mutability invariants, refactor some tests
RELNOTES: None
PiperOrigin-RevId: 170343759
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/Environment.java b/src/main/java/com/google/devtools/build/lib/syntax/Environment.java
index 2c0a2a6..8abf942 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/Environment.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/Environment.java
@@ -40,24 +40,25 @@
import javax.annotation.Nullable;
/**
- * An Environment is the main entry point to evaluating code in the BUILD language or Skylark. It
- * embodies all the state that is required to evaluate such code, except for the current instruction
- * pointer, which is an {@link ASTNode} whose {@link Statement#exec exec} or {@link Expression#eval
- * eval} method is invoked with this Environment, in a straightforward direct-style AST-walking
- * interpreter. {@link Continuation}-s are explicitly represented, but only partly, with another
- * part being implicit in a series of try-catch statements, to maintain the direct style. One
- * notable trick is how a {@link UserDefinedFunction} implements returning values as the function
- * catching a {@link ReturnStatement.ReturnException} thrown by a {@link ReturnStatement} in the
- * body.
+ * An {@code Environment} is the main entry point to evaluating Skylark code. It embodies all the
+ * state that is required to evaluate such code, except for the current instruction pointer, which
+ * is an {@link ASTNode} that is evaluated (for expressions) or executed (for statements) with
+ * respect to this {@code Environment}.
*
- * <p>Every Environment has a {@link Mutability} field, and must be used within a function that
- * creates and closes this {@link Mutability} with the try-with-resource pattern. This {@link
- * Mutability} is also used when initializing mutable objects within that Environment; when closed
- * at the end of the computation freezes the Environment and all those objects that then become
- * forever immutable. The pattern enforces the discipline that there should be no dangling mutable
- * Environment, or concurrency between interacting Environment-s. It is also an error to try to
- * mutate an Environment and its objects from another Environment, before the {@link Mutability} is
- * closed.
+ * <p>{@link Continuation}-s are explicitly represented, but only partly, with another part being
+ * implicit in a series of try-catch statements, to maintain the direct style. One notable trick is
+ * how a {@link UserDefinedFunction} implements returning values as the function catching a {@link
+ * ReturnStatement.ReturnException} thrown by a {@link ReturnStatement} in the body.
+ *
+ * <p>Every {@code Environment} has a {@link Mutability} field, and must be used within a function
+ * that creates and closes this {@link Mutability} with the try-with-resource pattern. This {@link
+ * Mutability} is also used when initializing mutable objects within that {@code Environment}. When
+ * the {@code Mutability} is closed at the end of the computation, it freezes the {@code
+ * Environment} along with all of those objects. This pattern enforces the discipline that there
+ * should be no dangling mutable {@code Environment}, or concurrency between interacting {@code
+ * Environment}s. It is a Skylark-level error to attempt to mutate a frozen {@code Environment} or
+ * its objects, but it is a Java-level error to attempt to mutate an unfrozen {@code Environment} or
+ * its objects from within a different {@code Environment}.
*
* <p>One creates an Environment using the {@link #builder} function, then populates it with {@link
* #setup}, {@link #setupDynamic} and sometimes {@link #setupOverride}, before to evaluate code in
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/Mutability.java b/src/main/java/com/google/devtools/build/lib/syntax/Mutability.java
index 15fbe6f..804fd48 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/Mutability.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/Mutability.java
@@ -31,13 +31,19 @@
* {@code Mutability} instance. Once the {@code Environment} is done evaluating, its {@code
* Mutability} is irreversibly closed ("frozen"). At that point, it is no longer possible to change
* either the bindings in that {@code Environment} or the state of its objects. This protects each
- * {@code Environment} from unintentional and unsafe modification. Before freezing, only a single
- * thread may use the contents of the {@code Environment}, but after freezing, any number of threads
- * may access it.
+ * {@code Environment} from unintentional and unsafe modification.
*
- * <p>It is illegal for an evaluation in one {@code Environment} to affect another {@code
- * Environment}, even if the second {@code Environment} has not yet been frozen. In practice, the
- * only unfrozen values that any {@code Environment} should be able to access are its own.
+ * <p>{@code Mutability}s enforce isolation between {@code Environment}s; it is illegal for an
+ * evaluation in one {@code Environment} to affect the bindings or values of another. In particular,
+ * the {@code Environment} for any Skylark module is frozen before its symbols can be imported for
+ * use by another module. Each individual {@code Environment}'s evaluation is single-threaded, so
+ * this isolation also translates to thread safety. Any number of threads may simultaneously access
+ * frozen data.
+ *
+ * <p>Although the mutability pointer of a {@code Freezable} contains some debugging information
+ * about its context, this should not affect the {@code Freezable}'s semantics. From a behavioral
+ * point of view, the only thing that matters is whether the {@code Mutability} is frozen, not what
+ * particular {@code Mutability} object is pointed to.
*
* <p>A {@code Mutability} also tracks which {@code Freezable} objects in its {@code Environment}
* are temporarily locked from mutation. This is used to prevent modification of iterables during
@@ -45,7 +51,7 @@
* iterable). Locking an object does not prohibit mutating its deeply contained values, such as in
* the case of a list of lists.
*
- * We follow two disciplines to ensure safety. First, all mutation methods of a {@code Freezable}
+ * <p>We follow two disciplines to ensure safety. First, all mutation methods of a {@code Freezable}
* must take in a {@code Mutability} as a parameter, and confirm that
* <ol>
* <li>the {@code Freezable} is not yet frozen,
@@ -67,9 +73,23 @@
* block, relying on the try-with-resource construct to ensure that everything gets frozen before
* the result is used. The only code that should create a {@code Mutability} without using
* try-with-resource is test code that is not part of the Bazel jar.
+ *
+ * We keep some (unchecked) invariants regarding where {@code Mutability} objects may appear in a
+ * compound value.
+ * <ol>
+ * <li>There is always at most one unfrozen {@code Mutability}, corresponding to the current
+ * {@code Environment}'s evaluation.
+ * <li>Whenever a new mutable Skylark value is created, its {@code Mutability} is either the
+ * current {@code Environment}'s {@code Mutability}, or else it is the special static
+ * instance, {@link #IMMUTABLE}, which represents that a value is at least shallowly
+ * immutable.
+ * </ol>
+ * It follows that an unfrozen value can never appear as the child of a frozen value unless the
+ * frozen value's {@code Mutability} is {@code IMMUTABLE}. This can be used to prune traversals that
+ * check whether a value is deeply immutable.
*/
-// TODO(bazel-team): This safe usage pattern can be enforced through the use of a higher-order
-// function.
+// TODO(bazel-team): The safe try-with-resources usage pattern can be enforced through the use of a
+// higher-order function.
public final class Mutability implements AutoCloseable, Serializable {
/**
@@ -280,6 +300,24 @@
}
}
- /** A singular instance for permanently immutable things. */
+ /**
+ * An instance indicating that a value is shallowly immutable. Its children may or may not be
+ * mutable.
+ *
+ * <p>This instance is treated specially with regard to the {@code Mutability} invariant. Usually
+ * an immutable value cannot directly or indirectly contain a mutable one. But an immutable value
+ * with this {@code Mutability} may.
+ *
+ * <p>In practice, this instance is used as the {@code Mutability} for tuples. It may also be used
+ * for certain lists and dictionaries that are immutable from creation -- though in general we
+ * prefer to use tuples rather than always-frozen lists.
+ */
+ // TODO(bazel-team): We might be able to remove this instance, and instead have tuples and other
+ // always-immutable things store the same Mutability as other values in that environment. Then we
+ // can simplify the Mutability invariant, and implement deep-immutability checking in constant
+ // time.
+ //
+ // This would also affect structs (SkylarkInfo). Maybe they would implement an interface similar
+ // to SkylarkMutable, or the relevant methods could be worked into SkylarkValue.
public static final Mutability IMMUTABLE = create("IMMUTABLE").freeze();
}
diff --git a/src/test/java/com/google/devtools/build/lib/syntax/EnvironmentTest.java b/src/test/java/com/google/devtools/build/lib/syntax/EnvironmentTest.java
index a61894e..8bf49f8 100644
--- a/src/test/java/com/google/devtools/build/lib/syntax/EnvironmentTest.java
+++ b/src/test/java/com/google/devtools/build/lib/syntax/EnvironmentTest.java
@@ -18,9 +18,7 @@
import static org.junit.Assert.fail;
import com.google.common.collect.Sets;
-import com.google.devtools.build.lib.events.Location;
import com.google.devtools.build.lib.syntax.util.EvaluationTestCase;
-import com.google.devtools.build.lib.vfs.PathFragment;
import org.junit.Test;
import org.junit.runner.RunWith;
import org.junit.runners.JUnit4;
@@ -230,60 +228,6 @@
}
@Test
- public void testLocked() throws Exception {
- final Mutability mutability = Mutability.create("testLocked");
- class DummyFreezable implements Mutability.Freezable {
- @Override
- public Mutability mutability() {
- return mutability;
- }
- }
- DummyFreezable dummy = new DummyFreezable();
- Location locA = Location.fromPathFragment(PathFragment.create("/a"));
- Location locB = Location.fromPathFragment(PathFragment.create("/b"));
- Environment env = Environment.builder(mutability).build();
-
- // Acquire two locks, release two locks, check along the way.
- assertThat(mutability.isLocked(dummy)).isFalse();
- mutability.lock(dummy, locA);
- assertThat(mutability.isLocked(dummy)).isTrue();
- mutability.lock(dummy, locB);
- assertThat(mutability.isLocked(dummy)).isTrue();
- assertThat(mutability.getLockLocations(dummy)).containsExactly(locA, locB);
- mutability.unlock(dummy, locA);
- assertThat(mutability.isLocked(dummy)).isTrue();
- try {
- Mutability.checkMutable(dummy, env.mutability());
- fail("Able to mutate locked object");
- } catch (Mutability.MutabilityException e) {
- assertThat(e).hasMessage("trying to mutate a locked object (is it currently being iterated "
- + "over by a for loop or comprehension?)\n"
- + "Object locked at the following location(s): /b:1");
- }
- try {
- mutability.unlock(dummy, locA);
- fail("Able to unlock object with wrong location");
- } catch (IllegalArgumentException e) {
- assertThat(e).hasMessage("trying to unlock an object for a location at which "
- + "it was not locked (/a:1)");
- }
- mutability.unlock(dummy, locB);
- assertThat(mutability.isLocked(dummy)).isFalse();
- Mutability.checkMutable(dummy, env.mutability());
-
- // Acquire, then freeze.
- mutability.lock(dummy, locA);
- mutability.freeze();
- assertThat(mutability.isLocked(dummy)).isFalse();
- try {
- Mutability.checkMutable(dummy, env.mutability());
- fail("Able to mutate locked object");
- } catch (Mutability.MutabilityException e) {
- assertThat(e).hasMessage("trying to mutate a frozen object");
- }
- }
-
- @Test
public void testReadOnly() throws Exception {
Environment env = newSkylarkEnvironment()
.setup("special_var", 42)
diff --git a/src/test/java/com/google/devtools/build/lib/syntax/EvalUtilsTest.java b/src/test/java/com/google/devtools/build/lib/syntax/EvalUtilsTest.java
index 3782c32..6430d0e 100644
--- a/src/test/java/com/google/devtools/build/lib/syntax/EvalUtilsTest.java
+++ b/src/test/java/com/google/devtools/build/lib/syntax/EvalUtilsTest.java
@@ -38,11 +38,11 @@
public class EvalUtilsTest extends EvaluationTestCase {
private static MutableList<Object> makeList(Environment env) {
- return MutableList.<Object>of(env, 1, 2, 3);
+ return MutableList.of(env, 1, 2, 3);
}
private static SkylarkDict<Object, Object> makeDict(Environment env) {
- return SkylarkDict.<Object, Object>of(env, 1, 1, 2, 2);
+ return SkylarkDict.of(env, 1, 1, 2, 2);
}
@Test
diff --git a/src/test/java/com/google/devtools/build/lib/syntax/MutabilityTest.java b/src/test/java/com/google/devtools/build/lib/syntax/MutabilityTest.java
new file mode 100644
index 0000000..63438cd
--- /dev/null
+++ b/src/test/java/com/google/devtools/build/lib/syntax/MutabilityTest.java
@@ -0,0 +1,249 @@
+// Copyright 2017 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;
+
+import static com.google.common.truth.Truth.assertThat;
+import static com.google.devtools.build.lib.testutil.MoreAsserts.expectThrows;
+
+import com.google.devtools.build.lib.events.Location;
+import com.google.devtools.build.lib.syntax.Mutability.Freezable;
+import com.google.devtools.build.lib.syntax.Mutability.MutabilityException;
+import com.google.devtools.build.lib.vfs.PathFragment;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.JUnit4;
+
+/** Tests for {@link Mutability}. */
+@RunWith(JUnit4.class)
+public final class MutabilityTest {
+
+ /** A trivial Freezable that can do nothing but freeze. */
+ private static class DummyFreezable implements Mutability.Freezable {
+ private final Mutability mutability;
+
+ public DummyFreezable(Mutability mutability) {
+ this.mutability = mutability;
+ }
+
+ @Override
+ public Mutability mutability() {
+ return mutability;
+ }
+ }
+
+ private void assertCheckMutableFailsBecauseFrozen(Freezable value, Mutability mutability) {
+ MutabilityException expected =
+ expectThrows(
+ MutabilityException.class,
+ () -> Mutability.checkMutable(value, mutability));
+ assertThat(expected).hasMessageThat().contains("trying to mutate a frozen object");
+ }
+
+ @Test
+ public void freeze() throws Exception {
+ Mutability mutability = Mutability.create("test");
+ DummyFreezable dummy = new DummyFreezable(mutability);
+
+ Mutability.checkMutable(dummy, mutability);
+ mutability.freeze();
+ assertCheckMutableFailsBecauseFrozen(dummy, mutability);
+ }
+
+ @Test
+ public void tryWithResources() throws Exception {
+ Mutability escapedMutability;
+ DummyFreezable dummy;
+ try (Mutability mutability = Mutability.create("test")) {
+ dummy = new DummyFreezable(mutability);
+ Mutability.checkMutable(dummy, mutability);
+ escapedMutability = mutability;
+ }
+ assertCheckMutableFailsBecauseFrozen(dummy, escapedMutability);
+ }
+
+ @Test
+ public void queryLockedState_InitiallyUnlocked() throws Exception {
+ Mutability mutability = Mutability.create("test");
+ DummyFreezable dummy = new DummyFreezable(mutability);
+
+ assertThat(mutability.isLocked(dummy)).isFalse();
+ Mutability.checkMutable(dummy, mutability);
+ }
+
+ @Test
+ public void queryLockedState_OneLocation() throws Exception {
+ Mutability mutability = Mutability.create("test");
+ DummyFreezable dummy = new DummyFreezable(mutability);
+ Location locA = Location.fromPathFragment(PathFragment.create("/a"));
+
+ mutability.lock(dummy, locA);
+ assertThat(mutability.isLocked(dummy)).isTrue();
+ assertThat(mutability.getLockLocations(dummy)).containsExactly(locA);
+ }
+
+ @Test
+ public void queryLockedState_ManyLocations() throws Exception {
+ Mutability mutability = Mutability.create("test");
+ DummyFreezable dummy = new DummyFreezable(mutability);
+ Location locA = Location.fromPathFragment(PathFragment.create("/a"));
+ Location locB = Location.fromPathFragment(PathFragment.create("/b"));
+ Location locC = Location.fromPathFragment(PathFragment.create("/c"));
+ Location locD = Location.fromPathFragment(PathFragment.create("/d"));
+
+ mutability.lock(dummy, locA);
+ mutability.lock(dummy, locB);
+ mutability.lock(dummy, locC);
+ mutability.lock(dummy, locD);
+ assertThat(mutability.isLocked(dummy)).isTrue();
+ assertThat(mutability.getLockLocations(dummy))
+ .containsExactly(locA, locB, locC, locD).inOrder();
+ }
+
+ @Test
+ public void queryLockedState_LockTwiceUnlockOnce() throws Exception {
+ Mutability mutability = Mutability.create("test");
+ DummyFreezable dummy = new DummyFreezable(mutability);
+ Location locA = Location.fromPathFragment(PathFragment.create("/a"));
+ Location locB = Location.fromPathFragment(PathFragment.create("/b"));
+
+ mutability.lock(dummy, locA);
+ mutability.lock(dummy, locB);
+ mutability.unlock(dummy, locA);
+ assertThat(mutability.isLocked(dummy)).isTrue();
+ assertThat(mutability.getLockLocations(dummy)).containsExactly(locB);
+ }
+
+ @Test
+ public void queryLockedState_LockTwiceUnlockTwice() throws Exception {
+ Mutability mutability = Mutability.create("test");
+ DummyFreezable dummy = new DummyFreezable(mutability);
+ Location locA = Location.fromPathFragment(PathFragment.create("/a"));
+ Location locB = Location.fromPathFragment(PathFragment.create("/b"));
+
+ mutability.lock(dummy, locA);
+ mutability.lock(dummy, locB);
+ mutability.unlock(dummy, locA);
+ mutability.unlock(dummy, locB);
+ assertThat(mutability.isLocked(dummy)).isFalse();
+ Mutability.checkMutable(dummy, mutability);
+ }
+
+ @Test
+ public void cannotMutateLocked() throws Exception {
+ Mutability mutability = Mutability.create("test");
+ DummyFreezable dummy = new DummyFreezable(mutability);
+ Location locA = Location.fromPathFragment(PathFragment.create("/a"));
+ Location locB = Location.fromPathFragment(PathFragment.create("/b"));
+
+ mutability.lock(dummy, locA);
+ mutability.lock(dummy, locB);
+ MutabilityException expected =
+ expectThrows(
+ MutabilityException.class,
+ () -> Mutability.checkMutable(dummy, mutability));
+ assertThat(expected).hasMessageThat().contains(
+ "trying to mutate a locked object (is it currently being iterated over by a for loop or "
+ + "comprehension?)\nObject locked at the following location(s): /a:1, /b:1");
+ }
+
+ @Test
+ public void unlockLocationMismatch() throws Exception {
+ Mutability mutability = Mutability.create("test");
+ DummyFreezable dummy = new DummyFreezable(mutability);
+ Location locA = Location.fromPathFragment(PathFragment.create("/a"));
+ Location locB = Location.fromPathFragment(PathFragment.create("/b"));
+
+ mutability.lock(dummy, locA);
+ IllegalArgumentException expected =
+ expectThrows(
+ IllegalArgumentException.class,
+ () -> mutability.unlock(dummy, locB));
+ assertThat(expected).hasMessageThat().contains(
+ "trying to unlock an object for a location at which it was not locked (/b:1)");
+ }
+
+ @Test
+ public void lockAndThenFreeze() throws Exception {
+ Mutability mutability = Mutability.create("test");
+ DummyFreezable dummy = new DummyFreezable(mutability);
+ Location loc = Location.fromPathFragment(PathFragment.create("/a"));
+
+ mutability.lock(dummy, loc);
+ mutability.freeze();
+ assertThat(mutability.isLocked(dummy)).isFalse();
+ // Should fail with frozen error, not locked error.
+ assertCheckMutableFailsBecauseFrozen(dummy, mutability);
+ }
+
+ @Test
+ public void wrongContext_CheckMutable() throws Exception {
+ Mutability mutability1 = Mutability.create("test1");
+ Mutability mutability2 = Mutability.create("test2");
+ DummyFreezable dummy = new DummyFreezable(mutability1);
+
+ IllegalArgumentException expected =
+ expectThrows(
+ IllegalArgumentException.class,
+ () -> Mutability.checkMutable(dummy, mutability2));
+ assertThat(expected).hasMessageThat().contains(
+ "trying to mutate an object from a different context");
+ }
+
+ @Test
+ public void wrongContext_Lock() throws Exception {
+ Mutability mutability1 = Mutability.create("test1");
+ Mutability mutability2 = Mutability.create("test2");
+ DummyFreezable dummy = new DummyFreezable(mutability1);
+ Location loc = Location.fromPathFragment(PathFragment.create("/a"));
+
+ IllegalArgumentException expected =
+ expectThrows(
+ IllegalArgumentException.class,
+ () -> mutability2.lock(dummy, loc));
+ assertThat(expected).hasMessageThat().contains(
+ "trying to lock an object from a different context");
+ }
+
+ @Test
+ public void wrongContext_Unlock() throws Exception {
+ Mutability mutability1 = Mutability.create("test1");
+ Mutability mutability2 = Mutability.create("test2");
+ DummyFreezable dummy = new DummyFreezable(mutability1);
+ Location loc = Location.fromPathFragment(PathFragment.create("/a"));
+
+ IllegalArgumentException expected =
+ expectThrows(
+ IllegalArgumentException.class,
+ () -> mutability2.unlock(dummy, loc));
+ assertThat(expected).hasMessageThat().contains(
+ "trying to unlock an object from a different context");
+ }
+
+ @Test
+ public void wrongContext_IsLocked() throws Exception {
+ Mutability mutability1 = Mutability.create("test1");
+ Mutability mutability2 = Mutability.create("test2");
+ DummyFreezable dummy = new DummyFreezable(mutability1);
+ Location loc = Location.fromPathFragment(PathFragment.create("/a"));
+
+ mutability1.lock(dummy, loc);
+ IllegalArgumentException expected =
+ expectThrows(
+ IllegalArgumentException.class,
+ () -> mutability2.isLocked(dummy));
+ assertThat(expected).hasMessageThat().contains(
+ "trying to check the lock of an object from a different context");
+ }
+}
