diff --git a/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetVisitor.java b/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetVisitor.java
index a353850..1ecb2b8 100644
--- a/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetVisitor.java
+++ b/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetVisitor.java
@@ -14,9 +14,7 @@
 package com.google.devtools.build.lib.collect.nestedset;
 
 import com.google.common.base.Preconditions;
-import com.google.common.collect.Sets;
 import java.util.Collection;
-import java.util.Set;
 
 /**
  * NestedSetVisitor facilitates a transitive visitation over a NestedSet. The callback may be called
@@ -39,9 +37,9 @@
 
   private final Receiver<E> callback;
 
-  private final AbstractVisitedState visited;
+  private final VisitedState visited;
 
-  public NestedSetVisitor(Receiver<E> callback, AbstractVisitedState visited) {
+  public NestedSetVisitor(Receiver<E> callback, VisitedState visited) {
     this.callback = Preconditions.checkNotNull(callback);
     this.visited = Preconditions.checkNotNull(visited);
   }
@@ -81,10 +79,8 @@
     }
   }
 
-  /** A class that allows us to keep track of the seen nodes and transitive sets. */
-  public interface AbstractVisitedState {
-    /** Removes all visited nodes from the VisitedState. */
-    void clear();
+  /** Allows {@link NestedSetVisitor} to keep track of the seen nodes and transitive sets. */
+  public interface VisitedState {
 
     /**
      * Adds a node to the visited state, returning true if the node was not yet in the visited state
@@ -92,19 +88,4 @@
      */
     boolean add(Object node);
   }
-
-  /** A class that allows us to keep track of the seen nodes and transitive sets. */
-  public static final class VisitedState implements AbstractVisitedState {
-    private final Set<Object> seenNodes = Sets.newConcurrentHashSet();
-
-    @Override
-    public void clear() {
-      seenNodes.clear();
-    }
-
-    @Override
-    public boolean add(Object node) {
-      return seenNodes.add(node);
-    }
-  }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/events/Event.java b/src/main/java/com/google/devtools/build/lib/events/Event.java
index 3768468..ded7ba6 100644
--- a/src/main/java/com/google/devtools/build/lib/events/Event.java
+++ b/src/main/java/com/google/devtools/build/lib/events/Event.java
@@ -73,7 +73,10 @@
 
   @Override
   public boolean storeForReplay() {
-    return kind != EventKind.PROGRESS && kind != EventKind.INFO && kind != EventKind.DEBUG;
+    return kind != EventKind.PROGRESS
+        && kind != EventKind.WARNING
+        && kind != EventKind.INFO
+        && kind != EventKind.DEBUG;
   }
 
   public EventKind getKind() {
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SequencedSkyframeExecutor.java b/src/main/java/com/google/devtools/build/lib/skyframe/SequencedSkyframeExecutor.java
index b7e2aa3..ce55d84 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SequencedSkyframeExecutor.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SequencedSkyframeExecutor.java
@@ -37,7 +37,6 @@
 import com.google.devtools.build.lib.bugreport.BugReporter;
 import com.google.devtools.build.lib.buildtool.BuildRequestOptions;
 import com.google.devtools.build.lib.cmdline.PackageIdentifier;
-import com.google.devtools.build.lib.collect.nestedset.NestedSetVisitor;
 import com.google.devtools.build.lib.concurrent.QuiescingExecutors;
 import com.google.devtools.build.lib.concurrent.Uninterruptibles;
 import com.google.devtools.build.lib.events.Event;
@@ -71,6 +70,7 @@
 import com.google.devtools.build.lib.vfs.Root;
 import com.google.devtools.build.lib.vfs.SyscallCache;
 import com.google.devtools.build.skyframe.Differencer;
+import com.google.devtools.build.skyframe.EmittedEventState;
 import com.google.devtools.build.skyframe.EvaluationContext;
 import com.google.devtools.build.skyframe.EventFilter;
 import com.google.devtools.build.skyframe.GraphInconsistencyReceiver;
@@ -182,7 +182,7 @@
   protected InMemoryMemoizingEvaluator createEvaluator(
       ImmutableMap<SkyFunctionName, SkyFunction> skyFunctions,
       SkyframeProgressReceiver progressReceiver,
-      NestedSetVisitor.VisitedState emittedEventState) {
+      EmittedEventState emittedEventState) {
     return new InMemoryMemoizingEvaluator(
         skyFunctions,
         recordingDiffer,
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java
index 5284df2..db43923 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java
@@ -119,7 +119,6 @@
 import com.google.devtools.build.lib.cmdline.TargetParsingException;
 import com.google.devtools.build.lib.collect.nestedset.NestedSet;
 import com.google.devtools.build.lib.collect.nestedset.NestedSetBuilder;
-import com.google.devtools.build.lib.collect.nestedset.NestedSetVisitor;
 import com.google.devtools.build.lib.concurrent.ExecutorUtil;
 import com.google.devtools.build.lib.concurrent.NamedForkJoinPool;
 import com.google.devtools.build.lib.concurrent.QuiescingExecutor;
@@ -212,6 +211,7 @@
 import com.google.devtools.build.lib.vfs.SyscallCache;
 import com.google.devtools.build.skyframe.CyclesReporter;
 import com.google.devtools.build.skyframe.Differencer;
+import com.google.devtools.build.skyframe.EmittedEventState;
 import com.google.devtools.build.skyframe.ErrorInfo;
 import com.google.devtools.build.skyframe.EvaluationContext;
 import com.google.devtools.build.skyframe.EvaluationContext.UnnecessaryTemporaryStateDropper;
@@ -280,8 +280,7 @@
   private static final GoogleLogger logger = GoogleLogger.forEnclosingClass();
 
   protected MemoizingEvaluator memoizingEvaluator;
-  private final NestedSetVisitor.VisitedState emittedEventState =
-      new NestedSetVisitor.VisitedState();
+  private final EmittedEventState emittedEventState = new EmittedEventState();
   protected final PackageFactory pkgFactory;
   private final WorkspaceStatusAction.Factory workspaceStatusActionFactory;
   private final FileSystem fileSystem;
@@ -867,7 +866,7 @@
   protected abstract MemoizingEvaluator createEvaluator(
       ImmutableMap<SkyFunctionName, SkyFunction> skyFunctions,
       SkyframeProgressReceiver progressReceiver,
-      NestedSetVisitor.VisitedState emittedEventState);
+      EmittedEventState emittedEventState);
 
   /**
    * Use the fact that analysis of a target must occur before execution of that target, and in a
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/packages/AbstractPackageLoader.java b/src/main/java/com/google/devtools/build/lib/skyframe/packages/AbstractPackageLoader.java
index 63c06e3..3475414 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/packages/AbstractPackageLoader.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/packages/AbstractPackageLoader.java
@@ -31,7 +31,6 @@
 import com.google.devtools.build.lib.bazel.bzlmod.BzlmodRepoRuleValue;
 import com.google.devtools.build.lib.clock.BlazeClock;
 import com.google.devtools.build.lib.cmdline.PackageIdentifier;
-import com.google.devtools.build.lib.collect.nestedset.NestedSetVisitor;
 import com.google.devtools.build.lib.concurrent.NamedForkJoinPool;
 import com.google.devtools.build.lib.events.Reporter;
 import com.google.devtools.build.lib.events.StoredEventHandler;
@@ -83,6 +82,7 @@
 import com.google.devtools.build.lib.vfs.PathFragment;
 import com.google.devtools.build.lib.vfs.Root;
 import com.google.devtools.build.skyframe.Differencer;
+import com.google.devtools.build.skyframe.EmittedEventState;
 import com.google.devtools.build.skyframe.ErrorInfo;
 import com.google.devtools.build.skyframe.EvaluationContext;
 import com.google.devtools.build.skyframe.EvaluationProgressReceiver;
@@ -416,7 +416,7 @@
         EvaluationProgressReceiver.NULL,
         GraphInconsistencyReceiver.THROWING,
         EventFilter.FULL_STORAGE,
-        new NestedSetVisitor.VisitedState(),
+        new EmittedEventState(),
         /* keepEdges= */ false,
         usePooledSkyKeyInterning);
   }
diff --git a/src/main/java/com/google/devtools/build/skyframe/AbstractIncrementalInMemoryMemoizingEvaluator.java b/src/main/java/com/google/devtools/build/skyframe/AbstractIncrementalInMemoryMemoizingEvaluator.java
index f49cd77..d9fd2de 100644
--- a/src/main/java/com/google/devtools/build/skyframe/AbstractIncrementalInMemoryMemoizingEvaluator.java
+++ b/src/main/java/com/google/devtools/build/skyframe/AbstractIncrementalInMemoryMemoizingEvaluator.java
@@ -17,7 +17,6 @@
 
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.Iterables;
-import com.google.devtools.build.lib.collect.nestedset.NestedSetVisitor;
 import com.google.devtools.build.skyframe.InvalidatingNodeVisitor.DeletingInvalidationState;
 import com.google.devtools.build.skyframe.InvalidatingNodeVisitor.DirtyingInvalidationState;
 import com.google.devtools.build.skyframe.InvalidatingNodeVisitor.InvalidationState;
@@ -56,7 +55,7 @@
   // re-evaluated even if none of their children are changed.
   private final InvalidationState invalidatorState = new DirtyingInvalidationState();
 
-  protected final NestedSetVisitor.VisitedState emittedEventState;
+  final EmittedEventState emittedEventState;
 
   protected IntVersion lastGraphVersion = null;
 
@@ -65,7 +64,7 @@
       Differencer differencer,
       DirtyTrackingProgressReceiver dirtyTrackingProgressReceiver,
       EventFilter eventFilter,
-      NestedSetVisitor.VisitedState emittedEventState,
+      EmittedEventState emittedEventState,
       GraphInconsistencyReceiver graphInconsistencyReceiver,
       boolean keepEdges) {
     this.skyFunctions = checkNotNull(skyFunctions);
diff --git a/src/main/java/com/google/devtools/build/skyframe/AbstractParallelEvaluator.java b/src/main/java/com/google/devtools/build/skyframe/AbstractParallelEvaluator.java
index c579fed..0a63c48 100644
--- a/src/main/java/com/google/devtools/build/skyframe/AbstractParallelEvaluator.java
+++ b/src/main/java/com/google/devtools/build/skyframe/AbstractParallelEvaluator.java
@@ -31,7 +31,6 @@
 import com.google.common.graph.Traverser;
 import com.google.common.util.concurrent.ListenableFuture;
 import com.google.devtools.build.lib.clock.BlazeClock;
-import com.google.devtools.build.lib.collect.nestedset.NestedSetVisitor;
 import com.google.devtools.build.lib.concurrent.ComparableRunnable;
 import com.google.devtools.build.lib.concurrent.QuiescingExecutor;
 import com.google.devtools.build.lib.events.Event;
@@ -116,7 +115,7 @@
       Version minimalVersion,
       ImmutableMap<SkyFunctionName, SkyFunction> skyFunctions,
       ExtendedEventHandler reporter,
-      NestedSetVisitor.VisitedState emittedEventState,
+      EmittedEventState emittedEventState,
       EventFilter storedEventFilter,
       ErrorInfoManager errorInfoManager,
       boolean keepGoing,
diff --git a/src/main/java/com/google/devtools/build/skyframe/EmittedEventState.java b/src/main/java/com/google/devtools/build/skyframe/EmittedEventState.java
new file mode 100644
index 0000000..6089f9a
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/skyframe/EmittedEventState.java
@@ -0,0 +1,53 @@
+// Copyright 2023 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.skyframe;
+
+import static com.google.common.base.Preconditions.checkArgument;
+
+import com.google.common.collect.Sets;
+import com.google.devtools.build.lib.collect.nestedset.NestedSetVisitor;
+import com.google.devtools.build.lib.events.Event;
+import com.google.devtools.build.lib.events.EventKind;
+import java.util.Set;
+
+/**
+ * Keeps track of visited nodes for {@linkplain com.google.devtools.build.lib.events.Reportable
+ * events} stored in a {@link com.google.devtools.build.lib.collect.nestedset.NestedSet}.
+ *
+ * <p>Also tracks warnings for purposes of deduplication, since those are not {@linkplain
+ * Event#storeForReplay stored}.
+ */
+public final class EmittedEventState implements NestedSetVisitor.VisitedState {
+
+  private final Set<Object> seenNodes = Sets.newConcurrentHashSet();
+  private final Set<Event> seenWarnings = Sets.newConcurrentHashSet();
+
+  /** Clears the seen nodes and warnings. */
+  public void clear() {
+    seenNodes.clear();
+    seenWarnings.clear();
+  }
+
+  @Override
+  public boolean add(Object node) {
+    return seenNodes.add(node);
+  }
+
+  /** Returns {@code true} if the given warning was not seen before. */
+  boolean addWarning(Event warning) {
+    checkArgument(warning.getKind() == EventKind.WARNING, "Not a warning: %s", warning);
+    return seenWarnings.add(warning);
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/skyframe/InMemoryMemoizingEvaluator.java b/src/main/java/com/google/devtools/build/skyframe/InMemoryMemoizingEvaluator.java
index 5fda7c8..771d70a 100644
--- a/src/main/java/com/google/devtools/build/skyframe/InMemoryMemoizingEvaluator.java
+++ b/src/main/java/com/google/devtools/build/skyframe/InMemoryMemoizingEvaluator.java
@@ -16,7 +16,6 @@
 import com.google.common.base.Preconditions;
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.Sets;
-import com.google.devtools.build.lib.collect.nestedset.NestedSetVisitor;
 import com.google.devtools.build.lib.concurrent.AbstractQueueVisitor;
 import com.google.devtools.build.lib.events.ExtendedEventHandler;
 import com.google.devtools.build.lib.profiler.AutoProfiler;
@@ -62,7 +61,7 @@
         progressReceiver,
         GraphInconsistencyReceiver.THROWING,
         EventFilter.FULL_STORAGE,
-        new NestedSetVisitor.VisitedState(),
+        new EmittedEventState(),
         /* keepEdges= */ true,
         /* usePooledSkyKeyInterning= */ true);
   }
@@ -73,7 +72,7 @@
       @Nullable EvaluationProgressReceiver progressReceiver,
       GraphInconsistencyReceiver graphInconsistencyReceiver,
       EventFilter eventFilter,
-      NestedSetVisitor.VisitedState emittedEventState,
+      EmittedEventState emittedEventState,
       boolean keepEdges,
       boolean usePooledSkyKeyInterning) {
     super(
diff --git a/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluator.java b/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluator.java
index d93ab77..96f4a9e 100644
--- a/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluator.java
+++ b/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluator.java
@@ -20,7 +20,6 @@
 import com.google.common.collect.Iterables;
 import com.google.common.flogger.GoogleLogger;
 import com.google.devtools.build.lib.collect.nestedset.NestedSet;
-import com.google.devtools.build.lib.collect.nestedset.NestedSetVisitor;
 import com.google.devtools.build.lib.concurrent.QuiescingExecutor;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadCompatible;
 import com.google.devtools.build.lib.events.ExtendedEventHandler;
@@ -62,7 +61,7 @@
       Version minimalVersion,
       ImmutableMap<SkyFunctionName, SkyFunction> skyFunctions,
       ExtendedEventHandler reporter,
-      NestedSetVisitor.VisitedState emittedEventState,
+      EmittedEventState emittedEventState,
       EventFilter storedEventFilter,
       ErrorInfoManager errorInfoManager,
       boolean keepGoing,
diff --git a/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluatorContext.java b/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluatorContext.java
index 5957586..043e715 100644
--- a/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluatorContext.java
+++ b/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluatorContext.java
@@ -41,6 +41,7 @@
   private final Version minimalVersion;
   private final ImmutableMap<SkyFunctionName, SkyFunction> skyFunctions;
   private final ExtendedEventHandler reporter;
+  private final EmittedEventState emittedEventState;
   private final NestedSetVisitor<Reportable> replayingNestedSetEventVisitor;
   private final boolean keepGoing;
   private final DirtyTrackingProgressReceiver progressReceiver;
@@ -74,7 +75,7 @@
       Version minimalVersion,
       ImmutableMap<SkyFunctionName, SkyFunction> skyFunctions,
       ExtendedEventHandler reporter,
-      NestedSetVisitor.VisitedState emittedEventState,
+      EmittedEventState emittedEventState,
       boolean keepGoing,
       DirtyTrackingProgressReceiver progressReceiver,
       EventFilter storedEventFilter,
@@ -89,6 +90,7 @@
     this.skyFunctions = skyFunctions;
     this.reporter = reporter;
     this.graphInconsistencyReceiver = graphInconsistencyReceiver;
+    this.emittedEventState = emittedEventState;
     this.replayingNestedSetEventVisitor =
         new NestedSetVisitor<>(new NestedSetEventReceiver(reporter), emittedEventState);
     this.keepGoing = keepGoing;
@@ -158,6 +160,10 @@
     return graphInconsistencyReceiver;
   }
 
+  EmittedEventState getEmittedEventState() {
+    return emittedEventState;
+  }
+
   NestedSetVisitor<Reportable> getReplayingNestedSetEventVisitor() {
     return replayingNestedSetEventVisitor;
   }
diff --git a/src/main/java/com/google/devtools/build/skyframe/SkyFunctionEnvironment.java b/src/main/java/com/google/devtools/build/skyframe/SkyFunctionEnvironment.java
index 7fc2e78..0bf1ffd 100644
--- a/src/main/java/com/google/devtools/build/skyframe/SkyFunctionEnvironment.java
+++ b/src/main/java/com/google/devtools/build/skyframe/SkyFunctionEnvironment.java
@@ -31,6 +31,7 @@
 import com.google.devtools.build.lib.collect.nestedset.NestedSetBuilder;
 import com.google.devtools.build.lib.collect.nestedset.Order;
 import com.google.devtools.build.lib.events.Event;
+import com.google.devtools.build.lib.events.EventKind;
 import com.google.devtools.build.lib.events.ExtendedEventHandler;
 import com.google.devtools.build.lib.events.Reportable;
 import com.google.devtools.build.skyframe.EvaluationProgressReceiver.EvaluationState;
@@ -757,6 +758,12 @@
 
   @Override
   public void handle(Event event) {
+    if (event.getKind() == EventKind.WARNING) {
+      event = event.withTag(getTagFromKey());
+      if (!evaluatorContext.getEmittedEventState().addWarning(event)) {
+        return; // Duplicate warning.
+      }
+    }
     reportEvent(event);
   }
 
diff --git a/src/test/java/com/google/devtools/build/lib/analysis/util/AnalysisCachingTestBase.java b/src/test/java/com/google/devtools/build/lib/analysis/util/AnalysisCachingTestBase.java
index 6db4202..55c1792 100644
--- a/src/test/java/com/google/devtools/build/lib/analysis/util/AnalysisCachingTestBase.java
+++ b/src/test/java/com/google/devtools/build/lib/analysis/util/AnalysisCachingTestBase.java
@@ -27,15 +27,4 @@
   protected boolean hasTopLevelAnalysisError(ConfiguredTarget configuredTarget) {
     return !getAnalysisResult().getTargetsToBuild().contains(configuredTarget);
   }
-
-  protected void assertEventCached(String target, String expectedWarning) throws Exception {
-    reporter.removeHandler(failFastHandler);
-    // Run with keep_going, so this method can also be used for errors (which otherwise throw an
-    // exception).
-    update(defaultFlags().with(Flag.KEEP_GOING), target);
-    assertContainsEvent(expectedWarning);
-    eventCollector.clear();
-    update(defaultFlags().with(Flag.KEEP_GOING), target);
-    assertContainsEvent(expectedWarning);
-  }
 }
