Skip to main content

xrack_runtime/
tree.rs

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