diff options
2 files changed, 556 insertions, 0 deletions
diff --git a/kotlin-analysis/src/main/kotlin/org/jetbrains/dokka/analysis/JvmDependenciesIndexImpl.kt b/kotlin-analysis/src/main/kotlin/org/jetbrains/dokka/analysis/JvmDependenciesIndexImpl.kt new file mode 100644 index 00000000..021c6292 --- /dev/null +++ b/kotlin-analysis/src/main/kotlin/org/jetbrains/dokka/analysis/JvmDependenciesIndexImpl.kt @@ -0,0 +1,251 @@ +/* + * Copyright 2010-2016 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 org.jetbrains.kotlin.cli.jvm.index + +import com.intellij.ide.highlighter.JavaClassFileType +import com.intellij.ide.highlighter.JavaFileType +import com.intellij.openapi.vfs.VfsUtilCore +import com.intellij.openapi.vfs.VirtualFile +import com.intellij.util.containers.IntArrayList +import gnu.trove.THashMap +import org.jetbrains.kotlin.name.ClassId +import org.jetbrains.kotlin.name.FqName +import java.util.* + +// speeds up finding files/classes in classpath/java source roots +// NOT THREADSAFE, needs to be adapted/removed if we want compiler to be multithreaded +// the main idea of this class is for each package to store roots which contains it to avoid excessive file system traversal +class JvmDependenciesIndexImpl(_roots: List<JavaRoot>) : JvmDependenciesIndex { + //these fields are computed based on _roots passed to constructor which are filled in later + private val roots: List<JavaRoot> by lazy { _roots.toList() } + + private val maxIndex: Int + get() = roots.size + + // each "Cache" object corresponds to a package + private class Cache { + private val innerPackageCaches = HashMap<String, Cache>() + + operator fun get(name: String) = innerPackageCaches.getOrPut(name, ::Cache) + + // indices of roots that are known to contain this package + // if this list contains [1, 3, 5] then roots with indices 1, 3 and 5 are known to contain this package, 2 and 4 are known not to (no information about roots 6 or higher) + // if this list contains maxIndex that means that all roots containing this package are known + val rootIndices = IntArrayList(2) + } + + // root "Cache" object corresponds to DefaultPackage which exists in every root. Roots with non-default fqname are also listed here but + // they will be ignored on requests with invalid fqname prefix. + private val rootCache: Cache by lazy { + Cache().apply { + roots.indices.forEach(rootIndices::add) + rootIndices.add(maxIndex) + rootIndices.trimToSize() + } + } + + // holds the request and the result last time we searched for class + // helps improve several scenarios, LazyJavaResolverContext.findClassInJava being the most important + private var lastClassSearch: Pair<FindClassRequest, SearchResult>? = null + + override val indexedRoots by lazy { roots.asSequence() } + + private val packageCache: Array<out MutableMap<String, VirtualFile?>> by lazy { + Array(roots.size) { THashMap<String, VirtualFile?>() } + } + + override fun traverseDirectoriesInPackage( + packageFqName: FqName, + acceptedRootTypes: Set<JavaRoot.RootType>, + continueSearch: (VirtualFile, JavaRoot.RootType) -> Boolean + ) { + search(TraverseRequest(packageFqName, acceptedRootTypes)) { dir, rootType -> + if (continueSearch(dir, rootType)) null else Unit + } + } + + // findClassGivenDirectory MUST check whether the class with this classId exists in given package + override fun <T : Any> findClass( + classId: ClassId, + acceptedRootTypes: Set<JavaRoot.RootType>, + findClassGivenDirectory: (VirtualFile, JavaRoot.RootType) -> T? + ): T? { + // make a decision based on information saved from last class search + if (lastClassSearch?.first?.classId != classId) { + return search(FindClassRequest(classId, acceptedRootTypes), findClassGivenDirectory) + } + + val (cachedRequest, cachedResult) = lastClassSearch!! + return when (cachedResult) { + is SearchResult.NotFound -> { + val limitedRootTypes = acceptedRootTypes - cachedRequest.acceptedRootTypes + if (limitedRootTypes.isEmpty()) { + null + } else { + search(FindClassRequest(classId, limitedRootTypes), findClassGivenDirectory) + } + } + is SearchResult.Found -> { + if (cachedRequest.acceptedRootTypes == acceptedRootTypes) { + findClassGivenDirectory(cachedResult.packageDirectory, cachedResult.root.type) + } else { + search(FindClassRequest(classId, acceptedRootTypes), findClassGivenDirectory) + } + } + } + } + + private fun <T : Any> search(request: SearchRequest, handler: (VirtualFile, JavaRoot.RootType) -> T?): T? { + // a list of package sub names, ["org", "jb", "kotlin"] + val packagesPath = request.packageFqName.pathSegments().map { it.identifier } + // a list of caches corresponding to packages, [default, "org", "org.jb", "org.jb.kotlin"] + val caches = cachesPath(packagesPath) + + var processedRootsUpTo = -1 + // traverse caches starting from last, which contains most specific information + + // NOTE: indices manipulation instead of using caches.reversed() is here for performance reasons + for (cacheIndex in caches.lastIndex downTo 0) { + val cacheRootIndices = caches[cacheIndex].rootIndices + for (i in 0..cacheRootIndices.size() - 1) { + val rootIndex = cacheRootIndices[i] + if (rootIndex <= processedRootsUpTo) continue // roots with those indices have been processed by now + + val directoryInRoot = travelPath(rootIndex, request.packageFqName, packagesPath, cacheIndex, caches) ?: continue + val root = roots[rootIndex] + if (root.type in request.acceptedRootTypes) { + val result = handler(directoryInRoot, root.type) + if (result != null) { + if (request is FindClassRequest) { + lastClassSearch = Pair(request, SearchResult.Found(directoryInRoot, root)) + } + return result + } + } + } + processedRootsUpTo = if (cacheRootIndices.isEmpty) processedRootsUpTo else cacheRootIndices.get(cacheRootIndices.size() - 1) + } + + if (request is FindClassRequest) { + lastClassSearch = Pair(request, SearchResult.NotFound) + } + return null + } + + // try to find a target directory corresponding to package represented by packagesPath in a given root represented by index + // possibly filling "Cache" objects with new information + private fun travelPath( + rootIndex: Int, + packageFqName: FqName, + packagesPath: List<String>, + fillCachesAfter: Int, + cachesPath: List<Cache> + ): VirtualFile? { + if (rootIndex >= maxIndex) { + for (i in (fillCachesAfter + 1)..(cachesPath.size - 1)) { + // we all know roots that contain this package by now + cachesPath[i].rootIndices.add(maxIndex) + cachesPath[i].rootIndices.trimToSize() + } + return null + } + + return synchronized(packageCache) { + packageCache[rootIndex].getOrPut(packageFqName.asString()) { + doTravelPath(rootIndex, packagesPath, fillCachesAfter, cachesPath) + } + } + } + + private fun doTravelPath(rootIndex: Int, packagesPath: List<String>, fillCachesAfter: Int, cachesPath: List<Cache>): VirtualFile? { + val pathRoot = roots[rootIndex] + val prefixPathSegments = pathRoot.prefixFqName?.pathSegments() + + var currentFile = pathRoot.file + + for (pathIndex in packagesPath.indices) { + val subPackageName = packagesPath[pathIndex] + if (prefixPathSegments != null && pathIndex < prefixPathSegments.size) { + // Traverse prefix first instead of traversing real directories + if (prefixPathSegments[pathIndex].identifier != subPackageName) { + return null + } + } else { + currentFile = currentFile.findChildPackage(subPackageName, pathRoot.type) ?: return null + } + + val correspondingCacheIndex = pathIndex + 1 + if (correspondingCacheIndex > fillCachesAfter) { + // subPackageName exists in this root + cachesPath[correspondingCacheIndex].rootIndices.add(rootIndex) + } + } + + return currentFile + } + + private fun VirtualFile.findChildPackage(subPackageName: String, rootType: JavaRoot.RootType): VirtualFile? { + val childDirectory = findChild(subPackageName) ?: return null + + val fileExtension = when (rootType) { + JavaRoot.RootType.BINARY -> JavaClassFileType.INSTANCE.defaultExtension + JavaRoot.RootType.SOURCE -> JavaFileType.INSTANCE.defaultExtension + } + + // If in addition to a directory "foo" there's a class file "foo.class" AND there are no classes anywhere in the directory "foo", + // then we ignore the directory and let the resolution choose the class "foo" instead. + if (findChild("$subPackageName.$fileExtension")?.isDirectory == false) { + if (VfsUtilCore.processFilesRecursively(childDirectory) { file -> file.extension != fileExtension }) { + return null + } + } + + return childDirectory + } + + private fun cachesPath(path: List<String>): List<Cache> { + val caches = ArrayList<Cache>(path.size + 1) + caches.add(rootCache) + var currentCache = rootCache + for (subPackageName in path) { + currentCache = currentCache[subPackageName] + caches.add(currentCache) + } + return caches + } + + private data class FindClassRequest(val classId: ClassId, override val acceptedRootTypes: Set<JavaRoot.RootType>) : SearchRequest { + override val packageFqName: FqName + get() = classId.packageFqName + } + + private data class TraverseRequest( + override val packageFqName: FqName, + override val acceptedRootTypes: Set<JavaRoot.RootType> + ) : SearchRequest + + private interface SearchRequest { + val packageFqName: FqName + val acceptedRootTypes: Set<JavaRoot.RootType> + } + + private sealed class SearchResult { + class Found(val packageDirectory: VirtualFile, val root: JavaRoot) : SearchResult() + + object NotFound : SearchResult() + } +} diff --git a/kotlin-analysis/src/main/kotlin/org/jetbrains/dokka/analysis/KotlinCliJavaFileManagerImpl.kt b/kotlin-analysis/src/main/kotlin/org/jetbrains/dokka/analysis/KotlinCliJavaFileManagerImpl.kt new file mode 100644 index 00000000..5955c3e4 --- /dev/null +++ b/kotlin-analysis/src/main/kotlin/org/jetbrains/dokka/analysis/KotlinCliJavaFileManagerImpl.kt @@ -0,0 +1,305 @@ +/* + * Copyright 2010-2015 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 org.jetbrains.kotlin.cli.jvm.compiler + +import com.intellij.core.CoreJavaFileManager +import com.intellij.openapi.diagnostic.Logger +import com.intellij.openapi.util.text.StringUtil +import com.intellij.openapi.vfs.VirtualFile +import com.intellij.psi.* +import com.intellij.psi.impl.file.PsiPackageImpl +import com.intellij.psi.search.GlobalSearchScope +import gnu.trove.THashMap +import gnu.trove.THashSet +import org.jetbrains.kotlin.cli.jvm.index.JavaRoot +import org.jetbrains.kotlin.cli.jvm.index.JvmDependenciesIndex +import org.jetbrains.kotlin.cli.jvm.index.SingleJavaFileRootsIndex +import org.jetbrains.kotlin.load.java.JavaClassFinder +import org.jetbrains.kotlin.load.java.structure.JavaClass +import org.jetbrains.kotlin.load.java.structure.impl.JavaClassImpl +import org.jetbrains.kotlin.load.java.structure.impl.classFiles.BinaryClassSignatureParser +import org.jetbrains.kotlin.load.java.structure.impl.classFiles.BinaryJavaClass +import org.jetbrains.kotlin.load.java.structure.impl.classFiles.ClassifierResolutionContext +import org.jetbrains.kotlin.load.java.structure.impl.classFiles.isNotTopLevelClass +import org.jetbrains.kotlin.name.ClassId +import org.jetbrains.kotlin.name.FqName +import org.jetbrains.kotlin.resolve.jvm.KotlinCliJavaFileManager +import org.jetbrains.kotlin.util.PerformanceCounter +import org.jetbrains.kotlin.utils.addIfNotNull +import java.util.* + +// TODO: do not inherit from CoreJavaFileManager to avoid accidental usage of its methods which do not use caches/indices +// Currently, the only relevant usage of this class as CoreJavaFileManager is at CoreJavaDirectoryService.getPackage, +// which is indirectly invoked from PsiPackage.getSubPackages +class KotlinCliJavaFileManagerImpl(private val myPsiManager: PsiManager) : CoreJavaFileManager(myPsiManager), KotlinCliJavaFileManager { + private val perfCounter = PerformanceCounter.create("Find Java class") + private lateinit var index: JvmDependenciesIndex + private lateinit var singleJavaFileRootsIndex: SingleJavaFileRootsIndex + private lateinit var packagePartProviders: List<JvmPackagePartProvider> + private val topLevelClassesCache: MutableMap<FqName, VirtualFile?> = THashMap() + private val allScope = GlobalSearchScope.allScope(myPsiManager.project) + private var usePsiClassFilesReading = false + + fun initialize( + index: JvmDependenciesIndex, + packagePartProviders: List<JvmPackagePartProvider>, + singleJavaFileRootsIndex: SingleJavaFileRootsIndex, + usePsiClassFilesReading: Boolean + ) { + this.index = index + this.packagePartProviders = packagePartProviders + this.singleJavaFileRootsIndex = singleJavaFileRootsIndex + this.usePsiClassFilesReading = usePsiClassFilesReading + } + + private fun findPsiClass(classId: ClassId, searchScope: GlobalSearchScope): PsiClass? = perfCounter.time { + findVirtualFileForTopLevelClass(classId, searchScope)?.findPsiClassInVirtualFile(classId.relativeClassName.asString()) + } + + private fun findVirtualFileForTopLevelClass(classId: ClassId, searchScope: GlobalSearchScope): VirtualFile? { + val relativeClassName = classId.relativeClassName.asString() + synchronized(topLevelClassesCache) { + return topLevelClassesCache.getOrPut(classId.packageFqName.child(classId.relativeClassName.pathSegments().first())) { + index.findClass(classId) { dir, type -> + findVirtualFileGivenPackage(dir, relativeClassName, type) + } ?: singleJavaFileRootsIndex.findJavaSourceClass(classId) + }?.takeIf { it in searchScope } + } + } + + private val binaryCache: MutableMap<ClassId, JavaClass?> = THashMap() + private val signatureParsingComponent = BinaryClassSignatureParser() + + fun findClass(classId: ClassId, searchScope: GlobalSearchScope): JavaClass? = findClass(JavaClassFinder.Request(classId), searchScope) + + override fun findClass(request: JavaClassFinder.Request, searchScope: GlobalSearchScope): JavaClass? { + val (classId, classFileContentFromRequest, outerClassFromRequest) = request + val virtualFile = findVirtualFileForTopLevelClass(classId, searchScope) ?: return null + + if (!usePsiClassFilesReading && virtualFile.extension == "class") { + synchronized(binaryCache){ + // We return all class files' names in the directory in knownClassNamesInPackage method, so one may request an inner class + return binaryCache.getOrPut(classId) { + // Note that currently we implicitly suppose that searchScope for binary classes is constant and we do not use it + // as a key in cache + // This is a true assumption by now since there are two search scopes in compiler: one for sources and another one for binary + // When it become wrong because we introduce the modules into CLI, it's worth to consider + // having different KotlinCliJavaFileManagerImpl's for different modules + + classId.outerClassId?.let { outerClassId -> + val outerClass = outerClassFromRequest ?: findClass(outerClassId, searchScope) + + return if (outerClass is BinaryJavaClass) + outerClass.findInnerClass(classId.shortClassName, classFileContentFromRequest) + else + outerClass?.findInnerClass(classId.shortClassName) + } + + // Here, we assume the class is top-level + val classContent = classFileContentFromRequest ?: virtualFile.contentsToByteArray() + if (virtualFile.nameWithoutExtension.contains("$") && isNotTopLevelClass(classContent)) return@getOrPut null + + val resolver = ClassifierResolutionContext { findClass(it, allScope) } + + BinaryJavaClass( + virtualFile, classId.asSingleFqName(), resolver, signatureParsingComponent, + outerClass = null, classContent = classContent + ) + } + } + } + + return virtualFile.findPsiClassInVirtualFile(classId.relativeClassName.asString())?.let(::JavaClassImpl) + } + + // this method is called from IDEA to resolve dependencies in Java code + // which supposedly shouldn't have errors so the dependencies exist in general + override fun findClass(qName: String, scope: GlobalSearchScope): PsiClass? { + // String cannot be reliably converted to ClassId because we don't know where the package name ends and class names begin. + // For example, if qName is "a.b.c.d.e", we should either look for a top level class "e" in the package "a.b.c.d", + // or, for example, for a nested class with the relative qualified name "c.d.e" in the package "a.b". + // Below, we start by looking for the top level class "e" in the package "a.b.c.d" first, then for the class "d.e" in the package + // "a.b.c", and so on, until we find something. Most classes are top level, so most of the times the search ends quickly + + forEachClassId(qName) { classId -> + findPsiClass(classId, scope)?.let { return it } + } + + return null + } + + private inline fun forEachClassId(fqName: String, block: (ClassId) -> Unit) { + var classId = fqName.toSafeTopLevelClassId() ?: return + + while (true) { + block(classId) + + val packageFqName = classId.packageFqName + if (packageFqName.isRoot) break + + classId = ClassId( + packageFqName.parent(), + FqName(packageFqName.shortName().asString() + "." + classId.relativeClassName.asString()), + false + ) + } + } + + override fun findClasses(qName: String, scope: GlobalSearchScope): Array<PsiClass> = perfCounter.time { + val result = ArrayList<PsiClass>(1) + forEachClassId(qName) { classId -> + val relativeClassName = classId.relativeClassName.asString() + index.traverseDirectoriesInPackage(classId.packageFqName) { dir, rootType -> + val psiClass = + findVirtualFileGivenPackage(dir, relativeClassName, rootType) + ?.takeIf { it in scope } + ?.findPsiClassInVirtualFile(relativeClassName) + if (psiClass != null) { + result.add(psiClass) + } + // traverse all + true + } + + result.addIfNotNull( + singleJavaFileRootsIndex.findJavaSourceClass(classId) + ?.takeIf { it in scope } + ?.findPsiClassInVirtualFile(relativeClassName) + ) + + if (result.isNotEmpty()) { + return@time result.toTypedArray() + } + } + + PsiClass.EMPTY_ARRAY + } + + override fun findPackage(packageName: String): PsiPackage? { + var found = false + val packageFqName = packageName.toSafeFqName() ?: return null + index.traverseDirectoriesInPackage(packageFqName) { _, _ -> + found = true + //abort on first found + false + } + if (!found) { + found = packagePartProviders.any { it.findPackageParts(packageName).isNotEmpty() } + } + if (!found) { + found = singleJavaFileRootsIndex.findJavaSourceClasses(packageFqName).isNotEmpty() + } + return if (found) PsiPackageImpl(myPsiManager, packageName) else null + } + + private fun findVirtualFileGivenPackage( + packageDir: VirtualFile, + classNameWithInnerClasses: String, + rootType: JavaRoot.RootType + ): VirtualFile? { + val topLevelClassName = classNameWithInnerClasses.substringBefore('.') + + val vFile = when (rootType) { + JavaRoot.RootType.BINARY -> packageDir.findChild("$topLevelClassName.class") + JavaRoot.RootType.SOURCE -> packageDir.findChild("$topLevelClassName.java") + } ?: return null + + if (!vFile.isValid) { + LOG.error("Invalid child of valid parent: ${vFile.path}; ${packageDir.isValid} path=${packageDir.path}") + return null + } + + return vFile + } + + private fun VirtualFile.findPsiClassInVirtualFile(classNameWithInnerClasses: String): PsiClass? { + val file = myPsiManager.findFile(this) as? PsiClassOwner ?: return null + return findClassInPsiFile(classNameWithInnerClasses, file) + } + + override fun knownClassNamesInPackage(packageFqName: FqName): Set<String> { + val result = THashSet<String>() + index.traverseDirectoriesInPackage(packageFqName, continueSearch = { dir, _ -> + for (child in dir.children) { + if (child.extension == "class" || child.extension == "java") { + result.add(child.nameWithoutExtension) + } + } + + true + }) + + for (classId in singleJavaFileRootsIndex.findJavaSourceClasses(packageFqName)) { + assert(!classId.isNestedClass) { "ClassId of a single .java source class should not be nested: $classId" } + result.add(classId.shortClassName.asString()) + } + + return result + } + + override fun findModules(moduleName: String, scope: GlobalSearchScope): Collection<PsiJavaModule> { + // TODO + return emptySet() + } + + override fun getNonTrivialPackagePrefixes(): Collection<String> = emptyList() + + companion object { + private val LOG = Logger.getInstance(KotlinCliJavaFileManagerImpl::class.java) + + private fun findClassInPsiFile(classNameWithInnerClassesDotSeparated: String, file: PsiClassOwner): PsiClass? { + for (topLevelClass in file.classes) { + val candidate = findClassByTopLevelClass(classNameWithInnerClassesDotSeparated, topLevelClass) + if (candidate != null) { + return candidate + } + } + return null + } + + private fun findClassByTopLevelClass(className: String, topLevelClass: PsiClass): PsiClass? { + if (className.indexOf('.') < 0) { + return if (className == topLevelClass.name) topLevelClass else null + } + + val segments = StringUtil.split(className, ".").iterator() + if (!segments.hasNext() || segments.next() != topLevelClass.name) { + return null + } + var curClass = topLevelClass + while (segments.hasNext()) { + val innerClassName = segments.next() + val innerClass = curClass.findInnerClassByName(innerClassName, false) ?: return null + curClass = innerClass + } + return curClass + } + } +} + +// a sad workaround to avoid throwing exception when called from inside IDEA code +private fun <T : Any> safely(compute: () -> T): T? = + try { + compute() + } catch (e: IllegalArgumentException) { + null + } catch (e: AssertionError) { + null + } + +private fun String.toSafeFqName(): FqName? = safely { FqName(this) } +private fun String.toSafeTopLevelClassId(): ClassId? = safely { ClassId.topLevel(FqName(this)) } |