diff --git a/src/main/java/com/google/devtools/build/lib/analysis/constraints/ConstraintSemantics.java b/src/main/java/com/google/devtools/build/lib/analysis/constraints/ConstraintSemantics.java
index 233a8f3..5719f52 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/constraints/ConstraintSemantics.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/constraints/ConstraintSemantics.java
@@ -27,6 +27,7 @@
 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.EnvironmentGroup;
 import com.google.devtools.build.lib.packages.Rule;
 import com.google.devtools.build.lib.packages.RuleClass;
@@ -529,7 +530,7 @@
             || attr.equals("visibility")
             // Use the same implicit deps check that query uses. This facilitates running queries to
             // determine exactly which rules need to be constraint-annotated for depot migrations.
-            || !Rule.NO_IMPLICIT_DEPS.apply(ruleContext.getRule(), attrDef)
+            || !DependencyFilter.NO_IMPLICIT_DEPS.apply(ruleContext.getRule(), attrDef)
             // We can't identify host deps by calling BuildConfiguration.isHostConfiguration()
             // because --nodistinct_host_configuration subverts that call.
             || attrDef.getConfigurationTransition() == Attribute.ConfigurationTransition.HOST) {
diff --git a/src/main/java/com/google/devtools/build/lib/packages/AspectDefinition.java b/src/main/java/com/google/devtools/build/lib/packages/AspectDefinition.java
index 3e7bf76..43704f2 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/AspectDefinition.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/AspectDefinition.java
@@ -24,7 +24,6 @@
 import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
 import com.google.devtools.build.lib.packages.ConfigurationFragmentPolicy.MissingFragmentPolicy;
 import com.google.devtools.build.lib.packages.NativeAspectClass.NativeAspectFactory;
-import com.google.devtools.build.lib.util.BinaryPredicate;
 import com.google.devtools.build.lib.util.Preconditions;
 
 import java.util.Collection;
@@ -168,7 +167,8 @@
           candidateClass.getDefinition().getRequiredProviderNames())) {
         continue;
       }
-      addAllAttributesOfAspect(from, result, candidateClass.getDefinition(), Rule.ALL_DEPS);
+      addAllAttributesOfAspect(
+          from, result, candidateClass.getDefinition(), DependencyFilter.ALL_DEPS);
     }
     return ImmutableMultimap.copyOf(result);
   }
@@ -184,9 +184,11 @@
   /**
    * Collects all attribute labels from the specified aspectDefinition.
    */
