From ee6f85b2a0ac56c9759a4581ae8a03fbfd4b4d3c Mon Sep 17 00:00:00 2001 From: Oleg Shpynov Date: Fri, 12 Mar 2010 18:29:17 +0300 Subject: [PATCH] Python reaching defs fix leading to unbound local variable inspection false positives --- .../controlflow/ControlFlowUtil.java | 7 ++++- .../codeInsight/dataflow/DFAEngine.java | 31 +++---------------- .../intellij/codeInsight/dataflow/DFAMap.java | 26 ++++++++++++++-- .../codeInsight/dataflow/DfaInstance.java | 2 ++ 4 files changed, 37 insertions(+), 29 deletions(-) diff --git a/platform/lang-impl/src/com/intellij/codeInsight/controlflow/ControlFlowUtil.java b/platform/lang-impl/src/com/intellij/codeInsight/controlflow/ControlFlowUtil.java index 0d690cb36dc7..5860786b79e9 100644 --- a/platform/lang-impl/src/com/intellij/codeInsight/controlflow/ControlFlowUtil.java +++ b/platform/lang-impl/src/com/intellij/codeInsight/controlflow/ControlFlowUtil.java @@ -56,6 +56,11 @@ public class ControlFlowUtil { public void clear() { myIndex = -1; } + + @Override + public String toString() { + return "Stack(" + (myIndex + 1) + ") elements"; + } } public static int[] postOrder(Instruction[] flow) { @@ -74,7 +79,7 @@ public class ControlFlowUtil { while (!stack.isEmpty()) { final int num = stack.pop(); - result[num] = N++; + result[N++] = num; for (Instruction succ : flow[num].allSucc()) { final int succNum = succ.num(); if (!visited[succNum]) { diff --git a/platform/lang-impl/src/com/intellij/codeInsight/dataflow/DFAEngine.java b/platform/lang-impl/src/com/intellij/codeInsight/dataflow/DFAEngine.java index 94457d42c0ac..4e30944ef4ae 100644 --- a/platform/lang-impl/src/com/intellij/codeInsight/dataflow/DFAEngine.java +++ b/platform/lang-impl/src/com/intellij/codeInsight/dataflow/DFAEngine.java @@ -23,7 +23,7 @@ import java.util.*; public class DFAEngine { private static final Logger LOG = Logger.getInstance(DFAEngine.class.getName()); - private static final double TIME_LIMIT = 5*10e9; + private static final double TIME_LIMIT = 3*10e9; private final Instruction[] myFlow; @@ -60,8 +60,6 @@ public class DFAEngine { final boolean forward = myDfa.isForward(); final int[] order = ControlFlowUtil.postOrder(myFlow); -// Count limit for number of iterations per worklist - final int limit = getIterationLimit(forward); int dfaCount = 0; final long startTime = System.nanoTime(); @@ -76,8 +74,6 @@ public class DFAEngine { break; } - // Iteration count per one worklist - int count = 0; final Instruction instruction = myFlow[order[i]]; final int number = instruction.num(); @@ -87,13 +83,7 @@ public class DFAEngine { visited[number] = true; while (true) { - count++; - if (count > limit){ - if (LOG.isDebugEnabled()){ - LOG.debug("Iteration count exceeded on worklist"); - } - break; - } + dfaCount++; final Instruction currentInstruction = worklist.poll(); if (currentInstruction == null) { @@ -105,6 +95,9 @@ public class DFAEngine { final DFAMap joinedE = join(currentInstruction, info); final DFAMap newE = myDfa.fun(joinedE, currentInstruction); if (!mySemilattice.eq(newE, oldE)) { + if (LOG.isDebugEnabled()){ + LOG.debug("Number: " + currentNumber + " old: " + oldE.keySet() + " new: " + newE.keySet()); + } info.set(currentNumber, newE); for (Instruction next : getNext(currentInstruction)) { worklist.add(next); @@ -120,7 +113,6 @@ public class DFAEngine { } else { i--; } - dfaCount += count; } if (LOG.isDebugEnabled()){ LOG.debug("Done in: " + (System.nanoTime() - startTime)/10e6 + "ms. Ratio: " + dfaCount / myFlow.length); @@ -129,19 +121,6 @@ public class DFAEngine { } - /** - * Count limit for dfa number of iterations. - * Every node in dfa should be processed <= pred times * 2 - * Multiplier 2 is because of cycles. - */ - private int getIterationLimit(final boolean forward) { - int allPred = myFlow.length; - for (Instruction instruction : myFlow) { - allPred += forward ? instruction.allPred().size() : instruction.allSucc().size(); - } - return allPred * 2; - } - private DFAMap join(final Instruction instruction, final List> info) { final Iterable prev = myDfa.isForward() ? instruction.allPred() : instruction.allSucc(); final ArrayList> prevInfos = new ArrayList>(); diff --git a/platform/lang-impl/src/com/intellij/codeInsight/dataflow/DFAMap.java b/platform/lang-impl/src/com/intellij/codeInsight/dataflow/DFAMap.java index bb57567e16e6..148a5942c3ec 100644 --- a/platform/lang-impl/src/com/intellij/codeInsight/dataflow/DFAMap.java +++ b/platform/lang-impl/src/com/intellij/codeInsight/dataflow/DFAMap.java @@ -37,7 +37,7 @@ public class DFAMap { public DFAMap() { } - public DFAMap(DFAMap initialMap) { + private DFAMap(DFAMap initialMap) { myK = initialMap.myK; myV = initialMap.myV; myAll = initialMap.myAll == null ? null : new HashMap(initialMap.myAll); @@ -71,6 +71,7 @@ public class DFAMap { } } + @Nullable public V get(String key) { if (myAll != null) { return myAll.get(key); @@ -166,6 +167,27 @@ public class DFAMap { } public DFAMap asWritable() { - return this; + return new DFAMap(this); + } + + @Override + public String toString() { + if (this == ourEmptyMap){ + return "Empty Map"; + } + if (myAll != null){ + return myAll.toString(); + } + if (myK != null){ + return "{" + myK + "=" + myV + "}"; + } + return "Empty"; + } + + public Set keySet() { + if (myAll != null){ + return myAll.keySet(); + } + return myK != null ? Collections.singleton(myK) : Collections.emptySet(); } } diff --git a/platform/lang-impl/src/com/intellij/codeInsight/dataflow/DfaInstance.java b/platform/lang-impl/src/com/intellij/codeInsight/dataflow/DfaInstance.java index 716ec6989374..ce618834fe4b 100644 --- a/platform/lang-impl/src/com/intellij/codeInsight/dataflow/DfaInstance.java +++ b/platform/lang-impl/src/com/intellij/codeInsight/dataflow/DfaInstance.java @@ -18,6 +18,8 @@ import com.intellij.codeInsight.controlflow.Instruction; import org.jetbrains.annotations.NotNull; public interface DfaInstance { + // Please ensure that E has correctly implemented equals method + // Invariant: fun must create new instance of DFAMap if modifies it DFAMap fun(DFAMap e, Instruction instruction); -- 2.32.0