Something went wrong. Try again.
A 5e storytelling engine with an LLM DM
Something went wrong. Try again.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463//! Finds the first place two word streams diverge and describes it.//!//! The edit script is a Levenshtein alignment (insert, delete, substitute//! each cost one word) rather than a longest-common-subsequence alignment,//! because a single changed word should read as one substitution, not as a//! drop immediately followed by an unrelated add. Building that alignment//! costs one `u32` cell per pair of words still under consideration after//! trimming, so a pair of streams with little in common (a chapter file//! paired against the wrong entry, say) can demand an allocation far//! larger than the words involved would suggest; `first_divergence` falls//! back to a cheaper, coarser report rather than let that grow unbounded.
const CONTEXT_WORDS: usize = 3;
/// The most alignment-matrix cells `first_divergence` will build before/// falling back to `bounded_divergence`. At 4 bytes per `u32` cell, this/// caps the matrix at 32 MB. A 68,000-word chapter file mismatched against/// a 10,000-word entry, the shape of input that has triggered this before,/// would otherwise ask for roughly 680,000,000 cells: 2.7 GB.const MAX_ALIGNMENT_CELLS: usize = 8_000_000;
enum Op { Equal(String), Delete(String), Insert(String), Substitute(String, String),}
/// What kind of divergence an `Op` describes, or `None` for `Op::Equal`./// Splitting this out of `first_divergence` means every arm, including/// the equal case, runs during the scan for the first mismatch, rather/// than only at one already-known-non-equal index.fn template(op: &Op) -> Option<String> { match op { Op::Equal(_) => None, Op::Delete(word) => Some(format!( "source has \"{word}\" but the corpus body drops it" )), Op::Insert(word) => Some(format!( "corpus body adds \"{word}\", which the source does not have" )), Op::Substitute(source_word, corpus_word) => Some(format!( "source has \"{source_word}\" but the corpus body has \"{corpus_word}\"" )), }}
/// Describes the first divergence between `source` and `corpus`, or `None`/// if the two word streams are identical.////// Equal streams return immediately, without allocating the alignment/// matrix. On a mismatch, the common prefix and common suffix are trimmed/// off both streams first, so the matrix only covers the words that/// actually differ; the trimmed words still supply context when the/// divergence sits too close to either end of what remains. When even the/// trimmed streams are too large for the matrix to stay under/// `MAX_ALIGNMENT_CELLS`, this reports the first position where the/// trimmed streams disagree instead of computing the full alignment: a/// coarser report (an insert or delete part way through can read as a run/// of substitutions), but one that costs no more memory than the streams/// themselves.pub fn first_divergence(source: &[String], corpus: &[String]) -> Option<String> { if source == corpus { return None; }
let prefix_len = common_prefix_len(source, corpus); let suffix_len = common_suffix_len(&source[prefix_len..], &corpus[prefix_len..]); let prefix = &source[..prefix_len]; let suffix = &source[source.len() - suffix_len..]; let source_middle = &source[prefix_len..source.len() - suffix_len]; let corpus_middle = &corpus[prefix_len..corpus.len() - suffix_len];
if alignment_cells(source_middle.len(), corpus_middle.len()) > MAX_ALIGNMENT_CELLS { return Some(bounded_divergence( source_middle, corpus_middle, prefix, suffix, )); }
let ops = edit_script(source_middle, corpus_middle); let (index, message) = ops .iter() .enumerate() .find_map(|(i, op)| template(op).map(|message| (i, message)))?; let before = context_before(&ops, index, prefix); let after = context_after(&ops, index, suffix); let context = format!("{before} ... {after}").trim().to_string(); Some(format!("{message} (context: {context})"))}
/// How many cells an alignment matrix over streams of these lengths would/// need: one row per source word plus the empty prefix, one column per/// corpus word plus the empty prefix.fn alignment_cells(source_len: usize, corpus_len: usize) -> usize { (source_len + 1).saturating_mul(corpus_len + 1)}
/// Reports the first position where two already-trimmed word streams/// disagree, comparing them word by word instead of computing an/// alignment. Because nothing here realigns the streams after a mismatch,/// an insert or delete part way through reads as a run of substitutions/// rather than as the single insert or delete `edit_script` would find;/// `first_divergence` only reaches this when the streams are too large for/// that better report to be worth its memory.fn bounded_divergence( source_middle: &[String], corpus_middle: &[String], prefix: &[String], suffix: &[String],) -> String { let len = source_middle.len().max(corpus_middle.len()); let index = (0..len) .find(|&i| source_middle.get(i) != corpus_middle.get(i)) .expect("first_divergence only calls this with streams already confirmed unequal");
let source_word = source_middle.get(index); let corpus_word = corpus_middle.get(index); let message = if let (Some(source_word), Some(corpus_word)) = (source_word, corpus_word) { format!("source has \"{source_word}\" but the corpus body has \"{corpus_word}\"") } else if let Some(source_word) = source_word { format!("source has \"{source_word}\" but the corpus body drops it") } else { let corpus_word = corpus_word.expect("index is within source_middle or corpus_middle"); format!("corpus body adds \"{corpus_word}\", which the source does not have") };
let context_stream = if index < source_middle.len() { source_middle } else { corpus_middle }; let before = bounded_context_before(context_stream, index, prefix); let after = bounded_context_after(context_stream, index, suffix); let context = format!("{before} ... {after}").trim().to_string(); format!("{message} (context: {context})")}
/// The last few words of `stream` before `index`, in reading order, filled/// in from `prefix` when `stream` alone doesn't hold enough. Mirrors/// `context_before`, but reads a plain word slice instead of `Op`s.fn bounded_context_before(stream: &[String], index: usize, prefix: &[String]) -> String { let mut words: Vec<&str> = stream[..index] .iter() .rev() .take(CONTEXT_WORDS) .map(String::as_str) .collect(); if words.len() < CONTEXT_WORDS { let remaining = CONTEXT_WORDS - words.len(); words.extend(prefix.iter().rev().take(remaining).map(String::as_str)); } words.reverse(); words.join(" ")}
/// The next few words of `stream` after `index`, in reading order, filled/// in from `suffix` when `stream` alone doesn't hold enough. Mirrors/// `context_after`, but reads a plain word slice instead of `Op`s.fn bounded_context_after(stream: &[String], index: usize, suffix: &[String]) -> String { let mut words: Vec<&str> = stream .get(index + 1..) .unwrap_or(&[]) .iter() .take(CONTEXT_WORDS) .map(String::as_str) .collect(); if words.len() < CONTEXT_WORDS { let remaining = CONTEXT_WORDS - words.len(); words.extend(suffix.iter().take(remaining).map(String::as_str)); } words.join(" ")}
/// How many leading words `source` and `corpus` share.fn common_prefix_len(source: &[String], corpus: &[String]) -> usize { source .iter() .zip(corpus.iter()) .take_while(|(a, b)| a == b) .count()}
/// How many trailing words `source` and `corpus` share. Comparing from the/// end and stopping at the first zipped mismatch naturally caps the count/// at the shorter stream's length, so a stream that is a prefix of the/// other never double-counts words already claimed by the common prefix.fn common_suffix_len(source: &[String], corpus: &[String]) -> usize { source .iter() .rev() .zip(corpus.iter().rev()) .take_while(|(a, b)| a == b) .count()}
/// Aligns `source` against `corpus` word by word, minimizing the number of/// single-word inserts, deletes, and substitutions.fn edit_script(source: &[String], corpus: &[String]) -> Vec<Op> { let (n, m) = (source.len(), corpus.len()); let mut distance = vec![vec![0u32; m + 1]; n + 1]; for (i, row) in distance.iter_mut().enumerate() { row[0] = i as u32; } for (j, cell) in distance[0].iter_mut().enumerate() { *cell = j as u32; } for i in 1..=n { for j in 1..=m { distance[i][j] = if source[i - 1] == corpus[j - 1] { distance[i - 1][j - 1] } else { 1 + distance[i - 1][j - 1] .min(distance[i - 1][j]) .min(distance[i][j - 1]) }; } }
let mut ops = Vec::new(); let (mut i, mut j) = (n, m); while i > 0 || j > 0 { if i > 0 && j > 0 && source[i - 1] == corpus[j - 1] { ops.push(Op::Equal(source[i - 1].clone())); i -= 1; j -= 1; } else if i > 0 && j > 0 && distance[i][j] == distance[i - 1][j - 1] + 1 { ops.push(Op::Substitute(source[i - 1].clone(), corpus[j - 1].clone())); i -= 1; j -= 1; } else if i > 0 && distance[i][j] == distance[i - 1][j] + 1 { ops.push(Op::Delete(source[i - 1].clone())); i -= 1; } else { ops.push(Op::Insert(corpus[j - 1].clone())); j -= 1; } } ops.reverse(); ops}
/// The last few equal words before `ops[index]`, in reading order. When/// `ops` itself does not hold enough equal words, the words trimmed off/// the common prefix before the alignment ran fill in the rest.fn context_before(ops: &[Op], index: usize, prefix: &[String]) -> String { let mut words: Vec<&str> = ops[..index] .iter() .rev() .filter_map(equal_word) .take(CONTEXT_WORDS) .collect(); if words.len() < CONTEXT_WORDS { let remaining = CONTEXT_WORDS - words.len(); words.extend(prefix.iter().rev().take(remaining).map(String::as_str)); } words.reverse(); words.join(" ")}
/// The next few equal words after `ops[index]`, in reading order. When/// `ops` itself does not hold enough equal words, the words trimmed off/// the common suffix before the alignment ran fill in the rest.fn context_after(ops: &[Op], index: usize, suffix: &[String]) -> String { let mut words: Vec<&str> = ops[index + 1..] .iter() .filter_map(equal_word) .take(CONTEXT_WORDS) .collect(); if words.len() < CONTEXT_WORDS { let remaining = CONTEXT_WORDS - words.len(); words.extend(suffix.iter().take(remaining).map(String::as_str)); } words.join(" ")}
fn equal_word(op: &Op) -> Option<&str> { match op { Op::Equal(word) => Some(word.as_str()), _ => None, }}
#[cfg(test)]mod tests { use super::*;
fn words(text: &str) -> Vec<String> { text.split_whitespace().map(str::to_string).collect() }
#[test] fn template_is_none_for_an_equal_op() { assert_eq!(template(&Op::Equal("a".to_string())), None); }
#[test] fn context_skips_a_second_nearby_divergence() { let message = first_divergence(&words("a b c d e f g"), &words("a b X d Y f g")).unwrap(); assert!(message.contains("context: a b ... d f g")); }
#[test] fn identical_streams_have_no_divergence() { assert_eq!(first_divergence(&words("a b c"), &words("a b c")), None); }
#[test] fn common_prefix_len_counts_leading_shared_words() { assert_eq!(common_prefix_len(&words("a b c"), &words("a b x")), 2); }
#[test] fn common_prefix_len_is_zero_without_a_shared_first_word() { assert_eq!(common_prefix_len(&words("a b c"), &words("x b c")), 0); }
#[test] fn common_suffix_len_counts_trailing_shared_words() { assert_eq!(common_suffix_len(&words("a b c"), &words("x b c")), 2); }
#[test] fn common_suffix_len_caps_at_the_shorter_streams_length() { assert_eq!(common_suffix_len(&words("a b c"), &words("c")), 1); }
#[test] fn reports_an_extra_trailing_word_when_source_is_a_strict_prefix() { let message = first_divergence(&words("a b"), &words("a b b")).unwrap(); assert!(message.contains("adds")); assert!(message.contains("\"b\"")); }
#[test] fn reports_a_missing_trailing_word_when_corpus_is_a_strict_prefix() { let message = first_divergence(&words("a b b"), &words("a b")).unwrap(); assert!(message.contains("drops it")); assert!(message.contains("\"b\"")); }
#[test] fn a_single_word_change_deep_in_a_long_stream_stays_isolated() { let mut source_text = "filler ".repeat(500); source_text.push_str("roar"); let mut corpus_text = "filler ".repeat(500); corpus_text.push_str("roars");
let message = first_divergence(&words(&source_text), &words(&corpus_text)).unwrap();
assert!(message.contains("\"roar\"")); assert!(message.contains("\"roars\"")); assert!(message.contains("context: filler filler filler ...")); }
#[test] fn reports_a_dropped_word() { let message = first_divergence( &words("the low roar into the fire"), &words("the low into the fire"), ) .unwrap(); assert!(message.contains("drops it")); assert!(message.contains("\"roar\"")); assert!(message.contains("the low ... into the fire")); }
#[test] fn reports_an_added_word() { let message = first_divergence( &words("the low roar into"), &words("the low roar loud into"), ) .unwrap(); assert!(message.contains("adds")); assert!(message.contains("\"loud\"")); }
#[test] fn reports_a_changed_word() { let message = first_divergence(&words("a low roar into"), &words("a low roars into")).unwrap(); assert!(message.contains("\"roar\"")); assert!(message.contains("\"roars\"")); }
#[test] fn context_is_short_at_the_start_of_the_stream() { let message = first_divergence(&words("roar into fire"), &words("roars into fire")).unwrap(); assert!(message.contains("context: ... into fire")); }
#[test] fn alignment_cells_counts_rows_times_columns_including_the_empty_prefix() { assert_eq!(alignment_cells(2, 3), 3 * 4); }
#[test] fn a_small_entirely_mismatched_pair_stays_under_the_ceiling() { // A stream this size, entirely mismatched, keeps the trimmed // middle's cell count comfortably under the ceiling, so this still // takes the full alignment path. Pairs this size (or the existing // under-500-word tests above) are the "existing nicer report" // behavior the ceiling must leave unchanged. let source: Vec<String> = (0..50).map(|i| format!("s{i}")).collect(); let corpus: Vec<String> = (0..50).map(|i| format!("c{i}")).collect();
assert!(alignment_cells(source.len(), corpus.len()) <= MAX_ALIGNMENT_CELLS); let message = first_divergence(&source, &corpus).unwrap(); assert!(message.contains("\"s0\"")); assert!(message.contains("\"c0\"")); }
#[test] fn a_pair_of_streams_over_the_alignment_ceiling_uses_the_bounded_report() { // Every word differs and neither end matches, so prefix/suffix // trimming can't shrink the middle: the whole streams count // toward the cell ceiling, the same shape of input a mismatched // `source:` field produces on a real chapter file. let side = (MAX_ALIGNMENT_CELLS as f64).sqrt() as usize + 10; let source: Vec<String> = vec!["a".to_string(); side]; let corpus: Vec<String> = vec!["b".to_string(); side]; assert!(alignment_cells(source.len(), corpus.len()) > MAX_ALIGNMENT_CELLS);
let message = first_divergence(&source, &corpus).unwrap();
assert!(message.contains("source has \"a\" but the corpus body has \"b\"")); }
#[test] fn bounded_divergence_reports_a_substitution() { let message = bounded_divergence(&words("a b c"), &words("a x c"), &[], &[]); assert!(message.contains("source has \"b\" but the corpus body has \"x\"")); assert!(message.contains("context: a ... c")); }
#[test] fn bounded_divergence_reports_a_source_only_tail() { let message = bounded_divergence(&words("a b"), &words("a"), &[], &[]); assert!(message.contains("source has \"b\" but the corpus body drops it")); }
#[test] fn bounded_divergence_reports_a_corpus_only_tail() { let message = bounded_divergence(&words("a"), &words("a b"), &[], &[]); assert!(message.contains("corpus body adds \"b\", which the source does not have")); }
#[test] fn bounded_divergence_fills_in_context_from_the_trimmed_prefix_and_suffix() { let message = bounded_divergence( &words("roar"), &words("roars"), &words("well into the"), &words("fire indeed"), ); assert!(message.contains("context: well into the ... fire indeed")); }}