content: /*
   * Copyright 2016 HuntBugs contributors
   * 
   * 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 one.util.huntbugs.flow;
  
  import java.util.ArrayList;
  import java.util.Arrays;
  import java.util.Collection;
  import java.util.Collections;
  import java.util.HashMap;
  import java.util.HashSet;
  import java.util.LinkedHashMap;
  import java.util.List;
  import java.util.Map;
  import java.util.Map.Entry;
  import java.util.Objects;
  import java.util.Set;
  import java.util.function.BiConsumer;
  import java.util.function.BiFunction;
  import java.util.function.Function;
  import java.util.stream.Collectors;
  import java.util.stream.Stream;
  
  import com.strobel.assembler.metadata.FieldReference;
  import com.strobel.assembler.metadata.MethodDefinition;
  import com.strobel.assembler.metadata.MethodReference;
  import com.strobel.assembler.metadata.TypeDefinition;
  import com.strobel.assembler.metadata.TypeReference;
  import com.strobel.decompiler.ast.AstCode;
  import com.strobel.decompiler.ast.Block;
  import com.strobel.decompiler.ast.CaseBlock;
  import com.strobel.decompiler.ast.CatchBlock;
  import com.strobel.decompiler.ast.Condition;
  import com.strobel.decompiler.ast.Expression;
  import com.strobel.decompiler.ast.Label;
  import com.strobel.decompiler.ast.Lambda;
  import com.strobel.decompiler.ast.Loop;
  import com.strobel.decompiler.ast.LoopType;
  import com.strobel.decompiler.ast.Node;
  import com.strobel.decompiler.ast.Switch;
  import com.strobel.decompiler.ast.TryCatchBlock;
  import com.strobel.decompiler.ast.Variable;
  
  import one.util.huntbugs.warning.WarningAnnotation.MemberInfo;
  import one.util.huntbugs.util.Exprs;
  import one.util.huntbugs.util.Nodes;
  import one.util.huntbugs.util.Types;
  
  /**
   * @author Tagir Valeev
   *
   */
  public class CFG {
      private static final int BLOCKTYPE_UNKNOWN = -1;
      private static final int BLOCKTYPE_EXIT = -2;
      private static final int BLOCKTYPE_FAIL = -3;
      private static final int BLOCKTYPE_IMPLICIT = -4;
  
      static final TypeDefinition throwable = Types.lookupJdkType("java/lang/Throwable");
      static final TypeDefinition exception = Types.lookupJdkType("java/lang/Exception");
      static final TypeDefinition runtimeException = Types.lookupJdkType("java/lang/RuntimeException");
      static final TypeDefinition classCastException = Types.lookupJdkType("java/lang/ClassCastException");
      static final TypeDefinition nullPointerException = Types.lookupJdkType("java/lang/NullPointerException");
      static final TypeDefinition arrayIndexOutOfBoundsException = Types.lookupJdkType("java/lang/ArrayIndexOutOfBoundsException");
      static final TypeDefinition arrayStoreException = Types.lookupJdkType("java/lang/ArrayStoreException");
      static final TypeDefinition outOfMemoryError = Types.lookupJdkType("java/lang/OutOfMemoryError");
      static final TypeDefinition linkageError = Types.lookupJdkType("java/lang/LinkageError");
      static final TypeDefinition error = Types.lookupJdkType("java/lang/Error");
  
      final List<BasicBlock> blocks = new ArrayList<>();
      final Map<Lambda, CFG> lambdas = new HashMap<>();
      final BasicBlock closure;
      final MethodDefinition md;
      final Block body;
      final BasicBlock entry, exit = new BasicBlock(BLOCKTYPE_EXIT), fail = new BasicBlock(BLOCKTYPE_FAIL), implicit = new BasicBlock(BLOCKTYPE_IMPLICIT);
      final Map<Label, BasicBlock> labelTargets = new HashMap<>();
      final List<List<BasicBlock>> dupExpr;
      // Number of block till which CFG is forward-only
      final int forwardTill;
      final boolean hasUnreachable;
  
      private CFG(MethodDefinition md, BasicBlock closure, Block methodBody) {
          this.md = md;
          this.body = methodBody;
          this.closure = closure;
          if (methodBody.getBody().isEmpty()) {
              entry = exit;
              hasUnreachable = false;
              dupExpr = Collections.emptyList();
          } else {
              entry = new BasicBlock();
              buildBlock(entry, exit, new OuterJumpContext(), methodBody);
              verify();
              inlineBooleans();
              fixBlocks();
              dupExpr = computeDupBlocks(findDuplicates(methodBody));
              hasUnreachable = blocks.stream().anyMatch(bb -> !bb.reached);
          }
          this.forwardTill = computeForwardTill();
      }
      
      private TrueFalse<List<BasicBlock>> getConditionalBranches(BasicBlock cond) {
          int trueStart = cond.trueTarget.id;
          int falseStart = cond.falseTarget.id;
          if(trueStart == BLOCKTYPE_EXIT)
              trueStart = blocks.size();
          if(falseStart == BLOCKTYPE_EXIT)
              falseStart = blocks.size();
          if(trueStart < cond.id || falseStart < cond.id)
              return null;
          Integer START = 0;
          Integer TRUE = 1;
          Integer FALSE = 2;
          Integer BOTH = 3;
          graphSearch(new GraphSearch<Integer>() {
              @Override
              public Integer markStart(Expression expr, boolean isEntry) {
                  return expr == cond.expr ? START : null;
              }
  
              @Override
              public Integer transfer(Integer orig, Expression from, EdgeType edge, Expression to) {
                  if(orig == START) {
                      if(edge == EdgeType.TRUE)
                          return TRUE;
                      if(edge == EdgeType.FALSE)
                          return FALSE;
                      return BOTH;
                  }
                  return orig;
              }
  
              @Override
              public Integer merge(Integer f1, Integer f2) {
                  if(f1 == null)
                      return f2;
                  if(f2 == null)
                      return f1;
                  return BOTH;
              }
          });
          List<BasicBlock> trueBlocks = null;
          List<BasicBlock> falseBlocks = null;
          int trueEnd = -1, falseEnd = -1;
          for(BasicBlock bb : blocks) {
              Integer state = (Integer) bb.state;
              if(state == null)
                  continue;
              if(trueEnd != -1 && trueBlocks == null && state != TRUE) {
                  trueBlocks = blocks.subList(trueStart, trueEnd+1);
              }
              if(falseEnd != -1 && falseBlocks == null && state != FALSE) {
                  falseBlocks = blocks.subList(falseStart, falseEnd+1);
              }
              if(state == TRUE) {
                  if(bb.id < trueStart || trueBlocks != null)
                      return null;
                  trueEnd = bb.id;
              }
              if(state == FALSE) {
                  if(bb.id < falseStart || falseBlocks != null)
                      return null;
                  falseEnd = bb.id;
              }
          }
          if(trueEnd != -1 && trueBlocks == null) {
              trueBlocks = blocks.subList(trueStart, blocks.size());
          }
          if(falseEnd != -1 && falseBlocks == null) {
              falseBlocks = blocks.subList(falseStart, blocks.size());
          }
          if(trueBlocks == null && falseBlocks == null) {
              return null;
          }
          if(trueBlocks == null) {
              trueBlocks = Collections.emptyList();
          }
          if(falseBlocks == null) {
              falseBlocks = Collections.emptyList();
          }
          return new TrueFalse<>(trueBlocks, falseBlocks);
      }
  
      private void inlineBooleans() {
          boolean changed = true;
          while(changed) {
              changed = false;
              for (BasicBlock bb : blocks) {
                  if (bb.trueTarget == null)
                      continue;
                  BasicBlock load = bb;
                  boolean invert = false;
                  while (load.expr.getCode() == AstCode.LogicalNot) {
                      load = blocks.get(load.id - 1);
                      invert = !invert;
                  }
                  if (load.expr.getCode() != AstCode.Load)
                      continue;
                  TrueFalse<List<BasicBlock>> branches = getConditionalBranches(bb);
                  if (branches == null)
                      continue;
                  Variable var = (Variable) load.expr.getOperand();
                  if(var.getOriginalParameter() != null)
                      continue;
                  List<BasicBlock> stores = blocks.stream().filter(s -> s.expr.getCode() == AstCode.Store && var.equals(s.expr
                          .getOperand())).collect(Collectors.toList());
                  if (stores.size() != 1)
                      continue;
                  BasicBlock store = stores.get(0);
                  BasicBlock cond = blocks.get(store.id-1);
                  int copyStart = store.id + 1;
                  int copyEnd = load.id;
                  int domStart = -1;
                  if(!branches.trueState.isEmpty()) {
                      domStart = branches.trueState.get(branches.trueState.size()-1).id+1;
                  }
                  if(!branches.falseState.isEmpty()) {
                      domStart = Math.max(domStart, branches.falseState.get(branches.falseState.size()-1).id+1);
                  }
                  if(copyEnd < copyStart || domStart == -1)
                      continue;
                  List<BasicBlock> falseCopy = copyBlocks(copyStart, copyEnd);
                  if(falseCopy == null)
                      continue;
                  List<BasicBlock> trueCopy = blocks.subList(copyStart, copyEnd);
                  List<BasicBlock> newBlocks = new ArrayList<>();
                  newBlocks.addAll(blocks.subList(0, cond.id+1));
                  BasicBlock storeTrue = new BasicBlock(true, new Expression(AstCode.Store, var, -1, new Expression(AstCode.LdC, Boolean.TRUE, -1)));
                  BasicBlock storeFalse = new BasicBlock(true, new Expression(AstCode.Store, var, -1, new Expression(AstCode.LdC, Boolean.FALSE, -1)));
                  cond.passTarget = null;
                  cond.trueTarget = storeTrue;
                  cond.falseTarget = storeFalse;
                  List<BasicBlock> dom = blocks.subList(domStart, blocks.size());
                  BasicBlock domTarget = dom.isEmpty() ? exit : dom.get(0);
                  BasicBlock trueTarget = branches.trueState.isEmpty() ? domTarget : branches.trueState.get(0);
                  if(!trueCopy.isEmpty())
                      trueTarget = trueCopy.get(0);
                  BasicBlock falseTarget = branches.falseState.isEmpty() ? domTarget : branches.falseState.get(0);
                  if(!falseCopy.isEmpty())
                      falseTarget = falseCopy.get(0);
                  newBlocks.add(storeTrue);
                  if(invert) {
                      storeTrue.addTarget(EdgeType.PASS, falseTarget);
                      newBlocks.addAll(falseCopy);
                      newBlocks.addAll(branches.falseState);
                      newBlocks.add(storeFalse);
                      storeFalse.addTarget(EdgeType.PASS, trueTarget);
                      newBlocks.addAll(trueCopy);
                      newBlocks.addAll(branches.trueState);
                  } else {
                      storeTrue.addTarget(EdgeType.PASS, trueTarget);
                      newBlocks.addAll(trueCopy);
                      newBlocks.addAll(branches.trueState);
                      newBlocks.add(storeFalse);
                      storeFalse.addTarget(EdgeType.PASS, falseTarget);
                      newBlocks.addAll(falseCopy);
                      newBlocks.addAll(branches.falseState);
                  }
                  newBlocks.addAll(dom);
                  blocks.clear();
                  blocks.addAll(newBlocks);
                  renumBlocks();
                  verify();
                  changed = true;
                  break;
              }
          }
      }
      
      private List<BasicBlock> copyBlocks(int copyStart, int copyEnd) {
          if(copyStart==copyEnd)
              return Collections.emptyList();
          // TODO
          return null;
      }
  
      private void renumBlocks() {
          for(int i=0; i<blocks.size(); i++) {
              blocks.get(i).id = i;
          }
      }
  
      private List<List<BasicBlock>> computeDupBlocks(Collection<Set<Expression>> dupExpr) {
          return dupExpr.stream().map(dupSet -> blocks.stream().filter(bb -> dupSet.contains(bb.expr)).collect(Collectors
                  .toList())).collect(Collectors.toList());
      }
  
      private Collection<Set<Expression>> findDuplicates(Block methodBody) {
          Map<List<?>, Set<Expression>> result = new HashMap<>();
          Annotator.forExpressions(methodBody, e -> Exprs.stream(e).filter(expr -> expr.getOffset() > 0).forEach(
              expr -> result.computeIfAbsent(Arrays.asList(expr.getOffset(), expr.getCode(), expr.getArguments().size(), expr.getOperand()),
                  k -> new HashSet<>()).add(expr)));
          result.values().removeIf(set -> set.size() < 2);
          return result.values();
      }
  
      private void verify() {
          for (BasicBlock bb : blocks) {
              if (bb.trueTarget == null ^ bb.falseTarget == null) {
                  throw new IllegalStateException("Mismatch true/false targets CFG at [" + bb.getId() + "]: " + this);
              }
              if (bb.targets().anyMatch(target -> target.id == -1)) {
                  throw new IllegalStateException("Not linked target block at [" + bb.getId() + "]: " + this);
              }
              if (bb.targets().anyMatch(target -> target.id >= 0 && blocks.get(target.id) != target)) {
                  throw new IllegalStateException("Missing target block at [" + bb.getId() + "]: " + this);
              }
              if (bb.reached && bb.targets().anyMatch(target -> !target.reached)) {
                  throw new IllegalStateException("Invalid flow control at [" + bb.getId() + "]: " + this);
              }
          }
      }
  
      private void fixBlocks() {
          entry.reached = true;
          for (BasicBlock bb : blocks) {
              while (bb.falseTarget != null && bb.falseTarget.expr != null && bb.falseTarget.expr
                      .getCode() == AstCode.LogicalAnd)
                  bb.falseTarget = bb.falseTarget.falseOrPass();
              while (bb.trueTarget != null && bb.trueTarget.expr != null && bb.trueTarget.expr
                      .getCode() == AstCode.LogicalOr)
                  bb.trueTarget = bb.trueTarget.trueOrPass();
              if(bb.synthetic) {
                  Expression expr = bb.expr;
                  if(expr.getCode() == AstCode.Store) {
                      Variable var = (Variable) expr.getOperand();
                      Expression arg = expr.getArguments().get(0);
                      if(arg.getCode() == AstCode.LdC && arg.getOperand() instanceof Boolean) {
                          boolean val = (boolean) arg.getOperand();
                          while(true) {
                              BasicBlock target = bb.passTarget;
                              if(target == null)
                                  break;
                              Expression targetExpr = target.expr;
                              if(targetExpr == null)
                                  break;
                              boolean wanted;
                              if(targetExpr.getCode() == AstCode.LogicalAnd)
                                  wanted = false;
                              else if(targetExpr.getCode() == AstCode.LogicalOr)
                                  wanted = true;
                              else break;
                              Expression targetArg = targetExpr.getArguments().get(0);
                              while(targetArg.getCode() == AstCode.LogicalNot) {
                                  val = !val;
                                  targetArg = targetArg.getArguments().get(0);
                              }
                              if (wanted != val || targetArg.getCode() != AstCode.Load || !var.equals(targetArg.getOperand()))
                                  break;
                              bb.passTarget = wanted ? target.trueOrPass() : target.falseOrPass();
                          }
                      }
                  }
              }
              if (bb.reached)
                  bb.targets().forEach(t -> t.reached = true);
          }
      }
  
      private int computeForwardTill() {
          int forwardTill = blocks.size();
          for (BasicBlock bb : blocks) {
              int min = bb.targets().mapToInt(t -> t.id).filter(id -> id >= 0 && id < bb.id).min().orElse(forwardTill);
              if (min < forwardTill)
                  forwardTill = min;
          }
          return forwardTill;
      }
  
      private void buildBlock(BasicBlock entry, BasicBlock exit, JumpContext jc, Block block) {
          BasicBlock curBlock = entry;
          BasicBlock nextBlock = null;
          Node prevNode = null;
          List<Node> body = block.getBody();
          if (body.isEmpty()) {
              throw new IllegalStateException("Empty body is supplied!");
          }
          if (body.size() == 1 && body.get(0) instanceof Label) {
              buildSingleLabel(entry, exit, (Label) body.get(0));
              return;
          }
          Set<Label> labels = new HashSet<>();
          for (Node node : body) {
              if (node instanceof Label) {
                  labels.add((Label) node);
              }
          }
          if (!labels.isEmpty()) {
              jc = new LabelJumpContext(jc, labels);
          }
          Node last = body.get(body.size() - 1);
          if (last instanceof Label && labelTargets.put((Label) last, exit) != null) {
              throw new IllegalStateException("Label " + last + " is already linked");
          }
          for (Node node : body) {
              if (node instanceof Label) {
                  Label label = (Label) node;
                  if (prevNode == null) {
                      BasicBlock oldTarget = labelTargets.putIfAbsent(label, entry);
                      if (oldTarget != null && oldTarget != entry) {
                          oldTarget.setExpression(new Expression(AstCode.Goto, label, -1));
                          oldTarget.addTarget(EdgeType.PASS, entry);
                          register(oldTarget);
                      }
                  } else {
                      nextBlock = labelTargets.computeIfAbsent(label, k -> new BasicBlock());
                  }
                  continue;
              }
              if (nextBlock == null)
                  nextBlock = new BasicBlock();
              if (prevNode != null) {
                  buildNode(curBlock, nextBlock, jc, prevNode);
                  curBlock = nextBlock;
                  nextBlock = null;
              }
              prevNode = node;
          }
          if (prevNode != null) {
              buildNode(curBlock, exit, jc, prevNode);
          }
      }
  
      private void buildSingleLabel(BasicBlock entry, BasicBlock exit, Label label) {
          BasicBlock oldTarget = labelTargets.putIfAbsent(label, entry);
          if (oldTarget != null && oldTarget != entry) {
              oldTarget.setExpression(new Expression(AstCode.Goto, label, -1));
              oldTarget.addTarget(EdgeType.PASS, entry);
              register(oldTarget);
          }
          entry.setExpression(new Expression(AstCode.Goto, label, -1));
          entry.addTarget(EdgeType.PASS, exit);
          register(entry);
          return;
      }
  
      private void buildNode(final BasicBlock curBlock, BasicBlock nextBlock, JumpContext jc, Node node) {
          if (node instanceof Expression) {
              BasicBlock lastBlock = buildExpr(curBlock, (Expression) node, jc);
              if (lastBlock != null)
                  lastBlock.addTarget(EdgeType.PASS, nextBlock);
          } else if (node instanceof Condition) {
              buildCondition(curBlock, nextBlock, jc, (Condition) node);
          } else if (node instanceof Loop) {
              buildLoop(curBlock, nextBlock, jc, (Loop) node);
          } else if (node instanceof Switch) {
              buildSwitch(curBlock, nextBlock, jc, (Switch) node);
          } else if (node instanceof TryCatchBlock) {
              TryCatchBlock tryCatch = (TryCatchBlock) node;
              if (tryCatch.getFinallyBlock() == null || tryCatch.getFinallyBlock().getBody().isEmpty()) {
                  buildTryCatch(curBlock, nextBlock, jc, tryCatch);
              } else if (tryCatch.getTryBlock().getBody().isEmpty() && tryCatch.getCatchBlocks().isEmpty()) {
                  buildBlock(curBlock, nextBlock, jc, tryCatch.getFinallyBlock());
              } else {
                  buildFinally(curBlock, nextBlock, jc, tryCatch);
              }
          }
      }
  
      private void buildFinally(final BasicBlock curBlock, BasicBlock nextBlock, JumpContext jc, TryCatchBlock tryCatch) {
          BasicBlock finallyBlock = new BasicBlock();
          FinallyJumpContext fjc = new FinallyJumpContext(jc);
          buildTryCatch(curBlock, finallyBlock, fjc, tryCatch);
          if (blocks.stream().flatMap(BasicBlock::targets).anyMatch(finallyBlock::equals)) {
              buildBlock(finallyBlock, nextBlock, jc, tryCatch.getFinallyBlock());
          }
          fjc.targetEntries.forEach((target, entry) -> {
              buildBlock(entry, target, jc, tryCatch.getFinallyBlock());
          });
      }
  
      // Processes try-catch only, ignores finally, if any
      private void buildTryCatch(final BasicBlock curBlock, BasicBlock nextBlock, JumpContext jc,
              TryCatchBlock tryCatch) {
          if (!tryCatch.getCatchBlocks().isEmpty()) {
              CatchJumpContext cjc = new CatchJumpContext(jc, nextBlock, tryCatch.getCatchBlocks());
              buildBlock(curBlock, nextBlock, cjc, tryCatch.getTryBlock());
              for (CatchBlock cb : tryCatch.getCatchBlocks()) {
                  BasicBlock catchEntry = cjc.getEntry(cb);
                  if (catchEntry != nextBlock)
                      buildBlock(catchEntry, nextBlock, jc, cb);
              }
          } else {
              buildBlock(curBlock, nextBlock, jc, tryCatch.getTryBlock());
          }
      }
  
      private void buildSwitch(final BasicBlock curBlock, BasicBlock nextBlock, JumpContext jc, Switch switchBlock) {
          Expression condition = switchBlock.getCondition();
          BasicBlock condBlock = buildExpr(curBlock, condition, jc);
          jc = new SwitchJumpContext(jc, nextBlock);
          List<CaseBlock> caseBlocks = switchBlock.getCaseBlocks();
          BasicBlock finalCondBlock = nextBlock;
          Map<Integer, BasicBlock> targets = new LinkedHashMap<>();
          List<BasicBlock> blocks = new ArrayList<>();
          CaseBlock prevBlock = null;
          for (CaseBlock cb : caseBlocks) {
              BasicBlock curBB;
              if (prevBlock != null && prevBlock.isDefault() && prevBlock.getBody().isEmpty()) {
                  curBB = blocks.get(blocks.size() - 1);
              } else {
                  curBB = new BasicBlock();
              }
              blocks.add(curBB);
              if (cb.isDefault()) {
                  finalCondBlock = curBB;
              } else {
                  for (Integer val : cb.getValues()) {
                      targets.put(val, curBB);
                  }
              }
              if (!cb.getBody().isEmpty() && cb.getBody().get(0) instanceof Label) {
                  Label l = (Label) cb.getBody().get(0);
                  labelTargets.putIfAbsent(l, curBB);
              }
          }
          blocks.add(nextBlock);
          BasicBlock prevCondBlock = condBlock;
          for (Entry<Integer, BasicBlock> entry : targets.entrySet()) {
              Expression ldc = new Expression(AstCode.LdC, entry.getKey(), -1);
              Expression eq = new Expression(AstCode.CmpEq, null, -1, condition, ldc);
              BasicBlock curCondBlock = register(new BasicBlock(eq));
              prevCondBlock.addTarget(prevCondBlock == condBlock ? EdgeType.PASS : EdgeType.FALSE, curCondBlock);
              curCondBlock.addTarget(EdgeType.TRUE, entry.getValue());
              prevCondBlock = curCondBlock;
          }
          prevCondBlock.addTarget(prevCondBlock == condBlock ? EdgeType.PASS : EdgeType.FALSE, finalCondBlock);
          for (int i = 0; i < caseBlocks.size(); i++) {
              CaseBlock caseBlock = caseBlocks.get(i);
              BasicBlock caseBB = blocks.get(i);
              BasicBlock nextBB = blocks.get(i + 1);
              if (caseBlock.getBody().isEmpty()) {
                  // likely a procyon bug: seems that return is expected
                  buildNode(caseBB, nextBB, jc, new Expression(AstCode.Return, null, -1));
              } else {
                  buildBlock(caseBB, nextBB, jc, caseBlock);
              }
          }
      }
  
      private void buildLoop(final BasicBlock curBlock, BasicBlock nextBlock, JumpContext jc, Loop loop)
              throws InternalError {
          Expression condition = loop.getCondition();
          if (condition == null) {
              jc = new LoopJumpContext(jc, curBlock, nextBlock, curBlock);
              buildBlock(curBlock, curBlock, jc, loop.getBody());
          } else if (loop.getLoopType() == LoopType.PreCondition) {
              BasicBlock condExitBlock = buildExpr(curBlock, condition, jc);
              if (loop.getBody().getBody().isEmpty()) {
                  condExitBlock.addTarget(EdgeType.TRUE, curBlock);
                  condExitBlock.addTarget(EdgeType.FALSE, nextBlock);
              } else {
                  jc = new LoopJumpContext(jc, curBlock, nextBlock, curBlock);
                  BasicBlock bodyBlock = new BasicBlock();
                  condExitBlock.addTarget(EdgeType.TRUE, bodyBlock);
                  condExitBlock.addTarget(EdgeType.FALSE, nextBlock);
                  buildBlock(bodyBlock, curBlock, jc, loop.getBody());
              }
          } else if (loop.getLoopType() == LoopType.PostCondition) {
              if (loop.getBody().getBody().isEmpty())
                  throw new InternalError("Unexpected empty do-while loop");
              BasicBlock condEntryBlock = new BasicBlock();
              jc = new LoopJumpContext(jc, curBlock, nextBlock, condEntryBlock);
              buildBlock(curBlock, condEntryBlock, jc, loop.getBody());
              BasicBlock condExitBlock = buildExpr(condEntryBlock, condition, jc);
              condExitBlock.addTarget(EdgeType.TRUE, curBlock);
              condExitBlock.addTarget(EdgeType.FALSE, nextBlock);
          } else
              throw new InternalError("Unexpected loop type: " + loop.getLoopType());
      }
  
      private void buildCondition(final BasicBlock curBlock, BasicBlock nextBlock, JumpContext jc, Condition condition) {
          BasicBlock lastBlock = buildExpr(curBlock, condition.getCondition(), jc);
          if (!condition.getTrueBlock().getBody().isEmpty()) {
              BasicBlock leftBlock = new BasicBlock();
              lastBlock.addTarget(EdgeType.TRUE, leftBlock);
              buildBlock(leftBlock, nextBlock, jc, condition.getTrueBlock());
          } else {
              lastBlock.addTarget(EdgeType.TRUE, nextBlock);
          }
          if (!condition.getFalseBlock().getBody().isEmpty()) {
              BasicBlock rightBlock = new BasicBlock();
              lastBlock.addTarget(EdgeType.FALSE, rightBlock);
              buildBlock(rightBlock, nextBlock, jc, condition.getFalseBlock());
          } else {
              lastBlock.addTarget(EdgeType.FALSE, nextBlock);
          }
      }
  
      private BasicBlock buildExpr(BasicBlock entry, Expression expr, JumpContext jc) {
          switch (expr.getCode()) {
          case TernaryOp: {
              Expression cond = expr.getArguments().get(0);
              Expression left = expr.getArguments().get(1);
              Expression right = expr.getArguments().get(2);
              BasicBlock condBlock = buildExpr(entry, cond, jc);
              BasicBlock leftBlock = new BasicBlock();
              BasicBlock rightBlock = new BasicBlock();
              BasicBlock ternary = new BasicBlock(expr);
              condBlock.addTarget(EdgeType.TRUE, leftBlock);
              condBlock.addTarget(EdgeType.FALSE, rightBlock);
              buildExpr(leftBlock, left, jc).addTarget(EdgeType.PASS, ternary);
              buildExpr(rightBlock, right, jc).addTarget(EdgeType.PASS, ternary);
              return register(ternary);
          }
          case LogicalAnd: {
              Expression left = expr.getArguments().get(0);
              Expression right = expr.getArguments().get(1);
              BasicBlock rightBlock = new BasicBlock();
              BasicBlock and = new BasicBlock(expr);
              BasicBlock leftRes = buildExpr(entry, left, jc);
              leftRes.addTarget(EdgeType.TRUE, rightBlock);
              leftRes.addTarget(EdgeType.FALSE, and);
              BasicBlock rightRes = buildExpr(rightBlock, right, jc);
              rightRes.addTarget(EdgeType.TRUE, and);
              rightRes.addTarget(EdgeType.FALSE, and);
              return register(and);
          }
          case LogicalOr: {
              Expression left = expr.getArguments().get(0);
              Expression right = expr.getArguments().get(1);
              BasicBlock rightBlock = new BasicBlock();
              BasicBlock or = new BasicBlock(expr);
              BasicBlock leftBlock = buildExpr(entry, left, jc);
              leftBlock.addTarget(EdgeType.FALSE, rightBlock);
              leftBlock.addTarget(EdgeType.TRUE, or);
              BasicBlock rightRes = buildExpr(rightBlock, right, jc);
              rightRes.addTarget(EdgeType.TRUE, or);
              rightRes.addTarget(EdgeType.FALSE, or);
              return register(or);
          }
          default:
              break;
          }
          BasicBlock block = entry;
          for (Expression child : expr.getArguments()) {
              BasicBlock lastExpr = buildExpr(block, child, jc);
              block = new BasicBlock();
              lastExpr.addTarget(EdgeType.PASS, block);
          }
          block.setExpression(expr);
          register(block);
          if (expr.getOperand() instanceof Lambda) {
              Lambda lambda = (Lambda) expr.getOperand();
              CFG lambdaCFG = new CFG(Nodes.getLambdaMethod(lambda), block, lambda.getBody());
              lambdas.put(lambda, lambdaCFG);
          }
          switch (expr.getCode()) {
          case AThrow: {
              TypeReference exc = expr.getInferredType();
              if (exc == null)
                  exc = expr.getExpectedType();
              if (exc == null)
                  exc = throwable;
              jc.addExceptional(block, exc);
              return null;
          }
          case CheckCast:
              jc.addExceptional(block, classCastException);
              jc.addExceptional(block, linkageError);
              break;
          case InstanceOf:
              jc.addExceptional(block, linkageError);
              break;
          case Goto:
              jc.addJump(block, (Label) expr.getOperand());
              return null;
          case LoopContinue:
              jc.addContinue(block, (Label) expr.getOperand());
              return null;
          case LoopOrSwitchBreak:
              jc.addBreak(block, (Label) expr.getOperand());
              return null;
          case Return:
              jc.addReturn(block);
              return null;
          case ArrayLength:
              jc.addExceptional(block, nullPointerException);
              break;
          case Bind:
          case InvokeDynamic:
              jc.addExceptional(block, error);
              jc.addExceptional(block, runtimeException);
              break;
          case InitObject:
          case InvokeInterface:
          case InvokeSpecial:
          case InvokeStatic:
          case InvokeVirtual: {
              MethodReference mr = (MethodReference) expr.getOperand();
              if(mr.getName().equals("exit") && Types.is(mr.getDeclaringType(), System.class)) {
                  block.addTarget(EdgeType.PASS, implicit);
                  return null;
              }
              jc.addExceptional(block, error);
              jc.addExceptional(block, runtimeException);
              MethodDefinition md = mr.resolve();
              if (md != null) {
                  for (TypeReference thrownType : md.getThrownTypes()) {
                      jc.addExceptional(block, thrownType);
                  }
              } else {
                  jc.addExceptional(block, exception);
              }
              break;
          }
          case LoadElement:
              jc.addExceptional(block, arrayIndexOutOfBoundsException);
              jc.addExceptional(block, nullPointerException);
              break;
          case StoreElement:
              jc.addExceptional(block, arrayIndexOutOfBoundsException);
              jc.addExceptional(block, arrayStoreException);
              jc.addExceptional(block, nullPointerException);
              break;
          case __New:
          case NewArray:
          case InitArray:
          case MultiANewArray:
              jc.addExceptional(block, outOfMemoryError);
              break;
          case PutStatic:
          case GetStatic: {
              FieldReference fr = ((FieldReference) expr.getOperand());
              if (!fr.getDeclaringType().isEquivalentTo(md.getDeclaringType()))
                  jc.addExceptional(block, linkageError);
              break;
          }
          case PutField:
          case GetField: {
              if (md.isStatic() || !Exprs.isThis(expr.getArguments().get(0))) {
                  jc.addExceptional(block, nullPointerException);
                  jc.addExceptional(block, linkageError);
              }
              break;
          }
          default:
          }
          return block;
      }
  
      private BasicBlock register(BasicBlock block) {
          block.setId(blocks.size());
          blocks.add(block);
          return block;
      }
  
      @Override
      public String toString() {
          StringBuilder sb = new StringBuilder("CFG for ").append(new MemberInfo(md)).append("\n");
          for (BasicBlock bb : blocks)
              sb.append(bb);
          return sb.toString();
      }
  
      public static CFG build(MethodDefinition md, Block body) {
          try {
              return new CFG(md, null, body);
          } catch (Exception e) {
              throw new RuntimeException("Unable to build CFG for " + new MemberInfo(md) + "\n" + body, e);
          }
      }
  
      public <STATE, FACT> boolean runDFA(Annotator<FACT> annotator,
              BiFunction<MethodDefinition, STATE, Dataflow<FACT, STATE>> dfFactory, int maxIter) {
          @SuppressWarnings("unchecked")
          STATE closureState = closure == null ? null : (STATE) closure.state;
          boolean valid = new DFARunner<>(annotator, dfFactory.apply(md, closureState)).run(maxIter);
          for (CFG subCFG : lambdas.values()) {
              valid &= subCFG.runDFA(annotator, dfFactory, maxIter);
          }
          return valid;
      }
  
      public void forBodies(BiConsumer<MethodDefinition, Block> consumer) {
          consumer.accept(md, body);
          lambdas.values().forEach(cfg -> cfg.forBodies(consumer));
      }
  
      public CFG getLambdaCFG(Lambda lambda) {
          return lambdas.get(lambda);
      }
      
      private boolean isReachable(BasicBlock from, BasicBlock to) {
          clearChanged();
          boolean[] changed = { true };
          from.changed = true;
          while (changed[0]) {
              changed[0] = false;
              for (BasicBlock bb : blocks) {
                  if (bb.changed) {
                      bb.targets().filter(t -> !t.changed).forEach(t -> {
                          t.changed = changed[0] = true;
                      });
                  }
              }
              if (to.changed)
                  return true;
          }
          return to.changed;
      }
      
      private boolean isAlwaysReachable(BasicBlock from, Set<BasicBlock> targets) {
          clearChanged();
          boolean[] changed = { true };
          from.changed = true;
          while (changed[0]) {
              changed[0] = false;
              for (BasicBlock bb : blocks) {
                  if (targets.contains(bb))
                      continue;
                  if (bb.changed) {
                      // Explicit throw
                      if(bb.passTarget == null && bb.trueTarget == null &&
                              bb.targets().anyMatch(fail::equals))
                          return false;
                      bb.targets().filter(t -> !t.changed).forEach(t -> {
                          t.changed = changed[0] = true;
                      });
                  }
              }
              if (exit.changed || implicit.changed)
                  return false;
          }
          return true;
      }
      
      private <T> boolean updateState(GraphSearch<T> gs, BasicBlock bb, T newState) {
          @SuppressWarnings("unchecked")
          T oldState = (T) bb.state;
          if(Objects.equals(oldState, newState))
              return false;
          newState = gs.merge(oldState, newState);
          if(Objects.equals(oldState, newState))
              return false;
          bb.state = newState;
          return bb.changed = true;
      }
  
      /**
       * Result works only until new graph-search is performed.
       * Must not be called during DFA run on the same CFG.
       */
      public <T> SearchResult<T> graphSearch(GraphSearch<T> gs) {
          clearChanged();
          for(BasicBlock bb : blocks) {
              bb.state = gs.markStart(bb.expr, bb == entry);
              if(bb.state != null)
                  bb.changed = true;
          }
          exit.state = fail.state = implicit.state = null;
          boolean changed = true;
          while(changed) {
              changed = false;
              for(BasicBlock bb : blocks) {
                  if(bb.changed) {
                      bb.changed = false;
                      @SuppressWarnings("unchecked")
                      T state = (T) bb.state;
                      if(bb.passTarget != null) {
                          changed |= updateState(gs, bb.passTarget, gs.transfer(state, bb.expr, EdgeType.PASS, bb.passTarget.expr));
                      } else if(bb.trueTarget != null) {
                          changed |= updateState(gs, bb.trueTarget, gs.transfer(state, bb.expr, EdgeType.TRUE, bb.trueTarget.expr));
                          changed |= updateState(gs, bb.falseTarget, gs.transfer(state, bb.expr, EdgeType.FALSE, bb.falseTarget.expr));
                      }
                      if(bb.failTargets != null) {
                          for(BasicBlock target : bb.failTargets)
                              changed |= updateState(gs, target, gs.transfer(state, bb.expr, EdgeType.FAIL, target.expr));
                      }
                  }
              }
              if(forwardTill == blocks.size())
                  break;
          }
          return new SearchResult<>(gs);
      }
      
      @SuppressWarnings("unchecked")
      public class SearchResult<T> {
          private final GraphSearch<T> gs;
  
          SearchResult(GraphSearch<T> gs) {
              this.gs = gs;
          }
          
          public T atExit() {
              return (T) exit.state;
          }
          
          public T atFail() {
              return (T) fail.state;
          }
          
          public T atImplicit() {
              return (T) implicit.state;
          }
          
          public T atExpression(Expression expr) {
              return blocksBy(expr).map(bb -> (T)bb.state).filter(Objects::nonNull).reduce(gs::merge).orElse(null);
          }
      }
      
      private Stream<BasicBlock> blocksBy(Expression expr) {
          return blocks.stream().filter(bb -> bb.expr == expr);
      }
      
      public boolean mayTerminateImplicitly(Expression expr) {
          return blocksBy(expr).anyMatch(bb -> isReachable(bb, implicit));
      }
  
      public boolean isReachable(Expression expr) {
          if (!hasUnreachable)
              return true;
          return blocksBy(expr).anyMatch(bb -> bb.reached);
      }
      
      public boolean isAlwaysReachable(Expression from, Expression to) {
          Set<BasicBlock> targets = blocksBy(to).collect(Collectors.toSet());
          return blocksBy(from).allMatch(bb -> isAlwaysReachable(bb, targets));
      }
  
      public CodeBlock findDeadCode(Expression expr, EdgeType deadEdge) {
          Set<BasicBlock> targetBlocks = blocksBy(expr).collect(Collectors.toSet());
          if (targetBlocks.isEmpty())
              return null;
          if (deadEdge == EdgeType.TRUE || deadEdge == EdgeType.FALSE) {
              if (targetBlocks.stream().allMatch(bb -> bb.trueTarget == null && bb.passTarget != null)) {
                  targetBlocks = targetBlocks.stream().map(bb -> bb.passTarget).collect(Collectors.toSet());
                  if (!targetBlocks.stream().allMatch(bb -> bb.expr != null && bb.expr.getCode() == AstCode.LogicalNot))
                      return null;
                  deadEdge = deadEdge == EdgeType.TRUE ? EdgeType.FALSE : EdgeType.TRUE;
              }
          }
          clearChanged();
          boolean[] changed = { true };
          entry.changed = true;
          while (changed[0]) {
              changed[0] = false;
              for (BasicBlock bb : blocks) {
                  if (bb.changed) {
                      Stream<BasicBlock> targets = targetBlocks.contains(bb) ? bb.targetsExcept(deadEdge) : bb.targets();
                      targets.filter(t -> !t.changed).forEach(t -> {
                          t.changed = changed[0] = true;
                      });
                  }
              }
          }
          BasicBlock deadCodeEntry = null;
          Set<Expression> deadExpressions = new HashSet<>();
          for (BasicBlock bb : blocks) {
              if (!bb.changed && bb.reached) {
                  AstCode code = bb.expr.getCode();
                  if (code == AstCode.Goto || code == AstCode.LogicalAnd || code == AstCode.LogicalOr
                      || code == AstCode.LoopContinue || code == AstCode.LoopOrSwitchBreak)
                      continue;
                  deadExpressions.add(bb.expr);
                  if (deadCodeEntry == null) {
                      deadCodeEntry = bb;
                  }
              }
          }
          return deadCodeEntry == null ? null
                  : new CodeBlock(deadCodeEntry.expr, deadExpressions.size(), isExceptional(deadCodeEntry));
      }
      
      public boolean isInCFG(Expression expr) {
          return blocksBy(expr).findAny().isPresent();
      }
  
      private boolean isExceptional(BasicBlock start) {
          return !isReachable(start, exit);
      }
  
      void clearChanged() {
          for (BasicBlock bb : blocks) {
              bb.changed = false;
          }
          exit.changed = false;
          fail.changed = false;
          implicit.changed = false;
      }
  
      void initialize() {
          for (BasicBlock bb : blocks) {
              bb.state = null;
          }
          exit.state = null;
          fail.state = null;
          implicit.state = null;
      }
      
      class DFARunner<STATE, FACT> {
          private final Annotator<FACT> annotator;
          private final Dataflow<FACT, STATE> df;
          private boolean changed = false;
  
          DFARunner(Annotator<FACT> annotator, Dataflow<FACT, STATE> df) {
              this.df = df;
              this.annotator = annotator;
          }
  
          boolean run(int maxIteration) {
              if (blocks.isEmpty()) {
                  return true;
              }
              initialize();
              entry.state = df.makeEntryState();
              runIteration(blocks);
              boolean valid = true;
              if (changed && forwardTill < blocks.size()) {
                  List<BasicBlock> subList = blocks.subList(forwardTill, blocks.size());
                  valid = false;
                  for (int iter = 0; iter < maxIteration; iter++) {
                      runIteration(subList);
                      if (!changed) {
                          valid = true;
                          break;
                      }
                  }
                  if (!valid) {
                      for (BasicBlock bb : subList) {
                          if (bb.changed) {
                              annotator.put(bb.expr, df.makeUnknownFact());
                              bb.state = null;
                          }
                      }
                      if (exit.changed) {
                          exit.state = null;
                      }
                      if (fail.changed) {
                          fail.state = null;
                      }
                  }
              }
              for (List<BasicBlock> dupList : dupExpr) {
                  FACT res = dupList.stream().map(bb -> annotator.get(bb.expr)).reduce(null, df::mergeFacts);
                  dupList.forEach(bb -> annotator.put(bb.expr, res));
              }
              @SuppressWarnings("unchecked")
              STATE exitState = (STATE) exit.state;
              df.onSuccess(exitState);
              @SuppressWarnings("unchecked")
              STATE failState = (STATE) fail.state;
              df.onFail(failState);
              return valid;
          }
  
          private void runIteration(List<BasicBlock> blocks) {
              changed = false;
              clearChanged();
              for (BasicBlock bb : blocks) {
                  try {
                      if (!bb.reached) {
                          annotator.put(bb.expr, df.makeUnknownFact());
                          continue;
                      }
                      @SuppressWarnings("unchecked")
                      STATE state = (STATE) bb.state;
                      FACT fact = df.makeFact(state, bb.expr);
                      FACT oldFact = annotator.get(bb.expr);
                      if (!df.sameFact(oldFact, fact)) {
                          FACT updatedFact = df.mergeFacts(oldFact, fact);
                          if (!df.sameFact(updatedFact, oldFact)) {
                              annotator.put(bb.expr, updatedFact);
                              bb.changed = changed = true;
                          }
                      }
                      if (bb.expr.getCode() == AstCode.Goto) {
                          updateState(state, bb.passTarget);
                          continue;
                      }
                      if (bb.passTarget != null) {
                          updateState(df.transferState(state, bb.expr), bb.passTarget);
                      }
                      if (bb.trueTarget != null || bb.falseTarget != null) {
                          TrueFalse<STATE> tf = transferConditional(bb.expr, state);
                          updateState(tf.trueState, bb.trueTarget);
                          updateState(tf.falseState, bb.falseTarget);
                      }
                      if (bb.failTargets != null) {
                          STATE newState = bb.expr.getCode() == AstCode.Ret ? df.transferState(state, bb.expr)
                                  : df.transferExceptionalState(state, bb.expr);
                          for (BasicBlock target : bb.failTargets) {
                              updateState(newState, target);
                          }
                      }
                  } catch (Exception e) {
                      throw new RuntimeException("Error running DFA at block " + bb + "\n" + CFG.this + CFG.this.body, e);
                  }
              }
          }
  
          private TrueFalse<STATE> transferConditional(Expression expr, STATE state) {
              boolean invert = false;
              while(expr.getCode() == AstCode.LogicalNot) {
                  invert = !invert;
                  expr = expr.getArguments().get(0);
              }
              TrueFalse<STATE> tf = df.transferConditionalState(state, expr);
              return invert ? tf.invert() : tf;
          }
  
          private void updateState(STATE newState, BasicBlock target) {
              @SuppressWarnings("unchecked")
              STATE oldState = (STATE) target.state;
              if (oldState == null) {
                  if (newState != null) {
                      target.state = newState;
                      target.changed = changed = true;
                  }
              } else if (newState != null && !df.sameState(oldState, newState)) {
                  STATE updatedState = df.mergeStates(oldState, newState);
                  target.state = updatedState;
                  if (!df.sameState(oldState, updatedState)) {
                      target.changed = changed = true;
                  }
              }
          }
  
          @Override
          public String toString() {
              StringBuilder sb = new StringBuilder();
              for (BasicBlock bb : blocks) {
                  sb.append(getBlockDescription(bb));
              }
              sb.append(getBlockDescription(exit));
              sb.append(getBlockDescription(fail));
              return sb.toString();
          }
  
          String getBlockDescription(BasicBlock bb) {
              return "[" + bb.getId() + "] " + (bb.changed ? "*" : " ") + " " + bb.state + " | " + (bb.expr == null ? "?"
                      : annotator.get(bb.expr)) + "\n";
          }
      }
  
      public enum EdgeType {
          PASS, TRUE, FALSE, FAIL;
      }
  
      static class BasicBlock {
          Object state;
          boolean changed, reached, synthetic;
          int id = -1;
          Expression expr;
          BasicBlock passTarget;
          BasicBlock trueTarget;
          BasicBlock falseTarget;
          List<BasicBlock> failTargets;
  
          BasicBlock() {
          }
  
          BasicBlock(int id) {
              this.id = id;
          }
  
          BasicBlock(Expression expr) {
              this.expr = expr;
          }
  
          BasicBlock(boolean synthetic, Expression expr) {
              this.expr = expr;
              this.synthetic = synthetic;
          }
          
          void setId(int id) {
              if (this.id >= 0)
                  throw new IllegalStateException("Double id: " + this.id + "/" + id);
              this.id = id;
          }
          
          BasicBlock falseOrPass() {
              return falseTarget != null ? falseTarget : passTarget;
          }
  
          BasicBlock trueOrPass() {
              return trueTarget != null ? trueTarget : passTarget;
          }
  
          void setExpression(Expression expr) {
              if (this.expr != null)
                  throw new IllegalStateException("Expression is set twice: " + expr + "\n" + this);
              this.expr = expr;
          }
  
          void addTarget(EdgeType type, BasicBlock target) {
              switch (type) {
              case FAIL:
                  if (failTargets == null)
                      failTargets = new ArrayList<>();
                  if (!failTargets.contains(target))
                      failTargets.add(target);
                  break;
              case FALSE:
                  if (falseTarget != null || passTarget != null)
                      throw new IllegalStateException("False target is set twice: " + expr);
                  falseTarget = target;
                  break;
              case PASS:
                  if (passTarget != null || trueTarget != null || falseTarget != null)
                      throw new IllegalStateException("Pass target is set twice: " + expr);
                  passTarget = target;
                  break;
              case TRUE:
                  if (trueTarget != null || passTarget != null)
                      throw new IllegalStateException("True target is set twice: " + expr);
                  trueTarget = target;
                  break;
              default:
                  throw new InternalError();
              }
          }
  
          public String getId() {
              switch (id) {
              case BLOCKTYPE_UNKNOWN:
                  return "UNKNOWN";
              case BLOCKTYPE_EXIT:
                  return "EXIT";
              case BLOCKTYPE_FAIL:
                  return "FAIL";
              case BLOCKTYPE_IMPLICIT:
                  return "IMPLICIT";
              default:
                  return String.valueOf(id);
              }
          }
  
          public Stream<BasicBlock> targets() {
              Stream<BasicBlock> stream = Stream.of(passTarget, trueTarget, falseTarget);
              if (failTargets != null)
                  stream = Stream.concat(stream, failTargets.stream());
              return stream.filter(Objects::nonNull);
          }
  
          public Stream<BasicBlock> targetsExcept(EdgeType type) {
              switch (type) {
              case PASS: {
                  Stream<BasicBlock> stream = Stream.of(trueTarget, falseTarget);
                  if (failTargets != null)
                      stream = Stream.concat(stream, failTargets.stream());
                  return stream.filter(Objects::nonNull);
              }
              case TRUE: {
                  Stream<BasicBlock> stream = Stream.of(passTarget, falseTarget);
                  if (failTargets != null)
                      stream = Stream.concat(stream, failTargets.stream());
                  return stream.filter(Objects::nonNull);
              }
              case FALSE: {
                  Stream<BasicBlock> stream = Stream.of(passTarget, trueTarget);
                  if (failTargets != null)
                      stream = Stream.concat(stream, failTargets.stream());
                  return stream.filter(Objects::nonNull);
              }
              case FAIL:
                  return Stream.of(passTarget, trueTarget, falseTarget).filter(Objects::nonNull);
              default:
                  throw new InternalError();
              }
          }
  
          @Override
          public String toString() {
              StringBuilder sb = new StringBuilder("[").append(getId()).append("]").append(!reached ? "-" : " ").append(
                  expr).append("\n  ");
              if (passTarget != null)
                  sb.append("PASS -> [").append(passTarget.getId()).append("] ");
              if (trueTarget != null)
                  sb.append("TRUE -> [").append(trueTarget.getId()).append("] ");
              if (falseTarget != null)
                  sb.append("FALSE -> [").append(falseTarget.getId()).append("] ");
              if (failTargets != null)
                  sb.append("FAIL -> [").append(failTargets.stream().map(BasicBlock::getId).collect(Collectors.joining(
                      ","))).append("]");
              sb.append("\n");
              return sb.toString();
          }
      }
  
      interface JumpContext {
          void addReturn(BasicBlock block);
  
          void addBreak(BasicBlock block, Label label);
  
          void addContinue(BasicBlock block, Label label);
  
          void addJump(BasicBlock block, Label label);
  
          void addExceptional(BasicBlock block, TypeReference exception);
      }
  
      class OuterJumpContext implements JumpContext {
          @Override
          public void addExceptional(BasicBlock block, TypeReference exception) {
              block.addTarget(EdgeType.FAIL, fail);
          }
  
          @Override
          public void addReturn(BasicBlock block) {
              block.addTarget(EdgeType.PASS, exit);
          }
  
          @Override
          public void addBreak(BasicBlock block, Label label) {
              if (label != null)
                  addJump(block, label);
              else
                  throw new IllegalStateException("Misplaced break");
          }
  
          @Override
          public void addContinue(BasicBlock block, Label label) {
              throw new IllegalStateException("Misplaced continue");
          }
  
          @Override
          public void addJump(BasicBlock block, Label label) {
              block.addTarget(EdgeType.PASS, labelTargets.computeIfAbsent(label, k -> new BasicBlock()));
          }
      }
  
      static abstract class DelegatingJumpContext implements JumpContext {
          private final JumpContext parent;
  
          protected DelegatingJumpContext(JumpContext parent) {
              this.parent = parent;
          }
  
          @Override
          public void addReturn(BasicBlock block) {
              parent.addReturn(block);
          }
  
          @Override
          public void addBreak(BasicBlock block, Label label) {
              parent.addBreak(block, label);
          }
  
          @Override
          public void addContinue(BasicBlock block, Label label) {
              parent.addContinue(block, label);
          }
  
          @Override
          public void addJump(BasicBlock block, Label label) {
              parent.addJump(block, label);
          }
  
          @Override
          public void addExceptional(BasicBlock block, TypeReference exception) {
              parent.addExceptional(block, exception);
          }
      }
  
      static class SwitchJumpContext extends DelegatingJumpContext {
          private final BasicBlock exit;
  
          public SwitchJumpContext(JumpContext parent, BasicBlock exit) {
              super(parent);
              this.exit = exit;
          }
  
          @Override
          public void addBreak(BasicBlock block, Label label) {
              if (label == null) {
                  block.addTarget(EdgeType.PASS, exit);
              } else {
                  super.addBreak(block, label);
              }
          }
      }
  
      class LoopJumpContext extends DelegatingJumpContext {
          private final BasicBlock exit;
          private final BasicBlock continueTarget;
          private final BasicBlock entry;
  
          public LoopJumpContext(JumpContext parent, BasicBlock entry, BasicBlock exit, BasicBlock continueTarget) {
              super(parent);
              this.entry = entry;
              this.exit = exit;
              this.continueTarget = continueTarget;
          }
  
          @Override
          public void addBreak(BasicBlock block, Label label) {
              if (label == null) {
                  block.addTarget(EdgeType.PASS, exit);
              } else {
                  super.addBreak(block, label);
              }
          }
  
          @Override
          public void addContinue(BasicBlock block, Label label) {
              if (label == null || labelTargets.get(label) == entry) {
                  block.addTarget(EdgeType.PASS, continueTarget);
              } else {
                  super.addBreak(block, label);
              }
          }
      }
  
      class LabelJumpContext extends DelegatingJumpContext {
          private final Set<Label> labels;
  
          LabelJumpContext(JumpContext parent, Set<Label> labels) {
              super(parent);
              this.labels = labels;
          }
  
          @Override
          public void addBreak(BasicBlock block, Label label) {
              if (label != null) {
                  addJump(block, label);
              } else {
                  super.addBreak(block, label);
              }
          }
  
          @Override
          public void addJump(BasicBlock block, Label label) {
              if (labels.contains(label)) {
                  block.addTarget(EdgeType.PASS, labelTargets.computeIfAbsent(label, k -> new BasicBlock()));
              } else {
                  super.addJump(block, label);
              }
          }
      }
  
      static class CatchJumpContext extends DelegatingJumpContext {
          private final Map<CatchBlock, BasicBlock> catches;
  
          CatchJumpContext(JumpContext parent, BasicBlock nextBlock, List<CatchBlock> catchBlocks) {
              super(parent);
              this.catches = catchBlocks.stream().collect(Collectors.toMap(Function.identity(), cb -> cb.getBody()
                      .isEmpty() ? nextBlock : new BasicBlock(), (a, b) -> a, LinkedHashMap::new));
          }
  
          @Override
          public void addExceptional(BasicBlock block, TypeReference exception) {
              for (Entry<CatchBlock, BasicBlock> entry : catches.entrySet()) {
                  for (TypeReference tr : types(entry.getKey())) {
                      if (Types.isInstance(exception, tr)) {
                          // Exact match: catch and return
                          block.addTarget(EdgeType.FAIL, entry.getValue());
                          return;
                      } else if (Types.isInstance(tr, exception) || !Types.hasCompleteHierarchy(tr.resolve())) {
                          // Inexact match: probably caught here or by another catch block
                          block.addTarget(EdgeType.FAIL, entry.getValue());
                      }
                  }
              }
              super.addExceptional(block, exception);
          }
  
          BasicBlock getEntry(CatchBlock cb) {
              return catches.get(cb);
          }
  
          private static Collection<TypeReference> types(CatchBlock cb) {
              if (cb.getCaughtTypes().isEmpty())
                  return Collections.singleton(cb.getExceptionType());
              return cb.getCaughtTypes();
          }
      }
  
      static class FinallyJumpContext extends DelegatingJumpContext {
          final Map<BasicBlock, BasicBlock> targetEntries = new HashMap<>();
  
          FinallyJumpContext(JumpContext parent) {
              super(parent);
          }
  
          private void replacePass(BasicBlock block) {
              if (block.passTarget == null)
                  throw new IllegalStateException("Passtarget is null for " + block);
              block.passTarget = targetEntries.computeIfAbsent(block.passTarget, t -> new BasicBlock());
          }
  
          @Override
          public void addReturn(BasicBlock block) {
              super.addReturn(block);
              replacePass(block);
          }
  
          @Override
          public void addBreak(BasicBlock block, Label label) {
              super.addBreak(block, label);
              replacePass(block);
          }
  
          @Override
          public void addContinue(BasicBlock block, Label label) {
              super.addContinue(block, label);
              replacePass(block);
          }
  
          @Override
          public void addJump(BasicBlock block, Label label) {
              super.addJump(block, label);
              replacePass(block);
          }
  
          @Override
          public void addExceptional(BasicBlock block, TypeReference exception) {
              List<BasicBlock> oldTargets = block.failTargets;
              block.failTargets = null;
              super.addExceptional(block, exception);
              List<BasicBlock> newTargets = block.failTargets;
              block.failTargets = oldTargets;
              newTargets.forEach(t -> block.addTarget(EdgeType.FAIL, targetEntries.computeIfAbsent(t,
                  tt -> new BasicBlock())));
          }
      }
  }
  