GCC Code Coverage Report

src/
Coverage:
low: ≥ 0%
medium: ≥ 75.0%
high: ≥ 90.0%
Lines:
138 / 152
90.8%
Branches:
32 / 44, 18 excl
72.7%
Functions:
10 / 10
100.0%
typechecker/union-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/union";
15 import "@/model/generic-type";
16 import "@/symboltablebuilder/qual-type";
17 import "@/symboltablebuilder/super-type";
18 import "@/symboltablebuilder/scope";
19 import "@/symboltablebuilder/symbol-table-entry";
20 import "@/typechecker/type-matcher";
21 import "@/util/custom-hash-functions";
22 import "@/util/lookup-cache";
23 import "@/util/concurrency";
24
25 // Type aliases
26 public type UnionManifestationList alias UnorderedMap</*mangledName=*/String, Union>;
27 public type UnionRegistry alias Map</*unionId=*/String, /*manifestationList=*/UnionManifestationList>;
28
29 /**
30 * Insert a union declaration into the given scope
31 *
32 * @param insertScope Scope to insert the union into
33 * @param spiceUnion Union to insert
34 * @param nodeUnionList List to collect the inserted manifestation into (owned by the declaration node)
35 * @return Inserted union manifestation
36 */
37 22 #[ignoreUnusedReturnValue]
38 22 public f<Union*> insertUnion(Scope* insertScope, Union& spiceUnion, Vector<Union*>* nodeUnionList) {
39 // Open a new manifestation list. Which gets filled by the substantiated manifestations of the union
40 22 const String unionId = spiceUnion.name + ":" + spiceUnion.declNode.codeLoc.toString();
41 // Keep an existing manifestation list
42
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 22 times.
 22 if !insertScope.unions.contains(unionId) {
43 22 insertScope.unions.upsert(unionId, UnionManifestationList());
44 22 }
45
46 // Save substantiation in declaration node
47 22 Union* substantiation = insertSubstantiation(insertScope, spiceUnion, spiceUnion.declNode);
48 22 nodeUnionList.pushBack(substantiation);
49
50 44 return substantiation;
51 22 }
52
53 31 f<Union*> insertSubstantiation(Scope* insertScope, Union& newManifestation, const ASTNode* declNode) {
54 31 const String signature = newManifestation.structBase.getSignature();
55
56 // Retrieve the matching manifestation list of the scope
57 31 const String unionId = newManifestation.name + ":" + declNode.codeLoc.toString();
58 31 assert insertScope.unions.contains(unionId);
59 31 UnionManifestationList& manifestationList = insertScope.unions.get(unionId);
60
61 // Add substantiated union
62 31 newManifestation.manifestationIndex = manifestationList.getSize();
63 31 manifestationList.upsert(signature, newManifestation);
64 62 return &manifestationList.get(signature);
65 31 }
66
67 // Active union lookup cache. It is owned by the global resource manager.
68 LookupCache<Union>* ACTIVE_UNION_LOOKUP_CACHE;
69
70 /**
71 * Make the given lookup cache the active one. The union lookup operates on it.
72 *
73 * @param cache Lookup cache
74 */
75 1055 public p setActiveUnionLookupCache(LookupCache<Union>* cache) {
76 1055 ACTIVE_UNION_LOOKUP_CACHE = cache;
77 1055 }
78
79 /**
80 * Get the active union lookup cache
81 *
82 * @return Active lookup cache
83 */
84 822 f<LookupCache<Union>*> getActiveUnionLookupCache() {
85 822 assert ACTIVE_UNION_LOOKUP_CACHE != nil<LookupCache<Union>*>;
86 822 return ACTIVE_UNION_LOOKUP_CACHE;
87 }
88
89 /**
90 * Check if there is a union in this scope, fulfilling all given requirements and if found, return it.
91 * If more than one union matches the requirement, this is reported as an ambiguity error.
92 *
93 * @param matchScope Scope to match against
94 * @param qt Union name requirement
95 * @param reqTemplateTypes Template types to substantiate generic types
96 * @param node Instantiation AST node for printing error messages
97 * @return Matched union or nil
98 */
99 62 public f<Union*> matchUnion(Scope* matchScope, const String& qt, const QualTypeList& reqTemplateTypes, const ASTNode* node) {
100 // The IR generator reaches this from the worker threads of the parallel back end
101 62 ConditionalLock _lock = ConditionalLock(getSymbolRegistryMutex());
102
103 // Do cache lookup
104 62 LookupCache<Union>* cache = getActiveUnionLookupCache();
105 62 const Hash cacheKey = getUnionCacheKey(matchScope, qt, reqTemplateTypes);
106
2/2
✓ Branch 0 taken 38 times.
✓ Branch 1 taken 24 times.
 62 if cache.lookupCache.contains(cacheKey) {
107 38 cache.lookupCacheHits++;
108 76 return cache.lookupCache.get(cacheKey);
109 }
110 24 cache.lookupCacheMisses++;
111
112 // Loop over union registry to find unions, that match the requirements of the instantiation
113 24 Vector<Union*> matches;
114
2/2
✓ Branch 0 taken 28 times.
✓ Branch 1 taken 24 times.
 52 foreach Pair<const String&, UnionManifestationList&> defEntry : matchScope.unions {
115 28 const String& unionId = defEntry.getFirst();
116
2/2
✓ Branch 0 taken 11 times.
✓ Branch 1 taken 28 times.
 39 foreach Pair<const String&, Union&> manEntry : defEntry.getSecond() {
117 28 const String& mangledName = manEntry.getFirst();
118 28 const Union& presetUnion = manEntry.getSecond();
119 // Skip generic and newly inserted substantiations to prevent double matching of a union
120
2/4
✗ Branch 0 not taken.
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 28 times.
 28 if presetUnion.structBase.isGenericSubstantiation() || presetUnion.isNewlyInserted {
121 ✗ continue;
122 }
123
124 // Copy the union to be able to substantiate types
125 28 Union candidate = presetUnion;
126
127 // Check name requirement
128
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 20 times.
 28 if !matchName(candidate, qt) {
129 8 break; // Leave the whole manifestation list, because all manifestations in this list have the same name
130 }
131
132 // Prepare mapping table from generic type name to concrete type
133 20 candidate.typeMapping.clear();
134
135 // Check template types requirement
136
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 20 times.
 20 if !matchTemplateTypes(candidate, reqTemplateTypes, candidate.typeMapping, node) {
137 ✗ continue; // Leave this manifestation and continue with the next one
138 }
139
140 // Map field types from generic to concrete
141 20 substantiateFieldTypes(candidate, candidate.typeMapping, node);
142
143 // We found a match! -> Set the actual candidate and its entry to used
144 20 candidate.used = true;
145 20 candidate.entry.used = true;
146
147 // Check if it needs to be substantiated
148
2/2
✓ Branch 0 taken 11 times.
✓ Branch 1 taken 9 times.
 20 if presetUnion.templateTypes.isEmpty() {
149 11 assert matchScope.unions.contains(unionId);
150 11 UnionManifestationList& unionManifestations = matchScope.unions.get(unionId);
151 11 assert unionManifestations.contains(mangledName);
152 11 Union* unionMatch = &unionManifestations.get(mangledName);
153 11 unionMatch.used = true;
154 11 matches.pushBack(unionMatch);
155 11 continue; // Match was successful -> match the next union
156 }
157
158 // Check if we already have this manifestation and can simply re-use it
159 9 const String candidateSignature = candidate.structBase.getSignature();
160 9 UnionManifestationList& defManifestations = defEntry.getSecond();
161
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 9 times.
 9 if defManifestations.contains(candidateSignature) {
162 ✗ Union& existingManifestation = defManifestations.get(candidateSignature);
163 ✗ existingManifestation.used = true;
164 ✗ matches.pushBack(&existingManifestation);
165 ✗ break; // Leave the whole manifestation list to not double-match the manifestation
166 }
167
168 // Insert the substantiated version if required
169 9 Union* substantiatedUnion = insertSubstantiation(matchScope, candidate, presetUnion.declNode);
170 9 UnionManifestationList& presetManifestations = matchScope.unions.get(unionId);
171 9 Union& presetManifestation = presetManifestations.get(mangledName);
172 9 substantiatedUnion.genericPreset = &presetManifestation.structBase;
173 9 const ASTUnionDefNode* unionDefNode = downcast<ASTUnionDefNode>(substantiatedUnion.structBase.declNode);
174 9 unionDefNode.unionManifestations.pushBack(substantiatedUnion);
175 9 substantiatedUnion.isNewlyInserted = true; // To not iterate over it in the same matching
176
177 // Copy union entry
178 9 const String newSignature = substantiatedUnion.structBase.getSignature();
179 9 matchScope.lookupStrict(substantiatedUnion.name).used = true;
180 9 substantiatedUnion.entry = matchScope.symbolTable.copySymbol(substantiatedUnion.name, newSignature);
181 9 assert substantiatedUnion.entry != nil<SymbolTableEntry*>;
182
183 // Copy union scope
184 9 const String oldScopeName = presetUnion.getScopeName();
185 9 const String newScopeName = substantiatedUnion.getScopeName();
186 9 matchScope.copyChildScope(oldScopeName, newScopeName);
187 9 substantiatedUnion.scope = matchScope.getChildScope(newScopeName);
188 9 assert substantiatedUnion.scope != nil<Scope*>;
189 9 substantiatedUnion.scope.isGenericScope = false;
190
191 // Attach the template types to the new union entry
192 9 const QualType& oldEntryType = substantiatedUnion.entry.getQualType();
193 9 const QualTypeList concreteTemplateTypes = substantiatedUnion.structBase.getTemplateTypes();
194 9 const QualType entryTypeWithTemplates = oldEntryType.getWithTemplateTypes(concreteTemplateTypes);
195 9 const QualType entryType = entryTypeWithTemplates.getWithBodyScope(substantiatedUnion.scope);
196 9 substantiatedUnion.entry.updateType(entryType, true);
197
198 // Replace symbol types of field entries with concrete types
199 9 assert substantiatedUnion.scope != nil<Scope*>;
200 9 const unsigned long fieldCount = substantiatedUnion.fieldTypes.getSize();
201 9 const unsigned long explicitFieldsStartIdx = substantiatedUnion.scope.getFieldCount() - fieldCount;
202 9 unsigned long i = 0ul;
203
2/2
✓ Branch 0 taken 9 times.
✓ Branch 1 taken 18 times.
 27 while i < fieldCount {
204 // Replace field type with concrete template type
205 18 SymbolTableEntry* fieldEntry = substantiatedUnion.scope.lookupField(cast<unsigned int>(explicitFieldsStartIdx + i));
206 18 assert fieldEntry != nil<SymbolTableEntry*> && fieldEntry.isField();
207 18 QualType& fieldType = substantiatedUnion.fieldTypes.get(i);
208 18 QualType baseType = fieldType.getBase();
209
210 // Set the body scope of fields that are of type <candidate-union>*
211
1/2
✓ Branch 0 taken 18 times.
✗ Branch 1 not taken.
 18 if baseType.matches(substantiatedUnion.entry.getQualType(), false, true, true) {
212 ✗ fieldType = fieldType.replaceBaseType(baseType.getWithBodyScope(substantiatedUnion.scope));
213 ✗ }
214
215 18 fieldEntry.updateType(fieldType, /*overwriteExistingType=*/true);
216
217 // Instantiate structs/unions nested by value
218
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 18 times.
 18 if baseType.is(SuperType::TY_STRUCT) {
219 ✗ const Struct* _ = baseType.getStruct(node);
220
1/2
✓ Branch 0 taken 18 times.
✗ Branch 1 not taken.
 18 } else if baseType.is(SuperType::TY_UNION) {
221 ✗ const Union* _ = baseType.getUnion(node);
222 18 }
223
224 18 i++;
225 18 }
226
227 // Add to matched unions
228 9 matches.pushBack(substantiatedUnion);
229 // Leave the manifestation list: the remaining manifestations are substantiations, which are skipped anyway, and
230 // iterating the hash table further after inserting into it could visit the generic preset a second time
231 9 break;
232 28 }
233 28 }
234
235 // If no matches were found, return a nil
236
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 20 times.
 24 if matches.isEmpty() {
237 4 return nil<Union*>;
238 }
239
240 // Check if more than one union matches the requirements
241
1/2
✓ Branch 0 taken 20 times.
✗ Branch 1 not taken.
 20 if matches.getSize() > 1l {
242 ✗ throwSemanticError(node, SemanticErrorType::UNION_AMBIGUITY, String("Multiple unions match the requested signature"));
243 // The compilation is aborted after this stage. Until then, deterministically pick the first candidate
244 ✗ }
245 20 Union* matchedUnion = matches.front();
246 20 matchedUnion.isNewlyInserted = false;
247
248 // Insert into cache
249 20 cache.lookupCache.upsert(cacheKey, matchedUnion);
250
251 40 return matchedUnion;
252 62 }
253
254 /**
255 * Checks if the matching candidate fulfills the name requirement
256 */
257 28 f<bool> matchName(const Union& candidate, const String& reqName) {
258 28 return candidate.name == reqName;
259 }
260
261 /**
262 * Checks if the matching candidate fulfills the template types requirement
263 */
264 20 f<bool> matchTemplateTypes(Union& candidate, const QualTypeList& reqTemplateTypes, TypeMapping& typeMapping, const ASTNode* node) {
265 // Check if the number of types match
266
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 20 times.
 20 if reqTemplateTypes.getSize() != candidate.templateTypes.getSize() {
267 ✗ return false;
268 }
269
270
271 // Loop over all template types
272
2/2
✓ Branch 0 taken 9 times.
✓ Branch 1 taken 20 times.
 29 foreach unsigned long i, GenericType& candidateTemplateType : candidate.templateTypes {
273 9 QualType& candidateType = candidateTemplateType.qualType;
274 9 const QualType& reqType = reqTemplateTypes.get(i);
275
276 // Check if the requested template type matches the candidate template type. The type mapping may be extended
277
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 9 times.
 9 if !matchRequestedToCandidateType(candidateType, reqType, typeMapping, candidate.templateTypes, true, false) {
278 ✗ return false;
279 }
280
281 // Substantiate the candidate param type, based on the type mapping
282
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 9 times.
 9 if candidateType.hasAnyGenericParts() {
283 9 substantiateTypeWithTypeMapping(candidateType, typeMapping, node);
284 9 }
285 9 }
286
287 20 return true;
288 }
289
290 /**
291 * Come up with the concrete field types, by applying the type mapping onto the generic field types
292 */
293 20 p substantiateFieldTypes(Union& candidate, const TypeMapping& typeMapping, const ASTNode* node) {
294 // Loop over all explicit field types and substantiate the generic ones
295
2/2
✓ Branch 0 taken 44 times.
✓ Branch 1 taken 20 times.
 64 foreach QualType& fieldType : candidate.fieldTypes {
296
2/2
✓ Branch 0 taken 35 times.
✓ Branch 1 taken 9 times.
 44 if fieldType.hasAnyGenericParts() {
297 9 substantiateTypeWithTypeMapping(fieldType, typeMapping, node);
298 9 }
299 44 }
300 20 }
301
302
303 /**
304 * Calculate the cache key for the union lookup cache
305 *
306 * @param scope Scope to match against
307 * @param name Union name requirement
308 * @param templateTypes Template types to substantiate generic types
309 * @return Cache key
310 */
311 62 f<Hash> getUnionCacheKey(const Scope* scope, const String& name, const QualTypeList& templateTypes) {
312 62 Hash hash = 0ul;
313 62 hashCombine64(hash, hashPointer(scope));
314 62 hashCombine64(hash, hash(name));
315 62 hashCombine64(hash, hashQualTypeList(templateTypes));
316 62 return hash;
317 }
318
319 /**
320 * Dump usage statistics for the lookup cache
321 */
322 760 public f<String> dumpUnionLookupCacheStatistics() {
323 760 LookupCache<Union>* cache = getActiveUnionLookupCache();
324 760 return cache.dumpLookupCacheStatistics("UnionManager");
325 }
326