{
: sort_by_dependence
: gather_imports
}

Where

Define (sort_by_dependence packages)
    Do  (LIST.for_each packages
            Func p
                (LIST.for_each p.imports
                    Func path
                        When (STRING.equal path p.path)
                            (OS.die
                                (STRING.concat
                                    [Right "Package " & path &
                                        " imports itself." & 'nil]))
                        End))
    Let ordered_paths
        Let components
            Let MAP (SEARCH.MAP STRING.compare [Func {key _} key])
            In
            Let G (GRAPH.G MAP)
            Let g (MAP.new (LIST.map packages [Func p {p.path p.imports}]))
            In
            (G.strongly_connected_components g)
        In
        (LIST.map components
            Func c
                Match c
                | 'cons.{path paths}
                    Match paths
                    | 'nil path
                    | 'cons._
                        (OS.die "There is a cycle in the package dependence graph.")
                    ;
                ;)
    In
    (LIST.map ordered_paths
        Func path
            Define (has_matching_path package)
                (STRING.equal package.path path)
            In
            Match (LIST.filter packages has_matching_path)
            | 'cons.{package _} package
            ;)

Define (gather_imports expr)
    Let SET (SEARCH.SET STRING.compare)
    In
    Let f
        Let empty Func set set
        In
        Unfold exprs From [expr & 'nil]
            Match exprs
            | 'nil empty
            | 'cons.{expr exprs}
                Let g (Fold exprs)
                Let f
                    Match expr
                    | 'true empty
                    | 'false empty
                    | 'num._ empty
                    | 'str._ empty
                    | 'package.path [Func set (SET.insert set path)]
                    | 'prim._ empty
                    | 'var._ empty
                    | 'chain.{expr _} (Fold [expr & 'nil])
                    | 'tuple.exprs (Fold exprs)
                    | 'record.{_ inits} (Fold inits)
                    | 'block.{binders expr}
                        (Fold
                            (LIST.cons expr
                                (LIST.map binders
                                    Func binder
                                        Match binder
                                        | 'let.{_ expr} expr
                                        | 'do.expr expr
                                        ;)))
                    | 'app.{func args} (Fold [func & args])
                    | 'func.{_ expr} (Fold [expr & 'nil])
                    | 'iterate.{_ inits expr} (Fold [expr & inits])
                    | 'continue.exprs (Fold exprs)
                    | 'unfold.{_ inits expr} (Fold [expr & inits])
                    | 'fold.exprs (Fold exprs)
                    | 'cond.clauses
                        (Fold
                            (LIST.concat_map clauses
                                Func {test body}
                                    [Right test & body & 'nil]))
                    | 'if.{test then else}
                        (Fold [Right test & then & else & 'nil])
                    | 'and.{test then}
                        (Fold [Right test & then & 'nil])
                    | 'or.{test else}
                        (Fold [Right test & else & 'nil])
                    | 'labeled.{_ expr} (Fold [expr & 'nil])
                    | 'match.{expr clauses}
                        (Fold [expr & (LIST.map clauses [Func {_ body} body])])
                    ;
                In
                [f >> g]
            ;
    In
    (SET.list (f SET.empty))

Where

Let GRAPH Package "graph"
Let LIST Package "list"
Let OS Package "os"
Let SEARCH Package "search"
Let STRING Package "string"