diff --git a/src/test/java/com/google/devtools/build/lib/buildtool/MiscAnalysisTest.java b/src/test/java/com/google/devtools/build/lib/buildtool/MiscAnalysisTest.java
index 5f1b858..93726a1 100644
--- a/src/test/java/com/google/devtools/build/lib/buildtool/MiscAnalysisTest.java
+++ b/src/test/java/com/google/devtools/build/lib/buildtool/MiscAnalysisTest.java
@@ -39,11 +39,8 @@
 @RunWith(JUnit4.class)
 public class MiscAnalysisTest extends BuildIntegrationTestCase {
 
-  // Regression test for bug #1324794, "Replay of errors in --cache_analysis
-  // mode is not working".
-  // Note that the cache_analysis flag has been deleted, as it is now standard app behavior.
   @Test
-  public void testWarningsAreReplayedEvenWithAnalysisCaching() throws Exception {
+  public void testWarningsNotReplayed() throws Exception {
     AnalysisMock.get().pySupport().setup(mockToolsConfig);
     write(
         "y/BUILD",
@@ -56,18 +53,43 @@
     events.clear();
 
     buildTarget("//y");
-    events.assertContainsWarning("target '//y:y' is deprecated");
+    events.assertDoesNotContainEvent("target '//y:y' is deprecated");
   }
 
   @Test
   public void testDeprecatedTargetOnCommandLine() throws Exception {
-    write("raspberry/BUILD",
+    write(
+        "raspberry/BUILD",
         "sh_library(name='raspberry', srcs=['raspberry.sh'], deprecation='rotten')");
     addOptions("--nobuild");
     buildTarget("//raspberry:raspberry");
     events.assertContainsWarning("target '//raspberry:raspberry' is deprecated: rotten");
   }
 
+  @Test
+  public void targetAnalyzedInTwoConfigurations_deprecationWarningDisplayedOncePerBuild()
+      throws Exception {
+    // :a depends on :dep in the target configuration. :b depends on :dep in the exec configuration.
+    write(
+        "foo/BUILD",
+        "genrule(name = 'a', outs = ['a.out'], srcs = [':dep'], cmd = 'touch $@')",
+        "genrule(name = 'b', outs = ['b.out'], tools = [':dep'], cmd = 'touch $@')",
+        "genrule(name = 'dep', outs = ['dep.out'], srcs = ['//deprecated'], cmd = 'touch $@')");
+    write("deprecated/BUILD", "sh_library(name = 'deprecated', deprecation = 'old')");
+    addOptions("--nobuild");
+    buildTarget("//foo:a", "//foo:b");
+    events.assertContainsEventWithFrequency(
+        "'//foo:dep' depends on deprecated target '//deprecated:deprecated'", 1);
+
+    events.clear();
+
+    // Edit to force re-analysis.
+    write("deprecated/BUILD", "sh_library(name = 'deprecated', deprecation = 'very old')");
+    buildTarget("//foo:a", "//foo:b");
+    events.assertContainsEventWithFrequency(
+        "'//foo:dep' depends on deprecated target '//deprecated:deprecated'", 1);
+  }
+
   // Regression test for http://b/12465751: "IllegalStateException in ParallelEvaluator".
   @Test
   public void testShBinaryTwoSrcs() throws Exception {
diff --git a/src/test/java/com/google/devtools/build/lib/collect/nestedset/NestedSetVisitorTest.java b/src/test/java/com/google/devtools/build/lib/collect/nestedset/NestedSetVisitorTest.java
index 5899ef1..6fadfbe 100644
--- a/src/test/java/com/google/devtools/build/lib/collect/nestedset/NestedSetVisitorTest.java
+++ b/src/test/java/com/google/devtools/build/lib/collect/nestedset/NestedSetVisitorTest.java
@@ -15,8 +15,8 @@
 
 import static com.google.common.truth.Truth.assertThat;
 
-import com.google.devtools.build.lib.collect.nestedset.NestedSetVisitor.VisitedState;
 import java.util.ArrayList;
+import java.util.HashSet;
 import java.util.List;
 import org.junit.Test;
 import org.junit.runner.RunWith;
@@ -38,7 +38,7 @@
             .build();
 
     List<Integer> visited = new ArrayList<>();
-    new NestedSetVisitor<Integer>(visited::add, new VisitedState()).visit(set);
+    new NestedSetVisitor<Integer>(visited::add, new HashSet<>()::add).visit(set);
 
     assertThat(visited).isEqualTo(set.toList());
   }
@@ -55,7 +55,7 @@
             .build();
 
     List<Integer> visited = new ArrayList<>();
-    new NestedSetVisitor<Integer>(visited::add, new VisitedState()).visit(set);
+    new NestedSetVisitor<Integer>(visited::add, new HashSet<>()::add).visit(set);
 
     assertThat(visited).isEqualTo(set.toList());
   }
@@ -72,7 +72,7 @@
             .build();
 
     List<Integer> visited = new ArrayList<>();
-    new NestedSetVisitor<Integer>(visited::add, new VisitedState()).visit(set);
+    new NestedSetVisitor<Integer>(visited::add, new HashSet<>()::add).visit(set);
 
     // #toList() for LINK_ORDER reverses the result list.
     assertThat(visited).isEqualTo(set.toList().reverse());
@@ -90,7 +90,7 @@
             .build();
 
     List<Integer> visited = new ArrayList<>();
-    new NestedSetVisitor<Integer>(visited::add, new VisitedState()).visit(set);
+    new NestedSetVisitor<Integer>(visited::add, new HashSet<>()::add).visit(set);
 
     assertThat(visited).isEqualTo(set.toList());
   }
@@ -118,7 +118,7 @@
             .build();
 
     List<Integer> visited = new ArrayList<>();
-    new NestedSetVisitor<Integer>(visited::add, new VisitedState()).visit(set);
+    new NestedSetVisitor<Integer>(visited::add, new HashSet<>()::add).visit(set);
 
     assertThat(visited).isEqualTo(set.toList());
   }
@@ -144,7 +144,7 @@
             .build();
 
     List<Integer> visited = new ArrayList<>();
-    new NestedSetVisitor<Integer>(visited::add, new VisitedState()).visit(set);
+    new NestedSetVisitor<Integer>(visited::add, new HashSet<>()::add).visit(set);
 
     assertThat(visited).isEqualTo(set.toList());
     assertThat(visited).hasSize(9);
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/TimestampBuilderTestCase.java b/src/test/java/com/google/devtools/build/lib/skyframe/TimestampBuilderTestCase.java
index 546a225..6fc9c28 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/TimestampBuilderTestCase.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/TimestampBuilderTestCase.java
@@ -68,7 +68,6 @@
 import com.google.devtools.build.lib.clock.Clock;
 import com.google.devtools.build.lib.collect.nestedset.NestedSet;
 import com.google.devtools.build.lib.collect.nestedset.NestedSetBuilder;
-import com.google.devtools.build.lib.collect.nestedset.NestedSetVisitor;
 import com.google.devtools.build.lib.collect.nestedset.Order;
 import com.google.devtools.build.lib.events.Reporter;
 import com.google.devtools.build.lib.events.StoredEventHandler;
@@ -101,6 +100,7 @@
 import com.google.devtools.build.lib.vfs.Root;
 import com.google.devtools.build.lib.vfs.SyscallCache;
 import com.google.devtools.build.skyframe.CycleInfo;
+import com.google.devtools.build.skyframe.EmittedEventState;
 import com.google.devtools.build.skyframe.ErrorInfo;
 import com.google.devtools.build.skyframe.EvaluationContext;
 import com.google.devtools.build.skyframe.EvaluationProgressReceiver;
@@ -312,7 +312,7 @@
             evaluationProgressReceiver,
             graphInconsistencyReceiver,
             EventFilter.FULL_STORAGE,
-            new NestedSetVisitor.VisitedState(),
+            new EmittedEventState(),
             /* keepEdges= */ true,
             /* usePooledSkyKeyInterning= */ true);
     PrecomputedValue.BUILD_ID.set(differencer, UUID.randomUUID());
