bug#59067: 29.0.50; Exexpected overlay order in `overlays-in' return value

bug#59067: 29.0.50; Exexpected overlay order in `overlays-in' return value

[Ihor Radchenko]

Hi,

Some Org tests are failing when testing with the latest Emacs 29 master.

To reproduce, get the latest Org from git and run make test.

The common feature of all the failing tests is usage of overlays-in and
expecting certain order of overlays in its return value. The order is
changed compared to Emacs 28.

I consider this an Emacs bug.

In GNU Emacs 29.0.50 (build 1, x86_64-pc-linux-gnu, GTK+ Version
 3.24.34, cairo version 1.16.0) of 2022-11-06 built on localhost
Repository revision: 6e5ec085510ccf52ac6cb07c3a1a2778324a1d89
Repository branch: master
Windowing system distributor 'The X.Org Foundation', version 11.0.12101004
System Description: Gentoo Linux

-- 
Ihor Radchenko // yantar92,
Org mode contributor,
Learn more about Org mode at <https://orgmode.org/>.
Support Org development at <https://liberapay.com/org-mode>,
or support my work at <https://liberapay.com/yantar92>

bug#59067: 29.0.50; Exexpected overlay order in `overlays-in' return value

[Eli Zaretskii]

> From: Ihor Radchenko <yantar92@posteo.net>
> Date: Sun, 06 Nov 2022 03:39:06 +0000
> 
> Some Org tests are failing when testing with the latest Emacs 29 master.
> 
> To reproduce, get the latest Org from git and run make test.
> 
> The common feature of all the failing tests is usage of overlays-in and
> expecting certain order of overlays in its return value. The order is
> changed compared to Emacs 28.
> 
> I consider this an Emacs bug.

I'm not sure we want to keep the old order (which AFAIU was the side
effect of the implementation), nor become committed to a specific
order.  Sorting overlays is a slowdown, and not every application
cares about the order.  The ones that do care can sort the overlays in
the order they want.

Or maybe I'm missing something: can you explain why the order matters
in a couple of specific examples from Org?

bug#59067: 29.0.50; Exexpected overlay order in `overlays-in' return value

[Ihor Radchenko]

Eli Zaretskii <eliz@gnu.org> writes:

>> The common feature of all the failing tests is usage of overlays-in and
>> expecting certain order of overlays in its return value. The order is
>> changed compared to Emacs 28.
>> 
>> I consider this an Emacs bug.
>
> I'm not sure we want to keep the old order (which AFAIU was the side
> effect of the implementation), nor become committed to a specific
> order.  Sorting overlays is a slowdown, and not every application
> cares about the order.  The ones that do care can sort the overlays in
> the order they want.
>
> Or maybe I'm missing something: can you explain why the order matters
> in a couple of specific examples from Org?

You are right. `overlays-in' docstring does not give any promises.
It is not really a big deal for Org as well (can as well sort the return
value).

The only thing that could be useful on Emacs side is explicitly stating
in the `overlays-in' docstring that overlay list may be in arbitrary
order.

-- 
Ihor Radchenko // yantar92,
Org mode contributor,
Learn more about Org mode at <https://orgmode.org/>.
Support Org development at <https://liberapay.com/org-mode>,
or support my work at <https://liberapay.com/yantar92>

bug#59067: 29.0.50; Exexpected overlay order in `overlays-in' return value

[Eli Zaretskii]

> From: Ihor Radchenko <yantar92@posteo.net>
> Cc: 59067@debbugs.gnu.org
> Date: Sun, 06 Nov 2022 07:04:54 +0000
> 
> Eli Zaretskii <eliz@gnu.org> writes:
> 
> > I'm not sure we want to keep the old order (which AFAIU was the side
> > effect of the implementation), nor become committed to a specific
> > order.  Sorting overlays is a slowdown, and not every application
> > cares about the order.  The ones that do care can sort the overlays in
> > the order they want.
> >
> > Or maybe I'm missing something: can you explain why the order matters
> > in a couple of specific examples from Org?
> 
> You are right. `overlays-in' docstring does not give any promises.
> It is not really a big deal for Org as well (can as well sort the return
> value).
> 
> The only thing that could be useful on Emacs side is explicitly stating
> in the `overlays-in' docstring that overlay list may be in arbitrary
> order.

I'll wait for a few days for other ideas and opinions, and if nothing
pops up, I will amend the documentation (and NEWS, as this is probably
NEWS-worthy).

Thanks.

bug#59067: 29.0.50; Exexpected overlay order in `overlays-in' return value

