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