aboutsummaryrefslogtreecommitdiffstats
path: root/lib
diff options
context:
space:
mode:
authorStavros Aronis <[email protected]>2012-02-28 11:04:12 +0100
committerHenrik Nord <[email protected]>2012-05-21 15:31:21 +0200
commit9f30b73af775daeca99e8094b08ca4e5d9b6cd82 (patch)
treebe6c48979fc5c582c05008444e266fab82e4e128 /lib
parent9b0cf90622c3f84f2e3f463c2685d0257d249846 (diff)
downloadotp-9f30b73af775daeca99e8094b08ca4e5d9b6cd82.tar.gz
otp-9f30b73af775daeca99e8094b08ca4e5d9b6cd82.tar.bz2
otp-9f30b73af775daeca99e8094b08ca4e5d9b6cd82.zip
More efficient calculation of module deps and postorder
Diffstat (limited to 'lib')
-rw-r--r--lib/dialyzer/src/dialyzer_callgraph.erl45
1 files changed, 23 insertions, 22 deletions
diff --git a/lib/dialyzer/src/dialyzer_callgraph.erl b/lib/dialyzer/src/dialyzer_callgraph.erl
index 0384160abc..cc26d9fdd5 100644
--- a/lib/dialyzer/src/dialyzer_callgraph.erl
+++ b/lib/dialyzer/src/dialyzer_callgraph.erl
@@ -279,26 +279,36 @@ modules(#callgraph{digraph = DG}) ->
-spec module_postorder(callgraph()) -> {[module()], {'d', digraph()}}.
module_postorder(#callgraph{digraph = DG}) ->
- Edges = digraph_edges(DG),
- Nodes = ordsets:from_list([M || {M,_F,_A} <- digraph_vertices(DG)]),
+ Edges = lists:foldl(fun edge_fold/2, sets:new(), digraph_edges(DG)),
+ Nodes = sets:from_list([M || {M,_F,_A} <- digraph_vertices(DG)]),
MDG = digraph:new([acyclic]),
- MDG1 = digraph_confirm_vertices(Nodes, MDG),
- MDG2 = create_module_digraph(Edges, MDG1),
- PostOrder = digraph_utils:topsort(MDG2),
- {PostOrder, {'d', MDG2}}.
+ MDG = digraph_confirm_vertices(sets:to_list(Nodes), MDG),
+ Foreach = fun({M1,M2}) -> digraph:add_edge(MDG, M1, M2) end,
+ lists:foreach(Foreach, sets:to_list(Edges)),
+ PostOrder = digraph_utils:topsort(MDG),
+ {PostOrder, {'d', MDG}}.
+
+edge_fold({{M1,_,_},{M2,_,_}}, Set) ->
+ case M1 =/= M2 of
+ true -> sets:add_element({M1,M2},Set);
+ false -> Set
+ end;
+edge_fold(_, Set) -> Set.
+
%% The module deps of a module are modules that depend on the module
-spec module_deps(callgraph()) -> dict().
module_deps(#callgraph{digraph = DG}) ->
- Edges = digraph_edges(DG),
- Nodes = ordsets:from_list([M || {M,_F,_A} <- digraph_vertices(DG)]),
+ Edges = lists:foldl(fun edge_fold/2, sets:new(), digraph_edges(DG)),
+ Nodes = sets:from_list([M || {M,_F,_A} <- digraph_vertices(DG)]),
MDG = digraph:new(),
- MDG1 = digraph_confirm_vertices(Nodes, MDG),
- MDG2 = create_module_digraph(Edges, MDG1),
- Deps = [{N, ordsets:from_list(digraph:in_neighbours(MDG2, N))}
- || N <- Nodes],
- digraph_delete(MDG2),
+ MDG = digraph_confirm_vertices(sets:to_list(Nodes), MDG),
+ Foreach = fun({M1,M2}) -> digraph:add_edge(MDG, M1, M2) end,
+ lists:foreach(Foreach, sets:to_list(Edges)),
+ Deps = [{N, ordsets:from_list(digraph:in_neighbours(MDG, N))}
+ || N <- sets:to_list(Nodes)],
+ digraph_delete(MDG),
dict:from_list(Deps).
-spec strip_module_deps(dict(), set()) -> dict().
@@ -310,15 +320,6 @@ strip_module_deps(ModDeps, StripSet) ->
FilterFun2 = fun(_Key, ValSet) -> ValSet =/= [] end,
dict:filter(FilterFun2, ModDeps1).
-create_module_digraph([{{M, _, _}, {M, _, _}}|Left], MDG) ->
- create_module_digraph(Left, MDG);
-create_module_digraph([{{M1, _, _}, {M2, _, _}}|Left], MDG) ->
- create_module_digraph(Left, digraph_add_edge(M1, M2, MDG));
-create_module_digraph([{_, _}|Left], MDG) ->
- create_module_digraph(Left, MDG);
-create_module_digraph([], MDG) ->
- MDG.
-
-spec finalize(callgraph()) -> {[scc()], callgraph()}.
finalize(#callgraph{digraph = DG} = CG) ->