use super::pass::room;
use super::zones::{Bag, Eigens, State, Zone, table_bytes};
use crate::hash::HashMap;
use crate::linear::occurrences::{Forest, Member};
use crate::linear::proofs::{Node, NodeId, Proof};
use crate::linear::sequents::{Eigen, Sequent};
const MEMBERS: u64 = 1 << 32;
#[kani::proof]
fn table_bytes_stay_below_two_to_the_38() {
let most: usize = kani::any();
kani::assume(most as u64 <= MEMBERS);
for entry in [
size_of::<Member>(),
size_of::<(Member, u32)>(),
size_of::<Eigen>(),
] {
let bytes = table_bytes(most, entry);
assert!(bytes < 1 << 38);
assert!(bytes >= most as u64 * entry as u64);
}
}
#[kani::proof]
fn a_sequent_takes_fewer_than_two_to_the_39_bytes() {
let theta: usize = kani::any();
let gamma: usize = kani::any();
let eigens: usize = kani::any();
kani::assume(theta as u64 <= MEMBERS && gamma as u64 <= MEMBERS);
kani::assume(eigens as u64 <= MEMBERS);
let state = State {
theta: Zone {
most: theta,
..Zone::default()
},
gamma: Bag {
most: gamma,
..Bag::default()
},
outputs: 0,
linear: 0,
unrestricted: 0,
goal: 0,
any: false,
};
assert!(state.bytes() < 1 << 39);
let set = Eigens {
most: eigens,
..Eigens::default()
};
assert!(set.bytes() < (1 << 38) + 1024);
}
#[kani::proof]
fn the_zone_bound_is_capped_below_a_saturated_count() {
let goal: usize = kani::any();
let later: usize = kani::any();
let bound = room(goal, later);
let wanted = (goal as u128 + 2 * later as u128).min(Bag::MOST as u128);
assert!(bound as u128 == wanted);
assert!(Bag::MOST < u32::MAX as usize);
}
const DOMAIN: usize = 2;
type Shape = [bool; DOMAIN];
const FIRST: Shape = [true, false];
const SECOND: Shape = [false, true];
struct Members {
weights: [u32; DOMAIN],
outputs: [bool; DOMAIN],
}
type Sums = [u128; 3];
impl Members {
fn any() -> Self {
Self {
weights: kani::any(),
outputs: kani::any(),
}
}
fn counts(shape: Shape) -> [u32; DOMAIN] {
let counts: [u32; DOMAIN] = kani::any();
for k in 0..DOMAIN {
kani::assume((counts[k] > 0) == shape[k]);
}
counts
}
fn state(&self, shape: Shape, counts: [u32; DOMAIN]) -> State {
let mut table = HashMap::default();
let mut len: u64 = 0;
let mut outputs: u64 = 0;
for k in 0..DOMAIN {
if shape[k] {
table.insert(Member::new(k as u32), counts[k]);
len += u64::from(counts[k]);
if self.outputs[k] {
outputs += u64::from(counts[k]);
}
}
}
kani::assume(len <= Bag::MOST as u64);
let (linear, goal): (u64, u64) = (kani::any(), kani::any());
kani::assume(u128::from(goal) <= u128::from(outputs) << 32);
kani::assume(u128::from(linear - goal.min(linear)) <= u128::from(len - outputs) << 32);
kani::assume(goal <= linear);
for k in 0..DOMAIN {
if shape[k] {
let weight = u64::from(self.weights[k]);
if self.outputs[k] {
kani::assume(goal >= weight);
} else {
kani::assume(linear - goal >= weight);
}
}
}
State {
theta: Zone::default(),
gamma: Bag {
most: table.len(),
counts: table,
len: len as usize,
},
outputs: outputs as usize,
linear,
unrestricted: 0,
goal,
any: kani::any(),
}
}
fn sums(state: &State) -> Sums {
[
state.outputs as u128,
u128::from(state.linear),
u128::from(state.goal),
]
}
fn one(&self, k: usize) -> Sums {
let weight = u128::from(self.weights[k]);
if self.outputs[k] {
[1, weight, weight]
} else {
[0, weight, 0]
}
}
fn assert_exact_or_refused(state: &State, counts: [u64; DOMAIN], wanted: Sums) {
let bag = &state.gamma;
assert!(bag.most >= bag.counts.len());
for (_, n) in bag.counts() {
assert!(n > 0);
assert!(n as usize <= bag.len);
}
if bag.len <= Bag::MOST {
for k in 0..DOMAIN {
let held = bag.counts.get(&Member::new(k as u32)).copied();
assert!(u64::from(held.unwrap_or(0)) == counts[k]);
}
assert!(bag.len as u64 == counts.iter().sum::<u64>());
let sums = Self::sums(state);
for i in 0..3 {
assert!(sums[i] == wanted[i]);
}
let [outputs, linear, goal] = wanted;
assert!(goal <= linear && outputs <= bag.len as u128);
}
}
fn put(shape: Shape, k: usize) {
let members = Self::any();
let counts = Self::counts(shape);
let mut state = members.state(shape, counts);
let before = (state.gamma.len, Self::sums(&state));
state.put(
Member::new(k as u32),
u64::from(members.weights[k]),
members.outputs[k],
);
let mut wanted = counts.map(u64::from);
wanted[k] += 1;
let one = members.one(k);
assert!(state.gamma.len >= before.0);
let sums = std::array::from_fn(|i| before.1[i] + one[i]);
Self::assert_exact_or_refused(&state, wanted, sums);
}
fn take(shape: Shape, k: usize) {
let members = Self::any();
let counts = Self::counts(shape);
let mut state = members.state(shape, counts);
let before = Self::sums(&state);
let taken = state.remove(Member::new(k as u32), || {
(u64::from(members.weights[k]), members.outputs[k])
});
assert!(taken == shape[k]);
let mut wanted = counts.map(u64::from);
let mut sums = before;
if taken {
wanted[k] -= 1;
let one = members.one(k);
sums = std::array::from_fn(|i| before[i] - one[i]);
}
Self::assert_exact_or_refused(&state, wanted, sums);
}
fn join(left: Shape, right: Shape) {
let members = Self::any();
let (l, r) = (Self::counts(left), Self::counts(right));
let mut state = members.state(left, l);
let mut other = members.state(right, r);
let lengths = (state.gamma.len, other.gamma.len);
let (ours, theirs) = (Self::sums(&state), Self::sums(&other));
let any = state.any || other.any;
state.add_linear(&mut other);
let wanted = std::array::from_fn(|k| u64::from(l[k]) + u64::from(r[k]));
assert!(state.gamma.len >= lengths.0 && state.gamma.len >= lengths.1);
assert!(state.any == any);
let sums = std::array::from_fn(|i| ours[i] + theirs[i]);
Self::assert_exact_or_refused(&state, wanted, sums);
}
fn unite(left: Shape, right: Shape) {
let members = Self::any();
let (l, r) = (Self::counts(left), Self::counts(right));
let mut state = members.state(left, l);
let other = members.state(right, r);
let lengths = (state.gamma.len, other.gamma.len);
state.gamma.unite(other.gamma);
state.recount(|m| {
let k = m.index();
(members.weights[k], members.outputs[k])
});
let wanted: [u64; DOMAIN] = std::array::from_fn(|k| u64::from(l[k].max(r[k])));
let mut sums = [0u128; 3];
for k in 0..DOMAIN {
let weight = u64::from(members.weights[k]) * u64::from(l[k].max(r[k]));
sums[1] += u128::from(weight);
if members.outputs[k] {
sums[0] += u128::from(wanted[k]);
sums[2] += u128::from(weight);
}
}
assert!(state.gamma.len >= lengths.0 && state.gamma.len >= lengths.1);
Self::assert_exact_or_refused(&state, wanted, sums);
}
}
#[kani::proof]
#[kani::unwind(5)]
fn a_copy_put_is_counted_or_refused() {
Members::put(FIRST, 0);
}
#[kani::proof]
#[kani::unwind(5)]
fn a_new_member_put_is_counted_or_refused() {
Members::put(FIRST, 1);
}
#[kani::proof]
#[kani::unwind(5)]
fn a_copy_taken_is_counted() {
Members::take(FIRST, 0);
}
#[kani::proof]
#[kani::unwind(5)]
fn a_member_missing_is_not_taken() {
Members::take(FIRST, 1);
}
#[kani::proof]
#[kani::unwind(5)]
fn the_sum_of_two_zones_is_counted_or_refused() {
Members::join(FIRST, FIRST);
}
#[kani::proof]
#[kani::unwind(5)]
fn the_sum_of_two_zones_apart_is_counted_or_refused() {
Members::join(FIRST, SECOND);
}
#[kani::proof]
#[kani::unwind(5)]
fn the_union_of_two_zones_is_counted_or_refused() {
Members::unite(FIRST, FIRST);
}
const NODES: u32 = 3;
fn any_index() -> NodeId {
NodeId::new(kani::any_where(|&p: &u32| p <= NODES))
}
#[kani::proof]
#[kani::unwind(5)]
fn a_kept_proof_is_ordered_and_reached() {
let forest = match Forest::new(&Sequent::new()) {
Ok(forest) => forest,
Err(error) => {
std::mem::forget(error);
unreachable!()
}
};
let leaf = Node::One(Member::new(0));
let nodes = vec![
leaf,
Node::Mix(any_index(), any_index()),
Node::Mix(any_index(), any_index()),
];
let len = nodes.len();
let root = NodeId::new(NODES - 1);
let proof = match Proof::reach(forest, nodes, root, 1, &mut || false) {
Ok(proof) => proof,
Err(error) => return std::mem::forget(error),
};
let kept = proof.nodes();
assert!(!kept.is_empty() && kept.len() <= len);
assert!(proof.root().index() == kept.len() - 1);
let mut readers = [0u32; NODES as usize];
for (i, node) in kept.iter().enumerate() {
for p in node.premises() {
assert!(p.index() < i);
readers[p.index()] += 1;
}
}
for (i, &count) in readers.iter().enumerate().take(kept.len()) {
let later = kept.len() - 1 - i;
assert!(count as usize <= later + 1);
assert!(later == 0 || count >= 1);
}
std::mem::forget(proof);
}