| /* |
| * Copyright 2000-2014 JetBrains s.r.o. |
| * |
| * Licensed 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 com.intellij.codeInspection.bytecodeAnalysis.asm; |
| |
| import com.intellij.codeInspection.bytecodeAnalysis.asm.ControlFlowGraph.Edge; |
| |
| import java.util.HashSet; |
| import java.util.Set; |
| |
| /** |
| * @author lambdamix |
| */ |
| public final class DFSTree { |
| public final int[] preOrder, postOrder; |
| public final Set<Edge> nonBack, back; |
| public final boolean[] loopEnters; |
| |
| DFSTree(int[] preOrder, |
| int[] postOrder, |
| Set<Edge> nonBack, |
| Set<Edge> back, |
| boolean[] loopEnters) { |
| this.preOrder = preOrder; |
| this.postOrder = postOrder; |
| this.nonBack = nonBack; |
| this.back = back; |
| this.loopEnters = loopEnters; |
| } |
| |
| public final boolean isDescendant(int child, int parent) { |
| return preOrder[parent] <= preOrder[child] && postOrder[child] <= postOrder[parent]; |
| } |
| |
| // Graphs: Theory and Algorithms. by K. Thulasiraman , M. N. S. Swamy (1992) |
| // 11.7.2 DFS of a directed graph |
| public static DFSTree build(int[][] transitions, int edgeCount) { |
| HashSet<Edge> nonBack = new HashSet<Edge>(); |
| HashSet<Edge> back = new HashSet<Edge>(); |
| |
| boolean[] marked = new boolean[transitions.length]; |
| boolean[] scanned = new boolean[transitions.length]; |
| int[] preOrder = new int[transitions.length]; |
| int[] postOrder = new int[transitions.length]; |
| |
| int entered = 0; |
| int completed = 0; |
| |
| boolean[] loopEnters = new boolean[transitions.length]; |
| |
| // enter 0 |
| entered ++; |
| preOrder[0] = entered; |
| marked[0] = true; |
| |
| boolean[] stackFlag = new boolean[edgeCount*2 + 1]; |
| int[] stackFrom = new int[edgeCount*2 + 1]; |
| int[] stackTo = new int[edgeCount*2 + 1]; |
| |
| int top = 0; |
| |
| // stack.push(new MarkScanned(0)); |
| stackFlag[top] = true; |
| stackTo[top] = 0; |
| top++; |
| |
| for (int to : transitions[0]) { |
| //stack.push(new ExamineEdge(0, to)); |
| stackFlag[top] = false; |
| stackFrom[top] = 0; |
| stackTo[top] = to; |
| top++; |
| } |
| |
| while (top > 0) { |
| top--; |
| //Action action = stack.pop(); |
| // markScanned |
| if (stackFlag[top]) { |
| completed ++; |
| postOrder[stackTo[top]] = completed; |
| scanned[stackTo[top]] = true; |
| } |
| else { |
| //ExamineEdge examineEdgeAction = (ExamineEdge) action; |
| int from = stackFrom[top]; |
| int to = stackTo[top]; |
| if (!marked[to]) { |
| nonBack.add(new Edge(from, to)); |
| // enter to |
| entered ++; |
| preOrder[to] = entered; |
| marked[to] = true; |
| |
| //stack.push(new MarkScanned(to)); |
| stackFlag[top] = true; |
| stackTo[top] = to; |
| top++; |
| |
| for (int to1 : transitions[to]) { |
| //stack.push(new ExamineEdge(to, to1)); |
| stackFlag[top] = false; |
| stackFrom[top] = to; |
| stackTo[top] = to1; |
| top++; |
| } |
| } |
| else if (preOrder[to] > preOrder[from]) { |
| nonBack.add(new Edge(from, to)); |
| } |
| else if (preOrder[to] < preOrder[from] && !scanned[to]) { |
| back.add(new Edge(from, to)); |
| loopEnters[to] = true; |
| } else { |
| nonBack.add(new Edge(from, to)); |
| } |
| } |
| } |
| |
| return new DFSTree(preOrder, postOrder, nonBack, back, loopEnters); |
| } |
| } |