GNU bug report logs - #67008
30.0.50; Multiple major mode parents

Previous Next

To add a comment to this bug, you must first unarchive it, by sending
a message to control AT debbugs.gnu.org, with unarchive 67008 in the body.
You can then email your comments to 67008 AT debbugs.gnu.org in the normal way.

Toggle the display of automated, internal messages from the tracker.

Message #5 received at submit <at> debbugs.gnu.org (full text, mbox):

From: Stefan Monnier <monnier <at> iro.umontreal.ca>
To: bug-gnu-emacs <at> gnu.org
Subject: 30.0.50; Multiple major mode parents
Date: Thu, 09 Nov 2023 00:38:22 -0500

Package: Emacs
Version: 30.0.50


While it seems difficult to add support for multiple inheritance to
`define-derived-mode`, it's fairly easy to allow a major mode to declare
itself the spiritual heir of various other major modes beside the one
from which it actually inherits.

We already have some very basic such cases in our own code:
- `locate-mode` inherits from `special-mode` but declares itself
  as a child of `dired-mode`.
- CEDET declares that `c++-mode` is a child of `c-mode`.

I'd been toying with this idea for a while because it has seemed useful
a few times, tho until now there seemed to be good enough alternatives.
But in order to really support AUCTeX modes well, we do need such
a thing: we need `LaTeX-mode` to be able to declare itself as a child
of `latex-mode` (even tho it does not inherit from it) so that
directory-local variables are properly applied to it, which is
a fairly common use case.

I pushed to the branch `feature/derived-mode-add-parents` a bunch of
patches which add support for such limited form of `multiple
inheritance`.

The patch is fairly large because it goes through all the code that
uses the `derived-mode-parent` property and adjusts it to use
a few new functions:

- `derived-mode-set-parent` and `derived-mode-all-parents` cover
  basically all previous uses of the `derived-mode-parent` property.
- `derived-mode-add-parents` to declare additional parents.

The patch also consolidates the code that linearizes the inheritance
hierarchy of CL classes, EIEIO classes, and major modes.

You can see below the corresponding commit log.
There are no doc (or etc/NEWS) changes yet.
Any comment/objection?


        Stefan


commit 19445b6b7bb04e44e39ef2e39a620bd3eadb0acd
Author: Stefan Monnier <monnier <at> iro.umontreal.ca>
Date:   Wed Nov 8 11:32:27 2023 -0500

    subr.el: Provide a functional API around `derived-mode-parent`
    
    The `derived-mode-parent` property should be an implementation detail,
    so we can change it more easily.  To that end, add functions to set and
    query it.
    
    * lisp/subr.el (derived-mode-all-parents): New function.
    (provided-mode-derived-p): Use it.
    (derived-mode-set-parent): New function.

commit 9c6b22bb3e2126a1ab355b81ae4268ac53c2b6fe
Author: Stefan Monnier <monnier <at> iro.umontreal.ca>
Date:   Wed Nov 8 14:20:09 2023 -0500

    (derived-mode-all-parents): Speed up with a cache
    
    Most uses of the mode hierarchy don't really need to construct the
    list, they just need to iterate over it.  With single inheritance
    we could do it just by jumping up from a mode to its parent,
    but to support the upcoming multiple inheritance we'd need a more
    complex and costly iterator.
    Luckily, the inheritance graph is mostly static so we can cache
    the list of all parents, making `derived-mode-all-parents` cheap
    enough to be the basis of iteration and keeping the API very simple.
    
    * lisp/subr.el (derived-mode-all-parents): Cache the result.
    (derived-mode--flush): New function.
    (derived-mode-set-parent): Use it.

commit 492920dd5b469e18596a49a62fbefd8ad2cc518b
Author: Stefan Monnier <monnier <at> iro.umontreal.ca>
Date:   Wed Nov 8 22:53:39 2023 -0500

    Use new `derived-mode-all/set-parents` functions.
    
    Try and avoid using the `derived-mode-parent` property directly
    and use the new API functions instead.
    
    * lisp/emacs-lisp/derived.el (define-derived-mode):
    Use `derived-mode-set-parent`.
    
    * lisp/loadhist.el (unload--set-major-mode):
    * lisp/info-look.el (info-lookup-select-mode):
    * lisp/ibuf-ext.el (ibuffer-list-buffer-modes):
    * lisp/files.el (dir-locals--get-sort-score):
    * lisp/emacs-lisp/cl-generic.el (cl--generic-derived-specializers):
    Use `derived-mode-all-parents`.

commit 5afa55a946a0271c624359e9de5d62bcaf39729b
Author: Stefan Monnier <monnier <at> iro.umontreal.ca>
Date:   Mon Nov 6 16:57:05 2023 -0500

    subr.el: Add multiple inheritance to `derived-mode-p`
    
    Add the ability for a major mode to declare "extra parents" in
    addition to the one from which it inherits.
    
    * lisp/subr.el (derived-mode-add-parents): New function.
    (derived-mode-all-parents): Adjust accordingly.

