PY-43388 Add basic type checker support in Cython files
[idea/community.git] / python / python-psi-impl / src / com / jetbrains / python / psi / types / PyTypeChecker.java
1 // Copyright 2000-2018 JetBrains s.r.o. Use of this source code is governed by the Apache 2.0 license that can be found in the LICENSE file.
2 package com.jetbrains.python.psi.types;
3
4 import com.intellij.openapi.util.Pair;
5 import com.intellij.openapi.util.RecursionManager;
6 import com.intellij.psi.PsiElement;
7 import com.intellij.psi.PsiFile;
8 import com.intellij.psi.ResolveResult;
9 import com.intellij.util.ArrayUtil;
10 import com.intellij.util.containers.ContainerUtil;
11 import com.jetbrains.python.PyNames;
12 import com.jetbrains.python.PythonRuntimeService;
13 import com.jetbrains.python.codeInsight.dataflow.scope.ScopeUtil;
14 import com.jetbrains.python.codeInsight.typing.PyProtocolsKt;
15 import com.jetbrains.python.codeInsight.typing.PyTypingTypeProvider;
16 import com.jetbrains.python.psi.*;
17 import com.jetbrains.python.psi.impl.PyBuiltinCache;
18 import com.jetbrains.python.psi.impl.PyTypeProvider;
19 import com.jetbrains.python.psi.resolve.PyResolveContext;
20 import com.jetbrains.python.psi.resolve.RatedResolveResult;
21 import com.jetbrains.python.pyi.PyiFile;
22 import com.jetbrains.python.sdk.PythonSdkUtil;
23 import one.util.streamex.StreamEx;
24 import org.jetbrains.annotations.NotNull;
25 import org.jetbrains.annotations.Nullable;
26
27 import java.util.*;
28 import java.util.function.Function;
29
30 import static com.jetbrains.python.PyNames.FUNCTION;
31 import static com.jetbrains.python.psi.PyUtil.as;
32 import static com.jetbrains.python.psi.PyUtil.getReturnTypeToAnalyzeAsCallType;
33 import static com.jetbrains.python.psi.impl.PyCallExpressionHelper.*;
34
35 /**
36  * @author vlan
37  */
38 public final class PyTypeChecker {
39   private PyTypeChecker() {
40   }
41
42   /**
43    * See {@link PyTypeChecker#match(PyType, PyType, TypeEvalContext, Map)} for description.
44    */
45   public static boolean match(@Nullable PyType expected, @Nullable PyType actual, @NotNull TypeEvalContext context) {
46     return match(expected, actual, new MatchContext(context, new HashMap<>())).orElse(true);
47   }
48
49   /**
50    * Checks whether a type {@code actual} can be placed where {@code expected} is expected.
51    *
52    * For example {@code int} matches {@code object}, while {@code str} doesn't match {@code int}.
53    * Work for builtin types, classes, tuples etc.
54    *
55    * Whether it's unknown if {@code actual} match {@code expected} the method returns {@code true}.
56    *
57    * @implNote This behavior may be changed in future by replacing {@code boolean} with {@code Optional<Boolean>} and updating the clients.
58    *
59    * @param expected expected type
60    * @param actual type to be matched against expected
61    * @param context type evaluation context
62    * @param substitutions map of substitutions for {@code expected} type
63    * @return {@code false} if {@code expected} and {@code actual} don't match, true otherwise
64    */
65   public static boolean match(@Nullable PyType expected,
66                               @Nullable PyType actual,
67                               @NotNull TypeEvalContext context,
68                               @NotNull Map<PyGenericType, PyType> substitutions) {
69     return match(expected, actual, new MatchContext(context, substitutions)).orElse(true);
70   }
71
72   @NotNull
73   private static Optional<Boolean> match(@Nullable PyType expected, @Nullable PyType actual, @NotNull MatchContext context) {
74     final Optional<Boolean> result = RecursionManager.doPreventingRecursion(
75       Pair.create(expected, actual),
76       false,
77       () -> matchImpl(expected, actual, context)
78     );
79
80     return result == null ? Optional.of(true) : result;
81   }
82
83   /**
84    * Perform type matching.
85    *
86    * Implementation details:
87    * <ul>
88    *  <li>The method mutates {@code context.substitutions} map adding new entries into it
89    *  <li>The order of match subroutine calls is important
90    *  <li>The method may recursively call itself
91    * </ul>
92    */
93   @NotNull
94   private static Optional<Boolean> matchImpl(@Nullable PyType expected, @Nullable PyType actual, @NotNull MatchContext context) {
95     for (PyTypeCheckerExtension extension : PyTypeCheckerExtension.EP_NAME.getExtensionList()) {
96       final Optional<Boolean> result = extension.match(expected, actual, context.context, context.substitutions);
97       if (result.isPresent()) {
98         return result;
99       }
100     }
101
102     if (expected instanceof PyClassType) {
103       Optional<Boolean> match = matchObject((PyClassType)expected, actual);
104       if (match.isPresent()) {
105         return match;
106       }
107     }
108
109     if (actual instanceof PyGenericType && context.reversedSubstitutions) {
110       return Optional.of(match((PyGenericType)actual, expected, context));
111     }
112
113     if (expected instanceof PyGenericType) {
114       return Optional.of(match((PyGenericType)expected, actual, context));
115     }
116
117     if (expected == null || actual == null || isUnknown(actual, context.context)) {
118       return Optional.of(true);
119     }
120
121     if (actual instanceof PyUnionType) {
122       return Optional.of(match(expected, (PyUnionType)actual, context));
123     }
124
125     if (expected instanceof PyUnionType) {
126       return Optional.of(match((PyUnionType)expected, actual, context));
127     }
128
129     if (expected instanceof PyClassType && actual instanceof PyClassType) {
130       Optional<Boolean> match = match((PyClassType)expected, (PyClassType)actual, context);
131       if (match.isPresent()) {
132         return match;
133       }
134     }
135
136     if (actual instanceof PyStructuralType && ((PyStructuralType)actual).isInferredFromUsages()) {
137       return Optional.of(true);
138     }
139
140     if (expected instanceof PyStructuralType) {
141       return Optional.of(match((PyStructuralType)expected, actual, context.context));
142     }
143
144     if (actual instanceof PyStructuralType && expected instanceof PyClassType) {
145       final Set<String> expectedAttributes = ((PyClassType)expected).getMemberNames(true, context.context);
146       return Optional.of(expectedAttributes.containsAll(((PyStructuralType)actual).getAttributeNames()));
147     }
148
149     if (actual instanceof PyCallableType && expected instanceof PyCallableType) {
150       final PyCallableType expectedCallable = (PyCallableType)expected;
151       final PyCallableType actualCallable = (PyCallableType)actual;
152       final Optional<Boolean> match = match(expectedCallable, actualCallable, context);
153       if (match.isPresent()) {
154         return match;
155       }
156     }
157
158     // remove after making PyNoneType inheriting PyClassType
159     if (expected instanceof PyNoneType) {
160       return Optional.of(actual instanceof PyNoneType);
161     }
162
163     if (expected instanceof PyModuleType) {
164       return Optional.of(actual instanceof PyModuleType && ((PyModuleType)expected).getModule() == ((PyModuleType)actual).getModule());
165     }
166
167     if (expected instanceof PyClassType && actual instanceof PyModuleType) {
168       return match(expected, ((PyModuleType)actual).getModuleClassType(), context);
169     }
170
171     return Optional.of(matchNumericTypes(expected, actual));
172   }
173
174   /**
175    * Check whether {@code expected} is Python *object* or *type*.
176    *
177    * {@see PyTypeChecker#match(PyType, PyType, TypeEvalContext, Map)}
178    */
179   @NotNull
180   private static Optional<Boolean> matchObject(@NotNull PyClassType expected, @Nullable PyType actual) {
181     if (ArrayUtil.contains(expected.getName(), PyNames.OBJECT, PyNames.TYPE)) {
182       final PyBuiltinCache builtinCache = PyBuiltinCache.getInstance(expected.getPyClass());
183       if (expected.equals(builtinCache.getObjectType())) {
184         return Optional.of(true);
185       }
186       if (expected.equals(builtinCache.getTypeType()) &&
187           actual instanceof PyInstantiableType && ((PyInstantiableType)actual).isDefinition()) {
188         return Optional.of(true);
189       }
190     }
191     return Optional.empty();
192   }
193
194   /**
195    * Match {@code actual} versus {@code PyGenericType expected}.
196    *
197    * The method mutates {@code context.substitutions} map adding new entries into it
198    */
199   private static boolean match(@NotNull PyGenericType expected, @Nullable PyType actual, @NotNull MatchContext context) {
200     if (expected.isDefinition() && actual instanceof PyInstantiableType && !((PyInstantiableType<?>)actual).isDefinition()) {
201       return false;
202     }
203
204     final PyType substitution = context.substitutions.get(expected);
205     PyType bound = expected.getBound();
206     // Promote int in Type[TypeVar('T', int)] to Type[int] before checking that bounds match
207     if (expected.isDefinition()) {
208       final Function<PyType, PyType> toDefinition = t -> t instanceof PyInstantiableType ? ((PyInstantiableType<?>)t).toClass() : t;
209       bound = PyUnionType.union(PyTypeUtil.toStream(bound).map(toDefinition).toList());
210     }
211
212     Optional<Boolean> match = match(bound, actual, context);
213     if (match.isPresent() && !match.get()) {
214       return false;
215     }
216
217     if (substitution != null) {
218       if (expected.equals(actual) || substitution.equals(expected)) {
219         return true;
220       }
221
222       Optional<Boolean> recursiveMatch = RecursionManager.doPreventingRecursion(
223         expected, false, context.reversedSubstitutions
224                          ? () -> match(actual, substitution, context)
225                          : () -> match(substitution, actual, context)
226       );
227       return recursiveMatch != null ? recursiveMatch.orElse(false) : false;
228     }
229
230     if (actual != null) {
231       context.substitutions.put(expected, actual);
232     }
233     else if (bound != null) {
234       context.substitutions.put(expected, PyUnionType.createWeakType(bound));
235     }
236
237     return true;
238   }
239
240   private static boolean match(@NotNull PyType expected, @NotNull PyUnionType actual, @NotNull MatchContext context) {
241     if (expected instanceof PyTupleType) {
242       Optional<Boolean> match = match((PyTupleType)expected, actual, context);
243       if (match.isPresent()) {
244         return match.get();
245       }
246     }
247
248     return ContainerUtil.or(actual.getMembers(), type -> match(expected, type, context).orElse(false));
249   }
250
251   @NotNull
252   private static Optional<Boolean> match(@NotNull PyTupleType expected, @NotNull PyUnionType actual, @NotNull MatchContext context) {
253     final int elementCount = expected.getElementCount();
254
255     if (!expected.isHomogeneous() && consistsOfSameElementNumberTuples(actual, elementCount)) {
256       return Optional.of(substituteExpectedElementsWithUnions(expected, elementCount, actual, context));
257     }
258
259     return Optional.empty();
260   }
261
262   private static boolean match(@NotNull PyUnionType expected, @NotNull PyType actual, @NotNull MatchContext context) {
263     return ContainerUtil.or(expected.getMembers(), type -> match(type, actual, context).orElse(true));
264   }
265
266   @NotNull
267   private static Optional<Boolean> match(@NotNull PyClassType expected, @NotNull PyClassType actual, @NotNull MatchContext matchContext) {
268     if (expected.equals(actual)) {
269       return Optional.of(true);
270     }
271
272     final TypeEvalContext context = matchContext.context;
273
274     if (expected.isDefinition() ^ actual.isDefinition() && !PyProtocolsKt.isProtocol(expected, context)) {
275       if (!expected.isDefinition() && actual.isDefinition()) {
276         final PyClassLikeType metaClass = actual.getMetaClassType(context, true);
277         return Optional.of(metaClass != null && match((PyType)expected, metaClass.toInstance(), matchContext).orElse(true));
278       }
279       return Optional.of(false);
280     }
281
282     if (expected instanceof PyTupleType && actual instanceof PyTupleType) {
283       return match((PyTupleType)expected, (PyTupleType)actual, matchContext);
284     }
285
286     if (expected instanceof PyLiteralType) {
287       return Optional.of(actual instanceof PyLiteralType && PyLiteralType.Companion.match((PyLiteralType)expected, (PyLiteralType)actual));
288     }
289
290     if (actual instanceof PyTypedDictType) {
291       if (!((PyTypedDictType)actual).isInferred()) {
292         final Optional<Boolean> match = PyTypedDictType.Companion.checkStructuralCompatibility(expected, (PyTypedDictType)actual, context);
293         if (match.isPresent()) {
294           return match;
295         }
296       }
297       if (expected instanceof PyTypedDictType) {
298         return Optional.of(PyTypedDictType.Companion.match((PyTypedDictType)expected, (PyTypedDictType)actual, context));
299       }
300     }
301
302     final PyClass superClass = expected.getPyClass();
303     final PyClass subClass = actual.getPyClass();
304     final boolean matchClasses = matchClasses(superClass, subClass, context);
305
306     if (PyProtocolsKt.isProtocol(expected, context) && !matchClasses) {
307       if (expected instanceof PyCollectionType && !matchGenerics((PyCollectionType)expected, actual, matchContext)) {
308         return Optional.of(false);
309       }
310
311       // methods from the actual will be matched against method definitions from the expected below
312       // here we make substitutions from expected definition to its usage
313       StreamEx
314         .of(PyTypeProvider.EP_NAME.getExtensionList())
315         .map(provider -> provider.getGenericType(superClass, context))
316         .select(PyCollectionType.class)
317         .findFirst()
318         .ifPresent(it -> matchGenerics(it, expected, matchContext));
319
320       for (kotlin.Pair<PyTypedElement, List<RatedResolveResult>> pair : PyProtocolsKt.inspectProtocolSubclass(expected, actual, context)) {
321         final List<RatedResolveResult> subclassElements = pair.getSecond();
322         if (ContainerUtil.isEmpty(subclassElements)) {
323           return Optional.of(false);
324         }
325
326         final PyType protocolElementType = dropSelfIfNeeded(expected, context.getType(pair.getFirst()), context);
327
328         final boolean elementResult = StreamEx
329           .of(subclassElements)
330           .map(ResolveResult::getElement)
331           .select(PyTypedElement.class)
332           .map(context::getType)
333           .anyMatch(
334             subclassElementType -> {
335               return match(protocolElementType,
336                            dropSelfIfNeeded(actual, subclassElementType, context), matchContext).orElse(true);
337             }
338           );
339
340         if (!elementResult) {
341           return Optional.of(false);
342         }
343       }
344
345       return Optional.of(true);
346     }
347
348     if (expected instanceof PyCollectionType) {
349       return Optional.of(match((PyCollectionType)expected, actual, matchContext));
350     }
351
352     if (matchClasses) {
353       if (expected instanceof PyTypingNewType && !expected.equals(actual) && superClass.equals(subClass)) {
354         return Optional.of(actual.getAncestorTypes(context).contains(expected));
355       }
356       return Optional.of(true);
357     }
358
359     if (expected.equals(actual)) {
360       return Optional.of(true);
361     }
362     return Optional.empty();
363   }
364
365   private static @Nullable PyType dropSelfIfNeeded(@NotNull PyClassType classType,
366                                                    @Nullable PyType elementType,
367                                                    @NotNull TypeEvalContext context) {
368     if (elementType instanceof PyFunctionType) {
369       PyFunctionType functionType = (PyFunctionType)elementType;
370       if (PyUtil.isInitOrNewMethod(functionType.getCallable()) || !classType.isDefinition()) {
371         return functionType.dropSelf(context);
372       }
373     }
374     return elementType;
375   }
376
377
378   @NotNull
379   private static Optional<Boolean> match(@NotNull PyTupleType expected, @NotNull PyTupleType actual, @NotNull MatchContext context) {
380     if (!expected.isHomogeneous() && !actual.isHomogeneous()) {
381       if (expected.getElementCount() != actual.getElementCount()) {
382         return Optional.of(false);
383       }
384
385       for (int i = 0; i < expected.getElementCount(); i++) {
386         if (!match(expected.getElementType(i), actual.getElementType(i), context).orElse(true)) {
387           return Optional.of(false);
388         }
389       }
390       return Optional.of(true);
391     }
392
393     if (expected.isHomogeneous() && !actual.isHomogeneous()) {
394       final PyType expectedElementType = expected.getIteratedItemType();
395       for (int i = 0; i < actual.getElementCount(); i++) {
396         if (!match(expectedElementType, actual.getElementType(i), context).orElse(true)) {
397           return Optional.of(false);
398         }
399       }
400       return Optional.of(true);
401     }
402
403     if (!expected.isHomogeneous() && actual.isHomogeneous()) {
404       return Optional.of(false);
405     }
406
407     return match(expected.getIteratedItemType(), actual.getIteratedItemType(), context);
408   }
409
410   private static boolean match(@NotNull PyCollectionType expected, @NotNull PyClassType actual, @NotNull MatchContext context) {
411     if (actual instanceof PyTupleType) {
412       return match(expected, (PyTupleType)actual, context);
413     }
414
415     final PyClass superClass = expected.getPyClass();
416     final PyClass subClass = actual.getPyClass();
417
418     return matchClasses(superClass, subClass, context.context) && matchGenerics(expected, actual, context);
419   }
420
421   private static boolean match(@NotNull PyCollectionType expected, @NotNull PyTupleType actual, @NotNull MatchContext context) {
422     if (!matchClasses(expected.getPyClass(), actual.getPyClass(), context.context)) {
423       return false;
424     }
425
426     final PyType superElementType = expected.getIteratedItemType();
427     final PyType subElementType = actual.getIteratedItemType();
428
429     return match(superElementType, subElementType, context).orElse(true);
430   }
431
432   private static boolean match(@NotNull PyStructuralType expected, @NotNull PyType actual, @NotNull TypeEvalContext context) {
433     if (actual instanceof PyStructuralType) {
434       return match(expected, (PyStructuralType)actual);
435     }
436     if (actual instanceof PyClassType) {
437       return match(expected, (PyClassType)actual, context);
438     }
439     if (actual instanceof PyModuleType) {
440       final PyFile module = ((PyModuleType)actual).getModule();
441       if (module.getLanguageLevel().isAtLeast(LanguageLevel.PYTHON37) && definesGetAttr(module, context)) {
442         return true;
443       }
444     }
445
446     final PyResolveContext resolveContext = PyResolveContext.defaultContext().withTypeEvalContext(context);
447     return !ContainerUtil.exists(expected.getAttributeNames(), attribute -> ContainerUtil
448       .isEmpty(actual.resolveMember(attribute, null, AccessDirection.READ, resolveContext)));
449   }
450
451   private static boolean match(@NotNull PyStructuralType expected, @NotNull PyStructuralType actual) {
452     if (expected.isInferredFromUsages()) {
453       return true;
454     }
455     return expected.getAttributeNames().containsAll(actual.getAttributeNames());
456   }
457
458   private static boolean match(@NotNull PyStructuralType expected, @NotNull PyClassType actual, @NotNull TypeEvalContext context) {
459     if (overridesGetAttr(actual.getPyClass(), context)) {
460       return true;
461     }
462     final Set<String> actualAttributes = actual.getMemberNames(true, context);
463     return actualAttributes.containsAll(expected.getAttributeNames());
464   }
465
466   @NotNull
467   private static Optional<Boolean> match(@NotNull PyCallableType expected,
468                                          @NotNull PyCallableType actual,
469                                          @NotNull MatchContext matchContext) {
470     if (actual instanceof PyFunctionType && expected instanceof PyClassType && FUNCTION.equals(expected.getName())
471         && expected.equals(PyBuiltinCache.getInstance(actual.getCallable()).getObjectType(FUNCTION))) {
472       return Optional.of(true);
473     }
474
475     if (expected instanceof PyClassLikeType) {
476       return PyTypingTypeProvider.CALLABLE.equals(((PyClassLikeType)expected).getClassQName())
477              ? Optional.of(actual.isCallable())
478              : Optional.empty();
479     }
480
481     if (expected.isCallable() && actual.isCallable()) {
482       final TypeEvalContext context = matchContext.context;
483       final List<PyCallableParameter> expectedParameters = expected.getParameters(context);
484       final List<PyCallableParameter> actualParameters = actual.getParameters(context);
485       if (expectedParameters != null && actualParameters != null) {
486         final int size = Math.min(expectedParameters.size(), actualParameters.size());
487         for (int i = 0; i < size; i++) {
488           final PyCallableParameter expectedParam = expectedParameters.get(i);
489           final PyCallableParameter actualParam = actualParameters.get(i);
490           // TODO: Check named and star params, not only positional ones
491           if (expectedParam.isSelf() && actualParam.isSelf()) {
492             if (!match(expectedParam.getType(context), actualParam.getType(context), matchContext).orElse(true)) {
493               return Optional.of(false);
494             }
495           }
496           else {
497             final PyType actualParamType =
498               actualParam.isPositionalContainer() && couldBeMappedOntoPositionalContainer(expectedParam)
499               ? actualParam.getArgumentType(context)
500               : actualParam.getType(context);
501
502             // actual callable type could accept more general parameter type
503             if (!match(actualParamType, expectedParam.getType(context), matchContext.reverseSubstitutions()).orElse(true)) {
504               return Optional.of(false);
505             }
506           }
507         }
508       }
509       if (!match(expected.getReturnType(context), getActualReturnType(actual, context), matchContext).orElse(true)) {
510         return Optional.of(false);
511       }
512       return Optional.of(true);
513     }
514     return Optional.empty();
515   }
516
517   private static @Nullable PyType getActualReturnType(@NotNull PyCallableType actual, @NotNull TypeEvalContext context) {
518     PyCallable callable = actual.getCallable();
519     if (callable instanceof PyFunction) {
520       return getReturnTypeToAnalyzeAsCallType((PyFunction)callable, context);
521     }
522     return actual.getReturnType(context);
523   }
524
525   private static boolean couldBeMappedOntoPositionalContainer(@NotNull PyCallableParameter parameter) {
526     if (parameter.isPositionalContainer() || parameter.isKeywordContainer()) return false;
527
528     final var psi = parameter.getParameter();
529     if (psi != null) {
530       final var namedPsi = psi.getAsNamed();
531       if (namedPsi != null && namedPsi.isKeywordOnly()) {
532         return false;
533       }
534     }
535
536     return true;
537   }
538
539   private static boolean consistsOfSameElementNumberTuples(@NotNull PyUnionType unionType, int elementCount) {
540     for (PyType type : unionType.getMembers()) {
541       if (type instanceof PyTupleType) {
542         final PyTupleType tupleType = (PyTupleType)type;
543
544         if (!tupleType.isHomogeneous() && elementCount != tupleType.getElementCount()) {
545           return false;
546         }
547       }
548       else {
549         return false;
550       }
551     }
552
553     return true;
554   }
555
556   private static boolean substituteExpectedElementsWithUnions(@NotNull PyTupleType expected,
557                                                               int elementCount,
558                                                               @NotNull PyUnionType actual,
559                                                               @NotNull MatchContext context) {
560     for (int i = 0; i < elementCount; i++) {
561       final int currentIndex = i;
562
563       final PyType elementType = PyUnionType.union(
564         StreamEx
565           .of(actual.getMembers())
566           .select(PyTupleType.class)
567           .map(type -> type.getElementType(currentIndex))
568           .toList()
569       );
570
571       if (!match(expected.getElementType(i), elementType, context).orElse(true)) {
572         return false;
573       }
574     }
575
576     return true;
577   }
578
579   private static boolean matchGenerics(@NotNull PyCollectionType expected, @NotNull PyType actual, @NotNull MatchContext context) {
580     // TODO: Match generic parameters based on the correspondence between the generic parameters of subClass and its base classes
581     final List<PyType> superElementTypes = expected.getElementTypes();
582     final PyCollectionType actualCollectionType = as(actual, PyCollectionType.class);
583     final List<PyType> subElementTypes = actualCollectionType != null ?
584                                          actualCollectionType.getElementTypes() :
585                                          Collections.emptyList();
586     for (int i = 0; i < superElementTypes.size(); i++) {
587       final PyType subElementType = i < subElementTypes.size() ? subElementTypes.get(i) : null;
588       if (!match(superElementTypes.get(i), subElementType, context).orElse(true)) {
589         return false;
590       }
591     }
592     return true;
593   }
594
595   private static boolean matchNumericTypes(PyType expected, PyType actual) {
596     if (expected instanceof PyClassType && actual instanceof PyClassType) {
597       final String superName = ((PyClassType)expected).getPyClass().getName();
598       final String subName = ((PyClassType)actual).getPyClass().getName();
599       final boolean subIsBool = "bool".equals(subName);
600       final boolean subIsInt = PyNames.TYPE_INT.equals(subName);
601       final boolean subIsLong = PyNames.TYPE_LONG.equals(subName);
602       final boolean subIsFloat = "float".equals(subName);
603       final boolean subIsComplex = "complex".equals(subName);
604       if (superName == null || subName == null ||
605           superName.equals(subName) ||
606           (PyNames.TYPE_INT.equals(superName) && subIsBool) ||
607           ((PyNames.TYPE_LONG.equals(superName) || PyNames.ABC_INTEGRAL.equals(superName)) && (subIsBool || subIsInt)) ||
608           (("float".equals(superName) || PyNames.ABC_REAL.equals(superName)) && (subIsBool || subIsInt || subIsLong)) ||
609           (("complex".equals(superName) || PyNames.ABC_COMPLEX.equals(superName)) && (subIsBool || subIsInt || subIsLong || subIsFloat)) ||
610           (PyNames.ABC_NUMBER.equals(superName) && (subIsBool || subIsInt || subIsLong || subIsFloat || subIsComplex))) {
611         return true;
612       }
613     }
614     return false;
615   }
616
617   public static boolean isUnknown(@Nullable PyType type, @NotNull TypeEvalContext context) {
618     return isUnknown(type, true, context);
619   }
620
621   public static boolean isUnknown(@Nullable PyType type, boolean genericsAreUnknown, @NotNull TypeEvalContext context) {
622     if (type == null || (genericsAreUnknown && type instanceof PyGenericType)) {
623       return true;
624     }
625     if (type instanceof PyFunctionType) {
626       final PyCallable callable = ((PyFunctionType)type).getCallable();
627       if (callable instanceof PyDecoratable &&
628           PyKnownDecoratorUtil.hasUnknownOrChangingReturnTypeDecorator((PyDecoratable)callable, context)) {
629         return true;
630       }
631     }
632     if (type instanceof PyUnionType) {
633       final PyUnionType union = (PyUnionType)type;
634       for (PyType t : union.getMembers()) {
635         if (isUnknown(t, genericsAreUnknown, context)) {
636           return true;
637         }
638       }
639     }
640     return false;
641   }
642
643   public static boolean hasGenerics(@Nullable PyType type, @NotNull TypeEvalContext context) {
644     final Set<PyGenericType> collected = new HashSet<>();
645     collectGenerics(type, context, collected, new HashSet<>());
646     return !collected.isEmpty();
647   }
648
649   private static void collectGenerics(@Nullable PyType type, @NotNull TypeEvalContext context, @NotNull Set<? super PyGenericType> collected,
650                                       @NotNull Set<? super PyType> visited) {
651     if (visited.contains(type)) {
652       return;
653     }
654     visited.add(type);
655     if (type instanceof PyGenericType) {
656       collected.add((PyGenericType)type);
657     }
658     else if (type instanceof PyUnionType) {
659       final PyUnionType union = (PyUnionType)type;
660       for (PyType t : union.getMembers()) {
661         collectGenerics(t, context, collected, visited);
662       }
663     }
664     else if (type instanceof PyTupleType) {
665       final PyTupleType tuple = (PyTupleType)type;
666       final int n = tuple.isHomogeneous() ? 1 : tuple.getElementCount();
667       for (int i = 0; i < n; i++) {
668         collectGenerics(tuple.getElementType(i), context, collected, visited);
669       }
670     }
671     else if (type instanceof PyCollectionType) {
672       final PyCollectionType collection = (PyCollectionType)type;
673       for (PyType elementType : collection.getElementTypes()) {
674         collectGenerics(elementType, context, collected, visited);
675       }
676     }
677     else if (type instanceof PyCallableType && !(type instanceof PyClassLikeType)) {
678       final PyCallableType callable = (PyCallableType)type;
679       final List<PyCallableParameter> parameters = callable.getParameters(context);
680       if (parameters != null) {
681         for (PyCallableParameter parameter : parameters) {
682           if (parameter != null) {
683             collectGenerics(parameter.getType(context), context, collected, visited);
684           }
685         }
686       }
687       collectGenerics(callable.getReturnType(context), context, collected, visited);
688     }
689   }
690
691   @Nullable
692   public static PyType substitute(@Nullable PyType type, @NotNull Map<PyGenericType, PyType> substitutions,
693                                   @NotNull TypeEvalContext context) {
694     if (hasGenerics(type, context)) {
695       if (type instanceof PyGenericType) {
696         final PyGenericType typeVar = (PyGenericType)type;
697         PyType substitution = substitutions.get(typeVar);
698         if (substitution == null) {
699           if (!typeVar.isDefinition()) {
700             final PyInstantiableType<?> classType = as(substitutions.get(typeVar.toClass()), PyInstantiableType.class);
701             if (classType != null) {
702               substitution = classType.toInstance();
703             }
704           }
705           else {
706             final PyInstantiableType<?> instanceType = as(substitutions.get(typeVar.toInstance()), PyInstantiableType.class);
707             if (instanceType != null) {
708               substitution = instanceType.toClass();
709             }
710           }
711         }
712         if (substitution instanceof PyGenericType && !typeVar.equals(substitution) && substitutions.containsKey(substitution)) {
713           return substitute(substitution, substitutions, context);
714         }
715         return substitution;
716       }
717       else if (type instanceof PyUnionType) {
718         return ((PyUnionType)type).map(member -> substitute(member, substitutions, context));
719       }
720       else if (type instanceof PyCollectionTypeImpl) {
721         final PyCollectionTypeImpl collection = (PyCollectionTypeImpl)type;
722         final List<PyType> elementTypes = collection.getElementTypes();
723         final List<PyType> substitutes = new ArrayList<>();
724         for (PyType elementType : elementTypes) {
725           substitutes.add(substitute(elementType, substitutions, context));
726         }
727         return new PyCollectionTypeImpl(collection.getPyClass(), collection.isDefinition(), substitutes);
728       }
729       else if (type instanceof PyTupleType) {
730         final PyTupleType tupleType = (PyTupleType)type;
731         final PyClass tupleClass = tupleType.getPyClass();
732
733         final List<PyType> oldElementTypes = tupleType.isHomogeneous()
734                                              ? Collections.singletonList(tupleType.getIteratedItemType())
735                                              : tupleType.getElementTypes();
736
737         final List<PyType> newElementTypes =
738           ContainerUtil.map(oldElementTypes, elementType -> substitute(elementType, substitutions, context));
739
740         return new PyTupleType(tupleClass, newElementTypes, tupleType.isHomogeneous());
741       }
742       else if (type instanceof PyCallableType && !(type instanceof PyClassLikeType)) {
743         final PyCallableType callable = (PyCallableType)type;
744         List<PyCallableParameter> substParams = null;
745         final List<PyCallableParameter> parameters = callable.getParameters(context);
746         if (parameters != null) {
747           substParams = new ArrayList<>();
748           for (PyCallableParameter parameter : parameters) {
749             final PyType substType = substitute(parameter.getType(context), substitutions, context);
750             final PyParameter psi = parameter.getParameter();
751             final PyCallableParameter subst = psi != null ?
752                                               PyCallableParameterImpl.psi(psi, substType) :
753                                               PyCallableParameterImpl.nonPsi(parameter.getName(), substType, parameter.getDefaultValue());
754             substParams.add(subst);
755           }
756         }
757         final PyType substResult = substitute(callable.getReturnType(context), substitutions, context);
758         return new PyCallableTypeImpl(substParams, substResult);
759       }
760     }
761     return type;
762   }
763
764   @Nullable
765   public static Map<PyGenericType, PyType> unifyGenericCall(@Nullable PyExpression receiver,
766                                                             @NotNull Map<PyExpression, PyCallableParameter> arguments,
767                                                             @NotNull TypeEvalContext context) {
768     final Map<PyGenericType, PyType> substitutions = unifyReceiver(receiver, context);
769     for (Map.Entry<PyExpression, PyCallableParameter> entry : getRegularMappedParameters(arguments).entrySet()) {
770       final PyCallableParameter paramWrapper = entry.getValue();
771       final PyType expectedType = paramWrapper.getArgumentType(context);
772       PyType actualType = PyLiteralType.Companion.promoteToLiteral(entry.getKey(), expectedType, context);
773       if (paramWrapper.isSelf()) {
774         // TODO find out a better way to pass the corresponding function inside
775         final PyParameter param = paramWrapper.getParameter();
776         final PyFunction function = as(ScopeUtil.getScopeOwner(param), PyFunction.class);
777         if (function != null && function.getModifier() == PyFunction.Modifier.CLASSMETHOD) {
778           actualType = PyTypeUtil.toStream(actualType)
779             .select(PyClassLikeType.class)
780             .map(PyClassLikeType::toClass)
781             .select(PyType.class)
782             .foldLeft(PyUnionType::union)
783             .orElse(actualType);
784         }
785         else if (PyUtil.isInitMethod(function)) {
786           actualType = PyTypeUtil.toStream(actualType)
787             .select(PyInstantiableType.class)
788             .map(PyInstantiableType::toInstance)
789             .select(PyType.class)
790             .foldLeft(PyUnionType::union)
791             .orElse(actualType);
792         }
793       }
794       if (!match(expectedType, actualType, context, substitutions)) {
795         return null;
796       }
797     }
798     if (!matchContainer(getMappedPositionalContainer(arguments), getArgumentsMappedToPositionalContainer(arguments), substitutions,
799                         context)) {
800       return null;
801     }
802     if (!matchContainer(getMappedKeywordContainer(arguments), getArgumentsMappedToKeywordContainer(arguments), substitutions, context)) {
803       return null;
804     }
805     return substitutions;
806   }
807
808   private static boolean matchContainer(@Nullable PyCallableParameter container, @NotNull List<? extends PyExpression> arguments,
809                                         @NotNull Map<PyGenericType, PyType> substitutions, @NotNull TypeEvalContext context) {
810     if (container == null) {
811       return true;
812     }
813     final List<PyType> types = ContainerUtil.map(arguments, context::getType);
814     return match(container.getArgumentType(context), PyUnionType.union(types), context, substitutions);
815   }
816
817   @NotNull
818   public static Map<PyGenericType, PyType> unifyReceiver(@Nullable PyExpression receiver, @NotNull TypeEvalContext context) {
819     final Map<PyGenericType, PyType> substitutions = new LinkedHashMap<>();
820     // Collect generic params of object type
821     final Set<PyGenericType> generics = new LinkedHashSet<>();
822     final PyType qualifierType = receiver != null ? context.getType(receiver) : null;
823     collectGenerics(qualifierType, context, generics, new HashSet<>());
824     for (PyGenericType t : generics) {
825       substitutions.put(t, t);
826     }
827     if (qualifierType != null) {
828       for (PyClassType type : PyTypeUtil.toStream(qualifierType).select(PyClassType.class)) {
829         for (PyTypeProvider provider : PyTypeProvider.EP_NAME.getExtensionList()) {
830           final PyType genericType = provider.getGenericType(type.getPyClass(), context);
831           final Set<PyGenericType> providedTypeGenerics = new LinkedHashSet<>();
832
833           if (genericType != null) {
834             match(genericType, type, context, substitutions);
835             collectGenerics(genericType, context, providedTypeGenerics, new HashSet<>());
836           }
837
838           for (Map.Entry<PyType, PyType> entry : provider.getGenericSubstitutions(type.getPyClass(), context).entrySet()) {
839             final PyGenericType genericKey = as(entry.getKey(), PyGenericType.class);
840             final PyType value = entry.getValue();
841
842             if (genericKey != null &&
843                 value != null &&
844                 !substitutions.containsKey(genericKey) &&
845                 !providedTypeGenerics.contains(genericKey)) {
846               substitutions.put(genericKey, value);
847             }
848           }
849         }
850       }
851     }
852
853     replaceUnresolvedGenericsWithAny(substitutions);
854     return substitutions;
855   }
856
857   private static void replaceUnresolvedGenericsWithAny(@NotNull Map<PyGenericType, PyType> substitutions) {
858     final List<PyType> unresolvedGenerics =
859       ContainerUtil.filter(substitutions.values(), type -> type instanceof PyGenericType && !substitutions.containsKey(type));
860
861     for (PyType unresolvedGeneric : unresolvedGenerics) {
862       substitutions.put((PyGenericType)unresolvedGeneric, null);
863     }
864   }
865
866   private static boolean matchClasses(@Nullable PyClass superClass, @Nullable PyClass subClass, @NotNull TypeEvalContext context) {
867     if (superClass == null ||
868         subClass == null ||
869         subClass.isSubclass(superClass, context) ||
870         PyABCUtil.isSubclass(subClass, superClass, context) ||
871         isStrUnicodeMatch(subClass, superClass) ||
872         isBytearrayBytesStringMatch(subClass, superClass) ||
873         PyUtil.hasUnresolvedAncestors(subClass, context)) {
874       return true;
875     }
876     else {
877       final String superName = superClass.getName();
878       return superName != null && superName.equals(subClass.getName());
879     }
880   }
881
882   private static boolean isStrUnicodeMatch(@NotNull PyClass subClass, @NotNull PyClass superClass) {
883     // TODO: Check for subclasses as well
884     return PyNames.TYPE_STR.equals(subClass.getName()) && PyNames.TYPE_UNICODE.equals(superClass.getName());
885   }
886
887   private static boolean isBytearrayBytesStringMatch(@NotNull PyClass subClass, @NotNull PyClass superClass) {
888     if (!PyNames.TYPE_BYTEARRAY.equals(subClass.getName())) return false;
889
890     final PsiFile subClassFile = subClass.getContainingFile();
891
892     final boolean isPy2 = subClassFile instanceof PyiFile
893                           ? PythonRuntimeService.getInstance().getLanguageLevelForSdk(PythonSdkUtil.findPythonSdk(subClassFile)).isPython2()
894                           : LanguageLevel.forElement(subClass).isPython2();
895
896     final String superClassName = superClass.getName();
897     return isPy2 && PyNames.TYPE_STR.equals(superClassName) || !isPy2 && PyNames.TYPE_BYTES.equals(superClassName);
898   }
899
900   @Nullable
901   public static Boolean isCallable(@Nullable PyType type) {
902     if (type == null) {
903       return null;
904     }
905     if (type instanceof PyUnionType) {
906       return isUnionCallable((PyUnionType)type);
907     }
908     if (type instanceof PyCallableType) {
909       return ((PyCallableType)type).isCallable();
910     }
911     if (type instanceof PyStructuralType && ((PyStructuralType)type).isInferredFromUsages()) {
912       return true;
913     }
914     if (type instanceof PyGenericType) {
915       if (((PyGenericType)type).isDefinition()) {
916         return true;
917       }
918
919       return isCallable(((PyGenericType)type).getBound());
920     }
921     return false;
922   }
923
924   /**
925    * If at least one is callable -- it is callable.
926    * If at least one is unknown -- it is unknown.
927    * It is false otherwise.
928    */
929   @Nullable
930   private static Boolean isUnionCallable(@NotNull final PyUnionType type) {
931     for (final PyType member : type.getMembers()) {
932       final Boolean callable = isCallable(member);
933       if (callable == null) {
934         return null;
935       }
936       if (callable) {
937         return true;
938       }
939     }
940     return false;
941   }
942
943   public static boolean definesGetAttr(@NotNull PyFile file, @NotNull TypeEvalContext context) {
944     if (file instanceof PyTypedElement) {
945       final PyType type = context.getType((PyTypedElement)file);
946       if (type != null) {
947         return resolveTypeMember(type, PyNames.GETATTR, context) != null;
948       }
949     }
950
951     return false;
952   }
953
954   public static boolean overridesGetAttr(@NotNull PyClass cls, @NotNull TypeEvalContext context) {
955     final PyType type = context.getType(cls);
956     if (type != null) {
957       if (resolveTypeMember(type, PyNames.GETATTR, context) != null) {
958         return true;
959       }
960       final PsiElement method = resolveTypeMember(type, PyNames.GETATTRIBUTE, context);
961       if (method != null && !PyBuiltinCache.getInstance(cls).isBuiltin(method)) {
962         return true;
963       }
964     }
965     return false;
966   }
967
968   @Nullable
969   private static PsiElement resolveTypeMember(@NotNull PyType type, @NotNull String name, @NotNull TypeEvalContext context) {
970     final PyResolveContext resolveContext = PyResolveContext.defaultContext().withTypeEvalContext(context);
971     final List<? extends RatedResolveResult> results = type.resolveMember(name, null, AccessDirection.READ, resolveContext);
972     return !ContainerUtil.isEmpty(results) ? results.get(0).getElement() : null;
973   }
974
975   @Nullable
976   public static PyType getTargetTypeFromTupleAssignment(@NotNull PyTargetExpression target,
977                                                         @NotNull PyTupleExpression parentTuple,
978                                                         @NotNull PyType assignedType,
979                                                         @NotNull TypeEvalContext context) {
980     if (assignedType instanceof PyTupleType) {
981       return getTargetTypeFromTupleAssignment(target, parentTuple, (PyTupleType)assignedType);
982     }
983     else if (assignedType instanceof PyClassLikeType) {
984       return StreamEx
985         .of(((PyClassLikeType)assignedType).getAncestorTypes(context))
986         .select(PyNamedTupleType.class)
987         .findFirst()
988         .map(t -> getTargetTypeFromTupleAssignment(target, parentTuple, t))
989         .orElse(null);
990     }
991
992     return null;
993   }
994
995   @Nullable
996   public static PyType getTargetTypeFromTupleAssignment(@NotNull PyTargetExpression target, @NotNull PyTupleExpression parentTuple,
997                                                         @NotNull PyTupleType assignedTupleType) {
998     final int count = assignedTupleType.getElementCount();
999     final PyExpression[] elements = parentTuple.getElements();
1000     if (elements.length == count || assignedTupleType.isHomogeneous()) {
1001       final int index = ArrayUtil.indexOf(elements, target);
1002       if (index >= 0) {
1003         return assignedTupleType.getElementType(index);
1004       }
1005       for (int i = 0; i < count; i++) {
1006         PyExpression element = elements[i];
1007         while (element instanceof PyParenthesizedExpression) {
1008           element = ((PyParenthesizedExpression)element).getContainedExpression();
1009         }
1010         if (element instanceof PyTupleExpression) {
1011           final PyType elementType = assignedTupleType.getElementType(i);
1012           if (elementType instanceof PyTupleType) {
1013             final PyType result = getTargetTypeFromTupleAssignment(target, (PyTupleExpression)element, (PyTupleType)elementType);
1014             if (result != null) {
1015               return result;
1016             }
1017           }
1018         }
1019       }
1020     }
1021     return null;
1022   }
1023
1024   private static class MatchContext {
1025
1026     @NotNull
1027     private final TypeEvalContext context;
1028
1029     @NotNull
1030     private final Map<PyGenericType, PyType> substitutions; // mutable
1031
1032     private final boolean reversedSubstitutions;
1033
1034     MatchContext(@NotNull TypeEvalContext context,
1035                  @NotNull Map<PyGenericType, PyType> substitutions) {
1036       this(context, substitutions, false);
1037     }
1038
1039     private MatchContext(@NotNull TypeEvalContext context,
1040                          @NotNull Map<PyGenericType, PyType> substitutions,
1041                          boolean reversedSubstitutions) {
1042       this.context = context;
1043       this.substitutions = substitutions;
1044       this.reversedSubstitutions = reversedSubstitutions;
1045     }
1046
1047     @NotNull
1048     public MatchContext reverseSubstitutions() {
1049       return new MatchContext(context, substitutions, !reversedSubstitutions);
1050     }
1051   }
1052 }