Compile-time type hierarchy information in pattern switch
Peter Levart
peter.levart at gmail.com
Thu Apr 5 21:06:50 UTC 2018
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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.openjdk.java.net/pipermail/amber-spec-experts/attachments/20180405/8f63a973/attachment.html>
More information about the amber-spec-experts
mailing list