swh_graph_stdlib/

lib.rs

// Copyright (C) 2024-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

//! Standard library to work on Software Heritage compressed graph in Rust

use anyhow::{Result, bail, ensure};

use swh_graph::graph::*;
use swh_graph::labels::{EdgeLabel, VisitStatus};
use swh_graph::{NodeConstraint, NodeType, properties};

/// Given a graph and an origin node in it, return the node id and timestamp
/// (as a number of seconds since Epoch) of the most recent snapshot of that
/// origin, if it exists.
///
/// Note: only visit with status `Full` are considered when selecting
/// snapshots.
pub fn find_latest_snp<G>(graph: &G, ori: NodeId) -> Result<Option<(NodeId, u64)>>
where
    G: SwhLabeledForwardGraph + SwhGraphWithProperties,
    <G as SwhGraphWithProperties>::Maps: properties::Maps,
{
    let props = graph.properties();
    let node_type = props.node_type(ori);
    ensure!(
        node_type == NodeType::Origin,
        "Cannot find latest snapshot of {}: not an origin",
        graph.properties().swhid(ori),
    );
    // Most recent snapshot thus far, as an optional (node_id, timestamp) pair
    let mut latest_snp: Option<(usize, u64)> = None;
    for (succ, labels) in graph.labeled_successors(ori) {
        let node_type = props.node_type(succ);
        if node_type != NodeType::Snapshot {
            continue;
        }
        for label in labels {
            if let EdgeLabel::Visit(visit) = label {
                if visit.status() != VisitStatus::Full {
                    continue;
                }
                let ts = visit.timestamp();
                if let Some((_cur_snp, cur_ts)) = latest_snp {
                    if ts > cur_ts {
                        latest_snp = Some((succ, ts))
                    }
                } else {
                    latest_snp = Some((succ, ts))
                }
            }
        }
    }
    Ok(latest_snp)
}

/// Peel a node once, following the natural SWH object model.
///
/// The peeling rules are:
///
/// - Origin → first snapshot successor
///
/// - Snapshot → HEAD revision (as per [vcs::find_head_rev]) if it exists, first revision or release
///   successor if not
///
/// - Release → follows release target (first successor of any kind)
///
/// - Revision → follows root directory successor
///
/// - Directory and Content cannot be peeled further (error)
///
/// Returns `Ok(Some(node_id))` on success, `Ok(None)` if no suitable successor exists.
pub fn peel_once<G>(graph: &G, node: NodeId) -> Result<Option<NodeId>>
where
    G: SwhLabeledForwardGraph + SwhGraphWithProperties,
    <G as SwhGraphWithProperties>::LabelNames: properties::LabelNames,
    <G as SwhGraphWithProperties>::Maps: properties::Maps,
{
    ensure!(!graph.is_transposed(), "Cannot peel on a transposed graph.");
    let props = graph.properties();
    let source_type = props.node_type(node);

    match source_type {
        NodeType::Content | NodeType::Directory => {
            bail!("Cannot peel nodes of type {source_type}");
        }
        NodeType::Revision => {
            for succ in graph.successors(node) {
                if props.node_type(succ) == NodeType::Directory {
                    return Ok(Some(succ));
                }
            }
            Ok(None)
        }
        NodeType::Release => {
            if let Some(succ) = graph.successors(node).into_iter().next() {
                return Ok(Some(succ));
            }
            Ok(None)
        }
        NodeType::Snapshot => {
            if let Ok(Some(succ)) = vcs::find_head_rev(&graph, node) {
                Ok(Some(succ))
            } else {
                for succ in graph.successors(node) {
                    let t = props.node_type(succ);
                    if t == NodeType::Revision || t == NodeType::Release {
                        return Ok(Some(succ));
                    }
                }
                Ok(None)
            }
        }
        NodeType::Origin => {
            find_latest_snp(&graph, node).map(|opt_node| opt_node.map(|(node, _ts)| node))
        }
    }
}

