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}
25
26fn default_max() -> usize {
27    1000
28}
29fn default_overlap() -> usize {
30    100
31}
32fn yes() -> bool {
33    true
34}
35
36impl Default for ChunkerConfig {
37    fn default() -> Self {
38        Self { max_chars: default_max(), overlap: default_overlap(), markdown: true }
39    }
40}
41
42impl ChunkerConfig {
43    /// Size limits expressed in approximate tokens (1 token ≈ 4 characters).
44    pub fn from_tokens(max_tokens: usize, overlap_tokens: usize) -> Self {
45        Self { max_chars: max_tokens.saturating_mul(4), overlap: overlap_tokens.saturating_mul(4), markdown: true }
46    }
47}
48
49/// One chunk of a document.
50#[derive(Clone, Debug, PartialEq, Eq)]
51pub struct TextChunk {
52    /// Position of the chunk in the document (0-based).
53    pub index: usize,
54    pub text: String,
55    /// Heading path, e.g. `Guide > Install`, when the chunk is under a Markdown heading.
56    pub heading: Option<String>,
57}
58
59/// Separators tried in order, coarse to fine. The empty separator means "split by character".
60const SEPARATORS: &[&str] = &["\n\n", "\n", ". ", "? ", "! ", "; ", ", ", " ", ""];
61
62/// Split `text` into chunks.
63pub fn chunk_text(text: &str, config: &ChunkerConfig) -> Vec<TextChunk> {
64    let max = config.max_chars.max(1);
65    let overlap = config.overlap.min(max / 2);
66    let sections = if config.markdown { markdown_sections(text) } else { vec![(None, text.to_owned())] };
67
68    let mut chunks = Vec::new();
69    for (heading, body) in sections {
70        let pieces = split_recursive(&body, max, SEPARATORS);
71        let mut previous: Option<String> = None;
72        for piece in pieces {
73            let trimmed = piece.trim();
74            if trimmed.is_empty() {
75                continue;
76            }
77            let text = match (&previous, overlap) {
78                (Some(prev), n) if n > 0 => {
79                    let tail = overlap_tail(prev, n);
80                    if tail.is_empty() { trimmed.to_owned() } else { format!("{tail} {trimmed}") }
81                }
82                _ => trimmed.to_owned(),
83            };
84            previous = Some(trimmed.to_owned());
85            chunks.push(TextChunk { index: chunks.len(), text, heading: heading.clone() });
86        }
87    }
88    chunks
89}
90
91/// Divide Markdown text into `(heading path, body)` sections. Text before the first
92/// heading has no heading. Headings inside fenced code blocks are ignored.
93fn markdown_sections(text: &str) -> Vec<(Option<String>, String)> {
94    let mut sections: Vec<(Option<String>, String)> = Vec::new();
95    let mut path: Vec<(usize, String)> = Vec::new();
96    let mut current = String::new();
97    let mut current_heading: Option<String> = None;
98    let mut in_fence = false;
99
100    for line in text.split_inclusive('\n') {
101        let trimmed = line.trim_start();
102        if trimmed.starts_with("```") || trimmed.starts_with("~~~") {
103            in_fence = !in_fence;
104        }
105        let level = if in_fence { 0 } else { heading_level(trimmed) };
106        if level > 0 {
107            if !current.trim().is_empty() {
108                sections.push((current_heading.clone(), std::mem::take(&mut current)));
109            } else {
110                current.clear();
111            }
112            let title = trimmed.get(level..).unwrap_or_default().trim().trim_end_matches('#').trim().to_owned();
113            path.retain(|(l, _)| *l < level);
114            path.push((level, title));
115            current_heading = Some(path.iter().map(|(_, t)| t.as_str()).collect::<Vec<_>>().join(" > "));
116            // Keep the heading line in the body so chunks stay self-describing.
117            current.push_str(line);
118        } else {
119            current.push_str(line);
120        }
121    }
122    if !current.trim().is_empty() {
123        sections.push((current_heading, current));
124    }
125    sections
126}
127
128/// `#` count of an ATX heading line (1-6), or 0.
129fn heading_level(line: &str) -> usize {
130    let hashes = line.chars().take_while(|c| *c == '#').count();
131    if (1..=6).contains(&hashes) && line.chars().nth(hashes).is_some_and(char::is_whitespace) { hashes } else { 0 }
132}
133
134fn char_len(s: &str) -> usize {
135    s.chars().count()
136}
137
138/// Split into pieces of at most `max` characters using the first separator that
139/// occurs, merging small adjacent pieces greedily.
140fn split_recursive(text: &str, max: usize, separators: &[&str]) -> Vec<String> {
141    if char_len(text) <= max {
142        return vec![text.to_owned()];
143    }
144    let Some((sep, rest)) = separators.split_first() else {
145        return hard_split(text, max);
146    };
147    if sep.is_empty() {
148        return hard_split(text, max);
149    }
150    if !text.contains(sep) {
151        return split_recursive(text, max, rest);
152    }
153
154    // Keep the separator attached to the end of each piece.
155    let parts: Vec<&str> = text.split_inclusive(sep).collect();
156    let mut out = Vec::new();
157    let mut buffer = String::new();
158    // Running character count of `buffer`, so each part is measured once.
159    let mut buffer_chars = 0usize;
160    for part in parts {
161        let part_chars = char_len(part);
162        if part_chars > max {
163            if !buffer.is_empty() {
164                out.push(std::mem::take(&mut buffer));
165                buffer_chars = 0;
166            }
167            out.extend(split_recursive(part, max, rest));
168            continue;
169        }
170        if buffer_chars + part_chars > max && !buffer.is_empty() {
171            out.push(std::mem::take(&mut buffer));
172            buffer_chars = 0;
173        }
174        buffer.push_str(part);
175        buffer_chars += part_chars;
176    }
177    if !buffer.is_empty() {
178        out.push(buffer);
179    }
180    out
181}
182
183fn hard_split(text: &str, max: usize) -> Vec<String> {
184    let chars: Vec<char> = text.chars().collect();
185    chars.chunks(max.max(1)).map(|c| c.iter().collect()).collect()
186}
187
188/// The last `n` characters of `text`, starting at a word boundary when possible.
189fn overlap_tail(text: &str, n: usize) -> String {
190    let total = char_len(text);
191    if total <= n {
192        return text.to_owned();
193    }
194    let tail: String = text.chars().skip(total - n).collect();
195    match tail.find(char::is_whitespace) {
196        Some(pos) if pos + 1 < tail.len() => tail.get(pos..).unwrap_or_default().trim_start().to_owned(),
197        _ => tail,
198    }
199}
200
201#[cfg(test)]
202mod tests {
203    use super::*;
204
205    #[test]
206    fn respects_max_size_and_keeps_text() {
207        let text = "Alpha beta gamma. Delta epsilon zeta. Eta theta iota. Kappa lambda mu.".repeat(20);
208        let cfg = ChunkerConfig { max_chars: 100, overlap: 0, markdown: false };
209        let chunks = chunk_text(&text, &cfg);
210        assert!(chunks.len() > 5);
211        for c in &chunks {
212            assert!(char_len(&c.text) <= 100, "{}", c.text.len());
213        }
214        let joined: String = chunks.iter().map(|c| c.text.as_str()).collect::<Vec<_>>().join(" ");
215        assert_eq!(joined.split_whitespace().count(), text.split_whitespace().count());
216    }
217
218    #[test]
219    fn overlap_repeats_previous_tail() {
220        let text = "one two three four five six seven eight nine ten eleven twelve";
221        let cfg = ChunkerConfig { max_chars: 25, overlap: 10, markdown: false };
222        let chunks = chunk_text(text, &cfg);
223        assert!(chunks.len() >= 2);
224        let second = &chunks[1].text;
225        let tail = overlap_tail(&chunks[0].text, 10);
226        assert!(!tail.is_empty());
227        assert!(chunks[0].text.ends_with(&tail));
228        assert!(second.starts_with(&tail), "{second:?} vs {:?}", chunks[0].text);
229    }
230
231    #[test]
232    fn markdown_headings_become_metadata() {
233        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";
234        let chunks = chunk_text(text, &ChunkerConfig::default());
235        let headings: Vec<Option<&str>> = chunks.iter().map(|c| c.heading.as_deref()).collect();
236        assert_eq!(headings, vec![None, Some("Guide"), Some("Guide > Install"), Some("Faq")]);
237        assert!(chunks[2].text.contains("# not a heading"));
238    }
239
240    #[test]
241    fn multibyte_text_is_split_on_char_boundaries() {
242        let text = "日本語のテキストです。".repeat(50);
243        let cfg = ChunkerConfig { max_chars: 30, overlap: 5, markdown: false };
244        let chunks = chunk_text(&text, &cfg);
245        assert!(chunks.len() > 10);
246        assert!(chunks.iter().all(|c| char_len(&c.text) <= 36));
247    }
248
249    #[test]
250    fn token_helper() {
251        let cfg = ChunkerConfig::from_tokens(256, 32);
252        assert_eq!(cfg.max_chars, 1024);
253        assert_eq!(cfg.overlap, 128);
254    }
255}