Adding pkg deps tests and refactorings

- Adding tests for package deps
- Adding conflict/override warnings for package deps
- Adding cycle detection for packages
- Adding cycle detection for mixed packages+source
- Fixing internal dependency format of package resources when converted
  to rebar_app_info
- normalizing level-order prioritization to be based on lexicographical
  sort of app names rather than traversal order (which is undefined for
  package deps)
- Fixing tests for source deps for deep cycle detection
- Fixing bugs with source deps
- Relaxed version format checks for test utils

A lot of fixes are combined in there because I didn't want to commit
non-passing code, and many bugs were found when adding the second batch
of tests as part of the original effort.

2 files changed, 55 insertions, 32 deletions

diff --git a/src/rebar_digraph.erl b/src/rebar_digraph.erl
index dbcf649..55d7272 100644
--- a/src/rebar_digraph.erl
+++ b/src/rebar_digraph.erl
@@ -69,27 +69,31 @@ restore_graph({Vs, Es}) ->
 %% 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, lists:foldl(fun({Key, _}=N, Solution) ->
-                                               dict:store(Key, N, Solution)
-                                       end, dict:new(), Vertices)).
+    cull_deps(Graph,
+              Vertices,
+              lists:foldl(fun({Key, _}=N, Solution) -> dict:store(Key, N, Solution) end,
+                          dict:new(), Vertices),
+              []).
 
-cull_deps(_Graph, [], Solution) ->
+cull_deps(_Graph, [], Solution, Discarded) ->
     {_, Vertices} = lists:unzip(dict:to_list(Solution)),
-    {ok, Vertices};
-cull_deps(Graph, Vertices, Solution) ->
-    {NV, NS} =
-        lists:foldl(fun(V, {NewVertices, SolutionAcc}) ->
+    {ok, Vertices, Discarded};
+cull_deps(Graph, Vertices, Solution, Discarded) ->
+    {NV, NS, DS} =
+        lists:foldl(fun(V, {NewVertices, SolutionAcc, DiscardedAcc}) ->
                         OutNeighbors = digraph:out_neighbours(Graph, V),
-                        lists:foldl(fun({Key, _}=N, {NewVertices1, SolutionAcc1}) ->
-                                            case dict:is_key(Key, SolutionAcc1) of
-                                                true ->
-                                                    {NewVertices1, SolutionAcc1};
-                                                false ->
-                                                    {[N | NewVertices1], dict:store(Key, N, SolutionAcc1)}
+                        lists:foldl(fun({Key, _}=N, {NewVertices1, SolutionAcc1, DiscardedAcc1}) ->
+                                            case dict:find(Key, SolutionAcc1) of
+                                                {ok, N} -> % already seen
+                                                    {NewVertices1, SolutionAcc1, DiscardedAcc1};
+                                                {ok, _} -> % conflict resolution!
+                                                    {NewVertices1, SolutionAcc1, [N|DiscardedAcc1]};
+                                                error ->
+                                                    {[N | NewVertices1], dict:store(Key, N, SolutionAcc1), DiscardedAcc1}
                                             end
-                                    end, {NewVertices, SolutionAcc}, OutNeighbors)
-                    end, {[], Solution}, Vertices),
-    cull_deps(Graph, NV, NS).
+                                    end, {NewVertices, SolutionAcc, DiscardedAcc}, OutNeighbors)
+                    end, {[], Solution, Discarded}, lists:sort(Vertices)),
+    cull_deps(Graph, NV, NS, DS).
 
 subgraph(Graph, Vertices) ->
     digraph_utils:subgraph(Graph, Vertices).
diff --git a/src/rebar_prv_install_deps.erl b/src/rebar_prv_install_deps.erl
index 5878e8c..3728b70 100644
--- a/src/rebar_prv_install_deps.erl
+++ b/src/rebar_prv_install_deps.erl
@@ -81,15 +81,20 @@ do(State) ->
                                 end,
 
         Source = ProjectApps ++ SrcApps,
-        case rebar_digraph:compile_order(Source) of
-            {ok, Sort} ->
-                {ok, rebar_state:deps_to_build(State1,
-                                              lists:dropwhile(fun rebar_app_info:valid/1
-                                                             , Sort -- ProjectApps))};
-            {error, {cycles, Cycles}} ->
+        case find_cycles(Source ++ rebar_state:all_deps(State1)) of
+            {cycles, Cycles} ->
                 ?PRV_ERROR({cycles, Cycles});
             {error, Error} ->
