From ab92f1a2925fc69215d1355a6a8ec263c3e36007 Mon Sep 17 00:00:00 2001 From: Tristan Sloughter Date: Wed, 12 Aug 2015 22:36:34 -0500 Subject: install package deps in same level/profile order as src deps --- src/rebar_digraph.erl | 133 +++++++++++++++++++++++++++-------------- src/rebar_prv_deps.erl | 3 +- src/rebar_prv_install_deps.erl | 85 +++++++++++++------------- src/rebar_prv_lock.erl | 2 +- 4 files changed, 130 insertions(+), 93 deletions(-) (limited to 'src') diff --git a/src/rebar_digraph.erl b/src/rebar_digraph.erl index e989fdc..af51ecc 100644 --- a/src/rebar_digraph.erl +++ b/src/rebar_digraph.erl @@ -2,8 +2,8 @@ -export([compile_order/1 ,restore_graph/1 + ,cull_deps/2 ,cull_deps/3 - ,cull_deps/4 ,subgraph/2 ,print_solution/2 ,format_error/1]). @@ -70,64 +70,112 @@ restore_graph({Vs, Es}) -> %% 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, Level) -> - {ok, LvlVertices, Discarded, _} = cull_deps(Graph, Vertices, Level, none), +cull_deps(Graph, Vertices) -> + {ok, LvlVertices, Discarded, _} = cull_deps(Graph, Vertices, none), {ok, LvlVertices, Discarded}. -cull_deps(Graph, Vertices, Level, SolutionGraph) -> +print_solution(Graph, PkgDeps=[{_, _, Deps} | _]) -> + SolutionGraph = digraph:new(), + [digraph:add_vertex(SolutionGraph, V) || V <- Deps], + cull_deps(Graph, PkgDeps, SolutionGraph), + print_solution(SolutionGraph, Deps, 0). + +format_error(no_solution) -> + io_lib:format("No solution for packages found.", []). + +%%==================================================================== +%% Internal Functions +%%==================================================================== + +cull_deps(Graph, Vertices, SolutionGraph) -> + {Solution, Levels} = build_initial_dicts(Vertices), cull_deps(Graph, Vertices, - Level+1, - lists:foldl(fun({Key, _}, Levels) -> - dict:store(Key, Level, Levels) - end, dict:new(), Vertices), - lists:foldl(fun({Key, _}=N, Solution) -> - dict:store(Key, N, Solution) - end, dict:new(), Vertices), + Levels, + Solution, [], SolutionGraph). -cull_deps(_Graph, [], _Level, Levels, Solution, Discarded, SolutionGraph) -> +cull_deps(_Graph, [], Levels, Solution, Discarded, SolutionGraph) -> {_, Vertices} = lists:unzip(dict:to_list(Solution)), - LvlVertices = [{App,Vsn,dict:fetch(App,Levels)} || {App,Vsn} <- Vertices], + LvlVertices = [{Profile, {App,Vsn,dict:fetch(App,Levels)}} || {Profile, {App,Vsn}} <- Vertices], {ok, LvlVertices, Discarded, SolutionGraph}; -cull_deps(Graph, Vertices, Level, Levels, Solution, Discarded, SolutionGraph) -> +cull_deps(Graph, [{Profile, Level, Vs} | Vertices], Levels, Solution, Discarded, SolutionGraph) -> {NV, NS, LS, DS} = - lists:foldl(fun(V, {NewVertices, SolutionAcc, LevelsAcc, DiscardedAcc}) -> - OutNeighbors = lists:keysort(1, digraph:out_neighbours(Graph, V)), - lists:foldl(fun({Key, _}=N, {NewVertices1, SolutionAcc1, LevelsAcc1, DiscardedAcc1}) -> - case dict:find(Key, SolutionAcc1) of - {ok, N} -> % already seen - {NewVertices1, SolutionAcc1, LevelsAcc1, DiscardedAcc1}; - {ok, _} -> % conflict resolution! - {NewVertices1, SolutionAcc1, LevelsAcc1, [N|DiscardedAcc1]}; - error -> - add_to_solution_graph(N, V, SolutionGraph), - {[N | NewVertices1], - dict:store(Key, N, SolutionAcc1), - dict:store(Key, Level, LevelsAcc1), - DiscardedAcc1} - end - end, {NewVertices, SolutionAcc, LevelsAcc, DiscardedAcc}, OutNeighbors) - end, {[], Solution, Levels, Discarded}, lists:keysort(1, Vertices)), - cull_deps(Graph, NV, Level+1, LS, NS, DS, SolutionGraph). + lists:foldl(fun(V, {Acc, SolutionAcc, LevelsAcc, DiscardedAcc}) -> + OutNeighbors = lists:keysort(1, digraph:out_neighbours(Graph, V)), + handle_neighbors(Profile, Level, V + ,OutNeighbors, Acc, SolutionAcc + ,LevelsAcc, DiscardedAcc, SolutionGraph) + + end, {[], Solution, Levels, Discarded}, lists:keysort(1, Vs)), + + cull_deps(Graph, Vertices++NV, LS, NS, DS, SolutionGraph). + +%% 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, Vertex, OutNeighbors, Vertices + ,Solution, Levels, Discarded, SolutionGraph) -> + case lists:foldl(fun({Key, _}=N, {NewVertices, Solution1, Levels1, Discarded1}) -> + maybe_add_to_solution(Profile, Level, Vertex, Key, N + ,NewVertices, Solution1 + ,Levels1, Discarded1, SolutionGraph) + end, {[], Solution, Levels, Discarded}, OutNeighbors) of + {[], SolutionAcc2, LevelsAcc2, DiscardedAcc2} -> + {Vertices, SolutionAcc2, LevelsAcc2, DiscardedAcc2}; + {NewVertices1, SolutionAcc2, LevelsAcc2, DiscardedAcc2} -> + {Vertices++[{Profile, Level+1, NewVertices1}] + ,SolutionAcc2, LevelsAcc2, DiscardedAcc2} + end. + +maybe_add_to_solution(Profile, Level, Vertex, Key, Value, Vertices + ,Solution, Levels, Discarded, SolutionGraph) -> + case dict:find(Key, Solution) of + {ok, Value} -> % already seen + {Vertices, + Solution, + Levels, + Discarded}; + {ok, _} -> % conflict resolution! + {Vertices, + Solution, + Levels, + [Value|Discarded]}; + error -> + add_to_solution_graph(Value, Vertex, SolutionGraph), + {[Value | Vertices], + dict:store(Key, {Profile, Value}, Solution), + dict:store(Key, Level+1, Levels), + Discarded} + end. subgraph(Graph, Vertices) -> digraph_utils:subgraph(Graph, Vertices). +maybe_add_to_dict(Key, Value, Dict) -> + case dict:is_key(Key, Dict) of + true -> + Dict; + false -> + dict:store(Key, Value, Dict) + end. + +%% Track the profile (so we know where to install it), name/vsn of each dep +%% and the level it is from (for the lock file) +build_initial_dicts(Vertices) -> + lists:foldl(fun({Profile, Level, Vs}, {Solution, Levels}) -> + lists:foldl(fun({Key, Vsn}, {SAcc, LAcc}) -> + {maybe_add_to_dict(Key, {Profile, {Key,Vsn}}, SAcc), + maybe_add_to_dict(Key, Level, LAcc)} + end, {Solution, Levels}, Vs) + end, {dict:new(), dict:new()}, Vertices). + add_to_solution_graph(_, _, none) -> ok; add_to_solution_graph(N, V, SolutionGraph) -> NewV = digraph:add_vertex(SolutionGraph, N), digraph:add_edge(SolutionGraph, V, NewV). -print_solution(Graph, Deps) -> - SolutionGraph = digraph:new(), - [digraph:add_vertex(SolutionGraph, V) || V <- Deps], - cull_deps(Graph, Deps, 0, SolutionGraph), - print_solution(SolutionGraph, Deps, 0). - print_solution(_, [], _) -> ok; print_solution(SolutionGraph, [{N, V} | Vertices], 0) -> @@ -141,13 +189,6 @@ print_solution(SolutionGraph, [{N, V} | Vertices], Indent) -> print_solution(SolutionGraph, OutNeighbors, Indent+4), print_solution(SolutionGraph, Vertices, Indent). -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]. diff --git a/src/rebar_prv_deps.erl b/src/rebar_prv_deps.erl index 9dc5346..112b60b 100644 --- a/src/rebar_prv_deps.erl +++ b/src/rebar_prv_deps.erl @@ -34,7 +34,8 @@ do(State) -> {_Packages, Graph} = rebar_state:packages(State), List = merge_deps_per_profile(State), {_SrcDeps, PkgDeps} = rebar_prv_install_deps:parse_deps(<<"">>, List, State, [], 0), - rebar_digraph:print_solution(Graph, PkgDeps), + PkgDeps1 = [{default, 0, PkgDeps}], + rebar_digraph:print_solution(Graph, PkgDeps1), {ok, State}; false -> Profiles = rebar_state:current_profiles(State), diff --git a/src/rebar_prv_install_deps.erl b/src/rebar_prv_install_deps.erl index 72350d6..be65032 100644 --- a/src/rebar_prv_install_deps.erl +++ b/src/rebar_prv_install_deps.erl @@ -125,11 +125,15 @@ handle_deps_as_profile(Profile, State, Deps, Upgrade) -> DepsDir = profile_dep_dir(State, Profile), {SrcDeps, PkgDeps} = parse_deps(DepsDir, Deps, State, Locks, Level), AllSrcProfileDeps = [{Profile, SrcDeps, Locks, Level}], - AllPkgProfileDeps = [{Profile, Locks, PkgDeps, Level}], + AllPkgProfileDeps = case PkgDeps of + [] -> + []; + _ -> + [{Profile, Level, PkgDeps}] + end, {AllApps, PkgDeps1, Seen, State1} = handle_profile_level(AllSrcProfileDeps, AllPkgProfileDeps, Locks, sets:new(), Upgrade, State), - handle_profile_pkg_level(PkgDeps1, AllApps, Seen, Upgrade, State1). - + handle_profile_pkg_level(PkgDeps1, AllApps, Seen, Upgrade, [], State1). %% =================================================================== %% Internal functions @@ -139,19 +143,23 @@ handle_deps_as_profile(Profile, State, Deps, Upgrade) -> deps_per_profile(Profiles, Upgrade, State) -> Level = 0, {AllProfileDeps, PkgDeps} = lists:foldl(fun(Profile, {SrcAcc, PkgAcc}) -> - {Src, Pkg} = parse_profile_deps(State, Profile, Level), - {[Src | SrcAcc], [Pkg | PkgAcc]} + case parse_profile_deps(State, Profile, Level) of + {Src, {_, _, []}} -> + {[Src | SrcAcc], PkgAcc}; + {Src, Pkg} -> + {[Src | SrcAcc], [Pkg | PkgAcc]} + end end, {[], []}, Profiles), {AllApps, PkgDeps1, Seen, State1} = handle_profile_level(AllProfileDeps, PkgDeps, [], sets:new(), Upgrade, State), - - handle_profile_pkg_level(PkgDeps1, AllApps, Seen, Upgrade, State1). + Locks = rebar_state:get(State, {locks, default}, []), + handle_profile_pkg_level(PkgDeps1, AllApps, Seen, Upgrade, Locks, State1). parse_profile_deps(State, Profile, Level) -> DepsDir = profile_dep_dir(State, Profile), Locks = rebar_state:get(State, {locks, Profile}, []), Deps = rebar_state:get(State, {deps, Profile}, []), {SrcDeps, PkgDeps} = parse_deps(DepsDir, Deps, State, Locks, Level), - {{Profile, SrcDeps, Locks, Level}, {Profile, Locks, PkgDeps, Level}}. + {{Profile, SrcDeps, Locks, Level}, {Profile, Level, PkgDeps}}. %% Level-order traversal of all dependencies, across profiles. %% If profiles x,y,z are present, then the traversal will go: @@ -166,28 +174,34 @@ handle_profile_level([{Profile, SrcDeps, Locks, Level} | Rest], PkgDeps, SrcApps [] -> Rest; _ -> Rest ++ [{Profile, SrcDeps1, Locks1, Level+1}] end, - handle_profile_level(SrcDeps2, [{Profile, Locks1, PkgDeps1, Level+1} | PkgDeps], SrcApps1++SrcApps, sets:union(Seen, Seen1), Upgrade, State1). - -handle_profile_pkg_level(PkgDeps, AllApps, Seen, Upgrade, State) -> + handle_profile_level(SrcDeps2, case PkgDeps1 of + [] -> + PkgDeps; + _ -> + [{Profile, Level+1, PkgDeps1} | PkgDeps] + end, SrcApps1++SrcApps, sets:union(Seen, Seen1), Upgrade, State1). + +handle_profile_pkg_level([], AllApps, _Seen, _Upgrade, _Locks, State) -> + {AllApps, State}; +handle_profile_pkg_level(PkgDeps, AllApps, Seen, Upgrade, Locks, State) -> %% Read in package index and dep graph {Packages, Graph} = rebar_state:packages(State), Registry = rebar_packages:registry(State), State1 = rebar_state:packages(rebar_state:registry(State, Registry) ,{Packages, Graph}), - lists:foldl(fun({_Profile, _, [], _}, {AllAcc, StateAcc}) -> - {AllAcc, StateAcc}; - ({Profile1, Locks, PkgDeps2, Level}, {AllAcc, StateAcc}) -> - {Solved, StateAcc2} = update_pkg_deps(Profile1, Packages, PkgDeps2 - ,Graph, Upgrade, Seen, StateAcc, Locks - ,Level), - - AllDeps = lists:ukeymerge(2 - ,lists:ukeysort(2, AllAcc) - ,lists:ukeysort(2, Solved)), + S = case rebar_digraph:cull_deps(Graph, lists:keysort(2, PkgDeps)) of + {ok, [], _} -> + throw({rebar_digraph, no_solution}); + {ok, Solution, []} -> + Solution; + {ok, Solution, Discarded} -> + [warn_skip_pkg(Pkg, State) || Pkg <- Discarded, not(pkg_locked(Pkg, Locks))], + Solution + end, - {AllDeps, StateAcc2} - end, {AllApps, State1}, PkgDeps). + {PkgApps, State2} = update_pkg_deps(S, Packages, Upgrade, Seen, State1, Locks), + {AllApps++PkgApps, State2}. find_cycles(Apps) -> case rebar_digraph:compile_order(Apps) of @@ -199,24 +213,6 @@ find_cycles(Apps) -> cull_compile(TopSortedDeps, ProjectApps) -> lists:dropwhile(fun not_needs_compile/1, TopSortedDeps -- ProjectApps). -update_pkg_deps(Profile, Packages, PkgDeps, Graph, Upgrade, Seen, State, Locks, Level) -> - case PkgDeps of - [] -> %% No pkg deps - {[], State}; - PkgDeps -> - %% Find pkg deps needed - S = case rebar_digraph:cull_deps(Graph, PkgDeps, Level) of - {ok, [], _} -> - throw({rebar_digraph, no_solution}); - {ok, Solution, []} -> - Solution; - {ok, Solution, Discarded} -> - [warn_skip_pkg(Pkg, State) || Pkg <- Discarded, not(pkg_locked(Pkg, Locks))], - Solution - end, - update_pkg_deps(Profile, S, Packages, Upgrade, Seen, State, Locks) - end. - pkg_locked({Name, _, _}, Locks) -> pkg_locked(Name, Locks); pkg_locked({Name, _}, Locks) -> @@ -224,11 +220,10 @@ pkg_locked({Name, _}, Locks) -> pkg_locked(Name, Locks) -> false =/= lists:keyfind(Name, 1, Locks). -update_pkg_deps(Profile, Pkgs, Packages, Upgrade, Seen, State, Locks) -> - %% Create app_info record for each pkg dep - DepsDir = profile_dep_dir(State, Profile), +update_pkg_deps(Pkgs, Packages, Upgrade, Seen, State, Locks) -> {Solved, _, State1} - = lists:foldl(fun(Pkg, {Acc, SeenAcc, StateAcc}) -> + = lists:foldl(fun({Profile, Pkg}, {Acc, SeenAcc, StateAcc}) -> + DepsDir = profile_dep_dir(State, Profile), handle_pkg_dep(Profile, Pkg, Packages, Upgrade, DepsDir, Acc, SeenAcc, Locks, StateAcc) end, {[], Seen, State}, Pkgs), {Solved, State1}. diff --git a/src/rebar_prv_lock.erl b/src/rebar_prv_lock.erl index 1844934..80ac784 100644 --- a/src/rebar_prv_lock.erl +++ b/src/rebar_prv_lock.erl @@ -30,7 +30,7 @@ init(State) -> -spec do(rebar_state:t()) -> {ok, rebar_state:t()} | {error, string()}. do(State) -> OldLocks = rebar_state:get(State, {locks, default}, []), - Locks = build_locks(State), + Locks = lists:keysort(1, build_locks(State)), Dir = rebar_state:dir(State), file:write_file(filename:join(Dir, ?LOCK_FILE), io_lib:format("~p.~n", [Locks])), -- cgit v1.1