diff options
Diffstat (limited to 'src/rlx_topo.erl')
-rw-r--r-- | src/rlx_topo.erl | 189 |
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() -> |