diff options
Diffstat (limited to 'plugins/java-decompiler/engine/src/org/jetbrains/java/decompiler/modules/decompiler/StrongConnectivityHelper.java')
-rw-r--r-- | plugins/java-decompiler/engine/src/org/jetbrains/java/decompiler/modules/decompiler/StrongConnectivityHelper.java | 207 |
1 files changed, 207 insertions, 0 deletions
diff --git a/plugins/java-decompiler/engine/src/org/jetbrains/java/decompiler/modules/decompiler/StrongConnectivityHelper.java b/plugins/java-decompiler/engine/src/org/jetbrains/java/decompiler/modules/decompiler/StrongConnectivityHelper.java new file mode 100644 index 000000000000..23f778daea97 --- /dev/null +++ b/plugins/java-decompiler/engine/src/org/jetbrains/java/decompiler/modules/decompiler/StrongConnectivityHelper.java @@ -0,0 +1,207 @@ +/* + * 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 org.jetbrains.java.decompiler.modules.decompiler; + +import org.jetbrains.java.decompiler.modules.decompiler.stats.Statement; +import org.jetbrains.java.decompiler.util.ListStack; + +import java.util.ArrayList; +import java.util.HashMap; +import java.util.HashSet; +import java.util.List; + +// -------------------------------------------------------------------- +// Algorithm +// -------------------------------------------------------------------- +// DFS(G) +// { +// make a new vertex x with edges x->v for all v +// initialize a counter N to zero +// initialize list L to empty +// build directed tree T, initially a single vertex {x} +// visit(x) +// } +// +// visit(p) +// { +// add p to L +// dfsnum(p) = N +// increment N +// low(p) = dfsnum(p) +// for each edge p->q +// if q is not already in T +// { +// add p->q to T +// visit(q) +// low(p) = min(low(p), low(q)) +// } else low(p) = min(low(p), dfsnum(q)) +// +// if low(p)=dfsnum(p) +// { +// output "component:" +// repeat +// remove last element v from L +// output v +// remove v from G +// until v=p +// } +// } +// -------------------------------------------------------------------- + +public class StrongConnectivityHelper { + + private ListStack<Statement> lstack; + + private int ncounter; + + private HashSet<Statement> tset; + private HashMap<Statement, Integer> dfsnummap; + private HashMap<Statement, Integer> lowmap; + + private List<List<Statement>> components; + + private HashSet<Statement> setProcessed; + + // ***************************************************************************** + // constructors + // ***************************************************************************** + + public StrongConnectivityHelper() { + } + + public StrongConnectivityHelper(Statement stat) { + findComponents(stat); + } + + // ***************************************************************************** + // public methods + // ***************************************************************************** + + public List<List<Statement>> findComponents(Statement stat) { + + components = new ArrayList<List<Statement>>(); + setProcessed = new HashSet<Statement>(); + + visitTree(stat.getFirst()); + + for (Statement st : stat.getStats()) { + if (!setProcessed.contains(st) && st.getPredecessorEdges(Statement.STATEDGE_DIRECT_ALL).isEmpty()) { + visitTree(st); + } + } + + // should not find any more nodes! FIXME: ?? + for (Statement st : stat.getStats()) { + if (!setProcessed.contains(st)) { + visitTree(st); + } + } + + return components; + } + + public static boolean isExitComponent(List<Statement> lst) { + + HashSet<Statement> set = new HashSet<Statement>(); + for (Statement stat : lst) { + set.addAll(stat.getNeighbours(StatEdge.TYPE_REGULAR, Statement.DIRECTION_FORWARD)); + } + set.removeAll(lst); + + return (set.size() == 0); + } + + public static List<Statement> getExitReps(List<List<Statement>> lst) { + + List<Statement> res = new ArrayList<Statement>(); + + for (List<Statement> comp : lst) { + if (isExitComponent(comp)) { + res.add(comp.get(0)); + } + } + + return res; + } + + // ***************************************************************************** + // private methods + // ***************************************************************************** + + private void visitTree(Statement stat) { + lstack = new ListStack<Statement>(); + ncounter = 0; + tset = new HashSet<Statement>(); + dfsnummap = new HashMap<Statement, Integer>(); + lowmap = new HashMap<Statement, Integer>(); + + visit(stat); + + setProcessed.addAll(tset); + setProcessed.add(stat); + } + + private void visit(Statement stat) { + + lstack.push(stat); + dfsnummap.put(stat, ncounter); + lowmap.put(stat, ncounter); + ncounter++; + + List<Statement> lstSuccs = stat.getNeighbours(StatEdge.TYPE_REGULAR, Statement.DIRECTION_FORWARD); // TODO: set? + lstSuccs.removeAll(setProcessed); + + for (int i = 0; i < lstSuccs.size(); i++) { + Statement succ = lstSuccs.get(i); + int secvalue; + + if (tset.contains(succ)) { + secvalue = dfsnummap.get(succ); + } + else { + tset.add(succ); + visit(succ); + secvalue = lowmap.get(succ); + } + lowmap.put(stat, Math.min(lowmap.get(stat), secvalue)); + } + + + if (lowmap.get(stat).intValue() == dfsnummap.get(stat).intValue()) { + List<Statement> lst = new ArrayList<Statement>(); + Statement v; + do { + v = lstack.pop(); + lst.add(v); + } + while (v != stat); + components.add(lst); + } + } + + + // ***************************************************************************** + // getter and setter methods + // ***************************************************************************** + + public List<List<Statement>> getComponents() { + return components; + } + + public void setComponents(List<List<Statement>> components) { + this.components = components; + } +} |