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