summaryrefslogtreecommitdiff
path: root/lib/Dirgraph.hs
blob: 48732280201e1f90ef63510955bd04fbafda9527 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE LambdaCase       #-}
{-# LANGUAGE TupleSections    #-}

-- | Simple directed graphs, for dependency checking
module Dirgraph where

import           Universum

import           CheckMap        (MapResult (mapresultDepends))
import           Data.Map.Strict (mapMaybeWithKey, mapWithKey, traverseWithKey)
import qualified Data.Map.Strict as M
import           Data.Set        ((\\))
import qualified Data.Set        as S
import           Paths           (normalise)
import           Text.Dot        (Dot, (.->.))
import qualified Text.Dot        as D
import           Types           (Dep (LocalMap))

-- | a simple directed graph
type Graph a = Map a (Set a)

nodes :: Graph a -> Set a
nodes = M.keysSet

-- | simple directed graph of exits
resultToGraph :: Map FilePath (MapResult a) -> Graph FilePath
resultToGraph = fmap (S.fromList . mapMaybe onlyLocalMaps . mapresultDepends)
  where onlyLocalMaps = \case
          LocalMap path -> Just (normalise "" path)
          _             -> Nothing

-- | invert edges of a directed graph
invertGraph :: (Eq a, Ord a) => Graph a -> Graph a
invertGraph graph = mapWithKey collectFroms graph
  where collectFroms to _ = S.fromList . elems . mapMaybeWithKey (select to) $ graph
        select to from elems = if to `elem` elems then Just from else Nothing

-- | all nodes reachable from some entrypoint
reachableFrom :: Ord a => a -> Graph a -> Set a
reachableFrom entrypoint graph = recursive mempty (S.singleton entrypoint)
  where recursive seen current
          | null current = seen
          | otherwise    = recursive (S.union seen current) (next \\ seen)
          where next = S.unions
                 . S.fromList -- for some reason set is not filterable?
                 . mapMaybe (`M.lookup` graph)
                 . S.toList
                 $ current

unreachableFrom :: Ord a => a -> Graph a -> Set a
unreachableFrom entrypoint graph =
  nodes graph \\ reachableFrom entrypoint graph

graphToDot :: Graph FilePath -> Dot ()
graphToDot graph = do
  nodes <- traverseWithKey
    (\name edges -> D.node [("label",name)] <&> (,edges))
    graph

  forM_ nodes $ \(node, edges) ->
    forM_ edges $ \key ->
      case M.lookup key nodes of
        Just (other,_) -> node .->. other
        _              -> pure ()