Scopes: Encoding pseudo-tail-calls

[rakudrama]

It is not clear how to conditionally hide frames depending on what more recent frames are on the stack.

The Dart method foo might require parametric covariant type checks and / or argument defaulting

class X<T> {
  void foo(T a,               // 8
           [T? b = null]) {   // 9
    throw 'ouch';             // 10
  }  
}

main() {
  X<Object> x = X<String>();
  x.foo('abc');              // 21
  x.foo(123);                // 22
  X<int>().foo(1,2);         // 23
}

To support the checks, one strategy (used by dart2js) is to compile the method into multiple entry points.
Each entry point handles some combination of checks and argument defaulting without doing unnecessary checks.
Some entry points call others, to eventually reach the main unchecked body.
If JavaScript had tail calls (and the syntax for tail calls was compact), tail calls could be used.

X.prototype = {
  foo$body(a, b) { throwExpression("ouch"); }
  foo$1$unchecked(a) { return this.foo$body(a, null); }
  foo$2(a, b) { return this.foo$body(checkType(a, this.T), checkTypeNullable(b, this.T)); }
  foo$1(a) { return this.foo$1$unchecked(checkType(a, this.T)); }
}

(The minifier can pick almost any name for these entry points which erases the naming system, e.g., k7, q, A_, f.)

Without tail calls, multiple stack frames can represent one call. Depending which calls are commented out, one might see different JavaScript stacks for the 'same' call in Dart:

Error: "ouch"
throwExpression
foo$body
foo$1$unchecked
foo$1
main

TypeError: 123: Type 'int' is not a subtype of 'String'
checkType
foo$1
main

Error: "ouch"
throwExpression
foo$body            // body is called directly because arguments don't need to be checked since T=int
main

All three stacks should be translated to a stack trace that has one frame for foo.

Error: "ouch"
foo     file.dart:10
main    file.dart:21

TypeError: 123: Type 'int' is not a subtype of 'String'
foo     file.dart:8        // position of 'foo' or. better, position of 'T a' or 'a'
main    file.dart:22

Error: "ouch"
foo     file.dart:10
main    file.dart:23

The frames that might have been tail calls should be hidden, but only if the target of the 'tail' call frame is not above it.
Complications include:

• foo could be recursive, calling any of the entry points from the body
• The body, if small, might be inlined into any of the entry points

Does the scopes proposal contain enough mechanism to implement the policy of translating the JavaScript stack to one 'best' frame for Dart?

[szuend]

No, I don't think we can express this cleanly at the moment. With the current state of the proposal you'd encode it as follows:

• foo$body is the only generated range that points back to the original foo function scope.
• The rest of the foo$* functions don't point to any original scope.

Then the 3 stack traces would look like the following:

 Error: "ouch"
foo     file.dart:10
main    file.dart:21

TypeError: 123: Type 'int' is not a subtype of 'String'
main    file.dart:22

Note the missing foo frame.

Error: "ouch"
foo     file.dart:10
main    file.dart:23

As a side note: Intuitively this would have matched my expectation as the type-check happens "before" the actual call, without "foo" being on the stack. How can "foo" be on the stack if you can't call "foo" due to the wrong type? xD

On a more serious note: One way to support this could be to add a "tail call item": <start generated range><tail call item 1><tail call item 2><end generated range>. The "tail call items" would contain a reference to another generated range so the stack trace processor can collapse them if it sees the pattern:

generatedFunction1 bundle.js:2 <-- generated range pointing at orignal scope "function1".
generatedFunction2 bundle.js:5 <-- generated range with a tail call item referencing "generatedFunction1" but also pointing at original scope of "function1"

Note that the current encoding format will allow us to add such a "tail call item" to the scopes encoding after the fact without breakage. So we could add this (via standard ECMA-426 proposal process) after the current version has fully landed in the spec.

[rakudrama]

As a side note: Intuitively this would have matched my expectation as the type-check happens "before" the actual call, without "foo" being on the stack. How can "foo" be on the stack if you can't call "foo" due to the wrong type? xD

The person debugging the crash would like to know

1. which foo is the actual target, since the call could be indirect (e.g. subclass overrides).
2. which parameter has the failing covariance check.

The Dart VM shows the position of the covariance check, and that what dart2js and dart2wasm are trying to match.
The 123 case is too confusing without the (often indirect) target.

The analogous entry stubs from dart2wasm do not currently use tail-calls, so will need the same.

