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