Received: (at 68232) by debbugs.gnu.org; 12 Jan 2024 02:44:39 +0000 From debbugs-submit-bounces <at> debbugs.gnu.org Thu Jan 11 21:44:39 2024 Received: from localhost ([127.0.0.1]:34476 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>) id 1rO7XD-0001La-Ai for submit <at> debbugs.gnu.org; Thu, 11 Jan 2024 21:44:39 -0500 Received: from mout02.posteo.de ([185.67.36.66]:55693) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from <zacromero@HIDDEN>) id 1rO7X8-0001LD-Az for 68232 <at> debbugs.gnu.org; Thu, 11 Jan 2024 21:44:38 -0500 Received: from submission (posteo.de [185.67.36.169]) by mout02.posteo.de (Postfix) with ESMTPS id 35079240101 for <68232 <at> 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== 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) MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="=_08ad2565fc8fad05b3fcb1a43c055f83" Date: Fri, 12 Jan 2024 02:44:29 +0000 From: zacromero@HIDDEN To: Stefan Kangas <stefankangas@HIDDEN> Subject: Re: bug#68232: [PATCH] Fix range-intersection implementation In-Reply-To: <CADwFkmkviGnBEb2WJD9tnQLFQfnECZA_EYJebLH+FmH1qGR2mg@HIDDEN> References: <m2le97drf3.fsf@HIDDEN> <CADwFkmkviGnBEb2WJD9tnQLFQfnECZA_EYJebLH+FmH1qGR2mg@HIDDEN> Message-ID: <b8439c43400c963a433f8ed03d2a8bee@HIDDEN> X-Spam-Score: -2.3 (--) X-Debbugs-Envelope-To: 68232 Cc: 68232 <at> debbugs.gnu.org, Lars Magne Ingebrigtsen <larsi@HIDDEN> X-BeenThere: debbugs-submit <at> debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: <debbugs-submit.debbugs.gnu.org> List-Unsubscribe: <https://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>, <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe> List-Archive: <https://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit/> List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org> List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help> List-Subscribe: <https://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>, <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe> Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org> X-Spam-Score: -3.3 (---) --=_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 <zacromero@HIDDEN> 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--
bug-gnu-emacs@HIDDEN:bug#68232; Package emacs.
Full text available.Received: (at 68232) by debbugs.gnu.org; 11 Jan 2024 20:56:20 +0000 From debbugs-submit-bounces <at> debbugs.gnu.org Thu Jan 11 15:56:20 2024 Received: from localhost ([127.0.0.1]:34106 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>) id 1rO267-0005sn-RO for submit <at> debbugs.gnu.org; Thu, 11 Jan 2024 15:56:20 -0500 Received: from mail-lj1-x236.google.com ([2a00:1450:4864:20::236]:44096) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from <stefankangas@HIDDEN>) id 1rO265-0005sY-Bq for 68232 <at> debbugs.gnu.org; Thu, 11 Jan 2024 15:56:18 -0500 Received: by mail-lj1-x236.google.com with SMTP id 38308e7fff4ca-2cd0f4797aaso63465711fa.0 for <68232 <at> debbugs.gnu.org>; Thu, 11 Jan 2024 12:56:19 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1705006573; x=1705611373; darn=debbugs.gnu.org; h=cc:to:subject:message-id:date:mime-version:references:in-reply-to :from:from:to:cc:subject:date:message-id:reply-to; bh=vEmvE34AkUWWHaXXG/pZq1ZMEJ7rOWV++06CRAnp3ls=; b=Lq6E46WepbL8JZvYiGoB59mTkMudIi79kSNcTJkxWPewB7GYcpL6wx46rI7QzsqLkQ XxkSqTDCbA5oZBAQtzqRfoS8uQs3sShoTQ6GWvnmp3d/AHUbKbIkP7JBuGAnxKMvpgSn 0PtHOyeoNagfUrYBEKYr9CC2EMUBctCVdHYLAHH5tRQRUj1HnmCdoLj92sFWe4cyZfjw b6LlP7yvl2jF36O917PfEX41+6rnp08MFbg8QA/UuVGCn3FG3zSO+5hdRANSa3nTnAwI kFx/LDu+6ZKbF6mJIsp/wDbPKDcq7GF/SDPP0LdRpABtZZbDRJqgcuvYNTSSdJ64T+F+ CyVQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1705006573; x=1705611373; h=cc:to:subject:message-id:date:mime-version:references:in-reply-to :from:x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=vEmvE34AkUWWHaXXG/pZq1ZMEJ7rOWV++06CRAnp3ls=; b=dbQDADbTVjkml8pSb23uFAdxFjWUVaQv6+/Tj5xFMk/bvx6Q+qKrhGwJDB+IzJw9eC q91lb63NJr+vbUCxShTyeAR3BGyFXPgnZfxJL17sHK8PKmWgPB6tHKMj9V1i2hamZuOx aRMrxpPcXEIvDm3jzuAp+xGMQ1HVj3TijEULWMAINsOyBFG2SrHvyeaFInasmH0daZ1l yMx5StNnsPWs9JLW7fhVtrSbFQoDwvnohW+gpGsS/lwXCP4d5lJEXBSQb4sY9YCHkTin QrNWYAl/scq+Cxnp5Ojv43wrahZRBNJgE2luLtWD15jbD8PcCKuY2fHdU7fCrvBCfRp6 CT+g== X-Gm-Message-State: AOJu0YwT2aWOJNpehOqeYwrWDFMZisYlutBhdXL74gRvuqRwT3d3ohIj oNQgwKfTFrOhbtONg7BOtV97kHkKVOLL9fQq93w= X-Google-Smtp-Source: AGHT+IHrFvcCNqJuQKLtD67F3ApjEa0gldEx5Q1XR9BaPj81V6ZmNACBNPICalPFHLRDc9jR23ht8aGDwYaxfKGvG7U= X-Received: by 2002:a2e:9b0b:0:b0:2cd:5cfd:b19 with SMTP id u11-20020a2e9b0b000000b002cd5cfd0b19mr169888lji.19.1705006573370; Thu, 11 Jan 2024 12:56:13 -0800 (PST) Received: from 753933720722 named unknown by gmailapi.google.com with HTTPREST; Thu, 11 Jan 2024 12:56:13 -0800 From: Stefan Kangas <stefankangas@HIDDEN> In-Reply-To: <m2le97drf3.fsf@HIDDEN> (Zachary Romero's message of "Wed, 03 Jan 2024 03:30:56 +0000") References: <m2le97drf3.fsf@HIDDEN> MIME-Version: 1.0 Date: Thu, 11 Jan 2024 12:56:13 -0800 Message-ID: <CADwFkmkviGnBEb2WJD9tnQLFQfnECZA_EYJebLH+FmH1qGR2mg@HIDDEN> Subject: Re: bug#68232: [PATCH] Fix range-intersection implementation To: Zachary Romero <zacromero@HIDDEN> Content-Type: text/plain; charset="UTF-8" X-Spam-Score: -0.0 (/) X-Debbugs-Envelope-To: 68232 Cc: 68232 <at> debbugs.gnu.org, Lars Magne Ingebrigtsen <larsi@HIDDEN> X-BeenThere: debbugs-submit <at> debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: <debbugs-submit.debbugs.gnu.org> List-Unsubscribe: <https://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>, <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe> List-Archive: <https://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit/> List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org> List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help> List-Subscribe: <https://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>, <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe> Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org> X-Spam-Score: -1.0 (-) Zachary Romero <zacromero@HIDDEN> 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?
bug-gnu-emacs@HIDDEN:bug#68232; Package emacs.
Full text available.
Received: (at submit) by debbugs.gnu.org; 3 Jan 2024 17:39:00 +0000
From debbugs-submit-bounces <at> debbugs.gnu.org Wed Jan 03 12:39:00 2024
Received: from localhost ([127.0.0.1]:53144 helo=debbugs.gnu.org)
by debbugs.gnu.org with esmtp (Exim 4.84_2)
(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
id 1rL5Cl-0004DW-AA
for submit <at> debbugs.gnu.org; Wed, 03 Jan 2024 12:39:00 -0500
Received: from lists.gnu.org ([2001:470:142::17]:35910)
by debbugs.gnu.org with esmtp (Exim 4.84_2)
(envelope-from <zacromero@HIDDEN>) id 1rKryP-0004dt-Jo
for submit <at> debbugs.gnu.org; Tue, 02 Jan 2024 22:31:21 -0500
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 <zacromero@HIDDEN>)
id 1rKryH-00050X-2H
for bug-gnu-emacs@HIDDEN; Tue, 02 Jan 2024 22:31:09 -0500
Received: from mout02.posteo.de ([185.67.36.66])
by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256)
(Exim 4.90_1) (envelope-from <zacromero@HIDDEN>)
id 1rKryE-0004TN-18
for bug-gnu-emacs@HIDDEN; Tue, 02 Jan 2024 22:31:08 -0500
Received: from submission (posteo.de [185.67.36.169])
by mout02.posteo.de (Postfix) with ESMTPS id 88C26240101
for <bug-gnu-emacs@HIDDEN>; Wed, 3 Jan 2024 04:31:02 +0100 (CET)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=posteo.net; s=2017;
t=1704252662; bh=URUJ/hJY9xeHdQWUphbHRSY4YDbK5mTKIbCszxhBCQg=;
h=From:To:Subject:Date:Message-ID:MIME-Version:From;
b=oumHh2U+6OxTUWXZ8dt+3d78OWQQaLbclLuWliTA2z+TLe6+dUnpg2I9JwBZWaQI4
/6+JcnQNSm552CMFaTsLeAK6+urfdsNF+cTXB+3oVpEqOnGbJHAHkKf2HYLP5117N0
h0MKv//ZQbuV5PtSroNGM+8cWZ9u+91uFn3YTTEHWJSHMXlaGxMLJtwSi8vHVs/PZD
2BxKK/j0L3C4tsjNAFiHKhnpdauSsyTA1rXOr3M5sc3s7iiVqaFBg4KEpI7TR8BRi1
EOxlaBP+S2chIEpiAvwLR6ObS8Iyms67lSZKZIV/UKG04t0ViO4cxuvOF8VXKnks0+
QfO8QNk9INcwA==
Received: from customer (localhost [127.0.0.1])
by submission (posteo.de) with ESMTPSA id 4T4Zxd1k9Cz6txF
for <bug-gnu-emacs@HIDDEN>; Wed, 3 Jan 2024 04:31:00 +0100 (CET)
From: Zachary Romero <zacromero@HIDDEN>
To: bug-gnu-emacs@HIDDEN
Subject: [PATCH] Fix range-intersection implementation
Date: Wed, 03 Jan 2024 03:30:56 +0000
Message-ID: <m2le97drf3.fsf@HIDDEN>
MIME-Version: 1.0
Content-Type: multipart/mixed; boundary="=-=-="
Received-SPF: pass client-ip=185.67.36.66; envelope-from=zacromero@HIDDEN;
helo=mout02.posteo.de
X-Spam_score_int: -43
X-Spam_score: -4.4
X-Spam_bar: ----
X-Spam_report: (-4.4 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1,
DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1,
RCVD_IN_DNSWL_MED=-2.3, RCVD_IN_MSPIKE_H5=0.001, RCVD_IN_MSPIKE_WL=0.001,
SPF_HELO_NONE=0.001, SPF_PASS=-0.001,
T_SCC_BODY_TEXT_LINE=-0.01 autolearn=ham autolearn_force=no
X-Spam_action: no action
X-Spam-Score: 1.0 (+)
X-Debbugs-Envelope-To: submit
X-Mailman-Approved-At: Wed, 03 Jan 2024 12:38:54 -0500
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.18
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <https://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>,
<mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <https://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit/>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <https://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>,
<mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
X-Spam-Score: -0.0 (/)
--=-=-=
Content-Type: text/plain
Tags: patch
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.
In GNU Emacs 29.0.90 (build 1, x86_64-apple-darwin21.6.0, NS
appkit-2113.60 Version 12.6 (Build 21G115)) of 2023-04-26 built on
MacBook-Pro.local
Windowing system distributor 'Apple', version 10.3.2113
System Description: macOS 12.6
Configured using:
'configure --disable-dependency-tracking --disable-silent-rules
--enable-locallisppath=/usr/local/share/emacs/site-lisp
--infodir=/usr/local/Cellar/emacs-plus@29/29.0.60/share/info/emacs
--prefix=/usr/local/Cellar/emacs-plus@29/29.0.60 --with-xml2
--with-gnutls --with-native-compilation --without-compress-install
--with-dbus --without-imagemagick --with-modules --with-rsvg
--with-xwidgets --with-ns --disable-ns-self-contained 'CFLAGS=-Os -w
-pipe -march=nehalem -mmacosx-version-min=12
-isysroot/Library/Developer/CommandLineTools/SDKs/MacOSX12.sdk
-DFD_SETSIZE=10000 -DDARWIN_UNLIMITED_SELECT'
'CPPFLAGS=-I/usr/local/opt/zlib/include -I/usr/local/opt/jpeg/include
-I/usr/local/opt/icu4c/include -I/usr/local/opt/openssl@HIDDEN/include
-F/usr/local/Frameworks
-isysroot/Library/Developer/CommandLineTools/SDKs/MacOSX12.sdk'
'LDFLAGS=-L/usr/local/opt/zlib/lib -L/usr/local/opt/jpeg/lib
-L/usr/local/opt/icu4c/lib -L/usr/local/opt/openssl@HIDDEN/lib
-L/usr/local/lib -F/usr/local/Frameworks
-Wl,-headerpad_max_install_names
-isysroot/Library/Developer/CommandLineTools/SDKs/MacOSX12.sdk''
--=-=-=
Content-Type: text/patch
Content-Disposition: attachment;
filename=0001-Fix-range-intersection-implementation.patch
From b26e822e815c97686e9b7c5e712332eef78ba039 Mon Sep 17 00:00:00 2001
From: Zachary Romero <zacromero@HIDDEN>
Date: Tue, 12 Dec 2023 21:33:18 -0700
Subject: [PATCH] Fix range-intersection implementation
---
lisp/emacs-lisp/range.el | 81 +++++++++++++++++++---------------------
1 file changed, 38 insertions(+), 43 deletions(-)
diff --git a/lisp/emacs-lisp/range.el b/lisp/emacs-lisp/range.el
index f441c240a27..f30a1638ab1 100644
--- a/lisp/emacs-lisp/range.el
+++ b/lisp/emacs-lisp/range.el
@@ -89,50 +89,44 @@ range-difference
(defun range-intersection (range1 range2)
"Return intersection of RANGE1 and RANGE2."
- (let* (out
- (min1 (car range1))
- (max1 (if (numberp min1)
- (if (numberp (cdr range1))q
- (prog1 (cdr range1)
- (setq range1 nil)) min1)
- (prog1 (cdr min1)
- (setq min1 (car min1)))))
- (min2 (car range2))
- (max2 (if (numberp min2)
- (if (numberp (cdr range2))
- (prog1 (cdr range2)
- (setq range2 nil)) min2)
- (prog1 (cdr min2)
- (setq min2 (car min2))))))
- (setq range1 (cdr range1)
- range2 (cdr range2))
- (while (and min1 min2)
- (cond ((< max1 min2) ; range1 precedes range2
- (setq range1 (cdr range1)
- min1 nil))
- ((< max2 min1) ; range2 precedes range1
- (setq range2 (cdr range2)
- min2 nil))
- (t ; some sort of overlap is occurring
- (let ((min (max min1 min2))
- (max (min max1 max2)))
- (setq out (if (= min max)
- (cons min out)
- (cons (cons min max) out))))
- (if (< max1 max2) ; range1 ends before range2
- (setq min1 nil) ; incr range1
- (setq min2 nil)))) ; incr range2
- (unless min1
- (setq min1 (car range1)
- max1 (if (numberp min1) min1
- (prog1 (cdr min1) (setq min1 (car min1))))
- range1 (cdr range1)))
- (unless min2
- (setq min2 (car range2)
- max2 (if (numberp min2) min2
- (prog1 (cdr min2) (setq min2 (car min2))))
- range2 (cdr range2))))
+ (let ((out))
+ (while (and range1 range2)
+ (let* ((elt1 (car range1))
+ (elt2 (car range2)))
+ (pcase (list elt1 elt2)
+ (`((,min1 . ,max1) (,min2 . ,max2))
+ (let ((min (max min1 min2))
+ (max (min max1 max2)))
+ (cond
+ ((< min max)
+ (setq out (cons (cons min max) out)))
+ ((= min max)
+ (setq out (cons min out))))
+ (if (< max1 max2)
+ (setq range1 (cdr range1))
+ (setq range2 (cdr range2)))))
+ ((and `(,num1 (,min2 . ,max2))
+ (guard (numberp num1)))
+ (when (<= min2 num1 max2)
+ (setq out (cons num1 out)))
+ (if (< max2 num1)
+ (setq range2 (cdr range2))
+ (setq range1 (cdr range1))))
+ ((and `((,min1 . ,max1) ,num2)
+ (guard (numberp num2)))
+ (when (<= min1 num2 max1)
+ (setq out (cons num2 out)))
+ (if (< max1 num2)
+ (setq range1 (cdr range1))
+ (setq range2 (cdr range2))))
+ ((and `(,num1 ,num2)
+ (guard (and (numberp num1)
+ (numberp num2))))
+ (when (= num1 num2)
+ (setq out (cons num1 out)))
+ (if (< num1 num2)
+ (setq range1 (cdr range1))
+ (setq range2 (cdr range2)))))))
(cond ((cdr out)
(nreverse out))
((numberp (car out))
--
2.37.0 (Apple Git-136)
--=-=-=--
Zachary Romero <zacromero@HIDDEN>:bug-gnu-emacs@HIDDEN.
Full text available.bug-gnu-emacs@HIDDEN:bug#68232; Package emacs.
Full text available.
GNU bug tracking system
Copyright (C) 1999 Darren O. Benham,
1997 nCipher Corporation Ltd,
1994-97 Ian Jackson.