Compile-time type hierarchy information in pattern switch
Peter Levart
peter.levart at gmail.com
Fri Apr 6 09:01:23 UTC 2018
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-observers
mailing list