Crate lender

Expand description

§`lender` 🙂

license

A lender, also called a lending iterator, is an iterator that lends mutable borrows to the items it returns. In particular, this means that the reference to an item is invalidated by the subsequent call to next. Niko Matsakis has an interesting blog post explaining a general view of giving vs. lending traits.

The typical example that cannot be written with standard Rust iterators, but is covered by lenders, is that of a lender returning mutable, overlapping windows of a slice or array.

But lenders are more general than that, as they might return items that depend on some mutable state stored in the iterator. For example, a lender might return references to the lines of a file reusing an internal buffer; also, starting from an iterator on pairs of integers lexicographically sorted, a lender might return iterators on pairs with the same first coordinate without any copying; clearly, in all these cases any call on next would invalidate the reference returned by the previous call.

This crate provides a lender trait and an associated library of utility methods, “utilizing” #84533 and #25860 to implement the lender design based on higher-rank trait bounds proposed by Sabrina Jewson.

Similarly to what happens with standard iterators, besides the fundamental Lender trait there is an IntoLender trait, and methods such as for_each.

Indeed, the crate implements for Lender all of the methods as Iterator, except partition_in_place and array_chunks (the latter being replaced by chunky), and most methods provide the same functionality as the equivalent Iterator method.

Notable differences in behavior include next_chunk providing a lender instead of an array and certain closures requiring usage of the hrc!, hrc_mut!, hrc_once! (higher-rank closure) macros, which provide a stable replacement for the closure_lifetime_binder feature.

Turn a lender into an iterator with cloned where lend is Clone, copied where lend is Copy, owned where lend is ToOwned, or iter where the lender already satisfies the restrictions of Iterator.

§Usage

The Rust for syntax for iterating over types implementing IntoIterator will not work with lenders. The idiomatic way of iterating over a lender is to use a while let loop, as in:

while let Some(item) = lender.next() {
    // Do something with item
}

Note that the expression after the equal sign cannot be a method call returning a lender, as you would iterate over the first element forever.

To simplify usage, we provide a function-like procedural macro for_! that makes it possible to use a for-like syntax with types implementing IntoLender:

for_!(item in into_lender {
    // Do something with item
});

Finally, you can use the for_each method, which takes a closure as argument, but managing lifetimes in closures can be challenging:

lender.for_each{
    hrc_mut!(for<'lend> |item: &'lend mut TYPE| {
        // do something with item of type TYPE 
    })
};

§Binding the Lend

When writing methods accepting a Lender, to bind the type of the returned lend you need to use a higher-rank trait bound, as in:

use lender::*;

fn read_lender<L>(mut lender: L)
where
    L: Lender + for<'lend> Lending<'lend, Lend = &'lend str>,
{
    let _: Option<&'_ str> = lender.next(); 
}

You can also bind the lend using traits:

use lender::*;

fn read_lender<L>(mut lender: L)
where
    L: Lender + for<'lend> Lending<'lend, Lend: AsRef<str>>,
{
    let lend = lender.next();
    let _: Option<&'_ str> = lend.as_ref().map(AsRef::as_ref);
}

In this case, you can equivalently use the Lend type alias, which might be more concise:

use lender::*;

fn read_lender<L>(mut lender: L)
where
    L: Lender,
    for<'lend> Lend<'lend, L>: AsRef<str>,
{
    let lend = lender.next();
    let _: Option<&'_ str> = lend.as_ref().map(AsRef::as_ref);
}

§Caveats

If a dyn Lender trait object is in your future, this crate is not going to work.

Finally, note that, as a general rule, if you can avoid using lenders, you should. You should heed the counsel of Polonius: “Neither a borrower nor a lender be”.

§Examples

Let us compute the Fibonacci numbers using mutable windows:

use ::lender::prelude::*;
use lender_derive::for_;

// Fibonacci sequence
let mut data = vec![0u32; 3 * 3];
data[1] = 1;

// Fibonacci sequence, most ergonomic usage: for_! procedural macro.
for_!(w in data.array_windows_mut::<3>() {
   w[2] = w[0] + w[1];
});
assert_eq!(data, [0, 1, 1, 2, 3, 5, 8, 13, 21]);

// You can use decostructing assignments with for_!.
for_!([a, b, c] in data.array_windows_mut::<3>() {
   *c = *a + *b;
});
assert_eq!(data, [0, 1, 1, 2, 3, 5, 8, 13, 21]);

// Fibonacci sequence, explicit while let loop: you MUST assign the lender to a variable.
let mut windows = data.array_windows_mut::<3>();
while let Some(w) = windows.next() {
   w[2] = w[0] + w[1];
}
assert_eq!(data, [0, 1, 1, 2, 3, 5, 8, 13, 21]);

