GCC Code Coverage Report

src/
Coverage:
low: ≥ 0%
medium: ≥ 75.0%
high: ≥ 90.0%
Lines:
132 / 139
95.0%
Branches:
34 / 42, 12 excl
81.0%
Functions:
10 / 10
100.0%
typechecker/interface-manager.spice
Line Branch Exec Source
1 // Copyright (c) 2021-2026 ChilliBits. All rights reserved.
2
3 // Std imports
4 import "std/data/map";
5 import "std/data/unordered-map";
6 import "std/data/vector";
7 import "std/data/pair";
8 import "std/math/hash";
9
10 // Own imports
11 import "@/exception/error-manager";
12 import "@/exception/semantic-error";
13 import "@/ast/ast-nodes";
14 import "@/model/interface";
15 import "@/model/function";
16 import "@/model/generic-type";
17 import "@/symboltablebuilder/qual-type";
18 import "@/symboltablebuilder/super-type";
19 import "@/symboltablebuilder/scope";
20 import "@/symboltablebuilder/symbol-table-entry";
21 import "@/typechecker/type-matcher";
22 import "@/typechecker/function-manager";
23 import "@/util/custom-hash-functions";
24 import "@/util/lookup-cache";
25 import "@/util/concurrency";
26
27 // Type aliases
28 public type InterfaceManifestationList alias UnorderedMap</*mangledName=*/String, Interface>;
29 // Keyed by the interface name and its declaration code location, like the other registries. CodeLoc alone cannot be ordered by
30 // std/data/red-black-tree (Spice cannot overload '<').
31 public type InterfaceRegistry alias Map</*interfaceId=*/String, /*manifestationList=*/InterfaceManifestationList>;
32
33 /**
34 * Insert an interface declaration into the given scope
35 *
36 * @param insertScope Scope to insert the interface into
37 * @param spiceInterface Interface to insert
38 * @param nodeInterfaceList List to collect the inserted manifestation into (owned by the declaration node)
39 * @return Inserted interface manifestation
40 */
41 322 #[ignoreUnusedReturnValue]
42 322 public f<Interface*> insertInterface(Scope* insertScope, Interface& spiceInterface, Vector<Interface*>* nodeInterfaceList) {
43 // Open a new manifestation list. Which gets filled by the substantiated manifestations of the interface
44 322 const String interfaceId = spiceInterface.name + ":" + spiceInterface.declNode.codeLoc.toString();
45 // Keep an existing manifestation list
46
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 322 times.
 322 if !insertScope.interfaces.contains(interfaceId) {
47 322 insertScope.interfaces.upsert(interfaceId, InterfaceManifestationList());
48 322 }
49
50 // Save substantiation in declaration node
51 322 Interface* substantiation = insertSubstantiation(insertScope, spiceInterface, spiceInterface.declNode);
52 322 nodeInterfaceList.pushBack(substantiation);
53
54 644 return substantiation;
55 322 }
56
57 970 f<Interface*> insertSubstantiation(Scope* insertScope, Interface& newManifestation, const ASTNode* declNode) {
58 970 const String signature = newManifestation.structBase.getSignature();
59
60 // Retrieve the matching manifestation list of the scope
61 970 const String interfaceId = newManifestation.name + ":" + declNode.codeLoc.toString();
62 970 assert insertScope.interfaces.contains(interfaceId);
63 970 InterfaceManifestationList& manifestationList = insertScope.interfaces.get(interfaceId);
64
65 // Add substantiated interface
66 970 newManifestation.manifestationIndex = manifestationList.getSize();
67 970 manifestationList.upsert(signature, newManifestation);
68 1940 return &manifestationList.get(signature);
69 970 }
70
71 // Active interface lookup cache. It is owned by the global resource manager.
72 LookupCache<Interface>* ACTIVE_INTERFACE_LOOKUP_CACHE;
73
74 /**
75 * Make the given lookup cache the active one. The interface lookup operates on it.
76 *
77 * @param cache Lookup cache
78 */
79 1055 public p setActiveInterfaceLookupCache(LookupCache<Interface>* cache) {
80 1055 ACTIVE_INTERFACE_LOOKUP_CACHE = cache;
81 1055 }
82
83 /**
84 * Get the active interface lookup cache
85 *
86 * @return Active lookup cache
87 */
88 6884 f<LookupCache<Interface>*> getActiveInterfaceLookupCache() {
89 6884 assert ACTIVE_INTERFACE_LOOKUP_CACHE != nil<LookupCache<Interface>*>;
90 6884 return ACTIVE_INTERFACE_LOOKUP_CACHE;
91 }
92
93 /**
94 * Check if there is an interface in this scope, fulfilling all given requirements and if found, return it.
95 * If more than one interface matches the requirement, this is reported as an ambiguity error.
96 *
97 * @param matchScope Scope to match against
98 * @param reqName Interface name requirement
99 * @param reqTemplateTypes Template types to substantiate generic types
100 * @param node Instantiation AST node for printing error messages
101 * @return Matched interface or nil
102 */
103 6124 public f<Interface*> matchInterface(Scope* matchScope, const String& reqName, const QualTypeList& reqTemplateTypes, const ASTNode* node) {
104 // The IR generator reaches this from the worker threads of the parallel back end
105 6124 ConditionalLock _lock = ConditionalLock(getSymbolRegistryMutex());
106
107 // Do cache lookup
108 6124 LookupCache<Interface>* cache = getActiveInterfaceLookupCache();
109 6124 const Hash cacheKey = getInterfaceCacheKey(matchScope, reqName, reqTemplateTypes);
110
2/2
✓ Branch 0 taken 5084 times.
✓ Branch 1 taken 1040 times.
 6124 if cache.lookupCache.contains(cacheKey) {
111 5084 cache.lookupCacheHits++;
112 10168 return cache.lookupCache.get(cacheKey);
113 }
114 1040 cache.lookupCacheMisses++;
115
116 // Loop over interface registry to find interfaces, that match the requirements of the instantiation
117 1040 Vector<Interface*> matches;
118
2/2
✓ Branch 0 taken 1041 times.
✓ Branch 1 taken 1040 times.
 2081 foreach Pair<const String&, InterfaceManifestationList&> defEntry : matchScope.interfaces {
119 1041 const String& interfaceId = defEntry.getFirst();
120
2/2
✓ Branch 0 taken 58 times.
✓ Branch 1 taken 1283 times.
 1341 foreach Pair<const String&, Interface&> manEntry : defEntry.getSecond() {
121 1283 const String& mangledName = manEntry.getFirst();
122 1283 const Interface& presetInterface = manEntry.getSecond();
123 // Skip generic and newly inserted substantiations to prevent double matching of an interface
124
4/4
✓ Branch 0 taken 242 times.
✓ Branch 1 taken 1041 times.
✓ Branch 2 taken 242 times.
✓ Branch 3 taken 1041 times.
 1283 if presetInterface.structBase.isGenericSubstantiation() || presetInterface.isNewlyInserted {
125 242 continue;
126 }
127
128 // Copy the interface to be able to substantiate types
129 1041 Interface candidate = presetInterface;
130
131 // Check name requirement
132
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 1039 times.
 1041 if !matchName(candidate, reqName) {
133 2 break; // Leave the whole manifestation list, because all manifestations in this list have the same name
134 }
135
136 // Prepare mapping table from generic type name to concrete type
137 1039 candidate.typeMapping.clear();
138
139 // Check template types requirement
140
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1039 times.
 1039 if !matchTemplateTypes(candidate, reqTemplateTypes, candidate.typeMapping, node) {
141 ✗ continue; // Leave this manifestation and continue with the next one
142 }
143
144 // Map signatures from generic to concrete
145 1039 substantiateSignatures(candidate, candidate.typeMapping, node);
146
147 // We found a match! -> Set the actual candidate and its entry to used
148 1039 candidate.used = true;
149 1039 candidate.entry.used = true;
150
151 // Check if it needs to be substantiated
152
2/2
✓ Branch 0 taken 58 times.
✓ Branch 1 taken 981 times.
 1039 if presetInterface.templateTypes.isEmpty() {
153 58 assert matchScope.interfaces.contains(interfaceId);
154 58 InterfaceManifestationList& interfaceManifestations = matchScope.interfaces.get(interfaceId);
155 58 assert interfaceManifestations.contains(mangledName);
156 58 Interface* ifaceMatch = &interfaceManifestations.get(mangledName);
157 58 ifaceMatch.used = true;
158 58 matches.pushBack(ifaceMatch);
159 58 continue; // Match was successful -> match the next interface
160 }
161
162 // Check if we already have this manifestation and can simply re-use it
163 981 const String candidateSignature = candidate.structBase.getSignature();
164 981 InterfaceManifestationList& defManifestations = defEntry.getSecond();
165
2/2
✓ Branch 0 taken 333 times.
✓ Branch 1 taken 648 times.
 981 if defManifestations.contains(candidateSignature) {
166 333 Interface& existingManifestation = defManifestations.get(candidateSignature);
167 333 existingManifestation.used = true;
168 333 matches.pushBack(&existingManifestation);
169 333 break; // Leave the whole manifestation list to not double-match the manifestation
170 }
171
172 // Insert the substantiated version if required
173 648 Interface* substantiatedInterface = insertSubstantiation(matchScope, candidate, presetInterface.declNode);
174 648 InterfaceManifestationList& presetManifestations = matchScope.interfaces.get(interfaceId);
175 648 Interface& presetManifestation = presetManifestations.get(mangledName);
176 648 substantiatedInterface.genericPreset = &presetManifestation.structBase;
177 648 const ASTInterfaceDefNode* interfaceDefNode = downcast<ASTInterfaceDefNode>(substantiatedInterface.structBase.declNode);
178 648 interfaceDefNode.interfaceManifestations.pushBack(substantiatedInterface);
179 648 substantiatedInterface.isNewlyInserted = true; // To not iterate over it in the same matching
180
181 // Copy interface entry
182 648 const String newSignature = substantiatedInterface.structBase.getSignature();
183 648 matchScope.lookupStrict(substantiatedInterface.name).used = true;
184 648 substantiatedInterface.entry = matchScope.symbolTable.copySymbol(substantiatedInterface.name, newSignature);
185 648 assert substantiatedInterface.entry != nil<SymbolTableEntry*>;
186
187 // Copy interface scope
188 648 const String oldScopeName = presetInterface.getScopeName();
189 648 const String newScopeName = substantiatedInterface.getScopeName();
190 648 matchScope.copyChildScope(oldScopeName, newScopeName);
191 648 substantiatedInterface.scope = matchScope.getChildScope(newScopeName);
192 648 assert substantiatedInterface.scope != nil<Scope*>;
193 648 substantiatedInterface.scope.isGenericScope = false;
194
195 // Attach the template types to the new interface entry
196 648 const QualType& oldEntryType = substantiatedInterface.entry.getQualType();
197 648 const QualTypeList concreteTemplateTypes = substantiatedInterface.structBase.getTemplateTypes();
198 648 const QualType entryTypeWithTemplates = oldEntryType.getWithTemplateTypes(concreteTemplateTypes);
199 648 const QualType entryType = entryTypeWithTemplates.getWithBodyScope(substantiatedInterface.scope);
200 648 substantiatedInterface.entry.updateType(entryType, true);
201
202 // Add to matched interfaces
203 648 matches.pushBack(substantiatedInterface);
204 // Leave the manifestation list: the remaining manifestations are substantiations, which are skipped anyway, and
205 // iterating the hash table further after inserting into it could visit the generic preset a second time
206 648 break;
207 1041 }
208 1041 }
209
210 // If no matches were found, return a nil
211
2/2
✓ Branch 0 taken 1 time.
✓ Branch 1 taken 1039 times.
 1040 if matches.isEmpty() {
212 1 return nil<Interface*>;
213 }
214
215 // Check if more than one interface matches the requirements
216
1/2
✓ Branch 0 taken 1039 times.
✗ Branch 1 not taken.
 1039 if matches.getSize() > 1l {
217 ✗ throwSemanticError(node, SemanticErrorType::INTERFACE_AMBIGUITY, String("Multiple interfaces match the requested signature"));
218 // The compilation is aborted after this stage. Until then, deterministically pick the first candidate
219 ✗ }
220 1039 Interface* matchedInterface = matches.front();
221 1039 matchedInterface.isNewlyInserted = false;
222
223 // Insert into cache
224 1039 cache.lookupCache.upsert(cacheKey, matchedInterface);
225
226 2078 return matchedInterface;
227 6124 }
228
229 /**
230 * Checks if the matching candidate fulfills the name requirement
231 */
232 1041 f<bool> matchName(const Interface& candidate, const String& reqName) {
233 1041 return candidate.name == reqName;
234 }
235
236 /**
237 * Checks if the matching candidate fulfills the template types requirement
238 */
239 1039 f<bool> matchTemplateTypes(Interface& candidate, const QualTypeList& reqTemplateTypes, TypeMapping& typeMapping, const ASTNode* node) {
240 // Check if the number of types match
241
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1039 times.
 1039 if reqTemplateTypes.getSize() != candidate.templateTypes.getSize() {
242 ✗ return false;
243 }
244
245
246 // Loop over all template types
247
2/2
✓ Branch 0 taken 981 times.
✓ Branch 1 taken 1039 times.
 2020 foreach unsigned long i, GenericType& candidateTemplateType : candidate.templateTypes {
248 981 QualType& candidateType = candidateTemplateType.qualType;
249 981 const QualType& reqType = reqTemplateTypes.get(i);
250
251 // Check if the requested template type matches the candidate template type. The type mapping may be extended
252
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 981 times.
 981 if !matchRequestedToCandidateType(candidateType, reqType, typeMapping, candidate.templateTypes, true, false) {
253 ✗ return false;
254 }
255
256 // Substantiate the candidate param type, based on the type mapping
257
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 981 times.
 981 if candidateType.hasAnyGenericParts() {
258 981 substantiateTypeWithTypeMapping(candidateType, typeMapping, node);
259 981 }
260 981 }
261
262 1039 return true;
263 }
264
265 /**
266 * Come up with the concrete signatures, by applying the type mapping onto the generic signatures
267 */
268 1039 p substantiateSignatures(Interface& candidate, const TypeMapping& typeMapping, const ASTNode* node) {
269 // Loop over all signatures and substantiate the generic ones
270
2/2
✓ Branch 0 taken 2686 times.
✓ Branch 1 taken 1039 times.
 3725 foreach Function* method : candidate.methods {
271 // Skip methods, that are already fully substantiated
272
2/2
✓ Branch 0 taken 70 times.
✓ Branch 1 taken 2616 times.
 2686 if method.isFullySubstantiated() {
273 70 continue;
274 }
275
276 // Substantiate return type
277
1/2
✓ Branch 0 taken 2616 times.
✗ Branch 1 not taken.
 2616 if method.isNormalFunction() {
278 ✗ substantiateReturnType(*method, typeMapping, node);
279 ✗ }
280
281 // Substantiate param types
282
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 2616 times.
 2620 foreach Param& param : method.paramList {
283
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 4 times.
 4 if param.qualType.isBase(SuperType::TY_GENERIC) {
284 4 substantiateTypeWithTypeMapping(param.qualType, typeMapping, node);
285 4 }
286 4 }
287 2616 }
288 1039 }
289
290
291 /**
292 * Calculate the cache key for the interface lookup cache
293 *
294 * @param scope Scope to match against
295 * @param name Interface name requirement
296 * @param templateTypes Template types to substantiate generic types
297 * @return Cache key
298 */
299 6124 f<Hash> getInterfaceCacheKey(const Scope* scope, const String& name, const QualTypeList& templateTypes) {
300 6124 Hash hash = 0ul;
301 6124 hashCombine64(hash, hashPointer(scope));
302 6124 hashCombine64(hash, hash(name));
303 6124 hashCombine64(hash, hashQualTypeList(templateTypes));
304 6124 return hash;
305 }
306
307 /**
308 * Dump usage statistics for the lookup cache
309 */
310 760 public f<String> dumpInterfaceLookupCacheStatistics() {
311 760 LookupCache<Interface>* cache = getActiveInterfaceLookupCache();
312 760 return cache.dumpLookupCacheStatistics("InterfaceManager");
313 }
314