First steps toward inheritance for struct types (#1366)

* First steps toward inheritance for struct types

This change adds the ability for a `struct` type to declare a base type that is another `struct`:

```hlsl
struct Base
{
    int baseMember;
}

struct Derived : Base
{
    int derivedMember;
}
```

The semantics of the feature are that code like the above desugars into code like:

```hlsl
struct Base
{
    int baseMember;
}

struct Derived
{
    Base _base;
    int derivedMember;
}
```

At points where a member from the base type is being projected out, or the value is being implicitly cast to the base type, the compiler transforms the code to reference the implicitly-generated `_base` member. That means code like this:

```hlsl
void f(Base b);
...

Derived d = ...;

int x = d.baseMember;

f(d);
```

gets transformed into a form like this:

```hlsl
void f(Base b);
...

Derived d = ...;

int x = d._base.baseMember;

f(d._base);
```

Note that as a result of this choice, the behavior when passing a `Derived` value to a function that expects a `Base` (including to inherited member functions) is that of "object shearing" from the C++ world: the called function can only "see" the `Base` part of the argument, and any operations performed on it will behave as if the value was indeed a `Base`. There is no polymorphism going on because Slang doesn't currently have `virtual` methods.

In an attempt to work toward inheritance being a robust feature, this change adds a bunch of more detailed logic for checking the bases of various declarations:

* An `interface` declaration is only allowed to inherit from other `interface`s
* An `extension` declaration can only introduce inheritance from `interface`s
* A `struct` declaration can only inherit from at most one other `struct`, and that `struct` must be the first entry in the list of bases

This change also adds a mechanism to control whether a `struct` or `interface` in one module can inherit from a `struct` or `interface` declared in another module:

* If the base declaration is marked `[open]`, then the inheritance is allowed
* If the base declaration is marked `[sealed]`, then the inheritance is allowed
* If it is not marked otherwise, a `struct` is implicitly `[sealed]`
* If it is not marked otherwise, an `interface` is implicitly `[open]`

These seem like reasonable defaults. In order to safeguard the standard library a bit, the interfaces for builtin types have been marked `[sealed]` to make sure that a user cannot declare a `struct` and then mark it as a `BuiltinFloatingPointType`. This step should bring us a bit closer to being able to document and expose these interfaces for built-in types so that users can write code that is generic over them.

There are some big caveats with this work, such that it really only represents a stepping-stone toward a usable inheritance feature. The most important caveats are:

* If a `Derived` type tries to conform to an interface, such that one or more interface requirements are satisfied with members inherited from the `Base` type, that is likely to cause a crash or incorrect code generation.

* If a `Derived` type tries to inherit from a `Base` type that conforms to one or more interfaces, the witness table generated for the conformance of `Derived` to that interface is likely to lead to a crash or incorrect code generation.

It is clear that solving both of those issues will be necessary before we can really promote `struct` inheritance as a feature for users to try out.

* fixup: trying to appease clang error

* fixups: review feedback

1 files changed, 47 insertions, 13 deletions

diff --git a/source/slang/slang-check-impl.h b/source/slang/slang-check-impl.h
index 42edb5df7..c316dd820 100644
--- a/source/slang/slang-check-impl.h
+++ b/source/slang/slang-check-impl.h
@@ -645,7 +645,7 @@ namespace Slang
             /// which packages up the value, its type, and the witness
             /// of its conformance to the interface.
             ///
-        RefPtr<Expr> createCastToInterfaceExpr(
+        RefPtr<Expr> createCastToSuperTypeExpr(
             RefPtr<Type>    toType,
             RefPtr<Expr>    fromExpr,
             RefPtr<Val>     witness);
@@ -924,9 +924,15 @@ namespace Slang
         RefPtr<DeclaredSubtypeWitness> createSimpleSubtypeWitness(
             TypeWitnessBreadcrumb*  breadcrumb);
 
+            /// Create a withness 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.
+            ///
         RefPtr<Val> createTypeWitness(
-            RefPtr<Type>            type,
-            DeclRef<InterfaceDecl>  interfaceDeclRef,
+            RefPtr<Type>            subType,
+            DeclRef<AggTypeDecl>    superTypeDeclRef,
             TypeWitnessBreadcrumb*  inBreadcrumbs);
 
             /// Is the given interface one that a tagged-union type can conform to?
@@ -950,20 +956,48 @@ namespace Slang
             DeclRef<InterfaceDecl>  interfaceDeclRef,
             DeclRef<Decl>           requirementDeclRef);
 
-        bool doesTypeConformToInterfaceImpl(
-            RefPtr<Type>            originalType,
-            RefPtr<Type>            type,
-            DeclRef<InterfaceDecl>  interfaceDeclRef,
+            /// 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(
+            RefPtr<Type>            originalSubType,
+            RefPtr<Type>            subType,
+            DeclRef<AggTypeDecl>    superTypeDeclRef,
             RefPtr<Val>*            outWitness,
             TypeWitnessBreadcrumb*  inBreadcrumbs);
 
-        bool DoesTypeConformToInterface(
-            RefPtr<Type>  type,
-            DeclRef<InterfaceDecl>        interfaceDeclRef);
+            /// Check whether `subType` is a sub-type of `superTypeDeclRef`.
+        bool isDeclaredSubtype(
+            RefPtr<Type>            subType,
+            DeclRef<AggTypeDecl>    superTypeDeclRef);
+
+            /// Check whether `subType` is a sub-type of `superTypeDeclRef`,
+            /// and return a witness to the sub-type relationship if it holds
+            /// (return null otherwise).
+            ///
+        RefPtr<Val> tryGetSubtypeWitness(
+            RefPtr<Type>            subType,
+            DeclRef<AggTypeDecl>    superTypeDeclRef);
 
+            /// Check whether `type` conforms to `interfaceDeclRef`,
+            /// and return a witness to the conformance if it holds
+            /// (return null otherwise).
+            ///
+            /// This function is equivalent to `tryGetSubtypeWitness()`.
+            ///
         RefPtr<Val> tryGetInterfaceConformanceWitness(
-            RefPtr<Type>  type,
-            DeclRef<InterfaceDecl>        interfaceDeclRef);
+            RefPtr<Type>            type,
+            DeclRef<InterfaceDecl>  interfaceDeclRef);
 
         /// Does there exist an implicit conversion from `fromType` to `toType`?
         bool canConvertImplicitly(
@@ -1381,7 +1415,7 @@ namespace Slang
         CASE(OverloadedExpr)
         CASE(OverloadedExpr2)
         CASE(AggTypeCtorExpr)
-        CASE(CastToInterfaceExpr)
+        CASE(CastToSuperTypeExpr)
         CASE(LetExpr)
         CASE(ExtractExistentialValueExpr)