Skip to main content

xrack_runtime/
tree.rs

1use crate::{
2    ChangeSignal, ControlAction, ListMetrics, Node, Property, RowKey, RowSelection,
3    TableSelectionAction, Value, VecModel, list::MAX_ROWS,
4};
5use std::{
6    cell::RefCell,
7    collections::{BTreeMap, HashMap, HashSet},
8    ops::Range,
9    rc::Rc,
10    sync::{Arc, Weak},
11};
12
13#[derive(Clone, Copy, Debug, PartialEq, Eq)]
14pub enum TreeAction {
15    SetExpanded {
16        key: i64,
17        row: RowKey,
18        expanded: bool,
19    },
20    Selection(TreeSelectionAction),
21}
22
23/// Commands address the model's stable non-negative business keys.
24#[derive(Clone, Copy, Debug, PartialEq, Eq)]
25pub enum TreeCommand {
26    Expand(i64),
27    Collapse(i64),
28    ToggleExpanded(i64),
29    ExpandRecursively { key: i64, depth: i64 },
30    CollapseRecursively(i64),
31    ExpandTo(i64),
32}
33
34#[derive(Clone, Copy, Debug, PartialEq, Eq)]
35#[doc(hidden)]
36pub enum TreeCommandMethod {
37    Expand,
38    Collapse,
39    ToggleExpanded,
40    ExpandRecursively,
41    CollapseRecursively,
42    ExpandTo,
43}
44
45impl TreeCommandMethod {
46    pub fn parse(name: &str) -> Option<Self> {
47        Some(match name {
48            "expand" => Self::Expand,
49            "collapse" => Self::Collapse,
50            "toggle-expanded" => Self::ToggleExpanded,
51            "expand-recursively" => Self::ExpandRecursively,
52            "collapse-recursively" => Self::CollapseRecursively,
53            "expand-to" => Self::ExpandTo,
54            _ => return None,
55        })
56    }
57
58    pub fn requires_depth(self) -> bool {
59        self == Self::ExpandRecursively
60    }
61
62    pub fn action(self, key: i64, depth: Option<i64>) -> Option<TreeCommand> {
63        Some(match self {
64            Self::Expand => TreeCommand::Expand(key),
65            Self::Collapse => TreeCommand::Collapse(key),
66            Self::ToggleExpanded => TreeCommand::ToggleExpanded(key),
67            Self::ExpandRecursively => TreeCommand::ExpandRecursively { key, depth: depth? },
68            Self::CollapseRecursively => TreeCommand::CollapseRecursively(key),
69            Self::ExpandTo => TreeCommand::ExpandTo(key),
70        })
71    }
72}
73
74#[doc(hidden)]
75pub struct TreeExpansionChange {
76    pub key: i64,
77    pub expanded: bool,
78}
79
80#[derive(Clone, Copy, Debug, PartialEq, Eq)]
81pub enum TreeSelectionAction {
82    Row {
83        key: i64,
84        row: RowKey,
85        operation: RowSelection,
86    },
87    All,
88    Clear,
89}
90
91#[derive(Clone, Copy)]
92#[doc(hidden)]
93pub enum TreeSelectionCommand {
94    Visual(TableSelectionAction),
95    Source(usize),
96    Key(i64),
97}
98
99#[derive(Clone, Copy)]
100#[doc(hidden)]
101pub enum TreeSelectionLookup {
102    Row(i64),
103    Key(i64),
104}
105
106#[doc(hidden)]
107pub struct TreeSelectionChange {
108    pub current: Option<i64>,
109    pub selected_count: Option<usize>,
110}
111
112#[doc(hidden)]
113pub enum TreeControlChange {
114    Selection(TreeSelectionChange),
115    Expansion {
116        change: TreeExpansionChange,
117        current: Option<i64>,
118    },
119}
120
121#[doc(hidden)]
122pub enum TreeControlEvent {
123    CurrentKeyChanged(i64),
124    SelectionChanged(usize),
125    Expanded(i64),
126    Collapsed(i64),
127}
128
129impl TreeControlChange {
130    /// Publish the cursor before handlers for selection and expansion read it.
131    pub fn try_notify<E>(
132        self,
133        mut notify: impl FnMut(TreeControlEvent) -> Result<(), E>,
134    ) -> Result<bool, E> {
135        let (current, event) = match self {
136            Self::Selection(change) => (
137                change.current,
138                change
139                    .selected_count
140                    .map(TreeControlEvent::SelectionChanged),
141            ),
142            Self::Expansion { change, current } => (
143                current,
144                Some(if change.expanded {
145                    TreeControlEvent::Expanded(change.key)
146                } else {
147                    TreeControlEvent::Collapsed(change.key)
148                }),
149            ),
150        };
151        if let Some(key) = current {
152            notify(TreeControlEvent::CurrentKeyChanged(key))?;
153        }
154        if let Some(event) = event {
155            notify(event)?;
156            return Ok(true);
157        }
158        Ok(current.is_some())
159    }
160
161    pub fn notify(self, mut notify: impl FnMut(TreeControlEvent)) -> bool {
162        self.try_notify(|event| {
163            notify(event);
164            Ok::<_, std::convert::Infallible>(())
165        })
166        .unwrap_or_else(|error| match error {})
167    }
168}
169
170#[derive(Clone, Copy, Debug, PartialEq, Eq)]
171pub struct TreeItem {
172    pub key: i64,
173    pub row: RowKey,
174    pub model_index: usize,
175    pub parent: Option<i64>,
176    pub depth: usize,
177    pub has_children: bool,
178    pub expanded: bool,
179}
180
181#[derive(Debug, PartialEq, Eq)]
182struct Entry {
183    key: i64,
184    row: RowKey,
185    model_index: usize,
186    parent: Option<usize>,
187    children: Vec<usize>,
188    depth: usize,
189    preorder: usize,
190    subtree_end: usize,
191}
192
193#[derive(Debug, PartialEq, Eq)]
194struct Topology {
195    model: u64,
196    entries: Vec<Entry>,
197    index: HashMap<i64, usize>,
198    roots: Vec<usize>,
199}
200
201impl Topology {
202    fn new<T>(model: &VecModel<T>, model_id: u64, roles: impl Fn(&T) -> (i64, i64)) -> Self {
203        let mut candidates = Vec::new();
204        let mut seen = HashSet::new();
205        let mut duplicates = HashSet::new();
206        model.visit_rows_untracked(MAX_ROWS, |index, row, item| {
207            let (key, parent) = roles(item);
208            if key < 0 {
209                return;
210            }
211            if !seen.insert(key) {
212                duplicates.insert(key);
213            }
214            candidates.push((index, row, key, parent));
215        });
216        candidates.retain(|(_, _, key, _)| !duplicates.contains(key));
217        let index: HashMap<_, _> = candidates
218            .iter()
219            .enumerate()
220            .map(|(index, (_, _, key, _))| (*key, index))
221            .collect();
222        let mut entries: Vec<_> = candidates
223            .into_iter()
224            .map(|(model_index, row, key, parent)| Entry {
225                key,
226                row,
227                model_index,
228                parent: index.get(&parent).copied(),
229                children: Vec::new(),
230                depth: 0,
231                preorder: 0,
232                subtree_end: 0,
233            })
234            .collect();
235
236        // Follow parent chains iteratively and break cycles at the smallest key.
237        let mut state = vec![0_u8; entries.len()];
238        let mut chain = Vec::new();
239        for start in 0..entries.len() {
240            let mut current = Some(start);
241            while let Some(node) = current {
242                if state[node] == 2 {
243                    break;
244                }
245                if state[node] == 1 {
246                    let cycle = chain
247                        .iter()
248                        .copied()
249                        .rev()
250                        .take_while(|&index| index != node);
251                    let root = cycle
252                        .chain(std::iter::once(node))
253                        .min_by_key(|&index| entries[index].key)
254                        .unwrap_or(node);
255                    entries[root].parent = None;
256                    break;
257                }
258                state[node] = 1;
259                chain.push(node);
260                current = entries[node].parent;
261            }
262            for node in chain.drain(..) {
263                state[node] = 2;
264            }
265        }
266        let mut roots = Vec::new();
267        for child in 0..entries.len() {
268            if let Some(parent) = entries[child].parent {
269                entries[parent].children.push(child);
270            } else {
271                roots.push(child);
272            }
273        }
274        let mut preorder = 0;
275        let mut pending: Vec<_> = roots.iter().rev().map(|&index| (index, false)).collect();
276        while let Some((index, exiting)) = pending.pop() {
277            if exiting {
278                entries[index].subtree_end = preorder;
279                continue;
280            }
281            entries[index].preorder = preorder;
282            entries[index].depth = entries[index]
283                .parent
284                .map_or(0, |parent| entries[parent].depth + 1);
285            preorder += 1;
286            pending.push((index, true));
287            pending.extend(
288                entries[index]
289                    .children
290                    .iter()
291                    .rev()
292                    .map(|&child| (child, false)),
293            );
294        }
295        Self {
296            model: model_id,
297            entries,
298            index,
299            roots,
300        }
301    }
302
303    fn contains_descendant(&self, root: usize, index: usize) -> bool {
304        let root = &self.entries[root];
305        let entry = &self.entries[index];
306        root.preorder < entry.preorder && entry.preorder < root.subtree_end
307    }
308
309    fn roots_for(&self, root_key: i64, root: Option<usize>) -> &[usize] {
310        if root_key == -1 {
311            &self.roots
312        } else {
313            root.map_or(&[], |index| self.entries[index].children.as_slice())
314        }
315    }
316
317    fn row_key(&self, key: i64) -> Option<RowKey> {
318        self.index.get(&key).map(|&index| self.entries[index].row)
319    }
320}
321
322/// The flattened navigation order. Row delegates are materialized separately by the viewport.
323#[derive(Debug, PartialEq, Eq)]
324pub struct TreeSnapshot {
325    topology: Arc<Topology>,
326    expanded: Arc<BTreeMap<i64, RowKey>>,
327    root_key: i64,
328    root: Option<usize>,
329    available: Option<Arc<[bool]>>,
330    filtering: bool,
331    visible: Vec<TreeItem>,
332    visible_indices: HashMap<i64, usize>,
333}
334
335impl TreeSnapshot {
336    /// Match the visible identities, source positions and tree presentation used for layout.
337    #[doc(hidden)]
338    pub fn matches_scene_order(&self, scene: Option<&Node>) -> bool {
339        scene.is_none_or(|node| {
340            node.tree.as_deref().is_some_and(|old| {
341                std::ptr::eq(self, old) || (self.same_model(old) && self.rows() == old.rows())
342            })
343        })
344    }
345
346    fn new(
347        topology: Arc<Topology>,
348        expanded: Arc<BTreeMap<i64, RowKey>>,
349        root_key: i64,
350        available: Option<Arc<[bool]>>,
351        included: Option<Vec<bool>>,
352    ) -> Self {
353        let root = topology.index.get(&root_key).copied();
354        let roots = topology.roots_for(root_key, root);
355        let is_included = |index: usize| {
356            available.as_ref().is_none_or(|rows| rows[index])
357                && included.as_ref().is_none_or(|rows| rows[index])
358        };
359        let filtering = included.is_some();
360        let mut visible = Vec::new();
361        let mut pending: Vec<_> = roots
362            .iter()
363            .rev()
364            .copied()
365            .filter(|&index| is_included(index))
366            .map(|index| (index, 0))
367            .collect();
368        while let Some((index, depth)) = pending.pop() {
369            let node = &topology.entries[index];
370            let has_children = node.children.iter().copied().any(is_included);
371            let expanded =
372                has_children && (filtering || expanded.get(&node.key) == Some(&node.row));
373            visible.push(TreeItem {
374                key: node.key,
375                row: node.row,
376                model_index: node.model_index,
377                parent: node
378                    .parent
379                    .filter(|parent| Some(*parent) != root)
380                    .map(|index| topology.entries[index].key),
381                depth,
382                has_children,
383                expanded,
384            });
385            if expanded {
386                pending.extend(
387                    node.children
388                        .iter()
389                        .rev()
390                        .copied()
391                        .filter(|&index| is_included(index))
392                        .map(|index| (index, depth + 1)),
393                );
394            }
395        }
396        let visible_indices = visible
397            .iter()
398            .enumerate()
399            .map(|(index, item)| (item.key, index))
400            .collect();
401        Self {
402            topology,
403            expanded,
404            root_key,
405            root,
406            available,
407            filtering,
408            visible,
409            visible_indices,
410        }
411    }
412
413    pub fn rows(&self) -> &[TreeItem] {
414        &self.visible
415    }
416
417    #[doc(hidden)]
418    pub fn rows_in_range(&self, range: Range<usize>) -> &[TreeItem] {
419        self.visible
420            .get(range.start..range.end.min(self.visible.len()))
421            .unwrap_or_default()
422    }
423
424    pub fn visible_index(&self, key: i64) -> Option<usize> {
425        self.visible_indices.get(&key).copied()
426    }
427
428    pub fn visible_index_for_source(&self, source: usize) -> Option<usize> {
429        self.visible_index(self.entry_for_source(source)?.key)
430    }
431
432    #[doc(hidden)]
433    pub fn view_index(&self, index: usize, direction: crate::ViewIndex) -> Option<usize> {
434        match direction {
435            crate::ViewIndex::FromSource => self.visible_index_for_source(index),
436            crate::ViewIndex::ToSource => self.rows().get(index).map(|row| row.model_index),
437        }
438    }
439
440    /// Resolve a rendered row only if it still appears in the live tree.
441    #[doc(hidden)]
442    pub fn event_source_index(&self, live: &Self, index: usize, row: RowKey) -> Option<usize> {
443        let item = self.rows().get(index).filter(|item| item.row == row)?;
444        let current = live.rows().get(live.visible_index(item.key)?)?;
445        (current.row == row && current.model_index == item.model_index).then_some(item.model_index)
446    }
447
448    fn entry_for_source(&self, source: usize) -> Option<&Entry> {
449        let index = self
450            .topology
451            .entries
452            .binary_search_by_key(&source, |entry| entry.model_index)
453            .ok()?;
454        self.topology.entries.get(index)
455    }
456
457    pub(crate) fn position_of_source_key(&self, key: RowKey, source_index: usize) -> Option<usize> {
458        if key.model != self.topology.model {
459            return None;
460        }
461        if let Some(entry) = self.entry_for_source(source_index)
462            && entry.row == key
463        {
464            return self.visible_index(entry.key);
465        }
466        self.visible.iter().position(|item| item.row == key)
467    }
468
469    pub fn root_key(&self) -> i64 {
470        self.root_key
471    }
472
473    #[doc(hidden)]
474    pub fn root_identity(&self) -> (i64, Option<RowKey>) {
475        (
476            self.root_key,
477            self.root.map(|index| self.topology.entries[index].row),
478        )
479    }
480
481    fn structural_index(&self, key: i64) -> Option<usize> {
482        let index = *self.topology.index.get(&key)?;
483        (self.root_key == -1
484            || self
485                .root
486                .is_some_and(|root| self.topology.contains_descendant(root, index)))
487        .then_some(index)
488    }
489
490    fn entry_index(&self, key: i64) -> Option<usize> {
491        self.structural_index(key)
492            .filter(|&index| self.is_available(index))
493    }
494
495    fn is_available(&self, index: usize) -> bool {
496        self.available.as_ref().is_none_or(|rows| rows[index])
497    }
498
499    fn has_available_children(&self, index: usize) -> bool {
500        self.topology.entries[index]
501            .children
502            .iter()
503            .any(|&child| self.is_available(child))
504    }
505
506    fn root_entries(&self) -> &[usize] {
507        self.topology.roots_for(self.root_key, self.root)
508    }
509
510    pub fn is_filtering(&self) -> bool {
511        self.filtering
512    }
513
514    pub fn is_expanded(&self, key: i64) -> bool {
515        if self.filtering {
516            return self
517                .visible_index(key)
518                .is_some_and(|index| self.visible[index].expanded);
519        }
520        self.entry_index(key).is_some_and(|index| {
521            let entry = &self.topology.entries[index];
522            self.has_available_children(index) && self.expanded.get(&key) == Some(&entry.row)
523        })
524    }
525
526    pub fn depth(&self, key: i64) -> Option<usize> {
527        let index = self.entry_index(key)?;
528        let base = self
529            .root
530            .map_or(0, |root| self.topology.entries[root].depth + 1);
531        Some(self.topology.entries[index].depth - base)
532    }
533
534    #[doc(hidden)]
535    pub fn query_depth(&self, key: i64) -> i64 {
536        self.depth(key).map_or(-1, |depth| depth as i64)
537    }
538
539    #[doc(hidden)]
540    pub fn query_row(&self, key: i64) -> i64 {
541        self.visible_index(key).map_or(-1, |index| index as i64)
542    }
543
544    pub fn nearest_visible_ancestor(&self, key: i64) -> Option<i64> {
545        let mut index = self.structural_index(key)?;
546        loop {
547            let entry = &self.topology.entries[index];
548            if self.visible_index(entry.key).is_some() {
549                return Some(entry.key);
550            }
551            index = entry.parent.filter(|index| Some(*index) != self.root)?;
552        }
553    }
554
555    fn nearest_visible_after_expansion(
556        &self,
557        key: i64,
558        expanded: &BTreeMap<i64, RowKey>,
559    ) -> Option<i64> {
560        let mut index = self.structural_index(key)?;
561        let mut path = vec![index];
562        while let Some(parent) = self.topology.entries[index]
563            .parent
564            .filter(|parent| Some(*parent) != self.root)
565        {
566            path.push(parent);
567            index = parent;
568        }
569        let mut visible = None;
570        for index in path.into_iter().rev() {
571            if !self.is_available(index) {
572                break;
573            }
574            let entry = &self.topology.entries[index];
575            visible = Some(entry.key);
576            if expanded.get(&entry.key) != Some(&entry.row) {
577                break;
578            }
579        }
580        visible
581    }
582
583    #[doc(hidden)]
584    pub fn same_model(&self, other: &Self) -> bool {
585        self.topology.model == other.topology.model
586    }
587
588    fn same_visible_rows(&self, other: &Self) -> bool {
589        let identity = |item: &TreeItem| (item.key, item.row);
590        std::ptr::eq(self, other)
591            || self
592                .rows()
593                .iter()
594                .map(identity)
595                .eq(other.rows().iter().map(identity))
596    }
597
598    pub fn is_descendant(&self, key: i64, ancestor: i64) -> bool {
599        let Some(index) = self.entry_index(key) else {
600            return false;
601        };
602        let Some(ancestor) = self.entry_index(ancestor) else {
603            return false;
604        };
605        self.topology.contains_descendant(ancestor, index)
606    }
607}
608
609#[derive(Default)]
610struct Selection {
611    keys: Arc<BTreeMap<i64, RowKey>>,
612    anchor: Option<(i64, RowKey)>,
613}
614
615impl Selection {
616    fn replace_keys(&mut self, keys: Arc<BTreeMap<i64, RowKey>>) -> Option<usize> {
617        if self.keys == keys {
618            return None;
619        }
620        let count = keys.len();
621        self.keys = keys;
622        Some(count)
623    }
624
625    fn retain_live(&mut self, topology: &Topology) {
626        let live = |key, row| topology.row_key(key) == Some(row);
627        if self.keys.iter().any(|(&key, &row)| !live(key, row)) {
628            Arc::make_mut(&mut self.keys).retain(|&key, row| live(key, *row));
629        }
630        self.anchor = self.anchor.filter(|&(key, row)| live(key, row));
631    }
632}
633
634struct FilterObservation {
635    topology: Weak<Topology>,
636    available: Option<Arc<[bool]>>,
637    root: i64,
638    query: Rc<str>,
639    changed: Rc<ChangeSignal>,
640}
641
642#[doc(hidden)]
643#[derive(Default)]
644pub struct TreeState {
645    source: Property<u64>,
646    topology: Property<Arc<Topology>>,
647    roles_changed: RefCell<Option<(u64, Rc<ChangeSignal>)>>,
648    visibility_changed: RefCell<Option<Rc<ChangeSignal>>>,
649    availability: Property<Arc<[bool]>>,
650    filter_observation: RefCell<Option<FilterObservation>>,
651    snapshot: Property<Arc<TreeSnapshot>>,
652    expanded: Property<Arc<BTreeMap<i64, RowKey>>>,
653    selection: RefCell<Selection>,
654    selection_changed: ChangeSignal,
655}
656
657impl TreeState {
658    /// Read topology from a stable, pure projection of a row's key and parent key.
659    pub fn snapshot<T>(
660        &self,
661        model: impl FnOnce() -> Rc<VecModel<T>>,
662        roles: impl Fn(&T) -> (i64, i64) + Clone + 'static,
663    ) -> Arc<TreeSnapshot> {
664        self.snapshot_with_root(model, roles, || -1)
665    }
666
667    pub fn snapshot_with_root<T>(
668        &self,
669        model: impl FnOnce() -> Rc<VecModel<T>>,
670        roles: impl Fn(&T) -> (i64, i64) + Clone + 'static,
671        root: impl FnOnce() -> i64,
672    ) -> Arc<TreeSnapshot> {
673        self.try_snapshot_with_root(model(), roles, || Ok::<_, std::convert::Infallible>(root()))
674            .unwrap_or_else(|error| match error {})
675    }
676
677    #[doc(hidden)]
678    pub fn try_snapshot_with_root<T, E>(
679        &self,
680        model: Rc<VecModel<T>>,
681        roles: impl Fn(&T) -> (i64, i64) + Clone + 'static,
682        root: impl FnOnce() -> Result<i64, E>,
683    ) -> Result<Arc<TreeSnapshot>, E> {
684        self.source.set_if_changed(model.edit_stamp().0);
685        self.snapshot.try_get(|| {
686            self.track_source();
687            let root = root()?;
688            Ok(self.build_snapshot(self.topology(&model, roles), root, None, None))
689        })
690    }
691
692    pub fn snapshot_filtered<T: 'static>(
693        &self,
694        model: impl FnOnce() -> Rc<VecModel<T>>,
695        roles: impl Fn(&T) -> (i64, i64) + Clone + 'static,
696        root: impl FnOnce() -> i64,
697        query: impl FnOnce() -> String,
698        field: fn(&T) -> &str,
699    ) -> Arc<TreeSnapshot> {
700        self.snapshot_projected(model, roles, root, None, Some(field), query)
701    }
702
703    pub fn snapshot_projected<T: 'static>(
704        &self,
705        model: impl FnOnce() -> Rc<VecModel<T>>,
706        roles: impl Fn(&T) -> (i64, i64) + Clone + 'static,
707        root: impl FnOnce() -> i64,
708        visible: Option<fn(&T) -> bool>,
709        field: Option<fn(&T) -> &str>,
710        query: impl FnOnce() -> String,
711    ) -> Arc<TreeSnapshot> {
712        self.snapshot_projected_by(model, roles, root, visible, field, query)
713    }
714
715    /// Project using field selectors that may capture immutable schema paths.
716    #[doc(hidden)]
717    pub fn snapshot_projected_by<T: 'static>(
718        &self,
719        model: impl FnOnce() -> Rc<VecModel<T>>,
720        roles: impl Fn(&T) -> (i64, i64) + Clone + 'static,
721        root: impl FnOnce() -> i64,
722        visible: Option<impl Fn(&T) -> bool + Clone + 'static>,
723        field: Option<impl Fn(&T) -> &str + Clone + 'static>,
724        query: impl FnOnce() -> String,
725    ) -> Arc<TreeSnapshot> {
726        self.try_snapshot_projected_by(
727            model(),
728            roles,
729            || Ok::<_, std::convert::Infallible>(root()),
730            visible,
731            field,
732            || Ok(query()),
733        )
734        .unwrap_or_else(|error| match error {})
735    }
736
737    /// Resolve fallible view bindings without caching a substitute projection.
738    #[doc(hidden)]
739    pub fn try_snapshot_projected_by<T: 'static, E>(
740        &self,
741        model: Rc<VecModel<T>>,
742        roles: impl Fn(&T) -> (i64, i64) + Clone + 'static,
743        root: impl FnOnce() -> Result<i64, E>,
744        visible: Option<impl Fn(&T) -> bool + Clone + 'static>,
745        field: Option<impl Fn(&T) -> &str + Clone + 'static>,
746        query: impl FnOnce() -> Result<String, E>,
747    ) -> Result<Arc<TreeSnapshot>, E> {
748        self.source.set_if_changed(model.edit_stamp().0);
749        self.snapshot.try_get(|| {
750            let root = root()?;
751            let query = Self::read_filter(field.is_some(), query)?;
752            Ok(self.project_snapshot(&model, roles, root, visible, field, query))
753        })
754    }
755
756    /// Resolve the row model after the view bindings and return it with its projection.
757    /// The model resolver must track changes to the source binding.
758    #[doc(hidden)]
759    pub fn try_project_model<T: 'static, M, E>(
760        &self,
761        resolve: impl Fn() -> Result<M, E>,
762        model: impl Fn(&M) -> &VecModel<T>,
763        roles: impl Fn(&T) -> (i64, i64) + Clone + 'static,
764        root: impl FnOnce() -> Result<i64, E>,
765        visible: Option<impl Fn(&T) -> bool + Clone + 'static>,
766        field: Option<impl Fn(&T) -> &str + Clone + 'static>,
767        query: impl FnOnce() -> Result<String, E>,
768    ) -> Result<(Arc<TreeSnapshot>, M), E> {
769        let mut source = None;
770        let snapshot = self.snapshot.try_get(|| {
771            let root = root()?;
772            let query = Self::read_filter(field.is_some(), query)?;
773            let resolved = resolve()?;
774            let rows = model(&resolved);
775            self.source.set_if_changed(rows.edit_stamp().0);
776            let snapshot = self.project_snapshot(rows, roles, root, visible, field, query);
777            source = Some(resolved);
778            Ok(snapshot)
779        })?;
780        Ok((snapshot, source.map_or_else(resolve, Ok)?))
781    }
782
783    #[doc(hidden)]
784    pub fn project_model<T: 'static>(
785        &self,
786        model: impl Fn() -> Rc<VecModel<T>>,
787        roles: impl Fn(&T) -> (i64, i64) + Clone + 'static,
788        root: impl FnOnce() -> i64,
789        visible: Option<fn(&T) -> bool>,
790        field: Option<fn(&T) -> &str>,
791        query: impl FnOnce() -> String,
792    ) -> (Arc<TreeSnapshot>, Rc<VecModel<T>>) {
793        self.try_project_model(
794            || Ok::<_, std::convert::Infallible>(model()),
795            |model| model.as_ref(),
796            roles,
797            || Ok(root()),
798            visible,
799            field,
800            || Ok(query()),
801        )
802        .unwrap_or_else(|error| match error {})
803    }
804
805    fn read_filter<E>(
806        has_field: bool,
807        query: impl FnOnce() -> Result<String, E>,
808    ) -> Result<Rc<str>, E> {
809        Ok(if has_field {
810            query()?.trim().to_lowercase().into()
811        } else {
812            Rc::from("")
813        })
814    }
815
816    fn project_snapshot<T: 'static>(
817        &self,
818        model: &VecModel<T>,
819        roles: impl Fn(&T) -> (i64, i64) + Clone + 'static,
820        root: i64,
821        visible: Option<impl Fn(&T) -> bool + Clone + 'static>,
822        field: Option<impl Fn(&T) -> &str + Clone + 'static>,
823        query: Rc<str>,
824    ) -> Arc<TreeSnapshot> {
825        self.track_source();
826        let topology = self.topology(model, roles.clone());
827        let available = visible.map(|visible| {
828            self.availability.get(|| {
829                let topology = self.topology(model, roles);
830                let mut shown = vec![false; topology.entries.len()];
831                let mut pending = topology.roots.clone();
832                while let Some(index) = pending.pop() {
833                    let entry = &topology.entries[index];
834                    if model
835                        .project_row_untracked(entry.model_index, &visible)
836                        .unwrap_or(false)
837                    {
838                        shown[index] = true;
839                        pending.extend_from_slice(&entry.children);
840                    }
841                }
842                let shown: Arc<[bool]> = shown.into();
843                let observed = Arc::downgrade(&topology);
844                let reachable = shown.clone();
845                let signal = model.observe_projection_changes(
846                    MAX_ROWS,
847                    move |model_index, before, after| {
848                        if visible(before) == visible(after) {
849                            return false;
850                        }
851                        let Some(topology) = observed.upgrade() else {
852                            return false;
853                        };
854                        topology
855                            .entries
856                            .binary_search_by_key(&model_index, |entry| entry.model_index)
857                            .is_ok_and(|index| {
858                                topology.entries[index]
859                                    .parent
860                                    .is_none_or(|parent| reachable[parent])
861                            })
862                    },
863                );
864                signal.track();
865                *self.visibility_changed.borrow_mut() = Some(signal);
866                shown
867            })
868        });
869        let Some(field) = field.filter(|_| !query.is_empty()) else {
870            self.filter_observation.borrow_mut().take();
871            return self.build_snapshot(topology, root, available, None);
872        };
873        let branch = topology.index.get(&root).copied();
874        let matches = |row: &T| field(row).to_lowercase().contains(query.as_ref());
875        {
876            let mut observation = self.filter_observation.borrow_mut();
877            let topology_ref = Arc::downgrade(&topology);
878            if observation.as_ref().is_none_or(|current| {
879                !Weak::ptr_eq(&current.topology, &topology_ref)
880                    || match (&current.available, &available) {
881                        (Some(a), Some(b)) => !Arc::ptr_eq(a, b),
882                        (None, None) => false,
883                        _ => true,
884                    }
885                    || current.root != root
886                    || current.query != query
887            }) {
888                let needle = query.clone();
889                let observed = topology_ref.clone();
890                let shown = available.clone();
891                let field = field.clone();
892                *observation = Some(FilterObservation {
893                    topology: topology_ref,
894                    available: available.clone(),
895                    root,
896                    query: query.clone(),
897                    changed: model.observe_projection_changes(
898                        MAX_ROWS,
899                        move |model_index, before, after| {
900                            let Some(topology) = observed.upgrade() else {
901                                return false;
902                            };
903                            let Ok(index) = topology
904                                .entries
905                                .binary_search_by_key(&model_index, |entry| entry.model_index)
906                            else {
907                                return false;
908                            };
909                            let in_scope = root == -1
910                                || branch.is_some_and(|branch| {
911                                    topology.contains_descendant(branch, index)
912                                });
913                            let matches =
914                                |row: &T| field(row).to_lowercase().contains(needle.as_ref());
915                            in_scope
916                                && shown.as_ref().is_none_or(|rows| rows[index])
917                                && matches(before) != matches(after)
918                        },
919                    ),
920                });
921            }
922            if let Some(observation) = observation.as_ref() {
923                observation.changed.track();
924            }
925        }
926        let mut included = vec![false; topology.entries.len()];
927        let mut pending = topology.roots_for(root, branch).to_vec();
928        while let Some(index) = pending.pop() {
929            if available.as_ref().is_some_and(|rows| !rows[index]) {
930                continue;
931            }
932            let entry = &topology.entries[index];
933            pending.extend_from_slice(&entry.children);
934            if !model
935                .project_row_untracked(entry.model_index, matches)
936                .unwrap_or(false)
937            {
938                continue;
939            }
940            let mut ancestor = Some(index);
941            while let Some(index) = ancestor {
942                if Some(index) == branch || included[index] {
943                    break;
944                }
945                included[index] = true;
946                ancestor = topology.entries[index].parent;
947            }
948        }
949        self.build_snapshot(topology, root, available, Some(included))
950    }
951
952    fn track_source(&self) {
953        self.source
954            .get(|| unreachable!("tree source is initialized"));
955    }
956
957    fn topology<T>(
958        &self,
959        model: &VecModel<T>,
960        roles: impl Fn(&T) -> (i64, i64) + Clone + 'static,
961    ) -> Arc<Topology> {
962        self.topology.get(|| {
963            self.track_source();
964            let model_id = model.structure_stamp().0;
965            {
966                let mut observation = self.roles_changed.borrow_mut();
967                if let Some((_, signal)) = observation.as_ref().filter(|(id, _)| *id == model_id) {
968                    signal.track();
969                } else {
970                    let signal = model.observe_projection(MAX_ROWS, roles.clone());
971                    signal.track();
972                    *observation = Some((model_id, signal));
973                }
974            }
975            let topology = Arc::new(Topology::new(model, model_id, roles));
976            self.selection.borrow_mut().retain_live(&topology);
977            topology
978        })
979    }
980
981    fn build_snapshot(
982        &self,
983        topology: Arc<Topology>,
984        root: i64,
985        available: Option<Arc<[bool]>>,
986        included: Option<Vec<bool>>,
987    ) -> Arc<TreeSnapshot> {
988        Arc::new(TreeSnapshot::new(
989            topology,
990            self.expanded.get(|| Arc::new(BTreeMap::new())),
991            root,
992            available,
993            included,
994        ))
995    }
996
997    pub fn set_expanded(&self, tree: &TreeSnapshot, key: i64, row: RowKey, expanded: bool) -> bool {
998        if !tree
999            .visible_index(key)
1000            .and_then(|index| tree.rows().get(index))
1001            .is_some_and(|item| item.row == row && item.has_children && item.expanded != expanded)
1002        {
1003            return false;
1004        }
1005        let command = if expanded {
1006            TreeCommand::Expand(key)
1007        } else {
1008            TreeCommand::Collapse(key)
1009        };
1010        self.command(tree, command).is_some()
1011    }
1012
1013    pub fn command(
1014        &self,
1015        tree: &TreeSnapshot,
1016        command: TreeCommand,
1017    ) -> Option<TreeExpansionChange> {
1018        let (expanded, change) = self.prepare_command(tree, command)?;
1019        self.expanded.set(expanded);
1020        Some(change)
1021    }
1022
1023    /// Resolve the command and cursor against the same live tree before committing.
1024    #[doc(hidden)]
1025    pub fn try_apply_command<E>(
1026        &self,
1027        command: TreeCommand,
1028        live: impl FnOnce() -> Result<Arc<TreeSnapshot>, E>,
1029        current: impl FnOnce() -> Result<i64, E>,
1030    ) -> Result<Option<(TreeExpansionChange, Option<i64>)>, E> {
1031        let prepared = crate::try_prepare_action_view(|| {
1032            let tree = live()?;
1033            let Some((expanded, change)) = self.prepare_command(&tree, command) else {
1034                return Ok(None);
1035            };
1036            let current = current()?;
1037            let next = tree
1038                .nearest_visible_after_expansion(current, &expanded)
1039                .filter(|key| *key != current);
1040            Ok(Some((expanded, change, next)))
1041        })?;
1042        Ok(prepared.map(|(expanded, change, next)| {
1043            self.expanded.set(expanded);
1044            (change, next)
1045        }))
1046    }
1047
1048    #[doc(hidden)]
1049    pub fn apply_command(
1050        &self,
1051        command: TreeCommand,
1052        live: impl FnOnce() -> Arc<TreeSnapshot>,
1053        current: impl FnOnce() -> i64,
1054    ) -> Option<(TreeExpansionChange, Option<i64>)> {
1055        self.try_apply_command(
1056            command,
1057            || Ok::<_, std::convert::Infallible>(live()),
1058            || Ok(current()),
1059        )
1060        .unwrap_or_else(|error| match error {})
1061    }
1062
1063    fn prepare_command(
1064        &self,
1065        tree: &TreeSnapshot,
1066        command: TreeCommand,
1067    ) -> Option<(Arc<BTreeMap<i64, RowKey>>, TreeExpansionChange)> {
1068        if tree.is_filtering()
1069            || !self
1070                .topology
1071                .matches_current(|current| Arc::ptr_eq(current, &tree.topology))
1072            || tree.available.as_ref().is_some_and(|shown| {
1073                !self
1074                    .availability
1075                    .matches_current(|current| Arc::ptr_eq(current, shown))
1076            })
1077        {
1078            return None;
1079        }
1080        let topology = &tree.topology;
1081        let mut state = self.expanded.get(|| Arc::new(BTreeMap::new()));
1082        let expanded = Arc::make_mut(&mut state);
1083        expanded.retain(|key, row| topology.row_key(*key) == Some(*row));
1084        let (key, expand, pending, depth_limit) = match command {
1085            TreeCommand::Expand(key)
1086            | TreeCommand::Collapse(key)
1087            | TreeCommand::ToggleExpanded(key) => {
1088                let index = tree.entry_index(key)?;
1089                let entry = &topology.entries[index];
1090                let expand = match command {
1091                    TreeCommand::ToggleExpanded(_) => expanded.get(&key) != Some(&entry.row),
1092                    TreeCommand::Expand(_) => true,
1093                    _ => false,
1094                };
1095                (key, expand, vec![index], Some(1_usize))
1096            }
1097            TreeCommand::ExpandRecursively { key, depth } => {
1098                if depth < -1 || depth == 0 {
1099                    return None;
1100                }
1101                let roots = if key == -1 {
1102                    tree.root_entries().to_vec()
1103                } else {
1104                    vec![tree.entry_index(key)?]
1105                };
1106                (key, true, roots, usize::try_from(depth).ok())
1107            }
1108            TreeCommand::CollapseRecursively(key) => {
1109                let roots = if key == -1 {
1110                    tree.root_entries().to_vec()
1111                } else {
1112                    vec![tree.entry_index(key)?]
1113                };
1114                (key, false, roots, None)
1115            }
1116            TreeCommand::ExpandTo(key) => {
1117                let mut index = tree.entry_index(key)?;
1118                let mut ancestors = Vec::new();
1119                while let Some(parent) = topology.entries[index]
1120                    .parent
1121                    .filter(|parent| Some(*parent) != tree.root)
1122                {
1123                    ancestors.push(parent);
1124                    index = parent;
1125                }
1126                (key, true, ancestors, Some(1))
1127            }
1128        };
1129        let mut pending: Vec<_> = pending.into_iter().map(|index| (index, 0_usize)).collect();
1130        let mut changed = false;
1131        while let Some((index, depth)) = pending.pop() {
1132            let entry = &topology.entries[index];
1133            if !tree.is_available(index) || !tree.has_available_children(index) {
1134                continue;
1135            }
1136            if expand {
1137                changed |= expanded.insert(entry.key, entry.row) != Some(entry.row);
1138            } else {
1139                changed |= expanded.remove(&entry.key).is_some();
1140            }
1141            if depth_limit.is_none_or(|limit| depth + 1 < limit) {
1142                pending.extend(entry.children.iter().map(|&child| (child, depth + 1)));
1143            }
1144        }
1145        if !changed {
1146            return None;
1147        }
1148        Some((
1149            state,
1150            TreeExpansionChange {
1151                key,
1152                expanded: expand,
1153            },
1154        ))
1155    }
1156
1157    pub fn selection(&self) -> Arc<BTreeMap<i64, RowKey>> {
1158        self.selection_changed.track();
1159        self.selection.borrow().keys.clone()
1160    }
1161
1162    #[doc(hidden)]
1163    pub fn selected_keys(&self, tree: &TreeSnapshot, single_current: Option<i64>) -> Vec<i64> {
1164        if let Some(current) = single_current {
1165            return tree
1166                .visible_index(current)
1167                .map(|_| current)
1168                .into_iter()
1169                .collect();
1170        }
1171        self.selection_changed.track();
1172        self.selection.borrow().keys.keys().copied().collect()
1173    }
1174
1175    /// Replace the full selection by business key, leaving cursor and expansion alone.
1176    #[doc(hidden)]
1177    pub fn try_replace_selection<E>(
1178        &self,
1179        keys: &[i64],
1180        live: impl FnOnce() -> Result<Arc<TreeSnapshot>, E>,
1181        multiple: impl FnOnce() -> Result<bool, E>,
1182    ) -> Result<Option<TreeSelectionChange>, E> {
1183        let keys = crate::try_prepare_action_view(|| {
1184            if !multiple()? {
1185                return Ok(None);
1186            }
1187            let tree = live()?;
1188            Ok(keys
1189                .iter()
1190                .map(|&key| tree.topology.row_key(key).map(|row| (key, row)))
1191                .collect::<Option<BTreeMap<_, _>>>())
1192        })?;
1193        let Some(keys) = keys else {
1194            return Ok(None);
1195        };
1196        let selected_count = {
1197            let mut selection = self.selection.borrow_mut();
1198            selection.anchor = None;
1199            selection.replace_keys(Arc::new(keys))
1200        };
1201        if selected_count.is_some() {
1202            self.selection_changed.notify();
1203        }
1204        Ok(Some(TreeSelectionChange {
1205            current: None,
1206            selected_count,
1207        }))
1208    }
1209
1210    #[doc(hidden)]
1211    pub fn replace_selection(
1212        &self,
1213        keys: &[i64],
1214        live: impl FnOnce() -> Arc<TreeSnapshot>,
1215        multiple: impl FnOnce() -> bool,
1216    ) -> Option<TreeSelectionChange> {
1217        self.try_replace_selection(
1218            keys,
1219            || Ok::<_, std::convert::Infallible>(live()),
1220            || Ok(multiple()),
1221        )
1222        .unwrap_or_else(|error| match error {})
1223    }
1224
1225    #[doc(hidden)]
1226    pub fn selection_info(
1227        &self,
1228        tree: &TreeSnapshot,
1229        multiple: bool,
1230        current: i64,
1231        query: Option<TreeSelectionLookup>,
1232    ) -> (i64, bool) {
1233        let key = match query {
1234            Some(TreeSelectionLookup::Row(index)) => usize::try_from(index)
1235                .ok()
1236                .and_then(|index| tree.rows().get(index))
1237                .map(|item| item.key),
1238            Some(TreeSelectionLookup::Key(key)) => Some(key),
1239            None => None,
1240        };
1241        if multiple {
1242            self.selection_changed.track();
1243            let selection = self.selection.borrow();
1244            (
1245                selection.keys.len() as i64,
1246                key.is_some_and(|key| selection.keys.contains_key(&key)),
1247            )
1248        } else {
1249            let current = tree.visible_index(current).map(|_| current);
1250            (
1251                i64::from(current.is_some()),
1252                key.is_some() && key == current,
1253            )
1254        }
1255    }
1256
1257    /// Publish the same visible rows for layout, painting and input routing.
1258    #[doc(hidden)]
1259    pub fn populate_scene(&self, node: &mut Node, tree: Arc<TreeSnapshot>) {
1260        node.list = Some(ListMetrics {
1261            row_count: tree.rows().len(),
1262            first_row: 0,
1263        });
1264        node.properties
1265            .entry("current-key")
1266            .or_insert(Value::Int(-1));
1267        node.tree_selection = node
1268            .boolean("multi-select", false)
1269            .then(|| self.selection());
1270        node.tree = Some(tree);
1271    }
1272
1273    /// Resolve a scene's positional input to stable rows before changing tree state.
1274    #[doc(hidden)]
1275    pub fn try_apply_control<E>(
1276        &self,
1277        node: &Node,
1278        input: crate::InputRoute<'_>,
1279        available: impl FnOnce() -> Result<bool, E>,
1280        multiple: impl FnOnce() -> Result<bool, E>,
1281        live: impl FnOnce() -> Result<Arc<TreeSnapshot>, E>,
1282        current: impl FnOnce() -> Result<i64, E>,
1283    ) -> Result<Option<TreeControlChange>, E> {
1284        let crate::RoutedEvent::Control(action) = *input.event() else {
1285            return Ok(None);
1286        };
1287        let Some(snapshot) = &node.tree else {
1288            return Ok(None);
1289        };
1290        let snapshot_multiple = node.tree_selection.is_some();
1291        let action = match action {
1292            ControlAction::Select(index) => {
1293                let Some(item) = snapshot.rows().get(index) else {
1294                    return Ok(None);
1295                };
1296                TreeAction::Selection(TreeSelectionAction::Row {
1297                    key: item.key,
1298                    row: item.row,
1299                    operation: RowSelection::Replace,
1300                })
1301            }
1302            ControlAction::Tree(action @ TreeAction::SetExpanded { .. }) => action,
1303            ControlAction::Tree(action @ TreeAction::Selection(_)) if snapshot_multiple => action,
1304            _ => return Ok(None),
1305        };
1306        let prepared = crate::property::watch_reads(|reads| {
1307            if !available()? || reads.changed() {
1308                return Ok(None);
1309            }
1310            if matches!(action, TreeAction::Selection(_))
1311                && (multiple()? != snapshot_multiple || reads.changed())
1312            {
1313                return Ok(None);
1314            }
1315            let live = live()?;
1316            if reads.changed() {
1317                return Ok(None);
1318            }
1319            if let TreeAction::Selection(selection) = action
1320                && snapshot_multiple
1321            {
1322                let needs_order = matches!(
1323                    selection,
1324                    TreeSelectionAction::Row {
1325                        operation: RowSelection::Extend | RowSelection::AddRange,
1326                        ..
1327                    }
1328                );
1329                if !snapshot.same_model(&live)
1330                    || (needs_order && !snapshot.same_visible_rows(&live))
1331                {
1332                    return Ok(None);
1333                }
1334            }
1335            let current = current()?;
1336            Ok((input.is_current() && !reads.changed()).then_some((live, current)))
1337        })?;
1338        let Some((live, current)) = prepared else {
1339            return Ok(None);
1340        };
1341        Ok(match action {
1342            TreeAction::Selection(selection) => self
1343                .select_in_mode(&live, current, snapshot_multiple, selection)
1344                .map(TreeControlChange::Selection),
1345            TreeAction::SetExpanded { key, row, expanded } => self
1346                .set_expanded(&live, key, row, expanded)
1347                .then(|| TreeControlChange::Expansion {
1348                    change: TreeExpansionChange { key, expanded },
1349                    current: (!expanded && live.is_descendant(current, key)).then_some(key),
1350                }),
1351        })
1352    }
1353
1354    #[doc(hidden)]
1355    pub fn apply_control(
1356        &self,
1357        node: &Node,
1358        input: crate::InputRoute<'_>,
1359        available: impl FnOnce() -> bool,
1360        multiple: impl FnOnce() -> bool,
1361        live: impl FnOnce() -> Arc<TreeSnapshot>,
1362        current: impl FnOnce() -> i64,
1363    ) -> Option<TreeControlChange> {
1364        self.try_apply_control(
1365            node,
1366            input,
1367            || Ok::<_, std::convert::Infallible>(available()),
1368            || Ok(multiple()),
1369            || Ok(live()),
1370            || Ok(current()),
1371        )
1372        .unwrap_or_else(|error| match error {})
1373    }
1374
1375    /// Resolve a programmatic selection against the current tree projection.
1376    #[doc(hidden)]
1377    pub fn try_apply_selection<E>(
1378        &self,
1379        command: TreeSelectionCommand,
1380        live: impl FnOnce() -> Result<Arc<TreeSnapshot>, E>,
1381        multiple: impl FnOnce() -> Result<bool, E>,
1382        current: impl FnOnce() -> Result<i64, E>,
1383    ) -> Result<Option<TreeSelectionChange>, E> {
1384        let prepared = crate::try_prepare_action_view(|| {
1385            let tree = live()?;
1386            let row = |index: usize, operation| {
1387                tree.rows().get(index).map(|item| TreeSelectionAction::Row {
1388                    key: item.key,
1389                    row: item.row,
1390                    operation,
1391                })
1392            };
1393            let replace = |index| row(index, RowSelection::Replace);
1394            let action = match command {
1395                TreeSelectionCommand::Source(source) => {
1396                    tree.visible_index_for_source(source).and_then(replace)
1397                }
1398                TreeSelectionCommand::Key(key) => tree.visible_index(key).and_then(replace),
1399                TreeSelectionCommand::Visual(TableSelectionAction::Row { index, operation }) => {
1400                    row(index, operation)
1401                }
1402                TreeSelectionCommand::Visual(TableSelectionAction::All) => {
1403                    Some(TreeSelectionAction::All)
1404                }
1405                TreeSelectionCommand::Visual(TableSelectionAction::Clear) => {
1406                    Some(TreeSelectionAction::Clear)
1407                }
1408                TreeSelectionCommand::Visual(_) => None,
1409            };
1410            let Some(action) = action else {
1411                return Ok(None);
1412            };
1413            let multiple = multiple()?;
1414            if !multiple
1415                && !matches!(
1416                    action,
1417                    TreeSelectionAction::Row {
1418                        operation: RowSelection::Replace,
1419                        ..
1420                    }
1421                )
1422            {
1423                return Ok(None);
1424            }
1425            let current = current()?;
1426            Ok(Some((tree, multiple, current, action)))
1427        })?;
1428        Ok(prepared.and_then(|(tree, multiple, current, action)| {
1429            self.select_in_mode(&tree, current, multiple, action)
1430        }))
1431    }
1432
1433    #[doc(hidden)]
1434    pub fn apply_selection(
1435        &self,
1436        command: TreeSelectionCommand,
1437        live: impl FnOnce() -> Arc<TreeSnapshot>,
1438        multiple: impl FnOnce() -> bool,
1439        current: impl FnOnce() -> i64,
1440    ) -> Option<TreeSelectionChange> {
1441        self.try_apply_selection(
1442            command,
1443            || Ok::<_, std::convert::Infallible>(live()),
1444            || Ok(multiple()),
1445            || Ok(current()),
1446        )
1447        .unwrap_or_else(|error| match error {})
1448    }
1449
1450    #[doc(hidden)]
1451    pub fn try_select_source<E>(
1452        &self,
1453        source: usize,
1454        live: impl FnOnce() -> Result<Arc<TreeSnapshot>, E>,
1455        multiple: impl FnOnce() -> Result<bool, E>,
1456        current: impl FnOnce() -> Result<i64, E>,
1457    ) -> Result<Option<TreeSelectionChange>, E> {
1458        self.try_apply_selection(
1459            TreeSelectionCommand::Source(source),
1460            live,
1461            multiple,
1462            current,
1463        )
1464    }
1465
1466    #[doc(hidden)]
1467    pub fn select_source(
1468        &self,
1469        source: usize,
1470        live: impl FnOnce() -> Arc<TreeSnapshot>,
1471        multiple: impl FnOnce() -> bool,
1472        current: impl FnOnce() -> i64,
1473    ) -> Option<TreeSelectionChange> {
1474        self.apply_selection(
1475            TreeSelectionCommand::Source(source),
1476            live,
1477            multiple,
1478            current,
1479        )
1480    }
1481
1482    #[doc(hidden)]
1483    pub fn select_in_mode(
1484        &self,
1485        tree: &TreeSnapshot,
1486        current: i64,
1487        multiple: bool,
1488        action: TreeSelectionAction,
1489    ) -> Option<TreeSelectionChange> {
1490        if !self
1491            .snapshot
1492            .matches_current(|live| std::ptr::eq(live.as_ref(), tree))
1493        {
1494            return None;
1495        }
1496        if multiple {
1497            return self.select(tree, current, action);
1498        }
1499        let TreeSelectionAction::Row { key, row, .. } = action else {
1500            return None;
1501        };
1502        let item = tree.rows().get(tree.visible_index(key)?)?;
1503        (item.row == row && key != current).then_some(TreeSelectionChange {
1504            current: Some(key),
1505            selected_count: None,
1506        })
1507    }
1508
1509    pub fn select(
1510        &self,
1511        tree: &TreeSnapshot,
1512        current: i64,
1513        action: TreeSelectionAction,
1514    ) -> Option<TreeSelectionChange> {
1515        let mut selection = self.selection.borrow_mut();
1516        let mut next = selection.keys.clone();
1517        let current = match action {
1518            TreeSelectionAction::Row {
1519                key,
1520                row,
1521                operation,
1522            } => {
1523                let index = tree.visible_index(key)?;
1524                if tree.rows()[index].row != row {
1525                    return None;
1526                }
1527                match operation {
1528                    RowSelection::Replace => {
1529                        next = Arc::new(BTreeMap::from([(key, row)]));
1530                        selection.anchor = Some((key, row));
1531                    }
1532                    RowSelection::Toggle => {
1533                        let selected = Arc::make_mut(&mut next);
1534                        if selected.remove(&key).is_none() {
1535                            selected.insert(key, row);
1536                        }
1537                        selection.anchor = Some((key, row));
1538                    }
1539                    RowSelection::Extend | RowSelection::AddRange => {
1540                        let start = selection
1541                            .anchor
1542                            .and_then(|(key, _)| tree.visible_index(key))
1543                            .or_else(|| tree.visible_index(current))
1544                            .unwrap_or(index);
1545                        let anchor = &tree.rows()[start];
1546                        selection.anchor = Some((anchor.key, anchor.row));
1547                        let rows = tree.rows()[start.min(index)..=start.max(index)]
1548                            .iter()
1549                            .map(|item| (item.key, item.row));
1550                        if operation == RowSelection::Extend {
1551                            next = Arc::new(rows.collect());
1552                        } else {
1553                            Arc::make_mut(&mut next).extend(rows);
1554                        }
1555                    }
1556                    RowSelection::Move => {}
1557                }
1558                (key != current).then_some(key)
1559            }
1560            TreeSelectionAction::All => {
1561                next = Arc::new(
1562                    tree.rows()
1563                        .iter()
1564                        .map(|item| (item.key, item.row))
1565                        .collect(),
1566                );
1567                selection.anchor = None;
1568                None
1569            }
1570            TreeSelectionAction::Clear => {
1571                next = Arc::new(BTreeMap::new());
1572                selection.anchor = None;
1573                None
1574            }
1575        };
1576        let selected_count = selection.replace_keys(next);
1577        drop(selection);
1578        if selected_count.is_some() {
1579            self.selection_changed.notify();
1580        }
1581        Some(TreeSelectionChange {
1582            current,
1583            selected_count,
1584        })
1585    }
1586}
1587
1588#[cfg(test)]
1589mod tests {
1590    use super::*;
1591    use std::cell::Cell;
1592
1593    #[test]
1594    fn projection_handles_cycles_orphans_and_duplicates_without_rebuilding_on_expand() {
1595        let model = Rc::new(VecModel::from(vec![
1596            (9, 8),
1597            (8, 9),
1598            (10, 9),
1599            (3, -1),
1600            (3, -1),
1601            (6, 3),
1602            (7, 7),
1603        ]));
1604        let state = TreeState::default();
1605        let reads = Rc::new(Cell::new(0));
1606        let role_reads = reads.clone();
1607        let roles = move |item: &(i64, i64)| {
1608            role_reads.set(role_reads.get() + 1);
1609            *item
1610        };
1611        let tree = state.snapshot(|| model.clone(), roles.clone());
1612        assert_eq!(
1613            tree.rows().iter().map(|row| row.key).collect::<Vec<_>>(),
1614            [8, 6, 7]
1615        );
1616        assert!(tree.is_descendant(10, 8));
1617        assert!(!tree.is_descendant(8, 9));
1618        let root = tree.rows()[0];
1619        assert!(state.set_expanded(&tree, root.key, root.row, true));
1620        let expanded = state.snapshot(|| model.clone(), roles.clone());
1621        assert_eq!(reads.get(), 7);
1622        assert_eq!(
1623            expanded
1624                .rows()
1625                .iter()
1626                .map(|row| row.key)
1627                .collect::<Vec<_>>(),
1628            [8, 9, 6, 7]
1629        );
1630        assert!(model.set_row(2, (10, 6)));
1631        assert_eq!(reads.get(), 9);
1632        let reparented = state.snapshot(|| model.clone(), roles);
1633        assert_eq!(reads.get(), 16);
1634        assert!(!reparented.is_descendant(10, 8));
1635        assert!(reparented.is_descendant(10, 6));
1636        assert!(reparented.rows()[0].expanded);
1637    }
1638
1639    #[test]
1640    fn recursive_commands_clear_hidden_descendants_and_preserve_depth_limits() {
1641        let model = Rc::new(VecModel::from(vec![
1642            (1, -1),
1643            (2, 1),
1644            (3, 2),
1645            (4, 1),
1646            (9, -1),
1647            (10, 9),
1648        ]));
1649        let state = TreeState::default();
1650        let tree = || state.snapshot(|| model.clone(), |row| *row);
1651        let initial = tree();
1652        assert_eq!(initial.depth(3), Some(2));
1653        assert_eq!(initial.depth(99), None);
1654        assert!(
1655            state
1656                .command(
1657                    &initial,
1658                    TreeCommand::ExpandRecursively { key: 1, depth: 1 }
1659                )
1660                .is_some()
1661        );
1662        assert!(tree().is_expanded(1));
1663        assert!(!tree().is_expanded(2));
1664        assert_eq!(tree().visible_index(3), None);
1665
1666        assert!(state.command(&tree(), TreeCommand::ExpandTo(3)).is_some());
1667        assert_eq!(tree().visible_index(3), Some(2));
1668        assert!(state.command(&tree(), TreeCommand::Collapse(1)).is_some());
1669        assert!(tree().is_expanded(2));
1670        assert_eq!(tree().nearest_visible_ancestor(3), Some(1));
1671        assert!(
1672            state
1673                .command(&tree(), TreeCommand::CollapseRecursively(1))
1674                .is_some()
1675        );
1676        assert!(!tree().is_expanded(2));
1677        assert!(state.command(&tree(), TreeCommand::Expand(1)).is_some());
1678        assert_eq!(tree().visible_index(3), None);
1679
1680        let before = tree();
1681        for command in [
1682            TreeCommand::Expand(99),
1683            TreeCommand::ExpandRecursively { key: 1, depth: 0 },
1684            TreeCommand::ExpandRecursively { key: 1, depth: -2 },
1685        ] {
1686            assert!(state.command(&before, command).is_none());
1687        }
1688        assert!(Arc::ptr_eq(&before, &tree()));
1689        assert!(state.command(&tree(), TreeCommand::ExpandTo(3)).is_some());
1690        let prior_model = tree();
1691        assert_eq!(model.remove(1), Some((2, 1)));
1692        model.push((2, 1));
1693        assert!(
1694            state
1695                .command(&prior_model, TreeCommand::CollapseRecursively(-1))
1696                .is_none()
1697        );
1698        assert!(!tree().is_expanded(2));
1699        assert_eq!(tree().visible_index(3), None);
1700    }
1701
1702    #[test]
1703    fn changing_the_view_root_reuses_topology_and_limits_expansion_to_the_branch() {
1704        let model = Rc::new(VecModel::from(vec![
1705            (1, -1),
1706            (10, 1),
1707            (100, 10),
1708            (103, 100),
1709            (2, -1),
1710            (20, 2),
1711        ]));
1712        let state = TreeState::default();
1713        let requested = Property::default();
1714        let reads = Rc::new(Cell::new(0));
1715        let count = reads.clone();
1716        let roles = move |row: &(i64, i64)| {
1717            count.set(count.get() + 1);
1718            *row
1719        };
1720        let tree =
1721            || state.snapshot_with_root(|| model.clone(), roles.clone(), || requested.get(|| -1));
1722        assert!(
1723            state
1724                .command(
1725                    &tree(),
1726                    TreeCommand::ExpandRecursively { key: -1, depth: -1 }
1727                )
1728                .is_some()
1729        );
1730        let global = tree();
1731        assert_eq!(global.rows().len(), 6);
1732
1733        requested.set(10);
1734        let source = tree();
1735        assert!(Arc::ptr_eq(&global.topology, &source.topology));
1736        assert_eq!(
1737            source.rows().iter().map(|row| row.key).collect::<Vec<_>>(),
1738            [100, 103]
1739        );
1740        assert_eq!(source.rows()[0].parent, None);
1741        assert_eq!(source.depth(100), Some(0));
1742        assert_eq!(source.depth(103), Some(1));
1743        assert_eq!(source.depth(10), None);
1744        assert_eq!(source.depth(20), None);
1745        assert!(!source.is_descendant(103, 10));
1746        assert!(state.command(&source, TreeCommand::ExpandTo(20)).is_none());
1747        assert!(
1748            state
1749                .command(&source, TreeCommand::CollapseRecursively(-1))
1750                .is_some()
1751        );
1752
1753        requested.set(2);
1754        assert_eq!(tree().rows()[0].key, 20);
1755        assert_eq!(tree().rows()[0].depth, 0);
1756        requested.set(-1);
1757        let restored = tree();
1758        assert!(restored.is_expanded(1));
1759        assert!(restored.is_expanded(10));
1760        assert!(!restored.is_expanded(100));
1761        assert!(restored.is_expanded(2));
1762        assert_eq!(reads.get(), 6);
1763
1764        requested.set(999);
1765        let missing = tree();
1766        assert!(missing.rows().is_empty());
1767        assert!(
1768            state
1769                .command(&missing, TreeCommand::CollapseRecursively(-1))
1770                .is_none()
1771        );
1772        assert_eq!(missing.depth(100), None);
1773        assert_eq!(missing.root_key(), 999);
1774    }
1775
1776    #[test]
1777    fn filtering_uses_live_matches_and_preserves_the_saved_expansion() {
1778        type Row = (i64, i64, &'static str);
1779        let source = Property::default();
1780        let model = Rc::new(VecModel::from(vec![
1781            (1, -1, "project"),
1782            (2, 1, "src"),
1783            (3, 2, "Window.RS"),
1784            (4, 1, "notes"),
1785            (5, -1, "window outside"),
1786        ]));
1787        source.set(model.clone());
1788        let query = Property::default();
1789        query.set(" WINDOW ".to_owned());
1790        let state = TreeState::default();
1791        let read = || {
1792            state.snapshot_filtered(
1793                || source.get(|| unreachable!()),
1794                |row: &Row| (row.0, row.1),
1795                || 1,
1796                || query.get(String::new),
1797                |row| row.2,
1798            )
1799        };
1800        let filtered = read();
1801        assert!(filtered.is_filtering());
1802        assert_eq!(
1803            filtered
1804                .rows()
1805                .iter()
1806                .map(|row| row.key)
1807                .collect::<Vec<_>>(),
1808            [2, 3]
1809        );
1810        assert!(filtered.is_expanded(2));
1811        assert!(state.command(&filtered, TreeCommand::Collapse(2)).is_none());
1812        assert!(model.set_row(3, (4, 1, "README")));
1813        assert!(model.set_row(4, (5, -1, "outside rename")));
1814        assert!(Arc::ptr_eq(&filtered, &read()));
1815        assert!(model.set_row(3, (4, 1, "window docs")));
1816        assert_eq!(read().visible_index(4), Some(2));
1817
1818        query.set(String::new());
1819        let original = read();
1820        assert!(!original.is_filtering());
1821        assert!(!original.is_expanded(2));
1822        assert_eq!(original.visible_index(3), None);
1823
1824        query.set("window".to_owned());
1825        let before = read();
1826        source.set(Rc::new(VecModel::from(vec![
1827            (1, -1, "new project"),
1828            (9, 1, "window"),
1829        ])));
1830        let replaced = read();
1831        assert!(!before.same_model(&replaced));
1832        assert_eq!(replaced.rows()[0].key, 9);
1833        assert_eq!(replaced.rows().len(), 1);
1834    }
1835
1836    #[test]
1837    fn filtering_projects_the_model_after_reading_the_query() {
1838        let model = Rc::new(VecModel::from(vec![(1, -1, "one"), (2, 1, "two")]));
1839        let state = TreeState::default();
1840        let tree = state.snapshot_filtered(
1841            || model.clone(),
1842            |row| (row.0, row.1),
1843            || -1,
1844            || {
1845                assert_eq!(model.remove(0), Some((1, -1, "one")));
1846                "two".to_owned()
1847            },
1848            |row| row.2,
1849        );
1850        assert_eq!(tree.rows().len(), 1);
1851        assert_eq!((tree.rows()[0].key, tree.rows()[0].model_index), (2, 0));
1852    }
1853
1854    #[test]
1855    fn deep_ancestor_expansion_uses_the_topology_without_recursive_calls() {
1856        let model = Rc::new(VecModel::from(
1857            (0..4096).map(|key| (key, key - 1)).collect::<Vec<_>>(),
1858        ));
1859        let state = TreeState::default();
1860        let initial = state.snapshot(|| model.clone(), |row| *row);
1861        let topology = initial.topology.clone();
1862        assert!(
1863            state
1864                .command(&initial, TreeCommand::ExpandTo(4095))
1865                .is_some()
1866        );
1867        let expanded = state.snapshot(|| model.clone(), |row| *row);
1868        assert!(Arc::ptr_eq(&topology, &expanded.topology));
1869        assert_eq!(expanded.visible_index(4095), Some(4095));
1870        assert_eq!(expanded.depth(4095), Some(4095));
1871        assert!(
1872            state
1873                .command(&expanded, TreeCommand::CollapseRecursively(-1))
1874                .is_some()
1875        );
1876        let collapsed = state.snapshot(|| model.clone(), |row| *row);
1877        assert_eq!(collapsed.rows().len(), 1);
1878        assert!(!collapsed.is_expanded(4094));
1879    }
1880
1881    #[test]
1882    fn payload_changes_leave_independent_tree_projections_clean() {
1883        let model = Rc::new(VecModel::from(vec![(1, -1, -1, 0), (2, 1, -1, 0)]));
1884        let source = Property::default();
1885        source.set(model.clone());
1886        let primary = TreeState::default();
1887        let alternate = TreeState::default();
1888        let roles = |row: &(i64, i64, i64, i64)| (row.0, row.1);
1889        let other_roles = |row: &(i64, i64, i64, i64)| (row.0, row.2);
1890        let primary_tree = || primary.snapshot(|| source.get(|| unreachable!()), roles);
1891        let alternate_tree = || alternate.snapshot(|| model.clone(), other_roles);
1892        let first = primary_tree();
1893        let second = alternate_tree();
1894
1895        assert!(model.set_row(1, (2, 1, -1, 50)));
1896        assert!(Arc::ptr_eq(&first, &primary_tree()));
1897        assert!(Arc::ptr_eq(&second, &alternate_tree()));
1898        assert!(model.set_row(1, (2, 1, 1, 50)));
1899        assert!(Arc::ptr_eq(&first, &primary_tree()));
1900        let reparented = alternate_tree();
1901        assert!(!Arc::ptr_eq(&second, &reparented));
1902        assert!(reparented.is_descendant(2, 1));
1903
1904        source.set(Rc::new(VecModel::from(vec![(3, -1, -1, 0)])));
1905        let replacement = primary_tree();
1906        assert!(!replacement.same_model(&first));
1907        assert_eq!(replacement.rows()[0].key, 3);
1908        assert!(model.set_row(1, (2, -1, -1, 50)));
1909        assert!(Arc::ptr_eq(&replacement, &primary_tree()));
1910        assert!(!alternate_tree().is_descendant(2, 1));
1911        assert!(model.sort_by(|left, right| right.0.cmp(&left.0)));
1912        assert_eq!(alternate_tree().rows()[0].key, 2);
1913        assert!(Arc::ptr_eq(&replacement, &primary_tree()));
1914    }
1915
1916    #[test]
1917    fn visibility_masks_branches_without_rebuilding_topology_or_losing_expansion() {
1918        type Record = (i64, i64, bool, &'static str);
1919        let model = Rc::new(VecModel::from(vec![
1920            (1, -1, true, "root"),
1921            (2, 1, true, "branch"),
1922            (3, 2, true, "leaf"),
1923            (4, -1, true, "other"),
1924        ]));
1925        let root = Property::default();
1926        let query = Property::default();
1927        let state = TreeState::default();
1928        let snapshot = || {
1929            state.snapshot_projected(
1930                || model.clone(),
1931                |row| (row.0, row.1),
1932                || root.get(|| -1),
1933                Some(|row: &Record| row.2),
1934                Some(|row: &Record| row.3),
1935                || query.get(String::new),
1936            )
1937        };
1938        let keys =
1939            |tree: &TreeSnapshot| tree.rows().iter().map(|item| item.key).collect::<Vec<_>>();
1940        let first = snapshot();
1941        assert!(state.command(&first, TreeCommand::ExpandTo(3)).is_some());
1942        let expanded = snapshot();
1943        assert_eq!(keys(&expanded), [1, 2, 3, 4]);
1944        assert!(Arc::ptr_eq(
1945            first.available.as_ref().unwrap(),
1946            expanded.available.as_ref().unwrap()
1947        ));
1948        let leaf = model.row_key(2).unwrap();
1949        state
1950            .select(
1951                &expanded,
1952                -1,
1953                TreeSelectionAction::Row {
1954                    key: 3,
1955                    row: leaf,
1956                    operation: RowSelection::Replace,
1957                },
1958            )
1959            .unwrap();
1960
1961        model.set_row(1, (2, 1, false, "branch"));
1962        assert!(state.command(&expanded, TreeCommand::Collapse(2)).is_none());
1963        let hidden = snapshot();
1964        assert!(Arc::ptr_eq(&expanded.topology, &hidden.topology));
1965        assert_eq!(keys(&hidden), [1, 4]);
1966        assert_eq!(hidden.depth(3), None);
1967        assert_eq!(hidden.nearest_visible_ancestor(3), Some(1));
1968        assert!(!hidden.is_expanded(1));
1969        assert!(!hidden.is_filtering());
1970        assert!(
1971            state
1972                .command(&hidden, TreeCommand::CollapseRecursively(-1))
1973                .is_none()
1974        );
1975        assert_eq!(state.selection().get(&3), Some(&leaf));
1976        model.set_row(2, (3, 2, false, "leaf"));
1977        assert!(Arc::ptr_eq(&hidden, &snapshot()));
1978
1979        query.set("needle".into());
1980        let filtered = snapshot();
1981        assert!(filtered.rows().is_empty());
1982        model.set_row(2, (3, 2, true, "needle"));
1983        assert!(Arc::ptr_eq(&filtered, &snapshot()));
1984        model.set_row(1, (2, 1, true, "branch"));
1985        assert_eq!(keys(&snapshot()), [1, 2, 3]);
1986        query.set(String::new());
1987        assert_eq!(keys(&snapshot()), [1, 2, 3, 4]);
1988
1989        root.set(2);
1990        assert_eq!(keys(&snapshot()), [3]);
1991        model.set_row(0, (1, -1, false, "root"));
1992        assert!(snapshot().rows().is_empty());
1993        model.set_row(0, (1, -1, true, "root"));
1994        assert_eq!(keys(&snapshot()), [3]);
1995    }
1996}