Skip to main content

rapx/
verify.rs

1//! The staged verification pipeline and crate-level verification driver.
2//!
3//! Contract-based, path-sensitive verification of safety properties: collect
4//! targets and contracts, extract SCC-aware paths, slice them backward, execute
5//! the relevant MIR symbolically, and discharge each property with Z3.
6
7mod alias;
8mod auto_trait;
9mod checkpoint;
10pub(crate) mod config;
11mod display;
12mod function_verifier;
13mod loop_handling;
14mod marker_trait;
15mod path;
16mod proof_cache;
17mod property_checker;
18mod report;
19mod slicer;
20mod target;
21mod trait_ensurance;
22mod vm;
23
24pub(crate) use crate::analysis::dataflow::call_summary;
25pub(crate) use self::target::PrepareTargets;
26
27use std::rc::Rc;
28
29use rustc_hir::def_id::DefId;
30use rustc_middle::ty::TyCtxt;
31
32use crate::analysis::Analysis;
33use crate::compat::{FxHashMap, FxHashSet};
34use crate::util::{
35    fn_info::{get_cons, get_mutated_fields, get_muts},
36    name::short_fn_name,
37};
38use crate::contract::{
39    ContractExpr, ContractPlace, ContractProjection, PlaceBase, Property, PropertyArg,
40    annotation::get_contract_from_annotation, compound::register_compound_properties,
41    ensures::get_trait_method_ensures,
42};
43use self::{
44    config::{PostfixRepeat, VerifyConfig},
45    display::{
46        dedup_compound_props, emit_results_and_verdict, emit_verify_summary, fmt_contract_expanded,
47        fmt_fn_path_with_bounds, print_contracts_debug,
48    },
49    function_verifier::FunctionVerifier,
50    loop_handling::LoopSensitivityAnalyzer,
51    marker_trait::MarkerTraitVerifier,
52    proof_cache::{VmCache, new_z3_context},
53    report::{PropertyCheckResult, VerificationLimits},
54    target::{FunctionTarget, VerifyTargetCollector},
55    trait_ensurance::TraitEnsuranceKind,
56};
57
58/// Collects verification targets, schedules checks, and emits their summaries.
59pub(crate) struct VerifyDriver<'tcx> {
60    /// Compiler context for target collection and verification.
61    tcx: TyCtxt<'tcx>,
62    /// Verification options shared with target preparation and call handling.
63    config: Rc<VerifyConfig>,
64}
65
66#[derive(Default)]
67struct FunctionVerdicts<'tcx> {
68    results: Vec<PropertyCheckResult<'tcx>>,
69    has_obligations: bool,
70    limits: VerificationLimits,
71}
72
73impl<'tcx> VerifyDriver<'tcx> {
74    /// Create a verification pass with the selected options.
75    pub(crate) fn new(tcx: TyCtxt<'tcx>, config: Rc<VerifyConfig>) -> Self {
76        Self { tcx, config }
77    }
78
79    fn max_repeat_for_target(&self, target: &FunctionTarget<'tcx>) -> usize {
80        match &self.config.postfix_repeat {
81            PostfixRepeat::Fixed(n) => *n,
82            PostfixRepeat::Auto => LoopSensitivityAnalyzer::new(self.tcx).analyze(target),
83        }
84    }
85
86    /// With `--no-invariant-target`, generate verification sequences for each read method
87    /// that chain through constructors and mutators.
88    ///
89    /// Produces sequences like:
90    /// - `constructor → method`
91    /// - `constructor → mutator → method`
92    ///
93    /// Each sequence propagates the constructor's `#[rapx::requires]` through
94    /// the mutator chain to serve as entry assumptions for the read method.
95    /// TODO: This sequence analysis is incomplete; it currently considers at most one mutator.
96    fn run_invless_sequences(&self, targets: &[FunctionTarget<'tcx>]) {
97        for target in targets {
98            let read_def_id = target.def_id;
99            let cons = get_cons(self.tcx, read_def_id);
100            if cons.is_empty() {
101                continue;
102            }
103            let muts = get_muts(self.tcx, read_def_id);
104
105            for &con_id in &cons {
106                let con_target = self.build_virtual_target(target, read_def_id, con_id, &[]);
107                self.verify_and_emit_sequence(read_def_id, &con_target, con_id, &[]);
108
109                for &mut_id in &muts {
110                    let con_target = self.build_virtual_target(target, read_def_id, con_id, &[mut_id]);
111                    self.verify_and_emit_sequence(read_def_id, &con_target, con_id, &[mut_id]);
112                }
113            }
114        }
115    }
116
117    fn build_virtual_target(
118        &self,
119        read_target: &FunctionTarget<'tcx>,
120        read_def_id: DefId,
121        con_id: DefId,
122        mut_ids: &[DefId],
123    ) -> FunctionTarget<'tcx> {
124        let mut accumulated_requires: Vec<Property<'tcx>> = Vec::new();
125        // Start with the constructor's requires, remapped to refer to struct
126        // fields (self.field) instead of constructor parameters.
127        let con_contracts: Vec<Property<'tcx>> = get_contract_from_annotation(self.tcx, con_id)
128            .into_iter()
129            .map(|c| remap_constructor_contract(c))
130            .collect();
131        accumulated_requires.extend(con_contracts);
132
133        let mutated_fields: FxHashSet<_> = mut_ids.iter().flat_map(|&id| get_mutated_fields(self.tcx, id)).collect();
134        if !mutated_fields.is_empty() {
135            accumulated_requires.retain(|prop| {
136                let prop_fields = property_field_indices(prop);
137                !prop_fields.iter().any(|f| mutated_fields.contains(f))
138            });
139        }
140
141        // Also include the read method's own caller requires (which already
142        // contains struct invariants merged by build_function_target).
143        // This is broader than just `get_contract_from_annotation` because
144        // it propagates struct-level properties even when the method has no
145        // explicit `#[rapx::requires]`.
146        accumulated_requires.extend(read_target.caller_requires.clone());
147
148        FunctionTarget {
149            def_id: read_def_id,
150            body: read_target.body,
151            callee_bodies: read_target.callee_bodies.clone(),
152            owner_struct_def_id: read_target.owner_struct_def_id,
153            checkpoints: read_target.checkpoints.clone(),
154            callee_requires: read_target.callee_requires.clone(),
155            caller_requires: accumulated_requires,
156            invariants: Vec::new(),
157            declared_invariant_count: 0,
158            raw_ptr_deref_checks: read_target.raw_ptr_deref_checks.clone(),
159            static_mut_checks: read_target.static_mut_checks.clone(),
160        }
161    }
162
163    /// Run `verify_checkpoints` at every repeat depth up to `max_repeat`.
164    fn run_repeat_rounds(
165        &self,
166        target: &FunctionTarget<'tcx>,
167        max_repeat: usize,
168        all_results: &mut Vec<PropertyCheckResult<'tcx>>,
169        limits: &mut VerificationLimits,
170    ) {
171        let z3_ctx = new_z3_context();
172        let mut cache = VmCache::new(&z3_ctx, Rc::clone(&self.config));
173        for repeat in 0..=max_repeat {
174            let (results, round_limits) = FunctionVerifier::verify_checkpoints(self.tcx, target, repeat, Rc::clone(&self.config), &mut cache);
175            limits.merge(round_limits);
176            all_results.extend(results);
177        }
178    }
179
180    fn verify_and_emit_sequence(
181        &self,
182        read_def_id: DefId,
183        con_target: &FunctionTarget<'tcx>,
184        con_id: DefId,
185        mut_ids: &[DefId],
186    ) {
187        let mut all_results: Vec<PropertyCheckResult<'_>> = Vec::new();
188        let mut limits = VerificationLimits::default();
189        let max_repeat = self.max_repeat_for_target(con_target);
190        self.run_repeat_rounds(con_target, max_repeat, &mut all_results, &mut limits);
191
192        let read_name = short_fn_name(self.tcx, read_def_id);
193        let con_name = short_fn_name(self.tcx, con_id);
194        let mut chain_parts: Vec<String> = vec![con_name];
195        for &mut_id in mut_ids {
196            chain_parts.push(short_fn_name(self.tcx, mut_id));
197        }
198        chain_parts.push(read_name);
199        let chain_label = chain_parts.join(" -> ");
200
201        rap_info!("============================================================");
202        rap_info!("[rapx::verify] sequence: {chain_label}");
203        rap_info!("============================================================");
204
205        if all_results.is_empty() && !limits.path_limited {
206            rap_info!("  result: SOUND (no unsafe checkpoints)");
207        } else {
208            emit_results_and_verdict(&all_results, limits);
209        }
210        rap_info!("");
211    }
212}
213
214impl<'tcx> Analysis for VerifyDriver<'tcx> {
215    /// Collect targets, run each function verifier, and emit a compact summary.
216    ///
217    /// For each target, extracts paths with increasing `postfix-repeat`
218    /// levels from 0 to the configured maximum, running verification at each
219    /// level. Earlier rounds use fewer loop unrollings; later rounds incrementally
220    /// add deeper paths.
221    fn run(&mut self) {
222        register_compound_properties(self.tcx);
223        let mut collector = VerifyTargetCollector::collect_all(self.tcx, Rc::clone(&self.config));
224        if self.config.debug_contracts {
225            print_contracts_debug(self.tcx, &collector.function_targets, &collector.trait_targets);
226            return;
227        }
228
229        // Merge target results per function so monomorphized instances are reported once.
230        let mut function_verdicts: FxHashMap<DefId, FunctionVerdicts<'tcx>> = FxHashMap::default();
231        for target in &collector.function_targets {
232            let mut all_results: Vec<PropertyCheckResult<'_>> = Vec::new();
233            let mut limits = VerificationLimits::default();
234            let max_repeat = self.max_repeat_for_target(target);
235            // Check each repeat depth, collecting checkpoint results and coverage limits.
236            self.run_repeat_rounds(target, max_repeat, &mut all_results, &mut limits);
237
238            // Recheck collected invariants at function exits after checkpoint verification.
239            if !target.invariants.is_empty() && !self.config.skip_invariant {
240                let verifier = FunctionVerifier::new(self.tcx, target, max_repeat, None, Rc::clone(&self.config));
241                limits.merge(verifier.limits());
242                all_results.extend(verifier.verify_invariants());
243            }
244
245            let no_obligations = all_results.is_empty()
246                && target.checkpoints.iter().all(|ckpt| ckpt.callee.is_some() && target.properties_for_callsite(ckpt).is_empty())
247                && target.raw_ptr_deref_checks.is_empty()
248                && target.static_mut_checks.is_empty()
249                && target.declared_invariants().is_empty();
250
251            limits.mono_limited |= target.body.is_some();
252            let entry = function_verdicts.entry(target.def_id).or_default();
253            entry.results.extend(all_results);
254            entry.has_obligations |= !no_obligations;
255            entry.limits.merge(limits);
256        }
257
258        let mut ordered: Vec<DefId> = function_verdicts.keys().copied().collect();
259        ordered.sort_by_key(|d| self.tcx.def_path_str(*d));
260        for def_id in ordered {
261            let FunctionVerdicts { results: all_results, has_obligations, limits } =
262                function_verdicts.remove(&def_id).unwrap();
263            let target_path = fmt_fn_path_with_bounds(self.tcx, def_id);
264
265            if all_results.is_empty() && !limits.path_limited {
266                if !has_obligations {
267                    rap_info!("============================================================");
268                    rap_info!("[rapx::verify] function: {target_path}");
269                    rap_info!("============================================================");
270                    if self.config.skip_invariant {
271                        let cons = get_cons(self.tcx, def_id);
272                        for con in &cons {
273                            rap_info!("  + constructor: {}", self.tcx.def_path_str(*con));
274                        }
275                    }
276                    rap_info!("  result: SOUND (no properties to check)");
277                    rap_info!("");
278                }
279                continue;
280            }
281
282            // When --no-invariant-target is set, skip standalone emission for methods that
283            // have constructors — sequences will generate dedicated entries.
284            if self.config.skip_invariant && !get_cons(self.tcx, def_id).is_empty() {
285                continue;
286            }
287
288            emit_verify_summary(
289                self.tcx,
290                &target_path,
291                def_id,
292                &all_results,
293                self.config.skip_invariant,
294                limits,
295            );
296        }
297
298        let marker_verifier = MarkerTraitVerifier::new(self.tcx);
299        for trait_target in std::mem::take(&mut collector.trait_targets) {
300            let TraitEnsuranceKind::Unsafe(ensures) = &trait_target.kind else {
301                marker_verifier.emit(&[&trait_target]);
302                continue;
303            };
304            rap_info!("============================================================");
305            rap_info!("[rapx::verify] unsafe trait impl: {}", self.tcx.def_path_str(trait_target.def_id));
306            rap_info!("============================================================");
307            if let Some(self_ty) = trait_target.self_ty_def_id {
308                rap_info!("  impl for: {}", self.tcx.def_path_str(self_ty));
309            } else {
310                rap_info!("  impl: {}", self.tcx.def_path_str(trait_target.impl_def_id));
311            }
312            if ensures.is_empty() {
313                rap_info!("  ensures: <none>");
314            } else {
315                rap_info!("  ensures (implementor must satisfy):");
316                let mut checked_methods = FxHashSet::default();
317                for item in self.tcx.associated_items(trait_target.impl_def_id).in_definition_order() {
318                    let Some(trait_method) = item.trait_item_def_id() else {
319                        continue;
320                    };
321                    if !ensures.iter().any(|(name, _)| *name == self.tcx.def_path_str(trait_method)) {
322                        continue;
323                    }
324                    checked_methods.insert(self.tcx.def_path_str(trait_method));
325                    let postconditions = get_trait_method_ensures(self.tcx, item.def_id);
326                    rap_info!("    fn {}:", item.name());
327                    for property in dedup_compound_props(postconditions.iter()) {
328                        let (call, _) = fmt_contract_expanded(
329                            self.tcx, property, trait_target.self_ty_def_id, Some(item.def_id),
330                        );
331                        rap_info!("      - {call}");
332                    }
333                    if postconditions.is_empty() || !self.tcx.is_mir_available(item.def_id) {
334                        rap_warn!("      result: UNKNOWN (contract or MIR unavailable)");
335                        continue;
336                    }
337                    let target = collector.build_function_target(item.def_id, None);
338                    let max_repeat = self.max_repeat_for_target(&target);
339                    let mut results = Vec::new();
340                    let mut limits = VerificationLimits::default();
341                    for repeat in 0..=max_repeat {
342                        let verifier = FunctionVerifier::new(self.tcx, &target, repeat, None, Rc::clone(&self.config));
343                        limits.merge(verifier.limits());
344                        results.extend(verifier.verify_postconditions(&postconditions));
345                    }
346                    emit_results_and_verdict(&results, limits);
347                }
348                for (method_name, contracts) in ensures {
349                    if checked_methods.contains(method_name) {
350                        continue;
351                    }
352                    rap_info!("    fn {method_name}:");
353                    for property in dedup_compound_props(contracts.iter()) {
354                        let (call, _) = fmt_contract_expanded(self.tcx, property, trait_target.self_ty_def_id, None);
355                        rap_info!("      - {call}");
356                    }
357                    rap_warn!("      result: UNKNOWN (default method body not checked)");
358                }
359            }
360            rap_info!("");
361        }
362
363        if self.config.skip_invariant {
364            self.run_invless_sequences(&collector.function_targets);
365        }
366    }
367}
368
369/// Collect struct field indices referenced by a property's contract places.
370///
371/// Used to determine which invariants are invalidated when a mutator writes
372/// to specific struct fields.
373fn property_field_indices(property: &Property<'_>) -> Vec<usize> {
374    let mut indices = Vec::new();
375    for arg in property.args() {
376        let place = match arg {
377            PropertyArg::Expr(ContractExpr::Place(p)) | PropertyArg::ForEach(ContractExpr::Place(p)) => Some(p),
378            _ => None,
379        };
380        if let Some(place) = place {
381            for proj in &place.projections {
382                match proj {
383                    ContractProjection::Field { index } => {
384                        let idx = *index;
385                        if !indices.contains(&idx) {
386                            indices.push(idx);
387                        }
388                    }
389                    ContractProjection::Downcast { .. } => {}
390                    ContractProjection::ForEach => {}
391                }
392            }
393        }
394    }
395    indices
396}
397
398/// Remap constructor parameter references in an atomic contract to fields of `self`.
399fn remap_constructor_contract<'tcx>(property: Property<'tcx>) -> Property<'tcx> {
400    fn remap_place_arg<'tcx>(arg: &PropertyArg<'tcx>) -> PropertyArg<'tcx> {
401        let place = match arg {
402            PropertyArg::Expr(ContractExpr::Place(p)) | PropertyArg::ForEach(ContractExpr::Place(p)) => p,
403            _ => return arg.clone(),
404        };
405        let PlaceBase::Arg(field_idx) = place.base else {
406            return arg.clone();
407        };
408        let projection = ContractProjection::Field { index: field_idx };
409        let mut new_place = ContractPlace { base: PlaceBase::Arg(0), projections: vec![projection] };
410        new_place.projections.extend(place.projections.iter().cloned());
411        match arg {
412            PropertyArg::ForEach(_) => PropertyArg::ForEach(ContractExpr::Place(new_place)),
413            _ => PropertyArg::Expr(ContractExpr::Place(new_place)),
414        }
415    }
416
417    match property {
418        Property::Atom(mut atom) => {
419            atom.args = atom.args.iter().map(remap_place_arg).collect();
420            Property::Atom(atom)
421        }
422        Property::And(and) => Property::And(and),
423        Property::Or(or) => Property::Or(or),
424    }
425}