webgraph/traits/
lenders.rs

1/*
2 * SPDX-FileCopyrightText: 2023 Inria
3 * SPDX-FileCopyrightText: 2023 Sebastiano Vigna
4 * SPDX-FileCopyrightText: 2023 Tommaso Fontana
5 *
6 * SPDX-License-Identifier: Apache-2.0 OR LGPL-2.1-or-later
7 */
8
9//! The [main iteration trait](NodeLabelsLender), convenience types and
10//! associated implementations.
11//!
12//! The implementations in this module have the effect that most of the methods
13//! of a [`Lender`] (e.g., [`lender::Map`]) will return a [`NodeLabelsLender`]
14//! when applied to a [`NodeLabelsLender`]. Without the implementations, one
15//! would obtain a normal [`Lender`], which would not be usable as an argument,
16//! say, of [`BvComp::extend`](crate::graphs::bvgraph::BvComp::extend).
17
18use std::marker::PhantomData;
19
20use lender::{DoubleEndedLender, Lend, Lender, Lending};
21
22use crate::traits::Pair;
23
24/// Iteration on nodes and associated labels.
25///
26/// This trait is a [`Lender`] returning pairs given by a `usize` (a node of the
27/// graph) and an [`IntoIterator`], specified by the associated type
28/// `IntoIterator`, over the labels associated with that node, specified by the
29/// associated type `Label` (which is forced to be identical to the associated
30/// type `Item` of the [`IntoIterator`]).
31///
32/// For those types we provide convenience type aliases [`LenderIntoIterator`],
33/// [`LenderIntoIter`], and [`LenderLabel`].
34///
35/// # Flattening Facilities
36///
37/// The methods [`into_pairs`](NodeLabelsLender::into_pairs) and
38/// [`into_labeled_pairs`](NodeLabelsLender::into_labeled_pairs) convert a
39/// [`NodeLabelsLender`] into an iterator of pairs `(usize, usize)` or labeled
40/// pairs `((usize, usize), Label)`, respectively. These are convenience
41/// methods that delegate to [`From`] trait implementations for [`IntoPairs`]
42/// and [`IntoLabeledPairs`].
43///
44/// # Extension of [`Lender`] Methods
45///
46/// Methods defined on [`Lender`], such as [`Lender::zip`], normally would
47/// return a [`Lender`], but not a [`NodeLabelsLender`]. However, the module
48/// [`lenders`](super::lenders) contains implementations that automatically turn
49/// such as a [`Lender`] into a [`NodeLabelsLender`] whenever it makes sense.
50///
51/// Thus, for example, one can take two graphs and merge easily the first half
52/// of the first one and the second half of the second one:
53/// ```rust
54/// use webgraph::prelude::*;
55/// use webgraph::graphs::random::ErdosRenyi;
56/// use lender::*;
57/// use itertools::Itertools;
58///
59/// // First random graph
60/// let g = ErdosRenyi::new(100, 0.1, 0);
61/// // Second random graph
62/// let h = ErdosRenyi::new(100, 0.1, 1);
63/// let mut v = VecGraph::new();
64/// // Put first half of the first random graph in v
65/// v.add_lender(g.iter().take(50));
66/// // Put second half of the second random graph in v
67/// v.add_lender(h.iter().skip(50));
68///
69/// let mut iter = v.iter();
70/// for i in 0..50 {
71///     itertools::assert_equal(v.successors(i), iter.next().unwrap().1);
72/// }
73/// let mut iter = h.iter().skip(50);
74/// for i in 50..100 {
75///     itertools::assert_equal(v.successors(i), iter.next().unwrap().1);
76/// }
77/// ```
78/// [`VecGraph::add_lender`](crate::graphs::vec_graph::VecGraph::add_lender)
79/// takes a [`NodeLabelsLender`] as an argument, but the implementations in the
80/// module [`lenders`](super::lenders) makes the result of [`Lender::take`] and
81/// [`Lender::skip`] a [`NodeLabelsLender`].
82///
83/// # Propagation of implicit bounds
84///
85/// The definition of this trait emerged from a [discussion on the Rust language
86/// forum](https://users.rust-lang.org/t/more-help-for-more-complex-lifetime-situation/103821/10).
87/// The purpose of the trait is to propagate the implicit bound appearing in the
88/// definition [`Lender`] to the iterator returned by the associated type
89/// [`IntoIterator`]. In this way, one can return iterators depending on the
90/// internal state of the labeling. Without this additional trait, it would be
91/// possible to return iterators whose state depends on the state of the lender,
92/// but not on the state of the labeling.
93///
94/// [`ArcListGraph`](crate::graphs::arc_list_graph::ArcListGraph) is the main
95/// motivation for this trait.
96pub trait NodeLabelsLender<'lend, __ImplBound: lender::ImplBound = lender::Ref<'lend, Self>>:
97    Lender + Lending<'lend, __ImplBound, Lend = (usize, Self::IntoIterator)>
98{
99    type Label;
100    type IntoIterator: IntoIterator<Item = Self::Label>;
101
102    /// Converts this lender into an iterator of labeled pairs of type
103    /// `((usize, usize), Label)`, provided that the label type implements
104    /// [`Pair`] with `Left = usize`.
105    ///
106    /// Typically, this method is used to convert a lender on a labeled graph
107    /// into an iterator of labeled arcs.
108    ///
109    /// This is a convenience method that delegates to the [`From`] trait
110    /// implementation.
111    fn into_labeled_pairs<'a>(self) -> IntoLabeledPairs<'a, Self>
112    where
113        Self: Sized + for<'b> NodeLabelsLender<'b, Label: Pair<Left = usize>>,
114    {
115        self.into()
116    }
117
118    /// Converts this lender into an iterator of pairs, provided that the label
119    /// type is `usize`.
120    ///
121    /// Typically, this method is used to convert a lender on a graph into an
122    /// iterator of arcs expressed as pairs.
123    ///
124    /// This is a convenience method that delegates to the [`From`] trait
125    /// implementation.
126    fn into_pairs<'a>(self) -> IntoPairs<'a, Self>
127    where
128        Self: Sized + for<'b> NodeLabelsLender<'b, Label = usize>,
129    {
130        self.into()
131    }
132}
133
134/// An [`Iterator`] adapter that converts a [`NodeLabelsLender`] into an
135/// iterator of labeled pairs.
136///
137/// This struct is created via the [`From`] trait. It converts a lender that
138/// yields `(usize, IntoIterator)` pairs into a flat iterator of `((src, dst), label)`
139/// labeled pairs, where each `(dst, label)` comes from the inner iterator.
140pub struct IntoLabeledPairs<'a, L: for<'b> NodeLabelsLender<'b, Label: Pair<Left = usize>> + 'a> {
141    lender: Box<L>,
142    current_node: usize,
143    current_iter: Option<LenderIntoIter<'a, L>>,
144    _marker: PhantomData<&'a L>, // That is, L: 'a
145}
146
147impl<'a, L: for<'b> NodeLabelsLender<'b, Label: Pair<Left = usize, Right: Copy>>> Iterator
148    for IntoLabeledPairs<'a, L>
149{
150    type Item = (
151        (usize, usize),
152        <<L as NodeLabelsLender<'a>>::Label as Pair>::Right,
153    );
154
155    fn next(
156        &mut self,
157    ) -> Option<(
158        (usize, usize),
159        <<L as NodeLabelsLender<'a>>::Label as Pair>::Right,
160    )> {
161        loop {
162            if let Some(inner) = &mut self.current_iter {
163                if let Some((dst, label)) = inner.next().map(Pair::into_pair) {
164                    return Some(((self.current_node, dst), label));
165                }
166            }
167            // SAFETY: We use transmute to extend the lifetime of the iterator from the
168            // temporary borrow of `self.lender` to `'a`. This is sound because:
169            // 1. The previous iterator in `current_iter` is dropped before we create a new one
170            // 2. We only call `lender.next()` after the previous iterator is fully consumed
171            // 3. Therefore, at most one iterator borrowed from `lender` exists at any time
172            // 4. The iterator will be dropped before `lender` is dropped (it's in `current_iter`)
173            //
174            // This pattern is necessary because Rust's borrow checker cannot express the
175            // "only one lend alive at a time" invariant that the lending iterator pattern maintains.
176            if let Some((next_node, next_iter)) = self.lender.next().map(|(x, it)| {
177                (x, unsafe {
178                    std::mem::transmute::<LenderIntoIter<'_, L>, LenderIntoIter<'_, L>>(
179                        it.into_iter(),
180                    )
181                })
182            }) {
183                self.current_node = next_node;
184                self.current_iter = Some(next_iter);
185            } else {
186                return None;
187            }
188        }
189    }
190}
191
192impl<'a, L> From<L> for IntoLabeledPairs<'a, L>
193where
194    L: Sized + for<'b> NodeLabelsLender<'b, Label: Pair<Left = usize>>,
195{
196    fn from(lender: L) -> Self {
197        IntoLabeledPairs {
198            lender: Box::new(lender),
199            current_node: 0,
200            current_iter: None,
201            _marker: PhantomData,
202        }
203    }
204}
205
206/// An [`Iterator`] adapter that converts a [`NodeLabelsLender`] into an
207/// iterator of pairs.
208///
209/// This struct is created via the [`From`] trait. It converts a lender that
210/// yields `(usize, IntoIterator)` pairs into a flat iterator of `(src, dst)`
211/// pairs, where each `dst` comes from the inner iterator.
212pub struct IntoPairs<'a, L: for<'b> NodeLabelsLender<'b, Label = usize>> {
213    lender: Box<L>,
214    current_node: usize,
215    current_iter: Option<LenderIntoIter<'a, L>>,
216    _marker: PhantomData<&'a L>, // That is, L: 'a
217}
218
219impl<'a, L: for<'b> NodeLabelsLender<'b, Label = usize>> Iterator for IntoPairs<'a, L> {
220    type Item = (usize, usize);
221
222    fn next(&mut self) -> Option<(usize, usize)> {
223        loop {
224            if let Some(inner) = &mut self.current_iter {
225                if let Some(dst) = inner.next() {
226                    return Some((self.current_node, dst));
227                }
228            }
229            // SAFETY: We use transmute to extend the lifetime of the iterator from the
230            // temporary borrow of `self.lender` to `'a`. This is sound because:
231            // 1. The previous iterator in `current_iter` is dropped before we create a new one
232            // 2. We only call `lender.next()` after the previous iterator is fully consumed
233            // 3. Therefore, at most one iterator borrowed from `lender` exists at any time
234            // 4. The iterator will be dropped before `lender` is dropped (it's in `current_iter`)
235            //
236            // This pattern is necessary because Rust's borrow checker cannot express the
237            // "only one lend alive at a time" invariant that the lending iterator pattern maintains.
238            if let Some((next_node, next_iter)) = self.lender.next().map(|(x, it)| {
239                (x, unsafe {
240                    std::mem::transmute::<LenderIntoIter<'_, L>, LenderIntoIter<'_, L>>(
241                        it.into_iter(),
242                    )
243                })
244            }) {
245                self.current_node = next_node;
246                self.current_iter = Some(next_iter);
247            } else {
248                return None;
249            }
250        }
251    }
252}
253
254impl<'a, L> From<L> for IntoPairs<'a, L>
255where
256    L: Sized + for<'b> NodeLabelsLender<'b, Label = usize>,
257{
258    fn from(lender: L) -> Self {
259        IntoPairs {
260            lender: Box::new(lender),
261            current_node: 0,
262            current_iter: None,
263            _marker: PhantomData,
264        }
265    }
266}
267
268/// Convenience type alias for the associated type `Label` of a [`NodeLabelsLender`].
269pub type LenderLabel<'lend, L> = <L as NodeLabelsLender<'lend>>::Label;
270
271/// Convenience type alias for the associated type `IntoIterator` of a [`NodeLabelsLender`].
272pub type LenderIntoIterator<'lend, L> = <L as NodeLabelsLender<'lend>>::IntoIterator;
273
274/// Convenience type alias for the [`Iterator`] returned by the `IntoIterator`
275/// associated type of a [`NodeLabelsLender`].
276pub type LenderIntoIter<'lend, L> =
277    <<L as NodeLabelsLender<'lend>>::IntoIterator as IntoIterator>::IntoIter;
278
279// Missing implementations for [Cloned, Copied, Owned] because they don't
280// implement Lender but Iterator
281
282impl<'lend, A, B> NodeLabelsLender<'lend> for lender::Chain<A, B>
283where
284    A: Lender + for<'next> NodeLabelsLender<'next>,
285    B: Lender
286        + for<'next> NodeLabelsLender<
287            'next,
288            Label = <A as NodeLabelsLender<'next>>::Label,
289            IntoIterator = <A as NodeLabelsLender<'next>>::IntoIterator,
290        >,
291{
292    type Label = <A as NodeLabelsLender<'lend>>::Label;
293    type IntoIterator = <A as NodeLabelsLender<'lend>>::IntoIterator;
294}
295
296impl<'lend, T> NodeLabelsLender<'lend> for lender::Chunk<'_, T>
297where
298    T: Lender + for<'next> NodeLabelsLender<'next>,
299{
300    type Label = <T as NodeLabelsLender<'lend>>::Label;
301    type IntoIterator = <T as NodeLabelsLender<'lend>>::IntoIterator;
302}
303
304impl<'lend, L> NodeLabelsLender<'lend> for lender::Cycle<L>
305where
306    L: Clone + Lender + for<'next> NodeLabelsLender<'next>,
307{
308    type Label = LenderLabel<'lend, L>;
309    type IntoIterator = <L as NodeLabelsLender<'lend>>::IntoIterator;
310}
311
312impl<Label, II, L> NodeLabelsLender<'_> for lender::Enumerate<L>
313where
314    L: Lender,
315    L: for<'all> Lending<'all, Lend = II>,
316    II: IntoIterator<Item = Label>,
317{
318    type Label = Label;
319    type IntoIterator = II;
320}
321
322impl<'lend, L, P> NodeLabelsLender<'lend> for lender::Filter<L, P>
323where
324    P: for<'next> FnMut(&(usize, <L as NodeLabelsLender<'next>>::IntoIterator)) -> bool,
325    L: Lender + for<'next> NodeLabelsLender<'next>,
326{
327    type Label = LenderLabel<'lend, L>;
328    type IntoIterator = <L as NodeLabelsLender<'lend>>::IntoIterator;
329}
330
331impl<L, F, II> NodeLabelsLender<'_> for lender::FilterMap<L, F>
332where
333    II: IntoIterator,
334    F: for<'all> lender::higher_order::FnMutHKAOpt<'all, Lend<'all, L>, B = (usize, II)>,
335    L: Lender,
336{
337    type Label = II::Item;
338    type IntoIterator = II;
339}
340
341impl<'lend, LL, L, F> NodeLabelsLender<'lend> for lender::FlatMap<'_, LL, F>
342where
343    LL: Lender,
344    L: Lender + for<'next> NodeLabelsLender<'next> + 'lend,
345    F: for<'all> lender::higher_order::FnMutHKA<'all, Lend<'all, LL>, B = L>,
346{
347    type Label = <L as NodeLabelsLender<'lend>>::Label;
348    type IntoIterator = <L as NodeLabelsLender<'lend>>::IntoIterator;
349}
350
351impl<'lend, LL, L> NodeLabelsLender<'lend> for lender::Flatten<'_, LL>
352where
353    LL: Lender<Lend = L>,
354    L: Lender + for<'next> NodeLabelsLender<'next> + 'lend,
355{
356    type Label = <L as NodeLabelsLender<'lend>>::Label;
357    type IntoIterator = <L as NodeLabelsLender<'lend>>::IntoIterator;
358}
359
360impl<'lend, L> NodeLabelsLender<'lend> for lender::Fuse<L>
361where
362    L: Lender + for<'next> NodeLabelsLender<'next>,
363{
364    type Label = LenderLabel<'lend, L>;
365    type IntoIterator = <L as NodeLabelsLender<'lend>>::IntoIterator;
366}
367
368impl<'lend, L, F> NodeLabelsLender<'lend> for lender::Inspect<L, F>
369where
370    F: for<'next> FnMut(&Lend<'next, L>),
371    L: Lender + for<'next> NodeLabelsLender<'next>,
372{
373    type Label = LenderLabel<'lend, L>;
374    type IntoIterator = <L as NodeLabelsLender<'lend>>::IntoIterator;
375}
376
377impl<L, F, II> NodeLabelsLender<'_> for lender::Map<L, F>
378where
379    F: for<'all> lender::higher_order::FnMutHKA<'all, Lend<'all, L>, B = (usize, II)>,
380    II: IntoIterator,
381    L: Lender,
382{
383    type Label = II::Item;
384    type IntoIterator = II;
385}
386
387impl<L, P, II> NodeLabelsLender<'_> for lender::MapWhile<L, P>
388where
389    P: for<'all> lender::higher_order::FnMutHKAOpt<'all, Lend<'all, L>, B = (usize, II)>,
390    II: IntoIterator,
391    L: Lender,
392{
393    type Label = II::Item;
394    type IntoIterator = II;
395}
396
397impl<'lend, L, F> NodeLabelsLender<'lend> for lender::Mutate<L, F>
398where
399    F: FnMut(&mut Lend<'_, L>),
400    L: Lender + for<'next> NodeLabelsLender<'next>,
401{
402    type Label = LenderLabel<'lend, L>;
403    type IntoIterator = <L as NodeLabelsLender<'lend>>::IntoIterator;
404}
405
406impl<'lend, L> NodeLabelsLender<'lend> for lender::Peekable<'_, L>
407where
408    L: Lender + for<'next> NodeLabelsLender<'next>,
409{
410    type Label = LenderLabel<'lend, L>;
411    type IntoIterator = <L as NodeLabelsLender<'lend>>::IntoIterator;
412}
413
414impl<'lend, L> NodeLabelsLender<'lend> for lender::Rev<L>
415where
416    L: Lender + DoubleEndedLender + for<'next> NodeLabelsLender<'next>,
417{
418    type Label = LenderLabel<'lend, L>;
419    type IntoIterator = <L as NodeLabelsLender<'lend>>::IntoIterator;
420}
421
422impl<L, St, F, II> NodeLabelsLender<'_> for lender::Scan<L, St, F>
423where
424    for<'all> F:
425        lender::higher_order::FnMutHKAOpt<'all, (&'all mut St, Lend<'all, L>), B = (usize, II)>,
426    L: Lender,
427    II: IntoIterator,
428{
429    type Label = II::Item;
430    type IntoIterator = II;
431}
432
433impl<'lend, L> NodeLabelsLender<'lend> for lender::Skip<L>
434where
435    L: Lender + for<'next> NodeLabelsLender<'next>,
436{
437    type Label = LenderLabel<'lend, L>;
438    type IntoIterator = <L as NodeLabelsLender<'lend>>::IntoIterator;
439}
440
441impl<'lend, L, P> NodeLabelsLender<'lend> for lender::SkipWhile<L, P>
442where
443    L: Lender + for<'next> NodeLabelsLender<'next>,
444    P: for<'next> FnMut(&Lend<'next, L>) -> bool,
445{
446    type Label = LenderLabel<'lend, L>;
447    type IntoIterator = <L as NodeLabelsLender<'lend>>::IntoIterator;
448}
449
450impl<'lend, L> NodeLabelsLender<'lend> for lender::StepBy<L>
451where
452    L: Lender + for<'next> NodeLabelsLender<'next>,
453{
454    type Label = LenderLabel<'lend, L>;
455    type IntoIterator = <L as NodeLabelsLender<'lend>>::IntoIterator;
456}
457
458impl<'lend, L> NodeLabelsLender<'lend> for lender::Take<L>
459where
460    L: Lender + for<'next> NodeLabelsLender<'next>,
461{
462    type Label = LenderLabel<'lend, L>;
463    type IntoIterator = <L as NodeLabelsLender<'lend>>::IntoIterator;
464}
465
466impl<'lend, L, P> NodeLabelsLender<'lend> for lender::TakeWhile<L, P>
467where
468    L: Lender + for<'next> NodeLabelsLender<'next>,
469    P: FnMut(&Lend<'_, L>) -> bool,
470{
471    type Label = LenderLabel<'lend, L>;
472    type IntoIterator = <L as NodeLabelsLender<'lend>>::IntoIterator;
473}
474
475impl<A, B, II> NodeLabelsLender<'_> for lender::Zip<A, B>
476where
477    A: Lender + for<'next> Lending<'next, Lend = usize>,
478    B: Lender + for<'next> Lending<'next, Lend = II>,
479    II: IntoIterator,
480{
481    type Label = II::Item;
482    type IntoIterator = II;
483}
484
485impl<I, J> NodeLabelsLender<'_> for lender::FromIter<I>
486where
487    I: Iterator<Item = (usize, J)>,
488    J: IntoIterator,
489{
490    type Label = J::Item;
491    type IntoIterator = J;
492}
493
494impl<S, F, J> NodeLabelsLender<'_> for lender::FromFn<S, F>
495where
496    F: for<'all> lender::higher_order::FnMutHKAOpt<'all, &'all mut S, B = (usize, J)>,
497    J: IntoIterator,
498{
499    type Label = J::Item;
500    type IntoIterator = J;
501}
webgraph/traits/lenders.rs

webgraph/traits/
lenders.rs
