rapx 0.7.63

//! Call summaries for the staged verifier: backward dependency (which call
//! arguments stay relevant) and forward effect (what facts a call adds).
pub(crate) mod effects;
pub(crate) mod dependencies;

use rustc_middle::{
    mir::Operand,
    ty::TyCtxt,
};

use crate::helpers::mir_utils;
use crate::verify::api_classify::is_branch;

/// Dependency summary consumed by the backward visitor.
#[derive(Clone, Debug)]
pub(crate) struct CallDependencySummary {
    /// If the call destination is relevant, these call arguments are relevant.
    pub return_depends_on_args: Vec<usize>,
    /// Arguments the callee writes; the backward slicer keeps them relevant so
    /// the write effect is applied.
    pub write_args: Vec<usize>,
}

impl CallDependencySummary {
    /// Conservative fallback: keep all arguments relevant.
    fn fallback(arg_count: usize) -> Self {
        Self {
            return_depends_on_args: (0..arg_count).collect(),
            write_args: Vec::new(),
        }
    }
}

/// Effect summary consumed by the forward visitor.
pub(crate) type CallEffectSummary = Vec<CallEffect>;

/// Path-local effect produced by a retained call.
#[derive(Clone, Debug)]
pub(crate) enum CallEffect {
    /// The return value aliases or is a direct value flow from an argument.
    ReturnAliasArg { arg: usize },
    /// The return value is a transparent copy of an argument's *value*
    /// (`MaybeUninit::assume_init`, `ManuallyDrop::into_inner`): same term and
    /// facts, retyped to the destination — no pointer `non_null` forcing.
    ReturnArgValue { arg: usize },
    ReturnOpaque,
    ReturnRawEq { left_arg: usize, right_arg: usize },
    ReturnExactDiv { lhs_arg: usize, rhs_arg: usize },
    /// `select_unpredictable(cond, x, y)` returns either `x` or `y`: the result
    /// is one of the two candidate values (`args[1]`/`args[2]`), non-deterministic
    /// since the boolean selector (`args[0]`) is unpredictable.
    SelectUnpredictable,
    /// The return value is a pointer extracted from an aggregate/reference arg.
    ReturnPointerFromArg { arg: usize },
    /// The return value is `base + offset * stride`.
    ReturnPointerAdd {
        base_arg: usize,
        offset_arg: usize,
        stride: Option<u64>,
        /// Whether the result is a *dereferenceable* pointer (its contract
        /// guarantees strict in-bounds, e.g. `SliceIndex::get_unchecked`), as
        /// opposed to plain `add` arithmetic whose result may be one-past-end.
        dereferenceable: bool,
    },
    ReturnWrappingPointerOffset { base_arg: usize, offset_arg: usize },
    ReturnPtrOffsetFrom { ptr_arg: usize, base_arg: usize },
    /// The return value is known to be non-zero.
    ReturnNonZero,
    /// The return value is known to satisfy a concrete alignment.
    ReturnAligned,
    /// The return value is a concrete layout/numeric constant.
    ReturnConst { value: u64 },
    /// The call writes one initialized element through a pointer argument.
    WriteMemory { pointer_arg: usize },
    CopyMemory { source_arg: usize, destination_arg: usize, count_arg: usize },
    SwapMemory { left_arg: usize, right_arg: usize },
    FillBytes { pointer_arg: usize, byte_arg: usize, count_arg: usize },
    /// The return value is a pointer backed by a fresh allocation of
    /// `size_arg` elements × `elem_size` bytes. The base address is taken
    /// from `pointer_arg`. Used for `from_raw_parts(ptr, len)`.
    ReturnFreshAllocation {
        pointer_arg: usize,
        size_arg: usize,
        elem_size: u64,
    },
    /// `alloc::alloc::exchange_malloc(size, align)` — a fresh allocation of
    /// `size_arg` bytes, returned as `*mut u8`.
    ReturnExchangeMalloc { size_arg: usize },
    /// The return value is `min(lhs_arg, rhs_arg)`, satisfying
    /// `return <= lhs_arg` and `return <= rhs_arg`.
    ReturnMin { lhs_arg: usize, rhs_arg: usize },
    /// The return value is `max(lhs_arg, rhs_arg)`.
    ReturnMax { lhs_arg: usize, rhs_arg: usize },
    /// The return value is `lhs_arg + rhs_arg`.
    ReturnAdd { lhs_arg: usize, rhs_arg: usize },
    /// The return value is `lhs_arg * rhs_arg`.
    ReturnMul { lhs_arg: usize, rhs_arg: usize },
    ReturnBoundedArithmetic {
        lhs_arg: usize,
        rhs_arg: usize,
        op: BoundedArithmeticOp,
    },
    ReturnWithOverflow {
        lhs_arg: usize,
        rhs_arg: usize,
        op: OverflowOp,
    },
    /// The return value is non-zero *iff* `arg` is non-zero (models bit-manipulating
    /// intrinsics like `bswap`/`bitreverse`/`ctpop`/`rotate_*`, which map `0` to
    /// `0` and non-zero to non-zero).
    ReturnNonZeroIff { arg: usize },
    /// The call returns `Option<T>` whose `Some` payload is unconditionally
    /// non-zero (models `checked_next_power_of_two`, where the next power of
    /// two is always positive regardless of the argument).
    ReturnOptionSomeNonZero,
    /// A specific field of the returned tuple carries the length of a given
    /// argument (e.g. split_at(mid) returns (left, right) where left.len() == mid).
    ReturnTupleFieldLength { field: usize, from_arg: usize },
    /// The return value is a pointer backed by a fresh heap allocation of
    /// `size_arg` elements × `elem_size` bytes. Unlike ReturnFreshAllocation
    /// this does not require a pointer argument — used for constructors like
    /// `Vec::from_elem(init, count)` that allocate fresh memory.
    ReturnNewAllocation { size_arg: usize, elem_size: u64 },
    /// `Box::new` / `Box::new_in` / `Box::new_uninit` / `Box::new_uninit_in`
    /// (and `try_` variants): allocate a fresh heap buffer of `size_of::<T>()`
    /// bytes and return a `Box` whose pointer field backs it.  These have MIR
    /// available but carry a `match` on the allocator's `Result`, which the
    /// inline heuristic rejects as a semantic branch, so a direct effect is the
    /// only way the fresh allocation's provenance reaches the `NonNull`.
    ReturnBoxAllocation,
    /// Like ReturnNewAllocation but the length is carried by the argument
    /// itself (a Box fat pointer) rather than a separate count argument.
    /// Used for `into_vec` / `box_assume_init_into_vec_unsafe`.
    ReturnNewAllocationFromBox,
    /// Like `ReturnNewAllocation`, but the argument is the *capacity*: the
    /// returned Vec starts empty (`len == 0`) with `cap == cap_arg` (models
    /// `Vec::with_capacity`).
    ReturnNewAllocationFromCap { cap_arg: usize, elem_size: u64 },
    /// The return value is a non-zero power of two (models `Layout::align`).
    ReturnPowerOfTwo,
    /// The call transfers a Vec's backing allocation into a Box (e.g.
    /// `Vec::into_boxed_slice`). Looks up the current heap allocation from the
    /// argument's owning pointer field via its stack provenance.
    ReturnBoxFromVec { arg: usize },
    /// The return value is known to own initialized memory of the type pointed
    /// to by the indicated argument (e.g. `Box::from_raw(p)` owns one initialized
    /// `T` element reached through `p`).
    OwnsInitMemory { arg: usize },
    /// The call returns `Option<usize>` whose `Some` payload is a scan index
    /// into the iterator argument `self_arg` (models `Iterator::position` /
    /// `Iterator::find`): `Some(i)` satisfies `0 <= i < self.len()` where
    /// `self` is the Iter/IterMut struct produced by `into_iter`/`iter`.
    ReturnOptionSomeScanIndex { self_arg: usize },
    /// The call is `Try::branch`: `Option<T>` -> `ControlFlow<Option<!>, T>`,
    /// so the result's `Continue` payload (field 0) equals the input's `Some`
    /// payload (field 0).  Models the `?` operator's `if let Some(..) = expr?`
    /// unwrap so the payload's provenance survives the branch.
    ReturnBranchPayload { arg: usize },
    /// The call returns the length of a nul-terminated string (models
    /// `strlen`): `0 <= len < isize::MAX`, so `len + 1` (the byte length with
    /// the terminator) fits in `isize::MAX` — discharging the
    /// `from_raw_parts` `ValidNum(size_of(T)*(len+1) <= isize::MAX)` bound.
    ReturnScanLength,
    /// `ptr.align_offset(align)` returns an offset such that
    /// `(ptr + offset) % align == 0` and `0 <= offset < align` (or `usize::MAX`
    /// when no such offset exists). Models `*const T::align_offset` /
    /// `*mut T::align_offset` by recording the alignment path-condition so
    /// downstream `ptr.add(offset)` dereferences can discharge `Align`.
    ReturnAlignOffset { ptr_arg: usize, align_arg: usize },
    /// A local `align_to`-style wrapper (`align_to_ext`/`align_to_mut_ext`)
    /// returns `(prefix, body, suffix)` where `body` is `align_of::<U>()`-aligned.
    /// Models the tuple by creating three sub-slices whose lengths/offsets obey
    /// `prefix.len() = offset` and `len - suffix.len() = offset + k*size_of::<U>()`,
    /// and records `(ptr + offset) % align_of::<U>() == 0` so downstream
    /// `ptr.add(offset - k)` dereferences can discharge `Align`.
    ReturnAlignTo { receiver_arg: usize },
    /// `<ManuallyDrop<T> as Deref>::deref` / `MaybeDangling::as_ref` return a
    /// reference to the inner value at the *same* address (transparent
    /// wrappers).  The return aliases `arg` (a `&T` pointing at `arg`'s
    /// pointee) and its pointee field values are the argument's field values
    /// with the leading `peel` transparent field-0 hops stripped.
    ReturnTransparentDeref { arg: usize, peel: usize },
    /// `slice::range(range, bounds)` returns `Range { start, end }` satisfying
    /// `0 <= start <= end <= bounds.end`. Models the range normalizer whose
    /// `start_bound`/`end_bound` trait dispatch cannot be inlined.
    ReturnRange { bounds_arg: usize },
    /// `mem::replace(dest, src)` returns `*dest` (the old value), so the return
    /// is the *pointee* of the reference argument, not the reference itself.
    ReturnDerefArg { arg: usize },
    /// The call *frees* the heap allocation behind `pointer_arg` (a `&mut`
    /// reference to a `Box`/`Vec`/`String` pointee). Models `ManuallyDrop::drop`.
    DropMemory { pointer_arg: usize },
    /// `<[T]>::index(range)` / `::index_mut(range)` returns a sub-slice whose
    /// length is the range's extent. Modelled as a sub-allocation of the array
    /// so downstream `into_iter`/`next()` see the correct element count.
    ReturnSliceRangeIndex,
    /// `Iter::len()` / `Iter::is_empty()` computed from the iterator's pointer
    /// fields (`ptr` + `end_or_len` sharing the same allocation).
    ReturnIterLen { is_len: bool },
    /// `NonNull::<T>::new(ptr) -> Option<NonNull<T>>`: the safe constructor,
    /// returning `Some(ptr)` when the pointer is provably non-null and an
    /// unconstrained `Option` otherwise.
    ReturnNonNullNew,
    /// `Iter::next()` / `IterMut::next()`: return the current element pointer
    /// and advance the iterator's tracked offset by one.
    ReturnIterNext,
    /// `Range<A>::next` / `RangeInclusive<A>::next`: return the current
    /// `start` and advance it by one, carrying the `start < end` bound so a
    /// downstream `InBound(arr, i)` can be discharged.
    ReturnRangeNext,
    /// `size_of::<T>()` / `align_of::<T>()` for a *generic* `T` (no concrete
    /// layout): the result is the shared symbolic `sizeof_T` / `align_T`, bound
    /// at apply time from `func`'s type argument.
    ReturnLayoutSymbolic { is_size: bool },
}

