diff options
Diffstat (limited to 'source')
26 files changed, 2114 insertions, 854 deletions
diff --git a/source/core/slang-hash.h b/source/core/slang-hash.h index 248d11303..8c4fbac42 100644 --- a/source/core/slang-hash.h +++ b/source/core/slang-hash.h @@ -177,6 +177,15 @@ namespace Slang return h; } + inline HashCode combineHash(HashCode hash0, HashCode hash1, HashCode hash2, HashCode hash3) + { + auto h = hash0; + h = combineHash(h, hash1); + h = combineHash(h, hash2); + h = combineHash(h, hash3); + return h; + } + struct Hasher { public: diff --git a/source/core/slang-memory-arena.h b/source/core/slang-memory-arena.h index 75f3faac3..4d2372e44 100644 --- a/source/core/slang-memory-arena.h +++ b/source/core/slang-memory-arena.h @@ -440,4 +440,15 @@ SLANG_FORCE_INLINE void MemoryArena::rewindToCursor(const void* cursor) } // namespace Slang +SLANG_FORCE_INLINE void* operator new(size_t size, Slang::MemoryArena& arena) +{ + return arena.allocate(size); +} + +SLANG_FORCE_INLINE void operator delete(void* memory, Slang::MemoryArena& arena) +{ + SLANG_UNUSED(memory); + SLANG_UNUSED(arena); +} + #endif // SLANG_MEMORY_ARENA_H diff --git a/source/slang/slang-ast-base.h b/source/slang/slang-ast-base.h index 5319dca7e..f52b7fcff 100644 --- a/source/slang/slang-ast-base.h +++ b/source/slang/slang-ast-base.h @@ -415,7 +415,7 @@ private: // The underlying declaration Decl* decl = nullptr; // Optionally, a chain of substitutions to perform - Substitutions* substitutions; + Substitutions* substitutions = nullptr; }; diff --git a/source/slang/slang-ast-builder.cpp b/source/slang/slang-ast-builder.cpp index e6e1b5e75..7f1b90837 100644 --- a/source/slang/slang-ast-builder.cpp +++ b/source/slang/slang-ast-builder.cpp @@ -338,7 +338,7 @@ DifferentialPairType* ASTBuilder::getDifferentialPairType( return as<DifferentialPairType>(rsType); } -DeclRef<InterfaceDecl> ASTBuilder::getDifferentiableInterface() +DeclRef<InterfaceDecl> ASTBuilder::getDifferentiableInterfaceDecl() { DeclRef<InterfaceDecl> declRef = DeclRef<InterfaceDecl>(getBuiltinDeclRef("DifferentiableType", nullptr)); return declRef; @@ -378,6 +378,11 @@ MeshOutputType* ASTBuilder::getMeshOutputTypeFromModifier( return as<MeshOutputType>(rsType); } +Type* ASTBuilder::getDifferentiableInterfaceType() +{ + return DeclRefType::create(this, getDifferentiableInterfaceDecl()); +} + DeclRef<Decl> ASTBuilder::getBuiltinDeclRef(const char* builtinMagicTypeName, Val* genericArg) { auto decl = m_sharedASTBuilder->findMagicDecl(builtinMagicTypeName); @@ -443,6 +448,235 @@ TypeType* ASTBuilder::getTypeType(Type* type) return getOrCreate<TypeType>(type); } +TypeEqualityWitness* ASTBuilder::getTypeEqualityWitness( + Type* type) +{ + return getOrCreate<TypeEqualityWitness>(type); +} + + +SubtypeWitness* ASTBuilder::getDeclaredSubtypeWitness( + Type* subType, + Type* superType, + DeclRef<Decl> const& declRef) +{ + auto witness = getOrCreate<DeclaredSubtypeWitness>( + subType, superType, declRef.declRefBase); + return witness; +} + +SubtypeWitness* ASTBuilder::getTransitiveSubtypeWitness( + SubtypeWitness* aIsSubtypeOfBWitness, + SubtypeWitness* bIsSubtypeOfCWitness) +{ +top: + // Our job is to take the witnesses that `a <: b` and `b <: c` + // and produce a valid witness that `a <: c` + // + // There are some special cases we want to handle, in order + // to simplify logic elesewhere in the compiler. For example, + // if either of the input witnesses is a type *equality* witness, + // then the other witness can be returned as-is. + // + // If `a == b`, then the `b <: c` witness is also a witness of `a <: c`. + // + if(as<TypeEqualityWitness>(aIsSubtypeOfBWitness)) + { + return bIsSubtypeOfCWitness; + } + + // Similarly, if `b == c`, then the `a <: b` witness is a witness for `a <: c` + // + if (as<TypeEqualityWitness>(bIsSubtypeOfCWitness)) + { + return aIsSubtypeOfBWitness; + } + + // HACK: There is downstream code generation logic that assumes that + // a `TransitiveSubtypeWitness` will never have a transitive witness + // as its `b <: c` witness. If we are at risk of creating such a witness here, + // we will shift things around to make that not be the case: + // + if (auto bIsTransitiveSubtypeOfCWitness = as<TransitiveSubtypeWitness>(bIsSubtypeOfCWitness)) + { + // Let's call the intermediate type here `x`, we know that the `b <: c` + // witness is based on witnesses that `b <: x` and `x <: c`: + // + auto bIsSubtypeOfXWitness = bIsTransitiveSubtypeOfCWitness->subToMid; + auto xIsSubtypeOfCWitness = bIsTransitiveSubtypeOfCWitness->midToSup; + + // We can recursively call this operation to produce a witness that + // `a <: x`, based on the witnesses we already have for `a <: b` and `b <: x`: + // + auto aIsSubtypeOfXWitness = getTransitiveSubtypeWitness( + aIsSubtypeOfBWitness, + bIsSubtypeOfXWitness); + + // Now we can perform a "tail recursive" call to this function (via `goto` + // to combine the `a <: x` witness with our `x <: c` witness: + // + aIsSubtypeOfBWitness = aIsSubtypeOfXWitness; + bIsSubtypeOfCWitness = xIsSubtypeOfCWitness; + goto top; + } + + auto aType = aIsSubtypeOfBWitness->sub; + auto cType = bIsSubtypeOfCWitness->sup; + + // If the right-hand side is a conjunction witness for `B <: C` + // of the form `(B <: X)&(B <: Y)`, then we have it that `C = X&Y` + // and we'd rather form a conjunction witness for `A <: C` + // that is of the form `(A <: X)&(A <: Y)`. + // + if(auto bIsSubtypeOfXAndY = as<ConjunctionSubtypeWitness>(bIsSubtypeOfCWitness)) + { + auto bIsSubtypeOfXWitness = bIsSubtypeOfXAndY->getLeftWitness(); + auto bIsSubtypeOfYWitness = bIsSubtypeOfXAndY->getRightWitness(); + + return getConjunctionSubtypeWitness( + aType, + cType, + getTransitiveSubtypeWitness(aIsSubtypeOfBWitness, bIsSubtypeOfXWitness), + getTransitiveSubtypeWitness(aIsSubtypeOfBWitness, bIsSubtypeOfYWitness)); + } + + // If the right-hand witness `R` is of the form `extract(i, W)`, then + // `W` is a witness that `B <: X&Y&...` for some conjunction, where `C` + // is one component of that conjunction. + // + if(auto bIsSubtypeViaExtraction = as<ExtractFromConjunctionSubtypeWitness>(bIsSubtypeOfCWitness)) + { + // We decompose the witness `extract(i, W)` to get both + // the witness `W` that `B <: X&Y&...` as well as the index + // `i` of `C` within the conjunction. + // + auto bIsSubtypeOfConjunction = bIsSubtypeViaExtraction->conjunctionWitness; + auto indexOfCInConjunction = bIsSubtypeViaExtraction->indexInConjunction; + + // We lift the extraction to the outside of the composition, by + // forming a witness for `A <: C` that is of the form + // `extract(i, L . W )`, where `L` is the left-hand witnes (for `A <: B`). + // The composition `L . W` is a witness that `A <: X&Y&...`, and + // the `i`th component of it should be a witness that `A <: C`. + // + return getExtractFromConjunctionSubtypeWitness( + aType, + cType, + getTransitiveSubtypeWitness(aIsSubtypeOfBWitness, bIsSubtypeOfConjunction), + indexOfCInConjunction); + } + + // If none of the above special cases applied, then we are just going to create + // a `TransitiveSubtypeWitness` directly. + // + // TODO: Identify other cases that we can potentially simplify. + // It is particularly notable that we do not have simplification rules that + // detect when the left-hand side of a composition has some particular + // structure. This may be fine, or it may not; we should write down a more + // formal set of rules for the allowed structure of our witnesses to + // guarantee that our simplifications are sufficient. + + TransitiveSubtypeWitness* transitiveWitness = getOrCreateWithDefaultCtor<TransitiveSubtypeWitness>( + aType, + cType, + aIsSubtypeOfBWitness, + bIsSubtypeOfCWitness); + transitiveWitness->sub = aType; + transitiveWitness->sup = cType; + transitiveWitness->subToMid = aIsSubtypeOfBWitness; + transitiveWitness->midToSup = bIsSubtypeOfCWitness; + + return transitiveWitness; +} + +SubtypeWitness* ASTBuilder::getExtractFromConjunctionSubtypeWitness( + Type* subType, + Type* superType, + SubtypeWitness* conjunctionWitness, + int indexOfSuperTypeInConjunction) +{ + // We are taking a witness `W` for `S <: L&R` and + // using it to produce a witness for `S <: L` + // or `S <: R`. + + // If it turns out that the witness `W` is itself + // formed as a conjuction of witnesses: `(S <: L) & (S <: R)`, + // then we can simply re-use the appropriate sub-witness. + // + if (auto conjWitness = as<ConjunctionSubtypeWitness>(conjunctionWitness)) + { + return conjWitness->getComponentWitness(indexOfSuperTypeInConjunction); + } + + // TODO: Are there other simplification cases we should be paying attention + // to here? For example: + // + // * What if the original witness is transitive? + + auto witness = getOrCreateWithDefaultCtor<ExtractFromConjunctionSubtypeWitness>( + subType, + superType, + conjunctionWitness, + indexOfSuperTypeInConjunction); + + witness->sub = subType; + witness->sup = superType; + witness->conjunctionWitness = conjunctionWitness; + witness->indexInConjunction = indexOfSuperTypeInConjunction; + return witness; +} + +SubtypeWitness* ASTBuilder::getConjunctionSubtypeWitness( + Type* sub, + Type* lAndR, + SubtypeWitness* subIsLWitness, + SubtypeWitness* subIsRWitness) +{ + // If a conjunction witness for `S <: L&R` is being formed, + // where the constituent witnesses for `S <: L` and `S <: R` + // are themselves extractions of the first and second + // components, respectively, of a single witness `W`, then + // we can simply use `W` as-is. + // + auto lExtract = as<ExtractFromConjunctionSubtypeWitness>(subIsLWitness); + auto rExtract = as<ExtractFromConjunctionSubtypeWitness>(subIsRWitness); + if(lExtract && rExtract) + { + if (lExtract->indexInConjunction == 0 + && rExtract->indexInConjunction == 1) + { + auto lInner = lExtract->conjunctionWitness; + auto rInner = rExtract->conjunctionWitness; + if (lInner == rInner) + { + return lInner; + } + } + } + + // TODO: Depending on how we decide our canonicalized witnesses + // should be structured, we could detect the case where the + // `S <: L` and `S <: R` witnesses are both transitive compositions + // of the form `X . A` and `X . B`, such that we *could* form + // a composition around a conjunction - that is, produce + // `X . (A & B)` rather than `(X . A) & (X . B)`. + // + // For now we are favoring putting the composition (transitive + // witness) deeper, so that we have more chances to expose a + // conjunction witness at higher levels. + + auto witness = getOrCreateWithDefaultCtor<ConjunctionSubtypeWitness>( + sub, + lAndR, + subIsLWitness, + subIsRWitness); + witness->componentWitnesses[0] = subIsLWitness; + witness->componentWitnesses[1] = subIsRWitness; + witness->sub = sub; + witness->sup = lAndR; + return witness; +} + bool ASTBuilder::NodeDesc::operator==(NodeDesc const& that) const { if (hashCode != that.hashCode) return false; diff --git a/source/slang/slang-ast-builder.h b/source/slang/slang-ast-builder.h index a2543ab1e..9aa3a2f8e 100644 --- a/source/slang/slang-ast-builder.h +++ b/source/slang/slang-ast-builder.h @@ -195,6 +195,7 @@ public: }; }; + MemoryArena& getArena() { return m_arena; } /// Create AST types template <typename T> @@ -399,7 +400,8 @@ public: Type* valueType, Witness* primalIsDifferentialWitness); - DeclRef<InterfaceDecl> getDifferentiableInterface(); + DeclRef<InterfaceDecl> getDifferentiableInterfaceDecl(); + Type* getDifferentiableInterfaceType(); Decl* getDifferentiableAssociatedTypeRequirement(); bool isDifferentiableInterfaceAvailable(); @@ -428,6 +430,34 @@ public: TypeType* getTypeType(Type* type); + /// Produce a witness that `T : T` for any type `T` + TypeEqualityWitness* getTypeEqualityWitness( + Type* type); + + SubtypeWitness* getDeclaredSubtypeWitness( + Type* subType, + Type* superType, + DeclRef<Decl> const& declRef); + + /// Produce a witness that `A <: C` given witnesses that `A <: B` and `B <: C` + SubtypeWitness* getTransitiveSubtypeWitness( + SubtypeWitness* aIsSubtypeOfBWitness, + SubtypeWitness* bIsSubtypeOfCWitness); + + /// Produce a witness that `T <: L` or `T <: R` given `T <: L&R` + SubtypeWitness* getExtractFromConjunctionSubtypeWitness( + Type* subType, + Type* superType, + SubtypeWitness* subIsSubtypeOfConjunction, + int indexOfSuperTypeInConjunction); + + /// Produce a witnes that `S <: L&R` given witnesses that `S <: L` and `S <: R` + SubtypeWitness* getConjunctionSubtypeWitness( + Type* sub, + Type* lAndR, + SubtypeWitness* subIsLWitness, + SubtypeWitness* subIsRWitness); + /// Helpers to get type info from the SharedASTBuilder const ReflectClassInfo* findClassInfo(const UnownedStringSlice& slice) { return m_sharedASTBuilder->findClassInfo(slice); } SyntaxClass<NodeBase> findSyntaxClass(const UnownedStringSlice& slice) { return m_sharedASTBuilder->findSyntaxClass(slice); } diff --git a/source/slang/slang-ast-decl.h b/source/slang/slang-ast-decl.h index 93e5a19ad..61e623366 100644 --- a/source/slang/slang-ast-decl.h +++ b/source/slang/slang-ast-decl.h @@ -100,14 +100,14 @@ class LetDecl : public VarDecl SLANG_AST_CLASS(LetDecl) }; -// An `AggTypeDeclBase` captures the shared functionality -// between true aggregate type declarations and extension -// declarations: -// -// - Both can container members (they are `ContainerDecl`s) -// - Both can have declared bases -// - Both expose a `this` variable in their body -// + // An `AggTypeDeclBase` captures the shared functionality + // between true aggregate type declarations and extension + // declarations: + // + // - Both can contain members (they are `ContainerDecl`s) + // - Both can have declared bases + // - Both expose a `this` variable in their body + // class AggTypeDeclBase : public ContainerDecl { SLANG_ABSTRACT_AST_CLASS(AggTypeDeclBase); diff --git a/source/slang/slang-ast-support-types.h b/source/slang/slang-ast-support-types.h index 19f3f42d4..9ae253547 100644 --- a/source/slang/slang-ast-support-types.h +++ b/source/slang/slang-ast-support-types.h @@ -753,7 +753,7 @@ namespace Slang Val* _tryLookupConcreteAssociatedTypeFromThisTypeSubst(ASTBuilder* builder, DeclRef<Decl> declRef); void _printNestedDecl(const Substitutions* substitutions, const Decl* decl, StringBuilder& out); - template<typename T> + template<typename T = Decl> struct DeclRef { friend class ASTBuilder; @@ -773,12 +773,10 @@ namespace Slang init(base); } - template <typename U> - DeclRef(DeclRef<U> const& other, - typename EnableIf<IsConvertible<T*, U*>::Value, void>::type* = 0) + template <typename U, typename = typename EnableIf<IsConvertible<T*, U*>::Value, void>::type> + DeclRef(DeclRef<U> const& other) : declRefBase(other.declRefBase) - { - } + {} T* getDecl() const; Substitutions* getSubst() const; diff --git a/source/slang/slang-ast-type.cpp b/source/slang/slang-ast-type.cpp index b24e0eb8e..9b6b439ce 100644 --- a/source/slang/slang-ast-type.cpp +++ b/source/slang/slang-ast-type.cpp @@ -1063,8 +1063,6 @@ HashCode AndType::_getHashCodeOverride() Type* AndType::_createCanonicalTypeOverride() { - AndType* canType = m_astBuilder->create<AndType>(); - // TODO: proper canonicalization of an `&` type relies on // several different things: // @@ -1097,9 +1095,10 @@ Type* AndType::_createCanonicalTypeOverride() // We are going to completely ignore these issues for // right now, in the name of getting something up and running. // - canType->left = left->getCanonicalType(); - canType->right = right->getCanonicalType(); + auto canLeft = left->getCanonicalType(); + auto canRight = right->getCanonicalType(); + auto canType = m_astBuilder->getAndType(canLeft, canRight); return canType; } @@ -1115,9 +1114,7 @@ Val* AndType::_substituteImplOverride(ASTBuilder* astBuilder, SubstitutionSet su (*ioDiff)++; - AndType* substType = m_astBuilder->create<AndType>(); - substType->left = substLeft; - substType->right = substRight; + auto substType = m_astBuilder->getAndType(substLeft, substRight); return substType; } diff --git a/source/slang/slang-ast-val.cpp b/source/slang/slang-ast-val.cpp index 6850fdbfc..37912bac2 100644 --- a/source/slang/slang-ast-val.cpp +++ b/source/slang/slang-ast-val.cpp @@ -348,11 +348,8 @@ Val* DeclaredSubtypeWitness::_substituteImplOverride(ASTBuilder* astBuilder, Sub } } - DeclaredSubtypeWitness* rs = astBuilder->getOrCreate<DeclaredSubtypeWitness>( - substSub, substSup, astBuilder->getSpecializedDeclRef(substDeclRef.getDecl(), substDeclRef.getSubst())); - rs->sub = substSub; - rs->sup = substSup; - rs->declRef = substDeclRef; + auto rs = astBuilder->getDeclaredSubtypeWitness( + substSub, substSup, substDeclRef); return rs; } @@ -384,8 +381,6 @@ Val* TransitiveSubtypeWitness::_substituteImplOverride(ASTBuilder* astBuilder, S { int diff = 0; - Type* substSub = as<Type>(sub->substituteImpl(astBuilder, subst, &diff)); - Type* substSup = as<Type>(sup->substituteImpl(astBuilder, subst, &diff)); SubtypeWitness* substSubToMid = as<SubtypeWitness>(subToMid->substituteImpl(astBuilder, subst, &diff)); SubtypeWitness* substMidToSup = as<SubtypeWitness>(midToSup->substituteImpl(astBuilder, subst, &diff)); @@ -396,29 +391,14 @@ Val* TransitiveSubtypeWitness::_substituteImplOverride(ASTBuilder* astBuilder, S // Something changes, so let the caller know. (*ioDiff)++; - // TODO: are there cases where we can simplify? + // If it possible that substitution could have led to either of the + // constituent witnesses being simplified, and such simplification could + // (in principle) lead to opportunities to simplify this transitive witness. + // As such, we do not simply create a fresh `TransitiveSubtypeWitness` here, + // and instead go through a bottleneck routine in the `ASTBuilder` that will + // detect and handle any possible simplifications. // - // In principle, if either `subToMid` or `midToSub` turns into - // a reflexive subtype witness, then we could drop that side, - // and just return the other one (this would imply that `sub == mid` - // or `mid == sup` after substitutions). - // - // In the long run, is it also possible that if `sub` gets resolved - // to a concrete type *and* we decide to flatten out the inheritance - // graph into a linearized "class precedence list" stored in any - // aggregate type, then we could potentially just redirect to point - // to the appropriate inheritance decl in the original type. - // - // For now I'm going to ignore those possibilities and hope for the best. - - // In the simple case, we just construct a new transitive subtype - // witness, and we move on with life. - TransitiveSubtypeWitness* result = astBuilder->create<TransitiveSubtypeWitness>(); - result->sub = substSub; - result->sup = substSup; - result->subToMid = substSubToMid; - result->midToSup = substMidToSup; - return result; + return astBuilder->getTransitiveSubtypeWitness(substSubToMid, substMidToSup); } void TransitiveSubtypeWitness::_toTextOverride(StringBuilder& out) @@ -445,9 +425,9 @@ Val* ExtractFromConjunctionSubtypeWitness::_substituteImplOverride(ASTBuilder* a { int diff = 0; - Type* substSub = as<Type>(sub->substituteImpl(astBuilder, subst, &diff)); - Type* substSup = as<Type>(sup->substituteImpl(astBuilder, subst, &diff)); - SubtypeWitness* substWitness = as<SubtypeWitness>(conjunctionWitness->substituteImpl(astBuilder, subst, &diff)); + auto substSub = as<Type>(sub->substituteImpl(astBuilder, subst, &diff)); + auto substSup = as<Type>(sup->substituteImpl(astBuilder, subst, &diff)); + auto substWitness = as<SubtypeWitness>(conjunctionWitness->substituteImpl(astBuilder, subst, &diff)); // If nothing changed, then we can bail out early. if (!diff) @@ -456,47 +436,18 @@ Val* ExtractFromConjunctionSubtypeWitness::_substituteImplOverride(ASTBuilder* a // Something changes, so let the caller know. (*ioDiff)++; - // If the substituted witness is a conjunction, break it apart, but it's important to replace the - // sub and super types with the current ones since the conjunction witness will have an - // - if (auto substConjunctionWitness = as<ConjunctionSubtypeWitness>(substWitness)) - { - if (indexInConjunction == 0) - { - auto witness = as<SubtypeWitness>(substConjunctionWitness->leftWitness); - SLANG_ASSERT(witness); - - witness->sub = substSub; - witness->sup = substSup; - - return witness; - } - else if (indexInConjunction == 1) - { - auto witness = as<SubtypeWitness>(substConjunctionWitness->rightWitness); - SLANG_ASSERT(witness); - - witness->sub = substSub; - witness->sup = substSup; - - return witness; - } - else - { - SLANG_UNIMPLEMENTED_X("conjunction index must be 0 or 1"); - } - } - else - { - // In the simple case, we just construct a new conjunction subtype - // witness. - ExtractFromConjunctionSubtypeWitness* result = astBuilder->create<ExtractFromConjunctionSubtypeWitness>(); - result->sub = substSub; - result->sup = substSup; - result->conjunctionWitness = substWitness; - result->indexInConjunction = indexInConjunction; - return result; - } + // Substitution into the constituent pieces of this witness could + // have created opportunities for simplification. For example, + // the `substWitness` might be a `ConjunctionSubtypeWitness`, + // such that we could directly use one of its components in + // place of the extraction. + // + // We use the factory function on the AST builder to create + // the result witness, so that it can perform all of the + // simplification logic as needed. + // + return astBuilder->getExtractFromConjunctionSubtypeWitness( + substSub, substSup, substWitness, indexInConjunction); } // !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! ExtractExistentialSubtypeWitness !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! @@ -595,10 +546,11 @@ Val* TaggedUnionSubtypeWitness::_substituteImplOverride(ASTBuilder* astBuilder, auto substSub = as<Type>(sub->substituteImpl(astBuilder, subst, &diff)); auto substSup = as<Type>(sup->substituteImpl(astBuilder, subst, &diff)); - List<Val*> substCaseWitnesses; + List<SubtypeWitness*> substCaseWitnesses; for (auto caseWitness : caseWitnesses) { - substCaseWitnesses.add(caseWitness->substituteImpl(astBuilder, subst, &diff)); + substCaseWitnesses.add( + as<SubtypeWitness>(caseWitness->substituteImpl(astBuilder, subst, &diff))); } if (!diff) @@ -615,65 +567,83 @@ Val* TaggedUnionSubtypeWitness::_substituteImplOverride(ASTBuilder* astBuilder, bool ConjunctionSubtypeWitness::_equalsValOverride(Val* val) { - if (auto other = as<ConjunctionSubtypeWitness>(val)) + auto other = as<ConjunctionSubtypeWitness>(val); + if (!other) + return false; + + for (Index i = 0; i < kComponentCount; ++i) { - return other->leftWitness && other->leftWitness->equalsVal(leftWitness) && - other->rightWitness && other->rightWitness->equalsVal(rightWitness); + if (!other->componentWitnesses[i]) return false; + if (!other->componentWitnesses[i]->equalsVal(componentWitnesses[i])) return false; } - return false; + return true; } void ConjunctionSubtypeWitness::_toTextOverride(StringBuilder& out) { out << "ConjunctionSubtypeWitness("; - if (leftWitness) out << leftWitness; - out << ","; - if (rightWitness) out << rightWitness; + for (Index i = 0; i < kComponentCount; ++i) + { + if (i != 0) out << ","; + + auto w = componentWitnesses[i]; + if (w) out << w; + } out << ")"; } HashCode ConjunctionSubtypeWitness::_getHashCodeOverride() { HashCode result = 0; - if (leftWitness) result = leftWitness->getHashCode(); - if (rightWitness) result = combineHash(result, rightWitness->getHashCode()); + for (Index i = 0; i < kComponentCount; ++i) + { + auto w = componentWitnesses[i]; + if (w) result = combineHash(result, w->getHashCode()); + } return result; } Val* ConjunctionSubtypeWitness::_substituteImplOverride(ASTBuilder* astBuilder, SubstitutionSet subst, int* ioDiff) { int diff = 0; - Val* left = nullptr; - Val* right = nullptr; + Val* substComponentWitnesses[kComponentCount]; auto substSub = as<Type>(sub->substituteImpl(astBuilder, subst, &diff)); auto substSup = as<Type>(sup->substituteImpl(astBuilder, subst, &diff)); - if (leftWitness) - left = leftWitness->substituteImpl(astBuilder, subst, &diff); - if (rightWitness) - right = rightWitness->substituteImpl(astBuilder, subst, &diff); + for (Index i = 0; i < kComponentCount; ++i) + { + auto w = componentWitnesses[i]; + substComponentWitnesses[i] = w ? w->substituteImpl(astBuilder, subst, &diff) : nullptr; + } + + if(!diff) + return this; *ioDiff += diff; - if (diff) - { - auto result = astBuilder->create<ConjunctionSubtypeWitness>(); - result->leftWitness = left; - result->rightWitness = right; - result->sub = substSub; - result->sup = substSup; - return result; - } - return this; + // We use the factory function on the AST builder rather than + // directly construct a new `ConjunctionSubtypeWitness`, because + // the substitution process might have created further opportunities + // for simplification. + // + auto result = astBuilder->getConjunctionSubtypeWitness( + substSub, + substSup, + componentWitnesses[0], + componentWitnesses[1]); + return result; } bool ExtractFromConjunctionSubtypeWitness::_equalsValOverride(Val* val) { if (auto other = as<ExtractFromConjunctionSubtypeWitness>(val)) { - return other->conjunctionWitness && other->conjunctionWitness->equalsVal(conjunctionWitness) && - other->indexInConjunction == indexInConjunction; + if(!sub->equals(other->sub)) return false; + if(!sup->equals(other->sup)) return false; + if(indexInConjunction != other->indexInConjunction) return false; + + return true; } return false; } @@ -683,13 +653,22 @@ void ExtractFromConjunctionSubtypeWitness::_toTextOverride(StringBuilder& out) out << "ExtractFromConjunctionSubtypeWitness("; if (conjunctionWitness) out << conjunctionWitness; + if (sub) + out << sub; + out << ","; + if (sup) + out << sup; out << "," << indexInConjunction; out << ")"; } HashCode ExtractFromConjunctionSubtypeWitness::_getHashCodeOverride() { - return combineHash(indexInConjunction, conjunctionWitness ? conjunctionWitness->getHashCode() : 0); + return combineHash( + conjunctionWitness ? conjunctionWitness->getHashCode() : 0, + sub ? sub->getHashCode() : 0, + sup ? sup->getHashCode() : 0, + indexInConjunction); } // ModifierVal diff --git a/source/slang/slang-ast-val.h b/source/slang/slang-ast-val.h index 75979cb15..1731a5799 100644 --- a/source/slang/slang-ast-val.h +++ b/source/slang/slang-ast-val.h @@ -309,6 +309,13 @@ class TypeEqualityWitness : public SubtypeWitness { SLANG_AST_CLASS(TypeEqualityWitness) + TypeEqualityWitness( + Type* type) + { + this->sub = type; + this->sup = type; + } + // Overrides should be public so base classes can access bool _equalsValOverride(Val* val); void _toTextOverride(StringBuilder& out); @@ -360,7 +367,7 @@ class TransitiveSubtypeWitness : public SubtypeWitness {} }; -// A witness taht `sub : sup` because `sub` was wrapped into +// A witness that `sub : sup` because `sub` was wrapped into // an existential of type `sup`. class ExtractExistentialSubtypeWitness : public SubtypeWitness { @@ -387,7 +394,7 @@ class TaggedUnionSubtypeWitness : public SubtypeWitness // Witnesses that each of the "case" types in the union // is a subtype of `sup`. // - List<Val*> caseWitnesses; + List<SubtypeWitness*> caseWitnesses; // Overrides should be public so base classes can access bool _equalsValOverride(Val* val); @@ -414,11 +421,23 @@ class ConjunctionSubtypeWitness : public SubtypeWitness { SLANG_AST_CLASS(ConjunctionSubtypeWitness) - /// Witness that `sub : sup->left` - Val* leftWitness; + // At the operational level, this class of witness is + // an operation that takes two witness tables `leftWitness` + // and `rightWitness`, and forms a pair/tuple of + // `(leftWitness, rightWitness)`. + + static const Count kComponentCount = 2; + SubtypeWitness* componentWitnesses[kComponentCount]; - /// Witness that `sub : sup->right` - Val* rightWitness; + SubtypeWitness* getLeftWitness() const { return componentWitnesses[0]; } + SubtypeWitness* getRightWitness() const { return componentWitnesses[1]; } + + Count getComponentCount() const { return kComponentCount; } + SubtypeWitness* getComponentWitness(Index index) const + { + SLANG_ASSERT(index >= 0 && index < kComponentCount); + return componentWitnesses[index]; + } bool _equalsValOverride(Val* val); void _toTextOverride(StringBuilder& out); @@ -426,18 +445,23 @@ class ConjunctionSubtypeWitness : public SubtypeWitness Val* _substituteImplOverride(ASTBuilder* astBuilder, SubstitutionSet subst, int* ioDiff); }; - /// A witness that `T : X` because `T : X & Y` or `T : Y & X` + /// A witness that `T <: L` or `T <: R` because `T <: L&R` class ExtractFromConjunctionSubtypeWitness : public SubtypeWitness { SLANG_AST_CLASS(ExtractFromConjunctionSubtypeWitness) - /// Witness that `T : L & R` for some `R` - Val* conjunctionWitness; + // At the operational level, this class of witness is + // an operation that takes a pair/tuple of witness tables + // `(leftWtiness, rightWitness)` and extracts one of the + // elements of it. + + /// Witness that `T < L & R` + SubtypeWitness* conjunctionWitness; /// The zero-based index of the super-type we care about in the conjunction /// - /// If `conjunctionWitness` is `T : X & Y` then this index should be zero if - /// we want to represent `T : X` and one if we want `T : Y`. + /// If `conjunctionWitness` is `T < L & R` then this index should be zero if + /// we want to represent `T < L` and one if we want `T < R`. /// int indexInConjunction; diff --git a/source/slang/slang-check-conformance.cpp b/source/slang/slang-check-conformance.cpp index 7379a6538..0eb44399d 100644 --- a/source/slang/slang-check-conformance.cpp +++ b/source/slang/slang-check-conformance.cpp @@ -7,195 +7,6 @@ namespace Slang { - DeclaredSubtypeWitness* SemanticsVisitor::createSimpleSubtypeWitness( - TypeWitnessBreadcrumb* breadcrumb) - { - DeclaredSubtypeWitness* witness = m_astBuilder->getOrCreate<DeclaredSubtypeWitness>( - breadcrumb->sub, - breadcrumb->sup, - breadcrumb->declRef); - return witness; - } - - - Val* simplifyWitness(ASTBuilder* builder, Val* witness) - { - if (auto extractFromConjunction = as<ExtractFromConjunctionSubtypeWitness>(witness)) - { - auto simplWitness = simplifyWitness(builder, extractFromConjunction->conjunctionWitness); - if (auto conjunction = as<ConjunctionSubtypeWitness>(simplWitness)) - { - auto index = extractFromConjunction->indexInConjunction; - SLANG_ASSERT(index == 0 || index == 1); - if (index == 0) - return conjunction->leftWitness; - else - return conjunction->rightWitness; - } - ExtractFromConjunctionSubtypeWitness* simplExtractFromConjunction = builder->create<ExtractFromConjunctionSubtypeWitness>(); - simplExtractFromConjunction->sub = extractFromConjunction->sub; - simplExtractFromConjunction->sup = extractFromConjunction->sup; - simplExtractFromConjunction->indexInConjunction = extractFromConjunction->indexInConjunction; - simplExtractFromConjunction->conjunctionWitness = as<SubtypeWitness>(simplWitness); - - return simplExtractFromConjunction; - } - else if (auto conjunctionWitness = as<ConjunctionSubtypeWitness>(witness)) - { - auto simplConjunctionWitness = builder->create<ConjunctionSubtypeWitness>(); - simplConjunctionWitness->leftWitness = as<SubtypeWitness>(simplifyWitness(builder, conjunctionWitness->leftWitness)); - simplConjunctionWitness->rightWitness = as<SubtypeWitness>(simplifyWitness(builder, conjunctionWitness->rightWitness)); - simplConjunctionWitness->sub = conjunctionWitness->sub; - simplConjunctionWitness->sup = conjunctionWitness->sup; - - return simplConjunctionWitness; - } - else if (auto transitiveWitness = as<TransitiveSubtypeWitness>(witness)) - { - TransitiveSubtypeWitness* simplTransitiveWitness = builder->getOrCreateWithDefaultCtor<TransitiveSubtypeWitness>( - transitiveWitness->sub, - transitiveWitness->sup, - transitiveWitness->midToSup); - - simplTransitiveWitness->sub = transitiveWitness->sub; - simplTransitiveWitness->sup = transitiveWitness->sup; - simplTransitiveWitness->midToSup = as<SubtypeWitness>(simplifyWitness(builder, transitiveWitness->midToSup)); - simplTransitiveWitness->subToMid = as<SubtypeWitness>(simplifyWitness(builder, transitiveWitness->subToMid)); - - return simplTransitiveWitness; - } - else - { - // TODO: Add other cases. - return witness; - } - } - - - Val* SemanticsVisitor::createTypeWitness( - Type* subType, - DeclRef<AggTypeDecl> superTypeDeclRef, - TypeWitnessBreadcrumb* inBreadcrumbs) - { - SLANG_UNUSED(subType); - SLANG_UNUSED(superTypeDeclRef); - - if(!inBreadcrumbs) - { - // We need to construct a witness to the fact - // that `subType` has been proven to be *equal* - // to `superTypeDeclRef`. - // - auto witness = m_astBuilder->create<TypeEqualityWitness>(); - witness->sub = subType; - witness->sup = subType; - return witness; - } - - // We might have one or more steps in the breadcrumb trail, e.g.: - // - // {A : B} {B : C} {C : D} - // - // The chain is stored as a reversed linked list, so that - // the first entry would be the `(C : D)` relationship - // above. - // - // We need to walk the list and build up a suitable witness, - // which in the above case would look like: - // - // Transitive( - // Transitive( - // Declared({A : B}), - // {B : C}), - // {C : D}) - // - // Because of the ordering of the breadcrumb trail, along - // with the way the `Transitive` case nests, we will be - // building these objects outside-in, and keeping - // track of the "hole" where the next step goes. - // - auto bb = inBreadcrumbs; - - // `witness` here will hold the first (outer-most) object - // we create, which is the overall result. - SubtypeWitness* witness = nullptr; - - // `link` will point at the remaining "hole" in the - // data structure, to be filled in. - SubtypeWitness** link = &witness; - - // As long as there is more than one breadcrumb, we - // need to be creating transitive witnesses. - while (bb->prev) - { - // On the first iteration when processing the list - // above, the breadcrumb would be for `{ C : D }`, - // and so we'd create: - // - // Transitive( - // [...], - // { C : D}) - // - // where `[...]` represents the "hole" we leave - // open to fill in next. - // - if (bb->flavor == TypeWitnessBreadcrumb::Flavor::DeclFlavor) - { - DeclaredSubtypeWitness* declaredWitness = - m_astBuilder->getOrCreate<DeclaredSubtypeWitness>( - bb->sub, bb->sup, bb->declRef); - - TransitiveSubtypeWitness* transitiveWitness = m_astBuilder->getOrCreateWithDefaultCtor<TransitiveSubtypeWitness>(); - transitiveWitness->sub = subType; - transitiveWitness->sup = bb->sup; - transitiveWitness->midToSup = declaredWitness; - - // Fill in the current hole, and then set the - // hole to point into the node we just created. - *link = transitiveWitness; - link = &transitiveWitness->subToMid; - } - else if(bb->flavor == TypeWitnessBreadcrumb::Flavor::AndTypeLeftFlavor) - { - ExtractFromConjunctionSubtypeWitness* extractWitness = m_astBuilder->create<ExtractFromConjunctionSubtypeWitness>(); - extractWitness->sub = subType; - extractWitness->sup = bb->sup; - extractWitness->indexInConjunction = 0; - - *link = extractWitness; - link = (SubtypeWitness**) &extractWitness->conjunctionWitness; - } - else if(bb->flavor == TypeWitnessBreadcrumb::Flavor::AndTypeRightFlavor) - { - ExtractFromConjunctionSubtypeWitness* extractWitness = m_astBuilder->create<ExtractFromConjunctionSubtypeWitness>(); - extractWitness->sub = subType; - extractWitness->sup = bb->sup; - extractWitness->indexInConjunction = 1; - - *link = extractWitness; - link = (SubtypeWitness**) &extractWitness->conjunctionWitness; - } - // Move on with the list. - bb = bb->prev; - } - - // If we exit the loop, then there is only one breadcrumb left. - // In our running example this would be `{ A : B }`. We create - // a simple (declared) subtype witness for it, and plug the - // final hole, after which there shouldn't be a hole to deal with. - DeclaredSubtypeWitness* declaredWitness = createSimpleSubtypeWitness(bb); - *link = declaredWitness; - - // Simplify witnesses of the form ExtractFromConjunction(ConjunctionWitness(...)) - // TODO: At some point, we need a more robust way of checking that two witnesses are in-fact 'equal'. - // In the meantime, this step should suffice. - - - // We now know that our original `witness` variable has been - // filled in, and there are no other holes. - return simplifyWitness(m_astBuilder, witness); - } - bool SemanticsVisitor::isInterfaceSafeForTaggedUnion( DeclRef<InterfaceDecl> interfaceDeclRef) { @@ -238,146 +49,141 @@ namespace Slang } } - bool SemanticsVisitor::_isDeclaredSubtype( - Type* originalSubType, - Type* subType, - DeclRef<AggTypeDecl> superTypeDeclRef, - Val** outWitness, - TypeWitnessBreadcrumb* inBreadcrumbs) + SubtypeWitness* SemanticsVisitor::isSubtype( + Type* subType, + Type* superType) { - // for now look up a conformance member... - if(auto declRefType = as<DeclRefType>(subType)) - { - auto declRef = declRefType->declRef; - - // Easy case: a type conforms to itself. - // - // TODO: This is actually a bit more complicated, as - // the interface needs to be "object-safe" for us to - // really make this determination... - if(declRef == superTypeDeclRef) - { - if(outWitness) - { - *outWitness = createTypeWitness(originalSubType, superTypeDeclRef, inBreadcrumbs); - } - return true; - } - if (const auto dynamicType = as<DynamicType>(subType)) - { - // A __Dynamic type always conforms to the interface via its witness table. - if (outWitness) - { - *outWitness = m_astBuilder->create<DynamicSubtypeWitness>(); - } - return true; - } - else if( auto aggTypeDeclRef = declRef.as<AggTypeDecl>() ) - { - ensureDecl(aggTypeDeclRef, DeclCheckState::CanEnumerateBases); - - bool found = false; - foreachDirectOrExtensionMemberOfType<InheritanceDecl>(this, aggTypeDeclRef, [&](DeclRef<InheritanceDecl> const& inheritanceDeclRef) - { - ensureDecl(inheritanceDeclRef, DeclCheckState::CanUseBaseOfInheritanceDecl); - - // Here we will recursively look up conformance on the type - // that is being inherited from. This is dangerous because - // it might lead to infinite loops. - // - // TODO: A better approach would be to create a linearized list - // of all the interfaces that a given type directly or indirectly - // inherits, and store it with the type, so that we don't have - // to recurse in places like this (and can maybe catch infinite - // loops better). This would also help avoid checking multiply-inherited - // conformances multiple times. - - auto inheritedType = getBaseType(m_astBuilder, inheritanceDeclRef); - - - // There's one annoying corner case where something that *looks* like an inheritnace - // declaration isn't actually one, and that is when an `enum` type includes an explicit - // declaration of its "tag type." - // - if (auto enumDeclRef = declRef.as<EnumDecl>()) - { - if (inheritedType->equals(getTagType(m_astBuilder, enumDeclRef))) - { - return; - } - } - - - // We need to ensure that the witness that gets created - // is a composite one, reflecting lookup through - // the inheritance declaration. - TypeWitnessBreadcrumb breadcrumb; - breadcrumb.prev = inBreadcrumbs; - - breadcrumb.sub = subType; - breadcrumb.sup = inheritedType; - breadcrumb.declRef = inheritanceDeclRef; + // TODO: The Slang codebase is currently being quite slippery by conflating + // multiple concepts, all under the banner of a "subtype" test: + // + // * Struct/class inheritance: When concrete type `A` inherits from concrete + // type `B`, we can directly convert any value of type `A` into a value of type `B` + // + // * Derived interfaces: When interface `X` derives from interface `Y`, we know + // that any concrete type conforming to `X` must also conform to `Y`, so we can + // derive a witness that `A : Y` from a witness tbale that `A : X` for some concrete `A` + // + // * Conformance: When concrete type `A` conforms to interface `X`, we know that there exists + // a witness table for that conformance. + // + // The problem is that these relationships mean different things. If we use the same + // `isSubtype()` test for all of the above cases, then we risk determining that `IFoo` + // *conforms* to `IBar` just because it was declared as `interface IFoo : IBar`. Or + // even more simply that `IFoo` conforms to `IFoo`. + // + // It is dangerous to start treating an interface type like it conforms to itself: + // + // interface IFoo { static int getValue(); } + // int get< T : IFoo >() { return T.getValue(); } + // + // int x = get<IFoo>(); // This needs to be an error!!! + // + // We will eventually need to clarify the distinction between the different kinds of + // subtype-ish relationships, *or* we will need to ensure that `interface`s are not + // treated as proper types (such that they can be passed as generic arguments, etc.) + // + // Note that there is one more case of a subtype-ish relationship that is not covered + // by this function, but that is relevant if/when we do more serious type inference: + // + // * Convertibility: When any value of type `A` can be converted to a value of type + // `B` (even if that conversion might involve computation or a change of representation), + // and that conversion is one that the compiler considers "okay" to do implicitly. + // + // For now we are continuing to conflate all the subtype-ish relationships but not + // tangling convertibility into it. - if(_isDeclaredSubtype(originalSubType, inheritedType, superTypeDeclRef, outWitness, &breadcrumb)) - { - found = true; - } - }); - if(found) - return true; + // TODO: Evaluate whether it is beneficial to memo-cache + // the results of subtype tests on the `SharedSemanticsContext`. - // if an inheritance decl is not found, try to find a GenericTypeConstraintDecl - for (auto genConstraintDeclRef : getMembersOfType<GenericTypeConstraintDecl>(m_astBuilder, aggTypeDeclRef)) - { - ensureDecl(genConstraintDeclRef, DeclCheckState::CanUseBaseOfInheritanceDecl); - auto inheritedType = getSup(m_astBuilder, genConstraintDeclRef); - TypeWitnessBreadcrumb breadcrumb; - breadcrumb.prev = inBreadcrumbs; - breadcrumb.sub = subType; - breadcrumb.sup = inheritedType; - breadcrumb.declRef = genConstraintDeclRef; - if (_isDeclaredSubtype(originalSubType, inheritedType, superTypeDeclRef, outWitness, &breadcrumb)) - { - return true; - } - } - } - else if( auto genericTypeParamDeclRef = declRef.as<GenericTypeParamDecl>() ) - { - // We need to enumerate the constraints placed on this type by its outer - // generic declaration, and see if any of them guarantees that we - // satisfy the given interface.. - auto genericDeclRef = genericTypeParamDeclRef.getParent(m_astBuilder).as<GenericDecl>(); - SLANG_ASSERT(genericDeclRef); + // In the common case, we can use the pre-computed inheritance information for `subType` + // to enumerate all the types it transitively inherits from. + // + auto inheritanceInfo = getShared()->getInheritanceInfo(subType); + for (auto facet : inheritanceInfo.facets) + { + // The `subType` will have a `facet` for each type + // that it transitively inherits from, as well as + // for each `extension` that was found to apply to it. + // + // For subtype testing, we are only interested in + // the facets that represent supertypes, and those + // will be the ones that store a type on the facet. + // + auto facetType = facet->getType(); + if (!facetType) + continue; - for( auto constraintDeclRef : getMembersOfType<GenericTypeConstraintDecl>(m_astBuilder, genericDeclRef) ) - { - ensureDecl(constraintDeclRef, DeclCheckState::CanUseBaseOfInheritanceDecl); - auto sub = getSub(m_astBuilder, constraintDeclRef); - auto sup = getSup(m_astBuilder, constraintDeclRef); + // We will scan until we find a facet that corresponds + // to `superType`, or fail to find such a facet. + // + if (!facetType->equals(superType)) + continue; - auto subDeclRef = as<DeclRefType>(sub); - if(!subDeclRef) - continue; - if(subDeclRef->declRef != genericTypeParamDeclRef) - continue; + // If the `superType` appears in the flattened inheritance list + // for the `subType`, then we know that the subtype relationship + // holds. Conveniently, the `facet` stores a pre-computed witness + // for the subtype relationship, which we can return here. + // + return facet->subtypeWitness; + } + // + // TODO: We could expand upon the test using the facet list above + // by taking the facet lists of both `subType` and `superType` + // and then checking if all of the facets that appear in `superType`'s + // linearization also appear in the linearization for `subType` + // (and occur in the same order). + // + // That test could potentially handle certain cases of interface + // conjunctions that the simpler algorithm above can't, but it wouldn't + // seem to be a complete algorithm unless we ensured that interfaces + // have a canonical sorting order for how they appear in linearizations. + // + // One of the main reasons why we don't implement such a test right now + // is that it isn't obvious how to directly produce a witness value + // as collateral from the test. - // The witness that we create needs to reflect that - // it found the needed conformance by lookup through - // a generic type constraint. + // We expect the logic above to cover the vast majority of subtype + // tests, but there are a few remaining cases of subtype testing + // that cannot be folded into the type linearizations above. + // + // A few of these cases case if the `superType` is a `DeclRefType` + // and, if so, want to compare its `DeclRef` against others. As + // such, we will extract the `DeclRef` here, if it exists, + // as a convienience. + // + DeclRef<Decl> superTypeDeclRef; + if (auto superDeclRefType = as<DeclRefType>(superType)) + { + superTypeDeclRef = superDeclRefType->declRef; + } - TypeWitnessBreadcrumb breadcrumb; - breadcrumb.prev = inBreadcrumbs; - breadcrumb.sub = sub; - breadcrumb.sup = sup; - breadcrumb.declRef = constraintDeclRef; + if (auto dynamicType = as<DynamicType>(subType)) + { + // A __Dynamic type always conforms to the interface via its witness table. + auto witness = m_astBuilder->create<DynamicSubtypeWitness>(); + return witness; + } + else if (auto conjunctionSuperType = as<AndType>(superType)) + { + // We know that `T <: L & R` if `T <: L` and `T <: R`. + // + // We therefore simply recursively test both `T <: L` + // and `T <: R`. + // + auto leftWitness = isSubtype(subType, conjunctionSuperType->left); + if (!leftWitness) return nullptr; + // + auto rightWitness = isSubtype(subType, conjunctionSuperType->right); + if (!rightWitness) return nullptr; - if(_isDeclaredSubtype(originalSubType, sup, superTypeDeclRef, outWitness, &breadcrumb)) - { - return true; - } - } - } + // If both of the sub-relationships hold, we can construct + // a conjunction of those witnesses to witness `T <: L&R` + // + return m_astBuilder->getConjunctionSubtypeWitness( + subType, + conjunctionSuperType, + leftWitness, + rightWitness); } else if (auto extractExistentialType = as<ExtractExistentialType>(subType)) { @@ -386,17 +192,21 @@ namespace Slang // We need to check and make sure the interface type of the `ExtractExistentialType` // is equal to `superType`. // + // TODO(tfoley): We could add support for `ExtractExistentialType` to + // the inheritance linearization logic, and eliminate this case. + // auto interfaceDeclRef = extractExistentialType->originalInterfaceDeclRef; if (interfaceDeclRef.equals(superTypeDeclRef)) { - if (outWitness) - { - *outWitness = extractExistentialType->getSubtypeWitness(); - } - return true; + auto witness = extractExistentialType->getSubtypeWitness(); + return witness; } - return false; + return nullptr; } + // + // TODO(tfoley): We should probably just remove `TaggedUnionType`, + // since there is no useful code that relies on it any more. + // else if(auto taggedUnionType = as<TaggedUnionType>(subType)) { // A tagged union type conforms to an interface if all of @@ -405,29 +215,19 @@ namespace Slang // We will iterate over the "case" types in the tagged // union, and check if they conform to the interface. // Along the way we will collect the conformance witness - // values *if* we are being asked to produce a witness - // value for the tagged union itself (that is, if - // `outWitness` is non-null). + // values for the case types. // - List<Val*> caseWitnesses; + List<SubtypeWitness*> caseWitnesses; for(auto caseType : taggedUnionType->caseTypes) { - Val* caseWitness = nullptr; + auto caseWitness = isSubtype(caseType, superType); - if(!_isDeclaredSubtype( - caseType, - caseType, - superTypeDeclRef, - outWitness ? &caseWitness : nullptr, - nullptr)) + if(!caseWitness) { - return false; + return nullptr; } - if(outWitness) - { - caseWitnesses.add(caseWitness); - } + caseWitnesses.add(caseWitness); } // We also need to validate the requirements on @@ -445,74 +245,23 @@ namespace Slang if( auto superInterfaceDeclRef = superTypeDeclRef.as<InterfaceDecl>() ) { if(!isInterfaceSafeForTaggedUnion(superInterfaceDeclRef)) - return false; + return nullptr; } // If we reach this point then we have a concrete // witness for each of the case types, and that is // enough to build a witness for the tagged union. // - if(outWitness) - { - TaggedUnionSubtypeWitness* taggedUnionWitness = m_astBuilder->create<TaggedUnionSubtypeWitness>(); - taggedUnionWitness->sub = taggedUnionType; - taggedUnionWitness->sup = DeclRefType::create(m_astBuilder, superTypeDeclRef); - taggedUnionWitness->caseWitnesses.swapWith(caseWitnesses); + TaggedUnionSubtypeWitness* taggedUnionWitness = m_astBuilder->create<TaggedUnionSubtypeWitness>(); + taggedUnionWitness->sub = taggedUnionType; + taggedUnionWitness->sup = superType; + taggedUnionWitness->caseWitnesses.swapWith(caseWitnesses); - *outWitness = taggedUnionWitness; - } - return true; + return taggedUnionWitness; } - else if (auto andType = as<AndType>(subType)) - { - // (L & R) is a subtype of T if either L or R is a subtype of T. - // Note that in this method T is explicitly a DeclRef and so cannot be a conjunction itself. - // - TypeWitnessBreadcrumb leftBreadcrumb; - leftBreadcrumb.prev = inBreadcrumbs; - leftBreadcrumb.sub = andType; - leftBreadcrumb.sup = DeclRefType::create(m_astBuilder, superTypeDeclRef); - leftBreadcrumb.declRef = DeclRef<Decl>(); - leftBreadcrumb.flavor = TypeWitnessBreadcrumb::Flavor::AndTypeLeftFlavor; - - if(_isDeclaredSubtype(originalSubType, andType->left, superTypeDeclRef, outWitness, &leftBreadcrumb)) - { - return true; - } - - TypeWitnessBreadcrumb rightBreadcrumb; - rightBreadcrumb.prev = inBreadcrumbs; - rightBreadcrumb.sub = andType; - rightBreadcrumb.sup = DeclRefType::create(m_astBuilder, superTypeDeclRef); - rightBreadcrumb.declRef = DeclRef<Decl>(); - rightBreadcrumb.flavor = TypeWitnessBreadcrumb::Flavor::AndTypeRightFlavor; - if(_isDeclaredSubtype(originalSubType, andType->right, superTypeDeclRef, outWitness, &rightBreadcrumb)) - { - return true; - } - } // default is failure - return false; - } - - bool SemanticsVisitor::isDeclaredSubtype( - Type* subType, - DeclRef<AggTypeDecl> superTypeDeclRef) - { - return _isDeclaredSubtype(subType, subType, superTypeDeclRef, nullptr, nullptr); - } - - bool SemanticsVisitor::isDeclaredSubtype( - Type* subType, - Type* superType) - { - if (auto declRefType = as<DeclRefType>(superType)) - { - if (auto aggTypeDeclRef = declRefType->declRef.as<AggTypeDecl>()) - return _isDeclaredSubtype(subType, subType, aggTypeDeclRef, nullptr, nullptr); - } - return false; + return nullptr; } bool SemanticsVisitor::isInterfaceType(Type* type) @@ -527,77 +276,19 @@ namespace Slang bool SemanticsVisitor::isTypeDifferentiable(Type* type) { - return isDeclaredSubtype(type, m_astBuilder->getDiffInterfaceType()); - } - - Val* SemanticsVisitor::tryGetSubtypeWitness( - Type* subType, - DeclRef<AggTypeDecl> superTypeDeclRef) - { - Val* result = nullptr; - _isDeclaredSubtype(subType, subType, superTypeDeclRef, &result, nullptr); - return result; + return isSubtype(type, m_astBuilder->getDiffInterfaceType()); } - Val* SemanticsVisitor::tryGetInterfaceConformanceWitness( - Type* type, - DeclRef<InterfaceDecl> interfaceDeclRef) + SubtypeWitness* SemanticsVisitor::tryGetInterfaceConformanceWitness( + Type* type, + Type* interfaceType) { - return tryGetSubtypeWitness(type, interfaceDeclRef); + return isSubtype(type, interfaceType); } - Val* SemanticsVisitor::createTypeEqualityWitness( + TypeEqualityWitness* SemanticsVisitor::createTypeEqualityWitness( Type* type) { - TypeEqualityWitness* rs = m_astBuilder->create<TypeEqualityWitness>(); - rs->sub = type; - rs->sup = type; - return rs; - } - - Val* SemanticsVisitor::tryGetSubtypeWitness( - Type* sub, - Type* sup) - { - if(sub->equals(sup)) - { - // They are the same type, so we just need a witness - // for type equality. - return createTypeEqualityWitness(sub); - } - - if(auto supDeclRefType = as<DeclRefType>(sup)) - { - auto supDeclRef = supDeclRefType->declRef; - if(auto supInterfaceDeclRef = supDeclRef.as<InterfaceDecl>()) - { - if(auto witness = tryGetInterfaceConformanceWitness(sub, supInterfaceDeclRef)) - { - return witness; - } - } - } - else if( auto andType = as<AndType>(sup) ) - { - // A type `T` is a subtype of `A & B` if `T` is a - // subtype of `A` and `T` is a subtype of `B`. - // - auto leftWitness = tryGetSubtypeWitness(sub, andType->left); - if(!leftWitness) return nullptr; - - auto rightWitness = tryGetSubtypeWitness(sub, andType->right); - if(!rightWitness) return nullptr; - - ConjunctionSubtypeWitness* w = m_astBuilder->create<ConjunctionSubtypeWitness>(); - w->leftWitness = leftWitness; - w->rightWitness = rightWitness; - w->sub = sub; - w->sup = sup; - return w; - } - - return nullptr; + return m_astBuilder->getTypeEqualityWitness(type); } - - } diff --git a/source/slang/slang-check-constraint.cpp b/source/slang/slang-check-constraint.cpp index c38c9e7f2..2dc263115 100644 --- a/source/slang/slang-check-constraint.cpp +++ b/source/slang/slang-check-constraint.cpp @@ -75,12 +75,12 @@ namespace Slang vectorType->elementCount); } - Type* SemanticsVisitor::TryJoinTypeWithInterface( - Type* type, - DeclRef<InterfaceDecl> interfaceDeclRef) + Type* SemanticsVisitor::_tryJoinTypeWithInterface( + Type* type, + Type* interfaceType) { // The most basic test here should be: does the type declare conformance to the trait. - if(isDeclaredSubtype(type, interfaceDeclRef)) + if(isSubtype(type, interfaceType)) return type; // Just because `type` doesn't conform to the given `interfaceDeclRef`, that @@ -119,7 +119,7 @@ namespace Slang continue; // We only want to consider types that implement the target interface. - if(!isDeclaredSubtype(candidateType, interfaceDeclRef)) + if(!isSubtype(candidateType, interfaceType)) continue; // We only want to consider types where we can implicitly convert from `type` @@ -245,7 +245,7 @@ namespace Slang if( auto leftInterfaceRef = leftDeclRefType->declRef.as<InterfaceDecl>() ) { // - return TryJoinTypeWithInterface(right, leftInterfaceRef); + return _tryJoinTypeWithInterface(right, left); } } if(auto rightDeclRefType = as<DeclRefType>(right)) @@ -253,7 +253,7 @@ namespace Slang if( auto rightInterfaceRef = rightDeclRefType->declRef.as<InterfaceDecl>() ) { // - return TryJoinTypeWithInterface(left, rightInterfaceRef); + return _tryJoinTypeWithInterface(left, right); } } @@ -480,7 +480,7 @@ namespace Slang } // Search for a witness that shows the constraint is satisfied. - auto subTypeWitness = tryGetSubtypeWitness(sub, sup); + auto subTypeWitness = isSubtype(sub, sup); if(subTypeWitness) { // We found a witness, so it will become an (implicit) argument. diff --git a/source/slang/slang-check-conversion.cpp b/source/slang/slang-check-conversion.cpp index 357b75cce..abe9f4817 100644 --- a/source/slang/slang-check-conversion.cpp +++ b/source/slang/slang-check-conversion.cpp @@ -891,43 +891,39 @@ namespace Slang } return true; } - // If we are casting to an interface type, then that will succeed - // if the "from" type conforms to the interface. + + // A type is always convertible to any of its supertypes. // - if (auto toDeclRefType = as<DeclRefType>(toType)) + if(auto witness = tryGetSubtypeWitness(fromType, toType)) { - auto toTypeDeclRef = toDeclRefType->declRef; - if (auto toAggTypeDeclRef = toTypeDeclRef.as<AggTypeDecl>()) + if (outToExpr) { - if(auto witness = tryGetSubtypeWitness(fromType, toAggTypeDeclRef)) + *outToExpr = createCastToSuperTypeExpr(toType, fromExpr, witness); + + // If the original expression was an l-value, then the result + // of the cast may be an l-value itself. We want to be able + // to invoke `[mutating]` methods on a value that is cast to + // an interface it conforms to, and we also expect to be able + // to pass a value of a derived `struct` type into methods that + // expect a value of its base type. + // + // TODO: vet this logic for correctness. + // + if (fromExpr && fromExpr->type.isLeftValue) { - if (outToExpr) - { - *outToExpr = createCastToSuperTypeExpr(toType, fromExpr, witness); - - // If the original expression was an l-value, then the result - // of the cast may be an l-value itself. We want to be able - // to invoke `[mutating]` methods on a value that is cast to - // an interface it conforms to, and we also expect to be able - // to pass a value of a derived `struct` type into methods that - // expect a value of its base type. - // - // TODO: vet this logic for correctness. - // - if (fromExpr && fromExpr->type.isLeftValue) - { - (*outToExpr)->type.isLeftValue = true; - } - } - if (outCost) - *outCost = kConversionCost_CastToInterface; - return true; + (*outToExpr)->type.isLeftValue = true; } } + if (outCost) + *outCost = kConversionCost_CastToInterface; + return true; } // Disallow converting to a ParameterGroupType. - if (const auto toParameterGroupType = as<ParameterGroupType>(toType)) + // + // TODO(tfoley): Under what circumstances would this check ever be needed? + // + if (auto toParameterGroupType = as<ParameterGroupType>(toType)) { return _failedCoercion(toType, outToExpr, fromExpr); } diff --git a/source/slang/slang-check-decl.cpp b/source/slang/slang-check-decl.cpp index 06616b38c..5279ca068 100644 --- a/source/slang/slang-check-decl.cpp +++ b/source/slang/slang-check-decl.cpp @@ -587,11 +587,6 @@ namespace Slang return semantics->ApplyExtensionToType(extDecl, type); } - void ensureDecl(SemanticsVisitor* visitor, Decl* decl, DeclCheckState state) - { - visitor->ensureDecl(decl, state); - } - GenericSubstitution* createDefaultSubstitutionsForGeneric( ASTBuilder* astBuilder, SemanticsVisitor* semantics, @@ -636,8 +631,8 @@ namespace Slang ensureDecl(semantics, genericTypeConstraintDecl, DeclCheckState::ReadyForReference); } auto constraintDeclRef = astBuilder->getSpecializedDeclRef<GenericTypeConstraintDecl>(genericTypeConstraintDecl, outerSubst); - DeclaredSubtypeWitness* witness = - astBuilder->getOrCreate<DeclaredSubtypeWitness>( + auto witness = + astBuilder->getDeclaredSubtypeWitness( getSub(astBuilder, constraintDeclRef), getSup(astBuilder, constraintDeclRef), astBuilder->getSpecializedDeclRef(genericTypeConstraintDecl, outerSubst)); @@ -1530,7 +1525,7 @@ namespace Slang { if (auto declRefType = as<DeclRefType>(inheritanceDecl->base.type)) { - if (declRefType->declRef == m_astBuilder->getDifferentiableInterface()) + if (declRefType->declRef == m_astBuilder->getDifferentiableInterfaceDecl()) { hasDifferentialConformance = true; break; @@ -1732,7 +1727,7 @@ namespace Slang auto baseType = as<DeclRefType>(inheritanceDecl->witnessTable->baseType); if (!baseType) return; - if (baseType->declRef.getDecl() != m_astBuilder->getDifferentiableInterface().getDecl()) + if (baseType->declRef.getDecl() != m_astBuilder->getDifferentiableInterfaceDecl().getDecl()) return; RequirementWitness witnessValue; auto requirementDecl = m_astBuilder->getSharedASTBuilder()->findBuiltinRequirementDecl(BuiltinRequirementKind::DifferentialType); @@ -2287,10 +2282,10 @@ namespace Slang auto satisfyingConstraintDeclRef = satisfyingMemberDeclRef.as<GenericTypeConstraintDecl>(); SLANG_ASSERT(satisfyingConstraintDeclRef); - auto satisfyingWitness = m_astBuilder->getOrCreate<DeclaredSubtypeWitness>(); - satisfyingWitness->sub = getSub(m_astBuilder, satisfyingConstraintDeclRef); - satisfyingWitness->sup = getSup(m_astBuilder, satisfyingConstraintDeclRef); - satisfyingWitness->declRef = satisfyingConstraintDeclRef; + auto satisfyingWitness = m_astBuilder->getDeclaredSubtypeWitness( + getSub(m_astBuilder, satisfyingConstraintDeclRef), + getSup(m_astBuilder, satisfyingConstraintDeclRef), + satisfyingConstraintDeclRef); requiredSubstArgs.add(satisfyingWitness); } @@ -3533,18 +3528,16 @@ namespace Slang auto reqType = getBaseType(m_astBuilder, requiredInheritanceDeclRef); - DeclaredSubtypeWitness* interfaceIsReqWitness = - m_astBuilder->getOrCreate<DeclaredSubtypeWitness>( + auto interfaceIsReqWitness = + m_astBuilder->getDeclaredSubtypeWitness( superInterfaceType, reqType, requiredInheritanceDeclRef); // ... - TransitiveSubtypeWitness* subIsReqWitness = m_astBuilder->getOrCreateWithDefaultCtor<TransitiveSubtypeWitness>(subType, reqType, interfaceIsReqWitness); - subIsReqWitness->sub = subType; - subIsReqWitness->sup = reqType; - subIsReqWitness->subToMid = subTypeConformsToSuperInterfaceWitness; - subIsReqWitness->midToSup = interfaceIsReqWitness; + auto subIsReqWitness = m_astBuilder->getTransitiveSubtypeWitness( + subTypeConformsToSuperInterfaceWitness, + interfaceIsReqWitness); // ... RefPtr<WitnessTable> satisfyingWitnessTable = new WitnessTable(); @@ -6763,7 +6756,6 @@ namespace Slang } } - static void _dispatchDeclCheckingVisitor(Decl* decl, DeclCheckState state, SemanticsContext const& shared) { switch(state) diff --git a/source/slang/slang-check-expr.cpp b/source/slang/slang-check-expr.cpp index 9af8fd867..24f130add 100644 --- a/source/slang/slang-check-expr.cpp +++ b/source/slang/slang-check-expr.cpp @@ -935,7 +935,7 @@ namespace Slang return type; } } - if (const auto witness = as<SubtypeWitness>(tryGetInterfaceConformanceWitness(type, builder->getDifferentiableInterface()))) + if (const auto witness = as<SubtypeWitness>(tryGetInterfaceConformanceWitness(type, builder->getDifferentiableInterfaceType()))) { auto diffTypeLookupResult = lookUpMember( getASTBuilder(), @@ -1044,7 +1044,7 @@ namespace Slang if (auto declRefType = as<DeclRefType>(type)) { if (auto subtypeWitness = as<SubtypeWitness>( - tryGetInterfaceConformanceWitness(type, getASTBuilder()->getDifferentiableInterface()))) + tryGetInterfaceConformanceWitness(type, getASTBuilder()->getDifferentiableInterfaceType()))) { addDifferentiableTypeToDiffTypeRegistry((DeclRefType*)type, subtypeWitness); } @@ -2359,9 +2359,9 @@ namespace Slang } // Get a reference to the builtin 'IDifferentiable' interface - auto differentiableInterface = m_astBuilder->getDifferentiableInterface(); - - SubtypeWitness* conformanceWitness = as<SubtypeWitness>(tryGetInterfaceConformanceWitness(primalType, differentiableInterface)); + auto differentiableInterface = getASTBuilder()->getDifferentiableInterfaceType(); + + auto conformanceWitness = as<Witness>(isSubtype(primalType, differentiableInterface)); // Check if the provided type inherits from IDifferentiable. // If not, return the original type. if (conformanceWitness) @@ -2960,7 +2960,7 @@ namespace Slang expr->value = originalVal; // If value is a subtype of `type`, then this expr is always true. - if (isDeclaredSubtype(expr->value->type.type, expr->typeExpr.type)) + if(isSubtype(expr->value->type.type, expr->typeExpr.type)) { // Instead of returning a BoolLiteralExpr, we use a field to indicate this scenario, // so that the language server can still see the original syntax tree. diff --git a/source/slang/slang-check-impl.h b/source/slang/slang-check-impl.h index 0a99fcb97..709245c28 100644 --- a/source/slang/slang-check-impl.h +++ b/source/slang/slang-check-impl.h @@ -264,6 +264,274 @@ namespace Slang Initializer, }; + struct FacetImpl; + + /// Information about one "facet" of a type or declaration + /// + /// In the simplest terms, a facet represents a grouping of + /// member declarations that were all originally declared + /// as part of the same `{}`-enclosed body. + /// + /// A given *entity* (a type, type declaration, or `extension` + /// declaration) may have multiple facets, depending on what it + /// declares, what it inherits from, or what `extension`s apply to it. + /// + /// Broadly, an entity will have: + /// + /// * A *self facet*, if it has a body, that contains the members + /// the entity directly declares. + /// + /// * An *inherited facet* for each base type that it (transitively) + /// inherits from. Inherited facets are either *direct*, if the + /// original entity stated the inheritance relationship, or + /// *indirect* if they arise from the transitive closure of the + /// inheritance relationship. Each inherited facet contains the + /// members of the entity that was inherited from. + /// + /// * An *extension facet* for each `extension` declaration that + /// is known to apply to the entity in the context where semantic + /// checking is being performed. Each extension facet contains the + /// members of the `extension` that applied. + /// + struct Facet + { + public: + /// Kinds of facets that can occur + enum class Kind + { + Type, + Extension, + }; + + /// How many indirections away from the self facet? + typedef unsigned int DirectnessVal; + enum class Directness : DirectnessVal + { + Self = 0, + Direct = 1, + }; + + /// The *origin* of a facet is the type and/or declaration + /// that the facet's members belong to. + /// + struct Origin + { + /// A `DeclRef` to the declaration this facet corresponds to, if any. + /// + /// This might be a type declaration, an `extension` declaration, + /// or nothing. + /// + DeclRef<Decl> declRef; + + /// The type that this facet corresponds to, if any + Type* type = nullptr; + + Origin() + {} + + explicit Origin(DeclRef<Decl> declRef, Type* type = nullptr) + : declRef(declRef) + , type(type) + {} + }; + + Facet() + {} + + typedef FacetImpl Impl; + + Facet(Impl* impl) + : _impl(impl) + {} + + Impl* getImpl() const { return _impl; } + Impl* operator->() const { return _impl; } + + private: + Impl* _impl = nullptr; + }; + + + /// Do the origins of `left` and `right` match, + /// such that they are both facets for the same + /// base type or `extension`? + /// + bool originsMatch(Facet left, Facet right); + + inline bool operator!(Facet facet) { return !facet.getImpl(); } + + bool operator==(Facet::Origin left, Facet::Origin right); + + inline bool operator!=(Facet::Origin left, Facet::Origin right) + { + return !(left == right); + } + + /// Heap-allocated implementation of a single facet. + struct FacetImpl + { + /// The kind of this facet + Facet::Kind kind = Facet::Kind::Type; + + /// How many indirections away from the self facet? + Facet::Directness directness = Facet::Directness::Self; + + /// The origin of this facet. + /// + /// This is the type or declaration that the facet + /// corresponds to. + /// + Facet::Origin origin; + + Type* getType() const { return origin.type; } + DeclRef<Decl> getDeclRef() const { return origin.declRef; } + + /// A witness that the type this facet belongs to + /// is a subtype of `origin.type` (if both of those + /// types exist). + /// + SubtypeWitness* subtypeWitness = nullptr; + + /// The next facet in the linearized inheritance list of the entity. + Facet next; + + FacetImpl() + {} + + FacetImpl( + Facet::Kind kind, + Facet::Directness directness, + DeclRef<Decl> declRef, + Type* type, + SubtypeWitness* subtypeWitness) + : kind(kind) + , directness(directness) + , origin(declRef, type) + , subtypeWitness(subtypeWitness) + {} + }; + + struct FacetListBuilder; + + /// A singly linked list of facets. + struct FacetList + { + public: + FacetList() + {} + + explicit FacetList(Facet head) + : _head(head) + {} + + Facet getHead() const { return _head; } + Facet& getHead() { return _head; } + + Facet advanceHead() + { + SLANG_ASSERT(_head.getImpl()); + auto facet = _head; + _head = facet->next; + return facet; + } + + Facet popHead() + { + auto facet = advanceHead(); + facet->next = nullptr; + return facet; + } + + FacetList getTail() const + { + SLANG_ASSERT(_head.getImpl()); + return FacetList(_head->next); + } + + bool containsMatchFor(Facet facet) const; + + bool isEmpty() const { return _head.getImpl() == nullptr; } + + struct Iterator + { + public: + Iterator() + {} + + Iterator(Facet::Impl* cursor) + : _cursor(cursor) + {} + + bool operator!=(Iterator const& that) const + { + return this->_cursor != that._cursor; + } + + void operator++() + { + SLANG_ASSERT(_cursor); + _cursor = _cursor->next.getImpl(); + } + + Facet operator*() const + { + return _cursor; + } + + private: + Facet::Impl* _cursor = nullptr; + }; + + Iterator begin() const { return Iterator(_head.getImpl()); } + Iterator end() const { return Iterator(); } + + struct Appender + { + public: + Appender(FacetList& list) + { + _link = &list._head; + } + + void add(Facet facet) + { + *_link = facet; + _link = &facet->next; + } + + protected: + Appender() + {} + + Facet* _link = nullptr; + }; + + typedef FacetListBuilder Builder; + + protected: + + Facet _head; + }; + + struct FacetListBuilder : FacetList, FacetList::Appender + { + public: + FacetListBuilder() + { + _link = &_head; + } + }; + + /// Information about the inheritance of an entity (type or declaration) + /// + /// Currently this is only used to store a linearized list of the + /// `Facet`s that the type/declaration transitively inherits. + /// + struct InheritanceInfo + { + FacetList facets; + }; + /// Shared state for a semantics-checking session. struct SharedSemanticsContext { @@ -338,7 +606,13 @@ namespace Slang bool isBackwardDifferentiableFunc(FunctionDeclBase* func); FunctionDifferentiableLevel _getFuncDifferentiableLevelImpl(FunctionDeclBase* func, int recurseLimit); FunctionDifferentiableLevel getFuncDifferentiableLevel(FunctionDeclBase* func); - + + /// Get the processed inheritance information for `type`, including all its facets + InheritanceInfo getInheritanceInfo(Type* type); + + /// Get the processed inheritance information for `extension`, including all its facets + InheritanceInfo getInheritanceInfo(DeclRef<ExtensionDecl> const& extension); + private: /// Mapping from type declarations to the known extensiosn that apply to them Dictionary<AggTypeDecl*, RefPtr<CandidateExtensionList>> m_mapTypeDeclToCandidateExtensions; @@ -359,6 +633,96 @@ namespace Slang /// Add associated decls declared in `moduleDecl` to `m_mapDeclToAssociatedDecls` void _addDeclAssociationsFromModule(ModuleDecl* moduleDecl); + ASTBuilder* _getASTBuilder() { return m_linkage->getASTBuilder(); } + + InheritanceInfo _getInheritanceInfo(DeclRef<Decl> declRef, DeclRefType* correspondingType); + InheritanceInfo _calcInheritanceInfo(Type* type); + InheritanceInfo _calcInheritanceInfo(DeclRef<Decl> declRef, DeclRefType* correspondingType); + + struct DirectBaseInfo + { + FacetList facets; + + Facet::Impl facetImpl; + + DirectBaseInfo* next = nullptr; + }; + + struct DirectBaseListBuilder; + + struct DirectBaseList + { + public: + struct Iterator + { + public: + Iterator() + {} + + Iterator(DirectBaseInfo* cursor) + : _cursor(cursor) + {} + + bool operator!=(Iterator that) const + { + return _cursor != that._cursor; + } + + void operator++() + { + SLANG_ASSERT(_cursor); + _cursor = _cursor->next; + } + + DirectBaseInfo* operator*() + { + return _cursor; + } + + private: + DirectBaseInfo* _cursor = nullptr; + }; + + Iterator begin() const { return Iterator(_head); } + Iterator end() const { return Iterator(); } + + bool isEmpty() const + { + return _head == nullptr; + } + + bool doesAnyTailContainMatchFor(Facet facet) const; + + void removeEmptyLists(); + + typedef DirectBaseListBuilder Builder; + + public: + DirectBaseInfo* _head = nullptr; + }; + + struct DirectBaseListBuilder : DirectBaseList + { + public: + DirectBaseListBuilder() + { + _link = &_head; + } + + void add(DirectBaseInfo* base) + { + *_link = base; + _link = &base->next; + } + + private: + DirectBaseInfo** _link = nullptr; + }; + + void _mergeFacetLists(DirectBaseList bases, FacetList baseFacets, FacetList::Builder& ioMergedFacets); + + Dictionary<Type*, InheritanceInfo> m_mapTypeToInheritanceInfo; + Dictionary<DeclRef<Decl>, InheritanceInfo> m_mapDeclRefToInheritanceInfo; }; /// Local/scoped state of the semantic-checking system @@ -1399,48 +1763,6 @@ namespace Slang VectorExpressionType* vectorType, BasicExpressionType* scalarType); - struct TypeWitnessBreadcrumb - { - TypeWitnessBreadcrumb* prev; - - Type* sub = nullptr; - Type* sup = nullptr; - DeclRef<Decl> declRef; - - enum Flavor - { - // Describes a sub-type super-type relationship through a - // reference to an inhertiance declaration. - DeclFlavor, - - // Describes a sub-type super-type relationship through - // conjunction. This doesn't necessarily have a corresponding declaration - // since AndTypes cannot actually be used as types. - // i.e. if (A & B) subtype C because A subtype C, then we use AndTypeLeft to represent - // that relationship. - AndTypeLeftFlavor, - AndTypeRightFlavor - }; - - Flavor flavor = DeclFlavor; - }; - - // Create a subtype witness based on the declared relationship - // found in a single breadcrumb - DeclaredSubtypeWitness* createSimpleSubtypeWitness( - TypeWitnessBreadcrumb* breadcrumb); - - /// Create a witness that `subType` is a sub-type of `superTypeDeclRef`. - /// - /// The `inBreadcrumbs` parameter represents a linked list of steps - /// in the process that validated the sub-type relationship, which - /// will be used to inform the construction of the witness. - /// - Val* createTypeWitness( - Type* subType, - DeclRef<AggTypeDecl> superTypeDeclRef, - TypeWitnessBreadcrumb* inBreadcrumbs); - /// Is the given interface one that a tagged-union type can conform to? /// /// If a tagged union type `__TaggedUnion(A,B)` is going to be @@ -1462,35 +1784,16 @@ namespace Slang DeclRef<InterfaceDecl> interfaceDeclRef, DeclRef<Decl> requirementDeclRef); - /// Check whether `subType` is declared a sub-type of `superTypeDeclRef` - /// - /// If this function returns `true` (because the subtype relationship holds), - /// then `outWitness` will be set to a value that serves as a witness - /// to the subtype relationship. - /// - /// This function may be used to validate a transitive subtype relationship - /// where, e.g., `A : C` becase `A : B` and `B : C`. In such a case, a recursive - /// call to `_isDeclaredSubtype` may occur where `originalSubType` is `A`, - /// `subType` is `C`, and `superTypeDeclRef` is `C`. The `inBreadcrumbs` in that - /// case would include information for the `A : B` relationship, which can be - /// used to construct a witness for `A : C` from the `A : B` and `B : C` witnesses. - /// - bool _isDeclaredSubtype( - Type* originalSubType, - Type* subType, - DeclRef<AggTypeDecl> superTypeDeclRef, - Val** outWitness, - TypeWitnessBreadcrumb* inBreadcrumbs); - - /// Check whether `subType` is a sub-type of `superTypeDeclRef`. - bool isDeclaredSubtype( - Type* subType, - DeclRef<AggTypeDecl> superTypeDeclRef); - - /// Check whether `subType` is a sub-type of `supType`. - bool isDeclaredSubtype( - Type* subType, - Type* supType); + /// Check whether `subType` is a subtype of `superType` + /// + /// If `subType` is a subtype of `superType`, returns + /// a witness value for the subtype relationship. + /// + /// If `subType` is *not* a subtype of `superType`, returns null. + /// + SubtypeWitness* isSubtype( + Type* subType, + Type* superType); bool isInterfaceType(Type* type); @@ -1500,9 +1803,12 @@ namespace Slang /// and return a witness to the sub-type relationship if it holds /// (return null otherwise). /// - Val* tryGetSubtypeWitness( - Type* subType, - DeclRef<AggTypeDecl> superTypeDeclRef); + SubtypeWitness* tryGetSubtypeWitness( + Type* subType, + Type* superType) + { + return isSubtype(subType, superType); + } /// Check whether `type` conforms to `interfaceDeclRef`, /// and return a witness to the conformance if it holds @@ -1510,9 +1816,9 @@ namespace Slang /// /// This function is equivalent to `tryGetSubtypeWitness()`. /// - Val* tryGetInterfaceConformanceWitness( - Type* type, - DeclRef<InterfaceDecl> interfaceDeclRef); + SubtypeWitness* tryGetInterfaceConformanceWitness( + Type* type, + Type* interfaceType); Expr* createCastToSuperTypeExpr( Type* toType, @@ -1528,9 +1834,9 @@ namespace Slang Type* toType, Type* fromType); - Type* TryJoinTypeWithInterface( - Type* type, - DeclRef<InterfaceDecl> interfaceDeclRef); + Type* _tryJoinTypeWithInterface( + Type* type, + Type* interfaceType); // Try to compute the "join" between two types Type* TryJoinTypes( @@ -1649,15 +1955,9 @@ namespace Slang // Create a witness that attests to the fact that `type` // is equal to itself. - Val* createTypeEqualityWitness( + TypeEqualityWitness* createTypeEqualityWitness( Type* type); - // If `sub` is a subtype of `sup`, then return a value that - // can serve as a "witness" for that fact. - Val* tryGetSubtypeWitness( - Type* sub, - Type* sup); - // In the case where we are explicitly applying a generic // to arguments (e.g., `G<A,B>`) check that the constraints // on those parameters are satisfied. @@ -1924,6 +2224,18 @@ namespace Slang CompletionSuggestions::ScopeKind scopeKind, LookupResult const& lookupResult); }; + + inline void ensureDecl(SemanticsVisitor* visitor, Decl* decl, DeclCheckState state) + { + visitor->ensureDecl(decl, state); + } + + DeclRef<ExtensionDecl> ApplyExtensionToType( + SemanticsVisitor* semantics, + ExtensionDecl* extDecl, + Type* type); + + struct SemanticsExprVisitor : public SemanticsVisitor , ExprVisitor<SemanticsExprVisitor, Expr*> diff --git a/source/slang/slang-check-inheritance.cpp b/source/slang/slang-check-inheritance.cpp new file mode 100644 index 000000000..8e867b4a7 --- /dev/null +++ b/source/slang/slang-check-inheritance.cpp @@ -0,0 +1,945 @@ +// slang-check-inheritance.cpp +#include "slang-check-impl.h" + +// This file implements the semantic checking logic +// related to computing linearized inheritance +// information for types and decalrations. + +//#include "slang-lookup.h" +//#include "slang-syntax.h" +//#include "slang-ast-synthesis.h" +//#include <limits> + +namespace Slang +{ + InheritanceInfo SharedSemanticsContext::getInheritanceInfo(Type* type) + { + // We cache the computed inheritance information for types, + // and re-use that information whenever possible. + + if(auto found = m_mapTypeToInheritanceInfo.tryGetValue(type)) + return *found; + + // Note: we install a null pointer into the dictionary to act + // as a sentinel during the processing of calculating the inheritnace + // info. If we encounter this sentinel value during the calcuation, + // it means that there was some kind of circular dependency in the + // inheritance graph, and we need to avoid crashing or going + // into an infinite loop in such cases. + // + m_mapTypeToInheritanceInfo[type] = InheritanceInfo(); + + auto info = _calcInheritanceInfo(type); + m_mapTypeToInheritanceInfo[type] = info; + + return info; + } + + InheritanceInfo SharedSemanticsContext::getInheritanceInfo(DeclRef<ExtensionDecl> const& extension) + { + // We bottleneck the calculation of inheritance information + // for type and `extension` `DeclRef`s through a single + // routine with an optional `Type` parameter. + // + return _getInheritanceInfo(extension, nullptr); + } + + InheritanceInfo SharedSemanticsContext::_getInheritanceInfo(DeclRef<Decl> declRef, DeclRefType* declRefType) + { + // Just as with `Type`s, we cache and re-use the inheritance + // information that has been computed for a `DeclRef` whenever + // possible. + + if (auto found = m_mapDeclRefToInheritanceInfo.tryGetValue(declRef)) + return *found; + + // Note: we install a null pointer into the dictionary to act + // as a sentinel during the processing of calculating the inheritnace + // info. If we encounter this sentinel value during the calcuation, + // it means that there was some kind of circular dependency in the + // inheritance graph, and we need to avoid crashing or going + // into an infinite loop in such cases. + // + m_mapDeclRefToInheritanceInfo[declRef] = InheritanceInfo(); + + auto info = _calcInheritanceInfo(declRef, declRefType); + m_mapDeclRefToInheritanceInfo[declRef] = info; + + return info; + } + + InheritanceInfo SharedSemanticsContext::_calcInheritanceInfo(DeclRef<Decl> declRef, DeclRefType* declRefType) + { + // This method is the main engine for computing linearized inheritance + // lists for types and `extension` declarations. + // + // The approach we use for linearization of an inheritance graph is based on + // what is the most broadly-accepted solution to the problem, presented in + // "A Monotonic Superclass Linearization for Dylan" by Barret et al. + // The algorithm recommended in that paper is also called the "C3 linearization + // algorithm." Many developers are most familiar with C3 linearization because + // it is used to compute the method resolution order (MRO) for a class in Python. + // + // The basic idea is that given a type declaration like: + // + // class A : B, C { ... } + // + // we can construct a linearization of the transitive bases of `A` + // by merging the linearizations for `B` and `C`. Any transitive + // base of `A` should appear in the linearization for `B` and/or `C`, + // so the main tasks are to remove duplicates (when a base type appears + // in both the linearization of `B` *and* `C`), and to ensure that + // the ordering is reasonable. + // + // What makes an ordering "reasonable" is a little subtle, especially + // in the context of Slang. In the original use case, the order of types + // in the linearization would determine which methods would override + // which other ones, so different orderings could have large semantic + // impact. Slang currently has less support for overriding, but is + // likely to add more over time. + // + // At the very least, we require that if `S <: T` for types `S` and `T`, + // then `S` should appear *before* `T` in the linearization. This, e.g., + // guarantees that a concrete type that implements an `interface` will + // be listed before that interface and thus during lookup the members + // of the concrete type will be found before those of the `interface`. + // + // We will revisit the question of "reasonable" orderings later, as + // we get more into the core of the algorithm. + + // Our linearization approach will construct a list of *facets* for + // the `declRef` in question, where each facet corresponds to a + // transitive base type, or an applicable `extension`. + // + FacetList::Builder allFacets; + + // It is possible that `declRef` is itself a type declaration, + // in which case `declRefType` will be the coresponding type. + // However, if `declRef` is an `extension` declaration, we + // will extract the type that the extension applies to, so + // that we can have a consistent "self type" to represent + // the type that is at the root of the inheritance list. + // + Type* selfType = declRefType; + Facet::Kind selfFacetKind = Facet::Kind::Type; + + auto astBuilder = _getASTBuilder(); + auto& arena = astBuilder->getArena(); + SemanticsVisitor visitor(this); + if (auto extensionDeclRef = declRef.as<ExtensionDecl>()) + { + auto extendedType = getTargetType(astBuilder, extensionDeclRef); + selfType = extendedType; + selfFacetKind = Facet::Kind::Extension; + } + + // Because we are dealing with entities that have declarations, the + // first item in our linearization will always be a facet for + // the declaration itself. + // + TypeEqualityWitness* selfIsSelf = selfType ? visitor.createTypeEqualityWitness(selfType) : nullptr; + Facet selfFacet = new(arena) Facet::Impl( + selfFacetKind, + Facet::Directness::Self, + declRef, + selfType, + selfIsSelf); + allFacets.add(selfFacet); + + // After the self facet will come a list of facets formed + // by merging the facet lists of each of the direct/declared + // bases of the type/declaration in question. + // + // We will first traverse the structure of `declRef` to + // accumulate the list of bases, and then perform the merge + // when we are done. + // + DirectBaseList::Builder directBases; + FacetList::Builder directBaseFacets; + + // We start with a simple operation to add an entry + // into the list of direct bases, for the case where + // we already have all of the relevant information + // about that base. + // + auto addDirectBaseFacet = [&]( + Facet::Kind kind, + Type* baseType, + SubtypeWitness* selfIsBaseWitness, + DeclRef<Decl> const& baseDeclRef, + InheritanceInfo const& baseInheritanceInfo) + { + auto baseInfo = new(arena) DirectBaseInfo(); + + // The information we store for each direct + // base comprises two main things. + // + // First, we have a `Facet` that will represent + // the base in the linearized inheritance list + // we are building. + // + baseInfo->facetImpl = FacetImpl( + kind, + Facet::Directness::Direct, + baseDeclRef, + baseType, + selfIsBaseWitness); + Facet baseFacet(&baseInfo->facetImpl); + // + // Second, we have a list of the facets in the + // linearization of the base itself. + // + baseInfo->facets = baseInheritanceInfo.facets; + + directBaseFacets.add(baseFacet); + directBases.add(baseInfo); + }; + + // In the case where we know that the base being added + // represents a direct base *type* (and not an `extension`) + // we can derive some of the information needed by + // `addDirectBaseFacet`. + // + auto addDirectBaseType = [&]( + Type* baseType, + SubtypeWitness* selfIsBaseWitness) + { + // If we are representing inheritance from a type, + // then we should have a witness that the type + // in question (either the type being declared by + // `declRef`, or the type being *extended* by + // `declRef`) inherits from that base. + // + SLANG_ASSERT(selfIsBaseWitness); + + auto baseInheritanceInfo = getInheritanceInfo(baseType); + + DeclRef<Decl> baseDeclRef; + if (auto baseDeclRefType = as<DeclRefType>(baseType)) + { + baseDeclRef = baseDeclRefType->declRef; + } + + addDirectBaseFacet( + Facet::Kind::Type, + baseType, + selfIsBaseWitness, + baseDeclRef, + baseInheritanceInfo); + }; + + // We now look at the structure of the declaration itself + // to help us enumerate the direct bases. + // + if (auto aggTypeDeclBaseRef = declRef.as<AggTypeDeclBase>()) + { + // In the case where we have an aggregate type or `extension` + // declaration, we can use the explicit list of direct bases. + // + for (auto inheritanceDeclRef : getMembersOfType<InheritanceDecl>(_getASTBuilder(), aggTypeDeclBaseRef)) + { + visitor.ensureDecl(inheritanceDeclRef, DeclCheckState::CanUseBaseOfInheritanceDecl); + + // Note: In certain cases something takes the *syntactic* form of an inheritance + // clause, but it is not actually something that should be treated as implying + // a subtype relationship. For example, an `enum` declaration can use what looks + // like an inheritance clause to indicate its underlying "tag type." + // + // We skip such pseudo-inheritance relationships for the purposes of determining + // the linearized list of bases. + // + if (inheritanceDeclRef.getDecl()->hasModifier<IgnoreForLookupModifier>()) + continue; + + // The base type and subtype witness can easily be determined + // using the `InheritanceDecl`. + // + auto baseType = getSup(astBuilder, inheritanceDeclRef); + auto satisfyingWitness = astBuilder->getDeclaredSubtypeWitness( + selfType, + baseType, + inheritanceDeclRef); + + addDirectBaseType(baseType, satisfyingWitness); + } + + // In the case of an `associatedtype`, the constraints on the associated + // type are encoded as `GenericTypeConstraintDecl`s instead of `InheritanceDecl`s. + // + // TOD(tfoley): Can we try to unify the representations of these to avoid having + // to iterate twice? + // + for (auto constraintDeclRef : getMembersOfType<GenericTypeConstraintDecl>(astBuilder, aggTypeDeclBaseRef)) + { + visitor.ensureDecl(constraintDeclRef, DeclCheckState::CanUseBaseOfInheritanceDecl); + + auto baseType = getSup(astBuilder, constraintDeclRef); + auto satisfyingWitness = astBuilder->getDeclaredSubtypeWitness( + selfType, + baseType, + constraintDeclRef); + addDirectBaseType(baseType, satisfyingWitness); + } + } + else if (auto genericTypeParamDeclRef = declRef.as<GenericTypeParamDecl>()) + { + // The constraints placed on a generic type parameter are siblings of that + // parameter in its parent `GenericDecl`, so we need to enumerate all of + // the constraints of the parent declaration to find those that constrain + // this parameter. + // + // TODO(tfoley): We might consider adding a cached representation of the + // constraint information that is keyed on a per-parameter basis. Such a + // representation would need to take into account canonicalization of + // constraints. + + auto genericDeclRef = genericTypeParamDeclRef.getParent(astBuilder).as<GenericDecl>(); + SLANG_ASSERT(genericDeclRef); + + ensureDecl(&visitor, genericDeclRef.getDecl(), DeclCheckState::CanSpecializeGeneric); + + for (auto constraintDeclRef : getMembersOfType<GenericTypeConstraintDecl>(astBuilder, genericDeclRef)) + { + auto subType = getSub(astBuilder, constraintDeclRef); + auto superType = getSup(astBuilder, constraintDeclRef); + + // We only consider constraints where the type represented + // by `genericTypeParamDeclRef` is the subtype, since those + // constraints are the ones that give us information about + // the declared supertypes. + // + // TODO: consider whether other kinds of constraints could + // also apply here. + // + auto subDeclRefType = as<DeclRefType>(subType); + if (!subDeclRefType) + continue; + if (subDeclRefType->declRef != genericTypeParamDeclRef) + continue; + + // Because the constraint is a declared inheritance relationship, + // adding the base to our list of direct bases is as straightforward + // as in all the preceding cases. + // + auto satisfyingWitness = _getASTBuilder()->getDeclaredSubtypeWitness( + selfType, + superType, + constraintDeclRef); + addDirectBaseType(superType, satisfyingWitness); + } + } + + // At this point we have enumerated all of the bases that can be + // gleaned by looking at the `declRef` itself. The next step is + // to consider any `extension` declarations that might apply to + // a type being delared. + // + // In our current system, only nominal types (those with `Decl`s) + // can be extended, so we begin by checking if the `selfType` + // is a nominal/`DeclRef` type. + // + // Note: this step will *not* apply when `declRef` is an `extension` + // declaration, since it directly checks for an `AggTypeDecl` + // instead of an `AggTypeDeclBase`. + // + // Similarly, we do *not* add the type being extended to the list + // of bases for an `extension`. + // + // These choices are important to avoid circular dependencies, where + // the linearization of an `extension` would end up depending on its + // own linearization (either directly or through a dependency on + // the linearization of the type being extended). + // + // Instead, the linearization we create here for an `extension` will + // *only* contain facets for the members introduced by the `extension` + // itself, as well as any transitive bases declared on that `extension`. + // + if (auto directAggTypeDeclRef = declRef.as<AggTypeDecl>()) + { + for (auto extDecl : getCandidateExtensions(directAggTypeDeclRef, &visitor)) + { + // The list of *candidate* extensions is computed and + // cached based on the identity of the declaration alone, + // and does not take into account any generic arguments + // of either the type or the `extension`. + // + // For example, we might have an `extension` that applies + // to `vector<float,N>` for any `N`, but the `selfType` + // that we are working with could be `<vector<int,2>` so + // that the extension doesn't match. + // + // In order to make sure that we don't enumerate members + // that don't make sense in context, we must apply + // the extension to the type and see if we succeed in + // making a match. + // + auto extDeclRef = ApplyExtensionToType(&visitor, extDecl, selfType); + if (!extDeclRef) + continue; + + // In the case where we *do* find an extension that + // applies to the type, we add a declared base to + // represent the `extension`, knowing that its + // own linearized inheritance list will include + // any transitive based declared on the `extension`. + // + auto extInheritanceInfo = getInheritanceInfo(extDeclRef); + addDirectBaseFacet( + Facet::Kind::Extension, + selfType, + selfIsSelf, + extDeclRef, + extInheritanceInfo); + } + } + + // At this point, the list of direct bases (each with its own linearization) + // is complete. + // + // At this point we could scan through the list of bases and perform + // consistency checks on it. For example, when two types in the list of direct + // bases have a subtype relationship between them, it is possible that the + // programmer made some kind of mistake, and we could emit a diagnostic + // about it. + // + // The published C3 algorithm actually considers the declared list of bases + // as one of the inputs to its merge, and is very strict about ordering. + // As such, it would be an error for strict C3 if direct bases were declared + // in an order that is inconsitent with the partial order determined by + // the subtype relationship. Our implementation of linearization is relaxed + // compared to C3 so that it is robust to such ordering issues. + // + // Note: This step takes quadratic time in the number of direct bases, but + // there's really no other way to easily detect these issues. + // + for(auto leftBase = directBaseFacets.getHead(); leftBase.getImpl(); leftBase = leftBase->next) + { + // Note: all of the direct base facets with a `Type` kind will + // precede all of those with `Extension` kind, so we can bail + // out of the outer loop as soon as we find a non-`Type` + // facet. + // + if(leftBase->kind != Facet::Kind::Type) + break; + auto leftBaseType = leftBase->origin.type; + + // For the inner loop we scan only the facets that appear *after* + // the `leftBase` in the list of direct bases. + // + for(auto rightBase = leftBase->next; rightBase.getImpl(); rightBase = rightBase->next) + { + if (rightBase->kind != Facet::Kind::Type) + break; + auto rightBaseType = rightBase->origin.type; + + if (visitor.isSubtype(leftBaseType, rightBaseType)) + { + // If a type earlier in the list of bases is a subtype of + // one later in the list, then the ordering is consistent + // with the linearization that will be produced, but it + // might represent a mistake on the programmer's part, + // since they listed a base type that is redundant. + // + // TODO: decide whether to diagnose this case. + } + else if (visitor.isSubtype(rightBaseType, leftBaseType)) + { + // If a type later in the list is a subtype of a type earlier + // in the list, then the declared list of bases is inconsistent + // with the ordering that will (indeed *must*) appear in the + // linearization we generate. + // + // If we end up implementing a strict version of the C3 algorithm, + // we would need to treat such situations as an error, or at least + // emit a warning and then remove the subtype from the list of + // bases. + // + // TODO: decide whether to diagnose this case. + } + } + } + + // Now that we've built up the list of direct bases and their + // respective linearizations, we can apply the core merge algorithm + // to those lists to produce the rest of the linearization for + // the declaration in question. + // + _mergeFacetLists(directBases, directBaseFacets, allFacets); + + InheritanceInfo info; + info.facets = allFacets; + return info; + } + + void SharedSemanticsContext::_mergeFacetLists(DirectBaseList bases, FacetList baseFacets, FacetList::Builder& ioMergedFacets) + { + // Our task here is to take the list of direct/declared `bases`, + // each of which holds a linearized list of `Facet`s, and produce + // a single linearized list of facets in `ioMergedFacets`. + // + // The `Facet`s in the lists referenced by `bases` are always + // relative to the base type/extension itself, and not to + // the type or declaration for which we are computing + // a linearization. + // + // The `baseFacets` list provides one `Facet` for each direct + // base that are relative to the type/declaration we are + // computing a linearization for. These facets will be used + // directly, instead of those from `bases`, where possible. + // + auto astBuilder = _getASTBuilder(); + auto& arena = astBuilder->getArena(); + for(;;) + { + // The basic logic here is that on each iteration we + // will look at the first item on each list in `bases` + // and pick one that we will append to the merged output + // (after removing it from the relevant input(s)). + + // If we have run out of lists that need merging, then we are done. + // + if (bases.isEmpty()) + break; + + // Otherwise, we will look at the remaining non-empty lists, + // and see if one of them starts with an facet that can + // be appended to our merged output. + // + // If multiple such facets are viable, we will always take + // the one from the earliest list in `bases`. Doing so favors + // the types that appear earlier in a list of bases. + // + Facet foundFacet; + DirectBaseInfo* foundBase = nullptr; + for (auto base : bases) + { + Facet headFacet = base->facets.getHead(); + + // If the head facet of the `base` list appears at a non-head + // position in any of the other lists, we cannot append this + // element without risking inverting the order of some facets + // relative to those other lists. + // + if (bases.doesAnyTailContainMatchFor(headFacet)) + continue; + + // Otherwise, we are safe to add the `headFacet` to our + // merged list, because it only ever appears as the head + // of one or more of the lists in `bases`. + // + foundFacet = headFacet; + foundBase = base; + break; + } + + if(!foundFacet) + { + // If we could not identify a facet that could be safely + // removed from any of the base lists, then it means that + // we must have a cycle in the ordering constraints implied + // by the `bases` lists. + // + // The simplest example of such a cycle would be if we + // had two lists, `A` and `B`, such that: + // + // A = { X, Y } + // B = { Y, X } + // + // In this case, producing output in the order `X, Y` *or* + // `Y, X` will always invalidate the ordering constraints + // implied by either `A` or `B`. + // + // In the C3 algorithm as published, such a situation is an + // error, and the algorithm fails to produce a linearization. + // The reason for this decision is that allowing this case + // means that a base type and a derived type could disagree + // on the relative priority of method overrides, and thus + // a subclass could possible break semantic assumptions of + // a superclass. + // + // In a more static language like Slang, it seems better to + // allow more flexible inheritance, *especially* when dealing + // with things like `interface`s and `extension`s, where the + // relative ordering of things will often be immaterial. + // + // In a case like this, we would like to arbitrarily pick + // one or the other of `X` and `Y`, and given our default + // policy to favor the earlier list in `bases` where possible, + // we would select `X` from `A`. + // + // One thing worth noting is that when a case like the above + // arises, it is not possible that `X <: Y` or `Y <: X`. + // If a subtype relationship existed between the two, then + // they would be consistently ordered in *both* lists. + // We thus do not have to worry about violating the most + // important requirement for a "reasonable" linearization. + // + foundBase = *bases.begin(); + foundFacet = foundBase->facets.getHead(); + + // Note: because we are grabbing a facet that might appear + // in a non-head position in one or more of our lists, + // we need to have a plan for what to do when we see + // that same facet come to the front of one of our lists + // later. + } + + // At this point we definitely have a facet we'd like to + // add to the output, whether it was found via the true + // C3 approach, or our relaxed rule above. + // + SLANG_ASSERT(foundFacet.getImpl()); + + // If the facet we want to append to the output is the same as the front-most + // facet on the list of bases, then we want to use that facet as-is (since we + // have already allocated storage for it). + // + // TODO: in cases where the strict C3 algorithm would fail, and we choose a + // `foundFacet` that is at a non-head position in at least some lists, it + // might be possible that we have a facet that matches ones of the `baseFacets`, + // but not the head one. We should confirm what happens in that case. + // + if(originsMatch(foundFacet, baseFacets.getHead())) + { + auto directBaseFacet = baseFacets.popHead(); + ioMergedFacets.add(directBaseFacet); + } + else + { + // This facet is seemingly *not* a facet that represents one of the direct + // bases for the type/declaration being processed. + // + // As such, we need to allocate a fresh facet to represent it in the + // linearization we are creating, since the `foundFacet` already belongs + // to the linearization of one of the bases, and shouldn't be repurposed. + // + auto indirectFacet = new(arena) Facet::Impl(); + + // We will initialize the fresh facet to a copy of the state of the + // `foundFacet`, albeit with a higher level of indirection. + // + // TODO: In principle we could search through all of the lists to + // find the one with a facet matching `foundFacet` with minimum + // indirection, so that our measure of indirection is always + // as small as possible for any given facet. + // + *indirectFacet = *(foundFacet.getImpl()); + indirectFacet->next = nullptr; + indirectFacet->directness = + Facet::Directness(Facet::DirectnessVal(indirectFacet->directness) + 1); + + // When using this facet for subtype tests, or when looking + // up member through this facet, we will need a witness + // to show that the self type of the declaration being + // linearized (the type being declared or extended) is a + // subtype of the type for this facet. + // + // We can construct the appropriate witness transitively, + // by noting that: + // + // * The self type is known to be a subtype of the direct + // base represented by `foundBase`, and the facet for + // that base stores a witness to that fact. + // + SubtypeWitness* selfIsSubtypeOfBase = foundBase->facetImpl.subtypeWitness; + // + // * The direct base type must be a subtype of the type + // for any facet found in its own linearization, and + // the `foundFacet` that came from the relevant base + // stores a witness to that fact. + // + SubtypeWitness* baseIsSubtypeOfFacet = foundFacet->subtypeWitness; + + auto selfIsSubtypeOfFacet = _getASTBuilder()->getTransitiveSubtypeWitness( + selfIsSubtypeOfBase, + baseIsSubtypeOfFacet); + + indirectFacet->subtypeWitness = selfIsSubtypeOfFacet; + + ioMergedFacets.add(indirectFacet); + } + + // We picked one `foundFacet` above to be added to the merged + // output list, and we now need to ensure that we won't ever + // emit a matching facet again. + // + // In the case of the strict/standard C3 algorithm, any facets + // matching `foundFacet` would need to appear at a head position + // in one of the base lists. As such, it is sufficient to run + // through the base lists, check for a match at the head of each, + // and remove any matching facets we find. + // + for (auto base : bases) + { + if (originsMatch(foundFacet, base->facets.getHead())) + { + base->facets.advanceHead(); + continue; + } + } + // + // Because we are not implementing the C3 algorithm strictly, + // we need a solution for the case where `foundFacet` is + // in a non-head position in one or more of the base lists. + // + // Proactively filtering `foundFacet` out of all of the lists + // is possible, but given that these are singly-linked lists + // we cannot easily filter them without either allocation + // or mutation. + // + // Instead, we will filter out facets that have already been + // added to the merged list as needed, when such facets come + // to the front of the relevant list. + // + for (auto base : bases) + { + for(;;) + { + // For each base list, we will check if its + // head facet is one that has already been + // emitted to the output. + // + // If the head facet has not been emitted + // already, we don't need to perform any + // filtering on the base list at this time. + // + auto head = base->facets.getHead(); + if (!ioMergedFacets.containsMatchFor(head)) + break; + + // Otherwise, we remove the head facet from + // the given base list and test again, unless + // the list is now empty. + // + base->facets.advanceHead(); + if (base->facets.isEmpty()) + break; + } + } + + // The filtering step might have led to one or more + // of the `bases` lists becomming empty. Our merge + // algorithm really only wants to consider non-empty + // lists, so we go ahead and remove the empty lists + // here. + // + bases.removeEmptyLists(); + + // At this point all of the lists have been appropriately filtered, + // and we are ready to circle back around again to the step + // where select a facet to add to the merged list. + } + + // At this point, all of the input lists in `bases` should be empty, + // and all of the facets in those lists should have found their way + // over to `ioMergedFacets`. + } + + // The mering algorithm needs to be able to test if two potentially-distinct + // `Facet`s represent the same underlying type or declaration. + // + bool originsMatch(Facet left, Facet right) + { + if (left.getImpl() == right.getImpl()) + return true; + if (!left.getImpl() || !right.getImpl()) + return false; + + // If both of the facets are non-null, and not + // identical, we check if their origins match, + // meaning that they represent the same type + // or declaration. + // + return left->origin == right->origin; + } + + bool operator==(Facet::Origin left, Facet::Origin right) + { + // If either facet represents a declaration, then + // the origins only match if they both represent + // the *same* declaration. + // + if (left.declRef.getDecl() || right.declRef.getDecl()) + { + return left.declRef.getDecl() + && right.declRef.getDecl() + && left.declRef.equals(right.declRef); + } + + // Otherwise, if they both represent types, then the + // origins match if they are the same type. + // + // Note: an `extension` facet will always have a non-null + // `declRef`, so there is no risk here of an `extension` + // and a type facet being matched by this step; they + // would always land in the case above. + // + if (left.type || right.type) + { + return left.type + && right.type + && left.type->equals(right.type); + } + + // TODO: The rules we are using for matching here + // would need to be revisited and overhauled significantly + // if we start supporting generic type declarations + // with covariant/contravariant type parameters. + // + // In such cases we would need to treat two facets as + // matching if their declarations or types are an exact + // matching modulo type arguments, and the relationship + // between pairwise type arguments is consistent with + // the variance of the corresponding parameter. + // + // E.g., we would need to treat facets for `IEnumerable<Derived>` + // and `IEnumerable<Base>` as matching, and ensure that a + // merged output list for a type/declaration could only + // include the more specific of the two (`IEnumerable<Derived>`). + + return false; + } + + // The remaining list-related operations that relate to the merging + // process are relatively simple to follow once the definition of + // matching is clear. + + bool SharedSemanticsContext::DirectBaseList::doesAnyTailContainMatchFor(Facet facet) const + { + for (auto base : *this) + { + if (base->facets.getTail().containsMatchFor(facet)) + return true; + } + return false; + } + + void SharedSemanticsContext::DirectBaseList::removeEmptyLists() + { + DirectBaseInfo** link = &_head; + while (auto base = *link) + { + if (base->facets.isEmpty()) + { + *link = base->next; + } + else + { + link = &base->next; + } + } + } + + bool FacetList::containsMatchFor(Facet facet) const + { + for (auto f : *this) + { + if (originsMatch(f, facet)) + return true; + } + return false; + } + + InheritanceInfo SharedSemanticsContext::_calcInheritanceInfo(Type* type) + { + // The majority of the interesting for for computing linearized + // inheritance information arises for `DeclRef`s, but we still + // need a way to compute the relevant information for types + // that might or might not be defined using `Decl`s. + + auto astBuilder = _getASTBuilder(); + auto& arena = astBuilder->getArena(); + if (auto declRefType = as<DeclRefType>(type)) + { + // The `DeclRef` case is the easy one, since we can + // bottleneck through the logic that gets shared between + // type and `extension` declarations. + // + return _getInheritanceInfo(declRefType->declRef, declRefType); + } + else if (auto conjunctionType = as<AndType>(type)) + { + // In this case, we have a type of the form `L & R`, + // such that it is a subtype of both `L` and `R`. + // + auto leftType = conjunctionType->left; + auto rightType = conjunctionType->right; + + // The linearized inheritance list for the conjunction + // must include all the facets from the lists for `L` + // and `R`, respectively. + // + auto leftInfo = getInheritanceInfo(leftType); + auto rightInfo = getInheritanceInfo(rightType); + + // We have a case of subtype witness that can show that + // `T : L` or `T : R` based on `T : L&R`. In this case, + // though, the type `T` is actually `L&R` itself, so + // we need to construct an identity witness for `L&R : L&R` + // to give it something to start from. + // + auto selfIsSelf = astBuilder->getTypeEqualityWitness(conjunctionType); + auto selfIsSubtypeOfLeft = _getASTBuilder()->getExtractFromConjunctionSubtypeWitness(type, leftType, selfIsSelf, 0); + auto selfIsSubtypeOfRight = _getASTBuilder()->getExtractFromConjunctionSubtypeWitness(type, rightType, selfIsSelf, 1); + + // We will set up to perform a merge between the facet + // lists for the two "bases" `L` and `R`. Note that the + // information we write into the `facetImpl` in each case + // is largely just for completeness and debugging, since + // we are *not* going to add those facets into a list + // of direct base facets to be merged. + // + DirectBaseInfo leftBaseInfo; + leftBaseInfo.facetImpl = FacetImpl( + Facet::Kind::Type, + Facet::Directness::Direct, + DeclRef<Decl>(), + leftType, + selfIsSubtypeOfLeft); + leftBaseInfo.facets = leftInfo.facets; + + DirectBaseInfo rightBaseInfo; + rightBaseInfo.facetImpl = FacetImpl( + Facet::Kind::Type, + Facet::Directness::Direct, + DeclRef<Decl>(), + rightType, + selfIsSubtypeOfRight); + rightBaseInfo.facets = rightInfo.facets; + + DirectBaseList::Builder directBases; + directBases.add(&leftBaseInfo); + directBases.add(&rightBaseInfo); + + // The merging step is then the same as for the more "standard" case, + // with the only detail that we are not passing in a list of facets + // to represent the directly-declared bases (since there are none; + // this is a structural rather than nominal type). + // + FacetList::Builder mergedFacets; + _mergeFacetLists(directBases, FacetList(), mergedFacets); + + InheritanceInfo info; + info.facets = mergedFacets; + return info; + } + else + { + // As a fallback, any type not covered by the above cases will + // get a trivial linearization that consists of a single facet + // corresponding to that type itself. + // + SemanticsVisitor visitor(this); + auto directFacet = new(arena) Facet::Impl( + Facet::Kind::Type, + Facet::Directness::Self, + DeclRef<Decl>(), + type, + visitor.createTypeEqualityWitness(type)); + + InheritanceInfo info; + info.facets = FacetList(directFacet); + return info; + } + } +} diff --git a/source/slang/slang-check-overload.cpp b/source/slang/slang-check-overload.cpp index 423d1f6bb..38856d7bf 100644 --- a/source/slang/slang-check-overload.cpp +++ b/source/slang/slang-check-overload.cpp @@ -537,6 +537,7 @@ namespace Slang { if(context.mode != OverloadResolveContext::Mode::JustTrying) { + subTypeWitness = tryGetSubtypeWitness(sub, sup); getSink()->diagnose(context.loc, Diagnostics::typeArgumentDoesNotConformToInterface, sub, sup); } return false; diff --git a/source/slang/slang-check-shader.cpp b/source/slang/slang-check-shader.cpp index 69e419f75..382abf081 100644 --- a/source/slang/slang-check-shader.cpp +++ b/source/slang/slang-check-shader.cpp @@ -1062,8 +1062,8 @@ namespace Slang auto interfaceType = getSup(getLinkage()->getASTBuilder(), DeclRef<GenericTypeConstraintDecl>(constraintDecl)); // Use our semantic-checking logic to search for a witness to the required conformance - auto witness = visitor.tryGetSubtypeWitness(argType, interfaceType); - if (!witness) + auto witness = visitor.isSubtype(argType, interfaceType); + if(!witness) { // If no witness was found, then we will be unable to satisfy // the conformances required. @@ -1094,7 +1094,7 @@ namespace Slang argType = getLinkage()->getASTBuilder()->getErrorType(); } - auto witness = visitor.tryGetSubtypeWitness(argType, interfaceType); + auto witness = visitor.isSubtype(argType, interfaceType); if (!witness) { // If no witness was found, then we will be unable to satisfy @@ -1220,7 +1220,7 @@ namespace Slang auto sub = getSub(astBuilder, constraintDeclRef); auto sup = getSup(astBuilder, constraintDeclRef); - auto subTypeWitness = visitor.tryGetSubtypeWitness(sub, sup); + auto subTypeWitness = visitor.isSubtype(sub, sup); if(subTypeWitness) { genericArgs.add(subTypeWitness); @@ -1264,7 +1264,7 @@ namespace Slang auto paramType = as<Type>(param.object); auto argType = as<Type>(specializationArg.val); - auto witness = visitor.tryGetSubtypeWitness(argType, paramType); + auto witness = visitor.isSubtype(argType, paramType); if (!witness) { // If no witness was found, then we will be unable to satisfy @@ -1414,7 +1414,7 @@ namespace Slang ExpandedSpecializationArg arg; arg.val = argType; - arg.witness = visitor.tryGetSubtypeWitness(argType, paramType); + arg.witness = visitor.isSubtype(argType, paramType); specializationArgs.add(arg); } diff --git a/source/slang/slang-compiler.cpp b/source/slang/slang-compiler.cpp index c1d7798e3..224e30fa1 100644 --- a/source/slang/slang-compiler.cpp +++ b/source/slang/slang-compiler.cpp @@ -281,12 +281,12 @@ namespace Slang } else if (auto conjunctionWitness = as<ConjunctionSubtypeWitness>(witness)) { - auto left = as<SubtypeWitness>(conjunctionWitness->leftWitness); - if (left) - addDepedencyFromWitness(left); - auto right = as<SubtypeWitness>(conjunctionWitness->rightWitness); - if (right) - addDepedencyFromWitness(right); + auto componentCount = conjunctionWitness->getComponentCount(); + for (Index i = 0; i < componentCount; ++i) + { + auto w = as<SubtypeWitness>(conjunctionWitness->getComponentWitness(i)); + if (w) addDepedencyFromWitness(w); + } } } diff --git a/source/slang/slang-ir-liveness.h b/source/slang/slang-ir-liveness.h index db3c7633f..54ac20e0d 100644 --- a/source/slang/slang-ir-liveness.h +++ b/source/slang/slang-ir-liveness.h @@ -186,4 +186,4 @@ struct LivenessUtil } -#endif // SLANG_IR_LIVENESS_H
\ No newline at end of file +#endif // SLANG_IR_LIVENESS_H diff --git a/source/slang/slang-lookup.cpp b/source/slang/slang-lookup.cpp index b16671efb..efc413e24 100644 --- a/source/slang/slang-lookup.cpp +++ b/source/slang/slang-lookup.cpp @@ -4,6 +4,12 @@ #include "../compiler-core/slang-name.h" #include "slang-check-impl.h" +// TODO(tfoley): The implementation of lookup still involves +// recursion over the structure of a type/declaration, but +// it should be possible for it to use the flattened/linearized +// inheritance information that is being computed in +// `slang-check-inheritance.cpp`. + namespace Slang { void ensureDecl(SemanticsVisitor* visitor, Decl* decl, DeclCheckState state); @@ -278,13 +284,14 @@ static SubtypeWitness* _makeSubtypeWitness( Type* superType, SubtypeWitness* midtoSuperWitness) { + SLANG_UNUSED(subType); + SLANG_UNUSED(superType); + if(subToMidWitness) { - TransitiveSubtypeWitness* transitiveWitness = astBuilder->create<TransitiveSubtypeWitness>(); - transitiveWitness->subToMid = subToMidWitness; - transitiveWitness->midToSup = midtoSuperWitness; - transitiveWitness->sub = subType; - transitiveWitness->sup = superType; + auto transitiveWitness = astBuilder->getTransitiveSubtypeWitness( + subToMidWitness, + midtoSuperWitness); return transitiveWitness; } else @@ -300,11 +307,10 @@ static SubtypeWitness* _makeSubtypeWitness( Type* superType, DeclRef<TypeConstraintDecl> midToSuperConstraint) { - DeclaredSubtypeWitness* midToSuperWitness = astBuilder->create<DeclaredSubtypeWitness>(); - midToSuperWitness->declRef = midToSuperConstraint; - midToSuperWitness->sub = subType; - midToSuperWitness->sup = superType; - return _makeSubtypeWitness(astBuilder, subType, subToMidWitness, superType, midToSuperWitness); + auto midToSuperWitness = astBuilder->getDeclaredSubtypeWitness( + subType, superType, midToSuperConstraint); + return _makeSubtypeWitness( + astBuilder, subType, subToMidWitness, superType, midToSuperWitness); } // Same as the above, but we are specializing a type instead of a decl-ref @@ -380,14 +386,6 @@ static void _lookUpMembersInSuperType( breadcrumb.val = leafIsSuperWitness; breadcrumb.prev = inBreadcrumbs; - // TODO: Need to consider case where this might recurse infinitely (e.g., - // if an inheritance clause does something like `Bad<T> : Bad<Bad<T>>`. - // - // TODO: The even simpler thing we need to worry about here is that if - // there is ever a "diamond" relationship in the inheritance hierarchy, - // we might end up seeing the same interface via different "paths" and - // we wouldn't want that to lead to overload-resolution failure. - // _lookUpMembersInSuperTypeImpl(astBuilder, name, leafType, superType, leafIsSuperWitness, request, ioResult, &breadcrumb); } @@ -663,36 +661,24 @@ static void _lookUpMembersInSuperTypeImpl( // // Effectively, we have a witness that `T : X & Y` and we // need to extract from it a witness that `T : X`. - // Fortunately, we have a class of subtype witness that does - // *precisely* this: - // - auto leafIsLeftWitness = astBuilder->create<ExtractFromConjunctionSubtypeWitness>(); - // - // Our witness will be to the fact that `leafType` is a subtype of `leftType` - // - leafIsLeftWitness->sub = leafType; - leafIsLeftWitness->sup = leftType; // - // The evidence for the subtype relationship will be a witness - // proving that `leafType : leftType & rightType`: // - leafIsLeftWitness->conjunctionWitness = leafIsSuperWitness; - // - // ... along with the index of the desired super-type in - // that conjunction. The index of `leftType` in `leftType & rightType` - // is zero. - // - leafIsLeftWitness->indexInConjunction = 0; + auto leafIsLeftWitness = astBuilder->getExtractFromConjunctionSubtypeWitness( + leafType, + leftType, + leafIsSuperWitness, + 0); + // The witness for the fact that `leafType : rightType` is the // same as for the left case, just with a different index into // the conjunction. // - auto leafIsRightWitness = astBuilder->create<ExtractFromConjunctionSubtypeWitness>(); - leafIsRightWitness->conjunctionWitness = leafIsSuperWitness; - leafIsRightWitness->indexInConjunction = 1; - leafIsRightWitness->sub = leafType; - leafIsRightWitness->sup = rightType; + auto leafIsRightWitness = astBuilder->getExtractFromConjunctionSubtypeWitness( + leafType, + rightType, + leafIsSuperWitness, + 1); // We then perform lookup on both sides of the conjunction, and // accumulate whatever items are found on either/both sides. diff --git a/source/slang/slang-lower-to-ir.cpp b/source/slang/slang-lower-to-ir.cpp index 7439c67f4..b941212ea 100644 --- a/source/slang/slang-lower-to-ir.cpp +++ b/source/slang/slang-lower-to-ir.cpp @@ -1862,15 +1862,21 @@ struct ValLoweringVisitor : ValVisitor<ValLoweringVisitor, LoweredValInfo, Lower LoweredValInfo visitConjunctionSubtypeWitness(ConjunctionSubtypeWitness* val) { - // A witness `T : L & R` for a conformance of `T` to a conjunction of - // types `L` and `R` will be lowered as a tuple of two witnesses: one - // for `T : L` and one for `T : R`. Luckily, those two conformances - // are exactly what the `ConjunctionSubtypeWitness` stores, so we just - // need to lower them individually and make a tuple. - // - auto left = lowerSimpleVal(context, val->leftWitness); - auto right = lowerSimpleVal(context, val->rightWitness); - return LoweredValInfo::simple(getBuilder()->emitMakeTuple(left, right)); + // A witness `W = X & Y & ...` will lower as a tuple of the sub-witnesses + // `X`, `Y`, etc. + // + // The AST representation of a conjunction of witnesses matches this + // tuple-like encoding very closely, so we can simply lower each of + // the component witnesses to produce our result. + // + List<IRInst*> componentWitnesses; + auto componentCount = val->getComponentCount(); + for (Index i = 0; i < componentCount; ++i) + { + auto componentWitness = lowerSimpleVal(context, val->getComponentWitness(i)); + componentWitnesses.add(componentWitness); + } + return LoweredValInfo::simple(getBuilder()->emitMakeTuple(componentWitnesses)); } LoweredValInfo visitExtractFromConjunctionSubtypeWitness(ExtractFromConjunctionSubtypeWitness* val) diff --git a/source/slang/slang-syntax.cpp b/source/slang/slang-syntax.cpp index fbb30e4eb..4033dfff1 100644 --- a/source/slang/slang-syntax.cpp +++ b/source/slang/slang-syntax.cpp @@ -366,10 +366,11 @@ Index getFilterCountImpl(const ReflectClassInfo& clsInfo, MemberFilterStyle filt { if (auto conjunctionTypeWitness = as<ConjunctionSubtypeWitness>(extractFromConjunctionTypeWitness->conjunctionWitness)) { - if (extractFromConjunctionTypeWitness->indexInConjunction == 0) - return tryLookUpRequirementWitness(astBuilder, as<SubtypeWitness>(conjunctionTypeWitness->leftWitness), requirementKey); - else - return tryLookUpRequirementWitness(astBuilder, as<SubtypeWitness>(conjunctionTypeWitness->rightWitness), requirementKey); + auto componentWitness = as<SubtypeWitness>( + conjunctionTypeWitness->getComponentWitness( + extractFromConjunctionTypeWitness->indexInConjunction)); + + return tryLookUpRequirementWitness(astBuilder, componentWitness, requirementKey); } } // TODO: should handle the transitive case here too diff --git a/source/slang/slang.cpp b/source/slang/slang.cpp index 246662909..28227b39b 100644 --- a/source/slang/slang.cpp +++ b/source/slang/slang.cpp @@ -1320,7 +1320,7 @@ SLANG_NO_THROW SlangResult SLANG_MCALL Linkage::createTypeConformanceComponentTy SharedSemanticsContext sharedSemanticsContext(this, nullptr, &sink); SemanticsVisitor visitor(&sharedSemanticsContext); auto witness = - visitor.tryGetSubtypeWitness((Slang::Type*)type, (Slang::Type*)interfaceType); + visitor.isSubtype((Slang::Type*)type, (Slang::Type*)interfaceType); if (auto subtypeWitness = as<SubtypeWitness>(witness)) { result = new TypeConformance(this, subtypeWitness, conformanceIdOverride, &sink); diff --git a/source/slang/slang.natvis b/source/slang/slang.natvis index 59f2007ce..1db7b9bce 100644 --- a/source/slang/slang.natvis +++ b/source/slang/slang.natvis @@ -10,9 +10,10 @@ </Expand> </Type> <Type Name="Slang::DeclRef<*>"> - <SmartPointer Usage="Minimal">decl ? ($T1*)(decl) : ($T1*)0</SmartPointer> - <DisplayString Condition="decl == 0">DeclRef nullptr</DisplayString> - <DisplayString Condition="decl != 0">{(*(*(Slang::DeclRefBase*)this).decl).nameAndLoc}</DisplayString> + <SmartPointer Usage="Minimal">declRefBase ? ($T1*)(declRefBase->decl) : ($T1*)0</SmartPointer> + <DisplayString Condition="declRefBase == 0">DeclRef nullptr</DisplayString> + <DisplayString Condition="declRefBase != 0">{*declRefBase}</DisplayString> + <!-- <Expand> <ExpandedItem>decl ? ($T1*)(decl) : ($T1*)0</ExpandedItem> <Synthetic Name="[Substitutions]"> @@ -25,23 +26,27 @@ </Expand> </Synthetic> </Expand> + --> </Type> <Type Name="Slang::DeclRefBase"> - <SmartPointer Usage="Minimal">decl</SmartPointer> - <DisplayString Condition="decl == 0">DeclRefBase nullptr</DisplayString> - <DisplayString Condition="decl != 0">{(*(*(Slang::DeclRefBase*)this).decl).nameAndLoc}</DisplayString> - <Expand> - <ExpandedItem>decl</ExpandedItem> - <Synthetic Name="[Substitutions]"> - <Expand> - <LinkedListItems> - <HeadPointer>substitutions.substitutions</HeadPointer> - <NextPointer>outer</NextPointer> - <ValueNode>this</ValueNode> - </LinkedListItems> - </Expand> - </Synthetic> - </Expand> + <SmartPointer Usage="Minimal">decl</SmartPointer> + <DisplayString Condition="decl != 0 && substitutions != 0">{*decl}{*substitutions}</DisplayString> + <DisplayString Condition="decl != 0">{*decl}</DisplayString> + <DisplayString Condition="decl == 0">DeclRefBase nullptr</DisplayString> + <!-- + <Expand> + <ExpandedItem>decl</ExpandedItem> + <Synthetic Name="[Substitutions]"> + <Expand> + <LinkedListItems> + <HeadPointer>substitutions.substitutions</HeadPointer> + <NextPointer>outer</NextPointer> + <ValueNode>this</ValueNode> + </LinkedListItems> + </Expand> + </Synthetic> + </Expand> + --> </Type> <Type Name="Slang::GenericSubstitution"> <DisplayString>GenSubst {(*genericDecl).nameAndLoc}</DisplayString> @@ -191,7 +196,7 @@ </Type> <Type Name="Slang::Expr" Inheritable="false"> - <DisplayString>{astNodeType}</DisplayString> + <DisplayString>{astNodeType,en}</DisplayString> <Expand> <ExpandedItem Condition="astNodeType == Slang::ASTNodeType::DeclRefExpr">(Slang::DeclRefExpr*)&astNodeType</ExpandedItem> <ExpandedItem Condition="astNodeType == Slang::ASTNodeType::VarExpr">(Slang::VarExpr*)&astNodeType</ExpandedItem> @@ -246,7 +251,7 @@ </Expand> </Type> <Type Name="Slang::Stmt" Inheritable="false"> - <DisplayString>{astNodeType}</DisplayString> + <DisplayString>{astNodeType,en}</DisplayString> <Expand> <ExpandedItem Condition="astNodeType == Slang::ASTNodeType::ScopeStmt">(Slang::ScopeStmt*)&astNodeType</ExpandedItem> <ExpandedItem Condition="astNodeType == Slang::ASTNodeType::BlockStmt">(Slang::BlockStmt*)&astNodeType</ExpandedItem> @@ -281,8 +286,8 @@ <DisplayString>{text}</DisplayString> </Type> <Type Name="Slang::Decl" Inheritable="false"> - <DisplayString Condition="nameAndLoc.name!=0">{nameAndLoc.name->text}: {astNodeType}</DisplayString> - <DisplayString Condition="nameAndLoc.name==0">{astNodeType}</DisplayString> + <DisplayString Condition="nameAndLoc.name!=0">{nameAndLoc.name->text}</DisplayString> + <DisplayString Condition="nameAndLoc.name==0">{astNodeType,en}</DisplayString> <Expand> <Item Name="[Name]" Condition="nameAndLoc.name!=0">nameAndLoc.name->text</Item> <Item Name="[Parent]">parentDecl</Item> @@ -332,7 +337,7 @@ </Type> <Type Name="Slang::DeclBase" Inheritable="false"> - <DisplayString>{astNodeType}</DisplayString> + <DisplayString>{astNodeType,en}</DisplayString> <Expand> <ExpandedItem Condition="astNodeType == Slang::ASTNodeType::ContainerDecl">(Slang::ContainerDecl*)&astNodeType</ExpandedItem> <ExpandedItem Condition="astNodeType == Slang::ASTNodeType::ExtensionDecl">(Slang::ExtensionDecl*)&astNodeType</ExpandedItem> @@ -379,8 +384,9 @@ </Type> <Type Name="Slang::Type" Inheritable="false"> - <DisplayString>{astNodeType}</DisplayString> - <Expand> + <DisplayString Condition="astNodeType == Slang::ASTNodeType::DeclRefType">{((Slang::DeclRefType*)&astNodeType)->declRef}</DisplayString> + <DisplayString>{astNodeType,en}</DisplayString> + <Expand> <ExpandedItem Condition="astNodeType == Slang::ASTNodeType::OverloadGroupType">(Slang::OverloadGroupType*)&astNodeType</ExpandedItem> <ExpandedItem Condition="astNodeType == Slang::ASTNodeType::InitializerListType">(Slang::InitializerListType*)&astNodeType</ExpandedItem> <ExpandedItem Condition="astNodeType == Slang::ASTNodeType::ErrorType">(Slang::ErrorType*)&astNodeType</ExpandedItem> @@ -420,7 +426,7 @@ <ExpandedItem Condition="astNodeType == Slang::ASTNodeType::HLSLPointStreamType">(Slang::HLSLPointStreamType*)&astNodeType</ExpandedItem> <ExpandedItem Condition="astNodeType == Slang::ASTNodeType::HLSLLineStreamType">(Slang::HLSLLineStreamType*)&astNodeType</ExpandedItem> <ExpandedItem Condition="astNodeType == Slang::ASTNodeType::HLSLTriangleStreamType">(Slang::HLSLTriangleStreamType*)&astNodeType</ExpandedItem> - <ExpandedItem Condition="astNodeType == Slang::ASTNodeType::MeshOutputType">(Slang::HLSLMeshOutputType*)&astNodeType</ExpandedItem> + <ExpandedItem Condition="astNodeType == Slang::ASTNodeType::MeshOutputType">(Slang::MeshOutputType*)&astNodeType</ExpandedItem> <ExpandedItem Condition="astNodeType == Slang::ASTNodeType::VerticesType">(Slang::VerticesType*)&astNodeType</ExpandedItem> <ExpandedItem Condition="astNodeType == Slang::ASTNodeType::IndicesType">(Slang::IndicesType*)&astNodeType</ExpandedItem> <ExpandedItem Condition="astNodeType == Slang::ASTNodeType::PrimitivesType">(Slang::PrimitivesType*)&astNodeType</ExpandedItem> @@ -462,16 +468,26 @@ <Item Name="[Type]">(Slang::Type*)this,nd</Item> </Expand> </Type> - <Type Name="Slang::Substitutions" Inheritable="false"> - <DisplayString>{astNodeType}</DisplayString> + <DisplayString Condition="astNodeType == Slang::ASTNodeType::GenericSubstitution">{*(Slang::GenericSubstitution*)&astNodeType}</DisplayString> + <DisplayString Condition="astNodeType == Slang::ASTNodeType::ThisTypeSubstitution">{*(Slang::ThisTypeSubstitution*)&astNodeType}</DisplayString> + <DisplayString>{astNodeType,en}</DisplayString> + <DisplayString>{astNodeType,en}</DisplayString> <Expand> <ExpandedItem Condition="astNodeType == Slang::ASTNodeType::GenericSubstitution">(Slang::GenericSubstitution*)&astNodeType</ExpandedItem> <ExpandedItem Condition="astNodeType == Slang::ASTNodeType::ThisTypeSubstitution">(Slang::ThisTypeSubstitution*)&astNodeType</ExpandedItem> </Expand> </Type> + <Type Name="Slang::GenericSubstitution" Inheritable="false"> + <DisplayString Condition="outer != 0"><{args}>{*outer}</DisplayString> + <DisplayString><{args}></DisplayString> + </Type> + <Type Name="Slang::ThisTypeSubstitution" Inheritable="false"> + <DisplayString Condition="outer != 0">{*outer}[This=={witness->sub,na}]</DisplayString> + <DisplayString>[{witness->sup,na}.This: {witness->sub,na}]</DisplayString> + </Type> <Type Name="Slang::SubstitutionSet"> - <DisplayString>{astNodeType}</DisplayString> + <DisplayString>{astNodeType,en}</DisplayString> <Expand> <LinkedListItems> <HeadPointer>substitutions</HeadPointer> @@ -481,13 +497,13 @@ </Expand> </Type> <Type Name="Slang::AggTypeDecl"> - <DisplayString>{nameAndLoc.name}: {astNodeType}</DisplayString> + <DisplayString>{astNodeType}({nameAndLoc.name})</DisplayString> <Expand> <Item Name="[Members]">members</Item> </Expand> </Type> <Type Name="Slang::Val" Inheritable="false"> - <DisplayString>{astNodeType}</DisplayString> + <DisplayString>{astNodeType,en}</DisplayString> <Expand> <ExpandedItem Condition="astNodeType == Slang::ASTNodeType::ConstantIntVal">(Slang::ConstantIntVal*)&astNodeType</ExpandedItem> <ExpandedItem Condition="astNodeType == Slang::ASTNodeType::PolynomialIntVal">(Slang::PolynomialIntVal*)&astNodeType</ExpandedItem> @@ -569,4 +585,36 @@ <ExpandedItem Condition="astNodeType == Slang::ASTNodeType::ModifiedType">(Slang::ModifiedType*)&astNodeType</ExpandedItem> </Expand> </Type> + <Type Name="Slang::Facet"> + <SmartPointer Usage="Minimal">_impl</SmartPointer> + <DisplayString Condition="_impl == 0">nullptr</DisplayString> + <DisplayString Condition="_impl != 0">{_impl}</DisplayString> + </Type> + <Type Name="Slang::FacetList"> + <DisplayString Condition="_head == 0">empty</DisplayString> + <Expand> + <LinkedListItems> + <HeadPointer>_head._impl != 0 ? &_head : 0</HeadPointer> + <NextPointer>_impl->next._impl != 0 ? &_impl->next : 0</NextPointer> + <ValueNode>*this</ValueNode> + </LinkedListItems> + </Expand> + </Type> + <Type Name="Slang::SharedSemanticsContext::DirectBaseList"> + <DisplayString Condition="_head == 0">empty</DisplayString> + <Expand> + <LinkedListItems> + <HeadPointer>_head != 0 ? _head : 0</HeadPointer> + <NextPointer>next != 0 ? next : 0</NextPointer> + <ValueNode>*this</ValueNode> + </LinkedListItems> + </Expand> + </Type> + <Type Name="Slang::SubtypeWitness"> + <DisplayString Condition="astNodeType == Slang::ASTNodeType::TypeEqualityWitness">{*(Slang::TypeEqualityWitness*)this}</DisplayString> + <DisplayString>{sub,na} <: {sup,na}</DisplayString> + </Type> + <Type Name="Slang::TypeEqualityWitness"> + <DisplayString>{sub,na} == {sup,na}</DisplayString> + </Type> </AutoVisualizer> |