diff --git a/src/test/java/com/google/devtools/build/lib/view/cpp/CppTemplateTest.java b/src/test/java/com/google/devtools/build/lib/view/cpp/CppTemplateTest.java
index 79c6740..b5029e3 100644
--- a/src/test/java/com/google/devtools/build/lib/view/cpp/CppTemplateTest.java
+++ b/src/test/java/com/google/devtools/build/lib/view/cpp/CppTemplateTest.java
@@ -18,7 +18,6 @@
 import static com.google.common.truth.Truth.assertWithMessage;
 import static org.junit.Assert.assertThrows;
 
-import com.google.devtools.build.lib.actions.ActionLookupData;
 import com.google.devtools.build.lib.actions.BuildFailedException;
 import com.google.devtools.build.lib.buildtool.util.BuildIntegrationTestCase;
 import com.google.devtools.build.lib.events.EventKind;
@@ -137,17 +136,14 @@
         .getEvaluator()
         .getDoneValues()
         .forEach(
-            (k, v) -> {
-              if (k instanceof ActionLookupData) {
+            (k, v) ->
                 assertWithMessage("Node " + k + " warnings")
                     .that(ValueWithMetadata.getEvents(v).toList())
-                    .isEmpty();
-              }
-            });
+                    .isEmpty());
 
