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.

1 files changed, 113 insertions, 5 deletions

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<DeclRefType>(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<typename F>
     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<VarExpr>(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<LetExpr>(binding->body);
+                SLANG_ASSERT(binding);
+                continue;
+            }
+            else
+            {
+                binding->body = checkedTerm;
+                break;
+            }
+        }
+
+        return outerMostBinding;
     }
 
     Expr* SemanticsVisitor::CreateErrorExpr(Expr* expr)