X-Git-Url: https://git.xandkar.net/?p=dups.git;a=blobdiff_plain;f=dups.ml;h=c627369c5de0c44d6b6d6cbb12921f9382d17276;hp=3cfbee31847b99958b9900a81c48bbf6db9b181f;hb=8c54ccb832581554a2c272c0f08b4300081d22b5;hpb=1253df349226345e7596e77e9b0120094f0f1a34

diff --git a/dups.ml b/dups.ml
index 3cfbee3..c627369 100644
--- a/dups.ml
+++ b/dups.ml
@@ -2,7 +2,7 @@ open Printf
 
 module Array = ArrayLabels
 module List  = ListLabels
-module StrSet= Set.Make(String)
+module StrSet = Set.Make(String)
 module Unix  = UnixLabels
 
 module Stream : sig
@@ -89,12 +89,17 @@ module File : sig
 
   val lookup : string Stream.t -> t Stream.t
   (** Lookup file info for given paths *)
+
+  module Set : sig include Set.S with type elt := t end
 end = struct
   type t =
     { path : string
     ; size : int
     }
 
+  let compare {path=p1; _} {path=p2; _} =
+    Stdlib.compare p1 p2
+
   let lookup paths =
     Stream.map paths ~f:(fun path ->
       let {Unix.st_size = size; _} = Unix.lstat path in
@@ -132,6 +137,12 @@ end = struct
           next ()
     in
     Stream.create next
+
+  module Set = Set.Make(struct
+    type elt = t
+    type t = elt
+    let compare = compare
+  end)
 end
 
 type input =
@@ -146,6 +157,7 @@ type opt =
   { input  : input
   ; output : output
   ; ignore : Str.regexp option
+  ; sample : int
   }
 
 type count =
@@ -153,6 +165,7 @@ type count =
   ; empty       : int ref
   ; ignored     : int ref
   ; unique_size : int ref
+  ; unique_sample : int ref
   ; hashed      : int ref
   }
 
@@ -182,21 +195,42 @@ let make_input_stream input ignore count =
 
 let make_output_fun = function
   | Stdout ->
-      fun digest n_paths paths ->
-        printf "%s %d\n%!" (Digest.to_hex digest) n_paths;
-        List.iter (StrSet.elements paths) ~f:(printf "    %S\n%!")
+      fun digest n_files files ->
+        printf "%s %d\n%!" (Digest.to_hex digest) n_files;
+        List.iter (File.Set.elements files) ~f:(fun {File.path; _} ->
+          printf "    %S\n%!" path
+        )
   | Directory dir ->
-      fun digest _ paths ->
+      fun digest _ files ->
         let digest = Digest.to_hex digest in
         let dir = Filename.concat dir (String.sub digest 0 2) in
         Unix.mkdir dir ~perm:0o700;
         let oc = open_out (Filename.concat dir digest) in
