Basic file rename from rcl to rlx

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, []), ""].