Skip to main content

logicaffeine_proof/
unify.rs

1//! First-order unification for proof search.
2//!
3//! Implements Robinson's Unification Algorithm with occurs check. This is the
4//! core pattern-matching engine that enables logical reasoning.
5//!
6//! ## What Unification Does
7//!
8//! Unification finds a substitution that makes two terms identical:
9//!
10//! | Pattern | Target | Substitution |
11//! |---------|--------|--------------|
12//! | `Mortal(x)` | `Mortal(Socrates)` | `{x ↦ Socrates}` |
13//! | `Add(Succ(n), 0)` | `Add(Succ(Zero), 0)` | `{n ↦ Zero}` |
14//! | `f(x, x)` | `f(a, b)` | Fails (x can't be both a and b) |
15//!
16//! ## Occurs Check
17//!
18//! The occurs check prevents infinite terms. `x = f(x)` has no finite solution
19//! since it would require `x = f(f(f(...)))`. We reject such unifications.
20//!
21//! ## Alpha-Equivalence
22//!
23//! Bound variable names are arbitrary: `∃e P(e) ≡ ∃x P(x)`. We handle this
24//! by substituting fresh constants for bound variables when unifying
25//! quantified expressions.
26//!
27//! # See Also
28//!
29//! * [`beta_reduce`] - Normalizes lambda applications before unification
30//! * [`ProofTerm`] - The term representation being unified
31//! * [`ProofExpr`] - The expression representation for higher-order unification
32
33use std::collections::HashMap;
34use std::sync::atomic::{AtomicUsize, Ordering};
35
36use crate::error::{ProofError, ProofResult};
37use crate::{MatchArm, ProofExpr, ProofTerm};
38
39/// A substitution mapping variable names to terms.
40///
41/// Substitutions are the output of unification. Applying a substitution
42/// to both sides of a unification problem yields identical terms.
43///
44/// # Example
45///
46/// After unifying `Mortal(x)` with `Mortal(Socrates)`:
47///
48/// ```text
49/// { "x" ↦ Constant("Socrates") }
50/// ```
51///
52/// # Operations
53///
54/// * [`unify_terms`] - Creates substitutions from term unification
55/// * [`apply_subst_to_term`] - Applies substitution to a term
56/// * [`compose_substitutions`] - Combines two substitutions
57pub type Substitution = HashMap<String, ProofTerm>;
58
59/// Substitution for expression-level meta-variables (holes).
60///
61/// Maps hole names to their solutions, typically lambda abstractions
62/// inferred during higher-order pattern unification.
63///
64/// # Example
65///
66/// Solving `?P(x) = Even(x)` yields:
67///
68/// ```text
69/// { "P" ↦ Lambda { variable: "x", body: Even(x) } }
70/// ```
71///
72/// # See Also
73///
74/// * [`unify_pattern`] - Creates expression substitutions via Miller pattern unification
75pub type ExprSubstitution = HashMap<String, ProofExpr>;
76
77// =============================================================================
78// ALPHA-EQUIVALENCE SUPPORT
79// =============================================================================
80
81/// Global counter for generating fresh constants during alpha-renaming.
82static ALPHA_COUNTER: AtomicUsize = AtomicUsize::new(0);
83
84/// Generate a fresh constant for alpha-renaming.
85/// Uses a prefix that cannot appear in user input to avoid collisions.
86fn fresh_alpha_constant() -> ProofTerm {
87    let id = ALPHA_COUNTER.fetch_add(1, Ordering::SeqCst);
88    ProofTerm::Constant(format!("#α{}", id))
89}
90
91// =============================================================================
92// BETA-REDUCTION
93// =============================================================================
94
95/// Check if an expression is a constructor form (safe for fix unfolding).
96/// Only constructors are safe guards against non-termination.
97fn is_constructor_form(expr: &ProofExpr) -> bool {
98    matches!(expr, ProofExpr::Ctor { .. })
99}
100
101/// Beta-reduce an expression to Weak Head Normal Form (WHNF).
102///
103/// Normalizes lambda applications and match expressions, enabling unification
104/// to work on structurally equivalent terms.
105///
106/// # Reduction Rules
107///
108/// | Redex | Reduction |
109/// |-------|-----------|
110/// | `(λx. body)(arg)` | `body[x := arg]` (beta) |
111/// | `(fix f. body) (Ctor ...)` | `body[f := fix f. body] (Ctor ...)` (fix unfolding) |
112/// | `match (Ctor args) { ... }` | Selected arm with args substituted (iota) |
113///
114/// # Weak Head Normal Form
115///
116/// WHNF stops at the outermost constructor or lambda. It does not reduce
117/// under binders, making it efficient for unification purposes.
118///
119/// # Termination
120///
121/// Fix unfolding only occurs when the argument is a constructor (`Ctor`),
122/// ensuring termination for well-typed terms.
123///
124/// # Example
125///
126/// ```text
127/// beta_reduce((λx. P(x))(Socrates))
128/// → P(Socrates)
129///
130/// beta_reduce(match Zero { Zero => True, Succ(k) => False })
131/// → True
132/// ```
133///
134/// # See Also
135///
136/// * [`unify_exprs`] - Calls beta_reduce before comparing expressions
137/// * [`certifier::certify`](crate::certifier::certify) - Uses normalized terms for kernel conversion
138pub fn beta_reduce(expr: &ProofExpr) -> ProofExpr {
139    match expr {
140        // Beta-reduction and Fix unfolding
141        ProofExpr::App(func, arg) => {
142            // First, reduce both function and argument
143            let func_reduced = beta_reduce(func);
144            let arg_reduced = beta_reduce(arg);
145
146            match func_reduced {
147                // Beta-reduction: (λx. body)(arg) → body[x := arg]
148                ProofExpr::Lambda { variable, body } => {
149                    let result = substitute_expr_for_var(&body, &variable, &arg_reduced);
150                    // Recursively reduce the result (handle nested redexes)
151                    beta_reduce(&result)
152                }
153
154                // Fix unfolding: (fix f. body) arg → body[f := fix f. body] arg
155                // Only unfold when arg is a constructor (guard against non-termination)
156                ProofExpr::Fixpoint { ref name, ref body } if is_constructor_form(&arg_reduced) => {
157                    // Substitute fix for f in body
158                    let fix_expr = ProofExpr::Fixpoint {
159                        name: name.clone(),
160                        body: body.clone(),
161                    };
162                    let unfolded = substitute_expr_for_var(body, name, &fix_expr);
163                    // Apply unfolded body to arg and reduce
164                    let applied = ProofExpr::App(Box::new(unfolded), Box::new(arg_reduced));
165                    beta_reduce(&applied)
166                }
167
168                _ => {
169                    // No reduction possible, return normalized application
170                    ProofExpr::App(Box::new(func_reduced), Box::new(arg_reduced))
171                }
172            }
173        }
174
175        // Reduce inside binary connectives
176        ProofExpr::And(l, r) => ProofExpr::And(Box::new(beta_reduce(l)), Box::new(beta_reduce(r))),
177        ProofExpr::Or(l, r) => ProofExpr::Or(Box::new(beta_reduce(l)), Box::new(beta_reduce(r))),
178        ProofExpr::Implies(l, r) => {
179            ProofExpr::Implies(Box::new(beta_reduce(l)), Box::new(beta_reduce(r)))
180        }
181        ProofExpr::Iff(l, r) => ProofExpr::Iff(Box::new(beta_reduce(l)), Box::new(beta_reduce(r))),
182        ProofExpr::Not(inner) => ProofExpr::Not(Box::new(beta_reduce(inner))),
183
184        // Reduce inside quantifiers
185        ProofExpr::ForAll { variable, body } => ProofExpr::ForAll {
186            variable: variable.clone(),
187            body: Box::new(beta_reduce(body)),
188        },
189        ProofExpr::Exists { variable, body } => ProofExpr::Exists {
190            variable: variable.clone(),
191            body: Box::new(beta_reduce(body)),
192        },
193
194        // Reduce inside lambda bodies (but not the lambda itself - that's a value)
195        ProofExpr::Lambda { variable, body } => ProofExpr::Lambda {
196            variable: variable.clone(),
197            body: Box::new(beta_reduce(body)),
198        },
199
200        // Reduce inside modal and temporal operators
201        ProofExpr::Modal {
202            domain,
203            force,
204            flavor,
205            body,
206        } => ProofExpr::Modal {
207            domain: domain.clone(),
208            force: *force,
209            flavor: flavor.clone(),
210            body: Box::new(beta_reduce(body)),
211        },
212        ProofExpr::Counterfactual {
213            antecedent,
214            consequent,
215        } => ProofExpr::Counterfactual {
216            antecedent: Box::new(beta_reduce(antecedent)),
217            consequent: Box::new(beta_reduce(consequent)),
218        },
219        ProofExpr::Temporal { operator, body } => ProofExpr::Temporal {
220            operator: operator.clone(),
221            body: Box::new(beta_reduce(body)),
222        },
223        ProofExpr::TemporalBinary {
224            operator,
225            left,
226            right,
227        } => ProofExpr::TemporalBinary {
228            operator: operator.clone(),
229            left: Box::new(beta_reduce(left)),
230            right: Box::new(beta_reduce(right)),
231        },
232
233        // Reduce inside Ctor arguments
234        ProofExpr::Ctor { name, args } => ProofExpr::Ctor {
235            name: name.clone(),
236            args: args.iter().map(beta_reduce).collect(),
237        },
238
239        // Iota reduction: match (Ctor args) with arms → selected arm body
240        ProofExpr::Match { scrutinee, arms } => {
241            let reduced_scrutinee = beta_reduce(scrutinee);
242
243            // Try iota reduction: if scrutinee is a Ctor, select matching arm
244            if let ProofExpr::Ctor {
245                name: ctor_name,
246                args: ctor_args,
247            } = &reduced_scrutinee
248            {
249                for arm in arms {
250                    if &arm.ctor == ctor_name {
251                        // Found matching arm - substitute constructor args for bindings
252                        let mut result = arm.body.clone();
253                        for (binding, arg) in arm.bindings.iter().zip(ctor_args.iter()) {
254                            result = substitute_expr_for_var(&result, binding, arg);
255                        }
256                        // Continue reducing the result
257                        return beta_reduce(&result);
258                    }
259                }
260            }
261
262            // No iota reduction possible - just reduce subexpressions
263            ProofExpr::Match {
264                scrutinee: Box::new(reduced_scrutinee),
265                arms: arms
266                    .iter()
267                    .map(|arm| MatchArm {
268                        ctor: arm.ctor.clone(),
269                        bindings: arm.bindings.clone(),
270                        body: beta_reduce(&arm.body),
271                    })
272                    .collect(),
273            }
274        }
275
276        // Reduce inside Fixpoint
277        ProofExpr::Fixpoint { name, body } => ProofExpr::Fixpoint {
278            name: name.clone(),
279            body: Box::new(beta_reduce(body)),
280        },
281
282        // Atomic expressions don't reduce
283        ProofExpr::Predicate { .. }
284        | ProofExpr::Identity(_, _)
285        | ProofExpr::Atom(_)
286        | ProofExpr::NeoEvent { .. }
287        | ProofExpr::TypedVar { .. }
288        | ProofExpr::Unsupported(_)
289        | ProofExpr::Hole(_)
290        | ProofExpr::Term(_) => expr.clone(),
291    }
292}
293
294/// Collect the free variables of an expression (complete, binder-aware).
295///
296/// Unlike [`collect_free_vars`], this descends into every binder form (modal,
297/// temporal, event, match, fixpoint, …) so it is sound to use for capture
298/// detection.
299fn free_vars_expr(
300    expr: &ProofExpr,
301    bound: &mut Vec<String>,
302    acc: &mut std::collections::HashSet<String>,
303) {
304    match expr {
305        ProofExpr::Atom(s) => {
306            if !bound.iter().any(|b| b == s) {
307                acc.insert(s.clone());
308            }
309        }
310        ProofExpr::Predicate { args, .. } => {
311            for a in args {
312                free_vars_term(a, bound, acc);
313            }
314        }
315        ProofExpr::Identity(l, r) => {
316            free_vars_term(l, bound, acc);
317            free_vars_term(r, bound, acc);
318        }
319        ProofExpr::And(l, r)
320        | ProofExpr::Or(l, r)
321        | ProofExpr::Implies(l, r)
322        | ProofExpr::Iff(l, r) => {
323            free_vars_expr(l, bound, acc);
324            free_vars_expr(r, bound, acc);
325        }
326        ProofExpr::Not(i) => free_vars_expr(i, bound, acc),
327        ProofExpr::ForAll { variable, body }
328        | ProofExpr::Exists { variable, body }
329        | ProofExpr::Lambda { variable, body } => {
330            bound.push(variable.clone());
331            free_vars_expr(body, bound, acc);
332            bound.pop();
333        }
334        ProofExpr::Modal { body, .. } => free_vars_expr(body, bound, acc),
335        ProofExpr::Counterfactual {
336            antecedent,
337            consequent,
338        } => {
339            free_vars_expr(antecedent, bound, acc);
340            free_vars_expr(consequent, bound, acc);
341        }
342        ProofExpr::Temporal { body, .. } => free_vars_expr(body, bound, acc),
343        ProofExpr::TemporalBinary { left, right, .. } => {
344            free_vars_expr(left, bound, acc);
345            free_vars_expr(right, bound, acc);
346        }
347        ProofExpr::App(f, a) => {
348            free_vars_expr(f, bound, acc);
349            free_vars_expr(a, bound, acc);
350        }
351        ProofExpr::NeoEvent {
352            event_var, roles, ..
353        } => {
354            bound.push(event_var.clone());
355            for (_, t) in roles {
356                free_vars_term(t, bound, acc);
357            }
358            bound.pop();
359        }
360        ProofExpr::Ctor { args, .. } => {
361            for a in args {
362                free_vars_expr(a, bound, acc);
363            }
364        }
365        ProofExpr::Match { scrutinee, arms } => {
366            free_vars_expr(scrutinee, bound, acc);
367            for arm in arms {
368                let depth = arm.bindings.len();
369                for b in &arm.bindings {
370                    bound.push(b.clone());
371                }
372                free_vars_expr(&arm.body, bound, acc);
373                for _ in 0..depth {
374                    bound.pop();
375                }
376            }
377        }
378        ProofExpr::Fixpoint { name, body } => {
379            bound.push(name.clone());
380            free_vars_expr(body, bound, acc);
381            bound.pop();
382        }
383        ProofExpr::TypedVar { name, .. } => {
384            if !bound.iter().any(|b| b == name) {
385                acc.insert(name.clone());
386            }
387        }
388        ProofExpr::Hole(_) | ProofExpr::Unsupported(_) => {}
389        ProofExpr::Term(t) => free_vars_term(t, bound, acc),
390    }
391}
392
393/// Whether `var` occurs free in `expr` — binder-aware, see [`free_vars_expr`].
394pub(crate) fn occurs_free(var: &str, expr: &ProofExpr) -> bool {
395    let mut free = std::collections::HashSet::new();
396    free_vars_expr(expr, &mut Vec::new(), &mut free);
397    free.contains(var)
398}
399
400fn free_vars_term(term: &ProofTerm, bound: &[String], acc: &mut std::collections::HashSet<String>) {
401    match term {
402        ProofTerm::Variable(s) | ProofTerm::BoundVarRef(s) => {
403            if !bound.iter().any(|b| b == s) {
404                acc.insert(s.clone());
405            }
406        }
407        ProofTerm::Constant(_) => {}
408        ProofTerm::Function(_, args) | ProofTerm::Group(args) => {
409            for a in args {
410                free_vars_term(a, bound, acc);
411            }
412        }
413    }
414}
415
416/// Collect every name appearing anywhere in an expression (bound or free) so a
417/// fresh binder name can be chosen that collides with nothing.
418fn all_names_expr(expr: &ProofExpr, acc: &mut std::collections::HashSet<String>) {
419    match expr {
420        ProofExpr::Atom(s) => {
421            acc.insert(s.clone());
422        }
423        ProofExpr::Predicate { args, .. } => {
424            for a in args {
425                all_names_term(a, acc);
426            }
427        }
428        ProofExpr::Identity(l, r) => {
429            all_names_term(l, acc);
430            all_names_term(r, acc);
431        }
432        ProofExpr::And(l, r)
433        | ProofExpr::Or(l, r)
434        | ProofExpr::Implies(l, r)
435        | ProofExpr::Iff(l, r) => {
436            all_names_expr(l, acc);
437            all_names_expr(r, acc);
438        }
439        ProofExpr::Not(i) => all_names_expr(i, acc),
440        ProofExpr::ForAll { variable, body }
441        | ProofExpr::Exists { variable, body }
442        | ProofExpr::Lambda { variable, body } => {
443            acc.insert(variable.clone());
444            all_names_expr(body, acc);
445        }
446        ProofExpr::Modal { body, .. } => all_names_expr(body, acc),
447        ProofExpr::Counterfactual {
448            antecedent,
449            consequent,
450        } => {
451            all_names_expr(antecedent, acc);
452            all_names_expr(consequent, acc);
453        }
454        ProofExpr::Temporal { body, .. } => all_names_expr(body, acc),
455        ProofExpr::TemporalBinary { left, right, .. } => {
456            all_names_expr(left, acc);
457            all_names_expr(right, acc);
458        }
459        ProofExpr::App(f, a) => {
460            all_names_expr(f, acc);
461            all_names_expr(a, acc);
462        }
463        ProofExpr::NeoEvent {
464            event_var, roles, ..
465        } => {
466            acc.insert(event_var.clone());
467            for (_, t) in roles {
468                all_names_term(t, acc);
469            }
470        }
471        ProofExpr::Ctor { args, .. } => {
472            for a in args {
473                all_names_expr(a, acc);
474            }
475        }
476        ProofExpr::Match { scrutinee, arms } => {
477            all_names_expr(scrutinee, acc);
478            for arm in arms {
479                for b in &arm.bindings {
480                    acc.insert(b.clone());
481                }
482                all_names_expr(&arm.body, acc);
483            }
484        }
485        ProofExpr::Fixpoint { name, body } => {
486            acc.insert(name.clone());
487            all_names_expr(body, acc);
488        }
489        ProofExpr::TypedVar { name, .. } => {
490            acc.insert(name.clone());
491        }
492        ProofExpr::Hole(_) | ProofExpr::Unsupported(_) => {}
493        ProofExpr::Term(t) => all_names_term(t, acc),
494    }
495}
496
497fn all_names_term(term: &ProofTerm, acc: &mut std::collections::HashSet<String>) {
498    match term {
499        ProofTerm::Constant(s) | ProofTerm::Variable(s) | ProofTerm::BoundVarRef(s) => {
500            acc.insert(s.clone());
501        }
502        ProofTerm::Function(_, args) | ProofTerm::Group(args) => {
503            for a in args {
504                all_names_term(a, acc);
505            }
506        }
507    }
508}
509
510/// Pick a binder name derived from `base` that collides with nothing in `avoid`.
511fn fresh_proof_name(base: &str, avoid: &std::collections::HashSet<String>) -> String {
512    let mut candidate = format!("{}'", base);
513    let mut n: u32 = 0;
514    while avoid.contains(&candidate) {
515        n += 1;
516        candidate = format!("{}'{}", base, n);
517    }
518    candidate
519}
520
521/// Rename free occurrences of `from` to `to` in an expression, preserving each
522/// occurrence's kind (Atom stays Atom, Variable stays Variable). `to` must be
523/// globally fresh in `expr`, so the rename itself cannot capture. Stops at
524/// binders that re-bind `from`.
525fn alpha_rename_expr(expr: &ProofExpr, from: &str, to: &str) -> ProofExpr {
526    match expr {
527        ProofExpr::Atom(s) if s == from => ProofExpr::Atom(to.to_string()),
528        ProofExpr::Atom(s) => ProofExpr::Atom(s.clone()),
529        ProofExpr::Predicate { name, args, world } => ProofExpr::Predicate {
530            name: name.clone(),
531            args: args
532                .iter()
533                .map(|a| alpha_rename_term(a, from, to))
534                .collect(),
535            world: world.clone(),
536        },
537        ProofExpr::Identity(l, r) => ProofExpr::Identity(
538            alpha_rename_term(l, from, to),
539            alpha_rename_term(r, from, to),
540        ),
541        ProofExpr::And(l, r) => ProofExpr::And(
542            Box::new(alpha_rename_expr(l, from, to)),
543            Box::new(alpha_rename_expr(r, from, to)),
544        ),
545        ProofExpr::Or(l, r) => ProofExpr::Or(
546            Box::new(alpha_rename_expr(l, from, to)),
547            Box::new(alpha_rename_expr(r, from, to)),
548        ),
549        ProofExpr::Implies(l, r) => ProofExpr::Implies(
550            Box::new(alpha_rename_expr(l, from, to)),
551            Box::new(alpha_rename_expr(r, from, to)),
552        ),
553        ProofExpr::Iff(l, r) => ProofExpr::Iff(
554            Box::new(alpha_rename_expr(l, from, to)),
555            Box::new(alpha_rename_expr(r, from, to)),
556        ),
557        ProofExpr::Not(i) => ProofExpr::Not(Box::new(alpha_rename_expr(i, from, to))),
558        ProofExpr::ForAll { variable, body } => {
559            if variable == from {
560                expr.clone()
561            } else {
562                ProofExpr::ForAll {
563                    variable: variable.clone(),
564                    body: Box::new(alpha_rename_expr(body, from, to)),
565                }
566            }
567        }
568        ProofExpr::Exists { variable, body } => {
569            if variable == from {
570                expr.clone()
571            } else {
572                ProofExpr::Exists {
573                    variable: variable.clone(),
574                    body: Box::new(alpha_rename_expr(body, from, to)),
575                }
576            }
577        }
578        ProofExpr::Lambda { variable, body } => {
579            if variable == from {
580                expr.clone()
581            } else {
582                ProofExpr::Lambda {
583                    variable: variable.clone(),
584                    body: Box::new(alpha_rename_expr(body, from, to)),
585                }
586            }
587        }
588        ProofExpr::Modal {
589            domain,
590            force,
591            flavor,
592            body,
593        } => ProofExpr::Modal {
594            domain: domain.clone(),
595            force: *force,
596            flavor: flavor.clone(),
597            body: Box::new(alpha_rename_expr(body, from, to)),
598        },
599        ProofExpr::Counterfactual {
600            antecedent,
601            consequent,
602        } => ProofExpr::Counterfactual {
603            antecedent: Box::new(alpha_rename_expr(antecedent, from, to)),
604            consequent: Box::new(alpha_rename_expr(consequent, from, to)),
605        },
606        ProofExpr::Temporal { operator, body } => ProofExpr::Temporal {
607            operator: operator.clone(),
608            body: Box::new(alpha_rename_expr(body, from, to)),
609        },
610        ProofExpr::TemporalBinary {
611            operator,
612            left,
613            right,
614        } => ProofExpr::TemporalBinary {
615            operator: operator.clone(),
616            left: Box::new(alpha_rename_expr(left, from, to)),
617            right: Box::new(alpha_rename_expr(right, from, to)),
618        },
619        ProofExpr::App(f, a) => ProofExpr::App(
620            Box::new(alpha_rename_expr(f, from, to)),
621            Box::new(alpha_rename_expr(a, from, to)),
622        ),
623        ProofExpr::NeoEvent {
624            event_var,
625            verb,
626            roles,
627        } => {
628            if event_var == from {
629                expr.clone()
630            } else {
631                ProofExpr::NeoEvent {
632                    event_var: event_var.clone(),
633                    verb: verb.clone(),
634                    roles: roles
635                        .iter()
636                        .map(|(r, t)| (r.clone(), alpha_rename_term(t, from, to)))
637                        .collect(),
638                }
639            }
640        }
641        ProofExpr::Ctor { name, args } => ProofExpr::Ctor {
642            name: name.clone(),
643            args: args
644                .iter()
645                .map(|a| alpha_rename_expr(a, from, to))
646                .collect(),
647        },
648        ProofExpr::Match { scrutinee, arms } => ProofExpr::Match {
649            scrutinee: Box::new(alpha_rename_expr(scrutinee, from, to)),
650            arms: arms
651                .iter()
652                .map(|arm| {
653                    if arm.bindings.iter().any(|b| b == from) {
654                        arm.clone()
655                    } else {
656                        MatchArm {
657                            ctor: arm.ctor.clone(),
658                            bindings: arm.bindings.clone(),
659                            body: alpha_rename_expr(&arm.body, from, to),
660                        }
661                    }
662                })
663                .collect(),
664        },
665        ProofExpr::Fixpoint { name, body } => {
666            if name == from {
667                expr.clone()
668            } else {
669                ProofExpr::Fixpoint {
670                    name: name.clone(),
671                    body: Box::new(alpha_rename_expr(body, from, to)),
672                }
673            }
674        }
675        ProofExpr::TypedVar { name, typename } => {
676            if name == from {
677                ProofExpr::TypedVar {
678                    name: to.to_string(),
679                    typename: typename.clone(),
680                }
681            } else {
682                expr.clone()
683            }
684        }
685        ProofExpr::Hole(_) | ProofExpr::Unsupported(_) => expr.clone(),
686        ProofExpr::Term(t) => ProofExpr::Term(alpha_rename_term(t, from, to)),
687    }
688}
689
690fn alpha_rename_term(term: &ProofTerm, from: &str, to: &str) -> ProofTerm {
691    match term {
692        ProofTerm::Variable(s) if s == from => ProofTerm::Variable(to.to_string()),
693        ProofTerm::BoundVarRef(s) if s == from => ProofTerm::BoundVarRef(to.to_string()),
694        ProofTerm::Variable(s) => ProofTerm::Variable(s.clone()),
695        ProofTerm::BoundVarRef(s) => ProofTerm::BoundVarRef(s.clone()),
696        ProofTerm::Constant(s) => ProofTerm::Constant(s.clone()),
697        ProofTerm::Function(n, args) => ProofTerm::Function(
698            n.clone(),
699            args.iter()
700                .map(|a| alpha_rename_term(a, from, to))
701                .collect(),
702        ),
703        ProofTerm::Group(args) => ProofTerm::Group(
704            args.iter()
705                .map(|a| alpha_rename_term(a, from, to))
706                .collect(),
707        ),
708    }
709}
710
711/// Choose a (binder, body) pair for a single-binder form so that substituting
712/// `replacement` into `body` cannot capture a free variable of `replacement`.
713/// If `variable` is free in `replacement`, the binder is alpha-renamed fresh.
714fn rebind_for_subst(
715    variable: &str,
716    inner: &ProofExpr,
717    repl_fvs: &std::collections::HashSet<String>,
718) -> (String, ProofExpr) {
719    if repl_fvs.contains(variable) {
720        let mut avoid = repl_fvs.clone();
721        all_names_expr(inner, &mut avoid);
722        let fresh = fresh_proof_name(variable, &avoid);
723        let renamed = alpha_rename_expr(inner, variable, &fresh);
724        (fresh, renamed)
725    } else {
726        (variable.to_string(), inner.clone())
727    }
728}
729
730/// Substitute an expression for a variable name in another expression.
731///
732/// Used for beta-reduction: (λx. body)(arg) → body[x := arg]
733///
734/// This is capture-avoiding: a binder whose name is free in `replacement` is
735/// alpha-renamed to a fresh name before the substitution descends into it, so a
736/// free variable of the argument is never captured by an inner binder.
737fn substitute_expr_for_var(body: &ProofExpr, var: &str, replacement: &ProofExpr) -> ProofExpr {
738    let mut repl_fvs = std::collections::HashSet::new();
739    free_vars_expr(replacement, &mut Vec::new(), &mut repl_fvs);
740    subst_expr_avoiding(
741        body,
742        var,
743        replacement,
744        &repl_fvs,
745        Occurrences::TermsAndAtoms,
746    )
747}
748
749/// Instantiate one binder: `body[var := t]`, the formula a quantifier's body states of `t`.
750///
751/// Every free occurrence of `var` in a term position becomes `t`, once: `t` is not read again, so it may
752/// mention `var` itself (`P(a)[a := succ(a)]` is `P(succ(a))`). A binder that rebinds `var` shadows it, and a
753/// binder whose name is free in `t` is renamed first, so no free variable of `t` is captured. A propositional
754/// atom is not a term position and is left as it is.
755pub fn instantiate_expr(body: &ProofExpr, var: &str, t: &ProofTerm) -> ProofExpr {
756    let mut repl_fvs = std::collections::HashSet::new();
757    free_vars_term(t, &[], &mut repl_fvs);
758    subst_expr_avoiding(
759        body,
760        var,
761        &ProofExpr::Term(t.clone()),
762        &repl_fvs,
763        Occurrences::Terms,
764    )
765}
766
767/// Where [`subst_expr_avoiding`] replaces the variable.
768#[derive(Clone, Copy, PartialEq, Eq)]
769enum Occurrences {
770    /// Term positions only: instantiating a binder with a term.
771    Terms,
772    /// Term positions and propositional atoms: β-reducing with an expression argument, where a
773    /// term-level function's variable may be written as an atom.
774    TermsAndAtoms,
775}
776
777fn subst_expr_avoiding(
778    body: &ProofExpr,
779    var: &str,
780    replacement: &ProofExpr,
781    repl_fvs: &std::collections::HashSet<String>,
782    at: Occurrences,
783) -> ProofExpr {
784    match body {
785        ProofExpr::Predicate { name, args, world } => ProofExpr::Predicate {
786            name: name.clone(),
787            args: args
788                .iter()
789                .map(|t| substitute_term_for_var(t, var, replacement))
790                .collect(),
791            world: world.clone(),
792        },
793
794        ProofExpr::Identity(l, r) => ProofExpr::Identity(
795            substitute_term_for_var(l, var, replacement),
796            substitute_term_for_var(r, var, replacement),
797        ),
798
799        ProofExpr::Atom(a) => {
800            // If the atom matches the variable, replace it
801            if a == var && at == Occurrences::TermsAndAtoms {
802                replacement.clone()
803            } else {
804                ProofExpr::Atom(a.clone())
805            }
806        }
807
808        ProofExpr::And(l, r) => ProofExpr::And(
809            Box::new(subst_expr_avoiding(l, var, replacement, repl_fvs, at)),
810            Box::new(subst_expr_avoiding(r, var, replacement, repl_fvs, at)),
811        ),
812        ProofExpr::Or(l, r) => ProofExpr::Or(
813            Box::new(subst_expr_avoiding(l, var, replacement, repl_fvs, at)),
814            Box::new(subst_expr_avoiding(r, var, replacement, repl_fvs, at)),
815        ),
816        ProofExpr::Implies(l, r) => ProofExpr::Implies(
817            Box::new(subst_expr_avoiding(l, var, replacement, repl_fvs, at)),
818            Box::new(subst_expr_avoiding(r, var, replacement, repl_fvs, at)),
819        ),
820        ProofExpr::Iff(l, r) => ProofExpr::Iff(
821            Box::new(subst_expr_avoiding(l, var, replacement, repl_fvs, at)),
822            Box::new(subst_expr_avoiding(r, var, replacement, repl_fvs, at)),
823        ),
824        ProofExpr::Not(inner) => ProofExpr::Not(Box::new(subst_expr_avoiding(
825            inner,
826            var,
827            replacement,
828            repl_fvs,
829            at,
830        ))),
831
832        // Quantifiers: shadowing stops substitution; otherwise alpha-rename the
833        // binder away from the replacement's free vars to avoid capture.
834        ProofExpr::ForAll {
835            variable,
836            body: inner,
837        } => {
838            if variable == var {
839                body.clone()
840            } else {
841                let (v, b) = rebind_for_subst(variable, inner, repl_fvs);
842                ProofExpr::ForAll {
843                    variable: v,
844                    body: Box::new(subst_expr_avoiding(&b, var, replacement, repl_fvs, at)),
845                }
846            }
847        }
848        ProofExpr::Exists {
849            variable,
850            body: inner,
851        } => {
852            if variable == var {
853                body.clone()
854            } else {
855                let (v, b) = rebind_for_subst(variable, inner, repl_fvs);
856                ProofExpr::Exists {
857                    variable: v,
858                    body: Box::new(subst_expr_avoiding(&b, var, replacement, repl_fvs, at)),
859                }
860            }
861        }
862
863        ProofExpr::Lambda {
864            variable,
865            body: inner,
866        } => {
867            if variable == var {
868                body.clone()
869            } else {
870                let (v, b) = rebind_for_subst(variable, inner, repl_fvs);
871                ProofExpr::Lambda {
872                    variable: v,
873                    body: Box::new(subst_expr_avoiding(&b, var, replacement, repl_fvs, at)),
874                }
875            }
876        }
877
878        ProofExpr::App(f, a) => ProofExpr::App(
879            Box::new(subst_expr_avoiding(f, var, replacement, repl_fvs, at)),
880            Box::new(subst_expr_avoiding(a, var, replacement, repl_fvs, at)),
881        ),
882
883        ProofExpr::Modal {
884            domain,
885            force,
886            flavor,
887            body: inner,
888        } => ProofExpr::Modal {
889            domain: domain.clone(),
890            force: *force,
891            flavor: flavor.clone(),
892            body: Box::new(subst_expr_avoiding(inner, var, replacement, repl_fvs, at)),
893        },
894
895        ProofExpr::Counterfactual {
896            antecedent,
897            consequent,
898        } => ProofExpr::Counterfactual {
899            antecedent: Box::new(subst_expr_avoiding(
900                antecedent,
901                var,
902                replacement,
903                repl_fvs,
904                at,
905            )),
906            consequent: Box::new(subst_expr_avoiding(
907                consequent,
908                var,
909                replacement,
910                repl_fvs,
911                at,
912            )),
913        },
914
915        ProofExpr::Temporal {
916            operator,
917            body: inner,
918        } => ProofExpr::Temporal {
919            operator: operator.clone(),
920            body: Box::new(subst_expr_avoiding(inner, var, replacement, repl_fvs, at)),
921        },
922
923        ProofExpr::TemporalBinary {
924            operator,
925            left,
926            right,
927        } => ProofExpr::TemporalBinary {
928            operator: operator.clone(),
929            left: Box::new(subst_expr_avoiding(left, var, replacement, repl_fvs, at)),
930            right: Box::new(subst_expr_avoiding(right, var, replacement, repl_fvs, at)),
931        },
932
933        ProofExpr::NeoEvent {
934            event_var,
935            verb,
936            roles,
937        } => {
938            if event_var == var {
939                // event_var shadows var
940                body.clone()
941            } else if repl_fvs.contains(event_var) {
942                // Alpha-rename event_var away from the replacement's free vars.
943                let mut avoid = repl_fvs.clone();
944                for (_, t) in roles {
945                    all_names_term(t, &mut avoid);
946                }
947                let fresh = fresh_proof_name(event_var, &avoid);
948                ProofExpr::NeoEvent {
949                    event_var: fresh.clone(),
950                    verb: verb.clone(),
951                    roles: roles
952                        .iter()
953                        .map(|(r, t)| {
954                            let renamed = alpha_rename_term(t, event_var, &fresh);
955                            (
956                                r.clone(),
957                                substitute_term_for_var(&renamed, var, replacement),
958                            )
959                        })
960                        .collect(),
961                }
962            } else {
963                ProofExpr::NeoEvent {
964                    event_var: event_var.clone(),
965                    verb: verb.clone(),
966                    roles: roles
967                        .iter()
968                        .map(|(r, t)| (r.clone(), substitute_term_for_var(t, var, replacement)))
969                        .collect(),
970                }
971            }
972        }
973
974        ProofExpr::Ctor { name, args } => ProofExpr::Ctor {
975            name: name.clone(),
976            args: args
977                .iter()
978                .map(|a| subst_expr_avoiding(a, var, replacement, repl_fvs, at))
979                .collect(),
980        },
981
982        ProofExpr::Match { scrutinee, arms } => ProofExpr::Match {
983            scrutinee: Box::new(subst_expr_avoiding(
984                scrutinee,
985                var,
986                replacement,
987                repl_fvs,
988                at,
989            )),
990            arms: arms
991                .iter()
992                .map(|arm| {
993                    // Don't substitute if var is bound in this arm
994                    if arm.bindings.iter().any(|b| b == var) {
995                        arm.clone()
996                    } else {
997                        // Alpha-rename any binding that would capture a free var of
998                        // the replacement before substituting into the arm body.
999                        let mut arm_body = arm.body.clone();
1000                        let mut new_bindings = arm.bindings.clone();
1001                        let mut avoid = repl_fvs.clone();
1002                        all_names_expr(&arm_body, &mut avoid);
1003                        for b in &arm.bindings {
1004                            avoid.insert(b.clone());
1005                        }
1006                        for binding in new_bindings.iter_mut() {
1007                            if repl_fvs.contains(binding) {
1008                                let fresh = fresh_proof_name(binding, &avoid);
1009                                arm_body = alpha_rename_expr(&arm_body, binding, &fresh);
1010                                avoid.insert(fresh.clone());
1011                                *binding = fresh;
1012                            }
1013                        }
1014                        MatchArm {
1015                            ctor: arm.ctor.clone(),
1016                            bindings: new_bindings,
1017                            body: subst_expr_avoiding(&arm_body, var, replacement, repl_fvs, at),
1018                        }
1019                    }
1020                })
1021                .collect(),
1022        },
1023
1024        ProofExpr::Fixpoint { name, body: inner } => {
1025            if name == var {
1026                body.clone()
1027            } else {
1028                let (v, b) = rebind_for_subst(name, inner, repl_fvs);
1029                ProofExpr::Fixpoint {
1030                    name: v,
1031                    body: Box::new(subst_expr_avoiding(&b, var, replacement, repl_fvs, at)),
1032                }
1033            }
1034        }
1035
1036        ProofExpr::TypedVar { .. } | ProofExpr::Unsupported(_) => body.clone(),
1037
1038        // Holes are meta-variables - don't substitute into them
1039        ProofExpr::Hole(_) => body.clone(),
1040
1041        // Terms: substitute into the inner term
1042        ProofExpr::Term(t) => ProofExpr::Term(substitute_term_for_var(t, var, replacement)),
1043    }
1044}
1045
1046/// Substitute an expression for a variable in a term.
1047///
1048/// When a variable in a term matches, convert the replacement expression to a term.
1049fn substitute_term_for_var(term: &ProofTerm, var: &str, replacement: &ProofExpr) -> ProofTerm {
1050    match term {
1051        ProofTerm::Variable(v) if v == var => {
1052            // Variable matches, convert replacement to term
1053            expr_to_term(replacement)
1054        }
1055        // BoundVarRef also participates in substitution (for instantiating quantified formulas)
1056        ProofTerm::BoundVarRef(v) if v == var => expr_to_term(replacement),
1057        ProofTerm::Variable(_) | ProofTerm::Constant(_) | ProofTerm::BoundVarRef(_) => term.clone(),
1058        ProofTerm::Function(name, args) => ProofTerm::Function(
1059            name.clone(),
1060            args.iter()
1061                .map(|a| substitute_term_for_var(a, var, replacement))
1062                .collect(),
1063        ),
1064        ProofTerm::Group(terms) => ProofTerm::Group(
1065            terms
1066                .iter()
1067                .map(|t| substitute_term_for_var(t, var, replacement))
1068                .collect(),
1069        ),
1070    }
1071}
1072
1073/// Convert a simple ProofExpr to ProofTerm.
1074///
1075/// Used during beta-reduction when substituting an expression argument
1076/// into a predicate's term position.
1077fn expr_to_term(expr: &ProofExpr) -> ProofTerm {
1078    match expr {
1079        // Atoms become constants
1080        ProofExpr::Atom(s) => ProofTerm::Constant(s.clone()),
1081
1082        // Zero-arity predicates become constants (e.g., "John" as a predicate name)
1083        ProofExpr::Predicate { name, args, .. } if args.is_empty() => {
1084            ProofTerm::Constant(name.clone())
1085        }
1086
1087        // Predicates with args become functions
1088        ProofExpr::Predicate { name, args, .. } => ProofTerm::Function(name.clone(), args.clone()),
1089
1090        // Constructors become functions
1091        ProofExpr::Ctor { name, args } => {
1092            ProofTerm::Function(name.clone(), args.iter().map(expr_to_term).collect())
1093        }
1094
1095        // TypedVar becomes a variable
1096        ProofExpr::TypedVar { name, .. } => ProofTerm::Variable(name.clone()),
1097
1098        // Term is already a term - extract it directly
1099        ProofExpr::Term(t) => t.clone(),
1100
1101        // Fallback: stringify the expression (covers Hole, etc.)
1102        _ => ProofTerm::Constant(format!("{}", expr)),
1103    }
1104}
1105
1106// =============================================================================
1107// TERM-LEVEL UNIFICATION
1108// =============================================================================
1109
1110/// Unify two terms, returning the Most General Unifier (MGU).
1111///
1112/// The MGU is the smallest substitution that makes both terms identical.
1113/// Uses Robinson's algorithm with occurs check.
1114///
1115/// # Arguments
1116///
1117/// * `t1` - The first term (often a pattern with variables)
1118/// * `t2` - The second term (often a ground term or another pattern)
1119///
1120/// # Returns
1121///
1122/// * `Ok(subst)` - A substitution that unifies the terms
1123/// * `Err(OccursCheck)` - If unification would create an infinite term
1124/// * `Err(SymbolMismatch)` - If function/constant names differ
1125/// * `Err(ArityMismatch)` - If argument counts differ
1126///
1127/// # Example
1128///
1129/// ```
1130/// use logicaffeine_proof::{ProofTerm, unify::unify_terms};
1131///
1132/// let pattern = ProofTerm::Function(
1133///     "Mortal".into(),
1134///     vec![ProofTerm::Variable("x".into())]
1135/// );
1136/// let target = ProofTerm::Function(
1137///     "Mortal".into(),
1138///     vec![ProofTerm::Constant("Socrates".into())]
1139/// );
1140///
1141/// let subst = unify_terms(&pattern, &target).unwrap();
1142/// assert_eq!(
1143///     subst.get("x"),
1144///     Some(&ProofTerm::Constant("Socrates".into()))
1145/// );
1146/// ```
1147///
1148/// # See Also
1149///
1150/// * [`unify_exprs`] - Unifies expressions (handles quantifiers, connectives)
1151/// * [`apply_subst_to_term`] - Applies the resulting substitution
1152pub fn unify_terms(t1: &ProofTerm, t2: &ProofTerm) -> ProofResult<Substitution> {
1153    let mut subst = Substitution::new();
1154    unify_terms_with_subst(t1, t2, &mut subst)?;
1155    Ok(subst)
1156}
1157
1158/// Internal unification with accumulating substitution.
1159fn unify_terms_with_subst(
1160    t1: &ProofTerm,
1161    t2: &ProofTerm,
1162    subst: &mut Substitution,
1163) -> ProofResult<()> {
1164    // Apply current substitution to both terms first
1165    let t1 = apply_subst_to_term(t1, subst);
1166    let t2 = apply_subst_to_term(t2, subst);
1167
1168    match (&t1, &t2) {
1169        // Identical terms unify trivially
1170        (ProofTerm::Constant(c1), ProofTerm::Constant(c2)) if c1 == c2 => Ok(()),
1171
1172        // Different constants cannot unify
1173        (ProofTerm::Constant(c1), ProofTerm::Constant(c2)) => Err(ProofError::SymbolMismatch {
1174            left: c1.clone(),
1175            right: c2.clone(),
1176        }),
1177
1178        // Variable on the left: bind it to the right term
1179        (ProofTerm::Variable(v), t) => {
1180            // Check if they're the same variable
1181            if let ProofTerm::Variable(v2) = t {
1182                if v == v2 {
1183                    return Ok(());
1184                }
1185            }
1186            // Occurs check: prevent infinite types
1187            if occurs(v, t) {
1188                return Err(ProofError::OccursCheck {
1189                    variable: v.clone(),
1190                    term: t.clone(),
1191                });
1192            }
1193            subst.insert(v.clone(), t.clone());
1194            Ok(())
1195        }
1196
1197        // Variable on the right: bind it to the left term
1198        (t, ProofTerm::Variable(v)) => {
1199            // Occurs check
1200            if occurs(v, t) {
1201                return Err(ProofError::OccursCheck {
1202                    variable: v.clone(),
1203                    term: t.clone(),
1204                });
1205            }
1206            subst.insert(v.clone(), t.clone());
1207            Ok(())
1208        }
1209
1210        // BoundVarRef on the left: treat like a variable for unification
1211        // This allows matching quantified formulas like ∀x P(x) against P(butler)
1212        (ProofTerm::BoundVarRef(v), t) => {
1213            if let ProofTerm::BoundVarRef(v2) = t {
1214                if v == v2 {
1215                    return Ok(());
1216                }
1217            }
1218            if occurs(v, t) {
1219                return Err(ProofError::OccursCheck {
1220                    variable: v.clone(),
1221                    term: t.clone(),
1222                });
1223            }
1224            subst.insert(v.clone(), t.clone());
1225            Ok(())
1226        }
1227
1228        // BoundVarRef on the right: bind it to the left term
1229        (t, ProofTerm::BoundVarRef(v)) => {
1230            if occurs(v, t) {
1231                return Err(ProofError::OccursCheck {
1232                    variable: v.clone(),
1233                    term: t.clone(),
1234                });
1235            }
1236            subst.insert(v.clone(), t.clone());
1237            Ok(())
1238        }
1239
1240        // Function unification: same name and arity, unify arguments pairwise
1241        (ProofTerm::Function(f1, args1), ProofTerm::Function(f2, args2)) => {
1242            if f1 != f2 {
1243                return Err(ProofError::SymbolMismatch {
1244                    left: f1.clone(),
1245                    right: f2.clone(),
1246                });
1247            }
1248            if args1.len() != args2.len() {
1249                return Err(ProofError::ArityMismatch {
1250                    expected: args1.len(),
1251                    found: args2.len(),
1252                });
1253            }
1254            for (a1, a2) in args1.iter().zip(args2.iter()) {
1255                unify_terms_with_subst(a1, a2, subst)?;
1256            }
1257            Ok(())
1258        }
1259
1260        // Group unification: same length, unify elements pairwise
1261        (ProofTerm::Group(g1), ProofTerm::Group(g2)) => {
1262            if g1.len() != g2.len() {
1263                return Err(ProofError::ArityMismatch {
1264                    expected: g1.len(),
1265                    found: g2.len(),
1266                });
1267            }
1268            for (t1, t2) in g1.iter().zip(g2.iter()) {
1269                unify_terms_with_subst(t1, t2, subst)?;
1270            }
1271            Ok(())
1272        }
1273
1274        // Any other combination fails
1275        _ => Err(ProofError::UnificationFailed {
1276            left: t1,
1277            right: t2,
1278        }),
1279    }
1280}
1281
1282/// Check if a variable occurs in a term (for occurs check).
1283/// Prevents infinite types like x = f(x).
1284fn occurs(var: &str, term: &ProofTerm) -> bool {
1285    match term {
1286        ProofTerm::Variable(v) => v == var,
1287        ProofTerm::BoundVarRef(v) => v == var, // BoundVarRef participates in occurs check
1288        ProofTerm::Constant(_) => false,
1289        ProofTerm::Function(_, args) => args.iter().any(|a| occurs(var, a)),
1290        ProofTerm::Group(terms) => terms.iter().any(|t| occurs(var, t)),
1291    }
1292}
1293
1294/// Apply a substitution to a term.
1295///
1296/// Replaces all variables in the term according to the substitution mapping.
1297/// Handles transitive chains: if `{x ↦ y, y ↦ z}`, then applying to `x` yields `z`.
1298///
1299/// The substitution is read as TRIANGULAR, which is what a unifier produces: a replacement is itself
1300/// resolved against the map. That is sound only on an acyclic map, and a unifier's is (its occurs check
1301/// refuses `x ↦ …x…`). A cyclic map has no resolution, so reaching `x` again while resolving `x` panics,
1302/// naming the cycle, instead of recursing until the stack is gone. Instantiating one binder,
1303/// `body[x := t]` with `t` free to mention `x`, is not this operation: use [`instantiate_expr`].
1304///
1305/// # Arguments
1306///
1307/// * `term` - The term to transform
1308/// * `subst` - The substitution mapping variables to replacement terms
1309///
1310/// # Returns
1311///
1312/// A new term with all substitutions applied.
1313///
1314/// # Example
1315///
1316/// ```
1317/// use logicaffeine_proof::{ProofTerm, unify::{Substitution, apply_subst_to_term}};
1318/// use std::collections::HashMap;
1319///
1320/// let mut subst = Substitution::new();
1321/// subst.insert("x".into(), ProofTerm::Constant("Socrates".into()));
1322///
1323/// let term = ProofTerm::Function(
1324///     "Mortal".into(),
1325///     vec![ProofTerm::Variable("x".into())]
1326/// );
1327///
1328/// let result = apply_subst_to_term(&term, &subst);
1329/// // result = Mortal(Socrates)
1330/// ```
1331pub fn apply_subst_to_term(term: &ProofTerm, subst: &Substitution) -> ProofTerm {
1332    resolve_term(term, subst, &mut Vec::new())
1333}
1334
1335/// [`apply_subst_to_term`], with `resolving` the variables whose replacements are being resolved on the
1336/// way down to `term`.
1337fn resolve_term(term: &ProofTerm, subst: &Substitution, resolving: &mut Vec<String>) -> ProofTerm {
1338    match term {
1339        // BoundVarRef participates in substitution (for instantiating quantified formulas)
1340        ProofTerm::Variable(v) | ProofTerm::BoundVarRef(v) => match subst.get(v) {
1341            Some(replacement) => {
1342                if resolving.iter().any(|r| r == v) {
1343                    resolving.push(v.clone());
1344                    panic!(
1345                        "cyclic substitution {}: a triangular substitution resolves each replacement against the map, \
1346                         and this one never resolves; a unifier's map is acyclic, and instantiating a binder \
1347                         (`body[x := t]`) is `unify::instantiate_expr`",
1348                        resolving.join(" ↦ ")
1349                    );
1350                }
1351                resolving.push(v.clone());
1352                let resolved = resolve_term(replacement, subst, resolving);
1353                resolving.pop();
1354                resolved
1355            }
1356            None => term.clone(),
1357        },
1358        ProofTerm::Constant(_) => term.clone(),
1359        ProofTerm::Function(name, args) => {
1360            let new_args = args
1361                .iter()
1362                .map(|a| resolve_term(a, subst, resolving))
1363                .collect();
1364            ProofTerm::Function(name.clone(), new_args)
1365        }
1366        ProofTerm::Group(terms) => {
1367            let new_terms = terms
1368                .iter()
1369                .map(|t| resolve_term(t, subst, resolving))
1370                .collect();
1371            ProofTerm::Group(new_terms)
1372        }
1373    }
1374}
1375
1376// =============================================================================
1377// EXPRESSION-LEVEL UNIFICATION
1378// =============================================================================
1379
1380/// Unify two expressions, returning the Most General Unifier.
1381///
1382/// Expression unification extends term unification with support for logical
1383/// connectives, quantifiers, and alpha-equivalence for bound variables.
1384///
1385/// # Alpha-Equivalence
1386///
1387/// Bound variable names are considered arbitrary:
1388/// - `∀x P(x)` unifies with `∀y P(y)`
1389/// - `∃e Run(e)` unifies with `∃x Run(x)`
1390///
1391/// This is achieved by substituting fresh constants for bound variables
1392/// before comparing bodies.
1393///
1394/// # Beta-Reduction
1395///
1396/// Both expressions are beta-reduced before comparison, so
1397/// `(λx. P(x))(a)` will unify with `P(a)`.
1398///
1399/// # Arguments
1400///
1401/// * `e1` - The first expression
1402/// * `e2` - The second expression
1403///
1404/// # Returns
1405///
1406/// * `Ok(subst)` - A substitution unifying the expressions
1407/// * `Err(ExprUnificationFailed)` - If expressions cannot be unified
1408///
1409/// # See Also
1410///
1411/// * [`unify_terms`] - Underlying term unification
1412/// * [`beta_reduce`] - Normalization applied before unification
1413/// * [`unify_pattern`] - Higher-order pattern unification for holes
1414pub fn unify_exprs(e1: &ProofExpr, e2: &ProofExpr) -> ProofResult<Substitution> {
1415    let mut subst = Substitution::new();
1416    unify_exprs_with_subst(e1, e2, &mut subst)?;
1417    Ok(subst)
1418}
1419
1420/// Internal expression unification with accumulating substitution.
1421fn unify_exprs_with_subst(
1422    e1: &ProofExpr,
1423    e2: &ProofExpr,
1424    subst: &mut Substitution,
1425) -> ProofResult<()> {
1426    // Beta-reduce both expressions before unification.
1427    // This normalizes lambda applications: (λx. P(x))(a) → P(a)
1428    let e1 = beta_reduce(e1);
1429    let e2 = beta_reduce(e2);
1430
1431    match (&e1, &e2) {
1432        // Atom unification
1433        (ProofExpr::Atom(a1), ProofExpr::Atom(a2)) if a1 == a2 => Ok(()),
1434
1435        // Predicate unification: same name, unify arguments
1436        (
1437            ProofExpr::Predicate {
1438                name: n1,
1439                args: a1,
1440                world: w1,
1441            },
1442            ProofExpr::Predicate {
1443                name: n2,
1444                args: a2,
1445                world: w2,
1446            },
1447        ) => {
1448            if n1 != n2 {
1449                return Err(ProofError::SymbolMismatch {
1450                    left: n1.clone(),
1451                    right: n2.clone(),
1452                });
1453            }
1454            if a1.len() != a2.len() {
1455                return Err(ProofError::ArityMismatch {
1456                    expected: a1.len(),
1457                    found: a2.len(),
1458                });
1459            }
1460            // Unify worlds if both present
1461            match (w1, w2) {
1462                (Some(w1), Some(w2)) if w1 != w2 => {
1463                    return Err(ProofError::SymbolMismatch {
1464                        left: w1.clone(),
1465                        right: w2.clone(),
1466                    });
1467                }
1468                _ => {}
1469            }
1470            // Unify arguments
1471            for (t1, t2) in a1.iter().zip(a2.iter()) {
1472                unify_terms_with_subst(t1, t2, subst)?;
1473            }
1474            Ok(())
1475        }
1476
1477        // Identity unification
1478        (ProofExpr::Identity(l1, r1), ProofExpr::Identity(l2, r2)) => {
1479            unify_terms_with_subst(l1, l2, subst)?;
1480            unify_terms_with_subst(r1, r2, subst)?;
1481            Ok(())
1482        }
1483
1484        // Binary operators: same operator, unify both sides
1485        (ProofExpr::And(l1, r1), ProofExpr::And(l2, r2))
1486        | (ProofExpr::Or(l1, r1), ProofExpr::Or(l2, r2))
1487        | (ProofExpr::Implies(l1, r1), ProofExpr::Implies(l2, r2))
1488        | (ProofExpr::Iff(l1, r1), ProofExpr::Iff(l2, r2)) => {
1489            unify_exprs_with_subst(l1, l2, subst)?;
1490            unify_exprs_with_subst(r1, r2, subst)?;
1491            Ok(())
1492        }
1493
1494        // Negation
1495        (ProofExpr::Not(inner1), ProofExpr::Not(inner2)) => {
1496            unify_exprs_with_subst(inner1, inner2, subst)
1497        }
1498
1499        // Quantifiers: Alpha-equivalence - bound variable names are arbitrary
1500        // ∃e P(e) ≡ ∃x P(x) because they describe the same logical content
1501        (
1502            ProofExpr::ForAll {
1503                variable: v1,
1504                body: b1,
1505            },
1506            ProofExpr::ForAll {
1507                variable: v2,
1508                body: b2,
1509            },
1510        )
1511        | (
1512            ProofExpr::Exists {
1513                variable: v1,
1514                body: b1,
1515            },
1516            ProofExpr::Exists {
1517                variable: v2,
1518                body: b2,
1519            },
1520        ) => {
1521            // Generate a fresh constant to substitute for both bound variables.
1522            // Using a constant (not a variable) avoids capture issues.
1523            let fresh = fresh_alpha_constant();
1524
1525            // Create substitutions for each bound variable
1526            let subst1: Substitution = [(v1.clone(), fresh.clone())].into_iter().collect();
1527            let subst2: Substitution = [(v2.clone(), fresh)].into_iter().collect();
1528
1529            // Apply substitutions to bodies
1530            let body1_renamed = apply_subst_to_expr(b1, &subst1);
1531            let body2_renamed = apply_subst_to_expr(b2, &subst2);
1532
1533            // Recursively unify the renamed bodies
1534            unify_exprs_with_subst(&body1_renamed, &body2_renamed, subst)
1535        }
1536
1537        // Lambda expressions: Alpha-equivalence - λx.P(x) ≡ λy.P(y)
1538        (
1539            ProofExpr::Lambda {
1540                variable: v1,
1541                body: b1,
1542            },
1543            ProofExpr::Lambda {
1544                variable: v2,
1545                body: b2,
1546            },
1547        ) => {
1548            // Same alpha-renaming technique as quantifiers
1549            let fresh = fresh_alpha_constant();
1550            let subst1: Substitution = [(v1.clone(), fresh.clone())].into_iter().collect();
1551            let subst2: Substitution = [(v2.clone(), fresh)].into_iter().collect();
1552            let body1_renamed = apply_subst_to_expr(b1, &subst1);
1553            let body2_renamed = apply_subst_to_expr(b2, &subst2);
1554            unify_exprs_with_subst(&body1_renamed, &body2_renamed, subst)
1555        }
1556
1557        // Application
1558        (ProofExpr::App(f1, a1), ProofExpr::App(f2, a2)) => {
1559            unify_exprs_with_subst(f1, f2, subst)?;
1560            unify_exprs_with_subst(a1, a2, subst)?;
1561            Ok(())
1562        }
1563
1564        // NeoEvent: Alpha-equivalence for event variables
1565        // ∃e(Run(e) ∧ Agent(e, John)) should unify with ∃x(Run(x) ∧ Agent(x, John))
1566        (
1567            ProofExpr::NeoEvent {
1568                event_var: e1,
1569                verb: v1,
1570                roles: r1,
1571            },
1572            ProofExpr::NeoEvent {
1573                event_var: e2,
1574                verb: v2,
1575                roles: r2,
1576            },
1577        ) => {
1578            // Verb names must match (case-insensitive for robustness)
1579            if v1.to_lowercase() != v2.to_lowercase() {
1580                return Err(ProofError::SymbolMismatch {
1581                    left: v1.clone(),
1582                    right: v2.clone(),
1583                });
1584            }
1585
1586            // Roles must have same length
1587            if r1.len() != r2.len() {
1588                return Err(ProofError::ArityMismatch {
1589                    expected: r1.len(),
1590                    found: r2.len(),
1591                });
1592            }
1593
1594            // Alpha-equivalence: generate fresh constant for event variable
1595            let fresh = fresh_alpha_constant();
1596            let subst1: Substitution = [(e1.clone(), fresh.clone())].into_iter().collect();
1597            let subst2: Substitution = [(e2.clone(), fresh)].into_iter().collect();
1598
1599            // Unify roles pairwise with alpha-renamed event variables
1600            for ((role1, term1), (role2, term2)) in r1.iter().zip(r2.iter()) {
1601                // Role names must match
1602                if role1 != role2 {
1603                    return Err(ProofError::SymbolMismatch {
1604                        left: role1.clone(),
1605                        right: role2.clone(),
1606                    });
1607                }
1608                // Apply alpha-renaming to terms and unify
1609                let t1_renamed = apply_subst_to_term(term1, &subst1);
1610                let t2_renamed = apply_subst_to_term(term2, &subst2);
1611                unify_terms_with_subst(&t1_renamed, &t2_renamed, subst)?;
1612            }
1613            Ok(())
1614        }
1615
1616        // Temporal operators: Past(P), Future(P)
1617        // Same operator required, then unify bodies
1618        (
1619            ProofExpr::Temporal {
1620                operator: op1,
1621                body: b1,
1622            },
1623            ProofExpr::Temporal {
1624                operator: op2,
1625                body: b2,
1626            },
1627        ) => {
1628            if op1 != op2 {
1629                return Err(ProofError::ExprUnificationFailed {
1630                    left: e1.clone(),
1631                    right: e2.clone(),
1632                });
1633            }
1634            unify_exprs_with_subst(b1, b2, subst)
1635        }
1636
1637        // Binary temporal operators: Until(P,Q), Release(P,Q)
1638        // Same operator required, then unify both children
1639        (
1640            ProofExpr::TemporalBinary {
1641                operator: op1,
1642                left: l1,
1643                right: r1,
1644            },
1645            ProofExpr::TemporalBinary {
1646                operator: op2,
1647                left: l2,
1648                right: r2,
1649            },
1650        ) => {
1651            if op1 != op2 {
1652                return Err(ProofError::ExprUnificationFailed {
1653                    left: e1.clone(),
1654                    right: e2.clone(),
1655                });
1656            }
1657            unify_exprs_with_subst(l1, l2, subst)?;
1658            unify_exprs_with_subst(r1, r2, subst)
1659        }
1660
1661        // Anything else fails
1662        _ => Err(ProofError::ExprUnificationFailed {
1663            left: e1.clone(),
1664            right: e2.clone(),
1665        }),
1666    }
1667}
1668
1669/// Apply a substitution to an expression.
1670///
1671/// Recursively replaces variables in terms within the expression according
1672/// to the substitution mapping. Also handles binder renaming when the
1673/// substitution maps a bound variable name to a new variable.
1674///
1675/// # Arguments
1676///
1677/// * `expr` - The expression to transform
1678/// * `subst` - The substitution mapping variables to replacement terms
1679///
1680/// # Returns
1681///
1682/// A new expression with all substitutions applied to embedded terms.
1683///
1684/// # Binder Handling
1685///
1686/// When a quantifier or lambda binds a variable that maps to another variable
1687/// in the substitution, the binder is renamed:
1688///
1689/// ```text
1690/// apply_subst_to_expr(∀x P(x), {x ↦ y}) = ∀y P(y)
1691/// ```
1692pub fn apply_subst_to_expr(expr: &ProofExpr, subst: &Substitution) -> ProofExpr {
1693    match expr {
1694        ProofExpr::Predicate { name, args, world } => ProofExpr::Predicate {
1695            name: name.clone(),
1696            args: args.iter().map(|a| apply_subst_to_term(a, subst)).collect(),
1697            world: world.clone(),
1698        },
1699        ProofExpr::Identity(l, r) => {
1700            ProofExpr::Identity(apply_subst_to_term(l, subst), apply_subst_to_term(r, subst))
1701        }
1702        ProofExpr::Atom(a) => ProofExpr::Atom(a.clone()),
1703        ProofExpr::And(l, r) => ProofExpr::And(
1704            Box::new(apply_subst_to_expr(l, subst)),
1705            Box::new(apply_subst_to_expr(r, subst)),
1706        ),
1707        ProofExpr::Or(l, r) => ProofExpr::Or(
1708            Box::new(apply_subst_to_expr(l, subst)),
1709            Box::new(apply_subst_to_expr(r, subst)),
1710        ),
1711        ProofExpr::Implies(l, r) => ProofExpr::Implies(
1712            Box::new(apply_subst_to_expr(l, subst)),
1713            Box::new(apply_subst_to_expr(r, subst)),
1714        ),
1715        ProofExpr::Iff(l, r) => ProofExpr::Iff(
1716            Box::new(apply_subst_to_expr(l, subst)),
1717            Box::new(apply_subst_to_expr(r, subst)),
1718        ),
1719        ProofExpr::Not(inner) => ProofExpr::Not(Box::new(apply_subst_to_expr(inner, subst))),
1720        ProofExpr::ForAll { variable, body } => {
1721            // If the variable is being renamed (maps to a Variable), update the binder
1722            let new_variable = match subst.get(variable) {
1723                Some(ProofTerm::Variable(new_name)) => new_name.clone(),
1724                _ => variable.clone(),
1725            };
1726            ProofExpr::ForAll {
1727                variable: new_variable,
1728                body: Box::new(apply_subst_to_expr(body, subst)),
1729            }
1730        }
1731        ProofExpr::Exists { variable, body } => {
1732            // If the variable is being renamed (maps to a Variable), update the binder
1733            let new_variable = match subst.get(variable) {
1734                Some(ProofTerm::Variable(new_name)) => new_name.clone(),
1735                _ => variable.clone(),
1736            };
1737            ProofExpr::Exists {
1738                variable: new_variable,
1739                body: Box::new(apply_subst_to_expr(body, subst)),
1740            }
1741        }
1742        ProofExpr::Modal {
1743            domain,
1744            force,
1745            flavor,
1746            body,
1747        } => ProofExpr::Modal {
1748            domain: domain.clone(),
1749            force: *force,
1750            flavor: flavor.clone(),
1751            body: Box::new(apply_subst_to_expr(body, subst)),
1752        },
1753        ProofExpr::Counterfactual {
1754            antecedent,
1755            consequent,
1756        } => ProofExpr::Counterfactual {
1757            antecedent: Box::new(apply_subst_to_expr(antecedent, subst)),
1758            consequent: Box::new(apply_subst_to_expr(consequent, subst)),
1759        },
1760        ProofExpr::Temporal { operator, body } => ProofExpr::Temporal {
1761            operator: operator.clone(),
1762            body: Box::new(apply_subst_to_expr(body, subst)),
1763        },
1764        ProofExpr::TemporalBinary {
1765            operator,
1766            left,
1767            right,
1768        } => ProofExpr::TemporalBinary {
1769            operator: operator.clone(),
1770            left: Box::new(apply_subst_to_expr(left, subst)),
1771            right: Box::new(apply_subst_to_expr(right, subst)),
1772        },
1773        ProofExpr::Lambda { variable, body } => {
1774            // If the variable is being renamed (maps to a Variable), update the binder
1775            let new_variable = match subst.get(variable) {
1776                Some(ProofTerm::Variable(new_name)) => new_name.clone(),
1777                _ => variable.clone(),
1778            };
1779            ProofExpr::Lambda {
1780                variable: new_variable,
1781                body: Box::new(apply_subst_to_expr(body, subst)),
1782            }
1783        }
1784        ProofExpr::App(f, a) => ProofExpr::App(
1785            Box::new(apply_subst_to_expr(f, subst)),
1786            Box::new(apply_subst_to_expr(a, subst)),
1787        ),
1788        ProofExpr::NeoEvent {
1789            event_var,
1790            verb,
1791            roles,
1792        } => ProofExpr::NeoEvent {
1793            event_var: event_var.clone(),
1794            verb: verb.clone(),
1795            roles: roles
1796                .iter()
1797                .map(|(r, t)| (r.clone(), apply_subst_to_term(t, subst)))
1798                .collect(),
1799        },
1800        // Peano / Inductive Types
1801        ProofExpr::Ctor { name, args } => ProofExpr::Ctor {
1802            name: name.clone(),
1803            args: args.iter().map(|a| apply_subst_to_expr(a, subst)).collect(),
1804        },
1805        ProofExpr::Match { scrutinee, arms } => ProofExpr::Match {
1806            scrutinee: Box::new(apply_subst_to_expr(scrutinee, subst)),
1807            arms: arms
1808                .iter()
1809                .map(|arm| MatchArm {
1810                    ctor: arm.ctor.clone(),
1811                    bindings: arm.bindings.clone(),
1812                    body: apply_subst_to_expr(&arm.body, subst),
1813                })
1814                .collect(),
1815        },
1816        ProofExpr::Fixpoint { name, body } => ProofExpr::Fixpoint {
1817            name: name.clone(),
1818            body: Box::new(apply_subst_to_expr(body, subst)),
1819        },
1820        ProofExpr::TypedVar { name, typename } => ProofExpr::TypedVar {
1821            name: name.clone(),
1822            typename: typename.clone(),
1823        },
1824        ProofExpr::Unsupported(s) => ProofExpr::Unsupported(s.clone()),
1825        // Holes are meta-variables - term substitution doesn't apply
1826        ProofExpr::Hole(name) => ProofExpr::Hole(name.clone()),
1827        // Terms: apply substitution to the inner term
1828        ProofExpr::Term(t) => ProofExpr::Term(apply_subst_to_term(t, subst)),
1829    }
1830}
1831
1832/// Compose two substitutions: apply s2 after s1.
1833///
1834/// The resulting substitution applies s1 first, then s2. This is the standard
1835/// composition operation for Most General Unifiers.
1836///
1837/// # Semantics
1838///
1839/// For any term t: `apply(compose(s1, s2), t) = apply(s2, apply(s1, t))`
1840///
1841/// # Arguments
1842///
1843/// * `s1` - The first substitution (applied first)
1844/// * `s2` - The second substitution (applied second)
1845///
1846/// # Returns
1847///
1848/// A combined substitution equivalent to applying s1 then s2.
1849///
1850/// # Example
1851///
1852/// ```
1853/// use logicaffeine_proof::{ProofTerm, unify::{Substitution, compose_substitutions}};
1854///
1855/// let mut s1 = Substitution::new();
1856/// s1.insert("x".into(), ProofTerm::Variable("y".into()));
1857///
1858/// let mut s2 = Substitution::new();
1859/// s2.insert("y".into(), ProofTerm::Constant("a".into()));
1860///
1861/// let composed = compose_substitutions(s1, s2);
1862/// // x ↦ a (via y), y ↦ a
1863/// ```
1864pub fn compose_substitutions(s1: Substitution, s2: Substitution) -> Substitution {
1865    let mut result: Substitution = s1
1866        .into_iter()
1867        .map(|(k, v)| (k, apply_subst_to_term(&v, &s2)))
1868        .collect();
1869
1870    // Add bindings from s2 that aren't in s1
1871    for (k, v) in s2 {
1872        result.entry(k).or_insert(v);
1873    }
1874
1875    result
1876}
1877
1878// =============================================================================
1879// HIGHER-ORDER PATTERN UNIFICATION
1880// =============================================================================
1881
1882/// Attempt higher-order pattern unification (Miller patterns).
1883///
1884/// Given `lhs` and `rhs`, if `lhs` is of the form `Hole(h)(args...)` where
1885/// args are distinct `BoundVarRef`s, solves: `h = λargs. rhs`.
1886///
1887/// # Miller Patterns
1888///
1889/// A Miller pattern is a meta-variable applied to distinct bound variables:
1890/// - `?P(x)` is a valid pattern
1891/// - `?F(x, y)` is a valid pattern (x ≠ y)
1892/// - `?G(x, x)` is NOT valid (duplicate variable)
1893/// - `?H(f(x))` is NOT valid (non-variable argument)
1894///
1895/// # Why This Matters
1896///
1897/// Higher-order pattern unification is decidable and has unique most general
1898/// solutions, unlike full higher-order unification. This restriction enables
1899/// automatic motive inference for structural induction.
1900///
1901/// # Returns
1902///
1903/// * `Ok(subst)` - An [`ExprSubstitution`] mapping hole names to lambdas
1904/// * `Err(PatternNotDistinct)` - If pattern has duplicate variables
1905/// * `Err(NotAPattern)` - If arguments aren't bound variable references
1906/// * `Err(ScopeViolation)` - If RHS uses variables not in pattern scope
1907///
1908/// # Example
1909///
1910/// ```text
1911/// unify_pattern(?P(x), Even(x))
1912/// → { "P" ↦ λx. Even(x) }
1913/// ```
1914///
1915/// # See Also
1916///
1917/// * [`ExprSubstitution`] - The result type for hole solutions
1918/// * [`ProofError::PatternNotDistinct`] - Duplicate variable error
1919pub fn unify_pattern(lhs: &ProofExpr, rhs: &ProofExpr) -> ProofResult<ExprSubstitution> {
1920    let mut solution = ExprSubstitution::new();
1921    unify_pattern_internal(lhs, rhs, &mut solution)?;
1922    Ok(solution)
1923}
1924
1925/// Internal pattern unification with accumulating solution.
1926fn unify_pattern_internal(
1927    lhs: &ProofExpr,
1928    rhs: &ProofExpr,
1929    solution: &mut ExprSubstitution,
1930) -> ProofResult<()> {
1931    // Beta-reduce both sides first
1932    let lhs = beta_reduce(lhs);
1933    let rhs = beta_reduce(rhs);
1934
1935    match &lhs {
1936        // Case: Bare hole ?P = rhs
1937        ProofExpr::Hole(h) => {
1938            solution.insert(h.clone(), rhs.clone());
1939            Ok(())
1940        }
1941
1942        // Case: Application - might be Hole(h)(args...)
1943        ProofExpr::App(_, _) => {
1944            // Collect all arguments and find the head
1945            let (head, args) = collect_app_args(&lhs);
1946
1947            if let ProofExpr::Hole(h) = head {
1948                // Check Miller pattern: all args must be distinct BoundVarRefs
1949                let var_args = extract_distinct_vars(&args)?;
1950
1951                // Check that rhs only uses variables from var_args (scope check)
1952                check_scope(&rhs, &var_args)?;
1953
1954                // Construct solution: h = λargs. rhs
1955                // Need to rename variables in rhs to match the BoundVarRef names
1956                let renamed_rhs = rename_vars_to_bound(&rhs, &var_args);
1957                let lambda = build_lambda(var_args, renamed_rhs);
1958                solution.insert(h.clone(), lambda);
1959                Ok(())
1960            } else {
1961                // Not a pattern, try structural equality
1962                if lhs == rhs {
1963                    Ok(())
1964                } else {
1965                    Err(ProofError::ExprUnificationFailed {
1966                        left: lhs.clone(),
1967                        right: rhs.clone(),
1968                    })
1969                }
1970            }
1971        }
1972
1973        // Other cases: structural equality
1974        _ => {
1975            if lhs == rhs {
1976                Ok(())
1977            } else {
1978                Err(ProofError::ExprUnificationFailed {
1979                    left: lhs.clone(),
1980                    right: rhs.clone(),
1981                })
1982            }
1983        }
1984    }
1985}
1986
1987/// Collect f(a)(b)(c) into (f, [a, b, c])
1988fn collect_app_args(expr: &ProofExpr) -> (ProofExpr, Vec<ProofExpr>) {
1989    let mut args = Vec::new();
1990    let mut current = expr.clone();
1991
1992    while let ProofExpr::App(func, arg) = current {
1993        args.push(*arg);
1994        current = *func;
1995    }
1996
1997    args.reverse();
1998    (current, args)
1999}
2000
2001/// Extract distinct variable names from pattern arguments.
2002/// Fails if any arg is not a Term(BoundVarRef) or if duplicates exist.
2003fn extract_distinct_vars(args: &[ProofExpr]) -> ProofResult<Vec<String>> {
2004    let mut vars = Vec::new();
2005    for arg in args {
2006        match arg {
2007            ProofExpr::Term(ProofTerm::BoundVarRef(v)) => {
2008                if vars.contains(v) {
2009                    return Err(ProofError::PatternNotDistinct(v.clone()));
2010                }
2011                vars.push(v.clone());
2012            }
2013            _ => return Err(ProofError::NotAPattern(arg.clone())),
2014        }
2015    }
2016    Ok(vars)
2017}
2018
2019/// Check that all free variables in expr are in the allowed set.
2020fn check_scope(expr: &ProofExpr, allowed: &[String]) -> ProofResult<()> {
2021    let free_vars = collect_free_vars(expr);
2022    for var in free_vars {
2023        if !allowed.contains(&var) {
2024            return Err(ProofError::ScopeViolation {
2025                var,
2026                allowed: allowed.to_vec(),
2027            });
2028        }
2029    }
2030    Ok(())
2031}
2032
2033/// Collect free variables from an expression.
2034fn collect_free_vars(expr: &ProofExpr) -> Vec<String> {
2035    let mut vars = Vec::new();
2036    collect_free_vars_impl(expr, &mut vars, &mut Vec::new());
2037    vars
2038}
2039
2040fn collect_free_vars_impl(expr: &ProofExpr, vars: &mut Vec<String>, bound: &mut Vec<String>) {
2041    match expr {
2042        ProofExpr::Predicate { args, .. } => {
2043            for arg in args {
2044                collect_free_vars_term(arg, vars, bound);
2045            }
2046        }
2047        ProofExpr::Identity(l, r) => {
2048            collect_free_vars_term(l, vars, bound);
2049            collect_free_vars_term(r, vars, bound);
2050        }
2051        ProofExpr::Atom(s) => {
2052            if !bound.contains(s) && !vars.contains(s) {
2053                vars.push(s.clone());
2054            }
2055        }
2056        ProofExpr::And(l, r)
2057        | ProofExpr::Or(l, r)
2058        | ProofExpr::Implies(l, r)
2059        | ProofExpr::Iff(l, r) => {
2060            collect_free_vars_impl(l, vars, bound);
2061            collect_free_vars_impl(r, vars, bound);
2062        }
2063        ProofExpr::Not(inner) => collect_free_vars_impl(inner, vars, bound),
2064        ProofExpr::ForAll { variable, body }
2065        | ProofExpr::Exists { variable, body }
2066        | ProofExpr::Lambda { variable, body } => {
2067            bound.push(variable.clone());
2068            collect_free_vars_impl(body, vars, bound);
2069            bound.pop();
2070        }
2071        ProofExpr::App(f, a) => {
2072            collect_free_vars_impl(f, vars, bound);
2073            collect_free_vars_impl(a, vars, bound);
2074        }
2075        ProofExpr::Term(t) => collect_free_vars_term(t, vars, bound),
2076        ProofExpr::Hole(_) => {} // Holes don't contribute free vars
2077        _ => {}                  // Other cases don't add free vars
2078    }
2079}
2080
2081fn collect_free_vars_term(term: &ProofTerm, vars: &mut Vec<String>, bound: &[String]) {
2082    match term {
2083        ProofTerm::Variable(v) => {
2084            if !bound.contains(v) && !vars.contains(v) {
2085                vars.push(v.clone());
2086            }
2087        }
2088        ProofTerm::Function(_, args) => {
2089            for arg in args {
2090                collect_free_vars_term(arg, vars, bound);
2091            }
2092        }
2093        ProofTerm::Group(terms) => {
2094            for t in terms {
2095                collect_free_vars_term(t, vars, bound);
2096            }
2097        }
2098        ProofTerm::Constant(_) | ProofTerm::BoundVarRef(_) => {}
2099    }
2100}
2101
2102/// Rename Variable(x) to Variable(x) if x is in the bound vars list.
2103/// This ensures the solution lambda binds the right names.
2104fn rename_vars_to_bound(expr: &ProofExpr, bound_vars: &[String]) -> ProofExpr {
2105    // For the basic case, we don't need to rename since the RHS already uses
2106    // Variable("x") and we want the lambda to bind "x".
2107    // The key is just to use the same names.
2108    expr.clone()
2109}
2110
2111/// Build λx₁.λx₂...λxₙ. body
2112fn build_lambda(vars: Vec<String>, body: ProofExpr) -> ProofExpr {
2113    vars.into_iter()
2114        .rev()
2115        .fold(body, |acc, var| ProofExpr::Lambda {
2116            variable: var,
2117            body: Box::new(acc),
2118        })
2119}
2120
2121// =============================================================================
2122// One-sided pattern matching (pattern → target)
2123// =============================================================================
2124
2125/// One-sided match of a term `pattern` against a `target`: pattern
2126/// `Variable`s bind target subterms; the target is inspected, never bound.
2127/// Repeated pattern variables must bind the same subterm. This is the
2128/// arbiter behind discrimination-tree retrieval (`crate::discrimination`) —
2129/// the tree over-approximates, this decides.
2130pub fn match_term_pattern(pattern: &ProofTerm, target: &ProofTerm) -> Option<Substitution> {
2131    let mut subst = Substitution::new();
2132    let mut bound = Vec::new();
2133    if match_term_into(pattern, target, &mut subst, &mut bound) {
2134        Some(subst)
2135    } else {
2136        None
2137    }
2138}
2139
2140/// One-sided match of an expression `pattern` against a `target` (see
2141/// [`match_term_pattern`]). Quantified subexpressions match name-strictly
2142/// (no alpha-renaming — conservative: an alpha-variant simply fails), and a
2143/// pattern variable never binds a term that mentions a bound variable
2144/// (capture is rejected, not silently permitted).
2145pub fn match_expr_pattern(pattern: &ProofExpr, target: &ProofExpr) -> Option<Substitution> {
2146    let mut subst = Substitution::new();
2147    let mut bound = Vec::new();
2148    if match_expr_into(pattern, target, &mut subst, &mut bound) {
2149        Some(subst)
2150    } else {
2151        None
2152    }
2153}
2154
2155/// Bind `name ↦ value`, enforcing consistency with any existing binding and
2156/// rejecting values that mention an enclosing bound variable (escape check).
2157fn match_bind(subst: &mut Substitution, bound: &[String], name: &str, value: &ProofTerm) -> bool {
2158    if let Some(existing) = subst.get(name) {
2159        return existing == value;
2160    }
2161    if term_mentions_any(value, bound) {
2162        return false;
2163    }
2164    subst.insert(name.to_string(), value.clone());
2165    true
2166}
2167
2168fn term_mentions_any(t: &ProofTerm, names: &[String]) -> bool {
2169    match t {
2170        ProofTerm::Variable(n) | ProofTerm::BoundVarRef(n) => names.iter().any(|b| b == n),
2171        ProofTerm::Constant(_) => false,
2172        ProofTerm::Function(_, args) | ProofTerm::Group(args) => {
2173            args.iter().any(|a| term_mentions_any(a, names))
2174        }
2175    }
2176}
2177
2178fn match_term_into(
2179    pattern: &ProofTerm,
2180    target: &ProofTerm,
2181    subst: &mut Substitution,
2182    bound: &mut Vec<String>,
2183) -> bool {
2184    match pattern {
2185        ProofTerm::Variable(name) => {
2186            // A pattern variable bound by an enclosing quantifier is rigid: it
2187            // matches exactly itself, never an arbitrary subterm.
2188            if bound.contains(name) {
2189                return matches!(target, ProofTerm::Variable(n) if n == name);
2190            }
2191            match_bind(subst, bound, name, target)
2192        }
2193        ProofTerm::Constant(a) => matches!(target, ProofTerm::Constant(b) if a == b),
2194        ProofTerm::BoundVarRef(a) => matches!(target, ProofTerm::BoundVarRef(b) if a == b),
2195        ProofTerm::Function(name, args) => match target {
2196            ProofTerm::Function(tname, targs) if name == tname && args.len() == targs.len() => {
2197                for (a, b) in args.iter().zip(targs) {
2198                    if !match_term_into(a, b, subst, bound) {
2199                        return false;
2200                    }
2201                }
2202                true
2203            }
2204            _ => false,
2205        },
2206        ProofTerm::Group(args) => match target {
2207            ProofTerm::Group(targs) if args.len() == targs.len() => {
2208                for (a, b) in args.iter().zip(targs) {
2209                    if !match_term_into(a, b, subst, bound) {
2210                        return false;
2211                    }
2212                }
2213                true
2214            }
2215            _ => false,
2216        },
2217    }
2218}
2219
2220fn match_expr_into(
2221    pattern: &ProofExpr,
2222    target: &ProofExpr,
2223    subst: &mut Substitution,
2224    bound: &mut Vec<String>,
2225) -> bool {
2226    match (pattern, target) {
2227        (
2228            ProofExpr::Predicate {
2229                name: pn,
2230                args: pa,
2231                world: pw,
2232            },
2233            ProofExpr::Predicate {
2234                name: tn,
2235                args: ta,
2236                world: tw,
2237            },
2238        ) => {
2239            if pn != tn || pa.len() != ta.len() || pw != tw {
2240                return false;
2241            }
2242            for (a, b) in pa.iter().zip(ta) {
2243                if !match_term_into(a, b, subst, bound) {
2244                    return false;
2245                }
2246            }
2247            true
2248        }
2249        (ProofExpr::Identity(pl, pr), ProofExpr::Identity(tl, tr)) => {
2250            match_term_into(pl, tl, subst, bound) && match_term_into(pr, tr, subst, bound)
2251        }
2252        (ProofExpr::Atom(a), ProofExpr::Atom(b)) => a == b,
2253        (ProofExpr::And(pl, pr), ProofExpr::And(tl, tr))
2254        | (ProofExpr::Or(pl, pr), ProofExpr::Or(tl, tr))
2255        | (ProofExpr::Implies(pl, pr), ProofExpr::Implies(tl, tr))
2256        | (ProofExpr::Iff(pl, pr), ProofExpr::Iff(tl, tr)) => {
2257            match_expr_into(pl, tl, subst, bound) && match_expr_into(pr, tr, subst, bound)
2258        }
2259        (ProofExpr::Not(p), ProofExpr::Not(t)) => match_expr_into(p, t, subst, bound),
2260        (
2261            ProofExpr::ForAll {
2262                variable: pv,
2263                body: pb,
2264            },
2265            ProofExpr::ForAll {
2266                variable: tv,
2267                body: tb,
2268            },
2269        )
2270        | (
2271            ProofExpr::Exists {
2272                variable: pv,
2273                body: pb,
2274            },
2275            ProofExpr::Exists {
2276                variable: tv,
2277                body: tb,
2278            },
2279        ) => {
2280            if pv != tv {
2281                return false;
2282            }
2283            bound.push(pv.clone());
2284            let ok = match_expr_into(pb, tb, subst, bound);
2285            bound.pop();
2286            ok
2287        }
2288        // Any other variant pair: match only on structural equality — no
2289        // bindings inside shapes this matcher does not walk (conservative).
2290        _ => pattern == target,
2291    }
2292}
2293
2294#[cfg(test)]
2295#[path = "../../logicaffeine_tests/unit/logicaffeine_proof/unify/tests.rs"]
2296mod tests;