Merge remote-tracking branch 'origin/master' into mikhail.golubev/py-attribute-inference
authorMikhail Golubev <mikhail.golubev@jetbrains.com>
Thu, 25 Dec 2014 12:18:08 +0000 (15:18 +0300)
committerMikhail Golubev <mikhail.golubev@jetbrains.com>
Thu, 25 Dec 2014 12:32:43 +0000 (15:32 +0300)
Conflicts:
python/src/com/jetbrains/python/psi/impl/PyClassImpl.java
python/src/com/jetbrains/python/psi/impl/PyNamedParameterImpl.java
python/src/com/jetbrains/python/psi/impl/PyReferenceExpressionImpl.java
python/src/com/jetbrains/python/psi/impl/references/PyQualifiedReference.java
python/testSrc/com/jetbrains/python/PythonCompletionTest.java
python/testSrc/com/jetbrains/python/codeInsight/PyClassMROTest.java

1  2 
python/src/META-INF/python-core.xml
python/src/com/jetbrains/python/psi/impl/PyClassImpl.java
python/src/com/jetbrains/python/psi/impl/references/PyQualifiedReference.java
python/src/com/jetbrains/python/psi/impl/stubs/PyClassElementType.java
python/src/com/jetbrains/python/psi/resolve/ResolveImportUtil.java
python/src/com/jetbrains/python/psi/types/PyTypeFromUsedAttributesHelper.java
python/testSrc/com/jetbrains/python/PyTypeFromUsedAttributesTest.java
python/testSrc/com/jetbrains/python/PythonCompletionTest.java
python/testSrc/com/jetbrains/python/codeInsight/PyClassMROTest.java

index bdc4393bf7118f8da7d19d70d76693c8e2b78575,b00b859243be3df53421b4d4ac0591b37c7e63f9..8d78b2ad9e3191f9d17fd4f50411eda21f8c14f8
@@@ -95,8 -95,8 +95,9 @@@
      <stubIndex implementation="com.jetbrains.python.psi.stubs.PyVariableNameIndex"/>
      <stubIndex implementation="com.jetbrains.python.psi.stubs.PyInstanceAttributeIndex"/>
      <stubIndex implementation="com.jetbrains.python.psi.stubs.PyDecoratorStubIndex"/>
 +    <stubIndex implementation="com.jetbrains.python.psi.stubs.PyClassAttributesIndex"/>
      <fileBasedIndex implementation="com.jetbrains.python.psi.stubs.PyModuleNameIndex"/>
+     <fileBasedIndex implementation="com.jetbrains.python.psi.stubs.PySetuptoolsNamespaceIndex"/>
  
      <declarationRangeHandler key="com.jetbrains.python.psi.PyClass"
                               implementationClass="com.jetbrains.python.codeInsight.PyDeclarationRangeHandler"/>