[hbenl]

It is not clear how to conditionally hide frames depending on what more recent frames are on the stack.

This isn't possible but it's actually not needed for this example, all we need is to use a combination of inlining and outlining. The way I think about it is that dart2js first outlined parts of foo() into the foo$...() methods and then inlined (the remainder of) foo() into main() (turning each inlining into a single foo$...() call).
This is expressed by this scope map and here's what I get when I run it in my debug adapter prototype:

[rakudrama]

Clever! Nice to see the screen shots!

The calling convention does not call foo, but calls foo$1 to signal a call passing one argument in a way that is immune to spoofing with undefined and requires no checks of the collection of arguments against the signature.

If there was another class, Y, implementing the same interface method 'I.foo()', Y too would have a foo$1 entry stub, which could contain anything. I.foo() might have exactly one parameter, and X.foo and Y.foo could have different signatures provided they are both consistent with the interface.
At the call site in main we can't pretend we are inlining X.foo or Y.foo because we don't know which implementation of I.foo we are calling.

Can we get the effect without pretending there is an inlining in main?

[hbenl]

At the call site in main we can't pretend we are inlining X.foo or Y.foo because we don't know which implementation of I.foo we are calling.

We could define an original scope for I.foo and use that for the inlining.

Can we get the effect without pretending there is an inlining in main?

I don't think so.

[rakudrama]

If I read the example correctly, the range L13-L17 checkType is not hidden, but it does not have a definition (originalScope).
Is it the lack of definition why it is not in the reported stack?

For off-line stack translation we keep untranslated frames rather than elide them. In practice, source maps have incomplete and bad mappings and we would rather those show up.

Would the following work?

There are no ranges with a call site because there has been no inlining of one user-level method into another.
The range for main is simple, no children. Call sites will be located in the stack trace and are located with the V3 mappings.

The stubs themselves have multiple ranges.

There is inlining of a sort: the checks in the stubs are 'inlined' from the user's model of a single function.
We can attribute the check to the parameter.
It is a non-hidden subrange that is just like a range for an inlining, but there is no call site.

5    foo$1(a) { return this.foo$1$unchecked(checkType(a, this.T)); }
     aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
                                            iiiiiiiiiiiiiiiiiiii

aaa: isHidden=true, isStackFrame=true, V3 mappings to declaration identifier foo.
When the call this.foo$1$unchecked( is on the stack, it is hidden.

iii: a child of aaa, isHidden=false, originalScope=scope for foo, and the V3 mapping to T a.
When the call checkType( is on the stack, it maps to T a with a and b in scope.

What is the [[StackFrameType]] of this range?

[hbenl]

If I read the example correctly, the range L13-L17 checkType is not hidden, but it does not have a definition (originalScope).
Is it the lack of definition why it is not in the reported stack?

It is not in the reported stack because checkType() doesn't have a V3 mapping to the original source.

For off-line stack translation we keep untranslated frames rather than elide them. In practice, source maps have incomplete and bad mappings and we would rather those show up.

I agree, adding those frames is on my TODO list. I've filtered them out in the prototype for now to match the current state of the spec but when I leave them in, it looks like this:

Would the following work?
[...]

So you're trying to turn the frame pointing to checkType() into one pointing to foo(). I see some problems with that:

• checkType() could be called from other places as well
• for the case of x.foo('abc') I guess you'd use the frame pointing to throwExpression() for the same purpose? But I think there wouldn't always be such a "terminal" function that could be chosen to point to foo().

Thinking about this I realized that I may have caused some confusion when I wrote this:

It is not clear how to conditionally hide frames depending on what more recent frames are on the stack.

This isn't possible

Actually when you set the isHidden flag on a range, it is not the frame pointing to that range that gets hidden but its caller frame, maybe that's what you meant by "conditionally hide frames depending on what more recent frames are on the stack".
So when you have this stack:

Error: "ouch"
throwExpression
foo$body
foo$1$unchecked
foo$1
main

... the foo$body, foo$1$unchecked and foo$1 ranges have the isHidden flag, so the main, foo$1 and foo$1$unchecked frames are hidden and the foo$body frame becomes the foo frame because foo$body has V3 mappings pointing to foo (like all the foo$... functions). The main frame that is reported comes from the inlining.

I still feel that the inlining approach is sound, there is some logic (linked to the function's type declaration) that decides which foo$...() entry stub to call and that logic is sort of inlined and constant-folded at the foo() call sites.