From 24e60fd14bd957a69fb054d20e43e2c0580d57f2 Mon Sep 17 00:00:00 2001 From: Theresa Foley <10618364+tangent-vector@users.noreply.github.com> Date: Wed, 25 May 2022 08:14:28 -0700 Subject: Allow [mutating] methods on existential values (#2245) The problematic case is when an `interface` has a `[mutating]` method: interface ICounter { [mutating] void increment(); } and code tries to invoke that method on a value of existential type: ICounter c = ...; c.increment(); We know that the existential value `c` is conceptually a tuple of: * A concrete type `X` * A witness that `X : ICounter` * A value `v` of type `X` We simply want to invoke `increment()` on the `v` part, using the `X : ICounter` witness table. The catch that the compiler faces is that the variable `c` is mutable, so we need to be careful that we "snapshot" its value (the tuple `X, X:ICounter, v`) at a single point. The snapshotting behavior is important when invoking a method that involves `This` or associated types in its signature, so we cannot get rid of it. The snapshotting we do relies on the idea of a `LetExpr` AST node, which cannot be written in the input syntax. A `LetExpr` introduces a variable binding (with an initial-value expression) and then evaluates a body expression in the context of that binding. For a call site like `c.increment()` the front-end makes an intermediate copy of `c` and then "opens" that immutable value to get at the elements of the tuple `X`, `X : ICounter`, `v`. The resulting AST after checking looks something like: ICounter c = ...; (let tmp = c in extractExistentialValue(tmp)).increment(); In that form it is more clear why the attempt to call `increment()` fails: 1. The binding `tmp` sure looks immutable 2. There is no logic in the compiler to make `extractExistentialValue(x)` be an l-value if `x` is 3. There is seemingly no logic to write back from `tmp` to `c` when the operation completes Let us walk through those problems in order. Item (1) turns out to be a bit of a non-issue. Despite the way that I've written out `let` expressions above, the logic in `moveTemp()` in the compiler actually introduces a *mutable* binding. Item (2) can be fixed for the purposes of semantic checking by modifying `openExistential()`. Simplistically, we make the overall expression be an l-value if the operand is. Item (3) is handled at the level of AST->IR lowering. Each kind of expression that can form an l-value needs to have a way to represent the "location" of that l-value in the `LoweredValInfo` type. This change adds a case to handle the `extractExistentialVal` operation, by tracking both the extract value (of concrete type) and the underlying l-value (of existential type). Where all of this comes crashing against reality a bit is that the scoping I've drawn for the `let` expressions above kind of doesn't work once we look at types. The basic problem is that the *type* of the `(let tmp = c in ...)` expression is the concrete type `X` that was extracted from the existential. That type can conceptually be written as `ExtractExistentialType(tmp)` which, notably, references `tmp`. That means that we end up with AST expression nodes that reference the variable `tmp` *outside* of its scope. Furthermore, those references to `tmp` can end up being lowered to IR *before* we have lowered the `let ...` expression itself. Fixing the scoping issue turns out to be a major undertaking. The first (and more obvious) issue is needing to address the scoping problem. The solution I implemented includes a bit of refactoring to make all the `SemanticsVisitor` types better able to pass around the contextual scope-dependent state that might be needed during semantic checking, but really only adds a single piece of state. The semantic-checking state used for checking expressions is bottlenecked so that there will (or at least *should*) always be an explicit representation of a "scope" that surrounds a complete expression (as opposed to a sub-expression). When a `LetExpr` needs to be introduced, it is added to a pending list on the active scope, rather than being added locally. Once the complete expression is checked, the resulting expression is wrapped up in the pending `LetExpr`s so that their scope is as broad as possible. Technically this solution doesn't cover all cases. For example: interface ICell { associatedtype Content; Content getContent(); } ... ICell cell = ...; let content = cell.getContent(); In this case the type of `content` refers to the binding introduced by a `LetExpr` in the initial-value expression. I am leaving such issues as a piece of future work, in the hopes that we can get at least a partial fix for the problem in place. A future fix probably nees to extend the scoping even wider (e.g., by unwrapping the `LetExpr`s from the initial-value expression and turning them into distinct temporaries). The second piece of the fix is that we need a way for the modified value of the extracted existential to be "written back" to the original location. Well... We are actually being a little slippery here, based on some logic in the compiler codebase that I guess Just Works. When AST->IR lowering encounters a `LetExpr` that binds an l-value to a name, it actually ends up binding that name more or less as a *reference* to that l-value. At this point the `let`-ness of `LetExpr` is very much in doubt: the binding can be mutable, and it can even be an *alias* of some location?!? In any case, the result is that the AST->IR codegen logic implicitly handles the "write-back" because the `let`-bound temporary is actually an alias for the original location. A more complete future fix might need to introduce a distinct case in `LoweredValInfo` to handle the case of copy of a mutable temporary. --- source/slang/slang-check-expr.cpp | 118 ++++++++++++++++++++++++++++++++++++-- 1 file changed, 113 insertions(+), 5 deletions(-) (limited to 'source/slang/slang-check-expr.cpp') diff --git a/source/slang/slang-check-expr.cpp b/source/slang/slang-check-expr.cpp index 2290936d8..317ab6a1a 100644 --- a/source/slang/slang-check-expr.cpp +++ b/source/slang/slang-check-expr.cpp @@ -25,6 +25,31 @@ namespace Slang return as(expr->type); } + void SemanticsContext::ExprLocalScope::addBinding(LetExpr* binding) + { + if (!m_innerMostBinding) + { + SLANG_ASSERT(!m_outerMostBinding); + + // If we haven't added any bindings, then `binding` + // becomes both the inner-most and outer most. + // + m_innerMostBinding = binding; + m_outerMostBinding = binding; + } + else + { + SLANG_ASSERT(m_outerMostBinding); + + // If we already have bindings, then `binding` + // will become the new inner-most binding. + // + m_innerMostBinding->body = binding; + m_innerMostBinding = binding; + } + } + + /// Move `expr` into a temporary variable and execute `func` on that variable. /// /// Returns an expression that wraps both the creation and initialization of @@ -46,11 +71,30 @@ namespace Slang letExpr->decl = varDecl; auto body = func(varDeclRef); + Expr* result = body; + if (auto exprLocalScope = getExprLocalScope()) + { + // We want to add the `LetExpr` to the set of such expressions + // in the local scope, so that it can be emitted properly. + // + exprLocalScope->addBinding(letExpr); + } + else + { + // If we somehow got in here and there wasn't an expression-local + // scope established yet, it almost certainly represents an error. + // + SLANG_ASSERT(exprLocalScope); - letExpr->body = body; - letExpr->type = body->type; + // As a fallback, though, we will try to wire up the `letExpr` + // to surround the body directly and return that. + // + letExpr->body = body; + letExpr->type = body->type; - return letExpr; + result = letExpr; + } + return result; } /// Execute `func` on a variable with the value of `expr`. @@ -62,6 +106,11 @@ namespace Slang template Expr* SemanticsVisitor::maybeMoveTemp(Expr* const& expr, F const& func) { + // TODO: Eventually this operation could consider any case where the + // input `expr` names an immutable "path": one that starts at an + // immutable binding and follows a (possibly empty) chain of accesses + // to immutable members. + if(auto varExpr = as(expr)) { auto declRef = varExpr->declRef; @@ -114,6 +163,26 @@ namespace Slang openedValue->declRef = varDeclRef; openedValue->type = QualType(openedType); + // The result of opening an existential is an l-value + // if the original existential is an l-value. + // + if(expr->type.isLeftValue) + { + // Marking the opened value as an l-value is the easy part. + // + openedValue->type.isLeftValue = true; + + // The more challenging bit is that in this case the `maybeMoveTemp()` + // operation will have copied the original existential value into + // a temporary. + // + // If this expression is used in an l-value context, then we need + // to be able to generate code to "write back" the modified value + // (which will be of `openedType`) to the original location named + // by `expr` (an existential for `interfaceDeclRef`). + // + } + return openedValue; }); } @@ -606,8 +675,47 @@ namespace Slang { if (!term) return nullptr; - SemanticsExprVisitor exprVisitor(getShared()); - return exprVisitor.dispatch(term); + // The process of checking a term/expression can end up introducing + // temporaries that need to be added to an outer scope. When jumping + // into expression checking, we want to check if we already have such + // a scope in place. If we do, we will re-use it for any sub-expressions. + // If not, we need to create one. + // + if(getExprLocalScope()) + { + return dispatchExpr(term, *this); + } + + ExprLocalScope exprLocalScope; + + Expr* checkedTerm = dispatchExpr(term, withExprLocalScope(&exprLocalScope)); + + LetExpr* outerMostBinding = exprLocalScope.getOuterMostBinding(); + if(!outerMostBinding) + { + return checkedTerm; + } + + LetExpr* binding = outerMostBinding; + auto type = checkedTerm->type; + while (binding) + { + binding->type = type; + + if (auto body = binding->body) + { + binding = as(binding->body); + SLANG_ASSERT(binding); + continue; + } + else + { + binding->body = checkedTerm; + break; + } + } + + return outerMostBinding; } Expr* SemanticsVisitor::CreateErrorExpr(Expr* expr) -- cgit v1.2.3