Replace Digraph's Node type synonym with a data type

This refactoring makes it more obvious when we are constructing
a Node for the digraph rather than a less useful 3-tuple.

Reviewers: austin, goldfire, bgamari, simonmar, dfeuer

Reviewed By: dfeuer

Subscribers: rwbarton, thomie

Differential Revision: https://phabricator.haskell.org/D3414

1 files changed, 16 insertions, 14 deletions

diff --git a/compiler/utils/Digraph.hs b/compiler/utils/Digraph.hs
index 48e39f761f..fe325e6a06 100644
--- a/compiler/utils/Digraph.hs
+++ b/compiler/utils/Digraph.hs
@@ -1,11 +1,11 @@
 -- (c) The University of Glasgow 2006
 
-{-# LANGUAGE CPP, ScopedTypeVariables #-}
+{-# LANGUAGE CPP, ScopedTypeVariables, ViewPatterns #-}
 
 module Digraph(
         Graph, graphFromEdgedVerticesOrd, graphFromEdgedVerticesUniq,
 
-        SCC(..), Node, flattenSCC, flattenSCCs,
+        SCC(..), Node(..), flattenSCC, flattenSCCs,
         stronglyConnCompG,
         topologicalSortG, dfsTopSortG,
         verticesG, edgesG, hasVertexG,
@@ -89,7 +89,10 @@ data Graph node = Graph {
 
 data Edge node = Edge node node
 
-type Node key payload = (payload, key, [key])
+data Node key payload = DigraphNode {
+      node_payload :: payload,
+      node_key :: key,
+      node_dependencies :: [key] }
      -- The payload is user data, just carried around in this module
      -- The keys are ordered
      -- The [key] are the dependencies of the node;
@@ -109,11 +112,11 @@ graphFromEdgedVertices
 graphFromEdgedVertices _reduceFn []            = emptyGraph
 graphFromEdgedVertices reduceFn edged_vertices =
   Graph graph vertex_fn (key_vertex . key_extractor)
-  where key_extractor (_, k, _) = k
+  where key_extractor = node_key
         (bounds, vertex_fn, key_vertex, numbered_nodes) =
           reduceFn edged_vertices key_extractor
         graph = array bounds [ (v, sort $ mapMaybe key_vertex ks)
-                             | (v, (_, _, ks)) <- numbered_nodes]
+                             | (v, (node_dependencies -> ks)) <- numbered_nodes]
                 -- We normalize outgoing edges by sorting on node order, so
                 -- that the result doesn't depend on the order of the edges
 
@@ -212,14 +215,15 @@ findCycle graph
   = go Set.empty (new_work root_deps []) []
   where
     env :: Map.Map key (Node key payload)
-    env = Map.fromList [ (key, node) | node@(_, key, _) <- graph ]
+    env = Map.fromList [ (node_key node, node) | node <- graph ]
 
     -- Find the node with fewest dependencies among the SCC modules
     -- This is just a heuristic to find some plausible root module
     root :: Node key payload
-    root = fst (minWith snd [ (node, count (`Map.member` env) deps)
-                            | node@(_,_,deps) <- graph ])
-    (root_payload,root_key,root_deps) = root
+    root = fst (minWith snd [ (node, count (`Map.member` env)
+                                           (node_dependencies node))
+                            | node <- graph ])
+    DigraphNode root_payload root_key root_deps = root
 
 
     -- 'go' implements Dijkstra's algorithm, more or less
@@ -232,7 +236,7 @@ findCycle graph
 
     go _       [] [] = Nothing  -- No cycles
     go visited [] qs = go visited qs []
-    go visited (((payload,key,deps), path) : ps) qs
+    go visited (((DigraphNode payload key deps), path) : ps) qs
        | key == root_key           = Just (root_payload : reverse path)
        | key `Set.member` visited  = go visited ps qs
        | key `Map.notMember` env   = go visited ps qs
@@ -294,8 +298,7 @@ stronglyConnCompFromEdgedVerticesOrd
         => [Node key payload]
         -> [SCC payload]
 stronglyConnCompFromEdgedVerticesOrd
-  = map (fmap get_node) . stronglyConnCompFromEdgedVerticesOrdR
-  where get_node (n, _, _) = n
+  = map (fmap node_payload) . stronglyConnCompFromEdgedVerticesOrdR
 
 -- The following two versions are provided for backwards compatibility:
 -- See Note [Deterministic SCC]
@@ -305,8 +308,7 @@ stronglyConnCompFromEdgedVerticesUniq
         => [Node key payload]
         -> [SCC payload]
 stronglyConnCompFromEdgedVerticesUniq
-  = map (fmap get_node) . stronglyConnCompFromEdgedVerticesUniqR
-  where get_node (n, _, _) = n
+  = map (fmap node_payload) . stronglyConnCompFromEdgedVerticesUniqR
 
 -- The "R" interface is used when you expect to apply SCC to
 -- (some of) the result of SCC, so you dont want to lose the dependency info