Return-Path: X-Original-To: apmail-accumulo-commits-archive@www.apache.org Delivered-To: apmail-accumulo-commits-archive@www.apache.org Received: from mail.apache.org (hermes.apache.org [140.211.11.3]) by minotaur.apache.org (Postfix) with SMTP id 5A31210979 for ; Tue, 26 Nov 2013 15:47:41 +0000 (UTC) Received: (qmail 33027 invoked by uid 500); 26 Nov 2013 15:47:26 -0000 Delivered-To: apmail-accumulo-commits-archive@accumulo.apache.org Received: (qmail 32233 invoked by uid 500); 26 Nov 2013 15:47:08 -0000 Mailing-List: contact commits-help@accumulo.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: dev@accumulo.apache.org Delivered-To: mailing list commits@accumulo.apache.org Received: (qmail 31785 invoked by uid 99); 26 Nov 2013 15:47:06 -0000 Received: from tyr.zones.apache.org (HELO tyr.zones.apache.org) (140.211.11.114) by apache.org (qpsmtpd/0.29) with ESMTP; Tue, 26 Nov 2013 15:47:06 +0000 Received: by tyr.zones.apache.org (Postfix, from userid 65534) id DB8939185B2; Tue, 26 Nov 2013 15:47:05 +0000 (UTC) Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit From: ecn@apache.org To: commits@accumulo.apache.org Date: Tue, 26 Nov 2013 15:47:14 -0000 Message-Id: In-Reply-To: References: X-Mailer: ASF-Git Admin Mailer Subject: [10/38] ACCUMULO-600 removed wikisearch from trunk http://git-wip-us.apache.org/repos/asf/accumulo/blob/8db62992/src/examples/wikisearch/query/src/main/java/org/apache/accumulo/examples/wikisearch/iterator/BooleanLogicIterator.java ---------------------------------------------------------------------- diff --git a/src/examples/wikisearch/query/src/main/java/org/apache/accumulo/examples/wikisearch/iterator/BooleanLogicIterator.java b/src/examples/wikisearch/query/src/main/java/org/apache/accumulo/examples/wikisearch/iterator/BooleanLogicIterator.java deleted file mode 100644 index 09ad8d3..0000000 --- a/src/examples/wikisearch/query/src/main/java/org/apache/accumulo/examples/wikisearch/iterator/BooleanLogicIterator.java +++ /dev/null @@ -1,1949 +0,0 @@ -/* - * Licensed to the Apache Software Foundation (ASF) under one or more - * contributor license agreements. See the NOTICE file distributed with - * this work for additional information regarding copyright ownership. - * The ASF licenses this file to You 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 org.apache.accumulo.examples.wikisearch.iterator; - -import java.io.IOException; -import java.util.ArrayList; -import java.util.Collection; -import java.util.Collections; -import java.util.Comparator; -import java.util.Enumeration; -import java.util.HashMap; -import java.util.HashSet; -import java.util.Iterator; -import java.util.List; -import java.util.Map; -import java.util.Map.Entry; -import java.util.PriorityQueue; -import java.util.Set; - -import org.apache.accumulo.core.data.ByteSequence; -import org.apache.accumulo.core.data.Key; -import org.apache.accumulo.core.data.Range; -import org.apache.accumulo.core.data.Value; -import org.apache.accumulo.core.iterators.IteratorEnvironment; -import org.apache.accumulo.core.iterators.OptionDescriber; -import org.apache.accumulo.core.iterators.SortedKeyValueIterator; -import org.apache.accumulo.examples.wikisearch.parser.JexlOperatorConstants; -import org.apache.accumulo.examples.wikisearch.parser.QueryParser; -import org.apache.accumulo.examples.wikisearch.parser.QueryParser.QueryTerm; -import org.apache.accumulo.examples.wikisearch.parser.RangeCalculator.RangeBounds; -import org.apache.accumulo.examples.wikisearch.parser.TreeNode; -import org.apache.accumulo.examples.wikisearch.util.FieldIndexKeyParser; -import org.apache.commons.jexl2.parser.ASTAndNode; -import org.apache.commons.jexl2.parser.ASTEQNode; -import org.apache.commons.jexl2.parser.ASTERNode; -import org.apache.commons.jexl2.parser.ASTGENode; -import org.apache.commons.jexl2.parser.ASTGTNode; -import org.apache.commons.jexl2.parser.ASTJexlScript; -import org.apache.commons.jexl2.parser.ASTLENode; -import org.apache.commons.jexl2.parser.ASTLTNode; -import org.apache.commons.jexl2.parser.ASTNENode; -import org.apache.commons.jexl2.parser.ASTNRNode; -import org.apache.commons.jexl2.parser.ASTNotNode; -import org.apache.commons.jexl2.parser.ASTOrNode; -import org.apache.commons.jexl2.parser.ParseException; -import org.apache.commons.jexl2.parser.ParserTreeConstants; -import org.apache.hadoop.io.Text; -import org.apache.log4j.Level; -import org.apache.log4j.Logger; - -import com.google.common.collect.Multimap; - -public class BooleanLogicIterator implements SortedKeyValueIterator, OptionDescriber { - - private static final Collection EMPTY_COL_FAMS = new ArrayList(); - protected static final Logger log = Logger.getLogger(BooleanLogicIterator.class); - public static final String QUERY_OPTION = "expr"; - public static final String TERM_CARDINALITIES = "TERM_CARDINALITIES"; // comma separated list of term : count - public static final String FIELD_INDEX_QUERY = "FIELD_INDEX_QUERY"; - public static final String FIELD_NAME_PREFIX = "fi\0"; - // -------------------------------------------------------------------------- - private static IteratorEnvironment env = new DefaultIteratorEnvironment(); - protected Text nullText = new Text(); - private Key topKey = null; - private Value topValue = null; - private SortedKeyValueIterator sourceIterator; - private BooleanLogicTreeNode root; - private PriorityQueue positives; - private ArrayList negatives = new ArrayList(); - private ArrayList rangerators; - private String updatedQuery; - private Map termCardinalities = new HashMap(); - private Range overallRange = null; - private FieldIndexKeyParser keyParser; - - public BooleanLogicIterator() { - keyParser = new FieldIndexKeyParser(); - rangerators = new ArrayList(); - } - - public BooleanLogicIterator(BooleanLogicIterator other, IteratorEnvironment env) { - if (other.sourceIterator != null) { - this.sourceIterator = other.sourceIterator.deepCopy(env); - } - keyParser = new FieldIndexKeyParser(); - rangerators = new ArrayList(); - log.debug("Congratulations, you've reached the BooleanLogicIterator"); - } - - public static void setLogLevel(Level lev) { - log.setLevel(lev); - } - - public void setDebug(Level lev) { - log.setLevel(lev); - } - - public SortedKeyValueIterator deepCopy(IteratorEnvironment env) { - return new BooleanLogicIterator(this, env); - } - - /** - * init is responsible for setting up the iterator. It will pull the serialized boolean parse tree from the options mapping and construct the - * appropriate sub-iterators - * - * Once initialized, this iterator will automatically seek to the first matching instance. If no top key exists, that means an event matching the boolean - * logic did not exist in the partition. Subsequent calls to next will move the iterator and all sub-iterators to the next match. - * - * @param source - * The underlying SortedkeyValueIterator. - * @param options - * A Map of options. - * @param env - * The iterator environment - * @throws IOException - */ - public void init(SortedKeyValueIterator source, Map options, IteratorEnvironment env) throws IOException { - validateOptions(options); - try { - if (log.isDebugEnabled()) { - log.debug("Congratulations, you've reached the BooleanLogicIterator.init method"); - } - // Copy the source iterator - sourceIterator = source.deepCopy(env); - - // Potentially take advantage of term cardinalities - String[] terms = null; - if (null != options.get(TERM_CARDINALITIES)) { - terms = options.get(TERM_CARDINALITIES).split(","); - for (String term : terms) { - int idx = term.indexOf(":"); - if (-1 != idx) { - termCardinalities.put(term.substring(0, idx), Long.parseLong(term.substring(idx + 1))); - } - } - } - - // Step 1: Parse the query - if (log.isDebugEnabled()) { - log.debug("QueryParser"); - } - QueryParser qp = new QueryParser(); - qp.execute(this.updatedQuery); // validateOptions updates the updatedQuery - - // need to build the query tree based on jexl parsing. - // Step 2: refactor QueryTree - inplace modification - if (log.isDebugEnabled()) { - log.debug("transformTreeNode"); - } - TreeNode tree = qp.getIteratorTree(); - this.root = transformTreeNode(tree); - - if (log.isDebugEnabled()) { - log.debug("refactorTree"); - } - this.root = refactorTree(this.root); - - if (log.isDebugEnabled()) { - log.debug("collapseBranches"); - } - collapseBranches(root); - - // Step 3: create iterators where we need them. - createIteratorTree(this.root); - if (log.isDebugEnabled()) { - log.debug("Query tree after iterator creation:\n\t" + this.root.getContents()); - } - // Step 4: split the positive and negative leaves - splitLeaves(this.root); - - } catch (ParseException ex) { - log.error("ParseException in init: " + ex); - throw new IllegalArgumentException("Failed to parse query", ex); - } catch (Exception ex) { - throw new IllegalArgumentException("probably had no indexed terms", ex); - } - - } - - /* ************************************************************************* - * Methods for sub iterator creation. - */ - private void createIteratorTree(BooleanLogicTreeNode root) throws IOException { - if (log.isDebugEnabled()) { - log.debug("BoolLogic createIteratorTree()"); - } - // Walk the tree, if all of your children are leaves, roll you into the - // appropriate iterator. - Enumeration dfe = root.depthFirstEnumeration(); - - while (dfe.hasMoreElements()) { - BooleanLogicTreeNode node = (BooleanLogicTreeNode) dfe.nextElement(); - if (!node.isLeaf() && node.getType() != ParserTreeConstants.JJTJEXLSCRIPT) { - // try to roll up. - if (canRollUp(node)) { - node.setRollUp(true); - if (node.getType() == ParserTreeConstants.JJTANDNODE) { - if (log.isDebugEnabled()) { - log.debug("creating IntersectingIterator"); - } - node.setUserObject(createIntersectingIterator(node)); - } else if (node.getType() == ParserTreeConstants.JJTORNODE) { - node.setUserObject(createOrIterator(node)); - } else { - // throw an error. - log.debug("createIteratorTree, encounterd a node type I do not know about: " + node.getType()); - log.debug("createIteratorTree, node contents: " + node.getContents()); - } - node.removeAllChildren(); - } - } - } - - // now for remaining leaves, create basic iterators. - // you can add in specialized iterator mappings here if necessary. - dfe = root.depthFirstEnumeration(); - while (dfe.hasMoreElements()) { - BooleanLogicTreeNode node = (BooleanLogicTreeNode) dfe.nextElement(); - if (node.isLeaf() && node.getType() != ParserTreeConstants.JJTANDNODE && node.getType() != ParserTreeConstants.JJTORNODE) { - node.setUserObject(createFieldIndexIterator(node)); - } - } - } - - private AndIterator createIntersectingIterator(BooleanLogicTreeNode node) throws IOException { - if (log.isDebugEnabled()) { - log.debug("createIntersectingIterator(node)"); - log.debug("fName: " + node.getFieldName() + " , fValue: " + node.getFieldValue() + " , operator: " + node.getFieldOperator()); - } - Text[] columnFamilies = new Text[node.getChildCount()]; - Text[] termValues = new Text[node.getChildCount()]; - boolean[] negationMask = new boolean[node.getChildCount()]; - Enumeration children = node.children(); - int i = 0; - while (children.hasMoreElements()) { - BooleanLogicTreeNode child = (BooleanLogicTreeNode) children.nextElement(); - columnFamilies[i] = child.getFieldName(); - termValues[i] = child.getFieldValue(); - negationMask[i] = child.isNegated(); - i++; - } - - AndIterator ii = new AndIterator(); - Map options = new HashMap(); - options.put(AndIterator.columnFamiliesOptionName, AndIterator.encodeColumns(columnFamilies)); - options.put(AndIterator.termValuesOptionName, AndIterator.encodeTermValues(termValues)); - options.put(AndIterator.notFlagsOptionName, AndIterator.encodeBooleans(negationMask)); - - ii.init(sourceIterator.deepCopy(env), options, env); - return ii; - } - - private OrIterator createOrIterator(BooleanLogicTreeNode node) throws IOException { - if (log.isDebugEnabled()) { - log.debug("createOrIterator(node)"); - log.debug("fName: " + node.getFieldName() + " , fValue: " + node.getFieldValue() + " , operator: " + node.getFieldOperator()); - } - - Enumeration children = node.children(); - ArrayList fams = new ArrayList(); - ArrayList quals = new ArrayList(); - while (children.hasMoreElements()) { - BooleanLogicTreeNode child = (BooleanLogicTreeNode) children.nextElement(); - fams.add(child.getFieldName()); - quals.add(child.getFieldValue()); - } - - OrIterator iter = new OrIterator(); - SortedKeyValueIterator source = sourceIterator.deepCopy(env); - for (int i = 0; i < fams.size(); i++) { - iter.addTerm(source, fams.get(i), quals.get(i), env); - } - - return iter; - } - - /* - * This takes the place of the SortedKeyIterator used previously. This iterator is bound to the partitioned table structure. When next is called it will jump - * rows as necessary internally versus needing to do it externally as was the case with the SortedKeyIterator. - */ - private FieldIndexIterator createFieldIndexIterator(BooleanLogicTreeNode node) throws IOException { - if (log.isDebugEnabled()) { - log.debug("BoolLogic.createFieldIndexIterator()"); - log.debug("fName: " + node.getFieldName() + " , fValue: " + node.getFieldValue() + " , operator: " + node.getFieldOperator()); - } - Text rowId = null; - sourceIterator.seek(new Range(), EMPTY_COL_FAMS, false); - if (sourceIterator.hasTop()) { - rowId = sourceIterator.getTopKey().getRow(); - } - - FieldIndexIterator iter = new FieldIndexIterator(node.getType(), rowId, node.getFieldName(), node.getFieldValue(), node.isNegated(), - node.getFieldOperator()); - - Map options = new HashMap(); - iter.init(sourceIterator.deepCopy(env), options, env); - if (log.isDebugEnabled()) { - FieldIndexIterator.setLogLevel(Level.DEBUG); - } else { - FieldIndexIterator.setLogLevel(Level.OFF); - } - - return iter; - } - - /* ************************************************************************* - * Methods for testing the tree WRT boolean logic. - */ - // After all iterator pointers have been advanced, test if the current - // record passes the boolean logic. - private boolean testTreeState() { - if (log.isDebugEnabled()) { - log.debug("BoolLogic testTreeState() begin"); - } - Enumeration dfe = this.root.depthFirstEnumeration(); - while (dfe.hasMoreElements()) { - BooleanLogicTreeNode node = (BooleanLogicTreeNode) dfe.nextElement(); - if (!node.isLeaf()) { - - int type = node.getType(); - if (type == ParserTreeConstants.JJTANDNODE) { // BooleanLogicTreeNode.NodeType.AND) { - handleAND(node); - } else if (type == ParserTreeConstants.JJTORNODE) {// BooleanLogicTreeNode.NodeType.OR) { - handleOR(node); - } else if (type == ParserTreeConstants.JJTJEXLSCRIPT) {// BooleanLogicTreeNode.NodeType.HEAD) { - handleHEAD(node); - } else if (type == ParserTreeConstants.JJTNOTNODE) { // BooleanLogicTreeNode.NodeType.NOT) { - // there should not be any "NOT"s. - // throw new Exception(); - } - } else { - // it is a leaf, if it is an AND or OR do something - if (node.getType() == ParserTreeConstants.JJTORNODE) {// BooleanLogicTreeNode.NodeType.OR) { //OrIterator - node.setValid(node.hasTop()); - node.reSet(); - node.addToSet(node.getTopKey()); - - } else if (node.getType() == ParserTreeConstants.JJTANDNODE || node.getType() == ParserTreeConstants.JJTEQNODE - || node.getType() == ParserTreeConstants.JJTERNODE || node.getType() == ParserTreeConstants.JJTLENODE - || node.getType() == ParserTreeConstants.JJTLTNODE || node.getType() == ParserTreeConstants.JJTGENODE - || node.getType() == ParserTreeConstants.JJTGTNODE) { - // sub iterator guarantees it is in its internal range, - // otherwise, no top. - node.setValid(node.hasTop()); - } - } - } - - if (log.isDebugEnabled()) { - log.debug("BoolLogic.testTreeState end, treeState:: " + this.root.getContents() + " , valid: " + root.isValid()); - } - return this.root.isValid(); - } - - private void handleHEAD(BooleanLogicTreeNode node) { - Enumeration children = node.children(); - while (children.hasMoreElements()) { - BooleanLogicTreeNode child = (BooleanLogicTreeNode) children.nextElement(); - - if (child.getType() == ParserTreeConstants.JJTANDNODE) {// BooleanLogicTreeNode.NodeType.AND) { - node.setValid(child.isValid()); - node.setTopKey(child.getTopKey()); - } else if (child.getType() == ParserTreeConstants.JJTORNODE) {// BooleanLogicTreeNode.NodeType.OR) { - node.setValid(child.isValid()); - node.setTopKey(child.getTopKey()); - } else if (child.getType() == ParserTreeConstants.JJTEQNODE || child.getType() == ParserTreeConstants.JJTERNODE - || child.getType() == ParserTreeConstants.JJTGTNODE || child.getType() == ParserTreeConstants.JJTGENODE - || child.getType() == ParserTreeConstants.JJTLTNODE || child.getType() == ParserTreeConstants.JJTLENODE) {// BooleanLogicTreeNode.NodeType.SEL) { - node.setValid(true); - node.setTopKey(child.getTopKey()); - if (child.getTopKey() == null) { - node.setValid(false); - } - } - }// end while - - // I have to be valid AND have a top key - if (node.isValid() && !node.hasTop()) { - node.setValid(false); - } - } - - private void handleAND(BooleanLogicTreeNode me) { - if (log.isDebugEnabled()) { - log.debug("handleAND::" + me.getContents()); - } - Enumeration children = me.children(); - me.setValid(true); // it's easier to prove false than true - - HashSet goodSet = new HashSet(); - HashSet badSet = new HashSet(); - while (children.hasMoreElements()) { - BooleanLogicTreeNode child = (BooleanLogicTreeNode) children.nextElement(); - - if (child.getType() == ParserTreeConstants.JJTEQNODE || child.getType() == ParserTreeConstants.JJTANDNODE - || child.getType() == ParserTreeConstants.JJTERNODE || child.getType() == ParserTreeConstants.JJTNENODE - || child.getType() == ParserTreeConstants.JJTGENODE || child.getType() == ParserTreeConstants.JJTLENODE - || child.getType() == ParserTreeConstants.JJTGTNODE || child.getType() == ParserTreeConstants.JJTLTNODE) { - - if (child.isNegated()) { - if (child.hasTop()) { - badSet.add(child.getTopKey()); - if (goodSet.contains(child.getTopKey())) { - me.setValid(false); - return; - } - if (child.isValid()) { - me.setValid(false); - return; - } - } - } else { - if (child.hasTop()) { - if (log.isDebugEnabled()) { - log.debug("handleAND, child node: " + child.getContents()); - } - // if you're in the bad set, you're done. - if (badSet.contains(child.getTopKey())) { - if (log.isDebugEnabled()) { - log.debug("handleAND, child is in bad set, setting parent false"); - } - me.setValid(false); - return; - } - - // if good set is empty, add it. - if (goodSet.isEmpty()) { - if (log.isDebugEnabled()) { - log.debug("handleAND, goodSet is empty, adding child: " + child.getContents()); - } - goodSet.add(child.getTopKey()); - } else { - // must be in the good set & not in the bad set - // if either fails, I'm false. - if (!goodSet.contains(child.getTopKey())) { - if (log.isDebugEnabled()) { - log.debug("handleAND, goodSet is not empty, and does NOT contain child, setting false. child: " + child.getContents()); - } - me.setValid(false); - return; - } else { - // trim the good set to this one value - // (handles the case were the initial encounters were ORs) - goodSet = new HashSet(); - goodSet.add(child.getTopKey()); - if (log.isDebugEnabled()) { - log.debug("handleAND, child in goodset, trim to this value: " + child.getContents()); - } - } - } - } else { - // test if its children are all false - if (child.getChildCount() > 0) { - Enumeration subchildren = child.children(); - boolean allFalse = true; - while (subchildren.hasMoreElements()) { - BooleanLogicTreeNode subchild = (BooleanLogicTreeNode) subchildren.nextElement(); - if (!subchild.isNegated()) { - allFalse = false; - break; - } else if (subchild.isNegated() && subchild.hasTop()) { - allFalse = false; - break; - } - } - if (!allFalse) { - me.setValid(false); - return; - } - } else { - // child returned a null value and is not a negation, this in turn makes me false. - me.setValid(false); - return; - } - } - } - - } else if (child.getType() == ParserTreeConstants.JJTORNODE) {// BooleanLogicTreeNode.NodeType.OR) { - - // NOTE: The OR may be an OrIterator in which case it will only produce - // a single unique identifier, or it may be a pure logical construct and - // be capable of producing multiple unique identifiers. - // This should handle all cases. - Iterator iter = child.getSetIterator(); - boolean goodSetEmpty = goodSet.isEmpty(); - boolean matchedOne = false; - boolean pureNegations = true; - if (!child.isValid()) { - if (log.isDebugEnabled()) { - log.debug("handleAND, child is an OR and it is not valid, setting false, ALL NEGATED?: " + child.isChildrenAllNegated()); - } - me.setValid(false); // I'm an AND if one of my children is false, I'm false. - return; - } else if (child.isValid() && !child.hasTop()) { - // pure negation, do nothing - } else if (child.isValid() && child.hasTop()) { // I need to match one - if (log.isDebugEnabled()) { - log.debug("handleAND, child OR, valid and has top, means not pureNegations"); - } - pureNegations = false; - while (iter.hasNext()) { - Key i = (Key) iter.next(); - if (child.isNegated()) { - badSet.add(i); - if (goodSet.contains(i)) { - if (log.isDebugEnabled()) { - log.debug("handleAND, child OR, goodSet contains bad value: " + i); - } - me.setValid(false); - return; - } - } else { - // if the good set is empty, then push all of my ids. - if (goodSetEmpty && !badSet.contains(i)) { - goodSet.add(i); - matchedOne = true; - } else { - // I need at least one to match - if (goodSet.contains(i)) { - matchedOne = true; - } - } - } - } - } - - // is the goodSet still empty? that means were were only negations - // otherwise, if it's not empty and we didn't match one, false - if (child.isNegated()) { - // we're ok - } else { - if (goodSet.isEmpty() && !pureNegations) { - if (log.isDebugEnabled()) { - log.debug("handleAND, child OR, empty goodset && !pureNegations, set false"); - } - // that's bad, we weren't negated, should've pushed something in there. - me.setValid(false); - return; - } else if (!goodSet.isEmpty() && !pureNegations) { // goodSet contains values. - if (!matchedOne) { // but we didn't match any. - if (log.isDebugEnabled()) { - log.debug("handleAND, child OR, goodSet had values but I didn't match any, false"); - } - me.setValid(false); - return; - } - - // we matched something, trim the set. - // i.e. two child ORs - goodSet = child.getIntersection(goodSet); - } - } - - } - }// end while - - if (goodSet.isEmpty()) { // && log.isDebugEnabled()) { - if (log.isDebugEnabled()) { - log.debug("handleAND-> goodSet is empty, pure negations?"); - } - } else { - me.setTopKey(Collections.min(goodSet)); - if (log.isDebugEnabled()) { - log.debug("End of handleAND, this node's topKey: " + me.getTopKey()); - } - } - } - - private void handleOR(BooleanLogicTreeNode me) { - Enumeration children = me.children(); - // I'm an OR node, need at least one positive. - me.setValid(false); - me.reSet(); - me.setTopKey(null); - boolean allNegated = true; - while (children.hasMoreElements()) { - // 3 cases for child: SEL, AND, OR - // and negation - BooleanLogicTreeNode child = (BooleanLogicTreeNode) children.nextElement(); - if (child.getType() == ParserTreeConstants.JJTEQNODE || child.getType() == ParserTreeConstants.JJTNENODE - || child.getType() == ParserTreeConstants.JJTANDNODE || child.getType() == ParserTreeConstants.JJTERNODE - || child.getType() == ParserTreeConstants.JJTNRNODE || child.getType() == ParserTreeConstants.JJTLENODE - || child.getType() == ParserTreeConstants.JJTLTNODE || child.getType() == ParserTreeConstants.JJTGENODE - || child.getType() == ParserTreeConstants.JJTGTNODE) { - - if (child.hasTop()) { - if (child.isNegated()) { - // do nothing. - } else { - allNegated = false; - // I have something add it to my set. - if (child.isValid()) { - me.addToSet(child.getTopKey()); - } - } - } else if (!child.isNegated()) { // I have a non-negated child - allNegated = false; - // that child could be pure negations in which case I'm true - me.setValid(child.isValid()); - } - - } else if (child.getType() == ParserTreeConstants.JJTORNODE) {// BooleanLogicTreeNode.NodeType.OR) { - if (child.hasTop()) { - if (!child.isNegated()) { - allNegated = false; - // add its rowIds to my rowIds - Iterator iter = child.getSetIterator(); - while (iter.hasNext()) { - Key i = (Key) iter.next(); - if (i != null) { - me.addToSet(i); - } - } - } - } else { - // Or node that doesn't have a top, check if it's valid or not - // because it could be pure negations itself. - if (child.isValid()) { - me.setValid(true); - } - } - } - }// end while - - if (allNegated) { - // do all my children have top? - children = me.children(); - while (children.hasMoreElements()) { - BooleanLogicTreeNode child = (BooleanLogicTreeNode) children.nextElement(); - if (!child.hasTop()) { - me.setValid(true); - me.setTopKey(null); - return; - } - } - me.setValid(false); - - } else { - Key k = me.getMinUniqueID(); - if (k == null) { - me.setValid(false); - } else { - me.setValid(true); - me.setTopKey(k); - } - } - } - - /* ************************************************************************* - * Utility methods. - */ - // Transforms the TreeNode tree of query.parser into the - // BooleanLogicTreeNodeJexl form. - public BooleanLogicTreeNode transformTreeNode(TreeNode node) throws ParseException { - if (node.getType().equals(ASTEQNode.class) || node.getType().equals(ASTNENode.class)) { - if (log.isDebugEnabled()) { - log.debug("Equals Node"); - } - - Multimap terms = node.getTerms(); - for (String fName : terms.keySet()) { - Collection values = terms.get(fName); - - for (QueryTerm t : values) { - if (null == t || null == t.getValue()) { - continue; - } - String fValue = t.getValue().toString(); - fValue = fValue.replaceAll("'", ""); - boolean negated = t.getOperator().equals("!="); - - if (!fName.startsWith(FIELD_NAME_PREFIX)) { - fName = FIELD_NAME_PREFIX + fName; - } - BooleanLogicTreeNode child = new BooleanLogicTreeNode(ParserTreeConstants.JJTEQNODE, fName, fValue, negated); - return child; - } - } - } - - if (node.getType().equals(ASTERNode.class) || node.getType().equals(ASTNRNode.class)) { - if (log.isDebugEnabled()) { - log.debug("Regex Node"); - } - - Multimap terms = node.getTerms(); - for (String fName : terms.keySet()) { - Collection values = terms.get(fName); - for (QueryTerm t : values) { - if (null == t || null == t.getValue()) { - continue; - } - String fValue = t.getValue().toString(); - fValue = fValue.replaceAll("'", ""); - boolean negated = node.getType().equals(ASTNRNode.class); - - if (!fName.startsWith(FIELD_NAME_PREFIX)) { - fName = FIELD_NAME_PREFIX + fName; - } - - BooleanLogicTreeNode child = new BooleanLogicTreeNode(ParserTreeConstants.JJTERNODE, fName, fValue, negated); - return child; - } - } - } - - if (node.getType().equals(ASTLTNode.class) || node.getType().equals(ASTLENode.class) || node.getType().equals(ASTGTNode.class) - || node.getType().equals(ASTGENode.class)) { - Multimap terms = node.getTerms(); - for (String fName : terms.keySet()) { - Collection values = terms.get(fName); - - if (!fName.startsWith(FIELD_NAME_PREFIX)) { - fName = FIELD_NAME_PREFIX + fName; - } - for (QueryTerm t : values) { - if (null == t || null == t.getValue()) { - continue; - } - String fValue = t.getValue().toString(); - fValue = fValue.replaceAll("'", "").toLowerCase(); - boolean negated = false; // to be negated, must be child of Not, which is handled elsewhere. - int mytype = JexlOperatorConstants.getJJTNodeType(t.getOperator()); - - BooleanLogicTreeNode child = new BooleanLogicTreeNode(mytype, fName, fValue, negated); - if (log.isDebugEnabled()) { - log.debug("adding child node: " + child.getContents()); - } - return child; - } - } - } - - BooleanLogicTreeNode returnNode = null; - - if (node.getType().equals(ASTAndNode.class) || node.getType().equals(ASTOrNode.class)) { - int parentType = node.getType().equals(ASTAndNode.class) ? ParserTreeConstants.JJTANDNODE : ParserTreeConstants.JJTORNODE; - if (log.isDebugEnabled()) { - log.debug("AND/OR node: " + parentType); - } - if (node.isLeaf() || !node.getTerms().isEmpty()) { - returnNode = new BooleanLogicTreeNode(parentType); - Multimap terms = node.getTerms(); - for (String fName : terms.keySet()) { - Collection values = terms.get(fName); - if (!fName.startsWith(FIELD_NAME_PREFIX)) { - fName = FIELD_NAME_PREFIX + fName; - } - for (QueryTerm t : values) { - if (null == t || null == t.getValue()) { - continue; - } - String fValue = t.getValue().toString(); - fValue = fValue.replaceAll("'", ""); - boolean negated = t.getOperator().equals("!="); - int mytype = JexlOperatorConstants.getJJTNodeType(t.getOperator()); - BooleanLogicTreeNode child = new BooleanLogicTreeNode(mytype, fName, fValue, negated); - if (log.isDebugEnabled()) { - log.debug("adding child node: " + child.getContents()); - } - returnNode.add(child); - } - } - } else { - returnNode = new BooleanLogicTreeNode(parentType); - - } - } else if (node.getType().equals(ASTNotNode.class)) { - if (log.isDebugEnabled()) { - log.debug("NOT node"); - } - if (node.isLeaf()) { - // NOTE: this should be cleaned up a bit. - Multimap terms = node.getTerms(); - for (String fName : terms.keySet()) { - Collection values = terms.get(fName); - - if (!fName.startsWith(FIELD_NAME_PREFIX)) { - fName = FIELD_NAME_PREFIX + fName; - } - for (QueryTerm t : values) { - if (null == t || null == t.getValue()) { - continue; - } - String fValue = t.getValue().toString(); - fValue = fValue.replaceAll("'", "").toLowerCase(); - boolean negated = !t.getOperator().equals("!="); - int mytype = JexlOperatorConstants.getJJTNodeType(t.getOperator()); - - if (!fName.startsWith(FIELD_NAME_PREFIX)) { - fName = FIELD_NAME_PREFIX + fName; - } - return new BooleanLogicTreeNode(mytype, fName, fValue, negated); - } - } - } else { - returnNode = new BooleanLogicTreeNode(ParserTreeConstants.JJTNOTNODE); - } - } else if (node.getType().equals(ASTJexlScript.class) || node.getType().getSimpleName().equals("RootNode")) { - - if (log.isDebugEnabled()) { - log.debug("ROOT/JexlScript node"); - } - if (node.isLeaf()) { - returnNode = new BooleanLogicTreeNode(ParserTreeConstants.JJTJEXLSCRIPT); - // NOTE: this should be cleaned up a bit. - Multimap terms = node.getTerms(); - for (String fName : terms.keySet()) { - Collection values = terms.get(fName); - - if (!fName.startsWith(FIELD_NAME_PREFIX)) { - fName = FIELD_NAME_PREFIX + fName; - } - for (QueryTerm t : values) { - if (null == t || null == t.getValue()) { - continue; - } - String fValue = t.getValue().toString(); - fValue = fValue.replaceAll("'", "").toLowerCase(); - boolean negated = t.getOperator().equals("!="); - int mytype = JexlOperatorConstants.getJJTNodeType(t.getOperator()); - - BooleanLogicTreeNode child = new BooleanLogicTreeNode(mytype, fName, fValue, negated); - returnNode.add(child); - return returnNode; - } - } - } else { - returnNode = new BooleanLogicTreeNode(ParserTreeConstants.JJTJEXLSCRIPT); - } - } else { - log.error("Currently Unsupported Node type: " + node.getClass().getName() + " \t" + node.getType()); - } - for (TreeNode child : node.getChildren()) { - returnNode.add(transformTreeNode(child)); - } - - return returnNode; - } - - // After tree conflicts have been resolve, we can collapse branches where - // leaves have been pruned. - public static void collapseBranches(BooleanLogicTreeNode myroot) throws Exception { - - // NOTE: doing a depth first enumeration didn't wory when I started - // removing nodes halfway through. The following method does work, - // it's essentially a reverse breadth first traversal. - List nodes = new ArrayList(); - Enumeration bfe = myroot.breadthFirstEnumeration(); - - while (bfe.hasMoreElements()) { - BooleanLogicTreeNode node = (BooleanLogicTreeNode) bfe.nextElement(); - nodes.add(node); - } - - // walk backwards - for (int i = nodes.size() - 1; i >= 0; i--) { - BooleanLogicTreeNode node = nodes.get(i); - if (log.isDebugEnabled()) { - log.debug("collapseBranches, inspecting node: " + node.toString() + " " + node.printNode()); - } - - if (node.getType() == ParserTreeConstants.JJTANDNODE || node.getType() == ParserTreeConstants.JJTORNODE) { - if (node.getChildCount() == 0 && !node.isRangeNode()) { - node.removeFromParent(); - } else if (node.getChildCount() == 1) { - BooleanLogicTreeNode p = (BooleanLogicTreeNode) node.getParent(); - BooleanLogicTreeNode c = (BooleanLogicTreeNode) node.getFirstChild(); - node.removeFromParent(); - p.add(c); - - } - } else if (node.getType() == ParserTreeConstants.JJTJEXLSCRIPT) { - if (node.getChildCount() == 0) { - if (log.isDebugEnabled()) { - log.debug("collapseBranches, headNode has no children"); - } - throw new Exception("Head node has no children."); - } - } - } - - } - - public BooleanLogicTreeNode refactorTree(BooleanLogicTreeNode myroot) { - List nodes = new ArrayList(); - Enumeration bfe = myroot.breadthFirstEnumeration(); - - while (bfe.hasMoreElements()) { - BooleanLogicTreeNode node = (BooleanLogicTreeNode) bfe.nextElement(); - nodes.add(node); - } - - // walk backwards - for (int i = nodes.size() - 1; i >= 0; i--) { - BooleanLogicTreeNode node = nodes.get(i); - if (node.getType() == ParserTreeConstants.JJTANDNODE || node.getType() == ParserTreeConstants.JJTORNODE) { - // 1. check to see if all children are negated - // 2. check to see if we have to handle ranges. - - Map ranges = new HashMap(); - Enumeration children = node.children(); - boolean allNegated = true; - while (children.hasMoreElements()) { - BooleanLogicTreeNode child = (BooleanLogicTreeNode) children.nextElement(); - if (!child.isNegated()) { - allNegated = false; - // break; - } - - // currently we are not allowing unbounded ranges, so they must sit under an AND node. - if (node.getType() == ParserTreeConstants.JJTANDNODE) { - // check for ranges - if (child.getType() == JexlOperatorConstants.JJTGTNODE) { - if (log.isDebugEnabled()) { - log.debug("refactor: GT " + child.getContents()); - } - if (ranges.containsKey(child.getFieldName())) { - RangeBounds rb = ranges.get(child.getFieldName()); - rb.setLower(child.getFieldValue()); - } else { - RangeBounds rb = new RangeBounds(); - rb.setLower(child.getFieldValue()); - ranges.put(child.getFieldName(), rb); - } - } else if (child.getType() == JexlOperatorConstants.JJTGENODE) { - if (log.isDebugEnabled()) { - log.debug("refactor: GE " + child.getContents()); - } - if (ranges.containsKey(child.getFieldName())) { - RangeBounds rb = ranges.get(child.getFieldName()); - rb.setLower(child.getFieldValue()); - } else { - RangeBounds rb = new RangeBounds(); - rb.setLower(child.getFieldValue()); - ranges.put(child.getFieldName(), rb); - } - } else if (child.getType() == JexlOperatorConstants.JJTLTNODE) { - if (log.isDebugEnabled()) { - log.debug("refactor: LT " + child.getContents()); - } - if (ranges.containsKey(child.getFieldName())) { - RangeBounds rb = ranges.get(child.getFieldName()); - rb.setUpper(child.getFieldValue()); - } else { - RangeBounds rb = new RangeBounds(); - rb.setUpper(child.getFieldValue()); - ranges.put(child.getFieldName(), rb); - } - } else if (child.getType() == JexlOperatorConstants.JJTLENODE) { - if (log.isDebugEnabled()) { - log.debug("refactor: LE " + child.getContents()); - } - if (ranges.containsKey(child.getFieldName())) { - RangeBounds rb = ranges.get(child.getFieldName()); - rb.setUpper(child.getFieldValue()); - } else { - RangeBounds rb = new RangeBounds(); - rb.setUpper(child.getFieldValue()); - ranges.put(child.getFieldName(), rb); - } - } - } - } - if (allNegated) { - node.setChildrenAllNegated(true); - } - - // see if the AND node had a range. - if (node.getType() == ParserTreeConstants.JJTANDNODE) { - - // if(ranges.containsKey(node.getFieldName())){ - if (!ranges.isEmpty()) { - // we have a range, process it - if (node.getChildCount() <= 2 && ranges.size() == 1) { - if (log.isDebugEnabled()) { - log.debug("AND range 2 children or less"); - } - // only has a range, modify the node - node.setType(ParserTreeConstants.JJTORNODE); - node.removeAllChildren(); - // RangeBounds rb = ranges.get(node.getFieldName()); - - for (Entry entry : ranges.entrySet()) { - Text fName = entry.getKey(); - RangeBounds rb = entry.getValue(); - node.setFieldName(fName); - node.setFieldValue(new Text("")); - node.setLowerBound(rb.getLower()); - node.setUpperBound(rb.getUpper()); - node.setRangeNode(true); - } - - rangerators.add(node); - - if (log.isDebugEnabled()) { - log.debug("refactor: " + node.getContents()); - log.debug("refactor: " + node.getLowerBound() + " " + node.getUpperBound()); - } - - } else { - if (log.isDebugEnabled()) { - log.debug("AND range more than 2 children"); - } - // node has range plus other children, create another node from the range - // remove lt,le,gt,ge from parent and push in a single node - - // removing nodes via enumeration doesn't work, push into a list - // and walk backwards - List temp = new ArrayList(); - Enumeration e = node.children(); - while (e.hasMoreElements()) { - BooleanLogicTreeNode c = (BooleanLogicTreeNode) e.nextElement(); - temp.add(c); - } - - for (int j = temp.size() - 1; j >= 0; j--) { - BooleanLogicTreeNode c = temp.get(j); - if (c.getType() == JexlOperatorConstants.JJTLENODE || c.getType() == JexlOperatorConstants.JJTLTNODE - || c.getType() == JexlOperatorConstants.JJTGENODE || c.getType() == JexlOperatorConstants.JJTGTNODE) { - c.removeFromParent(); - } - } - - for (Entry entry : ranges.entrySet()) { - Text fName = entry.getKey(); - BooleanLogicTreeNode nchild = new BooleanLogicTreeNode(ParserTreeConstants.JJTORNODE, fName.toString(), ""); - RangeBounds rb = entry.getValue(); - nchild.setFieldValue(new Text("")); - nchild.setLowerBound(rb.getLower()); - nchild.setUpperBound(rb.getUpper()); - nchild.setRangeNode(true); - node.add(nchild); - rangerators.add(nchild); - } - - if (log.isDebugEnabled()) { - log.debug("refactor: " + node.getContents()); - } - } - } - } - - } - } - - return myroot; - - } - - // If all children are of type SEL, roll this up into an AND or OR node. - private static boolean canRollUp(BooleanLogicTreeNode parent) { - if (log.isDebugEnabled()) { - log.debug("canRollUp: testing " + parent.getContents()); - } - if (parent.getChildCount() < 1) { - if (log.isDebugEnabled()) { - log.debug("canRollUp: child count < 1, return false"); - } - return false; - } - Enumeration e = parent.children(); - while (e.hasMoreElements()) { - BooleanLogicTreeNode child = (BooleanLogicTreeNode) e.nextElement(); - - if (child.getType() != ParserTreeConstants.JJTEQNODE) {// BooleanLogicTreeNode.NodeType.SEL) { - if (log.isDebugEnabled()) { - log.debug("canRollUp: child.getType -> " + ParserTreeConstants.jjtNodeName[child.getType()] + " int: " + child.getType() + " return false"); - } - return false; - } - - if (child.isNegated()) { - if (log.isDebugEnabled()) { - log.debug("canRollUp: child.isNegated, return false"); - } - return false; - } - - if (child.getFieldValue().toString().contains("*")) { - if (log.isDebugEnabled()) { - log.debug("canRollUp: child has wildcard: " + child.getFieldValue()); - } - return false; - } - } - return true; - } - - /** - * Small utility function to print out the depth-first enumeration of the tree. Specify the root or sub root of the tree you wish to view. - * - * @param root - * The root node of the tree or sub-tree. - */ - public static void showDepthFirstTraversal(BooleanLogicTreeNode root) { - System.out.println("DepthFirstTraversal"); - Enumeration e = root.depthFirstEnumeration(); - int i = -1; - while (e.hasMoreElements()) { - i += 1; - BooleanLogicTreeNode n = (BooleanLogicTreeNode) e.nextElement(); - System.out.println(i + " : " + n); - } - } - - public static void showBreadthFirstTraversal(BooleanLogicTreeNode root) { - System.out.println("BreadthFirstTraversal"); - log.debug("BooleanLogicIterator.showBreadthFirstTraversal()"); - Enumeration e = root.breadthFirstEnumeration(); - int i = -1; - while (e.hasMoreElements()) { - i += 1; - BooleanLogicTreeNode n = (BooleanLogicTreeNode) e.nextElement(); - System.out.println(i + " : " + n); - log.debug(i + " : " + n); - } - } - - private void splitLeaves(BooleanLogicTreeNode node) { - if (log.isDebugEnabled()) { - log.debug("BoolLogic: splitLeaves()"); - } - positives = new PriorityQueue(10, new BooleanLogicTreeNodeComparator()); - // positives = new ArrayList(); - negatives.clear(); - - Enumeration dfe = node.depthFirstEnumeration(); - while (dfe.hasMoreElements()) { - BooleanLogicTreeNode elem = (BooleanLogicTreeNode) dfe.nextElement(); - - if (elem.isLeaf()) { - if (elem.isNegated()) { - negatives.add(elem); - } else { - positives.add(elem); - } - } - } - } - - private void reHeapPriorityQueue(BooleanLogicTreeNode node) { - positives.clear(); - Enumeration dfe = node.depthFirstEnumeration(); - BooleanLogicTreeNode elem; - while (dfe.hasMoreElements()) { - elem = (BooleanLogicTreeNode) dfe.nextElement(); - if (elem.isLeaf() && !elem.isNegated()) { - positives.add(elem); - } - } - } - - /* ************************************************************************* - * The iterator interface methods. - */ - public boolean hasTop() { - return (topKey != null); - } - - public Key getTopKey() { - if (log.isDebugEnabled()) { - log.debug("getTopKey: " + topKey); - } - return topKey; - } - - private void setTopKey(Key key) { - if (this.overallRange != null && key != null) { - if (overallRange.getEndKey() != null) { // if null end key, that means range is to the end of the tablet. - if (!this.overallRange.contains(key)) { - topKey = null; - return; - } - } - } - topKey = key; - } - - public Value getTopValue() { - if (topValue == null) { - topValue = new Value(new byte[0]); - } - return topValue; - } - - private void resetNegatives() { - for (BooleanLogicTreeNode neg : negatives) { - neg.setTopKey(null); - neg.setValid(true); - } - } - - private String getEventKeyUid(Key k) { - if (k == null || k.getColumnFamily() == null) { - return null; - } else { - return k.getColumnFamily().toString(); - } - } - - private String getIndexKeyUid(Key k) { - try { - int idx = 0; - String sKey = k.getColumnQualifier().toString(); - idx = sKey.indexOf("\0"); - return sKey.substring(idx + 1); - } catch (Exception e) { - return null; - } - } - - /* - * Remember, the Key in the BooleanLogicTreeNode is different structurally than the Key in its sub iterator because the key BooleanLogic needs to return is an - * event key created from the index key (which is what the sub iterators are looking at!) - */ - private Key getOptimizedAdvanceKey() throws IOException { - if (log.isDebugEnabled()) { - log.debug("getOptimizedAdvanceKey() called"); - } - Enumeration bfe = root.breadthFirstEnumeration(); - ArrayList bfl = new ArrayList(); - while (bfe.hasMoreElements()) { - BooleanLogicTreeNode node = (BooleanLogicTreeNode) bfe.nextElement(); - if (!node.isNegated()) { - node.setAdvanceKey(node.getTopKey()); - node.setDone(false); - bfl.add(node); - } - } - - // walk the tree backwards - for (int i = bfl.size() - 1; i >= 0; i--) { - if (bfl.get(i).isLeaf() || bfl.get(i).isNegated()) { - if (log.isDebugEnabled()) { - log.debug("leaf, isDone?: " + bfl.get(i).isDone()); - } - continue; - } - - BooleanLogicTreeNode node = bfl.get(i); - node.setDone(false); - if (log.isDebugEnabled()) { - log.debug("for loop, node: " + node + " isDone? " + node.isDone()); - } - if (node.getType() == ParserTreeConstants.JJTANDNODE) { - // get max - BooleanLogicTreeNode max = null; - Enumeration children = node.children(); - boolean firstTime = true; - while (children.hasMoreElements()) { - BooleanLogicTreeNode child = (BooleanLogicTreeNode) children.nextElement(); - - if (child.isNegated() || child.isChildrenAllNegated()) { - continue; - } - - // all advance keys were initially set from topkey for the leaves. - if (child.getAdvanceKey() == null) { - log.debug("\tchild does not advance key: " + child.printNode()); - // i'm an and, i have a child that's done, mark me as done. - node.setDone(true); - break; - } else { - log.debug("\tchild advanceKey: " + child.getAdvanceKey()); - } - - if (firstTime) { - firstTime = false; - max = child; - if (log.isDebugEnabled()) { - log.debug("\tAND block, first valid child: " + child); - } - continue; - } - - log.debug("\tAND block, max: " + max); - log.debug("\tAND block, child: " + child); - - // first test row - if (max.getAdvanceKey().getRow().compareTo(child.getAdvanceKey().getRow()) < 0) { - max = child; - if (log.isDebugEnabled()) { - log.debug("\tAND block, child row greater, new max."); - } - continue; - } - - // if rows are equal, test uids - String uid_max = getEventKeyUid(max.getAdvanceKey()); - String uid_child = getEventKeyUid(child.getAdvanceKey()); - if (log.isDebugEnabled()) { - if (uid_max == null) { - log.debug("\tuid_max is currently null"); - } else { - log.debug("\tuid_max: " + uid_max); - } - if (uid_child == null) { - log.debug("\tuid_child is null"); - } else { - log.debug("\tuid_child: " + uid_child); - } - } - - if (uid_max != null && uid_child != null) { - if (uid_max.compareTo(uid_child) < 0) { - max = child; - } - } else if (uid_child == null) { // one or the other is null so we want the next row - max = child; - log.debug("uid_child is null, we need to grab the next row."); - break; - } else { - log.debug("max is null and child is not, who should we keep? child: " + child); - break; - } - } // end while - if (log.isDebugEnabled()) { - log.debug("attemptOptimization: AND with children, max: " + max); - } - if (max != null) { - node.setAdvanceKey(max.getAdvanceKey()); - } else { - if (log.isDebugEnabled()) { - log.debug("AND block finished, max is null"); - } - node.setDone(true); - } - - } else if (node.getType() == ParserTreeConstants.JJTORNODE) { - // get min - BooleanLogicTreeNode min = null; - Enumeration children = node.children(); - boolean firstTime = true; - int numChildren = node.getChildCount(); - int allChildrenDone = 0; - - while (children.hasMoreElements()) { - BooleanLogicTreeNode child = (BooleanLogicTreeNode) children.nextElement(); - - if (log.isDebugEnabled()) { - log.debug("\tOR block start, child: " + child); - } - if (child.isNegated() || child.isChildrenAllNegated()) { - if (log.isDebugEnabled()) { - log.debug("\tskip negated child: " + child); - } - numChildren -= 1; - continue; - } - if (child.isDone()) { - if (log.isDebugEnabled()) { - log.debug("\tchild is done: " + child); - } - allChildrenDone += 1; - if (numChildren == allChildrenDone) { - if (log.isDebugEnabled()) { - log.debug("\tnumChildren==allChildrenDone, setDone & break"); - } - // we're done here - node.setDone(true); - break; - } - } - - if (child.getAdvanceKey() == null) { - log.debug("\tOR child doesn't have top or an AdvanceKey"); - continue; - } - if (firstTime) { - if (log.isDebugEnabled()) { - log.debug("\tOR block, first valid node, min=child: " + child + " advanceKey: " + child.getAdvanceKey()); - } - - firstTime = false; - min = child; - continue; - } - if (log.isDebugEnabled()) { - log.debug("\tOR block, min: " + min); - log.debug("\tOR block, child: " + child); - } - if (min.getAdvanceKey().getRow().toString().compareTo(child.getAdvanceKey().getRow().toString()) > 0) { - // child row is less than min, set min to child - min = child; - if (log.isDebugEnabled()) { - log.debug("\tmin row was greater than child, min=child: " + min); - } - continue; - - } else if (min.getAdvanceKey().getRow().compareTo(child.getAdvanceKey().getRow()) < 0) { - // min row is less child, skip - if (log.isDebugEnabled()) { - log.debug("\tmin row less than childs, keep min: " + min); - } - continue; - - } else { // they're equal, test uids - String uid_min = getEventKeyUid(min.getAdvanceKey()); - String uid_child = getEventKeyUid(child.getAdvanceKey()); - if (log.isDebugEnabled()) { - log.debug("\ttesting uids, uid_min: " + uid_min + " uid_child: " + uid_child); - } - if (uid_min != null && uid_child != null) { - if (uid_min.compareTo(uid_child) > 0) { - - min = child; - if (log.isDebugEnabled()) { - log.debug("\tuid_min > uid_child, set min to child: " + min); - } - } - } else if (uid_min == null) { - if (log.isDebugEnabled()) { - log.debug("\tuid_min is null, take childs: " + uid_child); - } - min = child; - } - } - }// end while - if (log.isDebugEnabled()) { - log.debug("attemptOptimization: OR with children, min: " + min); - } - - if (min != null) { - if (log.isDebugEnabled()) { - log.debug("OR block, min != null, advanceKey? " + min.getAdvanceKey()); - } - node.setAdvanceKey(min.getAdvanceKey()); - } else { - log.debug("OR block, min is null..." + min); - node.setAdvanceKey(null); - node.setDone(true); - } - - } else if (node.getType() == ParserTreeConstants.JJTJEXLSCRIPT) { // HEAD node - if (log.isDebugEnabled()) { - log.debug("getOptimizedAdvanceKey, HEAD node"); - } - BooleanLogicTreeNode child = (BooleanLogicTreeNode) node.getFirstChild(); - - if (child.isDone()) { - if (log.isDebugEnabled()) { - log.debug("Head node's child is done, need to move to the next row"); - } - Key k = child.getAdvanceKey(); - if (k == null) { - if (log.isDebugEnabled()) { - log.debug("HEAD node, advance key is null, try to grab next row from topKey"); - } - if (hasTop()) { - k = this.getTopKey(); - child.setAdvanceKey(new Key(new Text(k.getRow().toString() + "\1"))); - } else { - return null; - } - } else { - Text row = new Text(k.getRow().toString() + "\1"); - k = new Key(row); - child.setAdvanceKey(k); - } - - } - if (log.isDebugEnabled()) { - log.debug("advance Key: " + child.getAdvanceKey()); - } - Key key = new Key(child.getAdvanceKey().getRow(), child.getAdvanceKey().getColumnFamily(), child.getAdvanceKey().getColumnFamily()); - return key; - - }// end else - }// end for - return null; - } - - /* - * The incoming jump key has been formatted into the structure of an index key, but the leaves are eventkeys - */ - private boolean jump(Key jumpKey) throws IOException { - if (log.isDebugEnabled()) { - log.debug("JUMP!"); - } - Enumeration bfe = root.breadthFirstEnumeration(); - while (bfe.hasMoreElements()) { - BooleanLogicTreeNode n = (BooleanLogicTreeNode) bfe.nextElement(); - n.setAdvanceKey(null); - } // now advance all nodes to the advance key - - if (log.isDebugEnabled()) { - log.debug("jump, All leaves need to advance to: " + jumpKey); - } - - String advanceUid = getIndexKeyUid(jumpKey); - if (log.isDebugEnabled()) { - log.debug("advanceUid => " + advanceUid); - } - boolean ok = true; - for (BooleanLogicTreeNode leaf : positives) { - leaf.jump(jumpKey); - } - return ok; - } - - @SuppressWarnings("unused") - public void next() throws IOException { - if (log.isDebugEnabled()) { - log.debug("next() method called"); - } - boolean finished = false; - boolean ok = true; - if (positives.isEmpty()) { - setTopKey(null); - return; - } - - Key previousJumpKey = null; - while (!finished) { - - Key jumpKey = this.getOptimizedAdvanceKey(); - - if (jumpKey == null) { // stop? - if (log.isDebugEnabled()) { - log.debug("next(), jump key is null, stopping"); - } - setTopKey(null); - return; - } - - if (log.isDebugEnabled()) { - if (jumpKey != null) { - log.debug("next(), jumpKey: " + jumpKey); - } else { - log.debug("jumpKey is null"); - } - } - - boolean same = false; - if (jumpKey != null && topKey != null) { - // check that the uid's are not the same - same = getIndexKeyUid(jumpKey).equals(getEventKeyUid(topKey)); - if (log.isDebugEnabled()) { - log.debug("jumpKeyUid: " + getIndexKeyUid(jumpKey) + " topKeyUid: " + getEventKeyUid(topKey)); - } - } - - if (log.isDebugEnabled()) { - log.debug("previousJumpKey: " + previousJumpKey); - log.debug("current JumpKey: " + jumpKey); - } - - if (jumpKey != null && !this.overallRange.contains(jumpKey)) { - if (log.isDebugEnabled()) { - log.debug("jumpKey is outside of range, that means the next key is out of range, stopping"); - log.debug("jumpKey: " + jumpKey + " overallRange.endKey: " + overallRange.getEndKey()); - } - // stop - setTopKey(null); - return; - } - - boolean previousSame = false; - if (previousJumpKey != null && jumpKey != null) { - previousSame = previousJumpKey.equals(jumpKey); - } - // ----------------------------------- - // OPTIMIZED block - if (jumpKey != null && !same && !previousSame && ok) { - previousJumpKey = jumpKey; - ok = jump(jumpKey); // attempt to jump everybody forward to this row and uid. - // tryJump = false; - - // now test the tree state. - if (testTreeState()) { - Key tempKey = root.getTopKey(); - // it is potentially valid, now we need to seek all of the negatives - if (!negatives.isEmpty()) { - advanceNegatives(this.root.getTopKey()); - if (!testTreeState()) { - continue; - } - } - - if (root.getTopKey().equals(tempKey)) { - // it's valid set nextKey and make sure it's not the same as topKey. - if (log.isDebugEnabled()) { - if (this.root.hasTop()) { - log.debug("this.root.getTopKey()->" + this.root.getTopKey()); - } else { - log.debug("next, this.root.getTopKey() is null"); - } - - if (topKey != null) { - log.debug("topKey->" + topKey); - - } else { - log.debug("topKey is null"); - } - } - if (compare(topKey, this.root.getTopKey()) != 0) { - // topKey = this.root.getTopKey(); - setTopKey(this.root.getTopKey()); - return; - } - } - } - - // -------------------------------------- - // Regular next block - } else { - - reHeapPriorityQueue(this.root); - BooleanLogicTreeNode node; - - while (true) { - node = positives.poll(); - if (!node.isDone() && node.hasTop()) { - break; - } - - if (positives.isEmpty()) { - setTopKey(null); - return; - } - } - - if (log.isDebugEnabled()) { - if (jumpKey == null) { - log.debug("no jump, jumpKey is null"); - } else if (topKey == null) { - log.debug("no jump, jumpKey: " + jumpKey + " topKey: null"); - } else { - log.debug("no jump, jumpKey: " + jumpKey + " topKey: " + topKey); - } - log.debug("next, (no jump) min node: " + node); - log.debug(node); - } - node.next(); - resetNegatives(); - - if (!node.hasTop()) { - // it may be part of an or, so it could be ok. - node.setValid(false); - if (testTreeState()) { - // it's valid set nextKey and make sure it's not the same as topKey. - if (topKey.compareTo(this.root.getTopKey()) != 0) { - // topKey = this.root.getTopKey(); - if (this.overallRange != null) { - if (this.overallRange.contains(root.getTopKey())) { - setTopKey(this.root.getTopKey()); - return; - } else { - setTopKey(null); - finished = true; - return; - } - - } else { - setTopKey(this.root.getTopKey()); - return; - } - } - } - } else { - - if (overallRange.contains(node.getTopKey())) { - // the node had something so push it back into priority queue - positives.add(node); - } - - // now test the tree state. - if (testTreeState()) { - Key tempKey = root.getTopKey(); - // it is potentially valid, now we need to seek all of the negatives - if (!negatives.isEmpty()) { - advanceNegatives(this.root.getTopKey()); - if (!testTreeState()) { - continue; - } - } - - if (root.getTopKey().equals(tempKey)) { - // it's valid set nextKey and make sure it's not the same as topKey. - if (log.isDebugEnabled()) { - if (this.root.hasTop()) { - log.debug("this.root.getTopKey()->" + this.root.getTopKey()); - } else { - log.debug("next, this.root.getTopKey() is null"); - } - - if (topKey != null) { - log.debug("topKey->" + topKey); - - } else { - log.debug("topKey is null"); - } - } - if (compare(topKey, this.root.getTopKey()) != 0) { - // topKey = this.root.getTopKey(); - if (this.overallRange != null) { - if (overallRange.contains(this.root.getTopKey())) { - setTopKey(this.root.getTopKey()); - return; - } else { - topKey = null; - finished = true; - return; - } - } else { - setTopKey(this.root.getTopKey()); - return; - } - } - } - } - - } - - // is the priority queue empty? - if (positives.isEmpty()) { - finished = true; - topKey = null; - } - } - } - } - - /* - * create a range for the given row of the - */ - private void advanceNegatives(Key k) throws IOException { - if (log.isDebugEnabled()) { - log.debug("advancingNegatives for Key: " + k); - } - Text rowID = k.getRow(); - Text colFam = k.getColumnFamily(); - - for (BooleanLogicTreeNode neg : negatives) { - Key startKey = new Key(rowID, neg.getFieldName(), new Text(neg.getFieldValue() + "\0" + colFam)); - Key endKey = new Key(rowID, neg.getFieldName(), new Text(neg.getFieldValue() + "\0" + colFam + "\1")); - Range range = new Range(startKey, true, endKey, false); - - if (log.isDebugEnabled()) { - log.debug("range: " + range); - } - neg.seek(range, EMPTY_COL_FAMS, false); - - if (neg.hasTop()) { - neg.setValid(false); - } - if (log.isDebugEnabled()) { - if (neg.hasTop()) { - log.debug("neg top key: " + neg.getTopKey()); - } else { - log.debug("neg has no top"); - } - } - } - } - - public void seek(Range range, Collection columnFamilies, boolean inclusive) throws IOException { - this.overallRange = range; - if (log.isDebugEnabled()) { - log.debug("seek, overallRange: " + overallRange); - } - // Given some criteria, advance all iterators to that position. - // NOTE: All of our iterators exist in the leaves. - topKey = null; - root.setTopKey(null); - - // set up the range iterators for the given seek range. - // these should exist in the positives as OR iterators, but need special setup. - setupRangerators(range); - - // don't take this out, if you jump rows on the tablet you could have - // pulled nodes out of the positives priority queue. On a call to seek - // it is usually jumping rows, so everything needs to become possibly - // valid again. - reHeapPriorityQueue(this.root); - for (BooleanLogicTreeNode node : positives) { - node.setDone(false); - node.seek(range, columnFamilies, inclusive); - if (log.isDebugEnabled()) { - String tk = "empty"; - if (node.hasTop()) { - tk = node.getTopKey().toString(); - } - log.debug("leaf: " + node.getContents() + " topKey: " + tk); - } - } - - // Now that all nodes have been seek'd recreate the priorityQueue to sort them properly. - splitLeaves(this.root); - resetNegatives(); - - // test Tree, if it's not valid, call next - if (testTreeState() && overallRange.contains(root.getTopKey())) { - if (!negatives.isEmpty()) { - // now advance negatives - advanceNegatives(this.root.getTopKey()); - if (!testTreeState()) { - next(); - } - } - - if (log.isDebugEnabled()) { - log.debug("overallRange " + overallRange + " topKey " + this.root.getTopKey() + " contains " + overallRange.contains(this.root.getTopKey())); - } - - if (overallRange.contains(this.root.getTopKey()) && this.root.isValid()) { - setTopKey(this.root.getTopKey()); - } else { - setTopKey(null); - return; - } - } else { - // seek failed in the logic test, but there may be other possible - // values which satisfy the logic tree. Make sure our iterators aren't - // all null, and then call next. - - // if(!root.hasTop()){ - if (log.isDebugEnabled()) { - log.debug("seek, testTreeState is false, HEAD(root) does not have top"); - } - // check nodes in positives to see if they're all null/outside range - // or if nothing percolated up to root yet. - List removals = new ArrayList(); - for (BooleanLogicTreeNode node : positives) { - if (!node.hasTop() || !overallRange.contains(node.getTopKey())) { - removals.add(node); - } - } - for (BooleanLogicTreeNode node : removals) { - positives.remove(node); - } - next(); - return; - } - } - - private int compare(Key k1, Key k2) { - if (k1 != null && k2 != null) { - return k1.compareTo(k2); - } else if (k1 == null && k2 == null) { - return 0; - } else if (k1 == null) { // in this case, null is considered bigger b/c it's closer to the end of the table. - return 1; - } else { - return -1; - } - } - - private void setupRangerators(Range range) throws IOException { - if (rangerators == null || rangerators.isEmpty()) { - return; - } - for (BooleanLogicTreeNode node : rangerators) { - Set fValues = new HashSet(); - OrIterator orIter = new OrIterator(); - SortedKeyValueIterator siter = sourceIterator.deepCopy(env); - // create UniqFieldNameValueIterator to find uniq field names values - UniqFieldNameValueIterator uniq = new UniqFieldNameValueIterator(node.getFieldName(), node.getLowerBound(), node.getUpperBound()); - uniq.setSource(siter); - uniq.seek(range, EMPTY_COL_FAMS, false); - while (uniq.hasTop()) { - // log.debug("uniq.top: "+uniq.getTopKey()); - Key k = uniq.getTopKey(); - keyParser.parse(k); - String val = keyParser.getFieldValue(); - if (!fValues.contains(val)) { - fValues.add(val); - orIter.addTerm(siter, node.getFieldName(), new Text(val), env); - if (log.isDebugEnabled()) { - log.debug("setupRangerators, adding to OR: " + node.getFieldName() + ":" + val); - } - } else { - log.debug("already have this one: " + val); - } - uniq.next(); - } - node.setUserObject(orIter); - } - - } - - /* ************************************************************************* - * Inner classes - */ - public class BooleanLogicTreeNodeComparator implements Comparator { - - public int compare(Object o1, Object o2) { - BooleanLogicTreeNode n1 = (BooleanLogicTreeNode) o1; - BooleanLogicTreeNode n2 = (BooleanLogicTreeNode) o2; - - Key k1 = n1.getTopKey(); - Key k2 = n2.getTopKey(); - if (log.isDebugEnabled()) { - String t1 = "null"; - String t2 = "null"; - if (k1 != null) { - t1 = k1.getRow().toString() + "\0" + k1.getColumnFamily().toString(); - } - if (k2 != null) { - t2 = k2.getRow().toString() + "\0" + k2.getColumnFamily().toString(); - } - log.debug("BooleanLogicTreeNodeComparator \tt1: " + t1 + " t2: " + t2); - } - // return t1.compareTo(t2); - - if (k1 != null && k2 != null) { - return k1.compareTo(k2); - } else if (k1 == null && k2 == null) { - return 0; - } else if (k1 == null) { - return 1; - } else { - return -1; - } - - } - } - - public IteratorOptions describeOptions() { - return new IteratorOptions(getClass().getSimpleName(), "evaluates event objects against an expression", Collections.singletonMap(QUERY_OPTION, - "query expression"), null); - } - - public boolean validateOptions(Map options) { - if (!options.containsKey(QUERY_OPTION)) { - return false; - } - if (!options.containsKey(FIELD_INDEX_QUERY)) { - return false; - } - this.updatedQuery = options.get(FIELD_INDEX_QUERY); - return true; - } -}