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

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

[João Távora]

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.

João

diff --git a/src/buffer.c b/src/buffer.c
index 2d508f35cf..14722f7c17 100644
--- a/src/buffer.c
+++ b/src/buffer.c
@@ -4151,7 +4151,7 @@ OVERLAY.  */)
 \f
 DEFUN ("overlays-at", Foverlays_at, Soverlays_at, 1, 2, 0,
        doc: /* Return a list of the overlays that contain the character at POS.
-If SORTED is non-nil, then sort them by decreasing priority.  */)
+If SORTED is non-nil, then sort them by increasing priority.  */)
   (Lisp_Object pos, Lisp_Object sorted)
 {
   ptrdiff_t len, noverlays;

diff --git a/doc/lispref/display.texi b/doc/lispref/display.texi
index 2ed848adf3..181b003501 100644
--- a/doc/lispref/display.texi
+++ b/doc/lispref/display.texi
@@ -1806,7 +1806,7 @@ Finding Overlays
 @defun overlays-at pos &optional sorted
 This function returns a list of all the overlays that cover the character at
 position @var{pos} in the current buffer.  If @var{sorted} is non-@code{nil},
-the list is in decreasing order of priority, otherwise it is in no particular
+the list is in increasing order of priority, otherwise it is in no particular
 order.  An overlay contains position @var{pos} if it begins at or before
 @var{pos}, and ends after @var{pos}.


In GNU Emacs 26.0.50 (build 1, x86_64-pc-linux-gnu, X toolkit, Xaw scroll bars)
 of 2017-08-24 built on lolita
Repository revision: 5c048f5b327bbcd93d69c332a6c51ab139cd8071
Windowing system distributor 'The X.Org Foundation', version 11.0.11903000
System Description:	Ubuntu 17.04

Recent messages:
Undo!
Saving file /home/capitaomorte/Source/Emacs/emacs/src/buffer.c...
Wrote /home/capitaomorte/Source/Emacs/emacs/src/buffer.c
Undo!
Saving file /home/capitaomorte/Source/Emacs/emacs/src/buffer.c...
Wrote /home/capitaomorte/Source/Emacs/emacs/src/buffer.c
Finding changes in /home/capitaomorte/Source/Emacs/emacs/src/buffer.c...done
You can run the command ‘vc-diff’ with C-x v =
Finding changes in /home/capitaomorte/Source/Emacs/emacs/src/buffer.c...done
Mark set [2 times]
Quit
Configured using:
 'configure --with-modules --with-x-toolkit=lucid'

Configured features:
XPM JPEG TIFF GIF PNG RSVG SOUND DBUS GSETTINGS NOTIFY GNUTLS LIBXML2
FREETYPE M17N_FLT LIBOTF XFT ZLIB TOOLKIT_SCROLL_BARS LUCID X11 MODULES

Important settings:
  value of $LC_CTYPE: en_US.UTF-8
  value of $LC_MONETARY: pt_PT.UTF-8
  value of $LC_NUMERIC: pt_PT.UTF-8
  value of $LC_TIME: pt_PT.UTF-8
  value of $LANG: en_US.UTF-8
  value of $XMODIFIERS: @im=ibus
  locale-coding-system: utf-8-unix

Major mode: Diff

Minor modes in effect:
  global-aggressive-indent-mode: t
  shell-dirtrack-mode: t
  sly-autodoc-mode: t
  erc-list-mode: t
  erc-menu-mode: t
  erc-autojoin-mode: t
  erc-ring-mode: t
  erc-networks-mode: t
  erc-pcomplete-mode: t
  erc-track-mode: t
  erc-match-mode: t
  erc-button-mode: t
  erc-fill-mode: t
  erc-stamp-mode: t
  erc-netsplit-mode: t
  erc-irccontrols-mode: t
  erc-noncommands-mode: t
  erc-move-to-prompt-mode: t
  erc-readonly-mode: t
  diff-auto-refine-mode: t
  whitespace-mode: t
  electric-pair-mode: t
  ido-everywhere: t
  delete-selection-mode: t
  global-auto-revert-mode: t
  show-paren-mode: t
  yas-global-mode: t
  yas-minor-mode: t
  cl-old-struct-compat-mode: t
  global-eldoc-mode: t
  electric-indent-mode: t
  mouse-wheel-mode: t
  file-name-shadow-mode: t
  global-font-lock-mode: t
  font-lock-mode: t
  blink-cursor-mode: t
  auto-composition-mode: t
  auto-encryption-mode: t
  auto-compression-mode: t
  buffer-read-only: t
  column-number-mode: t
  line-number-mode: t
  transient-mark-mode: t

Load-path shadows:
~/Source/Emacs/darkroom/darkroom hides /home/capitaomorte/.emacs.d/elpa/darkroom-0.1/darkroom

Features:
(shadow sort emacsbug sendmail descr-text crm aggressive-indent tabify
hanja-util vc-annotate vc-filewise smerge-mode vc-dir trace ibuf-ext
ibuffer ibuffer-loaddefs sly-named-readtables sly-fancy sly-tramp tramp
tramp-compat tramp-loaddefs trampver ucs-normalize shell parse-time
sly-indentation sly-cl-indent cl-indent sly-stickers color hi-lock
sly-trace-dialog sly-fontifying-fu sly-package-fu sly-scratch
sly-fancy-trace sly-fancy-inspector sly-autodoc sly-parse sly-mrepl
network-stream nsm starttls tls gnutls sly info gud sly-completion
sly-buttons sly-messages sly-common apropos arc-mode archive-mode
noutline outline hyperspec browse-url display-line-numbers mail-extr
ffap etags log-view semantic/symref/grep semantic/symref
semantic/util-modes semantic/util semantic semantic/tag semantic/lex
semantic/fw mode-local cedet vc-bzr vc-src vc-sccs vc-svn vc-cvs vc-rcs
erc-list erc-menu erc-join erc-ring erc-networks erc-pcomplete pcomplete
erc-track erc-match erc-button erc-fill erc-stamp erc-netsplit
erc-goodies erc erc-backend erc-compat cua-rect rect cua-base eieio-opt
speedbar sb-image ezimage dframe edebug disass perl-mode flymake-tests
pulse warnings imenu base16-hopscotch-theme base16-irblack-theme
base16-isotope-theme base16-london-tube-theme base16-default-light-theme
base16-eighties-theme base16-chalk-theme base16-solarflare-theme
base16-tomorrow-theme base16-theme cus-theme hippie-exp bug-reference
cl-print ert-x ert find-func ewoc debug help-fns radix-tree misearch
multi-isearch vc-git diff-mode linum hideshow whitespace cc-mode
cc-fonts cc-guess cc-menus cc-cmds cc-styles cc-align cc-engine cc-langs
cc-vars cc-defs cc-bytecomp git-rebase-mode thingatpt darkroom
face-remap sly-named-readtables-autoloads sly-autoloads flymake-easy
flymake flymake-proc flymake-ui rust-mode json map pp cus-edit cus-start
cus-load wid-edit epa-file windmove ediff-merg ediff-wind ediff-diff
ediff-mult ediff-help ediff-init ediff-util ediff elec-pair ido delsel
autorevert filenotify paren server log-edit message puny dired-x dired
desktop frameset pcase dired-loaddefs subr-x format-spec rfc822 mml
mml-sec epa derived epg gnus-util rmail rmail-loaddefs mm-decode
mm-bodies mm-encode mail-parse rfc2231 rfc2047 rfc2045 mm-util
ietf-drums mail-prsvr mailabbrev mail-utils gmm-utils mailheader
pcvs-util add-log grep compile comint ansi-color vc vc-dispatcher advice
xref project ring cl-extra yasnippet help-mode easy-mmode edmacro kmacro
holy cl finder-inf rx package easymenu epg-config url-handlers url-parse
auth-source cl-seq eieio eieio-core cl-macs eieio-loaddefs
password-cache url-vars seq byte-opt gv bytecomp byte-compile cconv
cl-loaddefs cl-lib time-date mule-util tooltip eldoc electric uniquify
ediff-hook vc-hooks lisp-float-type mwheel term/x-win x-win
term/common-win x-dnd tool-bar dnd fontset image regexp-opt fringe
tabulated-list replace newcomment text-mode elisp-mode lisp-mode
prog-mode register page menu-bar rfn-eshadow isearch timer select
scroll-bar mouse jit-lock font-lock syntax facemenu font-core
term/tty-colors frame cl-generic cham georgian utf-8-lang misc-lang
vietnamese tibetan thai tai-viet lao korean japanese eucjp-ms cp51932
hebrew greek romanian slovak czech european ethiopic indian cyrillic
chinese composite charscript charprop case-table epa-hook jka-cmpr-hook
help simple abbrev obarray minibuffer cl-preloaded nadvice loaddefs
button faces cus-face macroexp files text-properties overlay sha1 md5
base64 format env code-pages mule custom widget hashtable-print-readable
backquote dbusbind inotify dynamic-setting system-font-setting
font-render-setting x-toolkit x multi-tty make-network-process emacs)

Memory information:
((conses 16 930795 207805)
 (symbols 48 50058 1)
 (miscs 40 3425 957)
 (strings 32 147889 13156)
 (string-bytes 1 5467904)
 (vectors 16 73522)
 (vector-slots 8 1956561 77022)
 (floats 8 329 1718)
 (intervals 56 33152 527)
 (buffers 992 148))

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

[Eli Zaretskii]

> From: joaotavora@gmail.com (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.  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)))))

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

