How a Span Fits in Eight Bytes: rustc's Four-Format Packed Encoding

TL;DR: A Span has to say where in the source something is, and which hygiene context it belongs to. rustc packs that into eight bytes using four different layouts, selected by a variable-length prefix in the high bits. And the decoding is a macro, not an enum, because — as the comment says — “converting span to an enum and matching on it doesn’t optimize away properly.”

The four formats

rust
// compiler/rustc_span/src/span_encoding.rs:31-50

//! There are four different span formats and each packs data into the 8 bytes
//! in a different way. A variable-length prefix in the high bits identifies
//! which format is being used. It is an invariant that we always use the first
//! listed format whose requirements are satisfied. `len` is `hi - lo`.
//!
//! - Inline-context format (requires 15-bit length, 16-bit context, and no parent):
//!
//!     `[ prefix=0 | len:15 | ctxt:16 | lo:32 ]`
//!
//! - Inline-parent format (requires 14-bit length, root context, and 15-bit parent):
//!
//!     `[ prefix=110 | len:14 | parent:15 | lo:32 ]`
//!
//! - Inline-pair format (requires 24-bit lo, 7-bit length, 15-bit context, 16-bit parent):
//!
//!     `[ prefix=10 | len:7 | ctxt:15 | parent:16 | lo:24 ]`
//!
//! - Interned format (all cases not covered above):
//!
//!     `[ prefix=111 | ctxt:29 | index:32 ]`

Read the invariants:

Inline-context is the common case: a 32-bit start offset, a 15-bit length, and a 16-bit hygiene context. No parent needed.
Inline-parent handles the case where the span’s context is the root context but it has a parent expansion: the parent is stored (15 bits) and the context is implied.
Inline-pair is for spans with a 24-bit offset — needed for very large files — trading length and context bits for offset bits.
Interned is the escape hatch: everything goes into a side table and the span holds an index.

The prefix lengths differ per format (1 bit, 3 bits, 2 bits, 3 bits), so the decoding is a small decision tree.

The type

rust
// compiler/rustc_span/src/span_encoding.rs:86-95

#[derive(Clone, Copy, Eq, PartialEq, Hash)]
#[rustc_pass_by_value]
#[repr(packed(4))]
pub struct Span(u64);

repr(packed(4)) keeps the alignment at 4 bytes while the size stays 8, so AST nodes containing spans stay smaller. The rustc_pass_by_value attribute tells the compiler to pass spans by value rather than by reference.

The bit-field helper

rust
// compiler/rustc_span/src/span_encoding.rs:182-201

impl InlineCtxt {
    const PREFIX_VALUE: u32 = 0b0;
    const PREFIX: SpanField = SpanField::top(1);
    const LEN: SpanField = Self::PREFIX.below(15);
    const CTXT: SpanField = Self::LEN.below(16);
    const LO: SpanField = Self::CTXT.below(32);

    #[inline]
    pub(crate) const fn try_new_span(lo: u32, len: u32, ctxt: u32) -> Option<Span> {
        if Self::LEN.too_big(len) | Self::CTXT.too_big(ctxt) == 0 {
            Some(Span(
                Self::PREFIX.set(Self::PREFIX_VALUE)
                    | Self::LEN.set(len)
                    | Self::CTXT.set(ctxt)
                    | Self::LO.set(lo),
            ))
        } else {
            None
        }
    }
}

The bit-field layout is computed at compile time (shift, width, mask are consts), so each format is just shifts and masks at runtime. And note the |: the two “does it fit?” tests are combined into a single branchless test.

Why a macro and not an enum

rust
// compiler/rustc_span/src/span_encoding.rs:346-372

// This code is very hot, and converting span to an enum and matching on it doesn't optimize away
// properly. So we are using a macro emulating such a match, but expand it directly to an if-else
// chain.
macro_rules! match_span_kind {
    (
        $span:expr,
        InlineCtxt($span1:ident) => $arm1:expr,
        InlineParent($span2:ident) => $arm2:expr,
        InlinePair($span3:ident) => $arm3:expr,
        Interned($span4:ident) => $arm4:expr,
    ) => {{
        let span64 = $span.0;
        if InlineCtxt::PREFIX.get(span64) == InlineCtxt::PREFIX_VALUE {
            let $span1 = InlineCtxt::from_span($span);
            $arm1
        } else if InlineParent::PREFIX.get(span64) == InlineParent::PREFIX_VALUE {
            let $span2 = InlineParent::from_span($span);
            $arm2
        } else if InlinePair::PREFIX.get(span64) == InlinePair::PREFIX_VALUE {
            let $span3 = InlinePair::from_span($span);
            $arm3
        } else {
            let $span4 = Interned::from_span($span);
            $arm4
        }
    }};
}

