*/
package com.intellij.psi.controlFlow;
+import com.intellij.codeInsight.ExceptionUtil;
import com.intellij.openapi.diagnostic.Logger;
import com.intellij.psi.*;
import com.intellij.psi.impl.source.DummyHolder;
import com.intellij.psi.util.PsiTreeUtil;
import com.intellij.psi.util.PsiUtil;
import com.intellij.util.ArrayUtil;
+import com.intellij.util.Function;
import com.intellij.util.IncorrectOperationException;
import com.intellij.util.ReflectionUtil;
import com.intellij.util.containers.IntArrayList;
import com.intellij.util.containers.IntStack;
+import gnu.trove.THashMap;
import gnu.trove.THashSet;
import gnu.trove.TIntHashSet;
import org.jetbrains.annotations.NotNull;
return PsiTreeUtil.getParentOfType(element, PsiStatement.class, false);
}
+ /**
+ * Detect throw instructions which might affect observable control flow via side effects with local variables
+ * The side effect of exception thrown occurs when a local variable is written in the try block, and then accessed
+ * in the finally section or in/after a catch section.
+ */
+ public static boolean hasObservableThrowExitPoints(@NotNull ControlFlow flow,
+ int flowStart,
+ int flowEnd,
+ @NotNull PsiElement[] elements,
+ @NotNull PsiElement enclosingCodeFragment) {
+ final List<Instruction> instructions = flow.getInstructions();
+ final Map<PsiVariable, IntArrayList> writeOffsets = new THashMap<PsiVariable, IntArrayList>();
+ for (int i = flowStart; i < flowEnd; i++) {
+ Instruction instruction = instructions.get(i);
+ if (instruction instanceof WriteVariableInstruction) {
+ final PsiVariable variable = ((WriteVariableInstruction)instruction).variable;
+ if (variable instanceof PsiLocalVariable || variable instanceof PsiParameter) {
+ IntArrayList offsets = writeOffsets.get(variable);
+ if (offsets == null) writeOffsets.put(variable, offsets = new IntArrayList());
+ offsets.add(i);
+ }
+ }
+ }
+ if (writeOffsets.isEmpty()) return false;
+ LOG.debug("minWriteOffsets:", writeOffsets);
+
+ final PsiElement commonParent = elements.length != 1 ? PsiTreeUtil.findCommonParent(elements) : elements[0].getParent();
+ final List<PsiTryStatement> tryStatements = collectTryStatementStack(commonParent, enclosingCodeFragment);
+ if (tryStatements.isEmpty()) return false;
+ final PsiCodeBlock tryBlock = tryStatements.get(0).getTryBlock();
+ if (tryBlock == null) return false;
+
+ final Map<PsiVariable, IntArrayList> visibleReadOffsets = new THashMap<PsiVariable, IntArrayList>();
+ for (PsiVariable variable : writeOffsets.keySet()) {
+ if (!PsiTreeUtil.isAncestor(tryBlock, variable, true)) {
+ visibleReadOffsets.put(variable, new IntArrayList());
+ }
+ }
+ if (visibleReadOffsets.isEmpty()) return false;
+
+ for (int i = 0; i < instructions.size(); i++) {
+ final Instruction instruction = instructions.get(i);
+ if (instruction instanceof ReadVariableInstruction) {
+ final PsiVariable variable = ((ReadVariableInstruction)instruction).variable;
+ final IntArrayList readOffsets = visibleReadOffsets.get(variable);
+ if (readOffsets != null) {
+ readOffsets.add(i);
+ }
+ }
+ }
+ if (visibleReadOffsets.isEmpty()) return false;
+ LOG.debug("visibleReadOffsets:", visibleReadOffsets);
+
+ final Map<PsiVariable, Set<PsiElement>> afterWrite = new THashMap<PsiVariable, Set<PsiElement>>();
+ for (PsiVariable variable : visibleReadOffsets.keySet()) {
+ final Function<Integer, BitSet> calculator = getReachableInstructionsCalculator(flow, flowStart, flowEnd);
+ final BitSet collectedOffsets = new BitSet(flowEnd);
+ for (final int writeOffset : writeOffsets.get(variable).toArray()) {
+ LOG.assertTrue(writeOffset >= flowStart, "writeOffset");
+ final BitSet reachableOffsets = calculator.fun(writeOffset);
+ collectedOffsets.or(reachableOffsets);
+ }
+ Set<PsiElement> throwSources = afterWrite.get(variable);
+ if (throwSources == null) afterWrite.put(variable, throwSources = new THashSet<PsiElement>());
+ for (int i = flowStart; i < flowEnd; i++) {
+ if (collectedOffsets.get(i)) {
+ throwSources.add(flow.getElement(i));
+ }
+ }
+ final List<PsiElement> subordinates = new ArrayList<PsiElement>();
+ for (PsiElement element : throwSources) {
+ if (throwSources.contains(element.getParent())) {
+ subordinates.add(element);
+ }
+ }
+ throwSources.removeAll(subordinates);
+ }
+ LOG.debug("afterWrite:", afterWrite);
+
+ for (Map.Entry<PsiVariable, Set<PsiElement>> entry : afterWrite.entrySet()) {
+ final PsiVariable variable = entry.getKey();
+ final PsiElement[] psiElements = entry.getValue().toArray(PsiElement.EMPTY_ARRAY);
+ final List<PsiClassType> thrownExceptions = ExceptionUtil.getThrownExceptions(psiElements);
+
+ if (!thrownExceptions.isEmpty()) {
+ final IntArrayList catchOrFinallyOffsets = new IntArrayList();
+ for (PsiTryStatement tryStatement : tryStatements) {
+ final PsiCodeBlock finallyBlock = tryStatement.getFinallyBlock();
+ if (finallyBlock != null) {
+ int offset = flow.getStartOffset(finallyBlock);
+ if (offset >= 0) {
+ catchOrFinallyOffsets.add(offset - 2); // -2 is an adjustment for rethrow-after-finally
+ }
+ }
+ for (PsiCatchSection catchSection : tryStatement.getCatchSections()) {
+ final PsiCodeBlock catchBlock = catchSection.getCatchBlock();
+ final PsiParameter parameter = catchSection.getParameter();
+ if (catchBlock != null && parameter != null) {
+ for (PsiClassType throwType : thrownExceptions) {
+ if (ControlFlowUtil.isCaughtExceptionType(throwType, parameter.getType())) {
+ int offset = flow.getStartOffset(catchBlock);
+ if (offset >= 0) {
+ catchOrFinallyOffsets.add(offset - 1); // -1 is an adjustment for catch block initialization
+ }
+ }
+ }
+ }
+ }
+ }
+ if (!catchOrFinallyOffsets.isEmpty()) {
+ final IntArrayList readOffsets = visibleReadOffsets.get(variable);
+ if (readOffsets != null && !readOffsets.isEmpty()) {
+ for (int j = 0; j < catchOrFinallyOffsets.size(); j++) {
+ int catchOrFinallyOffset = catchOrFinallyOffsets.get(j);
+ if (ControlFlowUtil.areInstructionsReachable(flow, readOffsets.toArray(), catchOrFinallyOffset)) {
+ LOG.debug("catchOrFinallyOffset:", catchOrFinallyOffset);
+ return true;
+ }
+ }
+ }
+ }
+ }
+ }
+ return false;
+ }
+
+ @Nullable
+ private static PsiTryStatement getEnclosingTryStatementHavingCatchOrFinally(@Nullable PsiElement startElement,
+ @NotNull PsiElement enclosingCodeFragment) {
+ for (PsiElement element = startElement; element != null && element != enclosingCodeFragment; element = element.getParent()) {
+ if (element instanceof PsiCodeBlock) {
+ final PsiElement parent = element.getParent();
+ if (parent instanceof PsiTryStatement) {
+ final PsiTryStatement tryStatement = (PsiTryStatement)parent;
+ if (tryStatement.getTryBlock() == element &&
+ (tryStatement.getFinallyBlock() != null || tryStatement.getCatchBlocks().length != 0)) {
+ return tryStatement;
+ }
+ }
+ }
+ }
+ return null;
+ }
+
+ @NotNull
+ private static List<PsiTryStatement> collectTryStatementStack(@Nullable PsiElement startElement,
+ @NotNull PsiElement enclosingCodeFragment) {
+ final List<PsiTryStatement> stack = new ArrayList<PsiTryStatement>();
+ for (PsiTryStatement tryStatement = getEnclosingTryStatementHavingCatchOrFinally(startElement, enclosingCodeFragment);
+ tryStatement != null;
+ tryStatement = getEnclosingTryStatementHavingCatchOrFinally(tryStatement, enclosingCodeFragment)) {
+ stack.add(tryStatement);
+ }
+ return stack;
+ }
+
@NotNull
public static PsiElement findCodeFragment(@NotNull PsiElement element) {
PsiElement codeFragment = element;
/**
* @return true if instruction at 'instructionOffset' is reachable from offset 'startOffset'
*/
- public static boolean isInstructionReachable(final ControlFlow flow, final int instructionOffset, final int startOffset) {
+ public static boolean isInstructionReachable(@NotNull final ControlFlow flow, final int instructionOffset, final int startOffset) {
+ return areInstructionsReachable(flow, new int[]{instructionOffset}, startOffset);
+ }
+
+ private static boolean areInstructionsReachable(@NotNull final ControlFlow flow,
+ @NotNull final int[] instructionOffsets,
+ final int startOffset) {
class MyVisitor extends InstructionClientVisitor<Boolean> {
boolean reachable;
@Override
public void visitInstruction(Instruction instruction, int offset, int nextOffset) {
- if (nextOffset == instructionOffset) reachable = true;
+ reachable |= ArrayUtil.indexOf(instructionOffsets, nextOffset) >= 0;
}
@Override
// Additional computations are required to take into account CALL and RETURN instructions in the case where
// the start offset isn't the beginning of the control flow, because we couldn't know the correct state
// of the call stack if we started traversal of the control flow from an offset in the middle.
- return isInstructionReachableConsideringCalls(flow, instructionOffset, startOffset);
+ return areInstructionsReachableWithCalls(flow, instructionOffsets, startOffset);
}
MyVisitor visitor = new MyVisitor();
depthFirstSearch(flow, visitor, startOffset, flow.getSize());
return false;
}
- public static boolean isInstructionReachableConsideringCalls(final ControlFlow flow, final int instructionOffset, final int startOffset) {
- class ControlFlowGraph {
- // The graph is sparse: simple instructions have 1 next offset, branching - 2 next offsets, RETURN may have many (one per call)
- final int[][] nextOffsets;
+ private abstract static class ControlFlowGraph extends InstructionClientVisitor<Void> {
+ // The graph is sparse: simple instructions have 1 next offset, branching - 2 next offsets, RETURN may have many (one per call)
+ final int[][] nextOffsets;
- ControlFlowGraph(int size) {
- nextOffsets = new int[size][];
- }
+ ControlFlowGraph(int size) {
+ nextOffsets = new int[size][];
+ }
- void addArc(int offset, int nextOffset) {
- if (nextOffsets[offset] == null) {
- nextOffsets[offset] = new int[]{nextOffset, -1};
- }
- else {
- int[] targets = nextOffsets[offset];
- if (ArrayUtil.indexOf(targets, nextOffset) < 0) {
- int freeIndex = ArrayUtil.indexOf(targets, -1);
- if (freeIndex >= 0) {
- targets[freeIndex] = nextOffset;
- }
- else {
- int oldLength = targets.length;
- nextOffsets[offset] = targets = ArrayUtil.realloc(targets, oldLength * 3 / 2);
- Arrays.fill(targets, oldLength, targets.length, -1);
- targets[oldLength] = nextOffset;
- }
+ @Override
+ public void visitInstruction(Instruction instruction, int offset, int nextOffset) {
+ if (nextOffset > size()) nextOffset = size();
+ addArc(offset, nextOffset);
+ }
+
+ void addArc(int offset, int nextOffset) {
+ if (nextOffsets[offset] == null) {
+ nextOffsets[offset] = new int[]{nextOffset, -1};
+ }
+ else {
+ int[] targets = nextOffsets[offset];
+ if (ArrayUtil.indexOf(targets, nextOffset) < 0) {
+ int freeIndex = ArrayUtil.indexOf(targets, -1);
+ if (freeIndex >= 0) {
+ targets[freeIndex] = nextOffset;
+ }
+ else {
+ int oldLength = targets.length;
+ nextOffsets[offset] = targets = ArrayUtil.realloc(targets, oldLength * 3 / 2);
+ Arrays.fill(targets, oldLength, targets.length, -1);
+ targets[oldLength] = nextOffset;
}
}
}
+ }
- int[] getNextOffsets(int offset) {
- return nextOffsets[offset] != null ? nextOffsets[offset] : ArrayUtil.EMPTY_INT_ARRAY;
- }
+ int[] getNextOffsets(int offset) {
+ return nextOffsets[offset] != null ? nextOffsets[offset] : ArrayUtil.EMPTY_INT_ARRAY;
+ }
+
+ int size() {
+ return nextOffsets.length;
+ }
- int size() {
- return nextOffsets.length;
+ @Override
+ public String toString() {
+ StringBuilder s = new StringBuilder();
+ for (int i = 0; i < nextOffsets.length; i++) {
+ int[] targets = nextOffsets[i];
+ if (targets != null && targets.length != 0 && targets[0] != -1) {
+ if (s.length() != 0) s.append(' ');
+ s.append('(').append(i).append("->");
+ for (int j = 0; j < targets.length && targets[j] != -1; j++) {
+ if (j != 0) s.append(",");
+ s.append(targets[j]);
+ }
+ s.append(')');
+ }
}
+ return s.toString();
+ }
- @Override
- public String toString() {
- StringBuilder s = new StringBuilder();
- for (int i = 0; i < nextOffsets.length; i++) {
- int[] targets = nextOffsets[i];
- if (targets != null && targets.length != 0 && targets[0] != -1) {
- if (s.length() != 0) s.append(' ');
- s.append('(').append(i).append("->");
- for (int j = 0; j < targets.length && targets[j] != -1; j++) {
- if (j != 0) s.append(",");
- s.append(targets[j]);
+ boolean depthFirstSearch(final int startOffset, final BitSet visitedOffsets) {
+ // traverse the graph starting with the startOffset
+ IntStack walkThroughStack = new IntStack(Math.max(size() / 2, 2));
+ visitedOffsets.clear();
+ walkThroughStack.push(startOffset);
+ while (!walkThroughStack.empty()) {
+ int currentOffset = walkThroughStack.pop();
+ if (currentOffset < size() && !visitedOffsets.get(currentOffset)) {
+ visitedOffsets.set(currentOffset);
+ int[] nextOffsets = getNextOffsets(currentOffset);
+ for (int nextOffset : nextOffsets) {
+ if (nextOffset == -1) break;
+ if (isComplete(currentOffset, nextOffset)) {
+ return true;
}
- s.append(')');
+ walkThroughStack.push(nextOffset);
}
}
- return s.toString();
}
+ return false;
}
- class MyVisitor extends InstructionClientVisitor<Boolean> {
- final ControlFlowGraph graph = new ControlFlowGraph(flow.getInstructions().size());
+ @Override
+ public Void getResult() {
+ return null;
+ }
- @Override
- public void visitInstruction(Instruction instruction, int offset, int nextOffset) {
- if (nextOffset > graph.size()) nextOffset = graph.size();
- graph.addArc(offset, nextOffset);
+ boolean isComplete(int offset, int nextOffset) {
+ return false;
+ }
+
+ void buildFrom(ControlFlow flow) {
+ // traverse the whole flow in order to collect the graph edges
+ ControlFlowUtil.depthFirstSearch(flow, this, 0, flow.getSize());
+ }
+ }
+
+ private static boolean areInstructionsReachableWithCalls(@NotNull final ControlFlow flow,
+ @NotNull final int[] instructionOffsets,
+ final int startOffset) {
+ ControlFlowGraph graph = new ControlFlowGraph(flow.getSize()) {
+ boolean isComplete(int offset, int nextOffset) {
+ return ArrayUtil.indexOf(instructionOffsets, nextOffset) >= 0;
}
+ };
+ graph.buildFrom(flow);
+ return graph.depthFirstSearch(startOffset, new BitSet(flow.getSize()));
+ }
+ private static Function<Integer, BitSet> getReachableInstructionsCalculator(@NotNull final ControlFlow flow,
+ final int flowStart,
+ final int flowEnd) {
+ final ControlFlowGraph graph = new ControlFlowGraph(flow.getSize()) {
@Override
- public Boolean getResult() {
- // The same logic as in depthFirstSearch(), just more lightweight implementation
- Arrays.fill(processedInstructions, false);
- IntStack walkThroughStack = new IntStack(Math.max(graph.size() / 2, 2));
- walkThroughStack.push(startOffset);
- while (!walkThroughStack.empty()) {
- int currentOffset = walkThroughStack.pop();
- if (currentOffset < graph.size() && !processedInstructions[currentOffset]) {
- processedInstructions[currentOffset] = true;
- int[] nextOffsets = graph.getNextOffsets(currentOffset);
- for (int nextOffset : nextOffsets) {
- if (nextOffset == -1) break;
- if (nextOffset == instructionOffset) {
- return true;
- }
- walkThroughStack.push(nextOffset);
- }
- }
+ void addArc(int offset, int nextOffset) {
+ nextOffset = promoteThroughGotoChain(flow, nextOffset);
+ if (nextOffset >= flowStart && nextOffset < flowEnd) {
+ super.addArc(offset, nextOffset);
}
- return false;
}
- }
+ };
+ graph.buildFrom(flow);
- MyVisitor visitor = new MyVisitor();
- depthFirstSearch(flow, visitor, 0, flow.getSize()); // traverse the graph, store the graph edges in visitor.graph
- return visitor.getResult().booleanValue(); // traverse the visitor.graph starting with the startOffset
+ return new Function<Integer, BitSet>() {
+ @Override
+ public BitSet fun(Integer startOffset) {
+ BitSet visitedOffsets = new BitSet(flowEnd);
+ graph.depthFirstSearch(startOffset, visitedOffsets);
+ return visitedOffsets;
+ }
+ };
}
public static boolean isVariableAssignedInLoop(@NotNull PsiReferenceExpression expression, PsiElement resolved) {
int startOffset = flow.getStartOffset(assignmentExpression);
return startOffset != -1 && isInstructionReachable(flow, startOffset, startOffset);
}
+
+ public static boolean isCaughtExceptionType(@NotNull PsiClassType throwType, @NotNull PsiType catchType) {
+ return catchType.isAssignableFrom(throwType) || mightBeAssignableFromSubclass(throwType, catchType);
+ }
+
+ private static boolean mightBeAssignableFromSubclass(@NotNull final PsiClassType throwType, @NotNull PsiType catchType) {
+ if (catchType instanceof PsiDisjunctionType) {
+ for (PsiType catchDisjunction : ((PsiDisjunctionType)catchType).getDisjunctions()) {
+ if (throwType.isAssignableFrom(catchDisjunction)) {
+ return true;
+ }
+ }
+ return false;
+ }
+ return throwType.isAssignableFrom(catchType);
+ }
}
\ No newline at end of file
projects / idea / community.git / commitdiff