use std::fmt::Debug;
use ::sum_tree::SumTree;
use collections::FxHashMap;
use sum_tree::Bias;
use crate::{FocusHandle, FocusId};
#[derive(Debug)]
pub(crate) struct TabStopMap {
current_path: TabStopPath,
pub(crate) insertion_history: Vec<TabStopOperation>,
by_id: FxHashMap<FocusId, TabStopNode>,
order: SumTree<TabStopNode>,
}
#[derive(Debug, Clone)]
pub enum TabStopOperation {
Insert(FocusHandle),
Group(TabIndex),
GroupEnd,
}
impl TabStopOperation {
fn focus_handle(&self) -> Option<&FocusHandle> {
match self {
TabStopOperation::Insert(focus_handle) => Some(focus_handle),
_ => None,
}
}
}
type TabIndex = isize;
#[derive(Debug, Default, PartialEq, Eq, Clone, Ord, PartialOrd)]
struct TabStopPath(smallvec::SmallVec<[TabIndex; 6]>);
#[derive(Clone, Debug, Default, Eq, PartialEq)]
struct TabStopNode {
path: TabStopPath,
node_insertion_index: usize,
tab_stop: bool,
}
impl Ord for TabStopNode {
fn cmp(&self, other: &Self) -> std::cmp::Ordering {
self.path
.cmp(&other.path)
.then(self.node_insertion_index.cmp(&other.node_insertion_index))
}
}
impl PartialOrd for TabStopNode {
fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
Some(self.cmp(&other))
}
}
impl Default for TabStopMap {
fn default() -> Self {
Self {
current_path: TabStopPath::default(),
insertion_history: Vec::new(),
by_id: FxHashMap::default(),
order: SumTree::new(()),
}
}
}
impl TabStopMap {
pub fn insert(&mut self, focus_handle: &FocusHandle) {
self.insertion_history
.push(TabStopOperation::Insert(focus_handle.clone()));
let mut path = self.current_path.clone();
path.0.push(focus_handle.tab_index);
let order = TabStopNode {
node_insertion_index: self.insertion_history.len() - 1,
tab_stop: focus_handle.tab_stop,
path,
};
self.by_id.insert(focus_handle.id, order.clone());
self.order.insert_or_replace(order, ());
}
pub fn begin_group(&mut self, tab_index: isize) {
self.insertion_history
.push(TabStopOperation::Group(tab_index));
self.current_path.0.push(tab_index);
}
pub fn end_group(&mut self) {
self.insertion_history.push(TabStopOperation::GroupEnd);
self.current_path.0.pop();
}
pub fn clear(&mut self) {
*self = Self::default();
self.current_path.0.clear();
self.insertion_history.clear();
self.by_id.clear();
self.order = SumTree::new(());
}
pub fn next(&self, focused_id: Option<&FocusId>) -> Option<FocusHandle> {
let Some(focused_id) = focused_id else {
let first = self.order.first()?;
if first.tab_stop {
return self.focus_handle_for_order(first);
} else {
return self
.next_inner(first)
.and_then(|order| self.focus_handle_for_order(order));
}
};
let Some(node) = self.tab_node_for_focus_id(focused_id) else {
return self.next(None);
};
let item = self.next_inner(node);
if let Some(item) = item {
self.focus_handle_for_order(&item)
} else {
self.next(None)
}
}
fn next_inner(&self, node: &TabStopNode) -> Option<&TabStopNode> {
let mut cursor = self.order.cursor::<TabStopNode>(());
cursor.seek(&node, Bias::Left);
cursor.next();
while let Some(item) = cursor.item()
&& !item.tab_stop
{
cursor.next();
}
cursor.item()
}
pub fn prev(&self, focused_id: Option<&FocusId>) -> Option<FocusHandle> {
let Some(focused_id) = focused_id else {
let last = self.order.last()?;
if last.tab_stop {
return self.focus_handle_for_order(last);
} else {
return self
.prev_inner(last)
.and_then(|order| self.focus_handle_for_order(order));
}
};
let Some(node) = self.tab_node_for_focus_id(focused_id) else {
return self.prev(None);
};
let item = self.prev_inner(node);
if let Some(item) = item {
self.focus_handle_for_order(&item)
} else {
self.prev(None)
}
}
fn prev_inner(&self, node: &TabStopNode) -> Option<&TabStopNode> {
let mut cursor = self.order.cursor::<TabStopNode>(());
cursor.seek(&node, Bias::Left);
cursor.prev();
while let Some(item) = cursor.item()
&& !item.tab_stop
{
cursor.prev();
}
cursor.item()
}
pub fn replay(&mut self, nodes: &[TabStopOperation]) {
for node in nodes {
match node {
TabStopOperation::Insert(focus_handle) => self.insert(focus_handle),
TabStopOperation::Group(tab_index) => self.begin_group(*tab_index),
TabStopOperation::GroupEnd => self.end_group(),
}
}
}
pub fn paint_index(&self) -> usize {
self.insertion_history.len()
}
fn focus_handle_for_order(&self, order: &TabStopNode) -> Option<FocusHandle> {
let handle = self.insertion_history[order.node_insertion_index].focus_handle();
debug_assert!(
handle.is_some(),
"The order node did not correspond to an element, this is a GPUI bug"
);
handle.cloned()
}
fn tab_node_for_focus_id(&self, focused_id: &FocusId) -> Option<&TabStopNode> {
let Some(order) = self.by_id.get(focused_id) else {
return None;
};
Some(order)
}
}
mod sum_tree_impl {
use sum_tree::SeekTarget;
use crate::tab_stop::{TabStopNode, TabStopPath};
#[derive(Clone, Debug)]
pub struct TabStopOrderNodeSummary {
max_index: usize,
max_path: TabStopPath,
pub tab_stops: usize,
}
pub type TabStopCount = usize;
impl sum_tree::ContextLessSummary for TabStopOrderNodeSummary {
fn zero() -> Self {
TabStopOrderNodeSummary {
max_index: 0,
max_path: TabStopPath::default(),
tab_stops: 0,
}
}
fn add_summary(&mut self, summary: &Self) {
self.max_index = summary.max_index;
self.max_path = summary.max_path.clone();
self.tab_stops += summary.tab_stops;
}
}
impl sum_tree::KeyedItem for TabStopNode {
type Key = Self;
fn key(&self) -> Self::Key {
self.clone()
}
}
impl sum_tree::Item for TabStopNode {
type Summary = TabStopOrderNodeSummary;
fn summary(&self, _cx: <Self::Summary as sum_tree::Summary>::Context<'_>) -> Self::Summary {
TabStopOrderNodeSummary {
max_index: self.node_insertion_index,
max_path: self.path.clone(),
tab_stops: if self.tab_stop { 1 } else { 0 },
}
}
}
impl<'a> sum_tree::Dimension<'a, TabStopOrderNodeSummary> for TabStopCount {
fn zero(_: <TabStopOrderNodeSummary as sum_tree::Summary>::Context<'_>) -> Self {
0
}
fn add_summary(
&mut self,
summary: &'a TabStopOrderNodeSummary,
_: <TabStopOrderNodeSummary as sum_tree::Summary>::Context<'_>,
) {
*self += summary.tab_stops;
}
}
impl<'a> sum_tree::Dimension<'a, TabStopOrderNodeSummary> for TabStopNode {
fn zero(_: <TabStopOrderNodeSummary as sum_tree::Summary>::Context<'_>) -> Self {
TabStopNode::default()
}
fn add_summary(
&mut self,
summary: &'a TabStopOrderNodeSummary,
_: <TabStopOrderNodeSummary as sum_tree::Summary>::Context<'_>,
) {
self.node_insertion_index = summary.max_index;
self.path = summary.max_path.clone();
}
}
impl<'a, 'b> SeekTarget<'a, TabStopOrderNodeSummary, TabStopNode> for &'b TabStopNode {
fn cmp(
&self,
cursor_location: &TabStopNode,
_: <TabStopOrderNodeSummary as sum_tree::Summary>::Context<'_>,
) -> std::cmp::Ordering {
Iterator::cmp(self.path.0.iter(), cursor_location.path.0.iter()).then(
<usize as Ord>::cmp(
&self.node_insertion_index,
&cursor_location.node_insertion_index,
),
)
}
}
}
#[cfg(test)]
mod tests {
use itertools::Itertools as _;
use crate::{FocusHandle, FocusId, FocusMap, TabStopMap};
use std::sync::Arc;
#[test]
fn test_tab_handles() {
let focus_map = Arc::new(FocusMap::default());
let mut tab_index_map = TabStopMap::default();
let focus_handles = [
FocusHandle::new(&focus_map).tab_stop(true).tab_index(0),
FocusHandle::new(&focus_map).tab_stop(true).tab_index(1),
FocusHandle::new(&focus_map).tab_stop(true).tab_index(1),
FocusHandle::new(&focus_map),
FocusHandle::new(&focus_map).tab_index(2),
FocusHandle::new(&focus_map).tab_stop(true).tab_index(0),
FocusHandle::new(&focus_map).tab_stop(true).tab_index(2),
];
for handle in focus_handles.iter() {
tab_index_map.insert(handle);
}
let expected = [
focus_handles[0].clone(),
focus_handles[5].clone(),
focus_handles[1].clone(),
focus_handles[2].clone(),
focus_handles[6].clone(),
];
let mut prev = None;
let mut found = vec![];
for _ in 0..expected.len() {
let handle = tab_index_map.next(prev.as_ref()).unwrap();
prev = Some(handle.id);
found.push(handle.id);
}
assert_eq!(
found,
expected.iter().map(|handle| handle.id).collect::<Vec<_>>()
);
assert_eq!(tab_index_map.next(None), Some(expected[0].clone()));
assert_eq!(tab_index_map.prev(None), expected.last().cloned(),);
assert_eq!(
tab_index_map.next(Some(&expected[0].id)),
Some(expected[1].clone())
);
assert_eq!(
tab_index_map.next(Some(&expected[1].id)),
Some(expected[2].clone())
);
assert_eq!(
tab_index_map.next(Some(&expected[2].id)),
Some(expected[3].clone())
);
assert_eq!(
tab_index_map.next(Some(&expected[3].id)),
Some(expected[4].clone())
);
assert_eq!(
tab_index_map.next(Some(&expected[4].id)),
Some(expected[0].clone())
);
assert_eq!(tab_index_map.prev(None), Some(expected[4].clone()));
assert_eq!(
tab_index_map.prev(Some(&expected[0].id)),
Some(expected[4].clone())
);
assert_eq!(
tab_index_map.prev(Some(&expected[1].id)),
Some(expected[0].clone())
);
assert_eq!(
tab_index_map.prev(Some(&expected[2].id)),
Some(expected[1].clone())
);
assert_eq!(
tab_index_map.prev(Some(&expected[3].id)),
Some(expected[2].clone())
);
assert_eq!(
tab_index_map.prev(Some(&expected[4].id)),
Some(expected[3].clone())
);
}
#[test]
fn test_tab_non_stop_filtering() {
let focus_map = Arc::new(FocusMap::default());
let mut tab_index_map = TabStopMap::default();
let tab_non_stop_1 = FocusHandle::new(&focus_map).tab_stop(false).tab_index(1);
let tab_stop_2 = FocusHandle::new(&focus_map).tab_stop(true).tab_index(2);
tab_index_map.insert(&tab_non_stop_1);
tab_index_map.insert(&tab_stop_2);
let result = tab_index_map.next(Some(&tab_non_stop_1.id)).unwrap();
assert_eq!(result.id, tab_stop_2.id);
let tab_stop_0 = FocusHandle::new(&focus_map).tab_stop(true).tab_index(0);
let tab_non_stop_0 = FocusHandle::new(&focus_map).tab_stop(false).tab_index(0);
tab_index_map.insert(&tab_stop_0);
tab_index_map.insert(&tab_non_stop_0);
let result = tab_index_map.next(Some(&tab_stop_0.id)).unwrap();
assert_eq!(result.id, tab_stop_2.id);
}
#[must_use]
struct TabStopMapTest {
tab_map: TabStopMap,
focus_map: Arc<FocusMap>,
expected: Vec<(usize, FocusId)>,
}
impl TabStopMapTest {
#[must_use]
fn new() -> Self {
Self {
tab_map: TabStopMap::default(),
focus_map: Arc::new(FocusMap::default()),
expected: Vec::default(),
}
}
#[must_use]
fn tab_non_stop(mut self, index: isize) -> Self {
let handle = FocusHandle::new(&self.focus_map)
.tab_stop(false)
.tab_index(index);
self.tab_map.insert(&handle);
self
}
#[must_use]
fn tab_stop(mut self, index: isize, expected: usize) -> Self {
let handle = FocusHandle::new(&self.focus_map)
.tab_stop(true)
.tab_index(index);
self.tab_map.insert(&handle);
self.expected.push((expected, handle.id));
self.expected.sort_by_key(|(expected, _)| *expected);
self
}
#[must_use]
fn tab_group(mut self, tab_index: isize, children: impl FnOnce(Self) -> Self) -> Self {
self.tab_map.begin_group(tab_index);
self = children(self);
self.tab_map.end_group();
self
}
fn traverse_tab_map(
&self,
traverse: impl Fn(&TabStopMap, Option<&FocusId>) -> Option<FocusHandle>,
) -> Vec<FocusId> {
let mut last_focus_id = None;
let mut found = vec![];
for _ in 0..self.expected.len() {
let handle = traverse(&self.tab_map, last_focus_id.as_ref()).unwrap();
last_focus_id = Some(handle.id);
found.push(handle.id);
}
found
}
fn assert(self) {
let mut expected = self.expected.iter().map(|(_, id)| *id).collect_vec();
let forward_found = self.traverse_tab_map(|tab_map, prev| tab_map.next(prev));
assert_eq!(forward_found, expected);
assert_eq!(
self.tab_map
.next(forward_found.last())
.map(|handle| handle.id),
expected.first().cloned()
);
let reversed_found = self.traverse_tab_map(|tab_map, prev| tab_map.prev(prev));
expected.reverse();
assert_eq!(reversed_found, expected);
assert_eq!(
self.tab_map
.prev(reversed_found.last())
.map(|handle| handle.id),
expected.first().cloned(),
);
}
}
#[test]
fn test_with_disabled_tab_stop() {
TabStopMapTest::new()
.tab_stop(0, 0)
.tab_non_stop(1)
.tab_stop(2, 1)
.tab_stop(3, 2)
.assert();
}
#[test]
fn test_with_multiple_disabled_tab_stops() {
TabStopMapTest::new()
.tab_non_stop(0)
.tab_stop(1, 0)
.tab_non_stop(3)
.tab_stop(3, 1)
.tab_non_stop(4)
.assert();
}
#[test]
fn test_tab_group_functionality() {
TabStopMapTest::new()
.tab_stop(0, 0)
.tab_stop(0, 1)
.tab_group(2, |t| t.tab_stop(0, 2).tab_stop(1, 3))
.tab_stop(3, 4)
.tab_stop(4, 5)
.assert()
}
#[test]
fn test_sibling_groups() {
TabStopMapTest::new()
.tab_stop(0, 0)
.tab_stop(1, 1)
.tab_group(2, |test| test.tab_stop(0, 2).tab_stop(1, 3))
.tab_stop(3, 4)
.tab_stop(4, 5)
.tab_group(6, |test| test.tab_stop(0, 6).tab_stop(1, 7))
.tab_stop(7, 8)
.tab_stop(8, 9)
.assert();
}
#[test]
fn test_nested_group() {
TabStopMapTest::new()
.tab_stop(0, 0)
.tab_stop(1, 1)
.tab_group(2, |t| {
t.tab_group(0, |t| t.tab_stop(0, 2).tab_stop(1, 3))
.tab_stop(1, 4)
})
.tab_stop(3, 5)
.tab_stop(4, 6)
.assert();
}
#[test]
fn test_sibling_nested_groups() {
TabStopMapTest::new()
.tab_stop(0, 0)
.tab_stop(1, 1)
.tab_group(2, |builder| {
builder
.tab_stop(0, 2)
.tab_stop(2, 5)
.tab_group(1, |builder| builder.tab_stop(0, 3).tab_stop(1, 4))
.tab_group(3, |builder| builder.tab_stop(0, 6).tab_stop(1, 7))
})
.tab_stop(3, 8)
.tab_stop(4, 9)
.assert();
}
#[test]
fn test_sibling_nested_groups_out_of_order() {
TabStopMapTest::new()
.tab_stop(9, 9)
.tab_stop(8, 8)
.tab_group(7, |builder| {
builder
.tab_stop(0, 2)
.tab_stop(2, 5)
.tab_group(3, |builder| builder.tab_stop(1, 7).tab_stop(0, 6))
.tab_group(1, |builder| builder.tab_stop(0, 3).tab_stop(1, 4))
})
.tab_stop(3, 0)
.tab_stop(4, 1)
.assert();
}
}