This is an automated email from the ASF dual-hosted git repository.
jackietien pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/iotdb.git
The following commit(s) were added to refs/heads/master by this push:
new 810ec62f824 [IOTDB-6124] Add scope filter parameter for tree visitor
framework
810ec62f824 is described below
commit 810ec62f824b405a68f435499db327af96ed870f
Author: Chen YZ <[email protected]>
AuthorDate: Thu Aug 24 19:02:04 2023 +0800
[IOTDB-6124] Add scope filter parameter for tree visitor framework
---
.../visitor/SchemaTreeDeviceVisitor.java | 6 +
.../visitor/SchemaTreeMeasurementVisitor.java | 7 +
.../schematree/visitor/SchemaTreeVisitor.java | 36 +++++
.../visitor/SchemaTreeVisitorFactory.java | 23 +++
.../schemaregion/mtree/traverser/Traverser.java | 46 +++++-
.../common/schematree/ClusterSchemaTreeTest.java | 178 +++++++++++++++++++++
.../ClusterSchemaTreeTestWithRelease.java | 16 ++
.../MockSchemaTreeMeasurementVisitor.java | 6 +
.../apache/iotdb/commons/path/fa/FAFactory.java | 14 +-
.../apache/iotdb/commons/path/fa/IPatternFA.java | 17 +-
.../iotdb/commons/path/fa/dfa/PatternDFA.java | 60 +++++++
.../iotdb/commons/path/fa/dfa/graph/NFAGraph.java | 65 ++++++++
.../commons/path/fa/match/IStateMatchInfo.java | 2 +
.../commons/path/fa/match/StateMultiMatchInfo.java | 14 +-
.../path/fa/match/StateSingleMatchInfo.java | 10 +-
.../iotdb/commons/schema/SchemaConstant.java | 12 +-
.../commons/schema/tree/AbstractTreeVisitor.java | 136 +++++++++++-----
.../iotdb/commons/schema/tree/ITreeNode.java | 4 +
.../apache/iotdb/commons/path/PatternDFATest.java | 45 ++++++
19 files changed, 648 insertions(+), 49 deletions(-)
diff --git
a/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/common/schematree/visitor/SchemaTreeDeviceVisitor.java
b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/common/schematree/visitor/SchemaTreeDeviceVisitor.java
index 16512a8aeb0..5a50c4bda92 100644
---
a/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/common/schematree/visitor/SchemaTreeDeviceVisitor.java
+++
b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/common/schematree/visitor/SchemaTreeDeviceVisitor.java
@@ -20,6 +20,7 @@
package org.apache.iotdb.db.queryengine.common.schematree.visitor;
import org.apache.iotdb.commons.path.PartialPath;
+import org.apache.iotdb.commons.path.PathPatternTree;
import org.apache.iotdb.db.queryengine.common.schematree.DeviceSchemaInfo;
import org.apache.iotdb.db.queryengine.common.schematree.MeasurementSchemaInfo;
import
org.apache.iotdb.db.queryengine.common.schematree.node.SchemaMeasurementNode;
@@ -35,6 +36,11 @@ public class SchemaTreeDeviceVisitor extends
SchemaTreeVisitor<DeviceSchemaInfo>
super(root, pathPattern, isPrefixMatch);
}
+ public SchemaTreeDeviceVisitor(
+ SchemaNode root, PartialPath pathPattern, boolean isPrefixMatch,
PathPatternTree scope) {
+ super(root, pathPattern, isPrefixMatch, scope);
+ }
+
@Override
protected boolean mayTargetNodeType(SchemaNode node) {
return node.isEntity();
diff --git
a/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/common/schematree/visitor/SchemaTreeMeasurementVisitor.java
b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/common/schematree/visitor/SchemaTreeMeasurementVisitor.java
index 0b56e6a9596..ca33a519b01 100644
---
a/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/common/schematree/visitor/SchemaTreeMeasurementVisitor.java
+++
b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/common/schematree/visitor/SchemaTreeMeasurementVisitor.java
@@ -21,6 +21,7 @@ package
org.apache.iotdb.db.queryengine.common.schematree.visitor;
import org.apache.iotdb.commons.path.MeasurementPath;
import org.apache.iotdb.commons.path.PartialPath;
+import org.apache.iotdb.commons.path.PathPatternTree;
import org.apache.iotdb.commons.path.fa.IFAState;
import org.apache.iotdb.commons.path.fa.IFATransition;
import org.apache.iotdb.db.queryengine.common.schematree.node.SchemaNode;
@@ -37,6 +38,12 @@ public class SchemaTreeMeasurementVisitor extends
SchemaTreeVisitor<MeasurementP
tailNode = pathPattern.getTailNode();
}
+ public SchemaTreeMeasurementVisitor(
+ SchemaNode root, PartialPath pathPattern, boolean isPrefixMatch,
PathPatternTree scope) {
+ super(root, pathPattern, isPrefixMatch, scope);
+ tailNode = pathPattern.getTailNode();
+ }
+
@Override
protected boolean mayTargetNodeType(SchemaNode node) {
return node.isMeasurement();
diff --git
a/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/common/schematree/visitor/SchemaTreeVisitor.java
b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/common/schematree/visitor/SchemaTreeVisitor.java
index 7eb97b6191f..337225813ef 100644
---
a/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/common/schematree/visitor/SchemaTreeVisitor.java
+++
b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/common/schematree/visitor/SchemaTreeVisitor.java
@@ -20,12 +20,14 @@
package org.apache.iotdb.db.queryengine.common.schematree.visitor;
import org.apache.iotdb.commons.path.PartialPath;
+import org.apache.iotdb.commons.path.PathPatternTree;
import org.apache.iotdb.commons.schema.tree.AbstractTreeVisitor;
import org.apache.iotdb.db.queryengine.common.schematree.node.SchemaNode;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
+import java.util.NoSuchElementException;
public abstract class SchemaTreeVisitor<R> extends
AbstractTreeVisitor<SchemaNode, R> {
@@ -36,6 +38,12 @@ public abstract class SchemaTreeVisitor<R> extends
AbstractTreeVisitor<SchemaNod
initStack();
}
+ protected SchemaTreeVisitor(
+ SchemaNode root, PartialPath pathPattern, boolean isPrefixMatch,
PathPatternTree scope) {
+ super(root, pathPattern, isPrefixMatch, scope);
+ initStack();
+ }
+
public List<R> getAllResult() {
List<R> result = new ArrayList<>();
while (hasNext()) {
@@ -59,6 +67,34 @@ public abstract class SchemaTreeVisitor<R> extends
AbstractTreeVisitor<SchemaNod
return parent.getChild(childName);
}
+ @Override
+ protected Iterator<SchemaNode> getChildrenIterator(
+ SchemaNode parent, Iterator<String> childrenName) throws Exception {
+ return new Iterator<SchemaNode>() {
+ private SchemaNode next = null;
+
+ @Override
+ public boolean hasNext() {
+ if (next == null) {
+ while (next == null && childrenName.hasNext()) {
+ next = getChild(parent, childrenName.next());
+ }
+ }
+ return next != null;
+ }
+
+ @Override
+ public SchemaNode next() {
+ if (!hasNext()) {
+ throw new NoSuchElementException();
+ }
+ SchemaNode result = next;
+ next = null;
+ return result;
+ }
+ };
+ }
+
@Override
protected Iterator<SchemaNode> getChildrenIterator(SchemaNode parent) {
return parent.getChildrenIterator();
diff --git
a/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/common/schematree/visitor/SchemaTreeVisitorFactory.java
b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/common/schematree/visitor/SchemaTreeVisitorFactory.java
index 69195fd816d..3132801696b 100644
---
a/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/common/schematree/visitor/SchemaTreeVisitorFactory.java
+++
b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/common/schematree/visitor/SchemaTreeVisitorFactory.java
@@ -21,6 +21,7 @@ package
org.apache.iotdb.db.queryengine.common.schematree.visitor;
import org.apache.iotdb.commons.path.MeasurementPath;
import org.apache.iotdb.commons.path.PartialPath;
+import org.apache.iotdb.commons.path.PathPatternTree;
import org.apache.iotdb.db.queryengine.common.schematree.node.SchemaNode;
public class SchemaTreeVisitorFactory {
@@ -49,4 +50,26 @@ public class SchemaTreeVisitorFactory {
return new SchemaTreeVisitorWithLimitOffsetWrapper<>(
new SchemaTreeMeasurementVisitor(root, pathPattern, isPrefixMatch),
slimit, soffset);
}
+
+ public static SchemaTreeDeviceVisitor createSchemaTreeDeviceVisitor(
+ SchemaNode root, PartialPath pathPattern, boolean isPrefixMatch,
PathPatternTree scope) {
+ return new SchemaTreeDeviceVisitor(root, pathPattern, isPrefixMatch,
scope);
+ }
+
+ public static SchemaTreeMeasurementVisitor
createSchemaTreeMeasurementVisitor(
+ SchemaNode root, PartialPath pathPattern, boolean isPrefixMatch,
PathPatternTree scope) {
+ return new SchemaTreeMeasurementVisitor(root, pathPattern, isPrefixMatch,
scope);
+ }
+
+ public static SchemaTreeVisitorWithLimitOffsetWrapper<MeasurementPath>
+ createSchemaTreeMeasurementVisitor(
+ SchemaNode root,
+ PartialPath pathPattern,
+ boolean isPrefixMatch,
+ int slimit,
+ int soffset,
+ PathPatternTree scope) {
+ return new SchemaTreeVisitorWithLimitOffsetWrapper<>(
+ new SchemaTreeMeasurementVisitor(root, pathPattern, isPrefixMatch,
scope), slimit, soffset);
+ }
}
diff --git
a/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/schemaengine/schemaregion/mtree/traverser/Traverser.java
b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/schemaengine/schemaregion/mtree/traverser/Traverser.java
index 745b60b4323..115ce1d27df 100644
---
a/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/schemaengine/schemaregion/mtree/traverser/Traverser.java
+++
b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/schemaengine/schemaregion/mtree/traverser/Traverser.java
@@ -38,6 +38,7 @@ import org.slf4j.LoggerFactory;
import java.util.Iterator;
import java.util.Map;
+import java.util.NoSuchElementException;
import static org.apache.iotdb.commons.conf.IoTDBConstant.PATH_ROOT;
import static org.apache.iotdb.commons.schema.SchemaConstant.NON_TEMPLATE;
@@ -150,6 +151,47 @@ public abstract class Traverser<R, N extends IMNode<N>>
extends AbstractTreeVisi
}
}
+ @Override
+ protected Iterator<N> getChildrenIterator(N parent, Iterator<String>
childrenName)
+ throws Exception {
+ return new IMNodeIterator<N>() {
+ private N next = null;
+
+ @Override
+ public boolean hasNext() {
+ if (next == null) {
+ while (next == null && childrenName.hasNext()) {
+ try {
+ next = getChild(parent, childrenName.next());
+ } catch (Throwable e) {
+ logger.warn(e.getMessage(), e);
+ throw new RuntimeException(e);
+ }
+ }
+ }
+ return next != null;
+ }
+
+ @Override
+ public N next() {
+ if (!hasNext()) {
+ throw new NoSuchElementException();
+ }
+ N result = next;
+ next = null;
+ return result;
+ }
+
+ @Override
+ public void close() {
+ if (next != null) {
+ releaseNode(next);
+ next = null;
+ }
+ }
+ };
+ }
+
@Override
protected Iterator<N> getChildrenIterator(N parent) throws MetadataException
{
if (parent.isAboveDatabase()) {
@@ -161,7 +203,9 @@ public abstract class Traverser<R, N extends IMNode<N>>
extends AbstractTreeVisi
@Override
protected void releaseNodeIterator(Iterator<N> nodeIterator) {
- ((IMNodeIterator<N>) nodeIterator).close();
+ if (nodeIterator instanceof IMNodeIterator) {
+ ((IMNodeIterator<N>) nodeIterator).close();
+ }
}
@Override
diff --git
a/iotdb-core/datanode/src/test/java/org/apache/iotdb/db/queryengine/common/schematree/ClusterSchemaTreeTest.java
b/iotdb-core/datanode/src/test/java/org/apache/iotdb/db/queryengine/common/schematree/ClusterSchemaTreeTest.java
index 18760f25cc9..56ae45668da 100644
---
a/iotdb-core/datanode/src/test/java/org/apache/iotdb/db/queryengine/common/schematree/ClusterSchemaTreeTest.java
+++
b/iotdb-core/datanode/src/test/java/org/apache/iotdb/db/queryengine/common/schematree/ClusterSchemaTreeTest.java
@@ -21,6 +21,7 @@ package org.apache.iotdb.db.queryengine.common.schematree;
import org.apache.iotdb.commons.exception.IllegalPathException;
import org.apache.iotdb.commons.path.MeasurementPath;
import org.apache.iotdb.commons.path.PartialPath;
+import org.apache.iotdb.commons.path.PathPatternTree;
import org.apache.iotdb.commons.schema.view.LogicalViewSchema;
import
org.apache.iotdb.commons.schema.view.viewExpression.leaf.TimeSeriesViewOperand;
import org.apache.iotdb.db.queryengine.common.schematree.node.SchemaEntityNode;
@@ -468,6 +469,171 @@ public class ClusterSchemaTreeTest {
return root;
}
+ @Test
+ public void testSchemaTreeWithScope() throws Exception {
+ SchemaNode root = generateSchemaTree();
+ PathPatternTree scope = new PathPatternTree();
+ scope.appendPathPattern(new PartialPath("root.sg.d1.**"));
+ scope.appendPathPattern(new PartialPath("root.sg.d2.status"));
+ scope.appendPathPattern(new PartialPath("root.sg.d2.a.**"));
+ scope.constructTree();
+
+ SchemaTreeVisitorWithLimitOffsetWrapper<MeasurementPath> visitor =
+ createSchemaTreeVisitorWithLimitOffsetWrapper(
+ root, new PartialPath("root.sg.d2.a.s1"), 0, 0, false, scope);
+ checkVisitorResult(visitor, 1, new String[] {"root.sg.d2.a.s1"}, null, new
boolean[] {true});
+
+ visitor =
+ createSchemaTreeVisitorWithLimitOffsetWrapper(
+ root, new PartialPath("root.sg.d2.s1"), 0, 0, false, scope);
+ checkVisitorResult(visitor, 0, new String[] {}, null, new boolean[] {});
+
+ visitor =
+ createSchemaTreeVisitorWithLimitOffsetWrapper(
+ root, new PartialPath("root.sg.*.s2"), 0, 0, false, scope);
+ checkVisitorResult(
+ visitor, 2, new String[] {"root.sg.d1.s2", "root.sg.d2.s2"}, new
String[] {"", ""}, null);
+
+ visitor =
+ createSchemaTreeVisitorWithLimitOffsetWrapper(
+ root, new PartialPath("root.sg.*.s1"), 0, 0, false, scope);
+ checkVisitorResult(visitor, 1, new String[] {"root.sg.d1.s1"}, new
String[] {""}, null);
+
+ visitor =
+ createSchemaTreeVisitorWithLimitOffsetWrapper(
+ root, new PartialPath("root.sg.*.status"), 0, 0, false, scope);
+ checkVisitorResult(
+ visitor,
+ 2,
+ new String[] {"root.sg.d1.s2", "root.sg.d2.s2"},
+ new String[] {"status", "status"},
+ null);
+
+ visitor =
+ createSchemaTreeVisitorWithLimitOffsetWrapper(
+ root, new PartialPath("root.sg.d2.*.*"), 0, 0, false, scope);
+ checkVisitorResult(
+ visitor,
+ 2,
+ new String[] {"root.sg.d2.a.s1", "root.sg.d2.a.s2"},
+ new String[] {"", ""},
+ new boolean[] {true, true});
+
+ visitor =
+ createSchemaTreeVisitorWithLimitOffsetWrapper(
+ root, new PartialPath("root.sg.d1"), 0, 0, true, scope);
+ checkVisitorResult(
+ visitor,
+ 2,
+ new String[] {"root.sg.d1.s1", "root.sg.d1.s2"},
+ new String[] {"", ""},
+ new boolean[] {false, false});
+
+ visitor =
+ createSchemaTreeVisitorWithLimitOffsetWrapper(
+ root, new PartialPath("root.sg.*.a"), 0, 0, true, scope);
+ checkVisitorResult(
+ visitor,
+ 2,
+ new String[] {"root.sg.d2.a.s1", "root.sg.d2.a.s2"},
+ new String[] {"", ""},
+ new boolean[] {true, true},
+ new int[] {0, 0});
+
+ visitor =
+ createSchemaTreeVisitorWithLimitOffsetWrapper(
+ root, new PartialPath("root.sg.*.*"), 2, 2, false, scope);
+ checkVisitorResult(
+ visitor,
+ 1,
+ new String[] {"root.sg.d2.s2"},
+ new String[] {""},
+ new boolean[] {false},
+ new int[] {3});
+
+ visitor =
+ createSchemaTreeVisitorWithLimitOffsetWrapper(
+ root, new PartialPath("root.sg.*"), 2, 3, true, scope);
+ checkVisitorResult(
+ visitor,
+ 2,
+ new String[] {"root.sg.d2.a.s2", "root.sg.d2.s2"},
+ new String[] {"", ""},
+ new boolean[] {true, false},
+ new int[] {4, 5});
+
+ visitor =
+ createSchemaTreeVisitorWithLimitOffsetWrapper(
+ root, new PartialPath("root.sg.d1.**"), 0, 0, false, scope);
+ checkVisitorResult(
+ visitor,
+ 2,
+ new String[] {"root.sg.d1.s1", "root.sg.d1.s2"},
+ new String[] {"", ""},
+ new boolean[] {false, false});
+
+ visitor =
+ createSchemaTreeVisitorWithLimitOffsetWrapper(
+ root, new PartialPath("root.sg.d2.**"), 3, 1, true, scope);
+ checkVisitorResult(
+ visitor,
+ 2,
+ new String[] {"root.sg.d2.a.s2", "root.sg.d2.s2"},
+ new String[] {"", ""},
+ new boolean[] {true, false},
+ new int[] {2, 3});
+
+ visitor =
+ createSchemaTreeVisitorWithLimitOffsetWrapper(
+ root, new PartialPath("root.sg.**.status"), 2, 1, true, scope);
+ checkVisitorResult(
+ visitor,
+ 2,
+ new String[] {"root.sg.d2.a.s2", "root.sg.d2.s2"},
+ new String[] {"status", "status"},
+ new boolean[] {true, false},
+ new int[] {2, 3});
+
+ visitor =
+ createSchemaTreeVisitorWithLimitOffsetWrapper(
+ root, new PartialPath("root.**.*"), 10, 0, false, scope);
+ checkVisitorResult(
+ visitor,
+ 5,
+ new String[] {
+ "root.sg.d1.s1", "root.sg.d1.s2", "root.sg.d2.a.s1",
"root.sg.d2.a.s2", "root.sg.d2.s2"
+ },
+ new String[] {"", "", "", "", ""},
+ new boolean[] {false, false, true, true, false},
+ new int[] {1, 2, 3, 4, 5});
+
+ visitor =
+ createSchemaTreeVisitorWithLimitOffsetWrapper(
+ root, new PartialPath("root.**.*.**"), 10, 0, false, scope);
+ checkVisitorResult(
+ visitor,
+ 5,
+ new String[] {
+ "root.sg.d1.s1", "root.sg.d1.s2", "root.sg.d2.a.s1",
"root.sg.d2.a.s2", "root.sg.d2.s2"
+ },
+ new String[] {"", "", "", "", ""},
+ new boolean[] {false, false, true, true, false},
+ new int[] {1, 2, 3, 4, 5});
+
+ visitor =
+ createSchemaTreeVisitorWithLimitOffsetWrapper(
+ root, new PartialPath("root.*.**.**"), 10, 0, false, scope);
+ checkVisitorResult(
+ visitor,
+ 5,
+ new String[] {
+ "root.sg.d1.s1", "root.sg.d1.s2", "root.sg.d2.a.s1",
"root.sg.d2.a.s2", "root.sg.d2.s2"
+ },
+ new String[] {"", "", "", "", ""},
+ new boolean[] {false, false, true, true, false},
+ new int[] {1, 2, 3, 4, 5});
+ }
+
private void checkVisitorResult(
SchemaTreeVisitorWithLimitOffsetWrapper<MeasurementPath> visitor,
int expectedNum,
@@ -731,6 +897,18 @@ public class ClusterSchemaTreeTest {
root, pathPattern, isPrefixMatch, slimit, soffset);
}
+ protected SchemaTreeVisitorWithLimitOffsetWrapper<MeasurementPath>
+ createSchemaTreeVisitorWithLimitOffsetWrapper(
+ SchemaNode root,
+ PartialPath pathPattern,
+ int slimit,
+ int soffset,
+ boolean isPrefixMatch,
+ PathPatternTree scope) {
+ return SchemaTreeVisitorFactory.createSchemaTreeMeasurementVisitor(
+ root, pathPattern, isPrefixMatch, slimit, soffset, scope);
+ }
+
@Test
public void testHasView() throws IllegalPathException {
ClusterSchemaTree schemaTree = new ClusterSchemaTree();
diff --git
a/iotdb-core/datanode/src/test/java/org/apache/iotdb/db/queryengine/common/schematree/ClusterSchemaTreeTestWithRelease.java
b/iotdb-core/datanode/src/test/java/org/apache/iotdb/db/queryengine/common/schematree/ClusterSchemaTreeTestWithRelease.java
index b7204d5d5b8..72b77254b21 100644
---
a/iotdb-core/datanode/src/test/java/org/apache/iotdb/db/queryengine/common/schematree/ClusterSchemaTreeTestWithRelease.java
+++
b/iotdb-core/datanode/src/test/java/org/apache/iotdb/db/queryengine/common/schematree/ClusterSchemaTreeTestWithRelease.java
@@ -20,6 +20,7 @@ package org.apache.iotdb.db.queryengine.common.schematree;
import org.apache.iotdb.commons.path.MeasurementPath;
import org.apache.iotdb.commons.path.PartialPath;
+import org.apache.iotdb.commons.path.PathPatternTree;
import org.apache.iotdb.db.queryengine.common.schematree.node.SchemaNode;
import
org.apache.iotdb.db.queryengine.common.schematree.visitor.SchemaTreeVisitorWithLimitOffsetWrapper;
@@ -36,4 +37,19 @@ public class ClusterSchemaTreeTestWithRelease extends
ClusterSchemaTreeTest {
return new SchemaTreeVisitorWithLimitOffsetWrapper<>(
new MockSchemaTreeMeasurementVisitor(root, pathPattern,
isPrefixMatch), slimit, soffset);
}
+
+ @Override
+ protected SchemaTreeVisitorWithLimitOffsetWrapper<MeasurementPath>
+ createSchemaTreeVisitorWithLimitOffsetWrapper(
+ SchemaNode root,
+ PartialPath pathPattern,
+ int slimit,
+ int soffset,
+ boolean isPrefixMatch,
+ PathPatternTree scope) {
+ return new SchemaTreeVisitorWithLimitOffsetWrapper<>(
+ new MockSchemaTreeMeasurementVisitor(root, pathPattern, isPrefixMatch,
scope),
+ slimit,
+ soffset);
+ }
}
diff --git
a/iotdb-core/datanode/src/test/java/org/apache/iotdb/db/queryengine/common/schematree/MockSchemaTreeMeasurementVisitor.java
b/iotdb-core/datanode/src/test/java/org/apache/iotdb/db/queryengine/common/schematree/MockSchemaTreeMeasurementVisitor.java
index ee8e61126d3..b1fc5db615e 100644
---
a/iotdb-core/datanode/src/test/java/org/apache/iotdb/db/queryengine/common/schematree/MockSchemaTreeMeasurementVisitor.java
+++
b/iotdb-core/datanode/src/test/java/org/apache/iotdb/db/queryengine/common/schematree/MockSchemaTreeMeasurementVisitor.java
@@ -20,6 +20,7 @@ package org.apache.iotdb.db.queryengine.common.schematree;
import org.apache.iotdb.commons.path.MeasurementPath;
import org.apache.iotdb.commons.path.PartialPath;
+import org.apache.iotdb.commons.path.PathPatternTree;
import org.apache.iotdb.db.queryengine.common.schematree.node.SchemaNode;
import
org.apache.iotdb.db.queryengine.common.schematree.visitor.SchemaTreeMeasurementVisitor;
@@ -43,6 +44,11 @@ public class MockSchemaTreeMeasurementVisitor extends
SchemaTreeMeasurementVisit
super(root, pathPattern, isPrefixMatch);
}
+ public MockSchemaTreeMeasurementVisitor(
+ SchemaNode root, PartialPath pathPattern, boolean isPrefixMatch,
PathPatternTree scope) {
+ super(root, pathPattern, isPrefixMatch, scope);
+ }
+
@Override
protected Iterator<SchemaNode> getChildrenIterator(SchemaNode parent) {
return new CountIterator(super.getChildrenIterator(parent));
diff --git
a/iotdb-core/node-commons/src/main/java/org/apache/iotdb/commons/path/fa/FAFactory.java
b/iotdb-core/node-commons/src/main/java/org/apache/iotdb/commons/path/fa/FAFactory.java
index c2b50414c3c..ea6c2d02f80 100644
---
a/iotdb-core/node-commons/src/main/java/org/apache/iotdb/commons/path/fa/FAFactory.java
+++
b/iotdb-core/node-commons/src/main/java/org/apache/iotdb/commons/path/fa/FAFactory.java
@@ -20,6 +20,7 @@ package org.apache.iotdb.commons.path.fa;
import org.apache.iotdb.commons.path.fa.dfa.PatternDFA;
import org.apache.iotdb.commons.path.fa.nfa.SimpleNFA;
+import org.apache.iotdb.commons.schema.SchemaConstant;
import com.github.benmanes.caffeine.cache.Caffeine;
import com.github.benmanes.caffeine.cache.LoadingCache;
@@ -41,7 +42,18 @@ public class FAFactory {
dfaCache =
Caffeine.newBuilder()
.maximumSize(DFA_CACHE_SIZE)
- .build(builder -> new PatternDFA(builder.getPathPattern(),
builder.isPrefixMatch()));
+ .build(
+ builder -> {
+ if (builder.getPatternTree() != null) {
+ if
(builder.getPatternTree().equals(SchemaConstant.ALL_MATCH_PATTERN_TREE)) {
+ // always return the same instance for root.**
+ return SchemaConstant.ALL_MATCH_DFA;
+ }
+ return new PatternDFA(builder.getPatternTree());
+ } else {
+ return new PatternDFA(builder.getPathPattern(),
builder.isPrefixMatch());
+ }
+ });
}
public static FAFactory getInstance() {
diff --git
a/iotdb-core/node-commons/src/main/java/org/apache/iotdb/commons/path/fa/IPatternFA.java
b/iotdb-core/node-commons/src/main/java/org/apache/iotdb/commons/path/fa/IPatternFA.java
index 825531d5369..3016ab4d4a1 100644
---
a/iotdb-core/node-commons/src/main/java/org/apache/iotdb/commons/path/fa/IPatternFA.java
+++
b/iotdb-core/node-commons/src/main/java/org/apache/iotdb/commons/path/fa/IPatternFA.java
@@ -20,6 +20,7 @@
package org.apache.iotdb.commons.path.fa;
import org.apache.iotdb.commons.path.PartialPath;
+import org.apache.iotdb.commons.path.PathPatternTree;
import java.util.Iterator;
import java.util.Map;
@@ -86,6 +87,7 @@ public interface IPatternFA {
final class Builder {
private PartialPath pathPattern;
+ private PathPatternTree patternTree;
private boolean isPrefixMatch = false;
public Builder() {}
@@ -95,6 +97,12 @@ public interface IPatternFA {
return this;
}
+ /** @param patternTree the included PartialPath must be a prefix or a
fullPath */
+ public Builder patternTree(PathPatternTree patternTree) {
+ this.patternTree = patternTree;
+ return this;
+ }
+
public Builder isPrefixMatch(boolean isPrefixMatch) {
this.isPrefixMatch = isPrefixMatch;
return this;
@@ -104,6 +112,10 @@ public interface IPatternFA {
return pathPattern;
}
+ public PathPatternTree getPatternTree() {
+ return patternTree;
+ }
+
public boolean isPrefixMatch() {
return isPrefixMatch;
}
@@ -122,12 +134,13 @@ public interface IPatternFA {
if (o == null || getClass() != o.getClass()) return false;
Builder builder = (Builder) o;
return isPrefixMatch == builder.isPrefixMatch
- && Objects.equals(pathPattern, builder.pathPattern);
+ && Objects.equals(pathPattern, builder.pathPattern)
+ && Objects.equals(patternTree, builder.patternTree);
}
@Override
public int hashCode() {
- return Objects.hash(pathPattern, isPrefixMatch);
+ return Objects.hash(pathPattern, patternTree, isPrefixMatch);
}
}
}
diff --git
a/iotdb-core/node-commons/src/main/java/org/apache/iotdb/commons/path/fa/dfa/PatternDFA.java
b/iotdb-core/node-commons/src/main/java/org/apache/iotdb/commons/path/fa/dfa/PatternDFA.java
index c0f909d84cf..2a0504c9158 100644
---
a/iotdb-core/node-commons/src/main/java/org/apache/iotdb/commons/path/fa/dfa/PatternDFA.java
+++
b/iotdb-core/node-commons/src/main/java/org/apache/iotdb/commons/path/fa/dfa/PatternDFA.java
@@ -20,6 +20,7 @@ package org.apache.iotdb.commons.path.fa.dfa;
import org.apache.iotdb.commons.conf.IoTDBConstant;
import org.apache.iotdb.commons.path.PartialPath;
+import org.apache.iotdb.commons.path.PathPatternTree;
import org.apache.iotdb.commons.path.fa.IFAState;
import org.apache.iotdb.commons.path.fa.IFATransition;
import org.apache.iotdb.commons.path.fa.IPatternFA;
@@ -84,6 +85,65 @@ public class PatternDFA implements IPatternFA {
batchMatchTransitionCached = new List[dfaGraph.getStateSize()];
}
+ /**
+ * Construct PatternDFA for given path pattern. Only used for authentication
now.
+ *
+ * @param prefixOrFullPatternTree the included PartialPath must be a prefix
or a fullPath
+ */
+ public PatternDFA(PathPatternTree prefixOrFullPatternTree) {
+ // 1. build transition
+ boolean wildcard = false;
+ AtomicInteger transitionIndex = new AtomicInteger();
+ for (PartialPath pathPattern :
prefixOrFullPatternTree.getAllPathPatterns()) {
+ for (String node : pathPattern.getNodes()) {
+ if (IoTDBConstant.ONE_LEVEL_PATH_WILDCARD.equals(node)
+ || IoTDBConstant.MULTI_LEVEL_PATH_WILDCARD.equals(node)) {
+ wildcard = true;
+ } else {
+ transitionMap.computeIfAbsent(
+ node,
+ i -> {
+ IFATransition transition =
+ new
DFAPreciseTransition(transitionIndex.getAndIncrement(), node);
+ preciseMatchTransitionList.add(transition);
+ return transition;
+ });
+ }
+ }
+ }
+ if (wildcard) {
+ IFATransition transition =
+ new DFAWildcardTransition(
+ transitionIndex.getAndIncrement(), new
ArrayList<>(transitionMap.keySet()));
+ transitionMap.put(transition.getAcceptEvent(), transition);
+ batchMatchTransitionList.add(transition);
+ }
+
+ // 2. build NFA
+ NFAGraph nfaGraph = new NFAGraph(prefixOrFullPatternTree, transitionMap);
+
+ // 3. NFA to DFA
+ dfaGraph = new DFAGraph(nfaGraph, transitionMap.values());
+ preciseMatchTransitionCached = new HashMap[dfaGraph.getStateSize()];
+ batchMatchTransitionCached = new List[dfaGraph.getStateSize()];
+ }
+
+ public IFAState getNextState(IFAState currentState, String acceptEvent) {
+ if (transitionMap.containsKey(acceptEvent)) {
+ return dfaGraph.getNextState(currentState,
transitionMap.get(acceptEvent));
+ } else {
+ Iterator<IFATransition> fuzzyMatchTransitionIterator =
+ getFuzzyMatchTransitionIterator(currentState);
+ while (fuzzyMatchTransitionIterator.hasNext()) {
+ IFATransition transition = fuzzyMatchTransitionIterator.next();
+ if (transition.isMatch(acceptEvent)) {
+ return dfaGraph.getNextState(currentState, transition);
+ }
+ }
+ }
+ return null;
+ }
+
@Override
public Map<String, IFATransition> getPreciseMatchTransition(IFAState state) {
if (preciseMatchTransitionCached[state.getIndex()] == null) {
diff --git
a/iotdb-core/node-commons/src/main/java/org/apache/iotdb/commons/path/fa/dfa/graph/NFAGraph.java
b/iotdb-core/node-commons/src/main/java/org/apache/iotdb/commons/path/fa/dfa/graph/NFAGraph.java
index fa6299167e6..92a40719280 100644
---
a/iotdb-core/node-commons/src/main/java/org/apache/iotdb/commons/path/fa/dfa/graph/NFAGraph.java
+++
b/iotdb-core/node-commons/src/main/java/org/apache/iotdb/commons/path/fa/dfa/graph/NFAGraph.java
@@ -20,6 +20,7 @@ package org.apache.iotdb.commons.path.fa.dfa.graph;
import org.apache.iotdb.commons.conf.IoTDBConstant;
import org.apache.iotdb.commons.path.PartialPath;
+import org.apache.iotdb.commons.path.PathPatternTree;
import org.apache.iotdb.commons.path.fa.IFAState;
import org.apache.iotdb.commons.path.fa.IFATransition;
import org.apache.iotdb.commons.path.fa.dfa.DFAState;
@@ -30,6 +31,7 @@ import org.apache.commons.lang3.StringUtils;
import java.util.ArrayList;
import java.util.List;
import java.util.Map;
+import java.util.concurrent.atomic.AtomicInteger;
import java.util.stream.Collectors;
/**
@@ -42,6 +44,13 @@ public class NFAGraph {
// [transitionIndex][stateIndex]List<IFAState>
private final List<IFAState>[][] nfaTransitionTable;
+ /**
+ * Construct NFA graph for given path pattern.
+ *
+ * @param pathPattern matched path pattern
+ * @param isPrefix prefix match mode, matched pattern will be pathPattern.**
if isPrefix is true
+ * @param transitionMap transitionMap
+ */
public NFAGraph(
PartialPath pathPattern, boolean isPrefix, Map<String, IFATransition>
transitionMap) {
nfaTransitionTable = new
List[transitionMap.size()][pathPattern.getNodeLength() + 1];
@@ -84,6 +93,62 @@ public class NFAGraph {
}
}
+ /**
+ * Construct NFA graph for given path pattern. Only used for authentication
now.
+ *
+ * @param prefixOrFullPatternTree the included PartialPath must be a prefix
or a fullPath
+ * @param transitionMap transitionMap
+ */
+ public NFAGraph(
+ PathPatternTree prefixOrFullPatternTree, Map<String, IFATransition>
transitionMap) {
+ List<PartialPath> partialPathList =
prefixOrFullPatternTree.getAllPathPatterns();
+ int maxStateSize =
partialPathList.stream().mapToInt(PartialPath::getNodeLength).sum() + 1;
+ nfaTransitionTable = new List[transitionMap.size()][maxStateSize];
+ // init start state, curNodeIndex=0
+ AtomicInteger stateIndexGenerator = new AtomicInteger(0);
+ nfaStateList.add(new DFAState(0));
+ for (int i = 0; i < transitionMap.size(); i++) {
+ nfaTransitionTable[i][0] = new ArrayList<>();
+ }
+ for (PartialPath pathPattern : partialPathList) {
+ buildPattern(pathPattern, transitionMap, stateIndexGenerator);
+ }
+ }
+
+ private void buildPattern(
+ PartialPath pathPattern,
+ Map<String, IFATransition> transitionMap,
+ AtomicInteger stateIndexGenerator) {
+ // traverse pathPattern and construct NFA
+ int prevIndex = 0;
+ for (int i = 0; i < pathPattern.getNodeLength(); i++) {
+ String node = pathPattern.getNodes()[i];
+ // if it is tail node, transit to final state
+ DFAState state =
+ i == pathPattern.getNodeLength() - 1
+ ? new DFAState(stateIndexGenerator.incrementAndGet(), true)
+ : new DFAState(stateIndexGenerator.incrementAndGet());
+ nfaStateList.add(state);
+ for (int j = 0; j < transitionMap.size(); j++) {
+ nfaTransitionTable[j][state.getIndex()] = new ArrayList<>();
+ }
+ // construct transition
+ if (IoTDBConstant.ONE_LEVEL_PATH_WILDCARD.equals(node)) {
+ for (IFATransition transition : transitionMap.values()) {
+ nfaTransitionTable[transition.getIndex()][prevIndex].add(state);
+ }
+ } else if (IoTDBConstant.MULTI_LEVEL_PATH_WILDCARD.equals(node)) {
+ for (IFATransition transition : transitionMap.values()) {
+ nfaTransitionTable[transition.getIndex()][prevIndex].add(state);
+
nfaTransitionTable[transition.getIndex()][state.getIndex()].add(state);
+ }
+ } else {
+
nfaTransitionTable[transitionMap.get(node).getIndex()][prevIndex].add(state);
+ }
+ prevIndex = state.getIndex();
+ }
+ }
+
@TestOnly
public void print(Map<String, IFATransition> transitionMap) {
System.out.println();
diff --git
a/iotdb-core/node-commons/src/main/java/org/apache/iotdb/commons/path/fa/match/IStateMatchInfo.java
b/iotdb-core/node-commons/src/main/java/org/apache/iotdb/commons/path/fa/match/IStateMatchInfo.java
index 4e050c1d7e3..da582c32282 100644
---
a/iotdb-core/node-commons/src/main/java/org/apache/iotdb/commons/path/fa/match/IStateMatchInfo.java
+++
b/iotdb-core/node-commons/src/main/java/org/apache/iotdb/commons/path/fa/match/IStateMatchInfo.java
@@ -76,4 +76,6 @@ public interface IStateMatchInfo {
/** @param sourceTransitionIterator the iterator of current checking source
states' transition */
void setSourceTransitionIterator(Iterator<IFATransition>
sourceTransitionIterator);
+
+ IFAState getScopeMatchedState();
}
diff --git
a/iotdb-core/node-commons/src/main/java/org/apache/iotdb/commons/path/fa/match/StateMultiMatchInfo.java
b/iotdb-core/node-commons/src/main/java/org/apache/iotdb/commons/path/fa/match/StateMultiMatchInfo.java
index fbad7e70a4b..a1974ba4134 100644
---
a/iotdb-core/node-commons/src/main/java/org/apache/iotdb/commons/path/fa/match/StateMultiMatchInfo.java
+++
b/iotdb-core/node-commons/src/main/java/org/apache/iotdb/commons/path/fa/match/StateMultiMatchInfo.java
@@ -38,21 +38,26 @@ public class StateMultiMatchInfo implements IStateMatchInfo
{
private boolean hasFinalState = false;
- public StateMultiMatchInfo(IPatternFA patternFA) {
+ private final IFAState scopeState;
+
+ public StateMultiMatchInfo(IPatternFA patternFA, IFAState scopeState) {
this.patternFA = patternFA;
matchedStateSet = new MatchedStateSet(patternFA.getStateSize());
+ this.scopeState = scopeState;
}
public StateMultiMatchInfo(
IPatternFA patternFA,
IFAState matchedState,
- Iterator<IFATransition> sourceTransitionIterator) {
+ Iterator<IFATransition> sourceTransitionIterator,
+ IFAState scopeState) {
this.patternFA = patternFA;
matchedStateSet = new MatchedStateSet(patternFA.getStateSize());
matchedStateSet.add(matchedState);
sourceStateIndex = 0;
this.sourceTransitionIterator = sourceTransitionIterator;
this.hasFinalState = matchedState.isFinal();
+ this.scopeState = scopeState;
}
@Override
@@ -117,4 +122,9 @@ public class StateMultiMatchInfo implements IStateMatchInfo
{
public void setSourceTransitionIterator(Iterator<IFATransition>
sourceTransitionIterator) {
this.sourceTransitionIterator = sourceTransitionIterator;
}
+
+ @Override
+ public IFAState getScopeMatchedState() {
+ return scopeState;
+ }
}
diff --git
a/iotdb-core/node-commons/src/main/java/org/apache/iotdb/commons/path/fa/match/StateSingleMatchInfo.java
b/iotdb-core/node-commons/src/main/java/org/apache/iotdb/commons/path/fa/match/StateSingleMatchInfo.java
index e3ccf7df613..e94319c907e 100644
---
a/iotdb-core/node-commons/src/main/java/org/apache/iotdb/commons/path/fa/match/StateSingleMatchInfo.java
+++
b/iotdb-core/node-commons/src/main/java/org/apache/iotdb/commons/path/fa/match/StateSingleMatchInfo.java
@@ -32,9 +32,12 @@ public class StateSingleMatchInfo implements IStateMatchInfo
{
private final IFAState matchedState;
- public StateSingleMatchInfo(IPatternFA patternFA, IFAState matchedState) {
+ private final IFAState scopeState;
+
+ public StateSingleMatchInfo(IPatternFA patternFA, IFAState matchedState,
IFAState scopeState) {
this.patternFA = patternFA;
this.matchedState = matchedState;
+ this.scopeState = scopeState;
}
@Override
@@ -100,4 +103,9 @@ public class StateSingleMatchInfo implements
IStateMatchInfo {
public void setSourceTransitionIterator(Iterator<IFATransition>
sourceTransitionIterator) {
throw new UnsupportedOperationException();
}
+
+ @Override
+ public IFAState getScopeMatchedState() {
+ return scopeState;
+ }
}
diff --git
a/iotdb-core/node-commons/src/main/java/org/apache/iotdb/commons/schema/SchemaConstant.java
b/iotdb-core/node-commons/src/main/java/org/apache/iotdb/commons/schema/SchemaConstant.java
index 3b01d82e5d7..7717b1c679b 100644
---
a/iotdb-core/node-commons/src/main/java/org/apache/iotdb/commons/schema/SchemaConstant.java
+++
b/iotdb-core/node-commons/src/main/java/org/apache/iotdb/commons/schema/SchemaConstant.java
@@ -20,6 +20,8 @@ package org.apache.iotdb.commons.schema;
import org.apache.iotdb.commons.conf.IoTDBConstant;
import org.apache.iotdb.commons.path.PartialPath;
+import org.apache.iotdb.commons.path.PathPatternTree;
+import org.apache.iotdb.commons.path.fa.dfa.PatternDFA;
public class SchemaConstant {
@@ -54,7 +56,15 @@ public class SchemaConstant {
public static final String SYSTEM_DATABASE = "root.__system";
public static final String[] ALL_RESULT_NODES = new String[] {"root", "**"};
- public static final PartialPath ALL_MATCH_PATTERN = new PartialPath(new
String[] {"root", "**"});
+ public static final PartialPath ALL_MATCH_PATTERN = new
PartialPath(ALL_RESULT_NODES);
+ public static final PathPatternTree ALL_MATCH_PATTERN_TREE = new
PathPatternTree();
+
+ static {
+ ALL_MATCH_PATTERN_TREE.appendPathPattern(ALL_MATCH_PATTERN);
+ ALL_MATCH_PATTERN_TREE.constructTree();
+ }
+
+ public static final PatternDFA ALL_MATCH_DFA = new
PatternDFA(ALL_MATCH_PATTERN, false);
public static final PartialPath SYSTEM_DATABASE_PATTERN =
new PartialPath(SYSTEM_DATABASE.split("\\."));
diff --git
a/iotdb-core/node-commons/src/main/java/org/apache/iotdb/commons/schema/tree/AbstractTreeVisitor.java
b/iotdb-core/node-commons/src/main/java/org/apache/iotdb/commons/schema/tree/AbstractTreeVisitor.java
index 130d3c7143d..f678f379ff4 100644
---
a/iotdb-core/node-commons/src/main/java/org/apache/iotdb/commons/schema/tree/AbstractTreeVisitor.java
+++
b/iotdb-core/node-commons/src/main/java/org/apache/iotdb/commons/schema/tree/AbstractTreeVisitor.java
@@ -21,12 +21,15 @@ package org.apache.iotdb.commons.schema.tree;
import org.apache.iotdb.commons.conf.IoTDBConstant;
import org.apache.iotdb.commons.path.PartialPath;
+import org.apache.iotdb.commons.path.PathPatternTree;
import org.apache.iotdb.commons.path.fa.IFAState;
import org.apache.iotdb.commons.path.fa.IFATransition;
import org.apache.iotdb.commons.path.fa.IPatternFA;
+import org.apache.iotdb.commons.path.fa.dfa.PatternDFA;
import org.apache.iotdb.commons.path.fa.match.IStateMatchInfo;
import org.apache.iotdb.commons.path.fa.match.StateMultiMatchInfo;
import org.apache.iotdb.commons.path.fa.match.StateSingleMatchInfo;
+import org.apache.iotdb.commons.schema.SchemaConstant;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
@@ -73,6 +76,9 @@ public abstract class AbstractTreeVisitor<N extends
ITreeNode, R> implements Sch
// finite automation constructed from given path pattern or pattern tree
protected final IPatternFA patternFA;
+ // deterministic finite automation for filtering traversed subtrees
+ private final PatternDFA scopeDFA;
+ private final boolean allScope;
// run time variables
// stack to store children iterator of visited ancestor
@@ -99,9 +105,16 @@ public abstract class AbstractTreeVisitor<N extends
ITreeNode, R> implements Sch
protected AbstractTreeVisitor() {
root = null;
patternFA = null;
+ scopeDFA = SchemaConstant.ALL_MATCH_DFA;
+ allScope = true;
}
protected AbstractTreeVisitor(N root, PartialPath pathPattern, boolean
isPrefixMatch) {
+ this(root, pathPattern, isPrefixMatch, null);
+ }
+
+ protected AbstractTreeVisitor(
+ N root, PartialPath pathPattern, boolean isPrefixMatch, PathPatternTree
scope) {
this.root = root;
boolean usingDFA = false;
@@ -121,6 +134,11 @@ public abstract class AbstractTreeVisitor<N extends
ITreeNode, R> implements Sch
usingDFA
? new
IPatternFA.Builder().pattern(pathPattern).isPrefixMatch(isPrefixMatch).buildDFA()
: new
IPatternFA.Builder().pattern(pathPattern).isPrefixMatch(isPrefixMatch).buildNFA();
+ this.scopeDFA =
+ scope == null
+ ? SchemaConstant.ALL_MATCH_DFA
+ : (PatternDFA) new
IPatternFA.Builder().patternTree(scope).buildDFA();
+ this.allScope = this.scopeDFA == SchemaConstant.ALL_MATCH_DFA;
}
/** This method must be invoked before iteration */
@@ -133,7 +151,8 @@ public abstract class AbstractTreeVisitor<N extends
ITreeNode, R> implements Sch
return;
}
IFAState rootState = patternFA.getNextState(initialState, transition);
- currentStateMatchInfo = new StateSingleMatchInfo(patternFA, rootState);
+ IFAState initScopeState =
scopeDFA.getNextState(scopeDFA.getInitialState(), root.getName());
+ currentStateMatchInfo = new StateSingleMatchInfo(patternFA, rootState,
initScopeState);
visitorStack.push(new VisitorStackEntry(createChildrenIterator(root), 1));
ancestorStack.add(new AncestorStackEntry(root, currentStateMatchInfo));
}
@@ -188,7 +207,7 @@ public abstract class AbstractTreeVisitor<N extends
ITreeNode, R> implements Sch
private void getNext() {
nextMatchedNode = null;
VisitorStackEntry stackEntry;
- Iterator<N> iterator;
+ AbstractChildrenIterator iterator;
while (!visitorStack.isEmpty()) {
stackEntry = visitorStack.peek();
iterator = stackEntry.iterator;
@@ -242,17 +261,15 @@ public abstract class AbstractTreeVisitor<N extends
ITreeNode, R> implements Sch
return new TraceBackChildrenIterator(parent, currentStateMatchInfo);
} else if (currentStateMatchInfo.hasOnlyPreciseMatchTransition()) {
// the child can be got directly with the precise value of transition
- return new PreciseMatchChildrenIterator(parent,
currentStateMatchInfo.getOneMatchedState());
+ return new PreciseMatchChildrenIterator(parent, currentStateMatchInfo);
} else if (currentStateMatchInfo.hasNoPreciseMatchTransition()
&& currentStateMatchInfo.isSingleFuzzyMatchTransition()) {
// only one transition which may match batch children, need to iterate
and check all child
- return new SingleFuzzyMatchChildrenIterator(
- parent, currentStateMatchInfo.getOneMatchedState());
+ return new SingleFuzzyMatchChildrenIterator(parent,
currentStateMatchInfo);
} else {
// child may be matched by multi transitions, precise match or fuzzy
match,
// which results in one child match multi state; need to iterate and
check all child
- return new MultiMatchTransitionChildrenIterator(
- parent, currentStateMatchInfo.getOneMatchedState());
+ return new MultiMatchTransitionChildrenIterator(parent,
currentStateMatchInfo);
}
}
@@ -368,6 +385,10 @@ public abstract class AbstractTreeVisitor<N extends
ITreeNode, R> implements Sch
// Get an iterator of all children.
protected abstract Iterator<N> getChildrenIterator(N parent) throws
Exception;
+ // Get an iterator of specific children.
+ protected abstract Iterator<N> getChildrenIterator(N parent,
Iterator<String> childrenName)
+ throws Exception;
+
// Release a child node.
protected void releaseNode(N node) {}
@@ -430,17 +451,32 @@ public abstract class AbstractTreeVisitor<N extends
ITreeNode, R> implements Sch
}
}
+ protected final IFAState getNextMatchedScopeState(IFAState currentState, N
node) {
+ IFAState nextState = scopeDFA.getNextState(currentState, node.getName());
+ if (nextState == null && node.getAlias() != null) {
+ return scopeDFA.getNextState(currentState, node.getAlias());
+ }
+ return nextState;
+ }
+
// implement common iterating logic of different children iterator
private abstract class AbstractChildrenIterator implements Iterator<N> {
-
+ protected final N parent;
+ protected final IFAState currentScopeState;
private N nextMatchedChild;
+ protected AbstractChildrenIterator(N parent, IFAState currentScopeState) {
+ this.parent = parent;
+ this.currentScopeState = currentScopeState;
+ }
+
@Override
public boolean hasNext() {
if (nextMatchedChild == null) {
try {
getNext();
} catch (Throwable e) {
+ logger.warn(e.getMessage(), e);
throw new RuntimeException(e.getMessage(), e);
}
}
@@ -464,6 +500,15 @@ public abstract class AbstractTreeVisitor<N extends
ITreeNode, R> implements Sch
protected abstract void getNext() throws Exception;
+ protected final Iterator<N> initChildrenIterator() throws Exception {
+ if (!allScope && scopeDFA.getFuzzyMatchTransitionSize(currentScopeState)
== 0) {
+ return getChildrenIterator(
+ parent,
scopeDFA.getPreciseMatchTransition(currentScopeState).keySet().iterator());
+ } else {
+ return getChildrenIterator(parent);
+ }
+ }
+
protected void close() {
if (nextMatchedChild != null) {
releaseNode(nextMatchedChild);
@@ -473,13 +518,12 @@ public abstract class AbstractTreeVisitor<N extends
ITreeNode, R> implements Sch
// the child can be got directly with the precise value of transition,
there's no traceback
private class PreciseMatchChildrenIterator extends AbstractChildrenIterator {
- private final N parent;
private final IFAState sourceState;
private final Iterator<IFATransition> transitionIterator;
- private PreciseMatchChildrenIterator(N parent, IFAState sourceState) {
- this.parent = parent;
- this.sourceState = sourceState;
+ private PreciseMatchChildrenIterator(N parent, IStateMatchInfo
stateMatchInfo) {
+ super(parent, stateMatchInfo.getScopeMatchedState());
+ this.sourceState = stateMatchInfo.getOneMatchedState();
transitionIterator =
patternFA.getPreciseMatchTransitionIterator(sourceState);
}
@@ -492,9 +536,16 @@ public abstract class AbstractTreeVisitor<N extends
ITreeNode, R> implements Sch
if (child == null) {
continue;
}
+ IFAState nextScopeState =
+ allScope ? null : getNextMatchedScopeState(currentScopeState,
child);
+ if (!allScope && nextScopeState == null) {
+ releaseNode(child);
+ continue;
+ }
saveResult(
child,
- new StateSingleMatchInfo(patternFA,
patternFA.getNextState(sourceState, transition)));
+ new StateSingleMatchInfo(
+ patternFA, patternFA.getNextState(sourceState, transition),
nextScopeState));
return;
}
}
@@ -507,23 +558,18 @@ public abstract class AbstractTreeVisitor<N extends
ITreeNode, R> implements Sch
private final IFAState sourceState;
private final IFATransition transition;
- private final StateSingleMatchInfo stateMatchInfo;
- private final N parent;
-
private Iterator<N> childrenIterator;
- private SingleFuzzyMatchChildrenIterator(N parent, IFAState sourceState) {
- this.sourceState = sourceState;
+ private SingleFuzzyMatchChildrenIterator(N parent, IStateMatchInfo
stateMatchInfo) {
+ super(parent, stateMatchInfo.getScopeMatchedState());
+ this.sourceState = stateMatchInfo.getOneMatchedState();
this.transition =
patternFA.getFuzzyMatchTransitionIterator(sourceState).next();
- this.stateMatchInfo =
- new StateSingleMatchInfo(patternFA,
patternFA.getNextState(sourceState, transition));
- this.parent = parent;
}
@Override
protected void getNext() throws Exception {
if (childrenIterator == null) {
- this.childrenIterator = getChildrenIterator(parent);
+ this.childrenIterator = initChildrenIterator();
}
N child;
while (childrenIterator.hasNext()) {
@@ -532,7 +578,12 @@ public abstract class AbstractTreeVisitor<N extends
ITreeNode, R> implements Sch
releaseNode(child);
continue;
}
- saveResult(child, stateMatchInfo);
+ IFAState nextScopeState =
+ allScope ? null : getNextMatchedScopeState(currentScopeState,
child);
+ saveResult(
+ child,
+ new StateSingleMatchInfo(
+ patternFA, patternFA.getNextState(sourceState, transition),
nextScopeState));
return;
}
}
@@ -554,20 +605,18 @@ public abstract class AbstractTreeVisitor<N extends
ITreeNode, R> implements Sch
private final IFAState sourceState;
private final Map<String, IFATransition> preciseMatchTransitionMap;
- private final N parent;
-
private Iterator<N> iterator;
- private MultiMatchTransitionChildrenIterator(N parent, IFAState
sourceState) {
- this.sourceState = sourceState;
+ private MultiMatchTransitionChildrenIterator(N parent, IStateMatchInfo
stateMatchInfo) {
+ super(parent, stateMatchInfo.getScopeMatchedState());
+ this.sourceState = stateMatchInfo.getOneMatchedState();
this.preciseMatchTransitionMap =
patternFA.getPreciseMatchTransition(sourceState);
- this.parent = parent;
}
@Override
protected void getNext() throws Exception {
if (iterator == null) {
- this.iterator = getChildrenIterator(parent);
+ this.iterator = initChildrenIterator();
}
N child;
@@ -576,7 +625,8 @@ public abstract class AbstractTreeVisitor<N extends
ITreeNode, R> implements Sch
IStateMatchInfo stateMatchInfo;
while (iterator.hasNext()) {
child = iterator.next();
-
+ IFAState nextScopeState =
+ allScope ? null : getNextMatchedScopeState(currentScopeState,
child);
// find first matched state
if (!preciseMatchTransitionMap.isEmpty()) {
matchedState = tryGetNextState(child, sourceState,
preciseMatchTransitionMap);
@@ -600,7 +650,9 @@ public abstract class AbstractTreeVisitor<N extends
ITreeNode, R> implements Sch
// not accept the first matched state since this node may be a
target result, check the
// other states
if (patternFA.mayTransitionOverlap() &&
transitionIterator.hasNext()) {
- stateMatchInfo = new StateMultiMatchInfo(patternFA, matchedState,
transitionIterator);
+ stateMatchInfo =
+ new StateMultiMatchInfo(
+ patternFA, matchedState, transitionIterator,
nextScopeState);
firstAncestorOfTraceback = ancestorStack.size();
while (transitionIterator.hasNext()) {
@@ -613,15 +665,17 @@ public abstract class AbstractTreeVisitor<N extends
ITreeNode, R> implements Sch
}
}
} else {
- stateMatchInfo = new StateSingleMatchInfo(patternFA, matchedState);
+ stateMatchInfo = new StateSingleMatchInfo(patternFA, matchedState,
nextScopeState);
}
} else {
// accept the first matched state, directly save it
if (patternFA.mayTransitionOverlap() &&
transitionIterator.hasNext()) {
- stateMatchInfo = new StateMultiMatchInfo(patternFA, matchedState,
transitionIterator);
+ stateMatchInfo =
+ new StateMultiMatchInfo(
+ patternFA, matchedState, transitionIterator,
nextScopeState);
firstAncestorOfTraceback = ancestorStack.size();
} else {
- stateMatchInfo = new StateSingleMatchInfo(patternFA, matchedState);
+ stateMatchInfo = new StateSingleMatchInfo(patternFA, matchedState,
nextScopeState);
}
}
@@ -643,20 +697,18 @@ public abstract class AbstractTreeVisitor<N extends
ITreeNode, R> implements Sch
// the iterating process will try to get the first matched state of a child.
private class TraceBackChildrenIterator extends AbstractChildrenIterator {
- private final N parent;
private final IStateMatchInfo sourceStateMatchInfo;
-
private Iterator<N> iterator;
- TraceBackChildrenIterator(N parent, IStateMatchInfo sourceStateMatchInfo) {
- this.sourceStateMatchInfo = sourceStateMatchInfo;
- this.parent = parent;
+ TraceBackChildrenIterator(N parent, IStateMatchInfo stateMatchInfo) {
+ super(parent, stateMatchInfo.getScopeMatchedState());
+ this.sourceStateMatchInfo = stateMatchInfo;
}
@Override
protected void getNext() throws Exception {
if (iterator == null) {
- iterator = getChildrenIterator(parent);
+ this.iterator = initChildrenIterator();
}
N child;
@@ -668,8 +720,10 @@ public abstract class AbstractTreeVisitor<N extends
ITreeNode, R> implements Sch
while (iterator.hasNext()) {
child = iterator.next();
+ IFAState nextScopeState =
+ allScope ? null : getNextMatchedScopeState(currentScopeState,
child);
- stateMatchInfo = new StateMultiMatchInfo(patternFA);
+ stateMatchInfo = new StateMultiMatchInfo(patternFA, nextScopeState);
if (mayTargetNodeType(child)) {
for (int i = 0; i < sourceStateMatchInfo.getMatchedStateSize(); i++)
{
sourceState = sourceStateMatchInfo.getMatchedState(i);
diff --git
a/iotdb-core/node-commons/src/main/java/org/apache/iotdb/commons/schema/tree/ITreeNode.java
b/iotdb-core/node-commons/src/main/java/org/apache/iotdb/commons/schema/tree/ITreeNode.java
index 71537bc303d..4b7b30b5498 100644
---
a/iotdb-core/node-commons/src/main/java/org/apache/iotdb/commons/schema/tree/ITreeNode.java
+++
b/iotdb-core/node-commons/src/main/java/org/apache/iotdb/commons/schema/tree/ITreeNode.java
@@ -24,4 +24,8 @@ import java.io.Serializable;
public interface ITreeNode extends Serializable {
String getName();
+
+ default String getAlias() {
+ return null;
+ }
}
diff --git
a/iotdb-core/node-commons/src/test/java/org/apache/iotdb/commons/path/PatternDFATest.java
b/iotdb-core/node-commons/src/test/java/org/apache/iotdb/commons/path/PatternDFATest.java
index f0ee0579e9b..147d9d2f505 100644
---
a/iotdb-core/node-commons/src/test/java/org/apache/iotdb/commons/path/PatternDFATest.java
+++
b/iotdb-core/node-commons/src/test/java/org/apache/iotdb/commons/path/PatternDFATest.java
@@ -34,6 +34,7 @@ import org.junit.Ignore;
import org.junit.Test;
import java.util.ArrayList;
+import java.util.Arrays;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
@@ -74,6 +75,50 @@ public class PatternDFATest {
dfaGraph.print(transitionMap);
}
+ @Test
+ @Ignore
+ public void printFASketch2() throws IllegalPathException {
+ // Map<AcceptEvent, IFATransition>
+ Map<String, IFATransition> transitionMap = new HashMap<>();
+ List<PartialPath> partialPathList =
+ Arrays.asList(
+ new PartialPath("root.sg2.**"),
+ new PartialPath("root.sg1.d1.**"),
+ new PartialPath("root.sg1.d2.**"),
+ new PartialPath("root.sg1.d2.s1"));
+ PathPatternTree patternTree = new PathPatternTree();
+ for (PartialPath pathPattern : partialPathList) {
+ patternTree.appendPathPattern(pathPattern);
+ }
+ patternTree.constructTree();
+ // 1. build transition
+ boolean wildcard = false;
+ AtomicInteger transitionIndex = new AtomicInteger();
+ for (PartialPath pathPattern : patternTree.getAllPathPatterns()) {
+ for (String node : pathPattern.getNodes()) {
+ if (IoTDBConstant.ONE_LEVEL_PATH_WILDCARD.equals(node)
+ || IoTDBConstant.MULTI_LEVEL_PATH_WILDCARD.equals(node)) {
+ wildcard = true;
+ } else {
+ transitionMap.computeIfAbsent(
+ node, i -> new
DFAPreciseTransition(transitionIndex.getAndIncrement(), node));
+ }
+ }
+ }
+ if (wildcard) {
+ IFATransition transition =
+ new DFAWildcardTransition(
+ transitionIndex.getAndIncrement(), new
ArrayList<>(transitionMap.keySet()));
+ transitionMap.put(transition.getAcceptEvent(), transition);
+ }
+ // 2. build NFA
+ NFAGraph nfaGraph = new NFAGraph(patternTree, transitionMap);
+ nfaGraph.print(transitionMap);
+ // 3. NFA to DFA
+ DFAGraph dfaGraph = new DFAGraph(nfaGraph, transitionMap.values());
+ dfaGraph.print(transitionMap);
+ }
+
@Test
public void testMatchFullPath() throws IllegalPathException {
PartialPath p1 = new PartialPath("root.sg1.d1.*");