-                {error, Error}
+                {error, Error};
+            no_cycle ->
+                case rebar_digraph:compile_order(Source) of
+                    {ok, Sort} ->
+                        {ok, rebar_state:deps_to_build(State1,
+                                                    lists:dropwhile(fun rebar_app_info:valid/1,
+                                                                    Sort -- ProjectApps))};
+                    {error, Error} ->
+                        {error, Error}
+                end
         end
     catch
         %% maybe_fetch will maybe_throw an exception to break out of some loops
@@ -97,6 +102,13 @@ do(State) ->
             {error, Reason}
     end.
 
+find_cycles(Apps) ->
+    case rebar_digraph:compile_order(Apps) of
+        {error, {cycles, Cycles}} -> {cycles, Cycles};
+        {error, Error} -> {error, Error};
+        {ok, _} -> no_cycle
+    end.
+
 -spec format_error(any()) -> iolist().
 format_error({cycles, Cycles}) ->
     Prints = [["applications: ",
@@ -119,11 +131,9 @@ handle_deps(State, [], _) ->
 handle_deps(State, Deps, Update) ->
     %% Read in package index and dep graph
     {Packages, Graph} = rebar_packages:get_packages(State),
-
     %% Split source deps from pkg deps, needed to keep backwards compatibility
     DepsDir = rebar_dir:deps_dir(State),
     {SrcDeps, PkgDeps} = parse_deps(State, DepsDir, Deps),
-
     %% Fetch transitive src deps
     {State1, SrcApps, PkgDeps1, Seen} =
         update_src_deps(0, SrcDeps, PkgDeps, [], State, Update, sets:new()),
@@ -134,15 +144,16 @@ handle_deps(State, Deps, Update) ->
                            PkgDeps2 ->
                                %% Find pkg deps needed
                                S = case rebar_digraph:cull_deps(Graph, PkgDeps2) of
-                                       {ok, []} ->
+                                       {ok, [], _} ->
                                            throw({rebar_digraph, no_solution});
-                                       {ok, Solution} ->
+                                       {ok, Solution, []} ->
+                                           Solution;
+                                       {ok, Solution, Discarded} ->
+                                           [warn_skip_pkg(Pkg) || Pkg <- Discarded],
                                            Solution
                                    end,
-
                                update_pkg_deps(S, Packages, Update, Seen, State1)
                        end,
-
     AllDeps = lists:ukeymerge(2
                              ,lists:ukeysort(2, SrcApps)
                              ,lists:ukeysort(2, Solved)),
@@ -193,7 +204,8 @@ package_to_app(DepsDir, Packages, {Name, Vsn}) ->
         error ->
             {error, missing_package};
         {ok, P} ->
-            PkgDeps = proplists:get_value(<<"deps">>, P, []),
+            PkgDeps = [{atom_to_binary(PkgName,utf8), list_to_binary(PkgVsn)}
+                       || {PkgName,PkgVsn} <- proplists:get_value(<<"deps">>, P, [])],
             Link = proplists:get_value(<<"link">>, P, ""),
             {ok, AppInfo} = rebar_app_info:new(Name, Vsn),
             AppInfo1 = rebar_app_info:deps(AppInfo, PkgDeps),
@@ -233,7 +245,9 @@ update_src_deps(Level, SrcDeps, PkgDeps, SrcApps, State, Update, Seen) ->
                                          end,
                                      {SrcDepsAcc1, PkgDepsAcc1, SrcAppsAcc1, StateAcc2, SeenAcc1}
                              end
-                     end, {[], PkgDeps, SrcApps, State, Seen}, SrcDeps) of
+                     end,
+                     {[], PkgDeps, SrcApps, State, Seen},
+                     lists:sort(SrcDeps)) of
         {[], NewPkgDeps, NewSrcApps, State1, Seen1} ->
             {State1, NewSrcApps, NewPkgDeps, Seen1};
         {NewSrcDeps, NewPkgDeps, NewSrcApps, State1, Seen1} ->
@@ -427,3 +441,8 @@ warn_skip_deps(AppInfo) ->
           "has already been fetched~n",
           [rebar_app_info:name(AppInfo),
            rebar_app_info:source(AppInfo)]).
+
+warn_skip_pkg({Name, Source}) ->
+    ?WARN("Skipping ~s (version ~s from package index) as an app of the same "
+          "name has already been fetched~n",
+          [Name, Source]).