Add --implicit_deps custom filtering to configuredtargetqueryenvironment.

This implementation requires adding an interned list of LabelAndConfiguration objects to each RuleConfiguredTarget ('implicit' is an attribute describer, not a dep describer so filtering needs to happen while attribute information still exists).

PiperOrigin-RevId: 178411882

3 files changed, 128 insertions, 44 deletions

diff --git a/src/main/java/com/google/devtools/build/lib/analysis/Util.java b/src/main/java/com/google/devtools/build/lib/analysis/Util.java
index e40c3ea5ac..aa12b40463 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/Util.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/Util.java
@@ -14,9 +14,17 @@
 
 package com.google.devtools.build.lib.analysis;
 
+import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.ListMultimap;
+import com.google.common.collect.Sets;
+import com.google.devtools.build.lib.analysis.config.BuildConfiguration;
 import com.google.devtools.build.lib.cmdline.Label;
+import com.google.devtools.build.lib.collect.compacthashset.CompactHashSet;
+import com.google.devtools.build.lib.packages.AttributeMap;
 import com.google.devtools.build.lib.packages.Target;
 import com.google.devtools.build.lib.vfs.PathFragment;
+import java.util.List;
+import java.util.Set;
 
 /**
  * Utility methods for use by ConfiguredTarget implementations.
@@ -61,4 +69,49 @@ public abstract class Util {
   public static boolean containsHyphen(PathFragment path) {
     return path.getPathString().indexOf('-') >= 0;
   }
+
+  // ---------- Implicit dependency extractor
+
+  /*
+   * Given a RuleContext, find all the implicit deps aka deps that weren't explicitly set in the
+   * build file and all toolchain deps.
+   * note: nodes that are depended on both implicitly and explicitly are considered explicit.
+   */
+  public static ImmutableSet<LabelAndConfiguration> findImplicitDeps(RuleContext ruleContext) {
+    // (1) Consider rule attribute dependencies.
+    Set<LabelAndConfiguration> maybeImplicitDeps = CompactHashSet.create();
+    Set<LabelAndConfiguration> explicitDeps = CompactHashSet.create();
+    AttributeMap attributes = ruleContext.attributes();
+    ListMultimap<String, ? extends TransitiveInfoCollection> targetMap =
+        ruleContext.getConfiguredTargetMap();
+    for (String attrName : attributes.getAttributeNames()) {
+      List<? extends TransitiveInfoCollection> attrValues = targetMap.get(attrName);
+      if (attrValues != null && !attrValues.isEmpty()) {
+        if (attributes.isAttributeValueExplicitlySpecified(attrName)) {
+          addLabelsAndConfigs(explicitDeps, attrValues);
+        } else {
+          addLabelsAndConfigs(maybeImplicitDeps, attrValues);
+        }
+      }
+    }
+    // (2) Consider toolchain dependencies
+    ToolchainContext toolchainContext = ruleContext.getToolchainContext();
+    if (toolchainContext != null) {
+      BuildConfiguration config = ruleContext.getConfiguration();
+      for (Label toolchain : toolchainContext.getResolvedToolchainLabels()) {
+        maybeImplicitDeps.add(LabelAndConfiguration.of(toolchain, config));
+      }
+      maybeImplicitDeps.add(
+          LabelAndConfiguration.of(toolchainContext.getExecutionPlatform().label(), config));
+      maybeImplicitDeps.add(
+          LabelAndConfiguration.of(toolchainContext.getTargetPlatform().label(), config));
+    }
+    return ImmutableSet.copyOf(Sets.difference(maybeImplicitDeps, explicitDeps));
+  }
+
+  private static void addLabelsAndConfigs(
+      Set<LabelAndConfiguration> set, List<? extends TransitiveInfoCollection> deps) {
+    deps.forEach(
+        target -> set.add(LabelAndConfiguration.of(target.getLabel(), target.getConfiguration())));
+  }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/configuredtargets/RuleConfiguredTarget.java b/src/main/java/com/google/devtools/build/lib/analysis/configuredtargets/RuleConfiguredTarget.java
index 7a8a27e4b0..d95c4d31ac 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/configuredtargets/RuleConfiguredTarget.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/configuredtargets/RuleConfiguredTarget.java
@@ -15,19 +15,24 @@ package com.google.devtools.build.lib.analysis.configuredtargets;
 
 import com.google.common.base.Preconditions;
 import com.google.common.collect.ImmutableMap;
