java/java-impl/src/com/intellij/codeInspection/dataFlow/DfaMemoryStateImpl.java

   1 /*
   2  * Copyright 2000-2009 JetBrains s.r.o.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  * http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 /*
  18  * Created by IntelliJ IDEA.
  19  * User: max
  20  * Date: Jan 28, 2002
  21  * Time: 9:39:36 PM
  22  * To change template for new class use
  23  * Code Style | Class Templates options (Tools | IDE Options).
  24  */
  25 package com.intellij.codeInspection.dataFlow;
  26
  27 import com.intellij.codeInspection.dataFlow.value.*;
  28 import com.intellij.openapi.diagnostic.Logger;
  29 import com.intellij.openapi.progress.ProgressManager;
  30 import com.intellij.psi.PsiType;
  31 import com.intellij.psi.PsiVariable;
  32 import com.intellij.psi.util.TypeConversionUtil;
  33 import com.intellij.util.ArrayUtil;
  34 import com.intellij.util.containers.ContainerUtil;
  35 import com.intellij.util.containers.Stack;
  36 import gnu.trove.*;
  37 import org.jetbrains.annotations.NotNull;
  38 import org.jetbrains.annotations.Nullable;
  39
  40 import java.util.*;
  41
  42
  43 public class DfaMemoryStateImpl implements DfaMemoryState {
  44   private static final Logger LOG = Logger.getInstance("#com.intellij.codeInspection.dataFlow.DfaMemoryStateImpl");
  45   private final DfaValueFactory myFactory;
  46
  47   private ArrayList<SortedIntSet> myEqClasses;
  48   private int myStateSize;
  49   private Stack<DfaValue> myStack;
  50   private TIntStack myOffsetStack;
  51   private TLongHashSet myDistinctClasses;
  52   private Map<DfaVariableValue,DfaVariableState> myVariableStates;
  53
  54   public DfaMemoryStateImpl(final DfaValueFactory factory) {
  55     myFactory = factory;
  56     myEqClasses = new ArrayList<SortedIntSet>();
  57     myStateSize = 0;
  58     myStack = new Stack<DfaValue>();
  59     myDistinctClasses = new TLongHashSet();
  60     myVariableStates = new THashMap<DfaVariableValue, DfaVariableState>();
  61     myOffsetStack = new TIntStack(1);
  62   }
  63
  64   public DfaValueFactory getFactory() {
  65     return myFactory;
  66   }
  67
  68   protected DfaMemoryStateImpl createNew() {
  69     return new DfaMemoryStateImpl(myFactory);
  70   }
  71
  72   public DfaMemoryStateImpl createCopy() {
  73     DfaMemoryStateImpl newState = createNew();
  74
  75     newState.myStack = (Stack<DfaValue>)myStack.clone();
  76     newState.myDistinctClasses = new TLongHashSet(myDistinctClasses.toArray());
  77     newState.myEqClasses = new ArrayList<SortedIntSet>();
  78     newState.myStateSize = myStateSize;
  79     newState.myVariableStates = new THashMap<DfaVariableValue, DfaVariableState>();
  80     newState.myOffsetStack = new TIntStack(myOffsetStack);
  81
  82     for (int i = 0; i < myEqClasses.size(); i++) {
  83       SortedIntSet aClass = myEqClasses.get(i);
  84       newState.myEqClasses.add(aClass != null ? new SortedIntSet(aClass.toNativeArray()) : null);
  85     }
  86
  87     try {
  88       for (Object o : myVariableStates.keySet()) {
  89         DfaVariableValue dfaVariableValue = (DfaVariableValue)o;
  90         DfaVariableState clone = (DfaVariableState)myVariableStates.get(dfaVariableValue).clone();
  91         newState.myVariableStates.put(dfaVariableValue, clone);
  92       }
  93     }
  94     catch (CloneNotSupportedException e) {
  95       LOG.error(e);
  96     }
  97     return newState;
  98   }
  99
 100   public boolean equals(Object obj) {
 101     if (obj == this) return true;
 102     if (!(obj instanceof DfaMemoryState)) return false;
 103     DfaMemoryStateImpl that = (DfaMemoryStateImpl)obj;
 104
 105     if (myStateSize != that.myStateSize) return false;
 106     if (myDistinctClasses.size() != that.myDistinctClasses.size()) return false;
 107
 108     if (!myStack.equals(that.myStack)) return false;
 109     if (!myOffsetStack.equals(that.myOffsetStack)) return false;
 110     if (!myVariableStates.equals(that.myVariableStates)) return false;
 111
 112     int[] permutation = getPermutationToSortedState();
 113     int[] thatPermutation = that.getPermutationToSortedState();
 114
 115     for (int i = 0; i < myStateSize; i++) {
 116       SortedIntSet thisClass = myEqClasses.get(permutation[i]);
 117       SortedIntSet thatClass = that.myEqClasses.get(thatPermutation[i]);
 118       if (thisClass == null) break;
 119       if (thisClass.compareTo(thatClass) != 0) return false;
 120     }
 121
 122     long[] pairs = getSortedDistinctClasses(permutation);
 123     long[] thatPairs = that.getSortedDistinctClasses(thatPermutation);
 124
 125     for (int i = 0; i < pairs.length; i++) {
 126       if (pairs[i] != thatPairs[i]) {
 127         return false;
 128       }
 129     }
 130
 131     return true;
 132   }
 133
 134   private long[] getSortedDistinctClasses(int[] permutation) {
 135     long[] pairs = myDistinctClasses.toArray();
 136     for (int i = 0; i < pairs.length; i++) {
 137       pairs[i] = convert(pairs[i], permutation);
 138     }
 139     Arrays.sort(pairs);
 140     return pairs;
 141   }
 142
 143   private long convert(long pair, int[] permutation) {
 144     if (myEqClasses.get(low(pair)) == null || myEqClasses.get(high(pair)) == null) {
 145       return -1L;
 146     }
 147     return createPair(inversePermutation(permutation, low(pair)), inversePermutation(permutation, high(pair)));
 148   }
 149
 150   private static int inversePermutation(int[] permutation, int idx) {
 151     for (int i = 0; i < permutation.length; i++) {
 152       if (idx == permutation[i]) return i;
 153     }
 154     return -1;
 155   }
 156
 157   private int[] getPermutationToSortedState() {
 158     int size = myEqClasses.size();
 159     int[] permutation = ArrayUtil.newIntArray(size);
 160     for (int i = 0; i < size; i++) {
 161       permutation[i] = i;
 162     }
 163
 164     for (int i = 0; i < permutation.length; i++) {
 165       for (int j = i + 1; j < permutation.length; j++) {
 166         if (compare(permutation[i], permutation[j]) > 0) {
 167           int t = permutation[i];
 168           permutation[i] = permutation[j];
 169           permutation[j] = t;
 170         }
 171       }
 172     }
 173
 174     return permutation;
 175   }
 176
 177   private int compare(int i1, int i2) {
 178     SortedIntSet s1 = myEqClasses.get(i1);
 179     SortedIntSet s2 = myEqClasses.get(i2);
 180     if (s1 == null && s2 == null) return 0;
 181     if (s1 == null) return 1;
 182     if (s2 == null) return -1;
 183     return s1.compareTo(s2);
 184   }
 185
 186   public int hashCode() {
 187     return 0;
 188     //return myEqClasses.hashCode() + myStack.hashCode() + myVariableStates.hashCode();
 189   }
 190
 191   private void appendClass(StringBuffer buf, int aClassIndex) {
 192     SortedIntSet aClass = myEqClasses.get(aClassIndex);
 193     if (aClass != null) {
 194       buf.append("(");
 195
 196       for (int i = 0; i < aClass.size(); i++) {
 197         if (i > 0) buf.append(", ");
 198         int value = aClass.get(i);
 199         DfaValue dfaValue = myFactory.getValue(value);
 200         buf.append(dfaValue);
 201       }
 202       buf.append(")");
 203     }
 204   }
 205
 206   @SuppressWarnings({"HardCodedStringLiteral"})
 207   public String toString() {
 208     StringBuffer result = new StringBuffer();
 209     result.append('<');
 210
 211     for (int i = 0; i < myEqClasses.size(); i++) {
 212       appendClass(result, i);
 213     }
 214
 215     result.append(" distincts: ");
 216     long[] dclasses = myDistinctClasses.toArray();
 217     for (long pair : dclasses) {
 218       result.append("{");
 219       appendClass(result, low(pair));
 220       result.append(", ");
 221       appendClass(result, high(pair));
 222       result.append("} ");
 223     }
 224
 225     result.append(" stack: ");
 226     for (DfaValue value : myStack) {
 227       result.append(value);
 228     }
 229     result.append('>');
 230     return result.toString();
 231   }
 232
 233   public DfaValue pop() {
 234     return myStack.pop();
 235   }
 236
 237   public DfaValue peek() {
 238     return myStack.peek();
 239   }
 240
 241   public void push(@NotNull DfaValue value) {
 242     myStack.push(value);
 243   }
 244
 245   public int popOffset() {
 246     return myOffsetStack.pop();
 247   }
 248
 249   public void pushOffset(int offset) {
 250     myOffsetStack.push(offset);
 251   }
 252
 253   public void emptyStack() {
 254     myStack.clear();
 255   }
 256
 257   public void setVarValue(DfaVariableValue var, DfaValue value) {
 258     flushVariable(var);
 259     if (value instanceof DfaUnknownValue) return;
 260
 261     getVariableState(var).setValue(value);
 262     if (value instanceof DfaNotNullValue) {
 263       DfaTypeValue dfaType = myFactory.getTypeFactory().create(((DfaNotNullValue)value).getType());
 264       DfaRelationValue dfaInstanceof = myFactory.getRelationFactory().create(var, dfaType, "instanceof", false);
 265       applyCondition(dfaInstanceof);
 266       applyCondition(compareToNull(var, true));
 267     }
 268     else if (value instanceof DfaTypeValue) {
 269       DfaRelationValue dfaInstanceof = myFactory.getRelationFactory().create(var, value, "instanceof", false);
 270       applyInstanceofOrNull(dfaInstanceof);
 271     }
 272     else {
 273       DfaRelationValue dfaEqual = myFactory.getRelationFactory().create(var, value, "==", false);
 274       if (dfaEqual == null) return;
 275       applyCondition(dfaEqual);
 276
 277       if (value instanceof DfaVariableValue) {
 278         try {
 279           DfaVariableState newState = (DfaVariableState)getVariableState((DfaVariableValue)value).clone();
 280           myVariableStates.put(var, newState);
 281         }
 282         catch (CloneNotSupportedException e) {
 283           LOG.error(e);
 284         }
 285       }
 286     }
 287
 288     if (getVariableState(var).isNotNull()) {
 289       applyCondition(compareToNull(var, true));
 290     }
 291   }
 292
 293   private int getOrCreateEqClassIndex(DfaValue dfaValue) {
 294     int i = getEqClassIndex(dfaValue);
 295     if (i != -1) return i;
 296     SortedIntSet aClass = new SortedIntSet();
 297     aClass.add(dfaValue.getID());
 298     myEqClasses.add(aClass);
 299     myStateSize++;
 300
 301     return myEqClasses.size() - 1;
 302   }
 303
 304   @NotNull
 305   private List<DfaValue> getEqClassesFor(@NotNull DfaValue dfaValue) {
 306     int index = getEqClassIndex(dfaValue);
 307     SortedIntSet set = index == -1 ? null : myEqClasses.get(index);
 308     if (set == null) {
 309       return Collections.emptyList();
 310     }
 311     final List<DfaValue> result = new ArrayList<DfaValue>(set.size());
 312     set.forEach(new TIntProcedure() {
 313       public boolean execute(int c1) {
 314         DfaValue value = myFactory.getValue(c1);
 315         result.add(value);
 316         return true;
 317       }
 318     });
 319     return result;
 320   }
 321
 322   public  boolean canBeNaN(@NotNull DfaValue dfaValue) {
 323     List<DfaValue> eqClasses = getEqClassesFor(dfaValue);
 324     for (DfaValue eqClass : eqClasses) {
 325       if (isNaN(eqClass)) return true;
 326     }
 327     return false;
 328   }
 329
 330   private int getEqClassIndex(@NotNull DfaValue dfaValue) {
 331     for (int i = 0; i < myEqClasses.size(); i++) {
 332       SortedIntSet aClass = myEqClasses.get(i);
 333       if (aClass != null && aClass.contains(dfaValue.getID())) {
 334         if (dfaValue instanceof DfaBoxedValue && !canBeReused(((DfaBoxedValue)dfaValue).getWrappedValue(), this) && aClass.size() > 1) return -1;
 335         return i;
 336       }
 337     }
 338     return -1;
 339   }
 340   private static boolean canBeReused(final DfaValue valueToWrap, final DfaMemoryState memoryState) {
 341     if (valueToWrap instanceof DfaConstValue) {
 342       return cacheable((DfaConstValue)valueToWrap);
 343     }
 344     else if (valueToWrap instanceof DfaVariableValue) {
 345       if (PsiType.BOOLEAN.equals(((DfaVariableValue)valueToWrap).getPsiVariable().getType())) return true;
 346       List<DfaValue> values = ((DfaMemoryStateImpl)memoryState).getEqClassesFor(valueToWrap);
 347       for (DfaValue value : values) {
 348         if (value instanceof DfaConstValue && cacheable((DfaConstValue)value)) return true;
 349       }
 350       return false;
 351     }
 352     return false;
 353     //throw new IllegalArgumentException(""+valueToWrap);
 354   }
 355
 356   private static boolean cacheable(DfaConstValue dfaConstValue) {
 357     Object value = dfaConstValue.getValue();
 358     return box(value) == box(value);
 359   }
 360
 361   @SuppressWarnings({"UnnecessaryBoxing"})
 362   private static Object box(final Object value) {
 363     Object newBoxedValue;
 364     if (value instanceof Integer) newBoxedValue = Integer.valueOf(((Integer)value).intValue());
 365     else if (value instanceof Byte) newBoxedValue = Byte.valueOf(((Byte)value).byteValue());
 366     else if (value instanceof Short) newBoxedValue = Short.valueOf(((Short)value).shortValue());
 367     else if (value instanceof Long) newBoxedValue = Long.valueOf(((Long)value).longValue());
 368     else if (value instanceof Boolean) newBoxedValue = Boolean.valueOf(((Boolean)value).booleanValue());
 369     else if (value instanceof Character) newBoxedValue = Character.valueOf(((Character)value).charValue());
 370     else return new Object();
 371     return newBoxedValue;
 372   }
 373
 374   private boolean uniteClasses(int c1Index, int c2Index) {
 375     SortedIntSet c1 = myEqClasses.get(c1Index);
 376     SortedIntSet c2 = myEqClasses.get(c2Index);
 377
 378     Set<PsiVariable> vars = new THashSet<PsiVariable>();
 379     Set<PsiVariable> negatedvars = new THashSet<PsiVariable>();
 380     int[] cs = new int[c1.size() + c2.size()];
 381     c1.set(0, cs, 0, c1.size());
 382     c2.set(0, cs, c1.size(), c2.size());
 383
 384     int nConst = 0;
 385     for (int c : cs) {
 386       DfaValue dfaValue = myFactory.getValue(c);
 387       if (dfaValue instanceof DfaBoxedValue) dfaValue = ((DfaBoxedValue)dfaValue).getWrappedValue();
 388       if (dfaValue instanceof DfaUnboxedValue) dfaValue = ((DfaUnboxedValue)dfaValue).getVariable();
 389       if (dfaValue instanceof DfaConstValue) nConst++;
 390       if (dfaValue instanceof DfaVariableValue) {
 391         DfaVariableValue variableValue = (DfaVariableValue)dfaValue;
 392         PsiVariable variable = variableValue.getPsiVariable();
 393         Set<PsiVariable> set = variableValue.isNegated() ? negatedvars : vars;
 394         set.add(variable);
 395       }
 396       if (nConst > 1) return false;
 397     }
 398     if (ContainerUtil.intersects(vars, negatedvars)) return false;
 399
 400     TLongArrayList c2Pairs = new TLongArrayList();
 401     long[] distincts = myDistinctClasses.toArray();
 402     for (long distinct : distincts) {
 403       int pc1 = low(distinct);
 404       int pc2 = high(distinct);
 405       boolean addedToC1 = false;
 406
 407       if (pc1 == c1Index || pc2 == c1Index) {
 408         addedToC1 = true;
 409       }
 410
 411       if (pc1 == c2Index || pc2 == c2Index) {
 412         if (addedToC1) return false;
 413         c2Pairs.add(distinct);
 414       }
 415     }
 416
 417     for (int i = 0; i < c2.size(); i++) {
 418       int c = c2.get(i);
 419       c1.add(c);
 420     }
 421
 422     for (int i = 0; i < c2Pairs.size(); i++) {
 423       long c = c2Pairs.get(i);
 424       myDistinctClasses.remove(c);
 425       myDistinctClasses.add(createPair(c1Index, low(c) == c2Index ? high(c) : low(c)));
 426     }
 427     myEqClasses.set(c2Index, null);
 428     myStateSize--;
 429
 430     return true;
 431   }
 432
 433   private static int low(long l) {
 434     return (int)(l & 0xFFFFFFFF);
 435   }
 436
 437   private static int high(long l) {
 438     return (int)((l & 0xFFFFFFFF00000000L) >> 32);
 439   }
 440
 441   private static long createPair(int i1, int i2) {
 442     if (i1 < i2) {
 443       long l = i1;
 444       l <<= 32;
 445       l += i2;
 446       return l;
 447     }
 448     else {
 449       long l = i2;
 450       l <<= 32;
 451       l += i1;
 452       return l;
 453     }
 454   }
 455
 456   private void makeClassesDistinct(int c1Index, int c2Index) {
 457     myDistinctClasses.add(createPair(c1Index, c2Index));
 458   }
 459
 460   public boolean isNull(DfaValue dfaValue) {
 461     if (dfaValue instanceof DfaNotNullValue) return false;
 462
 463     if (dfaValue instanceof DfaVariableValue || dfaValue instanceof DfaConstValue) {
 464       DfaConstValue dfaNull = myFactory.getConstFactory().getNull();
 465       int c1Index = getOrCreateEqClassIndex(dfaValue);
 466       int c2Index = getOrCreateEqClassIndex(dfaNull);
 467
 468       return c1Index == c2Index;
 469     }
 470
 471     return false;
 472   }
 473
 474   public boolean isNotNull(DfaVariableValue dfaVar) {
 475     DfaConstValue dfaNull = myFactory.getConstFactory().getNull();
 476     int c1Index = getOrCreateEqClassIndex(dfaVar);
 477     int c2Index = getOrCreateEqClassIndex(dfaNull);
 478
 479     long[] pairs = myDistinctClasses.toArray();
 480     for (long pair : pairs) {
 481       if (low(pair) == c1Index && high(pair) == c2Index ||
 482           high(pair) == c1Index && low(pair) == c2Index) {
 483         return true;
 484       }
 485     }
 486
 487     return false;
 488   }
 489
 490   public boolean applyInstanceofOrNull(DfaRelationValue dfaCond) {
 491     DfaValue left = dfaCond.getLeftOperand();
 492     if (left instanceof DfaBoxedValue) {
 493       left = ((DfaBoxedValue)left).getWrappedValue();
 494     }
 495     else if (left instanceof DfaUnboxedValue) {
 496       left = ((DfaUnboxedValue)left).getVariable();
 497     }
 498
 499     if (!(left instanceof DfaVariableValue)) return true;
 500
 501     DfaVariableValue dfaVar = (DfaVariableValue)left;
 502     DfaTypeValue dfaType = (DfaTypeValue)dfaCond.getRightOperand();
 503
 504     final DfaVariableState varState = getVariableState(dfaVar);
 505     varState.setNullable(varState.isNullable() || dfaType.isNullable());
 506     return !isNotNull(dfaVar) || varState.setInstanceofValue(dfaType);
 507   }
 508
 509   public boolean applyCondition(DfaValue dfaCond) {
 510     if (dfaCond instanceof DfaUnknownValue) return true;
 511     if (dfaCond instanceof DfaUnboxedValue) {
 512       DfaVariableValue dfaVar = ((DfaUnboxedValue)dfaCond).getVariable();
 513       boolean isNegated = dfaVar.isNegated();
 514       DfaVariableValue dfaNormalVar = isNegated ? (DfaVariableValue)dfaVar.createNegated() : dfaVar;
 515       DfaConstValue dfaTrue = myFactory.getConstFactory().getTrue();
 516       final DfaValue boxedTrue = myFactory.getBoxedFactory().createBoxed(dfaTrue);
 517       DfaRelationValue dfaEqualsTrue = myFactory.getRelationFactory().create(dfaNormalVar, boxedTrue, "==", isNegated);
 518
 519       return applyCondition(dfaEqualsTrue);
 520     }
 521     if (dfaCond instanceof DfaVariableValue) {
 522       DfaVariableValue dfaVar = (DfaVariableValue)dfaCond;
 523       boolean isNegated = dfaVar.isNegated();
 524       DfaVariableValue dfaNormalVar = isNegated ? (DfaVariableValue)dfaVar.createNegated() : dfaVar;
 525       DfaConstValue dfaTrue = myFactory.getConstFactory().getTrue();
 526       DfaRelationValue dfaEqualsTrue = myFactory.getRelationFactory().create(dfaNormalVar, dfaTrue, "==", isNegated);
 527
 528       return applyCondition(dfaEqualsTrue);
 529     }
 530
 531     if (dfaCond instanceof DfaConstValue) {
 532       return dfaCond == myFactory.getConstFactory().getTrue() || dfaCond != myFactory.getConstFactory().getFalse();
 533     }
 534
 535     if (!(dfaCond instanceof DfaRelationValue)) return true;
 536
 537     DfaRelationValue dfaRelation = (DfaRelationValue)dfaCond;
 538     DfaValue dfaLeft = dfaRelation.getLeftOperand();
 539     DfaValue dfaRight = dfaRelation.getRightOperand();
 540     if (dfaRight == null || dfaLeft == null) return false;
 541
 542     boolean isNegated = dfaRelation.isNegated();
 543     if (dfaLeft instanceof DfaNotNullValue && dfaRight == myFactory.getConstFactory().getNull()) {
 544       return isNegated;
 545     }
 546
 547     if (dfaRight instanceof DfaTypeValue) {
 548       if (dfaLeft instanceof DfaVariableValue) {
 549         DfaVariableState varState = getVariableState((DfaVariableValue)dfaLeft);
 550         DfaVariableValue dfaVar = (DfaVariableValue)dfaLeft;
 551         if (isNegated) {
 552           return varState.addNotInstanceofValue((DfaTypeValue)dfaRight) || applyCondition(compareToNull(dfaVar, false));
 553         }
 554         return applyCondition(compareToNull(dfaVar, true)) && varState.setInstanceofValue((DfaTypeValue)dfaRight);
 555       }
 556       return true;
 557     }
 558
 559     if (dfaRight == myFactory.getConstFactory().getNull() && dfaLeft instanceof DfaVariableValue) {
 560       final DfaVariableState varState = getVariableState((DfaVariableValue)dfaLeft);
 561       if (varState.isNotNull()) return isNegated;
 562       varState.setNullable(true);
 563     }
 564
 565     if (dfaLeft instanceof DfaUnknownValue || dfaRight instanceof DfaUnknownValue) return true;
 566
 567     boolean result = applyRelation(dfaLeft, dfaRight, isNegated);
 568     if (dfaRight instanceof DfaConstValue) {
 569       Object constVal = ((DfaConstValue)dfaRight).getValue();
 570       if (constVal instanceof Boolean) {
 571         boolean neg = !((Boolean)constVal).booleanValue();
 572         DfaConstValue negVal = myFactory.getConstFactory().createFromValue(Boolean.valueOf(neg), PsiType.BOOLEAN);
 573         result &= applyRelation(dfaLeft, negVal, !isNegated);
 574       }
 575     }
 576     if (dfaLeft instanceof DfaVariableValue) {
 577       PsiVariable psiVariable = ((DfaVariableValue)dfaLeft).getPsiVariable();
 578       if (TypeConversionUtil.isPrimitiveWrapper(psiVariable.getType())
 579           && (!isNegated // from the fact (wrappers are not the same) does not follow (unboxed values are not equals)
 580               || dfaRight instanceof DfaConstValue || dfaRight instanceof DfaBoxedValue && ((DfaBoxedValue)dfaRight).getWrappedValue() instanceof DfaConstValue)
 581       ){
 582         dfaLeft = myFactory.getBoxedFactory().createUnboxed(dfaLeft);
 583         dfaRight = myFactory.getBoxedFactory().createUnboxed(dfaRight);
 584         result &= applyRelation(dfaLeft, dfaRight, isNegated);
 585       }
 586       else if (TypeConversionUtil.isPrimitiveAndNotNull(psiVariable.getType())){
 587         dfaLeft = myFactory.getBoxedFactory().createBoxed(dfaLeft);
 588         dfaRight = myFactory.getBoxedFactory().createBoxed(dfaRight);
 589         if (dfaLeft != null && dfaRight != null) {
 590           result &= applyRelation(dfaLeft, dfaRight, isNegated);
 591         }
 592       }
 593     }
 594
 595     return result;
 596   }
 597
 598   private static boolean isNaN(final DfaValue dfa) {
 599     if (dfa instanceof DfaConstValue) {
 600       Object value = ((DfaConstValue)dfa).getValue();
 601       if (value instanceof Double && ((Double)value).isNaN()) return true;
 602       if (value instanceof Float && ((Float)value).isNaN()) return true;
 603     }
 604     else if (dfa instanceof DfaBoxedValue){
 605       return isNaN(((DfaBoxedValue)dfa).getWrappedValue());
 606     }
 607     return false;
 608   }
 609
 610   private boolean applyRelation(@NotNull final DfaValue dfaLeft, @NotNull final DfaValue dfaRight, boolean isNegated) {
 611     // DfaConstValue || DfaVariableValue
 612     int c1Index = getOrCreateEqClassIndex(dfaLeft);
 613     int c2Index = getOrCreateEqClassIndex(dfaRight);
 614
 615     if (!isNegated) { //Equals
 616       if (c1Index == c2Index) return true;
 617       if (!uniteClasses(c1Index, c2Index)) return false;
 618     }
 619     else { // Not Equals
 620       if (c1Index == c2Index) return false;
 621       makeClassesDistinct(c1Index, c2Index);
 622     }
 623
 624     return true;
 625   }
 626
 627   public boolean checkNotNullable(DfaValue value) {
 628     if (value == myFactory.getConstFactory().getNull()) return false;
 629     if (value instanceof DfaTypeValue && ((DfaTypeValue)value).isNullable()) return false;
 630
 631     if (value instanceof DfaVariableValue) {
 632       if (isNotNull((DfaVariableValue)value)) return true;
 633       final DfaVariableState varState = getVariableState((DfaVariableValue)value);
 634       if (varState.isNullable()) return false;
 635     }
 636     return true;
 637   }
 638
 639   public boolean applyNotNull(DfaValue value) {
 640     return checkNotNullable(value) && applyCondition(compareToNull(value, true));
 641   }
 642
 643   @Nullable
 644   private DfaRelationValue compareToNull(DfaValue dfaVar, boolean negated) {
 645     DfaConstValue dfaNull = myFactory.getConstFactory().getNull();
 646     return myFactory.getRelationFactory().create(dfaVar, dfaNull, "==", negated);
 647   }
 648
 649   public DfaVariableState getVariableState(DfaVariableValue dfaVar) {
 650     DfaVariableState state = myVariableStates.get(dfaVar);
 651
 652     if (state == null) {
 653       final PsiVariable psiVariable = dfaVar.getPsiVariable();
 654       state = createVariableState(psiVariable);
 655       myVariableStates.put(dfaVar, state);
 656       if (psiVariable != null) {
 657         state.setInstanceofValue(myFactory.getTypeFactory().create(psiVariable.getType()));
 658       }
 659     }
 660
 661     return state;
 662   }
 663
 664   protected Map<DfaVariableValue, DfaVariableState> getVariableStates() {
 665     return myVariableStates;
 666   }
 667
 668   protected DfaVariableState createVariableState(final PsiVariable psiVariable) {
 669     return new DfaVariableState(psiVariable);
 670   }
 671
 672   public void flushFields(DataFlowRunner runner) {
 673     DfaVariableValue[] fields = runner.getFields();
 674     for (DfaVariableValue field : fields) {
 675       flushVariable(field);
 676     }
 677   }
 678
 679   public void flushVariable(@NotNull DfaVariableValue variable) {
 680     final int id = variable.getID();
 681     int size = myEqClasses.size();
 682     int interruptCount = 0;
 683     for (int varClassIndex = 0; varClassIndex < size; varClassIndex++) {
 684       final SortedIntSet varClass = myEqClasses.get(varClassIndex);
 685       if (varClass == null) continue;
 686
 687       for (int i = 0; i < varClass.size(); i++) {
 688         if ((++interruptCount & 0xf) == 0) {
 689           ProgressManager.checkCanceled();
 690         }
 691         int cl = varClass.get(i);
 692         DfaValue value = myFactory.getValue(cl);
 693         if (value != null && id == value.getID() ||
 694             value instanceof DfaBoxedValue && ((DfaBoxedValue)value).getWrappedValue().getID() == id ||
 695             value instanceof DfaUnboxedValue && ((DfaUnboxedValue)value).getVariable().getID() == id) {
 696           varClass.remove(i);
 697           break;
 698         }
 699       }
 700
 701       if (varClass.isEmpty()) {
 702         myEqClasses.set(varClassIndex, null);
 703         myStateSize--;
 704         long[] pairs = myDistinctClasses.toArray();
 705         for (long pair : pairs) {
 706           if (low(pair) == varClassIndex || high(pair) == varClassIndex) {
 707             myDistinctClasses.remove(pair);
 708           }
 709         }
 710       }
 711     }
 712
 713     myVariableStates.remove(variable);
 714   }
 715 }