summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authorTristan Sloughter <t@crashfast.com>2014-11-22 12:58:23 -0600
committerTristan Sloughter <t@crashfast.com>2014-11-22 20:24:21 -0600
commit4888810c69548c08034bd6be941a28ed7e29a7cf (patch)
tree406f0021ddb95a0810de639b15159cbe34252c65 /src
parenteb5c0eb42434d0603149f6de460bef7b3ef7b4de (diff)
use digraph topo sort for building
Diffstat (limited to 'src')
-rw-r--r--src/rebar_digraph.erl49
-rw-r--r--src/rebar_prv_install_deps.erl2
-rw-r--r--src/rebar_prv_test_deps.erl2
-rw-r--r--src/rebar_topo.erl212
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 &lt; 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.