Batch all DependencyResolver#getTarget calls. This leads to some duplicate iteration, but that should be cheap, while requesting packages sequentially can hurt...

PiperOrigin-RevId: 208126130

20 files changed, 477 insertions, 342 deletions

diff --git a/src/main/java/com/google/devtools/build/lib/analysis/AspectAwareAttributeMapper.java b/src/main/java/com/google/devtools/build/lib/analysis/AspectAwareAttributeMapper.java
index b45e350fc4..4419d0b162 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/AspectAwareAttributeMapper.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/AspectAwareAttributeMapper.java
@@ -22,6 +22,7 @@ import com.google.devtools.build.lib.packages.Attribute;
 import com.google.devtools.build.lib.packages.AttributeMap;
 import com.google.devtools.build.lib.packages.RuleClass;
 import com.google.devtools.build.lib.syntax.Type;
+import java.util.Collection;
 
 /**
  * An {@link AttributeMap} that supports attribute type queries on both a rule and its aspects and
@@ -134,7 +135,7 @@ class AspectAwareAttributeMapper implements AttributeMap {
   }
 
   @Override
-  public void visitLabels(AcceptsLabelAttribute observer) throws InterruptedException {
+  public Collection<DepEdge> visitLabels() throws InterruptedException {
     throw new UnsupportedOperationException("rule + aspects label visition is not supported");
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/DependencyResolver.java b/src/main/java/com/google/devtools/build/lib/analysis/DependencyResolver.java
index 0ae17e2093..6062d064ee 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/DependencyResolver.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/DependencyResolver.java
@@ -18,6 +18,7 @@ import com.google.common.base.Preconditions;
 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.devtools.build.lib.analysis.AspectCollection.AspectCycleOnPathException;
 import com.google.devtools.build.lib.analysis.config.BuildConfiguration;
 import com.google.devtools.build.lib.analysis.config.BuildOptions;
@@ -56,11 +57,12 @@ import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec.
 import com.google.devtools.build.lib.syntax.EvalException;
 import com.google.devtools.build.lib.syntax.EvalUtils;
 import com.google.devtools.build.lib.util.OrderedSetMultimap;
-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.stream.Stream;
 import javax.annotation.Nullable;
 
 /**
@@ -214,8 +216,8 @@ public abstract class DependencyResolver {
       @Nullable RuleTransitionFactory trimmingTransitionFactory)
       throws EvalException, InvalidConfigurationException, InconsistentAspectOrderException,
           InterruptedException {
-    Preconditions.checkArgument(node.getTarget() instanceof Rule);
-    BuildConfiguration ruleConfig = Preconditions.checkNotNull(node.getConfiguration());
+    Preconditions.checkArgument(node.getTarget() instanceof Rule, node);
+    BuildConfiguration ruleConfig = Preconditions.checkNotNull(node.getConfiguration(), node);
     Rule rule = (Rule) node.getTarget();
 
     ConfiguredAttributeMapper attributeMap = ConfiguredAttributeMapper.of(rule, configConditions);
@@ -289,31 +291,31 @@ public abstract class DependencyResolver {
   private void resolveExplicitAttributes(final RuleResolver depResolver)
       throws InterruptedException, InconsistentAspectOrderException {
 
-    // Record error that might happen during label visitation.
-    final InconsistentAspectOrderException[] exception = new InconsistentAspectOrderException[1];
-
-    depResolver.attributeMap.visitLabels(
-        new AttributeMap.AcceptsLabelAttribute() {
-          @Override
-          public void acceptLabelAttribute(Label label, Attribute attribute)
-              throws InterruptedException {
-            if (attribute.getType() == BuildType.NODEP_LABEL
-                || attribute.isImplicit()
-                || attribute.isLateBound()) {
-              return;
-            }
-            try {
-              depResolver.resolveDep(new AttributeAndOwner(attribute), label);
-            } catch (InconsistentAspectOrderException e) {
-              if (exception[0] == null) {
-                exception[0] = e;
-              }
-            }
-          }
-        });
+    // Track size of filtered iterable by having an always-true clause that only gets checked after
+    // all relevant clauses are checked.
+    Collection<AttributeMap.DepEdge> depEdges = depResolver.attributeMap.visitLabels();
+    Iterable<AttributeMap.DepEdge> filteredEdges =
+        Iterables.filter(
+            depEdges,
+            depEdge ->
+                depEdge.getAttribute().getType() != BuildType.NODEP_LABEL
+                    && !depEdge.getAttribute().isImplicit()
+                    && !depEdge.getAttribute().isLateBound());
+    Map<Label, Target> result =
+        getTargets(
+            Iterables.transform(filteredEdges, AttributeMap.DepEdge::getLabel),
+            depResolver.rule,
+            depResolver.rootCauses,
+            depEdges.size());
+    if (result == null) {
+      return;
+    }
 
-    if (exception[0] != null) {
-      throw exception[0];
+    for (AttributeMap.DepEdge depEdge : filteredEdges) {
+      Target target = result.get(depEdge.getLabel());
+      if (target != null) {
+        depResolver.registerEdge(new AttributeAndOwner(depEdge.getAttribute()), target);
+      }
     }
   }
 
@@ -328,33 +330,57 @@ public abstract class DependencyResolver {
     Label ruleLabel = rule.getLabel();
     ConfiguredAttributeMapper attributeMap = depResolver.attributeMap;
     ImmutableSet<String> mappedAttributes = ImmutableSet.copyOf(attributeMap.getAttributeNames());
-    for (AttributeAndOwner attributeAndOwner : depResolver.attributes) {
-      Attribute attribute = attributeAndOwner.attribute;
-      if (!attribute.isImplicit() || !attribute.getCondition().apply(attributeMap)) {
-        continue;
-      }
+    Set<Label> labelsToFetch = new HashSet<>();
+    Map<Label, Target> targetLookupResult = null;
+    for (boolean collectingLabels : ImmutableList.of(Boolean.TRUE, Boolean.FALSE)) {
+      for (AttributeAndOwner attributeAndOwner : depResolver.attributes) {
+        Attribute attribute = attributeAndOwner.attribute;
+        if (!attribute.isImplicit() || !attribute.getCondition().apply(attributeMap)) {
+          continue;
+        }
 
-      if (attribute.getType() == BuildType.LABEL) {
-        Label label = mappedAttributes.contains(attribute.getName())
-            ? attributeMap.get(attribute.getName(), BuildType.LABEL)
-            : BuildType.LABEL.cast(attribute.getDefaultValue(rule));
+        if (attribute.getType() == BuildType.LABEL) {
+          Label label =
+              mappedAttributes.contains(attribute.getName())
+                  ? attributeMap.get(attribute.getName(), BuildType.LABEL)
+                  : BuildType.LABEL.cast(attribute.getDefaultValue(rule));
 
-        if (label != null) {
-          label = ruleLabel.resolveRepositoryRelative(label);
-          depResolver.resolveDep(attributeAndOwner, label);
-        }
-      } else if (attribute.getType() == BuildType.LABEL_LIST) {
-        List<Label> labelList;
-        if (mappedAttributes.contains(attribute.getName())) {
-          labelList = new ArrayList<>();
-          for (Label label : attributeMap.get(attribute.getName(), BuildType.LABEL_LIST)) {
-            labelList.add(label);
+          if (label != null) {
+            label = ruleLabel.resolveRepositoryRelative(label);
+            if (collectingLabels) {
+              labelsToFetch.add(label);
+            } else {
+              Target target = targetLookupResult.get(label);
+              if (target != null) {
+                depResolver.registerEdge(attributeAndOwner, target);
+              }
+            }
+          }
+        } else if (attribute.getType() == BuildType.LABEL_LIST) {
+          List<Label> labelList;
+          if (mappedAttributes.contains(attribute.getName())) {
+            labelList = attributeMap.get(attribute.getName(), BuildType.LABEL_LIST);
+          } else {
+            labelList = BuildType.LABEL_LIST.cast(attribute.getDefaultValue(rule));
+          }
+          Stream<Label> labelStream = labelList.stream().map(ruleLabel::resolveRepositoryRelative);
+          if (collectingLabels) {
+            labelStream.forEach(labelsToFetch::add);
+          } else {
+            for (Label label : (Iterable<Label>) labelStream::iterator) {
+              Target target = targetLookupResult.get(label);
+              if (target != null) {
+                depResolver.registerEdge(attributeAndOwner, target);
+              }
+            }
           }
-        } else {
-          labelList = BuildType.LABEL_LIST.cast(attribute.getDefaultValue(rule));
         }
-        for (Label label : labelList) {
-          depResolver.resolveDep(attributeAndOwner, ruleLabel.resolveRepositoryRelative(label));
+      }
+      if (collectingLabels) {
+        targetLookupResult =
+            getTargets(labelsToFetch, rule, depResolver.rootCauses, labelsToFetch.size());
+        if (targetLookupResult == null) {
+          return;
         }
       }
     }
@@ -396,51 +422,86 @@ public abstract class DependencyResolver {
       throws EvalException, InvalidConfigurationException, InconsistentAspectOrderException,
           InterruptedException {
     ConfiguredAttributeMapper attributeMap = depResolver.attributeMap;
-    for (AttributeAndOwner attributeAndOwner : depResolver.attributes) {
-      Attribute attribute = attributeAndOwner.attribute;
-      if (!attribute.isLateBound() || !attribute.getCondition().apply(attributeMap)) {
-        continue;
-      }
-
-      LateBoundDefault<?, ?> lateBoundDefault = attribute.getLateBoundDefault();
+    Set<Label> labelsToFetch = new HashSet<>();
+    Map<Label, Target> targetLookupResult = null;
+    for (boolean collectingLabels : ImmutableList.of(Boolean.TRUE, Boolean.FALSE)) {
+      for (AttributeAndOwner attributeAndOwner : depResolver.attributes) {
+        Attribute attribute = attributeAndOwner.attribute;
+        if (!attribute.isLateBound() || !attribute.getCondition().apply(attributeMap)) {
+          continue;
+        }
 
-      boolean hasSplitTransition = false;
-      List<BuildOptions> splitOptions = null;
-      if (attribute.hasSplitConfigurationTransition()) {
-        splitOptions =
-            attribute.getSplitTransition(attributeMap).split(ruleConfig.getOptions());
-        hasSplitTransition = !SplitTransition.equals(ruleConfig.getOptions(), splitOptions);
-      }
+        LateBoundDefault<?, ?> lateBoundDefault = attribute.getLateBoundDefault();
 
-      if (hasSplitTransition && !ruleConfig.isHostConfiguration()) {
-        // Late-bound attribute with a split transition:
-        // Since we want to get the same results as TransitionResolver.evaluateTransition (but
-        // skip it since we've already applied the split), we want to make sure this logic
-        // doesn't do anything differently. TransitionResolver.evaluateTransition has additional
-        // logic for host configs. So when we're in the host configuration we fall back to the
-        // non-split branch, which calls TransitionResolver.evaluateTransition, which returns its
-        // "host mode" result without ever looking at the split.
-        Iterable<BuildConfiguration> splitConfigs =
-            getConfigurations(ruleConfig.fragmentClasses(), splitOptions, defaultBuildOptions);
-        if (splitConfigs == null) {
-          continue; // Need Skyframe deps.
+        boolean hasSplitTransition = false;
+        List<BuildOptions> splitOptions = null;
+        if (attribute.hasSplitConfigurationTransition()) {
+          splitOptions = attribute.getSplitTransition(attributeMap).split(ruleConfig.getOptions());
+          hasSplitTransition = !SplitTransition.equals(ruleConfig.getOptions(), splitOptions);
         }
-        for (BuildConfiguration splitConfig : splitConfigs) {
-          for (Label dep : resolveLateBoundAttribute(depResolver.rule, attribute,
-              lateBoundDefault.useHostConfiguration() ? hostConfig : splitConfig, attributeMap)) {
-            // Skip the normal config transition pipeline and directly feed the split config. This
-            // is because the split already had to be applied to determine the attribute's value.
-            // This makes the split logic in the normal pipeline redundant and potentially
-            // incorrect.
-            depResolver.resolveDep(attributeAndOwner, dep, splitConfig);
+
+        if (hasSplitTransition && !ruleConfig.isHostConfiguration()) {
+          // Late-bound attribute with a split transition:
+          // Since we want to get the same results as TransitionResolver.evaluateTransition (but
+          // skip it since we've already applied the split), we want to make sure this logic
+          // doesn't do anything differently. TransitionResolver.evaluateTransition has additional
+          // logic for host configs. So when we're in the host configuration we fall back to the
+          // non-split branch, which calls TransitionResolver.evaluateTransition, which returns its
+          // "host mode" result without ever looking at the split.
+          Iterable<BuildConfiguration> splitConfigs =
+              getConfigurations(ruleConfig.fragmentClasses(), splitOptions, defaultBuildOptions);
+          if (splitConfigs == null) {
+            Preconditions.checkState(collectingLabels, attributeAndOwner);
+            continue; // Need Skyframe deps.
+          }
+          for (BuildConfiguration splitConfig : splitConfigs) {
+            for (Label dep :
+                resolveLateBoundAttribute(
+                    depResolver.rule,
+                    attribute,
+                    lateBoundDefault.useHostConfiguration() ? hostConfig : splitConfig,
+                    attributeMap)) {
+              if (collectingLabels) {
+                labelsToFetch.add(dep);
+              } else {
+                // Skip the normal config transition pipeline and directly feed the split config.
+                // This is because the split already had to be applied to determine the attribute's
+                // value. This makes the split logic in the normal pipeline redundant and
+                // potentially incorrect.
+                Target target = targetLookupResult.get(dep);
+                if (target != null) {
+                  depResolver.registerEdge(attributeAndOwner, target, splitConfig);
+                }
+              }
+            }
+          }
+        } else {
+          List<Label> deps =
+              resolveLateBoundAttribute(
+                  depResolver.rule,
+                  attribute,
+                  lateBoundDefault.useHostConfiguration() ? hostConfig : ruleConfig,
+                  attributeMap);
+          if (collectingLabels) {
+            labelsToFetch.addAll(deps);
+          } else {
+            // Late-bound attribute without a split transition:
+            for (Label dep : deps) {
+              Target target = targetLookupResult.get(dep);
+              if (target != null) {
+                // Process this dep like a normal attribute.
+                depResolver.registerEdge(attributeAndOwner, target);
+              }
+            }
           }
         }
-      } else {
-        // Late-bound attribute without a split transition:
-        for (Label dep : resolveLateBoundAttribute(depResolver.rule, attribute,
-            lateBoundDefault.useHostConfiguration() ? hostConfig : ruleConfig, attributeMap)) {
-          // Process this dep like a normal attribute.
-          depResolver.resolveDep(attributeAndOwner, dep);
+      }
+      if (collectingLabels) {
+        targetLookupResult =
+            getTargets(
+                labelsToFetch, depResolver.rule, depResolver.rootCauses, labelsToFetch.size());
+        if (targetLookupResult == null) {
+          return;
         }
       }
     }
@@ -464,12 +525,9 @@ public abstract class DependencyResolver {
    * @param config the configuration to evaluate the attribute in
    * @param attributeMap mapper to attribute values
    */
