From 0bae6c82503b348e62f11edfbfc880145ef06794 Mon Sep 17 00:00:00 2001 From: Stavros Aronis Date: Tue, 21 Feb 2012 16:01:50 +0100 Subject: Avoid digraph_utils:condensation and ordering in typesig --- lib/dialyzer/src/dialyzer_callgraph.erl | 85 ++++++++++++++++++++++++------- lib/dialyzer/src/dialyzer_coordinator.erl | 15 ++++-- lib/dialyzer/src/dialyzer_worker.erl | 28 ++++++---- 3 files changed, 95 insertions(+), 33 deletions(-) (limited to 'lib/dialyzer') diff --git a/lib/dialyzer/src/dialyzer_callgraph.erl b/lib/dialyzer/src/dialyzer_callgraph.erl index bb96ada65f..0c3e8ca311 100644 --- a/lib/dialyzer/src/dialyzer_callgraph.erl +++ b/lib/dialyzer/src/dialyzer_callgraph.erl @@ -92,7 +92,7 @@ %%----------------------------------------------------------------------------- -record(callgraph, {digraph = digraph:new() :: digraph(), - active_digraph :: digraph(), + active_digraph :: active_digraph(), esc :: ets:tid(), name_map :: ets:tid(), rev_name_map :: ets:tid(), @@ -111,6 +111,8 @@ -type callgraph() :: #callgraph{}. +-type active_digraph() :: {'d', digraph()} | {'e', ets:tid(), ets:tid()}. + %%---------------------------------------------------------------------- -spec new() -> callgraph(). @@ -247,12 +249,22 @@ find_non_local_calls([], Set) -> -spec get_depends_on(scc(), callgraph()) -> [scc()]. -get_depends_on(SCC, #callgraph{active_digraph = DG}) -> +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 = {'d', DG}}) -> digraph:out_neighbours(DG, SCC). -spec get_required_by(scc(), callgraph()) -> [scc()]. -get_required_by(SCC, #callgraph{active_digraph = DG}) -> +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 = {'d', DG}}) -> digraph:in_neighbours(DG, SCC). %%---------------------------------------------------------------------- @@ -273,7 +285,7 @@ module_postorder(#callgraph{digraph = DG}) -> MDG1 = digraph_confirm_vertices(Nodes, MDG), MDG2 = create_module_digraph(Edges, MDG1), PostOrder = digraph_utils:topsort(MDG2), - {PostOrder, MDG2}. + {PostOrder, {'d', MDG2}}. %% The module deps of a module are modules that depend on the module -spec module_deps(callgraph()) -> dict(). @@ -310,23 +322,24 @@ create_module_digraph([], MDG) -> -spec finalize(callgraph()) -> {[scc()], callgraph()}. finalize(#callgraph{digraph = DG} = CG) -> - {ActiveDG, Postorder} = digraph_finalize(DG), + {ActiveDG, Postorder} = condensation(DG), {Postorder, CG#callgraph{active_digraph = ActiveDG}}. -spec reset_from_funs([mfa_or_funlbl()], callgraph()) -> {[scc()], callgraph()}. -reset_from_funs(Funs, #callgraph{digraph = DG, - active_digraph = OldActiveDG} = CG) -> - digraph_delete(OldActiveDG), +reset_from_funs(Funs, #callgraph{digraph = DG, active_digraph = ADG} = CG) -> + active_digraph_delete(ADG), SubGraph = digraph_reaching_subgraph(Funs, DG), - {NewActiveDG, Postorder} = digraph_finalize(SubGraph), + {NewActiveDG, Postorder} = condensation(SubGraph), digraph_delete(SubGraph), {Postorder, CG#callgraph{active_digraph = NewActiveDG}}. -spec module_postorder_from_funs([mfa_or_funlbl()], callgraph()) -> {[module()], callgraph()}. -module_postorder_from_funs(Funs, #callgraph{digraph = DG} = CG) -> +module_postorder_from_funs(Funs, #callgraph{digraph = DG, + active_digraph = ADG} = CG) -> + active_digraph_delete(ADG), SubGraph = digraph_reaching_subgraph(Funs, DG), {PO, Active} = module_postorder(CG#callgraph{digraph = SubGraph}), digraph_delete(SubGraph), @@ -544,6 +557,12 @@ remove_unconfirmed([], DG, Unconfirmed) -> digraph_delete(DG) -> digraph:delete(DG). +active_digraph_delete({'d', DG}) -> + digraph:delete(DG); +active_digraph_delete({'e', Out, In}) -> + ets:delete(Out), + ets:delete(In). + digraph_edges(DG) -> digraph:edges(DG). @@ -556,14 +575,6 @@ digraph_in_neighbours(V, DG) -> List -> List end. -digraph_postorder(Digraph) -> - digraph_utils:topsort(Digraph). - -digraph_finalize(DG) -> - DG1 = digraph_utils:condensation(DG), - Postorder = digraph_postorder(DG1), - {DG1, Postorder}. - digraph_reaching_subgraph(Funs, DG) -> Vertices = digraph_utils:reaching(Funs, DG), digraph_utils:subgraph(DG, Vertices). @@ -792,3 +803,41 @@ to_ps(#callgraph{} = CG, File, Args) -> Command = io_lib:format("dot -Tps ~s -o ~s ~s", [Args, File, Dot_File]), _ = os:cmd(Command), ok. + +condensation(G) -> + SCs = digraph_utils:strong_components(G), + V2I = ets:new(condensation, []), + I2C = ets:new(condensation, []), + I2I = ets:new(condensation, [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), + case I1 =:= I2 of + true -> true; + false -> ets:insert(I2I, {I1, I2}) + end + 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 = ets:new(out,[]), + InETS = ets:new(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}. diff --git a/lib/dialyzer/src/dialyzer_coordinator.erl b/lib/dialyzer/src/dialyzer_coordinator.erl index 437af69f5a..9d31c739d0 100644 --- a/lib/dialyzer/src/dialyzer_coordinator.erl +++ b/lib/dialyzer/src/dialyzer_coordinator.erl @@ -123,8 +123,8 @@ sccs_to_pids_request(SCCs, Coordinator) -> cast({sccs_to_pids, SCCs, self()}, Coordinator). scc_to_pids_request_handle(Worker, SCCs, SCCtoPID) -> - Pids = [fetch_map(SCC, SCCtoPID) || SCC <- SCCs], - Worker ! {sccs_to_pids, Pids}, + Result = map_lookup(SCCs, SCCtoPID), + Worker ! {sccs_to_pids, Result}, ok. -spec sccs_to_pids_reply() -> [dialyzer_worker:worker()]. @@ -314,5 +314,12 @@ new_map() -> store_map(Key, Value, Map) -> dict:store(Key, Value, Map). -fetch_map(Key, Map) -> - dict:fetch(Key, Map). +map_lookup(SCCs, Map) -> + Fold = + fun(Key, {Mapped, Unknown}) -> + case dict:find(Key, Map) of + {ok, Value} -> {[Value|Mapped], Unknown}; + error -> {Mapped, [Key|Unknown]} + end + end, + lists:foldl(Fold, {[], []}, SCCs). diff --git a/lib/dialyzer/src/dialyzer_worker.erl b/lib/dialyzer/src/dialyzer_worker.erl index 6608b78f0a..0efa5d9b01 100644 --- a/lib/dialyzer/src/dialyzer_worker.erl +++ b/lib/dialyzer/src/dialyzer_worker.erl @@ -88,9 +88,8 @@ loop(updating, State) -> loop(NextStatus, State); loop(initializing, #state{job = SCC, servers = Servers} = State) -> DependsOn = dialyzer_succ_typings:find_depends_on(SCC, Servers), - WithoutSelf = DependsOn -- [SCC], - ?debug("Deps ~p: ~p\n",[State#state.job, WithoutSelf]), - loop(updating, State#state{depends_on = WithoutSelf}); + ?debug("Deps ~p: ~p\n",[State#state.job, DependsOn]), + loop(updating, State#state{depends_on = DependsOn}); loop(waiting, State) -> ?debug("Wait: ~p\n",[State#state.job]), NewState = wait_for_success_typings(State), @@ -118,8 +117,7 @@ loop(running, #state{mode = Mode} = State) when ?debug("Run: ~p\n",[State#state.job]), ok = ask_coordinator_for_callers(State), NotFixpoint = do_work(State), - Callers = get_callers_reply_from_coordinator(), - ok = broadcast_done(State, Callers), + ok = broadcast_done(State), report_to_coordinator(NotFixpoint, State). waits_more_success_typings(#state{depends_on = Depends}) -> @@ -147,18 +145,26 @@ ask_coordinator_for_callers(#state{job = SCC, servers = Servers, coordinator = Coordinator}) -> RequiredBy = dialyzer_succ_typings:find_required_by(SCC, Servers), - WithoutSelf = RequiredBy -- [SCC], - ?debug("Waiting for me~p: ~p\n",[SCC, WithoutSelf]), - dialyzer_coordinator:sccs_to_pids_request(WithoutSelf, Coordinator). + ?debug("Waiting for me~p: ~p\n",[SCC, RequiredBy]), + dialyzer_coordinator:sccs_to_pids_request(RequiredBy, Coordinator). -get_callers_reply_from_coordinator() -> - dialyzer_coordinator:sccs_to_pids_reply(). +broadcast_done(#state{job = SCC, coordinator = Coordinator}) -> + {Callers, Unknown} = dialyzer_coordinator:sccs_to_pids_reply(), + send_done(Callers, SCC), + continue_broadcast_done(Unknown, SCC, Coordinator). -broadcast_done(#state{job = SCC}, Callers) -> +send_done(Callers, SCC) -> ?debug("Sending ~p: ~p\n",[SCC, Callers]), SendSTFun = fun(PID) -> PID ! {done, SCC} end, lists:foreach(SendSTFun, Callers). +continue_broadcast_done([], _SCC, _Coordinator) -> ok; +continue_broadcast_done(Rest, SCC, Coordinator) -> + dialyzer_coordinator:sccs_to_pids_request(Rest, Coordinator), + {Callers, Unknown} = dialyzer_coordinator:sccs_to_pids_reply(), + send_done(Callers, SCC), + continue_broadcast_done(Unknown, SCC, Coordinator). + wait_for_success_typings(#state{depends_on = DependsOn} = State) -> receive {done, SCC} -> -- cgit v1.2.3