commit 8323394bc801e01dedd95e0ff8d573dd1f5e34ba
Author: Stefan Monnier <monnier <at> iro.umontreal.ca>
Date:   Mon Nov 6 19:05:40 2023 -0500

    Use `derived-mode-add-parents` in remaining uses of `derived-mode-parent`
    
    Until now multiple inheritance wasn't really used, but some ad-hoc
    code went a bit beyond the normal uses of the mode hierarchy.
    Use the new multiple inheritance code to replace that ad-hoc code,
    thereby eliminating basically all remaining direct uses of the
    `derived-mode-parent` property.
    
    CEDET had its own notion of mode hierrchy using `derived-mode-parent`
    as well as its own `mode-local-parent` property set via
    `define-child-mode`.
    `derived-mode-add-parents` lets us reimplement `define-child-mode`
    such that CEDET can now use the normal API functions.
    
    * lisp/locate.el (locate-mode): Use `derived-mode-add-parents`.
    
    * lisp/cedet/mode-local.el (get-mode-local-parent): Declare obsolete.
    (mode-local-equivalent-mode-p, mode-local-use-bindings-p): Make them
    obsolete aliases.
    (mode-local--set-parent): Rewrite to use `derived-mode-add-parents`.
    Declare as obsolete.
    (mode-local-map-mode-buffers): Use `derived-mode-p`.
    (mode-local-symbol, mode-local--activate-bindings)
    (mode-local--deactivate-bindings, mode-local-describe-bindings-2):
    Use `derived-mode-all-parents`.
    
    * lisp/cedet/srecode/table.el (srecode-get-mode-table):
    * lisp/cedet/srecode/find.el (srecode-table, srecode-load-tables-for-mode)
    (srecode-all-template-hash): Use `derived-mode-all-parents`.
    
    * lisp/cedet/srecode/map.el (srecode-map-entries-for-mode):
    * lisp/cedet/semantic/db.el (semanticdb-equivalent-mode):
    Use `provided-mode-derived-p` now that it obeys `define-child-mode`.

commit 0939433b63ab45d18fe1a2db706f66efe7307261
Author: Stefan Monnier <monnier <at> iro.umontreal.ca>
Date:   Tue Nov 7 18:57:03 2023 -0500

    Move EIEIO's C3 linearization code to `subr.el`
    
    The code was used to linearize the EIEIO class hierarchy, since
    it results in saner results than things like BFS or DFS.
    By moving it to `subr.el` we get to benefit from that same
    advantage both in `cl--class-allparents` and
    in `derived-mode-all-parents`.
    
    * lisp/subr.el (merge-ordered-lists): New function.
    (derived-mode-all-parents): Use it to improve parent ordering.
    
    * lisp/emacs-lisp/eieio-core.el (eieio--c3-candidate)
    (eieio--c3-merge-lists): Delete functions, replaced by
    `merge-ordered-lists`.
    (eieio--class-precedence-c3): Use `merge-ordered-lists`.
    
    * lisp/emacs-lisp/cl-preloaded.el (cl--class-allparents):
    Use `merge-ordered-lists` to improve parent ordering.
    * lisp/emacs-lisp/cl-macs.el (cl--struct-all-parents): Delete function.
    (cl--pcase-mutually-exclusive-p): Use `cl--class-allparents` instead.

Message #8 received at 67008 <at> debbugs.gnu.org (full text, mbox):

From: Yuan Fu <casouri <at> gmail.com>
To: Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: 67008 <at> debbugs.gnu.org, Ikumi Keita <ikumi <at> ikumi.que.jp>
Subject: Re: bug#67008: 30.0.50; Multiple major mode parents
Date: Wed, 8 Nov 2023 23:43:10 -0800

> On Nov 8, 2023, at 9:38 PM, Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors <bug-gnu-emacs <at> gnu.org> wrote:
> 
> Package: Emacs
> Version: 30.0.50
> 
> 
> While it seems difficult to add support for multiple inheritance to
> `define-derived-mode`, it's fairly easy to allow a major mode to declare
> itself the spiritual heir of various other major modes beside the one
> from which it actually inherits.
> 
> We already have some very basic such cases in our own code:
> - `locate-mode` inherits from `special-mode` but declares itself
>  as a child of `dired-mode`.
> - CEDET declares that `c++-mode` is a child of `c-mode`.
> 
> I'd been toying with this idea for a while because it has seemed useful
> a few times, tho until now there seemed to be good enough alternatives.
> But in order to really support AUCTeX modes well, we do need such
> a thing: we need `LaTeX-mode` to be able to declare itself as a child
> of `latex-mode` (even tho it does not inherit from it) so that
> directory-local variables are properly applied to it, which is
> a fairly common use case.
> 
> I pushed to the branch `feature/derived-mode-add-parents` a bunch of
> patches which add support for such limited form of `multiple
> inheritance`.
> 
> The patch is fairly large because it goes through all the code that
> uses the `derived-mode-parent` property and adjusts it to use
> a few new functions:
> 
> - `derived-mode-set-parent` and `derived-mode-all-parents` cover
>  basically all previous uses of the `derived-mode-parent` property.
> - `derived-mode-add-parents` to declare additional parents.
> 
> The patch also consolidates the code that linearizes the inheritance
> hierarchy of CL classes, EIEIO classes, and major modes.
> 
> You can see below the corresponding commit log.
> There are no doc (or etc/NEWS) changes yet.
> Any comment/objection?

Great work! Thanks! I need to find some time to read through the changes, but sounds promising.

Yuan

Message #11 received at 67008 <at> debbugs.gnu.org (full text, mbox):

From: Dmitry Gutov <dmitry <at> gutov.dev>
To: Stefan Monnier <monnier <at> iro.umontreal.ca>, 67008 <at> debbugs.gnu.org
Cc: Ikumi Keita <ikumi <at> ikumi.que.jp>
Subject: Re: bug#67008: 30.0.50; Multiple major mode parents
Date: Sat, 11 Nov 2023 02:01:57 +0200

On 09/11/2023 07:38, Stefan Monnier via Bug reports for GNU Emacs, the 
Swiss army knife of text editors wrote:
> While it seems difficult to add support for multiple inheritance to
> `define-derived-mode`, it's fairly easy to allow a major mode to declare
> itself the spiritual heir of various other major modes beside the one
> from which it actually inherits.

I think it would help with certain customizations which check whether a 
mode is derived from e.g. js-mode.

But whatever code that runs in parent-mode-hook won't run in the 
"derived modes" that use the new mechanism, would it?

I wonder which of these two problems have a bigger impact for the 
seamless migration to ts modes.

Message #14 received at 67008 <at> debbugs.gnu.org (full text, mbox):

