netsuke-build 0.1.0-beta2

//! Deterministic projection of the build graph for rendering adapters.
//!
//! [`GraphView`] is the domain port that every renderer (DOT, HTML, future
//! JSON) consumes. It is constructed once from [`BuildGraph`] and exposes a
//! canonical, fully sorted view that is invariant under `HashMap` iteration
//! order. Renderer adapters under this module read [`GraphView`] only — they
//! never touch [`BuildGraph`] directly.

use std::collections::{BTreeMap, BTreeSet};

use camino::{Utf8Path, Utf8PathBuf};
use hashbrown::HashMap;

use crate::ir::{BuildEdge, BuildGraph};

pub mod render;
pub mod render_dot;
pub mod render_html;

/// Deterministic projection of [`BuildGraph`] consumed by renderer adapters.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct GraphView {
    /// Targets built when no explicit target is requested, sorted lexically.
    pub default_targets: Vec<Utf8PathBuf>,
    /// Every node referenced by the graph, sorted by [`NodeView::path`].
    pub nodes: Vec<NodeView>,
    /// Every edge, sorted by `(from, to, class)`.
    pub edges: Vec<EdgeView>,
    /// Reserved for the visualisation-bounding work tracked under roadmap
    /// item 3.15.6. Currently always `None`.
    pub limit: Option<usize>,
}

/// A node in the rendered graph. A node is either a build target produced by
/// some action, or a leaf source path referenced as an input.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct NodeView {
    /// Path identifying the node. Output paths for targets, input paths for
    /// sources.
    pub path: Utf8PathBuf,
    /// Whether the node is a target produced by an action or a leaf source.
    pub kind: NodeKind,
    /// Identifier of the producing action, when [`NodeKind::Target`].
    pub action_id: Option<String>,
    /// Optional human-readable description carried by the producing action.
    pub description: Option<String>,
}

/// Classification of a [`NodeView`].
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum NodeKind {
    /// A leaf input file referenced by one or more build edges. The node is
    /// not produced by any action in the current manifest.
    Source,
    /// A target produced by an action. `phony` and `always` mirror the
    /// corresponding flags on [`BuildEdge`].
    Target {
        /// The output is `phony` and has no on-disk artefact.
        phony: bool,
        /// The producing action runs on every invocation.
        always: bool,
    },
}

/// A directed edge in the rendered graph.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct EdgeView {
    /// Source of the edge.
    pub from: Utf8PathBuf,
    /// Destination of the edge.
    pub to: Utf8PathBuf,
    /// Classification of the edge.
    pub class: EdgeClass,
}

/// Dependency class of an [`EdgeView`].
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
pub enum EdgeClass {
    /// Explicit input → output dependency. The input appears in `$in`.
    Explicit,
    /// Implicit input → output dependency (Ninja `|`). The input triggers a
    /// rebuild when changed but is not substituted into `$in`.
    ImplicitDep,
    /// Input → implicit output dependency. The output is generated by the
    /// action but is not listed in its `explicit_outputs`.
    ImplicitOutput,
    /// Order-only dependency (Ninja `||`). Does not trigger a rebuild.
    OrderOnly,
}

impl GraphView {
    /// Project a [`BuildGraph`] into a deterministic [`GraphView`].
    ///
    /// The projection sorts every collection so that two graphs equal up to
    /// `HashMap` insertion order yield byte-identical views.
    #[must_use]
    pub fn from_build_graph(graph: &BuildGraph) -> Self {
        let edges_seen = collect_unique_edges(graph);

        let mut registry = NodePathRegistry::default();
        let mut node_metadata: BTreeMap<Utf8PathBuf, NodeMetadata> = BTreeMap::new();
        let mut edges: BTreeSet<EdgeView> = BTreeSet::new();

        for edge in &edges_seen {
            register_outputs(graph, edge, &mut registry, &mut node_metadata);
            EdgeRegistrar {
                edge,
                registry: &mut registry,
                edges: &mut edges,
            }
            .register();
        }

        let nodes = registry
            .into_inner()
            .into_iter()
            .map(|(path, kind)| {
                let meta = node_metadata.remove(&path).unwrap_or_default();
                NodeView {
                    path,
                    kind,
                    action_id: meta.action_id,
                    description: meta.description,
                }
            })
            .collect();

        let mut default_targets = graph.default_targets.clone();
        default_targets.sort();
        default_targets.dedup();

        Self {
            default_targets,
            nodes,
            edges: edges.into_iter().collect(),
            limit: None,
        }
    }
}

#[derive(Debug, Default, Clone)]
struct NodeMetadata {
    action_id: Option<String>,
    description: Option<String>,
}

/// Registry mapping node paths to their [`NodeKind`] classification.
///
/// Wraps the projection's path map behind borrow-returning accessors so
/// callers work with references instead of cloning keys defensively.
#[derive(Debug, Default)]
struct NodePathRegistry {
    paths: HashMap<Utf8PathBuf, NodeKind>,
}

