{-# LANGUAGE UndecidableInstances #-} -- tmp show
{-# LANGUAGE FlexibleContexts #-}
{-# OPTIONS_HADDOCK hide #-}
{-|
 Non-abstract definition of e-graphs
 -}
module Data.Equality.Graph.Internal where

import Data.Functor.Classes

import Data.Equality.Graph.ReprUnionFind
import Data.Equality.Graph.Classes
import Data.Equality.Graph.Nodes
import Data.Equality.Analysis

-- | E-graph representing terms of language @l@.
--
-- Intuitively, an e-graph is a set of equivalence classes (e-classes). Each e-class is a
-- set of e-nodes representing equivalent terms from a given language, and an e-node is a function
-- symbol paired with a list of children e-classes.
data EGraph l = EGraph
    { forall (l :: * -> *). EGraph l -> ReprUnionFind
unionFind :: !ReprUnionFind           -- ^ Union find like structure to find canonical representation of an e-class id
    , forall (l :: * -> *). EGraph l -> ClassIdMap (EClass l)
classes   :: !(ClassIdMap (EClass l)) -- ^ Map canonical e-class ids to their e-classes
    , forall (l :: * -> *). EGraph l -> Memo l
memo      :: !(Memo l)                -- ^ Hashcons maps all canonical e-nodes to their e-class ids
    , forall (l :: * -> *). EGraph l -> Worklist l
worklist  :: !(Worklist l)            -- ^ Worklist of e-class ids that need to be upward merged
    , forall (l :: * -> *). EGraph l -> Worklist l
analysisWorklist :: !(Worklist l)     -- ^ Like 'worklist' but for analysis repairing
    }

-- | The hashcons 𝐻  is a map from e-nodes to e-class ids
type Memo l = NodeMap l ClassId

-- | Maintained worklist of e-class ids that need to be “upward merged”
type Worklist l = [(ClassId, ENode l)]

instance (Show (Domain l), Show1 l) => Show (EGraph l) where
    show :: EGraph l -> String
show (EGraph ReprUnionFind
a ClassIdMap (EClass l)
b Memo l
c Worklist l
d Worklist l
e) =
        String
"UnionFind: " forall a. Semigroup a => a -> a -> a
<> forall a. Show a => a -> String
show ReprUnionFind
a forall a. Semigroup a => a -> a -> a
<>
            String
"\n\nE-Classes: " forall a. Semigroup a => a -> a -> a
<> forall a. Show a => a -> String
show ClassIdMap (EClass l)
b forall a. Semigroup a => a -> a -> a
<>
                String
"\n\nHashcons: " forall a. Semigroup a => a -> a -> a
<> forall a. Show a => a -> String
show Memo l
c forall a. Semigroup a => a -> a -> a
<>
                    String
"\n\nWorklist: " forall a. Semigroup a => a -> a -> a
<> forall a. Show a => a -> String
show Worklist l
d forall a. Semigroup a => a -> a -> a
<>
                        String
"\n\nAnalWorklist: " forall a. Semigroup a => a -> a -> a
<> forall a. Show a => a -> String
show Worklist l
e