Make purges faster, and test

Fixes: ticket:892

7 files changed, 208 insertions, 6 deletions

diff --git a/.gitignore b/.gitignore
index 2bd6552..24206a7 100644
--- a/.gitignore
+++ b/.gitignore
@@ -330,6 +330,7 @@ paludis-*.*.*.tar.bz2
 /paludis/resolver/resolver_TEST_cycles
 /paludis/resolver/resolver_TEST_errors
 /paludis/resolver/resolver_TEST_fetches
+/paludis/resolver/resolver_TEST_purges
 /paludis/resolver/resolver_TEST_serialisation
 /paludis/resolver/resolver_TEST_simple
 /paludis/resolver/resolver_TEST_suggestions
diff --git a/paludis/resolver/Makefile.am b/paludis/resolver/Makefile.am
index 8ba96d0..94d7e78 100644
--- a/paludis/resolver/Makefile.am
+++ b/paludis/resolver/Makefile.am
@@ -113,6 +113,7 @@ TESTS = \
 	resolver_TEST_continue_on_failure \
 	resolver_TEST_uninstalls \
 	resolver_TEST_fetches \
+	resolver_TEST_purges \
 	$(virtuals_tests)
 endif
 
@@ -129,7 +130,8 @@ check_SCRIPTS = \
 	resolver_TEST_errors_setup.sh resolver_TEST_errors_cleanup.sh \
 	resolver_TEST_continue_on_failure_setup.sh resolver_TEST_continue_on_failure_cleanup.sh \
 	resolver_TEST_uninstalls_setup.sh resolver_TEST_uninstalls_cleanup.sh \
-	resolver_TEST_fetches_setup.sh resolver_TEST_fetches_cleanup.sh
+	resolver_TEST_fetches_setup.sh resolver_TEST_fetches_cleanup.sh \
+	resolver_TEST_purges_setup.sh resolver_TEST_purges_cleanup.sh
 
 check_LIBRARIES = libpaludisresolvertest.a
 
@@ -280,6 +282,19 @@ resolver_TEST_fetches_LDADD = \
 
 resolver_TEST_fetches_CXXFLAGS = $(AM_CXXFLAGS) @PALUDIS_CXXFLAGS_NO_DEBUGGING@
 
+resolver_TEST_purges_SOURCES = resolver_TEST_purges.cc
+
+resolver_TEST_purges_LDADD = \
+	libpaludisresolvertest.a \
+	$(top_builddir)/paludis/util/test_extras.o \
+	$(top_builddir)/test/libtest.a \
+	$(top_builddir)/paludis/libpaludis_@PALUDIS_PC_SLOT@.la \
+	$(top_builddir)/paludis/util/libpaludisutil_@PALUDIS_PC_SLOT@.la \
+	libpaludisresolver.a \
+	$(DYNAMIC_LD_LIBS)
+
+resolver_TEST_purges_CXXFLAGS = $(AM_CXXFLAGS) @PALUDIS_CXXFLAGS_NO_DEBUGGING@
+
 use_existing-se.hh : use_existing.se $(top_srcdir)/misc/make_se.bash
 	if ! $(top_srcdir)/misc/make_se.bash --header $(srcdir)/use_existing.se > $@ ; then rm -f $@ ; exit 1 ; fi
 
diff --git a/paludis/resolver/decider.cc b/paludis/resolver/decider.cc
index a5dc18f..e4c82a6 100644
--- a/paludis/resolver/decider.cc
+++ b/paludis/resolver/decider.cc
@@ -1757,7 +1757,7 @@ Decider::purge()
     std::copy(have_now->begin(), have_now->end(), have_now_seq->back_inserter());
 
     const std::tr1::shared_ptr<const PackageIDSet> world(_collect_world(have_now));
-    const std::tr1::shared_ptr<const PackageIDSet> world_plus_deps(_accumulate_deps(world, have_now_seq));
+    const std::tr1::shared_ptr<const PackageIDSet> world_plus_deps(_accumulate_deps(world, have_now_seq, true));
 
     _imp->env->trigger_notifier_callback(NotifierCallbackResolverStageEvent("Calculating Unused"));
 
@@ -1963,8 +1963,8 @@ Decider::_resolve_purges()
     const std::tr1::shared_ptr<PackageIDSequence> will_eventually_have(new PackageIDSequence);
     std::copy(will_eventually_have_set->begin(), will_eventually_have_set->end(), will_eventually_have->back_inserter());
 
