java/com/google/gerrit/index/query/QueryBuilder.java

// Copyright (C) 2009 The Android Open Source Project
//
// 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.gerrit.index.query;

import static com.google.common.base.Preconditions.checkArgument;
import static com.google.gerrit.index.query.Predicate.and;
import static com.google.gerrit.index.query.Predicate.not;
import static com.google.gerrit.index.query.Predicate.or;
import static com.google.gerrit.index.query.QueryParser.AND;
import static com.google.gerrit.index.query.QueryParser.COLON;
import static com.google.gerrit.index.query.QueryParser.DEFAULT_FIELD;
import static com.google.gerrit.index.query.QueryParser.EXACT_PHRASE;
import static com.google.gerrit.index.query.QueryParser.FIELD_NAME;
import static com.google.gerrit.index.query.QueryParser.NOT;
import static com.google.gerrit.index.query.QueryParser.OR;
import static com.google.gerrit.index.query.QueryParser.SINGLE_WORD;

import com.google.common.base.Ascii;
import com.google.common.base.CharMatcher;
import com.google.common.base.MoreObjects;
import com.google.common.base.Strings;
import com.google.common.base.Throwables;
import com.google.common.collect.ImmutableMap;
import com.google.gerrit.common.Nullable;
import com.google.gerrit.extensions.registration.DynamicMap;
import com.google.gerrit.extensions.registration.Extension;
import java.lang.annotation.ElementType;
import java.lang.annotation.Retention;
import java.lang.annotation.RetentionPolicy;
import java.lang.annotation.Target;
import java.lang.reflect.InvocationTargetException;
import java.lang.reflect.Method;
import java.lang.reflect.Modifier;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Map;
import java.util.Optional;
import org.antlr.runtime.CharStream;
import org.antlr.runtime.CommonToken;
import org.antlr.runtime.tree.CommonTree;
import org.antlr.runtime.tree.Tree;

/**
 * Base class to support writing parsers for query languages.
 *
 * <p>Subclasses may document their supported query operators by declaring public methods that
 * perform the query conversion into a {@link Predicate}. For example, to support "is:starred",
 * "is:unread", and nothing else, a subclass may write:
 *
 * <pre>
 * &#064;Operator
 * public Predicate is(String value) {
 *   if (&quot;starred&quot;.equals(value)) {
 *     return new StarredPredicate();
 *   }
 *   if (&quot;unread&quot;.equals(value)) {
 *     return new UnreadPredicate();
 *   }
 *   throw new IllegalArgumentException();
 * }
 * </pre>
 *
 * <p>The available operator methods are discovered at runtime via reflection. Method names (after
 * being converted to lowercase), correspond to operators in the query language, method string
 * values correspond to the operator argument. Methods must be declared {@code public}, returning
 * {@link Predicate}, accepting one {@link String}, and annotated with the {@link Operator}
 * annotation.
 *
 * <p>Subclasses may also declare a handler for values which appear without operator by overriding
 * {@link #defaultField(String)}.
 *
 * <p>Instances are non-singletons and should only be used once, in order to rescan the {@code
 * DynamicMap} of plugin-provided operators on each query invocation.
 *
 * @param <T> type of object the predicates can evaluate in memory.
 */
public abstract class QueryBuilder<T, Q extends QueryBuilder<T, Q>> {
  /** Converts a value string passed to an operator into a {@link Predicate}. */
  public interface OperatorFactory<T, Q extends QueryBuilder<T, Q>> {
    Predicate<T> create(Q builder, String value) throws QueryParseException;
  }

  /**
   * Defines the operators known by a QueryBuilder.
   *
   * <p>Operators are discovered by scanning for methods annotated with {@link Operator}. Operator
   * methods must be public, non-abstract, return a {@code Predicate}, and take a single string as
   * an argument.
   *
   * <p>This class is deeply immutable.
   *
   * @param <T> type of object the predicates can evaluate.
   * @param <Q> type of the query builder subclass.
   */
  public static class Definition<T, Q extends QueryBuilder<T, Q>> {
    private final ImmutableMap<String, OperatorFactory<T, Q>> opFactories;

    public Definition(Class<? extends Q> clazz) {
      ImmutableMap.Builder<String, OperatorFactory<T, Q>> b = ImmutableMap.builder();
      Class<?> c = clazz;
      while (c != QueryBuilder.class) {
        for (Method method : c.getDeclaredMethods()) {
          if (method.getAnnotation(Operator.class) == null) {
            continue;
          }
          checkArgument(
              CharMatcher.ascii().matchesAllOf(method.getName()),
              "method name must be ASCII: %s",
              method.getName());
          checkArgument(
              Predicate.class.isAssignableFrom(method.getReturnType())
                  && method.getParameterTypes().length == 1
                  && method.getParameterTypes()[0] == String.class
                  && Modifier.isPublic(method.getModifiers())
                  && !Modifier.isAbstract(method.getModifiers()),
              "method must be of the form \"@%s public Predicate<T> %s(String value)\": %s",
              Operator.class.getSimpleName(),
              method.getName(),
              method);
          String name = Ascii.toLowerCase(method.getName());
          b.put(name, new ReflectionFactory<>(name, method));
        }
        c = c.getSuperclass();
      }
      opFactories = b.build();
    }
  }

