logicaffeine_proof/rule_search.rs
1//! `aesop`-style rule-set search: turn `auto`'s fixed cascade into an
2//! extensible, best-first search over registered rules.
3//!
4//! Lean's `aesop` lets you register lemmas as intro/elim/forward/destruct rules
5//! with priorities and a safe/unsafe classification, then searches best-first.
6//! This is that shape, built on the existing tactic combinators and the cheap
7//! [`ProofState`] clone that already powers backtracking: SAFE rules are applied
8//! whenever they fire (no branching — they never lose information); UNSAFE rules
9//! fork the search, ordered by priority. A node budget bounds the search, and
10//! [`SearchStats`] exposes how much was explored — so a best-first strategy can
11//! be shown to expand fewer nodes than blind depth-first `first`/`repeat`.
12//!
13//! `auto` becomes one rule among many (an unsafe fallback), completing the
14//! inversion the tactic framework was built for.
15
16use crate::tactic::{ProofState, Tactic};
17
18/// How a rule participates in search.
19#[derive(Clone, Copy, Debug, PartialEq, Eq)]
20pub enum Safety {
21 /// Never loses provability — applied eagerly, no branch point.
22 Safe,
23 /// May not lead to a proof — forks the search; higher priority tried first.
24 Unsafe(u8),
25}
26
27/// The role a rule plays (currently advisory metadata for ordering/diagnostics;
28/// the tactic itself encodes the actual transformation).
29#[derive(Clone, Copy, Debug, PartialEq, Eq)]
30pub enum RuleKind {
31 Intro,
32 Elim,
33 Forward,
34 Destruct,
35}
36
37/// A search rule: a named tactic with a role and a safety classification.
38pub struct Rule {
39 pub name: String,
40 pub kind: RuleKind,
41 pub safety: Safety,
42 pub tactic: Tactic,
43}
44
45impl Rule {
46 pub fn new(name: &str, kind: RuleKind, safety: Safety, tactic: Tactic) -> Self {
47 Rule {
48 name: name.to_string(),
49 kind,
50 safety,
51 tactic,
52 }
53 }
54}
55
56/// An extensible collection of search rules.
57#[derive(Default)]
58pub struct RuleSet {
59 rules: Vec<Rule>,
60}
61
62/// What the search explored.
63#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
64pub struct SearchStats {
65 pub nodes_expanded: usize,
66 pub succeeded: bool,
67}
68
69/// Default node budget for a best-first search.
70const DEFAULT_NODE_BUDGET: usize = 2000;
71
72impl RuleSet {
73 pub fn new() -> Self {
74 Self::default()
75 }
76
77 pub fn register(&mut self, rule: Rule) {
78 self.rules.push(rule);
79 }
80
81 pub fn len(&self) -> usize {
82 self.rules.len()
83 }
84
85 pub fn is_empty(&self) -> bool {
86 self.rules.is_empty()
87 }
88
89 /// Best-first search from `st`. Applies safe rules eagerly at each node,
90 /// then forks on unsafe rules in priority order. Succeeds (leaving `st` at
91 /// a closed proof state) when some branch drives the open goals to zero.
92 pub fn search(&self, st: &mut ProofState) -> SearchStats {
93 self.search_bounded(st, DEFAULT_NODE_BUDGET)
94 }
95
96 pub fn search_bounded(&self, st: &mut ProofState, budget: usize) -> SearchStats {
97 let mut stats = SearchStats::default();
98 // A best-first frontier of `(path-cost, state)`; the next node expanded
99 // is the one with the fewest open goals, then the cheapest path. The
100 // frontier stays small for the goal sizes this targets.
101 let mut frontier: Vec<(usize, ProofState)> = vec![(0, st.clone())];
102 let rules = self.rules_by_priority();
103
104 while let Some(best_idx) = pick_best(&frontier) {
105 if stats.nodes_expanded >= budget {
106 break;
107 }
108 let (cost, node) = frontier.swap_remove(best_idx);
109 stats.nodes_expanded += 1;
110
111 if node.open_goals() == 0 {
112 *st = node;
113 stats.succeeded = true;
114 return stats;
115 }
116
117 // Fork on each rule, highest priority (and safe) first. A safe rule
118 // adds no path-cost (it never loses provability), so its branch is
119 // explored ahead of any unsafe alternative.
120 for rule in &rules {
121 let mut child = node.clone();
122 if (rule.tactic)(&mut child).is_ok() && !state_eq(&child, &node) {
123 frontier.push((cost + rule_cost(rule), child));
124 }
125 }
126 }
127 stats
128 }
129
130 /// Rules ordered for expansion: safe first, then unsafe by descending priority.
131 fn rules_by_priority(&self) -> Vec<&Rule> {
132 let mut r: Vec<&Rule> = self.rules.iter().collect();
133 r.sort_by_key(|rule| std::cmp::Reverse(priority_of(rule)));
134 r
135 }
136}
137
138/// The path-cost of taking a rule: zero for safe rules (free), and the inverse
139/// of priority for unsafe ones, so high-priority unsafe branches are cheaper.
140fn rule_cost(rule: &Rule) -> usize {
141 match rule.safety {
142 Safety::Safe => 0,
143 Safety::Unsafe(p) => (255 - p as usize) + 1,
144 }
145}
146
147fn priority_of(rule: &Rule) -> u8 {
148 match rule.safety {
149 Safety::Unsafe(p) => p,
150 Safety::Safe => 255,
151 }
152}
153
154/// Cheap progress check: two states differ if their open-goal count or focused
155/// target differ (enough to avoid enqueuing a no-op rule application).
156fn state_eq(a: &ProofState, b: &ProofState) -> bool {
157 a.open_goals() == b.open_goals() && a.focused_target() == b.focused_target()
158}
159
160/// The frontier node to expand next: fewest open goals, then cheapest path.
161fn pick_best(frontier: &[(usize, ProofState)]) -> Option<usize> {
162 frontier
163 .iter()
164 .enumerate()
165 .min_by_key(|(_, (cost, st))| (st.open_goals(), *cost))
166 .map(|(i, _)| i)
167}
168
169/// The default rule set: `auto` as the sole unsafe fallback — so a default
170/// `search` closes exactly what `auto` closes, the regression baseline.
171pub fn default_ruleset() -> RuleSet {
172 let mut rs = RuleSet::new();
173 rs.register(Rule::new(
174 "auto",
175 RuleKind::Elim,
176 Safety::Unsafe(10),
177 crate::tactic::combinators::auto(),
178 ));
179 rs
180}