type Id = Int

pub(all) suberror ParseError {
  UnexpectedEof
  UnexpectedChar(Int, Char)
  ExpectedRParen(Int)
}

pub(all) struct Analysis {
  make : (ENode, (Int) -> Data?) -> Data
  merge : (Data, Data) -> Data
  modify : (EGraph, Int) -> Unit
}

pub struct Applier {
  apply : (EGraph, Map[String, Int]) -> Int raise
}

pub(all) struct Data {
  free : Map[Int, Bool]
  constant : Value?
}

pub struct EClass {
  id : Int
  nodes : Array[Int]
  data : Data
}

#alias(SimpleGraph)
pub struct EGraph {
  uf : UnionFind
  classes : Map[Int, EClass]
  memo : Map[NodeKey, Int]
  nodes : Array[ENode]
  node_classes : Array[Int]
  dirty : Bool
  analysis : Analysis
  allow_cycles : Bool
}

pub struct ENode {
  op : NodeOp
  children : Array[Int]
}

pub enum ENodeOrReg {
  Node(ENode)
  Reg(Int)
}

pub struct ExplainEdge {
  from : Int
  to : Int
  rewrite : String
  iter : Int
  subst : Map[String, Int]
}

pub struct ExplainStep {
  iter : Int
  rewrite : String
  root_before : Int
  rhs_id : Int
  subst : Map[String, Int]
}

pub struct Explanation {
  steps : Array[ExplainStep]
  edges : Map[Int, Array[ExplainEdge]]
}

pub enum Expr {
  Leaf(String)
  Node(String, Array[Expr])
}

pub enum Instruction {
  Bind(NodeOp, Int, Int, Int)
  Compare(Int, Int)
  Lookup(Array[ENodeOrReg], Int)
  Scan(Int)
}

pub struct IterationReport {
  iter : Int
  matched : Map[String, Int]
  applied : Map[String, Int]
  total_matched : Int
  total_applied : Int
  node_count : Int
  class_count : Int
  saturated : Bool
}

pub(all) struct Match {
  root : Int
  subst : Map[String, Int]
}

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

pub struct MultiPattern {
  asts : Array[(String, Pattern)]
  program : Program
}

type NodeKey

pub enum NodeOp {
  Name(String)
  Symbol(String)
  Number(Float)
}

pub enum Pattern {
  Wild
  Var(String)
  VarIf(String, (Int) -> Bool)
  Sym(String)
  Num(Float)
  Node(String, Array[Pattern])
}

pub struct Program {
  instructions : Array[Instruction]
  subst : Map[String, Int]
  var_if : Map[String, (Int) -> Bool]
}

pub struct Rewrite {
  name : String
  searcher : Searcher
  applier : Applier
  condition : (EGraph, Map[String, Int]) -> Bool
}

pub struct RewriteStats {
  name : String
  matched : Int
  applied : Int
}

pub struct RunConfig {
  iter_limit : Int
  node_limit : Int?
  match_limit : Int?
  worklist : Worklist
  allow_ematching_cycles : Bool
}

pub struct RunResult {
  egraph : EGraph
  root : Int
  iterations : Int
  stop_reason : StopReason
  applied : Map[String, Int]
  total_applied : Int
  reports : Array[IterationReport]
  explanation : Explanation
}

pub struct Runner {
  rewrites : Array[Rewrite]
  queue : Array[Rewrite]
  egraph : EGraph
  root : Int
  config : RunConfig
  backoff : Map[String, Int]
  last_applied : Map[String, Int]
}

pub struct Searcher {
  run : (EGraph) -> Array[Match]
}

pub enum StopReason {
  Saturated
  IterationLimit
  NodeLimit
  MatchLimit
}

type TodoKey

pub struct UnionFind {
  parents : Array[Int]
  sizes : Array[Int]
}

pub(all) enum Value {
  Num(Float)
  Bool(Bool)
}

pub(all) enum Worklist {
  All
  Queue
  Backoff
  Greedy
  Recent
}

fn bool_analysis() -> Analysis

fn build_rhs(pat : Pattern, egraph : EGraph, subst : Map[String, Int]) -> Int raise

fn constant_analysis() -> Analysis

fn data_bool(d : Data?) -> Bool?

fn data_num(d : Data?) -> Float?

fn default_analysis() -> Analysis

fn default_cost(op : NodeOp, child_costs : Array[Int]) -> Int

fn expr_leaf(name : String) -> Expr

fn expr_node(op : String, children : Array[Expr]) -> Expr

fn extract_best(egraph : EGraph, root : Int, cost_fn? : (NodeOp, Array[Int]) -> Int) -> (Int, Expr) raise

fn intersect_free(a : Map[Int, Bool], b : Map[Int, Bool]) -> Map[Int, Bool]

fn is_const(name : String) -> ((EGraph, Map[String, Int]) -> Bool)

fn is_const_or_distinct(name : String, other : String) -> ((EGraph, Map[String, Int]) -> Bool)

fn is_not_zero(name : String) -> ((EGraph, Map[String, Int]) -> Bool)

fn is_sym(name : String) -> ((EGraph, Map[String, Int]) -> Bool)

fn lambda_analysis() -> Analysis

fn make_enode(op : String, children : Array[Int]) -> ENode

fn make_number(n : Float) -> ENode

fn make_symbol(sym : String) -> ENode

fn math_rules() -> Array[Rewrite] raise

fn merge_data(left : Data, right : Data) -> Data

fn multi_applier(asts : Array[(String, Pattern)]) -> MultiApplier

fn multi_rewrite(name : String, lhs : String, rhs : String) -> Rewrite raise

fn multipattern_searcher(mp : MultiPattern) -> Searcher

fn parse_multipattern(s : String) -> MultiPattern raise

fn parse_pattern(expr : Expr) -> Pattern raise

fn parse_sexpr(s : String) -> Expr raise ParseError

fn pat_node(op : String, children : Array[Pattern]) -> Pattern

fn pat_num(n : Float) -> Pattern

fn pat_sym(name : String) -> Pattern

fn pat_var(name : String) -> Pattern

fn pat_var_if(name : String, pred : (Int) -> Bool) -> Pattern

fn pat_wild() -> Pattern

fn reachable_classes(egraph : EGraph, root : Int) -> Map[Int, Bool]

fn rhs_mp_applier(mp : MultiPattern, eg : EGraph, subst : Map[String, Int]) -> Int raise

fn run(expr : Expr, rewrites : Array[Rewrite], config? : RunConfig) -> RunResult raise

fn run_rewrites(expr : Expr, rewrites : Array[Rewrite], iter_limit? : Int) -> (EGraph, Int) raise