-    // Warning is shown on a no-op incremental build.
+    // Warning is not replayed on a no-op incremental build.
     events.clear();
     buildTarget("//cc:cc");
-    events.assertContainsEvent(EventKind.WARNING, "This is a warning");
+    events.assertDoesNotContainEvent("This is a warning");
   }
 }
diff --git a/src/test/java/com/google/devtools/build/skyframe/EagerInvalidatorTest.java b/src/test/java/com/google/devtools/build/skyframe/EagerInvalidatorTest.java
index 9dccb5d..4d0944a 100644
--- a/src/test/java/com/google/devtools/build/skyframe/EagerInvalidatorTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/EagerInvalidatorTest.java
@@ -24,7 +24,6 @@
 import com.google.common.collect.Sets;
 import com.google.common.eventbus.EventBus;
 import com.google.common.testing.GcFinalization;
-import com.google.devtools.build.lib.collect.nestedset.NestedSetVisitor;
 import com.google.devtools.build.lib.concurrent.AbstractQueueVisitor;
 import com.google.devtools.build.lib.events.Reporter;
 import com.google.devtools.build.lib.testutil.TestUtils;
@@ -141,7 +140,7 @@
             Version.minimal(),
             tester.getSkyFunctionMap(),
             reporter,
-            new NestedSetVisitor.VisitedState(),
+            new EmittedEventState(),
             EventFilter.FULL_STORAGE,
             ErrorInfoManager.UseChildErrorInfoIfNecessary.INSTANCE,
             keepGoing,
