Can EGraph be Sync + Send?

[cksac]

Currently EGraph not Sync+Send due to Arc<dyn Macro<T>> not Sync+Send. Can we make Parser Sync+Send?

#[derive(Clone)]
pub struct Parser {
    commands: HashMap<Symbol, Arc<dyn Macro<Vec<Command>>>>,
    actions: HashMap<Symbol, Arc<dyn Macro<Vec<Action>>>>,
    exprs: HashMap<Symbol, Arc<dyn Macro<Expr>>>,
    pub symbol_gen: SymbolGen,
}

[Alex-Fischman]

I'm not super familiar with Rust concurrency, but the following code gives me many different error messages (that are not related to Parser). Why do you believe that the Parser is the problem?

const _: () = {
    fn assert_send<T: Send>() {}
    fn assert_sync<T: Sync>() {}
    fn assert_all() {
        assert_send::<EGraph>();
        assert_sync::<EGraph>();
    }
};

[Alex-Fischman]

Also, what is your use case? We can (maybe?) make it Send and Sync if we have a good reason to do so... You might be better served by serialization depending on your application though.

[cksac]

I would like to use EGraph with lazy_static

lazy_static::lazy_static! {
    pub static ref RT:  std::sync::Mutex<EGraph> = std::sync::Mutex::new(EGraph::default());
}

you are right, there are numbers of errors, not only the Parser.

314 | / pub struct Rc<
315 | |     T: ?Sized,
316 | |     #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator = Global,
317 | | > {
    | |_- doesn't satisfy `Rc<egglog::actions::Program>: Send` or `Rc<egglog::function::index::ColumnIndex>: Send`
    |
    = note: the following trait bounds were not satisfied:
            `(dyn Macro<Vec<GenericCommand<Symbol, Symbol>>> + 'static): Sync`
            which is required by `Mutex<EGraph>: Sync`
            `(dyn Macro<Vec<GenericCommand<Symbol, Symbol>>> + 'static): Send`
            which is required by `Mutex<EGraph>: Sync`
            `(dyn Macro<Vec<GenericAction<Symbol, Symbol>>> + 'static): Sync`
            which is required by `Mutex<EGraph>: Sync`
            `(dyn Macro<Vec<GenericAction<Symbol, Symbol>>> + 'static): Send`
            which is required by `Mutex<EGraph>: Sync`
            `(dyn Macro<GenericExpr<Symbol, Symbol>> + 'static): Sync`
            which is required by `Mutex<EGraph>: Sync`
            `(dyn Macro<GenericExpr<Symbol, Symbol>> + 'static): Send`
            which is required by `Mutex<EGraph>: Sync`
            `Rc<egglog::actions::Program>: Send`
            which is required by `Mutex<EGraph>: Sync`
            `Rc<egglog::function::index::ColumnIndex>: Send`
            which is required by `Mutex<EGraph>: Sync`
            `(dyn PrimitiveLike + 'static): Sync`
            which is required by `Mutex<EGraph>: Sync`
            `(dyn PrimitiveLike + 'static): Send`
            which is required by `Mutex<EGraph>: Sync`

[Alex-Fischman]

Currently the union-find can not be easily made thread safe due to it's use of interior mutability. We are working on a new backend for egglog that will support parallel access. In the meantime, if you want a global mutable e-graph, I suggest just passing it around. If you require interior mutability, you can use Rc<RefCell<EGraph>> instead.

[yihozhang]

Actually, I'm able to make the EGraph implement the Send trait by using thread-safe alternatives. See #517.

Interior mutability could be an issue, but not in this case I think. For example, UnionFind::find takes an immutable self reference but updates its entries, so if two immutable references to the EGraph concurrently call UnionFind::find, this may cause a race condition. But in the case of Mutex, this won't happen because only one reference (immutable or mutable) can be obtained at a time. In fact, wrapping the E-graph inside a RwLock fails the type check as expected

    lazy_static! {
        pub static ref RT2: RwLock<EGraph> = RwLock::new(EGraph::default());
    }

[Alex-Fischman]

Thanks Yihong! I guess checking the EGraph for Send+Sync was the wrong test.