// Copyright 2000-2017 JetBrains s.r.o. Use of this source code is governed by the Apache 2.0 license that can be found in the LICENSE file.
package org.jetbrains.java.decompiler.modules.decompiler;
+import org.jetbrains.annotations.NotNull;
import org.jetbrains.java.decompiler.modules.decompiler.stats.Statement;
import org.jetbrains.java.decompiler.util.ListStack;
import java.util.*;
+/**
+ * The class finds the strongly connected components (SCCs) of a directed graph,
+ * implementing "Tarjan's strongly connected components" algorithm.
+ * Running time is linear.
+ */
+// todo should be replaced or reuse InferenceGraphNode.strongConnect or DFSTBuilder.Tarjan?
public class StrongConnectivityHelper {
- private final List<List<Statement>> components;
- private final Set<Statement> setProcessed;
-
- private ListStack<Statement> lstack;
- private int ncounter;
- private Set<Statement> tset;
- private Map<Statement, Integer> dfsnummap;
- private Map<Statement, Integer> lowmap;
-
- public StrongConnectivityHelper(Statement stat) {
- components = new ArrayList<>();
- setProcessed = new HashSet<>();
-
- visitTree(stat.getFirst());
-
- for (Statement st : stat.getStats()) {
- if (!setProcessed.contains(st) && st.getPredecessorEdges(Statement.STATEDGE_DIRECT_ALL).isEmpty()) {
- visitTree(st);
+ private final List<List<Statement>> components = new ArrayList<>();
+ private final Set<Statement> setProcessed = new HashSet<>();
+ private final ListStack<Statement> component = new ListStack<>();
+ private final Set<Statement> visited = new HashSet<>();
+ private final Map<Statement, Integer> indices = new HashMap<>();
+ private final Map<Statement, Integer> lowIndices = new HashMap<>();
+
+ private int nextIndex;
+
+ public StrongConnectivityHelper(@NotNull Statement startStatement) {
+ visitTree(startStatement.getFirst());
+ for (Statement statement : startStatement.getStats()) {
+ if (!setProcessed.contains(statement) && statement.getPredecessorEdges(Statement.STATEDGE_DIRECT_ALL).isEmpty()) {
+ visitTree(statement);
}
}
-
// should not find any more nodes! FIXME: ??
- for (Statement st : stat.getStats()) {
- if (!setProcessed.contains(st)) {
- visitTree(st);
+ for (Statement statement : startStatement.getStats()) {
+ if (!setProcessed.contains(statement)) {
+ visitTree(statement);
}
}
}
- private void visitTree(Statement stat) {
- lstack = new ListStack<>();
- ncounter = 0;
- tset = new HashSet<>();
- dfsnummap = new HashMap<>();
- lowmap = new HashMap<>();
+ private void visitTree(@NotNull Statement statement) {
+ component.clear();
+ visited.clear();
+ indices.clear();
+ lowIndices.clear();
+ nextIndex = 0;
- visit(stat);
+ visit(statement);
- setProcessed.addAll(tset);
- setProcessed.add(stat);
+ setProcessed.addAll(visited);
+ setProcessed.add(statement);
}
- 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 (Statement succ : lstSuccs) {
- int secvalue;
-
- if (tset.contains(succ)) {
- secvalue = dfsnummap.get(succ);
+ private void visit(@NotNull Statement statement) {
+ component.push(statement);
+ indices.put(statement, nextIndex);
+ lowIndices.put(statement, nextIndex);
+ nextIndex++;
+ List<Statement> successors = statement.getNeighbours(StatEdge.TYPE_REGULAR, Statement.DIRECTION_FORWARD); // TODO: set?
+ successors.removeAll(setProcessed);
+ for (Statement successor : successors) {
+ int successorIndex;
+ if (visited.contains(successor)) {
+ successorIndex = indices.get(successor);
}
else {
- tset.add(succ);
- visit(succ);
- secvalue = lowmap.get(succ);
+ visited.add(successor);
+ visit(successor);
+ successorIndex = lowIndices.get(successor);
}
- lowmap.put(stat, Math.min(lowmap.get(stat), secvalue));
+ lowIndices.put(statement, Math.min(lowIndices.get(statement), successorIndex));
}
-
-
- if (lowmap.get(stat).intValue() == dfsnummap.get(stat).intValue()) {
- List<Statement> lst = new ArrayList<>();
- Statement v;
+ if (lowIndices.get(statement).intValue() == indices.get(statement).intValue()) {
+ List<Statement> component = new ArrayList<>();
+ Statement statementInComponent;
do {
- v = lstack.pop();
- lst.add(v);
+ statementInComponent = this.component.pop();
+ component.add(statementInComponent);
}
- while (v != stat);
- components.add(lst);
+ while (statementInComponent != statement);
+ components.add(component);
}
}
- public static boolean isExitComponent(List<? extends Statement> lst) {
- Set<Statement> set = new HashSet<>();
- for (Statement stat : lst) {
- set.addAll(stat.getNeighbours(StatEdge.TYPE_REGULAR, Statement.DIRECTION_FORWARD));
+ public static boolean isExitComponent(@NotNull List<? extends Statement> component) {
+ Set<Statement> statements = new HashSet<>();
+ for (Statement statement : component) {
+ statements.addAll(statement.getNeighbours(StatEdge.TYPE_REGULAR, Statement.DIRECTION_FORWARD));
}
- for (Statement stat : lst) {
- set.remove(stat);
+ for (Statement statement : component) {
+ statements.remove(statement);
}
-
- return (set.size() == 0);
+ return statements.size() == 0;
}
- public static List<Statement> getExitReps(List<? extends List<Statement>> lst) {
- List<Statement> res = new ArrayList<>();
-
- for (List<Statement> comp : lst) {
- if (isExitComponent(comp)) {
- res.add(comp.get(0));
+ public @NotNull List<Statement> getExitReps() {
+ List<Statement> result = new ArrayList<>();
+ for (List<Statement> component : components) {
+ if (isExitComponent(component)) {
+ result.add(component.get(0));
}
}
-
- return res;
+ return result;
}
- public List<List<Statement>> getComponents() {
+ public @NotNull List<@NotNull List<Statement>> getComponents() {
return components;
}
}
\ No newline at end of file