Merge pull request #606 from campanja-forks/fix-topo-sort

Start top-level applications as early as possible.

1 files changed, 71 insertions, 118 deletions

diff --git a/src/rlx_topo.erl b/src/rlx_topo.erl
index b9c94b1..f8fc5ad 100644
--- a/src/rlx_topo.erl
+++ b/src/rlx_topo.erl
@@ -17,10 +17,12 @@
 %%%-------------------------------------------------------------------
 %%% @author Joe Armstrong
 %%% @author Eric Merritt
+%%% @author Konstantin Tcepliaev
 %%% @doc
 %%%  This is a pretty simple topological sort for erlang. It was
 %%%  originally written for ermake by Joe Armstrong back in '98. It
 %%%  has been pretty heavily modified by Eric Merritt since '06 and modified again for Relx.
+%%%  Konstantin Tcepliaev rewrote the algorithm in 2017.
 %%%
 %%%  A partial order on the set S is a set of pairs {Xi,Xj} such that
 %%%  some relation between Xi and Xj is obeyed.
@@ -28,24 +30,22 @@
 %%%  A topological sort of a partial order is a sequence of elements
 %%%  [X1, X2, X3 ...] such that if whenever {Xi, Xj} is in the partial
 %%%  order i < j
+%%%
+%%%  This particular implementation guarantees that nodes closer to
+%%%  the top level of the graph will be put as close as possible to
+%%%  the beginning of the resulting list - this ensures that dependencies
+%%%  are started as late as possible, and top-level apps are started
+%%%  as early as possible.
 %%% @end
 %%%-------------------------------------------------------------------
 -module(rlx_topo).
 
--export([sort/1,
-         sort_apps/1,
+-export([sort_apps/1,
          format_error/1]).
 
 -include("relx.hrl").
 
 %%====================================================================
-%% Types
-%%====================================================================
--type pair() :: {DependentApp::atom(), PrimaryApp::atom()}.
--type name() :: AppName::atom().
--type element() :: name() | pair().
-
-%%====================================================================
 %% API
 %%====================================================================
 
@@ -58,37 +58,64 @@
                        {ok, [rlx_app_info:t()]} |
                        relx:error().
 sort_apps(Apps) ->
-    Pairs = apps_to_pairs(Apps),
-    case sort(Pairs) of
-        {ok, Names} ->
-            {ok, names_to_apps(Names, Apps)};
+    AppDeps = [{rlx_app_info:name(App),
+                rlx_app_info:active_deps(App) ++ rlx_app_info:library_deps(App)}
+               || App <- Apps],
+    {AppNames, _} = lists:unzip(AppDeps),
+    case lists:foldl(fun iterator/2, {ok, [], AppDeps, []}, AppNames) of
+        {ok, Names, _, _} ->
+            {ok, names_to_apps(lists:reverse(Names), Apps)};
         E ->
             E
     end.
 
-%% @doc Do a topological sort on the list of pairs.
--spec sort([pair()]) -> {ok, [atom()]} | relx:error().
-sort(Pairs) ->
-    iterate(Pairs, [], all(Pairs)).
-
 %% @doc nicely format the error from the sort.
 -spec format_error(Reason::term()) -> iolist().
-format_error({cycle, Pairs}) ->
+format_error({cycle, App, Path}) ->
     ["Cycle detected in dependency graph, this must be resolved "
      "before we can continue:\n",
-    case Pairs of
-        [{P1, P2}] ->
-            [rlx_util:indent(2), erlang:atom_to_list(P2), "->", erlang:atom_to_list(P1)];
-        [{P1, P2} | Rest] ->
-            [rlx_util:indent(2), erlang:atom_to_list(P2), "->", erlang:atom_to_list(P1),
-             [["-> ", erlang:atom_to_list(PP2), " -> ", erlang:atom_to_list(PP1)] || {PP1, PP2} <- Rest]];
-        [] ->
-            []
-    end].
+     rlx_util:indent(2),
+     [[erlang:atom_to_list(A), " -> "] || A <- lists:reverse(Path)],
+     erlang:atom_to_list(App)].
 
 %%====================================================================
 %% Internal Functions
 %%====================================================================
+
+-type name() :: AppName::atom().
+-type app_dep() :: {AppName::name(), [DepName::name()]}.
+-type iterator_state() :: {ok, [Acc::name()],
+                           [Apps::app_dep()],
+                           [Path::name()]}.
+
+-spec iterator(name(), iterator_state() | relx:error()) ->
+                      iterator_state() | relx:error().
+iterator(App, {ok, Acc, Apps, Path}) ->
+    case lists:member(App, Acc) of
+        false ->
+            %% haven't seen this app yet
+            case lists:keytake(App, 1, Apps) of
+                {value, {App, Deps}, NewApps} ->
+                    DepInit = {ok, Acc, NewApps, [App | Path]},
+                    %% recurse over deps
+                    case lists:foldl(fun iterator/2, DepInit, Deps) of
+                        {ok, DepAcc, DepApps, _} ->
+                            {ok, [App | DepAcc], DepApps, Path};
+                        Error ->
+                            Error
+                    end;
+                false ->
+                    %% we have visited this app before,
+                    %% that means there's a cycle
+                    ?RLX_ERROR({cycle, App, Path})
+            end;
+        true ->
+            %% this app and its deps were already processed
+            {ok, Acc, Apps, Path}
+    end;
+iterator(_, Error) ->
+    Error.
+
 -spec names_to_apps([atom()], [rlx_app_info:t()]) -> [rlx_app_info:t()].
 names_to_apps(Names, Apps) ->
  [find_app_by_name(Name, Apps) || Name <- Names].
@@ -101,104 +128,17 @@ find_app_by_name(Name, Apps) ->
                       end, Apps),
     App1.
 
