From 1d1104ebe13c30bdab8e36af247bddbd169af6cd Mon Sep 17 00:00:00 2001
From: rjones <rjones>
Date: Wed, 25 Mar 2009 22:44:46 +0000
Subject: [PATCH] Switch to using a breadth-first traversal of the tree.

---
 rpmdepsize.ml | 53 +++++++++++++++++++++++++++++++++++++++++++++--------
 1 file changed, 45 insertions(+), 8 deletions(-)

diff --git a/rpmdepsize.ml b/rpmdepsize.ml
index 92ab20b..4bc2a42 100644
--- a/rpmdepsize.ml
+++ b/rpmdepsize.ml
@@ -16,6 +16,7 @@
  * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  *
  * Written by Richard W.M. Jones <rjones@redhat.com>
+ * Python script modified from a version by Seth Vidal.
  *)
 
 open Sexplib
@@ -121,6 +122,14 @@ let () =
        failwith (sprintf "command stopped with signal %d" i)
   );
 
+  if debug then (
+    List.iter (
+      fun pkg -> printf "%s -> [%s]\n" pkg.nevra (String.concat ", " pkg.deps)
+    ) pkgs;
+    printf "root package is %s\n" root;
+    printf "===\n%!"
+  );
+
   (* Create the dependency graph, probably contains loops so beware. *)
   let deps = List.map (fun pkg -> Deps (pkg, ref [])) pkgs in
   let depsmap =
@@ -133,6 +142,27 @@ let () =
       let deps' = List.map (fun n -> StringMap.find n depsmap) pkg.deps in
       deps := List.append !deps deps'
   ) deps;
+  let deps = () in ignore deps;
+
+  if debug then (
+    let seen = ref StringMap.empty in
+    let rec display ?(indent=0) = function
+      | Deps (pkg, deps) ->
+	  if StringMap.mem pkg.nevra !seen then
+	    printf "%s%s -> ...\n" (spaces indent) pkg.nevra
+	  else (
+	    printf "%s%s -> [%s]\n"
+	      (spaces indent) pkg.nevra (
+		String.concat ", "
+		  (List.map (fun (Deps (pkg, _)) -> pkg.nevra) !deps)
+	      );
+	    seen := StringMap.add pkg.nevra true !seen;
+	    List.iter (display ~indent:(indent+2)) !deps
+	  )
+    in
+    display (StringMap.find root depsmap);
+    printf "===\n%!"
+  );
 
   (* For each package, calculate the total installed size of the package,
    * which includes all subpackages pulled in.  So it's what would be
@@ -160,9 +190,12 @@ let () =
    * size of the additional packages.
    *)
   let tree =
-    let seen = ref StringMap.empty in
+    let seen = StringMap.empty in
+    let seen = StringMap.add root true seen in
+    let seen = ref seen in
+    let mark_seen (Deps (pkg, _))= seen := StringMap.add pkg.nevra true !seen in
+    let not_seen (Deps (pkg, _)) = not (StringMap.mem pkg.nevra !seen) in
     let rec build_tree = function
-      | Deps (pkg, _) when StringMap.mem pkg.nevra !seen -> None
       | Deps (pkg, { contents = children }) ->
 	  (* Sort children by reverse total size. *)
 	  let cmp (Deps (p1, _)) (Deps (p2, _)) =
@@ -171,8 +204,9 @@ let () =
 	    compare t2 t1
 	  in
 	  let children = List.sort ~cmp children in
-	  seen := StringMap.add pkg.nevra true !seen;
-	  let children = List.filter_map build_tree children in
+	  let children = List.filter not_seen children in
+	  List.iter mark_seen children;
+	  let children = List.map build_tree children in
 	  let total = StringMap.find pkg.nevra totalsmap in
 	  let increm =
 	    let rec sum_child_sizes = function
@@ -182,9 +216,9 @@ let () =
 		  ) pkg.size children
 	    in
 	    sum_child_sizes (Tree (pkg, 0L, 0L, `WHITE, children)) in
-	  Some (Tree (pkg, total, increm, `WHITE, children))
+	  Tree (pkg, total, increm, `WHITE, children)
     in
-    Option.get (build_tree (StringMap.find root depsmap)) in
+    build_tree (StringMap.find root depsmap) in
 
   if debug then (
     let rec display ?(indent=0) = function
@@ -193,7 +227,7 @@ let () =
 	    (spaces indent) pkg.nevra pkg.size increm total;
 	  List.iter (display ~indent:(indent+2)) children
     in
-    display tree
+    display tree;
   );
 
   (* Max depth of the tree. *)
@@ -314,7 +348,10 @@ let () =
       )
       else if width >= 4 then
 	draw_pkg_narrow x y width height colour
-      (* else nothing *)
+      (* else
+	 XXX This doesn't work.  We need to coalesce small packages
+	 in the tree.
+	draw_pkg_narrow x y 1 height colour *)
 
     and draw_pkg_outline x y width pkgsizewidth height colour =
       draw#set_foreground colour;
-- 
1.8.3.1