plugins/groovy/groovy-psi/src/org/jetbrains/plugins/groovy/lang/psi/dataFlow/types/TypeInferenceHelper.java - platform/tools/idea - Git at Google

 /*
  * Copyright 2000-2014 JetBrains s.r.o.
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
  * You may obtain a copy of the License at
  *
  * http://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS,
  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */
 package org.jetbrains.plugins.groovy.lang.psi.dataFlow.types;

 import com.intellij.openapi.diagnostic.Logger;
 import com.intellij.openapi.util.Computable;
 import com.intellij.openapi.util.Condition;
 import com.intellij.openapi.util.NullableComputable;
 import com.intellij.openapi.util.Pair;
 import com.intellij.psi.PsiElement;
 import com.intellij.psi.PsiRecursiveElementWalkingVisitor;
 import com.intellij.psi.PsiType;
 import com.intellij.psi.util.*;
 import com.intellij.util.containers.ConcurrentHashSet;
 import com.intellij.util.containers.ContainerUtil;
 import org.jetbrains.annotations.NotNull;
 import org.jetbrains.annotations.Nullable;
 import org.jetbrains.plugins.groovy.codeInspection.utils.ControlFlowUtils;
 import org.jetbrains.plugins.groovy.lang.lexer.TokenSets;
 import org.jetbrains.plugins.groovy.lang.psi.GrControlFlowOwner;
 import org.jetbrains.plugins.groovy.lang.psi.api.auxiliary.GrListOrMap;
 import org.jetbrains.plugins.groovy.lang.psi.api.statements.GrVariable;
 import org.jetbrains.plugins.groovy.lang.psi.api.statements.expressions.*;
 import org.jetbrains.plugins.groovy.lang.psi.api.statements.expressions.path.GrIndexProperty;
 import org.jetbrains.plugins.groovy.lang.psi.controlFlow.InstanceOfInstruction;
 import org.jetbrains.plugins.groovy.lang.psi.controlFlow.Instruction;
 import org.jetbrains.plugins.groovy.lang.psi.controlFlow.MixinTypeInstruction;
 import org.jetbrains.plugins.groovy.lang.psi.controlFlow.ReadWriteVariableInstruction;
 import org.jetbrains.plugins.groovy.lang.psi.controlFlow.impl.ArgumentInstruction;
 import org.jetbrains.plugins.groovy.lang.psi.dataFlow.DFAEngine;
 import org.jetbrains.plugins.groovy.lang.psi.dataFlow.DFAType;
 import org.jetbrains.plugins.groovy.lang.psi.dataFlow.DfaInstance;
 import org.jetbrains.plugins.groovy.lang.psi.dataFlow.reachingDefs.DefinitionMap;
 import org.jetbrains.plugins.groovy.lang.psi.dataFlow.reachingDefs.ReachingDefinitionsDfaInstance;
 import org.jetbrains.plugins.groovy.lang.psi.dataFlow.reachingDefs.ReachingDefinitionsSemilattice;
 import org.jetbrains.plugins.groovy.lang.psi.impl.GrTupleType;
 import org.jetbrains.plugins.groovy.lang.psi.impl.InferenceContext;
 import org.jetbrains.plugins.groovy.lang.psi.impl.statements.expressions.TypesUtil;

 import java.util.*;
 import java.util.concurrent.atomic.AtomicReference;

 /**
  * @author ven
  */
 @SuppressWarnings("UtilityClassWithoutPrivateConstructor")
 public class TypeInferenceHelper {
   private static final Logger LOG = Logger.getInstance(TypeInferenceHelper.class);
   private static final ThreadLocal<InferenceContext> ourInferenceContext = new ThreadLocal<InferenceContext>();

   private static <T> T doInference(@NotNull Map<String, PsiType> bindings, @NotNull Computable<T> computation) {
     InferenceContext old = ourInferenceContext.get();
     ourInferenceContext.set(new InferenceContext.PartialContext(bindings));
     try {
       return computation.compute();
     }
     finally {
       ourInferenceContext.set(old);
     }
   }

   public static InferenceContext getCurrentContext() {
     InferenceContext context = ourInferenceContext.get();
     return context != null ? context : InferenceContext.TOP_CONTEXT;
   }

   @Nullable
   public static PsiType getInferredType(@NotNull final GrReferenceExpression refExpr) {
     final GrControlFlowOwner scope = ControlFlowUtils.findControlFlowOwner(refExpr);
     if (scope == null) return null;

     final String referenceName = refExpr.getReferenceName();
     if (referenceName == null) return null;

     final ReadWriteVariableInstruction rwInstruction = ControlFlowUtils.findRWInstruction(refExpr, scope.getControlFlow());
     if (rwInstruction == null) return null;

     return getInferenceCache(scope).getInferredType(referenceName, rwInstruction);
   }

   @Nullable
   public static PsiType getInferredType(@NotNull PsiElement place, @NotNull String variableName) {
     final GrControlFlowOwner scope = ControlFlowUtils.findControlFlowOwner(place);
     if (scope == null) return null;

     final Instruction nearest = ControlFlowUtils.findNearestInstruction(place, scope.getControlFlow());
     if (nearest == null) return null;
     return getInferenceCache(scope).getInferredType(variableName, nearest);
   }

   @NotNull
   private static InferenceCache getInferenceCache(@NotNull final GrControlFlowOwner scope) {
     return CachedValuesManager.getCachedValue(scope, new CachedValueProvider<InferenceCache>() {
       @Nullable
       @Override
       public Result<InferenceCache> compute() {
         return Result.create(new InferenceCache(scope), PsiModificationTracker.MODIFICATION_COUNT);
       }
     });
   }

   public static boolean isTooComplexTooAnalyze(@NotNull GrControlFlowOwner scope) {
     return getDefUseMaps(scope) == null;
   }

   @Nullable
   private static DFAType getInferredType(@NotNull String varName, @NotNull Instruction instruction, @NotNull Instruction[] flow, @NotNull GrControlFlowOwner scope, Set<MixinTypeInstruction> trace) {
     final Pair<ReachingDefinitionsDfaInstance, List<DefinitionMap>> pair = getDefUseMaps(scope);
     if (pair == null) return null;

     final int varIndex = pair.first.getVarIndex(varName);
     final DefinitionMap allDefs = pair.second.get(instruction.num());
     final int[] varDefs = allDefs.getDefinitions(varIndex);
     if (varDefs == null) return null;

     DFAType result = null;
     for (int defIndex : varDefs) {
       DFAType defType = getDefinitionType(flow[defIndex], flow, scope, trace);

       if (defType != null) {
         defType = defType.negate(instruction);
       }

       if (defType != null) {
         result = result == null ? defType : DFAType.create(defType, result, scope.getManager());
       }
     }
     return result;
   }

   @Nullable
   private static Pair<ReachingDefinitionsDfaInstance, List<DefinitionMap>> getDefUseMaps(@NotNull final GrControlFlowOwner scope) {
     return CachedValuesManager.getCachedValue(scope, new CachedValueProvider<Pair<ReachingDefinitionsDfaInstance, List<DefinitionMap>>>() {
       @Override
       public Result<Pair<ReachingDefinitionsDfaInstance, List<DefinitionMap>>> compute() {
         final Instruction[] flow = scope.getControlFlow();
         final ReachingDefinitionsDfaInstance dfaInstance = new ReachingDefinitionsDfaInstance(flow) {
           @Override
           public void fun(DefinitionMap m, Instruction instruction) {
             if (instruction instanceof InstanceOfInstruction) {
               final InstanceOfInstruction instanceOfInstruction = (InstanceOfInstruction)instruction;
               ReadWriteVariableInstruction i = instanceOfInstruction.getInstructionToMixin(flow);
               if (i != null) {
                 int varIndex = getVarIndex(i.getVariableName());
                 if (varIndex >= 0) {
                   m.registerDef(instruction, varIndex);
                 }
               }
             }
             else if (instruction instanceof ArgumentInstruction) {
               String variableName = ((ArgumentInstruction)instruction).getVariableName();
               if (variableName != null) {
                 m.registerDef(instruction, getVarIndex(variableName));
               }
             }
             else {
               super.fun(m, instruction);
             }
           }
         };
         final ReachingDefinitionsSemilattice lattice = new ReachingDefinitionsSemilattice();
         final DFAEngine<DefinitionMap> engine = new DFAEngine<DefinitionMap>(flow, dfaInstance, lattice);
         final List<DefinitionMap> dfaResult = engine.performDFAWithTimeout();
         Pair<ReachingDefinitionsDfaInstance, List<DefinitionMap>> result = dfaResult == null ? null : Pair.create(dfaInstance, dfaResult);
         return Result.create(result, PsiModificationTracker.MODIFICATION_COUNT);
       }
     });
   }

   @Nullable
   private static DFAType getDefinitionType(Instruction instruction, Instruction[] flow, GrControlFlowOwner scope, Set<MixinTypeInstruction> trace) {
     if (instruction instanceof ReadWriteVariableInstruction && ((ReadWriteVariableInstruction) instruction).isWrite()) {
       final PsiElement element = instruction.getElement();
       if (element != null) {
         return DFAType.create(TypesUtil.boxPrimitiveType(getInitializerType(element), scope.getManager(), scope.getResolveScope()));
       }
     }
     if (instruction instanceof MixinTypeInstruction) {
       return mixinType((MixinTypeInstruction)instruction, flow, scope, trace);
     }
     return null;
   }

   @Nullable
   private static DFAType mixinType(final MixinTypeInstruction instruction, final Instruction[] flow, final GrControlFlowOwner scope, Set<MixinTypeInstruction> trace) {
     if (!trace.add(instruction)) {
       return null;
     }

     String varName = instruction.getVariableName();
     if (varName == null) {
       return null;
     }
     ReadWriteVariableInstruction originalInstr = instruction.getInstructionToMixin(flow);
     if (originalInstr == null) {
       LOG.error(scope.getContainingFile().getName() + ":" + scope.getText());
     }

     DFAType original = getInferredType(varName, originalInstr, flow, scope, trace);
     final PsiType mixin = instruction.inferMixinType();
     if (mixin == null) {
       return original;
     }
     if (original == null) {
       original = DFAType.create(null);
     }
     original.addMixin(mixin, instruction.getConditionInstruction());
     trace.remove(instruction);
     return original;
   }


   @Nullable
   public static PsiType getInitializerType(final PsiElement element) {
     if (element instanceof GrReferenceExpression && ((GrReferenceExpression) element).getQualifierExpression() == null) {
       return getInitializerTypeFor(element);
     }

     if (element instanceof GrVariable) {
       return ((GrVariable)element).getTypeGroovy();
     }

     return null;
   }

   @Nullable
   public static PsiType getInitializerTypeFor(PsiElement element) {
     final PsiElement parent = element.getParent();
     if (parent instanceof GrAssignmentExpression) {
       if (element instanceof GrIndexProperty) {
         final GrExpression rvalue = ((GrAssignmentExpression)parent).getRValue();
         return rvalue != null ? rvalue.getType() : null; //don't try to infer assignment type in case of index property because of infinite recursion (example: a[2]+=4)
       }
       return ((GrAssignmentExpression)parent).getType();
     }

     if (parent instanceof GrTupleExpression) {
       GrTupleExpression list = (GrTupleExpression)parent;
       if (list.getParent() instanceof GrAssignmentExpression) { // multiple assignment
         final GrExpression rValue = ((GrAssignmentExpression) list.getParent()).getRValue();
         int idx = list.indexOf(element);
         if (idx >= 0 && rValue != null) {
           PsiType rType = rValue.getType();
           if (rType instanceof GrTupleType) {
             PsiType[] componentTypes = ((GrTupleType) rType).getComponentTypes();
             if (idx < componentTypes.length) return componentTypes[idx];
             return null;
           }
           return PsiUtil.extractIterableTypeParameter(rType, false);
         }
       }
     }
     if (parent instanceof GrUnaryExpression &&
         TokenSets.POSTFIX_UNARY_OP_SET.contains(((GrUnaryExpression)parent).getOperationTokenType())) {
       return ((GrUnaryExpression)parent).getType();
     }

     return null;
   }

   @Nullable
   public static GrExpression getInitializerFor(GrExpression lValue) {
     final PsiElement parent = lValue.getParent();
     if (parent instanceof GrAssignmentExpression) return ((GrAssignmentExpression)parent).getRValue();
     if (parent instanceof GrTupleExpression) {
       final int i = ((GrTupleExpression)parent).indexOf(lValue);
       final PsiElement pparent = parent.getParent();
       org.jetbrains.plugins.groovy.lang.psi.util.PsiUtil.LOG.assertTrue(pparent instanceof GrAssignmentExpression);

       final GrExpression rValue = ((GrAssignmentExpression)pparent).getRValue();
       if (rValue instanceof GrListOrMap && !((GrListOrMap)rValue).isMap()) {
         final GrExpression[] initializers = ((GrListOrMap)rValue).getInitializers();
         if (initializers.length < i) return initializers[i];
       }
     }

     return null;
   }

   static class TypeDfaInstance implements DfaInstance<TypeDfaState> {
     private final GrControlFlowOwner myScope;
     private final Instruction[] myFlow;
     private final Set<Instruction> myInteresting;
     private final InferenceCache myCache;

     TypeDfaInstance(@NotNull GrControlFlowOwner scope, @NotNull Instruction[] flow, @NotNull Set<Instruction> interesting, @NotNull InferenceCache cache) {
       myScope = scope;
       myFlow = flow;
       myInteresting = interesting;
       myCache = cache;
     }

     @Override
     public void fun(final TypeDfaState state, final Instruction instruction) {
       if (instruction instanceof ReadWriteVariableInstruction) {
         handleVariableWrite(state, (ReadWriteVariableInstruction)instruction);
       }
       else if (instruction instanceof MixinTypeInstruction) {
         handleMixin(state, (MixinTypeInstruction)instruction);
       }
     }

     private void handleMixin(@NotNull final TypeDfaState state, @NotNull final MixinTypeInstruction instruction) {
       final String varName = instruction.getVariableName();
       if (varName == null) return;

       updateVariableType(state, instruction, varName, new NullableComputable<DFAType>() {
         @Override
         public DFAType compute() {
           ReadWriteVariableInstruction originalInstr = instruction.getInstructionToMixin(myFlow);
           assert originalInstr != null && !originalInstr.isWrite();

           DFAType original = state.getVariableType(varName);
           if (original == null) {
             original = DFAType.create(null);
           }
           original = original.negate(originalInstr);
           original.addMixin(instruction.inferMixinType(), instruction.getConditionInstruction());
           return original;
         }
       });
     }

     private void handleVariableWrite(TypeDfaState state, ReadWriteVariableInstruction instruction) {
       final PsiElement element = instruction.getElement();
       if (element != null && instruction.isWrite()) {
         updateVariableType(state, instruction, instruction.getVariableName(), new Computable<DFAType>() {
           @Override
           public DFAType compute() {
             return DFAType.create(TypesUtil.boxPrimitiveType(getInitializerType(element), myScope.getManager(), myScope.getResolveScope()));
           }
         });
       }
     }

     private void updateVariableType(@NotNull TypeDfaState state, @NotNull Instruction instruction, @NotNull String variableName, @NotNull Computable<DFAType> computation) {
       if (!myInteresting.contains(instruction)) {
         state.removeBinding(variableName);
         return;
       }

       DFAType type = myCache.getCachedInferredType(variableName, instruction);
       if (type == null) {
         type = doInference(state.getBindings(instruction), computation);
       }
       state.putType(variableName, type);
     }

     @Override
     @NotNull
     public TypeDfaState initial() {
       return new TypeDfaState();
     }

     @Override
     public boolean isForward() {
       return true;
     }

   }

   private static class InferenceCache {
     final GrControlFlowOwner scope;
     final Instruction[] flow;
     final AtomicReference<List<TypeDfaState>> varTypes;
     final ConcurrentHashSet<Instruction> tooComplex = new ConcurrentHashSet<Instruction>();

     InferenceCache(final GrControlFlowOwner scope) {
       this.scope = scope;
       this.flow = scope.getControlFlow();
       List<TypeDfaState> noTypes = new ArrayList<TypeDfaState>();
       //noinspection ForLoopReplaceableByForEach
       for (int i = 0; i < flow.length; i++) {
         noTypes.add(new TypeDfaState());
       }
       varTypes = new AtomicReference<List<TypeDfaState>>(noTypes);
     }

     @Nullable
     private PsiType getInferredType(@NotNull String variableName, @NotNull Instruction instruction) {
       if (tooComplex.contains(instruction)) return null;

       TypeDfaState cache = varTypes.get().get(instruction.num());
       if (!cache.containsVariable(variableName)) {
         Pair<ReachingDefinitionsDfaInstance, List<DefinitionMap>> defUse = getDefUseMaps(scope);
         if (defUse == null) {
           tooComplex.add(instruction);
           return null;
         }

         Set<Instruction> interesting = collectRequiredInstructions(instruction, variableName, defUse);
         List<TypeDfaState> dfaResult = performTypeDfa(scope, flow, interesting);
         if (dfaResult == null) {
           tooComplex.addAll(interesting);
         } else {
           cacheDfaResult(dfaResult);
         }
       }
       DFAType dfaType = getCachedInferredType(variableName, instruction);
       return dfaType == null ? null : dfaType.getResultType();
     }

     @Nullable
     private List<TypeDfaState> performTypeDfa(@NotNull GrControlFlowOwner owner, @NotNull Instruction[] flow, @NotNull Set<Instruction> interesting) {
       final TypeDfaInstance dfaInstance = new TypeDfaInstance(owner, flow, interesting, this);
       final TypesSemilattice semilattice = new TypesSemilattice(owner.getManager());
       return new DFAEngine<TypeDfaState>(flow, dfaInstance, semilattice).performDFAWithTimeout();
     }

     @Nullable
     DFAType getCachedInferredType(@NotNull String variableName, @NotNull Instruction instruction) {
       DFAType dfaType = varTypes.get().get(instruction.num()).getVariableType(variableName);
       return dfaType == null ? null : dfaType.negate(instruction);
     }

     private Set<Instruction> collectRequiredInstructions(@NotNull Instruction instruction,
                                                          @NotNull String variableName,
                                                          @NotNull Pair<ReachingDefinitionsDfaInstance, List<DefinitionMap>> defUse) {
       Set<Instruction> interesting = ContainerUtil.newHashSet(instruction);
       LinkedList<Pair<Instruction,String>> queue = ContainerUtil.newLinkedList();
       queue.add(Pair.create(instruction, variableName));
       while (!queue.isEmpty()) {
         Pair<Instruction, String> pair = queue.removeFirst();
         for (Pair<Instruction, String> dep : findDependencies(defUse, pair.first, pair.second)) {
           if (interesting.add(dep.first)) {
             queue.addLast(dep);
           }
         }
       }

       return interesting;
     }

     @NotNull
     private Set<Pair<Instruction,String>> findDependencies(@NotNull Pair<ReachingDefinitionsDfaInstance, List<DefinitionMap>> defUse,
                                                            @NotNull Instruction insn,
                                                            @NotNull String varName) {
       DefinitionMap definitionMap = defUse.second.get(insn.num());
       int varIndex = defUse.first.getVarIndex(varName);
       int[] definitions = definitionMap.getDefinitions(varIndex);
       if (definitions == null) return Collections.emptySet();

       LinkedHashSet<Pair<Instruction, String>> pairs = ContainerUtil.newLinkedHashSet();
       for (int defIndex : definitions) {
         Instruction write = flow[defIndex];
         pairs.add(Pair.create(write, varName));
         PsiElement statement = findDependencyScope(write.getElement());
         if (statement != null) {
           pairs.addAll(findAllInstructionsInside(statement));
         }
       }
       return pairs;
     }

     @NotNull
     private List<Pair<Instruction, String>> findAllInstructionsInside(@NotNull PsiElement scope) {
       final List<Pair<Instruction, String>> result = ContainerUtil.newArrayList();
       scope.accept(new PsiRecursiveElementWalkingVisitor() {
         @Override
         public void visitElement(PsiElement element) {
           if (element instanceof GrReferenceExpression && !((GrReferenceExpression)element).isQualified()) {
             String varName = ((GrReferenceExpression)element).getReferenceName();
             if (varName != null) {
               for (Instruction dependency : ControlFlowUtils.findAllInstructions(element, flow)) {
                 result.add(Pair.create(dependency, varName));
               }
             }
           }
           super.visitElement(element);
         }
       });
       return result;
     }

     @Nullable
     private static PsiElement findDependencyScope(@Nullable PsiElement element) {
       return PsiTreeUtil.findFirstParent(element, new Condition<PsiElement>() {
         @Override
         public boolean value(PsiElement element) {
           return org.jetbrains.plugins.groovy.lang.psi.util.PsiUtil.isExpressionStatement(element) ||
                  !(element.getParent() instanceof GrExpression);
         }
       });
     }

     private void cacheDfaResult(@NotNull List<TypeDfaState> dfaResult) {
       while (true) {
         List<TypeDfaState> oldTypes = varTypes.get();
         if (varTypes.compareAndSet(oldTypes, addDfaResult(dfaResult, oldTypes))) {
           return;
         }
       }
     }

     @NotNull
     private static List<TypeDfaState> addDfaResult(@NotNull List<TypeDfaState> dfaResult, @NotNull List<TypeDfaState> oldTypes) {
       List<TypeDfaState> newTypes = new ArrayList<TypeDfaState>(oldTypes);
       for (int i = 0; i < dfaResult.size(); i++) {
         newTypes.set(i, newTypes.get(i).mergeWith(dfaResult.get(i)));
       }
       return newTypes;
     }
   }

 }
	/*
	* Copyright 2000-2014 JetBrains s.r.o.
	*
	* Licensed under the Apache License, Version 2.0 (the "License");
	* you may not use this file except in compliance with the License.
	* You may obtain a copy of the License at
	*
	* http://www.apache.org/licenses/LICENSE-2.0
	*
	* Unless required by applicable law or agreed to in writing, software
	* distributed under the License is distributed on an "AS IS" BASIS,
	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	* See the License for the specific language governing permissions and
	* limitations under the License.
	*/
	package org.jetbrains.plugins.groovy.lang.psi.dataFlow.types;

	import com.intellij.openapi.diagnostic.Logger;
	import com.intellij.openapi.util.Computable;
	import com.intellij.openapi.util.Condition;
	import com.intellij.openapi.util.NullableComputable;
	import com.intellij.openapi.util.Pair;
	import com.intellij.psi.PsiElement;
	import com.intellij.psi.PsiRecursiveElementWalkingVisitor;
	import com.intellij.psi.PsiType;
	import com.intellij.psi.util.*;
	import com.intellij.util.containers.ConcurrentHashSet;
	import com.intellij.util.containers.ContainerUtil;
	import org.jetbrains.annotations.NotNull;
	import org.jetbrains.annotations.Nullable;
	import org.jetbrains.plugins.groovy.codeInspection.utils.ControlFlowUtils;
	import org.jetbrains.plugins.groovy.lang.lexer.TokenSets;
	import org.jetbrains.plugins.groovy.lang.psi.GrControlFlowOwner;
	import org.jetbrains.plugins.groovy.lang.psi.api.auxiliary.GrListOrMap;
	import org.jetbrains.plugins.groovy.lang.psi.api.statements.GrVariable;
	import org.jetbrains.plugins.groovy.lang.psi.api.statements.expressions.*;
	import org.jetbrains.plugins.groovy.lang.psi.api.statements.expressions.path.GrIndexProperty;
	import org.jetbrains.plugins.groovy.lang.psi.controlFlow.InstanceOfInstruction;
	import org.jetbrains.plugins.groovy.lang.psi.controlFlow.Instruction;
	import org.jetbrains.plugins.groovy.lang.psi.controlFlow.MixinTypeInstruction;
	import org.jetbrains.plugins.groovy.lang.psi.controlFlow.ReadWriteVariableInstruction;
	import org.jetbrains.plugins.groovy.lang.psi.controlFlow.impl.ArgumentInstruction;
	import org.jetbrains.plugins.groovy.lang.psi.dataFlow.DFAEngine;
	import org.jetbrains.plugins.groovy.lang.psi.dataFlow.DFAType;
	import org.jetbrains.plugins.groovy.lang.psi.dataFlow.DfaInstance;
	import org.jetbrains.plugins.groovy.lang.psi.dataFlow.reachingDefs.DefinitionMap;
	import org.jetbrains.plugins.groovy.lang.psi.dataFlow.reachingDefs.ReachingDefinitionsDfaInstance;
	import org.jetbrains.plugins.groovy.lang.psi.dataFlow.reachingDefs.ReachingDefinitionsSemilattice;
	import org.jetbrains.plugins.groovy.lang.psi.impl.GrTupleType;
	import org.jetbrains.plugins.groovy.lang.psi.impl.InferenceContext;
	import org.jetbrains.plugins.groovy.lang.psi.impl.statements.expressions.TypesUtil;

	import java.util.*;
	import java.util.concurrent.atomic.AtomicReference;

	/**
	* @author ven
	*/
	@SuppressWarnings("UtilityClassWithoutPrivateConstructor")
	public class TypeInferenceHelper {
	private static final Logger LOG = Logger.getInstance(TypeInferenceHelper.class);
	private static final ThreadLocal<InferenceContext> ourInferenceContext = new ThreadLocal<InferenceContext>();

	private static <T> T doInference(@NotNull Map<String, PsiType> bindings, @NotNull Computable<T> computation) {
	InferenceContext old = ourInferenceContext.get();
	ourInferenceContext.set(new InferenceContext.PartialContext(bindings));
	try {
	return computation.compute();
	}
	finally {
	ourInferenceContext.set(old);
	}
	}

	public static InferenceContext getCurrentContext() {
	InferenceContext context = ourInferenceContext.get();
	return context != null ? context : InferenceContext.TOP_CONTEXT;
	}

	@Nullable
	public static PsiType getInferredType(@NotNull final GrReferenceExpression refExpr) {
	final GrControlFlowOwner scope = ControlFlowUtils.findControlFlowOwner(refExpr);
	if (scope == null) return null;

	final String referenceName = refExpr.getReferenceName();
	if (referenceName == null) return null;

	final ReadWriteVariableInstruction rwInstruction = ControlFlowUtils.findRWInstruction(refExpr, scope.getControlFlow());
	if (rwInstruction == null) return null;

	return getInferenceCache(scope).getInferredType(referenceName, rwInstruction);
	}

	@Nullable
	public static PsiType getInferredType(@NotNull PsiElement place, @NotNull String variableName) {
	final GrControlFlowOwner scope = ControlFlowUtils.findControlFlowOwner(place);
	if (scope == null) return null;

	final Instruction nearest = ControlFlowUtils.findNearestInstruction(place, scope.getControlFlow());
	if (nearest == null) return null;
	return getInferenceCache(scope).getInferredType(variableName, nearest);
	}

	@NotNull
	private static InferenceCache getInferenceCache(@NotNull final GrControlFlowOwner scope) {
	return CachedValuesManager.getCachedValue(scope, new CachedValueProvider<InferenceCache>() {
	@Nullable
	@Override
	public Result<InferenceCache> compute() {
	return Result.create(new InferenceCache(scope), PsiModificationTracker.MODIFICATION_COUNT);
	}
	});
	}

	public static boolean isTooComplexTooAnalyze(@NotNull GrControlFlowOwner scope) {
	return getDefUseMaps(scope) == null;
	}

	@Nullable
	private static DFAType getInferredType(@NotNull String varName, @NotNull Instruction instruction, @NotNull Instruction[] flow, @NotNull GrControlFlowOwner scope, Set<MixinTypeInstruction> trace) {
	final Pair<ReachingDefinitionsDfaInstance, List<DefinitionMap>> pair = getDefUseMaps(scope);
	if (pair == null) return null;

	final int varIndex = pair.first.getVarIndex(varName);
	final DefinitionMap allDefs = pair.second.get(instruction.num());
	final int[] varDefs = allDefs.getDefinitions(varIndex);
	if (varDefs == null) return null;

	DFAType result = null;
	for (int defIndex : varDefs) {
	DFAType defType = getDefinitionType(flow[defIndex], flow, scope, trace);

	if (defType != null) {
	defType = defType.negate(instruction);
	}

	if (defType != null) {
	result = result == null ? defType : DFAType.create(defType, result, scope.getManager());
	}
	}
	return result;
	}

	@Nullable
	private static Pair<ReachingDefinitionsDfaInstance, List<DefinitionMap>> getDefUseMaps(@NotNull final GrControlFlowOwner scope) {
	return CachedValuesManager.getCachedValue(scope, new CachedValueProvider<Pair<ReachingDefinitionsDfaInstance, List<DefinitionMap>>>() {
	@Override
	public Result<Pair<ReachingDefinitionsDfaInstance, List<DefinitionMap>>> compute() {
	final Instruction[] flow = scope.getControlFlow();
	final ReachingDefinitionsDfaInstance dfaInstance = new ReachingDefinitionsDfaInstance(flow) {
	@Override
	public void fun(DefinitionMap m, Instruction instruction) {
	if (instruction instanceof InstanceOfInstruction) {
	final InstanceOfInstruction instanceOfInstruction = (InstanceOfInstruction)instruction;
	ReadWriteVariableInstruction i = instanceOfInstruction.getInstructionToMixin(flow);
	if (i != null) {
	int varIndex = getVarIndex(i.getVariableName());
	if (varIndex >= 0) {
	m.registerDef(instruction, varIndex);
	}
	}
	}
	else if (instruction instanceof ArgumentInstruction) {
	String variableName = ((ArgumentInstruction)instruction).getVariableName();
	if (variableName != null) {
	m.registerDef(instruction, getVarIndex(variableName));
	}
	}
	else {
	super.fun(m, instruction);
	}
	}
	};
	final ReachingDefinitionsSemilattice lattice = new ReachingDefinitionsSemilattice();
	final DFAEngine<DefinitionMap> engine = new DFAEngine<DefinitionMap>(flow, dfaInstance, lattice);
	final List<DefinitionMap> dfaResult = engine.performDFAWithTimeout();
	Pair<ReachingDefinitionsDfaInstance, List<DefinitionMap>> result = dfaResult == null ? null : Pair.create(dfaInstance, dfaResult);
	return Result.create(result, PsiModificationTracker.MODIFICATION_COUNT);
	}
	});
	}

	@Nullable
	private static DFAType getDefinitionType(Instruction instruction, Instruction[] flow, GrControlFlowOwner scope, Set<MixinTypeInstruction> trace) {
	if (instruction instanceof ReadWriteVariableInstruction && ((ReadWriteVariableInstruction) instruction).isWrite()) {
	final PsiElement element = instruction.getElement();
	if (element != null) {
	return DFAType.create(TypesUtil.boxPrimitiveType(getInitializerType(element), scope.getManager(), scope.getResolveScope()));
	}
	}
	if (instruction instanceof MixinTypeInstruction) {
	return mixinType((MixinTypeInstruction)instruction, flow, scope, trace);
	}
	return null;
	}

	@Nullable
	private static DFAType mixinType(final MixinTypeInstruction instruction, final Instruction[] flow, final GrControlFlowOwner scope, Set<MixinTypeInstruction> trace) {
	if (!trace.add(instruction)) {
	return null;
	}

	String varName = instruction.getVariableName();
	if (varName == null) {
	return null;
	}
	ReadWriteVariableInstruction originalInstr = instruction.getInstructionToMixin(flow);
	if (originalInstr == null) {
	LOG.error(scope.getContainingFile().getName() + ":" + scope.getText());
	}

	DFAType original = getInferredType(varName, originalInstr, flow, scope, trace);
	final PsiType mixin = instruction.inferMixinType();
	if (mixin == null) {
	return original;
	}
	if (original == null) {
	original = DFAType.create(null);
	}
	original.addMixin(mixin, instruction.getConditionInstruction());
	trace.remove(instruction);
	return original;
	}


	@Nullable
	public static PsiType getInitializerType(final PsiElement element) {
	if (element instanceof GrReferenceExpression && ((GrReferenceExpression) element).getQualifierExpression() == null) {
	return getInitializerTypeFor(element);
	}

	if (element instanceof GrVariable) {
	return ((GrVariable)element).getTypeGroovy();
	}

	return null;
	}

	@Nullable
	public static PsiType getInitializerTypeFor(PsiElement element) {
	final PsiElement parent = element.getParent();
	if (parent instanceof GrAssignmentExpression) {
	if (element instanceof GrIndexProperty) {
	final GrExpression rvalue = ((GrAssignmentExpression)parent).getRValue();
	return rvalue != null ? rvalue.getType() : null; //don't try to infer assignment type in case of index property because of infinite recursion (example: a[2]+=4)
	}
	return ((GrAssignmentExpression)parent).getType();
	}

	if (parent instanceof GrTupleExpression) {
	GrTupleExpression list = (GrTupleExpression)parent;
	if (list.getParent() instanceof GrAssignmentExpression) { // multiple assignment
	final GrExpression rValue = ((GrAssignmentExpression) list.getParent()).getRValue();
	int idx = list.indexOf(element);
	if (idx >= 0 && rValue != null) {
	PsiType rType = rValue.getType();
	if (rType instanceof GrTupleType) {
	PsiType[] componentTypes = ((GrTupleType) rType).getComponentTypes();
	if (idx < componentTypes.length) return componentTypes[idx];
	return null;
	}
	return PsiUtil.extractIterableTypeParameter(rType, false);
	}
	}
	}
	if (parent instanceof GrUnaryExpression &&
	TokenSets.POSTFIX_UNARY_OP_SET.contains(((GrUnaryExpression)parent).getOperationTokenType())) {
	return ((GrUnaryExpression)parent).getType();
	}

	return null;
	}

	@Nullable
	public static GrExpression getInitializerFor(GrExpression lValue) {
	final PsiElement parent = lValue.getParent();
	if (parent instanceof GrAssignmentExpression) return ((GrAssignmentExpression)parent).getRValue();
	if (parent instanceof GrTupleExpression) {
	final int i = ((GrTupleExpression)parent).indexOf(lValue);
	final PsiElement pparent = parent.getParent();
	org.jetbrains.plugins.groovy.lang.psi.util.PsiUtil.LOG.assertTrue(pparent instanceof GrAssignmentExpression);

	final GrExpression rValue = ((GrAssignmentExpression)pparent).getRValue();
	if (rValue instanceof GrListOrMap && !((GrListOrMap)rValue).isMap()) {
	final GrExpression[] initializers = ((GrListOrMap)rValue).getInitializers();
	if (initializers.length < i) return initializers[i];
	}
	}

	return null;
	}

	static class TypeDfaInstance implements DfaInstance<TypeDfaState> {
	private final GrControlFlowOwner myScope;
	private final Instruction[] myFlow;
	private final Set<Instruction> myInteresting;
	private final InferenceCache myCache;

	TypeDfaInstance(@NotNull GrControlFlowOwner scope, @NotNull Instruction[] flow, @NotNull Set<Instruction> interesting, @NotNull InferenceCache cache) {
	myScope = scope;
	myFlow = flow;
	myInteresting = interesting;
	myCache = cache;
	}

	@Override
	public void fun(final TypeDfaState state, final Instruction instruction) {
	if (instruction instanceof ReadWriteVariableInstruction) {
	handleVariableWrite(state, (ReadWriteVariableInstruction)instruction);
	}
	else if (instruction instanceof MixinTypeInstruction) {
	handleMixin(state, (MixinTypeInstruction)instruction);
	}
	}

	private void handleMixin(@NotNull final TypeDfaState state, @NotNull final MixinTypeInstruction instruction) {
	final String varName = instruction.getVariableName();
	if (varName == null) return;

	updateVariableType(state, instruction, varName, new NullableComputable<DFAType>() {
	@Override
	public DFAType compute() {
	ReadWriteVariableInstruction originalInstr = instruction.getInstructionToMixin(myFlow);
	assert originalInstr != null && !originalInstr.isWrite();

	DFAType original = state.getVariableType(varName);
	if (original == null) {
	original = DFAType.create(null);
	}
	original = original.negate(originalInstr);
	original.addMixin(instruction.inferMixinType(), instruction.getConditionInstruction());
	return original;
	}
	});
	}

	private void handleVariableWrite(TypeDfaState state, ReadWriteVariableInstruction instruction) {
	final PsiElement element = instruction.getElement();
	if (element != null && instruction.isWrite()) {
	updateVariableType(state, instruction, instruction.getVariableName(), new Computable<DFAType>() {
	@Override
	public DFAType compute() {
	return DFAType.create(TypesUtil.boxPrimitiveType(getInitializerType(element), myScope.getManager(), myScope.getResolveScope()));
	}
	});
	}
	}

	private void updateVariableType(@NotNull TypeDfaState state, @NotNull Instruction instruction, @NotNull String variableName, @NotNull Computable<DFAType> computation) {
	if (!myInteresting.contains(instruction)) {
	state.removeBinding(variableName);
	return;
	}

	DFAType type = myCache.getCachedInferredType(variableName, instruction);
	if (type == null) {
	type = doInference(state.getBindings(instruction), computation);
	}
	state.putType(variableName, type);
	}

	@Override
	@NotNull
	public TypeDfaState initial() {
	return new TypeDfaState();
	}

	@Override
	public boolean isForward() {
	return true;
	}

	}

	private static class InferenceCache {
	final GrControlFlowOwner scope;
	final Instruction[] flow;
	final AtomicReference<List<TypeDfaState>> varTypes;
	final ConcurrentHashSet<Instruction> tooComplex = new ConcurrentHashSet<Instruction>();

	InferenceCache(final GrControlFlowOwner scope) {
	this.scope = scope;
	this.flow = scope.getControlFlow();
	List<TypeDfaState> noTypes = new ArrayList<TypeDfaState>();
	//noinspection ForLoopReplaceableByForEach
	for (int i = 0; i < flow.length; i++) {
	noTypes.add(new TypeDfaState());
	}
	varTypes = new AtomicReference<List<TypeDfaState>>(noTypes);
	}

	@Nullable
	private PsiType getInferredType(@NotNull String variableName, @NotNull Instruction instruction) {
	if (tooComplex.contains(instruction)) return null;

	TypeDfaState cache = varTypes.get().get(instruction.num());
	if (!cache.containsVariable(variableName)) {
	Pair<ReachingDefinitionsDfaInstance, List<DefinitionMap>> defUse = getDefUseMaps(scope);
	if (defUse == null) {
	tooComplex.add(instruction);
	return null;
	}

	Set<Instruction> interesting = collectRequiredInstructions(instruction, variableName, defUse);
	List<TypeDfaState> dfaResult = performTypeDfa(scope, flow, interesting);
	if (dfaResult == null) {
	tooComplex.addAll(interesting);
	} else {
	cacheDfaResult(dfaResult);
	}
	}
	DFAType dfaType = getCachedInferredType(variableName, instruction);
	return dfaType == null ? null : dfaType.getResultType();
	}

	@Nullable
	private List<TypeDfaState> performTypeDfa(@NotNull GrControlFlowOwner owner, @NotNull Instruction[] flow, @NotNull Set<Instruction> interesting) {
	final TypeDfaInstance dfaInstance = new TypeDfaInstance(owner, flow, interesting, this);
	final TypesSemilattice semilattice = new TypesSemilattice(owner.getManager());
	return new DFAEngine<TypeDfaState>(flow, dfaInstance, semilattice).performDFAWithTimeout();
	}

	@Nullable
	DFAType getCachedInferredType(@NotNull String variableName, @NotNull Instruction instruction) {
	DFAType dfaType = varTypes.get().get(instruction.num()).getVariableType(variableName);
	return dfaType == null ? null : dfaType.negate(instruction);
	}

	private Set<Instruction> collectRequiredInstructions(@NotNull Instruction instruction,
	@NotNull String variableName,
	@NotNull Pair<ReachingDefinitionsDfaInstance, List<DefinitionMap>> defUse) {
	Set<Instruction> interesting = ContainerUtil.newHashSet(instruction);
	LinkedList<Pair<Instruction,String>> queue = ContainerUtil.newLinkedList();
	queue.add(Pair.create(instruction, variableName));
	while (!queue.isEmpty()) {
	Pair<Instruction, String> pair = queue.removeFirst();
	for (Pair<Instruction, String> dep : findDependencies(defUse, pair.first, pair.second)) {
	if (interesting.add(dep.first)) {
	queue.addLast(dep);
	}
	}
	}

	return interesting;
	}

	@NotNull
	private Set<Pair<Instruction,String>> findDependencies(@NotNull Pair<ReachingDefinitionsDfaInstance, List<DefinitionMap>> defUse,
	@NotNull Instruction insn,
	@NotNull String varName) {
	DefinitionMap definitionMap = defUse.second.get(insn.num());
	int varIndex = defUse.first.getVarIndex(varName);
	int[] definitions = definitionMap.getDefinitions(varIndex);
	if (definitions == null) return Collections.emptySet();

	LinkedHashSet<Pair<Instruction, String>> pairs = ContainerUtil.newLinkedHashSet();
	for (int defIndex : definitions) {
	Instruction write = flow[defIndex];
	pairs.add(Pair.create(write, varName));
	PsiElement statement = findDependencyScope(write.getElement());
	if (statement != null) {
	pairs.addAll(findAllInstructionsInside(statement));
	}
	}
	return pairs;
	}

	@NotNull
	private List<Pair<Instruction, String>> findAllInstructionsInside(@NotNull PsiElement scope) {
	final List<Pair<Instruction, String>> result = ContainerUtil.newArrayList();
	scope.accept(new PsiRecursiveElementWalkingVisitor() {
	@Override
	public void visitElement(PsiElement element) {
	if (element instanceof GrReferenceExpression && !((GrReferenceExpression)element).isQualified()) {
	String varName = ((GrReferenceExpression)element).getReferenceName();
	if (varName != null) {
	for (Instruction dependency : ControlFlowUtils.findAllInstructions(element, flow)) {
	result.add(Pair.create(dependency, varName));
	}
	}
	}
	super.visitElement(element);
	}
	});
	return result;
	}

	@Nullable
	private static PsiElement findDependencyScope(@Nullable PsiElement element) {
	return PsiTreeUtil.findFirstParent(element, new Condition<PsiElement>() {
	@Override
	public boolean value(PsiElement element) {
	return org.jetbrains.plugins.groovy.lang.psi.util.PsiUtil.isExpressionStatement(element) \|\|
	!(element.getParent() instanceof GrExpression);
	}
	});
	}

	private void cacheDfaResult(@NotNull List<TypeDfaState> dfaResult) {
	while (true) {
	List<TypeDfaState> oldTypes = varTypes.get();
	if (varTypes.compareAndSet(oldTypes, addDfaResult(dfaResult, oldTypes))) {
	return;
	}
	}
	}

	@NotNull
	private static List<TypeDfaState> addDfaResult(@NotNull List<TypeDfaState> dfaResult, @NotNull List<TypeDfaState> oldTypes) {
	List<TypeDfaState> newTypes = new ArrayList<TypeDfaState>(oldTypes);
	for (int i = 0; i < dfaResult.size(); i++) {
	newTypes.set(i, newTypes.get(i).mergeWith(dfaResult.get(i)));
	}
	return newTypes;
	}
	}

	}