1use super::expand::formula_at;
12use super::{GoalId, Interactive, Step, StepError, Witness};
13use crate::limits::{Limits, Phase, Refusal};
14use crate::linear::occurrences::{Member, OccId};
15use crate::linear::proofs::derivation::Inference;
16use crate::linear::proofs::multiset::Multiset;
17use crate::linear::proofs::{Named, Rule};
18use crate::linear::sequents::Kind;
19
20#[non_exhaustive]
30#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
31#[cfg_attr(
32 feature = "serialize",
33 derive(serde::Serialize, serde::Deserialize),
34 serde(default, deny_unknown_fields)
35)]
36pub struct Options {
37 pub invertible: bool,
41}
42
43impl Options {
44 pub const DEFAULT_INVERTIBLE: bool = false;
47
48 #[must_use]
50 pub const fn with_invertible(self, invertible: bool) -> Self {
51 Self { invertible }
52 }
53}
54
55impl Default for Options {
56 fn default() -> Self {
59 Self {
60 invertible: Self::DEFAULT_INVERTIBLE,
61 }
62 }
63}
64
65#[non_exhaustive]
69#[derive(Clone, Debug, PartialEq, Eq)]
70pub struct Inverted {
71 pub steps: usize,
75 pub open: Vec<GoalId>,
79 pub finished: Result<(), Refusal>,
83}
84
85impl Interactive {
86 pub fn invert(&mut self, goal: GoalId, limits: &Limits) -> Result<Inverted, StepError> {
102 self.goal(goal)?;
103 Ok(self.invert_goals(vec![goal], limits))
104 }
105
106 pub fn invert_all(&mut self, limits: &Limits) -> Inverted {
109 let goals = self.goals().collect();
110 self.invert_goals(goals, limits)
111 }
112
113 pub fn is_invertible(&self, sequent: &[Member], step: &Step) -> bool {
129 let sequent: Vec<OccId> = sequent.iter().map(|&m| self.occurrence(m)).collect();
130 let Ok(left) = step.left_positions(sequent.len()) else {
131 return false;
132 };
133 let Ok(o) = formula_at(&sequent, step.position) else {
134 return false;
135 };
136 let rule = self.invertible_rule(&sequent, self.non_quests(&sequent), step.position);
137 if !left.is_empty() || rule != Some(step.rule.rule) {
138 return false;
139 }
140 let reading = self.reading();
141 let named = Named::applied(step.rule.rule, reading.as_ref(), o);
142 (step.rule.side.is_none() || step.rule == named)
143 && self
144 .expand(reading.as_ref(), &sequent, step.position, named, &[])
145 .is_ok()
146 }
147
148 fn invert_goals(&mut self, goals: Vec<GoalId>, limits: &Limits) -> Inverted {
151 let mut todo: Vec<GoalId> = goals.into_iter().rev().collect();
152 let (mut steps, mut open) = (0, Vec::new());
153 let mut held = 0u64;
157 while let Some(goal) = todo.pop() {
158 let Some((position, rule, premises)) = self.invertible_step(goal) else {
159 open.push(goal);
160 continue;
161 };
162 let needed = premises.iter().fold(0u64, |sum, premise| {
163 let members = premise.as_slice().len() * size_of::<Member>();
164 sum.saturating_add((size_of::<Inference>() + members) as u64)
165 });
166 if let Some(limit) = limits.memory_bytes
167 && held.saturating_add(needed) > limit
168 {
169 open.push(goal);
170 open.extend(todo.into_iter().rev());
171 return Inverted {
172 steps,
173 open,
174 finished: Err(Refusal::Memory {
175 phase: Phase::View,
176 limit_bytes: limit,
177 needed_bytes: Some(held.saturating_add(needed)),
178 }),
179 };
180 }
181 held = held.saturating_add(needed);
182 let premises = if self.fo.is_some() {
183 match self.framed_premises(goal, position, rule.rule, &[], &Witness::Open) {
184 Ok(premises) => premises,
185 Err(_) => {
188 open.push(goal);
189 continue;
190 }
191 }
192 } else {
193 premises.into_iter().map(Multiset::into_members).collect()
194 };
195 let opened = self.record(goal, position, rule, premises);
196 steps += 1;
197 todo.extend(opened.into_iter().rev());
198 }
199 Inverted {
200 steps,
201 open,
202 finished: Ok(()),
203 }
204 }
205
206 fn invertible_step(&self, goal: GoalId) -> Option<(usize, Named, Vec<Multiset>)> {
210 let sequent = self.open(goal).ok()?;
211 let reading = self.reading();
212 let closes = |rule: Rule| matches!(rule, Rule::Top | Rule::Ax | Rule::One);
213 let non_quests = self.non_quests(&sequent);
214 for closing in [true, false] {
215 for position in 0..sequent.len() {
216 let Some(rule) = self.invertible_rule(&sequent, non_quests, position) else {
217 continue;
218 };
219 if closes(rule) != closing {
220 continue;
221 }
222 let named = Named::applied(rule, reading.as_ref(), sequent[position]);
223 if rule == Rule::Ax
226 && let Some(q) = &self.fo
227 && let Ok(&[x, y]) = self.goal(goal)
228 && !q.same_atom(&self.forest, x, y)
229 {
230 continue;
231 }
232 if let Ok(premises) = self.expand(reading.as_ref(), &sequent, position, named, &[])
235 {
236 return Some((position, named, premises));
237 }
238 }
239 }
240 None
241 }
242
243 fn non_quests(&self, sequent: &[OccId]) -> usize {
245 (sequent.iter())
246 .filter(|&&o| self.forest.kind(o) != Kind::Quest)
247 .count()
248 }
249
250 fn invertible_rule(
255 &self,
256 sequent: &[OccId],
257 non_quests: usize,
258 position: usize,
259 ) -> Option<Rule> {
260 let f = &self.forest;
261 let o = sequent[position];
262 let alone = sequent.len() == 1;
263 match f.kind(o) {
264 Kind::Par => Some(Rule::Par),
265 Kind::Bot => Some(Rule::Bot),
266 Kind::With => Some(Rule::With),
267 Kind::Top => Some(Rule::Top),
268 Kind::Bang => (non_quests == 1).then_some(Rule::Promotion),
270 Kind::One => alone.then_some(Rule::One),
271 Kind::Tensor => alone.then_some(Rule::Tensor),
272 Kind::Atom | Kind::DualAtom => match sequent {
273 &[x, y] if f.dual_literals(x, y) => Some(Rule::Ax),
274 _ => None,
275 },
276 Kind::Forall => Some(Rule::Forall),
277 Kind::Plus | Kind::Zero | Kind::Quest | Kind::Exists => None,
278 }
279 }
280}
281
282#[cfg(all(test, feature = "parse"))]
283mod tests {
284 use super::*;
285 use crate::linear::fragment::Mode;
286 use crate::linear::search::generate::{self, IllRules, Rng, Rules};
287 use crate::linear::search::{self, Verdict};
288 use crate::linear::{Sequent, ViewOptions};
289
290 fn start(input: &str, mode: Mode) -> Interactive {
292 let sequent = Sequent::parse_ordered(input, mode.order(), &Limits::default())
293 .unwrap_or_else(|e| panic!("{input:?}: {e}"));
294 Interactive::new(&sequent, mode).unwrap()
295 }
296
297 fn taken(state: &Interactive) -> Vec<String> {
299 (state.inferences.iter())
300 .filter(|i| i.rule.rule != Rule::Open)
301 .map(|i| i.rule.to_string())
302 .collect()
303 }
304
305 #[test]
309 fn the_invertible_rules_under_their_conditions() {
310 let classical = Mode::CLASSICAL;
311 for (input, mode, rules) in [
312 ("|- a par ~a", classical, &["⅋", "ax"][..]),
313 ("|- bot, 1", classical, &["⊥", "1"]),
314 ("|- a & b, top", classical, &["⊤"]),
315 ("|- (a par ~a) & 1", classical, &["&", "⅋", "1", "ax"]),
316 ("|- !(a par ~a), ?b", classical, &["!", "⅋"]),
317 ("|- 1 * 1", classical, &["⊗", "1", "1"]),
318 ("|- 1, a", classical, &[]),
319 ("|- !a, b", classical, &[]),
320 ("|- a * b, c", classical, &[]),
321 ("|- a, ~a, b", classical.with_affine(), &[]),
322 ("|- a, ?b", classical, &[]),
323 ("|- a + b, ~a", classical.with_mix(), &[]),
324 ("a * b |- b * a", Mode::INTUITIONISTIC, &["⊗L"]),
325 ("!a |- !(a & a)", Mode::INTUITIONISTIC, &["!R", "&R"]),
326 ("|- a -o (b -o a * b)", Mode::INTUITIONISTIC, &["⊸R", "⊸R"]),
327 ("|- 1 * 1", Mode::INTUITIONISTIC, &["⊗R", "1R", "1R"]),
328 ("b |- (a \\ a) \\ b", Mode::LAMBEK, &["\\R"]),
329 (
330 "|- (a \\ a) * (b \\ b)",
331 Mode::LAMBEK.with_empty_antecedents(),
332 &["⊗R", "\\R", "\\R", "ax", "ax"],
333 ),
334 (
335 "|- (a \\ a) * (b \\ b)",
336 Mode::CYCLIC,
337 &["⊗", "⅋", "⅋", "ax", "ax"],
338 ),
339 ("a * b |- a * b", Mode::CYCLIC, &["⅋"]),
340 ] {
341 let mut state = start(input, mode);
342 let before = state.derivation().unwrap().to_string();
343 let inverted = state.invert_all(&Limits::default());
344 assert_eq!(taken(&state), rules, "{input} in {mode}");
345 assert_eq!(
346 (inverted.steps, state.steps(), inverted.finished.clone()),
347 (rules.len(), rules.len(), Ok(())),
348 "{input} in {mode}"
349 );
350 let mut open = inverted.open.clone();
351 open.sort_unstable();
352 assert_eq!(open, state.goals().collect::<Vec<_>>());
353 assert_eq!(state.invert_all(&Limits::default()).steps, 0);
354 if state.is_complete() {
355 state.proof(&Limits::default(), |_| false).unwrap();
356 }
357 for _ in 0..rules.len() {
358 state.undo().unwrap();
359 }
360 assert_eq!(state.derivation().unwrap().to_string(), before);
361 }
362 let mut state = start("|- a par b", classical);
363 state
364 .apply(GoalId::new(0), &Step::new(0, Rule::Par))
365 .unwrap();
366 assert_eq!(
367 state.invert(GoalId::new(0), &Limits::default()),
368 Err(StepError::NoGoal {
369 goal: GoalId::new(0)
370 })
371 );
372 }
373
374 fn weight(forest: &crate::linear::Forest, sequent: &[Member]) -> usize {
377 let mut todo: Vec<OccId> = sequent.iter().map(|m| m.occ()).collect();
378 let mut weight = 0;
379 while let Some(o) = todo.pop() {
380 weight += 1;
381 todo.extend(forest.left(o));
382 todo.extend(forest.right(o));
383 }
384 weight
385 }
386
387 #[test]
393 fn inverting_keeps_every_proof_and_ends() {
394 let mut cases: Vec<(String, Mode)> = Vec::new();
395 for (i, rules) in Rules::ALL.into_iter().enumerate() {
396 let mut rng = Rng::new(3800 + i as u64);
397 let base = if rules.mix {
398 Mode::CLASSICAL.with_mix()
399 } else {
400 Mode::CLASSICAL
401 };
402 for _ in 0..8 {
403 let budget = 2 + rng.below(10);
404 let text =
405 generate::sequent(&generate::provable(&mut rng, rules, 3, budget).formulas);
406 cases.push((text.clone(), base));
407 cases.push((text, base.with_affine()));
408 }
409 }
410 for (i, rules) in IllRules::ALL.into_iter().enumerate() {
411 let mut rng = Rng::new(3900 + i as u64);
412 for _ in 0..8 {
413 let budget = 2 + rng.below(10);
414 let ill = generate::ill(&mut rng, rules, 3, budget);
415 let text = generate::two_sided(&ill.hypotheses, &ill.goal);
416 cases.push((text.clone(), Mode::INTUITIONISTIC));
417 cases.push((text, Mode::INTUITIONISTIC.with_affine()));
418 }
419 }
420 let mut rng = Rng::new(3999);
421 for k in 0..60 {
422 let star = k % 2 == 1;
423 let budget = 2 + rng.below(8);
424 let (hypotheses, goal) = generate::lambek(&mut rng, 3, budget, star);
425 let text = generate::lambek_text(&hypotheses, &goal);
426 let lambek = if star {
427 Mode::LAMBEK.with_empty_antecedents()
428 } else {
429 Mode::LAMBEK
430 };
431 cases.push((text.clone(), lambek));
432 cases.push((text, Mode::CYCLIC));
433 }
434 let options = search::Options::default();
435 let limits = Limits::default();
436 let (mut proved, mut steps) = (0, 0);
437 let mut used = std::collections::BTreeMap::<String, usize>::new();
438 for (text, mode) in cases {
439 let sequent = Sequent::parse_ordered(&text, mode.order(), &limits).unwrap();
440 let Ok(outcome) = search::prove(&sequent, mode, &options) else {
441 continue;
442 };
443 if !matches!(outcome.verdict, Verdict::Proved(_)) {
444 continue;
445 }
446 proved += 1;
447 let mut state = Interactive::new(&sequent, mode).unwrap();
448 let inverted = state.invert_all(&limits);
449 assert_eq!(inverted.finished, Ok(()), "{text} in {mode}");
450 assert_eq!(state.invert_all(&limits).steps, 0, "{text} in {mode}");
451 steps += inverted.steps;
452 for inference in state
453 .inferences
454 .iter()
455 .filter(|i| i.rule.rule != Rule::Open)
456 {
457 *used
458 .entry(format!("{mode}: {}", inference.rule))
459 .or_default() += 1;
460 let conclusion = weight(&state.forest, &inference.sequent);
461 for premise in &inference.premises {
462 let premise = &state.inferences[premise.index()].sequent;
463 assert!(
464 weight(&state.forest, premise) < conclusion,
465 "{text} in {mode}"
466 );
467 }
468 }
469 for goal in inverted.open {
470 let members = state.goal(goal).unwrap();
471 let target = search::Goal::new(state.forest(), members).unwrap();
472 let verdict = search::prove_goal(target, mode, &options, &limits, |_| false)
473 .unwrap()
474 .verdict;
475 assert!(
476 matches!(verdict, Verdict::Proved(_)),
477 "{text} in {mode}: goal {} is {verdict:?}",
478 goal.get()
479 );
480 }
481 for (goal, closed) in
482 state.close_all(&options, &ViewOptions::default(), &limits, |_| false)
483 {
484 let closed = closed.unwrap();
485 assert!(
486 closed.grafted.is_ok(),
487 "{text} in {mode}: goal {}",
488 goal.get()
489 );
490 }
491 assert!(state.is_complete(), "{text} in {mode}");
492 state.proof(&limits, |_| false).unwrap();
493 }
494 assert!(
495 proved >= 500 && steps >= 600,
496 "{proved} proved, {steps} steps"
497 );
498 for (mode, rules) in [
501 ("classical", &["⅋", "⊥", "&", "⊤", "!", "1", "⊗", "ax"][..]),
502 (
503 "classical with Mix",
504 &["⅋", "⊥", "&", "⊤", "!", "1", "⊗", "ax"],
505 ),
506 (
507 "classical affine",
508 &["⅋", "⊥", "&", "⊤", "!", "1", "⊗", "ax"],
509 ),
510 (
511 "intuitionistic",
512 &["⊸R", "⊗L", "&R", "⊕L", "1L", "⊤R", "0L", "!R", "1R", "ax"],
513 ),
514 (
515 "intuitionistic affine",
516 &["⊸R", "⊗L", "&R", "⊕L", "1L", "⊤R", "0L", "!R", "1R", "ax"],
517 ),
518 ("Lambek", &["\\R", "/R", "⊗L", "ax"]),
519 ("Lambek with empty antecedents", &["\\R", "/R", "⊗L", "ax"]),
520 ("cyclic", &["⅋", "ax"]),
521 ] {
522 for rule in rules {
523 assert!(
524 used.contains_key(&format!("{mode}: {rule}")),
525 "{mode}: {rule}"
526 );
527 }
528 }
529 }
530
531 #[test]
534 fn inverting_stops_at_the_memory_bound() {
535 let input = "|- a & a, a & a, a & a, a & a, a & a, a & a";
536 let mut state = start(input, Mode::CLASSICAL);
537 let bounded = Limits::default().with_memory_bytes(Some(4096));
538 let inverted = state.invert_all(&bounded);
539 assert!(
540 matches!(
541 inverted.finished,
542 Err(Refusal::Memory {
543 limit_bytes: 4096,
544 needed_bytes: Some(needed),
545 ..
546 }) if needed > 4096
547 ),
548 "{inverted:?}"
549 );
550 assert!(0 < inverted.steps && inverted.steps < 63, "{inverted:?}");
551 let mut open = inverted.open.clone();
552 open.sort_unstable();
553 assert_eq!(open, state.goals().collect::<Vec<_>>());
554 while state.undo().is_some() {}
555 let inverted = state.invert_all(&Limits::default().with_memory_bytes(None));
556 assert_eq!((inverted.steps, inverted.open.len()), (63, 64));
557 }
558}