fcea19f0836ed3729d855b1efe3136905b623bee
[idea/community.git] / 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 }