diff --git a/src/test/java/com/google/devtools/build/skyframe/GraphTester.java b/src/test/java/com/google/devtools/build/skyframe/GraphTester.java
index d4da456..dfb3850 100644
--- a/src/test/java/com/google/devtools/build/skyframe/GraphTester.java
+++ b/src/test/java/com/google/devtools/build/skyframe/GraphTester.java
@@ -121,6 +121,9 @@
         if (builder.progress != null) {
           env.getListener().handle(Event.progress(builder.progress));
         }
+        if (builder.errorEvent != null) {
+          env.getListener().handle(Event.error(builder.errorEvent));
+        }
         if (builder.postable != null) {
           env.getListener().post(builder.postable);
         }
@@ -262,6 +265,7 @@
 
     private String warning;
     private String progress;
+    private String errorEvent;
     private Postable postable;
 
     private String tag;
@@ -334,6 +338,7 @@
       Preconditions.checkState(!hasError);
       Preconditions.checkState(warning == null);
       Preconditions.checkState(progress == null);
+      Preconditions.checkState(errorEvent == null);
       Preconditions.checkState(tag == null);
       this.builder = builder;
       return this;
@@ -370,6 +375,16 @@
       return this;
     }
 
+    /**
+     * Sets an error message to emit as an {@link Event}. Does not imply that the function throws an
+     * error.
+     */
+    @CanIgnoreReturnValue
+    public TestFunction setErrorEvent(String error) {
+      this.errorEvent = error;
+      return this;
+    }
+
     @CanIgnoreReturnValue
     public TestFunction setTag(String tag) {
       Preconditions.checkState(builder == null);
diff --git a/src/test/java/com/google/devtools/build/skyframe/MemoizingEvaluatorTest.java b/src/test/java/com/google/devtools/build/skyframe/MemoizingEvaluatorTest.java
index fab1d35..63fbe06 100644
--- a/src/test/java/com/google/devtools/build/skyframe/MemoizingEvaluatorTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/MemoizingEvaluatorTest.java
@@ -39,7 +39,6 @@
 import com.google.common.util.concurrent.SettableFuture;
 import com.google.common.util.concurrent.Uninterruptibles;
 import com.google.devtools.build.lib.bugreport.BugReport;
-import com.google.devtools.build.lib.collect.nestedset.NestedSetVisitor;
 import com.google.devtools.build.lib.events.DelegatingEventHandler;
 import com.google.devtools.build.lib.events.Event;
 import com.google.devtools.build.lib.events.EventCollector;
@@ -82,7 +81,7 @@
   protected MemoizingEvaluatorTester tester;
   protected EventCollector eventCollector;
   protected ExtendedEventHandler reporter;
-  protected NestedSetVisitor.VisitedState emittedEventState;
+  protected EmittedEventState emittedEventState;
 
   // Knobs that control the size / duration of larger tests.
   private static final int TEST_NODE_COUNT = 100;
@@ -96,7 +95,7 @@
   }
 
   private void initializeTester(@Nullable TrackingProgressReceiver customProgressReceiver) {
-    emittedEventState = new NestedSetVisitor.VisitedState();
+    emittedEventState = new EmittedEventState();
     tester = new MemoizingEvaluatorTester();
     if (customProgressReceiver != null) {
       tester.setProgressReceiver(customProgressReceiver);
@@ -138,10 +137,6 @@
   protected void afterEvaluation(@Nullable EvaluationResult<?> result, EvaluationContext context)
       throws InterruptedException {}
 
-  protected boolean eventsStored() {
-    return true;
-  }
-
   protected boolean cyclesDetected() {
     return true;
   }
@@ -232,9 +227,6 @@
     tester.invalidate();
     value = (StringValue) tester.evalAndGet("x");
     assertThat(value.getValue()).isEqualTo("y");
-    if (eventsStored()) {
-      assertThatEvents(eventCollector).containsExactly("fizzlepop");
-    }
   }
 
   @Test
@@ -528,20 +520,14 @@
             MemoizingEvaluatorTester.toSkyKeys("top1", "d1", "d2", "top2", "d3"));
   }
 
