install package deps in same level/profile order as src deps

4 files changed, 130 insertions, 93 deletions

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])),