úÎyÑvñ(      !"#$%&'Safe Æ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.3You can also use a regular Haskell list. Implement append% using list prepend and remember to ($ the list returned by the algorithm.QSpecification of the order in which a node's outgoing edges should be traversed.™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 ) instance you are using. Reverse of .Ó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. *) means the first edge is visited first. +* means the second edge is visited first. ,H means it doesn't matter and the implementation can choose arbitrarily. ¹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. @A graph node container to be used with Kanh's topsort algorithm. €Take a graph node and a container, insert the node into it and return the resulting container. insert :: LNode a -> s a -> s a «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 -(. extract :: s a -> Maybe (LNode a, s a) Find the label for a .c, assuming you know the node exists in the graph. If the node isn't found, an exception is thrown.1Flexible 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.7Kahn's algorithm has room for variations in two places: hWhen traversing a node's outgoing edges, the order in which this traversal happens isn't specified. 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. Ahttps://en.wikipedia.org/wiki/Topological_sort#Kahn.27s_algorithm­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. Adds an additioal constraint to <: When traversing a node's outgoing edges, do so using the /% instance of the labels of the edges. 0Graph whose nodes to sort5The set of graph nodes which don't have inbound edges6In which order to go over the outgoing edges of a node3Topologically sorted list. For each edge from node u to node v, u appears before vƒ in this list. If the graph is empty or the initial node set is empty, an empty list is returned. If the graph contains a cycle, - is returned.      0NonexA git object identifier. This is a SHA-1 hash. Its common textual representation is a 40-byte ASCII hexadecimal string.FFor a given ref name - HEAD or branch or tag - determine its ref hash.FFor a given ref name - HEAD or branch or tag - determine its ref hash.lList the available references in a git repo, sorted by ref name. The list includes HEAD, branches and tags.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 a inside monad m.ÿMThis 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.Like |, but takes a list of refs and goes over all their ancestors. This is just a convenience shortcut which folds a list with ?. Passing a list with a single element is the same as running . Open git repository context7Given a child commit, one of its parent commits and an a value, generate an updated a‚ value. The second returned value determines whether traversal should proceed to the parent of the parent commit. If you return -6, it won't. If you load the parent commit (e.g. with 1 ) and return 2, it, traversal will proceed to its parents. Initial value8Hash of the commit whose ancestor graph should be loaded•If you already read the commit for the ref passed as the previous parameter, pass the commit here to avoid repeated loading of it. Otherwise, pass -# and it will be read from the repo.Open git repository context7Given a child commit, one of its parent commits and an a value, generate an updated a‚ value. The second returned value determines whether traversal should proceed to the parent of the parent commit. If you return -6, it won't. If you load the parent commit (e.g. with 1 ) and return 2, it, traversal will proceed to its parents. Initial value7Commits whose ancestors to scan. For each commit, pass: Hash of the commitzIf you already loaded the commit from the ref, pass the commit here to avoid repeated loading of it. Otherwise, pass -( and it will be read from the repo.None Ï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 3 field.The 4& wrapper reverses the comparison (the /m instance), so that merged-from branches are inserted earlier into the sorted list than merged-to branches.2Each node in the commit graph represents a commit. ¤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."ÿ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.#TReturn a subgraph containing only commits whose depth is up to the depth specified.$Given a depth threshold D=, the commits in the graph can be partitioned into 3 groups: Commits at depth DY or below, whose parents (if any) are all present in the graph and as well at depth D or belowCommits at depth D7 which have parents, and the parents are at depth D+1 or missing from the graphCommits at depth D+1 or above)In this library, these groups are called healthy, shallow and excluded respectively.%1Determine whether a given commit is healthy (see $).&1Determine whether a given commit is shallow (see $).'2Determine whether a given commit is excluded (see $). !"567#$%&'  !"#$%&'  !"#$%&' !"567#$%&'8      !"#$%&'()*+,-./012013014*56-.7089:;<=*5>;?@*ABCDEF#hit-graph-0.1-7bEZ1ZlIQIRhcnxJLDMX0"Data.Graph.Inductive.Query.TopsortData.Git.Graph.UtilData.Git.Graph NodeStack ResultList emptyList appendItemTraversalOrderInOrder ReverseOrder SortedOrder CustomOrderNodeSet insertNode extractNode nodeLabel topsortKahn topsortUnmixtopsortUnmixOrder$fNodeSetNodeStackObjIdunObjIdresolveNameMaybe resolveNamelistReferences loadCommitsloadCommitsMulti$fHashableObjId $fEqObjIdDepth CommitGraph EdgeLabel NodeLabelloadCommitGraphloadCommitGraphPT commitDepths filterDepthpartitionDepth isHealthy isShallow isExcludedbaseGHC.Listreverse"fgl-5.5.3.0-KO9F4uETTjy3vgLQ22ev7IData.Graph.Inductive.GraphGraphghc-prim GHC.TypesLTGTEQGHC.BaseNothingNode GHC.ClassesOrd sortNodes hit-0.6.3-GhtnRyVhAZ5F3isVAaXVb0Data.Git.Repository getCommitJustData.Git.Types commitParentsData.OrdDown getDepth' getLabel' parentRefs