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