diff options
Diffstat (limited to 'third_party/checker_framework_dataflow/java/org/checkerframework/dataflow/cfg/CFGBuilder.java')
| -rw-r--r-- | third_party/checker_framework_dataflow/java/org/checkerframework/dataflow/cfg/CFGBuilder.java | 4448 |
1 files changed, 4448 insertions, 0 deletions
diff --git a/third_party/checker_framework_dataflow/java/org/checkerframework/dataflow/cfg/CFGBuilder.java b/third_party/checker_framework_dataflow/java/org/checkerframework/dataflow/cfg/CFGBuilder.java new file mode 100644 index 0000000000..2cff0f2802 --- /dev/null +++ b/third_party/checker_framework_dataflow/java/org/checkerframework/dataflow/cfg/CFGBuilder.java @@ -0,0 +1,4448 @@ +package org.checkerframework.dataflow.cfg; + +/*>>> +import org.checkerframework.checker.nullness.qual.Nullable; +*/ + +import org.checkerframework.dataflow.analysis.Store; +import org.checkerframework.dataflow.cfg.CFGBuilder.ExtendedNode.ExtendedNodeType; +import org.checkerframework.dataflow.cfg.UnderlyingAST.CFGMethod; +import org.checkerframework.dataflow.cfg.block.Block; +import org.checkerframework.dataflow.cfg.block.Block.BlockType; +import org.checkerframework.dataflow.cfg.block.BlockImpl; +import org.checkerframework.dataflow.cfg.block.ConditionalBlockImpl; +import org.checkerframework.dataflow.cfg.block.ExceptionBlockImpl; +import org.checkerframework.dataflow.cfg.block.RegularBlockImpl; +import org.checkerframework.dataflow.cfg.block.SingleSuccessorBlockImpl; +import org.checkerframework.dataflow.cfg.block.SpecialBlock.SpecialBlockType; +import org.checkerframework.dataflow.cfg.block.SpecialBlockImpl; +import org.checkerframework.dataflow.cfg.node.*; +import org.checkerframework.dataflow.qual.TerminatesExecution; +import org.checkerframework.dataflow.util.MostlySingleton; +import org.checkerframework.javacutil.AnnotationProvider; +import org.checkerframework.javacutil.BasicAnnotationProvider; +import org.checkerframework.javacutil.ElementUtils; +import org.checkerframework.javacutil.InternalUtils; +import org.checkerframework.javacutil.Pair; +import org.checkerframework.javacutil.TreeUtils; +import org.checkerframework.javacutil.TypesUtils; +import org.checkerframework.javacutil.trees.TreeBuilder; + +import java.util.ArrayList; +import java.util.Arrays; +import java.util.Collections; +import java.util.HashMap; +import java.util.HashSet; +import java.util.IdentityHashMap; +import java.util.LinkedList; +import java.util.List; +import java.util.Map; +import java.util.Map.Entry; +import java.util.Set; + +import javax.annotation.processing.ProcessingEnvironment; +import javax.lang.model.element.Element; +import javax.lang.model.element.ExecutableElement; +import javax.lang.model.element.Name; +import javax.lang.model.element.TypeElement; +import javax.lang.model.element.VariableElement; +import javax.lang.model.type.ArrayType; +import javax.lang.model.type.DeclaredType; +import javax.lang.model.type.PrimitiveType; +import javax.lang.model.type.ReferenceType; +import javax.lang.model.type.TypeKind; +import javax.lang.model.type.TypeMirror; +import javax.lang.model.type.TypeVariable; +import javax.lang.model.type.UnionType; +import javax.lang.model.util.Elements; +import javax.lang.model.util.Types; + +import com.sun.source.tree.*; +import com.sun.source.tree.Tree.Kind; +import com.sun.source.util.TreePath; +import com.sun.source.util.TreePathScanner; +import com.sun.source.util.Trees; +import com.sun.tools.javac.code.Symbol.MethodSymbol; +import com.sun.tools.javac.code.Type; +import com.sun.tools.javac.processing.JavacProcessingEnvironment; +import com.sun.tools.javac.util.Context; + +/** + * Builds the control flow graph of some Java code (either a method, or an + * arbitrary statement). + * + * <p> + * + * The translation of the AST to the CFG is split into three phases: + * <ol> + * <li><em>Phase one.</em> In the first phase, the AST is translated into a + * sequence of {@link org.checkerframework.dataflow.cfg.CFGBuilder.ExtendedNode}s. An extended node can either be a + * {@link Node}, or one of several meta elements such as a conditional or + * unconditional jump or a node with additional information about exceptions. + * Some of the extended nodes contain labels (e.g., for the jump target), and + * phase one additionally creates a mapping from labels to extended nodes. + * Finally, the list of leaders is computed: A leader is an extended node which + * will give rise to a basic block in phase two.</li> + * <li><em>Phase two.</em> In this phase, the sequence of extended nodes is + * translated to a graph of control flow blocks that contain nodes. The meta + * elements from phase one are translated into the correct edges.</li> + * <li><em>Phase three.</em> The control flow graph generated in phase two can + * contain degenerate basic blocks such as empty regular basic blocks or + * conditional basic blocks that have the same block as both 'then' and 'else' + * successor. This phase removes these cases while preserving the control flow + * structure.</li> + * </ol> + * + * @author Stefan Heule + * + */ +public class CFGBuilder { + + /** Can assertions be assumed to be disabled? */ + protected final boolean assumeAssertionsDisabled; + + /** Can assertions be assumed to be enabled? */ + protected final boolean assumeAssertionsEnabled; + + public CFGBuilder(boolean assumeAssertionsEnabled, boolean assumeAssertionsDisabled) { + assert !(assumeAssertionsDisabled && assumeAssertionsEnabled); + this.assumeAssertionsEnabled = assumeAssertionsEnabled; + this.assumeAssertionsDisabled = assumeAssertionsDisabled; + } + + /** + * Class declarations that have been encountered when building the + * control-flow graph for a method. + */ + protected final List<ClassTree> declaredClasses = new LinkedList<>(); + + public List<ClassTree> getDeclaredClasses() { + return declaredClasses; + } + + /** + * Lambdas encountered when building the control-flow graph for + * a method, variable initializer, or initializer. + */ + protected final List<LambdaExpressionTree> declaredLambdas = new LinkedList<>(); + + public List<LambdaExpressionTree> getDeclaredLambdas() { + return declaredLambdas; + } + + /** + * Build the control flow graph of some code. + */ + public static ControlFlowGraph build( + CompilationUnitTree root, ProcessingEnvironment env, + UnderlyingAST underlyingAST, boolean assumeAssertionsEnabled, boolean assumeAssertionsDisabled) { + return new CFGBuilder(assumeAssertionsEnabled, assumeAssertionsDisabled).run(root, env, underlyingAST); + } + + /** + * Build the control flow graph of some code (method, initializer block, ...). + * bodyPath is the TreePath to the body of that code. + */ + public static ControlFlowGraph build( + TreePath bodyPath, ProcessingEnvironment env, + UnderlyingAST underlyingAST, boolean assumeAssertionsEnabled, boolean assumeAssertionsDisabled) { + return new CFGBuilder(assumeAssertionsEnabled, assumeAssertionsDisabled).run(bodyPath, env, underlyingAST); + } + + /** + * Build the control flow graph of a method. + */ + public static ControlFlowGraph build( + CompilationUnitTree root, ProcessingEnvironment env, + MethodTree tree, ClassTree classTree, boolean assumeAssertionsEnabled, boolean assumeAssertionsDisabled) { + return new CFGBuilder(assumeAssertionsEnabled, assumeAssertionsDisabled).run(root, env, tree, classTree); + } + + /** + * Build the control flow graph of some code. + */ + public static ControlFlowGraph build( + CompilationUnitTree root, ProcessingEnvironment env, + UnderlyingAST underlyingAST) { + return new CFGBuilder(false, false).run(root, env, underlyingAST); + } + + /** + * Build the control flow graph of a method. + */ + public static ControlFlowGraph build( + CompilationUnitTree root, ProcessingEnvironment env, + MethodTree tree, ClassTree classTree) { + return new CFGBuilder(false, false).run(root, env, tree, classTree); + } + + /** + * Build the control flow graph of some code. + */ + public ControlFlowGraph run( + CompilationUnitTree root, ProcessingEnvironment env, + UnderlyingAST underlyingAST) { + declaredClasses.clear(); + declaredLambdas.clear(); + + TreeBuilder builder = new TreeBuilder(env); + AnnotationProvider annotationProvider = new BasicAnnotationProvider(); + PhaseOneResult phase1result = new CFGTranslationPhaseOne().process( + root, env, underlyingAST, exceptionalExitLabel, builder, annotationProvider); + ControlFlowGraph phase2result = new CFGTranslationPhaseTwo() + .process(phase1result); + ControlFlowGraph phase3result = CFGTranslationPhaseThree + .process(phase2result); + return phase3result; + } + + /** + * Build the control flow graph of some code (method, initializer block, ...). + * bodyPath is the TreePath to the body of that code. + */ + public ControlFlowGraph run( + TreePath bodyPath, ProcessingEnvironment env, + UnderlyingAST underlyingAST) { + declaredClasses.clear(); + TreeBuilder builder = new TreeBuilder(env); + AnnotationProvider annotationProvider = new BasicAnnotationProvider(); + PhaseOneResult phase1result = new CFGTranslationPhaseOne().process( + bodyPath, env, underlyingAST, exceptionalExitLabel, builder, annotationProvider); + ControlFlowGraph phase2result = new CFGTranslationPhaseTwo() + .process(phase1result); + ControlFlowGraph phase3result = CFGTranslationPhaseThree + .process(phase2result); + return phase3result; + } + + /** + * Build the control flow graph of a method. + */ + public ControlFlowGraph run( + CompilationUnitTree root, ProcessingEnvironment env, + MethodTree tree, ClassTree classTree) { + UnderlyingAST underlyingAST = new CFGMethod(tree, classTree); + return run(root, env, underlyingAST); + } + + /* --------------------------------------------------------- */ + /* Extended Node Types and Labels */ + /* --------------------------------------------------------- */ + + /** Special label to identify the exceptional exit. */ + protected final Label exceptionalExitLabel = new Label(); + + /** Special label to identify the regular exit. */ + protected final Label regularExitLabel = new Label(); + + /** + * An extended node can be one of several things (depending on its + * {@code type}): + * <ul> + * <li><em>NODE</em>. An extended node of this type is just a wrapper for a + * {@link Node} (that cannot throw exceptions).</li> + * <li><em>EXCEPTION_NODE</em>. A wrapper for a {@link Node} which can throw + * exceptions. It contains a label for every possible exception type the + * node might throw.</li> + * <li><em>UNCONDITIONAL_JUMP</em>. An unconditional jump to a label.</li> + * <li><em>TWO_TARGET_CONDITIONAL_JUMP</em>. A conditional jump with two + * targets for both the 'then' and 'else' branch.</li> + * </ul> + */ + protected static abstract class ExtendedNode { + + /** + * The basic block this extended node belongs to (as determined in phase + * two). + */ + protected BlockImpl block; + + /** Type of this node. */ + protected ExtendedNodeType type; + + /** Does this node terminate the execution? (e.g., "System.exit()") */ + protected boolean terminatesExecution = false; + + public ExtendedNode(ExtendedNodeType type) { + this.type = type; + } + + /** Extended node types (description see above). */ + public enum ExtendedNodeType { + NODE, EXCEPTION_NODE, UNCONDITIONAL_JUMP, CONDITIONAL_JUMP + } + + public ExtendedNodeType getType() { + return type; + } + + public boolean getTerminatesExecution() { + return terminatesExecution; + } + + public void setTerminatesExecution(boolean terminatesExecution) { + this.terminatesExecution = terminatesExecution; + } + + /** + * @return the node contained in this extended node (only applicable if + * the type is {@code NODE} or {@code EXCEPTION_NODE}). + */ + public Node getNode() { + assert false; + return null; + } + + /** + * @return the label associated with this extended node (only applicable + * if type is {@link ExtendedNodeType#CONDITIONAL_JUMP} or + * {@link ExtendedNodeType#UNCONDITIONAL_JUMP}). + */ + public Label getLabel() { + assert false; + return null; + } + + public BlockImpl getBlock() { + return block; + } + + public void setBlock(BlockImpl b) { + this.block = b; + } + + @Override + public String toString() { + return "ExtendedNode(" + type + ")"; + } + } + + /** + * An extended node of type {@code NODE}. + */ + protected static class NodeHolder extends ExtendedNode { + + protected Node node; + + public NodeHolder(Node node) { + super(ExtendedNodeType.NODE); + this.node = node; + } + + @Override + public Node getNode() { + return node; + } + + @Override + public String toString() { + return "NodeHolder(" + node + ")"; + } + + } + + /** + * An extended node of type {@code EXCEPTION_NODE}. + */ + protected static class NodeWithExceptionsHolder extends ExtendedNode { + + protected Node node; + /** + * Map from exception type to labels of successors that may + * be reached as a result of that exception. + */ + protected Map<TypeMirror, Set<Label>> exceptions; + + public NodeWithExceptionsHolder(Node node, + Map<TypeMirror, Set<Label>> exceptions) { + super(ExtendedNodeType.EXCEPTION_NODE); + this.node = node; + this.exceptions = exceptions; + } + + public Map<TypeMirror, Set<Label>> getExceptions() { + return exceptions; + } + + @Override + public Node getNode() { + return node; + } + + @Override + public String toString() { + return "NodeWithExceptionsHolder(" + node + ")"; + } + + } + + /** + * An extended node of type {@link ExtendedNodeType#CONDITIONAL_JUMP}. + * + * <p> + * + * <em>Important:</em> In the list of extended nodes, there should not be + * any labels that point to a conditional jump. Furthermore, the node + * directly ahead of any conditional jump has to be a + * {@link NodeWithExceptionsHolder} or {@link NodeHolder}, and the node held + * by that extended node is required to be of boolean type. + */ + protected static class ConditionalJump extends ExtendedNode { + + protected Label trueSucc; + protected Label falseSucc; + + protected Store.FlowRule trueFlowRule; + protected Store.FlowRule falseFlowRule; + + public ConditionalJump(Label trueSucc, Label falseSucc) { + super(ExtendedNodeType.CONDITIONAL_JUMP); + this.trueSucc = trueSucc; + this.falseSucc = falseSucc; + } + + public Label getThenLabel() { + return trueSucc; + } + + public Label getElseLabel() { + return falseSucc; + } + + public Store.FlowRule getTrueFlowRule() { + return trueFlowRule; + } + + public Store.FlowRule getFalseFlowRule() { + return falseFlowRule; + } + + public void setTrueFlowRule(Store.FlowRule rule) { + trueFlowRule = rule; + } + + public void setFalseFlowRule(Store.FlowRule rule) { + falseFlowRule = rule; + } + + @Override + public String toString() { + return "TwoTargetConditionalJump(" + getThenLabel() + "," + + getElseLabel() + ")"; + } + } + + /** + * An extended node of type {@link ExtendedNodeType#UNCONDITIONAL_JUMP}. + */ + protected static class UnconditionalJump extends ExtendedNode { + + protected Label jumpTarget; + + public UnconditionalJump(Label jumpTarget) { + super(ExtendedNodeType.UNCONDITIONAL_JUMP); + this.jumpTarget = jumpTarget; + } + + @Override + public Label getLabel() { + return jumpTarget; + } + + @Override + public String toString() { + return "JumpMarker(" + getLabel() + ")"; + } + } + + /** + * A label is used to refer to other extended nodes using a mapping from + * labels to extended nodes. Labels get their names either from labeled + * statements in the source code or from internally generated unique names. + */ + protected static class Label { + private static int uid = 0; + + protected String name; + + public Label(String name) { + this.name = name; + } + + public Label() { + this.name = uniqueName(); + } + + @Override + public String toString() { + return name; + } + + /** + * Return a new unique label name that cannot be confused with a Java + * source code label. + * + * @return a new unique label name + */ + private static String uniqueName() { + return "%L" + uid++; + } + } + + /** + * A TryFrame takes a thrown exception type and maps it to a set + * of possible control-flow successors. + */ + protected static interface TryFrame { + /** + * Given a type of thrown exception, add the set of possible control + * flow successor {@link Label}s to the argument set. Return true + * if the exception is known to be caught by one of those labels and + * false if it may propagate still further. + */ + public boolean possibleLabels(TypeMirror thrown, Set<Label> labels); + } + + /** + * A TryCatchFrame contains an ordered list of catch labels that apply + * to exceptions with specific types. + */ + protected static class TryCatchFrame implements TryFrame { + protected Types types; + + /** An ordered list of pairs because catch blocks are ordered. */ + protected List<Pair<TypeMirror, Label>> catchLabels; + + public TryCatchFrame(Types types, List<Pair<TypeMirror, Label>> catchLabels) { + this.types = types; + this.catchLabels = catchLabels; + } + + /** + * Given a type of thrown exception, add the set of possible control + * flow successor {@link Label}s to the argument set. Return true + * if the exception is known to be caught by one of those labels and + * false if it may propagate still further. + */ + @Override + public boolean possibleLabels(TypeMirror thrown, Set<Label> labels) { + // A conservative approach would be to say that every catch block + // might execute for any thrown exception, but we try to do better. + // + // We rely on several assumptions that seem to hold as of Java 7. + // 1) An exception parameter in a catch block must be either + // a declared type or a union composed of declared types, + // all of which are subtypes of Throwable. + // 2) A thrown type must either be a declared type or a variable + // that extends a declared type, which is a subtype of Throwable. + // + // Under those assumptions, if the thrown type (or its bound) is + // a subtype of the caught type (or one of its alternatives), then + // the catch block must apply and none of the later ones can apply. + // Otherwise, if the thrown type (or its bound) is a supertype + // of the caught type (or one of its alternatives), then the catch + // block may apply, but so may later ones. + // Otherwise, the thrown type and the caught type are unrelated + // declared types, so they do not overlap on any non-null value. + + while (!(thrown instanceof DeclaredType)) { + assert thrown instanceof TypeVariable : + "thrown type must be a variable or a declared type"; + thrown = ((TypeVariable)thrown).getUpperBound(); + } + DeclaredType declaredThrown = (DeclaredType)thrown; + assert thrown != null : "thrown type must be bounded by a declared type"; + + for (Pair<TypeMirror, Label> pair : catchLabels) { + TypeMirror caught = pair.first; + boolean canApply = false; + + if (caught instanceof DeclaredType) { + DeclaredType declaredCaught = (DeclaredType)caught; + if (types.isSubtype(declaredThrown, declaredCaught)) { + // No later catch blocks can apply. + labels.add(pair.second); + return true; + } else if (types.isSubtype(declaredCaught, declaredThrown)) { + canApply = true; + } + } else { + assert caught instanceof UnionType : + "caught type must be a union or a declared type"; + UnionType caughtUnion = (UnionType)caught; + for (TypeMirror alternative : caughtUnion.getAlternatives()) { + assert alternative instanceof DeclaredType : + "alternatives of an caught union type must be declared types"; + DeclaredType declaredAlt = (DeclaredType)alternative; + if (types.isSubtype(declaredThrown, declaredAlt)) { + // No later catch blocks can apply. + labels.add(pair.second); + return true; + } else if (types.isSubtype(declaredAlt, declaredThrown)) { + canApply = true; + } + } + } + + if (canApply) { + labels.add(pair.second); + } + } + + return false; + } + } + + /** + * A TryFinallyFrame applies to exceptions of any type + */ + protected class TryFinallyFrame implements TryFrame { + protected Label finallyLabel; + + public TryFinallyFrame(Label finallyLabel) { + this.finallyLabel = finallyLabel; + } + + @Override + public boolean possibleLabels(TypeMirror thrown, Set<Label> labels) { + labels.add(finallyLabel); + return true; + } + } + + /** + * An exception stack represents the set of all try-catch blocks + * in effect at a given point in a program. It maps an exception + * type to a set of Labels and it maps a block exit (via return or + * fall-through) to a single Label. + */ + protected static class TryStack { + protected Label exitLabel; + protected LinkedList<TryFrame> frames; + + public TryStack(Label exitLabel) { + this.exitLabel = exitLabel; + this.frames = new LinkedList<>(); + } + + public void pushFrame(TryFrame frame) { + frames.addFirst(frame); + } + + public void popFrame() { + frames.removeFirst(); + } + + /** + * Returns the set of possible {@link Label}s where control may + * transfer when an exception of the given type is thrown. + */ + public Set<Label> possibleLabels(TypeMirror thrown) { + // Work up from the innermost frame until the exception is known to + // be caught. + Set<Label> labels = new MostlySingleton<>(); + for (TryFrame frame : frames) { + if (frame.possibleLabels(thrown, labels)) { + return labels; + } + } + labels.add(exitLabel); + return labels; + } + } + + /* --------------------------------------------------------- */ + /* Phase Three */ + /* --------------------------------------------------------- */ + + /** + * Class that performs phase three of the translation process. In + * particular, the following degenerate cases of basic blocks are removed: + * + * <ol> + * <li>Empty regular basic blocks: These blocks will be removed and their + * predecessors linked directly to the successor.</li> + * <li>Conditional basic blocks that have the same basic block as the 'then' + * and 'else' successor: The conditional basic block will be removed in this + * case.</li> + * <li>Two consecutive, non-empty, regular basic blocks where the second + * block has exactly one predecessor (namely the other of the two blocks): + * In this case, the two blocks are merged.</li> + * <li>Some basic blocks might not be reachable from the entryBlock. These + * basic blocks are removed, and the list of predecessors (in the + * doubly-linked structure of basic blocks) are adapted correctly.</li> + * </ol> + * + * Eliminating the second type of degenerate cases might introduce cases of + * the third problem. These are also removed. + */ + public static class CFGTranslationPhaseThree { + + /** + * A simple wrapper object that holds a basic block and allows to set + * one of its successors. + */ + protected interface PredecessorHolder { + void setSuccessor(BlockImpl b); + + BlockImpl getBlock(); + } + + /** + * Perform phase three on the control flow graph {@code cfg}. + * + * @param cfg + * The control flow graph. Ownership is transfered to this + * method and the caller is not allowed to read or modify + * {@code cfg} after the call to {@code process} any more. + * @return the resulting control flow graph + */ + public static ControlFlowGraph process(ControlFlowGraph cfg) { + Set<Block> worklist = cfg.getAllBlocks(); + Set<Block> dontVisit = new HashSet<>(); + + // note: this method has to be careful when relinking basic blocks + // to not forget to adjust the predecessors, too + + // fix predecessor lists by removing any unreachable predecessors + for (Block c : worklist) { + BlockImpl cur = (BlockImpl) c; + for (BlockImpl pred : new HashSet<>(cur.getPredecessors())) { + if (!worklist.contains(pred)) { + cur.removePredecessor(pred); + } + } + } + + // remove empty blocks + for (Block cur : worklist) { + if (dontVisit.contains(cur)) { + continue; + } + + if (cur.getType() == BlockType.REGULAR_BLOCK) { + RegularBlockImpl b = (RegularBlockImpl) cur; + if (b.isEmpty()) { + Set<RegularBlockImpl> empty = new HashSet<>(); + Set<PredecessorHolder> predecessors = new HashSet<>(); + BlockImpl succ = computeNeighborhoodOfEmptyBlock(b, + empty, predecessors); + for (RegularBlockImpl e : empty) { + succ.removePredecessor(e); + dontVisit.add(e); + } + for (PredecessorHolder p : predecessors) { + BlockImpl block = p.getBlock(); + dontVisit.add(block); + succ.removePredecessor(block); + p.setSuccessor(succ); + } + } + } + } + + // remove useless conditional blocks + worklist = cfg.getAllBlocks(); + for (Block c : worklist) { + BlockImpl cur = (BlockImpl) c; + + if (cur.getType() == BlockType.CONDITIONAL_BLOCK) { + ConditionalBlockImpl cb = (ConditionalBlockImpl) cur; + assert cb.getPredecessors().size() == 1; + if (cb.getThenSuccessor() == cb.getElseSuccessor()) { + BlockImpl pred = cb.getPredecessors().iterator().next(); + PredecessorHolder predecessorHolder = getPredecessorHolder( + pred, cb); + BlockImpl succ = (BlockImpl) cb.getThenSuccessor(); + succ.removePredecessor(cb); + predecessorHolder.setSuccessor(succ); + } + } + } + + // merge consecutive basic blocks if possible + worklist = cfg.getAllBlocks(); + for (Block cur : worklist) { + if (cur.getType() == BlockType.REGULAR_BLOCK) { + RegularBlockImpl b = (RegularBlockImpl) cur; + Block succ = b.getRegularSuccessor(); + if (succ.getType() == BlockType.REGULAR_BLOCK) { + RegularBlockImpl rs = (RegularBlockImpl) succ; + if (rs.getPredecessors().size() == 1) { + b.setSuccessor(rs.getRegularSuccessor()); + b.addNodes(rs.getContents()); + rs.getRegularSuccessor().removePredecessor(rs); + } + } + } + } + + return cfg; + } + + /** + * Compute the set of empty regular basic blocks {@code empty}, starting + * at {@code start} and going both forward and backwards. Furthermore, + * compute the predecessors of these empty blocks ({@code predecessors} + * ), and their single successor (return value). + * + * @param start + * The starting point of the search (an empty, regular basic + * block). + * @param empty + * An empty set to be filled by this method with all empty + * basic blocks found (including {@code start}). + * @param predecessors + * An empty set to be filled by this method with all + * predecessors. + * @return the single successor of the set of the empty basic blocks + */ + protected static BlockImpl computeNeighborhoodOfEmptyBlock( + RegularBlockImpl start, Set<RegularBlockImpl> empty, + Set<PredecessorHolder> predecessors) { + + // get empty neighborhood that come before 'start' + computeNeighborhoodOfEmptyBlockBackwards(start, empty, predecessors); + + // go forward + BlockImpl succ = (BlockImpl) start.getSuccessor(); + while (succ.getType() == BlockType.REGULAR_BLOCK) { + RegularBlockImpl cur = (RegularBlockImpl) succ; + if (cur.isEmpty()) { + computeNeighborhoodOfEmptyBlockBackwards(cur, empty, + predecessors); + assert empty.contains(cur) : "cur ought to be in empty"; + succ = (BlockImpl) cur.getSuccessor(); + if (succ == cur) { + // An infinite loop, making exit block unreachable + break; + } + } else { + break; + } + } + return succ; + } + + /** + * Compute the set of empty regular basic blocks {@code empty}, starting + * at {@code start} and looking only backwards in the control flow + * graph. Furthermore, compute the predecessors of these empty blocks ( + * {@code predecessors}). + * + * @param start + * The starting point of the search (an empty, regular basic + * block). + * @param empty + * A set to be filled by this method with all empty basic + * blocks found (including {@code start}). + * @param predecessors + * A set to be filled by this method with all predecessors. + */ + protected static void computeNeighborhoodOfEmptyBlockBackwards( + RegularBlockImpl start, Set<RegularBlockImpl> empty, + Set<PredecessorHolder> predecessors) { + + RegularBlockImpl cur = start; + empty.add(cur); + for (final BlockImpl pred : cur.getPredecessors()) { + switch (pred.getType()) { + case SPECIAL_BLOCK: + // add pred correctly to predecessor list + predecessors.add(getPredecessorHolder(pred, cur)); + break; + case CONDITIONAL_BLOCK: + // add pred correctly to predecessor list + predecessors.add(getPredecessorHolder(pred, cur)); + break; + case EXCEPTION_BLOCK: + // add pred correctly to predecessor list + predecessors.add(getPredecessorHolder(pred, cur)); + break; + case REGULAR_BLOCK: + RegularBlockImpl r = (RegularBlockImpl) pred; + if (r.isEmpty()) { + // recursively look backwards + if (!empty.contains(r)) { + computeNeighborhoodOfEmptyBlockBackwards(r, empty, + predecessors); + } + } else { + // add pred correctly to predecessor list + predecessors.add(getPredecessorHolder(pred, cur)); + } + break; + } + } + } + + /** + * Return a predecessor holder that can be used to set the successor of + * {@code pred} in the place where previously the edge pointed to + * {@code cur}. Additionally, the predecessor holder also takes care of + * unlinking (i.e., removing the {@code pred} from {@code cur's} + * predecessors). + */ + protected static PredecessorHolder getPredecessorHolder( + final BlockImpl pred, final BlockImpl cur) { + switch (pred.getType()) { + case SPECIAL_BLOCK: + SingleSuccessorBlockImpl s = (SingleSuccessorBlockImpl) pred; + return singleSuccessorHolder(s, cur); + case CONDITIONAL_BLOCK: + // add pred correctly to predecessor list + final ConditionalBlockImpl c = (ConditionalBlockImpl) pred; + if (c.getThenSuccessor() == cur) { + return new PredecessorHolder() { + @Override + public void setSuccessor(BlockImpl b) { + c.setThenSuccessor(b); + cur.removePredecessor(pred); + } + + @Override + public BlockImpl getBlock() { + return c; + } + }; + } else { + assert c.getElseSuccessor() == cur; + return new PredecessorHolder() { + @Override + public void setSuccessor(BlockImpl b) { + c.setElseSuccessor(b); + cur.removePredecessor(pred); + } + + @Override + public BlockImpl getBlock() { + return c; + } + }; + } + case EXCEPTION_BLOCK: + // add pred correctly to predecessor list + final ExceptionBlockImpl e = (ExceptionBlockImpl) pred; + if (e.getSuccessor() == cur) { + return singleSuccessorHolder(e, cur); + } else { + Set<Entry<TypeMirror, Set<Block>>> entrySet = e + .getExceptionalSuccessors().entrySet(); + for (final Entry<TypeMirror, Set<Block>> entry : entrySet) { + if (entry.getValue().contains(cur)) { + return new PredecessorHolder() { + @Override + public void setSuccessor(BlockImpl b) { + e.addExceptionalSuccessor(b, entry.getKey()); + cur.removePredecessor(pred); + } + + @Override + public BlockImpl getBlock() { + return e; + } + }; + } + } + } + assert false; + break; + case REGULAR_BLOCK: + RegularBlockImpl r = (RegularBlockImpl) pred; + return singleSuccessorHolder(r, cur); + } + return null; + } + + /** + * @return a {@link PredecessorHolder} that sets the successor of a + * single successor block {@code s}. + */ + protected static PredecessorHolder singleSuccessorHolder( + final SingleSuccessorBlockImpl s, final BlockImpl old) { + return new PredecessorHolder() { + @Override + public void setSuccessor(BlockImpl b) { + s.setSuccessor(b); + old.removePredecessor(s); + } + + @Override + public BlockImpl getBlock() { + return s; + } + }; + } + } + + /* --------------------------------------------------------- */ + /* Phase Two */ + /* --------------------------------------------------------- */ + + /** Tuple class with up to three members. */ + protected static class Tuple<A, B, C> { + public A a; + public B b; + public C c; + + public Tuple(A a, B b) { + this.a = a; + this.b = b; + } + + public Tuple(A a, B b, C c) { + this.a = a; + this.b = b; + this.c = c; + } + } + + /** + * Class that performs phase two of the translation process. + */ + public class CFGTranslationPhaseTwo { + + public CFGTranslationPhaseTwo() { + } + + /** + * Perform phase two of the translation. + * + * @param in + * The result of phase one. + * @return a control flow graph that might still contain degenerate + * basic block (such as empty regular basic blocks or + * conditional blocks with the same block as 'then' and 'else' + * sucessor) + */ + public ControlFlowGraph process(PhaseOneResult in) { + + Map<Label, Integer> bindings = in.bindings; + ArrayList<ExtendedNode> nodeList = in.nodeList; + Set<Integer> leaders = in.leaders; + + assert in.nodeList.size() > 0; + + // exit blocks + SpecialBlockImpl regularExitBlock = new SpecialBlockImpl( + SpecialBlockType.EXIT); + SpecialBlockImpl exceptionalExitBlock = new SpecialBlockImpl( + SpecialBlockType.EXCEPTIONAL_EXIT); + + // record missing edges that will be added later + Set<Tuple<? extends SingleSuccessorBlockImpl, Integer, ?>> missingEdges = new MostlySingleton<>(); + + // missing exceptional edges + Set<Tuple<ExceptionBlockImpl, Integer, TypeMirror>> missingExceptionalEdges = new HashSet<>(); + + // create start block + SpecialBlockImpl startBlock = new SpecialBlockImpl( + SpecialBlockType.ENTRY); + missingEdges.add(new Tuple<>(startBlock, 0)); + + // loop through all 'leaders' (while dynamically detecting the + // leaders) + RegularBlockImpl block = new RegularBlockImpl(); + int i = 0; + for (ExtendedNode node : nodeList) { + switch (node.getType()) { + case NODE: + if (leaders.contains(i)) { + RegularBlockImpl b = new RegularBlockImpl(); + block.setSuccessor(b); + block = b; + } + block.addNode(node.getNode()); + node.setBlock(block); + + // does this node end the execution (modeled as an edge to + // the exceptional exit block) + boolean terminatesExecution = node.getTerminatesExecution(); + if (terminatesExecution) { + block.setSuccessor(exceptionalExitBlock); + block = new RegularBlockImpl(); + } + break; + case CONDITIONAL_JUMP: { + ConditionalJump cj = (ConditionalJump) node; + // Exception nodes may fall through to conditional jumps, + // so we set the block which is required for the insertion + // of missing edges. + node.setBlock(block); + assert block != null; + final ConditionalBlockImpl cb = new ConditionalBlockImpl(); + if (cj.getTrueFlowRule() != null) { + cb.setThenFlowRule(cj.getTrueFlowRule()); + } + if (cj.getFalseFlowRule() != null) { + cb.setElseFlowRule(cj.getFalseFlowRule()); + } + block.setSuccessor(cb); + block = new RegularBlockImpl(); + // use two anonymous SingleSuccessorBlockImpl that set the + // 'then' and 'else' successor of the conditional block + final Label thenLabel = cj.getThenLabel(); + final Label elseLabel = cj.getElseLabel(); + missingEdges.add(new Tuple<>( + new SingleSuccessorBlockImpl() { + @Override + public void setSuccessor(BlockImpl successor) { + cb.setThenSuccessor(successor); + } + }, bindings.get(thenLabel))); + missingEdges.add(new Tuple<>( + new SingleSuccessorBlockImpl() { + @Override + public void setSuccessor(BlockImpl successor) { + cb.setElseSuccessor(successor); + } + }, bindings.get(elseLabel))); + break; + } + case UNCONDITIONAL_JUMP: + if (leaders.contains(i)) { + RegularBlockImpl b = new RegularBlockImpl(); + block.setSuccessor(b); + block = b; + } + node.setBlock(block); + if (node.getLabel() == regularExitLabel) { + block.setSuccessor(regularExitBlock); + } else if (node.getLabel() == exceptionalExitLabel) { + block.setSuccessor(exceptionalExitBlock); + } else { + missingEdges.add(new Tuple<>(block, bindings.get(node + .getLabel()))); + } + block = new RegularBlockImpl(); + break; + case EXCEPTION_NODE: + NodeWithExceptionsHolder en = (NodeWithExceptionsHolder) node; + // create new exception block and link with previous block + ExceptionBlockImpl e = new ExceptionBlockImpl(); + Node nn = en.getNode(); + e.setNode(nn); + node.setBlock(e); + block.setSuccessor(e); + block = new RegularBlockImpl(); + + // ensure linking between e and next block (normal edge) + // Note: do not link to the next block for throw statements + // (these throw exceptions for sure) + if (!node.getTerminatesExecution()) { + missingEdges.add(new Tuple<>(e, i + 1)); + } + + // exceptional edges + for (Entry<TypeMirror, Set<Label>> entry : en.getExceptions() + .entrySet()) { + TypeMirror cause = entry.getKey(); + for (Label label : entry.getValue()) { + Integer target = bindings.get(label); + missingExceptionalEdges + .add(new Tuple<ExceptionBlockImpl, Integer, TypeMirror>( + e, target, cause)); + } + } + break; + } + i++; + } + + // add missing edges + for (Tuple<? extends SingleSuccessorBlockImpl, Integer, ?> p : missingEdges) { + Integer index = p.b; + ExtendedNode extendedNode = nodeList.get(index); + BlockImpl target = extendedNode.getBlock(); + SingleSuccessorBlockImpl source = p.a; + source.setSuccessor(target); + } + + // add missing exceptional edges + for (Tuple<ExceptionBlockImpl, Integer, ?> p : missingExceptionalEdges) { + Integer index = p.b; + TypeMirror cause = (TypeMirror) p.c; + ExceptionBlockImpl source = p.a; + if (index == null) { + // edge to exceptional exit + source.addExceptionalSuccessor(exceptionalExitBlock, cause); + } else { + // edge to specific target + ExtendedNode extendedNode = nodeList.get(index); + BlockImpl target = extendedNode.getBlock(); + source.addExceptionalSuccessor(target, cause); + } + } + + return new ControlFlowGraph(startBlock, regularExitBlock, exceptionalExitBlock, in.underlyingAST, + in.treeLookupMap, in.convertedTreeLookupMap, in.returnNodes); + } + } + + /* --------------------------------------------------------- */ + /* Phase One */ + /* --------------------------------------------------------- */ + + /** + * A wrapper object to pass around the result of phase one. For a + * documentation of the fields see {@link CFGTranslationPhaseOne}. + */ + protected static class PhaseOneResult { + + private final IdentityHashMap<Tree, Node> treeLookupMap; + private final IdentityHashMap<Tree, Node> convertedTreeLookupMap; + private final UnderlyingAST underlyingAST; + private final Map<Label, Integer> bindings; + private final ArrayList<ExtendedNode> nodeList; + private final Set<Integer> leaders; + private final List<ReturnNode> returnNodes; + + public PhaseOneResult(UnderlyingAST underlyingAST, + IdentityHashMap<Tree, Node> treeLookupMap, + IdentityHashMap<Tree, Node> convertedTreeLookupMap, + ArrayList<ExtendedNode> nodeList, Map<Label, Integer> bindings, + Set<Integer> leaders, List<ReturnNode> returnNodes) { + this.underlyingAST = underlyingAST; + this.treeLookupMap = treeLookupMap; + this.convertedTreeLookupMap = convertedTreeLookupMap; + this.nodeList = nodeList; + this.bindings = bindings; + this.leaders = leaders; + this.returnNodes = returnNodes; + } + + @Override + public String toString() { + StringBuilder sb = new StringBuilder(); + for (ExtendedNode n : nodeList) { + sb.append(nodeToString(n)); + sb.append("\n"); + } + return sb.toString(); + } + + protected String nodeToString(ExtendedNode n) { + if (n.getType() == ExtendedNodeType.CONDITIONAL_JUMP) { + ConditionalJump t = (ConditionalJump) n; + return "TwoTargetConditionalJump(" + + resolveLabel(t.getThenLabel()) + "," + + resolveLabel(t.getElseLabel()) + ")"; + } else if (n.getType() == ExtendedNodeType.UNCONDITIONAL_JUMP) { + return "UnconditionalJump(" + resolveLabel(n.getLabel()) + ")"; + } else { + return n.toString(); + } + } + + private String resolveLabel(Label label) { + Integer index = bindings.get(label); + if (index == null) { + return "null"; + } + return nodeToString(nodeList.get(index)); + } + + } + + /** + * Class that performs phase one of the translation process. It generates + * the following information: + * <ul> + * <li>A sequence of extended nodes.</li> + * <li>A set of bindings from {@link Label}s to positions in the node + * sequence.</li> + * <li>A set of leader nodes that give rise to basic blocks in phase two.</li> + * <li>A lookup map that gives the mapping from AST tree nodes to + * {@link Node}s.</li> + * </ul> + * + * <p> + * + * The return type of this scanner is {@link Node}. For expressions, the + * corresponding node is returned to allow linking between different nodes. + * + * However, for statements there is usually no single {@link Node} that is + * created, and thus no node is returned (rather, null is returned). + * + * <p> + * + * Every {@code visit*} method is assumed to add at least one extended node + * to the list of nodes (which might only be a jump). + * + */ + public class CFGTranslationPhaseOne extends TreePathScanner<Node, Void> { + + public CFGTranslationPhaseOne() { + } + + /** + * Annotation processing environment and its associated type and tree + * utilities. + */ + protected ProcessingEnvironment env; + protected Elements elements; + protected Types types; + protected Trees trees; + protected TreeBuilder treeBuilder; + protected AnnotationProvider annotationProvider; + + /** + * Current {@link Label} to which a break statement with no label should + * jump, or null if there is no valid destination. + */ + protected /*@Nullable*/ Label breakTargetL; + + /** + * Map from AST label Names to CFG {@link Label}s for breaks. Each + * labeled statement creates two CFG {@link Label}s, one for break and + * one for continue. + */ + protected Map<Name, Label> breakLabels; + + /** + * Current {@link Label} to which a continue statement with no label + * should jump, or null if there is no valid destination. + */ + protected /*@Nullable*/ Label continueTargetL; + + /** + * Map from AST label Names to CFG {@link Label}s for continues. Each + * labeled statement creates two CFG {@link Label}s, one for break and + * one for continue. + */ + protected Map<Name, Label> continueLabels; + + /** + * Maps from AST {@link Tree}s to {@link Node}s. Every Tree that produces + * a value will have at least one corresponding Node. Trees + * that undergo conversions, such as boxing or unboxing, can map to two + * distinct Nodes. The Node for the pre-conversion value is stored + * in the treeLookupMap, while the Node for the post-conversion value + * is stored in the convertedTreeLookupMap. + */ + protected IdentityHashMap<Tree, Node> treeLookupMap; + + /** Map from AST {@link Tree}s to post-conversion {@link Node}s. */ + protected IdentityHashMap<Tree, Node> convertedTreeLookupMap; + + /** The list of extended nodes. */ + protected ArrayList<ExtendedNode> nodeList; + + /** + * The bindings of labels to positions (i.e., indices) in the + * {@code nodeList}. + */ + protected Map<Label, Integer> bindings; + + /** The set of leaders (represented as indices into {@code nodeList}). */ + protected Set<Integer> leaders; + + /** + * All return nodes (if any) encountered. Only includes return + * statements that actually return something + */ + private List<ReturnNode> returnNodes; + + /** + * Nested scopes of try-catch blocks in force at the current + * program point. + */ + private TryStack tryStack; + + /** + * Performs the actual work of phase one. + * + * @param bodyPath + * path to the body of the underlying AST's method + * @param env + * annotation processing environment containing type + * utilities + * @param underlyingAST + * the AST for which the CFG is to be built + * @param exceptionalExitLabel + * the label for exceptional exits from the CFG + * @param treeBuilder + * builder for new AST nodes + * @param annotationProvider + * extracts annotations from AST nodes + * @return the result of phase one + */ + public PhaseOneResult process( + TreePath bodyPath, ProcessingEnvironment env, + UnderlyingAST underlyingAST, Label exceptionalExitLabel, + TreeBuilder treeBuilder, AnnotationProvider annotationProvider) { + this.env = env; + this.tryStack = new TryStack(exceptionalExitLabel); + this.treeBuilder = treeBuilder; + this.annotationProvider = annotationProvider; + elements = env.getElementUtils(); + types = env.getTypeUtils(); + + // initialize lists and maps + treeLookupMap = new IdentityHashMap<>(); + convertedTreeLookupMap = new IdentityHashMap<>(); + nodeList = new ArrayList<>(); + bindings = new HashMap<>(); + leaders = new HashSet<>(); + breakLabels = new HashMap<>(); + continueLabels = new HashMap<>(); + returnNodes = new ArrayList<>(); + + // traverse AST of the method body + scan(bodyPath, null); + + // add marker to indicate that the next block will be the exit block + // Note: if there is a return statement earlier in the method (which + // is always the case for non-void methods), then this is not + // strictly necessary. However, it is also not a problem, as it will + // just generate a degenerated control graph case that will be + // removed in a later phase. + nodeList.add(new UnconditionalJump(regularExitLabel)); + + return new PhaseOneResult(underlyingAST, treeLookupMap, + convertedTreeLookupMap, nodeList, + bindings, leaders, returnNodes); + } + + public PhaseOneResult process( + CompilationUnitTree root, ProcessingEnvironment env, + UnderlyingAST underlyingAST, Label exceptionalExitLabel, + TreeBuilder treeBuilder, AnnotationProvider annotationProvider) { + trees = Trees.instance(env); + TreePath bodyPath = trees.getPath(root, underlyingAST.getCode()); + return process(bodyPath, env, underlyingAST, exceptionalExitLabel, treeBuilder, annotationProvider); + } + + /** + * Perform any actions required when CFG translation creates a + * new Tree that is not part of the original AST. + * + * @param tree the newly created Tree + */ + public void handleArtificialTree(Tree tree) {} + + /* --------------------------------------------------------- */ + /* Nodes and Labels Management */ + /* --------------------------------------------------------- */ + + /** + * Add a node to the lookup map if it not already present. + * + * @param node + * The node to add to the lookup map. + */ + protected void addToLookupMap(Node node) { + Tree tree = node.getTree(); + if (tree == null) { + return; + } + if (!treeLookupMap.containsKey(tree)) { + treeLookupMap.put(tree, node); + } + + Tree enclosingParens = parenMapping.get(tree); + while (enclosingParens != null) { + treeLookupMap.put(enclosingParens, node); + enclosingParens = parenMapping.get(enclosingParens); + } + } + + /** + * Add a node in the post-conversion lookup map. The node + * should refer to a Tree and that Tree should already be in + * the pre-conversion lookup map. This method is used to + * update the Tree-Node mapping with conversion nodes. + * + * @param node + * The node to add to the lookup map. + */ + protected void addToConvertedLookupMap(Node node) { + Tree tree = node.getTree(); + addToConvertedLookupMap(tree, node); + } + + /** + * Add a node in the post-conversion lookup map. The tree + * argument should already be in the pre-conversion lookup + * map. This method is used to update the Tree-Node mapping + * with conversion nodes. + * + * @param tree + * The tree used as a key in the map. + * @param node + * The node to add to the lookup map. + */ + protected void addToConvertedLookupMap(Tree tree, Node node) { + assert tree != null; + assert treeLookupMap.containsKey(tree); + convertedTreeLookupMap.put(tree, node); + } + + /** + * Extend the list of extended nodes with a node. + * + * @param node + * The node to add. + * @return the same node (for convenience) + */ + protected <T extends Node> T extendWithNode(T node) { + addToLookupMap(node); + extendWithExtendedNode(new NodeHolder(node)); + return node; + } + + /** + * Extend the list of extended nodes with a node, where + * {@code node} might throw the exception {@code cause}. + * + * @param node + * The node to add. + * @param cause + * An exception that the node might throw. + * @return the node holder + */ + protected NodeWithExceptionsHolder extendWithNodeWithException(Node node, TypeMirror cause) { + addToLookupMap(node); + return extendWithNodeWithExceptions(node, Collections.singleton(cause)); + } + + /** + * Extend the list of extended nodes with a node, where + * {@code node} might throw any of the exception in + * {@code causes}. + * + * @param node + * The node to add. + * @param causes + * Set of exceptions that the node might throw. + * @return the node holder + */ + protected NodeWithExceptionsHolder extendWithNodeWithExceptions(Node node, + Set<TypeMirror> causes) { + addToLookupMap(node); + Map<TypeMirror, Set<Label>> exceptions = new HashMap<>(); + for (TypeMirror cause : causes) { + exceptions.put(cause, tryStack.possibleLabels(cause)); + } + NodeWithExceptionsHolder exNode = new NodeWithExceptionsHolder( + node, exceptions); + extendWithExtendedNode(exNode); + return exNode; + } + + /** + * Insert {@code node} after {@code pred} in + * the list of extended nodes, or append to the list if + * {@code pred} is not present. + * + * @param node + * The node to add. + * @param pred + * The desired predecessor of node. + * @return the node holder + */ + protected <T extends Node> T insertNodeAfter(T node, Node pred) { + addToLookupMap(node); + insertExtendedNodeAfter(new NodeHolder(node), pred); + return node; + } + + /** + * Insert a {@code node} that might throw the exception + * {@code cause} after {@code pred} in the list of + * extended nodes, or append to the list if {@code pred} + * is not present. + * + * @param node + * The node to add. + * @param causes + * Set of exceptions that the node might throw. + * @param pred + * The desired predecessor of node. + * @return the node holder + */ + protected NodeWithExceptionsHolder insertNodeWithExceptionsAfter(Node node, + Set<TypeMirror> causes, Node pred) { + addToLookupMap(node); + Map<TypeMirror, Set<Label>> exceptions = new HashMap<>(); + for (TypeMirror cause : causes) { + exceptions.put(cause, tryStack.possibleLabels(cause)); + } + NodeWithExceptionsHolder exNode = new NodeWithExceptionsHolder( + node, exceptions); + insertExtendedNodeAfter(exNode, pred); + return exNode; + } + + /** + * Extend the list of extended nodes with an extended node. + * + * @param n + * The extended node. + */ + protected void extendWithExtendedNode(ExtendedNode n) { + nodeList.add(n); + } + + /** + * Insert {@code n} after the node {@code pred} in the + * list of extended nodes, or append {@code n} if {@code pred} + * is not present. + * + * @param n + * The extended node. + * @param pred + * The desired predecessor. + */ + protected void insertExtendedNodeAfter(ExtendedNode n, Node pred) { + int index = -1; + for (int i = 0; i < nodeList.size(); i++) { + ExtendedNode inList = nodeList.get(i); + if (inList instanceof NodeHolder || + inList instanceof NodeWithExceptionsHolder) { + if (inList.getNode() == pred) { + index = i; + break; + } + } + } + if (index != -1) { + nodeList.add(index + 1, n); + // update bindings + for (Entry<Label, Integer> e : bindings.entrySet()) { + if (e.getValue() >= index+1) { + bindings.put(e.getKey(), e.getValue() + 1); + } + } + // update leaders + Set<Integer> newLeaders = new HashSet<>(); + for (Integer l : leaders) { + if (l >= index+1) { + newLeaders.add(l+1); + } else { + newLeaders.add(l); + } + } + leaders = newLeaders; + } else { + nodeList.add(n); + } + } + + /** + * Add the label {@code l} to the extended node that will be placed next + * in the sequence. + */ + protected void addLabelForNextNode(Label l) { + leaders.add(nodeList.size()); + bindings.put(l, nodeList.size()); + } + + /* --------------------------------------------------------- */ + /* Utility Methods */ + /* --------------------------------------------------------- */ + + protected long uid = 0; + protected String uniqueName(String prefix) { + return prefix + "#num" + uid++; + } + + /** + * If the input node is an unboxed primitive type, insert a call to the + * appropriate valueOf method, otherwise leave it alone. + * + * @param node + * in input node + * @return a Node representing the boxed version of the input, which may + * simply be the input node + */ + protected Node box(Node node) { + // For boxing conversion, see JLS 5.1.7 + if (TypesUtils.isPrimitive(node.getType())) { + PrimitiveType primitive = types.getPrimitiveType(node.getType() + .getKind()); + TypeMirror boxedType = types.getDeclaredType(types + .boxedClass(primitive)); + + TypeElement boxedElement = (TypeElement)((DeclaredType)boxedType).asElement(); + IdentifierTree classTree = treeBuilder.buildClassUse(boxedElement); + handleArtificialTree(classTree); + ClassNameNode className = new ClassNameNode(classTree); + className.setInSource(false); + insertNodeAfter(className, node); + + MemberSelectTree valueOfSelect = treeBuilder.buildValueOfMethodAccess(classTree); + handleArtificialTree(valueOfSelect); + MethodAccessNode valueOfAccess = new MethodAccessNode(valueOfSelect, className); + valueOfAccess.setInSource(false); + insertNodeAfter(valueOfAccess, className); + + MethodInvocationTree valueOfCall = + treeBuilder.buildMethodInvocation(valueOfSelect, (ExpressionTree)node.getTree()); + handleArtificialTree(valueOfCall); + Node boxed = new MethodInvocationNode(valueOfCall, valueOfAccess, + Collections.singletonList(node), + getCurrentPath()); + boxed.setInSource(false); + // Add Throwable to account for unchecked exceptions + TypeElement throwableElement = elements + .getTypeElement("java.lang.Throwable"); + addToConvertedLookupMap(node.getTree(), boxed); + insertNodeWithExceptionsAfter(boxed, + Collections.singleton(throwableElement.asType()), valueOfAccess); + return boxed; + } else { + return node; + } + } + + /** + * If the input node is a boxed type, unbox it, otherwise leave it + * alone. + * + * @param node + * in input node + * @return a Node representing the unboxed version of the input, which + * may simply be the input node + */ + protected Node unbox(Node node) { + if (TypesUtils.isBoxedPrimitive(node.getType())) { + + MemberSelectTree primValueSelect = + treeBuilder.buildPrimValueMethodAccess(node.getTree()); + handleArtificialTree(primValueSelect); + MethodAccessNode primValueAccess = new MethodAccessNode(primValueSelect, node); + primValueAccess.setInSource(false); + // Method access may throw NullPointerException + TypeElement npeElement = elements + .getTypeElement("java.lang.NullPointerException"); + insertNodeWithExceptionsAfter(primValueAccess, + Collections.singleton(npeElement.asType()), node); + + MethodInvocationTree primValueCall = + treeBuilder.buildMethodInvocation(primValueSelect); + handleArtificialTree(primValueCall); + Node unboxed = new MethodInvocationNode(primValueCall, primValueAccess, + Collections.<Node>emptyList(), + getCurrentPath()); + unboxed.setInSource(false); + + // Add Throwable to account for unchecked exceptions + TypeElement throwableElement = elements + .getTypeElement("java.lang.Throwable"); + addToConvertedLookupMap(node.getTree(), unboxed); + insertNodeWithExceptionsAfter(unboxed, + Collections.singleton(throwableElement.asType()), primValueAccess); + return unboxed; + } else { + return node; + } + } + + private TreeInfo getTreeInfo(Tree tree) { + final TypeMirror type = InternalUtils.typeOf(tree); + final boolean boxed = TypesUtils.isBoxedPrimitive(type); + final TypeMirror unboxedType = boxed ? types.unboxedType(type) : type; + + final boolean bool = TypesUtils.isBooleanType(type); + final boolean numeric = TypesUtils.isNumeric(unboxedType); + + return new TreeInfo() { + @Override + public boolean isNumeric() { + return numeric; + } + + @Override + public boolean isBoxed() { + return boxed; + } + + @Override + public boolean isBoolean() { + return bool; + } + + @Override + public TypeMirror unboxedType() { + return unboxedType; + } + }; + } + + /** + * @return the unboxed tree if necessary, as described in JLS 5.1.8 + */ + private Node unboxAsNeeded(Node node, boolean boxed) { + return boxed ? unbox(node) : node; + } + + /** + * Convert the input node to String type, if it isn't already. + * + * @param node + * an input node + * @return a Node with the value promoted to String, which may be the + * input node + */ + protected Node stringConversion(Node node) { + // For string conversion, see JLS 5.1.11 + TypeElement stringElement = + elements.getTypeElement("java.lang.String"); + if (!TypesUtils.isString(node.getType())) { + Node converted = new StringConversionNode(node.getTree(), node, + stringElement.asType()); + addToConvertedLookupMap(converted); + insertNodeAfter(converted, node); + return converted; + } else { + return node; + } + } + + /** + * Perform unary numeric promotion on the input node. + * + * @param node + * a node producing a value of numeric primitive or boxed + * type + * @return a Node with the value promoted to the int, long float or + * double, which may be the input node + */ + protected Node unaryNumericPromotion(Node node) { + // For unary numeric promotion, see JLS 5.6.1 + node = unbox(node); + + switch (node.getType().getKind()) { + case BYTE: + case CHAR: + case SHORT: { + TypeMirror intType = types.getPrimitiveType(TypeKind.INT); + Node widened = new WideningConversionNode(node.getTree(), node, intType); + addToConvertedLookupMap(widened); + insertNodeAfter(widened, node); + return widened; + } + default: + // Nothing to do. + break; + } + + return node; + } + + /** + * Returns true if the argument type is a numeric primitive or + * a boxed numeric primitive and false otherwise. + */ + protected boolean isNumericOrBoxed(TypeMirror type) { + if (TypesUtils.isBoxedPrimitive(type)) { + type = types.unboxedType(type); + } + return TypesUtils.isNumeric(type); + } + + /** + * Compute the type to which two numeric types must be promoted + * before performing a binary numeric operation on them. The + * input types must both be numeric and the output type is primitive. + * + * @param left the type of the left operand + * @param right the type of the right operand + * @return a TypeMirror representing the binary numeric promoted type + */ + protected TypeMirror binaryPromotedType(TypeMirror left, TypeMirror right) { + if (TypesUtils.isBoxedPrimitive(left)) { + left = types.unboxedType(left); + } + if (TypesUtils.isBoxedPrimitive(right)) { + right = types.unboxedType(right); + } + TypeKind promotedTypeKind = TypesUtils.widenedNumericType(left, right); + return types.getPrimitiveType(promotedTypeKind); + } + + /** + * Perform binary numeric promotion on the input node to make it match + * the expression type. + * + * @param node + * a node producing a value of numeric primitive or boxed + * type + * @param exprType + * the type to promote the value to + * @return a Node with the value promoted to the exprType, which may be + * the input node + */ + protected Node binaryNumericPromotion(Node node, TypeMirror exprType) { + // For binary numeric promotion, see JLS 5.6.2 + node = unbox(node); + + if (!types.isSameType(node.getType(), exprType)) { + Node widened = new WideningConversionNode(node.getTree(), node, + exprType); + addToConvertedLookupMap(widened); + insertNodeAfter(widened, node); + return widened; + } else { + return node; + } + } + + /** + * Perform widening primitive conversion on the input node to make it + * match the destination type. + * + * @param node + * a node producing a value of numeric primitive type + * @param destType + * the type to widen the value to + * @return a Node with the value widened to the exprType, which may be + * the input node + */ + protected Node widen(Node node, TypeMirror destType) { + // For widening conversion, see JLS 5.1.2 + assert TypesUtils.isPrimitive(node.getType()) + && TypesUtils.isPrimitive(destType) : "widening must be applied to primitive types"; + if (types.isSubtype(node.getType(), destType) + && !types.isSameType(node.getType(), destType)) { + Node widened = new WideningConversionNode(node.getTree(), node, + destType); + addToConvertedLookupMap(widened); + insertNodeAfter(widened, node); + return widened; + } else { + return node; + } + } + + /** + * Perform narrowing conversion on the input node to make it match the + * destination type. + * + * @param node + * a node producing a value of numeric primitive type + * @param destType + * the type to narrow the value to + * @return a Node with the value narrowed to the exprType, which may be + * the input node + */ + protected Node narrow(Node node, TypeMirror destType) { + // For narrowing conversion, see JLS 5.1.3 + assert TypesUtils.isPrimitive(node.getType()) + && TypesUtils.isPrimitive(destType) : "narrowing must be applied to primitive types"; + if (types.isSubtype(destType, node.getType()) + && !types.isSameType(destType, node.getType())) { + Node narrowed = new NarrowingConversionNode(node.getTree(), node, + destType); + addToConvertedLookupMap(narrowed); + insertNodeAfter(narrowed, node); + return narrowed; + } else { + return node; + } + } + + /** + * Perform narrowing conversion and optionally boxing conversion on the + * input node to make it match the destination type. + * + * @param node + * a node producing a value of numeric primitive type + * @param destType + * the type to narrow the value to (possibly boxed) + * @return a Node with the value narrowed and boxed to the destType, + * which may be the input node + */ + protected Node narrowAndBox(Node node, TypeMirror destType) { + if (TypesUtils.isBoxedPrimitive(destType)) { + return box(narrow(node, types.unboxedType(destType))); + } else { + return narrow(node, destType); + } + } + + + /** + * Return whether a conversion from the type of the node to varType + * requires narrowing. + * + * @param varType the type of a variable (or general LHS) to be converted to + * @param node a node whose value is being converted + * @return whether this conversion requires narrowing to succeed + */ + protected boolean conversionRequiresNarrowing(TypeMirror varType, Node node) { + // Narrowing is restricted to cases where the left hand side + // is byte, char, short or Byte, Char, Short and the right + // hand side is a constant. + TypeMirror unboxedVarType = TypesUtils.isBoxedPrimitive(varType) ? types + .unboxedType(varType) : varType; + TypeKind unboxedVarKind = unboxedVarType.getKind(); + boolean isLeftNarrowableTo = unboxedVarKind == TypeKind.BYTE + || unboxedVarKind == TypeKind.SHORT + || unboxedVarKind == TypeKind.CHAR; + boolean isRightConstant = node instanceof ValueLiteralNode; + return isLeftNarrowableTo && isRightConstant; + } + + + /** + * Assignment conversion and method invocation conversion are almost + * identical, except that assignment conversion allows narrowing. We + * factor out the common logic here. + * + * @param node + * a Node producing a value + * @param varType + * the type of a variable + * @param contextAllowsNarrowing + * whether to allow narrowing (for assignment conversion) or + * not (for method invocation conversion) + * @return a Node with the value converted to the type of the variable, + * which may be the input node itself + */ + protected Node commonConvert(Node node, TypeMirror varType, + boolean contextAllowsNarrowing) { + // For assignment conversion, see JLS 5.2 + // For method invocation conversion, see JLS 5.3 + + // Check for identical types or "identity conversion" + TypeMirror nodeType = node.getType(); + boolean isSameType = types.isSameType(nodeType, varType); + if (isSameType) { + return node; + } + + boolean isRightNumeric = TypesUtils.isNumeric(nodeType); + boolean isRightPrimitive = TypesUtils.isPrimitive(nodeType); + boolean isRightBoxed = TypesUtils.isBoxedPrimitive(nodeType); + boolean isRightReference = nodeType instanceof ReferenceType; + boolean isLeftNumeric = TypesUtils.isNumeric(varType); + boolean isLeftPrimitive = TypesUtils.isPrimitive(varType); + // boolean isLeftBoxed = TypesUtils.isBoxedPrimitive(varType); + boolean isLeftReference = varType instanceof ReferenceType; + boolean isSubtype = types.isSubtype(nodeType, varType); + + if (isRightNumeric && isLeftNumeric && isSubtype) { + node = widen(node, varType); + nodeType = node.getType(); + } else if (isRightReference && isLeftReference && isSubtype) { + // widening reference conversion is a no-op, but if it + // applies, then later conversions do not. + } else if (isRightPrimitive && isLeftReference) { + if (contextAllowsNarrowing && conversionRequiresNarrowing(varType, node)) { + node = narrowAndBox(node, varType); + nodeType = node.getType(); + } else { + node = box(node); + nodeType = node.getType(); + } + } else if (isRightBoxed && isLeftPrimitive) { + node = unbox(node); + nodeType = node.getType(); + + if (types.isSubtype(nodeType, varType) + && !types.isSameType(nodeType, varType)) { + node = widen(node, varType); + nodeType = node.getType(); + } + } else if (isRightPrimitive && isLeftPrimitive) { + if (contextAllowsNarrowing && conversionRequiresNarrowing(varType, node)) { + node = narrow(node, varType); + nodeType = node.getType(); + } + } + + // TODO: if checkers need to know about null references of + // a particular type, add logic for them here. + + return node; + } + + /** + * Perform assignment conversion so that it can be assigned to a + * variable of the given type. + * + * @param node + * a Node producing a value + * @param varType + * the type of a variable + * @return a Node with the value converted to the type of the variable, + * which may be the input node itself + */ + protected Node assignConvert(Node node, TypeMirror varType) { + return commonConvert(node, varType, true); + } + + /** + * Perform method invocation conversion so that the node can be passed + * as a formal parameter of the given type. + * + * @param node + * a Node producing a value + * @param formalType + * the type of a formal parameter + * @return a Node with the value converted to the type of the formal, + * which may be the input node itself + */ + protected Node methodInvocationConvert(Node node, TypeMirror formalType) { + return commonConvert(node, formalType, false); + } + + /** + * Given a method element and as list of argument expressions, return a + * list of {@link Node}s representing the arguments converted for a call + * of the method. This method applies to both method invocations and + * constructor calls. + * + * @param method + * an ExecutableElement representing a method to be called + * @param actualExprs + * a List of argument expressions to a call + * @return a List of {@link Node}s representing arguments after + * conversions required by a call to this method. + */ + protected List<Node> convertCallArguments(ExecutableElement method, + List<? extends ExpressionTree> actualExprs) { + // NOTE: It is important to convert one method argument before + // generating CFG nodes for the next argument, since label binding + // expects nodes to be generated in execution order. Therefore, + // this method first determines which conversions need to be applied + // and then iterates over the actual arguments. + List<? extends VariableElement> formals = method.getParameters(); + + ArrayList<Node> convertedNodes = new ArrayList<Node>(); + + int numFormals = formals.size(); + int numActuals = actualExprs.size(); + if (method.isVarArgs()) { + // Create a new array argument if the actuals outnumber + // the formals, or if the last actual is not assignable + // to the last formal. + int lastArgIndex = numFormals - 1; + TypeMirror lastParamType = formals.get(lastArgIndex).asType(); + List<Node> dimensions = new ArrayList<>(); + List<Node> initializers = new ArrayList<>(); + + if (numActuals == numFormals - 1) { + // Apply method invocation conversion to all actual + // arguments, then create and append an empty array + for (int i = 0; i < numActuals; i++) { + Node actualVal = scan(actualExprs.get(i), null); + convertedNodes.add(methodInvocationConvert(actualVal, + formals.get(i).asType())); + } + + Node lastArgument = new ArrayCreationNode(null, + lastParamType, dimensions, initializers); + extendWithNode(lastArgument); + + convertedNodes.add(lastArgument); + } else { + TypeMirror actualType = InternalUtils.typeOf(actualExprs + .get(lastArgIndex)); + if (numActuals == numFormals + && types.isAssignable(actualType, lastParamType)) { + // Normal call with no array creation, apply method + // invocation conversion to all arguments. + for (int i = 0; i < numActuals; i++) { + Node actualVal = scan(actualExprs.get(i), null); + convertedNodes.add(methodInvocationConvert(actualVal, + formals.get(i).asType())); + } + } else { + assert lastParamType instanceof ArrayType : + "variable argument formal must be an array"; + // Apply method invocation conversion to lastArgIndex + // arguments and use the remaining ones to initialize + // an array. + for (int i = 0; i < lastArgIndex; i++) { + Node actualVal = scan(actualExprs.get(i), null); + convertedNodes.add(methodInvocationConvert(actualVal, + formals.get(i).asType())); + } + + TypeMirror elemType = + ((ArrayType)lastParamType).getComponentType(); + for (int i = lastArgIndex; i < numActuals; i++) { + Node actualVal = scan(actualExprs.get(i), null); + initializers.add(assignConvert(actualVal, elemType)); + } + + Node lastArgument = new ArrayCreationNode(null, + lastParamType, dimensions, initializers); + extendWithNode(lastArgument); + convertedNodes.add(lastArgument); + } + } + } else { + for (int i = 0; i < numActuals; i++) { + Node actualVal = scan(actualExprs.get(i), null); + convertedNodes.add(methodInvocationConvert(actualVal, + formals.get(i).asType())); + } + } + + return convertedNodes; + } + + /** + * Convert an operand of a conditional expression to the type of the + * whole expression. + * + * @param node + * a node occurring as the second or third operand of + * a conditional expression + * @param destType + * the type to promote the value to + * @return a Node with the value promoted to the destType, which may be + * the input node + */ + protected Node conditionalExprPromotion(Node node, TypeMirror destType) { + // For rules on converting operands of conditional expressions, + // JLS 15.25 + TypeMirror nodeType = node.getType(); + + // If the operand is already the same type as the whole + // expression, then do nothing. + if (types.isSameType(nodeType, destType)) { + return node; + } + + // If the operand is a primitive and the whole expression is + // boxed, then apply boxing. + if (TypesUtils.isPrimitive(nodeType) && + TypesUtils.isBoxedPrimitive(destType)) { + return box(node); + } + + // If the operand is byte or Byte and the whole expression is + // short, then convert to short. + boolean isBoxedPrimitive = TypesUtils.isBoxedPrimitive(nodeType); + TypeMirror unboxedNodeType = + isBoxedPrimitive ? types.unboxedType(nodeType) : nodeType; + TypeMirror unboxedDestType = + TypesUtils.isBoxedPrimitive(destType) ? + types.unboxedType(destType) : destType; + if (TypesUtils.isNumeric(unboxedNodeType) && + TypesUtils.isNumeric(unboxedDestType)) { + if (unboxedNodeType.getKind() == TypeKind.BYTE && + destType.getKind() == TypeKind.SHORT) { + if (isBoxedPrimitive) { + node = unbox(node); + } + return widen(node, destType); + } + + // If the operand is Byte, Short or Character and the whole expression + // is the unboxed version of it, then apply unboxing. + TypeKind destKind = destType.getKind(); + if (destKind == TypeKind.BYTE || destKind == TypeKind.CHAR || + destKind == TypeKind.SHORT) { + if (isBoxedPrimitive) { + return unbox(node); + } else if (nodeType.getKind() == TypeKind.INT) { + return narrow(node, destType); + } + } + + return binaryNumericPromotion(node, destType); + } + + // For the final case in JLS 15.25, apply boxing but not lub. + if (TypesUtils.isPrimitive(nodeType) && + (destType.getKind() == TypeKind.DECLARED || + destType.getKind() == TypeKind.UNION || + destType.getKind() == TypeKind.INTERSECTION)) { + return box(node); + } + + return node; + } + + /** + * Returns the label {@link Name} of the leaf in the argument path, or + * null if the leaf is not a labeled statement. + */ + protected /*@Nullable*/ Name getLabel(TreePath path) { + if (path.getParentPath() != null) { + Tree parent = path.getParentPath().getLeaf(); + if (parent.getKind() == Tree.Kind.LABELED_STATEMENT) { + return ((LabeledStatementTree) parent).getLabel(); + } + } + return null; + } + + /* --------------------------------------------------------- */ + /* Visitor Methods */ + /* --------------------------------------------------------- */ + + @Override + public Node visitAnnotatedType(AnnotatedTypeTree tree, Void p) { + return scan(tree.getUnderlyingType(), p); + } + + @Override + public Node visitAnnotation(AnnotationTree tree, Void p) { + assert false : "AnnotationTree is unexpected in AST to CFG translation"; + return null; + } + + @Override + public MethodInvocationNode visitMethodInvocation(MethodInvocationTree tree, Void p) { + + // see JLS 15.12.4 + + // First, compute the receiver, if any (15.12.4.1) + // Second, evaluate the actual arguments, left to right and + // possibly some arguments are stored into an array for variable + // arguments calls (15.12.4.2) + // Third, test the receiver, if any, for nullness (15.12.4.4) + // Fourth, convert the arguments to the type of the formal + // parameters (15.12.4.5) + // Fifth, if the method is synchronized, lock the receiving + // object or class (15.12.4.5) + ExecutableElement method = TreeUtils.elementFromUse(tree); + // TODO? Variable wasn't used. + // boolean isBooleanMethod = TypesUtils.isBooleanType(method.getReturnType()); + + ExpressionTree methodSelect = tree.getMethodSelect(); + assert TreeUtils.isMethodAccess(methodSelect) : "Expected a method access, but got: " + methodSelect; + + List<? extends ExpressionTree> actualExprs = tree.getArguments(); + + // Look up method to invoke and possibly throw NullPointerException + Node receiver = getReceiver(methodSelect, + TreeUtils.enclosingClass(getCurrentPath())); + + MethodAccessNode target = new MethodAccessNode(methodSelect, + receiver); + + ExecutableElement element = TreeUtils.elementFromUse(tree); + if (ElementUtils.isStatic(element) || + receiver instanceof ThisLiteralNode) { + // No NullPointerException can be thrown, use normal node + extendWithNode(target); + } else { + TypeElement npeElement = elements + .getTypeElement("java.lang.NullPointerException"); + extendWithNodeWithException(target, npeElement.asType()); + } + + List<Node> arguments = new ArrayList<>(); + + // Don't convert arguments for enum super calls. The AST contains + // no actual arguments, while the method element expects two arguments, + // leading to an exception in convertCallArguments. Since no actual + // arguments are present in the AST that is being checked, it shouldn't + // cause any harm to omit the conversions. + // See also BaseTypeVisitor.visitMethodInvocation and + // QualifierPolymorphism.annotate + if (!TreeUtils.isEnumSuper(tree)) { + arguments = convertCallArguments(method, actualExprs); + } + + // TODO: lock the receiver for synchronized methods + + MethodInvocationNode node = new MethodInvocationNode(tree, target, arguments, getCurrentPath()); + + Set<TypeMirror> thrownSet = new HashSet<>(); + // Add exceptions explicitly mentioned in the throws clause. + List<? extends TypeMirror> thrownTypes = element.getThrownTypes(); + thrownSet.addAll(thrownTypes); + // Add Throwable to account for unchecked exceptions + TypeElement throwableElement = elements + .getTypeElement("java.lang.Throwable"); + thrownSet.add(throwableElement.asType()); + + ExtendedNode extendedNode = extendWithNodeWithExceptions(node, thrownSet); + + /* Check for the TerminatesExecution annotation. */ + Element methodElement = InternalUtils.symbol(tree); + boolean terminatesExecution = annotationProvider.getDeclAnnotation( + methodElement, TerminatesExecution.class) != null; + if (terminatesExecution) { + extendedNode.setTerminatesExecution(true); + } + + return node; + } + + @Override + public Node visitAssert(AssertTree tree, Void p) { + + // see JLS 14.10 + + // If assertions are enabled, then we can just translate the + // assertion. + if (assumeAssertionsEnabled || assumeAssertionsEnabledFor(tree)) { + translateAssertWithAssertionsEnabled(tree); + return null; + } + + // If assertions are disabled, then nothing is executed. + if (assumeAssertionsDisabled) { + return null; + } + + + // Otherwise, we don't know if assertions are enabled, so we use a + // variable "ea" and case-split on it. One branch does execute the + // assertion, while the other assumes assertions are disabled. + VariableTree ea = getAssertionsEnabledVariable(); + + // all necessary labels + Label assertionEnabled = new Label(); + Label assertionDisabled = new Label(); + + extendWithNode(new LocalVariableNode(ea)); + extendWithExtendedNode(new ConditionalJump(assertionEnabled, + assertionDisabled)); + + // 'then' branch (i.e. check the assertion) + addLabelForNextNode(assertionEnabled); + + translateAssertWithAssertionsEnabled(tree); + + // 'else' branch + addLabelForNextNode(assertionDisabled); + + return null; + } + + /** + * Should assertions be assumed to be executed for a given + * {@link AssertTree}? False by default. + */ + protected boolean assumeAssertionsEnabledFor(AssertTree tree) { + return false; + } + + /** + * The {@link VariableTree} that indicates whether assertions are + * enabled or not. + */ + protected VariableTree ea = null; + + /** + * Get a synthetic {@link VariableTree} that indicates whether assertions are + * enabled or not. + */ + protected VariableTree getAssertionsEnabledVariable() { + if (ea == null) { + String name = uniqueName("assertionsEnabled"); + MethodTree enclosingMethod = TreeUtils + .enclosingMethod(getCurrentPath()); + Element owner; + if (enclosingMethod != null) { + owner = TreeUtils.elementFromDeclaration(enclosingMethod); + } else { + ClassTree enclosingClass = TreeUtils.enclosingClass(getCurrentPath()); + owner = TreeUtils.elementFromDeclaration(enclosingClass); + } + ExpressionTree initializer = null; + ea = treeBuilder.buildVariableDecl( + types.getPrimitiveType(TypeKind.BOOLEAN), name, owner, + initializer); + } + return ea; + } + + /** + * Translates an assertion statement to the correct CFG nodes. The + * translation assumes that assertions are enabled. + */ + protected void translateAssertWithAssertionsEnabled(AssertTree tree) { + + // all necessary labels + Label assertEnd = new Label(); + Label elseEntry = new Label(); + + // basic block for the condition + Node condition = unbox(scan(tree.getCondition(), null)); + ConditionalJump cjump = new ConditionalJump(assertEnd, elseEntry); + extendWithExtendedNode(cjump); + + // else branch + Node detail = null; + addLabelForNextNode(elseEntry); + if (tree.getDetail() != null) { + detail = scan(tree.getDetail(), null); + } + TypeElement assertException = elements + .getTypeElement("java.lang.AssertionError"); + AssertionErrorNode assertNode = new AssertionErrorNode(tree, + condition, detail, assertException.asType()); + extendWithNode(assertNode); + NodeWithExceptionsHolder exNode = extendWithNodeWithException( + new ThrowNode(null, assertNode, env.getTypeUtils()), assertException.asType()); + exNode.setTerminatesExecution(true); + + // then branch (nothing happens) + addLabelForNextNode(assertEnd); + } + + @Override + public Node visitAssignment(AssignmentTree tree, Void p) { + + // see JLS 15.26.1 + + AssignmentNode assignmentNode; + ExpressionTree variable = tree.getVariable(); + TypeMirror varType = InternalUtils.typeOf(variable); + + // case 1: field access + if (TreeUtils.isFieldAccess(variable)) { + // visit receiver + Node receiver = getReceiver(variable, + TreeUtils.enclosingClass(getCurrentPath())); + + // visit expression + Node expression = scan(tree.getExpression(), p); + expression = assignConvert(expression, varType); + + // visit field access (throws null-pointer exception) + FieldAccessNode target = new FieldAccessNode(variable, receiver); + target.setLValue(); + + Element element = TreeUtils.elementFromUse(variable); + if (ElementUtils.isStatic(element) || + receiver instanceof ThisLiteralNode) { + // No NullPointerException can be thrown, use normal node + extendWithNode(target); + } else { + TypeElement npeElement = elements + .getTypeElement("java.lang.NullPointerException"); + extendWithNodeWithException(target, npeElement.asType()); + } + + // add assignment node + assignmentNode = new AssignmentNode(tree, + target, expression); + extendWithNode(assignmentNode); + } + + // case 2: other cases + else { + Node target = scan(variable, p); + target.setLValue(); + + assignmentNode = translateAssignment(tree, target, + tree.getExpression()); + } + + return assignmentNode; + } + + /** + * Translate an assignment. + */ + protected AssignmentNode translateAssignment(Tree tree, Node target, + ExpressionTree rhs) { + Node expression = scan(rhs, null); + return translateAssignment(tree, target, expression); + } + + /** + * Translate an assignment where the RHS has already been scanned. + */ + protected AssignmentNode translateAssignment(Tree tree, Node target, + Node expression) { + assert tree instanceof AssignmentTree + || tree instanceof VariableTree; + target.setLValue(); + expression = assignConvert(expression, target.getType()); + AssignmentNode assignmentNode = new AssignmentNode(tree, target, + expression); + extendWithNode(assignmentNode); + return assignmentNode; + } + + /** + * Note 1: Requires {@code tree} to be a field or method access + * tree. + * <p> + * Note 2: Visits the receiver and adds all necessary blocks to the CFG. + * + * @param tree + * the field access tree containing the receiver + * @param classTree + * the ClassTree enclosing the field access + * @return the receiver of the field access + */ + private Node getReceiver(Tree tree, ClassTree classTree) { + assert TreeUtils.isFieldAccess(tree) + || TreeUtils.isMethodAccess(tree); + if (tree.getKind().equals(Tree.Kind.MEMBER_SELECT)) { + MemberSelectTree mtree = (MemberSelectTree) tree; + return scan(mtree.getExpression(), null); + } else { + TypeMirror classType = InternalUtils.typeOf(classTree); + Node node = new ImplicitThisLiteralNode(classType); + extendWithNode(node); + return node; + } + } + + /** + * Map an operation with assignment to the corresponding operation + * without assignment. + * + * @param kind a Tree.Kind representing an operation with assignment + * @return the Tree.Kind for the same operation without assignment + */ + protected Tree.Kind withoutAssignment(Tree.Kind kind) { + switch (kind) { + case DIVIDE_ASSIGNMENT: + return Tree.Kind.DIVIDE; + case MULTIPLY_ASSIGNMENT: + return Tree.Kind.MULTIPLY; + case REMAINDER_ASSIGNMENT: + return Tree.Kind.REMAINDER; + case MINUS_ASSIGNMENT: + return Tree.Kind.MINUS; + case PLUS_ASSIGNMENT: + return Tree.Kind.PLUS; + case LEFT_SHIFT_ASSIGNMENT: + return Tree.Kind.LEFT_SHIFT; + case RIGHT_SHIFT_ASSIGNMENT: + return Tree.Kind.RIGHT_SHIFT; + case UNSIGNED_RIGHT_SHIFT_ASSIGNMENT: + return Tree.Kind.UNSIGNED_RIGHT_SHIFT; + case AND_ASSIGNMENT: + return Tree.Kind.AND; + case OR_ASSIGNMENT: + return Tree.Kind.OR; + case XOR_ASSIGNMENT: + return Tree.Kind.XOR; + default: + return Tree.Kind.ERRONEOUS; + } + } + + + @Override + public Node visitCompoundAssignment(CompoundAssignmentTree tree, Void p) { + // According the JLS 15.26.2, E1 op= E2 is equivalent to + // E1 = (T) ((E1) op (E2)), where T is the type of E1, + // except that E1 is evaluated only once. + // + + Tree.Kind kind = tree.getKind(); + switch (kind) { + case DIVIDE_ASSIGNMENT: + case MULTIPLY_ASSIGNMENT: + case REMAINDER_ASSIGNMENT: { + // see JLS 15.17 and 15.26.2 + Node targetLHS = scan(tree.getVariable(), p); + Node value = scan(tree.getExpression(), p); + + TypeMirror exprType = InternalUtils.typeOf(tree); + TypeMirror leftType = InternalUtils.typeOf(tree.getVariable()); + TypeMirror rightType = InternalUtils.typeOf(tree.getExpression()); + TypeMirror promotedType = binaryPromotedType(leftType, rightType); + Node targetRHS = binaryNumericPromotion(targetLHS, promotedType); + value = binaryNumericPromotion(value, promotedType); + + BinaryTree operTree = treeBuilder.buildBinary(promotedType, withoutAssignment(kind), + tree.getVariable(), tree.getExpression()); + handleArtificialTree(operTree); + Node operNode; + if (kind == Tree.Kind.MULTIPLY_ASSIGNMENT) { + operNode = new NumericalMultiplicationNode(operTree, targetRHS, value); + } else if (kind == Tree.Kind.DIVIDE_ASSIGNMENT) { + if (TypesUtils.isIntegral(exprType)) { + operNode = new IntegerDivisionNode(operTree, targetRHS, value); + } else { + operNode = new FloatingDivisionNode(operTree, targetRHS, value); + } + } else { + assert kind == Kind.REMAINDER_ASSIGNMENT; + if (TypesUtils.isIntegral(exprType)) { + operNode = new IntegerRemainderNode(operTree, targetRHS, value); + } else { + operNode = new FloatingRemainderNode(operTree, targetRHS, value); + } + } + extendWithNode(operNode); + + TypeCastTree castTree = treeBuilder.buildTypeCast(leftType, operTree); + handleArtificialTree(castTree); + TypeCastNode castNode = new TypeCastNode(castTree, operNode, leftType); + castNode.setInSource(false); + extendWithNode(castNode); + + AssignmentNode assignNode = new AssignmentNode(tree, targetLHS, castNode); + extendWithNode(assignNode); + return assignNode; + } + + case MINUS_ASSIGNMENT: + case PLUS_ASSIGNMENT: { + // see JLS 15.18 and 15.26.2 + + Node targetLHS = scan(tree.getVariable(), p); + Node value = scan(tree.getExpression(), p); + + TypeMirror leftType = InternalUtils.typeOf(tree.getVariable()); + TypeMirror rightType = InternalUtils.typeOf(tree.getExpression()); + + if (TypesUtils.isString(leftType) || TypesUtils.isString(rightType)) { + assert (kind == Tree.Kind.PLUS_ASSIGNMENT); + Node targetRHS = stringConversion(targetLHS); + value = stringConversion(value); + Node r = new StringConcatenateAssignmentNode(tree, targetRHS, value); + extendWithNode(r); + return r; + } else { + TypeMirror promotedType = binaryPromotedType(leftType, rightType); + Node targetRHS = binaryNumericPromotion(targetLHS, promotedType); + value = binaryNumericPromotion(value, promotedType); + + BinaryTree operTree = treeBuilder.buildBinary(promotedType, withoutAssignment(kind), + tree.getVariable(), tree.getExpression()); + handleArtificialTree(operTree); + Node operNode; + if (kind == Tree.Kind.PLUS_ASSIGNMENT) { + operNode = new NumericalAdditionNode(operTree, targetRHS, value); + } else { + assert kind == Kind.MINUS_ASSIGNMENT; + operNode = new NumericalSubtractionNode(operTree, targetRHS, value); + } + extendWithNode(operNode); + + TypeCastTree castTree = treeBuilder.buildTypeCast(leftType, operTree); + handleArtificialTree(castTree); + TypeCastNode castNode = new TypeCastNode(castTree, operNode, leftType); + castNode.setInSource(false); + extendWithNode(castNode); + + // Map the compound assignment tree to an assignment node, which + // will have the correct type. + AssignmentNode assignNode = new AssignmentNode(tree, targetLHS, castNode); + extendWithNode(assignNode); + return assignNode; + } + } + + case LEFT_SHIFT_ASSIGNMENT: + case RIGHT_SHIFT_ASSIGNMENT: + case UNSIGNED_RIGHT_SHIFT_ASSIGNMENT: { + // see JLS 15.19 and 15.26.2 + Node targetLHS = scan(tree.getVariable(), p); + Node value = scan(tree.getExpression(), p); + + TypeMirror leftType = InternalUtils.typeOf(tree.getVariable()); + + Node targetRHS = unaryNumericPromotion(targetLHS); + value = unaryNumericPromotion(value); + + BinaryTree operTree = treeBuilder.buildBinary(leftType, withoutAssignment(kind), + tree.getVariable(), tree.getExpression()); + handleArtificialTree(operTree); + Node operNode; + if (kind == Tree.Kind.LEFT_SHIFT_ASSIGNMENT) { + operNode = new LeftShiftNode(operTree, targetRHS, value); + } else if (kind == Tree.Kind.RIGHT_SHIFT_ASSIGNMENT) { + operNode = new SignedRightShiftNode(operTree, targetRHS, value); + } else { + assert kind == Kind.UNSIGNED_RIGHT_SHIFT_ASSIGNMENT; + operNode = new UnsignedRightShiftNode(operTree, targetRHS, value); + } + extendWithNode(operNode); + + TypeCastTree castTree = treeBuilder.buildTypeCast(leftType, operTree); + handleArtificialTree(castTree); + TypeCastNode castNode = new TypeCastNode(castTree, operNode, leftType); + castNode.setInSource(false); + extendWithNode(castNode); + + AssignmentNode assignNode = new AssignmentNode(tree, targetLHS, castNode); + extendWithNode(assignNode); + return assignNode; + } + + case AND_ASSIGNMENT: + case OR_ASSIGNMENT: + case XOR_ASSIGNMENT: + // see JLS 15.22 + Node targetLHS = scan(tree.getVariable(), p); + Node value = scan(tree.getExpression(), p); + + TypeMirror leftType = InternalUtils.typeOf(tree.getVariable()); + TypeMirror rightType = InternalUtils.typeOf(tree.getExpression()); + + Node targetRHS = null; + if (isNumericOrBoxed(leftType) && isNumericOrBoxed(rightType)) { + TypeMirror promotedType = binaryPromotedType(leftType, rightType); + targetRHS = binaryNumericPromotion(targetLHS, promotedType); + value = binaryNumericPromotion(value, promotedType); + } else if (TypesUtils.isBooleanType(leftType) && + TypesUtils.isBooleanType(rightType)) { + targetRHS = unbox(targetLHS); + value = unbox(value); + } else { + assert false : + "Both argument to logical operation must be numeric or boolean"; + } + + BinaryTree operTree = treeBuilder.buildBinary(leftType, withoutAssignment(kind), + tree.getVariable(), tree.getExpression()); + handleArtificialTree(operTree); + Node operNode; + if (kind == Tree.Kind.AND_ASSIGNMENT) { + operNode = new BitwiseAndNode(operTree, targetRHS, value); + } else if (kind == Tree.Kind.OR_ASSIGNMENT) { + operNode = new BitwiseOrNode(operTree, targetRHS, value); + } else { + assert kind == Kind.XOR_ASSIGNMENT; + operNode = new BitwiseXorNode(operTree, targetRHS, value); + } + extendWithNode(operNode); + + TypeCastTree castTree = treeBuilder.buildTypeCast(leftType, operTree); + handleArtificialTree(castTree); + TypeCastNode castNode = new TypeCastNode(castTree, operNode, leftType); + castNode.setInSource(false); + extendWithNode(castNode); + + AssignmentNode assignNode = new AssignmentNode(tree, targetLHS, castNode); + extendWithNode(assignNode); + return assignNode; + default: + assert false : "unexpected compound assignment type"; + break; + } + assert false : "unexpected compound assignment type"; + return null; + } + + @Override + public Node visitBinary(BinaryTree tree, Void p) { + // Note that for binary operations it is important to perform any required + // promotion on the left operand before generating any Nodes for the right + // operand, because labels must be inserted AFTER ALL preceding Nodes and + // BEFORE ALL following Nodes. + Node r = null; + Tree leftTree = tree.getLeftOperand(); + Tree rightTree = tree.getRightOperand(); + + Tree.Kind kind = tree.getKind(); + switch (kind) { + case DIVIDE: + case MULTIPLY: + case REMAINDER: { + // see JLS 15.17 + + TypeMirror exprType = InternalUtils.typeOf(tree); + TypeMirror leftType = InternalUtils.typeOf(leftTree); + TypeMirror rightType = InternalUtils.typeOf(rightTree); + TypeMirror promotedType = binaryPromotedType(leftType, rightType); + + Node left = binaryNumericPromotion(scan(leftTree, p), promotedType); + Node right = binaryNumericPromotion(scan(rightTree, p), promotedType); + + if (kind == Tree.Kind.MULTIPLY) { + r = new NumericalMultiplicationNode(tree, left, right); + } else if (kind == Tree.Kind.DIVIDE) { + if (TypesUtils.isIntegral(exprType)) { + r = new IntegerDivisionNode(tree, left, right); + } else { + r = new FloatingDivisionNode(tree, left, right); + } + } else { + assert kind == Kind.REMAINDER; + if (TypesUtils.isIntegral(exprType)) { + r = new IntegerRemainderNode(tree, left, right); + } else { + r = new FloatingRemainderNode(tree, left, right); + } + } + break; + } + + case MINUS: + case PLUS: { + // see JLS 15.18 + + // TypeMirror exprType = InternalUtils.typeOf(tree); + TypeMirror leftType = InternalUtils.typeOf(leftTree); + TypeMirror rightType = InternalUtils.typeOf(rightTree); + + if (TypesUtils.isString(leftType) || TypesUtils.isString(rightType)) { + assert (kind == Tree.Kind.PLUS); + Node left = stringConversion(scan(leftTree, p)); + Node right = stringConversion(scan(rightTree, p)); + r = new StringConcatenateNode(tree, left, right); + } else { + TypeMirror promotedType = binaryPromotedType(leftType, rightType); + Node left = binaryNumericPromotion(scan(leftTree, p), promotedType); + Node right = binaryNumericPromotion(scan(rightTree, p), promotedType); + + // TODO: Decide whether to deal with floating-point value + // set conversion. + if (kind == Tree.Kind.PLUS) { + r = new NumericalAdditionNode(tree, left, right); + } else { + assert kind == Kind.MINUS; + r = new NumericalSubtractionNode(tree, left, right); + } + } + break; + } + + case LEFT_SHIFT: + case RIGHT_SHIFT: + case UNSIGNED_RIGHT_SHIFT: { + // see JLS 15.19 + + Node left = unaryNumericPromotion(scan(leftTree, p)); + Node right = unaryNumericPromotion(scan(rightTree, p)); + + if (kind == Tree.Kind.LEFT_SHIFT) { + r = new LeftShiftNode(tree, left, right); + } else if (kind == Tree.Kind.RIGHT_SHIFT) { + r = new SignedRightShiftNode(tree, left, right); + } else { + assert kind == Kind.UNSIGNED_RIGHT_SHIFT; + r = new UnsignedRightShiftNode(tree, left, right); + } + break; + } + + case GREATER_THAN: + case GREATER_THAN_EQUAL: + case LESS_THAN: + case LESS_THAN_EQUAL: { + // see JLS 15.20.1 + TypeMirror leftType = InternalUtils.typeOf(leftTree); + if (TypesUtils.isBoxedPrimitive(leftType)) { + leftType = types.unboxedType(leftType); + } + + TypeMirror rightType = InternalUtils.typeOf(rightTree); + if (TypesUtils.isBoxedPrimitive(rightType)) { + rightType = types.unboxedType(rightType); + } + + TypeMirror promotedType = binaryPromotedType(leftType, rightType); + Node left = binaryNumericPromotion(scan(leftTree, p), promotedType); + Node right = binaryNumericPromotion(scan(rightTree, p), promotedType); + + Node node; + if (kind == Tree.Kind.GREATER_THAN) { + node = new GreaterThanNode(tree, left, right); + } else if (kind == Tree.Kind.GREATER_THAN_EQUAL) { + node = new GreaterThanOrEqualNode(tree, left, right); + } else if (kind == Tree.Kind.LESS_THAN) { + node = new LessThanNode(tree, left, right); + } else { + assert kind == Tree.Kind.LESS_THAN_EQUAL; + node = new LessThanOrEqualNode(tree, left, right); + } + + extendWithNode(node); + + return node; + } + + case EQUAL_TO: + case NOT_EQUAL_TO: { + // see JLS 15.21 + TreeInfo leftInfo = getTreeInfo(leftTree); + TreeInfo rightInfo = getTreeInfo(rightTree); + Node left = scan(leftTree, p); + Node right = scan(rightTree, p); + + if (leftInfo.isNumeric() && rightInfo.isNumeric() && + !(leftInfo.isBoxed() && rightInfo.isBoxed())) { + // JLS 15.21.1 numerical equality + TypeMirror promotedType = binaryPromotedType(leftInfo.unboxedType(), + rightInfo.unboxedType()); + left = binaryNumericPromotion(left, promotedType); + right = binaryNumericPromotion(right, promotedType); + } else if (leftInfo.isBoolean() && rightInfo.isBoolean() && + !(leftInfo.isBoxed() && rightInfo.isBoxed())) { + // JSL 15.21.2 boolean equality + left = unboxAsNeeded(left, leftInfo.isBoxed()); + right = unboxAsNeeded(right, rightInfo.isBoxed()); + } + + Node node; + if (kind == Tree.Kind.EQUAL_TO) { + node = new EqualToNode(tree, left, right); + } else { + assert kind == Kind.NOT_EQUAL_TO; + node = new NotEqualNode(tree, left, right); + } + extendWithNode(node); + + return node; + } + + case AND: + case OR: + case XOR: { + // see JLS 15.22 + TypeMirror leftType = InternalUtils.typeOf(leftTree); + TypeMirror rightType = InternalUtils.typeOf(rightTree); + boolean isBooleanOp = TypesUtils.isBooleanType(leftType) && + TypesUtils.isBooleanType(rightType); + + Node left; + Node right; + + if (isBooleanOp) { + left = unbox(scan(leftTree, p)); + right = unbox(scan(rightTree, p)); + } else if (isNumericOrBoxed(leftType) && isNumericOrBoxed(rightType)) { + TypeMirror promotedType = binaryPromotedType(leftType, rightType); + left = binaryNumericPromotion(scan(leftTree, p), promotedType); + right = binaryNumericPromotion(scan(rightTree, p), promotedType); + } else { + left = unbox(scan(leftTree, p)); + right = unbox(scan(rightTree, p)); + } + + Node node; + if (kind == Tree.Kind.AND) { + node = new BitwiseAndNode(tree, left, right); + } else if (kind == Tree.Kind.OR) { + node = new BitwiseOrNode(tree, left, right); + } else { + assert kind == Kind.XOR; + node = new BitwiseXorNode(tree, left, right); + } + + extendWithNode(node); + + return node; + } + + case CONDITIONAL_AND: + case CONDITIONAL_OR: { + // see JLS 15.23 and 15.24 + + // all necessary labels + Label rightStartL = new Label(); + Label shortCircuitL = new Label(); + + // left-hand side + Node left = scan(leftTree, p); + + ConditionalJump cjump; + if (kind == Tree.Kind.CONDITIONAL_AND) { + cjump = new ConditionalJump(rightStartL, shortCircuitL); + cjump.setFalseFlowRule(Store.FlowRule.ELSE_TO_ELSE); + } else { + cjump = new ConditionalJump(shortCircuitL, rightStartL); + cjump.setTrueFlowRule(Store.FlowRule.THEN_TO_THEN); + } + extendWithExtendedNode(cjump); + + // right-hand side + addLabelForNextNode(rightStartL); + Node right = scan(rightTree, p); + + // conditional expression itself + addLabelForNextNode(shortCircuitL); + Node node; + if (kind == Tree.Kind.CONDITIONAL_AND) { + node = new ConditionalAndNode(tree, left, right); + } else { + node = new ConditionalOrNode(tree, left, right); + } + extendWithNode(node); + return node; + } + default: + assert false : "unexpected binary tree: " + kind; + break; + } + assert r != null : "unexpected binary tree"; + return extendWithNode(r); + } + + @Override + public Node visitBlock(BlockTree tree, Void p) { + for (StatementTree n : tree.getStatements()) { + scan(n, null); + } + return null; + } + + @Override + public Node visitBreak(BreakTree tree, Void p) { + Name label = tree.getLabel(); + if (label == null) { + assert breakTargetL != null : "no target for break statement"; + + extendWithExtendedNode(new UnconditionalJump(breakTargetL)); + } else { + assert breakLabels.containsKey(label); + + extendWithExtendedNode(new UnconditionalJump( + breakLabels.get(label))); + } + + return null; + } + + @Override + public Node visitSwitch(SwitchTree tree, Void p) { + SwitchBuilder builder = new SwitchBuilder(tree, p); + builder.build(); + return null; + } + + private class SwitchBuilder { + final private SwitchTree switchTree; + final private Label[] caseBodyLabels; + final private Void p; + private Node switchExpr; + + private SwitchBuilder(SwitchTree tree, Void p) { + this.switchTree = tree; + this.caseBodyLabels = new Label[switchTree.getCases().size() + 1]; + this.p = p; + } + + public void build() { + Label oldBreakTargetL = breakTargetL; + breakTargetL = new Label(); + int cases = caseBodyLabels.length-1; + for (int i = 0; i < cases; ++i) { + caseBodyLabels[i] = new Label(); + } + caseBodyLabels[cases] = breakTargetL; + + switchExpr = unbox(scan(switchTree.getExpression(), p)); + extendWithNode(new MarkerNode(switchTree, "start of switch statement", env.getTypeUtils())); + + Integer defaultIndex = null; + for (int i = 0; i < cases; ++i) { + CaseTree caseTree = switchTree.getCases().get(i); + if (caseTree.getExpression() == null) { + defaultIndex = i; + } else { + buildCase(caseTree, i); + } + } + if (defaultIndex != null) { + // the checks of all cases must happen before the default case, + // therefore we build the default case last. + // fallthrough is still handled correctly with the caseBodyLabels. + buildCase(switchTree.getCases().get(defaultIndex), defaultIndex); + } + + addLabelForNextNode(breakTargetL); + breakTargetL = oldBreakTargetL; + } + + private void buildCase(CaseTree tree, int index) { + final Label thisBodyL = caseBodyLabels[index]; + final Label nextBodyL = caseBodyLabels[index+1]; + final Label nextCaseL = new Label(); + + ExpressionTree exprTree = tree.getExpression(); + if (exprTree != null) { + Node expr = scan(exprTree, p); + CaseNode test = new CaseNode(tree, switchExpr, expr, env.getTypeUtils()); + extendWithNode(test); + extendWithExtendedNode(new ConditionalJump(thisBodyL, nextCaseL)); + } + addLabelForNextNode(thisBodyL); + for (StatementTree stmt : tree.getStatements()) { + scan(stmt, p); + } + extendWithExtendedNode(new UnconditionalJump(nextBodyL)); + addLabelForNextNode(nextCaseL); + } + } + + @Override + public Node visitCase(CaseTree tree, Void p) { + throw new AssertionError("case visitor is implemented in SwitchBuilder"); + } + + @Override + public Node visitCatch(CatchTree tree, Void p) { + scan(tree.getParameter(), p); + scan(tree.getBlock(), p); + return null; + } + + @Override + public Node visitClass(ClassTree tree, Void p) { + declaredClasses.add(tree); + return null; + } + + @Override + public Node visitConditionalExpression(ConditionalExpressionTree tree, + Void p) { + // see JLS 15.25 + TypeMirror exprType = InternalUtils.typeOf(tree); + + Label trueStart = new Label(); + Label falseStart = new Label(); + Label merge = new Label(); + + Node condition = unbox(scan(tree.getCondition(), p)); + ConditionalJump cjump = new ConditionalJump(trueStart, falseStart); + extendWithExtendedNode(cjump); + + addLabelForNextNode(trueStart); + Node trueExpr = scan(tree.getTrueExpression(), p); + trueExpr = conditionalExprPromotion(trueExpr, exprType); + extendWithExtendedNode(new UnconditionalJump(merge)); + + addLabelForNextNode(falseStart); + Node falseExpr = scan(tree.getFalseExpression(), p); + falseExpr = conditionalExprPromotion(falseExpr, exprType); + + addLabelForNextNode(merge); + Node node = new TernaryExpressionNode(tree, condition, trueExpr, falseExpr); + extendWithNode(node); + + return node; + } + + @Override + public Node visitContinue(ContinueTree tree, Void p) { + Name label = tree.getLabel(); + if (label == null) { + assert continueTargetL != null : "no target for continue statement"; + + extendWithExtendedNode(new UnconditionalJump(continueTargetL)); + } else { + assert continueLabels.containsKey(label); + + extendWithExtendedNode(new UnconditionalJump( + continueLabels.get(label))); + } + + return null; + } + + @Override + public Node visitDoWhileLoop(DoWhileLoopTree tree, Void p) { + Name parentLabel = getLabel(getCurrentPath()); + + Label loopEntry = new Label(); + Label loopExit = new Label(); + + // If the loop is a labeled statement, then its continue + // target is identical for continues with no label and + // continues with the loop's label. + Label conditionStart; + if (parentLabel != null) { + conditionStart = continueLabels.get(parentLabel); + } else { + conditionStart = new Label(); + } + + Label oldBreakTargetL = breakTargetL; + breakTargetL = loopExit; + + Label oldContinueTargetL = continueTargetL; + continueTargetL = conditionStart; + + // Loop body + addLabelForNextNode(loopEntry); + if (tree.getStatement() != null) { + scan(tree.getStatement(), p); + } + + // Condition + addLabelForNextNode(conditionStart); + if (tree.getCondition() != null) { + unbox(scan(tree.getCondition(), p)); + ConditionalJump cjump = new ConditionalJump(loopEntry, loopExit); + extendWithExtendedNode(cjump); + } + + // Loop exit + addLabelForNextNode(loopExit); + + breakTargetL = oldBreakTargetL; + continueTargetL = oldContinueTargetL; + + return null; + } + + @Override + public Node visitErroneous(ErroneousTree tree, Void p) { + assert false : "ErroneousTree is unexpected in AST to CFG translation"; + return null; + } + + @Override + public Node visitExpressionStatement(ExpressionStatementTree tree, + Void p) { + return scan(tree.getExpression(), p); + } + + @Override + public Node visitEnhancedForLoop(EnhancedForLoopTree tree, Void p) { + // see JLS 14.14.2 + Name parentLabel = getLabel(getCurrentPath()); + + Label conditionStart = new Label(); + Label loopEntry = new Label(); + Label loopExit = new Label(); + + // If the loop is a labeled statement, then its continue + // target is identical for continues with no label and + // continues with the loop's label. + Label updateStart; + if (parentLabel != null) { + updateStart = continueLabels.get(parentLabel); + } else { + updateStart = new Label(); + } + + Label oldBreakTargetL = breakTargetL; + breakTargetL = loopExit; + + Label oldContinueTargetL = continueTargetL; + continueTargetL = updateStart; + + // Distinguish loops over Iterables from loops over arrays. + + TypeElement iterableElement = elements.getTypeElement("java.lang.Iterable"); + TypeMirror iterableType = types.erasure(iterableElement.asType()); + + VariableTree variable = tree.getVariable(); + VariableElement variableElement = + TreeUtils.elementFromDeclaration(variable); + ExpressionTree expression = tree.getExpression(); + StatementTree statement = tree.getStatement(); + + TypeMirror exprType = InternalUtils.typeOf(expression); + + if (types.isSubtype(exprType, iterableType)) { + // Take the upper bound of a type variable or wildcard + exprType = TypesUtils.upperBound(exprType); + + assert (exprType instanceof DeclaredType) : "an Iterable must be a DeclaredType"; + DeclaredType declaredExprType = (DeclaredType) exprType; + declaredExprType.getTypeArguments(); + + MemberSelectTree iteratorSelect = + treeBuilder.buildIteratorMethodAccess(expression); + handleArtificialTree(iteratorSelect); + + MethodInvocationTree iteratorCall = + treeBuilder.buildMethodInvocation(iteratorSelect); + handleArtificialTree(iteratorCall); + + VariableTree iteratorVariable = createEnhancedForLoopIteratorVariable(iteratorCall, variableElement); + handleArtificialTree(iteratorVariable); + + VariableDeclarationNode iteratorVariableDecl = + new VariableDeclarationNode(iteratorVariable); + iteratorVariableDecl.setInSource(false); + + extendWithNode(iteratorVariableDecl); + + Node expressionNode = scan(expression, p); + + MethodAccessNode iteratorAccessNode = + new MethodAccessNode(iteratorSelect, expressionNode); + iteratorAccessNode.setInSource(false); + extendWithNode(iteratorAccessNode); + MethodInvocationNode iteratorCallNode = + new MethodInvocationNode(iteratorCall, iteratorAccessNode, + Collections.<Node>emptyList(), getCurrentPath()); + iteratorCallNode.setInSource(false); + extendWithNode(iteratorCallNode); + + translateAssignment(iteratorVariable, + new LocalVariableNode(iteratorVariable), + iteratorCallNode); + + // Test the loop ending condition + addLabelForNextNode(conditionStart); + IdentifierTree iteratorUse1 = + treeBuilder.buildVariableUse(iteratorVariable); + handleArtificialTree(iteratorUse1); + + LocalVariableNode iteratorReceiverNode = + new LocalVariableNode(iteratorUse1); + iteratorReceiverNode.setInSource(false); + extendWithNode(iteratorReceiverNode); + + MemberSelectTree hasNextSelect = + treeBuilder.buildHasNextMethodAccess(iteratorUse1); + handleArtificialTree(hasNextSelect); + + MethodAccessNode hasNextAccessNode = + new MethodAccessNode(hasNextSelect, iteratorReceiverNode); + hasNextAccessNode.setInSource(false); + extendWithNode(hasNextAccessNode); + + MethodInvocationTree hasNextCall = + treeBuilder.buildMethodInvocation(hasNextSelect); + handleArtificialTree(hasNextCall); + + MethodInvocationNode hasNextCallNode = + new MethodInvocationNode(hasNextCall, hasNextAccessNode, + Collections.<Node>emptyList(), getCurrentPath()); + hasNextCallNode.setInSource(false); + extendWithNode(hasNextCallNode); + extendWithExtendedNode(new ConditionalJump(loopEntry, loopExit)); + + // Loop body, starting with declaration of the loop iteration variable + addLabelForNextNode(loopEntry); + extendWithNode(new VariableDeclarationNode(variable)); + + IdentifierTree iteratorUse2 = + treeBuilder.buildVariableUse(iteratorVariable); + handleArtificialTree(iteratorUse2); + + LocalVariableNode iteratorReceiverNode2 = + new LocalVariableNode(iteratorUse2); + iteratorReceiverNode2.setInSource(false); + extendWithNode(iteratorReceiverNode2); + + MemberSelectTree nextSelect = + treeBuilder.buildNextMethodAccess(iteratorUse2); + handleArtificialTree(nextSelect); + + MethodAccessNode nextAccessNode = + new MethodAccessNode(nextSelect, iteratorReceiverNode2); + nextAccessNode.setInSource(false); + extendWithNode(nextAccessNode); + + MethodInvocationTree nextCall = + treeBuilder.buildMethodInvocation(nextSelect); + handleArtificialTree(nextCall); + + MethodInvocationNode nextCallNode = + new MethodInvocationNode(nextCall, nextAccessNode, + Collections.<Node>emptyList(), getCurrentPath()); + nextCallNode.setInSource(false); + extendWithNode(nextCallNode); + + translateAssignment(variable, + new LocalVariableNode(variable), + nextCall); + + if (statement != null) { + scan(statement, p); + } + + // Loop back edge + addLabelForNextNode(updateStart); + extendWithExtendedNode(new UnconditionalJump(conditionStart)); + + } else { + // TODO: Shift any labels after the initialization of the + // temporary array variable. + + VariableTree arrayVariable = createEnhancedForLoopArrayVariable(expression, variableElement); + handleArtificialTree(arrayVariable); + + VariableDeclarationNode arrayVariableNode = + new VariableDeclarationNode(arrayVariable); + arrayVariableNode.setInSource(false); + extendWithNode(arrayVariableNode); + Node expressionNode = scan(expression, p); + + translateAssignment(arrayVariable, + new LocalVariableNode(arrayVariable), + expressionNode); + + // Declare and initialize the loop index variable + TypeMirror intType = types.getPrimitiveType(TypeKind.INT); + + LiteralTree zero = + treeBuilder.buildLiteral(new Integer(0)); + handleArtificialTree(zero); + + VariableTree indexVariable = + treeBuilder.buildVariableDecl(intType, + uniqueName("index"), + variableElement.getEnclosingElement(), + zero); + handleArtificialTree(indexVariable); + VariableDeclarationNode indexVariableNode = + new VariableDeclarationNode(indexVariable); + indexVariableNode.setInSource(false); + extendWithNode(indexVariableNode); + IntegerLiteralNode zeroNode = + extendWithNode(new IntegerLiteralNode(zero)); + + translateAssignment(indexVariable, + new LocalVariableNode(indexVariable), + zeroNode); + + // Compare index to array length + addLabelForNextNode(conditionStart); + IdentifierTree indexUse1 = + treeBuilder.buildVariableUse(indexVariable); + handleArtificialTree(indexUse1); + LocalVariableNode indexNode1 = + new LocalVariableNode(indexUse1); + indexNode1.setInSource(false); + extendWithNode(indexNode1); + + IdentifierTree arrayUse1 = + treeBuilder.buildVariableUse(arrayVariable); + handleArtificialTree(arrayUse1); + LocalVariableNode arrayNode1 = + extendWithNode(new LocalVariableNode(arrayUse1)); + + MemberSelectTree lengthSelect = + treeBuilder.buildArrayLengthAccess(arrayUse1); + handleArtificialTree(lengthSelect); + FieldAccessNode lengthAccessNode = + new FieldAccessNode(lengthSelect, arrayNode1); + lengthAccessNode.setInSource(false); + extendWithNode(lengthAccessNode); + + BinaryTree lessThan = + treeBuilder.buildLessThan(indexUse1, lengthSelect); + handleArtificialTree(lessThan); + + LessThanNode lessThanNode = + new LessThanNode(lessThan, indexNode1, lengthAccessNode); + lessThanNode.setInSource(false); + extendWithNode(lessThanNode); + extendWithExtendedNode(new ConditionalJump(loopEntry, loopExit)); + + // Loop body, starting with declaration of the loop iteration variable + addLabelForNextNode(loopEntry); + extendWithNode(new VariableDeclarationNode(variable)); + + IdentifierTree arrayUse2 = + treeBuilder.buildVariableUse(arrayVariable); + handleArtificialTree(arrayUse2); + LocalVariableNode arrayNode2 = + new LocalVariableNode(arrayUse2); + arrayNode2.setInSource(false); + extendWithNode(arrayNode2); + + IdentifierTree indexUse2 = + treeBuilder.buildVariableUse(indexVariable); + handleArtificialTree(indexUse2); + LocalVariableNode indexNode2 = + new LocalVariableNode(indexUse2); + indexNode2.setInSource(false); + extendWithNode(indexNode2); + + ArrayAccessTree arrayAccess = + treeBuilder.buildArrayAccess(arrayUse2, indexUse2); + handleArtificialTree(arrayAccess); + ArrayAccessNode arrayAccessNode = + new ArrayAccessNode(arrayAccess, arrayNode2, indexNode2); + arrayAccessNode.setInSource(false); + extendWithNode(arrayAccessNode); + translateAssignment(variable, + new LocalVariableNode(variable), + arrayAccessNode); + + if (statement != null) { + scan(statement, p); + } + + // Loop back edge + addLabelForNextNode(updateStart); + + IdentifierTree indexUse3 = + treeBuilder.buildVariableUse(indexVariable); + handleArtificialTree(indexUse3); + LocalVariableNode indexNode3 = + new LocalVariableNode(indexUse3); + indexNode3.setInSource(false); + extendWithNode(indexNode3); + + LiteralTree oneTree = treeBuilder.buildLiteral(Integer.valueOf(1)); + handleArtificialTree(oneTree); + Node one = new IntegerLiteralNode(oneTree); + one.setInSource(false); + extendWithNode(one); + + BinaryTree addOneTree = treeBuilder.buildBinary(intType, Tree.Kind.PLUS, + indexUse3, oneTree); + handleArtificialTree(addOneTree); + Node addOneNode = new NumericalAdditionNode(addOneTree, indexNode3, one); + addOneNode.setInSource(false); + extendWithNode(addOneNode); + + AssignmentTree assignTree = treeBuilder.buildAssignment(indexUse3, addOneTree); + handleArtificialTree(assignTree); + Node assignNode = new AssignmentNode(assignTree, indexNode3, addOneNode); + assignNode.setInSource(false); + extendWithNode(assignNode); + + extendWithExtendedNode(new UnconditionalJump(conditionStart)); + } + + // Loop exit + addLabelForNextNode(loopExit); + + breakTargetL = oldBreakTargetL; + continueTargetL = oldContinueTargetL; + + return null; + } + + protected VariableTree createEnhancedForLoopIteratorVariable(MethodInvocationTree iteratorCall, VariableElement variableElement) { + TypeMirror iteratorType = InternalUtils.typeOf(iteratorCall); + + // Declare and initialize a new, unique iterator variable + VariableTree iteratorVariable = + treeBuilder.buildVariableDecl(iteratorType, // annotatedIteratorTypeTree, + uniqueName("iter"), + variableElement.getEnclosingElement(), + iteratorCall); + return iteratorVariable; + } + + protected VariableTree createEnhancedForLoopArrayVariable(ExpressionTree expression, VariableElement variableElement) { + TypeMirror arrayType = InternalUtils.typeOf(expression); + + // Declare and initialize a temporary array variable + VariableTree arrayVariable = + treeBuilder.buildVariableDecl(arrayType, + uniqueName("array"), + variableElement.getEnclosingElement(), + expression); + return arrayVariable; + } + + @Override + public Node visitForLoop(ForLoopTree tree, Void p) { + Name parentLabel = getLabel(getCurrentPath()); + + Label conditionStart = new Label(); + Label loopEntry = new Label(); + Label loopExit = new Label(); + + // If the loop is a labeled statement, then its continue + // target is identical for continues with no label and + // continues with the loop's label. + Label updateStart; + if (parentLabel != null) { + updateStart = continueLabels.get(parentLabel); + } else { + updateStart = new Label(); + } + + Label oldBreakTargetL = breakTargetL; + breakTargetL = loopExit; + + Label oldContinueTargetL = continueTargetL; + continueTargetL = updateStart; + + // Initializer + for (StatementTree init : tree.getInitializer()) { + scan(init, p); + } + + // Condition + addLabelForNextNode(conditionStart); + if (tree.getCondition() != null) { + unbox(scan(tree.getCondition(), p)); + ConditionalJump cjump = new ConditionalJump(loopEntry, loopExit); + extendWithExtendedNode(cjump); + } + + // Loop body + addLabelForNextNode(loopEntry); + if (tree.getStatement() != null) { + scan(tree.getStatement(), p); + } + + // Update + addLabelForNextNode(updateStart); + for (ExpressionStatementTree update : tree.getUpdate()) { + scan(update, p); + } + + extendWithExtendedNode(new UnconditionalJump(conditionStart)); + + // Loop exit + addLabelForNextNode(loopExit); + + breakTargetL = oldBreakTargetL; + continueTargetL = oldContinueTargetL; + + return null; + } + + @Override + public Node visitIdentifier(IdentifierTree tree, Void p) { + Node node; + if (TreeUtils.isFieldAccess(tree)) { + Node receiver = getReceiver(tree, + TreeUtils.enclosingClass(getCurrentPath())); + node = new FieldAccessNode(tree, receiver); + } else { + Element element = TreeUtils.elementFromUse(tree); + switch (element.getKind()) { + case ANNOTATION_TYPE: + case CLASS: + case ENUM: + case INTERFACE: + case TYPE_PARAMETER: + node = new ClassNameNode(tree); + break; + case FIELD: + // Note that "this"/"super" is a field, but not a field access. + if (element.getSimpleName().contentEquals("this")) { + node = new ExplicitThisLiteralNode(tree); + } else { + node = new SuperNode(tree); + } + break; + case EXCEPTION_PARAMETER: + case LOCAL_VARIABLE: + case RESOURCE_VARIABLE: + case PARAMETER: + node = new LocalVariableNode(tree); + break; + case PACKAGE: + node = new PackageNameNode(tree); + break; + default: + throw new IllegalArgumentException( + "unexpected element kind : " + element.getKind()); + } + } + extendWithNode(node); + return node; + } + + @Override + public Node visitIf(IfTree tree, Void p) { + // all necessary labels + Label thenEntry = new Label(); + Label elseEntry = new Label(); + Label endIf = new Label(); + + // basic block for the condition + unbox(scan(tree.getCondition(), p)); + + ConditionalJump cjump = new ConditionalJump(thenEntry, elseEntry); + extendWithExtendedNode(cjump); + + // then branch + addLabelForNextNode(thenEntry); + StatementTree thenStatement = tree.getThenStatement(); + scan(thenStatement, p); + extendWithExtendedNode(new UnconditionalJump(endIf)); + + // else branch + addLabelForNextNode(elseEntry); + StatementTree elseStatement = tree.getElseStatement(); + if (elseStatement != null) { + scan(elseStatement, p); + } + + // label the end of the if statement + addLabelForNextNode(endIf); + + return null; + } + + @Override + public Node visitImport(ImportTree tree, Void p) { + assert false : "ImportTree is unexpected in AST to CFG translation"; + return null; + } + + @Override + public Node visitArrayAccess(ArrayAccessTree tree, Void p) { + Node array = scan(tree.getExpression(), p); + Node index = unaryNumericPromotion(scan(tree.getIndex(), p)); + return extendWithNode(new ArrayAccessNode(tree, array, index)); + } + + @Override + public Node visitLabeledStatement(LabeledStatementTree tree, Void p) { + // This method can set the break target after generating all Nodes + // in the contained statement, but it can't set the continue target, + // which may be in the middle of a sequence of nodes. Labeled loops + // must look up and use the continue Labels. + Name labelName = tree.getLabel(); + + Label breakL = new Label(labelName + "_break"); + Label continueL = new Label(labelName + "_continue"); + + breakLabels.put(labelName, breakL); + continueLabels.put(labelName, continueL); + + scan(tree.getStatement(), p); + + addLabelForNextNode(breakL); + + breakLabels.remove(labelName); + continueLabels.remove(labelName); + + return null; + } + + @Override + public Node visitLiteral(LiteralTree tree, Void p) { + Node r = null; + switch (tree.getKind()) { + case BOOLEAN_LITERAL: + r = new BooleanLiteralNode(tree); + break; + case CHAR_LITERAL: + r = new CharacterLiteralNode(tree); + break; + case DOUBLE_LITERAL: + r = new DoubleLiteralNode(tree); + break; + case FLOAT_LITERAL: + r = new FloatLiteralNode(tree); + break; + case INT_LITERAL: + r = new IntegerLiteralNode(tree); + break; + case LONG_LITERAL: + r = new LongLiteralNode(tree); + break; + case NULL_LITERAL: + r = new NullLiteralNode(tree); + break; + case STRING_LITERAL: + r = new StringLiteralNode(tree); + break; + default: + assert false : "unexpected literal tree"; + break; + } + assert r != null : "unexpected literal tree"; + Node result = extendWithNode(r); + return result; + } + + @Override + public Node visitMethod(MethodTree tree, Void p) { + assert false : "MethodTree is unexpected in AST to CFG translation"; + return null; + } + + @Override + public Node visitModifiers(ModifiersTree tree, Void p) { + assert false : "ModifiersTree is unexpected in AST to CFG translation"; + return null; + } + + @Override + public Node visitNewArray(NewArrayTree tree, Void p) { + // see JLS 15.10 + + ArrayType type = (ArrayType)InternalUtils.typeOf(tree); + TypeMirror elemType = type.getComponentType(); + + List<? extends ExpressionTree> dimensions = tree.getDimensions(); + List<? extends ExpressionTree> initializers = tree + .getInitializers(); + + List<Node> dimensionNodes = new ArrayList<Node>(); + if (dimensions != null) { + for (ExpressionTree dim : dimensions) { + dimensionNodes.add(unaryNumericPromotion(scan(dim, p))); + } + } + + List<Node> initializerNodes = new ArrayList<Node>(); + if (initializers != null) { + for (ExpressionTree init : initializers) { + initializerNodes.add(assignConvert(scan(init, p), elemType)); + } + } + + Node node = new ArrayCreationNode(tree, type, dimensionNodes, + initializerNodes); + return extendWithNode(node); + } + + @Override + public Node visitNewClass(NewClassTree tree, Void p) { + // see JLS 15.9 + + Tree enclosingExpr = tree.getEnclosingExpression(); + if (enclosingExpr != null) { + scan(enclosingExpr, p); + } + + // We ignore any class body because its methods should + // be visited separately. + + // Convert constructor arguments + ExecutableElement constructor = TreeUtils.elementFromUse(tree); + + List<? extends ExpressionTree> actualExprs = tree.getArguments(); + + List<Node> arguments = convertCallArguments(constructor, + actualExprs); + + Node constructorNode = scan(tree.getIdentifier(), p); + + Node node = new ObjectCreationNode(tree, constructorNode, arguments); + + Set<TypeMirror> thrownSet = new HashSet<>(); + // Add exceptions explicitly mentioned in the throws clause. + List<? extends TypeMirror> thrownTypes = constructor.getThrownTypes(); + thrownSet.addAll(thrownTypes); + // Add Throwable to account for unchecked exceptions + TypeElement throwableElement = elements + .getTypeElement("java.lang.Throwable"); + thrownSet.add(throwableElement.asType()); + + extendWithNodeWithExceptions(node, thrownSet); + + return node; + } + + /** + * Maps a {@code Tree} its directly enclosing {@code ParenthesizedTree} if one exists. + * + * This map is used by {@link CFGTranslationPhaseOne#addToLookupMap(Node)} to + * associate a {@code ParenthesizedTree} with the dataflow {@code Node} that was used + * during inference. This map is necessary because dataflow does + * not create a {@code Node} for a {@code ParenthesizedTree.} + */ + private final Map<Tree, ParenthesizedTree> parenMapping = new HashMap<>(); + + @Override + public Node visitParenthesized(ParenthesizedTree tree, Void p) { + parenMapping.put(tree.getExpression(), tree); + return scan(tree.getExpression(), p); + } + + @Override + public Node visitReturn(ReturnTree tree, Void p) { + ExpressionTree ret = tree.getExpression(); + // TODO: also have a return-node if nothing is returned + ReturnNode result = null; + if (ret != null) { + Node node = scan(ret, p); + Tree enclosing = TreeUtils.enclosingOfKind(getCurrentPath(), new HashSet<Kind>(Arrays.asList(Kind.METHOD, Kind.LAMBDA_EXPRESSION))); + if (enclosing.getKind() == Kind.LAMBDA_EXPRESSION) { + LambdaExpressionTree lambdaTree = (LambdaExpressionTree) enclosing; + TreePath lambdaTreePath = TreePath.getPath(getCurrentPath().getCompilationUnit(), lambdaTree); + Context ctx = ((JavacProcessingEnvironment)env).getContext(); + Element overriddenElement = com.sun.tools.javac.code.Types.instance(ctx).findDescriptorSymbol( + ((Type)trees.getTypeMirror(lambdaTreePath)).tsym); + + result = new ReturnNode(tree, node, env.getTypeUtils(), lambdaTree, (MethodSymbol)overriddenElement); + } else { + result = new ReturnNode(tree, node, env.getTypeUtils(), (MethodTree)enclosing); + } + returnNodes.add(result); + extendWithNode(result); + } + extendWithExtendedNode(new UnconditionalJump(regularExitLabel)); + // TODO: return statements should also flow to an enclosing finally block + return result; + } + + @Override + public Node visitMemberSelect(MemberSelectTree tree, Void p) { + Node expr = scan(tree.getExpression(), p); + if (!TreeUtils.isFieldAccess(tree)) { + // Could be a selector of a class or package + Node result = null; + Element element = TreeUtils.elementFromUse(tree); + switch (element.getKind()) { + case ANNOTATION_TYPE: + case CLASS: + case ENUM: + case INTERFACE: + result = extendWithNode(new ClassNameNode(tree, expr)); + break; + case PACKAGE: + result = extendWithNode(new PackageNameNode(tree, (PackageNameNode) expr)); + break; + default: + assert false : "Unexpected element kind: " + element.getKind(); + return null; + } + return result; + } + + Node node = new FieldAccessNode(tree, expr); + + Element element = TreeUtils.elementFromUse(tree); + if (ElementUtils.isStatic(element) || + expr instanceof ImplicitThisLiteralNode || + expr instanceof ExplicitThisLiteralNode) { + // No NullPointerException can be thrown, use normal node + extendWithNode(node); + } else { + TypeElement npeElement = elements + .getTypeElement("java.lang.NullPointerException"); + extendWithNodeWithException(node, npeElement.asType()); + } + + return node; + } + + @Override + public Node visitEmptyStatement(EmptyStatementTree tree, Void p) { + return null; + } + + @Override + public Node visitSynchronized(SynchronizedTree tree, Void p) { + // see JLS 14.19 + + Node synchronizedExpr = scan(tree.getExpression(), p); + SynchronizedNode synchronizedStartNode = new SynchronizedNode(tree, synchronizedExpr, true, env.getTypeUtils()); + extendWithNode(synchronizedStartNode); + scan(tree.getBlock(), p); + SynchronizedNode synchronizedEndNode = new SynchronizedNode(tree, synchronizedExpr, false, env.getTypeUtils()); + extendWithNode(synchronizedEndNode); + + return null; + } + + @Override + public Node visitThrow(ThrowTree tree, Void p) { + Node expression = scan(tree.getExpression(), p); + TypeMirror exception = expression.getType(); + ThrowNode throwsNode = new ThrowNode(tree, expression, env.getTypeUtils()); + NodeWithExceptionsHolder exNode = extendWithNodeWithException( + throwsNode, exception); + exNode.setTerminatesExecution(true); + return throwsNode; + } + + @Override + public Node visitCompilationUnit(CompilationUnitTree tree, Void p) { + assert false : "CompilationUnitTree is unexpected in AST to CFG translation"; + return null; + } + + @Override + public Node visitTry(TryTree tree, Void p) { + List<? extends CatchTree> catches = tree.getCatches(); + BlockTree finallyBlock = tree.getFinallyBlock(); + + extendWithNode(new MarkerNode(tree, "start of try statement", env.getTypeUtils())); + + // TODO: Should we handle try-with-resources blocks by also generating code + // for automatically closing the resources? + List<? extends Tree> resources = tree.getResources(); + for (Tree resource : resources) { + scan(resource, p); + } + + List<Pair<TypeMirror, Label>> catchLabels = new ArrayList<>(); + for (CatchTree c : catches) { + TypeMirror type = InternalUtils.typeOf(c.getParameter().getType()); + assert type != null : "exception parameters must have a type"; + catchLabels.add(Pair.of(type, new Label())); + } + + Label finallyLabel = null; + if (finallyBlock != null) { + finallyLabel = new Label(); + tryStack.pushFrame(new TryFinallyFrame(finallyLabel)); + } + + Label doneLabel = new Label(); + + tryStack.pushFrame(new TryCatchFrame(types, catchLabels)); + + scan(tree.getBlock(), p); + extendWithExtendedNode(new UnconditionalJump(firstNonNull(finallyLabel, doneLabel))); + + tryStack.popFrame(); + + int catchIndex = 0; + for (CatchTree c : catches) { + addLabelForNextNode(catchLabels.get(catchIndex).second); + scan(c, p); + catchIndex++; + extendWithExtendedNode(new UnconditionalJump(firstNonNull(finallyLabel, doneLabel))); + } + + if (finallyLabel != null) { + tryStack.popFrame(); + addLabelForNextNode(finallyLabel); + scan(finallyBlock, p); + + TypeMirror throwableType = + elements.getTypeElement("java.lang.Throwable").asType(); + extendWithNodeWithException(new MarkerNode(tree, "end of finally block", env.getTypeUtils()), + throwableType); + } + + addLabelForNextNode(doneLabel); + + return null; + } + + @Override + public Node visitParameterizedType(ParameterizedTypeTree tree, Void p) { + return extendWithNode(new ParameterizedTypeNode(tree)); + } + + @Override + public Node visitUnionType(UnionTypeTree tree, Void p) { + assert false : "UnionTypeTree is unexpected in AST to CFG translation"; + return null; + } + + @Override + public Node visitArrayType(ArrayTypeTree tree, Void p) { + return extendWithNode(new ArrayTypeNode(tree)); + } + + @Override + public Node visitTypeCast(TypeCastTree tree, Void p) { + final Node operand = scan(tree.getExpression(), p); + final TypeMirror type = InternalUtils.typeOf(tree.getType()); + final Node node = new TypeCastNode(tree, operand, type); + final TypeElement cceElement = elements.getTypeElement("java.lang.ClassCastException"); + + extendWithNodeWithException(node, cceElement.asType()); + return node; + } + + @Override + public Node visitPrimitiveType(PrimitiveTypeTree tree, Void p) { + return extendWithNode(new PrimitiveTypeNode(tree)); + } + + @Override + public Node visitTypeParameter(TypeParameterTree tree, Void p) { + assert false : "TypeParameterTree is unexpected in AST to CFG translation"; + return null; + } + + @Override + public Node visitInstanceOf(InstanceOfTree tree, Void p) { + Node operand = scan(tree.getExpression(), p); + TypeMirror refType = InternalUtils.typeOf(tree.getType()); + InstanceOfNode node = new InstanceOfNode(tree, operand, refType, + types); + extendWithNode(node); + return node; + } + + @Override + public Node visitUnary(UnaryTree tree, Void p) { + Node result = null; + Tree.Kind kind = tree.getKind(); + switch (kind) { + case BITWISE_COMPLEMENT: + case UNARY_MINUS: + case UNARY_PLUS: { + // see JLS 15.14 and 15.15 + Node expr = scan(tree.getExpression(), p); + expr = unaryNumericPromotion(expr); + + // TypeMirror exprType = InternalUtils.typeOf(tree); + + switch (kind) { + case BITWISE_COMPLEMENT: + result = extendWithNode(new BitwiseComplementNode(tree, + expr)); + break; + case UNARY_MINUS: + result = extendWithNode(new NumericalMinusNode(tree, expr)); + break; + case UNARY_PLUS: + result = extendWithNode(new NumericalPlusNode(tree, expr)); + break; + default: + assert false; + break; + } + break; + } + + case LOGICAL_COMPLEMENT: { + // see JLS 15.15.6 + Node expr = scan(tree.getExpression(), p); + result = extendWithNode(new ConditionalNotNode(tree, + unbox(expr))); + break; + } + + case POSTFIX_DECREMENT: + case POSTFIX_INCREMENT: { + ExpressionTree exprTree = tree.getExpression(); + TypeMirror exprType = InternalUtils.typeOf(exprTree); + TypeMirror oneType = types.getPrimitiveType(TypeKind.INT); + Node expr = scan(exprTree, p); + + TypeMirror promotedType = binaryPromotedType(exprType, oneType); + + LiteralTree oneTree = treeBuilder.buildLiteral(Integer.valueOf(1)); + handleArtificialTree(oneTree); + + Node exprRHS = binaryNumericPromotion(expr, promotedType); + Node one = new IntegerLiteralNode(oneTree); + one.setInSource(false); + extendWithNode(one); + one = binaryNumericPromotion(one, promotedType); + + BinaryTree operTree = treeBuilder.buildBinary(promotedType, + (kind == Tree.Kind.POSTFIX_INCREMENT ? Tree.Kind.PLUS : Tree.Kind.MINUS), + exprTree, oneTree); + handleArtificialTree(operTree); + Node operNode; + if (kind == Tree.Kind.POSTFIX_INCREMENT) { + operNode = new NumericalAdditionNode(operTree, exprRHS, one); + } else { + assert kind == Tree.Kind.POSTFIX_DECREMENT; + operNode = new NumericalSubtractionNode(operTree, exprRHS, one); + } + extendWithNode(operNode); + + Node narrowed = narrowAndBox(operNode, exprType); + // TODO: By using the assignment as the result of the expression, we + // act like a pre-increment/decrement. Fix this by saving the initial + // value of the expression in a temporary. + AssignmentNode assignNode = new AssignmentNode(tree, expr, narrowed); + extendWithNode(assignNode); + result = assignNode; + break; + } + case PREFIX_DECREMENT: + case PREFIX_INCREMENT: { + ExpressionTree exprTree = tree.getExpression(); + TypeMirror exprType = InternalUtils.typeOf(exprTree); + TypeMirror oneType = types.getPrimitiveType(TypeKind.INT); + Node expr = scan(exprTree, p); + + TypeMirror promotedType = binaryPromotedType(exprType, oneType); + + LiteralTree oneTree = treeBuilder.buildLiteral(Integer.valueOf(1)); + handleArtificialTree(oneTree); + + Node exprRHS = binaryNumericPromotion(expr, promotedType); + Node one = new IntegerLiteralNode(oneTree); + one.setInSource(false); + extendWithNode(one); + one = binaryNumericPromotion(one, promotedType); + + BinaryTree operTree = treeBuilder.buildBinary(promotedType, + (kind == Tree.Kind.PREFIX_INCREMENT ? Tree.Kind.PLUS : Tree.Kind.MINUS), + exprTree, oneTree); + handleArtificialTree(operTree); + Node operNode; + if (kind == Tree.Kind.PREFIX_INCREMENT) { + operNode = new NumericalAdditionNode(operTree, exprRHS, one); + } else { + assert kind == Tree.Kind.PREFIX_DECREMENT; + operNode = new NumericalSubtractionNode(operTree, exprRHS, one); + } + extendWithNode(operNode); + + Node narrowed = narrowAndBox(operNode, exprType); + AssignmentNode assignNode = new AssignmentNode(tree, expr, narrowed); + extendWithNode(assignNode); + result = assignNode; + break; + } + + case OTHER: + default: + // special node NLLCHK + if (tree.toString().startsWith("<*nullchk*>")) { + Node expr = scan(tree.getExpression(), p); + result = extendWithNode(new NullChkNode(tree, expr)); + break; + } + + assert false : "Unknown kind (" + kind + + ") of unary expression: " + tree; + } + + return result; + } + + @Override + public Node visitVariable(VariableTree tree, Void p) { + + // see JLS 14.4 + + boolean isField = getCurrentPath().getParentPath() != null + && getCurrentPath().getParentPath().getLeaf().getKind() == Kind.CLASS; + Node node = null; + + ClassTree enclosingClass = TreeUtils + .enclosingClass(getCurrentPath()); + TypeElement classElem = TreeUtils + .elementFromDeclaration(enclosingClass); + Node receiver = new ImplicitThisLiteralNode(classElem.asType()); + + if (isField) { + ExpressionTree initializer = tree.getInitializer(); + assert initializer != null; + node = translateAssignment( + tree, + new FieldAccessNode(tree, TreeUtils.elementFromDeclaration(tree), receiver), + initializer); + } else { + // local variable definition + VariableDeclarationNode decl = new VariableDeclarationNode(tree); + extendWithNode(decl); + + // initializer + + ExpressionTree initializer = tree.getInitializer(); + if (initializer != null) { + node = translateAssignment(tree, new LocalVariableNode(tree, receiver), + initializer); + } + } + + return node; + } + + @Override + public Node visitWhileLoop(WhileLoopTree tree, Void p) { + Name parentLabel = getLabel(getCurrentPath()); + + Label loopEntry = new Label(); + Label loopExit = new Label(); + + // If the loop is a labeled statement, then its continue + // target is identical for continues with no label and + // continues with the loop's label. + Label conditionStart; + if (parentLabel != null) { + conditionStart = continueLabels.get(parentLabel); + } else { + conditionStart = new Label(); + } + + Label oldBreakTargetL = breakTargetL; + breakTargetL = loopExit; + + Label oldContinueTargetL = continueTargetL; + continueTargetL = conditionStart; + + // Condition + addLabelForNextNode(conditionStart); + if (tree.getCondition() != null) { + unbox(scan(tree.getCondition(), p)); + ConditionalJump cjump = new ConditionalJump(loopEntry, loopExit); + extendWithExtendedNode(cjump); + } + + // Loop body + addLabelForNextNode(loopEntry); + if (tree.getStatement() != null) { + scan(tree.getStatement(), p); + } + extendWithExtendedNode(new UnconditionalJump(conditionStart)); + + // Loop exit + addLabelForNextNode(loopExit); + + breakTargetL = oldBreakTargetL; + continueTargetL = oldContinueTargetL; + + return null; + } + + @Override + public Node visitLambdaExpression(LambdaExpressionTree tree, Void p) { + declaredLambdas.add(tree); + Node node = new FunctionalInterfaceNode(tree); + extendWithNode(node); + return node; + } + + @Override + public Node visitMemberReference(MemberReferenceTree tree, Void p) { + Tree enclosingExpr = tree.getQualifierExpression(); + if (enclosingExpr != null) { + scan(enclosingExpr, p); + } + + Node node = new FunctionalInterfaceNode(tree); + extendWithNode(node); + + return node; + } + + @Override + public Node visitWildcard(WildcardTree tree, Void p) { + assert false : "WildcardTree is unexpected in AST to CFG translation"; + return null; + } + + @Override + public Node visitOther(Tree tree, Void p) { + assert false : "Unknown AST element encountered in AST to CFG translation."; + return null; + } + } + + /** + * A tuple with 4 named elements. + */ + private interface TreeInfo { + boolean isBoxed(); + boolean isNumeric(); + boolean isBoolean(); + TypeMirror unboxedType(); + } + + private static <A> A firstNonNull(A first, A second) { + if (first != null) { + return first; + } else if (second != null) { + return second; + } else { + throw new NullPointerException(); + } + } + + /* --------------------------------------------------------- */ + /* Utility routines for debugging CFG building */ + /* --------------------------------------------------------- */ + + /** + * Print a set of {@link Block}s and the edges between them. This is useful + * for examining the results of phase two. + */ + protected static void printBlocks(Set<Block> blocks) { + for (Block b : blocks) { + System.out.print(b.hashCode() + ": " + b); + switch (b.getType()) { + case REGULAR_BLOCK: + case SPECIAL_BLOCK: { + Block succ = ((SingleSuccessorBlockImpl) b).getSuccessor(); + System.out.println(" -> " + + (succ != null ? succ.hashCode() : "||")); + break; + } + case EXCEPTION_BLOCK: { + Block succ = ((SingleSuccessorBlockImpl) b).getSuccessor(); + System.out.print(" -> " + + (succ != null ? succ.hashCode() : "||") + " {"); + for (Map.Entry<TypeMirror, Set<Block>> entry : ((ExceptionBlockImpl) b).getExceptionalSuccessors().entrySet()) { + System.out.print(entry.getKey() + " : " + entry.getValue() + ", "); + } + System.out.println("}"); + break; + } + case CONDITIONAL_BLOCK: { + Block tSucc = ((ConditionalBlockImpl) b).getThenSuccessor(); + Block eSucc = ((ConditionalBlockImpl) b).getElseSuccessor(); + System.out.println(" -> T " + + (tSucc != null ? tSucc.hashCode() : "||") + " F " + + (eSucc != null ? eSucc.hashCode() : "||")); + break; + } + } + } + } +} |