X-Loop: help-debbugs@HIDDEN Subject: bug#68232: [PATCH] Fix range-intersection implementation Resent-From: Zachary Romero <zacromero@HIDDEN> Original-Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org> Resent-CC: bug-gnu-emacs@HIDDEN Resent-Date: Wed, 03 Jan 2024 17:39:03 +0000 Resent-Message-ID: <handler.68232.B.170430354016221 <at> debbugs.gnu.org> Resent-Sender: help-debbugs@HIDDEN X-GNU-PR-Message: report 68232 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: patch To: 68232 <at> debbugs.gnu.org X-Debbugs-Original-To: bug-gnu-emacs@HIDDEN Received: via spool by submit <at> debbugs.gnu.org id=B.170430354016221 (code B ref -1); Wed, 03 Jan 2024 17:39:03 +0000 Received: (at submit) by debbugs.gnu.org; 3 Jan 2024 17:39:00 +0000 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> 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-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) --=-=-=--
Content-Disposition: inline Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 X-Mailer: MIME-tools 5.505 (Entity 5.505) Content-Type: text/plain; charset=utf-8 X-Loop: help-debbugs@HIDDEN From: help-debbugs@HIDDEN (GNU bug Tracking System) To: Zachary Romero <zacromero@HIDDEN> Subject: bug#68232: Acknowledgement ([PATCH] Fix range-intersection implementation) Message-ID: <handler.68232.B.170430354016221.ack <at> debbugs.gnu.org> References: <m2le97drf3.fsf@HIDDEN> X-Gnu-PR-Message: ack 68232 X-Gnu-PR-Package: emacs X-Gnu-PR-Keywords: patch Reply-To: 68232 <at> debbugs.gnu.org Date: Wed, 03 Jan 2024 17:39:03 +0000 Thank you for filing a new bug report with debbugs.gnu.org. This is an automatically generated reply to let you know your message has been received. Your message is being forwarded to the package maintainers and other interested parties for their attention; they will reply in due course. Your message has been sent to the package maintainer(s): bug-gnu-emacs@HIDDEN If you wish to submit further information on this problem, please send it to 68232 <at> debbugs.gnu.org. Please do not send mail to help-debbugs@HIDDEN unless you wish to report a problem with the Bug-tracking system. --=20 68232: https://debbugs.gnu.org/cgi/bugreport.cgi?bug=3D68232 GNU Bug Tracking System Contact help-debbugs@HIDDEN with problems
X-Loop: help-debbugs@HIDDEN Subject: bug#68232: [PATCH] Fix range-intersection implementation Resent-From: Stefan Kangas <stefankangas@HIDDEN> Original-Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org> Resent-CC: bug-gnu-emacs@HIDDEN Resent-Date: Thu, 11 Jan 2024 20:57:02 +0000 Resent-Message-ID: <handler.68232.B68232.170500658022621 <at> debbugs.gnu.org> Resent-Sender: help-debbugs@HIDDEN X-GNU-PR-Message: followup 68232 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: patch To: Zachary Romero <zacromero@HIDDEN> Cc: 68232 <at> debbugs.gnu.org, Lars Magne Ingebrigtsen <larsi@HIDDEN> Received: via spool by 68232-submit <at> debbugs.gnu.org id=B68232.170500658022621 (code B ref 68232); Thu, 11 Jan 2024 20:57:02 +0000 Received: (at 68232) by debbugs.gnu.org; 11 Jan 2024 20:56:20 +0000 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> Content-Type: text/plain; charset="UTF-8" X-Spam-Score: -0.0 (/) 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?
X-Loop: help-debbugs@HIDDEN Subject: bug#68232: [PATCH] Fix range-intersection implementation Resent-From: zacromero@HIDDEN Original-Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org> Resent-CC: bug-gnu-emacs@HIDDEN Resent-Date: Fri, 12 Jan 2024 02:45:02 +0000 Resent-Message-ID: <handler.68232.B68232.17050274795186 <at> debbugs.gnu.org> Resent-Sender: help-debbugs@HIDDEN X-GNU-PR-Message: followup 68232 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: patch To: Stefan Kangas <stefankangas@HIDDEN> Cc: 68232 <at> debbugs.gnu.org, Lars Magne Ingebrigtsen <larsi@HIDDEN> Received: via spool by 68232-submit <at> debbugs.gnu.org id=B68232.17050274795186 (code B ref 68232); Fri, 12 Jan 2024 02:45:02 +0000 Received: (at 68232) by debbugs.gnu.org; 12 Jan 2024 02:44:39 +0000 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 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-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--
GNU bug tracking system
Copyright (C) 1999 Darren O. Benham,
1997 nCipher Corporation Ltd,
1994-97 Ian Jackson.