Support ordering constraints on build events

In the build event protocol, we promise to respect certain ordering
constraints that come naturally by causality anyway (e.g., the root
cause of a failure has to come before the failure). However, in the
way the call structure is organized, events might occur on the event
bus in wrong order. So allow events to specify that order and make the
streamer honor it.

--
Change-Id: I1fbe9b93681f0ddfa35d9d00d5d1b02103da38a5
Reviewed-on: https://bazel-review.googlesource.com/#/c/7370
MOS_MIGRATED_REVID=139774946

3 files changed, 164 insertions, 3 deletions

diff --git a/src/main/java/com/google/devtools/build/lib/buildeventstream/BuildEventWithOrderConstraint.java b/src/main/java/com/google/devtools/build/lib/buildeventstream/BuildEventWithOrderConstraint.java
new file mode 100644
index 0000000000..08cd280b7a
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/buildeventstream/BuildEventWithOrderConstraint.java
@@ -0,0 +1,29 @@
+// Copyright 2016 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.buildeventstream;
+
+import java.util.Collection;
+
+/** Interface for {@link BuildEvent}s with order constraints. */
+public interface BuildEventWithOrderConstraint extends BuildEvent {
+  /**
+   * Specify events that need to come first.
+   *
+   * <p>Specify events by their {@link BuildEventId} that need to be posted on the build event
+   * stream before this event. In doing so, the event promises that the events to be waited for are
+   * already generated, so that the event does not have to be buffered for an extended time.
+   */
+  Collection<BuildEventId> postedAfter();
+}
diff --git a/src/main/java/com/google/devtools/build/lib/runtime/BuildEventStreamer.java b/src/main/java/com/google/devtools/build/lib/runtime/BuildEventStreamer.java
index 812d223449..8f5292f83b 100644
--- a/src/main/java/com/google/devtools/build/lib/runtime/BuildEventStreamer.java
+++ b/src/main/java/com/google/devtools/build/lib/runtime/BuildEventStreamer.java
@@ -15,7 +15,9 @@
 package com.google.devtools.build.lib.runtime;
 
 import com.google.common.annotations.VisibleForTesting;
+import com.google.common.collect.HashMultimap;
 import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.Multimap;
 import com.google.common.collect.Sets;
 import com.google.common.eventbus.Subscribe;
 import com.google.devtools.build.lib.actions.ActionExecutedEvent;
@@ -25,6 +27,7 @@ import com.google.devtools.build.lib.buildeventstream.BuildEvent;
 import com.google.devtools.build.lib.buildeventstream.BuildEventId;
 import com.google.devtools.build.lib.buildeventstream.BuildEventStreamProtos.Aborted.AbortReason;
 import com.google.devtools.build.lib.buildeventstream.BuildEventTransport;
+import com.google.devtools.build.lib.buildeventstream.BuildEventWithOrderConstraint;
 import com.google.devtools.build.lib.buildeventstream.ProgressEvent;
 import com.google.devtools.build.lib.buildtool.buildevent.BuildCompleteEvent;
 import com.google.devtools.build.lib.buildtool.buildevent.BuildInterruptedEvent;