-        List.iter (StrSet.elements paths) ~f:(fun path ->
+        List.iter (File.Set.elements files) ~f:(fun {File.path; _} ->
           output_string oc (sprintf "%S\n%!" path)
         );
         close_out oc
 
-let main {input; output; ignore} =
+let sample path ~len =
+  let buf = Bytes.make len ' ' in
+  let ic = open_in_bin path in
+  let rec read pos len =
+    assert (len >= 0);
+    if len = 0 then
+      ()
+    else begin
+      let chunk_size = input ic buf pos len in
+      if chunk_size = 0 then (* EOF *)
+        ()
+      else
+        read (pos + chunk_size) (len - chunk_size)
+    end
+  in
+  read 0 len;
+  close_in ic;
+  Bytes.to_string buf
+
+let main {input; output; ignore; sample = sample_len} =
   let t0 = Sys.time () in
   let count =
     { considered  = ref 0
@@ -204,47 +238,79 @@ let main {input; output; ignore} =
     ; ignored     = ref 0
     ; unique_size = ref 0
     ; hashed      = ref 0
+    ; unique_sample     = ref 0
     }
   in
   let output = make_output_fun  output in
   let input  = make_input_stream input ignore count in
-  let paths_by_size = Hashtbl.create 1_000_000 in
-  let paths_by_digest = Hashtbl.create 1_000_000 in
-  let process tbl path ~f =
-    let key = f path in
-    let count, paths =
-      match Hashtbl.find_opt tbl key with
+  let files_by_size = Hashtbl.create 1_000_000 in
+  let files_by_sample = Hashtbl.create 1_000_000 in
+  let files_by_digest = Hashtbl.create 1_000_000 in
+  let process tbl ~group ~file =
+    let count, files =
+      match Hashtbl.find_opt tbl group with
       | None ->
-          (0, StrSet.empty)
-      | Some (n, paths) ->
-          (n, paths)
+          (0, File.Set.empty)
+      | Some (n, files) ->
+          (n, files)
     in
-    Hashtbl.replace tbl key (count + 1, StrSet.add path paths)
+    Hashtbl.replace tbl group (count + 1, File.Set.add file files)
   in
-  Stream.iter input ~f:(fun {File.path; size} ->
-    process paths_by_size path ~f:(fun _ -> size)
+  (* TODO: Make a nice(r) abstraction to re-assemble pieces in the pipeline:
+   *
+   * from input           to files_by_size
+   * from files_by_size   to files_by_sample
+   * from files_by_sample to files_by_digest
+   * from files_by_digest to output
+   *
+   * input |> files_by_size |> files_by_sample |> files_by_digest |> output
+   *)
+  Stream.iter input ~f:(fun ({File.size; _} as file) ->
+    process files_by_size ~group:size ~file
   );
   Hashtbl.iter
-    (fun _ (n, paths) ->
+    (fun _ (n, files) ->
       (* Skip files with unique sizes *)
       if n > 1 then
-        StrSet.iter
-          (fun path ->
-            incr count.hashed;
-            process paths_by_digest path ~f:Digest.file
+        File.Set.iter
+          (fun ({File.path; _} as file) ->
+            process
+              files_by_sample
+              ~group:(sample path ~len:sample_len)
+              ~file
           )
-          paths
+          files
       else
         incr count.unique_size;
     )
-    paths_by_size;
-  Hashtbl.iter (fun d (n, ps) -> if n > 1 then output d n ps) paths_by_digest;
+    files_by_size;
+  Hashtbl.iter
+    (fun _ (n, files) ->
+      (* Skip files with unique samples *)
+      if n > 1 then
+        File.Set.iter
+          (fun ({File.path; _} as file) ->
+            incr count.hashed;
+            process files_by_digest ~group:(Digest.file path) ~file
+          )
+          files
+      else
+        incr count.unique_sample;
+    )
+    files_by_sample;
+  Hashtbl.iter
+    (fun d (n, files) ->
+      if n > 1 then
+        output d n files
+    )
+    files_by_digest;
   let t1 = Sys.time () in
   eprintf "Time                       : %f seconds\n%!" (t1 -. t0);
   eprintf "Considered                 : %d\n%!" !(count.considered);
   eprintf "Hashed                     : %d\n%!" !(count.hashed);
   eprintf "Skipped due to 0      size : %d\n%!" !(count.empty);
   eprintf "Skipped due to unique size : %d\n%!" !(count.unique_size);
+  eprintf "Skipped due to unique sample : %d\n%!" !(count.unique_sample);
   eprintf "Ignored due to regex match : %d\n%!" !(count.ignored)
 
 let get_opt () : opt =
@@ -263,6 +329,7 @@ let get_opt () : opt =
   let input  = ref Stdin in
   let output = ref Stdout in
   let ignore = ref None in
+  let sample = ref 256 in
   let spec =
     [ ( "-out"
       , Arg.String (fun path ->
@@ -276,6 +343,10 @@ let get_opt () : opt =
       , Arg.String (fun regexp -> ignore := Some (Str.regexp regexp))
       , " Ignore file paths which match this regexp pattern (see Str module)."
       )
+    ; ( "-sample"
+      , Arg.Set_int sample
+      , (sprintf " Byte size of file samples to use. Default: %d" !sample)
+      )
     ]
   in
   Arg.parse
@@ -290,9 +361,14 @@ let get_opt () : opt =
           input := Directories (path :: paths)
     )
     "";
+  assert_
+    (fun x -> x > 0)
+    !sample
+    (sprintf "Sample size cannot be negative: %d" !sample);
   { input  = !input
   ; output = !output
   ; ignore = !ignore
+  ; sample = !sample
   }
 
 let () =