From: Stefan Monnier <monnier <at> iro.umontreal.ca>
To: Dmitry Gutov <dmitry <at> gutov.dev>
Cc: 67008 <at> debbugs.gnu.org, Ikumi Keita <ikumi <at> ikumi.que.jp>
Subject: Re: bug#67008: 30.0.50; Multiple major mode parents
Date: Fri, 10 Nov 2023 23:23:41 -0500

> I think it would help with certain customizations which check whether a mode
> is derived from e.g. js-mode.
> But whatever code that runs in parent-mode-hook won't run in the "derived
> modes" that use the new mechanism, would it?

The new functionality only affects `derived-mode-p` checks.
For mode hooks, it's up to the mode to run extra hooks if it deems them desirable.


        Stefan

Message #17 received at 67008 <at> debbugs.gnu.org (full text, mbox):

From: Mattias Engdegård <mattias.engdegard <at> gmail.com>
To: Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: 67008 <at> debbugs.gnu.org, Ikumi Keita <ikumi <at> ikumi.que.jp>,
 Yuan Fu <casouri <at> gmail.com>, Dmitry Gutov <dgutov <at> yandex.ru>
Subject: Re: bug#67008: 30.0.50; Multiple major mode parents 
Date: Sat, 11 Nov 2023 11:14:47 +0100

Thank you, I can see how this would be useful.

>     * lisp/subr.el (merge-ordered-lists): New function. 

That's nice to have, indeed.
The implementation is a bit imperative (and quadratic?) but I assume it was tuned for performance (on small inputs).

> +  "Merge LISTS in a consistent order.
> +LISTS is a list of lists of elements.
> +Merge them into a single list containing the same elements (removing
> +duplicates) and obeying their relative positions in each list.

I think the doc string should mention C3, and that we use `eq` as equivalence predicate here.

> +If a consistent order does not exist, call ERROR-FUNCTION with
> +the remaining lists.
> +It should return the candidate to use to continue the merge
> +By default we choose the first element of the first list."

It's not obvious from the text what the arguments to such an error-function would look like and what the return value should be. None of the existing three callers seem to use this argument, for that matter.
Given that `eieio--c3-merge-lists` raises an error if there is no total order, shouldn't the new code do so?

