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 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)]
41struct AnchorRangeMultimapEntry<T> {
42 range: FullOffsetRange,
43 value: T,
44}
45
46#[derive(Clone, Debug)]
47struct FullOffsetRange {
48 start: usize,
49 end: usize,
50}
51
52#[derive(Clone, Debug)]
53struct 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, O: ToOffset>(
169 &'a self,
170 range: Range<O>,
171 content: impl Into<Content<'a>>,
172 inclusive: bool,
173 ) -> impl Iterator<Item = (usize, Range<Point>, &T)> + 'a {
174 use super::ToPoint as _;
175
176 let content = content.into();
177 let start = range.start.to_full_offset(&content, self.start_bias);
178 let end = range.end.to_full_offset(&content, self.end_bias);
179 let mut cursor = self.entries.filter::<_, usize>(
180 move |summary: &AnchorRangeMultimapSummary| {
181 if inclusive {
182 start <= summary.max_end && end >= summary.min_start
183 } else {
184 start < summary.max_end && end > summary.min_start
185 }
186 },
187 &(),
188 );
189 let mut anchor = Anchor {
190 full_offset: 0,
191 bias: Bias::Left,
192 version: self.version.clone(),
193 };
194 std::iter::from_fn(move || {
195 if let Some(item) = cursor.item() {
196 let ix = *cursor.start();
197 anchor.full_offset = item.range.start;
198 anchor.bias = self.start_bias;
199 let start = anchor.to_point(&content);
200 anchor.full_offset = item.range.end;
201 anchor.bias = self.end_bias;
202 let end = anchor.to_point(&content);
203 let value = &item.value;
204 cursor.next(&());
205 Some((ix, start..end, value))
206 } else {
207 None
208 }
209 })
210 }
211}
212
213impl<T: Clone> sum_tree::Item for AnchorRangeMultimapEntry<T> {
214 type Summary = AnchorRangeMultimapSummary;
215
216 fn summary(&self) -> Self::Summary {
217 AnchorRangeMultimapSummary {
218 start: self.range.start,
219 end: self.range.end,
220 min_start: self.range.start,
221 max_end: self.range.end,
222 count: 1,
223 }
224 }
225}
226
227impl Default for AnchorRangeMultimapSummary {
228 fn default() -> Self {
229 Self {
230 start: 0,
231 end: usize::MAX,
232 min_start: usize::MAX,
233 max_end: 0,
234 count: 0,
235 }
236 }
237}
238
239impl sum_tree::Summary for AnchorRangeMultimapSummary {
240 type Context = ();
241
242 fn add_summary(&mut self, other: &Self, _: &Self::Context) {
243 self.min_start = self.min_start.min(other.min_start);
244 self.max_end = self.max_end.max(other.max_end);
245
246 #[cfg(debug_assertions)]
247 {
248 let start_comparison = self.start.cmp(&other.start);
249 assert!(start_comparison <= Ordering::Equal);
250 if start_comparison == Ordering::Equal {
251 assert!(self.end.cmp(&other.end) >= Ordering::Equal);
252 }
253 }
254
255 self.start = other.start;
256 self.end = other.end;
257 self.count += other.count;
258 }
259}
260
261impl Default for FullOffsetRange {
262 fn default() -> Self {
263 Self {
264 start: 0,
265 end: usize::MAX,
266 }
267 }
268}
269
270impl<'a> sum_tree::Dimension<'a, AnchorRangeMultimapSummary> for usize {
271 fn add_summary(&mut self, summary: &'a AnchorRangeMultimapSummary, _: &()) {
272 *self += summary.count;
273 }
274}
275
276impl<'a> sum_tree::Dimension<'a, AnchorRangeMultimapSummary> for FullOffsetRange {
277 fn add_summary(&mut self, summary: &'a AnchorRangeMultimapSummary, _: &()) {
278 self.start = summary.start;
279 self.end = summary.end;
280 }
281}
282
283impl<'a> sum_tree::SeekTarget<'a, AnchorRangeMultimapSummary, FullOffsetRange> for FullOffsetRange {
284 fn cmp(&self, cursor_location: &FullOffsetRange, _: &()) -> Ordering {
285 Ord::cmp(&self.start, &cursor_location.start)
286 .then_with(|| Ord::cmp(&cursor_location.end, &self.end))
287 }
288}
289
290pub trait AnchorRangeExt {
291 fn cmp<'a>(&self, b: &Range<Anchor>, buffer: impl Into<Content<'a>>) -> Result<Ordering>;
292}
293
294impl AnchorRangeExt for Range<Anchor> {
295 fn cmp<'a>(&self, other: &Range<Anchor>, buffer: impl Into<Content<'a>>) -> Result<Ordering> {
296 let buffer = buffer.into();
297 Ok(match self.start.cmp(&other.start, &buffer)? {
298 Ordering::Equal => other.end.cmp(&self.end, buffer)?,
299 ord @ _ => ord,
300 })
301 }
302}