Stack overflow during rule application

[bksaiki]

Encountering a stack overflow using Herbie. Using RUST_LOG=debug, it seemed to occur during rule application. Created a unit test to run with the same expressions and rules.

Rust version: 1.79.0
OS: Ubuntu 24.04 via WSL2
Arch: x86_64

Reproduce:

• checkout Herbie at egg-segfault
• in egg-herbie/ run cargo test --release

[pavpanchekha]

I didn't like the branch hanging around, so I shrunk the repro down to a single file; I also took the liberty of deleting everything I could (while keeping the segfault), to bring it down to under 100 lines:

//! ```cargo
//! [dependencies]
//! egg = "0.10.0"
//! num-rational = "0.4.0"
//! ```

use egg::*;

pub type Constant = num_rational::BigRational;
pub type RecExpr = egg::RecExpr<Math>;
pub type EGraph = egg::EGraph<Math, ConstantFold>;
pub type Rewrite = egg::Rewrite<Math, ConstantFold>;
pub type Runner = egg::Runner<Math, ConstantFold>;

// The minimal operators we need
define_language! {
    pub enum Math {
        "*" = Mul([Id; 2]),
        "/" = Div([Id; 2]),
        Constant(Constant),
        Symbol(egg::Symbol),
    }
}

#[derive(Clone, Default)]
pub struct ConstantFold {}

impl Analysis<Math> for ConstantFold {
    type Data = Option<Constant>;
    fn make(egraph: &mut EGraph, enode: &Math) -> Self::Data {
        let x = |id: &Id| egraph[*id].data.clone();

        Some(match enode {
            Math::Constant(c) => c.clone(),
            Math::Mul([a, b]) => x(a)? * x(b)?,
            Math::Div([a, b]) => x(a)? / x(b)?,
            _ => return None,
        })
    }

    fn merge(&mut self, to: &mut Self::Data, from: Self::Data) -> DidMerge {
        match (&to, from) {
            (None, None) => DidMerge(false, false),
            (Some(_), Some(_)) => DidMerge(false, false),
            (Some(_), None) => DidMerge(false, true),
            (None, Some(c)) => {
                *to = Some(c);
                DidMerge(true, false)
            }
        }
    }

    fn modify(egraph: &mut EGraph, class_id: Id) {
        if let Some(c) = egraph[class_id].data.clone() {
            let const_id = egraph.add(Math::Constant(c));
            egraph.union(class_id, const_id);
        }
    }
}

#[test]
fn repro() {
    let expr : RecExpr = "(/ (* x (* x 707281/11664)) (* 841/108 x))".parse().unwrap();

    let rules: Vec<Rewrite> = vec![
        rewrite!("times-frac"; "(/ (* ?a ?b) (* ?c ?d))" => "(* (/ ?a ?c) (/ ?b ?d))"),
        rewrite!("*-inverses"; "(/ ?a ?a)" => "1"),
        rewrite!("swap-sqr"; "(* (* ?a ?b) (* ?a ?b))" => "(* (* ?a ?a) (* ?b ?b))"),
        rewrite!("associate-*r*"; "(* ?a (* ?b ?c))" => "(* (* ?a ?b) ?c)"),
        rewrite!("associate-*l*"; "(* (* ?a ?b) ?c)" => "(* ?a (* ?b ?c))"),
        rewrite!("associate-*r/"; "(* ?a (/ ?b ?c))" => "(/ (* ?a ?b) ?c)"),
        rewrite!("associate-*l/"; "(* (/ ?a ?b) ?c)" => "(/ (* ?a ?c) ?b)"),
        rewrite!("associate-/r*"; "(/ ?a (* ?b ?c))" => "(/ (/ ?a ?b) ?c)"),
        rewrite!("associate-/r/"; "(/ ?a (/ ?b ?c))" => "(* (/ ?a ?b) ?c)"),
        rewrite!("associate-/l/"; "(/ (/ ?b ?c) ?a)" => "(/ ?b (* ?a ?c))"),
        rewrite!("associate-/l*"; "(/ (* ?b ?c) ?a)" => "(* ?b (/ ?c ?a))"),
        rewrite!("*-commutative"; "(* ?a ?b)" => "(* ?b ?a)"),
    ];
    
    Runner::new(Default::default()).with_expr(&expr).run(&rules);
}

[pavpanchekha]

I've confirmed it still segfaults with egg v0.10.0.

[bksaiki]

Reproduced on my system (Ubuntu 24.04 / WSL2, Rust 1.82.0, using dependencies in @pavpanchekha's example)

[pavpanchekha]

Ok, deleting the branch in the repo description.