charon_lib/ast/meta/
spans.rs

1use crate::utils::dedup::*;
2use derive_generic_visitor::{ControlFlow, Drive, DriveMut, DriveTwo, Visit, VisitMut, VisitTwo};
3use serde::{Deserialize, Serialize};
4use serde_state::{DeserializeState, SerializeState};
5use std::collections::HashMap;
6use std::sync::{LazyLock, Mutex};
7use std::{borrow::Cow, cmp::Ordering, ops::Range, path::PathBuf};
8
9generate_index_type!(FileId);
10
11/// A filename.
12#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
13#[derive(Serialize, Deserialize, Drive, DriveMut, DriveTwo)]
14pub enum FileName {
15    /// A remapped path (namely paths into stdlib)
16    Virtual(PathBuf),
17    /// A local path (a file coming from the current crate for instance)
18    Local(PathBuf),
19    /// A "not real" file name (macro, query, etc.)
20    NotReal(String),
21}
22
23#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
24#[derive(Serialize, Deserialize, Drive, DriveMut, DriveTwo)]
25pub struct File {
26    /// The file identifier.
27    #[cfg_attr(feature = "charon_on_charon", charon::opaque)]
28    pub id: FileId,
29    /// The path to the file.
30    pub name: FileName,
31    /// Name of the crate this file comes from.
32    pub crate_name: String,
33    /// The contents of the source file, as seen by rustc at the time of translation.
34    /// Some files don't have contents.
35    pub contents: Option<String>,
36}
37
38#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
39#[derive(Serialize, Deserialize, Drive, DriveMut, DriveTwo)]
40pub struct Loc {
41    /// The (1-based) line number.
42    pub line: u32,
43    /// The (0-based) column offset.
44    pub col: u32,
45}
46
47/// A snippet of source code within a file.
48#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
49#[derive(Serialize, Deserialize, Drive, DriveMut, DriveTwo)]
50pub struct SpanData {
51    #[cfg_attr(feature = "charon_on_charon", charon::rename("file"))]
52    pub file_id: FileId,
53    #[cfg_attr(feature = "charon_on_charon", charon::rename("beg_loc"))]
54    pub beg: Loc,
55    #[cfg_attr(feature = "charon_on_charon", charon::rename("end_loc"))]
56    pub end: Loc,
57}
58
59/// A snippet of source code within a file, along with the place the code was generated from in
60/// case of macro expansion. This is a pair of the span itself (`data`) and an optional
61/// "generated from" span (`generated_from_span`).
62///
63/// For code coming from a macro expansion, `data` is the span of the macro before expansion, i.e.
64/// the location where the user wrote the call to the macro, and `generated_from_span` is where
65/// the code actually comes from.
66///
67/// Ex:
68/// ```text
69/// // Below, we consider the spans for the statements inside `test`
70///
71/// //   the statement we consider, which gets inlined in `test`
72///                          VV
73/// macro_rules! macro { ... st ... } // `generated_from_span` refers to this location
74///
75/// fn test() {
76///     macro!(); // <-- `data` refers to this location
77/// }
78/// ```
79// A `Span` is stored inline in most AST nodes, so we care about its size. Instead of storing the
80// two `SpanData`s, we pack the common case into 8 bytes:
81// ```text
82//     63     62..47     47..27      27..17    17..10     10..0
83//   +------+----------+-----------+---------+----------+---------+
84//   | wide | file(16) | beg.line  | beg.col | nb lines | end.col |
85//   +------+----------+-----------+---------+----------+---------+
86// ```
87// The spans that don't fit this layout -- because they come from a macro expansion, span many
88// lines, or point into a very large file or a very long line -- are stored in `WIDE_SPANS` and
89// referred to by index.
90// Some numbers to back this up:
91// - For serde 1.0.228, out of 246K spans, 12 didn't fit
92// - For regex 1.11.1, out of 136K spans, 25 didn't fit
93// - For syn 2.0.104, out of 800K spans, 36 didn't fit
94#[derive(Copy, Clone, PartialEq, Eq, Hash)]
95pub struct Span(u64);
96
97/// Bit layout of the packed representation of [`Span`].
98mod pack {
99    /// Set when the rest of the bits is an index into `WIDE_SPANS` instead of a packed span.
100    pub const WIDE_FLAG: u64 = 1 << 63;
101    pub const FILE_BITS: u32 = 16;
102    pub const LINE_BITS: u32 = 20;
103    pub const COL_BITS: u32 = 10;
104    pub const NLINES_BITS: u32 = 7;
105
106    pub const END_COL_SHIFT: u32 = 0;
107    pub const NLINES_SHIFT: u32 = END_COL_SHIFT + COL_BITS;
108    pub const BEG_COL_SHIFT: u32 = NLINES_SHIFT + NLINES_BITS;
109    pub const BEG_LINE_SHIFT: u32 = BEG_COL_SHIFT + COL_BITS;
110    pub const FILE_SHIFT: u32 = BEG_LINE_SHIFT + LINE_BITS;
111
112    /// Extract the `bits` bits of `x` starting at `shift`.
113    #[inline]
114    pub fn get(x: u64, shift: u32, bits: u32) -> u32 {
115        ((x >> shift) & ((1 << bits) - 1)) as u32
116    }
117
118    /// Put `x` in its place, if it fits in `bits` bits.
119    #[inline]
120    pub fn put(x: u32, shift: u32, bits: u32) -> Option<u64> {
121        (u64::from(x) < (1 << bits)).then_some(u64::from(x) << shift)
122    }
123}
124
125/// A [`Span`] with its contents laid out, used for serialization and unpacking into a
126/// more readable format.
127#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
128#[derive(
129    Serialize,
130    Deserialize,
131    SerializeState,
132    DeserializeState,
133    Drive,
134    DriveMut,
135    DriveTwo
136)]
137#[cfg_attr(feature = "charon_on_charon", charon::rename("Span"))]
138#[serde_state(stateless)]
139pub struct SerializedSpan {
140    /// The source code span; for code coming from a macro expansion, the location of the macro
141    /// call.
142    pub data: SpanData,
143    /// Where the code actually comes from, in case of macro expansion/inlining/etc.
144    pub generated_from_span: Option<SpanData>,
145}
146
147/// The spans that don't fit the packed representation of [`Span`]. We store them here once and
148/// refer to them by index. Entries are deduplicated so equal spans have equal representations.
149///
150/// This table is global and never shrinks. In practice this is fine; for instance, syn 2.0.104
151/// only had distinct 36 spans here.
152static WIDE_SPANS: LazyLock<Mutex<WideSpans>> = LazyLock::new(Default::default);
153
154#[derive(Default)]
155struct WideSpans {
156    spans: Vec<SerializedSpan>,
157    indices: HashMap<SerializedSpan, u64>,
158}
159
160impl Span {
161    #[inline]
162    pub fn new(data: SpanData, generated_from_span: Option<SpanData>) -> Self {
163        Self::from_unpacked(SerializedSpan {
164            data,
165            generated_from_span,
166        })
167    }
168
169    /// The source code span; for code coming from a macro expansion, the location of the macro
170    /// call.
171    #[inline]
172    pub fn data(self) -> SpanData {
173        self.unpack().data
174    }
175
176    /// Where the code actually comes from, in case of macro expansion/inlining/etc.
177    #[inline]
178    pub fn generated_from_span(self) -> Option<SpanData> {
179        self.unpack().generated_from_span
180    }
181
182    fn from_unpacked(span: SerializedSpan) -> Self {
183        match Self::pack(span) {
184            Some(packed) => packed,
185            None => Self::store_wide(span),
186        }
187    }
188
189    fn pack(span: SerializedSpan) -> Option<Self> {
190        use pack::*;
191        if span.generated_from_span.is_some() {
192            return None;
193        }
194        let data = span.data;
195        let nb_lines = data.end.line.checked_sub(data.beg.line)?;
196        let bits = put(data.file_id.index() as u32, FILE_SHIFT, FILE_BITS)?
197            | put(data.beg.line, BEG_LINE_SHIFT, LINE_BITS)?
198            | put(data.beg.col, BEG_COL_SHIFT, COL_BITS)?
199            | put(nb_lines, NLINES_SHIFT, NLINES_BITS)?
200            | put(data.end.col, END_COL_SHIFT, COL_BITS)?;
201        Some(Span(bits))
202    }
203
204    fn unpack(self) -> SerializedSpan {
205        use pack::*;
206        if self.0 & WIDE_FLAG != 0 {
207            return WIDE_SPANS.lock().unwrap().spans[(self.0 ^ WIDE_FLAG) as usize];
208        }
209        let beg_line = get(self.0, BEG_LINE_SHIFT, LINE_BITS);
210        let data = SpanData {
211            file_id: FileId::from_raw(get(self.0, FILE_SHIFT, FILE_BITS)),
212            beg: Loc {
213                line: beg_line,
214                col: get(self.0, BEG_COL_SHIFT, COL_BITS),
215            },
216            end: Loc {
217                line: beg_line + get(self.0, NLINES_SHIFT, NLINES_BITS),
218                col: get(self.0, END_COL_SHIFT, COL_BITS),
219            },
220        };
221        SerializedSpan {
222            data,
223            generated_from_span: None,
224        }
225    }
226
227    #[cold]
228    fn store_wide(span: SerializedSpan) -> Self {
229        let mut wide_spans = WIDE_SPANS.lock().unwrap();
230        let index = match wide_spans.indices.get(&span) {
231            Some(index) => *index,
232            None => {
233                let index = wide_spans.spans.len() as u64;
234                assert!(index & pack::WIDE_FLAG == 0, "too many wide spans");
235                wide_spans.spans.push(span);
236                wide_spans.indices.insert(span, index);
237                index
238            }
239        };
240        Span(index | pack::WIDE_FLAG)
241    }
242}
243
244impl Ord for Span {
245    fn cmp(&self, other: &Self) -> Ordering {
246        if (self.0 | other.0) & pack::WIDE_FLAG == 0 {
247            // Both spans are packed: the bit layout is such that comparing the packed values is
248            // the same as comparing `(file, beg, end)`, so take the fast path.
249            self.0.cmp(&other.0)
250        } else {
251            self.unpack().cmp(&other.unpack())
252        }
253    }
254}
255impl PartialOrd for Span {
256    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
257        Some(self.cmp(other))
258    }
259}
260
261impl Serialize for Span {
262    fn serialize<S: serde::Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
263        SerDedup::Untagged(self.unpack()).serialize(serializer)
264    }
265}
266impl<'de> Deserialize<'de> for Span {
267    fn deserialize<D: serde::Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
268        use serde::de::Error;
269        match SerDedup::<SerializedSpan>::deserialize(deserializer)? {
270            SerDedup::Untagged(span) => Ok(Span::from_unpacked(span)),
271            SerDedup::Value { .. } | SerDedup::Deduplicated { .. } => {
272                Err(D::Error::custom(stateless_deserialize_error::<Span>()))
273            }
274        }
275    }
276}
277impl<State: DedupSerializerState> SerializeState<State> for Span {
278    fn serialize_state<S: serde::Serializer>(
279        &self,
280        state: &State,
281        serializer: S,
282    ) -> Result<S::Ok, S::Error> {
283        serialize_dedup(self, self.unpack(), state, serializer)
284    }
285}
286impl<'de, State: DedupSerializerState> DeserializeState<'de, State> for Span {
287    fn deserialize_state<D: serde::Deserializer<'de>>(
288        state: &State,
289        deserializer: D,
290    ) -> Result<Self, D::Error> {
291        deserialize_dedup(state, deserializer, Span::from_unpacked)
292    }
293}
294
295impl std::fmt::Debug for Span {
296    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
297        let span = self.unpack();
298        f.debug_struct("Span")
299            .field("data", &span.data)
300            .field("generated_from_span", &span.generated_from_span)
301            .finish()
302    }
303}
304
305impl<'s, V> Drive<'s, V> for Span
306where
307    V: for<'a> Visit<'a, SerializedSpan> + for<'a> Visit<'a, Option<SerializedSpan>>,
308{
309    fn drive_inner(&'s self, v: &mut V) -> ControlFlow<V::Break> {
310        v.visit(&self.unpack())
311    }
312}
313impl<'s, V> DriveMut<'s, V> for Span
314where
315    V: for<'a> VisitMut<'a, SerializedSpan> + for<'a> VisitMut<'a, Option<SerializedSpan>>,
316{
317    fn drive_inner_mut(&'s mut self, v: &mut V) -> ControlFlow<V::Break> {
318        let mut span = self.unpack();
319        let res = v.visit(&mut span);
320        *self = Span::from_unpacked(span);
321        res
322    }
323}
324impl<'s, V> DriveTwo<'s, V> for Span
325where
326    V: for<'a> VisitTwo<'a, SerializedSpan> + for<'a> VisitTwo<'a, Option<SerializedSpan>>,
327{
328    fn drive_two_inner(&'s self, other: &'s Self, v: &mut V) -> ControlFlow<V::Break> {
329        v.visit(&self.unpack(), &other.unpack())
330    }
331}
332
333/// Given a line number within a source file, get the byte of the start of the line. Obviously not
334/// efficient to do many times, but this is used is diagnostic paths only. The line numer is
335/// expected to be 1-based.
336fn line_to_start_byte(source: &str, line_nbr: usize) -> usize {
337    let mut cur_byte = 0;
338    for (i, line) in source.split_inclusive('\n').enumerate() {
339        if line_nbr == i + 1 {
340            break;
341        }
342        cur_byte += line.len();
343    }
344    cur_byte
345}
346
347impl Loc {
348    const fn dummy() -> Self {
349        Loc { line: 0, col: 0 }
350    }
351
352    fn min(l0: &Loc, l1: &Loc) -> Loc {
353        match l0.line.cmp(&l1.line) {
354            Ordering::Equal => Loc {
355                line: l0.line,
356                col: std::cmp::min(l0.col, l1.col),
357            },
358            Ordering::Less => *l0,
359            Ordering::Greater => *l1,
360        }
361    }
362
363    fn max(l0: &Loc, l1: &Loc) -> Loc {
364        match l0.line.cmp(&l1.line) {
365            Ordering::Equal => Loc {
366                line: l0.line,
367                col: std::cmp::max(l0.col, l1.col),
368            },
369            Ordering::Greater => *l0,
370            Ordering::Less => *l1,
371        }
372    }
373
374    pub fn to_byte(self, source: &str) -> usize {
375        line_to_start_byte(source, self.line as usize) + self.col as usize
376    }
377}
378
379impl SpanData {
380    pub const fn dummy() -> Self {
381        SpanData {
382            file_id: FileId::ZERO,
383            beg: Loc::dummy(),
384            end: Loc::dummy(),
385        }
386    }
387
388    /// Value with which we order `SpanDatas`s.
389    fn sort_key(&self) -> impl Ord {
390        (self.file_id, self.beg, self.end)
391    }
392
393    pub fn to_byte_range(self, source: &str) -> Range<usize> {
394        self.beg.to_byte(source)..self.end.to_byte(source)
395    }
396}
397
398/// Manual impls because `SpanData` is not orderable.
399impl PartialOrd for SpanData {
400    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
401        Some(self.cmp(other))
402    }
403}
404impl Ord for SpanData {
405    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
406        self.sort_key().cmp(&other.sort_key())
407    }
408}
409
410impl Span {
411    pub const fn dummy() -> Self {
412        // Every field of `SpanData::dummy()` packs to zero, so this is just zero!
413        // Actually tested below for correctness
414        Span(0)
415    }
416}
417
418/// Combine some span information (useful when we need to compute the
419/// span-information of, say, a sequence).
420pub fn combine_span(m0: &Span, m1: &Span) -> Span {
421    let (d0, d1) = (m0.data(), m1.data());
422    // Merge the spans
423    if d0.file_id == d1.file_id {
424        let data = SpanData {
425            file_id: d0.file_id,
426            beg: Loc::min(&d0.beg, &d1.beg),
427            end: Loc::max(&d0.end, &d1.end),
428        };
429
430        // We don't attempt to merge the "generated from" spans: they might
431        // come from different files, and even if they come from the same files
432        // they might come from different macros, etc.
433        Span::new(data, None)
434    } else {
435        // It happens that the spans don't come from the same file. In this
436        // situation, we just return the first span. TODO: improve this.
437        *m0
438    }
439}
440
441/// Combine all the span information in a slice.
442pub fn combine_span_iter<'a, T: Iterator<Item = &'a Span>>(mut ms: T) -> Span {
443    // The iterator should have a next element
444    let mut mc: Span = ms.next().copied().unwrap_or_default();
445    for m in ms {
446        mc = combine_span(&mc, m);
447    }
448
449    mc
450}
451
452impl FileName {
453    pub fn to_string(&self) -> Cow<'_, str> {
454        match self {
455            FileName::Virtual(path_buf) | FileName::Local(path_buf) => path_buf.to_string_lossy(),
456            FileName::NotReal(path) => Cow::Borrowed(path),
457        }
458    }
459}
460
461impl Default for Span {
462    fn default() -> Self {
463        Self::dummy()
464    }
465}
466
467/// `Span` is stored inline in most ast nodes, so its size matters
468#[test]
469fn span_is_small() {
470    assert_eq!(size_of::<Span>(), 8);
471}
472
473/// Check that `Span::dummy()` is correct.
474#[test]
475fn span_dummy_is_zero() {
476    assert_eq!(Span::dummy(), Span::new(SpanData::dummy(), None));
477    assert_eq!(Span::dummy().data(), SpanData::dummy());
478}
479
480/// Check that we roundtrip both the spans that fit the packed representation and the ones that
481/// don't.
482#[test]
483fn span_roundtrip() {
484    let data = |file: usize, beg: (u32, u32), end: (u32, u32)| SpanData {
485        file_id: FileId::from_usize(file),
486        beg: Loc {
487            line: beg.0,
488            col: beg.1,
489        },
490        end: Loc {
491            line: end.0,
492            col: end.1,
493        },
494    };
495    let packed = data(12, (34, 56), (78, 90));
496    let huge_file = data(1 << 20, (34, 56), (78, 90));
497    let long_line = data(12, (34, 5678), (78, 90));
498    let backwards = data(12, (78, 56), (34, 90));
499    for (d, generated) in [
500        (packed, None),
501        (packed, Some(packed)),
502        (huge_file, None),
503        (long_line, None),
504        (backwards, None),
505    ] {
506        let span = Span::new(d, generated);
507        assert_eq!(span.data(), d);
508        assert_eq!(span.generated_from_span(), generated);
509    }
510    // Only the first span above fits the packed representation.
511    assert!(Span::new(packed, None).0 & pack::WIDE_FLAG == 0);
512    // Equal spans have equal representations, even when they don't fit.
513    assert_eq!(Span::new(backwards, None), Span::new(backwards, None));
514}
charon_lib/ast/meta/spans.rs

charon_lib/ast/meta/
spans.rs
