Compile-time type hierarchy information in pattern switch

[Brian Goetz]

> 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. 

Perhaps I'm dense, but I don't see this.  Suppose I have completely 
unrelated interfaces I, J, K, and L.  The user says:

     case I:
     case J:
     case K:
     case L:

which is fine because they're unordered.  At runtime, any of the 
following type relations could have been injected:

     J <: I, K <: I, L <: I
     K <: J, L <: J
     L <: K

and these would cause the switch to be misordered (and would have been 
rejected at compile time.)

How am I to detect any of these with just three comparisons?  If I pick 
the obvious n-1 (compare each to their neighbor) I wouldn't detect any 
of { L <: J, K <: I, L <: I }.

Skipping ahead, yes, guards do play part in the ordering, and (a) we 
can't detect changes to data in at runtime and (b) we can't even 
necessarily order the guards.  But we can detect changes to type tests 
at runtime.  The question is whether we should.

> 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?

Our story here is straightforward; we lower a switch whose labels are 
patterns to a switch whose labels are ints, and encode the patterns (or 
parts of them) as the static bootstrap arguments of the classifier 
bootstrap (just a more sophisticated version of what we do for longs, 
strings, and enums, as discussed previously.)  The classifier spits out 
a number, and int switch mechanics does the rest.  The question is to 
what degree we can rely on the compile-time assertion that the inputs 
are topologically sorted.