panicgraph 0.2.1

//! What the walk reads a body's values as.
//!
//! Every claim here is drawn from one statement or one call and says what a
//! local can hold at that point. The walk itself lives next door; this is
//! the half that answers what a value is, which is what decides whether a
//! check the compiler wrote can fail.

use std::cmp::Ordering::Less;

use rustc_abi::FieldIdx;
use rustc_index::IndexSlice;
use rustc_middle::{
    mir::{self, BinOp},
    ty::{self, Instance, Ty, TyCtxt, TypeVisitableExt, TypingEnv},
};
use rustc_span::DUMMY_SP;

use crate::{
    fold::Folder,
    state::{State, root_of},
    value::{self, Bounds, Fact, Known, LenRel, Ranks, Value, truncate},
};

impl<'tcx> Folder<'_, 'tcx> {
    /// Evaluates an rvalue against what the locals are known about.
    pub(crate) fn rvalue(
        &self,
        state: &State<'tcx>,
        rvalue: &mir::Rvalue<'tcx>,
    ) -> Fact<'tcx> {
        let value = match rvalue {
            mir::Rvalue::Use(operand, _) => {
                return self.traced(state, operand);
            }
            mir::Rvalue::Cast(mir::CastKind::IntToInt, operand, ty) => {
                self.cast(state, operand, *ty)
            }
            mir::Rvalue::Cast(
                mir::CastKind::Transmute
                | mir::CastKind::PointerExposeProvenance
                | mir::CastKind::PtrToPtr,
                operand,
                ty,
            ) => return self.reinterpreted(state, operand, *ty),
            // Unsizing an array gives a slice as long as the array's type
            // says it is, which is what settles the length checks written
            // against a fixed size buffer.
            mir::Rvalue::Cast(
                mir::CastKind::PointerCoercion(
                    ty::adjustment::PointerCoercion::Unsize,
                    _,
                ),
                operand,
                _,
            ) => return self.unsized_from(operand),
            mir::Rvalue::BinaryOp(op, pair) => {
                return self.operated(state, *op, pair);
            }
            mir::Rvalue::UnaryOp(mir::UnOp::Not, operand) => {
                self.exact(state, operand).map(|value| {
                    let bits = if value.ty.is_bool() {
                        u128::from(!value.truth())
                    } else {
                        truncate(!value.bits, value.width)
                    };
                    Value::Exact(Known { bits, ..value })
                })
            }
            mir::Rvalue::UnaryOp(mir::UnOp::PtrMetadata, operand) => {
                return self
                    .length_of(state, operand)
                    .map_or_else(Fact::default, Self::measuring);
            }
            // A reference is never null. Taking one of everything another
            // points at leaves a slice as long as that one was.
            mir::Rvalue::Ref(_, _, place)
            | mir::Rvalue::Reborrow(_, _, place) => {
                return Fact {
                    address: true,
                    ..self.reborrowed(state, place)
                };
            }
            mir::Rvalue::RawPtr(_, place) => {
                return Fact {
                    address: self.addressed(state, place),
                    ..self.reborrowed(state, place)
                };
            }
            // Reading the discriminant of an enum the walk has settled is
            // what folds the match below it.
            mir::Rvalue::Discriminant(place) => self.tag_read(state, place),
            mir::Rvalue::Aggregate(kind, fields) => {
                return self.aggregate(state, kind, fields);
            }
            _ => None,
        };
        Fact {
            value,
            ..Fact::default()
        }
    }

    /// What is known about a value built from its parts.
    fn aggregate(
        &self,
        state: &State<'tcx>,
        kind: &mir::AggregateKind<'tcx>,
        fields: &IndexSlice<FieldIdx, mir::Operand<'tcx>>,
    ) -> Fact<'tcx> {
        match kind {
            mir::AggregateKind::Adt(did, variant, args, ..) => Fact {
                tag: self.tag_of(*did, args, *variant),
                ..Fact::default()
            },
            // A fat pointer is built from a thin one and what it points at,
            // and for a slice that is how many elements it holds.
            mir::AggregateKind::RawPtr(..) => {
                let Some(meta) = fields.iter().nth(1) else {
                    return Fact::default();
                };
                let held = self.fact(state, meta).value;
                // A slice as long as the length of another is as long as
                // that other, which is what settles the check a copy between
                // the two writes.
                let paired = match held {
                    Some(Value::Length(of)) => Some(of),
                    _ => None,
                };
                // A slice cut to a length is exactly that long, so one cut
                // to the same length again is as long as it.
                let spans = match meta {
                    mir::Operand::Copy(from) | mir::Operand::Move(from) => {
                        from.as_local().filter(|of| !self.escapes(*of))
                    }
                    _ => None,
                };
                Fact {
                    extent: held.and_then(Value::bounds),
                    paired,
                    spans,
                    ..Fact::default()
                }
            }
            _ => Fact::default(),
        }
    }

    /// Whether a raw pointer taken of a place is an address.
    ///
    /// Each dereference on the way must go through a reference, a box, or a
    /// raw pointer the walk knows to be an address, since
    /// `&raw mut (*p).first` of a null `p` is null.
    fn addressed(&self, state: &State<'tcx>, place: &mir::Place<'tcx>) -> bool {
        place.iter_projections().all(|(through, element)| {
            if element != mir::ProjectionElem::Deref {
                return true;
            }
            let Some(ty) = self
                .monomorphize(through.ty(&self.mir.local_decls, self.tcx).ty)
            else {
                return false;
            };
            match ty.kind() {
                ty::Ref(..) => true,
                ty::Adt(def, _) => def.is_box(),
                ty::RawPtr(..) => {
                    through.projection.is_empty()
                        && self
                            .slot_of(&mir::Place::from(through.local))
                            .is_some_and(|slot| {
                                Self::known_at(state, slot).address
                            })
                }
                _ => false,
            }
        })
    }

    /// How long a slice a reborrow of a whole pointee is.
    ///
    /// Taking a reference to everything a pointer points at leaves a slice
    /// as long as the one it was taken of, which is what carries the length
    /// of a subslice built from its parts to the call that reads it.
    pub(crate) fn reborrowed(
        &self,
        state: &State<'tcx>,
        place: &mir::Place<'tcx>,
    ) -> Fact<'tcx> {
        let blank = Fact::default();
        let [mir::ProjectionElem::Deref] = place.projection.as_slice() else {
            return blank;
        };
        if self.escapes(place.local) {
            return blank;
        }
        let Some(decl) = self.mir.local_decls.get(place.local) else {
            return blank;
        };
        let Some(ty) = self.monomorphize(decl.ty) else {
            return blank;
        };
        let (ty::Ref(_, inner, _) | ty::RawPtr(inner, _)) = ty.kind() else {
            return blank;
        };
        if !matches!(inner.kind(), ty::Slice(_) | ty::Str) {
            return blank;
        }
        let held = Self::known_at(state, place.local);
        Fact {
            extent: held.extent,
            // A reborrow of everything a pointer points at is as long as
            // the slice behind that pointer, which is the claim itself.
            paired: held.paired.or(Some(place.local)),
            spans: held.spans,
            ..blank
        }
    }

    /// How long the slice an array was unsized into is.
    ///
    /// The array states its own length, so the slice made of it is exactly
    /// that long wherever it is read, and a check comparing two such
    /// lengths is one the walk can settle.
    pub(crate) fn unsized_from(
        &self,
        operand: &mir::Operand<'tcx>,
    ) -> Fact<'tcx> {
        let Some(count) = self.array_length(operand) else {
            return Fact::default();
        };
        let ty = self.tcx.types.usize;
        let Some(width) = self.width(ty) else {
            return Fact::default();
        };
        let end = Known {
            bits: u128::from(count),
            ty,
            width,
        };
        Fact {
            extent: Bounds::new(end, end),
            address: true,
            ..Fact::default()
        }
    }

    /// How many elements the array behind a pointer holds.
    pub(crate) fn array_length(
        &self,
        operand: &mir::Operand<'tcx>,
    ) -> Option<u64> {
        let source = self.ty_of(operand)?;
        let pointee = match source.kind() {
            ty::Ref(_, inner, _) | ty::RawPtr(inner, _) => *inner,
            _ => return None,
        };
        let ty::Array(_, count) = pointee.kind() else {
            return None;
        };
        count.try_to_target_usize(self.tcx)
    }

    /// Reads a value out at another type without changing its bits.
    ///
    /// An address and the value inside a nonzero wrapper both come out this
    /// way, and neither of them is zero.
    pub(crate) fn reinterpreted(
        &self,
        state: &State<'tcx>,
        operand: &mir::Operand<'tcx>,
        ty: Ty<'tcx>,
    ) -> Fact<'tcx> {
        let tag = self.niched(state, operand, ty);
        if self.fact(state, operand).address {
            return Fact {
                address: true,
                value: self.apart_from_zero(ty),
                tag,
                ..Fact::default()
            };
        }
        let value = self
            .monomorphize(operand.ty(&self.mir.local_decls, self.tcx))
            .filter(|source| self.is_nonzero(*source))
            .and_then(|_| self.apart_from_zero(ty));
        Fact {
            value,
            tag,
            ..Fact::default()
        }
    }

    /// The variant a value read at a niche encoded enum's own type holds.
    ///
    /// Such an enum carries no tag of its own: a variant with no fields is
    /// written as a value the payload could never take, so a payload the
    /// walk has ruled that value out for is the variant that carries one.
    /// It is what settles the match written under `NonZero::new`, and with
    /// it every check the standard library builds on one.
    ///
    /// Only an encoding with a single such value is read, which is what an
    /// option around a pointer or a nonzero number uses.
    pub(crate) fn niched(
        &self,
        state: &State<'tcx>,
        operand: &mir::Operand<'tcx>,
        ty: Ty<'tcx>,
    ) -> Option<u128> {
        let ty = self.monomorphize(ty)?;
        let ty::Adt(def, _) = ty.kind() else {
            return None;
        };
        if !def.is_enum() {
            return None;
        }
        let layout = self.tcx.layout_of(self.env.as_query_input(ty)).ok()?;
        let rustc_abi::Variants::Multiple {
            tag_encoding:
                rustc_abi::TagEncoding::Niche {
                    untagged_variant,
                    ref niche_variants,
                    niche_start,
                },
            ..
        } = layout.variants
        else {
            return None;
        };
        if niche_variants.start != niche_variants.last {
            return None;
        }
        let held = self.fact(state, operand);
        let apart = if held.address && niche_start == 0 {
            true
        } else {
            let source = self.ty_of(operand)?;
            let width = self.width(source)?;
            value::compare(
                BinOp::Ne,
                held,
                Fact::of(Value::Exact(Known {
                    bits: truncate(niche_start, width),
                    ty: source,
                    width,
                })),
            )?
        };
        apart.then(|| {
            def.discriminant_for_variant(self.tcx, untagged_variant).val
        })
    }

    /// Applies a binary operator to what its operands are known about.
    pub(crate) fn operated(
        &self,
        state: &State<'tcx>,
        op: BinOp,
        pair: &(mir::Operand<'tcx>, mir::Operand<'tcx>),
    ) -> Fact<'tcx> {
        let left = self.fact(state, &pair.0);
        let right = self.fact(state, &pair.1);
        // A value and the same value raised by a constant compare by what
        // was added, which is what settles the order check a range index
        // writes over `at` and `at + 4`.
        if let Some(truth) = self.stepped(state, op, pair) {
            return Fact {
                value: self.boolean(truth).map(Value::Exact),
                ..Fact::default()
            };
        }
        let value = self.binary(state, op, pair, left, right);
        Fact {
            over: self.raised(state, op, pair, right, value),
            value,
            order: self.ordered(state, op, pair, left, right),
            ..Fact::default()
        }
    }

    /// How a value compares with the one it was reached from.
    fn stepped(
        &self,
        state: &State<'tcx>,
        op: BinOp,
        pair: &(mir::Operand<'tcx>, mir::Operand<'tcx>),
    ) -> Option<bool> {
        let root =
            |operand: &mir::Operand<'tcx>| self.root_slot(state, operand);
        // A value compared with itself is the same value, whichever local
        // each side was read from.
        if let (Some(near), Some(far)) = (root(&pair.0), root(&pair.1))
            && near == far
        {
            return value::stepped(op, 0);
        }
        if let (Some(near), Some((of, step))) =
            (root(&pair.0), self.fact(state, &pair.1).over)
            && of == near
        {
            return value::stepped(op, step);
        }
        let (far, (of, step)) =
            (root(&pair.1), self.fact(state, &pair.0).over?);
        (far? == of).then(|| value::stepped(value::mirrored(op), step))?
    }

    /// The link back to the value an addition was reached from.
    ///
    /// It is only recorded where the sum stayed inside its type, so the
    /// claim is the arithmetic one rather than what the machine wraps to.
    /// The range of the value shows that where it has one; where it has
    /// none, being ordered under a referenced slice does instead, since a
    /// slice of sized elements holds at most half the addresses there are
    /// and a value under its length has that much room above it.
    fn raised(
        &self,
        state: &State<'tcx>,
        op: BinOp,
        pair: &(mir::Operand<'tcx>, mir::Operand<'tcx>),
        right: Fact<'tcx>,
        value: Option<Value<'tcx>>,
    ) -> Option<(mir::Local, u128)> {
        if op != BinOp::Add {
            return None;
        }
        let step = right.value?.exact()?;
        if step.is_signed() {
            return None;
        }
        let (mir::Operand::Copy(place) | mir::Operand::Move(place)) = &pair.0
        else {
            return None;
        };
        let left = self.fact(state, &pair.0);
        let kept = matches!(value, Some(Value::Within(_)))
            || self.under_memory(left, step);
        if !kept {
            return None;
        }
        Some((root_of(state, self.slot_of(place)?), step.bits))
    }

    /// Whether adding a constant to a value ordered under a slice's length
    /// stays inside the type.
    ///
    /// A slice of sized elements is at most half the address space long,
    /// so a value at most its length has the other half to spare, and a
    /// constant below that cannot carry the sum round.
    fn under_memory(&self, left: Fact<'tcx>, step: Known<'tcx>) -> bool {
        let Some(shift) = step.width.checked_sub(1) else {
            return false;
        };
        if step.bits > 1u128 << shift {
            return false;
        }
        left.order.each().any(|(_, of)| self.sized_elements(of))
    }

    /// Whether the slice behind a local has elements that take up space,
    /// which is what bounds how long it can be.
    ///
    /// Only a reference bounds it: safe code can build a raw slice pointer
    /// of any length.
    fn sized_elements(&self, of: mir::Local) -> bool {
        let Some(decl) = self.mir.local_decls.get(of) else {
            return false;
        };
        let Some(ty) = self.monomorphize(decl.ty) else {
            return false;
        };
        let ty::Ref(_, inner, _) = ty.kind() else {
            return false;
        };
        match inner.kind() {
            ty::Str => true,
            ty::Slice(element) => self
                .tcx
                .layout_of(self.env.as_query_input(*element))
                .is_ok_and(|layout| layout.size.bytes() > 0),
            _ => false,
        }
    }

    /// How the result of an operator is ordered against a slice's length.
    ///
    /// The remainder of an unsigned value by a length lands below it, which
    /// is what the slice's own bounds check asks, and a length divided by
    /// anything is no larger than itself. Both divisors are above zero
    /// wherever this runs, since the check the compiler writes in front of
    /// them has passed to get here.
    pub(crate) fn ordered(
        &self,
        state: &State<'tcx>,
        op: BinOp,
        pair: &(mir::Operand<'tcx>, mir::Operand<'tcx>),
        left: Fact<'tcx>,
        right: Fact<'tcx>,
    ) -> Ranks {
        match op {
            BinOp::Rem => match right.value {
                Some(Value::Length(of)) if self.unsigned(&pair.0) => {
                    Ranks::of(LenRel::BELOW, of)
                }
                _ => Ranks::none_held(),
            },
            BinOp::Div => match left.value {
                Some(Value::Length(of)) if self.unsigned(&pair.1) => {
                    Ranks::of(LenRel::AT_MOST, of)
                }
                _ => Ranks::none_held(),
            },
            BinOp::Sub => self.shortened(state, pair, left, right),
            BinOp::Add => Self::lengthened(left, right),
            _ => Ranks::none_held(),
        }
    }

    /// How an addition leaves a value ordered against a slice's length.
    ///
    /// A value with room to spare under a length keeps what is left of
    /// that room once a constant is added to it, which is what the read of
    /// everything past a byte asks. The sum cannot wrap: the length itself
    /// lies inside the type, and the value stays under it.
    fn lengthened(left: Fact<'tcx>, right: Fact<'tcx>) -> Ranks {
        let mut ranks = Ranks::none_held();
        let Some(added) = right.value.and_then(Value::exact) else {
            return ranks;
        };
        if added.is_signed() {
            return ranks;
        }
        let Ok(added) = u64::try_from(added.bits) else {
            return ranks;
        };
        for (rel, of) in left.order.each() {
            if let Some(left) = rel.raised(added) {
                ranks.add(left, of);
            }
        }
        ranks
    }

    /// How a subtraction leaves a value ordered against a slice's length.
    ///
    /// A value already measured against a length is still measured against
    /// it once a constant is taken off, and strictly below it once anything
    /// at all is. The value has to be at least what is taken off, or a
    /// build with the check turned off wraps it round to the top of the
    /// type instead of shortening it.
    pub(crate) fn shortened(
        &self,
        state: &State<'tcx>,
        pair: &(mir::Operand<'tcx>, mir::Operand<'tcx>),
        left: Fact<'tcx>,
        right: Fact<'tcx>,
    ) -> Ranks {
        let mut ranks = Ranks::none_held();
        let Some(taken) = right.value.and_then(Value::exact) else {
            return ranks;
        };
        let held = match (left.order.is_empty(), left.value) {
            (true, Some(Value::Length(of))) => Ranks::of(LenRel::AT_MOST, of),
            _ => left.order,
        };
        if taken.is_signed() || held.is_empty() {
            return ranks;
        }
        let under = self
            .spread(state, &pair.0)
            .and_then(|span| span.lo.order(taken))
            .is_none_or(|by| by == Less);
        if under {
            return ranks;
        }
        let Ok(taken) = u64::try_from(taken.bits) else {
            return ranks;
        };
        for (rel, of) in held.each() {
            ranks.add(rel.lowered(taken), of);
        }
        ranks
    }

    /// Whether an operand is read as an unsigned integer.
    pub(crate) fn unsigned(&self, operand: &mir::Operand<'tcx>) -> bool {
        self.ty_of(operand)
            .is_some_and(|ty| matches!(ty.kind(), ty::Uint(_)))
    }

    /// The value the discriminant of a settled place reads as.
    pub(crate) fn tag_read(
        &self,
        state: &State<'tcx>,
        place: &mir::Place<'tcx>,
    ) -> Option<Value<'tcx>> {
        let slot = self.slot_of(place)?;
        let tag = Self::known_at(state, slot).tag?;
        let ty = self.enum_at(place)?;
        let ty::Adt(def, _) = ty.kind() else {
            return None;
        };
        for variant in def.variants().indices() {
            let discr = def.discriminant_for_variant(self.tcx, variant);
            if discr.val != tag {
                continue;
            }
            let width = self.width(discr.ty)?;
            return Some(Value::Exact(Known {
                bits: truncate(discr.val, width),
                ty: discr.ty,
                width,
            }));
        }
        None
    }

    /// The tag one variant of an enum carries.
    pub fn tag_of(
        &self,
        did: rustc_span::def_id::DefId,
        args: ty::GenericArgsRef<'tcx>,
        variant: rustc_abi::VariantIdx,
    ) -> Option<u128> {
        let ty = self.monomorphize(Ty::new_adt(
            self.tcx,
            self.tcx.adt_def(did),
            args,
        ))?;
        let ty::Adt(def, _) = ty.kind() else {
            return None;
        };
        if !def.is_enum() {
            return None;
        }
        Some(def.discriminant_for_variant(self.tcx, variant).val)
    }

    /// The enum type of a place, when it is one.
    pub(crate) fn enum_at(&self, place: &mir::Place<'tcx>) -> Option<Ty<'tcx>> {
        let ty = self.ty_at(place)?;
        matches!(ty.kind(), ty::Adt(def, _) if def.is_enum()).then_some(ty)
    }

    /// The local an operand's claims are recorded against, when it has one.
    pub(crate) fn root_slot(
        &self,
        state: &State<'tcx>,
        operand: &mir::Operand<'tcx>,
    ) -> Option<mir::Local> {
        let (mir::Operand::Copy(place) | mir::Operand::Move(place)) = operand
        else {
            return None;
        };
        self.slot_of(place).map(|slot| root_of(state, slot))
    }

    /// The length a wide pointer carries, when the pointee is a slice.
    pub(crate) fn length_of(
        &self,
        state: &State<'tcx>,
        operand: &mir::Operand<'tcx>,
    ) -> Option<Value<'tcx>> {
        let local = self.root_slot(state, operand)?;
        let ty = self.ty_of(operand)?;
        let pointee = match ty.kind() {
            ty::Ref(_, inner, _) | ty::RawPtr(inner, _) => *inner,
            _ => return None,
        };
        if !matches!(pointee.kind(), ty::Slice(_) | ty::Str) {
            return None;
        }
        Some(Value::Length(local))
    }

    /// The claim a reading of a slice's length carries.
    ///
    /// A length is at most itself. Saying so outright is what lets a value
    /// that started as one keep an ordering where a loop's arms meet: the
    /// turn that walks back carries a bound, and the two agree on the
    /// weaker of them rather than on nothing.
    pub fn measuring(value: Value<'tcx>) -> Fact<'tcx> {
        let order = match value {
            Value::Length(of) => Ranks::of(LenRel::AT_MOST, of),
            _ => Ranks::none_held(),
        };
        Fact {
            order,
            ..Fact::of(value)
        }
    }

    /// Reads an operand, when its value is settled.
    pub(crate) fn exact(
        &self,
        state: &State<'tcx>,
        operand: &mir::Operand<'tcx>,
    ) -> Option<Known<'tcx>> {
        value::pinned(self.fact(state, operand))
    }

    /// Reads everything known about an operand, reading through its link
    /// of sameness.
    ///
    /// A link always names a local that carries no link of its own, so one
    /// step is all there ever is. A claim held locally and one held at the
    /// source were both true when made and neither has been swept, so
    /// whichever exists is usable.
    pub fn fact(
        &self,
        state: &State<'tcx>,
        operand: &mir::Operand<'tcx>,
    ) -> Fact<'tcx> {
        match operand {
            mir::Operand::Copy(place) | mir::Operand::Move(place) => {
                let mut held =
                    self.slot_of(place).map_or_else(Fact::default, |slot| {
                        Self::known_at(state, slot)
                    });
                if matches!(
                    operand.ty(&self.mir.local_decls, self.tcx).kind(),
                    ty::Ref(..)
                ) {
                    held.address = true;
                }
                held
            }
            mir::Operand::Constant(konst) => {
                if let Some(sliced) = self.sliced(konst) {
                    return sliced;
                }
                let tag = self.variant_of(konst);
                self.constant(konst).map(Value::Exact).map_or_else(
                    || Fact {
                        tag,
                        ..Fact::default()
                    },
                    |value| Fact {
                        tag,
                        ..Fact::of(value)
                    },
                )
            }
            // Whether a check is on is settled by the session compiling the
            // crate, which is what makes a standard library block vanish in
            // a build that turns the check off.
            mir::Operand::RuntimeChecks(check) => self
                .boolean(check.value(self.tcx.sess))
                .map(Value::Exact)
                .map_or_else(Fact::default, Fact::of),
        }
    }

    /// Everything known about one local, read through its link of
    /// sameness.
    pub fn known_at(state: &State<'tcx>, local: mir::Local) -> Fact<'tcx> {
        let Some(own) = state.get(local.as_usize()).copied() else {
            return Fact::default();
        };
        let held = own.same.map_or(own, |root| {
            let at_root =
                state.get(root.as_usize()).copied().unwrap_or_default();
            // A copy denotes what its source did, so what the source is
            // known about stands for the copy as well.
            Fact {
                value: own.value.or(at_root.value),
                order: if own.order.is_empty() {
                    at_root.order
                } else {
                    own.order
                },
                extent: own.extent.or(at_root.extent),
                paired: own.paired.or(at_root.paired),
                spans: own.spans.or(at_root.spans),
                address: own.address || at_root.address,
                ..own
            }
        });
        let Some(Value::Length(of)) = held.value else {
            return Self::ranged(state, held);
        };
        let behind = state.get(of.as_usize()).copied().unwrap_or_default();
        Fact {
            extent: behind.extent,
            paired: behind.paired,
            ..held
        }
    }

    /// The claim an ordering against a slice of known length amounts to.
    ///
    /// An index below a length that lies in a range lies in that range
    /// too, one short of its top. That is what carries a bound proved
    /// against one slice into a read of a second slice known to be as
    /// long.
    pub(crate) fn ranged(state: &State<'tcx>, held: Fact<'tcx>) -> Fact<'tcx> {
        let Some((rel, of)) = held.order.first() else {
            return held;
        };
        // A slice is measured by how long it was found to be, and a number
        // by the range it was found to lie in.
        let Some(extent) = state.get(of.as_usize()).and_then(|slot| {
            slot.extent.or_else(|| slot.value.and_then(Value::bounds))
        }) else {
            return held;
        };
        if extent.hi.is_signed() {
            return held;
        }
        let top = extent
            .hi
            .bits
            .checked_sub(u128::from(rel.short))
            .map(|bits| Known { bits, ..extent.hi });
        let Some(bound) = top.and_then(|hi| Bounds::new(extent.hi.zero(), hi))
        else {
            return held;
        };
        Fact {
            value: Some(held.value.map_or(Value::Within(bound), |known| {
                known.refined(Value::Within(bound))
            })),
            ..held
        }
    }

    /// Reads an operand for an assignment, recording where a copy of a
    /// plain local came from.
    ///
    /// The link is kept even when the value itself is known: a fact the
    /// source learns later still has to reach the checks that read the
    /// copy, and the link is how it travels.
    pub(crate) fn traced(
        &self,
        state: &State<'tcx>,
        operand: &mir::Operand<'tcx>,
    ) -> Fact<'tcx> {
        let mut fact = self.fact(state, operand);
        let (mir::Operand::Copy(place) | mir::Operand::Move(place)) = operand
        else {
            return fact;
        };
        let Some(local) = self.slot_of(place) else {
            return fact;
        };
        let root = root_of(state, local);
        if !self.escapes(root) {
            fact.same = Some(root);
        }
        fact
    }

    /// The variant an enum written as a constant holds.
    ///
    /// A variant carrying no fields is written into the body as a constant
    /// rather than built by a constructor, so the tag has to be read out of
    /// the value the compiler laid down. Without it a `match` on such a
    /// variant walks every arm, including the one that panics.
    fn variant_of(&self, konst: &mir::ConstOperand<'tcx>) -> Option<u128> {
        let ty = self.monomorphize(konst.const_.ty())?;
        let ty::Adt(def, _) = ty.kind() else {
            return None;
        };
        if !def.is_enum() {
            return None;
        }
        let layout = self.tcx.layout_of(self.env.as_query_input(ty)).ok()?;
        let rustc_abi::Variants::Multiple {
            tag,
            tag_encoding: rustc_abi::TagEncoding::Direct,
            tag_field,
            ..
        } = &layout.variants
        else {
            return None;
        };
        let size = tag.size(&self.tcx);
        let held = konst.const_.eval(self.tcx, self.env, konst.span).ok()?;
        let scalar = match held {
            mir::ConstValue::Scalar(scalar) => scalar,
            mir::ConstValue::Indirect { alloc_id, offset } => {
                let at = offset.checked_add(
                    layout.fields.offset(tag_field.as_usize()),
                    &self.tcx,
                )?;
                let mir::interpret::GlobalAlloc::Memory(alloc) =
                    self.tcx.global_alloc(alloc_id)
                else {
                    return None;
                };
                alloc
                    .inner()
                    .read_scalar(
                        &self.tcx,
                        mir::interpret::alloc_range(at, size),
                        false,
                    )
                    .ok()?
            }
            _ => return None,
        };
        Some(scalar.try_to_scalar_int().ok()?.to_bits(size))
    }

    /// How long the slice a constant refers to is.
    ///
    /// A byte string, or a slice a constant item holds, carries its length
    /// as the metadata the compiler laid down beside the pointer, so a
    /// check written against that length is settled the way one against
    /// an array's is, and the reference itself is an address.
    fn sliced(&self, konst: &mir::ConstOperand<'tcx>) -> Option<Fact<'tcx>> {
        let ty = self.monomorphize(konst.const_.ty())?;
        let ty::Ref(_, inner, _) = ty.kind() else {
            return None;
        };
        if !matches!(inner.kind(), ty::Slice(_) | ty::Str) {
            return None;
        }
        let konst = self.resolved(konst)?;
        // A literal is laid down with its length beside it. A constant
        // item of slice type is laid down as memory holding the wide
        // pointer, so its length is the word after the pointer.
        let bits = match konst.eval(self.tcx, self.env, DUMMY_SP).ok()? {
            mir::ConstValue::Slice { meta, .. } => u128::from(meta),
            mir::ConstValue::Indirect { alloc_id, offset } => {
                self.metadata_at(alloc_id, offset)?
            }
            _ => return None,
        };
        let ty = self.tcx.types.usize;
        let end = Known {
            bits,
            ty,
            width: self.width(ty)?,
        };
        Some(Fact {
            extent: Bounds::new(end, end),
            address: true,
            ..Fact::default()
        })
    }

    /// The length half of a wide pointer a constant holds in memory.
    fn metadata_at(
        &self,
        alloc_id: mir::interpret::AllocId,
        offset: rustc_abi::Size,
    ) -> Option<u128> {
        let mir::interpret::GlobalAlloc::Memory(alloc) =
            self.tcx.global_alloc(alloc_id)
        else {
            return None;
        };
        let size = self.tcx.data_layout.pointer_size();
        let at = offset.checked_add(size, &self.tcx)?;
        let scalar = alloc
            .inner()
            .read_scalar(
                &self.tcx,
                mir::interpret::alloc_range(at, size),
                false,
            )
            .ok()?;
        Some(scalar.try_to_scalar_int().ok()?.to_bits(size))
    }

    /// A constant written in the body, resolved for the arguments the body
    /// was reached with.
    ///
    /// A body still carrying parameters has no value for a constant written
    /// against one: `<T as SizedTypeProperties>::SIZE` is exactly what the
    /// interesting checks compare against, and it has none until `T` has
    /// one. A constant that names no parameter is the same in every
    /// instantiation, so it is read where it stands.
    fn resolved(
        &self,
        konst: &mir::ConstOperand<'tcx>,
    ) -> Option<mir::Const<'tcx>> {
        if self.inst.args.has_param() {
            if konst.const_.has_param() {
                return None;
            }
            return Some(konst.const_);
        }
        instantiate(self.tcx, self.inst, self.env, konst.const_)
    }

    /// Evaluates an integer constant for the arguments this body was
    /// reached with.
    pub(crate) fn constant(
        &self,
        konst: &mir::ConstOperand<'tcx>,
    ) -> Option<Known<'tcx>> {
        let konst = self.resolved(konst)?;
        let ty = konst.ty();
        let width = self.width(ty)?;
        let bits = konst.try_eval_bits(self.tcx, self.env)?;
        Some(Known {
            bits: truncate(bits, width),
            ty,
            width,
        })
    }

    /// Widens or narrows a value to another integer type.
    ///
    /// A value nothing is known about still lies inside its own type, and
    /// that is the whole claim where the source is narrow: a byte read into
    /// an index is below two hundred and fifty six wherever it came from.
    pub(crate) fn cast(
        &self,
        state: &State<'tcx>,
        operand: &mir::Operand<'tcx>,
        ty: Ty<'tcx>,
    ) -> Option<Value<'tcx>> {
        let source = self.ty_of(operand)?;
        let held = self.fact(state, operand).value;
        if matches!(held, Some(Value::Length(_))) {
            return None;
        }
        let value = match held {
            Some(value) if value.ty() == Some(source) => value,
            _ => Value::Within(self.whole(source)?),
        };
        let ty = self.monomorphize(ty)?;
        let width = self.width(ty)?;
        match value {
            Value::Exact(known) => {
                Some(Value::Exact(Self::converted(known, ty, width)))
            }
            // A cast that cannot lose information keeps values apart, so
            // whatever the source differs from, the result differs from too.
            Value::Other(known) if width >= known.width => {
                Some(Value::other_than(Self::converted(known, ty, width)))
            }
            // A range survives a cast only when both ends keep their
            // mathematical value, which is when the map is order preserving.
            Value::Within(bounds) => {
                let lo = Self::preserved(bounds.lo, ty, width)?;
                let hi = Self::preserved(bounds.hi, ty, width)?;
                Bounds::new(lo, hi).map(Value::Within)
            }
            _ => None,
        }
    }

    /// Reads a value at another integer type, when the value fits.
    pub(crate) fn preserved(
        value: Known<'tcx>,
        ty: Ty<'tcx>,
        width: u32,
    ) -> Option<Known<'tcx>> {
        let semantic = |known: Known<'tcx>| {
            if known.is_signed() {
                Some(known.as_signed())
            } else {
                i128::try_from(known.bits).ok()
            }
        };
        let converted = Self::converted(value, ty, width);
        (semantic(value)? == semantic(converted)?).then_some(converted)
    }

    /// Reads a value at another integer type.
    ///
    /// Narrowing keeps the low bits and widening copies the sign of the
    /// source, which is what the machine does.
    pub(crate) fn converted(
        value: Known<'tcx>,
        ty: Ty<'tcx>,
        width: u32,
    ) -> Known<'tcx> {
        let extended = if value.is_signed() {
            value.as_signed().cast_unsigned()
        } else {
            value.bits
        };
        Known {
            bits: truncate(extended, width),
            ty,
            width,
        }
    }

    /// Applies an operator the folder can evaluate.
    ///
    /// Arithmetic is followed only where every end of the result lands
    /// inside its type. Past that the machine wraps and the arithmetic does
    /// not, and a claim drawn from the wrong one drops a panic that is
    /// real. The remaining two bound their result by construction: a
    /// remainder by a constant and a masked value cannot leave the range the
    /// operator itself defines.
    pub(crate) fn binary(
        &self,
        state: &State<'tcx>,
        op: BinOp,
        pair: &(mir::Operand<'tcx>, mir::Operand<'tcx>),
        left: Fact<'tcx>,
        right: Fact<'tcx>,
    ) -> Option<Value<'tcx>> {
        if let Some(truth) = value::compare(op, left, right) {
            return self.boolean(truth).map(Value::Exact);
        }
        if let Some(truth) = self.related(state, op, pair) {
            return self.boolean(truth).map(Value::Exact);
        }
        // A value nothing is known about still lies inside its own type,
        // and that alone settles a check written against the end of it:
        // nothing unsigned is below zero, which is what a range index turns
        // into once its other end is proved.
        if let Some(truth) = self
            .spread(state, &pair.0)
            .zip(self.spread(state, &pair.1))
            .and_then(|(left, right)| value::spans_compare(op, left, right))
        {
            return self.boolean(truth).map(Value::Exact);
        }
        if let (Some(Value::Exact(l)), Some(Value::Exact(r))) =
            (left.value, right.value)
            && let Some(known) = Self::settled(op, l, r)
        {
            return Some(Value::Exact(known));
        }
        match op {
            BinOp::Add | BinOp::Sub | BinOp::Mul => Self::spanned(
                op,
                self.spread(state, &pair.0)?,
                self.spread(state, &pair.1)?,
            ),
            BinOp::Div | BinOp::Rem => self.split(state, op, pair),
            BinOp::BitAnd | BinOp::BitOr | BinOp::BitXor => {
                self.bitwise(state, op, pair)
            }
            BinOp::Shl
            | BinOp::ShlUnchecked
            | BinOp::Shr
            | BinOp::ShrUnchecked => self.shifted(state, op, pair, right),
            _ => None,
        }
    }

    /// Evaluates a comparison between two locals one of which was measured
    /// against the other.
    ///
    /// A guard between two values the walk cannot settle still orders the
    /// pair, and that ordering is what the check between the two ends of a
    /// range asks. One step through a third value is followed as well: a
    /// value under another that is itself under a third is under that
    /// third, with both distances to spare.
    fn related(
        &self,
        state: &State<'tcx>,
        op: BinOp,
        pair: &(mir::Operand<'tcx>, mir::Operand<'tcx>),
    ) -> Option<bool> {
        let left = self.root_slot(state, &pair.0)?;
        let right = self.root_slot(state, &pair.1)?;
        let of_right = self.names(state, &pair.1);
        if let Some(rel) = Self::under(state, left, of_right) {
            return value::ordered_by(op, rel);
        }
        let of_left = self.names(state, &pair.0);
        let rel = Self::under(state, right, of_left)?;
        value::ordered_by(value::mirrored(op), rel)
    }

    /// The locals a claim about an operand's quantity can be recorded
    /// against: the local it was read from, and the slice it holds the
    /// length of, since a claim against a length names the slice.
    fn names(
        &self,
        state: &State<'tcx>,
        operand: &mir::Operand<'tcx>,
    ) -> [Option<mir::Local>; 2] {
        let slice = match self.fact(state, operand).value {
            Some(Value::Length(of)) => Some(of),
            _ => None,
        };
        [self.root_slot(state, operand), slice]
    }

    /// How far under a quantity a local sits, read from the claims it holds
    /// and one step through a local those name.
    fn under(
        state: &State<'tcx>,
        measured: mir::Local,
        of: [Option<mir::Local>; 2],
    ) -> Option<LenRel> {
        let against = |ranks: Ranks| {
            of.iter().flatten().find_map(|name| ranks.against(*name))
        };
        let held = Self::known_at(state, measured).order;
        if let Some(rel) = against(held) {
            return Some(rel);
        }
        held.each().find_map(|(first, mid)| {
            let second = against(state.get(mid.as_usize())?.order)?;
            Some(first.lowered(u64::from(second.short)))
        })
    }

    /// Whether a local holds a pointer to a slice, so that a claim naming it
    /// is about how long the slice is rather than about a number it holds.
    pub(crate) fn slice_behind(&self, local: mir::Local) -> bool {
        let Some(decl) = self.mir.local_decls.get(local) else {
            return false;
        };
        let Some(ty) = self.monomorphize(decl.ty) else {
            return false;
        };
        let (ty::Ref(_, inner, _) | ty::RawPtr(inner, _)) = ty.kind() else {
            return false;
        };
        matches!(inner.kind(), ty::Slice(_) | ty::Str)
    }

    /// The range a division or a remainder leaves behind.
    ///
    /// A remainder lies below its divisor and never above the value it was
    /// taken of, and a quotient moves with the value and against the
    /// divisor. Both are read as unsigned only: a signed remainder carries
    /// the sign of its left operand, and a signed division has a corner the
    /// type cannot hold. The divisor is above zero wherever this runs,
    /// since the check the compiler writes in front of it has passed to get
    /// here.
    pub(crate) fn split(
        &self,
        state: &State<'tcx>,
        op: BinOp,
        pair: &(mir::Operand<'tcx>, mir::Operand<'tcx>),
    ) -> Option<Value<'tcx>> {
        let left = self.spread(state, &pair.0)?;
        let right = self.spread(state, &pair.1)?;
        if left.lo.is_signed() || right.lo.is_signed() || right.lo.bits == 0 {
            return None;
        }
        let bounds = match op {
            BinOp::Div => Bounds::new(
                left.lo.quotient(right.hi)?,
                left.hi.quotient(right.lo)?,
            ),
            BinOp::Rem => Bounds::new(
                left.lo.zero(),
                left.hi.lesser(right.hi.predecessor()?)?,
            ),
            _ => return None,
        };
        bounds.map(Value::Within)
    }

    /// The range a bitwise operator leaves behind.
    ///
    /// An `and` keeps only the bits an operand already carried, so a side
    /// that is never negative bounds the result on its own. An `or` and an
    /// `xor` reach no higher than the topmost bit either side carries, and
    /// an `or` is never below the larger of the two, which is what keeps
    /// `d | 1` away from zero.
    pub(crate) fn bitwise(
        &self,
        state: &State<'tcx>,
        op: BinOp,
        pair: &(mir::Operand<'tcx>, mir::Operand<'tcx>),
    ) -> Option<Value<'tcx>> {
        let left = self.spread(state, &pair.0)?;
        let right = self.spread(state, &pair.1)?;
        if op == BinOp::BitAnd {
            let mut hi = None;
            for side in [left, right].iter().filter(|s| s.lo.nonnegative()) {
                hi = Some(match hi {
                    Some(held) => side.hi.lesser(held)?,
                    None => side.hi,
                });
            }
            return Bounds::new(left.lo.zero(), hi?).map(Value::Within);
        }
        if !left.lo.nonnegative() || !right.lo.nonnegative() {
            return None;
        }
        let hi = left.hi.greater(right.hi)?.saturated()?;
        let lo = if op == BinOp::BitOr {
            left.lo.greater(right.lo)?
        } else {
            left.lo.zero()
        };
        Bounds::new(lo, hi).map(Value::Within)
    }

    /// The range a shift by a settled amount leaves behind.
    ///
    /// The shift moves both ends of the range the same way, so what was an
    /// end of the value is an end of the result. Nothing is claimed unless
    /// the amount is settled: a shift the walk cannot read is a shift by
    /// anything.
    pub(crate) fn shifted(
        &self,
        state: &State<'tcx>,
        op: BinOp,
        pair: &(mir::Operand<'tcx>, mir::Operand<'tcx>),
        right: Fact<'tcx>,
    ) -> Option<Value<'tcx>> {
        let amount = right.value?.exact()?;
        if !amount.nonnegative() {
            return None;
        }
        let amount = u32::try_from(amount.bits).ok()?;
        let span = self.spread(state, &pair.0)?;
        Bounds::new(span.lo.shifted(op, amount)?, span.hi.shifted(op, amount)?)
            .map(Value::Within)
    }

    /// The range an arithmetic operator leaves behind.
    ///
    /// Each end is worked out as arithmetic rather than as the machine does
    /// it, and an end that would leave its type abandons the claim, so a
    /// result that wraps is never described by a range that cannot hold it.
    pub(crate) fn spanned(
        op: BinOp,
        left: Bounds<'tcx>,
        right: Bounds<'tcx>,
    ) -> Option<Value<'tcx>> {
        match op {
            BinOp::Add => Bounds::covering(&[
                left.lo.arith(op, right.lo)?,
                left.hi.arith(op, right.hi)?,
            ]),
            BinOp::Sub => Bounds::covering(&[
                left.lo.arith(op, right.hi)?,
                left.hi.arith(op, right.lo)?,
            ]),
            // With a sign in play the extreme can come from any pairing of
            // ends, so every corner has to land inside the type before any
            // of them describes the result.
            BinOp::Mul => Bounds::covering(&[
                left.lo.arith(op, right.lo)?,
                left.lo.arith(op, right.hi)?,
                left.hi.arith(op, right.lo)?,
                left.hi.arith(op, right.hi)?,
            ]),
            _ => None,
        }
        .map(Value::Within)
    }

    /// Applies an operator to two settled values.
    pub(crate) fn settled(
        op: BinOp,
        left: Known<'tcx>,
        right: Known<'tcx>,
    ) -> Option<Known<'tcx>> {
        if left.ty != right.ty || left.width != right.width {
            return None;
        }
        let bits = match op {
            BinOp::BitAnd => left.bits & right.bits,
            BinOp::BitOr => left.bits | right.bits,
            BinOp::BitXor => left.bits ^ right.bits,
            _ => return None,
        };
        Some(Known {
            bits: truncate(bits, left.width),
            ..left
        })
    }

    /// A `bool` the folder is certain of.
    fn boolean(&self, value: bool) -> Option<Known<'tcx>> {
        let ty = self.tcx.types.bool;
        Some(Known {
            bits: u128::from(value),
            ty,
            width: self.width(ty)?,
        })
    }

    /// The width of a type whose values are plain integers.
    ///
    /// Anything else is refused, so a float or a pointer never reaches the
    /// comparisons, where its bits would not mean what they say.
    pub fn width(&self, ty: Ty<'tcx>) -> Option<u32> {
        if !matches!(ty.kind(), ty::Bool | ty::Char | ty::Int(_) | ty::Uint(_))
        {
            return None;
        }
        let layout = self.tcx.layout_of(self.env.as_query_input(ty)).ok()?;
        u32::try_from(layout.size.bits()).ok()
    }

    /// Resolves a type written in the body against this instantiation.
    pub fn monomorphize(&self, ty: Ty<'tcx>) -> Option<Ty<'tcx>> {
        instantiate(self.tcx, self.inst, self.env, ty)
    }

    /// The type an operand is read at, resolved for this instantiation.
    pub fn ty_of(&self, operand: &mir::Operand<'tcx>) -> Option<Ty<'tcx>> {
        self.monomorphize(operand.ty(&self.mir.local_decls, self.tcx))
    }

    /// The type a place holds, resolved for this instantiation.
    pub fn ty_at(&self, place: &mir::Place<'tcx>) -> Option<Ty<'tcx>> {
        self.monomorphize(place.ty(&self.mir.local_decls, self.tcx).ty)
    }
}

/// Resolves something written in a body against the arguments the body was
/// reached with.
///
/// A type or a constant written against a generic parameter means nothing
/// until that parameter has one, so this is the step that turns it into a
/// value the walk can read.
pub fn instantiate<'tcx, T>(
    tcx: TyCtxt<'tcx>,
    inst: Instance<'tcx>,
    env: TypingEnv<'tcx>,
    value: T,
) -> Option<T>
where
    T: ty::TypeFoldable<TyCtxt<'tcx>>,
{
    inst.try_instantiate_mir_and_normalize_erasing_regions(
        tcx,
        env,
        ty::EarlyBinder::bind(tcx, value),
    )
    .ok()
}