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 00:40:42 +0000

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

>>> FWIW, `cl--class-allparents` does not promise a general topological sort.
>> It doesn't?
>
> No, you can have classes A and B with (linearized) parents:
>
>     (A .. C .. D .. t)
>
>     (B .. D .. C .. t)

I think it'd be helpful to express that in terms of defclass statements
and expected behavior of cl-defmethod.

The paper you cite below proposes to throw an error in some cases where
there is a topologically consistent ordering; we can do that (though I
think it'd be an annoyance), but what we should never do is to return a
topologically inconsistent ordering, as we do now, with or without your
patch.

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, but not to give up as long as there is a topologically
consistent ordering.

IOW, if a is a child of b, I think it's acceptable for
(cl--class-allparents a) not to be a refinement of (cl--class-allparents
b), if that's the only way we can make them topologically consistent.

But I may be wrong, and our code may rely on this refinement property.

This will result in behavior being a little difficult to predict in
cases where there are two conflicting cl-defmethods and neither one is
clearly more specific than the other, but I think that can safely be
made undefined behavior; well-written code shouldn't have such
conflicting definitions.

> 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.  If
we want to impose it, we clearly need to modify defclass (in addition to
cl--class-allparents) to complain about it.

What is there to gain from such a restriction?  Is it really just to
make cl-defmethod behave more predictably in weird corner cases?

>> Then the cl-generic code won't work...
>
> AFAIK it's good enough for most languages, so I hope it should be good
> enough for us.

It's certainly not true that "most" languages will give you a
linearization in which a parent is considered more specific than a
child.

> - We should emit some warning when faced with such an
>   inconsistent hierarchy.
>   [ Note: the hierarchy is not globally inconsistent, but it becomes
>     inconsistent because linearization is performed
>     piecemeal/locally/modularly, so by the time we're faced with an
>     inconsistency we'd have to go back and choose different
>     linearizations for some of the existing classes.  ]

I'm not sure how you define "globally inconsistent". The hierarchy is
"inconsistent" in the sense that the Dylan algorithm would throw the
"Inconsistent precedence graph" error; it is consistent in the sense
that there are no cycles.

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

> - We should try harder to degrade gracefully in the face of inconsistent
>   hierarchies, e.g. avoiding multiple occurrences of the same parent or
>   with `t` in the middle, ...

We must not return a topologically inconsistent linearization, ever.
It's much better to provide an error-function to merge-ordered-lists
which throws an error than to invoke inappropriate methods.

> - We should give more control to the programmer to impose a particular
>   choice of linearization.  To mimic what CLOS does, we could use the
>   patch below.

IMHO, most programmers don't really care about specifying superclasses
in any particular order. They just want an order that's topologically
consistent, and I assume many of them would be quite upset if we
informed them they have to tsort their superclasses manually to satisfy
a "consistency" property they never depend on.

> diff --git a/lisp/emacs-lisp/cl-preloaded.el b/lisp/emacs-lisp/cl-preloaded.el
> index 263a9b85225..71b4a863b30 100644
> --- a/lisp/emacs-lisp/cl-preloaded.el
> +++ b/lisp/emacs-lisp/cl-preloaded.el
> @@ -285,8 +285,14 @@ cl--copy-slot-descriptor
>
>  (defun cl--class-allparents (class)
>    (cons (cl--class-name class)
> -        (merge-ordered-lists (mapcar #'cl--class-allparents
> -                                     (cl--class-parents class)))))
> +        (let* ((parents (cl--class-parents class))
> +               (aps (mapcar #'cl--class-allparents parents)))
> +          (if (null (cdr aps)) ;; Single-inheritance fast-path.
> +              (car aps)
> +            (merge-ordered-lists
> +             ;; Add the list of immediate parents, to control which
> +             ;; linearization is chosen.  doi:10.1145/236337.236343
> +             (nconc aps (list (mapcar #'cl--class-name parents))))))))

Adding additional constraints (passing another list to
merge-ordered-lists) will make this problem worse, not better.

The important part in the paper you cite, and the two algorithms it
presents (in Appendix A and Appendix B), is that they both throw errors
when encountering "inconsistent" hierarchies.  We should do the same, if
we cannot agree that a topological ordering which is not a refinement of
the parents' order is better in this case.

diff --git a/lisp/emacs-lisp/cl-preloaded.el b/lisp/emacs-lisp/cl-preloaded.el
index 263a9b85225..b3a4540af46 100644
--- a/lisp/emacs-lisp/cl-preloaded.el
+++ b/lisp/emacs-lisp/cl-preloaded.el
@@ -286,7 +286,9 @@ cl--copy-slot-descriptor
 (defun cl--class-allparents (class)
   (cons (cl--class-name class)
         (merge-ordered-lists (mapcar #'cl--class-allparents
-                                     (cl--class-parents class)))))
+                                     (cl--class-parents class))
+                             (lambda (_lists)
+                               (error "The superclasses in a defclass were specified in the wrong order.  The tsort program may help.")))))
 
 (cl-defstruct (built-in-class
                (:include cl--class)

(Yes, I agree that error message isn't very helpful.  I don't really
think it can be made to be helpful).)

Pip

Previous Next

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