/// Recursively peel a [Release](NodeType::Release) node, following its target, until a node of a
/// different type is reached.
///
/// A release is peeled by following its target, i.e. its first successor of any kind (see
/// [`peel_once`]); chains of releases (e.g. an annotated tag pointing to another tag) are followed
/// transitively. A non-release `node` is returned unchanged.
///
/// Unlike [`peel`] and [`peel_once`], this only deals with release nodes and therefore needs
/// narrower trait bounds: in particular it does not need the [LabelNames](properties::LabelNames)
/// property, since (unlike snapshot peeling) it never has to resolve a HEAD branch by name.
///
/// Returns `Ok(Some(node_id))` on success, where `node_id` is the (non-release) peel result, or
/// `Ok(None)` if a release with no successor is reached (a dangling target).
pub fn peel_rel<G>(graph: &G, node: NodeId) -> Result<Option<NodeId>>
where
    G: SwhForwardGraph + SwhGraphWithProperties,
    <G as SwhGraphWithProperties>::Maps: properties::Maps,
{
    ensure!(!graph.is_transposed(), "Cannot peel on a transposed graph.");
    let props = graph.properties();

    let mut current = node;
    while props.node_type(current) == NodeType::Release {
        match graph.successors(current).into_iter().next() {
            Some(succ) => current = succ,
            None => return Ok(None),
        }
    }

    Ok(Some(current))
}

/// Recursively peel a node until a node of a different type is reached.
///
/// This is analogous to libgit2's
/// [`git_object_peel`](https://libgit2.org/docs/reference/main/object/git_object_peel.html)
/// with `GIT_OBJECT_ANY`.
///
/// See [`peel_once`] for peeling rules.
///
/// Returns `Ok(Some(node_id))` on success, where `node_id` is the peel result, `Ok(None)` if no
/// suitable successor exists (e.g., a root revision with no directory successor).
pub fn peel<G>(graph: &G, node: NodeId) -> Result<Option<NodeId>>
where
    G: SwhLabeledForwardGraph + SwhGraphWithProperties,
    <G as SwhGraphWithProperties>::LabelNames: properties::LabelNames,
    <G as SwhGraphWithProperties>::Maps: properties::Maps,
{
    let props = graph.properties();
    let source_type = props.node_type(node);

    let mut current = node;
    while props.node_type(current) == source_type {
        match peel_once(graph, current)? {
            Some(next) => current = next,
            None => return Ok(None),
        }
    }

    Ok(Some(current))
}

/// Recursively peel a node until a node with a type matching the specified constraint is reached.
///
/// This is analogous to libgit2's
/// [`git_object_peel`](https://libgit2.org/docs/reference/main/object/git_object_peel.html).
///
/// See [`peel_once`] for peeling rules.
///
/// See [`peel`] to peel to any type that is different from `node`'s
/// (analogous to `GIT_OBJECT_ANY`)
///
/// Returns `Ok(Some(node_id))` on success, where `node_id` is the peel result, `Ok(None)` if no
/// suitable successor exists (e.g., a root revision with no directory successor).
pub fn peel_until<G>(graph: &G, node: NodeId, target_type: NodeConstraint) -> Result<Option<NodeId>>
where
    G: SwhLabeledForwardGraph + SwhGraphWithProperties,
    <G as SwhGraphWithProperties>::LabelNames: properties::LabelNames,
    <G as SwhGraphWithProperties>::Maps: properties::Maps,
{
    let props = graph.properties();
    let source_type = props.node_type(node);

    // If we already are the target type, return immediately
    if target_type.matches(source_type) {
        return Ok(Some(node));
    }

    // Peel once
    let Some(mut current) = peel_once(graph, node)? else {
        return Ok(None);
    };

    loop {
        let current_type = props.node_type(current);
        if target_type.matches(current_type) {
            return Ok(Some(current));
        }
        if current_type == NodeType::Release || current_type == NodeType::Revision {
            // Continue peeling through releases or revision
            match peel_once(graph, current)? {
                Some(next) => current = next,
                None => return Ok(None),
            }
        } else {
            bail!("Cannot peel to {target_type}: stuck at node {current} of type {current_type}");
        }
    }
}

pub mod collections;
pub mod connectivity;
pub mod diff;
pub mod fs;
pub mod io;
pub mod labeling;
pub mod origins;
#[cfg(feature = "unstable_project_ids")]
pub mod project_ids;
mod root_directory;
pub use root_directory::find_root_dir;
pub mod vcs;
mod visit;
pub use visit::*;

pub use deprecated::*;

#[allow(deprecated)]
mod deprecated {
    use std::collections::HashMap;
    use swh_graph::labels::{LabelNameId, Permission};

    use super::*;

    #[doc(hidden)]
    #[deprecated(since = "10.3.0", note = "use swh_graph_stdlib::vcs::HEAD_REF_NAMES")]
    pub const HEAD_REF_NAMES: [&str; 2] = vcs::HEAD_REF_NAMES;

    #[doc(hidden)]
    #[deprecated(since = "10.3.0", note = "use swh_graph_stdlib::vcs::find_head_rev")]
    pub fn find_head_rev<G>(graph: &G, snp: NodeId) -> Result<Option<NodeId>>
    where
        G: SwhLabeledForwardGraph + SwhGraphWithProperties,
        <G as SwhGraphWithProperties>::LabelNames: properties::LabelNames,
        <G as SwhGraphWithProperties>::Maps: properties::Maps,
    {
        vcs::find_head_rev(graph, snp)
    }

