From a2b87f48775ca6687de0eb4af4b846bd1f0cdebf Mon Sep 17 00:00:00 2001 From: "Brian S. O'Neill" Date: Sun, 14 Oct 2007 02:31:22 +0000 Subject: Added support for "where exists" in queries via new syntax. --- .../amazon/carbonado/cursor/FilteredCursor.java | 12 +- .../carbonado/cursor/FilteredCursorGenerator.java | 253 ++++++++++++++++----- .../cursor/PropertyOrdinalMapVisitor.java | 58 +++++ .../carbonado/cursor/ShortCircuitOptimizer.java | 11 + 4 files changed, 276 insertions(+), 58 deletions(-) create mode 100644 src/main/java/com/amazon/carbonado/cursor/PropertyOrdinalMapVisitor.java (limited to 'src/main/java/com/amazon/carbonado/cursor') diff --git a/src/main/java/com/amazon/carbonado/cursor/FilteredCursor.java b/src/main/java/com/amazon/carbonado/cursor/FilteredCursor.java index 51d69e7..59cb941 100644 --- a/src/main/java/com/amazon/carbonado/cursor/FilteredCursor.java +++ b/src/main/java/com/amazon/carbonado/cursor/FilteredCursor.java @@ -25,10 +25,8 @@ import com.amazon.carbonado.FetchException; import com.amazon.carbonado.FetchInterruptedException; import com.amazon.carbonado.Storable; -import com.amazon.carbonado.filter.ClosedFilter; import com.amazon.carbonado.filter.Filter; import com.amazon.carbonado.filter.FilterValues; -import com.amazon.carbonado.filter.OpenFilter; /** * Wraps another cursor and applies custom filtering to reduce the set of @@ -66,7 +64,7 @@ public abstract class FilteredCursor extends AbstractCursor { * IllegalStateException will result otherwise. * * @param filter filter to apply - * @param filterValues values for filter + * @param filterValues values for filter, which may be null if filter has no parameters * @param cursor cursor to wrap * @return wrapped cursor which filters results * @throws IllegalStateException if any values are not specified @@ -76,18 +74,18 @@ public abstract class FilteredCursor extends AbstractCursor { FilterValues filterValues, Cursor cursor) { - if (filter instanceof OpenFilter) { + if (filter.isOpen()) { return cursor; } - if (filter instanceof ClosedFilter) { + if (filter.isClosed()) { throw new IllegalArgumentException(); } // Make sure the filter is the same one that filterValues should be using. filter = filter.bind(); - return FilteredCursorGenerator.getFactory(filter) - .newFilteredCursor(cursor, filterValues.getValuesFor(filter)); + Object[] values = filterValues == null ? null : filterValues.getValuesFor(filter); + return FilteredCursorGenerator.getFactory(filter).newFilteredCursor(cursor, values); } private final Cursor mCursor; diff --git a/src/main/java/com/amazon/carbonado/cursor/FilteredCursorGenerator.java b/src/main/java/com/amazon/carbonado/cursor/FilteredCursorGenerator.java index 9ca0b79..745ad7a 100644 --- a/src/main/java/com/amazon/carbonado/cursor/FilteredCursorGenerator.java +++ b/src/main/java/com/amazon/carbonado/cursor/FilteredCursorGenerator.java @@ -18,8 +18,13 @@ package com.amazon.carbonado.cursor; +import java.lang.reflect.InvocationTargetException; import java.lang.reflect.Method; + +import java.util.ArrayList; import java.util.Arrays; +import java.util.Collections; +import java.util.List; import java.util.Map; import java.util.Stack; @@ -38,9 +43,11 @@ import org.cojen.util.ClassInjector; import org.cojen.util.WeakIdentityMap; import com.amazon.carbonado.Cursor; +import com.amazon.carbonado.Query; import com.amazon.carbonado.Storable; import com.amazon.carbonado.filter.AndFilter; +import com.amazon.carbonado.filter.ExistsFilter; import com.amazon.carbonado.filter.OrFilter; import com.amazon.carbonado.filter.Filter; import com.amazon.carbonado.filter.PropertyFilter; @@ -50,8 +57,11 @@ import com.amazon.carbonado.filter.Visitor; import com.amazon.carbonado.info.ChainedProperty; import com.amazon.carbonado.info.StorableProperty; +import com.amazon.carbonado.util.ThrowUnchecked; import com.amazon.carbonado.util.QuickConstructorGenerator; +import com.amazon.carbonado.gen.CodeBuilderUtil; + /** * Generates Cursor implementations that wrap another Cursor, applying a @@ -61,6 +71,8 @@ import com.amazon.carbonado.util.QuickConstructorGenerator; * @see FilteredCursor */ class FilteredCursorGenerator { + private static final String SUB_FILTER_INIT_METHOD = "subFilterInit$"; + private static Map cCache = new WeakIdentityMap(); /** @@ -72,11 +84,6 @@ class FilteredCursorGenerator { */ @SuppressWarnings("unchecked") static Factory getFactory(Filter filter) { - return getFactory(filter, false); - } - - @SuppressWarnings("unchecked") - private static Factory getFactory(Filter filter, boolean optimize) { if (filter == null) { throw new IllegalArgumentException(); } @@ -85,16 +92,8 @@ class FilteredCursorGenerator { if (factory != null) { return factory; } - - Filter optimized; - if (optimize && (optimized = ShortCircuitOptimizer.optimize(filter)) != filter) { - // Use factory for filter optimized for short-circuit logic. - factory = getFactory(optimized, false); - } else { - Class> clazz = generateClass(filter); - factory = QuickConstructorGenerator.getInstance(clazz, Factory.class); - } - + Class> clazz = generateClass(filter); + factory = QuickConstructorGenerator.getInstance(clazz, Factory.class); cCache.put(filter, factory); return factory; } @@ -145,7 +144,7 @@ class FilteredCursorGenerator { CodeBuilder isAllowedBuilder; LocalVariable storableVar; { - TypeDesc[] params = {TypeDesc.OBJECT}; + TypeDesc[] params = {OBJECT}; MethodInfo mi = cf.addMethod(Modifiers.PUBLIC, "isAllowed", BOOLEAN, params); isAllowedBuilder = new CodeBuilder(mi); @@ -167,12 +166,38 @@ class FilteredCursorGenerator { isAllowedBuilder.storeLocal(storableVar); } - filter.accept(new CodeGen(cf, ctorBuilder, isAllowedBuilder, storableVar), null); + // Capture property filter ordinals before optimization scrambles them. + Map propertyOrdinalMap; + { + PropertyOrdinalMapVisitor visitor = new PropertyOrdinalMapVisitor(); + filter.accept(visitor, null); + propertyOrdinalMap = visitor.getPropertyOrdinalMap(); + } + + filter = ShortCircuitOptimizer.optimize(filter); + + CodeGen cg = new CodeGen + (propertyOrdinalMap, cf, ctorBuilder, isAllowedBuilder, storableVar); + filter.accept(cg, null); + + List subFilters = cg.finishSubFilterInit(); // Finish constructor. ctorBuilder.returnVoid(); - return (Class>) ci.defineClass(cf); + Class generated = ci.defineClass(cf); + + // Pass sub-filter instances to be stored in static fields. + if (subFilters != null && subFilters.size() > 0) { + try { + Method init = generated.getMethod(SUB_FILTER_INIT_METHOD, Filter[].class); + init.invoke(null, (Object) subFilters.toArray(new Filter[subFilters.size()])); + } catch (Exception e) { + ThrowUnchecked.fireDeclaredRootCause(e); + } + } + + return (Class>) generated; } public static interface Factory { @@ -235,8 +260,10 @@ class FilteredCursorGenerator { } private static class CodeGen extends Visitor { - private static String FIELD_PREFIX = "value$"; + private static final String FIELD_PREFIX = "value$"; + private static final String FILTER_FIELD_PREFIX = "filter$"; + private final Map mPropertyOrdinalMap; private final ClassFile mClassFile; private final CodeBuilder mCtorBuilder; private final CodeBuilder mIsAllowedBuilder; @@ -244,11 +271,16 @@ class FilteredCursorGenerator { private final Stack mScopeStack; - private int mPropertyOrdinal; + private List mSubFilters; + private CodeBuilder mSubFilterInitBuilder; - CodeGen(ClassFile cf, + CodeGen(Map propertyOrdinalMap, + ClassFile cf, CodeBuilder ctorBuilder, - CodeBuilder isAllowedBuilder, LocalVariable storableVar) { + CodeBuilder isAllowedBuilder, + LocalVariable storableVar) + { + mPropertyOrdinalMap = propertyOrdinalMap; mClassFile = cf; mCtorBuilder = ctorBuilder; mIsAllowedBuilder = isAllowedBuilder; @@ -257,6 +289,16 @@ class FilteredCursorGenerator { mScopeStack.push(new Scope(null, null)); } + public List finishSubFilterInit() { + if (mSubFilterInitBuilder != null) { + mSubFilterInitBuilder.returnVoid(); + } + if (mSubFilters == null) { + return Collections.emptyList(); + } + return mSubFilters; + } + public Object visit(OrFilter filter, Object param) { Label failLocation = mIsAllowedBuilder.createLabel(); // Inherit success location to short-circuit if 'or' test succeeds. @@ -280,26 +322,144 @@ class FilteredCursorGenerator { } public Object visit(PropertyFilter filter, Object param) { - ChainedProperty chained = filter.getChainedProperty(); - TypeDesc type = TypeDesc.forClass(chained.getType()); - TypeDesc fieldType = actualFieldType(type); - String fieldName = FIELD_PREFIX + mPropertyOrdinal; + final int propertyOrdinal = mPropertyOrdinalMap.get(filter); + final TypeDesc type = TypeDesc.forClass(filter.getChainedProperty().getType()); + final TypeDesc fieldType = actualFieldType(type); + final String fieldName = FIELD_PREFIX + propertyOrdinal; // Define storage field. mClassFile.addField(Modifiers.PRIVATE.toFinal(true), fieldName, fieldType); // Add code to constructor to store value into field. - CodeBuilder b = mCtorBuilder; - b.loadThis(); - b.loadLocal(b.getParameter(1)); - b.loadConstant(mPropertyOrdinal); - b.loadFromArray(OBJECT); - b.checkCast(type.toObjectType()); - convertProperty(b, type.toObjectType(), fieldType); - b.storeField(fieldName, fieldType); - - // Add code to load property value to stack. - b = mIsAllowedBuilder; + { + CodeBuilder b = mCtorBuilder; + b.loadThis(); + b.loadLocal(b.getParameter(1)); + b.loadConstant(propertyOrdinal); + b.loadFromArray(OBJECT); + b.checkCast(type.toObjectType()); + convertProperty(b, type.toObjectType(), fieldType); + b.storeField(fieldName, fieldType); + } + + loadChainedProperty(mIsAllowedBuilder, filter.getChainedProperty()); + addPropertyFilter(mIsAllowedBuilder, propertyOrdinal, type, filter.getOperator()); + + return null; + } + + public Object visit(ExistsFilter filter, Object param) { + // Recursively gather all the properties to be passed to sub-filter. + final List subPropFilters = new ArrayList(); + + filter.getSubFilter().accept(new Visitor() { + @Override + public Object visit(PropertyFilter filter, Object param) { + subPropFilters.add(filter); + return null; + } + @Override + public Object visit(ExistsFilter filter, Object param) { + return filter.getSubFilter().accept(this, param); + } + }, null); + + // Load join property value to stack. It is expected to be a Query. + CodeBuilder b = mIsAllowedBuilder; + loadChainedProperty(b, filter.getChainedProperty()); + + final TypeDesc queryType = TypeDesc.forClass(Query.class); + + // Refine Query filter, if sub-filter isn't open. + if (!filter.getSubFilter().isOpen()) { + String subFilterFieldName = addStaticFilterField(filter.getSubFilter()); + + TypeDesc filterType = TypeDesc.forClass(Filter.class); + + b.loadStaticField(subFilterFieldName, filterType); + b.invokeInterface(queryType, "and", queryType, new TypeDesc[] {filterType}); + + for (PropertyFilter subPropFilter : subPropFilters) { + final int propertyOrdinal = mPropertyOrdinalMap.get(subPropFilter); + final ChainedProperty chained = subPropFilter.getChainedProperty(); + final String fieldName = FIELD_PREFIX + propertyOrdinal; + + // Define storage for sub-filter. + mClassFile.addField(Modifiers.PRIVATE.toFinal(true), fieldName, OBJECT); + + // Assign value passed from constructor. + mCtorBuilder.loadThis(); + mCtorBuilder.loadLocal(mCtorBuilder.getParameter(1)); + mCtorBuilder.loadConstant(propertyOrdinal); + mCtorBuilder.loadFromArray(OBJECT); + mCtorBuilder.storeField(fieldName, OBJECT); + + // Pass value to Query. + b.loadThis(); + b.loadField(fieldName, OBJECT); + b.invokeInterface(queryType, "with", queryType, new TypeDesc[] {OBJECT}); + } + } + + // Call the all-important Query.exists method. + b.invokeInterface(queryType, "exists", BOOLEAN, null); + + // Success if boolean value is true (non-zero), opposite for "not exists". + RelOp op = filter.isNotExists() ? RelOp.EQ : RelOp.NE; + getScope().successIfZeroComparisonElseFail(b, op); + + return null; + } + + private String addStaticFilterField(Filter filter) { + if (mSubFilters == null) { + mSubFilters = new ArrayList(); + } + + final int filterOrdinal = mSubFilters.size(); + final String fieldName = FILTER_FIELD_PREFIX + filterOrdinal; + final TypeDesc filterType = TypeDesc.forClass(Filter.class); + + mClassFile.addField(Modifiers.PRIVATE.toStatic(true), fieldName, filterType); + + mSubFilters.add(filter); + + if (mSubFilterInitBuilder == null) { + TypeDesc filterArrayType = filterType.toArrayType(); + mSubFilterInitBuilder = new CodeBuilder + (mClassFile.addMethod + (Modifiers.PUBLIC.toStatic(true), + SUB_FILTER_INIT_METHOD, null, new TypeDesc[] {filterArrayType})); + + // This method must be public, so add a check to ensure it is + // called at most once. Just check one filter to see if it is non-null. + + mSubFilterInitBuilder.loadStaticField(fieldName, filterType); + Label isNull = mSubFilterInitBuilder.createLabel(); + mSubFilterInitBuilder.ifNullBranch(isNull, true); + CodeBuilderUtil.throwException + (mSubFilterInitBuilder, IllegalStateException.class, null); + isNull.setLocation(); + } + + // Now add code to init field later. + mSubFilterInitBuilder.loadLocal(mSubFilterInitBuilder.getParameter(0)); + mSubFilterInitBuilder.loadConstant(filterOrdinal); + mSubFilterInitBuilder.loadFromArray(filterType); + mSubFilterInitBuilder.storeStaticField(fieldName, filterType); + + return fieldName; + } + + private Scope getScope() { + return mScopeStack.peek(); + } + + /** + * Generated code checks if chained properties resolve to null, and if + * so, branches to the current scope's fail location. + */ + private void loadChainedProperty(CodeBuilder b, ChainedProperty chained) { b.loadLocal(mStorableVar); loadProperty(b, chained.getPrimeProperty()); for (int i=0; i property) { @@ -341,9 +492,9 @@ class FilteredCursorGenerator { b.invoke(readMethod); } - private void addPropertyFilter(CodeBuilder b, TypeDesc type, RelOp relOp) { + private void addPropertyFilter(CodeBuilder b, int ordinal, TypeDesc type, RelOp relOp) { TypeDesc fieldType = actualFieldType(type); - String fieldName = FIELD_PREFIX + mPropertyOrdinal; + String fieldName = FIELD_PREFIX + ordinal; if (type.getTypeCode() == OBJECT_CODE) { // Check if actual property being examined is null. @@ -524,7 +675,7 @@ class FilteredCursorGenerator { private void convertProperty(CodeBuilder b, TypeDesc fromType, TypeDesc toType) { TypeDesc fromPrimType = fromType.toPrimitiveType(); - if (fromPrimType != TypeDesc.FLOAT && fromPrimType != TypeDesc.DOUBLE) { + if (fromPrimType != FLOAT && fromPrimType != DOUBLE) { // Not converting floating point, so just convert as normal. b.convert(fromType, toType); return; @@ -532,7 +683,7 @@ class FilteredCursorGenerator { TypeDesc toPrimType = toType.toPrimitiveType(); - if (toPrimType != TypeDesc.INT && toPrimType != TypeDesc.LONG) { + if (toPrimType != INT && toPrimType != LONG) { // Floating point not being converted to bits, so just convert as normal. b.convert(fromType, toType); return; @@ -557,7 +708,7 @@ class FilteredCursorGenerator { // Floating point bits need to be flipped for negative values. - if (toPrimType == TypeDesc.INT) { + if (toPrimType == INT) { b.dup(); b.ifZeroComparisonBranch(box, ">="); b.loadConstant(0x7fffffff); diff --git a/src/main/java/com/amazon/carbonado/cursor/PropertyOrdinalMapVisitor.java b/src/main/java/com/amazon/carbonado/cursor/PropertyOrdinalMapVisitor.java new file mode 100644 index 0000000..8bcfa52 --- /dev/null +++ b/src/main/java/com/amazon/carbonado/cursor/PropertyOrdinalMapVisitor.java @@ -0,0 +1,58 @@ +/* + * Copyright 2007 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.cursor; + +import java.util.IdentityHashMap; +import java.util.Map; + +import com.amazon.carbonado.Storable; + +import com.amazon.carbonado.filter.ExistsFilter; +import com.amazon.carbonado.filter.PropertyFilter; +import com.amazon.carbonado.filter.Visitor; + +/** + * Visits a filter and maps all property filters to their zero-based ordinal + * position. + * + * @author Brian S O'Neill + */ +class PropertyOrdinalMapVisitor extends Visitor { + private int mOrdinal; + private Map mOrdinalMap; + + PropertyOrdinalMapVisitor() { + mOrdinalMap = new IdentityHashMap(); + } + + public Map getPropertyOrdinalMap() { + return mOrdinalMap; + } + + @Override + public Object visit(PropertyFilter filter, Object param) { + mOrdinalMap.put(filter, mOrdinal++); + return null; + } + + @Override + public Object visit(ExistsFilter filter, Object param) { + return filter.getSubFilter().accept(this, param); + } +} diff --git a/src/main/java/com/amazon/carbonado/cursor/ShortCircuitOptimizer.java b/src/main/java/com/amazon/carbonado/cursor/ShortCircuitOptimizer.java index 1a46d1e..46b03b1 100644 --- a/src/main/java/com/amazon/carbonado/cursor/ShortCircuitOptimizer.java +++ b/src/main/java/com/amazon/carbonado/cursor/ShortCircuitOptimizer.java @@ -25,6 +25,7 @@ import com.amazon.carbonado.info.StorableProperty; import com.amazon.carbonado.filter.AndFilter; import com.amazon.carbonado.filter.ClosedFilter; +import com.amazon.carbonado.filter.ExistsFilter; import com.amazon.carbonado.filter.Filter; import com.amazon.carbonado.filter.OpenFilter; import com.amazon.carbonado.filter.OrFilter; @@ -132,6 +133,7 @@ class ShortCircuitOptimizer { } private static class Walker extends Visitor, Object> { + @Override public FilterAndCost visit(OrFilter filter, Object param) { FilterAndCost leftCost = filter.getLeftFilter().accept(this, param); FilterAndCost rightCost = filter.getRightFilter().accept(this, param); @@ -154,6 +156,7 @@ class ShortCircuitOptimizer { return new FilterAndCost(newFilter, expensiveProperty); } + @Override public FilterAndCost visit(AndFilter filter, Object param) { FilterAndCost leftCost = filter.getLeftFilter().accept(this, param); FilterAndCost rightCost = filter.getRightFilter().accept(this, param); @@ -176,14 +179,22 @@ class ShortCircuitOptimizer { return new FilterAndCost(newFilter, expensiveProperty); } + @Override public FilterAndCost visit(PropertyFilter filter, Object param) { return new FilterAndCost(filter, filter.getChainedProperty()); } + @Override + public FilterAndCost visit(ExistsFilter filter, Object param) { + return new FilterAndCost(filter, filter.getChainedProperty()); + } + + @Override public FilterAndCost visit(OpenFilter filter, Object param) { return new FilterAndCost(filter, null); } + @Override public FilterAndCost visit(ClosedFilter filter, Object param) { return new FilterAndCost(filter, null); } -- cgit v1.2.3