Skip to main content

graphrt_rag/
chunker.rs

1//! Text chunking: Markdown-aware recursive splitting with overlap.
2//!
3//! The text is first divided into sections at Markdown headings (each chunk
4//! remembers its heading path), then each section is split recursively on
5//! progressively finer separators (paragraphs, lines, sentences, words, and
6//! finally characters) until every piece fits in `max_chars`. Adjacent chunks
7//! share up to `overlap` characters of context. All sizes count Unicode scalar
8//! values, never bytes, so multi-byte text is never cut mid-character.
9
10use serde::{Deserialize, Serialize};
11
12/// Chunking parameters.
13#[derive(Clone, Debug, PartialEq, Serialize, Deserialize)]
14pub struct ChunkerConfig {
15    /// Maximum characters per chunk (excluding overlap). Roughly 4 characters per token.
16    #[serde(default = "default_max")]
17    pub max_chars: usize,
18    /// Characters of the previous chunk repeated at the start of the next one.
19    #[serde(default = "default_overlap")]
20    pub overlap: usize,
21    /// Split at Markdown headings and record them as chunk metadata.
22    #[serde(default = "yes")]
23    pub markdown: bool,
24    /// Parent-child mode: split the text into parents of up to this many characters,
25    /// then each parent into children of `max_chars` (without overlap). Children are
26    /// embedded and searched; retrieval returns their parent's text. Must be larger
27    /// than `max_chars`.
28    #[serde(default)]
29    pub parent_max_chars: Option<usize>,
30}
31
32fn default_max() -> usize {
33    1000
34}
35fn default_overlap() -> usize {
36    100
37}
38fn yes() -> bool {
39    true
40}
41
42impl Default for ChunkerConfig {
43    fn default() -> Self {
44        Self { max_chars: default_max(), overlap: default_overlap(), markdown: true, parent_max_chars: None }
45    }
46}
47
48impl ChunkerConfig {
49    /// Size limits expressed in approximate tokens (1 token ≈ 4 characters).
50    pub fn from_tokens(max_tokens: usize, overlap_tokens: usize) -> Self {
51        Self {
52            max_chars: max_tokens.saturating_mul(4),
53            overlap: overlap_tokens.saturating_mul(4),
54            markdown: true,
55            parent_max_chars: None,
56        }
57    }
58}
59
60/// One chunk of a document.
61#[derive(Clone, Debug, PartialEq, Eq)]
62pub struct TextChunk {
63    /// Position of the chunk in the document (0-based).
64    pub index: usize,
65    pub text: String,
66    /// Heading path, e.g. `Guide > Install`, when the chunk is under a Markdown heading.
67    pub heading: Option<String>,
68    /// Index of the parent chunk in parent-child mode.
69    pub parent: Option<usize>,
70}
71
72/// Separators tried in order, coarse to fine. The empty separator means "split by character".
73const SEPARATORS: &[&str] = &["\n\n", "\n", ". ", "? ", "! ", "; ", ", ", " ", ""];
74
75/// Split `text` into chunks (children carrying their parent index in parent-child mode).
76pub fn chunk_text(text: &str, config: &ChunkerConfig) -> Vec<TextChunk> {
77    match config.parent_max_chars.filter(|&p| p > config.max_chars) {
78        Some(parent_max) => chunk_with_parents(text, config, parent_max),
79        None => chunk_flat(text, config),
80    }
81}
82
83/// Parents of up to `parent_max` characters, each split into children of
84/// `max_chars`. Children have no overlap, so joining a parent's children gives
85/// back its text and the parent never needs to be stored separately.
86fn chunk_with_parents(text: &str, config: &ChunkerConfig, parent_max: usize) -> Vec<TextChunk> {
87    let parent_config = ChunkerConfig { max_chars: parent_max, overlap: 0, parent_max_chars: None, ..config.clone() };
88    let child_config = ChunkerConfig { overlap: 0, markdown: false, parent_max_chars: None, ..config.clone() };
89    let mut children = Vec::new();
90    for (parent_index, parent) in chunk_flat(text, &parent_config).into_iter().enumerate() {
91        for child in chunk_flat(&parent.text, &child_config) {
92            children.push(TextChunk {
93                index: children.len(),
94                text: child.text,
95                heading: parent.heading.clone(),
96                parent: Some(parent_index),
97            });
98        }
99    }
100    children
101}
102
103fn chunk_flat(text: &str, config: &ChunkerConfig) -> Vec<TextChunk> {
104    let max = config.max_chars.max(1);
105    let overlap = config.overlap.min(max / 2);
106    let sections = if config.markdown { markdown_sections(text) } else { vec![(None, text.to_owned())] };
107
108    let mut chunks = Vec::new();
109    for (heading, body) in sections {
110        let pieces = split_recursive(&body, max, SEPARATORS);
111        let mut previous: Option<String> = None;
112        for piece in pieces {
113            let trimmed = piece.trim();
114            if trimmed.is_empty() {
115                continue;
116            }
117            let text = match (&previous, overlap) {
118                (Some(prev), n) if n > 0 => {
119                    let tail = overlap_tail(prev, n);
120                    if tail.is_empty() { trimmed.to_owned() } else { format!("{tail} {trimmed}") }
121                }
122                _ => trimmed.to_owned(),
123            };
124            previous = Some(trimmed.to_owned());
125            chunks.push(TextChunk { index: chunks.len(), text, heading: heading.clone(), parent: None });
126        }
127    }
128    chunks
129}
130
131/// Divide Markdown text into `(heading path, body)` sections. Text before the first
132/// heading has no heading. Headings inside fenced code blocks are ignored.
133fn markdown_sections(text: &str) -> Vec<(Option<String>, String)> {
134    let mut sections: Vec<(Option<String>, String)> = Vec::new();
135    let mut path: Vec<(usize, String)> = Vec::new();
136    let mut current = String::new();
137    let mut current_heading: Option<String> = None;
138    let mut in_fence = false;
139
140    for line in text.split_inclusive('\n') {
141        let trimmed = line.trim_start();
142        if trimmed.starts_with("```") || trimmed.starts_with("~~~") {
143            in_fence = !in_fence;
144        }
145        let level = if in_fence { 0 } else { heading_level(trimmed) };
146        if level > 0 {
147            if !current.trim().is_empty() {
148                sections.push((current_heading.clone(), std::mem::take(&mut current)));
149            } else {
150                current.clear();
151            }
152            let title = trimmed.get(level..).unwrap_or_default().trim().trim_end_matches('#').trim().to_owned();
153            path.retain(|(l, _)| *l < level);
154            path.push((level, title));
155            current_heading = Some(path.iter().map(|(_, t)| t.as_str()).collect::<Vec<_>>().join(" > "));
156            // Keep the heading line in the body so chunks stay self-describing.
157            current.push_str(line);
158        } else {
159            current.push_str(line);
160        }
161    }
162    if !current.trim().is_empty() {
163        sections.push((current_heading, current));
164    }
165    sections
166}
167
168/// `#` count of an ATX heading line (1-6), or 0.
169fn heading_level(line: &str) -> usize {
170    let hashes = line.chars().take_while(|c| *c == '#').count();
171    if (1..=6).contains(&hashes) && line.chars().nth(hashes).is_some_and(char::is_whitespace) { hashes } else { 0 }
172}
173
174fn char_len(s: &str) -> usize {
175    s.chars().count()
176}
177
178/// Split into pieces of at most `max` characters using the first separator that
179/// occurs, merging small adjacent pieces greedily.
180fn split_recursive(text: &str, max: usize, separators: &[&str]) -> Vec<String> {
181    if char_len(text) <= max {
182        return vec![text.to_owned()];
183    }
184    let Some((sep, rest)) = separators.split_first() else {
185        return hard_split(text, max);
186    };
187    if sep.is_empty() {
188        return hard_split(text, max);
189    }
190    if !text.contains(sep) {
191        return split_recursive(text, max, rest);
192    }
193
194    // Keep the separator attached to the end of each piece.
195    let parts: Vec<&str> = text.split_inclusive(sep).collect();
196    let mut out = Vec::new();
197    let mut buffer = String::new();
198    // Running character count of `buffer`, so each part is measured once.
199    let mut buffer_chars = 0usize;
200    for part in parts {
201        let part_chars = char_len(part);
202        if part_chars > max {
203            if !buffer.is_empty() {
204                out.push(std::mem::take(&mut buffer));
205                buffer_chars = 0;
206            }
207            out.extend(split_recursive(part, max, rest));
208            continue;
209        }
210        if buffer_chars + part_chars > max && !buffer.is_empty() {
211            out.push(std::mem::take(&mut buffer));
212            buffer_chars = 0;
213        }
214        buffer.push_str(part);
215        buffer_chars += part_chars;
216    }
217    if !buffer.is_empty() {
218        out.push(buffer);
219    }
220    out
221}
222
223fn hard_split(text: &str, max: usize) -> Vec<String> {
224    let chars: Vec<char> = text.chars().collect();
225    chars.chunks(max.max(1)).map(|c| c.iter().collect()).collect()
226}
227
228/// The last `n` characters of `text`, starting at a word boundary when possible.
229fn overlap_tail(text: &str, n: usize) -> String {
230    let total = char_len(text);
231    if total <= n {
232        return text.to_owned();
233    }
234    let tail: String = text.chars().skip(total - n).collect();
235    match tail.find(char::is_whitespace) {
236        Some(pos) if pos + 1 < tail.len() => tail.get(pos..).unwrap_or_default().trim_start().to_owned(),
237        _ => tail,
238    }
239}
240
241#[cfg(test)]
242mod tests {
243    use super::*;
244
245    #[test]
246    fn respects_max_size_and_keeps_text() {
247        let text = "Alpha beta gamma. Delta epsilon zeta. Eta theta iota. Kappa lambda mu.".repeat(20);
248        let cfg = ChunkerConfig { max_chars: 100, overlap: 0, markdown: false, parent_max_chars: None };
249        let chunks = chunk_text(&text, &cfg);
250        assert!(chunks.len() > 5);
251        for c in &chunks {
252            assert!(char_len(&c.text) <= 100, "{}", c.text.len());
253        }
254        let joined: String = chunks.iter().map(|c| c.text.as_str()).collect::<Vec<_>>().join(" ");
255        assert_eq!(joined.split_whitespace().count(), text.split_whitespace().count());
256    }
257
258    #[test]
259    fn overlap_repeats_previous_tail() {
260        let text = "one two three four five six seven eight nine ten eleven twelve";
261        let cfg = ChunkerConfig { max_chars: 25, overlap: 10, markdown: false, parent_max_chars: None };
262        let chunks = chunk_text(text, &cfg);
263        assert!(chunks.len() >= 2);
264        let second = &chunks[1].text;
265        let tail = overlap_tail(&chunks[0].text, 10);
266        assert!(!tail.is_empty());
267        assert!(chunks[0].text.ends_with(&tail));
268        assert!(second.starts_with(&tail), "{second:?} vs {:?}", chunks[0].text);
269    }
270
271    #[test]
272    fn markdown_headings_become_metadata() {
273        let text = "Intro text.\n\n# Guide\n\nRead me.\n\n## Install\n\nRun it.\n\n```\n# not a heading\n```\n\n# Faq\nQ and A.\n";
274        let chunks = chunk_text(text, &ChunkerConfig::default());
275        let headings: Vec<Option<&str>> = chunks.iter().map(|c| c.heading.as_deref()).collect();
276        assert_eq!(headings, vec![None, Some("Guide"), Some("Guide > Install"), Some("Faq")]);
277        assert!(chunks[2].text.contains("# not a heading"));
278    }
279
280    #[test]
281    fn multibyte_text_is_split_on_char_boundaries() {
282        let text = "日本語のテキストです。".repeat(50);
283        let cfg = ChunkerConfig { max_chars: 30, overlap: 5, markdown: false, parent_max_chars: None };
284        let chunks = chunk_text(&text, &cfg);
285        assert!(chunks.len() > 10);
286        assert!(chunks.iter().all(|c| char_len(&c.text) <= 36));
287    }
288
289    #[test]
290    fn token_helper() {
291        let cfg = ChunkerConfig::from_tokens(256, 32);
292        assert_eq!(cfg.max_chars, 1024);
293        assert_eq!(cfg.overlap, 128);
294    }
295    #[test]
296    fn parent_child_mode_splits_parents_into_children_without_overlap() {
297        let paragraph =
298            |topic: &str| format!("{topic} first sentence here. {topic} second sentence here. {topic} third one.");
299        let text = format!("{}\n\n{}\n\n{}", paragraph("Alpha"), paragraph("Beta"), paragraph("Gamma"));
300        let cfg = ChunkerConfig { max_chars: 40, overlap: 30, markdown: false, parent_max_chars: Some(90) };
301        let chunks = chunk_text(&text, &cfg);
302        assert!(chunks.iter().all(|c| c.parent.is_some()), "every chunk is a child");
303        assert!(chunks.iter().all(|c| c.text.chars().count() <= 40), "children fit max_chars");
304        assert!(chunks.windows(2).all(|w| w[0].index + 1 == w[1].index), "indexes are sequential");
305        let parents: std::collections::BTreeSet<usize> = chunks.iter().filter_map(|c| c.parent).collect();
306        assert!(parents.len() >= 3, "{parents:?}");
307        // No overlap: every word of the text appears once across children.
308        let words = |s: &str| s.split_whitespace().count();
309        assert_eq!(chunks.iter().map(|c| words(&c.text)).sum::<usize>(), words(&text));
310        // A parent's children never mix topics from different paragraphs.
311        for p in parents {
312            let joined: Vec<&str> = chunks.iter().filter(|c| c.parent == Some(p)).map(|c| c.text.as_str()).collect();
313            let joined = joined.join(" ");
314            let topics = ["Alpha", "Beta", "Gamma"].iter().filter(|t| joined.contains(*t)).count();
315            assert_eq!(topics, 1, "parent {p} mixes paragraphs: {joined}");
316        }
317    }
318
319    #[test]
320    fn parent_size_not_above_child_size_means_flat_chunks() {
321        let cfg = ChunkerConfig { max_chars: 50, overlap: 0, markdown: false, parent_max_chars: Some(50) };
322        assert!(chunk_text("one two three four five six seven", &cfg).iter().all(|c| c.parent.is_none()));
323    }
324}