From 68a18c80332bace9064e202d13f01c880cc114ec Mon Sep 17 00:00:00 2001
From: Maxime Dénès
Date: Wed, 24 Jun 2020 18:20:13 +0200
Subject: Special commit to start benchmarking.

---
 dev/bench/sort-by-deps | 33 +++++++++++++++++++++++++++++++++
 1 file changed, 33 insertions(+)
 create mode 100644 dev/bench/sort-by-deps

(limited to 'dev/bench/sort-by-deps')

diff --git a/dev/bench/sort-by-deps b/dev/bench/sort-by-deps
new file mode 100644
index 0000000000..e1da4e0ed5
--- /dev/null
+++ b/dev/bench/sort-by-deps
@@ -0,0 +1,33 @@
+#!/usr/bin/env ocaml
+
+let get_pkg_name arg =
+  List.nth (String.split_on_char ':' arg) 0
+
+let get_pkg_deps arg =
+  String.split_on_char ',' (List.nth (String.split_on_char ':' arg) 1)
+
+let split_pkg arg = get_pkg_name arg, get_pkg_deps arg
+
+let depends_on arg1 arg2 =
+  let pkg1, deps1 = split_pkg arg1 in
+  let pkg2, deps2 = split_pkg arg2 in
+  pkg1 != pkg2 && List.mem pkg2 deps1
+
+let rec sort = function
+  | [], [] -> []
+  | [], deferred -> sort (List.rev deferred, [])
+  | arg :: rest, deferred ->
+    (* check if any remaining package reverse-depends on this one *)
+    if List.exists (fun other_arg -> depends_on arg other_arg) rest
+    then (* defer this package *)
+      sort (rest, arg :: deferred)
+    else (* emit this package, and then try again with any deferred packages *)
+      arg :: sort (List.rev deferred @ rest, [])
+
+let main () =
+  let args = Array.to_list Sys.argv in
+  let pkgs = List.tl args in
+  let sorted_pkgs = sort (pkgs, []) in
+  Printf.printf "%s\n%!" (String.concat " " (List.map get_pkg_name sorted_pkgs))
+
+let () = main ()
-- 
cgit v1.2.3