http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/92ddfa59/extras/indexing/src/main/java/mvm/rya/indexing/accumulo/freetext/iterators/AndingIterator.java ---------------------------------------------------------------------- diff --git a/extras/indexing/src/main/java/mvm/rya/indexing/accumulo/freetext/iterators/AndingIterator.java b/extras/indexing/src/main/java/mvm/rya/indexing/accumulo/freetext/iterators/AndingIterator.java new file mode 100644 index 0000000..3bf4086 --- /dev/null +++ b/extras/indexing/src/main/java/mvm/rya/indexing/accumulo/freetext/iterators/AndingIterator.java @@ -0,0 +1,562 @@ +package mvm.rya.indexing.accumulo.freetext.iterators; + +/* + * #%L + * mvm.rya.indexing.accumulo + * %% + * Copyright (C) 2014 Rya + * %% + * 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. + * #L% + */ + +import java.io.IOException; +import java.util.Collection; +import java.util.Collections; +import java.util.Map; + +import org.apache.accumulo.core.client.IteratorSetting; +import org.apache.accumulo.core.data.ArrayByteSequence; +import org.apache.accumulo.core.data.ByteSequence; +import org.apache.accumulo.core.data.Key; +import org.apache.accumulo.core.data.PartialKey; +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.SortedKeyValueIterator; +import org.apache.accumulo.core.iterators.user.IntersectingIterator; +import org.apache.accumulo.core.util.TextUtil; +import org.apache.commons.codec.binary.Base64; +import org.apache.hadoop.io.Text; +import org.apache.log4j.Logger; + +/** + * Adapted from {@link IntersectingIterator} with very slight modifications. Specifically, the comparator on the TermSource internal class was + * modified to handle exhausted iterators and multiple rows per tablet server. + */ +public class AndingIterator implements SortedKeyValueIterator<Key, Value> { + + protected Text nullText = new Text(); + + protected Text getPartition(Key key) { + return key.getRow(); + } + + protected Text getTerm(Key key) { + return key.getColumnFamily(); + } + + protected Text getDocID(Key key) { + return key.getColumnQualifier(); + } + + protected Key buildKey(Text partition, Text term) { + return new Key(partition, (term == null) ? nullText : term); + } + + protected Key buildKey(Text partition, Text term, Text docID) { + return new Key(partition, (term == null) ? nullText : term, docID); + } + + protected Key buildFollowingPartitionKey(Key key) { + return key.followingKey(PartialKey.ROW); + } + + protected static final Logger log = Logger.getLogger(AndingIterator.class); + + protected static class TermSource { + public SortedKeyValueIterator<Key, Value> iter; + public Text term; + public Collection<ByteSequence> seekColfams; + public boolean notFlag; + + public TermSource(TermSource other) { + this.iter = other.iter; + this.term = other.term; + this.notFlag = other.notFlag; + this.seekColfams = other.seekColfams; + } + + public TermSource(SortedKeyValueIterator<Key, Value> iter, Text term) { + this(iter, term, false); + } + + public TermSource(SortedKeyValueIterator<Key, Value> iter, Text term, boolean notFlag) { + this.iter = iter; + this.term = term; + this.notFlag = notFlag; + // The desired column families for this source is the term itself + + // handle the case where the term is null. + if (term == null) { + this.seekColfams = Collections.<ByteSequence> emptyList(); + } else { + this.seekColfams = Collections.<ByteSequence> singletonList(new ArrayByteSequence(term.getBytes(), 0, term.getLength())); + } + } + + public String getTermString() { + return (this.term == null) ? new String("Iterator") : this.term.toString(); + } + } + + TermSource[] sources; + int sourcesCount = 0; + + Range overallRange; + + // query-time settings + protected Text currentPartition = null; + protected Text currentDocID = new Text(emptyByteArray); + static final byte[] emptyByteArray = new byte[0]; + + protected Key topKey = null; + protected Value value = new Value(emptyByteArray); + + public AndingIterator() { + } + + @Override + public SortedKeyValueIterator<Key, Value> deepCopy(IteratorEnvironment env) { + return new AndingIterator(this, env); + } + + private AndingIterator(AndingIterator other, IteratorEnvironment env) { + if (other.sources != null) { + sourcesCount = other.sourcesCount; + sources = new TermSource[sourcesCount]; + for (int i = 0; i < sourcesCount; i++) { + sources[i] = new TermSource(other.sources[i].iter.deepCopy(env), other.sources[i].term); + } + } + } + + @Override + public Key getTopKey() { + return topKey; + } + + @Override + public Value getTopValue() { + // we don't really care about values + return value; + } + + @Override + public boolean hasTop() { + return currentPartition != null; + } + + // precondition: currentRow is not null + private boolean seekOneSource(int sourceID) throws IOException { + // find the next key in the appropriate column family that is at or beyond the cursor (currentRow, currentCQ) + // advance the cursor if this source goes beyond it + // return whether we advanced the cursor + + // within this loop progress must be made in one of the following forms: + // - currentRow or currentCQ must be increased + // - the given source must advance its iterator + // this loop will end when any of the following criteria are met + // - the iterator for the given source is pointing to the key (currentRow, columnFamilies[sourceID], currentCQ) + // - the given source is out of data and currentRow is set to null + // - the given source has advanced beyond the endRow and currentRow is set to null + boolean advancedCursor = false; + + if (sources[sourceID].notFlag) { + while (true) { + if (sources[sourceID].iter.hasTop() == false) { + // an empty column that you are negating is a valid condition + break; + } + // check if we're past the end key + int endCompare = -1; + // we should compare the row to the end of the range + if (overallRange.getEndKey() != null) { + endCompare = overallRange.getEndKey().getRow().compareTo(sources[sourceID].iter.getTopKey().getRow()); + if ((!overallRange.isEndKeyInclusive() && endCompare <= 0) || endCompare < 0) { + // an empty column that you are negating is a valid condition + break; + } + } + int partitionCompare = currentPartition.compareTo(getPartition(sources[sourceID].iter.getTopKey())); + // check if this source is already at or beyond currentRow + // if not, then seek to at least the current row + + if (partitionCompare > 0) { + // seek to at least the currentRow + Key seekKey = buildKey(currentPartition, sources[sourceID].term); + sources[sourceID].iter.seek(new Range(seekKey, true, null, false), sources[sourceID].seekColfams, true); + continue; + } + // check if this source has gone beyond currentRow + // if so, this is a valid condition for negation + if (partitionCompare < 0) { + break; + } + // we have verified that the current source is positioned in currentRow + // now we must make sure we're in the right columnFamily in the current row + // Note: Iterators are auto-magically set to the correct columnFamily + if (sources[sourceID].term != null) { + int termCompare = sources[sourceID].term.compareTo(getTerm(sources[sourceID].iter.getTopKey())); + // check if this source is already on the right columnFamily + // if not, then seek forwards to the right columnFamily + if (termCompare > 0) { + Key seekKey = buildKey(currentPartition, sources[sourceID].term, currentDocID); + sources[sourceID].iter.seek(new Range(seekKey, true, null, false), sources[sourceID].seekColfams, true); + continue; + } + // check if this source is beyond the right columnFamily + // if so, then this is a valid condition for negating + if (termCompare < 0) { + break; + } + } + + // we have verified that we are in currentRow and the correct column family + // make sure we are at or beyond columnQualifier + Text docID = getDocID(sources[sourceID].iter.getTopKey()); + int docIDCompare = currentDocID.compareTo(docID); + // If we are past the target, this is a valid result + if (docIDCompare < 0) { + break; + } + // if this source is not yet at the currentCQ then advance in this source + if (docIDCompare > 0) { + // seek forwards + Key seekKey = buildKey(currentPartition, sources[sourceID].term, currentDocID); + sources[sourceID].iter.seek(new Range(seekKey, true, null, false), sources[sourceID].seekColfams, true); + continue; + } + // if we are equal to the target, this is an invalid result. + // Force the entire process to go to the next row. + // We are advancing column 0 because we forced that column to not contain a ! + // when we did the init() + if (docIDCompare == 0) { + sources[0].iter.next(); + advancedCursor = true; + break; + } + } + } else { + while (true) { + if (sources[sourceID].iter.hasTop() == false) { + currentPartition = null; + // setting currentRow to null counts as advancing the cursor + return true; + } + // check if we're past the end key + int endCompare = -1; + // we should compare the row to the end of the range + + if (overallRange.getEndKey() != null) { + endCompare = overallRange.getEndKey().getRow().compareTo(sources[sourceID].iter.getTopKey().getRow()); + if ((!overallRange.isEndKeyInclusive() && endCompare <= 0) || endCompare < 0) { + currentPartition = null; + // setting currentRow to null counts as advancing the cursor + return true; + } + } + int partitionCompare = currentPartition.compareTo(getPartition(sources[sourceID].iter.getTopKey())); + // check if this source is already at or beyond currentRow + // if not, then seek to at least the current row + if (partitionCompare > 0) { + // seek to at least the currentRow + Key seekKey = buildKey(currentPartition, sources[sourceID].term); + sources[sourceID].iter.seek(new Range(seekKey, true, null, false), sources[sourceID].seekColfams, true); + continue; + } + // check if this source has gone beyond currentRow + // if so, advance currentRow + if (partitionCompare < 0) { + currentPartition.set(getPartition(sources[sourceID].iter.getTopKey())); + currentDocID.set(emptyByteArray); + advancedCursor = true; + continue; + } + // we have verified that the current source is positioned in currentRow + // now we must make sure we're in the right columnFamily in the current row + // Note: Iterators are auto-magically set to the correct columnFamily + + if (sources[sourceID].term != null) { + int termCompare = sources[sourceID].term.compareTo(getTerm(sources[sourceID].iter.getTopKey())); + // check if this source is already on the right columnFamily + // if not, then seek forwards to the right columnFamily + if (termCompare > 0) { + Key seekKey = buildKey(currentPartition, sources[sourceID].term, currentDocID); + sources[sourceID].iter.seek(new Range(seekKey, true, null, false), sources[sourceID].seekColfams, true); + continue; + } + // check if this source is beyond the right columnFamily + // if so, then seek to the next row + if (termCompare < 0) { + // we're out of entries in the current row, so seek to the next one + // byte[] currentRowBytes = currentRow.getBytes(); + // byte[] nextRow = new byte[currentRowBytes.length + 1]; + // System.arraycopy(currentRowBytes, 0, nextRow, 0, currentRowBytes.length); + // nextRow[currentRowBytes.length] = (byte)0; + // // we should reuse text objects here + // sources[sourceID].seek(new Key(new Text(nextRow),columnFamilies[sourceID])); + if (endCompare == 0) { + // we're done + currentPartition = null; + // setting currentRow to null counts as advancing the cursor + return true; + } + Key seekKey = buildFollowingPartitionKey(sources[sourceID].iter.getTopKey()); + sources[sourceID].iter.seek(new Range(seekKey, true, null, false), sources[sourceID].seekColfams, true); + continue; + } + } + // we have verified that we are in currentRow and the correct column family + // make sure we are at or beyond columnQualifier + Text docID = getDocID(sources[sourceID].iter.getTopKey()); + int docIDCompare = currentDocID.compareTo(docID); + // if this source has advanced beyond the current column qualifier then advance currentCQ and return true + if (docIDCompare < 0) { + currentDocID.set(docID); + advancedCursor = true; + break; + } + // if this source is not yet at the currentCQ then seek in this source + if (docIDCompare > 0) { + // seek forwards + Key seekKey = buildKey(currentPartition, sources[sourceID].term, currentDocID); + sources[sourceID].iter.seek(new Range(seekKey, true, null, false), sources[sourceID].seekColfams, true); + continue; + } + // this source is at the current row, in its column family, and at currentCQ + break; + } + } + return advancedCursor; + } + + @Override + public void next() throws IOException { + if (currentPartition == null) { + return; + } + // precondition: the current row is set up and the sources all have the same column qualifier + // while we don't have a match, seek in the source with the smallest column qualifier + sources[0].iter.next(); + advanceToIntersection(); + } + + protected void advanceToIntersection() throws IOException { + boolean cursorChanged = true; + while (cursorChanged) { + // seek all of the sources to at least the highest seen column qualifier in the current row + cursorChanged = false; + for (int i = 0; i < sourcesCount; i++) { + if (currentPartition == null) { + topKey = null; + return; + } + if (seekOneSource(i)) { + cursorChanged = true; + break; + } + } + } + topKey = buildKey(currentPartition, nullText, currentDocID); + } + + public static String stringTopKey(SortedKeyValueIterator<Key, Value> iter) { + if (iter.hasTop()) + return iter.getTopKey().toString(); + return ""; + } + + private static final String columnFamiliesOptionName = "columnFamilies"; + private static final String notFlagOptionName = "notFlag"; + + /** + * @param columns + * @return encoded columns + * @deprecated since 1.4. To be made protected. Do not interact with flags string directly, just use + * {@link #setColumnFamilies(IteratorSetting, Text[], boolean[])}. + */ + public static String encodeColumns(Text[] columns) { + StringBuilder sb = new StringBuilder(); + for (int i = 0; i < columns.length; i++) { + sb.append(new String(Base64.encodeBase64(TextUtil.getBytes(columns[i])))); + sb.append('\n'); + } + return sb.toString(); + } + + /** + * @param flags + * @return encoded flags + * @deprecated since 1.4. To be made protected. Do not interact with flags string directly, just use + * {@link #setColumnFamilies(IteratorSetting, Text[], boolean[])}. + */ + public static String encodeBooleans(boolean[] flags) { + byte[] bytes = new byte[flags.length]; + for (int i = 0; i < flags.length; i++) { + if (flags[i]) + bytes[i] = 1; + else + bytes[i] = 0; + } + return new String(Base64.encodeBase64(bytes)); + } + + protected static Text[] decodeColumns(String columns) { + String[] columnStrings = columns.split("\n"); + Text[] columnTexts = new Text[columnStrings.length]; + for (int i = 0; i < columnStrings.length; i++) { + columnTexts[i] = new Text(Base64.decodeBase64(columnStrings[i].getBytes())); + } + return columnTexts; + } + + /** + * to be made protected + * + * @param flags + * @return decoded flags + * @deprecated since 1.4. To be made protected. Do not interact with flags string directly, just use + * {@link #setColumnFamilies(IteratorSetting, Text[], boolean[])}. + */ + public static boolean[] decodeBooleans(String flags) { + // return null of there were no flags + if (flags == null) + return null; + + byte[] bytes = Base64.decodeBase64(flags.getBytes()); + boolean[] bFlags = new boolean[bytes.length]; + for (int i = 0; i < bytes.length; i++) { + if (bytes[i] == 1) + bFlags[i] = true; + else + bFlags[i] = false; + } + return bFlags; + } + + @Override + public void init(SortedKeyValueIterator<Key, Value> source, Map<String, String> options, IteratorEnvironment env) throws IOException { + Text[] terms = decodeColumns(options.get(columnFamiliesOptionName)); + boolean[] notFlag = decodeBooleans(options.get(notFlagOptionName)); + + if (terms.length < 2) { + throw new IllegalArgumentException("IntersectionIterator requires two or more columns families"); + } + + // Scan the not flags. + // There must be at least one term that isn't negated + // And we are going to re-order such that the first term is not a ! term + if (notFlag == null) { + notFlag = new boolean[terms.length]; + for (int i = 0; i < terms.length; i++) + notFlag[i] = false; + } + if (notFlag[0]) { + for (int i = 1; i < notFlag.length; i++) { + if (notFlag[i] == false) { + Text swapFamily = new Text(terms[0]); + terms[0].set(terms[i]); + terms[i].set(swapFamily); + notFlag[0] = false; + notFlag[i] = true; + break; + } + } + if (notFlag[0]) { + throw new IllegalArgumentException("IntersectionIterator requires at lest one column family without not"); + } + } + + sources = new TermSource[terms.length]; + sources[0] = new TermSource(source, terms[0]); + for (int i = 1; i < terms.length; i++) { + sources[i] = new TermSource(source.deepCopy(env), terms[i], notFlag[i]); + } + sourcesCount = terms.length; + } + + @Override + public void seek(Range range, Collection<ByteSequence> seekColumnFamilies, boolean inclusive) throws IOException { + overallRange = new Range(range); + currentPartition = new Text(); + currentDocID.set(emptyByteArray); + + // seek each of the sources to the right column family within the row given by key + for (int i = 0; i < sourcesCount; i++) { + Key sourceKey; + if (range.getStartKey() != null) { + if (range.getStartKey().getColumnQualifier() != null) { + sourceKey = buildKey(getPartition(range.getStartKey()), sources[i].term, range.getStartKey().getColumnQualifier()); + } else { + sourceKey = buildKey(getPartition(range.getStartKey()), sources[i].term); + } + // Seek only to the term for this source as a column family + sources[i].iter.seek(new Range(sourceKey, true, null, false), sources[i].seekColfams, true); + } else { + // Seek only to the term for this source as a column family + sources[i].iter.seek(range, sources[i].seekColfams, true); + } + } + advanceToIntersection(); + } + + public void addSource(SortedKeyValueIterator<Key, Value> source, IteratorEnvironment env, Text term, boolean notFlag) { + // Check if we have space for the added Source + if (sources == null) { + sources = new TermSource[1]; + } else { + // allocate space for node, and copy current tree. + // TODO: Should we change this to an ArrayList so that we can just add() ? + TermSource[] localSources = new TermSource[sources.length + 1]; + int currSource = 0; + for (TermSource myTerm : sources) { + // TODO: Do I need to call new here? or can I just re-use the term? + localSources[currSource] = new TermSource(myTerm); + currSource++; + } + sources = localSources; + } + sources[sourcesCount] = new TermSource(source.deepCopy(env), term, notFlag); + sourcesCount++; + } + + /** + * Encode the columns to be used when iterating. + * + * @param cfg + * @param columns + */ + public static void setColumnFamilies(IteratorSetting cfg, Text[] columns) { + if (columns.length < 2) + throw new IllegalArgumentException("Must supply at least two terms to intersect"); + cfg.addOption(AndingIterator.columnFamiliesOptionName, AndingIterator.encodeColumns(columns)); + } + + /** + * Encode columns and NOT flags indicating which columns should be negated (docIDs will be excluded if matching negated columns, instead + * of included). + * + * @param cfg + * @param columns + * @param notFlags + */ + public static void setColumnFamilies(IteratorSetting cfg, Text[] columns, boolean[] notFlags) { + if (columns.length < 2) + throw new IllegalArgumentException("Must supply at least two terms to intersect"); + if (columns.length != notFlags.length) + throw new IllegalArgumentException("columns and notFlags arrays must be the same length"); + setColumnFamilies(cfg, columns); + cfg.addOption(AndingIterator.notFlagOptionName, AndingIterator.encodeBooleans(notFlags)); + } +}
http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/92ddfa59/extras/indexing/src/main/java/mvm/rya/indexing/accumulo/freetext/iterators/BooleanTreeIterator.java ---------------------------------------------------------------------- diff --git a/extras/indexing/src/main/java/mvm/rya/indexing/accumulo/freetext/iterators/BooleanTreeIterator.java b/extras/indexing/src/main/java/mvm/rya/indexing/accumulo/freetext/iterators/BooleanTreeIterator.java new file mode 100644 index 0000000..7f73b13 --- /dev/null +++ b/extras/indexing/src/main/java/mvm/rya/indexing/accumulo/freetext/iterators/BooleanTreeIterator.java @@ -0,0 +1,321 @@ +package mvm.rya.indexing.accumulo.freetext.iterators; + +/* + * #%L + * mvm.rya.indexing.accumulo + * %% + * Copyright (C) 2014 Rya + * %% + * 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. + * #L% + */ + +import static mvm.rya.indexing.accumulo.freetext.query.ASTNodeUtils.allChildrenAreNot; +import static mvm.rya.indexing.accumulo.freetext.query.ASTNodeUtils.findFirstNonNotChild; +import static mvm.rya.indexing.accumulo.freetext.query.ASTNodeUtils.getNodeIterator; +import static mvm.rya.indexing.accumulo.freetext.query.ASTNodeUtils.isNotFlag; +import static mvm.rya.indexing.accumulo.freetext.query.ASTNodeUtils.pushChild; +import static mvm.rya.indexing.accumulo.freetext.query.ASTNodeUtils.swapChildren; + +import java.io.IOException; +import java.util.ArrayList; +import java.util.Collection; +import java.util.Collections; +import java.util.List; +import java.util.Map; +import java.util.NoSuchElementException; + +import mvm.rya.indexing.accumulo.freetext.ColumnPrefixes; +import mvm.rya.indexing.accumulo.freetext.query.ASTExpression; +import mvm.rya.indexing.accumulo.freetext.query.ASTTerm; +import mvm.rya.indexing.accumulo.freetext.query.ParseException; +import mvm.rya.indexing.accumulo.freetext.query.QueryParser; +import mvm.rya.indexing.accumulo.freetext.query.QueryParserTreeConstants; +import mvm.rya.indexing.accumulo.freetext.query.SimpleNode; +import mvm.rya.indexing.accumulo.freetext.query.TokenMgrError; + +import org.apache.accumulo.core.client.IteratorSetting; +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.core.iterators.system.MultiIterator; +import org.apache.commons.lang.Validate; +import org.apache.hadoop.io.Text; +import org.apache.log4j.Logger; + +public class BooleanTreeIterator implements SortedKeyValueIterator<Key, Value>, OptionDescriber { + private static Logger logger = Logger.getLogger(BooleanTreeIterator.class); + + private static String queryOptionName = "query"; + + private SortedKeyValueIterator<Key, Value> iter; + private SortedKeyValueIterator<Key, Value> docSource; + + @Override + public void init(SortedKeyValueIterator<Key, Value> source, Map<String, String> options, IteratorEnvironment env) throws IOException { + + // pull out the query + String query = options.get(queryOptionName); + + // create the parse tree + SimpleNode root; + try { + root = QueryParser.parse(query); + } catch (ParseException e) { + // log and wrap in IOException + logger.error("ParseException encountered while parsing: " + query, e); + throw new IOException(e); + } catch (TokenMgrError e) { + // log and wrap in IOException + logger.error("TokenMgrError encountered while parsing: " + query, e); + throw new IOException(e); + } + + docSource = source.deepCopy(env); + iter = createIterator((SimpleNode) root.jjtGetChild(0), source, env); + } + + private SortedKeyValueIterator<Key, Value> createIterator(SimpleNode root, SortedKeyValueIterator<Key, Value> source, + IteratorEnvironment env) { + // if the root is only a single term, wrap it in an expression node + if (root instanceof ASTTerm) { + ASTExpression expression = new ASTExpression(QueryParserTreeConstants.JJTEXPRESSION); + expression.setNotFlag(false); + expression.setType(ASTExpression.AND); + + pushChild(expression, root); + root.jjtSetParent(expression); + + root = expression; + } + + // Pre-process the tree to compensate for iterator specific issues with certain topologies + preProcessTree(root); + + // Build an iterator tree + return createIteratorRecursive(root, source, env); + } + + private SortedKeyValueIterator<Key, Value> createIteratorRecursive(SimpleNode node, SortedKeyValueIterator<Key, Value> source, + IteratorEnvironment env) { + + Validate.isTrue(node instanceof ASTExpression, "node must be of type ASTExpression. Node is instance of " + + node.getClass().getName()); + + ASTExpression expression = (ASTExpression) node; + + if (expression.getType().equals(ASTExpression.AND)) { + return getAndIterator(node, source, env); + } + + if (expression.getType().equals(ASTExpression.OR)) { + return getOrIterator(node, source, env); + } + + throw new IllegalArgumentException("Expression is of unknown type: " + expression.getType()); + + } + + private MultiIterator getOrIterator(SimpleNode node, SortedKeyValueIterator<Key, Value> source, IteratorEnvironment env) { + List<SortedKeyValueIterator<Key, Value>> iters = new ArrayList<SortedKeyValueIterator<Key, Value>>(); + + for (SimpleNode n : getNodeIterator(node)) { + if (n instanceof ASTExpression) { + iters.add(createIteratorRecursive(n, source, env)); + } else if (n instanceof ASTTerm) { + iters.add(getSimpleAndingIterator((ASTTerm) n, source, env)); + } else { + throw new IllegalArgumentException("Node is of unknown type: " + n.getClass().getName()); + } + } + + return new MultiIterator(iters, new Range()); + } + + private AndingIterator getAndIterator(SimpleNode node, SortedKeyValueIterator<Key, Value> source, IteratorEnvironment env) { + + AndingIterator anding = new AndingIterator(); + + for (SimpleNode n : getNodeIterator(node)) { + boolean isNotFlag = isNotFlag(n); + if (n instanceof ASTExpression) { + anding.addSource(createIteratorRecursive(n, source, env), env, null, isNotFlag); + } else if (n instanceof ASTTerm) { + ASTTerm term = ((ASTTerm) n); + anding.addSource(source, env, getTermColFam(term), isNotFlag); + } else { + throw new IllegalArgumentException("Node is of unknown type: " + n.getClass().getName()); + } + } + + return anding; + } + + private static Text getTermColFam(ASTTerm termnode) { + String term = termnode.getTerm(); + if (term == null) { + // if the term is null, then I want all of the documents + return ColumnPrefixes.DOCS_CF_PREFIX; + } + if (term.contains("\0")) { + // if the term is contain a null char, then it's already formated for a CF + return new Text(term); + } + + // otherwise, point to the term CF + return ColumnPrefixes.getTermColFam(term.toLowerCase()); + } + + private AndingIterator getSimpleAndingIterator(ASTTerm node, SortedKeyValueIterator<Key, Value> source, IteratorEnvironment env) { + Validate.isTrue(!node.isNotFlag(), "Simple Anding node must not have \"not\" flag set"); + + AndingIterator anding = new AndingIterator(); + anding.addSource(source, env, getTermColFam(node), false); + return anding; + } + + /** + * Handle "lonely nots" (i.e. expressions with only nots), "or" statements containing nots, and make sure that the first term in an + * "and" statement is not a not. This is due to implementation specific limitations of the iterators. + * <p> + * For example: + * <ul> + * <li>lonely nots: (!a & !b) -> [all] & !a & !b</li> + * <li>"or" nots: (!a | b) -> ( ([all] & !a) | b)</li> + * <li>reorder "and" nots: (!a & b) -> ( b & !a )</li> + * </ul> + **/ + public static void preProcessTree(SimpleNode s) { + for (SimpleNode child : getNodeIterator(s)) { + preProcessTree(child); + } + + if (s instanceof ASTExpression) { + ASTExpression expression = (ASTExpression) s; + + if (expression.getType().equals(ASTExpression.AND)) { + if (allChildrenAreNot(expression)) { + // lonely nots: (!a & !b) -> [all] & !a & !b + ASTTerm allDocsTerm = createAllDocTermNode(); + pushChild(expression, allDocsTerm); + } else if (isNotFlag(expression.jjtGetChild(0))) { + // reorder "and" nots: (!a & b) -> ( b & !a ) + int firstNonNotChild = findFirstNonNotChild(expression); + swapChildren(expression, 0, firstNonNotChild); + } + } + + if (expression.getType().equals(ASTExpression.OR)) { + for (int i = 0; i < expression.jjtGetNumChildren(); i++) { + SimpleNode child = (SimpleNode) expression.jjtGetChild(i); + if (isNotFlag(child)) { + // "or" nots: (!a | b) -> ( ([all] & !a) | b) + // create the new expression + ASTExpression newExpression = new ASTExpression(QueryParserTreeConstants.JJTEXPRESSION); + newExpression.setNotFlag(false); + newExpression.setType(ASTExpression.AND); + pushChild(newExpression, child); + pushChild(newExpression, createAllDocTermNode()); + + // tie the new expression to the old one + newExpression.jjtSetParent(expression); + expression.jjtAddChild(newExpression, i); + } + } + } + } + + } + + public static ASTTerm createAllDocTermNode() { + ASTTerm t = new ASTTerm(QueryParserTreeConstants.JJTTERM); + t.setNotFlag(false); + t.setType(ASTTerm.TERM); + // note: a "null" signifies "all docs" should be returned. + t.setTerm(null); + return t; + } + + @Override + public boolean hasTop() { + return iter.hasTop(); + } + + @Override + public void next() throws IOException { + iter.next(); + if (iter.hasTop()) { + seekDocSource(iter.getTopKey()); + } + } + + @Override + public void seek(Range range, Collection<ByteSequence> columnFamilies, boolean inclusive) throws IOException { + iter.seek(range, columnFamilies, inclusive); + if (iter.hasTop()) { + seekDocSource(iter.getTopKey()); + } + } + + private void seekDocSource(Key key) throws IOException { + Key docKey = new Key(key.getRow(), ColumnPrefixes.DOCS_CF_PREFIX, key.getColumnQualifier()); + docSource.seek(new Range(docKey, true, null, false), Collections.<ByteSequence> emptyList(), false); + } + + @Override + public Key getTopKey() { + // from intersecting iterator: + // RowID: shardID + // CF: (empty) + // CQ: docID + return iter.getTopKey(); + } + + @Override + public Value getTopValue() { + if (!iter.hasTop()) { + throw new NoSuchElementException(); + } + + return docSource.getTopValue(); + } + + @Override + public SortedKeyValueIterator<Key, Value> deepCopy(IteratorEnvironment env) { + throw new UnsupportedOperationException(); + } + + public static void setQuery(IteratorSetting cfg, String query) { + cfg.addOption(BooleanTreeIterator.queryOptionName, query); + } + + @Override + public IteratorOptions describeOptions() { + return new IteratorOptions("FreeTextBooleanTree", "Perform a FreeText Query on properly formated table", + Collections.singletonMap(queryOptionName, "the free text query"), + null); + } + + @Override + public boolean validateOptions(Map<String, String> options) { + String q = options.get(queryOptionName); + if (q == null || q.isEmpty()) + throw new IllegalArgumentException(queryOptionName + " must not be empty"); + return true; + } + +} http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/92ddfa59/extras/indexing/src/main/java/mvm/rya/indexing/accumulo/freetext/query/ASTExpression.java ---------------------------------------------------------------------- diff --git a/extras/indexing/src/main/java/mvm/rya/indexing/accumulo/freetext/query/ASTExpression.java b/extras/indexing/src/main/java/mvm/rya/indexing/accumulo/freetext/query/ASTExpression.java new file mode 100644 index 0000000..d87f57d --- /dev/null +++ b/extras/indexing/src/main/java/mvm/rya/indexing/accumulo/freetext/query/ASTExpression.java @@ -0,0 +1,62 @@ +package mvm.rya.indexing.accumulo.freetext.query; + +/* + * #%L + * mvm.rya.indexing.accumulo + * %% + * Copyright (C) 2014 Rya + * %% + * 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. + * #L% + */ + +/** + * This is a slightly modified version of the ASTExpression file created by JavaCC. This version adds more state to the standard ASTTerm + * file including a "type", and "notFlag". + */ +public class ASTExpression extends SimpleNode { + public static final String AND = "AND"; + public static final String OR = "OR"; + + private String type = ""; + private boolean notFlag = false; + + public ASTExpression(int id) { + super(id); + } + + public ASTExpression(QueryParser p, int id) { + super(p, id); + } + + public void setType(String type) { + this.type = type; + } + + public String getType() { + return type; + } + + public boolean isNotFlag() { + return notFlag; + } + + public void setNotFlag(boolean notFlag) { + this.notFlag = notFlag; + } + + @Override + public String toString() { + return super.toString() + " [type: " + type + ", notFlag: " + notFlag + "]"; + } +} http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/92ddfa59/extras/indexing/src/main/java/mvm/rya/indexing/accumulo/freetext/query/ASTNodeUtils.java ---------------------------------------------------------------------- diff --git a/extras/indexing/src/main/java/mvm/rya/indexing/accumulo/freetext/query/ASTNodeUtils.java b/extras/indexing/src/main/java/mvm/rya/indexing/accumulo/freetext/query/ASTNodeUtils.java new file mode 100644 index 0000000..d328812 --- /dev/null +++ b/extras/indexing/src/main/java/mvm/rya/indexing/accumulo/freetext/query/ASTNodeUtils.java @@ -0,0 +1,209 @@ +package mvm.rya.indexing.accumulo.freetext.query; + +/* + * #%L + * mvm.rya.indexing.accumulo + * %% + * Copyright (C) 2014 Rya + * %% + * 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. + * #L% + */ + +import java.util.ArrayList; +import java.util.Iterator; +import java.util.List; +import java.util.NoSuchElementException; + +import org.apache.commons.lang.StringUtils; +import org.apache.commons.lang.Validate; + +public class ASTNodeUtils { + + /** + * Serialize a node (and it's children) to a parsable string. + * + * @param s + * @return + */ + public static String serializeExpression(Node s) { + if (s instanceof ASTTerm) { + ASTTerm a = (ASTTerm) s; + return (a.isNotFlag() ? "!" : "") + " " + a.getTerm(); + } + + String prefix = ""; + String suffix = ""; + String join = " "; + if (s instanceof ASTExpression) { + ASTExpression a = (ASTExpression) s; + prefix = (a.isNotFlag() ? "!" : "") + "("; + suffix = ")"; + join = " " + a.getType() + " "; + } + + List<String> children = new ArrayList<String>(); + for (int i = 0; i < s.jjtGetNumChildren(); i++) { + children.add(serializeExpression(s.jjtGetChild(i))); + } + return prefix + StringUtils.join(children, join) + suffix; + + } + + /** + * count the number of terms in this query tree. + * + * @param node + * @return + */ + public static int termCount(Node node) { + if (node instanceof SimpleNode) { + int count = 0; + for (SimpleNode n : getNodeIterator((SimpleNode) node)) { + count += termCount(n); + } + return count; + } else if (node instanceof ASTTerm) { + return 1; + } else { + throw new IllegalArgumentException("Node is of unknown type: " + node.getClass().getName()); + } + } + + /** + * Add the child as the parent's first child. + * + * @param parent + * @param child + */ + public static void pushChild(SimpleNode parent, SimpleNode child) { + // note: this implementation is very coupled with the SimpleNode jjt implementation + int parentSize = parent.jjtGetNumChildren(); + + // expand the parent node + parent.jjtAddChild(null, parentSize); + + // get the current head child + Node currentHeadChild = parent.jjtGetChild(0); + + // set the parameter as the parent's first child + parent.jjtAddChild(child, 0); + + // add the former head child to the end of the list + if (currentHeadChild != null) { + parent.jjtAddChild(currentHeadChild, parentSize); + } + + // tie the child to the parent + child.jjtSetParent(parent); + + } + + /** + * Get the index of the child, -1 if child not found. + * + * @param parent + * @param child + */ + public static int getChildIndex(SimpleNode parent, SimpleNode child) { + int parentSize = parent.jjtGetNumChildren(); + + for (int i = 0; i < parentSize; i++) { + if (child.equals(parent.jjtGetChild(i))) { + return i; + } + } + + return -1; + } + + /** + * return true is all of the node's children have the not flag enabled. + * + * @param node + * @return + */ + public static boolean allChildrenAreNot(ASTExpression node) { + for (SimpleNode child : getNodeIterator(node)) { + if (!isNotFlag(child)) { + return false; + } + } + return true; + } + + /** + * return the node's not flag value. node must be of type {@link ASTTerm} or {@link ASTExpression} + * + * @param node + * @return + */ + public static boolean isNotFlag(Node node) { + if (node instanceof ASTExpression) { + return ((ASTExpression) node).isNotFlag(); + } else if (node instanceof ASTTerm) { + return ((ASTTerm) node).isNotFlag(); + } else { + throw new IllegalArgumentException("Node is of unknown type: " + node.getClass().getName()); + } + } + + public static Iterable<SimpleNode> getNodeIterator(final SimpleNode n) { + return new Iterable<SimpleNode>() { + + @Override + public Iterator<SimpleNode> iterator() { + return new Iterator<SimpleNode>() { + int pointer = 0; + + @Override + public boolean hasNext() { + return pointer < n.jjtGetNumChildren(); + } + + @Override + public SimpleNode next() { + Node rtn = n.jjtGetChild(pointer); + pointer++; + return (SimpleNode) rtn; + } + + @Override + public void remove() { + throw new UnsupportedOperationException(); + } + }; + } + }; + } + + public static void swapChildren(ASTExpression parent, int childOneIndex, int childTwoIndex) { + Validate.isTrue(childOneIndex > -1 && childOneIndex < parent.jjtGetNumChildren()); + Validate.isTrue(childTwoIndex > -1 && childTwoIndex < parent.jjtGetNumChildren()); + + Node childOne = parent.jjtGetChild(childOneIndex); + Node childTwo = parent.jjtGetChild(childTwoIndex); + parent.jjtAddChild(childOne, childTwoIndex); + parent.jjtAddChild(childTwo, childOneIndex); + } + + public static int findFirstNonNotChild(ASTExpression expression) { + for (int i = 0; i < expression.jjtGetNumChildren(); i++) { + if (!isNotFlag(expression.jjtGetChild(i))) { + return i; + } + } + return -1; + } + +} http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/92ddfa59/extras/indexing/src/main/java/mvm/rya/indexing/accumulo/freetext/query/ASTSimpleNode.java ---------------------------------------------------------------------- diff --git a/extras/indexing/src/main/java/mvm/rya/indexing/accumulo/freetext/query/ASTSimpleNode.java b/extras/indexing/src/main/java/mvm/rya/indexing/accumulo/freetext/query/ASTSimpleNode.java new file mode 100644 index 0000000..18e856c --- /dev/null +++ b/extras/indexing/src/main/java/mvm/rya/indexing/accumulo/freetext/query/ASTSimpleNode.java @@ -0,0 +1,36 @@ +/* Generated By:JJTree: Do not edit this line. ASTSimpleNode.java Version 4.3 */ +/* JavaCCOptions:MULTI=true,NODE_USES_PARSER=false,VISITOR=false,TRACK_TOKENS=false,NODE_PREFIX=AST,NODE_EXTENDS=,NODE_FACTORY=,SUPPORT_CLASS_VISIBILITY_PUBLIC=true */ +package mvm.rya.indexing.accumulo.freetext.query; + +/* + * #%L + * mvm.rya.indexing.accumulo + * %% + * Copyright (C) 2014 Rya + * %% + * 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. + * #L% + */ + +public +class ASTSimpleNode extends SimpleNode { + public ASTSimpleNode(int id) { + super(id); + } + + public ASTSimpleNode(QueryParser p, int id) { + super(p, id); + } + +} +/* JavaCC - OriginalChecksum=8a57fc385ee56c7039cbbc4132eb8e0c (do not edit this line) */ http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/92ddfa59/extras/indexing/src/main/java/mvm/rya/indexing/accumulo/freetext/query/ASTTerm.java ---------------------------------------------------------------------- diff --git a/extras/indexing/src/main/java/mvm/rya/indexing/accumulo/freetext/query/ASTTerm.java b/extras/indexing/src/main/java/mvm/rya/indexing/accumulo/freetext/query/ASTTerm.java new file mode 100644 index 0000000..950c873 --- /dev/null +++ b/extras/indexing/src/main/java/mvm/rya/indexing/accumulo/freetext/query/ASTTerm.java @@ -0,0 +1,78 @@ +package mvm.rya.indexing.accumulo.freetext.query; + +/* + * #%L + * mvm.rya.indexing.accumulo + * %% + * Copyright (C) 2014 Rya + * %% + * 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. + * #L% + */ + +/** + * This is a slightly modified version of the ASTTerm file created by JavaCC. This version adds more state to the standard ASTTerm file + * including a "term", "type", and "notFlag". + */ +public class ASTTerm extends SimpleNode { + public static final String WILDTERM = "WILDTERM"; + public static final String PREFIXTERM = "PREFIXTERM"; + public static final String QUOTED = "QUOTED"; + public static final String TERM = "TERM"; + + private String term = ""; + private boolean notFlag = false; + private String type = ""; + + public ASTTerm(int id) { + super(id); + } + + public ASTTerm(QueryParser p, int id) { + super(p, id); + } + + @Override + public String toString() { + return super.toString() + "[notFlag: " + notFlag + " term: " + term + " type: " + type + "]"; + } + + @Override + public String toString(String prefix) { + return super.toString(prefix); + } + + public String getTerm() { + return term; + } + + public void setTerm(String term) { + this.term = term; + } + + public boolean isNotFlag() { + return notFlag; + } + + public void setNotFlag(boolean notFlag) { + this.notFlag = notFlag; + } + + public void setType(String type) { + this.type = type; + } + + public String getType() { + return type; + } +} http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/92ddfa59/extras/indexing/src/main/java/mvm/rya/indexing/accumulo/freetext/query/JJTQueryParserState.java ---------------------------------------------------------------------- diff --git a/extras/indexing/src/main/java/mvm/rya/indexing/accumulo/freetext/query/JJTQueryParserState.java b/extras/indexing/src/main/java/mvm/rya/indexing/accumulo/freetext/query/JJTQueryParserState.java new file mode 100644 index 0000000..e413842 --- /dev/null +++ b/extras/indexing/src/main/java/mvm/rya/indexing/accumulo/freetext/query/JJTQueryParserState.java @@ -0,0 +1,143 @@ +/* Generated By:JavaCC: Do not edit this line. JJTQueryParserState.java Version 5.0 */ +package mvm.rya.indexing.accumulo.freetext.query; + +/* + * #%L + * mvm.rya.indexing.accumulo + * %% + * Copyright (C) 2014 Rya + * %% + * 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. + * #L% + */ + +public class JJTQueryParserState { + private java.util.List<Node> nodes; + private java.util.List<Integer> marks; + + private int sp; // number of nodes on stack + private int mk; // current mark + private boolean node_created; + + public JJTQueryParserState() { + nodes = new java.util.ArrayList<Node>(); + marks = new java.util.ArrayList<Integer>(); + sp = 0; + mk = 0; + } + + /* Determines whether the current node was actually closed and + pushed. This should only be called in the final user action of a + node scope. */ + public boolean nodeCreated() { + return node_created; + } + + /* Call this to reinitialize the node stack. It is called + automatically by the parser's ReInit() method. */ + public void reset() { + nodes.clear(); + marks.clear(); + sp = 0; + mk = 0; + } + + /* Returns the root node of the AST. It only makes sense to call + this after a successful parse. */ + public Node rootNode() { + return nodes.get(0); + } + + /* Pushes a node on to the stack. */ + public void pushNode(Node n) { + nodes.add(n); + ++sp; + } + + /* Returns the node on the top of the stack, and remove it from the + stack. */ + public Node popNode() { + if (--sp < mk) { + mk = marks.remove(marks.size()-1); + } + return nodes.remove(nodes.size()-1); + } + + /* Returns the node currently on the top of the stack. */ + public Node peekNode() { + return nodes.get(nodes.size()-1); + } + + /* Returns the number of children on the stack in the current node + scope. */ + public int nodeArity() { + return sp - mk; + } + + + public void clearNodeScope(Node n) { + while (sp > mk) { + popNode(); + } + mk = marks.remove(marks.size()-1); + } + + + public void openNodeScope(Node n) { + marks.add(mk); + mk = sp; + n.jjtOpen(); + } + + + /* A definite node is constructed from a specified number of + children. That number of nodes are popped from the stack and + made the children of the definite node. Then the definite node + is pushed on to the stack. */ + public void closeNodeScope(Node n, int num) { + mk = marks.remove(marks.size()-1); + while (num-- > 0) { + Node c = popNode(); + c.jjtSetParent(n); + n.jjtAddChild(c, num); + } + n.jjtClose(); + pushNode(n); + node_created = true; + } + + + /* A conditional node is constructed if its condition is true. All + the nodes that have been pushed since the node was opened are + made children of the conditional node, which is then pushed + on to the stack. If the condition is false the node is not + constructed and they are left on the stack. */ + public void closeNodeScope(Node n, boolean condition) { + if (condition) { + int a = nodeArity(); + mk = marks.remove(marks.size()-1); + while (a-- > 0) { + Node c = popNode(); + c.jjtSetParent(n); + n.jjtAddChild(c, a); + } + n.jjtClose(); + pushNode(n); + node_created = true; + } else { + mk = marks.remove(marks.size()-1); + node_created = false; + } + } +} +/* JavaCC - OriginalChecksum=3658fa072c0d78e6abb5a6e2b4509dc4 (do not edit this line) */ http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/92ddfa59/extras/indexing/src/main/java/mvm/rya/indexing/accumulo/freetext/query/Node.java ---------------------------------------------------------------------- diff --git a/extras/indexing/src/main/java/mvm/rya/indexing/accumulo/freetext/query/Node.java b/extras/indexing/src/main/java/mvm/rya/indexing/accumulo/freetext/query/Node.java new file mode 100644 index 0000000..13d1649 --- /dev/null +++ b/extras/indexing/src/main/java/mvm/rya/indexing/accumulo/freetext/query/Node.java @@ -0,0 +1,56 @@ +/* Generated By:JJTree: Do not edit this line. Node.java Version 4.3 */ +/* JavaCCOptions:MULTI=true,NODE_USES_PARSER=false,VISITOR=false,TRACK_TOKENS=false,NODE_PREFIX=AST,NODE_EXTENDS=,NODE_FACTORY=,SUPPORT_CLASS_VISIBILITY_PUBLIC=true */ +package mvm.rya.indexing.accumulo.freetext.query; + +/* + * #%L + * mvm.rya.indexing.accumulo + * %% + * Copyright (C) 2014 Rya + * %% + * 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. + * #L% + */ + +/* All AST nodes must implement this interface. It provides basic + machinery for constructing the parent and child relationships + between nodes. */ + +public +interface Node { + + /** This method is called after the node has been made the current + node. It indicates that child nodes can now be added to it. */ + public void jjtOpen(); + + /** This method is called after all the child nodes have been + added. */ + public void jjtClose(); + + /** This pair of methods are used to inform the node of its + parent. */ + public void jjtSetParent(Node n); + public Node jjtGetParent(); + + /** This method tells the node to add its argument to the node's + list of children. */ + public void jjtAddChild(Node n, int i); + + /** This method returns a child node. The children are numbered + from zero, left to right. */ + public Node jjtGetChild(int i); + + /** Return the number of children the node has. */ + public int jjtGetNumChildren(); +} +/* JavaCC - OriginalChecksum=e66efa9c359bf70af0cdb4f33bea0630 (do not edit this line) */ http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/92ddfa59/extras/indexing/src/main/java/mvm/rya/indexing/accumulo/freetext/query/ParseException.java ---------------------------------------------------------------------- diff --git a/extras/indexing/src/main/java/mvm/rya/indexing/accumulo/freetext/query/ParseException.java b/extras/indexing/src/main/java/mvm/rya/indexing/accumulo/freetext/query/ParseException.java new file mode 100644 index 0000000..7adf9ba --- /dev/null +++ b/extras/indexing/src/main/java/mvm/rya/indexing/accumulo/freetext/query/ParseException.java @@ -0,0 +1,207 @@ +/* Generated By:JavaCC: Do not edit this line. ParseException.java Version 5.0 */ +/* JavaCCOptions:KEEP_LINE_COL=null */ +package mvm.rya.indexing.accumulo.freetext.query; + +/* + * #%L + * mvm.rya.indexing.accumulo + * %% + * Copyright (C) 2014 Rya + * %% + * 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. + * #L% + */ + +/** + * This exception is thrown when parse errors are encountered. + * You can explicitly create objects of this exception type by + * calling the method generateParseException in the generated + * parser. + * + * You can modify this class to customize your error reporting + * mechanisms so long as you retain the public fields. + */ +public class ParseException extends Exception { + + /** + * The version identifier for this Serializable class. + * Increment only if the <i>serialized</i> form of the + * class changes. + */ + private static final long serialVersionUID = 1L; + + /** + * This constructor is used by the method "generateParseException" + * in the generated parser. Calling this constructor generates + * a new object of this type with the fields "currentToken", + * "expectedTokenSequences", and "tokenImage" set. + */ + public ParseException(Token currentTokenVal, + int[][] expectedTokenSequencesVal, + String[] tokenImageVal + ) + { + super(initialise(currentTokenVal, expectedTokenSequencesVal, tokenImageVal)); + currentToken = currentTokenVal; + expectedTokenSequences = expectedTokenSequencesVal; + tokenImage = tokenImageVal; + } + + /** + * The following constructors are for use by you for whatever + * purpose you can think of. Constructing the exception in this + * manner makes the exception behave in the normal way - i.e., as + * documented in the class "Throwable". The fields "errorToken", + * "expectedTokenSequences", and "tokenImage" do not contain + * relevant information. The JavaCC generated code does not use + * these constructors. + */ + + public ParseException() { + super(); + } + + /** Constructor with message. */ + public ParseException(String message) { + super(message); + } + + + /** + * This is the last token that has been consumed successfully. If + * this object has been created due to a parse error, the token + * followng this token will (therefore) be the first error token. + */ + public Token currentToken; + + /** + * Each entry in this array is an array of integers. Each array + * of integers represents a sequence of tokens (by their ordinal + * values) that is expected at this point of the parse. + */ + public int[][] expectedTokenSequences; + + /** + * This is a reference to the "tokenImage" array of the generated + * parser within which the parse error occurred. This array is + * defined in the generated ...Constants interface. + */ + public String[] tokenImage; + + /** + * It uses "currentToken" and "expectedTokenSequences" to generate a parse + * error message and returns it. If this object has been created + * due to a parse error, and you do not catch it (it gets thrown + * from the parser) the correct error message + * gets displayed. + */ + private static String initialise(Token currentToken, + int[][] expectedTokenSequences, + String[] tokenImage) { + String eol = System.getProperty("line.separator", "\n"); + StringBuffer expected = new StringBuffer(); + int maxSize = 0; + for (int i = 0; i < expectedTokenSequences.length; i++) { + if (maxSize < expectedTokenSequences[i].length) { + maxSize = expectedTokenSequences[i].length; + } + for (int j = 0; j < expectedTokenSequences[i].length; j++) { + expected.append(tokenImage[expectedTokenSequences[i][j]]).append(' '); + } + if (expectedTokenSequences[i][expectedTokenSequences[i].length - 1] != 0) { + expected.append("..."); + } + expected.append(eol).append(" "); + } + String retval = "Encountered \""; + Token tok = currentToken.next; + for (int i = 0; i < maxSize; i++) { + if (i != 0) retval += " "; + if (tok.kind == 0) { + retval += tokenImage[0]; + break; + } + retval += " " + tokenImage[tok.kind]; + retval += " \""; + retval += add_escapes(tok.image); + retval += " \""; + tok = tok.next; + } + retval += "\" at line " + currentToken.next.beginLine + ", column " + currentToken.next.beginColumn; + retval += "." + eol; + if (expectedTokenSequences.length == 1) { + retval += "Was expecting:" + eol + " "; + } else { + retval += "Was expecting one of:" + eol + " "; + } + retval += expected.toString(); + return retval; + } + + /** + * The end of line string for this machine. + */ + protected String eol = System.getProperty("line.separator", "\n"); + + /** + * Used to convert raw characters to their escaped version + * when these raw version cannot be used as part of an ASCII + * string literal. + */ + static String add_escapes(String str) { + StringBuffer retval = new StringBuffer(); + char ch; + for (int i = 0; i < str.length(); i++) { + switch (str.charAt(i)) + { + case 0 : + continue; + case '\b': + retval.append("\\b"); + continue; + case '\t': + retval.append("\\t"); + continue; + case '\n': + retval.append("\\n"); + continue; + case '\f': + retval.append("\\f"); + continue; + case '\r': + retval.append("\\r"); + continue; + case '\"': + retval.append("\\\""); + continue; + case '\'': + retval.append("\\\'"); + continue; + case '\\': + retval.append("\\\\"); + continue; + default: + if ((ch = str.charAt(i)) < 0x20 || ch > 0x7e) { + String s = "0000" + Integer.toString(ch, 16); + retval.append("\\u" + s.substring(s.length() - 4, s.length())); + } else { + retval.append(ch); + } + continue; + } + } + return retval.toString(); + } + +} +/* JavaCC - OriginalChecksum=b2d839f0eac1c1a2c3ce06515ce25b20 (do not edit this line) */ http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/92ddfa59/extras/indexing/src/main/java/mvm/rya/indexing/accumulo/freetext/query/QueryParser.java ---------------------------------------------------------------------- diff --git a/extras/indexing/src/main/java/mvm/rya/indexing/accumulo/freetext/query/QueryParser.java b/extras/indexing/src/main/java/mvm/rya/indexing/accumulo/freetext/query/QueryParser.java new file mode 100644 index 0000000..8848174 --- /dev/null +++ b/extras/indexing/src/main/java/mvm/rya/indexing/accumulo/freetext/query/QueryParser.java @@ -0,0 +1,412 @@ +/* Generated By:JJTree&JavaCC: Do not edit this line. QueryParser.java */ +package mvm.rya.indexing.accumulo.freetext.query; + +/* + * #%L + * mvm.rya.indexing.accumulo + * %% + * Copyright (C) 2014 Rya + * %% + * 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. + * #L% + */ + +import java.io.StringReader; + +public class QueryParser/*@bgen(jjtree)*/implements QueryParserTreeConstants, QueryParserConstants {/*@bgen(jjtree)*/ + protected JJTQueryParserState jjtree = new JJTQueryParserState(); + // Helper method to parse Strings (instead of streams) + public static SimpleNode parse(String query) throws ParseException, TokenMgrError + { + QueryParser parser = new QueryParser(new StringReader(query)); + return parser.Start(); + } + + final public SimpleNode Start() throws ParseException { + /*@bgen(jjtree) SimpleNode */ + ASTSimpleNode jjtn000 = new ASTSimpleNode(JJTSIMPLENODE); + boolean jjtc000 = true; + jjtree.openNodeScope(jjtn000); + try { + OrExpression(); + jj_consume_token(0); + jjtree.closeNodeScope(jjtn000, true); + jjtc000 = false; + {if (true) return jjtn000;} + } catch (Throwable jjte000) { + if (jjtc000) { + jjtree.clearNodeScope(jjtn000); + jjtc000 = false; + } else { + jjtree.popNode(); + } + if (jjte000 instanceof RuntimeException) { + {if (true) throw (RuntimeException)jjte000;} + } + if (jjte000 instanceof ParseException) { + {if (true) throw (ParseException)jjte000;} + } + {if (true) throw (Error)jjte000;} + } finally { + if (jjtc000) { + jjtree.closeNodeScope(jjtn000, true); + } + } + throw new Error("Missing return statement in function"); + } + + final public void OrExpression() throws ParseException { + /*@bgen(jjtree) #Expression(> 1) */ + ASTExpression jjtn000 = new ASTExpression(JJTEXPRESSION); + boolean jjtc000 = true; + jjtree.openNodeScope(jjtn000);jjtn000.setType(ASTExpression.OR); + try { + AndExpression(); + label_1: + while (true) { + switch ((jj_ntk==-1)?jj_ntk():jj_ntk) { + case OR: + ; + break; + default: + jj_la1[0] = jj_gen; + break label_1; + } + jj_consume_token(OR); + AndExpression(); + } + } catch (Throwable jjte000) { + if (jjtc000) { + jjtree.clearNodeScope(jjtn000); + jjtc000 = false; + } else { + jjtree.popNode(); + } + if (jjte000 instanceof RuntimeException) { + {if (true) throw (RuntimeException)jjte000;} + } + if (jjte000 instanceof ParseException) { + {if (true) throw (ParseException)jjte000;} + } + {if (true) throw (Error)jjte000;} + } finally { + if (jjtc000) { + jjtree.closeNodeScope(jjtn000, jjtree.nodeArity() > 1); + } + } + } + + final public void AndExpression() throws ParseException { + /*@bgen(jjtree) #Expression(> 1) */ + ASTExpression jjtn000 = new ASTExpression(JJTEXPRESSION); + boolean jjtc000 = true; + jjtree.openNodeScope(jjtn000);jjtn000.setType(ASTExpression.AND); + try { + Term(); + label_2: + while (true) { + switch ((jj_ntk==-1)?jj_ntk():jj_ntk) { + case AND: + case NOT: + case LPAREN: + case QUOTED: + case TERM: + case PREFIXTERM: + case WILDTERM: + ; + break; + default: + jj_la1[1] = jj_gen; + break label_2; + } + switch ((jj_ntk==-1)?jj_ntk():jj_ntk) { + case AND: + jj_consume_token(AND); + break; + default: + jj_la1[2] = jj_gen; + ; + } + Term(); + } + } catch (Throwable jjte000) { + if (jjtc000) { + jjtree.clearNodeScope(jjtn000); + jjtc000 = false; + } else { + jjtree.popNode(); + } + if (jjte000 instanceof RuntimeException) { + {if (true) throw (RuntimeException)jjte000;} + } + if (jjte000 instanceof ParseException) { + {if (true) throw (ParseException)jjte000;} + } + {if (true) throw (Error)jjte000;} + } finally { + if (jjtc000) { + jjtree.closeNodeScope(jjtn000, jjtree.nodeArity() > 1); + } + } + } + + final public void Term() throws ParseException { + Token t; boolean notFlag = false; String type = ""; + switch ((jj_ntk==-1)?jj_ntk():jj_ntk) { + case NOT: + jj_consume_token(NOT); + notFlag = true; + break; + default: + jj_la1[3] = jj_gen; + ; + } + switch ((jj_ntk==-1)?jj_ntk():jj_ntk) { + case QUOTED: + case TERM: + case PREFIXTERM: + case WILDTERM: + switch ((jj_ntk==-1)?jj_ntk():jj_ntk) { + case TERM: + t = jj_consume_token(TERM); + type = ASTTerm.TERM; + break; + case WILDTERM: + t = jj_consume_token(WILDTERM); + type = ASTTerm.WILDTERM; + break; + case PREFIXTERM: + t = jj_consume_token(PREFIXTERM); + type = ASTTerm.PREFIXTERM; + break; + case QUOTED: + t = jj_consume_token(QUOTED); + type = ASTTerm.QUOTED; + break; + default: + jj_la1[4] = jj_gen; + jj_consume_token(-1); + throw new ParseException(); + } + ASTTerm jjtn001 = new ASTTerm(JJTTERM); + boolean jjtc001 = true; + jjtree.openNodeScope(jjtn001); + try { + jjtree.closeNodeScope(jjtn001, true); + jjtc001 = false; + jjtn001.setTerm(t.image); jjtn001.setNotFlag(notFlag); jjtn001.setType(type); + } finally { + if (jjtc001) { + jjtree.closeNodeScope(jjtn001, true); + } + } + break; + case LPAREN: + jj_consume_token(LPAREN); + OrExpression(); + jj_consume_token(RPAREN); + // pass on the notFlag state to the sub-expression + // note: the sub-expression might be a term (eg, "a" is a term in "!(!a)") + { + if (notFlag) { + Node n = jjtree.peekNode(); + if (n instanceof ASTExpression) { + boolean v = ((ASTExpression)n).isNotFlag(); + ((ASTExpression)n).setNotFlag(v ^ notFlag); + } + if (n instanceof ASTTerm) { + boolean v = ((ASTTerm)n).isNotFlag(); + ((ASTTerm)n).setNotFlag(v ^ notFlag); + } + } + } + break; + default: + jj_la1[5] = jj_gen; + jj_consume_token(-1); + throw new ParseException(); + } + } + + /** Generated Token Manager. */ + public QueryParserTokenManager token_source; + SimpleCharStream jj_input_stream; + /** Current token. */ + public Token token; + /** Next token. */ + public Token jj_nt; + private int jj_ntk; + private int jj_gen; + final private int[] jj_la1 = new int[6]; + static private int[] jj_la1_0; + static { + jj_la1_init_0(); + } + private static void jj_la1_init_0() { + jj_la1_0 = new int[] {0x40,0x75a0,0x20,0x80,0x7400,0x7500,}; + } + + /** Constructor with InputStream. */ + public QueryParser(java.io.InputStream stream) { + this(stream, null); + } + /** Constructor with InputStream and supplied encoding */ + public QueryParser(java.io.InputStream stream, String encoding) { + try { jj_input_stream = new SimpleCharStream(stream, encoding, 1, 1); } catch(java.io.UnsupportedEncodingException e) { throw new RuntimeException(e); } + token_source = new QueryParserTokenManager(jj_input_stream); + token = new Token(); + jj_ntk = -1; + jj_gen = 0; + for (int i = 0; i < 6; i++) jj_la1[i] = -1; + } + + /** Reinitialise. */ + public void ReInit(java.io.InputStream stream) { + ReInit(stream, null); + } + /** Reinitialise. */ + public void ReInit(java.io.InputStream stream, String encoding) { + try { jj_input_stream.ReInit(stream, encoding, 1, 1); } catch(java.io.UnsupportedEncodingException e) { throw new RuntimeException(e); } + token_source.ReInit(jj_input_stream); + token = new Token(); + jj_ntk = -1; + jjtree.reset(); + jj_gen = 0; + for (int i = 0; i < 6; i++) jj_la1[i] = -1; + } + + /** Constructor. */ + public QueryParser(java.io.Reader stream) { + jj_input_stream = new SimpleCharStream(stream, 1, 1); + token_source = new QueryParserTokenManager(jj_input_stream); + token = new Token(); + jj_ntk = -1; + jj_gen = 0; + for (int i = 0; i < 6; i++) jj_la1[i] = -1; + } + + /** Reinitialise. */ + public void ReInit(java.io.Reader stream) { + jj_input_stream.ReInit(stream, 1, 1); + token_source.ReInit(jj_input_stream); + token = new Token(); + jj_ntk = -1; + jjtree.reset(); + jj_gen = 0; + for (int i = 0; i < 6; i++) jj_la1[i] = -1; + } + + /** Constructor with generated Token Manager. */ + public QueryParser(QueryParserTokenManager tm) { + token_source = tm; + token = new Token(); + jj_ntk = -1; + jj_gen = 0; + for (int i = 0; i < 6; i++) jj_la1[i] = -1; + } + + /** Reinitialise. */ + public void ReInit(QueryParserTokenManager tm) { + token_source = tm; + token = new Token(); + jj_ntk = -1; + jjtree.reset(); + jj_gen = 0; + for (int i = 0; i < 6; i++) jj_la1[i] = -1; + } + + private Token jj_consume_token(int kind) throws ParseException { + Token oldToken; + if ((oldToken = token).next != null) token = token.next; + else token = token.next = token_source.getNextToken(); + jj_ntk = -1; + if (token.kind == kind) { + jj_gen++; + return token; + } + token = oldToken; + jj_kind = kind; + throw generateParseException(); + } + + +/** Get the next Token. */ + final public Token getNextToken() { + if (token.next != null) token = token.next; + else token = token.next = token_source.getNextToken(); + jj_ntk = -1; + jj_gen++; + return token; + } + +/** Get the specific Token. */ + final public Token getToken(int index) { + Token t = token; + for (int i = 0; i < index; i++) { + if (t.next != null) t = t.next; + else t = t.next = token_source.getNextToken(); + } + return t; + } + + private int jj_ntk() { + if ((jj_nt=token.next) == null) + return (jj_ntk = (token.next=token_source.getNextToken()).kind); + else + return (jj_ntk = jj_nt.kind); + } + + private java.util.List<int[]> jj_expentries = new java.util.ArrayList<int[]>(); + private int[] jj_expentry; + private int jj_kind = -1; + + /** Generate ParseException. */ + public ParseException generateParseException() { + jj_expentries.clear(); + boolean[] la1tokens = new boolean[16]; + if (jj_kind >= 0) { + la1tokens[jj_kind] = true; + jj_kind = -1; + } + for (int i = 0; i < 6; i++) { + if (jj_la1[i] == jj_gen) { + for (int j = 0; j < 32; j++) { + if ((jj_la1_0[i] & (1<<j)) != 0) { + la1tokens[j] = true; + } + } + } + } + for (int i = 0; i < 16; i++) { + if (la1tokens[i]) { + jj_expentry = new int[1]; + jj_expentry[0] = i; + jj_expentries.add(jj_expentry); + } + } + int[][] exptokseq = new int[jj_expentries.size()][]; + for (int i = 0; i < jj_expentries.size(); i++) { + exptokseq[i] = jj_expentries.get(i); + } + return new ParseException(token, exptokseq, tokenImage); + } + + /** Enable tracing. */ + final public void enable_tracing() { + } + + /** Disable tracing. */ + final public void disable_tracing() { + } + +} http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/92ddfa59/extras/indexing/src/main/java/mvm/rya/indexing/accumulo/freetext/query/QueryParser.jj ---------------------------------------------------------------------- diff --git a/extras/indexing/src/main/java/mvm/rya/indexing/accumulo/freetext/query/QueryParser.jj b/extras/indexing/src/main/java/mvm/rya/indexing/accumulo/freetext/query/QueryParser.jj new file mode 100644 index 0000000..1136f6c --- /dev/null +++ b/extras/indexing/src/main/java/mvm/rya/indexing/accumulo/freetext/query/QueryParser.jj @@ -0,0 +1,176 @@ +/*@bgen(jjtree) Generated By:JJTree: Do not edit this line. QueryParser.jj */ +/*@egen*//** + * A simple boolean query language that supports a number of features for free text querying. These + * features include: "and"s, "or"s, sub-expressions using parens "( )", negation, and prefix and postfix wildcard queries. + * + * Most of the classes in this package are auto-generated from QueryParser.jjt using javacc and jjtree. ASTExpression and + * ASTTerm slightly modified versions of the auto-generated files. + * + * I highly recommend the "JavaCC Eclipse Plug-in". + */options{ + JDK_VERSION = "1.5"; IGNORE_CASE = true; + static = false; +// DEBUG_PARSER = true; +// DEBUG_LOOKAHEAD = true;}PARSER_BEGIN(QueryParser)package mvm.rya.indexing.accumulo.freetext.query; +import java.io.StringReader; +public class QueryParser/*@bgen(jjtree)*/implements QueryParserTreeConstants/*@egen*/{/*@bgen(jjtree)*/ + protected JJTQueryParserState jjtree = new JJTQueryParserState(); + +/*@egen*/ + // Helper method to parse Strings (instead of streams) + public static SimpleNode parse(String query) throws ParseException, TokenMgrError { QueryParser parser = new QueryParser(new StringReader(query)); return parser.Start(); }}PARSER_END(QueryParser)SKIP : /* Ignore Whitespace */{ " " | "\t" | "\n" | "\r" +} +TOKEN : { + <AND: ("AND" | "&&" | "&") > +| <OR: ("OR" | "||" | "|") > +| <NOT: ("NOT" | "!") > +| <LPAREN: "(" > +| <RPAREN: ")" > +| <QUOTED: "\"" (<_QUOTED_CHAR>)* "\""> +| <#_QUOTED_CHAR: ~[ "\""] > +| <TERM: <_TERM_CHAR> (<_TERM_CHAR>)* > +| <PREFIXTERM: "*" <TERM> > +| <WILDTERM: <TERM> "*" > +| <#_TERM_CHAR: ~[ " ", "\t", "\n", "\r", "*", "(", ")", "!"] > +} +SimpleNode Start() :{/*@bgen(jjtree) SimpleNode */ + ASTSimpleNode jjtn000 = new ASTSimpleNode(JJTSIMPLENODE); + boolean jjtc000 = true; + jjtree.openNodeScope(jjtn000); +/*@egen*/}{/*@bgen(jjtree) SimpleNode */ + try { +/*@egen*/ + // "or"s have the lowest order of operations, so they will be highest on the tree. Start with them. OrExpression() < EOF >/*@bgen(jjtree)*/ + { + jjtree.closeNodeScope(jjtn000, true); + jjtc000 = false; + } +/*@egen*/ { return jjtn000; }/*@bgen(jjtree)*/ + } catch (Throwable jjte000) { + if (jjtc000) { + jjtree.clearNodeScope(jjtn000); + jjtc000 = false; + } else { + jjtree.popNode(); + } + if (jjte000 instanceof RuntimeException) { + throw (RuntimeException)jjte000; + } + if (jjte000 instanceof ParseException) { + throw (ParseException)jjte000; + } + throw (Error)jjte000; + } finally { + if (jjtc000) { + jjtree.closeNodeScope(jjtn000, true); + } + } +/*@egen*/} + +void OrExpression() : +{/*@bgen(jjtree) #Expression(> 1) */ + ASTExpression jjtn000 = new ASTExpression(JJTEXPRESSION); + boolean jjtc000 = true; + jjtree.openNodeScope(jjtn000); +/*@egen*/ jjtn000.setType(ASTExpression.OR); } +{/*@bgen(jjtree) #Expression(> 1) */ + try { +/*@egen*/ + AndExpression() (< OR > AndExpression())*/*@bgen(jjtree)*/ + } catch (Throwable jjte000) { + if (jjtc000) { + jjtree.clearNodeScope(jjtn000); + jjtc000 = false; + } else { + jjtree.popNode(); + } + if (jjte000 instanceof RuntimeException) { + throw (RuntimeException)jjte000; + } + if (jjte000 instanceof ParseException) { + throw (ParseException)jjte000; + } + throw (Error)jjte000; + } finally { + if (jjtc000) { + jjtree.closeNodeScope(jjtn000, jjtree.nodeArity() > 1); + } + } +/*@egen*/} + +void AndExpression() :{/*@bgen(jjtree) #Expression(> 1) */ + ASTExpression jjtn000 = new ASTExpression(JJTEXPRESSION); + boolean jjtc000 = true; + jjtree.openNodeScope(jjtn000); +/*@egen*/ jjtn000.setType(ASTExpression.AND); } +{/*@bgen(jjtree) #Expression(> 1) */ + try { +/*@egen*/ Term() ([< AND >] Term())*/*@bgen(jjtree)*/ + } catch (Throwable jjte000) { + if (jjtc000) { + jjtree.clearNodeScope(jjtn000); + jjtc000 = false; + } else { + jjtree.popNode(); + } + if (jjte000 instanceof RuntimeException) { + throw (RuntimeException)jjte000; + } + if (jjte000 instanceof ParseException) { + throw (ParseException)jjte000; + } + throw (Error)jjte000; + } finally { + if (jjtc000) { + jjtree.closeNodeScope(jjtn000, jjtree.nodeArity() > 1); + } + } +/*@egen*/ +} +void Term() :{ Token t; boolean notFlag = false; String type = ""; }{ + // Update the notFlag if a "not" is present + [ < NOT > { notFlag = true; } ] + + ( // Create a term, if a term is present + ( t = < TERM > { type = ASTTerm.TERM; } | t = < WILDTERM > { type = ASTTerm.WILDTERM; } + | t = < PREFIXTERM > { type = ASTTerm.PREFIXTERM; } + | t = < QUOTED > { type = ASTTerm.QUOTED; } + )/*@bgen(jjtree) #Term(true) */ + { + ASTTerm jjtn001 = new ASTTerm(JJTTERM); + boolean jjtc001 = true; + jjtree.openNodeScope(jjtn001); + } + try { +/*@egen*//*@bgen(jjtree)*/ + { + jjtree.closeNodeScope(jjtn001, true); + jjtc001 = false; + } +/*@egen*/ { jjtn001.setTerm(t.image); jjtn001.setNotFlag(notFlag); jjtn001.setType(type); }/*@bgen(jjtree)*/ + } finally { + if (jjtc001) { + jjtree.closeNodeScope(jjtn001, true); + } + } +/*@egen*/ + + // Otherwise, we a dealing with a Sub-Expression, so start back from the top. + | ( < LPAREN > ( OrExpression() ) < RPAREN > ) + { + // pass on the notFlag state to the sub-expression + // note: the sub-expression might be a term (eg, "a" is a term in "!(!a)") + { + if (notFlag) { + Node n = jjtree.peekNode(); + if (n instanceof ASTExpression) { + boolean v = ((ASTExpression)n).isNotFlag(); + ((ASTExpression)n).setNotFlag(v ^ notFlag); + } + if (n instanceof ASTTerm) { boolean v = ((ASTTerm)n).isNotFlag(); ((ASTTerm)n).setNotFlag(v ^ notFlag); } + } + } + } + ) + +} \ No newline at end of file http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/92ddfa59/extras/indexing/src/main/java/mvm/rya/indexing/accumulo/freetext/query/QueryParser.jjt ---------------------------------------------------------------------- diff --git a/extras/indexing/src/main/java/mvm/rya/indexing/accumulo/freetext/query/QueryParser.jjt b/extras/indexing/src/main/java/mvm/rya/indexing/accumulo/freetext/query/QueryParser.jjt new file mode 100644 index 0000000..51a1fd3 --- /dev/null +++ b/extras/indexing/src/main/java/mvm/rya/indexing/accumulo/freetext/query/QueryParser.jjt @@ -0,0 +1,71 @@ +/** + * A simple boolean query language that supports a number of features for free text querying. These + * features include: "and"s, "or"s, sub-expressions using parens "( )", negation, and prefix and postfix wildcard queries. + * + * Most of the classes in this package are auto-generated from QueryParser.jjt using javacc and jjtree. ASTExpression and + * ASTTerm slightly modified versions of the auto-generated files. + * + * I highly recommend the "JavaCC Eclipse Plug-in". + */options{ + MULTI = true; JDK_VERSION = "1.5"; IGNORE_CASE = true; NODE_DEFAULT_VOID=true; + static = false; +// DEBUG_PARSER = true; +// DEBUG_LOOKAHEAD = true;}PARSER_BEGIN(QueryParser)package mvm.rya.indexing.accumulo.freetext.query; +import java.io.StringReader; +public class QueryParser{ + // Helper method to parse Strings (instead of streams) + public static SimpleNode parse(String query) throws ParseException, TokenMgrError { QueryParser parser = new QueryParser(new StringReader(query)); return parser.Start(); }}PARSER_END(QueryParser)SKIP : /* Ignore Whitespace */{ " " | "\t" | "\n" | "\r" +} +TOKEN : { + <AND: ("AND" | "&&" | "&") > +| <OR: ("OR" | "||" | "|") > +| <NOT: ("NOT" | "!") > +| <LPAREN: "(" > +| <RPAREN: ")" > +| <QUOTED: "\"" (<_QUOTED_CHAR>)* "\""> +| <#_QUOTED_CHAR: ~[ "\""] > +| <TERM: <_TERM_CHAR> (<_TERM_CHAR>)* > +| <PREFIXTERM: "*" <TERM> > +| <WILDTERM: <TERM> "*" > +| <#_TERM_CHAR: ~[ " ", "\t", "\n", "\r", "*", "(", ")", "!"] > +} +SimpleNode Start() #SimpleNode:{}{ + // "or"s have the lowest order of operations, so they will be highest on the tree. Start with them. OrExpression() < EOF > { return jjtThis; }} + +void OrExpression() #Expression(>1): +{ jjtThis.setType(ASTExpression.OR); } +{ + AndExpression() (< OR > AndExpression())*} + +void AndExpression() #Expression(>1):{ jjtThis.setType(ASTExpression.AND); } +{ Term() ([< AND >] Term())* +} +void Term() :{ Token t; boolean notFlag = false; String type = ""; }{ + // Update the notFlag if a "not" is present + [ < NOT > { notFlag = true; } ] + + ( // Create a term, if a term is present + ( t = < TERM > { type = ASTTerm.TERM; } | t = < WILDTERM > { type = ASTTerm.WILDTERM; } + | t = < PREFIXTERM > { type = ASTTerm.PREFIXTERM; } + | t = < QUOTED > { type = ASTTerm.QUOTED; } + ) { jjtThis.setTerm(t.image); jjtThis.setNotFlag(notFlag); jjtThis.setType(type); } #Term() + + // Otherwise, we a dealing with a Sub-Expression, so start back from the top. + | ( < LPAREN > ( OrExpression() ) < RPAREN > ) + { + // pass on the notFlag state to the sub-expression + // note: the sub-expression might be a term (eg, "a" is a term in "!(!a)") + { + if (notFlag) { + Node n = jjtree.peekNode(); + if (n instanceof ASTExpression) { + boolean v = ((ASTExpression)n).isNotFlag(); + ((ASTExpression)n).setNotFlag(v ^ notFlag); + } + if (n instanceof ASTTerm) { boolean v = ((ASTTerm)n).isNotFlag(); ((ASTTerm)n).setNotFlag(v ^ notFlag); } + } + } + } + ) + +} \ No newline at end of file http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/92ddfa59/extras/indexing/src/main/java/mvm/rya/indexing/accumulo/freetext/query/QueryParserConstants.java ---------------------------------------------------------------------- diff --git a/extras/indexing/src/main/java/mvm/rya/indexing/accumulo/freetext/query/QueryParserConstants.java b/extras/indexing/src/main/java/mvm/rya/indexing/accumulo/freetext/query/QueryParserConstants.java new file mode 100644 index 0000000..5403763 --- /dev/null +++ b/extras/indexing/src/main/java/mvm/rya/indexing/accumulo/freetext/query/QueryParserConstants.java @@ -0,0 +1,79 @@ +/* Generated By:JJTree&JavaCC: Do not edit this line. QueryParserConstants.java */ +package mvm.rya.indexing.accumulo.freetext.query; + +/* + * #%L + * mvm.rya.indexing.accumulo + * %% + * Copyright (C) 2014 Rya + * %% + * 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. + * #L% + */ + + +/** + * Token literal values and constants. + * Generated by org.javacc.parser.OtherFilesGen#start() + */ +public interface QueryParserConstants { + + /** End of File. */ + int EOF = 0; + /** RegularExpression Id. */ + int AND = 5; + /** RegularExpression Id. */ + int OR = 6; + /** RegularExpression Id. */ + int NOT = 7; + /** RegularExpression Id. */ + int LPAREN = 8; + /** RegularExpression Id. */ + int RPAREN = 9; + /** RegularExpression Id. */ + int QUOTED = 10; + /** RegularExpression Id. */ + int _QUOTED_CHAR = 11; + /** RegularExpression Id. */ + int TERM = 12; + /** RegularExpression Id. */ + int PREFIXTERM = 13; + /** RegularExpression Id. */ + int WILDTERM = 14; + /** RegularExpression Id. */ + int _TERM_CHAR = 15; + + /** Lexical state. */ + int DEFAULT = 0; + + /** Literal token values. */ + String[] tokenImage = { + "<EOF>", + "\" \"", + "\"\\t\"", + "\"\\n\"", + "\"\\r\"", + "<AND>", + "<OR>", + "<NOT>", + "\"(\"", + "\")\"", + "<QUOTED>", + "<_QUOTED_CHAR>", + "<TERM>", + "<PREFIXTERM>", + "<WILDTERM>", + "<_TERM_CHAR>", + }; + +}