    #[doc(hidden)]
    #[deprecated(
        since = "10.3.0",
        note = "use swh_graph_stdlib::vcs::find_head_rev_by_refs"
    )]
    pub fn find_head_rev_by_refs<G>(
        graph: &G,
        snp: NodeId,
        ref_name_ids: &[LabelNameId],
    ) -> Result<Option<NodeId>>
    where
        G: SwhLabeledForwardGraph + SwhGraphWithProperties,
        <G as SwhGraphWithProperties>::Maps: properties::Maps,
        <G as SwhGraphWithProperties>::LabelNames: properties::LabelNames,
    {
        vcs::find_head_rev_by_refs(graph, snp, ref_name_ids)
    }

    #[doc(hidden)]
    #[deprecated(since = "10.3.0", note = "use swh_graph_stdlib::fs::FsTree")]
    #[derive(Debug, Default, PartialEq)]
    pub enum FsTree {
        #[default]
        Content,
        Directory(HashMap<Vec<u8>, (FsTree, Option<Permission>)>),
        Revision(NodeId),
    }

    impl From<fs::FsTree> for FsTree {
        fn from(tree: fs::FsTree) -> Self {
            match tree {
                fs::FsTree::Content => FsTree::Content,
                fs::FsTree::Directory(entries) => FsTree::Directory(
                    entries
                        .into_iter()
                        .map(|(name, (tree, perm))| (name, (tree.into(), perm)))
                        .collect(),
                ),
                fs::FsTree::Revision(rev) => FsTree::Revision(rev),
            }
        }
    }

    #[doc(hidden)]
    #[deprecated(since = "10.3.0", note = "use swh_graph_stdlib::fs::resolve_name")]
    pub fn fs_resolve_name<G>(
        graph: &G,
        dir: NodeId,
        name: impl AsRef<[u8]>,
    ) -> Result<Option<NodeId>>
    where
        G: SwhLabeledForwardGraph + SwhGraphWithProperties,
        <G as SwhGraphWithProperties>::LabelNames: properties::LabelNames,
        <G as SwhGraphWithProperties>::Maps: properties::Maps,
    {
        fs::resolve_name(graph, dir, name)
    }

    pub fn fs_resolve_name_by_id<G>(
        graph: &G,
        dir: NodeId,
        name: LabelNameId,
    ) -> Result<Option<NodeId>>
    where
        G: SwhLabeledForwardGraph + SwhGraphWithProperties,
        <G as SwhGraphWithProperties>::Maps: properties::Maps,
    {
        fs::resolve_name_by_id(graph, dir, name)
    }

    #[doc(hidden)]
    #[deprecated(since = "10.3.0", note = "use swh_graph_stdlib::fs::resolve_path")]
    pub fn fs_resolve_path<G>(
        graph: &G,
        dir: NodeId,
        path: impl AsRef<[u8]>,
    ) -> Result<Option<NodeId>>
    where
        G: SwhLabeledForwardGraph + SwhGraphWithProperties,
        <G as SwhGraphWithProperties>::LabelNames: properties::LabelNames,
        <G as SwhGraphWithProperties>::Maps: properties::Maps,
    {
        fs::resolve_path(graph, dir, path)
    }

    #[doc(hidden)]
    #[deprecated(
        since = "10.3.0",
        note = "use swh_graph_stdlib::fs::resolve_path_by_id"
    )]
    pub fn fs_resolve_path_by_id<G>(
        graph: &G,
        dir: NodeId,
        path: &[LabelNameId],
    ) -> Result<Option<NodeId>>
    where
        G: SwhLabeledForwardGraph + SwhGraphWithProperties,
        <G as SwhGraphWithProperties>::Maps: properties::Maps,
    {
        fs::resolve_path_by_id(graph, dir, path)
    }

    #[doc(hidden)]
    #[deprecated(since = "10.3.0", note = "use swh_graph_stdlib::fs::ls_tree")]
    pub fn fs_ls_tree<G>(graph: &G, dir: NodeId) -> Result<FsTree>
    where
        G: SwhLabeledForwardGraph + SwhGraphWithProperties,
        <G as SwhGraphWithProperties>::LabelNames: properties::LabelNames,
        <G as SwhGraphWithProperties>::Maps: properties::Maps,
    {
        fs::ls_tree(graph, dir).map(Into::into)
    }
}