[Matt Armstrong]

Eli Zaretskii <eliz@gnu.org> writes:

> I'll wait for a few days for other ideas and opinions, and if nothing
> pops up, I will amend the documentation (and NEWS, as this is probably
> NEWS-worthy).

I think amending the documentation is the right approach, and agree that
it is NEWS-worthy.

In Emacs git we have already seen one fix related to this issue:

651bf0a999 (Fix overlays order in Flyspell (bug#58970), 2022-11-03)

...with that example, and this one from Org, we can rationally expect
more.

The original overlay implementation happened to provide one ordering,
but it could change when the overlay "center" moved, so packages that
rely on anything specific are on shaky ground.

bug#59067: 29.0.50; Exexpected overlay order in `overlays-in' return value

[Eli Zaretskii]

> Cc: 59067@debbugs.gnu.org
> Date: Sun, 06 Nov 2022 09:16:37 +0200
> From: Eli Zaretskii <eliz@gnu.org>
> 
> > From: Ihor Radchenko <yantar92@posteo.net>
> > Cc: 59067@debbugs.gnu.org
> > Date: Sun, 06 Nov 2022 07:04:54 +0000
> > 
> > You are right. `overlays-in' docstring does not give any promises.
> > It is not really a big deal for Org as well (can as well sort the return
> > value).
> > 
> > The only thing that could be useful on Emacs side is explicitly stating
> > in the `overlays-in' docstring that overlay list may be in arbitrary
> > order.
> 
> I'll wait for a few days for other ideas and opinions, and if nothing
> pops up, I will amend the documentation (and NEWS, as this is probably
> NEWS-worthy).

Now done.

bug#59067: 29.0.50; Exexpected overlay order in `overlays-in' return value

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

> You are right. `overlays-in' docstring does not give any promises.
> It is not really a big deal for Org as well (can as well sort the return
> value).

Maybe we could provide a `sorted` argument to `overlays-in`, but the
problem is that it's not clear what is "the right ordering".

Maybe Someone™ should browse through the various calls to `overlays-in`
out there to try and see which orderings could be useful.


        Stefan

bug#59067: 29.0.50; Exexpected overlay order in `overlays-in' return value

[Dmitry Gutov]

On 10.11.2022 16:03, Stefan Monnier via Bug reports for GNU Emacs, the 
Swiss army knife of text editors wrote:
> Maybe Someone™ should browse through the various calls to `overlays-in`
> out there to try and see which orderings could be useful.

FWIW, mmm-mode uses overlay sorting based on the value of overlay-start 
(first come overlays where this value is higher, so basically the more 
deeply nested ones, if we imagine all overlays to be strictly nested, as 
is the case with mmm-mode).

It uses a custom sorting function, though (which also takes priority 
into account), so it shouldn't be affected by the breakage.

You can check it out here, it also seems reasonable as the potential 
default sort: 
https://git.savannah.gnu.org/cgit/emacs/elpa.git/tree/mmm-region.el?h=externals/mmm-mode#n148

If it's not too expensive to use as default, that is.

bug#59067: 29.0.50; Exexpected overlay order in `overlays-in' return value

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

>> Maybe Someone™ should browse through the various calls to `overlays-in`
>> out there to try and see which orderings could be useful.
>
> FWIW, mmm-mode uses overlay sorting based on the value of overlay-start
> (first come overlays where this value is higher, so basically the more
> deeply nested ones, if we imagine all overlays to be strictly nested, as is
> the case with mmm-mode).

AFAICT it sorts first based on priority and only for equal-priority
overlays does it use the overlay's start.

Is there any specific reason for this particular ordering?

> You can check it out here, it also seems reasonable as the potential default
> sort:
> https://git.savannah.gnu.org/cgit/emacs/elpa.git/tree/mmm-region.el?h=externals/mmm-mode#n148
>
> If it's not too expensive to use as default, that is.

I was thinking of doing like we did for `overlays-at`, i.e. leave the
default to "unsorted" but add a `sorted` argument.  This also acts as
a reminder that the default is not sorted.

        Stefan

bug#59067: 29.0.50; Exexpected overlay order in `overlays-in' return value

[Dmitry Gutov]

On 10.11.2022 22:51, Stefan Monnier via Bug reports for GNU Emacs, the 
Swiss army knife of text editors wrote:
>>> Maybe Someone™ should browse through the various calls to `overlays-in`
>>> out there to try and see which orderings could be useful.
>> FWIW, mmm-mode uses overlay sorting based on the value of overlay-start
>> (first come overlays where this value is higher, so basically the more
>> deeply nested ones, if we imagine all overlays to be strictly nested, as is
>> the case with mmm-mode).
> AFAICT it sorts first based on priority and only for equal-priority
> overlays does it use the overlay's start.
> 
> Is there any specific reason for this particular ordering?

Historical, I suppose. mmm-mode doesn't set the 'priority' property 
these days (the little snippet of code doing that is commented out).

It kind of makes sense, but I don't have a better argument than that.

>> You can check it out here, it also seems reasonable as the potential default
>> sort:
>> https://git.savannah.gnu.org/cgit/emacs/elpa.git/tree/mmm-region.el?h=externals/mmm-mode#n148
>>
>> If it's not too expensive to use as default, that is.
> I was thinking of doing like we did for `overlays-at`, i.e. leave the
> default to "unsorted" but add a `sorted` argument.  This also acts as
> a reminder that the default is not sorted.

Yeah, ok.

bug#59067: 29.0.50; Exexpected overlay order in `overlays-in' return value

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

>>>> Maybe Someone™ should browse through the various calls to `overlays-in`
>>>> out there to try and see which orderings could be useful.
>>> FWIW, mmm-mode uses overlay sorting based on the value of overlay-start
>>> (first come overlays where this value is higher, so basically the more
>>> deeply nested ones, if we imagine all overlays to be strictly nested, as is
>>> the case with mmm-mode).
>> AFAICT it sorts first based on priority and only for equal-priority
>> overlays does it use the overlay's start.
>> Is there any specific reason for this particular ordering?
>
> Historical, I suppose. mmm-mode doesn't set the 'priority' property these
> days (the little snippet of code doing that is commented out).
>
> It kind of makes sense, but I don't have a better argument than that.

I'm not asking for any kind of justification, but I'm wondering what
would happen if you used a different sort order (i.e. the same but in
reverse, or sorted by overlays's end, ...): would the rest of the code
need to be adjusted?  If so, in a trivial way?  Or does some of the
algorithm rely crucially on this particular ordering?

In many cases, I have found that the ordering doesn't really matter,
as long as it's deterministic.


        Stefan

bug#59067: 29.0.50; Exexpected overlay order in `overlays-in' return value

[Dmitry Gutov]

On 10.11.2022 23:56, Stefan Monnier wrote:
> I'm not asking for any kind of justification, but I'm wondering what
> would happen if you used a different sort order (i.e. the same but in
> reverse, or sorted by overlays's end, ...): would the rest of the code
> need to be adjusted?  If so, in a trivial way?  Or does some of the
> algorithm rely crucially on this particular ordering?

Most of the code there needs to use the "innermost" overlay, and more or 
less ignore the rest of them.

If the return value was in reverse, I think the adjustment would be to 
call 'reverse', or sort it all over again, rather than calling (car 
(last overlays)) every time.

Another place which might be important is the order in which the 'face' 
property is applied by Emacs (with 'priority' being equal).

bug#59067: 29.0.50; Exexpected overlay order in `overlays-in' return value

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

>> I'm not asking for any kind of justification, but I'm wondering what
>> would happen if you used a different sort order (i.e. the same but in
>> reverse, or sorted by overlays's end, ...): would the rest of the code
>> need to be adjusted?  If so, in a trivial way?  Or does some of the
>> algorithm rely crucially on this particular ordering?
>
> Most of the code there needs to use the "innermost" overlay, and more or
> less ignore the rest of them.

Hmm... but we're talking about `overlays-in`, so many/most overlays
might be completely disjoint and thus incomparable in the sense of
which one is "innermost".

> Another place which might be important is the order in which the 'face'
>  property is applied by Emacs (with 'priority' being equal).

Same here: this is designed for the case where all of those overlays
cover a given position, so they're not disjoint.  This said, sorting
using that same algorithm for disjoint overlays would end up sorting by
overlay-start, if I read the code correctly, so it might not be
a bad choice.


        Stefan

bug#59067: 29.0.50; Exexpected overlay order in `overlays-in' return value

[Eli Zaretskii]

> Date: Fri, 11 Nov 2022 04:13:03 +0200
> Cc: 59067@debbugs.gnu.org, Ihor Radchenko <yantar92@posteo.net>,
>  Eli Zaretskii <eliz@gnu.org>
> From: Dmitry Gutov <dgutov@yandex.ru>
> 
> Another place which might be important is the order in which the 'face' 
> property is applied by Emacs (with 'priority' being equal).

The display code sorts the overlays before applying them, so this is
covered.