Skip to main content

rapx/verify/
engine.rs

1//! Symbolic-VM-based verification engine.
2//!
3//! Uses a semantic MIR executor to build symbolic state,
4//! then checks safety properties with a unified property checker.
5
6use z3::Config;
7
8use std::collections::HashMap;
9
10use rustc_hir::def_id::DefId;
11use rustc_middle::mir::{BasicBlock, Local, Operand, Rvalue, StatementKind};
12use rustc_middle::ty::TyCtxt;
13
14use crate::analysis::path::PathTree;
15
16use super::{
17    contract::{AndProperty, AtomProperty, OrProperty, Property},
18    report::{CheckResult, UnknownReason},
19    slicer::{BackwardSlicer, RelevantItem},
20};
21use crate::helpers::mir_scan::{Checkpoint, CheckpointLocation};
22
23use super::{
24    property_checker::PropertyChecker,
25    vm::SymbolicVm,
26};
27
28/// The three verification stages: a backward [`BackwardSlicer`], a
29/// [`SymbolicVm`], and a [`PropertyChecker`].
30pub(crate) struct VerifyEngine<'tcx> {
31    tcx: TyCtxt<'tcx>,
32    slicer: BackwardSlicer<'tcx>,
33    vm: SymbolicVm,
34    checker: PropertyChecker,
35}
36
37impl<'tcx> VerifyEngine<'tcx> {
38    /// Construct a fresh engine wired to `tcx`.
39    pub(crate) fn new(tcx: TyCtxt<'tcx>) -> Self {
40        Self {
41            tcx,
42            slicer: BackwardSlicer::new(tcx),
43            vm: SymbolicVm::new(),
44            checker: PropertyChecker,
45        }
46    }
47
48    /// Create a fresh Z3 context with a fixed 10s solver timeout.
49    ///
50    /// A new context is created per top-level check so that each verification
51    /// runs in isolation (no shared solver state leaks between checks).
52    fn new_z3_context() -> z3::Context {
53        let mut cfg = Config::new();
54        cfg.set_timeout_msec(10000);
55        z3::Context::new(&cfg)
56    }
57
58    /// Verify a property against every path reaching `checkpoint`, one result
59    /// per path. Each path is sliced backward from the checkpoint, replayed
60    /// symbolically by the VM, and finally discharged by the property checker.
61    ///
62    /// Returns `(result, path_description)` pairs in forward MIR order.
63    pub(crate) fn check_callsite_from_tree(
64        &self,
65        tree: &PathTree,
66        checkpoint: &Checkpoint<'tcx>,
67        property: &Property<'tcx>,
68        caller_contracts: &[Property<'tcx>],
69    ) -> Vec<(CheckResult, String)> {
70        let target_block = checkpoint.block.as_usize();
71        let mut results = Vec::new();
72        let backward_items = self
73            .slicer
74            .visit_path_tree(tree, target_block, checkpoint, property);
75
76        let bound_property = Self::bind_property_to_checkpoint(property, checkpoint);
77
78        let z3_ctx = Self::new_z3_context();
79
80        // Accumulate checked-bounds facts across checkpoints.
81        // A ChecksIndexBoundsDisjoint call in an earlier checkpoint
82        // can discharge InBound checks in a later checkpoint.
83        let mut accumulated_has_checked: bool = false;
84
85        // Map (def_id, local block) -> global block(s), computed once and reused
86        // by `inject_inline_boundaries` for every checkpoint.  A callee inlined
87        // at several call sites (e.g. `as_mut_ptr` called twice) contributes one
88        // global entry block per site, so the value is a list in path order.
89        let mut local_to_global: HashMap<(DefId, usize), Vec<usize>> = HashMap::new();
90        for (global, (def_id, local)) in tree.block_fns().iter().enumerate() {
91            local_to_global.entry((*def_id, *local)).or_default().push(global);
92        }
93
94        // Process checkpoints in forward (MIR) order so that facts
95        // collected by earlier calls are available to later checks.
96        let backward_items: Vec<_> = backward_items.into_iter().rev().collect();
97        for backward in backward_items {
98            let path_desc = backward.path.describe_indices();
99
100            let mut items = Vec::new();
101            if !caller_contracts.is_empty() {
102                items.extend(
103                    caller_contracts
104                        .iter()
105                        .filter(|c| {
106                            !matches!(c.kind(), Some(super::contract::PropertyKind::Unknown))
107                        })
108                        .map(|c| RelevantItem::ContractFact {
109                            property: c.clone(),
110                        }),
111                );
112            }
113            items.extend(backward.items);
114            // Insert inlined-callee boundary markers (argument binding / return
115            // write-back) based on def_id transitions across the path.
116            items =
117                Self::inject_inline_boundaries(items, tree, &local_to_global, checkpoint.caller);
118
119            let wrapped = crate::verify::slicer::ProofGoal {
120                path: backward.path,
121                items,
122                block_fn: backward.block_fn,
123            };
124
125            let vm_state = self.vm.run(&z3_ctx, self.tcx, wrapped);
126
127            // Accumulate checked bounds/disjointness facts across
128            // checkpoints so that a validator called in one checkpoint
129            // can discharge InBound checks in a later checkpoint.
130            accumulated_has_checked =
131                accumulated_has_checked || vm_state.path_facts.has_checked_bounds;
132            let mut vm_state = vm_state;
133            vm_state.path_facts.has_checked_bounds = accumulated_has_checked;
134
135            let result = self.checker.check(&vm_state, checkpoint, &bound_property);
136            results.push((result, path_desc));
137        }
138
139        results
140    }
141
142    /// Path-sensitive forward scan for the `Drop` hazard.
143    ///
144    /// `manually_drop::drop(&mut slot)` frees the heap behind `slot`, but `slot`
145    /// (a `ManuallyDrop` wrapper) stays live.  A later use of `slot` reads
146    /// through the freed allocation — a use-after-free.  Unlike the other
147    /// properties (checked at the checkpoint by the VM over a backward-sliced
148    /// path), this is a *forward* obligation, so it walks the complete paths of
149    /// the shared [`PathTree`] and checks the suffix after the drop call.
150    pub(crate) fn check_drop_from_tree(
151        &self,
152        tree: &PathTree,
153        checkpoint: &Checkpoint<'tcx>,
154    ) -> Vec<(CheckResult, String)> {
155        let Some(slot) = self.drop_referent_local(checkpoint) else {
156            return vec![(CheckResult::Unknown(UnknownReason::Unimplemented), String::new())];
157        };
158        let caller = checkpoint.caller;
159        let target = checkpoint.block.as_usize();
160
161        let mut results: Vec<(CheckResult, String)> = Vec::new();
162        for path in tree.iter() {
163            // A loop-unrolled path repeats the same caller block (the SCC body);
164            // its later drop occurrence is an unrolled iteration, not a genuine
165            // same-path use-after-drop. Only non-unrolled paths distinguish them
166            // (uaf_5 uses `slot` after the drop; uaf_false_2 drops once in a loop
167            // and never uses `slot` again).
168            let mut seen = std::collections::HashSet::new();
169            let unrolled = path.iter().any(|&g| {
170                tree.block_fn_of(g)
171                    .is_some_and(|(def, local)| def == caller && !seen.insert(local))
172            });
173            if unrolled {
174                continue;
175            }
176            let mut used = false;
177            let mut reaches = false;
178            for (pos, &g) in path.iter().enumerate() {
179                let Some((def, local)) = tree.block_fn_of(g) else {
180                    continue;
181                };
182                if def == caller && local == target {
183                    reaches = true;
184                    for &g2 in &path[pos + 1..] {
185                        let Some((def2, local2)) = tree.block_fn_of(g2) else {
186                            continue;
187                        };
188                        if def2 != caller {
189                            continue;
190                        }
191                        if Self::block_uses_local(self.tcx, caller, local2, slot) {
192                            used = true;
193                            break;
194                        }
195                    }
196                }
197            }
198            if reaches {
199                let desc = format!("{:?}", path);
200                if used {
201                    results.push((CheckResult::Failed, desc));
202                } else {
203                    results.push((CheckResult::ProvedByRule, desc));
204                }
205            }
206        }
207
208        if results.is_empty() {
209            vec![(CheckResult::ProvedByRule, String::new())]
210        } else {
211            results
212        }
213    }
214
215    /// Resolve the `&mut slot` borrow operand of a `Drop(slot)` checkpoint to the
216    /// referent local (`slot` itself, e.g. `_1`).  The optimized MIR lowers
217    /// `drop(&mut slot)` to a reborrow chain (`_7 = &mut (*_8)`, `_8 = &mut _1`),
218    /// so follow both direct borrows (`&mut _1`) and deref reborrows
219    /// (`&mut (*_8)`) back to the ultimate referent.
220    fn drop_referent_local(&self, checkpoint: &Checkpoint<'tcx>) -> Option<Local> {
221        let arg = checkpoint.args.first()?;
222        let place = crate::helpers::mir_utils::operand_mir_place(arg)?;
223        let mut cur = place.local;
224        let body = self.tcx.optimized_mir(checkpoint.caller);
225        let mut seen = std::collections::HashSet::new();
226        loop {
227            if !seen.insert(cur) {
228                return Some(cur);
229            }
230            let mut next: Option<Local> = None;
231            'outer: for bb in body.basic_blocks.iter() {
232                for stmt in &bb.statements {
233                    if let StatementKind::Assign(assign) = &stmt.kind {
234                        let (target, rvalue) = assign.as_ref();
235                        if target.local == cur && target.projection.is_empty() {
236                            if let Rvalue::Ref(_, _, referent) = rvalue {
237                                next = Some(referent.local);
238                                break 'outer;
239                            }
240                        }
241                    }
242                }
243            }
244            match next {
245                Some(l) => cur = l,
246                None => return Some(cur),
247            }
248        }
249    }
250
251    /// Whether any statement or terminator in `block` reads/writes `local`.
252    fn block_uses_local(tcx: TyCtxt<'tcx>, caller: DefId, block: usize, local: Local) -> bool {
253        let body = tcx.optimized_mir(caller);
254        let data = &body.basic_blocks[BasicBlock::from(block)];
255        for stmt in &data.statements {
256            if let StatementKind::Assign(assign) = &stmt.kind {
257                let (target, rvalue) = assign.as_ref();
258                if target.local == local {
259                    return true;
260                }
261                if crate::helpers::mir_utils::rvalue_any_place_matching(rvalue, &mut |p| {
262                    p.local == local
263                }) {
264                    return true;
265                }
266            }
267        }
268        if let Some(terminator) = &data.terminator {
269            use rustc_middle::mir::TerminatorKind;
270            match &terminator.kind {
271                TerminatorKind::Call { args, .. } => {
272                    if args.iter().any(|a| match &a.node {
273                        Operand::Copy(p) | Operand::Move(p) => p.local == local,
274                        Operand::Constant(_) => false,
275                        #[cfg(rapx_ge_95)]
276                        Operand::RuntimeChecks(_) => false,
277                    }) {
278                        return true;
279                    }
280                }
281                TerminatorKind::SwitchInt { discr, .. }
282                | TerminatorKind::Assert { cond: discr, .. } => match discr {
283                    Operand::Copy(p) | Operand::Move(p) => {
284                        if p.local == local {
285                            return true;
286                        }
287                    }
288                    Operand::Constant(_) => {}
289                    #[cfg(rapx_ge_95)]
290                    Operand::RuntimeChecks(_) => {}
291                },
292                TerminatorKind::Drop { place, .. } => {
293                    if place.local == local {
294                        return true;
295                    }
296                }
297                _ => {}
298            }
299        }
300        false
301    }
302
303    /// Insert `CalleeEntry`/`CalleeExit` markers into a forward item stream by
304    /// detecting `def_id` transitions (caller → callee → caller). Each inlined
305    /// callee entry carries its argument binding; each exit writes the callee's
306    /// return value back to the caller's destination.
307    ///
308    /// `local_to_global` maps `(def_id, local_block)` pairs to the list of
309    /// their global block indices in `tree` (a callee inlined at multiple call
310    /// sites has several entries, in path order); it is precomputed by the
311    /// caller so it can be reused across every checkpoint instead of rebuilt
312    /// per path.
313    fn inject_inline_boundaries(
314        items: Vec<RelevantItem<'tcx>>,
315        tree: &PathTree,
316        local_to_global: &HashMap<(DefId, usize), Vec<usize>>,
317        caller: DefId,
318    ) -> Vec<RelevantItem<'tcx>> {
319        let mut out: Vec<RelevantItem<'tcx>> = Vec::new();
320        // Start in the caller so a path that begins inside an inlined callee
321        // still emits its CalleeEntry on the first item.
322        let mut prev_def_id: Option<DefId> = Some(caller);
323        // Stack of entered callees, innermost last: (def_id, dest_local,
324        // entry global block). The entry block lets us resolve each callee's
325        // parent (`tree.inline_parent`) so a *nested* callee — one whose body
326        // is split around a further-inlined callee (e.g. `next_unchecked`
327        // calling `post_inc_start` and continuing afterwards) — is not popped
328        // from the frame stack until it actually returns.
329        let mut active: Vec<(DefId, usize, usize)> = Vec::new();
330        // How many times each (callee, parent) pair has been entered so far, to
331        // select the correct entry binding when the same callee is inlined at
332        // several call sites — possibly under *different* parents — along a
333        // single (loop-unrolled) path.
334        let mut entry_cursor: HashMap<(DefId, DefId), usize> = HashMap::new();
335
336        for item in items {
337            let cur_def_id = match &item {
338                RelevantItem::Statement { def_id, .. }
339                | RelevantItem::Terminator { def_id, .. } => Some(*def_id),
340                _ => None,
341            };
342
343            if let Some(cur) = cur_def_id {
344                if let Some(prev) = prev_def_id {
345                    if prev != cur {
346                        if cur == caller {
347                            // Returning to the root caller: pop *every* still-active
348                            // frame. Nested inlined callees whose return blocks
349                            // produced no items (a plain `return` has no relevant
350                            // use/def) are skipped in the item stream, so the
351                            // transition can jump several levels at once.
352                            while let Some((_, dest, _)) = active.pop() {
353                                out.push(RelevantItem::CalleeExit { dest });
354                            }
355                        } else {
356                            // Distinguish an *ascent* (`prev` returns to an
357                            // already-active `cur`, e.g. `post_inc_start` → the
358                            // split `next_unchecked`) from a *descent* (`cur` is
359                            // a fresh callee). In an ascent we pop frames down to
360                            // `cur` and do NOT re-enter it (it is already active).
361                            // Checking membership (rather than only the top's
362                            // parent) handles multi-level skips where several
363                            // callee return blocks produced no items.
364                            let is_ascent = active.iter().any(|(d, _, _)| *d == cur);
365                            if is_ascent {
366                                while let Some(&(top_def, _, _)) = active.last() {
367                                    if top_def == cur {
368                                        break;
369                                    }
370                                    let (_, dest, _) = active.pop().unwrap();
371                                    out.push(RelevantItem::CalleeExit { dest });
372                                }
373                            } else {
374                                // Descent into a fresh callee `cur`.
375                                let current_parent =
376                                    active.last().map(|(d, _, _)| *d).unwrap_or(caller);
377
378                                // The "effective parent" of an entry block: the
379                                // deepest ancestor (via `inline_parent`) that is
380                                // either the root caller or a currently-active
381                                // frame. Intermediate inlined callees whose blocks
382                                // produced no relevant items are skipped in the
383                                // item stream, so a transition can jump straight
384                                // from a shallow frame to a deep descendant.
385                                let eff_parent = |g: usize| -> DefId {
386                                    let mut p = tree.inline_parent(g);
387                                    while let Some(pd) = p {
388                                        if pd == caller
389                                            || active.iter().any(|(d, _, _)| *d == pd)
390                                        {
391                                            return pd;
392                                        }
393                                        p = local_to_global
394                                            .get(&(pd, 0))
395                                            .and_then(|gs| gs.first().copied())
396                                            .and_then(|pe| tree.inline_parent(pe));
397                                    }
398                                    caller
399                                };
400
401                                // Select `cur`'s entry block whose effective parent
402                                // matches the current innermost frame.
403                                let mut cur_entry: Option<usize> = None;
404                                if let Some(globals) = local_to_global.get(&(cur, 0)) {
405                                    let matching: Vec<usize> = globals
406                                        .iter()
407                                        .copied()
408                                        .filter(|&g| eff_parent(g) == current_parent)
409                                        .collect();
410                                    let pool: &[usize] = if matching.is_empty() {
411                                        globals.as_slice()
412                                    } else {
413                                        matching.as_slice()
414                                    };
415                                    let idx = if pool.len() == 1 {
416                                        0
417                                    } else {
418                                        let cursor =
419                                            entry_cursor.entry((cur, current_parent)).or_insert(0);
420                                        let idx = *cursor;
421                                        *cursor = (*cursor + 1).min(pool.len() - 1);
422                                        idx
423                                    };
424                                    cur_entry = pool.get(idx).copied();
425                                }
426
427                                // The frame `cur` connects to, and the inlined
428                                // callees skipped between it and `cur`.
429                                let eff = cur_entry.map(&eff_parent).unwrap_or(caller);
430                                let mut skipped: Vec<(DefId, usize)> = Vec::new();
431                                {
432                                    let mut p = cur_entry.and_then(|g| tree.inline_parent(g));
433                                    while let Some(pd) = p {
434                                        if pd == eff {
435                                            break;
436                                        }
437                                        if let Some(pe) = local_to_global
438                                            .get(&(pd, 0))
439                                            .and_then(|gs| gs.first().copied())
440                                        {
441                                            skipped.push((pd, pe));
442                                            p = tree.inline_parent(pe);
443                                        } else {
444                                            break;
445                                        }
446                                    }
447                                }
448
449                                // Pop down to the connection frame (`eff`; if it is
450                                // the root caller, pop everything).
451                                while let Some(&(top_def, _, _)) = active.last() {
452                                    if top_def == eff {
453                                        break;
454                                    }
455                                    let (_, dest, _) = active.pop().unwrap();
456                                    out.push(RelevantItem::CalleeExit { dest });
457                                }
458                                // Enter the skipped frames (farthest first), then
459                                // `cur` itself.
460                                for (pd, pe) in skipped.iter().rev() {
461                                    if let Some(binding) = tree.inline_binding(*pe) {
462                                        out.push(RelevantItem::CalleeEntry {
463                                            callee: *pd,
464                                            args: binding.arg_locals.clone(),
465                                        });
466                                        active.push((*pd, binding.dest_local, *pe));
467                                    }
468                                }
469                                if let Some(&global) = cur_entry.as_ref()
470                                    && let Some(binding) = tree.inline_binding(global)
471                                {
472                                    out.push(RelevantItem::CalleeEntry {
473                                        callee: cur,
474                                        args: binding.arg_locals.clone(),
475                                    });
476                                    active.push((cur, binding.dest_local, global));
477                                }
478                            }
479                        }
480                    }
481                }
482                prev_def_id = Some(cur);
483            }
484
485            out.push(item);
486        }
487
488        while let Some((_, dest, _)) = active.pop() {
489            out.push(RelevantItem::CalleeExit { dest });
490        }
491
492        out
493    }
494
495    /// Rewrite a property so its contract expressions refer to the caller's
496    /// argument positions at `checkpoint` rather than the callee's local
497    /// numbering. Recurses through `Atom`/`And`/`Or` nodes and clears `origin`
498    /// metadata (which only applies to the source-level property).
499    fn bind_property_to_checkpoint(
500        property: &Property<'tcx>,
501        checkpoint: &Checkpoint<'tcx>,
502    ) -> Property<'tcx> {
503        match property {
504            Property::Atom(atom) => {
505                let new_args: Vec<super::contract::PropertyArg<'tcx>> = atom
506                    .args
507                    .iter()
508                    .map(|a| match a {
509                        super::contract::PropertyArg::Expr(expr) => {
510                            super::contract::PropertyArg::Expr(Self::rebind_contract_expr(
511                                expr, checkpoint,
512                            ))
513                        }
514                        super::contract::PropertyArg::Predicates(predicates) => {
515                            let rebound: Vec<_> = predicates
516                                .iter()
517                                .map(|p| {
518                                    let lhs = Self::rebind_contract_expr(&p.lhs, checkpoint);
519                                    let rhs = Self::rebind_contract_expr(&p.rhs, checkpoint);
520                                    super::contract::NumericPredicate::new(lhs, p.op, rhs)
521                                })
522                                .collect();
523                            super::contract::PropertyArg::Predicates(rebound)
524                        }
525                        _ => a.clone(),
526                    })
527                    .collect();
528                Property::Atom(AtomProperty {
529                    kind: atom.kind,
530                    args: new_args,
531                    contract_kind: atom.contract_kind,
532                    for_each: atom
533                        .for_each
534                        .as_ref()
535                        .map(|p| Self::rebind_place(p, checkpoint)),
536                    origin: None,
537                })
538            }
539            Property::And(and) => {
540                Property::And(AndProperty {
541                    conjuncts: and
542                        .conjuncts
543                        .iter()
544                        .map(|p| Self::bind_property_to_checkpoint(p, checkpoint))
545                        .map(Box::new)
546                        .collect(),
547                    contract_kind: and.contract_kind,
548                    origin: None,
549                })
550            }
551            Property::Or(or) => {
552                Property::Or(OrProperty {
553                    disjuncts: or
554                        .disjuncts
555                        .iter()
556                        .map(|p| Self::bind_property_to_checkpoint(p, checkpoint))
557                        .map(Box::new)
558                        .collect(),
559                    contract_kind: or.contract_kind,
560                    origin: None,
561                })
562            }
563        }
564    }
565
566    /// Rewrite a contract place's base to the checkpoint's view.
567    ///
568    /// `Return` and `Arg` bases are unchanged; a `Local(n)` that falls within
569    /// the checkpoint's argument range is remapped to `Arg(n - 1)` (locals
570    /// 1..=k correspond to the callee's arguments in order).
571    fn rebind_place(
572        place: &super::contract::ContractPlace<'tcx>,
573        checkpoint: &Checkpoint<'tcx>,
574    ) -> super::contract::ContractPlace<'tcx> {
575        let new_base = match place.base {
576            super::contract::PlaceBase::Return => super::contract::PlaceBase::Return,
577            super::contract::PlaceBase::Arg(n) => super::contract::PlaceBase::Arg(n),
578            super::contract::PlaceBase::Local(n) => {
579                if n > 0 && n <= checkpoint.args.len() {
580                    super::contract::PlaceBase::Arg(n - 1)
581                } else {
582                    super::contract::PlaceBase::Local(n)
583                }
584            }
585        };
586        super::contract::ContractPlace {
587            base: new_base,
588            projections: place.projections.clone(),
589        }
590    }
591
592    /// Recursively rewrite every place embedded in a contract expression,
593    /// rebinding `Local` bases to argument positions via [`Self::rebind_place`].
594    fn rebind_contract_expr(
595        expr: &super::contract::ContractExpr<'tcx>,
596        checkpoint: &Checkpoint<'tcx>,
597    ) -> super::contract::ContractExpr<'tcx> {
598        match expr {
599            super::contract::ContractExpr::Place(place) => {
600                super::contract::ContractExpr::Place(Self::rebind_place(place, checkpoint))
601            }
602            super::contract::ContractExpr::Len(inner) => super::contract::ContractExpr::Len(
603                Box::new(Self::rebind_contract_expr(inner, checkpoint)),
604            ),
605            super::contract::ContractExpr::SizeOf(_)
606            | super::contract::ContractExpr::AlignOf(_)
607            | super::contract::ContractExpr::Const(_)
608            | super::contract::ContractExpr::ConstParam { .. }
609            | super::contract::ContractExpr::Unknown => expr.clone(),
610            super::contract::ContractExpr::IndexAccess { slice, index } => {
611                super::contract::ContractExpr::IndexAccess {
612                    slice: Box::new(Self::rebind_contract_expr(slice, checkpoint)),
613                    index: Box::new(Self::rebind_contract_expr(index, checkpoint)),
614                }
615            }
616            super::contract::ContractExpr::Binary { op, lhs, rhs } => {
617                super::contract::ContractExpr::Binary {
618                    op: *op,
619                    lhs: Box::new(Self::rebind_contract_expr(lhs, checkpoint)),
620                    rhs: Box::new(Self::rebind_contract_expr(rhs, checkpoint)),
621                }
622            }
623            super::contract::ContractExpr::Unary { op, expr: inner } => {
624                super::contract::ContractExpr::Unary {
625                    op: *op,
626                    expr: Box::new(Self::rebind_contract_expr(inner, checkpoint)),
627                }
628            }
629            super::contract::ContractExpr::If {
630                cond,
631                then_expr,
632                else_expr,
633            } => super::contract::ContractExpr::If {
634                cond: Box::new(super::contract::NumericPredicate::new(
635                    Self::rebind_contract_expr(&cond.lhs, checkpoint),
636                    cond.op,
637                    Self::rebind_contract_expr(&cond.rhs, checkpoint),
638                )),
639                then_expr: Box::new(Self::rebind_contract_expr(then_expr, checkpoint)),
640                else_expr: Box::new(Self::rebind_contract_expr(else_expr, checkpoint)),
641            },
642        }
643    }
644
645    /// Verify an invariant against every path reaching `checkpoint`.
646    ///
647    /// Unlike [`Self::check_callsite_from_tree`], there is no callsite to bind
648    /// against, so `entry_facts` are prepended to each sliced path and the
649    /// checker runs directly against the invariant. Returns
650    /// `(result, path_description)` pairs.
651    pub(crate) fn check_invariant_from_tree(
652        &self,
653        def_id: DefId,
654        tree: &PathTree,
655        checkpoint: CheckpointLocation,
656        invariant: &Property<'tcx>,
657        entry_facts: &[RelevantItem<'tcx>],
658    ) -> Vec<(CheckResult, String)> {
659        let target_block = checkpoint.block.as_usize();
660        let mut results = Vec::new();
661        let backward_items = self.slicer.visit_path_tree_for_checkpoint(
662            tree,
663            target_block,
664            def_id,
665            checkpoint,
666            invariant,
667        );
668
669        let z3_ctx = Self::new_z3_context();
670
671        for mut backward in backward_items {
672            let path_desc = backward.path.describe_indices();
673
674            if !entry_facts.is_empty() {
675                let mut items: Vec<RelevantItem<'tcx>> = entry_facts.to_vec();
676                items.extend(backward.items.drain(..));
677                backward.items = items;
678            }
679
680            let vm_state = self.vm.run(&z3_ctx, self.tcx, backward);
681
682            let fake_checkpoint = Checkpoint {
683                caller: def_id,
684                callee: None,
685                block: checkpoint.block,
686                args: Vec::new(),
687                kind: crate::helpers::mir_scan::CheckpointKind::UnsafeCall,
688                destination: None,
689                is_mut_ref: false,
690                statement_index: 0,
691            };
692            let result = self.checker.check(&vm_state, &fake_checkpoint, invariant);
693            results.push((result, path_desc));
694        }
695
696        results
697    }
698}