1use super::{Buffer, Content, Point, ToOffset};
2use anyhow::Result;
3use std::{cmp::Ordering, ops::Range};
4use sum_tree::{Bias, SumTree};
5
6#[derive(Clone, Eq, PartialEq, Debug, Hash)]
7pub struct Anchor {
8 pub full_offset: usize,
9 pub bias: Bias,
10 pub version: clock::Global,
11}
12
13#[derive(Clone)]
14pub struct AnchorMap<T> {
15 pub(crate) version: clock::Global,
16 pub(crate) entries: Vec<((usize, Bias), T)>,
17}
18
19#[derive(Clone)]
20pub struct AnchorSet(pub(crate) AnchorMap<()>);
21
22#[derive(Clone)]
23pub struct AnchorRangeMap<T> {
24 pub(crate) version: clock::Global,
25 pub(crate) entries: Vec<(Range<(usize, Bias)>, T)>,
26}
27
28#[derive(Clone)]
29pub struct AnchorRangeSet(pub(crate) AnchorRangeMap<()>);
30
31#[derive(Clone)]
32pub struct AnchorRangeMultimap<T: Clone> {
33 pub(crate) entries: SumTree<AnchorRangeMultimapEntry<T>>,
34 pub(crate) version: clock::Global,
35 pub(crate) start_bias: Bias,
36 pub(crate) end_bias: Bias,
37}
38
39#[derive(Clone)]
40pub(crate) struct AnchorRangeMultimapEntry<T> {
41 pub(crate) range: FullOffsetRange,
42 pub(crate) value: T,
43}
44
45#[derive(Clone, Debug)]
46pub(crate) struct FullOffsetRange {
47 pub(crate) start: usize,
48 pub(crate) end: usize,
49}
50
51#[derive(Clone, Debug)]
52pub(crate) struct AnchorRangeMultimapSummary {
53 start: usize,
54 end: usize,
55 min_start: usize,
56 max_end: usize,
57 count: usize,
58}
59
60impl Anchor {
61 pub fn min() -> Self {
62 Self {
63 full_offset: 0,
64 bias: Bias::Left,
65 version: Default::default(),
66 }
67 }
68
69 pub fn max() -> Self {
70 Self {
71 full_offset: usize::MAX,
72 bias: Bias::Right,
73 version: Default::default(),
74 }
75 }
76
77 pub fn cmp<'a>(&self, other: &Anchor, buffer: impl Into<Content<'a>>) -> Result<Ordering> {
78 let buffer = buffer.into();
79
80 if self == other {
81 return Ok(Ordering::Equal);
82 }
83
84 let offset_comparison = if self.version == other.version {
85 self.full_offset.cmp(&other.full_offset)
86 } else {
87 buffer
88 .full_offset_for_anchor(self)
89 .cmp(&buffer.full_offset_for_anchor(other))
90 };
91
92 Ok(offset_comparison.then_with(|| self.bias.cmp(&other.bias)))
93 }
94
95 pub fn bias_left(&self, buffer: &Buffer) -> Anchor {
96 if self.bias == Bias::Left {
97 self.clone()
98 } else {
99 buffer.anchor_before(self)
100 }
101 }
102
103 pub fn bias_right(&self, buffer: &Buffer) -> Anchor {
104 if self.bias == Bias::Right {
105 self.clone()
106 } else {
107 buffer.anchor_after(self)
108 }
109 }
110}
111
112impl<T> AnchorMap<T> {
113 pub fn to_points<'a>(
114 &'a self,
115 content: impl Into<Content<'a>> + 'a,
116 ) -> impl Iterator<Item = (Point, &'a T)> + 'a {
117 let content = content.into();
118 content
119 .summaries_for_anchors(self)
120 .map(move |(sum, value)| (sum.lines, value))
121 }
122
123 pub fn version(&self) -> &clock::Global {
124 &self.version
125 }
126}
127
128impl AnchorSet {
129 pub fn to_points<'a>(
130 &'a self,
131 content: impl Into<Content<'a>> + 'a,
132 ) -> impl Iterator<Item = Point> + 'a {
133 self.0.to_points(content).map(move |(point, _)| point)
134 }
135}
136
137impl<T> AnchorRangeMap<T> {
138 pub fn to_point_ranges<'a>(
139 &'a self,
140 content: impl Into<Content<'a>> + 'a,
141 ) -> impl Iterator<Item = (Range<Point>, &'a T)> + 'a {
142 let content = content.into();
143 content
144 .summaries_for_anchor_ranges(self)
145 .map(move |(range, value)| ((range.start.lines..range.end.lines), value))
146 }
147
148 pub fn version(&self) -> &clock::Global {
149 &self.version
150 }
151}
152
153impl AnchorRangeSet {
154 pub fn to_point_ranges<'a>(
155 &'a self,
156 content: impl Into<Content<'a>> + 'a,
157 ) -> impl Iterator<Item = Range<Point>> + 'a {
158 self.0.to_point_ranges(content).map(|(range, _)| range)
159 }
160
161 pub fn version(&self) -> &clock::Global {
162 self.0.version()
163 }
164}
165
166impl<T: Clone> Default for AnchorRangeMultimap<T> {
167 fn default() -> Self {
168 Self {
169 entries: Default::default(),
170 version: Default::default(),
171 start_bias: Bias::Left,
172 end_bias: Bias::Left,
173 }
174 }
175}
176
177impl<T: Clone> AnchorRangeMultimap<T> {
178 pub fn intersecting_point_ranges<'a, O>(
179 &'a self,
180 range: Range<O>,
181 content: Content<'a>,
182 inclusive: bool,
183 ) -> impl Iterator<Item = (usize, Range<Point>, &T)> + 'a
184 where
185 O: ToOffset,
186 {
187 use super::ToPoint as _;
188
189 let end_bias = if inclusive { Bias::Right } else { Bias::Left };
190 let range = range.start.to_full_offset(&content, Bias::Left)
191 ..range.end.to_full_offset(&content, end_bias);
192 let mut cursor = self.entries.filter::<_, usize>(
193 {
194 let content = content.clone();
195 let mut endpoint = Anchor {
196 full_offset: 0,
197 bias: Bias::Right,
198 version: self.version.clone(),
199 };
200 move |summary: &AnchorRangeMultimapSummary| {
201 endpoint.full_offset = summary.max_end;
202 endpoint.bias = self.end_bias;
203 let max_end = endpoint.to_full_offset(&content, self.end_bias);
204 let start_cmp = range.start.cmp(&max_end);
205
206 endpoint.full_offset = summary.min_start;
207 endpoint.bias = self.start_bias;
208 let min_start = endpoint.to_full_offset(&content, self.start_bias);
209 let end_cmp = range.end.cmp(&min_start);
210
211 if inclusive {
212 start_cmp <= Ordering::Equal && end_cmp >= Ordering::Equal
213 } else {
214 start_cmp == Ordering::Less && end_cmp == Ordering::Greater
215 }
216 }
217 },
218 &(),
219 );
220
221 std::iter::from_fn({
222 let mut endpoint = Anchor {
223 full_offset: 0,
224 bias: Bias::Left,
225 version: self.version.clone(),
226 };
227 move || {
228 if let Some(item) = cursor.item() {
229 let ix = *cursor.start();
230 endpoint.full_offset = item.range.start;
231 endpoint.bias = self.start_bias;
232 let start = endpoint.to_point(&content);
233 endpoint.full_offset = item.range.end;
234 endpoint.bias = self.end_bias;
235 let end = endpoint.to_point(&content);
236 let value = &item.value;
237 cursor.next(&());
238 Some((ix, start..end, value))
239 } else {
240 None
241 }
242 }
243 })
244 }
245}
246
247impl<T: Clone> sum_tree::Item for AnchorRangeMultimapEntry<T> {
248 type Summary = AnchorRangeMultimapSummary;
249
250 fn summary(&self) -> Self::Summary {
251 AnchorRangeMultimapSummary {
252 start: self.range.start,
253 end: self.range.end,
254 min_start: self.range.start,
255 max_end: self.range.end,
256 count: 1,
257 }
258 }
259}
260
261impl Default for AnchorRangeMultimapSummary {
262 fn default() -> Self {
263 Self {
264 start: 0,
265 end: usize::MAX,
266 min_start: usize::MAX,
267 max_end: 0,
268 count: 0,
269 }
270 }
271}
272
273impl sum_tree::Summary for AnchorRangeMultimapSummary {
274 type Context = ();
275
276 fn add_summary(&mut self, other: &Self, _: &Self::Context) {
277 self.min_start = self.min_start.min(other.min_start);
278 self.max_end = self.max_end.max(other.max_end);
279
280 #[cfg(debug_assertions)]
281 {
282 let start_comparison = self.start.cmp(&other.start);
283 assert!(start_comparison <= Ordering::Equal);
284 if start_comparison == Ordering::Equal {
285 assert!(self.end.cmp(&other.end) >= Ordering::Equal);
286 }
287 }
288
289 self.start = other.start;
290 self.end = other.end;
291 self.count += other.count;
292 }
293}
294
295impl Default for FullOffsetRange {
296 fn default() -> Self {
297 Self {
298 start: 0,
299 end: usize::MAX,
300 }
301 }
302}
303
304impl<'a> sum_tree::Dimension<'a, AnchorRangeMultimapSummary> for usize {
305 fn add_summary(&mut self, summary: &'a AnchorRangeMultimapSummary, _: &()) {
306 *self += summary.count;
307 }
308}
309
310impl<'a> sum_tree::Dimension<'a, AnchorRangeMultimapSummary> for FullOffsetRange {
311 fn add_summary(&mut self, summary: &'a AnchorRangeMultimapSummary, _: &()) {
312 self.start = summary.start;
313 self.end = summary.end;
314 }
315}
316
317impl<'a> sum_tree::SeekTarget<'a, AnchorRangeMultimapSummary, FullOffsetRange> for FullOffsetRange {
318 fn cmp(&self, cursor_location: &FullOffsetRange, _: &()) -> Ordering {
319 Ord::cmp(&self.start, &cursor_location.start)
320 .then_with(|| Ord::cmp(&cursor_location.end, &self.end))
321 }
322}
323
324pub trait AnchorRangeExt {
325 fn cmp<'a>(&self, b: &Range<Anchor>, buffer: impl Into<Content<'a>>) -> Result<Ordering>;
326}
327
328impl AnchorRangeExt for Range<Anchor> {
329 fn cmp<'a>(&self, other: &Range<Anchor>, buffer: impl Into<Content<'a>>) -> Result<Ordering> {
330 let buffer = buffer.into();
331 Ok(match self.start.cmp(&other.start, &buffer)? {
332 Ordering::Equal => other.end.cmp(&self.end, buffer)?,
333 ord @ _ => ord,
334 })
335 }
336}