/usr/lib/hugs/packages/fgl/Data/Graph/Inductive/Query/Dominators.hs is in libhugs-fgl-bundled 98.200609.21-5.3.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
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 | module Data.Graph.Inductive.Query.Dominators(
dom
) where
import Data.List
import Data.Graph.Inductive.Graph
type DomSets = [(Node,[Node],[Node])]
intersection :: [[Node]] -> [Node]
intersection cs = foldr intersect (head cs) cs
getdomv :: [Node] -> DomSets -> [[Node]]
getdomv vs ds = [z|(w,_,z)<-ds,v<-vs,v==w]
builddoms :: DomSets -> [Node] -> DomSets
builddoms ds [] = ds
builddoms ds (v:vs) = builddoms ((fs++[(n,p,sort(n:idv))])++(tail rs)) vs
where idv = intersection (getdomv p ds)
(n,p,_) = head rs
(fs,rs) = span (\(x,_,_)->x/=v) ds
domr :: DomSets -> [Node] -> DomSets
domr ds vs|xs == ds = ds
|otherwise = builddoms xs vs
where xs = (builddoms ds vs)
{-|
Finds the dominators relationship for a given graph and an initial
node. For each node v, it returns the list of dominators of v.
-}
dom :: Graph gr => gr a b -> Node -> [(Node,[Node])]
dom g u = map (\(x,_,z)->(x,z)) (domr ld n')
where ld = (u,[],[u]):map (\v->(v,pre g v,n)) (n')
n' = n\\[u]
n = nodes g
|