use super::memory::{Account, bytes_of};
use super::{Answer, Decide, Engine, Finished, NotTaken, Options, Reason, Statistics, Task, Work};
use crate::Error;
use crate::hash::HashMap;
use crate::limits::Limits;
use crate::linear::fragment::Fragment;
use crate::linear::occurrences::{Forest, Member, OccId};
use crate::linear::proofs::{Branch, Node, NodeId};
use crate::linear::sequents::Kind;
pub(crate) struct Additive;
impl Decide for Additive {
fn admits(&self, task: &Task<'_>) -> Result<(), Error> {
let because = if !Fragment::ADDITIVE.contains(task.fragment) {
NotTaken::Fragment {
decides: Fragment::ADDITIVE,
goal: task.fragment,
}
} else if task.goal.len() != 2 {
NotTaken::Shape
} else {
return Ok(());
};
Err(Error::EngineRefused {
engine: Engine::Additive,
because,
})
}
fn decide(
&self,
task: &Task<'_>,
options: &Options,
limits: &Limits,
account: &Account,
_work: &Work,
stop: &mut dyn FnMut(u64) -> bool,
) -> Result<Answer, Error> {
let found = search_goal(task.forest, task.goal, options, limits, account, stop);
Ok(Answer::of_arena(task.forest, found, stop))
}
}
pub(crate) fn search_goal(
forest: &Forest,
goal: &[OccId],
options: &Options,
limits: &Limits,
account: &Account,
stop: &mut dyn FnMut(u64) -> bool,
) -> Finished {
let [x, y] = goal else {
unreachable!("the dispatch sends goals of two formulas here");
};
let mut engine = Pairs {
forest,
memo: HashMap::default(),
memo_limit: options.memo_entries(),
memo_peak: 0,
nodes: Vec::new(),
statistics: Statistics::default(),
depth: 0,
recursion_limit: limits.recursion_depth,
account,
charged: 0,
stop,
};
let result = engine.pair(*x, *y).map_err(|r| r.as_set(options, limits));
let _ = (engine.stop)(engine.statistics.nodes % PAIRS_PER_POLL);
let statistics = Statistics {
memo_entries: engine.memo_peak as u64,
..engine.statistics
};
Finished {
result,
nodes: engine.nodes,
statistics,
instances: None,
}
}
const PAIRS_PER_POLL: u64 = 1 << 10;
struct Pairs<'a> {
forest: &'a Forest,
memo: HashMap<(OccId, OccId), Option<NodeId>>,
memo_limit: usize,
memo_peak: usize,
nodes: Vec<Node>,
statistics: Statistics,
depth: u32,
recursion_limit: u32,
account: &'a Account,
charged: usize,
stop: &'a mut dyn FnMut(u64) -> bool,
}
impl Pairs<'_> {
fn pair(&mut self, x: OccId, y: OccId) -> Result<Option<NodeId>, Reason> {
self.statistics.nodes += 1;
if self.statistics.nodes.is_multiple_of(PAIRS_PER_POLL) && (self.stop)(PAIRS_PER_POLL) {
return Err(Reason::Stopped);
}
self.settle()?;
if let Some(&node) = self.memo.get(&(x, y)) {
self.statistics.memo_hits += 1;
return Ok(node);
}
if self.depth >= self.recursion_limit {
return Err(Reason::RecursionLimit {
depth: self.recursion_limit,
});
}
self.depth += 1;
let result = self.decide(x, y);
self.depth -= 1;
let node = result?;
if self.memo_limit != 0 {
if self.memo.len() >= self.memo_limit {
self.memo.clear();
}
self.memo.insert((x, y), node);
self.memo_peak = self.memo_peak.max(self.memo.len());
}
Ok(node)
}
fn decide(&mut self, x: OccId, y: OccId) -> Result<Option<NodeId>, Reason> {
let f = self.forest;
let (kx, ky) = (f.kind(x), f.kind(y));
if kx == Kind::Top {
return Ok(Some(self.push(Node::Top(Member::from(x)))));
}
if ky == Kind::Top {
return Ok(Some(self.push(Node::Top(Member::from(y)))));
}
for (o, other, x_first) in [(x, y, true), (y, x, false)] {
if f.kind(o) != Kind::With {
continue;
}
let (l, r) = (f.left(o).unwrap(), f.right(o).unwrap());
let Some(left) = self.ordered(l, other, x_first)? else {
return Ok(None);
};
let Some(right) = self.ordered(r, other, x_first)? else {
return Ok(None);
};
return Ok(Some(self.push(Node::With(Member::from(o), left, right))));
}
if kx.is_literal() && ky.is_literal() {
let dual = f.dual_literals(x, y);
return Ok(dual.then(|| self.push(Node::Ax(x.into(), y.into()))));
}
for (o, other, x_first) in [(x, y, true), (y, x, false)] {
if f.kind(o) != Kind::Plus {
continue;
}
for (side, sub) in [
(Branch::Left, f.left(o).unwrap()),
(Branch::Right, f.right(o).unwrap()),
] {
if let Some(premise) = self.ordered(sub, other, x_first)? {
return Ok(Some(self.push(Node::Plus(Member::from(o), side, premise))));
}
}
}
Ok(None)
}
fn ordered(
&mut self,
sub: OccId,
other: OccId,
sub_first: bool,
) -> Result<Option<NodeId>, Reason> {
if sub_first {
self.pair(sub, other)
} else {
self.pair(other, sub)
}
}
fn settle(&mut self) -> Result<(), Reason> {
const SLOT: usize = size_of::<((OccId, OccId), Option<NodeId>)>() + 1;
if self.nodes.len() >= u32::MAX as usize {
return Err(Reason::IndexLimit);
}
let held = self.memo.capacity() * SLOT + bytes_of(&self.nodes);
if held == self.charged {
return Ok(());
}
self.account.resize(self.charged, held);
self.charged = held;
if self.account.over() {
self.memo = HashMap::default();
self.account.resize(self.charged, bytes_of(&self.nodes));
self.charged = bytes_of(&self.nodes);
if self.account.over() {
return Err(Reason::MemoryLimit {
limit_bytes: self.account.limit(),
});
}
}
Ok(())
}
fn push(&mut self, node: Node) -> NodeId {
let id = NodeId::new(self.nodes.len() as u32);
self.nodes.push(node);
id
}
}
#[cfg(all(test, feature = "parse"))]
mod tests {
use super::*;
use crate::linear::Sequent;
use crate::linear::fragment::Mode;
use crate::linear::search::generate::Rng;
use crate::linear::search::{Engine as Which, Verdict, prove};
fn sequent(input: &str) -> Sequent {
input.parse().unwrap_or_else(|e| panic!("{input:?}: {e}"))
}
fn decide(input: &str, mode: Mode, engine: Which) -> bool {
let s = sequent(input);
let outcome = prove(&s, mode, &Options::default().with_engine(Some(engine)))
.unwrap_or_else(|e| panic!("{input:?} by {engine}: {e}"));
assert_eq!(outcome.engine, engine);
match outcome.verdict {
Verdict::Proved(proof) => {
assert_eq!(proof.sequent(), &s);
proof.check(mode).unwrap_or_else(|e| {
panic!("{input:?} by {engine}: {}", e.describe(proof.forest()))
});
true
}
Verdict::Unprovable(_) => false,
Verdict::Unknown(reason) => panic!("{input:?} by {engine}: {reason}"),
}
}
#[test]
fn capped_memo() {
let instance = crate::linear::families::find("additive")
.unwrap()
.instance(8, 0)
.unwrap();
let options = Options::default().with_memo_limit(64);
let outcome = prove(&instance.sequent, instance.mode, &options).unwrap();
assert_eq!(outcome.engine, Which::Additive);
assert_eq!(outcome.statistics.memo_entries, 64);
let Verdict::Proved(proof) = outcome.verdict else {
panic!("the identity is provable");
};
assert_eq!(proof.check(instance.mode), Ok(()));
}
#[test]
fn stops_between_pairs() {
let instance = crate::linear::families::find("additive")
.unwrap()
.instance(8, 0)
.unwrap();
let outcome = crate::linear::search::prove_within(
&instance.sequent,
instance.mode,
&Options::default(),
&crate::Limits::default(),
|_| true,
)
.unwrap();
assert_eq!(outcome.engine, Which::Additive);
assert!(
matches!(
outcome.verdict,
Verdict::Unknown(crate::linear::search::Reason::Stopped)
),
"{:?}",
outcome.verdict
);
assert_eq!(outcome.statistics.nodes, super::PAIRS_PER_POLL);
}
#[test]
fn additive_sequents() {
for (input, expected) in [
("a |- a", true),
("a |- b", false),
("a & b |- a", true),
("a |- a & b", false),
("a |- a + b", true),
("a + b |- a", false),
("a & b |- a + b", true),
("a + b |- a & b", false),
("a & b |- b & a", true),
("a + b |- b + a", true),
("a & (b + c) |- (a & b) + (a & c)", false),
("(a & b) + (a & c) |- a & (b + c)", true),
("|- top, 0", true),
("0 |- a", true),
("a |- 0", false),
("top |- a", false),
("a |- top", true),
("0 |- top", true),
("a & top |- a", true),
("a |- a & top", true),
("a + 0 |- a", true),
("a |- a + 0", true),
("0 + b |- a", false),
("(a + top) & b |- b", true),
("|- a & b, ~a + ~b", true),
("|- a & b, ~a", false),
("|- ~c + ~a, b + (c & a)", true),
("b + (c & a) |- b + (c & a)", true),
("c & a |- b + (c & a)", true),
] {
for mode in [
Mode::CLASSICAL,
Mode::CLASSICAL.with_affine(),
Mode::CLASSICAL.with_mix(),
] {
assert_eq!(
decide(input, mode, Which::Additive),
expected,
"{input:?} {mode}"
);
assert_eq!(
decide(input, mode, Which::Focus),
expected,
"{input:?} {mode}"
);
}
if !input.starts_with("|-") {
let i = Mode::INTUITIONISTIC;
assert_eq!(decide(input, i, Which::Additive), expected, "{input:?} {i}");
assert_eq!(decide(input, i, Which::TwoSided), expected, "{input:?} {i}");
}
}
}
fn formula(rng: &mut Rng, depth: usize) -> String {
if depth == 0 || rng.one_in(4) {
return match rng.below(8) {
0 => "top".into(),
1 => "0".into(),
n => ["a", "b", "c", "~a", "~b", "~c"][n - 2].into(),
};
}
let (l, r) = (formula(rng, depth - 1), formula(rng, depth - 1));
if rng.one_in(2) {
format!("({l} & {r})")
} else {
format!("({l} + {r})")
}
}
#[test]
fn agrees_with_the_focused_engine() {
let mut rng = Rng::new(11);
let (mut compared, mut provable) = (0, 0);
for _ in 0..300 {
let input = format!("|- {}, {}", formula(&mut rng, 3), formula(&mut rng, 3));
let expected = decide(&input, Mode::CLASSICAL, Which::Focus);
assert_eq!(
decide(&input, Mode::CLASSICAL, Which::Additive),
expected,
"{input:?}"
);
let i = Mode::INTUITIONISTIC;
if prove(&sequent(&input), i, &Options::default()).is_ok() {
let expected = decide(&input, i, Which::TwoSided);
assert_eq!(decide(&input, i, Which::Additive), expected, "{input:?}");
}
compared += 1;
provable += usize::from(expected);
}
assert!(
provable > 30 && provable < compared,
"{provable} of {compared}"
);
}
#[test]
fn memoized() {
let mut left = String::from("a");
let mut right = String::from("~b");
for _ in 0..7 {
left = format!("({left} + {left})");
right = format!("({right} + {right})");
}
let s = sequent(&format!("|- {left}, {right}"));
let outcome = prove(&s, Mode::CLASSICAL, &Options::default()).unwrap();
assert_eq!(outcome.engine, Which::Additive);
assert!(matches!(outcome.verdict, Verdict::Unprovable(_)));
let s = outcome.statistics;
assert!(s.memo_entries <= 255 * 255, "{}", s.memo_entries);
assert!(s.memo_hits > 0);
assert_eq!(s.memo_entries + s.memo_hits, s.nodes);
}
}