Skip to main content

xrack_runtime/
tree.rs

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