Subject: Re: bug#78989: 31.0.50; classes and methods inheritance (defclass) seq-contains-p

From: Stefan Monnier <[email-masked]>
Date: Sat, 12 Jul 2025 11:08:53 -0400

> I'm convinced both of your patches will still produce
> topologically inconsistent orderings.

Not without emitting a warning along the way.

> That is because the information necessary to figure out how to break
> an artificial "cycle" is lost the second we stop considering the
> inheritance graph and limit ourselves to previously-linearized
> ancestor lists.

Indeed.  That's a choice between losing monotonicity and suffering from
artificial-cycles.  You can't avoid both.  But years of experience in
other languages told us that it's easier for programmers to deal with
artificial cycles than with loss of monotonicity.

In large part it's the "obvious" consequence that the artificial cycles
are closer to the origin of the problem so it's easier to
explain/describe/understand/control.

>>> but not to give up as long as there is a topologically
>>> consistent ordering.
>> I don't think it's worth the trouble, and most other languages out there
>> don't either: just complain and let the programmer fix the problem.
> Fixing the problem means exporting your class hierarchy and running
> tsort.

No, you just look at the emitted warning.  E.g. for Pierre's code you
get warnings like:

    Inconsistent hierarchy: ((title widobj abstitle
    eieio-default-superclass record atom t) (widobj title))

So you see that there's a weird situation where OT1H `title` comes
before `widobj` and OTOH it comes after.  Looking at the code you see

    (defclass interface (widobj title) ())

and you go "hmm, maybe I should swap those two".

    Inconsistent hierarchy: ((interfacelist widgetlist interface title
    widobj baselist state sortable abstitle eieio-default-superclass
    record atom t) (widgetlist loadable interfacelist))

Same here with `interfacelist` and `widgetlist` and you notice

    (defclass father (widgetlist loadable interfacelist) ())

in the code, and you fix it.

    Inconsistent hierarchy: ((state interface title widobj abstitle
    eieio-default-superclass record atom t) (interface title widobj
    baselist state sortable abstitle eieio-default-superclass record
    atom t))

Same here with `state` and `interface`, but here the origin is
admittedly less obvious.  We could try and help the user further by
clarifying where those lists come from: IIRC the first list comes from
`loadable` while the second comes from `interfacelist`.  So the
programmer has to go and add `state interface` (or the reverse) to some
of the `defclass`es to force a particular linearization.

[ FWIW, with my patch, Pierre's code works "correctly" (beside
  emitting the above warnings) as is, thanks to the more graceful
  degradation.  ]

> It's a tedious task that should come with some benefits, and I'm
> not convinced refined ancestor lists even constitute a benefit.

The benefit is exactly what Pierre complained above: it makes sure that
if something works on `father` it will work identically on `son` (when
there's no matching method on `mother`, obviously).

> Situations like
>
>     (defclass a () ())
>     (defclass b (a) ())
>     (defclass c (a) ())
>     (defclass d (b c) ())
>     (cl-defgeneric f (x) 'x)
>     (cl-defgeneric f ((x b)) 'b)
>     (cl-defgeneric f ((x c)) 'c)
>     (f (d))
>
> are likely bugs.

I tend to agree, but it's much less likely when you change it to

    (cl-defgeneric f ((x b)) (cons 'b (cl-call-next-method)))
    (cl-defgeneric f ((x c)) (cons 'c (cl-call-next-method)))

> If we can, we should warn about them.

I wouldn't necessarily be opposed to such a patch, tho I suspect it
might not be trivial to keep it cheap enough, not too chatty, and with
an acceptable "code complexity vs benefit" tradeoff.

> I don't think of a class's ancestors as being in any particular order
> beyond that imposed by the DAG, which makes no distinction between
> (defclass d (b c) ()) and (defclass d (c b) ()), so being forced to
> order ancestors myself simply makes class hierarchies tedious to
> work with.

There's no free lunch in this respect.  We can improve one side at the
code of another side.  I haven't seen yet any proposal that's clearly
better than the options that have been known since the days of the Dylan
paper, nor have I seen any reason why the ELisp context would favor
different tradeoffs, so I'd rather stick to the known "least
bad" solution.

> Please, let's signal an error here.

Pierre's code has worked in EIEIO since "forever" (IOW probably since
long before he started writing it), despite the weird hierarchy.  So,
I wouldn't be surprised if signaling an error breaks existing
working code.

For this reason, I prefer starting with emitting a warning.
Maybe we can upgrade that to an error in due time.

> The patch below cannot possibly work: merge-ordered-lists cannot
> distinguish the dependencies it must keep for topological consistency
> from those it may drop to break the artificial cycles.  It doesn't
> have that information.

AFAIK, EIEIO has never really obeyed topological consistency (IIRC
until Emacs-25 it used a depth-first traversal linearization, with ways
for the programmer to request optionally breadth-first or C3).

>> The Dylan algorithm would signal an error on his code.
>> CLOS would as well:
>>
>>     % clisp
>>     [...]
>>     [1]> (defclass my-a () ())
>>     #<STANDARD-CLASS MY-A>
>>     [2]> (defclass my-b (my-a) ())
>>     #<STANDARD-CLASS MY-B>
>>     [3]> (defclass my-y (my-a my-b) ())
>>
>>     *** - DEFCLASS MY-Y: inconsistent precedence graph, cycle
>>           (#<STANDARD-CLASS MY-B> #<STANDARD-CLASS MY-A>)
>>     The following restarts are available:
>>     ABORT          :R1      Abort main loop
>>     Break 1 [4]>
>
> But (defclass my-y (my-b my-a)) works, I hope.

Yes, of course.

>>> Adding additional constraints (passing another list to
>>> merge-ordered-lists) will make this problem worse, not better.
>> Depends what you mean by "this problem".  Maybe it signals hierarchy
> This bug is caused by merge-ordered-lists not throwing an error.  It
> cannot do anything reasonable to break the cycle because it'll have to
> throw away a link in (at least) one of the linearized ancestor lists.
> It has no way of knowing whether the link it throws away is essential
> for maintaining topological order (a parent-child relationship) or
> merely the result of previous linearization.

That's right.  If we emit the "Inconsistent hierarchy" warning, we're
operating in "degraded mode: if your code still works, consider yourself
lucky".

        Stefan