And we definitely should have tests (I completely understand that you didn't bothered writing any for something that may or may not actually be used).

(Really wish we could hive off the whole CEDET tree to ELPA one day.)

Message #20 received at 67008 <at> debbugs.gnu.org (full text, mbox):

From: Ikumi Keita <ikumi <at> ikumi.que.jp>
To: Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: 67008 <at> debbugs.gnu.org
Subject: Re: bug#67008: 30.0.50; Multiple major mode parents
Date: Sat, 11 Nov 2023 21:21:36 +0900

[Message part 1 (text/plain, inline)]

Hi Stefan,

>>>>> Stefan Monnier <monnier <at> iro.umontreal.ca> writes:
> I pushed to the branch `feature/derived-mode-add-parents` a bunch of
> patches which add support for such limited form of `multiple
> inheritance`.

I tried the branch with the attached tentative addition to AUCTeX
feature/fix-mode-names-overlap branch. I tested two modes, namely latex
mode and japanese latex mode, with the second attachment to see whether
the directory local variables stored in the .dir-locals.el are reflected
or not.

For latex mode, it works as expected. Thank you, it is promising.

On the contrary, it fails for japanese latex mode with the error:
File mode specification error: (error Cycle in the major mode hierarchy: japanese-LaTeX-mode)
I think the reason is that AUCTeX has
(defalias 'japanese-latex-mode #'japanese-LaTeX-mode)
for backward compatibility.

AUCTeX major modes are divided into two categories.
[a] Modes with former names which are overlapped with built-in tex
modes:
plain-TeX-mode, LaTeX-mode, docTeX-mode, Texinfo-mode
[b] Modes with former names which aren't overlapped with built-in tex
modes:
ConTeXt-mode, AmSTeX-mode, japanese-plain-TeX-mode, japanese-LaTeX-mode

For category [b], AUCTeX feature branch has defalias'es similar to the
above example for compatibility with files which have "%%% mode:" tag
with former mode name such as "japanese-latex".

This new feature of multiple inheritance would work well for category
[a], which retains backward compatibility by `major-mode-remap-alist'
and doesn't use defalias. However, it doesn't work for category [b].

It seems to me very difficult to arrange the proposed feature to cover
category [b], looking at its way to handle mode alias. So I think AUCTeX
feature branch must rely on some very ugly hack to be able to pick up
directory local variable entry with former mode name. :-(
(Or AUCTeX should entirely give up such compatibility with directory
local variables for category [b].)

Best regards,
Ikumi Keita
#StandWithUkraine #StopWarInUkraine

[patch (text/x-diff, attachment)]

[dirlocal.tar.gz (application/gzip, attachment)]

Message #23 received at 67008 <at> debbugs.gnu.org (full text, mbox):

From: Stefan Monnier <monnier <at> iro.umontreal.ca>
To: Mattias Engdegård <mattias.engdegard <at> gmail.com>
Cc: 67008 <at> debbugs.gnu.org, Ikumi Keita <ikumi <at> ikumi.que.jp>,
 Yuan Fu <casouri <at> gmail.com>, Dmitry Gutov <dgutov <at> yandex.ru>
Subject: Re: bug#67008: 30.0.50; Multiple major mode parents
Date: Sat, 11 Nov 2023 11:20:45 -0500

>>     * lisp/subr.el (merge-ordered-lists): New function. 
> That's nice to have, indeed.
> The implementation is a bit imperative (and quadratic?) but I assume it was
> tuned for performance (on small inputs).

I basically took the code from EIEIO, just massaged a bit to offer
a simpler API.  I'm sure there are ways to make it more efficient for
larger inputs, but I haven't put much thought into optimizing/tuning it.

>> +  "Merge LISTS in a consistent order.
>> +LISTS is a list of lists of elements.
>> +Merge them into a single list containing the same elements (removing
>> +duplicates) and obeying their relative positions in each list.
> I think the doc string should mention C3,

Fair enough.

> and that we use `eq` as equivalence predicate here.

Oops, indeed, thanks.

>> +If a consistent order does not exist, call ERROR-FUNCTION with
>> +the remaining lists.
>> +It should return the candidate to use to continue the merge
>> +By default we choose the first element of the first list."
>
> It's not obvious from the text what the arguments to such an error-function
> would look like and what the return value should be. None of the existing
> three callers seem to use this argument, for that matter.

Oh, that's a bug in my patch: the EIEIO code should use (to signal the
same error it currently signals).

> Given that `eieio--c3-merge-lists` raises an error if there is no total
> order, shouldn't the new code do so?

Yup.

> And we definitely should have tests (I completely understand that you didn't
> bothered writing any for something that may or may not actually be used).

I don't understand, there are many `if` tests in the code already.

> (Really wish we could hive off the whole CEDET tree to ELPA one day.)

Including EIEIO?
`defclass` is quite popular among contributors coming from the Common
Lisp world, so we have several packages in Emacs itself which use it:

    % grep -l '^(defclass' lisp/**/*.el | grep -v 'cedet\|eieio'
    lisp/auth-source.el
    lisp/emacs-lisp/chart.el
    lisp/emacs-lisp/vtable.el
    lisp/gnus/gnus-icalendar.el
    lisp/gnus/gnus-search.el
    lisp/international/emoji.el
    lisp/jsonrpc.el
    lisp/progmodes/eglot.el
    lisp/registry.el
    lisp/transient.el
    %

The use in `emoji.el` seems to be due to the use in `transient.el`.


        Stefan

Message #26 received at 67008 <at> debbugs.gnu.org (full text, mbox):

From: Stefan Monnier <monnier <at> iro.umontreal.ca>
To: Ikumi Keita <ikumi <at> ikumi.que.jp>
Cc: 67008 <at> debbugs.gnu.org
Subject: Re: bug#67008: 30.0.50; Multiple major mode parents
Date: Sat, 11 Nov 2023 11:57:02 -0500

> I tried the branch with the attached tentative addition to AUCTeX
> feature/fix-mode-names-overlap branch. I tested two modes, namely latex
> mode and japanese latex mode, with the second attachment to see whether
> the directory local variables stored in the .dir-locals.el are reflected
> or not.

Thanks for testing :-)

> For latex mode, it works as expected. Thank you, it is promising.

Great.

> On the contrary, it fails for japanese latex mode with the error:
> File mode specification error: (error Cycle in the major mode hierarchy: japanese-LaTeX-mode)
> I think the reason is that AUCTeX has
> (defalias 'japanese-latex-mode #'japanese-LaTeX-mode)
> for backward compatibility.

Oh, I see so `japanese-LaTeX-mode` declares `japanese-latex-mode` as an
extra parent but the alias makes it a cycle.
Admittedly, in the current `provided-mode-derived-p` code, we actually
don't signal errors in case of cycles, we just silently break them via
de-duplications, so I just changed my code accordingly.

> This new feature of multiple inheritance would work well for category
> [a], which retains backward compatibility by `major-mode-remap-alist'
> and doesn't use defalias. However, it doesn't work for category [b].

I believe with the code I just pushed it should work fine for [b] as well.

> It seems to me very difficult to arrange the proposed feature to cover
> category [b], looking at its way to handle mode alias.

Maybe there's something I'm missing, but the change was simple and I
believe it does address your use case.


        Stefan

Message #29 received at 67008 <at> debbugs.gnu.org (full text, mbox):

From: Mattias Engdegård <mattias.engdegard <at> gmail.com>
To: Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: 67008 <at> debbugs.gnu.org, Ikumi Keita <ikumi <at> ikumi.que.jp>,
 Yuan Fu <casouri <at> gmail.com>, Dmitry Gutov <dgutov <at> yandex.ru>
Subject: Re: bug#67008: 30.0.50; Multiple major mode parents 
Date: Sat, 11 Nov 2023 19:12:51 +0100

11 nov. 2023 kl. 17.20 skrev Stefan Monnier <monnier <at> iro.umontreal.ca>:

>> And we definitely should have tests (I completely understand that you didn't
>> bothered writing any for something that may or may not actually be used).
> 
> I don't understand, there are many `if` tests in the code already.

Oh, carry on then. Testing my patience must count for something.

>> (Really wish we could hive off the whole CEDET tree to ELPA one day.)
> 
> Including EIEIO?

No, I didn't know it was part of or depended on CEDET. That so?
(xref.el depends on semantic/symref but I'm pretty sure that must be resolvable.)

Message #32 received at 67008 <at> debbugs.gnu.org (full text, mbox):

From: Stefan Monnier <monnier <at> iro.umontreal.ca>
To: Mattias Engdegård <mattias.engdegard <at> gmail.com>
Cc: 67008 <at> debbugs.gnu.org, Ikumi Keita <ikumi <at> ikumi.que.jp>,
 Yuan Fu <casouri <at> gmail.com>, Dmitry Gutov <dgutov <at> yandex.ru>
Subject: Re: bug#67008: 30.0.50; Multiple major mode parents
Date: Sat, 11 Nov 2023 13:43:36 -0500

>>> And we definitely should have tests (I completely understand that you didn't
>>> bothered writing any for something that may or may not actually be used).
>> I don't understand, there are many `if` tests in the code already.
> Oh, carry on then. Testing my patience must count for something.

:-)

>>> (Really wish we could hive off the whole CEDET tree to ELPA one day.)
>> Including EIEIO?
> No, I didn't know it was part of or depended on CEDET.

It doesn't depend on CEDET, no, but it was historically "part of" it, so
in some cases the term "CEDET" includes it and I just wanted to be sure
you didn't mean that.


        Stefan

Message #35 received at 67008 <at> debbugs.gnu.org (full text, mbox):

From: Stefan Monnier <monnier <at> iro.umontreal.ca>
To: Mattias Engdegård <mattias.engdegard <at> gmail.com>
Cc: 67008 <at> debbugs.gnu.org, Ikumi Keita <ikumi <at> ikumi.que.jp>,
 Yuan Fu <casouri <at> gmail.com>, Dmitry Gutov <dgutov <at> yandex.ru>
Subject: Re: bug#67008: 30.0.50; Multiple major mode parents
Date: Sat, 11 Nov 2023 15:13:03 -0500

>>> +  "Merge LISTS in a consistent order.
>>> +LISTS is a list of lists of elements.
>>> +Merge them into a single list containing the same elements (removing
>>> +duplicates) and obeying their relative positions in each list.
>> I think the doc string should mention C3,
> Fair enough.

Having read a bit further, I'm now not sure that `merge-ordered-lists`
implements C3.  I suspect it provides a useful primitive with which to
implement C3 but whether it gives the same result as C3 or not depends
on how we call it.


        Stefan

Message #38 received at 67008 <at> debbugs.gnu.org (full text, mbox):

From: Ikumi Keita <ikumikeita <at> jcom.home.ne.jp>
To: Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: 67008 <at> debbugs.gnu.org
Subject: Re: bug#67008: 30.0.50; Multiple major mode parents
Date: Sun, 12 Nov 2023 18:50:20 +0900

Hi Stefan,

>>>>> Stefan Monnier <monnier <at> iro.umontreal.ca> writes:
> Oh, I see so `japanese-LaTeX-mode` declares `japanese-latex-mode` as an
> extra parent but the alias makes it a cycle.
> Admittedly, in the current `provided-mode-derived-p` code, we actually
> don't signal errors in case of cycles, we just silently break them via
> de-duplications, so I just changed my code accordingly.

Great, it did work. Thank you very much!

>> It seems to me very difficult to arrange the proposed feature to cover
>> category [b], looking at its way to handle mode alias.

> Maybe there's something I'm missing, but the change was simple and I
> believe it does address your use case.

Now I think I can settle out the AUCTeX feature branch in clean and
consistent way.

Best regards,
Ikumi Keita
#StandWithUkraine #StopWarInUkraine
#Gaza #StopTheGenocide #CeasefireNOW

Message #41 received at 67008 <at> debbugs.gnu.org (full text, mbox):

From: Mattias Engdegård <mattias.engdegard <at> gmail.com>
To: Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: 67008 <at> debbugs.gnu.org, Ikumi Keita <ikumi <at> ikumi.que.jp>,
 Yuan Fu <casouri <at> gmail.com>, Dmitry Gutov <dgutov <at> yandex.ru>
Subject: Re: bug#67008: 30.0.50; Multiple major mode parents 
Date: Sun, 12 Nov 2023 14:37:15 +0100

11 nov. 2023 kl. 21.13 skrev Stefan Monnier <monnier <at> iro.umontreal.ca>:

> Having read a bit further, I'm now not sure that `merge-ordered-lists`
> implements C3.  I suspect it provides a useful primitive with which to
> implement C3 but whether it gives the same result as C3 or not depends
> on how we call it.

Yes, the output seems very sensitive about the input order:

 (B A) (C A) (D B) (E D C) -> (E D B C A)

 (E D C) (B A) (C A) (D B) -> (E D C B A)

Maybe that's obvious for someone who knows how to use it.

It could probably be used as a general-purpose topo-sorter but it's not a very efficient one (at least quadratic, possibly cubic).

Oh, and the function probably shouldn't call delq on its input argument.

Message #44 received at 67008 <at> debbugs.gnu.org (full text, mbox):

From: Stefan Monnier <monnier <at> iro.umontreal.ca>
To: Ikumi Keita <ikumikeita <at> jcom.home.ne.jp>
Cc: 67008 <at> debbugs.gnu.org
Subject: Re: bug#67008: 30.0.50; Multiple major mode parents
Date: Sun, 12 Nov 2023 11:04:10 -0500

>>> It seems to me very difficult to arrange the proposed feature to cover
>>> category [b], looking at its way to handle mode alias.
>> Maybe there's something I'm missing, but the change was simple and I
>> believe it does address your use case.

Indeed, I was missing something and it's a bit more tricky than
I thought, but I found a way to address it now.

> Now I think I can settle out the AUCTeX feature branch in clean and
> consistent way.

Excellent, thanks,


        Stefan

Message #47 received at 67008 <at> debbugs.gnu.org (full text, mbox):

From: Stefan Monnier <monnier <at> iro.umontreal.ca>
To: Mattias Engdegård <mattias.engdegard <at> gmail.com>
Cc: 67008 <at> debbugs.gnu.org, Ikumi Keita <ikumi <at> ikumi.que.jp>,
 Yuan Fu <casouri <at> gmail.com>, Dmitry Gutov <dgutov <at> yandex.ru>
Subject: Re: bug#67008: 30.0.50; Multiple major mode parents
Date: Sun, 12 Nov 2023 11:41:35 -0500

>> Having read a bit further, I'm now not sure that `merge-ordered-lists`
>> implements C3.  I suspect it provides a useful primitive with which to
>> implement C3 but whether it gives the same result as C3 or not depends
>> on how we call it.
> Yes, the output seems very sensitive about the input order:
>
>  (B A) (C A) (D B) (E D C) -> (E D B C A)
>
>  (E D C) (B A) (C A) (D B) -> (E D C B A)

Yes, that's on purpose: when the dependencies expressed by the
(sub)lists don't enforce a unique solution, the order between the
(sub)lists is used to choose between the available options.

> Maybe that's obvious for someone who knows how to use it.

I improved the docstring to try and clarify.

> It could probably be used as a general-purpose topo-sorter but it's not
> a very efficient one (at least quadratic, possibly cubic).

Also it doesn't start from a graph but from a lists of lists (because
for uses in method inheritance it's very desirable that the ordering be
"monotonic": if A comes before B in the linearization of class C's
parents then the same should be true in the linearization of all its
subclasses).


        Stefan

