b3bf84ac71ec113f7364a2f2586abd858b061892
[idea/community.git] / plugins / java-decompiler / engine / src / org / jetbrains / java / decompiler / modules / decompiler / DomHelper.java
1 // Copyright 2000-2021 JetBrains s.r.o. and contributors. 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.code.cfg.BasicBlock;
5 import org.jetbrains.java.decompiler.code.cfg.ControlFlowGraph;
6 import org.jetbrains.java.decompiler.code.cfg.ExceptionRangeCFG;
7 import org.jetbrains.java.decompiler.main.DecompilerContext;
8 import org.jetbrains.java.decompiler.main.extern.IFernflowerLogger;
9 import org.jetbrains.java.decompiler.modules.decompiler.decompose.FastExtendedPostdominanceHelper;
10 import org.jetbrains.java.decompiler.modules.decompiler.deobfuscator.IrreducibleCFGDeobfuscator;
11 import org.jetbrains.java.decompiler.modules.decompiler.stats.*;
12 import org.jetbrains.java.decompiler.util.FastFixedSetFactory;
13 import org.jetbrains.java.decompiler.util.FastFixedSetFactory.FastFixedSet;
14 import org.jetbrains.java.decompiler.util.VBStyleCollection;
15
16 import java.util.*;
17
18 public final class DomHelper {
19
20
21   private static RootStatement graphToStatement(ControlFlowGraph graph) {
22
23     VBStyleCollection<Statement, Integer> stats = new VBStyleCollection<>();
24     VBStyleCollection<BasicBlock, Integer> blocks = graph.getBlocks();
25
26     for (BasicBlock block : blocks) {
27       stats.addWithKey(new BasicBlockStatement(block), block.id);
28     }
29
30     BasicBlock firstblock = graph.getFirst();
31     // head statement
32     Statement firstst = stats.getWithKey(firstblock.id);
33     // dummy exit statement
34     DummyExitStatement dummyexit = new DummyExitStatement();
35
36     Statement general;
37     if (stats.size() > 1 || firstblock.isSuccessor(firstblock)) { // multiple basic blocks or an infinite loop of one block
38       general = new GeneralStatement(firstst, stats, null);
39     }
40     else { // one straightforward basic block
41       RootStatement root = new RootStatement(firstst, dummyexit);
42       firstst.addSuccessor(new StatEdge(StatEdge.TYPE_BREAK, firstst, dummyexit, root));
43
44       return root;
45     }
46
47     for (BasicBlock block : blocks) {
48       Statement stat = stats.getWithKey(block.id);
49
50       for (BasicBlock succ : block.getSuccessors()) {
51         Statement stsucc = stats.getWithKey(succ.id);
52
53         int type;
54         if (stsucc == firstst) {
55           type = StatEdge.TYPE_CONTINUE;
56         }
57         else if (graph.getFinallyExits().contains(block)) {
58           type = StatEdge.TYPE_FINALLYEXIT;
59           stsucc = dummyexit;
60         }
61         else if (succ.id == graph.getLast().id) {
62           type = StatEdge.TYPE_BREAK;
63           stsucc = dummyexit;
64         }
65         else {
66           type = StatEdge.TYPE_REGULAR;
67         }
68
69         stat.addSuccessor(new StatEdge(type, stat, (type == StatEdge.TYPE_CONTINUE) ? general : stsucc,
70                                        (type == StatEdge.TYPE_REGULAR) ? null : general));
71       }
72
73       // exceptions edges
74       for (BasicBlock succex : block.getSuccessorExceptions()) {
75         Statement stsuccex = stats.getWithKey(succex.id);
76
77         ExceptionRangeCFG range = graph.getExceptionRange(succex, block);
78         if (!range.isCircular()) {
79           stat.addSuccessor(new StatEdge(stat, stsuccex, range.getExceptionTypes()));
80         }
81       }
82     }
83
84     general.buildContinueSet();
85     general.buildMonitorFlags();
86     return new RootStatement(general, dummyexit);
87   }
88
89   public static VBStyleCollection<List<Integer>, Integer> calcPostDominators(Statement container) {
90
91     HashMap<Statement, FastFixedSet<Statement>> lists = new HashMap<>();
92
93     StrongConnectivityHelper schelper = new StrongConnectivityHelper(container);
94     List<List<Statement>> components = schelper.getComponents();
95
96     List<Statement> lstStats = container.getPostReversePostOrderList(StrongConnectivityHelper.getExitReps(components));
97
98     FastFixedSetFactory<Statement> factory = new FastFixedSetFactory<>(lstStats);
99
100     FastFixedSet<Statement> setFlagNodes = factory.spawnEmptySet();
101     setFlagNodes.setAllElements();
102
103     FastFixedSet<Statement> initSet = factory.spawnEmptySet();
104     initSet.setAllElements();
105
106     for (List<Statement> lst : components) {
107       FastFixedSet<Statement> tmpSet;
108
109       if (StrongConnectivityHelper.isExitComponent(lst)) {
110         tmpSet = factory.spawnEmptySet();
111         tmpSet.addAll(lst);
112       }
113       else {
114         tmpSet = initSet.getCopy();
115       }
116
117       for (Statement stat : lst) {
118         lists.put(stat, tmpSet);
119       }
120     }
121
122     do {
123
124       for (Statement stat : lstStats) {
125
126         if (!setFlagNodes.contains(stat)) {
127           continue;
128         }
129         setFlagNodes.remove(stat);
130
131         FastFixedSet<Statement> doms = lists.get(stat);
132         FastFixedSet<Statement> domsSuccs = factory.spawnEmptySet();
133
134         List<Statement> lstSuccs = stat.getNeighbours(StatEdge.TYPE_REGULAR, Statement.DIRECTION_FORWARD);
135         for (int j = 0; j < lstSuccs.size(); j++) {
136           Statement succ = lstSuccs.get(j);
137           FastFixedSet<Statement> succlst = lists.get(succ);
138
139           if (j == 0) {
140             domsSuccs.union(succlst);
141           }
142           else {
143             domsSuccs.intersection(succlst);
144           }
145         }
146
147         if (!domsSuccs.contains(stat)) {
148           domsSuccs.add(stat);
149         }
150
151         if (!Objects.equals(domsSuccs, doms)) {
152
153           lists.put(stat, domsSuccs);
154
155           List<Statement> lstPreds = stat.getNeighbours(StatEdge.TYPE_REGULAR, Statement.DIRECTION_BACKWARD);
156           for (Statement pred : lstPreds) {
157             setFlagNodes.add(pred);
158           }
159         }
160       }
161     }
162     while (!setFlagNodes.isEmpty());
163
164     VBStyleCollection<List<Integer>, Integer> ret = new VBStyleCollection<>();
165     List<Statement> lstRevPost = container.getReversePostOrderList(); // sort order crucial!
166
167     final HashMap<Integer, Integer> mapSortOrder = new HashMap<>();
168     for (int i = 0; i < lstRevPost.size(); i++) {
169       mapSortOrder.put(lstRevPost.get(i).id, i);
170     }
171
172     for (Statement st : lstStats) {
173
174       List<Integer> lstPosts = new ArrayList<>();
175       for (Statement stt : lists.get(st)) {
176         lstPosts.add(stt.id);
177       }
178
179       lstPosts.sort(Comparator.comparing(mapSortOrder::get));
180
181       if (lstPosts.size() > 1 && lstPosts.get(0).intValue() == st.id) {
182         lstPosts.add(lstPosts.remove(0));
183       }
184
185       ret.addWithKey(lstPosts, st.id);
186     }
187
188     return ret;
189   }
190
191   public static RootStatement parseGraph(ControlFlowGraph graph) {
192
193     RootStatement root = graphToStatement(graph);
194
195     if (!processStatement(root, new HashMap<>())) {
196
197       //                        try {
198       //                                DotExporter.toDotFile(root.getFirst().getStats().get(13), new File("c:\\Temp\\stat1.dot"));
199       //                        } catch (Exception ex) {
200       //                                ex.printStackTrace();
201       //                        }
202       throw new RuntimeException("parsing failure!");
203     }
204
205     LabelHelper.lowContinueLabels(root, new HashSet<>());
206
207     SequenceHelper.condenseSequences(root);
208     root.buildMonitorFlags();
209
210     // build synchronized statements
211     buildSynchronized(root);
212
213     return root;
214   }
215
216   public static void removeSynchronizedHandler(Statement stat) {
217
218     for (Statement st : stat.getStats()) {
219       removeSynchronizedHandler(st);
220     }
221
222     if (stat.type == Statement.TYPE_SYNCHRONIZED) {
223       ((SynchronizedStatement)stat).removeExc();
224     }
225   }
226
227
228   private static void buildSynchronized(Statement stat) {
229
230     for (Statement st : stat.getStats()) {
231       buildSynchronized(st);
232     }
233
234     if (stat.type == Statement.TYPE_SEQUENCE) {
235
236       while (true) {
237
238         boolean found = false;
239
240         List<Statement> lst = stat.getStats();
241         for (int i = 0; i < lst.size() - 1; i++) {
242           Statement current = lst.get(i);  // basic block
243
244           if (current.isMonitorEnter()) {
245
246             Statement next = lst.get(i + 1);
247             Statement nextDirect = next;
248
249             while (next.type == Statement.TYPE_SEQUENCE) {
250               next = next.getFirst();
251             }
252
253             if (next.type == Statement.TYPE_CATCH_ALL) {
254
255               CatchAllStatement ca = (CatchAllStatement)next;
256
257               if (ca.getFirst().isContainsMonitorExit() && ca.getHandler().isContainsMonitorExit()) {
258
259                 // remove the head block from sequence
260                 current.removeSuccessor(current.getSuccessorEdges(Statement.STATEDGE_DIRECT_ALL).get(0));
261
262                 for (StatEdge edge : current.getPredecessorEdges(Statement.STATEDGE_DIRECT_ALL)) {
263                   current.removePredecessor(edge);
264                   edge.getSource().changeEdgeNode(Statement.DIRECTION_FORWARD, edge, nextDirect);
265                   nextDirect.addPredecessor(edge);
266                 }
267
268                 stat.getStats().removeWithKey(current.id);
269                 stat.setFirst(stat.getStats().get(0));
270
271                 // new statement
272                 SynchronizedStatement sync = new SynchronizedStatement(current, ca.getFirst(), ca.getHandler());
273                 sync.setAllParent();
274
275                 for (StatEdge edge : new HashSet<>(ca.getLabelEdges())) {
276                   sync.addLabeledEdge(edge);
277                 }
278
279                 current.addSuccessor(new StatEdge(StatEdge.TYPE_REGULAR, current, ca.getFirst()));
280
281                 ca.getParent().replaceStatement(ca, sync);
282                 found = true;
283                 break;
284               }
285             }
286           }
287         }
288
289         if (!found) {
290           break;
291         }
292       }
293     }
294   }
295
296   private static boolean processStatement(Statement general, HashMap<Integer, Set<Integer>> mapExtPost) {
297
298     if (general.type == Statement.TYPE_ROOT) {
299       Statement stat = general.getFirst();
300       if (stat.type != Statement.TYPE_GENERAL) {
301         return true;
302       }
303       else {
304         boolean complete = processStatement(stat, mapExtPost);
305         if (complete) {
306           // replace general purpose statement with simple one
307           general.replaceStatement(stat, stat.getFirst());
308         }
309         return complete;
310       }
311     }
312
313     boolean mapRefreshed = mapExtPost.isEmpty();
314
315     for (int mapstage = 0; mapstage < 2; mapstage++) {
316
317       for (int reducibility = 0;
318            reducibility < 5;
319            reducibility++) { // FIXME: implement proper node splitting. For now up to 5 nodes in sequence are splitted.
320
321         if (reducibility > 0) {
322
323           //                                    try {
324           //                                            DotExporter.toDotFile(general, new File("c:\\Temp\\stat1.dot"));
325           //                                    } catch(Exception ex) {ex.printStackTrace();}
326
327           // take care of irreducible control flow graphs
328           if (IrreducibleCFGDeobfuscator.isStatementIrreducible(general)) {
329             if (!IrreducibleCFGDeobfuscator.splitIrreducibleNode(general)) {
330               DecompilerContext.getLogger().writeMessage("Irreducible statement cannot be decomposed!", IFernflowerLogger.Severity.ERROR);
331               break;
332             }
333           }
334           else {
335             if (mapstage == 2 || mapRefreshed) { // last chance lost
336               DecompilerContext.getLogger().writeMessage("Statement cannot be decomposed although reducible!", IFernflowerLogger.Severity.ERROR);
337             }
338             break;
339           }
340
341           //                                    try {
342           //                                            DotExporter.toDotFile(general, new File("c:\\Temp\\stat1.dot"));
343           //                                    } catch(Exception ex) {ex.printStackTrace();}
344
345           mapExtPost = new HashMap<>();
346           mapRefreshed = true;
347         }
348
349         for (int i = 0; i < 2; i++) {
350
351           boolean forceall = i != 0;
352
353           while (true) {
354
355             if (findSimpleStatements(general, mapExtPost)) {
356               reducibility = 0;
357             }
358
359             if (general.type == Statement.TYPE_PLACEHOLDER) {
360               return true;
361             }
362
363             Statement stat = findGeneralStatement(general, forceall, mapExtPost);
364
365             if (stat != null) {
366               boolean complete = processStatement(stat, general.getFirst() == stat ? mapExtPost : new HashMap<>());
367
368               if (complete) {
369                 // replace general purpose statement with simple one
370                 general.replaceStatement(stat, stat.getFirst());
371               }
372               else {
373                 return false;
374               }
375
376               mapExtPost = new HashMap<>();
377               mapRefreshed = true;
378               reducibility = 0;
379             }
380             else {
381               break;
382             }
383           }
384         }
385
386         //                              try {
387         //                                      DotExporter.toDotFile(general, new File("c:\\Temp\\stat1.dot"));
388         //                              } catch (Exception ex) {
389         //                                      ex.printStackTrace();
390         //                              }
391       }
392
393       if (mapRefreshed) {
394         break;
395       }
396       else {
397         mapExtPost = new HashMap<>();
398       }
399     }
400
401     return false;
402   }
403
404   private static Statement findGeneralStatement(Statement stat, boolean forceall, HashMap<Integer, Set<Integer>> mapExtPost) {
405
406     VBStyleCollection<Statement, Integer> stats = stat.getStats();
407     VBStyleCollection<List<Integer>, Integer> vbPost;
408
409     if (mapExtPost.isEmpty()) {
410       FastExtendedPostdominanceHelper extpost = new FastExtendedPostdominanceHelper();
411       mapExtPost.putAll(extpost.getExtendedPostdominators(stat));
412     }
413
414     if (forceall) {
415       vbPost = new VBStyleCollection<>();
416       List<Statement> lstAll = stat.getPostReversePostOrderList();
417
418       for (Statement st : lstAll) {
419         Set<Integer> set = mapExtPost.get(st.id);
420         if (set != null) {
421           vbPost.addWithKey(new ArrayList<>(set), st.id); // FIXME: sort order!!
422         }
423       }
424
425       // tail statements
426       Set<Integer> setFirst = mapExtPost.get(stat.getFirst().id);
427       if (setFirst != null) {
428         for (Integer id : setFirst) {
429           List<Integer> lst = vbPost.getWithKey(id);
430           if (lst == null) {
431             vbPost.addWithKey(lst = new ArrayList<>(), id);
432           }
433           lst.add(id);
434         }
435       }
436     }
437     else {
438       vbPost = calcPostDominators(stat);
439     }
440
441     for (int k = 0; k < vbPost.size(); k++) {
442
443       Integer headid = vbPost.getKey(k);
444       List<Integer> posts = vbPost.get(k);
445
446       if (!mapExtPost.containsKey(headid) &&
447           !(posts.size() == 1 && posts.get(0).equals(headid))) {
448         continue;
449       }
450
451       Statement head = stats.getWithKey(headid);
452
453       Set<Integer> setExtPosts = mapExtPost.get(headid);
454
455       for (Integer postId : posts) {
456         if (!postId.equals(headid) && !setExtPosts.contains(postId)) {
457           continue;
458         }
459
460         Statement post = stats.getWithKey(postId);
461
462         if (post == null) { // possible in case of an inherited postdominance set
463           continue;
464         }
465
466         boolean same = (post == head);
467
468         HashSet<Statement> setNodes = new HashSet<>();
469         HashSet<Statement> setPreds = new HashSet<>();
470
471         // collect statement nodes
472         HashSet<Statement> setHandlers = new HashSet<>();
473         setHandlers.add(head);
474         while (true) {
475
476           boolean hdfound = false;
477           for (Statement handler : setHandlers) {
478             if (setNodes.contains(handler)) {
479               continue;
480             }
481
482             boolean addhd = (setNodes.size() == 0); // first handler == head
483             if (!addhd) {
484               List<Statement> hdsupp = handler.getNeighbours(StatEdge.TYPE_EXCEPTION, Statement.DIRECTION_BACKWARD);
485               addhd = (setNodes.containsAll(hdsupp) && (setNodes.size() > hdsupp.size()
486                                                         || setNodes.size() == 1)); // strict subset
487             }
488
489             if (addhd) {
490               LinkedList<Statement> lstStack = new LinkedList<>();
491               lstStack.add(handler);
492
493               while (!lstStack.isEmpty()) {
494                 Statement st = lstStack.remove(0);
495
496                 if (!(setNodes.contains(st) || (!same && st == post))) {
497                   setNodes.add(st);
498                   if (st != head) {
499                     // record predeccessors except for the head
500                     setPreds.addAll(st.getNeighbours(StatEdge.TYPE_REGULAR, Statement.DIRECTION_BACKWARD));
501                   }
502
503                   // put successors on the stack
504                   lstStack.addAll(st.getNeighbours(StatEdge.TYPE_REGULAR, Statement.DIRECTION_FORWARD));
505
506                   // exception edges
507                   setHandlers.addAll(st.getNeighbours(StatEdge.TYPE_EXCEPTION, Statement.DIRECTION_FORWARD));
508                 }
509               }
510
511               hdfound = true;
512               setHandlers.remove(handler);
513               break;
514             }
515           }
516
517           if (!hdfound) {
518             break;
519           }
520         }
521
522         // check exception handlers
523         setHandlers.clear();
524         for (Statement st : setNodes) {
525           setHandlers.addAll(st.getNeighbours(StatEdge.TYPE_EXCEPTION, Statement.DIRECTION_FORWARD));
526         }
527         setHandlers.removeAll(setNodes);
528
529         boolean excok = true;
530         for (Statement handler : setHandlers) {
531           if (!handler.getNeighbours(StatEdge.TYPE_EXCEPTION, Statement.DIRECTION_BACKWARD).containsAll(setNodes)) {
532             excok = false;
533             break;
534           }
535         }
536
537         // build statement and return
538         if (excok) {
539           Statement res;
540
541           setPreds.removeAll(setNodes);
542           if (setPreds.size() == 0) {
543             if ((setNodes.size() > 1 ||
544                  head.getNeighbours(StatEdge.TYPE_REGULAR, Statement.DIRECTION_BACKWARD).contains(head))
545                 && setNodes.size() < stats.size()) {
546               if (checkSynchronizedCompleteness(setNodes)) {
547                 res = new GeneralStatement(head, setNodes, same ? null : post);
548                 stat.collapseNodesToStatement(res);
549
550                 return res;
551               }
552             }
553           }
554         }
555       }
556     }
557
558     return null;
559   }
560
561   private static boolean checkSynchronizedCompleteness(Set<Statement> setNodes) {
562     // check exit nodes
563     for (Statement stat : setNodes) {
564       if (stat.isMonitorEnter()) {
565         List<StatEdge> lstSuccs = stat.getSuccessorEdges(Statement.STATEDGE_DIRECT_ALL);
566         if (lstSuccs.size() != 1 || lstSuccs.get(0).getType() != StatEdge.TYPE_REGULAR) {
567           return false;
568         }
569
570         if (!setNodes.contains(lstSuccs.get(0).getDestination())) {
571           return false;
572         }
573       }
574     }
575
576     return true;
577   }
578
579   private static boolean findSimpleStatements(Statement stat, HashMap<Integer, Set<Integer>> mapExtPost) {
580
581     boolean found, success = false;
582
583     do {
584       found = false;
585
586       List<Statement> lstStats = stat.getPostReversePostOrderList();
587       for (Statement st : lstStats) {
588
589         Statement result = detectStatement(st);
590
591         if (result != null) {
592
593           if (stat.type == Statement.TYPE_GENERAL && result.getFirst() == stat.getFirst() &&
594               stat.getStats().size() == result.getStats().size()) {
595             // mark general statement
596             stat.type = Statement.TYPE_PLACEHOLDER;
597           }
598
599           stat.collapseNodesToStatement(result);
600
601           // update the postdominator map
602           if (!mapExtPost.isEmpty()) {
603             HashSet<Integer> setOldNodes = new HashSet<>();
604             for (Statement old : result.getStats()) {
605               setOldNodes.add(old.id);
606             }
607
608             Integer newid = result.id;
609
610             for (Integer key : new ArrayList<>(mapExtPost.keySet())) {
611               Set<Integer> set = mapExtPost.get(key);
612
613               int oldsize = set.size();
614               set.removeAll(setOldNodes);
615
616               if (setOldNodes.contains(key)) {
617                 mapExtPost.computeIfAbsent(newid, k -> new HashSet<>()).addAll(set);
618                 mapExtPost.remove(key);
619               }
620               else {
621                 if (set.size() < oldsize) {
622                   set.add(newid);
623                 }
624               }
625             }
626           }
627
628
629           found = true;
630           break;
631         }
632       }
633
634       if (found) {
635         success = true;
636       }
637     }
638     while (found);
639
640     return success;
641   }
642
643
644   private static Statement detectStatement(Statement head) {
645
646     Statement res;
647
648     if ((res = DoStatement.isHead(head)) != null) {
649       return res;
650     }
651
652     if ((res = SwitchStatement.isHead(head)) != null) {
653       return res;
654     }
655
656     if ((res = IfStatement.isHead(head)) != null) {
657       return res;
658     }
659
660     // synchronized statements will be identified later
661     // right now they are recognized as catchall
662
663     if ((res = SequenceStatement.isHead2Block(head)) != null) {
664       return res;
665     }
666
667     if ((res = CatchStatement.isHead(head)) != null) {
668       return res;
669     }
670
671     if ((res = CatchAllStatement.isHead(head)) != null) {
672       return res;
673     }
674
675     return null;
676   }
677 }