GCC Code Coverage Report

src/
Coverage:
low: ≥ 0%
medium: ≥ 75.0%
high: ≥ 90.0%
Lines:
173 / 176
98.3%
Branches:
50 / 56, 18 excl
89.3%
Functions:
10 / 10
100.0%
typechecker/struct-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/struct";
15 import "@/model/interface";
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 "@/source-file";
22 import "@/typechecker/type-checker";
23 import "@/typechecker/type-matcher";
24 import "@/util/custom-hash-functions";
25 import "@/util/lookup-cache";
26 import "@/util/concurrency";
27
28 // Type aliases
29 public type StructManifestationList alias UnorderedMap</*mangledName=*/String, Struct>;
30 public type StructRegistry alias Map</*structId=*/String, /*manifestationList=*/StructManifestationList>;
31
32 /**
33 * Insert a struct declaration into the given scope
34 *
35 * @param insertScope Scope to insert the struct into
36 * @param spiceStruct Struct to insert
37 * @param nodeStructList List to collect the inserted manifestation into (owned by the declaration node)
38 * @return Inserted struct manifestation
39 */
40 3218 #[ignoreUnusedReturnValue]
41 3218 public f<Struct*> insertStruct(Scope* insertScope, Struct& spiceStruct, Vector<Struct*>* nodeStructList) {
42 // Open a new manifestation list. Which gets filled by the substantiated manifestations of the struct
43 3218 const String structId = spiceStruct.name + ":" + spiceStruct.declNode.codeLoc.toString();
44 // Keep an existing manifestation list
45
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 3218 times.
 3218 if !insertScope.structs.contains(structId) {
46 3218 insertScope.structs.upsert(structId, StructManifestationList());
47 3218 }
48
49 // Save substantiation in declaration node
50 3218 Struct* substantiation = insertSubstantiation(insertScope, spiceStruct, spiceStruct.declNode);
51 3218 nodeStructList.pushBack(substantiation);
52
53 6436 return substantiation;
54 3218 }
55
56 5358 f<Struct*> insertSubstantiation(Scope* insertScope, Struct& newManifestation, const ASTNode* declNode) {
57 5358 const String signature = newManifestation.structBase.getSignature();
58
59 // Retrieve the matching manifestation list of the scope
60 5358 const String structId = newManifestation.name + ":" + declNode.codeLoc.toString();
61 5358 assert insertScope.structs.contains(structId);
62 5358 StructManifestationList& manifestationList = insertScope.structs.get(structId);
63
64 // Add substantiated struct
65 5358 newManifestation.manifestationIndex = manifestationList.getSize();
66 5358 manifestationList.upsert(signature, newManifestation);
67 10716 return &manifestationList.get(signature);
68 5358 }
69
70 // Active struct lookup cache. It is owned by the global resource manager.
71 LookupCache<Struct>* ACTIVE_STRUCT_LOOKUP_CACHE;
72
73 /**
74 * Make the given lookup cache the active one. The struct lookup operates on it.
75 *
76 * @param cache Lookup cache
77 */
78 1055 public p setActiveStructLookupCache(LookupCache<Struct>* cache) {
79 1055 ACTIVE_STRUCT_LOOKUP_CACHE = cache;
80 1055 }
81
82 /**
83 * Get the active struct lookup cache
84 *
85 * @return Active lookup cache
86 */
87 361066 f<LookupCache<Struct>*> getActiveStructLookupCache() {
88 361066 assert ACTIVE_STRUCT_LOOKUP_CACHE != nil<LookupCache<Struct>*>;
89 361066 return ACTIVE_STRUCT_LOOKUP_CACHE;
90 }
91
92 /**
93 * Check if there is a struct in this scope, fulfilling all given requirements and if found, return it.
94 * If more than one struct matches the requirement, this is reported as an ambiguity error.
95 *
96 * @param matchScope Scope to match against
97 * @param qt Struct name requirement
98 * @param reqTemplateTypes Template types to substantiate generic types
99 * @param node Instantiation AST node for printing error messages
100 * @return Matched struct or nil
101 */
102 360306 public f<Struct*> matchStruct(Scope* matchScope, const String& qt, const QualTypeList& reqTemplateTypes, const ASTNode* node) {
103 // The IR generator reaches this from the worker threads of the parallel back end
104 360306 ConditionalLock _lock = ConditionalLock(getSymbolRegistryMutex());
105
106 // Do cache lookup
107 360306 LookupCache<Struct>* cache = getActiveStructLookupCache();
108 360306 const Hash cacheKey = getStructCacheKey(matchScope, qt, reqTemplateTypes);
109
2/2
✓ Branch 0 taken 354571 times.
✓ Branch 1 taken 5735 times.
 360306 if cache.lookupCache.contains(cacheKey) {
110 354571 cache.lookupCacheHits++;
111 709142 return cache.lookupCache.get(cacheKey);
112 }
113 5735 cache.lookupCacheMisses++;
114
115 // Loop over struct registry to find structs, that match the requirements of the instantiation
116 5735 Vector<Struct*> matches;
117
2/2
✓ Branch 0 taken 10000 times.
✓ Branch 1 taken 5735 times.
 15735 foreach Pair<const String&, StructManifestationList&> defEntry : matchScope.structs {
118 10000 const String& structId = defEntry.getFirst();
119
2/2
✓ Branch 0 taken 2284 times.
✓ Branch 1 taken 12780 times.
 15064 foreach Pair<const String&, Struct&> manEntry : defEntry.getSecond() {
120 12780 const String& mangledName = manEntry.getFirst();
121 12780 const Struct& presetStruct = manEntry.getSecond();
122 // Skip generic and newly inserted substantiations to prevent double matching of a struct
123
4/4
✓ Branch 0 taken 2780 times.
✓ Branch 1 taken 10000 times.
✓ Branch 2 taken 2780 times.
✓ Branch 3 taken 10000 times.
 12780 if presetStruct.structBase.isGenericSubstantiation() || presetStruct.isNewlyInserted {
124 2780 continue;
125 }
126
127 // Copy the struct to be able to substantiate types
128 10000 Struct candidate = presetStruct;
129
130 // Check name requirement
131
2/2
✓ Branch 0 taken 4451 times.
✓ Branch 1 taken 5549 times.
 10000 if !matchName(candidate, qt) {
132 4451 break; // Leave the whole manifestation list, because all manifestations in this list have the same name
133 }
134
135 // Prepare mapping table from generic type name to concrete type
136 5549 candidate.typeMapping.clear();
137
138 // Check template types requirement
139
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 5547 times.
 5549 if !matchTemplateTypes(candidate, reqTemplateTypes, candidate.typeMapping, node) {
140 2 continue; // Leave this manifestation and continue with the next one
141 }
142
143 // Map field types from generic to concrete
144 5547 substantiateFieldTypes(candidate, candidate.typeMapping, node);
145
146 // We found a match! -> Set the actual candidate and its entry to used
147 5547 candidate.used = true;
148 5547 candidate.entry.used = true;
149
150 // Check if it needs to be substantiated
151
2/2
✓ Branch 0 taken 2282 times.
✓ Branch 1 taken 3265 times.
 5547 if presetStruct.templateTypes.isEmpty() {
152 2282 assert matchScope.structs.contains(structId);
153 2282 StructManifestationList& structManifestations = matchScope.structs.get(structId);
154 2282 assert structManifestations.contains(mangledName);
155 2282 Struct* structMatch = &structManifestations.get(mangledName);
156 2282 structMatch.used = true;
157 2282 matches.pushBack(structMatch);
158 2282 continue; // Match was successful -> match the next struct
159 }
160
161 // Check if we already have this manifestation and can simply re-use it
162 3265 const String candidateSignature = candidate.structBase.getSignature();
163 3265 StructManifestationList& defManifestations = defEntry.getSecond();
164
2/2
✓ Branch 0 taken 1125 times.
✓ Branch 1 taken 2140 times.
 3265 if defManifestations.contains(candidateSignature) {
165 1125 Struct& existingManifestation = defManifestations.get(candidateSignature);
166 1125 existingManifestation.used = true;
167 1125 matches.pushBack(&existingManifestation);
168 1125 break; // Leave the whole manifestation list to not double-match the manifestation
169 }
170
171 // Insert the substantiated version if required
172 2140 Struct* substantiatedStruct = insertSubstantiation(matchScope, candidate, presetStruct.declNode);
173 2140 StructManifestationList& presetManifestations = matchScope.structs.get(structId);
174 2140 Struct& presetManifestation = presetManifestations.get(mangledName);
175 2140 substantiatedStruct.genericPreset = &presetManifestation.structBase;
176 2140 const ASTStructDefNode* structDefNode = downcast<ASTStructDefNode>(substantiatedStruct.structBase.declNode);
177 2140 structDefNode.structManifestations.pushBack(substantiatedStruct);
178 2140 substantiatedStruct.isNewlyInserted = true; // To not iterate over it in the same matching
179 // The generic preset was already decided on, but this manifestation carries concrete field types and therefore
180 // needs its own decision (taken further below, once its fields and interfaces are substantiated)
181 2140 substantiatedStruct.structBase.implicitDefaultMembersDecided = false;
182
183 // Copy struct entry
184 2140 const String newSignature = substantiatedStruct.structBase.getSignature();
185 2140 matchScope.lookupStrict(substantiatedStruct.name).used = true;
186 2140 substantiatedStruct.entry = matchScope.symbolTable.copySymbol(substantiatedStruct.name, newSignature);
187 2140 assert substantiatedStruct.entry != nil<SymbolTableEntry*>;
188
189 // Copy struct scope
190 2140 const String oldScopeName = presetStruct.getScopeName();
191 2140 const String newScopeName = substantiatedStruct.getScopeName();
192 2140 matchScope.copyChildScope(oldScopeName, newScopeName);
193 2140 substantiatedStruct.scope = matchScope.getChildScope(newScopeName);
194 2140 assert substantiatedStruct.scope != nil<Scope*>;
195 2140 substantiatedStruct.scope.isGenericScope = false;
196
197 // Attach the template types to the new struct entry
198 2140 const QualType& oldEntryType = substantiatedStruct.entry.getQualType();
199 2140 const QualTypeList concreteTemplateTypes = substantiatedStruct.structBase.getTemplateTypes();
200 2140 const QualType entryTypeWithTemplates = oldEntryType.getWithTemplateTypes(concreteTemplateTypes);
201 2140 const QualType entryType = entryTypeWithTemplates.getWithBodyScope(substantiatedStruct.scope);
202 2140 substantiatedStruct.entry.updateType(entryType, true);
203
204 // Replace symbol types of field entries with concrete types
205 2140 assert substantiatedStruct.scope != nil<Scope*>;
206 2140 const unsigned long fieldCount = substantiatedStruct.fieldTypes.getSize();
207 2140 const unsigned long explicitFieldsStartIdx = substantiatedStruct.scope.getFieldCount() - fieldCount;
208 2140 unsigned long i = 0ul;
209
2/2
✓ Branch 0 taken 2140 times.
✓ Branch 1 taken 5094 times.
 7234 while i < fieldCount {
210 // Replace field type with concrete template type
211 5094 SymbolTableEntry* fieldEntry = substantiatedStruct.scope.lookupField(cast<unsigned int>(explicitFieldsStartIdx + i));
212 5094 assert fieldEntry != nil<SymbolTableEntry*> && fieldEntry.isField();
213 5094 QualType& fieldType = substantiatedStruct.fieldTypes.get(i);
214 5094 QualType baseType = fieldType.getBase();
215
216 // Set the body scope of fields that are of type <candidate-struct>*
217
2/2
✓ Branch 0 taken 4990 times.
✓ Branch 1 taken 104 times.
 5094 if baseType.matches(substantiatedStruct.entry.getQualType(), false, true, true) {
218 104 fieldType = fieldType.replaceBaseType(baseType.getWithBodyScope(substantiatedStruct.scope));
219 104 }
220
221 5094 fieldEntry.updateType(fieldType, /*overwriteExistingType=*/true);
222
223 // Instantiate structs
224
2/2
✓ Branch 0 taken 3095 times.
✓ Branch 1 taken 1999 times.
 5094 if baseType.is(SuperType::TY_STRUCT) {
225 1999 const Struct* _ = baseType.getStruct(node);
226 1999 }
227
228 5094 i++;
229 5094 }
230
231 // Instantiate implemented interfaces if required
232
2/2
✓ Branch 0 taken 702 times.
✓ Branch 1 taken 2140 times.
 2842 foreach QualType& interfaceType : substantiatedStruct.interfaceTypes {
233 // Skip non-generic interfaces
234
2/2
✓ Branch 0 taken 11 times.
✓ Branch 1 taken 691 times.
 702 if !interfaceType.hasAnyGenericParts() {
235 11 continue;
236 }
237
238 // Build template types
239 691 QualTypeList templateTypes = interfaceType.getTemplateTypes();
240 691 substantiateTypesWithTypeMapping(templateTypes, candidate.typeMapping, node);
241
242 // Instantiate interface
243 691 Interface* spiceInterface = interfaceType.getInterface(node, templateTypes);
244
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 691 times.
 691 if spiceInterface != nil<Interface*> {
245 691 interfaceType = spiceInterface.entry.getQualType();
246 691 }
247 691 }
248
249 // Decide which compiler-generated default members this brand-new manifestation needs. This has to happen right
250 // here, because the decision depends on the concrete field types and every reactive lookup that asks the struct
251 // for its dtor/ctor from now on has to see the answer (see createImplicitDefaultMembers). The nested
252 // field manifestations created above are decided on first, by their own recursive matchStruct() call, so a field's
253 // dtor is already in place when the outer struct is asked whether it needs one.
254 // A manifestation that is created while its own file is still being prepared is left alone: the generic preset
255 // has not been decided on yet at that point, so this manifestation could neither inherit its default members
256 // through the copied scope nor come to the same conclusion on its own. Those manifestations are covered by the
257 // one-shot sweep at the end of the file's prepare run (TypeChecker.visitEntry), which sees all of them.
258 2140 SourceFile* structSourceFile = substantiatedStruct.structBase.scope.sourceFile;
259
3/4
✗ Branch 0 not taken.
✓ Branch 1 taken 2140 times.
✓ Branch 2 taken 24 times.
✓ Branch 3 taken 2116 times.
 2140 if STRUCT_DEFAULT_MEMBERS_DECIDABLE && structSourceFile.previousStage >= CompileStageType::TYPE_CHECKER_PRE {
260 2116 createImplicitDefaultMembers(*substantiatedStruct, node, /*withMoveCtor=*/false);
261 2116 }
262
263 // Add to matched structs
264 2140 matches.pushBack(substantiatedStruct);
265 // Leave the manifestation list: the remaining manifestations are substantiations, which are skipped anyway, and
266 // iterating the hash table further after inserting into it could visit the generic preset a second time
267 2140 break;
268 10000 }
269 10000 }
270
271 // If no matches were found, return a nil
272
2/2
✓ Branch 0 taken 188 times.
✓ Branch 1 taken 5547 times.
 5735 if matches.isEmpty() {
273 188 return nil<Struct*>;
274 }
275
276 // Check if more than one struct matches the requirements
277
1/2
✓ Branch 0 taken 5547 times.
✗ Branch 1 not taken.
 5547 if matches.getSize() > 1l {
278 ✗ throwSemanticError(node, SemanticErrorType::STRUCT_AMBIGUITY, String("Multiple structs match the requested signature"));
279 // The compilation is aborted after this stage. Until then, deterministically pick the first candidate
280 ✗ }
281 5547 Struct* matchedStruct = matches.front();
282 5547 matchedStruct.isNewlyInserted = false;
283
284 // Insert into cache
285 5547 cache.lookupCache.upsert(cacheKey, matchedStruct);
286
287 11094 return matchedStruct;
288 360306 }
289
290 /**
291 * Checks if the matching candidate fulfills the name requirement
292 */
293 10000 f<bool> matchName(const Struct& candidate, const String& reqName) {
294 10000 return candidate.name == reqName;
295 }
296
297 /**
298 * Checks if the matching candidate fulfills the template types requirement
299 */
300 5549 f<bool> matchTemplateTypes(Struct& candidate, const QualTypeList& reqTemplateTypes, TypeMapping& typeMapping, const ASTNode* node) {
301 // Check if the number of types match
302
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 5547 times.
 5549 if reqTemplateTypes.getSize() != candidate.templateTypes.getSize() {
303 2 return false;
304 }
305
306
307 // Loop over all template types
308
2/2
✓ Branch 0 taken 4574 times.
✓ Branch 1 taken 5547 times.
 10121 foreach unsigned long i, GenericType& candidateTemplateType : candidate.templateTypes {
309 4574 QualType& candidateType = candidateTemplateType.qualType;
310 4574 const QualType& reqType = reqTemplateTypes.get(i);
311
312 // Check if the requested template type matches the candidate template type. The type mapping may be extended
313
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 4574 times.
 4574 if !matchRequestedToCandidateType(candidateType, reqType, typeMapping, candidate.templateTypes, true, false) {
314 ✗ return false;
315 }
316
317 // Substantiate the candidate param type, based on the type mapping
318
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 4574 times.
 4574 if candidateType.hasAnyGenericParts() {
319 4574 substantiateTypeWithTypeMapping(candidateType, typeMapping, node);
320 4574 }
321 4574 }
322
323 5547 return true;
324 }
325
326 /**
327 * Come up with the concrete field types, by applying the type mapping onto the generic field types
328 */
329 5547 p substantiateFieldTypes(Struct& candidate, const TypeMapping& typeMapping, const ASTNode* node) {
330 // Loop over all implicit fields and substantiate the generic ones
331 5547 const unsigned long implicitFieldCount = candidate.scope.getFieldCount() - candidate.fieldTypes.getSize();
332 5547 unsigned long i = 0ul;
333
2/2
✓ Branch 0 taken 1158 times.
✓ Branch 1 taken 5547 times.
 6705 while i < implicitFieldCount {
334 1158 SymbolTableEntry* fieldEntry = candidate.scope.lookupField(cast<unsigned int>(i));
335 1158 QualType fieldType = fieldEntry.getQualType();
336
2/2
✓ Branch 0 taken 413 times.
✓ Branch 1 taken 745 times.
 1158 if fieldType.hasAnyGenericParts() {
337 745 substantiateTypeWithTypeMapping(fieldType, typeMapping, node);
338 745 fieldEntry.updateType(fieldType, true);
339 745 }
340 1158 i++;
341 1158 }
342
343 // Loop over all explicit field types and substantiate the generic ones
344
2/2
✓ Branch 0 taken 13429 times.
✓ Branch 1 taken 5547 times.
 18976 foreach QualType& fieldType : candidate.fieldTypes {
345
2/2
✓ Branch 0 taken 8583 times.
✓ Branch 1 taken 4846 times.
 13429 if fieldType.hasAnyGenericParts() {
346 4846 substantiateTypeWithTypeMapping(fieldType, typeMapping, node);
347 4846 }
348 13429 }
349 5547 }
350
351
352 /**
353 * Calculate the cache key for the struct lookup cache
354 *
355 * @param scope Scope to match against
356 * @param name Struct name requirement
357 * @param templateTypes Template types to substantiate generic types
358 * @return Cache key
359 */
360 360306 f<Hash> getStructCacheKey(const Scope* scope, const String& name, const QualTypeList& templateTypes) {
361 360306 Hash hash = 0ul;
362 360306 hashCombine64(hash, hashPointer(scope));
363 360306 hashCombine64(hash, hash(name));
364 360306 hashCombine64(hash, hashQualTypeList(templateTypes));
365 360306 return hash;
366 }
367
368 /**
369 * Dump usage statistics for the lookup cache
370 */
371 760 public f<String> dumpStructLookupCacheStatistics() {
372 760 LookupCache<Struct>* cache = getActiveStructLookupCache();
373 760 return cache.dumpLookupCacheStatistics("StructManager");
374 }
375