diff options
Diffstat (limited to 'src/main/java/com/google/devtools/build/lib/query2/engine')
25 files changed, 2625 insertions, 0 deletions
diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/AllPathsFunction.java b/src/main/java/com/google/devtools/build/lib/query2/engine/AllPathsFunction.java new file mode 100644 index 0000000000..d2d5f05f9c --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/query2/engine/AllPathsFunction.java @@ -0,0 +1,96 @@ +// Copyright 2014 Google Inc. All rights reserved. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. +package com.google.devtools.build.lib.query2.engine; + +import com.google.common.collect.ImmutableList; +import com.google.common.collect.Sets; +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.QueryFunction; + +import java.util.HashSet; +import java.util.LinkedList; +import java.util.List; +import java.util.Set; + +/** + * Implementation of the <code>allpaths()</code> function. + */ +public class AllPathsFunction implements QueryFunction { + AllPathsFunction() { + } + + @Override + public String getName() { + return "allpaths"; + } + + @Override + public int getMandatoryArguments() { + return 2; + } + + @Override + public List<ArgumentType> getArgumentTypes() { + return ImmutableList.of(ArgumentType.EXPRESSION, ArgumentType.EXPRESSION); + } + + @Override + public <T> Set<T> eval(QueryEnvironment<T> env, QueryExpression expression, List<Argument> args) + throws QueryException { + QueryExpression from = args.get(0).getExpression(); + QueryExpression to = args.get(1).getExpression(); + + Set<T> fromValue = from.eval(env); + Set<T> toValue = to.eval(env); + + // Algorithm: compute "reachableFromX", the forward transitive closure of + // the "from" set, then find the intersection of "reachableFromX" with the + // reverse transitive closure of the "to" set. The reverse transitive + // closure and intersection operations are interleaved for efficiency. + // "result" holds the intersection. + + env.buildTransitiveClosure(expression, fromValue, Integer.MAX_VALUE); + + Set<T> reachableFromX = env.getTransitiveClosure(fromValue); + Set<T> result = intersection(reachableFromX, toValue); + LinkedList<T> worklist = new LinkedList<>(result); + + T n; + while ((n = worklist.poll()) != null) { + for (T np : env.getReverseDeps(n)) { + if (reachableFromX.contains(np)) { + if (result.add(np)) { + worklist.add(np); + } + } + } + } + return result; + } + + /** + * Returns a (new, mutable, unordered) set containing the intersection of the + * two specified sets. + */ + private static <T> Set<T> intersection(Set<T> x, Set<T> y) { + Set<T> result = new HashSet<>(); + if (x.size() > y.size()) { + Sets.intersection(y, x).copyInto(result); + } else { + Sets.intersection(x, y).copyInto(result); + } + return result; + } +} diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/AttrFunction.java b/src/main/java/com/google/devtools/build/lib/query2/engine/AttrFunction.java new file mode 100644 index 0000000000..054cf78b55 --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/query2/engine/AttrFunction.java @@ -0,0 +1,78 @@ +// Copyright 2014 Google Inc. All rights reserved. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. +package com.google.devtools.build.lib.query2.engine; + +import com.google.common.collect.ImmutableList; +import com.google.devtools.build.lib.query2.engine.QueryEnvironment.Argument; +import com.google.devtools.build.lib.query2.engine.QueryEnvironment.ArgumentType; + +import java.util.List; + +/** + * An attr(attribute, pattern, argument) filter expression, which computes + * the set of subset of nodes in 'argument' which correspond to rules with + * defined attribute 'attribute' with attribute value matching the unanchored + * regexp 'pattern'. For list attributes, the attribute value will be defined as + * a usual List.toString() representation (using '[' as first character, ']' as + * last character and ", " as a delimiter between multiple values). Also, all + * label-based attributes will use fully-qualified label names instead of + * original value specified in the BUILD file. + * + * <pre>expr ::= ATTR '(' ATTRNAME ',' WORD ',' expr ')'</pre> + * + * Examples + * <pre> + * attr(linkshared,1,//project/...) find all rules under in the //project/... that + * have attribute linkshared set to 1. + * </pre> + */ +class AttrFunction extends RegexFilterExpression { + AttrFunction() { + } + + @Override + public String getName() { + return "attr"; + } + + @Override + protected String getPattern(List<Argument> args) { + return args.get(1).getWord(); + } + + @Override + public int getMandatoryArguments() { + return 3; + } + + @Override + public List<ArgumentType> getArgumentTypes() { + return ImmutableList.of(ArgumentType.WORD, ArgumentType.WORD, ArgumentType.EXPRESSION); + } + + @Override + protected <T> String getFilterString(QueryEnvironment<T> env, List<Argument> args, T target) { + throw new IllegalStateException( + "The 'attr' regex filter gets its match values directly from getFilterStrings"); + } + + @Override + protected <T> Iterable<String> getFilterStrings(QueryEnvironment<T> env, + List<Argument> args, T target) { + if (env.getAccessor().isRule(target)) { + return env.getAccessor().getAttrAsString(target, args.get(0).getWord()); + } + return ImmutableList.of(); + } +} diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/BinaryOperatorExpression.java b/src/main/java/com/google/devtools/build/lib/query2/engine/BinaryOperatorExpression.java new file mode 100644 index 0000000000..e5e600f831 --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/query2/engine/BinaryOperatorExpression.java @@ -0,0 +1,93 @@ +// Copyright 2014 Google Inc. All rights reserved. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. +package com.google.devtools.build.lib.query2.engine; + +import com.google.common.base.Preconditions; +import com.google.common.collect.ImmutableList; + +import java.util.Collection; +import java.util.LinkedHashSet; +import java.util.List; +import java.util.Set; + +/** + * A binary algebraic set operation. + * + * <pre> + * expr ::= expr (INTERSECT expr)+ + * | expr ('^' expr)+ + * | expr (UNION expr)+ + * | expr ('+' expr)+ + * | expr (EXCEPT expr)+ + * | expr ('-' expr)+ + * </pre> + */ +class BinaryOperatorExpression extends QueryExpression { + + private final Lexer.TokenKind operator; // ::= INTERSECT/CARET | UNION/PLUS | EXCEPT/MINUS + private final ImmutableList<QueryExpression> operands; + + BinaryOperatorExpression(Lexer.TokenKind operator, + List<QueryExpression> operands) { + Preconditions.checkState(operands.size() > 1); + this.operator = operator; + this.operands = ImmutableList.copyOf(operands); + } + + @Override + public <T> Set<T> eval(QueryEnvironment<T> env) throws QueryException { + Set<T> lhsValue = new LinkedHashSet<>(operands.get(0).eval(env)); + + for (int i = 1; i < operands.size(); i++) { + Set<T> rhsValue = operands.get(i).eval(env); + switch (operator) { + case INTERSECT: + case CARET: + lhsValue.retainAll(rhsValue); + break; + case UNION: + case PLUS: + lhsValue.addAll(rhsValue); + break; + case EXCEPT: + case MINUS: + lhsValue.removeAll(rhsValue); + break; + default: + throw new IllegalStateException("operator=" + operator); + } + } + return lhsValue; + } + + @Override + public void collectTargetPatterns(Collection<String> literals) { + for (QueryExpression subExpression : operands) { + subExpression.collectTargetPatterns(literals); + } + } + + @Override + public String toString() { + StringBuilder result = new StringBuilder(); + for (int i = 1; i < operands.size(); i++) { + result.append("("); + } + result.append(operands.get(0)); + for (int i = 1; i < operands.size(); i++) { + result.append(" " + operator.getPrettyName() + " " + operands.get(i) + ")"); + } + return result.toString(); + } +} diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/BlazeQueryEvalResult.java b/src/main/java/com/google/devtools/build/lib/query2/engine/BlazeQueryEvalResult.java new file mode 100644 index 0000000000..7f2060f176 --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/query2/engine/BlazeQueryEvalResult.java @@ -0,0 +1,36 @@ +// Copyright 2014 Google Inc. All rights reserved. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +package com.google.devtools.build.lib.query2.engine; + +import com.google.common.base.Preconditions; +import com.google.devtools.build.lib.graph.Digraph; + +import java.util.Set; + +/** {@link QueryEvalResult} along with a digraph giving the structure of the results. */ +public class BlazeQueryEvalResult<T> extends QueryEvalResult<T> { + + private final Digraph<T> graph; + + public BlazeQueryEvalResult(boolean success, Set<T> resultSet, Digraph<T> graph) { + super(success, resultSet); + this.graph = Preconditions.checkNotNull(graph); + } + + /** Returns the result as a directed graph over elements. */ + public Digraph<T> getResultGraph() { + return graph.extractSubgraph(resultSet); + } +} diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/BuildFilesFunction.java b/src/main/java/com/google/devtools/build/lib/query2/engine/BuildFilesFunction.java new file mode 100644 index 0000000000..d606a6acb3 --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/query2/engine/BuildFilesFunction.java @@ -0,0 +1,56 @@ +// Copyright 2014 Google Inc. All rights reserved. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. +package com.google.devtools.build.lib.query2.engine; + +import com.google.common.collect.ImmutableList; +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.QueryFunction; + +import java.util.List; +import java.util.Set; + +/** + * A buildfiles(x) query expression, which computes the set of BUILD files and + * subincluded files for each target in set x. The result is unordered. This + * operator is typically used for determinining what files or packages to check + * out. + * + * <pre>expr ::= BUILDFILES '(' expr ')'</pre> + */ +class BuildFilesFunction implements QueryFunction { + BuildFilesFunction() { + } + + @Override + public String getName() { + return "buildfiles"; + } + + @Override + public <T> Set<T> eval(QueryEnvironment<T> env, QueryExpression expression, List<Argument> args) + throws QueryException { + return env.getBuildFiles(expression, args.get(0).getExpression().eval(env)); + } + + @Override + public int getMandatoryArguments() { + return 1; + } + + @Override + public List<ArgumentType> getArgumentTypes() { + return ImmutableList.of(ArgumentType.EXPRESSION); + } +} diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/DepsFunction.java b/src/main/java/com/google/devtools/build/lib/query2/engine/DepsFunction.java new file mode 100644 index 0000000000..2b693eb8a7 --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/query2/engine/DepsFunction.java @@ -0,0 +1,88 @@ +// Copyright 2014 Google Inc. All rights reserved. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. +package com.google.devtools.build.lib.query2.engine; + +import com.google.common.collect.ImmutableList; +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.QueryFunction; + +import java.util.ArrayList; +import java.util.Collection; +import java.util.LinkedHashSet; +import java.util.List; +import java.util.Set; + +/** + * A "deps" query expression, which computes the dependencies of the argument. An optional + * integer-literal second argument may be specified; its value bounds the search from the arguments. + * + * <pre>expr ::= DEPS '(' expr ')'</pre> + * <pre> | DEPS '(' expr ',' WORD ')'</pre> + */ +final class DepsFunction implements QueryFunction { + DepsFunction() { + } + + @Override + public String getName() { + return "deps"; + } + + @Override + public int getMandatoryArguments() { + return 1; // last argument is optional + } + + @Override + public List<ArgumentType> getArgumentTypes() { + return ImmutableList.of(ArgumentType.EXPRESSION, ArgumentType.INTEGER); + } + + /** + * Breadth-first search from the arguments. + */ + @Override + public <T> Set<T> eval(QueryEnvironment<T> env, QueryExpression expression, List<Argument> args) + throws QueryException { + Set<T> argumentValue = args.get(0).getExpression().eval(env); + int depthBound = args.size() > 1 ? args.get(1).getInteger() : Integer.MAX_VALUE; + env.buildTransitiveClosure(expression, argumentValue, depthBound); + + Set<T> visited = new LinkedHashSet<>(); + Collection<T> current = argumentValue; + + // We need to iterate depthBound + 1 times. + for (int i = 0; i <= depthBound; i++) { + List<T> next = new ArrayList<>(); + for (T node : current) { + if (!visited.add(node)) { + // Already visited; if we see a node in a later round, then we don't need to visit it + // again, because the depth at which we see it at must be greater than or equal to the + // last visit. + continue; + } + + next.addAll(env.getFwdDeps(node)); + } + if (next.isEmpty()) { + // Exit when there are no more nodes to visit. + break; + } + current = next; + } + + return visited; + } +} diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/FilterFunction.java b/src/main/java/com/google/devtools/build/lib/query2/engine/FilterFunction.java new file mode 100644 index 0000000000..bd8995082e --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/query2/engine/FilterFunction.java @@ -0,0 +1,63 @@ +// Copyright 2014 Google Inc. All rights reserved. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. +package com.google.devtools.build.lib.query2.engine; + +import com.google.common.collect.ImmutableList; +import com.google.devtools.build.lib.query2.engine.QueryEnvironment.Argument; +import com.google.devtools.build.lib.query2.engine.QueryEnvironment.ArgumentType; + +import java.util.List; + +/** + * A label(pattern, argument) filter expression, which computes the set of subset + * of nodes in 'argument' whose label matches the unanchored regexp 'pattern'. + * + * <pre>expr ::= FILTER '(' WORD ',' expr ')'</pre> + * + * Example patterns: + * <pre> + * '//third_party' Match all targets in the //third_party/... + * (equivalent to 'intersect //third_party/...) + * '\.jar$' Match all *.jar targets. + * </pre> + */ +class FilterFunction extends RegexFilterExpression { + FilterFunction() { + } + + @Override + public String getName() { + return "filter"; + } + + @Override + protected String getPattern(List<Argument> args) { + return args.get(0).getWord(); + } + + @Override + public int getMandatoryArguments() { + return 2; + } + + @Override + public List<ArgumentType> getArgumentTypes() { + return ImmutableList.of(ArgumentType.WORD, ArgumentType.EXPRESSION); + } + + @Override + protected <T> String getFilterString(QueryEnvironment<T> env, List<Argument> args, T target) { + return env.getAccessor().getLabel(target); + } +} diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/FunctionExpression.java b/src/main/java/com/google/devtools/build/lib/query2/engine/FunctionExpression.java new file mode 100644 index 0000000000..62734fd07e --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/query2/engine/FunctionExpression.java @@ -0,0 +1,59 @@ +// Copyright 2014 Google Inc. All rights reserved. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. +package com.google.devtools.build.lib.query2.engine; + +import com.google.common.base.Functions; +import com.google.common.base.Joiner; +import com.google.common.collect.ImmutableList; +import com.google.common.collect.Iterables; +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.QueryFunction; + +import java.util.Collection; +import java.util.List; +import java.util.Set; + +/** + * A query expression for user-defined query functions. + */ +public class FunctionExpression extends QueryExpression { + QueryFunction function; + List<Argument> args; + + public FunctionExpression(QueryFunction function, List<Argument> args) { + this.function = function; + this.args = ImmutableList.copyOf(args); + } + + @Override + public <T> Set<T> eval(QueryEnvironment<T> env) throws QueryException { + return function.<T>eval(env, this, args); + } + + @Override + public void collectTargetPatterns(Collection<String> literals) { + for (Argument arg : args) { + if (arg.getType() == ArgumentType.EXPRESSION) { + arg.getExpression().collectTargetPatterns(literals); + } + } + } + + @Override + public String toString() { + return function.getName() + + "(" + Joiner.on(", ").join(Iterables.transform(args, Functions.toStringFunction())) + ")"; + } +} diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/KindFunction.java b/src/main/java/com/google/devtools/build/lib/query2/engine/KindFunction.java new file mode 100644 index 0000000000..7ae80b88db --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/query2/engine/KindFunction.java @@ -0,0 +1,70 @@ +// Copyright 2014 Google Inc. All rights reserved. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. +package com.google.devtools.build.lib.query2.engine; + +import com.google.common.collect.ImmutableList; +import com.google.devtools.build.lib.query2.engine.QueryEnvironment.Argument; +import com.google.devtools.build.lib.query2.engine.QueryEnvironment.ArgumentType; + +import java.util.List; + +/** + * A kind(pattern, argument) filter expression, which computes the set of subset + * of nodes in 'argument' whose kind matches the unanchored regexp 'pattern'. + * + * <pre>expr ::= KIND '(' WORD ',' expr ')'</pre> + * + * Example patterns: + * <pre> + * ' file' Match all file targets. + * 'source file' Match all test source file targets. + * 'generated file' Match all test generated file targets. + * ' rule' Match all rule targets. + * 'foo_*' Match all rules starting with "foo_", + * 'test' Match all test (rule) targets. + * </pre> + * + * Note, the space before "file" is needed to prevent unwanted matches against + * (e.g.) "filegroup rule". + */ +class KindFunction extends RegexFilterExpression { + + KindFunction() { + } + + @Override + public String getName() { + return "kind"; + } + + @Override + protected String getPattern(List<Argument> args) { + return args.get(0).getWord(); + } + + @Override + public int getMandatoryArguments() { + return 2; + } + + @Override + public List<ArgumentType> getArgumentTypes() { + return ImmutableList.of(ArgumentType.WORD, ArgumentType.EXPRESSION); + } + + @Override + protected <T> String getFilterString(QueryEnvironment<T> env, List<Argument> args, T target) { + return env.getAccessor().getTargetKind(target); + } +} diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/LabelsFunction.java b/src/main/java/com/google/devtools/build/lib/query2/engine/LabelsFunction.java new file mode 100644 index 0000000000..1093d85290 --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/query2/engine/LabelsFunction.java @@ -0,0 +1,72 @@ +// Copyright 2014 Google Inc. All rights reserved. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. +package com.google.devtools.build.lib.query2.engine; + +import com.google.common.collect.ImmutableList; +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.QueryFunction; + +import java.util.LinkedHashSet; +import java.util.List; +import java.util.Set; + +/** + * A label(attr_name, argument) expression, which computes the set of targets + * whose labels appear in the specified attribute of some rule in 'argument'. + * + * <pre>expr ::= LABELS '(' WORD ',' expr ')'</pre> + * + * Example: + * <pre> + * labels(srcs, //foo) The 'srcs' source files to the //foo rule. + * </pre> + */ +class LabelsFunction implements QueryFunction { + LabelsFunction() { + } + + @Override + public String getName() { + return "labels"; + } + + @Override + public int getMandatoryArguments() { + return 2; + } + + @Override + public List<ArgumentType> getArgumentTypes() { + return ImmutableList.of(ArgumentType.WORD, ArgumentType.EXPRESSION); + } + + @Override + public <T> Set<T> eval(QueryEnvironment<T> env, QueryExpression expression, List<Argument> args) + throws QueryException { + Set<T> inputs = args.get(1).getExpression().eval(env); + Set<T> result = new LinkedHashSet<>(); + String attrName = args.get(0).getWord(); + for (T input : inputs) { + if (env.getAccessor().isRule(input)) { + List<T> targets = env.getAccessor().getLabelListAttr(expression, input, attrName, + "in '" + attrName + "' of rule " + env.getAccessor().getLabel(input) + ": "); + for (T target : targets) { + result.add(env.getOrCreate(target)); + } + } + } + return result; + } +} diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/LetExpression.java b/src/main/java/com/google/devtools/build/lib/query2/engine/LetExpression.java new file mode 100644 index 0000000000..3e17ccebbe --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/query2/engine/LetExpression.java @@ -0,0 +1,78 @@ +// Copyright 2014 Google Inc. All rights reserved. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. +package com.google.devtools.build.lib.query2.engine; + +import java.util.Collection; +import java.util.Set; +import java.util.regex.Pattern; + +/** + * A let expression. + * + * <pre>expr ::= LET WORD = expr IN expr</pre> + */ +class LetExpression extends QueryExpression { + + private static final String VAR_NAME_PATTERN = "[a-zA-Z_][a-zA-Z0-9_]*$"; + + // Variables names may be any legal identifier in the C programming language + private static final Pattern NAME_PATTERN = Pattern.compile("^" + VAR_NAME_PATTERN); + + // Variable references are prepended with the "$" character. + // A variable named "x" is referenced as "$x". + private static final Pattern REF_PATTERN = Pattern.compile("^\\$" + VAR_NAME_PATTERN); + + static boolean isValidVarReference(String varName) { + return REF_PATTERN.matcher(varName).matches(); + } + + static String getNameFromReference(String reference) { + return reference.substring(1); + } + + private final String varName; + private final QueryExpression varExpr; + private final QueryExpression bodyExpr; + + LetExpression(String varName, QueryExpression varExpr, QueryExpression bodyExpr) { + this.varName = varName; + this.varExpr = varExpr; + this.bodyExpr = bodyExpr; + } + + @Override + public <T> Set<T> eval(QueryEnvironment<T> env) throws QueryException { + if (!NAME_PATTERN.matcher(varName).matches()) { + throw new QueryException(this, "invalid variable name '" + varName + "' in let expression"); + } + Set<T> varValue = varExpr.eval(env); + Set<T> prevValue = env.setVariable(varName, varValue); + try { + return bodyExpr.eval(env); + } finally { + env.setVariable(varName, prevValue); // restore + } + } + + @Override + public void collectTargetPatterns(Collection<String> literals) { + varExpr.collectTargetPatterns(literals); + bodyExpr.collectTargetPatterns(literals); + } + + @Override + public String toString() { + return "let " + varName + " = " + varExpr + " in " + bodyExpr; + } +} diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/Lexer.java b/src/main/java/com/google/devtools/build/lib/query2/engine/Lexer.java new file mode 100644 index 0000000000..45b6f6183e --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/query2/engine/Lexer.java @@ -0,0 +1,281 @@ +// Copyright 2014 Google Inc. All rights reserved. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. +package com.google.devtools.build.lib.query2.engine; + +import java.util.ArrayList; +import java.util.EnumSet; +import java.util.HashMap; +import java.util.List; +import java.util.Map; +import java.util.Set; + +/** + * A tokenizer for the Blaze query language, revision 2. + * + * Note, we can avoid a lot of quoting by noting that the characters [() ,] do + * not appear in any label, filename, function name, or regular expression we care about. + * + * No string escapes are allowed ("\"). Given the domain, that's not currently + * a problem. + */ +final class Lexer { + + /** + * Discriminator for different kinds of tokens. + */ + public enum TokenKind { + WORD("word"), + EOF("EOF"), + + COMMA(","), + EQUALS("="), + LPAREN("("), + MINUS("-"), + PLUS("+"), + RPAREN(")"), + CARET("^"), + + __ALL_IDENTIFIERS_FOLLOW(""), // See below + + IN("in"), + LET("let"), + SET("set"), + + INTERSECT("intersect"), + EXCEPT("except"), + UNION("union"); + + private final String prettyName; + + private TokenKind(String prettyName) { + this.prettyName = prettyName; + } + + public String getPrettyName() { + return prettyName; + } + } + + public static final Set<TokenKind> BINARY_OPERATORS = EnumSet.of( + TokenKind.INTERSECT, + TokenKind.CARET, + TokenKind.UNION, + TokenKind.PLUS, + TokenKind.EXCEPT, + TokenKind.MINUS); + + private static final Map<String, TokenKind> keywordMap = new HashMap<>(); + static { + for (TokenKind kind : EnumSet.allOf(TokenKind.class)) { + if (kind.ordinal() > TokenKind.__ALL_IDENTIFIERS_FOLLOW.ordinal()) { + keywordMap.put(kind.getPrettyName(), kind); + } + } + } + + /** + * Returns true iff 'word' is a reserved word of the language. + */ + static boolean isReservedWord(String word) { + return keywordMap.containsKey(word); + } + + /** + * Tokens returned by the Lexer. + */ + static class Token { + + public final TokenKind kind; + public final String word; + + Token(TokenKind kind) { + this.kind = kind; + this.word = null; + } + + Token(String word) { + this.kind = TokenKind.WORD; + this.word = word; + } + + @Override + public String toString() { + return kind == TokenKind.WORD ? word : kind.getPrettyName(); + } + } + + /** + * Entry point to the lexer. Returns the list of tokens for the specified + * input, or throws QueryException. + */ + public static List<Token> scan(char[] buffer) throws QueryException { + Lexer lexer = new Lexer(buffer); + lexer.tokenize(); + return lexer.tokens; + } + + // Input buffer and position + private char[] buffer; + private int pos; + + private final List<Token> tokens = new ArrayList<>(); + + private Lexer(char[] buffer) { + this.buffer = buffer; + this.pos = 0; + } + + private void addToken(Token s) { + tokens.add(s); + } + + /** + * Scans a quoted word delimited by 'quot'. + * + * ON ENTRY: 'pos' is 1 + the index of the first delimiter + * ON EXIT: 'pos' is 1 + the index of the last delimiter. + * + * @return the word token. + */ + private Token quotedWord(char quot) throws QueryException { + int oldPos = pos - 1; + while (pos < buffer.length) { + char c = buffer[pos++]; + switch (c) { + case '\'': + case '"': + if (c == quot) { + // close-quote, all done. + return new Token(bufferSlice(oldPos + 1, pos - 1)); + } + } + } + throw new QueryException("unclosed quotation"); + } + + private TokenKind getTokenKindForWord(String word) { + TokenKind kind = keywordMap.get(word); + return kind == null ? TokenKind.WORD : kind; + } + + // Unquoted words may contain [-*$], but not start with them. For user convenience, unquoted + // words must include UNIX filenames, labels and target label patterns, and simple regexps + // (e.g. cc_.*). Keep consistent with TargetLiteral.toString()! + private String scanWord() { + int oldPos = pos - 1; + while (pos < buffer.length) { + switch (buffer[pos]) { + case 'a': case 'b': case 'c': case 'd': case 'e': case 'f': + case 'g': case 'h': case 'i': case 'j': case 'k': case 'l': + case 'm': case 'n': case 'o': case 'p': case 'q': case 'r': + case 's': case 't': case 'u': case 'v': case 'w': case 'x': + case 'y': case 'z': + case 'A': case 'B': case 'C': case 'D': case 'E': case 'F': + case 'G': case 'H': case 'I': case 'J': case 'K': case 'L': + case 'M': case 'N': case 'O': case 'P': case 'Q': case 'R': + case 'S': case 'T': case 'U': case 'V': case 'W': case 'X': + case 'Y': case 'Z': + case '0': case '1': case '2': case '3': case '4': case '5': + case '6': case '7': case '8': case '9': + case '*': case '/': case '@': case '.': case '-': case '_': + case ':': case '$': + pos++; + break; + default: + return bufferSlice(oldPos, pos); + } + } + return bufferSlice(oldPos, pos); + } + + /** + * Scans a word or keyword. + * + * ON ENTRY: 'pos' is 1 + the index of the first char in the word. + * ON EXIT: 'pos' is 1 + the index of the last char in the word. + * + * @return the word or keyword token. + */ + private Token wordOrKeyword() { + String word = scanWord(); + TokenKind kind = getTokenKindForWord(word); + return kind == TokenKind.WORD ? new Token(word) : new Token(kind); + } + + /** + * Performs tokenization of the character buffer of file contents provided to + * the constructor. + */ + private void tokenize() throws QueryException { + while (pos < buffer.length) { + char c = buffer[pos]; + pos++; + switch (c) { + case '(': { + addToken(new Token(TokenKind.LPAREN)); + break; + } + case ')': { + addToken(new Token(TokenKind.RPAREN)); + break; + } + case ',': { + addToken(new Token(TokenKind.COMMA)); + break; + } + case '+': { + addToken(new Token(TokenKind.PLUS)); + break; + } + case '-': { + addToken(new Token(TokenKind.MINUS)); + break; + } + case '=': { + addToken(new Token(TokenKind.EQUALS)); + break; + } + case '^': { + addToken(new Token(TokenKind.CARET)); + break; + } + case '\n': + case ' ': + case '\t': + case '\r': { + /* ignore */ + break; + } + case '\'': + case '\"': { + addToken(quotedWord(c)); + break; + } + default: { + addToken(wordOrKeyword()); + break; + } // default + } // switch + } // while + + addToken(new Token(TokenKind.EOF)); + + this.buffer = null; // release buffer now that we have our tokens + } + + private String bufferSlice(int start, int end) { + return new String(this.buffer, start, end - start); + } + +} diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/QueryEnvironment.java b/src/main/java/com/google/devtools/build/lib/query2/engine/QueryEnvironment.java new file mode 100644 index 0000000000..46a7afd42d --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/query2/engine/QueryEnvironment.java @@ -0,0 +1,351 @@ +// Copyright 2014 Google Inc. All rights reserved. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. +package com.google.devtools.build.lib.query2.engine; + +import com.google.common.collect.ImmutableList; + +import java.util.Collection; +import java.util.List; +import java.util.Set; + +import javax.annotation.Nonnull; + +/** + * The environment of a Blaze query. Implementations do not need to be thread-safe. The generic type + * T represents a node of the graph on which the query runs; as such, there is no restriction on T. + * However, query assumes a certain graph model, and the {@link TargetAccessor} class is used to + * access properties of these nodes. + * + * @param <T> the node type of the dependency graph + */ +public interface QueryEnvironment<T> { + /** + * Type of an argument of a user-defined query function. + */ + public enum ArgumentType { + EXPRESSION, WORD, INTEGER; + } + + /** + * Value of an argument of a user-defined query function. + */ + public static class Argument { + private final ArgumentType type; + private final QueryExpression expression; + private final String word; + private final int integer; + + private Argument(ArgumentType type, QueryExpression expression, String word, int integer) { + this.type = type; + this.expression = expression; + this.word = word; + this.integer = integer; + } + + static Argument of(QueryExpression expression) { + return new Argument(ArgumentType.EXPRESSION, expression, null, 0); + } + + static Argument of(String word) { + return new Argument(ArgumentType.WORD, null, word, 0); + } + + static Argument of(int integer) { + return new Argument(ArgumentType.INTEGER, null, null, integer); + } + + public ArgumentType getType() { + return type; + } + + public QueryExpression getExpression() { + return expression; + } + + public String getWord() { + return word; + } + + public int getInteger() { + return integer; + } + + @Override + public String toString() { + switch (type) { + case WORD: return "'" + word + "'"; + case EXPRESSION: return expression.toString(); + case INTEGER: return Integer.toString(integer); + default: throw new IllegalStateException(); + } + } + } + + /** + * A user-defined query function. + */ + public interface QueryFunction { + /** + * Name of the function as it appears in the query language. + */ + String getName(); + + /** + * The number of arguments that are required. The rest is optional. + * + * <p>This should be greater than or equal to zero and at smaller than or equal to the length + * of the list returned by {@link #getArgumentTypes}. + */ + int getMandatoryArguments(); + + /** + * The types of the arguments of the function. + */ + List<ArgumentType> getArgumentTypes(); + + /** + * Called when a user-defined function is to be evaluated. + * + * @param env the query environment this function is evaluated in. + * @param expression the expression being evaluated. + * @param args the input arguments. These are type-checked against the specification returned + * by {@link #getArgumentTypes} and {@link #getMandatoryArguments} + */ + <T> Set<T> eval(QueryEnvironment<T> env, QueryExpression expression, List<Argument> args) + throws QueryException; + } + + /** + * Exception type for the case where a target cannot be found. It's basically a wrapper for + * whatever exception is internally thrown. + */ + public static final class TargetNotFoundException extends Exception { + public TargetNotFoundException(String msg) { + super(msg); + } + + public TargetNotFoundException(Throwable cause) { + super(cause.getMessage(), cause); + } + } + + /** + * Returns the set of target nodes in the graph for the specified target + * pattern, in 'blaze build' syntax. + */ + Set<T> getTargetsMatchingPattern(QueryExpression owner, String pattern) + throws QueryException; + + /** Ensures the specified target exists. */ + // NOTE(bazel-team): this method is left here as scaffolding from a previous refactoring. It may + // be possible to remove it. + T getOrCreate(T target); + + /** Returns the direct forward dependencies of the specified target. */ + Collection<T> getFwdDeps(T target); + + /** Returns the direct reverse dependencies of the specified target. */ + Collection<T> getReverseDeps(T target); + + /** + * Returns the forward transitive closure of all of the targets in + * "targets". Callers must ensure that {@link #buildTransitiveClosure} + * has been called for the relevant subgraph. + */ + Set<T> getTransitiveClosure(Set<T> targets); + + /** + * Construct the dependency graph for a depth-bounded forward transitive closure + * of all nodes in "targetNodes". The identity of the calling expression is + * required to produce error messages. + * + * <p>If a larger transitive closure was already built, returns it to + * improve incrementality, since all depth-constrained methods filter it + * after it is built anyway. + */ + void buildTransitiveClosure(QueryExpression caller, + Set<T> targetNodes, + int maxDepth) throws QueryException; + + /** + * Returns the set of nodes on some path from "from" to "to". + */ + Set<T> getNodesOnPath(T from, T to); + + /** + * Returns the value of the specified variable, or null if it is undefined. + */ + Set<T> getVariable(String name); + + /** + * Sets the value of the specified variable. If value is null the variable + * becomes undefined. Returns the previous value, if any. + */ + Set<T> setVariable(String name, Set<T> value); + + void reportBuildFileError(QueryExpression expression, String msg) throws QueryException; + + /** + * Returns the set of BUILD, included, sub-included and Skylark files that define the given set of + * targets. Each such file is itself represented as a target in the result. + */ + Set<T> getBuildFiles(QueryExpression caller, Set<T> nodes) throws QueryException; + + /** + * Returns an object that can be used to query information about targets. Implementations should + * create a single instance and return that for all calls. A class can implement both {@code + * QueryEnvironment} and {@code TargetAccessor} at the same time, in which case this method simply + * returns {@code this}. + */ + TargetAccessor<T> getAccessor(); + + /** + * Whether the given setting is enabled. The code should default to return {@code false} for all + * unknown settings. The enum is used rather than a method for each setting so that adding more + * settings is backwards-compatible. + * + * @throws NullPointerException if setting is null + */ + boolean isSettingEnabled(@Nonnull Setting setting); + + /** + * Returns the set of query functions implemented by this query environment. + */ + Iterable<QueryFunction> getFunctions(); + + /** + * Settings for the query engine. See {@link QueryEnvironment#isSettingEnabled}. + */ + public static enum Setting { + + /** + * Whether to evaluate tests() expressions in strict mode. If {@link #isSettingEnabled} returns + * true for this setting, then the tests() expression will give an error when expanding tests + * suites, if the test suite contains any non-test targets. + */ + TESTS_EXPRESSION_STRICT, + + /** + * Do not consider implicit deps (any label that was not explicitly specified in the BUILD file) + * when traversing dependency edges. + */ + NO_IMPLICIT_DEPS, + + /** + * Do not consider host dependencies when traversing dependency edges. + */ + NO_HOST_DEPS, + + /** + * Do not consider nodep attributes when traversing dependency edges. + */ + NO_NODEP_DEPS; + } + + /** + * An adapter interface giving access to properties of T. There are four types of targets: rules, + * package groups, source files, and generated files. Of these, only rules can have attributes. + */ + public static interface TargetAccessor<T> { + /** + * Returns the target type represented as a string of the form {@code <type> rule} or + * {@code package group} or {@code source file} or {@code generated file}. This is widely used + * for target filtering, so implementations must use the Blaze rule class naming scheme. + */ + String getTargetKind(T target); + + /** + * Returns the full label of the target as a string, e.g. {@code //some:target}. + */ + String getLabel(T target); + + /** + * Returns whether the given target is a rule. + */ + boolean isRule(T target); + + /** + * Returns whether the given target is a test target. If this returns true, then {@link #isRule} + * must also return true for the target. + */ + boolean isTestRule(T target); + + /** + * Returns whether the given target is a test suite target. If this returns true, then {@link + * #isRule} must also return true for the target, but {@link #isTestRule} must return false; + * test suites are not test rules, and vice versa. + */ + boolean isTestSuite(T target); + + /** + * If the attribute of the given name on the given target is a label or label list, then this + * method returns the list of corresponding target instances. Otherwise returns an empty list. + * If an error occurs during resolution, it throws a {@link QueryException} using the caller and + * error message prefix. + * + * @throws IllegalArgumentException if target is not a rule (according to {@link #isRule}) + */ + List<T> getLabelListAttr(QueryExpression caller, T target, String attrName, + String errorMsgPrefix) throws QueryException; + + /** + * If the attribute of the given name on the given target is a string list, then this method + * returns it. + * + * @throws IllegalArgumentException if target is not a rule (according to {@link #isRule}), or + * if the target does not have an attribute of type string list + * with the given name + */ + List<String> getStringListAttr(T target, String attrName); + + /** + * If the attribute of the given name on the given target is a string, then this method returns + * it. + * + * @throws IllegalArgumentException if target is not a rule (according to {@link #isRule}), or + * if the target does not have an attribute of type string with + * the given name + */ + String getStringAttr(T target, String attrName); + + /** + * Returns the given attribute represented as a list of strings. For "normal" attributes, + * this should just be a list of size one containing the attribute's value. For configurable + * attributes, there should be one entry for each possible value the attribute may take. + * + *<p>Note that for backwards compatibility, tristate and boolean attributes are returned as + * int using the values {@code 0, 1} and {@code -1}. If there is no such attribute, this + * method returns an empty list. + * + * @throws IllegalArgumentException if target is not a rule (according to {@link #isRule}) + */ + Iterable<String> getAttrAsString(T target, String attrName); + } + + /** List of the default query functions. */ + public static final List<QueryFunction> DEFAULT_QUERY_FUNCTIONS = + ImmutableList.<QueryFunction>of( + new AllPathsFunction(), + new BuildFilesFunction(), + new AttrFunction(), + new FilterFunction(), + new LabelsFunction(), + new KindFunction(), + new SomeFunction(), + new SomePathFunction(), + new TestsFunction(), + new DepsFunction(), + new RdepsFunction() + ); +} diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/QueryEvalResult.java b/src/main/java/com/google/devtools/build/lib/query2/engine/QueryEvalResult.java new file mode 100644 index 0000000000..5bcea7e3b3 --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/query2/engine/QueryEvalResult.java @@ -0,0 +1,51 @@ +// Copyright 2015 Google Inc. All rights reserved. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +package com.google.devtools.build.lib.query2.engine; + +import com.google.common.base.Preconditions; + +import java.util.Set; + +/** + * The result of a query evaluation, containing a set of elements. + * + * @param <T> the node type of the elements. + */ +public class QueryEvalResult<T> { + + protected final boolean success; + protected final Set<T> resultSet; + + public QueryEvalResult( + boolean success, Set<T> resultSet) { + this.success = success; + this.resultSet = Preconditions.checkNotNull(resultSet); + } + + /** + * Whether the query was successful. This can only be false if the query was run with + * <code>keep_going</code>, otherwise evaluation will throw a {@link QueryException}. + */ + public boolean getSuccess() { + return success; + } + + /** + * Returns the result as a set of targets. + */ + public Set<T> getResultSet() { + return resultSet; + } +} diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/QueryException.java b/src/main/java/com/google/devtools/build/lib/query2/engine/QueryException.java new file mode 100644 index 0000000000..71c1a8a8a6 --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/query2/engine/QueryException.java @@ -0,0 +1,58 @@ +// Copyright 2014 Google Inc. All rights reserved. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. +package com.google.devtools.build.lib.query2.engine; + +/** + */ +public class QueryException extends Exception { + + /** + * Returns a better error message for the query. + */ + static String describeFailedQuery(QueryException e, QueryExpression toplevel) { + QueryExpression badQuery = e.getFailedExpression(); + if (badQuery == null) { + return "Evaluation failed: " + e.getMessage(); + } + return badQuery == toplevel + ? "Evaluation of query \"" + toplevel + "\" failed: " + e.getMessage() + : "Evaluation of subquery \"" + badQuery + + "\" failed (did you want to use --keep_going?): " + e.getMessage(); + } + + private final QueryExpression expression; + + public QueryException(QueryException e, QueryExpression toplevel) { + super(describeFailedQuery(e, toplevel), e); + this.expression = null; + } + + public QueryException(QueryExpression expression, String message) { + super(message); + this.expression = expression; + } + + public QueryException(String message) { + this(null, message); + } + + /** + * Returns the subexpression for which evaluation failed, or null if + * the failure occurred during lexing/parsing. + */ + public QueryExpression getFailedExpression() { + return expression; + } + +} diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/QueryExpression.java b/src/main/java/com/google/devtools/build/lib/query2/engine/QueryExpression.java new file mode 100644 index 0000000000..23603f16ff --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/query2/engine/QueryExpression.java @@ -0,0 +1,83 @@ +// Copyright 2014 Google Inc. All rights reserved. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. +package com.google.devtools.build.lib.query2.engine; + +import java.util.Collection; +import java.util.Set; + +/** + * Base class for expressions in the Blaze query language, revision 2. + * + * <p>All queries return a subgraph of the dependency graph, represented + * as a set of target nodes. + * + * <p>All queries must ensure that sufficient graph edges are created in the + * QueryEnvironment so that all nodes in the result are correctly ordered + * according to the type of query. For example, "deps" queries require that + * all the nodes in the transitive closure of its argument set are correctly + * ordered w.r.t. each other; "somepath" queries require that the order of the + * nodes on the resulting path are correctly ordered; algebraic set operations + * such as intersect and union are inherently unordered. + * + * <h2>Package overview</h2> + * + * <p>This package consists of two basic class hierarchies. The first, {@code + * QueryExpression}, is the set of different query expressions in the language, + * and the {@link #eval} method of each defines the semantics. The result of + * evaluating a query is set of Blaze {@code Target}s (a file or rule). The + * set may be interpreted as either a set or as nodes of a DAG, depending on + * the context. + * + * <p>The second hierarchy is {@code OutputFormatter}. Its subclasses define + * different ways of printing out the result of a query. Each accepts a {@code + * Digraph} of {@code Target}s, and an output stream. + */ +public abstract class QueryExpression { + + /** + * Scan and parse the specified query expression. + */ + public static QueryExpression parse(String query, QueryEnvironment<?> env) + throws QueryException { + return QueryParser.parse(query, env); + } + + protected QueryExpression() {} + + /** + * Evaluates this query in the specified environment, and returns a subgraph, + * concretely represented a new (possibly-immutable) set of target nodes. + * + * Failures resulting from evaluation of an ill-formed query cause + * QueryException to be thrown. + * + * The reporting of failures arising from errors in BUILD files depends on + * the --keep_going flag. If enabled (the default), then QueryException is + * thrown. If disabled, evaluation will stumble on to produce a (possibly + * inaccurate) result, but a result nonetheless. + */ + public abstract <T> Set<T> eval(QueryEnvironment<T> env) throws QueryException; + + /** + * Collects all target patterns that are referenced anywhere within this query expression and adds + * them to the given collection, which must be mutable. + */ + public abstract void collectTargetPatterns(Collection<String> literals); + + /** + * Returns this query expression pretty-printed. + */ + @Override + public abstract String toString(); +} diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/QueryParser.java b/src/main/java/com/google/devtools/build/lib/query2/engine/QueryParser.java new file mode 100644 index 0000000000..bcd89cc31b --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/query2/engine/QueryParser.java @@ -0,0 +1,261 @@ +// Copyright 2014 Google Inc. All rights reserved. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. +package com.google.devtools.build.lib.query2.engine; + +import static com.google.devtools.build.lib.query2.engine.Lexer.BINARY_OPERATORS; + +import com.google.devtools.build.lib.query2.engine.Lexer.TokenKind; +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.QueryFunction; + +import java.util.ArrayList; +import java.util.HashMap; +import java.util.Iterator; +import java.util.List; +import java.util.Map; + +/** + * LL(1) recursive descent parser for the Blaze query language, revision 2. + * + * In the grammar below, non-terminals are lowercase and terminals are + * uppercase, or character literals. + * + * <pre> + * expr ::= WORD + * | LET WORD = expr IN expr + * | '(' expr ')' + * | WORD '(' expr ( ',' expr ) * ')' + * | expr INTERSECT expr + * | expr '^' expr + * | expr UNION expr + * | expr '+' expr + * | expr EXCEPT expr + * | expr '-' expr + * | SET '(' WORD * ')' + * </pre> + */ +final class QueryParser { + + private Lexer.Token token; // current lookahead token + private final List<Lexer.Token> tokens; + private final Iterator<Lexer.Token> tokenIterator; + private final Map<String, QueryFunction> functions; + + /** + * Scan and parse the specified query expression. + */ + static QueryExpression parse(String query, QueryEnvironment<?> env) throws QueryException { + QueryParser parser = new QueryParser( + Lexer.scan(query.toCharArray()), env); + QueryExpression expr = parser.parseExpression(); + if (parser.token.kind != TokenKind.EOF) { + throw new QueryException("unexpected token '" + parser.token + + "' after query expression '" + expr + "'"); + } + return expr; + } + + private QueryParser(List<Lexer.Token> tokens, QueryEnvironment<?> env) { + this.functions = new HashMap<>(); + for (QueryFunction queryFunction : env.getFunctions()) { + this.functions.put(queryFunction.getName(), queryFunction); + } + this.tokens = tokens; + this.tokenIterator = tokens.iterator(); + nextToken(); + } + + /** + * Returns an exception. Don't forget to throw it. + */ + private QueryException syntaxError(Lexer.Token token) { + String message = "premature end of input"; + if (token.kind != TokenKind.EOF) { + StringBuilder buf = new StringBuilder("syntax error at '"); + String sep = ""; + for (int index = tokens.indexOf(token), + max = Math.min(tokens.size() - 1, index + 3); // 3 tokens of context + index < max; ++index) { + buf.append(sep).append(tokens.get(index)); + sep = " "; + } + buf.append("'"); + message = buf.toString(); + } + return new QueryException(message); + } + + /** + * Consumes the current token. If it is not of the specified (expected) + * kind, throws QueryException. Returns the value associated with the + * consumed token, if any. + */ + private String consume(TokenKind kind) throws QueryException { + if (token.kind != kind) { + throw syntaxError(token); + } + String word = token.word; + nextToken(); + return word; + } + + /** + * Consumes the current token, which must be a WORD containing an integer + * literal. Returns that integer, or throws a QueryException otherwise. + */ + private int consumeIntLiteral() throws QueryException { + String intString = consume(TokenKind.WORD); + try { + return Integer.parseInt(intString); + } catch (NumberFormatException e) { + throw new QueryException("expected an integer literal: '" + intString + "'"); + } + } + + private void nextToken() { + if (token == null || token.kind != TokenKind.EOF) { + token = tokenIterator.next(); + } + } + + /** + * expr ::= primary + * | expr INTERSECT expr + * | expr '^' expr + * | expr UNION expr + * | expr '+' expr + * | expr EXCEPT expr + * | expr '-' expr + */ + private QueryExpression parseExpression() throws QueryException { + // All operators are left-associative and of equal precedence. + return parseBinaryOperatorTail(parsePrimary()); + } + + /** + * tail ::= ( <op> <primary> )* + * All operators have equal precedence. + * This factoring is required for left-associative binary operators in LL(1). + */ + private QueryExpression parseBinaryOperatorTail(QueryExpression lhs) throws QueryException { + if (!BINARY_OPERATORS.contains(token.kind)) { + return lhs; + } + + List<QueryExpression> operands = new ArrayList<>(); + operands.add(lhs); + TokenKind lastOperator = token.kind; + + while (BINARY_OPERATORS.contains(token.kind)) { + TokenKind operator = token.kind; + consume(operator); + if (operator != lastOperator) { + lhs = new BinaryOperatorExpression(lastOperator, operands); + operands.clear(); + operands.add(lhs); + lastOperator = operator; + } + QueryExpression rhs = parsePrimary(); + operands.add(rhs); + } + return new BinaryOperatorExpression(lastOperator, operands); + } + + /** + * primary ::= WORD + * | LET WORD = expr IN expr + * | '(' expr ')' + * | WORD '(' expr ( ',' expr ) * ')' + * | DEPS '(' expr ')' + * | DEPS '(' expr ',' WORD ')' + * | RDEPS '(' expr ',' expr ')' + * | RDEPS '(' expr ',' expr ',' WORD ')' + * | SET '(' WORD * ')' + */ + private QueryExpression parsePrimary() throws QueryException { + switch (token.kind) { + case WORD: { + String word = consume(TokenKind.WORD); + if (token.kind == TokenKind.LPAREN) { + QueryFunction function = functions.get(word); + if (function == null) { + throw syntaxError(token); + } + List<Argument> args = new ArrayList<>(); + TokenKind tokenKind = TokenKind.LPAREN; + int argsSeen = 0; + for (ArgumentType type : function.getArgumentTypes()) { + if (token.kind == TokenKind.RPAREN && argsSeen >= function.getMandatoryArguments()) { + break; + } + + consume(tokenKind); + tokenKind = TokenKind.COMMA; + switch (type) { + case EXPRESSION: + args.add(Argument.of(parseExpression())); + break; + + case WORD: + args.add(Argument.of(consume(TokenKind.WORD))); + break; + + case INTEGER: + args.add(Argument.of(consumeIntLiteral())); + break; + + default: + throw new IllegalStateException(); + } + + argsSeen++; + } + + consume(TokenKind.RPAREN); + return new FunctionExpression(function, args); + } else { + return new TargetLiteral(word); + } + } + case LET: { + consume(TokenKind.LET); + String name = consume(TokenKind.WORD); + consume(TokenKind.EQUALS); + QueryExpression varExpr = parseExpression(); + consume(TokenKind.IN); + QueryExpression bodyExpr = parseExpression(); + return new LetExpression(name, varExpr, bodyExpr); + } + case LPAREN: { + consume(TokenKind.LPAREN); + QueryExpression expr = parseExpression(); + consume(TokenKind.RPAREN); + return expr; + } + case SET: { + nextToken(); + consume(TokenKind.LPAREN); + List<TargetLiteral> words = new ArrayList<>(); + while (token.kind == TokenKind.WORD) { + words.add(new TargetLiteral(consume(TokenKind.WORD))); + } + consume(TokenKind.RPAREN); + return new SetExpression(words); + } + default: + throw syntaxError(token); + } + } +} diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/RdepsFunction.java b/src/main/java/com/google/devtools/build/lib/query2/engine/RdepsFunction.java new file mode 100644 index 0000000000..6a8734bb3f --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/query2/engine/RdepsFunction.java @@ -0,0 +1,99 @@ +// Copyright 2014 Google Inc. All rights reserved. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. +package com.google.devtools.build.lib.query2.engine; + +import com.google.common.collect.ImmutableList; +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.QueryFunction; + +import java.util.ArrayList; +import java.util.Collection; +import java.util.LinkedHashSet; +import java.util.List; +import java.util.Set; + +/** + * An "rdeps" query expression, which computes the reverse dependencies of the argument within the + * transitive closure of the universe. An optional integer-literal third argument may be + * specified; its value bounds the search from the arguments. + * + * <pre>expr ::= RDEPS '(' expr ',' expr ')'</pre> + * <pre> | RDEPS '(' expr ',' expr ',' WORD ')'</pre> + */ +final class RdepsFunction implements QueryFunction { + RdepsFunction() { + } + + @Override + public String getName() { + return "rdeps"; + } + + @Override + public int getMandatoryArguments() { + return 2; // last argument is optional + } + + @Override + public List<ArgumentType> getArgumentTypes() { + return ImmutableList.of( + ArgumentType.EXPRESSION, ArgumentType.EXPRESSION, ArgumentType.INTEGER); + } + + /** + * Compute the transitive closure of the universe, then breadth-first search from the argument + * towards the universe while staying within the transitive closure. + */ + @Override + public <T> Set<T> eval(QueryEnvironment<T> env, QueryExpression expression, List<Argument> args) + throws QueryException { + Set<T> universeValue = args.get(0).getExpression().eval(env); + Set<T> argumentValue = args.get(1).getExpression().eval(env); + int depthBound = args.size() > 2 ? args.get(2).getInteger() : Integer.MAX_VALUE; + + env.buildTransitiveClosure(expression, universeValue, Integer.MAX_VALUE); + + Set<T> visited = new LinkedHashSet<>(); + Set<T> reachableFromUniverse = env.getTransitiveClosure(universeValue); + Collection<T> current = argumentValue; + + // We need to iterate depthBound + 1 times. + for (int i = 0; i <= depthBound; i++) { + List<T> next = new ArrayList<>(); + for (T node : current) { + if (!reachableFromUniverse.contains(node)) { + // Traversed outside the transitive closure of the universe. + continue; + } + + if (!visited.add(node)) { + // Already visited; if we see a node in a later round, then we don't need to visit it + // again, because the depth at which we see it at must be greater than or equal to the + // last visit. + continue; + } + + next.addAll(env.getReverseDeps(node)); + } + if (next.isEmpty()) { + // Exit when there are no more nodes to visit. + break; + } + current = next; + } + + return visited; + } +} diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/RegexFilterExpression.java b/src/main/java/com/google/devtools/build/lib/query2/engine/RegexFilterExpression.java new file mode 100644 index 0000000000..1dbe5e63d3 --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/query2/engine/RegexFilterExpression.java @@ -0,0 +1,83 @@ +// Copyright 2014 Google Inc. All rights reserved. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. +package com.google.devtools.build.lib.query2.engine; + +import com.google.common.collect.ImmutableList; +import com.google.devtools.build.lib.query2.engine.QueryEnvironment.Argument; +import com.google.devtools.build.lib.query2.engine.QueryEnvironment.QueryFunction; + +import java.util.LinkedHashSet; +import java.util.List; +import java.util.Set; +import java.util.regex.Pattern; + +/** + * An abstract class that provides generic regex filter expression. Actual + * expression are implemented by the subclasses. + */ +abstract class RegexFilterExpression implements QueryFunction { + protected RegexFilterExpression() { + } + + @Override + public <T> Set<T> eval(QueryEnvironment<T> env, QueryExpression expression, List<Argument> args) + throws QueryException { + Pattern compiledPattern; + try { + compiledPattern = Pattern.compile(getPattern(args)); + } catch (IllegalArgumentException e) { + throw new QueryException(expression, "illegal pattern regexp in '" + this + "': " + + e.getMessage()); + } + + QueryExpression argument = args.get(args.size() - 1).getExpression(); + + Set<T> result = new LinkedHashSet<>(); + for (T target : argument.eval(env)) { + for (String str : getFilterStrings(env, args, target)) { + if ((str != null) && compiledPattern.matcher(str).find()) { + result.add(target); + break; + } + } + } + return result; + } + + /** + * Returns string for the given target that must be matched against pattern. + * May return null, in which case matching is guaranteed to fail. + */ + protected abstract <T> String getFilterString( + QueryEnvironment<T> env, List<Argument> args, T target); + + /** + * Returns a list of strings for the given target that must be matched against + * pattern. The filter matches if *any* of these strings matches. + * + * <p>Unless subclasses have an explicit reason to override this method, it's fine + * to keep the default implementation that just delegates to {@link #getFilterString}. + * Overriding this method is useful for subclasses that want to match against a + * universe of possible values. For example, with configurable attributes, an + * attribute might have different values depending on the build configuration. One + * may wish the filter to match if *any* of those values matches. + */ + protected <T> Iterable<String> getFilterStrings( + QueryEnvironment<T> env, List<Argument> args, T target) { + String filterString = getFilterString(env, args, target); + return filterString == null ? ImmutableList.<String>of() : ImmutableList.of(filterString); + } + + protected abstract String getPattern(List<Argument> args); +} diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/SetExpression.java b/src/main/java/com/google/devtools/build/lib/query2/engine/SetExpression.java new file mode 100644 index 0000000000..a28c679fbb --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/query2/engine/SetExpression.java @@ -0,0 +1,70 @@ +// Copyright 2014 Google Inc. All rights reserved. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. +package com.google.devtools.build.lib.query2.engine; + +import com.google.common.base.Joiner; + +import java.util.Collection; +import java.util.LinkedHashSet; +import java.util.List; +import java.util.Set; + +/** + * A set(word, ..., word) expression, which computes the union of zero or more + * target patterns separated by whitespace. This is intended to support the + * use-case in which a set of labels written to a file by a previous query + * expression can be modified externally, then used as input to another query, + * like so: + * + * <pre> + * % blaze query 'somepath(foo, bar)' | grep ... | sed ... | awk ... >file + * % blaze query "kind(qux_library, set($(<file)))" + * </pre> + * + * <p>The grammar currently restricts the operands of set() to being zero or + * more words (target patterns), with no intervening punctuation. In principle + * this could be extended to arbitrary expressions without grammatical + * ambiguity, but this seems excessively general for now. + * + * <pre>expr ::= SET '(' WORD * ')'</pre> + */ +class SetExpression extends QueryExpression { + + private final List<TargetLiteral> words; + + SetExpression(List<TargetLiteral> words) { + this.words = words; + } + + @Override + public <T> Set<T> eval(QueryEnvironment<T> env) throws QueryException { + Set<T> result = new LinkedHashSet<>(); + for (TargetLiteral expr : words) { + result.addAll(expr.eval(env)); + } + return result; + } + + @Override + public void collectTargetPatterns(Collection<String> literals) { + for (TargetLiteral expr : words) { + expr.collectTargetPatterns(literals); + } + } + + @Override + public String toString() { + return "set(" + Joiner.on(' ').join(words) + ")"; + } +} diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/SkyframeRestartQueryException.java b/src/main/java/com/google/devtools/build/lib/query2/engine/SkyframeRestartQueryException.java new file mode 100644 index 0000000000..d720ec9e11 --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/query2/engine/SkyframeRestartQueryException.java @@ -0,0 +1,24 @@ +// Copyright 2014 Google Inc. All rights reserved. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. +package com.google.devtools.build.lib.query2.engine; + +/** + * This exception is thrown when a query operation was unable to complete because of a Skyframe + * missing dependency. + */ +public class SkyframeRestartQueryException extends RuntimeException { + public SkyframeRestartQueryException() { + super("need skyframe retry. missing dep"); + } +} diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/SomeFunction.java b/src/main/java/com/google/devtools/build/lib/query2/engine/SomeFunction.java new file mode 100644 index 0000000000..384b4740ad --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/query2/engine/SomeFunction.java @@ -0,0 +1,59 @@ +// Copyright 2014 Google Inc. All rights reserved. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. +package com.google.devtools.build.lib.query2.engine; + +import com.google.common.collect.ImmutableList; +import com.google.common.collect.ImmutableSet; +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.QueryFunction; + +import java.util.List; +import java.util.Set; + +/** + * A some(x) filter expression, which returns an arbitrary node in set x, or + * fails if x is empty. + * + * <pre>expr ::= SOME '(' expr ')'</pre> + */ +class SomeFunction implements QueryFunction { + SomeFunction() { + } + + @Override + public String getName() { + return "some"; + } + + @Override + public int getMandatoryArguments() { + return 1; + } + + @Override + public List<ArgumentType> getArgumentTypes() { + return ImmutableList.of(ArgumentType.EXPRESSION); + } + + @Override + public <T> Set<T> eval(QueryEnvironment<T> env, QueryExpression expression, List<Argument> args) + throws QueryException { + Set<T> argumentValue = args.get(0).getExpression().eval(env); + if (argumentValue.isEmpty()) { + throw new QueryException(expression, "argument set is empty"); + } + return ImmutableSet.of(argumentValue.iterator().next()); + } +} diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/SomePathFunction.java b/src/main/java/com/google/devtools/build/lib/query2/engine/SomePathFunction.java new file mode 100644 index 0000000000..b90bcdfde9 --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/query2/engine/SomePathFunction.java @@ -0,0 +1,87 @@ +// Copyright 2014 Google Inc. All rights reserved. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. +package com.google.devtools.build.lib.query2.engine; + +import com.google.common.collect.ImmutableList; +import com.google.common.collect.ImmutableSet; +import com.google.common.collect.Sets; +import com.google.common.collect.Sets.SetView; +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.QueryFunction; + +import java.util.HashSet; +import java.util.List; +import java.util.Set; + +/** + * A somepath(x, y) query expression, which computes the set of nodes + * on some arbitrary path from a target in set x to a target in set y. + * + * <pre>expr ::= SOMEPATH '(' expr ',' expr ')'</pre> + */ +class SomePathFunction implements QueryFunction { + SomePathFunction() { + } + + @Override + public String getName() { + return "somepath"; + } + + @Override + public int getMandatoryArguments() { + return 2; + } + + @Override + public List<ArgumentType> getArgumentTypes() { + return ImmutableList.of(ArgumentType.EXPRESSION, ArgumentType.EXPRESSION); + } + + @Override + public <T> Set<T> eval(QueryEnvironment<T> env, QueryExpression expression, List<Argument> args) + throws QueryException { + Set<T> fromValue = args.get(0).getExpression().eval(env); + Set<T> toValue = args.get(1).getExpression().eval(env); + + // Implementation strategy: for each x in "from", compute its forward + // transitive closure. If it intersects "to", then do a path search from x + // to an arbitrary node in the intersection, and return the path. This + // avoids computing the full transitive closure of "from" in some cases. + + env.buildTransitiveClosure(expression, fromValue, Integer.MAX_VALUE); + + // This set contains all nodes whose TC does not intersect "toValue". + Set<T> done = new HashSet<>(); + + for (T x : fromValue) { + if (done.contains(x)) { + continue; + } + Set<T> xtc = env.getTransitiveClosure(ImmutableSet.of(x)); + SetView<T> result; + if (xtc.size() > toValue.size()) { + result = Sets.intersection(toValue, xtc); + } else { + result = Sets.intersection(xtc, toValue); + } + if (!result.isEmpty()) { + return env.getNodesOnPath(x, result.iterator().next()); + } + done.addAll(xtc); + } + return ImmutableSet.of(); + } +} diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/TargetLiteral.java b/src/main/java/com/google/devtools/build/lib/query2/engine/TargetLiteral.java new file mode 100644 index 0000000000..b6a57cc5a5 --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/query2/engine/TargetLiteral.java @@ -0,0 +1,72 @@ +// Copyright 2014 Google Inc. All rights reserved. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. +package com.google.devtools.build.lib.query2.engine; + +import com.google.common.base.Preconditions; + +import java.util.Collection; +import java.util.Set; + +/** + * A literal set of targets, using 'blaze build' syntax. Or, a reference to a + * variable name. (The syntax of the string "pattern" determines which.) + * + * TODO(bazel-team): Perhaps we should distinguish NAME from WORD in the parser, + * based on the characters in it? Also, perhaps we should not allow NAMEs to + * be quoted like WORDs can be. + * + * <pre>expr ::= NAME | WORD</pre> + */ +final class TargetLiteral extends QueryExpression { + + private final String pattern; + + TargetLiteral(String pattern) { + this.pattern = Preconditions.checkNotNull(pattern); + } + + public boolean isVariableReference() { + return LetExpression.isValidVarReference(pattern); + } + + @Override + public <T> Set<T> eval(QueryEnvironment<T> env) throws QueryException { + if (isVariableReference()) { + String varName = LetExpression.getNameFromReference(pattern); + Set<T> value = env.getVariable(varName); + if (value == null) { + throw new QueryException(this, "undefined variable '" + varName + "'"); + } + return env.getVariable(varName); + } + + return env.getTargetsMatchingPattern(this, pattern); + } + + @Override + public void collectTargetPatterns(Collection<String> literals) { + if (!isVariableReference()) { + literals.add(pattern); + } + } + + @Override + public String toString() { + // Keep predicate consistent with Lexer.scanWord! + boolean needsQuoting = Lexer.isReservedWord(pattern) + || pattern.isEmpty() + || "$-*".indexOf(pattern.charAt(0)) != -1; + return needsQuoting ? ("\"" + pattern + "\"") : pattern; + } +} diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/TestsFunction.java b/src/main/java/com/google/devtools/build/lib/query2/engine/TestsFunction.java new file mode 100644 index 0000000000..c902609b9f --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/query2/engine/TestsFunction.java @@ -0,0 +1,257 @@ +// Copyright 2014 Google Inc. All rights reserved. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. +package com.google.devtools.build.lib.query2.engine; + +import com.google.common.collect.ImmutableList; +import com.google.common.collect.Sets; +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.QueryFunction; +import com.google.devtools.build.lib.query2.engine.QueryEnvironment.Setting; + +import java.util.ArrayList; +import java.util.Collection; +import java.util.HashMap; +import java.util.HashSet; +import java.util.Iterator; +import java.util.List; +import java.util.Map; +import java.util.Set; + +/** + * A tests(x) filter expression, which returns all the tests in set x, + * expanding test_suite rules into their constituents. + * + * <p>Unfortunately this class reproduces a substantial amount of logic from + * {@code TestSuiteConfiguredTarget}, albeit in a somewhat simplified form. + * This is basically inevitable since the expansion of test_suites cannot be + * done during the loading phase, because it involves inter-package references. + * We make no attempt to validate the input, or report errors or warnings other + * than missing target. + * + * <pre>expr ::= TESTS '(' expr ')'</pre> + */ +class TestsFunction implements QueryFunction { + TestsFunction() { + } + + @Override + public String getName() { + return "tests"; + } + + @Override + public int getMandatoryArguments() { + return 1; + } + + @Override + public List<ArgumentType> getArgumentTypes() { + return ImmutableList.of(ArgumentType.EXPRESSION); + } + + @Override + public <T> Set<T> eval(QueryEnvironment<T> env, QueryExpression expression, List<Argument> args) + throws QueryException { + Closure<T> closure = new Closure<>(expression, env); + Set<T> result = new HashSet<>(); + for (T target : args.get(0).getExpression().eval(env)) { + if (env.getAccessor().isTestRule(target)) { + result.add(target); + } else if (env.getAccessor().isTestSuite(target)) { + for (T test : closure.getTestsInSuite(target)) { + result.add(env.getOrCreate(test)); + } + } + } + return result; + } + + /** + * Decides whether to include a test in a test_suite or not. + * @param testTags Collection of all tags exhibited by a given test. + * @param positiveTags Tags declared by the suite. A test must match ALL of these. + * @param negativeTags Tags declared by the suite. A test must match NONE of these. + * @return false is the test is to be removed. + */ + private static boolean includeTest(Collection<String> testTags, + Collection<String> positiveTags, Collection<String> negativeTags) { + // Add this test if it matches ALL of the positive tags and NONE of the + // negative tags in the tags attribute. + for (String tag : negativeTags) { + if (testTags.contains(tag)) { + return false; + } + } + for (String tag : positiveTags) { + if (!testTags.contains(tag)) { + return false; + } + } + return true; + } + + /** + * Separates a list of text "tags" into a Pair of Collections, where + * the first element are the required or positive tags and the second element + * are the excluded or negative tags. + * This should work on tag list provided from the command line + * --test_tags_filters flag or on tag filters explicitly declared in the + * suite. + * + * Keep this function in sync with the version in + * java.com.google.devtools.build.lib.view.packages.TestTargetUtils.sortTagsBySense + * + * @param tagList A collection of text tags to separate. + */ + private static void sortTagsBySense( + Collection<String> tagList, Set<String> requiredTags, Set<String> excludedTags) { + for (String tag : tagList) { + if (tag.startsWith("-")) { + excludedTags.add(tag.substring(1)); + } else if (tag.startsWith("+")) { + requiredTags.add(tag.substring(1)); + } else if (tag.equals("manual")) { + // Ignore manual attribute because it is an exception: it is not a filter + // but a property of test_suite + continue; + } else { + requiredTags.add(tag); + } + } + } + + /** + * A closure over the temporary state needed to compute the expression. This makes the evaluation + * thread-safe, as long as instances of this class are used only within a single thread. + */ + private final class Closure<T> { + private final QueryExpression expression; + /** A dynamically-populated mapping from test_suite rules to their tests. */ + private final Map<T, Set<T>> testsInSuite = new HashMap<>(); + + /** The environment in which this query is being evaluated. */ + private final QueryEnvironment<T> env; + + private final boolean strict; + + private Closure(QueryExpression expression, QueryEnvironment<T> env) { + this.expression = expression; + this.env = env; + this.strict = env.isSettingEnabled(Setting.TESTS_EXPRESSION_STRICT); + } + + /** + * Computes and returns the set of test rules in a particular suite. Uses + * dynamic programming---a memoized version of {@link #computeTestsInSuite}. + * + * @precondition env.getAccessor().isTestSuite(testSuite) + */ + private Set<T> getTestsInSuite(T testSuite) throws QueryException { + Set<T> tests = testsInSuite.get(testSuite); + if (tests == null) { + tests = Sets.newHashSet(); + testsInSuite.put(testSuite, tests); // break cycles by inserting empty set early. + computeTestsInSuite(testSuite, tests); + } + return tests; + } + + /** + * Populates 'result' with all the tests associated with the specified + * 'testSuite'. Throws an exception if any target is missing. + * + * <p>CAUTION! Keep this logic consistent with {@code TestsSuiteConfiguredTarget}! + * + * @precondition env.getAccessor().isTestSuite(testSuite) + */ + private void computeTestsInSuite(T testSuite, Set<T> result) throws QueryException { + List<T> testsAndSuites = new ArrayList<>(); + // Note that testsAndSuites can contain input file targets; the test_suite rule does not + // restrict the set of targets that can appear in tests or suites. + testsAndSuites.addAll(getPrerequisites(testSuite, "tests")); + testsAndSuites.addAll(getPrerequisites(testSuite, "suites")); + + // 1. Add all tests + for (T test : testsAndSuites) { + if (env.getAccessor().isTestRule(test)) { + result.add(test); + } else if (strict && !env.getAccessor().isTestSuite(test)) { + // If strict mode is enabled, then give an error for any non-test, non-test-suite targets. + env.reportBuildFileError(expression, "The label '" + + env.getAccessor().getLabel(test) + "' in the test_suite '" + + env.getAccessor().getLabel(testSuite) + "' does not refer to a test or test_suite " + + "rule!"); + } + } + + // 2. Add implicit dependencies on tests in same package, if any. + for (T target : getPrerequisites(testSuite, "$implicit_tests")) { + // The Package construction of $implicit_tests ensures that this check never fails, but we + // add it here anyway for compatibility with future code. + if (env.getAccessor().isTestRule(target)) { + result.add(target); + } + } + + // 3. Filter based on tags, size, env. + filterTests(testSuite, result); + + // 4. Expand all suites recursively. + for (T suite : testsAndSuites) { + if (env.getAccessor().isTestSuite(suite)) { + result.addAll(getTestsInSuite(suite)); + } + } + } + + /** + * Returns the set of rules named by the attribute 'attrName' of test_suite rule 'testSuite'. + * The attribute must be a list of labels. If a target cannot be resolved, then an error is + * reported to the environment (which may throw an exception if {@code keep_going} is disabled). + * + * @precondition env.getAccessor().isTestSuite(testSuite) + */ + private List<T> getPrerequisites(T testSuite, String attrName) throws QueryException { + return env.getAccessor().getLabelListAttr(expression, testSuite, attrName, + "couldn't expand '" + attrName + + "' attribute of test_suite " + env.getAccessor().getLabel(testSuite) + ": "); + } + + /** + * Filters 'tests' (by mutation) according to the 'tags' attribute, specifically those that + * match ALL of the tags in tagsAttribute. + * + * @precondition {@code env.getAccessor().isTestSuite(testSuite)} + * @precondition {@code env.getAccessor().isTestRule(test)} for all test in tests + */ + private void filterTests(T testSuite, Set<T> tests) { + List<String> tagsAttribute = env.getAccessor().getStringListAttr(testSuite, "tags"); + // Split the tags list into positive and negative tags + Set<String> requiredTags = new HashSet<>(); + Set<String> excludedTags = new HashSet<>(); + sortTagsBySense(tagsAttribute, requiredTags, excludedTags); + + Iterator<T> it = tests.iterator(); + while (it.hasNext()) { + T test = it.next(); + List<String> testTags = new ArrayList<>(env.getAccessor().getStringListAttr(test, "tags")); + testTags.add(env.getAccessor().getStringAttr(test, "size")); + if (!includeTest(testTags, requiredTags, excludedTags)) { + it.remove(); + } + } + } + } +} |