Skip to main content

webfetch_core/
refs.rs

1//! Shared reference-style URL preservation.
2//!
3//! Both the fetch path and the search path cite URLs with inline `[N]` markers
4//! and collect the full URLs into a trailing block. This module owns the one
5//! canonical rendering of that block, and the budgeting rule that keeps the
6//! block and the body it belongs to inside a token cap together.
7
8use std::collections::BTreeSet;
9
10use serde::{Deserialize, Serialize};
11
12use crate::compress::{estimate_tokens, truncate_to_tokens_at};
13
14/// Anything that can be listed in a reference block: an index and a URL.
15pub 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/// A slim reference entry (index → URL) for an output's reference block.
30#[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
45/// Render references into the canonical block:
46///
47/// ```text
48/// References:
49/// [1] https://example.com/a
50/// [2] https://example.com/b
51/// ```
52///
53/// Returns an empty string when there are no references.
54pub 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
66/// The smallest body budget we will ever leave, so a page dominated by links
67/// still shows *some* body rather than collapsing to a bare reference list.
68const MIN_BODY_TOKENS: usize = 64;
69
70/// How many times we re-shrink the body budget trying to fit body + block.
71/// Each pass drops uncited references, which shrinks the block, which frees
72/// budget — the sequence is monotone and converges in two or three passes.
73const FIT_PASSES: usize = 6;
74
75/// Collect the distinct `[N]` reference indices cited in `text`, in order.
76pub 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
99/// Join a body and a rendered reference block into final output.
100fn 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
108/// What [`fit_to_budget`] produced: the assembled output, the references it
109/// kept, and how much of the body it got through.
110pub struct Fitted {
111    /// Body plus reference block, inside the cap.
112    pub content: String,
113    /// Indices of the references the surviving body still cites.
114    pub kept: Vec<usize>,
115    /// Bytes of `body` consumed. A caller paging a long document resumes here;
116    /// equal to `body.len()` when the whole body fit.
117    pub body_consumed: usize,
118}
119
120/// Fit `body` plus its reference block inside `max_tokens`.
121///
122/// Returns the assembled content, the reference indices it kept, and how far
123/// into the body it got.
124///
125/// The old rule reserved room for the *whole* reference block and then appended
126/// it regardless of size, so a link-dense page blew straight through the cap
127/// (a 120-link page answered `--max-tokens 200` with ~3300 tokens). The rule
128/// here is the other way round: truncate the body first, then keep only the
129/// references the surviving text still cites. Dropping a reference nobody cites
130/// costs nothing and is usually enough on its own; if the block still does not
131/// fit, references are dropped from the tail so the cap holds.
132///
133/// With `max_tokens == None` nothing is truncated and every reference is kept.
134pub 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            // The block alone is over budget (very long URLs, very small cap).
171            // Drop references from the tail until the whole thing fits.
172            return drop_until_fits(&body, &kept, max_tokens, consumed.min(full_len));
173        }
174        // Scale the body budget by how far over we landed, rather than
175        // subtracting the overshoot. Subtracting punishes the body for the
176        // reference block's size — one long block drove the budget straight to
177        // the floor and answered a 1000-token cap with under 300 tokens of
178        // output. Scaling converges on the cap from below in two or three
179        // passes instead.
180        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            // Not converging (already at the floor): stop shrinking the body
184            // and take references off the tail instead.
185            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
192/// Last resort: shrink the reference block itself, tail first. Markers for
193/// dropped references stop resolving, which is a worse output than a complete
194/// block — but a silently ignored token cap is worse still.
195fn 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    /// The regression this function exists for: a link-dense page must not
255    /// answer a small budget with a full reference block.
256    #[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    /// Fitting the cap is necessary but not sufficient: answering a 1000-token
280    /// budget with 280 tokens wastes most of the caller's allowance.
281    #[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}