-  private Iterable<Label> resolveLateBoundAttribute(
-      Rule rule,
-      Attribute attribute,
-      BuildConfiguration config,
-      AttributeMap attributeMap)
-      throws EvalException, InterruptedException {
+  private List<Label> resolveLateBoundAttribute(
+      Rule rule, Attribute attribute, BuildConfiguration config, AttributeMap attributeMap)
+      throws EvalException {
     Preconditions.checkArgument(attribute.isLateBound());
 
     Object actualValue =
@@ -533,7 +591,7 @@ public abstract class DependencyResolver {
    * @param attrName the name of the attribute to add dependency labels to
    * @param labels the dependencies to add
    */
-  private void addExplicitDeps(RuleResolver depResolver, String attrName, Iterable<Label> labels)
+  private void addExplicitDeps(RuleResolver depResolver, String attrName, Collection<Label> labels)
       throws InterruptedException, InconsistentAspectOrderException {
     Rule rule = depResolver.rule;
     if (!rule.isAttrDefined(attrName, BuildType.LABEL_LIST)
@@ -541,8 +599,14 @@ public abstract class DependencyResolver {
       return;
     }
     Attribute attribute = rule.getRuleClassObject().getAttributeByName(attrName);
-    for (Label label : labels) {
-      depResolver.resolveDep(new AttributeAndOwner(attribute), label);
+    Map<Label, Target> result = getTargets(labels, rule, depResolver.rootCauses, labels.size());
+    if (result == null) {
+      return;
+    }
+    AttributeAndOwner attributeAndOwner = new AttributeAndOwner(attribute);
+
+    for (Target target : result.values()) {
+      depResolver.registerEdge(attributeAndOwner, target);
     }
   }
 
@@ -550,8 +614,11 @@ public abstract class DependencyResolver {
    * Converts the given multimap of attributes to labels into a multi map of attributes to {@link
    * Dependency} objects using the proper configuration transition for each attribute.
    *
+   * <p>Returns null if Skyframe dependencies are missing.
+   *
    * @throws IllegalArgumentException if the {@code node} does not refer to a {@link Rule} instance
    */
+  @Nullable
   public final Collection<Dependency> resolveRuleLabels(
       TargetAndConfiguration node,
       OrderedSetMultimap<Attribute, Label> depLabels,
@@ -570,10 +637,17 @@ public abstract class DependencyResolver {
             rootCauses,
             outgoingEdges,
             trimmingTransitionFactory);
-    Map<Attribute, Collection<Label>> m = depLabels.asMap();
+    Map<Label, Target> result = getTargets(depLabels.values(), rule, rootCauses, depLabels.size());
+    if (result == null) {
+      return null;
+    }
     for (Map.Entry<Attribute, Collection<Label>> entry : depLabels.asMap().entrySet()) {
+      AttributeAndOwner attributeAndOwner = new AttributeAndOwner(entry.getKey());
       for (Label depLabel : entry.getValue()) {
-        depResolver.resolveDep(new AttributeAndOwner(entry.getKey()), depLabel);
+        Target target = result.get(depLabel);
+        if (target != null) {
+          depResolver.registerEdge(attributeAndOwner, target);
+        }
       }
     }
     return outgoingEdges.values();
@@ -585,20 +659,23 @@ public abstract class DependencyResolver {
       NestedSetBuilder<Cause> rootCauses,
       Collection<Dependency> outgoingEdges)
       throws InterruptedException {
-    for (Label label : packageGroup.getIncludes()) {
-      Target target = getTarget(packageGroup, label, rootCauses);
-      if (target == null) {
-        continue;
-      }
+    List<Label> includes = packageGroup.getIncludes();
+    Map<Label, Target> targetMap = getTargets(includes, packageGroup, rootCauses, includes.size());
+    if (targetMap == null) {
+      return;
+    }
+    Collection<Target> targets = targetMap.values();
+
+    for (Target target : targets) {
       if (!(target instanceof PackageGroup)) {
         // Note that this error could also be caught in PackageGroupConfiguredTarget, but since
         // these have the null configuration, visiting the corresponding target would trigger an
         // analysis of a rule with a null configuration, which doesn't work.
-        invalidPackageGroupReferenceHook(node, label);
+        invalidPackageGroupReferenceHook(node, target.getLabel());
         continue;
       }
 
-      outgoingEdges.add(Dependency.withNullConfiguration(label));
+      outgoingEdges.add(Dependency.withNullConfiguration(target.getLabel()));
     }
   }
 
@@ -749,15 +826,11 @@ public abstract class DependencyResolver {
     }
 
     /**
-     * Resolves the given dep for the given attribute, including determining which configurations to
-     * apply to it.
+     * Resolves the given dep for the given attribute, determining which configurations to apply to
+     * it.
      */
-    void resolveDep(AttributeAndOwner attributeAndOwner, Label depLabel)
-        throws InterruptedException, InconsistentAspectOrderException {
-      Target toTarget = getTarget(rule, depLabel, rootCauses);
-      if (toTarget == null) {
-        return; // Skip this round: we still need to Skyframe-evaluate the dep's target.
-      }
+    void registerEdge(AttributeAndOwner attributeAndOwner, Target toTarget)
+        throws InconsistentAspectOrderException {
       ConfigurationTransition transition =
           TransitionResolver.evaluateTransition(
               ruleConfig,
@@ -769,32 +842,31 @@ public abstract class DependencyResolver {
       outgoingEdges.put(
           attributeAndOwner.attribute,
           transition == NullTransition.INSTANCE
-              ? Dependency.withNullConfiguration(depLabel)
-              : Dependency.withTransitionAndAspects(depLabel, transition,
-                    requiredAspects(attributeAndOwner, toTarget)));
+              ? Dependency.withNullConfiguration(toTarget.getLabel())
+              : Dependency.withTransitionAndAspects(
+                  toTarget.getLabel(), transition, requiredAspects(attributeAndOwner, toTarget)));
     }
 
     /**
      * Resolves the given dep for the given attribute using a pre-prepared configuration.
      *
      * <p>Use this method with care: it skips Bazel's standard config transition semantics ({@link
-     * TransitionResolver#evaluateTransition}). That means attributes passed through here won't
-     * obey standard rules on which configurations apply to their deps. This should only be done for
+     * TransitionResolver#evaluateTransition}). That means attributes passed through here won't obey
+     * standard rules on which configurations apply to their deps. This should only be done for
      * special circumstances that really justify the difference. When in doubt, use {@link
-     * #resolveDep(AttributeAndOwner, Label)}.
+     * #registerEdge(AttributeAndOwner, Target)}.
      */
-    void resolveDep(AttributeAndOwner attributeAndOwner, Label depLabel, BuildConfiguration config)
-        throws InterruptedException, InconsistentAspectOrderException {
-      Target toTarget = getTarget(rule, depLabel, rootCauses);
-      if (toTarget == null) {
-        return; // Skip this round: this is either a loading error or unevaluated Skyframe dep.
-      }
+    void registerEdge(
+        AttributeAndOwner attributeAndOwner, Target toTarget, BuildConfiguration config)
+        throws InconsistentAspectOrderException {
       outgoingEdges.put(
           attributeAndOwner.attribute,
           TransitionResolver.usesNullConfiguration(toTarget)
-              ? Dependency.withNullConfiguration(depLabel)
-              : Dependency.withTransitionAndAspects(depLabel, new FixedTransition(
-                    config.getOptions()), requiredAspects(attributeAndOwner, toTarget)));
+              ? Dependency.withNullConfiguration(toTarget.getLabel())
+              : Dependency.withTransitionAndAspects(
+                  toTarget.getLabel(),
+                  new FixedTransition(config.getOptions()),
+                  requiredAspects(attributeAndOwner, toTarget)));
     }
 
     private AspectCollection requiredAspects(AttributeAndOwner attributeAndOwner,
@@ -844,23 +916,26 @@ public abstract class DependencyResolver {
       Collection<Dependency> outgoingEdges)
       throws InterruptedException {
     Target target = node.getTarget();
-    for (Label label : target.getVisibility().getDependencyLabels()) {
-      Target visibilityTarget = getTarget(target, label, rootCauses);
-      if (visibilityTarget == null) {
-        continue;
-      }
+    List<Label> dependencyLabels = target.getVisibility().getDependencyLabels();
+    Map<Label, Target> targetMap =
+        getTargets(dependencyLabels, target, rootCauses, dependencyLabels.size());
+    if (targetMap == null) {
+      return;
+    }
+    Collection<Target> targets = targetMap.values();
+    for (Target visibilityTarget : targets) {
       if (!(visibilityTarget instanceof PackageGroup)) {
         // Note that this error could also be caught in
         // AbstractConfiguredTarget.convertVisibility(), but we have an
         // opportunity here to avoid dependency cycles that result from
         // the visibility attribute of a rule referring to a rule that
         // depends on it (instead of its package)
-        invalidVisibilityReferenceHook(node, label);
+        invalidVisibilityReferenceHook(node, visibilityTarget.getLabel());
         continue;
       }
 
       // Visibility always has null configuration
-      outgoingEdges.add(Dependency.withNullConfiguration(label));
+      outgoingEdges.add(Dependency.withNullConfiguration(visibilityTarget.getLabel()));
     }
   }
 
@@ -886,23 +961,26 @@ public abstract class DependencyResolver {
    *
    * @param from the target referencing the missing target
    * @param to the missing target
-   * @param e the exception that was thrown, e.g., by {@link #getTarget}
+   * @param e the exception that was thrown, e.g., by {@link #getTargets}
    */
   protected abstract void missingEdgeHook(Target from, Label to, NoSuchThingException e)
       throws InterruptedException;
 
   /**
-   * Returns the target by the given label.
+   * Returns the targets for the given labels.
    *
-   * <p>Returns null if the target is not ready to be returned at this moment. If getTarget returns
-   * null once or more during a {@link #dependentNodeMap} call, the results of that call will be
-   * incomplete. For use within Skyframe, where several iterations may be needed to discover all
-   * dependencies.
+   * <p>Returns null if any targets are not ready to be returned at this moment because of missing
+   * Skyframe dependencies. If getTargets returns null once or more during a {@link
+   * #dependentNodeMap} call, the results of that call will be incomplete. As is usual in these
+   * situation, the caller must return control to Skyframe and wait for the SkyFunction to be
+   * restarted, at which point the requested dependencies will be available.
    */
-  @Nullable
-  protected abstract Target getTarget(Target from, Label label, NestedSetBuilder<Cause> rootCauses)
+  protected abstract Map<Label, Target> getTargets(
+      Iterable<Label> labels,
+      Target fromTarget,
+      NestedSetBuilder<Cause> rootCauses,
+      int labelsSizeHint)
       throws InterruptedException;
-
   /**
    * Returns the build configurations with the given fragments and {@link
    * BuildOptions.OptionsDiffForReconstruction} resulting from calling {@link
diff --git a/src/main/java/com/google/devtools/build/lib/packages/AbstractAttributeMapper.java b/src/main/java/com/google/devtools/build/lib/packages/AbstractAttributeMapper.java
index fc587e090b..384ce097b9 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/AbstractAttributeMapper.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/AbstractAttributeMapper.java
@@ -19,6 +19,9 @@ import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.events.Location;
 import com.google.devtools.build.lib.packages.BuildType.SelectorList;
 import com.google.devtools.build.lib.syntax.Type;
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.List;
 import javax.annotation.Nullable;
 
 /**
@@ -162,16 +165,15 @@ public abstract class AbstractAttributeMapper implements AttributeMap {
   }
 
   @Override
-  public void visitLabels(final AcceptsLabelAttribute observer) throws InterruptedException {
-    Type.LabelVisitor<Attribute> visitor = new Type.LabelVisitor<Attribute>() {
-      @Override
-      public void visit(@Nullable Label label, Attribute attribute) throws InterruptedException {
-        if (label != null) {
-          Label absoluteLabel = ruleLabel.resolveRepositoryRelative(label);
-          observer.acceptLabelAttribute(absoluteLabel, attribute);
-        }
-      }
-    };
+  public Collection<DepEdge> visitLabels() throws InterruptedException {
+    List<DepEdge> edges = new ArrayList<>();
+    Type.LabelVisitor<Attribute> visitor =
+        (label, attribute) -> {
+          if (label != null) {
+            Label absoluteLabel = ruleLabel.resolveRepositoryRelative(label);
+            edges.add(AttributeMap.DepEdge.create(absoluteLabel, attribute));
+          }
+        };
     for (Attribute attribute : ruleClass.getAttributes()) {
       Type<?> type = attribute.getType();
       // TODO(bazel-team): clean up the typing / visitation interface so we don't have to
@@ -181,6 +183,7 @@ public abstract class AbstractAttributeMapper implements AttributeMap {
         visitLabels(attribute, visitor);
       }
     }
+    return edges;
   }
 
   /** Visits all labels reachable from the given attribute. */
diff --git a/src/main/java/com/google/devtools/build/lib/packages/AggregatingAttributeMapper.java b/src/main/java/com/google/devtools/build/lib/packages/AggregatingAttributeMapper.java
index e932e60174..75d3e0ee7a 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/AggregatingAttributeMapper.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/AggregatingAttributeMapper.java
@@ -29,6 +29,7 @@ import com.google.devtools.build.lib.syntax.Type;
 import com.google.devtools.build.lib.syntax.Type.LabelVisitor;
 import com.google.devtools.build.lib.syntax.Type.ListType;
 import java.util.ArrayList;
+import java.util.Collection;
 import java.util.HashMap;
 import java.util.LinkedHashSet;
 import java.util.LinkedList;
@@ -521,8 +522,8 @@ public class AggregatingAttributeMapper extends AbstractAttributeMapper {
       }
 
       @Override
-      public void visitLabels(AcceptsLabelAttribute observer) throws InterruptedException {
-        owner.visitLabels(observer);
+      public Collection<DepEdge> visitLabels() throws InterruptedException {
+        return owner.visitLabels();
       }
 
       @Override
diff --git a/src/main/java/com/google/devtools/build/lib/packages/AttributeMap.java b/src/main/java/com/google/devtools/build/lib/packages/AttributeMap.java
index b8a28ce845..faf3d9ea45 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/AttributeMap.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/AttributeMap.java
@@ -13,10 +13,12 @@
 // limitations under the License.
 package com.google.devtools.build.lib.packages;
 
+import com.google.auto.value.AutoValue;
 import com.google.common.collect.ImmutableList;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.events.Location;
 import com.google.devtools.build.lib.syntax.Type;
+import java.util.Collection;
 import javax.annotation.Nullable;
 
 /**
@@ -104,24 +106,28 @@ public interface AttributeMap {
   /** Returns the {@link Location} at which the attribute was defined. */
   Location getAttributeLocation(String attrName);
 
-  /** An interface which accepts {@link Attribute}s, used by {@link #visitLabels}. */
-  interface AcceptsLabelAttribute {
-    /**
-     * Accept a (Label, Attribute) pair describing a dependency edge.
-     *
-     * @param label the target node of the (Rule, Label) edge. The source node should already be
-     *     known.
-     * @param attribute the attribute.
-     */
-    void acceptLabelAttribute(Label label, Attribute attribute) throws InterruptedException;
-  }
+  /**
+   * Returns a {@link Collection} with a {@link DepEdge} for every attribute that contains labels in
+   * its value (either by *being* a label or being a collection that includes labels).
+   */
+  Collection<DepEdge> visitLabels() throws InterruptedException;
 
   /**
-   * For all attributes that contain labels in their values (either by *being* a label or being a
-   * collection that includes labels), visits every label and notifies the specified observer at
-   * each visit.
+   * {@code (Label, Attribute)} pair describing a dependency edge.
+   *
+   * <p>The {@link Label} is the target node of the {@code (Rule, Label)} edge. The source node
+   * should already be known. The {@link Attribute} is the attribute giving the edge.
    */
-  void visitLabels(AcceptsLabelAttribute observer) throws InterruptedException;
+  @AutoValue
+  abstract class DepEdge {
+    public abstract Label getLabel();
+
+    public abstract Attribute getAttribute();
+
+    static DepEdge create(Label label, Attribute attribute) {
+      return new AutoValue_AttributeMap_DepEdge(label, attribute);
+    }
+  }
 
   // TODO(bazel-team): These methods are here to support computed defaults that inherit
   // package-level default values. Instead, we should auto-inherit and remove the computed
diff --git a/src/main/java/com/google/devtools/build/lib/packages/DelegatingAttributeMapper.java b/src/main/java/com/google/devtools/build/lib/packages/DelegatingAttributeMapper.java
index 28f29bc96e..c08f3d9ed2 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/DelegatingAttributeMapper.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/DelegatingAttributeMapper.java
@@ -18,6 +18,7 @@ import com.google.common.collect.ImmutableList;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.events.Location;
 import com.google.devtools.build.lib.syntax.Type;
+import java.util.Collection;
 import javax.annotation.Nullable;
 
 /**
@@ -79,8 +80,8 @@ public class DelegatingAttributeMapper implements AttributeMap {
   }
 
   @Override
-  public void visitLabels(AcceptsLabelAttribute observer) throws InterruptedException {
-    delegate.visitLabels(observer);
+  public Collection<DepEdge> visitLabels() throws InterruptedException {
+    return delegate.visitLabels();
   }
 
   @Override
diff --git a/src/main/java/com/google/devtools/build/lib/packages/Package.java b/src/main/java/com/google/devtools/build/lib/packages/Package.java
index daefc112ae..ad823a2e55 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/Package.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/Package.java
@@ -32,7 +32,6 @@ import com.google.devtools.build.lib.events.Event;
 import com.google.devtools.build.lib.events.EventHandler;
 import com.google.devtools.build.lib.events.ExtendedEventHandler.Postable;
 import com.google.devtools.build.lib.events.Location;
-import com.google.devtools.build.lib.packages.AttributeMap.AcceptsLabelAttribute;
 import com.google.devtools.build.lib.packages.License.DistributionType;
 import com.google.devtools.build.lib.skyframe.serialization.DeserializationContext;
 import com.google.devtools.build.lib.skyframe.serialization.ObjectCodec;
@@ -1413,12 +1412,10 @@ public class Package {
         // All labels mentioned in a rule that refer to an unknown target in the
         // current package are assumed to be InputFiles, so let's create them:
         for (final Rule rule : sortedRules) {
-          AggregatingAttributeMapper.of(rule).visitLabels(new AcceptsLabelAttribute() {
-            @Override
-            public void acceptLabelAttribute(Label label, Attribute attribute) {
-              createInputFileMaybe(label, rule.getAttributeLocation(attribute.getName()));
-            }
-          });
+          for (AttributeMap.DepEdge depEdge : AggregatingAttributeMapper.of(rule).visitLabels()) {
+            createInputFileMaybe(
+                depEdge.getLabel(), rule.getAttributeLocation(depEdge.getAttribute().getName()));
+          }
         }
       }
 
diff --git a/src/main/java/com/google/devtools/build/lib/packages/Rule.java b/src/main/java/com/google/devtools/build/lib/packages/Rule.java
index 37c8767a1e..94fbaafe54 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/Rule.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/Rule.java
@@ -406,12 +406,11 @@ public final class Rule implements Target, DependencyFilter.AttributeInfoProvide
   /** Returns a new List instance containing all direct dependencies (all types). */
   public Collection<Label> getLabels() throws InterruptedException {
     final List<Label> labels = Lists.newArrayList();
-    AggregatingAttributeMapper.of(this).visitLabels(new AttributeMap.AcceptsLabelAttribute() {
-      @Override
-      public void acceptLabelAttribute(Label label, Attribute attribute) {
-        labels.add(label);
-      }
-    });
+    AggregatingAttributeMapper.of(this)
+        .visitLabels()
+        .stream()
+        .map(AttributeMap.DepEdge::getLabel)
+        .forEach(labels::add);
     return labels;
   }
 
@@ -444,14 +443,11 @@ public final class Rule implements Target, DependencyFilter.AttributeInfoProvide
     // TODO(bazel-team): move this to AttributeMap, too. Just like visitLabels, which labels should
     // be visited may depend on the calling context. We shouldn't implicitly decide this for
     // the caller.
-    AggregatingAttributeMapper.of(this).visitLabels(new AttributeMap.AcceptsLabelAttribute() {
-      @Override
-      public void acceptLabelAttribute(Label label, Attribute attribute) {
-        if (predicate.apply(Rule.this, attribute)) {
-          transitions.put(attribute, label);
-        }
-      }
-    });
+    AggregatingAttributeMapper.of(this)
+        .visitLabels()
+        .stream()
+        .filter(depEdge -> predicate.apply(Rule.this, depEdge.getAttribute()))
+        .forEach(depEdge -> transitions.put(depEdge.getAttribute(), depEdge.getLabel()));
     return transitions;
   }
 
@@ -706,16 +702,10 @@ public final class Rule implements Target, DependencyFilter.AttributeInfoProvide
   // the introduction of this code is #2210848 (NullPointerException in
   // Package.checkForConflicts() ).
   void checkForNullLabels() throws InterruptedException {
-    AggregatingAttributeMapper.of(this).visitLabels(
-        new AttributeMap.AcceptsLabelAttribute() {
-          @Override
-          public void acceptLabelAttribute(Label labelToCheck, Attribute attribute) {
-            checkForNullLabel(labelToCheck, attribute);
-          }
-        });
-    for (OutputFile outputFile : getOutputFiles()) {
-      checkForNullLabel(outputFile.getLabel(), "output file");
-    }
+    AggregatingAttributeMapper.of(this)
+        .visitLabels()
+        .forEach(depEdge -> checkForNullLabel(depEdge.getLabel(), depEdge.getAttribute()));
+    getOutputFiles().forEach(outputFile -> checkForNullLabel(outputFile.getLabel(), "output file"));
   }
 
   /**
diff --git a/src/main/java/com/google/devtools/build/lib/packages/TargetUtils.java b/src/main/java/com/google/devtools/build/lib/packages/TargetUtils.java
index b1dd3da648..b68f90790a 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/TargetUtils.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/TargetUtils.java
@@ -275,9 +275,13 @@ public final class TargetUtils {
       return true;
     }
 
-    ExplicitEdgeVisitor visitor = new ExplicitEdgeVisitor(rule, label);
-    AggregatingAttributeMapper.of(rule).visitLabels(visitor);
-    return visitor.isExplicit();
+    for (AttributeMap.DepEdge depEdge : AggregatingAttributeMapper.of(rule).visitLabels()) {
+      if (rule.isAttributeValueExplicitlySpecified(depEdge.getAttribute())
+          && label.equals(depEdge.getLabel())) {
+        return true;
+      }
+    }
+    return false;
   }
 
   /**
@@ -306,30 +310,6 @@ public final class TargetUtils {
     };
   }
 
-  private static class ExplicitEdgeVisitor implements AttributeMap.AcceptsLabelAttribute {
-    private final Label expectedLabel;
-    private final Rule rule;
-    private boolean isExplicit = false;
-
-    public ExplicitEdgeVisitor(Rule rule, Label expected) {
-      this.rule = rule;
-      this.expectedLabel = expected;
-    }
-
-    @Override
-    public void acceptLabelAttribute(Label label, Attribute attr) {
-      if (isExplicit || !rule.isAttributeValueExplicitlySpecified(attr)) {
-        // Nothing to do here.
-      } else if (expectedLabel.equals(label)) {
-        isExplicit = true;
-      }
-    }
-
-    public boolean isExplicit() {
-      return isExplicit;
-    }
-  }
-
   /**
    * Return {@link Location} for {@link Target} target, if it should not be null.
    */
diff --git a/src/main/java/com/google/devtools/build/lib/query2/LabelVisitor.java b/src/main/java/com/google/devtools/build/lib/query2/LabelVisitor.java
index ab1f1eaaa3..af06cde70e 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/LabelVisitor.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/LabelVisitor.java
@@ -26,7 +26,6 @@ import com.google.devtools.build.lib.events.ExtendedEventHandler;
 import com.google.devtools.build.lib.packages.AggregatingAttributeMapper;
 import com.google.devtools.build.lib.packages.AspectDefinition;
 import com.google.devtools.build.lib.packages.Attribute;
-import com.google.devtools.build.lib.packages.AttributeMap;
 import com.google.devtools.build.lib.packages.BuildType;
 import com.google.devtools.build.lib.packages.DependencyFilter;
 import com.google.devtools.build.lib.packages.InputFile;
@@ -353,15 +352,13 @@ final class LabelVisitor {
     private void visitRule(final Rule rule, final int depth, final int count)
         throws InterruptedException {
       // Follow all labels defined by this rule:
-      AggregatingAttributeMapper.of(rule).visitLabels(new AttributeMap.AcceptsLabelAttribute() {
-        @Override
-        public void acceptLabelAttribute(Label label, Attribute attribute) {
-          if (!edgeFilter.apply(rule, attribute)) {
-            return;
-          }
-          enqueueTarget(rule, attribute, label, depth, count);
-        }
-      });
+      AggregatingAttributeMapper.of(rule)
+          .visitLabels()
+          .stream()
+          .filter(depEdge -> edgeFilter.apply(rule, depEdge.getAttribute()))
+          .forEach(
+              depEdge ->
+                  enqueueTarget(rule, depEdge.getAttribute(), depEdge.getLabel(), depth, count));
     }
 
     @ThreadSafe
diff --git a/src/main/java/com/google/devtools/build/lib/query2/TransitionsOutputFormatterCallback.java b/src/main/java/com/google/devtools/build/lib/query2/TransitionsOutputFormatterCallback.java
index 27685267e8..81298a46f7 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/TransitionsOutputFormatterCallback.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/TransitionsOutputFormatterCallback.java
@@ -19,6 +19,7 @@ import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.Iterables;
 import com.google.common.collect.Maps;
+import com.google.common.collect.Streams;
 import com.google.devtools.build.lib.analysis.AspectCollection;
 import com.google.devtools.build.lib.analysis.ConfiguredTarget;
 import com.google.devtools.build.lib.analysis.Dependency;
@@ -58,6 +59,8 @@ import java.io.OutputStream;
 import java.util.HashMap;
 import java.util.List;
 import java.util.Map;
+import java.util.Objects;
+import java.util.function.Function;
 import java.util.stream.Collectors;
 import javax.annotation.Nullable;
 
@@ -242,9 +245,16 @@ public class TransitionsOutputFormatterCallback extends CqueryThreadsafeCallback
     }
 
     @Override
-    protected Target getTarget(Target from, Label label, NestedSetBuilder<Cause> rootCauses)
-        throws InterruptedException {
-      return partialResultMap.get(label);
+    protected Map<Label, Target> getTargets(
+        Iterable<Label> labels,
+        Target fromTarget,
+        NestedSetBuilder<Cause> rootCauses,
+        int labelsSizeHint) {
+      return Streams.stream(labels)
+          .distinct()
+          .filter(Objects::nonNull)
+          .filter(partialResultMap::containsKey)
+          .collect(Collectors.toMap(Function.identity(), partialResultMap::get));
     }
 
     @Override
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ConfiguredTargetFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/ConfiguredTargetFunction.java
index d50c6c80f3..bad9ec038b 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ConfiguredTargetFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ConfiguredTargetFunction.java
@@ -568,8 +568,13 @@ public final class ConfiguredTargetFunction implements SkyFunction {
     // conditions evaluate over the current target's configuration).
     ImmutableList.Builder<Dependency> depsBuilder = ImmutableList.builder();
     try {
-      for (Dependency dep : resolver.resolveRuleLabels(
-          ctgValue, configLabelMap, transitiveRootCauses, trimmingTransitionFactory)) {
+      Iterable<Dependency> dependencies =
+          resolver.resolveRuleLabels(
+              ctgValue, configLabelMap, transitiveRootCauses, trimmingTransitionFactory);
+      if (env.valuesMissing()) {
+        return null;
+      }
+      for (Dependency dep : dependencies) {
         if (dep.hasExplicitConfiguration() && dep.getConfiguration() == null) {
           // Bazel assumes non-existent labels are source files, which have a null configuration.
           // Keep those as is. Otherwise ConfiguredTargetAndData throws an exception about a
@@ -584,9 +589,6 @@ public final class ConfiguredTargetFunction implements SkyFunction {
     } catch (InconsistentAspectOrderException e) {
       throw new DependencyEvaluationException(e);
     }
-    if (env.valuesMissing()) {
-      return null;
-    }
     ImmutableList<Dependency> configConditionDeps = depsBuilder.build();
 
     Map<SkyKey, ConfiguredTargetAndData> configValues =
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeDependencyResolver.java b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeDependencyResolver.java
index 4d1b86bed2..1e78a41891 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeDependencyResolver.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeDependencyResolver.java
@@ -13,7 +13,10 @@
 // limitations under the License.
 package com.google.devtools.build.lib.skyframe;
 
+import com.google.common.base.Preconditions;
 import com.google.common.collect.ImmutableList;
+import com.google.common.collect.Iterables;
+import com.google.common.collect.Maps;
 import com.google.devtools.build.lib.analysis.DependencyResolver;
 import com.google.devtools.build.lib.analysis.TargetAndConfiguration;
 import com.google.devtools.build.lib.analysis.config.BuildConfiguration;
@@ -35,6 +38,8 @@ import com.google.devtools.build.skyframe.SkyFunction.Environment;
 import com.google.devtools.build.skyframe.SkyKey;
 import com.google.devtools.build.skyframe.ValueOrException;
 import java.util.ArrayList;
+import java.util.Collection;
+import java.util.HashMap;
 import java.util.List;
 import java.util.Map;
 import javax.annotation.Nullable;
@@ -88,39 +93,53 @@ public final class SkyframeDependencyResolver extends DependencyResolver {
 
   @Nullable
   @Override
-  protected Target getTarget(Target from, Label label, NestedSetBuilder<Cause> rootCauses)
+  protected Map<Label, Target> getTargets(
+      Iterable<Label> labels,
+      Target fromTarget,
+      NestedSetBuilder<Cause> rootCauses,
+      int labelsSizeHint)
       throws InterruptedException {
-    SkyKey key = PackageValue.key(label.getPackageIdentifier());
-    PackageValue packageValue;
-    try {
-      packageValue = (PackageValue) env.getValueOrThrow(key, NoSuchPackageException.class);
-    } catch (NoSuchPackageException e) {
-      rootCauses.add(new LoadingFailedCause(label, e.getMessage()));
-      missingEdgeHook(from, label, e);
+    Map<SkyKey, ValueOrException<NoSuchPackageException>> packages =
+        env.getValuesOrThrow(
+            Iterables.transform(labels, label -> PackageValue.key(label.getPackageIdentifier())),
+            NoSuchPackageException.class);
+    if (env.valuesMissing()) {
       return null;
     }
-    if (packageValue == null) {
-      return null;
+    if (labels instanceof Collection) {
+      labelsSizeHint = ((Collection<Label>) labels).size();
+    } else if (labelsSizeHint <= 0) {
+      labelsSizeHint = 2 * packages.size();
     }
-    Package pkg = packageValue.getPackage();
-    try {
-      Target target = pkg.getTarget(label.getName());
-      if (pkg.containsErrors()) {
-        NoSuchTargetException e = new NoSuchTargetException(target);
-        missingEdgeHook(from, label, e);
-        if (target != null) {
+    // Duplicates can occur, so we can't use ImmutableMap.
+    HashMap<Label, Target> result = Maps.newHashMapWithExpectedSize(labelsSizeHint);
+    for (Label label : labels) {
+      PackageValue packageValue;
+      try {
+        packageValue =
+            Preconditions.checkNotNull(
+                (PackageValue) packages.get(PackageValue.key(label.getPackageIdentifier())).get(),
+                label);
+      } catch (NoSuchPackageException e) {
+        rootCauses.add(new LoadingFailedCause(label, e.getMessage()));
+        missingEdgeHook(fromTarget, label, e);
+        continue;
+      }
+      Package pkg = packageValue.getPackage();
+      try {
+        Target target = pkg.getTarget(label.getName());
+        if (pkg.containsErrors()) {
+          NoSuchTargetException e = new NoSuchTargetException(target);
+          missingEdgeHook(fromTarget, label, e);
           rootCauses.add(new LoadingFailedCause(label, e.getMessage()));
-          return target;
-        } else {
-          return null;
         }
+        result.put(label, target);
+      } catch (NoSuchTargetException e) {
+        rootCauses.add(new LoadingFailedCause(label, e.getMessage()));
+        missingEdgeHook(fromTarget, label, e);
       }
-      return target;
-    } catch (NoSuchTargetException e) {
-      rootCauses.add(new LoadingFailedCause(label, e.getMessage()));
-      missingEdgeHook(from, label, e);
-      return null;
     }
+    return result;
   }
 
   @Nullable
diff --git a/src/test/java/com/google/devtools/build/lib/analysis/BuildViewTest.java b/src/test/java/com/google/devtools/build/lib/analysis/BuildViewTest.java
index b6107f4915..3b6221ad82 100644
--- a/src/test/java/com/google/devtools/build/lib/analysis/BuildViewTest.java
+++ b/src/test/java/com/google/devtools/build/lib/analysis/BuildViewTest.java
@@ -46,6 +46,7 @@ import com.google.devtools.build.lib.packages.BuildType;
 import com.google.devtools.build.lib.packages.Rule;
 import com.google.devtools.build.lib.pkgcache.LoadingFailureEvent;
 import com.google.devtools.build.lib.skyframe.ConfiguredTargetAndData;
+import com.google.devtools.build.lib.syntax.Type;
 import com.google.devtools.build.lib.testutil.Suite;
 import com.google.devtools.build.lib.testutil.TestConstants;
 import com.google.devtools.build.lib.testutil.TestRuleClassProvider;
@@ -1321,6 +1322,43 @@ public class BuildViewTest extends BuildViewTestBase {
   }
 
   @Test
+  public void errorInImplicitDeps() throws Exception {
+    setRulesAvailableInTests(
+        (MockRule)
+            () -> {
+              try {
+                return MockRule.define(
+                    "custom_rule",
+                    attr("$implicit1", BuildType.LABEL_LIST)
+                        .defaultValue(
+                            ImmutableList.of(
+                                Label.parseAbsoluteUnchecked("//bad2:label"),
+                                Label.parseAbsoluteUnchecked("//foo:dep"))),
+                    attr("$implicit2", BuildType.LABEL)
+                        .defaultValue(Label.parseAbsoluteUnchecked("//bad:label")));
+              } catch (Type.ConversionException e) {
+                throw new IllegalStateException(e);
+              }
+            });
+    scratch.file("foo/BUILD", "custom_rule(name = 'foo')", "sh_library(name = 'dep')");
+    scratch.file(
+        "bad/BUILD",
+        "sh_library(name = 'other_label', nonexistent_attribute = 'blah')",
+        "sh_library(name = 'label')");
+    // bad2/BUILD is completely missing.
+    reporter.removeHandler(failFastHandler);
+    update(defaultFlags().with(Flag.KEEP_GOING), "//foo:foo");
+    assertContainsEvent(
+        "every rule of type custom_rule implicitly depends upon the target '//bad2:label', but this"
+            + " target could not be found because of: no such package 'bad2': BUILD file not found "
+            + "on package path");
+    assertContainsEvent(
+        "every rule of type custom_rule implicitly depends upon the target '//bad:label', but this "
+            + "target could not be found because of: Target '//bad:label' contains an error and its"
+            + " package is in error");
+  }
+
+  @Test
   public void onlyAllowedRuleClassesWithWarning() throws Exception {
     setRulesAvailableInTests(
         (MockRule) () -> MockRule.define(
diff --git a/src/test/java/com/google/devtools/build/lib/analysis/ConfiguredAttributeMapperTest.java b/src/test/java/com/google/devtools/build/lib/analysis/ConfiguredAttributeMapperTest.java
index 15a90a87a1..f3014f20d0 100644
--- a/src/test/java/com/google/devtools/build/lib/analysis/ConfiguredAttributeMapperTest.java
+++ b/src/test/java/com/google/devtools/build/lib/analysis/ConfiguredAttributeMapperTest.java
@@ -19,13 +19,13 @@ import com.google.common.collect.ImmutableMap;
 import com.google.devtools.build.lib.analysis.config.CompilationMode;
 import com.google.devtools.build.lib.analysis.util.BuildViewTestCase;
 import com.google.devtools.build.lib.cmdline.Label;
-import com.google.devtools.build.lib.packages.Attribute;
 import com.google.devtools.build.lib.packages.AttributeMap;
 import com.google.devtools.build.lib.packages.BuildType;
 import com.google.devtools.build.lib.packages.ConfiguredAttributeMapper;
 import com.google.devtools.build.lib.skyframe.ConfiguredTargetAndData;
 import com.google.devtools.build.lib.syntax.Type;
 import java.util.ArrayList;
+import java.util.Collection;
 import java.util.List;
 import org.junit.Test;
 import org.junit.runner.RunWith;
@@ -114,37 +114,36 @@ public class ConfiguredAttributeMapperTest extends BuildViewTestCase {
         "    name = 'defaultdep',",
         "    srcs = ['defaultdep.sh'])");
 
-    final List<Label> visitedLabels = new ArrayList<>();
-    AttributeMap.AcceptsLabelAttribute testVisitor =
-        new AttributeMap.AcceptsLabelAttribute() {
-          @Override
-          public void acceptLabelAttribute(Label label, Attribute attribute) {
-            if (label.toString().contains("//a:")) { // Ignore implicit common dependencies.
-              visitedLabels.add(label);
-            }
-          }
-        };
-
-    final Label binSrc = Label.parseAbsolute("//a:bin.sh", ImmutableMap.of());
+    List<Label> visitedLabels = new ArrayList<>();
+    Label binSrc = Label.parseAbsolute("//a:bin.sh", ImmutableMap.of());
 
     useConfiguration("--define", "mode=a");
-    getMapper("//a:bin").visitLabels(testVisitor);
+    addRelevantLabels(getMapper("//a:bin").visitLabels(), visitedLabels);
     assertThat(visitedLabels)
         .containsExactly(binSrc, Label.parseAbsolute("//a:adep", ImmutableMap.of()));
 
     visitedLabels.clear();
     useConfiguration("--define", "mode=b");
-    getMapper("//a:bin").visitLabels(testVisitor);
+    addRelevantLabels(getMapper("//a:bin").visitLabels(), visitedLabels);
     assertThat(visitedLabels)
         .containsExactly(binSrc, Label.parseAbsolute("//a:bdep", ImmutableMap.of()));
 
     visitedLabels.clear();
     useConfiguration("--define", "mode=c");
-    getMapper("//a:bin").visitLabels(testVisitor);
+    addRelevantLabels(getMapper("//a:bin").visitLabels(), visitedLabels);
     assertThat(visitedLabels)
         .containsExactly(binSrc, Label.parseAbsolute("//a:defaultdep", ImmutableMap.of()));
   }
 
+  private static void addRelevantLabels(
+      Collection<AttributeMap.DepEdge> depEdges, Collection<Label> visitedLabels) {
+    depEdges
+        .stream()
+        .map(AttributeMap.DepEdge::getLabel)
+        .filter((label) -> label.getPackageIdentifier().getPackageFragment().toString().equals("a"))
+        .forEach(visitedLabels::add);
+  }
+
   /**
    * Tests that for configurable attributes where the *values* are evaluated in different
    * configurations, the configuration checking still uses the original configuration.
diff --git a/src/test/java/com/google/devtools/build/lib/analysis/DependencyResolverTest.java b/src/test/java/com/google/devtools/build/lib/analysis/DependencyResolverTest.java
index 26005cfc3d..4ee313c221 100644
--- a/src/test/java/com/google/devtools/build/lib/analysis/DependencyResolverTest.java
+++ b/src/test/java/com/google/devtools/build/lib/analysis/DependencyResolverTest.java
@@ -18,6 +18,7 @@ import static com.google.common.truth.Truth.assertWithMessage;
 
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.Streams;
 import com.google.devtools.build.lib.analysis.config.BuildConfiguration;
 import com.google.devtools.build.lib.analysis.config.BuildOptions;
 import com.google.devtools.build.lib.analysis.config.ConfigMatchingProvider;
@@ -40,6 +41,9 @@ import com.google.devtools.build.lib.testutil.Suite;
 import com.google.devtools.build.lib.testutil.TestSpec;
 import com.google.devtools.build.lib.util.OrderedSetMultimap;
 import java.util.List;
+import java.util.Map;
+import java.util.function.Function;
+import java.util.stream.Collectors;
 import javax.annotation.Nullable;
 import org.junit.Before;
 import org.junit.Test;
@@ -80,14 +84,26 @@ public class DependencyResolverTest extends AnalysisTestCase {
             throw new IllegalStateException(e);
           }
 
-          @Nullable
           @Override
-          protected Target getTarget(Target from, Label label, NestedSetBuilder<Cause> rootCauses) {
-            try {
-              return packageManager.getTarget(reporter, label);
-            } catch (NoSuchPackageException | NoSuchTargetException | InterruptedException e) {
-              throw new IllegalStateException(e);
-            }
+          protected Map<Label, Target> getTargets(
+              Iterable<Label> labels,
+              Target fromTarget,
+              NestedSetBuilder<Cause> rootCauses,
+              int labelsSizeHint) {
+            return Streams.stream(labels)
+                .distinct()
+                .collect(
+                    Collectors.toMap(
+                        Function.identity(),
+                        label -> {
+                          try {
+                            return packageManager.getTarget(reporter, label);
+                          } catch (NoSuchPackageException
+                              | NoSuchTargetException
+                              | InterruptedException e) {
+                            throw new IllegalStateException(e);
+                          }
+                        }));
           }
 
           @Nullable
diff --git a/src/test/java/com/google/devtools/build/lib/analysis/select/AbstractAttributeMapperTest.java b/src/test/java/com/google/devtools/build/lib/analysis/select/AbstractAttributeMapperTest.java
index ac89f9f0eb..4901884590 100644
--- a/src/test/java/com/google/devtools/build/lib/analysis/select/AbstractAttributeMapperTest.java
+++ b/src/test/java/com/google/devtools/build/lib/analysis/select/AbstractAttributeMapperTest.java
@@ -16,7 +16,6 @@ package com.google.devtools.build.lib.analysis.select;
 import static com.google.common.truth.Truth.assertThat;
 import static org.junit.Assert.fail;
 
-import com.google.common.collect.Lists;
 import com.google.devtools.build.lib.analysis.util.BuildViewTestCase;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.packages.AbstractAttributeMapper;
@@ -29,6 +28,7 @@ import com.google.devtools.build.lib.packages.Rule;
 import com.google.devtools.build.lib.packages.RuleClass;
 import com.google.devtools.build.lib.syntax.Type;
 import java.util.List;
+import java.util.stream.Collectors;
 import org.junit.Before;
 import org.junit.Test;
 import org.junit.runner.RunWith;
@@ -116,27 +116,20 @@ public class AbstractAttributeMapperTest extends BuildViewTestCase {
     assertThat(mapper.isAttributeValueExplicitlySpecified("nonsense")).isFalse();
   }
 
-  protected static class VisitationRecorder implements AttributeMap.AcceptsLabelAttribute {
-    public List<String> labelsVisited = Lists.newArrayList();
-    private final String attrName;
-
-    public VisitationRecorder(String attrName) {
-      this.attrName = attrName;
-    }
-
-    @Override
-    public void acceptLabelAttribute(Label label, Attribute attribute) {
-      if (attribute.getName().equals(attrName)) {
-        labelsVisited.add(label.toString());
-      }
-    }
-  }
-
   @Test
   public void testVisitation() throws Exception {
-    VisitationRecorder recorder = new VisitationRecorder("srcs");
-    mapper.visitLabels(recorder);
-    assertThat(recorder.labelsVisited).containsExactly("//p:a", "//p:b", "//p:c");
+    assertThat(getLabelsForAttribute(mapper, "srcs")).containsExactly("//p:a", "//p:b", "//p:c");
+  }
+
+  protected static List<String> getLabelsForAttribute(
+      AttributeMap attributeMap, String attributeName) throws InterruptedException {
+    return attributeMap
+        .visitLabels()
+        .stream()
+        .filter((d) -> d.getAttribute().getName().equals(attributeName))
+        .map(AttributeMap.DepEdge::getLabel)
+        .map(Label::toString)
+        .collect(Collectors.toList());
   }
 
   @Test
diff --git a/src/test/java/com/google/devtools/build/lib/analysis/select/AggregatingAttributeMapperTest.java b/src/test/java/com/google/devtools/build/lib/analysis/select/AggregatingAttributeMapperTest.java
index a8f912602c..073c751766 100644
--- a/src/test/java/com/google/devtools/build/lib/analysis/select/AggregatingAttributeMapperTest.java
+++ b/src/test/java/com/google/devtools/build/lib/analysis/select/AggregatingAttributeMapperTest.java
@@ -146,9 +146,7 @@ public class AggregatingAttributeMapperTest extends AbstractAttributeMapperTest
         "              '" + BuildType.Selector.DEFAULT_CONDITION_KEY + "': ['default.sh'],",
         "          }))");
 
-    VisitationRecorder recorder = new VisitationRecorder("srcs");
-    AggregatingAttributeMapper.of(rule).visitLabels(recorder);
-    assertThat(recorder.labelsVisited)
+    assertThat(getLabelsForAttribute(AggregatingAttributeMapper.of(rule), "srcs"))
         .containsExactlyElementsIn(
             ImmutableList.of(
                 "//a:a.sh", "//a:b.sh", "//a:default.sh", "//conditions:a", "//conditions:b"));
@@ -163,9 +161,7 @@ public class AggregatingAttributeMapperTest extends AbstractAttributeMapperTest
         "        '//conditions:a': None,",
         "    }))");
 
-    VisitationRecorder recorder = new VisitationRecorder("malloc");
-    AggregatingAttributeMapper.of(rule).visitLabels(recorder);
-    assertThat(recorder.labelsVisited)
+    assertThat(getLabelsForAttribute(AggregatingAttributeMapper.of(rule), "malloc"))
         .containsExactly("//conditions:a", getDefaultMallocLabel(rule).toString());
   }
 
diff --git a/src/test/java/com/google/devtools/build/lib/analysis/select/RawAttributeMapperTest.java b/src/test/java/com/google/devtools/build/lib/analysis/select/RawAttributeMapperTest.java
index e5f38cb650..2078904857 100644
--- a/src/test/java/com/google/devtools/build/lib/analysis/select/RawAttributeMapperTest.java
+++ b/src/test/java/com/google/devtools/build/lib/analysis/select/RawAttributeMapperTest.java
@@ -18,8 +18,6 @@ import static org.junit.Assert.fail;
 
 import com.google.common.collect.ImmutableMap;
 import com.google.devtools.build.lib.cmdline.Label;
-import com.google.devtools.build.lib.packages.Attribute;
-import com.google.devtools.build.lib.packages.AttributeMap;
 import com.google.devtools.build.lib.packages.BuildType;
 import com.google.devtools.build.lib.packages.RawAttributeMapper;
 import com.google.devtools.build.lib.packages.Rule;
@@ -97,12 +95,7 @@ public class RawAttributeMapperTest extends AbstractAttributeMapperTest {
   public void testVisitLabels() throws Exception {
     RawAttributeMapper rawMapper = RawAttributeMapper.of(setupGenRule());
     try {
-      rawMapper.visitLabels(new AttributeMap.AcceptsLabelAttribute() {
-        @Override
-        public void acceptLabelAttribute(Label label, Attribute attribute) {
-          // Nothing to do.
-        }
-      });
+      rawMapper.visitLabels();
       fail("Expected label visitation to fail since one attribute is configurable");
     } catch (IllegalArgumentException e) {
       assertThat(e)
diff --git a/src/test/java/com/google/devtools/build/lib/analysis/util/BuildViewForTesting.java b/src/test/java/com/google/devtools/build/lib/analysis/util/BuildViewForTesting.java
index 083688d02b..1f92bea669 100644
--- a/src/test/java/com/google/devtools/build/lib/analysis/util/BuildViewForTesting.java
+++ b/src/test/java/com/google/devtools/build/lib/analysis/util/BuildViewForTesting.java
@@ -22,6 +22,7 @@ import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableMultimap;
 import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.Iterables;
+import com.google.common.collect.Streams;
 import com.google.common.eventbus.EventBus;
 import com.google.devtools.build.lib.actions.ArtifactFactory;
 import com.google.devtools.build.lib.actions.PackageRoots;
@@ -90,6 +91,8 @@ import java.util.LinkedHashSet;
 import java.util.List;
 import java.util.Map;
 import java.util.Set;
+import java.util.function.Function;
+import java.util.stream.Collectors;
 
 /**
  * A util class that contains all the helper stuff previously in BuildView that only exists to give
@@ -310,13 +313,25 @@ public class BuildViewForTesting {
       }
 
       @Override
-      protected Target getTarget(Target from, Label label, NestedSetBuilder<Cause> rootCauses)
-          throws InterruptedException {
-        try {
-          return skyframeExecutor.getPackageManager().getTarget(eventHandler, label);
-        } catch (NoSuchThingException e) {
-          throw new IllegalStateException(e);
-        }
+      protected Map<Label, Target> getTargets(
+          Iterable<Label> labels,
+          Target fromTarget,
+          NestedSetBuilder<Cause> rootCauses,
+          int labelsSizeHint) {
+        return Streams.stream(labels)
+            .distinct()
+            .collect(
+                Collectors.toMap(
+                    Function.identity(),
+                    label -> {
+                      try {
+                        return skyframeExecutor.getPackageManager().getTarget(eventHandler, label);
+                      } catch (NoSuchPackageException
+                          | NoSuchTargetException
+                          | InterruptedException e) {
+                        throw new IllegalStateException(e);
+                      }
+                    }));
       }
 
       @Override