Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Judgment prove_predicate

judgment_fn! {
    /// The "heart" of the trait system -- prove that a where-clause holds given a set of declarations, variable environment, and set of assumptions.
    /// If successful, returns the constraints under which the where-clause holds.
    pub fn prove_predicate(
        _decls: Program,
        env: Env,
        assumptions: Predicates,
        goal: Predicate,
    ) => Constraints {
        /* rules omitted */
    }
}

Source: crates/formality-rust/src/prove/prove_predicate.rs:23

The number on each rule’s conclusion is positive coverage; the number on each premise is negative coverage. Click a number to browse the tests.

forall
LineCoverageSource
354(scope(enter_universally_with_constraints(decls, env, assumptions, binder) => (env, p1)) with(c)
(prove_predicate(decls, env, assumptions, p1) => c))
──────── ("forall")
3826(prove_predicate(decls, env, assumptions, Predicate::ForAll(binder)) => c)
implies
LineCoverageSource
423(prove_predicate(decls, env, (assumptions, p1), p2) => c)
──────── ("implies")
444(prove_predicate(decls, env, assumptions, Predicate::Implies(p1, p2)) => c)
assumption
LineCoverageSource
48✗(a in assumptions)
4935(prove_via(decls, env, assumptions, a, goal) => c)
──────── ("assumption")
5135(prove_predicate(decls, env, assumptions, Predicate::AtomicPredicate(goal)) => c)
positive impl
LineCoverageSource
58✗(i in decls.impl_decls(&trait_ref.trait_id))
61✗(scope(enter_existentially_with_constraints(decls, env, assumptions, &i.binder) => (env, i)) with(c)
// Instantiate trait where-clauses from `Foo<?B>`. If we had `trait Foo<X: Debug>`, for example,
// this would yield `?B: Debug`.
(let t = decls.trait_decl(&i.trait_ref.trait_id).binder.instantiate_with(&i.trait_ref.parameters).unwrap())

// Create a set of assumptions `co_assumptions` that include the predicate the impl itself
// is asserting (i.e., `A: Foo<B>`). When proving the impl's where-clauses, we are allowed
// to assume this is true (in a coinductive fashion).
//
// NB: This is actually not what Rust currently does, but it is what "we" (types team) want it to do.
(let co_assumptions = (assumptions, trait_ref))
(prove(decls, env, co_assumptions, Predicates::all_eq(&trait_ref.parameters, &i.trait_ref.parameters)) => c)
(prove_after(decls, c, co_assumptions, &i.where_clause) => c)

// Prove that the well-formedness requirements of the *trait* hold -- for this proof, we cannot
// assume that the trait is implemented, because that would allow specious implied bounds
// (i.e., we could assume that `B: Debug` based on the trait definition + the existence of an impl,
// but actually the impl is responsible for proving that `B: Debug`).
(prove_after(decls, c, assumptions, &t.where_clause) => c))
──────── ("positive impl")
81337(prove_predicate(decls, env, assumptions, AtomicPredicate::IsImplemented(trait_ref)) => c)
coherence / remote impl
LineCoverageSource
85✗(if env.bias() == Bias::Completeness)
86✗(may_be_remote(decls, env, assumptions, trait_ref) => c)
──────── ("coherence / remote impl")
88✗(prove_predicate(decls, env, assumptions, AtomicPredicate::IsImplemented(trait_ref)) => c)
built-in Sized
LineCoverageSource
92✗(if trait_id.is_sized())
93✗(let (ty,) = parameters.downcast_err::<(Ty,)>()?)
949(prove_sized(decls, env, assumptions, ty) => c)
──────── ("built-in Sized")
9630(prove_predicate(decls, env, assumptions, AtomicPredicate::IsImplemented(TraitRef { trait_id, parameters })) => c)
negative impl
LineCoverageSource
1009(i in decls.neg_impl_decls(&trait_ref.trait_id))
101✗(scope(enter_existentially_with_constraints(decls, env, assumptions, &i.binder) => (env, i)) with(c)
(prove(decls, env, assumptions, Predicates::all_eq(&trait_ref.parameters, &i.trait_ref.parameters)) => c)
(prove_after(decls, c, assumptions, &i.where_clause) => c))
──────── ("negative impl")
1053(prove_predicate(decls, env, assumptions, AtomicPredicate::NotImplemented(trait_ref)) => c)
alias eq
LineCoverageSource
109✗(prove_eq(decls, env, assumptions, alias_ty, ty) => c)
──────── ("alias eq")
1111(prove_predicate(decls, env, assumptions, AtomicPredicate::AliasEq(alias_ty, ty)) => c)
trait implied bound
LineCoverageSource
11528(ti in decls.trait_invariants())
116✗(scope(enter_existentially_with_constraints(decls, env, assumptions, &ti.binder) => (env, ti)) with(c)
(prove_via(decls, env, assumptions, &ti.where_clause, trait_ref) => c)
(prove_after(decls, c, assumptions, &ti.trait_ref) => c))
──────── ("trait implied bound")
1201(prove_predicate(decls, env, assumptions, AtomicPredicate::IsImplemented(trait_ref)) => c)
eq
LineCoverageSource
12416(prove_eq(decls, env, assumptions, a, b) => c)
──────── ("eq")
126349(prove_predicate(decls, env, assumptions, AtomicPredicate::Equals(a, b)) => c)
subtype
LineCoverageSource
13020(prove_sub(decls, env, assumptions, a, b) => c)
──────── ("subtype")
132228(prove_predicate(decls, env, assumptions, AtomicPredicate::Sub(a, b)) => c)
trait well formed
LineCoverageSource
1361(for_all(decls, env, assumptions, &trait_ref.parameters, &prove_wf) => c)
137N/A(let t = decls.trait_decl(&trait_ref.trait_id))
138N/A(let t = t.binder.instantiate_with(&trait_ref.parameters).unwrap())
1392(prove_after(decls, c, assumptions, &t.where_clause) => c)
──────── ("trait well formed")
14149(prove_predicate(decls, env, assumptions, AtomicPredicate::WellFormedTraitRef(trait_ref)) => c)
trait ref is local
LineCoverageSource
14512(is_local_trait_ref(decls, env, assumptions, trait_ref) => c)
──────── ("trait ref is local")
147328(prove_predicate(decls, env, assumptions, AtomicPredicate::IsLocal(trait_ref)) => c)
outlives
LineCoverageSource
15110(prove_outlives(decls, env, assumptions, a, b) => c)
──────── ("outlives")
153321(prove_predicate(decls, env, assumptions, AtomicPredicate::Outlives(a, b)) => c)
parameter well formed
LineCoverageSource
1584(prove_wf(decls, env, assumptions, p) => c)
──────── ("parameter well formed")
160321(prove_predicate(decls, env, assumptions, AtomicPredicate::WellFormed(p)) => c)
const has ty
LineCoverageSource
1642(prove_const_has_type(decls, env, assumptions, constant) => (ty_constant, c))
1651(prove_after(decls, c, assumptions, AtomicPredicate::equals(ty_constant, ty)) => c)
──────── ("const has ty")
16711(prove_predicate(decls, env, assumptions, AtomicPredicate::ConstHasType(constant, ty)) => c)

How to read this page