Compile-time type hierarchy information in pattern switch
Brian Goetz
brian.goetz at oracle.com
Fri Apr 6 12:48:50 UTC 2018
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
>
More information about the amber-spec-experts
mailing list