add depsolver directly to the system

This is sub-optimal but I suspect rcl_depsolver is going to migrate
away from depsolver in any case.

8 files changed, 1101 insertions, 24 deletions

diff --git a/src/rcl_app_info.erl b/src/rcl_app_info.erl
index db32a8f..d0192e6 100644
--- a/src/rcl_app_info.erl
+++ b/src/rcl_app_info.erl
@@ -157,7 +157,7 @@ format(AppInfo) ->
 -spec format(non_neg_integer(), t()) -> iolist().
 format(Indent, #app_info_t{name=Name, vsn=Vsn, dir=Dir,
                            active_deps=Deps, library_deps=LibDeps}) ->
-    [rcl_util:indent(Indent), erlang:atom_to_list(Name), "-", depsolver:format_version(Vsn),
+    [rcl_util:indent(Indent), erlang:atom_to_list(Name), "-", ec_semver:format(Vsn),
      ": ", Dir, "\n",
      rcl_util:indent(Indent + 1), "Active Dependencies:\n",
      [[rcl_util:indent(Indent + 2), erlang:atom_to_list(Dep), ",\n"] || Dep <- Deps],
diff --git a/src/rcl_cmd_args.erl b/src/rcl_cmd_args.erl
index 201a7af..f12d216 100644
--- a/src/rcl_cmd_args.erl
+++ b/src/rcl_cmd_args.erl
@@ -127,11 +127,11 @@ create_goals(Opts, Acc) ->
             create_output_dir(Opts, [{goals, Specs} | Acc])
     end.
 
--spec convert_goals([string()], [depsolver:constraint()]) ->
-                           {ok,[depsolver:constraint()]} |
+-spec convert_goals([string()], [rcl_depsolver:constraint()]) ->
+                           {ok,[rcl_depsolver:constraint()]} |
                            relcool:error().
 convert_goals([], Specs) ->
-    %% Reverse the specs because order matters to depsolver
+    %% Reverse the specs because order matters to rcl_depsolver
     {ok, lists:reverse(Specs)};
 convert_goals([RawSpec | Rest], Acc) ->
     case rcl_goal:parse(RawSpec) of
diff --git a/src/rcl_depsolver.erl b/src/rcl_depsolver.erl
new file mode 100644
index 0000000..4d61d6c
--- /dev/null
+++ b/src/rcl_depsolver.erl
@@ -0,0 +1,714 @@
+%% -*- erlang-indent-level: 4; indent-tabs-mode: nil; fill-column: 80 -*-
+%% ex: ts=4 sx=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 <[email protected]>
+%%
+%%%-------------------------------------------------------------------
+%%% @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 = rcl_depsolver:new_graph(),
+%%%      Graph1 = rcl_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 rcl_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.
+%%%
+%%%    rcl_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
+%%%
+%%%    rcl_depsolver:solve(Graph1, [{app3, "0.3", '>='}]).
+%%%
+%%% Of course, you can specify any number of goals at the top level.
+%%% @end
+%%%-------------------------------------------------------------------
+-module(rcl_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,
+         filter_packages/2]).
+
+%% Internally Exported API. This should *not* be used outside of the rcl_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,
+              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
+%%============================================================================
+-type dep_graph() :: gb_tree().
+-opaque t() :: {?MODULE, dep_graph()}.
+-type pkg() :: {pkg_name(), vsn()}.
+-type pkg_name() :: 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(), 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.
+%%
+%% ``` rcl_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.
+%%  ```rcl_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.
+%%  ```rcl_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} ->
+                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.
+%%
+%% ```rcl_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.
+%% ``` rcl_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, rcl_depsolver_culprit:search(DepGraph1, [FirstCons], Rest)};
+                Solution ->
+                    {ok, Solution}
+            end
+    end.
+
+%% 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) ->
+    Vsn.
+
+%% @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) ->
+    rcl_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) ->
+    rcl_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) ->
+    rcl_depsolver_culprit:format_culprits(Culprits).
+
+%% @doc A formatted version tuple
+-spec format_version(vsn()) -> iolist().
+format_version(Version) ->
+    rcl_depsolver_culprit:format_version(Version).
+
+%% @doc A formatted constraint tuple
+-spec format_constraint(constraint()) -> iolist().
+format_constraint(Constraint) ->
+    rcl_depsolver_culprit:format_constraint(Constraint).
+
+%%====================================================================
+%% 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,
+    [{PkgName, [{PkgConstraint, {SrcPkg, SrcVsn}} | Constraints1]} |
+     lists:keydelete(PkgName, 1, PkgsConstraints)].
+
+%% @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).
diff --git a/src/rcl_depsolver_culprit.erl b/src/rcl_depsolver_culprit.erl
new file mode 100644
index 0000000..f2115c7
--- /dev/null
+++ b/src/rcl_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, []), ""].
diff --git a/src/rcl_goal_utils.erl b/src/rcl_goal_utils.erl
index 213a87d..3627b9c 100644
--- a/src/rcl_goal_utils.erl
+++ b/src/rcl_goal_utils.erl
@@ -32,7 +32,7 @@
 %%============================================================================
 %% API
 %%============================================================================
--spec to_op(iolist()) -> depsolver:constraint_op().
+-spec to_op(iolist()) -> rcl_depsolver:constraint_op().
 to_op(List)
   when erlang:is_list(List) ->
     to_op(erlang:iolist_to_binary(List));
@@ -70,7 +70,7 @@ to_op(<<":between:">>) ->
 to_vsn(Version) when erlang:is_list(Version) ->
     to_vsn(erlang:iolist_to_binary(Version));
 to_vsn(Vsn) ->
-    depsolver:parse_version(Vsn).
+    rcl_depsolver:parse_version(Vsn).
 
 %%%===================================================================
 %%% Test Functions
diff --git a/src/rcl_prv_release.erl b/src/rcl_prv_release.erl
index 0d692da..0d2e1d7 100644
--- a/src/rcl_prv_release.erl
+++ b/src/rcl_prv_release.erl
@@ -63,28 +63,28 @@ format_error({release_not_found, {RelName, RelVsn}}) ->
     io_lib:format("No releases exist in the system for ~p:~s!", [RelName, RelVsn]);
 format_error({failed_solve, Error}) ->
     io_lib:format("Failed to solve release:\n ~s",
-                  [depsolver:format_error({error, Error})]).
+                  [rcl_depsolver:format_error({error, Error})]).
 
 %%%===================================================================
 %%% Internal Functions
 %%%===================================================================
--spec create_dep_graph(rcl_state:t()) -> depsolver:t().
+-spec create_dep_graph(rcl_state:t()) -> rcl_depsolver:t().
 create_dep_graph(State) ->
     Apps = rcl_state:available_apps(State),
-    Graph0 = depsolver:new_graph(),
+    Graph0 = rcl_depsolver:new_graph(),
     lists:foldl(fun(App, Graph1) ->
                         AppName = rcl_app_info:name(App),
                         AppVsn = rcl_app_info:vsn(App),
                         Deps = rcl_app_info:active_deps(App) ++
                             rcl_app_info:library_deps(App),
-                        depsolver:add_package_version(Graph1,
+                        rcl_depsolver:add_package_version(Graph1,
                                                       AppName,
                                                       AppVsn,
                                                       Deps)
                 end, Graph0, Apps).
 
 
--spec find_default_release(rcl_state:t(), depsolver:t()) ->
+-spec find_default_release(rcl_state:t(), rcl_depsolver:t()) ->
                                   {ok, rcl_state:t()} | relcool:error().
 find_default_release(State, DepGraph) ->
     case rcl_state:default_release(State) of
@@ -151,7 +151,7 @@ solve_release(State0, DepGraph, RelName, RelVsn) ->
     try
         Release = rcl_state:get_release(State0, RelName, RelVsn),
         Goals = rcl_release:goals(Release),
-        case depsolver:solve(DepGraph, Goals) of
+        case rcl_depsolver:solve(DepGraph, Goals) of
             {ok, Pkgs} ->
                 set_resolved(State0, Release, Pkgs);
             {error, Error} ->
diff --git a/src/rcl_release.erl b/src/rcl_release.erl
index c8e52fc..9dbb866 100644
--- a/src/rcl_release.erl
+++ b/src/rcl_release.erl
@@ -32,6 +32,7 @@
          realize/3,
          applications/1,
          application_details/1,
+         realized/1,
          format/1,
          format/2,
          format_error/1]).
@@ -50,7 +51,7 @@
 -record(release_t, {name :: atom(),
                     vsn :: ec_semver:any_version(),
                     erts :: ec_semver:any_version(),
-                    goals = [] :: [depsolver:constraint()],
+                    goals = [] :: [rcl_depsolver:constraint()],
                     realized = false :: boolean(),
                     annotations = undefined :: annotations(),
                     applications = [] ::  [application_spec()],
@@ -70,9 +71,9 @@
                             {app_name(), app_vsn(), app_type() | incl_apps()} |
                             {app_name(), app_vsn(), app_type(), incl_apps()}.
 
--type application_goal() :: depsolver:constraint() |
-                            {depsolver:constraint(), app_type() | incl_apps()} |
-                            {depsolver:constraint(), app_type(), incl_apps()}.
+-type application_goal() :: rcl_depsolver:constraint() |
+                            {rcl_depsolver:constraint(), app_type() | incl_apps()} |
+                            {rcl_depsolver:constraint(), app_type(), incl_apps()}.
 
 -type annotations() ::  ec_dictionary:dictionary(app_name(),
                                                  {app_type(), incl_apps() | none}).
@@ -137,6 +138,9 @@ applications(#release_t{applications=Apps}) ->
 application_details(#release_t{app_detail=App}) ->
     App.
 
+-spec realized(t()) -> boolean().
+realized(#release_t{realized=Realized}) ->
+    Realized.
 
 -spec format(t()) -> iolist().
 format(Release) ->
@@ -161,11 +165,11 @@ format(Indent, #release_t{name=Name, vsn=Vsn, erts=ErtsVsn, realized=Realized,
      end].
 -spec format_goal(application_goal()) -> iolist().
 format_goal({Constraint, AppType}) ->
-    io_lib:format("~p", [{depsolver:format_constraint(Constraint), AppType}]);
+    io_lib:format("~p", [{rcl_depsolver:format_constraint(Constraint), AppType}]);
 format_goal({Constraint, AppType, AppInc}) ->
-    io_lib:format("~p", [{depsolver:format_constraint(Constraint), AppType, AppInc}]);
+    io_lib:format("~p", [{rcl_depsolver:format_constraint(Constraint), AppType, AppInc}]);
 format_goal(Constraint) ->
-    depsolver:format_constraint(Constraint).
+    rcl_depsolver:format_constraint(Constraint).
 
 -spec format_error(Reason::term()) -> iolist().
 format_error({topo_error, E}) ->
@@ -277,7 +281,7 @@ parse_goal0(Constraint0, {ok, Release = #release_t{goals=Goals}})
 parse_goal0(_, E = {error, _}) ->
     E.
 
--spec parse_goal1(t(), depsolver:constraint() | string(),
+-spec parse_goal1(t(), rcl_depsolver:constraint() | string(),
                   app_type() | incl_apps() | {app_type(), incl_apps() | none}) ->
                          {ok, t()} | relcool:error().
 parse_goal1(Release = #release_t{annotations=Annots,  goals=Goals},
@@ -296,7 +300,7 @@ parse_goal1(Release = #release_t{annotations=Annots,  goals=Goals},
            end
    end.
 
--spec get_app_name(depsolver:constraint()) ->
+-spec get_app_name(rcl_depsolver:constraint()) ->
                           AppName::atom() | relcool:error().
 get_app_name(AppName) when erlang:is_atom(AppName) ->
     AppName;
diff --git a/src/rcl_state.erl b/src/rcl_state.erl
index 2dd0b14..7526c1c 100644
--- a/src/rcl_state.erl
+++ b/src/rcl_state.erl
@@ -57,7 +57,7 @@
                   output_dir :: file:name(),
                   lib_dirs=[] :: [file:name()],
                   config_files=[] :: [file:filename()],
-                  goals=[] :: [depsolver:constraint()],
+                  goals=[] :: [rcl_depsolver:constraint()],
                   providers = [] :: [rcl_provider:t()],
                   available_apps = [] :: [rcl_app_info:t()],
                   default_release :: {rcl_release:name(), rcl_release:vsn()},
@@ -110,7 +110,7 @@ output_dir(#state_t{output_dir=OutDir}) ->
 lib_dirs(#state_t{lib_dirs=LibDir}) ->
     LibDir.
 
--spec goals(t()) -> [depsolver:constraints()].
+-spec goals(t()) -> [rcl_depsolver:constraints()].
 goals(#state_t{goals=TS}) ->
     TS.
 
@@ -210,7 +210,7 @@ format(#state_t{log=LogState, output_dir=OutDir, lib_dirs=LibDirs,
      rcl_util:indent(Indent + 1), "config files: \n",
      [[rcl_util:indent(Indent + 2), ConfigFile, ",\n"] || ConfigFile <- ConfigFiles],
      rcl_util:indent(Indent + 1), "goals: \n",
-     [[rcl_util:indent(Indent + 2), depsolver:format_constraint(Goal), ",\n"] || Goal <- Goals],
+     [[rcl_util:indent(Indent + 2), rcl_depsolver:format_constraint(Goal), ",\n"] || Goal <- Goals],
      rcl_util:indent(Indent + 1), "output_dir: ", OutDir, "\n",
      rcl_util:indent(Indent + 1), "lib_dirs: \n",
      [[rcl_util:indent(Indent + 2), LibDir, ",\n"] || LibDir <- LibDirs],