diff options
Diffstat (limited to 'src/rlx_topo.erl')
| -rw-r--r-- | src/rlx_topo.erl | 190 |
1 files changed, 190 insertions, 0 deletions
diff --git a/src/rlx_topo.erl b/src/rlx_topo.erl new file mode 100644 index 0000000..f8fc5ad --- /dev/null +++ b/src/rlx_topo.erl @@ -0,0 +1,190 @@ +%% -*- erlang-indent-level: 4; indent-tabs-mode: nil; fill-column: 80 -*- +%%% Copyright 2012 Erlware, LLC. All Rights Reserved. +%%% +%%% This file is provided to you under the Apache License, +%%% Version 2.0 (the "License"); you may not use this file +%%% except in compliance with the License. You may obtain +%%% a copy of the License at +%%% +%%% http://www.apache.org/licenses/LICENSE-2.0 +%%% +%%% Unless required by applicable law or agreed to in writing, +%%% software distributed under the License is distributed on an +%%% "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY +%%% KIND, either express or implied. See the License for the +%%% specific language governing permissions and limitations +%%% under the License. +%%%------------------------------------------------------------------- +%%% @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. +%%% +%%% 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_apps/1, + format_error/1]). + +-include("relx.hrl"). + +%%==================================================================== +%% API +%%==================================================================== + +%% @doc This only does a topo sort on the list of applications and +%% assumes that there is only *one* version of each app in the list of +%% applications. This implies that you have already done the +%% constraint solve before you pass the list of apps here to be +%% sorted. +-spec sort_apps([rlx_app_info:t()]) -> + {ok, [rlx_app_info:t()]} | + relx:error(). +sort_apps(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 nicely format the error from the sort. +-spec format_error(Reason::term()) -> iolist(). +format_error({cycle, App, Path}) -> + ["Cycle detected in dependency graph, this must be resolved " + "before we can continue:\n", + 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]. + +-spec find_app_by_name(atom(), [rlx_app_info:t()]) -> rlx_app_info:t(). +find_app_by_name(Name, Apps) -> + {ok, App1} = + ec_lists:find(fun(App) -> + rlx_app_info:name(App) =:= Name + end, Apps), + App1. + +%%==================================================================== +%% Tests +%%==================================================================== +-ifdef(TEST). +-include_lib("eunit/include/eunit.hrl"). + +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, app1, [app2, app1]}}}, + sort_apps(Apps)). + +topo_apps_good_test() -> + Apps = [App || + {ok, App} <- + [rlx_app_info:new(app1, "0.1", "/no-dir", [app2, zapp1], [stdlib, kernel]), + rlx_app_info:new(app2, "0.1", "/no-dir", [app3], []), + rlx_app_info:new(app3, "0.1", "/no-dir", [kernel], []), + rlx_app_info:new(zapp1, "0.1", "/no-dir", [app2,app3,zapp2], []), + rlx_app_info:new(stdlib, "0.1", "/no-dir", [], []), + rlx_app_info:new(kernel, "0.1", "/no-dir", [], []), + rlx_app_info:new(zapp2, "0.1", "/no-dir", [], [])]], + {ok, Sorted} = sort_apps(Apps), + ?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() -> + Apps = [App || + {ok, App} <- + [rlx_app_info:new(app1, "0.1", "/no-dir", [app2, app3, app4, app5, + stdlib, kernel], + []), + rlx_app_info:new(app2, "0.1", "/no-dir", [stdlib, kernel], []), + rlx_app_info:new(app3, "0.1", "/no-dir", [stdlib, kernel], []), + rlx_app_info:new(app4, "0.1", "/no-dir", [stdlib, kernel], []), + rlx_app_info:new(app5, "0.1", "/no-dir", [stdlib, kernel], []), + 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, kernel, app2, + app3, app4, app5, app1], + [rlx_app_info:name(App) || App <- Sorted]). + +-endif. |