@@ -41,6 +44,7 @@ public class BuildEventStreamer implements EventHandler {
   private final Collection<BuildEventTransport> transports;
   private Set<BuildEventId> announcedEvents;
   private Set<BuildEventId> postedEvents;
+  private final Multimap<BuildEventId, BuildEvent> pendingEvents;
   private int progressCount;
   private AbortReason abortReason = AbortReason.UNKNOWN;
   private static final Logger LOG = Logger.getLogger(BuildEventStreamer.class.getName());
@@ -50,6 +54,7 @@ public class BuildEventStreamer implements EventHandler {
     this.announcedEvents = null;
     this.postedEvents = null;
     this.progressCount = 0;
+    this.pendingEvents = HashMultimap.create();
   }
 
   /**
@@ -98,11 +103,19 @@ public class BuildEventStreamer implements EventHandler {
     }
   }
 
+  /** Clear pending events by generating aborted events for all their requisits. */
+  private void clearPendingEvents() {
+    while (!pendingEvents.isEmpty()) {
+      BuildEventId id = pendingEvents.keySet().iterator().next();
+      buildEvent(new AbortedEvent(id, abortReason, ""));
+    }
+  }
+
   /**
-   * Clear all events that are still pending; events not naturally closed by the expected event
+   * Clear all events that are still announced; events not naturally closed by the expected event
    * normally only occur if the build is aborted.
    */
-  private void clearPendingEvents() {
+  private void clearAnnouncedEvents() {
     if (announcedEvents != null) {
       // create a copy of the identifiers to clear, as the post method
       // will change the set of already announced events.
@@ -142,8 +155,9 @@ public class BuildEventStreamer implements EventHandler {
 
   @Subscribe
   public void buildComplete(BuildCompleteEvent event) {
-    post(ProgressEvent.finalProgressUpdate(progressCount));
     clearPendingEvents();
+    post(ProgressEvent.finalProgressUpdate(progressCount));
+    clearAnnouncedEvents();
     close();
   }
 
@@ -156,7 +170,23 @@ public class BuildEventStreamer implements EventHandler {
       }
     }
 
+    if (event instanceof BuildEventWithOrderConstraint) {
+      // Check if all prerequisit events are posted already.
+      for (BuildEventId prerequisiteId : ((BuildEventWithOrderConstraint) event).postedAfter()) {
+        if (!postedEvents.contains(prerequisiteId)) {
+          pendingEvents.put(prerequisiteId, event);
+          return;
+        }
+      }
+    }
+
     post(event);
+
+    // Reconsider all events blocked by the event just posted.
+    Collection<BuildEvent> toReconsider = pendingEvents.removeAll(event.getEventId());
+    for (BuildEvent freedEvent : toReconsider) {
+      buildEvent(freedEvent);
+    }
   }
 
   @VisibleForTesting
diff --git a/src/test/java/com/google/devtools/build/lib/runtime/BuildEventStreamerTest.java b/src/test/java/com/google/devtools/build/lib/runtime/BuildEventStreamerTest.java
index 8a02188df2..a5a79d082d 100644
--- a/src/test/java/com/google/devtools/build/lib/runtime/BuildEventStreamerTest.java
+++ b/src/test/java/com/google/devtools/build/lib/runtime/BuildEventStreamerTest.java
@@ -20,11 +20,14 @@ import static org.junit.Assert.assertTrue;
 import com.google.common.collect.ImmutableSet;
 import com.google.devtools.build.lib.buildeventstream.BuildEvent;
 import com.google.devtools.build.lib.buildeventstream.BuildEventId;
+import com.google.devtools.build.lib.buildeventstream.BuildEventStreamProtos;
 import com.google.devtools.build.lib.buildeventstream.BuildEventTransport;
+import com.google.devtools.build.lib.buildeventstream.BuildEventWithOrderConstraint;
 import com.google.devtools.build.lib.buildeventstream.GenericBuildEvent;
 import com.google.devtools.build.lib.buildeventstream.ProgressEvent;
 import com.google.devtools.build.lib.buildtool.buildevent.BuildCompleteEvent;
 import java.util.ArrayList;
+import java.util.Collection;
 import java.util.List;
 import org.junit.Test;
 import org.junit.runner.RunWith;
@@ -54,6 +57,43 @@ public class BuildEventStreamerTest {
     }
   }
 
+  private static class GenericOrderEvent implements BuildEventWithOrderConstraint {
+    private final BuildEventId id;
+    private final Collection<BuildEventId> children;
+    private final Collection<BuildEventId> after;
+
+    GenericOrderEvent(
+        BuildEventId id, Collection<BuildEventId> children, Collection<BuildEventId> after) {
+      this.id = id;
+      this.children = children;
+      this.after = after;
+    }
+
+    GenericOrderEvent(BuildEventId id, Collection<BuildEventId> children) {
+      this(id, children, children);
+    }
+
+    @Override
+    public BuildEventId getEventId() {
+      return id;
+    }
+
+    @Override
+    public Collection<BuildEventId> getChildrenEvents() {
+      return children;
+    }
+
+    @Override
+    public BuildEventStreamProtos.BuildEvent asStreamProto() {
+      return GenericBuildEvent.protoChaining(this).build();
+    }
+
+    @Override
+    public Collection<BuildEventId> postedAfter() {
+      return after;
+    }
+  }
+
   private static BuildEventId testId(String opaque) {
     return BuildEventId.unknownBuildEventId(opaque);
   }
@@ -188,4 +228,66 @@ public class BuildEventStreamerTest {
     // The early event should be reported precisely once.
     assertEquals(1, earlyEventCount);
   }
+
+  @Test
+  public void testReodering() {
+    // Verify that an event requiring to be posted after another one is indeed.
+
+    RecordingBuildEventTransport transport = new RecordingBuildEventTransport();
+    BuildEventStreamer streamer =
+        new BuildEventStreamer(ImmutableSet.<BuildEventTransport>of(transport));
+
+    BuildEventId expectedId = testId("the target");
+    BuildEvent startEvent =
+        new GenericBuildEvent(
+            testId("Initial"),
+            ImmutableSet.<BuildEventId>of(ProgressEvent.INITIAL_PROGRESS_UPDATE, expectedId));
+    BuildEvent rootCause =
+        new GenericBuildEvent(testId("failure event"), ImmutableSet.<BuildEventId>of());
+    BuildEvent failedTarget =
+        new GenericOrderEvent(expectedId, ImmutableSet.<BuildEventId>of(rootCause.getEventId()));
+
+    streamer.buildEvent(startEvent);
+    streamer.buildEvent(failedTarget);
+    streamer.buildEvent(rootCause);
+
+    List<BuildEvent> allEventsSeen = transport.getEvents();
+    assertThat(allEventsSeen).hasSize(4);
+    assertEquals(startEvent.getEventId(), allEventsSeen.get(0).getEventId());
+    BuildEvent linkEvent = allEventsSeen.get(1);
+    assertEquals(ProgressEvent.INITIAL_PROGRESS_UPDATE, linkEvent.getEventId());
+    assertEquals(rootCause.getEventId(), allEventsSeen.get(2).getEventId());
+    assertEquals(failedTarget.getEventId(), allEventsSeen.get(3).getEventId());
+  }
+
+  @Test
+  public void testMissingPrerequisits() {
+    // Verify that an event where the prerequisite is never coming till the end of
+    // the build still gets posted, with the prerequisite aborted.
+
+    RecordingBuildEventTransport transport = new RecordingBuildEventTransport();
+    BuildEventStreamer streamer =
+        new BuildEventStreamer(ImmutableSet.<BuildEventTransport>of(transport));
+
+    BuildEventId expectedId = testId("the target");
+    BuildEvent startEvent =
+        new GenericBuildEvent(
+            testId("Initial"),
+            ImmutableSet.<BuildEventId>of(ProgressEvent.INITIAL_PROGRESS_UPDATE, expectedId));
+    BuildEventId rootCauseId = testId("failure event");
+    BuildEvent failedTarget =
+        new GenericOrderEvent(expectedId, ImmutableSet.<BuildEventId>of(rootCauseId));
+
+    streamer.buildEvent(startEvent);
+    streamer.buildEvent(failedTarget);
+    streamer.buildComplete(new BuildCompleteEvent(null));
+
+    List<BuildEvent> allEventsSeen = transport.getEvents();
+    assertThat(allEventsSeen).hasSize(5);
+    assertEquals(startEvent.getEventId(), allEventsSeen.get(0).getEventId());
+    BuildEvent linkEvent = allEventsSeen.get(1);
+    assertEquals(ProgressEvent.INITIAL_PROGRESS_UPDATE, linkEvent.getEventId());
+    assertEquals(rootCauseId, allEventsSeen.get(2).getEventId());
+    assertEquals(failedTarget.getEventId(), allEventsSeen.get(3).getEventId());
+  }
 }