diff options
| -rw-r--r-- | src/rebar_digraph.erl | 49 | ||||
| -rw-r--r-- | src/rebar_prv_install_deps.erl | 2 | ||||
| -rw-r--r-- | src/rebar_prv_test_deps.erl | 2 | ||||
| -rw-r--r-- | src/rebar_topo.erl | 212 |
4 files changed, 50 insertions, 215 deletions
diff --git a/src/rebar_digraph.erl b/src/rebar_digraph.erl index bbcb736..0ca5984 100644 --- a/src/rebar_digraph.erl +++ b/src/rebar_digraph.erl @@ -1,12 +1,45 @@ -module(rebar_digraph). --export([restore_graph/1 +-export([sort_apps/1 + ,restore_graph/1 ,solve/2 ,subgraph/2 ,format_error/1]). -include("rebar.hrl"). +sort_apps(Apps) -> + Graph = digraph:new(), + lists:foreach(fun(App) -> + Name = rebar_app_info:name(App), + Deps = rebar_app_info:deps(App), + add(Graph, {Name, Deps}) + end, Apps), + case digraph_utils:topsort(Graph) of + false -> + {error, no_sort}; + V -> + {ok, names_to_apps(lists:reverse(V), Apps)} + end. + +add(Graph, {PkgName, Deps}) -> + case digraph:vertex(Graph, PkgName) of + false -> + V = digraph:add_vertex(Graph, PkgName); + {V, []} -> + V + end, + + lists:foreach(fun(DepName) -> + V3 = case digraph:vertex(Graph, DepName) of + false -> + digraph:add_vertex(Graph, DepName); + {V2, []} -> + V2 + end, + digraph:add_edge(Graph, V, V3) + end, Deps). + restore_graph({Vs, Es}) -> Graph = digraph:new(), lists:foreach(fun({V, LastUpdated}) -> @@ -45,3 +78,17 @@ subgraph(Graph, Vertices) -> format_error(no_solution) -> io_lib:format("No solution for packages found.", []). + +%%==================================================================== +%% Internal Functions +%%==================================================================== + +-spec names_to_apps([atom()], [rebar_app_info:t()]) -> [rebar_app_info:t()]. +names_to_apps(Names, Apps) -> + [element(2, App) || App <- [find_app_by_name(Name, Apps) || Name <- Names], App =/= error]. + +-spec find_app_by_name(atom(), [rebar_app_info:t()]) -> {ok, rebar_app_info:t()} | error. +find_app_by_name(Name, Apps) -> + ec_lists:find(fun(App) -> + ec_cnv:to_atom(rebar_app_info:name(App)) =:= ec_cnv:to_atom(Name) + end, Apps). diff --git a/src/rebar_prv_install_deps.erl b/src/rebar_prv_install_deps.erl index 81bc71f..d9cf7ac 100644 --- a/src/rebar_prv_install_deps.erl +++ b/src/rebar_prv_install_deps.erl @@ -77,7 +77,7 @@ do(State) -> end, Source = ProjectApps ++ rebar_state:src_apps(State1), - case rebar_topo:sort_apps(Source) of + case rebar_digraph:sort_apps(Source) of {ok, Sort} -> {ok, rebar_state:set(State1, deps_to_build, lists:dropwhile(fun rebar_app_info:valid/1, Sort -- ProjectApps))}; diff --git a/src/rebar_prv_test_deps.erl b/src/rebar_prv_test_deps.erl index 7975f27..108af98 100644 --- a/src/rebar_prv_test_deps.erl +++ b/src/rebar_prv_test_deps.erl @@ -43,7 +43,7 @@ do(State) -> AllDeps = rebar_state:get(State2, all_deps, []), State3 = rebar_state:set(State2, deps_dir, DepsDir), - case rebar_topo:sort_apps(ProjectApps1++AllDeps) of + case rebar_digraph:sort_apps(ProjectApps1++AllDeps) of {ok, Sort} -> ToBuild = lists:dropwhile(fun rebar_app_info:valid/1, Sort -- ProjectApps1), State4 = rebar_state:set(State3, deps_to_build, ToBuild), diff --git a/src/rebar_topo.erl b/src/rebar_topo.erl deleted file mode 100644 index d9f426d..0000000 --- a/src/rebar_topo.erl +++ /dev/null @@ -1,212 +0,0 @@ -%% -*- 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 -%%% @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. -%%% -%%% 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 -%%% @end -%%%------------------------------------------------------------------- --module(rebar_topo). - --export([sort/1, - sort_apps/1, - format_error/1]). - --include("rebar.hrl"). - -%%==================================================================== -%% Types -%%==================================================================== --type pair() :: {DependentApp::atom(), PrimaryApp::atom()}. --type name() :: AppName::atom(). --type element() :: name() | pair(). - -%%==================================================================== -%% 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([rebar_app_info:t()]) -> {ok, [rebar_app_info:t()]} | {error, any()}. -sort_apps(Apps) -> - Pairs = apps_to_pairs(Apps), - case sort(Pairs) of - {ok, Names} -> - {ok, names_to_apps(Names, Apps)}; - E -> - E - end. - -%% @doc Do a topological sort on the list of pairs. --spec sort([pair()]) -> {ok, [atom()]} | {error, any()}. -sort(Pairs) -> - iterate(Pairs, [], all(Pairs)). - -%% @doc nicely format the error from the sort. --spec format_error(Reason::term()) -> iolist(). -format_error({cycle, Pairs}) -> - ["Cycle detected in dependency graph, this must be resolved " - "before we can continue:\n", - case Pairs of - [{P1, P2}] -> - [rebar_utils:indent(2), erlang:atom_to_list(P2), "->", erlang:atom_to_list(P1)]; - [{P1, P2} | Rest] -> - [rebar_utils: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]. - -%%==================================================================== -%% Internal Functions -%%==================================================================== --spec names_to_apps([atom()], [rebar_app_info:t()]) -> [rebar_app_info:t()]. -names_to_apps(Names, Apps) -> - [element(2, App) || App <- [find_app_by_name(Name, Apps) || Name <- Names], App =/= error]. - --spec find_app_by_name(atom(), [rebar_app_info:t()]) -> {ok, rebar_app_info:t()} | error. -find_app_by_name(Name, Apps) -> - ec_lists:find(fun(App) -> - ec_cnv:to_atom(rebar_app_info:name(App)) =:= ec_cnv:to_atom(Name) - end, Apps). - --spec apps_to_pairs([rebar_app_info:t()]) -> [pair()]. -apps_to_pairs(Apps) -> - lists:flatten([app_to_pairs(App) || App <- Apps]). - --spec app_to_pairs(rebar_app_info:t()) -> [pair()]. -app_to_pairs(App) -> - [{ec_cnv:to_atom(DepApp), ec_cnv:to_atom(rebar_app_info:name(App))} || - DepApp <- - rebar_app_info:deps(App)]. - - -%% @doc Iterate over the system. @private --spec iterate([pair()], [name()], [name()]) -> - {ok, [name()]} | {error, iolist()}. -iterate([], L, All) -> - {ok, remove_duplicates(L ++ subtract(All, L))}; -iterate(Pairs, L, All) -> - case subtract(lhs(Pairs), rhs(Pairs)) of - [] -> - {error, format_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 -%%==================================================================== --ifndef(NOTEST). --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, _}, sort(Pairs)). - -topo_apps_cycle_test() -> - {ok, App1} = rebar_app_info:new(app1, "0.1", "/no-dir", [app2]), - {ok, App2} = rebar_app_info:new(app2, "0.1", "/no-dir", [app1]), - Apps = [App1, App2], - ?assertMatch({error, _}, sort_apps(Apps)). - -topo_apps_good_test() -> - Apps = [App || - {ok, App} <- - [rebar_app_info:new(app1, "0.1", "/no-dir", [app2, zapp1]), - rebar_app_info:new(app2, "0.1", "/no-dir", [app3]), - rebar_app_info:new(app3, "0.1", "/no-dir", [kernel]), - rebar_app_info:new(zapp1, "0.1", "/no-dir", [app2,app3,zapp2]), - rebar_app_info:new(stdlib, "0.1", "/no-dir", []), - rebar_app_info:new(kernel, "0.1", "/no-dir", []), - rebar_app_info:new(zapp2, "0.1", "/no-dir", [])]], - {ok, Sorted} = sort_apps(Apps), - ?assertMatch([stdlib, kernel, zapp2, - app3, app2, zapp1, app1], - [ec_cnv:to_atom(rebar_app_info:name(App)) || App <- Sorted]). - --endif. |