bug#67008: 30.0.50; Multiple major mode parents

bug#67008: 30.0.50; Multiple major mode parents

[Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors]

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

bug#67008: 30.0.50; Multiple major mode parents

[Yuan Fu]

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

bug#67008: 30.0.50; Multiple major mode parents

[Dmitry Gutov]

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.

bug#67008: 30.0.50; Multiple major mode parents

[Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors]

> 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

bug#67008: 30.0.50; Multiple major mode parents

[Mattias Engdegård]

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

bug#67008: 30.0.50; Multiple major mode parents

[Ikumi Keita]

[-- Attachment #1: Type: text/plain, Size: 2029 bytes --]

Hi Stefan,

>>>>> Stefan Monnier <monnier@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


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: Use multiple inheritance --]
[-- Type: text/x-diff, Size: 2459 bytes --]

diff --git a/latex.el b/latex.el
index e9b08cc1..0551c320 100644
--- a/latex.el
+++ b/latex.el
@@ -8087,6 +8087,8 @@ Run after mode hooks and file local variables application."
 ;;;###autoload
 (put 'LaTeX-mode 'auctex-function-definition (symbol-function 'LaTeX-mode))
 
+(TeX-derived-mode-add-parents 'LaTeX-mode '(latex-mode))
+
 (with-eval-after-load 'semantic/symref/grep
   (push '(docTeX-mode "*.dtx") semantic-symref-filepattern-alist))
 
diff --git a/tex-jp.el b/tex-jp.el
index ff562e22..36a39ec1 100644
--- a/tex-jp.el
+++ b/tex-jp.el
@@ -471,6 +471,9 @@ Now `japanese-latex-mode-initialization' is no-op.  Don't use it."))
 ;;;###autoload
 (defalias 'japanese-latex-mode #'japanese-LaTeX-mode)
 
+(TeX-derived-mode-add-parents 'japanese-LaTeX-mode
+                              '(japanese-latex-mode latex-mode))
+
 (defun japanese-LaTeX-guess-engine ()
   "Guess Japanese TeX engine and set it to `TeX-engine'.
 Document class and its option are taken into account.  Do not
diff --git a/tex.el b/tex.el
index d4fded73..f67e1e31 100644
--- a/tex.el
+++ b/tex.el
@@ -3875,6 +3875,15 @@ Run after mode hooks and file local variables application."
 ;;;###autoload
 (put 'TeX-mode 'auctex-function-definition (symbol-function 'TeX-mode))
 
+;; COMPATIBILITY for Emacs<30
+(unless (fboundp 'derived-mode-add-parents)
+  (advice-add 'derived-mode-p :after-until #'TeX--compat-derived-mode-p)
+  (defun TeX--compat-derived-mode-p (&rest modes)
+    (let ((extra-parents (get major-mode 'derived-mode-extra-parents)))
+      (and extra-parents
+           (cl-loop for parent in extra-parents
+                    thereis (memq parent modes))))))
+
 ;;; Hilighting
 
 ;; FIXME: It's likely that `hilit-patterns-alist' is much obsolete.
@@ -4828,6 +4837,16 @@ Also see `ignore'.
 This is a compatibility function for Emacs versions prior to v.28."
     t))
 
+;; COMPATIBILITY for Emacs<30
+(if (fboundp 'derived-mode-add-parents)
+    (defalias 'TeX-derived-mode-add-parents #'derived-mode-add-parents)
+  ;; Adapted copy of `derived-mode-add-parents'.
+  (defun TeX-derived-mode-add-parents (mode extra-parents)
+    "Add EXTRA-PARENTS to the parents of MODE.
+Declares the parents of MODE to be its main parent (as defined
+in `define-derived-mode') plus EXTRA-PARENTS."
+    (put mode 'derived-mode-extra-parents extra-parents)))
+
 (defun TeX-match-buffer (n)
   "Return the substring corresponding to the N'th match.
 See `match-data' for details."

[-- Attachment #3: Test suit --]
[-- Type: application/gzip, Size: 731 bytes --]

bug#67008: 30.0.50; Multiple major mode parents

[Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors]

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

bug#67008: 30.0.50; Multiple major mode parents

[Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors]

> 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

bug#67008: 30.0.50; Multiple major mode parents

[Mattias Engdegård]

11 nov. 2023 kl. 17.20 skrev Stefan Monnier <monnier@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.)

bug#67008: 30.0.50; Multiple major mode parents

[Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors]

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

bug#67008: 30.0.50; Multiple major mode parents

[Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors]

>>> +  "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

bug#67008: 30.0.50; Multiple major mode parents

[Ikumi Keita]

Hi Stefan,

>>>>> Stefan Monnier <monnier@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

bug#67008: 30.0.50; Multiple major mode parents

[Mattias Engdegård]

11 nov. 2023 kl. 21.13 skrev Stefan Monnier <monnier@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.

bug#67008: 30.0.50; Multiple major mode parents

[Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors]

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

bug#67008: 30.0.50; Multiple major mode parents

[Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors]

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

bug#67008: 30.0.50; Multiple major mode parents

[Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors]

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

bug#67008: 30.0.50; Multiple major mode parents

[Mattias Engdegård]

12 nov. 2023 kl. 17.41 skrev Stefan Monnier <monnier@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?

bug#67008: 30.0.50; Multiple major mode parents

[Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors]

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

bug#67008: 30.0.50; Multiple major mode parents

[Mattias Engdegård]

13 nov. 2023 kl. 14.30 skrev Stefan Monnier <monnier@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?

bug#67008: 30.0.50; Multiple major mode parents

[Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors]

> 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

bug#67008: 30.0.50; Multiple major mode parents

[Mattias Engdegård]

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

bug#67008: 30.0.50; Multiple major mode parents

[Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors]

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

bug#67008: 30.0.50; Multiple major mode parents

[Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors]

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

Done, closing, thanks,


        Stefan

bug#67008: 30.0.50; Multiple major mode parents

[Mattias Engdegård]

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

bug#67008: 30.0.50; Multiple major mode parents

[Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors]

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

bug#67008: 30.0.50; Multiple major mode parents

[Mattias Engdegård]

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

bug#67008: 30.0.50; Multiple major mode parents

[Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors]

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

bug#67008: 30.0.50; Multiple major mode parents

[Mattias Engdegård]

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