-  // NOTE: Some of these tests exercising errors/warnings run through a size-2 for loop in order
-  // to ensure that we are properly recording and replyaing these messages on null builds.
   @Test
   public void warningViaMultiplePaths() throws Exception {
     tester.set("d1", new StringValue("d1")).setWarning("warn-d1");
     tester.set("d2", new StringValue("d2")).setWarning("warn-d2");
     tester.getOrCreate("top").setComputedValue(CONCATENATE).addDependency("d1").addDependency("d2");
-    for (int i = 0; i < 2; i++) {
-      initializeReporter();
-      tester.evalAndGet("top");
-      if (i == 0 || eventsStored()) {
-        assertThatEvents(eventCollector).containsExactly("warn-d1", "warn-d2");
-      }
-    }
+    initializeReporter();
+    tester.evalAndGet("top");
+    assertThatEvents(eventCollector).containsExactly("warn-d1", "warn-d2");
   }
 
   @Test
@@ -561,7 +547,7 @@
           .hasSingletonErrorThat(topKey)
           .hasExceptionThat()
           .isInstanceOf(SomeErrorException.class);
-      if (i == 0 || eventsStored()) {
+      if (i == 0) {
         assertThatEvents(eventCollector).containsExactly("warn-dep");
       }
     }
@@ -583,7 +569,7 @@
           .hasSingletonErrorThat(topKey)
           .hasExceptionThat()
           .isInstanceOf(SomeErrorException.class);
-      if (i == 0 || eventsStored()) {
+      if (i == 0) {
         assertThatEvents(eventCollector).containsExactly("warning msg");
       }
     }
@@ -605,7 +591,7 @@
           .hasSingletonErrorThat(topKey)
           .hasExceptionThat()
           .isInstanceOf(SomeErrorException.class);
-      if (i == 0 || eventsStored()) {
+      if (i == 0) {
         assertThatEvents(eventCollector).containsExactly("warning msg");
       }
     }
@@ -616,14 +602,9 @@
     tester.set("t1", new StringValue("t1")).addDependency("dep");
     tester.set("t2", new StringValue("t2")).addDependency("dep");
     tester.set("dep", new StringValue("dep")).setWarning("look both ways before crossing");
-    for (int i = 0; i < 2; i++) {
-      // Make sure we see the warning exactly once.
-      initializeReporter();
-      tester.eval(/*keepGoing=*/ false, "t1", "t2");
-      if (i == 0 || eventsStored()) {
-        assertThatEvents(eventCollector).containsExactly("look both ways before crossing");
-      }
-    }
+    initializeReporter();
+    tester.eval(/* keepGoing= */ false, "t1", "t2");
+    assertThatEvents(eventCollector).containsExactly("look both ways before crossing");
   }
 
   @Test
@@ -633,42 +614,24 @@
         .set("warning-value", new StringValue("warning-value"))
         .setWarning("don't chew with your mouth open");
 
-    for (int i = 0; i < 2; i++) {
-      initializeReporter();
-      tester.evalAndGetError(/*keepGoing=*/ true, "error-value");
-      if (i == 0 || eventsStored()) {
-        assertThatEvents(eventCollector).containsExactly("don't chew with your mouth open");
-      }
-    }
-
     initializeReporter();
-    tester.evalAndGet("warning-value");
-    if (eventsStored()) {
-      assertThatEvents(eventCollector).containsExactly("don't chew with your mouth open");
-    }
+    tester.evalAndGetError(/* keepGoing= */ true, "error-value");
+    assertThatEvents(eventCollector).containsExactly("don't chew with your mouth open");
   }
 
   @Test
   public void progressMessageOnlyPrintedTheFirstTime() throws Exception {
-    // The framework keeps track of warning and error messages, but not progress messages.
-    // So here we see both the progress and warning on the first build, but only the warning
-    // on the subsequent null build.
-    tester
-        .set("x", new StringValue("y"))
-        .setWarning("fizzlepop")
-        .setProgress("just letting you know");
+    // Skyframe does not store progress messages. Here we only see the message on the first build.
+    tester.set("x", new StringValue("y")).setProgress("just letting you know");
 
     StringValue value = (StringValue) tester.evalAndGet("x");
     assertThat(value.getValue()).isEqualTo("y");
-    assertThatEvents(eventCollector).containsExactly("fizzlepop", "just letting you know");
+    assertThatEvents(eventCollector).containsExactly("just letting you know");
 
-    if (eventsStored()) {
-      // On the rebuild, we only replay warning messages.
-      initializeReporter();
-      value = (StringValue) tester.evalAndGet("x");
-      assertThat(value.getValue()).isEqualTo("y");
-      assertThatEvents(eventCollector).containsExactly("fizzlepop");
-    }
+    initializeReporter();
+    value = (StringValue) tester.evalAndGet("x");
+    assertThat(value.getValue()).isEqualTo("y");
+    assertThatEvents(eventCollector).isEmpty();
   }
 
   @Test
