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