GNU bug report logs - #68232
[PATCH] Fix range-intersection implementation

Previous Next

To reply to this bug, email your comments to 68232 AT debbugs.gnu.org.

Toggle the display of automated, internal messages from the tracker.

Message #5 received at submit <at> debbugs.gnu.org (full text, mbox):

From: Zachary Romero <zacromero <at> posteo.net>
To: bug-gnu-emacs <at> gnu.org
Subject: [PATCH] Fix range-intersection implementation
Date: Wed, 03 Jan 2024 03:30:56 +0000

[Message part 1 (text/plain, inline)]

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 <at> 29/29.0.60/share/info/emacs
 --prefix=/usr/local/Cellar/emacs-plus <at> 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 <at> 1.1/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 <at> 1.1/lib
 -L/usr/local/lib -F/usr/local/Frameworks
 -Wl,-headerpad_max_install_names
 -isysroot/Library/Developer/CommandLineTools/SDKs/MacOSX12.sdk''

[0001-Fix-range-intersection-implementation.patch (text/patch, attachment)]

Message #8 received at 68232 <at> debbugs.gnu.org (full text, mbox):

From: Stefan Kangas <stefankangas <at> gmail.com>
To: Zachary Romero <zacromero <at> posteo.net>
Cc: 68232 <at> debbugs.gnu.org, Lars Magne Ingebrigtsen <larsi <at> gnus.org>
Subject: Re: bug#68232: [PATCH] Fix range-intersection implementation
Date: Thu, 11 Jan 2024 12:56:13 -0800

Zachary Romero <zacromero <at> posteo.net> 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?

Message #11 received at 68232 <at> debbugs.gnu.org (full text, mbox):

From: zacromero <at> posteo.net
To: Stefan Kangas <stefankangas <at> gmail.com>
Cc: 68232 <at> debbugs.gnu.org, Lars Magne Ingebrigtsen <larsi <at> gnus.org>
Subject: Re: bug#68232: [PATCH] Fix range-intersection implementation
Date: Fri, 12 Jan 2024 02:44:29 +0000

[Message part 1 (text/plain, inline)]

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 <at> posteo.net> 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?

[0001-fix-range-intersection-edge-cases.patch (application/octet-stream, attachment)]

Message #14 received at 68232 <at> debbugs.gnu.org (full text, mbox):

From: Stefan Kangas <stefankangas <at> gmail.com>
To: zacromero <at> posteo.net
Cc: 68232 <at> debbugs.gnu.org, Lars Magne Ingebrigtsen <larsi <at> gnus.org>
Subject: Re: bug#68232: [PATCH] Fix range-intersection implementation
Date: Tue, 11 Feb 2025 11:58:07 -0800

zacromero <at> posteo.net writes:

> Thanks for pointing me to the tests. Attached is an updated patch with the added
> test cases and the range tests all pass.

Sorry for the delayed reply here.

It would seem that this contribution is too large for us to accept
without a copyright assignment from you.  Would you like to start the
copyright assignment process now?

Message #19 received at 68232 <at> debbugs.gnu.org (full text, mbox):

From: Andrew Cohen <acohen <at> ust.hk>
To: Stefan Kangas <stefankangas <at> gmail.com>, zacromero <at> posteo.net
Cc: 68232 <at> debbugs.gnu.org, Lars Magne Ingebrigtsen <larsi <at> gnus.org>
Subject: Re: bug#68232: [PATCH] Fix range-intersection implementation
Date: Thu, 13 Feb 2025 13:55:54 +0800

[Message part 1 (text/plain, inline)]

Wow, that is an excellent catch! This bug has apparently been present
forever. Thanks so much for finding it and sending a patch!

The function range-intersection is used in gnus in three places: two of
them are purely defensive (i.e. in code paths that should not normally
be reached) and one that is important (in nnimap.el). Since errors here
might cause problems with email I thought we should fix it ASAP
(although it has been this way for so long it's not likely to be a
source of any real problems).

As Zachary identified, the problem arises from the handling of both
integers and cons-pairs as part of ranges. I think it would be best if
we avoid this entirely by introducing two (inline) functions that return
the lower and upper ends of an interval, and work both with a cons and
an integer):

(define-inline range-min (x)
  "Return the lower end of the interval X."
  (inline-letevals (x)
    (inline-quote (if (consp ,x) (car ,x) ,x))))

(define-inline range-max (x)
  "Return the upper end of the interval X."
  (inline-letevals (x)
    (inline-quote (if (consp ,x) (cdr ,x) ,x))))

