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.common.base.Preconditions.checkState;
      19             : 
      20             : import com.google.common.collect.Iterables;
      21             : import java.util.ArrayDeque;
      22             : import java.util.ArrayList;
      23             : import java.util.Collection;
      24             : import java.util.Collections;
      25             : import java.util.List;
      26             : import java.util.Queue;
      27             : 
      28             : /**
      29             :  * An abstract predicate tree for any form of query.
      30             :  *
      31             :  * <p>Implementations should be immutable, such that the meaning of a predicate never changes once
      32             :  * constructed. They should ensure their immutable promise by defensively copying any structures
      33             :  * which might be modified externally, but was passed into the object's constructor.
      34             :  *
      35             :  * <p>However, implementations <i>may</i> retain non-thread-safe caches internally, to speed up
      36             :  * evaluation operations within the context of one thread's evaluation of the predicate. As a
      37             :  * result, callers should assume predicates are not thread-safe, but that two predicate graphs
      38             :  * produce the same results given the same inputs if they are {@link #equals(Object)}.
      39             :  *
      40             :  * <p>Predicates should support deep inspection whenever possible, so that generic algorithms can be
      41             :  * written to operate against them. Predicates which contain other predicates should override {@link
      42             :  * #getChildren()} to return the list of children nested within the predicate.
      43             :  *
      44             :  * @param <T> type of object the predicate can evaluate in memory.
      45             :  */
      46         153 : public abstract class Predicate<T> {
      47             :   /** Query String that was used to create this predicate. Only set from the Antlr query parser. */
      48         153 :   private String predicateString = null;
      49             : 
      50             :   /**
      51             :    * Boolean indicating if this predicate is a leaf predicate in a composite expression. Only set
      52             :    * from the Antlr query parser.
      53             :    */
      54         153 :   private boolean isLeaf = false;
      55             : 
      56             :   /** Sets the {@link #predicateString} field. This can only be set once. */
      57             :   void setPredicateString(String predicateString) {
      58          50 :     this.predicateString = this.predicateString == null ? predicateString : this.predicateString;
      59          50 :   }
      60             : 
      61             :   public String getPredicateString() {
      62           3 :     return predicateString;
      63             :   }
      64             : 
      65             :   void setLeaf(boolean isLeaf) {
      66          48 :     this.isLeaf = isLeaf;
      67          48 :   }
      68             : 
      69             :   public boolean isLeaf() {
      70           3 :     return isLeaf;
      71             :   }
      72             : 
      73             :   /** A predicate that matches any input, always, with no cost. */
      74             :   @SuppressWarnings("unchecked")
      75             :   public static <T> Predicate<T> any() {
      76           6 :     return (Predicate<T>) Any.INSTANCE;
      77             :   }
      78             : 
      79             :   /** Combine the passed predicates into a single AND node. */
      80             :   @SafeVarargs
      81             :   public static <T> Predicate<T> and(Predicate<T>... that) {
      82         111 :     if (that.length == 1) {
      83           0 :       return that[0];
      84             :     }
      85         111 :     return new AndPredicate<>(that);
      86             :   }
      87             : 
      88             :   /** Combine the passed predicates into a single AND node. */
      89             :   public static <T> Predicate<T> and(Collection<? extends Predicate<T>> that) {
      90          23 :     if (that.size() == 1) {
      91           8 :       return Iterables.getOnlyElement(that);
      92             :     }
      93          22 :     return new AndPredicate<>(that);
      94             :   }
      95             : 
      96             :   /** Combine the passed predicates into a single OR node. */
      97             :   @SafeVarargs
      98             :   public static <T> Predicate<T> or(Predicate<T>... that) {
      99          16 :     if (that.length == 1) {
     100           2 :       return that[0];
     101             :     }
     102          16 :     return new OrPredicate<>(that);
     103             :   }
     104             : 
     105             :   /** Combine the passed predicates into a single OR node. */
     106             :   public static <T> Predicate<T> or(Collection<? extends Predicate<T>> that) {
     107         121 :     if (that.size() == 1) {
     108         115 :       return Iterables.getOnlyElement(that);
     109             :     }
     110         121 :     return new OrPredicate<>(that);
     111             :   }
     112             : 
     113             :   /** Invert the passed node. */
     114             :   public static <T> Predicate<T> not(Predicate<T> that) {
     115          57 :     checkArgument(
     116             :         !(that instanceof Any), "negating any() is unsafe because it post-filters all results");
     117          57 :     if (that instanceof NotPredicate) {
     118             :       // Negate of a negate is the original predicate.
     119             :       //
     120           5 :       return that.getChild(0);
     121             :     }
     122          57 :     return new NotPredicate<>(that);
     123             :   }
     124             : 
     125             :   /** Get the children of this predicate, if any. */
     126             :   public List<Predicate<T>> getChildren() {
     127         152 :     return Collections.emptyList();
     128             :   }
     129             : 
     130             :   /** Same as {@code getChildren().size()} */
     131             :   public int getChildCount() {
     132          76 :     return getChildren().size();
     133             :   }
     134             : 
     135             :   /** Same as {@code getChildren().get(i)} */
     136             :   public Predicate<T> getChild(int i) {
     137           0 :     return getChildren().get(i);
     138             :   }
     139             : 
     140             :   /** Get the number of leaf terms in this predicate. */
     141             :   public int getLeafCount() {
     142           1 :     int leafCount = 0;
     143           1 :     for (Predicate<?> childPredicate : getChildren()) {
     144           1 :       if (childPredicate instanceof IndexPredicate) {
     145           1 :         leafCount++;
     146             :       }
     147           1 :       leafCount += childPredicate.getLeafCount();
     148           1 :     }
     149           1 :     return leafCount;
     150             :   }
     151             : 
     152             :   /** Returns a list of this predicate and all its descendants. */
     153             :   public List<Predicate<T>> getFlattenedPredicateList() {
     154         151 :     List<Predicate<T>> result = new ArrayList<>();
     155         151 :     Queue<Predicate<T>> queue = new ArrayDeque<>();
     156         151 :     queue.add(this);
     157         151 :     while (!queue.isEmpty()) {
     158         151 :       Predicate<T> current = queue.poll();
     159         151 :       result.add(current);
     160         151 :       current.getChildren().forEach(p -> queue.add(p));
     161         151 :     }
     162         151 :     return result;
     163             :   }
     164             : 
     165             :   /** Create a copy of this predicate, with new children. */
     166             :   public abstract Predicate<T> copy(Collection<? extends Predicate<T>> children);
     167             : 
     168             :   public boolean isMatchable() {
     169         152 :     return this instanceof Matchable;
     170             :   }
     171             : 
     172             :   /** Whether this predicate can be used in search queries. */
     173             :   public boolean supportedForQueries() {
     174         151 :     return true;
     175             :   }
     176             : 
     177             :   @SuppressWarnings("unchecked")
     178             :   public Matchable<T> asMatchable() {
     179         152 :     checkState(isMatchable(), "not matchable");
     180         152 :     return (Matchable<T>) this;
     181             :   }
     182             : 
     183             :   /** Returns a cost estimate to run this predicate, higher figures cost more. */
     184             :   public int estimateCost() {
     185         125 :     if (!isMatchable()) {
     186          19 :       return 1;
     187             :     }
     188         122 :     return asMatchable().getCost();
     189             :   }
     190             : 
     191             :   @Override
     192             :   public abstract int hashCode();
     193             : 
     194             :   @Override
     195             :   public abstract boolean equals(Object other);
     196             : 
     197             :   private static class Any<T> extends Predicate<T> implements Matchable<T> {
     198           6 :     private static final Any<Object> INSTANCE = new Any<>();
     199             : 
     200             :     private Any() {}
     201             : 
     202             :     @Override
     203             :     public Predicate<T> copy(Collection<? extends Predicate<T>> children) {
     204           0 :       return this;
     205             :     }
     206             : 
     207             :     @Override
     208             :     public boolean match(T object) {
     209           0 :       return true;
     210             :     }
     211             : 
     212             :     @Override
     213             :     public int getCost() {
     214           0 :       return 0;
     215             :     }
     216             : 
     217             :     @Override
     218             :     public int hashCode() {
     219           0 :       return System.identityHashCode(this);
     220             :     }
     221             : 
     222             :     @Override
     223             :     public boolean equals(Object other) {
     224           0 :       return other == this;
     225             :     }
     226             :   }
     227             : }