do not resolve relative import as absolute if corresponding virtualFile is null
[idea/community.git] / python / src / com / jetbrains / python / psi / resolve / ResolveImportUtil.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.resolve;
17
18 import com.intellij.openapi.extensions.Extensions;
19 import com.intellij.openapi.fileTypes.ExtensionFileNameMatcher;
20 import com.intellij.openapi.fileTypes.FileNameMatcher;
21 import com.intellij.openapi.fileTypes.FileTypeManager;
22 import com.intellij.openapi.module.Module;
23 import com.intellij.openapi.module.ModuleUtilCore;
24 import com.intellij.openapi.projectRoots.Sdk;
25 import com.intellij.openapi.roots.FileIndexFacade;
26 import com.intellij.openapi.util.io.FileUtil;
27 import com.intellij.openapi.vfs.VirtualFile;
28 import com.intellij.psi.PsiDirectory;
29 import com.intellij.psi.PsiElement;
30 import com.intellij.psi.PsiFile;
31 import com.intellij.psi.PsiInvalidElementAccessException;
32 import com.intellij.psi.util.PsiTreeUtil;
33 import com.intellij.psi.util.QualifiedName;
34 import com.intellij.util.containers.HashSet;
35 import com.jetbrains.python.PyNames;
36 import com.jetbrains.python.PythonFileType;
37 import com.jetbrains.python.psi.*;
38 import com.jetbrains.python.psi.impl.*;
39 import com.jetbrains.python.psi.types.PyModuleType;
40 import com.jetbrains.python.psi.types.PyType;
41 import org.jetbrains.annotations.NotNull;
42 import org.jetbrains.annotations.Nullable;
43
44 import java.util.ArrayList;
45 import java.util.Collections;
46 import java.util.List;
47 import java.util.Set;
48
49 import static com.jetbrains.python.psi.FutureFeature.ABSOLUTE_IMPORT;
50
51 /**
52  * @author dcheryasov
53  */
54 public class ResolveImportUtil {
55   private ResolveImportUtil() {
56   }
57
58   private static final ThreadLocal<Set<String>> ourBeingImported = new ThreadLocal<Set<String>>() {
59     @Override
60     protected Set<String> initialValue() {
61       return new HashSet<String>();
62     }
63   };
64
65   public static boolean isAbsoluteImportEnabledFor(PsiElement foothold) {
66     if (foothold != null) {
67       PsiFile file = foothold.getContainingFile();
68       if (file instanceof PyFile) {
69         final PyFile pyFile = (PyFile)file;
70         if (pyFile.getLanguageLevel().isPy3K()) {
71           return true;
72         }
73         return pyFile.hasImportFromFuture(ABSOLUTE_IMPORT);
74       }
75     }
76     // if the relevant import is below the foothold, it is either legal or we've detected the offending statement already
77     return false;
78   }
79
80
81   /**
82    * Finds a directory that many levels above a given file, making sure that every level has an __init__.py.
83    *
84    * @param base  file that works as a reference.
85    * @param depth must be positive, 1 means the dir that contains base, 2 is one dir above, etc.
86    * @return found directory, or null.
87    */
88   @Nullable
89   public static PsiDirectory stepBackFrom(PsiFile base, int depth) {
90     if (depth == 0) {
91       return base.getContainingDirectory();
92     }
93     PsiDirectory result;
94     if (base != null) {
95       base = base.getOriginalFile(); // just to make sure
96       result = base.getContainingDirectory();
97       int count = 1;
98       while (result != null && PyUtil.isPackage(result, base)) {
99         if (count >= depth) return result;
100         result = result.getParentDirectory();
101         count += 1;
102       }
103     }
104     return null;
105   }
106
107   @Nullable
108   public static PsiElement resolveImportElement(PyImportElement importElement, @NotNull final QualifiedName qName) {
109     List<RatedResolveResult> targets;
110     final PyStatement importStatement = importElement.getContainingImportStatement();
111     if (importStatement instanceof PyFromImportStatement) {
112       targets = resolveNameInFromImport((PyFromImportStatement)importStatement, qName);
113     }
114     else { // "import foo"
115       targets = resolveNameInImportStatement(importElement, qName);
116     }
117     final List<RatedResolveResult> resultList = RatedResolveResult.sorted(targets);
118     return resultList.size() > 0 ? resultList.get(0).getElement() : null;
119   }
120
121   public static List<RatedResolveResult> resolveNameInImportStatement(PyImportElement importElement, @NotNull QualifiedName qName) {
122     final PsiFile file = importElement.getContainingFile().getOriginalFile();
123     boolean absoluteImportEnabled = isAbsoluteImportEnabledFor(importElement);
124     final List<PsiElement> modules = resolveModule(qName, file, absoluteImportEnabled, 0);
125     return rateResults(modules);
126   }
127
128   public static List<RatedResolveResult> resolveNameInFromImport(PyFromImportStatement importStatement, @NotNull QualifiedName qName) {
129     PsiFile file = importStatement.getContainingFile().getOriginalFile();
130     String name = qName.getComponents().get(0);
131
132     final List<PsiElement> candidates = importStatement.resolveImportSourceCandidates();
133     List<PsiElement> resultList = new ArrayList<PsiElement>();
134     for (PsiElement candidate : candidates) {
135       if (!candidate.isValid()) {
136         throw new PsiInvalidElementAccessException(candidate, "Got an invalid candidate from resolveImportSourceCandidates(): " + candidate.getClass());
137       }
138       if (candidate instanceof PsiDirectory) {
139         candidate = PyUtil.getPackageElement((PsiDirectory)candidate, importStatement);
140       }
141       PsiElement result = resolveChild(candidate, name, file, false, true);
142       if (result != null) {
143         if (!result.isValid()) {
144           throw new PsiInvalidElementAccessException(result, "Got an invalid candidate from resolveChild(): " + result.getClass());
145         }
146         resultList.add(result);
147       }
148     }
149     if (!resultList.isEmpty()) {
150       return rateResults(resultList);
151     }
152     return Collections.emptyList();
153   }
154
155   @NotNull
156   public static List<PsiElement> resolveFromImportStatementSource(PyFromImportStatement from_import_statement, QualifiedName qName) {
157     boolean absoluteImportEnabled = isAbsoluteImportEnabledFor(from_import_statement);
158     PsiFile file = from_import_statement.getContainingFile();
159     return resolveModule(qName, file, absoluteImportEnabled, from_import_statement.getRelativeLevel());
160   }
161
162   /**
163    * Resolves a module reference in a general case.
164    *
165    *
166    * @param qualifiedName     qualified name of the module reference to resolve
167    * @param sourceFile        where that reference resides; serves as PSI foothold to determine module, project, etc.
168    * @param importIsAbsolute  if false, try old python 2.x's "relative first, absolute next" approach.
169    * @param relativeLevel     if > 0, step back from sourceFile and resolve from there (even if importIsAbsolute is false!).
170    * @return list of possible candidates
171    */
172   @NotNull
173   public static List<PsiElement> resolveModule(@Nullable QualifiedName qualifiedName, PsiFile sourceFile,
174                                                boolean importIsAbsolute, int relativeLevel) {
175     if (qualifiedName == null || sourceFile == null) {
176       return Collections.emptyList();
177     }
178     final String marker = qualifiedName + "#" + Integer.toString(relativeLevel);
179     final Set<String> beingImported = ourBeingImported.get();
180     if (beingImported.contains(marker)) {
181       return Collections.emptyList(); // break endless loop in import
182     }
183     try {
184       beingImported.add(marker);
185       final QualifiedNameResolver visitor = new QualifiedNameResolverImpl(qualifiedName).fromElement(sourceFile);
186       if (relativeLevel > 0) {
187         // "from ...module import"
188         visitor.withRelative(relativeLevel).withoutRoots();
189       }
190       else {
191         // "from module import"
192         if (!importIsAbsolute) {
193           visitor.withRelative(0);
194         }
195       }
196       List<PsiElement> results = visitor.resultsAsList();
197       if (results.isEmpty() && relativeLevel == 0 && !importIsAbsolute) {
198         results = resolveRelativeImportAsAbsolute(sourceFile, qualifiedName);
199       }
200       return results;
201     }
202     finally {
203       beingImported.remove(marker);
204     }
205   }
206
207   /**
208    * Try to resolve relative import as absolute in roots, not in its parent directory.
209    *
210    * This may be useful for resolving to child skeleton modules located in other directories.
211    *
212    * @param foothold        foothold file.
213    * @param qualifiedName   relative import name.
214    * @return                list of resolved elements.
215    */
216   @NotNull
217   private static List<PsiElement> resolveRelativeImportAsAbsolute(@NotNull PsiFile foothold,
218                                                                   @NotNull QualifiedName qualifiedName) {
219     final VirtualFile virtualFile = foothold.getVirtualFile();
220     if (virtualFile == null) return Collections.emptyList();
221     final boolean inSource = FileIndexFacade.getInstance(foothold.getProject()).isInContent(virtualFile);
222     if (inSource) return Collections.emptyList();
223     final PsiDirectory containingDirectory = foothold.getContainingDirectory();
224     if (containingDirectory != null) {
225       final QualifiedName containingPath = QualifiedNameFinder.findCanonicalImportPath(containingDirectory, null);
226       if (containingPath != null && containingPath.getComponentCount() > 0) {
227         final QualifiedName absolutePath = containingPath.append(qualifiedName.toString());
228         final QualifiedNameResolver absoluteVisitor = new QualifiedNameResolverImpl(absolutePath).fromElement(foothold);
229         return absoluteVisitor.resultsAsList();
230       }
231     }
232     return Collections.emptyList();
233   }
234
235   @Nullable
236   public static PsiElement resolveModuleInRoots(@NotNull QualifiedName moduleQualifiedName, @Nullable PsiElement foothold) {
237     if (foothold == null) return null;
238     QualifiedNameResolver visitor = new QualifiedNameResolverImpl(moduleQualifiedName).fromElement(foothold);
239     return visitor.firstResult();
240   }
241
242   @Nullable
243   static PythonPathCache getPathCache(PsiElement foothold) {
244     PythonPathCache cache = null;
245     final Module module = ModuleUtilCore.findModuleForPsiElement(foothold);
246     if (module != null) {
247       cache = PythonModulePathCache.getInstance(module);
248     }
249     else {
250       final Sdk sdk = PyBuiltinCache.findSdkForFile(foothold.getContainingFile());
251       if (sdk != null) {
252         cache = PythonSdkPathCache.getInstance(foothold.getProject(), sdk);
253       }
254     }
255     return cache;
256   }
257
258   /**
259    * Tries to find referencedName under the parent element. Used to resolve any names that look imported.
260    * Parent might happen to be a PyFile(__init__.py), then it is treated <i>both</i> as a file and as ist base dir.
261    *
262    * @param parent          element under which to look for referenced name; if null, null is returned.
263    * @param referencedName  which name to look for.
264    * @param containingFile  where we're in.
265    * @param fileOnly        if true, considers only a PsiFile child as a valid result; non-file hits are ignored.
266    * @param checkForPackage if true, directories are returned only if they contain __init__.py
267    * @return the element the referencedName resolves to, or null.
268    * @todo: Honor module's __all__ value.
269    * @todo: Honor package's __path__ value (hard).
270    */
271   @Nullable
272   public static PsiElement resolveChild(@Nullable final PsiElement parent, @NotNull final String referencedName,
273                                         @Nullable final PsiFile containingFile, boolean fileOnly, boolean checkForPackage) {
274     PsiDirectory dir = null;
275     PsiElement ret = null;
276     PsiElement possible_ret = null;
277     final PyResolveContext resolveContext = PyResolveContext.defaultContext();
278     if (parent instanceof PyFileImpl) {
279       if (PyNames.INIT_DOT_PY.equals(((PyFile)parent).getName())) {
280         // gobject does weird things like '_gobject = sys.modules['gobject._gobject'], so it's preferable to look at
281         // files before looking at names exported from __init__.py
282         dir = ((PyFile)parent).getContainingDirectory();
283         possible_ret = resolveInDirectory(referencedName, containingFile, dir, fileOnly, checkForPackage);
284       }
285
286       // OTOH, quite often a module named foo exports a class or function named foo, which is used as a fallback
287       // by a module one level higher (e.g. curses.set_key). Prefer it to submodule if possible.
288       final PyModuleType moduleType = new PyModuleType((PyFile)parent);
289       final List<? extends RatedResolveResult> results = moduleType.resolveMember(referencedName, null, AccessDirection.READ,
290                                                                                   resolveContext);
291       final PsiElement moduleMember = results != null && !results.isEmpty() ? results.get(0).getElement() : null;
292       if (!fileOnly || PyUtil.instanceOf(moduleMember, PsiFile.class, PsiDirectory.class)) {
293         ret = moduleMember;
294       }
295       if (ret != null && !PyUtil.instanceOf(ret, PsiFile.class, PsiDirectory.class) &&
296           PsiTreeUtil.getStubOrPsiParentOfType(ret, PyExceptPart.class) == null) {
297         return ret;
298       }
299
300       if (possible_ret != null) return possible_ret;
301     }
302     else if (parent instanceof PsiDirectory) {
303       dir = (PsiDirectory)parent;
304     }
305     else if (parent != null) {
306       PyType refType = PyReferenceExpressionImpl.getReferenceTypeFromProviders(parent, resolveContext.getTypeEvalContext(), null);
307       if (refType != null) {
308         final List<? extends RatedResolveResult> result = refType.resolveMember(referencedName, null, AccessDirection.READ, resolveContext);
309         if (result != null && !result.isEmpty()) {
310           return result.get(0).getElement();
311         }
312       }
313     }
314     if (dir != null) {
315       final PsiElement result = resolveInDirectory(referencedName, containingFile, dir, fileOnly, checkForPackage);
316       //if (fileOnly && ! (result instanceof PsiFile) && ! (result instanceof PsiDirectory)) return null;
317       if (result != null) {
318         return result;
319       }
320       if (parent instanceof PsiFile) {
321         final List<PsiElement> items = resolveRelativeImportAsAbsolute((PsiFile)parent,
322                                                                        QualifiedName.fromComponents(referencedName));
323         if (!items.isEmpty()) {
324           return items.get(0);
325         }
326       }
327     }
328     return ret;
329   }
330
331   @Nullable
332   private static PsiElement resolveInDirectory(final String referencedName, @Nullable final PsiFile containingFile,
333                                                final PsiDirectory dir, boolean isFileOnly, boolean checkForPackage) {
334     if (referencedName == null) return null;
335
336     final PsiDirectory subdir = dir.findSubdirectory(referencedName);
337     if (subdir != null && (!checkForPackage || PyUtil.isPackage(subdir, containingFile))) {
338       return subdir;
339     }
340
341     final PsiFile module = findPyFileInDir(dir, referencedName);
342     if (module != null) return module;
343
344     if (!isFileOnly) {
345       // not a subdir, not a file; could be a name in parent/__init__.py
346       final PsiFile initPy = dir.findFile(PyNames.INIT_DOT_PY);
347       if (initPy == containingFile) return null; // don't dive into the file we're in
348       if (initPy instanceof PyFile) {
349         return ((PyFile)initPy).getElementNamed(referencedName);
350       }
351     }
352     return null;
353   }
354
355   @Nullable
356   private static PsiFile findPyFileInDir(PsiDirectory dir, String referencedName) {
357     PsiFile file = dir.findFile(referencedName + PyNames.DOT_PY);
358     if (file == null) {
359       final List<FileNameMatcher> associations = FileTypeManager.getInstance().getAssociations(PythonFileType.INSTANCE);
360       for (FileNameMatcher association : associations) {
361         if (association instanceof ExtensionFileNameMatcher) {
362           file = dir.findFile(referencedName + "." + ((ExtensionFileNameMatcher)association).getExtension());
363           if (file != null) break;
364         }
365       }
366     }
367     if (file != null && FileUtil.getNameWithoutExtension(file.getName()).equals(referencedName)) {
368       return file;
369     }
370     return null;
371   }
372
373   public static ResolveResultList rateResults(List<? extends PsiElement> targets) {
374     ResolveResultList ret = new ResolveResultList();
375     for (PsiElement target : targets) {
376       if (target instanceof PsiDirectory) {
377         target = PyUtil.getPackageElement((PsiDirectory)target, null);
378       }
379       if (target != null) {   // Ignore non-package dirs, worthless
380         int rate = RatedResolveResult.RATE_HIGH;
381         if (target instanceof PyFile) {
382           VirtualFile vFile = ((PyFile)target).getVirtualFile();
383           if (vFile != null && vFile.getLength() > 0) {
384             rate += 100;
385           }
386           for (PyResolveResultRater rater : Extensions.getExtensions(PyResolveResultRater.EP_NAME)) {
387             rate += rater.getRate(target);
388           }
389         }
390         ret.poke(target, rate);
391       }
392     }
393     return ret;
394   }
395
396   /**
397    * @param element what we test (identifier, reference, import element, etc)
398    * @return the how the element relates to an enclosing import statement, if any
399    * @see com.jetbrains.python.psi.resolve.PointInImport
400    */
401   @NotNull
402   public static PointInImport getPointInImport(@NotNull PsiElement element) {
403     final PsiElement parent = PsiTreeUtil.getNonStrictParentOfType(element, PyImportElement.class, PyFromImportStatement.class);
404     if (parent instanceof PyFromImportStatement) {
405       return PointInImport.AS_MODULE; // from foo ...
406     }
407     if (parent instanceof PyImportElement) {
408       final PsiElement statement = parent.getParent();
409       if (statement instanceof PyImportStatement) {
410         return PointInImport.AS_MODULE; // import foo,...
411       }
412       else if (statement instanceof PyFromImportStatement) {
413         return PointInImport.AS_NAME;
414       }
415     }
416     return PointInImport.NONE;
417   }
418 }