WIP: Added function for extracting all possible expressions from an eclass
@@ -182,6 +182,61 @@ fn minimize_equalities(
return all_removed;
}
+fn cartesian_product<T : Clone>(lists: &Vec<Vec<T>>) -> Vec<Vec<T>> {
+ let mut res = vec![];
+
+ let mut list_iter = lists.iter();
+ if let Some(first_list) = list_iter.next() {
+ for i in first_list.clone() {
+ res.push(vec![i]);
+ }
+ }
+ for l in list_iter {
+ let mut tmp = vec![];
+ for r in res {
+ for el in l.clone() {
+ let mut tmp_el = r.clone();
+ tmp_el.push(el);
+ tmp.push(tmp_el);
+ }
+ }
+ res = tmp;
+ }
+ res
+}
+
+fn extract_all_exps(egraph : &EGraph<SimpleMath, SynthAnalysis>,
+ memo : &mut HashMap<Id, Vec<Vec<SimpleMath>>>,
+ root : Id) -> Vec<Vec<SimpleMath>> {
+ let mut exps = vec!();
+ if memo.contains_key(&root) {
+ return memo[&root].clone();
+ } else {
+ // Memo handles cycles naturally
+ memo.insert(root, vec!());
+ }
+
+ for n in egraph[root].iter() {
+ if n.is_leaf() {
+ return vec!(vec!(n.clone()));
+ } else {
+ let mut child_nodes = vec!();
+
+ n.for_each(|c| child_nodes.push(extract_all_exps(egraph, memo, c)));
+
+ let poss_exps = cartesian_product(&child_nodes);
+ for child_list in poss_exps {
+ let mut exp_nodes = child_list.concat();
+ exp_nodes.push(n.clone());
+ exps.push(exp_nodes);
+ }
+ }
+ }
+
+ memo.insert(root, exps.clone());
+ exps
+}
+
pub struct SynthParam {
rng: Pcg64,
n_iter: usize,
@@ -279,6 +334,18 @@ impl SynthParam {
if let Some(eq) = Equality::new(pat1, pat2) {
equalities.push(eq);
}
+
+ // for exp1 in extract_all_exps(&eg, &mut exp_memo, i.clone()) {
+ // for exp2 in extract_all_exps(&eg, &mut exp_memo, j.clone()) {
+ // let names = &mut HashMap::default();
+ // let pat1 = generalize(&RecExpr::from(exp1.clone()), names);
+ // let pat2 = generalize(&RecExpr::from(exp2), names);
+
+ // if let Some(eq) = Equality::new(pat1, pat2) {
+ // equalities.push(eq);
+ // }
+ // }
+ // }
}
}
