Dependencies.hs

module Dependencies (Analyzer (..), mkAnalyzer, News, Build, Graph) where

import Data.Set (Set)
import qualified Data.Set as S
import qualified Data.Map as M
import Control.Arrow ((&&&))
import Control.Applicative ((<$>))
import Data.Monoid (Monoid, mappend, mempty)

import DirectedGraph

type Graph = DirectedGraph

-- the running state of the analyzer
data Analyze a = Analyze
    { graph   :: Graph a  -- actual dependency graph
    , todo    :: Set a    -- targets to be built
    , done    :: Set a    -- targets built
    }

-- | Effects of a build action, targets that must be built and a dependency graph. FIX this splitted informations
type News a = (Set a, Graph a)

-- compute a new state for the analyzer. aside widening the graph new targets are inserted in the todo
insertNews :: (Ord a, Eq a)   => Graph a    -- previous graph
                              -> Analyze a  -- current state
                              -> News a     -- news from the build action
                              -> Analyze a  -- new state
insertNews prev  (Analyze g rs ds) (nrs,ng)=
  let   g' = g `mappend` ng -- new current graph
        igns = nodes ng `S.difference` nrs -- targets mentioned only in the graph (not marked as todo from outside)
        cdeps = S.fromList $ filter (\x -> x `neighbours` prev /= x `neighbours` g') $ S.toList $ igns -- touched father targets
        deps = reachableNodes (nrs `mappend` cdeps) g' -- dependants of asked targets and touched father targets
  in Analyze g' (rs `mappend` (deps `S.difference` ds)) ds

-- | build action, from a target to its effect. Client can use monad m for his businnes
type Build m a = a -> m (News a)

-- | State machine to drive the building of targets.
data Analyzer m a   = Done (Graph a)  -- | Work is over, the graph given is useful for next run
                    | Cycle           -- | A cycle was detected, abort
                    | Step (Build m a -> m (Analyzer m a)) -- | machine regular stepping 

-- | Boot an analyzer from the previous graph. Use mempty when it's missing.
mkAnalyzer prev = step prev $ Analyze mempty mempty mempty

-- check the Done state or fire a research for a target to build
step :: (Functor m, Ord a, Monad m) => Graph a -> Analyze a -> Analyzer m a
step prev r = case S.null $ todo r of
    -- No remaining items, spits out the new graph
    True -> Done $ graph r
    -- An item remains, let's find a ready item
    False -> findReady prev r $ S.findMin $ todo r

--  Find an item ready to be compiled. Goes straight down to the *left* until an item with all dependencies done is found.
findReady :: (Functor m, Monad m, Ord a) => Graph a -> Analyze a -> a -> Analyzer m a
findReady prev r x = findReady' r x S.empty where
    findReady' r@(Analyze g todos dones) x vs
        -- We already visited this item, cycle detected!
        | x `S.member` vs = Cycle
        -- The x has all neighbours in done set
        | neighbours x g `S.isSubsetOf` dones = let 
                insertion = insertNews prev $ Analyze g (x `S.delete` todos) (x `S.insert` dones)
                in Step $ \f -> step prev <$> insertion <$> f x
        -- Continue our search: find a neighbour we haven't visited yet
        | otherwise = let   ds = neighbours x g `S.difference` vs 
                            x = S.findMin ds
                      in if S.null ds then Cycle else findReady' r x (S.insert x vs)