Factor out filtering functions from universe in rdeps(u, x, 1).
For example, the query `rdeps(kind('binary', ...), //foo:bar, 1)` will be
first rewritten as `kind('binary', rdeps(..., //foo:bar, 1))`.
This rewriting is not much of an optimization on its own, but it may make the
query eligible for the RdepsToAllRdepsQueryExpressionMapper, which can rewrite
the example intermediate query as `kind('binary', allrdeps(//foo:bar, 1))`.
RELNOTES:
None.
PiperOrigin-RevId: 260773356
diff --git a/src/main/java/com/google/devtools/build/lib/query2/FilteredDirectRdepsInUniverseExpressionMapper.java b/src/main/java/com/google/devtools/build/lib/query2/FilteredDirectRdepsInUniverseExpressionMapper.java
new file mode 100644
index 0000000..a18535e
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/query2/FilteredDirectRdepsInUniverseExpressionMapper.java
@@ -0,0 +1,177 @@
+// Copyright 2019 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.query2;
+
+import com.google.common.base.Preconditions;
+import com.google.common.collect.ImmutableList;
+import com.google.devtools.build.lib.cmdline.TargetPattern;
+import com.google.devtools.build.lib.query2.engine.BinaryOperatorExpression;
+import com.google.devtools.build.lib.query2.engine.FunctionExpression;
+import com.google.devtools.build.lib.query2.engine.LetExpression;
+import com.google.devtools.build.lib.query2.engine.QueryEnvironment.Argument;
+import com.google.devtools.build.lib.query2.engine.QueryEnvironment.ArgumentType;
+import com.google.devtools.build.lib.query2.engine.QueryEnvironment.FilteringQueryFunction;
+import com.google.devtools.build.lib.query2.engine.QueryExpression;
+import com.google.devtools.build.lib.query2.engine.QueryExpressionMapper;
+import com.google.devtools.build.lib.query2.engine.QueryExpressionVisitor;
+import com.google.devtools.build.lib.query2.engine.RdepsFunction;
+import com.google.devtools.build.lib.query2.engine.SetExpression;
+import com.google.devtools.build.lib.query2.engine.TargetLiteral;
+import java.util.ArrayList;
+import java.util.List;
+
+/**
+ * A {@link QueryExpressionMapper} that transforms each occurrence of an expression of the form
+ * {@literal 'rdeps(filterfunc(<pat>, <universeScope>), <T>, 1)'} to {@literal 'filterfunc(<pat>,
+ * rdeps(<universeScope>, <T>, 1))'}.
+ *
+ * <p>By factoring the filterfunc out of the rdeps universe, we prepare the query for transformation
+ * by the {@link RdepsToAllRdepsQueryExpressionMapper}.
+ *
+ * <p><em>Note:</em> we require a max depth of 1 because the transformation is only sound with a
+ * depth of 1. Consider a query of depth 2.
+ *
+ * <ol>
+ * <li>{@literal 'rdeps(kind(^foo$, //...), //base:b, 2)'} yields these two disjoint sets:
+ * <ol>
+ * <li>targets of kind 'foo' that depend directly on //base:b
+ * <li>targets of kind 'foo' that do not depend directly on //base:b, and depend on a target
+ * of kind 'foo' that itself depends directly on //base:b
+ * </ol>
+ * <li>{@literal 'kind(^foo$, rdeps(//..., //base:b, 2))'} yields these two disjoint sets:
+ * <ol>
+ * <li>targets of kind 'foo' that depend directly on //base:b
+ * <li>targets of kind 'foo' that do not depend directly on //base:b, and depend on a target
+ * of <em>any</em> kind that itself depends directly on //base:b
+ * </ol>
+ * </ol>
+ *
+ * With a depth of 1, the rdeps operator in both queries would return only the first set: proof the
+ * transformation is sound. With a depth of 2, we see the rdeps operator with a filtered universe
+ * returns a strictly smaller set.
+ */
+public class FilteredDirectRdepsInUniverseExpressionMapper extends QueryExpressionMapper<Void> {
+ private final TargetPattern.Parser targetPatternParser;
+ private final String absoluteUniverseScopePattern;
+
+ FilteredDirectRdepsInUniverseExpressionMapper(
+ TargetPattern.Parser targetPatternParser, String universeScopePattern) {
+ this.targetPatternParser = targetPatternParser;
+ this.absoluteUniverseScopePattern = targetPatternParser.absolutize(universeScopePattern);
+ }
+
+ @Override
+ public QueryExpression visit(FunctionExpression functionExpression, Void context) {
+ if (functionExpression.getFunction().getName().equals(new RdepsFunction().getName())) {
+ List<Argument> args = functionExpression.getArgs();
+ // This transformation only applies to the 3-arg form of rdeps, with depth == 1.
+ if (args.size() == 3 && args.get(2).getInteger() == 1) {
+ List<FunctionExpression> universeFilteringFunctions =
+ args.get(0).getExpression().accept(new ExtractFilteringFunctionsFromUniverseVisitor());
+ // If we get back a non-empty list of FunctionExpressions, these are filtering functions
+ // that can be safely factored out.
+ if (!universeFilteringFunctions.isEmpty()) {
+ QueryExpression curFunction = makeUnfilteredRdepsWithDepthOne(args.get(1));
+ for (FunctionExpression filterExpr : universeFilteringFunctions) {
+ curFunction = wrapExprWithFilter(curFunction, filterExpr);
+ }
+ return curFunction;
+ }
+ }
+ }
+ return super.visit(functionExpression, context);
+ }
+
+ private FunctionExpression makeUnfilteredRdepsWithDepthOne(Argument target) {
+ return new FunctionExpression(
+ new RdepsFunction(),
+ ImmutableList.of(
+ Argument.of(new TargetLiteral(absoluteUniverseScopePattern)), target, Argument.of(1)));
+ }
+
+ private static QueryExpression wrapExprWithFilter(
+ QueryExpression curFunction, FunctionExpression filterExpr) {
+ List<Argument> filterExprArgs = filterExpr.getArgs();
+ FilteringQueryFunction filteringFunction = filterExpr.getFunction().asFilteringFunction();
+ List<Argument> rewrittenArgs = new ArrayList<>();
+ for (int i = 0; i < filterExprArgs.size(); i++) {
+ if (i == filteringFunction.getExpressionToFilterIndex()) {
+ rewrittenArgs.add(Argument.of(curFunction));
+ } else {
+ rewrittenArgs.add(filterExprArgs.get(i));
+ }
+ }
+ return new FunctionExpression(filteringFunction, rewrittenArgs);
+ }
+
+ /**
+ * Internal visitor applied to the universe argument of all QueryExpressions of the form {@literal
+ * rdeps(u, x, 1)}.
+ */
+ private class ExtractFilteringFunctionsFromUniverseVisitor
+ implements QueryExpressionVisitor<List<FunctionExpression>, Void> {
+
+ @Override
+ public List<FunctionExpression> visit(TargetLiteral targetLiteral, Void context) {
+ return ImmutableList.of();
+ }
+
+ @Override
+ public List<FunctionExpression> visit(
+ BinaryOperatorExpression binaryOperatorExpression, Void context) {
+ return ImmutableList.of();
+ }
+
+ @SuppressWarnings("MixedMutabilityReturnType")
+ @Override
+ public List<FunctionExpression> visit(FunctionExpression functionExpression, Void context) {
+ FilteringQueryFunction filteringFunction =
+ functionExpression.getFunction().asFilteringFunction();
+ if (filteringFunction == null) {
+ return ImmutableList.of();
+ }
+ Argument filteredArgument =
+ functionExpression.getArgs().get(filteringFunction.getExpressionToFilterIndex());
+ Preconditions.checkArgument(filteredArgument.getType() == ArgumentType.EXPRESSION);
+ QueryExpression filteredExpression = filteredArgument.getExpression();
+
+ ArrayList<FunctionExpression> results = new ArrayList<>();
+ if (filteredExpression instanceof TargetLiteral) {
+ TargetLiteral literalUniverseExpression = (TargetLiteral) filteredExpression;
+ String absolutizedUniverseExpression =
+ targetPatternParser.absolutize(literalUniverseExpression.getPattern());
+ if (absolutizedUniverseExpression.equals(absoluteUniverseScopePattern)) {
+ results.add(functionExpression);
+ }
+ } else if (filteredExpression instanceof FunctionExpression) {
+ List<FunctionExpression> nestedFilters = filteredExpression.accept(this);
+ if (!nestedFilters.isEmpty()) {
+ results.addAll(nestedFilters);
+ results.add(functionExpression);
+ }
+ }
+ return results;
+ }
+
+ @Override
+ public List<FunctionExpression> visit(LetExpression letExpression, Void context) {
+ return ImmutableList.of();
+ }
+
+ @Override
+ public List<FunctionExpression> visit(SetExpression setExpression, Void context) {
+ return ImmutableList.of();
+ }
+ }
+}
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 ddc9ded..b58c9be 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
@@ -355,7 +355,10 @@
}
TargetPattern.Parser targetPatternParser = new TargetPattern.Parser(parserPrefix);
String universeScopePattern = Iterables.getOnlyElement(universeScope);
- return new RdepsToAllRdepsQueryExpressionMapper(targetPatternParser, universeScopePattern);
+ return QueryExpressionMapper.compose(
+ new RdepsToAllRdepsQueryExpressionMapper(targetPatternParser, universeScopePattern),
+ new FilteredDirectRdepsInUniverseExpressionMapper(
+ targetPatternParser, universeScopePattern));
}
@Override
