Compile-time type hierarchy information in pattern switch

[Peter Levart]

Hi,

On 04/04/2018 07:07 PM, Brian Goetz wrote:
> The intended implementation strategy is to lower complex switches to 
> densely-numbered `int` switches, and then invoke a classifier function 
> that takes a target and returns the int corresponding to the lowered 
> case number.  The classifier function will be an `invokedynamic`, 
> whose static bootstrap will contain a summary of the patterns.  (We've 
> already done this for switches on strings, enums, longs, non-dense 
> ints, etc.)
>
> To deliver an early error, that means that (a) the compiler must 
> encode through the static argument list all the assumptions it needs 
> verified at runtime (e.g., `String <: Object`), and (b) at linkage 
> time (the first time the switch is executed), those have to be tested.
>
> Doing so is plenty easy, but there's a startup cost, which could be as 
> bad as _O(n^2)_, if I have to validate that no two case labels are 
> ordered inconsistently with subtyping.

Not necessarily. O(n log n) at worst for stable-sorting n cases which, 
if already sorted in compile time (i.e. no subtype changes between 
compile and link time), are resorted using just n-1 comparisons.

That's if you want to "fix" the order of cases at link-time in order to 
compute optimal dispatch logic. If you only want to verify and bail-out 
if they are not sorted already (i.e. you only accept changes in type 
hierarchy that don't change order of cases), you always need just n-1 
comparisons.

The question is whether you only want to re-order / check-order 
according to type hierarchy or also according to other aspects of 
"dominance", for example:

case Point p where (p.x >= 0 && p.y >= 0):
...
case Point p where (p.x >= 0):
...

Other aspects of dominance usually don't change between compile and link 
time, so stable-sorting cases could take just type hierarchy into 
account, unless you also allow type-hierarchy based conditions in where 
patterns, for example:

case Holder h where (h.value instanceof TypeA):
...
case Holder h where (h.value instanceof TypeB):
...

Another problem with re-ordering cases at link time is when you support 
fall-through. What are fall-through(s) in a switch with re-ordered 
cases? For example:

interface A {}
interface B extends A {}

switch (x) {
     case B b:
         ...
         // fall-through...
     case A a:
         A ab = ... ? a : b;

         ...

What happens when you remove A from supertypes of B in a separately 
compiled code:

interface A {}
interface B {}

Perhaps there's no need to worry about this as verifier would already 
catch such invalid code during runtime. So fall-through(s) could just 
stay the same even if cases are virtually reordered for the purpose of 
computing dispatch logic. The fall-through logic could sometimes survive 
changes in type hierarchy unnoticed by verifier but would give 
questionable results when executed. But that could be said for any 
logic, not necessarily concerned with switch statements.

Here's some experiment I played with that clearly separates 
compile-time, link-time and run-time parts of logic and is just API. You 
can even simulate the effects of adding subtype relationship(s) between 
compile-time of switch and link-time:

http://cr.openjdk.java.net/~plevart/misc/TypeSwitch/TypeSwitch.java

Regards, Peter

>
> A possible mitigation is to do the check as a system assertion, which 
> only gets run if we are run with `-esa`; we then might still have some 
> static code bloat (depending on how we encode the assumptions), but at 
> least skip the dynamic check most of the time.
>
> On 4/4/2018 1:01 PM, Mark Raynsford wrote:
>> I'm still giving thought to everything you've written, but I am
>> wondering: How feasible is it to get the above to fail early with an
>> informative exception/Error?
>