use super::rules::{Partner, Shape, Step};
use crate::linear::occurrences::{Member, OccId};
use crate::linear::proofs::{Node, NodeId};
#[derive(Clone, Debug, Default, PartialEq, Eq)]
pub(super) struct Zone {
pub(super) gamma: Vec<OccId>,
pub(super) theta: Vec<OccId>,
pub(super) top: bool,
pub(super) outputs: u64,
pub(super) node: Option<NodeId>,
}
pub(super) fn insert(list: &mut Vec<OccId>, o: OccId) {
let at = list.partition_point(|&x| x <= o);
list.insert(at, o);
}
fn remove(list: &mut Vec<OccId>, o: OccId) -> bool {
match list.binary_search(&o) {
Ok(at) => {
list.remove(at);
true
}
Err(_) => false,
}
}
fn sum(into: &mut Vec<OccId>, from: &[OccId]) {
if from.is_empty() {
return;
}
let mut merged = Vec::with_capacity(into.len() + from.len());
let (mut i, mut j) = (0, 0);
while i < into.len() && j < from.len() {
if into[i] <= from[j] {
merged.push(into[i]);
i += 1;
} else {
merged.push(from[j]);
j += 1;
}
}
merged.extend_from_slice(&into[i..]);
merged.extend_from_slice(&from[j..]);
*into = merged;
}
fn union(into: &mut Vec<OccId>, from: &[OccId]) {
for &o in from {
if let Err(at) = into.binary_search(&o) {
into.insert(at, o);
}
}
}
pub(super) fn excess(of: &[OccId], within: &[OccId]) -> Vec<OccId> {
let mut out = Vec::new();
let mut j = 0;
for &o in of {
while j < within.len() && within[j] < o {
j += 1;
}
if j < within.len() && within[j] == o {
j += 1;
} else {
out.push(o);
}
}
out
}
pub(super) fn within(small: &[OccId], large: &[OccId]) -> bool {
let mut j = 0;
for &o in small {
while j < large.len() && large[j] < o {
j += 1;
}
if j == large.len() || large[j] != o {
return false;
}
j += 1;
}
true
}
pub(super) struct Calculus<'s, 'a> {
pub(super) shape: &'s Shape<'a>,
}
impl Calculus<'_, '_> {
fn shaped(&self, z: &Zone) -> bool {
self.shape.reading.is_none() || z.outputs == 1 || (z.outputs == 0 && z.top)
}
fn add(&self, z: &mut Zone, o: OccId) {
insert(&mut z.gamma, o);
z.outputs += u64::from(self.shape.output(o));
}
fn weaken(&self, z: &mut Zone, o: OccId, nodes: &mut Option<&mut Vec<Node>>) -> bool {
if !self.shape.affine || self.shape.output(o) {
return false;
}
if let (Some(nodes), Some(n)) = (nodes.as_deref_mut(), z.node) {
z.node = Some(push(nodes, Node::Weaken(Member::from(o), n)));
}
true
}
pub(super) fn weaken_in(&self, z: &mut Zone, o: OccId, nodes: &mut Vec<Node>) -> bool {
if !self.weaken(z, o, &mut Some(nodes)) {
return false;
}
self.add(z, o);
true
}
fn take(&self, z: &mut Zone, o: OccId, nodes: &mut Option<&mut Vec<Node>>) -> bool {
if remove(&mut z.gamma, o) {
z.outputs -= u64::from(self.shape.output(o));
return true;
}
if z.top {
return !(self.shape.output(o) && z.outputs > 0);
}
self.weaken(z, o, nodes)
}
fn join(
&self,
mut l: Zone,
mut r: Zone,
nodes: &mut Option<&mut Vec<Node>>,
) -> Option<(Zone, Option<(NodeId, NodeId)>)> {
let mut most = l.gamma.clone();
sum(&mut most, &excess(&r.gamma, &l.gamma));
let gamma = match (l.top, r.top) {
(true, true) => most,
(false, false) if l.gamma == r.gamma => most,
(true, false) if within(&l.gamma, &r.gamma) => most,
(false, true) if within(&r.gamma, &l.gamma) => most,
_ if self.shape.affine => {
for side in [&mut l, &mut r] {
if !side.top {
for o in excess(&most, &side.gamma) {
if !self.weaken(side, o, nodes) {
return None;
}
}
}
}
most
}
_ => return None,
};
let mut theta = l.theta;
union(&mut theta, &r.theta);
let outputs = gamma.iter().map(|&o| u64::from(self.shape.output(o))).sum();
let zone = Zone {
gamma,
theta,
top: l.top && r.top,
outputs,
node: None,
};
Some((zone, l.node.zip(r.node)))
}
pub(super) fn derive(
&self,
steps: &[Step],
premise: &mut dyn FnMut(u32, &mut Zone),
partner: &dyn Fn(u32) -> Partner,
mut nodes: Option<&mut Vec<Node>>,
stack: &mut Vec<Zone>,
units: &mut u64,
) -> Option<Zone> {
let forest = self.shape.forest;
stack.clear();
for &step in steps {
let z = match step {
Step::Axiom(p, slot) => {
let Partner { x, theta } = partner(slot);
let mut z = Zone::default();
self.add(&mut z, p);
let ax = nodes
.as_deref_mut()
.map(|n| push(n, Node::Ax(Member::from(p), Member::from(x))));
if theta {
z.theta.push(x);
z.node = ax
.zip(nodes.as_deref_mut())
.map(|(a, n)| push(n, Node::Copy(Member::from(x), a)));
} else {
self.add(&mut z, x);
z.node = ax;
}
z
}
Step::One(o) => {
let mut z = Zone::default();
self.add(&mut z, o);
z.node = nodes
.as_deref_mut()
.map(|n| push(n, Node::One(Member::from(o))));
z
}
Step::Top(o) => {
let mut z = Zone::default();
self.add(&mut z, o);
z.top = true;
z.node = nodes
.as_deref_mut()
.map(|n| push(n, Node::Top(Member::from(o))));
z
}
Step::Hole(h) => {
let mut z = Zone::default();
premise(h, &mut z);
z
}
Step::Tensor(o) => {
let mut r = stack.pop()?;
let mut l = stack.pop()?;
let (a, b) = (forest.left(o)?, forest.right(o)?);
if !self.take(&mut l, a, &mut nodes) || !self.take(&mut r, b, &mut nodes) {
return None;
}
sum(&mut l.gamma, &r.gamma);
union(&mut l.theta, &r.theta);
l.top |= r.top;
l.outputs += r.outputs;
l.node = match (nodes.as_deref_mut(), l.node, r.node) {
(Some(n), Some(x), Some(y)) => {
Some(push(n, Node::Tensor(Member::from(o), x, y)))
}
_ => None,
};
self.add(&mut l, o);
l
}
Step::Plus(o, side) => {
let mut z = stack.pop()?;
let child = match side {
crate::linear::proofs::Branch::Left => forest.left(o)?,
crate::linear::proofs::Branch::Right => forest.right(o)?,
};
if !self.take(&mut z, child, &mut nodes) {
return None;
}
z.node = wrap(&mut nodes, z.node, |n| Node::Plus(Member::from(o), side, n));
self.add(&mut z, o);
z
}
Step::Bang(o) => {
let mut z = stack.pop()?;
if !self.take(&mut z, forest.left(o)?, &mut nodes) || !z.gamma.is_empty() {
return None;
}
z.top = false;
z.outputs = 0;
z.node = wrap(&mut nodes, z.node, |n| Node::Bang(Member::from(o), n));
self.add(&mut z, o);
z
}
Step::Par(o) => {
let mut z = stack.pop()?;
let (a, b) = (forest.left(o)?, forest.right(o)?);
if !self.take(&mut z, a, &mut nodes) || !self.take(&mut z, b, &mut nodes) {
return None;
}
z.node = wrap(&mut nodes, z.node, |n| Node::Par(Member::from(o), n));
self.add(&mut z, o);
z
}
Step::Bot(o) => {
let mut z = stack.pop()?;
z.node = wrap(&mut nodes, z.node, |n| Node::Bot(Member::from(o), n));
self.add(&mut z, o);
z
}
Step::With(o) => {
let mut r = stack.pop()?;
let mut l = stack.pop()?;
let (a, b) = (forest.left(o)?, forest.right(o)?);
if !self.take(&mut l, a, &mut nodes) || !self.take(&mut r, b, &mut nodes) {
return None;
}
let (mut z, premises) = self.join(l, r, &mut nodes)?;
z.node = match (nodes.as_deref_mut(), premises) {
(Some(n), Some((x, y))) => Some(push(n, Node::With(Member::from(o), x, y))),
_ => None,
};
self.add(&mut z, o);
z
}
Step::Quest(o) => {
let mut z = stack.pop()?;
let a = forest.left(o)?;
if let Ok(at) = z.theta.binary_search(&a) {
z.theta.remove(at);
}
z.node = wrap(&mut nodes, z.node, |n| Node::Quest(Member::from(o), n));
self.add(&mut z, o);
z
}
Step::Copy(o) => {
let mut z = stack.pop()?;
if !self.take(&mut z, o, &mut nodes) {
return None;
}
if let Err(at) = z.theta.binary_search(&o) {
z.theta.insert(at, o);
}
z.node = wrap(&mut nodes, z.node, |n| Node::Copy(Member::from(o), n));
z
}
};
*units += 1 + z.gamma.len() as u64;
if !self.shaped(&z) {
return None;
}
stack.push(z);
}
let z = stack.pop()?;
debug_assert!(stack.is_empty(), "a rule's term has one root");
Some(z)
}
pub(super) fn mix(&self, l: &Zone, r: &Zone, nodes: Option<&mut Vec<Node>>) -> Option<Zone> {
let mut z = l.clone();
sum(&mut z.gamma, &r.gamma);
union(&mut z.theta, &r.theta);
z.top |= r.top;
z.outputs += r.outputs;
z.node = match (nodes, l.node, r.node) {
(Some(n), Some(a), Some(b)) => Some(push(n, Node::Mix(a, b))),
_ => None,
};
Some(z)
}
}
fn push(nodes: &mut Vec<Node>, node: Node) -> NodeId {
let id = NodeId::new(u32::try_from(nodes.len()).expect("a proof has fewer than 2³² nodes"));
nodes.push(node);
id
}
fn wrap(
nodes: &mut Option<&mut Vec<Node>>,
premise: Option<NodeId>,
rule: impl FnOnce(NodeId) -> Node,
) -> Option<NodeId> {
match (nodes.as_deref_mut(), premise) {
(Some(n), Some(p)) => Some(push(n, rule(p))),
_ => None,
}
}