1use std::collections::BTreeSet;
9
10use serde::{Deserialize, Serialize};
11
12use crate::compress::{estimate_tokens, truncate_to_tokens_at};
13
14pub trait Referable {
16 fn index(&self) -> usize;
17 fn url(&self) -> &str;
18}
19
20impl<T: Referable> Referable for &T {
21 fn index(&self) -> usize {
22 (*self).index()
23 }
24 fn url(&self) -> &str {
25 (*self).url()
26 }
27}
28
29#[derive(Debug, Clone, Serialize, Deserialize, PartialEq, Eq)]
31pub struct Reference {
32 pub index: usize,
33 pub url: String,
34}
35
36impl Referable for Reference {
37 fn index(&self) -> usize {
38 self.index
39 }
40 fn url(&self) -> &str {
41 &self.url
42 }
43}
44
45pub fn render_block<T: Referable>(references: &[T]) -> String {
55 if references.is_empty() {
56 return String::new();
57 }
58 let mut s = String::from("References:\n");
59 for r in references {
60 s.push_str(&format!("[{}] {}\n", r.index(), r.url()));
61 }
62 s.truncate(s.trim_end().len());
63 s
64}
65
66const MIN_BODY_TOKENS: usize = 64;
69
70const FIT_PASSES: usize = 6;
74
75pub fn cited_indices(text: &str) -> BTreeSet<usize> {
77 let mut out = BTreeSet::new();
78 let bytes = text.as_bytes();
79 let mut i = 0;
80 while i < bytes.len() {
81 if bytes[i] != b'[' {
82 i += 1;
83 continue;
84 }
85 let mut j = i + 1;
86 while j < bytes.len() && bytes[j].is_ascii_digit() {
87 j += 1;
88 }
89 if j > i + 1 && j < bytes.len() && bytes[j] == b']' {
90 if let Ok(n) = text[i + 1..j].parse::<usize>() {
91 out.insert(n);
92 }
93 }
94 i = j.max(i + 1);
95 }
96 out
97}
98
99fn assemble(body: &str, block: &str) -> String {
101 if block.is_empty() {
102 body.to_string()
103 } else {
104 format!("{body}\n\n{block}")
105 }
106}
107
108pub struct Fitted {
111 pub content: String,
113 pub kept: Vec<usize>,
115 pub body_consumed: usize,
118}
119
120pub fn fit_to_budget<T: Referable>(
135 body: &str,
136 references: &[T],
137 max_tokens: Option<usize>,
138) -> Fitted {
139 let all = || references.iter().map(Referable::index).collect::<Vec<_>>();
140
141 let Some(max_tokens) = max_tokens else {
142 return Fitted {
143 content: assemble(body, &render_block(references)),
144 kept: all(),
145 body_consumed: body.len(),
146 };
147 };
148
149 let full_len = body.len();
150 let mut budget = max_tokens;
151 for pass in 0..FIT_PASSES {
152 let (body, consumed) = truncate_to_tokens_at(body, budget);
153 let cited = cited_indices(&body);
154 let kept: Vec<&T> = references
155 .iter()
156 .filter(|r| cited.contains(&r.index()))
157 .collect();
158 let block = render_block(&kept);
159 let content = assemble(&body, &block);
160 let total = estimate_tokens(&content);
161
162 if total <= max_tokens {
163 return Fitted {
164 content,
165 kept: kept.iter().map(|r| r.index()).collect(),
166 body_consumed: consumed.min(full_len),
167 };
168 }
169 if pass + 1 == FIT_PASSES || budget <= MIN_BODY_TOKENS {
170 return drop_until_fits(&body, &kept, max_tokens, consumed.min(full_len));
173 }
174 let scaled = (budget as u128 * max_tokens as u128 / total as u128) as usize;
181 let next = scaled.max(MIN_BODY_TOKENS);
182 if next >= budget {
183 return drop_until_fits(&body, &kept, max_tokens, consumed.min(full_len));
186 }
187 budget = next;
188 }
189 unreachable!("the loop returns on its final pass")
190}
191
192fn drop_until_fits<T: Referable>(
196 body: &str,
197 kept: &[&T],
198 max_tokens: usize,
199 body_consumed: usize,
200) -> Fitted {
201 let mut kept = kept.to_vec();
202 while !kept.is_empty() {
203 let content = assemble(body, &render_block(&kept));
204 if estimate_tokens(&content) <= max_tokens {
205 return Fitted {
206 content,
207 kept: kept.iter().map(|r| r.index()).collect(),
208 body_consumed,
209 };
210 }
211 kept.pop();
212 }
213 Fitted {
214 content: body.to_string(),
215 kept: Vec::new(),
216 body_consumed,
217 }
218}
219
220#[cfg(test)]
221mod tests {
222 use super::*;
223
224 fn refs(n: usize) -> Vec<Reference> {
225 (1..=n)
226 .map(|i| Reference {
227 index: i,
228 url: format!("https://example.com/very/long/path/segment/{i}?query=value#frag"),
229 })
230 .collect()
231 }
232
233 fn body_citing(n: usize) -> String {
234 (1..=n)
235 .map(|i| format!("Item {i} with filler prose describing the thing [{i}]."))
236 .collect::<Vec<_>>()
237 .join("\n")
238 }
239
240 #[test]
241 fn cited_indices_finds_markers() {
242 let got = cited_indices("a [1] b [12] c [x] d [3]");
243 assert_eq!(got.into_iter().collect::<Vec<_>>(), vec![1, 3, 12]);
244 }
245
246 #[test]
247 fn no_budget_keeps_everything() {
248 let Fitted { content, kept, .. } = fit_to_budget(&body_citing(3), &refs(3), None);
249 assert_eq!(kept, vec![1, 2, 3]);
250 assert!(content.contains("References:"));
251 assert!(content.contains("[3] https://example.com"));
252 }
253
254 #[test]
257 fn link_dense_page_respects_the_cap() {
258 let refs = refs(120);
259 let Fitted { content, kept, .. } = fit_to_budget(&body_citing(120), &refs, Some(200));
260 assert!(
261 estimate_tokens(&content) <= 200,
262 "estimate {} content: {content}",
263 estimate_tokens(&content)
264 );
265 assert!(kept.len() < 120, "kept {} of 120", kept.len());
266 }
267
268 #[test]
269 fn every_kept_reference_is_still_cited() {
270 let refs = refs(120);
271 let Fitted { content, kept, .. } = fit_to_budget(&body_citing(120), &refs, Some(300));
272 let body = content.split("References:").next().unwrap();
273 let cited = cited_indices(body);
274 for index in &kept {
275 assert!(cited.contains(index), "kept [{index}] is not cited");
276 }
277 }
278
279 #[test]
282 fn a_generous_budget_is_actually_used() {
283 let refs = refs(120);
284 let Fitted { content, .. } = fit_to_budget(&body_citing(120), &refs, Some(1000));
285 let used = estimate_tokens(&content);
286 assert!(used <= 1000, "over budget: {used}");
287 assert!(used >= 800, "left {} of 1000 tokens unused", 1000 - used);
288 }
289
290 #[test]
291 fn tiny_budget_still_fits() {
292 let refs = refs(40);
293 let Fitted { content, .. } = fit_to_budget(&body_citing(40), &refs, Some(80));
294 assert!(
295 estimate_tokens(&content) <= 80,
296 "estimate {}",
297 estimate_tokens(&content)
298 );
299 }
300
301 #[test]
302 fn generous_budget_is_a_noop() {
303 let refs = refs(3);
304 let body = body_citing(3);
305 let Fitted { content, kept, .. } = fit_to_budget(&body, &refs, Some(100_000));
306 assert_eq!(kept, vec![1, 2, 3]);
307 assert_eq!(content, assemble(&body, &render_block(&refs)));
308 }
309
310 #[test]
311 fn body_without_references_is_plain_truncation() {
312 let empty: [Reference; 0] = [];
313 let Fitted { content, kept, .. } = fit_to_budget(&"word ".repeat(500), &empty, Some(50));
314 assert!(kept.is_empty());
315 assert!(content.contains("…[truncated]"));
316 assert!(estimate_tokens(&content) <= 50);
317 }
318}