Skip to main content

xrack_runtime/
tree.rs

1use crate::{ChangeSignal, Property, RowKey, RowSelection, VecModel, list::MAX_ROWS};
2use std::{
3    cell::RefCell,
4    collections::{BTreeMap, HashMap, HashSet},
5    rc::Rc,
6    sync::Arc,
7};
8
9#[derive(Clone, Copy, Debug, PartialEq, Eq)]
10pub enum TreeAction {
11    SetExpanded {
12        key: i64,
13        row: RowKey,
14        expanded: bool,
15    },
16    Selection(TreeSelectionAction),
17}
18
19#[derive(Clone, Copy, Debug, PartialEq, Eq)]
20pub enum TreeSelectionAction {
21    Row {
22        key: i64,
23        row: RowKey,
24        operation: RowSelection,
25    },
26    All,
27    Clear,
28}
29
30#[doc(hidden)]
31pub struct TreeSelectionChange {
32    pub current: Option<i64>,
33    pub selected_count: Option<usize>,
34}
35
36#[derive(Clone, Copy, Debug, PartialEq, Eq)]
37pub struct TreeItem {
38    pub key: i64,
39    pub row: RowKey,
40    pub model_index: usize,
41    pub parent: Option<i64>,
42    pub depth: usize,
43    pub has_children: bool,
44    pub expanded: bool,
45}
46
47#[derive(Debug, PartialEq, Eq)]
48struct Entry {
49    key: i64,
50    row: RowKey,
51    model_index: usize,
52    parent: Option<usize>,
53    children: Vec<usize>,
54}
55
56#[derive(Debug, PartialEq, Eq)]
57struct Topology {
58    model: u64,
59    entries: Vec<Entry>,
60    index: HashMap<i64, usize>,
61    roots: Vec<usize>,
62}
63
64impl Topology {
65    fn new<T>(model: &VecModel<T>, model_id: u64, roles: impl Fn(&T) -> (i64, i64)) -> Self {
66        let mut candidates = Vec::new();
67        let mut seen = HashSet::new();
68        let mut duplicates = HashSet::new();
69        model.visit_rows_untracked(MAX_ROWS, |index, row, item| {
70            let (key, parent) = roles(item);
71            if key < 0 {
72                return;
73            }
74            if !seen.insert(key) {
75                duplicates.insert(key);
76            }
77            candidates.push((index, row, key, parent));
78        });
79        candidates.retain(|(_, _, key, _)| !duplicates.contains(key));
80        let index: HashMap<_, _> = candidates
81            .iter()
82            .enumerate()
83            .map(|(index, (_, _, key, _))| (*key, index))
84            .collect();
85        let mut entries: Vec<_> = candidates
86            .into_iter()
87            .map(|(model_index, row, key, parent)| Entry {
88                key,
89                row,
90                model_index,
91                parent: index.get(&parent).copied(),
92                children: Vec::new(),
93            })
94            .collect();
95
96        // Follow parent chains iteratively and break cycles at the smallest key.
97        let mut state = vec![0_u8; entries.len()];
98        let mut chain = Vec::new();
99        for start in 0..entries.len() {
100            let mut current = Some(start);
101            while let Some(node) = current {
102                if state[node] == 2 {
103                    break;
104                }
105                if state[node] == 1 {
106                    let cycle = chain
107                        .iter()
108                        .copied()
109                        .rev()
110                        .take_while(|&index| index != node);
111                    let root = cycle
112                        .chain(std::iter::once(node))
113                        .min_by_key(|&index| entries[index].key)
114                        .unwrap();
115                    entries[root].parent = None;
116                    break;
117                }
118                state[node] = 1;
119                chain.push(node);
120                current = entries[node].parent;
121            }
122            for node in chain.drain(..) {
123                state[node] = 2;
124            }
125        }
126        let mut roots = Vec::new();
127        for child in 0..entries.len() {
128            if let Some(parent) = entries[child].parent {
129                entries[parent].children.push(child);
130            } else {
131                roots.push(child);
132            }
133        }
134        Self {
135            model: model_id,
136            entries,
137            index,
138            roots,
139        }
140    }
141
142    fn row_key(&self, key: i64) -> Option<RowKey> {
143        self.index.get(&key).map(|&index| self.entries[index].row)
144    }
145}
146
147/// The flattened navigation order. Row delegates are materialized separately by the viewport.
148#[derive(Debug, PartialEq, Eq)]
149pub struct TreeSnapshot {
150    topology: Arc<Topology>,
151    visible: Vec<TreeItem>,
152    visible_indices: HashMap<i64, usize>,
153}
154
155impl TreeSnapshot {
156    fn new(topology: Arc<Topology>, expanded: &BTreeMap<i64, RowKey>) -> Self {
157        let mut visible = Vec::new();
158        let mut pending: Vec<_> = topology
159            .roots
160            .iter()
161            .rev()
162            .map(|&index| (index, 0))
163            .collect();
164        while let Some((index, depth)) = pending.pop() {
165            let node = &topology.entries[index];
166            let has_children = !node.children.is_empty();
167            let expanded = has_children && expanded.get(&node.key) == Some(&node.row);
168            visible.push(TreeItem {
169                key: node.key,
170                row: node.row,
171                model_index: node.model_index,
172                parent: node.parent.map(|index| topology.entries[index].key),
173                depth,
174                has_children,
175                expanded,
176            });
177            if expanded {
178                pending.extend(node.children.iter().rev().map(|&index| (index, depth + 1)));
179            }
180        }
181        let visible_indices = visible
182            .iter()
183            .enumerate()
184            .map(|(index, item)| (item.key, index))
185            .collect();
186        Self {
187            topology,
188            visible,
189            visible_indices,
190        }
191    }
192
193    pub fn rows(&self) -> &[TreeItem] {
194        &self.visible
195    }
196
197    pub fn visible_index(&self, key: i64) -> Option<usize> {
198        self.visible_indices.get(&key).copied()
199    }
200
201    #[doc(hidden)]
202    pub fn same_model(&self, other: &Self) -> bool {
203        self.topology.model == other.topology.model
204    }
205
206    pub fn is_descendant(&self, key: i64, ancestor: i64) -> bool {
207        let Some(&index) = self.topology.index.get(&key) else {
208            return false;
209        };
210        let mut parent = self.topology.entries[index].parent;
211        while let Some(index) = parent {
212            let node = &self.topology.entries[index];
213            if node.key == ancestor {
214                return true;
215            }
216            parent = node.parent;
217        }
218        false
219    }
220}
221
222#[derive(Default)]
223struct Selection {
224    keys: Arc<BTreeMap<i64, RowKey>>,
225    anchor: Option<(i64, RowKey)>,
226}
227
228impl Selection {
229    fn retain_live(&mut self, topology: &Topology) {
230        let live = |key, row| topology.row_key(key) == Some(row);
231        if self.keys.iter().any(|(&key, &row)| !live(key, row)) {
232            Arc::make_mut(&mut self.keys).retain(|&key, row| live(key, *row));
233        }
234        self.anchor = self.anchor.filter(|&(key, row)| live(key, row));
235    }
236}
237
238#[doc(hidden)]
239#[derive(Default)]
240pub struct TreeState {
241    topology: Property<Arc<Topology>>,
242    roles_changed: RefCell<Option<(u64, Rc<ChangeSignal>)>>,
243    snapshot: Property<Arc<TreeSnapshot>>,
244    expanded: Property<BTreeMap<i64, RowKey>>,
245    selection: RefCell<Selection>,
246    selection_changed: ChangeSignal,
247}
248
249impl TreeState {
250    /// Read topology from a stable, pure projection of a row's key and parent key.
251    pub fn snapshot<T>(
252        &self,
253        model: impl FnOnce() -> Rc<VecModel<T>>,
254        roles: impl Fn(&T) -> (i64, i64) + Clone + 'static,
255    ) -> Arc<TreeSnapshot> {
256        self.snapshot.get(|| {
257            let topology = self.topology.get(|| {
258                let model = model();
259                let model_id = model.structure_stamp().0;
260                {
261                    let mut observation = self.roles_changed.borrow_mut();
262                    if let Some((_, signal)) =
263                        observation.as_ref().filter(|(id, _)| *id == model_id)
264                    {
265                        signal.track();
266                    } else {
267                        let signal = model.observe_projection(MAX_ROWS, roles.clone());
268                        signal.track();
269                        *observation = Some((model_id, signal));
270                    }
271                }
272                let topology = Arc::new(Topology::new(&model, model_id, roles));
273                self.selection.borrow_mut().retain_live(&topology);
274                topology
275            });
276            Arc::new(TreeSnapshot::new(
277                topology,
278                &self.expanded.get(BTreeMap::new),
279            ))
280        })
281    }
282
283    pub fn set_expanded(&self, tree: &TreeSnapshot, key: i64, row: RowKey, expanded: bool) -> bool {
284        if !tree
285            .visible_index(key)
286            .and_then(|index| tree.rows().get(index))
287            .is_some_and(|item| item.row == row && item.has_children && item.expanded != expanded)
288        {
289            return false;
290        }
291        let mut state = self.expanded.get(BTreeMap::new);
292        state.retain(|key, row| tree.topology.row_key(*key) == Some(*row));
293        if expanded {
294            state.insert(key, row);
295        } else {
296            state.remove(&key);
297        }
298        self.expanded.set_if_changed(state);
299        true
300    }
301
302    pub fn selection(&self) -> Arc<BTreeMap<i64, RowKey>> {
303        self.selection_changed.track();
304        self.selection.borrow().keys.clone()
305    }
306
307    pub fn select(
308        &self,
309        tree: &TreeSnapshot,
310        current: i64,
311        action: TreeSelectionAction,
312    ) -> Option<TreeSelectionChange> {
313        let mut selection = self.selection.borrow_mut();
314        let mut next = selection.keys.clone();
315        let current = match action {
316            TreeSelectionAction::Row {
317                key,
318                row,
319                operation,
320            } => {
321                let index = tree.visible_index(key)?;
322                if tree.rows()[index].row != row {
323                    return None;
324                }
325                match operation {
326                    RowSelection::Replace => {
327                        next = Arc::new(BTreeMap::from([(key, row)]));
328                        selection.anchor = Some((key, row));
329                    }
330                    RowSelection::Toggle => {
331                        let selected = Arc::make_mut(&mut next);
332                        if selected.remove(&key).is_none() {
333                            selected.insert(key, row);
334                        }
335                        selection.anchor = Some((key, row));
336                    }
337                    RowSelection::Extend | RowSelection::AddRange => {
338                        let start = selection
339                            .anchor
340                            .and_then(|(key, _)| tree.visible_index(key))
341                            .or_else(|| tree.visible_index(current))
342                            .unwrap_or(index);
343                        let anchor = &tree.rows()[start];
344                        selection.anchor = Some((anchor.key, anchor.row));
345                        let rows = tree.rows()[start.min(index)..=start.max(index)]
346                            .iter()
347                            .map(|item| (item.key, item.row));
348                        if operation == RowSelection::Extend {
349                            next = Arc::new(rows.collect());
350                        } else {
351                            Arc::make_mut(&mut next).extend(rows);
352                        }
353                    }
354                    RowSelection::Move => {}
355                }
356                (key != current).then_some(key)
357            }
358            TreeSelectionAction::All => {
359                next = Arc::new(
360                    tree.rows()
361                        .iter()
362                        .map(|item| (item.key, item.row))
363                        .collect(),
364                );
365                selection.anchor = None;
366                None
367            }
368            TreeSelectionAction::Clear => {
369                next = Arc::new(BTreeMap::new());
370                selection.anchor = None;
371                None
372            }
373        };
374        let selected_count = (next != selection.keys).then_some(next.len());
375        if selected_count.is_some() {
376            selection.keys = next;
377            self.selection_changed.notify();
378        }
379        Some(TreeSelectionChange {
380            current,
381            selected_count,
382        })
383    }
384}
385
386#[cfg(test)]
387mod tests {
388    use super::*;
389    use std::cell::Cell;
390
391    #[test]
392    fn projection_handles_cycles_orphans_and_duplicates_without_rebuilding_on_expand() {
393        let model = Rc::new(VecModel::from(vec![
394            (9, 8),
395            (8, 9),
396            (10, 9),
397            (3, -1),
398            (3, -1),
399            (6, 3),
400            (7, 7),
401        ]));
402        let state = TreeState::default();
403        let reads = Rc::new(Cell::new(0));
404        let role_reads = reads.clone();
405        let roles = move |item: &(i64, i64)| {
406            role_reads.set(role_reads.get() + 1);
407            *item
408        };
409        let tree = state.snapshot(|| model.clone(), roles.clone());
410        assert_eq!(
411            tree.rows().iter().map(|row| row.key).collect::<Vec<_>>(),
412            [8, 6, 7]
413        );
414        assert!(tree.is_descendant(10, 8));
415        assert!(!tree.is_descendant(8, 9));
416        let root = tree.rows()[0];
417        assert!(state.set_expanded(&tree, root.key, root.row, true));
418        let expanded = state.snapshot(|| model.clone(), roles.clone());
419        assert_eq!(reads.get(), 7);
420        assert_eq!(
421            expanded
422                .rows()
423                .iter()
424                .map(|row| row.key)
425                .collect::<Vec<_>>(),
426            [8, 9, 6, 7]
427        );
428        assert!(model.set_row(2, (10, 6)));
429        assert_eq!(reads.get(), 9);
430        let reparented = state.snapshot(|| model.clone(), roles);
431        assert_eq!(reads.get(), 16);
432        assert!(!reparented.is_descendant(10, 8));
433        assert!(reparented.is_descendant(10, 6));
434        assert!(reparented.rows()[0].expanded);
435    }
436
437    #[test]
438    fn payload_changes_leave_independent_tree_projections_clean() {
439        let model = Rc::new(VecModel::from(vec![(1, -1, -1, 0), (2, 1, -1, 0)]));
440        let source = Property::default();
441        source.set(model.clone());
442        let primary = TreeState::default();
443        let alternate = TreeState::default();
444        let roles = |row: &(i64, i64, i64, i64)| (row.0, row.1);
445        let other_roles = |row: &(i64, i64, i64, i64)| (row.0, row.2);
446        let primary_tree = || primary.snapshot(|| source.get(|| unreachable!()), roles);
447        let alternate_tree = || alternate.snapshot(|| model.clone(), other_roles);
448        let first = primary_tree();
449        let second = alternate_tree();
450
451        assert!(model.set_row(1, (2, 1, -1, 50)));
452        assert!(Arc::ptr_eq(&first, &primary_tree()));
453        assert!(Arc::ptr_eq(&second, &alternate_tree()));
454        assert!(model.set_row(1, (2, 1, 1, 50)));
455        assert!(Arc::ptr_eq(&first, &primary_tree()));
456        let reparented = alternate_tree();
457        assert!(!Arc::ptr_eq(&second, &reparented));
458        assert!(reparented.is_descendant(2, 1));
459
460        source.set(Rc::new(VecModel::from(vec![(3, -1, -1, 0)])));
461        let replacement = primary_tree();
462        assert!(!replacement.same_model(&first));
463        assert_eq!(replacement.rows()[0].key, 3);
464        assert!(model.set_row(1, (2, -1, -1, 50)));
465        assert!(Arc::ptr_eq(&replacement, &primary_tree()));
466        assert!(!alternate_tree().is_descendant(2, 1));
467        assert!(model.sort_by(|left, right| right.0.cmp(&left.0)));
468        assert_eq!(alternate_tree().rows()[0].key, 2);
469        assert!(Arc::ptr_eq(&replacement, &primary_tree()));
470    }
471}