Subject: Re: bug#18361: New 'sort' implementation can crash Emacs

From: Paul Eggert <[email-masked]>
Date: Fri, 29 Aug 2014 16:07:09 -0700

Dmitry Antipov wrote:
> Can you provide an example?

Sure, a comparison function that returns a new random value every time 
you call it.  Such a function is most likely not well formed, that is, 
it most likely does not define a total order.

> Is that just a poor property of the particular qsort(_r) implementation?

Yes and no.  qsort is allowed to have undefined behavior (what you're 
calling a "poor property") if given a comparison function that is not a 
total order; see 
<http://pubs.opengroup.org/onlinepubs/9699919799/functions/qsort.html> 
DESCRIPTION paragraph 4.  Perhaps some qsort implementations have well 
defined behavior in this case (and so don't have the "poor property"), 
but there are performance reasons for qsort to have the "poor property" 
and in my experience most implementations have it.  GNU qsort and 
qsort_r, for example, have the "poor property".