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.
