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::hygiene::SyntaxContext;
   8 use crate::SESSION_GLOBALS;
   9 use crate::{BytePos, SpanData};
  10
  11 use rustc_data_structures::fx::FxIndexSet;
  12
  13 /// A compressed span.
  14 ///
  15 /// Whereas [`SpanData`] is 12 bytes, which is a bit too big to stick everywhere, `Span`
  16 /// is a form that only takes up 8 bytes, with less space for the length and
  17 /// context. The vast majority (99.9%+) of `SpanData` instances will fit within
  18 /// those 8 bytes; any `SpanData` whose fields don't fit into a `Span` are
  19 /// stored in a separate interner table, and the `Span` will index into that
  20 /// table. Interning is rare enough that the cost is low, but common enough
  21 /// that the code is exercised regularly.
  22 ///
  23 /// An earlier version of this code used only 4 bytes for `Span`, but that was
  24 /// slower because only 80--90% of spans could be stored inline (even less in
  25 /// very large crates) and so the interner was used a lot more.
  26 ///
  27 /// Inline (compressed) format:
  28 /// - `span.base_or_index == span_data.lo`
  29 /// - `span.len_or_tag == len == span_data.hi - span_data.lo` (must be `<= MAX_LEN`)
  30 /// - `span.ctxt == span_data.ctxt` (must be `<= MAX_CTXT`)
  31 ///
  32 /// Interned format:
  33 /// - `span.base_or_index == index` (indexes into the interner table)
  34 /// - `span.len_or_tag == LEN_TAG` (high bit set, all other bits are zero)
  35 /// - `span.ctxt == 0`
  36 ///
  37 /// The inline form uses 0 for the tag value (rather than 1) so that we don't
  38 /// need to mask out the tag bit when getting the length, and so that the
  39 /// dummy span can be all zeroes.
  40 ///
  41 /// Notes about the choice of field sizes:
  42 /// - `base` is 32 bits in both `Span` and `SpanData`, which means that `base`
  43 ///   values never cause interning. The number of bits needed for `base`
  44 ///   depends on the crate size. 32 bits allows up to 4 GiB of code in a crate.
  45 /// - `len` is 15 bits in `Span` (a u16, minus 1 bit for the tag) and 32 bits
  46 ///   in `SpanData`, which means that large `len` values will cause interning.
  47 ///   The number of bits needed for `len` does not depend on the crate size.
  48 ///   The most common numbers of bits for `len` are from 0 to 7, with a peak usually
  49 ///   at 3 or 4, and then it drops off quickly from 8 onwards. 15 bits is enough
  50 ///   for 99.99%+ of cases, but larger values (sometimes 20+ bits) might occur
  51 ///   dozens of times in a typical crate.
  52 /// - `ctxt` is 16 bits in `Span` and 32 bits in `SpanData`, which means that
  53 ///   large `ctxt` values will cause interning. The number of bits needed for
  54 ///   `ctxt` values depend partly on the crate size and partly on the form of
  55 ///   the code. No crates in `rustc-perf` need more than 15 bits for `ctxt`,
  56 ///   but larger crates might need more than 16 bits.
  57 ///
  58 #[derive(Clone, Copy, Eq, PartialEq, Hash)]
  59 pub struct Span {
  60     base_or_index: u32,
  61     len_or_tag: u16,
  62     ctxt_or_zero: u16,
  63 }
  64
  65 const LEN_TAG: u16 = 0b1000_0000_0000_0000;
  66 const MAX_LEN: u32 = 0b0111_1111_1111_1111;
  67 const MAX_CTXT: u32 = 0b1111_1111_1111_1111;
  68
  69 /// Dummy span, both position and length are zero, syntax context is zero as well.
  70 pub const DUMMY_SP: Span = Span { base_or_index: 0, len_or_tag: 0, ctxt_or_zero: 0 };
  71
  72 impl Span {
  73     #[inline]
  74     pub fn new(mut lo: BytePos, mut hi: BytePos, ctxt: SyntaxContext) -> Self {
  75         if lo > hi {
  76             std::mem::swap(&mut lo, &mut hi);
  77         }
  78
  79         let (base, len, ctxt2) = (lo.0, hi.0 - lo.0, ctxt.as_u32());
  80
  81         if len <= MAX_LEN && ctxt2 <= MAX_CTXT {
  82             // Inline format.
  83             Span { base_or_index: base, len_or_tag: len as u16, ctxt_or_zero: ctxt2 as u16 }
  84         } else {
  85             // Interned format.
  86             let index = with_span_interner(|interner| interner.intern(&SpanData { lo, hi, ctxt }));
  87             Span { base_or_index: index, len_or_tag: LEN_TAG, ctxt_or_zero: 0 }
  88         }
  89     }
  90
  91     #[inline]
  92     pub fn data(self) -> SpanData {
  93         if self.len_or_tag != LEN_TAG {
  94             // Inline format.
  95             debug_assert!(self.len_or_tag as u32 <= MAX_LEN);
  96             SpanData {
  97                 lo: BytePos(self.base_or_index),
  98                 hi: BytePos(self.base_or_index + self.len_or_tag as u32),
  99                 ctxt: SyntaxContext::from_u32(self.ctxt_or_zero as u32),
 100             }
 101         } else {
 102             // Interned format.
 103             debug_assert!(self.ctxt_or_zero == 0);
 104             let index = self.base_or_index;
 105             with_span_interner(|interner| *interner.get(index))
 106         }
 107     }
 108 }
 109
 110 #[derive(Default)]
 111 pub struct SpanInterner {
 112     spans: FxIndexSet<SpanData>,
 113 }
 114
 115 impl SpanInterner {
 116     fn intern(&mut self, span_data: &SpanData) -> u32 {
 117         let (index, _) = self.spans.insert_full(*span_data);
 118         index as u32
 119     }
 120
 121     #[inline]
 122     fn get(&self, index: u32) -> &SpanData {
 123         &self.spans[index as usize]
 124     }
 125 }
 126
 127 // If an interner exists, return it. Otherwise, prepare a fresh one.
 128 #[inline]
 129 fn with_span_interner<T, F: FnOnce(&mut SpanInterner) -> T>(f: F) -> T {
 130     SESSION_GLOBALS.with(|session_globals| f(&mut *session_globals.span_interner.lock()))
 131 }