The Dylan paper does describe what hierarchies will be inconsistent for C3, it just isn't as straightforward about it as perhaps the C3 pod should be. The first obvious constraint is that your hierarchy can have no inheritance loops (the inheritance graph must be acyclic). Algorithm::C3 reports this error distinctly with a message like: "Infinite loop detected in parents of 'A': [A B C A]".
The other is related to monotonicity. To quote the Dylan paper: "A monotonic linearization is one in which every property inherited by a class is inherited or defined by one of its direct superclasses; that is, an inherited property cannot skip over all of the direct superclasses. This means that the linearization of a class must be an extension without reordering of the linearizations of all of its superclasses." In other words, C3's algorithm is recursive (the C3 linearization of any given class is generated from the C3 linearization of the parent classes), and if the C3 linearizations of any two (or more) parent classes contain two (or more) common superclasses, those superclasses must appear in the same order in all superclasses. If they don't, then there is no way for C3 to comply with its monotonicity constraint with respect to all superclass linearizations.
The simplest example of a graph that fails this constraint:Note that it is only the ordering that matters - not whether other classes are present between the ones in question. This example is fine:
Hmm I should add that although rarer, I think you can generate an invalid hierarchy via making it impossible to simultaneously satisfy both monotonicity and local precedence order at the same time. Example:
The issue in the second case is that C3 gaurantees preservation of local precedence order (in other words, the ordering of @ISA won't be violated), so C3 requires on the one hand that C come before B due to the local precedence in A's @ISA, but due to B inheriting C this would violate monotonicity. (CB at the start of A's linearization vs BC at the start of B's linearizaton).
