typechecker/type-matcher.spice
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | // Copyright (c) 2021-2026 ChilliBits. All rights reserved. | ||
| 2 | |||
| 3 | // Std imports | ||
| 4 | import "std/data/unordered-map"; | ||
| 5 | import "std/data/vector"; | ||
| 6 | |||
| 7 | // Own imports | ||
| 8 | import "@/exception/error-manager"; | ||
| 9 | import "@/model/struct-base"; | ||
| 10 | import "@/exception/semantic-error"; | ||
| 11 | import "@/ast/ast-nodes"; | ||
| 12 | import "@/model/generic-type"; | ||
| 13 | import "@/model/struct"; | ||
| 14 | import "@/model/interface"; | ||
| 15 | import "@/model/union"; | ||
| 16 | import "@/symboltablebuilder/super-type"; | ||
| 17 | import "@/symboltablebuilder/qual-type"; | ||
| 18 | |||
| 19 | /** | ||
| 20 | * Helper functions for FunctionManager, StructManager, InterfaceManager and UnionManager to match generic types. | ||
| 21 | * This is a tricky task, because the types can be indirect or/and nested. | ||
| 22 | */ | ||
| 23 | |||
| 24 | /** | ||
| 25 | * Search the given candidate template types for a generic type with a certain name | ||
| 26 | * | ||
| 27 | * @param candidateTemplateTypes Template types of the candidate | ||
| 28 | * @param genericTypeName Name of the generic type | ||
| 29 | * @param genericOnly Skip template types that are not generic (anymore) | ||
| 30 | * @return Generic type, or nil if not found | ||
| 31 | */ | ||
| 32 | 27259 | public f<const GenericType*> resolveGenericTypeByName(const Vector<GenericType>& candidateTemplateTypes, const String& genericTypeName, bool genericOnly) { | |
| 33 | 31481 | foreach const GenericType& templateType : candidateTemplateTypes { | |
| 34 | 31481 | if genericOnly && !templateType.qualType.is(SuperType::TY_GENERIC) { | |
| 35 | 863 | continue; | |
| 36 | } | ||
| 37 | 30618 | if templateType.qualType.getSubType() == genericTypeName { | |
| 38 | 27259 | return &templateType; | |
| 39 | } | ||
| 40 | 3359 | } | |
| 41 | ✗ | return nil<const GenericType*>; | |
| 42 | } | ||
| 43 | |||
| 44 | /** | ||
| 45 | * Match a list of requested types against a list of candidate types, extending the type mapping as needed. | ||
| 46 | * | ||
| 47 | * @param candidateTypes Candidate types | ||
| 48 | * @param reqTypes Requested types | ||
| 49 | * @param typeMapping Concrete template type mapping | ||
| 50 | * @param candidateTemplateTypes Template types of the candidate, used to look up generic types by their name | ||
| 51 | * @param genericOnly Only consider template types that are (still) generic when looking them up by name | ||
| 52 | * @param strictQualifiers Match qualifiers strictly | ||
| 53 | * @return Fulfilled or not | ||
| 54 | */ | ||
| 55 | 16214 | public f<bool> matchRequestedToCandidateTypes(const QualTypeList& candidateTypes, const QualTypeList& reqTypes, TypeMapping& typeMapping, const Vector<GenericType>& candidateTemplateTypes, bool genericOnly, bool strictQualifiers) { | |
| 56 | // Check if the size of template types matches | ||
| 57 | 16214 | if reqTypes.getSize() != candidateTypes.getSize() { | |
| 58 | ✗ | return false; | |
| 59 | } | ||
| 60 | |||
| 61 | // Loop through both lists at the same time and match each pair of template types individually | ||
| 62 | 35221 | foreach unsigned long i, const QualType& candidateType : candidateTypes { | |
| 63 | 19007 | const QualType& reqType = reqTypes.get(i); | |
| 64 | |||
| 65 | // Match the pair of template types | ||
| 66 | 19007 | if !matchRequestedToCandidateType(candidateType, reqType, typeMapping, candidateTemplateTypes, genericOnly, strictQualifiers) { | |
| 67 | ✗ | return false; | |
| 68 | } | ||
| 69 | 19007 | } | |
| 70 | 16214 | return true; | |
| 71 | } | ||
| 72 | |||
| 73 | /** | ||
| 74 | * Check if a requested type matches a candidate type, which may be generic. The type mapping may be extended. | ||
| 75 | * | ||
| 76 | * @param candidateTypeIn Candidate type | ||
| 77 | * @param requestedTypeIn Requested type | ||
| 78 | * @param typeMapping Concrete template type mapping | ||
| 79 | * @param candidateTemplateTypes Template types of the candidate, used to look up generic types by their name | ||
| 80 | * @param genericOnly Only consider template types that are (still) generic when looking them up by name | ||
| 81 | * @param strictQualifierMatching Match qualifiers strictly | ||
| 82 | * @return Fulfilled or not | ||
| 83 | */ | ||
| 84 | 238875 | public f<bool> matchRequestedToCandidateType(const QualType& candidateTypeIn, const QualType& requestedTypeIn, TypeMapping& typeMapping, const Vector<GenericType>& candidateTemplateTypes, bool genericOnly, bool strictQualifierMatching) { | |
| 85 | 238875 | QualType candidateType = candidateTypeIn; | |
| 86 | 238875 | QualType requestedType = requestedTypeIn; | |
| 87 | |||
| 88 | // A reference or pointer candidate gives access to the requested value or pointee. If that is const, the candidate has to | ||
| 89 | // be const as well, even if the qualifiers are not matched strictly. Unwrapping below loses this information. | ||
| 90 | // Candidates that are a generic type themselves (e.g. T&) are excluded, as they might be substantiated with const types. | ||
| 91 | 238875 | const QualType requestedNonRefType = requestedTypeIn.removeReferenceWrapper(); | |
| 92 | 238875 | const bool sharesValue = candidateTypeIn.isRef() || (candidateTypeIn.isPtr() && requestedNonRefType.isPtr()); | |
| 93 | 238875 | if sharesValue && !candidateTypeIn.isBase(SuperType::TY_GENERIC) && requestedTypeIn.qualifiers.isConst && !candidateTypeIn.qualifiers.isConst { | |
| 94 | 1641 | return false; | |
| 95 | } | ||
| 96 | |||
| 97 | // Unwrap as far as possible and remove reference wrappers if possible | ||
| 98 | 237234 | unwrapBothWithRefWrappers(candidateType, requestedType); | |
| 99 | |||
| 100 | // If the candidate does not contain any generic parts, we can simply check for type equality | ||
| 101 | 237234 | if !candidateType.hasAnyGenericParts() { | |
| 102 | // Check if the right one is a struct that implements the interface on the left | ||
| 103 | 164796 | if candidateType.matchesInterfaceImplementedByStruct(requestedType) { | |
| 104 | 9 | return true; | |
| 105 | } | ||
| 106 | // Normal equality check | ||
| 107 | 164787 | return candidateType.matches(requestedType, true, !strictQualifierMatching, true); | |
| 108 | } | ||
| 109 | |||
| 110 | // Check if the candidate type itself is generic | ||
| 111 | 72438 | if candidateType.isBase(SuperType::TY_GENERIC) { // The candidate type itself is generic | |
| 112 | 38287 | const QualType candidateBaseType = candidateType.getBase(); | |
| 113 | 38287 | const String& genericTypeName = candidateBaseType.getSubType(); | |
| 114 | |||
| 115 | // Check if we know the concrete type for that generic type name already | ||
| 116 | 38287 | if typeMapping.contains(genericTypeName) { // This is a known generic type | |
| 117 | 11028 | QualType knownConcreteType = typeMapping.get(genericTypeName); | |
| 118 | |||
| 119 | // Merge qualifiers of candidate type and known concrete type together | ||
| 120 | 11028 | knownConcreteType.qualifiers = knownConcreteType.qualifiers.merge(candidateType.qualifiers); | |
| 121 | |||
| 122 | // With the generic type known, a reference or pointer candidate (e.g. T&) can be checked like a non-generic one: it | ||
| 123 | // gives access to the requested value or pointee, so it has to be const for a const requested type | ||
| 124 | 11028 | if sharesValue && requestedTypeIn.qualifiers.isConst && !knownConcreteType.qualifiers.isConst { | |
| 125 | 3 | return false; | |
| 126 | } | ||
| 127 | |||
| 128 | // Remove reference wrapper of candidate type if required | ||
| 129 | 11025 | if !requestedType.isRef() { | |
| 130 | 10280 | knownConcreteType = knownConcreteType.removeReferenceWrapper(); | |
| 131 | 10280 | } | |
| 132 | |||
| 133 | 11025 | if requestedType.isRef() && !knownConcreteType.isRef() { | |
| 134 | 68 | const QualType containedType = requestedType.getContained(); | |
| 135 | 68 | requestedType = containedType.toNonConst(); | |
| 136 | 68 | } | |
| 137 | |||
| 138 | // Check if the known concrete type matches the requested type | ||
| 139 | 11025 | return knownConcreteType.matches(requestedType, true, !strictQualifierMatching, true); | |
| 140 | } else { // This is an unknown generic type | ||
| 141 | // Retrieve generic candidate type by its name | ||
| 142 | 27259 | const GenericType* genericCandidateBaseType = resolveGenericTypeByName(candidateTemplateTypes, genericTypeName, genericOnly); | |
| 143 | 27259 | assert genericCandidateBaseType != nil<const GenericType*>; | |
| 144 | |||
| 145 | // Check if the requested type fulfills all conditions of the generic candidate type | ||
| 146 | 27259 | QualType newBaseType = QualType(SuperType::TY_DYN); // Overwritten by checkConditionsOf | |
| 147 | 27259 | if !genericCandidateBaseType.checkConditionsOf(requestedType, newBaseType, true, !strictQualifierMatching) { | |
| 148 | 4329 | return false; | |
| 149 | } | ||
| 150 | // The generic type does not take over the constness, that the candidate adds itself (e.g. T = int for a const T& | ||
| 151 | // candidate and a const int) | ||
| 152 | 22930 | if candidateType.qualifiers.isConst { | |
| 153 | 2243 | newBaseType.makeConst(false); | |
| 154 | 2243 | } | |
| 155 | |||
| 156 | 22930 | QualType substantiatedCandidateType = candidateType.replaceBaseType(newBaseType); | |
| 157 | |||
| 158 | // Remove reference wrapper of candidate type if required | ||
| 159 | 22930 | if !requestedType.isRef() { | |
| 160 | 21982 | substantiatedCandidateType = substantiatedCandidateType.removeReferenceWrapper(); | |
| 161 | 21982 | } | |
| 162 | |||
| 163 | 22930 | if requestedType.isRef() && !substantiatedCandidateType.isRef() { | |
| 164 | 23 | const QualType containedType = requestedType.getContained(); | |
| 165 | 23 | requestedType = containedType.toNonConst(); | |
| 166 | 23 | } | |
| 167 | |||
| 168 | 22930 | if !substantiatedCandidateType.matches(requestedType, true, !strictQualifierMatching, true) { | |
| 169 | 1 | return false; | |
| 170 | } | ||
| 171 | |||
| 172 | // Zero out all qualifiers in the requested type, that are present in the candidate type | ||
| 173 | // This is to set all qualifiers that are not present in the candidate type to the generic type replacement | ||
| 174 | 22929 | requestedType.qualifiers.eraseWithMask(substantiatedCandidateType.qualifiers); | |
| 175 | |||
| 176 | // Add to type mapping | ||
| 177 | 22929 | const QualType newMappingType = requestedType.hasAnyGenericParts() ? candidateBaseType : newBaseType; | |
| 178 | 22929 | typeMapping.upsert(genericTypeName, newMappingType); | |
| 179 | |||
| 180 | 22929 | return true; // The type was successfully matched, by enriching the type mapping | |
| 181 | } | ||
| 182 | ✗ | } else { // The candidate type itself is non-generic, but one or several template or param types are | |
| 183 | // Check if supertype and subtype are equal | ||
| 184 | 34151 | if requestedType.getSuperType() != candidateType.getSuperType() { | |
| 185 | 14919 | return false; | |
| 186 | } | ||
| 187 | |||
| 188 | // If we have a function/procedure type, check the param and return types. Otherwise, check the template types | ||
| 189 | 19232 | const dyn fctOptions = [SuperType::TY_FUNCTION, SuperType::TY_PROCEDURE]; | |
| 190 | 19232 | if candidateType.isOneOf(fctOptions, len(fctOptions)) { | |
| 191 | // Check param and return types | ||
| 192 | 22 | const QualTypeList candidatePRTypes = candidateType.getFunctionParamAndReturnTypes(); | |
| 193 | 22 | const QualTypeList requestedPRTypes = requestedType.getFunctionParamAndReturnTypes(); | |
| 194 | 22 | if !matchRequestedToCandidateTypes(candidatePRTypes, requestedPRTypes, typeMapping, candidateTemplateTypes, genericOnly, strictQualifierMatching) { | |
| 195 | ✗ | return false; | |
| 196 | } | ||
| 197 | 22 | } else { | |
| 198 | 19210 | if requestedType.getSubType() != candidateType.getSubType() { | |
| 199 | 3018 | return false; | |
| 200 | } | ||
| 201 | 16192 | if requestedType.getBodyScope().parent != candidateType.getBodyScope().parent { | |
| 202 | ✗ | return false; | |
| 203 | } | ||
| 204 | |||
| 205 | // Check template types | ||
| 206 | 16192 | const QualTypeList candidateTTypes = candidateType.getTemplateTypes(); | |
| 207 | 16192 | const QualTypeList requestedTTypes = requestedType.getTemplateTypes(); | |
| 208 | 16192 | if !matchRequestedToCandidateTypes(candidateTTypes, requestedTTypes, typeMapping, candidateTemplateTypes, genericOnly, strictQualifierMatching) { | |
| 209 | ✗ | return false; | |
| 210 | } | ||
| 211 | 16192 | } | |
| 212 | |||
| 213 | 16214 | return true; // All requested template types match to their respective candidate template type -> successfully matched | |
| 214 | } | ||
| 215 | ✗ | } | |
| 216 | |||
| 217 | /** | ||
| 218 | * Substantiate a list of types with a type mapping in place. | ||
| 219 | * | ||
| 220 | * @param qualTypes Types to substantiate | ||
| 221 | * @param typeMapping Concrete template type mapping | ||
| 222 | * @param node AST node for error messages | ||
| 223 | */ | ||
| 224 | 4836 | public p substantiateTypesWithTypeMapping(QualTypeList& qualTypes, const TypeMapping& typeMapping, const ASTNode* node) { | |
| 225 | 5563 | foreach QualType& qualType : qualTypes { | |
| 226 | 727 | if qualType.hasAnyGenericParts() { | |
| 227 | 691 | substantiateTypeWithTypeMapping(qualType, typeMapping, node); | |
| 228 | 691 | } | |
| 229 | 727 | } | |
| 230 | 4836 | } | |
| 231 | |||
| 232 | /** | ||
| 233 | * Substantiate a single (possibly nested) generic type with a type mapping in place. | ||
| 234 | * | ||
| 235 | * @param type Type to substantiate | ||
| 236 | * @param typeMapping Concrete template type mapping | ||
| 237 | * @param node AST node for error messages | ||
| 238 | */ | ||
| 239 | 70037 | public p substantiateTypeWithTypeMapping(QualType& qualType, const TypeMapping& typeMapping, const ASTNode* node) { | |
| 240 | 70037 | assert qualType.hasAnyGenericParts(); | |
| 241 | 70037 | const QualType baseType = qualType.getBase(); | |
| 242 | |||
| 243 | // Check if the type itself is generic | ||
| 244 | 70037 | if baseType.is(SuperType::TY_GENERIC) { // The symbol type itself is generic | |
| 245 | 47507 | const String& genericTypeName = baseType.getSubType(); | |
| 246 | 47507 | assert typeMapping.contains(genericTypeName); | |
| 247 | 47507 | const QualType& replacementType = typeMapping.get(genericTypeName); | |
| 248 | 47507 | qualType = qualType.replaceBaseType(replacementType); | |
| 249 | 47507 | return; | |
| 250 | } | ||
| 251 | |||
| 252 | 22530 | const dyn fctOptions = [SuperType::TY_FUNCTION, SuperType::TY_PROCEDURE]; | |
| 253 | 22530 | if baseType.isOneOf(fctOptions, len(fctOptions)) { // The base type is a function or procedure | |
| 254 | // Substantiate each param or return type | ||
| 255 | 72 | QualTypeList paramAndReturnTypes = qualType.getFunctionParamAndReturnTypes(); | |
| 256 | 220 | foreach QualType& paramOrReturnType : paramAndReturnTypes { | |
| 257 | 148 | if paramOrReturnType.hasAnyGenericParts() { | |
| 258 | 79 | substantiateTypeWithTypeMapping(paramOrReturnType, typeMapping, node); | |
| 259 | 79 | } | |
| 260 | 148 | } | |
| 261 | // Attach the list of concrete param types to the symbol type | ||
| 262 | 72 | qualType = qualType.getWithFunctionParamAndReturnTypes(paramAndReturnTypes); | |
| 263 | 72 | return; | |
| 264 | 72 | } | |
| 265 | |||
| 266 | // The base type is a struct, interface or union | ||
| 267 | 22458 | assert baseType.is(SuperType::TY_STRUCT) || baseType.is(SuperType::TY_INTERFACE) || baseType.is(SuperType::TY_UNION); | |
| 268 | // Substantiate each template type | ||
| 269 | 22458 | QualTypeList templateTypes = baseType.getTemplateTypes(); | |
| 270 | 50343 | foreach QualType& templateType : templateTypes { | |
| 271 | 27885 | if templateType.hasAnyGenericParts() { | |
| 272 | 26577 | substantiateTypeWithTypeMapping(templateType, typeMapping, node); | |
| 273 | 26577 | } | |
| 274 | 27885 | } | |
| 275 | // Attach the list of concrete template types to the symbol type | ||
| 276 | 22458 | qualType = qualType.getWithBaseTemplateTypes(templateTypes); | |
| 277 | // Lookup the scope of the concrete struct or interface type | ||
| 278 | // Only do this, if the struct or interface is not self-referencing, because in that case we'd end up in an infinite recursion | ||
| 279 | 22458 | if !baseType.isSelfReferencingStructType(nil<const QualType*>) { | |
| 280 | 21381 | if baseType.is(SuperType::TY_STRUCT) { // Struct | |
| 281 | 19847 | Struct* spiceStruct = baseType.getStruct(node, templateTypes); | |
| 282 | 19847 | if spiceStruct == nil<Struct*> { | |
| 283 | ✗ | assert node != nil<ASTNode*>; | |
| 284 | ✗ | const String signature = getStructSignature(baseType.getSubType(), templateTypes); | |
| 285 | ✗ | throwSemanticError(node, SemanticErrorType::UNKNOWN_DATATYPE, "Could not find struct '" + signature + "'"); | |
| 286 | // The compilation is aborted after this stage. Until then, leave the type as is | ||
| 287 | ✗ | return; | |
| 288 | ✗ | } | |
| 289 | 19847 | qualType = qualType.getWithBodyScope(spiceStruct.scope); | |
| 290 | 21381 | } else if baseType.is(SuperType::TY_UNION) { // Union | |
| 291 | ✗ | Union* spiceUnion = baseType.getUnion(node, templateTypes); | |
| 292 | ✗ | if spiceUnion != nil<Union*> { | |
| 293 | ✗ | qualType = qualType.getWithBodyScope(spiceUnion.scope); | |
| 294 | ✗ | } | |
| 295 | ✗ | } else { // Interface | |
| 296 | 1534 | Interface* spiceInterface = baseType.getInterface(node, templateTypes); | |
| 297 | 1534 | if spiceInterface == nil<Interface*> { | |
| 298 | ✗ | assert node != nil<ASTNode*>; | |
| 299 | ✗ | const String signature = getStructSignature(baseType.getSubType(), templateTypes); | |
| 300 | ✗ | throwSemanticError(node, SemanticErrorType::UNKNOWN_DATATYPE, "Could not find interface '" + signature + "'"); | |
| 301 | // The compilation is aborted after this stage. Until then, leave the type as is | ||
| 302 | ✗ | return; | |
| 303 | ✗ | } | |
| 304 | 1534 | qualType = qualType.getWithBodyScope(spiceInterface.scope); | |
| 305 | 1534 | } | |
| 306 | 21381 | } | |
| 307 | 22458 | } | |
| 308 |