aboutsummaryrefslogtreecommitdiffstats
path: root/lib/dialyzer/src/dialyzer_callgraph.erl
diff options
context:
space:
mode:
Diffstat (limited to 'lib/dialyzer/src/dialyzer_callgraph.erl')
-rw-r--r--lib/dialyzer/src/dialyzer_callgraph.erl140
1 files changed, 99 insertions, 41 deletions
diff --git a/lib/dialyzer/src/dialyzer_callgraph.erl b/lib/dialyzer/src/dialyzer_callgraph.erl
index 2a01b0f753..1cbb83a44a 100644
--- a/lib/dialyzer/src/dialyzer_callgraph.erl
+++ b/lib/dialyzer/src/dialyzer_callgraph.erl
@@ -43,12 +43,14 @@
%% module_postorder/1,
module_postorder_from_funs/2,
new/0,
+ mini_callgraph/1,
+ get_depends_on/2,
+ get_required_by/2,
in_neighbours/2,
renew_race_info/4,
reset_from_funs/2,
scan_core_tree/2,
strip_module_deps/2,
- take_scc/1,
remove_external/1,
to_dot/2,
to_ps/3]).
@@ -65,7 +67,6 @@
%%----------------------------------------------------------------------
--type mfa_or_funlbl() :: label() | mfa().
-type scc() :: [mfa_or_funlbl()].
-type mfa_calls() :: [{mfa_or_funlbl(), mfa_or_funlbl()}].
@@ -78,9 +79,6 @@
%% digraph - A digraph representing the callgraph.
%% Nodes are represented as MFAs or labels.
%% esc - A set of all escaping functions as reported by dialyzer_dep.
-%% postorder - A list of strongly connected components of the callgraph
-%% sorted in a topological bottom-up order.
-%% This is produced by calling finalize/1.
%% name_map - A mapping from label to MFA.
%% rev_name_map - A reverse mapping of the name_map.
%% rec_var_map - A dict mapping from letrec bound labels to function names.
@@ -91,13 +89,13 @@
%%-----------------------------------------------------------------------------
-record(callgraph, {digraph = digraph:new() :: digraph(),
- esc = sets:new() :: set(),
- name_map = dict:new() :: dict(),
- rev_name_map = dict:new() :: dict(),
- postorder = [] :: [scc()],
- rec_var_map = dict:new() :: dict(),
- self_rec = sets:new() :: set(),
- calls = dict:new() :: dict(),
+ active_digraph :: digraph(),
+ esc = sets:new() :: set() | ets:tid(),
+ name_map = dict:new() :: dict() | ets:tid(),
+ rev_name_map = dict:new() :: dict() | ets:tid(),
+ rec_var_map = dict:new() :: dict() | ets:tid(),
+ self_rec = sets:new() :: set() | ets:tid(),
+ calls = dict:new() :: dict() | ets:tid(),
race_code = dict:new() :: dict(),
public_tables = [] :: [label()],
named_tables = [] :: [string()],
@@ -115,6 +113,25 @@
new() ->
#callgraph{}.
+-spec mini_callgraph(callgraph()) -> callgraph().
+
+mini_callgraph(#callgraph{digraph = Digraph,
+ active_digraph = ActiveDigraph,
+ esc = Esc,
+ name_map = NameMap,
+ rev_name_map = RevNameMap,
+ rec_var_map = RecVarMap,
+ self_rec = SelfRecs,
+ calls = Calls}) ->
+ #callgraph{digraph = Digraph,
+ active_digraph = ActiveDigraph,
+ esc = Esc,
+ name_map = NameMap,
+ rev_name_map = RevNameMap,
+ rec_var_map = RecVarMap,
+ self_rec = SelfRecs,
+ calls = Calls}.
+
-spec delete(callgraph()) -> 'true'.
delete(#callgraph{digraph = Digraph}) ->
@@ -129,32 +146,32 @@ all_nodes(#callgraph{digraph = DG}) ->
lookup_rec_var(Label, #callgraph{rec_var_map = RecVarMap})
when is_integer(Label) ->
- dict:find(Label, RecVarMap).
+ ets_lookup_dict(Label, RecVarMap).
-spec lookup_call_site(label(), callgraph()) -> 'error' | {'ok', [_]}. % XXX: refine
lookup_call_site(Label, #callgraph{calls = Calls})
when is_integer(Label) ->
- dict:find(Label, Calls).
+ ets_lookup_dict(Label, Calls).
-spec lookup_name(label(), callgraph()) -> 'error' | {'ok', mfa()}.
lookup_name(Label, #callgraph{name_map = NameMap})
when is_integer(Label) ->
- dict:find(Label, NameMap).
+ ets_lookup_dict(Label, NameMap).
-spec lookup_label(mfa_or_funlbl(), callgraph()) -> 'error' | {'ok', integer()}.
lookup_label({_,_,_} = MFA, #callgraph{rev_name_map = RevNameMap}) ->
- dict:find(MFA, RevNameMap);
+ ets_lookup_dict(MFA, RevNameMap);
lookup_label(Label, #callgraph{}) when is_integer(Label) ->
{ok, Label}.
-spec in_neighbours(mfa_or_funlbl(), callgraph()) -> 'none' | [mfa_or_funlbl(),...].
-in_neighbours(Label, #callgraph{digraph = Digraph, name_map = NameMap})
+in_neighbours(Label, #callgraph{digraph = Digraph} = CG)
when is_integer(Label) ->
- Name = case dict:find(Label, NameMap) of
+ Name = case lookup_name(Label, CG) of
{ok, Val} -> Val;
error -> Label
end,
@@ -165,12 +182,12 @@ in_neighbours({_, _, _} = MFA, #callgraph{digraph = Digraph}) ->
-spec is_self_rec(mfa_or_funlbl(), callgraph()) -> boolean().
is_self_rec(MfaOrLabel, #callgraph{self_rec = SelfRecs}) ->
- sets:is_element(MfaOrLabel, SelfRecs).
+ ets_lookup_set(MfaOrLabel, SelfRecs).
-spec is_escaping(label(), callgraph()) -> boolean().
is_escaping(Label, #callgraph{esc = Esc}) when is_integer(Label) ->
- sets:is_element(Label, Esc).
+ ets_lookup_set(Label, Esc).
-type callgraph_edge() :: {mfa_or_funlbl(),mfa_or_funlbl()}.
-spec add_edges([callgraph_edge()], callgraph()) -> callgraph().
@@ -186,13 +203,6 @@ add_edges(Edges, MFAs, #callgraph{digraph = DG} = CG) ->
DG = digraph_confirm_vertices(MFAs, DG),
add_edges(Edges, CG).
--spec take_scc(callgraph()) -> 'none' | {'ok', scc(), callgraph()}.
-
-take_scc(#callgraph{postorder = [SCC|SCCs]} = CG) ->
- {ok, SCC, CG#callgraph{postorder = SCCs}};
-take_scc(#callgraph{postorder = []}) ->
- none.
-
-spec remove_external(callgraph()) -> {callgraph(), [tuple()]}.
remove_external(#callgraph{digraph = DG} = CG) ->
@@ -229,6 +239,16 @@ renew_race_info(CG, RaceCode, PublicTables, NamedTables) ->
public_tables = PublicTables,
named_tables = NamedTables}.
+-spec get_depends_on(scc(), callgraph()) -> [scc()].
+
+get_depends_on(SCC, #callgraph{active_digraph = DG}) ->
+ digraph:out_neighbours(DG, SCC).
+
+-spec get_required_by(scc(), callgraph()) -> [scc()].
+
+get_required_by(SCC, #callgraph{active_digraph = DG}) ->
+ digraph:in_neighbours(DG, SCC).
+
%%----------------------------------------------------------------------
%% Handling of modules & SCCs
%%----------------------------------------------------------------------
@@ -282,18 +302,44 @@ create_module_digraph([{_, _}|Left], MDG) ->
create_module_digraph([], MDG) ->
MDG.
--spec finalize(callgraph()) -> callgraph().
-
-finalize(#callgraph{digraph = DG} = CG) ->
- CG#callgraph{postorder = digraph_finalize(DG)}.
-
--spec reset_from_funs([mfa_or_funlbl()], callgraph()) -> callgraph().
-
-reset_from_funs(Funs, #callgraph{digraph = DG} = CG) ->
+-spec finalize(callgraph()) -> {[scc()], callgraph()}.
+
+finalize(#callgraph{digraph = DG,
+ esc = Esc,
+ name_map = NameMap,
+ rev_name_map = RevNameMap,
+ rec_var_map = RecVarMap,
+ self_rec = SelfRec,
+ calls = Calls
+ } = CG) ->
+ [ETSEsc, ETSNameMap, ETSRevNameMap, ETSRecVarMap, ETSSelfRec, ETSCalls] =
+ [ets:new(N,[public]) ||
+ N <- [callgraph_esc, callgraph_name_map, callgraph_rev_name_map,
+ callgraph_rec_var_map, callgraph_self_rec, callgraph_calls]],
+ [true,true] = [ets:insert(ETS, [{E} || E <- sets:to_list(Data)]) ||
+ {ETS, Data} <- [{ETSEsc, Esc}, {ETSSelfRec, SelfRec}]],
+ [true, true, true, true] =
+ [ets:insert(ETS, dict:to_list(Data)) ||
+ {ETS, Data} <- [{ETSNameMap, NameMap}, {ETSRevNameMap, RevNameMap},
+ {ETSRecVarMap, RecVarMap}, {ETSCalls, Calls}]],
+ {ActiveDG, Postorder} = digraph_finalize(DG),
+ {Postorder, CG#callgraph{active_digraph = ActiveDG,
+ esc = ETSEsc,
+ name_map = ETSNameMap,
+ rev_name_map = ETSRevNameMap,
+ rec_var_map = ETSRecVarMap,
+ self_rec = ETSSelfRec,
+ calls = ETSCalls}}.
+
+-spec reset_from_funs([mfa_or_funlbl()], callgraph()) -> {[scc()], callgraph()}.
+
+reset_from_funs(Funs, #callgraph{digraph = DG,
+ active_digraph = OldActiveDG} = CG) ->
+ digraph_delete(OldActiveDG),
SubGraph = digraph_reaching_subgraph(Funs, DG),
- Postorder = digraph_finalize(SubGraph),
+ {NewActiveDG, Postorder} = digraph_finalize(SubGraph),
digraph_delete(SubGraph),
- CG#callgraph{postorder = Postorder}.
+ {Postorder, CG#callgraph{active_digraph = NewActiveDG}}.
-spec module_postorder_from_funs([mfa_or_funlbl()], callgraph()) -> [module()].
@@ -302,7 +348,20 @@ module_postorder_from_funs(Funs, #callgraph{digraph = DG} = CG) ->
PO = module_postorder(CG#callgraph{digraph = SubGraph}),
digraph_delete(SubGraph),
PO.
-
+
+ets_lookup_dict(Key, Table) ->
+ try ets:lookup_element(Table, Key, 2) of
+ Val -> {ok, Val}
+ catch
+ _:_ -> error
+ end.
+
+ets_lookup_set(Key, Table) ->
+ case ets:lookup(Table, Key) of
+ [] -> false;
+ _ -> true
+ end.
+
%%----------------------------------------------------------------------
%% Core code
%%----------------------------------------------------------------------
@@ -516,13 +575,12 @@ digraph_in_neighbours(V, DG) ->
end.
digraph_postorder(Digraph) ->
- digraph_utils:postorder(Digraph).
+ digraph_utils:topsort(Digraph).
digraph_finalize(DG) ->
DG1 = digraph_utils:condensation(DG),
Postorder = digraph_postorder(DG1),
- digraph:delete(DG1),
- Postorder.
+ {DG1, Postorder}.
digraph_reaching_subgraph(Funs, DG) ->
Vertices = digraph_utils:reaching(Funs, DG),