java/java-analysis-impl/src/com/intellij/codeInspection/dataFlow/StateMerger.java

   1 /*
   2  * Copyright 2000-2013 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 package com.intellij.codeInspection.dataFlow;
  17
  18 import com.intellij.codeInspection.dataFlow.value.*;
  19 import com.intellij.openapi.progress.ProgressManager;
  20 import com.intellij.openapi.util.Condition;
  21 import com.intellij.openapi.util.UnorderedPair;
  22 import com.intellij.psi.JavaTokenType;
  23 import com.intellij.util.Function;
  24 import com.intellij.util.containers.ContainerUtil;
  25 import com.intellij.util.containers.MultiMap;
  26 import org.jetbrains.annotations.Nullable;
  27
  28 import java.util.*;
  29
  30 /**
  31  * @author peter
  32  */
  33 class StateMerger {
  34   private final Map<DfaMemoryStateImpl, LinkedHashSet<Fact>> myFacts = ContainerUtil.newIdentityHashMap();
  35   private final Map<DfaMemoryState, Map<DfaVariableValue, DfaMemoryStateImpl>> myCopyCache = ContainerUtil.newIdentityHashMap();
  36
  37   @Nullable
  38   List<DfaMemoryStateImpl> mergeByFacts(List<DfaMemoryStateImpl> states) {
  39     MultiMap<Fact, DfaMemoryStateImpl> statesByFact = MultiMap.createLinked();
  40     for (DfaMemoryStateImpl state : states) {
  41       ProgressManager.checkCanceled();
  42       for (Fact fact : getFacts(state)) {
  43         statesByFact.putValue(fact, state);
  44       }
  45     }
  46
  47     for (final Fact fact : statesByFact.keySet()) {
  48       if (statesByFact.get(fact).size() == states.size() || fact.myPositive) continue;
  49
  50       Collection<DfaMemoryStateImpl> statesWithNegations = statesByFact.get(fact.getPositiveCounterpart());
  51       if (statesWithNegations.isEmpty()) continue;
  52
  53       ProgressManager.checkCanceled();
  54
  55       MultiMap<Set<Fact>, DfaMemoryStateImpl> statesByUnrelatedFacts = MultiMap.createLinked();
  56       for (DfaMemoryStateImpl state : ContainerUtil.concat(statesByFact.get(fact), statesWithNegations)) {
  57         statesByUnrelatedFacts.putValue(getUnrelatedFacts(fact, state), state);
  58       }
  59
  60       Replacements replacements = new Replacements(states);
  61       for (Set<Fact> key : statesByUnrelatedFacts.keySet()) {
  62         final Collection<DfaMemoryStateImpl> group = statesByUnrelatedFacts.get(key);
  63         final Set<DfaVariableValue> unknowns = getAllUnknownVariables(group);
  64         replacements.stripAndMerge(group, new Function<DfaMemoryStateImpl, DfaMemoryStateImpl>() {
  65           @Override
  66           public DfaMemoryStateImpl fun(DfaMemoryStateImpl original) {
  67             DfaMemoryStateImpl copy = withUnknownVariables(original, unknowns);
  68             fact.removeFromState(copy);
  69             if (fact.myType == FactType.equality) {
  70               restoreOtherInequalities(fact, group, copy);
  71             }
  72             return copy;
  73           }
  74         });
  75       }
  76
  77       if (replacements.hasMerges()) return replacements.getMergeResult();
  78     }
  79     return null;
  80   }
  81
  82   private LinkedHashSet<Fact> getUnrelatedFacts(final Fact fact, DfaMemoryStateImpl state) {
  83     return new LinkedHashSet<Fact>(ContainerUtil.filter(getFacts(state), new Condition<Fact>() {
  84       @Override
  85       public boolean value(Fact another) {
  86         return !fact.invalidatesFact(another);
  87       }
  88     }));
  89   }
  90
  91   private void restoreOtherInequalities(Fact removedFact, Collection<DfaMemoryStateImpl> mergedGroup, DfaMemoryStateImpl state) {
  92     Set<DfaConstValue> inequalitiesToRestore = null;
  93     for (DfaMemoryStateImpl member : mergedGroup) {
  94       LinkedHashSet<Fact> memberFacts = getFacts(member);
  95       if (memberFacts.contains(removedFact)) {
  96         Set<DfaConstValue> otherInequalities = getOtherInequalities(removedFact, memberFacts, member);
  97         if (inequalitiesToRestore == null) {
  98           inequalitiesToRestore = otherInequalities;
  99         } else {
 100           inequalitiesToRestore.retainAll(otherInequalities);
 101         }
 102       }
 103     }
 104     if (inequalitiesToRestore != null) {
 105       DfaRelationValue.Factory relationFactory = state.getFactory().getRelationFactory();
 106       for (DfaConstValue toRestore : inequalitiesToRestore) {
 107         state.applyCondition(relationFactory.createRelation(removedFact.myVar, toRestore, JavaTokenType.EQEQ, true));
 108       }
 109     }
 110   }
 111
 112   private static Set<DfaConstValue> getOtherInequalities(Fact removedFact, LinkedHashSet<Fact> memberFacts, DfaMemoryStateImpl state) {
 113     Set<DfaConstValue> otherInequalities = ContainerUtil.newLinkedHashSet();
 114     Set<DfaValue> eqValues = ContainerUtil.newHashSet(state.getEquivalentValues((DfaValue)removedFact.myArg));
 115     for (Fact candidate : memberFacts) {
 116       if (candidate.myType == FactType.equality && !candidate.myPositive && candidate.myVar == removedFact.myVar &&
 117           !eqValues.contains((DfaValue)candidate.myArg) &&
 118           candidate.myArg instanceof DfaConstValue) {
 119         otherInequalities.add((DfaConstValue)candidate.myArg);
 120       }
 121     }
 122     return otherInequalities;
 123   }
 124
 125   private static Set<DfaVariableValue> getAllUnknownVariables(Collection<DfaMemoryStateImpl> complementary) {
 126     final Set<DfaVariableValue> toFlush = ContainerUtil.newLinkedHashSet();
 127     for (DfaMemoryStateImpl removedState : complementary) {
 128       toFlush.addAll(removedState.getUnknownVariables());
 129     }
 130     return toFlush;
 131   }
 132
 133   private static DfaMemoryStateImpl withUnknownVariables(DfaMemoryStateImpl original, Set<DfaVariableValue> toFlush) {
 134     DfaMemoryStateImpl copy = original.createCopy();
 135     for (DfaVariableValue value : toFlush) {
 136       copy.doFlush(value, true);
 137     }
 138     return copy;
 139   }
 140
 141   @Nullable
 142   public List<DfaMemoryStateImpl> mergeByUnknowns(List<DfaMemoryStateImpl> states) {
 143     MultiMap<Integer, DfaMemoryStateImpl> byHash = new MultiMap<Integer, DfaMemoryStateImpl>();
 144     for (DfaMemoryStateImpl state : states) {
 145       ProgressManager.checkCanceled();
 146       byHash.putValue(state.getPartialHashCode(false, true), state);
 147     }
 148
 149     Replacements replacements = new Replacements(states);
 150     for (Integer key : byHash.keySet()) {
 151       Collection<DfaMemoryStateImpl> similarStates = byHash.get(key);
 152       if (similarStates.size() < 2) continue;
 153
 154       for (final DfaMemoryStateImpl state1 : similarStates) {
 155         ProgressManager.checkCanceled();
 156         List<DfaMemoryStateImpl> complementary = ContainerUtil.filter(similarStates, new Condition<DfaMemoryStateImpl>() {
 157           @Override
 158           public boolean value(DfaMemoryStateImpl state2) {
 159             return state1.equalsByRelations(state2) && state1.equalsByVariableStates(state2);
 160           }
 161         });
 162         if (mergeUnknowns(replacements, complementary)) break;
 163       }
 164     }
 165
 166     return replacements.getMergeResult();
 167   }
 168
 169   @Nullable
 170   public List<DfaMemoryStateImpl> mergeByNullability(List<DfaMemoryStateImpl> states) {
 171     MultiMap<Integer, DfaMemoryStateImpl> byHash = new MultiMap<Integer, DfaMemoryStateImpl>();
 172     for (DfaMemoryStateImpl state : states) {
 173       ProgressManager.checkCanceled();
 174       byHash.putValue(state.getPartialHashCode(false, false), state);
 175     }
 176
 177     Replacements replacements = new Replacements(states);
 178     for (Integer key : byHash.keySet()) {
 179       Collection<DfaMemoryStateImpl> similarStates = byHash.get(key);
 180       if (similarStates.size() < 2) continue;
 181
 182       groupLoop:
 183       for (final DfaMemoryStateImpl state1 : similarStates) {
 184         ProgressManager.checkCanceled();
 185         for (final DfaVariableValue var : state1.getChangedVariables()) {
 186           if (state1.getVariableState(var).getNullability() != Nullness.NULLABLE) {
 187             continue;
 188           }
 189
 190           List<DfaMemoryStateImpl> complementary = ContainerUtil.filter(similarStates, new Condition<DfaMemoryStateImpl>() {
 191             @Override
 192             public boolean value(DfaMemoryStateImpl state2) {
 193               return state1.equalsByRelations(state2) &&
 194                      areEquivalentModuloVar(state1, state2, var) &&
 195                      areVarStatesEqualModuloNullability(state1, state2, var);
 196             }
 197           });
 198           if (mergeUnknowns(replacements, complementary)) break groupLoop;
 199         }
 200       }
 201     }
 202
 203     return replacements.getMergeResult();
 204   }
 205
 206   private static boolean mergeUnknowns(Replacements replacements, List<DfaMemoryStateImpl> complementary) {
 207     if (complementary.size() < 2) return false;
 208
 209     final Set<DfaVariableValue> toFlush = getAllUnknownVariables(complementary);
 210     if (toFlush.isEmpty()) return false;
 211
 212     return replacements.stripAndMerge(complementary, new Function<DfaMemoryStateImpl, DfaMemoryStateImpl>() {
 213       @Override
 214       public DfaMemoryStateImpl fun(DfaMemoryStateImpl original) {
 215         return withUnknownVariables(original, toFlush);
 216       }
 217     });
 218   }
 219
 220   private boolean areEquivalentModuloVar(DfaMemoryStateImpl state1, DfaMemoryStateImpl state2, DfaVariableValue var) {
 221     DfaMemoryStateImpl copy1 = copyWithoutVar(state1, var);
 222     DfaMemoryStateImpl copy2 = copyWithoutVar(state2, var);
 223     return copy2.equalsByRelations(copy1) && copy2.equalsByVariableStates(copy1);
 224   }
 225
 226   private DfaMemoryStateImpl copyWithoutVar(DfaMemoryStateImpl state, DfaVariableValue var) {
 227     Map<DfaVariableValue, DfaMemoryStateImpl> map = myCopyCache.get(state);
 228     if (map == null) {
 229       myCopyCache.put(state, map = ContainerUtil.newIdentityHashMap());
 230     }
 231     DfaMemoryStateImpl copy = map.get(var);
 232     if (copy == null) {
 233       copy = state.createCopy();
 234       copy.flushVariable(var);
 235       map.put(var, copy);
 236     }
 237     return copy;
 238   }
 239
 240   private static boolean areVarStatesEqualModuloNullability(DfaMemoryStateImpl state1, DfaMemoryStateImpl state2, DfaVariableValue var) {
 241     return state1.getVariableState(var).withNullability(Nullness.UNKNOWN).equals(state2.getVariableState(var).withNullability(Nullness.UNKNOWN));
 242   }
 243
 244   private LinkedHashSet<Fact> getFacts(DfaMemoryStateImpl state) {
 245     LinkedHashSet<Fact> result = myFacts.get(state);
 246     if (result != null) {
 247       return result;
 248     }
 249
 250     result = ContainerUtil.newLinkedHashSet();
 251     for (EqClass eqClass : state.getNonTrivialEqClasses()) {
 252       DfaValue constant = eqClass.findConstant(true);
 253       List<DfaVariableValue> vars = eqClass.getVariables(false);
 254       for (DfaVariableValue var : vars) {
 255         if (constant != null) {
 256           result.add(Fact.createEqualityFact(var, constant, true));
 257         }
 258         for (DfaVariableValue eqVar : vars) {
 259           if (var != eqVar) {
 260             result.add(Fact.createEqualityFact(var, eqVar, true));
 261           }
 262         }
 263       }
 264     }
 265
 266     for (UnorderedPair<EqClass> classPair : state.getDistinctClassPairs()) {
 267       List<DfaVariableValue> vars1 = classPair.first.getVariables(false);
 268       List<DfaVariableValue> vars2 = classPair.second.getVariables(false);
 269
 270       LinkedHashSet<DfaValue> firstSet = new LinkedHashSet<DfaValue>(vars1);
 271       ContainerUtil.addIfNotNull(firstSet, classPair.first.findConstant(true));
 272
 273       LinkedHashSet<DfaValue> secondSet = new LinkedHashSet<DfaValue>(vars2);
 274       ContainerUtil.addIfNotNull(secondSet, classPair.second.findConstant(true));
 275
 276       for (DfaVariableValue var : vars1) {
 277         for (DfaValue value : secondSet) {
 278           result.add(new Fact(FactType.equality, var, false, value));
 279         }
 280       }
 281       for (DfaVariableValue var : vars2) {
 282         for (DfaValue value : firstSet) {
 283           result.add(new Fact(FactType.equality, var, false, value));
 284         }
 285       }
 286     }
 287
 288     Map<DfaVariableValue, DfaVariableState> states = state.getVariableStates();
 289     for (DfaVariableValue var : states.keySet()) {
 290       DfaVariableState variableState = states.get(var);
 291       for (DfaPsiType type : variableState.getInstanceofValues()) {
 292         result.add(new Fact(FactType.instanceOf, var, true, type));
 293       }
 294       for (DfaPsiType type : variableState.getNotInstanceofValues()) {
 295         result.add(new Fact(FactType.instanceOf, var, false, type));
 296       }
 297     }
 298
 299     myFacts.put(state, result);
 300     return result;
 301   }
 302
 303   private enum FactType { equality, instanceOf }
 304
 305   private static class Fact {
 306     final FactType myType;
 307     final DfaVariableValue myVar;
 308     final boolean myPositive;
 309     final Object myArg; // DfaValue for equality fact, DfaPsiType for instanceOf fact
 310
 311     private Fact(FactType type, DfaVariableValue var, boolean positive, Object arg) {
 312       myType = type;
 313       myVar = var;
 314       myPositive = positive;
 315       myArg = arg;
 316     }
 317
 318     @Override
 319     public boolean equals(Object o) {
 320       if (this == o) return true;
 321       if (!(o instanceof Fact)) return false;
 322
 323       Fact fact = (Fact)o;
 324
 325       if (myPositive != fact.myPositive) return false;
 326       if (!myArg.equals(fact.myArg)) return false;
 327       if (myType != fact.myType) return false;
 328       if (!myVar.equals(fact.myVar)) return false;
 329
 330       return true;
 331     }
 332
 333     @Override
 334     public int hashCode() {
 335       int result = myType.hashCode();
 336       result = 31 * result + myVar.hashCode();
 337       result = 31 * result + (myPositive ? 1 : 0);
 338       result = 31 * result + myArg.hashCode();
 339       return result;
 340     }
 341
 342     @Override
 343     public String toString() {
 344       return myVar + " " + (myPositive ? "" : "!") + myType + " " + myArg;
 345     }
 346
 347     static Fact createEqualityFact(DfaVariableValue var, DfaValue val, boolean equal) {
 348       if (val instanceof DfaVariableValue && val.getID() < var.getID()) {
 349         return new Fact(FactType.equality, (DfaVariableValue)val, equal, var);
 350       }
 351       return new Fact(FactType.equality, var, equal, val);
 352     }
 353
 354     Fact getPositiveCounterpart() {
 355       return new Fact(myType, myVar, true, myArg);
 356     }
 357
 358     boolean invalidatesFact(Fact another) {
 359       if (another.myType != myType) return false;
 360       if (myType == FactType.equality) {
 361         return myVar == another.myVar || myVar == another.myArg;
 362       }
 363       return myVar == another.myVar && myArg == another.myArg;
 364     }
 365
 366     void removeFromState(DfaMemoryStateImpl state) {
 367       DfaVariableState varState = state.getVariableState(myVar);
 368       if (myType == FactType.equality) {
 369         state.flushVariable(myVar);
 370         state.setVariableState(myVar, varState);
 371       } else {
 372         state.setVariableState(myVar, varState.withoutType((DfaPsiType)myArg));
 373       }
 374     }
 375   }
 376
 377   private static class Replacements {
 378     private final List<DfaMemoryStateImpl> myAllStates;
 379     private final Set<DfaMemoryStateImpl> myRemovedStates = ContainerUtil.newIdentityTroveSet();
 380     private final List<DfaMemoryStateImpl> myMerged = ContainerUtil.newArrayList();
 381
 382     Replacements(List<DfaMemoryStateImpl> allStates) {
 383       myAllStates = allStates;
 384     }
 385
 386     boolean hasMerges() { return !myMerged.isEmpty(); }
 387
 388     @Nullable
 389     List<DfaMemoryStateImpl> getMergeResult() {
 390       if (hasMerges()) {
 391         List<DfaMemoryStateImpl> result = ContainerUtil.newArrayList(myMerged);
 392         for (DfaMemoryStateImpl state : myAllStates) {
 393           if (!myRemovedStates.contains(state)) {
 394             result.add(state);
 395           }
 396         }
 397         return result;
 398       }
 399       return null;
 400     }
 401
 402     boolean stripAndMerge(Collection<DfaMemoryStateImpl> group,
 403                                Function<DfaMemoryStateImpl, DfaMemoryStateImpl> stripper) {
 404       if (group.size() <= 1) return false;
 405
 406       boolean hasMerges = false;
 407       MultiMap<DfaMemoryStateImpl, DfaMemoryStateImpl> strippedToOriginals = MultiMap.create();
 408       for (DfaMemoryStateImpl original : group) {
 409         strippedToOriginals.putValue(stripper.fun(original), original);
 410       }
 411       for (Map.Entry<DfaMemoryStateImpl, Collection<DfaMemoryStateImpl>> entry : strippedToOriginals.entrySet()) {
 412         Collection<DfaMemoryStateImpl> merged = entry.getValue();
 413         if (merged.size() > 1) {
 414           myRemovedStates.addAll(merged);
 415           myMerged.add(entry.getKey());
 416           hasMerges = true;
 417         }
 418       }
 419       return hasMerges;
 420     }
 421   }
 422
 423 }