Emit deterministic output

[fitzgen]

The graphviz output is not deterministic because nodes are added to a hash map and then the contents of the hash map are later iterated over. Rusts standard library’s hash maps do not have stable iteration order. This makes the graphviz output unsuitable for use as test expectations/fixtures.

For example:

• https://github.com/egraphs-good/egraph-serialize/blob/main/src/graphviz.rs#L38
• https://github.com/egraphs-good/egraph-serialize/blob/main/src/graphviz.rs#L83

(I haven’t audited the rest of the code for other occurrences)

I suggest instead either using BTreeMap or collecting the hash map entries into a vec and then sorting it before iteration.

I can send a PR in the next day or so if no one else fixes this before then. Let me know if you prefer one of the above options to another.

Thanks!

Aside: I’ve been having fun experimenting with a little compiler to combine egraphs and a sea-of-nodes ish IR, trying to explore what we are missing in Cranelift land by only bringing the pure subset of the DFG into our egraph. Chris told me y’all were doing something similar, and I saw the eggcc RSVDG stuff in the test directory. Looks pretty neat! Would love to chat sometime.

[fitzgen]

Ah it seems that the example I linked above is actually a BTreeMap on main now, but not in the 0.1.0 on crates.io that egglog depends on.

But even after patching in main locally, I still get nondeterministic results from serializing egglog::EGraphs. Haven't tracked down where the nondeterminism is coming from yet.