#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

68.89

/iotdb-core/node-commons/src/main/java/org/apache/iotdb/commons/path/fa/dfa/graph/NFAGraph.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.graph;

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.dfa.DFAState;
import org.apache.iotdb.commons.utils.TestOnly;

import org.apache.commons.lang3.StringUtils;

import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.stream.Collectors;

/**
 * NFA graph for given path pattern. State 0 is initial state. Run PatternDFATest#printFASketch for
 * more detail.
 */
public class NFAGraph {
  private final List<IFAState> nfaStateList = new ArrayList<>();

  // [transitionIndex][stateIndex]List<IFAState>
  private final List<IFAState>[][] nfaTransitionTable;

  /**
   * Construct NFA graph for given path pattern.
   *
   * @param pathPattern matched path pattern
   * @param isPrefix prefix match mode, matched pattern will be pathPattern.** if isPrefix is true
   * @param transitionMap transitionMap
   */
  public NFAGraph(
      PartialPath pathPattern, boolean isPrefix, Map<String, IFATransition> transitionMap) {
    nfaTransitionTable = new List[transitionMap.size()][pathPattern.getNodeLength() + 1];
    // init start state, curNodeIndex=0
    int curStateIndex = 0;
    nfaStateList.add(new DFAState(curStateIndex));
    for (int i = 0; i < transitionMap.size(); i++) {
      nfaTransitionTable[i][0] = new ArrayList<>();
    }
    // traverse pathPattern and construct NFA
    for (int i = 0; i < pathPattern.getNodeLength(); i++) {
      String node = pathPattern.getNodes()[i];
      // if it is tail node, transit to final state
      DFAState state =
          i == pathPattern.getNodeLength() - 1
              ? new DFAState(++curStateIndex, true)
              : new DFAState(++curStateIndex);
      nfaStateList.add(state);
      for (int j = 0; j < transitionMap.size(); j++) {
        nfaTransitionTable[j][curStateIndex] = new ArrayList<>();
      }
      // construct transition
      if (IoTDBConstant.ONE_LEVEL_PATH_WILDCARD.equals(node)) {
        for (IFATransition transition : transitionMap.values()) {
          nfaTransitionTable[transition.getIndex()][curStateIndex - 1].add(state);
        }
      } else if (IoTDBConstant.MULTI_LEVEL_PATH_WILDCARD.equals(node)) {
        for (IFATransition transition : transitionMap.values()) {
          nfaTransitionTable[transition.getIndex()][curStateIndex - 1].add(state);
          nfaTransitionTable[transition.getIndex()][curStateIndex].add(state);
        }
      } else {
        nfaTransitionTable[transitionMap.get(node).getIndex()][curStateIndex - 1].add(state);
      }
      if (isPrefix && i == pathPattern.getNodeLength() - 1) {
        for (IFATransition transition : transitionMap.values()) {
          nfaTransitionTable[transition.getIndex()][curStateIndex].add(state);
        }
      }
    }
  }

  /**
   * Construct NFA graph for given path pattern. Only used for authentication now.
   *
   * @param prefixOrFullPatternTree the included PartialPath must be a prefix or a fullPath
   * @param transitionMap transitionMap
   */
  public NFAGraph(
      PathPatternTree prefixOrFullPatternTree, Map<String, IFATransition> transitionMap) {
    List<PartialPath> partialPathList = prefixOrFullPatternTree.getAllPathPatterns();
    int maxStateSize = partialPathList.stream().mapToInt(PartialPath::getNodeLength).sum() + 1;
    nfaTransitionTable = new List[transitionMap.size()][maxStateSize];
    // init start state, curNodeIndex=0
    AtomicInteger stateIndexGenerator = new AtomicInteger(0);
    nfaStateList.add(new DFAState(0));
    for (int i = 0; i < transitionMap.size(); i++) {
      nfaTransitionTable[i][0] = new ArrayList<>();
    }
    for (PartialPath pathPattern : partialPathList) {
      buildPattern(pathPattern, transitionMap, stateIndexGenerator);
    }
  }

  private void buildPattern(
      PartialPath pathPattern,
      Map<String, IFATransition> transitionMap,
      AtomicInteger stateIndexGenerator) {
    // traverse pathPattern and construct NFA
    int prevIndex = 0;
    for (int i = 0; i < pathPattern.getNodeLength(); i++) {
      String node = pathPattern.getNodes()[i];
      // if it is tail node, transit to final state
      DFAState state =
          i == pathPattern.getNodeLength() - 1
              ? new DFAState(stateIndexGenerator.incrementAndGet(), true)
              : new DFAState(stateIndexGenerator.incrementAndGet());
      nfaStateList.add(state);
      for (int j = 0; j < transitionMap.size(); j++) {
        nfaTransitionTable[j][state.getIndex()] = new ArrayList<>();
      }
      // construct transition
      if (IoTDBConstant.ONE_LEVEL_PATH_WILDCARD.equals(node)) {
        for (IFATransition transition : transitionMap.values()) {
          nfaTransitionTable[transition.getIndex()][prevIndex].add(state);
        }
      } else if (IoTDBConstant.MULTI_LEVEL_PATH_WILDCARD.equals(node)) {
        for (IFATransition transition : transitionMap.values()) {
          nfaTransitionTable[transition.getIndex()][prevIndex].add(state);
          nfaTransitionTable[transition.getIndex()][state.getIndex()].add(state);
        }
      } else {
        nfaTransitionTable[transitionMap.get(node).getIndex()][prevIndex].add(state);
      }
      prevIndex = state.getIndex();
    }
  }

