Merge remote-tracking branch 'origin/master' into mikhail.golubev/py-attribute-inference
[idea/community.git] / python / src / com / jetbrains / python / psi / impl / PyClassImpl.java
1 /*
2  * Copyright 2000-2014 JetBrains s.r.o.
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  * http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 package com.jetbrains.python.psi.impl;
17
18 import com.intellij.codeInsight.completion.CompletionUtil;
19 import com.intellij.lang.ASTNode;
20 import com.intellij.navigation.ItemPresentation;
21 import com.intellij.openapi.util.Comparing;
22 import com.intellij.openapi.util.Key;
23 import com.intellij.openapi.util.NotNullLazyValue;
24 import com.intellij.psi.*;
25 import com.intellij.psi.scope.PsiScopeProcessor;
26 import com.intellij.psi.search.LocalSearchScope;
27 import com.intellij.psi.search.SearchScope;
28 import com.intellij.psi.stubs.IStubElementType;
29 import com.intellij.psi.stubs.StubElement;
30 import com.intellij.psi.tree.TokenSet;
31 import com.intellij.psi.util.*;
32 import com.intellij.util.*;
33 import com.intellij.util.containers.ContainerUtil;
34 import com.jetbrains.python.PyElementTypes;
35 import com.jetbrains.python.PyNames;
36 import com.jetbrains.python.PyTokenTypes;
37 import com.jetbrains.python.PythonDialectsTokenSetProvider;
38 import com.jetbrains.python.codeInsight.controlflow.ControlFlowCache;
39 import com.jetbrains.python.codeInsight.controlflow.ScopeOwner;
40 import com.jetbrains.python.codeInsight.dataflow.scope.ScopeUtil;
41 import com.jetbrains.python.documentation.DocStringUtil;
42 import com.jetbrains.python.psi.*;
43 import com.jetbrains.python.psi.resolve.PyResolveContext;
44 import com.jetbrains.python.psi.resolve.PyResolveUtil;
45 import com.jetbrains.python.psi.resolve.QualifiedNameFinder;
46 import com.jetbrains.python.psi.resolve.RatedResolveResult;
47 import com.jetbrains.python.psi.stubs.PropertyStubStorage;
48 import com.jetbrains.python.psi.stubs.PyClassStub;
49 import com.jetbrains.python.psi.stubs.PyFunctionStub;
50 import com.jetbrains.python.psi.stubs.PyTargetExpressionStub;
51 import com.jetbrains.python.psi.types.*;
52 import com.jetbrains.python.toolbox.Maybe;
53 import org.jetbrains.annotations.NotNull;
54 import org.jetbrains.annotations.Nullable;
55
56 import javax.swing.*;
57 import java.util.*;
58
59 import static com.intellij.openapi.util.text.StringUtil.join;
60 import static com.intellij.openapi.util.text.StringUtil.notNullize;
61
62 /**
63  * @author yole
64  */
65 public class PyClassImpl extends PyBaseElementImpl<PyClassStub> implements PyClass {
66   public static class MROException extends Exception {
67     public MROException(String s) {
68       super(s);
69     }
70   }
71
72   public static final PyClass[] EMPTY_ARRAY = new PyClassImpl[0];
73   private static final Object EVALUATING = new Object();
74
75   private List<PyTargetExpression> myInstanceAttributes;
76   private final NotNullLazyValue<CachedValue<Boolean>> myNewStyle = new NotNullLazyValue<CachedValue<Boolean>>() {
77     @NotNull
78     @Override
79     protected CachedValue<Boolean> compute() {
80       return CachedValuesManager.getManager(getProject()).createCachedValue(new NewStyleCachedValueProvider(), false);
81     }
82   };
83
84   private volatile Map<String, Property> myPropertyCache;
85
86   private class CachedAncestorsProvider implements ParameterizedCachedValueProvider<List<PyClassLikeType>, TypeEvalContext> {
87     @Nullable
88     @Override
89     public CachedValueProvider.Result<List<PyClassLikeType>> compute(@NotNull TypeEvalContext context) {
90       List<PyClassLikeType> ancestorTypes;
91       if (isNewStyleClass()) {
92         try {
93           ancestorTypes = getMROAncestorTypes(context);
94         }
95         catch (MROException e) {
96           ancestorTypes = getOldStyleAncestorTypes(context);
97           boolean hasUnresolvedAncestorTypes = false;
98           for (PyClassLikeType type : ancestorTypes) {
99             if (type == null) {
100               hasUnresolvedAncestorTypes = true;
101               break;
102             }
103           }
104           if (!hasUnresolvedAncestorTypes) {
105             ancestorTypes = Collections.singletonList(null);
106           }
107         }
108       }
109       else {
110         ancestorTypes = getOldStyleAncestorTypes(context);
111       }
112       return CachedValueProvider.Result.create(ancestorTypes, PsiModificationTracker.MODIFICATION_COUNT);
113     }
114   }
115
116   private final Key<ParameterizedCachedValue<List<PyClassLikeType>, TypeEvalContext>> myCachedValueKey = Key.create("cached ancestors");
117   private final CachedAncestorsProvider myCachedAncestorsProvider = new CachedAncestorsProvider();
118
119   @Override
120   public PyType getType(@NotNull TypeEvalContext context, @NotNull TypeEvalContext.Key key) {
121     return new PyClassTypeImpl(this, true);
122   }
123
124   private class NewStyleCachedValueProvider implements CachedValueProvider<Boolean> {
125     @Override
126     public Result<Boolean> compute() {
127       return new Result<Boolean>(calculateNewStyleClass(), PsiModificationTracker.MODIFICATION_COUNT);
128     }
129   }
130
131   public PyClassImpl(@NotNull ASTNode astNode) {
132     super(astNode);
133   }
134
135   public PyClassImpl(@NotNull final PyClassStub stub) {
136     this(stub, PyElementTypes.CLASS_DECLARATION);
137   }
138
139   public PyClassImpl(@NotNull final PyClassStub stub, @NotNull IStubElementType nodeType) {
140     super(stub, nodeType);
141   }
142
143   public PsiElement setName(@NotNull String name) throws IncorrectOperationException {
144     final ASTNode nameElement = PyUtil.createNewName(this, name);
145     final ASTNode node = getNameNode();
146     if (node != null) {
147       getNode().replaceChild(node, nameElement);
148     }
149     return this;
150   }
151
152   @Nullable
153   @Override
154   public String getName() {
155     final PyClassStub stub = getStub();
156     if (stub != null) {
157       return stub.getName();
158     }
159     else {
160       ASTNode node = getNameNode();
161       return node != null ? node.getText() : null;
162     }
163   }
164
165   public PsiElement getNameIdentifier() {
166     final ASTNode nameNode = getNameNode();
167     return nameNode != null ? nameNode.getPsi() : null;
168   }
169
170   public ASTNode getNameNode() {
171     return getNode().findChildByType(PyTokenTypes.IDENTIFIER);
172   }
173
174   @Override
175   public Icon getIcon(int flags) {
176     return PlatformIcons.CLASS_ICON;
177   }
178
179   @Override
180   protected void acceptPyVisitor(PyElementVisitor pyVisitor) {
181     pyVisitor.visitPyClass(this);
182   }
183
184   @Override
185   @NotNull
186   public PyStatementList getStatementList() {
187     final PyStatementList statementList = childToPsi(PyElementTypes.STATEMENT_LIST);
188     assert statementList != null : "Statement list missing for class " + getText();
189     return statementList;
190   }
191
192   @Override
193   public PyArgumentList getSuperClassExpressionList() {
194     final PyArgumentList argList = PsiTreeUtil.getChildOfType(this, PyArgumentList.class);
195     if (argList != null && argList.getFirstChild() != null) {
196       return argList;
197     }
198     return null;
199   }
200
201   @NotNull
202   public PyExpression[] getSuperClassExpressions() {
203     final PyArgumentList argList = getSuperClassExpressionList();
204     if (argList != null) {
205       return argList.getArguments();
206     }
207     return PyExpression.EMPTY_ARRAY;
208   }
209
210   @NotNull
211   public static PyExpression unfoldClass(@NotNull PyExpression expression) {
212     if (expression instanceof PyCallExpression) {
213       PyCallExpression call = (PyCallExpression)expression;
214       final PyExpression callee = call.getCallee();
215       final PyExpression[] arguments = call.getArguments();
216       if (callee != null && "with_metaclass".equals(callee.getName()) && arguments.length > 1) {
217         final PyExpression secondArgument = arguments[1];
218         if (secondArgument != null) {
219           return secondArgument;
220         }
221       }
222     }
223     // Heuristic: unfold Foo[Bar] to Foo for subscription expressions for superclasses
224     else if (expression instanceof PySubscriptionExpression) {
225       final PySubscriptionExpression subscriptionExpr = (PySubscriptionExpression)expression;
226       return subscriptionExpr.getOperand();
227     }
228     return expression;
229   }
230
231   @NotNull
232   @Override
233   public List<PyClass> getAncestorClasses() {
234     return getAncestorClasses(TypeEvalContext.codeInsightFallback(getProject()));
235   }
236
237   @NotNull
238   @Override
239   public List<PyClass> getAncestorClasses(@NotNull TypeEvalContext context) {
240     final List<PyClass> results = new ArrayList<PyClass>();
241     for (PyClassLikeType type : getAncestorTypes(context)) {
242       if (type instanceof PyClassType) {
243         results.add(((PyClassType)type).getPyClass());
244       }
245     }
246     return results;
247   }
248
249   public boolean isSubclass(PyClass parent) {
250     if (this == parent) {
251       return true;
252     }
253     for (PyClass superclass : getAncestorClasses()) {
254       if (parent == superclass) return true;
255     }
256     return false;
257   }
258
259   @Override
260   public boolean isSubclass(@NotNull String superClassQName) {
261     if (superClassQName.equals(getQualifiedName())) {
262       return true;
263     }
264     for (PyClassLikeType type : getAncestorTypes(TypeEvalContext.codeInsightFallback(getProject()))) {
265       if (type != null && superClassQName.equals(type.getClassQName())) {
266         return true;
267       }
268     }
269     return false;
270   }
271
272   public PyDecoratorList getDecoratorList() {
273     return getStubOrPsiChild(PyElementTypes.DECORATOR_LIST);
274   }
275
276   @Nullable
277   public String getQualifiedName() {
278     return QualifiedNameFinder.getQualifiedName(this);
279   }
280
281   @Override
282   public List<String> getSlots() {
283     final Set<String> result = new LinkedHashSet<String>();
284     boolean found = false;
285     final List<String> ownSlots = getOwnSlots();
286     if (ownSlots != null) {
287       found = true;
288       result.addAll(ownSlots);
289     }
290     for (PyClass cls : getAncestorClasses()) {
291       final List<String> ancestorSlots = cls.getOwnSlots();
292       if (ancestorSlots != null) {
293         found = true;
294         result.addAll(ancestorSlots);
295       }
296     }
297     return found ? new ArrayList<String>(result) : null;
298   }
299
300   @Nullable
301   @Override
302   public List<String> getOwnSlots() {
303     final PyClassStub stub = getStub();
304     if (stub != null) {
305       return stub.getSlots();
306     }
307     return PyFileImpl.getStringListFromTargetExpression(PyNames.SLOTS, getClassAttributes());
308   }
309
310   @NotNull
311   public PyClass[] getSuperClasses() {
312     final List<PyClassLikeType> superTypes = getSuperClassTypes(TypeEvalContext.codeInsightFallback(getProject()));
313     if (superTypes.isEmpty()) {
314       return EMPTY_ARRAY;
315     }
316     final List<PyClass> result = new ArrayList<PyClass>();
317     for (PyClassLikeType type : superTypes) {
318       if (type instanceof PyClassType) {
319         result.add(((PyClassType)type).getPyClass());
320       }
321     }
322     return result.toArray(new PyClass[result.size()]);
323   }
324
325   @Override
326   public ItemPresentation getPresentation() {
327     return new PyElementPresentation(this) {
328       @Nullable
329       @Override
330       public String getPresentableText() {
331         if (!isValid()) {
332           return null;
333         }
334         final StringBuilder result = new StringBuilder(notNullize(getName(), PyNames.UNNAMED_ELEMENT));
335         final PyExpression[] superClassExpressions = getSuperClassExpressions();
336         if (superClassExpressions.length > 0) {
337           result.append("(");
338           result.append(join(Arrays.asList(superClassExpressions), new Function<PyExpression, String>() {
339             public String fun(PyExpression expr) {
340               String name = expr.getText();
341               return notNullize(name, PyNames.UNNAMED_ELEMENT);
342             }
343           }, ", "));
344           result.append(")");
345         }
346         return result.toString();
347       }
348     };
349   }
350
351   @NotNull
352   private static List<PyClassLikeType> mroMerge(@NotNull List<List<PyClassLikeType>> sequences) throws MROException {
353     List<PyClassLikeType> result = new LinkedList<PyClassLikeType>(); // need to insert to 0th position on linearize
354     while (true) {
355       // filter blank sequences
356       final List<List<PyClassLikeType>> nonBlankSequences = new ArrayList<List<PyClassLikeType>>(sequences.size());
357       for (List<PyClassLikeType> item : sequences) {
358         if (item.size() > 0) nonBlankSequences.add(item);
359       }
360       if (nonBlankSequences.isEmpty()) return result;
361       // find a clean head
362       boolean found = false;
363       PyClassLikeType head = null; // to keep compiler happy; really head is assigned in the loop at least once.
364       for (List<PyClassLikeType> seq : nonBlankSequences) {
365         head = seq.get(0);
366         if (head == null) {
367           seq.remove(0);
368           found = true;
369           break;
370         }
371         boolean headInTails = false;
372         for (List<PyClassLikeType> tailSeq : nonBlankSequences) {
373           if (tailSeq.indexOf(head) > 0) { // -1 is not found, 0 is head, >0 is tail.
374             headInTails = true;
375             break;
376           }
377         }
378         if (!headInTails) {
379           found = true;
380           break;
381         }
382         else {
383           head = null; // as a signal
384         }
385       }
386       if (!found) {
387         // Inconsistent hierarchy results in TypeError
388         throw new MROException("Inconsistent class hierarchy");
389       }
390       // our head is clean;
391       result.add(head);
392       // remove it from heads of other sequences
393       if (head != null) {
394         for (List<PyClassLikeType> seq : nonBlankSequences) {
395           if (Comparing.equal(seq.get(0), head)) {
396             seq.remove(0);
397           }
398         }
399       }
400     } // we either return inside the loop or die by assertion
401   }
402
403
404   private static List<PyClassLikeType> mroLinearize(@NotNull PyClassLikeType type,
405                                                     boolean addThisType,
406                                                     @NotNull TypeEvalContext context) throws MROException {
407     return mroLinearize(type, addThisType, context, new HashMap<PyClassLikeType, Object>());
408   }
409
410   @NotNull
411   private static List<PyClassLikeType> mroLinearize(@NotNull PyClassLikeType type, boolean addThisType,
412                                                     @NotNull TypeEvalContext context,
413                                                     @NotNull Map<PyClassLikeType, Object> cache) throws MROException {
414     final Object computed = cache.get(type);
415     if (computed == EVALUATING) {
416       throw new MROException("Circular class inheritance");
417     }
418     if (computed != null) {
419       //noinspection unchecked
420       return (List<PyClassLikeType>)computed;
421     }
422     cache.put(type, EVALUATING);
423     List<PyClassLikeType> result = null;
424     try {
425       final List<PyClassLikeType> bases = type.getSuperClassTypes(context);
426       final List<List<PyClassLikeType>> lines = new ArrayList<List<PyClassLikeType>>();
427       for (PyClassLikeType base : bases) {
428         if (base != null) {
429           final List<PyClassLikeType> baseClassMRO = mroLinearize(base, true, context, cache);
430           if (!baseClassMRO.isEmpty()) {
431             lines.add(baseClassMRO);
432           }
433         }
434       }
435       if (!bases.isEmpty()) {
436         lines.add(bases);
437       }
438       result = mroMerge(lines);
439       if (addThisType) {
440         result.add(0, type);
441       }
442     }
443     finally {
444       cache.put(type, result);
445     }
446     return result;
447   }
448
449   @Override
450   @NotNull
451   public PyFunction[] getMethods(final boolean inherited) {
452     final PyFunction[] thisClassFunctions =
453       getClassChildren(PythonDialectsTokenSetProvider.INSTANCE.getFunctionDeclarationTokens(), PyFunction.ARRAY_FACTORY);
454     if (!inherited) {
455       return thisClassFunctions;
456     }
457     // Map to get rid of duplicated (overwritten methods)
458     final Map<String, PyFunction> result = new HashMap<String, PyFunction>();
459     // We get classes in MRO order (hopefully), so last methods are last
460     for (final PyClass superClass : getSuperClasses()) {
461       for (final PyFunction function : superClass.getMethods(false)) {
462         final String functionName = function.getName();
463         if (functionName != null) {
464           result.put(functionName, function);
465         }
466       }
467     }
468     // We now need to add our own methods
469     for (final PyFunction function : thisClassFunctions) {
470       final String functionName = function.getName();
471       if (functionName != null) {
472         result.put(functionName, function);
473       }
474     }
475     final Collection<PyFunction> functionsToReturn = result.values();
476     return functionsToReturn.toArray(new PyFunction[functionsToReturn.size()]);
477   }
478
479   @Override
480   @NotNull
481   public Map<String, Property> getProperties() {
482     initProperties();
483     return new HashMap<String, Property>(myPropertyCache);
484   }
485
486   @Override
487   public PyClass[] getNestedClasses() {
488     return getClassChildren(TokenSet.create(PyElementTypes.CLASS_DECLARATION), PyClass.ARRAY_FACTORY);
489   }
490
491   protected <T extends PsiElement> T[] getClassChildren(TokenSet elementTypes, ArrayFactory<T> factory) {
492     // TODO: gather all top-level functions, maybe within control statements
493     final PyClassStub classStub = getStub();
494     if (classStub != null) {
495       return classStub.getChildrenByType(elementTypes, factory);
496     }
497     List<T> result = new ArrayList<T>();
498     final PyStatementList statementList = getStatementList();
499     for (PsiElement element : statementList.getChildren()) {
500       if (elementTypes.contains(element.getNode().getElementType())) {
501         //noinspection unchecked
502         result.add((T)element);
503       }
504     }
505     return result.toArray(factory.create(result.size()));
506   }
507
508   private static class NameFinder<T extends PyElement> implements Processor<T> {
509     private T myResult;
510     private final String[] myNames;
511
512     public NameFinder(String... names) {
513       myNames = names;
514       myResult = null;
515     }
516
517     public T getResult() {
518       return myResult;
519     }
520
521     public boolean process(T target) {
522       final String targetName = target.getName();
523       for (String name : myNames) {
524         if (name.equals(targetName)) {
525           myResult = target;
526           return false;
527         }
528       }
529       return true;
530     }
531   }
532
533   public PyFunction findMethodByName(@Nullable final String name, boolean inherited) {
534     if (name == null) return null;
535     NameFinder<PyFunction> proc = new NameFinder<PyFunction>(name);
536     visitMethods(proc, inherited);
537     return proc.getResult();
538   }
539
540   @Nullable
541   @Override
542   public PyClass findNestedClass(String name, boolean inherited) {
543     if (name == null) return null;
544     NameFinder<PyClass> proc = new NameFinder<PyClass>(name);
545     visitNestedClasses(proc, inherited);
546     return proc.getResult();
547   }
548
549   @Nullable
550   public PyFunction findInitOrNew(boolean inherited) {
551     NameFinder<PyFunction> proc;
552     if (isNewStyleClass()) {
553       proc = new NameFinder<PyFunction>(PyNames.INIT, PyNames.NEW);
554     }
555     else {
556       proc = new NameFinder<PyFunction>(PyNames.INIT);
557     }
558     visitMethods(proc, inherited, true);
559     return proc.getResult();
560   }
561
562   private final static Maybe<Callable> UNKNOWN_CALL = new Maybe<Callable>(); // denotes _not_ a PyFunction, actually
563   private final static Maybe<Callable> NONE = new Maybe<Callable>(null); // denotes an explicit None
564
565   /**
566    * @param name            name of the property
567    * @param property_filter returns true if the property is acceptable
568    * @param advanced        is @foo.setter syntax allowed
569    * @return the first property that both filters accepted.
570    */
571   @Nullable
572   private Property processPropertiesInClass(@Nullable String name, @Nullable Processor<Property> property_filter, boolean advanced) {
573     // NOTE: fast enough to be rerun every time
574     Property prop = processDecoratedProperties(name, property_filter, advanced);
575     if (prop != null) return prop;
576     if (getStub() != null) {
577       prop = processStubProperties(name, property_filter);
578       if (prop != null) return prop;
579     }
580     else {
581       // name = property(...) assignments from PSI
582       for (PyTargetExpression target : getClassAttributes()) {
583         if (name == null || name.equals(target.getName())) {
584           prop = PropertyImpl.fromTarget(target);
585           if (prop != null) {
586             if (property_filter == null || property_filter.process(prop)) return prop;
587           }
588         }
589       }
590     }
591     return null;
592   }
593
594   @Nullable
595   private Property processDecoratedProperties(@Nullable String name, @Nullable Processor<Property> filter, boolean useAdvancedSyntax) {
596     // look at @property decorators
597     Map<String, List<PyFunction>> grouped = new HashMap<String, List<PyFunction>>();
598     // group suitable same-named methods, each group defines a property
599     for (PyFunction method : getMethods(false)) {
600       final String methodName = method.getName();
601       if (name == null || name.equals(methodName)) {
602         List<PyFunction> bucket = grouped.get(methodName);
603         if (bucket == null) {
604           bucket = new SmartList<PyFunction>();
605           grouped.put(methodName, bucket);
606         }
607         bucket.add(method);
608       }
609     }
610     for (Map.Entry<String, List<PyFunction>> entry : grouped.entrySet()) {
611       Maybe<Callable> getter = NONE;
612       Maybe<Callable> setter = NONE;
613       Maybe<Callable> deleter = NONE;
614       String doc = null;
615       final String decoratorName = entry.getKey();
616       for (PyFunction method : entry.getValue()) {
617         final PyDecoratorList decoratorList = method.getDecoratorList();
618         if (decoratorList != null) {
619           for (PyDecorator deco : decoratorList.getDecorators()) {
620             final QualifiedName qname = deco.getQualifiedName();
621             if (qname != null) {
622               String decoName = qname.toString();
623               for (PyKnownDecoratorProvider provider : PyUtil.KnownDecoratorProviderHolder.KNOWN_DECORATOR_PROVIDERS) {
624                 final String knownName = provider.toKnownDecorator(decoName);
625                 if (knownName != null) {
626                   decoName = knownName;
627                 }
628               }
629               if (PyNames.PROPERTY.equals(decoName)) {
630                 getter = new Maybe<Callable>(method);
631               }
632               else if (useAdvancedSyntax && qname.matches(decoratorName, PyNames.GETTER)) {
633                 getter = new Maybe<Callable>(method);
634               }
635               else if (useAdvancedSyntax && qname.matches(decoratorName, PyNames.SETTER)) {
636                 setter = new Maybe<Callable>(method);
637               }
638               else if (useAdvancedSyntax && qname.matches(decoratorName, PyNames.DELETER)) {
639                 deleter = new Maybe<Callable>(method);
640               }
641             }
642           }
643         }
644         if (getter != NONE && setter != NONE && deleter != NONE) break; // can't improve
645       }
646       if (getter != NONE || setter != NONE || deleter != NONE) {
647         final PropertyImpl prop = new PropertyImpl(decoratorName, getter, setter, deleter, doc, null);
648         if (filter == null || filter.process(prop)) return prop;
649       }
650     }
651     return null;
652   }
653
654   private Maybe<Callable> fromPacked(Maybe<String> maybeName) {
655     if (maybeName.isDefined()) {
656       final String value = maybeName.value();
657       if (value == null || PyNames.NONE.equals(value)) {
658         return NONE;
659       }
660       PyFunction method = findMethodByName(value, true);
661       if (method != null) return new Maybe<Callable>(method);
662     }
663     return UNKNOWN_CALL;
664   }
665
666   @Nullable
667   private Property processStubProperties(@Nullable String name, @Nullable Processor<Property> propertyProcessor) {
668     final PyClassStub stub = getStub();
669     if (stub != null) {
670       for (StubElement subStub : stub.getChildrenStubs()) {
671         if (subStub.getStubType() == PyElementTypes.TARGET_EXPRESSION) {
672           final PyTargetExpressionStub targetStub = (PyTargetExpressionStub)subStub;
673           PropertyStubStorage prop = targetStub.getCustomStub(PropertyStubStorage.class);
674           if (prop != null && (name == null || name.equals(targetStub.getName()))) {
675             Maybe<Callable> getter = fromPacked(prop.getGetter());
676             Maybe<Callable> setter = fromPacked(prop.getSetter());
677             Maybe<Callable> deleter = fromPacked(prop.getDeleter());
678             String doc = prop.getDoc();
679             if (getter != NONE || setter != NONE || deleter != NONE) {
680               final PropertyImpl property = new PropertyImpl(targetStub.getName(), getter, setter, deleter, doc, targetStub.getPsi());
681               if (propertyProcessor == null || propertyProcessor.process(property)) return property;
682             }
683           }
684         }
685       }
686     }
687     return null;
688   }
689
690   @Nullable
691   @Override
692   public Property findProperty(@NotNull final String name, boolean inherited) {
693     Property property = findLocalProperty(name);
694     if (property != null) {
695       return property;
696     }
697     if (findMethodByName(name, false) != null || findClassAttribute(name, false) != null) {
698       return null;
699     }
700     if (inherited) {
701       for (PyClass aClass : getAncestorClasses()) {
702         final Property ancestorProperty = ((PyClassImpl)aClass).findLocalProperty(name);
703         if (ancestorProperty != null) {
704           return ancestorProperty;
705         }
706       }
707     }
708     return null;
709   }
710
711   @Override
712   public Property findPropertyByCallable(Callable callable) {
713     initProperties();
714     for (Property property : myPropertyCache.values()) {
715       if (property.getGetter().valueOrNull() == callable ||
716           property.getSetter().valueOrNull() == callable ||
717           property.getDeleter().valueOrNull() == callable) {
718         return property;
719       }
720     }
721     return null;
722   }
723
724   private Property findLocalProperty(String name) {
725     initProperties();
726     return myPropertyCache.get(name);
727   }
728
729   private synchronized void initProperties() {
730     if (myPropertyCache == null) {
731       myPropertyCache = initializePropertyCache();
732     }
733   }
734
735   private Map<String, Property> initializePropertyCache() {
736     final Map<String, Property> result = new HashMap<String, Property>();
737     processProperties(null, new Processor<Property>() {
738       @Override
739       public boolean process(Property property) {
740         result.put(property.getName(), property);
741         return false;
742       }
743     }, false);
744     return result;
745   }
746
747   @Nullable
748   @Override
749   public Property scanProperties(@Nullable Processor<Property> filter, boolean inherited) {
750     return processProperties(null, filter, inherited);
751   }
752
753   @Nullable
754   private Property processProperties(@Nullable String name, @Nullable Processor<Property> filter, boolean inherited) {
755     if (!isValid()) {
756       return null;
757     }
758     LanguageLevel level = LanguageLevel.getDefault();
759     // EA-32381: A tree-based instance may not have a parent element somehow, so getContainingFile() may be not appropriate
760     final PsiFile file = getParentByStub() != null ? getContainingFile() : null;
761     if (file != null) {
762       level = LanguageLevel.forElement(file);
763     }
764     final boolean useAdvancedSyntax = level.isAtLeast(LanguageLevel.PYTHON26);
765     final Property local = processPropertiesInClass(name, filter, useAdvancedSyntax);
766     if (local != null) {
767       return local;
768     }
769     if (inherited) {
770       if (name != null && (findMethodByName(name, false) != null || findClassAttribute(name, false) != null)) {
771         return null;
772       }
773       for (PyClass cls : getAncestorClasses()) {
774         final Property property = ((PyClassImpl)cls).processPropertiesInClass(name, filter, useAdvancedSyntax);
775         if (property != null) {
776           return property;
777         }
778       }
779     }
780     return null;
781   }
782
783   private static class PropertyImpl extends PropertyBunch<Callable> implements Property {
784     private final String myName;
785
786     private PropertyImpl(String name,
787                          Maybe<Callable> getter,
788                          Maybe<Callable> setter,
789                          Maybe<Callable> deleter,
790                          String doc,
791                          PyTargetExpression site) {
792       myName = name;
793       myDeleter = deleter;
794       myGetter = getter;
795       mySetter = setter;
796       myDoc = doc;
797       mySite = site;
798     }
799
800     @NotNull
801     @Override
802     public Maybe<Callable> getGetter() {
803       return filterNonStubExpression(myGetter);
804     }
805
806     @NotNull
807     @Override
808     public Maybe<Callable> getSetter() {
809       return filterNonStubExpression(mySetter);
810     }
811
812     @NotNull
813     @Override
814     public Maybe<Callable> getDeleter() {
815       return filterNonStubExpression(myDeleter);
816     }
817
818     public String getName() {
819       return myName;
820     }
821
822     public PyTargetExpression getDefinitionSite() {
823       return mySite;
824     }
825
826     @NotNull
827     @Override
828     public Maybe<Callable> getByDirection(@NotNull AccessDirection direction) {
829       switch (direction) {
830         case READ:
831           return getGetter();
832         case WRITE:
833           return getSetter();
834         case DELETE:
835           return getDeleter();
836       }
837       throw new IllegalArgumentException("Unknown direction " + PyUtil.nvl(direction));
838     }
839
840     @Nullable
841     @Override
842     public PyType getType(@NotNull TypeEvalContext context) {
843       if (mySite instanceof PyTargetExpressionImpl) {
844         final PyType targetDocStringType = ((PyTargetExpressionImpl)mySite).getTypeFromDocString();
845         if (targetDocStringType != null) {
846           return targetDocStringType;
847         }
848       }
849       final Callable callable = myGetter.valueOrNull();
850       if (callable != null) {
851         // Ignore return types of non stub-based elements if we are not allowed to use AST
852         if (!(callable instanceof StubBasedPsiElement) && !context.maySwitchToAST(callable)) {
853           return null;
854         }
855         return context.getReturnType(callable);
856       }
857       return null;
858     }
859
860     @NotNull
861     @Override
862     protected Maybe<Callable> translate(@Nullable PyExpression expr) {
863       if (expr == null) {
864         return NONE;
865       }
866       if (PyNames.NONE.equals(expr.getName())) return NONE; // short-circuit a common case
867       if (expr instanceof Callable) {
868         return new Maybe<Callable>((Callable)expr);
869       }
870       final PsiReference ref = expr.getReference();
871       if (ref != null) {
872         PsiElement something = ref.resolve();
873         if (something instanceof Callable) {
874           return new Maybe<Callable>((Callable)something);
875         }
876       }
877       return NONE;
878     }
879
880     @NotNull
881     private static Maybe<Callable> filterNonStubExpression(@NotNull Maybe<Callable> maybeCallable) {
882       final Callable callable = maybeCallable.valueOrNull();
883       if (callable != null) {
884         if (!(callable instanceof StubBasedPsiElement)) {
885           return UNKNOWN_CALL;
886         }
887       }
888       return maybeCallable;
889     }
890
891     public String toString() {
892       return "property(" + myGetter + ", " + mySetter + ", " + myDeleter + ", " + myDoc + ")";
893     }
894
895     @Nullable
896     public static PropertyImpl fromTarget(PyTargetExpression target) {
897       PyExpression expr = target.findAssignedValue();
898       final PropertyImpl prop = new PropertyImpl(target.getName(), null, null, null, null, target);
899       final boolean success = fillFromCall(expr, prop);
900       return success ? prop : null;
901     }
902   }
903
904   public boolean visitMethods(Processor<PyFunction> processor, boolean inherited) {
905     return visitMethods(processor, inherited, false);
906   }
907
908   public boolean visitMethods(Processor<PyFunction> processor,
909                               boolean inherited,
910                               boolean skipClassObj) {
911     PyFunction[] methods = getMethods(false);
912     if (!ContainerUtil.process(methods, processor)) return false;
913     if (inherited) {
914       for (PyClass ancestor : getAncestorClasses()) {
915         if (skipClassObj && PyNames.FAKE_OLD_BASE.equals(ancestor.getName())) {
916           continue;
917         }
918         if (!ancestor.visitMethods(processor, false)) {
919           return false;
920         }
921       }
922     }
923     return true;
924   }
925
926   public boolean visitNestedClasses(Processor<PyClass> processor, boolean inherited) {
927     PyClass[] nestedClasses = getNestedClasses();
928     if (!ContainerUtil.process(nestedClasses, processor)) return false;
929     if (inherited) {
930       for (PyClass ancestor : getAncestorClasses()) {
931         if (!((PyClassImpl)ancestor).visitNestedClasses(processor, false)) {
932           return false;
933         }
934       }
935     }
936     return true;
937   }
938
939   public boolean visitClassAttributes(Processor<PyTargetExpression> processor, boolean inherited) {
940     List<PyTargetExpression> methods = getClassAttributes();
941     if (!ContainerUtil.process(methods, processor)) return false;
942     if (inherited) {
943       for (PyClass ancestor : getAncestorClasses()) {
944         if (!ancestor.visitClassAttributes(processor, false)) {
945           return false;
946         }
947       }
948     }
949     return true;
950     // NOTE: sorry, not enough metaprogramming to generalize visitMethods and visitClassAttributes
951   }
952
953   public List<PyTargetExpression> getClassAttributes() {
954     PyClassStub stub = getStub();
955     if (stub != null) {
956       final PyTargetExpression[] children = stub.getChildrenByType(PyElementTypes.TARGET_EXPRESSION, PyTargetExpression.EMPTY_ARRAY);
957       return Arrays.asList(children);
958     }
959     List<PyTargetExpression> result = new ArrayList<PyTargetExpression>();
960     for (PsiElement psiElement : getStatementList().getChildren()) {
961       if (psiElement instanceof PyAssignmentStatement) {
962         final PyAssignmentStatement assignmentStatement = (PyAssignmentStatement)psiElement;
963         final PyExpression[] targets = assignmentStatement.getTargets();
964         for (PyExpression target : targets) {
965           if (target instanceof PyTargetExpression) {
966             result.add((PyTargetExpression)target);
967           }
968         }
969       }
970     }
971     return result;
972   }
973
974   @Override
975   public PyTargetExpression findClassAttribute(@NotNull String name, boolean inherited) {
976     final NameFinder<PyTargetExpression> processor = new NameFinder<PyTargetExpression>(name);
977     visitClassAttributes(processor, inherited);
978     return processor.getResult();
979   }
980
981   public List<PyTargetExpression> getInstanceAttributes() {
982     if (myInstanceAttributes == null) {
983       myInstanceAttributes = collectInstanceAttributes();
984     }
985     return myInstanceAttributes;
986   }
987
988   @Nullable
989   @Override
990   public PyTargetExpression findInstanceAttribute(String name, boolean inherited) {
991     final List<PyTargetExpression> instanceAttributes = getInstanceAttributes();
992     for (PyTargetExpression instanceAttribute : instanceAttributes) {
993       if (name.equals(instanceAttribute.getReferencedName())) {
994         return instanceAttribute;
995       }
996     }
997     if (inherited) {
998       for (PyClass ancestor : getAncestorClasses()) {
999         final PyTargetExpression attribute = ancestor.findInstanceAttribute(name, false);
1000         if (attribute != null) {
1001           return attribute;
1002         }
1003       }
1004     }
1005     return null;
1006   }
1007
1008   private List<PyTargetExpression> collectInstanceAttributes() {
1009     Map<String, PyTargetExpression> result = new HashMap<String, PyTargetExpression>();
1010
1011     collectAttributesInNew(result);
1012     PyFunctionImpl initMethod = (PyFunctionImpl)findMethodByName(PyNames.INIT, false);
1013     if (initMethod != null) {
1014       collectInstanceAttributes(initMethod, result);
1015     }
1016     Set<String> namesInInit = new HashSet<String>(result.keySet());
1017     final PyFunction[] methods = getMethods(false);
1018     for (PyFunction method : methods) {
1019       if (!PyNames.INIT.equals(method.getName())) {
1020         collectInstanceAttributes(method, result, namesInInit);
1021       }
1022     }
1023
1024     final Collection<PyTargetExpression> expressions = result.values();
1025     return new ArrayList<PyTargetExpression>(expressions);
1026   }
1027
1028   private void collectAttributesInNew(@NotNull final Map<String, PyTargetExpression> result) {
1029     final PyFunction newMethod = findMethodByName(PyNames.NEW, false);
1030     if (newMethod != null) {
1031       for (PyTargetExpression target : getTargetExpressions(newMethod)) {
1032         result.put(target.getName(), target);
1033       }
1034     }
1035   }
1036
1037   public static void collectInstanceAttributes(@NotNull PyFunction method, @NotNull final Map<String, PyTargetExpression> result) {
1038     collectInstanceAttributes(method, result, null);
1039   }
1040
1041   public static void collectInstanceAttributes(@NotNull PyFunction method,
1042                                                @NotNull final Map<String, PyTargetExpression> result,
1043                                                Set<String> existing) {
1044     final PyParameter[] params = method.getParameterList().getParameters();
1045     if (params.length == 0) {
1046       return;
1047     }
1048     for (PyTargetExpression target : getTargetExpressions(method)) {
1049       if (PyUtil.isInstanceAttribute(target) && (existing == null || !existing.contains(target.getName()))) {
1050         result.put(target.getName(), target);
1051       }
1052     }
1053   }
1054
1055   @NotNull
1056   private static List<PyTargetExpression> getTargetExpressions(@NotNull PyFunction function) {
1057     final PyFunctionStub stub = function.getStub();
1058     if (stub != null) {
1059       return Arrays.asList(stub.getChildrenByType(PyElementTypes.TARGET_EXPRESSION, PyTargetExpression.EMPTY_ARRAY));
1060     }
1061     else {
1062       final PyStatementList statementList = function.getStatementList();
1063       final List<PyTargetExpression> result = new ArrayList<PyTargetExpression>();
1064       statementList.accept(new PyRecursiveElementVisitor() {
1065         @Override
1066         public void visitPyClass(PyClass node) {
1067         }
1068
1069         public void visitPyAssignmentStatement(final PyAssignmentStatement node) {
1070           for (PyExpression expression : node.getTargets()) {
1071             if (expression instanceof PyTargetExpression) {
1072               result.add((PyTargetExpression)expression);
1073             }
1074           }
1075         }
1076       });
1077       return result;
1078     }
1079   }
1080
1081   public boolean isNewStyleClass() {
1082     return myNewStyle.getValue().getValue();
1083   }
1084
1085   private boolean calculateNewStyleClass() {
1086     final PsiFile containingFile = getContainingFile();
1087     if (containingFile instanceof PyFile && ((PyFile)containingFile).getLanguageLevel().isPy3K()) {
1088       return true;
1089     }
1090     final PyClass objClass = PyBuiltinCache.getInstance(this).getClass("object");
1091     if (this == objClass) return true; // a rare but possible case
1092     if (hasNewStyleMetaClass(this)) return true;
1093     for (PyClassLikeType type : getOldStyleAncestorTypes(TypeEvalContext.codeInsightFallback(getProject()))) {
1094       if (type == null) {
1095         // unknown, assume new-style class
1096         return true;
1097       }
1098       if (type instanceof PyClassType) {
1099         final PyClass pyClass = ((PyClassType)type).getPyClass();
1100         if (pyClass == objClass || hasNewStyleMetaClass(pyClass)) {
1101           return true;
1102         }
1103       }
1104     }
1105     return false;
1106   }
1107
1108   private static boolean hasNewStyleMetaClass(PyClass pyClass) {
1109     final PsiFile containingFile = pyClass.getContainingFile();
1110     if (containingFile instanceof PyFile) {
1111       final PsiElement element = ((PyFile)containingFile).getElementNamed(PyNames.DUNDER_METACLASS);
1112       if (element instanceof PyTargetExpression) {
1113         final QualifiedName qName = ((PyTargetExpression)element).getAssignedQName();
1114         if (qName != null && qName.matches("type")) {
1115           return true;
1116         }
1117       }
1118     }
1119     if (pyClass.findClassAttribute(PyNames.DUNDER_METACLASS, false) != null) {
1120       return true;
1121     }
1122     return false;
1123   }
1124
1125   @Override
1126   public boolean processClassLevelDeclarations(@NotNull PsiScopeProcessor processor) {
1127     final PyClassStub stub = getStub();
1128     if (stub != null) {
1129       final List<StubElement> children = stub.getChildrenStubs();
1130       for (StubElement child : children) {
1131         if (!processor.execute(child.getPsi(), ResolveState.initial())) {
1132           return false;
1133         }
1134       }
1135     }
1136     else {
1137       PyResolveUtil.scopeCrawlUp(processor, this, null, this);
1138     }
1139     return true;
1140   }
1141
1142   @Override
1143   public boolean processInstanceLevelDeclarations(@NotNull PsiScopeProcessor processor, @Nullable PsiElement location) {
1144     Map<String, PyTargetExpression> declarationsInMethod = new HashMap<String, PyTargetExpression>();
1145     PyFunction instanceMethod = PsiTreeUtil.getParentOfType(location, PyFunction.class);
1146     final PyClass containingClass = instanceMethod != null ? instanceMethod.getContainingClass() : null;
1147     if (instanceMethod != null && containingClass != null && CompletionUtil.getOriginalElement(containingClass) == this) {
1148       collectInstanceAttributes(instanceMethod, declarationsInMethod);
1149       for (PyTargetExpression targetExpression : declarationsInMethod.values()) {
1150         if (!processor.execute(targetExpression, ResolveState.initial())) {
1151           return false;
1152         }
1153       }
1154     }
1155     for (PyTargetExpression expr : getInstanceAttributes()) {
1156       if (declarationsInMethod.containsKey(expr.getName())) {
1157         continue;
1158       }
1159       if (!processor.execute(expr, ResolveState.initial())) return false;
1160     }
1161     return true;
1162   }
1163
1164   public int getTextOffset() {
1165     final ASTNode name = getNameNode();
1166     return name != null ? name.getStartOffset() : super.getTextOffset();
1167   }
1168
1169   public PyStringLiteralExpression getDocStringExpression() {
1170     return DocStringUtil.findDocStringExpression(getStatementList());
1171   }
1172
1173   @Override
1174   public String getDocStringValue() {
1175     final PyClassStub stub = getStub();
1176     if (stub != null) {
1177       return stub.getDocString();
1178     }
1179     return DocStringUtil.getDocStringValue(this);
1180   }
1181
1182   @Nullable
1183   @Override
1184   public StructuredDocString getStructuredDocString() {
1185     return DocStringUtil.getStructuredDocString(this);
1186   }
1187
1188   public String toString() {
1189     return "PyClass: " + getName();
1190   }
1191
1192   @NotNull
1193   public Iterable<PyElement> iterateNames() {
1194     return Collections.<PyElement>singleton(this);
1195   }
1196
1197   public PyElement getElementNamed(final String the_name) {
1198     return the_name.equals(getName()) ? this : null;
1199   }
1200
1201   public boolean mustResolveOutside() {
1202     return false;
1203   }
1204
1205   public void subtreeChanged() {
1206     super.subtreeChanged();
1207     ControlFlowCache.clear(this);
1208     if (myInstanceAttributes != null) {
1209       myInstanceAttributes = null;
1210     }
1211     myPropertyCache = null;
1212   }
1213
1214   @NotNull
1215   @Override
1216   public SearchScope getUseScope() {
1217     final ScopeOwner scopeOwner = ScopeUtil.getScopeOwner(this);
1218     if (scopeOwner instanceof PyFunction) {
1219       return new LocalSearchScope(scopeOwner);
1220     }
1221     return super.getUseScope();
1222   }
1223
1224   @NotNull
1225   @Override
1226   public List<PyClassLikeType> getSuperClassTypes(@NotNull TypeEvalContext context) {
1227     if (PyNames.FAKE_OLD_BASE.equals(getName())) {
1228       return Collections.emptyList();
1229     }
1230     final PyClassStub stub = getStub();
1231     final List<PyClassLikeType> result = new ArrayList<PyClassLikeType>();
1232     if (stub != null) {
1233       final PsiFile file = getContainingFile();
1234       if (file instanceof PyFile) {
1235         for (QualifiedName name : stub.getSuperClasses()) {
1236           result.add(name != null ? classTypeFromQName(name, (PyFile)file, context) : null);
1237         }
1238       }
1239     }
1240     else {
1241       for (PyExpression expression : getSuperClassExpressions()) {
1242         context.getType(expression);
1243         expression = unfoldClass(expression);
1244         if (expression instanceof PyKeywordArgument) {
1245           continue;
1246         }
1247         final PyType type = context.getType(expression);
1248         PyClassLikeType classLikeType = null;
1249         if (type instanceof PyClassLikeType) {
1250           classLikeType = (PyClassLikeType)type;
1251         }
1252         else {
1253           final PsiReference ref = expression.getReference();
1254           if (ref != null) {
1255             final PsiElement resolved = ref.resolve();
1256             if (resolved instanceof PyClass) {
1257               final PyType resolvedType = context.getType((PyClass)resolved);
1258               if (resolvedType instanceof PyClassLikeType) {
1259                 classLikeType = (PyClassLikeType)resolvedType;
1260               }
1261             }
1262           }
1263         }
1264         result.add(classLikeType);
1265       }
1266     }
1267     final PyBuiltinCache builtinCache = PyBuiltinCache.getInstance(this);
1268     if (result.isEmpty() && isValid() && !builtinCache.isBuiltin(this)) {
1269       final String implicitSuperName = LanguageLevel.forElement(this).isPy3K() ? PyNames.OBJECT : PyNames.FAKE_OLD_BASE;
1270       final PyClass implicitSuper = builtinCache.getClass(implicitSuperName);
1271       if (implicitSuper != null) {
1272         final PyType type = context.getType(implicitSuper);
1273         if (type instanceof PyClassLikeType) {
1274           result.add((PyClassLikeType)type);
1275         }
1276       }
1277     }
1278     return result;
1279   }
1280
1281   @NotNull
1282   @Override
1283   public List<PyClassLikeType> getAncestorTypes(@NotNull TypeEvalContext context) {
1284     // TODO: Return different cached copies depending on the type eval context parameters
1285     final CachedValuesManager manager = CachedValuesManager.getManager(getProject());
1286     return manager.getParameterizedCachedValue(this, myCachedValueKey, myCachedAncestorsProvider, false, context);
1287   }
1288
1289   @Nullable
1290   @Override
1291   public PyType getMetaClassType(@NotNull TypeEvalContext context) {
1292     if (context.maySwitchToAST(this)) {
1293       final PyExpression expression = getMetaClassExpression();
1294       if (expression != null) {
1295         final PyType type = context.getType(expression);
1296         if (type != null) {
1297           return type;
1298         }
1299       }
1300     }
1301     else {
1302       final PyClassStub stub = getStub();
1303       final QualifiedName name = stub != null ? stub.getMetaClass() : PyPsiUtils.asQualifiedName(getMetaClassExpression());
1304       final PsiFile file = getContainingFile();
1305       if (file instanceof PyFile) {
1306         final PyFile pyFile = (PyFile)file;
1307         if (name != null) {
1308           return classTypeFromQName(name, pyFile, context);
1309         }
1310       }
1311     }
1312     final LanguageLevel level = LanguageLevel.forElement(this);
1313     if (level.isOlderThan(LanguageLevel.PYTHON30)) {
1314       final PsiFile file = getContainingFile();
1315       if (file instanceof PyFile) {
1316         final PyFile pyFile = (PyFile)file;
1317         final PsiElement element = pyFile.getElementNamed(PyNames.DUNDER_METACLASS);
1318         if (element instanceof PyTypedElement) {
1319           return context.getType((PyTypedElement)element);
1320         }
1321       }
1322     }
1323     return null;
1324   }
1325
1326   @Nullable
1327   @Override
1328   public PyExpression getMetaClassExpression() {
1329     final LanguageLevel level = LanguageLevel.forElement(this);
1330     if (level.isAtLeast(LanguageLevel.PYTHON30)) {
1331       // Requires AST access
1332       for (PyExpression expression : getSuperClassExpressions()) {
1333         if (expression instanceof PyKeywordArgument) {
1334           final PyKeywordArgument argument = (PyKeywordArgument)expression;
1335           if (PyNames.METACLASS.equals(argument.getKeyword())) {
1336             return argument.getValueExpression();
1337           }
1338         }
1339       }
1340     }
1341     else {
1342       final PyTargetExpression attribute = findClassAttribute(PyNames.DUNDER_METACLASS, false);
1343       if (attribute != null) {
1344         return attribute.findAssignedValue();
1345       }
1346     }
1347     return null;
1348   }
1349
1350   @NotNull
1351   private List<PyClassLikeType> getMROAncestorTypes(@NotNull TypeEvalContext context) throws MROException {
1352     final PyType thisType = context.getType(this);
1353     if (thisType instanceof PyClassLikeType) {
1354       final PyClassLikeType thisClassLikeType = (PyClassLikeType)thisType;
1355       final List<PyClassLikeType> ancestorTypes = mroLinearize(thisClassLikeType, false, context, new HashMap<PyClassLikeType, Object>());
1356       if (isOverriddenMRO(ancestorTypes, context)) {
1357         ancestorTypes.add(null);
1358       }
1359       return ancestorTypes;
1360     }
1361     else {
1362       return Collections.emptyList();
1363     }
1364   }
1365
1366   private boolean isOverriddenMRO(@NotNull List<PyClassLikeType> ancestorTypes, @NotNull TypeEvalContext context) {
1367     final List<PyClass> classes = new ArrayList<PyClass>();
1368     classes.add(this);
1369     for (PyClassLikeType ancestorType : ancestorTypes) {
1370       if (ancestorType instanceof PyClassType) {
1371         final PyClassType classType = (PyClassType)ancestorType;
1372         classes.add(classType.getPyClass());
1373       }
1374     }
1375
1376     final PyClass typeClass = PyBuiltinCache.getInstance(this).getClass("type");
1377
1378     for (PyClass cls : classes) {
1379       final PyType metaClassType = cls.getMetaClassType(context);
1380       if (metaClassType instanceof PyClassType) {
1381         final PyClass metaClass = ((PyClassType)metaClassType).getPyClass();
1382         if (cls == metaClass) {
1383           return false;
1384         }
1385         final PyFunction mroMethod = metaClass.findMethodByName(PyNames.MRO, true);
1386         if (mroMethod != null) {
1387           final PyClass mroClass = mroMethod.getContainingClass();
1388           if (mroClass != null && mroClass != typeClass) {
1389             return true;
1390           }
1391         }
1392       }
1393     }
1394
1395     return false;
1396   }
1397
1398   @NotNull
1399   private List<PyClassLikeType> getOldStyleAncestorTypes(@NotNull TypeEvalContext context) {
1400     final List<PyClassLikeType> results = new ArrayList<PyClassLikeType>();
1401     final Deque<PyClassLikeType> toProcess = new LinkedList<PyClassLikeType>();
1402     final Set<PyClassLikeType> seen = new HashSet<PyClassLikeType>();
1403     final Set<PyClassLikeType> visited = new HashSet<PyClassLikeType>();
1404     final PyType thisType = context.getType(this);
1405     if (thisType instanceof PyClassLikeType) {
1406       toProcess.add((PyClassLikeType)thisType);
1407     }
1408     while (!toProcess.isEmpty()) {
1409       final PyClassLikeType currentType = toProcess.pollFirst();
1410       if (!visited.add(currentType)) {
1411         continue;
1412       }
1413       for (PyClassLikeType superType : currentType.getSuperClassTypes(context)) {
1414         if (superType == null || !seen.contains(superType)) {
1415           results.add(superType);
1416           seen.add(superType);
1417         }
1418         if (superType != null && !visited.contains(superType)) {
1419           toProcess.addLast(superType);
1420         }
1421       }
1422     }
1423     return results;
1424   }
1425
1426   @Nullable
1427   private static PsiElement getElementQNamed(@NotNull PyFile file, @NotNull QualifiedName qualifiedName, @NotNull TypeEvalContext context) {
1428     final int componentCount = qualifiedName.getComponentCount();
1429     final String fullName = qualifiedName.toString();
1430     final PyType type = new PyModuleType(file);
1431     if (componentCount == 0) {
1432       return null;
1433     }
1434     else if (componentCount == 1) {
1435       PsiElement element = resolveTypeMember(type, fullName, context);
1436       if (element == null) {
1437         element = PyBuiltinCache.getInstance(file).getByName(fullName);
1438       }
1439       return element;
1440     }
1441     else {
1442       final String name = qualifiedName.getLastComponent();
1443       final QualifiedName containingQName = qualifiedName.removeLastComponent();
1444       PyType currentType = type;
1445       for (String component : containingQName.getComponents()) {
1446         currentType = getMemberType(currentType, component, context);
1447         if (currentType == null) {
1448           return null;
1449         }
1450       }
1451       if (name != null) {
1452         return resolveTypeMember(currentType, name, context);
1453       }
1454       return null;
1455     }
1456   }
1457
1458   @Nullable
1459   private static PyType getMemberType(@NotNull PyType type, @NotNull String name, @NotNull TypeEvalContext context) {
1460     final PyType result;
1461     PsiElement element = resolveTypeMember(type, name, context);
1462     if (element instanceof PyImportedModule) {
1463       result = new PyImportedModuleType((PyImportedModule)element);
1464     }
1465     else if (element instanceof PyTypedElement) {
1466       result = context.getType((PyTypedElement)element);
1467     }
1468     else {
1469       return null;
1470     }
1471     if (result instanceof PyClassLikeType) {
1472       return ((PyClassLikeType)result).toInstance();
1473     }
1474     return result;
1475   }
1476
1477   @Nullable
1478   private static PsiElement resolveTypeMember(@NotNull PyType type, @NotNull String name, @NotNull TypeEvalContext context) {
1479     final PyResolveContext resolveContext = PyResolveContext.noImplicits().withTypeEvalContext(context);
1480     final List<? extends RatedResolveResult> results = type.resolveMember(name, null, AccessDirection.READ, resolveContext);
1481     return (results != null && !results.isEmpty()) ? results.get(0).getElement() : null;
1482   }
1483
1484   @Nullable
1485   private static PyClassLikeType classTypeFromQName(@NotNull QualifiedName qualifiedName, @NotNull PyFile containingFile,
1486                                                     @NotNull TypeEvalContext context) {
1487     final PsiElement element = getElementQNamed(containingFile, qualifiedName, context);
1488     if (element instanceof PyTypedElement) {
1489       final PyType type = context.getType((PyTypedElement)element);
1490       if (type instanceof PyClassLikeType) {
1491         return (PyClassLikeType)type;
1492       }
1493     }
1494     return null;
1495   }
1496
1497   @Nullable
1498   @Override
1499   public PyClassLikeType getType(@NotNull TypeEvalContext context) {
1500     return PyUtil.as(context.getType(this), PyClassLikeType.class);
1501   }
1502 }