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