crates/gunnar-ui-web/src/graph.rs
//! Commit-topology layout — the pure half of the graph page.
//!
//! `&[GraphCommit] -> GraphLayout`: no leptos, no web-sys, no browser. The web
//! crate builds on the host with a stub main, which is exactly what lets every
//! decision in this module run under plain `cargo test` (`lib.rs` gates the
//! DOM-touching modules on `wasm32`; this one it does not).
//!
//! Two passes, both textbook:
//!
//! 1. **Topological order** (Kahn). The wire order of gunnar's `Log` is NOT
//! trusted — a window seam can put a parent above its child, and rendering
//! that order crosses every edge through the seam. Children always end up
//! above parents; ties break newest-committer-time-first.
//! 2. **The gitk sweep**, newest-first: land on the column that was waiting
//! for you, else open the leftmost free column; first parent inherits the
//! column and its colour (that is what keeps a branch one stable colour
//! down the page); extra parents fork to a new column or join the lane
//! already waiting for them; merges close every other lane that was
//! waiting.
//!
//! The rendered gap between two rows is described on the UPPER row
//! ([`Row::edges`]): one segment per lane crossing that gap, already resolved
//! to its destination column, so the renderer never re-derives topology.
use std::collections::HashMap;
/// What the layout needs to know about one commit — deliberately decoupled
/// from the page's serde type.
#[derive(Debug, Clone)]
pub struct GraphCommit {
pub oid: String,
pub parent_oids: Vec<String>,
/// Committer time, for the ready-set ordering. Zero is fine; it only
/// breaks ties.
pub time_unix_seconds: i64,
}
/// One commit's place on the wall.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Row {
/// Index into the input slice.
pub commit: usize,
pub column: usize,
/// Palette index. Stable down a lane; the renderer wraps it mod 8.
pub color: usize,
/// True when the commit has more than one parent — rendered hollow.
pub merge: bool,
/// The lane segments crossing the gap BELOW this row.
pub edges: Vec<Edge>,
/// First parents that are outside the window: "history continues below".
pub stubs: Vec<Stub>,
}
/// One lane segment between this row and the next: from a column at this row
/// to a column at the next. Straight when they are equal, a spline when not.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Edge {
pub from_col: usize,
pub to_col: usize,
pub color: usize,
}
/// An edge that leaves the window. A fact, not decoration — the page makes it
/// clickable and fetches the missing lane.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Stub {
pub col: usize,
pub parent_oid: String,
pub color: usize,
}
#[derive(Debug, Clone, Default)]
pub struct GraphLayout {
/// One per input commit, in display order (children above parents).
pub rows: Vec<Row>,
/// The widest the wall ever gets, for sizing the gutter.
pub lane_count: usize,
}
/// A lane that is open and waiting for exactly one oid.
struct Open {
pending: usize,
color: usize,
/// Set when the lane was created or redirected at the row just above: the
/// first gap segment then departs from THAT column (the fork's swerve out
/// of the merge node) instead of from the lane's own column.
entered_from: Option<usize>,
}
/// Lay out a window of commits.
pub fn layout(commits: &[GraphCommit]) -> GraphLayout {
let index: HashMap<&str, usize> = commits
.iter()
.enumerate()
.map(|(i, c)| (c.oid.as_str(), i))
.collect();
let order = topo_order(commits, &index);
let mut columns: Vec<Option<Open>> = Vec::new();
let mut next_color = 0usize;
let mut lane_count = 0usize;
let mut rows: Vec<Row> = Vec::with_capacity(order.len());
// Fork segments waiting for the next gap: (from the merge node's column,
// into this lane's column, in that lane's colour).
let mut pending_forks: Vec<(usize, usize, usize)> = Vec::new();
for &at in &order {
let commit = &commits[at];
// ── where this commit lands ─────────────────────────────────────────
let landing: Vec<usize> = columns
.iter()
.enumerate()
.filter_map(|(i, slot)| slot.as_ref().filter(|open| open.pending == at).map(|_| i))
.collect();
let (column, color) = match landing.first() {
Some(&col) => {
let open = columns[col].as_ref().expect("landing is open");
(col, open.color)
}
None => {
let col = leftmost_free(&columns);
let color = next_color;
next_color += 1;
if col == columns.len() {
columns.push(None);
}
(col, color)
}
};
// ── the gap ABOVE this row, attached to the row before it ───────────
//
// Every open lane crosses it: into this commit's column when the lane
// was waiting for this commit, straight down otherwise. Fork swerves
// recorded at the previous row cross it too.
if let Some(previous) = rows.last_mut() {
for (i, slot) in columns.iter_mut().enumerate() {
let Some(open) = slot else { continue };
let from = open.entered_from.take().unwrap_or(i);
let to = if open.pending == at { column } else { i };
previous.edges.push(Edge {
from_col: from,
to_col: to,
color: open.color,
});
}
for (from, lane, color) in pending_forks.drain(..) {
// The lane the fork joins may itself be landing on this very
// commit; follow it.
let to = match columns.get(lane).and_then(|s| s.as_ref()) {
Some(open) if open.pending == at => column,
_ => lane,
};
previous.edges.push(Edge {
from_col: from,
to_col: to,
color,
});
}
} else {
pending_forks.clear();
}
// ── close every lane that merged here ───────────────────────────────
for &col in &landing {
columns[col] = None;
}
// ── continue, fork, stub ────────────────────────────────────────────
let mut stubs = Vec::new();
let mut parents = commit.parent_oids.iter();
// A root has no first parent, and its lane simply ends.
if let Some(first) = parents.next() {
match index.get(first.as_str()) {
Some(&parent_at) => {
// Another lane may ALREADY be waiting for this parent (two
// branches sharing history). Joining it keeps the graph a
// graph; opening a duplicate column draws the same commit
// twice.
let existing = columns.iter().position(|slot| {
slot.as_ref().is_some_and(|open| open.pending == parent_at)
});
match existing {
Some(lane) => {
let color = columns[lane].as_ref().expect("just found").color;
pending_forks.push((column, lane, color));
}
None => {
columns[column] = Some(Open {
pending: parent_at,
color,
entered_from: None,
});
}
}
}
None => stubs.push(Stub {
col: column,
parent_oid: first.clone(),
color,
}),
}
}
for parent in parents {
match index.get(parent.as_str()) {
Some(&parent_at) => {
let existing = columns.iter().position(|slot| {
slot.as_ref().is_some_and(|open| open.pending == parent_at)
});
match existing {
Some(lane) => {
let color = columns[lane].as_ref().expect("just found").color;
pending_forks.push((column, lane, color));
}
None => {
let col = leftmost_free(&columns);
if col == columns.len() {
columns.push(None);
}
let color = next_color;
next_color += 1;
columns[col] = Some(Open {
pending: parent_at,
color,
entered_from: Some(column),
});
}
}
}
None => stubs.push(Stub {
col: column,
parent_oid: parent.clone(),
color,
}),
}
}
lane_count = lane_count.max(columns.len());
rows.push(Row {
commit: at,
column,
color,
merge: commit.parent_oids.len() > 1,
edges: Vec::new(),
stubs,
});
}
GraphLayout { rows, lane_count }
}
fn leftmost_free(columns: &[Option<Open>]) -> usize {
columns
.iter()
.position(|slot| slot.is_none())
.unwrap_or(columns.len())
}
/// Children above parents; ready set ordered newest-committer-time-first.
///
/// Kahn over the child→parent edges that stay inside the window. A cycle —
/// which a well-formed repository cannot contain but a corrupt window might —
/// leaves its members unprocessed; they are appended in input order rather
/// than looping forever.
fn topo_order(commits: &[GraphCommit], index: &HashMap<&str, usize>) -> Vec<usize> {
use std::collections::BinaryHeap;
let n = commits.len();
let mut indegree = vec![0usize; n];
for commit in commits {
for parent in &commit.parent_oids {
if let Some(&p) = index.get(parent.as_str()) {
indegree[p] += 1;
}
}
}
let mut ready: BinaryHeap<(i64, std::cmp::Reverse<usize>)> = (0..n)
.filter(|&i| indegree[i] == 0)
.map(|i| (commits[i].time_unix_seconds, std::cmp::Reverse(i)))
.collect();
let mut out = Vec::with_capacity(n);
let mut done = vec![false; n];
while let Some((_, std::cmp::Reverse(i))) = ready.pop() {
out.push(i);
done[i] = true;
for parent in &commits[i].parent_oids {
if let Some(&p) = index.get(parent.as_str()) {
indegree[p] -= 1;
if indegree[p] == 0 {
ready.push((commits[p].time_unix_seconds, std::cmp::Reverse(p)));
}
}
}
}
for (i, finished) in done.iter().enumerate().take(n) {
if !finished {
out.push(i);
}
}
out
}
// ── SVG geometry, still pure ────────────────────────────────────────────────
/// Left padding before the first lane, in px.
pub const GUTTER_PAD: usize = 12;
/// Column pitch, in px.
pub const LANE_PITCH: usize = 16;
/// Row pitch, in px — must match the CSS row height.
pub const ROW_PITCH: usize = 28;
/// Node radius.
pub const NODE_R: usize = 4;
/// A node's x for its column.
pub fn lane_x(column: usize) -> usize {
GUTTER_PAD + column * LANE_PITCH
}
/// A node's y for its row.
pub fn row_y(row: usize) -> usize {
row * ROW_PITCH + ROW_PITCH / 2
}
/// One `<path>`: its palette colour and its `d`.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct PathSpec {
pub color: usize,
pub d: String,
}
/// Every edge of the layout as SVG path data, with straight runs coalesced.
///
/// A vertical lane that crosses many gaps unchanged becomes ONE
/// `M x y V y2`, so a 1000-row window with a handful of lanes is a few
/// hundred SVG nodes rather than tens of thousands. A segment that changes
/// column is a cubic bezier with vertical tangents at both ends — the lane
/// swerve — and is never coalesced.
pub fn svg_paths(layout: &GraphLayout) -> Vec<PathSpec> {
let mut out = Vec::new();
// Open straight runs: (column, color) → y the run started at.
let mut runs: HashMap<(usize, usize), usize> = HashMap::new();
for (r, row) in layout.rows.iter().enumerate() {
let y1 = row_y(r);
let y2 = row_y(r + 1);
let mut continuing: Vec<(usize, usize)> = Vec::new();
for edge in &row.edges {
if edge.from_col == edge.to_col {
let key = (edge.from_col, edge.color);
runs.entry(key).or_insert(y1);
continuing.push(key);
} else {
let x1 = lane_x(edge.from_col);
let x2 = lane_x(edge.to_col);
let mid = ROW_PITCH / 2;
out.push(PathSpec {
color: edge.color,
d: format!(
"M {x1} {y1} C {x1} {}, {x2} {}, {x2} {y2}",
y1 + mid,
y2 - mid
),
});
}
}
// Any straight run that did NOT continue through this gap ends at this
// row and is flushed.
runs.retain(|key, started| {
if continuing.contains(key) {
true
} else {
out.push(PathSpec {
color: key.1,
d: format!("M {} {} V {}", lane_x(key.0), *started, y1),
});
false
}
});
}
// Whatever is still open runs to the last row it could reach.
let bottom = row_y(layout.rows.len().saturating_sub(1));
for ((col, color), started) in runs {
out.push(PathSpec {
color,
d: format!("M {} {} V {}", lane_x(col), started, bottom),
});
}
out
}
#[cfg(test)]
mod tests {
use super::*;
fn commit(oid: &str, parents: &[&str], time: i64) -> GraphCommit {
GraphCommit {
oid: oid.to_owned(),
parent_oids: parents.iter().map(|p| (*p).to_owned()).collect(),
time_unix_seconds: time,
}
}
fn rows_by_oid<'a>(
commits: &'a [GraphCommit],
layout: &GraphLayout,
) -> Vec<(&'a str, &'static str)> {
// Just the display order, for readable assertions.
layout
.rows
.iter()
.map(|r| (commits[r.commit].oid.as_str(), ""))
.collect()
}
/// ★ A linear history is one lane, one colour, and nothing but straight
/// edges — the shape everything else degrades toward.
#[test]
fn a_linear_history_is_one_straight_lane() {
let commits = vec![
commit("c", &["b"], 3),
commit("b", &["a"], 2),
commit("a", &[], 1),
];
let l = layout(&commits);
assert_eq!(l.lane_count, 1);
assert!(l.rows.iter().all(|r| r.column == 0 && r.color == 0));
assert!(l
.rows
.iter()
.flat_map(|r| &r.edges)
.all(|e| e.from_col == 0 && e.to_col == 0));
// Coalescing: one lane over three rows is ONE path.
let paths = svg_paths(&l);
assert_eq!(paths.len(), 1, "straight runs must coalesce: {paths:?}");
assert!(paths[0].d.contains('V'));
}
/// ★ A feature branch opens a second lane at the merge and closes it at
/// the fork point — and the branch keeps ONE colour down its whole run.
#[test]
fn a_merge_opens_a_lane_and_the_branch_point_closes_it() {
let commits = vec![
commit("m", &["b", "f"], 4), // merge
commit("b", &["a"], 3), // mainline
commit("f", &["a"], 2), // feature
commit("a", &[], 1), // branch point
];
let l = layout(&commits);
assert_eq!(l.lane_count, 2);
assert!(l.rows[0].merge, "two parents render hollow");
let col_of = |oid: &str| {
l.rows
.iter()
.find(|r| commits[r.commit].oid == oid)
.map(|r| (r.column, r.color))
.unwrap()
};
assert_eq!(col_of("m").0, 0);
assert_eq!(col_of("b").0, 0);
let (f_col, f_color) = col_of("f");
assert_eq!(f_col, 1, "the second parent forks to the next lane");
assert_ne!(f_color, col_of("b").1, "a new lane is a new colour");
// The branch point lands back on column 0, and after it nothing is
// open: the feature lane closed INTO it.
assert_eq!(col_of("a").0, 0);
let a_row = l
.rows
.iter()
.position(|r| commits[r.commit].oid == "a")
.unwrap();
assert_eq!(a_row, l.rows.len() - 1);
// The gap above `a` carries a bend from lane 1 into column 0.
let above_a = &l.rows[a_row - 1].edges;
assert!(
above_a.iter().any(|e| e.from_col == 1 && e.to_col == 0),
"the feature lane must swerve into the branch point: {above_a:?}"
);
}
/// ★ A parent outside the window is a stub — a fact on the row, never a
/// dangling lane that pretends the history ends.
#[test]
fn a_parent_outside_the_window_is_a_stub() {
let commits = vec![commit("b", &["a"], 2), commit("a", &["gone"], 1)];
let l = layout(&commits);
let last = l.rows.last().unwrap();
assert_eq!(last.stubs.len(), 1);
assert_eq!(last.stubs[0].parent_oid, "gone");
// And no lane stays open for it.
assert_eq!(l.lane_count, 1);
}
/// ★ The wire order is not trusted: a parent listed ABOVE its child still
/// renders below it.
#[test]
fn a_seam_scrambled_window_is_repaired_by_the_topo_sort() {
let commits = vec![
commit("a", &[], 1), // parent first on the wire
commit("b", &["a"], 2),
];
let l = layout(&commits);
let order: Vec<&str> = l
.rows
.iter()
.map(|r| commits[r.commit].oid.as_str())
.collect();
assert_eq!(order, vec!["b", "a"], "children above parents, always");
let _ = rows_by_oid(&commits, &l);
}
/// ★ Two tips sharing history join ONE lane at the shared commit instead
/// of drawing it twice.
#[test]
fn two_branches_join_their_shared_history_once() {
let commits = vec![
commit("x", &["a"], 3),
commit("y", &["a"], 2),
commit("a", &[], 1),
];
let l = layout(&commits);
let a_rows: Vec<_> = l
.rows
.iter()
.filter(|r| commits[r.commit].oid == "a")
.collect();
assert_eq!(a_rows.len(), 1);
// Both lanes existed above it.
assert_eq!(l.lane_count, 2);
}
/// ★ A corrupt window with a cycle terminates and shows every commit.
#[test]
fn a_cycle_cannot_hang_the_layout() {
let commits = vec![commit("a", &["b"], 2), commit("b", &["a"], 1)];
let l = layout(&commits);
assert_eq!(l.rows.len(), 2, "both rendered, none looped");
}
}
// ── History: which refs the wall is drawn from ───────────────────────────
/// What History draws (owner order 2026-10-18): the default branch, one
/// named ref from the picker, or every branch and tag tip at once. The ref
/// walk is gunnar's; the page only names which.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum HistoryView {
Default,
Ref(String),
All,
}
impl HistoryView {
/// The view the page's own `?ref=` / `?all=1` name.
pub fn from_query(reference: Option<String>, all: Option<String>) -> Self {
if matches!(all.as_deref(), Some("1" | "true" | "yes")) {
return HistoryView::All;
}
match reference {
Some(name) if !name.is_empty() => HistoryView::Ref(name),
_ => HistoryView::Default,
}
}
/// The page's query string for this view: what the picker navigates to.
pub fn page_query(&self) -> String {
match self {
HistoryView::Default => String::new(),
HistoryView::All => "?all=1".to_owned(),
HistoryView::Ref(name) => format!("?ref={}", crate::auth::percent_encode(name)),
}
}
/// The picker's `<option value>` for this view.
pub fn pick_value(&self) -> String {
match self {
HistoryView::Default => String::new(),
HistoryView::All => PICK_ALL.to_owned(),
HistoryView::Ref(name) => name.clone(),
}
}
/// The view an `<option value>` names.
pub fn from_pick(value: &str) -> Self {
match value {
"" => HistoryView::Default,
PICK_ALL => HistoryView::All,
name => HistoryView::Ref(name.to_owned()),
}
}
}
/// The picker's value for "All branches"; no ref is named like this.
pub const PICK_ALL: &str = "*all";
/// The `/log` URL one fetch asks for. A frontier oid (`from`, from "Load
/// more" or a stub) continues the wall as a plain walk and wins over the view.
pub fn log_url(ns_seg: &str, name_seg: &str, limit: usize, from: &str, view: &HistoryView) -> String {
let tail = if !from.is_empty() {
format!("&start={}", crate::auth::percent_encode(from))
} else {
match view {
HistoryView::Default => String::new(),
HistoryView::All => "&all=1".to_owned(),
HistoryView::Ref(name) => format!("&ref={}", crate::auth::percent_encode(name)),
}
};
format!("/api/repos/{ns_seg}/{name_seg}/log?limit={limit}{tail}")
}
#[cfg(test)]
mod history_view_tests {
use super::*;
#[test]
fn the_log_url_names_the_view_and_a_frontier_continues_it() {
let main = HistoryView::from_query(None, None);
assert_eq!(main, HistoryView::Default);
assert_eq!(log_url("ns", "r", 500, "", &main), "/api/repos/ns/r/log?limit=500");
let side = HistoryView::from_query(Some("refs/heads/side".into()), None);
assert_eq!(side, HistoryView::Ref("refs/heads/side".into()));
assert_eq!(
log_url("ns", "r", 500, "", &side),
"/api/repos/ns/r/log?limit=500&ref=refs/heads/side"
);
let all = HistoryView::from_query(None, Some("1".into()));
assert_eq!(all, HistoryView::All);
assert_eq!(log_url("ns", "r", 500, "", &all), "/api/repos/ns/r/log?limit=500&all=1");
// "Load more" and a stub continue from a frontier oid, whatever the view.
assert_eq!(
log_url("ns", "r", 250, "abc", &all),
"/api/repos/ns/r/log?limit=250&start=abc"
);
// A ref name with characters a query string would split on is encoded.
let odd = HistoryView::Ref("refs/heads/a&b+c".into());
assert_eq!(
log_url("ns", "r", 1, "", &odd),
"/api/repos/ns/r/log?limit=1&ref=refs/heads/a%26b%2Bc"
);
}
#[test]
fn the_picker_round_trips_every_view_through_the_page_url() {
for view in [
HistoryView::Default,
HistoryView::All,
HistoryView::Ref("refs/tags/v1".into()),
] {
assert_eq!(HistoryView::from_pick(&view.pick_value()), view);
}
assert_eq!(HistoryView::Default.page_query(), "");
assert_eq!(HistoryView::All.page_query(), "?all=1");
assert_eq!(
HistoryView::Ref("refs/heads/side".into()).page_query(),
"?ref=refs/heads/side"
);
// An explicit all wins over a stray ref.
assert_eq!(
HistoryView::from_query(Some("refs/heads/x".into()), Some("1".into())),
HistoryView::All
);
}
}
/// **At most this many reference chips on one commit's row** (GUN-FIELD-TEST, 2026-11-01:
/// a commit under 300 branches drew 300 chips in one sideways row).
pub const CHIP_CAP: usize = 5;
/// Pure: the chips one row shows, the default branch first, then tags, then the rest by
/// name, and how many more there are. `rank` is 0 for the default branch, 1 for a tag,
/// 2 otherwise.
pub fn capped_chips<T: Clone>(chips: &[(String, u8, T)]) -> (Vec<(String, u8, T)>, usize) {
let mut all = chips.to_vec();
all.sort_by(|a, b| (a.1, &a.0).cmp(&(b.1, &b.0)));
let more = all.len().saturating_sub(CHIP_CAP);
all.truncate(CHIP_CAP);
(all, more)
}
#[cfg(test)]
mod gunfield_tests {
use super::*;
/// ★ 300 branches on one commit: the default branch and the tag first, five chips,
/// and "+N more".
#[test]
fn a_crowded_commit_shows_five_chips_and_how_many_more() {
let mut chips: Vec<(String, u8, ())> = (0..300).map(|i| (format!("fix/b{i:03}"), 2u8, ())).collect();
chips.push(("v1.0.0".into(), 1, ()));
chips.push(("main".into(), 0, ()));
let (shown, more) = capped_chips(&chips);
let names: Vec<&str> = shown.iter().map(|c| c.0.as_str()).collect();
assert_eq!(names, ["main", "v1.0.0", "fix/b000", "fix/b001", "fix/b002"]);
assert_eq!(more, 297);
let few = vec![("main".to_owned(), 0u8, ()), ("topic".to_owned(), 2u8, ())];
assert_eq!(capped_chips(&few), (few.clone(), 0), "nothing more: no '+0'");
}
/// ★ The graph draws through the cap and draws "+N more" only when there is more.
#[test]
fn the_graph_draws_the_capped_chips() {
let page = crate::code::of(include_str!("pages/graph.rs"));
assert!(page.contains("crate::graph::capped_chips("), "the rows use the cap");
assert!(page.contains("(more > 0).then("), "the '+N more' chip only when there is more");
}
}