aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorAvatar Ciaran McCreesh <ciaran.mccreesh@googlemail.com> 2009-07-29 17:35:27 +0100
committerAvatar Ciaran McCreesh <ciaran.mccreesh@googlemail.com> 2009-07-29 17:35:12 +0100
commit732764e6ddf33421a7003261178fcc72297cecb2 (patch)
tree71f48e04ed32949002dfda64391a534451356912
parentd99dae8f3d05f5afcac04fa7edf446d9020edfb9 (diff)
downloadpaludis-732764e6ddf33421a7003261178fcc72297cecb2.tar.gz
paludis-732764e6ddf33421a7003261178fcc72297cecb2.tar.xz
Merge in stupid incremental resolver
-rw-r--r--configure.ac15
-rw-r--r--paludis/Makefile.am.m42
-rw-r--r--paludis/resolver/Makefile.am62
-rw-r--r--paludis/resolver/arrow-fwd.hh40
-rw-r--r--paludis/resolver/arrow.cc36
-rw-r--r--paludis/resolver/arrow.hh43
-rw-r--r--paludis/resolver/constraint-fwd.hh40
-rw-r--r--paludis/resolver/constraint.cc40
-rw-r--r--paludis/resolver/constraint.hh50
-rw-r--r--paludis/resolver/decision-fwd.hh36
-rw-r--r--paludis/resolver/decision.cc47
-rw-r--r--paludis/resolver/decision.hh53
-rw-r--r--paludis/resolver/qpn_s-fwd.hh38
-rw-r--r--paludis/resolver/qpn_s.cc64
-rw-r--r--paludis/resolver/qpn_s.hh47
-rw-r--r--paludis/resolver/reason-fwd.hh38
-rw-r--r--paludis/resolver/reason.cc114
-rw-r--r--paludis/resolver/reason.hh80
-rw-r--r--paludis/resolver/resolution-fwd.hh36
-rw-r--r--paludis/resolver/resolution.cc45
-rw-r--r--paludis/resolver/resolution.hh52
-rw-r--r--paludis/resolver/resolver-fwd.hh31
-rw-r--r--paludis/resolver/resolver.cc1014
-rw-r--r--paludis/resolver/resolver.hh154
-rw-r--r--paludis/resolver/sanitised_dependencies-fwd.hh37
-rw-r--r--paludis/resolver/sanitised_dependencies.cc518
-rw-r--r--paludis/resolver/sanitised_dependencies.hh76
-rw-r--r--paludis/resolver/use_installed-fwd.hh34
-rw-r--r--paludis/resolver/use_installed.cc29
-rw-r--r--paludis/resolver/use_installed.hh33
-rw-r--r--paludis/resolver/use_installed.se16
-rw-r--r--src/clients/cave/Makefile.am7
-rw-r--r--src/clients/cave/cmd_resolve.cc488
-rw-r--r--src/clients/cave/cmd_resolve.hh46
-rw-r--r--src/clients/cave/command_factory.cc4
35 files changed, 3461 insertions, 4 deletions
diff --git a/configure.ac b/configure.ac
index 74904c1..d91ac4a 100644
--- a/configure.ac
+++ b/configure.ac
@@ -105,6 +105,7 @@ need_xml_check=
need_pcrecpp_check=
need_syck_check=
need_gem_check=
+need_resolver=
dnl {{{ we can use abi::__cxa_demangle
AC_MSG_CHECKING([for abi::__cxa_demangle])
@@ -1445,6 +1446,19 @@ AC_SUBST([BUILD_CLIENTS])
if echo $clients | tr ' ' '\n' | grep '^inquisitio$' >/dev/null ; then
need_pcrecpp_check=yes
fi
+
+if echo $clients | tr ' ' '\n' | grep '^cave$' >/dev/null ; then
+ need_resolver=yes
+fi
+dnl }}}
+
+dnl {{{ new resolver
+
+if test "x$need_resolver" = "xyes" ; then
+ AC_DEFINE([ENABLE_NEW_RESOLVER], [1], [Enable new resolver])
+fi
+AM_CONDITIONAL([ENABLE_NEW_RESOLVER], test "x$need_resolver" = "xyes")
+
dnl }}}
dnl {{{ libxml2 check
@@ -1622,6 +1636,7 @@ AC_OUTPUT(
paludis/repositories/unpackaged/Makefile
paludis/repositories/unwritten/Makefile
paludis/repositories/virtuals/Makefile
+ paludis/resolver/Makefile
paludis/selinux/Makefile
paludis/syncers/Makefile
paludis/util/Makefile
diff --git a/paludis/Makefile.am.m4 b/paludis/Makefile.am.m4
index 7419865..d59805a 100644
--- a/paludis/Makefile.am.m4
+++ b/paludis/Makefile.am.m4
@@ -83,7 +83,7 @@ EXTRA_DIST = about.hh.in Makefile.am.m4 paludis.hh.m4 files.m4 \
testscriptlist srlist srcleanlist selist secleanlist \
hooker.bash \
stripper_TEST_binary.cc
-SUBDIRS = distributions fetchers syncers util selinux . repositories environments args
+SUBDIRS = distributions fetchers syncers util selinux . repositories environments args resolver
BUILT_SOURCES = srcleanlist secleanlist
libpaludis_@PALUDIS_PC_SLOT@_la_SOURCES = filelist
diff --git a/paludis/resolver/Makefile.am b/paludis/resolver/Makefile.am
new file mode 100644
index 0000000..7bf1d9c
--- /dev/null
+++ b/paludis/resolver/Makefile.am
@@ -0,0 +1,62 @@
+CLEANFILES = *~ gmon.out *.gcov *.gcno *.gcda *.loT *.epicfail
+MAINTAINERCLEANFILES = Makefile.in
+DISTCLEANFILES = use_installed-se.hh use_installed-se.cc
+AM_CXXFLAGS = -I$(top_srcdir) @PALUDIS_CXXFLAGS@ @PALUDIS_CXXFLAGS_VISIBILITY@
+EXTRA_DIST = use_installed-se.hh use_installed-se.cc use_installed.se
+BUILT_SOURCES = use_installed-se.hh use_installed-se.cc
+
+TESTS =
+
+noinst_HEADERS = \
+ arrow.hh arrow-fwd.hh \
+ constraint.hh constraint-fwd.hh \
+ decision.hh decision-fwd.hh \
+ qpn_s.hh qpn_s-fwd.hh \
+ reason.hh reason-fwd.hh \
+ resolution.hh resolution-fwd.hh \
+ resolver.hh resolver-fwd.hh \
+ sanitised_dependencies.hh sanitised_dependencies-fwd.hh \
+ use_installed.hh use_installed-fwd.hh use_installed-se.hh
+
+libpaludisresolver_a_SOURCES = \
+ arrow.cc \
+ constraint.cc \
+ decision.cc \
+ qpn_s.cc \
+ reason.cc \
+ resolution.cc \
+ resolver.cc \
+ sanitised_dependencies.cc \
+ use_installed.cc
+
+TESTS_ENVIRONMENT = env PALUDIS_OPTIONS="" \
+ TEST_SCRIPT_DIR="$(srcdir)/" \
+ PALUDIS_REPOSITORY_SO_DIR="$(top_builddir)/paludis/repositories" \
+ PALUDIS_DISTRIBUTION="gentoo" \
+ bash $(top_srcdir)/test/run_test.sh
+
+if ENABLE_NEW_RESOLVER
+noinst_LIBRARIES = libpaludisresolver.a
+endif
+
+check_PROGRAMS = $(TESTS)
+
+built-sources : $(BUILT_SOURCES)
+ for s in `echo $(SUBDIRS) | tr -d .` ; do $(MAKE) -C $$s built-sources || exit 1 ; done
+
+DISTCHECK_DEPS =
+
+distcheck-deps-local : $(DISTCHECK_DEPS)
+
+distcheck-deps : distcheck-deps-subdirs
+
+distcheck-deps-subdirs :
+ for s in $(SUBDIRS) . ; do if test x$$s = x. ; then $(MAKE) distcheck-deps-local || exit 1 ; \
+ else $(MAKE) -C $$s distcheck-deps || exit 1 ; fi ; done
+
+use_installed-se.hh : use_installed.se $(top_srcdir)/misc/make_se.bash
+ if ! $(top_srcdir)/misc/make_se.bash --header $(srcdir)/use_installed.se > $@ ; then rm -f $@ ; exit 1 ; fi
+
+use_installed-se.cc : use_installed.se $(top_srcdir)/misc/make_se.bash
+ if ! $(top_srcdir)/misc/make_se.bash --source $(srcdir)/use_installed.se > $@ ; then rm -f $@ ; exit 1 ; fi
+
diff --git a/paludis/resolver/arrow-fwd.hh b/paludis/resolver/arrow-fwd.hh
new file mode 100644
index 0000000..e36f55d
--- /dev/null
+++ b/paludis/resolver/arrow-fwd.hh
@@ -0,0 +1,40 @@
+/* vim: set sw=4 sts=4 et foldmethod=syntax : */
+
+/*
+ * Copyright (c) 2009 Ciaran McCreesh
+ *
+ * This file is part of the Paludis package manager. Paludis is free software;
+ * you can redistribute it and/or modify it under the terms of the GNU General
+ * Public License version 2, as published by the Free Software Foundation.
+ *
+ * Paludis is distributed in the hope that it will be useful, but WITHOUT ANY
+ * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+ * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
+ * details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * this program; if not, write to the Free Software Foundation, Inc., 59 Temple
+ * Place, Suite 330, Boston, MA 02111-1307 USA
+ */
+
+#ifndef PALUDIS_GUARD_PALUDIS_RESOLVER_ARROW_FWD_HH
+#define PALUDIS_GUARD_PALUDIS_RESOLVER_ARROW_FWD_HH 1
+
+#include <paludis/util/attributes.hh>
+#include <paludis/util/sequence-fwd.hh>
+#include <tr1/memory>
+#include <iosfwd>
+
+namespace paludis
+{
+ namespace resolver
+ {
+ struct Arrow;
+
+ typedef Sequence<std::tr1::shared_ptr<Arrow> > ArrowSequence;
+
+ std::ostream & operator<< (std::ostream & s, const Arrow &) PALUDIS_VISIBLE;
+ }
+}
+
+#endif
diff --git a/paludis/resolver/arrow.cc b/paludis/resolver/arrow.cc
new file mode 100644
index 0000000..d5c6ffa
--- /dev/null
+++ b/paludis/resolver/arrow.cc
@@ -0,0 +1,36 @@
+/* vim: set sw=4 sts=4 et foldmethod=syntax : */
+
+/*
+ * Copyright (c) 2009 Ciaran McCreesh
+ *
+ * This file is part of the Paludis package manager. Paludis is free software;
+ * you can redistribute it and/or modify it under the terms of the GNU General
+ * Public License version 2, as published by the Free Software Foundation.
+ *
+ * Paludis is distributed in the hope that it will be useful, but WITHOUT ANY
+ * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+ * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
+ * details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * this program; if not, write to the Free Software Foundation, Inc., 59 Temple
+ * Place, Suite 330, Boston, MA 02111-1307 USA
+ */
+
+#include <paludis/resolver/arrow.hh>
+#include <paludis/util/sequence-impl.hh>
+#include <paludis/util/wrapped_forward_iterator-impl.hh>
+
+using namespace paludis;
+using namespace paludis::resolver;
+
+std::ostream &
+paludis::resolver::operator<< (std::ostream & s, const Arrow & a)
+{
+ s << a.to_qpn_s();
+ return s;
+}
+
+template class Sequence<std::tr1::shared_ptr<Arrow> >;
+template class WrappedForwardIterator<ArrowSequence::ConstIteratorTag, const std::tr1::shared_ptr<Arrow> >;
+
diff --git a/paludis/resolver/arrow.hh b/paludis/resolver/arrow.hh
new file mode 100644
index 0000000..f0fa08e
--- /dev/null
+++ b/paludis/resolver/arrow.hh
@@ -0,0 +1,43 @@
+/* vim: set sw=4 sts=4 et foldmethod=syntax : */
+
+/*
+ * Copyright (c) 2009 Ciaran McCreesh
+ *
+ * This file is part of the Paludis package manager. Paludis is free software;
+ * you can redistribute it and/or modify it under the terms of the GNU General
+ * Public License version 2, as published by the Free Software Foundation.
+ *
+ * Paludis is distributed in the hope that it will be useful, but WITHOUT ANY
+ * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+ * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
+ * details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * this program; if not, write to the Free Software Foundation, Inc., 59 Temple
+ * Place, Suite 330, Boston, MA 02111-1307 USA
+ */
+
+#ifndef PALUDIS_GUARD_PALUDIS_RESOLVER_ARROW_HH
+#define PALUDIS_GUARD_PALUDIS_RESOLVER_ARROW_HH 1
+
+#include <paludis/resolver/arrow-fwd.hh>
+#include <paludis/resolver/qpn_s.hh>
+#include <paludis/util/named_value.hh>
+
+namespace paludis
+{
+ namespace n
+ {
+ struct to_qpn_s;
+ }
+
+ namespace resolver
+ {
+ struct Arrow
+ {
+ NamedValue<n::to_qpn_s, QPN_S> to_qpn_s;
+ };
+ }
+}
+
+#endif
diff --git a/paludis/resolver/constraint-fwd.hh b/paludis/resolver/constraint-fwd.hh
new file mode 100644
index 0000000..9ee7491
--- /dev/null
+++ b/paludis/resolver/constraint-fwd.hh
@@ -0,0 +1,40 @@
+/* vim: set sw=4 sts=4 et foldmethod=syntax : */
+
+/*
+ * Copyright (c) 2009 Ciaran McCreesh
+ *
+ * This file is part of the Paludis package manager. Paludis is free software;
+ * you can redistribute it and/or modify it under the terms of the GNU General
+ * Public License version 2, as published by the Free Software Foundation.
+ *
+ * Paludis is distributed in the hope that it will be useful, but WITHOUT ANY
+ * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+ * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
+ * details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * this program; if not, write to the Free Software Foundation, Inc., 59 Temple
+ * Place, Suite 330, Boston, MA 02111-1307 USA
+ */
+
+#ifndef PALUDIS_GUARD_PALUDIS_RESOLVER_CONSTRAINT_FWD_HH
+#define PALUDIS_GUARD_PALUDIS_RESOLVER_CONSTRAINT_FWD_HH 1
+
+#include <paludis/util/attributes.hh>
+#include <paludis/util/sequence-fwd.hh>
+#include <tr1/memory>
+#include <iosfwd>
+
+namespace paludis
+{
+ namespace resolver
+ {
+ struct Constraint;
+
+ typedef Sequence<std::tr1::shared_ptr<const Constraint> > ConstraintSequence;
+
+ std::ostream & operator<< (std::ostream & s, const Constraint & c) PALUDIS_VISIBLE;
+ }
+}
+
+#endif
diff --git a/paludis/resolver/constraint.cc b/paludis/resolver/constraint.cc
new file mode 100644
index 0000000..38a537f
--- /dev/null
+++ b/paludis/resolver/constraint.cc
@@ -0,0 +1,40 @@
+/* vim: set sw=4 sts=4 et foldmethod=syntax : */
+
+/*
+ * Copyright (c) 2009 Ciaran McCreesh
+ *
+ * This file is part of the Paludis package manager. Paludis is free software;
+ * you can redistribute it and/or modify it under the terms of the GNU General
+ * Public License version 2, as published by the Free Software Foundation.
+ *
+ * Paludis is distributed in the hope that it will be useful, but WITHOUT ANY
+ * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+ * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
+ * details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * this program; if not, write to the Free Software Foundation, Inc., 59 Temple
+ * Place, Suite 330, Boston, MA 02111-1307 USA
+ */
+
+#include <paludis/resolver/constraint.hh>
+#include <paludis/resolver/reason.hh>
+#include <paludis/util/stringify.hh>
+#include <sstream>
+
+using namespace paludis;
+using namespace paludis::resolver;
+
+std::ostream &
+paludis::resolver::operator<< (std::ostream & s, const Constraint & c)
+{
+ std::stringstream ss;
+ ss << "Constraint(spec: " << c.spec()
+ << "; use_installed: " << stringify(c.use_installed())
+ << "; reason: " << (c.reason() ? stringify(*c.reason()) : "none")
+ << ")";
+ s << ss.str();
+
+ return s;
+}
+
diff --git a/paludis/resolver/constraint.hh b/paludis/resolver/constraint.hh
new file mode 100644
index 0000000..b94d566
--- /dev/null
+++ b/paludis/resolver/constraint.hh
@@ -0,0 +1,50 @@
+/* vim: set sw=4 sts=4 et foldmethod=syntax : */
+
+/*
+ * Copyright (c) 2009 Ciaran McCreesh
+ *
+ * This file is part of the Paludis package manager. Paludis is free software;
+ * you can redistribute it and/or modify it under the terms of the GNU General
+ * Public License version 2, as published by the Free Software Foundation.
+ *
+ * Paludis is distributed in the hope that it will be useful, but WITHOUT ANY
+ * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+ * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
+ * details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * this program; if not, write to the Free Software Foundation, Inc., 59 Temple
+ * Place, Suite 330, Boston, MA 02111-1307 USA
+ */
+
+#ifndef PALUDIS_GUARD_PALUDIS_RESOLVER_CONSTRAINT_HH
+#define PALUDIS_GUARD_PALUDIS_RESOLVER_CONSTRAINT_HH 1
+
+#include <paludis/resolver/constraint-fwd.hh>
+#include <paludis/resolver/reason-fwd.hh>
+#include <paludis/resolver/use_installed-fwd.hh>
+#include <paludis/util/named_value.hh>
+#include <paludis/dep_spec.hh>
+#include <tr1/memory>
+
+namespace paludis
+{
+ namespace n
+ {
+ struct reason;
+ struct spec;
+ struct use_installed;
+ }
+
+ namespace resolver
+ {
+ struct Constraint
+ {
+ NamedValue<n::reason, std::tr1::shared_ptr<const Reason> > reason;
+ NamedValue<n::spec, PackageDepSpec> spec;
+ NamedValue<n::use_installed, UseInstalled> use_installed;
+ };
+ }
+}
+
+#endif
diff --git a/paludis/resolver/decision-fwd.hh b/paludis/resolver/decision-fwd.hh
new file mode 100644
index 0000000..a17c564
--- /dev/null
+++ b/paludis/resolver/decision-fwd.hh
@@ -0,0 +1,36 @@
+/* vim: set sw=4 sts=4 et foldmethod=syntax : */
+
+/*
+ * Copyright (c) 2009 Ciaran McCreesh
+ *
+ * This file is part of the Paludis package manager. Paludis is free software;
+ * you can redistribute it and/or modify it under the terms of the GNU General
+ * Public License version 2, as published by the Free Software Foundation.
+ *
+ * Paludis is distributed in the hope that it will be useful, but WITHOUT ANY
+ * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+ * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
+ * details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * this program; if not, write to the Free Software Foundation, Inc., 59 Temple
+ * Place, Suite 330, Boston, MA 02111-1307 USA
+ */
+
+#ifndef PALUDIS_GUARD_PALUDIS_RESOLVER_DECISION_FWD_HH
+#define PALUDIS_GUARD_PALUDIS_RESOLVER_DECISION_FWD_HH 1
+
+#include <paludis/util/attributes.hh>
+#include <iosfwd>
+
+namespace paludis
+{
+ namespace resolver
+ {
+ struct Decision;
+
+ std::ostream & operator<< (std::ostream & s, const Decision & d) PALUDIS_VISIBLE;
+ }
+}
+
+#endif
diff --git a/paludis/resolver/decision.cc b/paludis/resolver/decision.cc
new file mode 100644
index 0000000..70588af
--- /dev/null
+++ b/paludis/resolver/decision.cc
@@ -0,0 +1,47 @@
+/* vim: set sw=4 sts=4 et foldmethod=syntax : */
+
+/*
+ * Copyright (c) 2009 Ciaran McCreesh
+ *
+ * This file is part of the Paludis package manager. Paludis is free software;
+ * you can redistribute it and/or modify it under the terms of the GNU General
+ * Public License version 2, as published by the Free Software Foundation.
+ *
+ * Paludis is distributed in the hope that it will be useful, but WITHOUT ANY
+ * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+ * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
+ * details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * this program; if not, write to the Free Software Foundation, Inc., 59 Temple
+ * Place, Suite 330, Boston, MA 02111-1307 USA
+ */
+
+#include <paludis/resolver/decision.hh>
+#include <sstream>
+
+using namespace paludis;
+using namespace paludis::resolver;
+
+std::ostream &
+paludis::resolver::operator<< (std::ostream & s, const Decision & d)
+{
+ std::stringstream ss;
+
+ ss << "Decision(" << *d.package_id();
+
+ if (d.is_installed())
+ ss << ", is installed";
+ if (d.is_new())
+ ss << ", is new";
+ if (d.is_same())
+ ss << ", is same";
+ if (d.is_same_version())
+ ss << ", is same version";
+
+ ss << ")";
+
+ s << ss.str();
+ return s;
+}
+
diff --git a/paludis/resolver/decision.hh b/paludis/resolver/decision.hh
new file mode 100644
index 0000000..737cc87
--- /dev/null
+++ b/paludis/resolver/decision.hh
@@ -0,0 +1,53 @@
+/* vim: set sw=4 sts=4 et foldmethod=syntax : */
+
+/*
+ * Copyright (c) 2009 Ciaran McCreesh
+ *
+ * This file is part of the Paludis package manager. Paludis is free software;
+ * you can redistribute it and/or modify it under the terms of the GNU General
+ * Public License version 2, as published by the Free Software Foundation.
+ *
+ * Paludis is distributed in the hope that it will be useful, but WITHOUT ANY
+ * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+ * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
+ * details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * this program; if not, write to the Free Software Foundation, Inc., 59 Temple
+ * Place, Suite 330, Boston, MA 02111-1307 USA
+ */
+
+#ifndef PALUDIS_GUARD_PALUDIS_RESOLVER_DECISION_HH
+#define PALUDIS_GUARD_PALUDIS_RESOLVER_DECISION_HH 1
+
+#include <paludis/resolver/decision-fwd.hh>
+#include <paludis/util/named_value.hh>
+#include <paludis/package_id.hh>
+
+namespace paludis
+{
+ namespace n
+ {
+ struct is_installed;
+ struct is_new;
+ struct is_same;
+ struct is_same_version;
+ struct is_transient;
+ struct package_id;
+ }
+
+ namespace resolver
+ {
+ struct Decision
+ {
+ NamedValue<n::is_installed, bool> is_installed;
+ NamedValue<n::is_new, bool> is_new;
+ NamedValue<n::is_same, bool> is_same;
+ NamedValue<n::is_same_version, bool> is_same_version;
+ NamedValue<n::is_transient, bool> is_transient;
+ NamedValue<n::package_id, std::tr1::shared_ptr<const PackageID> > package_id;
+ };
+ }
+}
+
+#endif
diff --git a/paludis/resolver/qpn_s-fwd.hh b/paludis/resolver/qpn_s-fwd.hh
new file mode 100644
index 0000000..91e4d89
--- /dev/null
+++ b/paludis/resolver/qpn_s-fwd.hh
@@ -0,0 +1,38 @@
+/* vim: set sw=4 sts=4 et foldmethod=syntax : */
+
+/*
+ * Copyright (c) 2009 Ciaran McCreesh
+ *
+ * This file is part of the Paludis package manager. Paludis is free software;
+ * you can redistribute it and/or modify it under the terms of the GNU General
+ * Public License version 2, as published by the Free Software Foundation.
+ *
+ * Paludis is distributed in the hope that it will be useful, but WITHOUT ANY
+ * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+ * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
+ * details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * this program; if not, write to the Free Software Foundation, Inc., 59 Temple
+ * Place, Suite 330, Boston, MA 02111-1307 USA
+ */
+
+#ifndef PALUDIS_GUARD_PALUDIS_RESOLVER_QPN_S_FWD_HH
+#define PALUDIS_GUARD_PALUDIS_RESOLVER_QPN_S_FWD_HH 1
+
+#include <paludis/util/attributes.hh>
+#include <iosfwd>
+
+namespace paludis
+{
+ namespace resolver
+ {
+ struct QPN_S;
+
+ std::ostream & operator<< (std::ostream & s, const QPN_S &) PALUDIS_VISIBLE;
+
+ bool operator< (const QPN_S &, const QPN_S &) PALUDIS_VISIBLE;
+ }
+}
+
+#endif
diff --git a/paludis/resolver/qpn_s.cc b/paludis/resolver/qpn_s.cc
new file mode 100644
index 0000000..f538228
--- /dev/null
+++ b/paludis/resolver/qpn_s.cc
@@ -0,0 +1,64 @@
+/* vim: set sw=4 sts=4 et foldmethod=syntax : */
+
+/*
+ * Copyright (c) 2009 Ciaran McCreesh
+ *
+ * This file is part of the Paludis package manager. Paludis is free software;
+ * you can redistribute it and/or modify it under the terms of the GNU General
+ * Public License version 2, as published by the Free Software Foundation.
+ *
+ * Paludis is distributed in the hope that it will be useful, but WITHOUT ANY
+ * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+ * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
+ * details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * this program; if not, write to the Free Software Foundation, Inc., 59 Temple
+ * Place, Suite 330, Boston, MA 02111-1307 USA
+ */
+
+#include <paludis/resolver/qpn_s.hh>
+#include <sstream>
+
+using namespace paludis;
+using namespace paludis::resolver;
+
+bool
+paludis::resolver::operator< (const QPN_S & lhs, const QPN_S & rhs)
+{
+ if (lhs.package() < rhs.package())
+ return true;
+ if (lhs.package() > rhs.package())
+ return false;
+
+ /* no slot orders before any slot */
+ if (lhs.slot_name_or_null())
+ {
+ if (rhs.slot_name_or_null())
+ return *lhs.slot_name_or_null() < *rhs.slot_name_or_null();
+ else
+ return false;
+ }
+ else
+ {
+ if (rhs.slot_name_or_null())
+ return true;
+ else
+ return false;
+ }
+}
+
+std::ostream &
+paludis::resolver::operator<< (std::ostream & s, const QPN_S & q)
+{
+ std::stringstream ss;
+ ss << q.package();
+ if (q.slot_name_or_null())
+ ss << ":" << *q.slot_name_or_null();
+ else
+ ss << ":(no slot)";
+
+ s << ss.str();
+ return s;
+}
+
diff --git a/paludis/resolver/qpn_s.hh b/paludis/resolver/qpn_s.hh
new file mode 100644
index 0000000..7dea100
--- /dev/null
+++ b/paludis/resolver/qpn_s.hh
@@ -0,0 +1,47 @@
+/* vim: set sw=4 sts=4 et foldmethod=syntax : */
+
+/*
+ * Copyright (c) 2009 Ciaran McCreesh
+ *
+ * This file is part of the Paludis package manager. Paludis is free software;
+ * you can redistribute it and/or modify it under the terms of the GNU General
+ * Public License version 2, as published by the Free Software Foundation.
+ *
+ * Paludis is distributed in the hope that it will be useful, but WITHOUT ANY
+ * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+ * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
+ * details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * this program; if not, write to the Free Software Foundation, Inc., 59 Temple
+ * Place, Suite 330, Boston, MA 02111-1307 USA
+ */
+
+#ifndef PALUDIS_GUARD_PALUDIS_RESOLVER_QPN_S_HH
+#define PALUDIS_GUARD_PALUDIS_RESOLVER_QPN_S_HH 1
+
+#include <paludis/resolver/qpn_s-fwd.hh>
+#include <paludis/util/named_value.hh>
+#include <paludis/name.hh>
+#include <tr1/memory>
+
+namespace paludis
+{
+ namespace n
+ {
+ struct package;
+ struct slot_name_or_null;
+ }
+
+ namespace resolver
+ {
+ struct QPN_S
+ {
+ NamedValue<n::package, QualifiedPackageName> package;
+ NamedValue<n::slot_name_or_null, std::tr1::shared_ptr<const SlotName> > slot_name_or_null;
+ };
+
+ }
+}
+
+#endif
diff --git a/paludis/resolver/reason-fwd.hh b/paludis/resolver/reason-fwd.hh
new file mode 100644
index 0000000..a0ef572
--- /dev/null
+++ b/paludis/resolver/reason-fwd.hh
@@ -0,0 +1,38 @@
+/* vim: set sw=4 sts=4 et foldmethod=syntax : */
+
+/*
+ * Copyright (c) 2009 Ciaran McCreesh
+ *
+ * This file is part of the Paludis package manager. Paludis is free software;
+ * you can redistribute it and/or modify it under the terms of the GNU General
+ * Public License version 2, as published by the Free Software Foundation.
+ *
+ * Paludis is distributed in the hope that it will be useful, but WITHOUT ANY
+ * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+ * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
+ * details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * this program; if not, write to the Free Software Foundation, Inc., 59 Temple
+ * Place, Suite 330, Boston, MA 02111-1307 USA
+ */
+
+#ifndef PALUDIS_GUARD_PALUDIS_RESOLVER_REASON_FWD_HH
+#define PALUDIS_GUARD_PALUDIS_RESOLVER_REASON_FWD_HH 1
+
+#include <paludis/util/attributes.hh>
+#include <iosfwd>
+
+namespace paludis
+{
+ namespace resolver
+ {
+ struct Reason;
+ struct DependencyReason;
+ struct TargetReason;
+
+ std::ostream & operator<< (std::ostream & s, const Reason &) PALUDIS_VISIBLE;
+ }
+}
+
+#endif
diff --git a/paludis/resolver/reason.cc b/paludis/resolver/reason.cc
new file mode 100644
index 0000000..b668af9
--- /dev/null
+++ b/paludis/resolver/reason.cc
@@ -0,0 +1,114 @@
+/* vim: set sw=4 sts=4 et foldmethod=syntax : */
+
+/*
+ * Copyright (c) 2009 Ciaran McCreesh
+ *
+ * This file is part of the Paludis package manager. Paludis is free software;
+ * you can redistribute it and/or modify it under the terms of the GNU General
+ * Public License version 2, as published by the Free Software Foundation.
+ *
+ * Paludis is distributed in the hope that it will be useful, but WITHOUT ANY
+ * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+ * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
+ * details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * this program; if not, write to the Free Software Foundation, Inc., 59 Temple
+ * Place, Suite 330, Boston, MA 02111-1307 USA
+ */
+
+#include <paludis/resolver/reason.hh>
+#include <paludis/resolver/qpn_s.hh>
+#include <paludis/resolver/sanitised_dependencies.hh>
+#include <paludis/util/stringify.hh>
+#include <paludis/util/private_implementation_pattern-impl.hh>
+
+using namespace paludis;
+using namespace paludis::resolver;
+
+std::ostream &
+paludis::resolver::operator<< (std::ostream & s, const Reason & r)
+{
+ s << r.as_string();
+ return s;
+}
+
+Reason::~Reason()
+{
+}
+
+std::string
+TargetReason::as_string() const
+{
+ return "Target()";
+}
+
+DependencyReason *
+TargetReason::if_dependency_reason()
+{
+ return 0;
+}
+
+const DependencyReason *
+TargetReason::if_dependency_reason() const
+{
+ return 0;
+}
+
+namespace paludis
+{
+ template <>
+ struct Implementation<DependencyReason>
+ {
+ const QPN_S qpn_s;
+ const SanitisedDependency dep;
+
+ Implementation(const QPN_S & q, const SanitisedDependency & d) :
+ qpn_s(q),
+ dep(d)
+ {
+ }
+ };
+}
+
+DependencyReason::DependencyReason(const QPN_S & q, const SanitisedDependency & d) :
+ PrivateImplementationPattern<DependencyReason>(new Implementation<DependencyReason>(q, d))
+{
+}
+
+DependencyReason::~DependencyReason()
+{
+}
+
+const QPN_S
+DependencyReason::qpn_s() const
+{
+ return _imp->qpn_s;
+}
+
+const SanitisedDependency &
+DependencyReason::sanitised_dependency() const
+{
+ return _imp->dep;
+}
+
+std::string
+DependencyReason::as_string() const
+{
+ return "Dependency(package: " + stringify(_imp->qpn_s) + " dep: " + stringify(_imp->dep) + ")";
+}
+
+DependencyReason *
+DependencyReason::if_dependency_reason()
+{
+ return this;
+}
+
+const DependencyReason *
+DependencyReason::if_dependency_reason() const
+{
+ return this;
+}
+
+template class PrivateImplementationPattern<DependencyReason>;
+
diff --git a/paludis/resolver/reason.hh b/paludis/resolver/reason.hh
new file mode 100644
index 0000000..620dd75
--- /dev/null
+++ b/paludis/resolver/reason.hh
@@ -0,0 +1,80 @@
+/* vim: set sw=4 sts=4 et foldmethod=syntax : */
+
+/*
+ * Copyright (c) 2009 Ciaran McCreesh
+ *
+ * This file is part of the Paludis package manager. Paludis is free software;
+ * you can redistribute it and/or modify it under the terms of the GNU General
+ * Public License version 2, as published by the Free Software Foundation.
+ *
+ * Paludis is distributed in the hope that it will be useful, but WITHOUT ANY
+ * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+ * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
+ * details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * this program; if not, write to the Free Software Foundation, Inc., 59 Temple
+ * Place, Suite 330, Boston, MA 02111-1307 USA
+ */
+
+#ifndef PALUDIS_GUARD_PALUDIS_RESOLVER_REASON_HH
+#define PALUDIS_GUARD_PALUDIS_RESOLVER_REASON_HH 1
+
+#include <paludis/resolver/reason-fwd.hh>
+#include <paludis/resolver/qpn_s-fwd.hh>
+#include <paludis/resolver/sanitised_dependencies-fwd.hh>
+#include <paludis/util/private_implementation_pattern.hh>
+
+namespace paludis
+{
+ namespace resolver
+ {
+ class Reason
+ {
+ public:
+ virtual ~Reason() = 0;
+ virtual std::string as_string() const = 0;
+
+ virtual DependencyReason * if_dependency_reason() = 0;
+ virtual const DependencyReason * if_dependency_reason() const = 0;
+ };
+
+ class TargetReason :
+ public Reason
+ {
+ public:
+ virtual std::string as_string() const;
+ virtual DependencyReason * if_dependency_reason();
+ virtual const DependencyReason * if_dependency_reason() const;
+ };
+
+ class DependencyReason :
+ private PrivateImplementationPattern<DependencyReason>,
+ public Reason
+ {
+ public:
+ DependencyReason(
+ const QPN_S & q,
+ const SanitisedDependency & s);
+
+ ~DependencyReason();
+
+ const QPN_S qpn_s() const;
+
+ const SanitisedDependency & sanitised_dependency() const;
+
+ virtual std::string as_string() const;
+
+ virtual DependencyReason * if_dependency_reason();
+
+ virtual const DependencyReason * if_dependency_reason() const;
+ };
+ }
+
+#ifdef PALUDIS_HAVE_EXTERN_TEMPLATE
+ extern template class PrivateImplementationPattern<resolver::DependencyReason>;
+#endif
+
+}
+
+#endif
diff --git a/paludis/resolver/resolution-fwd.hh b/paludis/resolver/resolution-fwd.hh
new file mode 100644
index 0000000..0345a2a
--- /dev/null
+++ b/paludis/resolver/resolution-fwd.hh
@@ -0,0 +1,36 @@
+/* vim: set sw=4 sts=4 et foldmethod=syntax : */
+
+/*
+ * Copyright (c) 2009 Ciaran McCreesh
+ *
+ * This file is part of the Paludis package manager. Paludis is free software;
+ * you can redistribute it and/or modify it under the terms of the GNU General
+ * Public License version 2, as published by the Free Software Foundation.
+ *
+ * Paludis is distributed in the hope that it will be useful, but WITHOUT ANY
+ * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+ * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
+ * details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * this program; if not, write to the Free Software Foundation, Inc., 59 Temple
+ * Place, Suite 330, Boston, MA 02111-1307 USA
+ */
+
+#ifndef PALUDIS_GUARD_PALUDIS_RESOLVER_RESOLUTION_FWD_HH
+#define PALUDIS_GUARD_PALUDIS_RESOLVER_RESOLUTION_FWD_HH 1
+
+#include <paludis/util/attributes.hh>
+#include <iosfwd>
+
+namespace paludis
+{
+ namespace resolver
+ {
+ struct Resolution;
+
+ std::ostream & operator<< (std::ostream & s, const Resolution & r) PALUDIS_VISIBLE;
+ }
+}
+
+#endif
diff --git a/paludis/resolver/resolution.cc b/paludis/resolver/resolution.cc
new file mode 100644
index 0000000..9c67877
--- /dev/null
+++ b/paludis/resolver/resolution.cc
@@ -0,0 +1,45 @@
+/* vim: set sw=4 sts=4 et foldmethod=syntax : */
+
+/*
+ * Copyright (c) 2009 Ciaran McCreesh
+ *
+ * This file is part of the Paludis package manager. Paludis is free software;
+ * you can redistribute it and/or modify it under the terms of the GNU General
+ * Public License version 2, as published by the Free Software Foundation.
+ *
+ * Paludis is distributed in the hope that it will be useful, but WITHOUT ANY
+ * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+ * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
+ * details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * this program; if not, write to the Free Software Foundation, Inc., 59 Temple
+ * Place, Suite 330, Boston, MA 02111-1307 USA
+ */
+
+#include <paludis/resolver/resolution.hh>
+#include <paludis/resolver/constraint.hh>
+#include <paludis/resolver/arrow.hh>
+#include <paludis/resolver/decision.hh>
+#include <paludis/util/sequence.hh>
+#include <paludis/util/join.hh>
+#include <paludis/util/wrapped_forward_iterator.hh>
+#include <paludis/util/indirect_iterator-impl.hh>
+#include <sstream>
+
+using namespace paludis;
+using namespace paludis::resolver;
+
+std::ostream &
+paludis::resolver::operator<< (std::ostream & s, const Resolution & r)
+{
+ std::stringstream ss;
+ ss << "Resolution("
+ << "constraints: " << join(indirect_iterator(r.constraints()->begin()), indirect_iterator(r.constraints()->end()), ", ")
+ << "; decision: " << (r.decision() ? stringify(*r.decision()) : "none")
+ << "; arrows: " << join(indirect_iterator(r.arrows()->begin()), indirect_iterator(r.arrows()->end()), ", ")
+ << "; already_ordered: " << stringify(r.already_ordered()) << ")";
+ s << ss.str();
+ return s;
+}
+
diff --git a/paludis/resolver/resolution.hh b/paludis/resolver/resolution.hh
new file mode 100644
index 0000000..335a270
--- /dev/null
+++ b/paludis/resolver/resolution.hh
@@ -0,0 +1,52 @@
+/* vim: set sw=4 sts=4 et foldmethod=syntax : */
+
+/*
+ * Copyright (c) 2009 Ciaran McCreesh
+ *
+ * This file is part of the Paludis package manager. Paludis is free software;
+ * you can redistribute it and/or modify it under the terms of the GNU General
+ * Public License version 2, as published by the Free Software Foundation.
+ *
+ * Paludis is distributed in the hope that it will be useful, but WITHOUT ANY
+ * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+ * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
+ * details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * this program; if not, write to the Free Software Foundation, Inc., 59 Temple
+ * Place, Suite 330, Boston, MA 02111-1307 USA
+ */
+
+#ifndef PALUDIS_GUARD_PALUDIS_RESOLVER_RESOLUTION_HH
+#define PALUDIS_GUARD_PALUDIS_RESOLVER_RESOLUTION_HH 1
+
+#include <paludis/resolver/resolution-fwd.hh>
+#include <paludis/resolver/arrow-fwd.hh>
+#include <paludis/resolver/constraint-fwd.hh>
+#include <paludis/resolver/decision-fwd.hh>
+#include <paludis/util/named_value.hh>
+#include <tr1/memory>
+
+namespace paludis
+{
+ namespace n
+ {
+ struct already_ordered;
+ struct arrows;
+ struct constraints;
+ struct decision;
+ }
+
+ namespace resolver
+ {
+ struct Resolution
+ {
+ NamedValue<n::already_ordered, bool> already_ordered;
+ NamedValue<n::arrows, std::tr1::shared_ptr<ArrowSequence> > arrows;
+ NamedValue<n::constraints, std::tr1::shared_ptr<ConstraintSequence> > constraints;
+ NamedValue<n::decision, std::tr1::shared_ptr<Decision> > decision;
+ };
+ }
+}
+
+#endif
diff --git a/paludis/resolver/resolver-fwd.hh b/paludis/resolver/resolver-fwd.hh
new file mode 100644
index 0000000..df41385
--- /dev/null
+++ b/paludis/resolver/resolver-fwd.hh
@@ -0,0 +1,31 @@
+/* vim: set sw=4 sts=4 et foldmethod=syntax : */
+
+/*
+ * Copyright (c) 2009 Ciaran McCreesh
+ *
+ * This file is part of the Paludis package manager. Paludis is free software;
+ * you can redistribute it and/or modify it under the terms of the GNU General
+ * Public License version 2, as published by the Free Software Foundation.
+ *
+ * Paludis is distributed in the hope that it will be useful, but WITHOUT ANY
+ * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+ * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
+ * details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * this program; if not, write to the Free Software Foundation, Inc., 59 Temple
+ * Place, Suite 330, Boston, MA 02111-1307 USA
+ */
+
+#ifndef PALUDIS_GUARD_PALUDIS_RESOLVER_RESOLVER_FWD_HH
+#define PALUDIS_GUARD_PALUDIS_RESOLVER_RESOLVER_FWD_HH 1
+
+namespace paludis
+{
+ namespace resolver
+ {
+ struct Resolver;
+ }
+}
+
+#endif
diff --git a/paludis/resolver/resolver.cc b/paludis/resolver/resolver.cc
new file mode 100644
index 0000000..5467a42
--- /dev/null
+++ b/paludis/resolver/resolver.cc
@@ -0,0 +1,1014 @@
+/* vim: set sw=4 sts=4 et foldmethod=syntax : */
+
+/*
+ * Copyright (c) 2009 Ciaran McCreesh
+ *
+ * This file is part of the Paludis package manager. Paludis is free software;
+ * you can redistribute it and/or modify it under the terms of the GNU General
+ * Public License version 2, as published by the Free Software Foundation.
+ *
+ * Paludis is distributed in the hope that it will be useful, but WITHOUT ANY
+ * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+ * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
+ * details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * this program; if not, write to the Free Software Foundation, Inc., 59 Temple
+ * Place, Suite 330, Boston, MA 02111-1307 USA
+ */
+
+#include <paludis/resolver/resolver.hh>
+#include <paludis/resolver/resolution.hh>
+#include <paludis/resolver/constraint.hh>
+#include <paludis/resolver/reason.hh>
+#include <paludis/resolver/qpn_s.hh>
+#include <paludis/resolver/sanitised_dependencies.hh>
+#include <paludis/resolver/arrow.hh>
+#include <paludis/resolver/decision.hh>
+#include <paludis/util/stringify.hh>
+#include <paludis/util/make_named_values.hh>
+#include <paludis/util/log.hh>
+#include <paludis/util/join.hh>
+#include <paludis/environment.hh>
+#include <paludis/notifier_callback.hh>
+#include <paludis/dep_spec_flattener.hh>
+#include <paludis/spec_tree.hh>
+#include <paludis/slot_requirement.hh>
+#include <paludis/filter.hh>
+#include <paludis/filtered_generator.hh>
+#include <paludis/generator.hh>
+#include <paludis/selection.hh>
+#include <paludis/metadata_key.hh>
+#include <paludis/match_package.hh>
+#include <paludis/action.hh>
+#include <paludis/version_spec.hh>
+#include <paludis/version_requirements.hh>
+#include <iostream>
+#include <iomanip>
+#include <list>
+#include <map>
+
+using namespace paludis;
+using namespace paludis::resolver;
+
+typedef std::map<QPN_S, std::tr1::shared_ptr<Resolution> > ResolutionsByQPN_SMap;
+typedef std::map<QPN_S, std::tr1::shared_ptr<ConstraintSequence> > InitialConstraints;
+typedef std::list<std::tr1::shared_ptr<const Resolution> > OrderedResolutionsList;
+
+namespace paludis
+{
+ template <>
+ struct Implementation<Resolver>
+ {
+ const Environment * const env;
+ ResolutionsByQPN_SMap resolutions_by_qpn_s;
+ InitialConstraints initial_constraints;
+ OrderedResolutionsList ordered_resolutions;
+
+ Implementation(const Environment * const e) :
+ env(e)
+ {
+ }
+ };
+}
+
+Resolver::Resolver(const Environment * const e) :
+ PrivateImplementationPattern<Resolver>(new Implementation<Resolver>(e))
+{
+}
+
+Resolver::~Resolver()
+{
+}
+
+void
+Resolver::resolve()
+{
+ Context context("When finding an appropriate resolution:");
+
+ _resolve_dependencies();
+ _resolve_arrows();
+ _resolve_order();
+}
+
+void
+Resolver::_resolve_dependencies()
+{
+ Context context("When resolving dependencies recursively:");
+
+ bool done(false);
+ while (! done)
+ {
+ done = true;
+
+ for (ResolutionsByQPN_SMap::iterator i(_imp->resolutions_by_qpn_s.begin()), i_end(_imp->resolutions_by_qpn_s.end()) ;
+ i != i_end ; ++i)
+ {
+ if (i->second->decision())
+ continue;
+
+ _imp->env->trigger_notifier_callback(NotifierCallbackResolverStepEvent());
+
+ done = false;
+ _decide(i->first, i->second);
+
+ _add_dependencies(i->first, i->second);
+ }
+ }
+}
+
+void
+Resolver::add_target(const PackageDepSpec & spec, const UseInstalled use_installed)
+{
+ Context context("When adding target '" + stringify(spec) + "':");
+ _imp->env->trigger_notifier_callback(NotifierCallbackResolverStepEvent());
+
+ std::list<QPN_S> qpn_s_s;
+ _find_qpn_s_s_for_spec(spec, std::back_inserter(qpn_s_s));
+ if (qpn_s_s.empty())
+ throw InternalError(PALUDIS_HERE, "not implemented: no slot for " + stringify(spec));
+
+ for (std::list<QPN_S>::const_iterator qpn_s(qpn_s_s.begin()), qpn_s_end(qpn_s_s.end()) ;
+ qpn_s != qpn_s_end ; ++qpn_s)
+ {
+ Context context_2("When adding constraints from target '" + stringify(spec) + "' to qpn:s '"
+ + stringify(*qpn_s) + "':");
+
+ const std::tr1::shared_ptr<Resolution> dep_resolution(_resolution_for_qpn_s(*qpn_s, true));
+ const std::tr1::shared_ptr<Constraint> constraint(_make_constraint_from_target(spec, use_installed));
+
+ _apply_resolution_constraint(*qpn_s, dep_resolution, constraint);
+ }
+}
+
+void
+Resolver::add_set(const SetName & set_name, const UseInstalled use_installed)
+{
+ Context context("When adding set target '" + stringify(set_name) + "':");
+ _imp->env->trigger_notifier_callback(NotifierCallbackResolverStepEvent());
+
+ const std::tr1::shared_ptr<const SetSpecTree> set(_imp->env->set(set_name));
+ if (! set)
+ throw InternalError(PALUDIS_HERE, "todo");
+
+ DepSpecFlattener<SetSpecTree, PackageDepSpec> flattener(_imp->env);
+ set->root()->accept(flattener);
+
+ for (DepSpecFlattener<SetSpecTree, PackageDepSpec>::ConstIterator s(flattener.begin()), s_end(flattener.end()) ;
+ s != s_end ; ++s)
+ add_target(**s, use_installed);
+}
+
+namespace
+{
+ struct SlotNameFinder
+ {
+ std::tr1::shared_ptr<SlotName> visit(const SlotExactRequirement & s)
+ {
+ return make_shared_ptr(new SlotName(s.slot()));
+ }
+
+ std::tr1::shared_ptr<SlotName> visit(const SlotAnyUnlockedRequirement &)
+ {
+ return make_null_shared_ptr();
+ }
+
+ std::tr1::shared_ptr<SlotName> visit(const SlotAnyLockedRequirement &)
+ {
+ return make_null_shared_ptr();
+ }
+ };
+}
+
+template <typename I_>
+void
+Resolver::_find_qpn_s_s_for_spec(const PackageDepSpec & spec, I_ iter) const
+{
+ std::tr1::shared_ptr<SlotName> exact_slot;
+
+ if (spec.slot_requirement_ptr())
+ {
+ SlotNameFinder f;
+ exact_slot = spec.slot_requirement_ptr()->accept_returning<std::tr1::shared_ptr<SlotName> >(f);
+ }
+
+ if (exact_slot)
+ *iter++ = make_named_values<QPN_S>(
+ value_for<n::package>(_package_from_spec(spec)),
+ value_for<n::slot_name_or_null>(exact_slot)
+ );
+ else
+ {
+ const std::tr1::shared_ptr<const PackageIDSequence> ids((*_imp->env)[selection::BestVersionOnly(
+ generator::Matches(spec, MatchPackageOptions() + mpo_ignore_additional_requirements) |
+ filter::SupportsAction<InstallAction>() |
+ filter::NotMasked())]);
+
+ if (! ids->empty())
+ *iter++ = qpn_s_from_id(*ids->begin());
+ else
+ {
+ const std::tr1::shared_ptr<const PackageIDSequence> installed_ids((*_imp->env)[selection::BestVersionOnly(
+ generator::Matches(spec, MatchPackageOptions() + mpo_ignore_additional_requirements) |
+ filter::SupportsAction<InstalledAction>())]);
+
+ if (! installed_ids->empty())
+ *iter++ = qpn_s_from_id(*installed_ids->begin());
+ }
+ }
+}
+
+QualifiedPackageName
+Resolver::_package_from_spec(const PackageDepSpec & spec) const
+{
+ if (! spec.package_ptr())
+ throw InternalError(PALUDIS_HERE, "not implemented");
+
+ return *spec.package_ptr();
+}
+
+const std::tr1::shared_ptr<Resolution>
+Resolver::_create_resolution_for_qpn_s(const QPN_S & qpn_s) const
+{
+ return make_shared_ptr(new Resolution(make_named_values<Resolution>(
+ value_for<n::already_ordered>(false),
+ value_for<n::arrows>(make_shared_ptr(new ArrowSequence)),
+ value_for<n::constraints>(_initial_constraints_for(qpn_s)),
+ value_for<n::decision>(make_null_shared_ptr())
+ )));
+}
+
+const std::tr1::shared_ptr<Resolution>
+Resolver::_resolution_for_qpn_s(const QPN_S & qpn_s, const bool create)
+{
+ ResolutionsByQPN_SMap::iterator i(_imp->resolutions_by_qpn_s.find(qpn_s));
+ if (_imp->resolutions_by_qpn_s.end() == i)
+ {
+ if (create)
+ i = _imp->resolutions_by_qpn_s.insert(std::make_pair(qpn_s, _create_resolution_for_qpn_s(qpn_s))).first;
+ else
+ throw InternalError(PALUDIS_HERE, "doesn't exist");
+ }
+
+ return i->second;
+}
+
+const std::tr1::shared_ptr<Resolution>
+Resolver::_resolution_for_qpn_s(const QPN_S & qpn_s) const
+{
+ ResolutionsByQPN_SMap::const_iterator i(_imp->resolutions_by_qpn_s.find(qpn_s));
+ if (_imp->resolutions_by_qpn_s.end() == i)
+ throw InternalError(PALUDIS_HERE, "doesn't exist");
+
+ return i->second;
+}
+
+QPN_S
+Resolver::qpn_s_from_id(const std::tr1::shared_ptr<const PackageID> & id) const
+{
+ return make_named_values<QPN_S>(
+ value_for<n::package>(id->name()),
+ value_for<n::slot_name_or_null>(id->slot_key() ? make_shared_ptr(new SlotName(id->slot_key()->value())) : make_null_shared_ptr())
+ );
+}
+
+const std::tr1::shared_ptr<Constraint>
+Resolver::_make_constraint_from_target(const PackageDepSpec & spec, const UseInstalled use_installed) const
+{
+ return make_shared_ptr(new Constraint(make_named_values<Constraint>(
+ // value_for<n::desire_strength>(ds_requirement),
+ value_for<n::reason>(make_shared_ptr(new TargetReason)),
+ value_for<n::spec>(spec),
+ value_for<n::use_installed>(use_installed)
+ )));
+}
+
+const std::tr1::shared_ptr<Constraint>
+Resolver::_make_constraint_from_dependency(const QPN_S & qpn_s, const SanitisedDependency & dep) const
+{
+ return make_shared_ptr(new Constraint(make_named_values<Constraint>(
+ // value_for<n::desire_strength>(_desire_strength_from_sanitised_dependency(qpn_s, dep)),
+ value_for<n::reason>(make_shared_ptr(new DependencyReason(qpn_s, dep))),
+ value_for<n::spec>(dep.spec()),
+ value_for<n::use_installed>(ui_if_same)
+ )));
+}
+
+void
+Resolver::_apply_resolution_constraint(
+ const QPN_S & qpn_s,
+ const std::tr1::shared_ptr<Resolution> & resolution,
+ const std::tr1::shared_ptr<const Constraint> & constraint)
+{
+ if (resolution->decision())
+ _verify_new_constraint(qpn_s, resolution, constraint);
+
+ resolution->constraints()->push_back(constraint);
+}
+
+void
+Resolver::_verify_new_constraint(
+ const QPN_S & qpn_s,
+ const std::tr1::shared_ptr<const Resolution> & r,
+ const std::tr1::shared_ptr<const Constraint> & c)
+{
+ if (! _constraint_matches(c, r->decision()))
+ _made_wrong_decision(qpn_s, r, c);
+}
+
+bool
+Resolver::_constraint_matches(
+ const std::tr1::shared_ptr<const Constraint> & c,
+ const std::tr1::shared_ptr<const Decision> & decision) const
+{
+ Context context("When working out whether '" + stringify(*decision) + "' is matched by '" + stringify(*c) + "':");
+
+ bool ok(true);
+
+ switch (c->use_installed())
+ {
+ case ui_never:
+ ok = ok && ! decision->is_installed();
+ break;
+
+ case ui_only_if_transient:
+ ok = ok && ((! decision->is_installed()) || (decision->is_transient()));
+ break;
+
+ case ui_if_possible:
+ break;
+
+ case ui_if_same:
+ if (decision->is_installed())
+ ok = ok && (decision->is_same() || decision->is_transient());
+ break;
+
+ case ui_if_same_version:
+ if (decision->is_installed())
+ ok = ok && (decision->is_same_version() || decision->is_transient());
+ break;
+
+ case ui_always:
+ ok = ok && decision->is_installed();
+ break;
+
+ case last_ui:
+ break;
+ }
+
+ ok = ok && match_package(*_imp->env, c->spec(), *decision->package_id(), MatchPackageOptions());
+
+ return ok;
+}
+
+void
+Resolver::_decide(const QPN_S & qpn_s, const std::tr1::shared_ptr<Resolution> & resolution)
+{
+ Context context("When deciding upon an origin ID to use for '" + stringify(qpn_s) + "' with '"
+ + stringify(*resolution) + "':");
+
+ std::tr1::shared_ptr<Decision> decision(_try_to_find_decision_for(qpn_s, resolution));
+ if (decision)
+ resolution->decision() = decision;
+ else
+ _unable_to_decide(qpn_s, resolution);
+}
+
+const std::tr1::shared_ptr<Decision>
+Resolver::_try_to_find_decision_for(const QPN_S & qpn_s,
+ const std::tr1::shared_ptr<const Resolution> & resolution) const
+{
+ std::tr1::shared_ptr<const PackageID> id;
+
+ if (((id = _best_installed_id_for(qpn_s, resolution))))
+ return _decision_from_package_id(qpn_s, id);
+
+ if (((id = _best_installable_id_for(qpn_s, resolution))))
+ return _decision_from_package_id(qpn_s, id);
+
+ return make_null_shared_ptr();
+}
+
+const std::tr1::shared_ptr<const PackageID>
+Resolver::_best_installed_id_for(const QPN_S & qpn_s, const std::tr1::shared_ptr<const Resolution> & resolution) const
+{
+ const std::tr1::shared_ptr<const PackageIDSequence> ids((*_imp->env)[selection::AllVersionsSorted(
+ generator::Package(qpn_s.package()) |
+ _make_slot_filter(qpn_s) |
+ filter::SupportsAction<InstalledAction>())]);
+
+ return _best_id_from(ids, qpn_s, resolution);
+}
+
+const std::tr1::shared_ptr<const PackageID>
+Resolver::_best_installable_id_for(const QPN_S & qpn_s, const std::tr1::shared_ptr<const Resolution> & resolution) const
+{
+ const std::tr1::shared_ptr<const PackageIDSequence> ids((*_imp->env)[selection::AllVersionsSorted(
+ generator::Package(qpn_s.package()) |
+ _make_slot_filter(qpn_s) |
+ filter::SupportsAction<InstallAction>() |
+ filter::NotMasked())]);
+
+ return _best_id_from(ids, qpn_s, resolution);
+}
+
+const std::tr1::shared_ptr<const PackageID>
+Resolver::_best_id_from(
+ const std::tr1::shared_ptr<const PackageIDSequence> & ids,
+ const QPN_S & qpn_s,
+ const std::tr1::shared_ptr<const Resolution> & resolution) const
+{
+ for (PackageIDSequence::ReverseConstIterator i(ids->rbegin()), i_end(ids->rend()) ;
+ i != i_end ; ++i)
+ {
+ bool ok(true);
+
+ for (ConstraintSequence::ConstIterator c(resolution->constraints()->begin()),
+ c_end(resolution->constraints()->end()) ;
+ c != c_end ; ++c)
+ {
+ if (! _constraint_matches(*c, _decision_from_package_id(qpn_s, *i)))
+ {
+ ok = false;
+ break;
+ }
+ }
+
+ if (ok)
+ return *i;
+ }
+
+ return make_null_shared_ptr();
+}
+
+Filter
+Resolver::_make_slot_filter(const QPN_S & qpn_s) const
+{
+ if (qpn_s.slot_name_or_null())
+ return filter::Slot(*qpn_s.slot_name_or_null());
+ else
+ return filter::NoSlot();
+}
+
+void
+Resolver::_add_dependencies(const QPN_S & our_qpn_s, const std::tr1::shared_ptr<Resolution> & our_resolution)
+{
+ Context context("When adding dependencies for '" + stringify(our_qpn_s) + "' with '"
+ + stringify(*our_resolution) + "':");
+
+ const std::tr1::shared_ptr<SanitisedDependencies> deps(new SanitisedDependencies);
+ deps->populate(*this, our_resolution->decision()->package_id());
+
+ for (SanitisedDependencies::ConstIterator s(deps->begin()), s_end(deps->end()) ;
+ s != s_end ; ++s)
+ {
+ Context context_2("When handling dependency '" + stringify(*s) + "':");
+
+ std::list<QPN_S> qpn_s_s;
+
+ if (! _care_about_dependency_spec(our_qpn_s, our_resolution, *s))
+ continue;
+
+ _find_qpn_s_s_for_spec(s->spec(), std::back_inserter(qpn_s_s));
+ if (qpn_s_s.empty())
+ {
+ if (our_resolution->decision()->is_installed())
+ Log::get_instance()->message("resolver.cannot_find_installed_dep", ll_warning, lc_context)
+ << "Installed package '" << *our_resolution->decision() << "' dependency '" << *s << " cannot be met";
+ else
+ throw InternalError(PALUDIS_HERE, "not implemented: no slot for " + stringify(s->spec()));
+ }
+
+ for (std::list<QPN_S>::const_iterator qpn_s(qpn_s_s.begin()), qpn_s_end(qpn_s_s.end()) ;
+ qpn_s != qpn_s_end ; ++qpn_s)
+ {
+ const std::tr1::shared_ptr<Resolution> dep_resolution(_resolution_for_qpn_s(*qpn_s, true));
+ const std::tr1::shared_ptr<Constraint> constraint(_make_constraint_from_dependency(our_qpn_s, *s));
+
+ _apply_resolution_constraint(*qpn_s, dep_resolution, constraint);
+ }
+ }
+}
+
+bool
+Resolver::_care_about_dependency_spec(const QPN_S & qpn_s,
+ const std::tr1::shared_ptr<const Resolution> &, const SanitisedDependency & dep) const
+{
+ return true;
+ // return _desire_strength_from_sanitised_dependency(qpn_s, dep) >= ds_recommendation;
+}
+
+void
+Resolver::_resolve_arrows()
+{
+ Context context("When creating arrows for order resolution:");
+
+ for (ResolutionsByQPN_SMap::iterator i(_imp->resolutions_by_qpn_s.begin()), i_end(_imp->resolutions_by_qpn_s.end()) ;
+ i != i_end ; ++i)
+ {
+ for (ConstraintSequence::ConstIterator c(i->second->constraints()->begin()),
+ c_end(i->second->constraints()->end()) ;
+ c != c_end ; ++c)
+ {
+ if (! (*c)->reason()->if_dependency_reason())
+ continue;
+
+ const QPN_S from_qpns((*c)->reason()->if_dependency_reason()->qpn_s());
+ const std::tr1::shared_ptr<Resolution> resolution(_resolution_for_qpn_s(from_qpns, false));
+
+ if (_causes_pre_arrow(*(*c)->reason()->if_dependency_reason()))
+ resolution->arrows()->push_back(make_shared_ptr(new Arrow(make_named_values<Arrow>(
+ value_for<n::to_qpn_s>(i->first)
+ ))));
+ }
+ }
+}
+
+namespace
+{
+ struct DependencyTypeLabelCausesPreArrow
+ {
+ bool visit(const DependencyBuildLabel &)
+ {
+ return true;
+ }
+
+ bool visit(const DependencyRunLabel &)
+ {
+ return true;
+ }
+
+ bool visit(const DependencyPostLabel &)
+ {
+ return false;
+ }
+
+ bool visit(const DependencyInstallLabel &)
+ {
+ return true;
+ }
+
+ bool visit(const DependencyCompileLabel &)
+ {
+ return true;
+ }
+ };
+}
+
+bool
+Resolver::_causes_pre_arrow(const DependencyReason & reason) const
+{
+ const std::tr1::shared_ptr<const ActiveDependencyLabels> labels(
+ reason.sanitised_dependency().active_dependency_labels());
+
+ if (labels->type_labels()->empty())
+ throw InternalError(PALUDIS_HERE, "why did that happen?");
+
+ for (DependencyTypeLabelSequence::ConstIterator l(labels->type_labels()->begin()),
+ l_end(labels->type_labels()->end()) ;
+ l != l_end ; ++l)
+ {
+ DependencyTypeLabelCausesPreArrow v;
+ if ((*l)->accept_returning<bool>(v))
+ return true;
+ }
+
+ return false;
+}
+
+void
+Resolver::_resolve_order()
+{
+ Context context("When finding an order for selected packages:");
+
+ bool done(false);
+
+ for (ResolutionsByQPN_SMap::iterator i(_imp->resolutions_by_qpn_s.begin()), i_end(_imp->resolutions_by_qpn_s.end()) ;
+ i != i_end ; ++i)
+ if (i->second->decision()->is_installed())
+ i->second->already_ordered() = true;
+
+ while (! done)
+ {
+ bool any(false);
+ done = true;
+
+ for (ResolutionsByQPN_SMap::iterator i(_imp->resolutions_by_qpn_s.begin()), i_end(_imp->resolutions_by_qpn_s.end()) ;
+ i != i_end ; ++i)
+ {
+ if (i->second->already_ordered())
+ continue;
+
+ if (_can_order_now(i->first, i->second))
+ {
+ _imp->env->trigger_notifier_callback(NotifierCallbackResolverStepEvent());
+ _do_order(i->first, i->second);
+ any = true;
+ }
+ else
+ done = false;
+ }
+
+ if ((! done) && (! any))
+ _unable_to_order_more();
+ }
+}
+
+bool
+Resolver::_can_order_now(const QPN_S &, const std::tr1::shared_ptr<const Resolution> & resolution) const
+{
+ for (ArrowSequence::ConstIterator a(resolution->arrows()->begin()), a_end(resolution->arrows()->end()) ;
+ a != a_end ; ++a)
+ {
+ const std::tr1::shared_ptr<const Resolution> dep_resolution(_resolution_for_qpn_s((*a)->to_qpn_s()));
+ if (! dep_resolution->already_ordered())
+ return false;
+ }
+
+ return true;
+}
+
+void
+Resolver::_do_order(const QPN_S &, const std::tr1::shared_ptr<Resolution> & resolution)
+{
+ _imp->ordered_resolutions.push_back(resolution);
+ resolution->already_ordered() = true;
+}
+
+const std::tr1::shared_ptr<Decision>
+Resolver::_decision_from_package_id(const QPN_S & qpn_s, const std::tr1::shared_ptr<const PackageID> & id) const
+{
+ bool is_installed, is_transient, is_new, is_same, is_same_version;
+
+ is_installed = id->supports_action(SupportsActionTest<InstalledAction>());
+ is_transient = is_installed && id->transient_key() && id->transient_key()->value();
+
+ std::tr1::shared_ptr<const PackageIDSequence> comparison_ids;
+
+ if (is_installed)
+ comparison_ids = ((*_imp->env)[selection::BestVersionOnly(
+ generator::Package(qpn_s.package()) |
+ _make_slot_filter(qpn_s) |
+ filter::SupportsAction<InstallAction>() |
+ filter::NotMasked())]);
+ else
+ comparison_ids = ((*_imp->env)[selection::BestVersionOnly(
+ generator::Package(qpn_s.package()) |
+ _make_slot_filter(qpn_s) |
+ filter::SupportsAction<InstalledAction>())]);
+
+ if (comparison_ids->empty())
+ {
+ is_new = true;
+ is_same = false;
+ is_same_version = false;
+ }
+ else
+ {
+ is_new = false;
+ is_same = ((*comparison_ids->begin())->version() == id->version());
+ is_same_version = is_same;
+ }
+
+ return make_shared_ptr(new Decision(make_named_values<Decision>(
+ value_for<n::is_installed>(is_installed),
+ value_for<n::is_new>(is_new),
+ value_for<n::is_same>(is_same),
+ value_for<n::is_same_version>(is_same_version),
+ value_for<n::is_transient>(is_transient),
+ value_for<n::package_id>(id)
+ )));
+}
+
+void
+Resolver::_unable_to_decide(
+ const QPN_S & qpn_s,
+ const std::tr1::shared_ptr<const Resolution> & resolution) const
+{
+ const std::tr1::shared_ptr<const PackageIDSequence> ids((*_imp->env)[selection::AllVersionsSorted(
+ generator::Package(qpn_s.package()) |
+ _make_slot_filter(qpn_s) |
+ filter::SupportsAction<InstallAction>() |
+ filter::NotMasked())]);
+
+ if (ids->empty())
+ {
+ std::cout << "Unable to find anything at all unmasked and installable for " << qpn_s << std::endl;
+ }
+ else
+ {
+ std::cout << "Unable to find anything suitable for " << qpn_s << ":" << std::endl;
+ for (PackageIDSequence::ReverseConstIterator i(ids->rbegin()), i_end(ids->rend()) ;
+ i != i_end ; ++i)
+ {
+ std::cout << " * " << **i << " doesn't match:" << std::endl;
+ for (ConstraintSequence::ConstIterator c(resolution->constraints()->begin()),
+ c_end(resolution->constraints()->end()) ;
+ c != c_end ; ++c)
+ if (! _constraint_matches(*c, _decision_from_package_id(qpn_s, *i)))
+ std::cout << " * " << **c << std::endl;
+ }
+ }
+
+ throw InternalError(PALUDIS_HERE, "not implemented");
+}
+
+void
+Resolver::_unable_to_order_more() const
+{
+ std::cout << "Unable to order any of the follwoing:" << std::endl;
+
+ for (ResolutionsByQPN_SMap::const_iterator i(_imp->resolutions_by_qpn_s.begin()),
+ i_end(_imp->resolutions_by_qpn_s.end()) ;
+ i != i_end ; ++i)
+ {
+ if (i->second->already_ordered())
+ continue;
+
+ std::cout << " * " << *i->second->decision() << std::endl;
+ }
+
+ throw InternalError(PALUDIS_HERE, "not implemented");
+}
+
+const std::tr1::shared_ptr<ConstraintSequence>
+Resolver::_initial_constraints_for(const QPN_S & qpn_s) const
+{
+ InitialConstraints::const_iterator i(_imp->initial_constraints.find(qpn_s));
+ if (i == _imp->initial_constraints.end())
+ return make_shared_ptr(new ConstraintSequence);
+ else
+ return i->second;
+}
+
+void
+Resolver::_made_wrong_decision(const QPN_S & qpn_s,
+ const std::tr1::shared_ptr<const Resolution> & resolution,
+ const std::tr1::shared_ptr<const Constraint> & constraint)
+{
+ /* can we find a resolution that works for all our constraints? */
+ std::tr1::shared_ptr<Resolution> adapted_resolution(make_shared_ptr(new Resolution(*resolution)));
+ adapted_resolution->constraints()->push_back(constraint);
+
+ const std::tr1::shared_ptr<Decision> decision(_try_to_find_decision_for(qpn_s, adapted_resolution));
+ if (decision)
+ {
+ /* can we preload and restart? */
+ InitialConstraints::const_iterator x(_imp->initial_constraints.find(qpn_s));
+ if (x == _imp->initial_constraints.end())
+ {
+ /* we've not already locked this to something. yes! */
+ _suggest_restart_with(qpn_s, resolution, constraint, decision);
+ }
+ else
+ {
+ /* we can restart if we've selected the same or a newer version
+ * than before. but we don't support that yet. */
+ throw InternalError(PALUDIS_HERE, "should have selected " + stringify(*decision));
+ }
+ }
+ else
+ _unable_to_decide(qpn_s, adapted_resolution);
+}
+
+void
+Resolver::_suggest_restart_with(const QPN_S & qpn_s,
+ const std::tr1::shared_ptr<const Resolution> & resolution,
+ const std::tr1::shared_ptr<const Constraint> & constraint,
+ const std::tr1::shared_ptr<const Decision> & decision) const
+{
+ std::cout << "Suggesting a restart: for " << qpn_s << ", we originally decided " << *resolution
+ << ", but new constraint " << *constraint << " means we want " << *decision << " instead" << std::endl;
+
+ // throw SuggestRestart(qpn_s, _make_constraint_for_preloading(decision));
+ throw InternalError(PALUDIS_HERE, "need a restart");
+}
+
+const std::tr1::shared_ptr<const Constraint>
+Resolver::_make_constraint_for_preloading(
+ const std::tr1::shared_ptr<const Decision> & d) const
+{
+ return make_shared_ptr(new Constraint(make_named_values<Constraint>(
+ // value_for<n::desire_strength>(ds_none),
+ value_for<n::reason>(make_shared_ptr(new TargetReason)),
+ value_for<n::spec>(d->package_id()->uniquely_identifying_spec()),
+ value_for<n::use_installed>(ui_if_possible)
+ )));
+}
+
+void
+Resolver::copy_initial_constraints_from(const Resolver & other)
+{
+ for (InitialConstraints::const_iterator i(other._imp->initial_constraints.begin()),
+ i_end(other._imp->initial_constraints.end()) ;
+ i != i_end ; ++i)
+ _imp->initial_constraints.insert(*i);
+}
+
+void
+Resolver::add_initial_constraint(const QPN_S & q, const std::tr1::shared_ptr<const Constraint> & c)
+{
+ InitialConstraints::iterator i(_imp->initial_constraints.find(q));
+ if (i == _imp->initial_constraints.end())
+ i = _imp->initial_constraints.insert(std::make_pair(q, make_shared_ptr(new ConstraintSequence))).first;
+ i->second->push_back(c);
+}
+
+#if 0
+
+namespace
+{
+ struct DesireStrengthFinder
+ {
+ DesireStrength visit(const DependencyRequiredLabel &) const
+ {
+ return ds_requirement;
+ }
+
+ DesireStrength visit(const DependencySuggestedLabel &) const
+ {
+ return ds_suggestion;
+ }
+
+ DesireStrength visit(const DependencyRecommendedLabel &) const
+ {
+ return ds_recommendation;
+ }
+ };
+}
+
+DesireStrength
+Resolver::_desire_strength_from_sanitised_dependency(const QPN_S &, const SanitisedDependency & dep) const
+{
+ DesireStrength result(ds_none);
+
+ if (dep.active_dependency_labels()->suggest_labels()->empty())
+ result = ds_requirement;
+ else
+ {
+ DesireStrengthFinder f;
+ for (DependencySuggestLabelSequence::ConstIterator l(dep.active_dependency_labels()->suggest_labels()->begin()),
+ l_end(dep.active_dependency_labels()->suggest_labels()->end()) ;
+ l != l_end ; ++l)
+ result = std::max(result, (*l)->accept_returning<DesireStrength>(f));
+ }
+
+ return result;
+}
+#endif
+
+Resolver::ConstIterator
+Resolver::begin() const
+{
+ return ConstIterator(_imp->ordered_resolutions.begin());
+}
+
+Resolver::ConstIterator
+Resolver::end() const
+{
+ return ConstIterator(_imp->ordered_resolutions.end());
+}
+
+void
+Resolver::dump(std::ostream & s) const
+{
+ s << "Initial Constraints:" << std::endl;
+ for (InitialConstraints::const_iterator i(_imp->initial_constraints.begin()),
+ i_end(_imp->initial_constraints.end()) ;
+ i != i_end ; ++i)
+ s << " [*] " << std::left << std::setw(30) << i->first << " " <<
+ join(indirect_iterator(i->second->begin()), indirect_iterator(i->second->end()), ", ") << std::endl;
+ s << std::endl;
+
+ s << "Resolutions by QPN:S:" << std::endl;
+ for (ResolutionsByQPN_SMap::const_iterator i(_imp->resolutions_by_qpn_s.begin()),
+ i_end(_imp->resolutions_by_qpn_s.end()) ;
+ i != i_end ; ++i)
+ s << " [*] " << std::left << std::setw(30) << i->first << " " << *i->second << std::endl;
+ s << std::endl;
+
+ s << "Ordered Resolutions:" << std::endl;
+ for (OrderedResolutionsList::const_iterator i(_imp->ordered_resolutions.begin()),
+ i_end(_imp->ordered_resolutions.end()) ;
+ i != i_end ; ++i)
+ s << " [*] " << **i << std::endl;
+ s << std::endl;
+}
+
+int
+Resolver::find_any_score(const QPN_S & our_qpn_s, const SanitisedDependency & dep) const
+{
+ Context context("When working out whether we'd like '" + stringify(dep) + "' because of '"
+ + stringify(our_qpn_s) + "':");
+
+ int operator_bias(0);
+ if (dep.spec().version_requirements_ptr() && ! dep.spec().version_requirements_ptr()->empty())
+ {
+ int score(-1);
+ for (VersionRequirements::ConstIterator v(dep.spec().version_requirements_ptr()->begin()),
+ v_end(dep.spec().version_requirements_ptr()->end()) ;
+ v != v_end ; ++v)
+ {
+ int local_score(0);
+
+ switch (v->version_operator().value())
+ {
+ case vo_greater:
+ case vo_greater_equal:
+ local_score = 9;
+ break;
+
+ case vo_equal:
+ case vo_tilde:
+ case vo_nice_equal_star:
+ case vo_stupid_equal_star:
+ case vo_tilde_greater:
+ local_score = 2;
+ break;
+
+ case vo_less_equal:
+ case vo_less:
+ local_score = 1;
+ break;
+
+ case last_vo:
+ local_score = 1;
+ break;
+ }
+
+ if (score == -1)
+ score = local_score;
+ else
+ switch (dep.spec().version_requirements_mode())
+ {
+ case vr_and:
+ score = std::min(score, local_score);
+ break;
+
+ case vr_or:
+ score = std::max(score, local_score);
+ break;
+
+ case last_vr:
+ break;
+ }
+ }
+ operator_bias = score;
+ }
+ else
+ {
+ /* don't bias no operator over a >= operator, so || ( >=foo-2 bar )
+ * still likes foo. */
+ operator_bias = 9;
+ }
+
+ /* best: already installed */
+ {
+ const std::tr1::shared_ptr<const PackageIDSequence> installed_ids((*_imp->env)[selection::BestVersionOnly(
+ generator::Matches(dep.spec(), MatchPackageOptions() + mpo_ignore_additional_requirements) |
+ filter::SupportsAction<InstalledAction>())]);
+ if (! installed_ids->empty())
+ return 40 + operator_bias;
+ }
+
+ std::list<QPN_S> qpn_s_s;
+ _find_qpn_s_s_for_spec(dep.spec(), std::back_inserter(qpn_s_s));
+
+ /* next: will already be installing */
+ {
+ for (std::list<QPN_S>::const_iterator qpn_s(qpn_s_s.begin()), qpn_s_end(qpn_s_s.end()) ;
+ qpn_s != qpn_s_end ; ++qpn_s)
+ {
+ ResolutionsByQPN_SMap::const_iterator i(_imp->resolutions_by_qpn_s.find(*qpn_s));
+ if (i != _imp->resolutions_by_qpn_s.end())
+ return 30 + operator_bias;
+ }
+ }
+
+ /* next: could install */
+ {
+ for (std::list<QPN_S>::const_iterator qpn_s(qpn_s_s.begin()), qpn_s_end(qpn_s_s.end()) ;
+ qpn_s != qpn_s_end ; ++qpn_s)
+ {
+ const std::tr1::shared_ptr<Resolution> resolution(_create_resolution_for_qpn_s(*qpn_s));
+ const std::tr1::shared_ptr<Constraint> constraint(_make_constraint_from_dependency(our_qpn_s, dep));
+ resolution->constraints()->push_back(constraint);
+ const std::tr1::shared_ptr<Decision> decision(_try_to_find_decision_for(*qpn_s, resolution));
+ if (decision)
+ return 20 + operator_bias;
+ }
+ }
+
+ /* next: exists */
+ {
+ const std::tr1::shared_ptr<const PackageIDSequence> ids((*_imp->env)[selection::BestVersionOnly(
+ generator::Matches(dep.spec(), MatchPackageOptions() + mpo_ignore_additional_requirements)
+ )]);
+ if (! ids->empty())
+ return 10 + operator_bias;
+ }
+
+ /* yay, people are depping upon packages that don't exist again. I SMELL A LESSPIPE. */
+ return 0;
+}
+
diff --git a/paludis/resolver/resolver.hh b/paludis/resolver/resolver.hh
new file mode 100644
index 0000000..3598462
--- /dev/null
+++ b/paludis/resolver/resolver.hh
@@ -0,0 +1,154 @@
+/* vim: set sw=4 sts=4 et foldmethod=syntax : */
+
+/*
+ * Copyright (c) 2009 Ciaran McCreesh
+ *
+ * This file is part of the Paludis package manager. Paludis is free software;
+ * you can redistribute it and/or modify it under the terms of the GNU General
+ * Public License version 2, as published by the Free Software Foundation.
+ *
+ * Paludis is distributed in the hope that it will be useful, but WITHOUT ANY
+ * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+ * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
+ * details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * this program; if not, write to the Free Software Foundation, Inc., 59 Temple
+ * Place, Suite 330, Boston, MA 02111-1307 USA
+ */
+
+#ifndef PALUDIS_GUARD_PALUDIS_RESOLVER_RESOLVER_HH
+#define PALUDIS_GUARD_PALUDIS_RESOLVER_RESOLVER_HH 1
+
+#include <paludis/resolver/resolver-fwd.hh>
+#include <paludis/resolver/resolution-fwd.hh>
+#include <paludis/resolver/qpn_s-fwd.hh>
+#include <paludis/resolver/constraint-fwd.hh>
+#include <paludis/resolver/sanitised_dependencies-fwd.hh>
+#include <paludis/resolver/decision-fwd.hh>
+#include <paludis/resolver/reason-fwd.hh>
+#include <paludis/resolver/use_installed-fwd.hh>
+#include <paludis/util/private_implementation_pattern.hh>
+#include <paludis/util/wrapped_forward_iterator-fwd.hh>
+#include <paludis/package_id-fwd.hh>
+#include <paludis/dep_spec-fwd.hh>
+#include <paludis/name.hh>
+#include <paludis/filter-fwd.hh>
+#include <paludis/environment-fwd.hh>
+#include <tr1/memory>
+
+namespace paludis
+{
+ namespace resolver
+ {
+ class PALUDIS_VISIBLE Resolver :
+ private PrivateImplementationPattern<Resolver>
+ {
+ private:
+ template <typename I_> void _find_qpn_s_s_for_spec(const PackageDepSpec &, I_) const;
+
+ QualifiedPackageName _package_from_spec(const PackageDepSpec &) const;
+
+ const std::tr1::shared_ptr<Resolution> _create_resolution_for_qpn_s(const QPN_S &) const;
+ const std::tr1::shared_ptr<Resolution> _resolution_for_qpn_s(const QPN_S &, const bool create);
+ const std::tr1::shared_ptr<Resolution> _resolution_for_qpn_s(const QPN_S &) const;
+
+ const std::tr1::shared_ptr<Constraint> _make_constraint_from_target(
+ const PackageDepSpec &, const UseInstalled) const;
+
+ const std::tr1::shared_ptr<Constraint> _make_constraint_from_dependency(
+ const QPN_S &, const SanitisedDependency &) const;
+
+ const std::tr1::shared_ptr<Decision> _decision_from_package_id(
+ const QPN_S &, const std::tr1::shared_ptr<const PackageID> &) const;
+
+ void _apply_resolution_constraint(const QPN_S &,
+ const std::tr1::shared_ptr<Resolution> &,
+ const std::tr1::shared_ptr<const Constraint> &);
+
+ void _verify_new_constraint(const QPN_S &,
+ const std::tr1::shared_ptr<const Resolution> &,
+ const std::tr1::shared_ptr<const Constraint> &);
+
+ void _made_wrong_decision(const QPN_S &,
+ const std::tr1::shared_ptr<const Resolution> &,
+ const std::tr1::shared_ptr<const Constraint> &) PALUDIS_ATTRIBUTE((noreturn));
+
+ bool _constraint_matches(
+ const std::tr1::shared_ptr<const Constraint> &,
+ const std::tr1::shared_ptr<const Decision> &) const;
+
+ void _resolve_dependencies();
+ void _resolve_arrows();
+ void _resolve_order();
+
+ void _decide(const QPN_S &, const std::tr1::shared_ptr<Resolution> & resolution);
+
+ const std::tr1::shared_ptr<Decision> _try_to_find_decision_for(
+ const QPN_S &, const std::tr1::shared_ptr<const Resolution> & resolution) const;
+
+ const std::tr1::shared_ptr<const PackageID> _best_installed_id_for(
+ const QPN_S &, const std::tr1::shared_ptr<const Resolution> &) const;
+
+ const std::tr1::shared_ptr<const PackageID> _best_installable_id_for(
+ const QPN_S &, const std::tr1::shared_ptr<const Resolution> &) const;
+
+ const std::tr1::shared_ptr<const PackageID> _best_id_from(
+ const std::tr1::shared_ptr<const PackageIDSequence> &,
+ const QPN_S &, const std::tr1::shared_ptr<const Resolution> &) const;
+
+ void _add_dependencies(const QPN_S & our_qpn_s, const std::tr1::shared_ptr<Resolution> & our_resolution);
+
+ Filter _make_slot_filter(const QPN_S &) const;
+
+ bool _care_about_dependency_spec(const QPN_S &, const std::tr1::shared_ptr<const Resolution> &,
+ const SanitisedDependency &) const;
+
+ bool _causes_pre_arrow(const DependencyReason &) const;
+
+ bool _can_order_now(const QPN_S &, const std::tr1::shared_ptr<const Resolution> & resolution) const;
+
+ void _do_order(const QPN_S &, const std::tr1::shared_ptr<Resolution> & resolution);
+
+ void _unable_to_decide(const QPN_S &,
+ const std::tr1::shared_ptr<const Resolution> &) const PALUDIS_ATTRIBUTE((noreturn));
+
+ void _unable_to_order_more() const PALUDIS_ATTRIBUTE((noreturn));
+
+ const std::tr1::shared_ptr<ConstraintSequence> _initial_constraints_for(const QPN_S &) const;
+
+ void _suggest_restart_with(const QPN_S &,
+ const std::tr1::shared_ptr<const Resolution> &,
+ const std::tr1::shared_ptr<const Constraint> &,
+ const std::tr1::shared_ptr<const Decision> &) const PALUDIS_ATTRIBUTE((noreturn));
+
+ const std::tr1::shared_ptr<const Constraint> _make_constraint_for_preloading(
+ const std::tr1::shared_ptr<const Decision> &) const;
+
+ public:
+ Resolver(const Environment * const);
+ ~Resolver();
+
+ void add_target(const PackageDepSpec &, const UseInstalled);
+ void add_set(const SetName &, const UseInstalled);
+
+ void copy_initial_constraints_from(const Resolver &);
+ void add_initial_constraint(const QPN_S &, const std::tr1::shared_ptr<const Constraint> &);
+
+ void resolve();
+ void dump(std::ostream &) const;
+
+ struct ConstIteratorTag;
+ typedef WrappedForwardIterator<ConstIteratorTag,
+ const std::tr1::shared_ptr<const Resolution> > ConstIterator;
+ ConstIterator begin() const PALUDIS_ATTRIBUTE((warn_unused_result));
+ ConstIterator end() const PALUDIS_ATTRIBUTE((warn_unused_result));
+
+ int find_any_score(const QPN_S &, const SanitisedDependency &) const;
+ QPN_S qpn_s_from_id(const std::tr1::shared_ptr<const PackageID> &) const;
+
+ };
+ }
+}
+
+#endif
diff --git a/paludis/resolver/sanitised_dependencies-fwd.hh b/paludis/resolver/sanitised_dependencies-fwd.hh
new file mode 100644
index 0000000..14bc0cf
--- /dev/null
+++ b/paludis/resolver/sanitised_dependencies-fwd.hh
@@ -0,0 +1,37 @@
+/* vim: set sw=4 sts=4 et foldmethod=syntax : */
+
+/*
+ * Copyright (c) 2009 Ciaran McCreesh
+ *
+ * This file is part of the Paludis package manager. Paludis is free software;
+ * you can redistribute it and/or modify it under the terms of the GNU General
+ * Public License version 2, as published by the Free Software Foundation.
+ *
+ * Paludis is distributed in the hope that it will be useful, but WITHOUT ANY
+ * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+ * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
+ * details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * this program; if not, write to the Free Software Foundation, Inc., 59 Temple
+ * Place, Suite 330, Boston, MA 02111-1307 USA
+ */
+
+#ifndef PALUDIS_GUARD_PALUDIS_RESOLVER_SANITISED_DEPENDENCIES_FWD_HH
+#define PALUDIS_GUARD_PALUDIS_RESOLVER_SANITISED_DEPENDENCIES_FWD_HH 1
+
+#include <paludis/util/attributes.hh>
+#include <iosfwd>
+
+namespace paludis
+{
+ namespace resolver
+ {
+ struct SanitisedDependencies;
+ struct SanitisedDependency;
+
+ std::ostream & operator<< (std::ostream & s, const SanitisedDependency & d) PALUDIS_VISIBLE;
+ }
+}
+
+#endif
diff --git a/paludis/resolver/sanitised_dependencies.cc b/paludis/resolver/sanitised_dependencies.cc
new file mode 100644
index 0000000..a176899
--- /dev/null
+++ b/paludis/resolver/sanitised_dependencies.cc
@@ -0,0 +1,518 @@
+/* vim: set sw=4 sts=4 et foldmethod=syntax : */
+
+/*
+ * Copyright (c) 2009 Ciaran McCreesh
+ *
+ * This file is part of the Paludis package manager. Paludis is free software;
+ * you can redistribute it and/or modify it under the terms of the GNU General
+ * Public License version 2, as published by the Free Software Foundation.
+ *
+ * Paludis is distributed in the hope that it will be useful, but WITHOUT ANY
+ * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+ * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
+ * details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * this program; if not, write to the Free Software Foundation, Inc., 59 Temple
+ * Place, Suite 330, Boston, MA 02111-1307 USA
+ */
+
+#include <paludis/resolver/sanitised_dependencies.hh>
+#include <paludis/resolver/resolver.hh>
+#include <paludis/resolver/qpn_s.hh>
+#include <paludis/util/make_named_values.hh>
+#include <paludis/util/save.hh>
+#include <paludis/util/stringify.hh>
+#include <paludis/util/options.hh>
+#include <paludis/spec_tree.hh>
+#include <paludis/package_dep_spec_properties.hh>
+#include <paludis/slot_requirement.hh>
+#include <paludis/metadata_key.hh>
+#include <paludis/package_id.hh>
+#include <set>
+#include <list>
+
+using namespace paludis;
+using namespace paludis::resolver;
+
+namespace
+{
+ struct IsUnrestrictedSlot
+ {
+ bool visit(const SlotExactRequirement &) const
+ {
+ return false;
+ }
+
+ bool visit(const SlotAnyUnlockedRequirement &) const
+ {
+ return true;
+ }
+
+ bool visit(const SlotAnyLockedRequirement &) const
+ {
+ return true;
+ }
+ };
+
+ template <typename T_>
+ void list_push_back(std::list<T_> * const l, const T_ & t)
+ {
+ l->push_back(t);
+ }
+
+ struct AnyDepSpecChildHandler
+ {
+ const Resolver & resolver;
+ const QPN_S our_qpn_s;
+ const std::tr1::function<SanitisedDependency (const PackageDepSpec &)> parent_make_sanitised;
+
+ bool super_complicated, nested;
+
+ std::list<std::list<PackageDepSpec> > child_groups;
+ std::list<PackageDepSpec> * active_sublist;
+ std::set<QualifiedPackageName> seen_qpns;
+
+ bool seen_unadorned, seen_slots, seen_additional_requirements, seen_version_requirements, seen_unknown;
+
+ AnyDepSpecChildHandler(const Resolver & r, const QPN_S & q,
+ const std::tr1::function<SanitisedDependency (const PackageDepSpec &)> & f) :
+ resolver(r),
+ our_qpn_s(q),
+ parent_make_sanitised(f),
+ super_complicated(false),
+ nested(false),
+ active_sublist(0),
+ seen_unadorned(false),
+ seen_slots(false),
+ seen_additional_requirements(false),
+ seen_version_requirements(false),
+ seen_unknown(false)
+ {
+ }
+
+ void visit_spec(const PackageDepSpec & spec)
+ {
+ if (spec.package_ptr())
+ {
+ seen_qpns.insert(*spec.package_ptr());
+
+ if (active_sublist)
+ active_sublist->push_back(spec);
+ else
+ {
+ std::list<PackageDepSpec> l;
+ l.push_back(spec);
+ child_groups.push_back(l);
+ }
+
+ if (spec.slot_requirement_ptr())
+ seen_slots = true;
+
+ if (spec.additional_requirements_ptr() && ! spec.additional_requirements_ptr()->empty())
+ seen_additional_requirements = true;
+
+ if (spec.version_requirements_ptr() && ! spec.version_requirements_ptr()->empty())
+ seen_version_requirements = true;
+
+ if (package_dep_spec_has_properties(spec, make_named_values<PackageDepSpecProperties>(
+ value_for<n::has_additional_requirements>(false),
+ value_for<n::has_category_name_part>(false),
+ value_for<n::has_from_repository>(false),
+ value_for<n::has_in_repository>(false),
+ value_for<n::has_installable_to_path>(false),
+ value_for<n::has_installable_to_repository>(false),
+ value_for<n::has_installed_at_path>(false),
+ value_for<n::has_package>(indeterminate),
+ value_for<n::has_package_name_part>(false),
+ value_for<n::has_slot_requirement>(false),
+ value_for<n::has_tag>(indeterminate),
+ value_for<n::has_version_requirements>(false)
+ )))
+ seen_unadorned = true;
+ else if (! package_dep_spec_has_properties(spec, make_named_values<PackageDepSpecProperties>(
+ value_for<n::has_additional_requirements>(indeterminate),
+ value_for<n::has_category_name_part>(false),
+ value_for<n::has_from_repository>(false),
+ value_for<n::has_in_repository>(false),
+ value_for<n::has_installable_to_path>(false),
+ value_for<n::has_installable_to_repository>(false),
+ value_for<n::has_installed_at_path>(false),
+ value_for<n::has_package>(indeterminate),
+ value_for<n::has_package_name_part>(false),
+ value_for<n::has_slot_requirement>(indeterminate),
+ value_for<n::has_tag>(indeterminate),
+ value_for<n::has_version_requirements>(indeterminate)
+ )))
+ seen_unknown = true;
+ }
+ else
+ super_complicated = true;
+ }
+
+ void visit(const DependencySpecTree::NodeType<PackageDepSpec>::Type & node)
+ {
+ visit_spec(*node.spec());
+ }
+
+ void visit(const DependencySpecTree::NodeType<BlockDepSpec>::Type &)
+ {
+ super_complicated = true;
+ }
+
+ void visit(const DependencySpecTree::NodeType<ConditionalDepSpec>::Type & node)
+ {
+ if (node.spec()->condition_met())
+ {
+ nested = true;
+
+ if (active_sublist)
+ std::for_each(indirect_iterator(node.begin()), indirect_iterator(node.end()), accept_visitor(*this));
+ else
+ {
+ Save<std::list<PackageDepSpec> *> save_active_sublist(&active_sublist, 0);
+ active_sublist = &*child_groups.insert(child_groups.end(), std::list<PackageDepSpec>());
+ std::for_each(indirect_iterator(node.begin()), indirect_iterator(node.end()), accept_visitor(*this));
+ }
+ }
+ }
+
+ void visit(const DependencySpecTree::NodeType<AllDepSpec>::Type & node)
+ {
+ nested = true;
+
+ if (active_sublist)
+ std::for_each(indirect_iterator(node.begin()), indirect_iterator(node.end()), accept_visitor(*this));
+ else
+ {
+ Save<std::list<PackageDepSpec> *> save_active_sublist(&active_sublist, 0);
+ active_sublist = &*child_groups.insert(child_groups.end(), std::list<PackageDepSpec>());
+ std::for_each(indirect_iterator(node.begin()), indirect_iterator(node.end()), accept_visitor(*this));
+ }
+ }
+
+ void visit(const DependencySpecTree::NodeType<AnyDepSpec>::Type & node)
+ {
+ AnyDepSpecChildHandler h(resolver, our_qpn_s, parent_make_sanitised);
+ std::for_each(indirect_iterator(node.begin()), indirect_iterator(node.end()), accept_visitor(h));
+ std::list<SanitisedDependency> l;
+ h.commit(
+ parent_make_sanitised,
+ std::tr1::bind(&list_push_back<SanitisedDependency>, &l, std::tr1::placeholders::_1)
+ );
+
+ if (active_sublist)
+ {
+ for (std::list<SanitisedDependency>::const_iterator i(l.begin()), i_end(l.end()) ;
+ i != i_end ; ++i)
+ visit_spec(i->spec());
+ }
+ else
+ {
+ Save<std::list<PackageDepSpec> *> save_active_sublist(&active_sublist, 0);
+ active_sublist = &*child_groups.insert(child_groups.end(), std::list<PackageDepSpec>());
+ for (std::list<SanitisedDependency>::const_iterator i(l.begin()), i_end(l.end()) ;
+ i != i_end ; ++i)
+ visit_spec(i->spec());
+ }
+ }
+
+ void visit(const DependencySpecTree::NodeType<NamedSetDepSpec>::Type &)
+ {
+ super_complicated = true;
+ }
+
+ void visit(const DependencySpecTree::NodeType<DependencyLabelsDepSpec>::Type &)
+ {
+ super_complicated = true;
+ }
+
+ void commit(
+ const std::tr1::function<SanitisedDependency (const PackageDepSpec &)> & make_sanitised,
+ const std::tr1::function<void (const SanitisedDependency &)> & apply)
+ {
+ if (seen_qpns.empty())
+ {
+ }
+ else if (1 == seen_qpns.size())
+ {
+ if (nested)
+ throw InternalError(PALUDIS_HERE, "not implemented");
+
+ if (seen_unadorned)
+ {
+ if (seen_slots || seen_additional_requirements || seen_version_requirements || seen_unknown)
+ throw InternalError(PALUDIS_HERE, "not implemented");
+
+ apply(make_sanitised(make_package_dep_spec(PartiallyMadePackageDepSpecOptions()).package(*seen_qpns.begin())));
+ }
+ else if (seen_slots)
+ {
+ if (seen_additional_requirements || seen_version_requirements || seen_unknown)
+ throw InternalError(PALUDIS_HERE, "not implemented");
+
+ /* we've got a choice of slots. if any of those slots is unrestricted, pick that. otherwise,
+ * pick the best score, left to right. */
+ bool done(false);
+ std::list<std::list<PackageDepSpec> >::const_iterator g_best(child_groups.end());
+ int best_score(-1);
+
+ for (std::list<std::list<PackageDepSpec> >::const_iterator g(child_groups.begin()), g_end(child_groups.end()) ;
+ g != g_end ; ++g)
+ {
+ if ((g->size() != 1) || (! g->begin()->slot_requirement_ptr()))
+ throw InternalError(PALUDIS_HERE, "why did that happen?");
+
+ IsUnrestrictedSlot u;
+ if (g->begin()->slot_requirement_ptr()->accept_returning<bool>(u))
+ {
+ apply(make_sanitised(*g->begin()));
+ done = true;
+ break;
+ }
+ else
+ {
+ int score(resolver.find_any_score(our_qpn_s, make_sanitised(*g->begin())));
+ if (score > best_score)
+ {
+ best_score = score;
+ g_best = g;
+ }
+ }
+ }
+
+ if (! done)
+ {
+ if (g_best == child_groups.end())
+ throw InternalError(PALUDIS_HERE, "why did that happen?");
+ apply(make_sanitised(*g_best->begin()));
+ }
+ }
+ else if (seen_additional_requirements || seen_version_requirements)
+ {
+ if (seen_additional_requirements && seen_version_requirements)
+ throw InternalError(PALUDIS_HERE, "not implemented");
+ if (seen_slots || seen_unknown)
+ throw InternalError(PALUDIS_HERE, "not implemented");
+
+ /* we've got a choice of additional requirements or version
+ * requirements. pick the best score, left to right. */
+ std::list<std::list<PackageDepSpec> >::const_iterator g_best(child_groups.end());
+ int best_score(-1);
+
+ for (std::list<std::list<PackageDepSpec> >::const_iterator g(child_groups.begin()), g_end(child_groups.end()) ;
+ g != g_end ; ++g)
+ {
+ if (g->size() != 1)
+ throw InternalError(PALUDIS_HERE, "why did that happen?");
+
+ int score(resolver.find_any_score(our_qpn_s, make_sanitised(*g->begin())));
+ if (score > best_score)
+ {
+ best_score = score;
+ g_best = g;
+ }
+ }
+
+ if (g_best == child_groups.end())
+ throw InternalError(PALUDIS_HERE, "why did that happen?");
+ apply(make_sanitised(*g_best->begin()));
+ }
+ else if (seen_unknown)
+ throw InternalError(PALUDIS_HERE, "not implemented");
+ else
+ throw InternalError(PALUDIS_HERE, "why did that happen?");
+ }
+ else if (super_complicated)
+ throw InternalError(PALUDIS_HERE, "can't");
+ else
+ {
+ /* we've got a choice of groups of packages. pick the best score, left to right. */
+ std::list<std::list<PackageDepSpec> >::const_iterator g_best(child_groups.end());
+ int best_score(-1);
+
+ for (std::list<std::list<PackageDepSpec> >::const_iterator g(child_groups.begin()), g_end(child_groups.end()) ;
+ g != g_end ; ++g)
+ {
+ int worst_score(-1);
+
+ if (g->empty())
+ throw InternalError(PALUDIS_HERE, "why did that happen?");
+
+ /* score of a group is the score of the worst child. */
+ for (std::list<PackageDepSpec>::const_iterator h(g->begin()), h_end(g->end()) ;
+ h != h_end ; ++h)
+ {
+ int score(resolver.find_any_score(our_qpn_s, make_sanitised(*h)));
+ if ((-1 == worst_score) || (score < worst_score))
+ worst_score = score;
+ }
+
+ if ((best_score == -1) || (worst_score > best_score))
+ {
+ best_score = worst_score;
+ g_best = g;
+ }
+ }
+
+ if (g_best == child_groups.end())
+ throw InternalError(PALUDIS_HERE, "why did that happen?");
+ for (std::list<PackageDepSpec>::const_iterator h(g_best->begin()), h_end(g_best->end()) ;
+ h != h_end ; ++h)
+ apply(make_sanitised(*h));
+ }
+ }
+ };
+
+ struct Finder
+ {
+ const Resolver & resolver;
+ const QPN_S our_qpn_s;
+ SanitisedDependencies & sanitised_dependencies;
+ std::list<std::tr1::shared_ptr<ActiveDependencyLabels> > labels_stack;
+
+ Finder(
+ const Resolver & r,
+ const QPN_S & q,
+ SanitisedDependencies & s,
+ const std::tr1::shared_ptr<const DependencyLabelSequence> & l) :
+ resolver(r),
+ our_qpn_s(q),
+ sanitised_dependencies(s)
+ {
+ labels_stack.push_front(make_shared_ptr(new ActiveDependencyLabels(*l)));
+ }
+
+
+ void add(const SanitisedDependency & dep)
+ {
+ sanitised_dependencies.add(dep);
+ }
+
+ SanitisedDependency make_sanitised(const PackageDepSpec & spec)
+ {
+ return make_named_values<SanitisedDependency>(
+ value_for<n::active_dependency_labels>(*labels_stack.begin()),
+ value_for<n::spec>(spec)
+ );
+ }
+
+ void visit(const DependencySpecTree::NodeType<PackageDepSpec>::Type & node)
+ {
+ add(make_sanitised(*node.spec()));
+ }
+
+ void visit(const DependencySpecTree::NodeType<BlockDepSpec>::Type &)
+ {
+ }
+
+ void visit(const DependencySpecTree::NodeType<ConditionalDepSpec>::Type & node)
+ {
+ if (node.spec()->condition_met())
+ {
+ labels_stack.push_front(make_shared_ptr(new ActiveDependencyLabels(**labels_stack.begin())));
+ std::for_each(indirect_iterator(node.begin()), indirect_iterator(node.end()), accept_visitor(*this));
+ labels_stack.pop_front();
+ }
+ }
+
+ void visit(const DependencySpecTree::NodeType<AllDepSpec>::Type & node)
+ {
+ labels_stack.push_front(make_shared_ptr(new ActiveDependencyLabels(**labels_stack.begin())));
+ std::for_each(indirect_iterator(node.begin()), indirect_iterator(node.end()), accept_visitor(*this));
+ labels_stack.pop_front();
+ }
+
+ void visit(const DependencySpecTree::NodeType<AnyDepSpec>::Type & node)
+ {
+ AnyDepSpecChildHandler h(resolver, our_qpn_s, std::tr1::bind(&Finder::make_sanitised, this, std::tr1::placeholders::_1));
+ std::for_each(indirect_iterator(node.begin()), indirect_iterator(node.end()), accept_visitor(h));
+ h.commit(
+ std::tr1::bind(&Finder::make_sanitised, this, std::tr1::placeholders::_1),
+ std::tr1::bind(&Finder::add, this, std::tr1::placeholders::_1)
+ );
+ }
+
+ void visit(const DependencySpecTree::NodeType<NamedSetDepSpec>::Type &)
+ {
+ throw InternalError(PALUDIS_HERE, "not implemented");
+ }
+
+ void visit(const DependencySpecTree::NodeType<DependencyLabelsDepSpec>::Type & node)
+ {
+ labels_stack.begin()->reset(new ActiveDependencyLabels(**labels_stack.begin(), *node.spec()));
+ }
+ };
+}
+
+namespace paludis
+{
+ template <>
+ struct Implementation<SanitisedDependencies>
+ {
+ std::list<SanitisedDependency> sanitised_dependencies;
+ };
+}
+
+SanitisedDependencies::SanitisedDependencies() :
+ PrivateImplementationPattern<SanitisedDependencies>(new Implementation<SanitisedDependencies>)
+{
+}
+
+SanitisedDependencies::~SanitisedDependencies()
+{
+}
+
+void
+SanitisedDependencies::_populate_one(
+ const Resolver & resolver,
+ const std::tr1::shared_ptr<const PackageID> & id,
+ const std::tr1::shared_ptr<const MetadataSpecTreeKey<DependencySpecTree> > (PackageID::* const pmf) () const
+ )
+{
+ Context context("When finding dependencies for '" + stringify(*id) + "' from key '" + ((*id).*pmf)()->raw_name() + "':");
+
+ Finder f(resolver, resolver.qpn_s_from_id(id), *this, ((*id).*pmf)()->initial_labels());
+ ((*id).*pmf)()->value()->root()->accept(f);
+}
+
+void
+SanitisedDependencies::populate(
+ const Resolver & resolver,
+ const std::tr1::shared_ptr<const PackageID> & id)
+{
+ Context context("When finding dependencies for '" + stringify(*id) + "':");
+
+ if (id->build_dependencies_key())
+ _populate_one(resolver, id, &PackageID::build_dependencies_key);
+ if (id->run_dependencies_key())
+ _populate_one(resolver, id, &PackageID::run_dependencies_key);
+ if (id->post_dependencies_key())
+ _populate_one(resolver, id, &PackageID::post_dependencies_key);
+}
+
+void
+SanitisedDependencies::add(const SanitisedDependency & dep)
+{
+ _imp->sanitised_dependencies.push_back(dep);
+}
+
+SanitisedDependencies::ConstIterator
+SanitisedDependencies::begin() const
+{
+ return ConstIterator(_imp->sanitised_dependencies.begin());
+}
+
+SanitisedDependencies::ConstIterator
+SanitisedDependencies::end() const
+{
+ return ConstIterator(_imp->sanitised_dependencies.end());
+}
+
+std::ostream &
+paludis::resolver::operator<< (std::ostream & s, const SanitisedDependency & d)
+{
+ s << d.spec();
+ return s;
+}
+
diff --git a/paludis/resolver/sanitised_dependencies.hh b/paludis/resolver/sanitised_dependencies.hh
new file mode 100644
index 0000000..5cb520a
--- /dev/null
+++ b/paludis/resolver/sanitised_dependencies.hh
@@ -0,0 +1,76 @@
+/* vim: set sw=4 sts=4 et foldmethod=syntax : */
+
+/*
+ * Copyright (c) 2009 Ciaran McCreesh
+ *
+ * This file is part of the Paludis package manager. Paludis is free software;
+ * you can redistribute it and/or modify it under the terms of the GNU General
+ * Public License version 2, as published by the Free Software Foundation.
+ *
+ * Paludis is distributed in the hope that it will be useful, but WITHOUT ANY
+ * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+ * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
+ * details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * this program; if not, write to the Free Software Foundation, Inc., 59 Temple
+ * Place, Suite 330, Boston, MA 02111-1307 USA
+ */
+
+#ifndef PALUDIS_GUARD_PALUDIS_RESOLVER_SANITISED_DEPENDENCIES_HH
+#define PALUDIS_GUARD_PALUDIS_RESOLVER_SANITISED_DEPENDENCIES_HH 1
+
+#include <paludis/resolver/sanitised_dependencies-fwd.hh>
+#include <paludis/resolver/resolver-fwd.hh>
+#include <paludis/util/named_value.hh>
+#include <paludis/dep_label-fwd.hh>
+#include <paludis/dep_spec.hh>
+#include <paludis/spec_tree-fwd.hh>
+#include <paludis/metadata_key-fwd.hh>
+
+namespace paludis
+{
+ namespace n
+ {
+ struct active_dependency_labels;
+ struct spec;
+ }
+
+ namespace resolver
+ {
+ struct SanitisedDependency
+ {
+ NamedValue<n::active_dependency_labels, std::tr1::shared_ptr<const ActiveDependencyLabels> > active_dependency_labels;
+ NamedValue<n::spec, PackageDepSpec> spec;
+ };
+
+ class SanitisedDependencies :
+ private PrivateImplementationPattern<SanitisedDependencies>
+ {
+ private:
+ void _populate_one(
+ const Resolver &,
+ const std::tr1::shared_ptr<const PackageID> &,
+ const std::tr1::shared_ptr<const MetadataSpecTreeKey<DependencySpecTree> > (PackageID::* const) () const
+ );
+
+ public:
+ SanitisedDependencies();
+ ~SanitisedDependencies();
+
+ void populate(
+ const Resolver &,
+ const std::tr1::shared_ptr<const PackageID> &);
+
+ void add(const SanitisedDependency & d);
+
+ struct ConstIteratorTag;
+ typedef WrappedForwardIterator<ConstIteratorTag, const SanitisedDependency> ConstIterator;
+
+ ConstIterator begin() const;
+ ConstIterator end() const;
+ };
+ }
+}
+
+#endif
diff --git a/paludis/resolver/use_installed-fwd.hh b/paludis/resolver/use_installed-fwd.hh
new file mode 100644
index 0000000..358c4c1
--- /dev/null
+++ b/paludis/resolver/use_installed-fwd.hh
@@ -0,0 +1,34 @@
+/* vim: set sw=4 sts=4 et foldmethod=syntax : */
+
+/*
+ * Copyright (c) 2009 Ciaran McCreesh
+ *
+ * This file is part of the Paludis package manager. Paludis is free software;
+ * you can redistribute it and/or modify it under the terms of the GNU General
+ * Public License version 2, as published by the Free Software Foundation.
+ *
+ * Paludis is distributed in the hope that it will be useful, but WITHOUT ANY
+ * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+ * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
+ * details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * this program; if not, write to the Free Software Foundation, Inc., 59 Temple
+ * Place, Suite 330, Boston, MA 02111-1307 USA
+ */
+
+#ifndef PALUDIS_GUARD_PALUDIS_RESOLVER_USE_INSTALLED_FWD_HH
+#define PALUDIS_GUARD_PALUDIS_RESOLVER_USE_INSTALLED_FWD_HH 1
+
+#include <paludis/util/attributes.hh>
+#include <iosfwd>
+
+namespace paludis
+{
+ namespace resolver
+ {
+#include <paludis/resolver/use_installed-se.hh>
+ }
+}
+
+#endif
diff --git a/paludis/resolver/use_installed.cc b/paludis/resolver/use_installed.cc
new file mode 100644
index 0000000..e611566
--- /dev/null
+++ b/paludis/resolver/use_installed.cc
@@ -0,0 +1,29 @@
+/* vim: set sw=4 sts=4 et foldmethod=syntax : */
+
+/*
+ * Copyright (c) 2009 Ciaran McCreesh
+ *
+ * This file is part of the Paludis package manager. Paludis is free software;
+ * you can redistribute it and/or modify it under the terms of the GNU General
+ * Public License version 2, as published by the Free Software Foundation.
+ *
+ * Paludis is distributed in the hope that it will be useful, but WITHOUT ANY
+ * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+ * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
+ * details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * this program; if not, write to the Free Software Foundation, Inc., 59 Temple
+ * Place, Suite 330, Boston, MA 02111-1307 USA
+ */
+
+#include <paludis/resolver/use_installed.hh>
+#include <paludis/util/exception.hh>
+#include <paludis/util/stringify.hh>
+#include <ostream>
+
+using namespace paludis;
+using namespace paludis::resolver;
+
+#include <paludis/resolver/use_installed-se.cc>
+
diff --git a/paludis/resolver/use_installed.hh b/paludis/resolver/use_installed.hh
new file mode 100644
index 0000000..c114c61
--- /dev/null
+++ b/paludis/resolver/use_installed.hh
@@ -0,0 +1,33 @@
+/* vim: set sw=4 sts=4 et foldmethod=syntax : */
+
+/*
+ * Copyright (c) 2009 Ciaran McCreesh
+ *
+ * This file is part of the Paludis package manager. Paludis is free software;
+ * you can redistribute it and/or modify it under the terms of the GNU General
+ * Public License version 2, as published by the Free Software Foundation.
+ *
+ * Paludis is distributed in the hope that it will be useful, but WITHOUT ANY
+ * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+ * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
+ * details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * this program; if not, write to the Free Software Foundation, Inc., 59 Temple
+ * Place, Suite 330, Boston, MA 02111-1307 USA
+ */
+
+#ifndef PALUDIS_GUARD_PALUDIS_RESOLVER_USE_INSTALLED_HH
+#define PALUDIS_GUARD_PALUDIS_RESOLVER_USE_INSTALLED_HH 1
+
+#include <paludis/resolver/use_installed-fwd.hh>
+
+namespace paludis
+{
+ namespace resolver
+ {
+
+ }
+}
+
+#endif
diff --git a/paludis/resolver/use_installed.se b/paludis/resolver/use_installed.se
new file mode 100644
index 0000000..508378a
--- /dev/null
+++ b/paludis/resolver/use_installed.se
@@ -0,0 +1,16 @@
+#!/usr/bin/env bash
+# vim: set sw=4 sts=4 et ft=sh :
+
+make_enum_UseInstalled()
+{
+ prefix ui
+ namespace paludis::resolver
+
+ key ui_never "Never"
+ key ui_only_if_transient "Only if it is transient"
+ key ui_if_same "If it is the same"
+ key ui_if_same_version "If it is the same version"
+ key ui_if_possible "If possible"
+ key ui_always "Always"
+}
+
diff --git a/src/clients/cave/Makefile.am b/src/clients/cave/Makefile.am
index 22035a2..9275170 100644
--- a/src/clients/cave/Makefile.am
+++ b/src/clients/cave/Makefile.am
@@ -30,6 +30,7 @@ command_MANS = \
cave-print-repository-formats.1 \
cave-print-sets.1 \
cave-print-sync-protocols.1 \
+ cave-resolve.1 \
cave-show.1 \
cave-sync.1
@@ -51,6 +52,7 @@ cave_LDADD = \
$(top_builddir)/paludis/libpaludis_@PALUDIS_PC_SLOT@.la \
$(top_builddir)/paludis/args/libpaludisargs_@PALUDIS_PC_SLOT@.la \
$(top_builddir)/paludis/util/libpaludisutil_@PALUDIS_PC_SLOT@.la \
+ $(top_builddir)/paludis/resolver/libpaludisresolver.a \
$(top_builddir)/src/output/liboutput.a \
$(DYNAMIC_LD_LIBS)
@@ -62,7 +64,8 @@ man_cave_LDADD = \
$(top_builddir)/paludis/args/libpaludisargs_@PALUDIS_PC_SLOT@.la \
$(top_builddir)/paludis/args/libpaludisman_@PALUDIS_PC_SLOT@.a \
$(top_builddir)/paludis/util/libpaludisutil_@PALUDIS_PC_SLOT@.la \
- $(top_builddir)/paludis/libpaludismanpagethings_@PALUDIS_PC_SLOT@.la
+ $(top_builddir)/paludis/libpaludismanpagethings_@PALUDIS_PC_SLOT@.la \
+ $(top_builddir)/paludis/resolver/libpaludisresolver.a
noinst_LIBRARIES = libcave.a
@@ -86,6 +89,7 @@ libcave_a_SOURCES = \
cmd_print_repository_formats.cc cmd_print_repository_formats.hh \
cmd_print_sets.cc cmd_print_sets.hh \
cmd_print_sync_protocols.cc cmd_print_sync_protocols.hh \
+ cmd_resolve.cc cmd_resolve.hh \
cmd_show.cc cmd_show.hh \
cmd_sync.cc cmd_sync.hh \
exceptions.cc exceptions.hh \
@@ -100,7 +104,6 @@ libcave_a_SOURCES = \
# cmd_contents.cc \
# cmd_executables.cc \
# cmd_info.cc \
-# cmd_install.cc \
# cmd_owner.cc \
# cmd_print_id_actions.cc \
# cmd_print_id_masks.cc \
diff --git a/src/clients/cave/cmd_resolve.cc b/src/clients/cave/cmd_resolve.cc
new file mode 100644
index 0000000..c9335e5
--- /dev/null
+++ b/src/clients/cave/cmd_resolve.cc
@@ -0,0 +1,488 @@
+/* vim: set sw=4 sts=4 et foldmethod=syntax : */
+
+/*
+ * Copyright (c) 2009 Ciaran McCreesh
+ *
+ * This file is part of the Paludis package manager. Paludis is free software;
+ * you can redistribute it and/or modify it under the terms of the GNU General
+ * Public License version 2, as published by the Free Software Foundation.
+ *
+ * Paludis is distributed in the hope that it will be useful, but WITHOUT ANY
+ * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+ * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
+ * details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * this program; if not, write to the Free Software Foundation, Inc., 59 Temple
+ * Place, Suite 330, Boston, MA 02111-1307 USA
+ */
+
+#include "cmd_resolve.hh"
+#include "exceptions.hh"
+
+#include "command_command_line.hh"
+
+#include <paludis/util/make_shared_ptr.hh>
+#include <paludis/util/mutex.hh>
+#include <paludis/util/stringify.hh>
+#include <paludis/args/do_help.hh>
+#include <paludis/resolver/resolver.hh>
+#include <paludis/user_dep_spec.hh>
+#include <paludis/notifier_callback.hh>
+
+#include <iostream>
+#include <cstdlib>
+
+using namespace paludis;
+using namespace cave;
+
+using std::cout;
+using std::endl;
+
+using resolver::Resolver;
+
+namespace
+{
+ struct ResolveCommandLine :
+ CaveCommandCommandLine
+ {
+ virtual std::string app_name() const
+ {
+ return "cave resolve";
+ }
+
+ virtual std::string app_synopsis() const
+ {
+ return "Display how to resolve one or more targets, and possibly then "
+ "perform that resolution.";
+ }
+
+ virtual std::string app_description() const
+ {
+ return "Displays how to resolve one or more targets. If instructed, then "
+ "executes the relevant install and uninstall actions to perform that "
+ "resolution.";
+ }
+
+// args::ArgsGroup g_execution_options;
+// args::SwitchArg a_execute;
+// args::SwitchArg a_preserve_world;
+
+// args::ArgsGroup g_convenience_options;
+// args::SwitchArg a_lazy;
+// args::SwitchArg a_complete;
+// args::SwitchArg a_everything;
+
+// args::ArgsGroup g_resolution_options;
+// args::SwitchArg a_permit_slot_uninstalls;
+// args::SwitchArg a_permit_uninstalls;
+// args::SwitchArg a_permit_downgrades;
+// args::SwitchArg a_permit_unsafe_uninstalls;
+
+// args::ArgsGroup g_cleanup_options;
+// args::SwitchArg a_purge_unused_slots;
+// args::SwitchArg a_purge_unused_packages;
+
+// args::ArgsGroup g_failure_options;
+// args::EnumArg a_continue_on_failure;
+
+// args::ArgsGroup g_display_options;
+// args::EnumArg a_show_option_descriptions;
+// args::EnumArg a_show_descriptions;
+
+ args::ArgsGroup g_explanations;
+ args::StringSetArg a_explain;
+
+// args::ArgsGroup g_phase_options;
+// args::StringSetArg a_skip_phase;
+// args::StringSetArg a_abort_at_phase;
+// args::StringSetArg a_skip_until_phase;
+// args::EnumArg a_change_phases_for;
+
+// args::ArgsGroup g_reinstall_options;
+// args::EnumArg a_reinstall_targets;
+// args::EnumArg a_reinstall;
+// args::EnumArg a_reinstall_scm;
+// args::SwitchArg a_reinstall_for_removals;
+
+// args::ArgsGroup g_slot_options;
+// args::EnumArg a_target_slots;
+// args::EnumArg a_slots;
+
+// args::ArgsGroup g_dependency_options;
+// args::SwitchArg a_follow_installed_build_dependencies;
+// args::SwitchArg a_ignore_installed_dependencies;
+
+// args::ArgsGroup g_suggestion_options;
+// args::EnumArg a_suggestions;
+// args::EnumArg a_recommendations;
+// args::StringSetArg a_take;
+// args::StringSetArg a_take_from;
+// args::StringSetArg a_discard;
+// args::StringSetArg a_discard_from;
+
+// args::ArgsGroup g_package_options;
+// args::StringSetArg a_prefer;
+// args::StringSetArg a_avoid;
+
+// args::ArgsGroup g_ordering_options;
+// args::StringSetArg a_early;
+// args::StringSetArg a_late;
+
+// args::ArgsGroup g_preset_options;
+// args::StringSetArg a_soft_preset;
+// args::StringSetArg a_fixed_preset;
+
+// args::ArgsGroup g_destination_options;
+// args::SwitchArg a_fetch;
+// args::SwitchArg a_create_binaries;
+// args::SwitchArg a_install_to_chroot;
+// args::SwitchArg a_install_to_root;
+
+ args::ArgsGroup g_dump_options;
+ args::SwitchArg a_dump;
+ args::SwitchArg a_dump_dependencies;
+
+ ResolveCommandLine() :
+// g_execution_options(this, "Execution Options", "Control execution."),
+// a_execute(&g_execution_options, "execute", 'x', "Execute the suggested actions", true),
+// a_preserve_world(&g_execution_options, "preserve-world", '1', "Do not modify the 'world' set", true),
+//
+// g_convenience_options(this, "Convenience Options", "Broad behaviour options."),
+// a_lazy(&g_convenience_options, "lazy", 'z', "Do as little work as possible.", true),
+// a_complete(&g_convenience_options, "complete", 'c', "Do all optional work.", true),
+// a_everything(&g_convenience_options, "everything", 'e', "Do all optional work, and also reinstall", true),
+//
+// g_resolution_options(this, "Resolution Options", "Resolution options."),
+// a_permit_slot_uninstalls(&g_resolution_options, "permit-slot-uninstalls", '\0',
+// "Uninstall slots of packages if they are blocked by other slots of that package", true),
+// a_permit_uninstalls(&g_resolution_options, "permit-uninstalls", '\0',
+// "Uninstall packages that are blocked", true),
+// a_permit_downgrades(&g_resolution_options, "permit-downgrades", '\0', "Permit downgrades", true),
+// a_permit_unsafe_uninstalls(&g_resolution_options, "permit-unsafe-uninstalls", '\0',
+// "Permit uninstalls even if the uninstall isn't known to be safe", true),
+//
+// g_cleanup_options(this, "Cleanup Options", "Cleanup options."),
+// a_purge_unused_slots(&g_cleanup_options, "purge-unused-slots", '\0',
+// "Purge slots that are no longer used after an uninstall or clean", true),
+// a_purge_unused_packages(&g_cleanup_options, "purge-unused-packages", '\0',
+// "Purge packages that are no longer used after an uninstall or clean", true),
+//
+// g_failure_options(this, "Failure Options", "Failure handling options."),
+// a_continue_on_failure(&g_failure_options, "continue-on-failure", '\0',
+// "Whether to continue after an error occurs",
+// args::EnumArg::EnumArgOptions
+// ("if-fetching", "Only if we are just fetching packages")
+// ("never", "Never")
+// ("if-satisfied", "If remaining packages' dependencies are satisfied")
+// ("if-independent", "If remaining packages do not depend upon any failing package")
+// ("always", "Always (dangerous)"),
+// "if-fetching"),
+//
+// g_display_options(this, "Display Options", "Options relating to the resolution display."),
+// a_show_option_descriptions(&g_display_options, "show-option-descriptions", '\0',
+// "Whether to display descriptions for package options",
+// args::EnumArg::EnumArgOptions
+// ("none", "Don't show any descriptions")
+// ("new", "Show for any new options")
+// ("changed", "Show for new or changed options")
+// ("all", "Show all options"),
+// "changed"
+// ),
+// a_show_descriptions(&g_display_options, "show-descriptions", '\0',
+// "Whether to display package descriptions",
+// args::EnumArg::EnumArgOptions
+// ("none", "Don't show any descriptions")
+// ("new", "Show for new packages")
+// ("all", "Show for all packages"),
+// "new"
+// ),
+//
+ g_explanations(this, "Explanations", "Options requesting the resolver explain a particular decision "
+ "that it made"),
+ a_explain(&g_explanations, "explain", '\0', "Explain why the resolver made a particular decision. The "
+ "argument is a package dependency specification, so --explain dev-libs/boost or --explain qt:3"
+ " or even --explain '*/*' (although --dump is a better way of getting highly noisy debug output)."),
+
+// g_phase_options(this, "Phase Options", "Options controlling which phases to execute. No sanity checking "
+// "is done, allowing you to shoot as many feet off as you desire. Phase names do not have the "
+// "src_, pkg_ or builtin_ prefix, so 'init', 'preinst', 'unpack', 'merge', 'strip' etc."),
+// a_skip_phase(&g_phase_options, "skip-phase", '\0', "Skip the named phases"),
+// a_abort_at_phase(&g_phase_options, "abort-at-phase", '\0', "Abort when a named phase is encounted"),
+// a_skip_until_phase(&g_phase_options, "skip-until-phase", '\0', "Skip every phase until a named phase is encounted"),
+// a_change_phases_for(&g_phase_options, "change-phases-for", '\0',
+// "Control to which package or packages these phase options apply",
+// args::EnumArg::EnumArgOptions
+// ("all", "All packages")
+// ("first", "Only the first package on the list")
+// ("last", "Only the last package on the list"),
+// "all"),
+//
+// g_reinstall_options(this, "Reinstall Options", "Control whether packages are reinstalled."),
+// a_reinstall_targets(&g_reinstall_options, "reinstall-targets", 'R',
+// "Select whether to reinstall target packages",
+// args::EnumArg::EnumArgOptions
+// ("auto", 'x', "If the target is a set, if-necessary, otherwise always")
+// ("always", 'a', "Always")
+// ("unless-transient", 't', "Unless the target is transient (e.g. from 'importare')"
+// " (default if --everything)")
+// ("unless-same", 's', "Unless the target is the same (version, option flags)")
+// ("unless-same-version", 'v', "Unless the target is the same version")
+// ("if-necessary", 'i', "If necessary")
+// ("never", 'n', "Never"),
+// "auto"
+// ),
+// a_reinstall(&g_reinstall_options, "reinstall", 'r',
+// "Select whether to reinstall packages that are not targets",
+// args::EnumArg::EnumArgOptions
+// ("always", 'a', "Always")
+// ("unless-transient", 't', "Unless the target is transient (e.g. from 'importare')"
+// " (default if --everything)")
+// ("unless-same", 's', "Unless the target is the same (version, option flags)"
+// " (default if --complete)")
+// ("unless-same-version", 'v', "Unless the target is the same version")
+// ("if-necessary", 'i', "If necessary")
+// ("never", 'n', "Never"),
+// "if-necessary"
+// ),
+// a_reinstall_scm(&g_reinstall_options, "reinstall-scm", 's',
+// "Select whether to reinstall SCM packages that would otherwise not be reinstalled",
+// args::EnumArg::EnumArgOptions
+// ("always", 'a', "Always")
+// ("daily", 'd', "If they were installed more than a day ago")
+// ("weekly", 'w', "If they were installed more than a week ago")
+// ("never", 'n', "Never"),
+// "weekly"
+// ),
+// a_reinstall_for_removals(&g_reinstall_options, "reinstall-for-removals", '\0',
+// "Select whether to rebuild packages if rebuilding would avoid an unsafe removal", true),
+//
+// g_slot_options(this, "Slot Options", "Control which slots are considered."),
+// a_target_slots(&g_slot_options, "target-slots", 'S',
+// "Which slots to consider for targets",
+// args::EnumArg::EnumArgOptions
+// ("best-or-installed", 'x', "Consider the best slot, if it is not installed, "
+// "or all installed slots otherwise")
+// ("installed-or-best", 'i', "Consider all installed slots, or the best "
+// "installable slot if nothing is installed")
+// ("all", 'a', "Consider all installed slots and the best installable slot"
+// " (default if --complete or --everything)")
+// ("best", 'b', "Consider the best installable slot only"
+// " (default if --lazy)"),
+// "best-or-installed"
+// ),
+// a_slots(&g_slot_options, "slots", 's',
+// "Which slots to consider for packages that are not targets",
+// args::EnumArg::EnumArgOptions
+// ("best-or-installed", 'x', "Consider the best slot, if it is not installed, "
+// "or all installed slots otherwise")
+// ("installed-or-best", 'i', "Consider all installed slots, or the best "
+// "installable slot if nothing is installed")
+// ("all", 'a', "Consider all installed slots and the best installable slot"
+// " (default if --complete or --everything)")
+// ("best", 'b', "Consider the best installable slot only"
+// " (default if --lazy)"),
+// "best-or-installed"
+// ),
+//
+// g_dependency_options(this, "Dependency Options", "Control which dependencies are followed."),
+// a_follow_installed_build_dependencies(&g_dependency_options, "follow-installed-build-dependencies", 'D',
+// "Follow build dependencies for installed packages (default if --complete or --everything", true),
+// a_ignore_installed_dependencies(&g_dependency_options, "ignore-installed-dependencies", 'd',
+// "Ignore (non-build) dependencies for installed packages (default if --lazy)", true),
+//
+// g_suggestion_options(this, "Suggestion Options", "Control whether suggestions are taken. Suggestions that are "
+// "already installed are instead treated as hard dependencies."),
+// a_suggestions(&g_suggestion_options, "suggestions", '\0', "How to treat suggestions and recommendations",
+// args::EnumArg::EnumArgOptions
+// ("ignore", "Ignore suggestions")
+// ("display", "Display suggestions, but do not take them unless explicitly told to do so")
+// ("take", "Take all suggestions"),
+// "display"),
+// a_recommendations(&g_suggestion_options, "recommendations", '\0', "How to treat recommendations",
+// args::EnumArg::EnumArgOptions
+// ("ignore", "Ignore recommendations")
+// ("display", "Display recommendations, but do not take them unless explicitly told to do so")
+// ("take", "Take all recommendations"),
+// "take"),
+// a_take(&g_suggestion_options, "take", '\0', "Take any suggestion matching the supplied package specification"
+// " (e.g. --take 'app-vim/securemodelines' or --take 'app-vim/*')"),
+// a_take_from(&g_suggestion_options, "take-from", '\0', "Take all suggestions made by any package matching the "
+// "supplied package specification"),
+// a_discard(&g_suggestion_options, "discard", '\0', "Discard any suggestion matching the supplied package specification"),
+// a_discard_from(&g_suggestion_options, "discard-from", '\0', "Discard all suggestions made by any package matching the "
+// "supplied package specification"),
+//
+// g_package_options(this, "Package Selection Options", "Control which packages are selected."),
+// a_prefer(&g_package_options, "prefer", '\0', "If there is a choice, prefer the specified package names"),
+// a_avoid(&g_package_options, "avoid", '\0', "If there is a choice, avoid the specified package names"),
+//
+// g_ordering_options(this, "Package Ordering Options", "Control the order in which packages are installed"),
+// a_early(&g_ordering_options, "early", '\0', "Try to install the specified package name as early as possible"),
+// a_late(&g_ordering_options, "late", '\0', "Try to install the specified package name as late as possible"),
+//
+// g_preset_options(this, "Preset Options", "Preset various constraints."),
+// a_soft_preset(&g_preset_options, "soft-preset", '\0', "Preset a given constraint, but allow the resolver to "
+// "override it. For example, --soft-preset cat/pkg::installed will tell the resolver to use the installed "
+// "cat/pkg if possible."),
+// a_fixed_preset(&g_preset_options, "fixed-preset", '\0', "Preset a given constraint, and do not allow the resolver to "
+// "override it. For example, --fixed-preset cat/pkg::installed will force the resolver to use the installed "
+// "cat/pkg, generating an error if it cannot."),
+//
+// g_destination_options(this, "Destination Options", "Control to which destinations packages are installed. "
+// "If no options from this group are selected, install only to /. Otherwise, install to all of the "
+// "specified destinations, and install to / as necessary to satisfy build dependencies."),
+// a_fetch(&g_destination_options, "fetch", 'f', "Only fetch packages, do not install anything", true),
+// a_create_binaries(&g_destination_options, "create-binaries", '\0', "Create binary packages", true),
+// a_install_to_chroot(&g_destination_options, "install-to-chroot", '\0', "Install packages to the environment-configured chroot", true),
+// a_install_to_root(&g_destination_options, "install-to-root", '\0', "Install packages to /", true),
+
+ g_dump_options(this, "Dump Options", "Dump the resolver's state to stdout after completion, or when an "
+ "error occurs. For debugging purposes; produces rather a lot of noise."),
+ a_dump(&g_dump_options, "dump", '\0', "Dump debug output", true),
+ a_dump_dependencies(&g_dump_options, "dump-dependencies", '\0', "If dumping, also dump dependency information", true)
+ {
+ add_usage_line("[ -x|--execute ] [ -z|--lazy or -c|--complete or -e|--everything ] spec ...");
+ add_usage_line("[ -x|--execute ] [ -z|--lazy or -c|--complete or -e|--everything ] set");
+ }
+ };
+
+ struct DisplayCallback
+ {
+ mutable Mutex mutex;
+ mutable int width, metadata, steps;
+
+ DisplayCallback() :
+ width(0),
+ metadata(0),
+ steps(0)
+ {
+ std::cout << "Resolving: " << std::flush;
+ }
+
+ ~DisplayCallback()
+ {
+ std::cout << std::endl;
+ }
+
+ void operator() (const NotifierCallbackEvent & event) const
+ {
+ event.accept(*this);
+ }
+
+ void visit(const NotifierCallbackGeneratingMetadataEvent &) const
+ {
+ Lock lock(mutex);
+ ++metadata;
+ update();
+ }
+
+ void visit(const NotifierCallbackResolverStepEvent &) const
+ {
+ Lock lock(mutex);
+ ++steps;
+ update();
+ }
+
+ void update() const
+ {
+ std::string s;
+ if (0 != steps)
+ s.append("steps: " + stringify(steps));
+
+ if (0 != metadata)
+ {
+ if (! s.empty())
+ s.append(", ");
+ s.append("metadata: " + stringify(metadata));
+ }
+
+ std::cout << std::string(width, '\010') << s << std::flush;
+ width = s.length();
+ }
+ };
+
+ void add_resolver_targets(
+ const std::tr1::shared_ptr<Environment> & env,
+ const std::tr1::shared_ptr<Resolver> & resolver,
+ const ResolveCommandLine & cmdline)
+ {
+ Context context("When adding targets from commandline:");
+
+ if (cmdline.begin_parameters() == cmdline.end_parameters())
+ throw args::DoHelp("Must specify at least one target");
+
+ bool seen_sets(false), seen_packages(false);
+ for (ResolveCommandLine::ParametersConstIterator p(cmdline.begin_parameters()), p_end(cmdline.end_parameters()) ;
+ p != p_end ; ++p)
+ {
+ try
+ {
+ resolver->add_target(parse_user_package_dep_spec(*p, env.get(),
+ UserPackageDepSpecOptions() + updso_throw_if_set),
+ resolver::ui_never);
+ if (seen_sets)
+ throw args::DoHelp("Cannot specify both set and package targets");
+ seen_packages = true;
+ }
+ catch (const GotASetNotAPackageDepSpec &)
+ {
+ if (seen_packages)
+ throw args::DoHelp("Cannot specify both set and package targets");
+ if (seen_sets)
+ throw args::DoHelp("Cannot specify multiple set targets");
+
+ resolver->add_set(SetName(*p), resolver::ui_if_same);
+ seen_sets = true;
+ }
+ }
+ }
+}
+
+bool
+ResolveCommand::important() const
+{
+ return true;
+}
+
+int
+ResolveCommand::run(
+ const std::tr1::shared_ptr<Environment> & env,
+ const std::tr1::shared_ptr<const Sequence<std::string > > & args
+ )
+{
+ ResolveCommandLine cmdline;
+ cmdline.run(args, "CAVE", "CAVE_RESOLVE_OPTIONS", "CAVE_RESOLVE_CMDLINE");
+
+ if (cmdline.a_help.specified())
+ {
+ cout << cmdline;
+ return EXIT_SUCCESS;
+ }
+
+ int retcode(0);
+
+ std::tr1::shared_ptr<Resolver> resolver(new Resolver(env.get()));
+ try
+ {
+ DisplayCallback display_callback;
+ ScopedNotifierCallback display_callback_holder(env.get(),
+ NotifierCallbackFunction(std::tr1::cref(display_callback)));
+ add_resolver_targets(env, resolver, cmdline);
+ resolver->resolve();
+ }
+ catch (...)
+ {
+ // dump_if_requested(resolver);
+ throw;
+ }
+
+ return retcode;
+}
+
+std::tr1::shared_ptr<args::ArgsHandler>
+ResolveCommand::make_doc_cmdline()
+{
+ return make_shared_ptr(new ResolveCommandLine);
+}
+
diff --git a/src/clients/cave/cmd_resolve.hh b/src/clients/cave/cmd_resolve.hh
new file mode 100644
index 0000000..9d7edbf
--- /dev/null
+++ b/src/clients/cave/cmd_resolve.hh
@@ -0,0 +1,46 @@
+/* vim: set sw=4 sts=4 et foldmethod=syntax : */
+
+/*
+ * Copyright (c) 2009 Ciaran McCreesh
+ *
+ * This file is part of the Paludis package manager. Paludis is free software;
+ * you can redistribute it and/or modify it under the terms of the GNU General
+ * Public License version 2, as published by the Free Software Foundation.
+ *
+ * Paludis is distributed in the hope that it will be useful, but WITHOUT ANY
+ * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+ * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
+ * details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * this program; if not, write to the Free Software Foundation, Inc., 59 Temple
+ * Place, Suite 330, Boston, MA 02111-1307 USA
+ */
+
+#ifndef PALUDIS_GUARD_SRC_CLIENTS_CAVE_CMD_RESOLVE_HH
+#define PALUDIS_GUARD_SRC_CLIENTS_CAVE_CMD_RESOLVE_HH 1
+
+#include "command.hh"
+
+namespace paludis
+{
+ namespace cave
+ {
+ class PALUDIS_VISIBLE ResolveCommand :
+ public Command
+ {
+ public:
+ bool important() const;
+
+ int run(
+ const std::tr1::shared_ptr<Environment> &,
+ const std::tr1::shared_ptr<const Sequence<std::string > > & args
+ );
+
+ std::tr1::shared_ptr<args::ArgsHandler> make_doc_cmdline();
+ };
+ }
+}
+
+
+#endif
diff --git a/src/clients/cave/command_factory.cc b/src/clients/cave/command_factory.cc
index 1f2d9e1..c07df95 100644
--- a/src/clients/cave/command_factory.cc
+++ b/src/clients/cave/command_factory.cc
@@ -1,7 +1,7 @@
/* vim: set sw=4 sts=4 et foldmethod=syntax : */
/*
- * Copyright (c) 2008 Ciaran McCreesh
+ * Copyright (c) 2008, 2009 Ciaran McCreesh
*
* This file is part of the Paludis package manager. Paludis is free software;
* you can redistribute it and/or modify it under the terms of the GNU General
@@ -40,6 +40,7 @@
#include "cmd_print_repository_formats.hh"
#include "cmd_print_sets.hh"
#include "cmd_print_sync_protocols.hh"
+#include "cmd_resolve.hh"
#include "cmd_show.hh"
#include "cmd_sync.hh"
@@ -83,6 +84,7 @@ CommandFactory::CommandFactory() :
_imp->handlers.insert(std::make_pair("print-repository-formats", make_command<PrintRepositoryFormatsCommand>));
_imp->handlers.insert(std::make_pair("print-sets", make_command<PrintSetsCommand>));
_imp->handlers.insert(std::make_pair("print-sync-protocols", make_command<PrintSyncProtocolsCommand>));
+ _imp->handlers.insert(std::make_pair("resolve", make_command<ResolveCommand>));
_imp->handlers.insert(std::make_pair("show", make_command<ShowCommand>));
_imp->handlers.insert(std::make_pair("sync", make_command<SyncCommand>));
}