--spec apps_to_pairs([rlx_app_info:t()]) -> [pair()].
-apps_to_pairs(Apps) ->
-    lists:flatten([app_to_pairs(App) || App <- Apps]).
-
--spec app_to_pairs(rlx_app_info:t()) -> [pair()].
-app_to_pairs(App) ->
-    [{DepApp, rlx_app_info:name(App)} ||
-        DepApp <-
-            rlx_app_info:active_deps(App) ++
-            rlx_app_info:library_deps(App)].
-
-
-%% @doc Iterate over the system.  @private
--spec iterate([pair()], [name()], [name()]) ->
-    {ok, [name()]} | relx:error().
-iterate([], L, All) ->
-    {ok, remove_duplicates(L ++ subtract(All, L))};
-iterate(Pairs, L, All) ->
-    case subtract(lhs(Pairs), rhs(Pairs)) of
-        []  ->
-            ?RLX_ERROR({cycle, Pairs});
-        Lhs ->
-            iterate(remove_pairs(Lhs, Pairs), L ++ Lhs, All)
-    end.
-
--spec all([pair()]) -> [atom()].
-all(L) ->
-    lhs(L) ++ rhs(L).
-
--spec lhs([pair()]) -> [atom()].
-lhs(L) ->
-    [X || {X, _} <- L].
-
--spec rhs([pair()]) -> [atom()].
-rhs(L) ->
-    [Y || {_, Y} <- L].
-
-%% @doc all the elements in L1 which are not in L2
-%% @private
--spec subtract([element()], [element()]) -> [element()].
-subtract(L1, L2) ->
-    [X || X <- L1, not lists:member(X, L2)].
-
-%% @doc remove dups from the list.  @private
--spec remove_duplicates([element()]) -> [element()].
-remove_duplicates([H|T]) ->
-  case lists:member(H, T) of
-      true  ->
-          remove_duplicates(T);
-      false ->
-          [H|remove_duplicates(T)]
-  end;
-remove_duplicates([]) ->
-    [].
-
-%% @doc
-%%   removes all pairs from L2 where the first element
-%%   of each pair is a member of L1
-%%
-%%   L2' L1 = [X] L2 = [{X,Y}].
-%% @private
--spec remove_pairs([atom()], [pair()]) -> [pair()].
-remove_pairs(L1, L2) ->
-    [All || All={X, _Y} <- L2, not lists:member(X, L1)].
-
 %%====================================================================
 %% Tests
 %%====================================================================
 -ifdef(TEST).
 -include_lib("eunit/include/eunit.hrl").
 