// Fibonacci sequence, for_each with hrc_mut!
data.array_windows_mut::<3>()
    .for_each(hrc_mut!(for<'lend> |w: &'lend mut [u32; 3]| {
         w[2] = w[0] + w[1]
    }));
assert_eq!(data, [0, 1, 1, 2, 3, 5, 8, 13, 21]);

This is a quite contrived example, but it shows how lenders can be used to mutate a slice in place.

So, let’s look at a slightly more interesting example, LinesStr, an io::Lines with an Item of &str instead of String. It’s a good example of borrowing from the iterator itself.

use std::io;
use ::lender::prelude::*;

struct LinesStr<B> {
    buf: B,
    line: String,
}
impl<'lend, B: io::BufRead> Lending<'lend> for LinesStr<B> {
    type Lend = io::Result<&'lend str>;
}
impl<B: io::BufRead> Lender for LinesStr<B> {
    fn next(&mut self) -> Option<io::Result<&'_ str>> {
        self.line.clear();
        match self.buf.read_line(&mut self.line) {
            Err(e) => return Some(Err(e)),
            Ok(0) => return None,
            Ok(_nread) => (),
        };
        if self.line.ends_with('\n') {
            self.line.pop();
            if self.line.ends_with('\r') {
                self.line.pop();
            }
        }
        Some(Ok(&self.line))
    }
}

let buf = io::BufReader::with_capacity(10, "Hello\nWorld\n".as_bytes());
let mut lines = LinesStr { buf, line: String::new() };
assert_eq!(lines.next().unwrap().unwrap(), "Hello");
assert_eq!(lines.next().unwrap().unwrap(), "World");

§Implementing Lender

To implement Lender first you’ll need to implement the Lending trait for your type. This is the equivalent provider of Iterator::Item:

use ::lender::prelude::*;
struct StrRef<'a>(&'a str);
impl<'this, 'lend> Lending<'lend> for StrRef<'this> {
    type Lend = &'lend str;
}

The lifetime parameter 'lend describes the lifetime of the Lend. It works by using under the hood a default generic of &'lend Self which induces an implicit reference lifetime bound 'lend: 'this, which is necessary for usage of higher-rank trait bounds with Lend.

Next, you’ll need to implement the Lender trait for your type, the lending equivalent of Iterator.

use ::lender::prelude::*;
struct StrRef<'a>(&'a str);
impl<'this, 'lend> Lending<'lend> for StrRef<'this> {
    type Lend = &'lend str;
}
impl<'this> Lender for StrRef<'this> {
    fn next(&mut self) -> Option<&'_ str> {
        Some(self.0)
    }
}

The Lend type alias can be used to avoid specifying twice the type of the lend; combined with lifetime elision, it can make your implementations more concise and less prone to errors:

use ::lender::prelude::*;
struct StrRef<'a>(&'a str);
impl<'this, 'lend> Lending<'lend> for StrRef<'this> {
    type Lend = &'lend str;
}
impl<'this> Lender for StrRef<'this> {
    fn next(&mut self) -> Option<Lend<'_, Self>> {
        Some(self.0)
    }
}

§Why Not GATs?

Generic associated types (GATs) were introduced exactly having lending iterators as a use case in mind. With GATs, a lender trait could be easily defined as

pub trait Lender {
    type Lend<'lend>: where Self: 'lend;
    fn next(&mut self) -> Option<Self::Lend<'_>>;
}

This looks all nice and cozy, and you can even write a full-fledged library around it. But you will hit a wall when trying to specify trait bounds on the lend type, something that can be done only using higher-rank trait bounds:

pub trait Lender {
    type Lend<'lend>: where Self: 'lend;
    fn next(&mut self) -> Option<Self::Lend<'_>>;
}

fn read_lender<L: Lender>(lender: L) 
    where for<'lend> L::Lend<'lend>: AsRef<str> {}

Again, this will compile without problems, but as you try to use read_lender with a type implementing Lender, since the where clause specifies that that trait bound must hold for all lifetimes, that means it must be valid for 'static, and since the lender must outlive the lend, also the lender must be 'static. Thus, until there is some syntax that makes it possible to restrict the lifetime variable that appears in a higher-rank trait bound, GAT-based lending iterators are of little practical use.

§Resources

Please check out the great resources below that helped us and many others learn about Rust and the lending iterator problem. Thank you to everyone!

Sabrina Jewson’s Blog for her awesome blog post on why lifetime GATs are not (yet) the solution to this problem, we highly recommend reading it.
The awesome people on the Rust Users Forum in helping us understand the borrow checker and HRTBs better and being patient with us and other aspiring rustaceans as we try to learn more about Rust.
Daniel Henry-Mantilla for writing lending-iterator and many other great crates and sharing their great work.
Everyone who’s contributed to Rust for making such a great language and iterator library.

§Unsafe & Transmutes

Many patterns in lenders require polonius-emulating unsafe code, but if you see any unsafe code that can be made safe, please let us know!

