You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@calcite.apache.org by jh...@apache.org on 2019/08/12 19:29:50 UTC
[calcite] 03/03: [CALCITE-1935] Implement MATCH_RECOGNIZE,
part 3: get it working (Julian Feinauer)
This is an automated email from the ASF dual-hosted git repository.
jhyde pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/calcite.git
commit 5ec3a2a503dcf26fe1b3cad8a5a9467264213dcf
Author: Julian Feinauer <j....@pragmaticminds.de>
AuthorDate: Tue Dec 25 23:50:58 2018 +0100
[CALCITE-1935] Implement MATCH_RECOGNIZE, part 3: get it working (Julian Feinauer)
Add support for OR ("|") and OPTIONAL ("?") patterns.
Translate eps-NFA to DFA, and implement Matcher based on DFA.
Fixed a Bug in RexImpTable to make the minimal example work.
Close apache/calcite#1343
---
.../adapter/enumerable/EnumerableMatch.java | 236 +++++++++++++--
.../calcite/adapter/enumerable/RexImpTable.java | 14 +
.../adapter/enumerable/RexToLixTranslator.java | 13 +-
.../java/org/apache/calcite/rel/core/Match.java | 2 +-
.../rel/rules/AggregateFilterTransposeRule.java | 4 +-
.../apache/calcite/rel/rules/SortJoinCopyRule.java | 17 +-
.../calcite/rel/rules/SubQueryRemoveRule.java | 4 +-
.../java/org/apache/calcite/runtime/Automaton.java | 30 +-
.../apache/calcite/runtime/AutomatonBuilder.java | 30 ++
.../calcite/runtime/DeterministicAutomaton.java | 188 ++++++++++++
.../org/apache/calcite/runtime/Enumerables.java | 24 +-
.../java/org/apache/calcite/runtime/Matcher.java | 335 ++++++++++++++-------
.../java/org/apache/calcite/runtime/Pattern.java | 22 +-
.../org/apache/calcite/util/BuiltInMethod.java | 9 +-
.../org/apache/calcite/runtime/AutomatonTest.java | 103 ++++++-
.../runtime/DeterministicAutomatonTest.java | 104 +++++++
.../apache/calcite/runtime/EnumerablesTest.java | 45 +++
.../ExtensionSqlParserTest.java | 5 +-
.../java/org/apache/calcite/test/CalciteSuite.java | 2 +
.../java/org/apache/calcite/test/JdbcTest.java | 46 ++-
.../org/apache/calcite/test/RelBuilderTest.java | 2 +-
.../apache/calcite/test/SqlToRelConverterTest.xml | 199 +++++++-----
core/src/test/resources/sql/match.iq | 70 +++--
.../org/apache/calcite/adapter/file/SqlTest.java | 4 +-
.../apache/calcite/linq4j/MemoryEnumerable.java | 48 +++
.../apache/calcite/linq4j/MemoryEnumerator.java | 88 ++++++
.../org/apache/calcite/linq4j/MemoryFactory.java | 97 ++++++
.../org/apache/calcite/linq4j/ModularInteger.java | 75 +++++
.../apache/calcite/linq4j/tree/ExpressionType.java | 7 +
.../apache/calcite/linq4j/tree/Expressions.java | 2 +-
.../calcite/linq4j/tree/ForEachStatement.java | 6 +-
.../apache/calcite/linq4j/tree/VisitorImpl.java | 3 +-
.../calcite/linq4j/MemoryEnumerableTest.java | 70 +++++
.../apache/calcite/linq4j/test/ExpressionTest.java | 21 ++
34 files changed, 1633 insertions(+), 292 deletions(-)
diff --git a/core/src/main/java/org/apache/calcite/adapter/enumerable/EnumerableMatch.java b/core/src/main/java/org/apache/calcite/adapter/enumerable/EnumerableMatch.java
index 0f73f16..2cd14ac 100644
--- a/core/src/main/java/org/apache/calcite/adapter/enumerable/EnumerableMatch.java
+++ b/core/src/main/java/org/apache/calcite/adapter/enumerable/EnumerableMatch.java
@@ -17,8 +17,10 @@
package org.apache.calcite.adapter.enumerable;
import org.apache.calcite.adapter.java.JavaTypeFactory;
+import org.apache.calcite.linq4j.MemoryFactory;
import org.apache.calcite.linq4j.Ord;
import org.apache.calcite.linq4j.tree.BlockBuilder;
+import org.apache.calcite.linq4j.tree.BlockStatement;
import org.apache.calcite.linq4j.tree.Expression;
import org.apache.calcite.linq4j.tree.Expressions;
import org.apache.calcite.linq4j.tree.MemberDeclaration;
@@ -30,9 +32,14 @@ import org.apache.calcite.rel.RelCollation;
import org.apache.calcite.rel.RelNode;
import org.apache.calcite.rel.core.Match;
import org.apache.calcite.rel.type.RelDataType;
+import org.apache.calcite.rel.type.RelDataTypeFactory;
+import org.apache.calcite.rex.RexBuilder;
import org.apache.calcite.rex.RexCall;
import org.apache.calcite.rex.RexLiteral;
import org.apache.calcite.rex.RexNode;
+import org.apache.calcite.rex.RexProgramBuilder;
+import org.apache.calcite.rex.RexSubQuery;
+import org.apache.calcite.rex.RexVisitorImpl;
import org.apache.calcite.runtime.Enumerables;
import org.apache.calcite.util.BuiltInMethod;
import org.apache.calcite.util.ImmutableBitSet;
@@ -40,13 +47,16 @@ import org.apache.calcite.util.Pair;
import com.google.common.collect.ImmutableList;
+import java.lang.reflect.Modifier;
+import java.lang.reflect.Type;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Map;
import java.util.SortedSet;
-import java.util.function.BiPredicate;
import java.util.function.Consumer;
+import java.util.function.Function;
+import java.util.function.Predicate;
import static org.apache.calcite.adapter.enumerable.EnumUtils.NO_EXPRS;
@@ -97,7 +107,7 @@ public class EnumerableMatch extends Match implements EnumerableRel {
final EnumerableRel input = (EnumerableRel) getInput();
final Result result = implementor.visitChild(this, 0, input, pref);
final PhysType physType =
- PhysTypeImpl.of(implementor.getTypeFactory(), getRowType(),
+ PhysTypeImpl.of(implementor.getTypeFactory(), input.getRowType(),
result.format);
final Expression inputExp =
builder.append("input", result.block);
@@ -107,38 +117,65 @@ public class EnumerableMatch extends Match implements EnumerableRel {
final PhysType keyPhysType =
inputPhysType.project(partitionKeys.asList(), JavaRowFormat.LIST);
final ParameterExpression row_ =
- Expressions.parameter(Object.class, "row");
+ Expressions.parameter(inputPhysType.getJavaRowType(), "row_");
final Expression keySelector_ =
builder.append("keySelector",
inputPhysType.generateSelector(row_,
partitionKeys.asList(),
keyPhysType.getFormat()));
- final Expression matcher_ = implementMatcher(builder, row_);
- final Expression emitter_ = implementEmitter(implementor, physType, null);
+ final RelDataTypeFactory.Builder typeBuilder =
+ implementor.getTypeFactory().builder();
+ measures.forEach((name, value) -> typeBuilder.add(name, value.getType()));
+
+ final PhysType emitType =
+ PhysTypeImpl.of(implementor.getTypeFactory(), typeBuilder.build(),
+ result.format);
+
+ final Expression matcher_ = implementMatcher(implementor, physType, builder, row_);
+ final Expression emitter_ = implementEmitter(implementor, emitType, physType);
+
+ final MaxHistoryFutureVisitor visitor = new MaxHistoryFutureVisitor();
+ patternDefinitions.values().forEach(pd -> pd.accept(visitor));
+
+ // Fetch
+ // Calculate how many steps we need to look back or forward
+ int history = visitor.getHistory();
+ int future = visitor.getFuture();
+
builder.add(
Expressions.return_(null,
- Expressions.call(BuiltInMethod.MATCH.method,
- inputExp, keySelector_, matcher_, emitter_)));
- return implementor.result(physType, builder.toBlock());
+ Expressions.call(BuiltInMethod.MATCH.method, inputExp, keySelector_,
+ matcher_, emitter_, Expressions.constant(history),
+ Expressions.constant(future))));
+ return implementor.result(emitType, builder.toBlock());
}
private Expression implementEmitter(EnumerableRelImplementor implementor,
PhysType physType, PhysType inputPhysType) {
final ParameterExpression rows_ =
- Expressions.parameter(List.class, "rows");
+ Expressions.parameter(Types.of(List.class, inputPhysType.getJavaRowType()), "rows");
final ParameterExpression rowStates_ =
Expressions.parameter(List.class, "rowStates");
+ final ParameterExpression symbols_ =
+ Expressions.parameter(List.class, "symbols");
final ParameterExpression match_ =
Expressions.parameter(int.class, "match");
final ParameterExpression consumer_ =
Expressions.parameter(Consumer.class, "consumer");
final ParameterExpression row_ =
- Expressions.parameter(Object.class, "row");
+ Expressions.parameter(inputPhysType.getJavaRowType(), "row");
final BlockBuilder builder2 = new BlockBuilder();
+
+ RexBuilder rexBuilder = new RexBuilder(implementor.getTypeFactory());
+ RexProgramBuilder rexProgramBuilder = new RexProgramBuilder(inputPhysType.getRowType(),
+ rexBuilder);
+ for (Map.Entry<String, RexNode> entry : measures.entrySet()) {
+ rexProgramBuilder.addProject(entry.getValue(), entry.getKey());
+ }
final List<Expression> arguments =
- RexToLixTranslator.translateProjects(null,
+ RexToLixTranslator.translateProjects(rexProgramBuilder.getProgram(),
(JavaTypeFactory) getCluster().getTypeFactory(),
implementor.getConformance(), builder2, physType,
implementor.getRootExpression(),
@@ -146,13 +183,23 @@ public class EnumerableMatch extends Match implements EnumerableRel {
Collections.singletonList(
Pair.of(row_, inputPhysType))),
implementor.allCorrelateVariables);
- for (RexNode measure : measures.values()) {
- arguments.add(null);
+
+ final ParameterExpression result_ =
+ Expressions.parameter(physType.getJavaRowType());
+
+ builder2.add(
+ Expressions.declare(Modifier.FINAL, result_,
+ Expressions.new_(physType.getJavaRowType())));
+ for (int i = 0; i < arguments.size(); i++) {
+ builder2.add(
+ Expressions.statement(
+ Expressions.assign(physType.fieldReference(result_, i),
+ arguments.get(i))));
}
builder2.add(
Expressions.statement(
Expressions.call(consumer_, BuiltInMethod.CONSUMER_ACCEPT.method,
- physType.record(arguments))));
+ result_)));
final BlockBuilder builder = new BlockBuilder();
builder.add(Expressions.forEach(row_, rows_, builder2.toBlock()));
@@ -162,25 +209,52 @@ public class EnumerableMatch extends Match implements EnumerableRel {
Expressions.list(
EnumUtils.overridingMethodDecl(
BuiltInMethod.EMITTER_EMIT.method,
- ImmutableList.of(rows_, rowStates_, match_, consumer_),
+ ImmutableList.of(rows_, rowStates_, symbols_, match_,
+ consumer_),
builder.toBlock())));
}
- private Expression implementMatcher(BlockBuilder builder,
- ParameterExpression row_) {
+ private Expression implementMatcher(EnumerableRelImplementor implementor,
+ PhysType physType, BlockBuilder builder, ParameterExpression row_) {
final Expression patternBuilder_ = builder.append("patternBuilder",
Expressions.call(BuiltInMethod.PATTERN_BUILDER.method));
final Expression automaton_ = builder.append("automaton",
- Expressions.call(
- implementPattern(patternBuilder_, pattern),
+ Expressions.call(implementPattern(patternBuilder_, pattern),
BuiltInMethod.PATTERN_TO_AUTOMATON.method));
Expression matcherBuilder_ = builder.append("matcherBuilder",
Expressions.call(BuiltInMethod.MATCHER_BUILDER.method, automaton_));
+ final BlockBuilder builder2 = new BlockBuilder();
+
+
+ // Wrap a MemoryEnumerable around
+
for (Map.Entry<String, RexNode> entry : patternDefinitions.entrySet()) {
- final Expression predicate_ = implementPredicate(row_);
+ // Translate REX to Expressions
+ RexBuilder rexBuilder = new RexBuilder(implementor.getTypeFactory());
+ RexProgramBuilder rexProgramBuilder =
+ new RexProgramBuilder(physType.getRowType(), rexBuilder);
+
+ rexProgramBuilder.addCondition(entry.getValue());
+
+ final RexToLixTranslator.InputGetter inputGetter1 =
+ new PrevInputGetter(row_, physType);
+
+ final Expression condition = RexToLixTranslator
+ .translateCondition(rexProgramBuilder.getProgram(),
+ (JavaTypeFactory) getCluster().getTypeFactory(),
+ builder2,
+ inputGetter1,
+ implementor.allCorrelateVariables,
+ implementor.getConformance());
+
+ builder2.add(Expressions.return_(null, condition));
+ final Expression predicate_ =
+ implementPredicate(physType, row_, builder2.toBlock());
+
matcherBuilder_ = Expressions.call(matcherBuilder_,
BuiltInMethod.MATCHER_BUILDER_ADD.method,
- Expressions.constant(entry.getKey()), predicate_);
+ Expressions.constant(entry.getKey()),
+ predicate_);
}
return builder.append("matcher",
Expressions.call(matcherBuilder_,
@@ -188,12 +262,17 @@ public class EnumerableMatch extends Match implements EnumerableRel {
}
/** Generates code for a predicate. */
- private Expression implementPredicate(ParameterExpression row_) {
- final ParameterExpression rows_ =
- Expressions.parameter(List.class, "rows"); // "List<E> rows"
- final BlockBuilder builder2 = new BlockBuilder();
- builder2.add(Expressions.return_(null, Expressions.constant(true)));
+ private Expression implementPredicate(PhysType physType,
+ ParameterExpression rows_, BlockStatement body) {
final List<MemberDeclaration> memberDeclarations = new ArrayList<>();
+ ParameterExpression row_ = Expressions.parameter(
+ Types.of(MemoryFactory.Memory.class,
+ physType.getJavaRowType()), "row_");
+ Expressions.assign(row_,
+ Expressions.call(rows_, BuiltInMethod.MEMORY_GET0.method));
+
+ // Implement the Predicate here based on the pattern definition
+
// Add a predicate method:
//
// public boolean test(E row, List<E> rows) {
@@ -201,14 +280,16 @@ public class EnumerableMatch extends Match implements EnumerableRel {
// }
memberDeclarations.add(
EnumUtils.overridingMethodDecl(
- BuiltInMethod.BI_PREDICATE_TEST.method,
- ImmutableList.of(row_, rows_), builder2.toBlock()));
+ BuiltInMethod.PREDICATE_TEST.method,
+ ImmutableList.of(row_), body));
if (EnumerableRules.BRIDGE_METHODS) {
// Add a bridge method:
//
// public boolean test(Object row, Object rows) {
// return this.test(row, (List) rows);
// }
+ final ParameterExpression row0_ =
+ Expressions.parameter(Object.class, "row");
final ParameterExpression rowsO_ =
Expressions.parameter(Object.class, "rows");
BlockBuilder bridgeBody = new BlockBuilder();
@@ -216,14 +297,16 @@ public class EnumerableMatch extends Match implements EnumerableRel {
Expressions.return_(null,
Expressions.call(
Expressions.parameter(Comparable.class, "this"),
- BuiltInMethod.BI_PREDICATE_TEST.method,
- row_, Expressions.convert_(rowsO_, List.class))));
+ BuiltInMethod.PREDICATE_TEST.method,
+ Expressions.convert_(row0_,
+ Types.of(MemoryFactory.Memory.class,
+ physType.getJavaRowType())))));
memberDeclarations.add(
EnumUtils.overridingMethodDecl(
- BuiltInMethod.BI_PREDICATE_TEST.method,
- ImmutableList.of(row_, rowsO_), bridgeBody.toBlock()));
+ BuiltInMethod.PREDICATE_TEST.method,
+ ImmutableList.of(row0_), bridgeBody.toBlock()));
}
- return Expressions.new_(Types.of(BiPredicate.class), NO_EXPRS,
+ return Expressions.new_(Types.of(Predicate.class), NO_EXPRS,
memberDeclarations);
}
@@ -255,6 +338,93 @@ public class EnumerableMatch extends Match implements EnumerableRel {
throw new AssertionError("unknown kind: " + pattern);
}
}
+
+ /**
+ * Visitor that finds out how much "history" we need in the past and future.
+ */
+ private static class MaxHistoryFutureVisitor extends RexVisitorImpl<Void> {
+ private int history;
+ private int future;
+
+ protected MaxHistoryFutureVisitor() {
+ super(true);
+ }
+
+ public int getHistory() {
+ return history;
+ }
+
+ public int getFuture() {
+ return future;
+ }
+
+ @Override public Void visitCall(RexCall call) {
+ call.operands.forEach(o -> o.accept(this));
+ final RexLiteral operand;
+ switch (call.op.kind) {
+ case PREV:
+ operand = (RexLiteral) call.getOperands().get(1);
+ final int prev = operand.getValueAs(Integer.class);
+ this.history = Math.max(this.history, prev);
+ break;
+ case NEXT:
+ operand = (RexLiteral) call.getOperands().get(1);
+ final int next = operand.getValueAs(Integer.class);
+ this.future = Math.max(this.future, next);
+ break;
+ }
+ return null;
+ }
+
+ @Override public Void visitSubQuery(RexSubQuery subQuery) {
+ return null;
+ }
+ }
+
+ /**
+ * A special Getter that "interchanges" the PREV and the field call.
+ */
+ static class PrevInputGetter implements RexToLixTranslator.InputGetter {
+ private Expression offset;
+ private final ParameterExpression row;
+ private final Function<Expression, RexToLixTranslator.InputGetter> generator;
+ private final PhysType physType;
+
+ PrevInputGetter(ParameterExpression row, PhysType physType) {
+ this.row = row;
+ generator = e -> new RexToLixTranslator.InputGetterImpl(
+ Collections.singletonList(
+ Pair.of(e, physType)));
+ this.physType = physType;
+ }
+
+ void setOffset(Expression offset) {
+ this.offset = offset;
+ }
+
+ @Override public Expression field(BlockBuilder list, int index,
+ Type storageType) {
+ final ParameterExpression row =
+ Expressions.parameter(physType.getJavaRowType());
+ final ParameterExpression tmp =
+ Expressions.parameter(Object.class);
+ list.add(
+ Expressions.declare(0, tmp,
+ Expressions.call(this.row, BuiltInMethod.MEMORY_GET1.method,
+ offset)));
+ list.add(
+ Expressions.declare(0, row,
+ Expressions.convert_(tmp, physType.getJavaRowType())));
+
+ // Add return statement if here is a null!
+ list.add(
+ Expressions.ifThen(
+ Expressions.equal(tmp, Expressions.constant(null)),
+ Expressions.return_(null, Expressions.constant(false))));
+
+ return generator.apply(row).field(list, index, storageType);
+ }
+ }
}
// End EnumerableMatch.java
diff --git a/core/src/main/java/org/apache/calcite/adapter/enumerable/RexImpTable.java b/core/src/main/java/org/apache/calcite/adapter/enumerable/RexImpTable.java
index 2aba884..42fd16c 100644
--- a/core/src/main/java/org/apache/calcite/adapter/enumerable/RexImpTable.java
+++ b/core/src/main/java/org/apache/calcite/adapter/enumerable/RexImpTable.java
@@ -153,6 +153,7 @@ import static org.apache.calcite.sql.fun.SqlStdOperatorTable.ELEMENT;
import static org.apache.calcite.sql.fun.SqlStdOperatorTable.EQUALS;
import static org.apache.calcite.sql.fun.SqlStdOperatorTable.EXP;
import static org.apache.calcite.sql.fun.SqlStdOperatorTable.EXTRACT;
+import static org.apache.calcite.sql.fun.SqlStdOperatorTable.FINAL;
import static org.apache.calcite.sql.fun.SqlStdOperatorTable.FIRST_VALUE;
import static org.apache.calcite.sql.fun.SqlStdOperatorTable.FLOOR;
import static org.apache.calcite.sql.fun.SqlStdOperatorTable.FUSION;
@@ -230,6 +231,7 @@ import static org.apache.calcite.sql.fun.SqlStdOperatorTable.PI;
import static org.apache.calcite.sql.fun.SqlStdOperatorTable.PLUS;
import static org.apache.calcite.sql.fun.SqlStdOperatorTable.POSITION;
import static org.apache.calcite.sql.fun.SqlStdOperatorTable.POWER;
+import static org.apache.calcite.sql.fun.SqlStdOperatorTable.PREV;
import static org.apache.calcite.sql.fun.SqlStdOperatorTable.RADIANS;
import static org.apache.calcite.sql.fun.SqlStdOperatorTable.RAND;
import static org.apache.calcite.sql.fun.SqlStdOperatorTable.RAND_INTEGER;
@@ -595,6 +597,18 @@ public class RexImpTable {
winAggMap.put(NTILE, constructorSupplier(NtileImplementor.class));
winAggMap.put(COUNT, constructorSupplier(CountWinImplementor.class));
winAggMap.put(REGR_COUNT, constructorSupplier(CountWinImplementor.class));
+
+ // Functions for MATCH_RECOGNIZE
+ defineMethod(FINAL, "abs", NullPolicy.ANY);
+
+ map.put(PREV, (translator, call, nullAs) -> {
+ final RexNode node = call.getOperands().get(0);
+ final RexNode offset = call.getOperands().get(1);
+ final Expression offs = Expressions.multiply(translator.translate(offset),
+ Expressions.constant(-1));
+ ((EnumerableMatch.PrevInputGetter) translator.inputGetter).setOffset(offs);
+ return translator.translate(node, nullAs);
+ });
}
private <T> Supplier<T> constructorSupplier(Class<T> klass) {
diff --git a/core/src/main/java/org/apache/calcite/adapter/enumerable/RexToLixTranslator.java b/core/src/main/java/org/apache/calcite/adapter/enumerable/RexToLixTranslator.java
index 4f7af47..ebc0c54 100644
--- a/core/src/main/java/org/apache/calcite/adapter/enumerable/RexToLixTranslator.java
+++ b/core/src/main/java/org/apache/calcite/adapter/enumerable/RexToLixTranslator.java
@@ -98,7 +98,7 @@ public class RexToLixTranslator {
private final RexProgram program;
final SqlConformance conformance;
private final Expression root;
- private final RexToLixTranslator.InputGetter inputGetter;
+ final RexToLixTranslator.InputGetter inputGetter;
private final BlockBuilder list;
private final Map<? extends RexNode, Boolean> exprNullableMap;
private final RexToLixTranslator parent;
@@ -664,7 +664,16 @@ public class RexToLixTranslator {
nullAs = RexImpTable.NullAs.NOT_POSSIBLE;
}
switch (expr.getKind()) {
- case INPUT_REF: {
+ case INPUT_REF:
+ {
+ final int index = ((RexInputRef) expr).getIndex();
+ Expression x = inputGetter.field(list, index, storageType);
+
+ Expression input = list.append("inp" + index + "_", x); // safe to share
+ return handleNullUnboxingIfNecessary(input, nullAs, storageType);
+ }
+ case PATTERN_INPUT_REF:
+ {
final int index = ((RexInputRef) expr).getIndex();
Expression x = inputGetter.field(list, index, storageType);
diff --git a/core/src/main/java/org/apache/calcite/rel/core/Match.java b/core/src/main/java/org/apache/calcite/rel/core/Match.java
index 043fe08..38fede5 100644
--- a/core/src/main/java/org/apache/calcite/rel/core/Match.java
+++ b/core/src/main/java/org/apache/calcite/rel/core/Match.java
@@ -192,7 +192,7 @@ public abstract class Match extends SingleRel {
@Override public RelWriter explainTerms(RelWriter pw) {
return super.explainTerms(pw)
- .item("partition", getPartitionKeys())
+ .item("partition", getPartitionKeys().asList())
.item("order", getOrderKeys())
.item("outputFields", getRowType().getFieldNames())
.item("allRows", isAllRows())
diff --git a/core/src/main/java/org/apache/calcite/rel/rules/AggregateFilterTransposeRule.java b/core/src/main/java/org/apache/calcite/rel/rules/AggregateFilterTransposeRule.java
index 06b0ecf..52d994f 100644
--- a/core/src/main/java/org/apache/calcite/rel/rules/AggregateFilterTransposeRule.java
+++ b/core/src/main/java/org/apache/calcite/rel/rules/AggregateFilterTransposeRule.java
@@ -90,8 +90,8 @@ public class AggregateFilterTransposeRule extends RelOptRule {
// the rule fires forever: A-F => A-F-A => A-A-F-A => A-A-A-F-A => ...
return;
}
- boolean allColumnsInAggregate = aggregate.getGroupSet().
- contains(filterColumns);
+ final boolean allColumnsInAggregate =
+ aggregate.getGroupSet().contains(filterColumns);
final Aggregate newAggregate =
aggregate.copy(aggregate.getTraitSet(), input,
newGroupSet, null, aggregate.getAggCallList());
diff --git a/core/src/main/java/org/apache/calcite/rel/rules/SortJoinCopyRule.java b/core/src/main/java/org/apache/calcite/rel/rules/SortJoinCopyRule.java
index d6eab35..7bdea42 100644
--- a/core/src/main/java/org/apache/calcite/rel/rules/SortJoinCopyRule.java
+++ b/core/src/main/java/org/apache/calcite/rel/rules/SortJoinCopyRule.java
@@ -31,20 +31,21 @@ import org.apache.calcite.rel.metadata.RelMdUtil;
import org.apache.calcite.rel.metadata.RelMetadataQuery;
import org.apache.calcite.tools.RelBuilderFactory;
-
import java.util.ArrayList;
import java.util.List;
/**
* Planner rule that copies a {@link org.apache.calcite.rel.core.Sort} past a
- * {@link org.apache.calcite.rel.core.Join} without its limit and offset.
- * The original {@link org.apache.calcite.rel.core.Sort} is preserved but
- * can be potentially removed by {@link org.apache.calcite.rel.rules.SortRemoveRule} if redundant.
+ * {@link org.apache.calcite.rel.core.Join} without its limit and offset. The
+ * original {@link org.apache.calcite.rel.core.Sort} is preserved but can be
+ * potentially removed by {@link org.apache.calcite.rel.rules.SortRemoveRule} if
+ * redundant.
*
- * Some examples where {@link org.apache.calcite.rel.rules.SortJoinCopyRule} can be useful are:
- * allowing a {@link org.apache.calcite.rel.core.Sort} to be incorporated in an index scan,
- * facilitating the use of operators requiring sorted inputs,
- * and allowing the sort to be performed on a possibly smaller result.
+ * <p>Some examples where {@link org.apache.calcite.rel.rules.SortJoinCopyRule}
+ * can be useful: allowing a {@link org.apache.calcite.rel.core.Sort} to be
+ * incorporated in an index scan; facilitating the use of operators requiring
+ * sorted inputs; and allowing the sort to be performed on a possibly smaller
+ * result.
*/
public class SortJoinCopyRule extends RelOptRule {
diff --git a/core/src/main/java/org/apache/calcite/rel/rules/SubQueryRemoveRule.java b/core/src/main/java/org/apache/calcite/rel/rules/SubQueryRemoveRule.java
index 39b257a..e71ffe6 100644
--- a/core/src/main/java/org/apache/calcite/rel/rules/SubQueryRemoveRule.java
+++ b/core/src/main/java/org/apache/calcite/rel/rules/SubQueryRemoveRule.java
@@ -196,8 +196,8 @@ public abstract class SubQueryRemoveRule extends RelOptRule {
// cross join (
// select max(deptno) as m, count(*) as c, count(deptno) as d
// from emp) as q
- builder.push(e.rel).
- aggregate(builder.groupKey(),
+ builder.push(e.rel)
+ .aggregate(builder.groupKey(),
builder.aggregateCall(minMax, builder.field(0)).as("m"),
builder.count(false, "c"),
builder.count(false, "d", builder.field(0)))
diff --git a/core/src/main/java/org/apache/calcite/runtime/Automaton.java b/core/src/main/java/org/apache/calcite/runtime/Automaton.java
index 594bf17..27fd6d6 100644
--- a/core/src/main/java/org/apache/calcite/runtime/Automaton.java
+++ b/core/src/main/java/org/apache/calcite/runtime/Automaton.java
@@ -16,19 +16,21 @@
*/
package org.apache.calcite.runtime;
+import org.apache.calcite.rel.core.Match;
import org.apache.calcite.util.ImmutableBitSet;
import com.google.common.collect.ImmutableList;
import java.util.Objects;
-/** A finite-state automaton.
+/** A nondeterministic finite-state automaton (NFA).
*
- * <p>It is used to implement the {@link org.apache.calcite.rel.core.Match}
+ * <p>It is used to implement the {@link Match}
* relational expression (for the {@code MATCH_RECOGNIZE} clause in SQL).
*
* @see Pattern
* @see AutomatonBuilder
+ * @see DeterministicAutomaton
*/
public class Automaton {
final State startState;
@@ -77,6 +79,14 @@ public class Automaton {
}
}
+ public ImmutableList<SymbolTransition> getTransitions() {
+ return this.transitions;
+ }
+
+ public ImmutableList<EpsilonTransition> getEpsilonTransitions() {
+ return this.epsilonTransitions;
+ }
+
/** Node in the finite-state automaton. A state has a number of
* transitions to other states, each labeled with the symbol that
* causes that transition. */
@@ -86,6 +96,22 @@ public class Automaton {
State(int id) {
this.id = id;
}
+
+ @Override public boolean equals(Object o) {
+ return o == this
+ || o instanceof State
+ && ((State) o).id == id;
+ }
+
+ @Override public int hashCode() {
+ return Objects.hash(id);
+ }
+
+ @Override public String toString() {
+ return "State{"
+ + "id=" + id
+ + '}';
+ }
}
/** Transition from one state to another in the finite-state automaton. */
diff --git a/core/src/main/java/org/apache/calcite/runtime/AutomatonBuilder.java b/core/src/main/java/org/apache/calcite/runtime/AutomatonBuilder.java
index acc52d8..b35d79c 100644
--- a/core/src/main/java/org/apache/calcite/runtime/AutomatonBuilder.java
+++ b/core/src/main/java/org/apache/calcite/runtime/AutomatonBuilder.java
@@ -70,6 +70,15 @@ public class AutomatonBuilder {
final Pattern.SymbolPattern pSymbol = (Pattern.SymbolPattern) p;
return symbol(fromState, toState, pSymbol.name);
+ case OR:
+ final Pattern.OpPattern pOr = (Pattern.OpPattern) p;
+ return or(fromState, toState, pOr.patterns.get(0), pOr.patterns.get(1));
+
+ case OPTIONAL:
+ // Rewrite as {0,1}
+ final Pattern.OpPattern pOptional = (Pattern.OpPattern) p;
+ return optional(fromState, toState, pOptional.patterns.get(0));
+
default:
throw new AssertionError("unknown op " + p.op);
}
@@ -134,6 +143,21 @@ public class AutomatonBuilder {
return this;
}
+ /** Adds a transition for the 'or' pattern. */
+ AutomatonBuilder or(State fromState, State toState, Pattern left,
+ Pattern right) {
+ //
+ // left
+ // / --------> toState
+ // fromState
+ // \ --------> toState
+ // right
+
+ add(left, fromState, toState);
+ add(right, fromState, toState);
+ return this;
+ }
+
/** Adds a transition made up of the Kleene star applied to a pattern. */
AutomatonBuilder star(State fromState, State toState, Pattern pattern) {
//
@@ -202,6 +226,12 @@ public class AutomatonBuilder {
transitionList.add(new EpsilonTransition(prevState, toState));
return this;
}
+
+ private AutomatonBuilder optional(State fromState, State toState, Pattern pattern) {
+ add(pattern, fromState, toState);
+ transitionList.add(new EpsilonTransition(fromState, toState));
+ return this;
+ }
}
// End AutomatonBuilder.java
diff --git a/core/src/main/java/org/apache/calcite/runtime/DeterministicAutomaton.java b/core/src/main/java/org/apache/calcite/runtime/DeterministicAutomaton.java
new file mode 100644
index 0000000..8dd47aa
--- /dev/null
+++ b/core/src/main/java/org/apache/calcite/runtime/DeterministicAutomaton.java
@@ -0,0 +1,188 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to you under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.calcite.runtime;
+
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableSet;
+
+import java.util.HashSet;
+import java.util.Objects;
+import java.util.Optional;
+import java.util.Set;
+import java.util.stream.Collectors;
+
+/**
+ * A deterministic finite automaton (DFA).
+ *
+ * <p>It is constructed from a
+ * {@link Automaton nondeterministic finite state automaton (NFA)}.
+ */
+public class DeterministicAutomaton {
+ final MultiState startState;
+ private final Automaton automaton;
+ private final ImmutableSet<MultiState> endStates;
+ private final ImmutableList<Transition> transitions;
+
+ /** Constructs the DFA from an epsilon-NFA. */
+ DeterministicAutomaton(Automaton automaton) {
+ this.automaton = Objects.requireNonNull(automaton);
+ // Calculate eps closure of start state
+ final Set<MultiState> traversedStates = new HashSet<>();
+ // Add transitions
+ this.startState = epsilonClosure(automaton.startState);
+
+ final ImmutableList.Builder<Transition> transitionsBuilder =
+ ImmutableList.builder();
+ traverse(startState, transitionsBuilder, traversedStates);
+ // Store transitions
+ transitions = transitionsBuilder.build();
+
+ // Calculate final States
+ final ImmutableSet.Builder<MultiState> endStateBuilder =
+ ImmutableSet.builder();
+ traversedStates.stream()
+ .filter(ms -> ms.contains(automaton.endState))
+ .forEach(endStateBuilder::add);
+ this.endStates = endStateBuilder.build();
+ }
+
+ MultiState getStartState() {
+ return startState;
+ }
+
+ public ImmutableSet<MultiState> getEndStates() {
+ return endStates;
+ }
+
+ public ImmutableList<Transition> getTransitions() {
+ return transitions;
+ }
+
+ private void traverse(MultiState start,
+ ImmutableList.Builder<Transition> transitionsBuilder,
+ Set<MultiState> traversedStates) {
+ traversedStates.add(start);
+ final Set<MultiState> newStates = new HashSet<>();
+ for (int symbol = 0; symbol < automaton.symbolNames.size(); symbol++) {
+ final Optional<MultiState> next = addTransitions(start, symbol, transitionsBuilder);
+ next.ifPresent(newStates::add);
+ }
+ // Remove all already known states
+ newStates.removeAll(traversedStates);
+ // If we have really new States, then traverse them
+ newStates.forEach(s -> traverse(s, transitionsBuilder, traversedStates));
+ }
+
+ private Optional<MultiState> addTransitions(MultiState start, int symbol,
+ ImmutableList.Builder<Transition> transitionsBuilder) {
+ final ImmutableSet.Builder<Automaton.State> builder = ImmutableSet.builder();
+ for (Automaton.SymbolTransition transition : this.automaton.getTransitions()) {
+ // Consider only transitions for the given symbol
+ if (transition.symbol != symbol) {
+ continue;
+ }
+ // Consider only those emitting from current state
+ if (!start.contains(transition.fromState)) {
+ continue;
+ }
+ // ...
+ builder.addAll(epsilonClosure(transition.toState).states);
+ }
+ final ImmutableSet<Automaton.State> stateSet = builder.build();
+ if (stateSet.isEmpty()) {
+ return Optional.empty();
+ }
+ final MultiState next = new MultiState(builder.build());
+ final Transition transition =
+ new Transition(start, next, symbol, automaton.symbolNames.get(symbol));
+ // Add the state to the list and add the transition in the table
+ transitionsBuilder.add(transition);
+ return Optional.of(next);
+ }
+
+ private MultiState epsilonClosure(Automaton.State state) {
+ final Set<Automaton.State> closure = new HashSet<>();
+ finder(state, closure);
+ return new MultiState(ImmutableSet.copyOf(closure));
+ }
+
+ private void finder(Automaton.State state, Set<Automaton.State> closure) {
+ closure.add(state);
+ final Set<Automaton.State> newStates =
+ automaton.getEpsilonTransitions().stream()
+ .filter(t -> t.fromState.equals(state))
+ .map(t -> t.toState)
+ .collect(Collectors.toSet());
+ newStates.removeAll(closure);
+ // Recursively call all "new" states
+ for (Automaton.State s : newStates) {
+ finder(s, closure);
+ }
+ }
+
+ /** Transition between states. */
+ static class Transition {
+ final MultiState fromState;
+ final MultiState toState;
+ final int symbolId;
+ final String symbol;
+
+ Transition(MultiState fromState, MultiState toState, int symbolId,
+ String symbol) {
+ this.fromState = Objects.requireNonNull(fromState);
+ this.toState = Objects.requireNonNull(toState);
+ this.symbolId = symbolId;
+ this.symbol = Objects.requireNonNull(symbol);
+ }
+ }
+
+ /**
+ * A state of the deterministic finite automaton. Consists of a set of states
+ * from the underlying eps-NFA.
+ */
+ static class MultiState {
+ private final ImmutableSet<Automaton.State> states;
+
+ MultiState(Automaton.State... states) {
+ this(ImmutableSet.copyOf(states));
+ }
+
+ MultiState(ImmutableSet<Automaton.State> states) {
+ this.states = Objects.requireNonNull(states);
+ }
+
+ public boolean contains(Automaton.State state) {
+ return states.contains(state);
+ }
+
+ @Override public boolean equals(Object o) {
+ return this == o
+ || o instanceof MultiState
+ && Objects.equals(states, ((MultiState) o).states);
+ }
+
+ @Override public int hashCode() {
+ return Objects.hash(states);
+ }
+
+ @Override public String toString() {
+ return states.toString();
+ }
+ }
+}
+
+// End DeterministicAutomaton.java
diff --git a/core/src/main/java/org/apache/calcite/runtime/Enumerables.java b/core/src/main/java/org/apache/calcite/runtime/Enumerables.java
index c8ab6a2..b3054e5 100644
--- a/core/src/main/java/org/apache/calcite/runtime/Enumerables.java
+++ b/core/src/main/java/org/apache/calcite/runtime/Enumerables.java
@@ -28,6 +28,7 @@ import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Objects;
+import java.util.concurrent.atomic.AtomicInteger;
import java.util.function.Consumer;
import java.util.function.Supplier;
@@ -73,7 +74,7 @@ public class Enumerables {
Enumerable<E> enumerable,
final Function1<E, TKey> keySelector,
Matcher<E> matcher,
- Emitter<E, TResult> emitter) {
+ Emitter<E, TResult> emitter, int history, int future) {
return new AbstractEnumerable<TResult>() {
public Enumerator<TResult> enumerator() {
return new Enumerator<TResult>() {
@@ -90,6 +91,9 @@ public class Enumerables {
/** Current result row. Null if no row is ready. */
TResult resultRow;
+ /** Match counter is 1 based in Oracle */
+ final AtomicInteger matchCounter = new AtomicInteger(1);
+
public TResult current() {
Objects.requireNonNull(resultRow);
return resultRow;
@@ -108,13 +112,19 @@ public class Enumerables {
return false;
}
++inputRow;
- final E e = inputEnumerator.current();
- final TKey key = keySelector.apply(e);
+ final E row = inputEnumerator.current();
+ final TKey key = keySelector.apply(row);
final Matcher.PartitionState<E> partitionState =
partitionStates.computeIfAbsent(key,
- k -> matcher.createPartitionState());
- matcher.matchOne(e, partitionState,
- list -> emitter.emit(list, null, 0, emitRows::add));
+ k -> matcher.createPartitionState(history, future));
+
+ partitionState.getMemoryFactory().add(row);
+
+
+ matcher.matchOne(partitionState.getRows(), partitionState,
+ // TODO 26.12.18 jf: add row states (whatever this is?)
+ list -> emitter.emit(list, null, null,
+ matchCounter.getAndIncrement(), emitRows::add));
/*
recentRows.add(e);
int earliestRetainedRow = Integer.MAX_VALUE;
@@ -178,7 +188,7 @@ public class Enumerables {
* @param <E> element type
* @param <TResult> result type */
public interface Emitter<E, TResult> {
- void emit(List<E> rows, List<Integer> rowStates, int match,
+ void emit(List<E> rows, List<Integer> rowStates, List<String> rowSymbols, int match,
Consumer<TResult> consumer);
}
}
diff --git a/core/src/main/java/org/apache/calcite/runtime/Matcher.java b/core/src/main/java/org/apache/calcite/runtime/Matcher.java
index e14da7f..a6a9b4c 100644
--- a/core/src/main/java/org/apache/calcite/runtime/Matcher.java
+++ b/core/src/main/java/org/apache/calcite/runtime/Matcher.java
@@ -16,50 +16,56 @@
*/
package org.apache.calcite.runtime;
-import org.apache.calcite.linq4j.Ord;
+import org.apache.calcite.linq4j.MemoryFactory;
import org.apache.calcite.util.ImmutableBitSet;
import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableMap;
+import com.google.common.collect.ImmutableSet;
import com.google.common.collect.Sets;
-import java.util.AbstractList;
import java.util.ArrayList;
import java.util.Arrays;
+import java.util.Collection;
import java.util.HashMap;
+import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.Set;
-import java.util.function.BiPredicate;
import java.util.function.Consumer;
+import java.util.function.Predicate;
+import java.util.stream.Collectors;
-/** Workspace that matches patterns against an automaton.
- *
- * @param <E> Type of rows matched by this automaton */
+/**
+ * Workspace that partialMatches patterns against an automaton.
+ * @param <E> Type of rows matched by this automaton
+ */
public class Matcher<E> {
- private final Automaton automaton;
- private final ImmutableList<BiPredicate<E, List<E>>> predicates;
+ private final DeterministicAutomaton dfa;
+ private final ImmutableMap<String, Predicate<MemoryFactory.Memory<E>>> predicates;
// The following members are work space. They can be shared among partitions,
// but only one thread can use them at a time. Putting them here saves the
// expense of creating a fresh object each call to "match".
- private final ImmutableBitSet emptyStateSet = ImmutableBitSet.of();
+ private final ImmutableList<Tuple<Integer>> emptyStateSet = ImmutableList.of();
private final ImmutableBitSet startSet;
private final List<Integer> rowSymbols = new ArrayList<>();
- private final ImmutableBitSet.Builder nextStateBuilder =
- ImmutableBitSet.builder();
- /** Creates a Matcher; use {@link #builder}. */
+ /**
+ * Creates a Matcher; use {@link #builder}.
+ */
private Matcher(Automaton automaton,
- ImmutableList<BiPredicate<E, List<E>>> predicates) {
- this.automaton = Objects.requireNonNull(automaton);
+ ImmutableMap<String, Predicate<MemoryFactory.Memory<E>>> predicates) {
this.predicates = Objects.requireNonNull(predicates);
final ImmutableBitSet.Builder startSetBuilder =
ImmutableBitSet.builder();
startSetBuilder.set(automaton.startState.id);
automaton.epsilonSuccessors(automaton.startState.id, startSetBuilder);
startSet = startSetBuilder.build();
+ // Build the DFA
+ dfa = new DeterministicAutomaton(automaton);
}
public static <E> Builder<E> builder(Automaton automaton) {
@@ -74,115 +80,219 @@ public class Matcher<E> {
final ImmutableList.Builder<List<E>> resultMatchBuilder =
ImmutableList.builder();
final Consumer<List<E>> resultMatchConsumer = resultMatchBuilder::add;
- final PartitionState<E> partitionState = createPartitionState();
+ final PartitionState<E> partitionState = createPartitionState(0, 0);
for (E row : rows) {
- matchOne(row, partitionState, resultMatchConsumer);
+ partitionState.getMemoryFactory().add(row);
+ matchOne(partitionState.getRows(), partitionState, resultMatchConsumer);
}
return resultMatchBuilder.build();
}
- public PartitionState<E> createPartitionState() {
- return new PartitionState<>();
+ public PartitionState<E> createPartitionState(int history, int future) {
+ return new PartitionState<>(history, future);
}
- /** Feeds a single input row into the given partition state,
- * and writes the resulting output rows (if any). */
- protected void matchOne(E row, PartitionState<E> partitionState,
- Consumer<List<E>> resultMatches) {
- // Add this row to the states.
- partitionState.bufferedRows.add(row);
- partitionState.stateSets.add(startSet);
-
- // Compute the set of symbols whose predicates that evaluate to true
- // for this row.
- rowSymbols.clear();
- for (Ord<BiPredicate<E, List<E>>> predicate : Ord.zip(predicates)) {
- if (predicate.e.test(row, partitionState.bufferedRows)) {
- rowSymbols.add(predicate.i);
- }
+ /**
+ * Feeds a single input row into the given partition state,
+ * and writes the resulting output rows (if any).
+ * This method ignores the symbols that caused a transition.
+ */
+ protected void matchOne(MemoryFactory.Memory<E> rows,
+ PartitionState<E> partitionState, Consumer<List<E>> resultMatches) {
+ List<PartialMatch<E>> matches = matchOneWithSymbols(rows, partitionState);
+ for (PartialMatch<E> pm : matches) {
+ resultMatches.accept(pm.rows);
}
+ }
- // TODO: Should we short-cut if symbols is empty?
- // TODO: Merge states with epsilon-successors
+ protected List<PartialMatch<E>> matchOneWithSymbols(MemoryFactory.Memory<E> rows,
+ PartitionState<E> partitionState) {
+ final HashSet<PartialMatch<E>> newMatches = new HashSet<>();
+ for (Map.Entry<String, Predicate<MemoryFactory.Memory<E>>> predicate
+ : predicates.entrySet()) {
+ for (PartialMatch<E> pm : partitionState.getPartialMatches()) {
+ // Remove this match
+ if (predicate.getValue().test(rows)) {
+ // Check if we have transitions from here
+ final List<DeterministicAutomaton.Transition> transitions =
+ dfa.getTransitions().stream()
+ .filter(t -> predicate.getKey().equals(t.symbol))
+ .filter(t -> pm.currentState.equals(t.fromState))
+ .collect(Collectors.toList());
- // Now process the states of matches, oldest first, and compute the
- // successors based on the predicates that are true for the current
- // row.
- for (int i = 0; i < partitionState.stateSets.size();) {
- final ImmutableBitSet stateSet = partitionState.stateSets.get(i);
- assert nextStateBuilder.isEmpty();
- for (int symbol : rowSymbols) {
- for (int state : stateSet) {
- automaton.successors(state, symbol, nextStateBuilder);
+ for (DeterministicAutomaton.Transition transition : transitions) {
+ // System.out.println("Append new transition to ");
+ final PartialMatch<E> newMatch = pm.append(transition.symbol,
+ rows.get(), transition.toState);
+ newMatches.add(newMatch);
+ }
}
}
- final ImmutableBitSet nextStateSet = nextStateBuilder.buildAndReset();
- if (nextStateSet.isEmpty()) {
- if (i == 0) {
- // Don't add the stateSet if it is empty and would be the oldest.
- // The first item in stateSets must not be empty.
- partitionState.bufferedRows.remove(0);
- partitionState.stateSets.remove(0);
- } else {
- partitionState.stateSets.set(i++, emptyStateSet);
- }
- } else if (nextStateSet.get(automaton.endState.id)) {
- resultMatches.accept(
- ImmutableList.copyOf(
- partitionState.bufferedRows.subList(i,
- partitionState.bufferedRows.size())));
- if (i == 0) {
- // Don't add the stateSet if it is empty and would be the oldest.
- // The first item in stateSets must not be empty.
- partitionState.bufferedRows.remove(0);
- partitionState.stateSets.remove(0);
- } else {
- // Set state to empty so that it is not considered for any
- // further matches, and will be removed when it is the oldest.
- partitionState.stateSets.set(i++, emptyStateSet);
+ // Check if a new Match starts here
+ if (predicate.getValue().test(rows)) {
+ final List<DeterministicAutomaton.Transition> transitions =
+ dfa.getTransitions().stream()
+ .filter(t -> predicate.getKey().equals(t.symbol))
+ .filter(t -> dfa.startState.equals(t.fromState))
+ .collect(Collectors.toList());
+
+ for (DeterministicAutomaton.Transition transition : transitions) {
+ final PartialMatch<E> newMatch = new PartialMatch<>(-1L,
+ ImmutableList.of(transition.symbol), ImmutableList.of(rows.get()),
+ transition.toState);
+ newMatches.add(newMatch);
}
- } else {
- partitionState.stateSets.set(i++, nextStateSet);
}
}
+
+ // Remove all current partitions
+ partitionState.clearPartitions();
+ // Add all partial matches
+ partitionState.addPartialMatches(newMatches);
+ // Check if one of the new Matches is in a final state, otherwise add them
+ // and go on
+ final ImmutableList.Builder<PartialMatch<E>> builder =
+ ImmutableList.builder();
+ for (PartialMatch<E> match : newMatches) {
+ if (dfa.getEndStates().contains(match.currentState)) {
+ // This is the match, handle all "open" partial matches with a suitable
+ // strategy
+ // TODO add strategy
+ // Return it!
+ builder.add(match);
+ }
+ }
+ return builder.build();
}
- /** State for each partition.
+ /**
+ * State for each partition.
*
- * @param <E> Row type */
+ * @param <E> Row type
+ */
static class PartitionState<E> {
- /** Rows that have arrived recently and might yield a match. */
- final CircularArrayList<E> bufferedRows =
- new CircularArrayList<>();
-
- /** The state of each recent row.
- *
- * <p>This collection always has the same number of entries as
- * {@link #bufferedRows}.
- *
- * <p>Because this automaton is non-deterministic, a row may be in more
- * than more than one state at a time, hence we use a bit set rather than
- * an integer.
- */
- final CircularArrayList<ImmutableBitSet> stateSets =
- new CircularArrayList<>();
+ private final Set<PartialMatch<E>> partialMatches = new HashSet<>();
+ private final MemoryFactory<E> memoryFactory;
+
+ PartitionState(int history, int future) {
+ this.memoryFactory = new MemoryFactory<>(history, future);
+ }
+
+ public void addPartialMatches(Collection<PartialMatch<E>> matches) {
+ partialMatches.addAll(matches);
+ }
+
+ public Set<PartialMatch<E>> getPartialMatches() {
+ return ImmutableSet.copyOf(partialMatches);
+ }
+
+ public void removePartialMatch(PartialMatch<E> pm) {
+ partialMatches.remove(pm);
+ }
+
+ public void clearPartitions() {
+ partialMatches.clear();
+ }
+
+ public MemoryFactory.Memory<E> getRows() {
+ return memoryFactory.create();
+ }
+
+ public MemoryFactory<E> getMemoryFactory() {
+ return this.memoryFactory;
+ }
}
- /** Builds a Matcher.
+ /**
+ * Partial match of the NFA.
*
- * @param <E> Type of rows matched by this automaton */
+ * <p>This class is immutable; the {@link #copy()} and
+ * {@link #append(String, Object, DeterministicAutomaton.MultiState)}
+ * methods generate new instances.
+ *
+ * @param <E> Row type
+ */
+ static class PartialMatch<E> {
+ final long startRow;
+ final ImmutableList<String> symbols;
+ final ImmutableList<E> rows;
+ final DeterministicAutomaton.MultiState currentState;
+
+ PartialMatch(long startRow, ImmutableList<String> symbols,
+ ImmutableList<E> rows, DeterministicAutomaton.MultiState currentState) {
+ this.startRow = startRow;
+ this.symbols = symbols;
+ this.rows = rows;
+ this.currentState = currentState;
+ }
+
+ public PartialMatch<E> copy() {
+ return new PartialMatch<>(startRow, symbols, rows, currentState);
+ }
+
+ public PartialMatch<E> append(String symbol, E row,
+ DeterministicAutomaton.MultiState toState) {
+ ImmutableList<String> symbols = ImmutableList.<String>builder()
+ .addAll(this.symbols)
+ .add(symbol)
+ .build();
+ ImmutableList<E> rows = ImmutableList.<E>builder()
+ .addAll(this.rows)
+ .add(row)
+ .build();
+ return new PartialMatch<>(startRow, symbols, rows, toState);
+ }
+
+ @Override public boolean equals(Object o) {
+ return o == this
+ || o instanceof PartialMatch
+ && startRow == ((PartialMatch) o).startRow
+ && Objects.equals(symbols, ((PartialMatch) o).symbols)
+ && Objects.equals(rows, ((PartialMatch) o).rows)
+ && Objects.equals(currentState, ((PartialMatch) o).currentState);
+ }
+
+ @Override public int hashCode() {
+ return Objects.hash(startRow, symbols, rows, currentState);
+ }
+
+ @Override public String toString() {
+ final StringBuilder sb = new StringBuilder();
+ sb.append("[");
+ for (int i = 0; i < rows.size(); i++) {
+ if (i > 0) {
+ sb.append(", ");
+ }
+ sb.append("(");
+ sb.append(symbols.get(i));
+ sb.append(", ");
+ sb.append(rows.get(i));
+ sb.append(")");
+ }
+ sb.append("]");
+ return sb.toString();
+ }
+ }
+
+ /**
+ * Builds a Matcher.
+ *
+ * @param <E> Type of rows matched by this automaton
+ */
public static class Builder<E> {
final Automaton automaton;
- final Map<String, BiPredicate<E, List<E>>> symbolPredicates =
+ final Map<String, Predicate<MemoryFactory.Memory<E>>> symbolPredicates =
new HashMap<>();
Builder(Automaton automaton) {
this.automaton = automaton;
}
- /** Associates a predicate with a symbol. */
+ /**
+ * Associates a predicate with a symbol.
+ */
public Builder<E> add(String symbolName,
- BiPredicate<E, List<E>> predicate) {
+ Predicate<MemoryFactory.Memory<E>> predicate) {
symbolPredicates.put(symbolName, predicate);
return this;
}
@@ -196,29 +306,46 @@ public class Matcher<E> {
+ predicateSymbolsNotInGraph + "] are in graph ["
+ automaton.symbolNames + "]");
}
- final ImmutableList.Builder<BiPredicate<E, List<E>>> builder =
- ImmutableList.builder();
+ final ImmutableMap.Builder<String, Predicate<MemoryFactory.Memory<E>>> builder =
+ ImmutableMap.builder();
for (String symbolName : automaton.symbolNames) {
// If a symbol does not have a predicate, it defaults to true.
// By convention, "STRT" is used for the start symbol, but it could be
// anything.
- builder.add(
- symbolPredicates.getOrDefault(symbolName, (e, list) -> true));
+ builder.put(symbolName,
+ symbolPredicates.getOrDefault(symbolName, e -> true));
}
return new Matcher<>(automaton, builder.build());
}
}
- /** Temporary. */
- private static class CircularArrayList<E> extends AbstractList<E> {
- @Override
- public E get(int index) {
- return null;
+ /**
+ * Represents a Tuple of a symbol and a row
+ *
+ * @param <E> Type of Row
+ */
+ static class Tuple<E> {
+ final String symbol;
+ final E row;
+
+ Tuple(String symbol, E row) {
+ this.symbol = symbol;
+ this.row = row;
+ }
+
+ @Override public boolean equals(Object o) {
+ return o == this
+ || o instanceof Tuple
+ && ((Tuple) o).symbol.equals(symbol)
+ && Objects.equals(row, ((Tuple) o).row);
+ }
+
+ @Override public int hashCode() {
+ return Objects.hash(symbol, row);
}
- @Override
- public int size() {
- return 0;
+ @Override public String toString() {
+ return "(" + symbol + ", " + row + ")";
}
}
}
diff --git a/core/src/main/java/org/apache/calcite/runtime/Pattern.java b/core/src/main/java/org/apache/calcite/runtime/Pattern.java
index 99b2e9a..60e01c5 100644
--- a/core/src/main/java/org/apache/calcite/runtime/Pattern.java
+++ b/core/src/main/java/org/apache/calcite/runtime/Pattern.java
@@ -38,6 +38,10 @@ public interface Pattern {
enum Op {
/** A leaf pattern, consisting of a single symbol. */
SYMBOL(0, 0),
+ /** Anchor for start "^" */
+ ANCHOR_START(0, 0),
+ /** Anchor for end "$" */
+ ANCHOR_END(0, 0),
/** Pattern that matches one pattern followed by another. */
SEQ(2, -1),
/** Pattern that matches one pattern or another. */
@@ -48,7 +52,9 @@ public interface Pattern {
PLUS(1, 1),
/** Pattern that matches a pattern repeated between {@code minRepeat}
* and {@code maxRepeat} times. */
- REPEAT(1, 1);
+ REPEAT(1, 1),
+ /** Pattern that machtes a pattern one time or zero times */
+ OPTIONAL(1, 1);
private final int minArity;
private final int maxArity;
@@ -119,6 +125,10 @@ public interface Pattern {
* of the stack,
* and pushes it onto the stack. */
public PatternBuilder or() {
+ if (stack.size() < 2) {
+ throw new AssertionError("Expecting stack to have at least 2 items, but has "
+ + stack.size());
+ }
final Pattern pattern1 = stack.pop();
final Pattern pattern0 = stack.pop();
return push(new OpPattern(Op.OR, pattern0, pattern1));
@@ -128,6 +138,12 @@ public interface Pattern {
final Pattern pattern = stack.pop();
return push(new RepeatPattern(minRepeat, maxRepeat, pattern));
}
+
+ public PatternBuilder optional() {
+ final Pattern pattern = stack.pop();
+ return push(new OpPattern(Op.OPTIONAL, pattern));
+ }
+
}
/** Base class for implementations of {@link Pattern}. */
@@ -179,6 +195,10 @@ public interface Pattern {
return "(" + patterns.get(0) + ")*";
case PLUS:
return "(" + patterns.get(0) + ")+";
+ case OR:
+ return patterns.get(0) + "|" + patterns.get(1);
+ case OPTIONAL:
+ return patterns.get(0) + "?";
default:
throw new AssertionError("unknown op " + op);
}
diff --git a/core/src/main/java/org/apache/calcite/util/BuiltInMethod.java b/core/src/main/java/org/apache/calcite/util/BuiltInMethod.java
index 83a25db..dd3ae8b 100644
--- a/core/src/main/java/org/apache/calcite/util/BuiltInMethod.java
+++ b/core/src/main/java/org/apache/calcite/util/BuiltInMethod.java
@@ -36,6 +36,7 @@ import org.apache.calcite.linq4j.Enumerator;
import org.apache.calcite.linq4j.ExtendedEnumerable;
import org.apache.calcite.linq4j.JoinType;
import org.apache.calcite.linq4j.Linq4j;
+import org.apache.calcite.linq4j.MemoryFactory;
import org.apache.calcite.linq4j.QueryProvider;
import org.apache.calcite.linq4j.Queryable;
import org.apache.calcite.linq4j.function.EqualityComparer;
@@ -167,7 +168,7 @@ public enum BuiltInMethod {
HASH_JOIN(ExtendedEnumerable.class, "hashJoin", Enumerable.class, Function1.class,
Function1.class, Function2.class),
MATCH(Enumerables.class, "match", Enumerable.class, Function1.class,
- Matcher.class, Enumerables.Emitter.class),
+ Matcher.class, Enumerables.Emitter.class, int.class, int.class),
PATTERN_BUILDER(Utilities.class, "patternBuilder"),
PATTERN_BUILDER_SYMBOL(Pattern.PatternBuilder.class, "symbol", String.class),
PATTERN_BUILDER_SEQ(Pattern.PatternBuilder.class, "seq"),
@@ -175,10 +176,10 @@ public enum BuiltInMethod {
PATTERN_TO_AUTOMATON(Pattern.PatternBuilder.class, "automaton"),
MATCHER_BUILDER(Matcher.class, "builder", Automaton.class),
MATCHER_BUILDER_ADD(Matcher.Builder.class, "add", String.class,
- BiPredicate.class),
+ Predicate.class),
MATCHER_BUILDER_BUILD(Matcher.Builder.class, "build"),
EMITTER_EMIT(Enumerables.Emitter.class, "emit", List.class, List.class,
- int.class, Consumer.class),
+ List.class, int.class, Consumer.class),
MERGE_JOIN(EnumerableDefaults.class, "mergeJoin", Enumerable.class,
Enumerable.class, Function1.class, Function1.class, Function2.class,
boolean.class, boolean.class),
@@ -245,6 +246,8 @@ public enum BuiltInMethod {
AS_ENUMERABLE2(Linq4j.class, "asEnumerable", Iterable.class),
ENUMERABLE_TO_LIST(ExtendedEnumerable.class, "toList"),
AS_LIST(Primitive.class, "asList", Object.class),
+ MEMORY_GET0(MemoryFactory.Memory.class, "get"),
+ MEMORY_GET1(MemoryFactory.Memory.class, "get", int.class),
ENUMERATOR_CURRENT(Enumerator.class, "current"),
ENUMERATOR_MOVE_NEXT(Enumerator.class, "moveNext"),
ENUMERATOR_CLOSE(Enumerator.class, "close"),
diff --git a/core/src/test/java/org/apache/calcite/runtime/AutomatonTest.java b/core/src/test/java/org/apache/calcite/runtime/AutomatonTest.java
index 36f166e..e7ec2db 100644
--- a/core/src/test/java/org/apache/calcite/runtime/AutomatonTest.java
+++ b/core/src/test/java/org/apache/calcite/runtime/AutomatonTest.java
@@ -16,6 +16,10 @@
*/
package org.apache.calcite.runtime;
+import org.apache.calcite.linq4j.MemoryFactory;
+
+import com.google.common.collect.ImmutableList;
+
import org.junit.Test;
import java.util.AbstractList;
@@ -33,7 +37,7 @@ public class AutomatonTest {
final String[] rows = {"", "a", "", "a"};
final Matcher<String> matcher =
Matcher.<String>builder(p.toAutomaton())
- .add("a", (s, list) -> s.contains("a"))
+ .add("a", s -> s.get().contains("a"))
.build();
final String expected = "[[a], [a]]";
assertThat(matcher.match(rows).toString(), is(expected));
@@ -48,8 +52,8 @@ public class AutomatonTest {
final String[] rows = {"", "a", "", "ab", "a", "ab", "b", "b"};
final Matcher<String> matcher =
Matcher.<String>builder(p.toAutomaton())
- .add("a", (s, list) -> s.contains("a"))
- .add("b", (s, list) -> s.contains("b"))
+ .add("a", s -> s.get().contains("a"))
+ .add("b", s -> s.get().contains("b"))
.build();
final String expected = "[[a, ab], [ab, b]]";
assertThat(matcher.match(rows).toString(), is(expected));
@@ -65,10 +69,11 @@ public class AutomatonTest {
final String[] rows = {"", "a", "", "b", "", "ab", "a", "ab", "b", "b"};
final Matcher<String> matcher =
Matcher.<String>builder(p.toAutomaton())
- .add("a", (s, list) -> s.contains("a"))
- .add("b", (s, list) -> s.contains("b"))
+ .add("a", s -> s.get().contains("a"))
+ .add("b", s -> s.get().contains("b"))
.build();
- final String expected = "[[b], [ab], [a, ab], [ab], [b], [b]]";
+ final String expected = "[[b], [ab], [ab], [ab, a, ab], [a, ab], [b], [ab, b], [ab, a, ab, b], "
+ + "[a, ab, b], [b]]";
assertThat(matcher.match(rows).toString(), is(expected));
}
@@ -82,13 +87,51 @@ public class AutomatonTest {
final String[] rows = {"", "a", "", "b", "", "ab", "a", "ab", "b", "b"};
final Matcher<String> matcher =
Matcher.<String>builder(p.toAutomaton())
- .add("a", (s, list) -> s.contains("a"))
- .add("b", (s, list) -> s.contains("b"))
+ .add("a", s -> s.get().contains("a"))
+ .add("b", s -> s.get().contains("b"))
+ .build();
+ final String expected = "[[ab, a, ab], [a, ab], [ab, b], [ab, a, ab, b], [a, ab, b]]";
+ assertThat(matcher.match(rows).toString(), is(expected));
+ }
+
+ @Test public void testOr() {
+ // pattern(a+ b)
+ final Pattern p = Pattern.builder()
+ .symbol("a")
+ .symbol("b").or()
+ .build();
+ assertThat(p.toString(), is("a|b"));
+
+ final String[] rows = {"", "a", "", "b", "", "ab", "a", "ab", "b", "b"};
+ final Matcher<String> matcher =
+ Matcher.<String>builder(p.toAutomaton())
+ .add("a", s -> s.get().contains("a"))
+ .add("b", s -> s.get().contains("b"))
.build();
- final String expected = "[[ab, a, ab], [a, ab], [ab, b]]";
+ final String expected = "[[a], [b], [ab], [ab], [a], [ab], [ab], [b], [b]]";
assertThat(matcher.match(rows).toString(), is(expected));
}
+ @Test public void testOptional() {
+ // pattern(a+ b)
+ final Pattern p = Pattern.builder()
+ .symbol("a")
+ .symbol("b").optional().seq()
+ .symbol("c").seq()
+ .build();
+ assertThat(p.toString(), is("a b? c"));
+
+ final String rows = "acabcabbc";
+ final Matcher<Character> matcher =
+ Matcher.<Character>builder(p.toAutomaton())
+ .add("a", s -> s.get() == 'a')
+ .add("b", s -> s.get() == 'b')
+ .add("c", s -> s.get() == 'c')
+ .build();
+ final String expected = "[[a, c], [a, b, c]]";
+ assertThat(matcher.match(chars(rows)).toString(), is(expected));
+ }
+
@Test public void testRepeat() {
// pattern(a b{0, 2} c)
checkRepeat(0, 2, "a (b){0, 2} c", "[[a, c], [a, b, c], [a, b, b, c]]");
@@ -117,9 +160,9 @@ public class AutomatonTest {
final String rows = "acabcabbcabbbcabbbbcabdbc";
final Matcher<Character> matcher =
Matcher.<Character>builder(p.toAutomaton())
- .add("a", (c, list) -> c == 'a')
- .add("b", (c, list) -> c == 'b')
- .add("c", (c, list) -> c == 'c')
+ .add("a", s -> s.get() == 'a')
+ .add("b", s -> s.get() == 'b')
+ .add("c", s -> s.get() == 'c')
.build();
assertThat(matcher.match(chars(rows)).toString(), is(expected));
}
@@ -137,12 +180,40 @@ public class AutomatonTest {
final String rows = "acabcabbcabbbcabbbbcabdbcabacababcababac";
final Matcher<Character> matcher =
Matcher.<Character>builder(p.toAutomaton())
- .add("a", (c, list) -> c == 'a')
- .add("b", (c, list) -> c == 'b')
- .add("c", (c, list) -> c == 'c')
+ .add("a", s -> s.get() == 'a')
+ .add("b", s -> s.get() == 'b')
+ .add("c", s -> s.get() == 'c')
.build();
assertThat(matcher.match(chars(rows)).toString(),
- is("[[a, b, a, c], [a, b, a, b, a, c], [a, b, a, c]]"));
+ is("[[a, b, a, c], [a, b, a, c], [a, b, a, b, a, c]]"));
+ }
+
+ @Test public void testResultWithLabels() {
+ // pattern(a)
+ final Pattern p = Pattern.builder()
+ .symbol("A")
+ .symbol("B").seq()
+ .build();
+ assertThat(p.toString(), is("A B"));
+
+ final String[] rows = {"", "a", "ab", "a", "b"};
+ final Matcher<String> matcher =
+ Matcher.<String>builder(p.toAutomaton())
+ .add("A", s -> s.get().contains("a"))
+ .add("B", s -> s.get().contains("b"))
+ .build();
+ final Matcher.PartitionState<String> partitionState =
+ matcher.createPartitionState(0, 0);
+ final ImmutableList.Builder<Matcher.PartialMatch<String>> builder =
+ ImmutableList.builder();
+ MemoryFactory<String> memoryFactory = new MemoryFactory<>(0, 0);
+ for (String row : rows) {
+ memoryFactory.add(row);
+ builder.addAll(
+ matcher.matchOneWithSymbols(memoryFactory.create(), partitionState));
+ }
+ assertThat(builder.build().toString(),
+ is("[[(A, a), (B, ab)], [(A, a), (B, b)]]"));
}
/** Converts a string into an iterable collection of its characters. */
diff --git a/core/src/test/java/org/apache/calcite/runtime/DeterministicAutomatonTest.java b/core/src/test/java/org/apache/calcite/runtime/DeterministicAutomatonTest.java
new file mode 100644
index 0000000..db02b95
--- /dev/null
+++ b/core/src/test/java/org/apache/calcite/runtime/DeterministicAutomatonTest.java
@@ -0,0 +1,104 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to you under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.calcite.runtime;
+
+import org.junit.Test;
+
+import static org.hamcrest.core.Is.is;
+import static org.junit.Assert.assertThat;
+
+/** Tests for the {@link DeterministicAutomaton} */
+public class DeterministicAutomatonTest {
+ @Test public void convertAutomaton() {
+ final Pattern.PatternBuilder builder = Pattern.builder();
+ final Pattern pattern = builder.symbol("A")
+ .repeat(1, 2)
+ .build();
+ final Automaton automaton = pattern.toAutomaton();
+
+ final DeterministicAutomaton da =
+ new DeterministicAutomaton(automaton);
+
+ assertThat(da.startState,
+ is(
+ new DeterministicAutomaton.MultiState(new Automaton.State(0),
+ new Automaton.State(2))));
+
+ // Result should have three states
+ // 0 -A-> 1 -A-> 2
+ // 1 and 2 should be final
+ assertThat(da.getTransitions().size(), is(2));
+ assertThat(da.getEndStates().size(), is(2));
+ }
+
+ @Test public void convertAutomaton2() {
+ final Pattern.PatternBuilder builder = Pattern.builder();
+ final Pattern pattern = builder
+ .symbol("A")
+ .symbol("B")
+ .or()
+ .build();
+ final Automaton automaton = pattern.toAutomaton();
+
+ final DeterministicAutomaton da =
+ new DeterministicAutomaton(automaton);
+
+ // Result should have two transitions
+ // 0 -A-> 1
+ // -B->
+ // 1 should be final
+ assertThat(da.getTransitions().size(), is(2));
+ assertThat(da.getEndStates().size(), is(1));
+ }
+
+ @Test public void convertAutomaton3() {
+ final Pattern.PatternBuilder builder = Pattern.builder();
+ final Pattern pattern = builder
+ .symbol("A")
+ .symbol("B").star().seq()
+ .build();
+ final Automaton automaton = pattern.toAutomaton();
+
+ final DeterministicAutomaton da =
+ new DeterministicAutomaton(automaton);
+
+ // Result should have two transitions
+ // 0 -A-> 1 -B-> 2 (which again goes to 2 on a "B")
+ // 1 should be final
+ assertThat(da.getTransitions().size(), is(3));
+ assertThat(da.getEndStates().size(), is(2));
+ }
+
+ @Test public void convertAutomaton4() {
+ final Pattern.PatternBuilder builder = Pattern.builder();
+ final Pattern pattern = builder
+ .symbol("A")
+ .symbol("B").optional().seq()
+ .symbol("A").seq()
+ .build();
+ final Automaton automaton = pattern.toAutomaton();
+
+ final DeterministicAutomaton da =
+ new DeterministicAutomaton(automaton);
+
+ // Result should have four transitions and one end state
+ assertThat(da.getTransitions().size(), is(4));
+ assertThat(da.getEndStates().size(), is(1));
+ }
+}
+
+// End DeterministicAutomatonTest.java
diff --git a/core/src/test/java/org/apache/calcite/runtime/EnumerablesTest.java b/core/src/test/java/org/apache/calcite/runtime/EnumerablesTest.java
index 41fd445..80aee31 100644
--- a/core/src/test/java/org/apache/calcite/runtime/EnumerablesTest.java
+++ b/core/src/test/java/org/apache/calcite/runtime/EnumerablesTest.java
@@ -26,11 +26,13 @@ import org.apache.calcite.linq4j.function.Predicate2;
import com.google.common.collect.Lists;
+import org.junit.Ignore;
import org.junit.Test;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
+import java.util.Locale;
import static com.google.common.collect.Lists.newArrayList;
@@ -207,6 +209,49 @@ public class EnumerablesTest {
equalTo("[]"));
}
+ @Test
+ @Ignore // TODO fix this
+ public void testMatch() {
+ final Enumerable<Emp> emps = Linq4j.asEnumerable(
+ Arrays.asList(
+ new Emp(20, "Theodore"),
+ new Emp(10, "Fred"),
+ new Emp(20, "Sebastian"),
+ new Emp(30, "Joe")));
+
+ final Pattern p =
+ Pattern.builder()
+ .symbol("A")
+ .symbol("B").seq()
+ .build();
+
+ final Matcher<Emp> matcher =
+ Matcher.<Emp>builder(p.toAutomaton())
+ .add("A", s -> s.get().deptno == 20)
+ .add("B", s -> s.get().deptno != 20)
+ .build();
+
+ final Enumerables.Emitter<Emp, String> emitter =
+ (rows, rowStates, rowSymbols, match, consumer) -> {
+ for (int i = 0; i < rows.size(); i++) {
+ if (rowSymbols == null) {
+ continue;
+ }
+ if ("A".equals(rowSymbols.get(i))) {
+ consumer.accept(
+ String.format(Locale.ENGLISH, "%s %s %d", rows, rowStates,
+ match));
+ }
+ }
+ };
+
+ final Enumerable<String> matches =
+ Enumerables.match(emps, emp -> 0L, matcher, emitter, 1, 1);
+ assertThat(matches.toList().toString(),
+ equalTo("[[Emp(20, Theodore), Emp(10, Fred)] null 1, "
+ + "[Emp(20, Sebastian), Emp(30, Joe)] null 2]"));
+ }
+
/** Employee record. */
private static class Emp {
final int deptno;
diff --git a/core/src/test/java/org/apache/calcite/sql/parser/parserextensiontesting/ExtensionSqlParserTest.java b/core/src/test/java/org/apache/calcite/sql/parser/parserextensiontesting/ExtensionSqlParserTest.java
index 825d072..6fafb2a 100644
--- a/core/src/test/java/org/apache/calcite/sql/parser/parserextensiontesting/ExtensionSqlParserTest.java
+++ b/core/src/test/java/org/apache/calcite/sql/parser/parserextensiontesting/ExtensionSqlParserTest.java
@@ -17,7 +17,6 @@
package org.apache.calcite.sql.parser.parserextensiontesting;
import org.apache.calcite.sql.SqlNode;
-import org.apache.calcite.sql.parser.SqlParseException;
import org.apache.calcite.sql.parser.SqlParserImplFactory;
import org.apache.calcite.sql.parser.SqlParserTest;
@@ -36,12 +35,12 @@ public class ExtensionSqlParserTest extends SqlParserTest {
return ExtensionSqlParserImpl.FACTORY;
}
- @Test public void testAlterSystemExtension() throws SqlParseException {
+ @Test public void testAlterSystemExtension() {
check("alter system upload jar '/path/to/jar'",
"ALTER SYSTEM UPLOAD JAR '/path/to/jar'");
}
- @Test public void testAlterSystemExtensionWithoutAlter() throws SqlParseException {
+ @Test public void testAlterSystemExtensionWithoutAlter() {
// We need to include the scope for custom alter operations
checkFails("^upload^ jar '/path/to/jar'",
"(?s).*Encountered \"upload\" at .*");
diff --git a/core/src/test/java/org/apache/calcite/test/CalciteSuite.java b/core/src/test/java/org/apache/calcite/test/CalciteSuite.java
index 1d1cd3b..f6c0e72 100644
--- a/core/src/test/java/org/apache/calcite/test/CalciteSuite.java
+++ b/core/src/test/java/org/apache/calcite/test/CalciteSuite.java
@@ -42,6 +42,7 @@ import org.apache.calcite.rel.rules.SortRemoveRuleTest;
import org.apache.calcite.rex.RexBuilderTest;
import org.apache.calcite.rex.RexExecutorTest;
import org.apache.calcite.rex.RexSqlStandardConvertletTableTest;
+import org.apache.calcite.runtime.AutomatonTest;
import org.apache.calcite.runtime.BinarySearchTest;
import org.apache.calcite.runtime.EnumerablesTest;
import org.apache.calcite.sql.SqlSetOptionOperatorTest;
@@ -124,6 +125,7 @@ import org.junit.runners.Suite;
RexProgramTest.class,
SqlOperatorBindingTest.class,
RexTransformerTest.class,
+ AutomatonTest.class,
BinarySearchTest.class,
EnumerablesTest.class,
ExceptionMessageTest.class,
diff --git a/core/src/test/java/org/apache/calcite/test/JdbcTest.java b/core/src/test/java/org/apache/calcite/test/JdbcTest.java
index a305b7e..9d8b5fa 100644
--- a/core/src/test/java/org/apache/calcite/test/JdbcTest.java
+++ b/core/src/test/java/org/apache/calcite/test/JdbcTest.java
@@ -6875,6 +6875,40 @@ public class JdbcTest {
.returns("EXPR$0=[250, 500, 1000]\n");
}
+ @Test public void testMatchSimple() {
+ final String sql = "select *\n"
+ + "from \"hr\".\"emps\" match_recognize (\n"
+ + " order by \"empid\" desc\n"
+ + " measures up.\"commission\" as c,\n"
+ + " up.\"empid\" as empid,\n"
+ + " 2 as two\n"
+ + " pattern (up s)\n"
+ + " define up as up.\"empid\" = 100)";
+ final String convert = ""
+ + "LogicalProject(C=[$0], EMPID=[$1], TWO=[$2])\n"
+ + " LogicalMatch(partition=[[]], order=[[0 DESC]], "
+ + "outputFields=[[C, EMPID, TWO]], allRows=[false], "
+ + "after=[FLAG(SKIP TO NEXT ROW)], pattern=[('UP', 'S')], "
+ + "isStrictStarts=[false], isStrictEnds=[false], subsets=[[]], "
+ + "patternDefinitions=[[=(CAST(PREV(UP.$0, 0)):INTEGER NOT NULL, 100)]], "
+ + "inputFields=[[empid, deptno, name, salary, commission]])\n"
+ + " EnumerableTableScan(table=[[hr, emps]])\n";
+ final String plan = "PLAN="
+ + "EnumerableMatch(partition=[[]], order=[[0 DESC]], "
+ + "outputFields=[[C, EMPID, TWO]], allRows=[false], "
+ + "after=[FLAG(SKIP TO NEXT ROW)], pattern=[('UP', 'S')], "
+ + "isStrictStarts=[false], isStrictEnds=[false], subsets=[[]], "
+ + "patternDefinitions=[[=(CAST(PREV(UP.$0, 0)):INTEGER NOT NULL, 100)]], "
+ + "inputFields=[[empid, deptno, name, salary, commission]])\n"
+ + " EnumerableTableScan(table=[[hr, emps]])";
+ CalciteAssert.that()
+ .with(CalciteAssert.Config.REGULAR)
+ .query(sql)
+ .convertContains(convert)
+ .explainContains(plan)
+ .returns("C=1000; EMPID=100; TWO=2\nC=500; EMPID=200; TWO=2\n");
+ }
+
@Test public void testMatch() {
final String sql = "select *\n"
+ "from \"hr\".\"emps\" match_recognize (\n"
@@ -6882,22 +6916,22 @@ public class JdbcTest {
+ " measures \"commission\" as c,\n"
+ " \"empid\" as empid\n"
+ " pattern (s up)\n"
- + " define up as up.\"commission\" > prev(up.\"commission\"))";
+ + " define up as up.\"commission\" < prev(up.\"commission\"))";
final String convert = ""
+ "LogicalProject(C=[$0], EMPID=[$1])\n"
- + " LogicalMatch(partition=[{}], order=[[0 DESC]], "
+ + " LogicalMatch(partition=[[]], order=[[0 DESC]], "
+ "outputFields=[[C, EMPID]], allRows=[false], "
+ "after=[FLAG(SKIP TO NEXT ROW)], pattern=[('S', 'UP')], "
+ "isStrictStarts=[false], isStrictEnds=[false], subsets=[[]], "
- + "patternDefinitions=[[>(PREV(UP.$4, 0), PREV(UP.$4, 1))]], "
+ + "patternDefinitions=[[<(PREV(UP.$4, 0), PREV(UP.$4, 1))]], "
+ "inputFields=[[empid, deptno, name, salary, commission]])\n"
+ " EnumerableTableScan(table=[[hr, emps]])\n";
final String plan = "PLAN="
- + "EnumerableMatch(partition=[{}], order=[[0 DESC]], "
+ + "EnumerableMatch(partition=[[]], order=[[0 DESC]], "
+ "outputFields=[[C, EMPID]], allRows=[false], "
+ "after=[FLAG(SKIP TO NEXT ROW)], pattern=[('S', 'UP')], "
+ "isStrictStarts=[false], isStrictEnds=[false], subsets=[[]], "
- + "patternDefinitions=[[>(PREV(UP.$4, 0), PREV(UP.$4, 1))]], "
+ + "patternDefinitions=[[<(PREV(UP.$4, 0), PREV(UP.$4, 1))]], "
+ "inputFields=[[empid, deptno, name, salary, commission]])\n"
+ " EnumerableTableScan(table=[[hr, emps]])";
CalciteAssert.that()
@@ -6905,7 +6939,7 @@ public class JdbcTest {
.query(sql)
.convertContains(convert)
.explainContains(plan)
- .returns("C=1000; EMPID=100");
+ .returns("C=1000; EMPID=100\nC=500; EMPID=200\n");
}
@Test public void testJsonType() {
diff --git a/core/src/test/java/org/apache/calcite/test/RelBuilderTest.java b/core/src/test/java/org/apache/calcite/test/RelBuilderTest.java
index 93dd716..e6e44a5 100644
--- a/core/src/test/java/org/apache/calcite/test/RelBuilderTest.java
+++ b/core/src/test/java/org/apache/calcite/test/RelBuilderTest.java
@@ -2625,7 +2625,7 @@ public class RelBuilderTest {
measuresBuilder.build(), after, subsets, false,
partitionKeysBuilder.build(), orderKeysBuilder.build(), interval)
.build();
- final String expected = "LogicalMatch(partition=[{7}], order=[[0]], "
+ final String expected = "LogicalMatch(partition=[[7]], order=[[0]], "
+ "outputFields=[[$7, 'start_nw', 'bottom_nw']], allRows=[false], "
+ "after=[FLAG(SKIP TO NEXT ROW)], pattern=[(('STRT', "
+ "PATTERN_QUANTIFIER('DOWN', 1, -1, false)), "
diff --git a/core/src/test/resources/org/apache/calcite/test/SqlToRelConverterTest.xml b/core/src/test/resources/org/apache/calcite/test/SqlToRelConverterTest.xml
index 2e52eb4..86a4273 100644
--- a/core/src/test/resources/org/apache/calcite/test/SqlToRelConverterTest.xml
+++ b/core/src/test/resources/org/apache/calcite/test/SqlToRelConverterTest.xml
@@ -241,8 +241,7 @@ LogicalProject(DEPTNO=[$0], NAME=[$1], I=[$2])
</TestCase>
<TestCase name="testSnapshotOnTemporalTable">
<Resource name="sql">
- <![CDATA[select * from products_temporal
-for system_time as of TIMESTAMP '2011-01-02 00:00:00']]>
+ <![CDATA[select * from products_temporal for system_time as of TIMESTAMP '2011-01-02 00:00:00']]>
</Resource>
<Resource name="plan">
<![CDATA[
@@ -254,8 +253,10 @@ LogicalProject(PRODUCTID=[$0], NAME=[$1], SUPPLIERID=[$2], SYS_START=[$3], SYS_E
</TestCase>
<TestCase name="testJoinTemporalTableOnSpecificTime">
<Resource name="sql">
- <![CDATA[select stream * from orders, products_temporal
-for system_time as of TIMESTAMP '2011-01-02 00:00:00']]>
+ <![CDATA[select stream *
+from orders,
+ products_temporal for system_time as of
+ TIMESTAMP '2011-01-02 00:00:00']]>
</Resource>
<Resource name="plan">
<![CDATA[
@@ -270,8 +271,10 @@ LogicalDelta
</TestCase>
<TestCase name="testJoinTemporalTableOnColumnReference">
<Resource name="sql">
- <![CDATA[select stream * from orders join products_temporal
-for system_time as of orders.rowtime on orders.productid = products_temporal.productid]]>
+ <![CDATA[select stream *
+from orders
+join products_temporal for system_time as of orders.rowtime
+on orders.productid = products_temporal.productid]]>
</Resource>
<Resource name="plan">
<![CDATA[
@@ -288,9 +291,12 @@ LogicalDelta
<TestCase name="testCrossJoinTemporalTable1">
<Resource name="sql">
<![CDATA[select stream *
- from orders
- join products_temporal for system_time as of orders.rowtime
- on orders.productid = products_temporal.productid]]>
+from orders
+cross join lateral (
+ select * from products_temporal for system_time
+ as of orders.rowtime
+ where orders.productid = products_temporal.productid)
+]]>
</Resource>
<Resource name="plan">
<![CDATA[
@@ -308,11 +314,12 @@ LogicalDelta
<TestCase name="testCrossJoinTemporalTable2">
<Resource name="sql">
<![CDATA[select stream *
- from orders
- cross join lateral (
- select * from products_temporal for system_time
- as of TIMESTAMP '2011-01-02 00:00:00'
- where orders.productid = products_temporal.productid)]]>
+from orders
+cross join lateral (
+ select * from products_temporal for system_time
+ as of TIMESTAMP '2011-01-02 00:00:00'
+ where orders.productid = products_temporal.productid)
+]]>
</Resource>
<Resource name="plan">
<![CDATA[
@@ -329,9 +336,12 @@ LogicalDelta
<TestCase name="testCrossJoinTemporalTable3">
<Resource name="sql">
<![CDATA[select stream *
- from orders
- join products_temporal for system_time as of orders.rowtime
- on products_temporal.productid > 1]]>
+from orders
+cross join lateral (
+ select * from products_temporal for system_time
+ as of orders.rowtime
+ where products_temporal.productid > 1)
+]]>
</Resource>
<Resource name="plan">
<![CDATA[
@@ -869,6 +879,9 @@ LogicalProject(ZIP=[$4])
LogicalTableScan(table=[[CATALOG, SALES, EMP_ADDRESS]])
]]>
</Resource>
+ <Resource name="sql">
+ <![CDATA[select empa.home_address.zip from sales.emp_address empa where empa.home_address.city = 'abc']]>
+ </Resource>
</TestCase>
<TestCase name="testSelectNestedColumnType">
<Resource name="plan">
@@ -881,6 +894,23 @@ LogicalProject(UNIT_LENGTH=[CHAR_LENGTH($3)])
LogicalTableScan(table=[[CATALOG, CUSTOMER, CONTACT_PEEK]])
]]>
</Resource>
+ <Resource name="sql">
+ <![CDATA[select
+ char_length(coord."unit") as unit_length
+from
+ (
+ select
+ fname,
+ coord
+ from
+ customer.contact_peek
+ where
+ coord.x > 1
+ and coord.y > 1
+ ) as view
+where
+ fname = 'john']]>
+ </Resource>
</TestCase>
<TestCase name="testGroupByNestedColumn">
<Resource name="plan">
@@ -891,6 +921,17 @@ LogicalProject(X=[$1], A=[$0], EXPR$2=[$2])
LogicalTableScan(table=[[CATALOG, CUSTOMER, CONTACT_PEEK]])
]]>
</Resource>
+ <Resource name="sql">
+ <![CDATA[select
+ coord.x,
+ coord_ne.sub.a,
+ avg(coord.y)
+from
+ customer.contact_peek
+group by
+ coord_ne.sub.a,
+ coord.x]]>
+ </Resource>
</TestCase>
<TestCase name="testGroupingSetsWithNestedColumn">
<Resource name="plan">
@@ -901,16 +942,41 @@ LogicalProject(X=[$1], unit=[$2], A=[$0], EXPR$3=[$3])
LogicalTableScan(table=[[CATALOG, CUSTOMER, CONTACT_PEEK]])
]]>
</Resource>
+ <Resource name="sql">
+ <![CDATA[select
+ coord.x,
+ coord."unit",
+ coord_ne.sub.a,
+ avg(coord.y)
+from
+ customer.contact_peek
+group by
+ grouping sets (
+ (coord_ne.sub.a, coord.x, coord."unit"),
+ (coord.x, coord."unit")
+ )]]>
+ </Resource>
</TestCase>
<TestCase name="testGroupByCubeWithNestedColumn">
- <Resource name="plan">
- <![CDATA[
+ <Resource name="plan">
+ <![CDATA[
LogicalProject(X=[$1], unit=[$2], A=[$0], EXPR$3=[$3])
LogicalAggregate(group=[{0, 1, 2}], groups=[[{0, 1, 2}, {0, 1}, {0, 2}, {0}, {1, 2}, {1}, {2}, {}]], EXPR$3=[AVG($3)])
LogicalProject(A=[$5.SUB.A], X=[$4.X], unit=[$4.unit], $f3=[$4.Y])
LogicalTableScan(table=[[CATALOG, CUSTOMER, CONTACT_PEEK]])
]]>
- </Resource>
+ </Resource>
+ <Resource name="sql">
+ <![CDATA[select
+ coord.x,
+ coord."unit",
+ coord_ne.sub.a,
+ avg(coord.y)
+from
+ customer.contact_peek
+group by
+ cube (coord_ne.sub.a, coord.x, coord."unit")]]>
+ </Resource>
</TestCase>
<TestCase name="testDynamicSchemaUnnest">
<Resource name="sql">
@@ -1407,8 +1473,7 @@ last_value(deptno) over w,
last_value(deptno) ignore nulls over w,
last_value(deptno) respect nulls over w
from emp
-window w as (order by empno)
-]]>
+window w as (order by empno)]]>
</Resource>
<Resource name="plan">
<![CDATA[
@@ -1886,7 +1951,7 @@ LogicalProject(EMPNO=[$0], ENAME=[$1], JOB=[$2], MGR=[$3], HIREDATE=[$4], SAL=[$
<TestCase name="testDuplicateColumnsInSubQuery">
<Resource name="sql">
<![CDATA[select "e" from (
-select empno as "e", deptno as d, 1 as "e" from EMP)]]>
+select empno as "e", deptno as d, 1 as "e0" from EMP)]]>
</Resource>
<Resource name="plan">
<![CDATA[
@@ -2734,7 +2799,7 @@ LogicalProject(DEPTNO=[$1], EXPR$1=[$2], EXPR$2=[$3], EXPR$3=[$4])
<Resource name="plan">
<![CDATA[
LogicalProject(EMPNO=[$0], ENAME=[$1], JOB=[$2], MGR=[$3], HIREDATE=[$4], SAL=[$5], COMM=[$6], DEPTNO=[$7], SLACKER=[$8])
- LogicalMatch(partition=[[$2, $5]], order=[[2, 5 DESC, 0]], outputFields=[[EMPNO, ENAME, JOB, MGR, HIREDATE, SAL, COMM, DEPTNO, SLACKER]], allRows=[false], after=[FLAG(SKIP TO NEXT ROW)], pattern=[(('STRT', PATTERN_QUANTIFIER('DOWN', 1, -1, false)), PATTERN_QUANTIFIER('UP', 1, -1, false))], isStrictStarts=[false], isStrictEnds=[false], subsets=[[]], patternDefinitions=[[<(PREV(DOWN.$3, 0), PREV(DOWN.$3, 1)), >(PREV(UP.$3, 0), PREV(UP.$3, 1))]], inputFields=[[EMPNO, ENAME, JOB, MGR, HIRE [...]
+ LogicalMatch(partition=[[2, 5]], order=[[2, 5 DESC, 0]], outputFields=[[EMPNO, ENAME, JOB, MGR, HIREDATE, SAL, COMM, DEPTNO, SLACKER]], allRows=[false], after=[FLAG(SKIP TO NEXT ROW)], pattern=[(('STRT', PATTERN_QUANTIFIER('DOWN', 1, -1, false)), PATTERN_QUANTIFIER('UP', 1, -1, false))], isStrictStarts=[false], isStrictEnds=[false], subsets=[[]], patternDefinitions=[[<(PREV(DOWN.$3, 0), PREV(DOWN.$3, 1)), >(PREV(UP.$3, 0), PREV(UP.$3, 1))]], inputFields=[[EMPNO, ENAME, JOB, MGR, HIREDA [...]
LogicalTableScan(table=[[CATALOG, SALES, EMP]])
]]>
</Resource>
@@ -2758,7 +2823,7 @@ from emp match_recognize (
<Resource name="plan">
<![CDATA[
LogicalProject(JOB=[$0], SAL=[$1], MATCH_NUM=[$2], VAR_MATCH=[$3], START_NW=[$4], BOTTOM_NW=[$5], END_NW=[$6])
- LogicalMatch(partition=[[$2, $5]], order=[[2, 5 DESC]], outputFields=[[JOB, SAL, MATCH_NUM, VAR_MATCH, START_NW, BOTTOM_NW, END_NW]], allRows=[false], after=[FLAG(SKIP TO NEXT ROW)], pattern=[(('STRT', PATTERN_QUANTIFIER('DOWN', 1, -1, false)), PATTERN_QUANTIFIER('UP', 1, -1, false))], isStrictStarts=[false], isStrictEnds=[false], subsets=[[]], patternDefinitions=[[<(PREV(DOWN.$3, 0), PREV(DOWN.$3, 1)), >(PREV(UP.$3, 0), PREV(UP.$3, 1))]], inputFields=[[EMPNO, ENAME, JOB, MGR, HIREDATE [...]
+ LogicalMatch(partition=[[2, 5]], order=[[2, 5 DESC]], outputFields=[[JOB, SAL, MATCH_NUM, VAR_MATCH, START_NW, BOTTOM_NW, END_NW]], allRows=[false], after=[FLAG(SKIP TO NEXT ROW)], pattern=[(('STRT', PATTERN_QUANTIFIER('DOWN', 1, -1, false)), PATTERN_QUANTIFIER('UP', 1, -1, false))], isStrictStarts=[false], isStrictEnds=[false], subsets=[[]], patternDefinitions=[[<(PREV(DOWN.$3, 0), PREV(DOWN.$3, 1)), >(PREV(UP.$3, 0), PREV(UP.$3, 1))]], inputFields=[[EMPNO, ENAME, JOB, MGR, HIREDATE, [...]
LogicalTableScan(table=[[CATALOG, SALES, EMP]])
]]>
</Resource>
@@ -2782,7 +2847,7 @@ from emp match_recognize (
<Resource name="plan">
<![CDATA[
LogicalProject(JOB=[$0], MATCH_NUM=[$1], VAR_MATCH=[$2], START_NW=[$3], BOTTOM_NW=[$4], END_NW=[$5])
- LogicalMatch(partition=[[$2]], order=[[5]], outputFields=[[JOB, MATCH_NUM, VAR_MATCH, START_NW, BOTTOM_NW, END_NW]], allRows=[false], after=[FLAG(SKIP TO NEXT ROW)], pattern=[(('STRT', PATTERN_QUANTIFIER('DOWN', 1, -1, false)), PATTERN_QUANTIFIER('UP', 1, -1, false))], isStrictStarts=[false], isStrictEnds=[false], subsets=[[]], patternDefinitions=[[<(PREV(DOWN.$3, 0), PREV(DOWN.$3, 1)), >(PREV(UP.$3, 0), PREV(UP.$3, 1))]], inputFields=[[EMPNO, ENAME, JOB, MGR, HIREDATE, SAL, COMM, DEPT [...]
+ LogicalMatch(partition=[[2]], order=[[5]], outputFields=[[JOB, MATCH_NUM, VAR_MATCH, START_NW, BOTTOM_NW, END_NW]], allRows=[false], after=[FLAG(SKIP TO NEXT ROW)], pattern=[(('STRT', PATTERN_QUANTIFIER('DOWN', 1, -1, false)), PATTERN_QUANTIFIER('UP', 1, -1, false))], isStrictStarts=[false], isStrictEnds=[false], subsets=[[]], patternDefinitions=[[<(PREV(DOWN.$3, 0), PREV(DOWN.$3, 1)), >(PREV(UP.$3, 0), PREV(UP.$3, 1))]], inputFields=[[EMPNO, ENAME, JOB, MGR, HIREDATE, SAL, COMM, DEPTN [...]
LogicalTableScan(table=[[CATALOG, SALES, EMP]])
]]>
</Resource>
@@ -2807,7 +2872,7 @@ from emp match_recognize (
<Resource name="plan">
<![CDATA[
LogicalProject(JOB=[$0], SAL=[$1], EMPNO=[$2], ENAME=[$3], MGR=[$4], HIREDATE=[$5], COMM=[$6], DEPTNO=[$7], SLACKER=[$8], MATCH_NUM=[$9], VAR_MATCH=[$10], START_NW=[$11], BOTTOM_NW=[$12], END_NW=[$13])
- LogicalMatch(partition=[[$2]], order=[[5]], outputFields=[[JOB, SAL, EMPNO, ENAME, MGR, HIREDATE, COMM, DEPTNO, SLACKER, MATCH_NUM, VAR_MATCH, START_NW, BOTTOM_NW, END_NW]], allRows=[true], after=[FLAG(SKIP TO NEXT ROW)], pattern=[(('STRT', PATTERN_QUANTIFIER('DOWN', 1, -1, false)), PATTERN_QUANTIFIER('UP', 1, -1, false))], isStrictStarts=[false], isStrictEnds=[false], subsets=[[]], patternDefinitions=[[<(PREV(DOWN.$3, 0), PREV(DOWN.$3, 1)), >(PREV(UP.$3, 0), PREV(UP.$3, 1))]], inputFi [...]
+ LogicalMatch(partition=[[2]], order=[[5]], outputFields=[[JOB, SAL, EMPNO, ENAME, MGR, HIREDATE, COMM, DEPTNO, SLACKER, MATCH_NUM, VAR_MATCH, START_NW, BOTTOM_NW, END_NW]], allRows=[true], after=[FLAG(SKIP TO NEXT ROW)], pattern=[(('STRT', PATTERN_QUANTIFIER('DOWN', 1, -1, false)), PATTERN_QUANTIFIER('UP', 1, -1, false))], isStrictStarts=[false], isStrictEnds=[false], subsets=[[]], patternDefinitions=[[<(PREV(DOWN.$3, 0), PREV(DOWN.$3, 1)), >(PREV(UP.$3, 0), PREV(UP.$3, 1))]], inputFie [...]
LogicalTableScan(table=[[CATALOG, SALES, EMP]])
]]>
</Resource>
@@ -3084,7 +3149,7 @@ LogicalAggregate(group=[{0}])
<Resource name="plan">
<![CDATA[
LogicalProject(EMPNO=[$0], ENAME=[$1], JOB=[$2], MGR=[$3], HIREDATE=[$4], SAL=[$5], COMM=[$6], DEPTNO=[$7], SLACKER=[$8])
- LogicalMatch(partition=[[$2, $5]], order=[[2, 5 DESC, 0]], outputFields=[[EMPNO, ENAME, JOB, MGR, HIREDATE, SAL, COMM, DEPTNO, SLACKER]], allRows=[false], after=[FLAG(SKIP TO NEXT ROW)], pattern=[(('STRT', PATTERN_QUANTIFIER('DOWN', 1, -1, false)), PATTERN_QUANTIFIER('UP', 1, -1, false))], isStrictStarts=[false], isStrictEnds=[false], subsets=[[]], patternDefinitions=[[OR(=(PREV(DOWN.$3, 0), 0), =(PREV(DOWN.$3, 0), 1)), >(PREV(UP.$3, 0), PREV(UP.$3, 1))]], inputFields=[[EMPNO, ENAME, J [...]
+ LogicalMatch(partition=[[2, 5]], order=[[2, 5 DESC, 0]], outputFields=[[EMPNO, ENAME, JOB, MGR, HIREDATE, SAL, COMM, DEPTNO, SLACKER]], allRows=[false], after=[FLAG(SKIP TO NEXT ROW)], pattern=[(('STRT', PATTERN_QUANTIFIER('DOWN', 1, -1, false)), PATTERN_QUANTIFIER('UP', 1, -1, false))], isStrictStarts=[false], isStrictEnds=[false], subsets=[[]], patternDefinitions=[[OR(=(PREV(DOWN.$3, 0), 0), =(PREV(DOWN.$3, 0), 1)), >(PREV(UP.$3, 0), PREV(UP.$3, 1))]], inputFields=[[EMPNO, ENAME, JOB [...]
LogicalTableScan(table=[[CATALOG, SALES, EMP]])
]]>
</Resource>
@@ -3315,8 +3380,8 @@ LogicalAggregate(group=[{0}], EXPR$1=[SUM($1) FILTER $2], EXPR$2=[COUNT()])
<TestCase name="testSimplifyExistsAggregateSubQuery">
<Resource name="sql">
<![CDATA[SELECT e1.empno
- FROM emp e1 where exists
- (select avg(sal) from emp e2 where e1.empno = e2.empno)]]>
+FROM emp e1 where exists
+(select avg(sal) from emp e2 where e1.empno = e2.empno)]]>
</Resource>
<Resource name="plan">
<![CDATA[
@@ -3328,8 +3393,8 @@ LogicalProject(EMPNO=[$0])
<TestCase name="testSimplifyNotExistsAggregateSubQuery">
<Resource name="sql">
<![CDATA[SELECT e1.empno
- FROM emp e1 where not exists
- (select avg(sal) from emp e2 where e1.empno = e2.empno)]]>
+FROM emp e1 where not exists
+(select avg(sal) from emp e2 where e1.empno = e2.empno)]]>
</Resource>
<Resource name="plan">
<![CDATA[
@@ -3342,8 +3407,8 @@ LogicalProject(EMPNO=[$0])
<TestCase name="testSimplifyExistsValuesSubQuery">
<Resource name="sql">
<![CDATA[select deptno
- from EMP
- where exists (values 10)]]>
+from EMP
+where exists (values 10)]]>
</Resource>
<Resource name="plan">
<![CDATA[
@@ -3355,8 +3420,8 @@ LogicalProject(DEPTNO=[$7])
<TestCase name="testSimplifyNotExistsValuesSubQuery">
<Resource name="sql">
<![CDATA[select deptno
- from EMP
- where not exists (values 10)]]>
+from EMP
+where not exists (values 10)]]>
</Resource>
<Resource name="plan">
<![CDATA[
@@ -4191,7 +4256,7 @@ LogicalProject(EMPNO=[$0])
from emp e1, dept d1
where e1.deptno = d1.deptno
and e1.sal > (select avg(e2.sal) from emp e2
-where e2.deptno = d1.deptno group by cube(comm, mgr))]]>
+ where e2.deptno = d1.deptno group by cube(comm, mgr))]]>
</Resource>
<Resource name="plan">
<![CDATA[
@@ -5929,10 +5994,10 @@ LogicalSort(sort0=[$0], dir0=[ASC])
</TestCase>
<TestCase name="testLeftJoinLateral1">
<Resource name="sql">
- <![CDATA[select * from (values 4) as t (c)
- left join lateral
- (select c,a*c from (values 2) as s(a)) as r(d,c)
- using(c)]]>
+ <![CDATA[select * from (values 4) as t(c)
+ left join lateral
+ (select c,a*c from (values 2) as s(a)) as r(d,c)
+ using(c)]]>
</Resource>
<Resource name="plan">
<![CDATA[
@@ -5947,9 +6012,9 @@ LogicalProject(C=[$0], D=[$1])
</TestCase>
<TestCase name="testLeftJoinLateral2">
<Resource name="sql">
- <![CDATA[select * from (values 4) as t (c)
- natural left join lateral
- (select c,a*c from (values 2) as s(a)) as r(d,c)]]>
+ <![CDATA[select * from (values 4) as t(c)
+ natural left join lateral
+ (select c,a*c from (values 2) as s(a)) as r(d,c)]]>
</Resource>
<Resource name="plan">
<![CDATA[
@@ -5964,10 +6029,10 @@ LogicalProject(C=[$0], D=[$1])
</TestCase>
<TestCase name="testLeftJoinLateral3">
<Resource name="sql">
- <![CDATA[select * from (values 4) as t (c)
- left join lateral
- (select c,a*c from (values 2) as s(a)) as r(d,c)
- on t.c=r.c]]>
+ <![CDATA[select * from (values 4) as t(c)
+ left join lateral
+ (select c,a*c from (values 2) as s(a)) as r(d,c)
+ on t.c=r.c]]>
</Resource>
<Resource name="plan">
<![CDATA[
@@ -5983,9 +6048,9 @@ LogicalProject(C=[$0], D=[$1], C0=[$2])
<TestCase name="testLeftJoinLateral4">
<Resource name="sql">
<![CDATA[select * from (values (4,5)) as t(c,d)
- left join lateral
- (select c,a*c from (values 2) as s(a)) as r(d,c)
- on t.c+t.d=r.c]]>
+ left join lateral
+ (select c,a*c from (values 2) as s(a)) as r(d,c)
+ on t.c+t.d=r.c]]>
</Resource>
<Resource name="plan">
<![CDATA[
@@ -6001,12 +6066,12 @@ LogicalProject(C=[$0], D=[$1], D0=[$2], C0=[$3])
<TestCase name="testLeftJoinLateral5">
<Resource name="sql">
<![CDATA[select * from (values 4) as t (c)
- left join lateral
- (select f1+b1 from (values 2) as foo(f1)
- join
- (select c+1 from (values 3)) as bar(b1)
- on f1=b1)
- as r(n) on c=n]]>
+left join lateral
+ (select f1+b1 from (values 2) as foo(f1)
+ join
+ (select c+1 from (values 3)) as bar(b1)
+ on f1=b1)
+as r(n) on c=n]]>
</Resource>
<Resource name="plan">
<![CDATA[
@@ -6025,9 +6090,9 @@ LogicalProject(C=[$0], N=[$1])
<TestCase name="testCrossJoinLateral1">
<Resource name="sql">
<![CDATA[select * from (values (4,5)) as t(c,d)
- cross join lateral
- (select c,a*c as f from (values 2) as s(a)
- where c+d=a*c)]]>
+ cross join lateral
+ (select c,a*c as f from (values 2) as s(a)
+ where c+d=a*c)]]>
</Resource>
<Resource name="plan">
<![CDATA[
@@ -6043,13 +6108,13 @@ LogicalProject(C=[$0], D=[$1], C0=[$2], F=[$3])
<TestCase name="testCrossJoinLateral2">
<Resource name="sql">
<![CDATA[select * from (values 4) as t (c)
- cross join lateral
- (select * from (
- select f1+b1 from (values 2) as foo(f1)
- join
- (select c+1 from (values 3)) as bar(b1)
- on f1=b1
- ) as r(n) where c=n)]]>
+cross join lateral
+(select * from (
+ select f1+b1 from (values 2) as foo(f1)
+ join
+ (select c+1 from (values 3)) as bar(b1)
+ on f1=b1
+) as r(n) where c=n)]]>
</Resource>
<Resource name="plan">
<![CDATA[
diff --git a/core/src/test/resources/sql/match.iq b/core/src/test/resources/sql/match.iq
index 1f60c3e..1aa8ef9 100755
--- a/core/src/test/resources/sql/match.iq
+++ b/core/src/test/resources/sql/match.iq
@@ -15,8 +15,8 @@
# See the License for the specific language governing permissions and
# limitations under the License.
#
-!use post
!set outputformat oracle
+!use scott
# Simple query to check that oracle output format works
select empno, deptno, ename, comm from "scott".emp;
@@ -41,7 +41,19 @@ EMPNO DEPTNO ENAME COMM
!ok
-# count(*) returns number of rows in table
+!if (false) {
+# Simple
+SELECT *
+FROM "scott".emp MATCH_RECOGNIZE(
+ ORDER BY hiredate
+ MEASURES 1 AS m1
+ PATTERN (s up)
+ DEFINE up AS up.deptno < prev(up.deptno));
+!ok
+!}
+
+!if (false) {
+# Pattern
SELECT * FROM "scott".emp MATCH_RECOGNIZE(
PARTITION BY deptno ORDER BY empno
MEASURES
@@ -69,38 +81,40 @@ SELECT * FROM "scott".emp MATCH_RECOGNIZE(
12 rows selected.
!ok
+!}
-# Match recognize
+!use post
+
+!if (false) {
SELECT *
-FROM ticker
- MATCH_RECOGNIZE (
- PARTITION BY symbol
- ORDER BY tstamp
- MEASURES STRT.tstamp AS start_tstamp,
- LAST(DOWN.tstamp) AS bottom_tstamp,
- LAST(UP.tstamp) AS end_tstamp
- ONE ROW PER MATCH
- AFTER MATCH SKIP TO LAST UP
- PATTERN (STRT DOWN+ UP+)
- DEFINE
- DOWN AS DOWN.price < PREV(DOWN.price),
- UP AS UP.price > PREV(UP.price)
- ) MR
- ORDER BY MR.symbol, MR.start_tstamp;
-+--------+--------+---+
-| GENDER | EXPR$1 | C |
-+--------+--------+---+
-| M | 21 | 1 |
-| F | 11 | 1 |
-+--------+--------+---+
-(3 rows)
+FROM "scott".emp MATCH_RECOGNIZE(
+ ORDER BY hiredate
+ MEASURES 1 AS m1
+ PATTERN (s up)
+ DEFINE up AS up.deptno < prev(up.deptno));
+!ok
+!}
+
+select *
+from "hr"."emps" match_recognize (
+ order by "empid" desc
+ measures "commission" as c,
+ "empid" as empid
+ pattern (s up)
+ define up as up."commission" < prev(up."commission"));
+
+C EMPID
+---- -----
+1000 100
+ 500 200
!ok
-!use scott
+!if (false) {
# Match recognize
SELECT *
-FROM Ticker MATCH_RECOGNIZE (
+FROM ticker
+ MATCH_RECOGNIZE (
PARTITION BY symbol
ORDER BY tstamp
MEASURES STRT.tstamp AS start_tstamp,
@@ -124,4 +138,6 @@ FROM Ticker MATCH_RECOGNIZE (
!ok
+!}
+
# End match.iq
diff --git a/file/src/test/java/org/apache/calcite/adapter/file/SqlTest.java b/file/src/test/java/org/apache/calcite/adapter/file/SqlTest.java
index 36f9dd8..b936b24 100644
--- a/file/src/test/java/org/apache/calcite/adapter/file/SqlTest.java
+++ b/file/src/test/java/org/apache/calcite/adapter/file/SqlTest.java
@@ -389,7 +389,7 @@ public class SqlTest {
}
/** Test returns the result of two json file joins. */
- @Test public void testJsonJoinOnString() throws SQLException {
+ @Test public void testJsonJoinOnString() {
final String sql = "select emps.EMPNO, emps.NAME, depts.deptno from emps\n"
+ "join depts on emps.deptno = depts.deptno";
final String[] lines = {
@@ -401,7 +401,7 @@ public class SqlTest {
}
/** The folder contains both JSON files and CSV files joins. */
- @Test public void testJsonWithCsvJoin() throws SQLException {
+ @Test public void testJsonWithCsvJoin() {
final String sql = "select emps.empno,\n"
+ " NAME,\n"
+ " \"DATE\".JOINEDAT\n"
diff --git a/linq4j/src/main/java/org/apache/calcite/linq4j/MemoryEnumerable.java b/linq4j/src/main/java/org/apache/calcite/linq4j/MemoryEnumerable.java
new file mode 100644
index 0000000..07b8307
--- /dev/null
+++ b/linq4j/src/main/java/org/apache/calcite/linq4j/MemoryEnumerable.java
@@ -0,0 +1,48 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to you under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.calcite.linq4j;
+
+/**
+ * Enumerable that has a (limited) memory for n past and m future steps.
+ *
+ * @param <E> Type of the Enumerable items to remember
+ */
+public class MemoryEnumerable<E> extends AbstractEnumerable<MemoryFactory.Memory<E>> {
+ private final Enumerable<E> input;
+ private final int history;
+ private final int future;
+
+ /**
+ * Creates a MemoryEnumerable.
+ *
+ * @param input The Enumerable which the memory should be "wrapped" around
+ * @param history Number of present steps to remember
+ * @param future Number of future steps to remember
+ */
+ MemoryEnumerable(Enumerable<E> input, int history, int future) {
+ this.input = input;
+ this.history = history;
+ this.future = future;
+ }
+
+ @Override public Enumerator<MemoryFactory.Memory<E>> enumerator() {
+ return new MemoryEnumerator<>(input.enumerator(), history, future);
+ }
+
+}
+
+// End MemoryEnumerable.java
diff --git a/linq4j/src/main/java/org/apache/calcite/linq4j/MemoryEnumerator.java b/linq4j/src/main/java/org/apache/calcite/linq4j/MemoryEnumerator.java
new file mode 100644
index 0000000..1323336
--- /dev/null
+++ b/linq4j/src/main/java/org/apache/calcite/linq4j/MemoryEnumerator.java
@@ -0,0 +1,88 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to you under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.calcite.linq4j;
+
+import java.util.concurrent.atomic.AtomicInteger;
+
+/**
+ * Enumerator that keeps some recent and some "future" values.
+ *
+ * @param <E> Row value
+ */
+public class MemoryEnumerator<E> implements Enumerator<MemoryFactory.Memory<E>> {
+ private final Enumerator<E> enumerator;
+ private final MemoryFactory<E> memoryFactory;
+ private final AtomicInteger prevCounter;
+ private final AtomicInteger postCounter;
+
+ /**
+ * Creates a MemoryEnumerator.
+ *
+ * <p>Use factory method {@link MemoryEnumerable#enumerator()}.
+ *
+ * @param enumerator The Enumerator that memory should be "wrapped" around
+ * @param history Number of present steps to remember
+ * @param future Number of future steps to "remember"
+ */
+ MemoryEnumerator(Enumerator<E> enumerator, int history, int future) {
+ this.enumerator = enumerator;
+ this.memoryFactory = new MemoryFactory<>(history, future);
+ this.prevCounter = new AtomicInteger(future);
+ this.postCounter = new AtomicInteger(future);
+ }
+
+ @Override public MemoryFactory.Memory<E> current() {
+ return memoryFactory.create();
+ }
+
+ @Override public boolean moveNext() {
+ if (prevCounter.get() > 0) {
+ boolean lastMove = false;
+ while (prevCounter.getAndDecrement() >= 0) {
+ lastMove = moveNextInternal();
+ }
+ return lastMove;
+ } else {
+ return moveNextInternal();
+ }
+ }
+
+ private boolean moveNextInternal() {
+ final boolean moveNext = enumerator.moveNext();
+ if (moveNext) {
+ memoryFactory.add(enumerator.current());
+ return true;
+ } else {
+ // Check if we have to add "history" additional values
+ if (postCounter.getAndDecrement() > 0) {
+ memoryFactory.add(null);
+ return true;
+ }
+ }
+ return false;
+ }
+
+ @Override public void reset() {
+ enumerator.reset();
+ }
+
+ @Override public void close() {
+ enumerator.close();
+ }
+}
+
+// End MemoryEnumerator.java
diff --git a/linq4j/src/main/java/org/apache/calcite/linq4j/MemoryFactory.java b/linq4j/src/main/java/org/apache/calcite/linq4j/MemoryFactory.java
new file mode 100644
index 0000000..119ef44
--- /dev/null
+++ b/linq4j/src/main/java/org/apache/calcite/linq4j/MemoryFactory.java
@@ -0,0 +1,97 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to you under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.calcite.linq4j;
+
+import java.util.Arrays;
+
+/**
+ * Contains the State and changes internally.
+ * with the {@link #create()} method one can get immutable Snapshots.
+ * @param <E> Type of the base Object
+ */
+public class MemoryFactory<E> {
+
+ private final int history;
+ private final int future;
+ // Index: 0 1 2 3 4
+ // Idea -2 -1 0 +1 +2
+ ModularInteger offset;
+ private Object[] values;
+
+ public MemoryFactory(int history, int future) {
+ this.history = history;
+ this.future = future;
+ this.values = new Object[history + future + 1];
+ this.offset = new ModularInteger(0, history + future + 1);
+ }
+
+ public void add(E current) {
+ values[offset.get()] = current;
+ this.offset = offset.plus(1);
+ }
+
+ public Memory<E> create() {
+ return new Memory<>(history, future, offset, values.clone());
+ }
+
+ /**
+ * Contents of a "memory segment", used for implementing the
+ * {@code MATCH_RECOGNIZE} operator.
+ *
+ * <p>Memory maintains a "window" of records preceding and following a record;
+ * the records can be browsed using the {@link #get()} or {@link #get(int)}
+ * methods.
+ *
+ * @param <E> Row type
+ */
+ public static class Memory<E> {
+ private final int history;
+ private final int future;
+ private final ModularInteger offset;
+ private final Object[] values;
+
+ public Memory(int history, int future,
+ ModularInteger offset, Object[] values) {
+ this.history = history;
+ this.future = future;
+ this.offset = offset;
+ this.values = values;
+ }
+
+ @Override public String toString() {
+ return Arrays.toString(this.values);
+ }
+
+ public E get() {
+ return get(0);
+ }
+
+ public E get(int position) {
+ if (position < 0 && position < -1 * history) {
+ throw new IllegalArgumentException("History can only go back " + history
+ + " points in time, you wanted " + Math.abs(position));
+ }
+ if (position > 0 && position > future) {
+ throw new IllegalArgumentException("Future can only see next " + future
+ + " points in time, you wanted " + position);
+ }
+ return (E) this.values[this.offset.plus(position - 1 - future).get()];
+ }
+ }
+}
+
+// End MemoryFactory.java
diff --git a/linq4j/src/main/java/org/apache/calcite/linq4j/ModularInteger.java b/linq4j/src/main/java/org/apache/calcite/linq4j/ModularInteger.java
new file mode 100644
index 0000000..6dca80c
--- /dev/null
+++ b/linq4j/src/main/java/org/apache/calcite/linq4j/ModularInteger.java
@@ -0,0 +1,75 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to you under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.calcite.linq4j;
+
+import com.google.common.base.Preconditions;
+
+/**
+ * Represents an integer in modular arithmetic.
+ * Its {@code value} is between 0 and {@code m - 1} for some modulus {@code m}.
+ *
+ * <p>This object is immutable; all operations create a new object.
+ */
+class ModularInteger {
+ private final int value;
+ private final int modulus;
+
+ /** Creates a ModularInteger. */
+ ModularInteger(int value, int modulus) {
+ Preconditions.checkArgument(value >= 0 && value < modulus);
+ this.value = value;
+ this.modulus = modulus;
+ }
+
+ @Override public boolean equals(Object obj) {
+ return obj == this
+ || obj instanceof ModularInteger
+ && value == ((ModularInteger) obj).value
+ && modulus == ((ModularInteger) obj).modulus;
+ }
+
+ @Override public int hashCode() {
+ // 8191 is prime and, as 2^13 - 1, can easily be multiplied by bit-shifting
+ return value + 8191 * modulus;
+ }
+
+ public int get() {
+ return this.value;
+ }
+
+ public ModularInteger plus(int operand) {
+ if (operand < 0) {
+ return minus(Math.abs(operand));
+ }
+ return new ModularInteger((value + operand) % modulus, modulus);
+ }
+
+ public ModularInteger minus(int operand) {
+ assert operand >= 0;
+ int r = value - operand;
+ while (r < 0) {
+ r = r + modulus;
+ }
+ return new ModularInteger(r, modulus);
+ }
+
+ @Override public String toString() {
+ return value + " mod " + modulus;
+ }
+}
+
+// End ModularInteger.java
diff --git a/linq4j/src/main/java/org/apache/calcite/linq4j/tree/ExpressionType.java b/linq4j/src/main/java/org/apache/calcite/linq4j/tree/ExpressionType.java
index 23504a6..b34e618 100644
--- a/linq4j/src/main/java/org/apache/calcite/linq4j/tree/ExpressionType.java
+++ b/linq4j/src/main/java/org/apache/calcite/linq4j/tree/ExpressionType.java
@@ -583,10 +583,17 @@ public enum ExpressionType {
*/
Declaration,
+ /**
+ * For loop.
+ */
For,
+ /** For-each loop, "for (Type i : expression) body". */
ForEach,
+ /**
+ * While loop.
+ */
While;
final String op;
diff --git a/linq4j/src/main/java/org/apache/calcite/linq4j/tree/Expressions.java b/linq4j/src/main/java/org/apache/calcite/linq4j/tree/Expressions.java
index 847cfe6..1c92876 100644
--- a/linq4j/src/main/java/org/apache/calcite/linq4j/tree/Expressions.java
+++ b/linq4j/src/main/java/org/apache/calcite/linq4j/tree/Expressions.java
@@ -592,7 +592,7 @@ public abstract class Expressions {
* Creates a GotoExpression representing a continue statement.
*/
public static GotoStatement continue_(LabelTarget labelTarget) {
- throw Extensions.todo();
+ return new GotoStatement(GotoExpressionKind.Continue, null, null);
}
/**
diff --git a/linq4j/src/main/java/org/apache/calcite/linq4j/tree/ForEachStatement.java b/linq4j/src/main/java/org/apache/calcite/linq4j/tree/ForEachStatement.java
index 2d03171..a42d4aa 100644
--- a/linq4j/src/main/java/org/apache/calcite/linq4j/tree/ForEachStatement.java
+++ b/linq4j/src/main/java/org/apache/calcite/linq4j/tree/ForEachStatement.java
@@ -26,9 +26,7 @@ public class ForEachStatement extends Statement {
public final Expression iterable;
public final Statement body;
- /**
- * Cache the hash code for the expression
- */
+ /** Cache the hash code for the expression */
private int hash;
public ForEachStatement(ParameterExpression parameter, Expression iterable,
@@ -52,6 +50,8 @@ public class ForEachStatement extends Statement {
@Override void accept0(ExpressionWriter writer) {
writer.append("for (")
+ .append(parameter.type)
+ .append(" ")
.append(parameter)
.append(" : ")
.append(iterable)
diff --git a/linq4j/src/main/java/org/apache/calcite/linq4j/tree/VisitorImpl.java b/linq4j/src/main/java/org/apache/calcite/linq4j/tree/VisitorImpl.java
index 9a711a9..5e60849 100644
--- a/linq4j/src/main/java/org/apache/calcite/linq4j/tree/VisitorImpl.java
+++ b/linq4j/src/main/java/org/apache/calcite/linq4j/tree/VisitorImpl.java
@@ -103,7 +103,8 @@ public class VisitorImpl<R> implements Visitor<R> {
}
public R visit(GotoStatement gotoStatement) {
- return gotoStatement.expression.accept(this);
+ return gotoStatement.expression == null ? null
+ : gotoStatement.expression.accept(this);
}
public R visit(IndexExpression indexExpression) {
diff --git a/linq4j/src/test/java/org/apache/calcite/linq4j/MemoryEnumerableTest.java b/linq4j/src/test/java/org/apache/calcite/linq4j/MemoryEnumerableTest.java
new file mode 100644
index 0000000..4558a1a
--- /dev/null
+++ b/linq4j/src/test/java/org/apache/calcite/linq4j/MemoryEnumerableTest.java
@@ -0,0 +1,70 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to you under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.calcite.linq4j;
+
+import org.junit.Test;
+
+import java.util.ArrayList;
+import java.util.List;
+import java.util.stream.Collectors;
+import java.util.stream.IntStream;
+
+import static org.hamcrest.CoreMatchers.is;
+import static org.hamcrest.CoreMatchers.nullValue;
+import static org.junit.Assert.assertThat;
+
+/** Tests for {@link org.apache.calcite.linq4j.MemoryEnumerable} */
+public class MemoryEnumerableTest {
+
+ @Test public void testHistoryAndFuture() {
+ final Enumerable<Integer> input =
+ Linq4j.asEnumerable(IntStream.range(0, 100)
+ .boxed().collect(Collectors.toList()));
+
+ final MemoryEnumerable<Integer> integers = new MemoryEnumerable<>(input, 5, 1);
+ final Enumerator<MemoryFactory.Memory<Integer>> enumerator = integers.enumerator();
+
+ final List<MemoryFactory.Memory<Integer>> results = new ArrayList<>();
+ while (enumerator.moveNext()) {
+ final MemoryFactory.Memory<Integer> current = enumerator.current();
+ results.add(current);
+ }
+
+ assertThat(results.size(), is(100));
+ // First entry
+ assertThat((int) results.get(0).get(), is(0));
+ assertThat((int) results.get(0).get(1), is(1));
+ assertThat(results.get(0).get(-2), nullValue());
+ // Last entry
+ assertThat((int) results.get(99).get(), is(99));
+ assertThat((int) results.get(99).get(-2), is(97));
+ assertThat(results.get(99).get(1), nullValue());
+ }
+
+ @Test public void testModularInteger() {
+ final ModularInteger modularInteger = new ModularInteger(4, 5);
+ assertThat(modularInteger.toString(), is("4 mod 5"));
+
+ final ModularInteger plus = modularInteger.plus(1);
+ assertThat(plus.toString(), is("0 mod 5"));
+
+ final ModularInteger minus = modularInteger.plus(-6);
+ assertThat(minus.toString(), is("3 mod 5"));
+ }
+}
+
+// End MemoryEnumerableTest.java
diff --git a/linq4j/src/test/java/org/apache/calcite/linq4j/test/ExpressionTest.java b/linq4j/src/test/java/org/apache/calcite/linq4j/test/ExpressionTest.java
index 6e77bd9..63ca081 100644
--- a/linq4j/src/test/java/org/apache/calcite/linq4j/test/ExpressionTest.java
+++ b/linq4j/src/test/java/org/apache/calcite/linq4j/test/ExpressionTest.java
@@ -1218,6 +1218,27 @@ public class ExpressionTest {
Expressions.toString(builder.toBlock()));
}
+ @Test public void testForEach() {
+ final BlockBuilder builder = new BlockBuilder();
+ final ParameterExpression i_ = Expressions.parameter(int.class, "i");
+ final ParameterExpression list_ = Expressions.parameter(List.class, "list");
+ builder.add(
+ Expressions.forEach(i_, list_,
+ Expressions.ifThen(
+ Expressions.lessThan(
+ Expressions.constant(1),
+ Expressions.constant(2)),
+ Expressions.break_(null))));
+ assertThat(Expressions.toString(builder.toBlock()),
+ is("{\n"
+ + " for (int i : list) {\n"
+ + " if (1 < 2) {\n"
+ + " break;\n"
+ + " }\n"
+ + " }\n"
+ + "}\n"));
+ }
+
@Test public void testEmptyListLiteral() throws Exception {
assertEquals("java.util.Collections.EMPTY_LIST",
Expressions.toString(Expressions.constant(Arrays.asList())));