Merging upstream version 1.74.1+dfsg1.

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 145 insertions, 110 deletions

diff --git a/compiler/rustc_span/src/span_encoding.rs b/compiler/rustc_span/src/span_encoding.rs
index 1eea0f63c..93ab15460 100644
--- a/compiler/rustc_span/src/span_encoding.rs
+++ b/compiler/rustc_span/src/span_encoding.rs
@@ -1,9 +1,3 @@
-// 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::def_id::{DefIndex, LocalDefId};
 use crate::hygiene::SyntaxContext;
 use crate::SPAN_TRACK;
@@ -13,59 +7,69 @@ use rustc_data_structures::fx::FxIndexSet;
 
 /// A compressed span.
 ///
-/// Whereas [`SpanData`] is 16 bytes, which is a bit too big to stick everywhere, `Span`
-/// is a form that only takes up 8 bytes, with less space for the length, parent and
-/// context. The vast majority (99.9%+) of `SpanData` instances will fit within
-/// those 8 bytes; any `SpanData` whose fields don't fit into a `Span` are
+/// [`SpanData`] is 16 bytes, which is too big to stick everywhere. `Span` only
+/// takes up 8 bytes, with less space for the length, parent and context. The
+/// vast majority (99.9%+) of `SpanData` instances can be made to fit within
+/// those 8 bytes. Any `SpanData` whose fields don't fit into a `Span` are
 /// stored in a separate interner table, and the `Span` will index into that
 /// table. Interning is rare enough that the cost is low, but common enough
 /// that the code is exercised regularly.
 ///
 /// An earlier version of this code used only 4 bytes for `Span`, but that was
 /// slower because only 80--90% of spans could be stored inline (even less in
-/// very large crates) and so the interner was used a lot more.
+/// very large crates) and so the interner was used a lot more. That version of
+/// the code also predated the storage of parents.
+///
+/// There are four different span forms.
 ///
-/// Inline (compressed) format with no parent:
-/// - `span.base_or_index == span_data.lo`
-/// - `span.len_or_tag == len == span_data.hi - span_data.lo` (must be `<= MAX_LEN`)
-/// - `span.ctxt_or_tag == span_data.ctxt` (must be `<= MAX_CTXT`)
+/// Inline-context format (requires non-huge length, non-huge context, and no parent):
+/// - `span.lo_or_index == span_data.lo`
+/// - `span.len_with_tag_or_marker == len == span_data.hi - span_data.lo` (must be `<= MAX_LEN`)
+/// - `span.ctxt_or_parent_or_marker == span_data.ctxt` (must be `<= MAX_CTXT`)
 ///
-/// Interned format with inline `SyntaxContext`:
-/// - `span.base_or_index == index` (indexes into the interner table)
-/// - `span.len_or_tag == LEN_TAG` (high bit set, all other bits are zero)
-/// - `span.ctxt_or_tag == span_data.ctxt` (must be `<= MAX_CTXT`)
+/// Inline-parent format (requires non-huge length, root context, and non-huge parent):
+/// - `span.lo_or_index == span_data.lo`
+/// - `span.len_with_tag_or_marker & !PARENT_TAG == len == span_data.hi - span_data.lo`
+///   (must be `<= MAX_LEN`)
+/// - `span.len_with_tag_or_marker` has top bit (`PARENT_TAG`) set
+/// - `span.ctxt_or_parent_or_marker == span_data.parent` (must be `<= MAX_CTXT`)
 ///
-/// Inline (compressed) format with root context:
-/// - `span.base_or_index == span_data.lo`
-/// - `span.len_or_tag == len == span_data.hi - span_data.lo` (must be `<= MAX_LEN`)
-/// - `span.len_or_tag` has top bit (`PARENT_MASK`) set
-/// - `span.ctxt == span_data.parent` (must be `<= MAX_CTXT`)
+/// Partially-interned format (requires non-huge context):
+/// - `span.lo_or_index == index` (indexes into the interner table)
+/// - `span.len_with_tag_or_marker == BASE_LEN_INTERNED_MARKER`
+/// - `span.ctxt_or_parent_or_marker == span_data.ctxt` (must be `<= MAX_CTXT`)
 ///
-/// Interned format:
-/// - `span.base_or_index == index` (indexes into the interner table)
-/// - `span.len_or_tag == LEN_TAG` (high bit set, all other bits are zero)
-/// - `span.ctxt_or_tag == CTXT_TAG`
+/// Fully-interned format (all cases not covered above):
+/// - `span.lo_or_index == index` (indexes into the interner table)
+/// - `span.len_with_tag_or_marker == BASE_LEN_INTERNED_MARKER`
+/// - `span.ctxt_or_parent_or_marker == CTXT_INTERNED_MARKER`
 ///
