Line data Source code
1 : // Copyright (C) 2009 The Android Open Source Project
2 : //
3 : // Licensed under the Apache License, Version 2.0 (the "License");
4 : // you may not use this file except in compliance with the License.
5 : // You may obtain a copy of the License at
6 : //
7 : // http://www.apache.org/licenses/LICENSE-2.0
8 : //
9 : // Unless required by applicable law or agreed to in writing, software
10 : // distributed under the License is distributed on an "AS IS" BASIS,
11 : // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 : // See the License for the specific language governing permissions and
13 : // limitations under the License.
14 :
15 : package com.google.gerrit.index.query;
16 :
17 : import static com.google.common.base.Preconditions.checkArgument;
18 : import static com.google.gerrit.index.query.Predicate.and;
19 : import static com.google.gerrit.index.query.Predicate.not;
20 : import static com.google.gerrit.index.query.Predicate.or;
21 : import static com.google.gerrit.index.query.QueryParser.AND;
22 : import static com.google.gerrit.index.query.QueryParser.COLON;
23 : import static com.google.gerrit.index.query.QueryParser.DEFAULT_FIELD;
24 : import static com.google.gerrit.index.query.QueryParser.EXACT_PHRASE;
25 : import static com.google.gerrit.index.query.QueryParser.FIELD_NAME;
26 : import static com.google.gerrit.index.query.QueryParser.NOT;
27 : import static com.google.gerrit.index.query.QueryParser.OR;
28 : import static com.google.gerrit.index.query.QueryParser.SINGLE_WORD;
29 :
30 : import com.google.common.base.Ascii;
31 : import com.google.common.base.CharMatcher;
32 : import com.google.common.base.MoreObjects;
33 : import com.google.common.base.Strings;
34 : import com.google.common.base.Throwables;
35 : import com.google.common.collect.ImmutableMap;
36 : import com.google.gerrit.common.Nullable;
37 : import com.google.gerrit.extensions.registration.DynamicMap;
38 : import com.google.gerrit.extensions.registration.Extension;
39 : import java.lang.annotation.ElementType;
40 : import java.lang.annotation.Retention;
41 : import java.lang.annotation.RetentionPolicy;
42 : import java.lang.annotation.Target;
43 : import java.lang.reflect.InvocationTargetException;
44 : import java.lang.reflect.Method;
45 : import java.lang.reflect.Modifier;
46 : import java.util.ArrayList;
47 : import java.util.Collections;
48 : import java.util.List;
49 : import java.util.Map;
50 : import java.util.Optional;
51 : import org.antlr.runtime.CharStream;
52 : import org.antlr.runtime.CommonToken;
53 : import org.antlr.runtime.tree.CommonTree;
54 : import org.antlr.runtime.tree.Tree;
55 :
56 : /**
57 : * Base class to support writing parsers for query languages.
58 : *
59 : * <p>Subclasses may document their supported query operators by declaring public methods that
60 : * perform the query conversion into a {@link Predicate}. For example, to support "is:starred",
61 : * "is:unread", and nothing else, a subclass may write:
62 : *
63 : * <pre>
64 : * @Operator
65 : * public Predicate is(String value) {
66 : * if ("starred".equals(value)) {
67 : * return new StarredPredicate();
68 : * }
69 : * if ("unread".equals(value)) {
70 : * return new UnreadPredicate();
71 : * }
72 : * throw new IllegalArgumentException();
73 : * }
74 : * </pre>
75 : *
76 : * <p>The available operator methods are discovered at runtime via reflection. Method names (after
77 : * being converted to lowercase), correspond to operators in the query language, method string
78 : * values correspond to the operator argument. Methods must be declared {@code public}, returning
79 : * {@link Predicate}, accepting one {@link String}, and annotated with the {@link Operator}
80 : * annotation.
81 : *
82 : * <p>Subclasses may also declare a handler for values which appear without operator by overriding
83 : * {@link #defaultField(String)}.
84 : *
85 : * <p>Instances are non-singletons and should only be used once, in order to rescan the {@code
86 : * DynamicMap} of plugin-provided operators on each query invocation.
87 : *
88 : * @param <T> type of object the predicates can evaluate in memory.
89 : */
90 : public abstract class QueryBuilder<T, Q extends QueryBuilder<T, Q>> {
91 : /** Converts a value string passed to an operator into a {@link Predicate}. */
92 : public interface OperatorFactory<T, Q extends QueryBuilder<T, Q>> {
93 : Predicate<T> create(Q builder, String value) throws QueryParseException;
94 : }
95 :
96 : /**
97 : * Defines the operators known by a QueryBuilder.
98 : *
99 : * <p>Operators are discovered by scanning for methods annotated with {@link Operator}. Operator
100 : * methods must be public, non-abstract, return a {@code Predicate}, and take a single string as
101 : * an argument.
102 : *
103 : * <p>This class is deeply immutable.
104 : *
105 : * @param <T> type of object the predicates can evaluate.
106 : * @param <Q> type of the query builder subclass.
107 : */
108 : public static class Definition<T, Q extends QueryBuilder<T, Q>> {
109 : private final ImmutableMap<String, OperatorFactory<T, Q>> opFactories;
110 :
111 151 : public Definition(Class<? extends Q> clazz) {
112 151 : ImmutableMap.Builder<String, OperatorFactory<T, Q>> b = ImmutableMap.builder();
113 151 : Class<?> c = clazz;
114 151 : while (c != QueryBuilder.class) {
115 151 : for (Method method : c.getDeclaredMethods()) {
116 151 : if (method.getAnnotation(Operator.class) == null) {
117 150 : continue;
118 : }
119 151 : checkArgument(
120 151 : CharMatcher.ascii().matchesAllOf(method.getName()),
121 : "method name must be ASCII: %s",
122 151 : method.getName());
123 151 : checkArgument(
124 151 : Predicate.class.isAssignableFrom(method.getReturnType())
125 151 : && method.getParameterTypes().length == 1
126 151 : && method.getParameterTypes()[0] == String.class
127 151 : && Modifier.isPublic(method.getModifiers())
128 151 : && !Modifier.isAbstract(method.getModifiers()),
129 : "method must be of the form \"@%s public Predicate<T> %s(String value)\": %s",
130 151 : Operator.class.getSimpleName(),
131 151 : method.getName(),
132 : method);
133 151 : String name = Ascii.toLowerCase(method.getName());
134 151 : b.put(name, new ReflectionFactory<>(name, method));
135 : }
136 151 : c = c.getSuperclass();
137 : }
138 151 : opFactories = b.build();
139 151 : }
140 : }
141 :
142 : /**
143 : * Locate a predicate in the predicate tree.
144 : *
145 : * @param p the predicate to find.
146 : * @param clazz type of the predicate instance.
147 : * @return the predicate, null if not found.
148 : */
149 : @SuppressWarnings("unchecked")
150 : public static <T, P extends Predicate<T>> P find(Predicate<T> p, Class<P> clazz) {
151 0 : if (clazz.isAssignableFrom(p.getClass())) {
152 0 : return (P) p;
153 : }
154 :
155 0 : for (Predicate<T> c : p.getChildren()) {
156 0 : P r = find(c, clazz);
157 0 : if (r != null) {
158 0 : return r;
159 : }
160 0 : }
161 :
162 0 : return null;
163 : }
164 :
165 : /**
166 : * Locate a predicate in the predicate tree.
167 : *
168 : * @param p the predicate to find.
169 : * @param clazz type of the predicate instance.
170 : * @param name name of the operator.
171 : * @return the first instance of a predicate having the given type, as found by a depth-first
172 : * search.
173 : */
174 : @SuppressWarnings("unchecked")
175 : public static <T, P extends OperatorPredicate<T>> P find(
176 : Predicate<T> p, Class<P> clazz, String name) {
177 151 : if (p instanceof OperatorPredicate
178 151 : && ((OperatorPredicate<?>) p).getOperator().equals(name)
179 8 : && clazz.isAssignableFrom(p.getClass())) {
180 8 : return (P) p;
181 : }
182 :
183 151 : for (Predicate<T> c : p.getChildren()) {
184 117 : P r = find(c, clazz, name);
185 117 : if (r != null) {
186 7 : return r;
187 : }
188 117 : }
189 :
190 151 : return null;
191 : }
192 :
193 : protected final Definition<T, Q> builderDef;
194 : private final ImmutableMap<String, OperatorFactory<T, Q>> opFactories;
195 151 : protected Map<String, String> opAliases = Collections.emptyMap();
196 :
197 : protected QueryBuilder(
198 : Definition<T, Q> def,
199 151 : @Nullable DynamicMap<? extends OperatorFactory<T, Q>> dynamicOpFactories) {
200 151 : builderDef = def;
201 :
202 151 : if (dynamicOpFactories != null) {
203 : ImmutableMap.Builder<String, OperatorFactory<T, Q>> opFactoriesBuilder =
204 149 : ImmutableMap.builder();
205 149 : opFactoriesBuilder.putAll(def.opFactories);
206 149 : for (Extension<? extends OperatorFactory<T, Q>> e : dynamicOpFactories) {
207 2 : String name = e.getExportName() + "_" + e.getPluginName();
208 2 : opFactoriesBuilder.put(name, e.getProvider().get());
209 2 : }
210 149 : opFactories = opFactoriesBuilder.build();
211 149 : } else {
212 151 : opFactories = def.opFactories;
213 : }
214 151 : }
215 :
216 : /**
217 : * Parse a user-supplied query string into a predicate.
218 : *
219 : * @param query the query string.
220 : * @return predicate representing the user query.
221 : * @throws QueryParseException the query string is invalid and cannot be parsed by this parser.
222 : * This may be due to a syntax error, may be due to an operator not being supported, or due to
223 : * an invalid value being passed to a recognized operator.
224 : */
225 : public Predicate<T> parse(String query) throws QueryParseException {
226 50 : if (Strings.isNullOrEmpty(query)) {
227 0 : throw new QueryParseException("query is empty");
228 : }
229 50 : return toPredicate(QueryParser.parse(query));
230 : }
231 :
232 : public void setOperatorAliases(Map<String, String> opAliases) {
233 149 : this.opAliases = opAliases;
234 149 : }
235 :
236 : /**
237 : * Parse multiple user-supplied query strings into a list of predicates.
238 : *
239 : * @param queries the query strings.
240 : * @return predicates representing the user query, in the same order as the input.
241 : * @throws QueryParseException one of the query strings is invalid and cannot be parsed by this
242 : * parser. This may be due to a syntax error, may be due to an operator not being supported,
243 : * or due to an invalid value being passed to a recognized operator.
244 : */
245 : public List<Predicate<T>> parse(List<String> queries) throws QueryParseException {
246 26 : List<Predicate<T>> predicates = new ArrayList<>(queries.size());
247 26 : for (String query : queries) {
248 26 : predicates.add(parse(query));
249 26 : }
250 26 : return predicates;
251 : }
252 :
253 : private Predicate<T> toPredicate(Tree r) throws QueryParseException, IllegalArgumentException {
254 : Predicate<T> result;
255 50 : switch (r.getType()) {
256 : case AND:
257 22 : result = and(children(r));
258 22 : break;
259 : case OR:
260 27 : result = or(children(r));
261 27 : break;
262 : case NOT:
263 9 : result = not(toPredicate(onlyChildOf(r)));
264 9 : break;
265 :
266 : case DEFAULT_FIELD:
267 25 : result = defaultField(concatenateChildText(r));
268 25 : break;
269 :
270 : case FIELD_NAME:
271 48 : result = operator(r.getText(), concatenateChildText(r));
272 48 : break;
273 :
274 : default:
275 0 : throw error("Unsupported operator: " + r);
276 : }
277 50 : result.setPredicateString(getPredicateString(r));
278 50 : return result;
279 : }
280 :
281 : /**
282 : * Reconstruct the query sub-expression that was passed as input to the query parser from the tree
283 : * input parameter.
284 : */
285 : private static String getPredicateString(Tree r) {
286 50 : CommonTree ct = (CommonTree) r;
287 50 : CommonToken token = (CommonToken) ct.getToken();
288 50 : CharStream inputStream = token.getInputStream();
289 50 : int leftIdx = getLeftIndex(r);
290 50 : int rightIdx = getRightIndex(r);
291 50 : if (inputStream == null) {
292 34 : return "";
293 : }
294 48 : return inputStream.substring(leftIdx, rightIdx);
295 : }
296 :
297 : private static int getLeftIndex(Tree r) {
298 50 : CommonTree ct = (CommonTree) r;
299 50 : CommonToken token = (CommonToken) ct.getToken();
300 50 : return token.getStartIndex();
301 : }
302 :
303 : private static int getRightIndex(Tree r) {
304 50 : CommonTree ct = (CommonTree) r;
305 50 : if (ct.getChildCount() == 0) {
306 50 : CommonToken token = (CommonToken) ct.getToken();
307 50 : return token.getStopIndex();
308 : }
309 50 : return getRightIndex(ct.getChild(ct.getChildCount() - 1));
310 : }
311 :
312 : private static String concatenateChildText(Tree r) throws QueryParseException {
313 50 : if (r.getChildCount() == 0) {
314 0 : throw error("Expected children under: " + r);
315 : }
316 50 : if (r.getChildCount() == 1) {
317 50 : return getFieldValue(r.getChild(0));
318 : }
319 5 : StringBuilder sb = new StringBuilder();
320 5 : for (int i = 0; i < r.getChildCount(); i++) {
321 5 : sb.append(getFieldValue(r.getChild(i)));
322 : }
323 5 : return sb.toString();
324 : }
325 :
326 : private static String getFieldValue(Tree r) throws QueryParseException {
327 50 : if (r.getChildCount() != 0) {
328 0 : throw error("Expected no children under: " + r);
329 : }
330 50 : switch (r.getType()) {
331 : case SINGLE_WORD:
332 : case COLON:
333 : case EXACT_PHRASE:
334 50 : return r.getText();
335 : default:
336 0 : throw error(
337 0 : String.format(
338 : "Unsupported %s node in operator %s: %s",
339 0 : QueryParser.tokenNames[r.getType()], r.getParent(), r));
340 : }
341 : }
342 :
343 : @SuppressWarnings("unchecked")
344 : private Predicate<T> operator(String name, String value) throws QueryParseException {
345 48 : String opName = MoreObjects.firstNonNull(opAliases.get(name), name);
346 : @SuppressWarnings("rawtypes")
347 48 : OperatorFactory f = opFactories.get(opName);
348 48 : if (f == null && !opName.equals(name)) {
349 0 : f = opFactories.get(name);
350 : }
351 48 : if (f == null) {
352 3 : throw error("Unsupported operator " + name + ":" + value);
353 : }
354 48 : return f.create(this, value);
355 : }
356 :
357 : /**
358 : * Handle a value present outside of an operator.
359 : *
360 : * <p>This default implementation always throws an "Unsupported query: " message containing the
361 : * input text. Subclasses may override this method to perform do-what-i-mean guesses based on the
362 : * input string.
363 : *
364 : * @param value the value supplied by itself in the query.
365 : * @return predicate representing this value.
366 : * @throws QueryParseException the parser does not recognize this value.
367 : */
368 : protected Predicate<T> defaultField(String value) throws QueryParseException {
369 2 : throw error("Unsupported query: " + value);
370 : }
371 :
372 : private List<Predicate<T>> children(Tree r) throws QueryParseException, IllegalArgumentException {
373 34 : List<Predicate<T>> p = new ArrayList<>(r.getChildCount());
374 34 : for (int i = 0; i < r.getChildCount(); i++) {
375 34 : p.add(toPredicate(r.getChild(i)));
376 : }
377 34 : return p;
378 : }
379 :
380 : private Tree onlyChildOf(Tree r) throws QueryParseException {
381 9 : if (r.getChildCount() != 1) {
382 0 : throw error("Expected exactly one child: " + r);
383 : }
384 9 : return r.getChild(0);
385 : }
386 :
387 : protected static QueryParseException error(String msg) {
388 18 : return new QueryParseException(msg);
389 : }
390 :
391 : protected static QueryParseException error(String msg, Throwable why) {
392 2 : return new QueryParseException(msg, why);
393 : }
394 :
395 : /** Denotes a method which is a query operator. */
396 : @Retention(RetentionPolicy.RUNTIME)
397 : @Target(ElementType.METHOD)
398 : protected @interface Operator {}
399 :
400 : private static class ReflectionFactory<T, Q extends QueryBuilder<T, Q>>
401 : implements OperatorFactory<T, Q> {
402 : private final String name;
403 : private final Method method;
404 :
405 151 : ReflectionFactory(String name, Method method) {
406 151 : this.name = name;
407 151 : this.method = method;
408 151 : }
409 :
410 : @SuppressWarnings("unchecked")
411 : @Override
412 : public Predicate<T> create(Q builder, String value) throws QueryParseException {
413 : try {
414 48 : Predicate<T> predicate = (Predicate<T>) method.invoke(builder, value);
415 : // All operator predicates are leaf predicates.
416 48 : predicate.setLeaf(true);
417 48 : return predicate;
418 0 : } catch (RuntimeException | IllegalAccessException e) {
419 0 : throw error("Error in operator " + name + ":" + value, e);
420 18 : } catch (InvocationTargetException e) {
421 18 : Optional<QueryParseException> queryParseException =
422 18 : Throwables.getCausalChain(e).stream()
423 18 : .filter(QueryParseException.class::isInstance)
424 18 : .map(QueryParseException.class::cast)
425 18 : .findAny();
426 18 : if (queryParseException.isPresent()) {
427 18 : throw queryParseException.get();
428 : }
429 0 : throw error("Error in operator " + name + ":" + value, e.getCause());
430 : }
431 : }
432 : }
433 : }
|
