Update from Google.
--
MOE_MIGRATED_REVID=85702957
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 0000000..ff62a7e
--- /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 0000000..4b61fe6
--- /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 0000000..6c6b878
--- /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 0000000..c7709e2
--- /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 0000000..72806dd
--- /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 0000000..618e88b
--- /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 0000000..878cb11
--- /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 0000000..372802d
--- /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 0000000..8d37275
--- /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 0000000..9178f985
--- /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<String>.
+ */
+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 0000000..e6c0011
--- /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 0000000..698758d
--- /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 0000000..788037d
--- /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 0000000..8307538
--- /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 0000000..c91b17b
--- /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 0000000..694e877
--- /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 0000000..e4c0876
--- /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 0000000..2bf956d
--- /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 0000000..24f55e4
--- /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 0000000..bdd1116
--- /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 0000000..0e037b2
--- /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 0000000..5170727
--- /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 0000000..498da77
--- /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 0000000..b19bd7e
--- /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 0000000..11bf94f
--- /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 0000000..fa12f59
--- /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 0000000..a377c3c
--- /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 0000000..34f6cd2
--- /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 0000000..7fd4b6d
--- /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 > 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 0000000..44c1112
--- /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 0000000..ec68736
--- /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 0000000..d7c6834
--- /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 0000000..ce26c6c
--- /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 0000000..55807f2
--- /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 0000000..fd23443
--- /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 0000000..7bdbe7e
--- /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 0000000..cf345d2
--- /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 0000000..4744c7e
--- /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 0000000..40f7ec1
--- /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"] -> "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"] -> "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"] -> "'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 0000000..9ac1d35
--- /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 0000000..7b8ebed
--- /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 0000000..689744a
--- /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 0000000..93e2a66
--- /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 0000000..fd5daab
--- /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 0000000..93bc12a
--- /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 0000000..726c5dd
--- /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 0000000..83ccf2f
--- /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 0000000..4f9aecf
--- /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 0000000..9355cc3
--- /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 0000000..a5a10cf
--- /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 0000000..23d6cd7
--- /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 0000000..c4700ea
--- /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 0000000..d276afc
--- /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 0000000..ffe0c19
--- /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 0000000..c214aa5
--- /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 0000000..64575ae
--- /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 ... > foo/bar
+ * blaze query ...
+ * echo ... > 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 ... > foo/BUILD
+ * blaze query ...
+ * echo ... > 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;
+ }
+
+}
