1 files changed, 97 insertions, 0 deletions
diff --git a/stdlib/source/library/lux/tool/compiler/meta/cache/dependency.lux b/stdlib/source/library/lux/tool/compiler/meta/cache/dependency.lux
new file mode 100644
index 000000000..3ba514b5f
--- /dev/null
+++ b/stdlib/source/library/lux/tool/compiler/meta/cache/dependency.lux
@@ -0,0 +1,97 @@
+(.module:
+  [library
+   [lux (#- Module)
+    [abstract
+     ["." monad (#+ do)]]
+    [control
+     ["." try (#+ Try)]
+     ["." state]
+     ["." function
+      ["." memo (#+ Memo)]]]
+    [data
+     ["." maybe ("#\." functor)]
+     ["." text
+      ["%" format (#+ format)]]
+     [collection
+      ["." list ("#\." functor fold)]
+      ["." dictionary (#+ Dictionary)]
+      ["." set (#+ Set)]]]]]
+  [///
+   ["." archive (#+ Output Archive)
+    [key (#+ Key)]
+    ["." descriptor (#+ Module Descriptor)]
+    ["." document (#+ Document)]]])
+
+(type: Ancestry
+  (Set Module))
+
+(def: fresh
+  Ancestry
+  (set.new text.hash))
+
+(type: #export Graph
+  (Dictionary Module Ancestry))
+
+(def: empty
+  Graph
+  (dictionary.new text.hash))
+
+(def: #export modules
+  (-> Graph (List Module))
+  dictionary.keys)
+
+(type: Dependency
+  {#module Module
+   #imports Ancestry})
+
+(def: #export graph
+  (-> (List Dependency) Graph)
+  (list\fold (function (_ [module imports] graph)
+               (dictionary.put module imports graph))
+             ..empty))
+
+(def: (ancestry archive)
+  (-> Archive Graph)
+  (let [memo (: (Memo Module Ancestry)
+                (function (_ recur module)
+                  (do {! state.monad}
+                    [#let [parents (case (archive.find module archive)
+                                     (#try.Success [descriptor document])
+                                     (get@ #descriptor.references descriptor)
+                                     
+                                     (#try.Failure error)
+                                     ..fresh)]
+                     ancestors (monad.map ! recur (set.to_list parents))]
+                    (wrap (list\fold set.union parents ancestors)))))
+        ancestry (memo.open memo)]
+    (list\fold (function (_ module memory)
+                 (if (dictionary.key? memory module)
+                   memory
+                   (let [[memory _] (ancestry [memory module])]
+                     memory)))
+               ..empty
+               (archive.archived archive))))
+
+(def: (dependency? ancestry target source)
+  (-> Graph Module Module Bit)
+  (let [target_ancestry (|> ancestry
+                            (dictionary.get target)
+                            (maybe.default ..fresh))]
+    (set.member? target_ancestry source)))
+
+(type: #export Order
+  (List [Module [archive.ID [Descriptor (Document .Module) Output]]]))
+
+(def: #export (load_order key archive)
+  (-> (Key .Module) Archive (Try Order))
+  (let [ancestry (..ancestry archive)]
+    (|> ancestry
+        dictionary.keys
+        (list.sort (..dependency? ancestry))
+        (monad.map try.monad
+                   (function (_ module)
+                     (do try.monad
+                       [module_id (archive.id module archive)
+                        [descriptor document output] (archive.find module archive)
+                        document (document.check key document)]
+                       (wrap [module [module_id [descriptor document output]]])))))))