1use crate::{rope::TextDimension, BufferSnapshot};
2
3use super::{Buffer, FromAnchor, FullOffset, Point, ToOffset};
4use anyhow::Result;
5use std::{
6 cmp::Ordering,
7 fmt::{Debug, Formatter},
8 ops::Range,
9};
10use sum_tree::{Bias, SumTree};
11
12#[derive(Clone, Eq, PartialEq, Debug, Hash)]
13pub struct Anchor {
14 pub full_offset: FullOffset,
15 pub bias: Bias,
16 pub version: clock::Global,
17}
18
19#[derive(Clone)]
20pub struct AnchorMap<T> {
21 pub(crate) version: clock::Global,
22 pub(crate) bias: Bias,
23 pub(crate) entries: Vec<(FullOffset, T)>,
24}
25
26#[derive(Clone)]
27pub struct AnchorSet(pub(crate) AnchorMap<()>);
28
29#[derive(Clone)]
30pub struct AnchorRangeMap<T> {
31 pub(crate) version: clock::Global,
32 pub(crate) entries: Vec<(Range<FullOffset>, T)>,
33 pub(crate) start_bias: Bias,
34 pub(crate) end_bias: Bias,
35}
36
37#[derive(Clone)]
38pub struct AnchorRangeSet(pub(crate) AnchorRangeMap<()>);
39
40#[derive(Clone)]
41pub struct AnchorRangeMultimap<T: Clone> {
42 pub(crate) entries: SumTree<AnchorRangeMultimapEntry<T>>,
43 pub(crate) version: clock::Global,
44 pub(crate) start_bias: Bias,
45 pub(crate) end_bias: Bias,
46}
47
48#[derive(Clone)]
49pub(crate) struct AnchorRangeMultimapEntry<T> {
50 pub(crate) range: FullOffsetRange,
51 pub(crate) value: T,
52}
53
54#[derive(Clone, Debug)]
55pub(crate) struct FullOffsetRange {
56 pub(crate) start: FullOffset,
57 pub(crate) end: FullOffset,
58}
59
60#[derive(Clone, Debug)]
61pub(crate) struct AnchorRangeMultimapSummary {
62 start: FullOffset,
63 end: FullOffset,
64 min_start: FullOffset,
65 max_end: FullOffset,
66 count: usize,
67}
68
69impl Anchor {
70 pub fn min() -> Self {
71 Self {
72 full_offset: FullOffset(0),
73 bias: Bias::Left,
74 version: Default::default(),
75 }
76 }
77
78 pub fn max() -> Self {
79 Self {
80 full_offset: FullOffset::MAX,
81 bias: Bias::Right,
82 version: Default::default(),
83 }
84 }
85
86 pub fn cmp<'a>(&self, other: &Anchor, buffer: &BufferSnapshot) -> Result<Ordering> {
87 if self == other {
88 return Ok(Ordering::Equal);
89 }
90
91 let offset_comparison = if self.version == other.version {
92 self.full_offset.cmp(&other.full_offset)
93 } else {
94 buffer
95 .full_offset_for_anchor(self)
96 .cmp(&buffer.full_offset_for_anchor(other))
97 };
98
99 Ok(offset_comparison.then_with(|| self.bias.cmp(&other.bias)))
100 }
101
102 pub fn bias_left(&self, buffer: &Buffer) -> Anchor {
103 if self.bias == Bias::Left {
104 self.clone()
105 } else {
106 buffer.anchor_before(self)
107 }
108 }
109
110 pub fn bias_right(&self, buffer: &Buffer) -> Anchor {
111 if self.bias == Bias::Right {
112 self.clone()
113 } else {
114 buffer.anchor_after(self)
115 }
116 }
117
118 pub fn summary<'a, D>(&self, content: &'a BufferSnapshot) -> D
119 where
120 D: TextDimension,
121 {
122 content.summary_for_anchor(self)
123 }
124}
125
126impl<T> AnchorMap<T> {
127 pub fn version(&self) -> &clock::Global {
128 &self.version
129 }
130
131 pub fn len(&self) -> usize {
132 self.entries.len()
133 }
134
135 pub fn iter<'a, D>(
136 &'a self,
137 snapshot: &'a BufferSnapshot,
138 ) -> impl Iterator<Item = (D, &'a T)> + 'a
139 where
140 D: TextDimension,
141 {
142 snapshot
143 .summaries_for_anchors(
144 self.version.clone(),
145 self.bias,
146 self.entries.iter().map(|e| &e.0),
147 )
148 .zip(self.entries.iter().map(|e| &e.1))
149 }
150}
151
152impl AnchorSet {
153 pub fn version(&self) -> &clock::Global {
154 &self.0.version
155 }
156
157 pub fn len(&self) -> usize {
158 self.0.len()
159 }
160
161 pub fn iter<'a, D>(&'a self, content: &'a BufferSnapshot) -> impl Iterator<Item = D> + 'a
162 where
163 D: TextDimension,
164 {
165 self.0.iter(content).map(|(position, _)| position)
166 }
167}
168
169impl<T> AnchorRangeMap<T> {
170 pub fn version(&self) -> &clock::Global {
171 &self.version
172 }
173
174 pub fn len(&self) -> usize {
175 self.entries.len()
176 }
177
178 pub fn from_full_offset_ranges(
179 version: clock::Global,
180 start_bias: Bias,
181 end_bias: Bias,
182 entries: Vec<(Range<FullOffset>, T)>,
183 ) -> Self {
184 Self {
185 version,
186 start_bias,
187 end_bias,
188 entries,
189 }
190 }
191
192 pub fn ranges<'a, D>(
193 &'a self,
194 content: &'a BufferSnapshot,
195 ) -> impl Iterator<Item = (Range<D>, &'a T)> + 'a
196 where
197 D: TextDimension,
198 {
199 content
200 .summaries_for_anchor_ranges(
201 self.version.clone(),
202 self.start_bias,
203 self.end_bias,
204 self.entries.iter().map(|e| &e.0),
205 )
206 .zip(self.entries.iter().map(|e| &e.1))
207 }
208
209 pub fn intersecting_ranges<'a, D, I>(
210 &'a self,
211 range: Range<(I, Bias)>,
212 content: &'a BufferSnapshot,
213 ) -> impl Iterator<Item = (Range<D>, &'a T)> + 'a
214 where
215 D: TextDimension,
216 I: ToOffset,
217 {
218 let range = content.anchor_at(range.start.0, range.start.1)
219 ..content.anchor_at(range.end.0, range.end.1);
220
221 let mut probe_anchor = Anchor {
222 full_offset: Default::default(),
223 bias: self.start_bias,
224 version: self.version.clone(),
225 };
226 let start_ix = self.entries.binary_search_by(|probe| {
227 probe_anchor.full_offset = probe.0.end;
228 probe_anchor.cmp(&range.start, &content).unwrap()
229 });
230
231 match start_ix {
232 Ok(start_ix) | Err(start_ix) => content
233 .summaries_for_anchor_ranges(
234 self.version.clone(),
235 self.start_bias,
236 self.end_bias,
237 self.entries[start_ix..].iter().map(|e| &e.0),
238 )
239 .zip(self.entries.iter().map(|e| &e.1)),
240 }
241 }
242
243 pub fn full_offset_ranges(&self) -> impl Iterator<Item = &(Range<FullOffset>, T)> {
244 self.entries.iter()
245 }
246
247 pub fn min_by_key<'a, D, F, K>(
248 &self,
249 content: &'a BufferSnapshot,
250 mut extract_key: F,
251 ) -> Option<(Range<D>, &T)>
252 where
253 D: TextDimension,
254 F: FnMut(&T) -> K,
255 K: Ord,
256 {
257 self.entries
258 .iter()
259 .min_by_key(|(_, value)| extract_key(value))
260 .map(|(range, value)| (self.resolve_range(range, &content), value))
261 }
262
263 pub fn max_by_key<'a, D, F, K>(
264 &self,
265 content: &'a BufferSnapshot,
266 mut extract_key: F,
267 ) -> Option<(Range<D>, &T)>
268 where
269 D: TextDimension,
270 F: FnMut(&T) -> K,
271 K: Ord,
272 {
273 self.entries
274 .iter()
275 .max_by_key(|(_, value)| extract_key(value))
276 .map(|(range, value)| (self.resolve_range(range, &content), value))
277 }
278
279 fn resolve_range<'a, D>(
280 &self,
281 range: &Range<FullOffset>,
282 content: &'a BufferSnapshot,
283 ) -> Range<D>
284 where
285 D: TextDimension,
286 {
287 let mut anchor = Anchor {
288 full_offset: range.start,
289 bias: self.start_bias,
290 version: self.version.clone(),
291 };
292 let start = content.summary_for_anchor(&anchor);
293
294 anchor.full_offset = range.end;
295 anchor.bias = self.end_bias;
296 let end = content.summary_for_anchor(&anchor);
297
298 start..end
299 }
300}
301
302impl<T: PartialEq> PartialEq for AnchorRangeMap<T> {
303 fn eq(&self, other: &Self) -> bool {
304 self.version == other.version && self.entries == other.entries
305 }
306}
307
308impl<T: Eq> Eq for AnchorRangeMap<T> {}
309
310impl<T: Debug> Debug for AnchorRangeMap<T> {
311 fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), std::fmt::Error> {
312 let mut f = f.debug_map();
313 for (range, value) in &self.entries {
314 f.key(range);
315 f.value(value);
316 }
317 f.finish()
318 }
319}
320
321impl Debug for AnchorRangeSet {
322 fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
323 let mut f = f.debug_set();
324 for (range, _) in &self.0.entries {
325 f.entry(range);
326 }
327 f.finish()
328 }
329}
330
331impl AnchorRangeSet {
332 pub fn len(&self) -> usize {
333 self.0.len()
334 }
335
336 pub fn version(&self) -> &clock::Global {
337 self.0.version()
338 }
339
340 pub fn ranges<'a, D>(
341 &'a self,
342 content: &'a BufferSnapshot,
343 ) -> impl 'a + Iterator<Item = Range<Point>>
344 where
345 D: TextDimension,
346 {
347 self.0.ranges(content).map(|(range, _)| range)
348 }
349}
350
351impl<T: Clone> Default for AnchorRangeMultimap<T> {
352 fn default() -> Self {
353 Self {
354 entries: Default::default(),
355 version: Default::default(),
356 start_bias: Bias::Left,
357 end_bias: Bias::Left,
358 }
359 }
360}
361
362impl<T: Clone> AnchorRangeMultimap<T> {
363 pub fn version(&self) -> &clock::Global {
364 &self.version
365 }
366
367 pub fn intersecting_ranges<'a, I, O>(
368 &'a self,
369 range: Range<I>,
370 content: &'a BufferSnapshot,
371 inclusive: bool,
372 ) -> impl Iterator<Item = (usize, Range<O>, &T)> + 'a
373 where
374 I: ToOffset,
375 O: FromAnchor,
376 {
377 let end_bias = if inclusive { Bias::Right } else { Bias::Left };
378 let range = range.start.to_full_offset(&content, Bias::Left)
379 ..range.end.to_full_offset(&content, end_bias);
380 let mut cursor = self.entries.filter::<_, usize>(
381 {
382 let mut endpoint = Anchor {
383 full_offset: FullOffset(0),
384 bias: Bias::Right,
385 version: self.version.clone(),
386 };
387 move |summary: &AnchorRangeMultimapSummary| {
388 endpoint.full_offset = summary.max_end;
389 endpoint.bias = self.end_bias;
390 let max_end = endpoint.to_full_offset(&content, self.end_bias);
391 let start_cmp = range.start.cmp(&max_end);
392
393 endpoint.full_offset = summary.min_start;
394 endpoint.bias = self.start_bias;
395 let min_start = endpoint.to_full_offset(&content, self.start_bias);
396 let end_cmp = range.end.cmp(&min_start);
397
398 if inclusive {
399 start_cmp <= Ordering::Equal && end_cmp >= Ordering::Equal
400 } else {
401 start_cmp == Ordering::Less && end_cmp == Ordering::Greater
402 }
403 }
404 },
405 &(),
406 );
407
408 std::iter::from_fn({
409 let mut endpoint = Anchor {
410 full_offset: FullOffset(0),
411 bias: Bias::Left,
412 version: self.version.clone(),
413 };
414 move || {
415 if let Some(item) = cursor.item() {
416 let ix = *cursor.start();
417 endpoint.full_offset = item.range.start;
418 endpoint.bias = self.start_bias;
419 let start = O::from_anchor(&endpoint, &content);
420 endpoint.full_offset = item.range.end;
421 endpoint.bias = self.end_bias;
422 let end = O::from_anchor(&endpoint, &content);
423 let value = &item.value;
424 cursor.next(&());
425 Some((ix, start..end, value))
426 } else {
427 None
428 }
429 }
430 })
431 }
432
433 pub fn from_full_offset_ranges(
434 version: clock::Global,
435 start_bias: Bias,
436 end_bias: Bias,
437 entries: impl Iterator<Item = (Range<FullOffset>, T)>,
438 ) -> Self {
439 Self {
440 version,
441 start_bias,
442 end_bias,
443 entries: SumTree::from_iter(
444 entries.map(|(range, value)| AnchorRangeMultimapEntry {
445 range: FullOffsetRange {
446 start: range.start,
447 end: range.end,
448 },
449 value,
450 }),
451 &(),
452 ),
453 }
454 }
455
456 pub fn full_offset_ranges(&self) -> impl Iterator<Item = (Range<FullOffset>, &T)> {
457 self.entries
458 .cursor::<()>()
459 .map(|entry| (entry.range.start..entry.range.end, &entry.value))
460 }
461
462 pub fn filter<'a, O, F>(
463 &'a self,
464 content: &'a BufferSnapshot,
465 mut f: F,
466 ) -> impl 'a + Iterator<Item = (usize, Range<O>, &T)>
467 where
468 O: FromAnchor,
469 F: 'a + FnMut(&'a T) -> bool,
470 {
471 let mut endpoint = Anchor {
472 full_offset: FullOffset(0),
473 bias: Bias::Left,
474 version: self.version.clone(),
475 };
476 self.entries
477 .cursor::<()>()
478 .enumerate()
479 .filter_map(move |(ix, entry)| {
480 if f(&entry.value) {
481 endpoint.full_offset = entry.range.start;
482 endpoint.bias = self.start_bias;
483 let start = O::from_anchor(&endpoint, &content);
484 endpoint.full_offset = entry.range.end;
485 endpoint.bias = self.end_bias;
486 let end = O::from_anchor(&endpoint, &content);
487 Some((ix, start..end, &entry.value))
488 } else {
489 None
490 }
491 })
492 }
493}
494
495impl<T: Clone> sum_tree::Item for AnchorRangeMultimapEntry<T> {
496 type Summary = AnchorRangeMultimapSummary;
497
498 fn summary(&self) -> Self::Summary {
499 AnchorRangeMultimapSummary {
500 start: self.range.start,
501 end: self.range.end,
502 min_start: self.range.start,
503 max_end: self.range.end,
504 count: 1,
505 }
506 }
507}
508
509impl Default for AnchorRangeMultimapSummary {
510 fn default() -> Self {
511 Self {
512 start: FullOffset(0),
513 end: FullOffset::MAX,
514 min_start: FullOffset::MAX,
515 max_end: FullOffset(0),
516 count: 0,
517 }
518 }
519}
520
521impl sum_tree::Summary for AnchorRangeMultimapSummary {
522 type Context = ();
523
524 fn add_summary(&mut self, other: &Self, _: &Self::Context) {
525 self.min_start = self.min_start.min(other.min_start);
526 self.max_end = self.max_end.max(other.max_end);
527
528 #[cfg(debug_assertions)]
529 {
530 let start_comparison = self.start.cmp(&other.start);
531 assert!(start_comparison <= Ordering::Equal);
532 if start_comparison == Ordering::Equal {
533 assert!(self.end.cmp(&other.end) >= Ordering::Equal);
534 }
535 }
536
537 self.start = other.start;
538 self.end = other.end;
539 self.count += other.count;
540 }
541}
542
543impl Default for FullOffsetRange {
544 fn default() -> Self {
545 Self {
546 start: FullOffset(0),
547 end: FullOffset::MAX,
548 }
549 }
550}
551
552impl<'a> sum_tree::Dimension<'a, AnchorRangeMultimapSummary> for usize {
553 fn add_summary(&mut self, summary: &'a AnchorRangeMultimapSummary, _: &()) {
554 *self += summary.count;
555 }
556}
557
558impl<'a> sum_tree::Dimension<'a, AnchorRangeMultimapSummary> for FullOffsetRange {
559 fn add_summary(&mut self, summary: &'a AnchorRangeMultimapSummary, _: &()) {
560 self.start = summary.start;
561 self.end = summary.end;
562 }
563}
564
565impl<'a> sum_tree::SeekTarget<'a, AnchorRangeMultimapSummary, FullOffsetRange> for FullOffsetRange {
566 fn cmp(&self, cursor_location: &FullOffsetRange, _: &()) -> Ordering {
567 Ord::cmp(&self.start, &cursor_location.start)
568 .then_with(|| Ord::cmp(&cursor_location.end, &self.end))
569 }
570}
571
572pub trait AnchorRangeExt {
573 fn cmp(&self, b: &Range<Anchor>, buffer: &BufferSnapshot) -> Result<Ordering>;
574 fn to_offset(&self, content: &BufferSnapshot) -> Range<usize>;
575}
576
577impl AnchorRangeExt for Range<Anchor> {
578 fn cmp(&self, other: &Range<Anchor>, buffer: &BufferSnapshot) -> Result<Ordering> {
579 Ok(match self.start.cmp(&other.start, buffer)? {
580 Ordering::Equal => other.end.cmp(&self.end, buffer)?,
581 ord @ _ => ord,
582 })
583 }
584
585 fn to_offset(&self, content: &BufferSnapshot) -> Range<usize> {
586 self.start.to_offset(&content)..self.end.to_offset(&content)
587 }
588}