ingraph 0.1.0

A declaration-driven indexing framework: records and nodes are written as Rust types, and the storage rows, the dataflow between them and the GraphQL query surface are emitted from the declaration.
Documentation
//! Validation: freeze a [`GraphBuilder`] into an immutable [`ChannelGraph`] with
//! **derived** layers (round-based Kahn topo-sort — no fixed tiers).

use super::{
  ArrangeError, CycleError, DirectFanoutError, EdgeEndpointError, EdgeId, NodeId,
  builder::{Edge, GraphBuilder, Node},
};

/// A validated, immutable unit-DAG: its nodes/edges plus the topologically derived
/// layers and any orphan nodes (unreachable from a source — reported, not rejected).
#[derive(Debug)]
pub struct ChannelGraph {
  nodes: Vec<Node>,
  edges: Vec<Edge>,
  layers: Vec<Vec<NodeId>>,
  orphans: Vec<NodeId>,
}

impl ChannelGraph {
  /// Every node, in declaration order (indexable by [`NodeId::index`]).
  #[inline]
  pub fn nodes(&self) -> &[Node] {
    &self.nodes
  }

  /// Every edge, in declaration order.
  #[inline]
  pub fn edges(&self) -> &[Edge] {
    &self.edges
  }

  /// The derived layers: layer `k` holds every node whose longest path from a root
  /// is `k`. Every edge runs from an earlier layer to a strictly later one.
  #[inline]
  pub fn layers(&self) -> &[Vec<NodeId>] {
    &self.layers
  }

  /// Nodes with no path from any source (dead in a static topology; reported as
  /// data, not an error — the runtime rejects an un-drivable node).
  #[inline]
  pub fn orphans(&self) -> &[NodeId] {
    &self.orphans
  }

  /// The declaration for `id`, or `None` if `id` does not name a node of this
  /// graph — a [`NodeId`] is unbranded, so one minted by a different graph may
  /// index past this node set.
  #[inline]
  pub fn node(&self, id: NodeId) -> Option<&Node> {
    self.nodes.get(id.index())
  }
}

impl GraphBuilder {
  /// Validate and freeze the graph.
  ///
  /// # Errors
  ///
  /// - [`ArrangeError::EdgeEndpointOutOfRange`] if an edge endpoint indexes past the
  ///   node set (a handle minted by a different builder).
  /// - [`ArrangeError::DirectFanout`] if a node has a `Direct` edge that is not its
  ///   sole out-edge.
  /// - [`ArrangeError::Cycle`] if the declared edges are cyclic.
  pub fn validate(self) -> Result<ChannelGraph, ArrangeError> {
    let (nodes, edges) = self.into_parts();
    let n = nodes.len();

    // Endpoint bounds: a `NodeHandle` carries no builder brand, so a handle minted
    // by a *different* builder can smuggle a NodeId that is out of range here. Reject
    // it up front — every later step indexes the node vectors by these endpoints.
    for (i, e) in edges.iter().enumerate() {
      for endpoint in [e.from(), e.to()] {
        if endpoint.index() >= n {
          return Err(ArrangeError::EdgeEndpointOutOfRange(
            EdgeEndpointError::new(EdgeId::new(i), endpoint, n),
          ));
        }
      }
    }

    // Fan-out legality: a Direct edge is an exclusive move, so it must be a node's
    // only out-edge. Broadcast/Group may coexist in multiples.
    let mut out_count = vec![0usize; n];
    let mut has_direct = vec![false; n];
    for e in &edges {
      let f = e.from().index();
      out_count[f] += 1;
      if e.kind().is_direct() {
        has_direct[f] = true;
      }
    }
    for i in 0..n {
      if out_count[i] > 1 && has_direct[i] {
        return Err(ArrangeError::DirectFanout(DirectFanoutError::new(
          NodeId::new(i),
          nodes[i].name().into(),
          out_count[i],
        )));
      }
    }

    // Round-based Kahn layering. Each round takes every not-yet-placed node whose
    // in-degree has dropped to 0 as one layer, then removes it. An edge to a node
    // keeps that node's in-degree > 0 until its producer is placed, so every edge
    // necessarily crosses to a strictly later layer — the "as many layers as the
    // topology implies" property.
    let mut adj: Vec<Vec<usize>> = vec![Vec::new(); n];
    let mut indeg = vec![0usize; n];
    for e in &edges {
      adj[e.from().index()].push(e.to().index());
      indeg[e.to().index()] += 1;
    }
    let mut remaining = indeg;
    let mut placed = vec![false; n];
    let mut placed_count = 0usize;
    let mut layers: Vec<Vec<NodeId>> = Vec::new();
    loop {
      // The ascending range scan already yields each layer sorted by NodeId —
      // deterministic contents (stable tests + stable launch order) with no sort.
      let layer: Vec<usize> = (0..n)
        .filter(|&i| !placed[i] && remaining[i] == 0)
        .collect();
      if layer.is_empty() {
        break;
      }
      for &i in &layer {
        placed[i] = true;
      }
      placed_count += layer.len();
      // Decrement successors only after the whole layer is placed, so two nodes in
      // the same layer never suppress each other into different rounds.
      for &i in &layer {
        for &t in &adj[i] {
          remaining[t] -= 1;
        }
      }
      layers.push(layer.into_iter().map(NodeId::new).collect());
    }
    if placed_count < n {
      // Kahn's stall leaves unplaced both cycle members AND nodes merely
      // downstream of a cycle, so "any unplaced node" would misname the culprit.
      // But the stall means every unplaced node kept an in-edge from another
      // unplaced node, so walking predecessors through unplaced nodes must
      // revisit one within n steps — and the first revisited node lies on a
      // genuine cycle (the walked segment between its two visits is that cycle,
      // reversed).
      let mut pred: Vec<Vec<usize>> = vec![Vec::new(); n];
      for e in &edges {
        pred[e.to().index()].push(e.from().index());
      }
      let mut visited = vec![false; n];
      let mut cur = (0..n)
        .find(|&i| !placed[i])
        .expect("a node remains unplaced");
      while !visited[cur] {
        visited[cur] = true;
        cur = pred[cur]
          .iter()
          .copied()
          .find(|&p| !placed[p])
          .expect("Kahn stalled, so every unplaced node has an unplaced predecessor");
      }
      return Err(ArrangeError::Cycle(CycleError::new(
        NodeId::new(cur),
        nodes[cur].name().into(),
      )));
    }

    // Orphans: nodes not reachable from any source via forward edges.
    let mut reachable = vec![false; n];
    let mut stack: Vec<usize> = (0..n).filter(|&i| nodes[i].is_source()).collect();
    for &s in &stack {
      reachable[s] = true;
    }
    while let Some(i) = stack.pop() {
      for &t in &adj[i] {
        if !reachable[t] {
          reachable[t] = true;
          stack.push(t);
        }
      }
    }
    let orphans: Vec<NodeId> = (0..n).filter(|&i| !reachable[i]).map(NodeId::new).collect();

    Ok(ChannelGraph {
      nodes,
      edges,
      layers,
      orphans,
    })
  }
}

#[cfg(test)]
mod tests;