#9917

Committed 24 Aug 2023 04:16PM UTC coverage: 47.861% (+0.009%) from 47.852%

Build # #9917

Build Type

push

travis_ci

Committed by

web-flow

Commit Message

Feature/streamlined grafana plugin profile (#10907)

Run Details

80245 of 167662 relevant lines covered (47.86%)

0.48 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

96.3

/iotdb-core/node-commons/src/main/java/org/apache/iotdb/commons/path/fa/dfa/PatternDFA.java

/*
 * 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.dfa;

import org.apache.iotdb.commons.conf.IoTDBConstant;
import org.apache.iotdb.commons.path.PartialPath;
import org.apache.iotdb.commons.path.PathPatternTree;
import org.apache.iotdb.commons.path.fa.IFAState;
import org.apache.iotdb.commons.path.fa.IFATransition;
import org.apache.iotdb.commons.path.fa.IPatternFA;
import org.apache.iotdb.commons.path.fa.dfa.graph.DFAGraph;
import org.apache.iotdb.commons.path.fa.dfa.graph.NFAGraph;
import org.apache.iotdb.commons.path.fa.dfa.transition.DFAPreciseTransition;
import org.apache.iotdb.commons.path.fa.dfa.transition.DFAWildcardTransition;
import org.apache.iotdb.commons.utils.TestOnly;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.concurrent.atomic.AtomicInteger;

public class PatternDFA implements IPatternFA {

  private final List<IFATransition> preciseMatchTransitionList = new ArrayList<>();
  private final List<IFATransition> batchMatchTransitionList = new ArrayList<>();
  // Map<AcceptEvent, IFATransition>
  private final Map<String, IFATransition> transitionMap = new HashMap<>();
  private final DFAGraph dfaGraph;

  // cached
  private final Map<String, IFATransition>[] preciseMatchTransitionCached;
  private final List<IFATransition>[] batchMatchTransitionCached;

  public PatternDFA(PartialPath pathPattern, boolean isPrefix) {
    // 1. build transition
    boolean wildcard = false;
    AtomicInteger transitionIndex = new AtomicInteger();
    for (String node : pathPattern.getNodes()) {
      if (IoTDBConstant.ONE_LEVEL_PATH_WILDCARD.equals(node)
          || IoTDBConstant.MULTI_LEVEL_PATH_WILDCARD.equals(node)) {
        wildcard = true;
      } else {
        transitionMap.computeIfAbsent(
            node,
            i -> {
              IFATransition transition =
                  new DFAPreciseTransition(transitionIndex.getAndIncrement(), node);
              preciseMatchTransitionList.add(transition);
              return transition;
            });
      }
    }
    if (wildcard || isPrefix) {
      IFATransition transition =
          new DFAWildcardTransition(
              transitionIndex.getAndIncrement(), new ArrayList<>(transitionMap.keySet()));
      transitionMap.put(transition.getAcceptEvent(), transition);
      batchMatchTransitionList.add(transition);
    }

    // 2. build NFA
    NFAGraph nfaGraph = new NFAGraph(pathPattern, isPrefix, transitionMap);

    // 3. NFA to DFA
    dfaGraph = new DFAGraph(nfaGraph, transitionMap.values());
    preciseMatchTransitionCached = new HashMap[dfaGraph.getStateSize()];
    batchMatchTransitionCached = new List[dfaGraph.getStateSize()];
  }

  /**
   * Construct PatternDFA for given path pattern. Only used for authentication now.
   *
   * @param prefixOrFullPatternTree the included PartialPath must be a prefix or a fullPath
   */
  public PatternDFA(PathPatternTree prefixOrFullPatternTree) {
    // 1. build transition
    boolean wildcard = false;
    AtomicInteger transitionIndex = new AtomicInteger();
    for (PartialPath pathPattern : prefixOrFullPatternTree.getAllPathPatterns()) {
      for (String node : pathPattern.getNodes()) {
        if (IoTDBConstant.ONE_LEVEL_PATH_WILDCARD.equals(node)
            || IoTDBConstant.MULTI_LEVEL_PATH_WILDCARD.equals(node)) {
          wildcard = true;
        } else {
          transitionMap.computeIfAbsent(
              node,
              i -> {
                IFATransition transition =
                    new DFAPreciseTransition(transitionIndex.getAndIncrement(), node);
                preciseMatchTransitionList.add(transition);
                return transition;
              });
        }
      }
    }
    if (wildcard) {
      IFATransition transition =
          new DFAWildcardTransition(
              transitionIndex.getAndIncrement(), new ArrayList<>(transitionMap.keySet()));
      transitionMap.put(transition.getAcceptEvent(), transition);
      batchMatchTransitionList.add(transition);
    }

    // 2. build NFA
    NFAGraph nfaGraph = new NFAGraph(prefixOrFullPatternTree, transitionMap);

    // 3. NFA to DFA
    dfaGraph = new DFAGraph(nfaGraph, transitionMap.values());
    preciseMatchTransitionCached = new HashMap[dfaGraph.getStateSize()];
    batchMatchTransitionCached = new List[dfaGraph.getStateSize()];
  }

  public IFAState getNextState(IFAState currentState, String acceptEvent) {
    if (transitionMap.containsKey(acceptEvent)) {
      return dfaGraph.getNextState(currentState, transitionMap.get(acceptEvent));
    } else {
      Iterator<IFATransition> fuzzyMatchTransitionIterator =
          getFuzzyMatchTransitionIterator(currentState);
      while (fuzzyMatchTransitionIterator.hasNext()) {
        IFATransition transition = fuzzyMatchTransitionIterator.next();
        if (transition.isMatch(acceptEvent)) {
          return dfaGraph.getNextState(currentState, transition);
        }
      }
    }
    return null;
  }

  @Override
  public Map<String, IFATransition> getPreciseMatchTransition(IFAState state) {
    if (preciseMatchTransitionCached[state.getIndex()] == null) {
      preciseMatchTransitionCached[state.getIndex()] =
          dfaGraph.getPreciseMatchTransition(state, preciseMatchTransitionList);
    }
    return preciseMatchTransitionCached[state.getIndex()];
  }

  @Override
  public Iterator<IFATransition> getPreciseMatchTransitionIterator(IFAState state) {
    if (preciseMatchTransitionCached[state.getIndex()] == null) {
      preciseMatchTransitionCached[state.getIndex()] =
          dfaGraph.getPreciseMatchTransition(state, preciseMatchTransitionList);
    }
    return preciseMatchTransitionCached[state.getIndex()].values().iterator();
  }

  @Override
  public Iterator<IFATransition> getFuzzyMatchTransitionIterator(IFAState state) {
    if (batchMatchTransitionCached[state.getIndex()] == null) {
      batchMatchTransitionCached[state.getIndex()] =
          dfaGraph.getTransition(state, batchMatchTransitionList);
    }
    return batchMatchTransitionCached[state.getIndex()].iterator();
  }

  @Override
  public int getFuzzyMatchTransitionSize(IFAState state) {
    if (batchMatchTransitionCached[state.getIndex()] == null) {
      batchMatchTransitionCached[state.getIndex()] =
          dfaGraph.getTransition(state, batchMatchTransitionList);
    }
    return batchMatchTransitionCached[state.getIndex()].size();
  }

  @Override
  public IFAState getNextState(IFAState currentState, IFATransition transition) {
    return dfaGraph.getNextState(currentState, transition);
  }

  @Override
  public IFAState getInitialState() {
    return dfaGraph.getInitialState();
  }

  @Override
  public int getStateSize() {
    return dfaGraph.getStateSize();
  }

  @Override
  public IFAState getState(int index) {
    return dfaGraph.getState(index);
  }

  @Override
  public boolean mayTransitionOverlap() {
    return false;
  }

  @TestOnly
  public List<IFATransition> getTransition(IFAState state) {
    return dfaGraph.getTransition(state, transitionMap.values());
  }
}

