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

From: [email-masked]
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