On 04/05/18 21:42, Brian Goetz wrote:
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 }.
You're right. Linear sorting would not help as there's no total order
that could be derived from subtyping relationships.
But as you say at the end, subtyping relationships form a directed
acyclic graph on which you can perform topological sorting in linear time.
Let's start with a list of cases that have already been ordered
topologically at compile time. Say I, J, K, L (as in your example above).
The types could be completely unrelated or there could be type
relationships among them. Let's add to them synthetic "subtype"
relationships (marked with <. to distinguish them from real subtype
relationships <:) according to compile-time order of cases):
I <. J
J <. K
K <. L
Together with real direct subtype relationships, those form a graph. We
just have to find out if this graph is acyclic or not. If it does not
have a cycle, the order of case(s) is still OK and the switch is still
valid. Otherwise the subtype relationships have changed in a way that
makes the compile-time order of cases invalid. Finding cycle can be
performed in linear time.
Have I missed something this time too?
Regards, Peter
