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, Weak},
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/// Commands address the model's stable non-negative business keys.
20#[derive(Clone, Copy, Debug, PartialEq, Eq)]
21pub enum TreeCommand {
22    Expand(i64),
23    Collapse(i64),
24    ToggleExpanded(i64),
25    ExpandRecursively { key: i64, depth: i64 },
26    CollapseRecursively(i64),
27    ExpandTo(i64),
28}
29
30#[doc(hidden)]
31pub struct TreeExpansionChange {
32    pub key: i64,
33    pub expanded: bool,
34}
35
36#[derive(Clone, Copy, Debug, PartialEq, Eq)]
37pub enum TreeSelectionAction {
38    Row {
39        key: i64,
40        row: RowKey,
41        operation: RowSelection,
42    },
43    All,
44    Clear,
45}
46
47#[doc(hidden)]
48pub struct TreeSelectionChange {
49    pub current: Option<i64>,
50    pub selected_count: Option<usize>,
51}
52
53#[derive(Clone, Copy, Debug, PartialEq, Eq)]
54pub struct TreeItem {
55    pub key: i64,
56    pub row: RowKey,
57    pub model_index: usize,
58    pub parent: Option<i64>,
59    pub depth: usize,
60    pub has_children: bool,
61    pub expanded: bool,
62}
63
64#[derive(Debug, PartialEq, Eq)]
65struct Entry {
66    key: i64,
67    row: RowKey,
68    model_index: usize,
69    parent: Option<usize>,
70    children: Vec<usize>,
71    depth: usize,
72    preorder: usize,
73    subtree_end: usize,
74}
75
76#[derive(Debug, PartialEq, Eq)]
77struct Topology {
78    model: u64,
79    entries: Vec<Entry>,
80    index: HashMap<i64, usize>,
81    roots: Vec<usize>,
82}
83
84impl Topology {
85    fn new<T>(model: &VecModel<T>, model_id: u64, roles: impl Fn(&T) -> (i64, i64)) -> Self {
86        let mut candidates = Vec::new();
87        let mut seen = HashSet::new();
88        let mut duplicates = HashSet::new();
89        model.visit_rows_untracked(MAX_ROWS, |index, row, item| {
90            let (key, parent) = roles(item);
91            if key < 0 {
92                return;
93            }
94            if !seen.insert(key) {
95                duplicates.insert(key);
96            }
97            candidates.push((index, row, key, parent));
98        });
99        candidates.retain(|(_, _, key, _)| !duplicates.contains(key));
100        let index: HashMap<_, _> = candidates
101            .iter()
102            .enumerate()
103            .map(|(index, (_, _, key, _))| (*key, index))
104            .collect();
105        let mut entries: Vec<_> = candidates
106            .into_iter()
107            .map(|(model_index, row, key, parent)| Entry {
108                key,
109                row,
110                model_index,
111                parent: index.get(&parent).copied(),
112                children: Vec::new(),
113                depth: 0,
114                preorder: 0,
115                subtree_end: 0,
116            })
117            .collect();
118
119        // Follow parent chains iteratively and break cycles at the smallest key.
120        let mut state = vec![0_u8; entries.len()];
121        let mut chain = Vec::new();
122        for start in 0..entries.len() {
123            let mut current = Some(start);
124            while let Some(node) = current {
125                if state[node] == 2 {
126                    break;
127                }
128                if state[node] == 1 {
129                    let cycle = chain
130                        .iter()
131                        .copied()
132                        .rev()
133                        .take_while(|&index| index != node);
134                    let root = cycle
135                        .chain(std::iter::once(node))
136                        .min_by_key(|&index| entries[index].key)
137                        .unwrap();
138                    entries[root].parent = None;
139                    break;
140                }
141                state[node] = 1;
142                chain.push(node);
143                current = entries[node].parent;
144            }
145            for node in chain.drain(..) {
146                state[node] = 2;
147            }
148        }
149        let mut roots = Vec::new();
150        for child in 0..entries.len() {
151            if let Some(parent) = entries[child].parent {
152                entries[parent].children.push(child);
153            } else {
154                roots.push(child);
155            }
156        }
157        let mut preorder = 0;
158        let mut pending: Vec<_> = roots.iter().rev().map(|&index| (index, false)).collect();
159        while let Some((index, exiting)) = pending.pop() {
160            if exiting {
161                entries[index].subtree_end = preorder;
162                continue;
163            }
164            entries[index].preorder = preorder;
165            entries[index].depth = entries[index]
166                .parent
167                .map_or(0, |parent| entries[parent].depth + 1);
168            preorder += 1;
169            pending.push((index, true));
170            pending.extend(
171                entries[index]
172                    .children
173                    .iter()
174                    .rev()
175                    .map(|&child| (child, false)),
176            );
177        }
178        Self {
179            model: model_id,
180            entries,
181            index,
182            roots,
183        }
184    }
185
186    fn contains_descendant(&self, root: usize, index: usize) -> bool {
187        let root = &self.entries[root];
188        let entry = &self.entries[index];
189        root.preorder < entry.preorder && entry.preorder < root.subtree_end
190    }
191
192    fn roots_for(&self, root_key: i64, root: Option<usize>) -> &[usize] {
193        if root_key == -1 {
194            &self.roots
195        } else {
196            root.map_or(&[], |index| self.entries[index].children.as_slice())
197        }
198    }
199
200    fn row_key(&self, key: i64) -> Option<RowKey> {
201        self.index.get(&key).map(|&index| self.entries[index].row)
202    }
203}
204
205/// The flattened navigation order. Row delegates are materialized separately by the viewport.
206#[derive(Debug, PartialEq, Eq)]
207pub struct TreeSnapshot {
208    topology: Arc<Topology>,
209    expanded: Arc<BTreeMap<i64, RowKey>>,
210    root_key: i64,
211    root: Option<usize>,
212    available: Option<Arc<[bool]>>,
213    filtering: bool,
214    visible: Vec<TreeItem>,
215    visible_indices: HashMap<i64, usize>,
216}
217
218impl TreeSnapshot {
219    fn new(
220        topology: Arc<Topology>,
221        expanded: Arc<BTreeMap<i64, RowKey>>,
222        root_key: i64,
223        available: Option<Arc<[bool]>>,
224        included: Option<Vec<bool>>,
225    ) -> Self {
226        let root = topology.index.get(&root_key).copied();
227        let roots = topology.roots_for(root_key, root);
228        let is_included = |index: usize| {
229            available.as_ref().is_none_or(|rows| rows[index])
230                && included.as_ref().is_none_or(|rows| rows[index])
231        };
232        let filtering = included.is_some();
233        let mut visible = Vec::new();
234        let mut pending: Vec<_> = roots
235            .iter()
236            .rev()
237            .copied()
238            .filter(|&index| is_included(index))
239            .map(|index| (index, 0))
240            .collect();
241        while let Some((index, depth)) = pending.pop() {
242            let node = &topology.entries[index];
243            let has_children = node.children.iter().copied().any(is_included);
244            let expanded =
245                has_children && (filtering || expanded.get(&node.key) == Some(&node.row));
246            visible.push(TreeItem {
247                key: node.key,
248                row: node.row,
249                model_index: node.model_index,
250                parent: node
251                    .parent
252                    .filter(|parent| Some(*parent) != root)
253                    .map(|index| topology.entries[index].key),
254                depth,
255                has_children,
256                expanded,
257            });
258            if expanded {
259                pending.extend(
260                    node.children
261                        .iter()
262                        .rev()
263                        .copied()
264                        .filter(|&index| is_included(index))
265                        .map(|index| (index, depth + 1)),
266                );
267            }
268        }
269        let visible_indices = visible
270            .iter()
271            .enumerate()
272            .map(|(index, item)| (item.key, index))
273            .collect();
274        Self {
275            topology,
276            expanded,
277            root_key,
278            root,
279            available,
280            filtering,
281            visible,
282            visible_indices,
283        }
284    }
285
286    pub fn rows(&self) -> &[TreeItem] {
287        &self.visible
288    }
289
290    pub fn visible_index(&self, key: i64) -> Option<usize> {
291        self.visible_indices.get(&key).copied()
292    }
293
294    pub fn visible_index_for_source(&self, source: usize) -> Option<usize> {
295        self.visible_index(self.entry_for_source(source)?.key)
296    }
297
298    fn entry_for_source(&self, source: usize) -> Option<&Entry> {
299        let index = self
300            .topology
301            .entries
302            .binary_search_by_key(&source, |entry| entry.model_index)
303            .ok()?;
304        self.topology.entries.get(index)
305    }
306
307    pub(crate) fn position_of_source_key(&self, key: RowKey, source_index: usize) -> Option<usize> {
308        if key.model != self.topology.model {
309            return None;
310        }
311        if let Some(entry) = self.entry_for_source(source_index)
312            && entry.row == key
313        {
314            return self.visible_index(entry.key);
315        }
316        self.visible.iter().position(|item| item.row == key)
317    }
318
319    pub fn root_key(&self) -> i64 {
320        self.root_key
321    }
322
323    #[doc(hidden)]
324    pub fn root_identity(&self) -> (i64, Option<RowKey>) {
325        (
326            self.root_key,
327            self.root.map(|index| self.topology.entries[index].row),
328        )
329    }
330
331    fn structural_index(&self, key: i64) -> Option<usize> {
332        let index = *self.topology.index.get(&key)?;
333        (self.root_key == -1
334            || self
335                .root
336                .is_some_and(|root| self.topology.contains_descendant(root, index)))
337        .then_some(index)
338    }
339
340    fn entry_index(&self, key: i64) -> Option<usize> {
341        self.structural_index(key)
342            .filter(|&index| self.is_available(index))
343    }
344
345    fn is_available(&self, index: usize) -> bool {
346        self.available.as_ref().is_none_or(|rows| rows[index])
347    }
348
349    fn has_available_children(&self, index: usize) -> bool {
350        self.topology.entries[index]
351            .children
352            .iter()
353            .any(|&child| self.is_available(child))
354    }
355
356    fn root_entries(&self) -> &[usize] {
357        self.topology.roots_for(self.root_key, self.root)
358    }
359
360    pub fn is_filtering(&self) -> bool {
361        self.filtering
362    }
363
364    pub fn is_expanded(&self, key: i64) -> bool {
365        if self.filtering {
366            return self
367                .visible_index(key)
368                .is_some_and(|index| self.visible[index].expanded);
369        }
370        self.entry_index(key).is_some_and(|index| {
371            let entry = &self.topology.entries[index];
372            self.has_available_children(index) && self.expanded.get(&key) == Some(&entry.row)
373        })
374    }
375
376    pub fn depth(&self, key: i64) -> Option<usize> {
377        let index = self.entry_index(key)?;
378        let base = self
379            .root
380            .map_or(0, |root| self.topology.entries[root].depth + 1);
381        Some(self.topology.entries[index].depth - base)
382    }
383
384    pub fn nearest_visible_ancestor(&self, key: i64) -> Option<i64> {
385        let mut index = self.structural_index(key)?;
386        loop {
387            let entry = &self.topology.entries[index];
388            if self.visible_index(entry.key).is_some() {
389                return Some(entry.key);
390            }
391            index = entry.parent.filter(|index| Some(*index) != self.root)?;
392        }
393    }
394
395    #[doc(hidden)]
396    pub fn same_model(&self, other: &Self) -> bool {
397        self.topology.model == other.topology.model
398    }
399
400    pub fn is_descendant(&self, key: i64, ancestor: i64) -> bool {
401        let Some(index) = self.entry_index(key) else {
402            return false;
403        };
404        let Some(ancestor) = self.entry_index(ancestor) else {
405            return false;
406        };
407        self.topology.contains_descendant(ancestor, index)
408    }
409}
410
411#[derive(Default)]
412struct Selection {
413    keys: Arc<BTreeMap<i64, RowKey>>,
414    anchor: Option<(i64, RowKey)>,
415}
416
417impl Selection {
418    fn retain_live(&mut self, topology: &Topology) {
419        let live = |key, row| topology.row_key(key) == Some(row);
420        if self.keys.iter().any(|(&key, &row)| !live(key, row)) {
421            Arc::make_mut(&mut self.keys).retain(|&key, row| live(key, *row));
422        }
423        self.anchor = self.anchor.filter(|&(key, row)| live(key, row));
424    }
425}
426
427struct FilterObservation {
428    topology: Weak<Topology>,
429    available: Option<Arc<[bool]>>,
430    root: i64,
431    query: Rc<str>,
432    changed: Rc<ChangeSignal>,
433}
434
435#[doc(hidden)]
436#[derive(Default)]
437pub struct TreeState {
438    topology: Property<Arc<Topology>>,
439    roles_changed: RefCell<Option<(u64, Rc<ChangeSignal>)>>,
440    visibility_changed: RefCell<Option<Rc<ChangeSignal>>>,
441    availability: Property<Arc<[bool]>>,
442    filter_observation: RefCell<Option<FilterObservation>>,
443    snapshot: Property<Arc<TreeSnapshot>>,
444    expanded: Property<Arc<BTreeMap<i64, RowKey>>>,
445    selection: RefCell<Selection>,
446    selection_changed: ChangeSignal,
447}
448
449impl TreeState {
450    /// Read topology from a stable, pure projection of a row's key and parent key.
451    pub fn snapshot<T>(
452        &self,
453        model: impl FnOnce() -> Rc<VecModel<T>>,
454        roles: impl Fn(&T) -> (i64, i64) + Clone + 'static,
455    ) -> Arc<TreeSnapshot> {
456        self.snapshot_with_root(model, roles, || -1)
457    }
458
459    pub fn snapshot_with_root<T>(
460        &self,
461        model: impl FnOnce() -> Rc<VecModel<T>>,
462        roles: impl Fn(&T) -> (i64, i64) + Clone + 'static,
463        root: impl FnOnce() -> i64,
464    ) -> Arc<TreeSnapshot> {
465        self.snapshot
466            .get(|| self.build_snapshot(self.topology(model, roles), root(), None, None))
467    }
468
469    pub fn snapshot_filtered<T: 'static>(
470        &self,
471        model: impl FnOnce() -> Rc<VecModel<T>>,
472        roles: impl Fn(&T) -> (i64, i64) + Clone + 'static,
473        root: impl FnOnce() -> i64,
474        query: impl FnOnce() -> String,
475        field: fn(&T) -> &str,
476    ) -> Arc<TreeSnapshot> {
477        self.snapshot_projected(model, roles, root, None, Some(field), query)
478    }
479
480    pub fn snapshot_projected<T: 'static>(
481        &self,
482        model: impl FnOnce() -> Rc<VecModel<T>>,
483        roles: impl Fn(&T) -> (i64, i64) + Clone + 'static,
484        root: impl FnOnce() -> i64,
485        visible: Option<fn(&T) -> bool>,
486        field: Option<fn(&T) -> &str>,
487        query: impl FnOnce() -> String,
488    ) -> Arc<TreeSnapshot> {
489        self.snapshot.get(|| {
490            let root = root();
491            let model = std::cell::LazyCell::new(model);
492            let topology = self.topology(|| Rc::clone(&model), roles.clone());
493            let available = visible.map(|visible| {
494                self.availability.get(|| {
495                    let topology = self.topology(|| Rc::clone(&model), roles);
496                    let mut shown = vec![false; topology.entries.len()];
497                    let mut pending = topology.roots.clone();
498                    while let Some(index) = pending.pop() {
499                        let entry = &topology.entries[index];
500                        if model
501                            .project_row_untracked(entry.model_index, visible)
502                            .unwrap_or(false)
503                        {
504                            shown[index] = true;
505                            pending.extend_from_slice(&entry.children);
506                        }
507                    }
508                    let shown: Arc<[bool]> = shown.into();
509                    let observed = Arc::downgrade(&topology);
510                    let reachable = shown.clone();
511                    let signal = model.observe_projection_changes(
512                        MAX_ROWS,
513                        move |model_index, before, after| {
514                            if visible(before) == visible(after) {
515                                return false;
516                            }
517                            let Some(topology) = observed.upgrade() else {
518                                return false;
519                            };
520                            topology
521                                .entries
522                                .binary_search_by_key(&model_index, |entry| entry.model_index)
523                                .is_ok_and(|index| {
524                                    topology.entries[index]
525                                        .parent
526                                        .is_none_or(|parent| reachable[parent])
527                                })
528                        },
529                    );
530                    signal.track();
531                    *self.visibility_changed.borrow_mut() = Some(signal);
532                    shown
533                })
534            });
535            let query: Rc<str> = field
536                .map_or_else(String::new, |_| query().trim().to_lowercase())
537                .into();
538            let Some(field) = field.filter(|_| !query.is_empty()) else {
539                self.filter_observation.borrow_mut().take();
540                return self.build_snapshot(topology, root, available, None);
541            };
542            let branch = topology.index.get(&root).copied();
543            let matches = |row: &T| field(row).to_lowercase().contains(query.as_ref());
544            {
545                let mut observation = self.filter_observation.borrow_mut();
546                let topology_ref = Arc::downgrade(&topology);
547                if observation.as_ref().is_none_or(|current| {
548                    !Weak::ptr_eq(&current.topology, &topology_ref)
549                        || match (&current.available, &available) {
550                            (Some(a), Some(b)) => !Arc::ptr_eq(a, b),
551                            (None, None) => false,
552                            _ => true,
553                        }
554                        || current.root != root
555                        || current.query != query
556                }) {
557                    let needle = query.clone();
558                    let observed = topology_ref.clone();
559                    let shown = available.clone();
560                    *observation = Some(FilterObservation {
561                        topology: topology_ref,
562                        available: available.clone(),
563                        root,
564                        query: query.clone(),
565                        changed: model.observe_projection_changes(
566                            MAX_ROWS,
567                            move |model_index, before, after| {
568                                let Some(topology) = observed.upgrade() else {
569                                    return false;
570                                };
571                                let Ok(index) = topology
572                                    .entries
573                                    .binary_search_by_key(&model_index, |entry| entry.model_index)
574                                else {
575                                    return false;
576                                };
577                                let in_scope = root == -1
578                                    || branch.is_some_and(|branch| {
579                                        topology.contains_descendant(branch, index)
580                                    });
581                                let matches =
582                                    |row: &T| field(row).to_lowercase().contains(needle.as_ref());
583                                in_scope
584                                    && shown.as_ref().is_none_or(|rows| rows[index])
585                                    && matches(before) != matches(after)
586                            },
587                        ),
588                    });
589                }
590                observation.as_ref().unwrap().changed.track();
591            }
592            let mut included = vec![false; topology.entries.len()];
593            let mut pending = topology.roots_for(root, branch).to_vec();
594            while let Some(index) = pending.pop() {
595                if available.as_ref().is_some_and(|rows| !rows[index]) {
596                    continue;
597                }
598                let entry = &topology.entries[index];
599                pending.extend_from_slice(&entry.children);
600                if !model
601                    .project_row_untracked(entry.model_index, matches)
602                    .unwrap_or(false)
603                {
604                    continue;
605                }
606                let mut ancestor = Some(index);
607                while let Some(index) = ancestor {
608                    if Some(index) == branch || included[index] {
609                        break;
610                    }
611                    included[index] = true;
612                    ancestor = topology.entries[index].parent;
613                }
614            }
615            self.build_snapshot(topology, root, available, Some(included))
616        })
617    }
618
619    fn topology<T>(
620        &self,
621        model: impl FnOnce() -> Rc<VecModel<T>>,
622        roles: impl Fn(&T) -> (i64, i64) + Clone + 'static,
623    ) -> Arc<Topology> {
624        self.topology.get(|| {
625            let model = model();
626            let model_id = model.structure_stamp().0;
627            {
628                let mut observation = self.roles_changed.borrow_mut();
629                if let Some((_, signal)) = observation.as_ref().filter(|(id, _)| *id == model_id) {
630                    signal.track();
631                } else {
632                    let signal = model.observe_projection(MAX_ROWS, roles.clone());
633                    signal.track();
634                    *observation = Some((model_id, signal));
635                }
636            }
637            let topology = Arc::new(Topology::new(&model, model_id, roles));
638            self.selection.borrow_mut().retain_live(&topology);
639            topology
640        })
641    }
642
643    fn build_snapshot(
644        &self,
645        topology: Arc<Topology>,
646        root: i64,
647        available: Option<Arc<[bool]>>,
648        included: Option<Vec<bool>>,
649    ) -> Arc<TreeSnapshot> {
650        Arc::new(TreeSnapshot::new(
651            topology,
652            self.expanded.get(|| Arc::new(BTreeMap::new())),
653            root,
654            available,
655            included,
656        ))
657    }
658
659    pub fn set_expanded(&self, tree: &TreeSnapshot, key: i64, row: RowKey, expanded: bool) -> bool {
660        if !tree
661            .visible_index(key)
662            .and_then(|index| tree.rows().get(index))
663            .is_some_and(|item| item.row == row && item.has_children && item.expanded != expanded)
664        {
665            return false;
666        }
667        let command = if expanded {
668            TreeCommand::Expand(key)
669        } else {
670            TreeCommand::Collapse(key)
671        };
672        self.command(tree, command).is_some()
673    }
674
675    pub fn command(
676        &self,
677        tree: &TreeSnapshot,
678        command: TreeCommand,
679    ) -> Option<TreeExpansionChange> {
680        if tree.is_filtering()
681            || !self
682                .topology
683                .matches_current(|current| Arc::ptr_eq(current, &tree.topology))
684            || tree.available.as_ref().is_some_and(|shown| {
685                !self
686                    .availability
687                    .matches_current(|current| Arc::ptr_eq(current, shown))
688            })
689        {
690            return None;
691        }
692        let topology = &tree.topology;
693        let mut state = self.expanded.get(|| Arc::new(BTreeMap::new()));
694        let expanded = Arc::make_mut(&mut state);
695        expanded.retain(|key, row| topology.row_key(*key) == Some(*row));
696        let (key, expand, pending, depth_limit) = match command {
697            TreeCommand::Expand(key)
698            | TreeCommand::Collapse(key)
699            | TreeCommand::ToggleExpanded(key) => {
700                let index = tree.entry_index(key)?;
701                let entry = &topology.entries[index];
702                let expand = match command {
703                    TreeCommand::ToggleExpanded(_) => expanded.get(&key) != Some(&entry.row),
704                    TreeCommand::Expand(_) => true,
705                    _ => false,
706                };
707                (key, expand, vec![index], Some(1_usize))
708            }
709            TreeCommand::ExpandRecursively { key, depth } => {
710                if depth < -1 || depth == 0 {
711                    return None;
712                }
713                let roots = if key == -1 {
714                    tree.root_entries().to_vec()
715                } else {
716                    vec![tree.entry_index(key)?]
717                };
718                (key, true, roots, usize::try_from(depth).ok())
719            }
720            TreeCommand::CollapseRecursively(key) => {
721                let roots = if key == -1 {
722                    tree.root_entries().to_vec()
723                } else {
724                    vec![tree.entry_index(key)?]
725                };
726                (key, false, roots, None)
727            }
728            TreeCommand::ExpandTo(key) => {
729                let mut index = tree.entry_index(key)?;
730                let mut ancestors = Vec::new();
731                while let Some(parent) = topology.entries[index]
732                    .parent
733                    .filter(|parent| Some(*parent) != tree.root)
734                {
735                    ancestors.push(parent);
736                    index = parent;
737                }
738                (key, true, ancestors, Some(1))
739            }
740        };
741        let mut pending: Vec<_> = pending.into_iter().map(|index| (index, 0_usize)).collect();
742        let mut changed = false;
743        while let Some((index, depth)) = pending.pop() {
744            let entry = &topology.entries[index];
745            if !tree.is_available(index) || !tree.has_available_children(index) {
746                continue;
747            }
748            if expand {
749                changed |= expanded.insert(entry.key, entry.row) != Some(entry.row);
750            } else {
751                changed |= expanded.remove(&entry.key).is_some();
752            }
753            if depth_limit.is_none_or(|limit| depth + 1 < limit) {
754                pending.extend(entry.children.iter().map(|&child| (child, depth + 1)));
755            }
756        }
757        if !changed {
758            return None;
759        }
760        self.expanded.set(state);
761        Some(TreeExpansionChange {
762            key,
763            expanded: expand,
764        })
765    }
766
767    pub fn selection(&self) -> Arc<BTreeMap<i64, RowKey>> {
768        self.selection_changed.track();
769        self.selection.borrow().keys.clone()
770    }
771
772    pub fn select(
773        &self,
774        tree: &TreeSnapshot,
775        current: i64,
776        action: TreeSelectionAction,
777    ) -> Option<TreeSelectionChange> {
778        let mut selection = self.selection.borrow_mut();
779        let mut next = selection.keys.clone();
780        let current = match action {
781            TreeSelectionAction::Row {
782                key,
783                row,
784                operation,
785            } => {
786                let index = tree.visible_index(key)?;
787                if tree.rows()[index].row != row {
788                    return None;
789                }
790                match operation {
791                    RowSelection::Replace => {
792                        next = Arc::new(BTreeMap::from([(key, row)]));
793                        selection.anchor = Some((key, row));
794                    }
795                    RowSelection::Toggle => {
796                        let selected = Arc::make_mut(&mut next);
797                        if selected.remove(&key).is_none() {
798                            selected.insert(key, row);
799                        }
800                        selection.anchor = Some((key, row));
801                    }
802                    RowSelection::Extend | RowSelection::AddRange => {
803                        let start = selection
804                            .anchor
805                            .and_then(|(key, _)| tree.visible_index(key))
806                            .or_else(|| tree.visible_index(current))
807                            .unwrap_or(index);
808                        let anchor = &tree.rows()[start];
809                        selection.anchor = Some((anchor.key, anchor.row));
810                        let rows = tree.rows()[start.min(index)..=start.max(index)]
811                            .iter()
812                            .map(|item| (item.key, item.row));
813                        if operation == RowSelection::Extend {
814                            next = Arc::new(rows.collect());
815                        } else {
816                            Arc::make_mut(&mut next).extend(rows);
817                        }
818                    }
819                    RowSelection::Move => {}
820                }
821                (key != current).then_some(key)
822            }
823            TreeSelectionAction::All => {
824                next = Arc::new(
825                    tree.rows()
826                        .iter()
827                        .map(|item| (item.key, item.row))
828                        .collect(),
829                );
830                selection.anchor = None;
831                None
832            }
833            TreeSelectionAction::Clear => {
834                next = Arc::new(BTreeMap::new());
835                selection.anchor = None;
836                None
837            }
838        };
839        let selected_count = (next != selection.keys).then_some(next.len());
840        if selected_count.is_some() {
841            selection.keys = next;
842            self.selection_changed.notify();
843        }
844        Some(TreeSelectionChange {
845            current,
846            selected_count,
847        })
848    }
849}
850
851#[cfg(test)]
852mod tests {
853    use super::*;
854    use std::cell::Cell;
855
856    #[test]
857    fn projection_handles_cycles_orphans_and_duplicates_without_rebuilding_on_expand() {
858        let model = Rc::new(VecModel::from(vec![
859            (9, 8),
860            (8, 9),
861            (10, 9),
862            (3, -1),
863            (3, -1),
864            (6, 3),
865            (7, 7),
866        ]));
867        let state = TreeState::default();
868        let reads = Rc::new(Cell::new(0));
869        let role_reads = reads.clone();
870        let roles = move |item: &(i64, i64)| {
871            role_reads.set(role_reads.get() + 1);
872            *item
873        };
874        let tree = state.snapshot(|| model.clone(), roles.clone());
875        assert_eq!(
876            tree.rows().iter().map(|row| row.key).collect::<Vec<_>>(),
877            [8, 6, 7]
878        );
879        assert!(tree.is_descendant(10, 8));
880        assert!(!tree.is_descendant(8, 9));
881        let root = tree.rows()[0];
882        assert!(state.set_expanded(&tree, root.key, root.row, true));
883        let expanded = state.snapshot(|| model.clone(), roles.clone());
884        assert_eq!(reads.get(), 7);
885        assert_eq!(
886            expanded
887                .rows()
888                .iter()
889                .map(|row| row.key)
890                .collect::<Vec<_>>(),
891            [8, 9, 6, 7]
892        );
893        assert!(model.set_row(2, (10, 6)));
894        assert_eq!(reads.get(), 9);
895        let reparented = state.snapshot(|| model.clone(), roles);
896        assert_eq!(reads.get(), 16);
897        assert!(!reparented.is_descendant(10, 8));
898        assert!(reparented.is_descendant(10, 6));
899        assert!(reparented.rows()[0].expanded);
900    }
901
902    #[test]
903    fn recursive_commands_clear_hidden_descendants_and_preserve_depth_limits() {
904        let model = Rc::new(VecModel::from(vec![
905            (1, -1),
906            (2, 1),
907            (3, 2),
908            (4, 1),
909            (9, -1),
910            (10, 9),
911        ]));
912        let state = TreeState::default();
913        let tree = || state.snapshot(|| model.clone(), |row| *row);
914        let initial = tree();
915        assert_eq!(initial.depth(3), Some(2));
916        assert_eq!(initial.depth(99), None);
917        assert!(
918            state
919                .command(
920                    &initial,
921                    TreeCommand::ExpandRecursively { key: 1, depth: 1 }
922                )
923                .is_some()
924        );
925        assert!(tree().is_expanded(1));
926        assert!(!tree().is_expanded(2));
927        assert_eq!(tree().visible_index(3), None);
928
929        assert!(state.command(&tree(), TreeCommand::ExpandTo(3)).is_some());
930        assert_eq!(tree().visible_index(3), Some(2));
931        assert!(state.command(&tree(), TreeCommand::Collapse(1)).is_some());
932        assert!(tree().is_expanded(2));
933        assert_eq!(tree().nearest_visible_ancestor(3), Some(1));
934        assert!(
935            state
936                .command(&tree(), TreeCommand::CollapseRecursively(1))
937                .is_some()
938        );
939        assert!(!tree().is_expanded(2));
940        assert!(state.command(&tree(), TreeCommand::Expand(1)).is_some());
941        assert_eq!(tree().visible_index(3), None);
942
943        let before = tree();
944        for command in [
945            TreeCommand::Expand(99),
946            TreeCommand::ExpandRecursively { key: 1, depth: 0 },
947            TreeCommand::ExpandRecursively { key: 1, depth: -2 },
948        ] {
949            assert!(state.command(&before, command).is_none());
950        }
951        assert!(Arc::ptr_eq(&before, &tree()));
952        assert!(state.command(&tree(), TreeCommand::ExpandTo(3)).is_some());
953        let prior_model = tree();
954        assert_eq!(model.remove(1), Some((2, 1)));
955        model.push((2, 1));
956        assert!(
957            state
958                .command(&prior_model, TreeCommand::CollapseRecursively(-1))
959                .is_none()
960        );
961        assert!(!tree().is_expanded(2));
962        assert_eq!(tree().visible_index(3), None);
963    }
964
965    #[test]
966    fn changing_the_view_root_reuses_topology_and_limits_expansion_to_the_branch() {
967        let model = Rc::new(VecModel::from(vec![
968            (1, -1),
969            (10, 1),
970            (100, 10),
971            (103, 100),
972            (2, -1),
973            (20, 2),
974        ]));
975        let state = TreeState::default();
976        let requested = Property::default();
977        let reads = Rc::new(Cell::new(0));
978        let count = reads.clone();
979        let roles = move |row: &(i64, i64)| {
980            count.set(count.get() + 1);
981            *row
982        };
983        let tree =
984            || state.snapshot_with_root(|| model.clone(), roles.clone(), || requested.get(|| -1));
985        assert!(
986            state
987                .command(
988                    &tree(),
989                    TreeCommand::ExpandRecursively { key: -1, depth: -1 }
990                )
991                .is_some()
992        );
993        let global = tree();
994        assert_eq!(global.rows().len(), 6);
995
996        requested.set(10);
997        let source = tree();
998        assert!(Arc::ptr_eq(&global.topology, &source.topology));
999        assert_eq!(
1000            source.rows().iter().map(|row| row.key).collect::<Vec<_>>(),
1001            [100, 103]
1002        );
1003        assert_eq!(source.rows()[0].parent, None);
1004        assert_eq!(source.depth(100), Some(0));
1005        assert_eq!(source.depth(103), Some(1));
1006        assert_eq!(source.depth(10), None);
1007        assert_eq!(source.depth(20), None);
1008        assert!(!source.is_descendant(103, 10));
1009        assert!(state.command(&source, TreeCommand::ExpandTo(20)).is_none());
1010        assert!(
1011            state
1012                .command(&source, TreeCommand::CollapseRecursively(-1))
1013                .is_some()
1014        );
1015
1016        requested.set(2);
1017        assert_eq!(tree().rows()[0].key, 20);
1018        assert_eq!(tree().rows()[0].depth, 0);
1019        requested.set(-1);
1020        let restored = tree();
1021        assert!(restored.is_expanded(1));
1022        assert!(restored.is_expanded(10));
1023        assert!(!restored.is_expanded(100));
1024        assert!(restored.is_expanded(2));
1025        assert_eq!(reads.get(), 6);
1026
1027        requested.set(999);
1028        let missing = tree();
1029        assert!(missing.rows().is_empty());
1030        assert!(
1031            state
1032                .command(&missing, TreeCommand::CollapseRecursively(-1))
1033                .is_none()
1034        );
1035        assert_eq!(missing.depth(100), None);
1036        assert_eq!(missing.root_key(), 999);
1037    }
1038
1039    #[test]
1040    fn filtering_uses_live_matches_and_preserves_the_saved_expansion() {
1041        type Row = (i64, i64, &'static str);
1042        let source = Property::default();
1043        let model = Rc::new(VecModel::from(vec![
1044            (1, -1, "project"),
1045            (2, 1, "src"),
1046            (3, 2, "Window.RS"),
1047            (4, 1, "notes"),
1048            (5, -1, "window outside"),
1049        ]));
1050        source.set(model.clone());
1051        let query = Property::default();
1052        query.set(" WINDOW ".to_owned());
1053        let state = TreeState::default();
1054        let read = || {
1055            state.snapshot_filtered(
1056                || source.get(|| unreachable!()),
1057                |row: &Row| (row.0, row.1),
1058                || 1,
1059                || query.get(String::new),
1060                |row| row.2,
1061            )
1062        };
1063        let filtered = read();
1064        assert!(filtered.is_filtering());
1065        assert_eq!(
1066            filtered
1067                .rows()
1068                .iter()
1069                .map(|row| row.key)
1070                .collect::<Vec<_>>(),
1071            [2, 3]
1072        );
1073        assert!(filtered.is_expanded(2));
1074        assert!(state.command(&filtered, TreeCommand::Collapse(2)).is_none());
1075        assert!(model.set_row(3, (4, 1, "README")));
1076        assert!(model.set_row(4, (5, -1, "outside rename")));
1077        assert!(Arc::ptr_eq(&filtered, &read()));
1078        assert!(model.set_row(3, (4, 1, "window docs")));
1079        assert_eq!(read().visible_index(4), Some(2));
1080
1081        query.set(String::new());
1082        let original = read();
1083        assert!(!original.is_filtering());
1084        assert!(!original.is_expanded(2));
1085        assert_eq!(original.visible_index(3), None);
1086
1087        query.set("window".to_owned());
1088        let before = read();
1089        source.set(Rc::new(VecModel::from(vec![
1090            (1, -1, "new project"),
1091            (9, 1, "window"),
1092        ])));
1093        let replaced = read();
1094        assert!(!before.same_model(&replaced));
1095        assert_eq!(replaced.rows()[0].key, 9);
1096        assert_eq!(replaced.rows().len(), 1);
1097    }
1098
1099    #[test]
1100    fn deep_ancestor_expansion_uses_the_topology_without_recursive_calls() {
1101        let model = Rc::new(VecModel::from(
1102            (0..4096).map(|key| (key, key - 1)).collect::<Vec<_>>(),
1103        ));
1104        let state = TreeState::default();
1105        let initial = state.snapshot(|| model.clone(), |row| *row);
1106        let topology = initial.topology.clone();
1107        assert!(
1108            state
1109                .command(&initial, TreeCommand::ExpandTo(4095))
1110                .is_some()
1111        );
1112        let expanded = state.snapshot(|| model.clone(), |row| *row);
1113        assert!(Arc::ptr_eq(&topology, &expanded.topology));
1114        assert_eq!(expanded.visible_index(4095), Some(4095));
1115        assert_eq!(expanded.depth(4095), Some(4095));
1116        assert!(
1117            state
1118                .command(&expanded, TreeCommand::CollapseRecursively(-1))
1119                .is_some()
1120        );
1121        let collapsed = state.snapshot(|| model.clone(), |row| *row);
1122        assert_eq!(collapsed.rows().len(), 1);
1123        assert!(!collapsed.is_expanded(4094));
1124    }
1125
1126    #[test]
1127    fn payload_changes_leave_independent_tree_projections_clean() {
1128        let model = Rc::new(VecModel::from(vec![(1, -1, -1, 0), (2, 1, -1, 0)]));
1129        let source = Property::default();
1130        source.set(model.clone());
1131        let primary = TreeState::default();
1132        let alternate = TreeState::default();
1133        let roles = |row: &(i64, i64, i64, i64)| (row.0, row.1);
1134        let other_roles = |row: &(i64, i64, i64, i64)| (row.0, row.2);
1135        let primary_tree = || primary.snapshot(|| source.get(|| unreachable!()), roles);
1136        let alternate_tree = || alternate.snapshot(|| model.clone(), other_roles);
1137        let first = primary_tree();
1138        let second = alternate_tree();
1139
1140        assert!(model.set_row(1, (2, 1, -1, 50)));
1141        assert!(Arc::ptr_eq(&first, &primary_tree()));
1142        assert!(Arc::ptr_eq(&second, &alternate_tree()));
1143        assert!(model.set_row(1, (2, 1, 1, 50)));
1144        assert!(Arc::ptr_eq(&first, &primary_tree()));
1145        let reparented = alternate_tree();
1146        assert!(!Arc::ptr_eq(&second, &reparented));
1147        assert!(reparented.is_descendant(2, 1));
1148
1149        source.set(Rc::new(VecModel::from(vec![(3, -1, -1, 0)])));
1150        let replacement = primary_tree();
1151        assert!(!replacement.same_model(&first));
1152        assert_eq!(replacement.rows()[0].key, 3);
1153        assert!(model.set_row(1, (2, -1, -1, 50)));
1154        assert!(Arc::ptr_eq(&replacement, &primary_tree()));
1155        assert!(!alternate_tree().is_descendant(2, 1));
1156        assert!(model.sort_by(|left, right| right.0.cmp(&left.0)));
1157        assert_eq!(alternate_tree().rows()[0].key, 2);
1158        assert!(Arc::ptr_eq(&replacement, &primary_tree()));
1159    }
1160
1161    #[test]
1162    fn visibility_masks_branches_without_rebuilding_topology_or_losing_expansion() {
1163        type Record = (i64, i64, bool, &'static str);
1164        let model = Rc::new(VecModel::from(vec![
1165            (1, -1, true, "root"),
1166            (2, 1, true, "branch"),
1167            (3, 2, true, "leaf"),
1168            (4, -1, true, "other"),
1169        ]));
1170        let root = Property::default();
1171        let query = Property::default();
1172        let state = TreeState::default();
1173        let snapshot = || {
1174            state.snapshot_projected(
1175                || model.clone(),
1176                |row| (row.0, row.1),
1177                || root.get(|| -1),
1178                Some(|row: &Record| row.2),
1179                Some(|row: &Record| row.3),
1180                || query.get(String::new),
1181            )
1182        };
1183        let keys =
1184            |tree: &TreeSnapshot| tree.rows().iter().map(|item| item.key).collect::<Vec<_>>();
1185        let first = snapshot();
1186        assert!(state.command(&first, TreeCommand::ExpandTo(3)).is_some());
1187        let expanded = snapshot();
1188        assert_eq!(keys(&expanded), [1, 2, 3, 4]);
1189        assert!(Arc::ptr_eq(
1190            first.available.as_ref().unwrap(),
1191            expanded.available.as_ref().unwrap()
1192        ));
1193        let leaf = model.row_key(2).unwrap();
1194        state
1195            .select(
1196                &expanded,
1197                -1,
1198                TreeSelectionAction::Row {
1199                    key: 3,
1200                    row: leaf,
1201                    operation: RowSelection::Replace,
1202                },
1203            )
1204            .unwrap();
1205
1206        model.set_row(1, (2, 1, false, "branch"));
1207        assert!(state.command(&expanded, TreeCommand::Collapse(2)).is_none());
1208        let hidden = snapshot();
1209        assert!(Arc::ptr_eq(&expanded.topology, &hidden.topology));
1210        assert_eq!(keys(&hidden), [1, 4]);
1211        assert_eq!(hidden.depth(3), None);
1212        assert_eq!(hidden.nearest_visible_ancestor(3), Some(1));
1213        assert!(!hidden.is_expanded(1));
1214        assert!(!hidden.is_filtering());
1215        assert!(
1216            state
1217                .command(&hidden, TreeCommand::CollapseRecursively(-1))
1218                .is_none()
1219        );
1220        assert_eq!(state.selection().get(&3), Some(&leaf));
1221        model.set_row(2, (3, 2, false, "leaf"));
1222        assert!(Arc::ptr_eq(&hidden, &snapshot()));
1223
1224        query.set("needle".into());
1225        let filtered = snapshot();
1226        assert!(filtered.rows().is_empty());
1227        model.set_row(2, (3, 2, true, "needle"));
1228        assert!(Arc::ptr_eq(&filtered, &snapshot()));
1229        model.set_row(1, (2, 1, true, "branch"));
1230        assert_eq!(keys(&snapshot()), [1, 2, 3]);
1231        query.set(String::new());
1232        assert_eq!(keys(&snapshot()), [1, 2, 3, 4]);
1233
1234        root.set(2);
1235        assert_eq!(keys(&snapshot()), [3]);
1236        model.set_row(0, (1, -1, false, "root"));
1237        assert!(snapshot().rows().is_empty());
1238        model.set_row(0, (1, -1, true, "root"));
1239        assert_eq!(keys(&snapshot()), [3]);
1240    }
1241}