The source looks like an exhaustive enum match — readable, and the compiler will warn if a format is forgotten — but it expands to a straight-line if/else chain over the raw u64.

Why does that matter? Using a real enum would mean constructing the enum (a store to a stack slot) and then matching on it, and LLVM failed to optimize that away in this hot path. The macro keeps the ergonomics and gets the codegen.

The order of the tests matters too: InlineCtxt (prefix 0) is tested first, because it is by far the most common. The source even micro-optimises that case:

rust
// compiler/rustc_span/src/span_encoding.rs:486-498

InlineCtxt(span) => {
    // This format occurs 1-2 orders of magnitude more often than others (#125017),
    // so it makes sense to micro-optimize it to avoid `span.data()` and `Span::new()`.

Hygiene as interned mark chains

The ctxt field is a SyntaxContext:

rust
// compiler/rustc_span/src/hygiene.rs:51-79

/// A `SyntaxContext` represents a chain of pairs `(ExpnId, Transparency)` named "marks".
///
/// See <https://rustc-dev-guide.rust-lang.org/macro-expansion.html> for more explanation.
#[derive(Default, Clone, Copy, PartialEq, Eq, Hash)]
pub struct SyntaxContext(u32);

Four bytes. It is an index into a global, interned table:

rust
// compiler/rustc_span/src/hygiene.rs:81-95

#[derive(Clone, Copy, Debug)]
struct SyntaxContextData {
    /// The last macro expansion in the chain.
    /// (Here we say the most deeply nested macro expansion is the "outermost" expansion.)
    outer_expn: ExpnId,
    /// Transparency of the last macro expansion
    outer_transparency: Transparency,
    parent: SyntaxContext,
    /// This context, but with all transparent and semi-opaque expansions filtered away.
    opaque: SyntaxContext,
    /// This context, but with all transparent expansions filtered away.
    opaque_and_semiopaque: SyntaxContext,
    /// Name of the crate to which `$crate` with this context would resolve.
    dollar_crate_name: Symbol,
}

The mark chain is a linked list of interned nodes, but the useful projections of it are precomputed: opaque is the chain with transparent and semi-opaque marks filtered out, opaque_and_semiopaque with only transparent ones. So “resolve this name under macros 2.0 rules” is an array index rather than a chain walk.

The interning itself:

rust
// compiler/rustc_span/src/hygiene.rs:729-750

fn alloc_ctxt(
    &mut self,
    parent: SyntaxContext,
    expn_id: ExpnId,
    transparency: Transparency,
) -> SyntaxContext {
    // Look into the cache first.
    let key = (parent, expn_id, transparency);
    if let Some(ctxt) = self.syntax_context_map.get(&key) {
        return *ctxt;
    }
    ...

Because contexts are hash-consed, two expansions with the same hygiene chain share one u32, and equality is a single integer compare.

Why `Ord` is forbidden

rust
// compiler/rustc_span/src/hygiene.rs:71-75

// To ensure correctness of incremental compilation,
// `SyntaxContext` must not implement `Ord` or `PartialOrd`.
// See https://github.com/rust-lang/rust/issues/90317.
impl !Ord for SyntaxContext {}
impl !PartialOrd for SyntaxContext {}

This is one of my favourite pieces of API design in the whole compiler. Hygiene contexts are allocated in an arbitrary, non-deterministic order as expansions are encountered. If SyntaxContext implemented Ord, then any BTreeMap/BTreeSet keyed by it would iterate in an order that depends on that arbitrary allocation order — and the incremental compiler compares query results across sessions. The same set of contexts, in a different order, would look like a different result, causing spurious recompilation and non-deterministic diagnostics.

By forbidding Ord, the type system forces callers to use HashSet / HashMap (order-independent) or to explicitly opt into an ordering (as Span does with its OrdSpan wrapper, which orders only by position).

Where it lives

compiler/rustc_span/src/span_encoding.rs — the four formats, the match_span_kind! macro, SpanField.
compiler/rustc_span/src/hygiene.rs — SyntaxContext, the interning table, the forbidden Ord.

Takeaway

Two lessons. First: when an enum’s discriminant is in the hot path, the source-level enum may not be the best representation — a packed integer with a prefix, decoded by a macro, can be strictly faster, and the macro lets you keep the readable version. Second: impl !Ord is a real technique. Sometimes the best way to guarantee a property (deterministic iteration order) is to remove a trait from a type so that the compiler enforces it everywhere.