-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Use graph algorithms to access and manipulate Git repos
--   
--   This library contains utilities for loading Git repo data into a
--   graph, and using graph algorithms to extract useful information, and
--   perhaps even modify the repo in interesting ways.
@package hit-graph
@version 0.1

module Data.Graph.Inductive.Query.Topsort

-- | Find the label for a <a>Node</a>, assuming you know the node exists in
--   the graph. If the node isn't found, an exception is thrown.
nodeLabel :: Graph g => g a b -> Node -> a

-- | A graph node container to be used with Kanh's topsort algorithm.
class NodeSet s

-- | Take a graph node and a container, insert the node into it and return
--   the resulting container. insert :: LNode a -&gt; s a -&gt; s a
insertNode :: NodeSet s => Node -> s -> s

-- | Remove a node from the container. Return the removed node and the
--   resulting container after removal. If the container is empty (i.e.
--   there is no node to remove), return <a>Nothing</a>. extract :: s a
--   -&gt; Maybe (LNode a, s a)
extractNode :: NodeSet s => s -> Maybe (Node, s)

-- | Specification of the order in which a node's outgoing edges should be
--   traversed.
data TraversalOrder b

-- | The order in which they're listed by FGL functions. The FGL
--   documentation doesn't seem to specify the order, which means it may
--   depend entirely on the <a>Graph</a> instance you are using.
InOrder :: TraversalOrder b

-- | Reverse of <a>InOrder</a>.
ReverseOrder :: TraversalOrder b

-- | Sort the outgoing edge list before traversal, using the given ordering
--   function. It takes two pairs, each pair having a labeled node and the
--   label of the edge, and determines the order they should be visited.
--   <a>LT</a> means the first edge is visited first. <a>GT</a> means the
--   second edge is visited first. <a>EQ</a> means it doesn't matter and
--   the implementation can choose arbitrarily.
SortedOrder :: ((Node, b) -> (Node, b) -> Ordering) -> TraversalOrder b

-- | Lets you reorder the edge list in an arbitrary way before it gets
--   traversed. Note that it's up to you to make sure the list you return
--   really contains all the items of the input list.
CustomOrder :: ([(Node, b)] -> [(Node, b)]) -> TraversalOrder b

-- | A container for storing the result of the sorting. Kahn's algorithm
--   begins with an empty structure and then appends nodes to produce the
--   result. Therefore almost any sequence container could work.
--   
--   You can also use a regular Haskell list. Implement <tt>append</tt>
--   using list prepend and remember to <a>reverse</a> the list returned by
--   the algorithm.
class ResultList l
emptyList :: ResultList l => l a
appendItem :: ResultList l => a -> l a -> l a

-- | Flexible topological sort using Kahn's algorithm.
--   
--   It seems that Haskell graph libraries (and perhaps graph libraries in
--   general) tend to implement topological sort using depth-first search
--   (DFS). While it's probably easier (since these libraries also
--   implement DFS), the result is that you pass a graph to a function and
--   get back the sorted list. There is no room left for specifying
--   variable parts of the algorithm, which means you can't control which
--   topsort order (out of potentially many orders possible) you get.
--   Sometimes you don't care, but sometimes you do.
--   
--   Kahn's algorithm has room for variations in two places:
--   
--   <ol>
--   <li>When traversing a node's outgoing edges, the order in which this
--   traversal happens isn't specified.</li>
--   <li>The internals of structure S, the set of nodes with no inbound
--   edges, aren't specified. Therefore, so is the order in which nodes are
--   removed from it.</li>
--   </ol>
--   
--   
--   <a>https://en.wikipedia.org/wiki/Topological_sort#Kahn.27s_algorithm</a>
topsortKahn :: (DynGraph g, NodeSet s, ResultList l) => g a b -> s -> TraversalOrder b -> Maybe (l Node)
newtype NodeStack
NodeStack :: [Node] -> NodeStack

-- | Topologically sort commits so that parallel lines of work, e.g. a
--   master branch and a short topic branch merged into it, don't get their
--   commits mixed in the sorted order.
topsortUnmix :: (DynGraph g, ResultList l) => g a b -> NodeStack -> TraversalOrder b -> Maybe (l Node)

-- | Adds an additioal constraint to <a>topsortUnmix</a>: When traversing a
--   node's outgoing edges, do so using the <a>Ord</a> instance of the
--   labels of the edges.
topsortUnmixOrder :: (Ord b, DynGraph g, ResultList l) => g a b -> NodeStack -> Maybe (l Node)
instance Data.Graph.Inductive.Query.Topsort.NodeSet Data.Graph.Inductive.Query.Topsort.NodeStack

module Data.Git.Graph.Util