Re-exports§

pub use stable_try_trait_v2 as try_trait_v2;

Modules§

higher_order: Higher-Order Types, Traits, etc.
prelude

Macros§

for_: Syntax sugar for iterating over a Lender.
hrc: Higher-Rank Closure (Fn) macro that replaces the closure_lifetime_binder feature for stable.
hrc_mut: Higher-Rank Closure (FnMut) macro that replaces the closure_lifetime_binder feature for stable.
hrc_once: Higher-Rank Closure (FnOnce) macro that replaces the closure_lifetime_binder feature for stable.
lend: Use lifetime 'lend within type $T to create an impl for<'lend> Lending<'lend, Lend = $T>. Uses a bug in the borrow checker which allows dyn objects to implement impossible traits.

Structs§

ArrayWindowsMut: This struct is returned by array_windows_mut.
Chain
Chunk
Chunky: A lender yielding lenders returning the next chunk_size lends.
Cloned
Copied
Cycle
Empty: A lender that yields nothing.
Enumerate
Filter
FilterMap
FlatMap
Flatten
FromFn: An lender where each iteration calls the provided closure F: FnMut(&mut St) -> Option<T>.
FromIntoIter: A IntoLender that returns lenders obtained by applying from_iter to the iterators returned by the wrapped IntoIterator.
FromIter: A lender that yields elements from an iterator.
Fuse
Inspect
Intersperse
IntersperseWith
Iter: Iterator adapter for any Lender where multiple Lends can exist at a time, allowing on-the-fly conversion into an iterator where Lending is no longer needed or inferred.
LendIter: A lender that lends elements from an iterator by shortening their lifetime.
Map
MapIntoIter
MapWhile
Mutate
Once: A lender that yields an element exactly once.
OnceWith: An iterator that yields a single element of type A by applying the provided closure F: FnOnce() -> A.
Owned
Peekable
Repeat: A lender that repeats an element endlessly.
RepeatWith: A lender that repeats an element endlessly by applying a closure.
Rev
Scan
Skip
SkipWhile
StepBy
Take
TakeWhile
TryShunt: Private adapter. Turns a Lender, where Lend implements Try, into a Lender of <Lend as Try>::Output.
WindowsMut: This struct is returned by windows_mut.
Zip

Traits§

DoubleEndedLender: Documentation is incomplete. Refer to core::iter::DoubleEndedIterator for more information
ExactSizeLender: Documentation is incomplete. Refer to core::iter::ExactSizeIterator for more information
ExtendLender: Documentation is incomplete. Refer to core::iter::Extend for more information
FromLender: Example
FusedLender: Documentation is incomplete. Refer to core::iter::FusedIterator for more information
IntoIteratorExt: Extension trait adding to IntoIterator the method into_into_lender, which turns an IntoIterator into a IntoLender without allocation.
IntoLender: Documentation is incomplete. Refer to core::iter::IntoIterator for more information
IteratorExt: Extension trait adding to Iterator the method into_lender, which turns an Iterator into a Lender without allocation.
Lender: A trait for dealing with lending iterators.
Lending: A trait for dealing with the ‘items’ of lending iterators.
ProductLender: Documentation is incomplete. Refer to core::iter::Product for more information
SumLender: Sums lends of a Lender into a single Self.
TupleLend: Marker trait for tuple lends, used by Lender::unzip().
WindowsMutExt: Extension trait adding to slices and arrays the methods windows_mut and array_windows_mut.

Functions§

array_windows_mut: Create a new lender that returns mutable overlapping array windows of fixed size over a slice.
empty: Creates a lender that yields nothing.
from_fn: Creates a lender from a state and a closure F: FnMut(&mut St) -> Option<T>.
from_into_iter: Creates an IntoLender from an IntoIterator.
from_iter: Creates a lender from an iterator.
lend_iter: Creates a lender from an iterator I, safely shortening the items’ lifetimes with the given lending type L.
once: Creates a lender that yields an element exactly once.
once_with: Creates an lender that lazily generates a value exactly once by invoking the provided closure.
repeat: Creates a new lender that endlessly repeats a single element.
repeat_with: Creates a new iterator that repeats elements of type A endlessly by applying the provided closure, the repeater, F: FnMut() -> A.
windows_mut: Create a new lender that returns mutable contiguous overlapping windows of fixed size over a slice.
zip

Type Aliases§

Lend: A readable shorthand for the type of the items of a Lender L.

Crate lender

Crate lender Copy item path

§lender 🙂

§Usage

§Binding the Lend

§Caveats

§Examples

§Implementing Lender

§Why Not GATs?

§Resources

§Unsafe & Transmutes

Re-exports§

Modules§

Macros§

Structs§

Traits§

Functions§

Type Aliases§

Crate lender

§`lender` 🙂