-  public static void addAllAttributesOfAspect(Rule from,
-      Multimap<Attribute, Label> labelBuilder, AspectDefinition aspectDefinition,
-      BinaryPredicate<Rule, Attribute> predicate) {
+  public static void addAllAttributesOfAspect(
+      Rule from,
+      Multimap<Attribute, Label> labelBuilder,
+      AspectDefinition aspectDefinition,
+      DependencyFilter predicate) {
     ImmutableMap<String, Attribute> attributes = aspectDefinition.getAttributes();
     for (Attribute aspectAttribute : attributes.values()) {
       if (!predicate.apply(from, aspectAttribute)) {
diff --git a/src/main/java/com/google/devtools/build/lib/packages/DependencyFilter.java b/src/main/java/com/google/devtools/build/lib/packages/DependencyFilter.java
new file mode 100644
index 0000000..6d1b943d
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/packages/DependencyFilter.java
@@ -0,0 +1,96 @@
+// Copyright 2016 The Bazel Authors. 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.packages;
+
+import com.google.devtools.build.lib.packages.Attribute.ConfigurationTransition;
+import com.google.devtools.build.lib.util.BinaryPredicate;
+
+/**
+ * A predicate that returns true if an dependency attribute should be included in the result of
+ * <code>blaze query</code>.
+ * Used to implement  <code>--[no]implicit_deps</code>, <code>--[no]host_deps</code> etc.
+ */
+public abstract class DependencyFilter implements BinaryPredicate<Rule, Attribute> {
+
+  /** Dependency predicate that includes all dependencies */
+  public static final DependencyFilter ALL_DEPS =
+      new DependencyFilter() {
+        @Override
+        public boolean apply(Rule x, Attribute y) {
+          return true;
+        }
+      };
+  /** Dependency predicate that excludes host dependencies */
+  public static final DependencyFilter NO_HOST_DEPS =
+      new DependencyFilter() {
+    @Override
+    public boolean apply(Rule rule, Attribute attribute) {
+      // isHostConfiguration() is only defined for labels and label lists.
+      if (attribute.getType() != BuildType.LABEL && attribute.getType() != BuildType.LABEL_LIST) {
+        return true;
+      }
+
+      return attribute.getConfigurationTransition() != ConfigurationTransition.HOST;
+    }
+  };
+  /** Dependency predicate that excludes implicit dependencies */
+  public static final DependencyFilter NO_IMPLICIT_DEPS =
+      new DependencyFilter() {
+    @Override
+    public boolean apply(Rule rule, Attribute attribute) {
+      return rule.isAttributeValueExplicitlySpecified(attribute);
+    }
+  };
+  /**
+   * Dependency predicate that excludes those edges that are not present in
+   * the loading phase target dependency graph.
+   */
+  public static final DependencyFilter NO_NODEP_ATTRIBUTES =
+      new DependencyFilter() {
+    @Override
+    public boolean apply(Rule rule, Attribute attribute) {
+      return attribute.getType() != BuildType.NODEP_LABEL
+          && attribute.getType() != BuildType.NODEP_LABEL_LIST;
+    }
+  };
+  /**
+   * Checks to see if the attribute has the isDirectCompileTimeInput property.
+   */
+  public static final DependencyFilter DIRECT_COMPILE_TIME_INPUT =
+      new DependencyFilter() {
+    @Override
+    public boolean apply(Rule rule, Attribute attribute) {
+      return attribute.isDirectCompileTimeInput();
+    }
+  };
+
+  /**
+   * Returns true if a given attribute should be processed.
+   */
+  @Override
+  public abstract boolean apply(Rule rule, Attribute attribute);
+
+  /**
+   * Returns a predicate that computes the logical and of the two given predicates.
+   */
+  public static DependencyFilter and(
+      final DependencyFilter a, final DependencyFilter b) {
+    return new DependencyFilter() {
+      @Override
+      public boolean apply(Rule rule, Attribute attribute) {
+        return a.apply(rule, attribute) && b.apply(rule, attribute);
+      }
+    };
+  }
+}
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 ff16662..c18d763 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
@@ -31,12 +31,10 @@
 import com.google.devtools.build.lib.events.Event;
 import com.google.devtools.build.lib.events.EventHandler;
 import com.google.devtools.build.lib.events.Location;
-import com.google.devtools.build.lib.packages.Attribute.ConfigurationTransition;
 import com.google.devtools.build.lib.packages.License.DistributionType;
 import com.google.devtools.build.lib.syntax.EvalException;
 import com.google.devtools.build.lib.syntax.GlobList;
 import com.google.devtools.build.lib.syntax.Type;
-import com.google.devtools.build.lib.util.BinaryPredicate;
 import com.google.devtools.build.lib.util.Preconditions;
 
 import java.util.Collection;
@@ -61,78 +59,10 @@
  * </pre>
  */
 public final class Rule implements Target {
-  /** Dependency predicate that includes all dependencies */
-  public static final BinaryPredicate<Rule, Attribute> ALL_DEPS =
-      new BinaryPredicate<Rule, Attribute>() {
-        @Override
-        public boolean apply(Rule x, Attribute y) {
-          return true;
-        }
-      };
-
-  /** Dependency predicate that excludes host dependencies */
-  public static final BinaryPredicate<Rule, Attribute> NO_HOST_DEPS =
-      new BinaryPredicate<Rule, Attribute>() {
-    @Override
-    public boolean apply(Rule rule, Attribute attribute) {
-      // isHostConfiguration() is only defined for labels and label lists.
-      if (attribute.getType() != BuildType.LABEL && attribute.getType() != BuildType.LABEL_LIST) {
-        return true;
-      }
-
-      return attribute.getConfigurationTransition() != ConfigurationTransition.HOST;
-    }
-  };
-
-  /** Dependency predicate that excludes implicit dependencies */
-  public static final BinaryPredicate<Rule, Attribute> NO_IMPLICIT_DEPS =
-      new BinaryPredicate<Rule, Attribute>() {
-    @Override
-    public boolean apply(Rule rule, Attribute attribute) {
-      return rule.isAttributeValueExplicitlySpecified(attribute);
-    }
-  };
-
-  /**
-   * Dependency predicate that excludes those edges that are not present in the
-   * configured target graph.
-   */
-  public static final BinaryPredicate<Rule, Attribute> NO_NODEP_ATTRIBUTES =
-      new BinaryPredicate<Rule, Attribute>() {
-    @Override
-    public boolean apply(Rule rule, Attribute attribute) {
-      return attribute.getType() != BuildType.NODEP_LABEL
-          && attribute.getType() != BuildType.NODEP_LABEL_LIST;
-    }
-  };
 
   /** Label predicate that allows every label. */
   public static final Predicate<Label> ALL_LABELS = Predicates.alwaysTrue();
 
-  /**
-   * Checks to see if the attribute has the isDirectCompileTimeInput property.
-   */
-  public static final BinaryPredicate<Rule, Attribute> DIRECT_COMPILE_TIME_INPUT =
-      new BinaryPredicate<Rule, Attribute>() {
-    @Override
-    public boolean apply(Rule rule, Attribute attribute) {
-      return attribute.isDirectCompileTimeInput();
-    }
-  };
-
-  /**
-   * Returns a predicate that computes the logical and of the two given predicates.
-   */
-  public static <X, Y> BinaryPredicate<X, Y> and(
-      final BinaryPredicate<X, Y> a, final BinaryPredicate<X, Y> b) {
-    return new BinaryPredicate<X, Y>() {
-      @Override
-      public boolean apply(X x, Y y) {
-        return a.apply(x, y) && b.apply(x, y);
-      }
-    };
-  }
-
   private final Label label;
 
   private final Package pkg;
@@ -457,7 +387,7 @@
    * Returns a new List instance containing all direct dependencies (all types).
    */
   public Collection<Label> getLabels() {
-    return getLabels(Rule.ALL_DEPS);
+    return getLabels(DependencyFilter.ALL_DEPS);
   }
 
   /**
@@ -469,7 +399,7 @@
    *     the attribute that contains the label. The label will be contained in the
    *     result iff (the predicate returned {@code true} and the labels are not outputs)
    */
-  public Collection<Label> getLabels(final BinaryPredicate<Rule, Attribute> predicate) {
+  public Collection<Label> getLabels(DependencyFilter predicate) {
     return ImmutableSortedSet.copyOf(getTransitions(predicate).values());
   }
 
@@ -482,8 +412,7 @@
    *     the attribute that contains the label. The label will be contained in the
    *     result iff (the predicate returned {@code true} and the labels are not outputs)
    */
-  public Multimap<Attribute, Label> getTransitions(
-      final BinaryPredicate<Rule, Attribute> predicate) {
+  public Multimap<Attribute, Label> getTransitions(final DependencyFilter predicate) {
     final Multimap<Attribute, Label> transitions = HashMultimap.create();
     // 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
@@ -733,8 +662,7 @@
    * Computes labels of additional dependencies that can be provided by aspects that this rule
    * can require from its direct dependencies.
    */
-  public Collection<? extends Label> getAspectLabelsSuperset(
-      BinaryPredicate<Rule, Attribute> predicate) {
+  public Collection<? extends Label> getAspectLabelsSuperset(DependencyFilter predicate) {
     LinkedHashMultimap<Attribute, Label> labels = LinkedHashMultimap.create();
     for (Attribute attribute : this.getAttributes()) {
       for (Aspect candidateClass : attribute.getAspects(this)) {
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
index b6389e2..48fff56 100644
--- a/src/main/java/com/google/devtools/build/lib/pkgcache/CompileOneDependencyTransformer.java
+++ b/src/main/java/com/google/devtools/build/lib/pkgcache/CompileOneDependencyTransformer.java
@@ -20,6 +20,7 @@
 import com.google.devtools.build.lib.events.EventHandler;
 import com.google.devtools.build.lib.packages.Attribute;
 import com.google.devtools.build.lib.packages.BuildType;
+import com.google.devtools.build.lib.packages.DependencyFilter;
 import com.google.devtools.build.lib.packages.FileTarget;
 import com.google.devtools.build.lib.packages.NoSuchThingException;
 import com.google.devtools.build.lib.packages.Package;
@@ -27,7 +28,6 @@
 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.util.BinaryPredicate;
 
 import java.util.Collections;
 import java.util.Comparator;
@@ -117,11 +117,11 @@
 
     // For each rule, see if it has directCompileTimeInputAttribute,
     // and if so check the targets listed in that attribute match the label.
-    final BinaryPredicate<Rule, Attribute> directCompileTimeInput =
-        new BinaryPredicate<Rule, Attribute>() {
+    DependencyFilter directCompileTimeInput =
+        new DependencyFilter() {
           @Override
           public boolean apply(Rule rule, Attribute attribute) {
-            return Rule.DIRECT_COMPILE_TIME_INPUT.apply(rule, attribute)
+            return DependencyFilter.DIRECT_COMPILE_TIME_INPUT.apply(rule, attribute)
                 // We don't know which path to follow for configurable attributes, so skip them.
                 && !rule.isConfigurableAttribute(attribute.getName());
           }
diff --git a/src/main/java/com/google/devtools/build/lib/query2/AbstractBlazeQueryEnvironment.java b/src/main/java/com/google/devtools/build/lib/query2/AbstractBlazeQueryEnvironment.java
index 004adec..348ce70 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/AbstractBlazeQueryEnvironment.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/AbstractBlazeQueryEnvironment.java
@@ -22,7 +22,7 @@
 import com.google.devtools.build.lib.events.ErrorSensingEventHandler;
 import com.google.devtools.build.lib.events.Event;
 import com.google.devtools.build.lib.events.EventHandler;
-import com.google.devtools.build.lib.packages.Attribute;
+import com.google.devtools.build.lib.packages.DependencyFilter;
 import com.google.devtools.build.lib.packages.Rule;
 import com.google.devtools.build.lib.packages.Target;
 import com.google.devtools.build.lib.pkgcache.PackageProvider;
@@ -36,7 +36,6 @@
 import com.google.devtools.build.lib.query2.engine.QueryException;
 import com.google.devtools.build.lib.query2.engine.QueryExpression;
 import com.google.devtools.build.lib.query2.engine.QueryUtil.AggregateAllCallback;
-import com.google.devtools.build.lib.util.BinaryPredicate;
 import com.google.devtools.build.lib.util.Preconditions;
 import com.google.devtools.build.skyframe.WalkableGraph.WalkableGraphFactory;
 
@@ -61,7 +60,7 @@
   protected final boolean keepGoing;
   protected final boolean strictScope;
 
-  protected final BinaryPredicate<Rule, Attribute> dependencyFilter;
+  protected final DependencyFilter dependencyFilter;
   private final Predicate<Label> labelFilter;
 
   private final Set<Setting> settings;
@@ -84,14 +83,16 @@
     this.extraFunctions = ImmutableList.copyOf(extraFunctions);
   }
 
-  private static BinaryPredicate<Rule, Attribute> constructDependencyFilter(Set<Setting> settings) {
-    BinaryPredicate<Rule, Attribute> specifiedFilter =
-        settings.contains(Setting.NO_HOST_DEPS) ? Rule.NO_HOST_DEPS : Rule.ALL_DEPS;
+  private static DependencyFilter constructDependencyFilter(Set<Setting> settings) {
+    DependencyFilter specifiedFilter =
+        settings.contains(Setting.NO_HOST_DEPS)
+            ? DependencyFilter.NO_HOST_DEPS
+            : DependencyFilter.ALL_DEPS;
     if (settings.contains(Setting.NO_IMPLICIT_DEPS)) {
-      specifiedFilter = Rule.and(specifiedFilter, Rule.NO_IMPLICIT_DEPS);
+      specifiedFilter = DependencyFilter.and(specifiedFilter, DependencyFilter.NO_IMPLICIT_DEPS);
     }
     if (settings.contains(Setting.NO_NODEP_DEPS)) {
-      specifiedFilter = Rule.and(specifiedFilter, Rule.NO_NODEP_ATTRIBUTES);
+      specifiedFilter = DependencyFilter.and(specifiedFilter, DependencyFilter.NO_NODEP_ATTRIBUTES);
     }
     return specifiedFilter;
   }
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 e5f78c1..1734977 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
@@ -31,6 +31,7 @@
 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;
 import com.google.devtools.build.lib.packages.NoSuchThingException;
 import com.google.devtools.build.lib.packages.OutputFile;
@@ -41,7 +42,6 @@
 import com.google.devtools.build.lib.packages.Target;
 import com.google.devtools.build.lib.pkgcache.PackageProvider;
 import com.google.devtools.build.lib.pkgcache.TargetEdgeObserver;
-import com.google.devtools.build.lib.util.BinaryPredicate;
 
 import java.util.Collection;
 import java.util.Map.Entry;
@@ -185,7 +185,7 @@
    * Life is not simple.
    */
   private final PackageProvider packageProvider;
-  private final BinaryPredicate<Rule, Attribute> edgeFilter;
+  private final DependencyFilter edgeFilter;
   private final SetMultimap<Package, Target> visitedMap =
       Multimaps.synchronizedSetMultimap(HashMultimap.<Package, Target>create());
   private final ConcurrentMap<Label, Integer> visitedTargets = new MapMaker().makeMap();
@@ -203,8 +203,7 @@
    * @param packageProvider how to resolve labels to targets.
    * @param edgeFilter which edges may be traversed.
    */
-  public LabelVisitor(PackageProvider packageProvider,
-                      BinaryPredicate<Rule, Attribute> edgeFilter) {
+  public LabelVisitor(PackageProvider packageProvider, DependencyFilter edgeFilter) {
     this.packageProvider = packageProvider;
     this.lastVisitation = new VisitationAttributes();
     this.edgeFilter = edgeFilter;
diff --git a/src/main/java/com/google/devtools/build/lib/query2/SkyQueryEnvironment.java b/src/main/java/com/google/devtools/build/lib/query2/SkyQueryEnvironment.java
index 927b4ec..363f5d5 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/SkyQueryEnvironment.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/SkyQueryEnvironment.java
@@ -35,6 +35,7 @@
 import com.google.devtools.build.lib.events.EventHandler;
 import com.google.devtools.build.lib.graph.Digraph;
 import com.google.devtools.build.lib.packages.BuildFileContainsErrorsException;
+import com.google.devtools.build.lib.packages.DependencyFilter;
 import com.google.devtools.build.lib.packages.NoSuchTargetException;
 import com.google.devtools.build.lib.packages.NoSuchThingException;
 import com.google.devtools.build.lib.packages.Package;
@@ -264,7 +265,7 @@
     for (Collection<Target> parentCollection : rawReverseDeps.values()) {
       for (Target parent : parentCollection) {
         if (visited.add(parent)) {
-          if (parent instanceof Rule && dependencyFilter != Rule.ALL_DEPS) {
+          if (parent instanceof Rule && dependencyFilter != DependencyFilter.ALL_DEPS) {
             for (Label label : getAllowedDeps((Rule) parent)) {
               if (keys.contains(label)) {
                 result.add(parent);
diff --git a/src/main/java/com/google/devtools/build/lib/query2/output/ConservativeAspectResolver.java b/src/main/java/com/google/devtools/build/lib/query2/output/ConservativeAspectResolver.java
index c71e372..47ed795 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/output/ConservativeAspectResolver.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/output/ConservativeAspectResolver.java
@@ -21,6 +21,7 @@
 import com.google.devtools.build.lib.packages.Aspect;
 import com.google.devtools.build.lib.packages.AspectDefinition;
 import com.google.devtools.build.lib.packages.Attribute;
+import com.google.devtools.build.lib.packages.DependencyFilter;
 import com.google.devtools.build.lib.packages.Rule;
 import com.google.devtools.build.lib.packages.Target;
 
@@ -44,7 +45,7 @@
     for (Attribute attribute : rule.getAttributes()) {
       for (Aspect aspect : attribute.getAspects(rule)) {
         AspectDefinition.addAllAttributesOfAspect(
-            rule, result, aspect.getDefinition(), Rule.ALL_DEPS);
+            rule, result, aspect.getDefinition(), DependencyFilter.ALL_DEPS);
       }
     }
 
diff --git a/src/main/java/com/google/devtools/build/lib/query2/output/OutputFormatter.java b/src/main/java/com/google/devtools/build/lib/query2/output/OutputFormatter.java
index c6e79e1..aa1b742 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/output/OutputFormatter.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/output/OutputFormatter.java
@@ -26,13 +26,13 @@
 import com.google.devtools.build.lib.graph.Node;
 import com.google.devtools.build.lib.packages.AggregatingAttributeMapper;
 import com.google.devtools.build.lib.packages.Attribute;
+import com.google.devtools.build.lib.packages.DependencyFilter;
 import com.google.devtools.build.lib.packages.Rule;
 import com.google.devtools.build.lib.packages.Target;
 import com.google.devtools.build.lib.query2.engine.OutputFormatterCallback;
 import com.google.devtools.build.lib.query2.output.QueryOptions.OrderOutput;
 import com.google.devtools.build.lib.syntax.EvalUtils;
 import com.google.devtools.build.lib.syntax.Printer;
-import com.google.devtools.build.lib.util.BinaryPredicate;
 import com.google.devtools.build.lib.util.Pair;
 import com.google.devtools.common.options.EnumConverter;
 
@@ -140,11 +140,13 @@
    * Given a set of query options, returns a BinaryPredicate suitable for
    * passing to {@link Rule#getLabels()}, {@link XmlOutputFormatter}, etc.
    */
-  public static BinaryPredicate<Rule, Attribute> getDependencyFilter(QueryOptions queryOptions) {
+  public static DependencyFilter getDependencyFilter(QueryOptions queryOptions) {
     // TODO(bazel-team): Optimize: and(ALL_DEPS, x) -> x, etc.
-    return Rule.and(
-          queryOptions.includeHostDeps ? Rule.ALL_DEPS : Rule.NO_HOST_DEPS,
-          queryOptions.includeImplicitDeps ? Rule.ALL_DEPS : Rule.NO_IMPLICIT_DEPS);
+    return DependencyFilter.and(
+        queryOptions.includeHostDeps ? DependencyFilter.ALL_DEPS : DependencyFilter.NO_HOST_DEPS,
+        queryOptions.includeImplicitDeps
+            ? DependencyFilter.ALL_DEPS
+            : DependencyFilter.NO_IMPLICIT_DEPS);
   }
 
   /**
diff --git a/src/main/java/com/google/devtools/build/lib/query2/output/PreciseAspectResolver.java b/src/main/java/com/google/devtools/build/lib/query2/output/PreciseAspectResolver.java
index 4da4f3a..7ec2884 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/output/PreciseAspectResolver.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/output/PreciseAspectResolver.java
@@ -23,13 +23,13 @@
 import com.google.devtools.build.lib.packages.Aspect;
 import com.google.devtools.build.lib.packages.AspectDefinition;
 import com.google.devtools.build.lib.packages.Attribute;
+import com.google.devtools.build.lib.packages.DependencyFilter;
 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.Rule;
 import com.google.devtools.build.lib.packages.Target;
 import com.google.devtools.build.lib.pkgcache.PackageProvider;
-import com.google.devtools.build.lib.util.BinaryPredicate;
 
 import java.util.LinkedHashSet;
 import java.util.Map.Entry;
@@ -58,7 +58,7 @@
     Multimap<Attribute, Label> result = LinkedListMultimap.create();
     if (target instanceof Rule) {
       Multimap<Attribute, Label> transitions =
-          ((Rule) target).getTransitions(Rule.NO_NODEP_ATTRIBUTES);
+          ((Rule) target).getTransitions(DependencyFilter.NO_NODEP_ATTRIBUTES);
       for (Entry<Attribute, Label> entry : transitions.entries()) {
         Target toTarget;
         try {
@@ -92,7 +92,7 @@
       Multimap<Attribute, Label> depsWithPossibleAspects =
           ((Rule) target)
               .getTransitions(
-                  new BinaryPredicate<Rule, Attribute>() {
+                  new DependencyFilter() {
                     @Override
                     public boolean apply(@Nullable Rule rule, Attribute attribute) {
                       for (Aspect aspectWithParameters : attribute.getAspects(rule)) {
diff --git a/src/main/java/com/google/devtools/build/lib/query2/output/ProtoOutputFormatter.java b/src/main/java/com/google/devtools/build/lib/query2/output/ProtoOutputFormatter.java
index abf1e08..84554af 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/output/ProtoOutputFormatter.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/output/ProtoOutputFormatter.java
@@ -28,6 +28,7 @@
 import com.google.devtools.build.lib.packages.Attribute;
 import com.google.devtools.build.lib.packages.AttributeSerializer;
 import com.google.devtools.build.lib.packages.BuildType;
+import com.google.devtools.build.lib.packages.DependencyFilter;
 import com.google.devtools.build.lib.packages.EnvironmentGroup;
 import com.google.devtools.build.lib.packages.InputFile;
 import com.google.devtools.build.lib.packages.OutputFile;
@@ -45,7 +46,6 @@
 import com.google.devtools.build.lib.query2.proto.proto2api.Build.QueryResult.Builder;
 import com.google.devtools.build.lib.query2.proto.proto2api.Build.SourceFile;
 import com.google.devtools.build.lib.syntax.Environment;
-import com.google.devtools.build.lib.util.BinaryPredicate;
 
 import java.io.IOException;
 import java.io.PrintStream;
@@ -67,7 +67,7 @@
    */
   public static final String RULE_IMPLEMENTATION_HASH_ATTR_NAME = "$rule_implementation_hash";
 
-  private transient BinaryPredicate<Rule, Attribute> dependencyFilter;
+  private transient DependencyFilter dependencyFilter;
   protected transient AspectResolver aspectResolver;
 
   private boolean relativeLocations = false;
diff --git a/src/main/java/com/google/devtools/build/lib/query2/output/XmlOutputFormatter.java b/src/main/java/com/google/devtools/build/lib/query2/output/XmlOutputFormatter.java
index 9f735e5..a14facf 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/output/XmlOutputFormatter.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/output/XmlOutputFormatter.java
@@ -18,6 +18,7 @@
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.packages.Attribute;
 import com.google.devtools.build.lib.packages.BuildType;
+import com.google.devtools.build.lib.packages.DependencyFilter;
 import com.google.devtools.build.lib.packages.EnvironmentGroup;
 import com.google.devtools.build.lib.packages.FilesetEntry;
 import com.google.devtools.build.lib.packages.InputFile;
@@ -30,7 +31,6 @@
 import com.google.devtools.build.lib.query2.engine.OutputFormatterCallback;
 import com.google.devtools.build.lib.query2.output.AspectResolver.BuildFileDependencyMode;
 import com.google.devtools.build.lib.query2.output.OutputFormatter.AbstractUnorderedFormatter;
-import com.google.devtools.build.lib.util.BinaryPredicate;
 import com.google.devtools.build.lib.util.Pair;
 
 import org.w3c.dom.DOMException;
@@ -61,7 +61,7 @@
 
   private QueryOptions options;
   private AspectResolver aspectResolver;
-  private BinaryPredicate<Rule, Attribute> dependencyFilter;
+  private DependencyFilter dependencyFilter;
 
   @Override
   public String getName() {
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/TransitiveBaseTraversalFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/TransitiveBaseTraversalFunction.java
index 797be40..44b161b 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/TransitiveBaseTraversalFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/TransitiveBaseTraversalFunction.java
@@ -19,6 +19,7 @@
 import com.google.devtools.build.lib.events.EventHandler;
 import com.google.devtools.build.lib.packages.Attribute;
 import com.google.devtools.build.lib.packages.BuildFileContainsErrorsException;
+import com.google.devtools.build.lib.packages.DependencyFilter;
 import com.google.devtools.build.lib.packages.InputFile;
 import com.google.devtools.build.lib.packages.NoSuchPackageException;
 import com.google.devtools.build.lib.packages.NoSuchTargetException;
@@ -169,7 +170,7 @@
       }
 
       Multimap<Attribute, Label> transitions =
-              ((Rule) target).getTransitions(Rule.NO_NODEP_ATTRIBUTES);
+          ((Rule) target).getTransitions(DependencyFilter.NO_NODEP_ATTRIBUTES);
       for (Entry<Attribute, Label> entry : transitions.entries()) {
         ValueOrException2<NoSuchPackageException, NoSuchTargetException> value =
             labelDepMap.get(entry.getValue());
@@ -217,7 +218,7 @@
   }
 
   private static void visitRule(Target target, Set<Label> labels) {
-    labels.addAll(((Rule) target).getTransitions(Rule.NO_NODEP_ATTRIBUTES).values());
+    labels.addAll(((Rule) target).getTransitions(DependencyFilter.NO_NODEP_ATTRIBUTES).values());
   }
 
   private static void visitTargetVisibility(Target target, Set<Label> labels) {