mod eval;
mod index;
mod rules;
#[cfg(all(test, feature = "parse"))]
mod tests;
use super::memory::{Account, Charged, bytes_of};
use super::{
Answer, Decide, Engine, Finished, NotTaken, Options, Reason, Refutation, Saturated, Stable,
Statistics, Task, Work,
};
use crate::Error;
use crate::hash::HashMap;
use crate::limits::Limits;
use crate::linear::fragment::Fragment;
use crate::linear::occurrences::OccId;
use crate::linear::proofs::{Node, NodeId};
use eval::{Calculus, Zone, within};
use rules::{Rules, Shape};
use std::cmp::Reverse;
use std::collections::BinaryHeap;
pub(crate) struct Inverse;
impl Decide for Inverse {
fn admits(&self, task: &Task<'_>) -> Result<(), Error> {
let because = if !Fragment::LL.contains(task.fragment) {
NotTaken::Fragment {
decides: Fragment::LL,
goal: task.fragment,
}
} else if task.mode.is_ordered() {
NotTaken::Mode { mode: task.mode }
} else if !task.roots && !coherent_goal(task) {
NotTaken::Shape
} else {
return Ok(());
};
Err(Error::EngineRefused {
engine: Engine::Inverse,
because,
})
}
fn decide(
&self,
task: &Task<'_>,
options: &Options,
limits: &Limits,
account: &Account,
_work: &Work,
stop: &mut dyn FnMut(u64) -> bool,
) -> Result<Answer, Error> {
let (mut found, refutation) = search(task, options, account, stop);
found.result = found.result.map_err(|r| r.as_set(options, limits));
let mut answer = Answer::of_arena(task.forest, found, stop);
answer.refutation = refutation;
Ok(answer)
}
}
fn coherent_goal(task: &Task<'_>) -> bool {
let mut members = task.goal.to_vec();
members.sort_unstable();
rules::coherent_list(task.forest, &members)
}
const APPLICATIONS_PER_POLL: u64 = 1 << 10;
const UNITS_PER_POLL: u64 = 1 << 20;
const BUILT_PER_POLL: usize = 1 << 12;
const MIX: u32 = u32::MAX;
fn search(
task: &Task<'_>,
options: &Options,
account: &Account,
stop: &mut dyn FnMut(u64) -> bool,
) -> (Finished, Option<Refutation>) {
let signs = super::focus::bias::signs(task.forest, options.bias);
let positive = signs.to_vec();
let shape = Shape::new(
task.forest,
task.goal,
signs,
task.reading,
task.mode.is_affine(),
);
let mut charged = Charged::new(account);
let goal = match rules::goal(&shape, &mut charged, stop) {
Ok(goal) => goal,
Err(reason) => return (Finished::gave_up(reason), None),
};
let derived = match rules::compile(&shape, &mut charged, stop) {
Ok(rules) => rules,
Err(reason) => return (Finished::gave_up(reason), None),
};
let mut saturation = Saturation::new(
&shape,
&derived,
&goal,
task.mode.has_mix() && !task.mode.is_affine(),
account,
stop,
);
let result = saturation.run();
let statistics = saturation.statistics;
let finished = |result| Finished {
result,
nodes: Vec::new(),
statistics,
instances: None,
};
match result {
Ok(Some(premises)) => match saturation.build(&premises) {
Ok((root, nodes)) => (
Finished {
result: Ok(Some(root)),
nodes,
statistics,
instances: None,
},
None,
),
Err(reason) => (finished(Err(reason)), None),
},
Ok(None) => (
finished(Ok(None)),
Some(Refutation::Saturated(saturation.saturated(positive))),
),
Err(reason) => (finished(Err(reason)), None),
}
}
#[derive(Clone, Copy, Debug)]
struct Kept {
start: usize,
gamma: u32,
theta: u32,
top: bool,
outputs: u64,
rank: u32,
dead: bool,
record: usize,
}
impl Kept {
fn size(&self) -> u64 {
u64::from(self.gamma) + u64::from(self.theta)
}
}
struct Saturation<'s, 'a> {
calculus: Calculus<'s, 'a>,
shape: &'s Shape<'a>,
rules: &'s Rules,
goal: &'s Rules,
mix: bool,
kept: Vec<Kept>,
store: Vec<OccId>,
records: Vec<u32>,
queue: BinaryHeap<Reverse<(u64, u32)>>,
exact: index::Trie,
weak: index::Trie,
active: Vec<u32>,
postings: HashMap<OccId, Vec<u32>>,
weak_active: Vec<u32>,
goal_index: HashMap<OccId, Vec<u32>>,
filled: Vec<Option<u32>>,
unfilled: usize,
lists: usize,
charged: Charged<'s>,
held: usize,
stack: Vec<Zone>,
unpolled: u64,
weighed: u64,
statistics: Statistics,
stop: &'s mut dyn FnMut(u64) -> bool,
}
fn grow(list: &mut Vec<u32>, id: u32) -> usize {
let before = bytes_of(list);
list.push(id);
bytes_of(list) - before
}
fn size(z: &Zone) -> u64 {
(z.gamma.len() + z.theta.len()) as u64
}
fn distinct(list: &[OccId]) -> impl Iterator<Item = OccId> + '_ {
list.iter()
.enumerate()
.filter(|&(i, o)| i == 0 || list[i - 1] != *o)
.map(|(_, &o)| o)
}
impl<'s, 'a> Saturation<'s, 'a> {
fn new(
shape: &'s Shape<'a>,
rules: &'s Rules,
goal: &'s Rules,
mix: bool,
account: &'s Account,
stop: &'s mut dyn FnMut(u64) -> bool,
) -> Self {
let mut goal_index: HashMap<OccId, Vec<u32>> = HashMap::default();
for (h, hole) in goal.holes.iter().enumerate() {
let leaves = &goal.leaves[hole.leaves.start as usize..hole.leaves.end as usize];
for o in distinct(leaves) {
goal_index.entry(o).or_default().push(h as u32);
}
}
Self {
calculus: Calculus { shape },
shape,
rules,
goal,
mix,
kept: Vec::new(),
store: Vec::new(),
records: Vec::new(),
queue: BinaryHeap::new(),
exact: index::Trie::default(),
weak: index::Trie::default(),
active: Vec::new(),
postings: HashMap::default(),
weak_active: Vec::new(),
goal_index,
filled: vec![None; goal.holes.len()],
unfilled: goal.holes.len(),
lists: 0,
charged: Charged::new(account),
held: 0,
stack: Vec::new(),
unpolled: 0,
weighed: 0,
statistics: Statistics::default(),
stop,
}
}
fn saturated(&self, positive: Vec<crate::linear::occurrences::Sign>) -> Saturated {
let sequents = (0..self.kept.len() as u32)
.filter(|&id| !self.kept[id as usize].dead)
.map(|id| {
Stable::new(
self.gamma(id).to_vec(),
self.theta(id).to_vec(),
self.kept[id as usize].top,
)
})
.collect();
Saturated::new(positive, sequents)
}
fn weak(&self, top: bool) -> bool {
top || self.shape.affine
}
fn gamma(&self, id: u32) -> &[OccId] {
let k = &self.kept[id as usize];
&self.store[k.start..k.start + k.gamma as usize]
}
fn theta(&self, id: u32) -> &[OccId] {
let k = &self.kept[id as usize];
let at = k.start + k.gamma as usize;
&self.store[at..at + k.theta as usize]
}
fn zone(&self, id: u32, node: Option<NodeId>, into: &mut Zone) {
let k = self.kept[id as usize];
into.gamma.clear();
into.gamma.extend_from_slice(self.gamma(id));
into.theta.clear();
into.theta.extend_from_slice(self.theta(id));
into.top = k.top;
into.outputs = k.outputs;
into.node = node;
}
fn settle(&mut self) -> Result<(), Reason> {
const CONTROL: usize = 1;
let held = bytes_of(&self.kept)
+ bytes_of(&self.store)
+ bytes_of(&self.records)
+ self.queue.capacity() * size_of::<Reverse<(u64, u32)>>()
+ self.exact.bytes()
+ self.weak.bytes()
+ bytes_of(&self.active)
+ self.postings.capacity() * (size_of::<(OccId, Vec<u32>)>() + CONTROL)
+ bytes_of(&self.weak_active)
+ self.lists;
self.charged.resize(self.held, held);
self.held = held;
if self.charged.account().over() {
return Err(Reason::MemoryLimit {
limit_bytes: self.charged.account().limit(),
});
}
Ok(())
}
fn work(&mut self, events: u64, units: u64, now: bool) -> Result<(), Reason> {
self.unpolled += events;
self.weighed += units;
if now || self.unpolled >= APPLICATIONS_PER_POLL || self.weighed >= UNITS_PER_POLL {
self.unpolled = 0;
if (self.stop)(std::mem::take(&mut self.weighed)) {
return Err(Reason::Stopped);
}
}
Ok(())
}
fn subsumed(&self, z: &Zone, except: Option<u32>) -> bool {
let alive = |t: u32| Some(t) != except && !self.kept[t as usize].dead;
(!self.weak(z.top) && self.exact.same_within(&z.gamma, &z.theta, alive))
|| self.weak.within(&z.gamma, &z.theta, alive)
}
fn coherent(&self, z: &Zone) -> bool {
let mut all: Vec<OccId> = z.gamma.iter().chain(&z.theta).copied().collect();
all.sort_unstable();
rules::coherent_list(self.shape.forest, &all)
}
fn keep(&mut self, mut z: Zone, record: &[u32]) -> Result<(), Reason> {
z.theta
.retain(|o| self.shape.globals.binary_search(o).is_err());
if !self.coherent(&z) {
return Ok(());
}
let subsumed = self.subsumed(&z, None);
self.work(0, self.exact.lookups() + self.weak.lookups(), false)?;
if subsumed {
self.statistics.memo_hits += 1;
return Ok(());
}
let id = u32::try_from(self.kept.len())
.ok()
.filter(|&id| id < u32::MAX)
.ok_or(Reason::IndexLimit)?;
let (Ok(gamma), Ok(theta)) = (u32::try_from(z.gamma.len()), u32::try_from(z.theta.len()))
else {
return Err(Reason::IndexLimit);
};
let start = self.store.len();
self.store.extend_from_slice(&z.gamma);
self.store.extend_from_slice(&z.theta);
let at = self.records.len();
self.records.extend_from_slice(record);
let kept = Kept {
start,
gamma,
theta,
top: z.top,
outputs: z.outputs,
rank: u32::MAX,
dead: false,
record: at,
};
self.kept.push(kept);
let index = if self.weak(z.top) {
&mut self.weak
} else {
&mut self.exact
};
if !index.insert(&z.gamma, &z.theta, id) {
return Err(Reason::IndexLimit);
}
self.queue.push(Reverse((kept.size(), id)));
self.statistics.memo_entries = self.kept.len() as u64;
let units = self.fill(id);
self.work(0, units, false)?;
self.settle()
}
fn fill(&mut self, id: u32) -> u64 {
let candidates: Vec<u32> = match self.gamma(id).first() {
Some(o) => self.goal_index.get(o).cloned().unwrap_or_default(),
None => (0..self.goal.holes.len() as u32).collect(),
};
let mut units = candidates.len() as u64;
let weak = self.weak(self.kept[id as usize].top);
for h in candidates {
if self.filled[h as usize].is_some() {
continue;
}
let hole = &self.goal.holes[h as usize];
let leaves = &self.goal.leaves[hole.leaves.start as usize..hole.leaves.end as usize];
units += leaves.len() as u64;
let theta = &self.goal.leaves[hole.theta.start as usize..hole.theta.end as usize];
let gamma = self.gamma(id);
let top = self.kept[id as usize].top;
if within(gamma, leaves)
&& (weak || gamma.len() == leaves.len())
&& (top
|| eval::excess(leaves, gamma)
.iter()
.all(|&o| !self.shape.output(o)))
&& within(self.theta(id), theta)
{
self.filled[h as usize] = Some(id);
self.unfilled -= 1;
}
}
units
}
fn concludes(&self, z: &Zone) -> bool {
z.theta.is_empty()
&& (z.gamma == self.shape.goal || (z.top && within(&z.gamma, &self.shape.goal)))
}
fn run(&mut self) -> Result<Option<Vec<u32>>, Reason> {
let rules = self.rules;
for r in 0..rules.all.len() as u32 {
if self.unfilled == 0 {
break;
}
if rules.all[r as usize].holes.is_empty() {
self.apply(r, None)?;
}
}
while self.unfilled > 0 {
let Some(Reverse((_, id))) = self.queue.pop() else {
return Ok(None);
};
if self.kept[id as usize].dead {
continue;
}
let mut z = Zone::default();
self.zone(id, None, &mut z);
let subsumed = self.subsumed(&z, Some(id));
self.work(0, self.exact.lookups() + self.weak.lookups(), false)?;
if subsumed {
self.kept[id as usize].dead = true;
continue;
}
self.activate(id)?;
}
Ok(Some(
self.filled
.iter()
.map(|f| f.expect("every hole is filled"))
.collect(),
))
}
fn activate(&mut self, id: u32) -> Result<(), Reason> {
self.work(1, 1 + 2 * u64::from(self.kept[id as usize].gamma), true)?;
self.statistics.nodes += 1;
let rank = self.active.len() as u32;
self.kept[id as usize].rank = rank;
self.lists += grow(&mut self.active, id);
let members: Vec<OccId> = distinct(self.gamma(id)).collect();
for &o in &members {
self.lists += grow(self.postings.entry(o).or_default(), id);
}
let weak = self.weak(self.kept[id as usize].top);
if weak {
self.lists += grow(&mut self.weak_active, id);
}
self.settle()?;
let holes: Vec<u32> = if weak {
(0..self.rules.holes.len() as u32).collect()
} else {
members
.iter()
.filter_map(|o| self.rules.by_leaf.get(o))
.flatten()
.chain(&self.rules.open)
.copied()
.collect()
};
for h in holes {
let hole = &self.rules.holes[h as usize];
let leaves = &self.rules.leaves[hole.leaves.start as usize..hole.leaves.end as usize];
if !weak && !within(leaves, self.gamma(id)) {
continue;
}
self.apply(hole.rule, Some((hole.index, id)))?;
if self.unfilled == 0 {
return Ok(());
}
}
if self.mix {
for rank in 0..=rank {
let t = self.active[rank as usize];
if self.kept[t as usize].dead {
continue;
}
let sizes = self.kept[t as usize].gamma + self.kept[id as usize].gamma;
self.work(1, 1 + 2 * u64::from(sizes), false)?;
let (mut l, mut r) = (Zone::default(), Zone::default());
self.zone(t, None, &mut l);
self.zone(id, None, &mut r);
if let Some(z) = self.calculus.mix(&l, &r, None) {
self.keep(z, &[MIX, t, id])?;
}
if self.unfilled == 0 {
return Ok(());
}
}
}
Ok(())
}
fn candidates(&self, hole: u32, rank: u32, before: bool) -> (Vec<u32>, u64) {
let hole = &self.rules.holes[hole as usize];
let leaves = &self.rules.leaves[hole.leaves.start as usize..hole.leaves.end as usize];
let fits = |t: &u32| {
let k = &self.kept[*t as usize];
!k.dead
&& if before {
k.rank < rank
} else {
k.rank <= rank
}
};
if leaves.is_empty() {
let scanned = self.active.len() as u64;
return (self.active.iter().copied().filter(fits).collect(), scanned);
}
let shortest = distinct(leaves)
.map(|o| self.postings.get(&o).map_or(&[][..], Vec::as_slice))
.min_by_key(|list| list.len())
.unwrap_or(&[]);
let mut out: Vec<u32> = shortest
.iter()
.copied()
.filter(|t| fits(t) && !self.weak(self.kept[*t as usize].top))
.filter(|&t| within(leaves, self.gamma(t)))
.collect();
out.extend(self.weak_active.iter().copied().filter(fits));
let scanned =
shortest.len() as u64 * (1 + leaves.len() as u64) + self.weak_active.len() as u64;
(out, scanned)
}
fn apply(&mut self, r: u32, fixed: Option<(u32, u32)>) -> Result<(), Reason> {
let rules = self.rules;
let rule = &rules.all[r as usize];
let holes = rule.holes.len();
let rank = fixed.map_or(u32::MAX, |(_, id)| self.kept[id as usize].rank);
let mut lists: Vec<Vec<Premise>> = Vec::with_capacity(holes);
for (j, h) in rule.holes.clone().enumerate() {
let (ids, scanned) = match fixed {
Some((i, id)) if i as usize == j => (vec![id], 0),
Some((i, _)) => self.candidates(h, rank, (j as u32) < i),
None => unreachable!("a rule with holes is applied with a premise"),
};
self.work(0, scanned, false)?;
let looked: u64 = ids
.iter()
.map(|&t| 1 + u64::from(self.kept[t as usize].gamma))
.sum();
self.work(0, looked, false)?;
if ids.is_empty() {
return Ok(());
}
lists.push(ids.into_iter().map(|id| self.premise(h, id)).collect());
}
let groups: Vec<u32> = rule
.holes
.clone()
.map(|h| rules.holes[h as usize].group)
.collect();
let slots = &rules.slots[rule.slots.start as usize..rule.slots.end as usize];
let steps = &rules.steps[rule.steps.start as usize..rule.steps.end as usize];
let mut at = vec![0usize; holes];
let mut partners = vec![0u32; slots.len()];
let mut chosen = vec![0u32; holes];
let mut record = Vec::with_capacity(1 + holes + slots.len());
let mut j = 0;
loop {
if j == holes {
for (c, (&p, list)) in chosen.iter_mut().zip(at.iter().zip(&lists)) {
*c = list[p].id;
}
loop {
let mut units = 0;
let mut stack = std::mem::take(&mut self.stack);
let derived = {
let this = &*self;
this.calculus.derive(
steps,
&mut |h, z| this.zone(chosen[h as usize], None, z),
&|s| {
rules.partners
[(slots[s as usize].start + partners[s as usize]) as usize]
},
None,
&mut stack,
&mut units,
)
};
self.stack = stack;
self.work(1, units, false)?;
if let Some(z) = derived {
self.work(0, size(&z), false)?;
record.clear();
record.push(r);
record.extend_from_slice(&chosen);
record.extend_from_slice(&partners);
self.keep(z, &record)?;
if self.unfilled == 0 {
return Ok(());
}
}
if !advance(&mut partners, |s| slots[s].len() as u32) {
break;
}
}
if holes == 0 {
return Ok(());
}
j = holes - 1;
at[j] += 1;
}
while at[j] < lists[j].len() && !self.fits(&lists, &groups, &at, j) {
self.work(1, 1, false)?;
at[j] += 1;
}
if at[j] < lists[j].len() {
j += 1;
} else if j == 0 {
return Ok(());
} else {
at[j] = 0;
j -= 1;
at[j] += 1;
}
}
}
fn premise(&self, hole: u32, id: u32) -> Premise {
let hole = &self.rules.holes[hole as usize];
let leaves = &self.rules.leaves[hole.leaves.start as usize..hole.leaves.end as usize];
let context = eval::excess(self.gamma(id), leaves);
let outputs = context.iter().filter(|&&o| self.shape.output(o)).count() as u64;
Premise {
id,
exact: !self.weak(self.kept[id as usize].top),
context,
outputs,
}
}
fn fits(&self, lists: &[Vec<Premise>], groups: &[u32], at: &[usize], j: usize) -> bool {
let p = &lists[j][at[j]];
if !self.shape.affine && p.exact {
for i in 0..j {
let q = &lists[i][at[i]];
if groups[i] == groups[j] && q.exact && q.context != p.context {
return false;
}
}
}
if self.shape.reading.is_some() {
let mut most: Vec<(u32, u64)> = Vec::new();
for i in 0..=j {
let (g, out) = (groups[i], lists[i][at[i]].outputs);
match most.iter_mut().find(|(h, _)| *h == g) {
Some((_, m)) => *m = (*m).max(out),
None => most.push((g, out)),
}
}
if most.iter().map(|&(_, m)| m).sum::<u64>() > 1 {
return false;
}
}
true
}
fn build(&mut self, premises: &[u32]) -> Result<(NodeId, Vec<Node>), Reason> {
let mut nodes: Vec<Node> = Vec::new();
let mut done: HashMap<u32, NodeId> = HashMap::default();
let mut charged = Charged::new(self.charged.account());
let mut todo: Vec<u32> = premises.to_vec();
while let Some(&t) = todo.last() {
if done.contains_key(&t) {
todo.pop();
continue;
}
let k = self.kept[t as usize];
let tag = self.records[k.record];
let needs: Vec<u32> = if tag == MIX {
self.records[k.record + 1..k.record + 3].to_vec()
} else {
let rule = &self.rules.all[tag as usize];
let n = rule.holes.len();
self.records[k.record + 1..k.record + 1 + n].to_vec()
};
let missing: Vec<u32> = needs
.iter()
.copied()
.filter(|p| !done.contains_key(p))
.collect();
if !missing.is_empty() {
todo.extend(missing);
continue;
}
todo.pop();
let before = bytes_of(&nodes);
let z = if tag == MIX {
let (mut l, mut r) = (Zone::default(), Zone::default());
self.zone(needs[0], Some(done[&needs[0]]), &mut l);
self.zone(needs[1], Some(done[&needs[1]]), &mut r);
self.calculus.mix(&l, &r, Some(&mut nodes))
} else {
let rules = self.rules;
let rule = &rules.all[tag as usize];
let slots = &rules.slots[rule.slots.start as usize..rule.slots.end as usize];
let n = rule.holes.len();
let chosen = &self.records[k.record + 1 + n..k.record + 1 + n + slots.len()];
let steps = &rules.steps[rule.steps.start as usize..rule.steps.end as usize];
let mut stack = Vec::new();
self.calculus.derive(
steps,
&mut |h, z| self.zone(needs[h as usize], Some(done[&needs[h as usize]]), z),
&|s| rules.partners[(slots[s as usize].start + chosen[s as usize]) as usize],
Some(&mut nodes),
&mut stack,
&mut 0,
)
};
let z = z.expect("a kept sequent's rule derives it again");
debug_assert!(
z.gamma == self.gamma(t) && z.top == k.top,
"the proof of a kept sequent derives its zones"
);
done.insert(t, z.node.expect("a node is written"));
charged.resize(before, bytes_of(&nodes));
if charged.account().over() {
return Err(Reason::MemoryLimit {
limit_bytes: charged.account().limit(),
});
}
if done.len().is_multiple_of(BUILT_PER_POLL) && (self.stop)(0) {
return Err(Reason::Stopped);
}
}
let goal = self.goal;
let steps = &goal.steps[..];
let mut stack = Vec::new();
let z = self
.calculus
.derive(
steps,
&mut |h, z| {
let t = premises[h as usize];
self.zone(t, Some(done[&t]), z);
},
&|_| unreachable!("the goal's phase has no axioms"),
Some(&mut nodes),
&mut stack,
&mut 0,
)
.expect("the goal's phase derives the goal again");
let mut z = z;
let goal = &self.shape.goal;
if self.shape.affine && !z.top && within(&z.gamma, goal) {
for o in eval::excess(goal, &z.gamma) {
let weakened = self.calculus.weaken_in(&mut z, o, &mut nodes);
debug_assert!(weakened, "only inputs go unused under a reading");
}
}
debug_assert!(self.concludes(&z), "the proof concludes the goal");
Ok((z.node.expect("a node is written"), nodes))
}
}
struct Premise {
id: u32,
exact: bool,
context: Vec<OccId>,
outputs: u64,
}
fn advance(places: &mut [u32], bound: impl Fn(usize) -> u32) -> bool {
for (i, p) in places.iter_mut().enumerate() {
*p += 1;
if *p < bound(i) {
return true;
}
*p = 0;
}
false
}