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.java.decompiler.modules.decompiler.stats.Statement;
   5 import org.jetbrains.java.decompiler.util.ListStack;
   6
   7 import java.util.*;
   8
   9 public class StrongConnectivityHelper {
  10   private final List<List<Statement>> components;
  11   private final Set<Statement> setProcessed;
  12
  13   private ListStack<Statement> lstack;
  14   private int ncounter;
  15   private Set<Statement> tset;
  16   private Map<Statement, Integer> dfsnummap;
  17   private Map<Statement, Integer> lowmap;
  18
  19   public StrongConnectivityHelper(Statement stat) {
  20     components = new ArrayList<>();
  21     setProcessed = new HashSet<>();
  22
  23     visitTree(stat.getFirst());
  24
  25     for (Statement st : stat.getStats()) {
  26       if (!setProcessed.contains(st) && st.getPredecessorEdges(Statement.STATEDGE_DIRECT_ALL).isEmpty()) {
  27         visitTree(st);
  28       }
  29     }
  30
  31     // should not find any more nodes! FIXME: ??
  32     for (Statement st : stat.getStats()) {
  33       if (!setProcessed.contains(st)) {
  34         visitTree(st);
  35       }
  36     }
  37   }
  38
  39   private void visitTree(Statement stat) {
  40     lstack = new ListStack<>();
  41     ncounter = 0;
  42     tset = new HashSet<>();
  43     dfsnummap = new HashMap<>();
  44     lowmap = new HashMap<>();
  45
  46     visit(stat);
  47
  48     setProcessed.addAll(tset);
  49     setProcessed.add(stat);
  50   }
  51
  52   private void visit(Statement stat) {
  53     lstack.push(stat);
  54     dfsnummap.put(stat, ncounter);
  55     lowmap.put(stat, ncounter);
  56     ncounter++;
  57
  58     List<Statement> lstSuccs = stat.getNeighbours(StatEdge.TYPE_REGULAR, Statement.DIRECTION_FORWARD); // TODO: set?
  59     lstSuccs.removeAll(setProcessed);
  60
  61     for (Statement succ : lstSuccs) {
  62       int secvalue;
  63
  64       if (tset.contains(succ)) {
  65         secvalue = dfsnummap.get(succ);
  66       }
  67       else {
  68         tset.add(succ);
  69         visit(succ);
  70         secvalue = lowmap.get(succ);
  71       }
  72       lowmap.put(stat, Math.min(lowmap.get(stat), secvalue));
  73     }
  74
  75
  76     if (lowmap.get(stat).intValue() == dfsnummap.get(stat).intValue()) {
  77       List<Statement> lst = new ArrayList<>();
  78       Statement v;
  79       do {
  80         v = lstack.pop();
  81         lst.add(v);
  82       }
  83       while (v != stat);
  84       components.add(lst);
  85     }
  86   }
  87
  88   public static boolean isExitComponent(List<? extends Statement> lst) {
  89     Set<Statement> set = new HashSet<>();
  90     for (Statement stat : lst) {
  91       set.addAll(stat.getNeighbours(StatEdge.TYPE_REGULAR, Statement.DIRECTION_FORWARD));
  92     }
  93     for (Statement stat : lst) {
  94       set.remove(stat);
  95     }
  96
  97     return (set.size() == 0);
  98   }
  99
 100   public static List<Statement> getExitReps(List<? extends List<Statement>> lst) {
 101     List<Statement> res = new ArrayList<>();
 102
 103     for (List<Statement> comp : lst) {
 104       if (isExitComponent(comp)) {
 105         res.add(comp.get(0));
 106       }
 107     }
 108
 109     return res;
 110   }
 111
 112   public List<List<Statement>> getComponents() {
 113     return components;
 114   }
 115 }