-
Notifications
You must be signed in to change notification settings - Fork 392
/
JvmDependenciesIndexImpl.kt
257 lines (221 loc) · 10.7 KB
/
JvmDependenciesIndexImpl.kt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
/*
* 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 it.unimi.dsi.fastutil.ints.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.trim()
}
}
// 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 until cacheRootIndices.size) {
val rootIndex = cacheRootIndices.getInt(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.getInt(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) until cachesPath.size) {
// we all know roots that contain this package by now
cachesPath[i].rootIndices.add(maxIndex)
cachesPath[i].rootIndices.trim()
}
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()
}
}