summaryrefslogtreecommitdiff
path: root/src/rebar_topo.erl
diff options
context:
space:
mode:
Diffstat (limited to 'src/rebar_topo.erl')
-rw-r--r--src/rebar_topo.erl212
1 files changed, 0 insertions, 212 deletions
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.
generated by cgit v1.1 at 2024-12-25 07:12:12 +0000