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.

1 files changed, 57 insertions, 18 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))