Restore DFA instruction count limit
authorOleg Shpynov <oleg.shpynov@jetbrains.com>
Fri, 12 Mar 2010 15:58:48 +0000 (18:58 +0300)
committerOleg Shpynov <oleg.shpynov@jetbrains.com>
Fri, 12 Mar 2010 15:58:48 +0000 (18:58 +0300)
platform/lang-impl/src/com/intellij/codeInsight/dataflow/DFAEngine.java

index 4e30944ef4ae80bdd796bd0d516f41abd6ae6edc..65908b8d7466ec5e1ddf15ea4166ba300f92027c 100644 (file)
@@ -60,6 +60,8 @@ public class DFAEngine<E> {
     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();
 
@@ -74,6 +76,8 @@ public class DFAEngine<E> {
         break;
       }
 
+      // Iteration count per one worklist
+      int count = 0;
       final Instruction instruction = myFlow[order[i]];
       final int number = instruction.num();
 
@@ -82,8 +86,17 @@ public class DFAEngine<E> {
         worklist.add(instruction);
         visited[number] = true;
 
+        // It is essential to apply this check!!!
+        // This gives us more chances that resulting info will be closer to expected result
+        // Also it is used as indicator that "equals" method is implemented correctly in E
         while (true) {
-          dfaCount++;
+          count++;
+          if (count > limit){
+             if (LOG.isDebugEnabled()){
+               LOG.debug("Iteration count exceeded on worklist");
+             }
+             break;
+          }
 
           final Instruction currentInstruction = worklist.poll();
           if (currentInstruction == null) {
@@ -113,6 +126,7 @@ public class DFAEngine<E> {
       } else {
         i--;
       }
+      dfaCount += count;
     }
     if (LOG.isDebugEnabled()){
       LOG.debug("Done in: " + (System.nanoTime() - startTime)/10e6 + "ms. Ratio: " + dfaCount / myFlow.length);
@@ -121,6 +135,19 @@ public class DFAEngine<E> {
   }
 
 
+  /**
+   * 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<E> join(final Instruction instruction, final List<DFAMap<E>> info) {
     final Iterable<? extends Instruction> prev = myDfa.isForward() ? instruction.allPred() : instruction.allSucc();
     final ArrayList<DFAMap<E>> prevInfos = new ArrayList<DFAMap<E>>();