From unknown Sat Sep 13 17:04:03 2025 Content-Disposition: inline Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 X-Mailer: MIME-tools 5.509 (Entity 5.509) Content-Type: text/plain; charset=utf-8 From: bug#18361 <18361@debbugs.gnu.org> To: bug#18361 <18361@debbugs.gnu.org> Subject: Status: New 'sort' implementation can crash Emacs Reply-To: bug#18361 <18361@debbugs.gnu.org> Date: Sun, 14 Sep 2025 00:04:03 +0000 retitle 18361 New 'sort' implementation can crash Emacs reassign 18361 emacs submitter 18361 Paul Eggert severity 18361 minor thanks From debbugs-submit-bounces@debbugs.gnu.org Fri Aug 29 17:25:38 2014 Received: (at submit) by debbugs.gnu.org; 29 Aug 2014 21:25:38 +0000 Received: from localhost ([127.0.0.1]:53835 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1XNTfr-0008JP-LX for submit@debbugs.gnu.org; Fri, 29 Aug 2014 17:25:36 -0400 Received: from eggs.gnu.org ([208.118.235.92]:57937) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1XNTfp-0008JD-IA for submit@debbugs.gnu.org; Fri, 29 Aug 2014 17:25:34 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1XNTfa-0002BK-EK for submit@debbugs.gnu.org; Fri, 29 Aug 2014 17:25:28 -0400 X-Spam-Checker-Version: SpamAssassin 3.3.2 (2011-06-06) on eggs.gnu.org X-Spam-Level: X-Spam-Status: No, score=0.8 required=5.0 tests=BAYES_50 autolearn=disabled version=3.3.2 Received: from lists.gnu.org ([2001:4830:134:3::11]:49974) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1XNTfa-0002B8-3j for submit@debbugs.gnu.org; Fri, 29 Aug 2014 17:25:18 -0400 Received: from eggs.gnu.org ([2001:4830:134:3::10]:59487) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1XNTfS-00051T-I0 for bug-gnu-emacs@gnu.org; Fri, 29 Aug 2014 17:25:17 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1XNTfL-0001mN-3Y for bug-gnu-emacs@gnu.org; Fri, 29 Aug 2014 17:25:10 -0400 Received: from smtp.cs.ucla.edu ([131.179.128.62]:59667) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1XNTfK-0001jc-SE for bug-gnu-emacs@gnu.org; Fri, 29 Aug 2014 17:25:02 -0400 Received: from localhost (localhost.localdomain [127.0.0.1]) by smtp.cs.ucla.edu (Postfix) with ESMTP id 1A037A60014; Fri, 29 Aug 2014 14:25:02 -0700 (PDT) X-Virus-Scanned: amavisd-new at smtp.cs.ucla.edu 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 3AoFdKTrw3mn; Fri, 29 Aug 2014 14:24:53 -0700 (PDT) Received: from penguin.cs.ucla.edu (Penguin.CS.UCLA.EDU [131.179.64.200]) by smtp.cs.ucla.edu (Postfix) with ESMTPSA id 62D6DA60013; Fri, 29 Aug 2014 14:24:53 -0700 (PDT) Message-ID: <5400EFA5.6090902@cs.ucla.edu> Date: Fri, 29 Aug 2014 14:24:53 -0700 From: Paul Eggert Organization: UCLA Computer Science Department User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:24.0) Gecko/20100101 Thunderbird/24.7.0 MIME-Version: 1.0 To: bug-emacs , Dmitry Antipov Subject: New 'sort' implementation can crash Emacs Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6.x X-detected-operating-system: by eggs.gnu.org: Error: Malformed IPv6 address (bad octet value). X-Received-From: 2001:4830:134:3::11 X-Spam-Score: -4.0 (----) X-Debbugs-Envelope-To: submit X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -4.0 (----) The new implementation of 'sort' in the trunk invokes qsort (or qsort_r), but these functions have undefined behavior if the comparison function is ill-behaved. Since the comparison predicate is user-defined, this means a bad user-supplied comparison function could crash Emacs. One possible fix would be to build on the proposed patch in Bug#18360, except to change Emacs to always define its own qsort_r substitute, one that is known to produce some permutation of the input without crashing even if the comparison function is ill-behaved. From debbugs-submit-bounces@debbugs.gnu.org Fri Aug 29 18:47:12 2014 Received: (at 18361) by debbugs.gnu.org; 29 Aug 2014 22:47:12 +0000 Received: from localhost ([127.0.0.1]:53873 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1XNUwq-0003Oh-8r for submit@debbugs.gnu.org; Fri, 29 Aug 2014 18:47:12 -0400 Received: from forward1h.cmail.yandex.net ([87.250.230.16]:53849) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1XNUwn-0003OS-FS for 18361@debbugs.gnu.org; Fri, 29 Aug 2014 18:47:10 -0400 Received: from smtp4o.mail.yandex.net (smtp4o.mail.yandex.net [37.140.190.29]) by forward1h.cmail.yandex.net (Yandex) with ESMTP id 6A7FE138D; Sat, 30 Aug 2014 02:47:02 +0400 (MSK) Received: from smtp4o.mail.yandex.net (localhost [127.0.0.1]) by smtp4o.mail.yandex.net (Yandex) with ESMTP id 221E223228A3; Sat, 30 Aug 2014 02:47:02 +0400 (MSK) Received: from unknown (unknown [37.139.80.10]) by smtp4o.mail.yandex.net (nwsmtp/Yandex) with ESMTPSA id Qvoj9nFsG0-l1X4JOFe; Sat, 30 Aug 2014 02:47:01 +0400 (using TLSv1.2 with cipher AES128-SHA (128/128 bits)) (Client certificate not present) X-Yandex-Uniq: d499518b-dc0e-499b-bc71-0e2e90f2f3aa DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=yandex.ru; s=mail; t=1409352421; bh=626TRRVliEQfrRj6uyfRdWIHp3gx5oiQMaJ8fPW61U8=; h=Message-ID:Date:From:User-Agent:MIME-Version:To:CC:Subject: References:In-Reply-To:Content-Type:Content-Transfer-Encoding; b=BKRoyDPF1Ro5wvYmBj3wpxSfQVogI/1/6mQ+Rys5rWYuV5qoDQ4JTxQSv+Cg023SV 0tb+dXsPKinoXRcJRIWvET8mS7BeRst47Y9YFMkE4ZvpgfrGzuMc0+0wfljYE2iUJ1 KY76GyG1RUO6XRicxPwE7j/E6dVITmzAL4Ihgpdw= Authentication-Results: smtp4o.mail.yandex.net; dkim=pass header.i=@yandex.ru Message-ID: <540102E5.6040404@yandex.ru> Date: Sat, 30 Aug 2014 02:47:01 +0400 From: Dmitry Antipov User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.0 MIME-Version: 1.0 To: Paul Eggert Subject: Re: bug#18361: New 'sort' implementation can crash Emacs References: <5400EFA5.6090902@cs.ucla.edu> In-Reply-To: <5400EFA5.6090902@cs.ucla.edu> Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Score: 0.0 (/) X-Debbugs-Envelope-To: 18361 Cc: 18361@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: 0.0 (/) On 08/30/2014 01:24 AM, Paul Eggert wrote: > The new implementation of 'sort' in the trunk invokes qsort (or qsort_r), > but these functions have undefined behavior if the comparison function is > ill-behaved. Since the comparison predicate is user-defined, this means > a bad user-supplied comparison function could crash Emacs. I don't see how is that possible if we operate on a correctly initialized vector and sort_vector_predicate is a valid function accepting 2 arguments. Can you provide an example? Is that just a poor property of the particular qsort(_r) implementation? Dmitry From debbugs-submit-bounces@debbugs.gnu.org Fri Aug 29 19:07:45 2014 Received: (at 18361) by debbugs.gnu.org; 29 Aug 2014 23:07:45 +0000 Received: from localhost ([127.0.0.1]:53893 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1XNVGi-0003sg-NS for submit@debbugs.gnu.org; Fri, 29 Aug 2014 19:07:45 -0400 Received: from smtp.cs.ucla.edu ([131.179.128.62]:45341) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1XNVGg-0003sO-8i for 18361@debbugs.gnu.org; Fri, 29 Aug 2014 19:07:43 -0400 Received: from localhost (localhost.localdomain [127.0.0.1]) by smtp.cs.ucla.edu (Postfix) with ESMTP id 22ED6A60013; Fri, 29 Aug 2014 16:07:36 -0700 (PDT) X-Virus-Scanned: amavisd-new at smtp.cs.ucla.edu 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 e+zvj0-sFvke; Fri, 29 Aug 2014 16:07:31 -0700 (PDT) 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 A2F4CA60002; Fri, 29 Aug 2014 16:07:31 -0700 (PDT) Message-ID: <5401079D.7070505@cs.ucla.edu> Date: Fri, 29 Aug 2014 16:07:09 -0700 From: Paul Eggert Organization: UCLA Computer Science Department User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.0 MIME-Version: 1.0 To: Dmitry Antipov Subject: Re: bug#18361: New 'sort' implementation can crash Emacs References: <5400EFA5.6090902@cs.ucla.edu> <540102E5.6040404@yandex.ru> In-Reply-To: <540102E5.6040404@yandex.ru> Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Score: -2.3 (--) X-Debbugs-Envelope-To: 18361 Cc: 18361@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -2.3 (--) 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 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". From debbugs-submit-bounces@debbugs.gnu.org Sat Aug 30 01:07:59 2014 Received: (at 18361) by debbugs.gnu.org; 30 Aug 2014 05:07:59 +0000 Received: from localhost ([127.0.0.1]:53941 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1XNatK-000489-Vx for submit@debbugs.gnu.org; Sat, 30 Aug 2014 01:07:59 -0400 Received: from forward1h.cmail.yandex.net ([87.250.230.16]:60278) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1XNatF-00047t-Nb for 18361@debbugs.gnu.org; Sat, 30 Aug 2014 01:07:55 -0400 Received: from smtp1h.mail.yandex.net (smtp1h.mail.yandex.net [84.201.187.144]) by forward1h.cmail.yandex.net (Yandex) with ESMTP id 20D7D1304; Sat, 30 Aug 2014 09:07:47 +0400 (MSK) Received: from smtp1h.mail.yandex.net (localhost [127.0.0.1]) by smtp1h.mail.yandex.net (Yandex) with ESMTP id CBB6B1340777; Sat, 30 Aug 2014 09:07:46 +0400 (MSK) Received: from unknown (unknown [37.139.80.10]) by smtp1h.mail.yandex.net (nwsmtp/Yandex) with ESMTPSA id vTjqd1BbvS-7kReWNIS; Sat, 30 Aug 2014 09:07:46 +0400 (using TLSv1.2 with cipher AES128-SHA (128/128 bits)) (Client certificate not present) X-Yandex-Uniq: c59c0833-a2ec-4b4d-b975-0c96936739fd DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=yandex.ru; s=mail; t=1409375266; bh=e4iICvOGWZa/HlXE1EuzW3DT91byPIHsYhWxNDZRhW0=; h=Message-ID:Date:From:User-Agent:MIME-Version:To:CC:Subject: References:In-Reply-To:Content-Type:Content-Transfer-Encoding; b=ojgBaTNJKKbGxrlr4VxIFNcTv7WYA2pt5jCsCh0Q17dx+1ecOupqN3KX9rZSmLogt hz4Q+RDZmoCdTjxvbGs3y9/aGMyiMcdmksVp1Z6l922Go/9FVUZwWihoGETwRfeWqR ASwC2X3aTJjIZfrcdOEUOLccp+uJl+gp0eKTwdJc= Authentication-Results: smtp1h.mail.yandex.net; dkim=pass header.i=@yandex.ru Message-ID: <54015C22.5030108@yandex.ru> Date: Sat, 30 Aug 2014 09:07:46 +0400 From: Dmitry Antipov User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.0 MIME-Version: 1.0 To: Paul Eggert Subject: Re: bug#18361: New 'sort' implementation can crash Emacs References: <5400EFA5.6090902@cs.ucla.edu> <540102E5.6040404@yandex.ru> <5401079D.7070505@cs.ucla.edu> In-Reply-To: <5401079D.7070505@cs.ucla.edu> Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Score: 0.0 (/) X-Debbugs-Envelope-To: 18361 Cc: 18361@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: 0.0 (/) On 08/30/2014 03:07 AM, Paul Eggert wrote: > 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. If an undefined behavior doesn't cause crash, I don't see a problem if this is well-documented (probably in lispref). I gave this function a solid run on GNU/Linux (glibc 2.18) and FreeBSD 10.0, and was unable to crash: (defun sort-run () (interactive) (let* ((max 1000000) (size 1000) (p (make-progress-reporter "Sorted: " 0 max))) (dotimes (loops max) (let ((v (make-vector size 0))) (dotimes (i size) (aset v i (% (random) (* size 2)))) (sort v (lambda (x y) (random))) (progress-reporter-update p loops))) (progress-reporter-done p))) I don't have any reasons to not trust in your experience, but I'm really curious to look at the real example crashing qsort(_r) due to ill-formed comparison function. Dmitry From debbugs-submit-bounces@debbugs.gnu.org Sat Aug 30 01:23:04 2014 Received: (at 18361) by debbugs.gnu.org; 30 Aug 2014 05:23:05 +0000 Received: from localhost ([127.0.0.1]:53947 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1XNb7w-0004XR-IA for submit@debbugs.gnu.org; Sat, 30 Aug 2014 01:23:04 -0400 Received: from smtp.cs.ucla.edu ([131.179.128.62]:55147) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1XNb7t-0004Wq-5U for 18361@debbugs.gnu.org; Sat, 30 Aug 2014 01:23:01 -0400 Received: from localhost (localhost.localdomain [127.0.0.1]) by smtp.cs.ucla.edu (Postfix) with ESMTP id E7DFBA60013; Fri, 29 Aug 2014 22:22:54 -0700 (PDT) X-Virus-Scanned: amavisd-new at smtp.cs.ucla.edu 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 eyCFqvtsBXQE; Fri, 29 Aug 2014 22:22:53 -0700 (PDT) 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 BAC15A60002; Fri, 29 Aug 2014 22:22:53 -0700 (PDT) Message-ID: <54015FA8.5070400@cs.ucla.edu> Date: Fri, 29 Aug 2014 22:22:48 -0700 From: Paul Eggert Organization: UCLA Computer Science Department User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.0 MIME-Version: 1.0 To: Dmitry Antipov Subject: Re: bug#18361: New 'sort' implementation can crash Emacs References: <5400EFA5.6090902@cs.ucla.edu> <540102E5.6040404@yandex.ru> <5401079D.7070505@cs.ucla.edu> <54015C22.5030108@yandex.ru> In-Reply-To: <54015C22.5030108@yandex.ru> Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Score: -2.3 (--) X-Debbugs-Envelope-To: 18361 Cc: 18361@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -2.3 (--) Dmitry Antipov wrote: > > If an undefined behavior doesn't cause crash, Unfortunately undefined behavior in qsort can cause a crash (or an infinite loop, etc., etc.). It's platform-dependent, and on many platforms the problem happens only in unusual cases, so I'm not surprised your tests didn't find it. But it definitely can happen. See, for example, https://gcc.gnu.org/bugzilla/show_bug.cgi?id=42157 https://gcc.gnu.org/bugzilla/show_bug.cgi?id=51297 These crash reports are for Solaris qsort, but today I found similar issues in the latest glibc qsort by code inspection (e.g., the path qsort takes when memory is low). These issues are not qsort bugs, since the qsort spec requires a total-order comparison function. It's a bug in the Emacs trunk. From debbugs-submit-bounces@debbugs.gnu.org Sat Aug 30 02:55:31 2014 Received: (at 18361) by debbugs.gnu.org; 30 Aug 2014 06:55:32 +0000 Received: from localhost ([127.0.0.1]:53953 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1XNcZP-0006sH-Et for submit@debbugs.gnu.org; Sat, 30 Aug 2014 02:55:31 -0400 Received: from forward5m.cmail.yandex.net ([5.255.216.23]:56347) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1XNcZL-0006s0-Qc for 18361@debbugs.gnu.org; Sat, 30 Aug 2014 02:55:29 -0400 Received: from smtp9.mail.yandex.net (smtp9.mail.yandex.net [77.88.61.35]) by forward5m.cmail.yandex.net (Yandex) with ESMTP id 70A77804F3; Sat, 30 Aug 2014 10:55:18 +0400 (MSK) Received: from smtp9.mail.yandex.net (localhost [127.0.0.1]) by smtp9.mail.yandex.net (Yandex) with ESMTP id CE97A15200F7; Sat, 30 Aug 2014 10:55:17 +0400 (MSK) Received: from unknown (unknown [37.139.80.10]) by smtp9.mail.yandex.net (nwsmtp/Yandex) with ESMTPSA id ohKxovX1OQ-tHsCV9ag; Sat, 30 Aug 2014 10:55:17 +0400 (using TLSv1.2 with cipher AES128-SHA (128/128 bits)) (Client certificate not present) X-Yandex-Uniq: 9400e389-b04c-46be-9bb5-7f1bc6ca76bd DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=yandex.ru; s=mail; t=1409381717; bh=Z7w34BsjuhjF7Qzo+E8JmyA4Vv5oj/nX05PVksJFxQA=; h=Message-ID:Date:From:User-Agent:MIME-Version:To:CC:Subject: References:In-Reply-To:Content-Type:Content-Transfer-Encoding; b=kHdYYZculv5hwflU9e370GtOkXvIl81We+lATjvSTDW1kNuYaAw5GsUMJiwI1Xi9t zrOrejgEBYlIwz74eWKiESbSG48bfrrUDUH363XbNKXCsMzP/r7LwUE23B4kyZ7hJe mBYTgsMAfPFpGYyY9RiPGcz85sAvelWgNQY4s0+I= Authentication-Results: smtp9.mail.yandex.net; dkim=pass header.i=@yandex.ru Message-ID: <54017555.8010903@yandex.ru> Date: Sat, 30 Aug 2014 10:55:17 +0400 From: Dmitry Antipov User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.0 MIME-Version: 1.0 To: Paul Eggert Subject: Re: bug#18361: New 'sort' implementation can crash Emacs References: <5400EFA5.6090902@cs.ucla.edu> <540102E5.6040404@yandex.ru> <5401079D.7070505@cs.ucla.edu> <54015C22.5030108@yandex.ru> <54015FA8.5070400@cs.ucla.edu> In-Reply-To: <54015FA8.5070400@cs.ucla.edu> Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Score: 0.0 (/) X-Debbugs-Envelope-To: 18361 Cc: 18361@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: 0.0 (/) On 08/30/2014 09:22 AM, Paul Eggert wrote: > See, for example, > > https://gcc.gnu.org/bugzilla/show_bug.cgi?id=42157 > https://gcc.gnu.org/bugzilla/show_bug.cgi?id=51297 Very nice. But couldn't we detect an improper comparison function at runtime? For example: === modified file 'src/fns.c' --- src/fns.c 2014-08-29 19:18:06 +0000 +++ src/fns.c 2014-08-30 06:52:20 +0000 @@ -1933,6 +1933,8 @@ preserve original order. Pretty ugly but works. */ more = NILP (call2 (sort_vector_predicate, vp, vq)); less = NILP (call2 (sort_vector_predicate, vq, vp)); + if (!more && !less) + error ("Not an anti-symmetrical predicate in sort"); return ((more && !less) ? 1 : ((!more && less) ? -1 : XSAVE_INTEGER (op, 0) - XSAVE_INTEGER (oq, 0))); Dmitry From debbugs-submit-bounces@debbugs.gnu.org Sat Aug 30 09:45:07 2014 Received: (at 18361) by debbugs.gnu.org; 30 Aug 2014 13:45:07 +0000 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 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 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 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) 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) Message-ID: <5401D556.4060102@cs.ucla.edu> Date: Sat, 30 Aug 2014 06:44:54 -0700 From: Paul Eggert Organization: UCLA Computer Science Department User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.0 MIME-Version: 1.0 To: Dmitry Antipov Subject: Re: bug#18361: New 'sort' implementation can crash Emacs 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> In-Reply-To: <54017555.8010903@yandex.ru> Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Score: -2.3 (--) X-Debbugs-Envelope-To: 18361 Cc: 18361@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -2.3 (--) 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. From debbugs-submit-bounces@debbugs.gnu.org Sat Aug 30 19:05:22 2014 Received: (at 18361) by debbugs.gnu.org; 30 Aug 2014 23:05:23 +0000 Received: from localhost ([127.0.0.1]:54659 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1XNrhy-0008FQ-9g for submit@debbugs.gnu.org; Sat, 30 Aug 2014 19:05:22 -0400 Received: from smtp.cs.ucla.edu ([131.179.128.62]:53818) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1XNrhu-0008FB-QQ for 18361@debbugs.gnu.org; Sat, 30 Aug 2014 19:05:19 -0400 Received: from localhost (localhost.localdomain [127.0.0.1]) by smtp.cs.ucla.edu (Postfix) with ESMTP id 83D59A60013; Sat, 30 Aug 2014 16:05:12 -0700 (PDT) X-Virus-Scanned: amavisd-new at smtp.cs.ucla.edu 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 Lf1cW7d58IO9; Sat, 30 Aug 2014 16:05:04 -0700 (PDT) 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 E0C27A60002; Sat, 30 Aug 2014 16:05:03 -0700 (PDT) Message-ID: <5402589F.2050801@cs.ucla.edu> Date: Sat, 30 Aug 2014 16:05:03 -0700 From: Paul Eggert Organization: UCLA Computer Science Department User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.0 MIME-Version: 1.0 To: 18361@debbugs.gnu.org Subject: Re: bug#18361: New 'sort' implementation can crash Emacs 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> <5401D556.4060102@cs.ucla.edu> In-Reply-To: <5401D556.4060102@cs.ucla.edu> Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Score: -2.3 (--) X-Debbugs-Envelope-To: 18361 Cc: Dmitry Antipov X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -2.3 (--) I installed what I hope is a fix for this bug as trunk bzr 117784; please give it a look. From debbugs-submit-bounces@debbugs.gnu.org Sat Aug 30 22:51:00 2014 Received: (at 18361) by debbugs.gnu.org; 31 Aug 2014 02:51:00 +0000 Received: from localhost ([127.0.0.1]:54741 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1XNvEK-0005CK-7N for submit@debbugs.gnu.org; Sat, 30 Aug 2014 22:51:00 -0400 Received: from mtaout24.012.net.il ([80.179.55.180]:34319) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1XNvEH-0005C6-08 for 18361@debbugs.gnu.org; Sat, 30 Aug 2014 22:50:58 -0400 Received: from conversion-daemon.mtaout24.012.net.il by mtaout24.012.net.il (HyperSendmail v2007.08) id <0NB500B00GA6YT00@mtaout24.012.net.il> for 18361@debbugs.gnu.org; Sun, 31 Aug 2014 05:46:02 +0300 (IDT) Received: from HOME-C4E4A596F7 ([87.69.4.28]) by mtaout24.012.net.il (HyperSendmail v2007.08) with ESMTPA id <0NB5004T6H0PJS80@mtaout24.012.net.il>; Sun, 31 Aug 2014 05:46:02 +0300 (IDT) Date: Sun, 31 Aug 2014 05:50:53 +0300 From: Eli Zaretskii Subject: Re: bug#18361: New 'sort' implementation can crash Emacs In-reply-to: <5402589F.2050801@cs.ucla.edu> X-012-Sender: halo1@inter.net.il To: Paul Eggert Message-id: <83egvxgynm.fsf@gnu.org> 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> <5401D556.4060102@cs.ucla.edu> <5402589F.2050801@cs.ucla.edu> X-Spam-Score: 1.0 (+) X-Debbugs-Envelope-To: 18361 Cc: dmantipov@yandex.ru, 18361@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 Precedence: list Reply-To: Eli Zaretskii List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: 1.0 (+) > Date: Sat, 30 Aug 2014 16:05:03 -0700 > From: Paul Eggert > Cc: Dmitry Antipov > > I installed what I hope is a fix for this bug as trunk bzr 117784; > please give it a look. Thanks. There's something I don't understand in that changeset: why are we importing the qsort_r module from gnulib, but then don't use anywhere? What am I missing? From debbugs-submit-bounces@debbugs.gnu.org Sun Aug 31 00:46:55 2014 Received: (at 18361) by debbugs.gnu.org; 31 Aug 2014 04:46:55 +0000 Received: from localhost ([127.0.0.1]:54752 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1XNx2T-0007y3-SS for submit@debbugs.gnu.org; Sun, 31 Aug 2014 00:46:54 -0400 Received: from smtp.cs.ucla.edu ([131.179.128.62]:33238) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1XNx2Q-0007xm-Sk for 18361@debbugs.gnu.org; Sun, 31 Aug 2014 00:46:51 -0400 Received: from localhost (localhost.localdomain [127.0.0.1]) by smtp.cs.ucla.edu (Postfix) with ESMTP id 8FEA0A6001A; Sat, 30 Aug 2014 21:46:44 -0700 (PDT) X-Virus-Scanned: amavisd-new at smtp.cs.ucla.edu 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 w56D5dcJHd4B; Sat, 30 Aug 2014 21:46:36 -0700 (PDT) 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 DE48DA60002; Sat, 30 Aug 2014 21:46:35 -0700 (PDT) Message-ID: <5402A8AB.4060801@cs.ucla.edu> Date: Sat, 30 Aug 2014 21:46:35 -0700 From: Paul Eggert Organization: UCLA Computer Science Department User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.0 MIME-Version: 1.0 To: Eli Zaretskii Subject: Re: bug#18361: New 'sort' implementation can crash Emacs 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> <5401D556.4060102@cs.ucla.edu> <5402589F.2050801@cs.ucla.edu> <83egvxgynm.fsf@gnu.org> In-Reply-To: <83egvxgynm.fsf@gnu.org> Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Score: -2.3 (--) X-Debbugs-Envelope-To: 18361 Cc: dmantipov@yandex.ru, 18361@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -2.3 (--) Eli Zaretskii wrote: > why are we importing the qsort_r module from gnulib We're not. Emacs is merely importing gnulib's stdlib module, which now has placeholders (unused by Emacs) for qsort_r, just as it has placeholders for all GNU functions it might define. From debbugs-submit-bounces@debbugs.gnu.org Sun Aug 31 11:20:25 2014 Received: (at 18361) by debbugs.gnu.org; 31 Aug 2014 15:20:25 +0000 Received: from localhost ([127.0.0.1]:55082 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1XO6vZ-00089v-4N for submit@debbugs.gnu.org; Sun, 31 Aug 2014 11:20:25 -0400 Received: from mtaout20.012.net.il ([80.179.55.166]:36657) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1XO6vT-00089d-Ob for 18361@debbugs.gnu.org; Sun, 31 Aug 2014 11:20:21 -0400 Received: from conversion-daemon.a-mtaout20.012.net.il by a-mtaout20.012.net.il (HyperSendmail v2007.08) id <0NB600L00FMUU400@a-mtaout20.012.net.il> for 18361@debbugs.gnu.org; Sun, 31 Aug 2014 18:20:13 +0300 (IDT) Received: from HOME-C4E4A596F7 ([87.69.4.28]) by a-mtaout20.012.net.il (HyperSendmail v2007.08) with ESMTPA id <0NB600LEYFXOO040@a-mtaout20.012.net.il>; Sun, 31 Aug 2014 18:20:13 +0300 (IDT) Date: Sun, 31 Aug 2014 18:20:18 +0300 From: Eli Zaretskii Subject: Re: bug#18361: New 'sort' implementation can crash Emacs In-reply-to: <5402A8AB.4060801@cs.ucla.edu> X-012-Sender: halo1@inter.net.il To: Paul Eggert Message-id: <83d2bghej1.fsf@gnu.org> 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> <5401D556.4060102@cs.ucla.edu> <5402589F.2050801@cs.ucla.edu> <83egvxgynm.fsf@gnu.org> <5402A8AB.4060801@cs.ucla.edu> X-Spam-Score: 1.0 (+) X-Debbugs-Envelope-To: 18361 Cc: dmantipov@yandex.ru, 18361@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 Precedence: list Reply-To: Eli Zaretskii List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: 1.0 (+) > Date: Sat, 30 Aug 2014 21:46:35 -0700 > From: Paul Eggert > CC: 18361@debbugs.gnu.org, dmantipov@yandex.ru > > Eli Zaretskii wrote: > > why are we importing the qsort_r module from gnulib > > We're not. Emacs is merely importing gnulib's stdlib module, which now > has placeholders (unused by Emacs) for qsort_r, just as it has > placeholders for all GNU functions it might define. OK, thanks. I guess what fooled me was this part of the commit message: Sync from gnulib, incorporating: 2014-08-29 qsort_r: new module, for GNU-style qsort_r From debbugs-submit-bounces@debbugs.gnu.org Fri Sep 05 14:35:46 2014 Received: (at control) by debbugs.gnu.org; 5 Sep 2014 18:35:47 +0000 Received: from localhost ([127.0.0.1]:60077 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1XPyMM-0005IH-Dd for submit@debbugs.gnu.org; Fri, 05 Sep 2014 14:35:46 -0400 Received: from smtp.cs.ucla.edu ([131.179.128.62]:57781) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1XPyMJ-0005I3-EE for control@debbugs.gnu.org; Fri, 05 Sep 2014 14:35:44 -0400 Received: from localhost (localhost.localdomain [127.0.0.1]) by smtp.cs.ucla.edu (Postfix) with ESMTP id 5C97439E8014 for ; Fri, 5 Sep 2014 11:35:37 -0700 (PDT) X-Virus-Scanned: amavisd-new at smtp.cs.ucla.edu 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 7T9SQqGe27XQ for ; Fri, 5 Sep 2014 11:35:28 -0700 (PDT) Received: from penguin.cs.ucla.edu (Penguin.CS.UCLA.EDU [131.179.64.200]) by smtp.cs.ucla.edu (Postfix) with ESMTPSA id C5E2139E8011 for ; Fri, 5 Sep 2014 11:35:28 -0700 (PDT) Message-ID: <540A026D.5070006@cs.ucla.edu> Date: Fri, 05 Sep 2014 11:35:25 -0700 From: Paul Eggert Organization: UCLA Computer Science Department User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:24.0) Gecko/20100101 Thunderbird/24.7.0 MIME-Version: 1.0 To: control@debbugs.gnu.org Subject: 18361 is fixed Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Score: -4.0 (----) X-Debbugs-Envelope-To: control X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -4.0 (----) close 18361 thanks It's fixed now. From unknown Sat Sep 13 17:04:03 2025 Received: (at fakecontrol) by fakecontrolmessage; To: internal_control@debbugs.gnu.org From: Debbugs Internal Request Subject: Internal Control Message-Id: bug archived. Date: Sat, 04 Oct 2014 11:24:03 +0000 User-Agent: Fakemail v42.6.9 # This is a fake control message. # # The action: # bug archived. thanks # This fakemail brought to you by your local debbugs # administrator