1	/*
2	* Licensed to the Apache Software Foundation (ASF) under one
3	* or more contributor license agreements. See the NOTICE file
4	* distributed with this work for additional information
5	* regarding copyright ownership. The ASF licenses this file
6	* to you under the Apache License, Version 2.0 (the
7	* "License"); you may not use this file except in compliance
8	* with the License. You may obtain a copy of the License at
9	*
10	* http://www.apache.org/licenses/LICENSE-2.0
11	*
12	* Unless required by applicable law or agreed to in writing,
13	* software distributed under the License is distributed on an
14	* "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
15	* KIND, either express or implied. See the License for the
16	* specific language governing permissions and limitations
17	* under the License.
18	*/
19	package org.apache.iotdb.commons.path.fa.dfa;
20
21	import org.apache.iotdb.commons.conf.IoTDBConstant;
22	import org.apache.iotdb.commons.path.PartialPath;
23	import org.apache.iotdb.commons.path.PathPatternTree;
24	import org.apache.iotdb.commons.path.fa.IFAState;
25	import org.apache.iotdb.commons.path.fa.IFATransition;
26	import org.apache.iotdb.commons.path.fa.IPatternFA;
27	import org.apache.iotdb.commons.path.fa.dfa.graph.DFAGraph;
28	import org.apache.iotdb.commons.path.fa.dfa.graph.NFAGraph;
29	import org.apache.iotdb.commons.path.fa.dfa.transition.DFAPreciseTransition;
30	import org.apache.iotdb.commons.path.fa.dfa.transition.DFAWildcardTransition;
31	import org.apache.iotdb.commons.utils.TestOnly;
32
33	import java.util.ArrayList;
34	import java.util.HashMap;
35	import java.util.Iterator;
36	import java.util.List;
37	import java.util.Map;
38	import java.util.concurrent.atomic.AtomicInteger;
39
40	public class PatternDFA implements IPatternFA {
41
42	private final List<IFATransition> preciseMatchTransitionList = new ArrayList<>();	1✔
43	private final List<IFATransition> batchMatchTransitionList = new ArrayList<>();	1✔
44	// Map<AcceptEvent, IFATransition>
45	private final Map<String, IFATransition> transitionMap = new HashMap<>();	1✔
46	private final DFAGraph dfaGraph;
47
48	// cached
49	private final Map<String, IFATransition>[] preciseMatchTransitionCached;
50	private final List<IFATransition>[] batchMatchTransitionCached;
51
52	public PatternDFA(PartialPath pathPattern, boolean isPrefix) {	1✔
53	// 1. build transition
54	boolean wildcard = false;	1✔
55	AtomicInteger transitionIndex = new AtomicInteger();	1✔
56	for (String node : pathPattern.getNodes()) {	1✔
57	if (IoTDBConstant.ONE_LEVEL_PATH_WILDCARD.equals(node)	1✔
58	\|\| IoTDBConstant.MULTI_LEVEL_PATH_WILDCARD.equals(node)) {	1✔
59	wildcard = true;	1✔
60	} else {
61	transitionMap.computeIfAbsent(	1✔
62	node,
63	i -> {
64	IFATransition transition =	1✔
65	new DFAPreciseTransition(transitionIndex.getAndIncrement(), node);	1✔
66	preciseMatchTransitionList.add(transition);	1✔
67	return transition;	1✔
68	});
69	}
70	}
71	if (wildcard \|\| isPrefix) {	1✔
72	IFATransition transition =	1✔
73	new DFAWildcardTransition(
74	transitionIndex.getAndIncrement(), new ArrayList<>(transitionMap.keySet()));	1✔
75	transitionMap.put(transition.getAcceptEvent(), transition);	1✔
76	batchMatchTransitionList.add(transition);	1✔
77	}
78
79	// 2. build NFA
80	NFAGraph nfaGraph = new NFAGraph(pathPattern, isPrefix, transitionMap);	1✔
81
82	// 3. NFA to DFA
83	dfaGraph = new DFAGraph(nfaGraph, transitionMap.values());	1✔
84	preciseMatchTransitionCached = new HashMap[dfaGraph.getStateSize()];	1✔
85	batchMatchTransitionCached = new List[dfaGraph.getStateSize()];	1✔
86	}	1✔
87
88	/**
89	* Construct PatternDFA for given path pattern. Only used for authentication now.
90	*
91	* @param prefixOrFullPatternTree the included PartialPath must be a prefix or a fullPath
92	*/
93	public PatternDFA(PathPatternTree prefixOrFullPatternTree) {	1✔
94	// 1. build transition
95	boolean wildcard = false;	1✔
96	AtomicInteger transitionIndex = new AtomicInteger();	1✔
97	for (PartialPath pathPattern : prefixOrFullPatternTree.getAllPathPatterns()) {	1✔
98	for (String node : pathPattern.getNodes()) {	1✔
99	if (IoTDBConstant.ONE_LEVEL_PATH_WILDCARD.equals(node)	1✔
100	\|\| IoTDBConstant.MULTI_LEVEL_PATH_WILDCARD.equals(node)) {	1✔
101	wildcard = true;	1✔
102	} else {
103	transitionMap.computeIfAbsent(	1✔
104	node,
105	i -> {
106	IFATransition transition =	1✔
107	new DFAPreciseTransition(transitionIndex.getAndIncrement(), node);	1✔
108	preciseMatchTransitionList.add(transition);	1✔
109	return transition;	1✔
110	});
111	}
112	}
113	}	1✔
114	if (wildcard) {	1✔
115	IFATransition transition =	1✔
116	new DFAWildcardTransition(
117	transitionIndex.getAndIncrement(), new ArrayList<>(transitionMap.keySet()));	1✔
118	transitionMap.put(transition.getAcceptEvent(), transition);	1✔
119	batchMatchTransitionList.add(transition);	1✔
120	}
121
122	// 2. build NFA
123	NFAGraph nfaGraph = new NFAGraph(prefixOrFullPatternTree, transitionMap);	1✔
124
125	// 3. NFA to DFA
126	dfaGraph = new DFAGraph(nfaGraph, transitionMap.values());	1✔
127	preciseMatchTransitionCached = new HashMap[dfaGraph.getStateSize()];	1✔
128	batchMatchTransitionCached = new List[dfaGraph.getStateSize()];	1✔
129	}	1✔
130
131	public IFAState getNextState(IFAState currentState, String acceptEvent) {
132	if (transitionMap.containsKey(acceptEvent)) {	1✔
133	return dfaGraph.getNextState(currentState, transitionMap.get(acceptEvent));	1✔
134	} else {
135	Iterator<IFATransition> fuzzyMatchTransitionIterator =	1✔
136	getFuzzyMatchTransitionIterator(currentState);	1✔
137	while (fuzzyMatchTransitionIterator.hasNext()) {	1✔
138	IFATransition transition = fuzzyMatchTransitionIterator.next();	1✔
139	if (transition.isMatch(acceptEvent)) {	1✔
140	return dfaGraph.getNextState(currentState, transition);	1✔
141	}
142	}	×
143	}
144	return null;	1✔
145	}
146
147	@Override
148	public Map<String, IFATransition> getPreciseMatchTransition(IFAState state) {
149	if (preciseMatchTransitionCached[state.getIndex()] == null) {	1✔
150	preciseMatchTransitionCached[state.getIndex()] =	1✔
151	dfaGraph.getPreciseMatchTransition(state, preciseMatchTransitionList);	1✔
152	}
153	return preciseMatchTransitionCached[state.getIndex()];	1✔
154	}
155
156	@Override
157	public Iterator<IFATransition> getPreciseMatchTransitionIterator(IFAState state) {
158	if (preciseMatchTransitionCached[state.getIndex()] == null) {	1✔
159	preciseMatchTransitionCached[state.getIndex()] =	1✔
160	dfaGraph.getPreciseMatchTransition(state, preciseMatchTransitionList);	1✔
161	}
162	return preciseMatchTransitionCached[state.getIndex()].values().iterator();	1✔
163	}
164
165	@Override
166	public Iterator<IFATransition> getFuzzyMatchTransitionIterator(IFAState state) {
167	if (batchMatchTransitionCached[state.getIndex()] == null) {	1✔
168	batchMatchTransitionCached[state.getIndex()] =	1✔
169	dfaGraph.getTransition(state, batchMatchTransitionList);	1✔
170	}
171	return batchMatchTransitionCached[state.getIndex()].iterator();	1✔
172	}
173
174	@Override
175	public int getFuzzyMatchTransitionSize(IFAState state) {
176	if (batchMatchTransitionCached[state.getIndex()] == null) {	1✔
177	batchMatchTransitionCached[state.getIndex()] =	1✔
178	dfaGraph.getTransition(state, batchMatchTransitionList);	1✔
179	}
180	return batchMatchTransitionCached[state.getIndex()].size();	1✔
181	}
182
183	@Override
184	public IFAState getNextState(IFAState currentState, IFATransition transition) {
185	return dfaGraph.getNextState(currentState, transition);	1✔
186	}
187
188	@Override
189	public IFAState getInitialState() {
190	return dfaGraph.getInitialState();	1✔
191	}
192
193	@Override
194	public int getStateSize() {
195	return dfaGraph.getStateSize();	×
196	}
197
198	@Override
199	public IFAState getState(int index) {
200	return dfaGraph.getState(index);	×
201	}
202
203	@Override
204	public boolean mayTransitionOverlap() {
205	return false;	1✔
206	}
207
208	@TestOnly
209	public List<IFATransition> getTransition(IFAState state) {
210	return dfaGraph.getTransition(state, transitionMap.values());	1✔
211	}
212	}

apache / iotdb / #9917

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous