1use super::{Buffer, Content, FromAnchor, FullOffset, Point, ToOffset};
2use anyhow::Result;
3use std::{
4 cmp::Ordering,
5 fmt::{Debug, Formatter},
6 ops::Range,
7};
8use sum_tree::{Bias, SumTree};
9
10#[derive(Clone, Eq, PartialEq, Debug, Hash)]
11pub struct Anchor {
12 pub full_offset: FullOffset,
13 pub bias: Bias,
14 pub version: clock::Global,
15}
16
17#[derive(Clone)]
18pub struct AnchorMap<T> {
19 pub(crate) version: clock::Global,
20 pub(crate) entries: Vec<((FullOffset, Bias), T)>,
21}
22
23#[derive(Clone)]
24pub struct AnchorSet(pub(crate) AnchorMap<()>);
25
26#[derive(Clone)]
27pub struct AnchorRangeMap<T> {
28 pub(crate) version: clock::Global,
29 pub(crate) entries: Vec<(Range<(FullOffset, Bias)>, T)>,
30}
31
32#[derive(Clone)]
33pub struct AnchorRangeSet(pub(crate) AnchorRangeMap<()>);
34
35#[derive(Clone)]
36pub struct AnchorRangeMultimap<T: Clone> {
37 pub(crate) entries: SumTree<AnchorRangeMultimapEntry<T>>,
38 pub(crate) version: clock::Global,
39 pub(crate) start_bias: Bias,
40 pub(crate) end_bias: Bias,
41}
42
43#[derive(Clone)]
44pub(crate) struct AnchorRangeMultimapEntry<T> {
45 pub(crate) range: FullOffsetRange,
46 pub(crate) value: T,
47}
48
49#[derive(Clone, Debug)]
50pub(crate) struct FullOffsetRange {
51 pub(crate) start: FullOffset,
52 pub(crate) end: FullOffset,
53}
54
55#[derive(Clone, Debug)]
56pub(crate) struct AnchorRangeMultimapSummary {
57 start: FullOffset,
58 end: FullOffset,
59 min_start: FullOffset,
60 max_end: FullOffset,
61 count: usize,
62}
63
64impl Anchor {
65 pub fn min() -> Self {
66 Self {
67 full_offset: FullOffset(0),
68 bias: Bias::Left,
69 version: Default::default(),
70 }
71 }
72
73 pub fn max() -> Self {
74 Self {
75 full_offset: FullOffset::MAX,
76 bias: Bias::Right,
77 version: Default::default(),
78 }
79 }
80
81 pub fn cmp<'a>(&self, other: &Anchor, buffer: impl Into<Content<'a>>) -> Result<Ordering> {
82 let buffer = buffer.into();
83
84 if self == other {
85 return Ok(Ordering::Equal);
86 }
87
88 let offset_comparison = if self.version == other.version {
89 self.full_offset.cmp(&other.full_offset)
90 } else {
91 buffer
92 .full_offset_for_anchor(self)
93 .cmp(&buffer.full_offset_for_anchor(other))
94 };
95
96 Ok(offset_comparison.then_with(|| self.bias.cmp(&other.bias)))
97 }
98
99 pub fn bias_left(&self, buffer: &Buffer) -> Anchor {
100 if self.bias == Bias::Left {
101 self.clone()
102 } else {
103 buffer.anchor_before(self)
104 }
105 }
106
107 pub fn bias_right(&self, buffer: &Buffer) -> Anchor {
108 if self.bias == Bias::Right {
109 self.clone()
110 } else {
111 buffer.anchor_after(self)
112 }
113 }
114}
115
116impl<T> AnchorMap<T> {
117 pub fn version(&self) -> &clock::Global {
118 &self.version
119 }
120
121 pub fn len(&self) -> usize {
122 self.entries.len()
123 }
124
125 pub fn offsets<'a>(
126 &'a self,
127 content: impl Into<Content<'a>> + 'a,
128 ) -> impl Iterator<Item = (usize, &'a T)> + 'a {
129 let content = content.into();
130 content
131 .summaries_for_anchors(self)
132 .map(move |(sum, value)| (sum.bytes, value))
133 }
134
135 pub fn points<'a>(
136 &'a self,
137 content: impl Into<Content<'a>> + 'a,
138 ) -> impl Iterator<Item = (Point, &'a T)> + 'a {
139 let content = content.into();
140 content
141 .summaries_for_anchors(self)
142 .map(move |(sum, value)| (sum.lines, value))
143 }
144}
145
146impl AnchorSet {
147 pub fn version(&self) -> &clock::Global {
148 &self.0.version
149 }
150
151 pub fn len(&self) -> usize {
152 self.0.len()
153 }
154
155 pub fn offsets<'a>(
156 &'a self,
157 content: impl Into<Content<'a>> + 'a,
158 ) -> impl Iterator<Item = usize> + 'a {
159 self.0.offsets(content).map(|(offset, _)| offset)
160 }
161
162 pub fn points<'a>(
163 &'a self,
164 content: impl Into<Content<'a>> + 'a,
165 ) -> impl Iterator<Item = Point> + 'a {
166 self.0.points(content).map(|(point, _)| point)
167 }
168}
169
170impl<T> AnchorRangeMap<T> {
171 pub fn version(&self) -> &clock::Global {
172 &self.version
173 }
174
175 pub fn len(&self) -> usize {
176 self.entries.len()
177 }
178
179 pub fn from_raw(version: clock::Global, entries: Vec<(Range<(FullOffset, Bias)>, T)>) -> Self {
180 Self { version, entries }
181 }
182
183 pub fn raw_entries(&self) -> &[(Range<(FullOffset, Bias)>, T)] {
184 &self.entries
185 }
186
187 pub fn point_ranges<'a>(
188 &'a self,
189 content: impl Into<Content<'a>> + 'a,
190 ) -> impl Iterator<Item = (Range<Point>, &'a T)> + 'a {
191 let content = content.into();
192 content
193 .summaries_for_anchor_ranges(self)
194 .map(move |(range, value)| ((range.start.lines..range.end.lines), value))
195 }
196
197 pub fn offset_ranges<'a>(
198 &'a self,
199 content: impl Into<Content<'a>> + 'a,
200 ) -> impl Iterator<Item = (Range<usize>, &'a T)> + 'a {
201 let content = content.into();
202 content
203 .summaries_for_anchor_ranges(self)
204 .map(move |(range, value)| ((range.start.bytes..range.end.bytes), value))
205 }
206}
207
208impl<T: PartialEq> PartialEq for AnchorRangeMap<T> {
209 fn eq(&self, other: &Self) -> bool {
210 self.version == other.version && self.entries == other.entries
211 }
212}
213
214impl<T: Eq> Eq for AnchorRangeMap<T> {}
215
216impl<T: Debug> Debug for AnchorRangeMap<T> {
217 fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), std::fmt::Error> {
218 let mut f = f.debug_map();
219 for (range, value) in &self.entries {
220 f.key(range);
221 f.value(value);
222 }
223 f.finish()
224 }
225}
226
227impl Debug for AnchorRangeSet {
228 fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
229 let mut f = f.debug_set();
230 for (range, _) in &self.0.entries {
231 f.entry(range);
232 }
233 f.finish()
234 }
235}
236
237impl AnchorRangeSet {
238 pub fn len(&self) -> usize {
239 self.0.len()
240 }
241
242 pub fn version(&self) -> &clock::Global {
243 self.0.version()
244 }
245
246 pub fn offset_ranges<'a>(
247 &'a self,
248 content: impl Into<Content<'a>> + 'a,
249 ) -> impl Iterator<Item = Range<usize>> + 'a {
250 self.0.offset_ranges(content).map(|(range, _)| range)
251 }
252
253 pub fn point_ranges<'a>(
254 &'a self,
255 content: impl Into<Content<'a>> + 'a,
256 ) -> impl Iterator<Item = Range<Point>> + 'a {
257 self.0.point_ranges(content).map(|(range, _)| range)
258 }
259}
260
261impl<T: Clone> Default for AnchorRangeMultimap<T> {
262 fn default() -> Self {
263 Self {
264 entries: Default::default(),
265 version: Default::default(),
266 start_bias: Bias::Left,
267 end_bias: Bias::Left,
268 }
269 }
270}
271
272impl<T: Clone> AnchorRangeMultimap<T> {
273 pub fn intersecting_ranges<'a, I, O>(
274 &'a self,
275 range: Range<I>,
276 content: Content<'a>,
277 inclusive: bool,
278 ) -> impl Iterator<Item = (usize, Range<O>, &T)> + 'a
279 where
280 I: ToOffset,
281 O: FromAnchor,
282 {
283 let end_bias = if inclusive { Bias::Right } else { Bias::Left };
284 let range = range.start.to_full_offset(&content, Bias::Left)
285 ..range.end.to_full_offset(&content, end_bias);
286 let mut cursor = self.entries.filter::<_, usize>(
287 {
288 let content = content.clone();
289 let mut endpoint = Anchor {
290 full_offset: FullOffset(0),
291 bias: Bias::Right,
292 version: self.version.clone(),
293 };
294 move |summary: &AnchorRangeMultimapSummary| {
295 endpoint.full_offset = summary.max_end;
296 endpoint.bias = self.end_bias;
297 let max_end = endpoint.to_full_offset(&content, self.end_bias);
298 let start_cmp = range.start.cmp(&max_end);
299
300 endpoint.full_offset = summary.min_start;
301 endpoint.bias = self.start_bias;
302 let min_start = endpoint.to_full_offset(&content, self.start_bias);
303 let end_cmp = range.end.cmp(&min_start);
304
305 if inclusive {
306 start_cmp <= Ordering::Equal && end_cmp >= Ordering::Equal
307 } else {
308 start_cmp == Ordering::Less && end_cmp == Ordering::Greater
309 }
310 }
311 },
312 &(),
313 );
314
315 std::iter::from_fn({
316 let mut endpoint = Anchor {
317 full_offset: FullOffset(0),
318 bias: Bias::Left,
319 version: self.version.clone(),
320 };
321 move || {
322 if let Some(item) = cursor.item() {
323 let ix = *cursor.start();
324 endpoint.full_offset = item.range.start;
325 endpoint.bias = self.start_bias;
326 let start = O::from_anchor(&endpoint, &content);
327 endpoint.full_offset = item.range.end;
328 endpoint.bias = self.end_bias;
329 let end = O::from_anchor(&endpoint, &content);
330 let value = &item.value;
331 cursor.next(&());
332 Some((ix, start..end, value))
333 } else {
334 None
335 }
336 }
337 })
338 }
339}
340
341impl<T: Clone> sum_tree::Item for AnchorRangeMultimapEntry<T> {
342 type Summary = AnchorRangeMultimapSummary;
343
344 fn summary(&self) -> Self::Summary {
345 AnchorRangeMultimapSummary {
346 start: self.range.start,
347 end: self.range.end,
348 min_start: self.range.start,
349 max_end: self.range.end,
350 count: 1,
351 }
352 }
353}
354
355impl Default for AnchorRangeMultimapSummary {
356 fn default() -> Self {
357 Self {
358 start: FullOffset(0),
359 end: FullOffset::MAX,
360 min_start: FullOffset::MAX,
361 max_end: FullOffset(0),
362 count: 0,
363 }
364 }
365}
366
367impl sum_tree::Summary for AnchorRangeMultimapSummary {
368 type Context = ();
369
370 fn add_summary(&mut self, other: &Self, _: &Self::Context) {
371 self.min_start = self.min_start.min(other.min_start);
372 self.max_end = self.max_end.max(other.max_end);
373
374 #[cfg(debug_assertions)]
375 {
376 let start_comparison = self.start.cmp(&other.start);
377 assert!(start_comparison <= Ordering::Equal);
378 if start_comparison == Ordering::Equal {
379 assert!(self.end.cmp(&other.end) >= Ordering::Equal);
380 }
381 }
382
383 self.start = other.start;
384 self.end = other.end;
385 self.count += other.count;
386 }
387}
388
389impl Default for FullOffsetRange {
390 fn default() -> Self {
391 Self {
392 start: FullOffset(0),
393 end: FullOffset::MAX,
394 }
395 }
396}
397
398impl<'a> sum_tree::Dimension<'a, AnchorRangeMultimapSummary> for usize {
399 fn add_summary(&mut self, summary: &'a AnchorRangeMultimapSummary, _: &()) {
400 *self += summary.count;
401 }
402}
403
404impl<'a> sum_tree::Dimension<'a, AnchorRangeMultimapSummary> for FullOffsetRange {
405 fn add_summary(&mut self, summary: &'a AnchorRangeMultimapSummary, _: &()) {
406 self.start = summary.start;
407 self.end = summary.end;
408 }
409}
410
411impl<'a> sum_tree::SeekTarget<'a, AnchorRangeMultimapSummary, FullOffsetRange> for FullOffsetRange {
412 fn cmp(&self, cursor_location: &FullOffsetRange, _: &()) -> Ordering {
413 Ord::cmp(&self.start, &cursor_location.start)
414 .then_with(|| Ord::cmp(&cursor_location.end, &self.end))
415 }
416}
417
418pub trait AnchorRangeExt {
419 fn cmp<'a>(&self, b: &Range<Anchor>, buffer: impl Into<Content<'a>>) -> Result<Ordering>;
420}
421
422impl AnchorRangeExt for Range<Anchor> {
423 fn cmp<'a>(&self, other: &Range<Anchor>, buffer: impl Into<Content<'a>>) -> Result<Ordering> {
424 let buffer = buffer.into();
425 Ok(match self.start.cmp(&other.start, &buffer)? {
426 Ordering::Equal => other.end.cmp(&self.end, buffer)?,
427 ord @ _ => ord,
428 })
429 }
430}