java/src/main/com/google/appengine/api/search/query/QueryTreeWalker.java

   1 // Copyright 2011 Google Inc. All Rights Reserved.
   2
   3 package com.google.appengine.api.search.query;
   4
   5 import org.antlr.runtime.tree.Tree;
   6
   7 /**
   8  * The walking of the query tree. This class takes care of visiting
   9  * a tree resulting from parsing a query. As it traverses the tree
  10  * it calls appropriate methods of the visitor, set at the construction
  11  * time. The class uses a depth-first search, visiting all children
  12  * of a node, before visiting the node. The visit is done by calling
  13  * an appropriate method of the visitor. Typical code should match
  14  * the following pattern:
  15  * <pre>
  16  * class MyVisitor implements QueryTreeVisitor {
  17  *   ...
  18  * }
  19  * class MyContext extends QueryTreeContext&lt;MyContext&gt; {
  20  *   ...
  21  *   &#64;Override
  22  *   protected MyContext newChildContext() {
  23  *     return new MyContext();
  24  *   }
  25  * }
  26  *
  27  * MyContext context = new MyContext();
  28  * QueryTreeWalker&lt;MyContext&gt; walker = new QueryTreeWalker&lt;MyContext&gt;(new MyVisitor());
  29  * Tree root = parser.query(queryStr);
  30  * walker.walk(root, context);
  31  * // retrieve whatever information you need from context
  32  * </pre>
  33  *
  34  * @param <T> the context used by the visitor
  35  */
  36 public class QueryTreeWalker<T extends QueryTreeContext<T>> {
  37
  38   private final QueryTreeVisitor<T> visitor;
  39
  40   /**
  41    * Creates a new query walker that calls the given {@code visitor}.
  42    *
  43    * @param visitor the visitor to be called by this walker
  44    */
  45   public QueryTreeWalker(QueryTreeVisitor<T> visitor) {
  46     this.visitor = visitor;
  47   }
  48
  49   /**
  50    * @param tree the tree to be walked
  51    * @param context the context in which the tree is walked
  52    */
  53   public void walk(Tree tree, T context) throws QueryTreeException {
  54     walkInternal(flatten(tree, null), context);
  55   }
  56
  57   /**
  58    * Walks the tree and updates the context. This is a depth-first search,
  59    * always exploring children of the {@code tree} in the order of their
  60    * index 0 ... n - 1, where n is the number of children. Once all children
  61    * of the {@code node} are visited, the appropriate visitor's method
  62    * is called
  63    *
  64    * @param tree the tree to be walked
  65    * @param context the context of the visit
  66    */
  67   private void walkInternal(Tree tree, T context) {
  68     switch (tree.getType()) {
  69       case QueryLexer.CONJUNCTION:
  70         walkChildren(tree, context);
  71         visitor.visitConjunction(tree, context);
  72         postBooleanExpression(context);
  73         break;
  74       case QueryLexer.DISJUNCTION:
  75         walkChildren(tree, context);
  76         visitor.visitDisjunction(tree, context);
  77         postBooleanExpression(context);
  78         break;
  79       case QueryLexer.SEQUENCE:
  80         walkChildren(tree, context);
  81         visitor.visitSequence(tree, context);
  82         postBooleanExpression(context);
  83         break;
  84       case QueryLexer.NEGATION:
  85         walkChildren(tree, context);
  86         visitor.visitNegation(tree, context);
  87         postBooleanExpression(context);
  88         break;
  89       case QueryLexer.HAS:
  90         walkChildren(tree, context);
  91         visitor.visitContains(tree, context);
  92         postBooleanExpression(context);
  93         break;
  94       case QueryLexer.EQ:
  95         walkChildren(tree, context);
  96         visitor.visitEqual(tree, context);
  97         postBooleanExpression(context);
  98         break;
  99       case QueryLexer.LT:
 100         walkChildren(tree, context);
 101         visitor.visitLessThan(tree, context);
 102         postBooleanExpression(context);
 103         break;
 104       case QueryLexer.LE:
 105         walkChildren(tree, context);
 106         visitor.visitLessOrEqual(tree, context);
 107         postBooleanExpression(context);
 108         break;
 109       case QueryLexer.GT:
 110         walkChildren(tree, context);
 111         visitor.visitGreaterThan(tree, context);
 112         postBooleanExpression(context);
 113         break;
 114       case QueryLexer.GE:
 115         walkChildren(tree, context);
 116         visitor.visitGreaterOrEqual(tree, context);
 117         postBooleanExpression(context);
 118         break;
 119       case QueryLexer.FUZZY:
 120         walkInternal(tree.getChild(0), context);
 121         visitor.visitFuzzy(tree, context);
 122         break;
 123       case QueryLexer.LITERAL:
 124         walkInternal(tree.getChild(0), context);
 125         visitor.visitLiteral(tree, context);
 126         break;
 127       case QueryLexer.VALUE:
 128         visitor.visitValue(tree, context);
 129         break;
 130       case QueryLexer.FUNCTION:
 131         walkChildren(tree.getChild(1), context);
 132         visitor.visitFunction(tree, context);
 133         break;
 134       case QueryLexer.GLOBAL:
 135         visitor.visitGlobal(tree, context);
 136         break;
 137       default:
 138         visitor.visitOther(tree, context);
 139     }
 140   }
 141
 142   protected void postBooleanExpression(T context) {
 143     context.setReturnType(QueryTreeContext.Type.BOOL);
 144     context.setKind(QueryTreeContext.Kind.EXPRESSION);
 145   }
 146
 147   private void walkChildren(Tree parent, T context) {
 148     for (int i = 0; i < parent.getChildCount(); ++i) {
 149       walkInternal(parent.getChild(i), context.addChild());
 150     }
 151   }
 152
 153   public static Tree simplify(Tree tree) {
 154     for (int i = 0; i < tree.getChildCount(); ++i) {
 155       Tree child = tree.getChild(i);
 156       Tree optimized = simplify(child);
 157       if (child != optimized) {
 158         tree.setChild(i, optimized);
 159       }
 160     }
 161     switch (tree.getType()) {
 162       case QueryLexer.CONJUNCTION:
 163       case QueryLexer.DISJUNCTION:
 164       case QueryLexer.SEQUENCE:
 165         if (tree.getChildCount() == 1) {
 166           return tree.getChild(0);
 167         }
 168         break;
 169     }
 170     return tree;
 171   }
 172
 173   /**
 174    * Flattens the tree by pushing down the field name. For example, if
 175    * the tree looks like this:
 176    * <pre>
 177    *                EQ
 178    *             /      \
 179    *        VALUE         EQ
 180    *        /    \      /    \
 181    *      TEXT  field GLOBAL (N)
 182    * </pre>
 183    * Then we will output tree that looks like this:
 184    * <pre>
 185    *                EQ
 186    *             /      \
 187    *        VALUE       (N)
 188    *        /    \
 189    *      TEXT  field
 190    * </pre>
 191    * Here <code>(N)</code> is an arbitrary node. We also drop EQ if it
 192    * is in front of conjunction or disjunction. We do not drop it for
 193    * other comparators, as we want parsing to fail for foo &lt; (1 2).
 194    */
 195   private static Tree flatten(Tree tree, Tree restriction) throws QueryTreeException {
 196     if (tree.getType() == QueryLexer.VALUE) {
 197       return tree;
 198     }
 199     if (tree.getType() == QueryLexer.HAS || tree.getType() == QueryLexer.EQ) {
 200       Tree lhs = tree.getChild(0);
 201       if (lhs.getType() == QueryLexer.VALUE) {
 202         String myField = lhs.getChild(1).getText();
 203         if (restriction == null) {
 204           restriction = lhs;
 205         } else {
 206           String otherField = restriction.getChild(1).getText();
 207           if (!myField.equals(otherField)) {
 208             throw new QueryTreeException(
 209                 String.format("Restriction on %s and %s", otherField, myField),
 210                 lhs.getChild(1).getCharPositionInLine());
 211           }
 212         }
 213       }
 214       Tree rhs = tree.getChild(1);
 215       Tree flattened = flatten(rhs, restriction);
 216       if (flattened.getType() == QueryLexer.HAS
 217           || flattened.getType() == QueryLexer.EQ
 218           || flattened.getType() == QueryLexer.CONJUNCTION
 219           || flattened.getType() == QueryLexer.DISJUNCTION
 220           || flattened.getType() == QueryLexer.SEQUENCE) {
 221         return flattened;
 222       }
 223       if (flattened != rhs) {
 224         tree.setChild(1, flattened);
 225       }
 226       if (restriction != lhs) {
 227         tree.setChild(0, restriction);
 228       }
 229       return tree;
 230     }
 231     for (int i = 0; i < tree.getChildCount(); ++i) {
 232       Tree original = tree.getChild(i);
 233       Tree flattened = flatten(tree.getChild(i), restriction);
 234       if (original != flattened) {
 235         tree.setChild(i, flattened);
 236       }
 237     }
 238     return tree;
 239   }
 240 }