1use super::{location::*, ExcerptSummary, MultiBufferSnapshot, ToOffset, ToPoint};
2use anyhow::{anyhow, Result};
3use smallvec::SmallVec;
4use std::{
5 cmp::Ordering,
6 ops::{Range, Sub},
7};
8use sum_tree::Bias;
9use text::{rope::TextDimension, AnchorRangeExt as _, Point};
10
11#[derive(Clone, Eq, PartialEq, Debug, Hash)]
12pub struct Anchor {
13 excerpt_id: ExcerptId,
14 text_anchor: text::Anchor,
15}
16
17#[derive(Clone, Debug, Default, PartialEq, Eq)]
18pub struct AnchorRangeMap<T> {
19 pub(crate) child_maps: SmallVec<[(ExcerptId, text::AnchorRangeMap<T>); 1]>,
20}
21
22#[derive(Clone, Debug, PartialEq, Eq)]
23pub struct AnchorRangeSet(AnchorRangeMap<()>);
24
25impl Anchor {
26 pub fn min() -> Self {
27 Self {
28 excerpt_id: ExcerptId::min(),
29 text_anchor: text::Anchor::min(),
30 }
31 }
32
33 pub fn max() -> Self {
34 Self {
35 excerpt_id: ExcerptId::max(),
36 text_anchor: text::Anchor::max(),
37 }
38 }
39
40 pub fn cmp<'a>(&self, other: &Anchor, snapshot: &MultiBufferSnapshot) -> Result<Ordering> {
41 let excerpt_id_cmp = self.excerpt_id.cmp(&other.excerpt_id);
42 if excerpt_id_cmp.is_eq() {
43 self.text_anchor.cmp(
44 &other.text_anchor,
45 snapshot
46 .buffer_snapshot_for_excerpt(&self.excerpt_id)
47 .ok_or_else(|| anyhow!("excerpt {:?} not found", self.excerpt_id))?,
48 )
49 } else {
50 return Ok(excerpt_id_cmp);
51 }
52 }
53
54 pub fn bias_left(&self, snapshot: &MultiBufferSnapshot) -> Anchor {
55 if self.text_anchor.bias != Bias::Left {
56 if let Some(buffer_snapshot) = snapshot.buffer_snapshot_for_excerpt(&self.excerpt_id) {
57 return Self {
58 excerpt_id: self.excerpt_id.clone(),
59 text_anchor: self.text_anchor.bias_left(buffer_snapshot),
60 };
61 }
62 }
63 self.clone()
64 }
65
66 pub fn bias_right(&self, snapshot: &MultiBufferSnapshot) -> Anchor {
67 if self.text_anchor.bias != Bias::Right {
68 if let Some(buffer_snapshot) = snapshot.buffer_snapshot_for_excerpt(&self.excerpt_id) {
69 return Self {
70 excerpt_id: self.excerpt_id.clone(),
71 text_anchor: self.text_anchor.bias_right(buffer_snapshot),
72 };
73 }
74 }
75 self.clone()
76 }
77
78 pub fn summary<'a, D>(&self, snapshot: &'a MultiBufferSnapshot) -> D
79 where
80 D: TextDimension + Ord + Sub<D, Output = D>,
81 {
82 let mut cursor = snapshot.excerpts.cursor::<ExcerptSummary>();
83 cursor.seek(&self.excerpt_id, Bias::Left, &());
84 if let Some(excerpt) = cursor.item() {
85 if excerpt.id == self.excerpt_id {
86 let mut excerpt_start = D::from_text_summary(&cursor.start().text);
87 excerpt_start.add_summary(&excerpt.header_summary(), &());
88 let excerpt_buffer_start = excerpt.range.start.summary::<D>(&excerpt.buffer);
89 let buffer_point = self.text_anchor.summary::<D>(&excerpt.buffer);
90 if buffer_point > excerpt_buffer_start {
91 excerpt_start.add_assign(&(buffer_point - excerpt_buffer_start));
92 }
93 return excerpt_start;
94 }
95 }
96 D::from_text_summary(&cursor.start().text)
97 }
98}
99
100impl<T> AnchorRangeMap<T> {
101 pub fn len(&self) -> usize {
102 self.child_maps
103 .iter()
104 .map(|(_, text_map)| text_map.len())
105 .sum()
106 }
107
108 pub fn ranges<'a, D>(
109 &'a self,
110 snapshot: &'a MultiBufferSnapshot,
111 ) -> impl Iterator<Item = (Range<D>, &'a T)> + 'a
112 where
113 D: TextDimension + Clone,
114 {
115 let mut cursor = snapshot.excerpts.cursor::<ExcerptSummary>();
116 self.child_maps
117 .iter()
118 .filter_map(move |(excerpt_id, text_map)| {
119 cursor.seek_forward(excerpt_id, Bias::Left, &());
120 if let Some(excerpt) = cursor.item() {
121 if excerpt.id == *excerpt_id {
122 let mut excerpt_start = D::from_text_summary(&cursor.start().text);
123 excerpt_start.add_summary(&excerpt.header_summary(), &());
124 return Some(text_map.ranges::<D>(&excerpt.buffer).map(
125 move |(range, value)| {
126 let mut full_range = excerpt_start.clone()..excerpt_start.clone();
127 full_range.start.add_assign(&range.start);
128 full_range.end.add_assign(&range.end);
129 (full_range, value)
130 },
131 ));
132 }
133 }
134 None
135 })
136 .flatten()
137 }
138
139 pub fn intersecting_ranges<'a, D, I>(
140 &'a self,
141 range: Range<(I, Bias)>,
142 snapshot: &'a MultiBufferSnapshot,
143 ) -> impl Iterator<Item = (Range<D>, &'a T)> + 'a
144 where
145 D: TextDimension,
146 I: ToOffset,
147 {
148 let start_bias = range.start.1;
149 let end_bias = range.end.1;
150 let start_offset = range.start.0.to_offset(snapshot);
151 let end_offset = range.end.0.to_offset(snapshot);
152
153 let mut cursor = snapshot.excerpts.cursor::<ExcerptSummary>();
154 cursor.seek(&start_offset, start_bias, &());
155 let start_excerpt_id = &cursor.start().excerpt_id;
156 let start_ix = match self
157 .child_maps
158 .binary_search_by_key(&start_excerpt_id, |e| &e.0)
159 {
160 Ok(ix) | Err(ix) => ix,
161 };
162
163 let mut entry_ranges = None;
164 let mut entries = self.child_maps[start_ix..].iter();
165 std::iter::from_fn(move || loop {
166 match &mut entry_ranges {
167 None => {
168 let (excerpt_id, text_map) = entries.next()?;
169 cursor.seek(excerpt_id, Bias::Left, &());
170 if cursor.start().text.bytes >= end_offset {
171 return None;
172 }
173
174 if let Some(excerpt) = cursor.item() {
175 if excerpt.id == *excerpt_id {
176 let mut excerpt_start = D::from_text_summary(&cursor.start().text);
177 excerpt_start.add_summary(&excerpt.header_summary(), &());
178
179 let excerpt_start_offset = cursor.start().text.bytes;
180 let excerpt_end_offset = cursor.end(&()).text.bytes;
181 let excerpt_buffer_range = excerpt.range.to_offset(&excerpt.buffer);
182
183 let start;
184 if start_offset >= excerpt_start_offset {
185 start = (
186 excerpt_buffer_range.start + start_offset
187 - excerpt_start_offset,
188 start_bias,
189 );
190 } else {
191 start = (excerpt_buffer_range.start, Bias::Left);
192 }
193
194 let end;
195 if end_offset <= excerpt_end_offset {
196 end = (
197 excerpt_buffer_range.start + end_offset - excerpt_start_offset,
198 end_bias,
199 );
200 } else {
201 end = (excerpt_buffer_range.end, Bias::Right);
202 }
203
204 entry_ranges = Some(
205 text_map
206 .intersecting_ranges(start..end, &excerpt.buffer)
207 .map(move |(range, value)| {
208 let mut full_range =
209 excerpt_start.clone()..excerpt_start.clone();
210 full_range.start.add_assign(&range.start);
211 full_range.end.add_assign(&range.end);
212 (full_range, value)
213 }),
214 );
215 }
216 }
217 }
218 Some(ranges) => {
219 if let Some(item) = ranges.next() {
220 return Some(item);
221 } else {
222 entry_ranges.take();
223 }
224 }
225 }
226 })
227 }
228
229 pub fn min_by_key<'a, D, F, K>(
230 &self,
231 snapshot: &'a MultiBufferSnapshot,
232 extract_key: F,
233 ) -> Option<(Range<D>, &T)>
234 where
235 D: TextDimension,
236 F: FnMut(&T) -> K,
237 K: Ord,
238 {
239 self.min_or_max_by_key(snapshot, Ordering::Less, extract_key)
240 }
241
242 pub fn max_by_key<'a, D, F, K>(
243 &self,
244 snapshot: &'a MultiBufferSnapshot,
245 extract_key: F,
246 ) -> Option<(Range<D>, &T)>
247 where
248 D: TextDimension,
249 F: FnMut(&T) -> K,
250 K: Ord,
251 {
252 self.min_or_max_by_key(snapshot, Ordering::Greater, extract_key)
253 }
254
255 fn min_or_max_by_key<'a, D, F, K>(
256 &self,
257 snapshot: &'a MultiBufferSnapshot,
258 target_ordering: Ordering,
259 mut extract_key: F,
260 ) -> Option<(Range<D>, &T)>
261 where
262 D: TextDimension,
263 F: FnMut(&T) -> K,
264 K: Ord,
265 {
266 let mut cursor = snapshot.excerpts.cursor::<ExcerptSummary>();
267 let mut max = None;
268 for (excerpt_id, text_map) in &self.child_maps {
269 cursor.seek(excerpt_id, Bias::Left, &());
270 if let Some(excerpt) = cursor.item() {
271 if excerpt.id == *excerpt_id {
272 if let Some((range, value)) =
273 text_map.max_by_key(&excerpt.buffer, &mut extract_key)
274 {
275 if max.as_ref().map_or(true, |(_, max_value)| {
276 extract_key(value).cmp(&extract_key(*max_value)) == target_ordering
277 }) {
278 let mut excerpt_start = D::from_text_summary(&cursor.start().text);
279 excerpt_start.add_summary(&excerpt.header_summary(), &());
280 let mut full_range = excerpt_start.clone()..excerpt_start.clone();
281 full_range.start.add_assign(&range.start);
282 full_range.end.add_assign(&range.end);
283 max = Some((full_range, value));
284 }
285 }
286 }
287 }
288 }
289 max
290 }
291}
292
293impl AnchorRangeSet {
294 pub fn len(&self) -> usize {
295 self.0.len()
296 }
297
298 pub fn ranges<'a, D>(
299 &'a self,
300 content: &'a MultiBufferSnapshot,
301 ) -> impl 'a + Iterator<Item = Range<Point>>
302 where
303 D: TextDimension,
304 {
305 self.0.ranges(content).map(|(range, _)| range)
306 }
307}
308
309impl ToOffset for Anchor {
310 fn to_offset<'a>(&self, snapshot: &MultiBufferSnapshot) -> usize {
311 self.summary(snapshot)
312 }
313}
314
315impl ToPoint for Anchor {
316 fn to_point<'a>(&self, snapshot: &MultiBufferSnapshot) -> Point {
317 self.summary(snapshot)
318 }
319}
320
321pub trait AnchorRangeExt {
322 fn cmp(&self, b: &Range<Anchor>, buffer: &MultiBufferSnapshot) -> Result<Ordering>;
323 fn to_offset(&self, content: &MultiBufferSnapshot) -> Range<usize>;
324}
325
326impl AnchorRangeExt for Range<Anchor> {
327 fn cmp(&self, other: &Range<Anchor>, buffer: &MultiBufferSnapshot) -> Result<Ordering> {
328 Ok(match self.start.cmp(&other.start, buffer)? {
329 Ordering::Equal => other.end.cmp(&self.end, buffer)?,
330 ord @ _ => ord,
331 })
332 }
333
334 fn to_offset(&self, content: &MultiBufferSnapshot) -> Range<usize> {
335 self.start.to_offset(&content)..self.end.to_offset(&content)
336 }
337}