path: root/plugins/java-decompiler/engine/src/org/jetbrains/java/decompiler/modules/decompiler/FinallyProcessor.java

/*
 * Copyright 2000-2014 JetBrains s.r.o.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.jetbrains.java.decompiler.modules.decompiler;

import org.jetbrains.java.decompiler.code.*;
import org.jetbrains.java.decompiler.code.cfg.BasicBlock;
import org.jetbrains.java.decompiler.code.cfg.ControlFlowGraph;
import org.jetbrains.java.decompiler.code.cfg.ExceptionRangeCFG;
import org.jetbrains.java.decompiler.main.DecompilerContext;
import org.jetbrains.java.decompiler.main.collectors.CounterContainer;
import org.jetbrains.java.decompiler.main.extern.IFernflowerPreferences;
import org.jetbrains.java.decompiler.modules.code.DeadCodeHelper;
import org.jetbrains.java.decompiler.modules.decompiler.exps.AssignmentExprent;
import org.jetbrains.java.decompiler.modules.decompiler.exps.ExitExprent;
import org.jetbrains.java.decompiler.modules.decompiler.exps.Exprent;
import org.jetbrains.java.decompiler.modules.decompiler.exps.VarExprent;
import org.jetbrains.java.decompiler.modules.decompiler.sforms.DirectGraph;
import org.jetbrains.java.decompiler.modules.decompiler.sforms.DirectNode;
import org.jetbrains.java.decompiler.modules.decompiler.sforms.FlattenStatementsHelper;
import org.jetbrains.java.decompiler.modules.decompiler.sforms.SSAConstructorSparseEx;
import org.jetbrains.java.decompiler.modules.decompiler.stats.BasicBlockStatement;
import org.jetbrains.java.decompiler.modules.decompiler.stats.CatchAllStatement;
import org.jetbrains.java.decompiler.modules.decompiler.stats.RootStatement;
import org.jetbrains.java.decompiler.modules.decompiler.stats.Statement;
import org.jetbrains.java.decompiler.modules.decompiler.vars.VarProcessor;
import org.jetbrains.java.decompiler.modules.decompiler.vars.VarVersionPaar;
import org.jetbrains.java.decompiler.struct.StructMethod;
import org.jetbrains.java.decompiler.struct.gen.VarType;
import org.jetbrains.java.decompiler.util.InterpreterUtil;

import java.util.*;
import java.util.Map.Entry;

public class FinallyProcessor {

  private Map<Integer, Integer> finallyBlockIDs = new HashMap<Integer, Integer>();
  private Map<Integer, Integer> catchallBlockIDs = new HashMap<Integer, Integer>();

  private VarProcessor varprocessor;

  public FinallyProcessor(VarProcessor varprocessor) {
    this.varprocessor = varprocessor;
  }

  public boolean iterateGraph(StructMethod mt, RootStatement root, ControlFlowGraph graph) {
    //		return processStatement(mt, root, graph, root);
    return processStatementEx(mt, root, graph);
  }

  private boolean processStatementEx(StructMethod mt, RootStatement root, ControlFlowGraph graph) {

    int bytecode_version = mt.getClassStruct().getBytecodeVersion();

    LinkedList<Statement> stack = new LinkedList<Statement>();
    stack.add(root);

    while (!stack.isEmpty()) {

      Statement stat = stack.removeLast();

      Statement parent = stat.getParent();
      if (parent != null && parent.type == Statement.TYPE_CATCHALL &&
          stat == parent.getFirst() && !parent.isCopied()) {

        CatchAllStatement fin = (CatchAllStatement)parent;
        BasicBlock head = fin.getBasichead().getBlock();
        BasicBlock handler = fin.getHandler().getBasichead().getBlock();

        if (catchallBlockIDs.containsKey(handler.id)) {
          // do nothing
        }
        else if (finallyBlockIDs.containsKey(handler.id)) {

          fin.setFinally(true);

          Integer var = finallyBlockIDs.get(handler.id);
          fin.setMonitor(var == null ? null : new VarExprent(var.intValue(), VarType.VARTYPE_INT, varprocessor));
        }
        else {

          Record inf = getFinallyInformation(mt, root, fin);

          if (inf == null) { // inconsistent finally
            catchallBlockIDs.put(handler.id, null);
          }
          else {

            if (DecompilerContext.getOption(IFernflowerPreferences.FINALLY_DEINLINE) && verifyFinallyEx(graph, fin, inf)) {
              finallyBlockIDs.put(handler.id, null);
            }
            else {

              int varindex = DecompilerContext.getCounterContainer().getCounterAndIncrement(CounterContainer.VAR_COUNTER);
              insertSemaphore(graph, getAllBasicBlocks(fin.getFirst()), head, handler, varindex, inf, bytecode_version);

              finallyBlockIDs.put(handler.id, varindex);
            }

            DeadCodeHelper.removeDeadBlocks(graph); // e.g. multiple return blocks after a nested finally
            DeadCodeHelper.removeEmptyBlocks(graph);
            DeadCodeHelper.mergeBasicBlocks(graph);
          }

          return true;
        }
      }

      stack.addAll(stat.getStats());
    }

    return false;
  }


  //	private boolean processStatement(StructMethod mt, RootStatement root, ControlFlowGraph graph, Statement stat) {
  //
  //		boolean res = false;
  //
  //		for(int i=stat.getStats().size()-1;i>=0;i--) {
  //			if(processStatement(mt, root, graph, stat.getStats().get(i))) {
  //				return true;
  //			}
  //		}
  //
  //
  //		if(stat.type == Statement.TYPE_CATCHALL && !stat.isCopied()) {
  //
  //			CatchAllStatement fin = (CatchAllStatement)stat;
  //			BasicBlock head = fin.getBasichead().getBlock();
  //			BasicBlock handler = fin.getHandler().getBasichead().getBlock();
  //
  //			if(catchallBlockIDs.containsKey(handler.id)) {
  //				; // do nothing
  //			}else if(finallyBlockIDs.containsKey(handler.id)) {
  //
  //				fin.setFinally(true);
  //
  //				Integer var = finallyBlockIDs.get(handler.id);
  //				fin.setMonitor(var==null?null:new VarExprent(var.intValue(), VarType.VARTYPE_INT, varprocessor));
  //
  //			} else {
  //
  //				Object[] inf = getFinallyInformation(mt, root, fin);
  //
  //				if(inf == null) { // inconsistent finally
  //					catchallBlockIDs.put(handler.id, null);
  //				} else {
  //
  //					if(DecompilerContext.getOption(IFernflowerPreferences.FINALLY_DEINLINE) && verifyFinallyEx(graph, fin, inf)) {
  //						finallyBlockIDs.put(handler.id, null);
  //					} else {
  //
  //						int varindex = DecompilerContext.getCountercontainer().getCounterAndIncrement(CounterContainer.VAR_COUNTER);
  //						insertSemaphore(graph, getAllBasicBlocks(fin.getFirst()), head, handler, varindex, inf);
  //
  //						finallyBlockIDs.put(handler.id, varindex);
  //					}
  //
  //					DeadCodeHelper.removeEmptyBlocks(graph);
  //					DeadCodeHelper.mergeBasicBlocks(graph);
  //				}
  //
  //				res = true;
  //			}
  //		}
  //
  //		return res;
  //	}

  private static class Record {
    private final int firstCode;
    private final Map<BasicBlock, Boolean> mapLast;

    private Record(int firstCode, Map<BasicBlock, Boolean> mapLast) {
      this.firstCode = firstCode;
      this.mapLast = mapLast;
    }
  }


  private static Record getFinallyInformation(StructMethod mt, RootStatement root, CatchAllStatement fstat) {

    Map<BasicBlock, Boolean> mapLast = new HashMap<BasicBlock, Boolean>();

    BasicBlockStatement firstBlockStatement = fstat.getHandler().getBasichead();
    BasicBlock firstBasicBlock = firstBlockStatement.getBlock();
    Instruction instrFirst = firstBasicBlock.getInstruction(0);

    int firstcode = 0;

    switch (instrFirst.opcode) {
      case CodeConstants.opc_pop:
        firstcode = 1;
        break;
      case CodeConstants.opc_astore:
        firstcode = 2;
    }

    ExprProcessor proc = new ExprProcessor();
    proc.processStatement(root, mt.getClassStruct());

    SSAConstructorSparseEx ssa = new SSAConstructorSparseEx();
    ssa.splitVariables(root, mt);

    List<Exprent> lstExprents = firstBlockStatement.getExprents();

    VarVersionPaar varpaar = new VarVersionPaar((VarExprent)((AssignmentExprent)lstExprents.get(firstcode == 2 ? 1 : 0)).getLeft());

    FlattenStatementsHelper flatthelper = new FlattenStatementsHelper();
    DirectGraph dgraph = flatthelper.buildDirectGraph(root);

    LinkedList<DirectNode> stack = new LinkedList<DirectNode>();
    stack.add(dgraph.first);

    Set<DirectNode> setVisited = new HashSet<DirectNode>();

    while (!stack.isEmpty()) {

      DirectNode node = stack.removeFirst();

      if (setVisited.contains(node)) {
        continue;
      }
      setVisited.add(node);

      BasicBlockStatement blockStatement = null;
      if (node.block != null) {
        blockStatement = node.block;
      }
      else if (node.preds.size() == 1) {
        blockStatement = node.preds.get(0).block;
      }

      boolean isTrueExit = true;

      if (firstcode != 1) {

        isTrueExit = false;

        for (int i = 0; i < node.exprents.size(); i++) {
          Exprent exprent = node.exprents.get(i);

          if (firstcode == 0) {
            List<Exprent> lst = exprent.getAllExprents();
            lst.add(exprent);

            boolean found = false;
            for (Exprent expr : lst) {
              if (expr.type == Exprent.EXPRENT_VAR && new VarVersionPaar((VarExprent)expr).equals(varpaar)) {
                found = true;
                break;
              }
            }

            if (found) {
              found = false;
              if (exprent.type == Exprent.EXPRENT_EXIT) {
                ExitExprent exexpr = (ExitExprent)exprent;
                if (exexpr.getExittype() == ExitExprent.EXIT_THROW && exexpr.getValue().type == Exprent.EXPRENT_VAR) {
                  found = true;
                }
              }

              if (!found) {
                return null;
              }
              else {
                isTrueExit = true;
              }
            }
          }
          else if (firstcode == 2) {
            // search for a load instruction
            if (exprent.type == Exprent.EXPRENT_ASSIGNMENT) {
              AssignmentExprent assexpr = (AssignmentExprent)exprent;
              if (assexpr.getRight().type == Exprent.EXPRENT_VAR &&
                  new VarVersionPaar((VarExprent)assexpr.getRight()).equals(varpaar)) {

                Exprent next = null;
                if (i == node.exprents.size() - 1) {
                  if (node.succs.size() == 1) {
                    DirectNode nd = node.succs.get(0);
                    if (!nd.exprents.isEmpty()) {
                      next = nd.exprents.get(0);
                    }
                  }
                }
                else {
                  next = node.exprents.get(i + 1);
                }

                boolean found = false;
                if (next != null && next.type == Exprent.EXPRENT_EXIT) {
                  ExitExprent exexpr = (ExitExprent)next;
                  if (exexpr.getExittype() == ExitExprent.EXIT_THROW && exexpr.getValue().type == Exprent.EXPRENT_VAR
                      && assexpr.getLeft().equals(exexpr.getValue())) {
                    found = true;
                  }
                }

                if (!found) {
                  return null;
                }
                else {
                  isTrueExit = true;
                }
              }
            }
          }
        }
      }

      // find finally exits
      if (blockStatement != null && blockStatement.getBlock() != null) {
        Statement handler = fstat.getHandler();
        for (StatEdge edge : blockStatement.getSuccessorEdges(Statement.STATEDGE_DIRECT_ALL)) {
          if (edge.getType() != StatEdge.TYPE_REGULAR && handler.containsStatement(blockStatement)
              && !handler.containsStatement(edge.getDestination())) {
            Boolean existingFlag = mapLast.get(blockStatement.getBlock());
            // note: the dummy node is also processed!
            if (existingFlag == null || !existingFlag) {
              mapLast.put(blockStatement.getBlock(), isTrueExit);
              break;
            }
          }
        }
      }

      stack.addAll(node.succs);
    }

    // empty finally block?
    if (fstat.getHandler().type == Statement.TYPE_BASICBLOCK) {

      boolean isEmpty = false;
      boolean isFirstLast = mapLast.containsKey(firstBasicBlock);
      InstructionSequence seq = firstBasicBlock.getSeq();

      switch (firstcode) {
        case 0:
          isEmpty = isFirstLast && seq.length() == 1;
          break;
        case 1:
          isEmpty = seq.length() == 1;
          break;
        case 2:
          isEmpty = isFirstLast ? seq.length() == 3 : seq.length() == 1;
      }

      if (isEmpty) {
        firstcode = 3;
      }
    }

    return new Record(firstcode, mapLast);
  }

  private static void insertSemaphore(ControlFlowGraph graph,
                                      Set<BasicBlock> setTry,
                                      BasicBlock head,
                                      BasicBlock handler,
                                      int var,
                                      Record information,
                                      int bytecode_version) {

    Set<BasicBlock> setCopy = new HashSet<BasicBlock>(setTry);

    int finallytype = information.firstCode;
    Map<BasicBlock, Boolean> mapLast = information.mapLast;

    // first and last statements
    removeExceptionInstructionsEx(handler, 1, finallytype);
    for (Entry<BasicBlock, Boolean> entry : mapLast.entrySet()) {
      BasicBlock last = entry.getKey();

      if (entry.getValue()) {
        removeExceptionInstructionsEx(last, 2, finallytype);
        graph.getFinallyExits().add(last);
      }
    }

    // disable semaphore at statement exit points
    for (BasicBlock block : setTry) {

      List<BasicBlock> lstSucc = block.getSuccs();
      for (BasicBlock dest : lstSucc) {

        // break out
        if (!setCopy.contains(dest) && dest != graph.getLast()) {
          // disable semaphore
          SimpleInstructionSequence seq = new SimpleInstructionSequence();

          seq.addInstruction(ConstantsUtil
                               .getInstructionInstance(CodeConstants.opc_bipush, false, CodeConstants.GROUP_GENERAL, bytecode_version,
                                                       new int[]{0}), -1);
          seq.addInstruction(ConstantsUtil
                               .getInstructionInstance(CodeConstants.opc_istore, false, CodeConstants.GROUP_GENERAL, bytecode_version,
                                                       new int[]{var}), -1);

          // build a separate block
          BasicBlock newblock = new BasicBlock(++graph.last_id);
          newblock.setSeq(seq);

          // insert between block and dest
          block.replaceSuccessor(dest, newblock);
          newblock.addSuccessor(dest);
          setCopy.add(newblock);
          graph.getBlocks().addWithKey(newblock, newblock.id);

          // exception ranges
          // FIXME: special case synchronized

          // copy exception edges and extend protected ranges
          for (int j = 0; j < block.getSuccExceptions().size(); j++) {
            BasicBlock hd = block.getSuccExceptions().get(j);
            newblock.addSuccessorException(hd);

            ExceptionRangeCFG range = graph.getExceptionRange(hd, block);
            range.getProtectedRange().add(newblock);
          }
        }
      }
    }

    // enable semaphor at the statement entrance
    SimpleInstructionSequence seq = new SimpleInstructionSequence();
    seq.addInstruction(
      ConstantsUtil.getInstructionInstance(CodeConstants.opc_bipush, false, CodeConstants.GROUP_GENERAL, bytecode_version, new int[]{1}),
      -1);
    seq.addInstruction(
      ConstantsUtil.getInstructionInstance(CodeConstants.opc_istore, false, CodeConstants.GROUP_GENERAL, bytecode_version, new int[]{var}),
      -1);

    BasicBlock newhead = new BasicBlock(++graph.last_id);
    newhead.setSeq(seq);

    insertBlockBefore(graph, head, newhead);

    // initialize semaphor with false
    seq = new SimpleInstructionSequence();
    seq.addInstruction(
      ConstantsUtil.getInstructionInstance(CodeConstants.opc_bipush, false, CodeConstants.GROUP_GENERAL, bytecode_version, new int[]{0}),
      -1);
    seq.addInstruction(
      ConstantsUtil.getInstructionInstance(CodeConstants.opc_istore, false, CodeConstants.GROUP_GENERAL, bytecode_version, new int[]{var}),
      -1);

    BasicBlock newheadinit = new BasicBlock(++graph.last_id);
    newheadinit.setSeq(seq);

    insertBlockBefore(graph, newhead, newheadinit);

    setCopy.add(newhead);
    setCopy.add(newheadinit);

    for (BasicBlock hd : new HashSet<BasicBlock>(newheadinit.getSuccExceptions())) {
      ExceptionRangeCFG range = graph.getExceptionRange(hd, newheadinit);

      if (setCopy.containsAll(range.getProtectedRange())) {
        newheadinit.removeSuccessorException(hd);
        range.getProtectedRange().remove(newheadinit);
      }
    }
  }


  private static void insertBlockBefore(ControlFlowGraph graph, BasicBlock oldblock, BasicBlock newblock) {

    List<BasicBlock> lstTemp = new ArrayList<BasicBlock>();
    lstTemp.addAll(oldblock.getPreds());
    lstTemp.addAll(oldblock.getPredExceptions());

    // replace predecessors
    for (BasicBlock pred : lstTemp) {
      pred.replaceSuccessor(oldblock, newblock);
    }

    // copy exception edges and extend protected ranges
    for (BasicBlock hd : oldblock.getSuccExceptions()) {
      newblock.addSuccessorException(hd);

      ExceptionRangeCFG range = graph.getExceptionRange(hd, oldblock);
      range.getProtectedRange().add(newblock);
    }

    // replace handler
    for (ExceptionRangeCFG range : graph.getExceptions()) {
      if (range.getHandler() == oldblock) {
        range.setHandler(newblock);
      }
    }

    newblock.addSuccessor(oldblock);
    graph.getBlocks().addWithKey(newblock, newblock.id);
    if (graph.getFirst() == oldblock) {
      graph.setFirst(newblock);
    }
  }

  private static HashSet<BasicBlock> getAllBasicBlocks(Statement stat) {

    List<Statement> lst = new LinkedList<Statement>();
    lst.add(stat);

    int index = 0;
    do {
      Statement st = lst.get(index);

      if (st.type == Statement.TYPE_BASICBLOCK) {
        index++;
      }
      else {
        lst.addAll(st.getStats());
        lst.remove(index);
      }
    }
    while (index < lst.size());

    HashSet<BasicBlock> res = new HashSet<BasicBlock>();

    for (Statement st : lst) {
      res.add(((BasicBlockStatement)st).getBlock());
    }

    return res;
  }


  private boolean verifyFinallyEx(ControlFlowGraph graph, CatchAllStatement fstat, Record information) {

    HashSet<BasicBlock> tryBlocks = getAllBasicBlocks(fstat.getFirst());
    HashSet<BasicBlock> catchBlocks = getAllBasicBlocks(fstat.getHandler());

    int finallytype = information.firstCode;
    Map<BasicBlock, Boolean> mapLast = information.mapLast;

    BasicBlock first = fstat.getHandler().getBasichead().getBlock();
    boolean skippedFirst = false;

    if (finallytype == 3) {
      // empty finally
      removeExceptionInstructionsEx(first, 3, finallytype);

      if (mapLast.containsKey(first)) {
        graph.getFinallyExits().add(first);
      }

      return true;
    }
    else {
      if (first.getSeq().length() == 1 && finallytype > 0) {
        BasicBlock firstsuc = first.getSuccs().get(0);
        if (catchBlocks.contains(firstsuc)) {
          first = firstsuc;
          skippedFirst = true;
        }
      }
    }

    // identify start blocks
    HashSet<BasicBlock> startBlocks = new HashSet<BasicBlock>();
    for (BasicBlock block : tryBlocks) {
      startBlocks.addAll(block.getSuccs());
    }
    // throw in the try body will point directly to the dummy exit
    // so remove dummy exit
    startBlocks.remove(graph.getLast());
    startBlocks.removeAll(tryBlocks);

    List<Area> lstAreas = new ArrayList<Area>();

    for (BasicBlock start : startBlocks) {

      Area arr = compareSubgraphsEx(graph, start, catchBlocks, first, finallytype, mapLast, skippedFirst);
      if (arr == null) {
        return false;
      }

      lstAreas.add(arr);
    }

    //		try {
    //			DotExporter.toDotFile(graph, new File("c:\\Temp\\fern5.dot"), true);
    //		} catch(Exception ex){ex.printStackTrace();}

    // delete areas
    for (Area area : lstAreas) {
      deleteArea(graph, area);
    }

    //		try {
    //			DotExporter.toDotFile(graph, new File("c:\\Temp\\fern5.dot"), true);
    //		} catch(Exception ex){ex.printStackTrace();}

    // INFO: empty basic blocks may remain in the graph!
    for (Entry<BasicBlock, Boolean> entry : mapLast.entrySet()) {
      BasicBlock last = entry.getKey();

      if (entry.getValue()) {
        removeExceptionInstructionsEx(last, 2, finallytype);
        graph.getFinallyExits().add(last);
      }
    }

    removeExceptionInstructionsEx(fstat.getHandler().getBasichead().getBlock(), 1, finallytype);

    return true;
  }

  private static class Area {
    private final BasicBlock start;
    private final Set<BasicBlock> sample;
    private final BasicBlock next;

    private Area(BasicBlock start, Set<BasicBlock> sample, BasicBlock next) {
      this.start = start;
      this.sample = sample;
      this.next = next;
    }
  }

  private Area compareSubgraphsEx(ControlFlowGraph graph,
                                  BasicBlock startSample,
                                  HashSet<BasicBlock> catchBlocks,
                                  BasicBlock startCatch,
                                  int finallytype,
                                  Map<BasicBlock, Boolean> mapLast,
                                  boolean skippedFirst) {

    class BlockStackEntry {
      public BasicBlock blockCatch;
      public BasicBlock blockSample;

      // TODO: correct handling (merging) of multiple paths
      public List<int[]> lstStoreVars;

      public BlockStackEntry(BasicBlock blockCatch, BasicBlock blockSample, List<int[]> lstStoreVars) {
        this.blockCatch = blockCatch;
        this.blockSample = blockSample;
        this.lstStoreVars = new ArrayList<int[]>(lstStoreVars);
      }
    }

    List<BlockStackEntry> stack = new LinkedList<BlockStackEntry>();

    Set<BasicBlock> setSample = new HashSet<BasicBlock>();

    Map<String, BasicBlock[]> mapNext = new HashMap<String, BasicBlock[]>();

    stack.add(new BlockStackEntry(startCatch, startSample, new ArrayList<int[]>()));

    while (!stack.isEmpty()) {

      BlockStackEntry entry = stack.remove(0);
      BasicBlock blockCatch = entry.blockCatch;
      BasicBlock blockSample = entry.blockSample;

      boolean isFirstBlock = !skippedFirst && blockCatch == startCatch;
      boolean isLastBlock = mapLast.containsKey(blockCatch);
      boolean isTrueLastBlock = isLastBlock && mapLast.get(blockCatch);

      if (!compareBasicBlocksEx(graph, blockCatch, blockSample, (isFirstBlock ? 1 : 0) | (isTrueLastBlock ? 2 : 0), finallytype,
                                entry.lstStoreVars)) {
        return null;
      }

      if (blockSample.getSuccs().size() != blockCatch.getSuccs().size()) {
        return null;
      }

      setSample.add(blockSample);

      // direct successors
      for (int i = 0; i < blockCatch.getSuccs().size(); i++) {
        BasicBlock sucCatch = blockCatch.getSuccs().get(i);
        BasicBlock sucSample = blockSample.getSuccs().get(i);

        if (catchBlocks.contains(sucCatch) && !setSample.contains(sucSample)) {
          stack.add(new BlockStackEntry(sucCatch, sucSample, entry.lstStoreVars));
        }
      }


      // exception successors
      if (isLastBlock && blockSample.getSeq().isEmpty()) {
        // do nothing, blockSample will be removed anyway
      }
      else {
        if (blockCatch.getSuccExceptions().size() == blockSample.getSuccExceptions().size()) {
          for (int i = 0; i < blockCatch.getSuccExceptions().size(); i++) {
            BasicBlock sucCatch = blockCatch.getSuccExceptions().get(i);
            BasicBlock sucSample = blockSample.getSuccExceptions().get(i);

            String excCatch = graph.getExceptionRange(sucCatch, blockCatch).getUniqueExceptionsString();
            String excSample = graph.getExceptionRange(sucSample, blockSample).getUniqueExceptionsString();

            // FIXME: compare handlers if possible
            boolean equalexc = excCatch == null ? excSample == null : excCatch.equals(excSample);

            if (equalexc) {
              if (catchBlocks.contains(sucCatch) && !setSample.contains(sucSample)) {

                List<int[]> lst = entry.lstStoreVars;

                if (sucCatch.getSeq().length() > 0 && sucSample.getSeq().length() > 0) {
                  Instruction instrCatch = sucCatch.getSeq().getInstr(0);
                  Instruction instrSample = sucSample.getSeq().getInstr(0);

                  if (instrCatch.opcode == CodeConstants.opc_astore &&
                      instrSample.opcode == CodeConstants.opc_astore) {
                    lst = new ArrayList<int[]>(lst);
                    lst.add(new int[]{instrCatch.getOperand(0), instrSample.getOperand(0)});
                  }
                }

                stack.add(new BlockStackEntry(sucCatch, sucSample, lst));
              }
            }
            else {
              return null;
            }
          }
        }
        else {
          return null;
        }
      }

      if (isLastBlock) {
        Set<BasicBlock> setSuccs = new HashSet<BasicBlock>(blockSample.getSuccs());
        setSuccs.removeAll(setSample);

        for (BlockStackEntry stackent : stack) {
          setSuccs.remove(stackent.blockSample);
        }

        for (BasicBlock succ : setSuccs) {
          if (graph.getLast() != succ) { // FIXME: why?
            mapNext.put(blockSample.id + "#" + succ.id, new BasicBlock[]{blockSample, succ, isTrueLastBlock ? succ : null});
          }
        }
      }
    }

    return new Area(startSample, setSample, getUniqueNext(graph, new HashSet<BasicBlock[]>(mapNext.values())));
  }

  private static BasicBlock getUniqueNext(ControlFlowGraph graph, Set<BasicBlock[]> setNext) {

    // precondition: there is at most one true exit path in a finally statement

    BasicBlock next = null;
    boolean multiple = false;

    for (BasicBlock[] arr : setNext) {

      if (arr[2] != null) {
        next = arr[1];
        multiple = false;
        break;
      }
      else {
        if (next == null) {
          next = arr[1];
        }
        else if (next != arr[1]) {
          multiple = true;
        }

        if (arr[1].getPreds().size() == 1) {
          next = arr[1];
        }
      }
    }

    if (multiple) { // TODO: generic solution
      for (BasicBlock[] arr : setNext) {
        BasicBlock block = arr[1];

        if (block != next) {
          if (InterpreterUtil.equalSets(next.getSuccs(), block.getSuccs())) {
            InstructionSequence seqNext = next.getSeq();
            InstructionSequence seqBlock = block.getSeq();

            if (seqNext.length() == seqBlock.length()) {
              for (int i = 0; i < seqNext.length(); i++) {
                Instruction instrNext = seqNext.getInstr(i);
                Instruction instrBlock = seqBlock.getInstr(i);

                if (instrNext.opcode != instrBlock.opcode || instrNext.wide != instrBlock.wide
                    || instrNext.operandsCount() != instrBlock.operandsCount()) {
                  return null;
                }

                for (int j = 0; j < instrNext.getOperands().length; j++) {
                  if (instrNext.getOperand(j) != instrBlock.getOperand(j)) {
                    return null;
                  }
                }
              }
            }
            else {
              return null;
            }
          }
          else {
            return null;
          }
        }
      }

      //			try {
      //				DotExporter.toDotFile(graph, new File("c:\\Temp\\fern5.dot"), true);
      //			} catch(IOException ex) {
      //				ex.printStackTrace();
      //			}

      for (BasicBlock[] arr : setNext) {
        if (arr[1] != next) {
          // FIXME: exception edge possible?
          arr[0].removeSuccessor(arr[1]);
          arr[0].addSuccessor(next);
        }
      }

      DeadCodeHelper.removeDeadBlocks(graph);
    }

    return next;
  }

  private boolean compareBasicBlocksEx(ControlFlowGraph graph,
                                       BasicBlock pattern,
                                       BasicBlock sample,
                                       int type,
                                       int finallytype,
                                       List<int[]> lstStoreVars) {

    InstructionSequence seqPattern = pattern.getSeq();
    InstructionSequence seqSample = sample.getSeq();

    if (type != 0) {
      seqPattern = seqPattern.clone();

      if ((type & 1) > 0) { // first
        if (finallytype > 0) {
          seqPattern.removeInstruction(0);
        }
      }

      if ((type & 2) > 0) { // last
        if (finallytype == 0 || finallytype == 2) {
          seqPattern.removeInstruction(seqPattern.length() - 1);
        }

        if (finallytype == 2) {
          seqPattern.removeInstruction(seqPattern.length() - 1);
        }
      }
    }

    if (seqPattern.length() > seqSample.length()) {
      return false;
    }

    for (int i = 0; i < seqPattern.length(); i++) {
      Instruction instrPattern = seqPattern.getInstr(i);
      Instruction instrSample = seqSample.getInstr(i);

      // compare instructions with respect to jumps
      if (!equalInstructions(instrPattern, instrSample, lstStoreVars)) {
        return false;
      }
    }

    if (seqPattern.length() < seqSample.length()) { // split in two blocks

      SimpleInstructionSequence seq = new SimpleInstructionSequence();
      for (int i = seqSample.length() - 1; i >= seqPattern.length(); i--) {
        seq.addInstruction(0, seqSample.getInstr(i), -1);
        seqSample.removeInstruction(i);
      }

      BasicBlock newblock = new BasicBlock(++graph.last_id);
      newblock.setSeq(seq);

      List<BasicBlock> lstTemp = new ArrayList<BasicBlock>();
      lstTemp.addAll(sample.getSuccs());

      // move successors
      for (BasicBlock suc : lstTemp) {
        sample.removeSuccessor(suc);
        newblock.addSuccessor(suc);
      }

      sample.addSuccessor(newblock);

      graph.getBlocks().addWithKey(newblock, newblock.id);

      Set<BasicBlock> setFinallyExits = graph.getFinallyExits();
      if (setFinallyExits.contains(sample)) {
        setFinallyExits.remove(sample);
        setFinallyExits.add(newblock);
      }

      // copy exception edges and extend protected ranges
      for (int j = 0; j < sample.getSuccExceptions().size(); j++) {
        BasicBlock hd = sample.getSuccExceptions().get(j);
        newblock.addSuccessorException(hd);

        ExceptionRangeCFG range = graph.getExceptionRange(hd, sample);
        range.getProtectedRange().add(newblock);
      }
    }

    return true;
  }

  public boolean equalInstructions(Instruction first, Instruction second, List<int[]> lstStoreVars) {
    if (first.opcode != second.opcode || first.wide != second.wide
        || first.operandsCount() != second.operandsCount()) {
      return false;
    }

    if (first.group != CodeConstants.GROUP_JUMP && first.getOperands() != null) { // FIXME: switch comparison
      for (int i = 0; i < first.getOperands().length; i++) {

        int firstOp = first.getOperand(i);
        int secondOp = second.getOperand(i);

        if (firstOp != secondOp) {

          // a-load/store instructions
          if (first.opcode == CodeConstants.opc_aload || first.opcode == CodeConstants.opc_astore) {
            for (int[] arr : lstStoreVars) {
              if (arr[0] == firstOp && arr[1] == secondOp) {
                return true;
              }
            }
          }

          return false;
        }
      }
    }

    return true;
  }

  private static void deleteArea(ControlFlowGraph graph, Area area) {

    BasicBlock start = area.start;
    BasicBlock next = area.next;

    if (start == next) {
      return;
    }

    if (next == null) {
      // dummy exit block
      next = graph.getLast();
    }

    // collect common exception ranges of predecessors and successors
    Set<BasicBlock> setCommonExceptionHandlers = new HashSet<BasicBlock>(next.getSuccExceptions());
    for (BasicBlock pred : start.getPreds()) {
      setCommonExceptionHandlers.retainAll(pred.getSuccExceptions());
    }

    boolean is_outside_range = false;

    Set<BasicBlock> setPredecessors = new HashSet<BasicBlock>(start.getPreds());

    // replace start with next
    for (BasicBlock pred : setPredecessors) {
      pred.replaceSuccessor(start, next);
    }

    Set<BasicBlock> setBlocks = area.sample;

    Set<ExceptionRangeCFG> setCommonRemovedExceptionRanges = null;

    // remove all the blocks inbetween
    for (BasicBlock block : setBlocks) {

      // artificial basic blocks (those resulted from splitting)
      // can belong to more than one area
      if (graph.getBlocks().containsKey(block.id)) {

        if (!block.getSuccExceptions().containsAll(setCommonExceptionHandlers)) {
          is_outside_range = true;
        }

        Set<ExceptionRangeCFG> setRemovedExceptionRanges = new HashSet<ExceptionRangeCFG>();
        for (BasicBlock handler : block.getSuccExceptions()) {
          setRemovedExceptionRanges.add(graph.getExceptionRange(handler, block));
        }

        if (setCommonRemovedExceptionRanges == null) {
          setCommonRemovedExceptionRanges = setRemovedExceptionRanges;
        }
        else {
          setCommonRemovedExceptionRanges.retainAll(setRemovedExceptionRanges);
        }

        // shift extern edges on splitted blocks
        if (block.getSeq().isEmpty() && block.getSuccs().size() == 1) {
          BasicBlock succs = block.getSuccs().get(0);
          for (BasicBlock pred : new ArrayList<BasicBlock>(block.getPreds())) {
            if (!setBlocks.contains(pred)) {
              pred.replaceSuccessor(block, succs);
            }
          }

          if (graph.getFirst() == block) {
            graph.setFirst(succs);
          }
        }

        graph.removeBlock(block);
      }
    }

    if (is_outside_range) {

      // new empty block
      BasicBlock emptyblock = new BasicBlock(++graph.last_id);
      emptyblock.setSeq(new SimpleInstructionSequence());
      graph.getBlocks().addWithKey(emptyblock, emptyblock.id);

      // add to ranges if necessary
      if (setCommonRemovedExceptionRanges != null) {
        for (ExceptionRangeCFG range : setCommonRemovedExceptionRanges) {
          emptyblock.addSuccessorException(range.getHandler());
          range.getProtectedRange().add(emptyblock);
        }
      }

      // insert between predecessors and next
      emptyblock.addSuccessor(next);
      for (BasicBlock pred : setPredecessors) {
        pred.replaceSuccessor(next, emptyblock);
      }
    }
  }

  private static void removeExceptionInstructionsEx(BasicBlock block, int blocktype, int finallytype) {

    InstructionSequence seq = block.getSeq();

    if (finallytype == 3) { // empty finally handler
      for (int i = seq.length() - 1; i >= 0; i--) {
        seq.removeInstruction(i);
      }
    }
    else {
      if ((blocktype & 1) > 0) { // first
        if (finallytype == 2 || finallytype == 1) { // astore or pop
          seq.removeInstruction(0);
        }
      }

      if ((blocktype & 2) > 0) { // last
        if (finallytype == 2 || finallytype == 0) {
          seq.removeInstruction(seq.length() - 1);
        }

        if (finallytype == 2) { // astore
          seq.removeInstruction(seq.length() - 1);
        }
      }
    }
  }
}