GNU bug report logs - #18361
New 'sort' implementation can crash Emacs

Previous Next

Package: emacs;

Reported by: Paul Eggert <eggert <at> cs.ucla.edu>

Date: Fri, 29 Aug 2014 21:26:01 UTC

Severity: minor

Done: Paul Eggert <eggert <at> cs.ucla.edu>

Bug is archived. No further changes may be made.

Full log

Message #23 received at 18361 <at> debbugs.gnu.org (full text, mbox):

From: Paul Eggert <eggert <at> cs.ucla.edu>
To: Dmitry Antipov <dmantipov <at> yandex.ru>
Cc: 18361 <at> debbugs.gnu.org
Subject: Re: bug#18361: New 'sort' implementation can crash Emacs
Date: Sat, 30 Aug 2014 06:44:54 -0700

Dmitry Antipov wrote:

> couldn't we detect an improper comparison
> function at runtime?

Not easily, because it doesn't suffice to check whether the function is 
antisymmetrical at each comparison (a local property).  One must check 
whether the function defines a total order (a global property).  One way 
to do such a check is to sort the array, and then compare all pairs to 
verify that the function is indeed a total order.  But of course that 
begs the question of sorting the array, plus it's an O(N**2) check, so 
it's not practical.
This bug report was last modified 10 years and 347 days ago.

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.