  @TestOnly
  public void print(Map<String, IFATransition> transitionMap) {
    System.out.println();
    System.out.println();
    System.out.println("NFA:");
    System.out.println(
        "==================================================================================================");
    StringBuilder stringBuilder = new StringBuilder();
    stringBuilder.append(String.format("|%-15s|", "State"));
    for (IFATransition transfer : transitionMap.values()) {
      stringBuilder.append(String.format("%-15s|", transfer.toString()));
    }
    stringBuilder.append(String.format("%-15s|", "Final"));
    System.out.println(stringBuilder);
    for (int i = 0; i < nfaStateList.size(); i++) {
      stringBuilder = new StringBuilder();
      stringBuilder.append(String.format("|%-15d|", i));
      for (IFATransition transition : transitionMap.values()) {
        stringBuilder.append(
            String.format(
                "%-15s|",
                StringUtils.join(
                    nfaTransitionTable[transition.getIndex()][i].stream()
                        .map(IFAState::getIndex)
                        .collect(Collectors.toList()),
                    ",")));
      }
      stringBuilder.append(String.format("%-15s|", nfaStateList.get(i).isFinal()));
      System.out.println(stringBuilder);
    }
  }

  public List<IFAState> getTransitions(IFATransition transition, IFAState state) {
    return nfaTransitionTable[transition.getIndex()][state.getIndex()];
  }

