Questions about backend interface and ranges

Questions about backend interface and ranges

[John McClary Prevost]

I have a couple of questions about ranges and about the interface
of nn*-retrieve-headers.

The ARTICLES argument of retrieve-headers is said to take "either a
range of article numbers or a list of Message-IDs."  I take that to
mean that it can contain Message-IDs, or a range, but not both?

Second, I'm about to implement a set of "useful range operations" in
order to get the nnimap stuff working better.  Here's what I plan to
implement:

(nnimap-range-split RANGE &optional COUNT)

This function takes a RANGE and returns a cons cell of a range
containing the first numerical member of the range and the range
without that first member.  I.e.:

(nnimap-range-split ((1 . 5) 7)) => ( (1) . ((2 . 5) 7) )

If the optional COUNT is given, COUNT items are returned as a second
range.  Like so:

(nnimap-range-split '((1 . 20) (30 . 500)) 400) =>
   ( ((1 . 20) (30 . 410)) . (411 . 500) )

[ The function might better be split into two: *-range-head and
  *-range-tail ]

This operation is fairly simple, and it is useful for two reasons.
First, a backend can use it to chop off a single item from a range at
a time, in order to do retrieve operations via methods that can only
deal with getting one article at a time.  Second, a protocol like IMAP
which can request multiple messages at a time (basically, you can get
a single article or an unbroken range of articles but not combinations
of the two) can use it to break a range down into bite-sized
chunks--this is good, because doing an
(nnimap-retrieve-headers '((1 . 1000))) right now doesn't give much
feedback until the operation is complete--it's too busy reading things
in.  This could result in deadlock, I assume, since nntp.el is worried
about reading things in every so often.

That function would be extremely useful, as would two others:

(*-range-length RANGE) : returns the number of individual articles in
a range.

(*-range-eq RANGE1 RANGE2) : returns t if they're equivalent, nil if
not.  This is a fairly easy operation, and has O(n+m) where n is the
number of discrete elements in RANGE1 and m is the number in RANGE2.

I'll code these into my nnimap.el for the time-being, but they'd
probably be better off in some other piece of code.

Re: Questions about backend interface and ranges

[Lars Magne Ingebrigtsen]

visigoth@olivier.pc.cs.cmu.edu (John McClary Prevost) writes:

> The ARTICLES argument of retrieve-headers is said to take "either a
> range of article numbers or a list of Message-IDs."  I take that to
> mean that it can contain Message-IDs, or a range, but not both?

Yup.  But you should take the "range" thing in the manual with a pinch
of salt.  Gnus uses virtually nothing but sorted numerical lists for
all these functions.  (Sorted numerical lists are a degenerate form of
a range, though, so the manual isn't actually wrong.  It's just more
strict than what the reality is.)

> Second, I'm about to implement a set of "useful range operations" in
> order to get the nnimap stuff working better. 

All the functions you outline are indeed useful.  The reason that
Gnus doesn't use (proper) ranges for much now is that functions like
that hadn't been written yet.

So if you write the functions, Gnus will begin to make them useful.
:-)

> (nnimap-range-split RANGE &optional COUNT)
> 
> This function takes a RANGE and returns a cons cell of a range
> containing the first numerical member of the range and the range
> without that first member.  I.e.:
> 
> (nnimap-range-split ((1 . 5) 7)) => ( (1) . ((2 . 5) 7) )

Perhaps `range-car' and `range-cdr' would be two useful functions
instead?  They would (kinda) mimic what `car' and `cdr' do for normal
lists...

> If the optional COUNT is given, COUNT items are returned as a second
> range.  Like so:
> 
> (nnimap-range-split '((1 . 20) (30 . 500)) 400) =>
>    ( ((1 . 20) (30 . 410)) . (411 . 500) )

That would be extremely useful.  I hadn't thought of that one.

> [ The function might better be split into two: *-range-head and
>   *-range-tail ]

Common Lisp calls the equivalent list functions `but-last' and
`last'...  No, wait, these would return ranges (lists) and `last' jsut
returns the last element...

> (*-range-length RANGE) : returns the number of individual articles in
> a range.

Yup; very useful.

> (*-range-eq RANGE1 RANGE2) : returns t if they're equivalent, nil if
> not.  This is a fairly easy operation, and has O(n+m) where n is the
> number of discrete elements in RANGE1 and m is the number in RANGE2.

Yup.

> I'll code these into my nnimap.el for the time-being, but they'd
> probably be better off in some other piece of code.

I haven't suggested this to RMS yet, but I would like functions like
this to exist in a separate "range.el" package, so the functions would
just be called `range-eq' and stuff.

-- 
Home is where the cat is.

Re: Questions about backend interface and ranges

[John McClary Prevost]

>>>>> "lmi" == Lars Magne Ingebrigtsen <larsi@ifi.uio.no> writes:

    lmi> Yup.  But you should take the "range" thing in the manual with a pinch
    lmi> of salt.  Gnus uses virtually nothing but sorted numerical lists for
    lmi> all these functions.  (Sorted numerical lists are a degenerate form of
    lmi> a range, though, so the manual isn't actually wrong.  It's just more
    lmi> strict than what the reality is.)

Yup--just trying to make my code as general as possible.  If your
document says ranges, I'll implement ranges.  ;>

    lmi> All the functions you outline are indeed useful.  The reason that
    lmi> Gnus doesn't use (proper) ranges for much now is that functions like
    lmi> that hadn't been written yet.

    lmi> So if you write the functions, Gnus will begin to make them useful.
    lmi> :-)

I'll write them up, then.  They might not be the most optimal form at
first (I'm not sure what needs to be done to make things optimal under
emacs... maybe the more trivial things should be macros) but somone
else can work that out later if need be.

    lmi> Perhaps `range-car' and `range-cdr' would be two useful functions
    lmi> instead?  They would (kinda) mimic what `car' and `cdr' do for normal
    lmi> lists...


         {...being able to get "first n pieces" out of range...}
    lmi> That would be extremely useful.  I hadn't thought of that one.

Better yet--if this operation were smart enough to group sequences of
numbers together (like getting the first 5 from (1 2 3 4 5 6 7) gives
you (1 . 5) and not (1 2 3 4 5)...)  Hmm...

    lmi> Common Lisp calls the equivalent list functions `but-last' and
    lmi> `last'...  No, wait, these would return ranges (lists) and `last' jsut
    lmi> returns the last element...

What I'm considering for names now is range-first and range-rest, to
go with the "first" and "rest" of CL.  Using an optional argument, it
also makes sense: (range-first foo 5) is the first 5 elements of foo.

    lmi> I haven't suggested this to RMS yet, but I would like functions like
    lmi> this to exist in a separate "range.el" package, so the functions would
    lmi> just be called `range-eq' and stuff.

Okay--I'm making a new range.el file, then.  Here's my list of
functions at the moment:

(range-first RANGE &optional COUNT)
(range-but-first RANGE &optional COUNT)
(range-append RANGE1 RANGE2)
(range-equal RANGE1 RANGE2)
(range-is-member-p RANGE NUMBER)
(range-add-member RANGE NUMBER)

These are pretty much self descriptive.  To be technical on what
range-append means, though, this is the guarantee:

{ for all z | z in R1 or z in R2, z is in (range-append R1 R2) }

Off to code it...

John.