Compile-time type hierarchy information in pattern switch

[Peter Levart]

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