1use std::fmt::Debug;
2
3use ::sum_tree::SumTree;
4use collections::FxHashMap;
5use sum_tree::Bias;
6
7use crate::{FocusHandle, FocusId};
8
9/// Represents a collection of focus handles using the tab-index APIs.
10#[derive(Debug)]
11pub(crate) struct TabStopMap {
12 current_path: TabStopPath,
13 pub(crate) insertion_history: Vec<TabStopOperation>,
14 by_id: FxHashMap<FocusId, TabStopNode>,
15 order: SumTree<TabStopNode>,
16}
17
18#[derive(Debug, Clone)]
19pub enum TabStopOperation {
20 Insert(FocusHandle),
21 Group(TabIndex),
22 GroupEnd,
23}
24
25impl TabStopOperation {
26 fn focus_handle(&self) -> Option<&FocusHandle> {
27 match self {
28 TabStopOperation::Insert(focus_handle) => Some(focus_handle),
29 _ => None,
30 }
31 }
32}
33
34type TabIndex = isize;
35
36#[derive(Debug, Default, PartialEq, Eq, Clone, Ord, PartialOrd)]
37struct TabStopPath(smallvec::SmallVec<[TabIndex; 6]>);
38
39#[derive(Clone, Debug, Default, Eq, PartialEq)]
40struct TabStopNode {
41 /// Path to access the node in the tree
42 /// The final node in the list is a leaf node corresponding to an actual focus handle,
43 /// all other nodes are group nodes
44 path: TabStopPath,
45 /// index into the backing array of nodes. Corresponds to insertion order
46 node_insertion_index: usize,
47
48 /// Whether this node is a tab stop
49 tab_stop: bool,
50}
51
52impl Ord for TabStopNode {
53 fn cmp(&self, other: &Self) -> std::cmp::Ordering {
54 self.path
55 .cmp(&other.path)
56 .then(self.node_insertion_index.cmp(&other.node_insertion_index))
57 }
58}
59
60impl PartialOrd for TabStopNode {
61 fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
62 Some(self.cmp(&other))
63 }
64}
65
66impl Default for TabStopMap {
67 fn default() -> Self {
68 Self {
69 current_path: TabStopPath::default(),
70 insertion_history: Vec::new(),
71 by_id: FxHashMap::default(),
72 order: SumTree::new(()),
73 }
74 }
75}
76
77impl TabStopMap {
78 pub fn insert(&mut self, focus_handle: &FocusHandle) {
79 self.insertion_history
80 .push(TabStopOperation::Insert(focus_handle.clone()));
81 let mut path = self.current_path.clone();
82 path.0.push(focus_handle.tab_index);
83 let order = TabStopNode {
84 node_insertion_index: self.insertion_history.len() - 1,
85 tab_stop: focus_handle.tab_stop,
86 path,
87 };
88 self.by_id.insert(focus_handle.id, order.clone());
89 self.order.insert_or_replace(order, ());
90 }
91
92 pub fn begin_group(&mut self, tab_index: isize) {
93 self.insertion_history
94 .push(TabStopOperation::Group(tab_index));
95 self.current_path.0.push(tab_index);
96 }
97
98 pub fn end_group(&mut self) {
99 self.insertion_history.push(TabStopOperation::GroupEnd);
100 self.current_path.0.pop();
101 }
102
103 pub fn clear(&mut self) {
104 *self = Self::default();
105 self.current_path.0.clear();
106 self.insertion_history.clear();
107 self.by_id.clear();
108 self.order = SumTree::new(());
109 }
110
111 pub fn next(&self, focused_id: Option<&FocusId>) -> Option<FocusHandle> {
112 let Some(focused_id) = focused_id else {
113 let first = self.order.first()?;
114 if first.tab_stop {
115 return self.focus_handle_for_order(first);
116 } else {
117 return self
118 .next_inner(first)
119 .and_then(|order| self.focus_handle_for_order(order));
120 }
121 };
122
123 let Some(node) = self.tab_node_for_focus_id(focused_id) else {
124 return self.next(None);
125 };
126 let item = self.next_inner(node);
127
128 if let Some(item) = item {
129 self.focus_handle_for_order(&item)
130 } else {
131 self.next(None)
132 }
133 }
134
135 fn next_inner(&self, node: &TabStopNode) -> Option<&TabStopNode> {
136 let mut cursor = self.order.cursor::<TabStopNode>(());
137 cursor.seek(&node, Bias::Left);
138 cursor.next();
139 while let Some(item) = cursor.item()
140 && !item.tab_stop
141 {
142 cursor.next();
143 }
144
145 cursor.item()
146 }
147
148 pub fn prev(&self, focused_id: Option<&FocusId>) -> Option<FocusHandle> {
149 let Some(focused_id) = focused_id else {
150 let last = self.order.last()?;
151 if last.tab_stop {
152 return self.focus_handle_for_order(last);
153 } else {
154 return self
155 .prev_inner(last)
156 .and_then(|order| self.focus_handle_for_order(order));
157 }
158 };
159
160 let Some(node) = self.tab_node_for_focus_id(focused_id) else {
161 return self.prev(None);
162 };
163 let item = self.prev_inner(node);
164
165 if let Some(item) = item {
166 self.focus_handle_for_order(&item)
167 } else {
168 self.prev(None)
169 }
170 }
171
172 fn prev_inner(&self, node: &TabStopNode) -> Option<&TabStopNode> {
173 let mut cursor = self.order.cursor::<TabStopNode>(());
174 cursor.seek(&node, Bias::Left);
175 cursor.prev();
176 while let Some(item) = cursor.item()
177 && !item.tab_stop
178 {
179 cursor.prev();
180 }
181
182 cursor.item()
183 }
184
185 pub fn replay(&mut self, nodes: &[TabStopOperation]) {
186 for node in nodes {
187 match node {
188 TabStopOperation::Insert(focus_handle) => self.insert(focus_handle),
189 TabStopOperation::Group(tab_index) => self.begin_group(*tab_index),
190 TabStopOperation::GroupEnd => self.end_group(),
191 }
192 }
193 }
194
195 pub fn paint_index(&self) -> usize {
196 self.insertion_history.len()
197 }
198
199 fn focus_handle_for_order(&self, order: &TabStopNode) -> Option<FocusHandle> {
200 let handle = self.insertion_history[order.node_insertion_index].focus_handle();
201 debug_assert!(
202 handle.is_some(),
203 "The order node did not correspond to an element, this is a GPUI bug"
204 );
205 handle.cloned()
206 }
207
208 fn tab_node_for_focus_id(&self, focused_id: &FocusId) -> Option<&TabStopNode> {
209 let Some(order) = self.by_id.get(focused_id) else {
210 return None;
211 };
212 Some(order)
213 }
214}
215
216mod sum_tree_impl {
217 use sum_tree::SeekTarget;
218
219 use crate::tab_stop::{TabStopNode, TabStopPath};
220
221 #[derive(Clone, Debug)]
222 pub struct TabStopOrderNodeSummary {
223 max_index: usize,
224 max_path: TabStopPath,
225 pub tab_stops: usize,
226 }
227
228 pub type TabStopCount = usize;
229
230 impl sum_tree::ContextLessSummary for TabStopOrderNodeSummary {
231 fn zero() -> Self {
232 TabStopOrderNodeSummary {
233 max_index: 0,
234 max_path: TabStopPath::default(),
235 tab_stops: 0,
236 }
237 }
238
239 fn add_summary(&mut self, summary: &Self) {
240 self.max_index = summary.max_index;
241 self.max_path = summary.max_path.clone();
242 self.tab_stops += summary.tab_stops;
243 }
244 }
245
246 impl sum_tree::KeyedItem for TabStopNode {
247 type Key = Self;
248
249 fn key(&self) -> Self::Key {
250 self.clone()
251 }
252 }
253
254 impl sum_tree::Item for TabStopNode {
255 type Summary = TabStopOrderNodeSummary;
256
257 fn summary(&self, _cx: <Self::Summary as sum_tree::Summary>::Context<'_>) -> Self::Summary {
258 TabStopOrderNodeSummary {
259 max_index: self.node_insertion_index,
260 max_path: self.path.clone(),
261 tab_stops: if self.tab_stop { 1 } else { 0 },
262 }
263 }
264 }
265
266 impl<'a> sum_tree::Dimension<'a, TabStopOrderNodeSummary> for TabStopCount {
267 fn zero(_: <TabStopOrderNodeSummary as sum_tree::Summary>::Context<'_>) -> Self {
268 0
269 }
270
271 fn add_summary(
272 &mut self,
273 summary: &'a TabStopOrderNodeSummary,
274 _: <TabStopOrderNodeSummary as sum_tree::Summary>::Context<'_>,
275 ) {
276 *self += summary.tab_stops;
277 }
278 }
279
280 impl<'a> sum_tree::Dimension<'a, TabStopOrderNodeSummary> for TabStopNode {
281 fn zero(_: <TabStopOrderNodeSummary as sum_tree::Summary>::Context<'_>) -> Self {
282 TabStopNode::default()
283 }
284
285 fn add_summary(
286 &mut self,
287 summary: &'a TabStopOrderNodeSummary,
288 _: <TabStopOrderNodeSummary as sum_tree::Summary>::Context<'_>,
289 ) {
290 self.node_insertion_index = summary.max_index;
291 self.path = summary.max_path.clone();
292 }
293 }
294
295 impl<'a, 'b> SeekTarget<'a, TabStopOrderNodeSummary, TabStopNode> for &'b TabStopNode {
296 fn cmp(
297 &self,
298 cursor_location: &TabStopNode,
299 _: <TabStopOrderNodeSummary as sum_tree::Summary>::Context<'_>,
300 ) -> std::cmp::Ordering {
301 Iterator::cmp(self.path.0.iter(), cursor_location.path.0.iter()).then(
302 <usize as Ord>::cmp(
303 &self.node_insertion_index,
304 &cursor_location.node_insertion_index,
305 ),
306 )
307 }
308 }
309}
310
311#[cfg(test)]
312mod tests {
313 use itertools::Itertools as _;
314
315 use crate::{FocusHandle, FocusId, FocusMap, TabStopMap};
316 use std::sync::Arc;
317
318 #[test]
319 fn test_tab_handles() {
320 let focus_map = Arc::new(FocusMap::default());
321 let mut tab_index_map = TabStopMap::default();
322
323 let focus_handles = vec![
324 FocusHandle::new(&focus_map).tab_stop(true).tab_index(0),
325 FocusHandle::new(&focus_map).tab_stop(true).tab_index(1),
326 FocusHandle::new(&focus_map).tab_stop(true).tab_index(1),
327 FocusHandle::new(&focus_map),
328 FocusHandle::new(&focus_map).tab_index(2),
329 FocusHandle::new(&focus_map).tab_stop(true).tab_index(0),
330 FocusHandle::new(&focus_map).tab_stop(true).tab_index(2),
331 ];
332
333 for handle in focus_handles.iter() {
334 tab_index_map.insert(handle);
335 }
336 let expected = [
337 focus_handles[0].clone(),
338 focus_handles[5].clone(),
339 focus_handles[1].clone(),
340 focus_handles[2].clone(),
341 focus_handles[6].clone(),
342 ];
343
344 let mut prev = None;
345 let mut found = vec![];
346 for _ in 0..expected.len() {
347 let handle = tab_index_map.next(prev.as_ref()).unwrap();
348 prev = Some(handle.id);
349 found.push(handle.id);
350 }
351
352 assert_eq!(
353 found,
354 expected.iter().map(|handle| handle.id).collect::<Vec<_>>()
355 );
356
357 // Select first tab index if no handle is currently focused.
358 assert_eq!(tab_index_map.next(None), Some(expected[0].clone()));
359 // Select last tab index if no handle is currently focused.
360 assert_eq!(tab_index_map.prev(None), expected.last().cloned(),);
361
362 assert_eq!(
363 tab_index_map.next(Some(&expected[0].id)),
364 Some(expected[1].clone())
365 );
366 assert_eq!(
367 tab_index_map.next(Some(&expected[1].id)),
368 Some(expected[2].clone())
369 );
370 assert_eq!(
371 tab_index_map.next(Some(&expected[2].id)),
372 Some(expected[3].clone())
373 );
374 assert_eq!(
375 tab_index_map.next(Some(&expected[3].id)),
376 Some(expected[4].clone())
377 );
378 assert_eq!(
379 tab_index_map.next(Some(&expected[4].id)),
380 Some(expected[0].clone())
381 );
382
383 // prev
384 assert_eq!(tab_index_map.prev(None), Some(expected[4].clone()));
385 assert_eq!(
386 tab_index_map.prev(Some(&expected[0].id)),
387 Some(expected[4].clone())
388 );
389 assert_eq!(
390 tab_index_map.prev(Some(&expected[1].id)),
391 Some(expected[0].clone())
392 );
393 assert_eq!(
394 tab_index_map.prev(Some(&expected[2].id)),
395 Some(expected[1].clone())
396 );
397 assert_eq!(
398 tab_index_map.prev(Some(&expected[3].id)),
399 Some(expected[2].clone())
400 );
401 assert_eq!(
402 tab_index_map.prev(Some(&expected[4].id)),
403 Some(expected[3].clone())
404 );
405 }
406
407 #[test]
408 fn test_tab_non_stop_filtering() {
409 let focus_map = Arc::new(FocusMap::default());
410 let mut tab_index_map = TabStopMap::default();
411
412 // Check that we can query next from a non-stop tab
413 let tab_non_stop_1 = FocusHandle::new(&focus_map).tab_stop(false).tab_index(1);
414 let tab_stop_2 = FocusHandle::new(&focus_map).tab_stop(true).tab_index(2);
415 tab_index_map.insert(&tab_non_stop_1);
416 tab_index_map.insert(&tab_stop_2);
417 let result = tab_index_map.next(Some(&tab_non_stop_1.id)).unwrap();
418 assert_eq!(result.id, tab_stop_2.id);
419
420 // Check that we skip over non-stop tabs
421 let tab_stop_0 = FocusHandle::new(&focus_map).tab_stop(true).tab_index(0);
422 let tab_non_stop_0 = FocusHandle::new(&focus_map).tab_stop(false).tab_index(0);
423 tab_index_map.insert(&tab_stop_0);
424 tab_index_map.insert(&tab_non_stop_0);
425 let result = tab_index_map.next(Some(&tab_stop_0.id)).unwrap();
426 assert_eq!(result.id, tab_stop_2.id);
427 }
428
429 #[must_use]
430 struct TabStopMapTest {
431 tab_map: TabStopMap,
432 focus_map: Arc<FocusMap>,
433 expected: Vec<(usize, FocusId)>,
434 }
435
436 impl TabStopMapTest {
437 #[must_use]
438 fn new() -> Self {
439 Self {
440 tab_map: TabStopMap::default(),
441 focus_map: Arc::new(FocusMap::default()),
442 expected: Vec::default(),
443 }
444 }
445
446 #[must_use]
447 fn tab_non_stop(mut self, index: isize) -> Self {
448 let handle = FocusHandle::new(&self.focus_map)
449 .tab_stop(false)
450 .tab_index(index);
451 self.tab_map.insert(&handle);
452 self
453 }
454
455 #[must_use]
456 fn tab_stop(mut self, index: isize, expected: usize) -> Self {
457 let handle = FocusHandle::new(&self.focus_map)
458 .tab_stop(true)
459 .tab_index(index);
460 self.tab_map.insert(&handle);
461 self.expected.push((expected, handle.id));
462 self.expected.sort_by_key(|(expected, _)| *expected);
463 self
464 }
465
466 #[must_use]
467 fn tab_group(mut self, tab_index: isize, children: impl FnOnce(Self) -> Self) -> Self {
468 self.tab_map.begin_group(tab_index);
469 self = children(self);
470 self.tab_map.end_group();
471 self
472 }
473
474 fn traverse_tab_map(
475 &self,
476 traverse: impl Fn(&TabStopMap, Option<&FocusId>) -> Option<FocusHandle>,
477 ) -> Vec<FocusId> {
478 let mut last_focus_id = None;
479 let mut found = vec![];
480 for _ in 0..self.expected.len() {
481 let handle = traverse(&self.tab_map, last_focus_id.as_ref()).unwrap();
482 last_focus_id = Some(handle.id);
483 found.push(handle.id);
484 }
485 found
486 }
487
488 fn assert(self) {
489 let mut expected = self.expected.iter().map(|(_, id)| *id).collect_vec();
490
491 // Check next order
492 let forward_found = self.traverse_tab_map(|tab_map, prev| tab_map.next(prev));
493 assert_eq!(forward_found, expected);
494
495 // Test overflow. Last to first
496 assert_eq!(
497 self.tab_map
498 .next(forward_found.last())
499 .map(|handle| handle.id),
500 expected.first().cloned()
501 );
502
503 // Check previous order
504 let reversed_found = self.traverse_tab_map(|tab_map, prev| tab_map.prev(prev));
505 expected.reverse();
506 assert_eq!(reversed_found, expected);
507
508 // Test overflow. First to last
509 assert_eq!(
510 self.tab_map
511 .prev(reversed_found.last())
512 .map(|handle| handle.id),
513 expected.first().cloned(),
514 );
515 }
516 }
517
518 #[test]
519 fn test_with_disabled_tab_stop() {
520 TabStopMapTest::new()
521 .tab_stop(0, 0)
522 .tab_non_stop(1)
523 .tab_stop(2, 1)
524 .tab_stop(3, 2)
525 .assert();
526 }
527
528 #[test]
529 fn test_with_multiple_disabled_tab_stops() {
530 TabStopMapTest::new()
531 .tab_non_stop(0)
532 .tab_stop(1, 0)
533 .tab_non_stop(3)
534 .tab_stop(3, 1)
535 .tab_non_stop(4)
536 .assert();
537 }
538
539 #[test]
540 fn test_tab_group_functionality() {
541 TabStopMapTest::new()
542 .tab_stop(0, 0)
543 .tab_stop(0, 1)
544 .tab_group(2, |t| t.tab_stop(0, 2).tab_stop(1, 3))
545 .tab_stop(3, 4)
546 .tab_stop(4, 5)
547 .assert()
548 }
549
550 #[test]
551 fn test_sibling_groups() {
552 TabStopMapTest::new()
553 .tab_stop(0, 0)
554 .tab_stop(1, 1)
555 .tab_group(2, |test| test.tab_stop(0, 2).tab_stop(1, 3))
556 .tab_stop(3, 4)
557 .tab_stop(4, 5)
558 .tab_group(6, |test| test.tab_stop(0, 6).tab_stop(1, 7))
559 .tab_stop(7, 8)
560 .tab_stop(8, 9)
561 .assert();
562 }
563
564 #[test]
565 fn test_nested_group() {
566 TabStopMapTest::new()
567 .tab_stop(0, 0)
568 .tab_stop(1, 1)
569 .tab_group(2, |t| {
570 t.tab_group(0, |t| t.tab_stop(0, 2).tab_stop(1, 3))
571 .tab_stop(1, 4)
572 })
573 .tab_stop(3, 5)
574 .tab_stop(4, 6)
575 .assert();
576 }
577
578 #[test]
579 fn test_sibling_nested_groups() {
580 TabStopMapTest::new()
581 .tab_stop(0, 0)
582 .tab_stop(1, 1)
583 .tab_group(2, |builder| {
584 builder
585 .tab_stop(0, 2)
586 .tab_stop(2, 5)
587 .tab_group(1, |builder| builder.tab_stop(0, 3).tab_stop(1, 4))
588 .tab_group(3, |builder| builder.tab_stop(0, 6).tab_stop(1, 7))
589 })
590 .tab_stop(3, 8)
591 .tab_stop(4, 9)
592 .assert();
593 }
594
595 #[test]
596 fn test_sibling_nested_groups_out_of_order() {
597 TabStopMapTest::new()
598 .tab_stop(9, 9)
599 .tab_stop(8, 8)
600 .tab_group(7, |builder| {
601 builder
602 .tab_stop(0, 2)
603 .tab_stop(2, 5)
604 .tab_group(3, |builder| builder.tab_stop(1, 7).tab_stop(0, 6))
605 .tab_group(1, |builder| builder.tab_stop(0, 3).tab_stop(1, 4))
606 })
607 .tab_stop(3, 0)
608 .tab_stop(4, 1)
609 .assert();
610 }
611}