module Stackctl.Sort
  ( sortByDependencies
  ) where

import Stackctl.Prelude

import Data.Graph (graphFromEdges, topSort)

sortByDependencies
  :: Ord k
  => (a -> k)
  -- ^ How to identify a given item
  -> (a -> [k])
  -- ^ How to get the given item's dependencies
  -> [a]
  -> [a]
sortByDependencies :: forall k a. Ord k => (a -> k) -> (a -> [k]) -> [a] -> [a]
sortByDependencies a -> k
toName a -> [k]
toDepends [a]
specs =
  forall a b. (a -> b) -> [a] -> [b]
map Vertex -> a
nodeFromVertex forall a b. (a -> b) -> a -> b
$ forall a. [a] -> [a]
reverse forall a b. (a -> b) -> a -> b
$ Graph -> [Vertex]
topSort Graph
graph
 where
  (Graph
graph, Vertex -> (a, k, [k])
tripleFromVertex, k -> Maybe Vertex
_) = forall key node.
Ord key =>
[(node, key, [key])]
-> (Graph, Vertex -> (node, key, [key]), key -> Maybe Vertex)
graphFromEdges forall a b. (a -> b) -> a -> b
$ forall a b. (a -> b) -> [a] -> [b]
map a -> (a, k, [k])
tripleFromNode [a]
specs

  nodeFromVertex :: Vertex -> a
nodeFromVertex = forall {a} {b} {c}. (a, b, c) -> a
nodeFromTriple forall b c a. (b -> c) -> (a -> b) -> a -> c
. Vertex -> (a, k, [k])
tripleFromVertex

  tripleFromNode :: a -> (a, k, [k])
tripleFromNode a
n = (a
n, a -> k
toName a
n, a -> [k]
toDepends a
n)

  nodeFromTriple :: (a, b, c) -> a
nodeFromTriple (a
n, b
_, c
_) = a
n