You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@iotdb.apache.org by zy...@apache.org on 2022/12/14 14:40:42 UTC
[iotdb] branch master updated: [IOTDB-5168] Refactor traverse of AbstractTreeVisitor to FA-based traverse (#8400)
This is an automated email from the ASF dual-hosted git repository.
zyk 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 8b4b397f9e [IOTDB-5168] Refactor traverse of AbstractTreeVisitor to FA-based traverse (#8400)
8b4b397f9e is described below
commit 8b4b397f9ebf17ba43c02f5d8dfeba7eebb29742
Author: Marcos_Zyk <38...@users.noreply.github.com>
AuthorDate: Wed Dec 14 22:40:34 2022 +0800
[IOTDB-5168] Refactor traverse of AbstractTreeVisitor to FA-based traverse (#8400)
[IOTDB-5168] Refactor traverse of AbstractTreeVisitor to FA-based traverse (#8400)
---
.../org/apache/iotdb/commons/path/fa/IFAState.java | 33 +
.../iotdb/commons/path/fa/IFATransition.java | 34 +
.../apache/iotdb/commons/path/fa/IPatternFA.java | 75 ++
.../apache/iotdb/commons/path/fa/SimpleNFA.java | 522 +++++++++++++
.../commons/path/fa/match/IStateMatchInfo.java | 79 ++
.../commons/path/fa/match/MatchedStateSet.java | 68 ++
.../commons/path/fa/match/StateMultiMatchInfo.java | 120 +++
.../path/fa/match/StateSingleMatchInfo.java | 103 +++
.../commons/schema/tree/AbstractTreeVisitor.java | 804 ++++++++++++---------
.../visitor/SchemaTreeDeviceVisitor.java | 2 +-
.../visitor/SchemaTreeMeasurementVisitor.java | 76 +-
.../schematree/visitor/SchemaTreeVisitor.java | 5 -
12 files changed, 1547 insertions(+), 374 deletions(-)
diff --git a/node-commons/src/main/java/org/apache/iotdb/commons/path/fa/IFAState.java b/node-commons/src/main/java/org/apache/iotdb/commons/path/fa/IFAState.java
new file mode 100644
index 0000000000..a21634086b
--- /dev/null
+++ b/node-commons/src/main/java/org/apache/iotdb/commons/path/fa/IFAState.java
@@ -0,0 +1,33 @@
+/*
+ * 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.iotdb.commons.path.fa;
+
+/** This interface defines the behaviour of a FA(Finite Automation)'s states. */
+public interface IFAState {
+
+ /** @return whether this state is the initial state of the belonged FA */
+ boolean isInitial();
+
+ /** @return whether this state is one of the final state of the belonged FA */
+ boolean isFinal();
+
+ /** @return the index of this state, used for uniquely identifying states in FA */
+ int getIndex();
+}
diff --git a/node-commons/src/main/java/org/apache/iotdb/commons/path/fa/IFATransition.java b/node-commons/src/main/java/org/apache/iotdb/commons/path/fa/IFATransition.java
new file mode 100644
index 0000000000..143c864ec6
--- /dev/null
+++ b/node-commons/src/main/java/org/apache/iotdb/commons/path/fa/IFATransition.java
@@ -0,0 +1,34 @@
+/*
+ * 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.iotdb.commons.path.fa;
+
+/** This interface defines the behaviour of a FA(Finite Automation)'s transition. */
+public interface IFATransition {
+
+ /** @return the value of this transition, which is used to match the events */
+ String getValue();
+
+ /**
+ * @param event event happened on one of the source state of this transition and is trying to find
+ * the next state
+ * @return whether this transition can match the event
+ */
+ boolean isMatch(String event);
+}
diff --git a/node-commons/src/main/java/org/apache/iotdb/commons/path/fa/IPatternFA.java b/node-commons/src/main/java/org/apache/iotdb/commons/path/fa/IPatternFA.java
new file mode 100644
index 0000000000..cd5c114ab7
--- /dev/null
+++ b/node-commons/src/main/java/org/apache/iotdb/commons/path/fa/IPatternFA.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.iotdb.commons.path.fa;
+
+import java.util.Iterator;
+import java.util.Map;
+
+/**
+ * This interface defines the behaviour of a FA(Finite Automation), generated from a path pattern or
+ * a pattern tree.
+ */
+public interface IPatternFA {
+
+ /**
+ * @param state the source state of the returned transitions
+ * @return transitions, that the given state has and only match one specified event rather than
+ * batch events
+ */
+ Map<String, IFATransition> getPreciseMatchTransition(IFAState state);
+
+ /**
+ * @param state the source state of the returned transitions
+ * @return transitions, that the given state has and only match one specified event rather than
+ * batch events
+ */
+ Iterator<IFATransition> getPreciseMatchTransitionIterator(IFAState state);
+
+ /**
+ * @param state state the source state of the returned transitions
+ * @return transitions, that the given state has and can match batch events
+ */
+ Iterator<IFATransition> getFuzzyMatchTransitionIterator(IFAState state);
+
+ /**
+ * @param state state the source state of the returned transitions
+ * @return num of transitions, that the given state has and can match batch events
+ */
+ int getFuzzyMatchTransitionSize(IFAState state);
+
+ /**
+ * @param sourceState source state
+ * @param transition transition that the source state has
+ * @return next state
+ */
+ IFAState getNextState(IFAState sourceState, IFATransition transition);
+
+ /** @return the initial state of this FA */
+ IFAState getInitialState();
+
+ /** @return the size of states this FA has */
+ int getStateSize();
+
+ /**
+ * @param index the index of the target state, used for uniquely identifying states in FA
+ * @return the state identified by given index
+ */
+ IFAState getState(int index);
+}
diff --git a/node-commons/src/main/java/org/apache/iotdb/commons/path/fa/SimpleNFA.java b/node-commons/src/main/java/org/apache/iotdb/commons/path/fa/SimpleNFA.java
new file mode 100644
index 0000000000..5eb3381101
--- /dev/null
+++ b/node-commons/src/main/java/org/apache/iotdb/commons/path/fa/SimpleNFA.java
@@ -0,0 +1,522 @@
+/*
+ * 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.iotdb.commons.path.fa;
+
+import org.apache.iotdb.commons.path.PartialPath;
+
+import java.util.Collections;
+import java.util.Iterator;
+import java.util.Map;
+import java.util.NoSuchElementException;
+import java.util.regex.Pattern;
+
+import static org.apache.iotdb.commons.conf.IoTDBConstant.MULTI_LEVEL_PATH_WILDCARD;
+import static org.apache.iotdb.commons.conf.IoTDBConstant.ONE_LEVEL_PATH_WILDCARD;
+
+/**
+ * Given path pattern root.sg.*.s, the SimpleNFA is:
+ *
+ * <p>initial -(root)-> state[0] -(sg)-> state[1] -(*)-> state[2] -(s)-> state[3] <br>
+ * state[3] is final state
+ *
+ * <p>Given path pattern root.**.s, the SimpleNFA is:
+ *
+ * <p>initial -(root)-> state[0] -(*)-> state[1] -(s)-> state[2] <br>
+ * with extra: state[1] -(*)-> state[1] and state[2] -(*)-> state[1] <br>
+ * state[3] is final state
+ *
+ * <p>Given path pattern root.sg.d with prefix match, the SimpleNFA is:
+ *
+ * <p>initial -(root)-> state[0] -(sg)-> state[1] -(d)-> state[2] -(*)-> state[3] <br>
+ * with extra: state[3] -(*)-> state[3] <br>
+ * both state[2] and state[3] are final states
+ */
+public class SimpleNFA implements IPatternFA {
+
+ private final boolean isPrefixMatch;
+
+ // raw nodes of pathPattern
+ private final String[] rawNodes;
+
+ // initial state of this NFA and the only transition from this state is "root"
+ private final SinglePathPatternNode initialState = new InitialNode();
+ // all states corresponding to raw pattern nodes, with an extra prefixMatch state
+ private final SinglePathPatternNode[] patternNodes;
+
+ public SimpleNFA(PartialPath pathPattern, boolean isPrefixMatch) {
+ this.isPrefixMatch = isPrefixMatch;
+ this.rawNodes = pathPattern.getNodes();
+ patternNodes = new SinglePathPatternNode[this.rawNodes.length + 1];
+ }
+
+ @Override
+ public Map<String, IFATransition> getPreciseMatchTransition(IFAState state) {
+ return getNextNode((SinglePathPatternNode) state).getPreNodePreciseMatchTransition();
+ }
+
+ @Override
+ public Iterator<IFATransition> getPreciseMatchTransitionIterator(IFAState state) {
+ return getNextNode((SinglePathPatternNode) state).getPreNodePreciseMatchTransitionIterator();
+ }
+
+ @Override
+ public Iterator<IFATransition> getFuzzyMatchTransitionIterator(IFAState state) {
+ return getNextNode((SinglePathPatternNode) state).getPreNodeFuzzyMatchTransitionIterator();
+ }
+
+ @Override
+ public int getFuzzyMatchTransitionSize(IFAState state) {
+ return getNextNode((SinglePathPatternNode) state).getPreNodeFuzzyMatchTransitionSize();
+ }
+
+ @Override
+ public IFAState getNextState(IFAState sourceState, IFATransition transition) {
+ return (SinglePathPatternNode) transition;
+ }
+
+ @Override
+ public IFAState getInitialState() {
+ return initialState;
+ }
+
+ @Override
+ public int getStateSize() {
+ return patternNodes.length;
+ }
+
+ @Override
+ public IFAState getState(int index) {
+ return patternNodes[index];
+ }
+
+ private SinglePathPatternNode getNextNode(SinglePathPatternNode currentNode) {
+ if (currentNode.patternIndex == rawNodes.length) {
+ return currentNode;
+ }
+ int nextIndex = currentNode.getIndex() + 1;
+ if (patternNodes[nextIndex] == null) {
+ if (nextIndex == rawNodes.length) {
+ patternNodes[nextIndex] = new PrefixMatchNode(nextIndex, currentNode.getTracebackNode());
+ } else if (rawNodes[nextIndex].equals(MULTI_LEVEL_PATH_WILDCARD)) {
+ patternNodes[nextIndex] = new MultiLevelWildcardMatchNode(nextIndex);
+ } else if (rawNodes[nextIndex].equals(ONE_LEVEL_PATH_WILDCARD)) {
+ patternNodes[nextIndex] =
+ new OneLevelWildcardMatchNode(nextIndex, currentNode.getTracebackNode());
+ } else if (rawNodes[nextIndex].contains(ONE_LEVEL_PATH_WILDCARD)) {
+ patternNodes[nextIndex] = new RegexMatchNode(nextIndex, currentNode.getTracebackNode());
+ } else {
+ patternNodes[nextIndex] = new NameMatchNode(nextIndex, currentNode.getTracebackNode());
+ }
+ }
+ return patternNodes[nextIndex];
+ }
+
+ // Each node in raw nodes of path pattern maps to a PatternNode, which can represent a state.
+ // Since the transition is defined by the node of next state, we directly let this class implement
+ // IFATransition.
+ private abstract class SinglePathPatternNode implements IFAState, IFATransition {
+
+ protected final int patternIndex;
+
+ protected final SinglePathPatternNode tracebackNode;
+
+ private SinglePathPatternNode(int patternIndex, SinglePathPatternNode tracebackNode) {
+ this.patternIndex = patternIndex;
+ this.tracebackNode = tracebackNode;
+ }
+
+ @Override
+ public boolean isInitial() {
+ return patternIndex == -1;
+ }
+
+ @Override
+ public boolean isFinal() {
+ return patternIndex >= rawNodes.length - 1;
+ }
+
+ @Override
+ public int getIndex() {
+ return patternIndex;
+ }
+
+ @Override
+ public String getValue() {
+ return rawNodes[patternIndex];
+ }
+
+ public SinglePathPatternNode getTracebackNode() {
+ return tracebackNode;
+ }
+
+ /**
+ * Since the transition generation of one patternNode need to judge based on next patternNode.
+ * Therefore, we implemented this method for previous node.
+ *
+ * @return the precise transitions of patternNode[patternIndex - 1]
+ */
+ protected abstract Map<String, IFATransition> getPreNodePreciseMatchTransition();
+
+ /**
+ * Since the transition generation of one patternNode need to judge based on next patternNode.
+ * Therefore, we implemented this method for previous node.
+ *
+ * @return the precise transitions of patternNode[patternIndex - 1]
+ */
+ protected abstract Iterator<IFATransition> getPreNodePreciseMatchTransitionIterator();
+
+ /**
+ * Since the transition generation of one patternNode need to judge based on next patternNode.
+ * Therefore, we implemented this method for previous node.
+ *
+ * @return the fuzzy transitions of patternNode[patternIndex - 1]
+ */
+ protected abstract Iterator<IFATransition> getPreNodeFuzzyMatchTransitionIterator();
+
+ /**
+ * Since the transition generation of one patternNode need to judge based on next patternNode.
+ * Therefore, we implemented this method for previous node.
+ *
+ * @return the num of fuzzy transitions of patternNode[patternIndex - 1]
+ */
+ protected abstract int getPreNodeFuzzyMatchTransitionSize();
+
+ @Override
+ public boolean equals(Object o) {
+ if (this == o) return true;
+ if (o == null || getClass() != o.getClass()) return false;
+ SinglePathPatternNode patternNode = (SinglePathPatternNode) o;
+ return patternIndex == patternNode.patternIndex;
+ }
+
+ @Override
+ public int hashCode() {
+ return patternIndex;
+ }
+ }
+
+ /** Initial node with patternIndex == -1. Holds the initial transition -(root)-> */
+ private class InitialNode extends SinglePathPatternNode {
+
+ private InitialNode() {
+ super(-1, null);
+ }
+
+ @Override
+ public boolean isInitial() {
+ return true;
+ }
+
+ @Override
+ protected Map<String, IFATransition> getPreNodePreciseMatchTransition() {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public boolean isMatch(String event) {
+ return false;
+ }
+
+ @Override
+ protected Iterator<IFATransition> getPreNodePreciseMatchTransitionIterator() {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ protected Iterator<IFATransition> getPreNodeFuzzyMatchTransitionIterator() {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ protected int getPreNodeFuzzyMatchTransitionSize() {
+ throw new UnsupportedOperationException();
+ }
+ }
+
+ /**
+ * The last node represents the prefix match state, and provides the transition access for
+ * patternNodes[rawNodes.length - 1]
+ */
+ private class PrefixMatchNode extends SinglePathPatternNode {
+
+ private PrefixMatchNode(int patternIndex, SinglePathPatternNode tracebackNode) {
+ super(patternIndex, tracebackNode);
+ }
+
+ @Override
+ public boolean isMatch(String event) {
+ return true;
+ }
+
+ @Override
+ protected Map<String, IFATransition> getPreNodePreciseMatchTransition() {
+ return Collections.emptyMap();
+ }
+
+ @Override
+ protected Iterator<IFATransition> getPreNodePreciseMatchTransitionIterator() {
+ return Collections.emptyIterator();
+ }
+
+ @Override
+ protected Iterator<IFATransition> getPreNodeFuzzyMatchTransitionIterator() {
+ if (isPrefixMatch) {
+ return new SingletonIterator<>(this);
+ } else {
+ if (tracebackNode == null) {
+ return Collections.emptyIterator();
+ } else {
+ return new SingletonIterator<>(tracebackNode);
+ }
+ }
+ }
+
+ @Override
+ protected int getPreNodeFuzzyMatchTransitionSize() {
+ return isPrefixMatch || tracebackNode != null ? 1 : 0;
+ }
+ }
+
+ /** The patternNode of the rawNode **. */
+ private class MultiLevelWildcardMatchNode extends SinglePathPatternNode {
+
+ private MultiLevelWildcardMatchNode(int patternIndex) {
+ super(patternIndex, null);
+ }
+
+ @Override
+ public SinglePathPatternNode getTracebackNode() {
+ return this;
+ }
+
+ @Override
+ public boolean isMatch(String event) {
+ return true;
+ }
+
+ @Override
+ protected Map<String, IFATransition> getPreNodePreciseMatchTransition() {
+ return Collections.emptyMap();
+ }
+
+ @Override
+ protected Iterator<IFATransition> getPreNodePreciseMatchTransitionIterator() {
+ return Collections.emptyIterator();
+ }
+
+ @Override
+ protected Iterator<IFATransition> getPreNodeFuzzyMatchTransitionIterator() {
+ return new SingletonIterator<>(this);
+ }
+
+ @Override
+ protected int getPreNodeFuzzyMatchTransitionSize() {
+ return 1;
+ }
+ }
+
+ /** The patternNode of the rawNode *. */
+ private class OneLevelWildcardMatchNode extends SinglePathPatternNode {
+
+ private OneLevelWildcardMatchNode(int patternIndex, SinglePathPatternNode tracebackNode) {
+ super(patternIndex, tracebackNode);
+ }
+
+ @Override
+ public boolean isMatch(String event) {
+ return true;
+ }
+
+ @Override
+ protected Map<String, IFATransition> getPreNodePreciseMatchTransition() {
+ return Collections.emptyMap();
+ }
+
+ @Override
+ protected Iterator<IFATransition> getPreNodePreciseMatchTransitionIterator() {
+ return Collections.emptyIterator();
+ }
+
+ @Override
+ protected Iterator<IFATransition> getPreNodeFuzzyMatchTransitionIterator() {
+ if (tracebackNode == null) {
+ return new SingletonIterator<>(this);
+ } else {
+ return new DualIterator<>(this, tracebackNode);
+ }
+ }
+
+ @Override
+ protected int getPreNodeFuzzyMatchTransitionSize() {
+ if (tracebackNode == null) {
+ return 1;
+ } else {
+ return 2;
+ }
+ }
+ }
+
+ /** The patternNode of the rawNode contains *, like d*. */
+ private class RegexMatchNode extends SinglePathPatternNode {
+
+ private Pattern regexPattern;
+
+ private RegexMatchNode(int patternIndex, SinglePathPatternNode tracebackNode) {
+ super(patternIndex, tracebackNode);
+ }
+
+ @Override
+ public boolean isMatch(String event) {
+ if (regexPattern == null) {
+ regexPattern = Pattern.compile(rawNodes[patternIndex].replace("*", ".*"));
+ }
+ return regexPattern.matcher(event).matches();
+ }
+
+ @Override
+ protected Map<String, IFATransition> getPreNodePreciseMatchTransition() {
+ return Collections.emptyMap();
+ }
+
+ @Override
+ protected Iterator<IFATransition> getPreNodePreciseMatchTransitionIterator() {
+ return Collections.emptyIterator();
+ }
+
+ @Override
+ protected Iterator<IFATransition> getPreNodeFuzzyMatchTransitionIterator() {
+ if (tracebackNode == null) {
+ return new SingletonIterator<>(this);
+ } else {
+ return new DualIterator<>(this, tracebackNode);
+ }
+ }
+
+ @Override
+ protected int getPreNodeFuzzyMatchTransitionSize() {
+ if (tracebackNode == null) {
+ return 1;
+ } else {
+ return 2;
+ }
+ }
+ }
+
+ /** The patternNode of the rawNode which is a specified name. */
+ private class NameMatchNode extends SinglePathPatternNode {
+
+ private Map<String, IFATransition> preNodePreciseMatchTransitionMap;
+
+ private NameMatchNode(int patternIndex, SinglePathPatternNode tracebackNode) {
+ super(patternIndex, tracebackNode);
+ }
+
+ @Override
+ public boolean isMatch(String event) {
+ return rawNodes[patternIndex].equals(event);
+ }
+
+ @Override
+ protected Map<String, IFATransition> getPreNodePreciseMatchTransition() {
+ if (preNodePreciseMatchTransitionMap == null) {
+ preNodePreciseMatchTransitionMap = Collections.singletonMap(rawNodes[patternIndex], this);
+ }
+ return preNodePreciseMatchTransitionMap;
+ }
+
+ @Override
+ protected Iterator<IFATransition> getPreNodePreciseMatchTransitionIterator() {
+ return new SingletonIterator<>(this);
+ }
+
+ @Override
+ protected Iterator<IFATransition> getPreNodeFuzzyMatchTransitionIterator() {
+ if (tracebackNode == null) {
+ return Collections.emptyIterator();
+ } else {
+ return new SingletonIterator<>(tracebackNode);
+ }
+ }
+
+ @Override
+ protected int getPreNodeFuzzyMatchTransitionSize() {
+ if (tracebackNode == null) {
+ return 0;
+ } else {
+ return 1;
+ }
+ }
+ }
+
+ private static class SingletonIterator<E> implements Iterator<E> {
+
+ private E e;
+
+ private SingletonIterator(E e) {
+ this.e = e;
+ }
+
+ @Override
+ public boolean hasNext() {
+ return e != null;
+ }
+
+ @Override
+ public E next() {
+ if (!hasNext()) {
+ throw new NoSuchElementException();
+ }
+ E result = e;
+ e = null;
+ return result;
+ }
+ }
+
+ private static class DualIterator<E> implements Iterator<E> {
+ private E e1;
+ private E e2;
+
+ private DualIterator(E e1, E e2) {
+ this.e1 = e1;
+ this.e2 = e2;
+ }
+
+ @Override
+ public boolean hasNext() {
+ return e2 != null;
+ }
+
+ @Override
+ public E next() {
+ if (!hasNext()) {
+ throw new NoSuchElementException();
+ }
+ E result;
+ if (e1 != null) {
+ result = e1;
+ e1 = null;
+ } else {
+ result = e2;
+ e2 = null;
+ }
+ return result;
+ }
+ }
+}
diff --git a/node-commons/src/main/java/org/apache/iotdb/commons/path/fa/match/IStateMatchInfo.java b/node-commons/src/main/java/org/apache/iotdb/commons/path/fa/match/IStateMatchInfo.java
new file mode 100644
index 0000000000..4e050c1d7e
--- /dev/null
+++ b/node-commons/src/main/java/org/apache/iotdb/commons/path/fa/match/IStateMatchInfo.java
@@ -0,0 +1,79 @@
+/*
+ * 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.iotdb.commons.path.fa.match;
+
+import org.apache.iotdb.commons.path.fa.IFAState;
+import org.apache.iotdb.commons.path.fa.IFATransition;
+
+import java.util.Iterator;
+
+/**
+ * This interface defines the behaviour of a state match info, which helps make decision during FA
+ * Graph traversing
+ */
+public interface IStateMatchInfo {
+
+ /** @return whether current matched state has a final state */
+ boolean hasFinalState();
+
+ /**
+ * @return whether the transitions, current matched states have, are only precise match
+ * transition, that only matches specified event rather than batch events
+ */
+ boolean hasOnlyPreciseMatchTransition();
+
+ /**
+ * @return whether none of the transitions, current matched states have, is precise match
+ * transition, that only matches specified event rather than batch events
+ */
+ boolean hasNoPreciseMatchTransition();
+
+ /**
+ * @return whether current match state only have one transition, and it is a fuzzy transition that
+ * may match batch events
+ */
+ boolean isSingleFuzzyMatchTransition();
+
+ /** @return one of the matched state */
+ IFAState getOneMatchedState();
+
+ void addMatchedState(IFAState state);
+
+ /**
+ * @param stateOrdinal the target state's ordinal of matched order
+ * @return the ordinal(th) matched state
+ */
+ IFAState getMatchedState(int stateOrdinal);
+
+ /** @return size of current matched states */
+ int getMatchedStateSize();
+
+ /** @return the ordinal of the source state in matched order */
+ int getSourceStateOrdinal();
+
+ /** @param sourceStateOrdinal the ordinal of the source state in matched order */
+ void setSourceStateOrdinal(int sourceStateOrdinal);
+
+ /** @return the iterator of current checking source states' transition */
+ Iterator<IFATransition> getSourceTransitionIterator();
+
+ /** @param sourceTransitionIterator the iterator of current checking source states' transition */
+ void setSourceTransitionIterator(Iterator<IFATransition> sourceTransitionIterator);
+}
diff --git a/node-commons/src/main/java/org/apache/iotdb/commons/path/fa/match/MatchedStateSet.java b/node-commons/src/main/java/org/apache/iotdb/commons/path/fa/match/MatchedStateSet.java
new file mode 100644
index 0000000000..7a94ff8c67
--- /dev/null
+++ b/node-commons/src/main/java/org/apache/iotdb/commons/path/fa/match/MatchedStateSet.java
@@ -0,0 +1,68 @@
+/*
+ * 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.iotdb.commons.path.fa.match;
+
+import org.apache.iotdb.commons.path.fa.IFAState;
+
+/** This class is used for recording the states, matched by one item, in order. */
+public class MatchedStateSet {
+ private static final int INITIAL_SIZE = 8;
+
+ /**
+ * Status of all states, identified by index in target FA. stateStatus[k] == true means state with
+ * index equals k is already in this set.
+ */
+ private final boolean[] stateStatus;
+
+ /** The existing state in this state, stored in the putting order. */
+ private int[] existingState = new int[INITIAL_SIZE];
+
+ private int end = 0;
+
+ /**
+ * Construct an empty set with given capacity. This set stores states no more than given cpacity.
+ *
+ * @param capacity generally, we use stateSize as capacity
+ */
+ MatchedStateSet(int capacity) {
+ stateStatus = new boolean[capacity];
+ }
+
+ void add(IFAState state) {
+ if (stateStatus[state.getIndex()]) {
+ return;
+ }
+ if (end == existingState.length) {
+ int[] array = new int[existingState.length * 2];
+ System.arraycopy(existingState, 0, array, 0, end);
+ existingState = array;
+ }
+ existingState[end++] = state.getIndex();
+ stateStatus[state.getIndex()] = true;
+ }
+
+ int getStateIndex(int stateOrdinal) {
+ return existingState[stateOrdinal];
+ }
+
+ int size() {
+ return end;
+ }
+}
diff --git a/node-commons/src/main/java/org/apache/iotdb/commons/path/fa/match/StateMultiMatchInfo.java b/node-commons/src/main/java/org/apache/iotdb/commons/path/fa/match/StateMultiMatchInfo.java
new file mode 100644
index 0000000000..fbad7e70a4
--- /dev/null
+++ b/node-commons/src/main/java/org/apache/iotdb/commons/path/fa/match/StateMultiMatchInfo.java
@@ -0,0 +1,120 @@
+/*
+ * 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.iotdb.commons.path.fa.match;
+
+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 java.util.Iterator;
+
+/** This class is used for cases need traceback. */
+public class StateMultiMatchInfo implements IStateMatchInfo {
+
+ private final IPatternFA patternFA;
+
+ private final MatchedStateSet matchedStateSet;
+
+ private int sourceStateIndex;
+
+ private Iterator<IFATransition> sourceTransitionIterator;
+
+ private boolean hasFinalState = false;
+
+ public StateMultiMatchInfo(IPatternFA patternFA) {
+ this.patternFA = patternFA;
+ matchedStateSet = new MatchedStateSet(patternFA.getStateSize());
+ }
+
+ public StateMultiMatchInfo(
+ IPatternFA patternFA,
+ IFAState matchedState,
+ Iterator<IFATransition> sourceTransitionIterator) {
+ this.patternFA = patternFA;
+ matchedStateSet = new MatchedStateSet(patternFA.getStateSize());
+ matchedStateSet.add(matchedState);
+ sourceStateIndex = 0;
+ this.sourceTransitionIterator = sourceTransitionIterator;
+ this.hasFinalState = matchedState.isFinal();
+ }
+
+ @Override
+ public boolean hasFinalState() {
+ return hasFinalState;
+ }
+
+ @Override
+ public boolean hasOnlyPreciseMatchTransition() {
+ return false;
+ }
+
+ @Override
+ public boolean hasNoPreciseMatchTransition() {
+ return false;
+ }
+
+ @Override
+ public boolean isSingleFuzzyMatchTransition() {
+ return false;
+ }
+
+ @Override
+ public IFAState getOneMatchedState() {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public void addMatchedState(IFAState state) {
+ matchedStateSet.add(state);
+ if (state.isFinal()) {
+ hasFinalState = true;
+ }
+ }
+
+ @Override
+ public IFAState getMatchedState(int stateOrdinal) {
+ return patternFA.getState(matchedStateSet.getStateIndex(stateOrdinal));
+ }
+
+ @Override
+ public int getMatchedStateSize() {
+ return matchedStateSet.size();
+ }
+
+ @Override
+ public int getSourceStateOrdinal() {
+ return sourceStateIndex;
+ }
+
+ @Override
+ public void setSourceStateOrdinal(int sourceStateOrdinal) {
+ this.sourceStateIndex = sourceStateOrdinal;
+ }
+
+ @Override
+ public Iterator<IFATransition> getSourceTransitionIterator() {
+ return sourceTransitionIterator;
+ }
+
+ @Override
+ public void setSourceTransitionIterator(Iterator<IFATransition> sourceTransitionIterator) {
+ this.sourceTransitionIterator = sourceTransitionIterator;
+ }
+}
diff --git a/node-commons/src/main/java/org/apache/iotdb/commons/path/fa/match/StateSingleMatchInfo.java b/node-commons/src/main/java/org/apache/iotdb/commons/path/fa/match/StateSingleMatchInfo.java
new file mode 100644
index 0000000000..e3ccf7df61
--- /dev/null
+++ b/node-commons/src/main/java/org/apache/iotdb/commons/path/fa/match/StateSingleMatchInfo.java
@@ -0,0 +1,103 @@
+/*
+ * 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.iotdb.commons.path.fa.match;
+
+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 java.util.Iterator;
+
+/** This class is only used for cases not need traceback yet. */
+public class StateSingleMatchInfo implements IStateMatchInfo {
+
+ private final IPatternFA patternFA;
+
+ private final IFAState matchedState;
+
+ public StateSingleMatchInfo(IPatternFA patternFA, IFAState matchedState) {
+ this.patternFA = patternFA;
+ this.matchedState = matchedState;
+ }
+
+ @Override
+ public boolean hasFinalState() {
+ return matchedState.isFinal();
+ }
+
+ @Override
+ public boolean hasOnlyPreciseMatchTransition() {
+ return patternFA.getFuzzyMatchTransitionSize(matchedState) == 0;
+ }
+
+ @Override
+ public boolean hasNoPreciseMatchTransition() {
+ return patternFA.getPreciseMatchTransition(matchedState).isEmpty();
+ }
+
+ @Override
+ public boolean isSingleFuzzyMatchTransition() {
+ return patternFA.getFuzzyMatchTransitionSize(matchedState) == 1;
+ }
+
+ @Override
+ public IFAState getOneMatchedState() {
+ return matchedState;
+ }
+
+ @Override
+ public void addMatchedState(IFAState state) {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public IFAState getMatchedState(int stateOrdinal) {
+ if (stateOrdinal == 0) {
+ return matchedState;
+ } else {
+ throw new IllegalStateException();
+ }
+ }
+
+ @Override
+ public int getMatchedStateSize() {
+ return 1;
+ }
+
+ @Override
+ public int getSourceStateOrdinal() {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public void setSourceStateOrdinal(int sourceStateOrdinal) {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public Iterator<IFATransition> getSourceTransitionIterator() {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public void setSourceTransitionIterator(Iterator<IFATransition> sourceTransitionIterator) {
+ throw new UnsupportedOperationException();
+ }
+}
diff --git a/node-commons/src/main/java/org/apache/iotdb/commons/schema/tree/AbstractTreeVisitor.java b/node-commons/src/main/java/org/apache/iotdb/commons/schema/tree/AbstractTreeVisitor.java
index dfb0c7acfe..efe829cec1 100644
--- a/node-commons/src/main/java/org/apache/iotdb/commons/schema/tree/AbstractTreeVisitor.java
+++ b/node-commons/src/main/java/org/apache/iotdb/commons/schema/tree/AbstractTreeVisitor.java
@@ -20,18 +20,21 @@
package org.apache.iotdb.commons.schema.tree;
import org.apache.iotdb.commons.path.PartialPath;
+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.SimpleNFA;
+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 java.util.ArrayDeque;
import java.util.ArrayList;
-import java.util.Collections;
import java.util.Deque;
import java.util.Iterator;
import java.util.List;
+import java.util.Map;
import java.util.NoSuchElementException;
-import java.util.regex.Pattern;
-
-import static org.apache.iotdb.commons.conf.IoTDBConstant.MULTI_LEVEL_PATH_WILDCARD;
-import static org.apache.iotdb.commons.conf.IoTDBConstant.ONE_LEVEL_PATH_WILDCARD;
/**
* This class defines a dfs-based algorithm of tree-traversing with path pattern match, and support
@@ -63,47 +66,57 @@ public abstract class AbstractTreeVisitor<N extends ITreeNode, R> implements Ite
// command parameters
protected final N root;
- protected final String[] nodes;
- protected final boolean isPrefixMatch;
- // run time variables
- protected final Deque<VisitorStackEntry<N>> visitorStack = new ArrayDeque<>();
- protected final Deque<AncestorStackEntry<N>> ancestorStack = new ArrayDeque<>();
- protected boolean shouldVisitSubtree;
+ // finite automation constructed from given path pattern or pattern tree
+ protected final IPatternFA patternFA;
- // result variables
+ // run time variables
+ // stack to store children iterator of visited ancestor
+ private final Deque<VisitorStackEntry> visitorStack = new ArrayDeque<>();
+ // stack to store ancestor nodes and their FA state match info
+ private final List<AncestorStackEntry> ancestorStack = new ArrayList<>();
+ // the FA match process can traceback since this ancestor in ancestor stack
+ // this field will be updated during iterating children in all subclass of
+ // AbstractChildrenIterator
+ private int firstAncestorOfTraceback = -1;
+ // the FA state match info of current node
+ // this field will be updated during iterating children in all subclass of
+ // AbstractChildrenIterator
+ private IStateMatchInfo currentStateMatchInfo;
+ // whether to visit the subtree of current node
+ private boolean shouldVisitSubtree;
+
+ // cached result variables
protected N nextMatchedNode;
- protected int patternIndexOfMatchedNode;
- protected int lastMultiLevelWildcardIndexOfMatchedNode;
protected AbstractTreeVisitor(N root, PartialPath pathPattern, boolean isPrefixMatch) {
this.root = root;
- this.nodes = optimizePathPattern(pathPattern);
- this.isPrefixMatch = isPrefixMatch;
- visitorStack.push(
- new VisitorStackEntry<>(Collections.singletonList(root).iterator(), 0, 0, -1));
+ this.patternFA = new SimpleNFA(pathPattern, isPrefixMatch);
+
+ initStack();
}
- /**
- * Optimize the given path pattern. Currently, the node name used for one level match will be
- * transformed into a regex. e.g. given pathPattern {"root", "sg", "d*", "s"} and the
- * optimizedPathPattern is {"root", "sg", "d.*", "s"}.
- */
- private String[] optimizePathPattern(PartialPath pathPattern) {
- String[] rawNodes = pathPattern.getNodes();
- List<String> optimizedNodes = new ArrayList<>(rawNodes.length);
- for (String rawNode : rawNodes) {
- if (rawNode.equals(MULTI_LEVEL_PATH_WILDCARD)) {
- optimizedNodes.add(MULTI_LEVEL_PATH_WILDCARD);
- } else if (rawNode.contains(ONE_LEVEL_PATH_WILDCARD)) {
- optimizedNodes.add(rawNode.replace("*", ".*"));
- } else {
- optimizedNodes.add(rawNode);
- }
+ private void initStack() {
+ IFAState initialState = patternFA.getInitialState();
+ IFATransition transition =
+ patternFA.getPreciseMatchTransition(initialState).get(root.getName());
+ if (transition == null) {
+ // the visitor stack will be empty and the result of hasNext() will be false
+ return;
}
+ IFAState rootState = patternFA.getNextState(initialState, transition);
+ currentStateMatchInfo = new StateSingleMatchInfo(patternFA, rootState);
+ visitorStack.push(new VisitorStackEntry(createChildrenIterator(root), 1));
+ ancestorStack.add(new AncestorStackEntry(root, currentStateMatchInfo));
+ }
- return optimizedNodes.toArray(new String[0]);
+ public void reset() {
+ visitorStack.clear();
+ ancestorStack.clear();
+ nextMatchedNode = null;
+ firstAncestorOfTraceback = -1;
+ initStack();
}
@Override
@@ -119,52 +132,16 @@ public abstract class AbstractTreeVisitor<N extends ITreeNode, R> implements Ite
if (!hasNext()) {
throw new NoSuchElementException();
}
- return consumeNextMatchedNode();
- }
-
- private R consumeNextMatchedNode() {
R result = generateResult();
-
- // after the node be consumed, the subTree should be considered.
- if (patternIndexOfMatchedNode == nodes.length) {
- pushChildrenWhilePrefixMatch(
- nextMatchedNode, patternIndexOfMatchedNode, lastMultiLevelWildcardIndexOfMatchedNode);
- } else if (patternIndexOfMatchedNode == nodes.length - 1) {
- pushChildrenWhileTail(
- nextMatchedNode, patternIndexOfMatchedNode, lastMultiLevelWildcardIndexOfMatchedNode);
- } else {
- pushChildrenWhileInternal(
- nextMatchedNode, patternIndexOfMatchedNode, lastMultiLevelWildcardIndexOfMatchedNode);
- }
-
nextMatchedNode = null;
return result;
}
- /**
- * Basically, the algorithm traverse the tree with dfs strategy. When it comes to push children
- * into stack, the path pattern will be used to filter the children.
- *
- * <p>When there's MULTI_LEVEL_WILDCARD in given path pattern. There are the following notices:
- *
- * <ol>
- * <li>When it comes to push children into stack and there's MULTI_LEVEL_WILDCARD before the
- * current patternIndex, all the children will be pushed.
- * <li>When a node cannot match the target node name in the patternIndex place and there's
- * MULTI_LEVEL_WILDCARD before the current patternIndex, the node names between the current
- * patternIndex and lastMultiLevelWildcardIndex will be checked until the partial path end
- * with current node can match one. The children will be pushed with the matched index + 1.
- * </ol>
- *
- * <p>Each node and fullPath of the tree will be traversed at most once.
- */
protected void getNext() {
nextMatchedNode = null;
- VisitorStackEntry<N> stackEntry;
- int patternIndex;
+ VisitorStackEntry stackEntry;
N node;
Iterator<N> iterator;
- int lastMultiLevelWildcardIndex;
while (!visitorStack.isEmpty()) {
stackEntry = visitorStack.peek();
iterator = stackEntry.iterator;
@@ -175,135 +152,47 @@ public abstract class AbstractTreeVisitor<N extends ITreeNode, R> implements Ite
}
node = iterator.next();
- patternIndex = stackEntry.patternIndex;
- lastMultiLevelWildcardIndex = stackEntry.lastMultiLevelWildcardIndex;
-
- // only prefixMatch
- if (patternIndex == nodes.length) {
-
- shouldVisitSubtree = processFullMatchedNode(node) && isInternalNode(node);
-
- if (nextMatchedNode != null) {
- saveNextMatchedNodeContext(patternIndex, lastMultiLevelWildcardIndex);
- return;
- }
- if (shouldVisitSubtree) {
- pushChildrenWhilePrefixMatch(node, patternIndex, lastMultiLevelWildcardIndex);
- }
-
- continue;
- }
-
- if (checkIsMatch(patternIndex, node)) {
- if (patternIndex == nodes.length - 1) {
- shouldVisitSubtree = processFullMatchedNode(node) && isInternalNode(node);
-
- if (nextMatchedNode != null) {
- saveNextMatchedNodeContext(patternIndex, lastMultiLevelWildcardIndex);
- return;
- }
-
- if (shouldVisitSubtree) {
- pushChildrenWhileTail(node, patternIndex, lastMultiLevelWildcardIndex);
- }
- } else {
- shouldVisitSubtree = processInternalMatchedNode(node) && isInternalNode(node);
-
- if (nextMatchedNode != null) {
- saveNextMatchedNodeContext(patternIndex, lastMultiLevelWildcardIndex);
- return;
- }
-
- if (shouldVisitSubtree) {
- pushChildrenWhileInternal(node, patternIndex, lastMultiLevelWildcardIndex);
- }
- }
+ if (currentStateMatchInfo.hasFinalState()) {
+ shouldVisitSubtree = processFullMatchedNode(node);
} else {
- if (lastMultiLevelWildcardIndex == -1) {
- continue;
- }
-
- int lastMatchIndex = findLastMatch(node, patternIndex, lastMultiLevelWildcardIndex);
-
- shouldVisitSubtree = processInternalMatchedNode(node) && isInternalNode(node);
-
- if (nextMatchedNode != null) {
- saveNextMatchedNodeContext(lastMatchIndex, lastMultiLevelWildcardIndex);
- return;
- }
-
- if (shouldVisitSubtree) {
- pushChildrenWhileInternal(node, lastMatchIndex, lastMultiLevelWildcardIndex);
- }
+ shouldVisitSubtree = processInternalMatchedNode(node);
}
- }
- }
- /**
- * The context, mainly the matching info, of nextedMatchedNode should be saved. When the
- * nextedMatchedNode is consumed, the saved info will be used to process its subtree.
- */
- private void saveNextMatchedNodeContext(
- int patternIndexOfMatchedNode, int lastMultiLevelWildcardIndexOfMatchedNode) {
- this.patternIndexOfMatchedNode = patternIndexOfMatchedNode;
- this.lastMultiLevelWildcardIndexOfMatchedNode = lastMultiLevelWildcardIndexOfMatchedNode;
- }
-
- /**
- * When current node cannot match the pattern node in nodes[patternIndex] and there is ** before
- * current pattern node, the pattern nodes before current pattern node should be checked. For
- * example, given path root.sg.d.s and path pattern root.**.s. A status, root.sg.d not match
- * root.**.s, may be reached during traversing process, then it should be checked and found that
- * root.sg.d could match root.**, after which the process could continue and find root.sg.d.s
- * matches root.**.s.
- */
- private int findLastMatch(N node, int patternIndex, int lastMultiLevelWildcardIndex) {
- for (int i = patternIndex - 1; i > lastMultiLevelWildcardIndex; i--) {
- if (!checkIsMatch(i, node)) {
- continue;
+ if (shouldVisitSubtree) {
+ pushChildren(node);
}
- Iterator<AncestorStackEntry<N>> ancestors = ancestorStack.iterator();
- boolean allMatch = true;
- AncestorStackEntry<N> ancestor;
- for (int j = i - 1; j > lastMultiLevelWildcardIndex; j--) {
- ancestor = ancestors.next();
- if (ancestor.isMatched(j)) {
- break;
- }
-
- if (ancestor.hasBeenChecked(j) || !checkIsMatch(j, ancestor.node)) {
- ancestors = ancestorStack.iterator();
- for (int k = i - 1; k >= j; k--) {
- ancestors.next().setNotMatched(k);
- }
- allMatch = false;
- break;
- }
- }
-
- if (allMatch) {
- ancestors = ancestorStack.iterator();
- for (int k = i - 1; k > lastMultiLevelWildcardIndex; k--) {
- ancestor = ancestors.next();
- if (ancestor.isMatched(k)) {
- break;
- }
- ancestor.setMatched(k);
- }
- return i;
+ if (nextMatchedNode != null) {
+ return;
}
}
- return lastMultiLevelWildcardIndex;
}
- public void reset() {
- visitorStack.clear();
- ancestorStack.clear();
- nextMatchedNode = null;
+ private void pushChildren(N parent) {
visitorStack.push(
- new VisitorStackEntry<>(Collections.singletonList(root).iterator(), 0, 0, -1));
+ new VisitorStackEntry(createChildrenIterator(parent), visitorStack.peek().level + 1));
+ ancestorStack.add(new AncestorStackEntry(parent, currentStateMatchInfo));
+ }
+
+ private Iterator<N> createChildrenIterator(N parent) {
+ if (firstAncestorOfTraceback > -1) {
+ // there may be traceback when try to find the matched state of node
+ 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());
+ } 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());
+ } 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());
+ }
}
private void popStack() {
@@ -311,152 +200,35 @@ public abstract class AbstractTreeVisitor<N extends ITreeNode, R> implements Ite
// The ancestor pop operation with level check supports the children of one node pushed by
// batch.
if (!visitorStack.isEmpty() && visitorStack.peek().level < ancestorStack.size()) {
- ancestorStack.pop();
- }
- }
-
- /**
- * This method is invoked to decide how to push children of given node. Invoked only when
- * patternIndex == nodes.length.
- *
- * @param node the current processed node
- * @param patternIndex the patternIndex for the given node
- * @param lastMultiLevelWildcardIndex the lastMultiLevelWildcardIndex of the given node
- */
- private void pushChildrenWhilePrefixMatch(
- N node, int patternIndex, int lastMultiLevelWildcardIndex) {
- pushAllChildren(node, patternIndex, lastMultiLevelWildcardIndex);
- }
-
- /**
- * This method is invoked to decide how to push children of given node. Invoked only when
- * patternIndex == nodes.length - 1.
- *
- * @param node the current processed node
- * @param patternIndex the patternIndex for the given node
- * @param lastMultiLevelWildcardIndex the lastMultiLevelWildcardIndex of the given node
- */
- private void pushChildrenWhileTail(N node, int patternIndex, int lastMultiLevelWildcardIndex) {
- if (nodes[patternIndex].equals(MULTI_LEVEL_PATH_WILDCARD)) {
- pushAllChildren(node, patternIndex, patternIndex);
- } else if (lastMultiLevelWildcardIndex != -1) {
- pushAllChildren(
- node,
- findLastMatch(node, patternIndex, lastMultiLevelWildcardIndex) + 1,
- lastMultiLevelWildcardIndex);
- } else if (isPrefixMatch) {
- pushAllChildren(node, patternIndex + 1, lastMultiLevelWildcardIndex);
- }
- }
-
- /**
- * This method is invoked to decide how to push children of given node. Invoked only when
- * patternIndex < nodes.length - 1.
- *
- * @param node the current processed node
- * @param patternIndex the patternIndex for the given node
- * @param lastMultiLevelWildcardIndex the lastMultiLevelWildcardIndex of the given node
- */
- private void pushChildrenWhileInternal(
- N node, int patternIndex, int lastMultiLevelWildcardIndex) {
- if (nodes[patternIndex + 1].equals(MULTI_LEVEL_PATH_WILDCARD)) {
- pushAllChildren(node, patternIndex + 1, patternIndex + 1);
- } else {
- if (lastMultiLevelWildcardIndex > -1) {
- pushAllChildren(node, patternIndex + 1, lastMultiLevelWildcardIndex);
- } else if (nodes[patternIndex + 1].contains(ONE_LEVEL_PATH_WILDCARD)) {
- pushAllChildren(node, patternIndex + 1, lastMultiLevelWildcardIndex);
- } else {
- pushSingleChild(node, patternIndex + 1, lastMultiLevelWildcardIndex);
+ ancestorStack.remove(ancestorStack.size() - 1);
+ if (ancestorStack.size() <= firstAncestorOfTraceback) {
+ firstAncestorOfTraceback = -1;
}
}
}
- /**
- * Push child for name match case.
- *
- * @param parent the parent node of target children
- * @param patternIndex the patternIndex to match children
- * @param lastMultiLevelWildcardIndex the lastMultiLevelWildcardIndex of child
- */
- protected void pushSingleChild(N parent, int patternIndex, int lastMultiLevelWildcardIndex) {
- N child = getChild(parent, nodes[patternIndex]);
- if (child != null) {
- ancestorStack.push(
- new AncestorStackEntry<>(
- parent,
- visitorStack.peek().patternIndex,
- visitorStack.peek().lastMultiLevelWildcardIndex));
- visitorStack.push(
- new VisitorStackEntry<>(
- Collections.singletonList(child).iterator(),
- patternIndex,
- ancestorStack.size(),
- lastMultiLevelWildcardIndex));
+ protected final String[] generateFullPathNodes() {
+ List<String> nodeNames = new ArrayList<>();
+ Iterator<AncestorStackEntry> iterator = ancestorStack.iterator();
+ for (int i = 0, size = shouldVisitSubtree ? ancestorStack.size() - 1 : ancestorStack.size();
+ i < size;
+ i++) {
+ if (iterator.hasNext()) {
+ nodeNames.add(iterator.next().node.getName());
+ }
}
+ nodeNames.add(nextMatchedNode.getName());
+ return nodeNames.toArray(new String[0]);
}
- /**
- * Push children for the following cases:
- *
- * <ol>
- * <li>the pattern to match children is **, multiLevelWildcard
- * <li>the pattern to match children contains *, oneLevelWildcard
- * <li>there's ** before the patternIndex for children
- * </ol>
- *
- * @param parent the parent node of target children
- * @param patternIndex the patternIndex to match children
- * @param lastMultiLevelWildcardIndex the lastMultiLevelWildcardIndex of child
- */
- protected void pushAllChildren(N parent, int patternIndex, int lastMultiLevelWildcardIndex) {
- ancestorStack.push(
- new AncestorStackEntry<>(
- parent,
- visitorStack.peek().patternIndex,
- visitorStack.peek().lastMultiLevelWildcardIndex));
- visitorStack.push(
- new VisitorStackEntry<>(
- getChildrenIterator(parent),
- patternIndex,
- ancestorStack.size(),
- lastMultiLevelWildcardIndex));
- }
-
- protected boolean checkIsMatch(int patternIndex, N node) {
- if (nodes[patternIndex].equals(MULTI_LEVEL_PATH_WILDCARD)) {
- return true;
- } else if (nodes[patternIndex].contains(ONE_LEVEL_PATH_WILDCARD)) {
- return checkOneLevelWildcardMatch(nodes[patternIndex], node);
+ protected final N getParentOfNextMatchedNode() {
+ if (shouldVisitSubtree) {
+ return ancestorStack.get(ancestorStack.size() - 2).node;
} else {
- return checkNameMatch(nodes[patternIndex], node);
+ return ancestorStack.get(ancestorStack.size() - 1).node;
}
}
- protected boolean checkOneLevelWildcardMatch(String regex, N node) {
- return Pattern.matches(regex, node.getName());
- }
-
- protected boolean checkNameMatch(String targetName, N node) {
- return targetName.equals(node.getName());
- }
-
- protected String[] generateFullPathNodes(N node) {
- List<String> nodeNames = new ArrayList<>();
- Iterator<AncestorStackEntry<N>> iterator = ancestorStack.descendingIterator();
- while (iterator.hasNext()) {
- nodeNames.add(iterator.next().node.getName());
- }
- nodeNames.add(node.getName());
- return nodeNames.toArray(new String[0]);
- }
-
- /**
- * Check whether the given node is an internal node of this tree. Return true if the given node is
- * an internal node. Return false if the given node is a leaf node.
- */
- protected abstract boolean isInternalNode(N node);
-
// Get a child with the given childName.
protected abstract N getChild(N parent, String childName);
@@ -487,54 +259,384 @@ public abstract class AbstractTreeVisitor<N extends ITreeNode, R> implements Ite
/** The method used for generating the result based on the matched node. */
protected abstract R generateResult();
- protected static class VisitorStackEntry<N> {
+ private class VisitorStackEntry {
+ // children iterator
private final Iterator<N> iterator;
- private final int patternIndex;
+
+ // level of children taken from iterator
private final int level;
- private final int lastMultiLevelWildcardIndex;
- VisitorStackEntry(
- Iterator<N> iterator, int patternIndex, int level, int lastMultiLevelWildcardIndex) {
+ VisitorStackEntry(Iterator<N> iterator, int level) {
this.iterator = iterator;
- this.patternIndex = patternIndex;
this.level = level;
- this.lastMultiLevelWildcardIndex = lastMultiLevelWildcardIndex;
}
}
- protected static class AncestorStackEntry<N> {
+ private class AncestorStackEntry {
private final N node;
- private final int matchedIndex;
- /** Record the check result to reduce repeating check. */
- private final byte[] matchStatus;
- AncestorStackEntry(N node, int matchedIndex, int lastMultiLevelWildcardIndex) {
+ private final IStateMatchInfo stateMatchInfo;
+
+ AncestorStackEntry(N node, IStateMatchInfo stateMatchInfo) {
this.node = node;
- this.matchedIndex = matchedIndex;
- matchStatus = new byte[matchedIndex - lastMultiLevelWildcardIndex + 1];
- matchStatus[0] = 1;
- matchStatus[matchStatus.length - 1] = 1;
+ this.stateMatchInfo = stateMatchInfo;
+ }
+ }
+
+ // implement common iterating logic of different children iterator
+ private abstract class AbstractChildrenIterator implements Iterator<N> {
+
+ private N nextMatchedChild;
+
+ @Override
+ public boolean hasNext() {
+ if (nextMatchedChild == null) {
+ getNext();
+ }
+ return nextMatchedChild != null;
+ }
+
+ @Override
+ public N next() {
+ if (!hasNext()) {
+ throw new NoSuchElementException();
+ }
+ N result = nextMatchedChild;
+ nextMatchedChild = null;
+ return result;
+ }
+
+ protected final void saveResult(N child, IStateMatchInfo stateMatchInfo) {
+ nextMatchedChild = child;
+ currentStateMatchInfo = stateMatchInfo;
+ }
+
+ protected abstract void getNext();
+ }
+
+ // 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;
+ transitionIterator = patternFA.getPreciseMatchTransitionIterator(sourceState);
+ }
+
+ @Override
+ protected void getNext() {
+ N child;
+ IFATransition transition;
+ while (transitionIterator.hasNext()) {
+ transition = transitionIterator.next();
+ child = getChild(parent, transition.getValue());
+ if (child == null) {
+ continue;
+ }
+ saveResult(
+ child,
+ new StateSingleMatchInfo(patternFA, patternFA.getNextState(sourceState, transition)));
+ return;
+ }
+ }
+ }
+
+ // only one fuzzy transition which may match batch children, need to iterate and check all
+ // children,
+ // there's no traceback
+ private class SingleFuzzyMatchChildrenIterator extends AbstractChildrenIterator {
+
+ private final IFAState sourceState;
+
+ private final IFATransition transition;
+
+ private final StateSingleMatchInfo stateMatchInfo;
+
+ private final Iterator<N> childrenIterator;
+
+ private SingleFuzzyMatchChildrenIterator(N parent, IFAState sourceState) {
+ this.sourceState = sourceState;
+ this.transition = patternFA.getFuzzyMatchTransitionIterator(sourceState).next();
+ this.stateMatchInfo =
+ new StateSingleMatchInfo(patternFA, patternFA.getNextState(sourceState, transition));
+ this.childrenIterator = getChildrenIterator(parent);
+ }
+
+ @Override
+ protected void getNext() {
+ N child;
+ while (childrenIterator.hasNext()) {
+ child = childrenIterator.next();
+ if (tryGetNextState(child, sourceState, transition) == null) {
+ continue;
+ }
+ saveResult(child, stateMatchInfo);
+ return;
+ }
+ }
+ }
+
+ // 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.
+ // the iterating process will try to get the first matched state of a child, and if there are some
+ // rest transitions, there may be traceback when checking the descendents
+ private class MultiMatchTransitionChildrenIterator extends AbstractChildrenIterator {
+
+ private final IFAState sourceState;
+
+ private final Map<String, IFATransition> preciseMatchTransitionMap;
+
+ private final Iterator<N> iterator;
+
+ private MultiMatchTransitionChildrenIterator(N parent, IFAState sourceState) {
+ this.sourceState = sourceState;
+ this.iterator = getChildrenIterator(parent);
+ this.preciseMatchTransitionMap = patternFA.getPreciseMatchTransition(sourceState);
+ }
+
+ @Override
+ protected void getNext() {
+ N child;
+
+ IFAState matchedState = null;
+ Iterator<IFATransition> transitionIterator;
+ IStateMatchInfo stateMatchInfo;
+ while (iterator.hasNext()) {
+ child = iterator.next();
+
+ if (!preciseMatchTransitionMap.isEmpty()) {
+ matchedState = tryGetNextState(child, sourceState, preciseMatchTransitionMap);
+ }
+
+ transitionIterator = patternFA.getFuzzyMatchTransitionIterator(sourceState);
+ if (matchedState == null) {
+ while (transitionIterator.hasNext()) {
+ matchedState = tryGetNextState(child, sourceState, transitionIterator.next());
+ if (matchedState != null) {
+ break;
+ }
+ }
+ if (matchedState == null) {
+ continue;
+ }
+ }
+
+ if (transitionIterator.hasNext()) {
+ stateMatchInfo = new StateMultiMatchInfo(patternFA, matchedState, transitionIterator);
+ firstAncestorOfTraceback = ancestorStack.size();
+ } else {
+ stateMatchInfo = new StateSingleMatchInfo(patternFA, matchedState);
+ }
+ saveResult(child, stateMatchInfo);
+ return;
+ }
}
+ }
+
+ // there may be traceback when try to find the matched state of node;
+ // the iterating process will try to get the first matched state of a child.
+ private class TraceBackChildrenIterator extends AbstractChildrenIterator {
+
+ private final Iterator<N> iterator;
+
+ private final IStateMatchInfo sourceStateMatchInfo;
- public N getNode() {
- return node;
+ TraceBackChildrenIterator(N parent, IStateMatchInfo sourceStateMatchInfo) {
+ this.sourceStateMatchInfo = sourceStateMatchInfo;
+ this.iterator = getChildrenIterator(parent);
}
- boolean hasBeenChecked(int index) {
- return matchStatus[matchedIndex - index] != 0;
+ @Override
+ protected void getNext() {
+ N child;
+
+ IFAState sourceState;
+
+ IStateMatchInfo stateMatchInfo;
+ Iterator<IFATransition> transitionIterator;
+
+ while (iterator.hasNext()) {
+
+ child = iterator.next();
+
+ stateMatchInfo = new StateMultiMatchInfo(patternFA);
+ for (int i = 0; i < sourceStateMatchInfo.getMatchedStateSize(); i++) {
+ sourceState = sourceStateMatchInfo.getMatchedState(i);
+ transitionIterator = tryGetNextMatchedState(child, sourceState, stateMatchInfo);
+ if (stateMatchInfo.getMatchedStateSize() > 0) {
+ stateMatchInfo.setSourceStateOrdinal(i);
+ stateMatchInfo.setSourceTransitionIterator(transitionIterator);
+ break;
+ }
+ }
+
+ if (stateMatchInfo.getMatchedStateSize() == 0) {
+ traceback(child, stateMatchInfo, sourceStateMatchInfo.getMatchedStateSize() - 1);
+ if (stateMatchInfo.getMatchedStateSize() == 0) {
+ continue;
+ }
+ }
+
+ saveResult(child, stateMatchInfo);
+ return;
+ }
}
- boolean isMatched(int index) {
- return matchStatus[matchedIndex - index] == 1;
+ /**
+ * Try to get next matched state from sourceState and add it into currentStateMatchInfo
+ *
+ * @param child child node to match
+ * @param sourceState source state
+ * @param currentStateMatchInfo currentStateMatchInfo
+ * @return iterator of rest transitions
+ */
+ private Iterator<IFATransition> tryGetNextMatchedState(
+ N child, IFAState sourceState, IStateMatchInfo currentStateMatchInfo) {
+ Map<String, IFATransition> preciseMatchTransitionMap =
+ patternFA.getPreciseMatchTransition(sourceState);
+
+ IFAState matchedState;
+ if (!preciseMatchTransitionMap.isEmpty()) {
+ matchedState = tryGetNextState(child, sourceState, preciseMatchTransitionMap);
+ if (matchedState != null) {
+ currentStateMatchInfo.addMatchedState(matchedState);
+ return patternFA.getFuzzyMatchTransitionIterator(sourceState);
+ }
+ }
+
+ Iterator<IFATransition> transitionIterator =
+ patternFA.getFuzzyMatchTransitionIterator(sourceState);
+ while (transitionIterator.hasNext()) {
+ matchedState = tryGetNextState(child, sourceState, transitionIterator.next());
+ if (matchedState != null) {
+ currentStateMatchInfo.addMatchedState(matchedState);
+ return transitionIterator;
+ }
+ }
+ return transitionIterator;
+ }
+
+ private void traceback(N node, IStateMatchInfo stateMatchInfo, int checkedSourceStateOrdinal) {
+ IStateMatchInfo parentStateMatchInfo;
+
+ N currentNode;
+ IStateMatchInfo currentStateMatchInfo;
+
+ int sourceStateOrdinal;
+ IFAState sourceState;
+ Iterator<IFATransition> transitionIterator = null;
+
+ int matchedStateSize;
+ IFAState matchedState;
+
+ int currentNodeIndex;
+ for (int i = ancestorStack.size() - 1; i >= firstAncestorOfTraceback; i--) {
+ parentStateMatchInfo = ancestorStack.get(i - 1).stateMatchInfo;
+ currentStateMatchInfo = ancestorStack.get(i).stateMatchInfo;
+
+ // there's no state not further searched
+ if (currentStateMatchInfo.getSourceStateOrdinal()
+ == parentStateMatchInfo.getMatchedStateSize()) {
+ continue;
+ }
+
+ // there's some state not further searched, process them in order
+ currentNodeIndex = i;
+ while (currentNodeIndex >= i) {
+ parentStateMatchInfo = ancestorStack.get(currentNodeIndex - 1).stateMatchInfo;
+
+ if (currentNodeIndex == ancestorStack.size()) {
+ currentNode = node;
+ currentStateMatchInfo = stateMatchInfo;
+ } else {
+ currentNode = ancestorStack.get(currentNodeIndex).node;
+ currentStateMatchInfo = ancestorStack.get(currentNodeIndex).stateMatchInfo;
+ }
+
+ matchedState = null;
+ if (currentNode == node) {
+ sourceStateOrdinal = checkedSourceStateOrdinal;
+ } else {
+ sourceStateOrdinal = currentStateMatchInfo.getSourceStateOrdinal();
+ if (sourceStateOrdinal == parentStateMatchInfo.getMatchedStateSize()) {
+ currentNodeIndex--;
+ continue;
+ }
+ // there may be some states could be matched from transition of current source state
+ sourceState = parentStateMatchInfo.getMatchedState(sourceStateOrdinal);
+ transitionIterator = currentStateMatchInfo.getSourceTransitionIterator();
+ while (transitionIterator.hasNext()) {
+ matchedState = tryGetNextState(currentNode, sourceState, transitionIterator.next());
+ if (matchedState != null) {
+ break;
+ }
+ }
+ }
+
+ if (matchedState == null) {
+ while (++sourceStateOrdinal < parentStateMatchInfo.getMatchedStateSize()) {
+ sourceState = parentStateMatchInfo.getMatchedState(sourceStateOrdinal);
+ matchedStateSize = currentStateMatchInfo.getMatchedStateSize();
+ transitionIterator =
+ tryGetNextMatchedState(currentNode, sourceState, currentStateMatchInfo);
+ // change of matchedStateSize means currentNode there is transition from sourceState
+ // matching currentNode
+ if (matchedStateSize != currentStateMatchInfo.getMatchedStateSize()) {
+ matchedState = currentStateMatchInfo.getMatchedState(matchedStateSize);
+ currentStateMatchInfo.setSourceStateOrdinal(sourceStateOrdinal);
+ currentStateMatchInfo.setSourceTransitionIterator(transitionIterator);
+ break;
+ }
+ }
+ if (matchedState == null) {
+ currentStateMatchInfo.setSourceStateOrdinal(sourceStateOrdinal - 1);
+ currentStateMatchInfo.setSourceTransitionIterator(transitionIterator);
+ currentNodeIndex--;
+ continue;
+ }
+ }
+
+ currentStateMatchInfo.addMatchedState(matchedState);
+
+ if (currentNode == node) {
+ return;
+ } else {
+ currentNodeIndex++;
+ }
+ }
+ }
}
+ }
- void setMatched(int index) {
- matchStatus[matchedIndex - index] = 1;
+ // the match process of FA graph is a dfs on FA Graph
+
+ // a tmp way to process alias of measurement node, which may results in multi event when checking
+ // the transition;
+ // fortunately, the measurement node only match the final state, which means there won't be any
+ // multi transition and traceback judge
+ protected IFAState tryGetNextState(
+ N node, IFAState sourceState, Map<String, IFATransition> preciseMatchTransitionMap) {
+ IFATransition transition = preciseMatchTransitionMap.get(node.getName());
+ if (transition == null) {
+ return null;
}
+ return patternFA.getNextState(sourceState, transition);
+ }
- void setNotMatched(int index) {
- matchStatus[matchedIndex - index] = -1;
+ // a tmp way to process alias of measurement node, which may results in multi event when checking
+ // the transition;
+ // fortunately, the measurement node only match the final state, which means there won't be any
+ // multi transition and traceback judge
+ protected IFAState tryGetNextState(N node, IFAState sourceState, IFATransition transition) {
+ if (transition.isMatch(node.getName())) {
+ return patternFA.getNextState(sourceState, transition);
+ } else {
+ return null;
}
}
}
diff --git a/server/src/main/java/org/apache/iotdb/db/mpp/common/schematree/visitor/SchemaTreeDeviceVisitor.java b/server/src/main/java/org/apache/iotdb/db/mpp/common/schematree/visitor/SchemaTreeDeviceVisitor.java
index 4f7ef159d0..792fc83273 100644
--- a/server/src/main/java/org/apache/iotdb/db/mpp/common/schematree/visitor/SchemaTreeDeviceVisitor.java
+++ b/server/src/main/java/org/apache/iotdb/db/mpp/common/schematree/visitor/SchemaTreeDeviceVisitor.java
@@ -50,7 +50,7 @@ public class SchemaTreeDeviceVisitor extends SchemaTreeVisitor<DeviceSchemaInfo>
@Override
protected DeviceSchemaInfo generateResult() {
- PartialPath path = new PartialPath(generateFullPathNodes(nextMatchedNode));
+ PartialPath path = new PartialPath(generateFullPathNodes());
List<MeasurementSchemaInfo> measurementSchemaInfoList = new ArrayList<>();
Iterator<SchemaNode> iterator = getChildrenIterator(nextMatchedNode);
SchemaNode node;
diff --git a/server/src/main/java/org/apache/iotdb/db/mpp/common/schematree/visitor/SchemaTreeMeasurementVisitor.java b/server/src/main/java/org/apache/iotdb/db/mpp/common/schematree/visitor/SchemaTreeMeasurementVisitor.java
index 38b03580a1..e524349231 100644
--- a/server/src/main/java/org/apache/iotdb/db/mpp/common/schematree/visitor/SchemaTreeMeasurementVisitor.java
+++ b/server/src/main/java/org/apache/iotdb/db/mpp/common/schematree/visitor/SchemaTreeMeasurementVisitor.java
@@ -21,37 +21,80 @@ package org.apache.iotdb.db.mpp.common.schematree.visitor;
import org.apache.iotdb.commons.path.MeasurementPath;
import org.apache.iotdb.commons.path.PartialPath;
-import org.apache.iotdb.db.mpp.common.schematree.node.SchemaMeasurementNode;
+import org.apache.iotdb.commons.path.fa.IFAState;
+import org.apache.iotdb.commons.path.fa.IFATransition;
import org.apache.iotdb.db.mpp.common.schematree.node.SchemaNode;
-import java.util.regex.Pattern;
+import java.util.Map;
public class SchemaTreeMeasurementVisitor extends SchemaTreeVisitor<MeasurementPath> {
+ private final String tailNode;
+
public SchemaTreeMeasurementVisitor(
SchemaNode root, PartialPath pathPattern, int slimit, int soffset, boolean isPrefixMatch) {
super(root, pathPattern, slimit, soffset, isPrefixMatch);
+ tailNode = pathPattern.getTailNode();
}
@Override
- protected boolean checkOneLevelWildcardMatch(String regex, SchemaNode node) {
- if (!node.isMeasurement()) {
- return Pattern.matches(regex, node.getName());
+ protected IFAState tryGetNextState(
+ SchemaNode node, IFAState sourceState, Map<String, IFATransition> preciseMatchTransitionMap) {
+ IFATransition transition;
+ IFAState state;
+ if (node.isMeasurement()) {
+ String alias = node.getAsMeasurementNode().getAlias();
+ if (alias != null) {
+ transition = preciseMatchTransitionMap.get(alias);
+ if (transition != null) {
+ state = patternFA.getNextState(sourceState, transition);
+ if (state.isFinal()) {
+ return state;
+ }
+ }
+ }
+ transition = preciseMatchTransitionMap.get(node.getName());
+ if (transition != null) {
+ state = patternFA.getNextState(sourceState, transition);
+ if (state.isFinal()) {
+ return state;
+ }
+ }
+ return null;
}
- SchemaMeasurementNode measurementNode = node.getAsMeasurementNode();
-
- return Pattern.matches(regex, measurementNode.getName())
- || Pattern.matches(regex, measurementNode.getAlias());
+ transition = preciseMatchTransitionMap.get(node.getName());
+ if (transition == null) {
+ return null;
+ }
+ return patternFA.getNextState(sourceState, transition);
}
@Override
- protected boolean checkNameMatch(String targetName, SchemaNode node) {
+ protected IFAState tryGetNextState(
+ SchemaNode node, IFAState sourceState, IFATransition transition) {
+ IFAState state;
if (node.isMeasurement()) {
- return targetName.equals(node.getName())
- || targetName.equals(node.getAsMeasurementNode().getAlias());
+ String alias = node.getAsMeasurementNode().getAlias();
+ if (alias != null && transition.isMatch(alias)) {
+ state = patternFA.getNextState(sourceState, transition);
+ if (state.isFinal()) {
+ return state;
+ }
+ }
+ if (transition.isMatch(node.getName())) {
+ state = patternFA.getNextState(sourceState, transition);
+ if (state.isFinal()) {
+ return state;
+ }
+ }
+ return null;
+ }
+
+ if (transition.isMatch(node.getName())) {
+ return patternFA.getNextState(sourceState, transition);
}
- return targetName.equals(node.getName());
+ return null;
}
@Override
@@ -72,12 +115,11 @@ public class SchemaTreeMeasurementVisitor extends SchemaTreeVisitor<MeasurementP
protected MeasurementPath generateResult() {
MeasurementPath result =
new MeasurementPath(
- generateFullPathNodes(nextMatchedNode),
- nextMatchedNode.getAsMeasurementNode().getSchema());
+ generateFullPathNodes(), nextMatchedNode.getAsMeasurementNode().getSchema());
result.setTagMap(nextMatchedNode.getAsMeasurementNode().getTagMap());
- result.setUnderAlignedEntity(ancestorStack.peek().getNode().getAsEntityNode().isAligned());
+ result.setUnderAlignedEntity(getParentOfNextMatchedNode().getAsEntityNode().isAligned());
String alias = nextMatchedNode.getAsMeasurementNode().getAlias();
- if (nodes[nodes.length - 1].equals(alias)) {
+ if (tailNode.equals(alias)) {
result.setMeasurementAlias(alias);
}
diff --git a/server/src/main/java/org/apache/iotdb/db/mpp/common/schematree/visitor/SchemaTreeVisitor.java b/server/src/main/java/org/apache/iotdb/db/mpp/common/schematree/visitor/SchemaTreeVisitor.java
index 848cacc213..4e497913e1 100644
--- a/server/src/main/java/org/apache/iotdb/db/mpp/common/schematree/visitor/SchemaTreeVisitor.java
+++ b/server/src/main/java/org/apache/iotdb/db/mpp/common/schematree/visitor/SchemaTreeVisitor.java
@@ -43,11 +43,6 @@ public abstract class SchemaTreeVisitor<R>
return result;
}
- @Override
- protected boolean isInternalNode(SchemaNode node) {
- return !node.isMeasurement();
- }
-
@Override
protected SchemaNode getChild(SchemaNode parent, String childName) {
return parent.getChild(childName);