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