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
118impl<T> AnchorMap<T> {
119 pub fn version(&self) -> &clock::Global {
120 &self.version
121 }
122
123 pub fn len(&self) -> usize {
124 self.entries.len()
125 }
126
127 pub fn offsets<'a>(
128 &'a self,
129 content: impl Into<Content<'a>> + 'a,
130 ) -> impl Iterator<Item = (usize, &'a T)> + 'a {
131 let content = content.into();
132 content
133 .summaries_for_anchors(self)
134 .map(move |(sum, value)| (sum.bytes, value))
135 }
136
137 pub fn points<'a>(
138 &'a self,
139 content: impl Into<Content<'a>> + 'a,
140 ) -> impl Iterator<Item = (Point, &'a T)> + 'a {
141 let content = content.into();
142 content
143 .summaries_for_anchors(self)
144 .map(move |(sum, value)| (sum.lines, 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 offsets<'a>(
158 &'a self,
159 content: impl Into<Content<'a>> + 'a,
160 ) -> impl Iterator<Item = usize> + 'a {
161 self.0.offsets(content).map(|(offset, _)| offset)
162 }
163
164 pub fn points<'a>(
165 &'a self,
166 content: impl Into<Content<'a>> + 'a,
167 ) -> impl Iterator<Item = Point> + 'a {
168 self.0.points(content).map(|(point, _)| point)
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 entries: Vec<(Range<(FullOffset, Bias)>, T)>,
184 ) -> Self {
185 Self { version, entries }
186 }
187
188 pub fn ranges<'a, D>(
189 &'a self,
190 content: impl Into<Content<'a>> + 'a,
191 ) -> impl Iterator<Item = (Range<D>, &'a T)> + 'a
192 where
193 D: 'a + TextDimension<'a>,
194 {
195 let content = content.into();
196 content.summaries_for_anchor_ranges(self)
197 }
198
199 pub fn full_offset_ranges(&self) -> impl Iterator<Item = (Range<FullOffset>, &T)> {
200 self.entries
201 .iter()
202 .map(|(range, value)| (range.start.0..range.end.0, value))
203 }
204}
205
206impl<T: PartialEq> PartialEq for AnchorRangeMap<T> {
207 fn eq(&self, other: &Self) -> bool {
208 self.version == other.version && self.entries == other.entries
209 }
210}
211
212impl<T: Eq> Eq for AnchorRangeMap<T> {}
213
214impl<T: Debug> Debug for AnchorRangeMap<T> {
215 fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), std::fmt::Error> {
216 let mut f = f.debug_map();
217 for (range, value) in &self.entries {
218 f.key(range);
219 f.value(value);
220 }
221 f.finish()
222 }
223}
224
225impl Debug for AnchorRangeSet {
226 fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
227 let mut f = f.debug_set();
228 for (range, _) in &self.0.entries {
229 f.entry(range);
230 }
231 f.finish()
232 }
233}
234
235impl AnchorRangeSet {
236 pub fn len(&self) -> usize {
237 self.0.len()
238 }
239
240 pub fn version(&self) -> &clock::Global {
241 self.0.version()
242 }
243
244 pub fn ranges<'a, D, C>(&'a self, content: C) -> impl 'a + Iterator<Item = Range<Point>>
245 where
246 D: 'a + TextDimension<'a>,
247 C: 'a + Into<Content<'a>>,
248 {
249 self.0.ranges(content).map(|(range, _)| range)
250 }
251}
252
253impl<T: Clone> Default for AnchorRangeMultimap<T> {
254 fn default() -> Self {
255 Self {
256 entries: Default::default(),
257 version: Default::default(),
258 start_bias: Bias::Left,
259 end_bias: Bias::Left,
260 }
261 }
262}
263
264impl<T: Clone> AnchorRangeMultimap<T> {
265 pub fn version(&self) -> &clock::Global {
266 &self.version
267 }
268
269 pub fn intersecting_ranges<'a, I, O>(
270 &'a self,
271 range: Range<I>,
272 content: Content<'a>,
273 inclusive: bool,
274 ) -> impl Iterator<Item = (usize, Range<O>, &T)> + 'a
275 where
276 I: ToOffset,
277 O: FromAnchor,
278 {
279 let end_bias = if inclusive { Bias::Right } else { Bias::Left };
280 let range = range.start.to_full_offset(&content, Bias::Left)
281 ..range.end.to_full_offset(&content, end_bias);
282 let mut cursor = self.entries.filter::<_, usize>(
283 {
284 let content = content.clone();
285 let mut endpoint = Anchor {
286 full_offset: FullOffset(0),
287 bias: Bias::Right,
288 version: self.version.clone(),
289 };
290 move |summary: &AnchorRangeMultimapSummary| {
291 endpoint.full_offset = summary.max_end;
292 endpoint.bias = self.end_bias;
293 let max_end = endpoint.to_full_offset(&content, self.end_bias);
294 let start_cmp = range.start.cmp(&max_end);
295
296 endpoint.full_offset = summary.min_start;
297 endpoint.bias = self.start_bias;
298 let min_start = endpoint.to_full_offset(&content, self.start_bias);
299 let end_cmp = range.end.cmp(&min_start);
300
301 if inclusive {
302 start_cmp <= Ordering::Equal && end_cmp >= Ordering::Equal
303 } else {
304 start_cmp == Ordering::Less && end_cmp == Ordering::Greater
305 }
306 }
307 },
308 &(),
309 );
310
311 std::iter::from_fn({
312 let mut endpoint = Anchor {
313 full_offset: FullOffset(0),
314 bias: Bias::Left,
315 version: self.version.clone(),
316 };
317 move || {
318 if let Some(item) = cursor.item() {
319 let ix = *cursor.start();
320 endpoint.full_offset = item.range.start;
321 endpoint.bias = self.start_bias;
322 let start = O::from_anchor(&endpoint, &content);
323 endpoint.full_offset = item.range.end;
324 endpoint.bias = self.end_bias;
325 let end = O::from_anchor(&endpoint, &content);
326 let value = &item.value;
327 cursor.next(&());
328 Some((ix, start..end, value))
329 } else {
330 None
331 }
332 }
333 })
334 }
335
336 pub fn from_full_offset_ranges(
337 version: clock::Global,
338 start_bias: Bias,
339 end_bias: Bias,
340 entries: impl Iterator<Item = (Range<FullOffset>, T)>,
341 ) -> Self {
342 Self {
343 version,
344 start_bias,
345 end_bias,
346 entries: SumTree::from_iter(
347 entries.map(|(range, value)| AnchorRangeMultimapEntry {
348 range: FullOffsetRange {
349 start: range.start,
350 end: range.end,
351 },
352 value,
353 }),
354 &(),
355 ),
356 }
357 }
358
359 pub fn full_offset_ranges(&self) -> impl Iterator<Item = (Range<FullOffset>, &T)> {
360 self.entries
361 .cursor::<()>()
362 .map(|entry| (entry.range.start..entry.range.end, &entry.value))
363 }
364}
365
366impl<T: Clone> sum_tree::Item for AnchorRangeMultimapEntry<T> {
367 type Summary = AnchorRangeMultimapSummary;
368
369 fn summary(&self) -> Self::Summary {
370 AnchorRangeMultimapSummary {
371 start: self.range.start,
372 end: self.range.end,
373 min_start: self.range.start,
374 max_end: self.range.end,
375 count: 1,
376 }
377 }
378}
379
380impl Default for AnchorRangeMultimapSummary {
381 fn default() -> Self {
382 Self {
383 start: FullOffset(0),
384 end: FullOffset::MAX,
385 min_start: FullOffset::MAX,
386 max_end: FullOffset(0),
387 count: 0,
388 }
389 }
390}
391
392impl sum_tree::Summary for AnchorRangeMultimapSummary {
393 type Context = ();
394
395 fn add_summary(&mut self, other: &Self, _: &Self::Context) {
396 self.min_start = self.min_start.min(other.min_start);
397 self.max_end = self.max_end.max(other.max_end);
398
399 #[cfg(debug_assertions)]
400 {
401 let start_comparison = self.start.cmp(&other.start);
402 assert!(start_comparison <= Ordering::Equal);
403 if start_comparison == Ordering::Equal {
404 assert!(self.end.cmp(&other.end) >= Ordering::Equal);
405 }
406 }
407
408 self.start = other.start;
409 self.end = other.end;
410 self.count += other.count;
411 }
412}
413
414impl Default for FullOffsetRange {
415 fn default() -> Self {
416 Self {
417 start: FullOffset(0),
418 end: FullOffset::MAX,
419 }
420 }
421}
422
423impl<'a> sum_tree::Dimension<'a, AnchorRangeMultimapSummary> for usize {
424 fn add_summary(&mut self, summary: &'a AnchorRangeMultimapSummary, _: &()) {
425 *self += summary.count;
426 }
427}
428
429impl<'a> sum_tree::Dimension<'a, AnchorRangeMultimapSummary> for FullOffsetRange {
430 fn add_summary(&mut self, summary: &'a AnchorRangeMultimapSummary, _: &()) {
431 self.start = summary.start;
432 self.end = summary.end;
433 }
434}
435
436impl<'a> sum_tree::SeekTarget<'a, AnchorRangeMultimapSummary, FullOffsetRange> for FullOffsetRange {
437 fn cmp(&self, cursor_location: &FullOffsetRange, _: &()) -> Ordering {
438 Ord::cmp(&self.start, &cursor_location.start)
439 .then_with(|| Ord::cmp(&cursor_location.end, &self.end))
440 }
441}
442
443pub trait AnchorRangeExt {
444 fn cmp<'a>(&self, b: &Range<Anchor>, buffer: impl Into<Content<'a>>) -> Result<Ordering>;
445}
446
447impl AnchorRangeExt for Range<Anchor> {
448 fn cmp<'a>(&self, other: &Range<Anchor>, buffer: impl Into<Content<'a>>) -> Result<Ordering> {
449 let buffer = buffer.into();
450 Ok(match self.start.cmp(&other.start, &buffer)? {
451 Ordering::Equal => other.end.cmp(&self.end, buffer)?,
452 ord @ _ => ord,
453 })
454 }
455}