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        }
140    }
141
142    fn add_part_of(store: &mut Store, child: &str, parent: &str) {
143        store.add_edge(
144            EntityId(child.to_string()),
145            Edge {
146                rel_type: "PART_OF".to_string(),
147                target: EntityId(parent.to_string()),
148                source: EdgeSource::Explicit,
149            },
150        );
151    }
152
153    #[test]
154    fn ancestors_empty_for_root() {
155        let mut store = Store::new();
156        store.upsert(EntityId("s--root".into()), entity("s--root", "s"));
157        let ancs = ancestors(&store, &EntityId("s--root".into()), "PART_OF");
158        assert!(ancs.is_empty());
159    }
160
161    #[test]
162    fn ancestors_single_parent() {
163        let mut store = Store::new();
164        store.upsert(EntityId("s--parent".into()), entity("s--parent", "s"));
165        store.upsert(EntityId("s--child".into()), entity("s--child", "s"));
166        add_part_of(&mut store, "s--child", "s--parent");
167
168        let ancs = ancestors(&store, &EntityId("s--child".into()), "PART_OF");
169        assert_eq!(ancs, vec![EntityId("s--parent".into())]);
170    }
171
172    #[test]
173    fn ancestors_chain() {
174        let mut store = Store::new();
175        store.upsert(EntityId("s--root".into()), entity("s--root", "s"));
176        store.upsert(EntityId("s--mid".into()), entity("s--mid", "s"));
177        store.upsert(EntityId("s--leaf".into()), entity("s--leaf", "s"));
178        add_part_of(&mut store, "s--leaf", "s--mid");
179        add_part_of(&mut store, "s--mid", "s--root");
180
181        let ancs = ancestors(&store, &EntityId("s--leaf".into()), "PART_OF");
182        assert_eq!(
183            ancs,
184            vec![EntityId("s--mid".into()), EntityId("s--root".into())]
185        );
186    }
187
188    #[test]
189    fn ancestors_cycle_detection() {
190        let mut store = Store::new();
191        store.upsert(EntityId("s--a".into()), entity("s--a", "s"));
192        store.upsert(EntityId("s--b".into()), entity("s--b", "s"));
193        add_part_of(&mut store, "s--a", "s--b");
194        add_part_of(&mut store, "s--b", "s--a");
195
196        let ancs = ancestors(&store, &EntityId("s--a".into()), "PART_OF");
197        assert_eq!(ancs, vec![EntityId("s--b".into())]); // stops at cycle
198    }
199
200    #[test]
201    fn ancestors_stops_at_mem_boundary() {
202        let mut store = Store::new();
203        store.upsert(EntityId("s--child".into()), entity("s--child", "s"));
204        store.upsert(
205            EntityId("other--parent".into()),
206            entity("other--parent", "other"),
207        );
208        add_part_of(&mut store, "s--child", "other--parent");
209
210        let ancs = ancestors(&store, &EntityId("s--child".into()), "PART_OF");
211        assert!(ancs.is_empty()); // parent is in different mem
212    }
213
214    #[test]
215    fn descendants_of_root() {
216        let mut store = Store::new();
217        store.upsert(EntityId("s--root".into()), entity("s--root", "s"));
218        store.upsert(EntityId("s--a".into()), entity("s--a", "s"));
219        store.upsert(EntityId("s--b".into()), entity("s--b", "s"));
220        store.upsert(EntityId("s--a/c".into()), entity("s--a/c", "s"));
221        add_part_of(&mut store, "s--a", "s--root");
222        add_part_of(&mut store, "s--b", "s--root");
223        add_part_of(&mut store, "s--a/c", "s--a");
224
225        let desc = descendants(&store, &EntityId("s--root".into()), "PART_OF");
226        assert_eq!(desc.len(), 3);
227    }
228
229    #[test]
230    fn descendants_stops_at_mem_boundary() {
231        let mut store = Store::new();
232        store.upsert(EntityId("s--root".into()), entity("s--root", "s"));
233        store.upsert(
234            EntityId("other--child".into()),
235            entity("other--child", "other"),
236        );
237        add_part_of(&mut store, "other--child", "s--root");
238
239        let desc = descendants(&store, &EntityId("s--root".into()), "PART_OF");
240        assert!(desc.is_empty());
241    }
242
243    #[test]
244    fn descendants_empty_for_leaf() {
245        let mut store = Store::new();
246        store.upsert(EntityId("s--leaf".into()), entity("s--leaf", "s"));
247
248        let desc = descendants(&store, &EntityId("s--leaf".into()), "PART_OF");
249        assert!(desc.is_empty());
250    }
251
252    #[test]
253    fn compute_file_path_root_entity() {
254        let mut store = Store::new();
255        store.upsert(EntityId("s--my-entity".into()), entity("s--my-entity", "s"));
256
257        let path = compute_file_path(&store, &EntityId("s--my-entity".into()), "PART_OF");
258        assert_eq!(path, "my-entity.md");
259    }
260
261    #[test]
262    fn compute_file_path_nested() {
263        let mut store = Store::new();
264        store.upsert(EntityId("s--root".into()), entity("s--root", "s"));
265        store.upsert(EntityId("s--child".into()), entity("s--child", "s"));
266        add_part_of(&mut store, "s--child", "s--root");
267
268        let path = compute_file_path(&store, &EntityId("s--child".into()), "PART_OF");
269        assert_eq!(path, "root/child.md");
270    }
271
272    #[test]
273    fn compute_file_path_deeply_nested() {
274        let mut store = Store::new();
275        store.upsert(EntityId("s--gp".into()), entity("s--gp", "s"));
276        store.upsert(EntityId("s--parent".into()), entity("s--parent", "s"));
277        store.upsert(EntityId("s--child".into()), entity("s--child", "s"));
278        add_part_of(&mut store, "s--child", "s--parent");
279        add_part_of(&mut store, "s--parent", "s--gp");
280
281        let path = compute_file_path(&store, &EntityId("s--child".into()), "PART_OF");
282        assert_eq!(path, "gp/parent/child.md");
283    }
284}
memstead_base/graph/relations.rs

memstead_base/graph/
relations.rs
