use super::error::{CheckError, Fault, Refused};
use super::frames::{Framed, Ground, Instancing};
use super::zones::{Bag, Eigens, State, Zone};
use crate::limits::{Limits, Phase, Progress, Refusal};
use crate::linear::fragment::Mode;
use crate::linear::occurrences::{Forest, Member, OccId, Reading, Side};
use crate::linear::proofs::{Branch, Node, NodeId, Proof};
use crate::linear::sequents::Kind;
#[derive(Debug)]
pub(super) enum Halt {
Fault(Fault),
Memory {
limit: u64,
},
Work {
limit: u64,
},
Stopped,
}
pub(super) const POLL: usize = 4096;
pub(super) const POLL_WORK: u64 = 1 << 16;
pub(crate) struct Allowance<'s> {
pub(crate) memory: Option<u64>,
pub(crate) work: Option<u64>,
pub(crate) phase: Phase,
pub(crate) stop: &'s mut dyn FnMut(Progress) -> bool,
}
impl<'s> Allowance<'s> {
pub(crate) fn new(
limits: &Limits,
phase: Phase,
stop: &'s mut dyn FnMut(Progress) -> bool,
) -> Self {
Self {
memory: limits.memory_bytes,
work: limits.work,
phase,
stop,
}
}
}
impl From<Fault> for Halt {
fn from(fault: Fault) -> Self {
Self::Fault(fault)
}
}
pub(crate) fn check(proof: &Proof, mode: Mode) -> Result<(), CheckError> {
check_within(proof, mode, &Limits::default(), &mut |_| false)
}
pub(crate) fn check_within(
proof: &Proof,
mode: Mode,
limits: &Limits,
stop: &mut dyn FnMut(Progress) -> bool,
) -> Result<(), CheckError> {
let reading = reading(proof, mode)?;
examine(
proof,
&proof.conclusion(),
mode,
reading.as_ref(),
Allowance::new(limits, Phase::Check, stop),
&mut (),
)
}
pub(crate) fn reading(proof: &Proof, mode: Mode) -> Result<Option<Reading<'_>>, CheckError> {
if !mode.intuitionistic {
return Ok(None);
}
match Reading::of_mode(proof.forest(), mode) {
Ok(reading) => Ok(Some(reading)),
Err(e) => Err(CheckError::invalid(
proof.root(),
proof.node(proof.root()),
vec![],
Fault::Shape(e),
)),
}
}
pub(crate) fn examine<O: Observer>(
proof: &Proof,
goal: &[OccId],
mode: Mode,
reading: Option<&Reading>,
allowance: Allowance<'_>,
observer: &mut O,
) -> Result<(), CheckError> {
match proof.instances() {
None => examine_with(proof, goal, mode, reading, allowance, observer, || Ground),
Some(table) => examine_with(proof, goal, mode, reading, allowance, observer, || {
Framed::new(proof, table)
}),
}
}
fn examine_with<O: Observer, I: Instancing>(
proof: &Proof,
goal: &[OccId],
mode: Mode,
reading: Option<&Reading>,
allowance: Allowance<'_>,
observer: &mut O,
instancing: impl Fn() -> I,
) -> Result<(), CheckError> {
let (memory, phase) = (allowance.memory, allowance.phase);
afford(proof, observer.bytes(), memory, phase)?;
let mut pass = Pass::new(
proof,
goal.len(),
mode,
reading,
allowance,
observer,
instancing(),
);
let end = proof.nodes().len();
let (node, halt) = match pass.run(end) {
Err(failure) => failure,
Ok(()) => match pass.conclude(goal) {
Ok(()) => return Ok(()),
Err(halt) => (proof.root(), halt),
},
};
drop(pass);
let rule = proof.node(node);
let fault = match halt {
Halt::Fault(fault) => fault,
Halt::Memory { limit } => return Err(memory_refused(node, limit, phase)),
Halt::Work { limit } => return Err(refused(node, Refusal::Work { limit })),
Halt::Stopped => return Err(refused(node, Refusal::Stopped { phase })),
};
let mut nobody = ();
let mut never = |_| false;
let again = Allowance {
memory,
work: None,
phase,
stop: &mut never,
};
let mut pass = Pass::new(
proof,
goal.len(),
mode,
reading,
again,
&mut nobody,
instancing(),
);
let again = pass.run(node.index());
debug_assert!(again.is_ok());
let premises = rule
.premises()
.filter_map(|p| pass.live[p.index()].as_deref().map(State::to_dyadic))
.collect();
Err(CheckError::invalid(node, rule, premises, fault))
}
fn arcs(forest: &Forest, o: OccId, left: &Bag, right: &Bag, occ: impl Fn(Member) -> OccId) -> bool {
let n = forest.len() as u64;
let from = |x: OccId| (u64::from(x.get()) + n - u64::from(o.get())) % n;
let last_right = right.counts().map(|(x, _)| from(occ(x))).max();
let first_left = left.counts().map(|(x, _)| from(occ(x))).min();
match (last_right, first_left) {
(Some(r), Some(l)) => r <= l,
_ => true,
}
}
pub(super) fn room(goal: usize, later: usize) -> usize {
goal.saturating_add(later.saturating_mul(2)).min(Bag::MOST)
}
pub(super) fn memory_refused(node: NodeId, limit: u64, phase: Phase) -> CheckError {
refused(
node,
Refusal::Memory {
phase,
limit_bytes: limit,
needed_bytes: None,
},
)
}
pub(super) fn refused(node: NodeId, refusal: Refusal) -> CheckError {
CheckError::Refused(Refused { node, refusal })
}
pub(super) fn tables(proof: &Proof) -> u64 {
proof.nodes().len() as u64 * (size_of::<u32>() + size_of::<Option<Box<State>>>()) as u64
}
pub(crate) fn afford(
proof: &Proof,
observer: u64,
memory: Option<u64>,
phase: Phase,
) -> Result<(), CheckError> {
match memory {
Some(limit) if tables(proof).saturating_add(observer) > limit => {
Err(memory_refused(NodeId::new(0), limit, phase))
}
_ => Ok(()),
}
}
pub(crate) trait Observer {
fn weight(&self, m: Member, o: OccId) -> u32 {
let _ = (m, o);
0
}
fn bytes(&self) -> u64 {
0
}
fn derived(&mut self, id: NodeId, state: &State, facts: &Facts<'_>);
}
impl Observer for () {
fn derived(&mut self, _: NodeId, _: &State, _: &Facts<'_>) {}
}
#[derive(Clone, Copy, Debug, Default)]
pub(crate) struct Facts<'a> {
pub(crate) used: bool,
pub(crate) shared: &'a [Member],
pub(crate) absent: [bool; 2],
pub(crate) needs: [usize; 2],
}
pub(super) struct Pass<'a, 's, O, I> {
proof: &'a Proof,
forest: &'a Forest,
goal: usize,
mode: Mode,
reading: Option<&'a Reading<'a>>,
readers: Vec<u32>,
live: Vec<Option<Box<State>>>,
observer: &'a mut O,
shared: Vec<Member>,
inst: I,
eigens: Vec<Option<Box<Eigens>>>,
memory: Option<u64>,
work: Option<u64>,
done: u64,
polled: u64,
phase: Phase,
stop: &'s mut dyn FnMut(Progress) -> bool,
held: u64,
passed: u64,
}
impl<'a, 's, O: Observer, I: Instancing> Pass<'a, 's, O, I> {
fn new(
proof: &'a Proof,
goal: usize,
mode: Mode,
reading: Option<&'a Reading<'a>>,
allowance: Allowance<'s>,
observer: &'a mut O,
inst: I,
) -> Self {
let mut readers = vec![0; proof.nodes().len()];
for node in proof.nodes() {
for p in node.premises() {
readers[p.index()] += 1;
}
}
let mut live = Vec::new();
live.resize_with(readers.len(), || None);
let held = tables(proof);
Self {
proof,
forest: proof.forest(),
goal,
mode,
reading,
readers,
live,
observer,
shared: Vec::new(),
eigens: if I::FRAMED {
let mut eigens = Vec::new();
eigens.resize_with(proof.nodes().len(), || None);
eigens
} else {
Vec::new()
},
inst,
memory: allowance.memory,
work: allowance.work,
phase: allowance.phase,
stop: allowance.stop,
held,
passed: 0,
done: 0,
polled: 0,
}
}
fn charge(&mut self, bytes: u64) -> Result<(), Halt> {
self.held = self.held.saturating_add(bytes);
match self.memory {
Some(limit) if self.held.saturating_add(self.observer.bytes()) > limit => {
Err(Halt::Memory { limit })
}
_ => Ok(()),
}
}
fn run(&mut self, end: usize) -> Result<(), (NodeId, Halt)> {
for id in self.proof.ids().take(end) {
if let Some(limit) = self.work
&& self.done >= limit
{
return Err((id, Halt::Work { limit }));
}
self.done = self.done.saturating_add(1);
if (id.index() + 1).is_multiple_of(POLL) || self.done - self.polled >= POLL_WORK {
let since = self.done - self.polled;
self.polled = self.done;
let progress = Progress {
held_bytes: self.held,
..Progress::new(self.phase, since, self.done)
};
if (self.stop)(progress) {
return Err((id, Halt::Stopped));
}
}
let mut facts = Facts::default();
self.passed = 0;
let state = self
.rule(id, self.proof.node(id), &mut facts)
.and_then(|state| self.within(id, state))
.and_then(|state| self.one_succedent(state))
.map_err(|problem| (id, problem))?;
if I::FRAMED {
self.flow(id).map_err(|problem| (id, problem))?;
}
facts.shared = &self.shared;
self.observer.derived(id, &state, &facts);
self.held = self.held.saturating_sub(self.passed);
if self.readers[id.index()] > 0 || id == self.proof.root() {
self.charge(state.bytes())
.map_err(|problem| (id, problem))?;
self.live[id.index()] = Some(state);
}
}
Ok(())
}
fn conclude(&self, goal: &[OccId]) -> Result<(), Halt> {
if let Some(reading) = self.reading {
let count = reading.outputs(goal.iter().copied());
if count != 1 {
return Err(Halt::Fault(Fault::Succedents { count }));
}
}
let root = self.live[self.proof.root().index()]
.as_deref()
.expect("the root's sequent is kept");
let remained = self
.eigens
.get(self.proof.root().index())
.and_then(Option::as_deref);
let escaped = remained.and_then(|e| {
e.set
.iter()
.copied()
.filter(|&a| self.inst.introduces(a))
.min()
});
if let Some(eigen) = escaped {
return Err(Halt::Fault(Fault::Eigenvariable { eigen }));
}
let goal = Bag::of(goal.iter().copied().map(Member::from));
let concludes = if root.any {
root.gamma.is_subset(&goal)
} else {
root.gamma == goal
};
if root.theta.is_empty() && concludes {
Ok(())
} else {
Err(Halt::Fault(Fault::Conclusion {
derived: root.to_dyadic(),
}))
}
}
fn premise(&mut self, p: NodeId) -> Result<Box<State>, Halt> {
self.readers[p.index()] -= 1;
let last = self.readers[p.index()] == 0;
let kept = "a premise's sequent is kept until its last reader";
let state = self.live[p.index()].as_deref().expect(kept);
let bytes = state.bytes();
self.done = self.done.saturating_add(state.entries());
if !last {
self.charge(bytes)?;
}
self.passed = self.passed.saturating_add(bytes);
let slot = &mut self.live[p.index()];
Ok(if last { slot.take() } else { slot.clone() }.expect(kept))
}
fn is_output(&self, o: OccId) -> bool {
self.reading.is_some_and(|r| r.position(o) == Side::Output)
}
fn expect(&self, m: Member, o: OccId, kind: Kind) -> Result<(), Halt> {
if self.forest.kind(o) == kind {
Ok(())
} else {
Err(Halt::Fault(Fault::Kind { member: m }))
}
}
fn put(&self, d: &mut State, m: Member) {
let o = self.inst.occ(m);
d.put(m, u64::from(self.observer.weight(m, o)), self.is_output(o));
}
fn take(&self, d: &mut State, m: Member, premise: usize) -> Result<bool, Halt> {
let o = self.inst.occ(m);
if d.remove(m, || {
(u64::from(self.observer.weight(m, o)), self.is_output(o))
}) {
return Ok(false);
}
if !d.any {
return Err(Halt::Fault(Fault::Missing { premise, member: m }));
}
if self.is_output(o) && d.outputs > 0 {
return Err(Halt::Fault(Fault::Succedents { count: 2 }));
}
Ok(true)
}
fn quest_weight(&self, a: Member) -> u64 {
let q = self
.forest
.parent(self.inst.occ(a))
.expect("an unrestricted occurrence is under a ?");
u64::from(self.observer.weight(self.inst.parent(a, q), q))
}
fn within(&self, id: NodeId, d: Box<State>) -> Result<Box<State>, Halt> {
let later = self.proof.nodes().len() - 1 - id.index();
if d.gamma.len > room(self.goal, later) {
return Err(Halt::Fault(Fault::Surplus));
}
Ok(d)
}
fn one_succedent(&self, d: Box<State>) -> Result<Box<State>, Halt> {
if self.reading.is_some() && (d.outputs > 1 || (d.outputs == 0 && !d.any)) {
return Err(Halt::Fault(Fault::Succedents { count: d.outputs }));
}
if !self.mode.allows_empty_antecedents() && d.gamma.len <= d.outputs {
return Err(Halt::Fault(Fault::EmptyAntecedent));
}
Ok(d)
}
fn left(&self, m: Member, o: OccId) -> Member {
self.inst.child(m, self.forest.left(o).unwrap())
}
fn right(&self, m: Member, o: OccId) -> Member {
self.inst.child(m, self.forest.right(o).unwrap())
}
#[cfg_attr(
target_pointer_width = "32",
expect(
clippy::unnecessary_box_returns,
reason = "a sequent is small on 32 bits, and the pass keeps every one boxed"
)
)]
fn just(&self, ids: impl IntoIterator<Item = Member>, any: bool) -> Box<State> {
let mut d = Box::new(State {
theta: Zone::default(),
gamma: Bag::default(),
outputs: 0,
linear: 0,
unrestricted: 0,
goal: 0,
any,
});
for m in ids {
self.put(&mut d, m);
}
d
}
fn unite(&mut self, l: &mut State, r: &mut State) {
if r.theta.len() > l.theta.len() {
std::mem::swap(&mut l.theta, &mut r.theta);
std::mem::swap(&mut l.unrestricted, &mut r.unrestricted);
}
for a in r.theta.members.drain() {
if l.theta.insert(a) {
l.unrestricted += self.quest_weight(a);
} else {
self.shared.push(a);
}
}
}
#[cfg_attr(
target_pointer_width = "32",
expect(
clippy::unnecessary_box_returns,
reason = "a sequent is small on 32 bits, and the pass keeps every one boxed"
)
)]
fn join(&mut self, mut l: Box<State>, mut r: Box<State>) -> Box<State> {
self.unite(&mut l, &mut r);
l.add_linear(&mut r);
l
}
fn flow(&mut self, id: NodeId) -> Result<(), Halt> {
let node = self.proof.node(id);
let mut set: Option<Box<Eigens>> = None;
for p in node.premises() {
let theirs = if self.readers[p.index()] == 0 {
self.eigens[p.index()].take()
} else {
let copy = self.eigens[p.index()].clone();
if let Some(copy) = © {
self.charge(copy.bytes())?;
}
copy
};
match (&mut set, theirs) {
(Some(ours), Some(theirs)) => {
let before = ours.bytes().saturating_add(theirs.bytes());
ours.add(*theirs);
let after = ours.bytes();
if after > before {
self.charge(after - before)?;
} else {
self.held = self.held.saturating_sub(before - after);
}
}
(None, theirs) => set = theirs,
(Some(_), None) => {}
}
}
if let Node::Forall(_, a, _) = node
&& let Some(set) = &mut set
{
set.set.remove(&a);
}
let mut brought = Vec::new();
let units = self.inst.bring(node, &mut brought);
self.done = self.done.saturating_add(units);
if !brought.is_empty() {
let set = set.get_or_insert_with(|| Box::new(Eigens::default()));
let before = set.bytes();
for a in brought {
set.insert(a);
}
let after = set.bytes();
self.charge(after.saturating_sub(before))?;
}
if self.readers[id.index()] > 0 || id == self.proof.root() {
self.eigens[id.index()] = set;
} else if let Some(set) = set {
self.held = self.held.saturating_sub(set.bytes());
}
Ok(())
}
fn rule(&mut self, id: NodeId, node: Node, facts: &mut Facts<'_>) -> Result<Box<State>, Halt> {
use Node::*;
let f = self.forest;
self.shared.clear();
if self.mode.is_ordered() && !matches!(node, Ax(..) | Par(..) | Tensor(..)) {
return Err(Halt::Fault(Fault::Forbidden));
}
if let Some(fault) = self.inst.fault(id) {
return Err(Halt::Fault(fault));
}
match node {
Ax(a, b) => {
for m in [a, b] {
if !f.is_literal(self.inst.occ(m)) {
return Err(Halt::Fault(Fault::Kind { member: m }));
}
}
if I::FRAMED {
let frames = self
.inst
.frame_len(a)
.saturating_add(self.inst.frame_len(b));
self.done = self.done.saturating_add(frames);
}
if !self.inst.dual_literals(f, a, b) {
return Err(Halt::Fault(Fault::NotDual));
}
Ok(self.just([a, b], false))
}
One(m) => {
self.expect(m, self.inst.occ(m), Kind::One)?;
Ok(self.just([m], false))
}
Top(m) => {
self.expect(m, self.inst.occ(m), Kind::Top)?;
Ok(self.just([m], true))
}
Bot(m, p) => {
self.expect(m, self.inst.occ(m), Kind::Bot)?;
let mut d = self.premise(p)?;
self.put(&mut d, m);
Ok(d)
}
Par(m, p) => {
let o = self.inst.occ(m);
self.expect(m, o, Kind::Par)?;
let mut d = self.premise(p)?;
facts.absent[0] = self.take(&mut d, self.left(m, o), 0)?;
facts.absent[1] = self.take(&mut d, self.right(m, o), 0)?;
self.put(&mut d, m);
Ok(d)
}
Tensor(m, l, r) => {
let o = self.inst.occ(m);
self.expect(m, o, Kind::Tensor)?;
let (mut dl, mut dr) = (self.premise(l)?, self.premise(r)?);
facts.needs = [dl.theta.len(), dr.theta.len()];
facts.absent[0] = self.take(&mut dl, self.left(m, o), 0)?;
facts.absent[1] = self.take(&mut dr, self.right(m, o), 1)?;
if self.mode.is_ordered()
&& !arcs(self.forest, o, &dl.gamma, &dr.gamma, |x| self.inst.occ(x))
{
return Err(Halt::Fault(Fault::Order));
}
let mut d = self.join(dl, dr);
self.put(&mut d, m);
Ok(d)
}
With(m, l, r) => {
let o = self.inst.occ(m);
self.expect(m, o, Kind::With)?;
let (mut dl, mut dr) = (self.premise(l)?, self.premise(r)?);
facts.needs = [dl.theta.len(), dr.theta.len()];
facts.absent[0] = self.take(&mut dl, self.left(m, o), 0)?;
facts.absent[1] = self.take(&mut dr, self.right(m, o), 1)?;
let mut d = match (dl.any, dr.any) {
(false, false) if dl.gamma == dr.gamma => self.over(dl, dr),
(true, false) if dl.gamma.is_subset(&dr.gamma) => self.over(dr, dl),
(false, true) if dr.gamma.is_subset(&dl.gamma) => self.over(dl, dr),
(true, true) => {
let gamma = std::mem::take(&mut dr.gamma);
dl.gamma.unite(gamma);
let mut d = self.over(dl, dr);
d.any = true;
self.recount(&mut d);
d
}
_ => return Err(Halt::Fault(Fault::Differ)),
};
self.shared.clear();
self.put(&mut d, m);
Ok(d)
}
Plus(m, side, p) => {
let o = self.inst.occ(m);
self.expect(m, o, Kind::Plus)?;
let mut d = self.premise(p)?;
let chosen = match side {
Branch::Left => self.left(m, o),
Branch::Right => self.right(m, o),
};
facts.absent[0] = self.take(&mut d, chosen, 0)?;
self.put(&mut d, m);
Ok(d)
}
Bang(m, p) => {
let o = self.inst.occ(m);
self.expect(m, o, Kind::Bang)?;
let mut d = self.premise(p)?;
facts.absent[0] = self.take(&mut d, self.left(m, o), 0)?;
if !d.gamma.is_empty() {
return Err(Halt::Fault(Fault::NotEmpty));
}
d.any = false;
self.put(&mut d, m);
Ok(d)
}
Quest(m, p) => {
let o = self.inst.occ(m);
self.expect(m, o, Kind::Quest)?;
let mut d = self.premise(p)?;
if d.theta.remove(self.left(m, o)) {
facts.used = true;
d.unrestricted -= u64::from(self.observer.weight(m, o));
}
self.put(&mut d, m);
Ok(d)
}
Copy(a, p) => {
let o = self.inst.occ(a);
if f.parent(o).map(|q| f.kind(q)) != Some(Kind::Quest) {
return Err(Halt::Fault(Fault::NotUnderQuest { member: a }));
}
let mut d = self.premise(p)?;
facts.absent[0] = self.take(&mut d, a, 0)?;
if d.theta.insert(a) {
d.unrestricted += self.quest_weight(a);
} else {
facts.used = true;
}
Ok(d)
}
Weaken(m, p) => {
let o = self.inst.occ(m);
if !self.mode.affine && f.kind(o) != Kind::Quest {
return Err(Halt::Fault(Fault::Forbidden));
}
if self.is_output(o) {
return Err(Halt::Fault(Fault::Succedents { count: 0 }));
}
let mut d = self.premise(p)?;
self.put(&mut d, m);
Ok(d)
}
Mix(l, r) => {
if !self.mode.mix || self.mode.intuitionistic {
return Err(Halt::Fault(Fault::Forbidden));
}
let (dl, dr) = (self.premise(l)?, self.premise(r)?);
facts.needs = [dl.theta.len(), dr.theta.len()];
Ok(self.join(dl, dr))
}
Cut(a, l, r) => {
let o = self.inst.occ(a);
let dual = match self.inst.dual(f, a) {
Some(dual) if o < self.inst.occ(dual) => dual,
_ => return Err(Halt::Fault(Fault::NotACut { member: a })),
};
let (mut dl, mut dr) = (self.premise(l)?, self.premise(r)?);
facts.needs = [dl.theta.len(), dr.theta.len()];
facts.absent[0] = self.take(&mut dl, a, 0)?;
facts.absent[1] = self.take(&mut dr, dual, 1)?;
Ok(self.join(dl, dr))
}
Forall(m, _, p) => {
self.expect(m, self.inst.occ(m), Kind::Forall)?;
let mut d = self.premise(p)?;
facts.absent[0] = self.take(&mut d, self.inst.body(id), 0)?;
self.put(&mut d, m);
Ok(d)
}
Exists(m, _, p) => {
self.expect(m, self.inst.occ(m), Kind::Exists)?;
let mut d = self.premise(p)?;
facts.absent[0] = self.take(&mut d, self.inst.body(id), 0)?;
self.put(&mut d, m);
Ok(d)
}
}
}
#[cfg_attr(
target_pointer_width = "32",
expect(
clippy::unnecessary_box_returns,
reason = "a sequent is small on 32 bits, and the pass keeps every one boxed"
)
)]
fn over(&mut self, mut keep: Box<State>, mut other: Box<State>) -> Box<State> {
self.unite(&mut keep, &mut other);
keep
}
fn recount(&self, d: &mut State) {
d.recount(|m| {
let o = self.inst.occ(m);
(self.observer.weight(m, o), self.is_output(o))
});
}
}