Compile-time type hierarchy information in pattern switch

[Peter Levart]

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>