-/// The inline form uses 0 for the tag value (rather than 1) so that we don't
-/// need to mask out the tag bit when getting the length, and so that the
-/// dummy span can be all zeroes.
+/// The partially-interned form requires looking in the interning table for
+/// lo and length, but the context is stored inline as well as interned.
+/// This is useful because context lookups are often done in isolation, and
+/// inline lookups are quicker.
 ///
 /// Notes about the choice of field sizes:
-/// - `base` is 32 bits in both `Span` and `SpanData`, which means that `base`
-///   values never cause interning. The number of bits needed for `base`
+/// - `lo` is 32 bits in both `Span` and `SpanData`, which means that `lo`
+///   values never cause interning. The number of bits needed for `lo`
 ///   depends on the crate size. 32 bits allows up to 4 GiB of code in a crate.
-/// - `len` is 15 bits in `Span` (a u16, minus 1 bit for the tag) and 32 bits
-///   in `SpanData`, which means that large `len` values will cause interning.
-///   The number of bits needed for `len` does not depend on the crate size.
-///   The most common numbers of bits for `len` are from 0 to 7, with a peak usually
-///   at 3 or 4, and then it drops off quickly from 8 onwards. 15 bits is enough
-///   for 99.99%+ of cases, but larger values (sometimes 20+ bits) might occur
-///   dozens of times in a typical crate.
-/// - `ctxt_or_tag` is 16 bits in `Span` and 32 bits in `SpanData`, which means that
-///   large `ctxt` values will cause interning. The number of bits needed for
-///   `ctxt` values depend partly on the crate size and partly on the form of
-///   the code. No crates in `rustc-perf` need more than 15 bits for `ctxt_or_tag`,
-///   but larger crates might need more than 16 bits.
+///   Having no compression on this field means there is no performance cliff
+///   if a crate exceeds a particular size.
+/// - `len` is ~15 bits in `Span` (a u16, minus 1 bit for PARENT_TAG) and 32
+///   bits in `SpanData`, which means that large `len` values will cause
+///   interning. The number of bits needed for `len` does not depend on the
+///   crate size. The most common numbers of bits for `len` are from 0 to 7,
+///   with a peak usually at 3 or 4, and then it drops off quickly from 8
+///   onwards. 15 bits is enough for 99.99%+ of cases, but larger values
+///   (sometimes 20+ bits) might occur dozens of times in a typical crate.
+/// - `ctxt_or_parent_or_marker` is 16 bits in `Span` and two 32 bit fields in
+///   `SpanData`, which means intering will happen if `ctxt` is large, if
+///   `parent` is large, or if both values are non-zero. The number of bits
+///   needed for `ctxt` values depend partly on the crate size and partly on
+///   the form of the code. No crates in `rustc-perf` need more than 15 bits
+///   for `ctxt_or_parent_or_marker`, but larger crates might need more than 16
+///   bits. The number of bits needed for `parent` hasn't been measured,
+///   because `parent` isn't currently used by default.
 ///
 /// In order to reliably use parented spans in incremental compilation,
 /// the dependency to the parent definition's span. This is performed
@@ -74,19 +78,22 @@ use rustc_data_structures::fx::FxIndexSet;
 #[derive(Clone, Copy, Eq, PartialEq, Hash)]
 #[rustc_pass_by_value]
 pub struct Span {
-    base_or_index: u32,
-    len_or_tag: u16,
-    ctxt_or_tag: u16,
+    lo_or_index: u32,
+    len_with_tag_or_marker: u16,
+    ctxt_or_parent_or_marker: u16,
 }
 
-const LEN_TAG: u16 = 0b1111_1111_1111_1111;
-const PARENT_MASK: u16 = 0b1000_0000_0000_0000;
-const MAX_LEN: u32 = 0b0111_1111_1111_1111;
-const CTXT_TAG: u32 = 0b1111_1111_1111_1111;
-const MAX_CTXT: u32 = CTXT_TAG - 1;
+// `MAX_LEN` is chosen so that `PARENT_TAG | MAX_LEN` is distinct from
+// `BASE_LEN_INTERNED_MARKER`. (If `MAX_LEN` was 1 higher, this wouldn't be true.)
+const MAX_LEN: u32 = 0b0111_1111_1111_1110;
+const MAX_CTXT: u32 = 0b0111_1111_1111_1110;
+const PARENT_TAG: u16 = 0b1000_0000_0000_0000;
+const BASE_LEN_INTERNED_MARKER: u16 = 0b1111_1111_1111_1111;
+const CTXT_INTERNED_MARKER: u16 = 0b1111_1111_1111_1111;
 
