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 `<T>` in all cases, instead of, e.g., `<vector<T,N>>` in the vector case

2. Of course, the overloads don't actually take `<vector<T,N>>` for the vector case, because `vector<T,N>` is not a `__BuiltinArithmeticType` (`T` is), so instead it should be `clamp<T,N>(...)`.

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<T,N> : __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.

5 files changed, 156 insertions, 24 deletions

diff --git a/source/slang/check.cpp b/source/slang/check.cpp
index b981fb778..6a15fb86c 100644
--- a/source/slang/check.cpp
+++ b/source/slang/check.cpp
@@ -3678,9 +3678,24 @@ namespace Slang
         struct TypeWitnessBreadcrumb
         {
             TypeWitnessBreadcrumb*  prev;
+
+            RefPtr<Type>            sub;
+            RefPtr<Type>            sup;
             DeclRef<Decl>           declRef;
         };
 
+        // Crete a subtype witness based on the declared relationship
+        // found in a single breadcrumb
+        RefPtr<SubtypeWitness> createSimplSubtypeWitness(
+            TypeWitnessBreadcrumb*  breadcrumb)
+        {
+            RefPtr<DeclaredSubtypeWitness> witness = new DeclaredSubtypeWitness();
+            witness->sub = breadcrumb->sub;
+            witness->sup = breadcrumb->sup;
+            witness->declRef = breadcrumb->declRef;
+            return witness;
+        }
+
         RefPtr<Val> createTypeWitness(
             RefPtr<Type>            type,
             DeclRef<InterfaceDecl>  interfaceDeclRef,
@@ -3696,29 +3711,46 @@ namespace Slang
                 UNREACHABLE_RETURN(nullptr);
             }
 
-            auto breadcrumbs = inBreadcrumbs;
+            // 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 are going to walk the list and build up a suitable
+            // subtype witness.
+            auto bb = inBreadcrumbs;
+
+            // Create a witness for the last step in the chain
+            RefPtr<SubtypeWitness> witness = createSimplSubtypeWitness(bb);
+            bb = bb->prev;
 
-            auto bb = breadcrumbs;
-            breadcrumbs = breadcrumbs->prev;
+            // Now, as long as we have more entries to deal with,
+            // we'll be in a situation like:
+            //
+            //      ... (B : C) <witness>
+            //
+            // and we want to wrap up one more link in our chain.
 
-            if(breadcrumbs)
+            while (bb)
             {
-                // There are multiple steps in the proof, so
-                // we need a transitive witness to show that
-                // because `A : B` and `B : C` then `A : C`
-                //
-                SLANG_UNEXPECTED("transitive type witness");
-                UNREACHABLE_RETURN(nullptr);
-            }
+                // Create simple witness for the step in the chain
+                RefPtr<SubtypeWitness> link = createSimplSubtypeWitness(bb);
 
-            // Simple case: we have a single declaration
-            // that shows that `type` conforms to `interfaceDeclRef`.
-            //
+                // Now join the link onto the existing chain represented
+                // by `witness`.
+                RefPtr<TransitiveSubtypeWitness> transitiveWitness = new TransitiveSubtypeWitness();
+                transitiveWitness->sub = link->sub;
+                transitiveWitness->sup = witness->sup;
+                transitiveWitness->subToMid = link;
+                transitiveWitness->midToSup = witness;
+
+                witness = transitiveWitness;
+                bb = bb->prev;
+            }
 
-            RefPtr<DeclaredSubtypeWitness> witness = new DeclaredSubtypeWitness();
-            witness->sub = type;
-            witness->sup = DeclRefType::Create(getSession(), interfaceDeclRef);
-            witness->declRef = bb->declRef;
             return witness;
         }
 
@@ -3772,6 +3804,9 @@ namespace Slang
                         // the inheritance declaration.
                         TypeWitnessBreadcrumb breadcrumb;
                         breadcrumb.prev = inBreadcrumbs;
+
+                        breadcrumb.sub = type;
+                        breadcrumb.sup = inheritedType;
                         breadcrumb.declRef = inheritanceDeclRef;
 
                         if(doesTypeConformToInterfaceImpl(originalType, inheritedType, interfaceDeclRef, outWitness, &breadcrumb))
@@ -3786,6 +3821,8 @@ namespace Slang
                         auto inheritedType = GetSup(genConstraintDeclRef);
                         TypeWitnessBreadcrumb breadcrumb;
                         breadcrumb.prev = inBreadcrumbs;
