#hkt #generics #gat #streaming-iterator #windows-mut

no-std lending-iterator

Fully general lending iterators in stable rust: windows_mut!

16 releases

0.1.7 Apr 4, 2023
0.1.7-rc1 Apr 2, 2023
0.1.6 Aug 8, 2022
0.1.5 Jul 22, 2022
0.0.0 May 26, 2022

#265 in Rust patterns

Download history 9418/week @ 2024-07-22 7292/week @ 2024-07-29 6669/week @ 2024-08-05 6900/week @ 2024-08-12 8933/week @ 2024-08-19 7776/week @ 2024-08-26 8996/week @ 2024-09-02 7802/week @ 2024-09-09 5756/week @ 2024-09-16 10295/week @ 2024-09-23 8860/week @ 2024-09-30 8995/week @ 2024-10-07 11898/week @ 2024-10-14 11878/week @ 2024-10-21 10846/week @ 2024-10-28 10262/week @ 2024-11-04

44,942 downloads per month
Used in 6 crates (5 directly)

Zlib OR MIT OR Apache-2.0

88KB
1.5K SLoC

::lending-iterator

Repository Latest version Documentation MSRV unsafe forbidden License CI

Fully generic LendingIterators in stable Rust.

  • this pattern used to be called StreamingIterator, but since Streams entered the picture (as the async/.await version of Iterators, that is, AsyncIterators), it has been deemed more suitable to go for the lending naming convention.

    • (this could be even more relevant since you can have a LendingIterator lending impl Futures, which would effectively make it another flavor of AsyncIterator, but not quite the Stream variant).
  • For context, this crate is a generalization of other crates such as:

    which hard-code their lending Item type to &_ and Result<&_, _> respectively.

    This crate does not hardcode such dependent types, and thus encompasses both of those traits, and infinitely more!

  • Mainly, it allows lending &mut _ Items, which means it can handle the infamously challenging windows_mut() pattern!

Examples

Click to hide

windows_mut()!

use ::lending_iterator::prelude::*;

let mut array = [0; 15];
array[1] = 1;
// Cumulative sums are trivial with a `mut` sliding window,
// so let's showcase that by generating a Fibonacci sequence.
let mut iter = array.windows_mut::<3>();
while let Some(&mut [a, b, ref mut next]) = iter.next() {
    *next = a + b;
}
assert_eq!(
    array,
    [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377],
);

Rolling your own version of it using the handy from_fn constructor

  • (Or even the FromFn flavor of it to enjoy "named arguments")
use ::lending_iterator::prelude::*;

let mut array = [0; 15];
array[1] = 1;
// Let's hand-roll our iterator lending `&mut` sliding windows:
let mut iter = {
    let mut start = 0;
    lending_iterator::FromFn::<HKT!(&mut [u16; 3]), _, _> {
        state: &mut array,
        next: move |array| {
            let to_yield =
                array
                    .get_mut(start..)?
                    .get_mut(..3)?
                    .try_into() // `&mut [u8] -> &mut [u8; 3]`
                    .unwrap()
            ;
            start += 1;
            Some(to_yield)
        },
        _phantom: <_>::default(),
    }
};
while let Some(&mut [a, b, ref mut next]) = iter.next() {
    *next = a + b;
}
assert_eq!(
    array,
    [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377],
);
  • where that HKT!(&mut [u16; 3]) is a higher-kinded type parameter that has to be turbofished to let the generic context properly figure out the return type of the next closure.

    Indeed, if we were to let type inference, alone, figure it out, it wouldn't be able to know which lifetimes would be fixed/tied to call-site captures, and which would be tied to the "lending-ness" of the iterator (higher-order return type). See ::higher-order-closure for more info about this.

LendingIterator adapters

See lending_iterator::adapters.


Bonus: Higher-Kinded Types (HKT)

See higher_kinded_types for a presentation about them.

Real-life usage: .sort_by_key() that is fully generic over the key lending mode

As noted in this 6-year-old issue:

Such an API can easily be provided using the HKT API of this crate:

Click to show
use ::lending_iterator::higher_kinded_types::{*, Apply as A};

fn slice_sort_by_key<Key, Item, KeyGetter> (
    slice: &'_ mut [Item],
    mut get_key: KeyGetter,
)
where
    Key : HKT, // "Key : <'_>"
    KeyGetter : for<'item> FnMut(&'item Item) -> A!(Key<'item>),
    for<'item>
        A!(Key<'item>) : Ord
    ,
{
    slice.sort_by(|a, b| Ord::cmp(
        &get_key(a),
        &get_key(b),
    ))
}

// ---- Demo ----

struct Client { key: String, version: u8 }

fn main ()
{
    let clients: &mut [Client] = &mut [];

    // Error: cannot infer an appropriate lifetime for autoref due to conflicting requirements
    // clients.sort_by_key(|c| &c.key);

    // OK
    slice_sort_by_key::<HKT!(&str), _, _>(clients, |c| &c.key);

    // Important: owned case works too!
    slice_sort_by_key::<HKT!(u8), _, _>(clients, |c| c.version);
}

Dependencies

~2MB
~40K SLoC