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?
