%% -*- erlang-indent-level: 4; indent-tabs-mode: nil; fill-column: 80 -*- %% ex: ts=4 sw=4 et %% %% 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. %% %% @author Eric Merritt %% %%%------------------------------------------------------------------- %%% @doc %%% This is a dependency constraint solver. You add your 'world' to the %%% solver. That is the packages that exist, their versions and their %%% dependencies. Then give the system a set of targets and ask it to solve. %%% %%% Lets say our world looks as follows %%% %%% app1 that has versions "0.1" %%% depends on app3 any version greater then "0.2" %%% "0.2" with no dependencies %%% "0.3" with no dependencies %%% %%% app2 that has versions "0.1" with no dependencies %%% "0.2" that depends on app3 exactly "0.3" %%% "0.3" with no dependencies %%% %%% app3 that has versions %%% "0.1", "0.2" and "0.3" all with no dependencies %%% %%% we can add this world to the system all at once as follows %%% %%% Graph0 = rlx_depsolver:new_graph(), %%% Graph1 = rlx_depsolver:add_packages( %%% [{app1, [{"0.1", [{app2, "0.2"}, %%% {app3, "0.2", '>='}]}, %%% {"0.2", []}, %%% {"0.3", []}]}, %%% {app2, [{"0.1", []}, %%% {"0.2",[{app3, "0.3"}]}, %%% {"0.3", []}]}, %%% {app3, [{"0.1", []}, %%% {"0.2", []}, %%% {"0.3", []}]}]). %%% %%% We can also build it up incrementally using the other add_package and %%% add_package_version functions. %%% %%% Finally, once we have built up the graph we can ask rlx_depsolver to solve the %%% dependency constraints. That is to give us a list of valid dependencies by %%% using the solve function. Lets say we want the app3 version "0.3" and all of %%% its resolved dependencies. We could call solve as follows. %%% %%% rlx_depsolver:solve(Graph1, [{app3, "0.3"}]). %%% %%% That will give us the completely resolved dependencies including app3 %%% itself. Lets be a little more flexible. Lets ask for a graph that is rooted %%% in anything greater then or equal to app3 "0.3". We could do that by %%% %%% rlx_depsolver:solve(Graph1, [{app3, "0.3", '>='}]). %%% %%% Of course, you can specify any number of goals at the top level. %%% @end %%%------------------------------------------------------------------- -module(rlx_depsolver). %% Public Api -export([format_error/1, format_roots/1, format_culprits/1, format_constraint/1, format_version/1, new_graph/0, solve/2, add_packages/2, add_package/3, add_package_version/3, add_package_version/4, parse_version/1, is_valid_raw_constraint/1, filter_packages/2]). %% Internally Exported API. This should *not* be used outside of the rlx_depsolver %% application. You have been warned. -export([dep_pkg/1, filter_package/2, primitive_solve/3]). -export_type([t/0, pkg/0, constraint_op/0, raw_constraint/0, pkg_name/0, vsn/0, constraint/0, dependency_set/0]). -export_type([dep_graph/0, constraints/0, ordered_constraints/0, fail_info/0, fail_detail/0]). %%============================================================================ %% type %%============================================================================ -ifdef(namespaced_types). -type dep_graph() :: gb_trees:tree(). -else. -type dep_graph() :: gb_tree(). -endif. -opaque t() :: {?MODULE, dep_graph()}. -type pkg() :: {pkg_name(), vsn()}. -type pkg_name() :: string() | binary() | atom(). -type raw_vsn() :: ec_semver:any_version(). -type vsn() :: 'NO_VSN' | ec_semver:semver(). -type constraint_op() :: '=' | gte | '>=' | lte | '<=' | gt | '>' | lt | '<' | pes | '~>' | between. -type raw_constraint() :: pkg_name() | {pkg_name(), raw_vsn()} | {pkg_name(), raw_vsn(), constraint_op()} | {pkg_name(), raw_vsn(), raw_vsn(), between}. -type constraint() :: pkg_name() | {pkg_name(), vsn()} | {pkg_name(), vsn(), constraint_op()} | {pkg_name(), vsn(), vsn(), between}. -type vsn_constraint() :: {raw_vsn(), [raw_constraint()]}. -type dependency_set() :: {pkg_name(), [vsn_constraint()]}. %% Internal Types -type constraints() :: [constraint()]. -type ordered_constraints() :: [{pkg_name(), constraints()}]. -type fail_info() :: {[pkg()], ordered_constraints()}. -type fail_detail() :: {fail, [fail_info()]}. -type version_checker() :: fun((vsn()) -> fail_detail() | vsn()). %%============================================================================ %% API %%============================================================================ %% @doc create a new empty dependency graph -spec new_graph() -> t(). new_graph() -> {?MODULE, gb_trees:empty()}. %% @doc add a complete set of list of packages to the graph. Where the package %% consists of the name and a list of versions and dependencies. %% %% ``` rlx_depsolver:add_packages(Graph, %% [{app1, [{"0.1", [{app2, "0.2"}, %% {app3, "0.2", '>='}]}, %% {"0.2", []}, %% {"0.3", []}]}, %% {app2, [{"0.1", []}, %% {"0.2",[{app3, "0.3"}]}, %% {"0.3", []}]}, %% {app3, [{"0.1", []}, %% {"0.2", []}, %% {"0.3", []}]}]) %% ''' -spec add_packages(t(),[dependency_set()]) -> t(). add_packages(Dom0, Info) when is_list(Info) -> lists:foldl(fun({Pkg, VsnInfo}, Dom1) -> add_package(Dom1, Pkg, VsnInfo) end, Dom0, Info). %% @doc add a single package to the graph, where it consists of a package name %% and its versions and thier dependencies. %% ```rlx_depsolver:add_package(Graph, app1, [{"0.1", [{app2, "0.2"}, %% {app3, "0.2", '>='}]}, %% {"0.2", []}, %% {"0.3", []}]}]). %% ''' -spec add_package(t(),pkg_name(),[vsn_constraint()]) -> t(). add_package(State, Pkg, Versions) when is_list(Versions) -> lists:foldl(fun({Vsn, Constraints}, Dom1) -> add_package_version(Dom1, Pkg, Vsn, Constraints); (Version, Dom1) -> add_package_version(Dom1, Pkg, Version, []) end, State, Versions). %% @doc add a set of dependencies to a specific package and version. %% and its versions and thier dependencies. %% ```rlx_depsolver:add_package(Graph, app1, "0.1", [{app2, "0.2"}, %% {app3, "0.2", '>='}]}, %% {"0.2", []}, %% {"0.3", []}]). %% ''' -spec add_package_version(t(), pkg_name(), raw_vsn(), [raw_constraint()]) -> t(). add_package_version({?MODULE, Dom0}, RawPkg, RawVsn, RawPkgConstraints) -> Pkg = fix_pkg(RawPkg), Vsn = parse_version(RawVsn), %% Incoming constraints are raw %% and need to be fixed PkgConstraints = [fix_con(PkgConstraint) || PkgConstraint <- RawPkgConstraints], Info2 = case gb_trees:lookup(Pkg, Dom0) of {value, Info0} -> %% Sort Vsns from greatest to lowest lists:reverse( lists:sort(fun(X, Y) -> ec_semver:lte(element(1, X), element(1, Y)) end, case lists:keytake(Vsn, 1, Info0) of {value, {Vsn, Constraints}, Info1} -> [{Vsn, join_constraints(Constraints, PkgConstraints)} | Info1]; false -> [{Vsn, PkgConstraints} | Info0] end)); none -> [{Vsn, PkgConstraints}] end, {?MODULE, gb_trees:enter(Pkg, Info2, Dom0)}. %% @doc add a package and version to the dependency graph with no dependency %% constraints, dependency constraints can always be added after the fact. %% %% ```rlx_depsolver:add_package_version(Graph, app1, "0.1").''' -spec add_package_version(t(),pkg_name(),raw_vsn()) -> t(). add_package_version(State, Pkg, Vsn) -> add_package_version(State, Pkg, Vsn, []). %% @doc Given a set of goals (in the form of constrains) find a set of packages %% and versions that satisfy all constraints. If no solution can be found then %% an exception is thrown. %% ``` rlx_depsolver:solve(State, [{app1, "0.1", '>='}]).''' -spec solve(t(),[constraint()]) -> {ok, [pkg()]} | {error, term()}. solve({?MODULE, DepGraph0}, RawGoals) when erlang:length(RawGoals) > 0 -> Goals = [fix_con(Goal) || Goal <- RawGoals], case trim_unreachable_packages(DepGraph0, Goals) of Error = {error, _} -> Error; DepGraph1 -> case primitive_solve(DepGraph1, Goals, no_path) of {fail, _} -> [FirstCons | Rest] = Goals, {error, rlx_depsolver_culprit:search(DepGraph1, [FirstCons], Rest)}; Solution -> {ok, Solution} end end. %% @doc Parse a string version into a tuple based version -spec parse_version(raw_vsn() | vsn()) -> vsn(). parse_version(RawVsn) when erlang:is_list(RawVsn); erlang:is_binary(RawVsn) -> ec_semver:parse(RawVsn); parse_version(Vsn) when erlang:is_tuple(Vsn) ; erlang:is_atom(Vsn) -> Vsn. -spec is_valid_raw_constraint(raw_constraint()) -> true; (any()) -> false. is_valid_raw_constraint(RawConstraint) -> try fix_con(RawConstraint) of Constraint -> is_valid_constraint(Constraint) catch error:function_clause -> false end. %% @doc given a list of package name version pairs, and a list of constraints %% return every member of that list that matches all constraints. -spec filter_packages([{pkg_name(), raw_vsn()}], [raw_constraint()]) -> {ok, [{pkg_name(), raw_vsn()}]} | {error, Reason::term()}. filter_packages(PVPairs, RawConstraints) -> Constraints = [fix_con(Constraint) || Constraint <- RawConstraints], case check_constraints(Constraints) of ok -> {ok, [PVPair || PVPair <- PVPairs, filter_pvpair_by_constraint(fix_con(PVPair), Constraints)]}; Error -> Error end. %% @doc Produce a full error message for a given error condition. This includes %% details of the paths taken to resolve the dependencies and shows which dependencies %% could not be satisfied -spec format_error({error, {unreachable_package, list()} | {invalid_constraints, [constraint()]} | list()}) -> iolist(). format_error(Error) -> rlx_depsolver_culprit:format_error(Error). %% @doc Return a formatted list of roots of the dependency trees which %% could not be satisified. These may also have versions attached. %% Example: %% %% ```(foo = 1.2.0), bar``` %% -spec format_roots([constraints()]) -> iolist(). format_roots(Roots) -> rlx_depsolver_culprit:format_roots(Roots). %% @doc Return a formatted list of the culprit depenedencies which led to %% the dependencies not being satisfied. Example: %% %% ```(foo = 1.2.0) -> (bar > 2.0.0)``` -spec format_culprits([{[constraint()], [constraint()]}]) -> iolist(). format_culprits(Culprits) -> rlx_depsolver_culprit:format_culprits(Culprits). %% @doc A formatted version tuple -spec format_version(vsn()) -> iolist(). format_version('NO_VSN') -> ""; format_version(Version) -> rlx_depsolver_culprit:format_version(Version). %% @doc A formatted constraint tuple -spec format_constraint(raw_constraint()) -> iolist(). format_constraint(RawConstraint) -> rlx_depsolver_culprit:format_constraint(fix_con(RawConstraint)). %%==================================================================== %% Internal Functions %%==================================================================== -spec check_constraints(constraints()) -> ok | {error, {invalid_constraints, [term()]}}. check_constraints(Constraints) -> PossibleInvalids = lists:foldl(fun(Constraint, InvalidConstraints) -> case is_valid_constraint(Constraint) of true -> InvalidConstraints; false -> [Constraint | InvalidConstraints] end end, [], Constraints), case PossibleInvalids of [] -> ok; _ -> {error, {invalid_constraints, PossibleInvalids}} end. -spec filter_pvpair_by_constraint({pkg_name(), vsn()}, [constraint()]) -> boolean(). filter_pvpair_by_constraint(PVPair, Constraints) -> lists:all(fun(Constraint) -> filter_package(PVPair, Constraint) end, Constraints). -spec filter_package({pkg_name(), vsn()}, constraint()) -> boolean(). filter_package({PkgName, Vsn}, C = {PkgName, _}) -> is_version_within_constraint(Vsn, C); filter_package({PkgName, Vsn}, C = {PkgName, _, _}) -> is_version_within_constraint(Vsn, C); filter_package({PkgName, Vsn}, C = {PkgName, _, _, _}) -> is_version_within_constraint(Vsn, C); filter_package(_, _) -> %% If its not explicitly excluded its included true. %% @doc %% fix the package name. If its a list turn it into a binary otherwise leave it as an atom fix_pkg(Pkg) when is_list(Pkg) -> erlang:list_to_binary(Pkg); fix_pkg(Pkg) when is_binary(Pkg); is_atom(Pkg) -> Pkg. %% @doc %% fix package. Take a package with a possible invalid version and fix it. -spec fix_con(raw_constraint()) -> constraint(). fix_con({Pkg, Vsn}) -> {fix_pkg(Pkg), parse_version(Vsn)}; fix_con({Pkg, Vsn, CI}) -> {fix_pkg(Pkg), parse_version(Vsn), CI}; fix_con({Pkg, Vsn1, Vsn2, CI}) -> {fix_pkg(Pkg), parse_version(Vsn1), parse_version(Vsn2), CI}; fix_con(Pkg) -> fix_pkg(Pkg). %% @doc given two lists of constraints join them in such a way that no %% constraint is duplicated but the over all order of the constraints is %% preserved. Order drives priority in this solver and is important for that %% reason. -spec join_constraints([constraint()], [constraint()]) -> [constraint()]. join_constraints(NewConstraints, ExistingConstraints) -> ECSet = sets:from_list(ExistingConstraints), FilteredNewConstraints = [NC || NC <- NewConstraints, not sets:is_element(NC, ECSet)], ExistingConstraints ++ FilteredNewConstraints. %% @doc constraints is an associated list keeping track of all the constraints %% that have been placed on a package -spec new_constraints() -> constraints(). new_constraints() -> []. %% @doc Given a dep graph and a set of goals this either solves the problem or %% fails. This is basically the root solver of the system, the main difference %% from the exported solve/2 function is the fact that this does not do the %% culprit search. -spec primitive_solve(dep_graph(),[constraint()], term()) -> [pkg()] | fail_detail(). primitive_solve(State, PackageList, PathInd) when erlang:length(PackageList) > 0 -> Constraints = lists:foldl(fun(Info, Acc) -> add_constraint('_GOAL_', 'NO_VSN', Acc, Info) end, new_constraints(), PackageList), Pkgs = lists:map(fun dep_pkg/1, PackageList), all_pkgs(State, [], Pkgs, Constraints, PathInd). %% @doc %% given a Pkg | {Pkg, Vsn} | {Pkg, Vsn, Constraint} return Pkg -spec dep_pkg(constraint()) -> pkg_name(). dep_pkg({Pkg, _Vsn}) -> Pkg; dep_pkg({Pkg, _Vsn, _}) -> Pkg; dep_pkg({Pkg, _Vsn1, _Vsn2, _}) -> Pkg; dep_pkg(Pkg) when is_atom(Pkg) orelse is_binary(Pkg) -> Pkg. -spec is_valid_constraint(constraint()) -> boolean(). is_valid_constraint(Pkg) when is_atom(Pkg) orelse is_binary(Pkg) -> true; is_valid_constraint({_Pkg, Vsn}) when is_tuple(Vsn) -> true; is_valid_constraint({_Pkg, Vsn, '='}) when is_tuple(Vsn) -> true; is_valid_constraint({_Pkg, _LVsn, gte}) -> true; is_valid_constraint({_Pkg, _LVsn, '>='}) -> true; is_valid_constraint({_Pkg, _LVsn, lte}) -> true; is_valid_constraint({_Pkg, _LVsn, '<='}) -> true; is_valid_constraint({_Pkg, _LVsn, gt}) -> true; is_valid_constraint({_Pkg, _LVsn, '>'}) -> true; is_valid_constraint({_Pkg, _LVsn, lt}) -> true; is_valid_constraint({_Pkg, _LVsn, '<'}) -> true; is_valid_constraint({_Pkg, _LVsn, pes}) -> true; is_valid_constraint({_Pkg, _LVsn, '~>'}) -> true; is_valid_constraint({_Pkg, _LVsn1, _LVsn2, between}) -> true; is_valid_constraint(_InvalidConstraint) -> false. -spec add_constraint(pkg_name(), vsn(), [constraint()],constraint()) -> ordered_constraints(). add_constraint(SrcPkg, SrcVsn, PkgsConstraints, PkgConstraint) -> case is_valid_constraint(PkgConstraint) of true -> ok; false -> erlang:throw({invalid_constraint, PkgConstraint}) end, PkgName = dep_pkg(PkgConstraint), Constraints1 = case lists:keysearch(PkgName, 1, PkgsConstraints) of false -> []; {value, {PkgName, Constraints0}} -> Constraints0 end, lists:keydelete(PkgName, 1, PkgsConstraints)++[{PkgName, [{PkgConstraint, {SrcPkg, SrcVsn}} | Constraints1]}]. %% @doc %% Extend the currently active constraints correctly for the given constraints. -spec extend_constraints(pkg_name(), vsn(), constraints(),constraints()) -> [{pkg_name(), constraints()}]. extend_constraints(SrcPkg, SrcVsn, ExistingConstraints0, NewConstraints) -> lists:foldl(fun (Constraint, ExistingConstraints1) -> add_constraint(SrcPkg, SrcVsn, ExistingConstraints1, Constraint) end, ExistingConstraints0, [{SrcPkg, SrcVsn} | NewConstraints]). -spec is_version_within_constraint(vsn(),constraint()) -> boolean(). is_version_within_constraint(_Vsn, Pkg) when is_atom(Pkg) orelse is_binary(Pkg) -> true; is_version_within_constraint(Vsn, {_Pkg, NVsn}) -> ec_semver:eql(Vsn, NVsn); is_version_within_constraint(Vsn, {_Pkg, NVsn, '='}) -> ec_semver:eql(Vsn, NVsn); is_version_within_constraint(Vsn, {_Pkg, LVsn, gte}) -> ec_semver:gte(Vsn, LVsn); is_version_within_constraint(Vsn, {_Pkg, LVsn, '>='}) -> ec_semver:gte(Vsn, LVsn); is_version_within_constraint(Vsn, {_Pkg, LVsn, lte}) -> ec_semver:lte(Vsn, LVsn); is_version_within_constraint(Vsn, {_Pkg, LVsn, '<='}) -> ec_semver:lte(Vsn, LVsn); is_version_within_constraint(Vsn, {_Pkg, LVsn, gt}) -> ec_semver:gt(Vsn, LVsn); is_version_within_constraint(Vsn, {_Pkg, LVsn, '>'}) -> ec_semver:gt(Vsn, LVsn); is_version_within_constraint(Vsn, {_Pkg, LVsn, lt}) -> ec_semver:lt(Vsn, LVsn); is_version_within_constraint(Vsn, {_Pkg, LVsn, '<'}) -> ec_semver:lt(Vsn, LVsn); is_version_within_constraint(Vsn, {_Pkg, LVsn, 'pes'}) -> ec_semver:pes(Vsn, LVsn); is_version_within_constraint(Vsn, {_Pkg, LVsn, '~>'}) -> ec_semver:pes(Vsn, LVsn); is_version_within_constraint(Vsn, {_Pkg, LVsn1, LVsn2, between}) -> ec_semver:between(LVsn1, LVsn2, Vsn); is_version_within_constraint(_Vsn, _Pkg) -> false. %% @doc %% Get the currently active constraints that relate to the specified package -spec get_constraints([{pkg_name(), constraints()}],pkg_name()) -> constraints(). get_constraints(PkgsConstraints, PkgName) -> case lists:keysearch(PkgName, 1, PkgsConstraints) of false -> []; {value, {PkgName, Constraints}} -> Constraints end. %% @doc %% Given a package name get the list of all versions available for that package. -spec get_versions(dep_graph(),pkg_name()) -> [vsn()]. get_versions(DepGraph, PkgName) -> case gb_trees:lookup(PkgName, DepGraph) of none -> []; {value, AllVsns} -> [Vsn || {Vsn, _} <- AllVsns] end. %% @doc %% make sure a given name/vsn meets all current constraints -spec valid_version(pkg_name(),vsn(),constraints()) -> boolean(). valid_version(PkgName, Vsn, PkgConstraints) -> lists:all(fun ({L, _ConstraintSrc}) -> is_version_within_constraint(Vsn, L) end, get_constraints(PkgConstraints, PkgName)). %% @doc %% Given a Package Name and a set of constraints get a list of package %% versions that meet all constraints. -spec constrained_package_versions(dep_graph(),pkg_name(),constraints()) -> [vsn()]. constrained_package_versions(State, PkgName, PkgConstraints) -> Versions = get_versions(State, PkgName), [Vsn || Vsn <- Versions, valid_version(PkgName, Vsn, PkgConstraints)]. %% Given a list of constraints filter said list such that only fail (for things %% that do not match a package and pkg are returned. Since at the end only pkg() %% we should have a pure list of packages. -spec filter_package_constraints([constraint()]) -> fail | pkg(). filter_package_constraints([]) -> fail; filter_package_constraints([PkgCon | PkgConstraints]) -> case PkgCon of {Pkg, _} when is_atom(Pkg); is_binary(Pkg) -> filter_package_constraints(PkgConstraints); {{_Pkg1, _Vsn} = PV, _} -> PV; {{_Pkg2, _Vsn, _R}, _} -> filter_package_constraints(PkgConstraints); {{_Pkg2, _Vsn1, _Vsn2, _R}, _} -> filter_package_constraints(PkgConstraints) end. %% @doc all_pkgs is one of the set of mutually recursive functions (all_pkgs and %% pkgs) that serve to walk the solution space of dependency. -spec all_pkgs(dep_graph(),[pkg()],[pkg_name()],[{pkg_name(), constraints()}], term()) -> fail_detail() | [pkg()]. all_pkgs(_State, Visited, [], Constraints, _PathInd) -> PkgVsns = [filter_package_constraints(PkgConstraints) || {_, PkgConstraints} <- Constraints], %% PkgVsns should be a list of pkg() where all the constraints are correctly %% met. If not we fail the solution. If so we return those pkg()s case lists:all(fun({Pkg, Vsn}) -> lists:all(fun({Constraint, _}) -> is_version_within_constraint(Vsn, Constraint) end, get_constraints(Constraints, Pkg)) end, PkgVsns) of true -> PkgVsns; false -> {fail, [{Visited, Constraints}]} end; all_pkgs(State, Visited, [PkgName | PkgNames], Constraints, PathInd) when is_atom(PkgName); is_binary(PkgName) -> case lists:keymember(PkgName, 1, Visited) of true -> all_pkgs(State, Visited, PkgNames, Constraints, PathInd); false -> pkgs(State, Visited, PkgName, Constraints, PkgNames, PathInd) end. %% @doc this is the key graph walker. Set of constraints it walks forward into %% the solution space searching for a path that solves all dependencies. -spec pkgs(dep_graph(),[pkg()], pkg_name(), [{pkg_name(), constraints()}], [pkg_name()], term()) -> fail_detail() | [pkg()]. pkgs(DepGraph, Visited, Pkg, Constraints, OtherPkgs, PathInd) -> F = fun (Vsn) -> Deps = get_dep_constraints(DepGraph, Pkg, Vsn), UConstraints = extend_constraints(Pkg, Vsn, Constraints, Deps), DepPkgs = [dep_pkg(Dep) || Dep <- Deps], NewVisited = [{Pkg, Vsn} | Visited], Res = all_pkgs(DepGraph, NewVisited, DepPkgs ++ OtherPkgs, UConstraints, PathInd), Res end, case constrained_package_versions(DepGraph, Pkg, Constraints) of [] -> {fail, [{Visited, Constraints}]}; Res -> lists_some(F, Res, PathInd) end. %% @doc This gathers the dependency constraints for a given package vsn from the %% dependency graph. -spec get_dep_constraints(dep_graph(), pkg_name(), vsn()) -> [constraint()]. get_dep_constraints(DepGraph, PkgName, Vsn) -> {Vsn, Constraints} = lists:keyfind(Vsn, 1, gb_trees:get(PkgName, DepGraph)), Constraints. lists_some(F, Res, PathInd) -> lists_some(F, Res, [], PathInd). -spec lists_some(version_checker(), [vsn()], term(), term()) -> vsn() | fail_detail(). %% @doc lists_some is the root of the system the actual backtracing search that %% makes the dep solver posible. It a takes a function that checks whether the %% 'problem' has been solved and an fail indicator. As long as the evaluator %% returns the fail indicator processing continues. If the evaluator returns %% anything but the fail indicator that indicates success. lists_some(_, [], FailPaths, _PathInd) -> {fail, FailPaths}; lists_some(F, [H | T], FailPaths, PathInd) -> case F(H) of {fail, FailPath} -> case PathInd of keep_paths -> lists_some(F, T, [FailPath | FailPaths], PathInd); _ -> lists_some(F, T, [], PathInd) end; Res -> Res end. %% @doc given a graph and a set of top level goals return a graph that contains %% only those top level packages and those packages that might be required by %% those packages. -spec trim_unreachable_packages(dep_graph(), [constraint()]) -> dep_graph() | {error, term()}. trim_unreachable_packages(State, Goals) -> {_, NewState0} = new_graph(), lists:foldl(fun(_Pkg, Error={error, _}) -> Error; (Pkg, NewState1) -> PkgName = dep_pkg(Pkg), find_reachable_packages(State, NewState1, PkgName) end, NewState0, Goals). %% @doc given a list of versions and the constraints for that version rewrite %% the new graph to reflect the requirements of those versions. -spec rewrite_vsns(dep_graph(), dep_graph(), [{vsn(), [constraint()]}]) -> dep_graph() | {error, term()}. rewrite_vsns(ExistingGraph, NewGraph0, Info) -> lists:foldl(fun(_, Error={error, _}) -> Error; ({_Vsn, Constraints}, NewGraph1) -> lists:foldl(fun(_DepPkg, Error={error, _}) -> Error; (DepPkg, NewGraph2) -> DepPkgName = dep_pkg(DepPkg), find_reachable_packages(ExistingGraph, NewGraph2, DepPkgName) end, NewGraph1, Constraints) end, NewGraph0, Info). %% @doc Rewrite the existing dep graph removing anything that is not reachable %% required by the goals or any of its potential dependencies. -spec find_reachable_packages(dep_graph(), dep_graph(), pkg_name()) -> dep_graph() | {error, term()}. find_reachable_packages(_ExistingGraph, Error={error, _}, _PkgName) -> Error; find_reachable_packages(ExistingGraph, NewGraph0, PkgName) -> case contains_package_version(NewGraph0, PkgName) of true -> NewGraph0; false -> case gb_trees:lookup(PkgName, ExistingGraph) of {value, Info} -> NewGraph1 = gb_trees:insert(PkgName, Info, NewGraph0), rewrite_vsns(ExistingGraph, NewGraph1, Info); none -> {error, {unreachable_package, PkgName}} end end. %% @doc %% Checks to see if a package name has been defined in the dependency graph -spec contains_package_version(dep_graph(), pkg_name()) -> boolean(). contains_package_version(Dom0, PkgName) -> gb_trees:is_defined(PkgName, Dom0).