Base.SCC

At various places in the compiler we had to partition a list of declarations into strongly connected components. The function scc computes this relation in two steps. First, the list is topologically sorted downwards using the defs relation. Then the resulting list is sorted upwards using the uses relation and partitioned into the connected components. Both relations are computed within this module using the bound and free names of each declaration.

In order to avoid useless recomputations, the code in the module first decorates the declarations with their bound and free names and a unique number. The latter is only used to provide a trivial ordering so that the declarations can be used as set elements.

Documentation

scc

Arguments

:: Eq b

=> (a -> [b])

entities defined by node

-> (a -> [b])

entities used by node

-> [a]

list of nodes

-> [[a]]

strongly connected components

Computation of strongly connected components