@@ -3978,7 +3941,7 @@
         .getOrCreate(parent)
         .addDependency(child)
         .setConstantValue(parentStringValue)
-        .setWarning(parentEvent);
+        .setErrorEvent(parentEvent);
 
     assertThat(tester.evalAndGet(/*keepGoing=*/ false, parent)).isEqualTo(parentStringValue);
     assertThatEvents(eventCollector).containsExactly(childEvent, parentEvent);
@@ -4000,9 +3963,6 @@
 
   @Test
   public void depEventPredicate() throws Exception {
-    if (!eventsStored()) {
-      return;
-    }
     SkyKey parent = GraphTester.toSkyKey("parent");
     SkyKey excludedDep = GraphTester.toSkyKey("excludedDep");
     SkyKey includedDep = GraphTester.toSkyKey("includedDep");
@@ -4026,18 +3986,19 @@
         .setComputedValue(CONCATENATE);
     tester
         .getOrCreate(excludedDep)
-        .setWarning("excludedDep warning")
+        .setErrorEvent("excludedDep error message")
         .setConstantValue(new StringValue("excludedDep"));
     tester
         .getOrCreate(includedDep)
-        .setWarning("includedDep warning")
+        .setErrorEvent("includedDep error message")
         .setConstantValue(new StringValue("includedDep"));
-    tester.eval(/*keepGoing=*/ false, includedDep, excludedDep);
-    assertThatEvents(eventCollector).containsExactly("excludedDep warning", "includedDep warning");
+    tester.eval(/* keepGoing= */ false, includedDep, excludedDep);
+    assertThatEvents(eventCollector)
+        .containsExactly("excludedDep error message", "includedDep error message");
     eventCollector.clear();
     emittedEventState.clear();
-    tester.eval(/*keepGoing=*/ true, parent);
-    assertThatEvents(eventCollector).containsExactly("includedDep warning");
+    tester.eval(/* keepGoing= */ true, parent);
+    assertThatEvents(eventCollector).containsExactly("includedDep error message");
     assertThat(
             ValueWithMetadata.getEvents(
                     tester
@@ -4045,7 +4006,7 @@
                         .getExistingEntryAtCurrentlyEvaluatingVersion(parent)
                         .getValueMaybeWithMetadata())
                 .toList())
-        .containsExactly(Event.warn("includedDep warning"));
+        .containsExactly(Event.error("includedDep error message"));
   }
 
   // Tests that we have a sane implementation of error transience.
diff --git a/src/test/java/com/google/devtools/build/skyframe/ParallelEvaluatorTest.java b/src/test/java/com/google/devtools/build/skyframe/ParallelEvaluatorTest.java
index f3b6572..590299f 100644
--- a/src/test/java/com/google/devtools/build/skyframe/ParallelEvaluatorTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/ParallelEvaluatorTest.java
@@ -50,7 +50,6 @@
 import com.google.common.util.concurrent.SettableFuture;
 import com.google.common.util.concurrent.Uninterruptibles;
 import com.google.devtools.build.lib.bugreport.BugReporter;
-import com.google.devtools.build.lib.collect.nestedset.NestedSetVisitor;
 import com.google.devtools.build.lib.concurrent.AbstractQueueVisitor;
 import com.google.devtools.build.lib.concurrent.BlazeInterners;
 import com.google.devtools.build.lib.events.Event;
@@ -134,7 +133,7 @@
         Version.minimal(),
         builders,
         reportedEvents,
-        new NestedSetVisitor.VisitedState(),
+        new EmittedEventState(),
         storedEventFilter,
         ErrorInfoManager.UseChildErrorInfoIfNecessary.INSTANCE,
         keepGoing,
@@ -627,54 +626,6 @@
     assertThatEvents(reportedEvents.getEvents()).containsExactly("warning on 'a'");
   }
 
