1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156

// Spans are encoded using 1-bit tag and 2 different encoding formats (one for each tag value).
// One format is used for keeping span data inline,
// another contains index into an out-of-line span interner.
// The encoding format for inline spans were obtained by optimizing over crates in rustc/libstd.
// See https://internals.rust-lang.org/t/rfc-compiler-refactoring-spans/1357/28

use crate::GLOBALS;
use crate::{BytePos, SpanData};
use crate::hygiene::SyntaxContext;

use rustc_data_structures::fx::FxHashMap;
use std::hash::{Hash, Hasher};

/// A compressed span.
/// Contains either fields of `SpanData` inline if they are small, or index into span interner.
/// The primary goal of `Span` is to be as small as possible and fit into other structures
/// (that's why it uses `packed` as well). Decoding speed is the second priority.
/// See `SpanData` for the info on span fields in decoded representation.
#[repr(packed)]
pub struct Span(u32);

impl Copy for Span {}
impl Clone for Span {
    #[inline]
    fn clone(&self) -> Span {
        *self
    }
}
impl PartialEq for Span {
    #[inline]
    fn eq(&self, other: &Span) -> bool {
        let a = self.0;
        let b = other.0;
        a == b
    }
}
impl Eq for Span {}
impl Hash for Span {
    #[inline]
    fn hash<H: Hasher>(&self, state: &mut H) {
        let a = self.0;
        a.hash(state)
    }
}

/// Dummy span, both position and length are zero, syntax context is zero as well.
/// This span is kept inline and encoded with format 0.
pub const DUMMY_SP: Span = Span(0);

impl Span {
    #[inline]
    pub fn new(lo: BytePos, hi: BytePos, ctxt: SyntaxContext) -> Self {
        encode(&match lo <= hi {
            true => SpanData { lo, hi, ctxt },
            false => SpanData { lo: hi, hi: lo, ctxt },
        })
    }

    #[inline]
    pub fn data(self) -> SpanData {
        decode(self)
    }
}

// Tags
const TAG_INLINE: u32 = 0;
const TAG_INTERNED: u32 = 1;
const TAG_MASK: u32 = 1;

// Fields indexes
const BASE_INDEX: usize = 0;
const LEN_INDEX: usize = 1;
const CTXT_INDEX: usize = 2;

// Tag = 0, inline format.
// -------------------------------------------------------------
// | base 31:8  | len 7:1  | ctxt (currently 0 bits) | tag 0:0 |
// -------------------------------------------------------------
// Since there are zero bits for ctxt, only SpanData with a 0 SyntaxContext
// can be inline.
const INLINE_SIZES: [u32; 3] = [24, 7, 0];
const INLINE_OFFSETS: [u32; 3] = [8, 1, 1];

// Tag = 1, interned format.
// ------------------------
// | index 31:1 | tag 0:0 |
// ------------------------
const INTERNED_INDEX_SIZE: u32 = 31;
const INTERNED_INDEX_OFFSET: u32 = 1;

#[inline]
fn encode(sd: &SpanData) -> Span {
    let (base, len, ctxt) = (sd.lo.0, sd.hi.0 - sd.lo.0, sd.ctxt.as_u32());

    let val = if (base >> INLINE_SIZES[BASE_INDEX]) == 0 &&
                 (len >> INLINE_SIZES[LEN_INDEX]) == 0 &&
                 (ctxt >> INLINE_SIZES[CTXT_INDEX]) == 0 {
        (base << INLINE_OFFSETS[BASE_INDEX]) | (len << INLINE_OFFSETS[LEN_INDEX]) |
        (ctxt << INLINE_OFFSETS[CTXT_INDEX]) | TAG_INLINE
    } else {
        let index = with_span_interner(|interner| interner.intern(sd));
        (index << INTERNED_INDEX_OFFSET) | TAG_INTERNED
    };
    Span(val)
}

#[inline]
fn decode(span: Span) -> SpanData {
    let val = span.0;

    // Extract a field at position `pos` having size `size`.
    let extract = |pos: u32, size: u32| {
        let mask = ((!0u32) as u64 >> (32 - size)) as u32; // Can't shift u32 by 32
        (val >> pos) & mask
    };

    let (base, len, ctxt) = if val & TAG_MASK == TAG_INLINE {(
        extract(INLINE_OFFSETS[BASE_INDEX], INLINE_SIZES[BASE_INDEX]),
        extract(INLINE_OFFSETS[LEN_INDEX], INLINE_SIZES[LEN_INDEX]),
        extract(INLINE_OFFSETS[CTXT_INDEX], INLINE_SIZES[CTXT_INDEX]),
    )} else {
        let index = extract(INTERNED_INDEX_OFFSET, INTERNED_INDEX_SIZE);
        return with_span_interner(|interner| *interner.get(index));
    };
    SpanData { lo: BytePos(base), hi: BytePos(base + len), ctxt: SyntaxContext::from_u32(ctxt) }
}

#[derive(Default)]
pub struct SpanInterner {
    spans: FxHashMap<SpanData, u32>,
    span_data: Vec<SpanData>,
}

impl SpanInterner {
    fn intern(&mut self, span_data: &SpanData) -> u32 {
        if let Some(index) = self.spans.get(span_data) {
            return *index;
        }

        let index = self.spans.len() as u32;
        self.span_data.push(*span_data);
        self.spans.insert(*span_data, index);
        index
    }

    #[inline]
    fn get(&self, index: u32) -> &SpanData {
        &self.span_data[index as usize]
    }
}

// If an interner exists, return it. Otherwise, prepare a fresh one.
#[inline]
fn with_span_interner<T, F: FnOnce(&mut SpanInterner) -> T>(f: F) -> T {
    GLOBALS.with(|globals| f(&mut *globals.span_interner.lock()))
}