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, 15 insertions, 0 deletions

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)