gerrit-server/src/main/java/com/google/gerrit/server/query/QueryRewriter.java - gerrit.git - Git at Google

 // 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.server.query;

 import com.google.inject.name.Named;

 import java.lang.annotation.Annotation;
 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.Arrays;
 import java.util.Collection;
 import java.util.Comparator;
 import java.util.HashMap;
 import java.util.Iterator;
 import java.util.LinkedList;
 import java.util.List;
 import java.util.Map;

 /**
  * Rewrites a Predicate tree by applying rewrite rules.
  * <p>
  * Subclasses may document their rewrite rules by declaring public methods with
  * {@link Rewrite} annotations, such as:
  *
  * <pre>
  * &#064;Rewrite(&quot;A=(owner:*) B=(status:*)&quot;)
  * public Predicate r1_ownerStatus(@Named(&quot;A&quot;) OperatorPredicate owner,
  *     &#064;Named(&quot;B&quot;) OperatorPredicate status) {
  * }
  * </pre>
  * <p>
  * Rewrite methods are applied in order by declared name, so naming methods with
  * a numeric prefix to ensure a specific ordering (if required) is suggested.
  *
  * @type <T> type of object the predicate can evaluate in memory.
  */
 public abstract class QueryRewriter<T> {
   /**
    * Defines the rewrite rules known by a QueryRewriter.
    *
    * This class is thread-safe and may be reused or cached.
    *
    * @param <T> type of object the predicates can evaluate in memory.
    * @param <R> type of the rewriter subclass.
    */
   public static class Definition<T, R extends QueryRewriter<T>> {
     private final List<RewriteRule<T>> rewriteRules;

     public Definition(Class<R> clazz, QueryBuilder<T> qb) {
       rewriteRules = new ArrayList<RewriteRule<T>>();

       Class<?> c = clazz;
       while (c != QueryRewriter.class) {
         final Method[] declared = c.getDeclaredMethods();
         Arrays.sort(declared, new Comparator<Method>() {
           @Override
           public int compare(Method o1, Method o2) {
             return o1.getName().compareTo(o2.getName());
           }
         });
         for (Method m : declared) {
           final Rewrite rp = m.getAnnotation(Rewrite.class);
           if ((m.getModifiers() & Modifier.ABSTRACT) != Modifier.ABSTRACT
               && (m.getModifiers() & Modifier.PUBLIC) == Modifier.PUBLIC
               && rp != null) {
             rewriteRules.add(new MethodRewrite<T>(qb, rp.value(), m));
           }
         }
         c = c.getSuperclass();
       }
     }
   }

   private final List<RewriteRule<T>> rewriteRules;

   protected QueryRewriter(final Definition<T, ? extends QueryRewriter<T>> def) {
     this.rewriteRules = def.rewriteRules;
   }

   /** Combine the passed predicates into a single AND node. */
   public Predicate<T> and(Collection<? extends Predicate<T>> that) {
     return Predicate.and(that);
   }

   /** Combine the passed predicates into a single AND node. */
   public Predicate<T> and(Predicate<T>... that) {
     return and(Arrays.asList(that));
   }

   /** Combine the passed predicates into a single OR node. */
   public Predicate<T> or(Collection<? extends Predicate<T>> that) {
     return Predicate.or(that);
   }

   /** Combine the passed predicates into a single OR node. */
   public Predicate<T> or(Predicate<T>... that) {
     return or(Arrays.asList(that));
   }

   /** Invert the passed node. */
   public Predicate<T> not(Predicate<T> that) {
     return Predicate.not(that);
   }

   /**
    * Apply rewrites to a graph until it stops changing.
    *
    * @param in the graph to rewrite.
    * @return the rewritten graph.
    */
   public Predicate<T> rewrite(Predicate<T> in) {
     Predicate<T> old;
     do {
       old = in;
       in = rewriteOne(in);

       if (old.equals(in) && in.getChildCount() > 0) {
         List<Predicate<T>> n = new ArrayList<Predicate<T>>(in.getChildCount());
         for (Predicate<T> p : in.getChildren()) {
           n.add(rewrite(p));
         }
         n = removeDuplicates(n);
         if (n.size() == 1 && (isAND(in) || isOR(in))) {
           in = n.get(0);
         } else {
           in = in.copy(n);
         }
       }

     } while (!old.equals(in));
     return replaceGenericNodes(in);
   }

   protected Predicate<T> replaceGenericNodes(final Predicate<T> in) {
     if (in.getClass() == NotPredicate.class) {
       return not(replaceGenericNodes(in.getChild(0)));

     } else if (in.getClass() == AndPredicate.class) {
       List<Predicate<T>> n = new ArrayList<Predicate<T>>(in.getChildCount());
       for (Predicate<T> c : in.getChildren()) {
         n.add(replaceGenericNodes(c));
       }
       return and(n);

     } else if (in.getClass() == OrPredicate.class) {
       List<Predicate<T>> n = new ArrayList<Predicate<T>>(in.getChildCount());
       for (Predicate<T> c : in.getChildren()) {
         n.add(replaceGenericNodes(c));
       }
       return or(n);

     } else {
       return in;
     }
   }

   private Predicate<T> rewriteOne(Predicate<T> input) {
     Predicate<T> best = null;
     for (RewriteRule<T> r : rewriteRules) {
       Predicate<T> n = r.rewrite(this, input);
       if (n == null) {
         continue;
       }

       if (!r.useBestCost()) {
         return n;
       }

       if (best == null || n.getCost() < best.getCost()) {
         best = n;
         continue;
       }
     }
     return best != null ? best : input;
   }

   private static class MatchResult<T> {
     private static final MatchResult<?> FAIL = new MatchResult<Object>(null);
     private static final MatchResult<?> OK = new MatchResult<Object>(null);

     @SuppressWarnings("unchecked")
     static <T> MatchResult<T> fail() {
       return (MatchResult<T>) FAIL;
     }

     @SuppressWarnings("unchecked")
     static <T> MatchResult<T> ok() {
       return (MatchResult<T>) OK;
     }

     final Predicate<T> extra;

     MatchResult(Predicate<T> extra) {
       this.extra = extra;
     }

     boolean success() {
       return this != FAIL;
     }
   }

   private MatchResult<T> match(final Map<String, Predicate<T>> outVars,
       final Predicate<T> pattern, final Predicate<T> actual) {
     if (pattern instanceof VariablePredicate) {
       final VariablePredicate<T> v = (VariablePredicate<T>) pattern;
       final MatchResult<T> r = match(outVars, v.getChild(0), actual);
       if (r.success()) {
         Predicate<T> old = outVars.get(v.getName());
         if (old == null) {
           outVars.put(v.getName(), actual);
           return r;
         } else if (old.equals(actual)) {
           return r;
         } else {
           return MatchResult.fail();
         }
       } else {
         return MatchResult.fail();
       }
     }

     if ((isAND(pattern) && isAND(actual)) //
         || (isOR(pattern) && isOR(actual)) //
         || (isNOT(pattern) && isNOT(actual)) //
     ) {
       // Order doesn't actually matter here. That does make our logic quite
       // a bit more complex as we need to consult each child at most once,
       // but in any order.
       //
       final LinkedList<Predicate<T>> have = dup(actual);
       final LinkedList<Predicate<T>> extra = new LinkedList<Predicate<T>>();
       for (final Predicate<T> pat : pattern.getChildren()) {
         boolean found = false;
         for (final Iterator<Predicate<T>> i = have.iterator(); i.hasNext();) {
           final MatchResult<T> r = match(outVars, pat, i.next());
           if (r.success()) {
             found = true;
             i.remove();
             if (r.extra != null) {
               extra.add(r.extra);
             }
             break;
           }
         }
         if (!found) {
           return MatchResult.fail();
         }
       }
       have.addAll(extra);
       switch (have.size()) {
         case 0:
           return MatchResult.ok();
         case 1:
           if (isNOT(actual)) {
             return new MatchResult<T>(actual.copy(have));
           }
           return new MatchResult<T>(have.get(0));
         default:
           return new MatchResult<T>(actual.copy(have));
       }

     } else if (pattern.equals(actual)) {
       return MatchResult.ok();

     } else if (pattern instanceof WildPatternPredicate
         && actual instanceof OperatorPredicate
         && ((OperatorPredicate<T>) pattern).getOperator().equals(
             ((OperatorPredicate<T>) actual).getOperator())) {
       return MatchResult.ok();

     } else {
       return MatchResult.fail();
     }
   }

   private static <T> LinkedList<Predicate<T>> dup(final Predicate<T> actual) {
     return new LinkedList<Predicate<T>>(actual.getChildren());
   }

   /**
    * Denotes a method which wants to replace a predicate expression.
    * <p>
    * This annotation must be applied to a public method which returns
    * {@link Predicate}. The arguments of the method should {@link Predicate}, or
    * any subclass of it. The annotation value is a query language string which
    * describes the subtree this rewrite applies to. Method arguments should be
    * named with a {@link Named} annotation, and the same names should be used in
    * the query.
    * <p>
    * For example:
    *
    * <pre>
    * &#064;Rewrite(&quot;A=(owner:*) B=(status:*)&quot;)
    * public Predicate ownerStatus(@Named(&quot;A&quot;) OperatorPredicate owner,
    *     &#064;Named(&quot;B&quot;) OperatorPredicate status) {
    * }
    * </pre>
    *
    * matches an AND Predicate with at least two children, one being an operator
    * predicate called "owner" and the other being an operator predicate called
    * "status". The variables in the query are matched by name against the
    * parameters.
    */
   @Retention(RetentionPolicy.RUNTIME)
   @Target(ElementType.METHOD)
   protected @interface Rewrite {
     String value();
   }

   @Retention(RetentionPolicy.RUNTIME)
   @Target(ElementType.METHOD)
   protected @interface NoCostComputation {
   }

   /** Applies a rewrite rule to a Predicate. */
   protected interface RewriteRule<T> {
     /**
      * Apply a rewrite rule to the Predicate.
      *
      * @param input the input predicate to be tested, and possibly rewritten.
      * @return a rewritten form of the predicate if this rule matches with the
      *         tree {@code input} and has a rewrite for it; {@code null} if this
      *         rule does not want this predicate.
      */
     Predicate<T> rewrite(QueryRewriter<T> rewriter, Predicate<T> input);

     /** @return true if the best cost should be selected. */
     boolean useBestCost();
   }

   /** Implements the magic behind {@link Rewrite} annotations. */
   private static class MethodRewrite<T> implements RewriteRule<T> {
     private final Method method;
     private final Predicate<T> pattern;
     private final String[] argNames;
     private final Class<? extends Predicate<T>>[] argTypes;
     private final boolean useBestCost;

     @SuppressWarnings("unchecked")
     MethodRewrite(QueryBuilder<T> queryBuilder, String patternText, Method m) {
       method = m;
       useBestCost = m.getAnnotation(NoCostComputation.class) == null;

       Predicate<T> p;
       try {
         p = queryBuilder.parse(patternText);
       } catch (QueryParseException e) {
         throw new RuntimeException("Bad @Rewrite(\"" + patternText + "\")"
             + " on " + m.toGenericString() + " in " + m.getDeclaringClass()
             + ": " + e.getMessage(), e);
       }
       if (!Predicate.class.isAssignableFrom(m.getReturnType())) {
         throw new RuntimeException(m.toGenericString() + " in "
             + m.getDeclaringClass() + " must return " + Predicate.class);
       }

       pattern = p;
       argNames = new String[method.getParameterTypes().length];
       argTypes = new Class[argNames.length];
       for (int i = 0; i < argNames.length; i++) {
         Named name = null;
         for (Annotation a : method.getParameterAnnotations()[i]) {
           if (a instanceof Named) {
             name = (Named) a;
             break;
           }
         }
         if (name == null) {
           throw new RuntimeException("Argument " + (i + 1) + " of "
               + m.toGenericString() + " in " + m.getDeclaringClass()
               + " has no @Named annotation");
         }
         if (!Predicate.class.isAssignableFrom(method.getParameterTypes()[i])) {
           throw new RuntimeException("Argument " + (i + 1) + " of "
               + m.toGenericString() + " in " + m.getDeclaringClass()
               + " must be of type " + Predicate.class);
         }
         argNames[i] = name.value();
         argTypes[i] = (Class<Predicate<T>>) method.getParameterTypes()[i];
       }
     }

     @Override
     public boolean useBestCost() {
       return useBestCost;
     }

     @SuppressWarnings("unchecked")
     @Override
     public Predicate<T> rewrite(QueryRewriter<T> rewriter,
         final Predicate<T> input) {
       final HashMap<String, Predicate<T>> args =
           new HashMap<String, Predicate<T>>();
       final MatchResult<T> res = rewriter.match(args, pattern, input);
       if (!res.success()) {
         return null;
       }

       final Predicate<T>[] argList = new Predicate[argNames.length];
       for (int i = 0; i < argList.length; i++) {
         argList[i] = args.get(argNames[i]);
         if (argList[i] == null) {
           final String a = "@Named(\"" + argNames[i] + "\")";
           throw error(new IllegalStateException("No value bound for " + a));
         }
         if (!argTypes[i].isInstance(argList[i])) {
           return null;
         }
       }

       final Predicate<T> rep;
       try {
         rep = (Predicate<T>) method.invoke(rewriter, (Object[]) argList);
       } catch (IllegalArgumentException e) {
         throw error(e);
       } catch (IllegalAccessException e) {
         throw error(e);
       } catch (InvocationTargetException e) {
         throw error(e.getCause());
       }

       if (rep instanceof RewritePredicate) {
         ((RewritePredicate<T>) rep).init(method.getName(), argList);
       }

       if (res.extra == null) {
         return rep;
       }

       Predicate<T> extra = removeDuplicates(res.extra);
       Predicate<T>[] newArgs = new Predicate[] {extra, rep};
       return input.copy(Arrays.asList(newArgs));
     }

     private IllegalArgumentException error(Throwable e) {
       final String msg = "Cannot apply " + method.getName();
       return new IllegalArgumentException(msg, e);
     }
   }

   private static <T> Predicate<T> removeDuplicates(Predicate<T> in) {
     if (in.getChildCount() > 0) {
       List<Predicate<T>> n = removeDuplicates(in.getChildren());
       if (n.size() == 1 && (isAND(in) || isOR(in))) {
         in = n.get(0);
       } else {
         in = in.copy(n);
       }
     }
     return in;
   }

   private static <T> List<Predicate<T>> removeDuplicates(List<Predicate<T>> n) {
     List<Predicate<T>> r = new ArrayList<Predicate<T>>();
     for (Predicate<T> p : n) {
       if (!r.contains(p)) {
         r.add(p);
       }
     }
     return r;
   }

   private static <T> void expand(final List<Predicate<T>> out,
       final List<Predicate<T>> allOR, final List<Predicate<T>> tmp,
       final List<Predicate<T>> nonOR) {
     if (tmp.size() == allOR.size()) {
       final int sz = nonOR.size() + tmp.size();
       final List<Predicate<T>> newList = new ArrayList<Predicate<T>>(sz);
       newList.addAll(nonOR);
       newList.addAll(tmp);
       out.add(Predicate.and(newList));

     } else {
       for (final Predicate<T> c : allOR.get(tmp.size()).getChildren()) {
         try {
           tmp.add(c);
           expand(out, allOR, tmp, nonOR);
         } finally {
           tmp.remove(tmp.size() - 1);
         }
       }
     }
   }

   private static <T> boolean isAND(final Predicate<T> p) {
     return p instanceof AndPredicate;
   }

   private static <T> boolean isOR(final Predicate<T> p) {
     return p instanceof OrPredicate;
   }

   private static <T> boolean isNOT(final Predicate<T> p) {
     return p instanceof NotPredicate;
   }
 }
	// 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.server.query;

	import com.google.inject.name.Named;

	import java.lang.annotation.Annotation;
	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.Arrays;
	import java.util.Collection;
	import java.util.Comparator;
	import java.util.HashMap;
	import java.util.Iterator;
	import java.util.LinkedList;
	import java.util.List;
	import java.util.Map;

	/**
	* Rewrites a Predicate tree by applying rewrite rules.
	* <p>
	* Subclasses may document their rewrite rules by declaring public methods with
	* {@link Rewrite} annotations, such as:
	*
	* <pre>
	* @Rewrite("A=(owner:) B=(status:)")
	* public Predicate r1_ownerStatus(@Named("A") OperatorPredicate owner,
	* @Named("B") OperatorPredicate status) {
	* }
	* </pre>
	* <p>
	* Rewrite methods are applied in order by declared name, so naming methods with
	* a numeric prefix to ensure a specific ordering (if required) is suggested.
	*
	* @type <T> type of object the predicate can evaluate in memory.
	*/
	public abstract class QueryRewriter<T> {
	/**
	* Defines the rewrite rules known by a QueryRewriter.
	*
	* This class is thread-safe and may be reused or cached.
	*
	* @param <T> type of object the predicates can evaluate in memory.
	* @param <R> type of the rewriter subclass.
	*/
	public static class Definition<T, R extends QueryRewriter<T>> {
	private final List<RewriteRule<T>> rewriteRules;

	public Definition(Class<R> clazz, QueryBuilder<T> qb) {
	rewriteRules = new ArrayList<RewriteRule<T>>();

	Class<?> c = clazz;
	while (c != QueryRewriter.class) {
	final Method[] declared = c.getDeclaredMethods();
	Arrays.sort(declared, new Comparator<Method>() {
	@Override
	public int compare(Method o1, Method o2) {
	return o1.getName().compareTo(o2.getName());
	}
	});
	for (Method m : declared) {
	final Rewrite rp = m.getAnnotation(Rewrite.class);
	if ((m.getModifiers() & Modifier.ABSTRACT) != Modifier.ABSTRACT
	&& (m.getModifiers() & Modifier.PUBLIC) == Modifier.PUBLIC
	&& rp != null) {
	rewriteRules.add(new MethodRewrite<T>(qb, rp.value(), m));
	}
	}
	c = c.getSuperclass();
	}
	}
	}

	private final List<RewriteRule<T>> rewriteRules;

	protected QueryRewriter(final Definition<T, ? extends QueryRewriter<T>> def) {
	this.rewriteRules = def.rewriteRules;
	}

	/** Combine the passed predicates into a single AND node. */
	public Predicate<T> and(Collection<? extends Predicate<T>> that) {
	return Predicate.and(that);
	}

	/** Combine the passed predicates into a single AND node. */
	public Predicate<T> and(Predicate<T>... that) {
	return and(Arrays.asList(that));
	}

	/** Combine the passed predicates into a single OR node. */
	public Predicate<T> or(Collection<? extends Predicate<T>> that) {
	return Predicate.or(that);
	}

	/** Combine the passed predicates into a single OR node. */
	public Predicate<T> or(Predicate<T>... that) {
	return or(Arrays.asList(that));
	}

	/** Invert the passed node. */
	public Predicate<T> not(Predicate<T> that) {
	return Predicate.not(that);
	}

	/**
	* Apply rewrites to a graph until it stops changing.
	*
	* @param in the graph to rewrite.
	* @return the rewritten graph.
	*/
	public Predicate<T> rewrite(Predicate<T> in) {
	Predicate<T> old;
	do {
	old = in;
	in = rewriteOne(in);

	if (old.equals(in) && in.getChildCount() > 0) {
	List<Predicate<T>> n = new ArrayList<Predicate<T>>(in.getChildCount());
	for (Predicate<T> p : in.getChildren()) {
	n.add(rewrite(p));
	}
	n = removeDuplicates(n);
	if (n.size() == 1 && (isAND(in) \|\| isOR(in))) {
	in = n.get(0);
	} else {
	in = in.copy(n);
	}
	}

	} while (!old.equals(in));
	return replaceGenericNodes(in);
	}

	protected Predicate<T> replaceGenericNodes(final Predicate<T> in) {
	if (in.getClass() == NotPredicate.class) {
	return not(replaceGenericNodes(in.getChild(0)));

	} else if (in.getClass() == AndPredicate.class) {
	List<Predicate<T>> n = new ArrayList<Predicate<T>>(in.getChildCount());
	for (Predicate<T> c : in.getChildren()) {
	n.add(replaceGenericNodes(c));
	}
	return and(n);

	} else if (in.getClass() == OrPredicate.class) {
	List<Predicate<T>> n = new ArrayList<Predicate<T>>(in.getChildCount());
	for (Predicate<T> c : in.getChildren()) {
	n.add(replaceGenericNodes(c));
	}
	return or(n);

	} else {
	return in;
	}
	}

	private Predicate<T> rewriteOne(Predicate<T> input) {
	Predicate<T> best = null;
	for (RewriteRule<T> r : rewriteRules) {
	Predicate<T> n = r.rewrite(this, input);
	if (n == null) {
	continue;
	}

	if (!r.useBestCost()) {
	return n;
	}

	if (best == null \|\| n.getCost() < best.getCost()) {
	best = n;
	continue;
	}
	}
	return best != null ? best : input;
	}

	private static class MatchResult<T> {
	private static final MatchResult<?> FAIL = new MatchResult<Object>(null);
	private static final MatchResult<?> OK = new MatchResult<Object>(null);

	@SuppressWarnings("unchecked")
	static <T> MatchResult<T> fail() {
	return (MatchResult<T>) FAIL;
	}

	@SuppressWarnings("unchecked")
	static <T> MatchResult<T> ok() {
	return (MatchResult<T>) OK;
	}

	final Predicate<T> extra;

	MatchResult(Predicate<T> extra) {
	this.extra = extra;
	}

	boolean success() {
	return this != FAIL;
	}
	}

	private MatchResult<T> match(final Map<String, Predicate<T>> outVars,
	final Predicate<T> pattern, final Predicate<T> actual) {
	if (pattern instanceof VariablePredicate) {
	final VariablePredicate<T> v = (VariablePredicate<T>) pattern;
	final MatchResult<T> r = match(outVars, v.getChild(0), actual);
	if (r.success()) {
	Predicate<T> old = outVars.get(v.getName());
	if (old == null) {
	outVars.put(v.getName(), actual);
	return r;
	} else if (old.equals(actual)) {
	return r;
	} else {
	return MatchResult.fail();
	}
	} else {
	return MatchResult.fail();
	}
	}

	if ((isAND(pattern) && isAND(actual)) //
	\|\| (isOR(pattern) && isOR(actual)) //
	\|\| (isNOT(pattern) && isNOT(actual)) //
	) {
	// Order doesn't actually matter here. That does make our logic quite
	// a bit more complex as we need to consult each child at most once,
	// but in any order.
	//
	final LinkedList<Predicate<T>> have = dup(actual);
	final LinkedList<Predicate<T>> extra = new LinkedList<Predicate<T>>();
	for (final Predicate<T> pat : pattern.getChildren()) {
	boolean found = false;
	for (final Iterator<Predicate<T>> i = have.iterator(); i.hasNext();) {
	final MatchResult<T> r = match(outVars, pat, i.next());
	if (r.success()) {
	found = true;
	i.remove();
	if (r.extra != null) {
	extra.add(r.extra);
	}
	break;
	}
	}
	if (!found) {
	return MatchResult.fail();
	}
	}
	have.addAll(extra);
	switch (have.size()) {
	case 0:
	return MatchResult.ok();
	case 1:
	if (isNOT(actual)) {
	return new MatchResult<T>(actual.copy(have));
	}
	return new MatchResult<T>(have.get(0));
	default:
	return new MatchResult<T>(actual.copy(have));
	}

	} else if (pattern.equals(actual)) {
	return MatchResult.ok();

	} else if (pattern instanceof WildPatternPredicate
	&& actual instanceof OperatorPredicate
	&& ((OperatorPredicate<T>) pattern).getOperator().equals(
	((OperatorPredicate<T>) actual).getOperator())) {
	return MatchResult.ok();

	} else {
	return MatchResult.fail();
	}
	}

	private static <T> LinkedList<Predicate<T>> dup(final Predicate<T> actual) {
	return new LinkedList<Predicate<T>>(actual.getChildren());
	}

	/**
	* Denotes a method which wants to replace a predicate expression.
	* <p>
	* This annotation must be applied to a public method which returns
	* {@link Predicate}. The arguments of the method should {@link Predicate}, or
	* any subclass of it. The annotation value is a query language string which
	* describes the subtree this rewrite applies to. Method arguments should be
	* named with a {@link Named} annotation, and the same names should be used in
	* the query.
	* <p>
	* For example:
	*
	* <pre>
	* @Rewrite("A=(owner:) B=(status:)")
	* public Predicate ownerStatus(@Named("A") OperatorPredicate owner,
	* @Named("B") OperatorPredicate status) {
	* }
	* </pre>
	*
	* matches an AND Predicate with at least two children, one being an operator
	* predicate called "owner" and the other being an operator predicate called
	* "status". The variables in the query are matched by name against the
	* parameters.
	*/
	@Retention(RetentionPolicy.RUNTIME)
	@Target(ElementType.METHOD)
	protected @interface Rewrite {
	String value();
	}

	@Retention(RetentionPolicy.RUNTIME)
	@Target(ElementType.METHOD)
	protected @interface NoCostComputation {
	}

	/** Applies a rewrite rule to a Predicate. */
	protected interface RewriteRule<T> {
	/**
	* Apply a rewrite rule to the Predicate.
	*
	* @param input the input predicate to be tested, and possibly rewritten.
	* @return a rewritten form of the predicate if this rule matches with the
	* tree {@code input} and has a rewrite for it; {@code null} if this
	* rule does not want this predicate.
	*/
	Predicate<T> rewrite(QueryRewriter<T> rewriter, Predicate<T> input);

	/** @return true if the best cost should be selected. */
	boolean useBestCost();
	}

	/** Implements the magic behind {@link Rewrite} annotations. */
	private static class MethodRewrite<T> implements RewriteRule<T> {
	private final Method method;
	private final Predicate<T> pattern;
	private final String[] argNames;
	private final Class<? extends Predicate<T>>[] argTypes;
	private final boolean useBestCost;

	@SuppressWarnings("unchecked")
	MethodRewrite(QueryBuilder<T> queryBuilder, String patternText, Method m) {
	method = m;
	useBestCost = m.getAnnotation(NoCostComputation.class) == null;

	Predicate<T> p;
	try {
	p = queryBuilder.parse(patternText);
	} catch (QueryParseException e) {
	throw new RuntimeException("Bad @Rewrite(\"" + patternText + "\")"
	+ " on " + m.toGenericString() + " in " + m.getDeclaringClass()
	+ ": " + e.getMessage(), e);
	}
	if (!Predicate.class.isAssignableFrom(m.getReturnType())) {
	throw new RuntimeException(m.toGenericString() + " in "
	+ m.getDeclaringClass() + " must return " + Predicate.class);
	}

	pattern = p;
	argNames = new String[method.getParameterTypes().length];
	argTypes = new Class[argNames.length];
	for (int i = 0; i < argNames.length; i++) {
	Named name = null;
	for (Annotation a : method.getParameterAnnotations()[i]) {
	if (a instanceof Named) {
	name = (Named) a;
	break;
	}
	}
	if (name == null) {
	throw new RuntimeException("Argument " + (i + 1) + " of "
	+ m.toGenericString() + " in " + m.getDeclaringClass()
	+ " has no @Named annotation");
	}
	if (!Predicate.class.isAssignableFrom(method.getParameterTypes()[i])) {
	throw new RuntimeException("Argument " + (i + 1) + " of "
	+ m.toGenericString() + " in " + m.getDeclaringClass()
	+ " must be of type " + Predicate.class);
	}
	argNames[i] = name.value();
	argTypes[i] = (Class<Predicate<T>>) method.getParameterTypes()[i];
	}
	}

	@Override
	public boolean useBestCost() {
	return useBestCost;
	}

	@SuppressWarnings("unchecked")
	@Override
	public Predicate<T> rewrite(QueryRewriter<T> rewriter,
	final Predicate<T> input) {
	final HashMap<String, Predicate<T>> args =
	new HashMap<String, Predicate<T>>();
	final MatchResult<T> res = rewriter.match(args, pattern, input);
	if (!res.success()) {
	return null;
	}

	final Predicate<T>[] argList = new Predicate[argNames.length];
	for (int i = 0; i < argList.length; i++) {
	argList[i] = args.get(argNames[i]);
	if (argList[i] == null) {
	final String a = "@Named(\"" + argNames[i] + "\")";
	throw error(new IllegalStateException("No value bound for " + a));
	}
	if (!argTypes[i].isInstance(argList[i])) {
	return null;
	}
	}

	final Predicate<T> rep;
	try {
	rep = (Predicate<T>) method.invoke(rewriter, (Object[]) argList);
	} catch (IllegalArgumentException e) {
	throw error(e);
	} catch (IllegalAccessException e) {
	throw error(e);
	} catch (InvocationTargetException e) {
	throw error(e.getCause());
	}

	if (rep instanceof RewritePredicate) {
	((RewritePredicate<T>) rep).init(method.getName(), argList);
	}

	if (res.extra == null) {
	return rep;
	}

	Predicate<T> extra = removeDuplicates(res.extra);
	Predicate<T>[] newArgs = new Predicate[] {extra, rep};
	return input.copy(Arrays.asList(newArgs));
	}

	private IllegalArgumentException error(Throwable e) {
	final String msg = "Cannot apply " + method.getName();
	return new IllegalArgumentException(msg, e);
	}
	}

	private static <T> Predicate<T> removeDuplicates(Predicate<T> in) {
	if (in.getChildCount() > 0) {
	List<Predicate<T>> n = removeDuplicates(in.getChildren());
	if (n.size() == 1 && (isAND(in) \|\| isOR(in))) {
	in = n.get(0);
	} else {
	in = in.copy(n);
	}
	}
	return in;
	}

	private static <T> List<Predicate<T>> removeDuplicates(List<Predicate<T>> n) {
	List<Predicate<T>> r = new ArrayList<Predicate<T>>();
	for (Predicate<T> p : n) {
	if (!r.contains(p)) {
	r.add(p);
	}
	}
	return r;
	}

	private static <T> void expand(final List<Predicate<T>> out,
	final List<Predicate<T>> allOR, final List<Predicate<T>> tmp,
	final List<Predicate<T>> nonOR) {
	if (tmp.size() == allOR.size()) {
	final int sz = nonOR.size() + tmp.size();
	final List<Predicate<T>> newList = new ArrayList<Predicate<T>>(sz);
	newList.addAll(nonOR);
	newList.addAll(tmp);
	out.add(Predicate.and(newList));

	} else {
	for (final Predicate<T> c : allOR.get(tmp.size()).getChildren()) {
	try {
	tmp.add(c);
	expand(out, allOR, tmp, nonOR);
	} finally {
	tmp.remove(tmp.size() - 1);
	}
	}
	}
	}

	private static <T> boolean isAND(final Predicate<T> p) {
	return p instanceof AndPredicate;
	}

	private static <T> boolean isOR(final Predicate<T> p) {
	return p instanceof OrPredicate;
	}

	private static <T> boolean isNOT(final Predicate<T> p) {
	return p instanceof NotPredicate;
	}
	}