///|
/// Multi-pattern support (datalog-style rules)
pub struct MultiPattern {
  asts : Array[(String, Pattern)]
  program : Program
}

///|
pub fn MultiPattern::new(asts : Array[(String, Pattern)]) -> MultiPattern {
  MultiPattern::{ program: Program::compile_from_multi(asts), asts }
}

///| Parse a multipattern string like "?x = pat1 = pat2, ?y = pat3".
pub fn parse_multipattern(s : String) -> MultiPattern raise {
  let asts : Array[(String, Pattern)] = Array::new()
  for clause_str in s.split(",") {
    let clause = clause_str.trim()
    if clause.is_empty() {
      continue
    }
    let parts = clause.split("=")
    let items : Array[String] = Array::new()
    for p in parts {
      let t = p.trim()
      if !t.is_empty() {
        items.push(t.to_string())
      }
    }
    if items.is_empty() {
      fail("bad multipattern clause")
    }
    let binder_raw = items[0]
    if !binder_raw.has_prefix("?") {
      fail("binder must start with ?")
    }
    let binder_view = try! binder_raw[1:]
    let binder = binder_view.to_string()
    for i in 1.. Array[Match] {
  let results : Array[Match] = Array::new()
  for class_id in egraph.class_ids() {
    let root = egraph.find(class_id)
    let substs = self.program.run_with_limit(egraph, root, limit=None)
    for subst in substs {
      results.push(Match::{ root, subst })
    }
  }
  results
}

///|
pub fn MultiPattern::n_matches(self : MultiPattern, egraph : EGraph) -> Int {
  self.search(egraph).length()
}

///|
pub fn multipattern_searcher(mp : MultiPattern) -> Searcher {
  Searcher::{
    run: egraph => {
      let results : Array[Match] = Array::new()
      for class_id in egraph.class_ids() {
        let root = egraph.find(class_id)
        let substs = mp.program.run_with_limit(egraph, root, limit=None)
        for subst in substs {
          results.push(Match::{ root, subst })
        }
      }
      results
    },
  }
}

///|
pub struct MultiApplier {
  asts : Array[(String, Pattern)]
}

///|
pub fn multi_applier(asts : Array[(String, Pattern)]) -> MultiApplier {
  MultiApplier::{ asts }
}

///|
pub fn MultiApplier::apply(
  self : MultiApplier,
  egraph : EGraph,
  subst : Map[String, Id],
) -> Id raise {
  let mut first : Id? = None
  let ctx = subst.copy()
  for pair in self.asts {
    let (binder, pat) = pair
    let id = build_rhs(pat, egraph, ctx.copy())
    match ctx.get(binder) {
      Some(existing) => {
        ignore(egraph.union(existing, id))
      }
      None => ctx.set(binder, id)
    }
    if first is None {
      first = Some(id)
    }
  }
  first.unwrap()
}

///|
pub fn multi_rewrite(
  name : String,
  lhs : String,
  rhs : String,
) -> Rewrite raise {
  let lhs_mp = parse_multipattern(lhs)
  let rhs_mp = parse_multipattern(rhs)
  let searcher = multipattern_searcher(lhs_mp)
  let applier = Applier::from_fn((eg, subst) => rhs_mp_applier(rhs_mp, eg, subst))
  Rewrite::from_parts(name, searcher, applier)
}

///|
pub fn rhs_mp_applier(
  mp : MultiPattern,
  eg : EGraph,
  subst : Map[String, Id],
) -> Id raise {
  multi_applier(mp.asts).apply(eg, subst)
}