TypeInference CreateNestedInstance()
		{
			TypeInference c = new TypeInference(context, conversions);
			c.algorithm = algorithm;
			c.nestingLevel = nestingLevel + 1;
			return c;
		}

        public static IType GuessType(RefactoringContext context, AstNode expr)
        {
            if (expr is SimpleType && expr.Role == Roles.TypeArgument) {
                if (expr.Parent is MemberReferenceExpression || expr.Parent is IdentifierExpression) {
                    var rr = context.Resolve (expr.Parent);
                    var argumentNumber = expr.Parent.GetChildrenByRole (Roles.TypeArgument).TakeWhile (c => c != expr).Count ();

                    var mgrr = rr as MethodGroupResolveResult;
                    if (mgrr != null && mgrr.Methods.Any () && mgrr.Methods.First ().TypeArguments.Count > argumentNumber)
                        return mgrr.Methods.First ().TypeParameters[argumentNumber];
                } else if (expr.Parent is MemberType || expr.Parent is SimpleType) {
                    var rr = context.Resolve (expr.Parent);
                    var argumentNumber = expr.Parent.GetChildrenByRole (Roles.TypeArgument).TakeWhile (c => c != expr).Count ();
                    var mgrr = rr as TypeResolveResult;
                    if (mgrr != null &&  mgrr.Type.TypeParameterCount > argumentNumber) {
                        return mgrr.Type.GetDefinition ().TypeParameters[argumentNumber];
                    }
                }
            }

            var type = GetValidTypes(context.Resolver, expr).ToArray();
            var typeInference = new TypeInference(context.Compilation);
            typeInference.Algorithm = TypeInferenceAlgorithm.Improved;
            var inferedType = typeInference.FindTypeInBounds(type, emptyTypes);
            return inferedType;
        }

 public static AstType GuessAstType(RefactoringContext context, AstNode expr)
 {
     var type = GetValidTypes(context.Resolver, expr).ToArray();
     var typeInference = new TypeInference(context.Compilation);
     typeInference.Algorithm = TypeInferenceAlgorithm.Improved;
     var inferedType = typeInference.FindTypeInBounds(type, emptyTypes);
     if (inferedType.Kind == TypeKind.Unknown)
         return new PrimitiveType("object");
     return context.CreateShortType(inferedType);
 }

        /// <summary>
        /// Resolves an array creation.
        /// </summary>
        /// <param name="elementType">
        /// The array element type.
        /// Pass null to resolve an implicitly-typed array creation.
        /// </param>
        /// <param name="dimensions">
        /// The number of array dimensions.
        /// </param>
        /// <param name="sizeArguments">
        /// The size arguments. May be null if no explicit size was given.
        /// The resolver may mutate this array to wrap elements in <see cref="ConversionResolveResult"/>s!
        /// </param>
        /// <param name="initializerElements">
        /// The initializer elements. May be null if no array initializer was specified.
        /// The resolver may mutate this array to wrap elements in <see cref="ConversionResolveResult"/>s!
        /// </param>
        /// <param name="allowArrayConstants">
        /// Specifies whether to allow treating single-dimensional arrays like compile-time constants.
        /// This is used for attribute arguments.
        /// </param>
        public ArrayCreateResolveResult ResolveArrayCreation(IType elementType, int dimensions = 1, ResolveResult[] sizeArguments = null, ResolveResult[] initializerElements = null)
        {
            if (sizeArguments != null && dimensions != Math.Max(1, sizeArguments.Length))
                throw new ArgumentException("dimensions and sizeArguments.Length don't match");
            if (elementType == null) {
                TypeInference typeInference = new TypeInference(compilation, conversions);
                bool success;
                elementType = typeInference.GetBestCommonType(initializerElements, out success);
            }
            IType arrayType = new ArrayType(compilation, elementType, dimensions);

            if (sizeArguments != null)
                AdjustArrayAccessArguments(sizeArguments);

            if (initializerElements != null) {
                for (int i = 0; i < initializerElements.Length; i++) {
                    initializerElements[i] = Convert(initializerElements[i], elementType);
                }
            }
            return new ArrayCreateResolveResult(arrayType, sizeArguments, initializerElements);
        }

		public void Setup()
		{
			ti = new TypeInference(compilation);
		}

		IEnumerable<ICompletionData> CreateConstructorCompletionData(IType hintType)
		{
			var wrapper = new CompletionDataWrapper(this);
			var state = GetState();
			Func<IType, IType> pred = null;
			Action<ICompletionData, IType> typeCallback = null;
			var inferredTypesCategory = new Category("Inferred Types", null);
			var derivedTypesCategory = new Category("Derived Types", null);
			if (hintType != null) {
				if (hintType.Kind != TypeKind.Unknown) {
					var lookup = new MemberLookup(
						ctx.CurrentTypeDefinition,
						Compilation.MainAssembly
					);
					typeCallback = (data, t) => {
						//check if type is in inheritance tree.
						if (hintType.GetDefinition() != null &&
							t.GetDefinition() != null &&
							t.GetDefinition().IsDerivedFrom(hintType.GetDefinition())) {
							data.CompletionCategory = derivedTypesCategory;
						}
					};
					pred = t => {
						if (t.Kind == TypeKind.Interface && hintType.Kind != TypeKind.Array) {
							return null;
						}
						// check for valid constructors
						if (t.GetConstructors().Count() > 0) {
							bool isProtectedAllowed = currentType != null ? 
							                          currentType.Resolve(ctx).GetDefinition().IsDerivedFrom(t.GetDefinition()) : false;
							if (!t.GetConstructors().Any(m => lookup.IsAccessible(m, isProtectedAllowed))) {
								return null;
							}
						}

						// check derived types
						var typeDef = t.GetDefinition();
						var hintDef = hintType.GetDefinition();
						if (typeDef != null && hintDef != null && typeDef.IsDerivedFrom(hintDef)) {
							var newType = wrapper.AddType(t, true);
							if (newType != null) {
								newType.CompletionCategory = inferredTypesCategory;
							}
						}

						// check type inference
						var typeInference = new TypeInference(Compilation);
						typeInference.Algorithm = TypeInferenceAlgorithm.ImprovedReturnAllResults;

						var inferedType = typeInference.FindTypeInBounds(new [] { t }, new [] { hintType });
						if (inferedType != SpecialType.UnknownType) {
							var newType = wrapper.AddType(inferedType, true);
							if (newType != null) {
								newType.CompletionCategory = inferredTypesCategory;
							}
							return null;
						}
						return t;
					};
					if (!(hintType.Kind == TypeKind.Interface && hintType.Kind != TypeKind.Array)) {
						var hint = wrapper.AddType(hintType, true);
						if (hint != null) {
							DefaultCompletionString = hint.DisplayText;
							hint.CompletionCategory = derivedTypesCategory;
						}
					}
					if (hintType is ParameterizedType && hintType.TypeParameterCount == 1 && hintType.FullName == "System.Collections.Generic.IEnumerable") {
						var arg = ((ParameterizedType)hintType).TypeArguments.FirstOrDefault();
						if (arg.Kind != TypeKind.TypeParameter) {
							var array = new ArrayType(ctx.Compilation, arg, 1);
							wrapper.AddType(array, true);
						}
					}
				} else {
					var hint = wrapper.AddType(hintType, true);
					if (hint != null) {
						DefaultCompletionString = hint.DisplayText;
						hint.CompletionCategory = derivedTypesCategory;
					}
				}
			} 
			AddTypesAndNamespaces(wrapper, state, null, pred, m => false, typeCallback, true);
			if (hintType == null || hintType == SpecialType.UnknownType) {
				AddKeywords(wrapper, primitiveTypesKeywords.Where(k => k != "void"));
			}

			CloseOnSquareBrackets = true;
			AutoCompleteEmptyMatch = true;
			AutoCompleteEmptyMatchOnCurlyBracket = false;
			return wrapper.Result;
		}

		void RunTypeInference(Candidate candidate)
		{
			IMethod method = candidate.Member as IMethod;
			if (method == null || method.TypeParameters.Count == 0) {
				if (explicitlyGivenTypeArguments != null) {
					// method does not expect type arguments, but was given some
					candidate.AddError(OverloadResolutionErrors.WrongNumberOfTypeArguments);
				}
				return;
			}
			ParameterizedType parameterizedDeclaringType = candidate.Member.DeclaringType as ParameterizedType;
			IList<IType> classTypeArguments;
			if (parameterizedDeclaringType != null) {
				classTypeArguments = parameterizedDeclaringType.TypeArguments;
			} else {
				classTypeArguments = null;
			}
			// The method is generic:
			if (explicitlyGivenTypeArguments != null) {
				if (explicitlyGivenTypeArguments.Length == method.TypeParameters.Count) {
					candidate.InferredTypes = explicitlyGivenTypeArguments;
				} else {
					candidate.AddError(OverloadResolutionErrors.WrongNumberOfTypeArguments);
					// wrong number of type arguments given, so truncate the list or pad with UnknownType
					candidate.InferredTypes = new IType[method.TypeParameters.Count];
					for (int i = 0; i < candidate.InferredTypes.Length; i++) {
						if (i < explicitlyGivenTypeArguments.Length)
							candidate.InferredTypes[i] = explicitlyGivenTypeArguments[i];
						else
							candidate.InferredTypes[i] = SpecialType.UnknownType;
					}
				}
			} else {
				TypeInference ti = new TypeInference(compilation, conversions);
				bool success;
				candidate.InferredTypes = ti.InferTypeArguments(candidate.TypeParameters, arguments, candidate.ParameterTypes, out success, classTypeArguments);
				if (!success)
					candidate.AddError(OverloadResolutionErrors.TypeInferenceFailed);
			}
			// Now substitute in the formal parameters:
			var substitution = new ConstraintValidatingSubstitution(classTypeArguments, candidate.InferredTypes, this);
			for (int i = 0; i < candidate.ParameterTypes.Length; i++) {
				candidate.ParameterTypes[i] = candidate.ParameterTypes[i].AcceptVisitor(substitution);
			}
			if (!substitution.ConstraintsValid)
				candidate.AddError(OverloadResolutionErrors.ConstructedTypeDoesNotSatisfyConstraint);
		}

 public OccursInVisitor(TypeInference typeInference)
 {
     this.tp = typeInference.typeParameters;
     this.Occurs = new bool[tp.Length];
 }

		static bool IsEligibleExtensionMethod(ICompilation compilation, CSharpConversions conversions, IType targetType, IMethod method, bool useTypeInference, out IType[] outInferredTypes)
		{
			outInferredTypes = null;
			if (targetType == null)
				return true;
			if (method.Parameters.Count == 0)
				return false;
			IType thisParameterType = method.Parameters[0].Type;
			if (useTypeInference && method.TypeParameters.Count > 0) {
				// We need to infer type arguments from targetType:
				TypeInference ti = new TypeInference(compilation, conversions);
				ResolveResult[] arguments = { new ResolveResult(targetType) };
				IType[] parameterTypes = { method.Parameters[0].Type };
				bool success;
				var inferredTypes = ti.InferTypeArguments(method.TypeParameters, arguments, parameterTypes, out success);
				var substitution = new TypeParameterSubstitution(null, inferredTypes);
				// Validate that the types that could be inferred (aren't unknown) satisfy the constraints:
				bool hasInferredTypes = false;
				for (int i = 0; i < inferredTypes.Length; i++) {
					if (inferredTypes[i].Kind != TypeKind.Unknown && inferredTypes[i].Kind != TypeKind.UnboundTypeArgument) {
						hasInferredTypes = true;
						if (!OverloadResolution.ValidateConstraints(method.TypeParameters[i], inferredTypes[i], substitution, conversions))
							return false;
					} else {
						inferredTypes[i] = method.TypeParameters[i]; // do not substitute types that could not be inferred
					}
				}
				if (hasInferredTypes)
					outInferredTypes = inferredTypes;
				thisParameterType = thisParameterType.AcceptVisitor(substitution);
			}
			Conversion c = conversions.ImplicitConversion(targetType, thisParameterType);
			return c.IsValid && (c.IsIdentityConversion || c.IsReferenceConversion || c.IsBoxingConversion);
		}

        /// <summary>
        /// Resolves an array creation.
        /// </summary>
        /// <param name="elementType">
        /// The array element type.
        /// Pass null to resolve an implicitly-typed array creation.
        /// </param>
        /// <param name="sizeArguments">
        /// The size arguments.
        /// The length of this array will be used as the number of dimensions of the array type.
        /// The resolver may mutate this array to wrap elements in <see cref="ConversionResolveResult"/>s!
        /// </param>
        /// <param name="initializerElements">
        /// The initializer elements. May be null if no array initializer was specified.
        /// The resolver may mutate this array to wrap elements in <see cref="ConversionResolveResult"/>s!
        /// </param>
        public ArrayCreateResolveResult ResolveArrayCreation(IType elementType, ResolveResult[] sizeArguments, ResolveResult[] initializerElements = null)
        {
            int dimensions = sizeArguments.Length;
            if (dimensions == 0)
                throw new ArgumentException("sizeArguments.Length must not be 0");
            if (elementType == null) {
                TypeInference typeInference = new TypeInference(compilation, conversions);
                bool success;
                elementType = typeInference.GetBestCommonType(initializerElements, out success);
            }
            IType arrayType = new ArrayType(compilation, elementType, dimensions);

            AdjustArrayAccessArguments(sizeArguments);

            if (initializerElements != null) {
                for (int i = 0; i < initializerElements.Length; i++) {
                    initializerElements[i] = Convert(initializerElements[i], elementType);
                }
            }
            return new ArrayCreateResolveResult(arrayType, sizeArguments, initializerElements);
        }

		public static IType GuessType(RefactoringContext context, Expression expr)
		{
			var type = GetValidTypes(context.Resolver, expr).ToArray();
			var typeInference = new TypeInference(context.Compilation);
			typeInference.Algorithm = TypeInferenceAlgorithm.Improved;
			var inferedType = typeInference.FindTypeInBounds(type, emptyTypes);
			return inferedType;
		}

		public void Setup()
		{
			ti = new TypeInference(ctx);
		}

		IEnumerable<ICompletionData> CreateTypeCompletionData(IType hintType, AstType hintTypeAst)
		{
			var wrapper = new CompletionDataWrapper(this);
			var state = GetState();
			Func<IType, IType> pred = null;
			if (hintType != null) {
				
				if (hintType.Kind != TypeKind.Unknown) {
					var lookup = new MemberLookup(ctx.CurrentTypeDefinition, Compilation.MainAssembly);
					pred = t => {
						// check if type is in inheritance tree.
						if (hintType.GetDefinition() != null && !t.GetDefinition().IsDerivedFrom(hintType.GetDefinition())) {
							return null;
						}
						if (t.Kind == TypeKind.Interface && hintType.Kind != TypeKind.Array) {
							return null;
						}
						// check for valid constructors
						if (t.GetConstructors().Count() > 0) {
							bool isProtectedAllowed = currentType != null ? currentType.Resolve(ctx).GetDefinition().IsDerivedFrom(t.GetDefinition()) : false;
							if (!t.GetConstructors().Any(m => lookup.IsAccessible(m, isProtectedAllowed)))
								return null;
						}

						var typeInference = new TypeInference(Compilation);
						typeInference.Algorithm = TypeInferenceAlgorithm.ImprovedReturnAllResults;
						var inferedType = typeInference.FindTypeInBounds(new [] { t }, new [] { hintType });
						wrapper.AddType(inferedType, amb.ConvertType(inferedType));
						return null;
					};
					if (!(hintType.Kind == TypeKind.Interface && hintType.Kind != TypeKind.Array)) {
						DefaultCompletionString = GetShortType(hintType, GetState());
						wrapper.AddType(hintType, DefaultCompletionString);
					}
					if (hintType is ParameterizedType && hintType.TypeParameterCount == 1 && hintType.FullName == "System.Collections.Generic.IEnumerable") {
						var arg = ((ParameterizedType)hintType).TypeArguments.FirstOrDefault();
						var array = new ArrayTypeReference(arg.ToTypeReference(), 1).Resolve(ctx);
						wrapper.AddType(array, amb.ConvertType(array));
					}
				} else {
					DefaultCompletionString = hintTypeAst.ToString();
					wrapper.AddType(hintType, DefaultCompletionString);
				}
			} 
			AddTypesAndNamespaces(wrapper, state, null, pred, m => false);
			if (hintType == null || hintType == SpecialType.UnknownType)
				AddKeywords(wrapper, primitiveTypesKeywords.Where(k => k != "void"));
			CloseOnSquareBrackets = true;
			AutoCompleteEmptyMatch = true;
			return wrapper.Result;
		}

 public void Setup()
 {
     ti = new TypeInference(CecilLoaderTests.Mscorlib);
 }