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:54 UTC
[iotdb] branch test_write_1228 created (now 146b2cdd82)
This is an automated email from the ASF dual-hosted git repository.
xingtanzjr pushed a change to branch test_write_1228
in repository https://gitbox.apache.org/repos/asf/iotdb.git
at 146b2cdd82 Revert "[IOTDB-5168] Refactor traverse of AbstractTreeVisitor to FA-based traverse (#8400)"
This branch includes the following new commits:
new 146b2cdd82 Revert "[IOTDB-5168] Refactor traverse of AbstractTreeVisitor to FA-based traverse (#8400)"
The 1 revisions listed above as "new" are entirely new to this
repository and will be described in separate emails. The revisions
listed as "add" were already present in the repository and have only
been added to this reference.
[iotdb] 01/01: Revert "[IOTDB-5168] Refactor traverse of AbstractTreeVisitor to FA-based traverse (#8400)"
Posted by xi...@apache.org.
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);