impl CallEffect {
    fn written_args(&self) -> Vec<usize> {
        match self {
            Self::WriteMemory { pointer_arg }
            | Self::DropMemory { pointer_arg }
            | Self::FillBytes { pointer_arg, .. } => vec![*pointer_arg],
            Self::CopyMemory { destination_arg, .. } => vec![*destination_arg],
            Self::SwapMemory { left_arg, right_arg } => vec![*left_arg, *right_arg],
            _ => Vec::new(),
        }
    }
}

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(crate) enum OverflowOp {
    Add,
    Sub,
    Mul,
}

#[derive(Clone, Copy, Debug)]
pub(crate) enum BoundedArithmeticOp {
    SaturatingAdd,
    SaturatingSub,
    WrappingSub,
}

/// Return dependency information for a MIR call terminator.
pub(crate) fn dependency_summary<'tcx>(
    tcx: TyCtxt<'tcx>,
    caller: rustc_hir::def_id::DefId,
    func: &Operand<'tcx>,
    destination: rustc_middle::mir::Local,
    arg_count: usize,
) -> CallDependencySummary {
    let callee = mir_utils::dep_callee_def_id(func);

    // MIR dataflow first: works for local and cross-crate (`#[inline]`)
    // callees alike, no hand-written table needed.
    if let Some(callee) = callee {
        if arg_count > 0
            && (crate::verify::api_classify::is_iter_next(Some(callee))
                || crate::verify::api_classify::is_range_next(Some(callee))
                || crate::def_ids::other_api::iterator_next_trait_fns().contains(&callee))
        {
            let mut summary = CallDependencySummary::fallback(arg_count);
            summary.write_args.push(0);
            return summary;
        }
        if let Some(summary) = effects::intrinsic_dependency_summary(
            tcx, caller, Some(callee), func, destination, arg_count,
        ) {
            return summary;
        }
        if mir_utils::is_drop_in_place(callee) {
            return CallDependencySummary::fallback(arg_count);
        }

        // Writes and return-dependencies are orthogonal: a callee can both
        // write an argument and return a value depending on another, so compute
        // both rather than clearing `return_depends_on_args` when a write exists.
        let write_args = match dependencies::local_write_args(tcx, callee) {
            Some(args) => args.into_iter().filter(|i| *i < arg_count).collect::<Vec<_>>(),
            None => tcx.fn_sig(callee).skip_binder().inputs().skip_binder().iter().enumerate()
                .filter_map(|(i, ty)| {
                    if i < arg_count && matches!(ty.kind(), rustc_middle::ty::TyKind::Ref(_, _, rustc_middle::ty::Mutability::Mut) | rustc_middle::ty::TyKind::RawPtr(_, rustc_middle::ty::Mutability::Mut)) {
                        Some(i)
                    } else {
                        None
                    }
                })
                .collect(),
        };
        let write_args = (!write_args.is_empty()).then_some(write_args);
        let return_deps = if is_branch(Some(callee)) {
            Some(vec![0])
        } else {
            dependencies::local_return_dependencies(tcx, callee)
                .map(|args| args.into_iter().filter(|i| *i < arg_count).collect::<Vec<_>>())
        };

        if write_args.is_some() || return_deps.is_some() {
            return CallDependencySummary {
                return_depends_on_args: return_deps.unwrap_or_default(),
                write_args: write_args.unwrap_or_default(),
            };
        }
    }

    CallDependencySummary::fallback(arg_count)
}