1use super::{Buffer, Content, Point, ToOffset};
2use anyhow::Result;
3use std::{cmp::Ordering, ops::Range};
4use sum_tree::{Bias, SumTree};
5
6#[derive(Clone, Eq, PartialEq, Debug, Hash)]
7pub struct Anchor {
8 pub full_offset: usize,
9 pub bias: Bias,
10 pub version: clock::Global,
11}
12
13#[derive(Clone)]
14pub struct AnchorMap<T> {
15 pub(crate) version: clock::Global,
16 pub(crate) entries: Vec<((usize, Bias), T)>,
17}
18
19#[derive(Clone)]
20pub struct AnchorSet(pub(crate) AnchorMap<()>);
21
22#[derive(Clone)]
23pub struct AnchorRangeMap<T> {
24 pub(crate) version: clock::Global,
25 pub(crate) entries: Vec<(Range<(usize, Bias)>, T)>,
26}
27
28#[derive(Clone)]
29pub struct AnchorRangeSet(pub(crate) AnchorRangeMap<()>);
30
31#[derive(Clone)]
32pub struct AnchorRangeMultimap<T: Clone> {
33 pub(crate) entries: SumTree<AnchorRangeMultimapEntry<T>>,
34 pub(crate) version: clock::Global,
35 pub(crate) start_bias: Bias,
36 pub(crate) end_bias: Bias,
37}
38
39#[derive(Clone)]
40pub(crate) struct AnchorRangeMultimapEntry<T> {
41 pub(crate) range: FullOffsetRange,
42 pub(crate) value: T,
43}
44
45#[derive(Clone, Debug)]
46pub(crate) struct FullOffsetRange {
47 pub(crate) start: usize,
48 pub(crate) end: usize,
49}
50
51#[derive(Clone, Debug)]
52pub(crate) struct AnchorRangeMultimapSummary {
53 start: usize,
54 end: usize,
55 min_start: usize,
56 max_end: usize,
57 count: usize,
58}
59
60impl Anchor {
61 pub fn min() -> Self {
62 Self {
63 full_offset: 0,
64 bias: Bias::Left,
65 version: Default::default(),
66 }
67 }
68
69 pub fn max() -> Self {
70 Self {
71 full_offset: usize::MAX,
72 bias: Bias::Right,
73 version: Default::default(),
74 }
75 }
76
77 pub fn cmp<'a>(&self, other: &Anchor, buffer: impl Into<Content<'a>>) -> Result<Ordering> {
78 let buffer = buffer.into();
79
80 if self == other {
81 return Ok(Ordering::Equal);
82 }
83
84 let offset_comparison = if self.version == other.version {
85 self.full_offset.cmp(&other.full_offset)
86 } else {
87 buffer
88 .full_offset_for_anchor(self)
89 .cmp(&buffer.full_offset_for_anchor(other))
90 };
91
92 Ok(offset_comparison.then_with(|| self.bias.cmp(&other.bias)))
93 }
94
95 pub fn bias_left(&self, buffer: &Buffer) -> Anchor {
96 if self.bias == Bias::Left {
97 self.clone()
98 } else {
99 buffer.anchor_before(self)
100 }
101 }
102
103 pub fn bias_right(&self, buffer: &Buffer) -> Anchor {
104 if self.bias == Bias::Right {
105 self.clone()
106 } else {
107 buffer.anchor_after(self)
108 }
109 }
110}
111
112impl<T> AnchorMap<T> {
113 pub fn to_points<'a>(
114 &'a self,
115 content: impl Into<Content<'a>> + 'a,
116 ) -> impl Iterator<Item = (Point, &'a T)> + 'a {
117 let content = content.into();
118 content
119 .summaries_for_anchors(self)
120 .map(move |(sum, value)| (sum.lines, value))
121 }
122
123 pub fn version(&self) -> &clock::Global {
124 &self.version
125 }
126}
127
128impl AnchorSet {
129 pub fn to_points<'a>(
130 &'a self,
131 content: impl Into<Content<'a>> + 'a,
132 ) -> impl Iterator<Item = Point> + 'a {
133 self.0.to_points(content).map(move |(point, _)| point)
134 }
135}
136
137impl<T> AnchorRangeMap<T> {
138 pub fn to_point_ranges<'a>(
139 &'a self,
140 content: impl Into<Content<'a>> + 'a,
141 ) -> impl Iterator<Item = (Range<Point>, &'a T)> + 'a {
142 let content = content.into();
143 content
144 .summaries_for_anchor_ranges(self)
145 .map(move |(range, value)| ((range.start.lines..range.end.lines), value))
146 }
147
148 pub fn version(&self) -> &clock::Global {
149 &self.version
150 }
151}
152
153impl AnchorRangeSet {
154 pub fn to_point_ranges<'a>(
155 &'a self,
156 content: impl Into<Content<'a>> + 'a,
157 ) -> impl Iterator<Item = Range<Point>> + 'a {
158 self.0.to_point_ranges(content).map(|(range, _)| range)
159 }
160
161 pub fn version(&self) -> &clock::Global {
162 self.0.version()
163 }
164}
165
166impl<T: Clone> Default for AnchorRangeMultimap<T> {
167 fn default() -> Self {
168 Self {
169 entries: Default::default(),
170 version: Default::default(),
171 start_bias: Bias::Left,
172 end_bias: Bias::Left,
173 }
174 }
175}
176
177impl<T: Clone> AnchorRangeMultimap<T> {
178 fn intersecting_point_ranges<'a, O>(
179 &'a self,
180 range: Range<O>,
181 content: &'a Content<'a>,
182 inclusive: bool,
183 ) -> impl Iterator<Item = (usize, Range<Point>, &T)> + 'a
184 where
185 O: ToOffset,
186 {
187 use super::ToPoint as _;
188
189 let end_bias = if inclusive { Bias::Right } else { Bias::Left };
190 let range = range.start.to_full_offset(content, Bias::Left)
191 ..range.end.to_full_offset(content, end_bias);
192 let mut cursor = self.entries.filter::<_, usize>(
193 {
194 let mut endpoint = Anchor {
195 full_offset: 0,
196 bias: Bias::Right,
197 version: self.version.clone(),
198 };
199 move |summary: &AnchorRangeMultimapSummary| {
200 endpoint.full_offset = summary.max_end;
201 endpoint.bias = self.end_bias;
202 let max_end = endpoint.to_full_offset(content, self.end_bias);
203 let start_cmp = range.start.cmp(&max_end);
204
205 endpoint.full_offset = summary.min_start;
206 endpoint.bias = self.start_bias;
207 let min_start = endpoint.to_full_offset(content, self.start_bias);
208 let end_cmp = range.end.cmp(&min_start);
209
210 if inclusive {
211 start_cmp <= Ordering::Equal && end_cmp >= Ordering::Equal
212 } else {
213 start_cmp == Ordering::Less && end_cmp == Ordering::Greater
214 }
215 }
216 },
217 &(),
218 );
219
220 std::iter::from_fn({
221 let mut endpoint = Anchor {
222 full_offset: 0,
223 bias: Bias::Left,
224 version: self.version.clone(),
225 };
226 move || {
227 if let Some(item) = cursor.item() {
228 let ix = *cursor.start();
229 endpoint.full_offset = item.range.start;
230 endpoint.bias = self.start_bias;
231 let start = endpoint.to_point(content);
232 endpoint.full_offset = item.range.end;
233 endpoint.bias = self.end_bias;
234 let end = endpoint.to_point(content);
235 let value = &item.value;
236 cursor.next(&());
237 Some((ix, start..end, value))
238 } else {
239 None
240 }
241 }
242 })
243 }
244}
245
246impl<T: Clone> sum_tree::Item for AnchorRangeMultimapEntry<T> {
247 type Summary = AnchorRangeMultimapSummary;
248
249 fn summary(&self) -> Self::Summary {
250 AnchorRangeMultimapSummary {
251 start: self.range.start,
252 end: self.range.end,
253 min_start: self.range.start,
254 max_end: self.range.end,
255 count: 1,
256 }
257 }
258}
259
260impl Default for AnchorRangeMultimapSummary {
261 fn default() -> Self {
262 Self {
263 start: 0,
264 end: usize::MAX,
265 min_start: usize::MAX,
266 max_end: 0,
267 count: 0,
268 }
269 }
270}
271
272impl sum_tree::Summary for AnchorRangeMultimapSummary {
273 type Context = ();
274
275 fn add_summary(&mut self, other: &Self, _: &Self::Context) {
276 self.min_start = self.min_start.min(other.min_start);
277 self.max_end = self.max_end.max(other.max_end);
278
279 #[cfg(debug_assertions)]
280 {
281 let start_comparison = self.start.cmp(&other.start);
282 assert!(start_comparison <= Ordering::Equal);
283 if start_comparison == Ordering::Equal {
284 assert!(self.end.cmp(&other.end) >= Ordering::Equal);
285 }
286 }
287
288 self.start = other.start;
289 self.end = other.end;
290 self.count += other.count;
291 }
292}
293
294impl Default for FullOffsetRange {
295 fn default() -> Self {
296 Self {
297 start: 0,
298 end: usize::MAX,
299 }
300 }
301}
302
303impl<'a> sum_tree::Dimension<'a, AnchorRangeMultimapSummary> for usize {
304 fn add_summary(&mut self, summary: &'a AnchorRangeMultimapSummary, _: &()) {
305 *self += summary.count;
306 }
307}
308
309impl<'a> sum_tree::Dimension<'a, AnchorRangeMultimapSummary> for FullOffsetRange {
310 fn add_summary(&mut self, summary: &'a AnchorRangeMultimapSummary, _: &()) {
311 self.start = summary.start;
312 self.end = summary.end;
313 }
314}
315
316impl<'a> sum_tree::SeekTarget<'a, AnchorRangeMultimapSummary, FullOffsetRange> for FullOffsetRange {
317 fn cmp(&self, cursor_location: &FullOffsetRange, _: &()) -> Ordering {
318 Ord::cmp(&self.start, &cursor_location.start)
319 .then_with(|| Ord::cmp(&cursor_location.end, &self.end))
320 }
321}
322
323pub trait AnchorRangeExt {
324 fn cmp<'a>(&self, b: &Range<Anchor>, buffer: impl Into<Content<'a>>) -> Result<Ordering>;
325}
326
327impl AnchorRangeExt for Range<Anchor> {
328 fn cmp<'a>(&self, other: &Range<Anchor>, buffer: impl Into<Content<'a>>) -> Result<Ordering> {
329 let buffer = buffer.into();
330 Ok(match self.start.cmp(&other.start, &buffer)? {
331 Ordering::Equal => other.end.cmp(&self.end, buffer)?,
332 ord @ _ => ord,
333 })
334 }
335}