#[derive(Clone, Debug, PartialEq)]
struct Lane {
waiting_for: String,
color: usize,
touched: u64,
}
pub const MAX_LANES: usize = 64;
#[derive(Debug, PartialEq)]
pub struct Step {
pub col: usize,
pub before: Vec<bool>,
pub at: Vec<bool>,
pub pre_shift: Vec<bool>,
pub after: Vec<bool>,
pub closing: Vec<usize>,
pub opening: Vec<usize>,
pub shifts: Vec<(usize, usize)>,
pub is_merge: bool,
pub colors: Vec<usize>,
pub colors_after: Vec<usize>,
pub dot_color: usize,
}
impl Step {
pub fn width(&self) -> usize {
self.before
.len()
.max(self.at.len())
.max(self.pre_shift.len())
.max(self.after.len())
}
}
#[derive(Default)]
pub struct Lanes {
slots: Vec<Option<Lane>>,
next_color: usize,
clock: u64,
evicted: bool,
}
impl Lanes {
pub fn new() -> Lanes {
Lanes::default()
}
#[cfg(test)]
fn awaits(&self, hash: &str) -> bool {
self.find(hash).is_some()
}
pub fn open(&self) -> usize {
self.slots.iter().filter(|s| s.is_some()).count()
}
pub fn width(&self) -> usize {
self.slots
.iter()
.rposition(|s| s.is_some())
.map_or(0, |i| i + 1)
}
pub fn advance(&mut self, hash: &str, parents: &[&str]) -> Step {
self.clock += 1;
let col = match self.find(hash) {
Some(i) => i,
None => self.claim(hash),
};
if let Some(lane) = self.slots[col].as_mut() {
lane.touched = self.clock;
}
let before = self.snapshot();
let mut closing = Vec::new();
for j in 0..self.slots.len() {
if j != col
&& self.slots[j]
.as_ref()
.is_some_and(|l| l.waiting_for == hash)
{
self.slots[j] = None;
closing.push(j);
}
}
let at = self.snapshot();
let dot_color = self.slots[col].as_ref().map_or(0, |l| l.color);
match parents.first() {
Some(p) => {
if let Some(lane) = self.slots[col].as_mut() {
lane.waiting_for = (*p).to_string();
}
}
None => self.slots[col] = None,
}
let mut opening = Vec::new();
for p in parents.iter().skip(1) {
let k = match self.find(p) {
Some(k) => k,
None => self.claim(p),
};
if k != col {
opening.push(k);
}
}
let colors = self.color_map();
let pre_shift = self.snapshot();
let shifts = self.compact();
Step {
col,
before,
at,
pre_shift,
after: self.snapshot(),
closing,
opening,
shifts,
is_merge: parents.len() > 1,
colors,
colors_after: self.color_map(),
dot_color,
}
}
fn compact(&mut self) -> Vec<(usize, usize)> {
let mut shifts = Vec::new();
for i in 0..self.slots.len().saturating_sub(1) {
if self.slots[i].is_none() && self.slots[i + 1].is_some() {
self.slots[i] = self.slots[i + 1].take();
shifts.push((i + 1, i));
}
}
while matches!(self.slots.last(), Some(None)) {
self.slots.pop();
}
shifts
}
fn find(&self, hash: &str) -> Option<usize> {
self.slots
.iter()
.position(|s| s.as_ref().is_some_and(|l| l.waiting_for == hash))
}
pub fn evicted(&self) -> bool {
self.evicted
}
fn claim(&mut self, hash: &str) -> usize {
let lane = Lane {
waiting_for: hash.to_string(),
color: self.next_color,
touched: self.clock,
};
self.next_color = self.next_color.wrapping_add(1);
if let Some(i) = self.slots.iter().position(|s| s.is_none()) {
self.slots[i] = Some(lane);
return i;
}
if self.slots.len() < MAX_LANES {
self.slots.push(Some(lane));
return self.slots.len() - 1;
}
let victim = self
.slots
.iter()
.enumerate()
.filter(|(_, s)| s.as_ref().is_some_and(|l| l.touched < self.clock))
.min_by_key(|(_, s)| s.as_ref().map_or(0, |l| l.touched))
.map(|(i, _)| i);
match victim {
Some(i) => {
self.evicted = true;
self.slots[i] = Some(lane);
i
}
None => {
self.slots.push(Some(lane));
self.slots.len() - 1
}
}
}
fn snapshot(&self) -> Vec<bool> {
let mut v: Vec<bool> = self.slots.iter().map(|s| s.is_some()).collect();
while matches!(v.last(), Some(false)) {
v.pop();
}
v
}
fn color_map(&self) -> Vec<usize> {
self.slots
.iter()
.map(|s| s.as_ref().map_or(0, |l| l.color))
.collect()
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn linear_history_stays_in_one_lane() {
let mut l = Lanes::new();
let a = l.advance("a", &["b"]);
let b = l.advance("b", &["c"]);
let c = l.advance("c", &[]);
for s in [&a, &b] {
assert_eq!(s.col, 0);
assert_eq!(s.before, vec![true]);
assert_eq!(s.after, vec![true]);
assert!(s.closing.is_empty() && s.opening.is_empty());
assert!(s.shifts.is_empty());
}
assert_eq!(c.at, vec![true]);
assert_eq!(c.after, Vec::<bool>::new());
}
#[test]
fn merge_opens_a_lane_and_fork_closes_it() {
let mut l = Lanes::new();
let m = l.advance("m", &["a", "s"]);
assert_eq!(m.col, 0);
assert!(m.is_merge);
assert_eq!(m.at, vec![true], "the dot sits alone before branching");
assert_eq!(m.opening, vec![1], "the side parent gets its own lane");
assert_eq!(m.after, vec![true, true]);
let a = l.advance("a", &["r"]);
assert_eq!(a.col, 0);
assert!(a.opening.is_empty() && a.closing.is_empty());
let s = l.advance("s", &["r"]);
assert_eq!(s.col, 1);
assert_eq!(s.after, vec![true, true]);
let r = l.advance("r", &[]);
assert_eq!(r.col, 0, "the fork resolves into the leftmost lane");
assert_eq!(r.before, vec![true, true], "both lanes are live above it");
assert_eq!(r.closing, vec![1], "the second lane folds in");
assert_eq!(r.at, vec![true], "and is gone by the dot's own row");
assert_eq!(l.open(), 0);
}
#[test]
fn octopus_merge_opens_every_extra_parent() {
let mut l = Lanes::new();
let m = l.advance("m", &["p1", "p2", "p3"]);
assert!(m.is_merge);
assert_eq!(m.opening, vec![1, 2]);
assert_eq!(m.after, vec![true, true, true]);
assert_eq!(l.open(), 3);
}
#[test]
fn a_branch_keeps_its_colour_for_life() {
let mut l = Lanes::new();
let m = l.advance("m", &["a", "s"]);
let side = m.colors_after[1];
assert_ne!(side, m.dot_color, "a new branch gets its own colour");
l.advance("a", &["r"]);
let s = l.advance("s", &["r"]);
assert_eq!(s.dot_color, side, "the side branch keeps that colour");
}
#[test]
fn a_freed_column_is_closed_up_by_shifting() {
let mut l = Lanes::new();
l.advance("m", &["a", "s"]);
let a = l.advance("a", &[]);
assert_eq!(a.shifts, vec![(1, 0)], "the live lane slides left");
assert_eq!(a.after, vec![true]);
assert_eq!(l.width(), 1, "no hole is left behind");
}
#[test]
fn compaction_keeps_width_near_the_number_of_live_lanes() {
let mut l = Lanes::new();
l.advance("m", &["p0", "p1", "p2", "p3", "p4"]);
assert_eq!(l.width(), 5);
for h in ["p0", "p1", "p2"] {
l.advance(h, &[]);
}
for h in ["p3", "p4"] {
l.advance(h, &[&format!("{}-next", h)]);
}
assert_eq!(l.open(), 2);
assert_eq!(l.width(), 2, "width tracks live lanes, not peak lanes");
}
#[test]
fn a_filtered_log_cannot_grow_the_lane_table_without_bound() {
let mut l = Lanes::new();
for i in 0..5_000u32 {
let hash = format!("commit-{}", i);
let missing = format!("never-shown-{}", i);
l.advance(&hash, &[missing.as_str()]);
assert!(
l.open() <= MAX_LANES,
"lane table reached {} at commit {}",
l.open(),
i
);
}
assert_eq!(l.open(), MAX_LANES, "the ceiling is what bounds it");
}
#[test]
fn a_merge_wider_than_the_ceiling_keeps_every_parent() {
let parents: Vec<String> = (0..MAX_LANES + 2).map(|i| format!("p{:03}", i)).collect();
let refs: Vec<&str> = parents.iter().map(String::as_str).collect();
let mut l = Lanes::new();
let s = l.advance("octopus", &refs);
assert_eq!(
s.opening.len(),
refs.len() - 1,
"every parent past the first needs its own lane"
);
assert!(
l.awaits(&parents[0]),
"the merge must still be waiting for its own first parent"
);
assert!(
!l.evicted(),
"growing for one commit's parents is not an eviction"
);
assert_eq!(l.open(), refs.len());
}
#[test]
fn eviction_is_reported_so_the_drawing_is_not_passed_off_as_exact() {
let mut l = Lanes::new();
assert!(!l.evicted());
for i in 0..MAX_LANES as u32 {
l.advance(&format!("c{}", i), &[format!("p{}", i).as_str()]);
}
assert_eq!(l.open(), MAX_LANES);
assert!(!l.evicted(), "the table filled without evicting anything");
l.advance("one-too-many", &["another"]);
assert!(l.evicted(), "an edge was dropped and nobody was told");
}
#[test]
fn eviction_takes_the_stalest_lane() {
let mut l = Lanes::new();
for i in 0..MAX_LANES as u32 {
l.advance(&format!("c{}", i), &[format!("p{}", i).as_str()]);
}
assert_eq!(l.open(), MAX_LANES);
let revived = l.advance("p0", &["p0-next"]);
let col = revived.col;
l.advance("brand-new", &["another"]);
assert!(
l.awaits("p0-next"),
"the freshly touched lane was evicted instead of a stale one"
);
let _ = col;
}
#[test]
fn state_is_bounded_by_open_lanes_not_history() {
let mut l = Lanes::new();
for i in 0..10_000u32 {
let h = i.to_string();
let p = (i + 1).to_string();
l.advance(&h, &[p.as_str()]);
assert_eq!(l.open(), 1);
}
}
}