Update from Google.

--
MOE_MIGRATED_REVID=85702957

56 files changed, 8201 insertions, 0 deletions

diff --git a/src/main/java/com/google/devtools/build/lib/util/AbruptExitException.java b/src/main/java/com/google/devtools/build/lib/util/AbruptExitException.java
new file mode 100644
index 0000000000..ff62a7eb90
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/util/AbruptExitException.java
@@ -0,0 +1,52 @@
+// Copyright 2014 Google Inc. 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.util;
+
+/**
+ * An exception thrown by various error conditions that are severe enough to halt the command (e.g.
+ * even a --keep_going build). These typically need to signal to the handling code what happened.
+ * Therefore, these exceptions contain a recommended ExitCode allowing the exception to "set" a
+ * returned numeric exit code.
+ *
+ * When an instance of this exception is thrown, Blaze will try to halt as soon as reasonably
+ * possible.
+ */
+public class AbruptExitException extends Exception {
+
+  private final ExitCode exitCode;
+
+  public AbruptExitException(String message, ExitCode exitCode) {
+    super(message);
+    this.exitCode = exitCode;
+  }
+
+  public AbruptExitException(String message, ExitCode exitCode, Throwable cause) {
+    super(message, cause);
+    this.exitCode = exitCode;
+  }
+
+  public AbruptExitException(ExitCode exitCode, Throwable cause) {
+    super(cause);
+    this.exitCode = exitCode;
+  }
+
+  public AbruptExitException(ExitCode exitCode) {
+    this.exitCode = exitCode;
+  }
+
+  public ExitCode getExitCode() {
+    return exitCode;
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/util/AbstractIndexer.java b/src/main/java/com/google/devtools/build/lib/util/AbstractIndexer.java
new file mode 100644
index 0000000000..4b61fe6541
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/util/AbstractIndexer.java
@@ -0,0 +1,37 @@
+// Copyright 2014 Google Inc. 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.util;
+
+import static java.nio.charset.StandardCharsets.UTF_8;
+
+/**
+ * Abstract class for string indexers.
+ */
+abstract class AbstractIndexer implements StringIndexer {
+
+  /**
+   * Conversion from String to byte[].
+   */
+  protected static byte[] string2bytes(String string) {
+    return string.getBytes(UTF_8);
+  }
+
+  /**
+   * Conversion from byte[] to String.
+   */
+  protected static String bytes2string(byte[] bytes) {
+    return new String(bytes, UTF_8);
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/util/AnsiStrippingOutputStream.java b/src/main/java/com/google/devtools/build/lib/util/AnsiStrippingOutputStream.java
new file mode 100644
index 0000000000..6c6b878543
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/util/AnsiStrippingOutputStream.java
@@ -0,0 +1,176 @@
+// Copyright 2014 Google Inc. 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.util;
+
+import java.io.IOException;
+import java.io.OutputStream;
+
+/**
+ * A pass-thru {@link OutputStream} that strips ANSI control codes.
+ */
+public class AnsiStrippingOutputStream extends OutputStream {
+  // The idea is straightforward: the regexp for ANSI control codes is
+  // \x1b\[[;0-9]*[a-zA-Z] . Implementing it as a stream is a little ugly,
+  // though.
+
+  private enum State {
+    NORMAL,
+    AFTER_ESCAPE,
+    PARAMETER,
+  }
+
+  private byte[] outputBuffer;
+  private int outputBufferPos;
+
+  private static final int ESCAPE_BUFFER_LENGTH = 128;
+  private byte[] escapeCodeBuffer;
+  private int escapeCodeBufferPos;
+  private OutputStream output;
+  private State state;
+
+  public AnsiStrippingOutputStream(OutputStream output) {
+    this.output = output;
+    escapeCodeBuffer = new byte[ESCAPE_BUFFER_LENGTH];
+    escapeCodeBufferPos = 0;
+    state = State.NORMAL;
+  }
+
+  @Override
+  public synchronized void write(int b) throws IOException {
+    // As per the contract of OutputStream.write(int)
+    byte[] array = { (byte) (b & 0xff) };
+    write(array, 0, 1);
+  }
+
+  @Override
+  public synchronized void write(byte b[], int off, int len) throws IOException {
+    int i = 0;
+    if (state == State.NORMAL) {
+
+      // Avoid outputBuffer allocation entirely if that's possible
+      while ((i < len) && (b[off + i] != 0x1b)) {
+        i++;
+      }
+      if (i == len) {
+        output.write(b, off, len);
+        return;
+      }
+    }
+
+    // In the worst case, the contents of the escape buffer and the contents
+    // of the input buffer are both copied to the output, so the length of the
+    // output buffer should be the sum of the length of both these buffers.
+    outputBuffer = new byte[len + ESCAPE_BUFFER_LENGTH];
+    System.arraycopy(b, off, outputBuffer, 0, i);
+    outputBufferPos = i;
+
+    for (; i < len; i++) {
+      processByte(b[off + i]);
+    }
+
+    try {
+      output.write(outputBuffer, 0, outputBufferPos);
+    } finally {
+      outputBuffer = null;  // Make it possible to garbage collect the array
+    }
+  }
+
+  private void processByte(byte b) {
+    switch (state) {
+      case NORMAL:
+        if (escapeCodeBufferPos != 0) {
+          throw new IllegalStateException();
+        }
+        if (b == 0x1b) {
+          state = State.AFTER_ESCAPE;
+          addByteToEscapeBuffer(b);
+        } else {
+          dumpByte(b);
+        }
+        break;
+
+      case AFTER_ESCAPE:
+        if (b == '[') {
+          state = State.PARAMETER;
+          addByteToEscapeBuffer(b);
+        } else if (b == 0x1b) {
+          dumpEscapeBuffer();
+          state = State.AFTER_ESCAPE;
+          addByteToEscapeBuffer(b);
+        } else {
+          dumpEscapeBuffer();
+          dumpByte(b);
+          state = State.NORMAL;
+        }
+        break;
+
+      case PARAMETER:
+        if ((b >= '0' && b <= '9') || b == ';') {
+          // Parameter continues
+          addByteToEscapeBuffer(b);
+        } else if ((b >= 'a' && b <= 'z') || (b >= 'A' && b <= 'Z')) {
+          // Found a control sequence, discard it and revert to normal state
+          discardEscapeBuffer();
+          state = State.NORMAL;
+        } else if (b == 0x1b) {
+          // Another escape sequence begins immediately after, and this is
+          // an illegal escape sequence
+          dumpEscapeBuffer();
+          state = State.AFTER_ESCAPE;
+          addByteToEscapeBuffer(b);
+        } else {
+          // Illegal control sequence, output it
+          dumpEscapeBuffer();
+          state = State.NORMAL;
+        }
+        break;
+    }
+  }
+
+  private void addByteToEscapeBuffer(byte b) {
+    escapeCodeBuffer[escapeCodeBufferPos++] = b;
+    if (escapeCodeBufferPos == ESCAPE_BUFFER_LENGTH) {
+      // Buffer full. Assume that no sane code emits an ANSI control code this
+      // long and revert to normal state.
+      dumpEscapeBuffer();
+      state = State.NORMAL;
+    }
+  }
+
+  private void discardEscapeBuffer() {
+    escapeCodeBufferPos = 0;
+  }
+
+  private void dumpByte(byte b) {
+    outputBuffer[outputBufferPos++] = b;
+  }
+
+  private void dumpEscapeBuffer() {
+    System.arraycopy(escapeCodeBuffer, 0,
+                     outputBuffer, outputBufferPos, escapeCodeBufferPos);
+    outputBufferPos += escapeCodeBufferPos;
+    escapeCodeBufferPos = 0;
+  }
+
+  @Override
+  public void flush() throws IOException {
+    output.flush();
+  }
+
+  @Override
+  public void close() throws IOException {
+    output.close();
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/util/BinaryPredicate.java b/src/main/java/com/google/devtools/build/lib/util/BinaryPredicate.java
new file mode 100644
index 0000000000..c7709e2145
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/util/BinaryPredicate.java
@@ -0,0 +1,38 @@
+// Copyright 2014 Google Inc. 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.util;
+
+import com.google.common.base.Predicate;
+
+import javax.annotation.Nullable;
+
+/**
+ * A two-argument version of {@link Predicate} that determines a true or false value for pairs of
+ * inputs.
+ *
+ * <p>Just as a {@link Predicate} is useful for filtering iterables of values, a {@link
+ * BinaryPredicate} is useful for filtering iterables of paired values, like {@link
+ * java.util.Map.Entry} or {@link Pair}.
+ *
+ * <p>See {@link Predicate} for implementation notes and advice.
+ */
+public interface BinaryPredicate<X, Y> {
+
+  /**
+   * Applies this {@link BinaryPredicate} to the given objects.
+   *
+   * @return the value of this predicate when applied to inputs {@code x, y}
+   */
+  boolean apply(@Nullable X x, @Nullable Y y);
+}
diff --git a/src/main/java/com/google/devtools/build/lib/util/BlazeClock.java b/src/main/java/com/google/devtools/build/lib/util/BlazeClock.java
new file mode 100644
index 0000000000..72806dda60
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/util/BlazeClock.java
@@ -0,0 +1,51 @@
+// Copyright 2014 Google Inc. 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.util;
+
+import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
+import com.google.devtools.build.lib.util.Clock;
+import com.google.devtools.build.lib.util.JavaClock;
+
+/**
+ * Provides the clock implementation used by Blaze, which is {@link JavaClock}
+ * by default, but can be overridden at runtime. Note that if you set this
+ * clock, you also have to set the clock used by the Profiler.
+ */
+@ThreadSafe
+public abstract class BlazeClock {
+
+  private BlazeClock() {
+  }
+
+  private static volatile Clock instance = new JavaClock();
+
+  /**
+   * Returns singleton instance of the clock
+   */
+  public static Clock instance() {
+    return instance;
+  }
+
+  /**
+   * Overrides default clock instance.
+   */
+  public static synchronized void setClock(Clock clock) {
+    instance = clock;
+  }
+
+  public static long nanoTime() {
+    return instance().nanoTime();
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/util/CanonicalStringIndexer.java b/src/main/java/com/google/devtools/build/lib/util/CanonicalStringIndexer.java
new file mode 100644
index 0000000000..618e88ba94
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/util/CanonicalStringIndexer.java
@@ -0,0 +1,113 @@
+// Copyright 2014 Google Inc. 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.util;
+
+import com.google.common.base.Preconditions;
+import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
+import com.google.devtools.build.lib.util.StringCanonicalizer;
+
+import java.util.Map;
+
+/**
+ * A string indexer backed by a map and reverse index lookup.
+ * Every unique string is stored in memory exactly once.
+ */
+@ThreadSafe
+public class CanonicalStringIndexer extends AbstractIndexer {
+
+  private static final int NOT_FOUND = -1;
+
+  // This is similar to (Synchronized) BiMap.
+  // These maps *must* be weakly threadsafe to ensure thread safety for string
+  // indexer as a whole. Specifically, mutating operations are serialized, but
+  // read-only operations may be executed concurrently with mutators.
+  private final Map<String, Integer> stringToInt;
+  private final Map<Integer, String> intToString;
+
+  /*
+   * Creates an indexer instance from two backing maps. These maps may be
+   * pre-initialized with data, but *must*:
+   * a. Support read-only operations done concurrently with mutations.
+   *    Note that mutations will be serialized.
+   * b. Be reverse mappings of each other, if pre-initialized.
+   */
+  public CanonicalStringIndexer(Map<String, Integer> stringToInt,
+                                Map<Integer, String> intToString) {
+    Preconditions.checkArgument(stringToInt.size() == intToString.size());
+    this.stringToInt = stringToInt;
+    this.intToString = intToString;
+  }
+
+
+  @Override
+  public synchronized void clear() {
+    stringToInt.clear();
+    intToString.clear();
+  }
+
+  @Override
+  public int size() {
+    return intToString.size();
+  }
+
+  @Override
+  public int getOrCreateIndex(String s) {
+    Integer i = stringToInt.get(s);
+    if (i == null) {
+      synchronized (this) {
+        // First, make sure another thread hasn't just added the entry:
+        i = stringToInt.get(s);
+        if (i != null) {
+          return i;
+        }
+
+        int ind = intToString.size();
+        s = StringCanonicalizer.intern(s);
+        stringToInt.put(s, ind);
+        intToString.put(ind, s);
+        return ind;
+      }
+    } else {
+      return i;
+    }
+  }
+
+  @Override
+  public int getIndex(String s) {
+    Integer i = stringToInt.get(s);
+    return (i == null) ? NOT_FOUND : i;
+  }
+
+  @Override
+  public synchronized boolean addString(String s) {
+    int originalSize = size();
+    getOrCreateIndex(s);
+    return (size() > originalSize);
+  }
+
+  @Override
+  public String getStringForIndex(int i) {
+    return intToString.get(i);
+  }
+
+  @Override
+  public synchronized String toString() {
+    StringBuilder builder = new StringBuilder();
+    builder.append("size = ").append(size()).append("\n");
+    for (Map.Entry<String, Integer> entry : stringToInt.entrySet()) {
+      builder.append(entry.getKey()).append(" <==> ").append(entry.getValue()).append("\n");
+    }
+    return builder.toString();
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/util/Clock.java b/src/main/java/com/google/devtools/build/lib/util/Clock.java
new file mode 100644
index 0000000000..878cb11379
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/util/Clock.java
@@ -0,0 +1,33 @@
+// Copyright 2014 Google Inc. 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.util;
+
+/**
+ * This class provides an interface for a pluggable clock.
+ */
+public interface Clock {
+
+  /**
+   * Returns the current time in milliseconds. The milliseconds are counted from midnight
+   * Jan 1, 1970.
+   */
+  long currentTimeMillis();
+
+  /**
+   * Returns the current time in nanoseconds. The nanoseconds are measured relative to some
+   * unknown, but fixed event. Unfortunately, a sequence of calls to this method is *not*
+   * guaranteed to return non-decreasing values, so callers should be tolerant to this behavior.
+   */
+  long nanoTime();
+}
diff --git a/src/main/java/com/google/devtools/build/lib/util/CommandBuilder.java b/src/main/java/com/google/devtools/build/lib/util/CommandBuilder.java
new file mode 100644
index 0000000000..372802de7d
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/util/CommandBuilder.java
@@ -0,0 +1,176 @@
+// Copyright 2014 Google Inc. 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.util;
+
+import com.google.common.annotations.VisibleForTesting;
+import com.google.common.base.CharMatcher;
+import com.google.common.base.Joiner;
+import com.google.common.base.Preconditions;
+import com.google.common.base.Splitter;
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.Iterables;
+import com.google.common.collect.Lists;
+import com.google.devtools.build.lib.shell.Command;
+import com.google.devtools.build.lib.vfs.Path;
+
+import java.io.File;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+
+/**
+ * Implements OS aware {@link Command} builder. At this point only Linux, Mac
+ * and Windows XP are supported.
+ *
+ * <p>Builder will also apply heuristic to identify trivial cases where
+ * unix-like command lines could be automatically converted into the
+ * Windows-compatible form.
+ *
+ * <p>TODO(bazel-team): (2010) Some of the code here is very similar to the
+ * {@link com.google.devtools.build.lib.shell.Shell} class. This should be looked at.
+ */
+public final class CommandBuilder {
+
+  private static final List<String> SHELLS = ImmutableList.of("/bin/sh", "/bin/bash");
+
+  private static final Splitter ARGV_SPLITTER = Splitter.on(CharMatcher.anyOf(" \t"));
+
+  private final OS system;
+  private final List<String> argv = new ArrayList<>();
+  private final Map<String, String> env = new HashMap<>();
+  private File workingDir = null;
+  private boolean useShell = false;
+
+  public CommandBuilder() {
+    this(OS.getCurrent());
+  }
+
+  @VisibleForTesting
+  CommandBuilder(OS system) {
+    this.system = system;
+  }
+
+  public CommandBuilder addArg(String arg) {
+    Preconditions.checkNotNull(arg, "Argument must not be null");
+    argv.add(arg);
+    return this;
+  }
+
+  public CommandBuilder addArgs(Iterable<String> args) {
+    Preconditions.checkArgument(!Iterables.contains(args, null), "Arguments must not be null");
+    Iterables.addAll(argv, args);
+    return this;
+  }
+
+  public CommandBuilder addArgs(String... args) {
+    return addArgs(Arrays.asList(args));
+  }
+
+  public CommandBuilder addEnv(Map<String, String> env) {
+    Preconditions.checkNotNull(env);
+    this.env.putAll(env);
+    return this;
+  }
+
+  public CommandBuilder emptyEnv() {
+    env.clear();
+    return this;
+  }
+
+  public CommandBuilder setEnv(Map<String, String> env) {
+    emptyEnv();
+    addEnv(env);
+    return this;
+  }
+
+  public CommandBuilder setWorkingDir(Path path) {
+    Preconditions.checkNotNull(path);
+    workingDir = path.getPathFile();
+    return this;
+  }
+
+  public CommandBuilder useTempDir() {
+    workingDir = new File(System.getProperty("java.io.tmpdir"));
+    return this;
+  }
+
+  public CommandBuilder useShell(boolean useShell) {
+    this.useShell = useShell;
+    return this;
+  }
+
+  private boolean argvStartsWithSh() {
+    return argv.size() >= 2 && SHELLS.contains(argv.get(0)) && "-c".equals(argv.get(1));
+  }
+
+  private String[] transformArgvForLinux() {
+    // If command line already starts with "/bin/sh -c", ignore useShell attribute.
+    if (useShell && !argvStartsWithSh()) {
+      // c.g.io.base.shell.Shell.shellify() actually concatenates argv into the space-separated
+      // string here. Not sure why, but we will do the same.
+      return new String[] { "/bin/sh", "-c", Joiner.on(' ').join(argv) };
+    }
+    return argv.toArray(new String[argv.size()]);
+  }
+
+  private String[] transformArgvForWindows() {
+    List<String> modifiedArgv;
+    // Heuristic: replace "/bin/sh -c" with something more appropriate for Windows.
+    if (argvStartsWithSh()) {
+      useShell = true;
+      modifiedArgv = Lists.newArrayList(argv.subList(2, argv.size()));
+    } else {
+      modifiedArgv = Lists.newArrayList(argv);
+    }
+
+    if (!modifiedArgv.isEmpty()) {
+      // args can contain whitespace, so figure out the first word
+      String argv0 = modifiedArgv.get(0);
+      String command = ARGV_SPLITTER.split(argv0).iterator().next();
+      
+      // Automatically enable CMD.EXE use if we are executing something else besides "*.exe" file.
+      if (!command.toLowerCase().endsWith(".exe")) {
+        useShell = true;
+      }
+    } else {
+      // This is degenerate "/bin/sh -c" case. We ensure that Windows behavior is identical
+      // to the Linux - call shell that will do nothing.
+      useShell = true;
+    }
+    if (useShell) {
+      // /S - strip first and last quotes and execute everything else as is.
+      // /E:ON - enable extended command set.
+      // /V:ON - enable delayed variable expansion
+      // /D - ignore AutoRun registry entries.
+      // /C - execute command. This must be the last option before the command itself.
+      return new String[] { "CMD.EXE", "/S", "/E:ON", "/V:ON", "/D", "/C",
+          "\"" + Joiner.on(' ').join(modifiedArgv) + "\"" };
+    } else {
+      return modifiedArgv.toArray(new String[argv.size()]);
+    }
+  }
+
+  public Command build() {
+    Preconditions.checkState(system != OS.UNKNOWN, "Unidentified operating system");
+    Preconditions.checkNotNull(workingDir, "Working directory must be set");
+    Preconditions.checkState(argv.size() > 0, "At least one argument is expected");
+
+    return new Command(
+        system == OS.WINDOWS ? transformArgvForWindows() : transformArgvForLinux(),
+        env, workingDir);
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/util/CommandDescriptionForm.java b/src/main/java/com/google/devtools/build/lib/util/CommandDescriptionForm.java
new file mode 100644
index 0000000000..8d37275630
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/util/CommandDescriptionForm.java
@@ -0,0 +1,41 @@
+// Copyright 2014 Google Inc. 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.util;
+
+/**
+ * Forms in which a command can be described by {@link CommandFailureUtils#describeCommand}.
+ */
+public enum CommandDescriptionForm {
+  /**
+   * A form that is usually suitable for identifying the command but not for
+   * re-executing it.  The working directory and environment are not shown, and
+   * the arguments are truncated to a maximum of a few hundred bytes.
+   */
+  ABBREVIATED,
+
+  /**
+   * A form that is complete and suitable for a user to copy and paste into a
+   * shell.  On Linux, the command is placed in a subshell so it has no side
+   * effects on the user's shell.  On Windows, this is not implemented, but the
+   * side effects in question are less severe (no "exec").
+   */
+  COMPLETE,
+
+  /**
+   * A form that is complete and does not isolate side effects.  Suitable for
+   * launch scripts, i.e., "blaze run --script_path".
+   */
+  COMPLETE_UNISOLATED,
+}
diff --git a/src/main/java/com/google/devtools/build/lib/util/CommandFailureUtils.java b/src/main/java/com/google/devtools/build/lib/util/CommandFailureUtils.java
new file mode 100644
index 0000000000..9178f985b7
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/util/CommandFailureUtils.java
@@ -0,0 +1,252 @@
+// Copyright 2014 Google Inc. 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.util;
+
+import com.google.common.base.Preconditions;
+import com.google.common.collect.Ordering;
+
+import java.io.File;
+import java.util.Collection;
+import java.util.Comparator;
+import java.util.Map;
+
+import javax.annotation.Nullable;
+
+/**
+ * Utility methods for describing command failures.
+ * See also the CommandUtils class.
+ * Unlike that one, this class does not depend on Command;
+ * instead, it just manipulates command lines represented as
+ * Collection&lt;String&gt;.
+ */
+public class CommandFailureUtils {
+
+  // Interface that provides building blocks when describing command.
+  private interface DescribeCommandImpl {
+    void describeCommandBeginIsolate(StringBuilder message);
+    void describeCommandEndIsolate(StringBuilder message);
+    void describeCommandCwd(String cwd, StringBuilder message);
+    void describeCommandEnvPrefix(StringBuilder message);
+    void describeCommandEnvVar(StringBuilder message, Map.Entry<String, String> entry);
+    void describeCommandElement(StringBuilder message, String commandElement);
+    void describeCommandExec(StringBuilder message);
+  }
+
+  private static final class LinuxDescribeCommandImpl implements DescribeCommandImpl {
+
+    @Override
+    public void describeCommandBeginIsolate(StringBuilder message) {
+      message.append("(");
+    }
+
+    @Override
+    public void describeCommandEndIsolate(StringBuilder message) {
+      message.append(")");
+    }
+
+    @Override
+    public void describeCommandCwd(String cwd, StringBuilder message) {
+      message.append("cd ").append(ShellEscaper.escapeString(cwd)).append(" && \\\n  ");
+    }
+
+    @Override
+    public void describeCommandEnvPrefix(StringBuilder message) {
+      message.append("env - \\\n  ");
+    }
+
+    @Override
+    public void describeCommandEnvVar(StringBuilder message, Map.Entry<String, String> entry) {
+      message.append(ShellEscaper.escapeString(entry.getKey())).append('=')
+          .append(ShellEscaper.escapeString(entry.getValue())).append(" \\\n  ");
+    }
+
+    @Override
+    public void describeCommandElement(StringBuilder message, String commandElement) {
+      message.append(ShellEscaper.escapeString(commandElement));
+    }
+
+    @Override
+    public void describeCommandExec(StringBuilder message) {
+      message.append("exec ");
+    }
+  }
+
+  // TODO(bazel-team): (2010) Add proper escaping. We can't use ShellUtils.shellEscape() as it is
+  // incompatible with CMD.EXE syntax, but something else might be needed.
+  private static final class WindowsDescribeCommandImpl implements DescribeCommandImpl {
+
+    @Override
+    public void describeCommandBeginIsolate(StringBuilder message) {
+      // TODO(bazel-team): Implement this.
+    }
+
+    @Override
+    public void describeCommandEndIsolate(StringBuilder message) {
+      // TODO(bazel-team): Implement this.
+    }
+
+    @Override
+    public void describeCommandCwd(String cwd, StringBuilder message) {
+      message.append("cd ").append(cwd).append("\n");
+    }
+
+    @Override
+    public void describeCommandEnvPrefix(StringBuilder message) { }
+
+    @Override
+    public void describeCommandEnvVar(StringBuilder message, Map.Entry<String, String> entry) {
+      message.append("SET ").append(entry.getKey()).append('=')
+          .append(entry.getValue()).append("\n  ");
+    }
+
+    @Override
+    public void describeCommandElement(StringBuilder message, String commandElement) {
+      message.append(commandElement);
+    }
+
+    @Override
+    public void describeCommandExec(StringBuilder message) {
+      // TODO(bazel-team): Implement this if possible for greater efficiency.
+    }
+  }
+
+  private static final DescribeCommandImpl describeCommandImpl =
+      OS.getCurrent() == OS.WINDOWS ? new WindowsDescribeCommandImpl()
+                                    : new LinuxDescribeCommandImpl();
+
+  private CommandFailureUtils() {} // Prevent instantiation.
+
+  private static Comparator<Map.Entry<String, String>> mapEntryComparator =
+      new Comparator<Map.Entry<String, String>>() {
+        @Override
+        public int compare(Map.Entry<String, String> x, Map.Entry<String, String> y) {
+          // A map can never have two keys with the same value, so we only need to compare the keys.
+          return x.getKey().compareTo(y.getKey());
+        }
+      };
+
+  /**
+   * Construct a string that describes the command.
+   * Currently this returns a message of the form "foo bar baz",
+   * with shell meta-characters appropriately quoted and/or escaped,
+   * prefixed (if verbose is true) with an "env" command to set the environment.
+   *
+   * @param form Form of the command to generate; see the documentation of the
+   * {@link CommandDescriptionForm} values.
+   */
+  public static String describeCommand(CommandDescriptionForm form,
+      Collection<String> commandLineElements,
+      @Nullable Map<String, String> environment, @Nullable String cwd) {
+    Preconditions.checkNotNull(form);
+    final int APPROXIMATE_MAXIMUM_MESSAGE_LENGTH = 200;
+    StringBuilder message = new StringBuilder();
+    int size = commandLineElements.size();
+    int numberRemaining = size;
+    if (form == CommandDescriptionForm.COMPLETE) {
+      describeCommandImpl.describeCommandBeginIsolate(message);
+    }
+    if (form != CommandDescriptionForm.ABBREVIATED) {
+      if (cwd != null) {
+        describeCommandImpl.describeCommandCwd(cwd, message);
+      }
+      /*
+       * On Linux, insert an "exec" keyword to save a fork in "blaze run"
+       * generated scripts.  If we use "env" as a wrapper, the "exec" needs to
+       * be applied to the entire "env" invocation.
+       *
+       * On Windows, this is a no-op.
+       */
+      describeCommandImpl.describeCommandExec(message);
+      /*
+       * Java does not provide any way to invoke a subprocess with the environment variables
+       * in a specified order.  The order of environment variables in the 'environ' array
+       * (which is set by the 'envp' parameter to the execve() system call)
+       * is determined by the order of iteration on a HashMap constructed inside Java's
+       * ProcessBuilder class (in the ProcessEnvironment class), which is nondeterministic.
+       *
+       * Nevertheless, we *print* the environment variables here in sorted order, rather
+       * than in the potentially nondeterministic order that will be actually used.
+       * This is slightly dubious... in theory a process's behaviour could depend on the order
+       * of the environment variables passed to it.  (For example, the order of environment
+       * variables in the environ array affects the output of '/usr/bin/env'.)
+       * However, in practice very few processes depend on the order of the environment
+       * variables, and using a deterministic sorted order here makes Blaze's output more
+       * deterministic and easier to read.  So this seems the lesser of two evils... I think.
+       * Anyway, it's not like we have much choice... even if we wanted to, there's no way to
+       * print out the nondeterministic order that will actually be used, since there's
+       * no way to guarantee that the iteration over entrySet() here will return the same
+       * sequence as the iteration over entrySet() inside the ProcessBuilder class
+       * (in ProcessEnvironment.StringEnvironment.toEnvironmentBlock()).
+       */
+      if (environment != null) {
+        describeCommandImpl.describeCommandEnvPrefix(message);
+        for (Map.Entry<String, String> entry :
+            Ordering.from(mapEntryComparator).sortedCopy(environment.entrySet())) {
+          message.append("  ");
+          describeCommandImpl.describeCommandEnvVar(message, entry);
+        }
+      }
+    }
+    for (String commandElement : commandLineElements) {
+      if (form == CommandDescriptionForm.ABBREVIATED &&
+          message.length() + commandElement.length() > APPROXIMATE_MAXIMUM_MESSAGE_LENGTH) {
+        message.append(
+            " ... (remaining " + numberRemaining + " argument(s) skipped)");
+        break;
+      } else {
+        if (numberRemaining < size) {
+          message.append(' ');
+        }
+        describeCommandImpl.describeCommandElement(message, commandElement);
+        numberRemaining--;
+      }
+    }
+    if (form == CommandDescriptionForm.COMPLETE) {
+      describeCommandImpl.describeCommandEndIsolate(message);
+    }
+    return message.toString();
+  }
+
+  /**
+   * Construct an error message that describes a failed command invocation.
+   * Currently this returns a message of the form "error executing command foo
+   * bar baz".
+   */
+  public static String describeCommandError(boolean verbose,
+                                            Collection<String> commandLineElements,
+                                            Map<String, String> env, String cwd) {
+    CommandDescriptionForm form = verbose
+        ? CommandDescriptionForm.COMPLETE
+        : CommandDescriptionForm.ABBREVIATED;
+    return "error executing command " + (verbose ? "\n  " : "")
+        + describeCommand(form, commandLineElements, env, cwd);
+  }
+
+  /**
+   * Construct an error message that describes a failed command invocation.
+   * Currently this returns a message of the form "foo failed: error executing
+   * command /dir/foo bar baz".
+   */
+  public static String describeCommandFailure(boolean verbose,
+                                              Collection<String> commandLineElements,
+                                              Map<String, String> env, String cwd) {
+    String commandName = commandLineElements.iterator().next();
+    // Extract the part of the command name after the last "/", if any.
+    String shortCommandName = new File(commandName).getName();
+    return shortCommandName + " failed: " +
+        describeCommandError(verbose, commandLineElements, env, cwd);
+  }
+
+}
diff --git a/src/main/java/com/google/devtools/build/lib/util/CommandUtils.java b/src/main/java/com/google/devtools/build/lib/util/CommandUtils.java
new file mode 100644
index 0000000000..e6c0011f34
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/util/CommandUtils.java
@@ -0,0 +1,88 @@
+// Copyright 2014 Google Inc. 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.util;
+
+import com.google.devtools.build.lib.shell.AbnormalTerminationException;
+import com.google.devtools.build.lib.shell.Command;
+import com.google.devtools.build.lib.shell.CommandException;
+import com.google.devtools.build.lib.shell.CommandResult;
+
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.Map;
+
+/**
+ * Utility methods relating to the {@link Command} class.
+ */
+public class CommandUtils {
+
+  private CommandUtils() {} // Prevent instantiation.
+
+  private static Collection<String> commandLine(Command command) {
+    return Arrays.asList(command.getCommandLineElements());
+  }
+
+  private static Map<String, String> env(Command command) {
+    return command.getEnvironmentVariables();
+  }
+
+  private static String cwd(Command command) {
+    return command.getWorkingDirectory() == null ? null : command.getWorkingDirectory().getPath();
+  }
+
+  /**
+   * Construct an error message that describes a failed command invocation.
+   * Currently this returns a message of the form "error executing command foo
+   * bar baz".
+   */
+  public static String describeCommandError(boolean verbose, Command command) {
+    return CommandFailureUtils.describeCommandError(verbose, commandLine(command), env(command),
+                                                    cwd(command));
+  }
+
+  /**
+   * Construct an error message that describes a failed command invocation.
+   * Currently this returns a message of the form "foo failed: error executing
+   * command /dir/foo bar baz".
+   */
+  public static String describeCommandFailure(boolean verbose, Command command) {
+    return CommandFailureUtils.describeCommandFailure(verbose, commandLine(command), env(command),
+                                                      cwd(command));
+  }
+
+  /**
+   * Construct an error message that describes a failed command invocation.
+   * Currently this returns a message of the form "foo failed: error executing
+   * command /dir/foo bar baz: exception message", with the
+   * command's stdout and stderr output appended if available.
+   */
+  public static String describeCommandFailure(boolean verbose, CommandException exception) {
+    String message = describeCommandFailure(verbose, exception.getCommand()) + ": "
+        + exception.getMessage();
+    if (exception instanceof AbnormalTerminationException) {
+      CommandResult result = ((AbnormalTerminationException) exception).getResult();
+      try {
+        return message + "\n" +
+            new String(result.getStdout()) +
+            new String(result.getStderr());
+      } catch (IllegalStateException e) {
+        // This can happen if the command didn't save stdout/stderr,
+        // so ignore this exception and fall through to the ordinary case.
+      }
+    }
+    return message;
+  }
+
+}
diff --git a/src/main/java/com/google/devtools/build/lib/util/CompactStringIndexer.java b/src/main/java/com/google/devtools/build/lib/util/CompactStringIndexer.java
new file mode 100644
index 0000000000..698758dba6
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/util/CompactStringIndexer.java
@@ -0,0 +1,546 @@
+// Copyright 2014 Google Inc. 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.util;
+
+import static java.nio.charset.StandardCharsets.UTF_8;
+
+import com.google.common.base.Preconditions;
+import com.google.common.collect.Lists;
+import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadCompatible;
+import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
+
+import java.util.ArrayList;
+
+/**
+ * Provides memory-efficient bidirectional mapping String <-> unique integer.
+ * Uses byte-wise compressed prefix trie internally.
+ * <p>
+ * Class allows index retrieval for the given string, addition of the new
+ * index and string retrieval for the given index. It also allows efficient
+ * serialization of the internal data structures.
+ * <p>
+ * Internally class stores list of nodes with each node containing byte[]
+ * representation of compressed trie node:
+ * <pre>
+ * varint32 parentIndex;  // index of the parent node
+ * varint32 keylen;       // length of the node key
+ * byte[keylen] key;      // node key data
+ * repeated jumpEntry {   // Zero or more jump entries, referencing child nodes
+ *   byte key             // jump key (first byte of the child node key)
+ *   varint32 nodeIndex   // child index
+ * }
+ * <p>
+ * Note that jumpEntry key byte is actually duplicated in the child node
+ * instance. This is done to improve performance of the index->string
+ * lookup (so we can avoid jump table parsing during this lookup).
+ * <p>
+ * Root node of the trie must have parent id pointing to itself.
+ * <p>
+ * TODO(bazel-team): (2010) Consider more fine-tuned locking mechanism - e.g.
+ * distinguishing between read and write locks.
+ */
+@ThreadSafe
+public class CompactStringIndexer extends AbstractIndexer {
+
+  private static final int NOT_FOUND = -1;
+
+  private ArrayList<byte[]> nodes;  // Compressed prefix trie nodes.
+  private int rootId;               // Root node id.
+
+  /*
+   * Creates indexer instance.
+   */
+  public CompactStringIndexer (int expectedCapacity) {
+    Preconditions.checkArgument(expectedCapacity > 0);
+    nodes = Lists.newArrayListWithExpectedSize(expectedCapacity);
+    rootId = NOT_FOUND;
+  }
+
+  /**
+   * Allocates new node index. Must be called only from
+   * synchronized methods.
+   */
+  private int allocateIndex() {
+    nodes.add(null);
+    return nodes.size() - 1;
+  }
+
+  /**
+   * Replaces given node record with the new one. Must be called only from
+   * synchronized methods.
+   * <p>
+   * Subclasses can override this method to be notified when an update actually
+   * takes place.
+   */
+  @ThreadCompatible
+  protected void updateNode(int index, byte[] content) {
+    nodes.set(index, content);
+  }
+
+  /**
+   * Returns parent id for the given node content.
+   *
+   * @return parent node id
+   */
+  private int getParentId(byte[] content) {
+    int[] intHolder = new int[1];
+    VarInt.getVarInt(content, 0, intHolder);
+    return intHolder[0];
+  }
+
+  /**
+   * Creates new node using specified key suffix. Must be called from
+   * synchronized methods.
+   *
+   * @param parentNode parent node id
+   * @param key original key that is being added to the indexer
+   * @param offset node key offset in the original key.
+   *
+   * @return new node id corresponding to the given key
+   */
+  private int createNode(int parentNode, byte[] key, int offset) {
+    int index = allocateIndex();
+
+    int len = key.length - offset;
+    Preconditions.checkState(len >= 0);
+
+    // Content consists of parent id, key length and key. There are no jump records.
+    byte[] content = new byte[VarInt.varIntSize(parentNode) + VarInt.varIntSize(len) + len];
+    // Add parent id.
+    int contentOffset = VarInt.putVarInt(parentNode, content, 0);
+    // Add node key length.
+    contentOffset = VarInt.putVarInt(len, content, contentOffset);
+    // Add node key content.
+    System.arraycopy(key, offset, content, contentOffset, len);
+
+    updateNode(index, content);
+    return index;
+  }
+
+  /**
+   * Updates jump entry index in the given node.
+   *
+   * @param node node id to update
+   * @param oldIndex old jump entry index
+   * @param newIndex updated jump entry index
+   */
+  private void updateJumpEntry(int node, int oldIndex, int newIndex) {
+    byte[] content = nodes.get(node);
+    int[] intHolder = new int[1];
+    int offset = VarInt.getVarInt(content, 0, intHolder); // parent id
+    offset = VarInt.getVarInt(content, offset, intHolder); // key length
+    offset += intHolder[0]; // Offset now points to the first jump entry.
+    while (offset < content.length) {
+      int next = VarInt.getVarInt(content, offset + 1, intHolder); // jump index
+      if (intHolder[0] == oldIndex) {
+        // Substitute oldIndex value with newIndex.
+        byte[] newContent =
+            new byte[content.length + VarInt.varIntSize(newIndex) - VarInt.varIntSize(oldIndex)];
+        System.arraycopy(content, 0, newContent, 0, offset + 1);
+        offset = VarInt.putVarInt(newIndex, newContent, offset + 1);
+        System.arraycopy(content, next, newContent, offset, content.length - next);
+        updateNode(node, newContent);
+        return;
+      } else {
+        offset = next;
+      }
+    }
+    StringBuilder builder = new StringBuilder().append("Index ").append(oldIndex)
+        .append(" is not present in the node ").append(node).append(", ");
+    dumpNodeContent(builder, content);
+    throw new IllegalArgumentException(builder.toString());
+  }
+
+  /**
+   * Creates new branch node content at the predefined location, splitting
+   * prefix from the given node and optionally adding another child node
+   * jump entry.
+   *
+   * @param originalNode node that will be split
+   * @param newBranchNode new branch node id
+   * @param splitOffset offset at which to split original node key
+   * @param indexKey optional additional jump key
+   * @param childIndex optional additional jump index. Optional jump entry will
+   *                   be skipped if this index is set to NOT_FOUND.
+   */
+  private void createNewBranchNode(int originalNode, int newBranchNode, int splitOffset,
+      byte indexKey, int childIndex) {
+    byte[] content = nodes.get(originalNode);
+    int[] intHolder = new int[1];
+    int keyOffset = VarInt.getVarInt(content, 0, intHolder); // parent id
+
+    // If original node is a root node, new branch node will become new root. So set parent id
+    // appropriately (for root node it is set to the node's own id).
+    int parentIndex = (originalNode == intHolder[0] ? newBranchNode : intHolder[0]);
+
+    keyOffset = VarInt.getVarInt(content, keyOffset, intHolder); // key length
+    Preconditions.checkState(intHolder[0] >= splitOffset);
+    // Calculate new content size.
+    int newSize = VarInt.varIntSize(parentIndex)
+        + VarInt.varIntSize(splitOffset) + splitOffset
+        + 1 + VarInt.varIntSize(originalNode)
+        + (childIndex != NOT_FOUND ? 1 + VarInt.varIntSize(childIndex) : 0);
+    // New content consists of parent id, new key length, truncated key and two jump records.
+    byte[] newContent = new byte[newSize];
+    // Add parent id.
+    int contentOffset = VarInt.putVarInt(parentIndex, newContent, 0);
+    // Add adjusted key length.
+    contentOffset = VarInt.putVarInt(splitOffset, newContent, contentOffset);
+    // Add truncated key content and first jump key.
+    System.arraycopy(content, keyOffset, newContent, contentOffset, splitOffset + 1);
+    // Add index for the first jump key.
+    contentOffset = VarInt.putVarInt(originalNode, newContent, contentOffset + splitOffset + 1);
+    // If requested, add additional jump entry.
+    if (childIndex != NOT_FOUND) {
+      // Add second jump key.
+      newContent[contentOffset] = indexKey;
+      // Add index for the second jump key.
+      VarInt.putVarInt(childIndex, newContent, contentOffset + 1);
+    }
+    updateNode(newBranchNode, newContent);
+  }
+
+  /**
+   * Inject newly created branch node into the trie data structure. Method
+   * will update parent node jump entry to point to the new branch node (or
+   * will update root id if branch node becomes new root) and will truncate
+   * key prefix from the original node that was split (that prefix now
+   * resides in the branch node).
+   *
+   * @param originalNode node that will be split
+   * @param newBranchNode new branch node id
+   * @param commonPrefixLength how many bytes should be split into the new branch node.
+   */
+  private void injectNewBranchNode(int originalNode, int newBranchNode, int commonPrefixLength) {
+    byte[] content = nodes.get(originalNode);
+
+    int parentId = getParentId(content);
+    if (originalNode == parentId) {
+      rootId = newBranchNode; // update root index
+    } else {
+      updateJumpEntry(parentId, originalNode, newBranchNode);
+    }
+
+    // Truncate prefix from the original node and set its parent to the our new branch node.
+    int[] intHolder = new int[1];
+    int suffixOffset = VarInt.getVarInt(content, 0, intHolder); // parent id
+    suffixOffset = VarInt.getVarInt(content, suffixOffset, intHolder); // key length
+    int len = intHolder[0] - commonPrefixLength;
+    Preconditions.checkState(len >= 0);
+    suffixOffset += commonPrefixLength;
+    // New content consists of parent id, new key length and duplicated key suffix.
+    byte[] newContent = new byte[VarInt.varIntSize(newBranchNode) + VarInt.varIntSize(len) +
+        (content.length - suffixOffset)];
+    // Add parent id.
+    int contentOffset = VarInt.putVarInt(newBranchNode, newContent, 0);
+    // Add new key length.
+    contentOffset = VarInt.putVarInt(len, newContent, contentOffset);
+    // Add key and jump table.
+    System.arraycopy(content, suffixOffset, newContent, contentOffset,
+        content.length - suffixOffset);
+    updateNode(originalNode, newContent);
+  }
+
+  /**
+   * Adds new child node (that uses specified key suffix) to the given
+   * current node.
+   * Example:
+   * <pre>
+   * Had "ab". Adding "abcd".
+   *
+   *           1:"ab",'c'->2
+   * 1:"ab" ->     \
+   *              2:"cd"
+   * </pre>
+   */
+  private int addChildNode(int parentNode, byte[] key, int keyOffset) {
+    int child = createNode(parentNode, key, keyOffset);
+
+    byte[] content = nodes.get(parentNode);
+    // Add jump table entry to the parent node.
+    int entryOffset = content.length;
+    // New content consists of original content and additional jump record.
+    byte[] newContent = new byte[entryOffset + 1 + VarInt.varIntSize(child)];
+    // Copy original content.
+    System.arraycopy(content, 0, newContent, 0, entryOffset);
+    // Add jump key.
+    newContent[entryOffset] = key[keyOffset];
+    // Add jump index.
+    VarInt.putVarInt(child, newContent, entryOffset + 1);
+
+    updateNode(parentNode, newContent);
+    return child;
+  }
+
+  /**
+   * Splits node into two at the specified offset.
+   * Example:
+   * <pre>
+   * Had "abcd". Adding "ab".
+   *
+   *             2:"ab",'c'->1
+   * 1:"abcd" ->     \
+   *                1:"cd"
+   * </pre>
+   */
+  private int splitNodeSuffix(int nodeToSplit, int commonPrefixLength) {
+    int newBranchNode = allocateIndex();
+    // Create new node with truncated key.
+    createNewBranchNode(nodeToSplit, newBranchNode, commonPrefixLength, (byte) 0, NOT_FOUND);
+    injectNewBranchNode(nodeToSplit, newBranchNode, commonPrefixLength);
+
+    return newBranchNode;
+  }
+
+  /**
+   * Splits node into two at the specified offset and adds another leaf.
+   * Example:
+   * <pre>
+   * Had "abcd". Adding "abef".
+   *
+   *                3:"ab",'c'->1,'e'->2
+   * 1:"abcd" ->    /     \
+   *             1:"cd"   2:"ef"
+   * </pre>
+   */
+  private int addBranch(int nodeToSplit, byte[] key, int offset, int commonPrefixLength) {
+    int newBranchNode = allocateIndex();
+    int child = createNode(newBranchNode, key, offset + commonPrefixLength);
+    // Create new node with the truncated key and reference to the new child node.
+    createNewBranchNode(nodeToSplit, newBranchNode, commonPrefixLength,
+        key[offset + commonPrefixLength], child);
+    injectNewBranchNode(nodeToSplit, newBranchNode, commonPrefixLength);
+
+    return child;
+  }
+
+  private int findOrCreateIndexInternal(int node, byte[] key, int offset,
+      boolean createIfNotFound) {
+    byte[] content = nodes.get(node);
+    int[] intHolder = new int[1];
+    int contentOffset = VarInt.getVarInt(content, 0, intHolder); // parent id
+    contentOffset = VarInt.getVarInt(content, contentOffset, intHolder); // key length
+    int skyKeyLen = intHolder[0];
+    int remainingKeyLen = key.length - offset;
+    int minKeyLen = remainingKeyLen > skyKeyLen ? skyKeyLen : remainingKeyLen;
+
+    // Compare given key/offset content with the node key. Skip first key byte for recursive
+    // calls - this byte is equal to the byte in the jump entry and was already compared.
+    for (int i = (offset > 0 ? 1 : 0); i < minKeyLen; i++) { // compare key
+      if (key[offset + i] != content[contentOffset + i]) {
+        // Mismatch found somewhere in the middle of the node key. If requested, node
+        // should be split and another leaf added for the new key.
+        return createIfNotFound ? addBranch(node, key, offset, i) : NOT_FOUND;
+      }
+    }
+
+    if (remainingKeyLen > minKeyLen) {
+      // Node key matched portion of the key - find appropriate jump entry. If found - recursion.
+      // If not - mismatch (we will add new child node if requested).
+      contentOffset += skyKeyLen;
+      while (contentOffset < content.length) {
+        if (key[offset + skyKeyLen] == content[contentOffset]) {  // compare index value
+          VarInt.getVarInt(content, contentOffset + 1, intHolder);
+          // Found matching jump entry - recursively compare the child.
+          return findOrCreateIndexInternal(intHolder[0], key, offset + skyKeyLen,
+              createIfNotFound);
+        } else {
+          // Jump entry key does not match. Skip rest of the entry data.
+          contentOffset = VarInt.getVarInt(content, contentOffset + 1, intHolder);
+        }
+      }
+      // There are no matching jump entries - report mismatch or create a new leaf if necessary.
+      return createIfNotFound ? addChildNode(node, key, offset + skyKeyLen) : NOT_FOUND;
+    } else if (skyKeyLen > minKeyLen) {
+      // Key suffix is a subset of the node key. Report mismatch or split the node if requested).
+      return createIfNotFound ? splitNodeSuffix(node, minKeyLen) : NOT_FOUND;
+    } else {
+      // Node key exactly matches key suffix - return associated index value.
+      return node;
+    }
+  }
+
+  private synchronized int findOrCreateIndex(byte[] key, boolean createIfNotFound) {
+    if (rootId == NOT_FOUND) {
+      // Root node does not seem to exist - create it if needed.
+      if (createIfNotFound) {
+        rootId = createNode(0, key, 0);
+        Preconditions.checkState(rootId == 0);
+        return 0;
+      } else {
+        return NOT_FOUND;
+      }
+    }
+    return findOrCreateIndexInternal(rootId, key, 0, createIfNotFound);
+  }
+
+  private byte[] reconstructKeyInternal(int node, int suffixSize) {
+    byte[] content = nodes.get(node);
+    Preconditions.checkNotNull(content);
+    int[] intHolder = new int[1];
+    int contentOffset = VarInt.getVarInt(content, 0, intHolder); // parent id
+    int parentNode = intHolder[0];
+    contentOffset = VarInt.getVarInt(content, contentOffset, intHolder); // key length
+    int len = intHolder[0];
+    byte[] key;
+    if (node != parentNode) {
+      // We haven't reached root node yet. Make a recursive call, adjusting suffix length.
+      key = reconstructKeyInternal(parentNode, suffixSize + len);
+    } else {
+      // We are in a root node. Finally allocate array for the key. It will be filled up
+      // on our way back from recursive call tree.
+      key = new byte[suffixSize + len];
+    }
+    // Fill appropriate portion of the full key with the node key content.
+    System.arraycopy(content, contentOffset, key, key.length - suffixSize - len, len);
+    return key;
+  }
+
+  private byte[] reconstructKey(int node) {
+    return reconstructKeyInternal(node, 0);
+  }
+
+  /* (non-Javadoc)
+   * @see com.google.devtools.build.lib.util.StringIndexer#clear()
+   */
+  @Override
+  public synchronized void clear() {
+    nodes.clear();
+  }
+
+  /* (non-Javadoc)
+   * @see com.google.devtools.build.lib.util.StringIndexer#size()
+   */
+  @Override
+  public synchronized int size() {
+    return nodes.size();
+  }
+
+  protected int getOrCreateIndexForBytes(byte[] bytes) {
+    return findOrCreateIndex(bytes, true);
+  }
+
+  protected synchronized boolean addBytes(byte[] bytes) {
+    int count = nodes.size();
+    int index = getOrCreateIndexForBytes(bytes);
+    return index >= count;
+  }
+
+  protected int getIndexForBytes(byte[] bytes) {
+    return findOrCreateIndex(bytes, false);
+  }
+
+  /* (non-Javadoc)
+   * @see com.google.devtools.build.lib.util.StringIndexer#getOrCreateIndex(java.lang.String)
+   */
+  @Override
+  public int getOrCreateIndex(String s) {
+    return getOrCreateIndexForBytes(string2bytes(s));
+  }
+
+  /* (non-Javadoc)
+   * @see com.google.devtools.build.lib.util.StringIndexer#getIndex(java.lang.String)
+   */
+  @Override
+  public int getIndex(String s) {
+    return getIndexForBytes(string2bytes(s));
+  }
+
+  /* (non-Javadoc)
+   * @see com.google.devtools.build.lib.util.StringIndexer#addString(java.lang.String)
+   */
+  @Override
+  public boolean addString(String s) {
+    return addBytes(string2bytes(s));
+  }
+
+  protected synchronized byte[] getBytesForIndex(int i) {
+    Preconditions.checkArgument(i >= 0);
+    if (i >= nodes.size()) {
+      return null;
+    }
+    return reconstructKey(i);
+  }
+
+  /* (non-Javadoc)
+   * @see com.google.devtools.build.lib.util.StringIndexer#getStringForIndex(int)
+   */
+  @Override
+  public String getStringForIndex(int i) {
+    byte[] bytes = getBytesForIndex(i);
+    return bytes != null ? bytes2string(bytes) : null;
+  }
+
+  private void dumpNodeContent(StringBuilder builder, byte[] content) {
+    int[] intHolder = new int[1];
+    int offset = VarInt.getVarInt(content, 0, intHolder);
+    builder.append("parent: ").append(intHolder[0]);
+    offset = VarInt.getVarInt(content, offset, intHolder);
+    int len = intHolder[0];
+    builder.append(", len: ").append(len).append(", key: \"")
+        .append(new String(content, offset, len, UTF_8)).append('"');
+    offset += len;
+    while (offset < content.length) {
+      builder.append(", '").append(new String(content, offset, 1, UTF_8)).append("': ");
+      offset = VarInt.getVarInt(content, offset + 1, intHolder);
+      builder.append(intHolder[0]);
+    }
+    builder.append(", size: ").append(content.length);
+  }
+
+  private int dumpContent(StringBuilder builder, int node, int indent, boolean[] seen) {
+    for(int i = 0; i < indent; i++) {
+      builder.append("  ");
+    }
+    builder.append(node).append(": ");
+    if (node >= nodes.size()) {
+      builder.append("OUT_OF_BOUNDS\n");
+      return 0;
+    } else if (seen[node]) {
+      builder.append("ALREADY_SEEN\n");
+      return 0;
+    }
+    seen[node] = true;
+    byte[] content = nodes.get(node);
+    if (content == null) {
+      builder.append("NULL\n");
+      return 0;
+    }
+    dumpNodeContent(builder, content);
+    builder.append("\n");
+    int contentSize = content.length;
+
+    int[] intHolder = new int[1];
+    int contentOffset = VarInt.getVarInt(content, 0, intHolder); // parent id
+    contentOffset = VarInt.getVarInt(content, contentOffset, intHolder); // key length
+    contentOffset += intHolder[0];
+    while (contentOffset < content.length) {
+      contentOffset = VarInt.getVarInt(content, contentOffset + 1, intHolder);
+      contentSize += dumpContent(builder, intHolder[0], indent + 1, seen);
+    }
+    return contentSize;
+  }
+
+  @Override
+  public synchronized String toString() {
+    StringBuilder builder = new StringBuilder();
+    builder.append("size = ").append(nodes.size()).append("\n");
+    if (nodes.size() > 0) {
+      int contentSize = dumpContent(builder, rootId, 0, new boolean[nodes.size()]);
+      builder.append("contentSize = ").append(contentSize).append("\n");
+    }
+    return builder.toString();
+  }
+
+}
diff --git a/src/main/java/com/google/devtools/build/lib/util/DependencySet.java b/src/main/java/com/google/devtools/build/lib/util/DependencySet.java
new file mode 100644
index 0000000000..788037d8a0
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/util/DependencySet.java
@@ -0,0 +1,225 @@
+// Copyright 2014 Google Inc. 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.util;
+
+import com.google.common.base.Preconditions;
+import com.google.devtools.build.lib.vfs.FileSystemUtils;
+import com.google.devtools.build.lib.vfs.Path;
+import com.google.devtools.build.lib.vfs.PathFragment;
+
+import java.io.IOException;
+import java.io.PrintStream;
+import java.nio.charset.StandardCharsets;
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.regex.Matcher;
+import java.util.regex.Pattern;
+
+/**
+ * Representation of a set of file dependencies for a given output file. There
+ * are generally one input dependency and a bunch of include dependencies. The
+ * files are stored as {@code PathFragment}s and may be relative or absolute.
+ * <p>
+ * The serialized format read and written is equivalent and compatible with the
+ * ".d" file produced by the -MM for a given out (.o) file.
+ * <p>
+ * The file format looks like:
+ *
+ * <pre>
+ * {outfile}:  \
+ *  {infile} \
+ *   {include} \
+ *   ... \
+ *   {include}
+ * </pre>
+ *
+ * @see "http://gcc.gnu.org/onlinedocs/gcc-4.2.1/gcc/Preprocessor-Options.html#Preprocessor-Options"
+ */
+public final class DependencySet {
+
+  private static final Pattern DOTD_MERGED_LINE_SEPARATOR = Pattern.compile("\\\\[\n\r]+");
+  private static final Pattern DOTD_LINE_SEPARATOR = Pattern.compile("[\n\r]+");
+  private static final Pattern DOTD_DEP = Pattern.compile("(?:[^\\s\\\\]++|\\\\ |\\\\)+");
+
+  /**
+   * The set of dependent files that this DependencySet embodies. May be
+   * relative or absolute PathFragments.  A tree set is used to ensure that we
+   * write them out in a consistent order.
+   */
+  private final Collection<PathFragment> dependencies = new ArrayList<>();
+
+  private final Path root;
+  private String outputFileName;
+
+  /**
+   * Get output file name for which dependencies are included in this DependencySet.
+   */
+  public String getOutputFileName() {
+    return outputFileName;
+  }
+
+  public void setOutputFileName(String outputFileName) {
+    this.outputFileName = outputFileName;
+  }
+  
+  /**
+   * Constructs a new empty DependencySet instance.
+   */
+  public DependencySet(Path root) {
+    this.root = root;
+  }
+
+  /**
+   * Gets an unmodifiable view of the set of dependencies in PathFragment form
+   * from this DependencySet instance.
+   */
+  public Collection<PathFragment> getDependencies() {
+    return Collections.unmodifiableCollection(dependencies);
+  }
+
+  /**
+   * Adds a given collection of dependencies in Path form to this DependencySet
+   * instance. Paths are converted to root-relative
+   */
+  public void addDependencies(Collection<Path> deps) {
+    for (Path d : deps) {
+      addDependency(d.relativeTo(root));
+    }
+  }
+
+  /**
+   * Adds a given dependency in PathFragment form to this DependencySet
+   * instance.
+   */
+  public void addDependency(PathFragment dep) {
+    dependencies.add(Preconditions.checkNotNull(dep));
+  }
+
+  /**
+   * Reads a dotd file into this DependencySet instance.
+   */
+  public DependencySet read(Path dotdFile) throws IOException {
+    return process(FileSystemUtils.readContent(dotdFile));
+  }
+
+  /**
+   * Parses a .d file.
+   *
+   * <p>Performance-critical! In large C++ builds there are lots of .d files to read, and some of
+   * them reach into hundreds of kilobytes.
+   */
+  public DependencySet process(byte[] content) {
+    // true if there is a CR in the input.
+    boolean cr = content.length > 0 && content[0] == '\r';
+    // true if there is more than one line in the input, not counting \-wrapped lines.
+    boolean multiline = false;
+
+    byte prevByte = ' ';
+    for (int i = 1; i < content.length; i++) {
+      byte b = content[i];
+      if (cr || b == '\r') {
+        // CR found, abort since our little loop here does not deal with CR/LFs.
+        cr = true;
+        break;
+      }
+      if (b == '\n') {
+        // Merge lines wrapped using backslashes.
+        if (prevByte == '\\') {
+          content[i] = ' ';
+          content[i - 1] = ' ';
+        } else {
+          multiline = true;
+        }
+      }
+      prevByte = b;
+    }
+
+    if (!cr && content.length > 0 && content[content.length - 1] == '\n') {
+      content[content.length - 1] = ' ';
+    }
+
+    String s = new String(content, StandardCharsets.UTF_8);
+    if (cr) {
+      s = DOTD_MERGED_LINE_SEPARATOR.matcher(s).replaceAll(" ").trim();
+      multiline = true;
+    }
+    return process(s, multiline);
+  }
+
+  private DependencySet process(String contents, boolean multiline) {
+    String[] lines;
+    if (!multiline) {
+      // Microoptimization: skip the usually unnecessary expensive-ish splitting step if there is
+      // only one target. This saves about 20% of CPU time.
+      lines = new String[] { contents };
+    } else {
+      lines = DOTD_LINE_SEPARATOR.split(contents);
+    }
+
+    for (String line : lines) {
+      // Split off output file name.
+      int pos = line.indexOf(':');
+      if (pos == -1) {
+        continue;
+      }
+      outputFileName = line.substring(0, pos);
+      
+      String deps = line.substring(pos + 1);
+
+      Matcher m = DOTD_DEP.matcher(deps);
+      while (m.find()) {
+        String token = m.group();
+        // Process escaped spaces.
+        if (token.contains("\\ ")) {
+          token = token.replace("\\ ", " ");
+        }
+        dependencies.add(new PathFragment(token).normalize());
+      }
+    }
+    return this;
+  }
+
+  /**
+   * Writes this DependencySet object for a specified output file under the root
+   * dir, and with a given suffix.
+   */
+  public void write(Path outFile, String suffix) throws IOException {
+    Path dotdFile =
+        outFile.getRelative(FileSystemUtils.replaceExtension(outFile.asFragment(), suffix));
+
+    PrintStream out = new PrintStream(dotdFile.getOutputStream());
+    try {
+      out.print(outFile.relativeTo(root) + ": ");
+      for (PathFragment d : dependencies) {
+        out.print(" \\\n  " + d.getPathString());  // should already be root relative
+      }
+      out.println();
+    } finally {
+      out.close();
+    }
+  }
+
+  @Override
+  public boolean equals(Object other) {
+    return other instanceof DependencySet
+        && ((DependencySet) other).dependencies.equals(dependencies);
+  }
+
+  @Override
+  public int hashCode() {
+    return dependencies.hashCode();
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/util/ExitCode.java b/src/main/java/com/google/devtools/build/lib/util/ExitCode.java
new file mode 100644
index 0000000000..83075381d3
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/util/ExitCode.java
@@ -0,0 +1,181 @@
+// Copyright 2014 Google Inc. 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.util;
+
+import com.google.common.base.Objects;
+
+import java.util.Collection;
+import java.util.HashMap;
+
+/**
+ *  <p>Anything marked FAILURE is generally from a problem with the source code
+ *  under consideration.  In these cases, a re-run in an identical client should
+ *  produce an identical return code all things being constant.
+ *
+ *  <p>Anything marked as an ERROR is generally a problem unrelated to the
+ *  source code itself.  It is either something wrong with the user's command
+ *  line or the user's machine or environment.
+ *
+ *  <p>Note that these exit codes should be kept consistent with the codes
+ *  returned by Blaze's launcher in //devtools/blaze/main:blaze.cc
+ */
+public class ExitCode {
+  // Tracks all exit codes defined here and elsewhere in Bazel.
+  private static final HashMap<Integer, ExitCode> exitCodeRegistry = new HashMap<>();
+
+  public static final ExitCode SUCCESS = ExitCode.create(0, "SUCCESS");
+  public static final ExitCode BUILD_FAILURE = ExitCode.create(1, "BUILD_FAILURE");
+  public static final ExitCode PARSING_FAILURE = ExitCode.createUnregistered(1, "PARSING_FAILURE");
+  public static final ExitCode COMMAND_LINE_ERROR = ExitCode.create(2, "COMMAND_LINE_ERROR");
+  public static final ExitCode TESTS_FAILED = ExitCode.create(3, "TESTS_FAILED");
+  public static final ExitCode PARTIAL_ANALYSIS_FAILURE =
+      ExitCode.createUnregistered(3, "PARTIAL_ANALYSIS_FAILURE");
+  public static final ExitCode NO_TESTS_FOUND = ExitCode.create(4, "NO_TESTS_FOUND");
+  public static final ExitCode RUN_FAILURE = ExitCode.create(6, "RUN_FAILURE");
+  public static final ExitCode ANALYSIS_FAILURE = ExitCode.create(7, "ANALYSIS_FAILURE");
+  public static final ExitCode INTERRUPTED = ExitCode.create(8, "INTERRUPTED");
+  public static final ExitCode OOM_ERROR = ExitCode.createInfrastructureFailure(33, "OOM_ERROR");
+  public static final ExitCode LOCAL_ENVIRONMENTAL_ERROR =
+      ExitCode.createInfrastructureFailure(36, "LOCAL_ENVIRONMENTAL_ERROR");
+  public static final ExitCode BLAZE_INTERNAL_ERROR =
+      ExitCode.createInfrastructureFailure(37, "BLAZE_INTERNAL_ERROR");
+  public static final ExitCode RESERVED = ExitCode.createInfrastructureFailure(40, "RESERVED");
+  /*
+    exit codes [50..60] and 253 are reserved for site specific wrappers to Bazel.
+   */
+
+  /**
+   * Creates and returns an ExitCode.  Requires a unique exit code number.
+   *
+   * @param code the int value for this exit code
+   * @param name a human-readable description
+   */
+  public static ExitCode create(int code, String name) {
+    return new ExitCode(code, name, /*infrastructureFailure=*/false, /*register=*/true);
+  }
+
+  /**
+   * Creates and returns an ExitCode that represents an infrastructure failure.
+   *
+   * @param code the int value for this exit code
+   * @param name a human-readable description
+   */
+  public static ExitCode createInfrastructureFailure(int code, String name) {
+    return new ExitCode(code, name, /*infrastructureFailure=*/true, /*register=*/true);
+  }
+
+  /**
+   * Creates and returns an ExitCode that has the same numeric code as another ExitCode. This is to
+   * allow the duplicate error codes listed above to be registered, but is private to prevent other
+   * users from creating duplicate error codes in the future.
+   *
+   * @param code the int value for this exit code
+   * @param name a human-readable description
+   */
+  private static ExitCode createUnregistered(int code, String name) {
+    return new ExitCode(code, name, /*infrastructureFailure=*/false, /*register=*/false);
+  }
+
+  /**
+   * Add the given exit code to the registry.
+   *
+   * @param exitCode the exit code to register
+   * @throws IllegalStateException if the numeric exit code is already in the registry.
+   */
+  private static void register(ExitCode exitCode) {
+    synchronized (exitCodeRegistry) {
+      int codeNum = exitCode.getNumericExitCode();
+      if (exitCodeRegistry.containsKey(codeNum)) {
+        throw new IllegalStateException(
+            "Exit code " + codeNum + " (" + exitCode.name + ") already registered");
+      }
+      exitCodeRegistry.put(codeNum, exitCode);
+    }
+  }
+
+  /**
+   * Returns all registered ExitCodes.
+   */
+  public static Collection<ExitCode> values() {
+    synchronized (exitCodeRegistry) {
+      return exitCodeRegistry.values();
+    }
+  }
+
+  private final int numericExitCode;
+  private final String name;
+  private final boolean infrastructureFailure;
+
+  /**
+   * Whenever a new exit code is created, it is registered (to prevent exit codes with identical
+   * numeric codes from being created).  However, there are some exit codes in this file that have
+   * duplicate numeric codes, so these are not registered.
+   */
+  private ExitCode(int exitCode, String name, boolean infrastructureFailure, boolean register) {
+    this.numericExitCode = exitCode;
+    this.name = name;
+    this.infrastructureFailure = infrastructureFailure;
+    if (register) {
+      ExitCode.register(this);
+    }
+  }
+
+  @Override
+  public int hashCode() {
+    return Objects.hashCode(numericExitCode, name, infrastructureFailure);
+  }
+
+  @Override
+  public boolean equals(Object object) {
+    if (object instanceof ExitCode) {
+      ExitCode that = (ExitCode) object;
+      return this.numericExitCode == that.numericExitCode
+          && this.name.equals(that.name)
+          && this.infrastructureFailure == that.infrastructureFailure;
+    }
+    return false;
+  }
+
+  /**
+   * Returns the human-readable name for this exit code.  Not guaranteed to be stable, use the
+   * numeric exit code for that.
+   */
+  @Override
+  public String toString() {
+    return name;
+  }
+
+  /**
+   * Returns the error's int value.
+   */
+  public int getNumericExitCode() {
+    return numericExitCode;
+  }
+
+  /**
+   * Returns the human-readable name.
+   */
+  public String name() {
+    return name;
+  }
+
+  /**
+   * Returns true if the current exit code represents a failure of Blaze infrastructure,
+   * vs. a build failure.
+   */
+  public boolean isInfrastructureFailure() {
+    return infrastructureFailure;
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/util/FileType.java b/src/main/java/com/google/devtools/build/lib/util/FileType.java
new file mode 100644
index 0000000000..c91b17b60b
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/util/FileType.java
@@ -0,0 +1,278 @@
+// Copyright 2014 Google Inc. 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.util;
+
+import com.google.common.base.Preconditions;
+import com.google.common.base.Predicate;
+import com.google.common.base.Predicates;
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.Iterables;
+import com.google.devtools.build.lib.vfs.Path;
+import com.google.devtools.build.lib.vfs.PathFragment;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.List;
+
+import javax.annotation.concurrent.Immutable;
+
+/**
+ * A base class for FileType matchers.
+ */
+@Immutable
+public abstract class FileType implements Predicate<String> {
+  // A special file type
+  public static final FileType NO_EXTENSION = new FileType() {
+      @Override
+      public boolean apply(String filename) {
+        return filename.lastIndexOf('.') == -1;
+      }
+  };
+
+  public static FileType of(final String ext) {
+    return new FileType() {
+      @Override
+      public boolean apply(String filename) {
+        return filename.endsWith(ext);
+      }
+      @Override
+      public List<String> getExtensions() {
+        return ImmutableList.of(ext);
+      }
+    };
+  }
+
+  public static FileType of(final Iterable<String> extensions) {
+    return new FileType() {
+      @Override
+      public boolean apply(String filename) {
+        for (String ext : extensions) {
+          if (filename.endsWith(ext)) {
+            return true;
+          }
+        }
+        return false;
+      }
+      @Override
+      public List<String> getExtensions() {
+        return ImmutableList.copyOf(extensions);
+      }
+    };
+  }
+
+  public static FileType of(final String... extensions) {
+    return of(Arrays.asList(extensions));
+  }
+
+  @Override
+  public String toString() {
+    return getExtensions().toString();
+  }
+
+  /**
+   * Returns true if the the filename matches. The filename should be a basename (the filename
+   * component without a path) for performance reasons.
+   */
+  @Override
+  public abstract boolean apply(String filename);
+
+  /**
+   * Get a list of filename extensions this matcher handles. The first entry in the list (if
+   * available) is the primary extension that code can use to construct output file names.
+   * The list can be empty for some matchers.
+   *
+   * @return a list of filename extensions
+   */
+  public List<String> getExtensions() {
+    return ImmutableList.of();
+  }
+
+  /** Return true if a file name is matched by the FileType */
+  public boolean matches(String filename) {
+    int slashIndex = filename.lastIndexOf('/');
+    if (slashIndex != -1) {
+      filename = filename.substring(slashIndex + 1);
+    }
+    return apply(filename);
+  }
+
+  /** Return true if a file referred by path is matched by the FileType */
+  public boolean matches(Path path) {
+    return apply(path.getBaseName());
+  }
+
+  /** Return true if a file referred by fragment is matched by the FileType */
+  public boolean matches(PathFragment fragment) {
+    return apply(fragment.getBaseName());
+  }
+
+  // Check FileTypes
+
+  /**
+   * An interface for entities that have a filename.
+   */
+  public interface HasFilename {
+    /**
+     * Returns the filename of this entity.
+     */
+    String getFilename();
+  }
+
+  /**
+   * Checks whether an Iterable<? extends HasFileType> contains any of the specified file types.
+   *
+   * <p>At least one FileType must be specified.
+   */
+  public static <T extends HasFilename> boolean contains(final Iterable<T> items,
+      FileType... fileTypes) {
+    Preconditions.checkState(fileTypes.length > 0, "Must specify at least one file type");
+    final FileTypeSet fileTypeSet = FileTypeSet.of(fileTypes);
+    for (T item : items)  {
+      if (fileTypeSet.matches(item.getFilename())) {
+        return true;
+      }
+    }
+    return false;
+  }
+
+  /**
+   * Checks whether a HasFileType is any of the specified file types.
+   *
+   * <p>At least one FileType must be specified.
+   */
+  public static <T extends HasFilename> boolean contains(T item, FileType... fileTypes) {
+    return FileTypeSet.of(fileTypes).matches(item.getFilename());
+  }
+
+
+  private static <T extends HasFilename> Predicate<T> typeMatchingPredicateFor(
+      final FileType matchingType) {
+    return new Predicate<T>() {
+      @Override
+      public boolean apply(T item) {
+        return matchingType.matches(item.getFilename());
+      }
+    };
+  }
+
+  private static <T extends HasFilename> Predicate<T> typeMatchingPredicateFor(
+      final FileTypeSet matchingTypes) {
+    return new Predicate<T>() {
+      @Override
+      public boolean apply(T item) {
+        return matchingTypes.matches(item.getFilename());
+      }
+    };
+  }
+
+  private static <T extends HasFilename> Predicate<T> typeMatchingPredicateFrom(
+      final Predicate<String> fileTypePredicate) {
+    return new Predicate<T>() {
+      @Override
+      public boolean apply(T item) {
+        return fileTypePredicate.apply(item.getFilename());
+      }
+    };
+  }
+
+  /**
+   * A filter for Iterable<? extends HasFileType> that returns only those whose FileType matches the
+   * specified Predicate.
+   */
+  public static <T extends HasFilename> Iterable<T> filter(final Iterable<T> items,
+      final Predicate<String> predicate) {
+    return Iterables.filter(items, typeMatchingPredicateFrom(predicate));
+  }
+
+  /**
+   * A filter for Iterable<? extends HasFileType> that returns only those of the specified file
+   * types.
+   */
+  public static <T extends HasFilename> Iterable<T> filter(final Iterable<T> items,
+      FileType... fileTypes) {
+    return filter(items, FileTypeSet.of(fileTypes));
+  }
+
+  /**
+   * A filter for Iterable<? extends HasFileType> that returns only those of the specified file
+   * types.
+   */
+  public static <T extends HasFilename> Iterable<T> filter(final Iterable<T> items,
+      FileTypeSet fileTypes) {
+    return Iterables.filter(items, typeMatchingPredicateFor(fileTypes));
+  }
+
+  /**
+   * A filter for Iterable<? extends HasFileType> that returns only those of the specified file
+   * type.
+   */
+  public static <T extends HasFilename> Iterable<T> filter(final Iterable<T> items,
+      FileType fileType) {
+    return Iterables.filter(items, typeMatchingPredicateFor(fileType));
+  }
+
+  /**
+   * A filter for Iterable<? extends HasFileType> that returns everything except the specified file
+   * type.
+   */
+  public static <T extends HasFilename> Iterable<T> except(final Iterable<T> items,
+      FileType fileType) {
+    return Iterables.filter(items, Predicates.not(typeMatchingPredicateFor(fileType)));
+  }
+
+
+  /**
+   * A filter for List<? extends HasFileType> that returns only those of the specified file types.
+   * The result is a mutable list, computed eagerly; see {@link #filter} for a lazy variant.
+   */
+  public static <T extends HasFilename> List<T> filterList(final Iterable<T> items,
+      FileType... fileTypes) {
+    if (fileTypes.length > 0) {
+      return filterList(items, FileTypeSet.of(fileTypes));
+    } else {
+      return new ArrayList<>();
+    }
+  }
+
+  /**
+   * A filter for List<? extends HasFileType> that returns only those of the specified file type.
+   * The result is a mutable list, computed eagerly.
+   */
+  public static <T extends HasFilename> List<T> filterList(final Iterable<T> items,
+      final FileType fileType) {
+    List<T> result = new ArrayList<>();
+    for (T item : items)  {
+      if (fileType.matches(item.getFilename())) {
+        result.add(item);
+      }
+    }
+    return result;
+  }
+
+  /**
+   * A filter for List<? extends HasFileType> that returns only those of the specified file types.
+   * The result is a mutable list, computed eagerly.
+   */
+  public static <T extends HasFilename> List<T> filterList(final Iterable<T> items,
+      final FileTypeSet fileTypeSet) {
+    List<T> result = new ArrayList<>();
+    for (T item : items)  {
+      if (fileTypeSet.matches(item.getFilename())) {
+        result.add(item);
+      }
+    }
+    return result;
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/util/FileTypeSet.java b/src/main/java/com/google/devtools/build/lib/util/FileTypeSet.java
new file mode 100644
index 0000000000..694e87745d
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/util/FileTypeSet.java
@@ -0,0 +1,139 @@
+// Copyright 2014 Google Inc. 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.util;
+
+import com.google.common.base.Predicate;
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.Iterables;
+
+import java.util.ArrayList;
+import java.util.List;
+
+import javax.annotation.concurrent.Immutable;
+
+/**
+ * A set of FileTypes for grouped matching.
+ */
+@Immutable
+public class FileTypeSet implements Predicate<String> {
+  private final ImmutableSet<FileType> types;
+
+  /** A set that matches all files. */
+  public static final FileTypeSet ANY_FILE =
+      new FileTypeSet() {
+        @Override
+        public String toString() {
+          return "any files";
+        }
+        @Override
+        public boolean matches(String filename) {
+          return true;
+        }
+        @Override
+        public List<String> getExtensions() {
+          return ImmutableList.<String>of();
+        }
+      };
+
+  /** A predicate that matches no files. */
+  public static final FileTypeSet NO_FILE =
+      new FileTypeSet(ImmutableList.<FileType>of()) {
+        @Override
+        public String toString() {
+          return "no files";
+        }
+        @Override
+        public boolean matches(String filename) {
+          return false;
+        }
+      };
+
+  private FileTypeSet() {
+    this.types = null;
+  }
+
+  private FileTypeSet(FileType... fileTypes) {
+    this.types = ImmutableSet.copyOf(fileTypes);
+  }
+
+  private FileTypeSet(Iterable<FileType> fileTypes) {
+    this.types = ImmutableSet.copyOf(fileTypes);
+  }
+
+  /**
+   * Returns a set that matches only the provided {@code fileTypes}.
+   *
+   * <p>If {@code fileTypes} is empty, the returned predicate will match no files.
+   */
+  public static FileTypeSet of(FileType... fileTypes) {
+    if (fileTypes.length == 0) {
+      return FileTypeSet.NO_FILE;
+    } else {
+      return new FileTypeSet(fileTypes);
+    }
+  }
+
+  /**
+   * Returns a set that matches only the provided {@code fileTypes}.
+   *
+   * <p>If {@code fileTypes} is empty, the returned predicate will match no files.
+   */
+  public static FileTypeSet of(Iterable<FileType> fileTypes) {
+    if (Iterables.isEmpty(fileTypes)) {
+      return FileTypeSet.NO_FILE;
+    } else {
+      return new FileTypeSet(fileTypes);
+    }
+  }
+
+  /** Returns true if the filename can be matched by any FileType in this set. */
+  public boolean matches(String filename) {
+    int slashIndex = filename.lastIndexOf('/');
+    if (slashIndex != -1) {
+      filename = filename.substring(slashIndex + 1);
+    }
+    for (FileType type : types) {
+      if (type.apply(filename)) {
+        return true;
+      }
+    }
+    return false;
+  }
+
+  /** Returns true if this predicate matches nothing. */
+  public boolean isNone() {
+    return this == FileTypeSet.NO_FILE;
+  }
+
+  @Override
+  public boolean apply(String filename) {
+    return matches(filename);
+  }
+
+  /** Returns the list of possible file extensions for this file type. Can be empty. */
+  public List<String> getExtensions() {
+    List<String> extensions = new ArrayList<>();
+    for (FileType type : types) {
+      extensions.addAll(type.getExtensions());
+    }
+    return extensions;
+  }
+
+  @Override
+  public String toString() {
+    return StringUtil.joinEnglishList(getExtensions());
+  }
+
+}
diff --git a/src/main/java/com/google/devtools/build/lib/util/Fingerprint.java b/src/main/java/com/google/devtools/build/lib/util/Fingerprint.java
new file mode 100644
index 0000000000..e4c0876737
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/util/Fingerprint.java
@@ -0,0 +1,319 @@
+// Copyright 2014 Google Inc. 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.util;
+
+import static java.nio.charset.StandardCharsets.UTF_8;
+
+import com.google.common.collect.Iterables;
+import com.google.devtools.build.lib.vfs.Path;
+import com.google.devtools.build.lib.vfs.PathFragment;
+
+import java.security.MessageDigest;
+import java.security.NoSuchAlgorithmException;
+import java.util.Map;
+import java.util.UUID;
+
+/**
+ * Simplified wrapper for MD5 message digests. See also
+ * com.google.math.crypto.MD5HMAC for a similar interface.
+ *
+ * @see java.security.MessageDigest
+ */
+public final class Fingerprint {
+
+  private final MessageDigest md;
+
+  /**
+   * Creates and initializes a new MD5 object; if this fails, Java must be
+   * installed incorrectly.
+   */
+  public Fingerprint() {
+    try {
+      md = MessageDigest.getInstance("md5");
+    } catch (NoSuchAlgorithmException e) {
+      throw new RuntimeException("MD5 not available");
+    }
+  }
+
+  /**
+   * Completes the hash computation by doing final operations, e.g., padding.
+   *
+   * <p>This method has the side-effect of resetting the underlying digest computer.
+   *
+   * @return the MD5 digest as a 16-byte array
+   * @see java.security.MessageDigest#digest()
+   */
+  public byte[] digestAndReset() {
+    return md.digest();
+  }
+
+  /**
+   * Completes the hash computation and returns the digest as a string.
+   *
+   * <p>This method has the side-effect of resetting the underlying digest computer.
+   *
+   * @return the MD5 digest as a 32-character string of hexadecimal digits
+   * @see com.google.math.crypto.MD5HMAC#toString()
+   */
+  public String hexDigestAndReset() {
+    return hexDigest(digestAndReset());
+  }
+
+  /**
+   * Returns a string representation of an MD5 digest.
+   *
+   * @param digest the MD5 digest, perhaps from a previous call to digest
+   * @return the digest as a 32-character string of hexadecimal digits
+   */
+  public static String hexDigest(byte[] digest) {
+    StringBuilder b = new StringBuilder(32);
+    for (int i = 0; i < digest.length; i++) {
+      int n = digest[i];
+      b.append("0123456789abcdef".charAt((n >> 4) & 0xF));
+      b.append("0123456789abcdef".charAt(n & 0xF));
+    }
+    return b.toString();
+  }
+
+  /**
+   * Override of Object.toString to return a string for the MD5 digest without
+   * finalizing the digest computation. Calling hexDigest() instead will
+   * finalize the digest computation.
+   *
+   * @return the string returned by hexDigest()
+   */
+  @Override
+  public String toString() {
+    try {
+      // MD5 does support cloning, so this should not fail
+      return hexDigest(((MessageDigest) md.clone()).digest());
+    } catch (CloneNotSupportedException e) {
+      // MessageDigest does not support cloning,
+      // so just return the toString() on the MessageDigest.
+      return md.toString();
+    }
+  }
+
+  /**
+   * Updates the digest with 0 or more bytes.
+   *
+   * @param input the array of bytes with which to update the digest
+   * @see java.security.MessageDigest#update(byte[])
+   */
+  public Fingerprint addBytes(byte[] input) {
+    md.update(input);
+    return this;
+  }
+
+  /**
+   * Updates the digest with the specified number of bytes starting at offset.
+   *
+   * @param input the array of bytes with which to update the digest
+   * @param offset the offset into the array
+   * @param len the number of bytes to use
+   * @see java.security.MessageDigest#update(byte[], int, int)
+   */
+  public Fingerprint addBytes(byte[] input, int offset, int len) {
+    md.update(input, offset, len);
+    return this;
+  }
+
+  /**
+   * Updates the digest with a boolean value.
+   */
+  public Fingerprint addBoolean(boolean input) {
+    addBytes(new byte[] { (byte) (input ? 1 : 0) });
+    return this;
+  }
+
+  /**
+   * Updates the digest with the little-endian bytes of a given int value.
+   *
+   * @param input the integer with which to update the digest
+   */
+  public Fingerprint addInt(int input) {
+    md.update(new byte[] {
+        (byte) input,
+        (byte) (input >>  8),
+        (byte) (input >> 16),
+        (byte) (input >> 24),
+    });
+
+    return this;
+  }
+
+  /**
+   * Updates the digest with the little-endian bytes of a given long value.
+   *
+   * @param input the long with which to update the digest
+   */
+  public Fingerprint addLong(long input) {
+    md.update(new byte[]{
+        (byte) input,
+        (byte) (input >> 8),
+        (byte) (input >> 16),
+        (byte) (input >> 24),
+        (byte) (input >> 32),
+        (byte) (input >> 40),
+        (byte) (input >> 48),
+        (byte) (input >> 56),
+    });
+
+    return this;
+  }
+
+  /**
+   * Updates the digest with a UUID.
+   *
+   * @param uuid the UUID with which to update the digest. Must not be null.
+   */
+  public Fingerprint addUUID(UUID uuid) {
+    addLong(uuid.getLeastSignificantBits());
+    addLong(uuid.getMostSignificantBits());
+    return this;
+  }
+
+  /**
+   * Updates the digest with a String using its length plus its UTF8 encoded bytes.
+   *
+   * @param input the String with which to update the digest
+   * @see java.security.MessageDigest#update(byte[])
+   */
+  public Fingerprint addString(String input) {
+    byte[] bytes = input.getBytes(UTF_8);
+    addInt(bytes.length);
+    md.update(bytes);
+    return this;
+  }
+
+  /**
+   * Updates the digest with a String using its length and content.
+   *
+   * @param input the String with which to update the digest
+   * @see java.security.MessageDigest#update(byte[])
+   */
+  public Fingerprint addStringLatin1(String input) {
+    addInt(input.length());
+    byte[] bytes = new byte[input.length()];
+    for (int i = 0; i < input.length(); i++) {
+      bytes[i] = (byte) input.charAt(i);
+    }
+    md.update(bytes);
+    return this;
+  }
+
+  /**
+   * Updates the digest with a Path.
+   *
+   * @param input the Path with which to update the digest.
+   */
+  public Fingerprint addPath(Path input) {
+    addStringLatin1(input.getPathString());
+    return this;
+  }
+
+  /**
+   * Updates the digest with a Path.
+   *
+   * @param input the Path with which to update the digest.
+   */
+  public Fingerprint addPath(PathFragment input) {
+    addStringLatin1(input.getPathString());
+    return this;
+  }
+
+  /**
+   * Updates the digest with inputs by iterating over them and invoking
+   * {@code #addString(String)} on each element.
+   *
+   * @param inputs the inputs with which to update the digest
+   */
+  public Fingerprint addStrings(Iterable<String> inputs) {
+    addInt(Iterables.size(inputs));
+    for (String input : inputs) {
+      addString(input);
+    }
+
+    return this;
+  }
+
+  /**
+   * Updates the digest with inputs by iterating over them and invoking
+   * {@code #addString(String)} on each element.
+   *
+   * @param inputs the inputs with which to update the digest
+   */
+  public Fingerprint addStrings(String... inputs) {
+    addInt(inputs.length);
+    for (String input : inputs) {
+      addString(input);
+    }
+
+    return this;
+  }
+
+  /**
+   * Updates the digest with inputs which are pairs in a map, by iterating over
+   * the map entries and invoking {@code #addString(String)} on each key and
+   * value.
+   *
+   * @param inputs the inputs in a map with which to update the digest
+   */
+  public Fingerprint addStringMap(Map<String, String> inputs) {
+    addInt(inputs.size());
+    for (Map.Entry<String, String> entry : inputs.entrySet()) {
+      addString(entry.getKey());
+      addString(entry.getValue());
+    }
+
+    return this;
+  }
+
+  /**
+   * Updates the digest with a list of paths by iterating over them and
+   * invoking {@link #addPath(PathFragment)} on each element.
+   *
+   * @param inputs the paths with which to update the digest
+   */
+  public Fingerprint addPaths(Iterable<PathFragment> inputs) {
+    addInt(Iterables.size(inputs));
+    for (PathFragment path : inputs) {
+      addPath(path);
+    }
+
+    return this;
+  }
+
+  /**
+   * Reset the Fingerprint for additional use as though previous digesting had not been done.
+   */
+  public void reset() {
+    md.reset();
+  }
+
+  // -------- Convenience methods ----------------------------
+
+  /**
+   * Computes the hex digest from a String using UTF8 encoding and returning
+   * the hexDigest().
+   *
+   * @param input the String from which to compute the digest
+   */
+  public static String md5Digest(String input) {
+    Fingerprint f = new Fingerprint();
+    f.addBytes(input.getBytes(UTF_8));
+    return f.hexDigestAndReset();
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/util/GroupedList.java b/src/main/java/com/google/devtools/build/lib/util/GroupedList.java
new file mode 100644
index 0000000000..2bf956df4c
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/util/GroupedList.java
@@ -0,0 +1,344 @@
+// Copyright 2014 Google Inc. 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.util;
+
+import com.google.common.base.Objects;
+import com.google.common.base.Preconditions;
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.Iterables;
+import com.google.devtools.build.lib.collect.CompactHashSet;
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Set;
+
+/**
+ * Encapsulates a list of lists. Is intended to be used in "batch" mode -- to set the value of a
+ * GroupedList, users should first construct a {@link GroupedListHelper}, add elements to it, and
+ * then {@link #append} the helper to a new GroupedList instance. The generic type T <i>must not</i>
+ * be a {@link List}.
+ *
+ * <p>Despite the "list" name, it is an error for the same element to appear multiple times in the
+ * list. Users are responsible for not trying to add the same element to a GroupedList twice.
+ */
+public class GroupedList<T> implements Iterable<Iterable<T>> {
+  // Total number of items in the list. At least elements.size(), but might be larger if there are
+  // any nested lists.
+  private int size = 0;
+  // Items in this GroupedList. Each element is either of type T or List<T>.
+  // Non-final only for #remove.
+  private List<Object> elements;
+
+  public GroupedList() {
+    // We optimize for small lists.
+    this.elements = new ArrayList<>(1);
+  }
+
+  // Only for use when uncompressing a GroupedList.
+  private GroupedList(int size, List<Object> elements) {
+    this.size = size;
+    this.elements = new ArrayList<>(elements);
+  }
+
+  /** Appends the list constructed in helper to this list. */
+  public void append(GroupedListHelper<T> helper) {
+    Preconditions.checkState(helper.currentGroup == null, "%s %s", this, helper);
+    // Do a check to make sure we don't have lists here. Note that if helper.elements is empty,
+    // Iterables.getFirst will return null, and null is not instanceof List.
+    Preconditions.checkState(!(Iterables.getFirst(helper.elements, null) instanceof List),
+        "Cannot make grouped list of lists: %s", helper);
+    elements.addAll(helper.groupedList);
+    size += helper.size();
+  }
+
+  /**
+   * Removes the elements in toRemove from this list. Takes time proportional to the size of the
+   * list, so should not be called often.
+   */
+  public void remove(Set<T> toRemove) {
+    elements = remove(elements, toRemove);
+    size -= toRemove.size();
+  }
+
+  /** Returns the number of elements in this list. */
+  public int size() {
+    return size;
+  }
+
+  /** Returns true if this list contains no elements. */
+  public boolean isEmpty() {
+    return elements.isEmpty();
+  }
+
+  private static final Object EMPTY_LIST = new Object();
+
+  public Object compress() {
+    switch (size()) {
+      case 0:
+        return EMPTY_LIST;
+      case 1:
+        return Iterables.getOnlyElement(elements);
+      default:
+        return elements.toArray();
+    }
+  }
+
+  @SuppressWarnings("unchecked")
+  public Set<T> toSet() {
+    ImmutableSet.Builder<T> builder = ImmutableSet.builder();
+    for (Object obj : elements) {
+      if (obj instanceof List) {
+        builder.addAll((List<T>) obj);
+      } else {
+        builder.add((T) obj);
+      }
+    }
+    return builder.build();
+  }
+
+  private static int sizeOf(Object obj) {
+    return obj instanceof List ? ((List<?>) obj).size() : 1;
+  }
+
+  public static <E> GroupedList<E> create(Object compressed) {
+    if (compressed == EMPTY_LIST) {
+      return new GroupedList<>();
+    }
+    if (compressed.getClass().isArray()) {
+      List<Object> elements = new ArrayList<>();
+      int size = 0;
+      for (Object item : (Object[]) compressed) {
+        size += sizeOf(item);
+        elements.add(item);
+      }
+      return new GroupedList<>(size, elements);
+    }
+    // Just a single element.
+    return new GroupedList<>(1, ImmutableList.<Object>of(compressed));
+  }
+
+  @Override
+  public boolean equals(Object other) {
+    if (other == null) {
+      return false;
+    }
+    if (this.getClass() != other.getClass()) {
+      return false;
+    }
+    GroupedList<?> that = (GroupedList<?>) other;
+    return elements.equals(that.elements);
+  }
+
+  @Override
+  @SuppressWarnings("deprecation")
+  public String toString() {
+    return Objects.toStringHelper(this)
+        .add("elements", elements)
+        .add("size", size).toString();
+
+  }
+
+  /**
+   * Iterator that returns the next group in elements for each call to {@link #next}. A custom
+   * iterator is needed here because, to optimize memory, we store single-element lists as elements
+   * internally, and so they must be wrapped before they're returned.
+   */
+  private class GroupedIterator implements Iterator<Iterable<T>> {
+    private final Iterator<Object> iter = elements.iterator();
+
+    @Override
+    public boolean hasNext() {
+      return iter.hasNext();
+    }
+
+    @SuppressWarnings("unchecked") // Cast of Object to List<T> or T.
+    @Override
+    public Iterable<T> next() {
+      Object obj = iter.next();
+      if (obj instanceof List) {
+        return (List<T>) obj;
+      }
+      return ImmutableList.of((T) obj);
+    }
+
+    @Override
+    public void remove() {
+      throw new UnsupportedOperationException();
+    }
+  }
+
+  @Override
+  public Iterator<Iterable<T>> iterator() {
+    return new GroupedIterator();
+  }
+
+  /**
+   * Removes everything in toRemove from the list of lists, elements. Called both by GroupedList and
+   * GroupedListHelper.
+   */
+  private static <E> List<Object> remove(List<Object> elements, Set<E> toRemove) {
+    int removedCount = 0;
+    // elements.size is an upper bound of the needed size. Since normally removal happens just
+    // before the list is finished and compressed, optimizing this size isn't a concern.
+    List<Object> newElements = new ArrayList<>(elements.size());
+    for (Object obj : elements) {
+      if (obj instanceof List) {
+        ImmutableList.Builder<E> newGroup = new ImmutableList.Builder<>();
+        @SuppressWarnings("unchecked")
+        List<E> oldGroup = (List<E>) obj;
+        for (E elt : oldGroup) {
+          if (toRemove.contains(elt)) {
+            removedCount++;
+          } else {
+            newGroup.add(elt);
+          }
+        }
+        ImmutableList<E> group = newGroup.build();
+        addItem(group, newElements);
+      } else {
+        if (toRemove.contains(obj)) {
+          removedCount++;
+        } else {
+          newElements.add(obj);
+        }
+      }
+    }
+    Preconditions.checkState(removedCount == toRemove.size(),
+        "%s %s %s %s", removedCount, removedCount, elements, newElements);
+    return newElements;
+  }
+
+  private static void addItem(Collection<?> item, List<Object> elements) {
+    switch (item.size()) {
+      case 0:
+        return;
+      case 1:
+        elements.add(Iterables.getOnlyElement(item));
+        return;
+      default:
+        elements.add(ImmutableList.copyOf(item));
+    }
+  }
+
+  /**
+   * Builder-like object for GroupedLists. An already-existing grouped list is appended to by
+   * constructing a helper, mutating it, and then appending that helper to the grouped list.
+   */
+  public static class GroupedListHelper<E> implements Iterable<E> {
+    // Non-final only for removal.
+    private List<Object> groupedList;
+    private List<E> currentGroup = null;
+    private final Set<E> elements = CompactHashSet.create();
+
+    private GroupedListHelper(GroupedList<E> groupedList) {
+      this.groupedList = new ArrayList<>(groupedList.elements);
+      for (Iterable<E> group : groupedList) {
+        Iterables.addAll(elements, group);
+      }
+    }
+
+    public GroupedListHelper() {
+      // Optimize for short lists.
+      groupedList = new ArrayList<>(1);
+    }
+
+    /**
+     * Add an element to this list. If in a group, will be added to the current group. Otherwise,
+     * goes in a group of its own.
+     */
+    public void add(E elt) {
+      Preconditions.checkState(elements.add(elt), "%s %s", elt, this);
+      if (currentGroup == null) {
+        groupedList.add(elt);
+      } else {
+        currentGroup.add(elt);
+      }
+    }
+
+    /**
+     * Remove all elements of toRemove from this list. It is a fatal error if any elements of
+     * toRemove are not present. Takes time proportional to the size of the list, so should not be
+     * called often.
+     */
+    public void remove(Set<E> toRemove) {
+      groupedList = GroupedList.remove(groupedList, toRemove);
+      int oldSize = size();
+      elements.removeAll(toRemove);
+      Preconditions.checkState(oldSize == size() + toRemove.size(),
+          "%s %s %s", oldSize, toRemove, this);
+    }
+
+    /**
+     * Starts a group. All elements added until {@link #endGroup} will be in the same group. Each
+     * call of {@link #startGroup} must be paired with a following {@link #endGroup} call.
+     */
+    public void startGroup() {
+      Preconditions.checkState(currentGroup == null, this);
+      currentGroup = new ArrayList<>();
+    }
+
+    private void addList(Collection<E> group) {
+      addItem(group, groupedList);
+    }
+
+    /** Ends a group started with {@link #startGroup}. */
+    public void endGroup() {
+      Preconditions.checkNotNull(currentGroup);
+      addList(currentGroup);
+      currentGroup = null;
+    }
+
+    /** Returns true if elt is present in the list. */
+    public boolean contains(E elt) {
+      return elements.contains(elt);
+    }
+
+    private int size() {
+      return elements.size();
+    }
+
+    /** Returns true if list is empty. */
+    public boolean isEmpty() {
+      return elements.isEmpty();
+    }
+
+    @Override
+    public Iterator<E> iterator() {
+      return elements.iterator();
+    }
+
+    /** Create a GroupedListHelper from a collection of elements, all put in the same group.*/
+    public static <F> GroupedListHelper<F> create(Collection<F> elements) {
+      GroupedListHelper<F> helper = new GroupedListHelper<>();
+      helper.addList(elements);
+      helper.elements.addAll(elements);
+      Preconditions.checkState(helper.elements.size() == elements.size(),
+          "%s %s", helper, elements);
+      return helper;
+    }
+
+    @Override
+    @SuppressWarnings("deprecation")
+    public String toString() {
+      return Objects.toStringHelper(this)
+          .add("groupedList", groupedList)
+          .add("elements", elements)
+          .add("currentGroup", currentGroup).toString();
+
+    }
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/util/IncludeScanningUtil.java b/src/main/java/com/google/devtools/build/lib/util/IncludeScanningUtil.java
new file mode 100644
index 0000000000..24f55e4862
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/util/IncludeScanningUtil.java
@@ -0,0 +1,48 @@
+// Copyright 2014 Google Inc. 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.util;
+
+import com.google.devtools.build.lib.Constants;
+import com.google.devtools.build.lib.vfs.PathFragment;
+
+/**
+ * Static utilities for include scanning.
+ */
+public class IncludeScanningUtil {
+  private IncludeScanningUtil() {
+  }
+
+  private static final String INCLUDES_SUFFIX = ".includes";
+  public static final PathFragment GREPPED_INCLUDES =
+      new PathFragment(Constants.PRODUCT_NAME + "-out/_grepped_includes");
+
+  /**
+   * Returns the exec-root relative output path for grepped includes.
+   *
+   * @param srcExecPath the exec-root relative path of the source file.
+   */
+  public static PathFragment getExecRootRelativeOutputPath(PathFragment srcExecPath) {
+    return GREPPED_INCLUDES.getRelative(getRootRelativeOutputPath(srcExecPath));
+  }
+
+  /**
+   * Returns the root relative output path for grepped includes.
+   *
+   * @param srcExecPath the exec-root relative path of the source file.
+   */
+  public static PathFragment getRootRelativeOutputPath(PathFragment srcExecPath) {
+    return srcExecPath.replaceName(srcExecPath.getBaseName() + INCLUDES_SUFFIX);
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/util/JavaClock.java b/src/main/java/com/google/devtools/build/lib/util/JavaClock.java
new file mode 100644
index 0000000000..bdd11169a3
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/util/JavaClock.java
@@ -0,0 +1,36 @@
+// Copyright 2014 Google Inc. 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.util;
+
+/**
+ * Class provides a simple clock implementation used by the tool. By default it uses {@link System}
+ * class.
+ */
+public class JavaClock implements Clock {
+
+  public JavaClock() {
+  }
+
+  @Override
+  public long currentTimeMillis() {
+    return System.currentTimeMillis();
+  }
+
+  @Override
+  public long nanoTime() {
+    // Note that some JVM implementations of System#nanoTime don't yield a non-decreasing
+    // sequence of values.
+    return System.nanoTime();
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/util/LazyString.java b/src/main/java/com/google/devtools/build/lib/util/LazyString.java
new file mode 100644
index 0000000000..0e037b28f1
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/util/LazyString.java
@@ -0,0 +1,41 @@
+// Copyright 2014 Google Inc. 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.util;
+
+/**
+ * This class serves as a base implementation for a {@code CharSequence}
+ * that delay string construction (mostly till the execution phase).
+ *
+ * They are not full implementations, they lack {@code #charAt(int)} and
+ * {@code #subSequence(int, int)}.
+ */
+public abstract class LazyString implements CharSequence {
+
+  @Override
+  public char charAt(int index) {
+    throw new UnsupportedOperationException();
+  }
+
+  @Override
+  public int length() {
+    return toString().length();
+  }
+
+  @Override
+  public CharSequence subSequence(int start, int end) {
+    throw new UnsupportedOperationException();
+  }
+
+}
diff --git a/src/main/java/com/google/devtools/build/lib/util/LoggingUtil.java b/src/main/java/com/google/devtools/build/lib/util/LoggingUtil.java
new file mode 100644
index 0000000000..5170727c6e
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/util/LoggingUtil.java
@@ -0,0 +1,87 @@
+// Copyright 2014 Google Inc. 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.util;
+
+import com.google.common.base.Preconditions;
+import com.google.common.util.concurrent.Uninterruptibles;
+import com.google.devtools.build.lib.concurrent.ThreadSafety;
+
+import java.util.concurrent.ExecutionException;
+import java.util.concurrent.Future;
+import java.util.logging.Level;
+import java.util.logging.LogRecord;
+import java.util.logging.Logger;
+
+/**
+ * Logging utilities for sending log messages to a remote service. Log messages
+ * will not be output anywhere else, including the terminal and blaze clients.
+ */
+@ThreadSafety.ThreadSafe
+public final class LoggingUtil {
+  // TODO(bazel-team): this class is a thin wrapper around Logger and could probably be discarded.
+  private static Future<Logger> remoteLogger;
+
+  /**
+   * Installs the remote logger.
+   *
+   * <p>This can only be called once, and the caller should not keep the
+   * reference to the logger.
+   *
+   * @param logger The logger future. Must have already started.
+   */
+  public static synchronized void installRemoteLogger(Future<Logger> logger) {
+    Preconditions.checkState(remoteLogger == null);
+    remoteLogger = logger;
+  }
+
+  /** Returns the installed logger, or null if none is installed. */
+  public static synchronized Logger getRemoteLogger() {
+    try {
+      return (remoteLogger == null) ? null : Uninterruptibles.getUninterruptibly(remoteLogger);
+    } catch (ExecutionException e) {
+      throw new RuntimeException("Unexpected error initializing remote logging", e);
+    }
+  }
+
+  /**
+   * @see #logToRemote(Level, String, Throwable, String...).
+   */
+  public static void logToRemote(Level level, String msg, Throwable trace) {
+    Logger logger = getRemoteLogger();
+    if (logger != null) {
+      logger.log(level, msg, trace);
+    }
+  }
+
+  /**
+   * Log a message to the remote backend.  This is done out of thread, so this
+   * method is non-blocking.
+   *
+   * @param level The severity level. Non null.
+   * @param msg The log message. Non null.
+   * @param trace The stack trace.  May be null.
+   * @param values Additional values to upload.
+   */
+  public static void logToRemote(Level level, String msg, Throwable trace,
+      String... values) {
+    Logger logger = getRemoteLogger();
+    if (logger != null) {
+      LogRecord logRecord = new LogRecord(level, msg);
+      logRecord.setThrown(trace);
+      logRecord.setParameters(values);
+      logger.log(logRecord);
+    }
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/util/NetUtil.java b/src/main/java/com/google/devtools/build/lib/util/NetUtil.java
new file mode 100644
index 0000000000..498da7775a
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/util/NetUtil.java
@@ -0,0 +1,38 @@
+// Copyright 2014 Google Inc. 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.util;
+
+import java.net.InetAddress;
+import java.net.UnknownHostException;
+
+/**
+ * Various utility methods for network related stuff.
+ */
+public final class NetUtil {
+
+  private NetUtil() {
+  }
+
+  /**
+   * Returns the short hostname or <code>unknown</code> if the host name could
+   * not be determined.
+   */
+  public static String findShortHostName() {
+    try {
+      return InetAddress.getLocalHost().getHostName();
+    } catch (UnknownHostException e) {
+      return "unknown";
+    }
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/util/OS.java b/src/main/java/com/google/devtools/build/lib/util/OS.java
new file mode 100644
index 0000000000..b19bd7e301
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/util/OS.java
@@ -0,0 +1,43 @@
+// Copyright 2014 Google Inc. 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.util;
+
+/**
+ * An operating system.
+ */
+public enum OS {
+  DARWIN,
+  LINUX,
+  WINDOWS,
+  UNKNOWN;
+
+  /**
+   * The current operating system.
+   */
+  public static OS getCurrent() {
+    return HOST_SYSTEM;
+  }
+  // We inject a the OS name through blaze.os, so we can have
+  // some coverage for Windows specific code on Linux.
+  private static String getOsName() {
+    String override = System.getProperty("blaze.os");
+    return override == null ? System.getProperty("os.name") : override;
+  }
+
+  private static final OS HOST_SYSTEM =
+      "Mac OS X".equals(getOsName()) ? OS.DARWIN : (
+      "Linux".equals(getOsName()) ? OS.LINUX : (
+          getOsName().contains("Windows") ? OS.WINDOWS : OS.UNKNOWN));
+}
+
diff --git a/src/main/java/com/google/devtools/build/lib/util/OptionsUtils.java b/src/main/java/com/google/devtools/build/lib/util/OptionsUtils.java
new file mode 100644
index 0000000000..11bf94f547
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/util/OptionsUtils.java
@@ -0,0 +1,154 @@
+// Copyright 2014 Google Inc. 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.util;
+
+import com.google.devtools.build.lib.vfs.PathFragment;
+import com.google.devtools.common.options.Converter;
+import com.google.devtools.common.options.Converters;
+import com.google.devtools.common.options.OptionsParser.UnparsedOptionValueDescription;
+import com.google.devtools.common.options.OptionsParsingException;
+import com.google.devtools.common.options.OptionsProvider;
+
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.List;
+
+/**
+ * Blaze-specific option utilities.
+ */
+public final class OptionsUtils {
+
+  /**
+   * Returns a string representation of the non-hidden specified options; option values are
+   * shell-escaped.
+   */
+  public static String asShellEscapedString(Iterable<UnparsedOptionValueDescription> optionsList) {
+    StringBuffer result = new StringBuffer();
+    for (UnparsedOptionValueDescription option : optionsList) {
+      if (option.isHidden()) {
+        continue;
+      }
+      if (result.length() != 0) {
+        result.append(' ');
+      }
+      String value = option.getUnparsedValue();
+      if (option.isBooleanOption()) {
+        boolean isEnabled = false;
+        try {
+          isEnabled = new Converters.BooleanConverter().convert(value);
+        } catch (OptionsParsingException e) {
+          throw new RuntimeException("Unexpected parsing exception", e);
+        }
+        result.append(isEnabled ? "--" : "--no").append(option.getName());
+      } else {
+        result.append("--").append(option.getName());
+        if (value != null) { // Can be null for Void options.
+          result.append("=").append(ShellEscaper.escapeString(value));
+        }
+      }
+    }
+    return result.toString();
+  }
+
+  /**
+   * Returns a string representation of the non-hidden explicitly or implicitly
+   * specified options; option values are shell-escaped.
+   */
+  public static String asShellEscapedString(OptionsProvider options) {
+    return asShellEscapedString(options.asListOfUnparsedOptions());
+  }
+
+  /**
+   * Returns a string representation of the non-hidden explicitly or implicitly
+   * specified options, filtering out any sensitive options; option values are
+   * shell-escaped.
+   */
+  public static String asFilteredShellEscapedString(OptionsProvider options,
+      Iterable<UnparsedOptionValueDescription> optionsList) {
+    return asShellEscapedString(optionsList);
+  }
+
+  /**
+   * Returns a string representation of the non-hidden explicitly or implicitly
+   * specified options, filtering out any sensitive options; option values are
+   * shell-escaped.
+   */
+  public static String asFilteredShellEscapedString(OptionsProvider options) {
+    return asFilteredShellEscapedString(options, options.asListOfUnparsedOptions());
+  }
+
+  /**
+   * Converter from String to PathFragment.
+   */
+  public static class PathFragmentConverter
+      implements Converter<PathFragment> {
+
+    @Override
+    public PathFragment convert(String input) {
+      return new PathFragment(input);
+    }
+
+    @Override
+    public String getTypeDescription() {
+      return "a path";
+    }
+  }
+
+  /**
+   * Converter from String to PathFragment.
+   *
+   * <p>Complains if the path is not absolute.
+   */
+  public static class AbsolutePathFragmentConverter
+      implements Converter<PathFragment> {
+
+    @Override
+    public PathFragment convert(String input) throws OptionsParsingException {
+      PathFragment pathFragment = new PathFragment(input);
+      if (!pathFragment.isAbsolute()) {
+        throw new OptionsParsingException("Expected absolute path, found " + input);
+      }
+      return pathFragment;
+    }
+
+    @Override
+    public String getTypeDescription() {
+      return "an absolute path";
+    }
+  }
+
+  /**
+   * Converts from a colon-separated list of strings into a list of PathFragment instances.
+   */
+  public static class PathFragmentListConverter
+      implements Converter<List<PathFragment>> {
+
+    @Override
+    public List<PathFragment> convert(String input) {
+      List<PathFragment> list = new ArrayList<>();
+      for (String piece : input.split(":")) {
+        if (!piece.equals("")) {
+          list.add(new PathFragment(piece));
+        }
+      }
+      return Collections.unmodifiableList(list);
+    }
+
+    @Override
+    public String getTypeDescription() {
+      return "a colon-separated list of paths";
+    }
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/util/OsUtils.java b/src/main/java/com/google/devtools/build/lib/util/OsUtils.java
new file mode 100644
index 0000000000..fa12f59682
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/util/OsUtils.java
@@ -0,0 +1,74 @@
+// Copyright 2014 Google Inc. 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.util;
+
+import com.google.devtools.build.lib.vfs.PathFragment;
+
+/**
+ * Operating system-specific utilities.
+ */
+public final class OsUtils {
+
+  private static final String EXECUTABLE_EXTENSION = OS.getCurrent() == OS.WINDOWS ? ".exe" : "";
+
+  // Utility class.
+  private OsUtils() {
+  }
+
+  /**
+   * Returns the extension used for executables on the current platform (.exe
+   * for Windows, empty string for others).
+   */
+  public static String executableExtension() {
+    return EXECUTABLE_EXTENSION;
+  }
+
+  /**
+   * Loads JNI libraries, if necessary under the current platform.
+   */
+  public static void maybeForceJNI(PathFragment installBase) {
+    if (jniLibsAvailable()) {
+      forceJNI(installBase);
+    }
+  }
+
+  private static boolean jniLibsAvailable() {
+    // JNI libraries work fine on Windows, but at the moment we are not using any.
+    return OS.getCurrent() != OS.WINDOWS;
+  }
+
+  // Force JNI linking at a moment when we have 'installBase' handy, and print
+  // an informative error if it fails.
+  private static void forceJNI(PathFragment installBase) {
+    try {
+      ProcessUtils.getpid(); // force JNI initialization
+    } catch (UnsatisfiedLinkError t) {
+      System.err.println("JNI initialization failed: " + t.getMessage() + ".  "
+          + "Possibly your installation has been corrupted; "
+          + "if this problem persists, try 'rm -fr " + installBase + "'.");
+      throw t;
+    }
+  }
+
+  /**
+   * Returns the PID of the current process, or -1 if not available.
+   */
+  public static int getpid() {
+    if (jniLibsAvailable()) {
+      return ProcessUtils.getpid();
+    }
+    return -1;
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/util/Pair.java b/src/main/java/com/google/devtools/build/lib/util/Pair.java
new file mode 100644
index 0000000000..a377c3c20f
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/util/Pair.java
@@ -0,0 +1,122 @@
+// Copyright 2014 Google Inc. 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.util;
+
+import com.google.common.base.Function;
+
+import java.util.Comparator;
+import java.util.Objects;
+
+import javax.annotation.Nullable;
+
+/**
+ * An immutable, semantic-free ordered pair of nullable values. Avoid using it in public APIs.
+ */
+public final class Pair<A, B> {
+
+  /**
+   * Creates a new pair containing the given elements in order.
+   */
+  public static <A, B> Pair<A, B> of(@Nullable A first, @Nullable B second) {
+    return new Pair<A, B>(first, second);
+  }
+
+  /**
+   * The first element of the pair.
+   */
+  @Nullable
+  public final A first;
+
+  /**
+   * The second element of the pair.
+   */
+  @Nullable
+  public final B second;
+
+  /**
+   * Constructor.  It is usually easier to call {@link #of}.
+   */
+  public Pair(@Nullable A first, @Nullable B second) {
+    this.first = first;
+    this.second = second;
+  }
+
+  @Nullable
+  public A getFirst() {
+    return first;
+  }
+
+  @Nullable
+  public B getSecond() {
+    return second;
+  }
+
+  @Override
+  public String toString() {
+    return "(" + first + ", " + second + ")";
+  }
+
+  @Override
+  public boolean equals(Object o) {
+    if (this == o) {
+      return true;
+    }
+    if (!(o instanceof Pair)) {
+      return false;
+    }
+    Pair<?, ?> p = (Pair<?, ?>) o;
+    return Objects.equals(first, p.first) && Objects.equals(second, p.second);
+  }
+
+  @Override
+  public int hashCode() {
+    return Objects.hash(first, second);
+  }
+
+  /**
+   * A function that maps to the first element in a pair.
+   */
+  public static <A, B> Function<Pair<A, B>, A> firstFunction() {
+    return new Function<Pair<A, B>, A>() {
+      @Override
+      public A apply(Pair<A, B> pair) {
+        return pair.first;
+      }
+    };
+  }
+
+  /**
+   * A function that maps to the second element in a pair.
+   */
+  public static <A, B> Function<Pair<A, B>, B> secondFunction() {
+    return new Function<Pair<A, B>, B>() {
+      @Override
+      public B apply(Pair<A, B> pair) {
+        return pair.second;
+      }
+    };
+  }
+
+  /**
+   * A comparator that compares pairs by comparing the first element.
+   */
+  public static <T extends Comparable<T>, B> Comparator<Pair<T, B>> compareByFirst() {
+    return new Comparator<Pair<T, B>>() {
+      @Override
+      public int compare(Pair<T, B> o1, Pair<T, B> o2) {
+        return o1.first.compareTo(o2.first);
+      }
+    };
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/util/PathFragmentFilter.java b/src/main/java/com/google/devtools/build/lib/util/PathFragmentFilter.java
new file mode 100644
index 0000000000..34f6cd2c95
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/util/PathFragmentFilter.java
@@ -0,0 +1,111 @@
+// Copyright 2014 Google Inc. 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.util;
+
+import com.google.common.base.Joiner;
+import com.google.common.base.Splitter;
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.Lists;
+import com.google.devtools.build.lib.vfs.PathFragment;
+import com.google.devtools.common.options.Converter;
+
+import java.io.Serializable;
+import java.util.ArrayList;
+import java.util.List;
+
+/**
+ * Handles options that specify list of included/excluded directories.
+ * Validates whether path is included in that filter.
+ *
+ * Excluded directories always take precedence over included ones (path depth
+ * and order are not important).
+ */
+public class PathFragmentFilter implements Serializable {
+  private final List<PathFragment> inclusions;
+  private final List<PathFragment> exclusions;
+
+  /**
+   * Converts from a colon-separated list of of paths with optional '-' prefix into the
+   * PathFragmentFilter:
+   *   [-]path1[,[-]path2]...
+   *
+   * Order of paths is not important. Empty entries are ignored. '-' marks an excluded path.
+   */
+  public static class PathFragmentFilterConverter implements Converter<PathFragmentFilter> {
+
+    @Override
+    public PathFragmentFilter convert(String input) {
+      List<PathFragment> inclusionList = new ArrayList<>();
+      List<PathFragment> exclusionList = new ArrayList<>();
+
+      for (String piece : Splitter.on(',').split(input)) {
+        if (piece.length() > 1 && piece.startsWith("-")) {
+          exclusionList.add(new PathFragment(piece.substring(1)));
+        } else if (piece.length() > 0) {
+          inclusionList.add(new PathFragment(piece));
+        }
+      }
+
+      // TODO(bazel-team): (2010) Both lists could be optimized not to include unnecessary
+      // entries - e.g.  entry 'a/b/c' is not needed if 'a/b' is also specified and 'a/b' on
+      // inclusion list is not needed if 'a' or 'a/b' is on exclusion list.
+      return new PathFragmentFilter(inclusionList, exclusionList);
+    }
+
+    @Override
+    public String getTypeDescription() {
+      return "a comma-separated list of paths with prefix '-' specifying excluded paths";
+    }
+
+  }
+
+  /**
+   * Creates new PathFragmentFilter using provided inclusion and exclusion path lists.
+   */
+  public PathFragmentFilter(List<PathFragment> inclusions, List<PathFragment> exclusions) {
+    this.inclusions = ImmutableList.copyOf(inclusions);
+    this.exclusions = ImmutableList.copyOf(exclusions);
+  }
+
+  /**
+   * @return true iff path is included (it is not on the exclusion list and
+   *         it is either on the inclusion list or inclusion list is empty).
+   */
+  public boolean isIncluded(PathFragment path) {
+    for (PathFragment excludedPath : exclusions) {
+      if (path.startsWith(excludedPath)) {
+        return false;
+      }
+    }
+    for (PathFragment includedPath : inclusions) {
+      if (path.startsWith(includedPath)) {
+        return true;
+      }
+    }
+    return inclusions.isEmpty(); // If inclusion filter is not specified, path is included.
+  }
+
+  @Override
+  public String toString() {
+    List<String> list = Lists.newArrayListWithExpectedSize(inclusions.size() + exclusions.size());
+    for (PathFragment path : inclusions) {
+      list.add(path.getPathString());
+    }
+    for (PathFragment path : exclusions) {
+      list.add("-" + path.getPathString());
+    }
+    return Joiner.on(',').join(list);
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/util/PersistentMap.java b/src/main/java/com/google/devtools/build/lib/util/PersistentMap.java
new file mode 100644
index 0000000000..7fd4b6d912
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/util/PersistentMap.java
@@ -0,0 +1,486 @@
+// Copyright 2014 Google Inc. 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.util;
+
+import com.google.common.collect.ForwardingMap;
+import com.google.devtools.build.lib.vfs.FileSystemUtils;
+import com.google.devtools.build.lib.vfs.Path;
+
+import java.io.BufferedInputStream;
+import java.io.BufferedOutputStream;
+import java.io.DataInputStream;
+import java.io.DataOutputStream;
+import java.io.IOException;
+import java.util.HashMap;
+import java.util.Hashtable;
+import java.util.LinkedHashMap;
+import java.util.Map;
+
+/**
+ * A map that is backed by persistent storage. It uses two files on disk for
+ * this: The first file contains all the entries and gets written when invoking
+ * the {@link #save()} method. The second file contains a journal of all entries
+ * that were added to or removed from the map since constructing the instance of
+ * the map or the last invocation of {@link #save()} and gets written after each
+ * update of the map although sub-classes are free to implement their own
+ * journal update strategy.
+ *
+ * <p><b>Ceci n'est pas un Map</b>.  Strictly speaking, the {@link Map}
+ * interface doesn't permit the possibility of failure.  This class uses
+ * persistence; persistence means I/O, and I/O means the possibility of
+ * failure.  Therefore the semantics of this may deviate from the Map contract
+ * in failure cases.  In particular, updates are not guaranteed to succeed.
+ * However, I/O failures are guaranteed to be reported upon the subsequent call
+ * to a method that throws {@code IOException} such as {@link #save}.
+ *
+ * <p>To populate the map entries using the previously persisted entries call
+ * {@link #load()} prior to invoking any other map operation.
+ * <p>
+ * Like {@link Hashtable} but unlike {@link HashMap}, this class does
+ * <em>not</em> allow <tt>null</tt> to be used as a key or a value.
+ * <p>
+ * IO failures during reading or writing the map entries to disk may result in
+ * {@link AssertionError} getting thrown from the failing method.
+ * <p>
+ * The implementation of the map is not synchronized. If access from multiple
+ * threads is required it must be synchronized using an external object.
+ * <p>
+ * The constructor allows passing in a version number that gets written to the
+ * files on disk and checked before reading from disk. Files with an
+ * incompatible version number will be ignored. This allows the client code to
+ * change the persistence format without polluting the file system name space.
+ */
+public abstract class PersistentMap<K, V> extends ForwardingMap<K, V> {
+
+  private static final int MAGIC = 0x20071105;
+
+  private static final int ENTRY_MAGIC = 0xfe;
+
+  private final int version;
+  private final Path mapFile;
+  private final Path journalFile;
+  private final Map<K, V> journal;
+  private DataOutputStream journalOut;
+
+  /**
+   * 'dirty' is true when the in-memory representation of the map is more recent
+   * than the on-disk representation.
+   */
+  private boolean dirty;
+
+  /**
+   * If non-null, contains the message from an {@code IOException} thrown by a
+   * previously failed write.  This error is deferred until the next call to a
+   * method which is able to throw an exception.
+   */
+  private String deferredIOFailure = null;
+
+  /**
+   * 'loaded' is true when the in-memory representation is at least as recent as
+   * the on-disk representation.
+   */
+  private boolean loaded;
+
+  private final Map<K, V> delegate;
+
+  /**
+   * Creates a new PersistentMap instance using the specified backing map.
+   *
+   * @param version the version tag. Changing the version tag allows updating
+   *        the on disk format. The map will never read from a file that was
+   *        written using a different version tag.
+   * @param map the backing map to use for this PersistentMap.
+   * @param mapFile the file to save the map entries to.
+   * @param journalFile the journal file to write entries between invocations of
+   *        {@link #save()}.
+   */
+  public PersistentMap(int version, Map<K, V> map, Path mapFile, Path journalFile) {
+    this.version = version;
+    journal = new LinkedHashMap<>();
+    this.mapFile = mapFile;
+    this.journalFile = journalFile;
+    delegate = map;
+  }
+
+  @Override protected Map<K, V> delegate() {
+    return delegate;
+  }
+
+  @Override
+  public V put(K key, V value) {
+    if (key == null) {
+      throw new NullPointerException();
+    }
+    if (value == null) {
+      throw new NullPointerException();
+    }
+    V previous = delegate().put(key, value);
+    journal.put(key, value);
+    markAsDirty();
+    return previous;
+  }
+
+  /**
+   * Marks the map as dirty and potentially writes updated entries to the
+   * journal.
+   */
+  private void markAsDirty() {
+    dirty = true;
+    if (updateJournal()) {
+      writeJournal();
+    }
+  }
+
+  /**
+   * Determines if the journal should be updated. The default implementation
+   * always returns 'true', but subclasses are free to override this to
+   * implement their own journal updating strategy. For example it is possible
+   * to implement an update at most every five seconds using the following code:
+   *
+   * <pre>
+   * private long nextUpdate;
+   * protected boolean updateJournal() {
+   *   long time = System.currentTimeMillis();
+   *   if (time &gt; nextUpdate) {
+   *     nextUpdate = time + 5 * 1000;
+   *     return true;
+   *   }
+   *   return false;
+   * }
+   * </pre>
+   */
+  protected boolean updateJournal() {
+    return true;
+  }
+
+  @Override
+  @SuppressWarnings("unchecked")
+  public V remove(Object object) {
+    V previous = delegate().remove(object);
+    if (previous != null) {
+      // we know that 'object' must be an instance of K, because the
+      // remove call succeeded, i.e. 'object' was mapped to 'previous'.
+      journal.put((K) object, null); // unchecked
+      markAsDirty();
+    }
+    return previous;
+  }
+
+  /**
+   * Updates the persistent journal by writing all entries to the
+   * {@link #journalOut} stream and clearing the in memory journal.
+   */
+  private void writeJournal() {
+    try {
+      if (journalOut == null) {
+        journalOut = createMapFile(journalFile);
+      }
+      writeEntries(journalOut, journal);
+      journalOut.flush();
+      journal.clear();
+    } catch (IOException e) {
+      this.deferredIOFailure = e.getMessage() + " during journal append";
+    }
+  }
+
+  protected void forceFlush() {
+    if (dirty) {
+      writeJournal();
+    }
+  }
+
+  /**
+   * Load the previous written map entries from disk.
+   *
+   * @param failFast if true, throw IOException rather than silently ignoring.
+   * @throws IOException
+   */
+  public void load(boolean failFast) throws IOException {
+    if (!loaded) {
+      loadEntries(mapFile, failFast);
+      if (journalFile.exists()) {
+        try {
+          loadEntries(journalFile, failFast);
+        } catch (IOException e) {
+          if (failFast) {
+            throw e;
+          }
+          //Else: ignore any errors reading the journal file as it may contain
+          //partial entries.
+        }
+        // Force the map to be dirty, so that we can save it to disk.
+        dirty = true;
+        save(/*fullSave=*/true);
+      } else {
+        dirty = false;
+      }
+      loaded = true;
+    }
+  }
+
+  /**
+   * Load the previous written map entries from disk.
+   *
+   * @throws IOException
+   */
+  public void load() throws IOException {
+    load(/*throwOnLoadFailure=*/false);
+  }
+
+  @Override
+  public void clear() {
+    super.clear();
+    markAsDirty();
+    try {
+      save();
+    } catch (IOException e) {
+      this.deferredIOFailure = e.getMessage() + " during map write";
+    }
+  }
+
+  /**
+   * Saves all the entries of this map to disk and deletes the journal file.
+   *
+   * @throws IOException if there was an I/O error during this call, or any previous call since the
+   *                     last save().
+   */
+  public long save() throws IOException {
+    return save(false);
+  }
+
+  /**
+   * Saves all the entries of this map to disk and deletes the journal file.
+   *
+   * @param fullSave if true, always write the full cache to disk, without the
+   *        journal.
+   * @throws IOException if there was an I/O error during this call, or any
+   *   previous call since the last save().
+   */
+  private long save(boolean fullSave) throws IOException {
+    /* Report a previously failing I/O operation. */
+    if (deferredIOFailure != null) {
+      try {
+        throw new IOException(deferredIOFailure);
+      } finally {
+        deferredIOFailure = null;
+      }
+    }
+    if (dirty) {
+      if (!fullSave && keepJournal()) {
+        forceFlush();
+        journalOut.close();
+        journalOut = null;
+        return journalSize() + cacheSize();
+      } else {
+        dirty = false;
+        Path mapTemp =
+            mapFile.getRelative(FileSystemUtils.replaceExtension(mapFile.asFragment(), ".tmp"));
+        try {
+          saveEntries(delegate(), mapTemp);
+          mapTemp.renameTo(mapFile);
+        } finally {
+          mapTemp.delete();
+        }
+        clearJournal();
+        journalFile.delete();
+        return cacheSize();
+      }
+    } else {
+      return cacheSize();
+    }
+  }
+
+  protected final long journalSize() throws IOException {
+    return journalFile.exists() ? journalFile.getFileSize() : 0;
+  }
+
+  protected final long cacheSize() throws IOException {
+    return mapFile.exists() ? mapFile.getFileSize() : 0;
+  }
+
+  /**
+   * If true, keep the journal during the save(). The journal is flushed, but
+   * the map file is not touched. This may be useful in cases where the journal
+   * is much smaller than the map.
+   */
+  protected boolean keepJournal() {
+    return false;
+  }
+
+  private void clearJournal() throws IOException {
+    journal.clear();
+    if (journalOut != null) {
+      journalOut.close();
+      journalOut = null;
+    }
+  }
+
+  private void loadEntries(Path mapFile, boolean failFast) throws IOException {
+    if (!mapFile.exists()) {
+      return;
+    }
+    DataInputStream in =
+      new DataInputStream(new BufferedInputStream(mapFile.getInputStream()));
+    try {
+      long fileSize = mapFile.getFileSize();
+      if (fileSize < (16)) {
+        if (failFast) {
+          throw new IOException(mapFile + " is too short: Only " + fileSize + " bytes");
+        } else {
+          return;
+        }
+      }
+      if (in.readLong() != MAGIC) { // not a PersistentMap
+        if (failFast) {
+          throw new IOException("Unexpected format");
+        }
+        return;
+      }
+      if (in.readLong() != version) { // PersistentMap version incompatible
+        if (failFast) {
+          throw new IOException("Unexpected format");
+        }
+        return;
+      }
+      readEntries(in, failFast);
+    } finally {
+      in.close();
+    }
+  }
+
+  /**
+   * Saves the entries in the specified map into the specified file.
+   *
+   * @param map the map to be written into the file.
+   * @param mapFile the file the map is written to.
+   * @throws IOException
+   */
+  private void saveEntries(Map<K, V> map, Path mapFile) throws IOException {
+    DataOutputStream out = createMapFile(mapFile);
+    writeEntries(out, map);
+    out.close();
+  }
+
+  /**
+   * Creates the specified file and returns the DataOuputStream suitable for writing entries.
+   *
+   * @param mapFile the file the map is written to.
+   * @return the DataOutputStream that was can be used for saving the map to the file.
+   * @throws IOException
+   */
+  private DataOutputStream createMapFile(Path mapFile) throws IOException {
+    FileSystemUtils.createDirectoryAndParents(mapFile.getParentDirectory());
+    DataOutputStream out =
+      new DataOutputStream(new BufferedOutputStream(mapFile.getOutputStream()));
+    out.writeLong(MAGIC);
+    out.writeLong(version);
+    return out;
+  }
+
+  /**
+   * Writes the Map entries to the specified DataOutputStream.
+   *
+   * @param out the DataOutputStream to write the Map entries to.
+   * @param map the Map containing the entries to be written to the
+   *        DataOutputStream.
+   * @throws IOException
+   */
+  private void writeEntries(DataOutputStream out, Map<K, V> map)
+      throws IOException {
+    for (Map.Entry<K, V> entry : map.entrySet()) {
+      out.writeByte(ENTRY_MAGIC);
+      writeKey(entry.getKey(), out);
+      V value = entry.getValue();
+      boolean isEntry = (value != null);
+      out.writeBoolean(isEntry);
+      if (isEntry) {
+        writeValue(value, out);
+      }
+    }
+  }
+
+  /**
+   * Reads the Map entries from the specified DataInputStream.
+   *
+   * @param failFast if true, throw IOException if entries are in an unexpected
+   *                 format.
+   * @param in the DataInputStream to read the Map entries from.
+   * @throws IOException
+   */
+  private void readEntries(DataInputStream in, boolean failFast) throws IOException {
+    Map<K, V> map = delegate();
+    while (hasEntries(in, failFast)) {
+      K key = readKey(in);
+      boolean isEntry = in.readBoolean();
+      if (isEntry) {
+        V value = readValue(in);
+        map.put(key, value);
+      } else {
+        map.remove(key);
+      }
+    }
+  }
+
+  private boolean hasEntries(DataInputStream in, boolean failFast) throws IOException {
+    if (in.available() <= 0) {
+      return false;
+    } else if (!(in.readUnsignedByte() == ENTRY_MAGIC)) {
+      if (failFast) {
+        throw new IOException("Corrupted entry separator");
+      } else {
+        return false;
+      }
+    }
+    return true;
+  }
+
+  /**
+   * Writes a key of this map into the specified DataOutputStream.
+   *
+   * @param key the key to write to the DataOutputStream.
+   * @param out the DataOutputStream to write the entry to.
+   * @throws IOException
+   */
+  protected abstract void writeKey(K key, DataOutputStream out)
+      throws IOException;
+
+  /**
+   * Writes a value of this map into the specified DataOutputStream.
+   *
+   * @param value the value to write to the DataOutputStream.
+   * @param out the DataOutputStream to write the entry to.
+   * @throws IOException
+   */
+  protected abstract void writeValue(V value, DataOutputStream out)
+      throws IOException;
+
+  /**
+   * Reads an entry of this map from the specified DataInputStream.
+   *
+   * @param in the DataOutputStream to read the entry from.
+   * @return the entry that was read from the DataInputStream.
+   * @throws IOException
+   */
+  protected abstract K readKey(DataInputStream in) throws IOException;
+
+  /**
+   * Reads an entry of this map from the specified DataInputStream.
+   *
+   * @param in the DataOutputStream to read the entry from.
+   * @return the entry that was read from the DataInputStream.
+   * @throws IOException
+   */
+  protected abstract V readValue(DataInputStream in) throws IOException;
+}
diff --git a/src/main/java/com/google/devtools/build/lib/util/ProcMeminfoParser.java b/src/main/java/com/google/devtools/build/lib/util/ProcMeminfoParser.java
new file mode 100644
index 0000000000..44c1112d61
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/util/ProcMeminfoParser.java
@@ -0,0 +1,121 @@
+// Copyright 2014 Google Inc. 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.util;
+
+import com.google.common.annotations.VisibleForTesting;
+import com.google.common.base.CharMatcher;
+import com.google.common.collect.ImmutableMap;
+import com.google.common.io.Files;
+
+import java.io.File;
+import java.io.IOException;
+import java.nio.charset.Charset;
+import java.util.List;
+import java.util.Map;
+
+/**
+ * Parse and return information from /proc/meminfo.
+ */
+public class ProcMeminfoParser {
+
+  public static final String FILE = "/proc/meminfo";
+
+  private final Map<String, Long> memInfo;
+
+  /**
+   * Populates memory information by reading /proc/meminfo.
+   * @throws IOException if reading the file failed.
+   */
+  public ProcMeminfoParser() throws IOException {
+    this(FILE);
+  }
+
+  @VisibleForTesting
+  public ProcMeminfoParser(String fileName) throws IOException {
+    List<String> lines = Files.readLines(new File(fileName), Charset.defaultCharset());
+    ImmutableMap.Builder<String, Long> builder = ImmutableMap.builder();
+    for (String line : lines) {
+      int colon = line.indexOf(":");
+      String keyword = line.substring(0, colon);
+      String valString = line.substring(colon + 1);
+      try {
+        long val =  Long.parseLong(CharMatcher.inRange('0', '9').retainFrom(valString));
+        builder.put(keyword, val);
+      } catch (NumberFormatException e) {
+        // Ignore: we'll fail later if somebody tries to capture this value.
+      }
+    }
+    memInfo = builder.build();
+  }
+
+  /**
+   * Gets a named field in KB.
+   */
+  public long getRamKb(String keyword) {
+    Long val = memInfo.get(keyword);
+    if (val == null) {
+      throw new IllegalArgumentException("Can't locate " + keyword + " in the /proc/meminfo");
+    }
+    return val;
+  }
+
+  /**
+   * Return the total physical memory.
+   */
+  public long getTotalKb() {
+    return getRamKb("MemTotal");
+  }
+
+  /**
+   * Return the inactive memory.
+   */
+  public long getInactiveKb() {
+    return getRamKb("Inactive");
+  }
+
+  /**
+   * Return the active memory.
+   */
+  public long getActiveKb() {
+    return getRamKb("Active");
+  }
+
+  /**
+   * Return the slab memory.
+   */
+  public long getSlabKb() {
+    return getRamKb("Slab");
+  }
+
+  /**
+   * Convert KB to MB.
+   */
+  public static double kbToMb(long kb) {
+    return kb / 1E3;
+  }
+
+  /**
+   * Calculates amount of free RAM from /proc/meminfo content by using
+   * MemTotal - (Active + 0.3*InActive + 0.8*Slab) formula.
+   * Assumption here is that we allow Blaze to use all memory except when
+   * used by active pages, 30% of the inactive pages (since they may become
+   * active at any time) and 80% of memory used by kernel slab heap (since we
+   * want to keep most of the slab heap in the memory but do not want it to
+   * consume all available free memory).
+   */
+  public long getFreeRamKb() {
+    return getTotalKb() - getActiveKb() - (long)(getInactiveKb() * 0.3) - (long)(getSlabKb() * 0.8);
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/util/ProcessUtils.java b/src/main/java/com/google/devtools/build/lib/util/ProcessUtils.java
new file mode 100644
index 0000000000..ec687365ca
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/util/ProcessUtils.java
@@ -0,0 +1,86 @@
+// Copyright 2014 Google Inc. 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.util;
+
+import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
+
+/**
+ * OS Process related utilities.
+ *
+ * <p>Default implementation forwards all requests to
+ * {@link com.google.devtools.build.lib.unix.ProcessUtils}. The default implementation
+ * can be overridden by {@code #setImplementation(ProcessUtilsImpl)} method.
+ */
+@ThreadSafe
+public final class ProcessUtils {
+
+  /**
+   * Describes implementation to which all {@code ProcessUtils} requests are
+   * forwarded.
+   */
+  public interface ProcessUtilsImpl {
+    /** @see ProcessUtils#getgid() */
+    int getgid();
+
+    /** @see ProcessUtils#getpid() */
+    int getpid();
+
+    /** @see ProcessUtils#getuid() */
+    int getuid();
+  }
+
+  private volatile static ProcessUtilsImpl implementation = new ProcessUtilsImpl() {
+
+    @Override
+    public int getgid() {
+      return com.google.devtools.build.lib.unix.ProcessUtils.getgid();
+    }
+
+    @Override
+    public int getpid() {
+      return com.google.devtools.build.lib.unix.ProcessUtils.getpid();
+    }
+
+    @Override
+    public int getuid() {
+      return com.google.devtools.build.lib.unix.ProcessUtils.getuid();
+    }
+  };
+
+  private ProcessUtils() {
+    // prevent construction.
+  }
+
+  /**
+   * @return the real group ID of the current process.
+   */
+  public static int getgid() {
+    return implementation.getgid();
+  }
+
+  /**
+   * @return the process ID of this process.
+   */
+  public static int getpid() {
+    return implementation.getpid();
+  }
+
+  /**
+   * @return the real user ID of the current process.
+   */
+  public static int getuid() {
+    return implementation.getuid();
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/util/RegexFilter.java b/src/main/java/com/google/devtools/build/lib/util/RegexFilter.java
new file mode 100644
index 0000000000..d7c6834ad5
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/util/RegexFilter.java
@@ -0,0 +1,167 @@
+// Copyright 2014 Google Inc. 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.util;
+
+import com.google.common.base.Joiner;
+import com.google.devtools.common.options.Converter;
+import com.google.devtools.common.options.OptionsParsingException;
+
+import java.io.Serializable;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Objects;
+import java.util.regex.Pattern;
+import java.util.regex.PatternSyntaxException;
+
+/**
+ * Handles options that specify list of included/excluded regex expressions.
+ * Validates whether string is included in that filter.
+ *
+ * String is considered to be included into the filter if it does not match
+ * any of the excluded regex expressions and if it matches at least one
+ * included regex expression.
+ */
+public class RegexFilter implements Serializable {
+  private final Pattern inclusionPattern;
+  private final Pattern exclusionPattern;
+  private final int hashCode;
+
+  /**
+   * Converts from a colon-separated list of regex expressions with optional
+   * -/+ prefix into the RegexFilter. Colons prefixed with backslash are
+   * considered to be part of regex definition and not a delimiter between
+   * separate regex expressions.
+   *
+   * Order of expressions is not important. Empty entries are ignored.
+   * '-' marks an excluded expression.
+   */
+  public static class RegexFilterConverter
+      implements Converter<RegexFilter> {
+
+    @Override
+    public RegexFilter convert(String input) throws OptionsParsingException {
+      List<String> inclusionList = new ArrayList<>();
+      List<String> exclusionList = new ArrayList<>();
+
+      for (String piece : input.split("(?<!\\\\),")) { // Split on ',' but not on '\,'
+        piece = piece.replace("\\,", ",");
+        boolean isExcluded = piece.startsWith("-");
+        if (isExcluded || piece.startsWith("+")) {
+          piece = piece.substring(1);
+        }
+        if (piece.length() > 0) {
+          (isExcluded ? exclusionList : inclusionList).add(piece);
+        }
+      }
+
+      try {
+        return new RegexFilter(inclusionList, exclusionList);
+      } catch (PatternSyntaxException e) {
+        throw new OptionsParsingException("Failed to build valid regular expression: "
+            + e.getMessage());
+      }
+    }
+
+    @Override
+    public String getTypeDescription() {
+      return "a comma-separated list of regex expressions with prefix '-' specifying"
+          + " excluded paths";
+    }
+
+  }
+
+  /**
+   * Creates new RegexFilter using provided inclusion and exclusion path lists.
+   */
+  public RegexFilter(List<String> inclusions, List<String> exclusions) {
+    inclusionPattern = convertRegexListToPattern(inclusions);
+    exclusionPattern = convertRegexListToPattern(exclusions);
+    hashCode = Objects.hash(inclusions, exclusions);
+  }
+
+  /**
+   * Converts list of regex expressions into one compiled regex expression.
+   */
+  private static Pattern convertRegexListToPattern(List<String> regexList) {
+    if (regexList.size() == 0) {
+      return null;
+    }
+    // Wrap each individual regex in the independent group, combine them using '|' and
+    // wrap in the non-capturing group.
+    return Pattern.compile("(?:(?>" + Joiner.on(")|(?>").join(regexList) + "))");
+  }
+
+  /**
+   * @return true iff given string is included (it is does not match exclusion
+   *         pattern (if any) and matches inclusionPatter (if any).
+   */
+  public boolean isIncluded(String value) {
+    if (exclusionPattern != null && exclusionPattern.matcher(value).find()) {
+      return false;
+    }
+    if (inclusionPattern == null) {
+      return true;
+    }
+    return inclusionPattern.matcher(value).find();
+  }
+
+  @Override
+  public String toString() {
+    StringBuilder builder = new StringBuilder();
+    if (inclusionPattern != null) {
+      builder.append(inclusionPattern.pattern().replace(",", "\\,"));
+      if (exclusionPattern != null) {
+        builder.append(",");
+      }
+    }
+    if (exclusionPattern != null) {
+      builder.append("-");
+      builder.append(exclusionPattern.pattern().replace(",", "\\,"));
+    }
+    return builder.toString();
+  }
+  
+  @Override
+  public boolean equals(Object other) {
+    if (this == other) {
+      return true;
+    }
+    if (!(other instanceof RegexFilter)) {
+      return false;
+    }
+
+    RegexFilter otherFilter = (RegexFilter) other; 
+    if (this.exclusionPattern == null ^ otherFilter.exclusionPattern == null) {
+      return false;
+    }
+    if (this.inclusionPattern == null ^ otherFilter.inclusionPattern == null) {
+      return false;
+    }
+    if (this.exclusionPattern != null && !this.exclusionPattern.pattern().equals(
+        otherFilter.exclusionPattern.pattern())) {
+      return false;
+    }
+    if (this.inclusionPattern != null && !this.inclusionPattern.pattern().equals(
+        otherFilter.inclusionPattern.pattern())) {
+      return false;
+    }
+    return true;
+  }
+  
+  @Override
+  public int hashCode() {
+    return hashCode;
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/util/ResourceFileLoader.java b/src/main/java/com/google/devtools/build/lib/util/ResourceFileLoader.java
new file mode 100644
index 0000000000..ce26c6c8a8
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/util/ResourceFileLoader.java
@@ -0,0 +1,57 @@
+// Copyright 2014 Google Inc. 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.util;
+
+import static java.nio.charset.StandardCharsets.UTF_8;
+
+import com.google.common.io.ByteStreams;
+
+import java.io.IOException;
+import java.io.InputStream;
+
+/**
+ * A little utility to load resources (property files) from jars or
+ * the classpath. Recommended for longer texts that do not fit nicely into
+ * a piece of Java code - e.g. a template for a lengthy email.
+ */
+public final class ResourceFileLoader {
+
+  private ResourceFileLoader() {}
+
+  /**
+   * Loads a text resource that is located in a directory on the Java classpath that
+   * corresponds to the package of <code>relativeToClass</code> using UTF8 encoding.
+   * E.g.
+   * <code>loadResource(Class.forName("com.google.foo.Foo", "bar.txt"))</code>
+   * will look for <code>com/google/foo/bar.txt</code> in the classpath.
+   */
+  public static String loadResource(Class<?> relativeToClass, String resourceName)
+      throws IOException {
+    ClassLoader loader = relativeToClass.getClassLoader();
+    // TODO(bazel-team): use relativeToClass.getPackage().getName().
+    String className = relativeToClass.getName();
+    String packageName = className.substring(0, className.lastIndexOf('.'));
+    String path = packageName.replace('.', '/');
+    String resource = path + '/' + resourceName;
+    InputStream stream = loader.getResourceAsStream(resource);
+    if (stream == null) {
+      throw new IOException(resourceName + " not found.");
+    }
+    try {
+      return new String(ByteStreams.toByteArray(stream), UTF_8);
+    } finally {
+      stream.close();
+    }
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/util/ResourceUsage.java b/src/main/java/com/google/devtools/build/lib/util/ResourceUsage.java
new file mode 100644
index 0000000000..55807f2395
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/util/ResourceUsage.java
@@ -0,0 +1,353 @@
+// Copyright 2014 Google Inc. 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.util;
+
+import static java.nio.charset.StandardCharsets.US_ASCII;
+
+import com.google.common.base.CharMatcher;
+import com.google.common.base.Splitter;
+import com.google.common.collect.Iterables;
+import com.google.common.io.Files;
+
+import com.sun.management.OperatingSystemMXBean;
+
+import java.io.File;
+import java.io.IOException;
+import java.lang.management.ManagementFactory;
+import java.lang.management.MemoryMXBean;
+import java.util.Iterator;
+
+/**
+ * Provides methods to measure the current resource usage of the current
+ * process. Also provides some convenience methods to obtain several system
+ * characteristics, like number of processors , total memory, etc.
+ */
+public final class ResourceUsage {
+
+  /*
+   * Use com.sun.management.OperatingSystemMXBean instead of
+   * java.lang.management.OperatingSystemMXBean because the latter does not
+   * support getTotalPhysicalMemorySize() and getFreePhysicalMemorySize().
+   */
+  private static final OperatingSystemMXBean OS_BEAN =
+      (OperatingSystemMXBean) ManagementFactory.getOperatingSystemMXBean();
+
+  private static final MemoryMXBean MEM_BEAN = ManagementFactory.getMemoryMXBean();
+  private static final Splitter WHITESPACE_SPLITTER = Splitter.on(CharMatcher.WHITESPACE);
+
+  /**
+   * Calculates an estimate of the current total CPU usage and the CPU usage of
+   * the process in percent measured from the two given measurements. The
+   * returned CPU usages rea average values for the time between the two
+   * measurements. The returned array contains the total CPU usage at index 0
+   * and the CPU usage of the measured process at index 1.
+   */
+  public static float[] calculateCurrentCpuUsage(Measurement oldMeasurement,
+      Measurement newMeasurement) {
+    if (oldMeasurement == null) {
+      return new float[2];
+    }
+    long idleJiffies =
+        newMeasurement.getTotalCpuIdleTimeInJiffies()
+            - oldMeasurement.getTotalCpuIdleTimeInJiffies();
+    long oldProcessJiffies =
+        oldMeasurement.getCpuUtilizationInJiffies()[0]
+            + oldMeasurement.getCpuUtilizationInJiffies()[1];
+    long newProcessJiffies =
+        newMeasurement.getCpuUtilizationInJiffies()[0]
+            + newMeasurement.getCpuUtilizationInJiffies()[1];
+    long processJiffies = newProcessJiffies - oldProcessJiffies;
+    long elapsedTimeJiffies =
+        newMeasurement.getTimeInJiffies() - oldMeasurement.getTimeInJiffies();
+    int processors = getAvailableProcessors();
+    // TODO(bazel-team): Sometimes smaller then zero. Not sure why.
+    double totalUsage = Math.max(0, 1.0D - (double) idleJiffies / elapsedTimeJiffies / processors);
+    double usage = Math.max(0, (double) processJiffies / elapsedTimeJiffies / processors);
+    return new float[] {(float) totalUsage * 100, (float) usage * 100};
+  }
+
+  private ResourceUsage() {
+  }
+
+  /**
+   * Returns the number of processors available to the Java virtual machine.
+   */
+  public static int getAvailableProcessors() {
+    return OS_BEAN.getAvailableProcessors();
+  }
+
+  /**
+   * Returns the total physical memory in bytes.
+   */
+  public static long getTotalPhysicalMemorySize() {
+    return OS_BEAN.getTotalPhysicalMemorySize();
+  }
+
+  /**
+   * Returns the operating system architecture.
+   */
+  public static String getOsArchitecture() {
+    return OS_BEAN.getArch();
+  }
+
+  /**
+   * Returns the operating system name.
+   */
+  public static String getOsName() {
+    return OS_BEAN.getName();
+  }
+
+  /**
+   * Returns the operating system version.
+   */
+  public static String getOsVersion() {
+    return OS_BEAN.getVersion();
+  }
+
+  /**
+   * Returns the initial size of heap memory in bytes.
+   *
+   * @see MemoryMXBean#getHeapMemoryUsage()
+   */
+  public static long getHeapMemoryInit() {
+    return MEM_BEAN.getHeapMemoryUsage().getInit();
+  }
+
+  /**
+   * Returns the initial size of non heap memory in bytes.
+   *
+   * @see MemoryMXBean#getNonHeapMemoryUsage()
+   */
+  public static long getNonHeapMemoryInit() {
+    return MEM_BEAN.getNonHeapMemoryUsage().getInit();
+  }
+
+  /**
+   * Returns the maximum size of heap memory in bytes.
+   *
+   * @see MemoryMXBean#getHeapMemoryUsage()
+   */
+  public static long getHeapMemoryMax() {
+    return MEM_BEAN.getHeapMemoryUsage().getMax();
+  }
+
+  /**
+   * Returns the maximum size of non heap memory in bytes.
+   *
+   * @see MemoryMXBean#getNonHeapMemoryUsage()
+   */
+  public static long getNonHeapMemoryMax() {
+    return MEM_BEAN.getNonHeapMemoryUsage().getMax();
+  }
+
+  /**
+   * Returns a measurement of the current resource usage of the current process.
+   */
+  public static Measurement measureCurrentResourceUsage() {
+    return measureCurrentResourceUsage("self");
+  }
+
+  /**
+   * Returns a measurement of the current resource usage of the process with the
+   * given process id.
+   *
+   * @param processId the process id or <code>self</code> for the current
+   *        process.
+   */
+  public static Measurement measureCurrentResourceUsage(String processId) {
+    return new Measurement(MEM_BEAN.getHeapMemoryUsage().getUsed(), MEM_BEAN.getHeapMemoryUsage()
+        .getCommitted(), MEM_BEAN.getNonHeapMemoryUsage().getUsed(), MEM_BEAN
+        .getNonHeapMemoryUsage().getCommitted(), (float) OS_BEAN.getSystemLoadAverage(), OS_BEAN
+        .getFreePhysicalMemorySize(), getCurrentTotalIdleTimeInJiffies(),
+        getCurrentCpuUtilizationInJiffies(processId));
+  }
+
+  /**
+   * Returns the current total idle time of the processors since system boot.
+   * Reads /proc/stat to obtain this information.
+   */
+  private static long getCurrentTotalIdleTimeInJiffies() {
+    try {
+      File file = new File("/proc/stat");
+      String content = Files.toString(file, US_ASCII);
+      String value = Iterables.get(WHITESPACE_SPLITTER.split(content), 5);
+      return Long.parseLong(value);
+    } catch (NumberFormatException | IOException e) {
+      return 0L;
+    }
+  }
+
+  /**
+   * Returns the current cpu utilization of the current process with the given
+   * id in jiffies. The returned array contains the following information: The
+   * 1st entry is the number of jiffies that the process has executed in user
+   * mode, and the 2nd entry is the number of jiffies that the process has
+   * executed in kernel mode. Reads /proc/self/stat to obtain this information.
+   *
+   * @param processId the process id or <code>self</code> for the current
+   *        process.
+   */
+  private static long[] getCurrentCpuUtilizationInJiffies(String processId) {
+    try {
+      File file = new File("/proc/" + processId + "/stat");
+      if (file.isDirectory()) {
+        return new long[2];
+      }
+      Iterator<String> stat = WHITESPACE_SPLITTER.split(
+          Files.toString(file, US_ASCII)).iterator();
+      for (int i = 0; i < 13; ++i) {
+        stat.next();
+      }
+      long token13 = Long.parseLong(stat.next());
+      long token14 = Long.parseLong(stat.next());
+      return new long[] { token13, token14 };
+    } catch (NumberFormatException e) {
+      return new long[2];
+    } catch (IOException e) {
+      return new long[2];
+    }
+  }
+
+  /**
+   * A snapshot of the resource usage of the current process at a point in time.
+   */
+  public static class Measurement {
+
+    private final long timeInNanos;
+    private final long heapMemoryUsed;
+    private final long heapMemoryCommitted;
+    private final long nonHeapMemoryUsed;
+    private final long nonHeapMemoryCommitted;
+    private final float loadAverageLastMinute;
+    private final long freePhysicalMemory;
+    private final long totalCpuIdleTimeInJiffies;
+    private final long[] cpuUtilizationInJiffies;
+
+    public Measurement(long heapMemoryUsed, long heapMemoryCommitted, long nonHeapMemoryUsed,
+        long nonHeapMemoryCommitted, float loadAverageLastMinute, long freePhysicalMemory,
+        long totalCpuIdleTimeInJiffies, long[] cpuUtilizationInJiffies) {
+      super();
+      timeInNanos = System.nanoTime();
+      this.heapMemoryUsed = heapMemoryUsed;
+      this.heapMemoryCommitted = heapMemoryCommitted;
+      this.nonHeapMemoryUsed = nonHeapMemoryUsed;
+      this.nonHeapMemoryCommitted = nonHeapMemoryCommitted;
+      this.loadAverageLastMinute = loadAverageLastMinute;
+      this.freePhysicalMemory = freePhysicalMemory;
+      this.totalCpuIdleTimeInJiffies = totalCpuIdleTimeInJiffies;
+      this.cpuUtilizationInJiffies = cpuUtilizationInJiffies;
+    }
+
+    /**
+     * Returns the time of the measurement in jiffies.
+     */
+    public long getTimeInJiffies() {
+      return timeInNanos / 10000000;
+    }
+
+    /**
+     * Returns the time of the measurement in ms.
+     */
+    public long getTimeInMs() {
+      return timeInNanos / 1000000;
+    }
+
+    /**
+     * Returns the amount of used heap memory in bytes at the time of
+     * measurement.
+     *
+     * @see MemoryMXBean#getHeapMemoryUsage()
+     */
+    public long getHeapMemoryUsed() {
+      return heapMemoryUsed;
+    }
+
+    /**
+     * Returns the amount of used non heap memory in bytes at the time of
+     * measurement.
+     *
+     * @see MemoryMXBean#getNonHeapMemoryUsage()
+     */
+    public long getHeapMemoryCommitted() {
+      return heapMemoryCommitted;
+    }
+
+    /**
+     * Returns the amount of memory in bytes that is committed for the Java
+     * virtual machine to use for the heap at the time of measurement.
+     *
+     * @see MemoryMXBean#getHeapMemoryUsage()
+     */
+    public long getNonHeapMemoryUsed() {
+      return nonHeapMemoryUsed;
+    }
+
+    /**
+     * Returns the amount of memory in bytes that is committed for the Java
+     * virtual machine to use for non heap memory at the time of measurement.
+     *
+     * @see MemoryMXBean#getNonHeapMemoryUsage()
+     */
+    public long getNonHeapMemoryCommitted() {
+      return nonHeapMemoryCommitted;
+    }
+
+    /**
+     * Returns the system load average for the last minute at the time of
+     * measurement.
+     *
+     * @see OperatingSystemMXBean#getSystemLoadAverage()
+     */
+    public float getLoadAverageLastMinute() {
+      return loadAverageLastMinute;
+    }
+
+    /**
+     * Returns the free physical memmory in bytes at the time of measurement.
+     */
+    public long getFreePhysicalMemory() {
+      return freePhysicalMemory;
+    }
+
+    /**
+     * Returns the current total cpu idle since system boot in jiffies.
+     */
+    public long getTotalCpuIdleTimeInJiffies() {
+      return totalCpuIdleTimeInJiffies;
+    }
+
+    /**
+     * Returns the current cpu utilization of the current process in jiffies.
+     * The returned array contains the following information: The 1st entry is
+     * the number of jiffies that the process has executed in user mode, and the
+     * 2nd entry is the number of jiffies that the process has executed in
+     * kernel mode. Reads /proc/self/stat to obtain this information.
+     */
+    public long[] getCpuUtilizationInJiffies() {
+      return cpuUtilizationInJiffies;
+    }
+
+    /**
+     * Returns the current cpu utilization of the current process in ms. The
+     * returned array contains the following information: The 1st entry is the
+     * number of ms that the process has executed in user mode, and the 2nd
+     * entry is the number of ms that the process has executed in kernel mode.
+     * Reads /proc/self/stat to obtain this information.
+     */
+    public long[] getCpuUtilizationInMs() {
+      return new long[] {cpuUtilizationInJiffies[0] * 10, cpuUtilizationInJiffies[1] * 10};
+    }
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/util/ShellEscaper.java b/src/main/java/com/google/devtools/build/lib/util/ShellEscaper.java
new file mode 100644
index 0000000000..fd23443471
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/util/ShellEscaper.java
@@ -0,0 +1,202 @@
+// Copyright 2014 Google Inc. 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.util;
+
+import com.google.common.base.CharMatcher;
+import com.google.common.base.Function;
+import com.google.common.base.Joiner;
+import com.google.common.collect.Iterables;
+import com.google.common.escape.CharEscaperBuilder;
+import com.google.common.escape.Escaper;
+import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
+
+import java.io.IOException;
+
+/**
+ * Utility class to escape strings for use with shell commands.
+ *
+ * <p>Escaped strings may safely be inserted into shell commands. Escaping is
+ * only done if necessary. Strings containing only shell-neutral characters
+ * will not be escaped.
+ *
+ * <p>This is a replacement for {@code ShellUtils.shellEscape(String)} and
+ * {@code ShellUtils.prettyPrintArgv(java.util.List)} (see
+ * {@link com.google.devtools.build.lib.shell.ShellUtils}). Its advantage is the use
+ * of standard building blocks from the {@code com.google.common.base}
+ * package, such as {@link Joiner} and {@link CharMatcher}, making this class
+ * more efficient and reliable than {@code ShellUtils}.
+ *
+ * <p>The behavior is slightly different though: this implementation will
+ * defensively escape non-ASCII letters and digits, whereas
+ * {@code shellEscape} does not.
+ */
+@Immutable
+public final class ShellEscaper extends Escaper {
+  // Note: extending Escaper may seem desirable, but is in fact harmful.
+  // The class would then need to implement escape(Appendable), returning an Appendable
+  // that escapes everything it receives. In case of shell escaping, we most often join
+  // string parts on spaces, using a Joiner. Spaces are escaped characters. Using the
+  // Appendable returned by escape(Appendable) would escape these spaces too, which
+  // is unwanted.
+
+  public static final ShellEscaper INSTANCE = new ShellEscaper();
+
+  private static final Function<String, String> AS_FUNCTION = INSTANCE.asFunction();
+
+  private static final Joiner SPACE_JOINER = Joiner.on(' ');
+  private static final Escaper STRONGQUOTE_ESCAPER =
+      new CharEscaperBuilder().addEscape('\'', "'\\''").toEscaper();
+  private static final CharMatcher SAFECHAR_MATCHER =
+      CharMatcher.anyOf("@%-_+:,./")
+          .or(CharMatcher.inRange('0', '9'))  // We can't use CharMatcher.JAVA_LETTER_OR_DIGIT,
+          .or(CharMatcher.inRange('a', 'z'))  // that would also accept non-ASCII digits and
+          .or(CharMatcher.inRange('A', 'Z')); // letters.
+
+  /**
+   * Escapes a string by adding strong (single) quotes around it if necessary.
+   *
+   * <p>A string is not escaped iff it only contains safe characters.
+   * The following characters are safe:
+   * <ul>
+   * <li>ASCII letters and digits: [a-zA-Z0-9]
+   * <li>shell-neutral characters: at symbol (@), percent symbol (%),
+   *     dash/minus sign (-), underscore (_), plus sign (+), colon (:),
+   *     comma(,), period (.) and slash (/).
+   * </ul>
+   *
+   * <p>A string is escaped iff it contains at least one non-safe character.
+   * Escaped strings are created by replacing every occurrence of single
+   * quotes with the string '\'' and enclosing the result in a pair of
+   * single quotes.
+   *
+   * <p>Examples:
+   * <ul>
+   * <li>"{@code foo}" becomes "{@code foo}" (remains the same)
+   * <li>"{@code +bar}" becomes "{@code +bar}" (remains the same)
+   * <li>"" becomes "{@code''}" (empty string becomes a pair of strong quotes)
+   * <li>"{@code $BAZ}" becomes "{@code '$BAZ'}"
+   * <li>"{@code quote'd}" becomes "{@code 'quote'\''d'}"
+   * </ul>
+   */
+  @Override
+  public String escape(String unescaped) {
+    final String s = unescaped.toString();
+    if (s.isEmpty()) {
+      // Empty string is a special case: needs to be quoted to ensure that it
+      // gets treated as a separate argument.
+      return "''";
+    } else {
+      return SAFECHAR_MATCHER.matchesAllOf(s)
+          ? s
+          : "'" + STRONGQUOTE_ESCAPER.escape(s) + "'";
+    }
+  }
+
+  public static String escapeString(String unescaped) {
+    return INSTANCE.escape(unescaped);
+  }
+
+  /**
+   * Transforms the input {@code Iterable} of unescaped strings to an
+   * {@code Iterable} of escaped ones. The escaping is done lazily.
+   */
+  public static Iterable<String> escapeAll(Iterable<? extends String> unescaped) {
+    return Iterables.transform(unescaped, AS_FUNCTION);
+  }
+
+  /**
+   * Escapes all strings in {@code argv} individually and joins them on
+   * single spaces into {@code out}. The result is appended directly into
+   * {@code out}, without adding a separator.
+   *
+   * <p>This method works as if by invoking
+   * {@link #escapeJoinAll(Appendable, Iterable, Joiner)} with
+   * {@code Joiner.on(' ')}.
+   *
+   * @param out what the result will be appended to
+   * @param argv the strings to escape and join
+   * @return the same reference as {@code out}, now containing the the
+   *     joined, escaped fragments
+   * @throws IOException if an I/O error occurs while appending
+   */
+  public static Appendable escapeJoinAll(Appendable out, Iterable<? extends String> argv)
+      throws IOException {
+    return SPACE_JOINER.appendTo(out, escapeAll(argv));
+  }
+
+  /**
+   * Escapes all strings in {@code argv} individually and joins them into
+   * {@code out} using the specified {@link Joiner}. The result is appended
+   * directly into {@code out}, without adding a separator.
+   *
+   * <p>The resulting strings are the same as if escaped one by one using
+   * {@link #escapeString(String)}.
+   *
+   * <p>Example: if the joiner is {@code Joiner.on('|')}, then the input
+   * {@code ["abc", "de'f"]} will be escaped as "{@code abc|'de'\''f'}".
+   * If {@code out} initially contains "{@code 123}", then the returned
+   * {@code Appendable} will contain "{@code 123abc|'de'\''f'}".
+   *
+   * @param out what the result will be appended to
+   * @param argv the strings to escape and join
+   * @param joiner the {@link Joiner} to use to join the escaped strings
+   * @return the same reference as {@code out}, now containing the the
+   *     joined, escaped fragments
+   * @throws IOException if an I/O error occurs while appending
+   */
+  public static Appendable escapeJoinAll(Appendable out, Iterable<? extends String> argv,
+      Joiner joiner) throws IOException {
+    return joiner.appendTo(out, escapeAll(argv));
+  }
+
+  /**
+   * Escapes all strings in {@code argv} individually and joins them on
+   * single spaces, then returns the resulting string.
+   *
+   * <p>This method works as if by invoking
+   * {@link #escapeJoinAll(Iterable, Joiner)} with {@code Joiner.on(' ')}.
+   *
+   * <p>Example: {@code ["abc", "de'f"]} will be escaped and joined as
+   * "abc 'de'\''f'".
+   *
+   * @param argv the strings to escape and join
+   * @return the string of escaped and joined input elements
+   */
+  public static String escapeJoinAll(Iterable<? extends String> argv) {
+    return SPACE_JOINER.join(escapeAll(argv));
+  }
+
+  /**
+   * Escapes all strings in {@code argv} individually and joins them using
+   * the specified {@link Joiner}, then returns the resulting string.
+   *
+   * <p>The resulting strings are the same as if escaped one by one using
+   * {@link #escapeString(String)}.
+   *
+   * <p>Example: if the joiner is {@code Joiner.on('|')}, then the input
+   * {@code ["abc", "de'f"]} will be escaped and joined as "abc|'de'\''f'".
+   *
+   * @param argv the strings to escape and join
+   * @param joiner the {@link Joiner} to use to join the escaped strings
+   * @return the string of escaped and joined input elements
+   */
+  public static String escapeJoinAll(Iterable<? extends String> argv, Joiner joiner) {
+    return joiner.join(escapeAll(argv));
+  }
+
+  private ShellEscaper() {
+    // Utility class - do not instantiate.
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/util/StringCanonicalizer.java b/src/main/java/com/google/devtools/build/lib/util/StringCanonicalizer.java
new file mode 100644
index 0000000000..7bdbe7eb63
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/util/StringCanonicalizer.java
@@ -0,0 +1,36 @@
+// Copyright 2014 Google Inc. 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.util;
+
+import com.google.common.collect.Interner;
+import com.google.common.collect.Interners;
+
+/**
+ * Static singleton holder for the string interning pool.  Doesn't use {@link String#intern}
+ * because that consumes permgen space.
+ */
+public final class StringCanonicalizer {
+
+  private static final Interner<String> interner = Interners.newWeakInterner();
+
+  private StringCanonicalizer() {
+  }
+
+  /**
+   * Interns a String.
+   */
+  public final static String intern(String arg) {
+    return interner.intern(arg);
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/util/StringIndexer.java b/src/main/java/com/google/devtools/build/lib/util/StringIndexer.java
new file mode 100644
index 0000000000..cf345d25eb
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/util/StringIndexer.java
@@ -0,0 +1,61 @@
+// Copyright 2014 Google Inc. 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.util;
+
+/**
+ * An object that provides bidirectional String <-> unique integer mapping.
+ */
+public interface StringIndexer {
+
+  /**
+   * Removes all mappings.
+   */
+  public void clear();
+
+  /**
+   * @return some measure of the size of the index.
+   */
+  public int size();
+
+  /**
+   * Creates new mapping for the given string if necessary and returns
+   * string index. Also, as a side effect, zero or more additional mappings
+   * may be created for various prefixes of the given string.
+   *
+   * @return a unique index.
+   */
+  public int getOrCreateIndex(String s);
+
+  /**
+   * @return a unique index for the given string or -1 if string
+   *         was not added.
+   */
+  public int getIndex(String s);
+
+  /**
+   * Creates mapping for the given string if necessary.
+   * Also, as a side effect, zero or more additional mappings may be
+   * created for various prefixes of the given string.
+   *
+   * @return true if new mapping was created, false if mapping already existed.
+   */
+  public boolean addString(String s);
+
+  /**
+   * @return string associated with the given index or null if
+   *         mapping does not exist.
+   */
+  public String getStringForIndex(int i);
+
+}
diff --git a/src/main/java/com/google/devtools/build/lib/util/StringTrie.java b/src/main/java/com/google/devtools/build/lib/util/StringTrie.java
new file mode 100644
index 0000000000..4744c7e31f
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/util/StringTrie.java
@@ -0,0 +1,90 @@
+// Copyright 2014 Google Inc. 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.util;
+
+import com.google.common.base.Preconditions;
+
+
+/**
+ * A trie that operates on path segments of an input string instead of individual characters.
+ *
+ * <p>Only accepts strings that contain only low-ASCII characters (0-127)
+ *
+ * @param <T> the type of the values
+ */
+public class StringTrie<T> {
+  private static final int RANGE = 128;
+
+  @SuppressWarnings("unchecked")
+  private static class Node<T> {
+    private Node() {
+      children = new Node[RANGE];
+    }
+
+    private T value;
+    private Node<T> children[];
+  }
+
+  private final Node<T> root;
+
+  public StringTrie() {
+    root = new Node<T>();
+  }
+
+  /**
+   * Puts a value in the trie.
+   */
+  public void put(CharSequence key, T value) {
+    Node<T> current = root;
+
+    for (int i = 0; i < key.length(); i++) {
+      char ch = key.charAt(i);
+      Preconditions.checkState(ch < RANGE);
+      Node<T> next = current.children[ch];
+      if (next == null) {
+        next = new Node<T>();
+        current.children[ch] = next;
+      }
+
+      current = next;
+    }
+
+    current.value = value;
+  }
+
+  /**
+   * Gets a value from the trie. If there is an entry with the same key, that will be returned,
+   * otherwise, the value corresponding to the key that matches the longest prefix of the input.
+   */
+  public T get(String key) {
+    Node<T> current = root;
+    T lastValue = current.value;
+
+    for (int i = 0; i < key.length(); i++) {
+      char ch = key.charAt(i);
+      Preconditions.checkState(ch < RANGE);
+
+      current = current.children[ch];
+      if (current == null) {
+        break;
+      }
+
+      if (current.value != null) {
+        lastValue = current.value;
+      }
+    }
+
+    return lastValue;
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/util/StringUtil.java b/src/main/java/com/google/devtools/build/lib/util/StringUtil.java
new file mode 100644
index 0000000000..40f7ec14e1
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/util/StringUtil.java
@@ -0,0 +1,175 @@
+// Copyright 2014 Google Inc. 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.util;
+
+import com.google.common.base.Function;
+import com.google.common.base.Joiner;
+import com.google.common.base.Preconditions;
+import com.google.common.base.Splitter;
+import com.google.common.collect.Iterables;
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.Iterator;
+import java.util.List;
+
+/**
+ * Various utility methods operating on strings.
+ */
+public class StringUtil {
+  /**
+   * Creates a comma-separated list of words as in English.
+   *
+   * <p>Example: ["a", "b", "c"] -&gt; "a, b or c".
+   */
+  public static String joinEnglishList(Iterable<?> choices) {
+    return joinEnglishList(choices, "or", "");
+  }
+
+  /**
+   * Creates a comma-separated list of words as in English with the given last-separator.
+   *
+   * <p>Example with lastSeparator="then": ["a", "b", "c"] -&gt; "a, b then c".
+   */
+  public static String joinEnglishList(Iterable<?> choices, String lastSeparator) {
+    return joinEnglishList(choices, lastSeparator, "");
+  }
+
+  /**
+   * Creates a comma-separated list of words as in English with the given last-separator and quotes.
+   *
+   * <p>Example with lastSeparator="then", quote="'": ["a", "b", "c"] -&gt; "'a', 'b' then 'c'".
+   */
+  public static String joinEnglishList(Iterable<?> choices, String lastSeparator, String quote) {
+    StringBuilder buf = new StringBuilder();
+    for (Iterator<?> ii = choices.iterator(); ii.hasNext(); ) {
+      Object choice = ii.next();
+      if (buf.length() > 0) {
+        buf.append(ii.hasNext() ? "," : " " + lastSeparator);
+        buf.append(" ");
+      }
+      buf.append(quote).append(choice).append(quote);
+    }
+    return buf.length() == 0 ? "nothing" : buf.toString();
+  }
+
+  /**
+   * Split a single space-separated string into a List of values.
+   *
+   * <p>Individual values are canonicalized such that within and
+   * across calls to this method, equal values point to the same
+   * object.
+   *
+   * <p>If the input is null, return an empty list.
+   *
+   * @param in space-separated list of values, eg "value1   value2".
+   */
+  public static List<String> splitAndInternString(String in) {
+    List<String> result = new ArrayList<>();
+    if (in == null) {
+      return result;
+    }
+    for (String val : Splitter.on(" ").omitEmptyStrings().split(in)) {
+      // Note that splitter returns a substring(), effectively
+      // retaining the entire "in" String. Make an explicit copy here
+      // to avoid that memory pitfall. Further, because there may be
+      // many concurrent submissions that touch the same files,
+      // attempt to use a single reference for equal strings via the
+      // deduplicator.
+      result.add(StringCanonicalizer.intern(new String(val)));
+    }
+    return result;
+  }
+
+  /**
+   * Lists items up to a given limit, then prints how many were omitted.
+   */
+  public static StringBuilder listItemsWithLimit(StringBuilder appendTo, int limit,
+      Collection<?> items) {
+    Preconditions.checkState(limit > 0);
+    Joiner.on(", ").appendTo(appendTo, Iterables.limit(items, limit));
+    if (items.size() > limit) {
+      appendTo.append(" ...(omitting ")
+          .append(items.size() - limit)
+          .append(" more item(s))");
+    }
+    return appendTo;
+  }
+
+  /**
+   * Returns the ordinal representation of the number.
+   */
+  public static String ordinal(int number) {
+    switch (number) {
+      case 1:
+        return "1st";
+      case 2:
+        return "2nd";
+      case 3:
+        return "3rd";
+      default:
+        return number + "th";
+    }
+  }
+
+  /**
+   * Appends a prefix and a suffix to each of the Strings.
+   */
+  public static Iterable<String> append(Iterable<String> values, final String prefix,
+      final String suffix) {
+  return Iterables.transform(values, new Function<String, String>() {
+      @Override
+      public String apply(String input) {
+        return prefix + input + suffix;
+      }
+    });
+  }
+
+  /**
+   * Indents the specified string by the given number of characters.
+   *
+   * <p>The beginning of the string before the first newline is not indented.
+   */
+  public static String indent(String input, int depth) {
+    StringBuilder prefix = new StringBuilder();
+    prefix.append("\n");
+    for (int i = 0; i < depth; i++) {
+      prefix.append(" ");
+    }
+
+    return input.replace("\n", prefix);
+  }
+
+  /**
+   * Strips a suffix from a string. If the string does not end with the suffix, returns null.
+   */
+  public static String stripSuffix(String input, String suffix) {
+    return input.endsWith(suffix)
+        ? input.substring(0, input.length() - suffix.length())
+        : null;
+  }
+
+  /**
+   * Capitalizes the first character of a string.
+   */
+  public static String capitalize(String input) {
+    if (input.isEmpty()) {
+      return input;
+    }
+
+    char first = input.charAt(0);
+    char capitalized = Character.toUpperCase(first);
+    return first == capitalized ? input : capitalized + input.substring(1);
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/util/StringUtilities.java b/src/main/java/com/google/devtools/build/lib/util/StringUtilities.java
new file mode 100644
index 0000000000..9ac1d35696
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/util/StringUtilities.java
@@ -0,0 +1,207 @@
+// Copyright 2014 Google Inc. 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.util;
+
+import com.google.common.base.Joiner;
+import com.google.common.collect.ImmutableList;
+import com.google.common.escape.CharEscaperBuilder;
+import com.google.common.escape.Escaper;
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.List;
+import java.util.Map;
+
+/**
+ * Various utility methods operating on strings.
+ */
+public class StringUtilities {
+
+  private static final Joiner NEWLINE_JOINER = Joiner.on('\n');
+
+  private static final Escaper KEY_ESCAPER = new CharEscaperBuilder()
+      .addEscape('!', "!!")
+      .addEscape('<', "!<")
+      .addEscape('>', "!>")
+      .toEscaper();
+
+  private static final Escaper CONTROL_CHAR_ESCAPER = new CharEscaperBuilder()
+      .addEscape('\r', "\\r")
+      .addEscapes(new char[] {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, /*13=\r*/
+          14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 127}, "<?>")
+      .toEscaper();
+
+  /**
+   * Java doesn't have multiline string literals, so having to join a bunch
+   * of lines is a very common problem. So, here's a static method that we
+   * can static import in such situations.
+   */
+  public static String joinLines(String... lines) {
+    return NEWLINE_JOINER.join(lines);
+  }
+
+  /**
+   * A corollary to {@link #joinLines(String[])} for collections.
+   */
+  public static String joinLines(Collection<String> lines) {
+    return NEWLINE_JOINER.join(lines);
+  }
+
+  /**
+   * combineKeys(x1, ..., xn):
+   *   Computes a string that encodes the sequence
+   *   x1, ..., xn.  Distinct sequences map to distinct strings.
+   *
+   *   The encoding is intended to be vaguely human-readable.
+   */
+  public static String combineKeys(Iterable<String> parts) {
+    final StringBuilder buf = new StringBuilder(128);
+    for (String part : parts) {
+      // We enclose each part in angle brackets to separate them.  Some
+      // trickiness is required to ensure that the result is unique (distinct
+      // sequences map to distinct strings): we escape any angle bracket
+      // characters in the parts by preceding them with an escape character
+      // (we use "!") and we also need to escape any escape characters.
+      buf.append('<');
+      buf.append(KEY_ESCAPER.escape(part));
+      buf.append('>');
+    }
+    return buf.toString();
+  }
+
+  /**
+   * combineKeys(x1, ..., xn):
+   *   Computes a string that encodes the sequence
+   *   x1, ..., xn.  Distinct sequences map to distinct strings.
+   *
+   *   The encoding is intended to be vaguely human-readable.
+   */
+  public static String combineKeys(String... parts) {
+    return combineKeys(ImmutableList.copyOf(parts));
+  }
+
+  /**
+   * Replaces all occurrences of 'literal' in 'input' with 'replacement'.
+   * Like {@link String#replaceAll(String, String)} but for literal Strings
+   * instead of regular expression patterns.
+   *
+   * @param input the input String
+   * @param literal the literal String to replace in 'input'.
+   * @param replacement the replacement String to replace 'literal' in 'input'.
+   * @return the 'input' String with all occurrences of 'literal' replaced with
+   *        'replacement'.
+   */
+  public static String replaceAllLiteral(String input, String literal,
+                                         String replacement) {
+    int literalLength = literal.length();
+    if (literalLength == 0) {
+      return input;
+    }
+    StringBuilder result = new StringBuilder(
+        input.length() + replacement.length());
+    int start = 0;
+    int index = 0;
+
+    while ((index = input.indexOf(literal, start)) >= 0) {
+      result.append(input.substring(start, index));
+      result.append(replacement);
+      start = index + literalLength;
+    }
+    result.append(input.substring(start));
+    return result.toString();
+  }
+
+  /**
+   * Creates a simple key-value table of the form
+   *
+   * <pre>
+   * key: some value
+   * another key: some other value
+   * yet another key: and so on ...
+   * </pre>
+   *
+   * The return value will not include a final {@code "\n"}.
+   */
+  public static String layoutTable(Map<String, String> data) {
+    List<String> tableLines = new ArrayList<>();
+    for (Map.Entry<String, String> entry : data.entrySet()) {
+      tableLines.add(entry.getKey() + ": " + entry.getValue());
+    }
+    return NEWLINE_JOINER.join(tableLines);
+  }
+
+  /**
+   * Returns an easy-to-read string approximation of a number of bytes,
+   * e.g. "21MB".  Note, these are IEEE units, i.e. decimal not binary powers.
+   */
+  public static String prettyPrintBytes(long bytes) {
+    if (bytes < 1E4) {  // up to 10KB
+      return bytes + "B";
+    } else if (bytes < 1E7) {  // up to 10MB
+      return ((int) (bytes / 1E3)) + "KB";
+    } else if (bytes < 1E11) {  // up to 100GB
+      return ((int) (bytes / 1E6)) + "MB";
+    } else {
+      return ((int) (bytes / 1E9)) + "GB";
+    }
+  }
+
+  /**
+   * Returns true if 'source' contains 'target' as a sub-array.
+   */
+  public static boolean containsSubarray(char[] source, char[] target) {
+    if (target.length > source.length) {
+      return false;
+    }
+    for (int i = 0; i < source.length - target.length + 1; i++) {
+      boolean matches = true;
+      for (int j = 0; j < target.length; j++) {
+        if (source[i + j] != target[j]) {
+          matches = false;
+          break;
+        }
+      }
+      if (matches) {
+        return true;
+      }
+    }
+    return false;
+  }
+
+  /**
+   * Replace control characters with visible strings.
+   * @return the sanitized string.
+   */
+  public static String sanitizeControlChars(String message) {
+    return CONTROL_CHAR_ESCAPER.escape(message);
+  }
+
+  /**
+   * Converts a Java style function name to a Python style function name the following way:
+   * every upper case character gets replaced with an underscore and its lower case counterpart.
+   * <p>E.g. fooBar --> foo_bar 
+   */
+  public static String toPythonStyleFunctionName(String javaStyleFunctionName) {
+    StringBuilder sb = new StringBuilder();
+    for (int i = 0; i < javaStyleFunctionName.length(); i++) {
+      char c = javaStyleFunctionName.charAt(i);
+      if (Character.isUpperCase(c)) {
+        sb.append('_').append(Character.toLowerCase(c));
+      } else {
+        sb.append(c);
+      }
+    }
+    return sb.toString();
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/util/ThreadUtils.java b/src/main/java/com/google/devtools/build/lib/util/ThreadUtils.java
new file mode 100644
index 0000000000..7b8ebed8bd
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/util/ThreadUtils.java
@@ -0,0 +1,50 @@
+// Copyright 2014 Google Inc. 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.util;
+
+
+import java.util.Map;
+import java.util.logging.Level;
+import java.util.logging.Logger;
+
+/**
+ * Utility methods relating to threads and stack traces.
+ */
+public class ThreadUtils {
+  private static final Logger LOG = Logger.getLogger(ThreadUtils.class.getName());
+
+  private ThreadUtils() {
+  }
+
+  /** Write a thread dump to the blaze.INFO log if interrupt took too long. */
+  public static void warnAboutSlowInterrupt() {
+    LOG.warning("Interrupt took too long. Dumping thread state.");
+    for (Map.Entry <Thread, StackTraceElement[]> e : Thread.getAllStackTraces().entrySet()) {
+      Thread t = e.getKey();
+      LOG.warning("\"" + t.getName() + "\"" + " "
+          + " Thread id=" + t.getId() + " " + t.getState());
+      for (StackTraceElement line : e.getValue()) {
+        LOG.warning("\t" + line);
+      }
+      LOG.warning("");
+    }
+    LoggingUtil.logToRemote(Level.WARNING, "Slow interrupt", new SlowInterruptException());
+  }
+
+  private static final class SlowInterruptException extends RuntimeException {
+    public SlowInterruptException() {
+      super("Slow interruption...");
+    }
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/util/TimeUtilities.java b/src/main/java/com/google/devtools/build/lib/util/TimeUtilities.java
new file mode 100644
index 0000000000..689744a36f
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/util/TimeUtilities.java
@@ -0,0 +1,41 @@
+// Copyright 2014 Google Inc. 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.util;
+
+/**
+ * Various utility methods operating on time values.
+ */
+public class TimeUtilities {
+
+  private TimeUtilities() {
+  }
+
+  /**
+   * Converts time to the user-friendly string representation.
+   *
+   * @param timeInNs The length of time in nanoseconds.
+   */
+  public static String prettyTime(long timeInNs) {
+    double ms = timeInNs / 1000000.0;
+    if (ms < 10.0) {
+      return String.format("%.2f ms", ms);
+    } else if (ms < 100.0) {
+      return String.format("%.1f ms", ms);
+    } else if (ms < 1000.0) {
+      return String.format("%.0f ms", ms);
+    }
+    return String.format("%.3f s", ms / 1000.0);
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/util/UserUtils.java b/src/main/java/com/google/devtools/build/lib/util/UserUtils.java
new file mode 100644
index 0000000000..93e2a662af
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/util/UserUtils.java
@@ -0,0 +1,58 @@
+// Copyright 2014 Google Inc. 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.util;
+
+import com.google.common.base.Strings;
+
+import java.util.Map;
+
+/**
+ * User information utility methods.
+ */
+public final class UserUtils {
+
+  private static final String ORIGINATING_USER_KEY = "BLAZE_ORIGINATING_USER";
+
+  private UserUtils() {
+    // prohibit instantiation
+  }
+
+  private static class Holder {
+    static final String userName = System.getProperty("user.name");
+  }
+
+  /**
+   * Returns the user name as provided by system property 'user.name'.
+   */
+  public static String getUserName() {
+    return Holder.userName;
+  }
+
+  /**
+   * Returns the originating user for this build from the command-line or the environment.
+   */
+  public static String getOriginatingUser(String originatingUser,
+                                          Map<String, String> clientEnv) {
+    if (!Strings.isNullOrEmpty(originatingUser)) {
+      return originatingUser;
+    }
+
+    if (!Strings.isNullOrEmpty(clientEnv.get(ORIGINATING_USER_KEY))) {
+      return clientEnv.get(ORIGINATING_USER_KEY);
+    }
+
+    return UserUtils.getUserName();
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/util/VarInt.java b/src/main/java/com/google/devtools/build/lib/util/VarInt.java
new file mode 100644
index 0000000000..fd5daab4d4
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/util/VarInt.java
@@ -0,0 +1,286 @@
+// Copyright 2014 Google Inc. 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.util;
+
+import java.io.IOException;
+import java.io.InputStream;
+import java.io.OutputStream;
+import java.nio.ByteBuffer;
+
+/**
+ * Common methods to encode and decode varints and varlongs into ByteBuffers and
+ * arrays.
+ */
+public class VarInt {
+
+  /**
+   * Maximum encoded size of 32-bit positive integers (in bytes)
+   */
+  public static final int MAX_VARINT_SIZE = 5;
+
+  /**
+   * maximum encoded size of 64-bit longs, and negative 32-bit ints (in bytes)
+   */
+  public static final int MAX_VARLONG_SIZE = 10;
+
+  private VarInt() { }
+
+  /** Returns the encoding size in bytes of its input value.
+   * @param i the integer to be measured
+   * @return the encoding size in bytes of its input value
+   */
+  public static int varIntSize(int i) {
+    int result = 0;
+    do {
+      result++;
+      i >>>= 7;
+    } while (i != 0);
+    return result;
+  }
+
+  /**
+   * Reads a varint  from src, places its values into the first element of
+   * dst and returns the offset in to src of the first byte after the varint.
+   *
+   * @param src source buffer to retrieve from
+   * @param offset offset within src
+   * @param dst the resulting int value
+   * @return the updated offset after reading the varint
+   */
+  public static int getVarInt(byte[] src, int offset, int[] dst) {
+    int result = 0;
+    int shift = 0;
+    int b;
+    do {
+      if (shift >= 32) {
+        // Out of range
+        throw new IndexOutOfBoundsException("varint too long");
+      }
+      // Get 7 bits from next byte
+      b = src[offset++];
+      result |= (b & 0x7F) << shift;
+      shift += 7;
+    } while ((b & 0x80) != 0);
+    dst[0] = result;
+    return offset;
+  }
+
+  /**
+   * Encodes an integer in a variable-length encoding, 7 bits per byte, into a
+   * destination byte[], following the protocol buffer convention.
+   *
+   * @param v the int value to write to sink
+   * @param sink the sink buffer to write to
+   * @param offset the offset within sink to begin writing
+   * @return the updated offset after writing the varint
+   */
+  public static int putVarInt(int v, byte[] sink, int offset) {
+    do {
+      // Encode next 7 bits + terminator bit
+      int bits = v & 0x7F;
+      v >>>= 7;
+      byte b = (byte) (bits + ((v != 0) ? 0x80 : 0));
+      sink[offset++] = b;
+    } while (v != 0);
+    return offset;
+  }
+
+  /**
+   * Reads a varint from the current position of the given ByteBuffer and
+   * returns the decoded value as 32 bit integer.
+   *
+   * <p>The position of the buffer is advanced to the first byte after the
+   * decoded varint.
+   *
+   * @param src the ByteBuffer to get the var int from
+   * @return The integer value of the decoded varint
+   */
+  public static int getVarInt(ByteBuffer src) {
+    int tmp;
+    if ((tmp = src.get()) >= 0) {
+      return tmp;
+    }
+    int result = tmp & 0x7f;
+    if ((tmp = src.get()) >= 0) {
+      result |= tmp << 7;
+    } else {
+      result |= (tmp & 0x7f) << 7;
+      if ((tmp = src.get()) >= 0) {
+        result |= tmp << 14;
+      } else {
+        result |= (tmp & 0x7f) << 14;
+        if ((tmp = src.get()) >= 0) {
+          result |= tmp << 21;
+        } else {
+          result |= (tmp & 0x7f) << 21;
+          result |= (tmp = src.get()) << 28;
+          while (tmp < 0) {
+            // We get into this loop only in the case of overflow.
+            // By doing this, we can call getVarInt() instead of
+            // getVarLong() when we only need an int.
+            tmp = src.get();
+          }
+        }
+      }
+    }
+    return result;
+  }
+
+  /**
+   * Encodes an integer in a variable-length encoding, 7 bits per byte, to a
+   * ByteBuffer sink.
+   * @param v the value to encode
+   * @param sink the ByteBuffer to add the encoded value
+   */
+  public static void putVarInt(int v, ByteBuffer sink) {
+    while (true) {
+      int bits = v & 0x7f;
+      v >>>= 7;
+      if (v == 0) {
+        sink.put((byte) bits);
+        return;
+      }
+      sink.put((byte) (bits | 0x80));
+    }
+  }
+
+  /**
+   * Reads a varint from the given InputStream and returns the decoded value
+   * as an int.
+   *
+   * @param inputStream the InputStream to read from
+   */
+  public static int getVarInt(InputStream inputStream) throws IOException {
+    int result = 0;
+    int shift = 0;
+    int b;
+    do {
+      if (shift >= 32) {
+        // Out of range
+        throw new IndexOutOfBoundsException("varint too long");
+      }
+      // Get 7 bits from next byte
+      b = inputStream.read();
+      result |= (b & 0x7F) << shift;
+      shift += 7;
+    } while ((b & 0x80) != 0);
+    return result;
+  }
+
+  /**
+   * Encodes an integer in a variable-length encoding, 7 bits per byte, and
+   * writes it to the given OutputStream.
+   *
+   * @param v the value to encode
+   * @param outputStream the OutputStream to write to
+   */
+  public static void putVarInt(int v, OutputStream outputStream) throws IOException {
+    byte[] bytes = new byte[varIntSize(v)];
+    putVarInt(v, bytes, 0);
+    outputStream.write(bytes);
+  }
+
+  /**
+   * Returns the encoding size in bytes of its input value.
+   *
+   * @param v the long to be measured
+   * @return the encoding size in bytes of a given long value.
+   */
+  public static int varLongSize(long v) {
+    int result = 0;
+    do {
+      result++;
+      v >>>= 7;
+    } while (v != 0);
+    return result;
+  }
+
+  /**
+   * Reads an up to 64 bit long varint from the current position of the
+   * given ByteBuffer and returns the decoded value as long.
+   *
+   * <p>The position of the buffer is advanced to the first byte after the
+   * decoded varint.
+   *
+   * @param src the ByteBuffer to get the var int from
+   * @return The integer value of the decoded long varint
+   */
+  public static long getVarLong(ByteBuffer src) {
+    long tmp;
+    if ((tmp = src.get()) >= 0) {
+      return tmp;
+    }
+    long result = tmp & 0x7f;
+    if ((tmp = src.get()) >= 0) {
+      result |= tmp << 7;
+    } else {
+      result |= (tmp & 0x7f) << 7;
+      if ((tmp = src.get()) >= 0) {
+        result |= tmp << 14;
+      } else {
+        result |= (tmp & 0x7f) << 14;
+        if ((tmp = src.get()) >= 0) {
+          result |= tmp << 21;
+        } else {
+          result |= (tmp & 0x7f) << 21;
+          if ((tmp = src.get()) >= 0) {
+            result |= tmp << 28;
+          } else {
+            result |= (tmp & 0x7f) << 28;
+            if ((tmp = src.get()) >= 0) {
+              result |= tmp << 35;
+            } else {
+              result |= (tmp & 0x7f) << 35;
+              if ((tmp = src.get()) >= 0) {
+                result |= tmp << 42;
+              } else {
+                result |= (tmp & 0x7f) << 42;
+                if ((tmp = src.get()) >= 0) {
+                  result |= tmp << 49;
+                } else {
+                  result |= (tmp & 0x7f) << 49;
+                  if ((tmp = src.get()) >= 0) {
+                    result |= tmp << 56;
+                  } else {
+                    result |= (tmp & 0x7f) << 56;
+                    result |= ((long) src.get()) << 63;
+                  }
+                }
+              }
+            }
+          }
+        }
+      }
+    }
+    return result;
+  }
+
+  /**
+   * Encodes a long integer in a variable-length encoding, 7 bits per byte, to a
+   * ByteBuffer sink.
+   * @param v the value to encode
+   * @param sink the ByteBuffer to add the encoded value
+   */
+  public static void putVarLong(long v, ByteBuffer sink) {
+    while (true) {
+      int bits = ((int) v) & 0x7f;
+      v >>>= 7;
+      if (v == 0) {
+        sink.put((byte) bits);
+        return;
+      }
+      sink.put((byte) (bits | 0x80));
+    }
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/util/io/AnsiTerminal.java b/src/main/java/com/google/devtools/build/lib/util/io/AnsiTerminal.java
new file mode 100644
index 0000000000..93bc12af10
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/util/io/AnsiTerminal.java
@@ -0,0 +1,198 @@
+// Copyright 2014 Google Inc. 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.util.io;
+
+import java.io.IOException;
+import java.io.OutputStream;
+
+/**
+ * A class which encapsulates the fancy curses-type stuff that you can do using
+ * standard ANSI terminal control sequences.
+ */
+public class AnsiTerminal {
+  private static final byte[] ESC = {27, (byte) '['};
+  private static final byte BEL = 7;
+  private static final byte UP = (byte) 'A';
+  private static final byte ERASE_LINE = (byte) 'K';
+  private static final byte SET_GRAPHICS = (byte) 'm';
+  private static final byte TEXT_BOLD = (byte) '1';
+  private static final byte[] SET_TERM_TITLE = {27, (byte) ']', (byte) '0', (byte) ';'};
+
+  public static final String FG_BLACK = "30";
+  public static final String FG_RED = "31";
+  public static final String FG_GREEN = "32";
+  public static final String FG_YELLOW = "33";
+  public static final String FG_BLUE = "34";
+  public static final String FG_MAGENTA = "35";
+  public static final String FG_CYAN = "36";
+  public static final String FG_GRAY = "37";
+  public static final String BG_BLACK = "40";
+  public static final String BG_RED = "41";
+  public static final String BG_GREEN = "42";
+  public static final String BG_YELLOW = "43";
+  public static final String BG_BLUE = "44";
+  public static final String BG_MAGENTA = "45";
+  public static final String BG_CYAN = "46";
+  public static final String BG_GRAY = "47";
+
+  public static byte[] CR = { 13 };
+
+  private final OutputStream out;
+
+  /**
+   * Creates an AnsiTerminal object wrapping an output stream which is going to
+   * be displayed in an ANSI compatible terminal or shell window.
+   *
+   * @param out the output stream
+   */
+  public AnsiTerminal(OutputStream out) {
+    this.out = out;
+  }
+
+  /**
+   * Moves the cursor upwards by a specified number of lines. This will not
+   * cause any scrolling if it tries to move above the top of the terminal
+   * window.
+   */
+  public void cursorUp(int numLines) throws IOException {
+    writeBytes(ESC, ("" + numLines).getBytes(), new byte[] { UP });
+  }
+
+  /**
+   * Clear the current terminal line from the cursor position to the end.
+   */
+  public void clearLine() throws IOException {
+    writeEscapeSequence(ERASE_LINE);
+  }
+
+  /**
+   * Makes any text output to the terminal appear in bold.
+   */
+  public void textBold() throws IOException {
+    writeEscapeSequence(TEXT_BOLD,  SET_GRAPHICS);
+  }
+
+  /**
+   * Set the color of the foreground or background of the terminal.
+   *
+   * @param color one of the foreground or background color
+   * constants
+   */
+  public void setTextColor(String color) throws IOException {
+    writeBytes(ESC, color.getBytes(), new byte[] { SET_GRAPHICS });
+  }
+
+  /**
+   * Resets the terminal colors and fonts to defaults.
+   */
+  public void resetTerminal() throws IOException {
+    writeEscapeSequence((byte)'0', (byte)'m');
+  }
+
+  /**
+   * Makes text print on the terminal in red.
+   */
+  public void textRed() throws IOException {
+    setTextColor(FG_RED);
+  }
+
+  /**
+   * Makes text print on the terminal in blue.
+   */
+  public void textBlue() throws IOException {
+    setTextColor(FG_BLUE);
+  }
+
+  /**
+   * Makes text print on the terminal in red.
+   */
+  public void textGreen() throws IOException {
+    setTextColor(FG_GREEN);
+  }
+
+  /**
+   * Makes text print on the terminal in red.
+   */
+  public void textMagenta() throws IOException {
+    setTextColor(FG_MAGENTA);
+  }
+
+  /**
+   * Set the terminal title.
+   */
+  public void setTitle(String title) throws IOException {
+    writeBytes(SET_TERM_TITLE, title.getBytes(), new byte[] { BEL });
+  }
+
+  /**
+   * Writes a string to the terminal using the current font, color and cursor
+   * position settings.
+   *
+   * @param text the text to write
+   */
+  public void writeString(String text) throws IOException {
+    out.write(text.getBytes());
+  }
+
+  /**
+   * Writes a byte sequence to the terminal using the current font, color and
+   * cursor position settings.
+   *
+   * @param bytes the bytes to write
+   */
+  public void writeBytes(byte[] bytes) throws IOException {
+    out.write(bytes);
+  }
+
+  /**
+   * Utility method which makes it easier to generate the control sequences for
+   * the terminal.
+   *
+   * @param bytes bytes which should be prefixed with the terminal escape
+   *        sequence to produce a valid control sequence
+   */
+  private void writeEscapeSequence(byte... bytes) throws IOException {
+    writeBytes(ESC, bytes);
+  }
+
+  /**
+   * Utility method for generating control sequences. Takes a collection of byte
+   * arrays, which contain the components of a control sequence, concatenates
+   * them, and prints them to the terminal.
+   *
+   * @param stuff the byte arrays that make up the sequence to be sent to the
+   *        terminal
+   */
+  private void writeBytes(byte[]... stuff) throws IOException {
+    for (byte[] bytes : stuff) {
+      out.write(bytes);
+    }
+  }
+
+  /**
+   * Sends a carriage return to the terminal.
+   */
+  public void cr() throws IOException {
+    writeBytes(CR);
+  }
+
+  /**
+   * Flushes the underlying stream.
+   * This class does not do any buffering of its own, but the underlying
+   * OutputStream may.
+   */
+  public void flush() throws IOException {
+    out.flush();
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/util/io/AnsiTerminalPrinter.java b/src/main/java/com/google/devtools/build/lib/util/io/AnsiTerminalPrinter.java
new file mode 100644
index 0000000000..726c5dd701
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/util/io/AnsiTerminalPrinter.java
@@ -0,0 +1,156 @@
+// Copyright 2014 Google Inc. 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.util.io;
+
+import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadCompatible;
+
+import java.io.IOException;
+import java.io.OutputStream;
+import java.io.PrintWriter;
+import java.util.EnumSet;
+import java.util.logging.Logger;
+import java.util.regex.Pattern;
+
+/**
+ * Allows to print "colored" strings by parsing predefined string keywords,
+ * which, depending on the useColor value are either replaced with ANSI terminal
+ * coloring sequences (as defined by the {@link AnsiTerminal} class) or stripped.
+ *
+ * Supported keywords are defined by the enum {@link AnsiTerminalPrinter.Mode}.
+ * Following keywords are supported:
+ *   INFO  - switches color to green.
+ *   ERROR - switches color to bold red.
+ *   WARNING - switches color to magenta.
+ *   NORMAL - resets terminal to the default state.
+ *
+ * Each keyword is starts with prefix "{#" followed by the enum constant name
+ * and suffix "#}". Keywords should not be inserted manually - provided enum
+ * constants should be used instead.
+ */
+@ThreadCompatible
+public class AnsiTerminalPrinter {
+
+  private static final String MODE_PREFIX = "{#";
+  private static final String MODE_SUFFIX = "#}";
+
+  // Mode pattern must match MODE_PREFIX and do lookahead for the rest of the
+  // mode string.
+  private static final String MODE_PATTERN = "\\{\\#(?=[A-Z]+\\#\\})";
+
+  /**
+   * List of supported coloring modes for the {@link AnsiTerminalPrinter}.
+   */
+  public static enum Mode {
+    INFO,     // green
+    ERROR,    // bold red
+    WARNING,  // magenta
+    DEFAULT;  // default color
+
+    @Override
+    public String toString() {
+      return MODE_PREFIX + name() + MODE_SUFFIX;
+    }
+  }
+
+  private static final Logger LOG = Logger.getLogger(AnsiTerminalPrinter.class.getName());
+  private static final EnumSet<Mode> MODES = EnumSet.allOf(Mode.class);
+  private static final Pattern PATTERN = Pattern.compile(MODE_PATTERN);
+
+  private final OutputStream stream;
+  private final PrintWriter writer;
+  private final AnsiTerminal terminal;
+  private boolean useColor;
+  private Mode lastMode = Mode.DEFAULT;
+
+  /**
+   * Creates new instance using provided OutputStream and sets coloring logic
+   * for that instance.
+   */
+  public AnsiTerminalPrinter(OutputStream out, boolean useColor) {
+    this.useColor = useColor;
+    terminal = new AnsiTerminal(out);
+    writer = new PrintWriter(out, true);
+    stream = out;
+  }
+
+  /**
+   * Writes the specified string to the output stream while injecting coloring
+   * sequences when appropriate mode keyword is found and flushes.
+   *
+   * List of supported mode keywords is defined by the enum {@link Mode}.
+   *
+   * See class documentation for details.
+   */
+  public void print(String str) {
+    for (String part : PATTERN.split(str)) {
+      int index = part.indexOf(MODE_SUFFIX);
+      // Mode name will contain at least one character, so suffix index
+      // must be at least 1. If it isn't then there is no match.
+      if (index > 1) {
+        for (Mode mode : MODES) {
+          if (index == mode.name().length() && part.startsWith(mode.name())) {
+            setupTerminal(mode);
+            part = part.substring(index + MODE_SUFFIX.length());
+            break;
+          }
+        }
+      }
+      writer.print(part);
+      writer.flush();
+    }
+  }
+
+  public void printLn(String str) {
+    print(str + "\n");
+  }
+
+  /**
+   * Returns the underlying OutputStream.
+   */
+  public OutputStream getOutputStream() {
+    return stream;
+  }
+
+  /**
+   * Injects coloring escape sequences if output should be colored and mode
+   * has been changed.
+   */
+  private void setupTerminal(Mode mode) {
+    if (!useColor) {
+      return;
+    }
+    try {
+      if (lastMode != mode) {
+        terminal.resetTerminal();
+        lastMode = mode;
+        if (mode == Mode.DEFAULT) {
+          return; // Terminal is already reset - nothing else to do.
+        } else if (mode == Mode.INFO) {
+          terminal.textGreen();
+        } else if (mode == Mode.ERROR) {
+          terminal.textRed();
+          terminal.textBold();
+        } else if (mode == Mode.WARNING) {
+          terminal.textMagenta();
+        }
+      }
+    } catch (IOException e) {
+      // AnsiTerminal state is now considered to be inconsistent - coloring
+      // should be disabled to prevent future use of AnsiTerminal instance.
+      LOG.warning("Disabling coloring due to " + e.getMessage());
+      useColor = false;
+    }
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/util/io/DelegatingOutErr.java b/src/main/java/com/google/devtools/build/lib/util/io/DelegatingOutErr.java
new file mode 100644
index 0000000000..83ccf2ff63
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/util/io/DelegatingOutErr.java
@@ -0,0 +1,113 @@
+// Copyright 2014 Google Inc. 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.util.io;
+
+import java.io.IOException;
+import java.io.OutputStream;
+import java.util.ArrayList;
+import java.util.List;
+
+/**
+ * An {@link OutErr} specialization that supports subscribing / removing
+ * sinks, using {@link #addSink(OutErr)} and {@link #removeSink(OutErr)}.
+ * A sink is a destination to which the {@link DelegatingOutErr} will write.
+ *
+ * Also, we can hook up {@link System#out} / {@link System#err} as sources.
+ */
+public final class DelegatingOutErr extends OutErr {
+
+  /**
+   * Create a new instance to which no sinks have subscribed (basically just
+   * like a {@code /dev/null}.
+   */
+  public DelegatingOutErr() {
+    super(new DelegatingOutputStream(), new DelegatingOutputStream());
+  }
+
+
+  private final DelegatingOutputStream outSink() {
+    return (DelegatingOutputStream) getOutputStream();
+  }
+
+  private final DelegatingOutputStream errSink() {
+    return (DelegatingOutputStream) getErrorStream();
+  }
+
+  /**
+   * Add a sink, that is, after calling this method, {@code outErrSink} will
+   * receive all output / errors written to {@code this} object.
+   */
+  public void addSink(OutErr outErrSink) {
+    outSink().addSink(outErrSink.getOutputStream());
+    errSink().addSink(outErrSink.getErrorStream());
+  }
+
+  /**
+   * Remove the sink, that is, after calling this method, {@code outErrSink}
+   * will no longer receive output / errors written to {@code this} object.
+   */
+  public void removeSink(OutErr outErrSink) {
+    outSink().removeSink(outErrSink.getOutputStream());
+    errSink().removeSink(outErrSink.getErrorStream());
+  }
+
+  private static class DelegatingOutputStream extends OutputStream {
+
+    private final List<OutputStream> sinks = new ArrayList<>();
+
+    public void addSink(OutputStream sink) {
+      sinks.add(sink);
+    }
+
+    public void removeSink(OutputStream sink) {
+      sinks.remove(sink);
+    }
+
+    @Override
+    public void write(int b) throws IOException {
+      for (OutputStream sink : sinks) {
+        sink.write(b);
+      }
+    }
+
+    @Override
+    public void close() throws IOException {
+      for (OutputStream sink : sinks) {
+        sink.close();
+      }
+    }
+
+    @Override
+    public void flush() throws IOException {
+      for (OutputStream sink : sinks) {
+        sink.flush();
+      }
+    }
+
+    @Override
+    public void write(byte[] b, int off, int len) throws IOException {
+      for (OutputStream sink : sinks) {
+        sink.write(b, off, len);
+      }
+    }
+
+    @Override
+    public void write(byte[] b) throws IOException {
+      for (OutputStream sink : sinks) {
+        sink.write(b);
+      }
+    }
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/util/io/FileOutErr.java b/src/main/java/com/google/devtools/build/lib/util/io/FileOutErr.java
new file mode 100644
index 0000000000..4f9aecfbd1
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/util/io/FileOutErr.java
@@ -0,0 +1,404 @@
+// Copyright 2014 Google Inc. 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.util.io;
+
+import com.google.common.annotations.VisibleForTesting;
+import com.google.common.io.ByteStreams;
+import com.google.devtools.build.lib.concurrent.ThreadSafety;
+import com.google.devtools.build.lib.vfs.FileSystemUtils;
+import com.google.devtools.build.lib.vfs.Path;
+
+import java.io.FileInputStream;
+import java.io.IOException;
+import java.io.InputStream;
+import java.io.OutputStream;
+import java.io.PrintStream;
+
+/**
+ * An implementation of {@link OutErr} that captures all out/err output into
+ * a file for stdout and a file for stderr. The files are only created if any
+ * output is made.
+ * The OutErr assumes that the directory that will contain the output file
+ * must exist.
+ *
+ * You should not use this object from multiple different threads.
+ */
+@ThreadSafety.ThreadCompatible
+public class FileOutErr extends OutErr {
+
+  /**
+   * Create a new FileOutErr that will write its input,
+   * if any, to the files specified by stdout/stderr.
+   *
+   * No other process may write to the files,
+   *
+   * @param stdout The file for the stdout of this outErr
+   * @param stderr The file for the stderr of this outErr
+   */
+  public FileOutErr(Path stdout, Path stderr) {
+    super(new FileRecordingOutputStream(stdout), new FileRecordingOutputStream(stderr));
+  }
+
+  /**
+   * Creates a new FileOutErr that writes its input
+   * to the file specified by output. Both stdout/stderr will
+   * be copied into the single file.
+   *
+   * @param output The file for the both stdout and stderr of this outErr.
+   */
+  public FileOutErr(Path output) {
+    // We don't need to create a synchronized funnel here, like in the OutErr -- The
+    // respective functions in the FileRecordingOutputStream take care of locking.
+    this(new FileRecordingOutputStream(output));
+  }
+
+  /**
+   * Creates a new FileOutErr that discards its input. Useful
+   * for testing purposes.
+   */
+  @VisibleForTesting
+  public FileOutErr() {
+    this(new NullFileRecordingOutputStream());
+  }
+
+  private FileOutErr(OutputStream stream) {
+    // We need this function to duplicate the single new object into both arguments
+    // of the super-constructor.
+    super(stream, stream);
+  }
+
+  /**
+   * Returns true if any output was recorded.
+   */
+  public boolean hasRecordedOutput() {
+    return getFileOutputStream().hasRecordedOutput() || getFileErrorStream().hasRecordedOutput();
+  }
+
+  /**
+   * Returns true if output was recorded on stdout.
+   */
+  public boolean hasRecordedStdout() {
+    return getFileOutputStream().hasRecordedOutput();
+  }
+
+  /**
+   * Returns true if output was recorded on stderr.
+   */
+  public boolean hasRecordedStderr() {
+    return getFileErrorStream().hasRecordedOutput();
+  }
+
+  /**
+   * Returns the file this OutErr uses to buffer stdout
+   *
+   * The user must ensure that no other process is writing to the
+   * files at time of creation.
+   *
+   * @return the path object with the contents of stdout
+   */
+  public Path getOutputFile() {
+    return getFileOutputStream().getFile();
+  }
+
+  /**
+   * Returns the file this OutErr uses to buffer stderr.
+   *
+   * @return the path object with the contents of stderr
+   */
+  public Path getErrorFile() {
+    return getFileErrorStream().getFile();
+  }
+
+  /**
+   * Interprets the captured out content as an {@code ISO-8859-1} encoded
+   * string.
+   */
+  public String outAsLatin1() {
+    return getFileOutputStream().getRecordedOutput();
+  }
+
+  /**
+   * Interprets the captured err content as an {@code ISO-8859-1} encoded
+   * string.
+   */
+  public String errAsLatin1() {
+    return getFileErrorStream().getRecordedOutput();
+  }
+
+  /**
+   * Writes the captured out content to the given output stream,
+   * avoiding keeping the entire contents in memory.
+   */
+  public void dumpOutAsLatin1(OutputStream out) {
+    getFileOutputStream().dumpOut(out);
+  }
+
+  /**
+   * Writes the captured out content to the given output stream,
+   * avoiding keeping the entire contents in memory.
+   */
+  public void dumpErrAsLatin1(OutputStream out) {
+    getFileErrorStream().dumpOut(out);
+  }
+
+  private AbstractFileRecordingOutputStream getFileOutputStream() {
+    return (AbstractFileRecordingOutputStream) getOutputStream();
+  }
+
+  private AbstractFileRecordingOutputStream getFileErrorStream() {
+    return (AbstractFileRecordingOutputStream) getErrorStream();
+  }
+
+  /**
+   * An abstract supertype for the two other inner classes in this type
+   * to implement streams that can write to a file.
+   */
+  private abstract static class AbstractFileRecordingOutputStream extends OutputStream {
+
+    /**
+     * Returns true if this FileRecordingOutputStream has encountered an error.
+     *
+     * @return true there was an error, false otherwise.
+     */
+    abstract boolean hadError();
+
+    /**
+     * Returns the file this FileRecordingOutputStream is writing to.
+     */
+    abstract Path getFile();
+
+    /**
+     * Returns true if the FileOutErr has stored output.
+     */
+    abstract boolean hasRecordedOutput();
+
+    /**
+     * Returns the output this AbstractFileOutErr has recorded.
+     */
+    abstract String getRecordedOutput();
+
+    /**
+     * Writes the output to the given output stream,
+     * avoiding keeping the entire contents in memory.
+     */
+    abstract void dumpOut(OutputStream out);
+  }
+
+  /**
+   * An output stream that pretends to capture all its output into a file,
+   * but instead discards it.
+   */
+  private static class NullFileRecordingOutputStream extends AbstractFileRecordingOutputStream {
+
+    NullFileRecordingOutputStream() {
+    }
+
+    @Override
+    boolean hadError() {
+      return false;
+    }
+
+    @Override
+    Path getFile() {
+      return null;
+    }
+
+    @Override
+    boolean hasRecordedOutput() {
+      return false;
+    }
+
+    @Override
+    String getRecordedOutput() {
+      return "";
+    }
+
+    @Override
+    void dumpOut(OutputStream out) {
+      return;
+    }
+
+
+    @Override
+    public void write(byte[] b, int off, int len) {
+    }
+
+    @Override
+    public void write(int b) {
+    }
+
+    @Override
+    public void write(byte[] b) {
+    }
+  }
+
+
+  /**
+   * An output stream that captures all output into a file.
+   * The file is created only if output is received.
+   *
+   * The user must take care that nobody else is writing to the
+   * file that is backing the output stream.
+   *
+   * The write() methods of type are synchronized to ensure
+   * that writes from different threads are not mixed up.
+   *
+   * The outputStream is here only for the benefit of the pumping
+   * IO we're currently using for execution - Once that is gone,
+   * we can remove this output stream and fold its code into the
+   * FileOutErr.
+   */
+  @ThreadSafety.ThreadCompatible
+  private static class FileRecordingOutputStream extends AbstractFileRecordingOutputStream {
+
+    private final Path outputFile;
+    OutputStream outputStream;
+    String error;
+
+    FileRecordingOutputStream(Path outputFile) {
+      this.outputFile = outputFile;
+    }
+
+    @Override
+    boolean hadError() {
+      return error != null;
+    }
+
+    @Override
+    Path getFile() {
+      return outputFile;
+    }
+
+    private OutputStream getOutputStream() throws IOException {
+      // you should hold the lock before you invoke this method
+      if (outputStream == null) {
+        outputStream = outputFile.getOutputStream();
+      }
+      return outputStream;
+    }
+
+    private boolean hasOutputStream() {
+      return outputStream != null;
+    }
+
+    /**
+     * Called whenever the FileRecordingOutputStream finds an error.
+     */
+    private void recordError(IOException exception) {
+      String newErrorText = exception.getMessage();
+      error = (error == null) ? newErrorText : error + "\n" + newErrorText;
+    }
+
+    @Override
+    boolean hasRecordedOutput() {
+      if (hadError()) {
+        return true;
+      }
+      if (!outputFile.exists()) {
+        return false;
+      }
+      try {
+        return outputFile.getFileSize() > 0;
+      } catch (IOException ex) {
+        recordError(ex);
+        return true;
+      }
+    }
+
+    @Override
+    String getRecordedOutput() {
+      StringBuilder result = new StringBuilder();
+      try {
+        if (getFile().exists()) {
+          result.append(FileSystemUtils.readContentAsLatin1(getFile()));
+        }
+      } catch (IOException ex) {
+        recordError(ex);
+      }
+
+      if (hadError()) {
+        result.append(error);
+      }
+      return result.toString();
+    }
+
+    @Override
+    void dumpOut(OutputStream out) {
+      InputStream in = null;
+      try {
+        if (getFile().exists()) {
+          in = new FileInputStream(getFile().getPathString());
+          ByteStreams.copy(in, out);
+        }
+      } catch (IOException ex) {
+        recordError(ex);
+      } finally {
+        if (in != null) {
+          try {
+            in.close();
+          } catch (IOException e) {
+            // Ignore.
+          }
+        }
+      }
+
+      if (hadError()) {
+        PrintStream ps = new PrintStream(out);
+        ps.print(error);
+        ps.flush();
+      }
+    }
+
+    @Override
+    public synchronized void write(byte[] b, int off, int len) {
+      if (len > 0) {
+        try {
+          getOutputStream().write(b, off, len);
+        } catch (IOException ex) {
+          recordError(ex);
+        }
+      }
+    }
+
+    @Override
+    public synchronized void write(int b) {
+      try {
+        getOutputStream().write(b);
+      } catch (IOException ex) {
+        recordError(ex);
+      }
+    }
+
+    @Override
+    public synchronized void write(byte[] b) throws IOException {
+      if (b.length > 0) {
+        getOutputStream().write(b);
+      }
+    }
+
+    @Override
+    public synchronized void flush() throws IOException {
+      if (hasOutputStream()) {
+        getOutputStream().flush();
+      }
+    }
+
+    @Override
+    public synchronized void close() throws IOException {
+      if (hasOutputStream()) {
+        getOutputStream().close();
+      }
+    }
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/util/io/FileWatcher.java b/src/main/java/com/google/devtools/build/lib/util/io/FileWatcher.java
new file mode 100644
index 0000000000..9355cc35ea
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/util/io/FileWatcher.java
@@ -0,0 +1,111 @@
+// Copyright 2014 Google Inc. 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.util.io;
+
+import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
+import com.google.devtools.build.lib.vfs.Path;
+
+import java.io.IOException;
+import java.io.InputStream;
+import java.io.OutputStream;
+
+/**
+ * The FileWatcher dumps the contents of a files into an OutErr.
+ * It then stays active and dumps any content to the OutErr that is
+ * added to the file, until it is told to stop and all output has
+ * been dumped.
+ *
+ * This is useful to emulate streaming test output.
+ */
+@ThreadSafe
+public class FileWatcher extends Thread {
+
+  // How often we check for updates in the file we watch. (in ms)
+  private static final int WATCH_INTERVAL = 100;
+
+  private final Path outputFile;
+  private final OutErr output;
+  private volatile boolean finishPumping;
+  private long toSkip = 0;
+
+  /**
+   * Creates a FileWatcher that will dump any output that is appended to
+   * outputFile onto output. If skipExisting is true, the watcher will not dump
+   * any output that is in outputFile when we construct the watcher. If
+   * skipExisting is false, already existing output will be dumped, too.
+   *
+   * @param outputFile the File to watch
+   * @param output the outErr to dump the files contents to
+   * @param skipExisting whether to dump already existing output or not.
+   */
+  public FileWatcher(Path outputFile, OutErr output, boolean skipExisting) throws IOException {
+    super("Streaming Test Output Pump");
+    this.outputFile = outputFile;
+    this.output = output;
+    finishPumping = false;
+
+    if (outputFile.exists() && skipExisting) {
+      toSkip = outputFile.getFileSize();
+    }
+  }
+
+  /**
+   * Tells the FileWatcher to stop pumping output and finish.
+   * The FileWatcher will only finish until there is no data left to display.
+   * This means that it is rarely a good idea to unconditionally wait for the
+   * FileWatcher thread to terminate -- Instead, it is better to have a timeout.
+   */
+  @ThreadSafe
+  public void stopPumping() {
+    finishPumping = true;
+  }
+
+  @Override
+  public void run() {
+
+    try {
+
+      // Wait until the file exists, or we have to abort.
+      while (!outputFile.exists() && !finishPumping) {
+        Thread.sleep(WATCH_INTERVAL);
+      }
+
+      // Check that we did not have abort before the file was created.
+      if (outputFile.exists()) {
+        try (InputStream inputStream = outputFile.getInputStream();
+             OutputStream outputStream = output.getOutputStream();) {
+          byte[] buffer = new byte[1024];
+          while (!finishPumping || (inputStream.available() != 0)) {
+            if (inputStream.available() != 0) {
+              if (toSkip > 0) {
+                toSkip -= inputStream.skip(toSkip);
+              } else {
+                int read = inputStream.read(buffer);
+                if (read > 0) {
+                  outputStream.write(buffer, 0, read);
+                }
+              }
+            } else {
+              Thread.sleep(WATCH_INTERVAL);
+            }
+          }
+        }
+      }
+    } catch (IOException ex) {
+      output.printOutLn("Failure reading or writing: " + ex.getMessage());
+    } catch (InterruptedException ex) {
+      // Don't do anything.
+    }
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/util/io/LineFlushingOutputStream.java b/src/main/java/com/google/devtools/build/lib/util/io/LineFlushingOutputStream.java
new file mode 100644
index 0000000000..a5a10cf16c
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/util/io/LineFlushingOutputStream.java
@@ -0,0 +1,92 @@
+// Copyright 2014 Google Inc. 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.util.io;
+
+import java.io.IOException;
+import java.io.OutputStream;
+
+/**
+ * This stream maintains a buffer, which it flushes upon encountering bytes
+ * that might be new line characters. This stream implements {@link #close()}
+ * as {@link #flush()}.
+ */
+abstract class LineFlushingOutputStream extends OutputStream {
+
+  static final int BUFFER_LENGTH = 8192;
+  protected static byte NEWLINE = '\n';
+
+  /**
+   * The buffer containing the characters that have not been flushed yet.
+   */
+  protected final byte[] buffer = new byte[BUFFER_LENGTH];
+
+  /**
+   * The length of the buffer that's actually used.
+   */
+  protected int len = 0;
+
+  @Override
+  public synchronized void write(byte[] b, int off, int inlen)
+      throws IOException {
+    if (len == BUFFER_LENGTH) {
+      flush();
+    }
+    int charsInLine = 0;
+    while(inlen > charsInLine) {
+      boolean sawNewline = (b[off + charsInLine] == NEWLINE);
+      charsInLine++;
+      if (sawNewline || len + charsInLine == BUFFER_LENGTH) {
+        System.arraycopy(b, off, buffer, len, charsInLine);
+        len += charsInLine;
+        off += charsInLine;
+        inlen -= charsInLine;
+        flush();
+        charsInLine = 0;
+      }
+    }
+    System.arraycopy(b, off, buffer, len, charsInLine);
+    len += charsInLine;
+  }
+
+  @Override
+  public void write(int byteAsInt) throws IOException {
+    byte b = (byte) byteAsInt; // make sure we work with bytes in comparisons
+    write(new byte[] {b}, 0, 1);
+  }
+
+  /**
+   * Close is implemented as {@link #flush()}. Client code must close the
+   * underlying output stream itself in case that's desired.
+   */
+  @Override
+  public synchronized void close() throws IOException {
+    flush();
+  }
+
+  @Override
+  public final synchronized void flush() throws IOException {
+    flushingHook(); // The point of using a hook is to make it synchronized.
+  }
+
+  /**
+   * The implementing class must define this method, which must at least flush
+   * the bytes in {@code buffer[0] - buffer[len - 1]}, and reset {@code len=0}.
+   *
+   * Don't forget to synchronized the implementation of this method on whatever
+   * underlying object it writes to!
+   */
+  protected abstract void flushingHook() throws IOException;
+
+}
diff --git a/src/main/java/com/google/devtools/build/lib/util/io/LinePrefixingOutputStream.java b/src/main/java/com/google/devtools/build/lib/util/io/LinePrefixingOutputStream.java
new file mode 100644
index 0000000000..23d6cd7bcd
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/util/io/LinePrefixingOutputStream.java
@@ -0,0 +1,73 @@
+// Copyright 2014 Google Inc. 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.util.io;
+
+import static java.nio.charset.StandardCharsets.UTF_8;
+
+import java.io.IOException;
+import java.io.OutputStream;
+
+/**
+ * A stream that writes to another one, emittig a prefix before every line
+ * it emits. This stream will also add a newline for every flush; so it's not
+ * useful for anything other than simple text data (e.g. log files). Here's
+ * an example which demonstrates how an explicit flush or a flush caused by
+ * a full buffer causes a newline to be added to the output.
+ *
+ * <code>
+ * foo bar
+ * baz ba[flush]ng
+ * boo
+ * </code>
+ *
+ * This results in this output being emitted:
+ *
+ * <code>
+ * my prefix: foo bar
+ * my prefix: ba
+ * my prefix: ng
+ * my prefix: boo
+ * </code>
+ */
+public final class LinePrefixingOutputStream extends LineFlushingOutputStream {
+
+  private byte[] linePrefix;
+  private final OutputStream sink;
+
+  public LinePrefixingOutputStream(String linePrefix, OutputStream sink) {
+    this.linePrefix = linePrefix.getBytes(UTF_8);
+    this.sink = sink;
+  }
+
+  @Override
+  protected void flushingHook() throws IOException {
+    synchronized (sink) {
+      if (len == 0) {
+        sink.flush();
+        return;
+      }
+      byte lastByte = buffer[len - 1];
+      boolean lineIsIncomplete = lastByte != NEWLINE;
+      sink.write(linePrefix);
+      sink.write(buffer, 0, len);
+      if (lineIsIncomplete) {
+        sink.write(NEWLINE);
+      }
+      sink.flush();
+      len = 0;
+    }
+  }
+
+}
diff --git a/src/main/java/com/google/devtools/build/lib/util/io/OutErr.java b/src/main/java/com/google/devtools/build/lib/util/io/OutErr.java
new file mode 100644
index 0000000000..c4700eae77
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/util/io/OutErr.java
@@ -0,0 +1,132 @@
+// Copyright 2014 Google Inc. 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.util.io;
+
+import java.io.IOException;
+import java.io.OutputStream;
+import java.io.PrintStream;
+import java.io.PrintWriter;
+
+/**
+ * A pair of output streams to be used for redirecting the output and error
+ * streams of a subprocess.
+ */
+public class OutErr {
+
+  private final OutputStream out;
+  private final OutputStream err;
+
+  public static final OutErr SYSTEM_OUT_ERR = create(System.out, System.err);
+
+  /**
+   * Creates a new OutErr instance from the specified output and error streams.
+   */
+  public static OutErr create(OutputStream out, OutputStream err) {
+    return new OutErr(out, err);
+  }
+
+  protected OutErr(OutputStream out, OutputStream err) {
+    this.out = out;
+    this.err = err;
+  }
+
+  /**
+   * This method redirects {@link System#out} / {@link System#err} into
+   * {@code this} object. After calling this method, writing to
+   * {@link System#out} or {@link System#err} will result in
+   * {@code "System.out: " + message} or {@code "System.err: " + message}
+   * being written to the OutputStreams of {@code this} instance.
+   *
+   * Note: This method affects global variables.
+   */
+  public void addSystemOutErrAsSource() {
+    System.setOut(new PrintStream(new LinePrefixingOutputStream("System.out: ", getOutputStream()),
+                                  /*autoflush=*/false));
+    System.setErr(new PrintStream(new LinePrefixingOutputStream("System.err: ", getErrorStream()),
+                                  /*autoflush=*/false));
+  }
+
+  /**
+   * Creates a new OutErr instance from the specified stream.
+   * Writes to either the output or err of the new OutErr are written
+   * to outputStream, synchronized.
+   */
+  public static OutErr createSynchronizedFunnel(final OutputStream outputStream) {
+    OutputStream syncOut = new OutputStream() {
+
+      @Override
+      public synchronized void write(int b) throws IOException {
+        outputStream.write(b);
+      }
+
+      @Override
+      public synchronized void write(byte b[]) throws IOException {
+        outputStream.write(b);
+      }
+
+      @Override
+      public synchronized  void write(byte b[], int off, int len) throws IOException {
+        outputStream.write(b, off, len);
+      }
+
+      @Override
+      public synchronized void flush() throws IOException {
+        outputStream.flush();
+      }
+
+      @Override
+      public synchronized void close() throws IOException {
+        outputStream.close();
+      }
+    };
+
+    return create(syncOut, syncOut);
+  }
+
+  public OutputStream getOutputStream() {
+    return out;
+  }
+
+  public OutputStream getErrorStream() {
+    return err;
+  }
+
+  /**
+   * Writes the specified string to the output stream, and flushes.
+   */
+  public void printOut(String s) {
+    PrintWriter writer = new PrintWriter(out, true);
+    writer.print(s);
+    writer.flush();
+  }
+
+  public void printOutLn(String s) {
+    printOut(s + "\n");
+  }
+
+  /**
+   * Writes the specified string to the error stream, and flushes.
+   */
+  public void printErr(String s) {
+    PrintWriter writer = new PrintWriter(err, true);
+    writer.print(s);
+    writer.flush();
+  }
+
+  public void printErrLn(String s) {
+    printErr(s + "\n");
+  }
+
+}
diff --git a/src/main/java/com/google/devtools/build/lib/util/io/RecordingOutErr.java b/src/main/java/com/google/devtools/build/lib/util/io/RecordingOutErr.java
new file mode 100644
index 0000000000..d276afc1a6
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/util/io/RecordingOutErr.java
@@ -0,0 +1,91 @@
+// Copyright 2014 Google Inc. 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.util.io;
+
+import java.io.ByteArrayOutputStream;
+import java.io.UnsupportedEncodingException;
+
+/**
+ * An implementation of {@link OutErr} that captures all out / err output and
+ * makes it available as ISO-8859-1 strings. Useful for implementing test
+ * cases that assert particular output.
+ */
+public class RecordingOutErr extends OutErr {
+
+  public RecordingOutErr() {
+    super(new ByteArrayOutputStream(), new ByteArrayOutputStream());
+  }
+
+  public RecordingOutErr(ByteArrayOutputStream out, ByteArrayOutputStream err) {
+    super(out, err);
+  }
+
+  /**
+   * Reset the captured content; that is, reset the out / err buffers.
+   */
+  public void reset() {
+    getOutputStream().reset();
+    getErrorStream().reset();
+  }
+
+  /**
+   * Interprets the captured out content as an {@code ISO-8859-1} encoded
+   * string.
+   */
+  public String outAsLatin1() {
+    try {
+      return getOutputStream().toString("ISO-8859-1");
+    } catch (UnsupportedEncodingException e) {
+      throw new AssertionError(e);
+    }
+  }
+
+  /**
+   * Interprets the captured err content as an {@code ISO-8859-1} encoded
+   * string.
+   */
+  public String errAsLatin1() {
+    try {
+      return getErrorStream().toString("ISO-8859-1");
+    } catch (UnsupportedEncodingException e) {
+      throw new AssertionError(e);
+    }
+  }
+
+  /**
+   * Returns true if any output was recorded.
+   */
+  public boolean hasRecordedOutput() {
+    return getOutputStream().size() > 0 || getErrorStream().size() > 0;
+  }
+
+  @Override
+  public String toString() {
+    String out = outAsLatin1();
+    String err = errAsLatin1();
+    return "" + ((out.length() > 0) ? ("stdout: " + out + "\n") : "")
+              + ((err.length() > 0) ? ("stderr: " + err) : "");
+  }
+
+  @Override
+  public ByteArrayOutputStream getOutputStream() {
+    return (ByteArrayOutputStream) super.getOutputStream();
+  }
+
+  @Override
+  public ByteArrayOutputStream getErrorStream() {
+    return (ByteArrayOutputStream) super.getErrorStream();
+  }
+
+}
diff --git a/src/main/java/com/google/devtools/build/lib/util/io/StreamDemultiplexer.java b/src/main/java/com/google/devtools/build/lib/util/io/StreamDemultiplexer.java
new file mode 100644
index 0000000000..ffe0c19340
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/util/io/StreamDemultiplexer.java
@@ -0,0 +1,186 @@
+// Copyright 2014 Google Inc. 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.util.io;
+
+import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadCompatible;
+
+import java.io.IOException;
+import java.io.OutputStream;
+
+/**
+ * The dual of {@link StreamMultiplexer}: This is an output stream into which
+ * you can dump the multiplexed stream, and it delegates the de-multiplexed
+ * content back into separate channels (instances of {@link OutputStream}).
+ *
+ * The format of the tagged output stream is as follows:
+ *
+ * <pre>
+ * combined :: = [ control_line payload ... ]+
+ * control_line :: = '@' marker '@'? '\n'
+ * payload :: = r'^[^\n]*\n'
+ * </pre>
+ *
+ * For more details, please see {@link StreamMultiplexer}.
+ */
+@ThreadCompatible
+public final class StreamDemultiplexer extends OutputStream {
+
+  @Override
+  public void close() throws IOException {
+    flush();
+  }
+
+  @Override
+  public void flush() throws IOException {
+    if (selectedStream != null) {
+      selectedStream.flush();
+    }
+  }
+
+  private static final byte AT = '@';
+  private static final byte NEWLINE = '\n';
+
+  /**
+   * The output streams, conveniently in an array indexed by the marker byte.
+   * Some of these will be null, most likely.
+   */
+  private final OutputStream[] outputStreams =
+    new OutputStream[Byte.MAX_VALUE + 1];
+
+  /**
+   * Each state in this FSM corresponds to a position in the grammar, which is
+   * simple enough that we can just move through it from beginning to end as we
+   * parse things.
+   */
+  private enum State {
+    EXPECT_CONTROL_STARTING_AT,
+    EXPECT_MARKER_BYTE,
+    EXPECT_AT_OR_NEWLINE,
+    EXPECT_PAYLOAD_OR_NEWLINE
+  }
+
+  private State state = State.EXPECT_CONTROL_STARTING_AT;
+  private boolean addNewlineToPayload;
+  private OutputStream selectedStream;
+
+  /**
+   * Construct a new demultiplexer. The {@code smallestMarkerByte} indicates
+   * the marker byte we would expect for {@code outputStreams[0]} to be used.
+   * So, if this first stream is your stdout and you're using the
+   * {@link StreamMultiplexer}, then you will need to set this to
+   * {@code '1'}. Because {@link StreamDemultiplexer} extends
+   * {@link OutputStream}, this constructor effectively creates an
+   * {@link OutputStream} instance which demultiplexes the tagged data client
+   * code writes to it into {@code outputStreams}.
+   */
+  public StreamDemultiplexer(byte smallestMarkerByte,
+                             OutputStream... outputStreams) {
+    for (int i = 0; i < outputStreams.length; i++) {
+      this.outputStreams[smallestMarkerByte + i] = outputStreams[i];
+    }
+  }
+
+  @Override
+  public void write(int b) throws IOException {
+    // This dispatch traverses the finite state machine / grammar.
+    switch (state) {
+      case EXPECT_CONTROL_STARTING_AT:
+        parseControlStartingAt((byte) b);
+        resetFields();
+        break;
+      case EXPECT_MARKER_BYTE:
+        parseMarkerByte((byte) b);
+        break;
+      case EXPECT_AT_OR_NEWLINE:
+        parseAtOrNewline((byte) b);
+        break;
+      case EXPECT_PAYLOAD_OR_NEWLINE:
+        parsePayloadOrNewline((byte) b);
+        break;
+    }
+  }
+
+  /**
+   * Handles {@link State#EXPECT_PAYLOAD_OR_NEWLINE}, which is the payload
+   * we are actually transporting over the wire. At this point we can rely
+   * on a stream having been preselected into {@link #selectedStream}, and
+   * also we will add a newline if {@link #addNewlineToPayload} is set.
+   * Flushes at the end of every payload segment.
+   */
+  private void parsePayloadOrNewline(byte b) throws IOException {
+    if (b == NEWLINE) {
+      if (addNewlineToPayload) {
+        selectedStream.write(NEWLINE);
+      }
+      selectedStream.flush();
+      state = State.EXPECT_CONTROL_STARTING_AT;
+    } else {
+      selectedStream.write(b);
+      selectedStream.flush(); // slow?
+    }
+  }
+
+  /**
+   * Handles {@link State#EXPECT_AT_OR_NEWLINE}, which is either the
+   * suppress newline indicator (at) at the end of a control line, or the end
+   * of a control line.
+   */
+  private void parseAtOrNewline(byte b) throws IOException {
+    if (b == NEWLINE) {
+      state = State.EXPECT_PAYLOAD_OR_NEWLINE;
+    } else if (b == AT) {
+      addNewlineToPayload = false;
+    } else {
+      throw new IOException("Expected @ or \\n. (" + b + ")");
+    }
+  }
+
+  /**
+   * Reset the fields that are affected by our state.
+   */
+  private void resetFields() {
+    selectedStream = null;
+    addNewlineToPayload = true;
+  }
+
+  /**
+   * Handles {@link State#EXPECT_MARKER_BYTE}. The byte determines which stream
+   * we will be using, and will set {@link #selectedStream}.
+   */
+  private void parseMarkerByte(byte markerByte) throws IOException {
+    if (markerByte < 0 || markerByte > Byte.MAX_VALUE) {
+      String msg = "Illegal marker byte (" + markerByte + ")";
+      throw new IllegalArgumentException(msg);
+    }
+    if (markerByte > outputStreams.length
+        || outputStreams[markerByte] == null) {
+      throw new IOException("stream " + markerByte + " not registered.");
+    }
+    selectedStream = outputStreams[markerByte];
+    state = State.EXPECT_AT_OR_NEWLINE;
+  }
+
+  /**
+   * Handles {@link State#EXPECT_CONTROL_STARTING_AT}, the very first '@' with
+   * which each message starts.
+   */
+  private void parseControlStartingAt(byte b) throws IOException {
+    if (b != AT) {
+      throw new IOException("Expected control starting @. (" + b + ", "
+          + (char) b + ")");
+    }
+    state = State.EXPECT_MARKER_BYTE;
+  }
+
+}
diff --git a/src/main/java/com/google/devtools/build/lib/util/io/StreamMultiplexer.java b/src/main/java/com/google/devtools/build/lib/util/io/StreamMultiplexer.java
new file mode 100644
index 0000000000..c214aa5515
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/util/io/StreamMultiplexer.java
@@ -0,0 +1,132 @@
+// Copyright 2014 Google Inc. 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.util.io;
+
+import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
+
+import java.io.IOException;
+import java.io.OutputStream;
+
+/**
+ * Instances of this class are multiplexers, which redirect multiple
+ * output streams into a single output stream with tagging so it can be
+ * de-multiplexed into multiple streams as needed. This allows us to
+ * use one connection for multiple streams, but more importantly it avoids
+ * multiple threads or select etc. on the receiving side: A client on the other
+ * end of a networking connection can simply read the tagged lines and then act
+ * on them within a sigle thread.
+ *
+ * The format of the tagged output stream is as follows:
+ *
+ * <pre>
+ * combined :: = [ control_line payload ... ]+
+ * control_line :: = '@' marker '@'? '\n'
+ * payload :: = r'^[^\n]*\n'
+ * </pre>
+ *
+ * So basically:
+ * <ul>
+ *   <li>Control lines alternate with payload lines</li>
+ *   <li>Both types of lines end with a newline, and never have a newline in
+ *       them.</li>
+ *   <li>The marker indicates which stream we mean.
+ *       For now, '1'=stdout, '2'=stderr.</li>
+ *   <li>The optional second '@' indicates that the following line is
+ *       incomplete.</li>
+ * </ul>
+ *
+ * This format is optimized for easy interpretation by a Python client, but it's
+ * also a compromise in that it's still easy to interpret by a human (let's say
+ * you have to read the traffic over a wire for some reason).
+ */
+@ThreadSafe
+public final class StreamMultiplexer {
+
+  public static final byte STDOUT_MARKER = '1';
+  public static final byte STDERR_MARKER = '2';
+  public static final byte CONTROL_MARKER = '3';
+
+  private static final byte AT = '@';
+
+  private final Object mutex = new Object();
+  private final OutputStream multiplexed;
+
+  public StreamMultiplexer(OutputStream multiplexed) {
+    this.multiplexed = multiplexed;
+  }
+
+  private class MarkingStream extends LineFlushingOutputStream {
+
+    private final byte markerByte;
+
+    MarkingStream(byte markerByte) {
+      this.markerByte = markerByte;
+    }
+
+    @Override
+    protected void flushingHook() throws IOException {
+      synchronized (mutex) {
+        if (len == 0) {
+          multiplexed.flush();
+          return;
+        }
+        byte lastByte = buffer[len - 1];
+        boolean lineIsIncomplete = lastByte != NEWLINE;
+
+        multiplexed.write(AT);
+        multiplexed.write(markerByte);
+        if (lineIsIncomplete) {
+          multiplexed.write(AT);
+        }
+        multiplexed.write(NEWLINE);
+        multiplexed.write(buffer, 0, len);
+        if (lineIsIncomplete) {
+          multiplexed.write(NEWLINE);
+        }
+        multiplexed.flush();
+      }
+      len = 0;
+    }
+
+  }
+
+  /**
+   * Create a stream that will tag its contributions into the multiplexed stream
+   * with the marker '1', which means 'stdout'. Each newline byte leads
+   * to a forced automatic flush. Also, this stream never closes the underlying
+   * stream it delegates to - calling its {@code close()} method is equivalent
+   * to calling {@code flush}.
+   */
+  public OutputStream createStdout() {
+    return new MarkingStream(STDOUT_MARKER);
+  }
+
+  /**
+   * Like {@link #createStdout()}, except it tags with the marker '2' to
+   * indicate 'stderr'.
+   */
+  public OutputStream createStderr() {
+    return new MarkingStream(STDERR_MARKER);
+  }
+
+  /**
+   * Like {@link #createStdout()}, except it tags with the marker '3' to
+   * indicate control flow..
+   */
+  public OutputStream createControl() {
+    return new MarkingStream(CONTROL_MARKER);
+  }
+
+}
diff --git a/src/main/java/com/google/devtools/build/lib/util/io/TimestampGranularityMonitor.java b/src/main/java/com/google/devtools/build/lib/util/io/TimestampGranularityMonitor.java
new file mode 100644
index 0000000000..64575ae057
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/util/io/TimestampGranularityMonitor.java
@@ -0,0 +1,194 @@
+// Copyright 2014 Google Inc. 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.util.io;
+
+import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadCompatible;
+import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
+import com.google.devtools.build.lib.profiler.Profiler;
+import com.google.devtools.build.lib.profiler.ProfilerTask;
+import com.google.devtools.build.lib.util.Clock;
+
+/**
+ * A utility class for dealing with filesystem timestamp granularity issues.
+ *
+ * <p>
+ * Consider a sequence of commands such as
+ * <pre>
+ *     echo ... &gt; foo/bar
+ *     blaze query ...
+ *     echo ... &gt; foo/bar
+ *     blaze query ...
+ * </pre>
+ *
+ * If these commands all run very fast, it is possible that the timestamp
+ * on foo/bar is not changed by the second command, even though some time has
+ * passed, because the times are the same when rounded to the file system
+ * timestamp granularity (often 1 second).
+ * For performance, we assume that files
+ * timestamps haven't changed  can safely be cached without reexamining their contents.
+ * But this assumption would be violated in the above scenario.
+ *
+ * <p>
+ * To address this, we record the current time at the start of executing
+ * a Blaze command, and whenever we check the timestamp of a source file
+ * or BUILD file, we check if the timestamp of that source file matches
+ * the current time.  If so, we set a flag.  At the end of the command,
+ * if the flag was set, then we wait until the clock has advanced, so
+ * that any file modifications performed after the command exits will
+ * result in a different file timestamp.
+ *
+ * <p>
+ * This class implicitly assumes that each filesystem's clock
+ * is the same as either System.currentTimeMillis() or
+ * System.currentTimeMillis() rounded down to the nearest second.
+ * That is not strictly correct; there might be clock skew between
+ * the cpu clock and the file system clocks (e.g. for NFS file systems),
+ * and some file systems might have different granularity (e.g. the old
+ * DOS FAT filesystem has TWO-second granularity timestamps).
+ * Clock skew can be addressed using NTP.
+ * Other granularities could be addressed by small changes to this class,
+ * if it turns out to be needed.
+ *
+ * <p>
+ * Another alternative design that we considered was to write to a file and
+ * read its timestamp.  But doing that is a little tricky because we don't have
+ * a FileSystem or Path handy.  Also, if we were going to do this, the stamp
+ * file that is used should be in the same file system as the input files.
+ * But the input file system(s) might not be writeable, and even if it is,
+ * it's hard for Blaze to find a writable file on the same filesystem as the
+ * input files.
+ */
+@ThreadCompatible
+public class TimestampGranularityMonitor {
+
+  /**
+   * The time of the start of the current Blaze command,
+   * in milliseconds.
+   */
+  private long commandStartTimeMillis;
+
+  /**
+   * The time of the start of the current Blaze command,
+   * in milliseconds, rounded to one second granularity.
+   */
+  private long commandStartTimeMillisRounded;
+
+  /**
+   * True iff we detected a source file or BUILD file whose (unrounded)
+   * timestamp matched the time at the start of the current Blaze command
+   * rounded to the nearest second.
+   */
+  private volatile boolean waitASecond;
+
+  /**
+   * True iff we detected a source file or BUILD file whose timestamp
+   * exactly matched the time at the start of the current Blaze command
+   * (measuring both in integral numbers of milliseconds).
+   */
+  private volatile boolean waitAMillisecond;
+
+  private final Clock clock;
+
+  public TimestampGranularityMonitor(Clock clock) {
+    this.clock = clock;
+  }
+
+  /**
+   * Record the time at which the Blaze command started.
+   * This is needed for use by waitForTimestampGranularity().
+   */
+  public void setCommandStartTime() {
+    this.commandStartTimeMillis = clock.currentTimeMillis();
+    this.commandStartTimeMillisRounded = roundDown(this.commandStartTimeMillis);
+    this.waitASecond = false;
+    this.waitAMillisecond = false;
+  }
+
+  /**
+   * Record that the output of this Blaze command depended on the contents
+   * of a build file or source file with the specified time stamp.
+   */
+  @ThreadSafe
+  public void notifyDependenceOnFileTime(long mtime) {
+    if (mtime == this.commandStartTimeMillis) {
+      this.waitAMillisecond = true;
+    }
+    if (mtime == this.commandStartTimeMillisRounded) {
+      this.waitASecond = true;
+    }
+  }
+
+  /**
+   * If needed, wait until the next "tick" of the filesystem timestamp clock.
+   * This is done to ensure that files created after the current Blaze command
+   * finishes will have timestamps different than files created before the
+   * current Blaze command started.  Otherwise a sequence of commands
+   * such as
+   * <pre>
+   *     echo ... &gt; foo/BUILD
+   *     blaze query ...
+   *     echo ... &gt; foo/BUILD
+   *     blaze query ...
+   * </pre>
+   * could return wrong results, due to the contents of package foo
+   * being cached even though foo/BUILD changed.
+   */
+  public void waitForTimestampGranularity(OutErr outErr) {
+    if (this.waitASecond || this.waitAMillisecond) {
+      long startedWaiting = Profiler.nanoTimeMaybe();
+      boolean interrupted = false;
+
+      if (waitASecond) {
+        // 50ms slack after the whole-second boundary
+        while (clock.currentTimeMillis() < commandStartTimeMillisRounded + 1050) {
+          try {
+            Thread.sleep(50 /* milliseconds */);
+          } catch (InterruptedException e) {
+            if (!interrupted) {
+              outErr.printErrLn("INFO: Hang on a second...");
+              interrupted = true;
+            }
+          }
+        }
+      } else {
+        while (clock.currentTimeMillis() == commandStartTimeMillis) {
+          try {
+            Thread.sleep(1 /* milliseconds */);
+          } catch (InterruptedException e) {
+            if (!interrupted) {
+              outErr.printErrLn("INFO: Hang on a millisecond...");
+              interrupted = true;
+            }
+          }
+        }
+      }
+      if (interrupted) {
+        Thread.currentThread().interrupt();
+      }
+
+      Profiler.instance().logSimpleTask(startedWaiting, ProfilerTask.WAIT,
+                                        "Timestamp granularity");
+    }
+  }
+
+  /**
+   * Rounds the specified time, in milliseconds, down to the nearest second,
+   * and returns the result in milliseconds.
+   */
+  private static long roundDown(long millis) {
+    return millis / 1000 * 1000;
+  }
+
+}