From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Paul Eggert Newsgroups: gmane.emacs.bugs Subject: bug#18361: New 'sort' implementation can crash Emacs Date: Sat, 30 Aug 2014 06:44:54 -0700 Organization: UCLA Computer Science Department Message-ID: <5401D556.4060102@cs.ucla.edu> References: <5400EFA5.6090902@cs.ucla.edu> <540102E5.6040404@yandex.ru> <5401079D.7070505@cs.ucla.edu> <54015C22.5030108@yandex.ru> <54015FA8.5070400@cs.ucla.edu> <54017555.8010903@yandex.ru> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 7bit X-Trace: ger.gmane.org 1409406391 16723 80.91.229.3 (30 Aug 2014 13:46:31 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Sat, 30 Aug 2014 13:46:31 +0000 (UTC) Cc: 18361@debbugs.gnu.org To: Dmitry Antipov Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Sat Aug 30 15:46:23 2014 Return-path: Envelope-to: geb-bug-gnu-emacs@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1XNiz0-0001od-Oc for geb-bug-gnu-emacs@m.gmane.org; Sat, 30 Aug 2014 15:46:22 +0200 Original-Received: from localhost ([::1]:46610 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1XNiz0-0002l3-D4 for geb-bug-gnu-emacs@m.gmane.org; Sat, 30 Aug 2014 09:46:22 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:47570) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1XNiyp-0002j7-0X for bug-gnu-emacs@gnu.org; Sat, 30 Aug 2014 09:46:18 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1XNiyh-0002NC-H0 for bug-gnu-emacs@gnu.org; Sat, 30 Aug 2014 09:46:10 -0400 Original-Received: from debbugs.gnu.org ([140.186.70.43]:34307) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1XNiyh-0002N8-Dv for bug-gnu-emacs@gnu.org; Sat, 30 Aug 2014 09:46:03 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.80) (envelope-from ) id 1XNiyg-0002np-Kg for bug-gnu-emacs@gnu.org; Sat, 30 Aug 2014 09:46:02 -0400 X-Loop: help-debbugs@gnu.org Resent-From: Paul Eggert Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Sat, 30 Aug 2014 13:46:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 18361 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: Original-Received: via spool by 18361-submit@debbugs.gnu.org id=B18361.140940630710696 (code B ref 18361); Sat, 30 Aug 2014 13:46:02 +0000 Original-Received: (at 18361) by debbugs.gnu.org; 30 Aug 2014 13:45:07 +0000 Original-Received: from localhost ([127.0.0.1]:54103 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1XNixl-0002mM-Nt for submit@debbugs.gnu.org; Sat, 30 Aug 2014 09:45:06 -0400 Original-Received: from smtp.cs.ucla.edu ([131.179.128.62]:38693) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1XNixi-0002lQ-H8 for 18361@debbugs.gnu.org; Sat, 30 Aug 2014 09:45:03 -0400 Original-Received: from localhost (localhost.localdomain [127.0.0.1]) by smtp.cs.ucla.edu (Postfix) with ESMTP id EE7F1A60002; Sat, 30 Aug 2014 06:44:56 -0700 (PDT) X-Virus-Scanned: amavisd-new at smtp.cs.ucla.edu Original-Received: from smtp.cs.ucla.edu ([127.0.0.1]) by localhost (smtp.cs.ucla.edu [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id RxuArLLbveDG; Sat, 30 Aug 2014 06:44:54 -0700 (PDT) Original-Received: from [192.168.1.9] (pool-71-177-17-123.lsanca.dsl-w.verizon.net [71.177.17.123]) by smtp.cs.ucla.edu (Postfix) with ESMTPSA id 96231A60013; Sat, 30 Aug 2014 06:44:54 -0700 (PDT) User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.0 In-Reply-To: <54017555.8010903@yandex.ru> X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 Precedence: list X-detected-operating-system: by eggs.gnu.org: GNU/Linux 3.x X-Received-From: 140.186.70.43 X-BeenThere: bug-gnu-emacs@gnu.org List-Id: "Bug reports for GNU Emacs, the Swiss army knife of text editors" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Original-Sender: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.bugs:92857 Archived-At: 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.