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