1 /*
2  * Copyright (C) 2024 The Android Open Source Project
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 
17 package com.android.tools.metalava.model
18 
19 import java.lang.StringBuilder
20 
21 /**
22  * The set of [TypeParameterItem]s that are in scope.
23  *
24  * This is used to resolve a reference to a type parameter to the appropriate type parameter. They
25  * are in order from closest to most distant. e.g. When resolving the type parameters for `method`
26  * this will contain the type parameters from `method` then from `Inner`, then from `Outer`, i.e.
27  * `[M, X, I, X, O, X]`. That ensures that when searching for a type parameter whose name shadows
28  * one from an outer scope, e.g. `X`, that the inner one is used.
29  *
30  * ```
31  *     public class Outer<O, X> {
32  *     }
33  *
34  *     public class Outer.Inner<I, X> {
35  *       method public <M, X> M method(O o, I i);
36  *     }
37  * ```
38  *
39  * This does not implement [equals] and [hashCode] as the identity comparison is sufficient and
40  * necessary.
41  *
42  * It is sufficient because [TypeParameterScope]s have a one-to-one correspondence with a type
43  * parameter list owner.
44  *
45  * It is necessary because [TypeParameterItem.equals] is currently only based on the name. So,
46  * unless great care is taken to use identity comparison for [MapWrapper.nameToTypeParameterItem]
47  * contents it would break caching and have every type `T` reference the same type parameter.
48  */
49 sealed class TypeParameterScope private constructor() {
50 
51     /** True if there are no type parameters in scope. */
isEmptynull52     fun isEmpty() = this === empty
53 
54     /**
55      * Create a nested [TypeParameterScope] that will delegate to this one for any
56      * [TypeParameterItem]s that it cannot find.
57      *
58      * @param description is some helpful information about this scope that will be useful to track
59      *   down issues when a type parameter could not be found.
60      * @param typeParameters if this is empty then this method will return [this], otherwise it will
61      *   create a new [TypeParameterScope] that delegates to this one.
62      */
63     fun nestedScope(
64         description: String,
65         typeParameters: List<TypeParameterItem>,
66     ): TypeParameterScope =
67         // If the typeParameters is empty then just reuse this one, otherwise create a new scope
68         // delegating to this.
69         if (typeParameters.isEmpty()) this else MapWrapper(description, typeParameters, this)
70 
71     /**
72      * Finds the closest [TypeParameterItem] with the specified name.
73      *
74      * If none exists then returns `null`. This should only be used when it is not known if the name
75      * is a type parameter. Otherwise, call [getTypeParameter].
76      */
77     abstract fun findTypeParameter(name: String): TypeParameterItem?
78 
79     /**
80      * Finds the closest [TypeParameterItem] with the specified name.
81      *
82      * If none exists then fail. This should only be used when it is not known that the name is a
83      * type parameter. Otherwise, call [findTypeParameter].
84      */
85     fun getTypeParameter(name: String) =
86         findTypeParameter(name) ?: error("Could not find type parameter $name in $this")
87 
88     /** Finds the scope that provides at least one of the supplied [names] or [empty] otherwise. */
89     abstract fun findSignificantScope(names: Set<String>): TypeParameterScope
90 
91     companion object {
92         val empty: TypeParameterScope = Empty
93 
94         /**
95          * Collect all the type parameters in scope for the given [classItem] then wrap them in an
96          * [TypeParameterScope].
97          */
98         fun from(classItem: ClassItem?): TypeParameterScope {
99             return if (classItem == null) empty
100             else {
101                 // Construct a scope from the owner.
102                 from(classItem.containingClass())
103                     // Nest this inside it.
104                     .nestedScope(
105                         description = "class ${classItem.qualifiedName()}",
106                         classItem.typeParameterList,
107                     )
108             }
109         }
110 
111         /**
112          * Collect all the type parameters in scope for the given [methodItem] then wrap them in an
113          * [TypeParameterScope].
114          */
115         fun from(methodItem: MethodItem): TypeParameterScope {
116             // Construct a scope from the owner.
117             return from(methodItem.containingClass())
118                 // Nest this inside it.
119                 .nestedScope(
120                     description = "method ${methodItem.name()}",
121                     methodItem.typeParameterList,
122                 )
123         }
124     }
125 
126     private class MapWrapper(
127         private val description: String,
128         list: List<TypeParameterItem>,
129         private val enclosingScope: TypeParameterScope
130     ) : TypeParameterScope() {
131 
132         /**
133          * A mapping from name to [TypeParameterItem].
134          *
135          * Includes any [TypeParameterItem]s from the [enclosingScope] that are not shadowed by an
136          * item in the list.
137          */
138         private val nameToTypeParameterItem: Map<String, TypeParameterItem>
139 
140         /**
141          * The set of type parameter names added by this scope; does not include names from
142          * enclosing scopes but does include any shadows of those names added in this scope.
143          */
144         private val namesAddedInThisScope: Set<String>
145 
146         init {
<lambda>null147             namesAddedInThisScope = list.map { it.name() }.toSet()
148 
149             // Construct a map by taking a mutable copy of the map from the enclosing scope, if
150             // available, otherwise creating an empty map. Then adding all the type parameters that
151             // are part of this, replacing (i.e. shadowing) any type parameters with the same name
152             // from the enclosing scope.
153             val mutableMap =
154                 if (enclosingScope is MapWrapper)
155                     enclosingScope.nameToTypeParameterItem.toMutableMap()
156                 else mutableMapOf()
<lambda>null157             list.associateByTo(mutableMap) { it.name() }
158             nameToTypeParameterItem = mutableMap.toMap()
159         }
160 
findTypeParameternull161         override fun findTypeParameter(name: String) = nameToTypeParameterItem[name]
162 
163         override fun findSignificantScope(names: Set<String>): TypeParameterScope {
164             // Fast path to avoid recursing up enclosing scopes.
165             if (names.isEmpty()) return empty
166 
167             // If any of the supplied names are added in this scope then use this scope.
168             if (names.any { it in namesAddedInThisScope }) return this
169 
170             // Otherwise, check the enclosing scope.
171             return enclosingScope.findSignificantScope(names)
172         }
173 
toStringnull174         override fun toString(): String {
175             return buildString {
176                 appendTo(this)
177                 var scope = enclosingScope
178                 while (scope is MapWrapper) {
179                     append(" -> ")
180                     scope.appendTo(this)
181                     scope = scope.enclosingScope
182                 }
183             }
184         }
185 
186         /** Append information about this scope to the [builder], for debug purposes. */
appendTonull187         private fun appendTo(builder: StringBuilder) {
188             builder.apply {
189                 append("Scope(<")
190                 nameToTypeParameterItem.keys.joinTo(this)
191                 append("> for ")
192                 append(description)
193                 append(")")
194             }
195         }
196     }
197 
198     private object Empty : TypeParameterScope() {
199 
findTypeParameternull200         override fun findTypeParameter(name: String) = null
201 
202         override fun findSignificantScope(names: Set<String>) = this
203 
204         override fun toString(): String {
205             return "Scope()"
206         }
207     }
208 }
209