Skip to main content

rapx/contract/
type_invariants.rs

1//! Standard-library type-invariant generation.
2//!
3//! Type invariants are synthesized obligations that a value of a given type
4//! must satisfy. Unlike user-written `#[rapx::invariant]` struct invariants,
5//! these are generated automatically from the bundled `std-type-invariants.json`
6//! database, keyed by a normalized type path (e.g. `core::num::NonZero`) or by
7//! the built-in `[T]` slice key.
8//!
9//! The results join declared invariants on a verification target. Their entry
10//! facts are synthesized by the VM's `init_parameters` and re-proved at return
11//! by `FunctionVerifier::verify_invariants`.
12
13use crate::def_ids::type_ids;
14use crate::util::fn_info;
15use crate::util::mir_utils;
16use rustc_hir::def_id::DefId;
17use rustc_middle::ty::{self, Ty, TyCtxt};
18
19use crate::contract::{
20    json::AnyItem, ContractExpr, ContractPlace, ContractProjection, NumericPredicate, PlaceBase,
21    Property, PropertyArg, PropertyKind,
22};
23
24/// For each function parameter (and the return type), look up the type's
25/// invariants from `std-type-invariants.json` and create preconditions.
26pub(crate) fn build_type_invariants_from_params<'tcx>(
27    tcx: TyCtxt<'tcx>,
28    def_id: DefId,
29) -> Vec<Property<'tcx>> {
30    let db = crate::contract::json::get_std_type_invariants();
31    if db.is_empty() {
32        return Vec::new();
33    }
34
35    let fn_sig = tcx.fn_sig(def_id).skip_binder();
36    let inputs = fn_sig.inputs().skip_binder();
37    let output = fn_sig.output().skip_binder();
38
39    let mut results = Vec::new();
40
41    let (param_names, _param_tys) = crate::util::name::parse_signature(tcx, def_id);
42
43    for (index, &param_ty) in inputs.iter().enumerate() {
44        if param_ty.is_primitive() {
45            continue;
46        }
47        let param_name = param_names.get(index).cloned().unwrap_or_default();
48        let (type_path, elem_ty) = type_path_key(tcx, param_ty);
49        collect_type_invariants(
50            tcx,
51            def_id,
52            db,
53            &type_path,
54            &param_name,
55            elem_ty,
56            &mut results,
57        );
58    }
59
60    results.extend(build_type_invariants_for_ty(tcx, def_id, output));
61
62    results
63}
64
65pub(crate) fn build_type_invariants_for_ty<'tcx>(
66    tcx: TyCtxt<'tcx>,
67    def_id: DefId,
68    ty: Ty<'tcx>,
69) -> Vec<Property<'tcx>> {
70    if ty.is_unit() || ty.is_primitive() {
71        return Vec::new();
72    }
73    let db = crate::contract::json::get_std_type_invariants();
74    let (type_path, elem_ty) = type_path_key(tcx, ty);
75    let mut results = Vec::new();
76    collect_type_invariants(tcx, def_id, db, &type_path, "return", elem_ty, &mut results);
77    results
78}
79
80pub(crate) fn has_json_type_invariants<'tcx>(tcx: TyCtxt<'tcx>, ty: Ty<'tcx>) -> bool {
81    let db = crate::contract::json::get_std_type_invariants();
82    let (key, _) = type_path_key(tcx, ty);
83    db.contains_key(&key)
84        || ["alloc::", "std::"]
85            .iter()
86            .any(|prefix| db.contains_key(&format!("{prefix}{key}")))
87}
88
89/// Whether a constructor directly returns its owning ADT with a declared invariant.
90pub(crate) fn constructor_result_has_invariant(tcx: TyCtxt<'_>, callee: DefId) -> bool {
91    let Some(owner) = fn_info::get_adt_def_id_by_adt_method(tcx, callee) else {
92        return false;
93    };
94    let output = tcx.fn_sig(callee).skip_binder().output().skip_binder();
95    Some(owner) == output.ty_adt_def().map(|adt| adt.did())
96        && (crate::contract::annotation::has_rapx_struct_invariant(tcx, owner)
97            || has_json_type_invariants(tcx, output))
98}
99
100/// Whether the container's pointer field has an `Allocated` or `Owning` invariant.
101pub(crate) fn has_owner_ptr_invariant<'tcx>(tcx: TyCtxt<'tcx>, ty: Ty<'tcx>, path: &[usize], kind: PropertyKind) -> bool {
102    let ty::Adt(adt, _) = ty.kind() else {
103        return false;
104    };
105    let invariants = crate::contract::annotation::get_struct_invariants_from_annotation(tcx, adt.did(), adt.did());
106    let annotated = invariants.iter().any(|property| {
107        property.kind() == Some(kind)
108            && (kind != PropertyKind::Allocated
109                || property.args().get(2).is_none_or(|arg| {
110                    matches!(arg.expr(), Some(ContractExpr::Const(count)) if *count > 0)
111                }))
112            && property.target_place().is_some_and(|place| {
113                place.projections.iter().map(|projection| match projection {
114                    ContractProjection::Field { index } => Some(*index),
115                    _ => None,
116                }).collect::<Option<Vec<_>>>().as_deref() == Some(path)
117            })
118    });
119    if annotated {
120        return true;
121    }
122    let tag = match kind {
123        PropertyKind::Allocated => "Allocated",
124        PropertyKind::Owning => "Owning",
125        _ => return false,
126    };
127    let key = crate::util::name::public_def_path(tcx, adt.did());
128    let Some(entries) = crate::contract::json::get_std_type_invariants().get(&key) else {
129        return false;
130    };
131    entries.iter().any(|entry| {
132        entry.tag == tag
133            && (kind != PropertyKind::Allocated
134                || entry.args.get(2).is_none_or(|count| count.parse::<u128>().is_ok_and(|count| count > 0)))
135            && entry.args.first().and_then(|arg| {
136                let mut field_ty = ty;
137                arg.strip_prefix("$self.")?.split('.').map(|name| {
138                    let ty::Adt(adt, substs) = field_ty.kind() else {
139                        return None;
140                    };
141                    if adt.is_enum() {
142                        return None;
143                    }
144                    let field = adt.non_enum_variant().fields.iter().enumerate().find(|(index, field)| {
145                        name.parse::<usize>().ok() == Some(*index) || field.name.as_str() == name
146                    })?;
147                    field_ty = mir_utils::field_ty(tcx, field.1, substs);
148                    Some(field.0)
149                }).collect::<Option<Vec<_>>>()
150            }).as_deref() == Some(path)
151    })
152}
153
154/// Look up the type path in the DB and add instantiated invariants to `results`.
155fn collect_type_invariants<'tcx>(
156    tcx: TyCtxt<'tcx>,
157    def_id: DefId,
158    db: &std::collections::HashMap<String, Vec<crate::contract::json::JsonProperty>>,
159    type_path: &str,
160    param_name: &str,
161    elem_ty: Option<Ty<'tcx>>,
162    results: &mut Vec<Property<'tcx>>,
163) {
164    let zst_vec = matches!(type_path, "alloc::vec::Vec" | "std::vec::Vec" | "vec::Vec")
165        && elem_ty
166            .and_then(|ty| mir_utils::layout_of_ty(tcx, def_id, ty))
167            .is_some_and(|layout| layout.size.bytes() == 0);
168    if let Some(entries) = db.get(type_path) {
169        for prop_entry in entries {
170            if zst_vec && is_vec_capacity_bound(prop_entry) {
171                continue;
172            }
173            results.extend(instantiate_type_invariant(
174                tcx, def_id, prop_entry, param_name, elem_ty,
175            ));
176        }
177    }
178    for prefix in ["alloc::", "std::"] {
179        let prefixed = format!("{prefix}{type_path}");
180        if prefixed != type_path
181            && let Some(entries) = db.get(&prefixed)
182        {
183            for prop_entry in entries {
184                if zst_vec && is_vec_capacity_bound(prop_entry) {
185                    continue;
186                }
187                results.extend(instantiate_type_invariant(
188                    tcx, def_id, prop_entry, param_name, elem_ty,
189                ));
190            }
191        }
192    }
193}
194
195fn is_vec_capacity_bound(entry: &crate::contract::json::JsonProperty) -> bool {
196    entry.tag == "ValidNum"
197        && entry.args == ["$self.len <= $self.buf.inner.cap.0"]
198}
199
200/// Create properties from a type invariant entry, substituting the parameter
201/// name (and, for the slice entry, the element type). An entry with an `any`
202/// field expands to a single disjunctive `Property::Or`; otherwise it yields
203/// the properties denoted by its tag.
204fn instantiate_type_invariant<'tcx>(
205    tcx: TyCtxt<'tcx>,
206    def_id: DefId,
207    entry: &crate::contract::json::JsonProperty,
208    param_name: &str,
209    elem_ty: Option<Ty<'tcx>>,
210) -> Vec<Property<'tcx>> {
211    if let Some(disjuncts) = &entry.any {
212        if disjuncts.len() < 2 {
213            return Vec::new();
214        }
215        let mut or_disjuncts: Vec<Property<'tcx>> = Vec::with_capacity(disjuncts.len());
216        for item in disjuncts {
217            let mut group: Vec<Property<'tcx>> = Vec::new();
218            match item {
219                AnyItem::Single(e) => {
220                    group.extend(instantiate_entry(tcx, def_id, e, param_name, elem_ty))
221                }
222                AnyItem::And(es) => {
223                    for e in es {
224                        group.extend(instantiate_entry(tcx, def_id, e, param_name, elem_ty));
225                    }
226                }
227            }
228            if !group.is_empty() {
229                or_disjuncts.push(Property::conjunction(group));
230            }
231        }
232        let mut property = Property::new_or(or_disjuncts);
233        property.apply_kind(entry.kind.as_deref());
234        return vec![property];
235    }
236    instantiate_entry(tcx, def_id, entry, param_name, elem_ty)
237}
238
239/// Placeholder type name substituted for the `$elem` token before parsing. The
240/// JSON `$elem` is a bare type argument (e.g. `Align($self, $elem)`), and the
241/// real element type — which can be a composite like `[T; N]` that has no
242/// resolvable name — is injected afterwards by [`replace_ty_args`]. Any
243/// primitive placeholder resolves cleanly through the name-based type parser.
244const SLICE_ELEM_PLACEHOLDER: &str = "u8";
245
246/// Instantiate a single (non-`any`) type invariant entry.
247fn instantiate_entry<'tcx>(
248    tcx: TyCtxt<'tcx>,
249    def_id: DefId,
250    entry: &crate::contract::json::JsonProperty,
251    param_name: &str,
252    elem_ty: Option<Ty<'tcx>>,
253) -> Vec<Property<'tcx>> {
254    let mut uses_elem = false;
255    let mut exprs: Vec<syn::Expr> = Vec::new();
256    for arg_str in &entry.args {
257        // Substitute the `$self` placeholder with the actual parameter name
258        // (or "return"). `$elem` is a type argument: substitute a resolvable
259        // placeholder and inject the real element type after parsing.
260        let mut substituted = arg_str.replace("$self", param_name);
261        if substituted.contains("$elem") {
262            uses_elem = true;
263            substituted = substituted.replace("$elem", SLICE_ELEM_PLACEHOLDER);
264        }
265        match syn::parse_str::<syn::Expr>(&substituted) {
266            Ok(expr) => exprs.push(expr),
267            Err(_) => {
268                rap_debug!(
269                    "  [type-invariant] failed to parse arg '{}' for tag {}",
270                    substituted,
271                    entry.tag
272                );
273                return Vec::new();
274            }
275        }
276    }
277    if exprs.is_empty() {
278        return Vec::new();
279    }
280    let mut property = Property::new(tcx, def_id, &entry.tag, &exprs);
281    property.apply_kind(entry.kind.as_deref());
282    if matches!(property.kind(), Some(PropertyKind::Unknown)) {
283        return Vec::new();
284    }
285    if uses_elem {
286        let Some(ty) = elem_ty else {
287            return Vec::new();
288        };
289        replace_ty_args(&mut property, ty);
290    }
291    resolve_pointer_wrapper_target(tcx, def_id, &mut property);
292    vec![property]
293}
294
295fn resolve_pointer_wrapper_target<'tcx>(tcx: TyCtxt<'tcx>, def_id: DefId, property: &mut Property<'tcx>) {
296    let Property::Atom(atom) = property else { return };
297    let Some(PropertyArg::Expr(ContractExpr::Place(place)) | PropertyArg::ForEach(ContractExpr::Place(place))) = atom.args.first_mut() else {
298        return;
299    };
300    if !matches!(place.projections.last(), Some(ContractProjection::Field { .. })) {
301        return;
302    }
303    let Some(ty) = contract_place_ty(tcx, def_id, place) else { return };
304    let Some(fields) = transparent_nonnull_path(tcx, ty, 5) else { return };
305    place.projections.extend(fields.into_iter().map(|index| ContractProjection::Field { index }));
306}
307
308fn contract_place_ty<'tcx>(tcx: TyCtxt<'tcx>, def_id: DefId, place: &ContractPlace) -> Option<Ty<'tcx>> {
309    let sig = tcx.fn_sig(def_id).skip_binder();
310    let inputs = sig.inputs().skip_binder();
311    let ty = match place.base {
312        PlaceBase::Return | PlaceBase::Local(0) => sig.output().skip_binder(),
313        PlaceBase::Arg(index) => *inputs.get(index)?,
314        PlaceBase::Local(index) => *inputs.get(index.checked_sub(1)?)?,
315    };
316    mir_utils::projected_field_ty(tcx, ty, &place.plain_field_path()?)
317}
318
319fn transparent_nonnull_path<'tcx>(
320    tcx: TyCtxt<'tcx>,
321    ty: Ty<'tcx>,
322    depth: usize,
323) -> Option<Vec<usize>> {
324    let ty::Adt(adt, args) = ty.kind() else { return None };
325    if type_ids::is_std_nonnull(adt.did()) {
326        return Some(Vec::new());
327    }
328    if depth == 0 || !adt.is_struct() || !adt.repr().transparent() {
329        return None;
330    }
331    let mut path = None;
332    for (index, field) in adt.non_enum_variant().fields.iter().enumerate() {
333        let field_ty = crate::util::mir_utils::field_ty(tcx, field, args);
334        let Some(mut suffix) = transparent_nonnull_path(tcx, field_ty, depth - 1) else {
335            continue;
336        };
337        if path.is_some() {
338            return None;
339        }
340        suffix.insert(0, index);
341        path = Some(suffix);
342    }
343    path
344}
345
346/// Replace every type argument in a property tree with the slice element type.
347///
348/// The slice invariant's only type arguments are the `$elem` placeholders, so
349/// this recovers the concrete element type (including composites such as
350/// `[T; N]`) that the name-based JSON type parser cannot express. It also
351/// reaches `size_of`/`align_of` type arguments inside `ValidNum` predicates.
352fn replace_ty_args<'tcx>(property: &mut Property<'tcx>, ty: Ty<'tcx>) {
353    match property {
354        Property::Atom(atom) => {
355            for arg in &mut atom.args {
356                match arg {
357                    PropertyArg::Ty(t) => *t = ty,
358                    PropertyArg::Predicates(preds) => {
359                        for pred in preds {
360                            replace_pred_ty(pred, ty);
361                        }
362                    }
363                    _ => {}
364                }
365            }
366        }
367        Property::And(and) => {
368            for conjunct in &mut and.conjuncts {
369                replace_ty_args(conjunct, ty);
370            }
371        }
372        Property::Or(or) => {
373            for disjunct in &mut or.disjuncts {
374                replace_ty_args(disjunct, ty);
375            }
376        }
377    }
378}
379
380/// Replace `size_of`/`align_of` type arguments inside a numeric predicate.
381fn replace_pred_ty<'tcx>(pred: &mut NumericPredicate<'tcx>, ty: Ty<'tcx>) {
382    replace_expr_ty(&mut pred.lhs, ty);
383    replace_expr_ty(&mut pred.rhs, ty);
384}
385
386/// Replace `size_of`/`align_of` type arguments inside a contract expression.
387fn replace_expr_ty<'tcx>(expr: &mut ContractExpr<'tcx>, ty: Ty<'tcx>) {
388    match expr {
389        ContractExpr::SizeOf(t) | ContractExpr::AlignOf(t) => *t = ty,
390        ContractExpr::Len(inner, _) | ContractExpr::IsEmpty(inner, _) => replace_expr_ty(inner, ty),
391        ContractExpr::IndexAccess { slice, index } => {
392            replace_expr_ty(slice, ty);
393            replace_expr_ty(index, ty);
394        }
395        ContractExpr::Binary { lhs, rhs, .. } => {
396            replace_expr_ty(lhs, ty);
397            replace_expr_ty(rhs, ty);
398        }
399        ContractExpr::Unary { expr: inner, .. } => replace_expr_ty(inner, ty),
400        ContractExpr::If {
401            cond,
402            then_expr,
403            else_expr,
404        } => {
405            replace_pred_ty(cond, ty);
406            replace_expr_ty(then_expr, ty);
407            replace_expr_ty(else_expr, ty);
408        }
409        _ => {}
410    }
411}
412
413/// Generate a normalised type path key for lookups in the type-invariants DB,
414/// together with the element type for the built-in slice entry.
415///
416/// ADTs and mutable references to ADTs map to the ADT's def path (e.g.
417/// `core::num::NonZero`). Slice references map to the built-in `[T]` key and
418/// carry their element type; anything else falls back to the type's `Debug`
419/// representation.
420fn type_path_key<'tcx>(tcx: TyCtxt<'tcx>, ty: Ty<'tcx>) -> (String, Option<Ty<'tcx>>) {
421    match ty.kind() {
422        rustc_middle::ty::TyKind::Adt(adt_def, substs) => {
423            let key = crate::util::name::public_def_path(tcx, adt_def.did());
424            // The first type argument is the element type for containers
425            // (`Vec<T>`/`String`); `$elem` in a container invariant resolves to
426            // it (unused by non-container entries like `NonNull`).
427            let elem_ty = substs.first().and_then(|s| s.as_type());
428            (key, elem_ty)
429        }
430        rustc_middle::ty::TyKind::Ref(_, inner, mutability) => match inner.kind() {
431            rustc_middle::ty::TyKind::Slice(elem) => ("[T]".to_string(), Some(*elem)),
432            rustc_middle::ty::TyKind::Adt(..)
433                if *mutability == rustc_middle::ty::Mutability::Mut =>
434            {
435                type_path_key(tcx, *inner)
436            }
437            rustc_middle::ty::TyKind::Adt(adt, _)
438                if crate::util::name::public_def_path(tcx, adt.did()) == "core::ffi::CStr" =>
439            {
440                ("core::ffi::CStr".to_string(), None)
441            }
442            _ => (format!("{ty:?}"), None),
443        },
444        _ => (format!("{ty:?}"), None),
445    }
446}