Then all of the functions in range.el can be made much more
transparent. For example here is my version of 'range-intersection using
these accessors:

(defun range-intersection (range1 range2)
  "Return intersection of RANGE1 and RANGE2.
RANGE1 and RANGE2 must be sorted lists of disjoint intervals."
  ;; Normalize the ranges
  (setq range1 (range-normalize range1)
        range2 (range-normalize range2))
  (let (out)
    (while-let ((i1 (car range1))
                (i2 (car range2)))
      (seq-let (min1 max1 min2 max2)
          `(,(range-min i1) ,(range-max i1) ,(range-min i2) ,(range-max i2))
        (unless (or (< max1 min2) (< max2 min1))
          (let ((m (max min1 min2))
                (M (min max1 max2)))
            (push (if (= m M) m (cons m M)) out)))
        (if (< max1 max2)
            (setq range1 (cdr range1))
          (setq range2 (cdr range2)))))
    (cond ((cdr out)
           (nreverse out))
          ((numberp (car out))
           out)
          (t
           (car out)))))

I haven't tried to clean up the other functions in range.el using these
accessors, which would be a useful exercise.

Best,
Andy

[range.diff (text/x-diff, attachment)]

[Message part 3 (text/plain, inline)]

-- 
Andrew Cohen

Message #22 received at 68232 <at> debbugs.gnu.org (full text, mbox):

From: zacromero <at> posteo.net
To: Andrew Cohen <acohen <at> ust.hk>
Cc: 68232 <at> debbugs.gnu.org, Lars Magne Ingebrigtsen <larsi <at> gnus.org>,
 Stefan Kangas <stefankangas <at> gmail.com>
Subject: Re: bug#68232: [PATCH] Fix range-intersection implementation
Date: Thu, 13 Feb 2025 20:56:23 +0000

Something like this looks good. I have submitted my copyright assignment 
so I should be good on that front. Definitely let me know if there's 
anything else I should modify or do regarding this.

Best,
Zachary

On 13.02.2025 08:55, Andrew Cohen wrote:
> Wow, that is an excellent catch! This bug has apparently been present
> forever. Thanks so much for finding it and sending a patch!
> 
> The function range-intersection is used in gnus in three places: two of
> them are purely defensive (i.e. in code paths that should not normally
> be reached) and one that is important (in nnimap.el). Since errors here
> might cause problems with email I thought we should fix it ASAP
> (although it has been this way for so long it's not likely to be a
> source of any real problems).
> 
> As Zachary identified, the problem arises from the handling of both
> integers and cons-pairs as part of ranges. I think it would be best if
> we avoid this entirely by introducing two (inline) functions that 
> return
> the lower and upper ends of an interval, and work both with a cons and
> an integer):
> 
> (define-inline range-min (x)
>   "Return the lower end of the interval X."
>   (inline-letevals (x)
>     (inline-quote (if (consp ,x) (car ,x) ,x))))
> 
> (define-inline range-max (x)
>   "Return the upper end of the interval X."
>   (inline-letevals (x)
>     (inline-quote (if (consp ,x) (cdr ,x) ,x))))
> 
> Then all of the functions in range.el can be made much more
> transparent. For example here is my version of 'range-intersection 
> using
> these accessors:
> 
> (defun range-intersection (range1 range2)
>   "Return intersection of RANGE1 and RANGE2.
> RANGE1 and RANGE2 must be sorted lists of disjoint intervals."
>   ;; Normalize the ranges
>   (setq range1 (range-normalize range1)
>         range2 (range-normalize range2))
>   (let (out)
>     (while-let ((i1 (car range1))
>                 (i2 (car range2)))
>       (seq-let (min1 max1 min2 max2)
>           `(,(range-min i1) ,(range-max i1) ,(range-min i2) ,(range-max 
> i2))
>         (unless (or (< max1 min2) (< max2 min1))
>           (let ((m (max min1 min2))
>                 (M (min max1 max2)))
>             (push (if (= m M) m (cons m M)) out)))
>         (if (< max1 max2)
>             (setq range1 (cdr range1))
>           (setq range2 (cdr range2)))))
>     (cond ((cdr out)
>            (nreverse out))
>           ((numberp (car out))
>            out)
>           (t
>            (car out)))))
> 
> I haven't tried to clean up the other functions in range.el using these
> accessors, which would be a useful exercise.
> 
> Best,
> Andy

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.