Subject: Re: bug#28390: 26.0.50; overlays-at actually sorts by increating priority

From: [email-masked] (João Távora)
Date: Fri, 08 Sep 2017 09:57:28 +0100

Eli Zaretskii <[email-masked]> writes:

>> From: [email-masked] (João Távora)
>> Date: Thu, 07 Sep 2017 23:21:15 +0100
>> 
>> Hi Stefan, maintainters
>> 
>> I believe I found a rather easy glitch in the doc of overlays-at. It
>> says if SORTED in non-nil it sorts overlays by "decreasing" priority,
>> but actually the reverse is true.
>> 
>> Line 3234 of buffer.c seems to confirm this:
>> 
>>   /* Sort the overlays into the proper order: increasing priority.  */
>> 
>> and compare_overlays passed to qsort() as well:
>> 
>>     return s1->priority < s2->priority ? -1 : 1;
>> 
>> I also did this test:
>> 
>>    (progn
>>      (mapc #'delete-overlay (overlays-in (point-min) (point-max)))
>>      (dotimes (i 4) (overlay-put (make-overlay 20 30) 'priority i))
>>      (mapcar (lambda (ov) (overlay-get ov 'priority)) (overlays-at 20 t)))
>> 
>> this returns (0 1 2 3)
>> 
>> This is a 3-year-old docbug, so I'm suspicious I might be missing
>> something. Anyway here's a docpatch.
>
> I think the doc string says what the implementation was supposed to
> do, so we need to change the implementation instead.

Really? Won't that ripple very paintuflly across the elisp ecosphere?

> If you look at the changeset where the SORTED argument was introduced,
> you will see that the old code sorted the list returned by overlays-at
> in descending order of priorities, i.e. overlays with the largest
> priority first.  It used 'sort' like this:
>
>   (sort (mapcar #'overlay-properties (overlays-at p))
>         (lambda (A B) (> (or (cadr (memq 'priority A)) 0)
>                     (or (cadr (memq 'priority B)) 0)))))

I don't follow, where is the code that did this, or is this just an
illustration?

The optional SORTED to overlays-at is first introduced in buffer.c in
Stefan's 20fa59a0 commit. Before that, I see no evidence of explicit
sorting.

DEFUN("overlays-at") calls sort_overlays(), which has always
used qsort() with compare_overlays(), which in turn always returned
negatives if prio1 < prio2. (always ~= since 1994)

> The doc string of 'sort' says that its PREDICATE function should
> return non-nil if the first element passed to PREDICATE should sort
> _before_ the second.  And the predicate above uses '>'.

But where was sort() ever used before Stefan's 2014 change? Did
overlays-at make any sort guarantee back then?

I do agree that it should sort the other way, though. But it's too late
for that, bugs will be features :-).