use super::equation::Equation;
use super::reach::room;
use super::{Parents, Program};
use crate::hash::HashMap;
use crate::linear::search::memory::{Account, Charged};
use crate::linear::search::{Reason, Statistics};
use std::cell::RefCell;
use std::cmp::Reverse;
use std::collections::BinaryHeap;
pub(super) fn search(
program: &Program,
account: &Account,
most: usize,
equation: &mut Equation<'_>,
stop: &mut dyn FnMut(u64) -> bool,
) -> (Result<Option<Vec<u32>>, Reason>, Statistics) {
let mut search = Cover::new(program, account);
let result = search.run(most, equation, stop);
let statistics = Statistics {
nodes: search.computed,
memo_hits: search.covered,
memo_entries: search.parents.len() as u64,
..Statistics::default()
};
(result, statistics)
}
struct Cover<'a> {
program: &'a Program,
entries: Vec<(u32, u32)>,
ends: Vec<usize>,
sums: Vec<u64>,
parents: Parents,
edges: HashMap<(u32, u32), u32>,
listed: Vec<u32>,
first_child: Vec<u32>,
sibling: Vec<u32>,
place_of_node: Vec<u32>,
children: Vec<u32>,
after: Vec<u32>,
stack: RefCell<Vec<(u32, u32)>>,
queue: BinaryHeap<Reverse<(u64, u32)>>,
starts: Vec<u32>,
by_output: Vec<u32>,
tried: Vec<u32>,
probe: Vec<u32>,
position: Vec<u32>,
next: Vec<(u32, u32)>,
charged: Charged<'a>,
computed: u64,
covered: u64,
work: u64,
}
impl<'a> Cover<'a> {
fn new(program: &'a Program, account: &'a Account) -> Self {
let width = program.places;
let mut starts = vec![0u32; width + 1];
for transition in &program.transitions {
for &(p, _) in program.outputs(transition) {
starts[p as usize + 1] += 1;
}
}
for p in 0..width {
starts[p + 1] += starts[p];
}
let mut next = starts.clone();
let mut by_output = vec![0; starts[width] as usize];
for (t, transition) in program.transitions.iter().enumerate() {
for &(p, _) in program.outputs(transition) {
by_output[next[p as usize] as usize] = t as u32;
next[p as usize] += 1;
}
}
Self {
program,
entries: Vec::new(),
ends: Vec::new(),
sums: Vec::new(),
parents: Parents::default(),
edges: HashMap::default(),
listed: vec![0],
first_child: vec![0],
sibling: vec![0],
place_of_node: vec![0],
children: vec![0],
after: Vec::new(),
stack: RefCell::new(Vec::new()),
queue: BinaryHeap::new(),
starts,
by_output,
tried: vec![0; program.transitions.len()],
probe: vec![0; width],
position: vec![0; width],
next: Vec::new(),
charged: Charged::new(account),
computed: 0,
covered: 0,
work: 0,
}
}
fn run(
&mut self,
most: usize,
equation: &mut Equation<'_>,
stop: &mut dyn FnMut(u64) -> bool,
) -> Result<Option<Vec<u32>>, Reason> {
let program = self.program;
self.next.clear();
for (p, &count) in program.target.iter().enumerate() {
if count > 0 {
self.next.push((p as u32, count));
}
}
if self.below_initial() {
return Ok(Some(Vec::new()));
}
self.keep(Parents::ROOT, 0, most)?;
while let Some(Reverse((_, e))) = self.queue.pop() {
if stop(1) {
return Err(Reason::Stopped);
}
let budget = equation.budget(self.work);
if equation.wants(budget) && equation.run(program, budget, stop)? {
return Ok(None);
}
let (start, end) = self.span(e);
load(
&mut self.probe,
&mut self.position,
&self.entries[start..end],
false,
);
let (superseded, compared) = self.dominated(&self.entries[start..end], e);
load(
&mut self.probe,
&mut self.position,
&self.entries[start..end],
true,
);
self.work += compared;
if superseded {
continue;
}
for i in start..end {
let p = self.entries[i].0 as usize;
for k in self.starts[p]..self.starts[p + 1] {
let t = self.by_output[k as usize];
if self.tried[t as usize] == e + 1 {
continue;
}
self.tried[t as usize] = e + 1;
if stop(1) {
return Err(Reason::Stopped);
}
self.computed += 1;
self.before(e, t)?;
if self.below_initial() {
let mut firings = vec![t];
firings.extend(self.path(e));
return Ok(Some(firings));
}
load(&mut self.probe, &mut self.position, &self.next, false);
let (dominated, compared) = self.dominated(&self.next, u32::MAX);
load(&mut self.probe, &mut self.position, &self.next, true);
self.work += 1 + compared;
if dominated {
self.covered += 1;
} else {
match self.keep(e, t, most) {
Err(Reason::MemoryLimit { .. }) if equation.release() => {
self.keep(e, t, most)?;
}
kept => kept?,
}
}
}
}
}
Ok(None)
}
fn span(&self, e: u32) -> (usize, usize) {
let e = e as usize;
(if e == 0 { 0 } else { self.ends[e - 1] }, self.ends[e])
}
fn before(&mut self, e: u32, t: u32) -> Result<(), Reason> {
let program = self.program;
let transition = &program.transitions[t as usize];
let outputs = program.outputs(transition);
let inputs = program.inputs(transition);
let (start, end) = self.span(e);
let element = &self.entries[start..end];
self.next.clear();
let (mut i, mut j, mut o) = (0, 0, 0);
while i < element.len() || j < inputs.len() {
let p = match (element.get(i), inputs.get(j)) {
(Some(&(a, _)), Some(&(b, _))) => a.min(b),
(Some(&(a, _)), None) => a,
(None, Some(&(b, _))) => b,
(None, None) => unreachable!("the loop's condition"),
};
let mut count = 0;
if let Some(&(a, c)) = element.get(i)
&& a == p
{
i += 1;
while o < outputs.len() && outputs[o].0 < p {
o += 1;
}
let given = match outputs.get(o) {
Some(&(q, w)) if q == p => w,
_ => 0,
};
count = c.saturating_sub(given);
}
if let Some(&(b, w)) = inputs.get(j)
&& b == p
{
j += 1;
count = count.checked_add(w).ok_or(Reason::IndexLimit)?;
}
if count > 0 {
self.next.push((p, count));
}
}
Ok(())
}
fn below_initial(&self) -> bool {
self.next
.iter()
.all(|&(p, c)| c <= self.program.initial[p as usize])
}
fn dominated(&self, marking: &[(u32, u32)], except: u32) -> (bool, u64) {
let tokens: u64 = marking.iter().map(|&(_, c)| u64::from(c)).sum();
let mut looked = 0;
let mut stack = self.stack.borrow_mut();
stack.clear();
stack.push((0, 0));
while let Some((node, from)) = stack.pop() {
looked += 1;
let mut listed = self.listed[node as usize];
while listed != 0 {
let b = listed - 1;
if b != except && self.sums[b as usize] <= tokens {
looked += 1;
let (start, end) = self.span(b);
if self.entries[start..end]
.iter()
.all(|&(q, c)| self.probe[q as usize] >= c)
{
return (true, looked);
}
}
listed = self.after[b as usize];
}
let rest = marking.len() - from as usize;
let children = self.children[node as usize] as usize;
if children <= rest {
looked += children as u64;
let mut next = self.first_child[node as usize];
while next != 0 {
let child = next - 1;
let at = self.position[self.place_of_node[child as usize] as usize];
if at > from {
stack.push((child, at));
}
next = self.sibling[child as usize];
}
} else {
looked += rest as u64;
for (i, &(p, _)) in marking.iter().enumerate().skip(from as usize) {
if let Some(&child) = self.edges.get(&(node, p)) {
stack.push((child, i as u32 + 1));
}
}
}
}
(false, looked)
}
fn keep(&mut self, parent: u32, transition: u32, most: usize) -> Result<(), Reason> {
let index = self.parents.len();
if index >= most {
return Err(Reason::IndexLimit);
}
let more = self.next.len();
if self.listed.len() + more >= u32::MAX as usize {
return Err(Reason::IndexLimit);
}
if !room(&mut self.entries, more, &mut self.charged)
|| !room(&mut self.ends, 1, &mut self.charged)
|| !room(&mut self.sums, 1, &mut self.charged)
|| !self.parents.room(&mut self.charged)
|| !room(&mut self.listed, more, &mut self.charged)
|| !room(&mut self.first_child, more, &mut self.charged)
|| !room(&mut self.sibling, more, &mut self.charged)
|| !room(&mut self.place_of_node, more, &mut self.charged)
|| !room(&mut self.children, more, &mut self.charged)
|| !room(&mut self.after, 1, &mut self.charged)
|| !self.room_in_edges(more)
|| !self.room_in_queue()
{
return Err(Reason::MemoryLimit {
limit_bytes: self.charged.account().limit(),
});
}
self.entries.extend_from_slice(&self.next);
self.ends.push(self.entries.len());
let tokens = self.next.iter().map(|&(_, c)| u64::from(c)).sum();
self.sums.push(tokens);
self.parents.push(parent, transition);
let index = index as u32;
let mut node = 0;
for &(p, _) in &self.next {
node = match self.edges.get(&(node, p)) {
Some(&child) => child,
None => {
let child = self.listed.len() as u32;
self.edges.insert((node, p), child);
self.listed.push(0);
self.first_child.push(0);
self.sibling.push(self.first_child[node as usize]);
self.first_child[node as usize] = child + 1;
self.place_of_node.push(p);
self.children.push(0);
self.children[node as usize] += 1;
child
}
};
}
self.after.push(self.listed[node as usize]);
self.listed[node as usize] = index + 1;
self.queue.push(Reverse((tokens, index)));
Ok(())
}
fn room_in_edges(&mut self, more: usize) -> bool {
let slot = size_of::<((u32, u32), u32)>() + 1;
if self.edges.capacity() - self.edges.len() >= more {
return true;
}
let before = self.edges.capacity() * slot;
let wanted = self
.edges
.len()
.checked_add(more)
.map(|needed| needed.max(2 * self.edges.capacity()));
let fits = wanted
.and_then(|wanted| wanted.checked_mul(2 * slot))
.is_some_and(|bytes| self.charged.account().fits(bytes.saturating_sub(before)));
let (true, Some(wanted)) = (fits, wanted) else {
return false;
};
self.edges.reserve(wanted - self.edges.len());
self.charged.resize(before, self.edges.capacity() * slot);
true
}
fn room_in_queue(&mut self) -> bool {
let size = size_of::<Reverse<(u64, u32)>>();
if self.queue.len() < self.queue.capacity() {
return true;
}
let more = self.queue.capacity().max(16);
let fits = more
.checked_mul(size)
.is_some_and(|bytes| self.charged.account().fits(bytes));
if !fits {
return false;
}
let before = self.queue.capacity() * size;
self.queue.reserve_exact(more);
self.charged.resize(before, self.queue.capacity() * size);
true
}
fn path(&self, e: u32) -> Vec<u32> {
self.parents.up(e)
}
}
fn load(counts: &mut [u32], position: &mut [u32], marking: &[(u32, u32)], clear: bool) {
for (i, &(p, c)) in marking.iter().enumerate() {
(counts[p as usize], position[p as usize]) = if clear { (0, 0) } else { (c, i as u32 + 1) };
}
}