Enumerate all submodules in the permuter, modulo rewrites

[gussmith23]

• Figure out what's causing infinite loop
• Enumerate all modules into Rust object (I can get them as strings; see below)
• Given an eclass that may contain loops, extract a representative #405

[gussmith23]

I'm working on this. Two things I'm running into:

1. there's an infinite loop somewhere (my gut tells me it's on the extraction of Vars, maybe?). Or maybe extraction's just really slow for a sufficiently large example?
2. I'm struggling with the egglog API to get all the modules in a Rust object.

Raw paste of a slack thread:

also, i’m trying to extract all the things that match a certain query. seems like query-extract is what i want. but i’m confused at how to use it correctly. from Rust, is it possible to use it and then get the results into a Rust object? the best i can seem to do is to run it via parse_and_run_program and then get a list of strings out.
3 replies


Gus Smith
  [19 minutes ago](https://uw-cse.slack.com/archives/C01JJQNFA3G/p1701562702322689?thread_ts=1701562620.551559&cid=C01JJQNFA3G)
i also tried constructing a QueryExtract directly but its behavior is not what i expected. after i run it and check the extract report, it seems to be missing variants. despite there being many variants available, the extract report only lists a single variant!


Gus Smith
  [3 minutes ago](https://uw-cse.slack.com/archives/C01JJQNFA3G/p1701563662777529?thread_ts=1701562620.551559&cid=C01JJQNFA3G)
hm i’m looking at how QueryExtract is desugared here: https://github.com/egraphs-good/egglog/blob/41562802315eccc9136c9d2ae6967d2df4071420/src/ast/desugar.rs#L611-L625
I understand why the ExtractReport only has one thing in it; a QueryExtract for a “complex” query (i.e. not a Var) is actually multiple extract commands, and so i’m just getting the last one that fires! (please check my understanding if i’m wrong on this)
is there a way around this? as a hack I can presumably just convert the string results that i get back from parse_and_run_program into something usable in Rust, though it’s not ideal.

[desugar.rs](https://github.com/egraphs-good/egglog/blob/41562802315eccc9136c9d2ae6967d2df4071420/src/ast/desugar.rs)
        Command::QueryExtract { variants, expr } => {
            let fresh = desugar.get_fresh();
            let fresh_ruleset = desugar.get_fresh();
            let desugaring = if let Expr::Var(v) = expr {
                format!("(extract {v} {variants})")
Show more
<https://github.com/[egraphs-good/egglog](https://github.com/egraphs-good/egglog)|egraphs-good/egglog>egraphs-good/egglog | Added by [GitHub](https://uw-cse.slack.com/services/B01UA55DHT7)


Gus Smith
  [2 minutes ago](https://uw-cse.slack.com/archives/C01JJQNFA3G/p1701563692085159?thread_ts=1701562620.551559&cid=C01JJQNFA3G)
like it would be great if all the ExtractReports were saved

[gussmith23]

I think loops are caused, unsurprisingly, by loops. Still digging further. I'm not sure it fully makes sense to me yet. Here's my thought process:

• I could see there being an issue extracting MakeModule when the represented module has a loop. Because you can't flatten it into an expr. (Would this be a problem for extraction? or for printing? or both?)
• But I also don't know if our current Op_ etc. constructs actually allow for expressing designs with cycles. Do they? I didn't do any intentional design to enable expressing loops/cycles, but maybe they "just work".

[gussmith23]

See egraphs-good/egglog#315

[gussmith23]

There are two separate issues here.

1. There's the overarching task (that actually doesn't fall under this GitHub Issue) of extracting a hardware design that is represented purely as apply nodes. That task implies that we also need to extract a MakeModule node for each apply node, but that's actually a separate task.
2. The task of extracting a single MakeModule node from an eclass of them. And specifically, when they have cycles.

Both need to be done. I feel like it makes more sense to do 2 first, rather than 1.