use super::check::{
self, Allowance, CheckError, Facts, Framed, Ground, Instancing, Observer, State,
};
use super::{Branch, Derivation, Node, NodeId, Proof, ViewOptions};
use crate::limits::{Limits, Phase, Progress};
use crate::linear::fragment::Mode;
use crate::linear::occurrences::instances::{eigen_names, meta_name};
use crate::linear::occurrences::{Forest, Member, OccId, Reading, Side};
use crate::linear::sequents::{FoTerm, Kind, Term};
use std::collections::{HashMap, HashSet};
#[non_exhaustive]
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
#[cfg_attr(feature = "serialize", derive(serde::Serialize, serde::Deserialize))]
pub struct Size {
pub inferences: u64,
pub characters: u64,
pub height: u64,
pub width: u64,
pub exact: bool,
}
impl Size {
pub const BYTES_PER_CHARACTER: u64 = 8;
pub const BYTES_PER_INFERENCE: u64 = 128;
pub fn bytes(&self) -> u64 {
self.characters
.saturating_mul(Self::BYTES_PER_CHARACTER)
.saturating_add(self.inferences.saturating_mul(Self::BYTES_PER_INFERENCE))
}
pub fn lines(&self) -> u64 {
self.height.saturating_mul(2)
}
}
impl Proof {
pub fn derivation_size(
&self,
view: &ViewOptions,
limits: &Limits,
mut stop: impl FnMut(Progress) -> bool,
) -> Result<Size, CheckError> {
let mode = if view.two_sided(self) {
Derivation::two_sided_mode(self)
} else {
Derivation::ONE_SIDED
};
let reading = check::reading(self, mode)?;
let allowance = Allowance::new(limits, Phase::View, &mut stop);
measure(self, &self.conclusion(), mode, reading.as_ref(), allowance)
}
#[cfg(all(test, feature = "parse"))]
pub(crate) fn size_of(&self, two_sided: bool) -> Result<Size, CheckError> {
let sides = if two_sided {
super::Sides::Two
} else {
super::Sides::One
};
self.derivation_size(
&ViewOptions::default().with_sides(sides),
&Limits::default(),
|_| false,
)
}
}
#[derive(Clone, Copy, Debug, Default)]
struct Sub {
inferences: u64,
characters: u64,
reached: u64,
reached_goal: u64,
height: u64,
width: u64,
weight: u64,
goal: u64,
absorbs: bool,
firm: Firm,
}
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
pub(crate) struct Firm {
pub(crate) inferences: u64,
pub(crate) bytes: u64,
}
impl Firm {
fn and(self, characters: u64) -> Self {
Self {
inferences: self.inferences.saturating_add(1),
bytes: characters
.saturating_mul(Size::BYTES_PER_CHARACTER)
.saturating_add(Size::BYTES_PER_INFERENCE)
.saturating_add(self.bytes),
}
}
fn with(self, other: Self) -> Self {
Self {
inferences: self.inferences.saturating_add(other.inferences),
bytes: self.bytes.saturating_add(other.bytes),
}
}
}
struct Measure<'a, I> {
proof: &'a Proof,
inst: &'a I,
reading: Option<&'a Reading<'a>>,
weights: Weights,
subs: Vec<Sub>,
exact: bool,
}
pub(crate) fn weights(forest: &Forest) -> Vec<u32> {
let sequent = forest.sequent();
let names: Vec<u32> = sequent
.atom_names()
.iter()
.map(|name| u32::try_from(name.chars().count()).unwrap_or(u32::MAX))
.collect();
let mut top = Vec::<u32>::with_capacity(sequent.terms().len());
let mut inner = Vec::<u32>::with_capacity(sequent.terms().len());
for term in sequent.terms() {
use Term::*;
let (width, binary) = match *term {
Atom(a) => (names[a.index()], false),
DualAtom(a) => (names[a.index()].saturating_add(1), false),
One | Bot | Top | Zero => (1, false),
Tensor(k, l) | Par(k, l) | With(k, l) | Plus(k, l) => (
inner[k.index()]
.saturating_add(3)
.saturating_add(inner[l.index()]),
true,
),
Bang(k) | Quest(k) => (inner[k.index()].saturating_add(1), false),
Forall(_) | Exists(_) => return weights_with_binders(forest, &names),
};
top.push(width);
inner.push(if binary {
width.saturating_add(2)
} else {
width
});
}
forest
.ids()
.map(|o| top[forest.term(o).index()].saturating_add(2))
.collect()
}
fn printed_names(forest: &Forest) -> Vec<u32> {
let sequent = forest.sequent();
let symbols: HashSet<&str> = sequent.fo.symbols.iter().map(|(s, _)| s.as_str()).collect();
let mut open: HashMap<String, u32> = HashMap::new();
let mut scope: Vec<(usize, String)> = Vec::new();
let mut printed = vec![0u32; forest.len()];
for o in forest.ids() {
while let Some((end, _)) = scope.last()
&& *end <= o.index()
{
let (_, name) = scope.pop().expect("just seen");
if let Some(count) = open.get_mut(&name) {
*count -= 1;
if *count == 0 {
open.remove(&name);
}
}
}
if forest.kind(o).is_binder() {
let base = sequent.binder_name(forest.term(o)).unwrap_or("x");
let mut written = base.to_owned();
let mut n = 0u64;
while symbols.contains(written.as_str()) || open.contains_key(&written) {
n += 1;
written = format!("{base}_{n}");
}
printed[o.index()] = u32::try_from(written.chars().count()).unwrap_or(u32::MAX);
*open.entry(written.clone()).or_insert(0) += 1;
scope.push((o.index() + forest.size(o) as usize, written));
}
}
printed
}
fn weights_with_binders(forest: &Forest, names: &[u32]) -> Vec<u32> {
let sequent = forest.sequent();
let fo = &sequent.fo;
let printed = printed_names(forest);
let mut held: Vec<(Vec<(u32, u64)>, u64)> = Vec::with_capacity(fo.terms.len());
let gather = |held: &[(Vec<(u32, u64)>, u64)], args: &[crate::linear::sequents::FoTermId]| {
let mut uses: Vec<(u32, u64)> = Vec::new();
let mut keyed = 0u64;
for t in args {
let (more, k) = &held[t.index()];
keyed = keyed.saturating_add(*k);
merge(&mut uses, more.iter().copied());
}
(uses, keyed)
};
for term in &fo.terms {
let entry = match *term {
FoTerm::Bound(i) => (
vec![(i, 1)],
1 + u64::from(i.checked_ilog10().unwrap_or(0) + 1),
),
FoTerm::App(_, args) => gather(&held, fo.list(args)),
FoTerm::Eigen(_) | FoTerm::Meta(_) => (Vec::new(), 0),
};
held.push(entry);
}
let enclosing = enclosing_binders(forest);
let name_of = |b: OccId| printed[b.index()];
let mut top = vec![0u32; forest.len()];
let mut inner = vec![0u32; forest.len()];
for o in forest.ids().rev() {
use Term::*;
let at = |c: Option<OccId>| inner[c.expect("a child").index()];
let (width, binary) = match sequent.terms()[forest.term(o).index()] {
Atom(a) | DualAtom(a) if names[a.index()] == u32::MAX => (u32::MAX, false),
Atom(a) | DualAtom(a) => {
let mut width = u64::from(names[a.index()]);
if let Some((_, args)) = sequent.atom_predicate(a) {
let (uses, keyed) = gather(&held, fo.list(args));
width = width.saturating_sub(keyed);
for (i, n) in uses {
let mut b = enclosing[o.index()];
for _ in 0..i {
b = b.and_then(|b| enclosing[b.index()]);
}
let name = b.map_or(1, name_of);
width = width.saturating_add(n.saturating_mul(u64::from(name)));
}
}
let dual = u64::from(matches!(forest.kind(o), Kind::DualAtom));
(
u32::try_from(width.saturating_add(dual)).unwrap_or(u32::MAX),
false,
)
}
One | Bot | Top | Zero => (1, false),
Tensor(..) | Par(..) | With(..) | Plus(..) => (
at(forest.left(o))
.saturating_add(3)
.saturating_add(at(forest.right(o))),
true,
),
Bang(_) | Quest(_) => (at(forest.left(o)).saturating_add(1), false),
Forall(_) | Exists(_) => (
at(forest.left(o)).saturating_add(name_of(o).saturating_add(3)),
true,
),
};
top[o.index()] = width;
inner[o.index()] = if binary {
width.saturating_add(2)
} else {
width
};
}
top.iter().map(|w| w.saturating_add(2)).collect()
}
pub(crate) struct Weights(Vec<u32>);
impl Weights {
pub(crate) fn of(proof: &Proof) -> Self {
Self::of_members(proof.forest(), proof.instances())
}
pub(crate) fn of_members(
forest: &Forest,
instances: Option<&crate::linear::Instances>,
) -> Self {
let mut weights = weights(forest);
if let Some(table) = instances {
let instances = instance_weights(forest, table, &weights);
weights.extend(instances);
}
Self(weights)
}
pub(crate) fn get(&self, m: Member) -> u32 {
self.0[m.index()]
}
fn saturated(&self) -> bool {
self.0.contains(&u32::MAX)
}
}
fn instance_weights(
forest: &Forest,
table: &crate::linear::Instances,
weights: &[u32],
) -> Vec<u32> {
let sequent = forest.sequent();
let fo = &sequent.fo;
let width = |n: usize| u64::try_from(n).unwrap_or(u64::MAX);
let names = eigen_names(fo, &table.eigenvariables());
let terms = crate::linear::occurrences::instances::Terms { fo, table };
let mut written = Vec::<u64>::with_capacity(terms.len());
let mut bound = Vec::<u64>::with_capacity(terms.len());
for id in 0..terms.len() {
let (w, b) = match terms.term(crate::linear::sequents::FoTermId::new(id as u32)) {
FoTerm::Bound(_) => (1, 1),
FoTerm::Eigen(a) => (names.get(&a).map_or(1, |n| width(n.chars().count())), 0),
FoTerm::Meta(k) => (width(meta_name(k).chars().count()), 0),
FoTerm::App(f, args) => {
let list = terms.list(args);
let name = width(fo.symbols[f.index()].0.chars().count());
let (w, b) = list.iter().fold((0u64, 0u64), |(w, b), t| {
(
w.saturating_add(written[t.index()]),
b.saturating_add(bound[t.index()]),
)
});
let brackets = if list.is_empty() {
0
} else {
2 * width(list.len())
};
(name.saturating_add(w).saturating_add(brackets), b)
}
};
written.push(w);
bound.push(b);
}
let printed = printed_names(forest);
let loose = loose_variables(forest);
let enclosing = enclosing_binders(forest);
let renamed = names.values().any(|e| {
fo.binders.iter().any(|(_, b)| {
e == b
|| e.strip_prefix(b.as_str())
.is_some_and(|rest| rest.starts_with('_'))
}) || e == "x"
|| e.starts_with("x_")
});
let rename = renamed.then(|| {
let clashes = fo.symbols.len() + fo.binders.len() + names.len() + forest.len();
1 + u64::from(clashes.checked_ilog10().unwrap_or(0) + 1)
});
let written_names = rename.map(|_| {
let mut counted = vec![0u64; forest.len()];
for o in forest.ids().rev() {
let mut here = u64::from(forest.kind(o).is_binder());
if let Some((_, args)) = forest.atom(o).and_then(|a| sequent.atom_predicate(a)) {
here = fo
.list(args)
.iter()
.fold(here, |n, t| n.saturating_add(bound[t.index()]));
}
for c in forest.children(o) {
here = here.saturating_add(counted[c.index()]);
}
counted[o.index()] = here;
}
counted
});
table
.members
.iter()
.map(|&(o, frame)| {
let mut weight = u64::from(weights[o.index()]);
if weight == u64::from(u32::MAX) {
return u32::MAX;
}
let (mut binder, mut cell) = (enclosing[o.index()], Some(frame));
let mut level = 0;
for &(at, n) in &loose[o.index()] {
while level < at {
binder = binder.and_then(|b| enclosing[b.index()]);
cell = cell.and_then(|c| table.frames[c.index()].0);
level += 1;
}
let name = binder.map_or(1, |b| u64::from(printed[b.index()]));
let term = cell.map_or(1, |c| written[table.frames[c.index()].1.index()]);
weight = weight
.saturating_sub(n.saturating_mul(name))
.saturating_add(n.saturating_mul(term));
}
if let (Some(rename), Some(counted)) = (rename, &written_names) {
weight = weight.saturating_add(counted[o.index()].saturating_mul(rename));
}
u32::try_from(weight).unwrap_or(u32::MAX)
})
.collect()
}
fn enclosing_binders(forest: &Forest) -> Vec<Option<OccId>> {
let mut enclosing: Vec<Option<OccId>> = vec![None; forest.len()];
for o in forest.ids() {
if let Some(p) = forest.parent(o) {
enclosing[o.index()] = if forest.kind(p).is_binder() {
Some(p)
} else {
enclosing[p.index()]
};
}
}
enclosing
}
fn loose_variables(forest: &Forest) -> Vec<Vec<(u32, u64)>> {
let sequent = forest.sequent();
let fo = &sequent.fo;
let mut held: Vec<Vec<(u32, u64)>> = Vec::with_capacity(fo.terms.len());
for term in &fo.terms {
let entry = match *term {
FoTerm::Bound(i) => vec![(i, 1)],
FoTerm::App(_, args) => {
let mut uses = Vec::new();
for t in fo.list(args) {
merge(&mut uses, held[t.index()].iter().copied());
}
uses
}
FoTerm::Eigen(_) | FoTerm::Meta(_) => Vec::new(),
};
held.push(entry);
}
let mut loose: Vec<Vec<(u32, u64)>> = vec![Vec::new(); forest.len()];
for o in forest.ids().rev() {
let mut here = Vec::new();
if let Some((_, args)) = forest.atom(o).and_then(|a| sequent.atom_predicate(a)) {
for t in fo.list(args) {
merge(&mut here, held[t.index()].iter().copied());
}
}
for c in forest.children(o) {
if forest.kind(o).is_binder() {
let shifted = loose[c.index()].iter().filter(|&&(i, _)| i > 0);
merge(&mut here, shifted.map(|&(i, n)| (i - 1, n)));
} else {
merge(&mut here, loose[c.index()].iter().copied());
}
}
loose[o.index()] = here;
}
loose
}
fn merge(uses: &mut Vec<(u32, u64)>, more: impl Iterator<Item = (u32, u64)>) {
for (i, n) in more {
match uses.binary_search_by_key(&i, |&(j, _)| j) {
Ok(at) => uses[at].1 = uses[at].1.saturating_add(n),
Err(at) => uses.insert(at, (i, n)),
}
}
}
impl<I: Instancing> Measure<'_, I> {
fn tables(proof: &Proof) -> u64 {
let members = proof.instances().map_or(0, |t| t.len() as u64);
proof.nodes().len() as u64 * size_of::<Sub>() as u64
+ (proof.forest().len() as u64 + members) * size_of::<u32>() as u64
}
fn characters(&self, m: Member) -> u64 {
u64::from(self.weights.get(m))
}
fn quest(&self, a: Member) -> u64 {
let forest = self.proof.forest();
let q = forest.parent(self.inst.occ(a)).unwrap();
self.characters(self.inst.parent(a, q))
}
fn reach(&self, sub: &Sub, o: Member) -> u64 {
match self.reading {
Some(reading) if reading.position(self.inst.occ(o)) == Side::Output => sub.reached_goal,
_ => sub.reached,
}
}
fn absorbed(&self, sub: &Sub, o: Member, absent: bool) -> u64 {
if absent {
self.characters(o).saturating_mul(self.reach(sub, o))
} else {
0
}
}
fn unary(sub: &Sub, premise: &Sub, own: u64, extra: u64, absorbed: u64) -> Sub {
Sub {
inferences: premise.inferences.saturating_add(own),
characters: premise
.characters
.saturating_add(own.saturating_mul(sub.weight))
.saturating_add(extra)
.saturating_add(absorbed),
reached: premise.reached.saturating_add(own),
reached_goal: premise.reached_goal.saturating_add(own),
height: premise.height.saturating_add(own),
width: premise.width.max(sub.weight.saturating_add(extra)),
..*sub
}
}
fn padded(
&mut self,
premise: &Sub,
beyond: u64,
beyond_goal: u64,
unused: u64,
) -> (u64, u64, u64) {
if premise.absorbs {
let hypotheses = beyond.saturating_sub(beyond_goal);
let characters = premise
.characters
.saturating_add(hypotheses.saturating_mul(premise.reached))
.saturating_add(beyond_goal.saturating_mul(premise.reached_goal));
return (premise.inferences, characters, premise.height);
}
self.exact &= unused <= 1;
let weakened = premise.weight.saturating_add(beyond);
(
premise.inferences.saturating_add(unused),
premise
.characters
.saturating_add(unused.saturating_mul(weakened)),
premise.height.saturating_add(unused),
)
}
}
impl<I: Instancing> Observer for Measure<'_, I> {
fn weight(&self, m: Member, _: OccId) -> u32 {
self.weights.get(m)
}
fn bytes(&self) -> u64 {
Self::tables(self.proof)
}
fn derived(&mut self, id: NodeId, state: &State, facts: &Facts<'_>) {
use Node::*;
let forest = self.proof.forest();
let inst = self.inst;
let (left, right) = (
|m: Member| inst.child(m, forest.left(inst.occ(m)).unwrap()),
|m: Member| inst.child(m, forest.right(inst.occ(m)).unwrap()),
);
let at = |p: NodeId| self.subs[p.index()];
let sub = Sub {
weight: state.weight(),
goal: state.goal_weight(),
absorbs: state.absorbs(),
..Sub::default()
};
let sub = match self.proof.node(id) {
Ax(..) | One(_) | Top(_) => Sub {
inferences: 1,
characters: sub.weight,
reached: 1,
reached_goal: 1,
height: 1,
width: sub.weight,
..sub
},
Bot(_, p) | Weaken(_, p) => Self::unary(&sub, &at(p), 1, 0, 0),
Par(o, p) => {
let premise = at(p);
let absorbed = self
.absorbed(&premise, left(o), facts.absent[0])
.saturating_add(self.absorbed(&premise, right(o), facts.absent[1]));
Self::unary(&sub, &premise, 1, 0, absorbed)
}
Plus(o, side, p) => {
let chosen = match side {
Branch::Left => left(o),
Branch::Right => right(o),
};
let premise = at(p);
let absorbed = self.absorbed(&premise, chosen, facts.absent[0]);
Self::unary(&sub, &premise, 1, 0, absorbed)
}
Bang(o, p) => {
let premise = at(p);
let absorbed = self.absorbed(&premise, left(o), facts.absent[0]);
Self::unary(&sub, &premise, 1, 0, absorbed)
}
Quest(_, p) if facts.used => Sub { ..at(p) },
Quest(_, p) => Self::unary(&sub, &at(p), 1, 0, 0),
Copy(a, p) => {
let premise = at(p);
let absorbed = self.absorbed(&premise, a, facts.absent[0]);
if facts.used {
Self::unary(&sub, &premise, 2, self.quest(a), absorbed)
} else {
Self::unary(&sub, &premise, 1, 0, absorbed)
}
}
node @ (Tensor(_, l, r) | Mix(l, r) | Cut(_, l, r)) => {
let (pl, pr) = (at(l), at(r));
let mut shared: Vec<Member> = facts.shared.to_vec();
shared.sort_unstable();
let own = shared.len() as u64 + 1;
let mut doubled: u64 = 0;
for (j, &a) in shared.iter().enumerate() {
let q = self.quest(a);
doubled = doubled.saturating_add(q.saturating_mul(j as u64 + 1));
}
let widest: u64 = shared
.iter()
.map(|&a| self.quest(a))
.fold(sub.weight, u64::saturating_add);
let absorbed = match node {
Tensor(o, ..) => self
.absorbed(&pl, left(o), facts.absent[0])
.saturating_add(self.absorbed(&pr, right(o), facts.absent[1])),
Cut(a, ..) => {
let dual = inst.dual(forest, a).unwrap();
self.absorbed(&pl, a, facts.absent[0])
.saturating_add(self.absorbed(&pr, dual, facts.absent[1]))
}
_ => 0,
};
let goal_right = match node {
Cut(a, ..) => self
.reading
.is_some_and(|reading| reading.position(inst.occ(a)) == Side::Output),
_ => true,
};
let (reached, reached_goal) = if self.reading.is_some() && pl.absorbs && pr.absorbs
{
(
pl.reached,
if goal_right {
pr.reached_goal
} else {
pl.reached_goal
},
)
} else if pl.absorbs {
(pl.reached, pl.reached_goal)
} else {
(pr.reached, pr.reached_goal)
};
Sub {
inferences: pl
.inferences
.saturating_add(pr.inferences)
.saturating_add(own),
characters: pl
.characters
.saturating_add(pr.characters)
.saturating_add(own.saturating_mul(sub.weight))
.saturating_add(doubled)
.saturating_add(absorbed),
reached: reached.saturating_add(own),
reached_goal: reached_goal.saturating_add(own),
height: pl.height.max(pr.height).saturating_add(own),
width: pl.width.max(pr.width).max(widest),
..sub
}
}
Forall(_, _, p) | Exists(_, _, p) => {
let premise = at(p);
let absorbed = self.absorbed(&premise, inst.body(id), facts.absent[0]);
Self::unary(&sub, &premise, 1, 0, absorbed)
}
With(o, l, r) => {
let (pl, pr) = (at(l), at(r));
let needs = state.needs() as u64;
let output = self
.reading
.is_some_and(|reading| reading.position(inst.occ(o)) == Side::Output);
let beyond = |premise: &Sub, child: Member| {
let (whole, part) = (self.characters(o), self.characters(child));
let all = (sub.weight.saturating_add(part))
.saturating_sub(whole.saturating_add(premise.weight));
let goal = if output {
sub.goal.saturating_add(part).saturating_sub(whole)
} else {
sub.goal
};
(all, goal.saturating_sub(premise.goal).min(all))
};
let ((all_l, goal_l), (all_r, goal_r)) =
(beyond(&pl, left(o)), beyond(&pr, right(o)));
let (il, cl, hl) = self.padded(
&pl,
all_l,
goal_l,
needs.saturating_sub(facts.needs[0] as u64),
);
let (ir, cr, hr) = self.padded(
&pr,
all_r,
goal_r,
needs.saturating_sub(facts.needs[1] as u64),
);
Sub {
inferences: il.saturating_add(ir).saturating_add(1),
characters: cl.saturating_add(cr).saturating_add(sub.weight),
reached: pl.reached.saturating_add(pr.reached).saturating_add(1),
reached_goal: pl
.reached_goal
.saturating_add(pr.reached_goal)
.saturating_add(1),
height: hl.max(hr).saturating_add(1),
width: pl.width.max(pr.width).max(sub.weight),
..sub
}
}
};
let firm = |p: NodeId| self.subs[p.index()].firm;
let firm = match self.proof.node(id) {
Ax(..) | One(_) | Top(_) => Firm::default().and(sub.weight),
Bot(_, p)
| Par(_, p)
| Plus(_, _, p)
| Bang(_, p)
| Forall(_, _, p)
| Exists(_, _, p) => firm(p).and(sub.weight),
Weaken(_, p) | Quest(_, p) => firm(p),
Copy(a, p) if facts.used => firm(p).and(sub.weight.saturating_add(self.quest(a))),
Copy(_, p) => firm(p).and(sub.weight),
Tensor(_, l, r) | Mix(l, r) | Cut(_, l, r) => {
let doubled = facts
.shared
.iter()
.map(|&a| self.quest(a))
.fold(sub.weight, u64::saturating_add);
firm(l).with(firm(r)).and(doubled)
}
With(_, l, r) => firm(l).with(firm(r)).and(sub.weight),
};
self.subs[id.index()] = Sub { firm, ..sub };
}
}
pub(crate) fn measure(
proof: &Proof,
goal: &[OccId],
mode: Mode,
reading: Option<&Reading>,
allowance: Allowance<'_>,
) -> Result<Size, CheckError> {
measured(proof, goal, mode, reading, allowance).map(|(size, _)| size)
}
pub(crate) fn measured(
proof: &Proof,
goal: &[OccId],
mode: Mode,
reading: Option<&Reading>,
allowance: Allowance<'_>,
) -> Result<(Size, Firm), CheckError> {
match proof.instances() {
None => measured_with(proof, &Ground, goal, mode, reading, allowance),
Some(table) => {
let inst = Framed::new(proof, table);
measured_with(proof, &inst, goal, mode, reading, allowance)
}
}
}
fn measured_with<I: Instancing>(
proof: &Proof,
inst: &I,
goal: &[OccId],
mode: Mode,
reading: Option<&Reading>,
allowance: Allowance<'_>,
) -> Result<(Size, Firm), CheckError> {
check::afford(
proof,
Measure::<I>::tables(proof),
allowance.memory,
allowance.phase,
)?;
let mut measure = Measure {
proof,
inst,
reading,
weights: Weights::of(proof),
subs: vec![Sub::default(); proof.nodes().len()],
exact: proof
.instances()
.is_none_or(crate::linear::Instances::is_empty),
};
check::examine(proof, goal, mode, reading, allowance, &mut measure)?;
let root = measure.subs[proof.root().index()];
let characters = |output: bool| {
goal.iter()
.filter(|&&o| !output || reading.is_some_and(|r| r.position(o) == Side::Output))
.fold(0u64, |sum, &o| {
sum.saturating_add(measure.characters(Member::from(o)))
})
};
let (all, goal) = (characters(false), characters(true));
let beyond = all.saturating_sub(root.weight);
let beyond_goal = goal.saturating_sub(root.goal).min(beyond);
let characters = root
.characters
.saturating_add((beyond - beyond_goal).saturating_mul(root.reached))
.saturating_add(beyond_goal.saturating_mul(root.reached_goal));
if measure.weights.saturated() {
let size = Size {
inferences: root.inferences,
characters: u64::MAX,
height: root.height,
width: u64::MAX,
exact: false,
};
return Ok((size, root.firm));
}
let saturated = [root.inferences, characters, root.height].contains(&u64::MAX);
let size = Size {
inferences: root.inferences,
characters,
height: root.height,
width: root.width.max(all),
exact: measure.exact && !saturated,
};
Ok((size, root.firm))
}
#[cfg(all(test, feature = "parse"))]
mod tests {
use crate::linear::proofs::{Derivation, ViewOptions, oracle};
use crate::linear::search::{Options, Verdict, prove};
use crate::linear::{Member, Mode, Sequent};
fn counted(derivation: &Derivation) -> (u64, u64, u64, u64) {
let mut heights = vec![0u64; derivation.inferences().len()];
let (mut characters, mut widest) = (0, 0);
for (i, inference) in derivation.inferences().iter().enumerate() {
let above = inference.premises.iter().map(|p| heights[p.index()]).max();
heights[i] = above.unwrap_or(0) + 1;
let width: u64 = inference
.sequent
.iter()
.map(|&o| written(derivation, o) + 2)
.sum();
characters += width;
widest = widest.max(width);
}
(
heights.len() as u64,
characters,
heights[derivation.root().index()],
widest,
)
}
fn written(derivation: &Derivation, member: Member) -> u64 {
let forest = derivation.forest();
let text = if member.index() < forest.len() {
forest.formula(member.occ()).to_string()
} else {
derivation.formula(member).to_string()
};
text.chars().count() as u64
}
#[test]
fn is_the_size_of_the_derivation_built() {
let never = || false;
let mut bounds = 0;
let mut proofs = oracle::proofs();
let sequent: Sequent = "!A, !B |- (C -o C) & (A * B)".parse().unwrap();
let outcome = prove(&sequent, Mode::CLASSICAL, &Options::default()).unwrap();
let Verdict::Proved(proof) = outcome.verdict else {
panic!("provable");
};
proofs.push((*proof, Mode::CLASSICAL));
let affine = Mode::INTUITIONISTIC.with_affine();
for (input, mode) in [
("0, 0 -o 0 * D |- C * C * C", Mode::INTUITIONISTIC),
("0 -o 0 * D, 0 |- C * C * C", Mode::INTUITIONISTIC),
("0, 0, (D * 0) -o 0 |- C * C * C", Mode::INTUITIONISTIC),
("0 + 0, !A |- (A * A) * C", Mode::INTUITIONISTIC),
(
"|- top, ?(forall long. p(long, c)), exists v10. q(v10)",
Mode::CLASSICAL,
),
(
"(c -o a), ((a -o a) -o (c -o c)), c, (c -o c) |- (a * ((b -o top) -o (((c -o \
top) & (top + a)) -o ((c + (top -o a)) -o (((top * b) & b) + (((c * a) + (b & \
top)) + (top & (top * top))))))))",
affine,
),
] {
let sequent: Sequent = input.parse().unwrap();
let outcome = prove(&sequent, mode, &Options::default()).unwrap();
let Verdict::Proved(proof) = outcome.verdict else {
panic!("{input} is provable");
};
proofs.push((*proof, mode));
}
{
use crate::linear::proofs::{Node::*, NodeId};
let sequent: Sequent = "|- ?~a, (a * (a * top)) & top".parse().unwrap();
let (o, n) = (crate::linear::occurrences::Member::new, NodeId::new);
let nodes = vec![
Ax(o(4), o(1)),
Ax(o(6), o(1)),
Top(o(7)),
Tensor(o(5), n(1), n(2)),
Tensor(o(3), n(0), n(3)),
Top(o(8)),
With(o(2), n(4), n(5)),
Copy(o(1), n(6)),
Copy(o(1), n(7)),
Quest(o(0), n(8)),
];
let forest = crate::linear::Forest::new(&sequent).unwrap();
let proof = crate::linear::Proof::new(forest, nodes, n(9)).unwrap();
assert_eq!(proof.check(Mode::CLASSICAL), Ok(()));
proofs.push((proof, Mode::CLASSICAL));
}
for (proof, mode) in proofs {
let mut views = vec![(
false,
Derivation::new(
&proof,
&ViewOptions::default(),
&crate::Limits::default().with_derivation_bytes(None),
|_| never(),
)
.unwrap(),
)];
if mode.intuitionistic {
views.push((
true,
Derivation::two_sided(
&proof,
&ViewOptions::default(),
&crate::Limits::default().with_derivation_bytes(None),
|_| never(),
)
.unwrap(),
));
}
for (two_sided, derivation) in views {
let size = proof.size_of(two_sided).unwrap();
let (inferences, characters, height, widest) = counted(&derivation);
let conclusion = counted_root(&derivation);
let context = format!("{} ({mode}, two-sided: {two_sided})", proof.sequent());
assert_eq!(size.inferences, inferences, "{context}");
assert_eq!(size.height, height, "{context}");
if size.exact {
assert_eq!(size.characters, characters, "{context}");
} else {
bounds += 1;
assert!(size.characters >= characters, "{context}");
}
assert!(
conclusion <= size.width && size.width <= widest,
"{context}: {conclusion} <= {} <= {widest}",
size.width
);
}
}
assert!(bounds > 0, "no sample whose sum is a bound");
}
#[cfg(feature = "serialize")]
#[test]
fn binder_names_are_counted_as_written() {
let mut sequents: Vec<Sequent> = [
"|- (forall z. exists a. ~p(a)), forall b. p(b)",
"|- exists x. p(x), forall x. ~p(x)",
]
.iter()
.map(|text| text.parse().unwrap())
.collect();
sequents.push(
serde_json::from_str(r#"{"version":7,"terms":["1",{"∀":0}],"roots":[1],"atoms":[]}"#)
.unwrap(),
);
for sequent in sequents {
let outcome = prove(&sequent, Mode::CLASSICAL, &Options::default()).unwrap();
let Verdict::Proved(proof) = outcome.verdict else {
panic!("{sequent} is provable");
};
let derivation = Derivation::new(
&proof,
&ViewOptions::default(),
&crate::Limits::default().with_derivation_bytes(None),
|_| false,
)
.unwrap();
let size = proof.size_of(false).unwrap();
let (_, characters, _, widest) = counted(&derivation);
assert!(
size.characters >= characters && size.width <= widest,
"{sequent}: {size:?} against {characters} and {widest}"
);
}
}
#[test]
fn a_formula_too_long_to_count_is_not_counted_short() {
use crate::linear::proofs::{Node, NodeId, Proof};
use crate::linear::sequents::{Atom, Term, TermId};
use crate::linear::{Forest, Member};
let mut terms = vec![Term::Top, Term::Atom(Atom::new(0))];
for j in 0..12 {
terms.push(Term::With(TermId::new(1 + j), TermId::new(1 + j)));
}
let sequent = Sequent {
terms,
roots: vec![TermId::new(0), TermId::new(13)],
atoms: vec!["a".repeat(1 << 20)],
antecedents: None,
cuts: vec![],
fo: Default::default(),
};
let forest = Forest::new(&sequent).unwrap();
assert_eq!(forest.len(), 1 + (1 << 13) - 1);
let nodes = vec![Node::Top(Member::new(0))];
let proof = Proof::new(forest, nodes, NodeId::new(0)).unwrap();
let size = proof.size_of(false).unwrap();
assert_eq!((size.inferences, size.height), (1, 1));
assert_eq!((size.characters, size.width), (u64::MAX, u64::MAX));
assert!(!size.exact);
}
fn counted_root(derivation: &Derivation) -> u64 {
derivation
.inference(derivation.root())
.sequent
.iter()
.map(|&o| written(derivation, o) + 2)
.sum()
}
}