Subject: bug#68232: [PATCH] Fix range-intersection implementation

From: Andrew Cohen <[email-masked]>
Date: Thu, 13 Feb 2025 13:55:54 +0800

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

diff --git a/lisp/emacs-lisp/range.el b/lisp/emacs-lisp/range.el
index 770bf572289..e430448cfef 100644
--- a/lisp/emacs-lisp/range.el
+++ b/lisp/emacs-lisp/range.el
@@ -30,6 +30,16 @@
 
 ;;; Code:
 
+(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))))
+
 (defun range-normalize (range)
   "Normalize RANGE.
 If RANGE is a single range, return (RANGE).  Otherwise, return RANGE."
@@ -88,50 +98,23 @@ range-difference
     (cdr new-range)))
 
 (defun range-intersection (range1 range2)
-  "Return intersection of RANGE1 and RANGE2."
-  (let* (out
-         (min1 (car range1))
-         (max1 (if (numberp min1)
-                   (if (numberp (cdr range1))
-                       (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))))
+  "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))

-- 
Andrew Cohen