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
8 use {BytePos, SpanData};
9 use hygiene::SyntaxContext;
11 use rustc_data_structures::fx::FxHashMap;
12 use std::hash::{Hash, Hasher};
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.
25 fn clone(&self) -> Span {
29 impl PartialEq for Span {
31 fn eq(&self, other: &Span) -> bool {
40 fn hash<H: Hasher>(&self, state: &mut H) {
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);
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 },
60 pub fn data(self) -> SpanData {
66 const TAG_INLINE: u32 = 0;
67 const TAG_INTERNED: u32 = 1;
68 const TAG_MASK: u32 = 1;
71 const BASE_INDEX: usize = 0;
72 const LEN_INDEX: usize = 1;
73 const CTXT_INDEX: usize = 2;
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
81 const INLINE_SIZES: [u32; 3] = [24, 7, 0];
82 const INLINE_OFFSETS: [u32; 3] = [8, 1, 1];
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;
92 fn encode(sd: &SpanData) -> Span {
93 let (base, len, ctxt) = (sd.lo.0, sd.hi.0 - sd.lo.0, sd.ctxt.as_u32());
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
101 let index = with_span_interner(|interner| interner.intern(sd));
102 (index << INTERNED_INDEX_OFFSET) | TAG_INTERNED
108 fn decode(span: Span) -> SpanData {
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
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]),
122 let index = extract(INTERNED_INDEX_OFFSET, INTERNED_INDEX_SIZE);
123 return with_span_interner(|interner| *interner.get(index));
125 SpanData { lo: BytePos(base), hi: BytePos(base + len), ctxt: SyntaxContext::from_u32(ctxt) }
129 pub struct SpanInterner {
130 spans: FxHashMap<SpanData, u32>,
131 span_data: Vec<SpanData>,
135 fn intern(&mut self, span_data: &SpanData) -> u32 {
136 if let Some(index) = self.spans.get(span_data) {
140 let index = self.spans.len() as u32;
141 self.span_data.push(*span_data);
142 self.spans.insert(*span_data, index);
147 fn get(&self, index: u32) -> &SpanData {
148 &self.span_data[index as usize]
152 // If an interner exists, return it. Otherwise, prepare a fresh one.
154 fn with_span_interner<T, F: FnOnce(&mut SpanInterner) -> T>(f: F) -> T {
155 GLOBALS.with(|globals| f(&mut *globals.span_interner.lock()))