From d1c38523d4bfbb6672baca9973013538b549bfae Mon Sep 17 00:00:00 2001 From: Tim Foley Date: Fri, 22 Dec 2017 12:09:26 -0800 Subject: Support for transitive subtype witnesses (#331) * Change stdlib `saturate` to explicitly specialize `clamp` This exposes issue #329, and so gives us an easy way to see if transitive subtype witnesses have been implemented correctly. * Fixup: invoke correct `clamp` overloads When switching the `clamp` calls in the stdlib definition of `saturate` I made two big mistakes: 1. I was passing in `` in all cases, instead of, e.g., `>` in the vector case 2. Of course, the overloads don't actually take `>` for the vector case, because `vector` is not a `__BuiltinArithmeticType` (`T` is), so instead it should be `clamp(...)`. The issue behind (2) is that we don't support "conditional conformances," which would be a way to say that when `T : __BuiltinArithmeticType` then `vector : __BuiltinArithmeticType`. That would be a great long-term wish-list feature, but not something I can see us adding in a hurry. Anyway the fix here is the simple one: change the vector/matrix call sites to invoke the correct overload in each case. * Add a notion of transitive subtype witnesses There are two pieces here: 1. Add the `TransitiveSubtypeWitness` class. This is a witness that `A : C` that works by storing nested subtype witnesses that show that `A : B` and `B : C` for some intermediate type `B`. All the basic `Val` operations are easy enough to define on this. - The one gotcha case is whether we can ever simplify away a `TransitiveSubtypeWitness` as part of substitution. That is, if we end up substituting so that both `A` and `B` end up as the same type, then we really just need the `B : C` sub-part. Stuff like that is left as future work. 2. Make the logic in `check.cpp` that constructs subtype witnesses based on found inheritance and constraint declarations able to build up transitive chains. Most of the required infrastructure was already there (the search process maintains a trail of "breadcrumbs" that represent all the steps getting from `A : B` to `B : C` to `C : D` ...). This change does *not* deal with the required changes in the IR to take advantage of transitive witnesses. --- source/slang/syntax.cpp | 78 +++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 78 insertions(+) (limited to 'source/slang/syntax.cpp') diff --git a/source/slang/syntax.cpp b/source/slang/syntax.cpp index dd08fa2b1..070362ddf 100644 --- a/source/slang/syntax.cpp +++ b/source/slang/syntax.cpp @@ -1741,6 +1741,84 @@ void Type::accept(IValVisitor* visitor, void* extra) return hash; } + // TransitiveSubtypeWitness + + bool TransitiveSubtypeWitness::EqualsVal(Val* val) + { + auto otherWitness = dynamic_cast(val); + if(!otherWitness) + return false; + + return sub->Equals(otherWitness->sub) + && sup->Equals(otherWitness->sup) + && subToMid->EqualsVal(otherWitness->subToMid) + && midToSup->EqualsVal(otherWitness->midToSup); + } + + RefPtr TransitiveSubtypeWitness::SubstituteImpl(Substitutions* subst, int * ioDiff) + { + int diff = 0; + + RefPtr substSub = sub->SubstituteImpl(subst, &diff).As(); + RefPtr substSup = sup->SubstituteImpl(subst, &diff).As(); + RefPtr substSubToMid = subToMid->SubstituteImpl(subst, &diff).As(); + RefPtr substMidToSup = midToSup->SubstituteImpl(subst, &diff).As(); + + // If nothing changed, then we can bail out early. + if (!diff) + return this; + + // Something changes, so let the caller know. + (*ioDiff)++; + + // TODO: are there cases where we can simplify? + // + // 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. + RefPtr result = new TransitiveSubtypeWitness(); + result->sub = substSub; + result->sup = substSup; + result->subToMid = substSubToMid; + result->midToSup = substMidToSup; + return result; + } + + String TransitiveSubtypeWitness::ToString() + { + // Note: we only print the constituent + // witnesses, and rely on them to print + // the starting and ending types. + StringBuilder sb; + sb << "TransitiveSubtypeWitness("; + sb << this->subToMid->ToString(); + sb << ", "; + sb << this->midToSup->ToString(); + sb << ")"; + return sb.ProduceString(); + } + + int TransitiveSubtypeWitness::GetHashCode() + { + auto hash = sub->GetHashCode(); + hash = combineHash(hash, sup->GetHashCode()); + hash = combineHash(hash, subToMid->GetHashCode()); + hash = combineHash(hash, midToSup->GetHashCode()); + return hash; + } + // IRProxyVal bool IRProxyVal::EqualsVal(Val* val) -- cgit v1.2.3