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
