Update from Google.

--
MOE_MIGRATED_REVID=85702957

24 files changed, 2743 insertions, 0 deletions

diff --git a/src/main/java/com/google/devtools/build/lib/pkgcache/CompileOneDependencyTransformer.java b/src/main/java/com/google/devtools/build/lib/pkgcache/CompileOneDependencyTransformer.java
new file mode 100644
index 0000000000..ae14f181c3
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/pkgcache/CompileOneDependencyTransformer.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.pkgcache;
+
+import com.google.common.collect.Lists;
+import com.google.devtools.build.lib.cmdline.ResolvedTargets;
+import com.google.devtools.build.lib.cmdline.TargetParsingException;
+import com.google.devtools.build.lib.events.EventHandler;
+import com.google.devtools.build.lib.packages.FileTarget;
+import com.google.devtools.build.lib.packages.NoSuchPackageException;
+import com.google.devtools.build.lib.packages.NoSuchThingException;
+import com.google.devtools.build.lib.packages.Package;
+import com.google.devtools.build.lib.packages.RawAttributeMapper;
+import com.google.devtools.build.lib.packages.Rule;
+import com.google.devtools.build.lib.packages.RuleClass;
+import com.google.devtools.build.lib.packages.Target;
+import com.google.devtools.build.lib.packages.Type;
+import com.google.devtools.build.lib.syntax.Label;
+
+import java.util.Collections;
+import java.util.Comparator;
+import java.util.List;
+
+/**
+ * Implementation of --compile_one_dependency.
+ */
+final class CompileOneDependencyTransformer {
+
+  private final PackageManager pkgManager;
+
+  public CompileOneDependencyTransformer(PackageManager pkgManager) {
+    this.pkgManager = pkgManager;
+  }
+
+  /**
+   * For each input file in the original result, returns a rule in the same package which has the
+   * input file as a source.
+   */
+  public ResolvedTargets<Target> transformCompileOneDependency(EventHandler eventHandler,
+      ResolvedTargets<Target> original) throws TargetParsingException {
+    if (original.hasError()) {
+      return original;
+    }
+    ResolvedTargets.Builder<Target> builder = ResolvedTargets.builder();
+    for (Target target : original.getTargets()) {
+      builder.add(transformCompileOneDependency(eventHandler, target));
+    }
+    return builder.build();
+  }
+
+  /**
+   * Returns a list of rules in the given package sorted by BUILD file order. When
+   * multiple rules depend on a target, we choose the first match in this list (after
+   * filtering for preferred dependencies - see below).
+   *
+   * <p>Rules with configurable attributes are skipped, as this code doesn't know which
+   * configuration will be applied, so it can't reliably determine what their 'srcs'
+   * will look like.
+   */
+  private Iterable<Rule> getOrderedRuleList(Package pkg) {
+    List<Rule> orderedList = Lists.newArrayList();
+    for (Rule rule : pkg.getTargets(Rule.class)) {
+      if (!rule.hasConfigurableAttributes()) {
+        orderedList.add(rule);
+      }
+    }
+
+    Collections.sort(orderedList, new Comparator<Rule>() {
+      @Override
+      public int compare(Rule o1, Rule o2) {
+        return Integer.compare(
+            o1.getLocation().getStartOffset(),
+            o2.getLocation().getStartOffset());
+      }
+    });
+    return orderedList;
+  }
+
+  private Target transformCompileOneDependency(EventHandler eventHandler, Target target)
+      throws TargetParsingException {
+    if (!(target instanceof FileTarget)) {
+      throw new TargetParsingException("--compile_one_dependency target '" +
+                                       target.getLabel() + "' must be a file");
+    }
+
+    Package pkg;
+    try {
+      pkg = pkgManager.getLoadedPackage(target.getLabel().getPackageIdentifier());
+    } catch (NoSuchPackageException e) {
+      throw new IllegalStateException(e);
+    }
+
+    Iterable<Rule> orderedRuleList = getOrderedRuleList(pkg);
+    // Consuming rule to return if no "preferred" rules have been found.
+    Rule fallbackRule = null;
+
+    for (Rule rule : orderedRuleList) {
+      try {
+        // The call to getSrcTargets here can be removed in favor of the
+        // rule.getLabels() call below once we update "srcs" for all rules.
+        if (SrcTargetUtil.getSrcTargets(eventHandler, rule, pkgManager).contains(target)) {
+          if (rule.getRuleClassObject().isPreferredDependency(target.getName())) {
+            return rule;
+          } else if (fallbackRule == null) {
+            fallbackRule = rule;
+          }
+        }
+      } catch (NoSuchThingException e) {
+        // Nothing to see here. Move along.
+      } catch (InterruptedException e) {
+        throw new TargetParsingException("interrupted");
+      }
+    }
+
+    Rule result = null;
+
+    // For each rule, see if it has directCompileTimeInputAttribute,
+    // and if so check the targets listed in that attribute match the label.
+    for (Rule rule : orderedRuleList) {
+      if (rule.getLabels(Rule.DIRECT_COMPILE_TIME_INPUT).contains(target.getLabel())) {
+        if (rule.getRuleClassObject().isPreferredDependency(target.getName())) {
+          result = rule;
+        } else if (fallbackRule == null) {
+          fallbackRule = rule;
+        }
+      }
+    }
+
+    if (result == null) {
+      result = fallbackRule;
+    }
+
+    if (result == null) {
+      throw new TargetParsingException(
+          "Couldn't find dependency on target '" + target.getLabel() + "'");
+    }
+
+    try {
+      // If the rule has source targets, return it.
+      if (!SrcTargetUtil.getSrcTargets(eventHandler, result, pkgManager).isEmpty()) {
+        return result;
+      }
+    } catch (NoSuchThingException e) {
+      throw new TargetParsingException(
+          "Couldn't find dependency on target '" + target.getLabel() + "'");
+    } catch (InterruptedException e) {
+      throw new TargetParsingException("interrupted");
+    }
+
+    for (Rule rule : orderedRuleList) {
+      RawAttributeMapper attributes = RawAttributeMapper.of(rule);
+      // We don't know what configuration we're using at this point, so we can't be sure
+      // which deps/srcs apply to this invocation if they're configurable for this rule.
+      // So exclude such rules for consideration.
+      if (attributes.isConfigurable("deps", Type.LABEL_LIST)
+          || attributes.isConfigurable("srcs", Type.LABEL_LIST)) {
+        continue;
+        }
+      RuleClass ruleClass = rule.getRuleClassObject();
+      if (ruleClass.hasAttr("deps", Type.LABEL_LIST) &&
+          ruleClass.hasAttr("srcs", Type.LABEL_LIST)) {
+        for (Label dep : attributes.get("deps", Type.LABEL_LIST)) {
+          if (dep.equals(result.getLabel())) {
+            if (!attributes.get("srcs", Type.LABEL_LIST).isEmpty()) {
+              return rule;
+            }
+          }
+        }
+      }
+    }
+
+    throw new TargetParsingException(
+        "Couldn't find dependency on target '" + target.getLabel() + "'");
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/pkgcache/FilteringPolicies.java b/src/main/java/com/google/devtools/build/lib/pkgcache/FilteringPolicies.java
new file mode 100644
index 0000000000..df01326462
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/pkgcache/FilteringPolicies.java
@@ -0,0 +1,126 @@
+// 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.pkgcache;
+
+import com.google.common.base.Preconditions;
+import com.google.devtools.build.lib.packages.Rule;
+import com.google.devtools.build.lib.packages.Target;
+import com.google.devtools.build.lib.packages.TargetUtils;
+
+import java.util.Objects;
+
+/**
+ * Utility class for predefined filtering policies.
+ */
+public final class FilteringPolicies {
+
+  private FilteringPolicies() {
+  }
+
+  /**
+   * Base class for singleton filtering policies.
+   */
+  private abstract static class AbstractFilteringPolicy implements FilteringPolicy {
+    @Override
+    public int hashCode() {
+      return getClass().getSimpleName().hashCode();
+    }
+
+    @Override
+    public boolean equals(Object obj) {
+      if (obj == null) {
+        return false;
+      }
+      if (obj == this) {
+        return true;
+      }
+      return getClass().equals(obj.getClass());
+    }
+  }
+
+  private static class NoFilter extends AbstractFilteringPolicy {
+    @Override
+    public boolean shouldRetain(Target target, boolean explicit) {
+      return true;
+    }
+  }
+
+  public static final FilteringPolicy NO_FILTER = new NoFilter();
+
+  private static class FilterManualAndObsolete extends AbstractFilteringPolicy {
+    @Override
+    public boolean shouldRetain(Target target, boolean explicit) {
+      return explicit || !(TargetUtils.hasManualTag(target) || TargetUtils.isObsolete(target));
+    }
+  }
+
+  public static final FilteringPolicy FILTER_MANUAL_AND_OBSOLETE = new FilterManualAndObsolete();
+
+  private static class FilterTests extends AbstractFilteringPolicy {
+    @Override
+    public boolean shouldRetain(Target target, boolean explicit) {
+      return TargetUtils.isTestOrTestSuiteRule(target)
+          && FILTER_MANUAL_AND_OBSOLETE.shouldRetain(target, explicit);
+    }
+  }
+
+  public static final FilteringPolicy FILTER_TESTS = new FilterTests();
+
+  private static class RulesOnly extends AbstractFilteringPolicy {
+    @Override
+    public boolean shouldRetain(Target target, boolean explicit) {
+      return target instanceof Rule;
+    }
+  }
+
+  public static final FilteringPolicy RULES_ONLY = new RulesOnly();
+
+  /**
+   * Returns the result of applying y, if target passes x.
+   */
+  public static FilteringPolicy and(final FilteringPolicy x,
+                                    final FilteringPolicy y) {
+    return new AndFilteringPolicy(x, y);
+  }
+
+  private static class AndFilteringPolicy implements FilteringPolicy {
+    private final FilteringPolicy firstPolicy;
+    private final FilteringPolicy secondPolicy;
+
+    public AndFilteringPolicy(FilteringPolicy firstPolicy, FilteringPolicy secondPolicy) {
+      this.firstPolicy = Preconditions.checkNotNull(firstPolicy);
+      this.secondPolicy = Preconditions.checkNotNull(secondPolicy);
+    }
+
+    @Override
+    public boolean shouldRetain(Target target, boolean explicit) {
+      return firstPolicy.shouldRetain(target, explicit)
+          && secondPolicy.shouldRetain(target, explicit);
+    }
+
+    @Override
+    public int hashCode() {
+      return Objects.hash(firstPolicy, secondPolicy);
+    }
+
+    @Override
+    public boolean equals(Object obj) {
+      if (!(obj instanceof AndFilteringPolicy)) {
+        return false;
+      }
+      AndFilteringPolicy other = (AndFilteringPolicy) obj;
+      return other.firstPolicy.equals(firstPolicy) && other.secondPolicy.equals(secondPolicy);
+    }
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/pkgcache/FilteringPolicy.java b/src/main/java/com/google/devtools/build/lib/pkgcache/FilteringPolicy.java
new file mode 100644
index 0000000000..ac27fb09dc
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/pkgcache/FilteringPolicy.java
@@ -0,0 +1,35 @@
+// 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.pkgcache;
+
+import com.google.devtools.build.lib.concurrent.ThreadSafety;
+import com.google.devtools.build.lib.packages.Target;
+
+import java.io.Serializable;
+
+/**
+ * A filtering policy defines how target patterns are matched. For instance, we may wish to select
+ * only tests, no tests, or remove obsolete targets.
+ */
+public interface FilteringPolicy extends Serializable {
+
+  /**
+   * Returns true if this target should be retained.
+   *
+   * @param explicit true iff the label was specified explicitly, as opposed to being discovered by
+   *                 a wildcard.
+   */
+  @ThreadSafety.ThreadSafe
+  boolean shouldRetain(Target target, boolean explicit);
+}
diff --git a/src/main/java/com/google/devtools/build/lib/pkgcache/LoadedPackage.java b/src/main/java/com/google/devtools/build/lib/pkgcache/LoadedPackage.java
new file mode 100644
index 0000000000..3c6f70f181
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/pkgcache/LoadedPackage.java
@@ -0,0 +1,46 @@
+// 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.pkgcache;
+
+import com.google.devtools.build.lib.events.Event;
+
+/**
+ * A loaded package that can verify whether it is still up to date.
+ */
+interface LoadedPackage {
+  /**
+   * Returns the actual loaded {@link Package} object.
+   */
+  Package getPackage();
+
+  /**
+   * Returns true iff the entry is still valid.
+   *
+   * <p>An entry is valid when the package it denotes has not been moved, deleted, or changed. This
+   * requires disk I/O to fetch metadata and re-evaluate globs.
+   */
+  boolean isValid() throws InterruptedException;
+
+  /**
+   * Returns true iff the the contents of the package are guaranteed not to have changed after
+   * between {@link #isValid()} calls and syncs of the associated package loader.
+   */
+  boolean contentsCouldNotHaveChanged();
+
+  /**
+   * Returns the set of events (sorted by the order they were reported) that occurred during the
+   * loading of the package.
+   */
+  Iterable<Event> getEvents();
+}
diff --git a/src/main/java/com/google/devtools/build/lib/pkgcache/LoadedPackageProvider.java b/src/main/java/com/google/devtools/build/lib/pkgcache/LoadedPackageProvider.java
new file mode 100644
index 0000000000..1c51810b50
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/pkgcache/LoadedPackageProvider.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.pkgcache;
+
+import com.google.devtools.build.lib.packages.NoSuchPackageException;
+import com.google.devtools.build.lib.packages.NoSuchTargetException;
+import com.google.devtools.build.lib.packages.Package;
+import com.google.devtools.build.lib.packages.PackageIdentifier;
+import com.google.devtools.build.lib.packages.Target;
+import com.google.devtools.build.lib.syntax.Label;
+
+/**
+ * Read-only API for retrieving packages, i.e., calling this API should not result in packages being
+ * loaded.
+ *
+ * <p><b>Concurrency</b>: Implementations should be thread-safe.
+ */
+// TODO(bazel-team): Skyframe doesn't really implement this - can we remove it?
+public interface LoadedPackageProvider {
+
+  /**
+   * Returns a package if it was recently loaded, i.e., since the most recent cache sync. This
+   * throws an exception if the package was not loaded, even if it exists on disk.
+   */
+  Package getLoadedPackage(PackageIdentifier packageIdentifier) throws NoSuchPackageException;
+
+  /**
+   * Returns a target if it was recently loaded, i.e., since the most recent cache sync. This
+   * throws an exception if the target was not loaded or not validated, even if it exists in the
+   * surrounding package.
+   */
+  Target getLoadedTarget(Label label) throws NoSuchPackageException, NoSuchTargetException;
+
+  /**
+   * Returns true iff the specified target is current, i.e. a request for its label using {@link
+   * #getLoadedTarget} would return the same target instance.
+   */
+  boolean isTargetCurrent(Target target);
+}
diff --git a/src/main/java/com/google/devtools/build/lib/pkgcache/LoadingFailedException.java b/src/main/java/com/google/devtools/build/lib/pkgcache/LoadingFailedException.java
new file mode 100644
index 0000000000..537746b89a
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/pkgcache/LoadingFailedException.java
@@ -0,0 +1,29 @@
+// 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.pkgcache;
+
+/**
+ * An exception indicating that there was a problem during the loading phase for one or more
+ * targets in such a way that the build cannot proceed (for example because keep_going is disabled).
+ */
+public class LoadingFailedException extends Exception {
+
+  public LoadingFailedException(String message) {
+    super(message);
+  }
+
+  public LoadingFailedException(String message, Throwable cause) {
+    super(message + ": " + cause.getMessage(), cause);
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/pkgcache/LoadingFailureEvent.java b/src/main/java/com/google/devtools/build/lib/pkgcache/LoadingFailureEvent.java
new file mode 100644
index 0000000000..d7e0256b13
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/pkgcache/LoadingFailureEvent.java
@@ -0,0 +1,39 @@
+// 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.pkgcache;
+
+import com.google.devtools.build.lib.syntax.Label;
+
+/**
+ * This event is fired during the build, when it becomes known that the loading
+ * of a target cannot be completed because of an error in one of its
+ * dependencies.
+ */
+public class LoadingFailureEvent {
+  private final Label failedTarget;
+  private final Label failureReason;
+
+  public LoadingFailureEvent(Label failedTarget, Label failureReason) {
+    this.failedTarget = failedTarget;
+    this.failureReason = failureReason;
+  }
+
+  public Label getFailedTarget() {
+    return failedTarget;
+  }
+
+  public Label getFailureReason() {
+    return failureReason;
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/pkgcache/LoadingPhaseCompleteEvent.java b/src/main/java/com/google/devtools/build/lib/pkgcache/LoadingPhaseCompleteEvent.java
new file mode 100644
index 0000000000..19c22ecb1f
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/pkgcache/LoadingPhaseCompleteEvent.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.pkgcache;
+
+import com.google.common.base.Function;
+import com.google.common.collect.Iterables;
+import com.google.devtools.build.lib.packages.Target;
+import com.google.devtools.build.lib.syntax.Label;
+
+import java.util.Collection;
+
+/**
+ * This event is fired after the loading phase is complete.
+ */
+public class LoadingPhaseCompleteEvent {
+  private final Collection<Target> targets;
+  private final Collection<Target> filteredTargets;
+  private final PackageManager.PackageManagerStatistics pkgManagerStats;
+  private final long timeInMs;
+
+  /**
+   * Construct the event.
+   *
+   * @param targets the set of active targets that remain
+   * @param pkgManagerStats statistics about the package cache
+   */
+  public LoadingPhaseCompleteEvent(Collection<Target> targets, Collection<Target> filteredTargets,
+      PackageManager.PackageManagerStatistics pkgManagerStats, long timeInMs) {
+    this.targets = targets;
+    this.filteredTargets = filteredTargets;
+    this.pkgManagerStats = pkgManagerStats;
+    this.timeInMs = timeInMs;
+  }
+
+  /**
+   * @return The set of active targets remaining, which is a subset of the
+   *         targets we attempted to load.
+   */
+  public Collection<Target> getTargets() {
+    return targets;
+  }
+
+  /**
+   * @return The set of filtered targets.
+   */
+  public Collection<Target> getFilteredTargets() {
+    return filteredTargets;
+  }
+
+  /**
+   * @return The set of active target labels remaining, which is a subset of the
+   *         targets we attempted to load.
+   */
+  public Iterable<Label> getLabels() {
+    return Iterables.transform(targets, TO_LABEL);
+  }
+  
+  public long getTimeInMs() {
+    return timeInMs;
+  }
+
+  /**
+   * Returns the PackageCache statistics.
+   */
+  public PackageManager.PackageManagerStatistics getPkgManagerStats() {
+    return pkgManagerStats;
+  }
+
+  private static final Function<Target, Label> TO_LABEL = new Function<Target, Label>() {
+    @Override
+    public Label apply(Target input) {
+      return input.getLabel();
+    }
+  };
+}
diff --git a/src/main/java/com/google/devtools/build/lib/pkgcache/LoadingPhaseRunner.java b/src/main/java/com/google/devtools/build/lib/pkgcache/LoadingPhaseRunner.java
new file mode 100644
index 0000000000..4d8eea607f
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/pkgcache/LoadingPhaseRunner.java
@@ -0,0 +1,661 @@
+// 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.pkgcache;
+
+import com.google.common.base.Preconditions;
+import com.google.common.base.Predicate;
+import com.google.common.base.Predicates;
+import com.google.common.base.Stopwatch;
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableMap;
+import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.Iterables;
+import com.google.common.collect.ListMultimap;
+import com.google.common.collect.Multimap;
+import com.google.common.collect.Sets;
+import com.google.common.eventbus.EventBus;
+import com.google.devtools.build.lib.cmdline.ResolvedTargets;
+import com.google.devtools.build.lib.cmdline.TargetParsingException;
+import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadCompatible;
+import com.google.devtools.build.lib.events.DelegatingEventHandler;
+import com.google.devtools.build.lib.events.Event;
+import com.google.devtools.build.lib.events.EventHandler;
+import com.google.devtools.build.lib.packages.NoSuchPackageException;
+import com.google.devtools.build.lib.packages.NoSuchTargetException;
+import com.google.devtools.build.lib.packages.NoSuchThingException;
+import com.google.devtools.build.lib.packages.NonconfigurableAttributeMapper;
+import com.google.devtools.build.lib.packages.Package;
+import com.google.devtools.build.lib.packages.PackageIdentifier;
+import com.google.devtools.build.lib.packages.Rule;
+import com.google.devtools.build.lib.packages.Target;
+import com.google.devtools.build.lib.packages.TestSize;
+import com.google.devtools.build.lib.packages.TestTargetUtils;
+import com.google.devtools.build.lib.packages.TestTimeout;
+import com.google.devtools.build.lib.packages.Type;
+import com.google.devtools.build.lib.syntax.Label;
+import com.google.devtools.build.lib.vfs.Path;
+import com.google.devtools.build.lib.vfs.PathFragment;
+import com.google.devtools.common.options.Converters.CommaSeparatedOptionListConverter;
+import com.google.devtools.common.options.Option;
+import com.google.devtools.common.options.OptionsBase;
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+import java.util.concurrent.TimeUnit;
+import java.util.logging.Logger;
+
+import javax.annotation.Nullable;
+
+/**
+ * Implements the loading phase; responsible for:
+ * <ul>
+ *   <li>target pattern evaluation
+ *   <li>test suite expansion
+ *   <li>loading the labels needed to construct the build configuration
+ *   <li>loading the labels needed for the analysis with the build configuration
+ *   <li>loading the transitive closure of the targets and the configuration labels
+ * </ul>
+ *
+ * <p>In order to ensure correctness of incremental loading and of full cache hits, this class is
+ * very restrictive about access to its internal state and to its collaborators. In particular, none
+ * of the collaborators of this class may change in incompatible ways, such as changing the relative
+ * working directory for the target pattern parser, without notifying this class.
+ *
+ * <p>For full caching, this class tracks the exact values of all inputs to the loading phase. To
+ * maximize caching, it is vital that these change as rarely as possible.
+ */
+public class LoadingPhaseRunner {
+
+  /**
+   * Loading phase options.
+   */
+  public static class Options extends OptionsBase {
+
+    @Option(name = "loading_phase_threads",
+        defaultValue = "200",
+        category = "undocumented",
+        help = "Number of parallel threads to use for the loading phase.")
+    public int loadingPhaseThreads;
+
+    @Option(name = "build_tests_only",
+        defaultValue = "false",
+        category = "what",
+        help = "If specified, only *_test and test_suite rules will be built "
+          + "and other targets specified on the command line will be ignored. "
+          + "By default everything that was requested will be built.")
+    public boolean buildTestsOnly;
+
+    @Option(name = "compile_one_dependency",
+            defaultValue = "false",
+            category = "what",
+            help = "Compile a single dependency of the argument files.  "
+            + "This is useful for syntax checking source files in IDEs, "
+            + "for example, by rebuilding a single target that depends on "
+            + "the source file to detect errors as early as possible in the "
+            + "edit/build/test cycle.  This argument affects the way all "
+            + "non-flag arguments are interpreted; instead of being targets "
+            + "to build they are source filenames.  For each source filename "
+            + "an arbitrary target that depends on it will be built.")
+    public boolean compileOneDependency;
+
+    @Option(name = "test_tag_filters",
+        converter = CommaSeparatedOptionListConverter.class,
+        defaultValue = "",
+        category = "what",
+        help = "Specifies a comma-separated list of test tags. Each tag can be optionally " +
+               "preceded with '-' to specify excluded tags. Only those test targets will be " +
+               "found that contain at least one included tag and do not contain any excluded " +
+               "tags. This option affects --build_tests_only behavior and the test command."
+        )
+    public List<String> testTagFilterList;
+
+    @Option(name = "test_size_filters",
+        converter = TestSize.TestSizeFilterConverter.class,
+        defaultValue = "",
+        category = "what",
+        help = "Specifies a comma-separated list of test sizes. Each size can be optionally " +
+               "preceded with '-' to specify excluded sizes. Only those test targets will be " +
+               "found that contain at least one included size and do not contain any excluded " +
+               "sizes. This option affects --build_tests_only behavior and the test command."
+        )
+    public Set<TestSize> testSizeFilterSet;
+
+    @Option(name = "test_timeout_filters",
+        converter = TestTimeout.TestTimeoutFilterConverter.class,
+        defaultValue = "",
+        category = "what",
+        help = "Specifies a comma-separated list of test timeouts. Each timeout can be " +
+               "optionally preceded with '-' to specify excluded timeouts. Only those test " +
+               "targets will be found that contain at least one included timeout and do not " +
+               "contain any excluded timeouts. This option affects --build_tests_only behavior " +
+               "and the test command."
+        )
+    public Set<TestTimeout> testTimeoutFilterSet;
+
+    @Option(name = "test_lang_filters",
+        converter = CommaSeparatedOptionListConverter.class,
+        defaultValue = "",
+        category = "what",
+        help = "Specifies a comma-separated list of test languages. Each language can be " +
+               "optionally preceded with '-' to specify excluded languages. Only those " +
+               "test targets will be found that are written in the specified languages. " +
+               "The name used for each language should be the same as the language prefix in the " +
+               "*_test rule, e.g. one of 'cc', 'java', 'py', etc." +
+               "This option affects --build_tests_only behavior and the test command."
+        )
+    public List<String> testLangFilterList;
+  }
+
+  /**
+   * A callback interface to notify the caller about specific events.
+   * TODO(bazel-team): maybe we should use the EventBus instead?
+   */
+  public interface Callback {
+    /**
+     * Called after the target patterns have been resolved to give the caller a chance to validate
+     * the list before proceeding.
+     */
+    void notifyTargets(Collection<Target> targets) throws LoadingFailedException;
+
+    /**
+     * Called after loading has finished, to notify the caller about the visited packages.
+     *
+     * <p>The set of visited packages is the set of packages in the transitive closure of the
+     * union of the top level targets.
+     */
+    void notifyVisitedPackages(Set<PackageIdentifier> visitedPackages);
+  }
+
+  /**
+   * The result of the loading phase, i.e., whether there were errors, and which targets were
+   * successfully loaded, plus some related metadata.
+   */
+  public static final class LoadingResult {
+    private final boolean hasTargetPatternError;
+    private final boolean hasLoadingError;
+    private final ImmutableSet<Target> targetsToAnalyze;
+    private final ImmutableSet<Target> testsToRun;
+    private final ImmutableMap<PackageIdentifier, Path> packageRoots;
+    // TODO(bazel-team): consider moving this to LoadedPackageProvider
+    private final ImmutableSet<PackageIdentifier> visitedPackages;
+
+    public LoadingResult(boolean hasTargetPatternError, boolean hasLoadingError,
+        Collection<Target> targetsToAnalyze, Collection<Target> testsToRun,
+        ImmutableMap<PackageIdentifier, Path> packageRoots,
+        Set<PackageIdentifier> visitedPackages) {
+      this.hasTargetPatternError = hasTargetPatternError;
+      this.hasLoadingError = hasLoadingError;
+      this.targetsToAnalyze =
+          targetsToAnalyze == null ? null : ImmutableSet.copyOf(targetsToAnalyze);
+      this.testsToRun = testsToRun == null ? null : ImmutableSet.copyOf(testsToRun);
+      this.packageRoots = packageRoots;
+      this.visitedPackages = ImmutableSet.copyOf(visitedPackages);
+    }
+
+    /** Whether there were errors during target pattern evaluation. */
+    public boolean hasTargetPatternError() {
+      return hasTargetPatternError;
+    }
+
+    /** Whether there were errors during the loading phase. */
+    public boolean hasLoadingError() {
+      return hasLoadingError;
+    }
+
+    /** Successfully loaded targets that should be built. */
+    public Collection<Target> getTargets() {
+      return targetsToAnalyze;
+    }
+
+    /** Successfully loaded targets that should be run as tests. Must be a subset of the targets. */
+    public Collection<Target> getTestsToRun() {
+      return testsToRun;
+    }
+
+    /**
+     * The map from package names to the package root where each package was found; this is used to
+     * set up the symlink tree.
+     */
+    public ImmutableMap<PackageIdentifier, Path> getPackageRoots() {
+      return packageRoots;
+    }
+
+    /**
+     * Returns all packages that were visited during this loading phase.
+     *
+     * <p>We use this to decide when to evict ConfiguredTarget nodes from the graph.
+     */
+    @ThreadCompatible
+    private ImmutableSet<PackageIdentifier> getVisitedPackages() {
+      return visitedPackages;
+    }
+  }
+
+  private static final class ParseFailureListenerImpl extends DelegatingEventHandler
+      implements ParseFailureListener {
+    private final EventBus eventBus;
+
+    private ParseFailureListenerImpl(EventHandler delegate, EventBus eventBus) {
+      super(delegate);
+      this.eventBus = eventBus;
+    }
+
+    @Override
+    public void parsingError(String targetPattern, String message) {
+      if (eventBus != null) {
+        eventBus.post(new ParsingFailedEvent(targetPattern, message));
+      }
+    }
+  }
+
+  private static final Logger LOG = Logger.getLogger(LoadingPhaseRunner.class.getName());
+
+  private final PackageManager packageManager;
+  private final TargetPatternEvaluator targetPatternEvaluator;
+  private final Set<String> ruleNames;
+  private final TransitivePackageLoader pkgLoader;
+
+  public LoadingPhaseRunner(PackageManager packageManager,
+                            Set<String> ruleNames) {
+    this.packageManager = packageManager;
+    this.targetPatternEvaluator = packageManager.getTargetPatternEvaluator();
+    this.ruleNames = ruleNames;
+    this.pkgLoader = packageManager.newTransitiveLoader();
+  }
+
+  public TargetPatternEvaluator getTargetPatternEvaluator() {
+    return targetPatternEvaluator;
+  }
+
+  public void updatePatternEvaluator(PathFragment relativeWorkingDirectory) {
+    targetPatternEvaluator.updateOffset(relativeWorkingDirectory);
+  }
+
+  /**
+   * This method only exists for the benefit of InfoCommand, which needs to construct
+   * a {@code BuildConfigurationCollection} without running a full loading phase. Don't
+   * add any more clients; instead, we should change info so that it doesn't need the configuration.
+   */
+  public LoadedPackageProvider loadForConfigurations(EventHandler eventHandler,
+      Set<Label> labelsToLoad, boolean keepGoing) throws InterruptedException {
+    // Use a new Label Visitor here to avoid erasing the cache on the existing one.
+    TransitivePackageLoader transitivePackageLoader = packageManager.newTransitiveLoader();
+    boolean loadingSuccessful = transitivePackageLoader.sync(
+        eventHandler, ImmutableSet.<Target>of(),
+        labelsToLoad, keepGoing, /*parallelThreads=*/10,
+        /*maxDepth=*/Integer.MAX_VALUE);
+    return loadingSuccessful ? packageManager : null;
+  }
+
+  /**
+   * Performs target pattern evaluation, test suite expansion (if requested), and loads the
+   * transitive closure of the resulting targets as well as of the targets needed to use the
+   * given build configuration provider.
+   */
+  public LoadingResult execute(EventHandler eventHandler, EventBus eventBus,
+      List<String> targetPatterns, Options options,
+      ListMultimap<String, Label> labelsToLoadUnconditionally, boolean keepGoing,
+      boolean determineTests, @Nullable Callback callback)
+          throws TargetParsingException, LoadingFailedException, InterruptedException {
+    LOG.info("Starting pattern evaluation");
+    Stopwatch timer = Stopwatch.createStarted();
+    if (options.buildTestsOnly && options.compileOneDependency) {
+      throw new LoadingFailedException("--compile_one_dependency cannot be used together with "
+          + "the --build_tests_only option or the 'bazel test' command ");
+    }
+
+    EventHandler parseFailureListener = new ParseFailureListenerImpl(eventHandler, eventBus);
+    // Determine targets to build:
+    ResolvedTargets<Target> targets = getTargetsToBuild(parseFailureListener,
+        targetPatterns, options.compileOneDependency, keepGoing);
+
+    ImmutableSet<Target> filteredTargets = targets.getFilteredTargets();
+
+    boolean buildTestsOnly = options.buildTestsOnly;
+    ImmutableSet<Target> testsToRun = null;
+    ImmutableSet<Target> testFilteredTargets = ImmutableSet.of();
+
+    // Now we have a list of targets to build. If the --build_tests_only option was specified or we
+    // want to run tests, we need to determine the list of targets to test. For that, we remove
+    // manual tests and apply the command line filters. Also, if --build_tests_only is specified,
+    // then the list of filtered targets will be set as build list as well.
+    if (determineTests || buildTestsOnly) {
+      // Parse the targets to get the tests.
+      ResolvedTargets<Target> testTargets = determineTests(parseFailureListener,
+          targetPatterns, options, keepGoing);
+      if (testTargets.getTargets().isEmpty() && !testTargets.getFilteredTargets().isEmpty()) {
+        eventHandler.handle(Event.warn("All specified test targets were excluded by filters"));
+      }
+
+      if (buildTestsOnly) {
+        // Replace original targets to build with test targets, so that only targets that are
+        // actually going to be built are loaded in the loading phase. Note that this has a side
+        // effect that any test_suite target requested to be built is replaced by the set of *_test
+        // targets it represents; for example, this affects the status and the summary reports.
+        Set<Target> allFilteredTargets = new HashSet<>();
+        allFilteredTargets.addAll(targets.getTargets());
+        allFilteredTargets.addAll(targets.getFilteredTargets());
+        allFilteredTargets.removeAll(testTargets.getTargets());
+        allFilteredTargets.addAll(testTargets.getFilteredTargets());
+        testFilteredTargets = ImmutableSet.copyOf(allFilteredTargets);
+        filteredTargets = ImmutableSet.of();
+
+        targets = ResolvedTargets.<Target>builder()
+            .merge(testTargets)
+            .mergeError(targets.hasError())
+            .build();
+        if (determineTests) {
+          testsToRun = testTargets.getTargets();
+        }
+      } else /*if (determineTests)*/ {
+        testsToRun = testTargets.getTargets();
+        targets = ResolvedTargets.<Target>builder()
+            .merge(targets)
+            // Avoid merge() here which would remove the filteredTargets from the targets.
+            .addAll(testsToRun)
+            .mergeError(testTargets.hasError())
+            .build();
+        // filteredTargets is correct in this case - it cannot contain tests that got back in
+        // through test_suite expansion, because the test determination would also filter those out.
+        // However, that's not obvious, and it might be better to explicitly recompute it.
+      }
+      if (testsToRun != null) {
+        // Note that testsToRun can still be null here, if buildTestsOnly && !shouldRunTests.
+        Preconditions.checkState(targets.getTargets().containsAll(testsToRun));
+      }
+    }
+
+    eventBus.post(new TargetParsingCompleteEvent(targets.getTargets(),
+        filteredTargets, testFilteredTargets,
+        timer.stop().elapsed(TimeUnit.MILLISECONDS)));
+
+    if (targets.hasError()) {
+      eventHandler.handle(Event.warn("Target pattern parsing failed. Continuing anyway"));
+    }
+
+    if (callback != null) {
+      callback.notifyTargets(targets.getTargets());
+    }
+
+    maybeReportDeprecation(eventHandler, targets.getTargets());
+
+    // Load the transitive closure of all targets.
+    LoadingResult result = doLoadingPhase(eventHandler, eventBus, targets.getTargets(),
+        testsToRun, labelsToLoadUnconditionally, keepGoing, options.loadingPhaseThreads,
+        targets.hasError());
+
+    if (callback != null) {
+      callback.notifyVisitedPackages(result.getVisitedPackages());
+    }
+
+    return result;
+  }
+
+  /**
+   * Visit the transitive closure of the targets, populating the package cache
+   * and ensuring that all labels can be resolved and all rules were free from
+   * errors.
+   *
+   * @param targetsToLoad the list of command-line target patterns specified by the user
+   * @param testsToRun the tests to run as a subset of the targets to load
+   * @param labelsToLoadUnconditionally the labels to load unconditionally (presumably for the build
+   *                                    configuration)
+   * @param keepGoing if true, don't throw ViewCreationFailedException if some
+   *                  targets could not be loaded, just skip thm.
+   */
+  private LoadingResult doLoadingPhase(EventHandler eventHandler, EventBus eventBus,
+      ImmutableSet<Target> targetsToLoad, Collection<Target> testsToRun,
+      ListMultimap<String, Label> labelsToLoadUnconditionally, boolean keepGoing,
+      int loadingPhaseThreads, boolean hasError)
+          throws InterruptedException, LoadingFailedException {
+    eventHandler.handle(Event.progress("Loading..."));
+    Stopwatch timer = Stopwatch.createStarted();
+    LOG.info("Starting loading phase");
+
+    Set<Label> labelsToLoad = ImmutableSet.copyOf(labelsToLoadUnconditionally.values());
+
+    // For each label in {@code targetsToLoad}, ensure that the target to which
+    // it refers exists, and also every target in its transitive closure of label
+    // dependencies. Success guarantees that a call to
+    // {@code getConfiguredTarget} for the same targets will not fail; the
+    // configuration process is intolerant of missing packages/targets. Before
+    // calling getConfiguredTarget(), clients must ensure that all necessary
+    // packages/targets have been visited since the last sync/clear.
+    boolean loadingSuccessful = pkgLoader.sync(eventHandler, targetsToLoad, labelsToLoad,
+          keepGoing, loadingPhaseThreads, Integer.MAX_VALUE);
+
+    ImmutableSet<Target> targetsToAnalyze;
+    if (loadingSuccessful) {
+      // Success: all loaded targets will be analyzed.
+      targetsToAnalyze = targetsToLoad;
+    } else if (keepGoing) {
+      // Keep going: filter out the error-free targets and only continue with those.
+      targetsToAnalyze = filterErrorFreeTargets(eventBus, targetsToLoad,
+          pkgLoader, labelsToLoadUnconditionally);
+
+      // Tell the user about the subset of successful targets.
+      int requested = targetsToLoad.size();
+      int loaded = targetsToAnalyze.size();
+      if (0 < loaded && loaded < requested) {
+        String message = String.format("Loading succeeded for only %d of %d targets", loaded,
+            requested);
+        eventHandler.handle(Event.info(message));
+        LOG.info(message);
+      }
+    } else {
+      throw new LoadingFailedException("Loading failed; build aborted");
+    }
+
+    Set<Target> filteredTargets = targetsToAnalyze;
+    try {
+      // We use strict test_suite expansion here to match the analysis-time checks.
+      ResolvedTargets<Target> expandedResult = TestTargetUtils.expandTestSuites(
+          packageManager, eventHandler, targetsToAnalyze, /*strict=*/true, /*keepGoing=*/true);
+      targetsToAnalyze = expandedResult.getTargets();
+      filteredTargets = Sets.difference(filteredTargets, targetsToAnalyze);
+      if (expandedResult.hasError()) {
+        if (!keepGoing) {
+          throw new LoadingFailedException("Could not expand test suite target");
+        }
+        loadingSuccessful = false;
+      }
+    } catch (TargetParsingException e) {
+      // This shouldn't happen, because we've already loaded the targets successfully.
+      throw (AssertionError) (new AssertionError("Unexpected target failure").initCause(e));
+    }
+
+    // Perform some operations on the set of packages containing the collected targets.
+    ImmutableMap<PackageIdentifier, Path> packageRoots = collectPackageRoots(
+        pkgLoader.getErrorFreeVisitedPackages());
+
+    Set<PackageIdentifier> visitedPackageNames = pkgLoader.getVisitedPackageNames();
+
+    // Clear some targets from the cache to free memory.
+    packageManager.partiallyClear();
+
+    eventBus.post(new LoadingPhaseCompleteEvent(
+        targetsToAnalyze, filteredTargets, packageManager.getStatistics(),
+        timer.stop().elapsed(TimeUnit.MILLISECONDS)));
+    LOG.info("Loading phase finished");
+
+    // testsToRun can contain targets that aren't analyzed, but the BuildView ignores those.
+    return new LoadingResult(hasError, !loadingSuccessful, targetsToAnalyze, testsToRun,
+        packageRoots, visitedPackageNames);
+  }
+
+  private Collection<Target> getTargetsForLabels(Collection<Label> labels) {
+    Set<Target> result = new HashSet<>();
+
+    for (Label label : labels) {
+      try {
+        result.add(packageManager.getLoadedTarget(label));
+      } catch (NoSuchPackageException e) {
+        Package pkg = Preconditions.checkNotNull(e.getPackage());
+        try {
+          result.add(pkg.getTarget(label.getName()));
+        } catch (NoSuchTargetException ex) {
+          throw new IllegalStateException(ex);
+        }
+      } catch (NoSuchThingException e) {
+        throw new IllegalStateException(e);  // The target should have been loaded
+      }
+    }
+
+    return result;
+  }
+
+  private ImmutableSet<Target> filterErrorFreeTargets(
+      EventBus eventBus, Collection<Target> targetsToLoad,
+      TransitivePackageLoader pkgLoader,
+      ListMultimap<String, Label> labelsToLoadUnconditionally) throws LoadingFailedException {
+    // Error out if any of the labels needed for the configuration could not be loaded.
+    Collection<Label> labelsToLoad = new ArrayList<>(labelsToLoadUnconditionally.values());
+    for (Target target : targetsToLoad) {
+      labelsToLoad.add(target.getLabel());
+    }
+    Multimap<Label, Label> rootCauses = pkgLoader.getRootCauses(labelsToLoad);
+    for (Map.Entry<String, Label> entry : labelsToLoadUnconditionally.entries()) {
+      if (rootCauses.containsKey(entry.getValue())) {
+        throw new LoadingFailedException("Failed to load required " + entry.getKey()
+            + " target: '" + entry.getValue() + "'");
+      }
+    }
+
+    // Post root causes for command-line targets that could not be loaded.
+    for (Map.Entry<Label, Label> entry : rootCauses.entries()) {
+      eventBus.post(new LoadingFailureEvent(entry.getKey(), entry.getValue()));
+    }
+
+    return ImmutableSet.copyOf(Sets.difference(ImmutableSet.copyOf(targetsToLoad),
+        ImmutableSet.copyOf(getTargetsForLabels(rootCauses.keySet()))));
+  }
+
+  /**
+   * Returns a map of collected package names to root paths.
+   */
+  private static ImmutableMap<PackageIdentifier, Path> collectPackageRoots(
+      Collection<Package> packages) {
+    // Make a map of the package names to their root paths.
+    ImmutableMap.Builder<PackageIdentifier, Path> packageRoots = ImmutableMap.builder();
+    for (Package pkg : packages) {
+      packageRoots.put(pkg.getPackageIdentifier(), pkg.getSourceRoot());
+    }
+    return packageRoots.build();
+  }
+
+  /**
+   * Interpret the command-line arguments.
+   *
+   * @param targetPatterns the list of command-line target patterns specified by the user
+   * @param compileOneDependency if true, enables alternative interpretation of targetPatterns; see
+   *     {@link Options#compileOneDependency}
+   * @throws TargetParsingException if parsing failed and !keepGoing
+   */
+  private ResolvedTargets<Target> getTargetsToBuild(EventHandler eventHandler,
+      List<String> targetPatterns, boolean compileOneDependency,
+      boolean keepGoing) throws TargetParsingException, InterruptedException {
+    ResolvedTargets<Target> result =
+        targetPatternEvaluator.parseTargetPatternList(eventHandler, targetPatterns,
+            FilteringPolicies.FILTER_MANUAL_AND_OBSOLETE, keepGoing);
+    if (compileOneDependency) {
+      return new CompileOneDependencyTransformer(packageManager)
+          .transformCompileOneDependency(eventHandler, result);
+    }
+    return result;
+  }
+
+  /**
+   * Interpret test target labels from the command-line arguments and return the corresponding set
+   * of targets, handling the filter flags, and expanding test suites.
+   *
+   * @param eventHandler the error event eventHandler
+   * @param targetPatterns the list of command-line target patterns specified by the user
+   * @param options the loading phase options
+   * @param keepGoing value of the --keep_going flag
+   */
+  private ResolvedTargets<Target> determineTests(EventHandler eventHandler,
+      List<String> targetPatterns, Options options, boolean keepGoing)
+          throws TargetParsingException, InterruptedException {
+    // Parse the targets to get the tests.
+    ResolvedTargets.Builder<Target> testTargetsBuilder = ResolvedTargets.builder();
+    for (String targetPattern : targetPatterns) {
+      if (targetPattern.startsWith("-")) {
+        ResolvedTargets<Target> someNegativeTargets = targetPatternEvaluator.parseTargetPatternList(
+            eventHandler, ImmutableList.of(targetPattern.substring(1)),
+            FilteringPolicies.FILTER_TESTS, keepGoing);
+        ResolvedTargets<Target> moreNegativeTargets = TestTargetUtils.expandTestSuites(
+            packageManager, eventHandler, someNegativeTargets.getTargets(), /*strict=*/false,
+            keepGoing);
+        testTargetsBuilder.filter(Predicates.not(Predicates.in(moreNegativeTargets.getTargets())));
+        testTargetsBuilder.mergeError(moreNegativeTargets.hasError());
+      } else {
+        ResolvedTargets<Target> somePositiveTargets = targetPatternEvaluator.parseTargetPatternList(
+            eventHandler, ImmutableList.of(targetPattern),
+            FilteringPolicies.FILTER_TESTS, keepGoing);
+        ResolvedTargets<Target> morePositiveTargets = TestTargetUtils.expandTestSuites(
+            packageManager, eventHandler, somePositiveTargets.getTargets(), /*strict=*/false,
+            keepGoing);
+        testTargetsBuilder.addAll(morePositiveTargets.getTargets());
+        testTargetsBuilder.mergeError(morePositiveTargets.hasError());
+      }
+    }
+    testTargetsBuilder.filter(getTestFilter(eventHandler, options));
+    return testTargetsBuilder.build();
+  }
+
+  /**
+   * Convert the options into a test filter.
+   */
+  private Predicate<Target> getTestFilter(EventHandler eventHandler, Options options) {
+    Predicate<Target> testFilter = Predicates.alwaysTrue();
+    if (!options.testSizeFilterSet.isEmpty()) {
+      testFilter = Predicates.and(testFilter,
+          TestTargetUtils.testSizeFilter(options.testSizeFilterSet));
+    }
+    if (!options.testTimeoutFilterSet.isEmpty()) {
+      testFilter = Predicates.and(testFilter,
+          TestTargetUtils.testTimeoutFilter(options.testTimeoutFilterSet));
+    }
+    if (!options.testTagFilterList.isEmpty()) {
+      testFilter = Predicates.and(testFilter,
+          TestTargetUtils.tagFilter(options.testTagFilterList));
+    }
+    if (!options.testLangFilterList.isEmpty()) {
+      testFilter = Predicates.and(testFilter,
+          TestTargetUtils.testLangFilter(options.testLangFilterList, eventHandler, ruleNames));
+    }
+    return testFilter;
+  }
+
+  /**
+   * Emit a warning when a deprecated target is mentioned on the command line.
+   *
+   * <p>Note that this does not stop us from emitting "target X depends on deprecated target Y"
+   * style warnings for the same target and it is a good thing; <i>depending</i> on a target and
+   * <i>wanting</i> to build it are different things.
+   */
+  private void maybeReportDeprecation(EventHandler eventHandler, Collection<Target> targets) {
+    for (Rule rule : Iterables.filter(targets, Rule.class)) {
+      if (rule.isAttributeValueExplicitlySpecified("deprecation")) {
+        eventHandler.handle(Event.warn(rule.getLocation(), String.format(
+            "target '%s' is deprecated: %s", rule.getLabel(),
+            NonconfigurableAttributeMapper.of(rule).get("deprecation", Type.STRING))));
+      }
+    }
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/pkgcache/PackageCacheBackedTargetPatternResolver.java b/src/main/java/com/google/devtools/build/lib/pkgcache/PackageCacheBackedTargetPatternResolver.java
new file mode 100644
index 0000000000..e4dc0100b8
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/pkgcache/PackageCacheBackedTargetPatternResolver.java
@@ -0,0 +1,263 @@
+// 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.pkgcache;
+
+import com.google.common.base.Preconditions;
+import com.google.devtools.build.lib.cmdline.LabelValidator;
+import com.google.devtools.build.lib.cmdline.ResolvedTargets;
+import com.google.devtools.build.lib.cmdline.TargetParsingException;
+import com.google.devtools.build.lib.cmdline.TargetPatternResolver;
+import com.google.devtools.build.lib.events.Event;
+import com.google.devtools.build.lib.events.EventHandler;
+import com.google.devtools.build.lib.packages.BuildFileContainsErrorsException;
+import com.google.devtools.build.lib.packages.NoSuchPackageException;
+import com.google.devtools.build.lib.packages.NoSuchTargetException;
+import com.google.devtools.build.lib.packages.NoSuchThingException;
+import com.google.devtools.build.lib.packages.Package;
+import com.google.devtools.build.lib.packages.PackageIdentifier;
+import com.google.devtools.build.lib.packages.Target;
+import com.google.devtools.build.lib.syntax.Label;
+import com.google.devtools.build.lib.vfs.PathFragment;
+
+import java.util.concurrent.ThreadPoolExecutor;
+
+/**
+ * An implementation of the {@link TargetPatternResolver} that uses the {@link
+ * RecursivePackageProvider} as the backing implementation.
+ */
+final class PackageCacheBackedTargetPatternResolver implements TargetPatternResolver<Target> {
+
+  private final RecursivePackageProvider packageProvider;
+  private final EventHandler eventHandler;
+  private final boolean keepGoing;
+  private final FilteringPolicy policy;
+  private final ThreadPoolExecutor packageVisitorPool;
+
+  PackageCacheBackedTargetPatternResolver(RecursivePackageProvider packageProvider,
+      EventHandler eventHandler, boolean keepGoing, FilteringPolicy policy,
+      ThreadPoolExecutor packageVisitorPool) {
+    this.packageProvider = packageProvider;
+    this.eventHandler = eventHandler;
+    this.keepGoing = keepGoing;
+    this.policy = policy;
+    this.packageVisitorPool = packageVisitorPool;
+  }
+
+  @Override
+  public void warn(String msg) {
+    eventHandler.handle(Event.warn(msg));
+  }
+
+  @Override
+  public Target getTargetOrNull(String targetName) throws InterruptedException {
+    try {
+      return packageProvider.getTarget(eventHandler, Label.parseAbsolute(targetName));
+    } catch (NoSuchPackageException | NoSuchTargetException | Label.SyntaxException e) {
+      return null;
+    }
+  }
+
+  @Override
+  public ResolvedTargets<Target> getExplicitTarget(String targetName)
+      throws TargetParsingException, InterruptedException {
+    Label label = TargetPatternResolverUtil.label(targetName);
+    return getExplicitTarget(label, targetName);
+  }
+
+  private ResolvedTargets<Target> getExplicitTarget(Label label, String originalLabel)
+      throws TargetParsingException, InterruptedException {
+    try {
+      Target target = packageProvider.getTarget(eventHandler, label);
+      if (policy.shouldRetain(target, true)) {
+        return ResolvedTargets.of(target);
+      }
+      return ResolvedTargets.<Target>empty();
+    } catch (BuildFileContainsErrorsException e) {
+      // We don't need to report an error here because errors
+      // would have already been reported in this case.
+      return handleParsingError(eventHandler, originalLabel,
+          new TargetParsingException(e.getMessage(), e), keepGoing);
+    } catch (NoSuchThingException e) {
+      return handleParsingError(eventHandler, originalLabel,
+          new TargetParsingException(e.getMessage(), e), keepGoing);
+    }
+  }
+
+  /**
+   * Handles an error differently based on the value of keepGoing.
+   *
+   * @param badPattern The pattern we were unable to parse.
+   * @param e The underlying exception.
+   * @param keepGoing It true, report a warning and return.
+   *     If false, throw the exception.
+   * @return the empty set.
+   * @throws TargetParsingException if !keepGoing.
+   */
+  private ResolvedTargets<Target> handleParsingError(EventHandler eventHandler, String badPattern,
+      TargetParsingException e, boolean keepGoing) throws TargetParsingException {
+    if (eventHandler instanceof ParseFailureListener) {
+      ((ParseFailureListener) eventHandler).parsingError(badPattern, e.getMessage());
+    }
+    if (keepGoing) {
+      eventHandler.handle(Event.error("Skipping '" + badPattern + "': " + e.getMessage()));
+      return ResolvedTargets.<Target>failed();
+    } else {
+      throw e;
+    }
+  }
+
+  @Override
+  public ResolvedTargets<Target> getTargetsInPackage(String originalPattern, String packageName,
+      boolean rulesOnly) throws TargetParsingException, InterruptedException {
+    FilteringPolicy actualPolicy = rulesOnly
+        ? FilteringPolicies.and(FilteringPolicies.RULES_ONLY, policy)
+        : policy;
+    return getTargetsInPackage(originalPattern, packageName, actualPolicy);
+  }
+
+  private ResolvedTargets<Target> getTargetsInPackage(String originalPattern, String packageName,
+      FilteringPolicy policy) throws TargetParsingException, InterruptedException {
+    // Normalise, e.g "foo//bar" -> "foo/bar"; "foo/" -> "foo":
+    packageName = new PathFragment(packageName).toString();
+
+    // it's possible for this check to pass, but for Label.validatePackageNameFull to report an
+    // error because the package name is illegal.  That's a little weird, but we can live with
+    // that for now--see test case: testBadPackageNameButGoodEnoughForALabel. (BTW I tried
+    // duplicating that validation logic in Label but it was extremely tricky.)
+    if (LabelValidator.validatePackageName(packageName) != null) {
+      return handleParsingError(eventHandler, originalPattern,
+                                new TargetParsingException(
+                                  "'" + packageName + "' is not a valid package name"), keepGoing);
+    }
+    Package pkg;
+    try {
+      pkg = packageProvider.getPackage(
+          eventHandler, PackageIdentifier.createInDefaultRepo(packageName));
+    } catch (NoSuchPackageException e) {
+      return handleParsingError(eventHandler, originalPattern, new TargetParsingException(
+          TargetPatternResolverUtil.getParsingErrorMessage(
+              e.getMessage(), originalPattern)), keepGoing);
+    }
+
+    if (pkg.containsErrors()) {
+      // Report an error, but continue (and return partial results) if keepGoing is specified.
+      handleParsingError(eventHandler, originalPattern, new TargetParsingException(
+          TargetPatternResolverUtil.getParsingErrorMessage(
+              "package contains errors", originalPattern)), keepGoing);
+    }
+
+    return TargetPatternResolverUtil.resolvePackageTargets(pkg, policy);
+  }
+
+  @Override
+  public ResolvedTargets<Target> findTargetsBeneathDirectory(String originalPattern,
+      String pathPrefix, boolean rulesOnly) throws TargetParsingException, InterruptedException {
+    FilteringPolicy actualPolicy = rulesOnly
+        ? FilteringPolicies.and(FilteringPolicies.RULES_ONLY, policy)
+        : policy;
+    return findTargetsBeneathDirectory(eventHandler, originalPattern, pathPrefix, actualPolicy,
+        keepGoing, pathPrefix.isEmpty());
+  }
+
+  private ResolvedTargets<Target> findTargetsBeneathDirectory(final EventHandler eventHandler,
+      final String originalPattern, String pathPrefix, final FilteringPolicy policy,
+      final boolean keepGoing, boolean useTopLevelExcludes)
+      throws TargetParsingException, InterruptedException {
+    PathFragment directory = new PathFragment(pathPrefix);
+    if (directory.containsUplevelReferences()) {
+      throw new TargetParsingException("up-level references are not permitted: '"
+          + pathPrefix + "'");
+    }
+    if (!pathPrefix.isEmpty() && (LabelValidator.validatePackageName(pathPrefix) != null)) {
+      return handleParsingError(eventHandler, pathPrefix, new TargetParsingException(
+          "'" + pathPrefix + "' is not a valid package name"), keepGoing);
+    }
+
+    final ResolvedTargets.Builder<Target> builder = ResolvedTargets.concurrentBuilder();
+    try {
+      packageProvider.visitPackageNamesRecursively(eventHandler, directory,
+          useTopLevelExcludes, packageVisitorPool,
+          new PathPackageLocator.AcceptsPathFragment() {
+            @Override
+            public void accept(PathFragment packageName) {
+              String pkgName = packageName.getPathString();
+              try {
+                // Get the targets without transforming. We'll do that later below.
+                builder.merge(getTargetsInPackage(originalPattern, pkgName,
+                    FilteringPolicies.NO_FILTER));
+              } catch (InterruptedException e) {
+                throw new RuntimeParsingException(new TargetParsingException("interrupted"));
+              } catch (TargetParsingException e) {
+                // We'd like to make visitPackageNamesRecursively() generic
+                // over some checked exception type (TargetParsingException in
+                // this case). To do so, we'd have to make AbstractQueueVisitor
+                // generic over the same exception type. That won't work due to
+                // type erasure. As a workaround, we wrap the exception here,
+                // and unwrap it below.
+                throw new RuntimeParsingException(e);
+              }
+            }
+          });
+    } catch (RuntimeParsingException e) {
+      throw e.unwrap();
+    } catch (UnsupportedOperationException e) {
+      throw new TargetParsingException("recursive target patterns are not permitted: '"
+          + originalPattern + "'");
+    }
+
+    if (builder.isEmpty()) {
+      return handleParsingError(eventHandler, originalPattern,
+          new TargetParsingException("no targets found beneath '" + directory + "'"),
+          keepGoing);
+    }
+
+    // Apply the transform after the check so we only return the
+    // error if the tree really contains no targets.
+    ResolvedTargets<Target> intermediateResult = builder.build();
+    ResolvedTargets.Builder<Target> filteredBuilder = ResolvedTargets.builder();
+    if (intermediateResult.hasError()) {
+      filteredBuilder.setError();
+    }
+    for (Target target : intermediateResult.getTargets()) {
+      if (policy.shouldRetain(target, false)) {
+        filteredBuilder.add(target);
+      }
+    }
+    return filteredBuilder.build();
+  }
+
+  @Override
+  public boolean isPackage(String packageName) {
+    return packageProvider.isPackage(packageName);
+  }
+
+  @Override
+  public String getTargetKind(Target target) {
+    return target.getTargetKind();
+  }
+
+  private static final class RuntimeParsingException extends RuntimeException {
+    private TargetParsingException parsingException;
+
+    public RuntimeParsingException(TargetParsingException cause) {
+      super(cause);
+      this.parsingException = Preconditions.checkNotNull(cause);
+    }
+
+    public TargetParsingException unwrap() {
+      return parsingException;
+    }
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/pkgcache/PackageCacheOptions.java b/src/main/java/com/google/devtools/build/lib/pkgcache/PackageCacheOptions.java
new file mode 100644
index 0000000000..f9d3efcb73
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/pkgcache/PackageCacheOptions.java
@@ -0,0 +1,142 @@
+// 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.pkgcache;
+
+import com.google.devtools.build.lib.Constants;
+import com.google.devtools.build.lib.packages.ConstantRuleVisibility;
+import com.google.devtools.build.lib.packages.RuleVisibility;
+import com.google.devtools.build.lib.syntax.CommaSeparatedPackageNameListConverter;
+import com.google.devtools.common.options.Converter;
+import com.google.devtools.common.options.Converters;
+import com.google.devtools.common.options.Option;
+import com.google.devtools.common.options.OptionsBase;
+import com.google.devtools.common.options.OptionsParsingException;
+
+import java.util.List;
+
+/**
+ * Options for configuring the PackageCache.
+ */
+public class PackageCacheOptions extends OptionsBase {
+  /**
+   * A converter for package path that defaults to {@code Constants.DEFAULT_PACKAGE_PATH} if the
+   * option is not given.
+   *
+   * <p>Required because you cannot specify a non-constant value in annotation attributes.
+   */
+  public static class PackagePathConverter implements Converter<List<String>> {
+    @Override
+    public List<String> convert(String input) throws OptionsParsingException {
+      return input.isEmpty()
+          ? Constants.DEFAULT_PACKAGE_PATH
+          : new Converters.ColonSeparatedOptionListConverter().convert(input);
+    }
+
+    @Override
+    public String getTypeDescription() {
+      return "a string";
+    }
+  }
+
+  /**
+   * Converter for the {@code --default_visibility} option.
+   */
+  public static class DefaultVisibilityConverter implements Converter<RuleVisibility> {
+    @Override
+    public RuleVisibility convert(String input) throws OptionsParsingException {
+      if (input.equals("public")) {
+        return ConstantRuleVisibility.PUBLIC;
+      } else if (input.equals("private")) {
+        return ConstantRuleVisibility.PRIVATE;
+      } else {
+        throw new OptionsParsingException("Not a valid default visibility: '" + input
+            + "' (should be 'public' or 'private'");
+      }
+    }
+
+    @Override
+    public String getTypeDescription() {
+      return "default visibility";
+    }
+  }
+
+  @Option(name = "package_path",
+          defaultValue = "",
+          category = "package loading",
+          converter = PackagePathConverter.class,
+          help = "A colon-separated list of where to look for packages. "
+          +  "Elements beginning with '%workspace%' are relative to the enclosing "
+          +  "workspace. If omitted or empty, the default is the output of "
+          +  "'blaze info default-package-path'.")
+  public List<String> packagePath;
+
+  @Option(name = "show_package_location",
+          defaultValue = "false",
+          category = "verbosity",
+          deprecationWarning = "This flag is no longer supported and will go away soon.",
+          help = "If enabled, causes Blaze to print the location on the --package_path "
+          + "from which each package was loaded.")
+  public boolean showPackageLocation;
+
+  @Option(name = "show_loading_progress",
+          defaultValue = "true",
+          category = "verbosity",
+          help = "If enabled, causes Blaze to print \"Loading package:\" messages.")
+  public boolean showLoadingProgress;
+
+  @Option(name = "deleted_packages",
+          defaultValue = "",
+          category = "package loading",
+          converter = CommaSeparatedPackageNameListConverter.class,
+          help = "A comma-separated list of names of packages which the "
+          + "build system will consider non-existent, even if they are "
+          + "visible somewhere on the package path."
+          + "\n"
+          + "Use this option when deleting a subpackage 'x/y' of an "
+          + "existing package 'x'.  For example, after deleting x/y/BUILD "
+          + "in your client, the build system may complain if it "
+          + "encounters a label '//x:y/z' if that is still provided by another "
+          + "package_path entry.  Specifying --deleted_packages x/y avoids this "
+          + "problem.")
+  public List<String> deletedPackages;
+
+  @Option(name = "default_visibility",
+      defaultValue = "private",
+      category = "undocumented",
+      converter = DefaultVisibilityConverter.class,
+      help = "Default visibility for packages that don't set it explicitly ('public' or "
+          + "'private').")
+  public RuleVisibility defaultVisibility;
+
+  @Option(name = "min_pkg_count_for_ct_node_eviction",
+      defaultValue = "3700",
+      // Why is the default value 3700? As of December 2013, a medium target loads about this many
+      // packages, uses ~310MB RAM to only load [1] or ~990MB to load and analyze [2,3]. So we
+      // can likely load and analyze this many packages without worrying about Blaze OOM'ing.
+      //
+      // If the total number of unique packages so far [4] is higher than the value of this flag,
+      // then we evict CT nodes [5] from the Skyframe graph.
+      //
+      // [1] blaze -x build --nobuild --noanalyze //medium:target
+      // [2] blaze -x build --nobuild //medium:target
+      // [3] according to "blaze info used-heap-size"
+      // [4] this means the number of unique packages loaded by builds, including the current one,
+      //     since the last CT node eviction [5]
+      // [5] "CT node eviction" means clearing those nodes from the Skyframe graph that correspond
+      //     to ConfiguredTargets; this is done using SkyframeExecutor.resetConfiguredTargets
+      category = "undocumented",
+      help = "Threshold for number of loaded packages before skyframe-m1 cache eviction kicks in")
+  public int minLoadedPkgCountForCtNodeEviction;
+}
diff --git a/src/main/java/com/google/devtools/build/lib/pkgcache/PackageManager.java b/src/main/java/com/google/devtools/build/lib/pkgcache/PackageManager.java
new file mode 100644
index 0000000000..4d5e687bac
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/pkgcache/PackageManager.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.pkgcache;
+
+import com.google.devtools.build.lib.concurrent.ThreadSafety;
+import com.google.devtools.build.lib.packages.CachingPackageLocator;
+
+import java.io.PrintStream;
+
+/**
+ * A PackageManager keeps state about loaded packages around for quick lookup, and provides
+ * related functionality: Recursive package finding, loaded package checking, etc.
+ */
+public interface PackageManager extends PackageProvider, CachingPackageLocator,
+    LoadedPackageProvider {
+
+  /**
+   * Returns the package cache statistics.
+   */
+  PackageManagerStatistics getStatistics();
+
+  /**
+   * Removes cached data which is not needed anymore after loading is complete, to reduce memory
+   * consumption between builds. Whether or not this method is called does not affect correctness.
+   */
+  void partiallyClear();
+
+  /**
+   * Dump the contents of the package manager in human-readable form.
+   * Used by 'bazel dump' and the BuildTool's unexpected exception handler.
+   */
+  void dump(PrintStream printStream);
+
+  /**
+   * Returns the package locator used by this package manager.
+   *
+   * <p>If you are tempted to call {@code getPackagePath().getPathEntries().get(0)}, be warned that
+   * this is probably not the value you are looking for!  Look at the methods of {@code
+   * BazelRuntime} instead.
+   */
+  @ThreadSafety.ThreadSafe
+  PathPackageLocator getPackagePath();
+
+  /**
+   * Collects statistics of the package manager since the last sync.
+   */
+  interface PackageManagerStatistics {
+
+    /**
+     * Returns the number of packages loaded since the last sync. I.e. the cache
+     * misses.
+     */
+    int getPackagesLoaded();
+
+    /**
+     * Returns the number of packages looked up since the last sync.
+     */
+    int getPackagesLookedUp();
+
+    /**
+     * Returns the number of all the packages currently loaded.
+     *
+     * <p>
+     * Note that this method is not affected by sync(), and the packages it
+     * returns are not guaranteed to be up-to-date.
+     */
+    int getCacheSize();
+  }
+
+  /**
+   * Retrieve a target pattern parser that works with this package manager.
+   */
+  TargetPatternEvaluator getTargetPatternEvaluator();
+
+  /**
+   * Construct a new {@link TransitivePackageLoader}.
+   */
+  TransitivePackageLoader newTransitiveLoader();
+}
diff --git a/src/main/java/com/google/devtools/build/lib/pkgcache/PackageProvider.java b/src/main/java/com/google/devtools/build/lib/pkgcache/PackageProvider.java
new file mode 100644
index 0000000000..0573768e6a
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/pkgcache/PackageProvider.java
@@ -0,0 +1,60 @@
+// 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.pkgcache;
+
+import com.google.devtools.build.lib.events.EventHandler;
+import com.google.devtools.build.lib.packages.NoSuchPackageException;
+import com.google.devtools.build.lib.packages.Package;
+import com.google.devtools.build.lib.packages.PackageIdentifier;
+
+/**
+ * API for retrieving packages. Implementations generally load packages to fulfill requests.
+ *
+ * <p><b>Concurrency</b>: Implementations should be thread safe for {@link #getPackage}.
+ */
+public interface PackageProvider extends TargetProvider {
+
+  /**
+   * Returns the {@link Package} named "packageName". If there is no such package (e.g.
+   * {@code isPackage(packageName)} returns false), throws a {@link NoSuchPackageException}.
+   *
+   * <p>The returned package may contain lexical/grammatical errors, in which
+   * case <code>pkg.containsErrors() == true</code>.  Such packages may be
+   * missing some rules.  Any rules that are present may soundly be used for
+   * builds, though.
+   *
+   * @param eventHandler the eventHandler on which to report warning and errors; if the package
+   *        has been loaded by another thread, this eventHandler won't see any warnings or errors
+   * @param packageName a legal package name.
+   * @throws NoSuchPackageException if the package could not be found.
+   * @throws InterruptedException if the package loading was interrupted.
+   */
+  Package getPackage(EventHandler eventHandler, PackageIdentifier packageName)
+      throws NoSuchPackageException, InterruptedException;
+
+  /**
+   * Returns whether a package with the given name exists. That is, returns whether all the
+   * following hold
+   * <ol>
+   *   <li>{@code packageName} is a valid package name</li>
+   *   <li>there is a BUILD file for the package</li>
+   *   <li>the package is not considered deleted via --deleted_packages</li>
+   * </ol>
+   *
+   * <p> If these don't hold, then attempting to read the package with {@link #getPackage} may fail
+   * or may return a package containing errors.
+   */
+  boolean isPackage(String packageName);
+}
diff --git a/src/main/java/com/google/devtools/build/lib/pkgcache/ParseFailureListener.java b/src/main/java/com/google/devtools/build/lib/pkgcache/ParseFailureListener.java
new file mode 100644
index 0000000000..e3cf5ca5ee
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/pkgcache/ParseFailureListener.java
@@ -0,0 +1,28 @@
+// 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.pkgcache;
+
+import com.google.common.eventbus.EventBus;
+import com.google.devtools.build.lib.events.EventHandler;
+
+/**
+ * Represents a listener which reports parse errors to the underlying
+ * {@link EventHandler} and {@link EventBus} (if non-null).
+ */
+public interface ParseFailureListener {
+
+  /** Reports a parsing failure. */
+  void parsingError(String badPattern, String message);
+}
diff --git a/src/main/java/com/google/devtools/build/lib/pkgcache/ParsingFailedEvent.java b/src/main/java/com/google/devtools/build/lib/pkgcache/ParsingFailedEvent.java
new file mode 100644
index 0000000000..7eb916988a
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/pkgcache/ParsingFailedEvent.java
@@ -0,0 +1,42 @@
+// 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.pkgcache;
+
+/**
+ * This event is fired when a target or target pattern fails to parse.
+ * In some cases (not all) this happens before targets are created,
+ * and thus in these cases there are no status lines.
+ * Therefore, the parse failure is reported separately.
+ */
+public class ParsingFailedEvent {
+  private final String targetPattern;
+  private final String message;
+
+  /**
+   * Creates a new parsing failed event with the given pattern and message.
+   */
+  public ParsingFailedEvent(String targetPattern, String message) {
+    this.targetPattern = targetPattern;
+    this.message = message;
+  }
+
+  public String getPattern() {
+    return targetPattern;
+  }
+
+  public String getMessage() {
+    return message;
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/pkgcache/PathPackageLocator.java b/src/main/java/com/google/devtools/build/lib/pkgcache/PathPackageLocator.java
new file mode 100644
index 0000000000..a2af5f2639
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/pkgcache/PathPackageLocator.java
@@ -0,0 +1,213 @@
+// 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.pkgcache;
+
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableSet;
+import com.google.devtools.build.lib.events.Event;
+import com.google.devtools.build.lib.events.EventHandler;
+import com.google.devtools.build.lib.packages.BuildFileNotFoundException;
+import com.google.devtools.build.lib.packages.NoSuchPackageException;
+import com.google.devtools.build.lib.vfs.FileStatus;
+import com.google.devtools.build.lib.vfs.Path;
+import com.google.devtools.build.lib.vfs.PathFragment;
+import com.google.devtools.build.lib.vfs.Symlinks;
+import com.google.devtools.build.lib.vfs.UnixGlob;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.List;
+import java.util.Set;
+import java.util.concurrent.atomic.AtomicReference;
+import java.util.logging.Logger;
+
+/**
+ * A mapping from the name of a package to the location of its BUILD file.
+ * The implementation composes an ordered sequence of directories according to
+ * the package-path rules.
+ *
+ * <p>All methods are thread-safe, and (assuming no change to the underlying
+ * filesystem) idempotent.
+ */
+public class PathPackageLocator {
+
+  public static final Set<String> DEFAULT_TOP_LEVEL_EXCLUDES =
+      ImmutableSet.of("experimental", "obsolete");
+
+  /**
+   * An interface which accepts {@link PathFragment}s.
+   */
+  public interface AcceptsPathFragment {
+
+    /**
+     * Accept a {@link PathFragment}.
+     *
+     * @param fragment The path fragment.
+     */
+    void accept(PathFragment fragment);
+  }
+
+  private static final Logger LOG = Logger.getLogger(PathPackageLocator.class.getName());
+
+  private final ImmutableList<Path> pathEntries;
+
+  /**
+   * Constructs a PathPackageLocator based on the specified list of package root directories.
+   */
+  public PathPackageLocator(List<Path> pathEntries) {
+    this.pathEntries = ImmutableList.copyOf(pathEntries);
+  }
+
+  /**
+   * Constructs a PathPackageLocator based on the specified array of package root directories.
+   */
+  public PathPackageLocator(Path... pathEntries) {
+    this(Arrays.asList(pathEntries));
+  }
+
+  /**
+   * Returns the path to the build file for this package.
+   *
+   * <p>The package's root directory may be computed by calling getParentFile()
+   * on the result of this function.
+   *
+   * <p>Instances of this interface do not attempt to do any caching, nor
+   * implement checks for package-boundary crossing logic; the PackageCache
+   * does that.
+   *
+   * <p>If the same package exists beneath multiple package path entries, the
+   * first path that matches always wins.
+   */
+  public Path getPackageBuildFile(String packageName) throws NoSuchPackageException {
+    Path buildFile  = getPackageBuildFileNullable(packageName, UnixGlob.DEFAULT_SYSCALLS_REF);
+    if (buildFile == null) {
+      throw new BuildFileNotFoundException(packageName, "BUILD file not found on package path");
+    }
+    return buildFile;
+  }
+
+  /**
+   * Like #getPackageBuildFile(), but returns null instead of throwing.
+   *
+   * @param packageName the name of the package.
+   * @param cache a filesystem-level cache of stat() calls.
+   */
+  public Path getPackageBuildFileNullable(String packageName,
+      AtomicReference<? extends UnixGlob.FilesystemCalls> cache)  {
+    return getFilePath(new PathFragment(packageName).getRelative("BUILD"), cache);
+  }
+
+
+  /**
+   * Returns an immutable ordered list of the directories on the package path.
+   */
+  public ImmutableList<Path> getPathEntries() {
+    return pathEntries;
+  }
+
+  @Override
+  public String toString() {
+    return "PathPackageLocator" + pathEntries;
+  }
+
+  /**
+   * A factory of PathPackageLocators from a list of path elements.  Elements
+   * may contain "%workspace%", indicating the workspace.
+   *
+   * @param pathElements Each element must be an absolute path, relative path,
+   *                     or some string "%workspace%" + relative, where relative is itself a
+   *                     relative path.  The special symbol "%workspace%" means to interpret
+   *                     the path relative to the nearest enclosing workspace.  Relative
+   *                     paths are interpreted relative to the client's working directory,
+   *                     which may be below the workspace.
+   * @param eventHandler The eventHandler.
+   * @param workspace The nearest enclosing package root directory.
+   * @param clientWorkingDirectory The client's working directory.
+   * @return a list of {@link Path}s.
+   */
+  public static PathPackageLocator create(List<String> pathElements,
+                                          EventHandler eventHandler,
+                                          Path workspace,
+                                          Path clientWorkingDirectory) {
+    List<Path> resolvedPaths = new ArrayList<>();
+    final String workspaceWildcard = "%workspace%";
+
+    for (String pathElement : pathElements) {
+      // Replace "%workspace%" with the path of the enclosing workspace directory.
+      pathElement = pathElement.replace(workspaceWildcard, workspace.getPathString());
+
+      PathFragment pathElementFragment = new PathFragment(pathElement);
+
+      // If the path string started with "%workspace%" or "/", it is already absolute,
+      // so the following line is a no-op.
+      Path rootPath = clientWorkingDirectory.getRelative(pathElementFragment);
+
+      if (!pathElementFragment.isAbsolute() && !clientWorkingDirectory.equals(workspace)) {
+        eventHandler.handle(
+            Event.warn("The package path element '" + pathElementFragment + "' will be "
+                + "taken relative to your working directory. You may have intended "
+                + "to have the path taken relative to your workspace directory. "
+                + "If so, please use the '" + workspaceWildcard + "' wildcard."));
+      }
+
+      if (rootPath.exists()) {
+        resolvedPaths.add(rootPath);
+      } else {
+        LOG.fine("package path element " + rootPath + " does not exist, ignoring");
+      }
+    }
+    return new PathPackageLocator(resolvedPaths);
+  }
+
+  /**
+   * Returns the path to the WORKSPACE file for this build.
+   *
+   * <p>If there are WORKSPACE files beneath multiple package path entries, the first one always
+   * wins.
+   */
+  public Path getWorkspaceFile() {
+    AtomicReference<? extends UnixGlob.FilesystemCalls> cache = UnixGlob.DEFAULT_SYSCALLS_REF;
+    // TODO(bazel-team): correctness in the presence of changes to the location of the WORKSPACE
+    // file.
+    return getFilePath(new PathFragment("WORKSPACE"), cache);
+  }
+
+  private Path getFilePath(PathFragment suffix,
+      AtomicReference<? extends UnixGlob.FilesystemCalls> cache) {
+    for (Path pathEntry : pathEntries) {
+      Path buildFile = pathEntry.getRelative(suffix);
+      FileStatus stat = cache.get().statNullable(buildFile, Symlinks.FOLLOW);
+      if (stat != null && stat.isFile()) {
+        return buildFile;
+      }
+    }
+    return null;
+  }
+
+  @Override
+  public int hashCode() {
+    return pathEntries.hashCode();
+  }
+
+  @Override
+  public boolean equals(Object other) {
+    if (this == other) {
+      return true;
+    }
+    if (!(other instanceof PathPackageLocator)) {
+      return false;
+    }
+    return this.getPathEntries().equals(((PathPackageLocator) other).getPathEntries());
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/pkgcache/RecursivePackageProvider.java b/src/main/java/com/google/devtools/build/lib/pkgcache/RecursivePackageProvider.java
new file mode 100644
index 0000000000..8d7bd1dac2
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/pkgcache/RecursivePackageProvider.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.pkgcache;
+
+import com.google.devtools.build.lib.events.EventHandler;
+import com.google.devtools.build.lib.vfs.PathFragment;
+
+import java.util.concurrent.ThreadPoolExecutor;
+
+import javax.annotation.Nullable;
+
+/**
+ * Support for resolving {@code package/...} target patterns.
+ */
+public interface RecursivePackageProvider extends PackageProvider {
+
+  /**
+   * <p>Visits the names of all packages beneath the given directory recursively and concurrently.
+   *
+   * <p>Note: This operation needs to stat directories recursively. It could be very expensive when
+   * there is a big tree under the given directory.
+   *
+   * <p>Over a single iteration, package names are unique.
+   *
+   * <p>This method uses the given thread pool to call the observer method, possibly concurrently
+   * (depending on the thread pool). When this method terminates, however, all such threads will
+   * have completed.
+   *
+   * <p>To abort the traversal, call {@link Thread#interrupt()} on the calling thread.
+   *
+   * <p>This method guarantees that all BUILD files it returns correspond to valid package names
+   * that are not marked as deleted within the current build.
+   *
+   * @param eventHandler an eventHandler which should be used to log any errors that occur while
+   *    scanning directories for BUILD files
+   * @param directory a relative, canonical path specifying the directory to search
+   * @param useTopLevelExcludes whether to skip a pre-set list of top level directories
+   * @param visitorPool the thread pool to use to visit packages in parallel
+   * @param observer is called for each path fragment found; thread-safe if the thread pool supports
+   *    multiple parallel threads
+   * @throws InterruptedException if the calling thread was interrupted.
+   */
+  void visitPackageNamesRecursively(EventHandler eventHandler, PathFragment directory,
+      boolean useTopLevelExcludes, @Nullable ThreadPoolExecutor visitorPool,
+      PathPackageLocator.AcceptsPathFragment observer) throws InterruptedException;
+}
diff --git a/src/main/java/com/google/devtools/build/lib/pkgcache/SrcTargetUtil.java b/src/main/java/com/google/devtools/build/lib/pkgcache/SrcTargetUtil.java
new file mode 100644
index 0000000000..85d967e033
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/pkgcache/SrcTargetUtil.java
@@ -0,0 +1,148 @@
+// 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.pkgcache;
+
+import com.google.common.base.Preconditions;
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.Lists;
+import com.google.common.collect.Sets;
+import com.google.devtools.build.lib.concurrent.ThreadSafety;
+import com.google.devtools.build.lib.events.EventHandler;
+import com.google.devtools.build.lib.packages.AttributeMap;
+import com.google.devtools.build.lib.packages.FileTarget;
+import com.google.devtools.build.lib.packages.NoSuchPackageException;
+import com.google.devtools.build.lib.packages.NoSuchTargetException;
+import com.google.devtools.build.lib.packages.RawAttributeMapper;
+import com.google.devtools.build.lib.packages.Rule;
+import com.google.devtools.build.lib.packages.Target;
+import com.google.devtools.build.lib.packages.Type;
+import com.google.devtools.build.lib.syntax.Label;
+
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Set;
+
+/**
+ * A helper class for getting source and header files from a given {@link Rule}.
+ */
+public final class SrcTargetUtil {
+  private SrcTargetUtil() {
+  }
+
+  /**
+   * Given a Rule, returns an immutable list of FileTarget for its sources, in the order they appear
+   * in its "srcs", "src" or "srcjar" attribute, and any filegroups or other rules it references.
+   * An empty list is returned if no "srcs" or "src" attribute exists for this rule. The list may
+   * contain OutputFiles if the sources were generated by another rule.
+   *
+   * <p>This method should be considered only a heuristic, and should not be used during the
+   * analysis phase.
+   *
+   * <p>(We could remove the throws clauses if we restrict the results to srcs within the same
+   * package.)
+   *
+   * @throws NoSuchTargetException or NoSuchPackageException when a source label cannot be resolved
+   *         to a Target
+   */
+  @ThreadSafety.ThreadSafe
+  public static List<FileTarget> getSrcTargets(EventHandler eventHandler, Rule rule,
+                                               TargetProvider provider)
+      throws NoSuchTargetException, NoSuchPackageException, InterruptedException  {
+    return getTargets(eventHandler, rule, SOURCE_ATTRIBUTES, Sets.newHashSet(rule), provider);
+  }
+
+  // Attributes referring to "sources".
+  private static final ImmutableSet<String> SOURCE_ATTRIBUTES =
+      ImmutableSet.of("srcs", "src", "srcjar");
+
+  // Attributes referring to "headers".
+  private static final ImmutableSet<String> HEADER_ATTRIBUTES =
+      ImmutableSet.of("hdrs");
+  
+  // The attribute to search in filegroups.
+  private static final ImmutableSet<String> FILEGROUP_ATTRIBUTES =
+      ImmutableSet.of("srcs");
+
+  /**
+   * Same as {@link #getSrcTargets}, but for both source and headers (i.e. also traversing
+   * the "hdrs" attribute).
+   */
+  @ThreadSafety.ThreadSafe
+  public static List<FileTarget> getSrcAndHdrTargets(EventHandler eventHandler, Rule rule,
+                                                     TargetProvider provider)
+      throws NoSuchTargetException, NoSuchPackageException, InterruptedException  {
+    ImmutableSet<String> srcAndHdrAttributes = ImmutableSet.<String>builder()
+        .addAll(SOURCE_ATTRIBUTES)
+        .addAll(HEADER_ATTRIBUTES)
+        .build();
+    return getTargets(eventHandler, rule, srcAndHdrAttributes, Sets.newHashSet(rule), provider);
+  }
+
+  @ThreadSafety.ThreadSafe
+  public static List<FileTarget> getHdrTargets(EventHandler eventHandler, Rule rule,
+                                                     TargetProvider provider)
+      throws NoSuchTargetException, NoSuchPackageException, InterruptedException  {
+    ImmutableSet<String> srcAndHdrAttributes = ImmutableSet.<String>builder()
+        .addAll(HEADER_ATTRIBUTES)
+        .build();
+    return getTargets(eventHandler, rule, srcAndHdrAttributes, Sets.newHashSet(rule), provider);
+  }
+  
+  /**
+   * @see #getSrcTargets(EventHandler, Rule, TargetProvider)
+   */
+  private static List<FileTarget> getTargets(EventHandler eventHandler,
+      Rule rule,
+      ImmutableSet<String> attributes,
+      Set<Rule> visitedRules,
+      TargetProvider targetProvider)
+      throws NoSuchTargetException, NoSuchPackageException, InterruptedException {
+    Preconditions.checkState(!rule.hasConfigurableAttributes()); // Not currently supported.
+    List<Label> srcLabels = Lists.newArrayList();
+    AttributeMap attributeMap = RawAttributeMapper.of(rule);
+    for (String attrName : attributes) {
+      if (rule.isAttrDefined(attrName, Type.LABEL_LIST)) {
+        srcLabels.addAll(attributeMap.get(attrName, Type.LABEL_LIST));
+      } else if (rule.isAttrDefined(attrName, Type.LABEL)) {
+        Label srcLabel = attributeMap.get(attrName, Type.LABEL);
+        if (srcLabel != null) {
+          srcLabels.add(srcLabel);
+        }
+      }
+    }
+    if (srcLabels.isEmpty()) {
+      return ImmutableList.of();
+    }
+    List<FileTarget> srcTargets = new ArrayList<>();
+    for (Label label : srcLabels) {
+      Target target = targetProvider.getTarget(eventHandler, label);
+      if (target instanceof FileTarget) {
+        srcTargets.add((FileTarget) target);
+      } else {
+        Rule srcRule = target.getAssociatedRule();
+        if (srcRule != null && !visitedRules.contains(srcRule)) {
+          visitedRules.add(srcRule);
+          if ("filegroup".equals(srcRule.getRuleClass())) {
+            srcTargets.addAll(getTargets(eventHandler, srcRule, FILEGROUP_ATTRIBUTES, visitedRules,
+                targetProvider));
+          } else {
+            srcTargets.addAll(srcRule.getOutputFiles());
+          }
+        }
+      }
+    }
+    return ImmutableList.copyOf(srcTargets);
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/pkgcache/TargetEdgeObserver.java b/src/main/java/com/google/devtools/build/lib/pkgcache/TargetEdgeObserver.java
new file mode 100644
index 0000000000..acc858ffa9
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/pkgcache/TargetEdgeObserver.java
@@ -0,0 +1,59 @@
+// 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.pkgcache;
+
+import com.google.devtools.build.lib.packages.Attribute;
+import com.google.devtools.build.lib.packages.NoSuchThingException;
+import com.google.devtools.build.lib.packages.Target;
+import com.google.devtools.build.lib.syntax.Label;
+
+import javax.annotation.Nullable;
+
+/**
+ * An observer of the visitation over a target graph.
+ */
+public interface TargetEdgeObserver {
+
+  /**
+   * Called when an edge is discovered.
+   * May be called more than once for the same
+   * (from, to) pair.
+   *
+   * @param from the originating node.
+   * @param attribute The attribute which defines the edge.
+   *     Non-null iff (from instanceof Rule).
+   * @param to the target node.
+   */
+  void edge(Target from, Attribute attribute, Target to);
+
+  /**
+   * Called when a Target has a reference to a non-existent target.
+   *
+   * @param target the target.  May be null (e.g. in the case of an implicit
+   *   dependency on a subincluded file).
+   * @param to a label reference in the rule, which does not correspond
+   *     to a valid target.
+   * @param e the corresponding exception thrown
+   */
+  void missingEdge(@Nullable Target target, Label to, NoSuchThingException e);
+
+  /**
+   * Called when a node is discovered. May be called
+   * more than once for the same node.
+   *
+   * @param node the target.
+   */
+  void node(Target node);
+}
diff --git a/src/main/java/com/google/devtools/build/lib/pkgcache/TargetParsingCompleteEvent.java b/src/main/java/com/google/devtools/build/lib/pkgcache/TargetParsingCompleteEvent.java
new file mode 100644
index 0000000000..48d8861aad
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/pkgcache/TargetParsingCompleteEvent.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.pkgcache;
+
+import com.google.common.annotations.VisibleForTesting;
+import com.google.common.base.Function;
+import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.Iterables;
+import com.google.devtools.build.lib.packages.Target;
+import com.google.devtools.build.lib.syntax.Label;
+
+import java.util.Collection;
+
+/**
+ * This event is fired just after target pattern evaluation is completed.
+ */
+public class TargetParsingCompleteEvent {
+
+  private final ImmutableSet<Target> targets;
+  private final ImmutableSet<Target> filteredTargets;
+  private final ImmutableSet<Target> testFilteredTargets;
+  private final long timeInMs;
+
+  /**
+   * Construct the event.
+   * @param targets The targets that were parsed from the
+   *     command-line pattern.
+   */
+  public TargetParsingCompleteEvent(Collection<Target> targets,
+      Collection<Target> filteredTargets, Collection<Target> testFilteredTargets,
+      long timeInMs) {
+    this.timeInMs = timeInMs;
+    this.targets = ImmutableSet.copyOf(targets);
+    this.filteredTargets = ImmutableSet.copyOf(filteredTargets);
+    this.testFilteredTargets = ImmutableSet.copyOf(testFilteredTargets);
+  }
+
+  @VisibleForTesting
+  public TargetParsingCompleteEvent(Collection<Target> targets) {
+    this(targets, ImmutableSet.<Target>of(), ImmutableSet.<Target>of(), 0);
+  }
+
+  /**
+   * @return the parsed targets, which will subsequently be loaded
+   */
+  public ImmutableSet<Target> getTargets() {
+    return targets;
+  }
+
+  public Iterable<Label> getLabels() {
+    return Iterables.transform(targets, new Function<Target, Label>() {
+      @Override
+      public Label apply(Target input) {
+        return input.getLabel();
+      }
+    });
+  }
+
+  /**
+   * @return the filtered targets (i.e., using -//foo:bar on the command-line)
+   */
+  public ImmutableSet<Target> getFilteredTargets() {
+    return filteredTargets;
+  }
+
+  /**
+   * @return the test-filtered targets, if --build_test_only is in effect
+   */
+  public ImmutableSet<Target> getTestFilteredTargets() {
+    return testFilteredTargets;
+  }
+
+  public long getTimeInMs() {
+    return timeInMs;
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/pkgcache/TargetPatternEvaluator.java b/src/main/java/com/google/devtools/build/lib/pkgcache/TargetPatternEvaluator.java
new file mode 100644
index 0000000000..94e956b435
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/pkgcache/TargetPatternEvaluator.java
@@ -0,0 +1,97 @@
+// 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.pkgcache;
+
+import com.google.common.annotations.VisibleForTesting;
+import com.google.devtools.build.lib.cmdline.ResolvedTargets;
+import com.google.devtools.build.lib.cmdline.TargetParsingException;
+import com.google.devtools.build.lib.concurrent.ThreadSafety;
+import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadHostile;
+import com.google.devtools.build.lib.events.EventHandler;
+import com.google.devtools.build.lib.packages.Target;
+import com.google.devtools.build.lib.vfs.PathFragment;
+
+import java.util.Collection;
+import java.util.List;
+import java.util.Map;
+
+/**
+ * A parser for target patterns.  Target patterns are a generalisation of
+ * labels to include wildcards for finding all packages recursively
+ * beneath some root, and for finding all targets within a package.
+ *
+ * <p>A list of target patterns implies a union of all the labels of each
+ * pattern.  Each item in a list of target patterns may include a prefix
+ * negation operator, indicating that the sets of targets for this pattern
+ * should be subtracted from the set of targets for the preceding patterns (note
+ * this means that order matters).  Thus, the following list of target patterns:
+ * <pre>foo/... -foo/bar:all</pre>
+ * means "all targets beneath <tt>foo</tt> except for those targets in
+ * package <tt>foo/bar</tt>.
+ */
+@ThreadSafety.ConditionallyThreadSafe // as long as you don't call updateOffset.
+public interface TargetPatternEvaluator {
+  /**
+   * Attempts to parse an ordered list of target patterns, computing the union
+   * of the set of targets represented by each pattern, unless it is preceded by
+   * "-", in which case the set difference is computed.  Implements the
+   * specification described in the class-level comment.
+   */
+  ResolvedTargets<Target> parseTargetPatternList(EventHandler eventHandler,
+      List<String> targetPatterns, FilteringPolicy policy, boolean keepGoing)
+      throws TargetParsingException, InterruptedException;
+
+  /**
+  * Attempts to parse a single target pattern while consulting the package
+   * cache to check for the existence of packages and directories and the build
+   * targets in them.  Implements the specification described in the
+   * class-level comment.  Returns a {@link ResolvedTargets} object.
+   *
+   * <p>If an error is encountered, a {@link TargetParsingException} is thrown,
+   * unless {@code keepGoing} is set to true. In that case, the returned object
+   * will have its error bit set.
+   */
+  ResolvedTargets<Target> parseTargetPattern(EventHandler eventHandler, String pattern,
+      boolean keepGoing) throws TargetParsingException, InterruptedException;
+
+  /**
+   * Attempts to parse and load the given collection of patterns; the returned map contains the
+   * results for each pattern successfully parsed.
+   *
+   * <p>If an error is encountered, a {@link TargetParsingException} is thrown, unless {@code
+   * keepGoing} is set to true. In that case, the patterns that failed to load have the error flag
+   * set.
+   */
+  Map<String, ResolvedTargets<Target>> preloadTargetPatterns(EventHandler eventHandler,
+      Collection<String> patterns, boolean keepGoing)
+          throws TargetParsingException, InterruptedException;
+
+
+  /**
+   * Update the parser's offset, given the workspace and working directory.
+   *
+   * @param relativeWorkingDirectory the working directory relative to the workspace
+   */
+  @ThreadHostile
+  void updateOffset(PathFragment relativeWorkingDirectory);
+
+  /**
+   * @return the offset of this parser from the root of the workspace.
+   *         Non-absolute package-names will be resolved relative
+   *         to this offset.
+   */
+  @VisibleForTesting
+  String getOffset();
+}
diff --git a/src/main/java/com/google/devtools/build/lib/pkgcache/TargetPatternResolverUtil.java b/src/main/java/com/google/devtools/build/lib/pkgcache/TargetPatternResolverUtil.java
new file mode 100644
index 0000000000..6bbf55c7fe
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/pkgcache/TargetPatternResolverUtil.java
@@ -0,0 +1,69 @@
+// 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.pkgcache;
+
+import com.google.devtools.build.lib.cmdline.ResolvedTargets;
+import com.google.devtools.build.lib.cmdline.TargetParsingException;
+import com.google.devtools.build.lib.packages.Package;
+import com.google.devtools.build.lib.packages.Target;
+import com.google.devtools.build.lib.syntax.Label;
+import com.google.devtools.build.lib.util.StringUtilities;
+
+/**
+ * Common utility methods for target pattern resolution.
+ */
+public final class TargetPatternResolverUtil {
+  private TargetPatternResolverUtil() {
+    // Utility class.
+  }
+
+  // Parse 'label' as a Label, mapping Label.SyntaxException into
+  // TargetParsingException.
+  public static Label label(String label) throws TargetParsingException {
+    try {
+      return Label.parseAbsolute(label);
+    } catch (Label.SyntaxException e) {
+      throw invalidTarget(label, e.getMessage());
+    }
+  }
+
+  /**
+   * Returns a new exception indicating that a command-line target is invalid.
+   */
+  private static TargetParsingException invalidTarget(String packageName,
+                                                      String additionalMessage) {
+    return new TargetParsingException("invalid target format: '" +
+        StringUtilities.sanitizeControlChars(packageName) + "'; " +
+        StringUtilities.sanitizeControlChars(additionalMessage));
+  }
+
+  public static String getParsingErrorMessage(String message, String originalPattern) {
+    if (originalPattern == null) {
+      return message;
+    } else {
+      return String.format("while parsing '%s': %s", originalPattern, message);
+    }
+  }
+
+  public static ResolvedTargets<Target> resolvePackageTargets(Package pkg,
+                                                              FilteringPolicy policy) {
+    ResolvedTargets.Builder<Target> builder = ResolvedTargets.builder();
+    for (Target target : pkg.getTargets()) {
+      if (policy.shouldRetain(target, false)) {
+        builder.add(target);
+      }
+    }
+    return builder.build();
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/pkgcache/TargetProvider.java b/src/main/java/com/google/devtools/build/lib/pkgcache/TargetProvider.java
new file mode 100644
index 0000000000..72dc83422b
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/pkgcache/TargetProvider.java
@@ -0,0 +1,40 @@
+// 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.pkgcache;
+
+import com.google.devtools.build.lib.events.EventHandler;
+import com.google.devtools.build.lib.packages.NoSuchPackageException;
+import com.google.devtools.build.lib.packages.NoSuchTargetException;
+import com.google.devtools.build.lib.packages.Target;
+import com.google.devtools.build.lib.syntax.Label;
+
+/**
+ * API for retrieving targets.
+ *
+ * <p><b>Concurrency</b>: Implementations should be thread safe.
+ */
+public interface TargetProvider {
+  /**
+   * Returns the Target identified by "label", loading, parsing and evaluating the package if it is
+   * not already loaded.
+   *
+   * @throws NoSuchPackageException if the package could not be found
+   * @throws NoSuchTargetException if the package was loaded successfully, but
+   *         the specified {@link Target} was not found in it
+   * @throws InterruptedException if the package loading was interrupted
+   */
+  Target getTarget(EventHandler eventHandler, Label label) throws NoSuchPackageException,
+      NoSuchTargetException, InterruptedException;
+}
diff --git a/src/main/java/com/google/devtools/build/lib/pkgcache/TransitivePackageLoader.java b/src/main/java/com/google/devtools/build/lib/pkgcache/TransitivePackageLoader.java
new file mode 100644
index 0000000000..14990b22bc
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/pkgcache/TransitivePackageLoader.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.pkgcache;
+
+import com.google.common.collect.Multimap;
+import com.google.devtools.build.lib.events.EventHandler;
+import com.google.devtools.build.lib.packages.Package;
+import com.google.devtools.build.lib.packages.PackageIdentifier;
+import com.google.devtools.build.lib.packages.Target;
+import com.google.devtools.build.lib.syntax.Label;
+
+import java.util.Collection;
+import java.util.Set;
+
+/**
+ * Visits a set of Targets and Labels transitively.
+ */
+public interface TransitivePackageLoader {
+
+  /**
+   * Visit the specified labels and follow the transitive closure of their
+   * outbound dependencies. If the targets have previously been visited,
+   * may do an up-to-date check which will not trigger any of the observers.
+   *
+   * @param eventHandler the error and warnings eventHandler; must be thread-safe
+   * @param targetsToVisit the targets to visit
+   * @param labelsToVisit the labels to visit in addition to the targets
+   * @param keepGoing if false, stop visitation upon first error.
+   * @param parallelThreads number of threads to use in the visitation.
+   * @param maxDepth the maximum depth to traverse to.
+   */
+  boolean sync(EventHandler eventHandler,
+               Set<Target> targetsToVisit,
+               Set<Label> labelsToVisit,
+               boolean keepGoing,
+               int parallelThreads,
+               int maxDepth) throws InterruptedException;
+
+  /**
+   * Returns a read-only view of the set of targets visited since this visitor
+   * was constructed.
+   *
+   * <p>Not thread-safe; do not call during visitation.
+   */
+  // TODO(bazel-team): This is only used in legacy non-Skyframe code.
+  Set<Label> getVisitedTargets();
+
+  /**
+   * Returns a read-only view of the set of packages visited since this visitor
+   * was constructed.
+   *
+   * <p>Not thread-safe; do not call during visitation.
+   */
+  Set<PackageIdentifier> getVisitedPackageNames();
+
+  /**
+   * Returns a read-only view of the set of the actual packages visited without error since this
+   * visitor was constructed.
+   *
+   * <p>Use {@link #getVisitedPackageNames()} instead when possible.
+   *
+   * <p>Not thread-safe; do not call during visitation.
+   */
+  Set<Package> getErrorFreeVisitedPackages();
+
+  /**
+   * Return a mapping between the specified top-level targets and root causes. Note that targets in
+   * the input that are transitively error free will not be in the output map. "Top-level" targets
+   * are the targetsToVisit and labelsToVisit specified in the last sync.
+   *
+   * <p>May only be called once a keep_going visitation is complete, and prior to
+   * trimErrorTracking().
+   *
+   * @param targetsToLoad the set of targets to be checked. Implementations may choose to only
+   *        return root causes for targets in this set that were requested top-level targets.
+   * @return a mapping of targets to root causes
+   */
+  Multimap<Label, Label> getRootCauses(Collection<Label> targetsToLoad);
+}