Revert "[IOTDB-5168] Refactor traverse of AbstractTreeVisitor to FA-based traverse (#8400)" This reverts commit 8b4b397f9ebf17ba43c02f5d8dfeba7eebb29742.
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 a216340..0000000 --- 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 143c864..0000000 --- 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 cd5c114..0000000 --- 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 5eb3381..0000000 --- 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 4e050c1..0000000 --- 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 7a94ff8..0000000 --- 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 fbad7e7..0000000 --- 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 e3ccf7d..0000000 --- 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 efe829c..dfb0c7a 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 @@ // 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; + protected final Deque<VisitorStackEntry<N>> visitorStack = new ArrayDeque<>(); + protected final Deque<AncestorStackEntry<N>> ancestorStack = new ArrayDeque<>(); + protected boolean shouldVisitSubtree; - // cached result variables + // 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 @@ 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 @@ } node = iterator.next(); + patternIndex = stackEntry.patternIndex; + lastMultiLevelWildcardIndex = stackEntry.lastMultiLevelWildcardIndex; - if (currentStateMatchInfo.hasFinalState()) { - shouldVisitSubtree = processFullMatchedNode(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); + } + + continue; + } + + if (checkIsMatch(patternIndex, node)) { + if (patternIndex == nodes.length - 1) { + shouldVisitSubtree = processFullMatchedNode(node) && isInternalNode(node); + + if (nextMatchedNode != null) { + saveNextMatchedNodeContext(patternIndex, lastMultiLevelWildcardIndex); + return; + } + + if (shouldVisitSubtree) { + pushChildrenWhileTail(node, patternIndex, lastMultiLevelWildcardIndex); + } + } else { + shouldVisitSubtree = processInternalMatchedNode(node) && isInternalNode(node); + + if (nextMatchedNode != null) { + saveNextMatchedNodeContext(patternIndex, lastMultiLevelWildcardIndex); + return; + } + + if (shouldVisitSubtree) { + pushChildrenWhileInternal(node, patternIndex, lastMultiLevelWildcardIndex); + } + } } else { - shouldVisitSubtree = processInternalMatchedNode(node); - } + if (lastMultiLevelWildcardIndex == -1) { + continue; + } - if (shouldVisitSubtree) { - pushChildren(node); - } + int lastMatchIndex = findLastMatch(node, patternIndex, lastMultiLevelWildcardIndex); - if (nextMatchedNode != null) { - return; + shouldVisitSubtree = processInternalMatchedNode(node) && isInternalNode(node); + + if (nextMatchedNode != null) { + saveNextMatchedNodeContext(lastMatchIndex, lastMultiLevelWildcardIndex); + return; + } + + if (shouldVisitSubtree) { + pushChildrenWhileInternal(node, lastMatchIndex, lastMultiLevelWildcardIndex); + } } } } - private void pushChildren(N parent) { + /** + * The context, mainly the matching info, of nextedMatchedNode should be saved. When the + * nextedMatchedNode is consumed, the saved info will be used to process its subtree. + */ + private void saveNextMatchedNodeContext( + int patternIndexOfMatchedNode, int lastMultiLevelWildcardIndexOfMatchedNode) { + this.patternIndexOfMatchedNode = patternIndexOfMatchedNode; + this.lastMultiLevelWildcardIndexOfMatchedNode = lastMultiLevelWildcardIndexOfMatchedNode; + } + + /** + * When current node cannot match the pattern node in nodes[patternIndex] and there is ** before + * current pattern node, the pattern nodes before current pattern node should be checked. For + * example, given path root.sg.d.s and path pattern root.**.s. A status, root.sg.d not match + * root.**.s, may be reached during traversing process, then it should be checked and found that + * root.sg.d could match root.**, after which the process could continue and find root.sg.d.s + * matches root.**.s. + */ + private int findLastMatch(N node, int patternIndex, int lastMultiLevelWildcardIndex) { + for (int i = patternIndex - 1; i > lastMultiLevelWildcardIndex; i--) { + if (!checkIsMatch(i, node)) { + continue; + } + + 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(createChildrenIterator(parent), visitorStack.peek().level + 1)); - ancestorStack.add(new AncestorStackEntry(parent, currentStateMatchInfo)); - } - - private Iterator<N> createChildrenIterator(N parent) { - if (firstAncestorOfTraceback > -1) { - // there may be traceback when try to find the matched state of node - return new TraceBackChildrenIterator(parent, currentStateMatchInfo); - } else if (currentStateMatchInfo.hasOnlyPreciseMatchTransition()) { - // the child can be got directly with the precise value of transition - return new PreciseMatchChildrenIterator(parent, currentStateMatchInfo.getOneMatchedState()); - } else if (currentStateMatchInfo.hasNoPreciseMatchTransition() - && currentStateMatchInfo.isSingleFuzzyMatchTransition()) { - // only one transition which may match batch children, need to iterate and check all child - return new SingleFuzzyMatchChildrenIterator( - parent, currentStateMatchInfo.getOneMatchedState()); - } else { - // child may be matched by multi transitions, precise match or fuzzy match, - // which results in one child match multi state; need to iterate and check all child - return new MultiMatchTransitionChildrenIterator( - parent, currentStateMatchInfo.getOneMatchedState()); - } + new VisitorStackEntry<>(Collections.singletonList(root).iterator(), 0, 0, -1)); } private void popStack() { @@ -200,34 +311,151 @@ // 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(); + } + } + + /** + * 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); } } } - 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()); - } + /** + * 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)); } - nodeNames.add(nextMatchedNode.getName()); + } + + /** + * 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 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]); } - protected final N getParentOfNextMatchedNode() { - if (shouldVisitSubtree) { - return ancestorStack.get(ancestorStack.size() - 2).node; - } else { - return ancestorStack.get(ancestorStack.size() - 1).node; - } - } + /** + * 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 @@ /** 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; + this.matchedIndex = matchedIndex; + matchStatus = new byte[matchedIndex - lastMultiLevelWildcardIndex + 1]; + matchStatus[0] = 1; + matchStatus[matchStatus.length - 1] = 1; } - @Override - public N next() { - if (!hasNext()) { - throw new NoSuchElementException(); - } - N result = nextMatchedChild; - nextMatchedChild = null; - return result; + public N getNode() { + return node; } - protected final void saveResult(N child, IStateMatchInfo stateMatchInfo) { - nextMatchedChild = child; - currentStateMatchInfo = stateMatchInfo; + boolean hasBeenChecked(int index) { + return matchStatus[matchedIndex - index] != 0; } - 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); + boolean isMatched(int index) { + return matchStatus[matchedIndex - index] == 1; } - @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); + void setMatched(int index) { + matchStatus[matchedIndex - index] = 1; } - @Override - protected void getNext() { - N child; - while (childrenIterator.hasNext()) { - child = childrenIterator.next(); - if (tryGetNextState(child, sourceState, transition) == null) { - continue; - } - saveResult(child, stateMatchInfo); - return; - } - } - } - - // child may be matched by multi transitions, precise match or fuzzy match, - // which results in one child match multi state; need to iterate and check all child. - // the iterating process will try to get the first matched state of a child, and if there are some - // rest transitions, there may be traceback when checking the descendents - private class MultiMatchTransitionChildrenIterator extends AbstractChildrenIterator { - - private final IFAState sourceState; - - private final Map<String, IFATransition> preciseMatchTransitionMap; - - private final Iterator<N> iterator; - - private MultiMatchTransitionChildrenIterator(N parent, IFAState sourceState) { - this.sourceState = sourceState; - this.iterator = getChildrenIterator(parent); - this.preciseMatchTransitionMap = patternFA.getPreciseMatchTransition(sourceState); - } - - @Override - protected void getNext() { - N child; - - IFAState matchedState = null; - Iterator<IFATransition> transitionIterator; - IStateMatchInfo stateMatchInfo; - while (iterator.hasNext()) { - child = iterator.next(); - - if (!preciseMatchTransitionMap.isEmpty()) { - matchedState = tryGetNextState(child, sourceState, preciseMatchTransitionMap); - } - - transitionIterator = patternFA.getFuzzyMatchTransitionIterator(sourceState); - if (matchedState == null) { - while (transitionIterator.hasNext()) { - matchedState = tryGetNextState(child, sourceState, transitionIterator.next()); - if (matchedState != null) { - break; - } - } - if (matchedState == null) { - continue; - } - } - - if (transitionIterator.hasNext()) { - stateMatchInfo = new StateMultiMatchInfo(patternFA, matchedState, transitionIterator); - firstAncestorOfTraceback = ancestorStack.size(); - } else { - stateMatchInfo = new StateSingleMatchInfo(patternFA, matchedState); - } - saveResult(child, stateMatchInfo); - return; - } - } - } - - // there may be traceback when try to find the matched state of node; - // the iterating process will try to get the first matched state of a child. - private class TraceBackChildrenIterator extends AbstractChildrenIterator { - - private final Iterator<N> iterator; - - private final IStateMatchInfo sourceStateMatchInfo; - - TraceBackChildrenIterator(N parent, IStateMatchInfo sourceStateMatchInfo) { - this.sourceStateMatchInfo = sourceStateMatchInfo; - this.iterator = getChildrenIterator(parent); - } - - @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; - } - } - - /** - * 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++; - } - } - } - } - } - - // the match process of FA graph is a dfs on FA Graph - - // a tmp way to process alias of measurement node, which may results in multi event when checking - // the transition; - // fortunately, the measurement node only match the final state, which means there won't be any - // multi transition and traceback judge - protected IFAState tryGetNextState( - N node, IFAState sourceState, Map<String, IFATransition> preciseMatchTransitionMap) { - IFATransition transition = preciseMatchTransitionMap.get(node.getName()); - if (transition == null) { - return null; - } - return patternFA.getNextState(sourceState, transition); - } - - // 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 792fc83..4f7ef15 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 @@ @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 e524349..38b0358 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 @@ 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; + return targetName.equals(node.getName()) + || targetName.equals(node.getAsMeasurementNode().getAlias()); } - - if (transition.isMatch(node.getName())) { - return patternFA.getNextState(sourceState, transition); - } - return null; + return targetName.equals(node.getName()); } @Override @@ -115,11 +72,12 @@ 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 4e49791..848cacc 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
@@ -44,6 +44,11 @@ } @Override + protected boolean isInternalNode(SchemaNode node) { + return !node.isMeasurement(); + } + + @Override protected SchemaNode getChild(SchemaNode parent, String childName) { return parent.getChild(childName); }