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 }