-    const std::tr1::shared_ptr<const PackageIDSet> used_originally(_accumulate_deps(going_away, will_eventually_have));
-    const std::tr1::shared_ptr<const PackageIDSet> used_afterwards(_accumulate_deps(newly_available, will_eventually_have));
+    const std::tr1::shared_ptr<const PackageIDSet> used_originally(_accumulate_deps(going_away, will_eventually_have, false));
+    const std::tr1::shared_ptr<const PackageIDSet> used_afterwards(_accumulate_deps(newly_available, will_eventually_have, false));
 
     const std::tr1::shared_ptr<PackageIDSet> used_originally_and_not_going_away(new PackageIDSet);
     std::set_difference(used_originally->begin(), used_originally->end(),
@@ -2038,7 +2038,8 @@ Decider::_collect_installed() const
 const std::tr1::shared_ptr<const PackageIDSet>
 Decider::_accumulate_deps(
         const std::tr1::shared_ptr<const PackageIDSet> & start,
-        const std::tr1::shared_ptr<const PackageIDSequence> & will_eventually_have) const
+        const std::tr1::shared_ptr<const PackageIDSequence> & will_eventually_have,
+        const bool recurse) const
 {
     const std::tr1::shared_ptr<PackageIDSet> result(new PackageIDSet), done(new PackageIDSet);
     std::copy(start->begin(), start->end(), result->inserter());
@@ -2054,9 +2055,13 @@ Decider::_accumulate_deps(
             _imp->env->trigger_notifier_callback(NotifierCallbackResolverStepEvent());
 
             done->insert(*i);
+
             const std::tr1::shared_ptr<const PackageIDSet> depped_upon(_collect_depped_upon(*i, will_eventually_have));
             std::copy(depped_upon->begin(), depped_upon->end(), result->inserter());
         }
+
+        if (! recurse)
+            break;
     }
 
     return result;