+import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.Interner;
 import com.google.devtools.build.lib.analysis.ConfiguredTarget;
 import com.google.devtools.build.lib.analysis.FileProvider;
 import com.google.devtools.build.lib.analysis.FilesToRunProvider;
+import com.google.devtools.build.lib.analysis.LabelAndConfiguration;
 import com.google.devtools.build.lib.analysis.RuleConfiguredTargetBuilder;
 import com.google.devtools.build.lib.analysis.RuleContext;
 import com.google.devtools.build.lib.analysis.RunfilesProvider;
 import com.google.devtools.build.lib.analysis.TransitiveInfoProvider;
 import com.google.devtools.build.lib.analysis.TransitiveInfoProviderMap;
 import com.google.devtools.build.lib.analysis.TransitiveInfoProviderMapBuilder;
+import com.google.devtools.build.lib.analysis.Util;
 import com.google.devtools.build.lib.analysis.config.ConfigMatchingProvider;
 import com.google.devtools.build.lib.analysis.config.RunUnder;
 import com.google.devtools.build.lib.analysis.skylark.SkylarkApiProvider;
 import com.google.devtools.build.lib.cmdline.Label;
+import com.google.devtools.build.lib.concurrent.BlazeInterners;
 import com.google.devtools.build.lib.packages.ConfiguredAttributeMapper;
 import com.google.devtools.build.lib.packages.Info;
 import com.google.devtools.build.lib.packages.OutputFile;
@@ -57,6 +62,16 @@ public final class RuleConfiguredTarget extends AbstractConfiguredTarget {
     SPLIT,
     DONT_CHECK
   }
+  /** A set of this target's implicitDeps. */
+  private final ImmutableSet<LabelAndConfiguration> implicitDeps;
+
+  /*
+   * An interner for the implicitDeps set. {@link Util.findImplicitDeps} is called upon every
+   * construction of a RuleConfiguredTarget and we expect many of these targets to contain the same
+   * set of implicit deps so this reduces the memory load per build.
+   */
+  private static final Interner<ImmutableSet<LabelAndConfiguration>> IMPLICIT_DEPS_INTERNER =
+      BlazeInterners.newWeakInterner();
 
   private final TransitiveInfoProviderMap providers;
   private final ImmutableMap<Label, ConfigMatchingProvider> configConditions;
@@ -79,9 +94,9 @@ public final class RuleConfiguredTarget extends AbstractConfiguredTarget {
       }
     }
 
-
     this.providers = providerBuilder.build();
     this.configConditions = ruleContext.getConfigConditions();
+    this.implicitDeps = IMPLICIT_DEPS_INTERNER.intern(Util.findImplicitDeps(ruleContext));
 
     // If this rule is the run_under target, then check that we have an executable; note that
     // run_under is only set in the target configuration, and the target must also be analyzed for
@@ -109,6 +124,10 @@ public final class RuleConfiguredTarget extends AbstractConfiguredTarget {
     return configConditions;
   }
 
