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