Message #50 received at 67008 <at> debbugs.gnu.org (full text, mbox):

From: Stefan Monnier <monnier <at> iro.umontreal.ca>
To: 67008 <at> debbugs.gnu.org,  Ikumi Keita <ikumi <at> ikumi.que.jp>
Subject: Re: bug#67008: 30.0.50; Multiple major mode parents
Date: Sun, 12 Nov 2023 17:11:22 -0500

>> You can see below the corresponding commit log.
>> There are no doc (or etc/NEWS) changes yet.
>> Any comment/objection?

I have now added some doc in `modes.texi` as well as two
etc/NEWS entries.

Barring objection, I intend to push this to master in a few days.


        Stefan

Message #53 received at 67008 <at> debbugs.gnu.org (full text, mbox):

From: Mattias Engdegård <mattias.engdegard <at> gmail.com>
To: Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: 67008 <at> debbugs.gnu.org, Ikumi Keita <ikumi <at> ikumi.que.jp>,
 Yuan Fu <casouri <at> gmail.com>, Dmitry Gutov <dgutov <at> yandex.ru>
Subject: Re: bug#67008: 30.0.50; Multiple major mode parents 
Date: Mon, 13 Nov 2023 13:45:59 +0100

12 nov. 2023 kl. 17.41 skrev Stefan Monnier <monnier <at> iro.umontreal.ca>:

