dialyzer: Sort graphs topologically

Although some variable names indicate that lists of SCCs and modules
are sorted, that was not always the case. The effect on the execution
time of sorting them doesn't seem to be significant.

dialyzer_coordinator:sccs_to_pids() should now always return an empty
second list (not yet started workers).

Since the condensation of graphs often needs a lot of heap memory, it
is run in a separate process.

1 files changed, 53 insertions, 26 deletions

diff --git a/lib/dialyzer/src/dialyzer_callgraph.erl b/lib/dialyzer/src/dialyzer_callgraph.erl
index 8f6a3b99b3..27249440e9 100644
--- a/lib/dialyzer/src/dialyzer_callgraph.erl
+++ b/lib/dialyzer/src/dialyzer_callgraph.erl
@@ -287,7 +287,9 @@ module_postorder(#callgraph{digraph = DG}) ->
   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)),
-  {digraph_utils:topsort(MDG), {'d', MDG}}.
+  %% The out-neighbors of a vertex are the vertices called directly.
+  %% The used vertices are to occur *before* the calling vertex:
+  {lists:reverse(digraph_utils:topsort(MDG)), {'d', MDG}}.
 
 edge_fold({{M1,_,_},{M2,_,_}}, Set) ->
   case M1 =/= M2 of
@@ -774,28 +776,53 @@ to_ps(#callgraph{} = CG, File, Args) ->
   ok.
 
 condensation(G) ->
-  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, 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}.
+  erlang:garbage_collect(), % reduce heap size
+  {Pid, Ref} = erlang:spawn_monitor(do_condensation(G, self())),
+  receive {'DOWN', Ref, process, Pid, Result} ->
+      {SCCInts, OutETS, InETS, MapsETS} = Result,
+      NewSCCs = [ets:lookup_element(MapsETS, SCCInt, 2) || SCCInt <- SCCInts],
+      {{'e', OutETS, InETS, MapsETS}, NewSCCs}
+  end.
+
+-spec do_condensation(digraph:graph(), pid()) -> fun(() -> no_return()).
+
+do_condensation(G, Parent) ->
+  fun() ->
+      [OutETS, InETS, MapsETS] =
+        [ets:new(Name,[{read_concurrency, true}]) ||
+          Name <- [callgraph_deps_out, callgraph_deps_in, callgraph_scc_map]],
+      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}]),
+      %% Create mapping from unique integers to SCCs:
+      ets:insert(MapsETS, IntToSCC),
+      %% 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)),
+      R2Strict = sofs:strict_relation(R2),
+      %% Create out-neighbours:
+      Out = sofs:relation_to_family(sofs:converse(R2Strict)),
+      ets:insert(OutETS, sofs:to_external(Out)),
+      %% Sort the SCCs topologically:
+      DG = sofs:family_to_digraph(Out),
+      lists:foreach(fun(I) -> digraph:add_vertex(DG, I) end, Ints),
+      SCCInts0 = digraph_utils:topsort(DG),
+      digraph:delete(DG),
+      %% The out-neighbors of a vertex are the vertices called directly.
+      %% The used vertices are to occur *before* the calling vertex:
+      SCCInts = lists:reverse(SCCInts0),
+      %% Create in-neighbours:
+      In = sofs:relation_to_family(R2Strict),
+      ets:insert(InETS, sofs:to_external(In)),
+      %% Create mapping from SCCs to unique integers:
+      ets:insert(MapsETS, lists:zip([{'scc', SCC} || SCC<- SCCs], Ints)),
+      lists:foreach(fun(E) -> true = ets:give_away(E, Parent, any)
+                    end, [OutETS, InETS, MapsETS]),
+      exit({SCCInts, OutETS, InETS, MapsETS})
+  end.