use super::{Derivation, Formulas, Interactive, Logic, Node, NodeId, Rule, Sequent, Side, Step};
use crate::Error;
use crate::kripke::{Model, World};
use crate::limits::{Limits, Phase, Progress, Refusal};
use crate::linear::proofs::{GoalId, Structural, ViewOptions};
use std::fmt::{self, Display, Formatter, Write};
#[non_exhaustive]
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub enum Sign {
True,
False,
}
impl Sign {
pub const fn of(side: Side) -> Self {
match side {
Side::Left => Self::True,
Side::Right => Self::False,
}
}
pub const fn letter(self) -> &'static str {
match self {
Self::True => "T",
Self::False => "F",
}
}
}
#[non_exhaustive]
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub struct Signed {
pub sign: Sign,
pub formula: NodeId,
}
impl Signed {
pub const fn new(sign: Sign, formula: NodeId) -> Self {
Self { sign, formula }
}
}
#[non_exhaustive]
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub enum End {
Closed {
true_line: u32,
false_line: u32,
},
Falsity {
line: u32,
},
Truth {
line: u32,
},
Open,
Unexpanded,
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct TableauNode {
first: u32,
lines: Vec<Signed>,
expands: Option<(u32, Rule)>,
children: Vec<u32>,
end: Option<End>,
}
impl TableauNode {
pub fn first_line(&self) -> u32 {
self.first
}
pub fn lines(&self) -> &[Signed] {
&self.lines
}
pub fn expands(&self) -> Option<(u32, Rule)> {
self.expands
}
pub fn children(&self) -> &[u32] {
&self.children
}
pub fn end(&self) -> Option<End> {
self.end
}
}
#[derive(Clone, Debug)]
pub struct Tableau {
formulas: Formulas,
left: Vec<NodeId>,
right: Vec<NodeId>,
nodes: Vec<TableauNode>,
}
#[derive(Clone, Copy, Debug)]
enum Place {
Line(u32),
New(usize),
}
struct Pending {
inference: usize,
parent: Option<u32>,
lines: Vec<Signed>,
places: Vec<Place>,
}
fn placed(
conclusion: &[Signed],
lines: &[u32],
principal: Option<usize>,
premise: &[Signed],
structural: bool,
) -> (Vec<Place>, Vec<Signed>) {
let mut free: Vec<bool> = (0..conclusion.len())
.map(|k| Some(k) != principal)
.collect();
let mut added = Vec::new();
let places = premise
.iter()
.map(|line| {
let same = |k: &usize| conclusion[*k] == *line;
if let Some(k) = (0..conclusion.len()).find(|k| free[*k] && same(k)) {
free[k] = false;
Place::Line(lines[k])
} else if let (true, Some(k)) = (structural, (0..conclusion.len()).find(same)) {
Place::Line(lines[k])
} else {
added.push(*line);
Place::New(added.len() - 1)
}
})
.collect();
(places, added)
}
impl Tableau {
pub fn of(
derivation: &Derivation,
mut stop: impl FnMut(Progress) -> bool,
) -> Result<Self, Error> {
if derivation.logic() != Logic::Classical {
return Err(Error::Logic {
logic: derivation.logic(),
method: super::Method::Tableau,
});
}
let fail = |reason: String| Error::ReadBack {
calculus: "LK",
reason,
};
let inferences = derivation.inferences();
let (left, right) = derivation.sequent();
let root: Vec<Signed> = signed(left, right).collect();
let mut nodes: Vec<TableauNode> = Vec::new();
let mut next_line = 0u32;
let mut visited = 0u64;
let mut pending = vec![Pending {
inference: inferences.len() - 1,
parent: None,
places: (0..root.len()).map(Place::New).collect(),
lines: root,
}];
while let Some(node) = pending.pop() {
let index = u32::try_from(nodes.len()).map_err(|_| too_many(nodes.len()))?;
let first = next_line;
let count = u32::try_from(node.lines.len()).map_err(|_| too_many(node.lines.len()))?;
next_line = next_line
.checked_add(count)
.ok_or_else(|| too_many(next_line as usize))?;
if let Some(parent) = node.parent {
nodes[parent as usize].children.push(index);
}
let mut lines: Vec<u32> = node
.places
.iter()
.map(|place| match *place {
Place::Line(line) => line,
Place::New(k) => first + k as u32,
})
.collect();
let mut at = node.inference;
loop {
visited += 1;
if stop(Progress::new(Phase::View, 1, visited)) {
return Err(Error::Refused(Refusal::Stopped { phase: Phase::View }));
}
let inference = &inferences[at];
match inference.rule() {
Rule::WeakenLeft
| Rule::WeakenRight
| Rule::ContractLeft
| Rule::ContractRight => {
let premise = inference
.premises()
.first()
.ok_or_else(|| fail(format!("inference {at} has no premise")))?
.index();
let conclusion: Vec<Signed> =
signed(inference.left(), inference.right()).collect();
let above = &inferences[premise];
let (places, _) = placed(
&conclusion,
&lines,
None,
&signed(above.left(), above.right()).collect::<Vec<_>>(),
true,
);
lines = places
.iter()
.map(|place| match *place {
Place::Line(line) => Ok(line),
Place::New(_) => Err(fail(format!(
"the structural inference {at} adds a formula"
))),
})
.collect::<Result<_, _>>()?;
at = premise;
}
Rule::Axiom
| Rule::AndLeft
| Rule::AndLeft1
| Rule::AndLeft2
| Rule::AndRight
| Rule::OrLeft
| Rule::OrRight
| Rule::OrRight1
| Rule::OrRight2
| Rule::ImpliesLeft
| Rule::ImpliesRight
| Rule::NotLeft
| Rule::NotRight
| Rule::IffLeft
| Rule::IffLeft1
| Rule::IffLeft2
| Rule::IffRight
| Rule::FalseLeft
| Rule::FalseRight
| Rule::TrueLeft
| Rule::TrueRight
| Rule::Cut
| Rule::Open => break,
}
}
let inference = &inferences[at];
let conclusion: Vec<Signed> = signed(inference.left(), inference.right()).collect();
let hypotheses = inference.left().len();
let mut made = TableauNode {
first,
lines: node.lines,
expands: None,
children: Vec::new(),
end: None,
};
match inference.rule() {
Rule::Axiom => {
let pair = inference.left().iter().enumerate().find_map(|(i, x)| {
let j = inference.right().iter().position(|y| y == x)?;
Some((lines[i], lines[hypotheses + j]))
});
let (true_line, false_line) = pair
.ok_or_else(|| fail(format!("axiom {at} has no formula on both sides")))?;
made.end = Some(End::Closed {
true_line,
false_line,
});
}
Rule::FalseLeft | Rule::TrueRight => {
let falsity = inference.rule() == Rule::FalseLeft;
let constant = |x: &NodeId| match derivation.formulas().node(*x) {
Node::False => falsity,
Node::True => !falsity,
Node::Atom(_)
| Node::Not(_)
| Node::And(..)
| Node::Or(..)
| Node::Implies(..)
| Node::Iff(..) => false,
};
let line = if falsity {
inference.left().iter().position(constant).map(|i| lines[i])
} else {
inference
.right()
.iter()
.position(constant)
.map(|j| lines[hypotheses + j])
}
.ok_or_else(|| fail(format!("inference {at} closes on no line")))?;
made.end = Some(if falsity {
End::Falsity { line }
} else {
End::Truth { line }
});
}
Rule::Open => {
made.end = Some(if finished(derivation.formulas(), inference) {
End::Open
} else {
End::Unexpanded
});
}
Rule::Cut
| Rule::WeakenLeft
| Rule::WeakenRight
| Rule::ContractLeft
| Rule::ContractRight => {
return Err(fail(format!("inference {at} is no step of a tableau")));
}
rule @ (Rule::AndLeft
| Rule::AndLeft1
| Rule::AndLeft2
| Rule::AndRight
| Rule::OrLeft
| Rule::OrRight
| Rule::OrRight1
| Rule::OrRight2
| Rule::ImpliesLeft
| Rule::ImpliesRight
| Rule::NotLeft
| Rule::NotRight
| Rule::IffLeft
| Rule::IffLeft1
| Rule::IffLeft2
| Rule::IffRight
| Rule::FalseRight
| Rule::TrueLeft) => {
let (side, position) = inference
.principal()
.ok_or_else(|| fail(format!("inference {at} has no principal formula")))?;
let principal = match side {
Side::Left => position,
Side::Right => hypotheses + position,
};
let line = *lines
.get(principal)
.ok_or_else(|| fail(format!("inference {at} names no formula")))?;
made.expands = Some((line, rule));
for &premise in inference.premises().iter().rev() {
let above = &inferences[premise.index()];
let (places, lines_added) = placed(
&conclusion,
&lines,
Some(principal),
&signed(above.left(), above.right()).collect::<Vec<_>>(),
false,
);
pending.push(Pending {
inference: premise.index(),
parent: Some(index),
lines: lines_added,
places,
});
}
}
}
nodes.push(made);
}
Ok(Self {
formulas: derivation.formulas().clone(),
left: left.to_vec(),
right: right.to_vec(),
nodes,
})
}
pub fn formulas(&self) -> &Formulas {
&self.formulas
}
pub fn sequent(&self) -> (&[NodeId], &[NodeId]) {
(&self.left, &self.right)
}
pub fn nodes(&self) -> &[TableauNode] {
&self.nodes
}
pub fn line_count(&self) -> u32 {
self.nodes
.last()
.map_or(0, |node| node.first + node.lines.len() as u32)
}
pub fn line(&self, line: u32) -> Signed {
let at = self.nodes.partition_point(|node| node.first <= line) - 1;
let node = &self.nodes[at];
node.lines[(line - node.first) as usize]
}
pub fn is_closed(&self) -> bool {
self.nodes.iter().all(|node| {
!node.children.is_empty()
|| matches!(
node.end,
Some(End::Closed { .. } | End::Falsity { .. } | End::Truth { .. })
)
})
}
pub fn write_text(&self, out: &mut impl Write) -> fmt::Result {
let mut rows: Vec<(String, String)> = Vec::new();
let mut stack: Vec<(usize, String, &str)> = vec![(0, String::new(), "")];
while let Some((index, prefix, marker)) = stack.pop() {
let node = &self.nodes[index];
let from = self.parent_rule(index);
for (k, line) in node.lines.iter().enumerate() {
let lead = if k == 0 { marker } else { blank(marker) };
let mut text = format!(
"{prefix}{lead}{} {} ",
node.first as usize + k + 1,
line.sign.letter()
);
write!(text, "{}", self.formulas.formula(line.formula))?;
let just =
from.map_or(String::new(), |(line, rule)| format!("{rule} {}", line + 1));
rows.push((text, just));
}
let inner = format!("{prefix}{}", blank(marker));
if let Some(end) = node.end {
rows.push((format!("{inner}{}", ending(end)), String::new()));
}
match node.children.as_slice() {
[only] => stack.push((*only as usize, inner, "")),
children => {
for (k, &child) in children.iter().enumerate().rev() {
let last = k + 1 == children.len();
stack.push((
child as usize,
inner.clone(),
if last { "└─ " } else { "├─ " },
));
}
}
}
}
let width = rows
.iter()
.map(|(text, _)| text.chars().count())
.max()
.unwrap_or(0);
for (n, (text, just)) in rows.iter().enumerate() {
if n > 0 {
writeln!(out)?;
}
if just.is_empty() {
out.write_str(text)?;
} else {
let pad = width - text.chars().count();
write!(out, "{text}{:pad$} {just}", "")?;
}
}
Ok(())
}
fn parent_rule(&self, index: usize) -> Option<(u32, Rule)> {
let child = u32::try_from(index).ok()?;
self.nodes[..index]
.iter()
.rev()
.find(|node| node.children.contains(&child))
.and_then(|node| node.expands)
}
#[cfg(feature = "serialize")]
pub(crate) fn from_parts(
formulas: Formulas,
(left, right): (Vec<NodeId>, Vec<NodeId>),
nodes: Vec<TableauNode>,
) -> Self {
Self {
formulas,
left,
right,
nodes,
}
}
}
impl TableauNode {
#[cfg(feature = "serialize")]
pub(crate) fn from_parts(
first: u32,
lines: Vec<Signed>,
(expands, children, end): (Option<(u32, Rule)>, Vec<u32>, Option<End>),
) -> Self {
Self {
first,
lines,
expands,
children,
end,
}
}
}
impl Display for Tableau {
fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
self.write_text(f)
}
}
fn blank(marker: &str) -> &'static str {
match marker {
"" => "",
"├─ " => "│ ",
_ => " ",
}
}
fn ending(end: End) -> String {
match end {
End::Closed {
true_line,
false_line,
} => format!("× {}, {}", true_line + 1, false_line + 1),
End::Falsity { line } | End::Truth { line } => format!("× {}", line + 1),
End::Open => "open".to_owned(),
End::Unexpanded => "not expanded".to_owned(),
}
}
const GOAL_BYTES: u64 = 160;
fn axiom_bytes(formulas: usize) -> u64 {
let n = formulas as u64;
let below = n.saturating_sub(1);
below
.saturating_mul(GOAL_BYTES)
.saturating_add(4u64.saturating_mul(n).saturating_mul(below))
}
fn too_many(count: usize) -> Error {
Error::Refused(Refusal::Index {
what: crate::limits::Space::Inference,
count: count as u64,
most: u64::from(u32::MAX),
})
}
fn signed<'a>(left: &'a [NodeId], right: &'a [NodeId]) -> impl Iterator<Item = Signed> + 'a {
left.iter()
.map(|&x| Signed::new(Sign::True, x))
.chain(right.iter().map(|&x| Signed::new(Sign::False, x)))
}
fn finished(formulas: &Formulas, goal: &super::Inference) -> bool {
next_step(formulas, goal.left(), goal.right()).is_none()
}
fn next_step(formulas: &Formulas, left: &[NodeId], right: &[NodeId]) -> Option<Step> {
if let Some(i) = left.iter().position(|x| right.contains(x)) {
return Some(Step::new(Side::Left, i, Rule::Axiom));
}
if let Some(i) = left.iter().position(|&x| formulas.node(x) == Node::False) {
return Some(Step::new(Side::Left, i, Rule::FalseLeft));
}
if let Some(i) = right.iter().position(|&x| formulas.node(x) == Node::True) {
return Some(Step::new(Side::Right, i, Rule::TrueRight));
}
let one = |side: Side, x: NodeId| match (side, formulas.node(x)) {
(Side::Left, Node::And(..)) => Some(Rule::AndLeft),
(Side::Left, Node::Not(_)) => Some(Rule::NotLeft),
(Side::Left, Node::Iff(..)) => Some(Rule::IffLeft),
(Side::Right, Node::Or(..)) => Some(Rule::OrRight),
(Side::Right, Node::Implies(..)) => Some(Rule::ImpliesRight),
(Side::Right, Node::Not(_)) => Some(Rule::NotRight),
(_, Node::Atom(_) | Node::True | Node::False)
| (Side::Left, Node::Or(..) | Node::Implies(..))
| (Side::Right, Node::And(..) | Node::Iff(..)) => None,
};
let two = |side: Side, x: NodeId| match (side, formulas.node(x)) {
(Side::Left, Node::Or(..)) => Some(Rule::OrLeft),
(Side::Left, Node::Implies(..)) => Some(Rule::ImpliesLeft),
(Side::Right, Node::And(..)) => Some(Rule::AndRight),
(Side::Right, Node::Iff(..)) => Some(Rule::IffRight),
(_, Node::Atom(_) | Node::True | Node::False | Node::Not(_))
| (Side::Left, Node::And(..) | Node::Iff(..))
| (Side::Right, Node::Or(..) | Node::Implies(..)) => None,
};
let rules: [&dyn Fn(Side, NodeId) -> Option<Rule>; 2] = [&one, &two];
for rule_of in rules {
for (side, list) in [(Side::Left, left), (Side::Right, right)] {
for (i, &x) in list.iter().enumerate() {
if let Some(rule) = rule_of(side, x) {
return Some(Step::new(side, i, rule));
}
}
}
}
None
}
type Expanded = (Vec<GoalId>, Vec<(GoalId, Step)>, u64);
fn expand(
state: &mut Interactive,
limits: &Limits,
stop: &mut impl FnMut(Progress) -> bool,
) -> Result<Expanded, Error> {
let mut open = Vec::new();
let mut closing = Vec::new();
let mut goals: Vec<_> = state.goals().collect();
let mut steps = 0u64;
let mut held = 0u64;
while let Some(goal) = goals.pop() {
steps += 1;
if stop(Progress::new(Phase::Search, 1, steps)) {
return Err(Error::Refused(Refusal::Stopped {
phase: Phase::Search,
}));
}
if let Some(limit) = limits.work
&& steps > limit
{
return Err(Error::Refused(Refusal::Work { limit }));
}
let (left, right) = state.goal(goal)?;
match next_step(state.formulas(), left, right) {
Some(step) if matches!(step.rule, Rule::Axiom | Rule::FalseLeft | Rule::TrueRight) => {
if step.rule == Rule::Axiom {
held = held.saturating_add(axiom_bytes(left.len() + right.len()));
}
closing.push((goal, step));
}
Some(step) => {
let opened = state.apply(goal, &step)?;
for &new in &opened {
let (left, right) = state.goal(new)?;
held = held.saturating_add(GOAL_BYTES + 8 * (left.len() + right.len()) as u64);
}
goals.extend(opened.into_iter().rev());
}
None => open.push(goal),
}
if let Some(limit) = limits.memory_bytes
&& held > limit
{
return Err(Error::Refused(Refusal::Memory {
phase: Phase::Search,
limit_bytes: limit,
needed_bytes: None,
}));
}
}
Ok((open, closing, steps))
}
pub(super) fn decide(
sequent: &Sequent,
logic: Logic,
limits: &Limits,
mut stop: impl FnMut(Progress) -> bool,
) -> Result<super::Outcome, Error> {
if logic != Logic::Classical {
return Err(Error::Logic {
logic,
method: super::Method::Tableau,
});
}
let mut state = Interactive::within(sequent, logic, limits)?;
let (open, closing, steps) = expand(&mut state, limits, &mut stop)?;
for (goal, step) in closing {
if stop(Progress::new(Phase::Search, 1, steps)) {
return Err(Error::Refused(Refusal::Stopped {
phase: Phase::Search,
}));
}
state.apply(goal, &step)?;
}
let Some(&first) = open.first() else {
let derivation = state.finished(limits, &mut stop)?;
let tableau = Tableau::of(&derivation, &mut stop)?;
return Ok(super::Outcome {
verdict: super::Verdict::Valid(super::Evidence::Derivation(Box::new(derivation))),
logic,
search: super::Search::Tableau(Box::new(tableau)),
countermodel: None,
});
};
let view = ViewOptions::default().with_structural(Structural::Explicit);
let derivation = state.derivation_within(&view, limits, &mut stop)?;
let tableau = Tableau::of(&derivation, &mut stop)?;
let formulas = state.formulas();
let (left, _) = state.goal(first)?;
let mut atoms: Vec<String> = left
.iter()
.filter_map(|&x| match formulas.node(x) {
Node::Atom(a) => Some(formulas.atom_names()[a as usize].clone()),
Node::True
| Node::False
| Node::Not(_)
| Node::And(..)
| Node::Or(..)
| Node::Implies(..)
| Node::Iff(..) => None,
})
.collect();
atoms.sort_unstable();
atoms.dedup();
let model = Model::new(vec![World::new(atoms, false, Vec::new())], 0);
let countermodel =
super::Countermodel::found(sequent.clone(), model, logic, limits, &mut stop)?;
Ok(super::Outcome {
verdict: super::Verdict::NotValid,
logic,
search: super::Search::Tableau(Box::new(tableau)),
countermodel,
})
}
#[cfg(all(test, feature = "parse"))]
mod tests {
use super::super::{Evidence, Interactive, Logic, Options, Sequent, Verdict, decide};
use super::{End, Tableau, expand};
use crate::Limits;
#[test]
#[cfg(feature = "serialize")]
fn a_stopped_search_holds_no_closed_branch() {
let atoms = |x: char| {
(0..40)
.map(|i| format!("{x}{i}"))
.collect::<Vec<_>>()
.join(", ")
};
let text = format!(
"{}, (a \\/ b) /\\ (c \\/ d) /\\ (e \\/ f) |- {}, e, f",
atoms('p'),
atoms('q')
);
let sequent: Sequent = text.parse().unwrap();
let limits = Limits::default();
let mut state = Interactive::within(&sequent, Logic::Classical, &limits).unwrap();
let mut asked = 0u64;
let stopped = expand(&mut state, &limits, &mut |_| {
asked += 1;
asked > 6
});
assert!(stopped.is_err());
assert!(
state.parts().2.len() <= 1 + 6 * 2,
"{}",
state.parts().2.len()
);
let mut state = Interactive::within(&sequent, Logic::Classical, &limits).unwrap();
let (open, closing, _) = expand(&mut state, &limits, &mut |_| false).unwrap();
assert_eq!(open, []);
assert_eq!(closing.len(), 8);
}
#[test]
fn the_axioms_weakenings_count_against_the_memory_bound() {
use super::super::{Method, decide_within};
use crate::limits::Refusal;
let atoms = |x: char| {
(0..60)
.map(|i| format!("{x}{i}"))
.collect::<Vec<_>>()
.join(", ")
};
let splits = (0..6)
.map(|j| format!("(x{j} \\/ y{j})"))
.collect::<Vec<_>>()
.join(", ");
let text = format!("{}, {splits}, (z \\/ z) |- {}, z", atoms('p'), atoms('q'));
let sequent: Sequent = text.parse().unwrap();
let options = Options::default()
.with_logic(Logic::Classical)
.with_method(Some(Method::Tableau));
let decided = |bytes: u64| {
let limits = Limits::default().with_memory_bytes(Some(bytes));
decide_within(&sequent, &options, &Default::default(), &limits, |_| false)
};
assert!(matches!(
decided(1 << 20),
Err(crate::Error::Refused(Refusal::Memory { .. }))
));
assert!(matches!(
decided(64 << 20).unwrap().verdict,
Verdict::Valid(Evidence::Derivation(_))
));
}
#[test]
fn a_tableau_closes_or_gives_a_countermodel() {
let options = Options::default()
.with_logic(Logic::Classical)
.with_method(Some(super::super::Method::Tableau));
let sequent: Sequent = "a /\\ b |- b /\\ a".parse().unwrap();
let outcome = decide(&sequent, &options).unwrap();
let Verdict::Valid(Evidence::Derivation(derivation)) = &outcome.verdict else {
panic!("valid: {:?}", outcome.verdict);
};
let super::super::Search::Tableau(tableau) = &outcome.search else {
panic!("a tableau");
};
assert!(tableau.is_closed());
assert_eq!(
Tableau::of(derivation, |_| false).unwrap().nodes(),
tableau.nodes()
);
assert_eq!(
tableau.to_string(),
"1 T a ∧ b\n\
2 F b ∧ a\n\
3 T a ∧L 1\n\
4 T b ∧L 1\n\
├─ 5 F b ∧R 2\n\
│ × 4, 5\n\
└─ 6 F a ∧R 2\n\
\u{20} × 3, 6"
);
let sequent: Sequent = "a \\/ b |- a".parse().unwrap();
let outcome = decide(&sequent, &options).unwrap();
assert!(matches!(outcome.verdict, Verdict::NotValid));
let super::super::Search::Tableau(tableau) = &outcome.search else {
panic!("a tableau");
};
assert!(!tableau.is_closed());
assert!(tableau.nodes().iter().any(|n| n.end() == Some(End::Open)));
let countermodel = outcome.countermodel.unwrap();
assert_eq!(countermodel.model.worlds[0].atoms, ["b"]);
let intuitionistic = options.with_logic(Logic::Intuitionistic);
assert!(decide(&sequent, &intuitionistic).is_err());
let twice: Sequent = "a /\\ b, a /\\ b |- c".parse().unwrap();
let outcome = decide(&twice, &options).unwrap();
let super::super::Search::Tableau(tableau) = &outcome.search else {
panic!("a tableau");
};
let cited: Vec<u32> = tableau
.nodes()
.iter()
.filter_map(|n| n.expands().map(|(line, _)| line))
.collect();
assert_eq!(cited, [0, 1]);
let atoms = &outcome.countermodel.unwrap().model.worlds[0].atoms;
assert_eq!(atoms, &["a", "b"]);
let wide: Sequent = "a \\/ b, c \\/ d, e \\/ f |- g".parse().unwrap();
let small = crate::Limits::default().with_memory_bytes(Some(256));
let refused = super::super::decide_within(
&wide,
&options,
&crate::linear::search::Options::default(),
&small,
|_| false,
);
assert!(
matches!(
refused,
Err(crate::Error::Refused(crate::Refusal::Memory { .. }))
),
"{refused:?}"
);
}
}