+  public ImmutableSet<LabelAndConfiguration> getImplicitDeps() {
+    return implicitDeps;
+  }
+
   @Nullable
   @Override
   public <P extends TransitiveInfoProvider> P getProvider(Class<P> providerClass) {
diff --git a/src/main/java/com/google/devtools/build/lib/query2/ConfiguredTargetQueryEnvironment.java b/src/main/java/com/google/devtools/build/lib/query2/ConfiguredTargetQueryEnvironment.java
index def3b9d4f3..73e253ec37 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/ConfiguredTargetQueryEnvironment.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/ConfiguredTargetQueryEnvironment.java
@@ -81,10 +81,6 @@ import javax.annotation.Nullable;
 /**
  * {@link QueryEnvironment} that runs queries over the configured target (analysis) graph.
  *
- * <p>Currently no edges are filtered out, in contrast to query as implemented on the target graph
- * (host_deps and implicit_deps are important ones). Because of the higher fidelity that users of
- * the configured target graph presumably want, this may be ok, but also may not be.
- *
  * <p>This object can theoretically be used for multiple queries, but currently is only ever used
  * for one over the course of its lifetime.
  *
@@ -165,10 +161,11 @@ public class ConfiguredTargetQueryEnvironment
 
   // Check to make sure the settings requested are currently supported by this class
   private void checkSettings(Set<Setting> settings) throws QueryException {
-    if (settings.contains(Setting.NO_HOST_DEPS)) {
-      settings = Sets.difference(settings, ImmutableSet.of(Setting.NO_HOST_DEPS));
-    }
-    if (!settings.isEmpty()) {
+    if (settings.contains(Setting.NO_NODEP_DEPS)
+        || settings.contains(Setting.TESTS_EXPRESSION_STRICT)) {
+      settings =
+          Sets.difference(
+              settings, ImmutableSet.of(Setting.NO_HOST_DEPS, Setting.NO_IMPLICIT_DEPS));
       throw new QueryException(
           String.format(
               "The following filter(s) are not currently supported by configured query: %s",
@@ -279,37 +276,51 @@ public class ConfiguredTargetQueryEnvironment
     if (!(configTarget instanceof RuleConfiguredTarget) || settings.isEmpty()) {
       return rawFwdDeps;
     }
-    return getAllowedDeps(configTarget.getConfiguration(), rawFwdDeps);
+    return getAllowedDeps(configTarget, rawFwdDeps);
   }
 
   /**
-   * Note: We should check which settings to filter on here but not doing that since we currently
-   * only support one setting (NO_HOST_DEPS) and should've already thrown an error by now if it's
-   * any other filter.
-   *
-   * @param currentConfig: the config of the source target. It's possible to query on a target
-   *     that's configured in the host configuration. In those cases, if --nohost_deps is turned on,
-   *     we only allow reachable targets that are ALSO in the host config. This is somewhat
-   *     counterintuitive and subject to change in the future but seems like the best option right
-   *     now.
-   * @param rawDeps: the next level of deps to filter
+   * @param target source target
+   * @param deps next level of deps to filter
    */
   private Collection<ConfiguredTarget> getAllowedDeps(
-      BuildConfiguration currentConfig, Collection<ConfiguredTarget> rawDeps) {
-    if (currentConfig != null && currentConfig.isHostConfiguration()) {
-      return rawDeps
-          .stream()
-          .filter(
-              dep -> dep.getConfiguration() != null && dep.getConfiguration().isHostConfiguration())
-          .collect(Collectors.toList());
-    } else {
-      return rawDeps
-          .stream()
-          .filter(
-              dep ->
-                  dep.getConfiguration() == null || !dep.getConfiguration().isHostConfiguration())
-          .collect(Collectors.toList());
+      ConfiguredTarget target, Collection<ConfiguredTarget> deps) {
+    // It's possible to query on a target that's configured in the host configuration. In those
+    // cases if --nohost_deps is turned on, we only allow reachable targets that are ALSO in the
+    // host config. This is somewhat counterintuitive and subject to change in the future but seems
+    // like the best option right now.
+    if (settings.contains(Setting.NO_HOST_DEPS)) {
+      BuildConfiguration currentConfig = target.getConfiguration();
+      if (currentConfig != null && currentConfig.isHostConfiguration()) {
+        deps =
+            deps.stream()
+                .filter(
+                    dep ->
+                        dep.getConfiguration() != null
+                            && dep.getConfiguration().isHostConfiguration())
+                .collect(Collectors.toList());
+      } else {
+        deps =
+            deps.stream()
+                .filter(
+                    dep ->
+                        dep.getConfiguration() == null
+                            || !dep.getConfiguration().isHostConfiguration())
+                .collect(Collectors.toList());
+      }
+    }
+    if (settings.contains(Setting.NO_IMPLICIT_DEPS) && target instanceof RuleConfiguredTarget) {
+      Set<LabelAndConfiguration> implicitDeps = ((RuleConfiguredTarget) target).getImplicitDeps();
+      deps =
+          deps.stream()
+              .filter(
+                  dep ->
+                      !implicitDeps.contains(
+                          LabelAndConfiguration.of(
+                              dep.getTarget().getLabel(), dep.getConfiguration())))
+              .collect(Collectors.toList());
     }
+    return deps;
   }
 
   @Override
@@ -337,9 +348,9 @@ public class ConfiguredTargetQueryEnvironment
   }
 
   private Collection<ConfiguredTarget> filterReverseDeps(
-      Map<SkyKey, Collection<ConfiguredTarget>> rawReverseDeps) {
+      Map<ConfiguredTarget, Collection<ConfiguredTarget>> rawReverseDeps) {
     Set<ConfiguredTarget> result = CompactHashSet.create();
-    for (Map.Entry<SkyKey, Collection<ConfiguredTarget>> targetAndRdeps :
+    for (Map.Entry<ConfiguredTarget, Collection<ConfiguredTarget>> targetAndRdeps :
         rawReverseDeps.entrySet()) {
       ImmutableSet.Builder<ConfiguredTarget> ruleDeps = ImmutableSet.builder();
       for (ConfiguredTarget parent : targetAndRdeps.getValue()) {
@@ -350,10 +361,7 @@ public class ConfiguredTargetQueryEnvironment
           result.add(parent);
         }
       }
-      result.addAll(
-          getAllowedDeps(
-              ((ConfiguredTargetKey) targetAndRdeps.getKey().argument()).getConfiguration(),
-              ruleDeps.build()));
+      result.addAll(getAllowedDeps((targetAndRdeps.getKey()), ruleDeps.build()));
     }
     return result;
   }
@@ -365,17 +373,21 @@ public class ConfiguredTargetQueryEnvironment
     for (ConfiguredTarget target : targets) {
       targetsByKey.put(CT_TO_SKYKEY.apply(target), target);
     }
-    Map<SkyKey, Collection<ConfiguredTarget>> reverseDeps =
+    Map<SkyKey, Collection<ConfiguredTarget>> reverseDepsByKey =
         targetifyValues(graph.getReverseDeps(targetsByKey.keySet()));
-    if (targetsByKey.keySet().size() != reverseDeps.keySet().size()) {
+    if (targetsByKey.size() != reverseDepsByKey.size()) {
       Iterable<LabelAndConfiguration> missingTargets =
-          Sets.difference(targetsByKey.keySet(), reverseDeps.keySet())
+          Sets.difference(targetsByKey.keySet(), reverseDepsByKey.keySet())
               .stream()
               .map(SKYKEY_TO_LANDC)
               .collect(Collectors.toList());
       eventHandler.handle(Event.warn("Targets were missing from graph: " + missingTargets));
     }
-    return reverseDeps.isEmpty() ? Collections.emptyList() : filterReverseDeps(reverseDeps);
+    Map<ConfiguredTarget, Collection<ConfiguredTarget>> reverseDepsByCT = new HashMap<>();
+    for (Map.Entry<SkyKey, Collection<ConfiguredTarget>> entry : reverseDepsByKey.entrySet()) {
+      reverseDepsByCT.put(targetsByKey.get(entry.getKey()), entry.getValue());
+    }
+    return reverseDepsByCT.isEmpty() ? Collections.emptyList() : filterReverseDeps(reverseDepsByCT);
   }
 
   @Override