impl NodePathRegistry {
    /// Return the registered kind for `path`, recording a [`NodeKind::Source`]
    /// node when the path is not yet known.
    ///
    /// Performs a single lookup on the hit path and clones `path` only when
    /// inserting. An existing registration (for example a target produced by
    /// an earlier edge) is returned unchanged.
    fn ensure_node_mut(&mut self, path: &Utf8Path) -> &mut NodeKind {
        self.paths.entry_ref(path).or_insert(NodeKind::Source)
    }

    /// Record `path` as a target node, replacing any existing registration.
    fn insert_target(&mut self, path: &Utf8Path, kind: NodeKind) {
        self.paths.insert(path.to_owned(), kind);
    }

    /// Consume the registry, yielding the sorted path map.
    fn into_inner(self) -> BTreeMap<Utf8PathBuf, NodeKind> {
        self.paths.into_iter().collect()
    }
}

/// Deduplicate the build edges referenced by [`BuildGraph::targets`].
///
/// `BuildGraph::targets` maps every output path back to a (cloned) `BuildEdge`,
/// so iterating values produces duplicates. We dedup by the lexically-sorted
/// tuple of explicit outputs, which uniquely identifies a build statement.
fn collect_unique_edges(graph: &BuildGraph) -> Vec<BuildEdge> {
    let mut by_key: BTreeMap<Vec<Utf8PathBuf>, BuildEdge> = BTreeMap::new();
    for edge in graph.targets.values() {
        let mut key = edge.explicit_outputs.clone();
        key.sort();
        by_key.entry(key).or_insert_with(|| edge.clone());
    }
    by_key.into_values().collect()
}

fn register_outputs(
    graph: &BuildGraph,
    edge: &BuildEdge,
    registry: &mut NodePathRegistry,
    node_metadata: &mut BTreeMap<Utf8PathBuf, NodeMetadata>,
) {
    let description = graph
        .actions
        .get(&edge.action_id)
        .and_then(|action| action.description.clone());
    for out in all_outputs(edge) {
        registry.insert_target(
            out,
            NodeKind::Target {
                phony: edge.phony,
                always: edge.always,
            },
        );
        node_metadata.insert(
            out.clone(),
            NodeMetadata {
                action_id: Some(edge.action_id.clone()),
                description: description.clone(),
            },
        );
    }
}

/// Every output produced by `edge`, explicit first, then implicit.
fn all_outputs(edge: &BuildEdge) -> impl Iterator<Item = &Utf8PathBuf> {
    edge.explicit_outputs
        .iter()
        .chain(edge.implicit_outputs.iter())
}

/// Registers the dependency nodes and edges contributed by one build edge.
///
/// Groups the edge with the mutable projection state so the per-class
/// helpers share one borrow of the registry and edge set.
struct EdgeRegistrar<'a> {
    edge: &'a BuildEdge,
    registry: &'a mut NodePathRegistry,
    edges: &'a mut BTreeSet<EdgeView>,
}

impl EdgeRegistrar<'_> {
    /// Register the edge's inputs and dependencies with their edge classes.
    fn register(&mut self) {
        self.register_inputs();
        let edge = self.edge;
        self.register_dependencies(&edge.implicit_deps, EdgeClass::ImplicitDep);
        self.register_dependencies(&edge.order_only_deps, EdgeClass::OrderOnly);
    }

    /// Register explicit inputs, classifying edges into implicit outputs.
    fn register_inputs(&mut self) {
        let edge = self.edge;
        let implicit: BTreeSet<&Utf8PathBuf> = edge.implicit_outputs.iter().collect();
        for input in &edge.inputs {
            self.registry.ensure_node_mut(input);
            self.register_input_edges(input, &implicit);
        }
    }

    /// Add one edge from `input` to every output, classified by whether the
    /// output is implicit.
    fn register_input_edges(&mut self, input: &Utf8PathBuf, implicit: &BTreeSet<&Utf8PathBuf>) {
        self.insert_edges(input, |out| {
            if implicit.contains(out) {
                EdgeClass::ImplicitOutput
            } else {
                EdgeClass::Explicit
            }
        });
    }

    /// Register `deps` as source nodes with a `class` edge to every output.
    fn register_dependencies(&mut self, deps: &[Utf8PathBuf], class: EdgeClass) {
        for dep in deps {
            self.registry.ensure_node_mut(dep);
            self.insert_edges(dep, |_| class);
        }
    }

    /// Insert one edge from `from` to every output, classified by `class_for`.
    fn insert_edges(&mut self, from: &Utf8PathBuf, class_for: impl Fn(&Utf8PathBuf) -> EdgeClass) {
        for out in all_outputs(self.edge) {
            self.edges.insert(EdgeView {
                from: from.clone(),
                to: out.clone(),
                class: class_for(out),
            });
        }
    }
}

impl Ord for EdgeView {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        (&self.from, &self.to, self.class).cmp(&(&other.from, &other.to, other.class))
    }
}

impl PartialOrd for EdgeView {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        Some(self.cmp(other))
    }
}

#[cfg(test)]
mod tests;