You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@iotdb.apache.org by xi...@apache.org on 2022/12/28 06:31:55 UTC
[iotdb] 01/01: Revert "[IOTDB-5168] Refactor traverse of AbstractTreeVisitor to FA-based traverse (#8400)"
This is an automated email from the ASF dual-hosted git repository.
xingtanzjr pushed a commit to branch test_write_1228
in repository https://gitbox.apache.org/repos/asf/iotdb.git
commit 146b2cdd82b0dbeabe43db88ba09e6ea7c7e5915
Author: Jinrui.Zhang <xi...@gmail.com>
AuthorDate: Wed Dec 28 14:31:17 2022 +0800
Revert "[IOTDB-5168] Refactor traverse of AbstractTreeVisitor to FA-based traverse (#8400)"
This reverts commit 8b4b397f9ebf17ba43c02f5d8dfeba7eebb29742.
---
.../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, 374 insertions(+), 1547 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
deleted file mode 100644
index a21634086b..0000000000
--- a/node-commons/src/main/java/org/apache/iotdb/commons/path/fa/IFAState.java
+++ /dev/null
@@ -1,33 +0,0 @@
-/*
- * 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
deleted file mode 100644
index 143c864ec6..0000000000
--- a/node-commons/src/main/java/org/apache/iotdb/commons/path/fa/IFATransition.java
+++ /dev/null
@@ -1,34 +0,0 @@
-/*
- * 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
deleted file mode 100644
index cd5c114ab7..0000000000
--- a/node-commons/src/main/java/org/apache/iotdb/commons/path/fa/IPatternFA.java
+++ /dev/null
@@ -1,75 +0,0 @@
-/*
- * 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
deleted file mode 100644
index 5eb3381101..0000000000
--- a/node-commons/src/main/java/org/apache/iotdb/commons/path/fa/SimpleNFA.java
+++ /dev/null
@@ -1,522 +0,0 @@
-/*
- * 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
deleted file mode 100644
index 4e050c1d7e..0000000000
--- a/node-commons/src/main/java/org/apache/iotdb/commons/path/fa/match/IStateMatchInfo.java
+++ /dev/null
@@ -1,79 +0,0 @@
-/*
- * 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
deleted file mode 100644
index 7a94ff8c67..0000000000
--- a/node-commons/src/main/java/org/apache/iotdb/commons/path/fa/match/MatchedStateSet.java
+++ /dev/null
@@ -1,68 +0,0 @@
-/*
- * 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
deleted file mode 100644
index fbad7e70a4..0000000000
--- a/node-commons/src/main/java/org/apache/iotdb/commons/path/fa/match/StateMultiMatchInfo.java
+++ /dev/null
@@ -1,120 +0,0 @@
-/*
- * 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
deleted file mode 100644
index e3ccf7df61..0000000000
--- a/node-commons/src/main/java/org/apache/iotdb/commons/path/fa/match/StateSingleMatchInfo.java
+++ /dev/null
@@ -1,103 +0,0 @@
-/*
- * 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 efe829cec1..dfb0c7acfe 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,21 +20,18 @@
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
@@ -66,57 +63,47 @@ public abstract class AbstractTreeVisitor<N extends ITreeNode, R> implements Ite
// command parameters
protected final N root;
-
- // finite automation constructed from given path pattern or pattern tree
- protected final IPatternFA patternFA;
+ protected final String[] nodes;
+ protected final boolean isPrefixMatch;
// 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 final Deque<VisitorStackEntry<N>> visitorStack = new ArrayDeque<>();
+ protected final Deque<AncestorStackEntry<N>> ancestorStack = new ArrayDeque<>();
+ protected boolean shouldVisitSubtree;
+
+ // 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;
- this.patternFA = new SimpleNFA(pathPattern, isPrefixMatch);
-
- initStack();
+ visitorStack.push(
+ new VisitorStackEntry<>(Collections.singletonList(root).iterator(), 0, 0, -1));
}
- 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;
+ /**
+ * 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);
+ }
}
- IFAState rootState = patternFA.getNextState(initialState, transition);
- currentStateMatchInfo = new StateSingleMatchInfo(patternFA, rootState);
- visitorStack.push(new VisitorStackEntry(createChildrenIterator(root), 1));
- ancestorStack.add(new AncestorStackEntry(root, currentStateMatchInfo));
- }
- public void reset() {
- visitorStack.clear();
- ancestorStack.clear();
- nextMatchedNode = null;
- firstAncestorOfTraceback = -1;
- initStack();
+ return optimizedNodes.toArray(new String[0]);
}
@Override
@@ -132,16 +119,52 @@ 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 stackEntry;
+ VisitorStackEntry<N> stackEntry;
+ int patternIndex;
N node;
Iterator<N> iterator;
+ int lastMultiLevelWildcardIndex;
while (!visitorStack.isEmpty()) {
stackEntry = visitorStack.peek();
iterator = stackEntry.iterator;
@@ -152,47 +175,135 @@ public abstract class AbstractTreeVisitor<N extends ITreeNode, R> implements Ite
}
node = iterator.next();
+ patternIndex = stackEntry.patternIndex;
+ lastMultiLevelWildcardIndex = stackEntry.lastMultiLevelWildcardIndex;
- if (currentStateMatchInfo.hasFinalState()) {
- shouldVisitSubtree = processFullMatchedNode(node);
- } else {
- shouldVisitSubtree = processInternalMatchedNode(node);
- }
+ // only prefixMatch
+ if (patternIndex == nodes.length) {
+
+ shouldVisitSubtree = processFullMatchedNode(node) && isInternalNode(node);
+
+ if (nextMatchedNode != null) {
+ saveNextMatchedNodeContext(patternIndex, lastMultiLevelWildcardIndex);
+ return;
+ }
+
+ if (shouldVisitSubtree) {
+ pushChildrenWhilePrefixMatch(node, patternIndex, lastMultiLevelWildcardIndex);
+ }
- if (shouldVisitSubtree) {
- pushChildren(node);
+ continue;
}
- if (nextMatchedNode != null) {
- return;
+ 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);
+ }
+ }
+ } 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);
+ }
}
}
}
- private void pushChildren(N parent) {
- visitorStack.push(
- new VisitorStackEntry(createChildrenIterator(parent), visitorStack.peek().level + 1));
- ancestorStack.add(new AncestorStackEntry(parent, currentStateMatchInfo));
+ /**
+ * 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;
}
- 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());
+ /**
+ * 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;
+ }
+
+ 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;
+ }
}
+ return lastMultiLevelWildcardIndex;
+ }
+
+ public void reset() {
+ visitorStack.clear();
+ ancestorStack.clear();
+ nextMatchedNode = null;
+ visitorStack.push(
+ new VisitorStackEntry<>(Collections.singletonList(root).iterator(), 0, 0, -1));
}
private void popStack() {
@@ -200,35 +311,152 @@ 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.remove(ancestorStack.size() - 1);
- if (ancestorStack.size() <= firstAncestorOfTraceback) {
- firstAncestorOfTraceback = -1;
- }
+ ancestorStack.pop();
}
}
- 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());
+ /**
+ * 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);
}
}
- nodeNames.add(nextMatchedNode.getName());
- return nodeNames.toArray(new String[0]);
}
- protected final N getParentOfNextMatchedNode() {
- if (shouldVisitSubtree) {
- return ancestorStack.get(ancestorStack.size() - 2).node;
+ /**
+ * 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));
+ }
+ }
+
+ /**
+ * 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);
} else {
- return ancestorStack.get(ancestorStack.size() - 1).node;
+ return checkNameMatch(nodes[patternIndex], 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);
@@ -259,384 +487,54 @@ 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();
- private class VisitorStackEntry {
+ protected static class VisitorStackEntry<N> {
- // children iterator
private final Iterator<N> iterator;
-
- // level of children taken from iterator
+ private final int patternIndex;
private final int level;
+ private final int lastMultiLevelWildcardIndex;
- VisitorStackEntry(Iterator<N> iterator, int level) {
+ VisitorStackEntry(
+ Iterator<N> iterator, int patternIndex, int level, int lastMultiLevelWildcardIndex) {
this.iterator = iterator;
+ this.patternIndex = patternIndex;
this.level = level;
+ this.lastMultiLevelWildcardIndex = lastMultiLevelWildcardIndex;
}
}
- private class AncestorStackEntry {
+ protected static class AncestorStackEntry<N> {
private final N node;
+ private final int matchedIndex;
+ /** Record the check result to reduce repeating check. */
+ private final byte[] matchStatus;
- private final IStateMatchInfo stateMatchInfo;
-
- AncestorStackEntry(N node, IStateMatchInfo stateMatchInfo) {
+ AncestorStackEntry(N node, int matchedIndex, int lastMultiLevelWildcardIndex) {
this.node = node;
- 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;
- }
+ this.matchedIndex = matchedIndex;
+ matchStatus = new byte[matchedIndex - lastMultiLevelWildcardIndex + 1];
+ matchStatus[0] = 1;
+ matchStatus[matchStatus.length - 1] = 1;
}
- }
-
- // 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;
- TraceBackChildrenIterator(N parent, IStateMatchInfo sourceStateMatchInfo) {
- this.sourceStateMatchInfo = sourceStateMatchInfo;
- this.iterator = getChildrenIterator(parent);
+ public N getNode() {
+ return node;
}
- @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 hasBeenChecked(int index) {
+ return matchStatus[matchedIndex - index] != 0;
}
- /**
- * 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++;
- }
- }
- }
+ boolean isMatched(int index) {
+ return 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;
+ void setMatched(int index) {
+ matchStatus[matchedIndex - index] = 1;
}
- return patternFA.getNextState(sourceState, transition);
- }
- // 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;
+ void setNotMatched(int index) {
+ matchStatus[matchedIndex - index] = -1;
}
}
}
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 792fc83273..4f7ef159d0 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());
+ PartialPath path = new PartialPath(generateFullPathNodes(nextMatchedNode));
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 e524349231..38b03580a1 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,80 +21,37 @@ 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.commons.path.fa.IFAState;
-import org.apache.iotdb.commons.path.fa.IFATransition;
+import org.apache.iotdb.db.mpp.common.schematree.node.SchemaMeasurementNode;
import org.apache.iotdb.db.mpp.common.schematree.node.SchemaNode;
-import java.util.Map;
+import java.util.regex.Pattern;
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 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;
+ protected boolean checkOneLevelWildcardMatch(String regex, SchemaNode node) {
+ if (!node.isMeasurement()) {
+ return Pattern.matches(regex, node.getName());
}
- transition = preciseMatchTransitionMap.get(node.getName());
- if (transition == null) {
- return null;
- }
- return patternFA.getNextState(sourceState, transition);
+ SchemaMeasurementNode measurementNode = node.getAsMeasurementNode();
+
+ return Pattern.matches(regex, measurementNode.getName())
+ || Pattern.matches(regex, measurementNode.getAlias());
}
@Override
- protected IFAState tryGetNextState(
- SchemaNode node, IFAState sourceState, IFATransition transition) {
- IFAState state;
+ protected boolean checkNameMatch(String targetName, SchemaNode node) {
if (node.isMeasurement()) {
- 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())
+ || targetName.equals(node.getAsMeasurementNode().getAlias());
}
- return null;
+ return targetName.equals(node.getName());
}
@Override
@@ -115,11 +72,12 @@ public class SchemaTreeMeasurementVisitor extends SchemaTreeVisitor<MeasurementP
protected MeasurementPath generateResult() {
MeasurementPath result =
new MeasurementPath(
- generateFullPathNodes(), nextMatchedNode.getAsMeasurementNode().getSchema());
+ generateFullPathNodes(nextMatchedNode),
+ nextMatchedNode.getAsMeasurementNode().getSchema());
result.setTagMap(nextMatchedNode.getAsMeasurementNode().getTagMap());
- result.setUnderAlignedEntity(getParentOfNextMatchedNode().getAsEntityNode().isAligned());
+ result.setUnderAlignedEntity(ancestorStack.peek().getNode().getAsEntityNode().isAligned());
String alias = nextMatchedNode.getAsMeasurementNode().getAlias();
- if (tailNode.equals(alias)) {
+ if (nodes[nodes.length - 1].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 4e497913e1..848cacc213 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,6 +43,11 @@ 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);