From 8daafcc2e4bf7b2dfb66d7a3b7ac60c86b2d926c Mon Sep 17 00:00:00 2001 From: Yong He Date: Tue, 9 Jan 2018 10:50:44 -0800 Subject: bruteforce implementation of witness table resolution for associated (#358) --- source/slang/check.cpp | 221 ++++++++++++++++++++++++------------------------- 1 file changed, 109 insertions(+), 112 deletions(-) (limited to 'source/slang/check.cpp') diff --git a/source/slang/check.cpp b/source/slang/check.cpp index ca9e0e7e5..77f9c8f44 100644 --- a/source/slang/check.cpp +++ b/source/slang/check.cpp @@ -153,6 +153,8 @@ namespace Slang RefPtr baseExpr, SourceLoc loc) { + if (declRef.As()) + getNewThisTypeSubst(declRef); if (baseExpr) { RefPtr expr; @@ -182,26 +184,18 @@ namespace Slang if (auto baseDeclRefExpr = baseExpr->As()) { baseThisTypeSubst = getThisTypeSubst(baseDeclRefExpr->declRef, false); - if (auto baseAssocType = baseDeclRefExpr->declRef.As()) - { - baseThisTypeSubst = new ThisTypeSubstitution(); - baseThisTypeSubst->sourceType = baseDeclRefExpr->type.type; - if (auto typetype = baseThisTypeSubst->sourceType.As()) - baseThisTypeSubst->sourceType = typetype->type; - } } - if (auto assocTypeDecl = declRef.As()) + if (declRef.As()) { - auto newThisTypeSubst = new ThisTypeSubstitution(); - if (baseThisTypeSubst) - newThisTypeSubst->sourceType = baseThisTypeSubst->sourceType; - expr->type = GetTypeForDeclRef(DeclRef(assocTypeDecl.getDecl(), newThisTypeSubst)); - auto declOutThisTypeSubst = getNewThisTypeSubst(*declRefOut); - if (baseThisTypeSubst) - declOutThisTypeSubst->sourceType = baseThisTypeSubst->sourceType; - return expr; + // if this is a reference to type constraint, insert a this-type substitution + RefPtr expType; + expType = baseExpr->type; + if (auto baseExprTT = baseExpr->type->As()) + expType = baseExprTT->type; + auto thisTypeSubst = getNewThisTypeSubst(*declRefOut); + thisTypeSubst->sourceType = expType; + baseThisTypeSubst = nullptr; } - // propagate "this-type" substitutions if (baseThisTypeSubst) { @@ -210,7 +204,7 @@ namespace Slang getNewThisTypeSubst(declRefExpr->declRef)->sourceType = baseThisTypeSubst->sourceType; } } - expr->type = GetTypeForDeclRef(declRef); + expr->type = GetTypeForDeclRef(*declRefOut); return expr; } else @@ -219,21 +213,6 @@ namespace Slang expr->loc = loc; expr->name = declRef.GetName(); expr->type = GetTypeForDeclRef(declRef); - if (auto exprDeclRefType = getExprDeclRefType(expr)) - { - if (auto genParmDecl = exprDeclRefType->declRef.As()) - { - // if this is a reference to generic type param, insert a this-type substitution - auto exprType = GetTypeForDeclRef(declRef); - auto thisSubst = new ThisTypeSubstitution(); - if (auto typetype = exprType.type.As()) - thisSubst->sourceType = typetype->type; - else - thisSubst->sourceType = exprType.type; - thisSubst->outer = declRef.substitutions; - declRef.substitutions = thisSubst; - } - } expr->declRef = declRef; return expr; } @@ -1614,27 +1593,27 @@ namespace Slang } bool doesSignatureMatchRequirement( - CallableDecl* /*memberDecl*/, - DeclRef requiredMemberDeclRef) + DeclRef memberDecl, + DeclRef requiredMemberDeclRef, + Dictionary, DeclRef> & requirementDict) { // TODO: actually implement matching here. For now we'll - // just pretend that things are satisfied in order to make progress. + // just pretend that things are satisfied in order to make progress.. + requirementDict.Add(requiredMemberDeclRef, DeclRef(memberDecl, nullptr)); return true; } bool doesGenericSignatureMatchRequirement( - GenericDecl * genDecl, - DeclRef requirementGenDecl) + DeclRef genDecl, + DeclRef requirementGenDecl, + Dictionary, DeclRef> & requirementDict) { - // TODO: genDecl should be a DeclRef to capture the environment generic variables needed to get - // a concrete type for a generic constraint super type (e.g. when this member belongs to a generic type) - - if (genDecl->Members.Count() != requirementGenDecl.getDecl()->Members.Count()) + if (genDecl.getDecl()->Members.Count() != requirementGenDecl.getDecl()->Members.Count()) return false; - for (UInt i = 0; i < genDecl->Members.Count(); i++) + for (UInt i = 0; i < genDecl.getDecl()->Members.Count(); i++) { - auto genMbr = genDecl->Members[i]; - auto requiredGenMbr = genDecl->Members[i]; + auto genMbr = genDecl.getDecl()->Members[i]; + auto requiredGenMbr = genDecl.getDecl()->Members[i]; if (auto genTypeMbr = genMbr.As()) { if (auto requiredGenTypeMbr = requiredGenMbr.As()) @@ -1647,7 +1626,8 @@ namespace Slang { if (auto requiredGenValMbr = requiredGenMbr.As()) { - return genValMbr->type->Equals(requiredGenValMbr->type); + if (!genValMbr->type->Equals(requiredGenValMbr->type)) + return false; } else return false; @@ -1665,16 +1645,18 @@ namespace Slang return false; } } - return doesMemberSatisfyRequirement(genDecl->inner.Ptr(), - DeclRef(requirementGenDecl.getDecl()->inner.Ptr(), requirementGenDecl.substitutions)); + return doesMemberSatisfyRequirement(DeclRef(genDecl.getDecl()->inner.Ptr(), genDecl.substitutions), + DeclRef(requirementGenDecl.getDecl()->inner.Ptr(), requirementGenDecl.substitutions), + requirementDict); } // Does the given `memberDecl` work as an implementation // to satisfy the requirement `requiredMemberDeclRef` // from an interface? bool doesMemberSatisfyRequirement( - Decl* memberDecl, - DeclRef requiredMemberDeclRef) + DeclRef memberDeclRef, + DeclRef requiredMemberDeclRef, + Dictionary, DeclRef> & requirementDictionary) { // At a high level, we want to chack that the // `memberDecl` and the `requiredMemberDeclRef` @@ -1694,74 +1676,85 @@ namespace Slang // An associated type requirement should be allowed // to be satisfied by any type declaration: // a typedef, a `struct`, etc. - - if (auto memberFuncDecl = dynamic_cast(memberDecl)) + auto checkSubTypeMember = [&](DeclRef subStructTypeDeclRef) -> bool + { + EnsureDecl(subStructTypeDeclRef.getDecl()); + // this is a sub type (e.g. nested struct declaration) in an aggregate type + // check if this sub type declaration satisfies the constraints defined by the associated type + if (auto requiredTypeDeclRef = requiredMemberDeclRef.As()) + { + bool conformance = true; + auto inheritanceReqDeclRefs = getMembersOfType(requiredTypeDeclRef); + for (auto inheritanceReqDeclRef : inheritanceReqDeclRefs) + { + auto interfaceDeclRefType = inheritanceReqDeclRef.getDecl()->base.type.As(); + SLANG_ASSERT(interfaceDeclRefType); + auto interfaceDeclRef = interfaceDeclRefType->declRef.As(); + SLANG_ASSERT(interfaceDeclRef); + RefPtr declRefType = new DeclRefType(); + declRefType->declRef = subStructTypeDeclRef; + auto witness = tryGetInterfaceConformanceWitness(declRefType, + interfaceDeclRef).As(); + if (witness) + requirementDictionary.Add(inheritanceReqDeclRef, witness->getLastStepDeclRef()); + else + conformance = false; + } + return conformance; + } + return false; + }; + if (auto memberFuncDecl = memberDeclRef.As()) { if (auto requiredFuncDeclRef = requiredMemberDeclRef.As()) { // Check signature match. return doesSignatureMatchRequirement( memberFuncDecl, - requiredFuncDeclRef); + requiredFuncDeclRef, + requirementDictionary); } } - else if (auto memberInitDecl = dynamic_cast(memberDecl)) + else if (auto memberInitDecl = memberDeclRef.As()) { if (auto requiredInitDecl = requiredMemberDeclRef.As()) { // Check signature match. return doesSignatureMatchRequirement( memberInitDecl, - requiredInitDecl); + requiredInitDecl, + requirementDictionary); } } - else if (auto genDecl = dynamic_cast(memberDecl)) + else if (auto genDecl = memberDeclRef.As()) { if (auto requiredGenDeclRef = requiredMemberDeclRef.As()) { - return doesGenericSignatureMatchRequirement(genDecl, requiredGenDeclRef); + return doesGenericSignatureMatchRequirement(genDecl, requiredGenDeclRef, requirementDictionary); } } - else if (auto subStructTypeDecl = dynamic_cast(memberDecl)) + else if (auto subStructTypeDeclRef = memberDeclRef.As()) { - // this is a sub type (e.g. nested struct declaration) in an aggregate type - // check if this sub type declaration satisfies the constraints defined by the associated type - if (auto requiredTypeDeclRef = requiredMemberDeclRef.As()) - { - bool conformance = true; - for (auto & inheritanceDecl : requiredTypeDeclRef.getDecl()->getMembersOfType()) - { - conformance = conformance && checkConformance(subStructTypeDecl, inheritanceDecl.Ptr()); - } - return conformance; - } + return checkSubTypeMember(subStructTypeDeclRef); } - else if (auto typedefDecl = dynamic_cast(memberDecl)) + else if (auto typedefDeclRef = memberDeclRef.As()) { // this is a type-def decl in an aggregate type // check if the specified type satisfies the constraints defined by the associated type - if (auto requiredTypeDecl = requiredMemberDeclRef.As()) + if (auto requiredTypeDeclRef = requiredMemberDeclRef.As()) { - auto constraintList = requiredTypeDecl.getDecl()->getMembersOfType(); + auto constraintList = getMembersOfType(requiredTypeDeclRef); if (constraintList.Count()) { - auto declRefType = typedefDecl->type->AsDeclRefType(); + auto declRefType = GetType(typedefDeclRef)->GetCanonicalType()->As(); if (!declRefType) return false; - auto structTypeDecl = declRefType->declRef.getDecl()->As(); - if (!structTypeDecl) + auto structTypeDeclRef = declRefType->declRef.As(); + if (!structTypeDeclRef) return false; - //TODO: What do we do if type is a generic specialization? - // i.e. if the struct defines typedef Generic T; - // how to check if T satisfies the associatedtype constraints? - // the code below will only work when T is defined to be a simple aggregated type (no generics). - bool conformance = true; - for (auto & inheritanceDecl : constraintList) - { - conformance = conformance && checkConformance(structTypeDecl, inheritanceDecl.Ptr()); - } - return conformance; + + return checkSubTypeMember(structTypeDeclRef); } return true; } @@ -1779,10 +1772,11 @@ namespace Slang // `requiredMemberDeclRef` is a required member of // the interface. RefPtr findWitnessForInterfaceRequirement( - AggTypeDecl* typeDecl, + DeclRef typeDeclRef, InheritanceDecl* inheritanceDecl, DeclRef interfaceDeclRef, - DeclRef requiredMemberDeclRef) + DeclRef requiredMemberDeclRef, + Dictionary, DeclRef> & requirementWitness) { // We will look up members with the same name, // since only same-name members will be able to @@ -1816,14 +1810,14 @@ namespace Slang // now, so we won't worry about this. // Make sure that by-name lookup is possible. - buildMemberDictionary(typeDecl); + buildMemberDictionary(typeDeclRef.getDecl()); Decl* firstMemberOfName = nullptr; - typeDecl->memberDictionary.TryGetValue(name, firstMemberOfName); + typeDeclRef.getDecl()->memberDictionary.TryGetValue(name, firstMemberOfName); if (!firstMemberOfName) { - getSink()->diagnose(inheritanceDecl, Diagnostics::typeDoesntImplementInterfaceRequirement, typeDecl, requiredMemberDeclRef); + getSink()->diagnose(inheritanceDecl, Diagnostics::typeDoesntImplementInterfaceRequirement, typeDeclRef, requiredMemberDeclRef); return nullptr; } @@ -1831,7 +1825,7 @@ namespace Slang // the expected signature for the requirement. for (auto memberDecl = firstMemberOfName; memberDecl; memberDecl = memberDecl->nextInContainerWithSameName) { - if (doesMemberSatisfyRequirement(memberDecl, requiredMemberDeclRef)) + if (doesMemberSatisfyRequirement(DeclRef(memberDecl, typeDeclRef.substitutions), requiredMemberDeclRef, requirementWitness)) return memberDecl; } @@ -1842,7 +1836,7 @@ namespace Slang // of "candidates" for satisfaction of the requirement, // and if nothing is found we print the candidates - getSink()->diagnose(inheritanceDecl, Diagnostics::typeDoesntImplementInterfaceRequirement, typeDecl, requiredMemberDeclRef); + getSink()->diagnose(inheritanceDecl, Diagnostics::typeDoesntImplementInterfaceRequirement, typeDeclRef, requiredMemberDeclRef); return nullptr; } @@ -1851,7 +1845,7 @@ namespace Slang // (via the given `inheritanceDecl`) actually provides // members to satisfy all the requirements in the interface. bool checkInterfaceConformance( - AggTypeDecl* typeDecl, + DeclRef typeDeclRef, InheritanceDecl* inheritanceDecl, DeclRef interfaceDeclRef) { @@ -1884,7 +1878,7 @@ namespace Slang // // TODO: we *really* need a linearization step here!!!! result = result && checkConformanceToType( - typeDecl, + typeDeclRef, inheritanceDecl, getBaseType(requiredInheritanceDeclRef)); continue; @@ -1892,30 +1886,26 @@ namespace Slang // Look for a member in the type that can satisfy the // interface requirement. - auto conformanceWitness = findWitnessForInterfaceRequirement( - typeDecl, + auto isConformanceSatisfied = findWitnessForInterfaceRequirement( + typeDeclRef, inheritanceDecl, interfaceDeclRef, - requiredMemberDeclRef); + requiredMemberDeclRef, + inheritanceDecl->requirementWitnesses); - if (!conformanceWitness) + if (!isConformanceSatisfied) { result = false; continue; } - - // Store that witness into a table stored on the `inheritnaceDecl` - // so that it can be used for downstream code generation. - - inheritanceDecl->requirementWitnesses.Add(requiredMemberDeclRef, conformanceWitness); } return result; } bool checkConformanceToType( - AggTypeDecl* typeDecl, - InheritanceDecl* inheritanceDecl, - Type* baseType) + DeclRef typeDeclRef, + InheritanceDecl* inheritanceDecl, + Type* baseType) { if (auto baseDeclRefType = baseType->As()) { @@ -1926,7 +1916,7 @@ namespace Slang // We need to check that it provides all of the members // required by that interface. return checkInterfaceConformance( - typeDecl, + typeDeclRef, inheritanceDecl, baseInterfaceDeclRef); } @@ -1941,13 +1931,20 @@ namespace Slang // `inheritanceDecl` actually does what it needs to // for that inheritance to be valid. bool checkConformance( - AggTypeDecl* typeDecl, - InheritanceDecl* inheritanceDecl) + DeclRef typeDecl, + InheritanceDecl* inheritanceDecl) { // Look at the type being inherited from, and validate // appropriately. auto baseType = inheritanceDecl->base.type; - return checkConformanceToType(typeDecl, inheritanceDecl, baseType); + return checkConformanceToType(typeDecl, inheritanceDecl, baseType.As()); + } + + bool checkConformance( + AggTypeDecl* typeDecl, + InheritanceDecl* inheritanceDecl) + { + return checkConformance(DeclRef(typeDecl, nullptr), inheritanceDecl); } void visitAggTypeDecl(AggTypeDecl* decl) @@ -5095,7 +5092,7 @@ namespace Slang RefPtr snd) { // They must both be NULL or non-NULL - if (!fst || !snd) + if (!hasGenericSubstitutions(fst) || !hasGenericSubstitutions(snd)) return fst == snd; auto fstGen = fst.As(); auto sndGen = snd.As(); @@ -6927,7 +6924,7 @@ namespace Slang auto type = getFuncType(session, funcDeclRef); return QualType(type); } - else if (auto constraintDeclRef = declRef.As()) + else if (auto constraintDeclRef = declRef.As()) { // When we access a constraint or an inheritance decl (as a member), // we are conceptually performing a "cast" to the given super-type, -- cgit v1.2.3