GCC Code Coverage Report

Directory: ../
File: src/typechecker/InterfaceManager.cpp
Date: 2025-03-05 01:50:32
Exec Total Coverage
Lines: 118 127 92.9%
Functions: 12 12 100.0%
Branches: 117 215 54.4%
Line Branch Exec Source
1 // Copyright (c) 2021-2025 ChilliBits. All rights reserved.
2
3 #include "InterfaceManager.h"
4
5 #include <ast/ASTNodes.h>
6 #include <exception/SemanticError.h>
7 #include <symboltablebuilder/Scope.h>
8 #include <symboltablebuilder/SymbolTableBuilder.h>
9 #include <typechecker/TypeMatcher.h>
10 #include <util/CustomHashFunctions.h>
11
12 namespace spice::compiler {
13
14 // Static member initialization
15 std::unordered_map<uint64_t, Interface *> InterfaceManager::lookupCache = {};
16 size_t InterfaceManager::lookupCacheHits = 0;
17 size_t InterfaceManager::lookupCacheMisses = 0;
18
19 82 Interface *InterfaceManager::insert(Scope *insertScope, Interface &spiceInterface, std::vector<Interface *> *nodeInterfaceList) {
20 // Open a new manifestation list. Which gets filled by the substantiated manifestations of the interface
21
1/2
✓ Branch 0 (4→5) taken 82 times.
✗ Branch 1 (4→11) not taken.
 82 insertScope->interfaces.insert({spiceInterface.declNode->codeLoc, InterfaceManifestationList()});
22
23 // Save substantiation in declaration node
24
1/2
✓ Branch 0 (7→8) taken 82 times.
✗ Branch 1 (7→17) not taken.
 82 Interface *substantiation = insertSubstantiation(insertScope, spiceInterface, spiceInterface.declNode);
25
1/2
✓ Branch 0 (8→9) taken 82 times.
✗ Branch 1 (8→17) not taken.
 82 nodeInterfaceList->push_back(substantiation);
26
27 82 return substantiation;
28 }
29
30 201 Interface *InterfaceManager::insertSubstantiation(Scope *insertScope, Interface &newManifestation, const ASTNode *declNode) {
31
1/2
✓ Branch 0 (2→3) taken 201 times.
✗ Branch 1 (2→31) not taken.
 201 const std::string signature = newManifestation.getSignature();
32
33 // Make sure that the manifestation does not exist already
34
2/2
✓ Branch 0 (13→5) taken 201 times.
✓ Branch 1 (13→14) taken 201 times.
 402 for ([[maybe_unused]] const auto &manifestations : insertScope->interfaces)
35
3/6
✓ Branch 0 (6→7) taken 201 times.
✗ Branch 1 (6→27) not taken.
✓ Branch 2 (7→8) taken 201 times.
✗ Branch 3 (7→25) not taken.
✗ Branch 4 (8→9) not taken.
✓ Branch 5 (8→10) taken 201 times.
 201 assert(!manifestations.second.contains(newManifestation.getSignature()));
36
37 // Retrieve the matching manifestation list of the scope
38
2/4
✓ Branch 0 (14→15) taken 201 times.
✗ Branch 1 (14→29) not taken.
✗ Branch 2 (15→16) not taken.
✓ Branch 3 (15→17) taken 201 times.
 201 assert(insertScope->interfaces.contains(declNode->codeLoc));
39
1/2
✓ Branch 0 (17→18) taken 201 times.
✗ Branch 1 (17→29) not taken.
 201 InterfaceManifestationList &manifestationList = insertScope->interfaces.at(declNode->codeLoc);
40
41 // Add substantiated interface
42 201 newManifestation.manifestationIndex = manifestationList.size();
43
1/2
✓ Branch 0 (19→20) taken 201 times.
✗ Branch 1 (19→29) not taken.
 201 manifestationList.emplace(signature, newManifestation);
44
1/2
✓ Branch 0 (20→21) taken 201 times.
✗ Branch 1 (20→29) not taken.
 402 return &manifestationList.at(signature);
45 201 }
46
47 /**
48 * Check if there is an interface in this scope, fulfilling all given requirements and if found, return it.
49 * If more than one interface matches the requirement, an error gets thrown
50 *
51 * @param matchScope Scope to match against
52 * @param reqName Interface name requirement
53 * @param reqTemplateTypes Template types to substantiate generic types
54 * @param node Instantiation AST node for printing error messages
55 * @return Matched interface or nullptr
56 */
57 1160 Interface *InterfaceManager::match(Scope *matchScope, const std::string &reqName, const QualTypeList &reqTemplateTypes,
58 const ASTNode *node) {
59 // Do cache lookup
60
1/2
✓ Branch 0 (2→3) taken 1160 times.
✗ Branch 1 (2→160) not taken.
 1160 const uint64_t cacheKey = getCacheKey(matchScope, reqName, reqTemplateTypes);
61
3/4
✓ Branch 0 (3→4) taken 1160 times.
✗ Branch 1 (3→160) not taken.
✓ Branch 2 (4→5) taken 953 times.
✓ Branch 3 (4→7) taken 207 times.
 1160 if (lookupCache.contains(cacheKey)) {
62 953 lookupCacheHits++;
63
1/2
✓ Branch 0 (5→6) taken 953 times.
✗ Branch 1 (5→160) not taken.
 953 return lookupCache.at(cacheKey);
64 }
65 207 lookupCacheMisses++;
66
67 // Copy the registry to prevent iterating over items, that are created within the loop
68
1/2
✓ Branch 0 (7→8) taken 207 times.
✗ Branch 1 (7→160) not taken.
 207 InterfaceRegistry interfaceRegistry = matchScope->interfaces;
69 // Loop over interface registry to find interfaces, that match the requirements of the instantiation
70 207 std::vector<Interface *> matches;
71
2/2
✓ Branch 0 (98→10) taken 207 times.
✓ Branch 1 (98→99) taken 207 times.
 414 for (const auto &[defCodeLocStr, m] : interfaceRegistry) {
72 // Copy the manifestation list to prevent iterating over items, that are created within the loop
73
1/2
✓ Branch 0 (13→14) taken 207 times.
✗ Branch 1 (13→145) not taken.
 207 const InterfaceManifestationList manifestations = m;
74
2/2
✓ Branch 0 (94→16) taken 351 times.
✓ Branch 1 (94→95) taken 138 times.
 489 for (const auto &[mangledName, presetInterface] : manifestations) {
75 // Skip generic substantiations to prevent double matching of an interface
76
3/4
✓ Branch 0 (19→20) taken 351 times.
✗ Branch 1 (19→141) not taken.
✓ Branch 2 (20→21) taken 144 times.
✓ Branch 3 (20→22) taken 207 times.
 351 if (presetInterface.isGenericSubstantiation())
77 163 continue;
78
79 // Copy the interface to be able to substantiate types
80
1/2
✓ Branch 0 (22→23) taken 207 times.
✗ Branch 1 (22→141) not taken.
 207 Interface candidate = presetInterface;
81
82 // Check name requirement
83
1/2
✗ Branch 0 (24→25) not taken.
✓ Branch 1 (24→26) taken 207 times.
 207 if (!matchName(candidate, reqName))
84 ✗ break; // Leave the whole manifestation list, because all manifestations in this list have the same name
85
86 // Prepare mapping table from generic type name to concrete type
87 207 TypeMapping &typeMapping = candidate.typeMapping;
88 207 typeMapping.clear();
89
1/2
✓ Branch 0 (28→29) taken 207 times.
✗ Branch 1 (28→139) not taken.
 207 typeMapping.reserve(candidate.templateTypes.size());
90
91 // Check template types requirement
92
2/4
✓ Branch 0 (29→30) taken 207 times.
✗ Branch 1 (29→139) not taken.
✗ Branch 2 (30→31) not taken.
✓ Branch 3 (30→32) taken 207 times.
 207 if (!matchTemplateTypes(candidate, reqTemplateTypes, typeMapping, node))
93 ✗ continue; // Leave this manifestation and continue with the next one
94
95 // Map signatures from generic to concrete
96
1/2
✓ Branch 0 (32→33) taken 207 times.
✗ Branch 1 (32→139) not taken.
 207 substantiateSignatures(candidate, typeMapping, node);
97
98 // We found a match! -> Set the actual candidate and its entry to used
99 207 candidate.used = true;
100 207 candidate.entry->used = true;
101
102 // Check if it needs to be substantiated
103
2/2
✓ Branch 0 (34→35) taken 19 times.
✓ Branch 1 (34→47) taken 188 times.
 207 if (presetInterface.templateTypes.empty()) {
104
5/10
✓ Branch 0 (35→36) taken 19 times.
✗ Branch 1 (35→139) not taken.
✓ Branch 2 (36→37) taken 19 times.
✗ Branch 3 (36→41) not taken.
✓ Branch 4 (37→38) taken 19 times.
✗ Branch 5 (37→139) not taken.
✓ Branch 6 (38→39) taken 19 times.
✗ Branch 7 (38→139) not taken.
✓ Branch 8 (39→40) taken 19 times.
✗ Branch 9 (39→41) not taken.
 19 assert(matchScope->interfaces.contains(defCodeLocStr) && matchScope->interfaces.at(defCodeLocStr).contains(mangledName));
105
3/6
✓ Branch 0 (42→43) taken 19 times.
✗ Branch 1 (42→120) not taken.
✓ Branch 2 (43→44) taken 19 times.
✗ Branch 3 (43→120) not taken.
✓ Branch 4 (44→45) taken 19 times.
✗ Branch 5 (44→120) not taken.
 19 matches.push_back(&matchScope->interfaces.at(defCodeLocStr).at(mangledName));
106 19 matches.back()->used = true;
107 19 continue; // Match was successful -> match the next interface
108 }
109
110 // Check if we already have this manifestation and can simply re-use it
111
4/6
✓ Branch 0 (47→48) taken 188 times.
✗ Branch 1 (47→123) not taken.
✓ Branch 2 (48→49) taken 188 times.
✗ Branch 3 (48→121) not taken.
✓ Branch 4 (50→51) taken 69 times.
✓ Branch 5 (50→57) taken 119 times.
 188 if (manifestations.contains(candidate.getSignature())) {
112
4/8
✓ Branch 0 (51→52) taken 69 times.
✗ Branch 1 (51→127) not taken.
✓ Branch 2 (52→53) taken 69 times.
✗ Branch 3 (52→126) not taken.
✓ Branch 4 (53→54) taken 69 times.
✗ Branch 5 (53→124) not taken.
✓ Branch 6 (54→55) taken 69 times.
✗ Branch 7 (54→124) not taken.
 69 matches.push_back(&matchScope->interfaces.at(defCodeLocStr).at(candidate.getSignature()));
113 69 break; // Leave the whole manifestation list to not double-match the manifestation
114 }
115
116 // Insert the substantiated version if required
117
1/2
✓ Branch 0 (57→58) taken 119 times.
✗ Branch 1 (57→139) not taken.
 119 Interface *substantiatedInterface = insertSubstantiation(matchScope, candidate, presetInterface.declNode);
118
2/4
✓ Branch 0 (58→59) taken 119 times.
✗ Branch 1 (58→139) not taken.
✓ Branch 2 (59→60) taken 119 times.
✗ Branch 3 (59→139) not taken.
 119 substantiatedInterface->genericPreset = &matchScope->interfaces.at(defCodeLocStr).at(mangledName);
119
2/4
✓ Branch 0 (60→61) taken 119 times.
✗ Branch 1 (60→139) not taken.
✓ Branch 2 (61→62) taken 119 times.
✗ Branch 3 (61→139) not taken.
 119 substantiatedInterface->declNode->getInterfaceManifestations()->push_back(substantiatedInterface);
120
121 // Copy interface entry
122
1/2
✓ Branch 0 (62→63) taken 119 times.
✗ Branch 1 (62→139) not taken.
 119 const std::string newSignature = substantiatedInterface->getSignature();
123
1/2
✓ Branch 0 (63→64) taken 119 times.
✗ Branch 1 (63→137) not taken.
 119 matchScope->lookupStrict(substantiatedInterface->name)->used = true;
124
1/2
✓ Branch 0 (66→67) taken 119 times.
✗ Branch 1 (66→137) not taken.
 119 substantiatedInterface->entry = matchScope->symbolTable.copySymbol(substantiatedInterface->name, newSignature);
125
1/2
✗ Branch 0 (67→68) not taken.
✓ Branch 1 (67→69) taken 119 times.
 119 assert(substantiatedInterface->entry != nullptr);
126
127 // Copy interface scope
128
1/2
✓ Branch 0 (69→70) taken 119 times.
✗ Branch 1 (69→137) not taken.
 119 const std::string newScopeName = INTERFACE_SCOPE_PREFIX + newSignature;
129
2/4
✓ Branch 0 (70→71) taken 119 times.
✗ Branch 1 (70→130) not taken.
✓ Branch 2 (71→72) taken 119 times.
✗ Branch 3 (71→128) not taken.
 119 matchScope->copyChildScope(INTERFACE_SCOPE_PREFIX + presetInterface.name, newScopeName);
130
1/2
✓ Branch 0 (73→74) taken 119 times.
✗ Branch 1 (73→135) not taken.
 119 substantiatedInterface->scope = matchScope->getChildScope(newScopeName);
131
1/2
✗ Branch 0 (74→75) not taken.
✓ Branch 1 (74→76) taken 119 times.
 119 assert(substantiatedInterface->scope != nullptr);
132 119 substantiatedInterface->scope->isGenericScope = false;
133
134 // Attach the template types to the new interface entry
135
1/2
✓ Branch 0 (76→77) taken 119 times.
✗ Branch 1 (76→134) not taken.
 119 QualType entryType = substantiatedInterface->entry->getQualType()
136
2/4
✓ Branch 0 (77→78) taken 119 times.
✗ Branch 1 (77→133) not taken.
✓ Branch 2 (78→79) taken 119 times.
✗ Branch 3 (78→131) not taken.
 238 .getWithTemplateTypes(substantiatedInterface->getTemplateTypes())
137
1/2
✓ Branch 0 (79→80) taken 119 times.
✗ Branch 1 (79→131) not taken.
 119 .getWithBodyScope(substantiatedInterface->scope);
138
1/2
✓ Branch 0 (81→82) taken 119 times.
✗ Branch 1 (81→135) not taken.
 119 substantiatedInterface->entry->updateType(entryType, true);
139
140 // Add to matched interfaces
141
1/2
✓ Branch 0 (82→83) taken 119 times.
✗ Branch 1 (82→135) not taken.
 119 matches.push_back(substantiatedInterface);
142
3/3
✓ Branch 0 (87→88) taken 119 times.
✓ Branch 1 (87→90) taken 19 times.
✓ Branch 2 (87→91) taken 69 times.
 207 }
143 207 }
144
145 // If no matches were found, return a nullptr
146
1/2
✗ Branch 0 (100→101) not taken.
✓ Branch 1 (100→102) taken 207 times.
 207 if (matches.empty())
147 ✗ return nullptr;
148
149 // Check if more than one interface matches the requirements
150
1/2
✗ Branch 0 (103→104) not taken.
✓ Branch 1 (103→112) taken 207 times.
 207 if (matches.size() > 1)
151 ✗ throw SemanticError(node, INTERFACE_AMBIGUITY, "Multiple interfaces match the requested signature");
152
153 // Insert into cache
154
1/2
✓ Branch 0 (113→114) taken 207 times.
✗ Branch 1 (113→156) not taken.
 207 lookupCache[cacheKey] = matches.front();
155
156 207 return matches.front();
157 207 }
158
159 /**
160 * Checks if the matching candidate fulfills the name requirement
161 *
162 * @param candidate Matching candidate interface
163 * @param reqName Requested interface name
164 * @return Fulfilled or not
165 */
166 207 bool InterfaceManager::matchName(const Interface &candidate, const std::string &reqName) { return candidate.name == reqName; }
167
168 /**
169 * Checks if the matching candidate fulfills the template types requirement
170 *
171 * @param candidate Matching candidate interface
172 * @param reqTemplateTypes Requested interface template types
173 * @param typeMapping Generic type mapping
174 * @param node Instantiation AST node for printing error messages
175 * @return Fulfilled or not
176 */
177 207 bool InterfaceManager::matchTemplateTypes(Interface &candidate, const QualTypeList &reqTemplateTypes, TypeMapping &typeMapping, const ASTNode *node) {
178 // Check if the number of types match
179 207 const size_t typeCount = reqTemplateTypes.size();
180
1/2
✗ Branch 0 (4→5) not taken.
✓ Branch 1 (4→6) taken 207 times.
 207 if (typeCount != candidate.templateTypes.size())
181 ✗ return false;
182
183 // Give the type matcher a way to retrieve instances of GenericType by their name
184 602 TypeMatcher::ResolverFct genericTypeResolver = [&](const std::string &genericTypeName) {
185 188 return getGenericTypeOfCandidateByName(candidate, genericTypeName);
186 207 };
187
188 // Loop over all template types
189
2/2
✓ Branch 0 (17→8) taken 188 times.
✓ Branch 1 (17→18) taken 207 times.
 395 for (size_t i = 0; i < typeCount; i++) {
190
1/2
✓ Branch 0 (8→9) taken 188 times.
✗ Branch 1 (8→22) not taken.
 188 const QualType &reqType = reqTemplateTypes.at(i);
191
1/2
✓ Branch 0 (9→10) taken 188 times.
✗ Branch 1 (9→22) not taken.
 188 QualType &candidateType = candidate.templateTypes.at(i);
192
193 // Check if the requested template type matches the candidate template type. The type mapping may be extended
194
2/4
✓ Branch 0 (10→11) taken 188 times.
✗ Branch 1 (10→22) not taken.
✗ Branch 2 (11→12) not taken.
✓ Branch 3 (11→13) taken 188 times.
 188 if (!TypeMatcher::matchRequestedToCandidateType(candidateType, reqType, typeMapping, genericTypeResolver, false))
195 ✗ return false;
196
197 // Substantiate the candidate param type, based on the type mapping
198
2/4
✓ Branch 0 (13→14) taken 188 times.
✗ Branch 1 (13→22) not taken.
✓ Branch 2 (14→15) taken 188 times.
✗ Branch 3 (14→16) not taken.
 188 if (candidateType.hasAnyGenericParts())
199
1/2
✓ Branch 0 (15→16) taken 188 times.
✗ Branch 1 (15→22) not taken.
 188 TypeMatcher::substantiateTypeWithTypeMapping(candidateType, typeMapping, node);
200 }
201
202 207 return true;
203 207 }
204
205 /**
206 * Come up with the concrete signatures, by applying the type mapping onto the generic signatures
207 *
208 * @param candidate Candidate interface
209 * @param typeMapping Generic type mapping
210 * @param node Instantiation AST node for printing error messages
211 */
212 207 void InterfaceManager::substantiateSignatures(Interface &candidate, const TypeMapping &typeMapping, const ASTNode *node) {
213 // Loop over all signatures and substantiate the generic ones
214
2/2
✓ Branch 0 (34→4) taken 541 times.
✓ Branch 1 (34→35) taken 207 times.
 748 for (Function *method : candidate.methods) {
215 // Skip methods, that are already fully substantiated
216
3/4
✓ Branch 0 (5→6) taken 541 times.
✗ Branch 1 (5→37) not taken.
✓ Branch 2 (6→7) taken 243 times.
✓ Branch 3 (6→8) taken 298 times.
 541 if (method->isFullySubstantiated())
217 243 continue;
218
219 // Substantiate return type
220
1/2
✗ Branch 0 (20→21) not taken.
✓ Branch 1 (20→22) taken 298 times.
 298 if (method->isNormalFunction())
221 ✗ FunctionManager::substantiateReturnType(*method, typeMapping, node);
222
223 // Substantiate param types
224
2/2
✓ Branch 0 (30→24) taken 2 times.
✓ Branch 1 (30→31) taken 298 times.
 300 for (auto &[qualType, isOptional] : method->paramList)
225
2/4
✓ Branch 0 (25→26) taken 2 times.
✗ Branch 1 (25→36) not taken.
✓ Branch 2 (26→27) taken 2 times.
✗ Branch 3 (26→28) not taken.
 2 if (qualType.isBase(TY_GENERIC))
226
1/2
✓ Branch 0 (27→28) taken 2 times.
✗ Branch 1 (27→36) not taken.
 2 TypeMatcher::substantiateTypeWithTypeMapping(qualType, typeMapping, node);
227 }
228 207 }
229
230 /**
231 * Searches the candidate template types for a generic type object with a certain name and return it
232 *
233 * @param candidate Matching candidate interface
234 * @param templateTypeName Template type name
235 * @return Generic type object
236 */
237 188 const GenericType *InterfaceManager::getGenericTypeOfCandidateByName(const Interface &candidate,
238 const std::string &templateTypeName) {
239
1/2
✓ Branch 0 (14→4) taken 188 times.
✗ Branch 1 (14→15) not taken.
 188 for (const GenericType &templateType : candidate.templateTypes) {
240
2/4
✓ Branch 0 (5→6) taken 188 times.
✗ Branch 1 (5→17) not taken.
✗ Branch 2 (6→7) not taken.
✓ Branch 3 (6→8) taken 188 times.
 188 if (!templateType.is(TY_GENERIC))
241 ✗ continue;
242
2/4
✓ Branch 0 (8→9) taken 188 times.
✗ Branch 1 (8→17) not taken.
✓ Branch 2 (10→11) taken 188 times.
✗ Branch 3 (10→12) not taken.
 188 if (templateType.getSubType() == templateTypeName)
243 188 return &templateType;
244 }
245 ✗ return nullptr;
246 }
247
248 /**
249 * Calculate the cache key for the interface lookup cache
250 *
251 * @param scope Scope to match against
252 * @param name Interface name requirement
253 * @param templateTypes Template types to substantiate generic types
254 * @return Cache key
255 */
256 1160 uint64_t InterfaceManager::getCacheKey(Scope *scope, const std::string &name, const QualTypeList &templateTypes) {
257 1063 const auto pred = [](size_t acc, const QualType &val) {
258 // Combine the previous hash value with the current element's hash, adjusted by a prime number to reduce collisions
259 1063 return acc * 31 + std::hash<QualType>{}(val);
260 };
261 // Calculate the cache key
262 1160 const uint64_t scopeHash = std::hash<Scope *>{}(scope);
263 1160 const uint64_t hashName = std::hash<std::string>{}(name);
264 1160 const uint64_t hashTemplateTypes = std::accumulate(templateTypes.begin(), templateTypes.end(), 0u, pred);
265 1160 return scopeHash ^ (hashName << 1) ^ (hashTemplateTypes << 2);
266 }
267
268 /**
269 * Clear the lookup cache
270 */
271 407 void InterfaceManager::cleanup() {
272 407 lookupCache.clear();
273 407 lookupCacheHits = 0;
274 407 lookupCacheMisses = 0;
275 407 }
276
277 /**
278 * Dump usage statistics for the lookup cache
279 */
280 191 std::string InterfaceManager::dumpLookupCacheStatistics() {
281
1/2
✓ Branch 0 (2→3) taken 191 times.
✗ Branch 1 (2→22) not taken.
 191 std::stringstream stats;
282
2/4
✓ Branch 0 (3→4) taken 191 times.
✗ Branch 1 (3→20) not taken.
✓ Branch 2 (4→5) taken 191 times.
✗ Branch 3 (4→20) not taken.
 191 stats << "InterfaceManager lookup cache statistics:" << std::endl;
283
3/6
✓ Branch 0 (5→6) taken 191 times.
✗ Branch 1 (5→20) not taken.
✓ Branch 2 (7→8) taken 191 times.
✗ Branch 3 (7→20) not taken.
✓ Branch 4 (8→9) taken 191 times.
✗ Branch 5 (8→20) not taken.
 191 stats << " lookup cache entries: " << lookupCache.size() << std::endl;
284
3/6
✓ Branch 0 (9→10) taken 191 times.
✗ Branch 1 (9→20) not taken.
✓ Branch 2 (10→11) taken 191 times.
✗ Branch 3 (10→20) not taken.
✓ Branch 4 (11→12) taken 191 times.
✗ Branch 5 (11→20) not taken.
 191 stats << " lookup cache hits: " << lookupCacheHits << std::endl;
285
3/6
✓ Branch 0 (12→13) taken 191 times.
✗ Branch 1 (12→20) not taken.
✓ Branch 2 (13→14) taken 191 times.
✗ Branch 3 (13→20) not taken.
✓ Branch 4 (14→15) taken 191 times.
✗ Branch 5 (14→20) not taken.
 191 stats << " lookup cache misses: " << lookupCacheMisses << std::endl;
286
1/2
✓ Branch 0 (15→16) taken 191 times.
✗ Branch 1 (15→20) not taken.
 382 return stats.str();
287 191 }
288
289 } // namespace spice::compiler
290