> I improved the docstring to try and clarify.

Thank you, but the new text,

> +The order of the (sub)lists determines the final order in those cases where
> +the order within the sublists does not impose a unique choice.

still doesn't explain how the sublist order affects the choice of linearisation.

Since I'm here:

>      (while (cdr (setq lists (delq nil lists)))

When this loop is entered the first time, `lists` still holds the argument which probably shouldn't be mutated even if it's for removing empty lists inside. (In later iterations it seems to be a copy.)

+(ert-deftest subt-tests--merge-ordered-lists ()
                 ^
                 r

+  (should (equal (merge-ordered-lists
+                  '((B A) (C A) (D B) (E D C)))
+                 '(E D B C A)))
+  (should (equal (merge-ordered-lists
+                  '((E D C) (B A) (C A) (D B)))
+                 '(E D C B A)))
+  (should-error (merge-ordered-lists
+                 '((E C D) (B A) (A C) (D B))
+                 (lambda (_) (error "cycle")))))

All calls should error on cycles, not just the one that actually contains one.

Maybe the default value for the `error-function` argument should be one that raises an error, so that callers need to specify something explicitly if they want a different behaviour?

Message #56 received at 67008 <at> debbugs.gnu.org (full text, mbox):

From: Stefan Monnier <monnier <at> iro.umontreal.ca>
To: Mattias Engdegård <mattias.engdegard <at> gmail.com>
Cc: 67008 <at> debbugs.gnu.org, Ikumi Keita <ikumi <at> ikumi.que.jp>,
 Yuan Fu <casouri <at> gmail.com>, Dmitry Gutov <dgutov <at> yandex.ru>
Subject: Re: bug#67008: 30.0.50; Multiple major mode parents
Date: Mon, 13 Nov 2023 08:30:22 -0500

>> I improved the docstring to try and clarify.
> Thank you, but the new text,
>> +The order of the (sub)lists determines the final order in those cases where
>> +the order within the sublists does not impose a unique choice.
> still doesn't explain how the sublist order affects the choice of linearisation.

Suggestions welcome to make it better.  I couldn't come up with
a wording that is both short enough and clear.

> Since I'm here:
>>      (while (cdr (setq lists (delq nil lists)))
> When this loop is entered the first time, `lists` still holds the argument
> which probably shouldn't be mutated even if it's for removing empty lists
> inside. (In later iterations it seems to be a copy.)

I guess you're right.  The list passed to it is always freshly made, so
it's not a real problem in practice, but it's a bit ugly.

> +(ert-deftest subt-tests--merge-ordered-lists ()
>                  ^
>                  r

Damn, you caught my subt-erfuge!

> +  (should (equal (merge-ordered-lists
> +                  '((B A) (C A) (D B) (E D C)))
> +                 '(E D B C A)))
> +  (should (equal (merge-ordered-lists
> +                  '((E D C) (B A) (C A) (D B)))
> +                 '(E D C B A)))
> +  (should-error (merge-ordered-lists
> +                 '((E C D) (B A) (A C) (D B))
> +                 (lambda (_) (error "cycle")))))
>
> All calls should error on cycles, not just the one that actually contains one.

Fair enough.

> Maybe the default value for the `error-function` argument should be one that
> raises an error, so that callers need to specify something explicitly if
> they want a different behaviour?

I decided against that because the existing evidence is that we prefer
to hide the problem than to signal an error.  Part of the issue is also
that in practice most "cycles" aren't real: they are the result of
submode/subtype relationships where two types/modes have linearized their
parents in incompatible ways.

E.g. C inherits from (A B)
     D inherits from (B A)
     E inherits from (C D)

there is no cycle in the inheritance, but since the linearization is
done piecemeal (a.k.a locally), you get to merge

    ((C A B) (D B A))

and that finds a "cycle".  That's why EIEIO calls it
`inconsistent-class-hierarchy` rather than `cycle`.


        Stefan

Message #59 received at 67008 <at> debbugs.gnu.org (full text, mbox):

From: Mattias Engdegård <mattias.engdegard <at> gmail.com>
To: Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: 67008 <at> debbugs.gnu.org, Ikumi Keita <ikumi <at> ikumi.que.jp>,
 Yuan Fu <casouri <at> gmail.com>, Dmitry Gutov <dgutov <at> yandex.ru>
Subject: Re: bug#67008: 30.0.50; Multiple major mode parents
Date: Mon, 13 Nov 2023 17:44:24 +0100

13 nov. 2023 kl. 14.30 skrev Stefan Monnier <monnier <at> iro.umontreal.ca>:

> Suggestions welcome to make it better.  I couldn't come up with
> a wording that is both short enough and clear.

Nor can I, not without re-reading the C3 paper more closely (it was many years ago) and scrutinising your code.

Intuitively though, wouldn't we distinguish vertical (class-parent) edges from horizontal (parent-parent) ones? Use stiffer springs when building the former?

Message #62 received at 67008 <at> debbugs.gnu.org (full text, mbox):

From: Stefan Monnier <monnier <at> iro.umontreal.ca>
To: Mattias Engdegård <mattias.engdegard <at> gmail.com>
Cc: 67008 <at> debbugs.gnu.org, Ikumi Keita <ikumi <at> ikumi.que.jp>,
 Yuan Fu <casouri <at> gmail.com>, Dmitry Gutov <dgutov <at> yandex.ru>
Subject: Re: bug#67008: 30.0.50; Multiple major mode parents
Date: Mon, 13 Nov 2023 12:46:41 -0500

> Intuitively though, wouldn't we distinguish vertical (class-parent) edges
> from horizontal (parent-parent) ones? Use stiffer springs when building
> the former?

Yes we strictly obey the vertical edges (and call `error-function` when
that's not an option) and we use the horizontal edges when there's
a choice.

E.g. for

    (B A) (C A) (D B) (E D C) -> (E D B C A)
vs
    (E D C) (B A) (C A) (D B) -> (E D C B A)

the vertical edges force the "E D" at the beginning and the "A" at the
end but it's the horizontal edges that make us prefer "B C" in the
first case and "C B" in the other.

This is because after removing the "E D" which are uniquely
determined by the vertical dependencies we're left with:

    (B A) (C A) (B) (C)
vs
    (C) (B A) (C A) (B)

So we continue with "B" in the first case and with "C" in the second.


        Stefan

Message #65 received at 67008 <at> debbugs.gnu.org (full text, mbox):

From: Mattias Engdegård <mattias.engdegard <at> gmail.com>
To: Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: 67008 <at> debbugs.gnu.org, Ikumi Keita <ikumi <at> ikumi.que.jp>,
 Yuan Fu <casouri <at> gmail.com>, Dmitry Gutov <dgutov <at> yandex.ru>
Subject: Re: bug#67008: 30.0.50; Multiple major mode parents 
Date: Thu, 16 Nov 2023 12:07:58 +0100

> Yes we strictly obey the vertical edges (and call `error-function` when
> that's not an option) and we use the horizontal edges when there's
> a choice.

Yes, but `merge-ordered-lists` doesn't distinguish between vertical and horizontal edges in any way, does it? We only get a consistent (monotonic) result if the input is ordered correctly.

In that respect `merge-ordered-lists` is just half an algorithm. We could add the other half but presumably this wouldn't be a good fit in places where the function is currently used?

The other half might be something like: compute the linear order for each parent in sequence, then add the partial order (NODE PARENT1...PARENTn).

The documentation text

> The order of the (sub)lists determines the final order in those cases where
> the order within the sublists does not impose a unique choice.
> Equality of elements is tested with `eql'.

could perhaps be written more precisely to say that when the constraints do not impose a relative order between elements (not sublists), they are ordered by their occurrence in the input.

`merge-ordered-lists` should also have the left-to-right property that

(merge-ordered-lists (append X Y))
= (merge-ordered-lists (cons (merge-ordered-lists X) Y))

although I haven't verified this.

Message #68 received at 67008 <at> debbugs.gnu.org (full text, mbox):

From: Stefan Monnier <monnier <at> iro.umontreal.ca>
To: Mattias Engdegård <mattias.engdegard <at> gmail.com>
Cc: 67008 <at> debbugs.gnu.org, Ikumi Keita <ikumi <at> ikumi.que.jp>,
 Yuan Fu <casouri <at> gmail.com>, Dmitry Gutov <dgutov <at> yandex.ru>
Subject: Re: bug#67008: 30.0.50; Multiple major mode parents
Date: Thu, 16 Nov 2023 10:15:22 -0500

>> Yes we strictly obey the vertical edges (and call `error-function` when
>> that's not an option) and we use the horizontal edges when there's
>> a choice.
> Yes, but `merge-ordered-lists` doesn't distinguish between vertical and
> horizontal edges in any way, does it?

The text I wrote above says that it does (and I stand by it, and your
test cases additionally shows that it does), so I don't understand
the question.

> We only get a consistent (monotonic) result if the input is
> ordered correctly.

Not sure what you mean by that.  The vertical edges are the ones that
need to be obeyed to guarantee monotonicity (because they are the ones
that come from linearizations of other classes), the horizontal ones
represent the preferences expressed by the order in which direct parents
are listed by the programmer, so they are "softer".

> In that respect `merge-ordered-lists` is just half an algorithm. We could
> add the other half but presumably this wouldn't be a good fit in places
> where the function is currently used?
> The other half might be something like: compute the linear order for each
> parent in sequence, then add the partial order (NODE PARENT1...PARENTn).

If that's what you want to compute, then yes, that's what you need to do :-)

> The documentation text
>
>> The order of the (sub)lists determines the final order in those cases where
>> the order within the sublists does not impose a unique choice.
>> Equality of elements is tested with `eql'.
>
> could perhaps be written more precisely to say that when the constraints do
> not impose a relative order between elements (not sublists), they are
> ordered by their occurrence in the input.

I'm not super happy with my phrasing, but I must say that really your
above paragraph I don't really know what it means either, so for me it's
a wash.  I have now pushed my code to `master`, so feel free to update
the docstring there as you see fit.

> `merge-ordered-lists` should also have the left-to-right property that
>
> (merge-ordered-lists (append X Y))
> = (merge-ordered-lists (cons (merge-ordered-lists X) Y))
>
> although I haven't verified this.

Let me know if you find out.


        Stefan

Message #73 received at 67008-done <at> debbugs.gnu.org (full text, mbox):

From: Stefan Monnier <monnier <at> iro.umontreal.ca>
To: 67008-done <at> debbugs.gnu.org
Cc: Ikumi Keita <ikumi <at> ikumi.que.jp>
Subject: Re: bug#67008: 30.0.50; Multiple major mode parents
Date: Thu, 16 Nov 2023 10:16:27 -0500

> Barring objection, I intend to push this to master in a few days.

Done, closing, thanks,


        Stefan

Message #76 received at 67008 <at> debbugs.gnu.org (full text, mbox):

From: Mattias Engdegård <mattias.engdegard <at> gmail.com>
To: Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: 67008 <at> debbugs.gnu.org, Ikumi Keita <ikumi <at> ikumi.que.jp>,
 Yuan Fu <casouri <at> gmail.com>, Dmitry Gutov <dgutov <at> yandex.ru>
Subject: Re: bug#67008: 30.0.50; Multiple major mode parents
Date: Thu, 16 Nov 2023 20:35:54 +0100

>> Yes, but `merge-ordered-lists` doesn't distinguish between vertical and
>> horizontal edges in any way, does it?
> 
> The text I wrote above says that it does (and I stand by it, and your
> test cases additionally shows that it does), so I don't understand
> the question.

That's because I didn't articulate it very well but reading your elaboration I think we are in non-violent agreement.

> I'm not super happy with my phrasing, but I must say that really your
> above paragraph I don't really know what it means either, so for me it's
> a wash.

Would something like this serve as a start?

The return value is uniquely determined by the following rules:

* The return value is a list containing each input element exactly once.

* The relative order of two elements in the return value is determined by their relative order in the sublists, so that the input ((C D) (A B C)) implies that C precedes D, A precedes B, and B precedes C.

* If two elements are not ordered by the previous rule, they are ordered by the sublists they first occur in. For example, in ((A B) (A C)), B precedes C.

...except that I notice that the first rule is broken if a sublist contains duplicates (which seems wrong), or if the default error function (caar) is used.

I'm not sure I understand if this is correct, or why:

(A) (A) -> (A)
(A A) -> (A A)
(A) (A A) -> error

Message #79 received at 67008 <at> debbugs.gnu.org (full text, mbox):

From: Stefan Monnier <monnier <at> iro.umontreal.ca>
To: Mattias Engdegård <mattias.engdegard <at> gmail.com>
Cc: 67008 <at> debbugs.gnu.org, Ikumi Keita <ikumi <at> ikumi.que.jp>,
 Yuan Fu <casouri <at> gmail.com>, Dmitry Gutov <dgutov <at> yandex.ru>
Subject: Re: bug#67008: 30.0.50; Multiple major mode parents
Date: Thu, 16 Nov 2023 16:40:16 -0500

> ...except that I notice that the first rule is broken if a sublist contains
> duplicates (which seems wrong),

Garbage in, garbage out, eh?

> or if the default error function (caar) is used.

Same.


        Stefan

Message #82 received at 67008 <at> debbugs.gnu.org (full text, mbox):

From: Mattias Engdegård <mattias.engdegard <at> gmail.com>
To: Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: 67008 <at> debbugs.gnu.org, Ikumi Keita <ikumi <at> ikumi.que.jp>,
 Yuan Fu <casouri <at> gmail.com>, Dmitry Gutov <dgutov <at> yandex.ru>
Subject: Re: bug#67008: 30.0.50; Multiple major mode parents
Date: Fri, 17 Nov 2023 15:04:24 +0100

> Garbage in, garbage out, eh?

Indeed. Let's document the constraint on the argument and, if it's not too expensive, verify.

>> or if the default error function (caar) is used.
> 
> Same.

Well sort of -- since it's the default error function, we must be able to defend the results of having it used.
Otherwise we're just saying 'if the input graph is cyclic then the output is undefined' but that clearly isn't true since we make an effort to return something semi-useful in that case.

Are the duplicates essential to proper functioning of `cl--class-allparents` and `derived-mode-all-parents`, or would they work just as well with some edge of the cycle removed instead?

Message #85 received at 67008 <at> debbugs.gnu.org (full text, mbox):

From: Stefan Monnier <monnier <at> iro.umontreal.ca>
To: Mattias Engdegård <mattias.engdegard <at> gmail.com>
Cc: 67008 <at> debbugs.gnu.org, Ikumi Keita <ikumi <at> ikumi.que.jp>,
 Yuan Fu <casouri <at> gmail.com>, Dmitry Gutov <dgutov <at> yandex.ru>
Subject: Re: bug#67008: 30.0.50; Multiple major mode parents
Date: Fri, 17 Nov 2023 09:20:26 -0500

>> Garbage in, garbage out, eh?
> Indeed. Let's document the constraint on the argument and, if it's not
> too expensive, verify.

Duplicates in the input imply a cyclic dependency, so it immediately
fall into the case where the constraints can't be satisfied.

> Are the duplicates essential to proper functioning of `cl--class-allparents`
> and `derived-mode-all-parents`, or would they work just as well with some
> edge of the cycle removed instead?

They'd work as well.  It's just significantly more work for very
little benefit.


        Stefan

Message #88 received at 67008 <at> debbugs.gnu.org (full text, mbox):

From: Mattias Engdegård <mattias.engdegard <at> gmail.com>
To: Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: 67008 <at> debbugs.gnu.org, Ikumi Keita <ikumi <at> ikumi.que.jp>,
 Yuan Fu <casouri <at> gmail.com>, Dmitry Gutov <dgutov <at> yandex.ru>
Subject: Re: bug#67008: 30.0.50; Multiple major mode parents
Date: Fri, 17 Nov 2023 17:15:47 +0100

> Duplicates in the input imply a cyclic dependency, so it immediately
> fall into the case where the constraints can't be satisfied.

Yes, except these only sometimes result in the error function being called.
But perhaps checking this (duplicates in the input) should be the caller's responsibility.

Previous Next

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