Rust / Egg (E-graphs): the size for values of type dyn cannot be known at compilation time

Question

I'm working with the documentation of egg (e-graphs good) to define a cost function that uses Analysis class. I copied their example.

I have defined the following:

#[derive(Default)]
struct CostData;
impl Analysis<MyLanguage> for CostData {
    type Data = (Option<u64>, Option<Symbol>, Option<(Symbol, u64)>, Option<Vec<(Option<Symbol>, Option<u64>)>>);

    fn merge(&mut self, to: &mut Self::Data, from: Self::Data) -> DidMerge {
        egg::merge_min(to, from)
    }

    fn make(egraph: &EGraph<MyLanguage, Self>, enode: &MyLanguage) -> Self::Data {
      // implementation
    }
}

struct EGraphCostFn<'a> {
    egraph: &'a EGraph<MyLanguage, Analysis<MyLanguage, 
    Data = (Option<u64>, Option<Symbol>, Option<(Symbol, u64)>, Option<Vec<(Option<Symbol>, Option<u64>)>>)>>,
}

impl<'a> CostFunction<MyLanguage> for EGraphCostFn<'a> {
    type Cost = usize;
    fn cost<C>(&mut self, enode: &MyLanguage, mut costs: C) -> Self::Cost
    where
        C: FnMut(Id) -> Self::Cost
    {
       // implementation
    } 
}

However, I get the following error: error[E0782]: trait objects must include the `dyn` keyword

When I added dyn:

struct EGraphCostFn<'a> {
    egraph: &'a EGraph<MyLanguage, dyn Analysis<MyLanguage, 
    Data = (Option<u64>, Option<Symbol>, Option<(Symbol, u64)>, Option<Vec<(Option<Symbol>, Option<u64>)>>)>>,
} 

I get:

error[E0277]: the size for values of type `(dyn egg::Analysis<MyLanguage, Data = (Option<u64>, Option<egg::Symbol>, Option<(egg::Symbol, u64)>, Option<Vec<(Option<egg::Symbol>, Option<u64>)>>)> + 'static)` cannot be known at compilation time
error[E0038]: the trait `egg::Analysis` cannot be made into an object

Also tried to wrap it in Box:

struct EGraphCostFn<'a> {
    egraph: &'a EGraph<MyLanguage, Box<dyn Analysis<MyLanguage, 
    Data = (Option<u64>, Option<Symbol>, Option<(Symbol, u64)>, Option<Vec<(Option<Symbol>, Option<u64>)>>)>>>,
}

But got:

error[E0277]: the trait bound `Box<(dyn egg::Analysis<MyLanguage, Data = (Option<u64>, Option<egg::Symbol>, Option<(egg::Symbol, u64)>, Option<Vec<(Option<egg::Symbol>, Option<u64>)>>)> + 'static)>: egg::Analysis<MyLanguage>` is not satisfied

Any ideas what I need to change to make it work? Thanks

Answer 1

try substituting the second parameter in the generic list of EGraph there for a concrete type or generic parameter.

struct EGraphCostFn<'a> {
    egraph: &'a EGraph<MyLanguage, Analysis<MyLanguage, 
    Data = (Option<u64>, Option<Symbol>, Option<(Symbol, u64)>, Option<Vec<(Option<Symbol>, Option<u64>)>>)>>,
}

should be

type MyLanguageAnalysisData = (Option<u64>, Option<Symbol>, Option<(Symbol, u64)>, Option<Vec<(Option<Symbol>, Option<u64>)>>);

struct EGraphCostFn<'a, C> {
    egraph: &'a EGraph<MyLanguage, C>
} where C: Analysis<MyLanguage, Data = MyLanguageAnalysisData>