use regex::Regex;
use serde_json::{json, Map, Value};
use std::sync::LazyLock;
static WORD_RE: LazyLock<Regex> = LazyLock::new(|| Regex::new(r"\w+").expect("valid regex"));
pub const DEFAULT_MIN_COVERAGE: f64 = 0.75;
pub const DENSITY_GATE: f64 = 1.0 / 3.0;
const MAX_LCS_TOKENS: usize = 1024;
const WINDOW_FACTOR: usize = 4;
#[derive(Debug, Clone, PartialEq)]
pub struct ProvenanceConfig {
pub enabled: bool,
pub min_coverage: f64,
}
impl Default for ProvenanceConfig {
fn default() -> Self {
Self {
enabled: false,
min_coverage: DEFAULT_MIN_COVERAGE,
}
}
}
impl ProvenanceConfig {
pub fn from_settings(settings: &crate::config::settings::LLMSettings) -> Self {
Self {
enabled: settings.provenance_enabled,
min_coverage: settings.provenance_min_coverage,
}
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct CharInterval {
pub start: usize,
pub end: usize,
}
#[derive(Debug, Clone, PartialEq)]
pub struct AlignMatch {
pub interval: CharInterval,
pub coverage: f64,
}
#[derive(Debug, Clone)]
struct Token {
lower: String,
start: usize,
len: usize,
}
pub fn tokenize(s: &str) -> Vec<(String, usize)> {
tokenize_tokens(s)
.into_iter()
.map(|t| (t.lower, t.start))
.collect()
}
fn tokenize_tokens(s: &str) -> Vec<Token> {
let mut char_of_byte: std::collections::HashMap<usize, usize> =
std::collections::HashMap::new();
for (ci, (bi, _)) in s.char_indices().enumerate() {
char_of_byte.insert(bi, ci);
}
char_of_byte.insert(s.len(), s.chars().count());
WORD_RE
.find_iter(s)
.map(|m| {
let start = char_of_byte.get(&m.start()).copied().unwrap_or(0);
let end = char_of_byte.get(&m.end()).copied().unwrap_or(start);
Token {
lower: m.as_str().to_lowercase(),
start,
len: end.saturating_sub(start),
}
})
.collect()
}
pub fn align(source: &str, excerpt: &str, min_coverage: f64) -> Option<AlignMatch> {
if excerpt.is_empty() || source.is_empty() {
return None;
}
align_tokens(
&tokenize_tokens(source),
&tokenize_tokens(excerpt),
source,
excerpt,
min_coverage,
)
}
fn align_tokens(
src: &[Token],
ex: &[Token],
source: &str,
excerpt: &str,
min_coverage: f64,
) -> Option<AlignMatch> {
if ex.is_empty() || src.is_empty() {
return None;
}
let m = ex.len();
let need = ((min_coverage * m as f64).ceil() as usize).clamp(1, m);
let greedy = greedy_match(src, ex, m - need);
if let Some(res) = greedy_resolved(src, ex, &greedy, need, m) {
return Some(res);
}
let window = dp_window(src, ex, &greedy.matches, excerpt, source)?;
let matched = lcs_match(&src[window.clone()], ex);
if matched.len() < need {
return None;
}
let src_idx: Vec<usize> = matched.iter().map(|&j| window.start + j).collect();
gates(src, ex, &src_idx, need, m)
}
fn greedy_match(src: &[Token], ex: &[Token], allowed_miss: usize) -> GreedyResult {
let mut matches: Vec<usize> = Vec::new();
let mut j = 0usize;
let mut unmatched = 0usize;
for t in ex {
match find_next_token(src, j, &t.lower) {
Some(k) => {
matches.push(k);
j = k + 1;
}
None => {
unmatched += 1;
if unmatched > allowed_miss {
return GreedyResult {
matches,
pruned: true,
};
}
}
}
}
GreedyResult {
matches,
pruned: false,
}
}
fn find_next_token(src: &[Token], from: usize, lower: &str) -> Option<usize> {
let mut j = from;
while j < src.len() {
if src[j].lower == lower {
return Some(j);
}
j += 1;
}
None
}
struct GreedyResult {
matches: Vec<usize>,
pruned: bool,
}
fn greedy_resolved(
src: &[Token],
ex: &[Token],
greedy: &GreedyResult,
need: usize,
m: usize,
) -> Option<AlignMatch> {
if greedy.pruned || greedy.matches.len() < need {
return None;
}
gates(src, ex, &greedy.matches, need, m)
}
fn gates(
src: &[Token],
ex: &[Token],
matched_src_idx: &[usize],
need: usize,
m: usize,
) -> Option<AlignMatch> {
if matched_src_idx.len() < need {
return None;
}
let first = &src[matched_src_idx[0]];
let last = &src[*matched_src_idx.last()?];
let interval_chars = (last.start + last.len).saturating_sub(first.start);
if interval_chars == 0 {
return None;
}
let matched_chars: usize = matched_src_idx
.iter()
.enumerate()
.map(|(i, _src_idx)| ex[i].len)
.sum();
let density = matched_chars as f64 / interval_chars as f64;
if density < DENSITY_GATE {
return None;
}
Some(AlignMatch {
interval: CharInterval {
start: first.start,
end: last.start + last.len,
},
coverage: matched_src_idx.len() as f64 / m as f64,
})
}
fn dp_window(
src: &[Token],
ex: &[Token],
greedy_matches: &[usize],
excerpt: &str,
source: &str,
) -> Option<std::ops::Range<usize>> {
if ex.len() > MAX_LCS_TOKENS {
return None;
}
let excerpt_chars = excerpt.chars().count().max(1);
let anchor = greedy_matches
.first()
.map(|&i| src[i].start)
.or_else(|| {
ex.iter()
.filter_map(|t| src.iter().find(|s| s.lower == t.lower).map(|s| s.start))
.min()
})?;
let lo = anchor.saturating_sub(excerpt_chars);
let hi = greedy_matches
.last()
.map(|&i| src[i].start + src[i].len + excerpt_chars)
.unwrap_or(anchor + excerpt_chars * WINDOW_FACTOR)
.min(source.chars().count());
let start = src.partition_point(|t| t.start + t.len <= lo);
let end = src.partition_point(|t| t.start < hi);
if end <= start || end - start > MAX_LCS_TOKENS {
return None;
}
Some(start..end)
}
fn lcs_match(src: &[Token], ex: &[Token]) -> Vec<usize> {
let n = src.len();
let m = ex.len();
if n == 0 || m == 0 {
return Vec::new();
}
let w = m + 1;
let dp = lcs_length_table(src, ex, n, m, w);
backtrack_lcs(src, ex, n, m, w, &dp)
}
fn lcs_length_table(src: &[Token], ex: &[Token], n: usize, m: usize, w: usize) -> Vec<u32> {
let mut dp = vec![0u32; (n + 1) * w];
for i in 1..=n {
for j in 1..=m {
dp[i * w + j] = if src[i - 1].lower == ex[j - 1].lower {
dp[(i - 1) * w + (j - 1)] + 1
} else {
dp[(i - 1) * w + j].max(dp[i * w + (j - 1)])
};
}
}
dp
}
fn backtrack_lcs(
src: &[Token],
ex: &[Token],
mut i: usize,
mut j: usize,
w: usize,
dp: &[u32],
) -> Vec<usize> {
let mut res = Vec::new();
while i > 0 && j > 0 {
if src[i - 1].lower == ex[j - 1].lower {
res.push(i - 1);
i -= 1;
j -= 1;
} else if dp[(i - 1) * w + j] >= dp[i * w + (j - 1)] {
i -= 1;
} else {
j -= 1;
}
}
res.reverse();
res
}
pub fn provenance_map(source: &str, value: &Value, min_coverage: f64) -> Value {
let src_tokens = tokenize_tokens(source);
let mut map = Map::new();
collect_provenance(
&src_tokens,
source,
value,
String::new(),
min_coverage,
&mut map,
);
Value::Object(map)
}
fn collect_provenance(
src_tokens: &[Token],
source: &str,
value: &Value,
path: String,
min_coverage: f64,
out: &mut Map<String, Value>,
) {
match value {
Value::Object(m) => {
for (k, v) in m {
if k == "_provenance" {
continue;
}
let child = if path.is_empty() {
k.clone()
} else {
format!("{path}.{k}")
};
collect_provenance(src_tokens, source, v, child, min_coverage, out);
}
}
Value::Array(arr) => {
for (i, v) in arr.iter().enumerate() {
collect_provenance(
src_tokens,
source,
v,
format!("{path}[{i}]"),
min_coverage,
out,
);
}
}
Value::String(s) => {
let key = if path.is_empty() {
"$".to_string()
} else {
path
};
let entry = string_leaf_entry(src_tokens, source, s, min_coverage);
out.insert(key, entry);
}
_ => {}
}
}
fn string_leaf_entry(src_tokens: &[Token], source: &str, leaf: &str, min_coverage: f64) -> Value {
match align_tokens(
src_tokens,
&tokenize_tokens(leaf),
source,
leaf,
min_coverage,
) {
Some(m) => json!({
"start": m.interval.start,
"end": m.interval.end,
"coverage": m.coverage,
}),
None => Value::Null,
}
}
pub fn attach_provenance(result: &mut Value, provenance: &Value) {
match result {
Value::Object(map) => {
if map.contains_key("_provenance") {
log::warn!("provenance: result already has _provenance key; overwriting");
}
map.insert("_provenance".to_string(), provenance.clone());
}
_ => {
log::warn!("provenance: result is not a JSON object; skip attaching _provenance");
}
}
}
pub fn apply_provenance(
source: &str,
mut result: Value,
cfg: &ProvenanceConfig,
) -> (Value, Option<Value>) {
if !cfg.enabled {
return (result, None);
}
let map = provenance_map(source, &result, cfg.min_coverage);
let non_empty = map.as_object().is_some_and(|m| !m.is_empty());
if non_empty {
attach_provenance(&mut result, &map);
}
(result, Some(map))
}
pub fn slice_char_range(source: &str, interval: &CharInterval) -> String {
source
.chars()
.skip(interval.start)
.take(interval.end.saturating_sub(interval.start))
.collect()
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn tokenize_lowercases_and_reports_char_offsets() {
let toks = tokenize("Hello 世界, Rust Crawler");
assert_eq!(
toks,
vec![
("hello".to_string(), 0),
("世界".to_string(), 6),
("rust".to_string(), 10),
("crawler".to_string(), 15),
]
);
}
#[test]
fn tokenize_cjk_contiguous_run_is_single_token() {
let toks = tokenize("今天天气很好,我们去公园散步。");
assert_eq!(
toks,
vec![
("今天天气很好".to_string(), 0),
("我们去公园散步".to_string(), 7),
]
);
}
#[test]
fn align_exact_ascii_substring_returns_correct_interval() {
let source = "The quick brown fox jumps over the lazy dog.";
let m = align(source, "quick brown fox", DEFAULT_MIN_COVERAGE)
.expect("exact substring must align");
assert_eq!(m.coverage, 1.0);
assert_eq!(slice_char_range(source, &m.interval), "quick brown fox");
}
#[test]
fn align_exact_cjk_substring_char_offsets_safe() {
let source = "今天天气很好,我们去公园散步。";
let m =
align(source, "今天天气很好", DEFAULT_MIN_COVERAGE).expect("CJK substring must align");
assert_eq!(m.coverage, 1.0);
assert_eq!(m.interval.start, 0);
assert_eq!(m.interval.end, 6);
assert_eq!(slice_char_range(source, &m.interval), "今天天气很好");
}
#[test]
fn align_cjk_substring_in_middle_char_offsets_not_bytes() {
let source = "前言三字。今天天气很好,后文。";
let m = align(source, "今天天气很好", DEFAULT_MIN_COVERAGE).expect("CJK middle substring");
assert_eq!(slice_char_range(source, &m.interval), "今天天气很好");
}
#[test]
fn align_tolerates_reworded_excerpt_when_coverage_passes_gate() {
let source = "The quick brown fox jumps over the lazy dog.";
let m = align(source, "a quick brown fox jumps", DEFAULT_MIN_COVERAGE)
.expect("majority-ordered rewrite must align");
assert!(m.coverage >= 0.75, "coverage = {}", m.coverage);
assert_eq!(
slice_char_range(source, &m.interval),
"quick brown fox jumps"
);
}
#[test]
fn align_tolerates_missing_tokens_with_dense_interval() {
let source = "alpha beta delta epsilon";
let m = align(source, "alpha beta gamma delta", DEFAULT_MIN_COVERAGE)
.expect("3/4 tokens in order");
assert!((m.coverage - 0.75).abs() < 1e-9);
assert_eq!(slice_char_range(source, &m.interval), "alpha beta delta");
}
#[test]
fn align_scattered_tokens_fail_density_gate() {
let source = "alpha a1 a2 a3 a4 a5 a6 a7 a8 beta";
let m = align(source, "alpha beta", DEFAULT_MIN_COVERAGE);
assert!(m.is_none(), "sparse interval must be rejected");
}
#[test]
fn align_hallucinated_excerpt_returns_none() {
let source = "The quick brown fox jumps over the lazy dog.";
assert!(align(
source,
"purple elephant unicorn riding",
DEFAULT_MIN_COVERAGE
)
.is_none());
assert!(align(
source,
" completely fabricated words here ",
DEFAULT_MIN_COVERAGE
)
.is_none());
}
#[test]
fn align_coverage_gate_boundary_rejects_0_74_accepts_0_75() {
let source_of = |words: usize| {
let mut source = String::new();
for i in 0..words {
source.push_str(&format!("w{i:03} f{i:03} "));
}
source
};
let excerpt: String = (0..100)
.map(|i| format!("w{i:03}"))
.collect::<Vec<_>>()
.join(" ");
let source_75 = source_of(75);
let hit = align(&source_75, &excerpt, DEFAULT_MIN_COVERAGE).expect("0.75 must pass");
assert!((hit.coverage - 0.75).abs() < 1e-9);
assert!(slice_char_range(&source_75, &hit.interval).starts_with("w000"));
let source_74 = source_of(74);
let miss = align(&source_74, &excerpt, DEFAULT_MIN_COVERAGE);
assert!(miss.is_none(), "0.74 must be rejected by coverage gate");
}
#[test]
fn align_density_gate_boundary() {
let sparse = "alpha a1 a2 a3 a4 a5 a6 a7 a8 beta";
assert!(align(sparse, "alpha beta", DEFAULT_MIN_COVERAGE).is_none());
let dense = "alpha x beta";
let m = align(dense, "alpha beta", DEFAULT_MIN_COVERAGE).expect("dense interval passes");
assert_eq!(slice_char_range(dense, &m.interval), "alpha x beta");
}
#[test]
fn align_duplicate_phrase_takes_first_monotone_interval() {
let source = "the quick brown fox naps. later the quick brown fox returns.";
let m = align(source, "quick brown fox", DEFAULT_MIN_COVERAGE).expect("duplicate phrase");
assert_eq!(slice_char_range(source, &m.interval), "quick brown fox");
assert_eq!(m.interval.start, 4, "首个单调可行区间(确定性)");
}
#[test]
fn align_empty_inputs_return_none_without_panic() {
assert!(align("", "anything", DEFAULT_MIN_COVERAGE).is_none());
assert!(align("anything", "", DEFAULT_MIN_COVERAGE).is_none());
assert!(align("", "", DEFAULT_MIN_COVERAGE).is_none());
assert!(align(" \n\t ", " ", DEFAULT_MIN_COVERAGE).is_none());
assert!(align("no word tokens ??? !!!", "___", DEFAULT_MIN_COVERAGE).is_none());
}
#[test]
fn align_50k_char_source_completes_fast() {
let unit = "alpha beta gamma delta ";
let source = unit.repeat(2400); let excerpt = "gamma delta alpha beta";
let start = std::time::Instant::now();
let m = align(&source, excerpt, DEFAULT_MIN_COVERAGE).expect("exact phrase present");
let elapsed = start.elapsed();
assert_eq!(slice_char_range(&source, &m.interval), excerpt);
assert!(
elapsed < std::time::Duration::from_secs(5),
"elapsed = {elapsed:?}"
);
}
#[test]
fn align_50k_char_source_scattered_tokens_bounded() {
let unit = "alpha beta gamma delta ";
let source = unit.repeat(2400);
let excerpt = "delta zeta gamma beta"; let start = std::time::Instant::now();
let _ = align(&source, excerpt, DEFAULT_MIN_COVERAGE);
assert!(
start.elapsed() < std::time::Duration::from_secs(5),
"scattered align must stay bounded, took {:?}",
start.elapsed()
);
}
#[test]
fn provenance_map_nested_object_and_array_paths() {
let source = "Alice wrote Rust in Action in 2023. Chapters: intro, setup.";
let value = json!({
"author": "Alice",
"book": { "title": "Rust in Action", "year": 2023 },
"chapters": ["intro", "setup"]
});
let map = provenance_map(source, &value, DEFAULT_MIN_COVERAGE);
let obj = map.as_object().expect("object map");
let author = &obj["author"];
assert_eq!(author["start"], 0);
assert_eq!(author["end"], 5);
assert_eq!(author["coverage"], 1.0);
assert_eq!(obj["book.title"]["start"], 12);
assert_eq!(obj["book.title"]["coverage"], 1.0);
assert_eq!(obj["chapters[0]"]["coverage"], 1.0);
assert_eq!(obj["chapters[1]"]["coverage"], 1.0);
assert!(!obj.contains_key("book.year"));
}
#[test]
fn provenance_map_failed_string_fields_are_null() {
let source = "plain source text only";
let value = json!({ "present": "source text", "hallucinated": "no such words" });
let map = provenance_map(source, &value, DEFAULT_MIN_COVERAGE);
assert!(map["present"].is_object(), "命中字段产区间");
assert!(map["hallucinated"].is_null(), "全败字段值为 null");
}
#[test]
fn provenance_map_root_string_uses_dollar_path_and_skips_provenance_key() {
let map = provenance_map("hello world", &json!("hello world"), DEFAULT_MIN_COVERAGE);
assert_eq!(map["$"]["coverage"], 1.0);
let value = json!({ "_provenance": { "x": 1 }, "text": "hello" });
let map = provenance_map("hello world", &value, DEFAULT_MIN_COVERAGE);
assert!(!map.as_object().unwrap().contains_key("_provenance"));
assert!(map["text"].is_object());
}
#[test]
fn attach_provenance_merges_alongside_business_fields() {
let mut result = json!({"title": "t"});
let prov = json!({"title": {"start": 0, "end": 1, "coverage": 1.0}});
attach_provenance(&mut result, &prov);
assert_eq!(result["_provenance"], prov);
assert_eq!(result["title"], "t");
}
#[test]
fn attach_provenance_non_object_result_is_skipped() {
let mut result = json!(["a"]);
attach_provenance(&mut result, &json!({}));
assert_eq!(result, json!(["a"]), "非对象结果不挂载");
}
#[test]
fn apply_provenance_disabled_short_circuits_to_none() {
let cfg = ProvenanceConfig::default();
assert!(!cfg.enabled);
let (value, prov) = apply_provenance("source", json!({"a": "source"}), &cfg);
assert_eq!(value, json!({"a": "source"}));
assert!(prov.is_none());
assert!(value.get("_provenance").is_none());
}
#[test]
fn apply_provenance_enabled_attaches_map() {
let cfg = ProvenanceConfig {
enabled: true,
min_coverage: DEFAULT_MIN_COVERAGE,
};
let (value, prov) = apply_provenance("hello world", json!({"a": "world"}), &cfg);
assert!(value["_provenance"].is_object());
assert!(value["_provenance"]["a"].is_object());
let map = prov.expect("enabled yields Some(map)");
assert!(map["a"].is_object());
}
#[test]
fn apply_provenance_empty_map_not_attached() {
let cfg = ProvenanceConfig {
enabled: true,
min_coverage: DEFAULT_MIN_COVERAGE,
};
let (value, prov) = apply_provenance("source", json!({"count": 3}), &cfg);
assert!(value.get("_provenance").is_none(), "空映射不挂载");
let map = prov.expect("enabled yields Some(map)");
assert_eq!(map, json!({}));
}
#[test]
fn slice_char_range_is_cjk_safe() {
let source = "今天天气很好,我们去公园散步。";
let iv = CharInterval { start: 7, end: 14 };
assert_eq!(slice_char_range(source, &iv), "我们去公园散步");
}
#[test]
fn slice_char_range_out_of_bounds_clamps() {
assert_eq!(
slice_char_range("abc", &CharInterval { start: 1, end: 99 }),
"bc"
);
assert_eq!(
slice_char_range("abc", &CharInterval { start: 5, end: 9 }),
""
);
}
#[test]
fn provenance_config_default_is_disabled_with_spec_gate() {
let cfg = ProvenanceConfig::default();
assert!(!cfg.enabled);
assert!((cfg.min_coverage - 0.75).abs() < f64::EPSILON);
}
#[test]
fn provenance_config_from_settings_maps_both_keys() {
let settings = crate::config::settings::LLMSettings {
provenance_enabled: true,
provenance_min_coverage: 0.6,
..Default::default()
};
let cfg = ProvenanceConfig::from_settings(&settings);
assert!(cfg.enabled);
assert!((cfg.min_coverage - 0.6).abs() < f64::EPSILON);
}
#[allow(dead_code)]
fn allowed_miss(m: usize, min_coverage: f64) -> usize {
m - ((min_coverage * m as f64).ceil() as usize).clamp(1, m)
}
}