1use smallvec::SmallVec;
2use std::iter;
3
4/// An identifier for a position in a ordered collection.
5///
6/// Allows prepending and appending without needing to renumber existing locators
7/// using `Locator::between(lhs, rhs)`.
8///
9/// The initial location for a collection should be `Locator::between(Locator::min(), Locator::max())`,
10/// leaving room for items to be inserted before and after it.
11#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
12pub struct Locator(SmallVec<[u64; 4]>);
13
14impl Locator {
15 pub const fn min() -> Self {
16 // SAFETY: 1 is <= 4
17 Self(unsafe { SmallVec::from_const_with_len_unchecked([u64::MIN; 4], 1) })
18 }
19
20 pub const fn max() -> Self {
21 // SAFETY: 1 is <= 4
22 Self(unsafe { SmallVec::from_const_with_len_unchecked([u64::MAX; 4], 1) })
23 }
24
25 pub const fn min_ref() -> &'static Self {
26 const { &Self::min() }
27 }
28
29 pub const fn max_ref() -> &'static Self {
30 const { &Self::max() }
31 }
32
33 pub fn assign(&mut self, other: &Self) {
34 self.0.resize(other.0.len(), 0);
35 self.0.copy_from_slice(&other.0);
36 }
37
38 pub fn between(lhs: &Self, rhs: &Self) -> Self {
39 let lhs = lhs.0.iter().copied().chain(iter::repeat(u64::MIN));
40 let rhs = rhs.0.iter().copied().chain(iter::repeat(u64::MAX));
41 let mut location = SmallVec::new();
42 for (lhs, rhs) in lhs.zip(rhs) {
43 let mid = lhs + ((rhs.saturating_sub(lhs)) >> 48);
44 location.push(mid);
45 if mid > lhs {
46 break;
47 }
48 }
49 Self(location)
50 }
51
52 pub fn len(&self) -> usize {
53 self.0.len()
54 }
55
56 pub fn is_empty(&self) -> bool {
57 self.len() == 0
58 }
59}
60
61impl Default for Locator {
62 fn default() -> Self {
63 Self::min()
64 }
65}
66
67impl sum_tree::Item for Locator {
68 type Summary = Locator;
69
70 fn summary(&self, _cx: &()) -> Self::Summary {
71 self.clone()
72 }
73}
74
75impl sum_tree::KeyedItem for Locator {
76 type Key = Locator;
77
78 fn key(&self) -> Self::Key {
79 self.clone()
80 }
81}
82
83impl sum_tree::Summary for Locator {
84 type Context = ();
85
86 fn zero(_cx: &()) -> Self {
87 Default::default()
88 }
89
90 fn add_summary(&mut self, summary: &Self, _: &()) {
91 self.assign(summary);
92 }
93}
94
95#[cfg(test)]
96mod tests {
97 use super::*;
98 use rand::prelude::*;
99 use std::mem;
100
101 #[gpui::test(iterations = 100)]
102 fn test_locators(mut rng: StdRng) {
103 let mut lhs = Default::default();
104 let mut rhs = Default::default();
105 while lhs == rhs {
106 lhs = Locator(
107 (0..rng.random_range(1..=5))
108 .map(|_| rng.random_range(0..=100))
109 .collect(),
110 );
111 rhs = Locator(
112 (0..rng.random_range(1..=5))
113 .map(|_| rng.random_range(0..=100))
114 .collect(),
115 );
116 }
117
118 if lhs > rhs {
119 mem::swap(&mut lhs, &mut rhs);
120 }
121
122 let middle = Locator::between(&lhs, &rhs);
123 assert!(middle > lhs);
124 assert!(middle < rhs);
125 for ix in 0..middle.0.len() - 1 {
126 assert!(
127 middle.0[ix] == *lhs.0.get(ix).unwrap_or(&0)
128 || middle.0[ix] == *rhs.0.get(ix).unwrap_or(&0)
129 );
130 }
131 }
132}