use super::super::Reason;
use super::super::memory::{Charged, bytes_of};
use crate::hash::HashMap;
use crate::linear::occurrences::{Forest, OccId, Reading, Side};
use crate::linear::proofs::Branch;
use crate::linear::sequents::Kind;
use std::ops::Range;
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(super) enum Step {
Axiom(OccId, u32),
One(OccId),
Top(OccId),
Hole(u32),
Tensor(OccId),
Plus(OccId, Branch),
Bang(OccId),
Par(OccId),
Bot(OccId),
With(OccId),
Quest(OccId),
Copy(OccId),
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(super) struct Partner {
pub(super) x: OccId,
pub(super) theta: bool,
}
#[derive(Clone, Debug)]
pub(super) struct Rule {
pub(super) steps: Range<u32>,
pub(super) holes: Range<u32>,
pub(super) slots: Range<u32>,
}
#[derive(Clone, Debug)]
pub(super) struct Hole {
pub(super) rule: u32,
pub(super) index: u32,
pub(super) group: u32,
pub(super) leaves: Range<u32>,
pub(super) theta: Range<u32>,
}
#[derive(Debug, Default)]
pub(super) struct Rules {
pub(super) all: Vec<Rule>,
pub(super) steps: Vec<Step>,
pub(super) holes: Vec<Hole>,
pub(super) leaves: Vec<OccId>,
pub(super) slots: Vec<Range<u32>>,
pub(super) partners: Vec<Partner>,
lists: HashMap<(OccId, OccId), Range<u32>>,
pub(super) by_leaf: HashMap<OccId, Vec<u32>>,
pub(super) open: Vec<u32>,
}
pub(super) struct Shape<'a> {
pub(super) forest: &'a Forest,
signs: Box<[crate::linear::occurrences::Sign]>,
pub(super) reading: Option<&'a Reading<'a>>,
pub(super) affine: bool,
pub(super) goal: Vec<OccId>,
pub(super) globals: Vec<OccId>,
}
impl<'a> Shape<'a> {
pub(super) fn new(
forest: &'a Forest,
goal: &[OccId],
signs: Box<[crate::linear::occurrences::Sign]>,
reading: Option<&'a Reading<'a>>,
affine: bool,
) -> Self {
let mut members = goal.to_vec();
members.sort_unstable();
let mut globals = Vec::new();
let mut walk = members.clone();
while let Some(o) = walk.pop() {
match forest.kind(o) {
Kind::Par => walk.extend(forest.children(o)),
Kind::Quest => globals.extend(forest.left(o)),
_ => {}
}
}
globals.sort_unstable();
globals.dedup();
Self {
forest,
signs,
reading,
affine,
goal: members,
globals,
}
}
pub(super) fn positive(&self, o: OccId) -> bool {
match self.forest.kind(o) {
Kind::Tensor | Kind::One | Kind::Plus | Kind::Zero | Kind::Bang | Kind::Exists => true,
Kind::Atom | Kind::DualAtom => {
let atom = self.forest.atom(o).expect("a literal has an atom");
self.forest.sign(o) == Some(self.signs[atom.index()])
}
Kind::Par | Kind::Bot | Kind::With | Kind::Top | Kind::Quest | Kind::Forall => false,
}
}
fn stable(&self, o: OccId) -> bool {
self.positive(o) || self.forest.is_literal(o)
}
pub(super) fn coherent(&self, x: OccId, y: OccId) -> bool {
coherent(self.forest, x, y)
}
pub(super) fn output(&self, o: OccId) -> bool {
self.reading.is_some_and(|r| r.position(o) == Side::Output)
}
}
fn copied(forest: &Forest, o: OccId) -> bool {
let mut a = o;
while let Some(p) = forest.parent(a) {
if forest.kind(p) == Kind::Quest {
return true;
}
a = p;
}
false
}
pub(super) fn coherent(forest: &Forest, x: OccId, y: OccId) -> bool {
let Some(w) = forest.lca(x, y) else {
return true;
};
if forest.kind(w) == Kind::Quest || copied(forest, w) {
return true;
}
w != x && w != y && forest.kind(w) == Kind::Par
}
pub(super) fn coherent_list(forest: &Forest, sorted: &[OccId]) -> bool {
sorted.windows(2).all(|w| coherent(forest, w[0], w[1]))
}
enum Pending {
Focus(OccId),
Async(Phase),
Copy(OccId),
}
#[derive(Clone, Default)]
struct Phase {
top: Option<OccId>,
unary: Vec<OccId>,
withs: Vec<OccId>,
leaves: Vec<OccId>,
theta: Vec<OccId>,
group: u32,
}
impl Phase {
fn bytes(&self) -> usize {
bytes_of(&self.unary)
+ bytes_of(&self.withs)
+ bytes_of(&self.leaves)
+ bytes_of(&self.theta)
}
fn place(&mut self, shape: &Shape<'_>, o: OccId) {
if shape.stable(o) {
self.leaves.push(o);
return;
}
match shape.forest.kind(o) {
Kind::Top => {
self.top.get_or_insert(o);
}
Kind::With => self.withs.push(o),
_ => self.unary.push(o),
}
}
}
struct Writer<'s, 'a, 'c> {
shape: &'s Shape<'a>,
rules: Rules,
reversed: Vec<Step>,
holes: Vec<(Vec<OccId>, Vec<OccId>, u32)>,
slots: Vec<(OccId, OccId)>,
charged: &'s mut Charged<'c>,
held: usize,
unpolled: u64,
groups: u32,
pending: usize,
inner: usize,
}
const STEPS_PER_POLL: u64 = 1 << 12;
impl<'s, 'a, 'c> Writer<'s, 'a, 'c> {
fn settle(&mut self) -> Result<(), Reason> {
let r = &self.rules;
let held = bytes_of(&r.all)
+ bytes_of(&r.steps)
+ bytes_of(&r.holes)
+ bytes_of(&r.leaves)
+ bytes_of(&r.slots)
+ bytes_of(&r.partners)
+ r.by_leaf.capacity() * (size_of::<(OccId, Vec<u32>)>() + 1)
+ r.lists.capacity() * (size_of::<((OccId, OccId), Range<u32>)>() + 1)
+ bytes_of(&r.open)
+ bytes_of(&self.reversed)
+ bytes_of(&self.holes)
+ self.pending
+ self.inner;
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 tick(&mut self, stop: &mut dyn FnMut(u64) -> bool) -> Result<(), Reason> {
self.tick_by(1, stop)
}
fn tick_by(&mut self, units: u64, stop: &mut dyn FnMut(u64) -> bool) -> Result<(), Reason> {
self.unpolled += units;
if self.unpolled < STEPS_PER_POLL {
return Ok(());
}
self.settle()?;
if stop(std::mem::take(&mut self.unpolled)) {
return Err(Reason::Stopped);
}
Ok(())
}
fn write(
&mut self,
root: Pending,
sides: &[(OccId, Branch)],
anchor: OccId,
stop: &mut dyn FnMut(u64) -> bool,
) -> Result<(), Reason> {
let forest = self.shape.forest;
self.reversed.clear();
self.holes.clear();
self.slots.clear();
self.pending = 0;
self.groups = 0;
let mut stack = Vec::new();
self.push(&mut stack, root);
while let Some(pending) = stack.pop() {
self.tick(stop)?;
match pending {
Pending::Copy(o) => {
self.reversed.push(Step::Copy(o));
let next = self.under_focus(o);
self.push(&mut stack, next);
}
Pending::Focus(o) => match forest.kind(o) {
Kind::Tensor => {
self.reversed.push(Step::Tensor(o));
let (l, r) = (forest.left(o).expect("⊗"), forest.right(o).expect("⊗"));
let (l, r) = (self.under_focus(l), self.under_focus(r));
self.push(&mut stack, l);
self.push(&mut stack, r);
}
Kind::Plus => {
let side = sides
.iter()
.find(|&&(p, _)| p == o)
.map(|&(_, side)| side)
.expect("every ⊕ under the focus has a side");
self.reversed.push(Step::Plus(o, side));
let child = match side {
Branch::Left => forest.left(o),
Branch::Right => forest.right(o),
}
.expect("⊕");
let next = self.under_focus(child);
self.push(&mut stack, next);
}
Kind::One => self.reversed.push(Step::One(o)),
Kind::Bang => {
self.reversed.push(Step::Bang(o));
let mut phase = self.release();
phase.place(self.shape, forest.left(o).expect("!"));
self.push(&mut stack, Pending::Async(phase));
}
Kind::Atom | Kind::DualAtom => {
let slot = self.slots.len() as u32;
self.slots.push((o, anchor));
self.reversed.push(Step::Axiom(o, slot));
}
Kind::Zero
| Kind::Par
| Kind::Bot
| Kind::With
| Kind::Top
| Kind::Quest
| Kind::Forall
| Kind::Exists => {
unreachable!("a plan never focuses on a 0, a negative formula or a binder")
}
},
Pending::Async(mut phase) => {
self.pending -= phase.bytes();
loop {
if let Some(t) = phase.top {
self.reversed.push(Step::Top(t));
break;
}
if let Some(o) = phase.unary.pop() {
match forest.kind(o) {
Kind::Par => {
self.reversed.push(Step::Par(o));
for c in forest.children(o) {
phase.place(self.shape, c);
}
}
Kind::Bot => self.reversed.push(Step::Bot(o)),
Kind::Quest => {
self.reversed.push(Step::Quest(o));
phase.theta.push(forest.left(o).expect("?"));
}
_ => unreachable!("only ⅋, ⊥ and ? are unary in a phase"),
}
self.tick(stop)?;
continue;
}
if let Some(o) = phase.withs.pop() {
self.reversed.push(Step::With(o));
let mut left = phase.clone();
left.place(self.shape, forest.left(o).expect("&"));
phase.place(self.shape, forest.right(o).expect("&"));
self.push(&mut stack, Pending::Async(left));
self.tick(stop)?;
continue;
}
let index = self.holes.len() as u32;
phase.leaves.sort_unstable();
phase.theta.sort_unstable();
self.pending += bytes_of(&phase.leaves) + bytes_of(&phase.theta);
self.holes.push((phase.leaves, phase.theta, phase.group));
self.reversed.push(Step::Hole(index));
break;
}
}
}
}
self.record(stop)?;
self.settle()
}
fn push(&mut self, stack: &mut Vec<Pending>, pending: Pending) {
if let Pending::Async(phase) = &pending {
self.pending += phase.bytes();
}
stack.push(pending);
}
fn release(&mut self) -> Phase {
self.groups = self.groups.wrapping_add(1);
Phase {
group: self.groups.wrapping_sub(1),
..Phase::default()
}
}
fn under_focus(&mut self, o: OccId) -> Pending {
if self.shape.positive(o) {
Pending::Focus(o)
} else {
let mut phase = self.release();
phase.place(self.shape, o);
Pending::Async(phase)
}
}
fn record(&mut self, stop: &mut dyn FnMut(u64) -> bool) -> Result<(), Reason> {
let base_slot = self.rules.slots.len();
let slots = std::mem::take(&mut self.slots);
for &(p, anchor) in slots.iter().rev() {
let range = match self.rules.lists.get(&(p, anchor)) {
Some(range) => range.clone(),
None => {
let start = self.rules.partners.len() as u32;
let (found, scanned) = partners(self.shape, p, anchor);
self.rules.partners.extend(found);
let range = start..self.rules.partners.len() as u32;
self.rules.lists.insert((p, anchor), range.clone());
self.tick_by(scanned, stop)?;
range
}
};
if range.is_empty() {
self.rules.slots.truncate(base_slot);
self.holes.clear();
self.pending = 0;
return Ok(());
}
self.rules.slots.push(range);
}
let rule = self.rules.all.len() as u32;
let (holes, slots) = (self.holes.len() as u32, slots.len() as u32);
let hole_base = self.rules.holes.len() as u32;
let written = std::mem::take(&mut self.holes);
self.pending += bytes_of(&written);
for (index, (leaves, theta, group)) in written.into_iter().rev().enumerate() {
let start = self.rules.leaves.len() as u32;
self.rules.leaves.extend_from_slice(&leaves);
let mid = self.rules.leaves.len() as u32;
self.rules.leaves.extend_from_slice(&theta);
let end = self.rules.leaves.len() as u32;
let global = self.rules.holes.len() as u32;
match leaves.first() {
Some(&first) => {
let list = self.rules.by_leaf.entry(first).or_default();
let before = bytes_of(list);
list.push(global);
self.inner += bytes_of(list) - before;
}
None => self.rules.open.push(global),
}
self.rules.holes.push(Hole {
rule,
index: index as u32,
group,
leaves: start..mid,
theta: mid..end,
});
self.pending -= bytes_of(&leaves) + bytes_of(&theta);
self.tick_by(1 + (leaves.len() + theta.len()) as u64, stop)?;
}
self.pending = 0;
let step_base = self.rules.steps.len() as u32;
for i in (0..self.reversed.len()).rev() {
let step = self.reversed[i];
self.rules.steps.push(match step {
Step::Hole(h) => Step::Hole(holes - 1 - h),
Step::Axiom(p, s) => Step::Axiom(p, slots - 1 - s),
step => step,
});
self.tick(stop)?;
}
self.rules.all.push(Rule {
steps: step_base..self.rules.steps.len() as u32,
holes: hole_base..hole_base + holes,
slots: base_slot as u32..base_slot as u32 + slots,
});
let most = u32::MAX as usize;
let r = &self.rules;
if [
r.all.len(),
r.steps.len(),
r.holes.len(),
r.leaves.len(),
r.slots.len(),
r.partners.len(),
]
.into_iter()
.any(|len| len > most)
{
return Err(Reason::IndexLimit);
}
Ok(())
}
}
fn partners(shape: &Shape<'_>, p: OccId, anchor: OccId) -> (Vec<Partner>, u64) {
let forest = shape.forest;
let (atom, sign) = (
forest.atom(p).expect("a literal"),
forest.sign(p).expect("a literal"),
);
let mut found = Vec::new();
for &x in forest.literals(atom, !sign) {
if shape.reading.is_some() && shape.output(x) == shape.output(p) {
continue;
}
if !shape.coherent(anchor, x) {
continue;
}
let quest = forest
.parent(x)
.is_some_and(|q| forest.kind(q) == Kind::Quest);
if quest {
found.push(Partner { x, theta: true });
}
if !quest || shape.goal.binary_search(&x).is_ok() {
found.push(Partner { x, theta: false });
}
}
(found, forest.literals(atom, !sign).len() as u64)
}
fn plans(
shape: &Shape<'_>,
root: OccId,
mut each: impl FnMut(Option<&[(OccId, Branch)]>) -> Result<(), Reason>,
) -> Result<(), Reason> {
let forest = shape.forest;
let mut open = vec![Vec::new()];
'plans: while let Some(sides) = open.pop() {
each(None)?;
let mut walk = vec![root];
while let Some(o) = walk.pop() {
match forest.kind(o) {
Kind::Tensor => walk.extend(forest.children(o).filter(|&c| shape.positive(c))),
Kind::Plus => match sides.iter().find(|&&(p, _)| p == o) {
Some(&(_, side)) => {
let child = match side {
Branch::Left => forest.left(o),
Branch::Right => forest.right(o),
}
.expect("⊕");
if shape.positive(child) {
walk.push(child);
}
}
None => {
for side in [Branch::Right, Branch::Left] {
let mut more = sides.clone();
more.push((o, side));
open.push(more);
}
continue 'plans;
}
},
Kind::Zero => continue 'plans,
_ => {}
}
}
each(Some(&sides))?;
}
Ok(())
}
pub(super) fn compile(
shape: &Shape<'_>,
charged: &mut Charged<'_>,
stop: &mut dyn FnMut(u64) -> bool,
) -> Result<Rules, Reason> {
let forest = shape.forest;
let mut writer = Writer {
shape,
rules: Rules::default(),
reversed: Vec::new(),
holes: Vec::new(),
slots: Vec::new(),
charged,
held: 0,
unpolled: 0,
groups: 0,
pending: 0,
inner: 0,
};
let mut previous = None;
for &g in &shape.goal {
if previous.replace(g) == Some(g) {
continue;
}
for o in forest.subtree(g) {
let parent = forest.parent(o).filter(|_| o != g).map(|p| forest.kind(p));
let focus = shape.positive(o)
&& matches!(parent, None | Some(Kind::Par | Kind::With | Kind::Bang));
if focus {
plans(shape, o, |sides| match sides {
Some(sides) => writer.write(Pending::Focus(o), sides, o, stop),
None => writer.tick(stop),
})?;
}
let copied =
parent == Some(Kind::Quest) && !(forest.is_literal(o) && !shape.positive(o));
if copied {
plans(shape, o, |sides| match sides {
Some(sides) => writer.write(Pending::Copy(o), sides, o, stop),
None => writer.tick(stop),
})?;
}
}
}
writer.settle()?;
Ok(writer.rules)
}
pub(super) fn goal(
shape: &Shape<'_>,
charged: &mut Charged<'_>,
stop: &mut dyn FnMut(u64) -> bool,
) -> Result<Rules, Reason> {
let mut writer = Writer {
shape,
rules: Rules::default(),
reversed: Vec::new(),
holes: Vec::new(),
slots: Vec::new(),
charged,
held: 0,
unpolled: 0,
groups: 0,
pending: 0,
inner: 0,
};
let mut phase = writer.release();
for &o in &shape.goal {
phase.place(shape, o);
}
let anchor = shape.goal.first().copied().unwrap_or(OccId::new(0));
writer.write(Pending::Async(phase), &[], anchor, stop)?;
Ok(writer.rules)
}