swh-graph-stdlib 13.0.0

// Copyright (C) 2026  The Software Heritage developers
// See the AUTHORS file at the top-level directory of this distribution
// License: GNU General Public License version 3, or any later version
// See top-level LICENSE file for more information

//! Associate information to a subset of nodes

use std::borrow::Borrow;

use crate::NodeId;

mod labels;
pub use labels::*;
mod map_reduce;
pub use map_reduce::*;

/// Callbacks for [`MapReduce`]
pub trait MapReducer {
    type Label: ToOwned + ?Sized;
    type Error;

    /// Returns the label to assign to the given node, independently of its successors, if any
    fn map(&mut self, node: NodeId)
    -> Result<Option<<Self::Label as ToOwned>::Owned>, Self::Error>;

    /// Given the labels of the children of a node, merge them into a single label.
    ///
    /// Not guaranteed to be called for every node.
    fn reduce<'a, I: Iterator<Item = &'a Self::Label>>(
        &mut self,
        first_label: <Self::Label as ToOwned>::Owned,
        other_labels: I,
    ) -> Result<Option<<Self::Label as ToOwned>::Owned>, Self::Error>
    where
        Self::Label: 'a;

    /// Special-case of [`Self::reduce`] for merging a node's label with its successors' label
    ///
    /// Defaults to calling [`Self::map`] then [`Self::reduce`].
    /// Specialized implementations must have an equivalent implementation (which may be
    /// optimized), as there is no guarantee which is called by [`MapReduce`].
    ///
    /// Not guaranteed to be called for every node.
    fn map_reduce(
        &mut self,
        node: NodeId,
        successors_label: <Self::Label as ToOwned>::Owned,
    ) -> Result<Option<<Self::Label as ToOwned>::Owned>, Self::Error> {
        match self.map(node)? {
            Some(own_label) => self.reduce(own_label, [successors_label.borrow()].into_iter()),
            None => Ok(Some(successors_label)),
        }
    }

    /// Called once a node's initial label was computed and merged with its successors'
    ///
    /// Defaults to no-op.
    fn on_node_traversed(
        &mut self,
        _node: NodeId,
        _label: Option<&Self::Label>,
    ) -> Result<(), Self::Error> {
        Ok(())
    }
}