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<L: for<'b> NodeLabelsLender<'b, Label: Pair<Left = usize>>> std::fmt::Debug
148    for IntoLabeledPairs<'_, L>
149{
150    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
151        f.debug_struct("IntoLabeledPairs")
152            .field("current_node", &self.current_node)
153            .finish_non_exhaustive()
154    }
155}
156
157impl<'a, L: for<'b> NodeLabelsLender<'b, Label: Pair<Left = usize, Right: Copy>>> Iterator
158    for IntoLabeledPairs<'a, L>
159{
160    type Item = (
161        (usize, usize),
162        <<L as NodeLabelsLender<'a>>::Label as Pair>::Right,
163    );
164
165    fn next(
166        &mut self,
167    ) -> Option<(
168        (usize, usize),
169        <<L as NodeLabelsLender<'a>>::Label as Pair>::Right,
170    )> {
171        loop {
172            if let Some(inner) = &mut self.current_iter {
173                if let Some((dst, label)) = inner.next().map(Pair::into_pair) {
174                    return Some(((self.current_node, dst), label));
175                }
176            }
177            // SAFETY: We use transmute to extend the lifetime of the iterator from the
178            // temporary borrow of `self.lender` to `'a`. This is sound because:
179            // 1. The previous iterator in `current_iter` is dropped before we create a new one
180            // 2. We only call `lender.next()` after the previous iterator is fully consumed
181            // 3. Therefore, at most one iterator borrowed from `lender` exists at any time
182            // 4. The iterator will be dropped before `lender` is dropped (it's in `current_iter`)
183            //
184            // This pattern is necessary because Rust's borrow checker cannot express the
185            // "only one lend alive at a time" invariant that the lending iterator pattern maintains.
186            if let Some((next_node, next_iter)) = self.lender.next().map(|(x, it)| {
187                (x, unsafe {
188                    std::mem::transmute::<LenderIntoIter<'_, L>, LenderIntoIter<'_, L>>(
189                        it.into_iter(),
190                    )
191                })
192            }) {
193                self.current_node = next_node;
194                self.current_iter = Some(next_iter);
195            } else {
196                return None;
197            }
198        }
199    }
200}
201
202impl<'a, L> From<L> for IntoLabeledPairs<'a, L>
203where
204    L: Sized + for<'b> NodeLabelsLender<'b, Label: Pair<Left = usize>>,
205{
206    fn from(lender: L) -> Self {
207        IntoLabeledPairs {
208            lender: Box::new(lender),
209            current_node: 0,
210            current_iter: None,
211            _marker: PhantomData,
212        }
213    }
214}
215
216/// An [`Iterator`] adapter that converts a [`NodeLabelsLender`] into an
217/// iterator of pairs.
218///
219/// This struct is created via the [`From`] trait. It converts a lender that
220/// yields `(usize, IntoIterator)` pairs into a flat iterator of `(src, dst)`
221/// pairs, where each `dst` comes from the inner iterator.
222pub struct IntoPairs<'a, L: for<'b> NodeLabelsLender<'b, Label = usize>> {
223    lender: Box<L>,
224    current_node: usize,
225    current_iter: Option<LenderIntoIter<'a, L>>,
226    _marker: PhantomData<&'a L>, // That is, L: 'a
227}
228
229impl<'a, L: for<'b> NodeLabelsLender<'b, Label = usize>> Iterator for IntoPairs<'a, L> {
230    type Item = (usize, usize);
231
232    fn next(&mut self) -> Option<(usize, usize)> {
233        loop {
234            if let Some(inner) = &mut self.current_iter {
235                if let Some(dst) = inner.next() {
236                    return Some((self.current_node, dst));
237                }
238            }
239            // SAFETY: We use transmute to extend the lifetime of the iterator from the
240            // temporary borrow of `self.lender` to `'a`. This is sound because:
241            // 1. The previous iterator in `current_iter` is dropped before we create a new one
242            // 2. We only call `lender.next()` after the previous iterator is fully consumed
243            // 3. Therefore, at most one iterator borrowed from `lender` exists at any time
244            // 4. The iterator will be dropped before `lender` is dropped (it's in `current_iter`)
245            //
246            // This pattern is necessary because Rust's borrow checker cannot express the
247            // "only one lend alive at a time" invariant that the lending iterator pattern maintains.
248            if let Some((next_node, next_iter)) = self.lender.next().map(|(x, it)| {
249                (x, unsafe {
250                    std::mem::transmute::<LenderIntoIter<'_, L>, LenderIntoIter<'_, L>>(
251                        it.into_iter(),
252                    )
253                })
254            }) {
255                self.current_node = next_node;
256                self.current_iter = Some(next_iter);
257            } else {
258                return None;
259            }
260        }
261    }
262}
263
264impl<'a, L> From<L> for IntoPairs<'a, L>
265where
266    L: Sized + for<'b> NodeLabelsLender<'b, Label = usize>,
267{
268    fn from(lender: L) -> Self {
269        IntoPairs {
270            lender: Box::new(lender),
271            current_node: 0,
272            current_iter: None,
273            _marker: PhantomData,
274        }
275    }
276}
277
278/// Convenience type alias for the associated type `Label` of a [`NodeLabelsLender`].
279pub type LenderLabel<'lend, L> = <L as NodeLabelsLender<'lend>>::Label;
280
281/// Convenience type alias for the associated type `IntoIterator` of a [`NodeLabelsLender`].
282pub type LenderIntoIterator<'lend, L> = <L as NodeLabelsLender<'lend>>::IntoIterator;
283
284/// Convenience type alias for the [`Iterator`] returned by the `IntoIterator`
285/// associated type of a [`NodeLabelsLender`].
286pub type LenderIntoIter<'lend, L> =
287    <<L as NodeLabelsLender<'lend>>::IntoIterator as IntoIterator>::IntoIter;
288
289// Missing implementations for [Cloned, Copied, Owned] because they don't
290// implement Lender but Iterator
291
292impl<'lend, A, B> NodeLabelsLender<'lend> for lender::Chain<A, B>
293where
294    A: Lender + for<'next> NodeLabelsLender<'next>,
295    B: Lender
296        + for<'next> NodeLabelsLender<
297            'next,
298            Label = <A as NodeLabelsLender<'next>>::Label,
299            IntoIterator = <A as NodeLabelsLender<'next>>::IntoIterator,
300        >,
301{
302    type Label = <A as NodeLabelsLender<'lend>>::Label;
303    type IntoIterator = <A as NodeLabelsLender<'lend>>::IntoIterator;
304}
305
306impl<'lend, T> NodeLabelsLender<'lend> for lender::Chunk<'_, T>
307where
308    T: Lender + for<'next> NodeLabelsLender<'next>,
309{
310    type Label = <T as NodeLabelsLender<'lend>>::Label;
311    type IntoIterator = <T as NodeLabelsLender<'lend>>::IntoIterator;
312}
313
314impl<'lend, L> NodeLabelsLender<'lend> for lender::Cycle<L>
315where
316    L: Clone + Lender + for<'next> NodeLabelsLender<'next>,
317{
318    type Label = LenderLabel<'lend, L>;
319    type IntoIterator = <L as NodeLabelsLender<'lend>>::IntoIterator;
320}
321
322impl<Label, II, L> NodeLabelsLender<'_> for lender::Enumerate<L>
323where
324    L: Lender,
325    L: for<'all> Lending<'all, Lend = II>,
326    II: IntoIterator<Item = Label>,
327{
328    type Label = Label;
329    type IntoIterator = II;
330}
331
332impl<'lend, L, P> NodeLabelsLender<'lend> for lender::Filter<L, P>
333where
334    P: for<'next> FnMut(&(usize, <L as NodeLabelsLender<'next>>::IntoIterator)) -> bool,
335    L: Lender + for<'next> NodeLabelsLender<'next>,
336{
337    type Label = LenderLabel<'lend, L>;
338    type IntoIterator = <L as NodeLabelsLender<'lend>>::IntoIterator;
339}
340
341impl<L, F, II> NodeLabelsLender<'_> for lender::FilterMap<L, F>
342where
343    II: IntoIterator,
344    F: for<'all> lender::higher_order::FnMutHKAOpt<'all, Lend<'all, L>, B = (usize, II)>,
345    L: Lender,
346{
347    type Label = II::Item;
348    type IntoIterator = II;
349}
350
351impl<'lend, LL, L, F> NodeLabelsLender<'lend> for lender::FlatMap<'_, LL, F>
352where
353    LL: Lender,
354    L: Lender + for<'next> NodeLabelsLender<'next> + 'lend,
355    F: for<'all> lender::higher_order::FnMutHKA<'all, Lend<'all, LL>, B = L>,
356{
357    type Label = <L as NodeLabelsLender<'lend>>::Label;
358    type IntoIterator = <L as NodeLabelsLender<'lend>>::IntoIterator;
359}
360
361impl<'lend, LL, L> NodeLabelsLender<'lend> for lender::Flatten<'_, LL>
362where
363    LL: Lender<Lend = L>,
364    L: Lender + for<'next> NodeLabelsLender<'next> + 'lend,
365{
366    type Label = <L as NodeLabelsLender<'lend>>::Label;
367    type IntoIterator = <L as NodeLabelsLender<'lend>>::IntoIterator;
368}
369
370impl<'lend, L> NodeLabelsLender<'lend> for lender::Fuse<L>
371where
372    L: Lender + for<'next> NodeLabelsLender<'next>,
373{
374    type Label = LenderLabel<'lend, L>;
375    type IntoIterator = <L as NodeLabelsLender<'lend>>::IntoIterator;
376}
377
378impl<'lend, L, F> NodeLabelsLender<'lend> for lender::Inspect<L, F>
379where
380    F: for<'next> FnMut(&Lend<'next, L>),
381    L: Lender + for<'next> NodeLabelsLender<'next>,
382{
383    type Label = LenderLabel<'lend, L>;
384    type IntoIterator = <L as NodeLabelsLender<'lend>>::IntoIterator;
385}
386
387impl<L, F, II> NodeLabelsLender<'_> for lender::Map<L, F>
388where
389    F: for<'all> lender::higher_order::FnMutHKA<'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<L, P, II> NodeLabelsLender<'_> for lender::MapWhile<L, P>
398where
399    P: for<'all> lender::higher_order::FnMutHKAOpt<'all, Lend<'all, L>, B = (usize, II)>,
400    II: IntoIterator,
401    L: Lender,
402{
403    type Label = II::Item;
404    type IntoIterator = II;
405}
406
407impl<'lend, L, F> NodeLabelsLender<'lend> for lender::Mutate<L, F>
408where
409    F: FnMut(&mut Lend<'_, L>),
410    L: Lender + for<'next> NodeLabelsLender<'next>,
411{
412    type Label = LenderLabel<'lend, L>;
413    type IntoIterator = <L as NodeLabelsLender<'lend>>::IntoIterator;
414}
415
416impl<'lend, L> NodeLabelsLender<'lend> for lender::Peekable<'_, L>
417where
418    L: Lender + for<'next> NodeLabelsLender<'next>,
419{
420    type Label = LenderLabel<'lend, L>;
421    type IntoIterator = <L as NodeLabelsLender<'lend>>::IntoIterator;
422}
423
424impl<'lend, L> NodeLabelsLender<'lend> for lender::Rev<L>
425where
426    L: Lender + DoubleEndedLender + for<'next> NodeLabelsLender<'next>,
427{
428    type Label = LenderLabel<'lend, L>;
429    type IntoIterator = <L as NodeLabelsLender<'lend>>::IntoIterator;
430}
431
432impl<L, St, F, II> NodeLabelsLender<'_> for lender::Scan<L, St, F>
433where
434    for<'all> F:
435        lender::higher_order::FnMutHKAOpt<'all, (&'all mut St, Lend<'all, L>), B = (usize, II)>,
436    L: Lender,
437    II: IntoIterator,
438{
439    type Label = II::Item;
440    type IntoIterator = II;
441}
442
443impl<'lend, L> NodeLabelsLender<'lend> for lender::Skip<L>
444where
445    L: Lender + for<'next> NodeLabelsLender<'next>,
446{
447    type Label = LenderLabel<'lend, L>;
448    type IntoIterator = <L as NodeLabelsLender<'lend>>::IntoIterator;
449}
450
451impl<'lend, L, P> NodeLabelsLender<'lend> for lender::SkipWhile<L, P>
452where
453    L: Lender + for<'next> NodeLabelsLender<'next>,
454    P: for<'next> FnMut(&Lend<'next, L>) -> bool,
455{
456    type Label = LenderLabel<'lend, L>;
457    type IntoIterator = <L as NodeLabelsLender<'lend>>::IntoIterator;
458}
459
460impl<'lend, L> NodeLabelsLender<'lend> for lender::StepBy<L>
461where
462    L: Lender + for<'next> NodeLabelsLender<'next>,
463{
464    type Label = LenderLabel<'lend, L>;
465    type IntoIterator = <L as NodeLabelsLender<'lend>>::IntoIterator;
466}
467
468impl<'lend, L> NodeLabelsLender<'lend> for lender::Take<L>
469where
470    L: Lender + for<'next> NodeLabelsLender<'next>,
471{
472    type Label = LenderLabel<'lend, L>;
473    type IntoIterator = <L as NodeLabelsLender<'lend>>::IntoIterator;
474}
475
476impl<'lend, L, P> NodeLabelsLender<'lend> for lender::TakeWhile<L, P>
477where
478    L: Lender + for<'next> NodeLabelsLender<'next>,
479    P: FnMut(&Lend<'_, L>) -> bool,
480{
481    type Label = LenderLabel<'lend, L>;
482    type IntoIterator = <L as NodeLabelsLender<'lend>>::IntoIterator;
483}
484
485impl<A, B, II> NodeLabelsLender<'_> for lender::Zip<A, B>
486where
487    A: Lender + for<'next> Lending<'next, Lend = usize>,
488    B: Lender + for<'next> Lending<'next, Lend = II>,
489    II: IntoIterator,
490{
491    type Label = II::Item;
492    type IntoIterator = II;
493}
494
495impl<I, J> NodeLabelsLender<'_> for lender::FromIter<I>
496where
497    I: Iterator<Item = (usize, J)>,
498    J: IntoIterator,
499{
500    type Label = J::Item;
501    type IntoIterator = J;
502}
503
504impl<S, F, J> NodeLabelsLender<'_> for lender::FromFn<S, F>
505where
506    F: for<'all> lender::higher_order::FnMutHKAOpt<'all, &'all mut S, B = (usize, J)>,
507    J: IntoIterator,
508{
509    type Label = J::Item;
510    type IntoIterator = J;
511}
webgraph/traits/lenders.rs

webgraph/traits/
lenders.rs
