memstead_base/graph/
relations.rs

1//! PART_OF hierarchy traversal — ancestors and descendants.
2
3use std::collections::HashSet;
4
5use crate::entity::EntityId;
6use crate::store::Store;
7
8/// Get all ancestors of an entity via PART_OF chain (with cycle detection).
9/// Returns ancestors from immediate parent to root, same-mem only.
10pub fn ancestors(store: &Store, id: &EntityId, hierarchy_rel: &str) -> Vec<EntityId> {
11    let node = match store.get(id) {
12        Some(n) => n,
13        None => return Vec::new(),
14    };
15    let mem = &node.mem;
16
17    let mut result = Vec::new();
18    let mut visited = HashSet::new();
19    visited.insert(id.clone());
20
21    let mut current = id.clone();
22
23    loop {
24        // Find PART_OF edge in outgoing (child PART_OF parent)
25        let parent = store
26            .outgoing(&current)
27            .iter()
28            .find(|e| e.rel_type == hierarchy_rel)
29            .map(|e| e.target.clone());
30
31        let parent_id = match parent {
32            Some(pid) => pid,
33            None => break,
34        };
35
36        // Cycle detection
37        if visited.contains(&parent_id) {
38            break;
39        }
40
41        // Cross-mem boundary
42        let parent_node = match store.get(&parent_id) {
43            Some(n) => n,
44            None => break,
45        };
46        if parent_node.mem != *mem {
47            break;
48        }
49
50        result.push(parent_id.clone());
51        visited.insert(parent_id.clone());
52        current = parent_id;
53    }
54
55    result
56}
57
58/// Get all descendants of an entity via PART_OF hierarchy (BFS).
59/// Uses incoming PART_OF edges to find children. Same-mem only.
60pub fn descendants(store: &Store, id: &EntityId, hierarchy_rel: &str) -> Vec<EntityId> {
61    let node = match store.get(id) {
62        Some(n) => n,
63        None => return Vec::new(),
64    };
65    let mem = &node.mem;
66
67    let mut result = Vec::new();
68    let mut visited = HashSet::new();
69    visited.insert(id.clone());
70
71    // BFS using a manual queue
72    let mut queue = vec![id.clone()];
73    let mut head = 0;
74
75    while head < queue.len() {
76        let current = queue[head].clone();
77        head += 1;
78
79        // Children are entities with an outgoing PART_OF edge pointing to `current`
80        // So we look at incoming edges of `current` with the hierarchy relationship
81        for edge in store.incoming(&current) {
82            if edge.rel_type != hierarchy_rel {
83                continue;
84            }
85            if visited.contains(&edge.from) {
86                continue;
87            }
88            let child_node = match store.get(&edge.from) {
89                Some(n) => n,
90                None => continue,
91            };
92            if child_node.mem != *mem {
93                continue;
94            }
95            visited.insert(edge.from.clone());
96            result.push(edge.from.clone());
97            queue.push(edge.from.clone());
98        }
99    }
100
101    result
102}
103
104/// Compute file path for an entity based on its PART_OF ancestry.
105/// Path is: `grandparent/parent/entity-name.md` (reversed ancestor chain).
106pub fn compute_file_path(store: &Store, id: &EntityId, hierarchy_rel: &str) -> String {
107    let ancs = ancestors(store, id, hierarchy_rel);
108    let name = id.name();
109
110    if ancs.is_empty() {
111        return format!("{name}.md");
112    }
113
114    let segments: Vec<&str> = ancs.iter().rev().map(|a| a.name()).collect();
115    format!("{}/{name}.md", segments.join("/"))
116}
117
118#[cfg(test)]
119mod tests {
120    use super::*;
121    use crate::entity::Entity;
122    use crate::store::{Edge, EdgeSource};
123    use indexmap::IndexMap;
124
125    fn entity(id: &str, mem: &str) -> Entity {
126        Entity {
127            id: EntityId(id.to_string()),
128            title: id.to_string(),
129            entity_type: "spec".to_string(),
130            mem: mem.to_string(),
131            file_path: String::new(),
132            metadata: IndexMap::new(),
133            sections: IndexMap::new(),
134            relationships: Vec::new(),
135            content_hash: String::new(),
136            stub: false,
137            stub_kind: None,
138            heading_spans: std::collections::HashMap::new(),
139            raw_section_headings: Vec::new(),
140        }
141    }
142
143    fn add_part_of(store: &mut Store, child: &str, parent: &str) {
144        store.add_edge(
145            EntityId(child.to_string()),
146            Edge {
147                rel_type: "PART_OF".to_string(),
148                target: EntityId(parent.to_string()),
149                source: EdgeSource::Explicit,
150            },
151        );
152    }
153
154    #[test]
155    fn ancestors_empty_for_root() {
156        let mut store = Store::new();
157        store.upsert(EntityId("s--root".into()), entity("s--root", "s"));
158        let ancs = ancestors(&store, &EntityId("s--root".into()), "PART_OF");
159        assert!(ancs.is_empty());
160    }
161
162    #[test]
163    fn ancestors_single_parent() {
164        let mut store = Store::new();
165        store.upsert(EntityId("s--parent".into()), entity("s--parent", "s"));
166        store.upsert(EntityId("s--child".into()), entity("s--child", "s"));
167        add_part_of(&mut store, "s--child", "s--parent");
168
169        let ancs = ancestors(&store, &EntityId("s--child".into()), "PART_OF");
170        assert_eq!(ancs, vec![EntityId("s--parent".into())]);
171    }
172
173    #[test]
174    fn ancestors_chain() {
175        let mut store = Store::new();
176        store.upsert(EntityId("s--root".into()), entity("s--root", "s"));
177        store.upsert(EntityId("s--mid".into()), entity("s--mid", "s"));
178        store.upsert(EntityId("s--leaf".into()), entity("s--leaf", "s"));
179        add_part_of(&mut store, "s--leaf", "s--mid");
180        add_part_of(&mut store, "s--mid", "s--root");
181
182        let ancs = ancestors(&store, &EntityId("s--leaf".into()), "PART_OF");
183        assert_eq!(
184            ancs,
185            vec![EntityId("s--mid".into()), EntityId("s--root".into())]
186        );
187    }
188
189    #[test]
190    fn ancestors_cycle_detection() {
191        let mut store = Store::new();
192        store.upsert(EntityId("s--a".into()), entity("s--a", "s"));
193        store.upsert(EntityId("s--b".into()), entity("s--b", "s"));
194        add_part_of(&mut store, "s--a", "s--b");
195        add_part_of(&mut store, "s--b", "s--a");
196
197        let ancs = ancestors(&store, &EntityId("s--a".into()), "PART_OF");
198        assert_eq!(ancs, vec![EntityId("s--b".into())]); // stops at cycle
199    }
200
201    #[test]
202    fn ancestors_stops_at_mem_boundary() {
203        let mut store = Store::new();
204        store.upsert(EntityId("s--child".into()), entity("s--child", "s"));
205        store.upsert(
206            EntityId("other--parent".into()),
207            entity("other--parent", "other"),
208        );
209        add_part_of(&mut store, "s--child", "other--parent");
210
211        let ancs = ancestors(&store, &EntityId("s--child".into()), "PART_OF");
212        assert!(ancs.is_empty()); // parent is in different mem
213    }
214
215    #[test]
216    fn descendants_of_root() {
217        let mut store = Store::new();
218        store.upsert(EntityId("s--root".into()), entity("s--root", "s"));
219        store.upsert(EntityId("s--a".into()), entity("s--a", "s"));
220        store.upsert(EntityId("s--b".into()), entity("s--b", "s"));
221        store.upsert(EntityId("s--a/c".into()), entity("s--a/c", "s"));
222        add_part_of(&mut store, "s--a", "s--root");
223        add_part_of(&mut store, "s--b", "s--root");
224        add_part_of(&mut store, "s--a/c", "s--a");
225
226        let desc = descendants(&store, &EntityId("s--root".into()), "PART_OF");
227        assert_eq!(desc.len(), 3);
228    }
229
230    #[test]
231    fn descendants_stops_at_mem_boundary() {
232        let mut store = Store::new();
233        store.upsert(EntityId("s--root".into()), entity("s--root", "s"));
234        store.upsert(
235            EntityId("other--child".into()),
236            entity("other--child", "other"),
237        );
238        add_part_of(&mut store, "other--child", "s--root");
239
240        let desc = descendants(&store, &EntityId("s--root".into()), "PART_OF");
241        assert!(desc.is_empty());
242    }
243
244    #[test]
245    fn descendants_empty_for_leaf() {
246        let mut store = Store::new();
247        store.upsert(EntityId("s--leaf".into()), entity("s--leaf", "s"));
248
249        let desc = descendants(&store, &EntityId("s--leaf".into()), "PART_OF");
250        assert!(desc.is_empty());
251    }
252
253    #[test]
254    fn compute_file_path_root_entity() {
255        let mut store = Store::new();
256        store.upsert(EntityId("s--my-entity".into()), entity("s--my-entity", "s"));
257
258        let path = compute_file_path(&store, &EntityId("s--my-entity".into()), "PART_OF");
259        assert_eq!(path, "my-entity.md");
260    }
261
262    #[test]
263    fn compute_file_path_nested() {
264        let mut store = Store::new();
265        store.upsert(EntityId("s--root".into()), entity("s--root", "s"));
266        store.upsert(EntityId("s--child".into()), entity("s--child", "s"));
267        add_part_of(&mut store, "s--child", "s--root");
268
269        let path = compute_file_path(&store, &EntityId("s--child".into()), "PART_OF");
270        assert_eq!(path, "root/child.md");
271    }
272
273    #[test]
274    fn compute_file_path_deeply_nested() {
275        let mut store = Store::new();
276        store.upsert(EntityId("s--gp".into()), entity("s--gp", "s"));
277        store.upsert(EntityId("s--parent".into()), entity("s--parent", "s"));
278        store.upsert(EntityId("s--child".into()), entity("s--child", "s"));
279        add_part_of(&mut store, "s--child", "s--parent");
280        add_part_of(&mut store, "s--parent", "s--gp");
281
282        let path = compute_file_path(&store, &EntityId("s--child".into()), "PART_OF");
283        assert_eq!(path, "gp/parent/child.md");
284    }
285}
memstead_base/graph/relations.rs

memstead_base/graph/
relations.rs
