Compile-time type hierarchy information in pattern switch

[Brian Goetz]

This may be O(n), but its not really something I want to do when linking 
a call site...

On 4/6/2018 5:01 AM, Peter Levart wrote:
>
>
> On 04/05/2018 11:20 PM, Peter Levart wrote:
>>
>>
>> On 04/05/18 22:28, Remi Forax wrote:
>>> the way to detect it is to use the DAG of the supertypes (lazily 
>>> constructed*), from the last to the first case, the idea is to 
>>> propagate the index of down to the super types, if during the 
>>> propagation, you find a supertype which is also a case and with an 
>>> index lower that the currently propagated, then it's a failure.
>>>
>>> Rémi
>>>
>>> * you do not have to actually create the DAG, just be able to 
>>> traverse it from the subtype to the supertypes.
>>
>> Yes, this idea is similar to mine. We just have to find a conflict 
>> between subtype relationships and compile time order of cases which 
>> could be viewed as forming implicit pair-by-pair relationships of 
>> consecutive cases. If there's a cycle, we have a conflict.
>>
>
> And Remi's algorithm is of course the best implementation of this 
> search. Here's a variant that does not need an index, just a set of 
> types:
>
> start with an empty set S
> for each case type T from the last case up to the first:
>     if S contains T:
>         bail out with error
>     add T and all its supertypes to S
>
> The time complexity of this algorithm is O(n). It takes at most n * k 
> lookups into a (hash)set where k is an average number of supertypes of 
> a case type. Usually, when case types share common supertypes not 
> far-away, the algorithm can prune branches in type hierarchy already 
> visited. Implementation-wise, if the algorithm uses a HashMap, mapping 
> visited type to case type it was visited from (back to Remi's index of 
> case), it can also produce a meaningful diagnostic message, mentioning 
> precisely which two cases are in wrong order according to type hierarchy:
>
>     Class<?>[] caseTypes = ...;
>     TypeVisitor visitor = new TypeVisitor();
>     for (int i = caseTypes.length - 1; i >= 0; i++) {
>         visitor.visitType(caseTypes[i]);
>     }
>
>     class TypeVisitor extends HashMap<Class<?>, Class<?>> {
>
>         void visitType(Class<?> caseType) {
>             Class<?> conflictingCaseType = putIfAbsent(caseType, 
> caseType);
>             if (conflictingCaseType != null) {
>                 throw new IllegalStateException(
>                     "Case " + conflictingCaseType.getName() +
>                     " matches a subtype of what case " + 
> caseType.getName() +
>                     " matches but is located after it");
>             }
>             visitSupertypes(caseType, caseType);
>         }
>
>         private void visitSupertypes(Class<?> type, Class<?> caseType) {
>             Class<?> superclass = type.getSuperclass();
>             if (superclass != null && putIfAbsent(superclass, 
> caseType) == null) {
>                 visitSupertypes(superclass, caseType);
>             }
>             for (Class<?> superinterface : type.getInterfaces()) {
>                 if (putIfAbsent(superinterface, caseType) == null) {
>                     visitSupertypes(superinterface, caseType);
>                 }
>             }
>         }
>     }
>
>
> Regards, Peter
>