{
: 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 empty [Func {set} set]
    Define (reduce rec exprs)
        Func {set}
            (LIST.reduce exprs set
                Func {set expr} For (f set) Let f (rec rec expr))
    In
    Define (rec rec expr)
        Match expr
        | 'true empty
        | 'false empty
        | 'num._ empty
        | 'str._ empty
        | 'package.path [Func {set} (SET.insert set path)]
        | 'prim._ empty
        | 'var._ empty
        | 'chain.{expr _} (rec rec expr)
        | 'tuple.exprs (reduce rec exprs)
        | 'record.{_ inits} (reduce rec inits)
        | 'block.{binders expr}
            (reduce rec
                (LIST.cons expr
                    (LIST.map binders
                        Func {binder}
                            Match binder
                            | 'let.{_ expr} expr
                            | 'do.expr expr
                            ;)))
        | 'app.{func args} (reduce rec [func & args])
        | 'func.{_ expr} (rec rec expr)
        | 'iterate.{_ inits expr} (reduce rec [expr & inits])
        | 'continue.exprs (reduce rec exprs)
        | 'cond.clauses
            (reduce rec
                (LIST.concat_map clauses
                    Func {{test body}}
                        [Right test & body & 'nil]))
        | 'if.{test then else}
            (reduce rec
                [Right test & then & else & 'nil])
        | 'and.{test then}
            (reduce rec [Right test & then & 'nil])
        | 'or.{test else}
            (reduce rec [Right test & else & 'nil])
        | 'list.exprs (reduce rec exprs)
        | 'labeled.{_ expr} (rec rec expr)
        | 'match.{expr clauses}
            (reduce rec [expr & (LIST.map clauses [Func {{_ body}} body])])
        ;
    In
    For (SET.list (f SET.empty))
        Let f (rec rec expr)

Where

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