bug#23205: 25.0.92; sort-tests is flaky

bug#23205: 25.0.92; sort-tests is flaky

[Philipp Stephani]

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

In the emacs-25 branch, in the directory test/automated, run:

declare -i failures=0
for ((i=0; i<1000; i++)); do
if ! output="$(make sort-tests 2>&1)"; then
((failures++))
echo "Iteration $i: $output"
fi
done
echo "Failures: $failures"

There will be typically a small number of failures (< 10), caused by
e.g.

Test sort-tests--lines condition:
(ert-test-failed
((should
(string=
(substring ... 0 -1)
sorted-words))
:form
(string= "Zi
zI" "zI
Zi")
:value nil))

This is presumably due to non-stable sorting. Either the sorting should
be made stable, or the test shouldn't assume stable sorting.



In GNU Emacs 25.0.92.1 (x86_64-unknown-linux-gnu, GTK+ Version 3.10.8)
of 2016-03-24 built on localhost
Repository revision: 077b78cffc0711717ae8976ef302b788e88d27a8
Windowing system distributor 'The X.Org Foundation', version 11.0.11701000
System Description: Ubuntu 14.04 LTS

Configured features:
XPM JPEG TIFF GIF PNG SOUND GSETTINGS NOTIFY FREETYPE XFT ZLIB
TOOLKIT_SCROLL_BARS GTK3 X11

Important settings:
value of $LANG: en_US.UTF-8
locale-coding-system: utf-8-unix

Major mode: Lisp Interaction

Minor modes in effect:
tooltip-mode: t
global-eldoc-mode: t
electric-indent-mode: t
mouse-wheel-mode: t
tool-bar-mode: t
menu-bar-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
line-number-mode: t
transient-mark-mode: t

Recent messages:
For information about GNU Emacs and the GNU system, type C-h C-a.

Load-path shadows:
None found.

Features:
(shadow sort mail-extr emacsbug message dired format-spec rfc822 mml
mml-sec password-cache epg epg-config gnus-util mm-decode mm-bodies
mm-encode mail-parse rfc2231 mailabbrev gmm-utils mailheader sendmail
rfc2047 rfc2045 ietf-drums mm-util help-fns help-mode easymenu
cl-loaddefs pcase cl-lib mail-prsvr mail-utils time-date mule-util
tooltip eldoc electric uniquify ediff-hook vc-hooks lisp-float-type
mwheel x-win term/common-win x-dnd tool-bar dnd fontset image regexp-opt
fringe tabulated-list newcomment elisp-mode lisp-mode prog-mode register
page menu-bar rfn-eshadow timer select scroll-bar mouse jit-lock
font-lock syntax facemenu font-core 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 charscript case-table epa-hook
jka-cmpr-hook help simple abbrev 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 inotify dynamic-setting
system-font-setting font-render-setting move-toolbar gtk x-toolkit x
multi-tty make-network-process emacs)

Memory information:
((conses 16 87235 4859)
(symbols 48 19673 0)
(miscs 40 278 121)
(strings 32 14530 4256)
(string-bytes 1 423141)
(vectors 16 11958)
(vector-slots 8 433605 5930)
(floats 8 162 10)
(intervals 56 184 0)
(buffers 976 11)
(heap 1024 50063 1046))
-- 

Google Germany GmbH
Erika-Mann-Straße 33
80636 München

Registergericht und -nummer: Hamburg, HRB 86891
Sitz der Gesellschaft: Hamburg
Geschäftsführer: Matthew Scott Sucherman, Paul Terence Manicle

Diese E-Mail ist vertraulich. Wenn Sie nicht der richtige Adressat sind,
leiten Sie diese bitte nicht weiter, informieren Sie den Absender und
löschen Sie die E-Mail und alle Anhänge. Vielen Dank.

This e-mail is confidential. If you are not the right addressee please do
not forward it, please inform the sender, and please erase this e-mail
including any attachments. Thanks.

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

bug#23205: 25.0.92; sort-tests is flaky

[Eli Zaretskii]

> From: Philipp Stephani <phst@google.com>
> Date: Sun, 03 Apr 2016 10:30:10 +0000
> 
> In the emacs-25 branch, in the directory test/automated, run: 
> 
> declare -i failures=0 
> for ((i=0; i<1000; i++)); do 
> if ! output="$(make sort-tests 2>&1)"; then 
> ((failures++)) 
> echo "Iteration $i: $output" 
> fi 
> done 
> echo "Failures: $failures" 
> 
> There will be typically a small number of failures (< 10), caused by 
> e.g. 
> 
> Test sort-tests--lines condition: 
> (ert-test-failed 
> ((should 
> (string= 
> (substring ... 0 -1) 
> sorted-words)) 
> :form 
> (string= "Zi 
> zI" "zI 
> Zi") 
> :value nil)) 
> 
> This is presumably due to non-stable sorting. Either the sorting should 
> be made stable, or the test shouldn't assume stable sorting. 

Do you sometimes see such failures if you just run the test once?

bug#23205: 25.0.92; sort-tests is flaky

[Philipp Stephani]

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

On Sun, Apr 3, 2016 at 4:58 PM Eli Zaretskii <eliz@gnu.org> wrote:

> > From: Philipp Stephani <phst@google.com>
> > Date: Sun, 03 Apr 2016 10:30:10 +0000
> >
> > In the emacs-25 branch, in the directory test/automated, run:
> >
> > declare -i failures=0
> > for ((i=0; i<1000; i++)); do
> > if ! output="$(make sort-tests 2>&1)"; then
> > ((failures++))
> > echo "Iteration $i: $output"
> > fi
> > done
> > echo "Failures: $failures"
> >
> > There will be typically a small number of failures (< 10), caused by
> > e.g.
> >
> > Test sort-tests--lines condition:
> > (ert-test-failed
> > ((should
> > (string=
> > (substring ... 0 -1)
> > sorted-words))
> > :form
> > (string= "Zi
> > zI" "zI
> > Zi")
> > :value nil))
> >
> > This is presumably due to non-stable sorting. Either the sorting should
> > be made stable, or the test shouldn't assume stable sorting.
>
> Do you sometimes see such failures if you just run the test once?
>

I don't know, what's the difference between running it once and running it
1000 times? Since it fails randomly, it could fail in any iteration,
including the first one.
-- 

Google Germany GmbH
Erika-Mann-Straße 33
80636 München

Registergericht und -nummer: Hamburg, HRB 86891
Sitz der Gesellschaft: Hamburg
Geschäftsführer: Matthew Scott Sucherman, Paul Terence Manicle

Diese E-Mail ist vertraulich. Wenn Sie nicht der richtige Adressat sind,
leiten Sie diese bitte nicht weiter, informieren Sie den Absender und
löschen Sie die E-Mail und alle Anhänge. Vielen Dank.

This e-mail is confidential. If you are not the right addressee please do
not forward it, please inform the sender, and please erase this e-mail
including any attachments. Thanks.

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

bug#23205: 25.0.92; sort-tests is flaky

[Eli Zaretskii]

> From: Philipp Stephani <phst@google.com>
> Date: Sun, 03 Apr 2016 21:00:50 +0000
> Cc: 23205@debbugs.gnu.org
> 
>  Do you sometimes see such failures if you just run the test once?
> 
> I don't know, what's the difference between running it once and running it 1000 times? Since it fails randomly,
> it could fail in any iteration, including the first one. 

You assume that it fails randomly.  I would like to know if that is
true.  It could be that the failures only happen if the test is run
repeatedly, couldn't it?

bug#23205: 25.0.92; sort-tests is flaky

[Philipp Stephani]

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

On Mon, Apr 4, 2016 at 4:34 AM Eli Zaretskii <eliz@gnu.org> wrote:

> > From: Philipp Stephani <phst@google.com>
> > Date: Sun, 03 Apr 2016 21:00:50 +0000
> > Cc: 23205@debbugs.gnu.org
> >
> >  Do you sometimes see such failures if you just run the test once?
> >
> > I don't know, what's the difference between running it once and running
> it 1000 times? Since it fails randomly,
> > it could fail in any iteration, including the first one.
>
> You assume that it fails randomly.  I would like to know if that is
> true.  It could be that the failures only happen if the test is run
> repeatedly, couldn't it?
>

It also happens when I delete sort-tests.elc before each iteration.
Interestingly `sort' uses the stable mergesort.
-- 

Google Germany GmbH
Erika-Mann-Straße 33
80636 München

Registergericht und -nummer: Hamburg, HRB 86891
Sitz der Gesellschaft: Hamburg
Geschäftsführer: Matthew Scott Sucherman, Paul Terence Manicle

Diese E-Mail ist vertraulich. Wenn Sie nicht der richtige Adressat sind,
leiten Sie diese bitte nicht weiter, informieren Sie den Absender und
löschen Sie die E-Mail und alle Anhänge. Vielen Dank.

This e-mail is confidential. If you are not the right addressee please do
not forward it, please inform the sender, and please erase this e-mail
including any attachments. Thanks.

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

bug#23205: 25.0.92; sort-tests is flaky

[Paul Eggert]

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

> Either the sorting should
> be made stable, or the test shouldn't assume stable sorting.

GNU Emacs's sorting is stable, but some sorting code in the test case is wrong, 
and the random tests that trigger the test-case bug occur only with a small 
probability. I installed the attached to fix the test-case bug. Thanks for 
reporting the details; it would have taken a while for me to track it down 
without that useful clue involving Zi and zI.

[-- Attachment #2: 0001-Fix-stability-confusion-in-sort-tests.txt --]
[-- Type: text/plain, Size: 1492 bytes --]

From 9d3bf9ffdc8aaf2a04288c743116716ad6e4e78a Mon Sep 17 00:00:00 2001
From: Paul Eggert <eggert@cs.ucla.edu>
Date: Wed, 6 Apr 2016 01:22:00 -0700
Subject: [PATCH] Fix stability confusion in sort-tests
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

Problem reported by Philipp Stephani (Bug#23205).
* test/automated/sort-tests.el:
(sort-tests--insert-words-sort-and-compare):
Don’t assume that reversing a sorted list is the same
as sorting with the reverse predicate.  This is not true
for stable sorts when items compare equal.
---
 test/automated/sort-tests.el | 6 ++++--
 1 file changed, 4 insertions(+), 2 deletions(-)

diff --git a/test/automated/sort-tests.el b/test/automated/sort-tests.el
index 5297329..f3a182c 100644
--- a/test/automated/sort-tests.el
+++ b/test/automated/sort-tests.el
@@ -40,8 +40,10 @@ sort-tests--insert-words-sort-and-compare
     (funcall function reverse (point-min) (point-max))
     (let ((sorted-words
            (mapconcat #'identity
-                      (let ((x (sort (copy-sequence words) less-predicate)))
-                        (if reverse (reverse x) x))
+                      (sort (copy-sequence words)
+                            (if reverse
+                                (lambda (a b) (funcall less-predicate b a))
+                              less-predicate))
                       separator)))
       (should (string= (substring (buffer-string) 0 -1) sorted-words)))))
 
-- 
2.5.5

bug#23205: 25.0.92; sort-tests is flaky

[Philipp Stephani]

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

On Wed, Apr 6, 2016 at 10:31 AM Paul Eggert <eggert@cs.ucla.edu> wrote:

> > Either the sorting should
> > be made stable, or the test shouldn't assume stable sorting.
>
> GNU Emacs's sorting is stable, but some sorting code in the test case is
> wrong,
> and the random tests that trigger the test-case bug occur only with a small
> probability. I installed the attached to fix the test-case bug. Thanks for
> reporting the details; it would have taken a while for me to track it down
> without that useful clue involving Zi and zI.
>

Thanks for the quick fix; confirmed that the test is no longer flaky.
-- 

Google Germany GmbH
Erika-Mann-Straße 33
80636 München

Registergericht und -nummer: Hamburg, HRB 86891
Sitz der Gesellschaft: Hamburg
Geschäftsführer: Matthew Scott Sucherman, Paul Terence Manicle

Diese E-Mail ist vertraulich. Wenn Sie nicht der richtige Adressat sind,
leiten Sie diese bitte nicht weiter, informieren Sie den Absender und
löschen Sie die E-Mail und alle Anhänge. Vielen Dank.

This e-mail is confidential. If you are not the right addressee please do
not forward it, please inform the sender, and please erase this e-mail
including any attachments. Thanks.

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