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

Previous Next

Full log

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

Previous Next

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