path: root/python/src/com/jetbrains/python/psi/resolve/PyResolveUtil.java

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

import com.intellij.lang.ASTNode;
import com.intellij.lang.FileASTNode;
import com.intellij.openapi.progress.ProgressManager;
import com.intellij.openapi.util.Condition;
import com.intellij.psi.PsiElement;
import com.intellij.psi.PsiFile;
import com.intellij.psi.PsiNamedElement;
import com.intellij.psi.ResolveState;
import com.intellij.psi.impl.source.tree.TreeUtil;
import com.intellij.psi.scope.PsiScopeProcessor;
import com.intellij.psi.tree.TokenSet;
import com.intellij.psi.util.PsiTreeUtil;
import com.jetbrains.python.PyElementTypes;
import com.jetbrains.python.PythonDialectsTokenSetProvider;
import com.jetbrains.python.codeInsight.controlflow.ControlFlowCache;
import com.jetbrains.python.codeInsight.controlflow.ScopeOwner;
import com.jetbrains.python.codeInsight.dataflow.scope.Scope;
import com.jetbrains.python.codeInsight.dataflow.scope.ScopeUtil;
import com.jetbrains.python.psi.*;
import com.jetbrains.python.psi.impl.PyPsiUtils;
import org.jetbrains.annotations.NotNull;
import org.jetbrains.annotations.Nullable;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

/**
 * Ref resolution routines.
 * User: dcheryasov
 * Date: 14.06.2005
 */
public class PyResolveUtil {

  private PyResolveUtil() {
  }


  /**
   * Returns closest previous node of given class, as input file would have it.
   *
   * @param elt          node from which to look for a previous statement.
   * @param elementTypes selected element types.
   * @return previous statement, or null.
   */
  @Nullable
  private static PsiElement getPrevNodeOf(PsiElement elt, TokenSet elementTypes) {
    ASTNode seeker = elt.getNode();
    while (seeker != null) {
      ASTNode feeler = seeker.getTreePrev();
      if (feeler != null &&
          (feeler.getElementType() == PyElementTypes.FUNCTION_DECLARATION ||
           feeler.getElementType() == PyElementTypes.CLASS_DECLARATION) &&
          elementTypes.contains(feeler.getElementType())) {
        return feeler.getPsi();
      }
      if (feeler != null) {
        seeker = TreeUtil.getLastChild(feeler);
      }
      else { // we were the first subnode
        // find something above the parent node we've not exhausted yet
        seeker = seeker.getTreeParent();
        if (seeker instanceof FileASTNode) return null; // all file nodes have been looked up, in vain
      }
      if (seeker != null && elementTypes.contains(seeker.getElementType())) {
        return seeker.getPsi();
      }
    }
    // here elt is null or a PsiFile is not up in the parent chain.
    return null;
  }

  @Nullable
  private static PsiElement getPrevNodeOf(PsiElement elt) {
    if (elt instanceof PsiFile) return null;  // no sense to get the previous node of a file
    return getPrevNodeOf(elt, PythonDialectsTokenSetProvider.INSTANCE.getNameDefinerTokens());
  }

  /**
   * Crawls up scopes of the PSI tree, checking named elements and name definers.
   */
  public static void scopeCrawlUp(@NotNull PsiScopeProcessor processor, @NotNull PsiElement element, @Nullable String name,
                                  @Nullable PsiElement roof) {
    // Use real context here to enable correct completion and resolve in case of PyExpressionCodeFragment!!!
    final PsiElement realContext = PyPsiUtils.getRealContext(element);
    final ScopeOwner originalOwner;
    if (realContext != element && realContext instanceof PyFile) {
      originalOwner = (PyFile)realContext;
    }
    else {
      originalOwner = ScopeUtil.getScopeOwner(realContext);
    }
    final PsiElement parent = element.getParent();
    final boolean isGlobalOrNonlocal = parent instanceof PyGlobalStatement || parent instanceof PyNonlocalStatement;
    ScopeOwner owner = originalOwner;
    if (isGlobalOrNonlocal) {
      final ScopeOwner outerScopeOwner = ScopeUtil.getScopeOwner(owner);
      if (outerScopeOwner != null) {
        owner = outerScopeOwner;
      }
    }
    scopeCrawlUp(processor, owner, originalOwner, name, roof, realContext);
  }

  public static void scopeCrawlUp(@NotNull PsiScopeProcessor processor, @NotNull ScopeOwner scopeOwner, @Nullable String name,
                                  @Nullable PsiElement roof) {
    scopeCrawlUp(processor, scopeOwner, scopeOwner, name, roof, null);
  }

