1use crate::{rope::TextDimension, Snapshot};
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: &Snapshot) -> 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 Snapshot) -> D
119 where
120 D: TextDimension<'a>,
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>(&'a self, snapshot: &'a Snapshot) -> impl Iterator<Item = (D, &'a T)> + 'a
136 where
137 D: 'a + TextDimension<'a>,
138 {
139 snapshot
140 .summaries_for_anchors(
141 self.version.clone(),
142 self.bias,
143 self.entries.iter().map(|e| &e.0),
144 )
145 .zip(self.entries.iter().map(|e| &e.1))
146 }
147}
148
149impl AnchorSet {
150 pub fn version(&self) -> &clock::Global {
151 &self.0.version
152 }
153
154 pub fn len(&self) -> usize {
155 self.0.len()
156 }
157
158 pub fn iter<'a, D>(&'a self, content: &'a Snapshot) -> impl Iterator<Item = D> + 'a
159 where
160 D: 'a + TextDimension<'a>,
161 {
162 self.0.iter(content).map(|(position, _)| position)
163 }
164}
165
166impl<T> AnchorRangeMap<T> {
167 pub fn version(&self) -> &clock::Global {
168 &self.version
169 }
170
171 pub fn len(&self) -> usize {
172 self.entries.len()
173 }
174
175 pub fn from_full_offset_ranges(
176 version: clock::Global,
177 start_bias: Bias,
178 end_bias: Bias,
179 entries: Vec<(Range<FullOffset>, T)>,
180 ) -> Self {
181 Self {
182 version,
183 start_bias,
184 end_bias,
185 entries,
186 }
187 }
188
189 pub fn ranges<'a, D>(
190 &'a self,
191 content: &'a Snapshot,
192 ) -> impl Iterator<Item = (Range<D>, &'a T)> + 'a
193 where
194 D: 'a + TextDimension<'a>,
195 {
196 content
197 .summaries_for_anchor_ranges(
198 self.version.clone(),
199 self.start_bias,
200 self.end_bias,
201 self.entries.iter().map(|e| &e.0),
202 )
203 .zip(self.entries.iter().map(|e| &e.1))
204 }
205
206 pub fn intersecting_ranges<'a, D, I>(
207 &'a self,
208 range: Range<(I, Bias)>,
209 content: &'a Snapshot,
210 ) -> impl Iterator<Item = (Range<D>, &'a T)> + 'a
211 where
212 D: 'a + TextDimension<'a>,
213 I: ToOffset,
214 {
215 let range = content.anchor_at(range.start.0, range.start.1)
216 ..content.anchor_at(range.end.0, range.end.1);
217
218 let mut probe_anchor = Anchor {
219 full_offset: Default::default(),
220 bias: self.start_bias,
221 version: self.version.clone(),
222 };
223 let start_ix = self.entries.binary_search_by(|probe| {
224 probe_anchor.full_offset = probe.0.end;
225 probe_anchor.cmp(&range.start, &content).unwrap()
226 });
227
228 match start_ix {
229 Ok(start_ix) | Err(start_ix) => content
230 .summaries_for_anchor_ranges(
231 self.version.clone(),
232 self.start_bias,
233 self.end_bias,
234 self.entries[start_ix..].iter().map(|e| &e.0),
235 )
236 .zip(self.entries.iter().map(|e| &e.1)),
237 }
238 }
239
240 pub fn full_offset_ranges(&self) -> impl Iterator<Item = &(Range<FullOffset>, T)> {
241 self.entries.iter()
242 }
243
244 pub fn min_by_key<'a, D, F, K>(
245 &self,
246 content: &'a Snapshot,
247 mut extract_key: F,
248 ) -> Option<(Range<D>, &T)>
249 where
250 D: 'a + TextDimension<'a>,
251 F: FnMut(&T) -> K,
252 K: Ord,
253 {
254 self.entries
255 .iter()
256 .min_by_key(|(_, value)| extract_key(value))
257 .map(|(range, value)| (self.resolve_range(range, &content), value))
258 }
259
260 pub fn max_by_key<'a, D, F, K>(
261 &self,
262 content: &'a Snapshot,
263 mut extract_key: F,
264 ) -> Option<(Range<D>, &T)>
265 where
266 D: 'a + TextDimension<'a>,
267 F: FnMut(&T) -> K,
268 K: Ord,
269 {
270 self.entries
271 .iter()
272 .max_by_key(|(_, value)| extract_key(value))
273 .map(|(range, value)| (self.resolve_range(range, &content), value))
274 }
275
276 fn resolve_range<'a, D>(&self, range: &Range<FullOffset>, content: &'a Snapshot) -> Range<D>
277 where
278 D: 'a + TextDimension<'a>,
279 {
280 let mut anchor = Anchor {
281 full_offset: range.start,
282 bias: self.start_bias,
283 version: self.version.clone(),
284 };
285 let start = content.summary_for_anchor(&anchor);
286
287 anchor.full_offset = range.end;
288 anchor.bias = self.end_bias;
289 let end = content.summary_for_anchor(&anchor);
290
291 start..end
292 }
293}
294
295impl<T: PartialEq> PartialEq for AnchorRangeMap<T> {
296 fn eq(&self, other: &Self) -> bool {
297 self.version == other.version && self.entries == other.entries
298 }
299}
300
301impl<T: Eq> Eq for AnchorRangeMap<T> {}
302
303impl<T: Debug> Debug for AnchorRangeMap<T> {
304 fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), std::fmt::Error> {
305 let mut f = f.debug_map();
306 for (range, value) in &self.entries {
307 f.key(range);
308 f.value(value);
309 }
310 f.finish()
311 }
312}
313
314impl Debug for AnchorRangeSet {
315 fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
316 let mut f = f.debug_set();
317 for (range, _) in &self.0.entries {
318 f.entry(range);
319 }
320 f.finish()
321 }
322}
323
324impl AnchorRangeSet {
325 pub fn len(&self) -> usize {
326 self.0.len()
327 }
328
329 pub fn version(&self) -> &clock::Global {
330 self.0.version()
331 }
332
333 pub fn ranges<'a, D>(&'a self, content: &'a Snapshot) -> impl 'a + Iterator<Item = Range<Point>>
334 where
335 D: 'a + TextDimension<'a>,
336 {
337 self.0.ranges(content).map(|(range, _)| range)
338 }
339}
340
341impl<T: Clone> Default for AnchorRangeMultimap<T> {
342 fn default() -> Self {
343 Self {
344 entries: Default::default(),
345 version: Default::default(),
346 start_bias: Bias::Left,
347 end_bias: Bias::Left,
348 }
349 }
350}
351
352impl<T: Clone> AnchorRangeMultimap<T> {
353 pub fn version(&self) -> &clock::Global {
354 &self.version
355 }
356
357 pub fn intersecting_ranges<'a, I, O>(
358 &'a self,
359 range: Range<I>,
360 content: &'a Snapshot,
361 inclusive: bool,
362 ) -> impl Iterator<Item = (usize, Range<O>, &T)> + 'a
363 where
364 I: ToOffset,
365 O: FromAnchor,
366 {
367 let end_bias = if inclusive { Bias::Right } else { Bias::Left };
368 let range = range.start.to_full_offset(&content, Bias::Left)
369 ..range.end.to_full_offset(&content, end_bias);
370 let mut cursor = self.entries.filter::<_, usize>(
371 {
372 let mut endpoint = Anchor {
373 full_offset: FullOffset(0),
374 bias: Bias::Right,
375 version: self.version.clone(),
376 };
377 move |summary: &AnchorRangeMultimapSummary| {
378 endpoint.full_offset = summary.max_end;
379 endpoint.bias = self.end_bias;
380 let max_end = endpoint.to_full_offset(&content, self.end_bias);
381 let start_cmp = range.start.cmp(&max_end);
382
383 endpoint.full_offset = summary.min_start;
384 endpoint.bias = self.start_bias;
385 let min_start = endpoint.to_full_offset(&content, self.start_bias);
386 let end_cmp = range.end.cmp(&min_start);
387
388 if inclusive {
389 start_cmp <= Ordering::Equal && end_cmp >= Ordering::Equal
390 } else {
391 start_cmp == Ordering::Less && end_cmp == Ordering::Greater
392 }
393 }
394 },
395 &(),
396 );
397
398 std::iter::from_fn({
399 let mut endpoint = Anchor {
400 full_offset: FullOffset(0),
401 bias: Bias::Left,
402 version: self.version.clone(),
403 };
404 move || {
405 if let Some(item) = cursor.item() {
406 let ix = *cursor.start();
407 endpoint.full_offset = item.range.start;
408 endpoint.bias = self.start_bias;
409 let start = O::from_anchor(&endpoint, &content);
410 endpoint.full_offset = item.range.end;
411 endpoint.bias = self.end_bias;
412 let end = O::from_anchor(&endpoint, &content);
413 let value = &item.value;
414 cursor.next(&());
415 Some((ix, start..end, value))
416 } else {
417 None
418 }
419 }
420 })
421 }
422
423 pub fn from_full_offset_ranges(
424 version: clock::Global,
425 start_bias: Bias,
426 end_bias: Bias,
427 entries: impl Iterator<Item = (Range<FullOffset>, T)>,
428 ) -> Self {
429 Self {
430 version,
431 start_bias,
432 end_bias,
433 entries: SumTree::from_iter(
434 entries.map(|(range, value)| AnchorRangeMultimapEntry {
435 range: FullOffsetRange {
436 start: range.start,
437 end: range.end,
438 },
439 value,
440 }),
441 &(),
442 ),
443 }
444 }
445
446 pub fn full_offset_ranges(&self) -> impl Iterator<Item = (Range<FullOffset>, &T)> {
447 self.entries
448 .cursor::<()>()
449 .map(|entry| (entry.range.start..entry.range.end, &entry.value))
450 }
451
452 pub fn filter<'a, O, F>(
453 &'a self,
454 content: &'a Snapshot,
455 mut f: F,
456 ) -> impl 'a + Iterator<Item = (usize, Range<O>, &T)>
457 where
458 O: FromAnchor,
459 F: 'a + FnMut(&'a T) -> bool,
460 {
461 let mut endpoint = Anchor {
462 full_offset: FullOffset(0),
463 bias: Bias::Left,
464 version: self.version.clone(),
465 };
466 self.entries
467 .cursor::<()>()
468 .enumerate()
469 .filter_map(move |(ix, entry)| {
470 if f(&entry.value) {
471 endpoint.full_offset = entry.range.start;
472 endpoint.bias = self.start_bias;
473 let start = O::from_anchor(&endpoint, &content);
474 endpoint.full_offset = entry.range.end;
475 endpoint.bias = self.end_bias;
476 let end = O::from_anchor(&endpoint, &content);
477 Some((ix, start..end, &entry.value))
478 } else {
479 None
480 }
481 })
482 }
483}
484
485impl<T: Clone> sum_tree::Item for AnchorRangeMultimapEntry<T> {
486 type Summary = AnchorRangeMultimapSummary;
487
488 fn summary(&self) -> Self::Summary {
489 AnchorRangeMultimapSummary {
490 start: self.range.start,
491 end: self.range.end,
492 min_start: self.range.start,
493 max_end: self.range.end,
494 count: 1,
495 }
496 }
497}
498
499impl Default for AnchorRangeMultimapSummary {
500 fn default() -> Self {
501 Self {
502 start: FullOffset(0),
503 end: FullOffset::MAX,
504 min_start: FullOffset::MAX,
505 max_end: FullOffset(0),
506 count: 0,
507 }
508 }
509}
510
511impl sum_tree::Summary for AnchorRangeMultimapSummary {
512 type Context = ();
513
514 fn add_summary(&mut self, other: &Self, _: &Self::Context) {
515 self.min_start = self.min_start.min(other.min_start);
516 self.max_end = self.max_end.max(other.max_end);
517
518 #[cfg(debug_assertions)]
519 {
520 let start_comparison = self.start.cmp(&other.start);
521 assert!(start_comparison <= Ordering::Equal);
522 if start_comparison == Ordering::Equal {
523 assert!(self.end.cmp(&other.end) >= Ordering::Equal);
524 }
525 }
526
527 self.start = other.start;
528 self.end = other.end;
529 self.count += other.count;
530 }
531}
532
533impl Default for FullOffsetRange {
534 fn default() -> Self {
535 Self {
536 start: FullOffset(0),
537 end: FullOffset::MAX,
538 }
539 }
540}
541
542impl<'a> sum_tree::Dimension<'a, AnchorRangeMultimapSummary> for usize {
543 fn add_summary(&mut self, summary: &'a AnchorRangeMultimapSummary, _: &()) {
544 *self += summary.count;
545 }
546}
547
548impl<'a> sum_tree::Dimension<'a, AnchorRangeMultimapSummary> for FullOffsetRange {
549 fn add_summary(&mut self, summary: &'a AnchorRangeMultimapSummary, _: &()) {
550 self.start = summary.start;
551 self.end = summary.end;
552 }
553}
554
555impl<'a> sum_tree::SeekTarget<'a, AnchorRangeMultimapSummary, FullOffsetRange> for FullOffsetRange {
556 fn cmp(&self, cursor_location: &FullOffsetRange, _: &()) -> Ordering {
557 Ord::cmp(&self.start, &cursor_location.start)
558 .then_with(|| Ord::cmp(&cursor_location.end, &self.end))
559 }
560}
561
562pub trait AnchorRangeExt {
563 fn cmp(&self, b: &Range<Anchor>, buffer: &Snapshot) -> Result<Ordering>;
564 fn to_offset(&self, content: &Snapshot) -> Range<usize>;
565}
566
567impl AnchorRangeExt for Range<Anchor> {
568 fn cmp(&self, other: &Range<Anchor>, buffer: &Snapshot) -> Result<Ordering> {
569 Ok(match self.start.cmp(&other.start, buffer)? {
570 Ordering::Equal => other.end.cmp(&self.end, buffer)?,
571 ord @ _ => ord,
572 })
573 }
574
575 fn to_offset(&self, content: &Snapshot) -> Range<usize> {
576 self.start.to_offset(&content)..self.end.to_offset(&content)
577 }
578}