swh_graph_stdlib/

vcs.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

//! Version control system (VCS) functions.

use std::collections::VecDeque;

use anyhow::{Result, ensure};
use dsi_progress_logger::{ProgressLog, concurrent_progress_logger};
use rayon::prelude::*;

use swh_graph::graph::*;
use swh_graph::labels::{EdgeLabel, LabelNameId};
use swh_graph::properties;
use swh_graph::views::Subgraph;
use swh_graph::{NodeConstraint, NodeType};

use crate::collections::{AdaptiveNodeSet, NodeSet, ReadNodeSet};
use crate::{iter_nodes, peel_rel};

/// Names of references ("branches") that are considered to be pointing to the
/// HEAD revision in a VCS, by [find_head_rev] below. Names are tried in order,
/// when attempting to identify the HEAD revision.
pub const HEAD_REF_NAMES: [&str; 2] = ["refs/heads/main", "refs/heads/master"];

/// Given a graph and a snapshot node in it, return the node id of the revision
/// pointed by the HEAD branch, if it exists.
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,
{
    let props = graph.properties();
    let head_ref_name_ids: Vec<LabelNameId> = HEAD_REF_NAMES
        .into_iter()
        .filter_map(|name| props.label_name_id(name.as_bytes()).ok())
        // Note, we ignore errors on purpose here, because some ref names that
        // do exist on the SWH graph might be missing in user-provided graphs,
        // and will fail [label_name_id] call.
        .collect();
    find_head_rev_by_refs(graph, snp, &head_ref_name_ids)
}

/// Same as [find_head_rev], but with the ability to configure which branch
/// names correspond to the HEAD revision.
///
/// Note: this function is also more efficient than [find_head_rev], because
/// branch names are pre-resolved to integers once (before calling this
/// function) and compared as integers.  See the source code of [find_head_rev]
/// for an example of how to translate a given set of branch names (like
/// [HEAD_REF_NAMES]) to label-name IDs for this function.
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,
{
    let props = graph.properties();
    let node_type = props.node_type(snp);
    ensure!(
        node_type == NodeType::Snapshot,
        "Cannot find head revision of {}: not a snapshot",
        graph.properties().swhid(snp),
    );
    for (succ, labels) in graph.labeled_successors(snp) {
        let node_type = props.node_type(succ);
        if node_type != NodeType::Revision && node_type != NodeType::Release {
            continue;
        }
        for label in labels {
            #[allow(clippy::collapsible_if)]
            if let EdgeLabel::Branch(branch) = label {
                if ref_name_ids.contains(&branch.label_name_id()) {
                    return Ok(Some(succ));
                }
            }
        }
    }
    Ok(None)
}

/// Returns all revisions that have no parent revision.
pub fn list_root_revisions<G>(graph: &G) -> Result<Vec<NodeId>>
where
    G: SwhForwardGraph + SwhGraphWithProperties<Maps: properties::Maps> + Sync,
{
    let graph = Subgraph::with_node_constraint(graph, "rev".parse().unwrap());

    let mut pl = concurrent_progress_logger!(
        item_name = "rev",
        display_memory = false,
        expected_updates = graph.actual_num_nodes().ok(),
    );
    pl.start("Listing initial revs...");
    Ok(graph
        .par_iter_nodes(pl)
        .filter(|&node| graph.successors(node).next().is_none())
        .collect())
}

/// Revision listing options (for [`list_revisions_with`]).
///
/// All filters are AND-ed together. Following `git-rev-list` semantics, filters come in two
/// kinds:
///
/// - *Traversal filters* prune the traversal: a filtered-out commit is not listed, and none of
///   its ancestors are visited (nor listed, unless reachable via another path). The only
///   traversal filter is [since](Self::since).
///
/// - *Output filters* only affect which commits are listed: traversal continues through
///   filtered-out commits, so their ancestors are still visited and listed. For example,
///   `max_parents: 1` lists all non-merge ancestors, including those reachable only through
///   merges. Output filters are [min_parents](Self::min_parents),
///   [max_parents](Self::max_parents), and [until](Self::until).
///
/// All timestamps are specified as seconds since the UNIX epoch. All time-based filters apply to
/// committer date by default (rather than author date). Revisions with no known committer date
/// pass all time-based filters (i.e., they are never filtered out by [since](Self::since) or
/// [until](Self::until)).
#[derive(Default)]
pub struct RevListOptions {
    /// Only list revisions with at least this amount of "parents" (i.e., successors in the
    /// forward graph).
    pub min_parents: Option<usize>,

    /// Only list revisions with at most this amount of "parents" (i.e., successors in the
    /// forward graph).
    pub max_parents: Option<usize>,

    /// Only list revisions more recent (or equal) than this timestamp (and stop traversal).
    pub since: Option<i64>,

    /// Only list revisions older (or equal) than this timestamp (without stopping traversal).
    pub until: Option<i64>,
    // author/committer: …  // TODO filter on author/committer's name
    // first_parent: bool,  // TODO (once we have access to parent merge order in swh-graph)
    // grep: …              // TODO filter on the content of commit messages
    // order_by: author/committer/topo  // TODO
}

