plugins/java-decompiler/engine/src/org/jetbrains/java/decompiler/modules/decompiler/StrongConnectivityHelper.java

   1 // 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.
   2 package org.jetbrains.java.decompiler.modules.decompiler;
   3
   4 import org.jetbrains.annotations.NotNull;
   5 import org.jetbrains.java.decompiler.modules.decompiler.stats.Statement;
   6 import org.jetbrains.java.decompiler.util.ListStack;
   7
   8 import java.util.*;
   9
  10 /**
  11  * The class finds the strongly connected components (SCCs) of a directed graph,
  12  * implementing "Tarjan's strongly connected components" algorithm.
  13  * Running time is linear.
  14  */
  15 // todo should be replaced or reuse InferenceGraphNode.strongConnect or DFSTBuilder.Tarjan?
  16 public class StrongConnectivityHelper {
  17   private final List<List<Statement>> components = new ArrayList<>();
  18   private final Set<Statement> setProcessed = new HashSet<>();
  19   private final ListStack<Statement> component = new ListStack<>();
  20   private final Set<Statement> visited = new HashSet<>();
  21   private final Map<Statement, Integer> indices = new HashMap<>();
  22   private final Map<Statement, Integer> lowIndices = new HashMap<>();
  23
  24   private int nextIndex;
  25
  26   public StrongConnectivityHelper(@NotNull Statement startStatement) {
  27     visitTree(startStatement.getFirst());
  28     for (Statement statement : startStatement.getStats()) {
  29       if (!setProcessed.contains(statement) && statement.getPredecessorEdges(Statement.STATEDGE_DIRECT_ALL).isEmpty()) {
  30         visitTree(statement);
  31       }
  32     }
  33     // should not find any more nodes! FIXME: ??
  34     for (Statement statement : startStatement.getStats()) {
  35       if (!setProcessed.contains(statement)) {
  36         visitTree(statement);
  37       }
  38     }
  39   }
  40
  41   private void visitTree(@NotNull Statement statement) {
  42     component.clear();
  43     visited.clear();
  44     indices.clear();
  45     lowIndices.clear();
  46     nextIndex = 0;
  47
  48     visit(statement);
  49
  50     setProcessed.addAll(visited);
  51     setProcessed.add(statement);
  52   }
  53
  54   private void visit(@NotNull Statement statement) {
  55     component.push(statement);
  56     indices.put(statement, nextIndex);
  57     lowIndices.put(statement, nextIndex);
  58     nextIndex++;
  59     List<Statement> successors = statement.getNeighbours(StatEdge.TYPE_REGULAR, Statement.DIRECTION_FORWARD); // TODO: set?
  60     successors.removeAll(setProcessed);
  61     for (Statement successor : successors) {
  62       int successorIndex;
  63       if (visited.contains(successor)) {
  64         successorIndex = indices.get(successor);
  65       }
  66       else {
  67         visited.add(successor);
  68         visit(successor);
  69         successorIndex = lowIndices.get(successor);
  70       }
  71       lowIndices.put(statement, Math.min(lowIndices.get(statement), successorIndex));
  72     }
  73     if (lowIndices.get(statement).intValue() == indices.get(statement).intValue()) {
  74       List<Statement> component = new ArrayList<>();
  75       Statement statementInComponent;
  76       do {
  77         statementInComponent = this.component.pop();
  78         component.add(statementInComponent);
  79       }
  80       while (statementInComponent != statement);
  81       components.add(component);
  82     }
  83   }
  84
  85   public static boolean isExitComponent(@NotNull List<? extends Statement> component) {
  86     Set<Statement> statements = new HashSet<>();
  87     for (Statement statement : component) {
  88       statements.addAll(statement.getNeighbours(StatEdge.TYPE_REGULAR, Statement.DIRECTION_FORWARD));
  89     }
  90     for (Statement statement : component) {
  91       statements.remove(statement);
  92     }
  93     return statements.size() == 0;
  94   }
  95
  96   public @NotNull List<Statement> getExitReps() {
  97     List<Statement> result = new ArrayList<>();
  98     for (List<Statement> component : components) {
  99       if (isExitComponent(component)) {
 100         result.add(component.get(0));
 101       }
 102     }
 103     return result;
 104   }
 105
 106   public @NotNull List<@NotNull List<Statement>> getComponents() {
 107     return components;
 108   }
 109 }