module DataFlow(dataFlowAnalysis, Direction(..)) where

import Data.Function
import Data.List
import qualified Data.Map.Strict as Map


data Direction = Forwards | Backwards
  deriving (Show, Eq)

dataFlowAnalysis
        :: Ord id
        -- | The direction of the dataflow analysis
        => Direction               
        -- | The control flow graph of basic blocks
        -> Map.Map id [id]         
        -- | The initial values
        -> (id -> state)           
        -- | The transfer function; note that the meaning of the states
        -- depends on the direction
        -> (state -> id -> state)  
        -- | For each block, the incoming state and the outgoing state
        -> Map.Map id (state, state)
dataFlowAnalysis Backwards cfg initF transF =
    Map.map (\(a, b) -> (b, a)) $
        dataFlowAnalysis Forwards (reverseGraph cfg) initF transF
dataFlowAnalysis Forwards cfg initF transF = undefined


reverseGraph :: Ord a => Map.Map a [a] -> Map.Map a [a]
reverseGraph graph =
    Map.fromList
    . map ((,) <$> (fst . head) <*> map snd)
    . groupBy ((==) `on` fst)
    . sortBy (compare `on` fst)
    $ [(to, from)
      | (from, tos) <- Map.assocs graph
      , to <- tos]