GCC Code Coverage Report

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