Avoid digraph_utils:condensation and ordering in typesig

3 files changed, 95 insertions, 33 deletions

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} ->