span/
map.rs

1//! A map that maps a span to every position in a file. Usually maps a span to some range of positions.
2//! Allows bidirectional lookup.
3
4use std::{fmt, hash::Hash};
5
6use stdx::{always, itertools::Itertools};
7
8use crate::{
9    EditionedFileId, ErasedFileAstId, ROOT_ERASED_FILE_AST_ID, Span, SpanAnchor, SpanData,
10    SyntaxContext, TextRange, TextSize,
11};
12
13/// Maps absolute text ranges for the corresponding file to the relevant span data.
14#[derive(Debug, PartialEq, Eq, Clone, Hash)]
15pub struct SpanMap<S> {
16    /// The offset stored here is the *end* of the node.
17    spans: Vec<(TextSize, SpanData<S>)>,
18    /// Index of the matched macro arm on successful expansion for declarative macros.
19    // FIXME: Does it make sense to have this here?
20    pub matched_arm: Option<u32>,
21}
22
23impl<S> SpanMap<S>
24where
25    SpanData<S>: Copy,
26{
27    /// Creates a new empty [`SpanMap`].
28    pub fn empty() -> Self {
29        Self { spans: Vec::new(), matched_arm: None }
30    }
31
32    /// Finalizes the [`SpanMap`], shrinking its backing storage and validating that the offsets are
33    /// in order.
34    pub fn finish(&mut self) {
35        always!(
36            self.spans.iter().tuple_windows().all(|(a, b)| a.0 < b.0),
37            "spans are not in order"
38        );
39        self.spans.shrink_to_fit();
40    }
41
42    /// Pushes a new span onto the [`SpanMap`].
43    pub fn push(&mut self, offset: TextSize, span: SpanData<S>) {
44        if cfg!(debug_assertions)
45            && let Some(&(last_offset, _)) = self.spans.last()
46        {
47            assert!(
48                last_offset < offset,
49                "last_offset({last_offset:?}) must be smaller than offset({offset:?})"
50            );
51        }
52        self.spans.push((offset, span));
53    }
54
55    /// Returns all [`TextRange`]s that correspond to the given span.
56    ///
57    /// Note this does a linear search through the entire backing vector.
58    pub fn ranges_with_span_exact(
59        &self,
60        span: SpanData<S>,
61    ) -> impl Iterator<Item = (TextRange, S)> + '_
62    where
63        S: Copy,
64    {
65        self.spans.iter().enumerate().filter_map(move |(idx, &(end, s))| {
66            if !s.eq_ignoring_ctx(span) {
67                return None;
68            }
69            let start = idx.checked_sub(1).map_or(TextSize::new(0), |prev| self.spans[prev].0);
70            Some((TextRange::new(start, end), s.ctx))
71        })
72    }
73
74    /// Returns all [`TextRange`]s whose spans contain the given span.
75    ///
76    /// Note this does a linear search through the entire backing vector.
77    pub fn ranges_with_span(&self, span: SpanData<S>) -> impl Iterator<Item = (TextRange, S)> + '_
78    where
79        S: Copy,
80    {
81        self.spans.iter().enumerate().filter_map(move |(idx, &(end, s))| {
82            if s.anchor != span.anchor {
83                return None;
84            }
85            if !s.range.contains_range(span.range) {
86                return None;
87            }
88            let start = idx.checked_sub(1).map_or(TextSize::new(0), |prev| self.spans[prev].0);
89            Some((TextRange::new(start, end), s.ctx))
90        })
91    }
92
93    /// Returns the span at the given position.
94    pub fn span_at(&self, offset: TextSize) -> SpanData<S> {
95        let entry = self.spans.partition_point(|&(it, _)| it <= offset);
96        self.spans[entry].1
97    }
98
99    /// Returns the spans associated with the given range.
100    /// In other words, this will return all spans that correspond to all offsets within the given range.
101    pub fn spans_for_range(&self, range: TextRange) -> impl Iterator<Item = SpanData<S>> + '_ {
102        let (start, end) = (range.start(), range.end());
103        let start_entry = self.spans.partition_point(|&(it, _)| it <= start);
104        let end_entry = self.spans[start_entry..].partition_point(|&(it, _)| it <= end); // FIXME: this might be wrong?
105        self.spans[start_entry..][..end_entry].iter().map(|&(_, s)| s)
106    }
107
108    pub fn iter(&self) -> impl Iterator<Item = (TextSize, SpanData<S>)> + '_ {
109        self.spans.iter().copied()
110    }
111
112    /// Merges this span map with another span map, where `other` is inserted at (and replaces) `other_range`.
113    ///
114    /// The length of the replacement node needs to be `other_size`.
115    pub fn merge(&mut self, other_range: TextRange, other_size: TextSize, other: &SpanMap<S>) {
116        // I find the following diagram helpful to illustrate the bounds and why we use `<` or `<=`:
117        // --------------------------------------------------------------------
118        //   1   3   5   6   7   10    11          <-- offsets we store
119        // 0-1 1-3 3-5 5-6 6-7 7-10 10-11          <-- ranges these offsets refer to
120        //       3   ..      7                     <-- other_range
121        //         3-5 5-6 6-7                     <-- ranges we replace (len = 7-3 = 4)
122        //         ^^^^^^^^^^^ ^^^^^^^^^^
123        //           remove       shift
124        //   2   3   5   9                         <-- offsets we insert
125        // 0-2 2-3 3-5 5-9                         <-- ranges we insert (other_size = 9-0 = 9)
126        // ------------------------------------
127        //   1   3
128        // 0-1 1-3                                 <-- these remain intact
129        //           5   6   8   12
130        //         3-5 5-6 6-8 8-12                <-- we shift these by other_range.start() and insert them
131        //                             15    16
132        //                          12-15 15-16    <-- we shift these by other_size-other_range.len() = 9-4 = 5
133        // ------------------------------------
134        //   1   3   5   6   8   12    15    16    <-- final offsets we store
135        // 0-1 1-3 3-5 5-6 6-8 8-12 12-15 15-16    <-- final ranges
136
137        self.spans.retain_mut(|(offset, _)| {
138            if other_range.start() < *offset && *offset <= other_range.end() {
139                false
140            } else {
141                if *offset > other_range.end() {
142                    *offset += other_size;
143                    *offset -= other_range.len();
144                }
145                true
146            }
147        });
148
149        self.spans
150            .extend(other.spans.iter().map(|&(offset, span)| (offset + other_range.start(), span)));
151
152        self.spans.sort_unstable_by_key(|&(offset, _)| offset);
153
154        // Matched arm info is no longer correct once we have multiple macros.
155        self.matched_arm = None;
156    }
157}
158
159#[cfg(not(no_salsa_async_drops))]
160impl<S> Drop for SpanMap<S> {
161    fn drop(&mut self) {
162        struct SendPtr(*mut [()]);
163        unsafe impl Send for SendPtr {}
164        static SPAN_MAP_DROP_THREAD: std::sync::OnceLock<
165            std::sync::mpsc::Sender<(SendPtr, fn(SendPtr))>,
166        > = std::sync::OnceLock::new();
167        SPAN_MAP_DROP_THREAD
168            .get_or_init(|| {
169                let (sender, receiver) = std::sync::mpsc::channel::<(SendPtr, fn(SendPtr))>();
170                std::thread::Builder::new()
171                    .name("SpanMapDropper".to_owned())
172                    .spawn(move || receiver.iter().for_each(|(b, drop)| drop(b)))
173                    .unwrap();
174                sender
175            })
176            .send((
177                unsafe {
178                    SendPtr(std::mem::transmute::<*mut [(TextSize, SpanData<S>)], *mut [()]>(
179                        Box::<[(TextSize, SpanData<S>)]>::into_raw(
180                            std::mem::take(&mut self.spans).into_boxed_slice(),
181                        ),
182                    ))
183                },
184                |b: SendPtr| {
185                    _ = unsafe {
186                        Box::from_raw(std::mem::transmute::<
187                            *mut [()],
188                            *mut [(TextSize, SpanData<S>)],
189                        >(b.0))
190                    }
191                },
192            ))
193            .unwrap();
194    }
195}
196
197#[derive(PartialEq, Eq, Hash, Debug)]
198pub struct RealSpanMap {
199    file_id: EditionedFileId,
200    /// Invariant: Sorted vec over TextSize
201    // FIXME: SortedVec<(TextSize, ErasedFileAstId)>?
202    pairs: Box<[(TextSize, ErasedFileAstId)]>,
203    end: TextSize,
204}
205
206impl fmt::Display for RealSpanMap {
207    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
208        writeln!(f, "RealSpanMap({:?}):", self.file_id)?;
209        for span in self.pairs.iter() {
210            writeln!(f, "{}: {:#?}", u32::from(span.0), span.1)?;
211        }
212        Ok(())
213    }
214}
215
216impl RealSpanMap {
217    /// Creates a real file span map that returns absolute ranges (relative ranges to the root ast id).
218    pub fn absolute(file_id: EditionedFileId) -> Self {
219        RealSpanMap {
220            file_id,
221            pairs: Box::from([(TextSize::new(0), ROOT_ERASED_FILE_AST_ID)]),
222            end: TextSize::new(!0),
223        }
224    }
225
226    pub fn from_file(
227        file_id: EditionedFileId,
228        pairs: Box<[(TextSize, ErasedFileAstId)]>,
229        end: TextSize,
230    ) -> Self {
231        Self { file_id, pairs, end }
232    }
233
234    pub fn span_for_range(&self, range: TextRange) -> Span {
235        assert!(
236            range.end() <= self.end,
237            "range {range:?} goes beyond the end of the file {:?}",
238            self.end
239        );
240        let start = range.start();
241        let idx = self
242            .pairs
243            .binary_search_by(|&(it, _)| it.cmp(&start).then(std::cmp::Ordering::Less))
244            .unwrap_err();
245        let (offset, ast_id) = self.pairs[idx - 1];
246        Span {
247            range: range - offset,
248            anchor: SpanAnchor { file_id: self.file_id, ast_id },
249            ctx: SyntaxContext::root(self.file_id.edition()),
250        }
251    }
252}
span/map.rs

span/
map.rs