diff --git a/paludis/resolver/decider.hh b/paludis/resolver/decider.hh
index 708614f..63dde2b 100644
--- a/paludis/resolver/decider.hh
+++ b/paludis/resolver/decider.hh
@@ -234,7 +234,8 @@ namespace paludis
 
                 const std::tr1::shared_ptr<const PackageIDSet> _accumulate_deps(
                         const std::tr1::shared_ptr<const PackageIDSet> &,
-                        const std::tr1::shared_ptr<const PackageIDSequence> &) const PALUDIS_ATTRIBUTE((warn_unused_result));
+                        const std::tr1::shared_ptr<const PackageIDSequence> &,
+                        const bool recurse) const PALUDIS_ATTRIBUTE((warn_unused_result));
 
                 const std::tr1::shared_ptr<const PackageIDSet> _collect_depped_upon(
                         const std::tr1::shared_ptr<const PackageID> &,
diff --git a/paludis/resolver/resolver_TEST_purges.cc b/paludis/resolver/resolver_TEST_purges.cc
new file mode 100644
index 0000000..d7d92c3
--- /dev/null
+++ b/paludis/resolver/resolver_TEST_purges.cc
@@ -0,0 +1,125 @@
+/* vim: set sw=4 sts=4 et foldmethod=syntax : */
+
+/*
+ * Copyright (c) 2010 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/resolver_functions.hh>
+#include <paludis/resolver/resolution.hh>
+#include <paludis/resolver/decision.hh>
+#include <paludis/resolver/constraint.hh>
+#include <paludis/resolver/resolvent.hh>
+#include <paludis/resolver/suggest_restart.hh>
+#include <paludis/environments/test/test_environment.hh>
+#include <paludis/util/make_named_values.hh>
+#include <paludis/util/options.hh>
+#include <paludis/util/wrapped_forward_iterator-impl.hh>
+#include <paludis/util/make_shared_ptr.hh>
+#include <paludis/util/sequence.hh>
+#include <paludis/util/map.hh>
+#include <paludis/util/indirect_iterator-impl.hh>
+#include <paludis/util/accept_visitor.hh>
+#include <paludis/util/make_shared_copy.hh>
+#include <paludis/user_dep_spec.hh>
+#include <paludis/repository_factory.hh>
+#include <paludis/package_database.hh>
+
+#include <paludis/resolver/resolver_test.hh>
+#include <test/test_runner.hh>
+#include <test/test_framework.hh>
+
+#include <list>
+#include <tr1/functional>
+#include <algorithm>
+#include <map>
+
+using namespace paludis;
+using namespace paludis::resolver;
+using namespace paludis::resolver::resolver_test;
+using namespace test;
+
+namespace
+{
+    struct ResolverPurgesTestCase : ResolverTestCase
+    {
+        ResolverPurgesTestCase(const std::string & s) :
+            ResolverTestCase("purges", s, "exheres-0", "exheres")
+        {
+        }
+    };
+
+    UseExisting
+    use_existing_if_possible_except_target(
+            const std::tr1::shared_ptr<const Resolution> &,
+            const PackageDepSpec & s,
+            const std::tr1::shared_ptr<const Reason> &)
+    {
+        if (s.package_ptr() && s.package_ptr()->package() == PackageNamePart("target"))
+            return ue_never;
+        else
+            return ue_if_possible;
+    }
+}
+
+namespace test_cases
+{
+    struct TestPurges : ResolverPurgesTestCase
+    {
+        TestPurges() :
+            ResolverPurgesTestCase("purges")
+        {
+            install("purges", "target", "0")->build_dependencies_key()->set_from_string("purges/still-used-dep purges/old-dep purges/unrelated-dep");
+            install("purges", "old-dep", "0");
+            install("purges", "still-used-dep", "0");
+            install("purges", "unrelated-dep", "0");
+            install("purges", "unrelated", "0")->build_dependencies_key()->set_from_string("purges/unrelated-dep");
+
+            allowed_to_remove_names->insert(QualifiedPackageName("purges/old-dep"));
+        }
+
+        virtual ResolverFunctions get_resolver_functions(InitialConstraints & initial_constraints)
+        {
+            ResolverFunctions result(ResolverPurgesTestCase::get_resolver_functions(initial_constraints));
+            result.get_use_existing_fn() = std::tr1::bind(&use_existing_if_possible_except_target, std::tr1::placeholders::_1,
+                    std::tr1::placeholders::_2, std::tr1::placeholders::_3);
+            return result;
+        }
+
+        void run()
+        {
+            std::tr1::shared_ptr<const Resolved> resolved(get_resolved("purges/target"));
+            check_resolved(resolved,
+                    n::taken_change_or_remove_decisions() = make_shared_copy(DecisionChecks()
+                        .change(QualifiedPackageName("purges/new-dep"))
+                        .remove(QualifiedPackageName("purges/old-dep"))
+                        .change(QualifiedPackageName("purges/target"))
+                        .finished()),
+                    n::taken_unable_to_make_decisions() = make_shared_copy(DecisionChecks()
+                        .finished()),
+                    n::taken_unconfirmed_decisions() = make_shared_copy(DecisionChecks()
+                        .finished()),
+                    n::taken_unorderable_decisions() = make_shared_copy(DecisionChecks()
+                        .finished()),
+                    n::untaken_change_or_remove_decisions() = make_shared_copy(DecisionChecks()
+                        .finished()),
+                    n::untaken_unable_to_make_decisions() = make_shared_copy(DecisionChecks()
+                        .finished())
+                    );
+        }
+    } test_purges;
+}
+
diff --git a/paludis/resolver/resolver_TEST_purges_cleanup.sh b/paludis/resolver/resolver_TEST_purges_cleanup.sh
new file mode 100755
index 0000000..504a49a
--- /dev/null
+++ b/paludis/resolver/resolver_TEST_purges_cleanup.sh
@@ -0,0 +1,9 @@
+#!/usr/bin/env bash
+# vim: set ft=sh sw=4 sts=4 et :
+
+if [ -d resolver_TEST_purges_dir ] ; then
+    rm -fr resolver_TEST_purges_dir
+else
+    true
+fi
+
diff --git a/paludis/resolver/resolver_TEST_purges_setup.sh b/paludis/resolver/resolver_TEST_purges_setup.sh
new file mode 100755
index 0000000..f7a210a
--- /dev/null
+++ b/paludis/resolver/resolver_TEST_purges_setup.sh
@@ -0,0 +1,46 @@
+#!/usr/bin/env bash
+# vim: set ft=sh sw=4 sts=4 et :
+
+mkdir resolver_TEST_purges_dir || exit 1
+cd resolver_TEST_purges_dir || exit 1
+
+mkdir -p build
+mkdir -p distdir
+mkdir -p installed
+
+mkdir -p repo/{profiles/profile,metadata}
+
+cd repo
+echo "repo" > profiles/repo_name
+: > metadata/categories.conf
+
+# purges
+echo 'purges' >> metadata/categories.conf
+
+mkdir -p 'packages/purges/target'
+cat <<END > packages/purges/target/target-1.exheres-0
+SUMMARY="target"
+PLATFORMS="test"
+SLOT="0"
+DEPENDENCIES="
+    purges/still-used-dep
+    purges/new-dep
+    "
+END
+
+mkdir -p 'packages/purges/new-dep'
+cat <<END > packages/purges/new-dep/new-dep-1.exheres-0
+SUMMARY="dep"
+PLATFORMS="test"
+SLOT="0"
+END
+
+mkdir -p 'packages/purges/still-used-dep'
+cat <<END > packages/purges/still-used-dep/still-used-dep-1.exheres-0
+SUMMARY="dep"
+PLATFORMS="test"
+SLOT="0"
+END
+
+cd ..
+