1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
|
(**************************************************************************)
(* *)
(* Copyright (C) 2012 Johannes 'josch' Schauer <j.schauer@email.de> *)
(* Copyright (C) 2012 Pietro Abate <pietro.abate@pps.jussieu.fr> *)
(* *)
(* This library is free software: you can redistribute it and/or modify *)
(* it under the terms of the GNU Lesser General Public License as *)
(* published by the Free Software Foundation, either version 3 of the *)
(* License, or (at your option) any later version. A special linking *)
(* exception to the GNU Lesser General Public License applies to this *)
(* library, see the COPYING file for more information. *)
(**************************************************************************)
open! ExtLib
open Dose_common
module StringSet = BootstrapCommon.StringSet
module Make (U : sig val univ : Cudf.universe end) = struct
module G = BuildGraph.G
module FindCyclesG = GraphUtils.FindCycles(G)
module BGE = BuildGraphExtras.Make(struct let univ = U.univ end)
let edges_in_most_cycles g cycles =
let hist = FindCyclesG.get_cycles_per_edge_ht g cycles in
let builddep_edges = List.filter (fun (k,_) -> match k with
| (_,{BuildGraph.depend = BuildGraph.BuildDep},_) -> true
| (_,{BuildGraph.depend = BuildGraph.BuildsFrom _},_) -> false
) (Hashtbl.fold (fun k v acc -> (k,v)::acc) hist []) in
let cmp (v1, c1) (v2, c2) =
let c = compare c2 c1 in
if c <> 0 then c
else match v1,v2 with
| (sv1,{BuildGraph.depend = BuildGraph.BuildDep},iv1),(sv2,{BuildGraph.depend = BuildGraph.BuildDep},iv2) ->
let srcpkgcmp = compare (BuildGraph.Unique.uid sv1) (BuildGraph.Unique.uid sv2) in
if srcpkgcmp <> 0 then srcpkgcmp
else
compare (BuildGraph.Unique.uid iv1) (BuildGraph.Unique.uid iv2)
| _ -> failwith "impossible"
in
List.sort ~cmp builddep_edges
let min_builddep g =
let src_vertices = G.fold_vertex (fun v acc ->
let vertex = BuildGraph.Unique.value v in
match vertex with
| BuildGraph.SrcPkg id ->
let p = CudfAdd.inttopkg U.univ id in
(p, BGE.pkglist_of_vlist (G.succ g v))::acc
| _ -> acc
) g [] in
List.sort ~cmp:(fun (p1,a) (p2,b) ->
let num_comp = compare (List.length a) (List.length b) in
match num_comp with
| 0 -> CudfAdd.compare p1 p2
| n -> n
) src_vertices
let get_src_bin_stats g =
G.fold_vertex (fun v acc ->
let succ = List.length (G.succ g v) in
let pred = List.length (G.pred g v) in
(v, succ, pred)::acc
) g []
let ratio_source g =
let src_vertices = G.fold_vertex (fun v acc ->
let vertex = BuildGraph.Unique.value v in
match vertex with
| BuildGraph.SrcPkg id ->
let p = CudfAdd.inttopkg U.univ id in
let num_builddeps = List.length (G.succ g v) in
let neededby = G.pred g v in
let builddepof = List.fold_left (fun acc s -> (G.pred g s)@acc) [] neededby in
(p, num_builddeps, BGE.pkglist_of_vlist neededby, (BootstrapCommon.CudfSet.elements (CudfAdd.to_set (BGE.pkglist_of_vlist builddepof))))::acc
| _ -> acc
) g [] in
List.sort ~cmp:(fun (p1,a1,_,a2) (p2,b1,_,b2) ->
let num_comp = compare ((float_of_int b1)/.(float_of_int (List.length b2))) ((float_of_int a1)/.(float_of_int (List.length a2))) in
match num_comp with
| 0 -> CudfAdd.compare p1 p2
| n -> n
) src_vertices
let ratio_binary g =
let bin_vertices = G.fold_vertex (fun v acc ->
let vertex = BuildGraph.Unique.value v in
match vertex with
| BuildGraph.InstSet (id,_) ->
let p = CudfAdd.inttopkg U.univ id in
let num_srcpkgs = List.length (G.succ g v) in
let builddepof = G.pred g v in
(p, num_srcpkgs, BGE.pkglist_of_vlist builddepof)::acc
| _ -> acc
) g [] in
List.sort ~cmp:(fun (p1,a1,a2) (p2,b1,b2) ->
let num_comp = compare ((float_of_int b1)/.(float_of_int (List.length b2))) ((float_of_int a1)/.(float_of_int (List.length a2))) in
match num_comp with
| 0 -> CudfAdd.compare p1 p2
| n -> n
) bin_vertices
let only_weak_missing weak_deps_set g =
let only_weak = G.fold_vertex (fun v acc ->
let vertex = BuildGraph.Unique.value v in
match vertex with
| BuildGraph.SrcPkg id ->
let p = CudfAdd.inttopkg U.univ id in
let bd = G.fold_succ (fun v2 acc ->
let vertex2 = BuildGraph.Unique.value v2 in
match vertex2 with
| BuildGraph.InstSet (id,_) -> (CudfAdd.inttopkg U.univ id)::acc
| _ -> failwith "impossible"
) g v [] in
let bds = List.fold_left (fun acc p ->
StringSet.add (p.Cudf.package) acc
) StringSet.empty bd in
if StringSet.subset bds weak_deps_set then
(p,bd)::acc
else
acc
| _ -> acc
) g [] in
List.sort ~cmp:(fun (s1,l1) (s2,l2) ->
let num_comp = compare (List.length l2) (List.length l1) in
match num_comp with
| 0 -> CudfAdd.compare s1 s2
| n -> n
) only_weak
end
|