-  /** Regression test: events from already-done value not replayed. */
-  @Test
-  public void eventFromDoneChildRecorded() throws Exception {
-    graph = new InMemoryGraphImpl();
-    set("a", "a").setWarning("warning on 'a'");
-    SkyKey a = GraphTester.toSkyKey("a");
-    SkyKey top = GraphTester.toSkyKey("top");
-    tester.getOrCreate(top).addDependency(a).setComputedValue(CONCATENATE);
-    // Build a so that it is already in the graph.
-    eval(false, a);
-    assertThat(reportedEvents.getEvents()).hasSize(1);
-    reportedEvents.clear();
-    // Build top. The warning from a should be printed.
-    eval(false, top);
-    assertThat(reportedEvents.getEvents()).hasSize(1);
-    reportedEvents.clear();
-    // Build top again. The warning should have been stored in the value.
-    eval(false, top);
-    assertThat(reportedEvents.getEvents()).hasSize(1);
-  }
-
-  @Test
-  public void postableFromDoneChildRecorded() throws Exception {
-    graph = new InMemoryGraphImpl();
-    Postable post =
-        new Postable() {
-          @Override
-          public boolean storeForReplay() {
-            return true;
-          }
-        };
-    set("a", "a").setPostable(post);
-    SkyKey a = GraphTester.toSkyKey("a");
-    SkyKey top = GraphTester.toSkyKey("top");
-    tester.getOrCreate(top).addDependency(a).setComputedValue(CONCATENATE);
-    // Build a so that it is already in the graph.
-    eval(false, a);
-    assertThat(reportedEvents.getPosts()).containsExactly(post);
-    reportedEvents.clear();
-    // Build top. The post from a should be printed.
-    eval(false, top);
-    assertThat(reportedEvents.getPosts()).containsExactly(post);
-    reportedEvents.clear();
-    // Build top again. The post should have been stored in the value.
-    eval(false, top);
-    assertThat(reportedEvents.getPosts()).containsExactly(post);
-  }
-
   @Test
   public void errorOfTopLevelTargetReported() throws Exception {
     graph = new InMemoryGraphImpl();
@@ -728,7 +679,7 @@
 
       @Override
       Reportable createStored() {
-        return Event.warn("deprecated");
+        return Event.error("broken");
       }
 
       @Override
@@ -3238,7 +3189,7 @@
             Version.minimal(),
             tester.getSkyFunctionMap(),
             reportedEvents,
-            new NestedSetVisitor.VisitedState(),
+            new EmittedEventState(),
             EventFilter.FULL_STORAGE,
             ErrorInfoManager.UseChildErrorInfoIfNecessary.INSTANCE,
             // Doesn't matter for this test case.
diff --git a/src/test/java/com/google/devtools/build/skyframe/PriorityTest.java b/src/test/java/com/google/devtools/build/skyframe/PriorityTest.java
index 1b5f19f..12a3606 100644
--- a/src/test/java/com/google/devtools/build/skyframe/PriorityTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/PriorityTest.java
@@ -22,7 +22,6 @@
 import com.google.auto.value.AutoValue;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.Interner;
-import com.google.devtools.build.lib.collect.nestedset.NestedSetVisitor;
 import com.google.devtools.build.lib.concurrent.BlazeInterners;
 import com.google.devtools.build.lib.concurrent.TieredPriorityExecutor;
 import com.google.devtools.build.lib.events.StoredEventHandler;
@@ -63,7 +62,7 @@
             Version.minimal(),
             tester.getSkyFunctionMap(),
             reportedEvents,
-            new NestedSetVisitor.VisitedState(),
+            new EmittedEventState(),
             EventFilter.FULL_STORAGE,
             ErrorInfoManager.UseChildErrorInfoIfNecessary.INSTANCE,
             /* keepGoing= */ false,
diff --git a/src/test/java/com/google/devtools/build/skyframe/StateMachineTest.java b/src/test/java/com/google/devtools/build/skyframe/StateMachineTest.java
index ec3b429..59c64bf 100644
--- a/src/test/java/com/google/devtools/build/skyframe/StateMachineTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/StateMachineTest.java
@@ -21,7 +21,6 @@
 import static org.junit.Assert.fail;
 
 import com.google.common.collect.ImmutableList;
-import com.google.devtools.build.lib.collect.nestedset.NestedSetVisitor;
 import com.google.devtools.build.lib.concurrent.AbstractQueueVisitor;
 import com.google.devtools.build.lib.events.ExtendedEventHandler;
 import com.google.devtools.build.lib.events.StoredEventHandler;
@@ -66,7 +65,7 @@
             Version.minimal(),
             tester.getSkyFunctionMap(),
             reportedEvents,
-            new NestedSetVisitor.VisitedState(),
+            new EmittedEventState(),
             EventFilter.FULL_STORAGE,
             ErrorInfoManager.UseChildErrorInfoIfNecessary.INSTANCE,
             keepGoing,
diff --git a/src/test/shell/bazel/bazelignore_test.sh b/src/test/shell/bazel/bazelignore_test.sh
index b59e17d..30eb92c 100755
--- a/src/test/shell/bazel/bazelignore_test.sh
+++ b/src/test/shell/bazel/bazelignore_test.sh
@@ -130,7 +130,6 @@
     # Test patterns with exclude.
     bazel build -- //ignoreme/deep/... -//ignoreme/... >& "$TEST_log" \
         || fail "Expected success"
-    expect_log "WARNING: Pattern '//ignoreme/deep/...' was filtered out by ignored directory 'ignoreme'"
     expect_not_log "circular symlinks detected"
     expect_not_log "ignoreme/deep/deeper"
 
diff --git a/src/test/shell/integration/execution_phase_tests.sh b/src/test/shell/integration/execution_phase_tests.sh
index f61a8ea..7dcf63a 100755
--- a/src/test/shell/integration/execution_phase_tests.sh
+++ b/src/test/shell/integration/execution_phase_tests.sh
@@ -254,29 +254,6 @@
       "Digests cache not reenabled"
 }
 
-function test_analysis_warning_cached() {
-  mkdir -p "foo" "bar" || fail "Could not create directories"
-  cat > foo/BUILD <<'EOF' || fail "foo/BUILD"
-cc_library(
-    name = 'foo',
-    deprecation = 'foo warning',
-    srcs = ['foo.cc'],
-    visibility = ['//visibility:public']
-)
-EOF
-  cat > bar/BUILD <<'EOF' || fail "bar/BUILD"
-cc_library(name = 'bar', srcs = ['bar.cc'], deps = ['//foo:foo'])
-EOF
-  touch foo/foo.cc bar/bar.cc || fail "Couldn't touch"
-  bazel build --nobuild //bar:bar >& "$TEST_log" || fail "Expected success"
-  expect_log "WARNING: .*: foo warning"
-  bazel build //bar:bar >& "$TEST_log" || fail "Expected success"
-  expect_log "WARNING: .*: foo warning"
-  echo "// comment" >> bar/bar.cc || fail "Couldn't change contents"
-  bazel build //bar:bar >& "$TEST_log" || fail "Expected success"
-  expect_log "WARNING: .*: foo warning"
-}
-
 function test_max_open_file_descriptors() {
   echo "nfiles: hard $(ulimit -H -n), soft $(ulimit -S -n)"
 
diff --git a/src/test/shell/integration/output_filter_test.sh b/src/test/shell/integration/output_filter_test.sh
index fc0ebb8..f17d9f2 100755
--- a/src/test/shell/integration/output_filter_test.sh
+++ b/src/test/shell/integration/output_filter_test.sh
@@ -209,18 +209,17 @@
   bazel build //$pkg/foo/bar:tomato >&"$TEST_log" || fail "build failed"
   expect_log "is unexpected here"
 
-  # check that we do get a deprecation warning if we select the target
+  bazel clean >& "$TEST_log" || fail "clean failed"
 
-  echo "# add comment to trigger rebuild" >> $pkg/foo/bar/tomato.skin
-  echo "# add comment to trigger rebuild" >> $pkg/foo/bar/tomato.pulp
+  # check that we do get a deprecation warning if we select the target
   bazel build --output_filter=$pkg/foo/bar:tomato //$pkg/foo/bar:tomato >&"$TEST_log" \
     || fail "build failed"
   expect_log "is unexpected here"
 
+  bazel clean >& "$TEST_log" || fail "clean failed"
+
   # check that we do not get a deprecation warning if we select another target
-  echo "# add another comment" >> $pkg/foo/bar/tomato.skin
-  echo "# add another comment" >> $pkg/foo/bar/tomato.pulp
-  bazel build --output_filter=$pkg/foo/bar/:red //$pkg/foo/bar:tomato >&"$TEST_log" \
+  bazel build --output_filter=$pkg/foo/bar:red //$pkg/foo/bar:tomato >&"$TEST_log" \
     || fail "build failed"
   expect_not_log "is unexpected here"
 }