diff options
5 files changed, 317 insertions, 85 deletions
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 2c0a2a6f4e..8abf9428fd 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 java.util.TreeSet; 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 15fbe6f7ce..804fd48e57 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 @@ import java.util.List; * {@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 @@ import java.util.List; * 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 @@ import java.util.List; * 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 @@ public final class Mutability implements AutoCloseable, Serializable { } } - /** 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 a61894ecef..8bf49f8351 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 com.google.common.truth.Truth.assertThat; 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 @@ public class EnvironmentTest extends EvaluationTestCase { } @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 3782c3250d..6430d0e037 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 @@ import org.junit.runners.JUnit4; 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 0000000000..63438cd5ef --- /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"); + } +} |