From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: zacromero@posteo.net Newsgroups: gmane.emacs.bugs Subject: bug#68232: [PATCH] Fix range-intersection implementation Date: Fri, 12 Jan 2024 02:44:29 +0000 Message-ID: References: Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="=_08ad2565fc8fad05b3fcb1a43c055f83" Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="40568"; mail-complaints-to="usenet@ciao.gmane.io" Cc: 68232@debbugs.gnu.org, Lars Magne Ingebrigtsen To: Stefan Kangas Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Fri Jan 12 03:45:35 2024 Return-path: Envelope-to: geb-bug-gnu-emacs@m.gmane-mx.org Original-Received: from lists.gnu.org ([209.51.188.17]) by ciao.gmane.io with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1rO7Y7-000AOj-5H for geb-bug-gnu-emacs@m.gmane-mx.org; Fri, 12 Jan 2024 03:45:35 +0100 Original-Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1rO7Xi-0006FM-Q8; Thu, 11 Jan 2024 21:45:10 -0500 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1rO7Xf-0006F3-49 for bug-gnu-emacs@gnu.org; Thu, 11 Jan 2024 21:45:07 -0500 Original-Received: from debbugs.gnu.org ([2001:470:142:5::43]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1rO7Xd-0007bA-Df for bug-gnu-emacs@gnu.org; Thu, 11 Jan 2024 21:45:06 -0500 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1rO7Xa-0001MX-EO for bug-gnu-emacs@gnu.org; Thu, 11 Jan 2024 21:45:02 -0500 X-Loop: help-debbugs@gnu.org Resent-From: zacromero@posteo.net Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Fri, 12 Jan 2024 02:45:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 68232 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: patch Original-Received: via spool by 68232-submit@debbugs.gnu.org id=B68232.17050274795186 (code B ref 68232); Fri, 12 Jan 2024 02:45:02 +0000 Original-Received: (at 68232) by debbugs.gnu.org; 12 Jan 2024 02:44:39 +0000 Original-Received: from localhost ([127.0.0.1]:34476 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1rO7XD-0001La-Ai for submit@debbugs.gnu.org; Thu, 11 Jan 2024 21:44:39 -0500 Original-Received: from mout02.posteo.de ([185.67.36.66]:55693) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1rO7X8-0001LD-Az for 68232@debbugs.gnu.org; Thu, 11 Jan 2024 21:44:38 -0500 Original-Received: from submission (posteo.de [185.67.36.169]) by mout02.posteo.de (Postfix) with ESMTPS id 35079240101 for <68232@debbugs.gnu.org>; Fri, 12 Jan 2024 03:44:30 +0100 (CET) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=posteo.net; s=2017; t=1705027470; bh=mXiiMldm8LGCBYIQdBDjxVm3VQJcQKwKd/ZnV/UTK28=; h=MIME-Version:Date:From:To:Cc:Subject:Message-ID:From; b=HbQCFIJlmjNNNCytiKX0ArqHJe7/5GMGpJ3ZpBGHVyR8efdFyp6FXF/525V7L/j9W z1qEPKXRpW/H9sgPABU/qqh6arYXniNAz/iwimTfbe+2U8ZI9Ejz+7qoFjVXQuUznT uzkqhf6S+KT+IWbmivHPBrNt4N+au7BGlbuqv0Y6muoAukaZpy541PM0PCzttkSnw5 eecIaYh0cDNr0toGjVtgXBdAz6BHMEeBCIn8wmFXOx/D5QsB3KX6nyasno+lNHtIhf CQq0I/rh+Tw+FlY0K8noMEAkINQ8vqeEZkI45/K+pkQ8o5PkFA7RxwfVjwigZD/Vuw bmH+bu6nv6DiQ== Original-Received: from customer (localhost [127.0.0.1]) by submission (posteo.de) with ESMTPSA id 4TB5Tn3qPKz9rxB; Fri, 12 Jan 2024 03:44:29 +0100 (CET) In-Reply-To: X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list 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-mx.org@gnu.org Original-Sender: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Xref: news.gmane.io gmane.emacs.bugs:277978 Archived-At: --=_08ad2565fc8fad05b3fcb1a43c055f83 Content-Transfer-Encoding: 7bit Content-Type: text/plain; charset=US-ASCII; format=flowed Thanks for pointing me to the tests. Attached is an updated patch with the added test cases and the range tests all pass. On 11.01.2024 21:56, Stefan Kangas wrote: > Zachary Romero writes: > >> Hello Emacs maintainers, >> >> I was using the range package when I encountered a bug in the >> implementation of range-intersection. The bug seems to occur when the >> ranges involve a mix of integers and cons pairs. The following are >> some >> cases where the current implementation fails to compute the correct >> intersection: >> >> (range-intersection '((1 . 10) 11) '((11 . 12))) >> ;; Expects (11), returns nil >> >> (range-intersection '(11 (13 . 15)) '((13 . 15))) >> ;; Expects (13 . 15), returns nil >> >> (range-intersection '(1 11 13 15) '((1 . 2) (10 . 20))) >> ;; Expects (1 11 13 15), returns (1) >> >> >> I also refactored this function using pcase to try to make the steps >> of >> the algorithm more understandable. >> >> Let me know you thoughts and if there's any further changes I should >> make. > > Thanks for the patch. Could you please add tests for this as well? > See the file range-tests.el. > > Did you check that the existing tests all still pass? --=_08ad2565fc8fad05b3fcb1a43c055f83 Content-Transfer-Encoding: base64 Content-Type: application/octet-stream; name=0001-fix-range-intersection-edge-cases.patch Content-Disposition: attachment; filename=0001-fix-range-intersection-edge-cases.patch; size=5286 RnJvbSAxYmVlY2QxMjk2ZmYyNTJiNDFkZjEyZDdjNjhkZmI5MWI1MDM0MWYyIE1vbiBTZXAgMTcg MDA6MDA6MDAgMjAwMQpGcm9tOiBaYWNoYXJ5IFJvbWVybyA8emFjcm9tZXJvQHBvc3Rlby5uZXQ+ CkRhdGU6IFRodSwgMTEgSmFuIDIwMjQgMTk6MzY6MzYgLTA3MDAKU3ViamVjdDogW1BBVENIXSBm aXggcmFuZ2UgaW50ZXJzZWN0aW9uIGVkZ2UgY2FzZXMKCi0tLQogbGlzcC9lbWFjcy1saXNwL3Jh bmdlLmVsICAgICAgICAgICAgfCA4MSArKysrKysrKysrKysrKy0tLS0tLS0tLS0tLS0tLQogdGVz dC9saXNwL2VtYWNzLWxpc3AvcmFuZ2UtdGVzdHMuZWwgfCAxNCArKysrKwogMiBmaWxlcyBjaGFu Z2VkLCA1MiBpbnNlcnRpb25zKCspLCA0MyBkZWxldGlvbnMoLSkKCmRpZmYgLS1naXQgYS9saXNw L2VtYWNzLWxpc3AvcmFuZ2UuZWwgYi9saXNwL2VtYWNzLWxpc3AvcmFuZ2UuZWwKaW5kZXggMTlh NmRhMzRhY2IuLmYyNzY0OTE0NmQ2IDEwMDY0NAotLS0gYS9saXNwL2VtYWNzLWxpc3AvcmFuZ2Uu ZWwKKysrIGIvbGlzcC9lbWFjcy1saXNwL3JhbmdlLmVsCkBAIC04OSw0OSArODksNDQgQEAgcmFu Z2UtZGlmZmVyZW5jZQogCiAoZGVmdW4gcmFuZ2UtaW50ZXJzZWN0aW9uIChyYW5nZTEgcmFuZ2Uy KQogICAiUmV0dXJuIGludGVyc2VjdGlvbiBvZiBSQU5HRTEgYW5kIFJBTkdFMi4iCi0gIChsZXQq IChvdXQKLSAgICAgICAgIChtaW4xIChjYXIgcmFuZ2UxKSkKLSAgICAgICAgIChtYXgxIChpZiAo bnVtYmVycCBtaW4xKQotICAgICAgICAgICAgICAgICAgIChpZiAobnVtYmVycCAoY2RyIHJhbmdl MSkpCi0gICAgICAgICAgICAgICAgICAgICAgIChwcm9nMSAoY2RyIHJhbmdlMSkKLSAgICAgICAg ICAgICAgICAgICAgICAgICAoc2V0cSByYW5nZTEgbmlsKSkgbWluMSkKLSAgICAgICAgICAgICAg ICAgKHByb2cxIChjZHIgbWluMSkKLSAgICAgICAgICAgICAgICAgICAoc2V0cSBtaW4xIChjYXIg bWluMSkpKSkpCi0gICAgICAgICAobWluMiAoY2FyIHJhbmdlMikpCi0gICAgICAgICAobWF4MiAo aWYgKG51bWJlcnAgbWluMikKLSAgICAgICAgICAgICAgICAgICAoaWYgKG51bWJlcnAgKGNkciBy YW5nZTIpKQotICAgICAgICAgICAgICAgICAgICAgICAocHJvZzEgKGNkciByYW5nZTIpCi0gICAg ICAgICAgICAgICAgICAgICAgICAgKHNldHEgcmFuZ2UyIG5pbCkpIG1pbjIpCi0gICAgICAgICAg ICAgICAgIChwcm9nMSAoY2RyIG1pbjIpCi0gICAgICAgICAgICAgICAgICAgKHNldHEgbWluMiAo Y2FyIG1pbjIpKSkpKSkKLSAgICAoc2V0cSByYW5nZTEgKGNkciByYW5nZTEpCi0gICAgICAgICAg cmFuZ2UyIChjZHIgcmFuZ2UyKSkKLSAgICAod2hpbGUgKGFuZCBtaW4xIG1pbjIpCi0gICAgICAo Y29uZCAoKDwgbWF4MSBtaW4yKSAgICAgICAgICAgICAgOyByYW5nZTEgcHJlY2VkZXMgcmFuZ2Uy Ci0gICAgICAgICAgICAgKHNldHEgcmFuZ2UxIChjZHIgcmFuZ2UxKQotICAgICAgICAgICAgICAg ICAgIG1pbjEgbmlsKSkKLSAgICAgICAgICAgICgoPCBtYXgyIG1pbjEpICAgICAgICAgICAgICA7 IHJhbmdlMiBwcmVjZWRlcyByYW5nZTEKLSAgICAgICAgICAgICAoc2V0cSByYW5nZTIgKGNkciBy YW5nZTIpCi0gICAgICAgICAgICAgICAgICAgbWluMiBuaWwpKQotICAgICAgICAgICAgKHQgICAg ICAgICAgICAgICAgICAgICA7IHNvbWUgc29ydCBvZiBvdmVybGFwIGlzIG9jY3VycmluZwotICAg ICAgICAgICAgIChsZXQgKChtaW4gKG1heCBtaW4xIG1pbjIpKQotICAgICAgICAgICAgICAgICAg IChtYXggKG1pbiBtYXgxIG1heDIpKSkKLSAgICAgICAgICAgICAgIChzZXRxIG91dCAoaWYgKD0g bWluIG1heCkKLSAgICAgICAgICAgICAgICAgICAgICAgICAgICAgKGNvbnMgbWluIG91dCkKLSAg ICAgICAgICAgICAgICAgICAgICAgICAgIChjb25zIChjb25zIG1pbiBtYXgpIG91dCkpKSkKLSAg ICAgICAgICAgICAoaWYgKDwgbWF4MSBtYXgyKSAgICAgICAgICA7IHJhbmdlMSBlbmRzIGJlZm9y ZSByYW5nZTIKLSAgICAgICAgICAgICAgICAgKHNldHEgbWluMSBuaWwpICAgICAgICA7IGluY3Ig cmFuZ2UxCi0gICAgICAgICAgICAgICAoc2V0cSBtaW4yIG5pbCkpKSkgICAgICAgOyBpbmNyIHJh bmdlMgotICAgICAgKHVubGVzcyBtaW4xCi0gICAgICAgIChzZXRxIG1pbjEgKGNhciByYW5nZTEp Ci0gICAgICAgICAgICAgIG1heDEgKGlmIChudW1iZXJwIG1pbjEpIG1pbjEKLSAgICAgICAgICAg ICAgICAgICAgIChwcm9nMSAoY2RyIG1pbjEpIChzZXRxIG1pbjEgKGNhciBtaW4xKSkpKQotICAg ICAgICAgICAgICByYW5nZTEgKGNkciByYW5nZTEpKSkKLSAgICAgICh1bmxlc3MgbWluMgotICAg ICAgICAoc2V0cSBtaW4yIChjYXIgcmFuZ2UyKQotICAgICAgICAgICAgICBtYXgyIChpZiAobnVt YmVycCBtaW4yKSBtaW4yCi0gICAgICAgICAgICAgICAgICAgICAocHJvZzEgKGNkciBtaW4yKSAo c2V0cSBtaW4yIChjYXIgbWluMikpKSkKLSAgICAgICAgICAgICAgcmFuZ2UyIChjZHIgcmFuZ2Uy KSkpKQorICAobGV0ICgob3V0KSkKKyAgICAod2hpbGUgKGFuZCByYW5nZTEgcmFuZ2UyKQorICAg ICAgKGxldCogKChlbHQxIChjYXIgcmFuZ2UxKSkKKyAgICAgICAgICAgICAoZWx0MiAoY2FyIHJh bmdlMikpKQorICAgICAgICAocGNhc2UgKGxpc3QgZWx0MSBlbHQyKQorICAgICAgICAgIChgKCgs bWluMSAuICxtYXgxKSAoLG1pbjIgLiAsbWF4MikpCisgICAgICAgICAgIChsZXQgKChtaW4gKG1h eCBtaW4xIG1pbjIpKQorICAgICAgICAgICAgICAgICAobWF4IChtaW4gbWF4MSBtYXgyKSkpCisg ICAgICAgICAgICAgKGNvbmQKKyAgICAgICAgICAgICAgKCg8IG1pbiBtYXgpCisgICAgICAgICAg ICAgICAoc2V0cSBvdXQgKGNvbnMgKGNvbnMgbWluIG1heCkgb3V0KSkpCisgICAgICAgICAgICAg ICgoPSBtaW4gbWF4KQorICAgICAgICAgICAgICAgKHNldHEgb3V0IChjb25zIG1pbiBvdXQpKSkp CisgICAgICAgICAgICAgKGlmICg8IG1heDEgbWF4MikKKyAgICAgICAgICAgICAgICAgKHNldHEg cmFuZ2UxIChjZHIgcmFuZ2UxKSkKKyAgICAgICAgICAgICAgIChzZXRxIHJhbmdlMiAoY2RyIHJh bmdlMikpKSkpCisgICAgICAgICAgKChhbmQgYCgsbnVtMSAoLG1pbjIgLiAsbWF4MikpCisgICAg ICAgICAgICAgICAgKGd1YXJkIChudW1iZXJwIG51bTEpKSkKKyAgICAgICAgICAgKHdoZW4gKDw9 IG1pbjIgbnVtMSBtYXgyKQorICAgICAgICAgICAgIChzZXRxIG91dCAoY29ucyBudW0xIG91dCkp KQorICAgICAgICAgICAoaWYgKDwgbWF4MiBudW0xKQorICAgICAgICAgICAgICAgKHNldHEgcmFu Z2UyIChjZHIgcmFuZ2UyKSkKKyAgICAgICAgICAgICAoc2V0cSByYW5nZTEgKGNkciByYW5nZTEp KSkpCisgICAgICAgICAgKChhbmQgYCgoLG1pbjEgLiAsbWF4MSkgLG51bTIpCisgICAgICAgICAg ICAgICAgKGd1YXJkIChudW1iZXJwIG51bTIpKSkKKyAgICAgICAgICAgKHdoZW4gKDw9IG1pbjEg bnVtMiBtYXgxKQorICAgICAgICAgICAgIChzZXRxIG91dCAoY29ucyBudW0yIG91dCkpKQorICAg ICAgICAgICAoaWYgKDwgbWF4MSBudW0yKQorICAgICAgICAgICAgICAgKHNldHEgcmFuZ2UxIChj ZHIgcmFuZ2UxKSkKKyAgICAgICAgICAgICAoc2V0cSByYW5nZTIgKGNkciByYW5nZTIpKSkpCisg ICAgICAgICAgKChhbmQgYCgsbnVtMSAsbnVtMikKKyAgICAgICAgICAgICAgICAoZ3VhcmQgKGFu ZCAobnVtYmVycCBudW0xKQorICAgICAgICAgICAgICAgICAgICAgICAgICAgIChudW1iZXJwIG51 bTIpKSkpCisgICAgICAgICAgICh3aGVuICg9IG51bTEgbnVtMikKKyAgICAgICAgICAgICAoc2V0 cSBvdXQgKGNvbnMgbnVtMSBvdXQpKSkKKyAgICAgICAgICAgKGlmICg8IG51bTEgbnVtMikKKyAg ICAgICAgICAgICAgIChzZXRxIHJhbmdlMSAoY2RyIHJhbmdlMSkpCisgICAgICAgICAgICAgKHNl dHEgcmFuZ2UyIChjZHIgcmFuZ2UyKSkpKSkpKQogICAgIChjb25kICgoY2RyIG91dCkKICAgICAg ICAgICAgKG5yZXZlcnNlIG91dCkpCiAgICAgICAgICAgKChudW1iZXJwIChjYXIgb3V0KSkKZGlm ZiAtLWdpdCBhL3Rlc3QvbGlzcC9lbWFjcy1saXNwL3JhbmdlLXRlc3RzLmVsIGIvdGVzdC9saXNw L2VtYWNzLWxpc3AvcmFuZ2UtdGVzdHMuZWwKaW5kZXggYzY4MGFiNWE5Y2QuLmRiZmNlMGQ4ZGRm IDEwMDY0NAotLS0gYS90ZXN0L2xpc3AvZW1hY3MtbGlzcC9yYW5nZS10ZXN0cy5lbAorKysgYi90 ZXN0L2xpc3AvZW1hY3MtbGlzcC9yYW5nZS10ZXN0cy5lbApAQCAtNDAsNiArNDAsMjAgQEAgcmFu Z2VzCiAgIChzaG91bGQgKGVxdWFsIChyYW5nZS1pbnRlcnNlY3Rpb24gJygoMiAuIDUpIDkgKDEx IC4gMTMpKQogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICcoKDUgLiAxMikp KQogICAgICAgICAgICAgICAgICAnKDUgOSAoMTEgLiAxMikpKSkKKyAgKHNob3VsZCAoZXF1YWwg KHJhbmdlLWludGVyc2VjdGlvbiAnKDEgMTEgMTMgMTUpCisgICAgICAgICAgICAgICAgICAgICAg ICAgICAgICAgICAgICAgJygoMSAuIDIpICgxMCAuIDIwKSkpCisgICAgICAgICAgICAgICAgICco MSAxMSAxMyAxNSkpKQorICAoc2hvdWxkIChlcXVhbCAocmFuZ2UtaW50ZXJzZWN0aW9uICcoMTEg KDEzIC4gMTUpKQorICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICcoKDEzIC4g MTUpKSkKKyAgICAgICAgICAgICAgICAgJygxMyAuIDE1KSkpCisgIChzaG91bGQgKGVxdWFsIChy YW5nZS1pbnRlcnNlY3Rpb24gJygoMSAuIDEwKSAxMSkgJygoMTEgLiAxMikpKQorICAgICAgICAg ICAgICAgICAnKDExKSkpCisgIChzaG91bGQgKGVxdWFsIChyYW5nZS1pbnRlcnNlY3Rpb24gJygo MiAuIDUpIDkgKDExIC4gMTMpKQorICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAg ICcoKDIgLiAxMykpKQorICAgICAgICAgICAgICAgICAnKCgyIC4gNSkgOSAoMTEgLiAxMykpKSkK KyAgKHNob3VsZCAoZXF1YWwgKHJhbmdlLWludGVyc2VjdGlvbiAnKCgxMSAuIDEzKSkKKyAgICAg ICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAnKCgyIC4gMTApKSkKKyAgICAgICAgICAg ICAgICAgbmlsKSkKICAgKHNob3VsZCAoZXF1YWwgKHJhbmdlLWFkZC1saXN0ICcoKDIgLiA1KSA5 ICgxMSAuIDEzKSkKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICcoMTAgMTEgMTIg MTUgMTYgMTcpKQogICAgICAgICAgICAgICAgICAnKCgyIC4gNSkgKDkgLiAxMCkgKDExIC4gMTMp ICgxNSAuIDE3KSkpKQotLSAKMi4zNy4wIChBcHBsZSBHaXQtMTM2KQoK --=_08ad2565fc8fad05b3fcb1a43c055f83--