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.erl224
1 files changed, 79 insertions, 145 deletions
diff --git a/lib/dialyzer/src/dialyzer_callgraph.erl b/lib/dialyzer/src/dialyzer_callgraph.erl
index 9e53e171c0..b079cd3090 100644
--- a/lib/dialyzer/src/dialyzer_callgraph.erl
+++ b/lib/dialyzer/src/dialyzer_callgraph.erl
@@ -2,7 +2,7 @@
%%-----------------------------------------------------------------------
%% %CopyrightBegin%
%%
-%% Copyright Ericsson AB 2006-2014. All Rights Reserved.
+%% Copyright Ericsson AB 2006-2017. All Rights Reserved.
%%
%% Licensed under the Apache License, Version 2.0 (the "License");
%% you may not use this file except in compliance with the License.
@@ -96,28 +96,34 @@
%% whenever applicable.
%%-----------------------------------------------------------------------------
+%% Types with comment 'race' are due to dialyzer_races.erl.
-record(callgraph, {digraph = digraph:new() :: digraph:graph(),
- active_digraph :: active_digraph(),
- esc :: ets:tid(),
- letrec_map :: ets:tid(),
+ active_digraph :: active_digraph()
+ | 'undefined', % race
+ esc :: ets:tid()
+ | 'undefined', % race
+ letrec_map :: ets:tid()
+ | 'undefined', % race
name_map :: ets:tid(),
rev_name_map :: ets:tid(),
- rec_var_map :: ets:tid(),
- self_rec :: ets:tid(),
- calls :: ets:tid(),
+ rec_var_map :: ets:tid()
+ | 'undefined', % race
+ self_rec :: ets:tid()
+ | 'undefined', % race
+ calls :: ets:tid()
+ | 'undefined', % race
race_detection = false :: boolean(),
- race_data_server = new_race_data_server() :: pid()}).
-
--record(race_data_state, {race_code = dict:new() :: dict:dict(),
- public_tables = [] :: [label()],
- named_tables = [] :: [string()],
- beh_api_calls = [] :: [{mfa(), mfa()}]}).
+ race_data_server = dialyzer_race_data_server:new() :: pid()}).
%% Exported Types
--type callgraph() :: #callgraph{}.
+-opaque callgraph() :: #callgraph{}.
--type active_digraph() :: {'d', digraph:graph()} | {'e', ets:tid(), ets:tid()}.
+-type active_digraph() :: {'d', digraph:graph()}
+ | {'e',
+ Out :: ets:tid(),
+ In :: ets:tid(),
+ Map :: ets:tid()}.
%%----------------------------------------------------------------------
@@ -246,24 +252,30 @@ find_non_local_calls([], Set) ->
-spec get_depends_on(scc() | module(), callgraph()) -> [scc()].
-get_depends_on(SCC, #callgraph{active_digraph = {'e', Out, _In}}) ->
- case ets_lookup_dict(SCC, Out) of
- {ok, Value} -> Value;
- error -> []
- end;
+get_depends_on(SCC, #callgraph{active_digraph = {'e', Out, _In, Maps}}) ->
+ lookup_scc(SCC, Out, Maps);
get_depends_on(SCC, #callgraph{active_digraph = {'d', DG}}) ->
digraph:out_neighbours(DG, SCC).
-spec get_required_by(scc() | module(), callgraph()) -> [scc()].
-get_required_by(SCC, #callgraph{active_digraph = {'e', _Out, In}}) ->
- case ets_lookup_dict(SCC, In) of
- {ok, Value} -> Value;
- error -> []
- end;
+get_required_by(SCC, #callgraph{active_digraph = {'e', _Out, In, Maps}}) ->
+ lookup_scc(SCC, In, Maps);
get_required_by(SCC, #callgraph{active_digraph = {'d', DG}}) ->
digraph:in_neighbours(DG, SCC).
+lookup_scc(SCC, Table, Maps) ->
+ case ets_lookup_dict({'scc', SCC}, Maps) of
+ {ok, SCCInt} ->
+ case ets_lookup_dict(SCCInt, Table) of
+ {ok, Ints} ->
+ [ets:lookup_element(Maps, Int, 2) || Int <- Ints];
+ error ->
+ []
+ end;
+ error -> []
+ end.
+
%%----------------------------------------------------------------------
%% Handling of modules & SCCs
%%----------------------------------------------------------------------
@@ -580,9 +592,10 @@ digraph_delete(DG) ->
active_digraph_delete({'d', DG}) ->
digraph:delete(DG);
-active_digraph_delete({'e', Out, In}) ->
+active_digraph_delete({'e', Out, In, Maps}) ->
ets:delete(Out),
- ets:delete(In).
+ ets:delete(In),
+ ets:delete(Maps).
digraph_edges(DG) ->
digraph:edges(DG).
@@ -609,45 +622,30 @@ digraph_reaching_subgraph(Funs, DG) ->
renew_race_info(#callgraph{race_data_server = RaceDataServer} = CG,
RaceCode, PublicTables, NamedTables) ->
- ok = race_data_server_cast(
+ ok = dialyzer_race_data_server:cast(
{renew_race_info, {RaceCode, PublicTables, NamedTables}},
RaceDataServer),
CG.
-renew_race_info({RaceCode, PublicTables, NamedTables},
- #race_data_state{} = State) ->
- State#race_data_state{race_code = RaceCode,
- public_tables = PublicTables,
- named_tables = NamedTables}.
-
-spec renew_race_code(dialyzer_races:races(), callgraph()) -> callgraph().
renew_race_code(Races, #callgraph{race_data_server = RaceDataServer} = CG) ->
Fun = dialyzer_races:get_curr_fun(Races),
FunArgs = dialyzer_races:get_curr_fun_args(Races),
Code = lists:reverse(dialyzer_races:get_race_list(Races)),
- ok = race_data_server_cast(
+ ok = dialyzer_race_data_server:cast(
{renew_race_code, {Fun, FunArgs, Code}},
RaceDataServer),
CG.
-renew_race_code_handler({Fun, FunArgs, Code},
- #race_data_state{race_code = RaceCode} = State) ->
- State#race_data_state{race_code = dict:store(Fun, [FunArgs, Code], RaceCode)}.
-
-spec renew_race_public_tables(label(), callgraph()) -> callgraph().
renew_race_public_tables(VarLabel,
#callgraph{race_data_server = RaceDataServer} = CG) ->
ok =
- race_data_server_cast({renew_race_public_tables, VarLabel}, RaceDataServer),
+ dialyzer_race_data_server:cast({renew_race_public_tables, VarLabel}, RaceDataServer),
CG.
-renew_race_public_tables_handler(VarLabel,
- #race_data_state{public_tables = PT}
- = State) ->
- State#race_data_state{public_tables = ordsets:add_element(VarLabel, PT)}.
-
-spec cleanup(callgraph()) -> callgraph().
cleanup(#callgraph{digraph = Digraph,
@@ -657,18 +655,18 @@ cleanup(#callgraph{digraph = Digraph,
#callgraph{digraph = Digraph,
name_map = NameMap,
rev_name_map = RevNameMap,
- race_data_server = race_data_server_call(dup, RaceDataServer)}.
+ race_data_server = dialyzer_race_data_server:duplicate(RaceDataServer)}.
-spec duplicate(callgraph()) -> callgraph().
duplicate(#callgraph{race_data_server = RaceDataServer} = Callgraph) ->
Callgraph#callgraph{
- race_data_server = race_data_server_call(dup, RaceDataServer)}.
+ race_data_server = dialyzer_race_data_server:duplicate(RaceDataServer)}.
-spec dispose_race_server(callgraph()) -> ok.
dispose_race_server(#callgraph{race_data_server = RaceDataServer}) ->
- race_data_server_cast(stop, RaceDataServer).
+ dialyzer_race_data_server:stop(RaceDataServer).
-spec get_digraph(callgraph()) -> digraph:graph().
@@ -678,17 +676,17 @@ get_digraph(#callgraph{digraph = Digraph}) ->
-spec get_named_tables(callgraph()) -> [string()].
get_named_tables(#callgraph{race_data_server = RaceDataServer}) ->
- race_data_server_call(get_named_tables, RaceDataServer).
+ dialyzer_race_data_server:call(get_named_tables, RaceDataServer).
-spec get_public_tables(callgraph()) -> [label()].
get_public_tables(#callgraph{race_data_server = RaceDataServer}) ->
- race_data_server_call(get_public_tables, RaceDataServer).
+ dialyzer_race_data_server:call(get_public_tables, RaceDataServer).
-spec get_race_code(callgraph()) -> dict:dict().
get_race_code(#callgraph{race_data_server = RaceDataServer}) ->
- race_data_server_call(get_race_code, RaceDataServer).
+ dialyzer_race_data_server:call(get_race_code, RaceDataServer).
-spec get_race_detection(callgraph()) -> boolean().
@@ -698,12 +696,12 @@ get_race_detection(#callgraph{race_detection = RD}) ->
-spec get_behaviour_api_calls(callgraph()) -> [{mfa(), mfa()}].
get_behaviour_api_calls(#callgraph{race_data_server = RaceDataServer}) ->
- race_data_server_call(get_behaviour_api_calls, RaceDataServer).
+ dialyzer_race_data_server:call(get_behaviour_api_calls, RaceDataServer).
-spec race_code_new(callgraph()) -> callgraph().
race_code_new(#callgraph{race_data_server = RaceDataServer} = CG) ->
- ok = race_data_server_cast(race_code_new, RaceDataServer),
+ ok = dialyzer_race_data_server:cast(race_code_new, RaceDataServer),
CG.
-spec put_digraph(digraph:graph(), callgraph()) -> callgraph().
@@ -714,7 +712,7 @@ put_digraph(Digraph, Callgraph) ->
-spec put_race_code(dict:dict(), callgraph()) -> callgraph().
put_race_code(RaceCode, #callgraph{race_data_server = RaceDataServer} = CG) ->
- ok = race_data_server_cast({put_race_code, RaceCode}, RaceDataServer),
+ ok = dialyzer_race_data_server:cast({put_race_code, RaceCode}, RaceDataServer),
CG.
-spec put_race_detection(boolean(), callgraph()) -> callgraph().
@@ -726,78 +724,23 @@ put_race_detection(RaceDetection, Callgraph) ->
put_named_tables(NamedTables,
#callgraph{race_data_server = RaceDataServer} = CG) ->
- ok = race_data_server_cast({put_named_tables, NamedTables}, RaceDataServer),
+ ok = dialyzer_race_data_server:cast({put_named_tables, NamedTables}, RaceDataServer),
CG.
-spec put_public_tables([label()], callgraph()) -> callgraph().
put_public_tables(PublicTables,
#callgraph{race_data_server = RaceDataServer} = CG) ->
- ok = race_data_server_cast({put_public_tables, PublicTables}, RaceDataServer),
+ ok = dialyzer_race_data_server:cast({put_public_tables, PublicTables}, RaceDataServer),
CG.
-spec put_behaviour_api_calls([{mfa(), mfa()}], callgraph()) -> callgraph().
put_behaviour_api_calls(Calls,
#callgraph{race_data_server = RaceDataServer} = CG) ->
- ok = race_data_server_cast({put_behaviour_api_calls, Calls}, RaceDataServer),
+ ok = dialyzer_race_data_server:cast({put_behaviour_api_calls, Calls}, RaceDataServer),
CG.
-
-new_race_data_server() ->
- spawn_link(fun() -> race_data_server_loop(#race_data_state{}) end).
-
-race_data_server_loop(State) ->
- receive
- {call, From, Ref, Query} ->
- Reply = race_data_server_handle_call(Query, State),
- From ! {Ref, Reply},
- race_data_server_loop(State);
- {cast, stop} ->
- ok;
- {cast, Message} ->
- NewState = race_data_server_handle_cast(Message, State),
- race_data_server_loop(NewState)
- end.
-
-race_data_server_call(Query, Server) ->
- Ref = make_ref(),
- Server ! {call, self(), Ref, Query},
- receive
- {Ref, Reply} -> Reply
- end.
-
-race_data_server_cast(Message, Server) ->
- Server ! {cast, Message},
- ok.
-
-race_data_server_handle_cast(race_code_new, State) ->
- State#race_data_state{race_code = dict:new()};
-race_data_server_handle_cast({Tag, Data}, State) ->
- case Tag of
- renew_race_info -> renew_race_info(Data, State);
- renew_race_code -> renew_race_code_handler(Data, State);
- renew_race_public_tables -> renew_race_public_tables_handler(Data, State);
- put_race_code -> State#race_data_state{race_code = Data};
- put_public_tables -> State#race_data_state{public_tables = Data};
- put_named_tables -> State#race_data_state{named_tables = Data};
- put_behaviour_api_calls -> State#race_data_state{beh_api_calls = Data}
- end.
-
-race_data_server_handle_call(Query,
- #race_data_state{race_code = RaceCode,
- public_tables = PublicTables,
- named_tables = NamedTables,
- beh_api_calls = BehApiCalls}
- = State) ->
- case Query of
- dup -> spawn_link(fun() -> race_data_server_loop(State) end);
- get_race_code -> RaceCode;
- get_public_tables -> PublicTables;
- get_named_tables -> NamedTables;
- get_behaviour_api_calls -> BehApiCalls
- end.
-
%%=============================================================================
%% Utilities for 'dot'
%%=============================================================================
@@ -826,37 +769,28 @@ to_ps(#callgraph{} = CG, File, Args) ->
ok.
condensation(G) ->
- SCs = digraph_utils:strong_components(G),
- V2I = ets:new(condensation_v2i, []),
- I2C = ets:new(condensation_i2c, []),
- I2I = ets:new(condensation_i2i, [bag]),
- CFun =
- fun(SC, N) ->
- lists:foreach(fun(V) -> true = ets:insert(V2I, {V,N}) end, SC),
- true = ets:insert(I2C, {N, SC}),
- N + 1
- end,
- lists:foldl(CFun, 1, SCs),
- Fun1 =
- fun({V1, V2}) ->
- I1 = ets:lookup_element(V2I, V1, 2),
- I2 = ets:lookup_element(V2I, V2, 2),
- I1 =:= I2 orelse ets:insert(I2I, {I1, I2})
- end,
- lists:foreach(Fun1, digraph:edges(G)),
- Fun3 =
- fun({I1, I2}, {Out, In}) ->
- SC1 = ets:lookup_element(I2C, I1, 2),
- SC2 = ets:lookup_element(I2C, I2, 2),
- {dict:append(SC1, SC2, Out), dict:append(SC2, SC1, In)}
- end,
- {OutDict, InDict} = ets:foldl(Fun3, {dict:new(), dict:new()}, I2I),
- [OutETS, InETS] =
+ SCCs = digraph_utils:strong_components(G),
+ %% Assign unique numbers to SCCs:
+ Ints = lists:seq(1, length(SCCs)),
+ IntToSCC = lists:zip(Ints, SCCs),
+ IntScc = sofs:relation(IntToSCC, [{int, scc}]),
+ %% Subsitute strong components for vertices in edges using the
+ %% unique numbers:
+ C2V = sofs:relation([{SC, V} || SC <- SCCs, V <- SC], [{scc, v}]),
+ I2V = sofs:relative_product(IntScc, C2V), % [{v, int}]
+ Es = sofs:relation(digraph:edges(G), [{v, v}]),
+ R1 = sofs:relative_product(I2V, Es),
+ R2 = sofs:relative_product(I2V, sofs:converse(R1)),
+ %% Create in- and out-neighbours:
+ In = sofs:relation_to_family(sofs:strict_relation(R2)),
+ R3 = sofs:converse(R2),
+ Out = sofs:relation_to_family(sofs:strict_relation(R3)),
+ [OutETS, InETS, MapsETS] =
[ets:new(Name,[{read_concurrency, true}]) ||
- Name <- [callgraph_deps_out, callgraph_deps_in]],
- ets:insert(OutETS, dict:to_list(OutDict)),
- ets:insert(InETS, dict:to_list(InDict)),
- ets:delete(V2I),
- ets:delete(I2C),
- ets:delete(I2I),
- {{'e', OutETS, InETS}, SCs}.
+ Name <- [callgraph_deps_out, callgraph_deps_in, callgraph_scc_map]],
+ ets:insert(OutETS, sofs:to_external(Out)),
+ ets:insert(InETS, sofs:to_external(In)),
+ %% Create mappings from SCCs to unique integers, and the inverse:
+ ets:insert(MapsETS, lists:zip([{'scc', SCC} || SCC<- SCCs], Ints)),
+ ets:insert(MapsETS, IntToSCC),
+ {{'e', OutETS, InETS, MapsETS}, SCCs}.
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-21 14:45:04 +0000