  /**
   * Locate a predicate in the predicate tree.
   *
   * @param p the predicate to find.
   * @param clazz type of the predicate instance.
   * @return the predicate, null if not found.
   */
  @SuppressWarnings("unchecked")
  public static <T, P extends Predicate<T>> P find(Predicate<T> p, Class<P> clazz) {
    if (clazz.isAssignableFrom(p.getClass())) {
      return (P) p;
    }

    for (Predicate<T> c : p.getChildren()) {
      P r = find(c, clazz);
      if (r != null) {
        return r;
      }
    }

    return null;
  }

  /**
   * Locate a predicate in the predicate tree.
   *
   * @param p the predicate to find.
   * @param clazz type of the predicate instance.
   * @param name name of the operator.
   * @return the first instance of a predicate having the given type, as found by a depth-first
   *     search.
   */
  @SuppressWarnings("unchecked")
  public static <T, P extends OperatorPredicate<T>> P find(
      Predicate<T> p, Class<P> clazz, String name) {
    if (p instanceof OperatorPredicate
        && ((OperatorPredicate<?>) p).getOperator().equals(name)
        && clazz.isAssignableFrom(p.getClass())) {
      return (P) p;
    }

    for (Predicate<T> c : p.getChildren()) {
      P r = find(c, clazz, name);
      if (r != null) {
        return r;
      }
    }

    return null;
  }

  protected final Definition<T, Q> builderDef;
  private final ImmutableMap<String, OperatorFactory<T, Q>> opFactories;
  protected Map<String, String> opAliases = Collections.emptyMap();

  protected QueryBuilder(
      Definition<T, Q> def,
      @Nullable DynamicMap<? extends OperatorFactory<T, Q>> dynamicOpFactories) {
    builderDef = def;

    if (dynamicOpFactories != null) {
      ImmutableMap.Builder<String, OperatorFactory<T, Q>> opFactoriesBuilder =
          ImmutableMap.builder();
      opFactoriesBuilder.putAll(def.opFactories);
      for (Extension<? extends OperatorFactory<T, Q>> e : dynamicOpFactories) {
        String name = e.getExportName() + "_" + e.getPluginName();
        opFactoriesBuilder.put(name, e.getProvider().get());
      }
      opFactories = opFactoriesBuilder.build();
    } else {
      opFactories = def.opFactories;
    }
  }

  /**
   * Parse a user-supplied query string into a predicate.
   *
   * @param query the query string.
   * @return predicate representing the user query.
   * @throws QueryParseException the query string is invalid and cannot be parsed by this parser.
   *     This may be due to a syntax error, may be due to an operator not being supported, or due to
   *     an invalid value being passed to a recognized operator.
   */
  public Predicate<T> parse(String query) throws QueryParseException {
    if (Strings.isNullOrEmpty(query)) {
      throw new QueryParseException("query is empty");
    }
    return toPredicate(QueryParser.parse(query));
  }

  public void setOperatorAliases(Map<String, String> opAliases) {
    this.opAliases = opAliases;
  }

  /**
   * Parse multiple user-supplied query strings into a list of predicates.
   *
   * @param queries the query strings.
   * @return predicates representing the user query, in the same order as the input.
   * @throws QueryParseException one of the query strings is invalid and cannot be parsed by this
   *     parser. This may be due to a syntax error, may be due to an operator not being supported,
   *     or due to an invalid value being passed to a recognized operator.
   */
  public List<Predicate<T>> parse(List<String> queries) throws QueryParseException {
    List<Predicate<T>> predicates = new ArrayList<>(queries.size());
    for (String query : queries) {
      predicates.add(parse(query));
    }
    return predicates;
  }

  private Predicate<T> toPredicate(Tree r) throws QueryParseException, IllegalArgumentException {
    Predicate<T> result;
    switch (r.getType()) {
      case AND:
        result = and(children(r));
        break;
      case OR:
        result = or(children(r));
        break;
      case NOT:
        result = not(toPredicate(onlyChildOf(r)));
        break;

      case DEFAULT_FIELD:
        result = defaultField(concatenateChildText(r));
        break;

      case FIELD_NAME:
        result = operator(r.getText(), concatenateChildText(r));
        break;

      default:
        throw error("Unsupported operator: " + r);
    }
    result.setPredicateString(getPredicateString(r));
    return result;
  }

