Skip to main content

webfetch_core/
compress.rs

1use once_cell::sync::Lazy;
2use regex::Regex;
3
4static WHITESPACE_RE: Lazy<Regex> = Lazy::new(|| Regex::new(r"\s+").unwrap());
5static DECORATIVE_RE: Lazy<Regex> = Lazy::new(|| Regex::new(r"[▶→←▼▲•·◆◇◊✓✗✔✘‣⁃◦]").unwrap());
6
7/// Semantic text reduction: strip decorative glyphs, then collapse runs of
8/// whitespace, then trim.
9///
10/// Order matters — decorative characters are removed *before* collapsing
11/// whitespace so that a glyph surrounded by spaces (e.g. `"Click ▶ to play"`)
12/// does not leave a double space behind.
13pub fn compress_text(text: &str) -> String {
14    let clean = DECORATIVE_RE.replace_all(text, "");
15    let collapsed = WHITESPACE_RE.replace_all(&clean, " ");
16    collapsed.trim().to_string()
17}
18
19/// Collapse repeated blank lines while preserving paragraph breaks, and
20/// compress whitespace within each line.
21pub fn compress_block(text: &str) -> String {
22    let mut lines: Vec<String> = Vec::new();
23    let mut prev_blank = false;
24    for raw in text.lines() {
25        let line = compress_text(raw);
26        let blank = line.is_empty();
27        if blank && prev_blank {
28            continue;
29        }
30        lines.push(line);
31        prev_blank = blank;
32    }
33    lines.join("\n").trim().to_string()
34}
35
36/// Is this byte one of the punctuation characters a BPE tokenizer almost
37/// always splits on? See [`estimate_tokens`].
38fn is_url_punct(b: u8) -> bool {
39    matches!(
40        b,
41        b'/' | b':' | b'.' | b'?' | b'#' | b'&' | b'=' | b'%' | b'~'
42    )
43}
44
45/// Token cost of `text` in *quarter-tokens*, the unit both [`estimate_tokens`]
46/// and [`truncate_to_tokens`] work in so the two can never disagree.
47///
48/// One byte costs one quarter-token (the ~4-chars-per-token rule); each URL
49/// punctuation byte costs two extra (the half-token surcharge).
50fn cost_quarters(text: &str) -> usize {
51    text.len() + 2 * text.bytes().filter(|b| is_url_punct(*b)).count()
52}
53
54/// Fast token approximation.
55///
56/// Prose is ~4 characters per token, which matches common BPE tokenizers
57/// closely enough for budgeting. URLs and reference blocks, however, are
58/// punctuation-dense — BPE breaks on `/ : . ? # & = % ~`, so a URL yields far
59/// more tokens per character than prose and a naive `len/4` badly
60/// *under*-budgets them. We therefore add a surcharge of half a token per such
61/// punctuation byte, which pushes URL-heavy text (the trailing reference block
62/// especially) toward its true token count while leaving prose essentially
63/// unchanged. The heuristic is deterministic and a single linear scan.
64pub fn estimate_tokens(text: &str) -> usize {
65    cost_quarters(text) / 4
66}
67
68/// The elision marker appended when [`truncate_to_tokens`] drops content.
69pub const TRUNCATION_MARKER: &str = "\n…[truncated]";
70
71/// Truncate text to roughly `max_tokens`, on a character boundary, appending
72/// an elision marker when content is dropped.
73///
74/// The prefix is chosen with the *same* cost model [`estimate_tokens`] uses, so
75/// `estimate_tokens(truncate_to_tokens(t, n)) <= n` holds for the returned body
76/// even on punctuation-dense text. (A naive `max_tokens * 4` character cut
77/// ignores the URL surcharge and overshoots badly on link-heavy pages.)
78pub fn truncate_to_tokens(text: &str, max_tokens: usize) -> String {
79    truncate_to_tokens_at(text, max_tokens).0
80}
81
82/// [`truncate_to_tokens`], also reporting how many bytes of `text` the returned
83/// prefix consumed.
84///
85/// Callers that page through a document need the resume point to be exact. An
86/// estimate of what came back cannot supply it: [`estimate_tokens`] is lossy in
87/// both directions, so re-deriving a byte position from a token count drifts,
88/// and successive windows then overlap or skip text outright. The cut position
89/// is known here and nowhere else, so it is returned rather than reconstructed.
90///
91/// The count covers only `text`; the elision marker is not part of it.
92pub fn truncate_to_tokens_at(text: &str, max_tokens: usize) -> (String, usize) {
93    if estimate_tokens(text) <= max_tokens {
94        return (text.to_string(), text.len());
95    }
96    // Reserve room for the marker so the returned string still fits the budget.
97    let budget = (max_tokens * 4).saturating_sub(cost_quarters(TRUNCATION_MARKER));
98
99    let mut spent = 0usize;
100    let mut end = 0usize;
101    for (i, b) in text.bytes().enumerate() {
102        let next = spent + if is_url_punct(b) { 3 } else { 1 };
103        if next > budget {
104            break;
105        }
106        spent = next;
107        end = i + 1;
108    }
109    while end > 0 && !text.is_char_boundary(end) {
110        end -= 1;
111    }
112    end = snap_to_boundary(text, end);
113    // A budget smaller than the marker leaves no room for content at all, and a
114    // window that consumes nothing is worse than a small one: a caller paging by
115    // the reported consumption would ask for the same offset forever. Always
116    // make one character of progress.
117    if end == 0 {
118        end = text
119            .char_indices()
120            .nth(1)
121            .map(|(i, _)| i)
122            .unwrap_or(text.len());
123    }
124    (format!("{}{}", &text[..end], TRUNCATION_MARKER), end)
125}
126
127/// How far back a cut may be pulled to land on a natural boundary, as a
128/// fraction of the window. Beyond this the text has no usable break (a long
129/// unbroken token, CJK without spaces) and the hard cut stands.
130const SNAP_BACK_FRACTION: usize = 5;
131
132/// Pull a cut back to the nearest paragraph, line, or word boundary.
133///
134/// A window that ends mid-word reads as corrupted rather than continued, and
135/// the next window opens on the tail of a word nobody can parse. Snapping
136/// costs a few tokens of the budget and keeps both halves readable. It cannot
137/// desynchronize paging: the resume point is the consumption actually returned,
138/// so a shorter window simply means the next one starts earlier.
139fn snap_to_boundary(text: &str, end: usize) -> usize {
140    if end == 0 || end >= text.len() {
141        return end;
142    }
143    let floor = end - end / SNAP_BACK_FRACTION;
144    let head = &text[..end];
145    // Paragraph break first, then any newline, then a space: prefer the break
146    // that leaves the most self-contained window.
147    for pattern in ["\n\n", "\n", " "] {
148        if let Some(at) = head.rfind(pattern) {
149            let cut = at + pattern.len();
150            if cut >= floor {
151                return cut;
152            }
153        }
154    }
155    end
156}
157
158/// The remainder of `text` from a byte `offset`, for reading a long document a
159/// window at a time.
160///
161/// The offset is clamped to the document and snapped back to a character
162/// boundary, so an offset from any source is safe to pass: a caller that
163/// resumes from a stale or hand-written position gets a shorter window, never a
164/// panic. Offsets address the *extracted* text, not the source bytes, so they
165/// stay stable across output formats of the same document.
166pub fn window_from(text: &str, offset: usize) -> &str {
167    let mut start = offset.min(text.len());
168    while start > 0 && !text.is_char_boundary(start) {
169        start -= 1;
170    }
171    &text[start..]
172}
173
174#[cfg(test)]
175mod tests {
176    use super::*;
177
178    #[test]
179    fn estimate_unchanged_for_plain_prose() {
180        assert_eq!(estimate_tokens(&"a".repeat(100)), 25);
181    }
182
183    #[test]
184    fn url_heavy_text_estimates_higher_than_prose_of_same_length() {
185        // Four reference lines: punctuation-dense URLs.
186        let urls = "[1] https://example.com/a/b?c=d#e\n\
187                    [2] https://example.org/x/y/z?q=1\n\
188                    [3] https://sub.example.net/path/to/thing\n\
189                    [4] https://example.io/foo/bar/baz?k=v";
190        // Same byte length, but plain prose (no URL punctuation).
191        let prose = "x".repeat(urls.len());
192        assert_eq!(urls.len(), prose.len());
193        assert!(
194            estimate_tokens(urls) > estimate_tokens(&prose),
195            "urls={} prose={}",
196            estimate_tokens(urls),
197            estimate_tokens(&prose)
198        );
199    }
200
201    #[test]
202    fn truncate_respects_the_budget_it_reports() {
203        let text = "a".repeat(1000);
204        let out = truncate_to_tokens(&text, 20);
205        assert!(out.ends_with(TRUNCATION_MARKER));
206        assert!(
207            estimate_tokens(&out) <= 20,
208            "estimate {}",
209            estimate_tokens(&out)
210        );
211    }
212
213    /// The old `max_tokens * 4` character cut ignored the URL surcharge, so
214    /// punctuation-dense text came back well over budget.
215    #[test]
216    fn truncate_respects_budget_on_url_heavy_text() {
217        let urls = "[1] https://example.com/a/b?c=d#e\n".repeat(200);
218        let out = truncate_to_tokens(&urls, 50);
219        assert!(
220            estimate_tokens(&out) <= 50,
221            "estimate {}",
222            estimate_tokens(&out)
223        );
224    }
225
226    #[test]
227    fn truncate_is_a_noop_within_budget() {
228        let text = "short enough";
229        assert_eq!(truncate_to_tokens(text, 1000), text);
230    }
231
232    /// The property paging rests on: walking the reported consumption from one
233    /// window to the next reproduces the document exactly — no repeated
234    /// sentence, no silently skipped paragraph.
235    #[test]
236    fn windows_tile_the_document_exactly() {
237        let text = "Sentence number one is here. ".repeat(400);
238        let mut offset = 0usize;
239        let mut seen = String::new();
240        let mut windows = 0;
241
242        while offset < text.len() {
243            let remainder = window_from(&text, offset);
244            let (_, consumed) = truncate_to_tokens_at(remainder, 60);
245            assert!(consumed > 0, "a window must make progress");
246            seen.push_str(&remainder[..consumed]);
247            offset += consumed;
248            windows += 1;
249            assert!(windows < 1000, "paging failed to terminate");
250        }
251
252        assert!(windows > 5, "expected several windows, got {windows}");
253        assert_eq!(seen, text);
254    }
255
256    /// A budget too small to hold even the elision marker must still advance,
257    /// or a caller following the consumption never terminates.
258    #[test]
259    fn a_pathologically_small_budget_still_makes_progress() {
260        let text = "ünicode text that will not fit";
261        let (out, consumed) = truncate_to_tokens_at(text, 1);
262        assert!(consumed > 0);
263        assert!(text.is_char_boundary(consumed));
264        assert!(out.starts_with('ü'));
265    }
266
267    /// A window that ends mid-word reads as corrupted, and hands the next
268    /// window a fragment nobody can parse.
269    #[test]
270    fn a_window_ends_on_a_word_boundary_when_one_is_near() {
271        let text = "alpha beta gamma delta epsilon zeta eta theta iota kappa lambda mu ".repeat(20);
272        let (_, consumed) = truncate_to_tokens_at(&text, 20);
273        assert!(
274            text[..consumed].ends_with(' '),
275            "cut mid-word: {:?}",
276            &text[consumed.saturating_sub(12)..consumed]
277        );
278        // The next window opens on a whole word, not a suffix of one.
279        assert!(window_from(&text, consumed).starts_with(char::is_alphabetic));
280    }
281
282    /// Text with no break inside reach still gets a window: a hard cut beats
283    /// returning nothing.
284    #[test]
285    fn text_without_a_boundary_still_yields_a_window() {
286        let text = "x".repeat(500);
287        let (_, consumed) = truncate_to_tokens_at(&text, 20);
288        assert!(consumed > 0);
289    }
290
291    #[test]
292    fn consumption_covers_the_whole_text_when_nothing_is_cut() {
293        let text = "well within budget";
294        let (out, consumed) = truncate_to_tokens_at(text, 1000);
295        assert_eq!(out, text);
296        assert_eq!(consumed, text.len());
297    }
298
299    /// A stale or hand-written offset is a shorter window, never a panic.
300    #[test]
301    fn window_clamps_past_the_end_and_snaps_to_a_char_boundary() {
302        let text = "héllo wörld";
303        assert_eq!(window_from(text, text.len() + 500), "");
304        // Byte 2 is inside "é" (bytes 1..3): snapping back keeps the slice legal.
305        assert_eq!(window_from(text, 2), &text[1..]);
306    }
307
308    #[test]
309    fn truncate_never_splits_a_utf8_char() {
310        let text = "é".repeat(500);
311        let out = truncate_to_tokens(&text, 10);
312        // Round-trips as valid UTF-8 (the type system guarantees it, but the
313        // boundary walk is what makes the slice legal in the first place).
314        assert!(out.starts_with('é'));
315        assert!(estimate_tokens(&out) <= 10);
316    }
317}