From 1205ea08cc9e53de40b71447a79daf378cb0a205 Mon Sep 17 00:00:00 2001 From: "Brian S. O'Neill" Date: Wed, 30 Aug 2006 01:56:35 +0000 Subject: Add filter implementation --- .../com/amazon/carbonado/filter/AndFilter.java | 128 +++++ .../amazon/carbonado/filter/BinaryOpFilter.java | 116 ++++ .../java/com/amazon/carbonado/filter/Binder.java | 93 +++ .../com/amazon/carbonado/filter/ClosedFilter.java | 127 +++++ .../com/amazon/carbonado/filter/Distributer.java | 78 +++ .../java/com/amazon/carbonado/filter/Filter.java | 505 +++++++++++++++++ .../com/amazon/carbonado/filter/FilterParser.java | 316 +++++++++++ .../com/amazon/carbonado/filter/FilterValues.java | 623 +++++++++++++++++++++ .../java/com/amazon/carbonado/filter/Group.java | 134 +++++ .../com/amazon/carbonado/filter/OpenFilter.java | 127 +++++ .../java/com/amazon/carbonado/filter/OrFilter.java | 128 +++++ .../amazon/carbonado/filter/PropertyFilter.java | 472 ++++++++++++++++ .../carbonado/filter/PropertyFilterList.java | 186 ++++++ .../java/com/amazon/carbonado/filter/Reducer.java | 103 ++++ .../java/com/amazon/carbonado/filter/RelOp.java | 78 +++ .../java/com/amazon/carbonado/filter/Visitor.java | 55 ++ .../com/amazon/carbonado/filter/package-info.java | 24 + 17 files changed, 3293 insertions(+) create mode 100644 src/main/java/com/amazon/carbonado/filter/AndFilter.java create mode 100644 src/main/java/com/amazon/carbonado/filter/BinaryOpFilter.java create mode 100644 src/main/java/com/amazon/carbonado/filter/Binder.java create mode 100644 src/main/java/com/amazon/carbonado/filter/ClosedFilter.java create mode 100644 src/main/java/com/amazon/carbonado/filter/Distributer.java create mode 100644 src/main/java/com/amazon/carbonado/filter/Filter.java create mode 100644 src/main/java/com/amazon/carbonado/filter/FilterParser.java create mode 100644 src/main/java/com/amazon/carbonado/filter/FilterValues.java create mode 100644 src/main/java/com/amazon/carbonado/filter/Group.java create mode 100644 src/main/java/com/amazon/carbonado/filter/OpenFilter.java create mode 100644 src/main/java/com/amazon/carbonado/filter/OrFilter.java create mode 100644 src/main/java/com/amazon/carbonado/filter/PropertyFilter.java create mode 100644 src/main/java/com/amazon/carbonado/filter/PropertyFilterList.java create mode 100644 src/main/java/com/amazon/carbonado/filter/Reducer.java create mode 100644 src/main/java/com/amazon/carbonado/filter/RelOp.java create mode 100644 src/main/java/com/amazon/carbonado/filter/Visitor.java create mode 100644 src/main/java/com/amazon/carbonado/filter/package-info.java (limited to 'src/main/java') diff --git a/src/main/java/com/amazon/carbonado/filter/AndFilter.java b/src/main/java/com/amazon/carbonado/filter/AndFilter.java new file mode 100644 index 0000000..92c3937 --- /dev/null +++ b/src/main/java/com/amazon/carbonado/filter/AndFilter.java @@ -0,0 +1,128 @@ +/* + * Copyright 2006 Amazon Technologies, Inc. or its affiliates. + * Amazon, Amazon.com and Carbonado are trademarks or registered trademarks + * of Amazon Technologies, Inc. or its affiliates. All rights reserved. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package com.amazon.carbonado.filter; + +import java.io.IOException; + +import com.amazon.carbonado.Storable; + +/** + * Filter tree node that performs a logical 'and' test. + * + * @author Brian S O'Neill + */ +public class AndFilter extends BinaryOpFilter { + /** + * Returns a canonical instance. + * + * @throws IllegalArgumentException if either filter is null + */ + @SuppressWarnings("unchecked") + static AndFilter getCanonical(Filter left, Filter right) { + return (AndFilter) cCanonical.put(new AndFilter(left, right)); + } + + /** + * @throws IllegalArgumentException if either filter is null + */ + private AndFilter(Filter left, Filter right) { + super(left, right); + } + + public Filter not() { + return mLeft.not().or(mRight.not()); + } + + public R accept(Visitor visitor, P param) { + return visitor.visit(this, param); + } + + Filter buildDisjunctiveNormalForm() { + Filter left = mLeft.reduce().dnf(); + Filter right = mRight.reduce().dnf(); + if (left instanceof OrFilter) { + return left.accept(new Distributer(true, true), right).reduce().dnf(); + } + if (right instanceof OrFilter) { + return right.accept(new Distributer(false, true), left).reduce().dnf(); + } + return left.and(right).reduce(); + } + + Filter buildConjunctiveNormalForm() { + return mLeft.cnf().and(mRight.cnf()).reduce(); + } + + boolean checkIsDisjunctiveNormalForm() { + return (!(mLeft instanceof OrFilter)) + && (!(mRight instanceof OrFilter)) + && mLeft.isDisjunctiveNormalForm() + && mRight.isDisjunctiveNormalForm(); + } + + boolean checkIsConjunctiveNormalForm() { + return mLeft.isConjunctiveNormalForm() && mRight.isConjunctiveNormalForm(); + } + + @Override + public int hashCode() { + return mLeft.hashCode() * 31 + mRight.hashCode(); + } + + @Override + public boolean equals(Object obj) { + if (this == obj) { + return true; + } + if (obj instanceof AndFilter) { + AndFilter other = (AndFilter) obj; + return getStorableType() == other.getStorableType() + && mLeft.equals(other.mLeft) && mRight.equals(other.mRight); + } + return false; + } + + public void appendTo(Appendable app, FilterValues values) throws IOException { + if (mLeft instanceof OrFilter) { + app.append('('); + mLeft.appendTo(app, values); + app.append(')'); + } else { + mLeft.appendTo(app, values); + } + app.append(" & "); + if (mRight instanceof OrFilter) { + app.append('('); + mRight.appendTo(app, values); + app.append(')'); + } else { + mRight.appendTo(app, values); + } + } + + void dumpTree(Appendable app, int indentLevel) throws IOException { + mRight.dumpTree(app, indentLevel + 1); + for (int i=0; i extends Filter { + // Bits used in mState. + private static final byte REDUCED = 0x1 << 0; // tree is reduced + private static final byte DNF_KNOWN = 0x1 << 1; // disjunctive normal form state is known + private static final byte DNF = 0x1 << 2; // is disjunctive normal form if set + private static final byte CNF_KNOWN = 0x1 << 3; // conjunctive normal form state is known + private static final byte CNF = 0x1 << 4; // is conjunctive normal form if set + private static final byte BOUND = 0x1 << 5; // properties are bound when set + + final Filter mLeft; + final Filter mRight; + + byte mState; + + BinaryOpFilter(Filter left, Filter right) { + super(left == null ? null : left.getStorableType()); + if (right == null) { + throw new IllegalArgumentException(); + } + if (left.getStorableType() != right.getStorableType()) { + throw new IllegalArgumentException("Type mismatch"); + } + mLeft = left; + mRight = right; + } + + public Filter getLeftFilter() { + return mLeft; + } + + public Filter getRightFilter() { + return mRight; + } + + public Filter bind() { + if (isBound()) { + return this; + } + return accept(new Binder(), null); + } + + public boolean isBound() { + return (mState & BOUND) != 0; + } + + void markBound() { + mState |= BOUND; + } + + final synchronized boolean isDisjunctiveNormalForm() { + if ((mState & DNF_KNOWN) != 0) { // if dnf state is known... + return (mState & DNF) != 0; // return true if dnf + } + if (checkIsDisjunctiveNormalForm()) { + mState |= (DNF_KNOWN | DNF); // dnf state is now known, and is dnf + return true; + } else { + mState |= DNF_KNOWN; // dnf state is now known, and is not dnf + mState &= ~DNF; + return false; + } + } + + abstract boolean checkIsDisjunctiveNormalForm(); + + final synchronized boolean isConjunctiveNormalForm() { + if ((mState & CNF_KNOWN) != 0) { // if cnf state is known... + return (mState & CNF) != 0; // return true if cnf + } + if (checkIsConjunctiveNormalForm()) { + mState |= (CNF_KNOWN | CNF); // cnf state is now known, and is cnf + return true; + } else { + mState |= CNF_KNOWN; // cnf state is now known, and is not cnf + mState &= ~CNF; + return false; + } + } + + abstract boolean checkIsConjunctiveNormalForm(); + + synchronized boolean isReduced() { + return (mState & REDUCED) != 0; + } + + synchronized void markReduced() { + mState |= REDUCED; + } +} diff --git a/src/main/java/com/amazon/carbonado/filter/Binder.java b/src/main/java/com/amazon/carbonado/filter/Binder.java new file mode 100644 index 0000000..7a854f1 --- /dev/null +++ b/src/main/java/com/amazon/carbonado/filter/Binder.java @@ -0,0 +1,93 @@ +/* + * Copyright 2006 Amazon Technologies, Inc. or its affiliates. + * Amazon, Amazon.com and Carbonado are trademarks or registered trademarks + * of Amazon Technologies, Inc. or its affiliates. All rights reserved. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package com.amazon.carbonado.filter; + +import java.util.IdentityHashMap; +import java.util.Map; + +import com.amazon.carbonado.Storable; + +/** + * Used by bind operation - assigns bind IDs to property filters. This allows + * operations like dnf to not lose track of variable assignments even after + * more nodes are added to the filter tree. + * + * @author Brian S O'Neill + */ +class Binder extends Visitor, Object> { + // Maps PropertyFilter with bind ID zero to PropertyFilter with highest + // bind ID. + private final Map, PropertyFilter> mBindMap; + + Binder() { + mBindMap = new IdentityHashMap, PropertyFilter>(); + } + + @Override + public Filter visit(OrFilter filter, Object param) { + Filter left = filter.getLeftFilter(); + Filter newLeft = left.accept(this, null); + Filter right = filter.getRightFilter(); + Filter newRight = right.accept(this, null); + + Filter newFilter; + if (left != newLeft || right != newRight) { + newFilter = newLeft.or(newRight); + } else { + newFilter = filter; + } + + newFilter.markBound(); + return newFilter; + } + + @Override + public Filter visit(AndFilter filter, Object param) { + Filter left = filter.getLeftFilter(); + Filter newLeft = left.accept(this, null); + Filter right = filter.getRightFilter(); + Filter newRight = right.accept(this, null); + + Filter newFilter; + if (left != newLeft || right != newRight) { + newFilter = newLeft.and(newRight); + } else { + newFilter = filter; + } + + newFilter.markBound(); + return newFilter; + } + + @Override + public Filter visit(PropertyFilter filter, Object param) { + if (filter.getBindID() != 0) { + return filter; + } + filter = PropertyFilter.getCanonical(filter, 1); + PropertyFilter highest = mBindMap.get(filter); + if (highest == null) { + highest = filter; + } else { + highest = PropertyFilter.getCanonical(filter, highest.getBindID() + 1); + } + mBindMap.put(filter, highest); + return highest; + } +} diff --git a/src/main/java/com/amazon/carbonado/filter/ClosedFilter.java b/src/main/java/com/amazon/carbonado/filter/ClosedFilter.java new file mode 100644 index 0000000..4584109 --- /dev/null +++ b/src/main/java/com/amazon/carbonado/filter/ClosedFilter.java @@ -0,0 +1,127 @@ +/* + * Copyright 2006 Amazon Technologies, Inc. or its affiliates. + * Amazon, Amazon.com and Carbonado are trademarks or registered trademarks + * of Amazon Technologies, Inc. or its affiliates. All rights reserved. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package com.amazon.carbonado.filter; + +import java.io.IOException; + +import com.amazon.carbonado.Storable; + +/** + * Filter which blocks any results from passing through. + * + * @author Brian S O'Neill + */ +public class ClosedFilter extends Filter { + ClosedFilter(Class type) { + super(type); + } + + public Filter and(Filter filter) { + return this; + } + + public Filter or(Filter filter) { + return filter; + } + + public Filter not() { + return getOpenFilter(getStorableType()); + } + + @Override + public FilterValues initialFilterValues() { + return null; + } + + @Override + PropertyFilterList getTailPropertyFilterList() { + return null; + } + + public R accept(Visitor visitor, P param) { + return visitor.visit(this, param); + } + + public Filter bind() { + return this; + } + + public boolean isBound() { + return true; + } + + void markBound() { + } + + Filter buildDisjunctiveNormalForm() { + return this; + } + + Filter buildConjunctiveNormalForm() { + return this; + } + + boolean isDisjunctiveNormalForm() { + return true; + } + + boolean isConjunctiveNormalForm() { + return true; + } + + boolean isReduced() { + return true; + } + + void markReduced() { + } + + @Override + public int hashCode() { + return getStorableType().hashCode(); + } + + @Override + public boolean equals(Object obj) { + if (this == obj) { + return true; + } + if (obj instanceof ClosedFilter) { + ClosedFilter other = (ClosedFilter) obj; + return getStorableType() == other.getStorableType(); + } + return false; + } + + @Override + public String toString() { + return "closed"; + } + + public void appendTo(Appendable app, FilterValues values) throws IOException { + app.append("closed"); + } + + void dumpTree(Appendable app, int indentLevel) throws IOException { + for (int i=0; i extends Visitor, Filter> { + private final boolean mDoRight; + private final boolean mDoAnd; + + /** + * @param doRight when true, distribute to the right, otherwise, + * distribute to the left. + * @param doAnd when true, distribute 'and' operations, otherwise + * distribute 'or' operations. + */ + Distributer(boolean doRight, boolean doAnd) { + mDoRight = doRight; + mDoAnd = doAnd; + } + + /** + * @param filter candidate node to potentially replace + * @param distribute node to distribute into candidate node + * @return original candidate or replacement + */ + @Override + public Filter visit(OrFilter filter, Filter distribute) { + return OrFilter.getCanonical(filter.getLeftFilter().accept(this, distribute), + filter.getRightFilter().accept(this, distribute)); + } + + /** + * @param filter candidate node to potentially replace + * @param distribute node to distribute into candidate node + * @return original candidate or replacement + */ + @Override + public Filter visit(AndFilter filter, Filter distribute) { + return AndFilter.getCanonical(filter.getLeftFilter().accept(this, distribute), + filter.getRightFilter().accept(this, distribute)); + } + + /** + * @param filter candidate node to potentially replace + * @param distribute node to distribute into candidate node + * @return original candidate or replacement + */ + @Override + public Filter visit(PropertyFilter filter, Filter distribute) { + if (mDoRight) { + return mDoAnd ? filter.and(distribute) : filter.or(distribute); + } else { + return mDoAnd ? distribute.and(filter) : distribute.or(filter); + } + } +} diff --git a/src/main/java/com/amazon/carbonado/filter/Filter.java b/src/main/java/com/amazon/carbonado/filter/Filter.java new file mode 100644 index 0000000..f688d60 --- /dev/null +++ b/src/main/java/com/amazon/carbonado/filter/Filter.java @@ -0,0 +1,505 @@ +/* + * Copyright 2006 Amazon Technologies, Inc. or its affiliates. + * Amazon, Amazon.com and Carbonado are trademarks or registered trademarks + * of Amazon Technologies, Inc. or its affiliates. All rights reserved. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package com.amazon.carbonado.filter; + +import java.io.IOException; +import java.util.Map; +import org.cojen.util.SoftValuedHashMap; +import org.cojen.util.WeakCanonicalSet; +import org.cojen.util.WeakIdentityMap; + +import com.amazon.carbonado.MalformedFilterException; +import com.amazon.carbonado.Storable; + +import com.amazon.carbonado.info.ChainedProperty; + +import com.amazon.carbonado.util.Appender; + +/** + * An immutable tree structure representing a query result filter. Filters can + * be created using a builder pattern, by expression parsing, or by a + * combination of techniques. Filter instances are canonical, which means that + * equivalent instances can be compared for equality using the '==' operator. + * + *

Any method that accepts a filter expression parses against the following + * syntax: + * + * 

+ * Filter          = OrFilter
+ * OrFilter        = AndFilter { "|" AndFilter }
+ * AndFilter       = NotFilter { "&" NotFilter }
+ * NotFilter       = [ "!" ] EntityFilter
+ * EntityFilter    = PropertyFilter
+ *                 | "(" Filter ")"
+ * PropertyFilter  = ChainedProperty RelOp "?"
+ * RelOp           = "=" | "!=" | "<" | ">=" | ">" | "<="
+ * ChainedProperty = Identifier { "." Identifier }
+ *
+ * + * @author Brian S O'Neill + */ +public abstract class Filter implements Appender { + + private static final Object OPEN_KEY = new Object(); + private static final Object CLOSED_KEY = new Object(); + + // Collection of canonical filters. + static WeakCanonicalSet cCanonical = new WeakCanonicalSet(); + + // Map<(weak)Class, Map>> + private static Map cCache = new WeakIdentityMap(); + + /** + * Returns a cached filter instance that operates on the given type and + * filter expression. + * + * @param type type of Storable that query is made against + * @param expression query filter expression to parse + * @return canonical Filter instance + * @throws IllegalArgumentException if type or filter expression is null + * @throws MalformedFilterException if filter expression is malformed + */ + public static Filter filterFor(Class type, String expression) { + Map> filterCache = getFilterCache(type); + synchronized (filterCache) { + Filter filter = filterCache.get(expression); + if (filter == null) { + filter = new FilterParser(type, expression).parseRoot(); + filterCache.put(expression, filter); + } + return filter; + } + } + + /** + * Returns a cached filter instance that operates on the given type, which + * allows all results to pass through. + * + * @param type type of Storable that query is made against + * @return canonical Filter instance + * @see OpenFilter + */ + public static Filter getOpenFilter(Class type) { + Map> filterCache = getFilterCache(type); + synchronized (filterCache) { + Filter filter = filterCache.get(OPEN_KEY); + if (filter == null) { + filter = new OpenFilter(type); + filterCache.put(OPEN_KEY, filter); + } + return filter; + } + } + + /** + * Returns a cached filter instance that operates on the given type, which + * prevents any results from passing through. + * + * @param type type of Storable that query is made against + * @return canonical Filter instance + * @see ClosedFilter + */ + public static Filter getClosedFilter(Class type) { + Map> filterCache = getFilterCache(type); + synchronized (filterCache) { + Filter filter = filterCache.get(CLOSED_KEY); + if (filter == null) { + filter = new ClosedFilter(type); + filterCache.put(CLOSED_KEY, filter); + } + return filter; + } + } + + @SuppressWarnings("unchecked") + private static Map> getFilterCache(Class type) { + synchronized (cCache) { + Map> filterCache = (Map>) cCache.get(type); + if (filterCache == null) { + filterCache = new SoftValuedHashMap(7); + cCache.put(type, filterCache); + } + return filterCache; + } + } + + private final Class mType; + + // Root FilterValues, built on demand, which is immutable. + private transient volatile FilterValues mFilterValues; + + // Tail of PropertyFilterList used by mFilterValues. mFilterValues + // references the head. + private transient volatile PropertyFilterList mTailPropertyFilterList; + + /** + * Package-private constructor to prevent subclassing outside this package. + */ + Filter(Class type) { + mType = type; + } + + /** + * Returns the storable type that this filter operates on. + */ + public Class getStorableType() { + return mType; + } + + /** + * Returns a FilterValues instance for assigning values to a + * Filter. Returns null if Filter has no parameters. + * + *

Note: The returned FilterValues instance may reference a different + * filter instance than this one. Call getFilter to retrieve it. The + * difference is caused by the filter property values being {@link #bind bound}. + */ + public FilterValues initialFilterValues() { + if (mFilterValues == null) { + Filter boundFilter = bind(); + + if (boundFilter != this) { + return boundFilter.initialFilterValues(); + } + + buildFilterValues(); + } + + return mFilterValues; + } + + /** + * Returns tail of linked list, and so it can only be traversed by getting + * previous nodes. + * + * @return tail of PropertyFilterList, or null if no parameters + */ + PropertyFilterList getTailPropertyFilterList() { + if (mTailPropertyFilterList == null) { + buildFilterValues(); + } + + return mTailPropertyFilterList; + } + + private void buildFilterValues() { + PropertyFilterList list = accept(new PropertyFilterList.Builder(), null); + + // List should never be null since only OpenFilter and ClosedFilter + // have no properties, and they override initialFilterValues and + // getTailPropertyFilterList. + assert(list != null); + + // Since FilterValues instances are immutable, save this for re-use. + mFilterValues = FilterValues.create(this, list); + + // PropertyFilterList can be saved for re-use because it too is + // immutable (after PropertyFilterListBuilder has run). + mTailPropertyFilterList = list.get(-1); + } + + /** + * Returns a combined filter instance that accepts records which are only + * accepted by this filter and the one given. + * + * @param expression query filter expression to parse + * @return canonical Filter instance + * @throws IllegalArgumentException if filter is null + */ + public final Filter and(String expression) { + return and(new FilterParser(mType, expression).parseRoot()); + } + + /** + * Returns a combined filter instance that accepts records which are only + * accepted by this filter and the one given. + * + * @return canonical Filter instance + * @throws IllegalArgumentException if filter is null + */ + public Filter and(Filter filter) { + if (filter instanceof OpenFilter) { + return this; + } + if (filter instanceof ClosedFilter) { + return filter; + } + return AndFilter.getCanonical(this, filter); + } + + /** + * Returns a combined filter instance that accepts records which are only + * accepted by this filter and the one given. + * + * @param propertyName property name to match on, which may be a chained property + * @param operator relational operator + * @return canonical Filter instance + * @throws IllegalArgumentException if property is not found + */ + public final Filter and(String propertyName, RelOp operator) { + ChainedProperty prop = new FilterParser(mType, propertyName).parseChainedProperty(); + return and(PropertyFilter.getCanonical(prop, operator, 0)); + } + + /** + * Returns a combined filter instance that accepts records which are only + * accepted by this filter and the one given. + * + * @param propertyName property name to match on, which may be a chained property + * @param operator relational operator + * @param constantValue constant value to match + * @return canonical Filter instance + * @throws IllegalArgumentException if property is not found + */ + public final Filter and(String propertyName, RelOp operator, Object constantValue) { + ChainedProperty prop = new FilterParser(mType, propertyName).parseChainedProperty(); + return and(PropertyFilter.getCanonical(prop, operator, 0).constant(constantValue)); + } + + /** + * Returns a combined filter instance that accepts records which are + * accepted either by this filter or the one given. + * + * @param expression query filter expression to parse + * @return canonical Filter instance + * @throws IllegalArgumentException if filter is null + */ + public final Filter or(String expression) { + return or(new FilterParser(mType, expression).parseRoot()); + } + + /** + * Returns a combined filter instance that accepts records which are + * accepted either by this filter or the one given. + * + * @return canonical Filter instance + * @throws IllegalArgumentException if filter is null + */ + public Filter or(Filter filter) { + if (filter instanceof OpenFilter) { + return filter; + } + if (filter instanceof ClosedFilter) { + return this; + } + return OrFilter.getCanonical(this, filter); + } + + /** + * Returns a combined filter instance that accepts records which are + * accepted either by this filter or the one given. + * + * @param propertyName property name to match on, which may be a chained property + * @param operator relational operator + * @return canonical Filter instance + * @throws IllegalArgumentException if property is not found + */ + public final Filter or(String propertyName, RelOp operator) { + ChainedProperty prop = new FilterParser(mType, propertyName).parseChainedProperty(); + return or(PropertyFilter.getCanonical(prop, operator, 0)); + } + + /** + * Returns a combined filter instance that accepts records which are + * accepted either by this filter or the one given. + * + * @param propertyName property name to match on, which may be a chained property + * @param operator relational operator + * @param constantValue constant value to match + * @return canonical Filter instance + * @throws IllegalArgumentException if property is not found + */ + public final Filter or(String propertyName, RelOp operator, Object constantValue) { + ChainedProperty prop = new FilterParser(mType, propertyName).parseChainedProperty(); + return or(PropertyFilter.getCanonical(prop, operator, 0).constant(constantValue)); + } + + /** + * Returns the logical negation of this filter. + * + * @return canonical Filter instance + */ + public abstract Filter not(); + + /** + * Returns an equivalent filter that is in disjunctive normal form. In this + * form, all logical 'and' operations are performed before all logical 'or' + * operations. This method often returns a filter with more terms than + * before. + * + *

The tree is also normalized such that all terms in a common logical + * operation are ordered left to right. For example, expressions of the + * form {@code "(a = ? & b = ?) & (c = ? & d = ?)"} are converted to + * {@code "(((a = ?) & (b = ?)) & c = ?) & d = ?"}. + * + *

Although the disjunctive normal filter may have more terms, it can be + * used to extract values from a FilterValues instance created from this + * filter. This works because the disjunctive normal filter is composed of + * the same set of PropertyFilter instances. + * + * @return canonical Filter instance + */ + public final Filter disjunctiveNormalForm() { + return bind().dnf(); + } + + final Filter dnf() { + Filter filter = this; + if (!filter.isDisjunctiveNormalForm()) { + filter = filter.buildDisjunctiveNormalForm(); + } + return filter.reduce(); + } + + /** + * Returns an equivalent filter that is in conjunctive normal form. In this + * form, all logical 'or' operations are performed before all logical 'and' + * operations. This method often returns a filter with more terms than + * before. + * + *

The tree is also normalized such that all terms in a common logical + * operation are ordered left to right. For example, expressions of the + * form {@code "(a = ? | b = ?) | (c = ? | d = ?)"} are converted to + * {@code "(((a = ?) | (b = ?)) | c = ?) | d = ?"}. + * + *

Although the conjunctive normal filter may have more terms, it can be + * used to extract values from a FilterValues instance created from this + * filter. This works because the conjunctive normal filter is composed of + * the same set of PropertyFilter instances. + * + * @return canonical Filter instance + */ + public final Filter conjunctiveNormalForm() { + return bind().cnf(); + } + + final Filter cnf() { + Filter filter = this; + if (!filter.isConjunctiveNormalForm()) { + filter = filter.buildConjunctiveNormalForm(); + } + return filter.reduce(); + } + + /** + * Accept the given visitor subclass to traverse the filter tree. + * + * @param visitor visitor to traverse through the tree + * @param param generic input parameter passed to visit methods + * @return generic return value passed from visit methods + */ + public abstract R accept(Visitor visitor, P param); + + /** + * Walks through each property filter, assigning a bind ID to it. This step + * is automatically performed for proper dnf/cnf conversion, and for + * building FilterValues. + * + * @return canonical Filter instance with bound property filters + */ + public abstract Filter bind(); + + /** + * Returns true if all property filters are known to be properly + * bound. This is a side effect of calling {@link #bind}, {@link + * #initialFilterValues}, {@link #disjunctiveNormalForm} or {@link + * #conjunctiveNormalForm}. + */ + public abstract boolean isBound(); + + /** + * Identify this filter node as bound. Should only be called by Binder. + */ + abstract void markBound(); + + /** + * Returns an equivalent filter with redundant terms eliminated. The tree + * is also normalized such that all terms in a common logical operation are + * ordered left to right. For example, expressions of the form + * {@code "(a = ? & b = ?) & (c = ? & d = ?)"} are converted to + * {@code "(((a = ?) & (b = ?)) & c = ?) & d = ?"}. + * + * @return canonical Filter instance + */ + public final Filter reduce() { + return isReduced() ? this : accept(new Reducer(), null); + } + + abstract Filter buildDisjunctiveNormalForm(); + + abstract Filter buildConjunctiveNormalForm(); + + abstract boolean isDisjunctiveNormalForm(); + + abstract boolean isConjunctiveNormalForm(); + + /** + * Returns true if filter node is in a reduced form. + */ + abstract boolean isReduced(); + + /** + * Identify this filter node as reduced. Should only be called by Reducer. + */ + abstract void markReduced(); + + @Override + public abstract int hashCode(); + + @Override + public abstract boolean equals(Object obj); + + /** + * Returns the string value of this filter, which is also parsable. + */ + @Override + public String toString() { + StringBuilder buf = new StringBuilder(); + try { + appendTo(buf); + } catch (IOException e) { + // Not gonna happen. + } + return buf.toString(); + } + + /** + * Appends the string value of this filter into the given Appendable. + */ + public void appendTo(Appendable app) throws IOException { + appendTo(app, null); + } + + /** + * Appends the string value of this filter into the given Appendable. + * + * @param values optionally supply filter values + */ + public abstract void appendTo(Appendable app, FilterValues values) + throws IOException; + + /** + * Prints a tree representation of the filter to the given Appendable. + */ + public void dumpTree(Appendable app) throws IOException { + dumpTree(app, 0); + } + + abstract void dumpTree(Appendable app, int indentLevel) throws IOException; +} diff --git a/src/main/java/com/amazon/carbonado/filter/FilterParser.java b/src/main/java/com/amazon/carbonado/filter/FilterParser.java new file mode 100644 index 0000000..5c483e0 --- /dev/null +++ b/src/main/java/com/amazon/carbonado/filter/FilterParser.java @@ -0,0 +1,316 @@ +/* + * Copyright 2006 Amazon Technologies, Inc. or its affiliates. + * Amazon, Amazon.com and Carbonado are trademarks or registered trademarks + * of Amazon Technologies, Inc. or its affiliates. All rights reserved. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package com.amazon.carbonado.filter; + +import java.util.ArrayList; +import java.util.List; +import java.util.Map; + +import com.amazon.carbonado.Storable; +import com.amazon.carbonado.MalformedFilterException; + +import com.amazon.carbonado.info.ChainedProperty; +import com.amazon.carbonado.info.StorableInfo; +import com.amazon.carbonado.info.StorableIntrospector; +import com.amazon.carbonado.info.StorableProperty; + +/** + * + * + * @author Brian S O'Neill + */ +class FilterParser { + private final Class mType; + private final String mFilter; + private int mPos; + + FilterParser(Class type, String filter) { + if (type == null) { + throw new IllegalArgumentException(); + } + if (filter == null) { + throw new IllegalArgumentException("Query filter must not be null"); + } + mType = type; + mFilter = filter; + } + + // Design note: This parser is actually a scanner, parser, and type checker + // all rolled into one. This is okay since the grammar is so simple. + + Filter parseRoot() { + Filter filter = parseFilter(); + int c = nextCharIgnoreWhitespace(); + if (c >= 0) { + mPos--; + throw error("Unexpected trailing characters"); + } + return filter; + } + + private Filter parseFilter() { + return parseOrFilter(); + } + + private Filter parseOrFilter() { + Filter filter = parseAndFilter(); + while (true) { + int c = nextCharIgnoreWhitespace(); + if (c == '|') { + operatorCheck(); + filter = filter.or(parseAndFilter()); + } else { + mPos--; + break; + } + } + return filter; + } + + private Filter parseAndFilter() { + Filter filter = parseNotFilter(); + while (true) { + int c = nextCharIgnoreWhitespace(); + if (c == '&') { + operatorCheck(); + filter = filter.and(parseNotFilter()); + } else { + mPos--; + break; + } + } + return filter; + } + + private Filter parseNotFilter() { + int c = nextCharIgnoreWhitespace(); + if (c == '!') { + return parseEntityFilter().not(); + } else { + mPos--; + return parseEntityFilter(); + } + } + + private Filter parseEntityFilter() { + int c = nextCharIgnoreWhitespace(); + if (c == '(') { + Filter test = parseFilter(); + c = nextCharIgnoreWhitespace(); + if (c != ')') { + mPos--; + throw error("Right paren expected"); + } + return test; + } else { + mPos--; + return parsePropertyFilter(); + } + } + + private PropertyFilter parsePropertyFilter() { + ChainedProperty chained = parseChainedProperty(); + int c = nextCharIgnoreWhitespace(); + + RelOp op; + switch (c) { + case '=': + op = RelOp.EQ; + operatorCheck(); + break; + case '!': + c = nextChar(); + if (c == '=') { + op = RelOp.NE; + } else { + mPos--; + throw error("Inequality operator must be specified as '!='"); + } + operatorCheck(); + break; + case '<': + c = nextChar(); + if (c == '=') { + op = RelOp.LE; + } else { + mPos--; + op = RelOp.LT; + } + operatorCheck(); + break; + case '>': + c = nextChar(); + if (c == '=') { + op = RelOp.GE; + } else { + mPos--; + op = RelOp.GT; + } + operatorCheck(); + break; + case '?': case ':': + mPos--; + throw error("Relational operator missing"); + case -1: + throw error("Relational operator expected"); + default: + mPos--; + throw error("Unexpected operator character: '" + (char)c + '\''); + } + + c = nextCharIgnoreWhitespace(); + + if (c != '?') { + mPos--; + throw error("Parameter placeholder '?' required"); + } + + return PropertyFilter.getCanonical(chained, op, 0); + } + + private void operatorCheck() { + int c = nextChar(); + mPos--; + switch (c) { + case -1: + case '?': case ':': + case '(': case ')': + case ' ': case '\r': case '\n': case '\t': case '\0': + return; + default: + if (Character.isWhitespace(c)) { + return; + } + } + if (!Character.isJavaIdentifierStart(c)) { + throw error("Unknown operator"); + } + } + + @SuppressWarnings("unchecked") + ChainedProperty parseChainedProperty() { + String ident = parseIdentifier(); + StorableProperty prime = + StorableIntrospector.examine(mType).getAllProperties().get(ident); + if (prime == null) { + mPos -= ident.length(); + throw error("Property \"" + ident + "\" not found for type: \"" + + mType.getName() + '"'); + } + + if (nextCharIgnoreWhitespace() != '.') { + mPos--; + return ChainedProperty.get(prime); + } + + List> chain = new ArrayList>(4); + Class type = prime.isJoin() ? prime.getJoinedType() : prime.getType(); + + while (true) { + ident = parseIdentifier(); + if (Storable.class.isAssignableFrom(type)) { + StorableInfo info = + StorableIntrospector.examine((Class) type); + Map> props = info.getAllProperties(); + StorableProperty prop = props.get(ident); + if (prop == null) { + mPos -= ident.length(); + throw error("Property \"" + ident + "\" not found for type: \"" + + type.getName() + '"'); + } + chain.add(prop); + type = prop.isJoin() ? prop.getJoinedType() : prop.getType(); + } else { + throw error("Property \"" + ident + "\" not found for type \"" + + type.getName() + "\" because type has no properties"); + } + if (nextCharIgnoreWhitespace() != '.') { + mPos--; + break; + } + } + + return ChainedProperty.get(prime, (StorableProperty[]) chain.toArray(new StorableProperty[chain.size()])); + } + + private String parseIdentifier() { + int start = mPos; + int c = nextChar(); + if (c < 0) { + throw error("Identifier expected"); + } + if (!Character.isJavaIdentifierStart(c)) { + mPos--; + throw error("Not a valid character for start of identifier: '" + (char)c + '\''); + } + do { + c = nextChar(); + } while (Character.isJavaIdentifierPart(c)); + + return mFilter.substring(start, --mPos); + } + + /** + * Returns -1 if no more characters. + */ + private int nextChar() { + String filter = mFilter; + int pos = mPos; + int c = (pos >= filter.length()) ? -1 : mFilter.charAt(pos); + mPos = pos + 1; + return c; + } + + private int nextCharIgnoreWhitespace() { + int c; + while ((c = nextChar()) >= 0) { + switch (c) { + case ' ': case '\r': case '\n': case '\t': case '\0': + break; + default: + if (Character.isWhitespace(c)) { + break; + } + return c; + } + } + return c; + } + + private MalformedFilterException error(String message) { + return error(message, mPos); + } + + private MalformedFilterException error(String message, int pos) { + if (pos <= 0 || mFilter.length() == 0) { + message += " (at start of filter expession)"; + } else if (pos >= mFilter.length()) { + message += " (at end of filter expression)"; + } else { + // Show the next 20 characters, or show 17 + ellipsis if more than 20. + int remaining = mFilter.length() - pos; + if (remaining <= 20) { + message = message + " (at \"" + mFilter.substring(pos) + "\")"; + } else { + message = message + " (at \"" + mFilter.substring(pos, pos + 17) + "...\")"; + } + } + return new MalformedFilterException(mFilter, message, pos); + } +} diff --git a/src/main/java/com/amazon/carbonado/filter/FilterValues.java b/src/main/java/com/amazon/carbonado/filter/FilterValues.java new file mode 100644 index 0000000..162194c --- /dev/null +++ b/src/main/java/com/amazon/carbonado/filter/FilterValues.java @@ -0,0 +1,623 @@ +/* + * Copyright 2006 Amazon Technologies, Inc. or its affiliates. + * Amazon, Amazon.com and Carbonado are trademarks or registered trademarks + * of Amazon Technologies, Inc. or its affiliates. All rights reserved. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package com.amazon.carbonado.filter; + +import java.io.IOException; +import java.util.IdentityHashMap; +import java.util.Map; + +import com.amazon.carbonado.Storable; +import com.amazon.carbonado.util.Appender; + +/** + * Assigns values to {@link Filter} placeholders. FilterValues instances are + * immutable. + * + * @author Brian S O'Neill + */ +public class FilterValues implements Appender { + private static final Object[] NO_VALUES = new Object[0]; + + static FilterValues + create(Filter filter, PropertyFilterList propFilterList) + { + return create(filter, propFilterList, null, null); + } + + private static FilterValues + create(Filter filter, PropertyFilterList propFilterList, + FilterValues prevValues, Object prevValue) + { + FilterValues fv = new FilterValues(filter, propFilterList, prevValues, prevValue); + PropertyFilter propFilter; + while (propFilterList != null + && (propFilter = propFilterList.getPropertyFilter()).isConstant()) + { + propFilterList = propFilterList.getNext(); + fv = new FilterValues(filter, propFilterList, fv, propFilter.constant()); + } + return fv; + } + + private final Filter mFilter; + private final PropertyFilterList mCurrentProperty; + private final FilterValues mPrevValues; + private final Object mPrevValue; + + private transient volatile Map, Object> mValueMap; + + private FilterValues(Filter filter, + PropertyFilterList propFilterList, + FilterValues prevValues, + Object prevValue) + { + mFilter = filter; + mCurrentProperty = propFilterList; + mPrevValues = prevValues; + mPrevValue = prevValue; + } + + /** + * Returns the Filter that this FilterValues instance applies to. + */ + public Filter getFilter() { + return mFilter; + } + + /** + * Returns a new FilterValues instance with the next blank parameter filled in. + * + * @param value parameter value to fill in + * @throws IllegalStateException if no blank parameters + * @throws IllegalArgumentException if type doesn't match + */ + public FilterValues with(int value) { + PropertyFilterList current = currentProperty(); + Object obj; + try { + obj = current.getPropertyFilter().adaptValue(value); + } catch (IllegalArgumentException e) { + throw mismatch(int.class, value); + } + return with(current, obj); + } + + /** + * Returns a new FilterValues instance with the next blank parameter filled in. + * + * @param value parameter value to fill in + * @throws IllegalStateException if no blank parameters + * @throws IllegalArgumentException if type doesn't match + */ + public FilterValues with(long value) { + PropertyFilterList current = currentProperty(); + Object obj; + try { + obj = current.getPropertyFilter().adaptValue(value); + } catch (IllegalArgumentException e) { + throw mismatch(long.class, value); + } + return with(current, obj); + } + + /** + * Returns a new FilterValues instance with the next blank parameter filled in. + * + * @param value parameter value to fill in + * @throws IllegalStateException if no blank parameters + * @throws IllegalArgumentException if type doesn't match + */ + public FilterValues with(float value) { + PropertyFilterList current = currentProperty(); + Object obj; + try { + obj = current.getPropertyFilter().adaptValue(value); + } catch (IllegalArgumentException e) { + throw mismatch(float.class, value); + } + return with(current, obj); + } + + /** + * Returns a new FilterValues instance with the next blank parameter filled in. + * + * @param value parameter value to fill in + * @throws IllegalStateException if no blank parameters + * @throws IllegalArgumentException if type doesn't match + */ + public FilterValues with(double value) { + PropertyFilterList current = currentProperty(); + Object obj; + try { + obj = current.getPropertyFilter().adaptValue(value); + } catch (IllegalArgumentException e) { + throw mismatch(double.class, value); + } + return with(current, obj); + } + + /** + * Returns a new FilterValues instance with the next blank parameter filled in. + * + * @param value parameter value to fill in + * @throws IllegalStateException if no blank parameters + * @throws IllegalArgumentException if type doesn't match + */ + public FilterValues with(boolean value) { + PropertyFilterList current = currentProperty(); + Object obj; + try { + obj = current.getPropertyFilter().adaptValue(value); + } catch (IllegalArgumentException e) { + throw mismatch(boolean.class, value); + } + return with(current, obj); + } + + /** + * Returns a new FilterValues instance with the next blank parameter filled in. + * + * @param value parameter value to fill in + * @throws IllegalStateException if no blank parameters + * @throws IllegalArgumentException if type doesn't match + */ + public FilterValues with(char value) { + PropertyFilterList current = currentProperty(); + Object obj; + try { + obj = current.getPropertyFilter().adaptValue(value); + } catch (IllegalArgumentException e) { + throw mismatch(char.class, value); + } + return with(current, obj); + } + + /** + * Returns a new FilterValues instance with the next blank parameter filled in. + * + * @param value parameter value to fill in + * @throws IllegalStateException if no blank parameters + * @throws IllegalArgumentException if type doesn't match + */ + public FilterValues with(byte value) { + PropertyFilterList current = currentProperty(); + Object obj; + try { + obj = current.getPropertyFilter().adaptValue(value); + } catch (IllegalArgumentException e) { + throw mismatch(byte.class, value); + } + return with(current, obj); + } + + /** + * Returns a new FilterValues instance with the next blank parameter filled in. + * + * @param value parameter value to fill in + * @throws IllegalStateException if no blank parameters + * @throws IllegalArgumentException if type doesn't match + */ + public FilterValues with(short value) { + PropertyFilterList current = currentProperty(); + Object obj; + try { + obj = current.getPropertyFilter().adaptValue(value); + } catch (IllegalArgumentException e) { + throw mismatch(short.class, value); + } + return with(current, obj); + } + + /** + * Returns a new FilterValues instance with the next blank parameter filled in. + * + * @param value parameter value to fill in + * @throws IllegalStateException if no blank parameters + * @throws IllegalArgumentException if type doesn't match + */ + public FilterValues with(Object value) { + PropertyFilterList current = currentProperty(); + Object obj; + try { + obj = current.getPropertyFilter().adaptValue(value); + } catch (IllegalArgumentException e) { + throw mismatch(value == null ? null : value.getClass(), value); + } + return with(current, obj); + } + + /** + * Returns a new FilterValues instance with the next blank parameters filled in. + * + * @param values parameter values to fill in; if null or empty, this + * FilterValues instance is returned + * @throws IllegalStateException if no blank parameters or if too many + * parameter values supplied + * @throws IllegalArgumentException if type doesn't match + */ + public FilterValues withValues(Object... values) { + if (values == null) { + return this; + } + if (values.length > getBlankParameterCount()) { + throw new IllegalStateException("Too many values supplied"); + } + FilterValues filterValues = this; + for (Object value : values) { + filterValues = filterValues.with(value); + } + return filterValues; + } + + private FilterValues with(PropertyFilterList current, Object value) { + return create(mFilter, current.getNext(), this, value); + } + + /** + * Returns the amount of values yet to be assigned. + * + */ + public int getBlankParameterCount() { + return mCurrentProperty == null ? 0 : (mCurrentProperty.getNextBlankRemaining() + 1); + } + + /** + * Returns the value assigned to the given PropertyFilter. If null, value + * may be unassigned. Call getAssignedValue to have an exception thrown + * instead. + */ + public Object getValue(PropertyFilter propFilter) { + return getValue(propFilter, false); + } + + /** + * Returns the value assigned to the given PropertyFilter, throwing an + * exception if not assigned. Call getValue to have null returned instead. + * + * @throws IllegalStateException if value is blank + */ + public Object getAssignedValue(PropertyFilter propFilter) throws IllegalStateException { + return getValue(propFilter, true); + } + + private Object getValue(PropertyFilter propFilter, boolean mustBeAssigned) { + if (propFilter.isConstant()) { + return propFilter.constant(); + } + + Map, Object> map = mValueMap; + + if (map == null) { + FilterValues prevValues = mPrevValues; + if (prevValues == null) { + if (mustBeAssigned) { + throw valueNotFound(propFilter); + } + return null; + } + + if (prevValues.mCurrentProperty.getPreviousRemaining() < 3) { + // Map would have few values in it, so don't bother building it. + + FilterValues filterValues = this; + do { + if (propFilter == prevValues.mCurrentProperty.getPropertyFilter()) { + return filterValues.mPrevValue; + } + filterValues = prevValues; + prevValues = prevValues.mPrevValues; + } while (prevValues != null); + + if (mustBeAssigned) { + throw valueNotFound(propFilter); + } + return null; + } + + map = buildValueMap(); + } + + Object value = map.get(propFilter); + if (value == null && mustBeAssigned && !map.containsKey(propFilter)) { + throw valueNotFound(propFilter); + } + + return value; + } + + /** + * Returns true if a value is assigned to the given PropertyFilter. + */ + public boolean isAssigned(PropertyFilter propFilter) { + if (propFilter.isConstant()) { + return true; + } + + Map, Object> map = mValueMap; + + if (map == null) { + FilterValues prevValues = mPrevValues; + if (prevValues == null) { + return false; + } + + if (prevValues.mCurrentProperty.getPreviousRemaining() < 3) { + // Map would have few values in it, so don't bother building it. + + do { + if (propFilter == prevValues.mCurrentProperty.getPropertyFilter()) { + return true; + } + prevValues = prevValues.mPrevValues; + } while (prevValues != null); + + return false; + } + + map = buildValueMap(); + } + + return map.containsKey(propFilter); + } + + private Map, Object> buildValueMap() { + Map, Object> map = + new IdentityHashMap, Object>(); + + FilterValues filterValues = this; + FilterValues prevValues = mPrevValues; + + do { + map.put(prevValues.mCurrentProperty.getPropertyFilter(), filterValues.mPrevValue); + filterValues = prevValues; + prevValues = prevValues.mPrevValues; + } while (prevValues != null); + + mValueMap = map; + return map; + } + + /** + * Returns all values in this object, including those provided by filter + * constants. An IllegalStateException will result if any values are blank. + * + * @return new object array + * @throws IllegalStateException if any values are blank + */ + public Object[] getValues() throws IllegalStateException { + return getValuesFor(mFilter); + } + + /** + * Returns all supplied values in this object. Constant filter values are + * not included. + * + * @return new object array + */ + public Object[] getSuppliedValues() { + FilterValues prevValues = mPrevValues; + if (prevValues == null) { + return NO_VALUES; + } + + int i = prevValues.mCurrentProperty.getBlankCount(); + if (i == 0) { + return NO_VALUES; + } + Object[] values = new Object[i]; + FilterValues filterValues = this; + + while (true) { + if (!filterValues.mPrevValues.mCurrentProperty.getPropertyFilter().isConstant()) { + values[--i] = filterValues.mPrevValue; + if (i <= 0) { + break; + } + } + filterValues = prevValues; + prevValues = prevValues.mPrevValues; + } + + return values; + } + + /** + * Returns all values in this object, as required by the given Filter. The + * given Filter must be composed only of the same PropertyFilter instances + * as used to construct this object. An IllegalStateException will result + * otherwise. + * + * @return new object array + * @throws IllegalStateException if any values are blank + */ + public Object[] getValuesFor(Filter filter) throws IllegalStateException { + // Traverse filter properties in reverse, since the filter likely was + // used to create this FilterValues instance. If so, then no value map + // needs to be constructed. + PropertyFilterList list = filter.getTailPropertyFilterList(); + if (list == null) { + return NO_VALUES; + } + + int i = list.getPreviousRemaining() + 1; + Object[] values = new Object[i]; + + FilterValues filterValues = this; + FilterValues prevValues = mPrevValues; + + for (; --i >= 0; list = list.getPrevious()) { + PropertyFilter propFilter = list.getPropertyFilter(); + + Object value; + + if (prevValues != null + && propFilter == prevValues.mCurrentProperty.getPropertyFilter()) { + + value = filterValues.mPrevValue; + + filterValues = prevValues; + prevValues = prevValues.mPrevValues; + } else { + if (i > 0 || mValueMap != null) { + value = getAssignedValue(propFilter); + } else { + // No need to force value map to be created since this is + // the last property to be processed. Do the same scan operation + // as performed by buildValueMap, except don't save the results. + + filterValues = this; + prevValues = mPrevValues; + + findValue: { + while (prevValues != null) { + if (propFilter == prevValues.mCurrentProperty.getPropertyFilter()) { + value = filterValues.mPrevValue; + break findValue; + } + filterValues = prevValues; + prevValues = prevValues.mPrevValues; + } + + throw valueNotFound(propFilter); + } + } + } + + values[i] = value; + } + + return values; + } + + private IllegalStateException valueNotFound(PropertyFilter propFilter) { + return new IllegalStateException + ("Property value not found for: \"" + propFilter + "\" in filter \"" + this + '"'); + } + + @Override + public int hashCode() { + int hash = mFilter.hashCode(); + if (mPrevValue != null) { + hash += mPrevValue.hashCode(); + } + if (mPrevValues != null) { + hash += mPrevValues.hashCode(); + } + return hash; + } + + @Override + public boolean equals(Object obj) { + if (this == obj) { + return true; + } + if (obj instanceof FilterValues) { + FilterValues other = (FilterValues) obj; + return mFilter.equals(other.mFilter) + && mCurrentProperty == other.mCurrentProperty + && (mPrevValues == null ? other.mPrevValues == null + : mPrevValues.equals(other.mPrevValues)) + && (mPrevValue == null ? other.mPrevValue == null + : mPrevValue.equals(other.mPrevValue)); + } + return false; + } + + /** + * Returns the string value of the filter with any values substituted. + */ + @Override + public String toString() { + StringBuilder buf = new StringBuilder(); + try { + appendTo(buf); + } catch (java.io.IOException e) { + // Not gonna happen. + } + return buf.toString(); + } + + public void appendTo(Appendable app) throws IOException { + mFilter.appendTo(app, this); + } + + private PropertyFilterList currentProperty() { + PropertyFilterList current = mCurrentProperty; + if (current == null) { + throw new IllegalStateException("No blank parameters"); + } + return current; + } + + private IllegalArgumentException mismatch(Class actualType, Object actualValue) { + PropertyFilterList current = currentProperty(); + PropertyFilter propFilter = current.getPropertyFilter(); + + StringBuilder b = new StringBuilder(); + + try { + propFilter.appendMismatchMessage(b, actualType, actualValue); + } catch (IOException e) { + // Not gonna happen + } + + int subFilterCount = current.getPreviousRemaining() + current.getNextRemaining() + 1; + + if (subFilterCount <= 1) { + b.append(" for filter \""); + b.append(propFilter); + b.append('"'); + } else { + b.append(" for "); + appendOrdinal(b, current.getPreviousRemaining() + 1); + b.append(" sub filter in \""); + try { + appendTo(b); + } catch (IOException e) { + // Not gonna happen + } + b.append('"'); + } + + return new IllegalArgumentException(b.toString()); + } + + private void appendOrdinal(StringBuilder b, int value) { + b.append(value); + + if (value != 11 && value != 12 && value != 13) { + value = value % 10; + switch (value) { + default: + break; + case 1: + b.append("st"); + return; + case 2: + b.append("nd"); + return; + case 3: + b.append("rd"); + return; + } + } + + b.append("th"); + } +} diff --git a/src/main/java/com/amazon/carbonado/filter/Group.java b/src/main/java/com/amazon/carbonado/filter/Group.java new file mode 100644 index 0000000..6805bf4 --- /dev/null +++ b/src/main/java/com/amazon/carbonado/filter/Group.java @@ -0,0 +1,134 @@ +/* + * Copyright 2006 Amazon Technologies, Inc. or its affiliates. + * Amazon, Amazon.com and Carbonado are trademarks or registered trademarks + * of Amazon Technologies, Inc. or its affiliates. All rights reserved. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package com.amazon.carbonado.filter; + +import java.util.Iterator; +import java.util.LinkedHashSet; +import java.util.Set; + +import com.amazon.carbonado.Storable; + +/** + * Group of filter nodes that are all 'or'ed or 'and'ed together. + * + * @author Brian S O'Neill + */ +class Group { + final boolean mForAnd; + Set> mChildren; + + Group(boolean forAnd) { + mForAnd = forAnd; + } + + boolean add(Filter child) { + if (mChildren == null) { + mChildren = new LinkedHashSet>(20); + } + return mChildren.add(child); + } + + /** + * Reduce the group set by eliminating redundant children. The + * transformations applied are: + * + * ((a & b) | b) => b + * ((a | b) & b) => b + */ + void reduce() { + Iterator> it = mChildren.iterator(); + aLoop: + while (it.hasNext()) { + Filter a = it.next(); + for (Filter b : mChildren) { + if (a != b) { + if (a.accept(new Scanner(!mForAnd), b)) { + it.remove(); + continue aLoop; + } + } + } + } + } + + Filter merge() { + Filter filter = null; + if (mChildren != null) { + for (Filter child : mChildren) { + if (filter == null) { + filter = child; + } else if (mForAnd) { + filter = filter.and(child); + } else { + filter = filter.or(child); + } + } + } + return filter; + } + + /** + * Does the work of reducing a group + */ + private static class Scanner extends Visitor>{ + private final boolean mForAnd; + + Scanner(boolean forAnd) { + mForAnd = forAnd; + } + + /** + * @return TRUE if overlap was found + */ + @Override + public Boolean visit(OrFilter filter, Filter child) { + if (mForAnd) { + return false; + } + if (filter == child) { + return true; + } + return filter.getLeftFilter().accept(this, child) || + filter.getRightFilter().accept(this, child); + } + + /** + * @return TRUE if overlap was found + */ + @Override + public Boolean visit(AndFilter filter, Filter child) { + if (!mForAnd) { + return false; + } + if (filter == child) { + return true; + } + return filter.getLeftFilter().accept(this, child) || + filter.getRightFilter().accept(this, child); + } + + /** + * @return TRUE if overlap was found + */ + @Override + public Boolean visit(PropertyFilter filter, Filter child) { + return filter == child; + } + } +} diff --git a/src/main/java/com/amazon/carbonado/filter/OpenFilter.java b/src/main/java/com/amazon/carbonado/filter/OpenFilter.java new file mode 100644 index 0000000..407aed0 --- /dev/null +++ b/src/main/java/com/amazon/carbonado/filter/OpenFilter.java @@ -0,0 +1,127 @@ +/* + * Copyright 2006 Amazon Technologies, Inc. or its affiliates. + * Amazon, Amazon.com and Carbonado are trademarks or registered trademarks + * of Amazon Technologies, Inc. or its affiliates. All rights reserved. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package com.amazon.carbonado.filter; + +import java.io.IOException; + +import com.amazon.carbonado.Storable; + +/** + * Filter which lets all results pass through. + * + * @author Brian S O'Neill + */ +public class OpenFilter extends Filter { + OpenFilter(Class type) { + super(type); + } + + public Filter and(Filter filter) { + return filter; + } + + public Filter or(Filter filter) { + return this; + } + + public Filter not() { + return getClosedFilter(getStorableType()); + } + + @Override + public FilterValues initialFilterValues() { + return null; + } + + @Override + PropertyFilterList getTailPropertyFilterList() { + return null; + } + + public R accept(Visitor visitor, P param) { + return visitor.visit(this, param); + } + + public Filter bind() { + return this; + } + + public boolean isBound() { + return true; + } + + void markBound() { + } + + Filter buildDisjunctiveNormalForm() { + return this; + } + + Filter buildConjunctiveNormalForm() { + return this; + } + + boolean isDisjunctiveNormalForm() { + return true; + } + + boolean isConjunctiveNormalForm() { + return true; + } + + boolean isReduced() { + return true; + } + + void markReduced() { + } + + @Override + public int hashCode() { + return getStorableType().hashCode(); + } + + @Override + public boolean equals(Object obj) { + if (this == obj) { + return true; + } + if (obj instanceof OpenFilter) { + OpenFilter other = (OpenFilter) obj; + return getStorableType() == other.getStorableType(); + } + return false; + } + + @Override + public String toString() { + return "open"; + } + + public void appendTo(Appendable app, FilterValues values) throws IOException { + app.append("open"); + } + + void dumpTree(Appendable app, int indentLevel) throws IOException { + for (int i=0; i extends BinaryOpFilter { + /** + * Returns a canonical instance. + * + * @throws IllegalArgumentException if either filter is null + */ + @SuppressWarnings("unchecked") + static OrFilter getCanonical(Filter left, Filter right) { + return (OrFilter) cCanonical.put(new OrFilter(left, right)); + } + + /** + * @throws IllegalArgumentException if either filter is null + */ + private OrFilter(Filter left, Filter right) { + super(left, right); + } + + public Filter not() { + return mLeft.not().and(mRight.not()); + } + + public R accept(Visitor visitor, P param) { + return visitor.visit(this, param); + } + + Filter buildDisjunctiveNormalForm() { + return mLeft.dnf().or(mRight.dnf()).reduce(); + } + + Filter buildConjunctiveNormalForm() { + Filter left = mLeft.reduce().cnf(); + Filter right = mRight.reduce().cnf(); + if (left instanceof AndFilter) { + return left.accept(new Distributer(true, false), right).reduce().cnf(); + } + if (right instanceof AndFilter) { + return right.accept(new Distributer(false, false), left).reduce().cnf(); + } + return left.or(right).reduce(); + } + + boolean checkIsDisjunctiveNormalForm() { + return mLeft.isDisjunctiveNormalForm() && mRight.isDisjunctiveNormalForm(); + } + + boolean checkIsConjunctiveNormalForm() { + return (!(mLeft instanceof AndFilter)) + && (!(mRight instanceof AndFilter)) + && mLeft.isConjunctiveNormalForm() + && mRight.isConjunctiveNormalForm(); + } + + @Override + public int hashCode() { + return mLeft.hashCode() * 31 + mRight.hashCode(); + } + + @Override + public boolean equals(Object obj) { + if (this == obj) { + return true; + } + if (obj instanceof OrFilter) { + OrFilter other = (OrFilter) obj; + return getStorableType() == other.getStorableType() + && mLeft.equals(other.mLeft) && mRight.equals(other.mRight); + } + return false; + } + + public void appendTo(Appendable app, FilterValues values) throws IOException { + if (mLeft instanceof AndFilter) { + app.append('('); + mLeft.appendTo(app, values); + app.append(')'); + } else { + mLeft.appendTo(app, values); + } + app.append(" | "); + if (mRight instanceof AndFilter) { + app.append('('); + mRight.appendTo(app, values); + app.append(')'); + } else { + mRight.appendTo(app, values); + } + } + + void dumpTree(Appendable app, int indentLevel) throws IOException { + mRight.dumpTree(app, indentLevel + 1); + for (int i=0; i extends Filter { + // Indicates property has been bound to a constant value. + private static int BOUND_CONSTANT = -1; + + /** + * Returns a canonical instance, creating a new one if there isn't one + * already in the cache. + * + * @throws IllegalArgumentException if property or operator is null + */ + @SuppressWarnings("unchecked") + static PropertyFilter getCanonical(ChainedProperty property, + RelOp op, + int bindID) + { + return (PropertyFilter) cCanonical + .put(new PropertyFilter(property, op, bindID, null)); + } + + /** + * Returns a canonical instance, creating a new one if there isn't one + * already in the cache. + * + * @throws IllegalArgumentException if property or operator is null + */ + @SuppressWarnings("unchecked") + static PropertyFilter getCanonical(ChainedProperty property, + RelOp op, + Object constant) + { + return (PropertyFilter) cCanonical + .put(new PropertyFilter(property, op, BOUND_CONSTANT, constant)); + } + + /** + * Returns a canonical instance, creating a new one if there isn't one + * already in the cache. + */ + @SuppressWarnings("unchecked") + static PropertyFilter getCanonical(PropertyFilter filter, + int bindID) + { + if (filter.mBindID == bindID) { + return filter; + } + return (PropertyFilter) cCanonical + .put(new PropertyFilter(filter.getChainedProperty(), + filter.getOperator(), bindID, filter.mConstant)); + } + + private final ChainedProperty mProperty; + private final RelOp mOp; + + private final int mBindID; + + private final Object mConstant; + + private transient volatile Class mBoxedType; + + /** + * @throws IllegalArgumentException if property or operator is null + */ + private PropertyFilter(ChainedProperty property, RelOp op, int bindID, Object constant) { + super(property == null ? null : property.getPrimeProperty().getEnclosingType()); + if (op == null) { + throw new IllegalArgumentException(); + } + mProperty = property; + mOp = op; + mBindID = bindID; + mConstant = constant; + } + + @Override + public Filter not() { + if (mBindID == BOUND_CONSTANT) { + return getCanonical(mProperty, mOp.reverse(), mConstant); + } else { + return getCanonical(mProperty, mOp.reverse(), mBindID); + } + } + + public R accept(Visitor visitor, P param) { + return visitor.visit(this, param); + } + + public ChainedProperty getChainedProperty() { + return mProperty; + } + + /** + * Returns the type of the ChainedProperty. + */ + public Class getType() { + return mProperty.getType(); + } + + /** + * Returns the type of the ChainedProperty property, boxed into an object + * if primitive. + */ + public Class getBoxedType() { + if (mBoxedType == null) { + mBoxedType = TypeDesc.forClass(getType()).toObjectType().toClass(); + } + return mBoxedType; + } + + public RelOp getOperator() { + return mOp; + } + + /** + * Bind ID is used to distinguish this PropertyFilter instance from another + * against the same property. For example, the filter "a = ? | a = ?" + * references the property 'a' twice. Each '?' parameter is bound to a + * different value, and so the bind ID for each property filter is + * different. "a = ?[1] | a = ?[2]". + * + * @return assigned bind ID, or 0 if unbound + */ + public int getBindID() { + return mBindID; + } + + public Filter bind() { + return mBindID == 0 ? getCanonical(this, 1) : this; + } + + public boolean isBound() { + return mBindID != 0; + } + + /** + * Returns another PropertyFilter instance which is bound to the given constant value. + * + * @throws IllegalArgumentException if value is not compatible with property type + */ + public PropertyFilter constant(Object value) { + if (mBindID == BOUND_CONSTANT) { + if (mConstant == null && value == null || mConstant.equals(value)) { + return this; + } + } + return getCanonical(mProperty, mOp, adaptValue(value)); + } + + /** + * Returns the constant value of this PropertyFilter, which is valid only + * if isConstant returns true. + */ + public Object constant() { + return mConstant; + } + + /** + * Returns true if this PropertyFilter has a constant value. + */ + public boolean isConstant() { + return mBindID == BOUND_CONSTANT; + } + + void markBound() { + } + + Filter buildDisjunctiveNormalForm() { + return this; + } + + Filter buildConjunctiveNormalForm() { + return this; + } + + boolean isDisjunctiveNormalForm() { + return true; + } + + boolean isConjunctiveNormalForm() { + return true; + } + + boolean isReduced() { + return true; + } + + void markReduced() { + } + + /** + * @throws IllegalArgumentException if type doesn't match + */ + Object adaptValue(int value) { + Class type = getBoxedType(); + if (type == Integer.class) { + return Integer.valueOf(value); + } else if (type == Long.class) { + return Long.valueOf(value); + } else if (type == Double.class) { + return Double.valueOf(value); + } else if (type == Number.class || type == Object.class) { + return Integer.valueOf(value); + } + throw mismatch(int.class, value); + } + + /** + * @throws IllegalArgumentException if type doesn't match + */ + Object adaptValue(long value) { + Class type = getBoxedType(); + if (type == Long.class) { + return Long.valueOf(value); + } else if (type == Number.class || type == Object.class) { + return Long.valueOf(value); + } + throw mismatch(long.class, value); + } + + /** + * @throws IllegalArgumentException if type doesn't match + */ + Object adaptValue(float value) { + Class type = getBoxedType(); + if (type == Float.class) { + return Float.valueOf(value); + } else if (type == Double.class) { + return Double.valueOf(value); + } else if (type == Number.class || type == Object.class) { + return Float.valueOf(value); + } + throw mismatch(float.class, value); + } + + /** + * @throws IllegalArgumentException if type doesn't match + */ + Object adaptValue(double value) { + Class type = getBoxedType(); + if (type == Double.class) { + return Double.valueOf(value); + } else if (type == Number.class || type == Object.class) { + return Double.valueOf(value); + } + throw mismatch(float.class, value); + } + + /** + * @throws IllegalArgumentException if type doesn't match + */ + Object adaptValue(boolean value) { + Class type = getBoxedType(); + if (type == Boolean.class || type == Object.class) { + return Boolean.valueOf(value); + } + throw mismatch(boolean.class, value); + } + + /** + * @throws IllegalArgumentException if type doesn't match + */ + Object adaptValue(char value) { + Class type = getBoxedType(); + if (type == Character.class || type == Object.class) { + return Character.valueOf(value); + } else if (type == String.class || type == CharSequence.class) { + return String.valueOf(value); + } + throw mismatch(char.class, value); + } + + /** + * @throws IllegalArgumentException if type doesn't match + */ + Object adaptValue(byte value) { + Class type = getBoxedType(); + if (type == Byte.class) { + return Byte.valueOf(value); + } else if (type == Short.class) { + return Short.valueOf(value); + } else if (type == Integer.class) { + return Integer.valueOf(value); + } else if (type == Long.class) { + return Long.valueOf(value); + } else if (type == Double.class) { + return Double.valueOf(value); + } else if (type == Float.class) { + return Float.valueOf(value); + } else if (type == Number.class || type == Object.class) { + return Byte.valueOf(value); + } + throw mismatch(byte.class, value); + } + + /** + * @throws IllegalArgumentException if type doesn't match + */ + Object adaptValue(short value) { + Class type = getBoxedType(); + if (type == Short.class) { + return Short.valueOf(value); + } else if (type == Integer.class) { + return Integer.valueOf(value); + } else if (type == Long.class) { + return Long.valueOf(value); + } else if (type == Double.class) { + return Double.valueOf(value); + } else if (type == Float.class) { + return Float.valueOf(value); + } else if (type == Number.class || type == Object.class) { + return Short.valueOf(value); + } + throw mismatch(short.class, value); + } + + /** + * @throws IllegalArgumentException if type doesn't match + */ + Object adaptValue(Object value) { + if (getBoxedType().isInstance(value)) { + return value; + } + + Class type = getType(); + + if (value == null) { + if (!type.isPrimitive()) { + return value; + } + } else if (type.isPrimitive()) { + TypeDesc actualPrim = TypeDesc.forClass(value.getClass()).toPrimitiveType(); + if (actualPrim != null) { + if (type == actualPrim.toClass()) { + return value; + } + // Unbox and rebox. + switch (actualPrim.getTypeCode()) { + case TypeDesc.BYTE_CODE: + return adaptValue(((Number) value).byteValue()); + case TypeDesc.SHORT_CODE: + return adaptValue(((Number) value).shortValue()); + case TypeDesc.INT_CODE: + return adaptValue(((Number) value).intValue()); + case TypeDesc.LONG_CODE: + return adaptValue(((Number) value).longValue()); + case TypeDesc.FLOAT_CODE: + return adaptValue(((Number) value).floatValue()); + case TypeDesc.DOUBLE_CODE: + return adaptValue(((Number) value).doubleValue()); + case TypeDesc.BOOLEAN_CODE: + return adaptValue(((Boolean) value).booleanValue()); + case TypeDesc.CHAR_CODE: + return adaptValue(((Character) value).charValue()); + } + } + } + + throw mismatch(value == null ? null : value.getClass(), value); + } + + @Override + public int hashCode() { + return mProperty.hashCode() * 31 + mOp.hashCode() + mBindID; + } + + @Override + public boolean equals(Object obj) { + if (this == obj) { + return true; + } + if (obj instanceof PropertyFilter) { + PropertyFilter other = (PropertyFilter) obj; + return getStorableType() == other.getStorableType() + && mProperty.equals(other.mProperty) && mOp.equals(other.mOp) + && mBindID == other.mBindID + && (mConstant == null + ? (other.mConstant == null) + : mConstant.equals(other.mConstant)); + } + return false; + } + + public void appendTo(Appendable app, FilterValues values) throws IOException { + mProperty.appendTo(app); + app.append(' '); + app.append(mOp.toString()); + app.append(' '); + if (values != null) { + Object value = values.getValue(this); + if (value != null || values.isAssigned(this)) { + app.append(String.valueOf(value)); + return; + } + } + if (mBindID == BOUND_CONSTANT) { + app.append(String.valueOf(mConstant)); + } else { + app.append('?'); + /* Uncomment for testing + if (mBindID != 0) { + app.append('[').append(String.valueOf(mBindID)).append(']'); + } + */ + } + } + + void appendMismatchMessage(Appendable a, Class actualType, Object actualValue) + throws IOException + { + if (actualType == null || actualValue == null) { + a.append("Actual value is null, which cannot be assigned to type \""); + } else { + a.append("Actual value \""); + a.append(String.valueOf(actualValue)); + a.append("\", of type \""); + a.append(TypeDesc.forClass(actualType).getFullName()); + a.append("\", is incompatible with expected type of \""); + } + a.append(TypeDesc.forClass(getType()).getFullName()); + a.append('"'); + } + + private IllegalArgumentException mismatch(Class actualType, Object actualValue) { + StringBuilder b = new StringBuilder(); + try { + appendMismatchMessage(b, actualType, actualValue); + } catch (IOException e) { + // Not gonna happen + } + return new IllegalArgumentException(b.toString()); + } + + void dumpTree(Appendable app, int indentLevel) throws IOException { + for (int i=0; i { + private final PropertyFilter mPropFilter; + private final PropertyFilterList mNext; + private final int mNextRemaining; + private final int mNextBlankRemaining; + + private PropertyFilterList mPrev; + private int mPrevRemaining = -1; + private int mBlankCount = -1; + + /** + * @param next pass null for tail of list + */ + PropertyFilterList(PropertyFilter propFilter, PropertyFilterList next) { + mPropFilter = propFilter; + mNext = next; + mNextRemaining = next == null ? 0 : next.mNextRemaining + 1; + mNextBlankRemaining = next == null ? 0 + : (next.mNextBlankRemaining + (next.mPropFilter.isConstant() ? 0 : 1)); + } + + public PropertyFilter getPropertyFilter() { + return mPropFilter; + } + + public Class getNaturalPropertyType() { + return mPropFilter.getType(); + } + + /** + * Returns the property filter type, always represented as an object + * type. Primitive types are represented by a wrapper class. + */ + public Class getObjectPropertyType() { + return mPropFilter.getBoxedType(); + } + + /** + * Returns null if the next remaining is zero. + */ + public PropertyFilterList getNext() { + return mNext; + } + + /** + * Returns the amount of next remaining list nodes. + */ + public int getNextRemaining() { + return mNextRemaining; + } + + /** + * Returns the amount of next remaining non-constant list nodes. + */ + public int getNextBlankRemaining() { + return mNextBlankRemaining; + } + + /** + * Returns null if no previous node. + */ + public PropertyFilterList getPrevious() { + return mPrev; + } + + /** + * Returns the amount of previous remaining list nodes. + */ + public int getPreviousRemaining() { + int remaining = mPrevRemaining; + if (remaining < 0) { + mPrevRemaining = remaining = + ((mPrev == null) ? 0 : (mPrev.getPreviousRemaining() + 1)); + } + return remaining; + } + + /** + * Returns the amount of non-constant list nodes up to this node. + */ + public int getBlankCount() { + int count = mBlankCount; + if (count < 0) { + mBlankCount = count = (mPropFilter.isConstant() ? 0 : 1) + + ((mPrev == null) ? 0 : mPrev.getBlankCount()); + } + return count; + } + + /** + * @param index if zero, returns this, if one, returns next, etc. If + * negative, gets from last. -1 returns last, -2 returns next to last, etc. + * @return null if index too high or too low + */ + public PropertyFilterList get(int index) { + if (index <= 0) { + if (index == 0) { + return this; + } + if ((index = mNextRemaining + index + 1) <= 0) { + if (index == 0) { + return this; + } + return null; + } + } + if (mNext == null) { + return null; + } + // Tail recursion. + return mNext.get(index - 1); + } + + /** + * Searches list for given PropertyFilter. + */ + public boolean contains(PropertyFilter propFilter) { + if (mPropFilter == propFilter) { + return true; + } + if (mNext == null) { + return false; + } + // Tail recursion. + return mNext.contains(propFilter); + } + + /** + * Prepend a node to the head of the list. + */ + PropertyFilterList prepend(PropertyFilter propFilter) { + PropertyFilterList head = new PropertyFilterList(propFilter, this); + mPrev = head; + return head; + } + + static class Builder + extends Visitor, PropertyFilterList> + { + public PropertyFilterList visit(OrFilter filter, PropertyFilterList list) { + // Traverse right-to-left since list must be built in this order. + list = filter.getRightFilter().accept(this, list); + list = filter.getLeftFilter().accept(this, list); + return list; + } + + public PropertyFilterList visit(AndFilter filter, PropertyFilterList list) { + // Traverse right-to-left since list must be built in this order. + list = filter.getRightFilter().accept(this, list); + list = filter.getLeftFilter().accept(this, list); + return list; + } + + public PropertyFilterList visit(PropertyFilter filter, PropertyFilterList list) { + return list == null ? new PropertyFilterList(filter, null) : list.prepend(filter); + } + } +} diff --git a/src/main/java/com/amazon/carbonado/filter/Reducer.java b/src/main/java/com/amazon/carbonado/filter/Reducer.java new file mode 100644 index 0000000..6e2acc1 --- /dev/null +++ b/src/main/java/com/amazon/carbonado/filter/Reducer.java @@ -0,0 +1,103 @@ +/* + * Copyright 2006 Amazon Technologies, Inc. or its affiliates. + * Amazon, Amazon.com and Carbonado are trademarks or registered trademarks + * of Amazon Technologies, Inc. or its affiliates. All rights reserved. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package com.amazon.carbonado.filter; + +import com.amazon.carbonado.Storable; + +/** + * Reduces a tree by eliminating redundant 'and' or 'or' terms. As a desired + * side-effect, the tree is also unbalanced to the left. + * + * @author Brian S O'Neill + */ +class Reducer extends Visitor, Group> { + Reducer() { + } + + /** + * @param filter candidate node to potentially replace + * @param group gathered children + * @return original candidate or replacement + */ + @Override + public Filter visit(OrFilter filter, Group group) { + final Group parentGroup = group; + + boolean groupRoot; + if (groupRoot = (group == null || group.mForAnd)) { + group = new Group(false); + } + + filter.getLeftFilter().accept(this, group); + filter.getRightFilter().accept(this, group); + + if (groupRoot) { + group.reduce(); + Filter result = group.merge(); + result.markReduced(); + if (parentGroup != null) { + parentGroup.add(result); + } + return result; + } + + return null; + } + + /** + * @param filter candidate node to potentially replace + * @param group gathered children + * @return original candidate or replacement + */ + @Override + public Filter visit(AndFilter filter, Group group) { + final Group parentGroup = group; + + boolean groupRoot; + if (groupRoot = (group == null || !group.mForAnd)) { + group = new Group(true); + } + + filter.getLeftFilter().accept(this, group); + filter.getRightFilter().accept(this, group); + + if (groupRoot) { + group.reduce(); + Filter result = group.merge(); + result.markReduced(); + if (parentGroup != null) { + parentGroup.add(result); + } + return result; + } + + return null; + } + + /** + * @param filter candidate node to potentially replace + * @param group gathered children + * @return original candidate or replacement + */ + @Override + public Filter visit(PropertyFilter filter, Group group) { + group.add(filter); + return null; + } +} diff --git a/src/main/java/com/amazon/carbonado/filter/RelOp.java b/src/main/java/com/amazon/carbonado/filter/RelOp.java new file mode 100644 index 0000000..f74d21e --- /dev/null +++ b/src/main/java/com/amazon/carbonado/filter/RelOp.java @@ -0,0 +1,78 @@ +/* + * Copyright 2006 Amazon Technologies, Inc. or its affiliates. + * Amazon, Amazon.com and Carbonado are trademarks or registered trademarks + * of Amazon Technologies, Inc. or its affiliates. All rights reserved. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package com.amazon.carbonado.filter; + +/** + * Relational operator enumeration. + * + * @author Brian S O'Neill + */ +public enum RelOp { + /** Equals */ + EQ, + /** Not Equals */ + NE, + /** Less Than */ + LT, + /** Greator than or Equal */ + GE, + /** Greator Than */ + GT, + /** Less than or Equal */ + LE; + + /** + * Returns one of "=", "!=", "<", ">=", ">", or "<=". + */ + public String toString() { + switch (this) { + case EQ: + return "="; + case NE: + return "!="; + case LT: + return "<"; + case GE: + return ">="; + case GT: + return ">"; + case LE: + return "<="; + default: + return super.toString(); + } + } + + public RelOp reverse() { + switch (this) { + case EQ: default: + return NE; + case NE: + return EQ; + case LT: + return GE; + case GE: + return LT; + case GT: + return LE; + case LE: + return GT; + } + } +} diff --git a/src/main/java/com/amazon/carbonado/filter/Visitor.java b/src/main/java/com/amazon/carbonado/filter/Visitor.java new file mode 100644 index 0000000..77ca07f --- /dev/null +++ b/src/main/java/com/amazon/carbonado/filter/Visitor.java @@ -0,0 +1,55 @@ +/* + * Copyright 2006 Amazon Technologies, Inc. or its affiliates. + * Amazon, Amazon.com and Carbonado are trademarks or registered trademarks + * of Amazon Technologies, Inc. or its affiliates. All rights reserved. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package com.amazon.carbonado.filter; + +import com.amazon.carbonado.Storable; + +/** + * Traverses a filter tree in its canonical order. By overriding a visit + * method, individual nodes can be captured and processed based on their + * type. Call super.visit inside the overridden visit method to ensure that the + * node's children are properly traversed. + * + * @author Brian S O'Neill + */ +public abstract class Visitor { + public R visit(OrFilter filter, P param) { + filter.getLeftFilter().accept(this, param); + filter.getRightFilter().accept(this, param); + return null; + } + + public R visit(AndFilter filter, P param) { + filter.getLeftFilter().accept(this, param); + filter.getRightFilter().accept(this, param); + return null; + } + + public R visit(PropertyFilter filter, P param) { + return null; + } + + public R visit(OpenFilter filter, P param) { + return null; + } + + public R visit(ClosedFilter filter, P param) { + return null; + } +} diff --git a/src/main/java/com/amazon/carbonado/filter/package-info.java b/src/main/java/com/amazon/carbonado/filter/package-info.java new file mode 100644 index 0000000..b52a049 --- /dev/null +++ b/src/main/java/com/amazon/carbonado/filter/package-info.java @@ -0,0 +1,24 @@ +/* + * Copyright 2006 Amazon Technologies, Inc. or its affiliates. + * Amazon, Amazon.com and Carbonado are trademarks or registered trademarks + * of Amazon Technologies, Inc. or its affiliates. All rights reserved. + * + * 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. + */ + +/** + * Contains classes for representing query filters. + * + * @see com.amazon.carbonado.filter.Filter + */ +package com.amazon.carbonado.filter; -- cgit v1.2.3