+                        breadcrumb.sub = type;
+                        breadcrumb.sup = inheritedType;
                         breadcrumb.declRef = genConstraintDeclRef;
                         if (doesTypeConformToInterfaceImpl(originalType, inheritedType, interfaceDeclRef, outWitness, &breadcrumb))
                         {
@@ -3818,6 +3855,8 @@ namespace Slang
 
                         TypeWitnessBreadcrumb breadcrumb;
                         breadcrumb.prev = inBreadcrumbs;
+                        breadcrumb.sub = sub;
+                        breadcrumb.sup = sup;
                         breadcrumb.declRef = constraintDeclRef;
 
                         if(doesTypeConformToInterfaceImpl(originalType, sup, interfaceDeclRef, outWitness, &breadcrumb))
diff --git a/source/slang/hlsl.meta.slang b/source/slang/hlsl.meta.slang
index 09cf731b5..f63fd12df 100644
--- a/source/slang/hlsl.meta.slang
+++ b/source/slang/hlsl.meta.slang
@@ -824,14 +824,14 @@ __generic<T : __BuiltinFloatingPointType>
 __specialized_for_target(glsl)
 T saturate(T x)
 {
-    return clamp(x, T(0), T(1));
+    return clamp<T>(x, T(0), T(1));
 }
 
 __generic<T : __BuiltinFloatingPointType, let N : int>
 __specialized_for_target(glsl)
 vector<T,N> saturate(vector<T,N> x)
 {
-    return clamp(x,
+    return clamp<T,N>(x,
         vector<T,N>(T(0)),
         vector<T,N>(T(1)));
 }
@@ -846,7 +846,7 @@ __generic<T : __BuiltinFloatingPointType, let N : int, let M : int>
 __specialized_for_target(glsl)
 matrix<T,N,M> saturate(matrix<T,N,M> x)
 {
-    return clamp(x,
+    return clamp<T,N,M>(x,
         __scalarToMatrix<T,N,M>(T(0)),
         __scalarToMatrix<T,N,M>(T(1)));
 }
diff --git a/source/slang/hlsl.meta.slang.h b/source/slang/hlsl.meta.slang.h
index acaef8fbd..921c361bd 100644
--- a/source/slang/hlsl.meta.slang.h
+++ b/source/slang/hlsl.meta.slang.h
@@ -826,14 +826,14 @@ sb << "__generic<T : __BuiltinFloatingPointType>\n";
 sb << "__specialized_for_target(glsl)\n";
 sb << "T saturate(T x)\n";
 sb << "{\n";
-sb << "    return clamp(x, T(0), T(1));\n";
+sb << "    return clamp<T>(x, T(0), T(1));\n";
 sb << "}\n";
 sb << "\n";
 sb << "__generic<T : __BuiltinFloatingPointType, let N : int>\n";
 sb << "__specialized_for_target(glsl)\n";
 sb << "vector<T,N> saturate(vector<T,N> x)\n";
 sb << "{\n";
-sb << "    return clamp(x,\n";
+sb << "    return clamp<T,N>(x,\n";
 sb << "        vector<T,N>(T(0)),\n";
 sb << "        vector<T,N>(T(1)));\n";
 sb << "}\n";
@@ -848,7 +848,7 @@ sb << "__generic<T : __BuiltinFloatingPointType, let N : int, let M : int>\n";
 sb << "__specialized_for_target(glsl)\n";
 sb << "matrix<T,N,M> saturate(matrix<T,N,M> x)\n";
 sb << "{\n";
-sb << "    return clamp(x,\n";
+sb << "    return clamp<T,N,M>(x,\n";
 sb << "        __scalarToMatrix<T,N,M>(T(0)),\n";
 sb << "        __scalarToMatrix<T,N,M>(T(1)));\n";
 sb << "}\n";
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<TransitiveSubtypeWitness*>(val);
+        if(!otherWitness)
+            return false;
+
+        return sub->Equals(otherWitness->sub)
+            && sup->Equals(otherWitness->sup)
+            && subToMid->EqualsVal(otherWitness->subToMid)
+            && midToSup->EqualsVal(otherWitness->midToSup);
+    }
+
+    RefPtr<Val> TransitiveSubtypeWitness::SubstituteImpl(Substitutions* subst, int * ioDiff)
+    {
+        int diff = 0;
+
+        RefPtr<Type> substSub = sub->SubstituteImpl(subst, &diff).As<Type>();
+        RefPtr<Type> substSup = sup->SubstituteImpl(subst, &diff).As<Type>();
+        RefPtr<SubtypeWitness> substSubToMid = subToMid->SubstituteImpl(subst, &diff).As<SubtypeWitness>();
+        RefPtr<SubtypeWitness> substMidToSup = midToSup->SubstituteImpl(subst, &diff).As<SubtypeWitness>();
+
+        // 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<TransitiveSubtypeWitness> 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)
diff --git a/source/slang/val-defs.h b/source/slang/val-defs.h
index 5a370d34a..f3cdf52a2 100644
--- a/source/slang/val-defs.h
+++ b/source/slang/val-defs.h
@@ -99,6 +99,21 @@ RAW(
 )
 END_SYNTAX_CLASS()
 
+// A witness that `sub : sup` because `sub : mid` and `mid : sup`
+SYNTAX_CLASS(TransitiveSubtypeWitness, SubtypeWitness)
+    // Witness that `sub : mid`
+    FIELD(RefPtr<SubtypeWitness>, subToMid);
+
+    // Witness that `mid : sup`
+    FIELD(RefPtr<SubtypeWitness>, midToSup);
+RAW(
+    virtual bool EqualsVal(Val* val) override;
+    virtual String ToString() override;
+    virtual int GetHashCode() override;
+    virtual RefPtr<Val> SubstituteImpl(Substitutions * subst, int * ioDiff) override;
+)
+END_SYNTAX_CLASS()
+
 // A value that is used as a proxy when we need to
 // put an IR-level value into AST types
 SYNTAX_CLASS(IRProxyVal, Val)