Skip to main content

rapx/
contract.rs

1//! Contract IR and type invariants.
2//!
3//! Inline attributes, embedded JSON, and `pred!`-style compound properties
4//! produce the contract IR defined here. Attribute and JSON arguments are parsed
5//! as `syn` expressions; compound bodies use the pest grammar.
6//!
7//! `type_invariants` synthesizes properties for known types.
8//!
9//! ## Layering
10//!
11//! Contracts go through two stages, each with its own type:
12//!
13//! ```text
14//! attribute ──▶ AttrProperty ─┐
15//! JSON ───────▶ JsonProperty ─┴──▶ builder.rs ──▶ Property (Atom | And | Or)
16//! pred! ──────▶ CompoundSpec ─────▶ compound.rs ─▶ Property
17//! ```
18//!
19//! `Property::parse_list` dispatches compound tags to `compound::expand_compound`;
20//! their `CompoundSpec` bypasses the primitive property builder.
21//!
22//! Within the resolved IR, the naming follows granularity rather than stage:
23//! `Property*` names the formula level (`Property`, `PropertyKind`,
24//! `PropertyArg`), while `Contract*` names the expression sub-language used by
25//! `PropertyArg::Expr` and `PropertyArg::ForEach` (`ContractPlace`, `ContractExpr`,
26//! `ContractProjection`).
27
28pub(crate) mod annotation;
29pub(crate) mod attr;
30pub(crate) mod builder;
31pub(crate) mod compound;
32pub(crate) mod ensures;
33pub(crate) mod json;
34pub(crate) mod pest;
35pub(crate) mod place;
36pub(crate) mod render;
37pub(crate) mod resolve;
38pub(crate) mod spec;
39pub(crate) mod type_invariants;
40
41use rustc_hir::def_id::DefId;
42use rustc_middle::{mir::Local, ty::{Region, Ty}};
43
44/// The `Ident` a contract uses for the `'static` lifetime. `'static` is a Rust
45/// keyword, so after the leading `'` is stripped it cannot be a plain ident
46/// token; the attribute and JSON parsers map it to this name.
47pub(crate) const STATIC_LIFETIME_IDENT: &str = "static_lifetime";
48
49/// Whether a contract lifetime ident is the keyword-safe `'static` placeholder.
50pub(crate) fn is_static_lifetime_ident(name: &str) -> bool {
51    name == STATIC_LIFETIME_IDENT
52}
53
54/// The root of a contract place: a function's return value, an argument, or a
55/// raw MIR local.  `Return` ⇔ `Local(0)`; `Arg(n)` ⇔ `Local(n + 1)`.
56#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
57pub(crate) enum PlaceBase {
58    /// The function's return value.
59    Return,
60    /// The n-th parameter (0-indexed).
61    Arg(usize),
62    /// A MIR local (`0` is the return place, `1..` are the parameters).
63    Local(usize),
64}
65
66impl PlaceBase {
67    /// The MIR local this base denotes (`Return` ⇔ `Local(0)`, `Arg(n)` ⇔ `Local(n + 1)`).
68    pub(crate) fn to_local(&self) -> Local {
69        match self {
70            PlaceBase::Return => Local::from_usize(0),
71            PlaceBase::Arg(n) => Local::from_usize(*n + 1),
72            PlaceBase::Local(n) => Local::from_usize(*n),
73        }
74    }
75}
76
77/// A step into a place, from the base down to the value a contract talks
78/// about (written as `.field`, `.unwrap_some()`, or `.iter()` in the DSL).
79#[derive(Clone, Debug, PartialEq, Eq, Hash)]
80pub(crate) enum ContractProjection {
81    /// Select a struct/tuple field by index; its type is derived when needed.
82    Field { index: usize },
83    /// Unwrap the `Some` variant of an enum.
84    Downcast { variant_index: usize },
85    /// Treat `iter()` or `each_element()` syntax as a per-element projection.
86    ForEach,
87}
88
89/// A place a contract refers to: a [`PlaceBase`] root plus a sequence of
90/// [`ContractProjection`] steps into it (e.g. `self.next.value`).
91#[derive(Clone, Debug, PartialEq, Eq, Hash)]
92pub(crate) struct ContractPlace {
93    /// The root: return value, an argument, or a MIR local.
94    pub base: PlaceBase,
95    /// Field / `Some`-unwrap / element steps from the base down.
96    pub projections: Vec<ContractProjection>,
97}
98
99impl ContractPlace {
100    pub(crate) fn local(base: usize, fields: Vec<usize>) -> Self {
101        Self {
102            base: if base == 0 { PlaceBase::Return } else { PlaceBase::Local(base) },
103            projections: fields.into_iter().map(|index| ContractProjection::Field { index }).collect(),
104        }
105    }
106
107    pub(crate) fn arg(index: usize) -> Self {
108        Self {
109            base: PlaceBase::Arg(index),
110            projections: Vec::new(),
111        }
112    }
113
114    pub(crate) fn local_base(&self) -> Option<usize> {
115        match self.base {
116            PlaceBase::Return => Some(0),
117            PlaceBase::Local(local) => Some(local),
118            PlaceBase::Arg(_) => None,
119        }
120    }
121
122    /// The field indices when this place is a pure `Field` chain (no `Downcast`
123    /// / `ForEach` steps), otherwise `None`.  Shared by the exec- and
124    /// checker-side `Len` evaluators.
125    pub(crate) fn plain_field_path(&self) -> Option<Vec<usize>> {
126        let mut path = Vec::new();
127        for proj in &self.projections {
128            match proj {
129                ContractProjection::Field { index } => path.push(*index),
130                _ => return None,
131            }
132        }
133        Some(path)
134    }
135}
136
137#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
138pub(crate) enum BinOp {
139    Add,
140    Sub,
141    Mul,
142    Div,
143    Rem,
144    Min,
145    Max,
146    BitAnd,
147    BitOr,
148    BitXor,
149}
150
151#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
152pub(crate) enum UnaryOp {
153    Not,
154    Neg,
155}
156
157#[derive(Clone, Debug, PartialEq, Eq, Hash)]
158pub(crate) enum ContractExpr<'tcx> {
159    Place(ContractPlace),
160    Const(u128),
161    ConstParam { index: u32, name: String },
162    SizeOf(Ty<'tcx>),
163    AlignOf(Ty<'tcx>),
164    Len(Box<ContractExpr<'tcx>>, Option<DefId>),
165    MethodCall { receiver: Box<ContractExpr<'tcx>>, method: DefId, args: Vec<ContractExpr<'tcx>> },
166    IsEmpty(Box<ContractExpr<'tcx>>, Option<DefId>),
167    IndexAccess { slice: Box<ContractExpr<'tcx>>, index: Box<ContractExpr<'tcx>> },
168    Binary { op: BinOp, lhs: Box<ContractExpr<'tcx>>, rhs: Box<ContractExpr<'tcx>> },
169    Unary { op: UnaryOp, expr: Box<ContractExpr<'tcx>> },
170    If { cond: Box<NumericPredicate<'tcx>>, then_expr: Box<ContractExpr<'tcx>>, else_expr: Box<ContractExpr<'tcx>> },
171    Unknown,
172}
173
174#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
175pub(crate) enum RelOp {
176    Eq,
177    Ne,
178    Lt,
179    Le,
180    Gt,
181    Ge,
182}
183
184#[derive(Clone, Debug, PartialEq, Eq, Hash)]
185pub(crate) struct NumericPredicate<'tcx> {
186    pub lhs: ContractExpr<'tcx>,
187    pub op: RelOp,
188    pub rhs: ContractExpr<'tcx>,
189}
190
191impl<'tcx> NumericPredicate<'tcx> {
192    pub(crate) fn new(lhs: ContractExpr<'tcx>, op: RelOp, rhs: ContractExpr<'tcx>) -> Self {
193        Self { lhs, op, rhs }
194    }
195}
196
197/// The vocabulary of safety predicates a contract can assert.
198///
199/// Each kind's meaning and accepted argument shapes are declared in
200/// `spec::SPECS` (the single source of truth); this enum only names the kinds.
201/// A few kinds carry extra semantics: `Null` is the guard branch of
202/// `any(Null(p), …)` (proved when `p` is null), and `Owning` asserts
203/// `ownership(*p) = none` (psp IV.1 in primitive-sp.md).  The kinds `Unwrap`,
204/// `Pinned`, `Opened` and `Unreachable` are declared but not yet verified (the
205/// checker returns `Unknown`), and `NonVolatile` is assumed satisfied (the VM
206/// does not model volatile access).
207#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
208pub(crate) enum PropertyKind {
209    Align,
210    Size,
211    NoPadding,
212    NonNull,
213    Allocated,
214    InBound,
215    SliceOffset,
216    NonOverlap,
217    ValidNum,
218    ValidString,
219    ValidCStr,
220    Init,
221    Unwrap,
222    Typed,
223    Owning,
224    RefCountShare,
225    Alias,
226    Alive,
227    Pinned,
228    NonVolatile,
229    Opened,
230    Null,
231    Trait,
232    Unreachable,
233    ValidTransmute,
234    SplitTransmute,
235    ContainNoType,
236    NoRawPtr,
237    NoInternalMut,
238    UniInternalMut,
239    AtomicUpdate,
240    RefSend,
241    Unknown,
242}
243
244/// One argument of a predicate call — what the property is applied to.
245#[derive(Clone, Debug, PartialEq, Eq, Hash)]
246pub(crate) enum PropertyArg<'tcx> {
247    /// A type (e.g. `T` in `Align(ptr, T)`).
248    Ty(Ty<'tcx>),
249    /// A value expression (e.g. `buf`, `n`).
250    Expr(ContractExpr<'tcx>),
251    /// An expression checked for each element of its container.
252    ForEach(ContractExpr<'tcx>),
253    /// Numeric comparisons used by `ValidNum`.
254    Predicates(Vec<NumericPredicate<'tcx>>),
255    /// A name: lifetime, allocator, trait (e.g. `Copy`), or `sized`/`unsized`.
256    Ident(String),
257    /// Resolved lifetime region (e.g. `'a` in `Alive(p, 'a)`).
258    Region(Region<'tcx>),
259}
260
261impl<'tcx> PropertyArg<'tcx> {
262    pub(crate) fn expr(&self) -> Option<&ContractExpr<'tcx>> {
263        match self {
264            Self::Expr(expr) | Self::ForEach(expr) => Some(expr),
265            _ => None,
266        }
267    }
268}
269
270#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
271pub(crate) enum ContractKind {
272    Precond,
273    Hazard,
274    Option_,
275    Postcond,
276}
277
278/// Display metadata for a property expanded from a compound property
279/// (`pred!`-style macro).  Purely presentational: it lets reports render a
280/// macro-expanded contract as a single `name(args)` entry with its doc-derived
281/// meaning, instead of the underlying primitives it expanded into.
282#[derive(Clone, Debug, PartialEq, Eq, Hash)]
283pub(crate) struct ContractOrigin {
284    pub name: String,
285    pub args: Vec<String>,
286    pub meaning: Option<String>,
287}
288
289/// A safety property: a boolean formula over atomic predicates.
290///
291/// The formula is a tree of three node kinds — `Atom` (a single predicate),
292/// `And` (conjunction: all members hold), and `Or` (disjunction: at least one
293/// member holds). Vectors provide the indirection; the top-level `Vec<Property>`
294/// is an implicit conjunction of requirements.
295#[derive(Clone, Debug, PartialEq, Eq, Hash)]
296pub(crate) enum Property<'tcx> {
297    Atom(AtomProperty<'tcx>),
298    And(AndProperty<'tcx>),
299    Or(OrProperty<'tcx>),
300}
301
302#[derive(Clone, Debug, PartialEq, Eq, Hash)]
303pub(crate) struct AtomProperty<'tcx> {
304    pub kind: PropertyKind,
305    pub args: Vec<PropertyArg<'tcx>>,
306    pub contract_kind: ContractKind,
307    /// Display metadata when this property was expanded from a compound property.
308    pub origin: Option<ContractOrigin>,
309}
310
311/// A conjunction: every [`conjuncts`](Self::conjuncts) member must hold.
312#[derive(Clone, Debug, PartialEq, Eq, Hash)]
313pub(crate) struct AndProperty<'tcx> {
314    pub conjuncts: Vec<Property<'tcx>>,
315    /// Display metadata when this property was expanded from a compound property.
316    pub origin: Option<ContractOrigin>,
317}
318
319/// A disjunction: at least one [`disjuncts`](Self::disjuncts) member must hold.
320#[derive(Clone, Debug, PartialEq, Eq, Hash)]
321pub(crate) struct OrProperty<'tcx> {
322    pub disjuncts: Vec<Property<'tcx>>,
323    /// Display metadata when this property was expanded from a compound property.
324    pub origin: Option<ContractOrigin>,
325}
326
327impl<'tcx> Property<'tcx> {
328    /// Build a single atomic predicate.
329    pub(crate) fn new_atom(kind: PropertyKind, args: Vec<PropertyArg<'tcx>>) -> Self {
330        Self::Atom(AtomProperty {
331            kind,
332            args,
333            contract_kind: ContractKind::Precond,
334            origin: None,
335        })
336    }
337
338    /// Build a conjunction (`And`) of already-expanded conjuncts.
339    pub(crate) fn new_and(conjuncts: Vec<Property<'tcx>>) -> Self {
340        Self::And(AndProperty { conjuncts, origin: None })
341    }
342
343    /// Build a disjunction (`Or`) of already-expanded disjuncts.
344    pub(crate) fn new_or(disjuncts: Vec<Property<'tcx>>) -> Self {
345        Self::Or(OrProperty { disjuncts, origin: None })
346    }
347
348    /// Normalize a list of conjuncts into a single `Property`: a singleton is
349    /// returned as-is, otherwise the list is wrapped in an `And` node.
350    pub(crate) fn conjunction(conjuncts: Vec<Property<'tcx>>) -> Self {
351        if conjuncts.len() == 1 {
352            conjuncts.into_iter().next().unwrap()
353        } else {
354            Self::new_and(conjuncts)
355        }
356    }
357
358    /// The predicate kind of an atom (`None` for `And`/`Or`, which have no
359    /// single kind).
360    pub(crate) fn kind(&self) -> Option<PropertyKind> {
361        match self {
362            Property::Atom(a) => Some(a.kind),
363            Property::And(_) | Property::Or(_) => None,
364        }
365    }
366
367    /// The positional arguments of an atom (`And`/`Or` have none).
368    pub(crate) fn args(&self) -> &[PropertyArg<'tcx>] {
369        match self {
370            Property::Atom(a) => &a.args,
371            Property::And(_) | Property::Or(_) => &[],
372        }
373    }
374
375    pub(crate) fn try_type_arg_at(&self, index: usize) -> Option<Ty<'tcx>> {
376        match self.args().get(index) {
377            Some(PropertyArg::Ty(ty)) => Some(*ty),
378            _ => None,
379        }
380    }
381
382    /// The `ContractPlace` this atom's first argument refers to, when the
383    /// first argument is a place (or an index access over one, e.g. `slice[i]`).
384    pub(crate) fn target_place(&self) -> Option<&ContractPlace> {
385        match self.args().first()?.expr()? {
386            ContractExpr::Place(cp) => Some(cp),
387            ContractExpr::IndexAccess { slice, .. } => match slice.as_ref() {
388                ContractExpr::Place(cp) => Some(cp),
389                _ => None,
390            },
391            _ => None,
392        }
393    }
394
395    /// The conjuncts of an `And` property (`Atom`/`Or` have none).
396    pub(crate) fn conjuncts(&self) -> &[Property<'tcx>] {
397        match self {
398            Property::And(a) => &a.conjuncts,
399            Property::Atom(_) | Property::Or(_) => &[],
400        }
401    }
402
403    /// The disjuncts of an `Or` property (`Atom`/`And` have none).
404    pub(crate) fn disjuncts(&self) -> &[Property<'tcx>] {
405        match self {
406            Property::Or(o) => &o.disjuncts,
407            Property::Atom(_) | Property::And(_) => &[],
408        }
409    }
410
411    pub(crate) fn contract_kind(&self) -> ContractKind {
412        match self {
413            Property::Atom(a) => a.contract_kind,
414            Property::And(and) => Self::shared_contract_kind(&and.conjuncts),
415            Property::Or(or) => Self::shared_contract_kind(&or.disjuncts),
416        }
417    }
418
419    fn shared_contract_kind(children: &[Property<'tcx>]) -> ContractKind {
420        let mut kinds = children.iter().map(Property::contract_kind);
421        let Some(first) = kinds.next() else { return ContractKind::Precond };
422        if kinds.all(|kind| kind == first) { first } else { ContractKind::Precond }
423    }
424
425    /// Defer `ContractKind::Hazard` properties to the use point. A hazard
426    /// (e.g. `Alias`) marks exclusive ownership in a struct invariant, but
427    /// is not a standing fact: it is enforced at the operation that consumes the
428    /// pointer (whose `requires` names it), not verified at construction nor
429    /// carried as an entry fact (where `assert_contract_fact` would treat
430    /// `Alias` as an *accepted* structural-alias hazard via `alias_hazard_allocs`).
431    pub(crate) fn strip_hazards(&self) -> Option<Property<'tcx>> {
432        match self {
433            Property::Atom(atom) if atom.contract_kind == ContractKind::Hazard => None,
434            Property::Atom(_) => Some(self.clone()),
435            Property::And(and) => {
436                let conjuncts: Vec<Property<'tcx>> = and.conjuncts.iter().filter_map(Property::strip_hazards).collect();
437                match conjuncts.len() {
438                    0 => None,
439                    1 => conjuncts.into_iter().next(),
440                    _ => {
441                        let mut stripped = and.clone();
442                        stripped.conjuncts = conjuncts;
443                        Some(Property::And(stripped))
444                    }
445                }
446            }
447            Property::Or(or) => {
448                // A removed disjunct is vacuously true, so the whole OR gives
449                // no usable entry fact.
450                let disjuncts: Vec<Property<'tcx>> = or.disjuncts.iter().map(Property::strip_hazards).collect::<Option<_>>()?;
451                match disjuncts.len() {
452                    0 => None,
453                    1 => disjuncts.into_iter().next(),
454                    _ => {
455                        let mut stripped = or.clone();
456                        stripped.disjuncts = disjuncts;
457                        Some(Property::Or(stripped))
458                    }
459                }
460            }
461        }
462    }
463
464    pub(crate) fn for_each(&self) -> Option<&PlaceBase> {
465        match self {
466            Property::Atom(a) => a.args.iter().find_map(|arg| match arg {
467                PropertyArg::ForEach(ContractExpr::Place(place)) => Some(&place.base),
468                PropertyArg::ForEach(ContractExpr::IndexAccess { index, .. }) => match index.as_ref() {
469                    ContractExpr::Place(place) => Some(&place.base),
470                    _ => None,
471                },
472                _ => None,
473            }),
474            Property::And(_) | Property::Or(_) => None,
475        }
476    }
477
478    /// Display metadata when this property was expanded from a compound property.
479    pub(crate) fn origin(&self) -> Option<&ContractOrigin> {
480        match self {
481            Property::Atom(atom) => atom.origin.as_ref(),
482            Property::And(and) => and.origin.as_ref(),
483            Property::Or(or) => or.origin.as_ref(),
484        }
485    }
486
487    /// Apply contract kind metadata from a JSON entry or attribute.
488    pub(crate) fn apply_kind(&mut self, kind: Option<&str>) {
489        match kind {
490            Some("hazard") => self.set_contract_kind(ContractKind::Hazard),
491            Some("option") => self.set_contract_kind(ContractKind::Option_),
492            Some("postcond") => self.set_contract_kind(ContractKind::Postcond),
493            _ => {}
494        }
495    }
496
497    /// Tag a property (atom, `And`, or `Or`) with the display name, full
498    /// call-site arguments, and meaning of the compound property it expanded from.
499    pub(crate) fn set_origin(&mut self, name: String, args: Vec<String>, meaning: Option<String>) {
500        let origin = ContractOrigin { name, args, meaning };
501        match self {
502            Property::Atom(a) => a.origin = Some(origin),
503            Property::And(a) => a.origin = Some(origin),
504            Property::Or(o) => o.origin = Some(origin),
505        }
506    }
507
508    /// Remove the compound-origin display metadata from this property.
509    pub(crate) fn clear_origin(&mut self) {
510        match self {
511            Property::Atom(a) => a.origin = None,
512            Property::And(a) => a.origin = None,
513            Property::Or(o) => o.origin = None,
514        }
515    }
516
517    /// Override the contract kind (e.g. `Alias` → `Hazard`).
518    pub(crate) fn set_contract_kind(&mut self, k: ContractKind) {
519        match self {
520            Property::Atom(a) => a.contract_kind = k,
521            Property::And(and) => and.conjuncts.iter_mut().for_each(|child| child.set_contract_kind(k)),
522            Property::Or(or) => or.disjuncts.iter_mut().for_each(|child| child.set_contract_kind(k)),
523        }
524    }
525}