-/// Dummy span, both position and length are zero, syntax context is zero as well.
-pub const DUMMY_SP: Span = Span { base_or_index: 0, len_or_tag: 0, ctxt_or_tag: 0 };
+/// The dummy span has zero position, length, and context, and no parent.
+pub const DUMMY_SP: Span =
+    Span { lo_or_index: 0, len_with_tag_or_marker: 0, ctxt_or_parent_or_marker: 0 };
 
 impl Span {
     #[inline]
@@ -100,39 +107,43 @@ impl Span {
             std::mem::swap(&mut lo, &mut hi);
         }
 
-        let (base, len, ctxt2) = (lo.0, hi.0 - lo.0, ctxt.as_u32());
-
-        if len <= MAX_LEN && ctxt2 <= MAX_CTXT {
-            let len_or_tag = len as u16;
-            debug_assert_eq!(len_or_tag & PARENT_MASK, 0);
+        let (lo2, len, ctxt2) = (lo.0, hi.0 - lo.0, ctxt.as_u32());
 
-            if let Some(parent) = parent {
-                // Inline format with parent.
-                let len_or_tag = len_or_tag | PARENT_MASK;
-                let parent2 = parent.local_def_index.as_u32();
-                if ctxt2 == SyntaxContext::root().as_u32()
-                    && parent2 <= MAX_CTXT
-                    && len_or_tag < LEN_TAG
-                {
-                    debug_assert_ne!(len_or_tag, LEN_TAG);
-                    return Span { base_or_index: base, len_or_tag, ctxt_or_tag: parent2 as u16 };
-                }
-            } else {
-                // Inline format with ctxt.
-                debug_assert_ne!(len_or_tag, LEN_TAG);
+        if len <= MAX_LEN {
+            if ctxt2 <= MAX_CTXT && parent.is_none() {
+                // Inline-context format.
                 return Span {
-                    base_or_index: base,
-                    len_or_tag: len as u16,
-                    ctxt_or_tag: ctxt2 as u16,
+                    lo_or_index: lo2,
+                    len_with_tag_or_marker: len as u16,
+                    ctxt_or_parent_or_marker: ctxt2 as u16,
+                };
+            } else if ctxt2 == SyntaxContext::root().as_u32()
+                && let Some(parent) = parent
+                && let parent2 = parent.local_def_index.as_u32()
+                && parent2 <= MAX_CTXT
+            {
+                // Inline-parent format.
+                return Span {
+                    lo_or_index: lo2,
+                    len_with_tag_or_marker: PARENT_TAG | len as u16,
+                    ctxt_or_parent_or_marker: parent2 as u16
                 };
             }
         }
 
-        // Interned format.
+        // Partially-interned or fully-interned format.
         let index =
             with_span_interner(|interner| interner.intern(&SpanData { lo, hi, ctxt, parent }));
-        let ctxt_or_tag = if ctxt2 <= MAX_CTXT { ctxt2 } else { CTXT_TAG } as u16;
-        Span { base_or_index: index, len_or_tag: LEN_TAG, ctxt_or_tag }
+        let ctxt_or_parent_or_marker = if ctxt2 <= MAX_CTXT {
+            ctxt2 as u16 // partially-interned
+        } else {
+            CTXT_INTERNED_MARKER // fully-interned
+        };
+        Span {
+            lo_or_index: index,
+            len_with_tag_or_marker: BASE_LEN_INTERNED_MARKER,
+            ctxt_or_parent_or_marker,
+        }
     }
 
     #[inline]
@@ -148,56 +159,80 @@ impl Span {
     /// This function must not be used outside the incremental engine.
     #[inline]
     pub fn data_untracked(self) -> SpanData {
-        if self.len_or_tag != LEN_TAG {
-            // Inline format.
-            if self.len_or_tag & PARENT_MASK == 0 {
-                debug_assert!(self.len_or_tag as u32 <= MAX_LEN);
+        if self.len_with_tag_or_marker != BASE_LEN_INTERNED_MARKER {
+            if self.len_with_tag_or_marker & PARENT_TAG == 0 {
+                // Inline-context format.
+                let len = self.len_with_tag_or_marker as u32;
+                debug_assert!(len <= MAX_LEN);
                 SpanData {
-                    lo: BytePos(self.base_or_index),
-                    hi: BytePos(self.base_or_index + self.len_or_tag as u32),
-                    ctxt: SyntaxContext::from_u32(self.ctxt_or_tag as u32),
+                    lo: BytePos(self.lo_or_index),
+                    hi: BytePos(self.lo_or_index + len),
+                    ctxt: SyntaxContext::from_u32(self.ctxt_or_parent_or_marker as u32),
                     parent: None,
                 }
             } else {
-                let len = self.len_or_tag & !PARENT_MASK;
-                debug_assert!(len as u32 <= MAX_LEN);
-                let parent =
-                    LocalDefId { local_def_index: DefIndex::from_u32(self.ctxt_or_tag as u32) };
+                // Inline-parent format.
+                let len = (self.len_with_tag_or_marker & !PARENT_TAG) as u32;
+                debug_assert!(len <= MAX_LEN);
+                let parent = LocalDefId {
+                    local_def_index: DefIndex::from_u32(self.ctxt_or_parent_or_marker as u32),
+                };
                 SpanData {
-                    lo: BytePos(self.base_or_index),
-                    hi: BytePos(self.base_or_index + len as u32),
+                    lo: BytePos(self.lo_or_index),
+                    hi: BytePos(self.lo_or_index + len),
                     ctxt: SyntaxContext::root(),
                     parent: Some(parent),
                 }
             }
         } else {
-            // Interned format.
-            let index = self.base_or_index;
+            // Fully-interned or partially-interned format. In either case,
+            // the interned value contains all the data, so we don't need to
+            // distinguish them.
+            let index = self.lo_or_index;
             with_span_interner(|interner| interner.spans[index as usize])
         }
     }
 
+    /// Returns `true` if this is a dummy span with any hygienic context.
+    #[inline]
+    pub fn is_dummy(self) -> bool {
+        if self.len_with_tag_or_marker != BASE_LEN_INTERNED_MARKER {
+            // Inline-context or inline-parent format.
+            let lo = self.lo_or_index;
+            let len = (self.len_with_tag_or_marker & !PARENT_TAG) as u32;
+            debug_assert!(len <= MAX_LEN);
+            lo == 0 && len == 0
+        } else {
+            // Fully-interned or partially-interned format.
+            let index = self.lo_or_index;
+            let data = with_span_interner(|interner| interner.spans[index as usize]);
+            data.lo == BytePos(0) && data.hi == BytePos(0)
+        }
+    }
+
     /// This function is used as a fast path when decoding the full `SpanData` is not necessary.
+    /// It's a cut-down version of `data_untracked`.
     #[inline]
     pub fn ctxt(self) -> SyntaxContext {
-        let ctxt_or_tag = self.ctxt_or_tag as u32;
-        // Check for interned format.
-        if self.len_or_tag == LEN_TAG {
-            if ctxt_or_tag == CTXT_TAG {
-                // Fully interned format.
-                let index = self.base_or_index;
-                with_span_interner(|interner| interner.spans[index as usize].ctxt)
+        if self.len_with_tag_or_marker != BASE_LEN_INTERNED_MARKER {
+            if self.len_with_tag_or_marker & PARENT_TAG == 0 {
+                // Inline-context format.
+                SyntaxContext::from_u32(self.ctxt_or_parent_or_marker as u32)
             } else {
-                // Interned format with inline ctxt.
-                SyntaxContext::from_u32(ctxt_or_tag)
+                // Inline-parent format. We know that the SyntaxContext is root.
+                SyntaxContext::root()
             }
-        } else if self.len_or_tag & PARENT_MASK == 0 {
-            // Inline format with inline ctxt.
-            SyntaxContext::from_u32(ctxt_or_tag)
         } else {
-            // Inline format with inline parent.
-            // We know that the SyntaxContext is root.
-            SyntaxContext::root()
+            if self.ctxt_or_parent_or_marker != CTXT_INTERNED_MARKER {
+                // Partially-interned format. This path avoids looking up the
+                // interned value, and is the whole point of the
+                // partially-interned format.
+                SyntaxContext::from_u32(self.ctxt_or_parent_or_marker as u32)
+            } else {
+                // Fully-interned format.
+                let index = self.lo_or_index;
+                with_span_interner(|interner| interner.spans[index as usize].ctxt)
+            }
         }
     }
 }