Skip to main content

treesearch/
document.rs

1//! Defines serialized document trees and iterative structural lookup helpers.
2
3use serde::{Deserialize, Serialize};
4use std::collections::{HashMap, HashSet};
5
6/// Unique identifier for a node within a document.
7pub type NodeId = String;
8
9/// Source type classification for documents.
10#[derive(Debug, Clone, PartialEq, Eq, Hash, Serialize, Deserialize)]
11#[serde(rename_all = "lowercase")]
12pub enum SourceType {
13    Code,
14    Markdown,
15    Html,
16    Text,
17    Json,
18    Yaml,
19    Toml,
20    #[serde(other)]
21    Unknown,
22}
23
24impl SourceType {
25    pub fn as_str(&self) -> &str {
26        match self {
27            Self::Code => "code",
28            Self::Markdown => "markdown",
29            Self::Html => "html",
30            Self::Text => "text",
31            Self::Json => "json",
32            Self::Yaml => "yaml",
33            Self::Toml => "toml",
34            Self::Unknown => "unknown",
35        }
36    }
37
38    pub fn from_extension(ext: &str) -> Self {
39        match ext.to_lowercase().as_str() {
40            "md" | "mdx" | "markdown" => Self::Markdown,
41            "html" | "htm" => Self::Html,
42            "json" => Self::Json,
43            "yaml" | "yml" => Self::Yaml,
44            "toml" => Self::Toml,
45            "txt" | "text" | "log" | "csv" => Self::Text,
46            "rs" | "py" | "js" | "ts" | "jsx" | "tsx" | "go" | "java" | "c" | "cpp" | "h"
47            | "hpp" | "cs" | "rb" | "php" | "swift" | "kt" | "scala" | "sh" | "bash" | "zsh"
48            | "fish" | "lua" | "r" | "m" | "mm" | "pl" | "pm" | "ex" | "exs" | "erl" | "hs"
49            | "ml" | "mli" | "clj" | "cljs" | "el" | "vim" | "sql" | "graphql" | "proto" | "tf"
50            | "hcl" | "zig" | "nim" | "v" | "d" | "dart" | "cmake" | "makefile" | "dockerfile"
51            | "css" | "scss" | "sass" | "less" | "vue" | "svelte" => Self::Code,
52            _ => Self::Unknown,
53        }
54    }
55}
56
57impl std::fmt::Display for SourceType {
58    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
59        f.write_str(self.as_str())
60    }
61}
62
63/// A single node in the document tree.
64#[derive(Debug, Clone, Serialize, Deserialize)]
65pub struct Node {
66    pub node_id: NodeId,
67    pub title: String,
68    #[serde(default)]
69    pub summary: String,
70    #[serde(default)]
71    pub text: String,
72    #[serde(default)]
73    pub line_start: Option<u32>,
74    #[serde(default)]
75    pub line_end: Option<u32>,
76    #[serde(default)]
77    pub children: Vec<Node>,
78}
79
80impl Node {
81    /// Creates a node with empty content and no children.
82    pub fn new(node_id: impl Into<String>, title: impl Into<String>) -> Self {
83        Self {
84            node_id: node_id.into(),
85            title: title.into(),
86            summary: String::new(),
87            text: String::new(),
88            line_start: None,
89            line_end: None,
90            children: Vec::new(),
91        }
92    }
93
94    /// Flatten this node and all descendants into a vec.
95    pub fn flatten(&self) -> Vec<&Node> {
96        let mut result = Vec::new();
97        let mut stack = vec![self];
98        while let Some(node) = stack.pop() {
99            result.push(node);
100            stack.extend(node.children.iter().rev());
101        }
102        result
103    }
104}
105
106impl Drop for Node {
107    /// Drains descendants iteratively so destroying host-built deep trees cannot overflow the stack.
108    fn drop(&mut self) {
109        let mut pending = std::mem::take(&mut self.children);
110        while let Some(mut node) = pending.pop() {
111            pending.append(&mut node.children);
112        }
113    }
114}
115
116/// A structural invariant violation in one owned document tree.
117#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
118pub enum DocumentStructureError {
119    #[error("document ID cannot be empty")]
120    EmptyDocumentId,
121    #[error("node ID cannot be empty")]
122    EmptyNodeId,
123    #[error("node ID `{node_id}` occurs more than once")]
124    DuplicateNodeId { node_id: String },
125    #[error("node `{node_id}` has line_end before line_start")]
126    InvalidLineRange { node_id: String },
127}
128
129/// A parsed document with its tree structure.
130#[derive(Debug, Clone, Serialize, Deserialize)]
131pub struct Document {
132    pub doc_id: String,
133    pub doc_name: String,
134    pub source_type: SourceType,
135    #[serde(default)]
136    pub doc_description: String,
137    #[serde(default)]
138    pub source_path: String,
139    pub structure: Vec<Node>,
140}
141
142impl Document {
143    /// Creates an empty document with stable transport metadata.
144    pub fn new(
145        doc_id: impl Into<String>,
146        doc_name: impl Into<String>,
147        source_type: SourceType,
148    ) -> Self {
149        Self {
150            doc_id: doc_id.into(),
151            doc_name: doc_name.into(),
152            source_type,
153            doc_description: String::new(),
154            source_path: String::new(),
155            structure: Vec::new(),
156        }
157    }
158
159    /// Flatten all nodes in the document tree.
160    pub fn flatten_nodes(&self) -> Vec<&Node> {
161        let mut nodes = Vec::new();
162        let mut stack: Vec<&Node> = self.structure.iter().rev().collect();
163        while let Some(node) = stack.pop() {
164            nodes.push(node);
165            stack.extend(node.children.iter().rev());
166        }
167        nodes
168    }
169
170    /// Builds a borrowed node lookup table for repeated search operations.
171    ///
172    /// Call [`Document::validate_structure`] first when identities come from an
173    /// untrusted host; duplicate IDs would otherwise keep the last node.
174    pub fn build_node_map(&self) -> HashMap<&str, &Node> {
175        self.flatten_nodes()
176            .into_iter()
177            .map(|node| (node.node_id.as_str(), node))
178            .collect()
179    }
180
181    /// Validates identities and source ranges required by search maps.
182    pub fn validate_structure(&self) -> Result<(), DocumentStructureError> {
183        if self.doc_id.trim().is_empty() {
184            return Err(DocumentStructureError::EmptyDocumentId);
185        }
186        let mut node_ids = HashSet::new();
187        for node in self.flatten_nodes() {
188            if node.node_id.trim().is_empty() {
189                return Err(DocumentStructureError::EmptyNodeId);
190            }
191            if !node_ids.insert(node.node_id.as_str()) {
192                return Err(DocumentStructureError::DuplicateNodeId {
193                    node_id: node.node_id.clone(),
194                });
195            }
196            if matches!((node.line_start, node.line_end), (Some(start), Some(end)) if end < start) {
197                return Err(DocumentStructureError::InvalidLineRange {
198                    node_id: node.node_id.clone(),
199                });
200            }
201        }
202        Ok(())
203    }
204
205    /// Build parent map: node_id -> parent_node_id (None for roots).
206    pub fn build_parent_map(&self) -> HashMap<String, Option<String>> {
207        let mut map = HashMap::new();
208        let mut stack: Vec<(&Node, Option<&str>)> = self
209            .structure
210            .iter()
211            .rev()
212            .map(|root| (root, None))
213            .collect();
214        while let Some((node, parent_id)) = stack.pop() {
215            map.insert(node.node_id.clone(), parent_id.map(String::from));
216            stack.extend(
217                node.children
218                    .iter()
219                    .rev()
220                    .map(|child| (child, Some(node.node_id.as_str()))),
221            );
222        }
223        map
224    }
225
226    /// Build depth map: node_id -> depth (0 for roots).
227    pub fn build_depth_map(&self) -> HashMap<String, u32> {
228        let mut map = HashMap::new();
229        let mut stack: Vec<(&Node, u32)> =
230            self.structure.iter().rev().map(|root| (root, 0)).collect();
231        while let Some((node, depth)) = stack.pop() {
232            map.insert(node.node_id.clone(), depth);
233            stack.extend(
234                node.children
235                    .iter()
236                    .rev()
237                    .map(|child| (child, depth.saturating_add(1))),
238            );
239        }
240        map
241    }
242
243    /// Returns the maximum one-based tree depth, or zero for an empty document.
244    pub fn max_depth(&self) -> u32 {
245        let mut maximum = 0_u32;
246        let mut stack: Vec<(&Node, u32)> =
247            self.structure.iter().rev().map(|root| (root, 1)).collect();
248        while let Some((node, depth)) = stack.pop() {
249            maximum = maximum.max(depth);
250            stack.extend(
251                node.children
252                    .iter()
253                    .rev()
254                    .map(|child| (child, depth.saturating_add(1))),
255            );
256        }
257        maximum
258    }
259
260    /// Build children map: node_id -> list of child node_ids.
261    pub fn build_children_map(&self) -> HashMap<String, Vec<String>> {
262        let mut map: HashMap<String, Vec<String>> = HashMap::new();
263        let mut stack: Vec<&Node> = self.structure.iter().rev().collect();
264        while let Some(node) = stack.pop() {
265            let child_ids: Vec<String> = node.children.iter().map(|c| c.node_id.clone()).collect();
266            if !child_ids.is_empty() {
267                map.insert(node.node_id.clone(), child_ids);
268            }
269            stack.extend(node.children.iter().rev());
270        }
271        map
272    }
273
274    /// Find a node by id.
275    pub fn find_node(&self, node_id: &str) -> Option<&Node> {
276        let mut stack: Vec<&Node> = self.structure.iter().rev().collect();
277        while let Some(node) = stack.pop() {
278            if node.node_id == node_id {
279                return Some(node);
280            }
281            stack.extend(node.children.iter().rev());
282        }
283        None
284    }
285
286    /// Get path from root to a node (list of node_ids, root first).
287    pub fn path_to_node(&self, node_id: &str) -> Vec<String> {
288        let parent_map = self.build_parent_map();
289        let mut path = Vec::new();
290        let mut visited = HashSet::new();
291        let mut current = Some(node_id.to_string());
292        while let Some(nid) = current {
293            if !visited.insert(nid.clone()) {
294                return Vec::new();
295            }
296            path.push(nid.clone());
297            current = parent_map.get(&nid).and_then(|p| p.clone());
298        }
299        path.reverse();
300        path
301    }
302
303    /// Assign sequential node IDs to all nodes.
304    pub fn assign_node_ids(&mut self) {
305        let mut counter = 0u32;
306        let mut stack: Vec<&mut Node> = self.structure.iter_mut().rev().collect();
307        while let Some(node) = stack.pop() {
308            node.node_id = counter.to_string();
309            counter = counter.saturating_add(1);
310            stack.extend(node.children.iter_mut().rev());
311        }
312    }
313}
314
315/// Search result from FTS5.
316#[derive(Debug, Clone, Serialize, Deserialize)]
317pub struct SearchResult {
318    pub node_id: NodeId,
319    pub doc_id: String,
320    pub doc_name: String,
321    pub title: String,
322    pub summary: String,
323    pub text: String,
324    pub source_type: String,
325    pub source_path: String,
326    pub line_start: Option<u32>,
327    pub line_end: Option<u32>,
328    pub score: f64,
329    pub depth: u32,
330    /// Breadcrumb path from root to this node.
331    #[serde(default)]
332    pub breadcrumb: Vec<String>,
333}
334
335#[cfg(test)]
336mod tests {
337    use super::*;
338
339    fn sample_doc() -> Document {
340        let mut doc = Document::new("test", "test.rs", SourceType::Code);
341        let mut root = Node::new("0", "Root");
342        let mut child1 = Node::new("1", "Child 1");
343        child1.text = "some text".into();
344        let child2 = Node::new("2", "Child 2");
345        child1.children.push(Node::new("3", "Grandchild"));
346        root.children.push(child1);
347        root.children.push(child2);
348        doc.structure.push(root);
349        doc
350    }
351
352    #[test]
353    fn test_flatten_nodes() {
354        let doc = sample_doc();
355        let flat = doc.flatten_nodes();
356        assert_eq!(flat.len(), 4);
357        assert_eq!(flat[0].title, "Root");
358        assert_eq!(flat[1].title, "Child 1");
359        assert_eq!(flat[2].title, "Grandchild");
360        assert_eq!(flat[3].title, "Child 2");
361    }
362
363    #[test]
364    fn test_parent_map() {
365        let doc = sample_doc();
366        let pm = doc.build_parent_map();
367        assert_eq!(pm["0"], None);
368        assert_eq!(pm["1"], Some("0".into()));
369        assert_eq!(pm["3"], Some("1".into()));
370    }
371
372    #[test]
373    fn test_depth_map() {
374        let doc = sample_doc();
375        let dm = doc.build_depth_map();
376        assert_eq!(dm["0"], 0);
377        assert_eq!(dm["1"], 1);
378        assert_eq!(dm["3"], 2);
379    }
380
381    #[test]
382    fn test_find_node() {
383        let doc = sample_doc();
384        assert!(doc.find_node("3").is_some());
385        assert_eq!(doc.find_node("3").unwrap().title, "Grandchild");
386        assert!(doc.find_node("999").is_none());
387    }
388
389    #[test]
390    fn test_path_to_node() {
391        let doc = sample_doc();
392        let path = doc.path_to_node("3");
393        assert_eq!(path, vec!["0", "1", "3"]);
394    }
395
396    #[test]
397    fn test_assign_node_ids() {
398        let mut doc = Document::new("test", "test.rs", SourceType::Code);
399        let mut root = Node::new("", "Root");
400        root.children.push(Node::new("", "A"));
401        root.children.push(Node::new("", "B"));
402        doc.structure.push(root);
403        doc.assign_node_ids();
404        assert_eq!(doc.structure[0].node_id, "0");
405        assert_eq!(doc.structure[0].children[0].node_id, "1");
406        assert_eq!(doc.structure[0].children[1].node_id, "2");
407    }
408
409    #[test]
410    fn validation_rejects_duplicate_ids_and_invalid_ranges() {
411        let mut duplicate = sample_doc();
412        duplicate.structure[0].children[1].node_id = "1".into();
413        assert_eq!(
414            duplicate.validate_structure(),
415            Err(DocumentStructureError::DuplicateNodeId {
416                node_id: "1".into()
417            })
418        );
419
420        let mut invalid_range = sample_doc();
421        invalid_range.structure[0].line_start = Some(4);
422        invalid_range.structure[0].line_end = Some(3);
423        assert_eq!(
424            invalid_range.validate_structure(),
425            Err(DocumentStructureError::InvalidLineRange {
426                node_id: "0".into()
427            })
428        );
429    }
430
431    #[test]
432    fn iterative_lookups_handle_a_deep_tree() {
433        let mut node = Node::new("4095", "leaf");
434        for depth in (0..4095).rev() {
435            let mut parent = Node::new(depth.to_string(), "node");
436            parent.children.push(node);
437            node = parent;
438        }
439        let mut document = Document::new("deep", "Deep", SourceType::Markdown);
440        document.structure.push(node);
441
442        assert_eq!(document.flatten_nodes().len(), 4096);
443        assert_eq!(
444            document.find_node("4095").map(|node| node.title.as_str()),
445            Some("leaf")
446        );
447        assert_eq!(document.max_depth(), 4096);
448        assert_eq!(document.path_to_node("4095").len(), 4096);
449    }
450
451    #[test]
452    fn test_source_type_from_extension() {
453        assert_eq!(SourceType::from_extension("rs"), SourceType::Code);
454        assert_eq!(SourceType::from_extension("md"), SourceType::Markdown);
455        assert_eq!(SourceType::from_extension("html"), SourceType::Html);
456        assert_eq!(SourceType::from_extension("json"), SourceType::Json);
457        assert_eq!(SourceType::from_extension("xyz"), SourceType::Unknown);
458    }
459}