-- | A git object identifier. This is a SHA-1 hash. Its common textual
--   representation is a 40-byte ASCII hexadecimal string.
newtype ObjId
ObjId :: Ref -> ObjId
[unObjId] :: ObjId -> Ref

-- | For a given ref name - HEAD or branch or tag - determine its ref hash.
resolveNameMaybe :: Git -> String -> IO (Maybe ObjId)

-- | For a given ref name - HEAD or branch or tag - determine its ref hash.
resolveName :: Git -> String -> IO ObjId

-- | List the available references in a git repo, sorted by ref name. The
--   list includes HEAD, branches and tags.
listReferences :: Git -> IO [(ObjId, String)]

-- | Load the entire graph of commits which are ancestors of the given ref
--   (and that ref itself). Fold the commit structure into a value of type
--   <tt>a</tt> inside monad <tt>m</tt>.
--   
--   This is a low-level function which operates on a commit tree, i.e. the
--   same ref may be visited more than once (if it has more than one child
--   commit). You can use the provided flexibility to implement graph
--   algorithms over the commits, or build a graph using some graph library
--   and use that library's tools for further processing.
loadCommits :: MonadIO m => Git -> ((ObjId, Commit) -> ObjId -> a -> m (a, Maybe Commit)) -> a -> ObjId -> Maybe Commit -> m a

-- | Like <a>loadCommits</a>, but takes a list of refs and goes over all
--   their ancestors. This is just a convenience shortcut which folds a
--   list with <a>loadCommits</a>. Passing a list with a single element is
--   the same as running <a>loadCommits</a>.
loadCommitsMulti :: MonadIO m => Git -> ((ObjId, Commit) -> ObjId -> a -> m (a, Maybe Commit)) -> a -> [(ObjId, Maybe Commit)] -> m a
instance GHC.Classes.Eq Data.Git.Graph.Util.ObjId
instance Data.Hashable.Class.Hashable Data.Git.Graph.Util.ObjId

module Data.Git.Graph

-- | Each node in the commit graph represents a commit.
type NodeLabel = (ObjId, Commit)

-- | Edges are tagged by numbers defining the order of parents of a commit.
--   For each commit, the out-edges pointing to its parents are numbered
--   according to the order in which the parents were specified in the
--   <a>commitParents</a> field.
--   
--   The <a>Down</a> wrapper reverses the comparison (the <a>Ord</a>
--   instance), so that merged-from branches are inserted earlier into the
--   sorted list than merged-to branches.
type EdgeLabel = Down Int
type CommitGraph g = g NodeLabel EdgeLabel

-- | Build a directed acyclic graph of commits. The commits in the graph
--   are the ones specified, and all their ancestors. The edges point from
--   a commit to its parents.
loadCommitGraph :: Graph g => Git -> [ObjId] -> IO (CommitGraph g)
loadCommitGraphPT :: Git -> [ObjId] -> IO (CommitGraph Gr)
type Depth = Int

-- | Determine the depths of all the commits in the graph. Orphan commits
--   (i.e. which don't have parents are assigned depth 1, and any other
--   commit gets a higher depth. A commit's depth depends on the length of
--   the shortest path between that commit and any of the orphan commits.
commitDepths :: Graph g => CommitGraph g -> [(Node, Depth)]

-- | Return a subgraph containing only commits whose depth is up to the
--   depth specified.
filterDepth :: DynGraph g => Depth -> CommitGraph g -> CommitGraph g

-- | Given a depth threshold <i>D</i>, the commits in the graph can be
--   partitioned into 3 groups:
--   
--   <ol>
--   <li>Commits at depth <i>D</i> or below, whose parents (if any) are all
--   present in the graph and as well at depth <i>D</i> or below</li>
--   <li>Commits at depth <i>D</i> which have parents, and the parents are
--   at depth <i>D+1</i> or missing from the graph</li>
--   <li>Commits at depth <i>D+1</i> or above</li>
--   </ol>
--   
--   In this library, these groups are called <i>healthy</i>,
--   <i>shallow</i> and <i>excluded</i> respectively.
partitionDepth :: Graph g => CommitGraph g -> HashMap Node Depth -> Depth -> ([LNode NodeLabel], [LNode NodeLabel], [LNode NodeLabel])

-- | Determine whether a given commit is healthy (see
--   <a>partitionDepth</a>).
isHealthy :: Graph g => CommitGraph g -> HashMap Node Depth -> Depth -> Node -> Bool

-- | Determine whether a given commit is shallow (see
--   <a>partitionDepth</a>).
isShallow :: Graph g => CommitGraph g -> HashMap Node Depth -> Depth -> Node -> Bool

-- | Determine whether a given commit is excluded (see
--   <a>partitionDepth</a>).
isExcluded :: Graph g => CommitGraph g -> HashMap Node Depth -> Depth -> Node -> Bool