lots of portability changes (#1405)

[ghc-hetmet.git] / compiler / utils / Digraph.lhs

diff --git a/compiler/utils/Digraph.lhs b/compiler/utils/Digraph.lhs
index 958769c..939dc49 100644 (file)
--- a/compiler/utils/Digraph.lhs
+++ b/compiler/utils/Digraph.lhs
@@ -3,6 +3,13 @@
 %
 
 \begin{code}
+{-# OPTIONS -w #-}
+-- The above warning supression flag is a temporary kludge.
+-- While working on this module you are encouraged to remove it and fix
+-- any warnings in the module. See
+--     http://hackage.haskell.org/trac/ghc/wiki/Commentary/CodingStyle#Warnings
+-- for details
+
 module Digraph(
 
         -- At present the only one with a "nice" external interface
@@ -47,7 +54,7 @@ import Data.Maybe
 import Data.Array
 import Data.List
 
-#if __GLASGOW_HASKELL__ > 604
+#if !defined(__GLASGOW_HASKELL__) || __GLASGOW_HASKELL__ > 604
 import Data.Array.ST
 #else
 import Data.Array.ST  hiding ( indices, bounds )
@@ -76,6 +83,16 @@ instance Outputable a => Outputable (SCC a) where
    ppr (CyclicSCC vs) = text "REC" $$ (nest 3 (vcat (map ppr vs)))
 \end{code}
 
+Note [Nodes, keys, vertices]
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+ * A 'node' is a big blob of client-stuff
+
+ * Each 'node' has a unique (client) 'key', but the latter 
+       is in Ord and has fast comparison
+
+ * Digraph then maps each 'key' to a Vertex (Int) which is
+       arranged densely in 0.n
+
 \begin{code}
 stronglyConnComp
         :: Ord key
@@ -104,8 +121,8 @@ stronglyConnCompR [] = []  -- added to avoid creating empty array in graphFromEd
 stronglyConnCompR edges
   = map decode forest
   where
-    (graph, vertex_fn) = _scc_ "graphFromEdges" graphFromEdges edges
-    forest             = _scc_ "Digraph.scc" scc graph
+    (graph, vertex_fn) = {-# SCC "graphFromEdges" #-} graphFromEdges edges
+    forest             = {-# SCC "Digraph.scc" #-} scc graph
     decode (Node v []) | mentions_itself v = CyclicSCC [vertex_fn v]
                        | otherwise         = AcyclicSCC (vertex_fn v)
     decode other = CyclicSCC (dec other [])
@@ -323,17 +340,17 @@ preArr bnds      = tabulate bnds . preorderF
 ------------------------------------------------------------
 
 \begin{code}
---postorder :: Tree a -> [a]
-postorder (Node a ts) = postorderF ts ++ [a]
+postorder :: Tree a -> [a] -> [a]
+postorder (Node a ts) = postorderF ts . (a :)
 
-postorderF   :: Forest a -> [a]
-postorderF ts = concat (map postorder ts)
+postorderF   :: Forest a -> [a] -> [a]
+postorderF ts = foldr (.) id $ map postorder ts
 
-postOrd      :: Graph -> [Vertex]
-postOrd       = postorderF . dff
+postOrd :: Graph -> [Vertex]
+postOrd g = postorderF (dff g) []
 
-topSort      :: Graph -> [Vertex]
-topSort       = reverse . postOrd
+topSort :: Graph -> [Vertex]
+topSort = reverse . postOrd
 \end{code}