So I think we should rather reverse the list which overlays-at
returns.

Stefan?

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

[João Távora]

Eli Zaretskii <eliz@gnu.org> writes:

>> From: joaotavora@gmail.com (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 :-).

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

[Eli Zaretskii]

> From: joaotavora@gmail.com (João Távora)
> Cc: 28390@debbugs.gnu.org,  monnier@iro.umontreal.ca
> Date: Fri, 08 Sep 2017 09:57:28 +0100
> 
> Eli Zaretskii <eliz@gnu.org> writes:
> 
> > 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?

I don't think so.  I believe this optional argument is used very
rarely.

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

This is the code which was replaced when overlays-at got its optional
argument in that Stefan's change.

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

Look at the changeset of commit 20fa59a0, you will see that the uses
if 'sort' were replaced with calls to overlays-at with the new
optional argument.

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

I'm not sure it's too late.

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

[João Távora]

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

---------- Forwarded message ----------
From: João Távora <joaotavora@gmail.com>
Date: Fri, Sep 8, 2017 at 7:48 PM
Subject: Re: bug#28390: 26.0.50; overlays-at actually sorts by increating
priority
To: Eli Zaretskii <eliz@gnu.org>

On Fri, Sep 8, 2017 at 10:47 AM, Eli Zaretskii <eliz@gnu.org> wrote:
> >
> > Really? Won't that ripple very paintuflly across the elisp ecosphere?
>
> I don't think so.  I believe this optional argument is used very
> rarely.
>
> > I do agree that it should sort the other way, though. But it's too late
> > for that, bugs will be features :-).
>
> I'm not sure it's too late.

You might be right. Even I overestimated how much I use it in my libs. I
don't.

And the few first pages of a github code search for overlays-at don't
disprove
you. But they don't prove anything either.

Anyway, your call. I wouldn't do it, what's to gain besides consistency?

-- 
João Távora

[-- Attachment #2: Type: text/html, Size: 1785 bytes --]

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

[Stefan Monnier]

> So I think we should rather reverse the list which overlays-at
> returns.  Stefan?

No preference on my side,


        Stefan

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

[Eli Zaretskii]

> From: Stefan Monnier <monnier@IRO.UMontreal.CA>
> Cc: joaotavora@gmail.com (João Távora),
>         28390@debbugs.gnu.org
> Date: Sun, 10 Sep 2017 09:53:07 -0400
> 
> > So I think we should rather reverse the list which overlays-at
> > returns.  Stefan?
> 
> No preference on my side,

Done, and closing the bug report.

Thanks.