aboutsummaryrefslogtreecommitdiffstats
path: root/src/rlx_depsolver_culprit.erl
diff options
context:
space:
mode:
Diffstat (limited to 'src/rlx_depsolver_culprit.erl')
-rw-r--r--src/rlx_depsolver_culprit.erl359
1 files changed, 359 insertions, 0 deletions
diff --git a/src/rlx_depsolver_culprit.erl b/src/rlx_depsolver_culprit.erl
new file mode 100644
index 0000000..f2115c7
--- /dev/null
+++ b/src/rlx_depsolver_culprit.erl
@@ -0,0 +1,359 @@
+%% -*- erlang-indent-level: 4; indent-tabs-mode: nil; fill-column: 80 -*-
+%% ex: ts=4 sx=4 et
+%%
+%% @author Eric Merritt <[email protected]>
+%%
+%% Copyright 2012 Opscode, Inc. All Rights Reserved.
+%%
+%% This file is provided to you under the Apache License,
+%% Version 2.0 (the "License"); you may not use this file
+%% except in compliance with the License. You may obtain
+%% a copy of the License at
+%%
+%% http://www.apache.org/licenses/LICENSE-2.0
+%%
+%% Unless required by applicable law or agreed to in writing,
+%% software distributed under the License is distributed on an
+%% "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+%% KIND, either express or implied. See the License for the
+%% specific language governing permissions and limitations
+%% under the License.
+%%
+%%%-------------------------------------------------------------------
+%%% @doc
+%%% This app does the culprit search for a failed solve. It searches
+%%% through the goals provided by the user trying to find the first one
+%%% that fails. It then returns that as the culprit along with the
+%%% unknown apps from the goal, the version constrained apps from the
+%%% goal, and the good apps (those not immediately constrained from
+%%% the goals).
+%%% @end
+-module(rcl_depsolver_culprit).
+
+-export([search/3,
+ format_error/1,
+ format_version/1,
+ format_constraint/1,
+ format_roots/1,
+ format_culprits/1]).
+
+%%============================================================================
+%% Types
+%%============================================================================
+
+%%============================================================================
+%% Internal API
+%%============================================================================
+%% @doc start running the solver, with each run reduce the number of constraints
+%% set as goals. At some point the solver should succeed.
+-spec search(rcl_depsolver:dep_graph(), [rcl_depsolver:constraint()], [rcl_depsolver:constraint()])
+ -> term().
+search(State, ActiveCons, []) ->
+ case rcl_depsolver:primitive_solve(State, ActiveCons, keep_paths) of
+ {fail, FailPaths} ->
+ extract_culprit_information0(ActiveCons, lists:flatten(FailPaths));
+ _Success ->
+ %% This should *never* happen. 'Culprit' above represents the last
+ %% possible constraint that could cause things to fail. There for
+ %% this should have failed as well.
+ inconsistant_graph_state
+ end;
+search(State, ActiveCons, [NewCon | Constraints]) ->
+ case rcl_depsolver:primitive_solve(State, ActiveCons, keep_paths) of
+ {fail, FailPaths} ->
+ extract_culprit_information0(ActiveCons, lists:flatten(FailPaths));
+ _Success ->
+ %% Move one constraint from the inactive to the active
+ %% constraints and run again
+ search(State, [NewCon | ActiveCons], Constraints)
+ end.
+
+format_error({error, {unreachable_package, AppName}}) ->
+ ["Dependency ", format_constraint(AppName), " is specified as a dependency ",
+ "but is not reachable by the system.\n"];
+format_error({error, {invalid_constraints, Constraints}}) ->
+ ["Invalid constraint ", add_s(Constraints), " specified ",
+ lists:foldl(fun(Con, "") ->
+ [io_lib:format("~p", [Con])];
+ (Con, Acc) ->
+ [io_lib:format("~p", [Con]), ", " | Acc]
+ end, "", Constraints)];
+format_error({error, Detail}) ->
+ format_error(Detail);
+format_error(Details) when erlang:is_list(Details) ->
+ ["Unable to solve constraints, the following solutions were attempted \n\n",
+ [[format_error_path(" ", Detail)] || Detail <- Details]].
+
+-spec format_roots([rcl_depsolver:constraints()]) -> iolist().
+format_roots(Roots) ->
+ lists:foldl(fun(Root, Acc0) ->
+ lists:foldl(
+ fun(Con, "") ->
+ [format_constraint(Con)];
+ (Con, Acc1) ->
+ [format_constraint(Con), ", " | Acc1]
+ end, Acc0, Root)
+ end, [], Roots).
+
+-spec format_culprits([{[rcl_depsolver:constraint()], [rcl_depsolver:constraint()]}]) -> iolist().
+format_culprits(FailingDeps) ->
+ Deps = sets:to_list(sets:from_list(lists:flatten([[rcl_depsolver:dep_pkg(Con) || Con <- Cons]
+ || {_, Cons} <- FailingDeps]))),
+ lists:foldl(fun(Con, "") ->
+ [format_constraint(Con)];
+ (Con, Acc1) ->
+ [format_constraint(Con),
+ ", " | Acc1]
+ end, [], Deps).
+
+-spec format_version(rcl_depsolver:vsn()) -> iolist().
+format_version(Vsn) ->
+ ec_semver:format(Vsn).
+
+-spec format_constraint(rcl_depsolver:constraint()) -> list().
+format_constraint(Pkg) when is_atom(Pkg) ->
+ erlang:atom_to_list(Pkg);
+format_constraint(Pkg) when is_binary(Pkg) ->
+ erlang:binary_to_list(Pkg);
+format_constraint({Pkg, Vsn}) when is_tuple(Vsn) ->
+ ["(", format_constraint(Pkg), " = ",
+ format_version(Vsn), ")"];
+format_constraint({Pkg, Vsn, '='}) when is_tuple(Vsn) ->
+ ["(", format_constraint(Pkg), " = ",
+ format_version(Vsn), ")"];
+format_constraint({Pkg, Vsn, gte}) ->
+ ["(", format_constraint(Pkg), " >= ",
+ format_version(Vsn), ")"];
+format_constraint({Pkg, Vsn, '>='}) ->
+ ["(", format_constraint(Pkg), " >= ",
+ format_version(Vsn), ")"];
+format_constraint({Pkg, Vsn, lte}) ->
+ ["(", format_constraint(Pkg), " <= ",
+ format_version(Vsn), ")"];
+format_constraint({Pkg, Vsn, '<='}) ->
+ ["(", format_constraint(Pkg), " <= ",
+ format_version(Vsn), ")"];
+format_constraint({Pkg, Vsn, gt}) ->
+ ["(", format_constraint(Pkg), " > ",
+ format_version(Vsn), ")"];
+format_constraint({Pkg, Vsn, '>'}) ->
+ ["(", format_constraint(Pkg), " > ",
+ format_version(Vsn), ")"];
+format_constraint({Pkg, Vsn, lt}) ->
+ ["(", format_constraint(Pkg), " < ",
+ format_version(Vsn), ")"];
+format_constraint({Pkg, Vsn, '<'}) ->
+ ["(", format_constraint(Pkg), " < ",
+ format_version(Vsn), ")"];
+format_constraint({Pkg, Vsn, pes}) ->
+ ["(", format_constraint(Pkg), " ~> ",
+ format_version(Vsn), ")"];
+format_constraint({Pkg, Vsn, '~>'}) ->
+ ["(", format_constraint(Pkg), " ~> ",
+ format_version(Vsn), ")"];
+format_constraint({Pkg, Vsn1, Vsn2, between}) ->
+ ["(", format_constraint(Pkg), " between ",
+ format_version(Vsn1), " and ",
+ format_version(Vsn2), ")"].
+
+
+%%============================================================================
+%% Internal Functions
+%%============================================================================
+-spec append_value(term(), term(), proplists:proplist()) -> proplists:proplist().
+append_value(Key, Value, PropList) ->
+ case proplists:get_value(Key, PropList, undefined) of
+ undefined ->
+ [{Key, Value} | PropList];
+ ExistingValue ->
+ [{Key, sets:to_list(sets:from_list([Value | ExistingValue]))} |
+ proplists:delete(Key, PropList)]
+ end.
+
+-spec strip_goal([[rcl_depsolver:pkg()] | rcl_depsolver:pkg()]) ->
+ [[rcl_depsolver:pkg()] | rcl_depsolver:pkg()].
+strip_goal([{'_GOAL_', 'NO_VSN'}, Children]) ->
+ Children;
+strip_goal(All = [Val | _])
+ when erlang:is_list(Val) ->
+ [strip_goal(Element) || Element <- All];
+strip_goal(Else) ->
+ Else.
+
+-spec extract_culprit_information0(rcl_depsolver:constraints(),
+ [rcl_depsolver:fail_info()]) ->
+ [term()].
+extract_culprit_information0(ActiveCons, FailInfo)
+ when is_list(FailInfo) ->
+ [extract_culprit_information1(ActiveCons, FI) || FI <- FailInfo].
+
+
+-spec extract_root(rcl_depsolver:constraints(), [rcl_depsolver:pkg()]) ->
+ {[rcl_depsolver:constraint()], [rcl_depsolver:pkg()]}.
+extract_root(ActiveCons, TPath = [PRoot | _]) ->
+ RootName = rcl_depsolver:dep_pkg(PRoot),
+ Roots = lists:filter(fun(El) ->
+ RootName =:= rcl_depsolver:dep_pkg(El)
+ end, ActiveCons),
+ {Roots, TPath}.
+
+-spec extract_culprit_information1(rcl_depsolver:constraints(),
+ rcl_depsolver:fail_info()) ->
+ term().
+extract_culprit_information1(_ActiveCons, {[], RawConstraints}) ->
+ %% In this case where there was no realized versions, the GOAL
+ %% constraints actually where unsatisfiable
+ Constraints = lists:flatten([Constraints ||
+ {_, Constraints} <- RawConstraints]),
+
+ Cons = [Pkg || {Pkg, Src} <- Constraints,
+ Src =:= {'_GOAL_', 'NO_VSN'}],
+ {[{Cons, Cons}], []};
+extract_culprit_information1(ActiveCons, {Path, RawConstraints}) ->
+ Constraints = lists:flatten([Constraints ||
+ {_, Constraints} <- RawConstraints]),
+ FailCons =
+ lists:foldl(fun(El = {FailedPkg, FailedVsn}, Acc1) ->
+ case get_constraints(FailedPkg, FailedVsn, Path,
+ Constraints) of
+ [] ->
+ Acc1;
+ Cons ->
+ append_value(El, Cons, Acc1)
+ end
+ end, [], lists:reverse(Path)),
+ TreedPath = strip_goal(treeize_path({'_GOAL_', 'NO_VSN'}, Constraints, [])),
+ RunListItems = [extract_root(ActiveCons, TPath) || TPath <- TreedPath],
+ {RunListItems, FailCons}.
+
+-spec follow_chain(rcl_depsolver:pkg_name(), rcl_depsolver:vsn(),
+ {rcl_depsolver:constraint(), rcl_depsolver:pkg()}) ->
+ false | {ok, rcl_depsolver:constraint()}.
+follow_chain(Pkg, Vsn, {{Pkg, Vsn}, {Pkg, Vsn}}) ->
+ %% When the package version is the same as the source we dont want to try to follow it at all
+ false;
+follow_chain(Pkg, Vsn, {Con, {Pkg, Vsn}}) ->
+ {ok, Con};
+follow_chain(_Pkg, _Vsn, _) ->
+ false.
+
+-spec find_chain(rcl_depsolver:pkg_name(), rcl_depsolver:vsn(),
+ [{rcl_depsolver:constraint(), rcl_depsolver:pkg()}]) ->
+ rcl_depsolver:constraints().
+find_chain(Pkg, Vsn, Constraints) ->
+ lists:foldl(fun(NCon, Acc) ->
+ case follow_chain(Pkg, Vsn, NCon) of
+ {ok, Con} ->
+ [Con | Acc];
+ false ->
+ Acc
+ end
+ end, [], Constraints).
+
+-spec get_constraints(rcl_depsolver:pkg_name(), rcl_depsolver:vsn(), [rcl_depsolver:pkg()],
+ [{rcl_depsolver:constraint(), rcl_depsolver:pkg()}]) ->
+ rcl_depsolver:constraints().
+get_constraints(FailedPkg, FailedVsn, Path, Constraints) ->
+ Chain = find_chain(FailedPkg, FailedVsn, Constraints),
+ lists:filter(fun(Con) ->
+ PkgName = rcl_depsolver:dep_pkg(Con),
+ (lists:any(fun(PathEl) ->
+ not rcl_depsolver:filter_package(PathEl, Con)
+ end, Path) orelse
+ not lists:keymember(PkgName, 1, Path))
+ end, Chain).
+
+-spec pkg_vsn(rcl_depsolver:constraint(), [{rcl_depsolver:constraint(),
+ rcl_depsolver:pkg()}]) ->
+ [rcl_depsolver:pkg()].
+pkg_vsn(PkgCon, Constraints) ->
+ PkgName = rcl_depsolver:dep_pkg(PkgCon),
+ [DepPkg || Con = {DepPkg, _} <- Constraints,
+ case Con of
+ {Pkg = {PkgName, PkgVsn}, {PkgName, PkgVsn}} ->
+ rcl_depsolver:filter_package(Pkg, PkgCon);
+ _ ->
+ false
+ end].
+
+-spec depends(rcl_depsolver:pkg(), [{rcl_depsolver:constraint(),
+ rcl_depsolver:pkg()}],
+ [rcl_depsolver:pkg()]) ->
+ [rcl_depsolver:pkg()].
+depends(SrcPkg, Constraints, Seen) ->
+ lists:flatten([pkg_vsn(Pkg, Constraints) || {Pkg, Source} <- Constraints,
+ Source =:= SrcPkg andalso
+ Pkg =/= SrcPkg andalso
+ not lists:member(Pkg, Seen)]).
+
+-spec treeize_path(rcl_depsolver:pkg(), [{rcl_depsolver:constraint(),
+ rcl_depsolver:pkg()}],
+ [rcl_depsolver:pkg()]) ->
+ [rcl_depsolver:pkg() | [rcl_depsolver:pkg()]].
+treeize_path(Pkg, Constraints, Seen0) ->
+ Seen1 = [Pkg | Seen0],
+ case depends(Pkg, Constraints, Seen1) of
+ [] ->
+ [Pkg];
+ Deps ->
+ [Pkg, [treeize_path(Dep, Constraints, Seen1) ||
+ Dep <- Deps]]
+
+ end.
+
+-spec add_s(list()) -> iolist().
+add_s(Roots) ->
+ case erlang:length(Roots) of
+ Len when Len > 1 ->
+ "s";
+ _ ->
+ ""
+ end.
+
+-spec format_path(string(), [rcl_depsolver:pkg()]) -> iolist().
+format_path(CurrentIdent, Path) ->
+ [CurrentIdent, " ",
+ lists:foldl(fun(Con, "") ->
+ [format_constraint(Con)];
+ (Con, Acc) ->
+ [format_constraint(Con), " -> " | Acc]
+ end, "", Path),
+ "\n"].
+
+-spec format_dependency_paths(string(), [[rcl_depsolver:pkg()] | rcl_depsolver:pkg()],
+ [{rcl_depsolver:pkg(), [rcl_depsolver:constraint()]}], [rcl_depsolver:pkg()]) -> iolist().
+format_dependency_paths(CurrentIndent, [SubPath | Rest], FailingDeps, Acc)
+ when erlang:is_list(SubPath) ->
+ [format_dependency_paths(CurrentIndent, lists:sort(SubPath), FailingDeps, Acc),
+ format_dependency_paths(CurrentIndent, Rest, FailingDeps, Acc)];
+format_dependency_paths(CurrentIndent, [Dep], FailingDeps, Acc)
+ when erlang:is_tuple(Dep) ->
+ case proplists:get_value(Dep, FailingDeps, undefined) of
+ undefined ->
+ format_path(CurrentIndent, [Dep | Acc]);
+ Cons ->
+ [format_path(CurrentIndent, [Con, Dep | Acc]) || Con <- Cons]
+ end;
+format_dependency_paths(CurrentIndent, [Dep | Rest], FailingDeps, Acc)
+ when erlang:is_tuple(Dep) ->
+ case proplists:get_value(Dep, FailingDeps, undefined) of
+ undefined ->
+ format_dependency_paths(CurrentIndent, Rest, FailingDeps, [Dep | Acc]);
+ Cons ->
+ [[format_path(CurrentIndent, [Con, Dep | Acc]) || Con <- Cons],
+ format_dependency_paths(CurrentIndent, Rest, FailingDeps, [Dep | Acc])]
+ end;
+format_dependency_paths(CurrentIndent, [Con | Rest], FailingDeps, Acc) ->
+ format_dependency_paths(CurrentIndent, Rest, FailingDeps, [Con | Acc]);
+format_dependency_paths(_CurrentIndent, [], _FailingDeps, _Acc) ->
+ [].
+
+-spec format_error_path(string(), {[{[rcl_depsolver:constraint()], [rcl_depsolver:pkg()]}],
+ [rcl_depsolver:constraint()]}) -> iolist().
+format_error_path(CurrentIndent, {RawPaths, FailingDeps}) ->
+ Roots = [RootSet || {RootSet, _} <- RawPaths],
+ Paths = [Path || {_, Path} <- RawPaths],
+ [CurrentIndent, "Unable to satisfy goal constraint",
+ add_s(Roots), " ", format_roots(Roots), " due to constraint", add_s(FailingDeps), " on ",
+ format_culprits(FailingDeps), "\n",
+ format_dependency_paths(CurrentIndent, lists:sort(Paths), FailingDeps, []), ""].