  public int getStateSize() {
    return nfaStateList.size();
  }
}

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.graph;
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.dfa.DFAState;
27	import org.apache.iotdb.commons.utils.TestOnly;
28
29	import org.apache.commons.lang3.StringUtils;
30
31	import java.util.ArrayList;
32	import java.util.List;
33	import java.util.Map;
34	import java.util.concurrent.atomic.AtomicInteger;
35	import java.util.stream.Collectors;
36
37	/**
38	* NFA graph for given path pattern. State 0 is initial state. Run PatternDFATest#printFASketch for
39	* more detail.
40	*/
41	public class NFAGraph {
42	private final List<IFAState> nfaStateList = new ArrayList<>();	1✔
43
44	// [transitionIndex][stateIndex]List<IFAState>
45	private final List<IFAState>[][] nfaTransitionTable;
46
47	/**
48	* Construct NFA graph for given path pattern.
49	*
50	* @param pathPattern matched path pattern
51	* @param isPrefix prefix match mode, matched pattern will be pathPattern.** if isPrefix is true
52	* @param transitionMap transitionMap
53	*/
54	public NFAGraph(
55	PartialPath pathPattern, boolean isPrefix, Map<String, IFATransition> transitionMap) {	1✔
56	nfaTransitionTable = new List[transitionMap.size()][pathPattern.getNodeLength() + 1];	1✔
57	// init start state, curNodeIndex=0
58	int curStateIndex = 0;	1✔
59	nfaStateList.add(new DFAState(curStateIndex));	1✔
60	for (int i = 0; i < transitionMap.size(); i++) {	1✔
61	nfaTransitionTable[i][0] = new ArrayList<>();	1✔
62	}
63	// traverse pathPattern and construct NFA
64	for (int i = 0; i < pathPattern.getNodeLength(); i++) {	1✔
65	String node = pathPattern.getNodes()[i];	1✔
66	// if it is tail node, transit to final state
67	DFAState state =
68	i == pathPattern.getNodeLength() - 1	1✔
69	? new DFAState(++curStateIndex, true)	1✔
70	: new DFAState(++curStateIndex);	1✔
71	nfaStateList.add(state);	1✔
72	for (int j = 0; j < transitionMap.size(); j++) {	1✔
73	nfaTransitionTable[j][curStateIndex] = new ArrayList<>();	1✔
74	}
75	// construct transition
76	if (IoTDBConstant.ONE_LEVEL_PATH_WILDCARD.equals(node)) {	1✔
77	for (IFATransition transition : transitionMap.values()) {	1✔
78	nfaTransitionTable[transition.getIndex()][curStateIndex - 1].add(state);	1✔
79	}	1✔
80	} else if (IoTDBConstant.MULTI_LEVEL_PATH_WILDCARD.equals(node)) {	1✔
81	for (IFATransition transition : transitionMap.values()) {	1✔
82	nfaTransitionTable[transition.getIndex()][curStateIndex - 1].add(state);	1✔
83	nfaTransitionTable[transition.getIndex()][curStateIndex].add(state);	1✔
84	}	1✔
85	} else {
86	nfaTransitionTable[transitionMap.get(node).getIndex()][curStateIndex - 1].add(state);	1✔
87	}
88	if (isPrefix && i == pathPattern.getNodeLength() - 1) {	1✔
89	for (IFATransition transition : transitionMap.values()) {	1✔
90	nfaTransitionTable[transition.getIndex()][curStateIndex].add(state);	1✔
91	}	1✔
92	}
93	}
94	}	1✔
95
96	/**
97	* Construct NFA graph for given path pattern. Only used for authentication now.
98	*
99	* @param prefixOrFullPatternTree the included PartialPath must be a prefix or a fullPath
100	* @param transitionMap transitionMap
101	*/
102	public NFAGraph(
103	PathPatternTree prefixOrFullPatternTree, Map<String, IFATransition> transitionMap) {	1✔
104	List<PartialPath> partialPathList = prefixOrFullPatternTree.getAllPathPatterns();	1✔
105	int maxStateSize = partialPathList.stream().mapToInt(PartialPath::getNodeLength).sum() + 1;	1✔
106	nfaTransitionTable = new List[transitionMap.size()][maxStateSize];	1✔
107	// init start state, curNodeIndex=0
108	AtomicInteger stateIndexGenerator = new AtomicInteger(0);	1✔
109	nfaStateList.add(new DFAState(0));	1✔
110	for (int i = 0; i < transitionMap.size(); i++) {	1✔
111	nfaTransitionTable[i][0] = new ArrayList<>();	1✔
112	}
113	for (PartialPath pathPattern : partialPathList) {	1✔
114	buildPattern(pathPattern, transitionMap, stateIndexGenerator);	1✔
115	}	1✔
116	}	1✔
117
118	private void buildPattern(
119	PartialPath pathPattern,
120	Map<String, IFATransition> transitionMap,
121	AtomicInteger stateIndexGenerator) {
122	// traverse pathPattern and construct NFA
123	int prevIndex = 0;	1✔
124	for (int i = 0; i < pathPattern.getNodeLength(); i++) {	1✔
125	String node = pathPattern.getNodes()[i];	1✔
126	// if it is tail node, transit to final state
127	DFAState state =
128	i == pathPattern.getNodeLength() - 1	1✔
129	? new DFAState(stateIndexGenerator.incrementAndGet(), true)	1✔
130	: new DFAState(stateIndexGenerator.incrementAndGet());	1✔
131	nfaStateList.add(state);	1✔
132	for (int j = 0; j < transitionMap.size(); j++) {	1✔
133	nfaTransitionTable[j][state.getIndex()] = new ArrayList<>();	1✔
134	}
135	// construct transition
136	if (IoTDBConstant.ONE_LEVEL_PATH_WILDCARD.equals(node)) {	1✔
137	for (IFATransition transition : transitionMap.values()) {	×
138	nfaTransitionTable[transition.getIndex()][prevIndex].add(state);	×
139	}	×
140	} else if (IoTDBConstant.MULTI_LEVEL_PATH_WILDCARD.equals(node)) {	1✔
141	for (IFATransition transition : transitionMap.values()) {	1✔
142	nfaTransitionTable[transition.getIndex()][prevIndex].add(state);	1✔
143	nfaTransitionTable[transition.getIndex()][state.getIndex()].add(state);	1✔
144	}	1✔
145	} else {
146	nfaTransitionTable[transitionMap.get(node).getIndex()][prevIndex].add(state);	1✔
147	}
148	prevIndex = state.getIndex();	1✔
149	}
150	}	1✔
151
152	@TestOnly
153	public void print(Map<String, IFATransition> transitionMap) {
154	System.out.println();	×
155	System.out.println();	×
156	System.out.println("NFA:");	×
157	System.out.println(	×
158	"==================================================================================================");
159	StringBuilder stringBuilder = new StringBuilder();	×
160	stringBuilder.append(String.format("\|%-15s\|", "State"));	×
161	for (IFATransition transfer : transitionMap.values()) {	×
162	stringBuilder.append(String.format("%-15s\|", transfer.toString()));	×
163	}	×
164	stringBuilder.append(String.format("%-15s\|", "Final"));	×
165	System.out.println(stringBuilder);	×
166	for (int i = 0; i < nfaStateList.size(); i++) {	×
167	stringBuilder = new StringBuilder();	×
168	stringBuilder.append(String.format("\|%-15d\|", i));	×
169	for (IFATransition transition : transitionMap.values()) {	×
170	stringBuilder.append(	×
171	String.format(	×
172	"%-15s\|",
173	StringUtils.join(	×
174	nfaTransitionTable[transition.getIndex()][i].stream()	×
175	.map(IFAState::getIndex)	×
176	.collect(Collectors.toList()),	×
177	",")));
178	}	×
179	stringBuilder.append(String.format("%-15s\|", nfaStateList.get(i).isFinal()));	×
180	System.out.println(stringBuilder);	×
181	}
182	}	×
183
184	public List<IFAState> getTransitions(IFATransition transition, IFAState state) {
185	return nfaTransitionTable[transition.getIndex()][state.getIndex()];	1✔
186	}
187
188	public int getStateSize() {
189	return nfaStateList.size();	1✔
190	}
191	}

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