-topo_1_test() ->
-    Pairs = [{one,two},{two,four},{four,six},
-             {two,ten},{four,eight},
-             {six,three},{one,three},
-             {three,five},{five,eight},
-             {seven,five},{seven,nine},
-             {nine,four},{nine,ten}],
-    ?assertMatch({ok, [one,seven,two,nine,four,six,three,five,eight,ten]},
-                 sort(Pairs)).
-topo_2_test() ->
-    Pairs = [{app2, app1}, {zapp1, app1}, {stdlib, app1},
-             {app3, app2}, {kernel, app1}, {kernel, app3},
-             {app2, zapp1}, {app3, zapp1}, {zapp2, zapp1}],
-    ?assertMatch({ok, [stdlib, kernel, zapp2,
-                       app3, app2, zapp1, app1]},
-                 sort(Pairs)).
-
-topo_pairs_cycle_test() ->
-    Pairs = [{app2, app1}, {app1, app2}, {stdlib, app1}],
-    ?assertMatch({error, {_, {cycle, [{app2, app1}, {app1, app2}]}}},
-                 sort(Pairs)).
-
 topo_apps_cycle_test() ->
     {ok, App1} = rlx_app_info:new(app1, "0.1", "/no-dir", [app2], [stdlib]),
     {ok, App2} = rlx_app_info:new(app2, "0.1", "/no-dir", [app1], []),
     Apps = [App1, App2],
-    ?assertMatch({error, {_, {cycle, [{app2,app1},{app1,app2}]}}},
+    ?assertMatch({error, {_, {cycle, app1, [app2, app1]}}},
                  sort_apps(Apps)).
 
 topo_apps_good_test() ->
@@ -212,8 +152,21 @@ topo_apps_good_test() ->
                     rlx_app_info:new(kernel, "0.1", "/no-dir", [], []),
                     rlx_app_info:new(zapp2, "0.1", "/no-dir", [], [])]],
     {ok, Sorted} = sort_apps(Apps),
-    ?assertMatch([stdlib, kernel, zapp2,
-                  app3, app2, zapp1, app1],
+    ?assertMatch([kernel, app3, app2, zapp2, zapp1, stdlib, app1],
+                 [rlx_app_info:name(App) || App <- Sorted]).
+
+topo_apps_1_test() ->
+    Apps = [App ||
+               {ok, App} <-
+                   [rlx_app_info:new(app0, "0.1", "/no-dir", [], [stdlib, dep1, dep2, dep3]),
+                    rlx_app_info:new(app1, "0.1", "/no-dir", [], [stdlib, kernel]),
+                    rlx_app_info:new(dep1, "0.1", "/no-dir", [], []),
+                    rlx_app_info:new(dep2, "0.1", "/no-dir", [], []),
+                    rlx_app_info:new(dep3, "0.1", "/no-dir", [], []),
+                    rlx_app_info:new(stdlib, "0.1", "/no-dir", [], []),
+                    rlx_app_info:new(kernel, "0.1", "/no-dir", [], [])]],
+    {ok, Sorted} = sort_apps(Apps),
+    ?assertMatch([stdlib, dep1, dep2, dep3, app0, kernel, app1],
                  [rlx_app_info:name(App) || App <- Sorted]).
 
 topo_apps_2_test() ->