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();
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            observation.as_ref().unwrap().changed.track();
923        }
924        let mut included = vec![false; topology.entries.len()];
925        let mut pending = topology.roots_for(root, branch).to_vec();
926        while let Some(index) = pending.pop() {
927            if available.as_ref().is_some_and(|rows| !rows[index]) {
928                continue;
929            }
930            let entry = &topology.entries[index];
931            pending.extend_from_slice(&entry.children);
932            if !model
933                .project_row_untracked(entry.model_index, matches)
934                .unwrap_or(false)
935            {
936                continue;
937            }
938            let mut ancestor = Some(index);
939            while let Some(index) = ancestor {
940                if Some(index) == branch || included[index] {
941                    break;
942                }
943                included[index] = true;
944                ancestor = topology.entries[index].parent;
945            }
946        }
947        self.build_snapshot(topology, root, available, Some(included))
948    }
949
950    fn track_source(&self) {
951        self.source
952            .get(|| unreachable!("tree source is initialized"));
953    }
954
955    fn topology<T>(
956        &self,
957        model: &VecModel<T>,
958        roles: impl Fn(&T) -> (i64, i64) + Clone + 'static,
959    ) -> Arc<Topology> {
960        self.topology.get(|| {
961            self.track_source();
962            let model_id = model.structure_stamp().0;
963            {
964                let mut observation = self.roles_changed.borrow_mut();
965                if let Some((_, signal)) = observation.as_ref().filter(|(id, _)| *id == model_id) {
966                    signal.track();
967                } else {
968                    let signal = model.observe_projection(MAX_ROWS, roles.clone());
969                    signal.track();
970                    *observation = Some((model_id, signal));
971                }
972            }
973            let topology = Arc::new(Topology::new(model, model_id, roles));
974            self.selection.borrow_mut().retain_live(&topology);
975            topology
976        })
977    }
978
979    fn build_snapshot(
980        &self,
981        topology: Arc<Topology>,
982        root: i64,
983        available: Option<Arc<[bool]>>,
984        included: Option<Vec<bool>>,
985    ) -> Arc<TreeSnapshot> {
986        Arc::new(TreeSnapshot::new(
987            topology,
988            self.expanded.get(|| Arc::new(BTreeMap::new())),
989            root,
990            available,
991            included,
992        ))
993    }
994
995    pub fn set_expanded(&self, tree: &TreeSnapshot, key: i64, row: RowKey, expanded: bool) -> bool {
996        if !tree
997            .visible_index(key)
998            .and_then(|index| tree.rows().get(index))
999            .is_some_and(|item| item.row == row && item.has_children && item.expanded != expanded)
1000        {
1001            return false;
1002        }
1003        let command = if expanded {
1004            TreeCommand::Expand(key)
1005        } else {
1006            TreeCommand::Collapse(key)
1007        };
1008        self.command(tree, command).is_some()
1009    }
1010
1011    pub fn command(
1012        &self,
1013        tree: &TreeSnapshot,
1014        command: TreeCommand,
1015    ) -> Option<TreeExpansionChange> {
1016        let (expanded, change) = self.prepare_command(tree, command)?;
1017        self.expanded.set(expanded);
1018        Some(change)
1019    }
1020
1021    /// Resolve the command and cursor against the same live tree before committing.
1022    #[doc(hidden)]
1023    pub fn try_apply_command<E>(
1024        &self,
1025        command: TreeCommand,
1026        live: impl FnOnce() -> Result<Arc<TreeSnapshot>, E>,
1027        current: impl FnOnce() -> Result<i64, E>,
1028    ) -> Result<Option<(TreeExpansionChange, Option<i64>)>, E> {
1029        let prepared = crate::try_prepare_action_view(|| {
1030            let tree = live()?;
1031            let Some((expanded, change)) = self.prepare_command(&tree, command) else {
1032                return Ok(None);
1033            };
1034            let current = current()?;
1035            let next = tree
1036                .nearest_visible_after_expansion(current, &expanded)
1037                .filter(|key| *key != current);
1038            Ok(Some((expanded, change, next)))
1039        })?;
1040        Ok(prepared.map(|(expanded, change, next)| {
1041            self.expanded.set(expanded);
1042            (change, next)
1043        }))
1044    }
1045
1046    #[doc(hidden)]
1047    pub fn apply_command(
1048        &self,
1049        command: TreeCommand,
1050        live: impl FnOnce() -> Arc<TreeSnapshot>,
1051        current: impl FnOnce() -> i64,
1052    ) -> Option<(TreeExpansionChange, Option<i64>)> {
1053        self.try_apply_command(
1054            command,
1055            || Ok::<_, std::convert::Infallible>(live()),
1056            || Ok(current()),
1057        )
1058        .unwrap_or_else(|error| match error {})
1059    }
1060
1061    fn prepare_command(
1062        &self,
1063        tree: &TreeSnapshot,
1064        command: TreeCommand,
1065    ) -> Option<(Arc<BTreeMap<i64, RowKey>>, TreeExpansionChange)> {
1066        if tree.is_filtering()
1067            || !self
1068                .topology
1069                .matches_current(|current| Arc::ptr_eq(current, &tree.topology))
1070            || tree.available.as_ref().is_some_and(|shown| {
1071                !self
1072                    .availability
1073                    .matches_current(|current| Arc::ptr_eq(current, shown))
1074            })
1075        {
1076            return None;
1077        }
1078        let topology = &tree.topology;
1079        let mut state = self.expanded.get(|| Arc::new(BTreeMap::new()));
1080        let expanded = Arc::make_mut(&mut state);
1081        expanded.retain(|key, row| topology.row_key(*key) == Some(*row));
1082        let (key, expand, pending, depth_limit) = match command {
1083            TreeCommand::Expand(key)
1084            | TreeCommand::Collapse(key)
1085            | TreeCommand::ToggleExpanded(key) => {
1086                let index = tree.entry_index(key)?;
1087                let entry = &topology.entries[index];
1088                let expand = match command {
1089                    TreeCommand::ToggleExpanded(_) => expanded.get(&key) != Some(&entry.row),
1090                    TreeCommand::Expand(_) => true,
1091                    _ => false,
1092                };
1093                (key, expand, vec![index], Some(1_usize))
1094            }
1095            TreeCommand::ExpandRecursively { key, depth } => {
1096                if depth < -1 || depth == 0 {
1097                    return None;
1098                }
1099                let roots = if key == -1 {
1100                    tree.root_entries().to_vec()
1101                } else {
1102                    vec![tree.entry_index(key)?]
1103                };
1104                (key, true, roots, usize::try_from(depth).ok())
1105            }
1106            TreeCommand::CollapseRecursively(key) => {
1107                let roots = if key == -1 {
1108                    tree.root_entries().to_vec()
1109                } else {
1110                    vec![tree.entry_index(key)?]
1111                };
1112                (key, false, roots, None)
1113            }
1114            TreeCommand::ExpandTo(key) => {
1115                let mut index = tree.entry_index(key)?;
1116                let mut ancestors = Vec::new();
1117                while let Some(parent) = topology.entries[index]
1118                    .parent
1119                    .filter(|parent| Some(*parent) != tree.root)
1120                {
1121                    ancestors.push(parent);
1122                    index = parent;
1123                }
1124                (key, true, ancestors, Some(1))
1125            }
1126        };
1127        let mut pending: Vec<_> = pending.into_iter().map(|index| (index, 0_usize)).collect();
1128        let mut changed = false;
1129        while let Some((index, depth)) = pending.pop() {
1130            let entry = &topology.entries[index];
1131            if !tree.is_available(index) || !tree.has_available_children(index) {
1132                continue;
1133            }
1134            if expand {
1135                changed |= expanded.insert(entry.key, entry.row) != Some(entry.row);
1136            } else {
1137                changed |= expanded.remove(&entry.key).is_some();
1138            }
1139            if depth_limit.is_none_or(|limit| depth + 1 < limit) {
1140                pending.extend(entry.children.iter().map(|&child| (child, depth + 1)));
1141            }
1142        }
1143        if !changed {
1144            return None;
1145        }
1146        Some((
1147            state,
1148            TreeExpansionChange {
1149                key,
1150                expanded: expand,
1151            },
1152        ))
1153    }
1154
1155    pub fn selection(&self) -> Arc<BTreeMap<i64, RowKey>> {
1156        self.selection_changed.track();
1157        self.selection.borrow().keys.clone()
1158    }
1159
1160    #[doc(hidden)]
1161    pub fn selected_keys(&self, tree: &TreeSnapshot, single_current: Option<i64>) -> Vec<i64> {
1162        if let Some(current) = single_current {
1163            return tree
1164                .visible_index(current)
1165                .map(|_| current)
1166                .into_iter()
1167                .collect();
1168        }
1169        self.selection_changed.track();
1170        self.selection.borrow().keys.keys().copied().collect()
1171    }
1172
1173    /// Replace the full selection by business key, leaving cursor and expansion alone.
1174    #[doc(hidden)]
1175    pub fn try_replace_selection<E>(
1176        &self,
1177        keys: &[i64],
1178        live: impl FnOnce() -> Result<Arc<TreeSnapshot>, E>,
1179        multiple: impl FnOnce() -> Result<bool, E>,
1180    ) -> Result<Option<TreeSelectionChange>, E> {
1181        let keys = crate::try_prepare_action_view(|| {
1182            if !multiple()? {
1183                return Ok(None);
1184            }
1185            let tree = live()?;
1186            Ok(keys
1187                .iter()
1188                .map(|&key| tree.topology.row_key(key).map(|row| (key, row)))
1189                .collect::<Option<BTreeMap<_, _>>>())
1190        })?;
1191        let Some(keys) = keys else {
1192            return Ok(None);
1193        };
1194        let selected_count = {
1195            let mut selection = self.selection.borrow_mut();
1196            selection.anchor = None;
1197            selection.replace_keys(Arc::new(keys))
1198        };
1199        if selected_count.is_some() {
1200            self.selection_changed.notify();
1201        }
1202        Ok(Some(TreeSelectionChange {
1203            current: None,
1204            selected_count,
1205        }))
1206    }
1207
1208    #[doc(hidden)]
1209    pub fn replace_selection(
1210        &self,
1211        keys: &[i64],
1212        live: impl FnOnce() -> Arc<TreeSnapshot>,
1213        multiple: impl FnOnce() -> bool,
1214    ) -> Option<TreeSelectionChange> {
1215        self.try_replace_selection(
1216            keys,
1217            || Ok::<_, std::convert::Infallible>(live()),
1218            || Ok(multiple()),
1219        )
1220        .unwrap_or_else(|error| match error {})
1221    }
1222
1223    #[doc(hidden)]
1224    pub fn selection_info(
1225        &self,
1226        tree: &TreeSnapshot,
1227        multiple: bool,
1228        current: i64,
1229        query: Option<TreeSelectionLookup>,
1230    ) -> (i64, bool) {
1231        let key = match query {
1232            Some(TreeSelectionLookup::Row(index)) => usize::try_from(index)
1233                .ok()
1234                .and_then(|index| tree.rows().get(index))
1235                .map(|item| item.key),
1236            Some(TreeSelectionLookup::Key(key)) => Some(key),
1237            None => None,
1238        };
1239        if multiple {
1240            self.selection_changed.track();
1241            let selection = self.selection.borrow();
1242            (
1243                selection.keys.len() as i64,
1244                key.is_some_and(|key| selection.keys.contains_key(&key)),
1245            )
1246        } else {
1247            let current = tree.visible_index(current).map(|_| current);
1248            (
1249                i64::from(current.is_some()),
1250                key.is_some() && key == current,
1251            )
1252        }
1253    }
1254
1255    /// Publish the same visible rows for layout, painting and input routing.
1256    #[doc(hidden)]
1257    pub fn populate_scene(&self, node: &mut Node, tree: Arc<TreeSnapshot>) {
1258        node.list = Some(ListMetrics {
1259            row_count: tree.rows().len(),
1260            first_row: 0,
1261        });
1262        node.properties
1263            .entry("current-key")
1264            .or_insert(Value::Int(-1));
1265        node.tree_selection = node
1266            .boolean("multi-select", false)
1267            .then(|| self.selection());
1268        node.tree = Some(tree);
1269    }
1270
1271    /// Resolve a scene's positional input to stable rows before changing tree state.
1272    #[doc(hidden)]
1273    pub fn try_apply_control<E>(
1274        &self,
1275        node: &Node,
1276        input: crate::InputRoute<'_>,
1277        available: impl FnOnce() -> Result<bool, E>,
1278        multiple: impl FnOnce() -> Result<bool, E>,
1279        live: impl FnOnce() -> Result<Arc<TreeSnapshot>, E>,
1280        current: impl FnOnce() -> Result<i64, E>,
1281    ) -> Result<Option<TreeControlChange>, E> {
1282        let crate::RoutedEvent::Control(action) = *input.event() else {
1283            return Ok(None);
1284        };
1285        let Some(snapshot) = &node.tree else {
1286            return Ok(None);
1287        };
1288        let snapshot_multiple = node.tree_selection.is_some();
1289        let action = match action {
1290            ControlAction::Select(index) => {
1291                let Some(item) = snapshot.rows().get(index) else {
1292                    return Ok(None);
1293                };
1294                TreeAction::Selection(TreeSelectionAction::Row {
1295                    key: item.key,
1296                    row: item.row,
1297                    operation: RowSelection::Replace,
1298                })
1299            }
1300            ControlAction::Tree(action @ TreeAction::SetExpanded { .. }) => action,
1301            ControlAction::Tree(action @ TreeAction::Selection(_)) if snapshot_multiple => action,
1302            _ => return Ok(None),
1303        };
1304        let prepared = crate::property::watch_reads(|reads| {
1305            if !available()? || reads.changed() {
1306                return Ok(None);
1307            }
1308            if matches!(action, TreeAction::Selection(_))
1309                && (multiple()? != snapshot_multiple || reads.changed())
1310            {
1311                return Ok(None);
1312            }
1313            let live = live()?;
1314            if reads.changed() {
1315                return Ok(None);
1316            }
1317            if let TreeAction::Selection(selection) = action
1318                && snapshot_multiple
1319            {
1320                let needs_order = matches!(
1321                    selection,
1322                    TreeSelectionAction::Row {
1323                        operation: RowSelection::Extend | RowSelection::AddRange,
1324                        ..
1325                    }
1326                );
1327                if !snapshot.same_model(&live)
1328                    || (needs_order && !snapshot.same_visible_rows(&live))
1329                {
1330                    return Ok(None);
1331                }
1332            }
1333            let current = current()?;
1334            Ok((input.is_current() && !reads.changed()).then_some((live, current)))
1335        })?;
1336        let Some((live, current)) = prepared else {
1337            return Ok(None);
1338        };
1339        Ok(match action {
1340            TreeAction::Selection(selection) => self
1341                .select_in_mode(&live, current, snapshot_multiple, selection)
1342                .map(TreeControlChange::Selection),
1343            TreeAction::SetExpanded { key, row, expanded } => self
1344                .set_expanded(&live, key, row, expanded)
1345                .then(|| TreeControlChange::Expansion {
1346                    change: TreeExpansionChange { key, expanded },
1347                    current: (!expanded && live.is_descendant(current, key)).then_some(key),
1348                }),
1349        })
1350    }
1351
1352    #[doc(hidden)]
1353    pub fn apply_control(
1354        &self,
1355        node: &Node,
1356        input: crate::InputRoute<'_>,
1357        available: impl FnOnce() -> bool,
1358        multiple: impl FnOnce() -> bool,
1359        live: impl FnOnce() -> Arc<TreeSnapshot>,
1360        current: impl FnOnce() -> i64,
1361    ) -> Option<TreeControlChange> {
1362        self.try_apply_control(
1363            node,
1364            input,
1365            || Ok::<_, std::convert::Infallible>(available()),
1366            || Ok(multiple()),
1367            || Ok(live()),
1368            || Ok(current()),
1369        )
1370        .unwrap_or_else(|error| match error {})
1371    }
1372
1373    /// Resolve a programmatic selection against the current tree projection.
1374    #[doc(hidden)]
1375    pub fn try_apply_selection<E>(
1376        &self,
1377        command: TreeSelectionCommand,
1378        live: impl FnOnce() -> Result<Arc<TreeSnapshot>, E>,
1379        multiple: impl FnOnce() -> Result<bool, E>,
1380        current: impl FnOnce() -> Result<i64, E>,
1381    ) -> Result<Option<TreeSelectionChange>, E> {
1382        let prepared = crate::try_prepare_action_view(|| {
1383            let tree = live()?;
1384            let row = |index: usize, operation| {
1385                tree.rows().get(index).map(|item| TreeSelectionAction::Row {
1386                    key: item.key,
1387                    row: item.row,
1388                    operation,
1389                })
1390            };
1391            let replace = |index| row(index, RowSelection::Replace);
1392            let action = match command {
1393                TreeSelectionCommand::Source(source) => {
1394                    tree.visible_index_for_source(source).and_then(replace)
1395                }
1396                TreeSelectionCommand::Key(key) => tree.visible_index(key).and_then(replace),
1397                TreeSelectionCommand::Visual(TableSelectionAction::Row { index, operation }) => {
1398                    row(index, operation)
1399                }
1400                TreeSelectionCommand::Visual(TableSelectionAction::All) => {
1401                    Some(TreeSelectionAction::All)
1402                }
1403                TreeSelectionCommand::Visual(TableSelectionAction::Clear) => {
1404                    Some(TreeSelectionAction::Clear)
1405                }
1406                TreeSelectionCommand::Visual(_) => None,
1407            };
1408            let Some(action) = action else {
1409                return Ok(None);
1410            };
1411            let multiple = multiple()?;
1412            if !multiple
1413                && !matches!(
1414                    action,
1415                    TreeSelectionAction::Row {
1416                        operation: RowSelection::Replace,
1417                        ..
1418                    }
1419                )
1420            {
1421                return Ok(None);
1422            }
1423            let current = current()?;
1424            Ok(Some((tree, multiple, current, action)))
1425        })?;
1426        Ok(prepared.and_then(|(tree, multiple, current, action)| {
1427            self.select_in_mode(&tree, current, multiple, action)
1428        }))
1429    }
1430
1431    #[doc(hidden)]
1432    pub fn apply_selection(
1433        &self,
1434        command: TreeSelectionCommand,
1435        live: impl FnOnce() -> Arc<TreeSnapshot>,
1436        multiple: impl FnOnce() -> bool,
1437        current: impl FnOnce() -> i64,
1438    ) -> Option<TreeSelectionChange> {
1439        self.try_apply_selection(
1440            command,
1441            || Ok::<_, std::convert::Infallible>(live()),
1442            || Ok(multiple()),
1443            || Ok(current()),
1444        )
1445        .unwrap_or_else(|error| match error {})
1446    }
1447
1448    #[doc(hidden)]
1449    pub fn try_select_source<E>(
1450        &self,
1451        source: usize,
1452        live: impl FnOnce() -> Result<Arc<TreeSnapshot>, E>,
1453        multiple: impl FnOnce() -> Result<bool, E>,
1454        current: impl FnOnce() -> Result<i64, E>,
1455    ) -> Result<Option<TreeSelectionChange>, E> {
1456        self.try_apply_selection(
1457            TreeSelectionCommand::Source(source),
1458            live,
1459            multiple,
1460            current,
1461        )
1462    }
1463
1464    #[doc(hidden)]
1465    pub fn select_source(
1466        &self,
1467        source: usize,
1468        live: impl FnOnce() -> Arc<TreeSnapshot>,
1469        multiple: impl FnOnce() -> bool,
1470        current: impl FnOnce() -> i64,
1471    ) -> Option<TreeSelectionChange> {
1472        self.apply_selection(
1473            TreeSelectionCommand::Source(source),
1474            live,
1475            multiple,
1476            current,
1477        )
1478    }
1479
1480    #[doc(hidden)]
1481    pub fn select_in_mode(
1482        &self,
1483        tree: &TreeSnapshot,
1484        current: i64,
1485        multiple: bool,
1486        action: TreeSelectionAction,
1487    ) -> Option<TreeSelectionChange> {
1488        if !self
1489            .snapshot
1490            .matches_current(|live| std::ptr::eq(live.as_ref(), tree))
1491        {
1492            return None;
1493        }
1494        if multiple {
1495            return self.select(tree, current, action);
1496        }
1497        let TreeSelectionAction::Row { key, row, .. } = action else {
1498            return None;
1499        };
1500        let item = tree.rows().get(tree.visible_index(key)?)?;
1501        (item.row == row && key != current).then_some(TreeSelectionChange {
1502            current: Some(key),
1503            selected_count: None,
1504        })
1505    }
1506
1507    pub fn select(
1508        &self,
1509        tree: &TreeSnapshot,
1510        current: i64,
1511        action: TreeSelectionAction,
1512    ) -> Option<TreeSelectionChange> {
1513        let mut selection = self.selection.borrow_mut();
1514        let mut next = selection.keys.clone();
1515        let current = match action {
1516            TreeSelectionAction::Row {
1517                key,
1518                row,
1519                operation,
1520            } => {
1521                let index = tree.visible_index(key)?;
1522                if tree.rows()[index].row != row {
1523                    return None;
1524                }
1525                match operation {
1526                    RowSelection::Replace => {
1527                        next = Arc::new(BTreeMap::from([(key, row)]));
1528                        selection.anchor = Some((key, row));
1529                    }
1530                    RowSelection::Toggle => {
1531                        let selected = Arc::make_mut(&mut next);
1532                        if selected.remove(&key).is_none() {
1533                            selected.insert(key, row);
1534                        }
1535                        selection.anchor = Some((key, row));
1536                    }
1537                    RowSelection::Extend | RowSelection::AddRange => {
1538                        let start = selection
1539                            .anchor
1540                            .and_then(|(key, _)| tree.visible_index(key))
1541                            .or_else(|| tree.visible_index(current))
1542                            .unwrap_or(index);
1543                        let anchor = &tree.rows()[start];
1544                        selection.anchor = Some((anchor.key, anchor.row));
1545                        let rows = tree.rows()[start.min(index)..=start.max(index)]
1546                            .iter()
1547                            .map(|item| (item.key, item.row));
1548                        if operation == RowSelection::Extend {
1549                            next = Arc::new(rows.collect());
1550                        } else {
1551                            Arc::make_mut(&mut next).extend(rows);
1552                        }
1553                    }
1554                    RowSelection::Move => {}
1555                }
1556                (key != current).then_some(key)
1557            }
1558            TreeSelectionAction::All => {
1559                next = Arc::new(
1560                    tree.rows()
1561                        .iter()
1562                        .map(|item| (item.key, item.row))
1563                        .collect(),
1564                );
1565                selection.anchor = None;
1566                None
1567            }
1568            TreeSelectionAction::Clear => {
1569                next = Arc::new(BTreeMap::new());
1570                selection.anchor = None;
1571                None
1572            }
1573        };
1574        let selected_count = selection.replace_keys(next);
1575        drop(selection);
1576        if selected_count.is_some() {
1577            self.selection_changed.notify();
1578        }
1579        Some(TreeSelectionChange {
1580            current,
1581            selected_count,
1582        })
1583    }
1584}
1585
1586#[cfg(test)]
1587mod tests {
1588    use super::*;
1589    use std::cell::Cell;
1590
1591    #[test]
1592    fn projection_handles_cycles_orphans_and_duplicates_without_rebuilding_on_expand() {
1593        let model = Rc::new(VecModel::from(vec![
1594            (9, 8),
1595            (8, 9),
1596            (10, 9),
1597            (3, -1),
1598            (3, -1),
1599            (6, 3),
1600            (7, 7),
1601        ]));
1602        let state = TreeState::default();
1603        let reads = Rc::new(Cell::new(0));
1604        let role_reads = reads.clone();
1605        let roles = move |item: &(i64, i64)| {
1606            role_reads.set(role_reads.get() + 1);
1607            *item
1608        };
1609        let tree = state.snapshot(|| model.clone(), roles.clone());
1610        assert_eq!(
1611            tree.rows().iter().map(|row| row.key).collect::<Vec<_>>(),
1612            [8, 6, 7]
1613        );
1614        assert!(tree.is_descendant(10, 8));
1615        assert!(!tree.is_descendant(8, 9));
1616        let root = tree.rows()[0];
1617        assert!(state.set_expanded(&tree, root.key, root.row, true));
1618        let expanded = state.snapshot(|| model.clone(), roles.clone());
1619        assert_eq!(reads.get(), 7);
1620        assert_eq!(
1621            expanded
1622                .rows()
1623                .iter()
1624                .map(|row| row.key)
1625                .collect::<Vec<_>>(),
1626            [8, 9, 6, 7]
1627        );
1628        assert!(model.set_row(2, (10, 6)));
1629        assert_eq!(reads.get(), 9);
1630        let reparented = state.snapshot(|| model.clone(), roles);
1631        assert_eq!(reads.get(), 16);
1632        assert!(!reparented.is_descendant(10, 8));
1633        assert!(reparented.is_descendant(10, 6));
1634        assert!(reparented.rows()[0].expanded);
1635    }
1636
1637    #[test]
1638    fn recursive_commands_clear_hidden_descendants_and_preserve_depth_limits() {
1639        let model = Rc::new(VecModel::from(vec![
1640            (1, -1),
1641            (2, 1),
1642            (3, 2),
1643            (4, 1),
1644            (9, -1),
1645            (10, 9),
1646        ]));
1647        let state = TreeState::default();
1648        let tree = || state.snapshot(|| model.clone(), |row| *row);
1649        let initial = tree();
1650        assert_eq!(initial.depth(3), Some(2));
1651        assert_eq!(initial.depth(99), None);
1652        assert!(
1653            state
1654                .command(
1655                    &initial,
1656                    TreeCommand::ExpandRecursively { key: 1, depth: 1 }
1657                )
1658                .is_some()
1659        );
1660        assert!(tree().is_expanded(1));
1661        assert!(!tree().is_expanded(2));
1662        assert_eq!(tree().visible_index(3), None);
1663
1664        assert!(state.command(&tree(), TreeCommand::ExpandTo(3)).is_some());
1665        assert_eq!(tree().visible_index(3), Some(2));
1666        assert!(state.command(&tree(), TreeCommand::Collapse(1)).is_some());
1667        assert!(tree().is_expanded(2));
1668        assert_eq!(tree().nearest_visible_ancestor(3), Some(1));
1669        assert!(
1670            state
1671                .command(&tree(), TreeCommand::CollapseRecursively(1))
1672                .is_some()
1673        );
1674        assert!(!tree().is_expanded(2));
1675        assert!(state.command(&tree(), TreeCommand::Expand(1)).is_some());
1676        assert_eq!(tree().visible_index(3), None);
1677
1678        let before = tree();
1679        for command in [
1680            TreeCommand::Expand(99),
1681            TreeCommand::ExpandRecursively { key: 1, depth: 0 },
1682            TreeCommand::ExpandRecursively { key: 1, depth: -2 },
1683        ] {
1684            assert!(state.command(&before, command).is_none());
1685        }
1686        assert!(Arc::ptr_eq(&before, &tree()));
1687        assert!(state.command(&tree(), TreeCommand::ExpandTo(3)).is_some());
1688        let prior_model = tree();
1689        assert_eq!(model.remove(1), Some((2, 1)));
1690        model.push((2, 1));
1691        assert!(
1692            state
1693                .command(&prior_model, TreeCommand::CollapseRecursively(-1))
1694                .is_none()
1695        );
1696        assert!(!tree().is_expanded(2));
1697        assert_eq!(tree().visible_index(3), None);
1698    }
1699
1700    #[test]
1701    fn changing_the_view_root_reuses_topology_and_limits_expansion_to_the_branch() {
1702        let model = Rc::new(VecModel::from(vec![
1703            (1, -1),
1704            (10, 1),
1705            (100, 10),
1706            (103, 100),
1707            (2, -1),
1708            (20, 2),
1709        ]));
1710        let state = TreeState::default();
1711        let requested = Property::default();
1712        let reads = Rc::new(Cell::new(0));
1713        let count = reads.clone();
1714        let roles = move |row: &(i64, i64)| {
1715            count.set(count.get() + 1);
1716            *row
1717        };
1718        let tree =
1719            || state.snapshot_with_root(|| model.clone(), roles.clone(), || requested.get(|| -1));
1720        assert!(
1721            state
1722                .command(
1723                    &tree(),
1724                    TreeCommand::ExpandRecursively { key: -1, depth: -1 }
1725                )
1726                .is_some()
1727        );
1728        let global = tree();
1729        assert_eq!(global.rows().len(), 6);
1730
1731        requested.set(10);
1732        let source = tree();
1733        assert!(Arc::ptr_eq(&global.topology, &source.topology));
1734        assert_eq!(
1735            source.rows().iter().map(|row| row.key).collect::<Vec<_>>(),
1736            [100, 103]
1737        );
1738        assert_eq!(source.rows()[0].parent, None);
1739        assert_eq!(source.depth(100), Some(0));
1740        assert_eq!(source.depth(103), Some(1));
1741        assert_eq!(source.depth(10), None);
1742        assert_eq!(source.depth(20), None);
1743        assert!(!source.is_descendant(103, 10));
1744        assert!(state.command(&source, TreeCommand::ExpandTo(20)).is_none());
1745        assert!(
1746            state
1747                .command(&source, TreeCommand::CollapseRecursively(-1))
1748                .is_some()
1749        );
1750
1751        requested.set(2);
1752        assert_eq!(tree().rows()[0].key, 20);
1753        assert_eq!(tree().rows()[0].depth, 0);
1754        requested.set(-1);
1755        let restored = tree();
1756        assert!(restored.is_expanded(1));
1757        assert!(restored.is_expanded(10));
1758        assert!(!restored.is_expanded(100));
1759        assert!(restored.is_expanded(2));
1760        assert_eq!(reads.get(), 6);
1761
1762        requested.set(999);
1763        let missing = tree();
1764        assert!(missing.rows().is_empty());
1765        assert!(
1766            state
1767                .command(&missing, TreeCommand::CollapseRecursively(-1))
1768                .is_none()
1769        );
1770        assert_eq!(missing.depth(100), None);
1771        assert_eq!(missing.root_key(), 999);
1772    }
1773
1774    #[test]
1775    fn filtering_uses_live_matches_and_preserves_the_saved_expansion() {
1776        type Row = (i64, i64, &'static str);
1777        let source = Property::default();
1778        let model = Rc::new(VecModel::from(vec![
1779            (1, -1, "project"),
1780            (2, 1, "src"),
1781            (3, 2, "Window.RS"),
1782            (4, 1, "notes"),
1783            (5, -1, "window outside"),
1784        ]));
1785        source.set(model.clone());
1786        let query = Property::default();
1787        query.set(" WINDOW ".to_owned());
1788        let state = TreeState::default();
1789        let read = || {
1790            state.snapshot_filtered(
1791                || source.get(|| unreachable!()),
1792                |row: &Row| (row.0, row.1),
1793                || 1,
1794                || query.get(String::new),
1795                |row| row.2,
1796            )
1797        };
1798        let filtered = read();
1799        assert!(filtered.is_filtering());
1800        assert_eq!(
1801            filtered
1802                .rows()
1803                .iter()
1804                .map(|row| row.key)
1805                .collect::<Vec<_>>(),
1806            [2, 3]
1807        );
1808        assert!(filtered.is_expanded(2));
1809        assert!(state.command(&filtered, TreeCommand::Collapse(2)).is_none());
1810        assert!(model.set_row(3, (4, 1, "README")));
1811        assert!(model.set_row(4, (5, -1, "outside rename")));
1812        assert!(Arc::ptr_eq(&filtered, &read()));
1813        assert!(model.set_row(3, (4, 1, "window docs")));
1814        assert_eq!(read().visible_index(4), Some(2));
1815
1816        query.set(String::new());
1817        let original = read();
1818        assert!(!original.is_filtering());
1819        assert!(!original.is_expanded(2));
1820        assert_eq!(original.visible_index(3), None);
1821
1822        query.set("window".to_owned());
1823        let before = read();
1824        source.set(Rc::new(VecModel::from(vec![
1825            (1, -1, "new project"),
1826            (9, 1, "window"),
1827        ])));
1828        let replaced = read();
1829        assert!(!before.same_model(&replaced));
1830        assert_eq!(replaced.rows()[0].key, 9);
1831        assert_eq!(replaced.rows().len(), 1);
1832    }
1833
1834    #[test]
1835    fn filtering_projects_the_model_after_reading_the_query() {
1836        let model = Rc::new(VecModel::from(vec![(1, -1, "one"), (2, 1, "two")]));
1837        let state = TreeState::default();
1838        let tree = state.snapshot_filtered(
1839            || model.clone(),
1840            |row| (row.0, row.1),
1841            || -1,
1842            || {
1843                assert_eq!(model.remove(0), Some((1, -1, "one")));
1844                "two".to_owned()
1845            },
1846            |row| row.2,
1847        );
1848        assert_eq!(tree.rows().len(), 1);
1849        assert_eq!((tree.rows()[0].key, tree.rows()[0].model_index), (2, 0));
1850    }
1851
1852    #[test]
1853    fn deep_ancestor_expansion_uses_the_topology_without_recursive_calls() {
1854        let model = Rc::new(VecModel::from(
1855            (0..4096).map(|key| (key, key - 1)).collect::<Vec<_>>(),
1856        ));
1857        let state = TreeState::default();
1858        let initial = state.snapshot(|| model.clone(), |row| *row);
1859        let topology = initial.topology.clone();
1860        assert!(
1861            state
1862                .command(&initial, TreeCommand::ExpandTo(4095))
1863                .is_some()
1864        );
1865        let expanded = state.snapshot(|| model.clone(), |row| *row);
1866        assert!(Arc::ptr_eq(&topology, &expanded.topology));
1867        assert_eq!(expanded.visible_index(4095), Some(4095));
1868        assert_eq!(expanded.depth(4095), Some(4095));
1869        assert!(
1870            state
1871                .command(&expanded, TreeCommand::CollapseRecursively(-1))
1872                .is_some()
1873        );
1874        let collapsed = state.snapshot(|| model.clone(), |row| *row);
1875        assert_eq!(collapsed.rows().len(), 1);
1876        assert!(!collapsed.is_expanded(4094));
1877    }
1878
1879    #[test]
1880    fn payload_changes_leave_independent_tree_projections_clean() {
1881        let model = Rc::new(VecModel::from(vec![(1, -1, -1, 0), (2, 1, -1, 0)]));
1882        let source = Property::default();
1883        source.set(model.clone());
1884        let primary = TreeState::default();
1885        let alternate = TreeState::default();
1886        let roles = |row: &(i64, i64, i64, i64)| (row.0, row.1);
1887        let other_roles = |row: &(i64, i64, i64, i64)| (row.0, row.2);
1888        let primary_tree = || primary.snapshot(|| source.get(|| unreachable!()), roles);
1889        let alternate_tree = || alternate.snapshot(|| model.clone(), other_roles);
1890        let first = primary_tree();
1891        let second = alternate_tree();
1892
1893        assert!(model.set_row(1, (2, 1, -1, 50)));
1894        assert!(Arc::ptr_eq(&first, &primary_tree()));
1895        assert!(Arc::ptr_eq(&second, &alternate_tree()));
1896        assert!(model.set_row(1, (2, 1, 1, 50)));
1897        assert!(Arc::ptr_eq(&first, &primary_tree()));
1898        let reparented = alternate_tree();
1899        assert!(!Arc::ptr_eq(&second, &reparented));
1900        assert!(reparented.is_descendant(2, 1));
1901
1902        source.set(Rc::new(VecModel::from(vec![(3, -1, -1, 0)])));
1903        let replacement = primary_tree();
1904        assert!(!replacement.same_model(&first));
1905        assert_eq!(replacement.rows()[0].key, 3);
1906        assert!(model.set_row(1, (2, -1, -1, 50)));
1907        assert!(Arc::ptr_eq(&replacement, &primary_tree()));
1908        assert!(!alternate_tree().is_descendant(2, 1));
1909        assert!(model.sort_by(|left, right| right.0.cmp(&left.0)));
1910        assert_eq!(alternate_tree().rows()[0].key, 2);
1911        assert!(Arc::ptr_eq(&replacement, &primary_tree()));
1912    }
1913
1914    #[test]
1915    fn visibility_masks_branches_without_rebuilding_topology_or_losing_expansion() {
1916        type Record = (i64, i64, bool, &'static str);
1917        let model = Rc::new(VecModel::from(vec![
1918            (1, -1, true, "root"),
1919            (2, 1, true, "branch"),
1920            (3, 2, true, "leaf"),
1921            (4, -1, true, "other"),
1922        ]));
1923        let root = Property::default();
1924        let query = Property::default();
1925        let state = TreeState::default();
1926        let snapshot = || {
1927            state.snapshot_projected(
1928                || model.clone(),
1929                |row| (row.0, row.1),
1930                || root.get(|| -1),
1931                Some(|row: &Record| row.2),
1932                Some(|row: &Record| row.3),
1933                || query.get(String::new),
1934            )
1935        };
1936        let keys =
1937            |tree: &TreeSnapshot| tree.rows().iter().map(|item| item.key).collect::<Vec<_>>();
1938        let first = snapshot();
1939        assert!(state.command(&first, TreeCommand::ExpandTo(3)).is_some());
1940        let expanded = snapshot();
1941        assert_eq!(keys(&expanded), [1, 2, 3, 4]);
1942        assert!(Arc::ptr_eq(
1943            first.available.as_ref().unwrap(),
1944            expanded.available.as_ref().unwrap()
1945        ));
1946        let leaf = model.row_key(2).unwrap();
1947        state
1948            .select(
1949                &expanded,
1950                -1,
1951                TreeSelectionAction::Row {
1952                    key: 3,
1953                    row: leaf,
1954                    operation: RowSelection::Replace,
1955                },
1956            )
1957            .unwrap();
1958
1959        model.set_row(1, (2, 1, false, "branch"));
1960        assert!(state.command(&expanded, TreeCommand::Collapse(2)).is_none());
1961        let hidden = snapshot();
1962        assert!(Arc::ptr_eq(&expanded.topology, &hidden.topology));
1963        assert_eq!(keys(&hidden), [1, 4]);
1964        assert_eq!(hidden.depth(3), None);
1965        assert_eq!(hidden.nearest_visible_ancestor(3), Some(1));
1966        assert!(!hidden.is_expanded(1));
1967        assert!(!hidden.is_filtering());
1968        assert!(
1969            state
1970                .command(&hidden, TreeCommand::CollapseRecursively(-1))
1971                .is_none()
1972        );
1973        assert_eq!(state.selection().get(&3), Some(&leaf));
1974        model.set_row(2, (3, 2, false, "leaf"));
1975        assert!(Arc::ptr_eq(&hidden, &snapshot()));
1976
1977        query.set("needle".into());
1978        let filtered = snapshot();
1979        assert!(filtered.rows().is_empty());
1980        model.set_row(2, (3, 2, true, "needle"));
1981        assert!(Arc::ptr_eq(&filtered, &snapshot()));
1982        model.set_row(1, (2, 1, true, "branch"));
1983        assert_eq!(keys(&snapshot()), [1, 2, 3]);
1984        query.set(String::new());
1985        assert_eq!(keys(&snapshot()), [1, 2, 3, 4]);
1986
1987        root.set(2);
1988        assert_eq!(keys(&snapshot()), [3]);
1989        model.set_row(0, (1, -1, false, "root"));
1990        assert!(snapshot().rows().is_empty());
1991        model.set_row(0, (1, -1, true, "root"));
1992        assert_eq!(keys(&snapshot()), [3]);
1993    }
1994}