aheejin commented 3 years ago

We have an old issue #11 for this, but it is 4 years old so I think it is worth opening a new one.

Recently Google's J2CL team is using wasm and they asked for finally to be added in the spec, citing the complexity of code duplicating transformation in case there are many branches/returns from the try part and also code size increase, which I think is a valid concern. Without finally, in case we have four ways of exiting a try block, such as 1. normal fallthrough 2. exception 3. return 4. branch, we might end up duplicating the same code four times.

finally support was discussed briefly years ago in #11, but people thought it could be transformed into try-catch with code duplication so it was not strictly necessary, but I'd like to ask you on your opinions now again.

@jakobkummerow suggested implementing it in the engine may not be trivial either, but it can be still worth having it in the spec because of the code size.

I cc'ed some people who might be interested or working on EH now + and also the J2CL team, but please feel free to comment even if I missed you. cc @tlively @dschuff @jakobkummerow @ecmziegler @thibaudmichaud @manoskouk @ioannad @takikawa @rluble @gkdn @rossberg @RossTate

RossTate commented 3 years ago

In #124, I offered the suggestion of having an "unwinding" variant of branching/returning instructions that would run all intermediate unwind blocks.

aheejin commented 3 years ago

@RossTate True, but we decided to remove unwind in #156. I think unwind + your variant of branching/returning instruction in effect achieves the same thing with finally.

RossTate commented 3 years ago

Oh, you were suggesting adding a finally block directly to wasm. Sorry, I misunderstood your post as looking for a way to support surface-level finally blocks within wasm. That would seem odd to me given your decision to remove unwind. finally blocks need to work with both dynamically scoped exceptions and lexically scoped branches/returns. As we discussed (and as I believe @phoe discussed in his presentation on non-local control), the rethrow instruction in catch_all makes it ill-suited for lexically scoped branch/returns. So finally blocks would need to not have a rethrow instruction. That would make them like unwind blocks. This means that you'd have to generate "unwinding" code differently for catch_all and finally (and maybe likewise for resolving unwinding mismatches?). The suggestion in #124 let you use the same unwinder code for both use cases, using the simple unwinding modifier on branches/returns to distinguish the two.

In short, I would expect any design with direct support for finally would be trivial to extend with unwind, making it unclear why we have catch_all. I understand that this has all been discussed before, which is why I am confused by the suggestion to add direct support for finally at this point.

aheejin commented 3 years ago

@RossTate I'm not sure if I understand what you are suggesting, and I also am not sure if we want to repeat the discussion between unwind vs. catch_all again. Also didn't really understand well what you meant by dynamic vs. lexically scoped, because we already have exceptional control flow anyway like throw and rethrow. (not necessarily in finally, but elsewhere)

I get finally and your proposal (unwind and unwinding branches and returns?) achieve the same thing. But finally can be one more instruction, but yours will require unwinding variant for every existing branch and return instruction: br, br_if, br_table, return, return_call, and many more branch instructions in the GC proposal: br_on_null/br_on_non_null, br_on_func/br_on_non_func, .... Is there a reason we should choose this path?

The suggestion in #124 let you use the same unwinder code for both use cases, using the simple unwinding modifier on branches/returns to distinguish the two.

Is this any different for finally?

aheejin commented 3 years ago

Also what we should think about are:

