From 583c72af28d2dde5c564d5b56d3c5eb4ae4844f6 Mon Sep 17 00:00:00 2001 From: Tim Foley Date: Mon, 17 Dec 2018 19:26:32 -0800 Subject: First step toward supporting use of interfaces as existential types (#716) * First step toward supporting use of interfaces as existential types Traditional generics involve universal quantification. E.g., a declaration like: ``` void drive(T vehicle); ``` indicates for *for all* types `T` that implement the `IVehicle` interface, the `drive()` function is available. In contrast, whend directly using an interface type like: ``` IVehicle v = ...; v.doSomething(); ``` we only know that there *exists* some concrete type (we could call it `E`) such that `v` refers to a value of type `E`, and `E` implements the `IVehicle` interface. In order to perform an operation like `v.doSomething()` we need to "open" the existential value so that we can look at the concrete type and how it implements the `IVehicle.doSomething` requirement. This change adds a very explicit representation of existentials to Slang's IR. An operation like `e = makeExistential(v, w)` creates a value of some existential type (interfaces being our only existential types for now), by wrapping a concrete value `v` (the type of `v` can be seen as an implicit operand) and a witness table `w` showing that the type of `v` implements the requirements of the chosen interface type. In turn, opening of an existential is handled with operations `extractExistential{Value|Type|WitnessTable}` which pull the corresponding piece of information out of a value of existential type (which somewhere in the code had to have been created with `makeExistential`). The change includes a trivial simplification pass that can detect cases where an `extractExistential*` operation is applied direclty to a `makeExistential` operation, so that there is only one possible result that could be extracted. This allows for simplification of existential types used in trivial ways for local variables (this is mostly so I can check in a functional test, rather than to actually support useful code involving interfaces right now). The logic in the semantic checking phase of the compiler is comparatively more complex. When we are about to perform member lookup given an expression like `obj.member` we will first check if `obj` has an existential type, and if it does we will construct a suitable local context in which we extract the value, type, and witness table from the existential (these all become explicit AST expression nodes), and then use the extracted value as the base of the lookup operation. The nature of existential values is that two different values with the same existential (interface) type could wrap concrete values with differnt types, so that we need to carefully refer only to the extracted type/value/witness-table of specific *values*. We handle this right now by conceptually moving the existential-type value into a local variable (by introducing a `LetExpr` that amounts to `let v = in `) and then require that the extract expressions must refer to the (immutable) variable declaration from which they are extracting a value. (Eventually we should expand this so that when using an immutable local variable of existential type we just use that variable as-is rather than introduce a new temporary) A simple test case is included that uses an interface type in an almost trivial way for a local variable; this test can be run and produces the expected results. A more complex test case that passes an existential into a function is included, but left disabled because a more aggressive simplification approach is required to generate working code from it. * Add missing file for expected test output * Fixups for merge from top-of-tree --- source/slang/check.cpp | 164 ++++++++++++++++++++++++++++++++++++++++--------- 1 file changed, 135 insertions(+), 29 deletions(-) (limited to 'source/slang/check.cpp') diff --git a/source/slang/check.cpp b/source/slang/check.cpp index 38a79f1b7..7c60d3cf2 100644 --- a/source/slang/check.cpp +++ b/source/slang/check.cpp @@ -561,6 +561,80 @@ namespace Slang return isDeclUsableAsStaticMember(decl); } + RefPtr maybeOpenExistential(RefPtr expr) + { + auto exprType = expr->type.type; + + if(auto declRefType = exprType->As()) + { + if(auto interfaceDeclRef = declRefType->declRef.As()) + { + // Is there an this-type substitution being applied, so that + // we are referencing the interface type through a concrete + // type (e.g., a type parameter constrainted to this interface)? + // + // Because of the way that substitutions need to mirror the nesting + // hierarchy of declarations, any this-type substitution pertaining + // to the chosen interface decl must be the first substitution on + // the list (which is a linked list from the "inside" out). + // + auto thisTypeSubst = interfaceDeclRef.substitutions.substitutions.As(); + if(thisTypeSubst && thisTypeSubst->interfaceDecl == interfaceDeclRef.decl) + { + // This isn't really an existential type, because somebody + // has already filled in a this-type substitution. + } + else + { + // Okay, here is the case that matters. + // + + auto interfaceDecl = interfaceDeclRef.getDecl(); + + RefPtr varDecl = new Variable(); + varDecl->ParentDecl = nullptr; // TODO: need to fill this in somehow! + varDecl->checkState = DeclCheckState::Checked; + varDecl->nameAndLoc.loc = expr->loc; + varDecl->initExpr = expr; + varDecl->type.type = expr->type.type; + + auto varDeclRef = makeDeclRef(varDecl.Ptr()); + + RefPtr letExpr = new LetExpr(); + letExpr->decl = varDecl; + + RefPtr openedType = new ExtractExistentialType(); + openedType->declRef = varDeclRef; + + RefPtr openedWitness = new ExtractExistentialSubtypeWitness(); + openedWitness->sub = openedType; + openedWitness->sup = expr->type.type; + openedWitness->declRef = varDeclRef; + + RefPtr openedThisType = new ThisTypeSubstitution(); + openedThisType->outer = interfaceDeclRef.substitutions.substitutions; + openedThisType->interfaceDecl = interfaceDecl; + openedThisType->witness = openedWitness; + + DeclRef substDeclRef = DeclRef(interfaceDecl, openedThisType); + auto substDeclRefType = DeclRefType::Create(getSession(), substDeclRef); + + RefPtr openedValue = new ExtractExistentialValueExpr(); + openedValue->declRef = varDeclRef; + openedValue->type = QualType(substDeclRefType); + + letExpr->body = openedValue; + letExpr->type = openedValue->type; + + return letExpr; + } + } + } + + // Default: apply the callback to the original expression; + return expr; + } + RefPtr ConstructDeclRefExpr( DeclRef declRef, RefPtr baseExpr, @@ -577,6 +651,15 @@ namespace Slang { // If there was a base expression, we will have some kind of // member expression. + + // We want to check for the case where the base "expression" + // actually names a type, because in that case we are doing + // a static member reference. + // + // TODO: Should we be checking if the member is static here? + // If it isn't, should we be automatically producing a "curried" + // form (e.g., for a member function, return a value usable + // for referencing it as a free function). // if (baseExpr->type->As()) { @@ -1440,15 +1523,22 @@ namespace Slang // Trying to convert to an interface type. // // We will allow this if the type conforms to the interface. - if (DoesTypeConformToInterface(fromType, interfaceDeclRef)) + + if(auto witness = tryGetInterfaceConformanceWitness(fromType, interfaceDeclRef)) { if (outToExpr) - *outToExpr = CreateImplicitCastExpr(toType, fromExpr); + *outToExpr = createCastToInterfaceExpr(toType, fromExpr, witness); if (outCost) *outCost = kConversionCost_CastToInterface; return true; } } + + // Note: The following seems completely broken, and we should be using + // a `fromTypeDeclRef` here for the case when casting *from* a generic + // type parameter to an interface type... + // +#if 0 else if (auto genParamDeclRef = toTypeDeclRef.As()) { // We need to enumerate the constraints placed on this type by its outer @@ -1483,6 +1573,7 @@ namespace Slang } } +#endif } @@ -1721,6 +1812,25 @@ namespace Slang return castExpr; } + /// Create an "up-cast" from a value to an interface type + /// + /// This operation logically constructs an "existential" value, + /// which packages up the value, its type, and the witness + /// of its conformance to the interface. + /// + RefPtr createCastToInterfaceExpr( + RefPtr toType, + RefPtr fromExpr, + RefPtr witness) + { + RefPtr expr = new CastToInterfaceExpr(); + expr->loc = fromExpr->loc; + expr->type = QualType(toType); + expr->valueArg = fromExpr; + expr->witnessArg = witness; + return expr; + } + // Perform type coercion, and emit errors if it isn't possible RefPtr Coerce( RefPtr toType, @@ -7900,36 +8010,24 @@ namespace Slang // deal with this cases here, even if they are no-ops. // - RefPtr visitDerefExpr(DerefExpr* expr) - { - SLANG_DIAGNOSE_UNEXPECTED(getSink(), expr, "should not appear in input syntax"); - return expr; + #define CASE(NAME) \ + RefPtr visit##NAME(NAME* expr) \ + { \ + SLANG_DIAGNOSE_UNEXPECTED(getSink(), expr, \ + "should not appear in input syntax"); \ + return expr; \ } - RefPtr visitSwizzleExpr(SwizzleExpr* expr) - { - SLANG_DIAGNOSE_UNEXPECTED(getSink(), expr, "should not appear in input syntax"); - return expr; - } + CASE(DerefExpr) + CASE(SwizzleExpr) + CASE(OverloadedExpr) + CASE(OverloadedExpr2) + CASE(AggTypeCtorExpr) + CASE(CastToInterfaceExpr) + CASE(LetExpr) + CASE(ExtractExistentialValueExpr) - RefPtr visitOverloadedExpr(OverloadedExpr* expr) - { - SLANG_DIAGNOSE_UNEXPECTED(getSink(), expr, "should not appear in input syntax"); - return expr; - } - - RefPtr visitOverloadedExpr2(OverloadedExpr2* expr) - { - SLANG_DIAGNOSE_UNEXPECTED(getSink(), expr, "should not appear in input syntax"); - return expr; - } - - - RefPtr visitAggTypeCtorExpr(AggTypeCtorExpr* expr) - { - SLANG_DIAGNOSE_UNEXPECTED(getSink(), expr, "should not appear in input syntax"); - return expr; - } + #undef CASE // // @@ -8091,6 +8189,14 @@ namespace Slang expr->BaseExpression = MaybeDereference(expr->BaseExpression); + // If the base of the member lookup has an interface type + // *without* a suitable this-type substitution, then we are + // trying to perform lookup on a value of existential type, + // and we should "open" the existential here so that we + // can expose its structure. + // + expr->BaseExpression = maybeOpenExistential(expr->BaseExpression); + auto & baseType = expr->BaseExpression->type; // Note: Checking for vector types before declaration-reference types, -- cgit v1.2.3