GNU bug report logs - #78989
31.0.50; classes and methods inheritance (defclass) seq-contains-p

Previous Next

Full log

View this message in rfc822 format

From: Pip Cet <pipcet <at> protonmail.com>
To: Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: 78989 <at> debbugs.gnu.org, Eli Zaretskii <eliz <at> gnu.org>, "Pierre L. Nageoire" <devel <at> pollock-nageoire.net>
Subject: bug#78989: 31.0.50; classes and methods inheritance (defclass) seq-contains-p
Date: Sat, 12 Jul 2025 09:28:01 +0000

"Stefan Monnier" <monnier <at> iro.umontreal.ca> writes:

>>> in which case inheriting from both A and B is simply not supported
>>> because we can't create a merged linearization of the parents which
>>> is monotonic (i.e. obeys the existing linearization in both parents).
>> That's a very strong restriction on the possible inheritance graphs.
>
> It's not: as long as there's no cycle, it's always possible to change
> the details of the definition of A and/or B such that they still have
> the same set of parents but their parents' ordering can be
> merged consistently.

Of course: you just have to perform a tsort yourself rather than doing
it in merged-ordered-lists.

>> My proposal is to use the order that superclasses were listed in to
>> break the tie if there are several topologically consistent orderings to
>> choose from,
>
> That's what my patch does, yes.

It's not, sorry.  I'm convinced both of your patches will still produce
topologically inconsistent orderings.  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.

>> 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.  It's a tedious task that should come with some benefits, and I'm
not convinced refined ancestor lists even constitute a benefit.

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.  If we can, we should warn about them.

>> What is there to gain from such a restriction?  Is it really just to
>> make cl-defmethod behave more predictably in weird corner cases?
>
> It lets the language provide clean semantics, yes.

The approach I proposed (which is too slow to use in general) can be
made to provide well-defined semantics, as well.

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.

>> If we want this restriction, we need to die unconditionally when
>> encountering cases that we consider "inconsistent"; a warning is not
>> enough, and the current behavior of doing something random such as
>> considering the universal class more specific than a user-defined class
>> is simply a bug.
>
> I think we can tweak the current code so we don't get such
> pathologically poor behavior as Pierre encountered (e.g. patch below),
> so I'm not sure it's worth signaling an error, but I'm not fundamentally
> opposed to signaling an error.

Please, let's signal an error here.  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.

I'd still prefer to fall back to a well-defined (i.e. no hash tables and
associated randomness) topological sort in those cases where there is no
merged linearization, if only to give the user specific instructions
about which defclass must be changed and how.  But that's a nice feature
to have, the right fix for now is to signal an error.

>> I don't think there's anything "inconsistent" about the code the OP
>> provided; it should just work, without any reordering of superclasses.
>
> 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.

>> 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.

> inconsistencies more often, yes, but it makes them more deterministic,
> and there's always a way for the programmer to change the parents arg in
> `defclass`es so as to eliminate the inconsistencies (whereas IIRC with
> the current code, it's not always possible to eliminate the
> inconsistencies by changing only the parents args of `defclass`es).

Your patch does not signal hierarchy inconsistencies, it tries to "fix"
them.  We can't.

Pip

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.