1use crate::{ChangeSignal, Property, RowKey, RowSelection, VecModel, list::MAX_ROWS};
2use std::{
3 cell::RefCell,
4 collections::{BTreeMap, HashMap, HashSet},
5 rc::Rc,
6 sync::Arc,
7};
8
9#[derive(Clone, Copy, Debug, PartialEq, Eq)]
10pub enum TreeAction {
11 SetExpanded {
12 key: i64,
13 row: RowKey,
14 expanded: bool,
15 },
16 Selection(TreeSelectionAction),
17}
18
19#[derive(Clone, Copy, Debug, PartialEq, Eq)]
20pub enum TreeSelectionAction {
21 Row {
22 key: i64,
23 row: RowKey,
24 operation: RowSelection,
25 },
26 All,
27 Clear,
28}
29
30#[doc(hidden)]
31pub struct TreeSelectionChange {
32 pub current: Option<i64>,
33 pub selected_count: Option<usize>,
34}
35
36#[derive(Clone, Copy, Debug, PartialEq, Eq)]
37pub struct TreeItem {
38 pub key: i64,
39 pub row: RowKey,
40 pub model_index: usize,
41 pub parent: Option<i64>,
42 pub depth: usize,
43 pub has_children: bool,
44 pub expanded: bool,
45}
46
47#[derive(Debug, PartialEq, Eq)]
48struct Entry {
49 key: i64,
50 row: RowKey,
51 model_index: usize,
52 parent: Option<usize>,
53 children: Vec<usize>,
54}
55
56#[derive(Debug, PartialEq, Eq)]
57struct Topology {
58 model: u64,
59 entries: Vec<Entry>,
60 index: HashMap<i64, usize>,
61 roots: Vec<usize>,
62}
63
64impl Topology {
65 fn new<T>(model: &VecModel<T>, model_id: u64, roles: impl Fn(&T) -> (i64, i64)) -> Self {
66 let mut candidates = Vec::new();
67 let mut seen = HashSet::new();
68 let mut duplicates = HashSet::new();
69 model.visit_rows_untracked(MAX_ROWS, |index, row, item| {
70 let (key, parent) = roles(item);
71 if key < 0 {
72 return;
73 }
74 if !seen.insert(key) {
75 duplicates.insert(key);
76 }
77 candidates.push((index, row, key, parent));
78 });
79 candidates.retain(|(_, _, key, _)| !duplicates.contains(key));
80 let index: HashMap<_, _> = candidates
81 .iter()
82 .enumerate()
83 .map(|(index, (_, _, key, _))| (*key, index))
84 .collect();
85 let mut entries: Vec<_> = candidates
86 .into_iter()
87 .map(|(model_index, row, key, parent)| Entry {
88 key,
89 row,
90 model_index,
91 parent: index.get(&parent).copied(),
92 children: Vec::new(),
93 })
94 .collect();
95
96 let mut state = vec![0_u8; entries.len()];
98 let mut chain = Vec::new();
99 for start in 0..entries.len() {
100 let mut current = Some(start);
101 while let Some(node) = current {
102 if state[node] == 2 {
103 break;
104 }
105 if state[node] == 1 {
106 let cycle = chain
107 .iter()
108 .copied()
109 .rev()
110 .take_while(|&index| index != node);
111 let root = cycle
112 .chain(std::iter::once(node))
113 .min_by_key(|&index| entries[index].key)
114 .unwrap();
115 entries[root].parent = None;
116 break;
117 }
118 state[node] = 1;
119 chain.push(node);
120 current = entries[node].parent;
121 }
122 for node in chain.drain(..) {
123 state[node] = 2;
124 }
125 }
126 let mut roots = Vec::new();
127 for child in 0..entries.len() {
128 if let Some(parent) = entries[child].parent {
129 entries[parent].children.push(child);
130 } else {
131 roots.push(child);
132 }
133 }
134 Self {
135 model: model_id,
136 entries,
137 index,
138 roots,
139 }
140 }
141
142 fn row_key(&self, key: i64) -> Option<RowKey> {
143 self.index.get(&key).map(|&index| self.entries[index].row)
144 }
145}
146
147#[derive(Debug, PartialEq, Eq)]
149pub struct TreeSnapshot {
150 topology: Arc<Topology>,
151 visible: Vec<TreeItem>,
152 visible_indices: HashMap<i64, usize>,
153}
154
155impl TreeSnapshot {
156 fn new(topology: Arc<Topology>, expanded: &BTreeMap<i64, RowKey>) -> Self {
157 let mut visible = Vec::new();
158 let mut pending: Vec<_> = topology
159 .roots
160 .iter()
161 .rev()
162 .map(|&index| (index, 0))
163 .collect();
164 while let Some((index, depth)) = pending.pop() {
165 let node = &topology.entries[index];
166 let has_children = !node.children.is_empty();
167 let expanded = has_children && expanded.get(&node.key) == Some(&node.row);
168 visible.push(TreeItem {
169 key: node.key,
170 row: node.row,
171 model_index: node.model_index,
172 parent: node.parent.map(|index| topology.entries[index].key),
173 depth,
174 has_children,
175 expanded,
176 });
177 if expanded {
178 pending.extend(node.children.iter().rev().map(|&index| (index, depth + 1)));
179 }
180 }
181 let visible_indices = visible
182 .iter()
183 .enumerate()
184 .map(|(index, item)| (item.key, index))
185 .collect();
186 Self {
187 topology,
188 visible,
189 visible_indices,
190 }
191 }
192
193 pub fn rows(&self) -> &[TreeItem] {
194 &self.visible
195 }
196
197 pub fn visible_index(&self, key: i64) -> Option<usize> {
198 self.visible_indices.get(&key).copied()
199 }
200
201 #[doc(hidden)]
202 pub fn same_model(&self, other: &Self) -> bool {
203 self.topology.model == other.topology.model
204 }
205
206 pub fn is_descendant(&self, key: i64, ancestor: i64) -> bool {
207 let Some(&index) = self.topology.index.get(&key) else {
208 return false;
209 };
210 let mut parent = self.topology.entries[index].parent;
211 while let Some(index) = parent {
212 let node = &self.topology.entries[index];
213 if node.key == ancestor {
214 return true;
215 }
216 parent = node.parent;
217 }
218 false
219 }
220}
221
222#[derive(Default)]
223struct Selection {
224 keys: Arc<BTreeMap<i64, RowKey>>,
225 anchor: Option<(i64, RowKey)>,
226}
227
228impl Selection {
229 fn retain_live(&mut self, topology: &Topology) {
230 let live = |key, row| topology.row_key(key) == Some(row);
231 if self.keys.iter().any(|(&key, &row)| !live(key, row)) {
232 Arc::make_mut(&mut self.keys).retain(|&key, row| live(key, *row));
233 }
234 self.anchor = self.anchor.filter(|&(key, row)| live(key, row));
235 }
236}
237
238#[doc(hidden)]
239#[derive(Default)]
240pub struct TreeState {
241 topology: Property<Arc<Topology>>,
242 roles_changed: RefCell<Option<(u64, Rc<ChangeSignal>)>>,
243 snapshot: Property<Arc<TreeSnapshot>>,
244 expanded: Property<BTreeMap<i64, RowKey>>,
245 selection: RefCell<Selection>,
246 selection_changed: ChangeSignal,
247}
248
249impl TreeState {
250 pub fn snapshot<T>(
252 &self,
253 model: impl FnOnce() -> Rc<VecModel<T>>,
254 roles: impl Fn(&T) -> (i64, i64) + Clone + 'static,
255 ) -> Arc<TreeSnapshot> {
256 self.snapshot.get(|| {
257 let topology = self.topology.get(|| {
258 let model = model();
259 let model_id = model.structure_stamp().0;
260 {
261 let mut observation = self.roles_changed.borrow_mut();
262 if let Some((_, signal)) =
263 observation.as_ref().filter(|(id, _)| *id == model_id)
264 {
265 signal.track();
266 } else {
267 let signal = model.observe_projection(MAX_ROWS, roles.clone());
268 signal.track();
269 *observation = Some((model_id, signal));
270 }
271 }
272 let topology = Arc::new(Topology::new(&model, model_id, roles));
273 self.selection.borrow_mut().retain_live(&topology);
274 topology
275 });
276 Arc::new(TreeSnapshot::new(
277 topology,
278 &self.expanded.get(BTreeMap::new),
279 ))
280 })
281 }
282
283 pub fn set_expanded(&self, tree: &TreeSnapshot, key: i64, row: RowKey, expanded: bool) -> bool {
284 if !tree
285 .visible_index(key)
286 .and_then(|index| tree.rows().get(index))
287 .is_some_and(|item| item.row == row && item.has_children && item.expanded != expanded)
288 {
289 return false;
290 }
291 let mut state = self.expanded.get(BTreeMap::new);
292 state.retain(|key, row| tree.topology.row_key(*key) == Some(*row));
293 if expanded {
294 state.insert(key, row);
295 } else {
296 state.remove(&key);
297 }
298 self.expanded.set_if_changed(state);
299 true
300 }
301
302 pub fn selection(&self) -> Arc<BTreeMap<i64, RowKey>> {
303 self.selection_changed.track();
304 self.selection.borrow().keys.clone()
305 }
306
307 pub fn select(
308 &self,
309 tree: &TreeSnapshot,
310 current: i64,
311 action: TreeSelectionAction,
312 ) -> Option<TreeSelectionChange> {
313 let mut selection = self.selection.borrow_mut();
314 let mut next = selection.keys.clone();
315 let current = match action {
316 TreeSelectionAction::Row {
317 key,
318 row,
319 operation,
320 } => {
321 let index = tree.visible_index(key)?;
322 if tree.rows()[index].row != row {
323 return None;
324 }
325 match operation {
326 RowSelection::Replace => {
327 next = Arc::new(BTreeMap::from([(key, row)]));
328 selection.anchor = Some((key, row));
329 }
330 RowSelection::Toggle => {
331 let selected = Arc::make_mut(&mut next);
332 if selected.remove(&key).is_none() {
333 selected.insert(key, row);
334 }
335 selection.anchor = Some((key, row));
336 }
337 RowSelection::Extend | RowSelection::AddRange => {
338 let start = selection
339 .anchor
340 .and_then(|(key, _)| tree.visible_index(key))
341 .or_else(|| tree.visible_index(current))
342 .unwrap_or(index);
343 let anchor = &tree.rows()[start];
344 selection.anchor = Some((anchor.key, anchor.row));
345 let rows = tree.rows()[start.min(index)..=start.max(index)]
346 .iter()
347 .map(|item| (item.key, item.row));
348 if operation == RowSelection::Extend {
349 next = Arc::new(rows.collect());
350 } else {
351 Arc::make_mut(&mut next).extend(rows);
352 }
353 }
354 RowSelection::Move => {}
355 }
356 (key != current).then_some(key)
357 }
358 TreeSelectionAction::All => {
359 next = Arc::new(
360 tree.rows()
361 .iter()
362 .map(|item| (item.key, item.row))
363 .collect(),
364 );
365 selection.anchor = None;
366 None
367 }
368 TreeSelectionAction::Clear => {
369 next = Arc::new(BTreeMap::new());
370 selection.anchor = None;
371 None
372 }
373 };
374 let selected_count = (next != selection.keys).then_some(next.len());
375 if selected_count.is_some() {
376 selection.keys = next;
377 self.selection_changed.notify();
378 }
379 Some(TreeSelectionChange {
380 current,
381 selected_count,
382 })
383 }
384}
385
386#[cfg(test)]
387mod tests {
388 use super::*;
389 use std::cell::Cell;
390
391 #[test]
392 fn projection_handles_cycles_orphans_and_duplicates_without_rebuilding_on_expand() {
393 let model = Rc::new(VecModel::from(vec![
394 (9, 8),
395 (8, 9),
396 (10, 9),
397 (3, -1),
398 (3, -1),
399 (6, 3),
400 (7, 7),
401 ]));
402 let state = TreeState::default();
403 let reads = Rc::new(Cell::new(0));
404 let role_reads = reads.clone();
405 let roles = move |item: &(i64, i64)| {
406 role_reads.set(role_reads.get() + 1);
407 *item
408 };
409 let tree = state.snapshot(|| model.clone(), roles.clone());
410 assert_eq!(
411 tree.rows().iter().map(|row| row.key).collect::<Vec<_>>(),
412 [8, 6, 7]
413 );
414 assert!(tree.is_descendant(10, 8));
415 assert!(!tree.is_descendant(8, 9));
416 let root = tree.rows()[0];
417 assert!(state.set_expanded(&tree, root.key, root.row, true));
418 let expanded = state.snapshot(|| model.clone(), roles.clone());
419 assert_eq!(reads.get(), 7);
420 assert_eq!(
421 expanded
422 .rows()
423 .iter()
424 .map(|row| row.key)
425 .collect::<Vec<_>>(),
426 [8, 9, 6, 7]
427 );
428 assert!(model.set_row(2, (10, 6)));
429 assert_eq!(reads.get(), 9);
430 let reparented = state.snapshot(|| model.clone(), roles);
431 assert_eq!(reads.get(), 16);
432 assert!(!reparented.is_descendant(10, 8));
433 assert!(reparented.is_descendant(10, 6));
434 assert!(reparented.rows()[0].expanded);
435 }
436
437 #[test]
438 fn payload_changes_leave_independent_tree_projections_clean() {
439 let model = Rc::new(VecModel::from(vec![(1, -1, -1, 0), (2, 1, -1, 0)]));
440 let source = Property::default();
441 source.set(model.clone());
442 let primary = TreeState::default();
443 let alternate = TreeState::default();
444 let roles = |row: &(i64, i64, i64, i64)| (row.0, row.1);
445 let other_roles = |row: &(i64, i64, i64, i64)| (row.0, row.2);
446 let primary_tree = || primary.snapshot(|| source.get(|| unreachable!()), roles);
447 let alternate_tree = || alternate.snapshot(|| model.clone(), other_roles);
448 let first = primary_tree();
449 let second = alternate_tree();
450
451 assert!(model.set_row(1, (2, 1, -1, 50)));
452 assert!(Arc::ptr_eq(&first, &primary_tree()));
453 assert!(Arc::ptr_eq(&second, &alternate_tree()));
454 assert!(model.set_row(1, (2, 1, 1, 50)));
455 assert!(Arc::ptr_eq(&first, &primary_tree()));
456 let reparented = alternate_tree();
457 assert!(!Arc::ptr_eq(&second, &reparented));
458 assert!(reparented.is_descendant(2, 1));
459
460 source.set(Rc::new(VecModel::from(vec![(3, -1, -1, 0)])));
461 let replacement = primary_tree();
462 assert!(!replacement.same_model(&first));
463 assert_eq!(replacement.rows()[0].key, 3);
464 assert!(model.set_row(1, (2, -1, -1, 50)));
465 assert!(Arc::ptr_eq(&replacement, &primary_tree()));
466 assert!(!alternate_tree().is_descendant(2, 1));
467 assert!(model.sort_by(|left, right| right.0.cmp(&left.0)));
468 assert_eq!(alternate_tree().rows()[0].key, 2);
469 assert!(Arc::ptr_eq(&replacement, &primary_tree()));
470 }
471}