src/libsyntax_pos/span_encoding.rs

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