Skip to main content

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}