-module(rebar_digraph). -export([compile_order/1 ,restore_graph/1 ,cull_deps/2 ,cull_deps/3 ,subgraph/2 ,format_error/1]). -include("rebar.hrl"). %% Sort apps with topological sort to get proper build order compile_order(Apps) -> Graph = digraph:new(), lists:foreach(fun(App) -> Name = rebar_app_info:name(App), Deps = all_apps_deps(App), add(Graph, {Name, Deps}) end, Apps), case digraph_utils:topsort(Graph) of false -> case digraph_utils:is_acyclic(Graph) of true -> {error, no_sort}; false -> Cycles = lists:sort( [lists:sort(Comp) || Comp <- digraph_utils:strong_components(Graph), length(Comp)>1]), {error, {cycles, Cycles}} end; 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) -> Name1 = case DepName of {Name, _Vsn} -> ec_cnv:to_binary(Name); Name -> ec_cnv:to_binary(Name) end, V3 = case digraph:vertex(Graph, Name1) of false -> digraph:add_vertex(Graph, Name1); {V2, []} -> V2 end, digraph:add_edge(Graph, V, V3) end, Deps). restore_graph({Vs, Es}) -> Graph = digraph:new(), lists:foreach(fun({V, LastUpdated}) -> digraph:add_vertex(Graph, V, LastUpdated) end, Vs), lists:foreach(fun({V1, V2}) -> digraph:add_edge(Graph, V1, V2) end, Es), Graph. %% Pick packages to fullfill dependencies %% The first dep while traversing the graph is chosen and any conflicting %% dep encountered later on is ignored. cull_deps(Graph, Vertices) -> cull_deps(Graph, Vertices, sets:new()). cull_deps(Graph, Vertices, Seen) -> Vertices1 = lists:keysort(2, Vertices), {Solution, Levels, Discarded} = {dict:new(), dict:new(), []}, cull_deps(Graph, Vertices1, Levels, Solution, Seen, Discarded). format_error(no_solution) -> io_lib:format("No solution for packages found.", []). %%==================================================================== %% Internal Functions %%==================================================================== cull_deps(_Graph, [], Levels, Solution, _, Discarded) -> {_, Vertices} = lists:unzip(dict:to_list(Solution)), LvlVertices = [{Profile, {Parent, App, Vsn, dict:fetch(App, Levels)}} || {Profile, {Parent,App,Vsn}} <- Vertices], {ok, LvlVertices, Discarded}; cull_deps(Graph, [{Profile, Level, Vs} | Vertices], Levels, Solution, Seen, Discarded) -> {NV, NS, LS, DS} = lists:foldl(fun({Parent, Name, Vsn}, {Acc, SolutionAcc, LevelsAcc, DiscardedAcc}) -> {SolutionAcc1, LevelsAcc1, DiscardedAcc1} = maybe_add_to_solution(Profile, Level, Name, {Name, Vsn}, Parent ,SolutionAcc ,LevelsAcc, Seen, DiscardedAcc), OutNeighbors = digraph:out_neighbours(Graph, {Name,Vsn}), {NewVertices, DiscardedAcc2} = handle_neighbors(Profile, Level, Name ,OutNeighbors, Acc, SolutionAcc1 ,Seen, DiscardedAcc1), {NewVertices, SolutionAcc1, LevelsAcc1, DiscardedAcc2} end, {[], Solution, Levels, Discarded}, Vs), NewVertices = combine_profile_levels(Vertices, NV), cull_deps(Graph, NewVertices, LS, NS, Seen, DS). %% Combine lists of deps that have the same profile and level combine_profile_levels(Vertices, NewVertices) -> V = lists:foldl(fun({Profile, Level, Vs}, Acc) -> case ec_lists:find(fun({P, L, _}) -> P =:= Profile andalso L =:= Level end, Acc) of {ok, {_, _, OldVs}=Old} -> lists:delete(Old, Acc)++[{Profile, Level, lists:keysort(1, OldVs++Vs)}]; error -> Acc++[{Profile, Level, Vs}] end end, Vertices, NewVertices), lists:keysort(2, V). %% For each outgoing edge of a dep check if it should be added to the solution %% and add it to the list of vertices to do the same for handle_neighbors(Profile, Level, Parent, OutNeighbors, Vertices ,Solution, Seen, Discarded) -> case lists:foldl(fun({Name, Vsn}=Value, {NewVertices, Discarded1}) -> case dict:find(Name, Solution) of {ok, {Profile, {Parent, Name, Vsn}}} -> % already seen {NewVertices, Discarded1}; {ok, _} -> % conflict resolution! %% Warn on different version {NewVertices, [Value|Discarded1]}; error -> %% We check Seen separately because we don't care %% to warn if the exact same version of a package %% was already part of the solution but we do %% if it was simply seen in source deps case sets:is_element(Name, Seen) of true -> {NewVertices, [Value|Discarded1]}; false -> {[{Parent, Name, Vsn} | NewVertices], Discarded1} end end end, {[], Discarded}, OutNeighbors) of {[], DiscardedAcc2} -> {Vertices, DiscardedAcc2}; {NewVertices1, DiscardedAcc2} -> {Vertices++[{Profile, Level+1, NewVertices1}] ,DiscardedAcc2} end. maybe_add_to_solution(Profile, Level, Key, {Name, Vsn}=Value, Parent ,Solution, Levels, Seen, Discarded) -> case dict:find(Key, Solution) of {ok, {Profile, {Parent, Name, Vsn}}} -> % already seen {Solution, Levels, Discarded}; {ok, _} -> % conflict resolution! %% Warn on different version {Solution, Levels, [Value|Discarded]}; error -> %% We check Seen separately because we don't care to warn if the exact %% same version of a package was already part of the solution but we do %% if it was simply seen in source deps case sets:is_element(Name, Seen) of true -> {Solution, Levels, [Value|Discarded]}; false -> {dict:store(Key, {Profile, {Parent, Name, Vsn}}, Solution), dict:store(Key, Level, Levels), Discarded} end end. subgraph(Graph, Vertices) -> digraph_utils:subgraph(Graph, Vertices). -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) -> rebar_app_info:name(App) =:= Name end, Apps). %% The union of all entries in the applications list for an app and %% the deps listed in its rebar.config is all deps that may be needed %% for building the app. all_apps_deps(App) -> Applications = lists:usort([atom_to_binary(X, utf8) || X <- rebar_app_info:applications(App)]), Deps = lists:usort(lists:map(fun({Name, _}) -> Name; (Name) -> Name end, rebar_app_info:deps(App))), lists:umerge(Deps, Applications).