swh_graph_stdlib/labeling/
mod.rs

1// Copyright (C) 2026  The Software Heritage developers
2// See the AUTHORS file at the top-level directory of this distribution
3// License: GNU General Public License version 3, or any later version
4// See top-level LICENSE file for more information
5
6//! Associate information to a subset of nodes
7
8use std::borrow::Borrow;
9
10use crate::NodeId;
11
12mod labels;
13pub use labels::*;
14mod map_reduce;
15pub use map_reduce::*;
16
17/// Callbacks for [`MapReduce`]
18pub trait MapReducer {
19    type Label: ToOwned + ?Sized;
20    type Error;
21
22    /// Returns the label to assign to the given node, independently of its successors, if any
23    fn map(&mut self, node: NodeId)
24    -> Result<Option<<Self::Label as ToOwned>::Owned>, Self::Error>;
25
26    /// Given the labels of the children of a node, merge them into a single label.
27    ///
28    /// Not guaranteed to be called for every node.
29    fn reduce<'a, I: Iterator<Item = &'a Self::Label>>(
30        &mut self,
31        first_label: <Self::Label as ToOwned>::Owned,
32        other_labels: I,
33    ) -> Result<Option<<Self::Label as ToOwned>::Owned>, Self::Error>
34    where
35        Self::Label: 'a;
36
37    /// Special-case of [`Self::reduce`] for merging a node's label with its successors' label
38    ///
39    /// Defaults to calling [`Self::map`] then [`Self::reduce`].
40    /// Specialized implementations must have an equivalent implementation (which may be
41    /// optimized), as there is no guarantee which is called by [`MapReduce`].
42    ///
43    /// Not guaranteed to be called for every node.
44    fn map_reduce(
45        &mut self,
46        node: NodeId,
47        successors_label: <Self::Label as ToOwned>::Owned,
48    ) -> Result<Option<<Self::Label as ToOwned>::Owned>, Self::Error> {
49        match self.map(node)? {
50            Some(own_label) => self.reduce(own_label, [successors_label.borrow()].into_iter()),
51            None => Ok(Some(successors_label)),
52        }
53    }
54
55    /// Called once a node's initial label was computed and merged with its successors'
56    ///
57    /// Defaults to no-op.
58    fn on_node_traversed(
59        &mut self,
60        _node: NodeId,
61        _label: Option<&Self::Label>,
62    ) -> Result<(), Self::Error> {
63        Ok(())
64    }
65}
swh_graph_stdlib/labeling/mod.rs

swh_graph_stdlib/labeling/
mod.rs