What happens when catch throws or rethrows? In Java finally should run anyway. Then how should we define the semantics of catch's throw's argument, or in case of rethrow, how should we manage the rethrow's stack? Should we do a bookeeping of catch's argument (or rethrow stack) before running finally and after running finally throw the catch's exception?
What happens catch throws or rethrows but finally also throws or rethrows? (@RossTate suggested finally shouldn't rethrow, which I am yet to understand why, but I think this question is separate, because finally at least can just throw) In Java semantics, catch's exception is discarded and finally's exception is honored. Is this the semantics we want to pursue here too?

RossTate commented 3 years ago

Also didn't really understand well what you meant by dynamic vs. lexically scoped, because we already have exceptional control flow anyway like throw and rethrow.

Exceptional control flow can be either dynamically scoped or lexically scoped. throw is a form of dynamically-scoped non-local control—it's non-local in that it can cause control to transfer outside of a function in some way besides returning, and it's dynamically-scoped in the sense that one traverses the stack to find out where to transfer control to. In lexically-scoped control transfer, the target is determined without inspecting the stack. br and return are forms of local lexically-scoped control transfer. return-from and go in Common Lisp are both forms of non-local lexically-scoped control transfer (with non-local usages provided in @phoe's presentation). Two-phase exception handling is a combination of continuation marks (the generalization of dynamically scoped variables that Matthew Flatt just presented) and lexically-scoped non-local control—one uses stack inspection to enumerate through the potential handlers, calling them in sequence until the handler does not return and instead uses a lexical non-local control transfer to jump to the "catch" code that the handler determined to be the appropriate match for the exception.

but yours will require unwinding variant for every existing branch and return instruction

From #124: "One way we could enable this is to introduce an unwinding instruction that must precede a branching instruction, and its semantics is to modify that branching instruction to execute the unwinders in unwind clauses as it cleans up the stack."

That said, you could have finally be just a variant of unwind that effectively puts unwinding around every applicable instruction. A benefit of that would be to reduce code size (though unwinding can be a single-byte instruction). But it might also be problematic for code generation and optimization (as br and such now become context-sensitive, beyond just having to stay in a place where their target label is still in scope).

As for the questions, I get concerned when I see WebAssembly making such policy decisions. It suggests to me that we haven't developed the correct low-level mechanisms that would enable languages to implement their own policy within WebAssembly.

jakobkummerow commented 3 years ago

I am confused by the suggestion to add direct support for finally at this point.

As the OP says, the primary motivation is module size. When the J2CL team thought about how to support Java's finally in Wasm, they realized that (1) the obvious (/only?) solution with the currently proposed Wasm-EH feature set is to duplicate the contents of the finally-block, and (2) depending on the structure of the function, many such copies may be required. If the Wasm wire format supported the notion of finally-blocks, then the modules could remain smaller, and the copying could happen in the engine (if an engine chooses to implement it that way; on this level there may be viable alternatives).

We do not have specific numbers on the module size impact yet, as it isn't easy to get them (it requires implementing the duplication approach first).

tlively commented 3 years ago

124 proposes an alternative system that unbundles the search for dynamic control flow destinations from stack unwinding. Such a system is inarguably lower level (i.e. more expressive) than the currently proposed system, but that extra expressiveness comes at a great complexity cost in terms of the number of new primitives introduced. Although the presentation and exposition of Common Lisp control flow primitives was illuminating, I do not believe we currently have a large and diverse enough set of language implementors to validate a design for more general low-level control flow and unwinding primitives. All that is to say that I believe we should keep the current discussion focused on the current proposal scope of single phase exceptional control flow.

As for the questions, I get concerned when I see WebAssembly making such policy decisions. It suggests to me that we haven't developed the correct low-level mechanisms that would enable languages to implement their own policy within WebAssembly.

I agree that it would be great to develop such mechanisms, but they should be developed in a separate proposal and in partnership with language implementors who would use them

With that being said, I would like to say that I am tentatively in favor of adding some form of finally to this proposal for the following reasons:

Although the JVM does not have a finally construct, the .NET IL does, so there is precedent to include finally in a similar exception system.
Avoiding code path duplication will make it easier to optimize code. For example, inlining heuristics will be better if a call in a source-level finally block is not duplicated.
Producers will be simpler if they do not need to compile source-level finally via code duplication.
Code size benefits.

I would propose adding try-finally as a new form in addition to the existing try-delegate and try-catch*-catch_all? rather than allowing constructs like try-catch*-catch_all?-finally?. I believe this would sidestep the tricky questions @aheejin raised about the interactions between catching, throwing, and finally blocks by leaving it up to the producer to nest the constructs correctly.

Another question to resolve is whether control flow transfers via try-delegate should run finally blocks or tunnel through them the same way they tunnel through catches. I would propose that try-delegate should tunnel through finally blocks without running them because the whole point of try-delegate is to behave as though the exception is being thrown from the delegate scope.

I would be less inclined to add finally to the proposal if it turned out that various source languages had different finally semantics that could not all easily be supported by a single addition to the spec. To my knowledge this is not the case, but I also haven't investigated it at all.

aheejin commented 3 years ago

@tlively

I would propose adding try-finally as a new form in addition to the existing try-delegate and try-catch*-catch_all? rather than allowing constructs like try-catch*-catch_all?-finally?. I believe this would sidestep the tricky questions @aheejin raised about the interactions between catching, throwing, and finally blocks by leaving it up to the producer to nest the constructs correctly.

I think splitting this is a good idea if it makes thing simpler. But I'm not sure how we should transform this code in Java:

try {
  foo();
} catch (Exception e) {
  throw e; // rethrow or throw, doesn't matter
} finally {
}

The problem is the finally should rethrow, or more precisely pass, the already thrown exception in case the finally is entered by an exception thrown, but the finally should just fall through in case the finally is entered by a fallthrough, and it should return in case it is entered by a return, and so on. @rluble @gkdn How do you plan to generate code for this difference in J2CL?

Another question to resolve is whether control flow transfers via try-delegate should run finally blocks or tunnel through them the same way they tunnel through catches. I would propose that try-delegate should tunnel through finally blocks without running them because the whole point of try-delegate is to behave as though the exception is being thrown from the delegate scope.

I agree finally should just tunnel through the exceptions delegated by delegate, for the same reason.

fgmccabe commented 3 years ago

The finally clause is not the one doing the throwing in this example. In fact, in early Java implementations, the finally block was implemented using JSR (which is like a funclet). The finally code (void->void was run just before throwing.

tlively commented 3 years ago

The problem is the finally should rethrow, or more precisely pass, the already thrown exception in case the finally is entered by an exception thrown, but the finally should just fall through in case the finally is entered by a fallthrough, and it should return in case it is entered by a return, and so on.

Isn't this what the WebAssembly-level finally would do as well?

aheejin commented 3 years ago

The problem is the finally should rethrow, or more precisely pass, the already thrown exception in case the finally is entered by an exception thrown, but the finally should just fall through in case the finally is entered by a fallthrough, and it should return in case it is entered by a return, and so on.

Isn't this what the WebAssembly-level finally would do as well?

I guess so, but should we make spec decision finer-grained than that? For example, if we hold off on any throws from a catch to run it after finally body, how should we manage the value stack? By the time of throw we might have arbitrary number of values on top of the value stack to be used by the throw. How should we preserve that stack until the end of finally? Should we run finally in a shadow stack or something?

tlively commented 3 years ago

One possibility would be to require finally blocks to have type [] -> [] and to not give them access to any values that the control flow is carrying as it passes through the finally blocks, whether or not that control flow is exceptional. So finally would not be able to inspect or modify the values or exceptions associated with the control flow. I don't have a good sense of what languages this would or would not work for, though.

tlively commented 3 years ago

We also have to figure out what should happen to the in-flight exception or control flow payload if there is a branch (or return) out of a finally block and make sure that behavior is general enough among languages with exceptional control flow. @RossTate's point about leaving these policy decisions up to individual toolchains sounds nicer and nicer the more I think about this, so I hope we can do a low-level follow up proposal at some point :)

fgmccabe commented 3 years ago

finally blocks should definitely have type []->[]. Anything else is madness.

aheejin commented 3 years ago

FYI: It looks when there is a preceding control flow action (branch / return / exception) from try or catch, and finally clause also has its own control flow action, at least several languages I checked (Python, Java, JavaScript, Kotlin, and C#) all discard the preceding action and honor the finally's action.

Also among those five languages, only Python allowed rethrow in finally. https://docs.google.com/spreadsheets/d/1GV5T-mkf3NuN6SVnwr2LkvkxHPxtbbf9g7CfQZhpiP8/edit?usp=sharing

RossTate commented 3 years ago

Thanks for doing the survey!

Note, though, that Python does not allow rethrow in finally. Python's raise (without argument) statement is not the same as rethrow in catch_all. For example, the following program ends up printing "Hello" then "0" and then throws Exception("Hello"):

def foo():
    for i in range(0, 3):
        try:
            print(i)
            break
        finally:
            print("Hello")
            raise

try:
    raise Exception("Hello")
except: # finally instead of except also produces the same result here
    foo()

That is, if a finally clause is being executed due to lexical control flow (in this case, the break), the raise does not resume unwinding or the lexical control transfer. Instead, it looks up the stack to see if the current dynamic scope is within a try that is still handling an exception (i.e. is within an except or finally clause unless the finally clause follows an except clause that successfully handled the exception) and then rethrows that exception from the point of raise.

aheejin commented 3 years ago

@RossTate

That is, if a finally clause is being executed due to lexical control flow (in this case, the break), the raise does not resume unwinding or the lexical control transfer.

Not sure what you mean. Our rethrow doesn't resume lexical control flow either. (We don't have finally now so there is no case that we would do that in the first place)

Also other than foo is a function and our rethrow does not allow rethrowing from a callee (due to lack of exnref now), if we inline foo, I'm not sure why our rethrow and this raise should be different, other than we don't have finally.

But I'm also not sure if this is worth spending time debating about even if I don't understand your comment, given that this is a side topic.

aheejin commented 3 years ago

I'll try to sum up the requirements or suggestions so far. I might be missing something or there can be cases I haven't considered; please let me know if so. I'd like to ask especially to VM folks, since I'm not very familiar with VM internals and feasibility issues there.

Here "control flow transfer" means one of branches, returns, or exceptions.

The type of finally block is [] -> [].
When there is a preceding control flow transfer before entering finally and finally does not have its own control flow transfer, we pause the execution of the preceding control flow transfer and preserve that value stack, and run finally block, which cannot touch or consume the value stack (with an exception; see below). After finishing finally, we execute the paused preceding control transfer.
When there is a control flow transfer inside finally, the preceding control transfer, if any, is discarded, and the finally's control flow transfer is executed. The value stack is popped according to the normal rule, as in control flow transfers outside of finally.

I think try-finally can exist as a separate construct and also exist as an addition to try-catch; all languages I surveyed run finally after catches, so I don't think that will be very confusing.

takikawa commented 3 years ago

I'd like to ask especially to VM folks, since I'm not very familiar with VM internals and feasibility issues there.

I haven't thought through all of the details here yet, but one issue I wanted to raise is that with try-finally it seems potentially tricky to implement for the one-pass baseline compilers in engines. Assuming the binary format for try-finally looks similar to the current try-catch.

In particular, we won't know until seeing the finally opcode if it's a try-catch or try-finally. But my understanding of the proposed semantics is that if there's a br in the try part of a try-finally, it would need to jump to the finally block first before (potentially) resuming the jump out of the block. Since we don't know if we need to run cleanup code at the point the br opcode is consumed, it might be trickier to do this in one-pass.

Maybe the binary format for try-finally could be formulated differently to make this easier though. For example the finally block might come first, or maybe it uses a different opcode for its try, or something else.

rossberg commented 3 years ago

When there is a preceding control flow transfer before entering finally and finally does not have its own control flow transfer, we pause the execution of the preceding control flow transfer and preserve that value stack, and run finally block, which cannot touch or consume the value stack (with an exception; see below). After finishing finally, we execute the paused preceding control transfer.

Just to understand this right, are you saying that a branch out of a try body would still run the finally block?

I'm not convinced that's what should happen on the assembly level. For the machine, a jump is a jump. When compiling a language with a richer goto semantics it would be up to the compiler to translate that accordingly when it crosses a finally block. The ability to bypass a finally block is something a code generator might even want under certain circumstances.

I think finally semantics should be as regular and simple as possible. The equivalence I'd expect is something like

 try $l A finally B end ==
 block $l (try A catch_all B (rethrow 0) end) B end

That is, it merely ensures that B is executed on both completion and exceptional exit from A, but does not affect the meaning of explicit jumps.

That is sufficient to avoid the exponential code duplication of B that you'd otherwise need, and which is the problem this feature should focus on fixing. Gotos do not create that problem, AFAICS: at worst, you'll need a local and an extra br_table after the finally.

When there is a control flow transfer inside finally, the preceding control transfer, if any, is discarded, and the finally's control flow transfer is executed. The value stack is popped according to the normal rule, as in control flow transfers outside of finally.

Same question here, I am not sure if I am reading this correctly. It sounds like a br out of a finally block should be intercepted and still rethrow the exception? That would be really odd, and doesn't even match what source languages do.

I think try-finally can exist as a separate construct and also exist as an addition to try-catch; all languages I surveyed run finally after catches, so I don't think that will be very confusing.

Agreed, we should keep these instructions separate.

tlively commented 3 years ago

...

I think finally semantics should be as regular and simple as possible. The equivalence I'd expect is something like
 try $l A finally B end ==
 block $l (try A catch_all B (rethrow 0) end) B end
That is, it merely ensures that B is executed on both completion and exceptional exit from A, but does not affect the meaning of explicit jumps.

That is sufficient to avoid the exponential code duplication of B that you'd otherwise need, and which is the problem this feature should focus on fixing. Gotos do not create that problem, AFAICS: at worst, you'll need a local and an extra br_table after the finally.

This seems reasonable to me. br $l would still run the finally block, but br to anything outside of $l would not. What would happen if B contained a br 0, though? It would seem that in the exceptional case it would branch to the non-exceptional B so B would end up being run twice. So I think there needs to be some sort of fixup of the branch indices in the inner B.

When there is a control flow transfer inside finally, the preceding control transfer, if any, is discarded, and the finally's control flow transfer is executed. The value stack is popped according to the normal rule, as in control flow transfers outside of finally.

Same question here, I am not sure if I am reading this correctly. It sounds like a br out of a finally block should be intercepted and still rethrow the exception? That would be really odd, and doesn't even match what source languages do.

I had the opposite reading here: control flow out of the finally block overrules whatever control flow caused the finally block to be entered. This is in line with your proposed semantic equivalence.

I think try-finally can exist as a separate construct and also exist as an addition to try-catch; all languages I surveyed run finally after catches, so I don't think that will be very confusing.

Agreed, we should keep these instructions separate.

I think I had the opposite reading here, too. @aheejin, you are proposing that try-catch*-finally be allowed, right?

fgmccabe commented 3 years ago

The complexities of all these considerations is beginning to convince me that there 'should be another way' to reduce code duplication.

aheejin commented 3 years ago

@rossberg @tlively

When there is a control flow transfer inside finally, the preceding control transfer, if any, is discarded, and the finally's control flow transfer is executed. The value stack is popped according to the normal rule, as in control flow transfers outside of finally.

Same question here, I am not sure if I am reading this correctly. It sounds like a br out of a finally block should be intercepted and still rethrow the exception? That would be really odd, and doesn't even match what source languages do.

I had the opposite reading here: control flow out of the finally block overrules whatever control flow caused the finally block to be entered. This is in line with your proposed semantic equivalence.

Yeah, what @tlively said was what I meant. I tried to match the semantics to the source languages.

I think try-finally can exist as a separate construct and also exist as an addition to try-catch; all languages I surveyed run finally after catches, so I don't think that will be very confusing.

Agreed, we should keep these instructions separate.

I think I had the opposite reading here, too. @aheejin, you are proposing that try-catch*-finally be allowed, right?

Yes, your reading is what I meant. What I meant was try-catch*-finally shouldn't be too confusing. But I don't have a strong preference here.

aheejin commented 3 years ago

@rluble @gkdn Would the semantics @rossberg suggested in https://github.com/WebAssembly/exception-handling/issues/158#issuecomment-858485623 work for you? It'd be good to hear from you J2CL people given that currently this features is requested from J2CL. That semantics still require some code transformation, but not as many duplicated copies.

RossTate commented 3 years ago

In WebAssembly, each label can have a different type. This makes the suggestion in https://github.com/WebAssembly/exception-handling/issues/158#issuecomment-858485623 not well aligned with WebAssembly's existing local control flow as it expects people to use br_table, which requires all the relevant labels to have the same type. That is, not all WebAssembly code using a (full) finally construct would translate well to the (restricted) finally construct and a br_table. (For example, a return from inside the try versus a br from inside the try are very likely to have different payloads.)

That said, I'm receptive to @rossberg's "a jump is a jump" argument, which is one reason I had suggested the unwinding modifier: it indicates to the engine that the following branch is not just a jump.

In particular, we won't know until seeing the finally opcode if it's a try-catch or try-finally.

I agree this is a problem. I think the leading instruction should be more informative.

RossTate commented 3 years ago

Rather than change wasm, why not compile surface-level finally by putting all code in surface-level finally blocks into wasm-level catch_all blocks, and then translating branches/returns that would break out of a finally block into a throw of a distinguished exception that is caught outside the catch_all and branches to the respective label?

aheejin commented 3 years ago

@RossTate I think that's a way we can handle this. I agree finally is not a must-have primitive feature but J2CL people requested it as more of a feature for convenience. I haven't checked with them recently, but it is possible they are doing something similar on their end.

RossTate commented 2 years ago

190 provides a new option. The JS-to-wasm conversion enables J2CL to ensure the only non-trapping exception is `$__java_exception : [(ref $Throwable)]`. The wasm-to-JS conversion lets J2CL store the debug information inside `ref $Throwable` without losing any debugging support, and as such J2CL no longer needs to use `catch_all` or `rethrow` to get good debugging support for `finally`.

With that in mind, J2CL can support try { try-body } finally { finally-body } with the following:

(local $exn (ref null $Throwable))
(local $control i32)

(block $outer-label-1 ...
    (block $rethrow
        (block $finally
            (try
                ;; translate try-body
                ;; but instead of break/continue/return
                ;; use (local.set $control (i32.const [outer-label-index])) (br $finally)
            catch $__java_exception
                (local.set $exn) ;; a (ref $Throwable) was on the stack
                (local.set $control (i32.const 0))
                (br $finally)
            )
        )
        ;; translate finally-body
        (br-table $rethrow $outer-label-1 ... (local.get $control))
    )
    (throw $__java_exception (ref.as_non_null (local.get $exn)))
...)

aheejin commented 2 years ago

@RossTate This is what we used to do with exnref. At this point I'm not sure why you insisted on its removal for months last year.

rossberg commented 2 years ago

Like @aheejin, I'm having a strong déjà vu.

sjrd commented 3 months ago

For the next poor soul coming here in search of an answer, here are some good news. The new semantics with try_table and exnref allow to generically support try..finally constructs for all exceptions, irrespective of their tags and of whether your compiler generated them or not. We implemented it for the Scala-to-Wasm compiler that we are working on.

For the full deal of details, you can find our implementation and the big accompanying documentation comment at: https://github.com/tanishiking/scala-wasm/blob/7fd86c163814910a5d5155aa32386f8051e75a43/wasm/src/main/scala/ir2wasm/WasmExpressionBuilder.scala#L2651

tl;dr The scheme is a variant of https://github.com/WebAssembly/exception-handling/issues/158#issuecomment-963404970 that uses a try_table with catch_all_ref to deal with all exceptions. In addition, it uses a different $control variable for each finally block: indeed, if there is a try..finally inside a finally, they may both require a different $control result, which are both live at the same time. Moreover, it can deal with try..finally and blocks in expression position (therefore with non-empty (result ...) clauses).

To give you an idea, the try..finally blocks are compiled as follows (our $destinationTag locals correspond to $control in the previous comment):

block $innerDone (result i32)
  block $innerCatch (result exnref)
    block $innerCross
      try_table (catch_all_ref $innerCatch)
        ; [...] body of the try

        local.set $innerTryResult
      end ; try_table

      ; set destinationTagInner := 0 to mean fall-through
      i32.const 0
      local.set $destinationTagInner
    end ; block $innerCross

    ; no exception thrown
    ref.null exn
  end ; block $innerCatch

  ; now we have the common code with the finally

  ; [...] body of the finally

  ; maybe re-throw
  block $innerExnIsNull (param exnref)
    br_on_null $innerExnIsNull
    throw_ref
  end

  ; re-dispatch after the outer finally based on $destinationTagInner

  ; first transfer our destination tag to the outer try's destination tag
  local.get $destinationTagInner
  local.set $destinationTagOuter

  ; now use a br_table to jump to the appropriate destination
  ; if 0, fall-through
  ; if 1, go the outer try's cross label because it is still on the way to alpha
  ; if 2, go to beta's cross label
  ; default to fall-through (never used but br_table needs a default)
  br_table $innerDone $outerCross $betaCross $innerDone
end ; block $innerDone

For more context, please see the full code comment that I linked above.

WebAssembly / exception-handling

`finally` support? #158