[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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

From: Paul Eggert
Subject: bug#18361: New 'sort' implementation can crash Emacs
Date: Sat, 30 Aug 2014 06:44:54 -0700
User-agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.0

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.

reply via email to

[Prev in Thread] Current Thread [Next in Thread]