source: doc/proposals/exceptions.md@ 8136df1

Exception Update Proposal
=========================

Exceptions have pretty constant since the end of Andrew's project (*), with
the one major addition being some convenience macros. Experience, though, has
highlighted problems, particular some difficult to understand sections.

(* I'm Andrew, I am writing this in third person so other people can update
  it easily, but I'm not beating on myself.)

A lot of this should be viewed in the context of the "Proposal For Use of
Virtual Tables" (see `vtable.md`), and will refer to parts of it. In fact,
a lot of what to be discussed about exceptions is actually how it uses
that proposal, and at the same time, enabling exceptions is the primary
motivation behind virtual tables, with others being largely abstract.

Note that the following problem areas are also inter-related with each other,
the virtual table code (as above) and the exception feature list.

Type/Function Binding
---------------------
Exceptions (and the virtual table system) attempt to use the location based
binding like the rest of Cforall. However, because exceptions are created and
used in very different places, without stepping through all the intermediate
locations. This is the largest user issue the system faces right now.

The full list of things you have to do:
+   Define the structure (in the header).
+   Implement the required functions (in implementation).
+   Forward declare a virtual table instance (in the header).
+   Define the virtual table (in implementation).
+   Pass in the table reference to a constructed exception (at usage).

Even this example has some automation. For example, defining the virtual
table automatically defines some of the associated functions. This means that
you cannot control the implementation of those functions.

Helper macros have been plastered all over this process to try and reduce
the number of steps. It is annoying, repetitive and error prone. It does open
up new options for customization, similar to call-site binding, but this does
not get used very often (as of yet, no examples have come up naturally).

It turns out that you usually, almost always even, want a single binding
between a type and its implementing function. Call-site binding has some
similar issues, but the extra work for the flexibility is almost entirely
on the compiler. (See Stack Unwinding for information on why we can't just
resolve at the throw site.) We have also currently fixed implementations for
that one binding because of all the short-cut.

There are a couple of directions to go with this, but the root cause is just
that contextual binding does not work great with large shifts in context.
There are a couple of ways
+   Add universal (non-contextual) type/function binding. If a given type
    always have the same assertions associated with it, which then must be
    static, this problem goes away. This is a slight loss of functionality,
    but is the strategy used by most type-class systems as well as in
    object-orientated programming, which fits well with exceptions.
+   Improve the user interface. It may not be a logical change so much as
    just a user interface improvement to the system. The limits around
    life-time, memory allocation and resolution timing remain, but new tools
    could at least make the simple use cases easier and less error prone.
+   Remove the need for a stable binding entirely. This would allow the
    contextual binding to be used as it is in the rest of Cforall. However,
    it would likely require the largest changes to exceptions. It would be
    something like separately resolving the assertions at both sites.

Stack Unwinding and Lifetime
----------------------------
Termination exceptions unwind the stack between the throw and the catch.
This runs all the destructors and releases stored memory. The memory used
by an exception must remain in scope past the unwind while the handler is
run.

There are two main ways to make sure memory/data remains live. First, is to
make sure that the data already has a sufficient life-time. Because it is
usually not known where an exception will be caught, that usually just means
something with a static life-time. The second option is to manually extend
the life-time by copying the data. Most exception handling mechanisms (EHMs)
use both of these, copying some core data around that might refer to out to
static information (usually code).

The problem in Cforall, assertions can often be in neither of these areas.
While the value of the assertion itself is a local value that could be
copied around, but they often refer to stack allocated thunks, created when
a polymorphic function was specialized (monomorphized) to a less polymorphic
form. These are not static and we don't have the layout information to copy
them either.

The explicit virtual tables is an attempt to address this, because they
create a minimum on the life-time of the assertions and thunks. This still
could be unwound if the table is on the stack, but it explicitly shows where
that limit is, unlike the automatic monomorphiation.

This problem is really dependant on the constraints on it. There are minor
improvements to be made, however large improvements may only be possible
by changing the problem. Making non-contextual bindings
(see Type/Function Bindings) means the information can be static which could
allow it to be automatically located and reduce the issue.

The only way to remove the life-time limit would be to avoid unwinding the
stack. If the exception handling code only removes stack frames during
clean-up, most of these problems go away.
Resumption exceptions already does this. Termination exceptions might be able
to work if you unwind after the handler runs.

Exception Matching and Hierarchy
--------------------------------
When exceptions are caught, the primary tool to see if a given handler
should handle a given exception is hierarchical matching.

In terms of the underlying paradigms, this is the most fundamental mismatch,
because it is borrowed from object-orientated programming, and Cforall is not
an object-orientated programming language. But we added a limited system that
mimics that, the virtual type hierarchy, and currently exceptions are the
only supported use of that system. Also it isn't entirely implemented and
would require a lot of features with relatively narrow use cases to implement it.

Which does make updating it based on experience a bit harder, so far the only
real problem is allocating memory in the header. (Currently addressed by the
cfa_linkonce attribute.) But the missing implementation highlights that maybe
we don't need the full hierarchy.

If you can handle the exception fully, you can catch the leaf exception and
run the handling code. If it doesn't matter because the guarded code is
isolated, then you catch any exception, log it, and then move on.
In other words, without the hierarchy and just exact matches and a separate
catch all, that could handle the vast majority of cases.

Even within this solution, there are variants in what do these two cases
look like. The exact match case is fairly simple, it may not even have to
pass assertions because the concrete type is known at both locations.
The catch-all case is the tricky one, because we still have to manipulate
the exception in a generic form. It does however mean there is a single
generic interface in that case, which might still be simpler than the current
system.

(Also in this two layer system, it might also be worth revisiting checked
exceptions for the exact match cases, because there is a more direct than
usual logical binding there.)