index 0fa1b0d740094809be91b834d0adce6352404b70,c03fe346b6e365d8b56884e9150520cb450aa1a2..99d9e6cd7a157b7c329c4fd44b5a824e6add7a16
@@@ -61,8 -63,13 +63,14 @@@ import static com.intellij.openapi.util
   * @author yole
   */
  public class PyClassImpl extends PyBaseElementImpl<PyClassStub> implements PyClass {
+   public static class MROException extends Exception {
+     public MROException(String s) {
+       super(s);
+     }
+   }
    public static final PyClass[] EMPTY_ARRAY = new PyClassImpl[0];
 +  private static final Object EVALUATING = new Object();
  
    private List<PyTargetExpression> myInstanceAttributes;
    private final NotNullLazyValue<CachedValue<Boolean>> myNewStyle = new NotNullLazyValue<CachedValue<Boolean>>() {
        PyClassLikeType head = null; // to keep compiler happy; really head is assigned in the loop at least once.
        for (List<PyClassLikeType> seq : nonBlankSequences) {
          head = seq.get(0);
 -        boolean head_in_tails = false;
 -        for (List<PyClassLikeType> tail_seq : nonBlankSequences) {
 -          if (tail_seq.indexOf(head) > 0) { // -1 is not found, 0 is head, >0 is tail.
 -            head_in_tails = true;
+         if (head == null) {
+           seq.remove(0);
+           found = true;
+           break;
+         }
 +        boolean headInTails = false;
 +        for (List<PyClassLikeType> tailSeq : nonBlankSequences) {
 +          if (tailSeq.indexOf(head) > 0) { // -1 is not found, 0 is head, >0 is tail.
 +            headInTails = true;
              break;
            }
          }
      } // we either return inside the loop or die by assertion
    }
  
 -  @NotNull
 -  private static List<PyClassLikeType> mroLinearize(@NotNull PyClassLikeType type, @NotNull Set<PyClassLikeType> seen, boolean addThisType,
 +
-   private static List<PyClassLikeType> mroLinearize(@NotNull PyClassLikeType type, boolean addThisType, @NotNull TypeEvalContext context) {
++  private static List<PyClassLikeType> mroLinearize(@NotNull PyClassLikeType type,
++                                                    boolean addThisType,
+                                                     @NotNull TypeEvalContext context) throws MROException {
 -    if (seen.contains(type)) {
 +    return mroLinearize(type, addThisType, context, new HashMap<PyClassLikeType, Object>());
 +  }
 +
 +  @NotNull
 +  private static List<PyClassLikeType> mroLinearize(@NotNull PyClassLikeType type, boolean addThisType,
 +                                                    @NotNull TypeEvalContext context,
-                                                     @NotNull Map<PyClassLikeType, Object> cache) {
++                                                    @NotNull Map<PyClassLikeType, Object> cache) throws MROException {
 +    final Object computed = cache.get(type);
 +    if (computed == EVALUATING) {
-       throw new IllegalStateException("Circular class inheritance");
+       throw new MROException("Circular class inheritance");
      }
 -    final List<PyClassLikeType> bases = type.getSuperClassTypes(context);
 -    List<List<PyClassLikeType>> lines = new ArrayList<List<PyClassLikeType>>();
 -    for (PyClassLikeType base : bases) {
 -      if (base != null) {
 -        final Set<PyClassLikeType> newSeen = new HashSet<PyClassLikeType>(seen);
 -        newSeen.add(type);
 -        List<PyClassLikeType> lin = mroLinearize(base, newSeen, true, context);
 -        if (!lin.isEmpty()) lines.add(lin);
 +    if (computed != null) {
 +      //noinspection unchecked
 +      return (List<PyClassLikeType>)computed;
 +    }
 +    cache.put(type, EVALUATING);
 +    List<PyClassLikeType> result = null;
 +    try {
 +      final List<PyClassLikeType> bases = type.getSuperClassTypes(context);
 +      final List<List<PyClassLikeType>> lines = new ArrayList<List<PyClassLikeType>>();
 +      for (PyClassLikeType base : bases) {
 +        if (base != null) {
 +          final List<PyClassLikeType> baseClassMRO = mroLinearize(base, true, context, cache);
 +          if (!baseClassMRO.isEmpty()) {
 +            lines.add(baseClassMRO);
 +          }
 +        }
 +      }
 +      if (!bases.isEmpty()) {
 +        lines.add(bases);
 +      }
 +      result = mroMerge(lines);
 +      if (addThisType) {
 +        result.add(0, type);
        }
      }
 -    if (!bases.isEmpty()) {
 -      lines.add(bases);
 -    }
 -    List<PyClassLikeType> result = mroMerge(lines);
 -    if (addThisType) {
 -      result.add(0, type);
 +    finally {
 +      cache.put(type, result);
      }
      return result;
    }
    }
  
    @NotNull
-   private List<PyClassLikeType> getMROAncestorTypes(@NotNull TypeEvalContext context) {
+   private List<PyClassLikeType> getMROAncestorTypes(@NotNull TypeEvalContext context) throws MROException {
      final PyType thisType = context.getType(this);
      if (thisType instanceof PyClassLikeType) {
-       try {
-         return mroLinearize((PyClassLikeType)thisType, false, context);
+       final PyClassLikeType thisClassLikeType = (PyClassLikeType)thisType;
 -      final List<PyClassLikeType> ancestorTypes = mroLinearize(thisClassLikeType, new HashSet<PyClassLikeType>(), false, context);
++      final List<PyClassLikeType> ancestorTypes = mroLinearize(thisClassLikeType, false, context, new HashMap<PyClassLikeType, Object>());
+       if (isOverriddenMRO(ancestorTypes, context)) {
+         ancestorTypes.add(null);
+       }
+       return ancestorTypes;
+     }
+     else {
+       return Collections.emptyList();
+     }
+   }
+   private boolean isOverriddenMRO(@NotNull List<PyClassLikeType> ancestorTypes, @NotNull TypeEvalContext context) {
+     final List<PyClass> classes = new ArrayList<PyClass>();
+     classes.add(this);
+     for (PyClassLikeType ancestorType : ancestorTypes) {
+       if (ancestorType instanceof PyClassType) {
+         final PyClassType classType = (PyClassType)ancestorType;
+         classes.add(classType.getPyClass());
        }
-       catch (IllegalStateException ignored) {
+     }
+     final PyClass typeClass = PyBuiltinCache.getInstance(this).getClass("type");
+     for (PyClass cls : classes) {
+       final PyType metaClassType = cls.getMetaClassType(context);
+       if (metaClassType instanceof PyClassType) {
+         final PyClass metaClass = ((PyClassType)metaClassType).getPyClass();
+         final PyFunction mroMethod = metaClass.findMethodByName(PyNames.MRO, true);
+         if (mroMethod != null) {
+           final PyClass mroClass = mroMethod.getContainingClass();
+           if (mroClass != null && mroClass != typeClass) {
+             return true;
+           }
+         }
        }
      }
-     return Collections.emptyList();
+     return false;
    }
  
    @NotNull
index f08485d7efe46ec78789f74c730be5a2d1d2b51f,070ee1165c3652a107072451c135d52d90474e5b..81215f67f96ff57c0005d377e00f964aad20fb01
@@@ -105,7 -105,9 +105,9 @@@ public class PyQualifiedReference exten
        }
      }
  
-     if (qualifierType == null && myContext.allowImplicits() && canQualifyAnImplicitName(qualifier)) {
+     if ((PyTypeChecker.isUnknown(qualifierType) ||
+          (qualifierType instanceof PyStructuralType && ((PyStructuralType)qualifierType).isInferredFromUsages())) &&
 -        myContext.allowImplicits() && canQualifyAnImplicitName(qualifier, qualifierType)) {
++        myContext.allowImplicits() && canQualifyAnImplicitName(qualifier)) {
        addImplicitResolveResults(referencedName, ret);
      }
  
index 156fb551e5c26761bfc1fe02a6b6d402b8a669d1,0000000000000000000000000000000000000000..97fb75b40ceb7a2a5823f05fe41c4f0e94595c45
mode 100644,000000..100644
--- /dev/null
@@@ -1,361 -1,0 +1,361 @@@
-     if (!ENABLED || !myContext.allowLocalUsages(expression)) {
 +package com.jetbrains.python.psi.types;
 +
 +import com.google.common.annotations.VisibleForTesting;
 +import com.google.common.collect.*;
 +import com.intellij.openapi.diagnostic.Logger;
 +import com.intellij.psi.PsiFile;
 +import com.intellij.psi.PsiFileSystemItem;
 +import com.intellij.psi.PsiNamedElement;
 +import com.intellij.psi.PsiReference;
 +import com.intellij.psi.search.ProjectScope;
 +import com.intellij.psi.util.QualifiedName;
 +import com.intellij.util.Function;
 +import com.intellij.util.containers.ContainerUtil;
 +import com.jetbrains.python.PyNames;
 +import com.jetbrains.python.codeInsight.controlflow.ScopeOwner;
 +import com.jetbrains.python.codeInsight.dataflow.scope.ScopeUtil;
 +import com.jetbrains.python.codeInsight.userSkeletons.PyUserSkeletonsUtil;
 +import com.jetbrains.python.psi.*;
 +import com.jetbrains.python.psi.impl.PyBuiltinCache;
 +import com.jetbrains.python.psi.stubs.PyClassAttributesIndex;
 +import org.jetbrains.annotations.NotNull;
 +import org.jetbrains.annotations.Nullable;
 +
 +import java.util.*;
 +
 +import static com.jetbrains.python.psi.resolve.QualifiedNameFinder.findShortestImportableQName;
 +
 +/**
 + * @author Mikhail Golubev
 + */
 +public class PyTypeFromUsedAttributesHelper {
 +  public static final int MAX_CANDIDATES = 5;
 +  // Not final so it can be changed in debugger
 +  private static boolean ENABLED = Boolean.parseBoolean(System.getProperty("py.infer.types.from.used.attributes", "true"));
 +
 +  private static final Set<String> COMMON_OBJECT_ATTRIBUTES = ImmutableSet.of(
 +    "__init__",
 +    "__new__",
 +    "__str__",
 +    "__repr__", // TODO __module__ actually belongs to object's metaclass, it's not available to instances
 +    "__doc__",
 +    "__class__",
 +    "__module__",
 +    "__dict__"
 +  );
 +
 +  private static final Logger LOG = Logger.getInstance(PyTypeFromUsedAttributesHelper.class);
 +
 +  private final TypeEvalContext myContext;
 +  private final Map<PyClass, Set<PyClass>> myAncestorsCache = Maps.newHashMap();
 +
 +  /**
 +   * Attempts to guess the type of a given expression based on what attributes (including special names) were accessed on it. If several
 +   * types fit then their union is returned. Suggested classes are ordered according to their
 +   * {@link PyTypeFromUsedAttributesHelper.Priority}. Currently at most {@link #MAX_CANDIDATES} can be returned in a union.
 +   */
 +  @Nullable
 +  public static PyType getType(@NotNull PyExpression expression, @NotNull TypeEvalContext context) {
 +    return new PyTypeFromUsedAttributesHelper(context).getType(expression);
 +  }
 +
 +  private PyTypeFromUsedAttributesHelper(@NotNull TypeEvalContext context) {
 +    myContext = context;
 +  }
 +
 +  @Nullable
 +  private PyType getType(@NotNull PyExpression expression) {
++    if (!ENABLED || !myContext.allowCallContext(expression)) {
 +      return null;
 +    }
 +    final long startInference = System.currentTimeMillis();
 +    final Set<String> seenAttrs = collectUsedAttributes(expression);
 +    LOG.debug(String.format("Attempting to infer type for expression: %s. Used attributes: %s", expression.getText(), seenAttrs));
 +    final Set<PyClass> allCandidates = suggestCandidateClasses(expression, seenAttrs);
 +
 +    final long startPrioritization = System.currentTimeMillis();
 +    final List<CandidateClass> bestCandidates = prepareCandidates(allCandidates, expression);
 +    LOG.debug("Total " + (System.currentTimeMillis() - startPrioritization) + " ms to prioritize candidate classes");
 +    LOG.debug("Total " + (System.currentTimeMillis() - startInference) + " ms to infer candidate classes");
 +
 +    return PyUnionType.createWeakType(PyUnionType.union(ContainerUtil.map(bestCandidates, new Function<CandidateClass, PyType>() {
 +      @Override
 +      public PyType fun(CandidateClass cls) {
 +        return new PyClassTypeImpl(cls.myClass, false);
 +      }
 +    })));
 +  }
 +
 +  @NotNull
 +  private Set<PyClass> suggestCandidateClasses(@NotNull final PyExpression expression, @NotNull Set<String> seenAttrs) {
 +    final Set<PyClass> candidates = Sets.newHashSet();
 +    for (String attribute : seenAttrs) {
 +      // Search for some of these attributes like __init__ may produce thousands of candidates in average SDK
 +      // and we probably don't want to confuse user with PyNames.FAKE_OLD_BASE anyway
 +      if (COMMON_OBJECT_ATTRIBUTES.contains(attribute)) {
 +        candidates.add(PyBuiltinCache.getInstance(expression).getClass(PyNames.OBJECT));
 +      }
 +      else {
 +        final Collection<PyClass> declaringClasses = PyClassAttributesIndex.find(attribute, expression.getProject());
 +        LOG.debug("Attribute " + attribute + " is declared in " + declaringClasses.size() + " classes");
 +        candidates.addAll(declaringClasses);
 +      }
 +    }
 +
 +    final Set<PyClass> suitableClasses = Sets.newHashSet();
 +    for (PyClass candidate : candidates) {
 +      if (PyUserSkeletonsUtil.isUnderUserSkeletonsDirectory(candidate.getContainingFile())) {
 +        continue;
 +      }
 +      if (getAllInheritedAttributeNames(candidate).containsAll(seenAttrs)) {
 +        suitableClasses.add(candidate);
 +      }
 +    }
 +
 +    for (PyClass candidate : Lists.newArrayList(suitableClasses)) {
 +      for (PyClass ancestor : getAncestorClassesFast(candidate)) {
 +        if (suitableClasses.contains(ancestor)) {
 +          suitableClasses.remove(candidate);
 +        }
 +      }
 +    }
 +    return Collections.unmodifiableSet(suitableClasses);
 +  }
 +
 +  @NotNull
 +  private static List<CandidateClass> prepareCandidates(@NotNull Set<PyClass> candidates, @NotNull final PyExpression expression) {
 +    final Set<QualifiedName> importQualifiers = collectImportQualifiers(expression.getContainingFile());
 +
 +    final List<CandidateClass> prioritizedCandidates = ContainerUtil.map(candidates, new Function<PyClass, CandidateClass>() {
 +      @Override
 +      public CandidateClass fun(PyClass candidate) {
 +        return new CandidateClass(candidate, findPriority(candidate, expression, importQualifiers));
 +      }
 +    });
 +    Collections.sort(prioritizedCandidates);
 +
 +    final List<CandidateClass> result = Lists.newArrayList();
 +    for (CandidateClass candidate : prioritizedCandidates) {
 +      if (result.size() == MAX_CANDIDATES || candidate.myPriority.compareTo(Priority.PROJECT) >= 0) {
 +        break;
 +      }
 +      result.add(candidate);
 +    }
 +    return Collections.unmodifiableList(result);
 +  }
 +
 +  @NotNull
 +  private static Priority findPriority(@NotNull PyClass candidate, @NotNull PyExpression expression,
 +                                       @NotNull Set<QualifiedName> qualifiers) {
 +    if (PyBuiltinCache.getInstance(expression).isBuiltin(candidate)) {
 +      return Priority.BUILTIN;
 +    }
 +    if (PyUtil.inSameFile(candidate, expression)) {
 +      return Priority.SAME_FILE;
 +    }
 +    final String qualifiedName = candidate.getQualifiedName();
 +    if (qualifiedName != null) {
 +      for (QualifiedName qualifier : qualifiers) {
 +        if (QualifiedName.fromDottedString(qualifiedName).matchesPrefix(qualifier)) {
 +          return Priority.IMPORTED;
 +        }
 +      }
 +    }
 +    if (ProjectScope.getProjectScope(candidate.getProject()).contains(candidate.getContainingFile().getVirtualFile())) {
 +      return Priority.PROJECT;
 +    }
 +    return Priority.OTHER;
 +  }
 +
 +  @VisibleForTesting
 +  @NotNull
 +  public static Set<QualifiedName> collectImportQualifiers(@NotNull PsiFile file) {
 +    final Set<QualifiedName> result = Sets.newHashSet();
 +    if (file instanceof PyFile) {
 +      final PyFile originalModule = (PyFile)file;
 +      for (PyFromImportStatement fromImport : originalModule.getFromImports()) {
 +        if (fromImport.isFromFuture()) {
 +          continue;
 +        }
 +        final PsiFileSystemItem importedModule = PyUtil.as(fromImport.resolveImportSource(), PsiFileSystemItem.class);
 +        if (importedModule == null) {
 +          continue;
 +        }
 +        final QualifiedName qName = findShortestImportableQName(file.getFirstChild(), importedModule.getVirtualFile());
 +        if (qName == null) {
 +          continue;
 +        }
 +        final PyImportElement[] importElements = fromImport.getImportElements();
 +        if (fromImport.isStarImport() || importElements.length == 0) {
 +          result.add(qName);
 +        }
 +        else {
 +          result.addAll(ContainerUtil.map(importElements, new Function<PyImportElement, QualifiedName>() {
 +            @Override
 +            public QualifiedName fun(PyImportElement element) {
 +              final QualifiedName name = element.getImportedQName();
 +              return name != null ? qName.append(name) : qName;
 +            }
 +          }));
 +        }
 +      }
 +      for (PyImportElement normalImport : originalModule.getImportTargets()) {
 +        ContainerUtil.addIfNotNull(result, normalImport.getImportedQName());
 +      }
 +    }
 +    return Collections.unmodifiableSet(result);
 +  }
 +
 +  @NotNull
 +  private Set<String> getAllInheritedAttributeNames(@NotNull PyClass candidate) {
 +    final Set<String> availableAttrs = Sets.newHashSet(getAllDeclaredAttributeNames(candidate));
 +    for (PyClass parent : getAncestorClassesFast(candidate)) {
 +      availableAttrs.addAll(getAllDeclaredAttributeNames(parent));
 +    }
 +    return availableAttrs;
 +  }
 +
 +  @VisibleForTesting
 +  @NotNull
 +  public static Set<String> collectUsedAttributes(@NotNull PyExpression element) {
 +    final QualifiedName qualifiedName;
 +    if (element instanceof PyQualifiedExpression) {
 +      qualifiedName = ((PyQualifiedExpression)element).asQualifiedName();
 +    }
 +    else {
 +      final String elementName = element.getName();
 +      qualifiedName = elementName == null ? null : QualifiedName.fromDottedString(elementName);
 +    }
 +    if (qualifiedName == null) {
 +      return Collections.emptySet();
 +    }
 +    return collectUsedAttributes(element, qualifiedName);
 +  }
 +
 +  @NotNull
 +  private static Set<String> collectUsedAttributes(@NotNull PyExpression anchor, @NotNull final QualifiedName qualifiedName) {
 +    final Set<String> result = Sets.newHashSet();
 +
 +    final PsiReference reference = anchor.getReference();
 +    final ScopeOwner definitionScope = ScopeUtil.getScopeOwner(reference != null ? reference.resolve() : anchor);
 +    for (ScopeOwner scope = ScopeUtil.getScopeOwner(anchor); scope != null; scope = ScopeUtil.getScopeOwner(scope)) {
 +      final ScopeOwner inspectedScope = scope;
 +      scope.accept(new PyRecursiveElementVisitor() {
 +        @Override
 +        public void visitPyElement(PyElement node) {
 +          if (node instanceof ScopeOwner && node != inspectedScope) {
 +            return;
 +          }
 +          if (node instanceof PyQualifiedExpression) {
 +            ContainerUtil.addIfNotNull(result, getAttributeOfQualifier(((PyQualifiedExpression)node), qualifiedName));
 +          }
 +          super.visitPyElement(node);
 +        }
 +      });
 +      if (scope == definitionScope) {
 +        break;
 +      }
 +    }
 +    return result;
 +  }
 +
 +  @Nullable
 +  private static String getAttributeOfQualifier(@NotNull PyQualifiedExpression expression, @NotNull QualifiedName expectedQualifier) {
 +    if (!expression.isQualified()) {
 +      return null;
 +    }
 +    final QualifiedName qualifiedName = expression.asQualifiedName();
 +    if (qualifiedName != null && qualifiedName.removeTail(1).equals(expectedQualifier)) {
 +      return qualifiedName.getLastComponent();
 +    }
 +    return null;
 +  }
 +
 +  /**
 +   * Returns all attributes: methods, class and instance fields that are declared directly in the specified class
 +   * (not taking inheritance into account).
 +   * <p/>
 +   * This method <b>must not</b> access the AST because it is being called during stub indexing.
 +   */
 +  @NotNull
 +  public static List<String> getAllDeclaredAttributeNames(@NotNull PyClass pyClass) {
 +    final List<PsiNamedElement> members = ContainerUtil.<PsiNamedElement>concat(pyClass.getInstanceAttributes(),
 +                                                                                pyClass.getClassAttributes(),
 +                                                                                Arrays.asList(pyClass.getMethods(false)));
 +
 +    return ContainerUtil.mapNotNull(members, new Function<PsiNamedElement, String>() {
 +      @Override
 +      public String fun(PsiNamedElement expression) {
 +        final String attrName = expression.getName();
 +        return attrName != null ? attrName : null;
 +      }
 +    });
 +  }
 +
 +  /**
 +   * A simpler and faster alternative to {@link com.jetbrains.python.psi.impl.PyClassImpl#getAncestorClasses()}.
 +   * The approach used here does not require proper MRO order of ancestors and its performance is greatly improved by reusing
 +   * intermediate results in case of a large class hierarchy.
 +   */
 +  @NotNull
 +  private Set<PyClass> getAncestorClassesFast(@NotNull PyClass pyClass) {
 +    final Set<PyClass> ancestors = myAncestorsCache.get(pyClass);
 +    if (ancestors != null) {
 +      return ancestors;
 +    }
 +    // Sentinel value to prevent infinite recursion
 +    myAncestorsCache.put(pyClass, Collections.<PyClass>emptySet());
 +    final Set<PyClass> result = Sets.newHashSet();
 +    try {
 +      for (final PyClassLikeType baseType : pyClass.getSuperClassTypes(myContext)) {
 +        if (!(baseType instanceof PyClassType)) {
 +          continue;
 +        }
 +        final PyClass baseClass = ((PyClassType)baseType).getPyClass();
 +        result.add(baseClass);
 +        result.addAll(getAncestorClassesFast(baseClass));
 +      }
 +    }
 +    finally {
 +      // May happen in case of cyclic inheritance
 +      result.remove(pyClass);
 +      myAncestorsCache.put(pyClass, Collections.unmodifiableSet(result));
 +    }
 +    return result;
 +  }
 +
 +  private static class CandidateClass implements Comparable<CandidateClass> {
 +    final PyClass myClass;
 +    final Priority myPriority;
 +
 +    public CandidateClass(@NotNull PyClass cls, @NotNull Priority priority) {
 +      myClass = cls;
 +      myPriority = priority;
 +    }
 +
 +    @Override
 +    public int compareTo(@NotNull CandidateClass o) {
 +      // Alphabetical tie-breaker for consistent results
 +      //noinspection ConstantConditions
 +      return ComparisonChain.start()
 +        .compare(myPriority, o.myPriority)
 +        .compare(myClass.getName(), o.myClass.getName())
 +        .result();
 +    }
 +
 +    @Override
 +    public String toString() {
 +      return String.format("ClassCandidate(name='%s' priority=%s)", myClass.getName(), myPriority);
 +    }
 +  }
 +
 +  enum Priority {
 +    BUILTIN,
 +    SAME_FILE,
 +    IMPORTED,
 +    PROJECT,
 +    // TODO How to implement it?
 +    DEPENDENCY,
 +    OTHER
 +  }
 +}
index 6fe3bc6f54384a357f015007def2c5181038458d,0000000000000000000000000000000000000000..2cdea28b20dc9fbdb37706289af68006020f4717
mode 100644,000000..100644
--- /dev/null
@@@ -1,280 -1,0 +1,281 @@@
-     final TypeEvalContext context = TypeEvalContext.userInitiated(referenceExpression.getContainingFile()).withTracing();
 +package com.jetbrains.python;
 +
 +import com.intellij.psi.PsiElement;
 +import com.intellij.psi.util.PsiElementFilter;
 +import com.intellij.psi.util.PsiTreeUtil;
 +import com.intellij.psi.util.QualifiedName;
 +import com.intellij.util.ArrayUtil;
 +import com.intellij.util.Function;
 +import com.intellij.util.containers.ContainerUtil;
 +import com.jetbrains.python.documentation.PythonDocumentationProvider;
 +import com.jetbrains.python.fixtures.PyTestCase;
 +import com.jetbrains.python.psi.PyReferenceExpression;
 +import com.jetbrains.python.psi.types.PyType;
 +import com.jetbrains.python.psi.types.PyTypeFromUsedAttributesHelper;
 +import com.jetbrains.python.psi.types.TypeEvalContext;
 +import org.jetbrains.annotations.NotNull;
 +import org.jetbrains.annotations.Nullable;
 +
 +import java.util.Set;
 +
 +/**
 + * @author Mikhail Golubev
 + */
 +public class PyTypeFromUsedAttributesTest extends PyTestCase {
 +
 +  public void testCollectAttributeOfParameter() {
 +    doTestUsedAttributes("def func(x):\n" +
 +                         "    if x.baz():\n" +
 +                         "        x.foo = x.bar",
 +                         "foo", "bar", "baz");
 +  }
 +
 +  public void testCollectAttributesInOuterScopes() {
 +    doTestUsedAttributes("x = undefined()" +
 +                         "x.quux\n" +
 +                         "def func2():\n" +
 +                         "    x.bar\n" +
 +                         "    def nested():\n" +
 +                         "        x.baz",
 +                         "quux", "baz", "bar");
 +  }
 +
 +  public void testIgnoreAttributesOfParameterInOtherFunctions() {
 +    doTestUsedAttributes("def func1(x):\n" +
 +                         "    x.foo\n" +
 +                         "    \n" +
 +                         "def func2(x):\n" +
 +                         "    x.bar",
 +                         "bar");
 +  }
 +
 +
 +  public void testCollectSpecialMethodNames() {
 +    doTestUsedAttributes("x = undefined()\n" +
 +                         "x[0] = x[...]\n" +
 +                         "x + 42",
 +                         "__getitem__", "__setitem__", "__add__");
 +  }
 +
 +  public void testOnlyBaseClassesRetained() {
 +    doTestType("class Base(object):\n" +
 +               "    attr_a = None\n" +
 +               "    attr_b = None\n" +
 +               "\n" +
 +               "class C2(Base):\n" +
 +               "    pass\n" +
 +               "\n" +
 +               "class C3(Base):\n" +
 +               "    attr_a = None\n" +
 +               "\n" +
 +               "class C4(Base):\n" +
 +               "    attr_a = None\n" +
 +               "    attr_b = None\n" +
 +               "\n" +
 +               "x = undefined()\n" +
 +               "x.attr_a\n" +
 +               "x.attr_b",
 +               "Base | unknown");
 +  }
 +
 +  public void testDiamondHierarchyBottom() {
 +    doTestType("class D(object):\n" +
 +               "    pass\n" +
 +               "class B(D):\n" +
 +               "    pass\n" +
 +               "class C(D):\n" +
 +               "    pass\n" +
 +               "class A(B, C):\n" +
 +               "    foo = None\n" +
 +               "    bar = None\n" +
 +               "\n" +
 +               "def func(x):\n" +
 +               "    x.foo\n" +
 +               "    x.bar",
 +               "A | unknown");
 +  }
 +
 +  public void testDiamondHierarchySiblings() {
 +    doTestType("class D(object):\n" +
 +               "    bar = None\n" +
 +               "class B(D):\n" +
 +               "    foo = None\n" +
 +               "class C(D):\n" +
 +               "    foo = None\n" +
 +               "    bar = None\n" +
 +               "class A(B, C):\n" +
 +               "    foo = None\n" +
 +               "    bar = None\n" +
 +               "\n" +
 +               "def func(x):\n" +
 +               "    x.foo()\n" +
 +               "    x.bar()\n",
 +               "B | C | unknown");
 +  }
 +
 +  public void testDiamondHierarchyTop() {
 +    doTestType("class D(object):\n" +
 +               "    foo = None\n" +
 +               "    bar = None\n" +
 +               "\n" +
 +               "class B(D):\n" +
 +               "    foo = None\n" +
 +               "    bar = None\n" +
 +               "\n" +
 +               "class C(D):\n" +
 +               "    foo = None\n" +
 +               "\n" +
 +               "class A(B, C):\n" +
 +               "    foo = None\n" +
 +               "    bar = None\n" +
 +               "\n" +
 +               "def func(x):\n" +
 +               "    x.foo()\n" +
 +               "    x.bar()",
 +               "D | unknown");
 +  }
 +
 +  public void testDiamondHierarchyLeft() {
 +    doTestType("class D(object):\n" +
 +               "    foo = None\n" +
 +               "class B(D):\n" +
 +               "    bar = None\n" +
 +               "class C(D):\n" +
 +               "    pass\n" +
 +               "class A(B, C):\n" +
 +               "    foo = None\n" +
 +               "    bar = None\n" +
 +               "def func(x):\n" +
 +               "    x.foo()\n" +
 +               "    x.bar()",
 +               "B | unknown");
 +  }
 +
 +  public void testBuiltinTypes() {
 +    doTestType("def func(x):\n" +
 +               "    x.upper()\n" +
 +               "    x.decode()",
 +               "bytearray | str | unicode | unknown");
 +
 +    doTestType("def func(x):\n" +
 +               "    x.pop() and x.update()",
 +               "dict | set | unknown");
 +  }
 +
 +  public void testFunctionType() {
 +    doTestType("class A:\n" +
 +               "    def method_a(self):\n" +
 +               "        pass\n" +
 +               "class B:\n" +
 +               "    def method_b(self):\n" +
 +               "        pass\n" +
 +               "def func(a, b):\n" +
 +               "    a.method_a\n" +
 +               "    b.method_b\n" +
 +               "    return a\n" +
 +               "x = func\n" +
 +               "x",
 +               "(a: A | unknown, b: B | unknown) -> A | unknown");
 +  }
 +
 +  public void testFastInferenceForObjectAttributes() {
 +    doTestType("x = undefined()\n" +
 +               "x.__init__(1)\n" +
 +               "x",
 +               "object | unknown");
 +  }
 +
 +  public void testResultsOrdering() {
 +    myFixture.copyDirectoryToProject(getTestName(true), "");
 +    doTestType("import module\n" +
 +               "class MySortable(object):\n" +
 +               "    def sort(self):\n" +
 +               "        pass\n" +
 +               "x = undefined()\n" +
 +               "x.sort()",
 +               "list | MySortable | OtherClassA | OtherClassB | unknown");
 +  }
 +
 +  public void testCyclicInheritance() {
 +    myFixture.copyDirectoryToProject(getTestName(true), "");
 +    myFixture.configureByFile("main.py");
 +    final PyReferenceExpression referenceExpression = findLastReferenceByText("x");
 +    assertNotNull(referenceExpression);
-     final TypeEvalContext context = TypeEvalContext.userInitiated(referenceExpression.getContainingFile());
++    final TypeEvalContext context =
++      TypeEvalContext.userInitiated(myFixture.getProject(), referenceExpression.getContainingFile()).withTracing();
 +    final PyType actual = context.getType(referenceExpression);
 +    final String actualType = PythonDocumentationProvider.getTypeName(actual, context);
 +    assertEquals("B | unknown", actualType);
 +  }
 +
 +  public void testLongInheritanceChain() {
 +    // This obvious test is needed because of custom method for resolution of class ancestors
 +    doTestType("class C1(object):\n" +
 +               "    attr = 'top'\n" +
 +               "class C2(C1):\n" +
 +               "    pass\n" +
 +               "class C3(C2):\n" +
 +               "    pass\n" +
 +               "class C4(C3):\n" +
 +               "    pass\n" +
 +               "class C5(C4):\n" +
 +               "    attr = 'bottom'\n" +
 +               "x = undefined()\n" +
 +               "x.attr\n" +
 +               "x",
 +               "C1 | unknown");
 +  }
 +
 +  public void testImportQualifiers() {
 +    myFixture.copyDirectoryToProject(getTestName(true), "");
 +    myFixture.configureByFile("pkg1/pkg2/main.py");
 +    final Set<QualifiedName> qualifiers = PyTypeFromUsedAttributesHelper.collectImportQualifiers(myFixture.getFile());
 +    final Set<String> qualifiedNames = ContainerUtil.map2Set(qualifiers, new Function<QualifiedName, String>() {
 +      @Override
 +      public String fun(QualifiedName name) {
 +        return name.toString();
 +      }
 +    });
 +    assertSameElements(qualifiedNames,
 +                       "root",
 +                       "pkg1.pkg2.module2a",
 +                       "pkg1.module1a",
 +                       "pkg1.pkg2.module2b.C1",
 +                       "pkg1.module1b.B1",
 +                       "pkg1.pkg2.module2b",
 +                       "pkg1.pkg2");
 +  }
 +
 +  private void doTestType(@NotNull String text, @NotNull String expectedType) {
 +    myFixture.configureByText(PythonFileType.INSTANCE, text);
 +    final PyReferenceExpression referenceExpression = findLastReferenceByText("x");
 +    assertNotNull(referenceExpression);
++    final TypeEvalContext context = TypeEvalContext.userInitiated(myFixture.getProject(), referenceExpression.getContainingFile());
 +    final PyType actual = context.getType(referenceExpression);
 +    final String actualType = PythonDocumentationProvider.getTypeName(actual, context);
 +    assertEquals(expectedType, actualType);
 +  }
 +
 +  private void doTestUsedAttributes(@NotNull String text, @NotNull String... attributesExpected) {
 +    myFixture.configureByText(PythonFileType.INSTANCE, text);
 +    final PyReferenceExpression referenceExpression = findLastReferenceByText("x");
 +    assertNotNull(referenceExpression);
 +    assertSameElements(PyTypeFromUsedAttributesHelper.collectUsedAttributes(referenceExpression), attributesExpected);
 +  }
 +
 +  @Nullable
 +  private PyReferenceExpression findLastReferenceByText(@NotNull final String text) {
 +    final PsiElement[] elements = PsiTreeUtil.collectElements(myFixture.getFile(), new PsiElementFilter() {
 +      @Override
 +      public boolean isAccepted(PsiElement element) {
 +        return element instanceof PyReferenceExpression && element.getText().equals(text);
 +      }
 +    });
 +    return (PyReferenceExpression)ArrayUtil.getLastElement(elements);
 +  }
 +
 +  @Override
 +  protected String getTestDataPath() {
 +    return super.getTestDataPath() + "/typesFromAttributes/";
 +  }
 +}
index 9e57b1f92128efcbd3fac96a2bf0071114b4c745,487b43ef370c8400d6b8ec4e5b8118c8117b5d97..f5cf1ef01d7636bc5d42cae92cc70ad19cf5827b
@@@ -701,16 -709,52 +702,65 @@@ public class PythonCompletionTest exten
      assertDoesntContain(suggested, PyNames.METHOD_SPECIAL_ATTRIBUTES);
    }
  
 +  public void testFromUsedMethodsOfString() {
 +    final List<String> suggested = doTestByFile();
 +    assertNotNull(suggested);
 +    // append comes from bytearray
 +    assertContainsElements(suggested, "lower", "capitalize", "join", "append");
 +  }
 +
 +  public void testFromUsedAttributesOfClass() {
 +    final List<String> suggested = doTestByFile();
 +    assertNotNull(suggested);
 +    assertContainsElements(suggested, "other_method", "name", "unique_method");
 +  }
++
+   // PY-14388
+   public void testAttributeOfIndirectlyImportedPackage() {
+     doMultiFileTest();
+   }
+   // PY-14387
+   public void testSubmoduleOfIndirectlyImportedPackage() {
+     myFixture.copyDirectoryToProject("completion/" + getTestName(true), "");
+     myFixture.configureByFile("a.py");
+     myFixture.completeBasic();
+     final List<String> suggested = myFixture.getLookupElementStrings();
+     assertNotNull(suggested);
+     assertSameElements(suggested, "VAR", "subpkg1");
+   }
+   // PY-14519
+   public void testOsPath() {
+     myFixture.copyDirectoryToProject("completion/" + getTestName(true), "");
+     myFixture.configureByFile("a.py");
+     myFixture.completeBasic();
+     final List<String> suggested = myFixture.getLookupElementStrings();
+     assertNotNull(suggested);
+     assertContainsElements(suggested, "path");
+   }
+   // PY-14331
+   public void testExcludedTopLevelPackage() {
+     myFixture.copyDirectoryToProject("completion/" + getTestName(true), "");
+     myFixture.configureByFile("a.py");
+     PsiTestUtil.addExcludedRoot(myFixture.getModule(), myFixture.findFileInTempDir("pkg1"));
+     final LookupElement[] variants = myFixture.completeBasic();
+     assertNotNull(variants);
+     assertEmpty(variants);
+   }
+   // PY-14331
+   public void testExcludedSubPackage() {
+     myFixture.copyDirectoryToProject("completion/" + getTestName(true), "");
+     myFixture.configureByFile("a.py");
+     PsiTestUtil.addExcludedRoot(myFixture.getModule(), myFixture.findFileInTempDir("pkg1/subpkg1"));
+     final LookupElement[] variants = myFixture.completeBasic();
+     assertNotNull(variants);
+     assertEmpty(variants);
+   }
+   public void testStructuralType() {
+     doTest();
+   }
  }
index 022d512579c29be3be09bcb52d44e89867e2a15a,a6a2adc488c5ad5352a7f99d6fa75c623427ea14..dca624adabca58e73a7d9588354de244f3f6a7b2
@@@ -72,23 -71,15 +72,30 @@@ public class PyClassMROTest extends PyT
      assertMRO(getClass("H"), "E", "F", "B", "G", "C", "D", "A", "object");
    }
  
 +  public void testTangledInheritance() {
 +    final int numClasses = 100;
 +
 +    final List<String> expectedMRO = new ArrayList<String>();
 +    for (int i = numClasses - 1; i >= 1; i--) {
 +      expectedMRO.add(String.format("Class%03d", i));
 +    }
 +    expectedMRO.add("object");
 +    final PyClass pyClass = getClass(String.format("Class%03d", numClasses));
 +    final long startTime = System.currentTimeMillis();
 +    assertMRO(pyClass, ArrayUtil.toStringArray(expectedMRO));
 +    final long elapsed = System.currentTimeMillis() - startTime;
 +    assertTrue("Calculation of MRO takes too much time: " + elapsed + " ms", elapsed < 1000);
 +  }
 +
+   // PY-11401
+   public void testUnresolvedClassesImpossibleToBuildMRO() {
+     assertMRO(getClass("ObjectManager"),
+               "CopyContainer", "unknown", "Navigation", "unknown", "Tabs", "unknown", "unknown", "unknown", "Collection", "Resource",
+               "LockableItem", "EtagSupport", "Traversable", "object", "unknown");
+   }
    public void assertMRO(@NotNull PyClass cls, @NotNull String... mro) {
-     final List<PyClassLikeType> types = cls.getAncestorTypes(TypeEvalContext.codeInsightFallback());
+     final List<PyClassLikeType> types = cls.getAncestorTypes(TypeEvalContext.codeInsightFallback(cls.getProject()));
      final List<String> classNames = new ArrayList<String>();
      for (PyClassLikeType type : types) {
        if (type != null) {