compiler/rustc_span/src/span_encoding.rs

   1 // Spans are encoded using 1-bit tag and 2 different encoding formats (one for each tag value).
   2 // One format is used for keeping span data inline,
   3 // another contains index into an out-of-line span interner.
   4 // The encoding format for inline spans were obtained by optimizing over crates in rustc/libstd.
   5 // See https://internals.rust-lang.org/t/rfc-compiler-refactoring-spans/1357/28
   6
   7 use crate::def_id::{DefIndex, LocalDefId};
   8 use crate::hygiene::SyntaxContext;
   9 use crate::SPAN_TRACK;
  10 use crate::{BytePos, SpanData};
  11
  12 use rustc_data_structures::fx::FxIndexSet;
  13
  14 /// A compressed span.
  15 ///
  16 /// Whereas [`SpanData`] is 16 bytes, which is a bit too big to stick everywhere, `Span`
  17 /// is a form that only takes up 8 bytes, with less space for the length, parent and
  18 /// context. The vast majority (99.9%+) of `SpanData` instances will fit within
  19 /// those 8 bytes; any `SpanData` whose fields don't fit into a `Span` are
  20 /// stored in a separate interner table, and the `Span` will index into that
  21 /// table. Interning is rare enough that the cost is low, but common enough
  22 /// that the code is exercised regularly.
  23 ///
  24 /// An earlier version of this code used only 4 bytes for `Span`, but that was
  25 /// slower because only 80--90% of spans could be stored inline (even less in
  26 /// very large crates) and so the interner was used a lot more.
  27 ///
  28 /// Inline (compressed) format with no parent:
  29 /// - `span.base_or_index == span_data.lo`
  30 /// - `span.len_or_tag == len == span_data.hi - span_data.lo` (must be `<= MAX_LEN`)
  31 /// - `span.ctxt_or_tag == span_data.ctxt` (must be `<= MAX_CTXT`)
  32 ///
  33 /// Interned format with inline `SyntaxContext`:
  34 /// - `span.base_or_index == index` (indexes into the interner table)
  35 /// - `span.len_or_tag == LEN_TAG` (high bit set, all other bits are zero)
  36 /// - `span.ctxt_or_tag == span_data.ctxt` (must be `<= MAX_CTXT`)
  37 ///
  38 /// Inline (compressed) format with root context:
  39 /// - `span.base_or_index == span_data.lo`
  40 /// - `span.len_or_tag == len == span_data.hi - span_data.lo` (must be `<= MAX_LEN`)
  41 /// - `span.len_or_tag` has top bit (`PARENT_MASK`) set
  42 /// - `span.ctxt == span_data.parent` (must be `<= MAX_CTXT`)
  43 ///
  44 /// Interned format:
  45 /// - `span.base_or_index == index` (indexes into the interner table)
  46 /// - `span.len_or_tag == LEN_TAG` (high bit set, all other bits are zero)
  47 /// - `span.ctxt_or_tag == CTXT_TAG`
  48 ///
  49 /// The inline form uses 0 for the tag value (rather than 1) so that we don't
  50 /// need to mask out the tag bit when getting the length, and so that the
  51 /// dummy span can be all zeroes.
  52 ///
  53 /// Notes about the choice of field sizes:
  54 /// - `base` is 32 bits in both `Span` and `SpanData`, which means that `base`
  55 ///   values never cause interning. The number of bits needed for `base`
  56 ///   depends on the crate size. 32 bits allows up to 4 GiB of code in a crate.
  57 /// - `len` is 15 bits in `Span` (a u16, minus 1 bit for the tag) and 32 bits
  58 ///   in `SpanData`, which means that large `len` values will cause interning.
  59 ///   The number of bits needed for `len` does not depend on the crate size.
  60 ///   The most common numbers of bits for `len` are from 0 to 7, with a peak usually
  61 ///   at 3 or 4, and then it drops off quickly from 8 onwards. 15 bits is enough
  62 ///   for 99.99%+ of cases, but larger values (sometimes 20+ bits) might occur
  63 ///   dozens of times in a typical crate.
  64 /// - `ctxt_or_tag` is 16 bits in `Span` and 32 bits in `SpanData`, which means that
  65 ///   large `ctxt` values will cause interning. The number of bits needed for
  66 ///   `ctxt` values depend partly on the crate size and partly on the form of
  67 ///   the code. No crates in `rustc-perf` need more than 15 bits for `ctxt_or_tag`,
  68 ///   but larger crates might need more than 16 bits.
  69 ///
  70 /// In order to reliably use parented spans in incremental compilation,
  71 /// the dependency to the parent definition's span. This is performed
  72 /// using the callback `SPAN_TRACK` to access the query engine.
  73 ///
  74 #[derive(Clone, Copy, Eq, PartialEq, Hash)]
  75 #[rustc_pass_by_value]
  76 pub struct Span {
  77     base_or_index: u32,
  78     len_or_tag: u16,
  79     ctxt_or_tag: u16,
  80 }
  81
  82 const LEN_TAG: u16 = 0b1111_1111_1111_1111;
  83 const PARENT_MASK: u16 = 0b1000_0000_0000_0000;
  84 const MAX_LEN: u32 = 0b0111_1111_1111_1111;
  85 const CTXT_TAG: u32 = 0b1111_1111_1111_1111;
  86 const MAX_CTXT: u32 = CTXT_TAG - 1;
  87
  88 /// Dummy span, both position and length are zero, syntax context is zero as well.
  89 pub const DUMMY_SP: Span = Span { base_or_index: 0, len_or_tag: 0, ctxt_or_tag: 0 };
  90
  91 impl Span {
  92     #[inline]
  93     pub fn new(
  94         mut lo: BytePos,
  95         mut hi: BytePos,
  96         ctxt: SyntaxContext,
  97         parent: Option<LocalDefId>,
  98     ) -> Self {
  99         if lo > hi {
 100             std::mem::swap(&mut lo, &mut hi);
 101         }
 102
 103         let (base, len, ctxt2) = (lo.0, hi.0 - lo.0, ctxt.as_u32());
 104
 105         if len <= MAX_LEN && ctxt2 <= MAX_CTXT {
 106             let len_or_tag = len as u16;
 107             debug_assert_eq!(len_or_tag & PARENT_MASK, 0);
 108
 109             if let Some(parent) = parent {
 110                 // Inline format with parent.
 111                 let len_or_tag = len_or_tag | PARENT_MASK;
 112                 let parent2 = parent.local_def_index.as_u32();
 113                 if ctxt2 == SyntaxContext::root().as_u32() && parent2 <= MAX_CTXT {
 114                     return Span { base_or_index: base, len_or_tag, ctxt_or_tag: parent2 as u16 };
 115                 }
 116             } else {
 117                 // Inline format with ctxt.
 118                 return Span {
 119                     base_or_index: base,
 120                     len_or_tag: len as u16,
 121                     ctxt_or_tag: ctxt2 as u16,
 122                 };
 123             }
 124         }
 125
 126         // Interned format.
 127         let index =
 128             with_span_interner(|interner| interner.intern(&SpanData { lo, hi, ctxt, parent }));
 129         let ctxt_or_tag = if ctxt2 <= MAX_CTXT { ctxt2 } else { CTXT_TAG } as u16;
 130         Span { base_or_index: index, len_or_tag: LEN_TAG, ctxt_or_tag }
 131     }
 132
 133     #[inline]
 134     pub fn data(self) -> SpanData {
 135         let data = self.data_untracked();
 136         if let Some(parent) = data.parent {
 137             (*SPAN_TRACK)(parent);
 138         }
 139         data
 140     }
 141
 142     /// Internal function to translate between an encoded span and the expanded representation.
 143     /// This function must not be used outside the incremental engine.
 144     #[inline]
 145     pub fn data_untracked(self) -> SpanData {
 146         if self.len_or_tag != LEN_TAG {
 147             // Inline format.
 148             if self.len_or_tag & PARENT_MASK == 0 {
 149                 debug_assert!(self.len_or_tag as u32 <= MAX_LEN);
 150                 SpanData {
 151                     lo: BytePos(self.base_or_index),
 152                     hi: BytePos(self.base_or_index + self.len_or_tag as u32),
 153                     ctxt: SyntaxContext::from_u32(self.ctxt_or_tag as u32),
 154                     parent: None,
 155                 }
 156             } else {
 157                 let len = self.len_or_tag & !PARENT_MASK;
 158                 debug_assert!(len as u32 <= MAX_LEN);
 159                 let parent =
 160                     LocalDefId { local_def_index: DefIndex::from_u32(self.ctxt_or_tag as u32) };
 161                 SpanData {
 162                     lo: BytePos(self.base_or_index),
 163                     hi: BytePos(self.base_or_index + len as u32),
 164                     ctxt: SyntaxContext::root(),
 165                     parent: Some(parent),
 166                 }
 167             }
 168         } else {
 169             // Interned format.
 170             let index = self.base_or_index;
 171             with_span_interner(|interner| interner.spans[index as usize])
 172         }
 173     }
 174
 175     /// This function is used as a fast path when decoding the full `SpanData` is not necessary.
 176     #[inline]
 177     pub fn ctxt(self) -> SyntaxContext {
 178         let ctxt_or_tag = self.ctxt_or_tag as u32;
 179         if ctxt_or_tag <= MAX_CTXT {
 180             if self.len_or_tag == LEN_TAG || self.len_or_tag & PARENT_MASK == 0 {
 181                 // Inline format or interned format with inline ctxt.
 182                 SyntaxContext::from_u32(ctxt_or_tag)
 183             } else {
 184                 // Inline format or interned format with inline parent.
 185                 // We know that the SyntaxContext is root.
 186                 SyntaxContext::root()
 187             }
 188         } else {
 189             // Interned format.
 190             let index = self.base_or_index;
 191             with_span_interner(|interner| interner.spans[index as usize].ctxt)
 192         }
 193     }
 194 }
 195
 196 #[derive(Default)]
 197 pub struct SpanInterner {
 198     spans: FxIndexSet<SpanData>,
 199 }
 200
 201 impl SpanInterner {
 202     fn intern(&mut self, span_data: &SpanData) -> u32 {
 203         let (index, _) = self.spans.insert_full(*span_data);
 204         index as u32
 205     }
 206 }
 207
 208 // If an interner exists, return it. Otherwise, prepare a fresh one.
 209 #[inline]
 210 fn with_span_interner<T, F: FnOnce(&mut SpanInterner) -> T>(f: F) -> T {
 211     crate::with_session_globals(|session_globals| f(&mut session_globals.span_interner.lock()))
 212 }