diff options
Diffstat (limited to 'src/rlx_depsolver_culprit.erl')
-rw-r--r-- | src/rlx_depsolver_culprit.erl | 359 |
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, []), ""]. |