summaryrefslogtreecommitdiff
path: root/src/rebar_digraph.erl
diff options
context:
space:
mode:
Diffstat (limited to 'src/rebar_digraph.erl')
-rw-r--r--src/rebar_digraph.erl139
1 files changed, 87 insertions, 52 deletions
diff --git a/src/rebar_digraph.erl b/src/rebar_digraph.erl
index 1132a6c..f2bb540 100644
--- a/src/rebar_digraph.erl
+++ b/src/rebar_digraph.erl
@@ -3,6 +3,7 @@
-export([compile_order/1
,restore_graph/1
,cull_deps/2
+ ,cull_deps/3
,subgraph/2
,format_error/1]).
@@ -69,8 +70,12 @@ 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) ->
- {Solution, Levels} = build_initial_dicts(Vertices),
- cull_deps(Graph, Vertices, Levels, Solution, []).
+ 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.", []).
@@ -79,79 +84,109 @@ format_error(no_solution) ->
%% Internal Functions
%%====================================================================
-cull_deps(_Graph, [], Levels, Solution, Discarded) ->
+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],
+ 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, Discarded) ->
+cull_deps(Graph, [{Profile, Level, Vs} | Vertices], Levels, Solution, Seen, Discarded) ->
{NV, NS, LS, DS} =
- lists:foldl(fun({_, Name, Vsn}, {Acc, SolutionAcc, LevelsAcc, DiscardedAcc}) ->
- OutNeighbors = lists:keysort(1, digraph:out_neighbours(Graph, {Name,Vsn})),
- handle_neighbors(Profile, Level, Name
- ,OutNeighbors, Acc, SolutionAcc
- ,LevelsAcc, DiscardedAcc)
-
- end, {[], Solution, Levels, Discarded}, lists:keysort(2, Vs)),
-
- cull_deps(Graph, Vertices++NV, LS, NS, 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, _}) when P =:= Profile
+ , L =:= Level ->
+ true;
+ (_) ->
+ false
+ 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, Levels, Discarded) ->
- case lists:foldl(fun({Name, _}=N, {NewVertices, Solution1, Levels1, Discarded1}) ->
- maybe_add_to_solution(Profile, Level, Name, N, Parent
- ,NewVertices, Solution1
- ,Levels1, Discarded1)
- 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}
+ ,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
- ,Vertices ,Solution, Levels, Discarded) ->
+ ,Solution, Levels, Seen, Discarded) ->
case dict:find(Key, Solution) of
{ok, {Profile, {Parent, Name, Vsn}}} -> % already seen
- {Vertices,
- Solution,
+ {Solution,
Levels,
Discarded};
{ok, _} -> % conflict resolution!
- {Vertices,
- Solution,
+ %% Warn on different version
+ {Solution,
Levels,
[Value|Discarded]};
error ->
- {[{Parent, Name, Vsn} | Vertices],
- dict:store(Key, {Profile, {Parent, Name, Vsn}}, Solution),
- dict:store(Key, Level+1, Levels),
- Discarded}
+ %% 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).
-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({Parent, Key, Vsn}, {SAcc, LAcc}) ->
- {maybe_add_to_dict(Key, {Profile, {Parent,Key,Vsn}}, SAcc),
- maybe_add_to_dict(Key, Level, LAcc)}
- end, {Solution, Levels}, Vs)
- end, {dict:new(), dict:new()}, 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].
generated by cgit v1.1 at 2025-12-17 21:13:35 +0000