GCC Code Coverage Report

src/
Coverage:
low: ≥ 0%
medium: ≥ 75.0%
high: ≥ 90.0%
Lines:
130 / 138
94.2%
Branches:
49 / 56, 2 excl
87.5%
Functions:
17 / 19
89.5%
global/type-registry.spice
Line Branch Exec Source
1 // Copyright (c) 2021-2026 ChilliBits. All rights reserved.
2
3 // Std imports
4 import "std/data/vector";
5 import "std/data/unordered-map";
6 import "std/data/map";
7 import "std/data/pair";
8 import "std/text/stringstream";
9 import "std/math/hash";
10 import "std/os/recursive-mutex";
11
12 // Own imports
13 import "@/util/block-allocator";
14 import "@/util/memory";
15 import "@/util/concurrency";
16 import "@/symboltablebuilder/super-type";
17 import "@/symboltablebuilder/qual-type";
18 import "@/symboltablebuilder/type-chain";
19 import "@/symboltablebuilder/type";
20 import "@/symboltablebuilder/scope";
21
22 // The TypeRegistry interns every Type and hands back stable `const Type*` pointers, so that type identity can be
23 // compared by pointer. Spice has no usable mutable globals, so it is a normal struct owned by the GlobalResourceManager
24 // and threaded into each Type it creates (Type.registry), so the Type derivation methods (toPtr, getBase, ...) can re-enter it.
25 // Storage is a BlockAllocator<Type> (stable addresses, exactly like the parser's AST node pool) plus a hash ->
26 // bucket map for deduplication. Buckets (Vector<Type*>) are used instead of a single value per hash so that hash
27 // collisions are resolved exactly via structural equality.
28 766 public type TypeRegistry struct {
29 // The memory manager is declared before the allocator so that it outlives it (the allocator keeps a reference).
30 DefaultMemoryManager memoryManager
31 BlockAllocator<Type> alloc
32 UnorderedMap<Hash, Vector<Type*>> types
33 1055 unsigned long typeCount = 0ul
34 // Deriving a type (QualType.toPtr, ...) can insert into the registry while the back end runs in parallel. See
35 // ConditionalLock for why it is not locked unconditionally
36 RecursiveMutex typesMutex
37 }
38
39 // Active type registry, which context-free type creation like QualType(TY_INT) relies on. It is owned by the global
40 // resource manager.
41 TypeRegistry* ACTIVE_TYPE_REGISTRY;
42
43 /**
44 * Make the given type registry the active one. Context-free type creation, e.g. QualType(TY_INT), interns into it.
45 *
46 * @param registry Type registry, which must outlive all types created through it
47 */
48 1055 public p setActiveTypeRegistry(TypeRegistry* registry) {
49 1055 ACTIVE_TYPE_REGISTRY = registry;
50 1055 }
51
52 /**
53 * Get the active type registry
54 *
55 * @return Active type registry or nil if no type registry is active
56 */
57 4155381 public f<TypeRegistry*> getActiveTypeRegistry() {
58 4155381 return ACTIVE_TYPE_REGISTRY;
59 }
60
61 1055 public p TypeRegistry.ctor() {
62 1055 this.alloc = BlockAllocator<Type>(this.memoryManager);
63 1055 this.types = UnorderedMap<Hash, Vector<Type*>>();
64 1055 }
65
66 /**
67 * Get or insert a type built from a single super type
68 */
69 4150519 public f<const Type*> TypeRegistry.getOrInsert(SuperType superType) {
70 4150519 Type tmpType = Type(superType);
71 8301038 return this.getOrInsertType(tmpType);
72 4150519 }
73
74 /**
75 * Get or insert a type built from a super type and a sub type
76 */
77 6445 public f<const Type*> TypeRegistry.getOrInsertSub(SuperType superType, const String& subType) {
78 6445 Type tmpType = Type(superType, subType);
79 12890 return this.getOrInsertType(tmpType);
80 6445 }
81
82 /**
83 * Get or insert a type built from a super type, a sub type, a type id, type chain element data and template types
84 */
85 5079 public f<const Type*> TypeRegistry.getOrInsert(SuperType superType, const String& subType, unsigned long typeId, const TypeChainElementData& data, const QualTypeList& templateTypes) {
86 5079 Type tmpType = Type(superType, subType, typeId, data, templateTypes);
87 10158 return this.getOrInsertType(tmpType);
88 5079 }
89
90 /**
91 * Get or insert a type built from a full type chain
92 */
93 2320061 public f<const Type*> TypeRegistry.getOrInsertChain(const TypeChain& typeChain) {
94 2320061 Type tmpType = Type(typeChain);
95 4640122 return this.getOrInsertType(tmpType);
96 2320061 }
97
98 /**
99 * Get the number of types currently interned
100 */
101 ✗ public f<unsigned long> TypeRegistry.getTypeCount() {
102 ✗ return this.typeCount;
103 }
104
105 /**
106 * Dump all types in the type registry
107 */
108 760 public f<String> TypeRegistry.dump() {
109 // Sort to ensure deterministic output. Distinct types can share the same name (e.g. different body scopes), so count
110 // the occurrences of each name, to emit duplicates
111 760 Map<String, unsigned long> typeStrings;
112
2/2
✓ Branch 0 taken 65141 times.
✓ Branch 1 taken 760 times.
 65901 foreach Pair<const Hash&, Vector<Type*>&> bucket : this.types {
113
2/2
✓ Branch 0 taken 65141 times.
✓ Branch 1 taken 65141 times.
 130282 foreach Type* registryType : bucket.getSecond() {
114 65141 const String typeString = registryType.getName(false, true, true);
115
2/2
✓ Branch 0 taken 7544 times.
✓ Branch 1 taken 57597 times.
 65141 if typeStrings.contains(typeString) {
116 7544 typeStrings.get(typeString)++;
117 7544 } else {
118 57597 typeStrings.upsert(typeString, 1ul);
119 57597 }
120 65141 }
121 65141 }
122 // Serialize type registry
123 760 StringStream typeRegistryString;
124
2/2
✓ Branch 0 taken 57597 times.
✓ Branch 1 taken 760 times.
 58357 foreach Pair<const String&, unsigned long&> typeString : typeStrings {
125
2/2
✓ Branch 0 taken 65141 times.
✓ Branch 1 taken 57597 times.
 122738 for unsigned long i = 0ul; i < typeString.getSecond(); i++ {
126 65141 typeRegistryString << typeString.getFirst() << "\n";
127 65141 }
128 57597 }
129 1520 return typeRegistryString.str();
130 760 }
131
132 /**
133 * Clear the type registry. The types themselves are owned by the pool, not by the map, so they stay alive
134 * until the type registry is destroyed. This keeps the type pointers valid, that are still held by other components.
135 */
136 766 public p TypeRegistry.clear() {
137 766 this.types.clear();
138 766 this.typeCount = 0ul;
139 766 }
140
141 /**
142 * Core interning routine: hash the candidate type, return the matching cached instance, otherwise allocate a
143 * stable copy in the pool, wire its registry back-reference and remember it in the matching hash bucket.
144 */
145 6482104 f<const Type*> TypeRegistry.getOrInsertType(const Type& candidate) {
146 6482104 const Hash h = this.getTypeHash(candidate);
147 6482104 const Type* candidatePtr = &candidate;
148
149 6482104 ConditionalLock _ = ConditionalLock(&this.typesMutex);
150
151
2/2
✓ Branch 0 taken 69764 times.
✓ Branch 1 taken 6412340 times.
 6482104 if this.types.contains(h) {
152 // Search the bucket for a structurally equal type
153 6412340 Vector<Type*>& bucket = this.types.get(h);
154
1/2
✓ Branch 0 taken 6412340 times.
✗ Branch 1 not taken.
 6412340 foreach Type* existing : bucket {
155
2/4
✗ Branch 0 not taken.
✓ Branch 1 taken 6412340 times.
✓ Branch 2 taken 6412340 times.
✗ Branch 3 not taken.
 6412340 if existing.matches(candidatePtr, false) && haveSameBodyScopes(existing, candidatePtr) {
156 6412340 const Type* hit = existing;
157 12824680 return hit;
158 }
159 ✗ }
160 // Hash collision with a different type: allocate it and append to the existing bucket
161 ✗ Type* collisionType = this.allocateType(candidate);
162 ✗ bucket.pushBack(collisionType);
163 ✗ const Type* appended = collisionType;
164 ✗ return appended;
165 }
166
167 // First type with this hash: create a fresh bucket
168 69764 Type* newType = this.allocateType(candidate);
169 69764 Vector<Type*> bucket;
170 69764 bucket.pushBack(newType);
171 69764 this.types.upsert(h, bucket);
172 69764 const Type* newResult = newType;
173 139528 return newResult;
174 6482104 }
175
176 /**
177 * Allocate a stable copy of the given type in the pool, construct it in place and wire its registry back-reference.
178 */
179 69764 f<Type*> TypeRegistry.allocateType(const Type& candidate) {
180 69764 Type* newType = this.alloc.reserve<Type>();
181 unsafe {
182 69764 __placement_new<Type>(newType, candidate);
183 }
184 // Wire the non-owning registry back-reference so the type's derivation methods can re-enter the registry
185 69764 newType.registry = this;
186 69764 this.typeCount++;
187 69764 return newType;
188 }
189
190 /**
191 * Check if two types with the same structure also have the same body scopes. Type.matches ignores the body scopes of
192 * structs, interfaces and unions, but two manifestations of a generic type (e.g. the one bound to the generic struct scope
193 * and the one bound to the scope of the concrete substantiation) must be interned as distinct types.
194 */
195 6412340 f<bool> haveSameBodyScopes(const Type* lhs, const Type* rhs) {
196 6412340 assert lhs.typeChain.getSize() == rhs.typeChain.getSize();
197
2/2
✓ Branch 0 taken 6621873 times.
✓ Branch 1 taken 6412340 times.
 13034213 for unsigned long i = 0ul; i < lhs.typeChain.getSize(); i++ {
198 6621873 const TypeChainElement& lhsElement = lhs.typeChain.get(i);
199 6621873 const TypeChainElement& rhsElement = rhs.typeChain.get(i);
200 6621873 const SuperType superType = lhsElement.superType;
201
6/6
✓ Branch 0 taken 5163642 times.
✓ Branch 1 taken 1458231 times.
✓ Branch 2 taken 5157539 times.
✓ Branch 3 taken 6103 times.
✓ Branch 4 taken 101 times.
✓ Branch 5 taken 5157438 times.
 6621873 const bool hasBodyScope = superType == SuperType::TY_STRUCT || superType == SuperType::TY_INTERFACE || superType == SuperType::TY_UNION || superType == SuperType::TY_ENUM;
202
3/4
✓ Branch 0 taken 5157437 times.
✓ Branch 1 taken 1464436 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 6621873 times.
 6621873 if hasBodyScope && lhsElement.data.bodyScope != rhsElement.data.bodyScope {
203 ✗ return false;
204 }
205 6621873 }
206 6412340 return true;
207 }
208
209 // Id of the body scope of a type chain element (0 if there is none)
210 1729326 f<unsigned long> getBodyScopeId(const TypeChainElement& tce) {
211 1729326 const Scope* bodyScope = tce.data.bodyScope;
212
2/2
✓ Branch 0 taken 1728444 times.
✓ Branch 1 taken 882 times.
 1729326 if bodyScope == nil<const Scope*> {
213 882 return 0l;
214 }
215 1728444 return bodyScope.scopeId;
216 }
217
218 /**
219 * Compute the hash of a type over its type chain. Template and function param/return sub-types are hashed
220 * recursively (they are themselves interned Types).
221 */
222 7470455 public f<Hash> TypeRegistry.getTypeHash(const Type& candidate) {
223 7470455 Hash h = 0ul;
224
2/2
✓ Branch 0 taken 7862301 times.
✓ Branch 1 taken 7470455 times.
 15332756 foreach const TypeChainElement& tce : candidate.typeChain {
225 7862301 const Hash elementHash = this.hashElement(tce);
226 7862301 h = combineHashes(h, elementHash);
227 7862301 }
228 7470455 return h;
229 }
230
231 7862301 f<Hash> TypeRegistry.hashElement(const TypeChainElement& tce) {
232 7862301 Hash h = hash(cast<long>(tce.superType));
233 7862301 h = combineHashes(h, hash(tce.subType));
234 7862301 h = combineHashes(h, hash(tce.typeId));
235
236 // Hash the super-type-specific data payload
237
4/4
✓ Branch 0 taken 1729326 times.
✓ Branch 1 taken 132956 times.
✓ Branch 2 taken 5998332 times.
✓ Branch 3 taken 1687 times.
 7862301 switch tce.superType {
238 case SuperType::TY_ARRAY: {
239 1687 h = combineHashes(h, hash(cast<long>(tce.data.arraySize)));
240 1687 }
241 case SuperType::TY_FUNCTION, SuperType::TY_PROCEDURE: {
242 132956 h = combineHashes(h, hash(tce.data.hasCaptures));
243 132956 }
244 case SuperType::TY_STRUCT, SuperType::TY_INTERFACE, SuperType::TY_UNION, SuperType::TY_ENUM: {
245 // Hash the id of the body scope instead of its address, so that type hashes (e.g. typeid values) do not change
246 // between compiler runs
247 1729326 h = combineHashes(h, hash(cast<long>(getBodyScopeId(tce))));
248 1729326 }
249 5998332 default: {}
250 }
251
252 // Hash template types and function param/return types recursively by their interned content
253
2/2
✓ Branch 0 taken 830774 times.
✓ Branch 1 taken 7862301 times.
 8693075 foreach const QualType& templateType : tce.templateTypes {
254 830774 h = combineHashes(h, this.hashQualType(templateType));
255 830774 }
256
2/2
✓ Branch 0 taken 157530 times.
✓ Branch 1 taken 7862301 times.
 8019831 foreach const QualType& paramType : tce.paramTypes {
257 157530 h = combineHashes(h, this.hashQualType(paramType));
258 157530 }
259
260 7862301 return h;
261 }
262
263 988304 f<Hash> TypeRegistry.hashQualType(const QualType& qt) {
264 988304 Hash h = 0ul;
265
266 // Recurse into the (interned) raw type, if present
267
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 988304 times.
 988304 if qt.rawType != nil<const Type*> {
268 988304 const Type* rawType = qt.rawType;
269 988304 h = this.getTypeHash(*rawType);
270 988304 }
271
272 // Fold in the qualifier bits (the public qualifier is ignored)
273 988304 long bits = 0l;
274
2/2
✓ Branch 0 taken 942422 times.
✓ Branch 1 taken 45882 times.
 988304 if qt.qualifiers.isConst { bits = bits | 1l; }
275
2/2
✓ Branch 0 taken 721263 times.
✓ Branch 1 taken 267041 times.
 988304 if qt.qualifiers.isSigned { bits = bits | 2l; }
276
2/2
✓ Branch 0 taken 507913 times.
✓ Branch 1 taken 480391 times.
 988304 if qt.qualifiers.isUnsigned { bits = bits | 4l; }
277
2/2
✓ Branch 0 taken 941295 times.
✓ Branch 1 taken 47009 times.
 988304 if qt.qualifiers.isHeap { bits = bits | 8l; }
278
1/2
✓ Branch 0 taken 988304 times.
✗ Branch 1 not taken.
 988304 if qt.qualifiers.isInline { bits = bits | 16l; }
279
1/2
✓ Branch 0 taken 988304 times.
✗ Branch 1 not taken.
 988304 if qt.qualifiers.isComposition { bits = bits | 32l; }
280 988304 h = combineHashes(h, hash(bits));
281
282 988304 return h;
283 }
284