1use super::{Buffer, Content, FromAnchor, FullOffset, Point, ToOffset};
2use anyhow::Result;
3use std::{
4 cmp::Ordering,
5 fmt::{Debug, Formatter},
6 ops::Range,
7};
8use sum_tree::{Bias, SumTree};
9
10#[derive(Clone, Eq, PartialEq, Debug, Hash)]
11pub struct Anchor {
12 pub full_offset: FullOffset,
13 pub bias: Bias,
14 pub version: clock::Global,
15}
16
17#[derive(Clone)]
18pub struct AnchorMap<T> {
19 pub(crate) version: clock::Global,
20 pub(crate) entries: Vec<((FullOffset, Bias), T)>,
21}
22
23#[derive(Clone)]
24pub struct AnchorSet(pub(crate) AnchorMap<()>);
25
26#[derive(Clone)]
27pub struct AnchorRangeMap<T> {
28 pub(crate) version: clock::Global,
29 pub(crate) entries: Vec<(Range<(FullOffset, Bias)>, T)>,
30}
31
32#[derive(Clone)]
33pub struct AnchorRangeSet(pub(crate) AnchorRangeMap<()>);
34
35#[derive(Clone)]
36pub struct AnchorRangeMultimap<T: Clone> {
37 pub(crate) entries: SumTree<AnchorRangeMultimapEntry<T>>,
38 pub(crate) version: clock::Global,
39 pub(crate) start_bias: Bias,
40 pub(crate) end_bias: Bias,
41}
42
43#[derive(Clone)]
44pub(crate) struct AnchorRangeMultimapEntry<T> {
45 pub(crate) range: FullOffsetRange,
46 pub(crate) value: T,
47}
48
49#[derive(Clone, Debug)]
50pub(crate) struct FullOffsetRange {
51 pub(crate) start: FullOffset,
52 pub(crate) end: FullOffset,
53}
54
55#[derive(Clone, Debug)]
56pub(crate) struct AnchorRangeMultimapSummary {
57 start: FullOffset,
58 end: FullOffset,
59 min_start: FullOffset,
60 max_end: FullOffset,
61 count: usize,
62}
63
64impl Anchor {
65 pub fn min() -> Self {
66 Self {
67 full_offset: FullOffset(0),
68 bias: Bias::Left,
69 version: Default::default(),
70 }
71 }
72
73 pub fn max() -> Self {
74 Self {
75 full_offset: FullOffset::MAX,
76 bias: Bias::Right,
77 version: Default::default(),
78 }
79 }
80
81 pub fn cmp<'a>(&self, other: &Anchor, buffer: impl Into<Content<'a>>) -> Result<Ordering> {
82 let buffer = buffer.into();
83
84 if self == other {
85 return Ok(Ordering::Equal);
86 }
87
88 let offset_comparison = if self.version == other.version {
89 self.full_offset.cmp(&other.full_offset)
90 } else {
91 buffer
92 .full_offset_for_anchor(self)
93 .cmp(&buffer.full_offset_for_anchor(other))
94 };
95
96 Ok(offset_comparison.then_with(|| self.bias.cmp(&other.bias)))
97 }
98
99 pub fn bias_left(&self, buffer: &Buffer) -> Anchor {
100 if self.bias == Bias::Left {
101 self.clone()
102 } else {
103 buffer.anchor_before(self)
104 }
105 }
106
107 pub fn bias_right(&self, buffer: &Buffer) -> Anchor {
108 if self.bias == Bias::Right {
109 self.clone()
110 } else {
111 buffer.anchor_after(self)
112 }
113 }
114}
115
116impl<T> AnchorMap<T> {
117 pub fn version(&self) -> &clock::Global {
118 &self.version
119 }
120
121 pub fn len(&self) -> usize {
122 self.entries.len()
123 }
124
125 pub fn offsets<'a>(
126 &'a self,
127 content: impl Into<Content<'a>> + 'a,
128 ) -> impl Iterator<Item = (usize, &'a T)> + 'a {
129 let content = content.into();
130 content
131 .summaries_for_anchors(self)
132 .map(move |(sum, value)| (sum.bytes, value))
133 }
134
135 pub fn points<'a>(
136 &'a self,
137 content: impl Into<Content<'a>> + 'a,
138 ) -> impl Iterator<Item = (Point, &'a T)> + 'a {
139 let content = content.into();
140 content
141 .summaries_for_anchors(self)
142 .map(move |(sum, value)| (sum.lines, value))
143 }
144}
145
146impl AnchorSet {
147 pub fn version(&self) -> &clock::Global {
148 &self.0.version
149 }
150
151 pub fn len(&self) -> usize {
152 self.0.len()
153 }
154
155 pub fn offsets<'a>(
156 &'a self,
157 content: impl Into<Content<'a>> + 'a,
158 ) -> impl Iterator<Item = usize> + 'a {
159 self.0.offsets(content).map(|(offset, _)| offset)
160 }
161
162 pub fn points<'a>(
163 &'a self,
164 content: impl Into<Content<'a>> + 'a,
165 ) -> impl Iterator<Item = Point> + 'a {
166 self.0.points(content).map(|(point, _)| point)
167 }
168}
169
170impl<T> AnchorRangeMap<T> {
171 pub fn version(&self) -> &clock::Global {
172 &self.version
173 }
174
175 pub fn len(&self) -> usize {
176 self.entries.len()
177 }
178
179 pub fn from_full_offset_ranges(
180 version: clock::Global,
181 entries: Vec<(Range<(FullOffset, Bias)>, T)>,
182 ) -> Self {
183 Self { version, entries }
184 }
185
186 pub fn full_offset_ranges(&self) -> impl Iterator<Item = (Range<FullOffset>, &T)> {
187 self.entries
188 .iter()
189 .map(|(range, value)| (range.start.0..range.end.0, value))
190 }
191
192 pub fn point_ranges<'a>(
193 &'a self,
194 content: impl Into<Content<'a>> + 'a,
195 ) -> impl Iterator<Item = (Range<Point>, &'a T)> + 'a {
196 let content = content.into();
197 content
198 .summaries_for_anchor_ranges(self)
199 .map(move |(range, value)| ((range.start.lines..range.end.lines), value))
200 }
201
202 pub fn offset_ranges<'a>(
203 &'a self,
204 content: impl Into<Content<'a>> + 'a,
205 ) -> impl Iterator<Item = (Range<usize>, &'a T)> + 'a {
206 let content = content.into();
207 content
208 .summaries_for_anchor_ranges(self)
209 .map(move |(range, value)| ((range.start.bytes..range.end.bytes), value))
210 }
211}
212
213impl<T: PartialEq> PartialEq for AnchorRangeMap<T> {
214 fn eq(&self, other: &Self) -> bool {
215 self.version == other.version && self.entries == other.entries
216 }
217}
218
219impl<T: Eq> Eq for AnchorRangeMap<T> {}
220
221impl<T: Debug> Debug for AnchorRangeMap<T> {
222 fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), std::fmt::Error> {
223 let mut f = f.debug_map();
224 for (range, value) in &self.entries {
225 f.key(range);
226 f.value(value);
227 }
228 f.finish()
229 }
230}
231
232impl Debug for AnchorRangeSet {
233 fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
234 let mut f = f.debug_set();
235 for (range, _) in &self.0.entries {
236 f.entry(range);
237 }
238 f.finish()
239 }
240}
241
242impl AnchorRangeSet {
243 pub fn len(&self) -> usize {
244 self.0.len()
245 }
246
247 pub fn version(&self) -> &clock::Global {
248 self.0.version()
249 }
250
251 pub fn offset_ranges<'a>(
252 &'a self,
253 content: impl Into<Content<'a>> + 'a,
254 ) -> impl Iterator<Item = Range<usize>> + 'a {
255 self.0.offset_ranges(content).map(|(range, _)| range)
256 }
257
258 pub fn point_ranges<'a>(
259 &'a self,
260 content: impl Into<Content<'a>> + 'a,
261 ) -> impl Iterator<Item = Range<Point>> + 'a {
262 self.0.point_ranges(content).map(|(range, _)| range)
263 }
264}
265
266impl<T: Clone> Default for AnchorRangeMultimap<T> {
267 fn default() -> Self {
268 Self {
269 entries: Default::default(),
270 version: Default::default(),
271 start_bias: Bias::Left,
272 end_bias: Bias::Left,
273 }
274 }
275}
276
277impl<T: Clone> AnchorRangeMultimap<T> {
278 pub fn version(&self) -> &clock::Global {
279 &self.version
280 }
281
282 pub fn intersecting_ranges<'a, I, O>(
283 &'a self,
284 range: Range<I>,
285 content: Content<'a>,
286 inclusive: bool,
287 ) -> impl Iterator<Item = (usize, Range<O>, &T)> + 'a
288 where
289 I: ToOffset,
290 O: FromAnchor,
291 {
292 let end_bias = if inclusive { Bias::Right } else { Bias::Left };
293 let range = range.start.to_full_offset(&content, Bias::Left)
294 ..range.end.to_full_offset(&content, end_bias);
295 let mut cursor = self.entries.filter::<_, usize>(
296 {
297 let content = content.clone();
298 let mut endpoint = Anchor {
299 full_offset: FullOffset(0),
300 bias: Bias::Right,
301 version: self.version.clone(),
302 };
303 move |summary: &AnchorRangeMultimapSummary| {
304 endpoint.full_offset = summary.max_end;
305 endpoint.bias = self.end_bias;
306 let max_end = endpoint.to_full_offset(&content, self.end_bias);
307 let start_cmp = range.start.cmp(&max_end);
308
309 endpoint.full_offset = summary.min_start;
310 endpoint.bias = self.start_bias;
311 let min_start = endpoint.to_full_offset(&content, self.start_bias);
312 let end_cmp = range.end.cmp(&min_start);
313
314 if inclusive {
315 start_cmp <= Ordering::Equal && end_cmp >= Ordering::Equal
316 } else {
317 start_cmp == Ordering::Less && end_cmp == Ordering::Greater
318 }
319 }
320 },
321 &(),
322 );
323
324 std::iter::from_fn({
325 let mut endpoint = Anchor {
326 full_offset: FullOffset(0),
327 bias: Bias::Left,
328 version: self.version.clone(),
329 };
330 move || {
331 if let Some(item) = cursor.item() {
332 let ix = *cursor.start();
333 endpoint.full_offset = item.range.start;
334 endpoint.bias = self.start_bias;
335 let start = O::from_anchor(&endpoint, &content);
336 endpoint.full_offset = item.range.end;
337 endpoint.bias = self.end_bias;
338 let end = O::from_anchor(&endpoint, &content);
339 let value = &item.value;
340 cursor.next(&());
341 Some((ix, start..end, value))
342 } else {
343 None
344 }
345 }
346 })
347 }
348
349 pub fn from_full_offset_ranges(
350 version: clock::Global,
351 start_bias: Bias,
352 end_bias: Bias,
353 entries: impl Iterator<Item = (Range<FullOffset>, T)>,
354 ) -> Self {
355 Self {
356 version,
357 start_bias,
358 end_bias,
359 entries: SumTree::from_iter(
360 entries.map(|(range, value)| AnchorRangeMultimapEntry {
361 range: FullOffsetRange {
362 start: range.start,
363 end: range.end,
364 },
365 value,
366 }),
367 &(),
368 ),
369 }
370 }
371
372 pub fn full_offset_ranges(&self) -> impl Iterator<Item = (Range<FullOffset>, &T)> {
373 self.entries
374 .cursor::<()>()
375 .map(|entry| (entry.range.start..entry.range.end, &entry.value))
376 }
377}
378
379impl<T: Clone> sum_tree::Item for AnchorRangeMultimapEntry<T> {
380 type Summary = AnchorRangeMultimapSummary;
381
382 fn summary(&self) -> Self::Summary {
383 AnchorRangeMultimapSummary {
384 start: self.range.start,
385 end: self.range.end,
386 min_start: self.range.start,
387 max_end: self.range.end,
388 count: 1,
389 }
390 }
391}
392
393impl Default for AnchorRangeMultimapSummary {
394 fn default() -> Self {
395 Self {
396 start: FullOffset(0),
397 end: FullOffset::MAX,
398 min_start: FullOffset::MAX,
399 max_end: FullOffset(0),
400 count: 0,
401 }
402 }
403}
404
405impl sum_tree::Summary for AnchorRangeMultimapSummary {
406 type Context = ();
407
408 fn add_summary(&mut self, other: &Self, _: &Self::Context) {
409 self.min_start = self.min_start.min(other.min_start);
410 self.max_end = self.max_end.max(other.max_end);
411
412 #[cfg(debug_assertions)]
413 {
414 let start_comparison = self.start.cmp(&other.start);
415 assert!(start_comparison <= Ordering::Equal);
416 if start_comparison == Ordering::Equal {
417 assert!(self.end.cmp(&other.end) >= Ordering::Equal);
418 }
419 }
420
421 self.start = other.start;
422 self.end = other.end;
423 self.count += other.count;
424 }
425}
426
427impl Default for FullOffsetRange {
428 fn default() -> Self {
429 Self {
430 start: FullOffset(0),
431 end: FullOffset::MAX,
432 }
433 }
434}
435
436impl<'a> sum_tree::Dimension<'a, AnchorRangeMultimapSummary> for usize {
437 fn add_summary(&mut self, summary: &'a AnchorRangeMultimapSummary, _: &()) {
438 *self += summary.count;
439 }
440}
441
442impl<'a> sum_tree::Dimension<'a, AnchorRangeMultimapSummary> for FullOffsetRange {
443 fn add_summary(&mut self, summary: &'a AnchorRangeMultimapSummary, _: &()) {
444 self.start = summary.start;
445 self.end = summary.end;
446 }
447}
448
449impl<'a> sum_tree::SeekTarget<'a, AnchorRangeMultimapSummary, FullOffsetRange> for FullOffsetRange {
450 fn cmp(&self, cursor_location: &FullOffsetRange, _: &()) -> Ordering {
451 Ord::cmp(&self.start, &cursor_location.start)
452 .then_with(|| Ord::cmp(&cursor_location.end, &self.end))
453 }
454}
455
456pub trait AnchorRangeExt {
457 fn cmp<'a>(&self, b: &Range<Anchor>, buffer: impl Into<Content<'a>>) -> Result<Ordering>;
458}
459
460impl AnchorRangeExt for Range<Anchor> {
461 fn cmp<'a>(&self, other: &Range<Anchor>, buffer: impl Into<Content<'a>>) -> Result<Ordering> {
462 let buffer = buffer.into();
463 Ok(match self.start.cmp(&other.start, &buffer)? {
464 Ordering::Equal => other.end.cmp(&self.end, buffer)?,
465 ord @ _ => ord,
466 })
467 }
468}