/// List revision (commit) nodes in reverse chronological order, in the style of
/// [`git-rev-list`](https://git-scm.com/docs/git-rev-list).
///
/// Given a revision node, return a vector of all the revision nodes reachable from it following the
/// "parent revision" arcs, transitively.
///
/// For convenience, a release node can also be passed. If so, it will be peeled (see
/// [`peel_rel`]) to obtain the underlying revision node and start revision listing from
/// there.
///
/// Node ordering is by *committer* date (not author date), most recent date first. Revisions with
/// no known committer date are sorted last. Ties are broken by node id, in ascending order.
///
/// The revision listing behavior can be customized by passing [`RevListOptions`] to
/// [`list_revisions_with`].
pub fn list_revisions<G>(graph: &G, rev: NodeId) -> Result<Vec<NodeId>>
where
    G: SwhForwardGraph
        + SwhGraphWithProperties<Maps: properties::Maps, Timestamps: properties::Timestamps>,
{
    list_revisions_with(graph, &[rev], &[], &Default::default())
}

/// Variant of [`list_revisions`] that allows customizing listing behavior, in particular:
///
/// - Multiple start revisions can be specified with `start`.
/// - Multiple end revisions can be specified with `exclude`.
/// - Other options, such as revision filtering, can be specified via
///   [RevListOptions]
///
/// Intuitively, this function collects all commits reachable from *all* `start` revisions into a
/// single set, and then subtracts from it all commits reachable from *all* `exclude` revisions.
/// Filtering is applied during revision collection; only the [since](RevListOptions::since)
/// filter limits its reach (see [RevListOptions]). The obtained set is sorted in reverse
/// chronological order and returned to the caller.
///
/// See [`git-rev-list`](https://git-scm.com/docs/git-rev-list) for more information and examples.
pub fn list_revisions_with<G>(
    graph: &G,
    start: &[NodeId],
    exclude: &[NodeId],
    opts: &RevListOptions,
) -> Result<Vec<NodeId>>
where
    G: SwhForwardGraph
        + SwhGraphWithProperties<Maps: properties::Maps, Timestamps: properties::Timestamps>,
{
    let props = graph.properties();
    let rev_constraint: NodeConstraint = "rev".parse().unwrap();
    let rev_graph = Subgraph::with_node_constraint(graph, rev_constraint);

    // Peel release nodes to revisions; pass revision nodes through
    let peel_to_rev = |node: NodeId| -> Result<NodeId> {
        peel_rel(graph, node)?
            .filter(|&n| props.node_type(n) == NodeType::Revision)
            .ok_or_else(|| anyhow::anyhow!("Node {node} cannot be peeled to a revision"))
    };

    let start_revs: Vec<NodeId> = start
        .iter()
        .map(|&n| peel_to_rev(n))
        .collect::<Result<_>>()?;
    let exclude_revs: Vec<NodeId> = exclude
        .iter()
        .map(|&n| peel_to_rev(n))
        .collect::<Result<_>>()?;

    // Traversal filters: filtered-out commits are neither listed nor traversed through
    let passes_traversal_filters = |node: NodeId| -> bool {
        opts.since
            .is_none_or(|since| props.committer_timestamp(node).is_none_or(|ts| ts >= since))
    };

    // Count the parents of `node`, stopping at `limit`, i.e., return min(parent count, limit).
    // Subgraph::outdegree is O(outdegree), so this avoids full counts in the parent-count tests
    // below, which only need to compare the count against a bound.
    let count_parents_up_to =
        |node: NodeId, limit: usize| -> usize { rev_graph.successors(node).take(limit).count() };

    // Output filters: filtered-out commits are not listed, but traversal continues
    let passes_output_filters = |node: NodeId| -> bool {
        opts.min_parents
            .is_none_or(|min| count_parents_up_to(node, min) >= min)
            && opts
                .max_parents
                .is_none_or(|max| count_parents_up_to(node, max.saturating_add(1)) <= max)
            && opts
                .until
                .is_none_or(|until| props.committer_timestamp(node).is_none_or(|ts| ts <= until))
    };

    // Collect excluded revisions using iter_nodes (plain BFS, no filters), so that the main
    // traversal below can stop at excluded revisions without visiting their (also excluded)
    // ancestry.
    let excluded: AdaptiveNodeSet = {
        let mut set = AdaptiveNodeSet::new(graph.num_nodes());
        for node in iter_nodes(&rev_graph, &exclude_revs) {
            set.insert(node);
        }
        set
    };

    // Collect included revisions via BFS, stopping at excluded revisions (their ancestors must be
    // excluded too).
    let mut visited = AdaptiveNodeSet::new(graph.num_nodes());
    let mut included = Vec::new();
    let mut queue = VecDeque::new();
    for &rev in &start_revs {
        if !visited.contains(rev) && !excluded.contains(rev) {
            visited.insert(rev);
            queue.push_back(rev);
        }
    }
    while let Some(node) = queue.pop_front() {
        if !passes_traversal_filters(node) {
            continue; // don't list and don't traverse further
        }
        if passes_output_filters(node) {
            included.push(node);
        }
        for succ in rev_graph.successors(node) {
            if !visited.contains(succ) && !excluded.contains(succ) {
                visited.insert(succ);
                queue.push_back(succ);
            }
        }
    }

    // Sort by committer timestamp descending (most recent first), breaking ties by node id
    // ascending to make the result deterministic
    included.sort_unstable_by_key(|&rev| {
        (
            std::cmp::Reverse(props.committer_timestamp(rev).unwrap_or(i64::MIN)),
            rev,
        )
    });

    Ok(included)
}