  public static void scopeCrawlUp(@NotNull PsiScopeProcessor processor, @Nullable ScopeOwner scopeOwner,
                                  @Nullable ScopeOwner originalScopeOwner, @Nullable String name, @Nullable PsiElement roof,
                                  @Nullable final PsiElement anchor) {
    while (scopeOwner != null) {
      if (!(scopeOwner instanceof PyClass) || scopeOwner == originalScopeOwner) {
        final Scope scope = ControlFlowCache.getScope(scopeOwner);
        boolean found = false;
        if (name != null) {
          final PsiElement resolved = scope.getNamedElement(name);
          if (resolved != null) {
            if (!processor.execute(resolved, ResolveState.initial())) {
              found = true;
            }
          }
        }
        else {
          for (PsiNamedElement element : scope.getNamedElements()) {
            if (!processor.execute(element, ResolveState.initial())) {
              found = true;
              break;
            }
          }
        }
        List<NameDefiner> definers = new ArrayList<NameDefiner>(scope.getImportedNameDefiners());
        if (anchor != null && ScopeUtil.getScopeOwner(anchor) == scopeOwner) {
          final Comparator<NameDefiner> nearestDefinerComparator = new Comparator<NameDefiner>() {
            @Override
            public int compare(NameDefiner a, NameDefiner b) {
              final boolean aIsBefore = PyPsiUtils.isBefore(a, anchor);
              final boolean bIsBefore = PyPsiUtils.isBefore(b, anchor);
              final int diff = a.getTextOffset() - b.getTextOffset();
              if (aIsBefore && bIsBefore) {
                return -diff;
              }
              else if (aIsBefore) {
                return -1;
              }
              else if (bIsBefore) {
                return 1;
              }
              else {
                return diff;
              }
            }
          };
          Collections.sort(definers, nearestDefinerComparator);
        }
        for (NameDefiner definer : definers) {
          if (!processor.execute(definer, ResolveState.initial())) {
            found = true;
            break;
          }
        }
        if (found) {
          return;
        }
      }
      if (scopeOwner == roof) {
        return;
      }
      scopeOwner = ScopeUtil.getScopeOwner(scopeOwner);
    }
  }

  /**
   * Crawls up the PSI tree, checking nodes as if crawling backwards through source lexemes.
   *
   * @param processor a visitor that says when the crawl is done and collects info.
   * @param elt       element from which we start (not checked by processor); if null, the search immediately returns null.
   * @return first element that the processor accepted.
   *
   * @deprecated Use {@link #scopeCrawlUp} instead.
   */
  @Deprecated
  @Nullable
  public static PsiElement treeCrawlUp(PsiScopeProcessor processor, PsiElement elt) {
    if (elt == null || !elt.isValid()) return null; // can't find anyway.
    PsiElement seeker = elt;
    PsiElement cap = PyUtil.getConcealingParent(elt);
    PyFunction capFunction = cap != null ? PsiTreeUtil.getParentOfType(cap, PyFunction.class, false) : null;
    final boolean is_outside_param_list = PsiTreeUtil.getParentOfType(elt, PyParameterList.class) == null;
    do {
      ProgressManager.checkCanceled();
      seeker = getPrevNodeOf(seeker);
      // aren't we in the same defining assignment, global, etc?
      if ((seeker instanceof NameDefiner) && ((NameDefiner)seeker).mustResolveOutside() && PsiTreeUtil.isAncestor(seeker, elt, true)) {
        seeker = getPrevNodeOf(seeker);
      }
      // maybe we're under a cap?
      while (true) {
        PsiElement local_cap = PyUtil.getConcealingParent(seeker);
        if (local_cap == null) break; // seeker is in global context
        if (local_cap == cap) break; // seeker is in the same context as elt
        if ((cap != null) && PsiTreeUtil.isAncestor(local_cap, cap, true)) break; // seeker is in a context above elt's
        if (
          (local_cap != elt) && // elt isn't the cap of seeker itself
          ((cap == null) || !PsiTreeUtil.isAncestor(local_cap, cap, true)) // elt's cap is not under local cap
          ) { // only look at local cap and above
          if (local_cap instanceof NameDefiner) {
            seeker = local_cap;
          }
          else {
            seeker = getPrevNodeOf(local_cap);
          }
        }
        else {
          break;
        } // seeker is contextually under elt already
      }
      // maybe we're capped by a class? param lists are not capped though syntactically inside the function.
      if (is_outside_param_list && refersFromMethodToClass(capFunction, seeker)) continue;
      // names defined in a comprehension element are only visible inside it or the list comp expressions directly above it
      if (seeker instanceof PyComprehensionElement && !PsiTreeUtil.isAncestor(seeker, elt, false)) {
        continue;
      }
      // check what we got
      if (seeker != null) {
        if (!processor.execute(seeker, ResolveState.initial())) {
          if (processor instanceof ResolveProcessor) {
            return ((ResolveProcessor)processor).getResult();
          }
          else {
            return seeker;
          } // can't point to exact element, but somewhere here
        }
      }
    }
    while (seeker != null);
    if (processor instanceof ResolveProcessor) {
      return ((ResolveProcessor)processor).getResult();
    }
    return null;
  }

  /**
   * @param innerFunction a method, presumably inside the class
   * @param outer an element presumably in the class context.
   * @return true if an outer element is in a class context, while the inner is a method or function inside it.
   * @see com.jetbrains.python.psi.PyUtil#getConcealingParent(com.intellij.psi.PsiElement)
   */
  private static boolean refersFromMethodToClass(final PyFunction innerFunction, final PsiElement outer) {
    if (innerFunction == null) {
      return false;
    }
    PsiElement outerClass = PyUtil.getConcealingParent(outer);
    if (outerClass instanceof PyClass &&   // outer is in a class context
       innerFunction.getContainingClass() == outerClass) {   // inner is a function or method within the class
      return true;
    }
    return false;
  }

  /**
   * Accepts only targets that are not the given object.
   */
  public static class FilterNotInstance implements Condition<PsiElement> {
    Object instance;

    public FilterNotInstance(Object instance) {
      this.instance = instance;
    }

    public boolean value(final PsiElement target) {
      return (instance != target);
    }

  }
}