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

charon_lib/ast/meta/
spans.rs
