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::ContextLessSummary for Locator {
 84    fn zero() -> Self {
 85        Default::default()
 86    }
 87
 88    fn add_summary(&mut self, summary: &Self) {
 89        self.assign(summary);
 90    }
 91}
 92
 93#[cfg(test)]
 94mod tests {
 95    use super::*;
 96    use rand::prelude::*;
 97    use std::mem;
 98
 99    #[gpui::test(iterations = 100)]
100    fn test_locators(mut rng: StdRng) {
101        let mut lhs = Default::default();
102        let mut rhs = Default::default();
103        while lhs == rhs {
104            lhs = Locator(
105                (0..rng.random_range(1..=5))
106                    .map(|_| rng.random_range(0..=100))
107                    .collect(),
108            );
109            rhs = Locator(
110                (0..rng.random_range(1..=5))
111                    .map(|_| rng.random_range(0..=100))
112                    .collect(),
113            );
114        }
115
116        if lhs > rhs {
117            mem::swap(&mut lhs, &mut rhs);
118        }
119
120        let middle = Locator::between(&lhs, &rhs);
121        assert!(middle > lhs);
122        assert!(middle < rhs);
123        for ix in 0..middle.0.len() - 1 {
124            assert!(
125                middle.0[ix] == *lhs.0.get(ix).unwrap_or(&0)
126                    || middle.0[ix] == *rhs.0.get(ix).unwrap_or(&0)
127            );
128        }
129    }
130}