IDEA-285172 - [decompiler] - StrongConnectivityHelper refactoring

GitOrigin-RevId: 121119ea1def527f883a3034b1814ea7496871a0

diff --git a/plugins/java-decompiler/engine/src/org/jetbrains/java/decompiler/modules/decompiler/DomHelper.java b/plugins/java-decompiler/engine/src/org/jetbrains/java/decompiler/modules/decompiler/DomHelper.java
index b3bf84ac71ec113f7364a2f2586abd858b061892..ef674192e7aabeb742e127909df28c3c6d7d3aa4 100644 (file)
--- a/plugins/java-decompiler/engine/src/org/jetbrains/java/decompiler/modules/decompiler/DomHelper.java
+++ b/plugins/java-decompiler/engine/src/org/jetbrains/java/decompiler/modules/decompiler/DomHelper.java
@@ -90,10 +90,9 @@ public final class DomHelper {
 
     HashMap<Statement, FastFixedSet<Statement>> lists = new HashMap<>();
 
-    StrongConnectivityHelper schelper = new StrongConnectivityHelper(container);
-    List<List<Statement>> components = schelper.getComponents();
+    StrongConnectivityHelper connectivityHelper = new StrongConnectivityHelper(container);
 
-    List<Statement> lstStats = container.getPostReversePostOrderList(StrongConnectivityHelper.getExitReps(components));
+    List<Statement> lstStats = container.getPostReversePostOrderList(connectivityHelper.getExitReps());
 
     FastFixedSetFactory<Statement> factory = new FastFixedSetFactory<>(lstStats);
 
@@ -103,7 +102,7 @@ public final class DomHelper {
     FastFixedSet<Statement> initSet = factory.spawnEmptySet();
     initSet.setAllElements();
 
-    for (List<Statement> lst : components) {
+    for (List<Statement> lst : connectivityHelper.getComponents()) {
       FastFixedSet<Statement> tmpSet;
 
       if (StrongConnectivityHelper.isExitComponent(lst)) {

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
index fcea19f0836ed3729d855b1efe3136905b623bee..952855a7d5bf77b77f4cb1777e1d0c781ef9b2d1 100644 (file)
--- 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
@@ -1,115 +1,109 @@
 // 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

diff --git a/plugins/java-decompiler/engine/src/org/jetbrains/java/decompiler/modules/decompiler/stats/Statement.java b/plugins/java-decompiler/engine/src/org/jetbrains/java/decompiler/modules/decompiler/stats/Statement.java
index f29a45008525be7e84a4ca4cf89c910bc2dc2821..8cbb3c9d8e2e36db43ab240c0cad93f019e57425 100644 (file)
--- a/plugins/java-decompiler/engine/src/org/jetbrains/java/decompiler/modules/decompiler/stats/Statement.java
+++ b/plugins/java-decompiler/engine/src/org/jetbrains/java/decompiler/modules/decompiler/stats/Statement.java
@@ -439,8 +439,7 @@ public class Statement implements IMatchable {
     List<Statement> res = new ArrayList<>();
 
     if (lstexits == null) {
-      StrongConnectivityHelper schelper = new StrongConnectivityHelper(this);
-      lstexits = StrongConnectivityHelper.getExitReps(schelper.getComponents());
+      lstexits = new StrongConnectivityHelper(this).getExitReps();
     }
 
     HashSet<Statement> setVisited = new HashSet<>();