  /**
   * Reconstruct the query sub-expression that was passed as input to the query parser from the tree
   * input parameter.
   */
  private static String getPredicateString(Tree r) {
    CommonTree ct = (CommonTree) r;
    CommonToken token = (CommonToken) ct.getToken();
    CharStream inputStream = token.getInputStream();
    int leftIdx = getLeftIndex(r);
    int rightIdx = getRightIndex(r);
    if (inputStream == null) {
      return "";
    }
    return inputStream.substring(leftIdx, rightIdx);
  }

  private static int getLeftIndex(Tree r) {
    CommonTree ct = (CommonTree) r;
    CommonToken token = (CommonToken) ct.getToken();
    return token.getStartIndex();
  }

  private static int getRightIndex(Tree r) {
    CommonTree ct = (CommonTree) r;
    if (ct.getChildCount() == 0) {
      CommonToken token = (CommonToken) ct.getToken();
      return token.getStopIndex();
    }
    return getRightIndex(ct.getChild(ct.getChildCount() - 1));
  }

  private static String concatenateChildText(Tree r) throws QueryParseException {
    if (r.getChildCount() == 0) {
      throw error("Expected children under: " + r);
    }
    if (r.getChildCount() == 1) {
      return getFieldValue(r.getChild(0));
    }
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < r.getChildCount(); i++) {
      sb.append(getFieldValue(r.getChild(i)));
    }
    return sb.toString();
  }

  private static String getFieldValue(Tree r) throws QueryParseException {
    if (r.getChildCount() != 0) {
      throw error("Expected no children under: " + r);
    }
    switch (r.getType()) {
      case SINGLE_WORD:
      case COLON:
      case EXACT_PHRASE:
        return r.getText();
      default:
        throw error(
            String.format(
                "Unsupported %s node in operator %s: %s",
                QueryParser.tokenNames[r.getType()], r.getParent(), r));
    }
  }

  @SuppressWarnings("unchecked")
  private Predicate<T> operator(String name, String value) throws QueryParseException {
    String opName = MoreObjects.firstNonNull(opAliases.get(name), name);
    @SuppressWarnings("rawtypes")
    OperatorFactory f = opFactories.get(opName);
    if (f == null && !opName.equals(name)) {
      f = opFactories.get(name);
    }
    if (f == null) {
      throw error("Unsupported operator " + name + ":" + value);
    }
    return f.create(this, value);
  }

  /**
   * Handle a value present outside of an operator.
   *
   * <p>This default implementation always throws an "Unsupported query: " message containing the
   * input text. Subclasses may override this method to perform do-what-i-mean guesses based on the
   * input string.
   *
   * @param value the value supplied by itself in the query.
   * @return predicate representing this value.
   * @throws QueryParseException the parser does not recognize this value.
   */
  protected Predicate<T> defaultField(String value) throws QueryParseException {
    throw error("Unsupported query: " + value);
  }

  private List<Predicate<T>> children(Tree r) throws QueryParseException, IllegalArgumentException {
    List<Predicate<T>> p = new ArrayList<>(r.getChildCount());
    for (int i = 0; i < r.getChildCount(); i++) {
      p.add(toPredicate(r.getChild(i)));
    }
    return p;
  }

  private Tree onlyChildOf(Tree r) throws QueryParseException {
    if (r.getChildCount() != 1) {
      throw error("Expected exactly one child: " + r);
    }
    return r.getChild(0);
  }

  protected static QueryParseException error(String msg) {
    return new QueryParseException(msg);
  }

  protected static QueryParseException error(String msg, Throwable why) {
    return new QueryParseException(msg, why);
  }

  /** Denotes a method which is a query operator. */
  @Retention(RetentionPolicy.RUNTIME)
  @Target(ElementType.METHOD)
  protected @interface Operator {}

  private static class ReflectionFactory<T, Q extends QueryBuilder<T, Q>>
      implements OperatorFactory<T, Q> {
    private final String name;
    private final Method method;

    ReflectionFactory(String name, Method method) {
      this.name = name;
      this.method = method;
    }

    @SuppressWarnings("unchecked")
    @Override
    public Predicate<T> create(Q builder, String value) throws QueryParseException {
      try {
        Predicate<T> predicate = (Predicate<T>) method.invoke(builder, value);
        // All operator predicates are leaf predicates.
        predicate.setLeaf(true);
        return predicate;
      } catch (RuntimeException | IllegalAccessException e) {
        throw error("Error in operator " + name + ":" + value, e);
      } catch (InvocationTargetException e) {
        Optional<QueryParseException> queryParseException =
            Throwables.getCausalChain(e).stream()
                .filter(QueryParseException.class::isInstance)
                .map(QueryParseException.class::cast)
                .findAny();
        if (queryParseException.isPresent()) {
          throw queryParseException.get();
        }
        throw error("Error in operator " + name + ":" + value, e.getCause());
      }
    }
  }
}