src/libsyntax_pos/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::GLOBALS;
   8 use crate::{BytePos, SpanData};
   9 use crate::hygiene::SyntaxContext;
  10
  11 use rustc_data_structures::fx::FxHashMap;
  12 use std::hash::{Hash, Hasher};
  13
  14 /// A compressed span.
  15 /// Contains either fields of `SpanData` inline if they are small, or index into span interner.
  16 /// The primary goal of `Span` is to be as small as possible and fit into other structures
  17 /// (that's why it uses `packed` as well). Decoding speed is the second priority.
  18 /// See `SpanData` for the info on span fields in decoded representation.
  19 #[repr(packed)]
  20 pub struct Span(u32);
  21
  22 impl Copy for Span {}
  23 impl Clone for Span {
  24     #[inline]
  25     fn clone(&self) -> Span {
  26         *self
  27     }
  28 }
  29 impl PartialEq for Span {
  30     #[inline]
  31     fn eq(&self, other: &Span) -> bool {
  32         let a = self.0;
  33         let b = other.0;
  34         a == b
  35     }
  36 }
  37 impl Eq for Span {}
  38 impl Hash for Span {
  39     #[inline]
  40     fn hash<H: Hasher>(&self, state: &mut H) {
  41         let a = self.0;
  42         a.hash(state)
  43     }
  44 }
  45
  46 /// Dummy span, both position and length are zero, syntax context is zero as well.
  47 /// This span is kept inline and encoded with format 0.
  48 pub const DUMMY_SP: Span = Span(0);
  49
  50 impl Span {
  51     #[inline]
  52     pub fn new(lo: BytePos, hi: BytePos, ctxt: SyntaxContext) -> Self {
  53         encode(&match lo <= hi {
  54             true => SpanData { lo, hi, ctxt },
  55             false => SpanData { lo: hi, hi: lo, ctxt },
  56         })
  57     }
  58
  59     #[inline]
  60     pub fn data(self) -> SpanData {
  61         decode(self)
  62     }
  63 }
  64
  65 // Tags
  66 const TAG_INLINE: u32 = 0;
  67 const TAG_INTERNED: u32 = 1;
  68 const TAG_MASK: u32 = 1;
  69
  70 // Fields indexes
  71 const BASE_INDEX: usize = 0;
  72 const LEN_INDEX: usize = 1;
  73 const CTXT_INDEX: usize = 2;
  74
  75 // Tag = 0, inline format.
  76 // -------------------------------------------------------------
  77 // | base 31:8  | len 7:1  | ctxt (currently 0 bits) | tag 0:0 |
  78 // -------------------------------------------------------------
  79 // Since there are zero bits for ctxt, only SpanData with a 0 SyntaxContext
  80 // can be inline.
  81 const INLINE_SIZES: [u32; 3] = [24, 7, 0];
  82 const INLINE_OFFSETS: [u32; 3] = [8, 1, 1];
  83
  84 // Tag = 1, interned format.
  85 // ------------------------
  86 // | index 31:1 | tag 0:0 |
  87 // ------------------------
  88 const INTERNED_INDEX_SIZE: u32 = 31;
  89 const INTERNED_INDEX_OFFSET: u32 = 1;
  90
  91 #[inline]
  92 fn encode(sd: &SpanData) -> Span {
  93     let (base, len, ctxt) = (sd.lo.0, sd.hi.0 - sd.lo.0, sd.ctxt.as_u32());
  94
  95     let val = if (base >> INLINE_SIZES[BASE_INDEX]) == 0 &&
  96                  (len >> INLINE_SIZES[LEN_INDEX]) == 0 &&
  97                  (ctxt >> INLINE_SIZES[CTXT_INDEX]) == 0 {
  98         (base << INLINE_OFFSETS[BASE_INDEX]) | (len << INLINE_OFFSETS[LEN_INDEX]) |
  99         (ctxt << INLINE_OFFSETS[CTXT_INDEX]) | TAG_INLINE
 100     } else {
 101         let index = with_span_interner(|interner| interner.intern(sd));
 102         (index << INTERNED_INDEX_OFFSET) | TAG_INTERNED
 103     };
 104     Span(val)
 105 }
 106
 107 #[inline]
 108 fn decode(span: Span) -> SpanData {
 109     let val = span.0;
 110
 111     // Extract a field at position `pos` having size `size`.
 112     let extract = |pos: u32, size: u32| {
 113         let mask = ((!0u32) as u64 >> (32 - size)) as u32; // Can't shift u32 by 32
 114         (val >> pos) & mask
 115     };
 116
 117     let (base, len, ctxt) = if val & TAG_MASK == TAG_INLINE {(
 118         extract(INLINE_OFFSETS[BASE_INDEX], INLINE_SIZES[BASE_INDEX]),
 119         extract(INLINE_OFFSETS[LEN_INDEX], INLINE_SIZES[LEN_INDEX]),
 120         extract(INLINE_OFFSETS[CTXT_INDEX], INLINE_SIZES[CTXT_INDEX]),
 121     )} else {
 122         let index = extract(INTERNED_INDEX_OFFSET, INTERNED_INDEX_SIZE);
 123         return with_span_interner(|interner| *interner.get(index));
 124     };
 125     SpanData { lo: BytePos(base), hi: BytePos(base + len), ctxt: SyntaxContext::from_u32(ctxt) }
 126 }
 127
 128 #[derive(Default)]
 129 pub struct SpanInterner {
 130     spans: FxHashMap<SpanData, u32>,
 131     span_data: Vec<SpanData>,
 132 }
 133
 134 impl SpanInterner {
 135     fn intern(&mut self, span_data: &SpanData) -> u32 {
 136         if let Some(index) = self.spans.get(span_data) {
 137             return *index;
 138         }
 139
 140         let index = self.spans.len() as u32;
 141         self.span_data.push(*span_data);
 142         self.spans.insert(*span_data, index);
 143         index
 144     }
 145
 146     #[inline]
 147     fn get(&self, index: u32) -> &SpanData {
 148         &self.span_data[index as usize]
 149     }
 150 }
 151
 152 // If an interner exists, return it. Otherwise, prepare a fresh one.
 153 #[inline]
 154 fn with_span_interner<T, F: FnOnce(&mut SpanInterner) -> T>(f: F) -> T {
 155     GLOBALS.with(|globals| f(&mut *globals.span_interner.lock()))
 156 }