mod cover;
mod equation;
mod proof;
mod reach;
#[cfg(test)]
mod tests;
use super::memory::{Account, Charged};
use super::{
Answer, Decide, Engine, Finished, NotTaken, Options, Reason, Refutation, StateEquation,
Statistics, Task, Work,
};
use crate::Error;
use crate::hash::HashMap;
use crate::limits::Limits;
use crate::linear::fragment::Fragment;
use crate::linear::occurrences::{Forest, OccId, Side, Sign};
use crate::linear::sequents::{Atom, Kind};
use equation::Equation;
pub(crate) struct Horn;
impl Decide for Horn {
fn admits(&self, task: &Task<'_>) -> Result<(), Error> {
let because = if !Fragment::MELL.contains(task.fragment) {
NotTaken::Fragment {
decides: Fragment::MELL,
goal: task.fragment,
}
} else if Program::of(task).is_none() {
NotTaken::Shape
} else {
return Ok(());
};
Err(Error::EngineRefused {
engine: Engine::Horn,
because,
})
}
fn decide(
&self,
task: &Task<'_>,
_options: &Options,
_limits: &Limits,
account: &Account,
_work: &Work,
stop: &mut dyn FnMut(u64) -> bool,
) -> Result<Answer, Error> {
let counted = super::focus::counts::refutation(
task.forest,
task.goal,
task.fragment,
task.mode,
&account.fork(),
stop,
);
if counted != Refutation::Exhausted {
return Ok(Answer {
refutation: Some(counted),
..Answer::of_arena(
task.forest,
Finished {
result: Ok(None),
nodes: Vec::new(),
statistics: Statistics::default(),
instances: None,
},
stop,
)
});
}
let program = Program::of(task).expect("the engine admitted the goal");
let affine = task.mode.affine;
let mut equation = Equation::new(affine, account);
let most = reach::MOST_MARKINGS;
let (mut found, statistics) = if affine {
cover::search(program, account, most, &mut equation, stop)
} else {
reach::search(program, account, most, &mut equation, stop)
};
if let Err(Reason::MemoryLimit { .. } | Reason::IndexLimit) = found
&& let Ok(true) = equation.finish(program, stop)
{
found = Ok(None);
}
if let Ok(Some(_)) = found {
equation.release();
}
let (result, nodes) = match found {
Ok(Some(firings)) => {
match proof::build(
task.forest,
program,
&firings,
affine,
account,
proof::MOST_NODES,
) {
Ok((root, nodes)) => (Ok(Some(root)), nodes),
Err(reason) => (Err(reason), Vec::new()),
}
}
Ok(None) => (Ok(None), Vec::new()),
Err(reason) => (Err(reason), Vec::new()),
};
let mut answer = Answer::of_arena(
task.forest,
Finished {
result,
nodes,
statistics,
instances: None,
},
stop,
);
answer.refutation = equation
.certificate()
.map(|weights| program.refutation(weights));
Ok(answer)
}
}
pub(crate) fn is_net(task: &Task<'_>) -> bool {
Program::of(task).is_some_and(|program| !program.quests.is_empty())
}
type Arcs = Vec<(u32, u32)>;
impl Program {
fn inputs(&self, t: &Transition) -> &[(u32, u32)] {
t.inputs_in(&self.arcs)
}
fn outputs(&self, t: &Transition) -> &[(u32, u32)] {
t.outputs_in(&self.arcs)
}
fn reversed(&self) -> Program {
let mut arcs = Vec::with_capacity(self.arcs.len());
let transitions = self
.transitions
.iter()
.map(|t| {
let inputs = arcs.len() as u32;
arcs.extend_from_slice(self.outputs(t));
let outputs = arcs.len() as u32;
arcs.extend_from_slice(self.inputs(t));
Transition {
clause: t.clause,
inputs,
outputs,
end: arcs.len() as u32,
}
})
.collect();
Program {
places: self.places,
place_of: Vec::new(),
transitions,
arcs,
initial: self.target.clone(),
target: self.initial.clone(),
body: self.body,
quests: Vec::new(),
markings: Vec::new(),
goal: self.goal,
once: Vec::new(),
alike: Vec::new(),
dropped: Vec::new(),
}
}
fn caps(&self) -> Vec<u32> {
let mut raised = vec![false; self.places];
for t in &self.transitions {
let mut inputs = self.inputs(t).iter().peekable();
for &(p, w) in self.outputs(t) {
while inputs.next_if(|&&(q, _)| q < p).is_some() {}
let taken = inputs.next_if(|&&(q, _)| q == p).map_or(0, |&(_, v)| v);
if w > taken {
raised[p as usize] = true;
}
}
}
(0..self.places)
.map(|p| if raised[p] { u32::MAX } else { self.initial[p] })
.collect()
}
fn refutation(&self, weights: &[(u32, i64)]) -> Refutation {
let mut weight = vec![0; self.places];
for &(p, w) in weights {
weight[p as usize] = w;
}
let tickets = &weight[self.places - self.once.len()..];
let atoms = self
.place_of
.iter()
.enumerate()
.filter(|&(_, &p)| p != u32::MAX && weight[p as usize] != 0)
.map(|(a, &p)| (Atom::new(a as u32), weight[p as usize]))
.collect();
let mut clauses: Vec<(OccId, i64)> = self
.once
.iter()
.zip(tickets)
.filter(|&(_, &w)| w != 0)
.flat_map(|(class, &w)| class.iter().map(move |&clause| (clause, w)))
.collect();
clauses.sort_unstable();
let mut dropped = self.dropped.clone();
dropped.sort_unstable();
Refutation::StateEquation(StateEquation {
atoms,
clauses,
dropped,
})
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
enum Clause {
Reusable(OccId),
Once(u32),
}
#[derive(Default)]
struct Parents(Vec<u64>);
impl Parents {
const ROOT: u32 = u32::MAX;
fn len(&self) -> usize {
self.0.len()
}
fn room(&mut self, charged: &mut Charged<'_>) -> bool {
reach::room(&mut self.0, 1, charged)
}
fn push(&mut self, parent: u32, transition: u32) {
self.0.push(u64::from(parent) << 32 | u64::from(transition));
}
fn up(&self, mut i: u32) -> Vec<u32> {
let mut transitions = Vec::new();
loop {
let parent = self.0[i as usize];
if (parent >> 32) as u32 == Self::ROOT {
return transitions;
}
transitions.push(parent as u32);
i = (parent >> 32) as u32;
}
}
}
#[derive(Clone, Copy, Debug)]
struct Transition {
clause: Clause,
inputs: u32,
outputs: u32,
end: u32,
}
impl Transition {
fn inputs_in(self, arcs: &[(u32, u32)]) -> &[(u32, u32)] {
&arcs[self.inputs as usize..self.outputs as usize]
}
fn outputs_in(self, arcs: &[(u32, u32)]) -> &[(u32, u32)] {
&arcs[self.outputs as usize..self.end as usize]
}
}
pub(super) struct Program {
places: usize,
place_of: Vec<u32>,
transitions: Vec<Transition>,
arcs: Vec<(u32, u32)>,
initial: Vec<u32>,
target: Vec<u32>,
body: Sign,
quests: Vec<OccId>,
markings: Vec<OccId>,
goal: OccId,
once: Vec<Vec<OccId>>,
alike: Vec<Vec<OccId>>,
dropped: Vec<OccId>,
}
impl Program {
fn of<'t>(task: &'t Task<'_>) -> Option<&'t Self> {
task.program
.get_or_init(|| {
Self::read(task).map(|mut program| {
live(&mut program);
program
})
})
.as_ref()
}
fn read(task: &Task<'_>) -> Option<Self> {
[Sign::Atom, Sign::Dual]
.into_iter()
.find_map(|body| Self::read_with(task, body))
}
fn read_with(task: &Task<'_>, body: Sign) -> Option<Self> {
let forest = task.forest;
let atoms = forest.sequent().atom_names().len();
let mut reader = Reader {
forest,
body,
place_of: vec![u32::MAX; atoms],
places: 0,
};
let mut reusable = Vec::new();
let mut once = Vec::new();
let mut quests = Vec::new();
let mut markings = Vec::new();
let mut goal = None;
let mut tokens = Vec::new();
for &member in task.goal {
if forest.kind(member) == Kind::Quest {
let clause = forest.left(member)?;
let (inputs, outputs, head) = reader.clause(clause)?;
head?;
reusable.push((clause, inputs, outputs));
quests.push(member);
} else if is_head(forest, reader.body, member) {
tokens.extend(reader.literals(member));
markings.push(member);
} else {
let (inputs, outputs, head) = reader.clause(member)?;
if head.is_some() {
once.push((member, inputs, outputs));
} else if goal.replace(member).is_some() {
return None;
}
}
}
let goal = goal?;
if let Some(reading) = task.reading
&& !task.goal.iter().all(|&member| {
let head = if member == goal {
None
} else if forest.kind(member) == Kind::Quest {
Some(reader.head_of(forest.left(member).unwrap()))
} else {
Some(reader.head_of(member))
};
forest.subtree(member).all(|x| {
let left = head.is_some_and(|h| forest.is_below(h, x) || forest.is_below(x, h));
reading.position(x) == if left { Side::Input } else { Side::Output }
})
})
{
return None;
}
let target_tokens = reader.clause(goal)?.0;
Some(reader.program(
Parts {
reusable,
once,
tokens,
target: target_tokens,
},
quests,
markings,
goal,
))
}
}
struct Parts {
reusable: Vec<(OccId, Vec<u32>, Vec<u32>)>,
once: Vec<(OccId, Vec<u32>, Vec<u32>)>,
tokens: Vec<u32>,
target: Vec<u32>,
}
struct Reader<'a> {
forest: &'a Forest,
body: Sign,
place_of: Vec<u32>,
places: u32,
}
impl Reader<'_> {
fn place(&mut self, literal: OccId) -> u32 {
let atom = self.forest.atom(literal).expect("a literal").index();
if self.place_of[atom] == u32::MAX {
self.place_of[atom] = self.places;
self.places += 1;
}
self.place_of[atom]
}
fn literals(&mut self, o: OccId) -> Vec<u32> {
let forest = self.forest;
forest
.subtree(o)
.filter(|&x| forest.is_literal(x))
.map(|x| self.place(x))
.collect()
}
fn clause(&mut self, clause: OccId) -> Option<(Vec<u32>, Vec<u32>, Option<OccId>)> {
let forest = self.forest;
let (mut inputs, mut head) = (Vec::new(), None);
let mut factors = vec![clause];
while let Some(x) = factors.pop() {
match forest.kind(x) {
Kind::Tensor => factors.extend(forest.children(x)),
Kind::One => {}
_ if forest.sign(x) == Some(self.body) => inputs.push(self.place(x)),
_ if head.is_none() && is_head(forest, self.body, x) => head = Some(x),
_ => return None,
}
}
let outputs = head.map_or_else(Vec::new, |h| self.literals(h));
Some((inputs, outputs, head))
}
fn head_of(&self, clause: OccId) -> OccId {
clause_head(self.forest, self.body, clause)
.flatten()
.unwrap_or(clause)
}
fn program(
self,
parts: Parts,
quests: Vec<OccId>,
markings: Vec<OccId>,
goal: OccId,
) -> Program {
fn weights(mut places: Vec<u32>) -> Vec<(u32, u32)> {
places.sort_unstable();
let mut arcs: Vec<(u32, u32)> = Vec::new();
for p in places {
match arcs.last_mut() {
Some((q, w)) if *q == p => *w += 1,
_ => arcs.push((p, 1)),
}
}
arcs
}
let Reader {
place_of,
places,
body,
..
} = self;
let mut seen: HashMap<(Arcs, Arcs), u32> = HashMap::default();
let mut transitions = Vec::new();
let mut arcs = Vec::new();
let mut push = |clause, inputs: &[(u32, u32)], outputs: &[(u32, u32)]| {
let at = |arcs: &Vec<(u32, u32)>| u32::try_from(arcs.len()).expect("arcs are literals");
let inputs_at = at(&arcs);
arcs.extend_from_slice(inputs);
let outputs_at = at(&arcs);
arcs.extend_from_slice(outputs);
transitions.push(Transition {
clause,
inputs: inputs_at,
outputs: outputs_at,
end: at(&arcs),
});
};
let mut alike: Vec<Vec<OccId>> = Vec::new();
for (clause, inputs, outputs) in parts.reusable {
let (inputs, outputs) = (weights(inputs), weights(outputs));
if inputs == outputs {
continue;
}
match seen.get(&(inputs.clone(), outputs.clone())) {
Some(&t) => alike[t as usize].push(clause),
None => {
push(Clause::Reusable(clause), &inputs, &outputs);
seen.insert((inputs, outputs), alike.len() as u32);
alike.push(Vec::new());
}
}
}
seen.clear();
let mut once: Vec<Vec<OccId>> = Vec::new();
let mut classes = Vec::new();
for (clause, inputs, outputs) in parts.once {
let key = (weights(inputs), weights(outputs));
let class = *seen.entry(key.clone()).or_insert_with(|| {
once.push(Vec::new());
classes.push(key);
once.len() as u32 - 1
});
once[class as usize].push(clause);
}
let ticket = |class: usize| places + class as u32;
for (class, (inputs, outputs)) in classes.iter().enumerate() {
let mut inputs = inputs.clone();
inputs.push((ticket(class), 1));
push(Clause::Once(class as u32), &inputs, outputs);
}
let width = places as usize + once.len();
let mut initial = vec![0; width];
for p in parts.tokens {
initial[p as usize] += 1;
}
for (class, clauses) in once.iter().enumerate() {
initial[ticket(class) as usize] = clauses.len() as u32;
}
let mut target = vec![0; width];
for p in parts.target {
target[p as usize] += 1;
}
Program {
places: width,
place_of,
transitions,
arcs,
initial,
target,
body,
quests,
markings,
goal,
once,
alike,
dropped: Vec::new(),
}
}
}
fn live(program: &mut Program) {
let Program {
transitions,
arcs,
initial,
once,
alike,
dropped,
..
} = program;
let width = initial.len();
let mut marked: Vec<bool> = initial.iter().map(|&count| count > 0).collect();
let mut waiting: Vec<u32> = Vec::with_capacity(transitions.len());
let mut by_input: Vec<Vec<u32>> = vec![Vec::new(); width];
let mut ready = Vec::new();
for (t, transition) in transitions.iter().enumerate() {
let unmarked = transition
.inputs_in(arcs)
.iter()
.filter(|&&(p, _)| !marked[p as usize])
.inspect(|&&(p, _)| by_input[p as usize].push(t as u32))
.count();
waiting.push(unmarked as u32);
if unmarked == 0 {
ready.push(t as u32);
}
}
let mut enabled = vec![false; transitions.len()];
while let Some(t) = ready.pop() {
enabled[t as usize] = true;
let transition = transitions[t as usize];
for &(p, _) in transition.outputs_in(arcs) {
if !marked[p as usize] {
marked[p as usize] = true;
for &u in &by_input[p as usize] {
waiting[u as usize] -= 1;
if waiting[u as usize] == 0 {
ready.push(u);
}
}
}
}
}
for (t, transition) in transitions.iter().enumerate() {
if enabled[t] {
continue;
}
match transition.clause {
Clause::Reusable(clause) => {
dropped.push(clause);
dropped.extend_from_slice(&alike[t]);
}
Clause::Once(class) => dropped.extend_from_slice(&once[class as usize]),
}
}
*alike = Vec::new();
let mut t = 0;
transitions.retain(|_| {
t += 1;
enabled[t - 1]
});
}
pub(crate) fn is_head(forest: &Forest, body: Sign, o: OccId) -> bool {
forest.subtree(o).all(|x| match forest.kind(x) {
Kind::Par | Kind::Bot => true,
_ => forest.sign(x) == Some(!body),
})
}
#[expect(
clippy::option_option,
reason = "no clause, or a clause with or without a head: the goal has none"
)]
pub(crate) fn clause_head(forest: &Forest, body: Sign, clause: OccId) -> Option<Option<OccId>> {
let mut head = None;
let mut factors = vec![clause];
while let Some(x) = factors.pop() {
match forest.kind(x) {
Kind::Tensor => factors.extend(forest.children(x)),
Kind::One => {}
_ if forest.sign(x) == Some(body) => {}
_ if head.is_none() && is_head(forest, body, x) => head = Some(x),
_ => return None,
}
}
Some(head)
}