Do sets differently

Sets from repositories are now named setname::repo, and we automatically
create a master setname containing all of those sets.

Cache sets cleanly whilst we're at it.

Fixes: ticket:746

61 files changed, 817 insertions, 767 deletions

diff --git a/paludis/Makefile.am.m4 b/paludis/Makefile.am.m4
index d59805a..9bf8711 100644
--- a/paludis/Makefile.am.m4
+++ b/paludis/Makefile.am.m4
@@ -20,7 +20,6 @@ $1_TEST_LDADD = \
 	$(top_builddir)/paludis/util/test_extras.o \
 	$(top_builddir)/test/libtest.a \
 	$(top_builddir)/paludis/environments/test/libpaludistestenvironment_@PALUDIS_PC_SLOT@.la \
-	$(top_builddir)/paludis/repositories/e/libpaludiserepository_@PALUDIS_PC_SLOT@.la \
 	$(top_builddir)/paludis/repositories/fake/libpaludisfakerepository_@PALUDIS_PC_SLOT@.la \
 	libpaludis_@PALUDIS_PC_SLOT@.la \
 	$(top_builddir)/paludis/util/libpaludisutil_@PALUDIS_PC_SLOT@.la \
diff --git a/paludis/environment.hh b/paludis/environment.hh
index da6d76e..cf9465d 100644
--- a/paludis/environment.hh
+++ b/paludis/environment.hh
@@ -305,6 +305,30 @@ namespace paludis
             ///\{
 
             /**
+             * Add a package set.
+             *
+             * Generally called by repositories, when Repository::populate_sets is called.
+             *
+             * \param base_name The basic name of the set, such as 'security'.
+             *
+             * \param combined_name The name to use for this set when combine is true, such
+             *     as 'security.myrepo'. If combine is false, should be the same as base_name.
+             *
+             * \param func A function that returns the set.
+             *
+             * \param combine If true, rename the set from foo to foo.reponame, and make
+             *     the foo set contain foo.reponame, along with any other repositories'
+             *     sets named foo. If false, throw if the set already exists.
+             *
+             * \since 0.40
+             */
+            virtual void add_set(
+                    const SetName & base_name,
+                    const SetName & combined_name,
+                    const std::tr1::function<std::tr1::shared_ptr<const SetSpecTree> ()> & func,
+                    const bool combine) const = 0;
+
+            /**
              * Return all known named sets.
              */
             virtual std::tr1::shared_ptr<const SetNameSet> set_names() const
diff --git a/paludis/environment_implementation.cc b/paludis/environment_implementation.cc
index 077e537..a49fb84 100644
--- a/paludis/environment_implementation.cc
+++ b/paludis/environment_implementation.cc
@@ -28,6 +28,8 @@
 #include <paludis/util/system.hh>
 #include <paludis/util/sequence.hh>
 #include <paludis/util/wrapped_forward_iterator.hh>
+#include <paludis/util/mutex.hh>
+#include <paludis/util/member_iterator-impl.hh>
 #include <paludis/hook.hh>
 #include <paludis/distribution.hh>
 #include <paludis/selection.hh>
@@ -37,12 +39,82 @@
 
 using namespace paludis;
 
+namespace
+{
+    typedef std::tr1::function<void (const SetName &) > CombiningFunction;
+
+    struct CombineSets
+    {
+        std::tr1::shared_ptr<AllDepSpec> root;
+        std::tr1::shared_ptr<SetSpecTree> tree;
+
+        void add(const SetName & s)
+        {
+            tree->root()->append(make_shared_ptr(new NamedSetDepSpec(s)));
+        }
+
+        CombineSets() :
+            root(new AllDepSpec),
+            tree(new SetSpecTree(root))
+        {
+        }
+
+        CombineSets(const CombineSets & other) :
+            root(other.root),
+            tree(other.tree)
+        {
+        }
+
+        std::tr1::shared_ptr<const SetSpecTree> result() const
+        {
+            return tree;
+        }
+    };
+
+    typedef std::map<SetName, std::pair<std::tr1::function<std::tr1::shared_ptr<const SetSpecTree> ()>, CombiningFunction> > SetsStore;
+
+    template <typename F_>
+    struct Cache
+    {
+        F_ func;
+        std::tr1::shared_ptr<typename std::tr1::remove_reference<typename F_::result_type>::type> result;
+
+        Cache(const F_ & f) :
+            func(f)
+        {
+        }
+
+        typename F_::result_type operator() ()
+        {
+            if (! result)
+                result.reset(new typename std::tr1::remove_reference<typename F_::result_type>::type(func()));
+            return *result;
+        }
+    };
+
+    template <typename F_>
+    F_ cache(const F_ & f)
+    {
+        return Cache<F_>(f);
+    }
+}
+
 namespace paludis
 {
     template <>
     struct Implementation<EnvironmentImplementation>
     {
         std::map<unsigned, NotifierCallbackFunction> notifier_callbacks;
+
+        mutable Mutex sets_mutex;
+        mutable bool loaded_sets;
+        std::tr1::shared_ptr<SetNameSet> set_names;
+        SetsStore sets;
+
+        Implementation() :
+            loaded_sets(false)
+        {
+        }
     };
 }
 
@@ -102,60 +174,6 @@ EnvironmentImplementation::default_destinations() const
     return result;
 }
 
-const std::tr1::shared_ptr<const SetSpecTree>
-EnvironmentImplementation::set(const SetName & s) const
-{
-    {
-        const std::tr1::shared_ptr<const SetSpecTree> l(local_set(s));
-        if (l)
-        {
-            Log::get_instance()->message("environment_implementation.local_set", ll_debug, lc_context) << "Set '" << s << "' is a local set";
-            return l;
-        }
-    }
-
-    std::tr1::shared_ptr<SetSpecTree> result;;
-
-    /* these sets always exist, even if empty */
-    if (s.data() == "everything" || s.data() == "system" || s.data() == "world" || s.data() == "security")
-    {
-        Log::get_instance()->message("environment_implementation.standard_set", ll_debug, lc_context) << "Set '" << s << "' is a standard set";
-        result.reset(new SetSpecTree(make_shared_ptr(new AllDepSpec)));
-    }
-
-    for (PackageDatabase::RepositoryConstIterator r(package_database()->begin_repositories()),
-            r_end(package_database()->end_repositories()) ;
-            r != r_end ; ++r)
-    {
-        if (! (**r).sets_interface())
-            continue;
-
-        std::tr1::shared_ptr<const SetSpecTree> add((**r).sets_interface()->package_set(s));
-        if (add)
-        {
-            Log::get_instance()->message("environment_implementation.set_found_in_repository", ll_debug, lc_context)
-                << "Set '" << s << "' found in '" << (*r)->name() << "'";
-            if (! result)
-                result.reset(new SetSpecTree(make_shared_ptr(new AllDepSpec)));
-            result->root()->append_node(add->root());
-        }
-    }
-
-    if ("everything" == s.data() || "world" == s.data())
-        result->root()->append(make_shared_ptr(new NamedSetDepSpec(SetName("system"))));
-
-    if ("world" == s.data())
-    {
-        std::tr1::shared_ptr<const SetSpecTree> w(world_set());
-        if (w)
-            result->root()->append_node(w->root());
-    }
-
-    if (! result)
-        Log::get_instance()->message("environment_implementation.no_match_for_set", ll_debug, lc_context) << "No match for set '" << s << "'";
-    return result;
-}
-
 std::string
 EnvironmentImplementation::distribution() const
 {
@@ -163,12 +181,6 @@ EnvironmentImplementation::distribution() const
     return result;
 }
 
-std::tr1::shared_ptr<const SetNameSet>
-EnvironmentImplementation::set_names() const
-{
-    return make_shared_ptr(new SetNameSet);
-}
-
 bool
 EnvironmentImplementation::is_paludis_package(const QualifiedPackageName & n) const
 {
@@ -207,3 +219,111 @@ EnvironmentImplementation::trigger_notifier_callback(const NotifierCallbackEvent
         (i->second)(e);
 }
 
+void
+EnvironmentImplementation::add_set(
+        const SetName & name,
+        const SetName & combined_name,
+        const std::tr1::function<std::tr1::shared_ptr<const SetSpecTree> ()> & func,
+        const bool combine) const
+{
+    Lock lock(_imp->sets_mutex);
+    Context context("When adding set named '" + stringify(name) + ":");
+
+    if (combine)
+    {
+        if (! _imp->sets.insert(std::make_pair(combined_name, std::make_pair(cache(func), CombiningFunction()))).second)
+            throw DuplicateSetError(combined_name);
+
+        std::tr1::shared_ptr<CombineSets> c_s(new CombineSets);
+        CombiningFunction c_func(_imp->sets.insert(std::make_pair(name, std::make_pair(
+                            std::tr1::bind(&CombineSets::result, c_s),
+                            std::tr1::bind(&CombineSets::add, c_s, std::tr1::placeholders::_1)
+                            ))).first->second.second);
+        if (! c_func)
+            throw DuplicateSetError(name);
+        c_func(combined_name);
+    }
+    else
+    {
+        if (! _imp->sets.insert(std::make_pair(name, std::make_pair(cache(func), CombiningFunction()))).second)
+            throw DuplicateSetError(name);
+    }
+}
+
+std::tr1::shared_ptr<const SetNameSet>
+EnvironmentImplementation::set_names() const
+{
+    Lock lock(_imp->sets_mutex);
+    _need_sets();
+
+    return _imp->set_names;
+}
+
+const std::tr1::shared_ptr<const SetSpecTree>
+EnvironmentImplementation::set(const SetName & s) const
+{
+    Lock lock(_imp->sets_mutex);
+    _need_sets();
+
+    SetsStore::const_iterator i(_imp->sets.find(s));
+    if (_imp->sets.end() != i)
+        return i->second.first();
+    else
+        return make_null_shared_ptr();
+}
+
+void
+EnvironmentImplementation::_need_sets() const
+{
+    if (_imp->loaded_sets)
+        return;
+
+    for (PackageDatabase::RepositoryConstIterator r(package_database()->begin_repositories()),
+            r_end(package_database()->end_repositories()) ;
+            r != r_end ; ++r)
+        (*r)->populate_sets();
+
+    populate_sets();
+    populate_standard_sets();
+
+    _imp->set_names.reset(new SetNameSet);
+    std::copy(first_iterator(_imp->sets.begin()), first_iterator(_imp->sets.end()), _imp->set_names->inserter());
+
+    _imp->loaded_sets = true;
+}
+
+void
+EnvironmentImplementation::populate_standard_sets() const
+{
+    set_always_exists(SetName("system"));
+    set_always_exists(SetName("world"));
+    set_always_exists(SetName("everything"));
+
+    SetsStore::iterator i(_imp->sets.find(SetName("world")));
+    /* some test cases build world through evil haxx. don't inject system in
+     * then. */
+    if (i->second.second)
+        i->second.second(SetName("system"));
+}
+
+namespace
+{
+    std::tr1::shared_ptr<const SetSpecTree> make_empty_set()
+    {
+        return make_shared_ptr(new SetSpecTree(make_shared_ptr(new AllDepSpec)));
+    }
+}
+
+void
+EnvironmentImplementation::set_always_exists(const SetName & s) const
+{
+    SetsStore::const_iterator i(_imp->sets.find(s));
+    if (_imp->sets.end() == i)
+        add_set(s, SetName(stringify(s) + "::default"), make_empty_set, true);
+}
+
+DuplicateSetError::DuplicateSetError(const SetName & s) throw () :
+    Exception("A set named '" + stringify(s) + "' already exists")
+{
+}
+
diff --git a/paludis/environment_implementation.hh b/paludis/environment_implementation.hh
index cb880eb..94b54d5 100644
--- a/paludis/environment_implementation.hh
+++ b/paludis/environment_implementation.hh
@@ -53,12 +53,13 @@ namespace paludis
         private:
             PrivateImplementationPattern<EnvironmentImplementation>::ImpPtr & _imp;
 
+            void _need_sets() const;
+
         protected:
-            virtual const std::tr1::shared_ptr<const SetSpecTree> local_set(const SetName &) const
-                PALUDIS_ATTRIBUTE((warn_unused_result)) = 0;
+            virtual void populate_sets() const = 0;
 
-            virtual const std::tr1::shared_ptr<const SetSpecTree> world_set() const
-                PALUDIS_ATTRIBUTE((warn_unused_result)) = 0;
+            virtual void populate_standard_sets() const;
+            void set_always_exists(const SetName &) const;
 
         public:
             ///\name Basic operations
@@ -78,12 +79,6 @@ namespace paludis
             virtual std::tr1::shared_ptr<const FSEntrySequence> fetchers_dirs() const
                 PALUDIS_ATTRIBUTE((warn_unused_result));
 
-            virtual std::tr1::shared_ptr<const SetNameSet> set_names() const
-                PALUDIS_ATTRIBUTE((warn_unused_result));
-
-            virtual const std::tr1::shared_ptr<const SetSpecTree> set(const SetName &) const
-                PALUDIS_ATTRIBUTE((warn_unused_result));
-
             virtual std::tr1::shared_ptr<const DestinationsSet> default_destinations() const
                 PALUDIS_ATTRIBUTE((warn_unused_result));
 
@@ -101,6 +96,25 @@ namespace paludis
             virtual void remove_notifier_callback(const NotifierCallbackID);
 
             virtual void trigger_notifier_callback(const NotifierCallbackEvent &) const;
+
+            virtual void add_set(
+                    const SetName &,
+                    const SetName &,
+                    const std::tr1::function<std::tr1::shared_ptr<const SetSpecTree> ()> &,
+                    const bool combine) const;
+
+            virtual std::tr1::shared_ptr<const SetNameSet> set_names() const
+                PALUDIS_ATTRIBUTE((warn_unused_result));
+
+            virtual const std::tr1::shared_ptr<const SetSpecTree> set(const SetName &) const
+                PALUDIS_ATTRIBUTE((warn_unused_result));
+    };
+
+    class PALUDIS_VISIBLE DuplicateSetError :
+        public Exception
+    {
+        public:
+            DuplicateSetError(const SetName & s) throw ();
     };
 }
 
diff --git a/paludis/environments/no_config/no_config_environment.cc b/paludis/environments/no_config/no_config_environment.cc
index c20f7b7..0b4cbb2 100644
--- a/paludis/environments/no_config/no_config_environment.cc
+++ b/paludis/environments/no_config/no_config_environment.cc
@@ -505,18 +505,6 @@ NoConfigEnvironment::accept_keywords(const std::tr1::shared_ptr<const KeywordNam
     return false;
 }
 
-const std::tr1::shared_ptr<const SetSpecTree>
-NoConfigEnvironment::local_set(const SetName &) const
-{
-    return make_null_shared_ptr();
-}
-
-const std::tr1::shared_ptr<const SetSpecTree>
-NoConfigEnvironment::world_set() const
-{
-    return make_null_shared_ptr();
-}
-
 void
 NoConfigEnvironment::add_to_world(const QualifiedPackageName &) const
 {
@@ -649,3 +637,8 @@ NoConfigEnvironment::create_output_manager(const CreateOutputManagerInfo &) cons
     return make_shared_ptr(new StandardOutputManager);
 }
 
+void
+NoConfigEnvironment::populate_sets() const
+{
+}
+
diff --git a/paludis/environments/no_config/no_config_environment.hh b/paludis/environments/no_config/no_config_environment.hh
index 30c465a..506f419 100644
--- a/paludis/environments/no_config/no_config_environment.hh
+++ b/paludis/environments/no_config/no_config_environment.hh
@@ -79,15 +79,11 @@ namespace paludis
         private:
             PrivateImplementationPattern<NoConfigEnvironment>::ImpPtr & _imp;
 
-        protected:
-            virtual const std::tr1::shared_ptr<const SetSpecTree> local_set(const SetName &) const
-                PALUDIS_ATTRIBUTE((warn_unused_result));
-
-            virtual const std::tr1::shared_ptr<const SetSpecTree> world_set() const
-                PALUDIS_ATTRIBUTE((warn_unused_result));
-
             virtual void need_keys_added() const;
 
+        protected:
+            virtual void populate_sets() const;
+
         public:
             ///\name Basic operations
             ///\{
diff --git a/paludis/environments/paludis/paludis_environment.cc b/paludis/environments/paludis/paludis_environment.cc
index 8920584..25c4fed 100644
--- a/paludis/environments/paludis/paludis_environment.cc
+++ b/paludis/environments/paludis/paludis_environment.cc
@@ -274,66 +274,6 @@ PaludisEnvironment::syncers_dirs() const
     return result;
 }
 
-const std::tr1::shared_ptr<const SetSpecTree>
-PaludisEnvironment::local_set(const SetName & ss) const
-{
-    using namespace std::tr1::placeholders;
-
-    Context context("When looking for package set '" + stringify(ss) + "' in paludis environment:");
-
-    Lock l(_imp->sets_mutex);
-
-    std::map<SetName, std::tr1::shared_ptr<const SetSpecTree> >::const_iterator i(_imp->sets.find(ss));
-    if (i != _imp->sets.end())
-        return i->second;
-
-    std::pair<SetName, SetFileSetOperatorMode> s(find_base_set_name_and_suffix_mode(ss));
-
-    FSEntry dir(FSEntry(_imp->config->config_dir()) / "sets");
-    std::tr1::shared_ptr<GeneralSetDepTag> tag(new GeneralSetDepTag(ss, stringify(s.first) + ".conf"));
-
-    if ((dir / (stringify(s.first) + ".bash")).exists())
-    {
-        SetFile f(make_named_values<SetFileParams>(
-                    value_for<n::environment>(this),
-                    value_for<n::file_name>(dir / (stringify(s.first) + ".bash")),
-                    value_for<n::parser>(std::tr1::bind(&parse_user_package_dep_spec, _1, this, UserPackageDepSpecOptions() + updso_allow_wildcards + updso_no_disambiguation + updso_throw_if_set, filter::All())),
-                    value_for<n::set_operator_mode>(s.second),
-                    value_for<n::tag>(tag),
-                    value_for<n::type>(sft_paludis_bash)
-                    ));
-
-        _imp->sets.insert(std::make_pair(ss, f.contents()));
-        return f.contents();
-    }
-    else if ((dir / (stringify(s.first) + ".conf")).exists())
-    {
-        SetFile f(make_named_values<SetFileParams>(
-                value_for<n::environment>(this),
-                value_for<n::file_name>(dir / (stringify(s.first) + ".conf")),
-                value_for<n::parser>(std::tr1::bind(&parse_user_package_dep_spec, _1, this,
-                        UserPackageDepSpecOptions() + updso_allow_wildcards, filter::All())),
-                value_for<n::set_operator_mode>(s.second),
-                value_for<n::tag>(tag),
-                value_for<n::type>(sft_paludis_conf)
-                ));
-
-        _imp->sets.insert(std::make_pair(ss, f.contents()));
-        return f.contents();
-    }
-    else
-    {
-        _imp->sets.insert(std::make_pair(ss, make_null_shared_ptr()));
-        return make_null_shared_ptr();
-    }
-}
-
-const std::tr1::shared_ptr<const SetSpecTree>
-PaludisEnvironment::world_set() const
-{
-    return _imp->config->world()->world_set();
-}
-
 void
 PaludisEnvironment::add_to_world(const QualifiedPackageName & q) const
 {
@@ -358,26 +298,6 @@ PaludisEnvironment::remove_from_world(const SetName & s) const
     _imp->config->world()->remove_from_world(s);
 }
 
-std::tr1::shared_ptr<const SetNameSet>
-PaludisEnvironment::set_names() const
-{
-    std::tr1::shared_ptr<SetNameSet> result(new SetNameSet);
-
-    if ((FSEntry(_imp->config->config_dir()) / "sets").exists())
-        for (DirIterator d(FSEntry(_imp->config->config_dir()) / "sets"), d_end ;
-                d != d_end ; ++d)
-        {
-            if (is_file_with_extension(*d, ".conf", IsFileWithOptions()))
-                result->insert(SetName(strip_trailing_string(d->basename(), ".conf")));
-            else if (is_file_with_extension(*d, ".bash", IsFileWithOptions()))
-                result->insert(SetName(strip_trailing_string(d->basename(), ".bash")));
-        }
-
-    result->insert(SetName("world"));
-
-    return result;
-}
-
 std::tr1::shared_ptr<const MirrorsSequence>
 PaludisEnvironment::mirrors(const std::string & m) const
 {
@@ -575,3 +495,69 @@ PaludisEnvironment::create_named_output_manager(const std::string & s, const Cre
     return _imp->config->output_managers()->create_named_output_manager(s, i);
 }
 
+namespace
+{
+    std::tr1::shared_ptr<const SetSpecTree> make_world_set(const std::tr1::shared_ptr<const World> & world)
+    {
+        return world->world_set();
+    }
+
+    std::tr1::shared_ptr<const SetSpecTree> make_set(
+            const Environment * const env,
+            const FSEntry & f,
+            const SetName & n,
+            SetFileSetOperatorMode mode,
+            SetFileType type)
+    {
+        Context context("When making set '" + stringify(f) + "':");
+
+        const std::tr1::shared_ptr<GeneralSetDepTag> tag(new GeneralSetDepTag(n, stringify(f.basename())));
+
+        SetFile s(make_named_values<SetFileParams>(
+                    value_for<n::environment>(env),
+                    value_for<n::file_name>(f),
+                    value_for<n::parser>(std::tr1::bind(&parse_user_package_dep_spec,
+                            std::tr1::placeholders::_1, env, UserPackageDepSpecOptions() + updso_allow_wildcards,
+                            filter::All())),
+                    value_for<n::set_operator_mode>(mode),
+                    value_for<n::tag>(tag),
+                    value_for<n::type>(type)
+                    ));
+        return s.contents();
+    }
+}
+
+void
+PaludisEnvironment::populate_sets() const
+{
+    Lock lock(_imp->sets_mutex);
+    add_set(SetName("world"), SetName("world::environment"), std::tr1::bind(&make_world_set, _imp->config->world()), true);
+
+    FSEntry sets_dir(FSEntry(_imp->config->config_dir()) / "sets");
+    Context context("When looking in sets directory '" + stringify(sets_dir) + "':");
+
+    if (! sets_dir.exists())
+        return;
+
+    for (DirIterator d(sets_dir, DirIteratorOptions() + dio_inode_sort), d_end ;
+            d != d_end ; ++d)
+    {
+        if (is_file_with_extension(*d, ".bash", IsFileWithOptions()))
+        {
+            SetName n(strip_trailing_string(d->basename(), ".bash"));
+            add_set(n, n, std::tr1::bind(&make_set, this, *d, n, sfsmo_natural, sft_paludis_bash), false);
+
+            SetName n_s(stringify(n) + "*");
+            add_set(n_s, n_s, std::tr1::bind(&make_set, this, *d, n_s, sfsmo_star, sft_paludis_bash), false);
+        }
+        else if (is_file_with_extension(*d, ".conf", IsFileWithOptions()))
+        {
+            SetName n(strip_trailing_string(d->basename(), ".conf"));
+            add_set(n, n, std::tr1::bind(&make_set, this, *d, n, sfsmo_natural, sft_paludis_conf), false);
+
+            SetName n_s(stringify(n) + "*");
+            add_set(n_s, n_s, std::tr1::bind(&make_set, this, *d, n_s, sfsmo_star, sft_paludis_conf), false);
+        }
+    }
+}
+
diff --git a/paludis/environments/paludis/paludis_environment.hh b/paludis/environments/paludis/paludis_environment.hh
index c981a40..605dc4c 100644
--- a/paludis/environments/paludis/paludis_environment.hh
+++ b/paludis/environments/paludis/paludis_environment.hh
@@ -55,10 +55,7 @@ namespace paludis
 
         protected:
             virtual void need_keys_added() const;
-
-            virtual const std::tr1::shared_ptr<const SetSpecTree> local_set(const SetName & id) const;
-
-            virtual const std::tr1::shared_ptr<const SetSpecTree> world_set() const;
+            virtual void populate_sets() const;
 
         public:
             ///\name Basic operations
@@ -104,9 +101,6 @@ namespace paludis
             virtual std::tr1::shared_ptr<const MirrorsSequence> mirrors(const std::string &) const
                 PALUDIS_ATTRIBUTE((warn_unused_result));
 
-            virtual std::tr1::shared_ptr<const SetNameSet> set_names() const
-                PALUDIS_ATTRIBUTE((warn_unused_result));
-
             virtual HookResult perform_hook(const Hook &) const
                 PALUDIS_ATTRIBUTE((warn_unused_result));
 
diff --git a/paludis/environments/portage/portage_environment.cc b/paludis/environments/portage/portage_environment.cc
index 8b277b2..333db69 100644
--- a/paludis/environments/portage/portage_environment.cc
+++ b/paludis/environments/portage/portage_environment.cc
@@ -767,12 +767,6 @@ PortageEnvironment::mirrors(const std::string & m) const
     return result;
 }
 
-const std::tr1::shared_ptr<const SetSpecTree>
-PortageEnvironment::local_set(const SetName &) const
-{
-    return make_null_shared_ptr();
-}
-
 bool
 PortageEnvironment::accept_license(const std::string &, const PackageID &) const
 {
@@ -961,37 +955,6 @@ PortageEnvironment::_remove_string_from_world(const std::string & s) const
     }
 }
 
-const std::tr1::shared_ptr<const SetSpecTree>
-PortageEnvironment::world_set() const
-{
-    Context context("When fetching environment world set:");
-
-    std::tr1::shared_ptr<GeneralSetDepTag> tag(new GeneralSetDepTag(SetName("world"), stringify("Environment")));
-
-    using namespace std::tr1::placeholders;
-
-    Lock l(_imp->world_mutex);
-
-    if (_imp->world_file.exists())
-    {
-        SetFile world(make_named_values<SetFileParams>(
-                    value_for<n::environment>(this),
-                    value_for<n::file_name>(_imp->world_file),
-                    value_for<n::parser>(std::tr1::bind(&parse_user_package_dep_spec, _1, this,
-                            UserPackageDepSpecOptions() + updso_no_disambiguation, filter::All())),
-                    value_for<n::set_operator_mode>(sfsmo_natural),
-                    value_for<n::tag>(tag),
-                    value_for<n::type>(sft_simple)
-                ));
-        return world.contents();
-    }
-    else
-        Log::get_instance()->message("portage_environment.world_file.does_not_exist", ll_warning, lc_no_context) <<
-            "World file '" << _imp->world_file << "' doesn't exist";
-
-    return make_shared_ptr(new SetSpecTree(make_shared_ptr(new AllDepSpec)));
-}
-
 void
 PortageEnvironment::need_keys_added() const
 {
@@ -1009,17 +972,45 @@ PortageEnvironment::config_location_key() const
     return _imp->config_location_key;
 }
 
-std::tr1::shared_ptr<const SetNameSet>
-PortageEnvironment::set_names() const
-{
-    std::tr1::shared_ptr<SetNameSet> result(new SetNameSet);
-    result->insert(SetName("world"));
-    return result;
-}
-
 const std::tr1::shared_ptr<OutputManager>
 PortageEnvironment::create_output_manager(const CreateOutputManagerInfo &) const
 {
     return make_shared_ptr(new StandardOutputManager);
 }
 
+namespace
+{
+    std::tr1::shared_ptr<const SetSpecTree> make_world_set(
+            const Environment * const env,
+            const FSEntry & f)
+    {
+        Context context("When loading world from '" + stringify(f) + "':");
+
+        if (! f.exists())
+        {
+            Log::get_instance()->message("portage_environment.world.does_not_exist", ll_warning, lc_no_context)
+                << "World file '" << f << "' doesn't exist";
+            return make_shared_ptr(new SetSpecTree(make_shared_ptr(new AllDepSpec)));
+        }
+
+        const std::tr1::shared_ptr<GeneralSetDepTag> tag(new GeneralSetDepTag(SetName("world::environment"), "Environment"));
+        SetFile world(make_named_values<SetFileParams>(
+                    value_for<n::environment>(env),
+                    value_for<n::file_name>(f),
+                    value_for<n::parser>(std::tr1::bind(&parse_user_package_dep_spec, std::tr1::placeholders::_1,
+                            env, UserPackageDepSpecOptions() + updso_no_disambiguation, filter::All())),
+                    value_for<n::set_operator_mode>(sfsmo_natural),
+                    value_for<n::tag>(tag),
+                    value_for<n::type>(sft_simple)
+                    ));
+        return world.contents();
+    }
+}
+
+void
+PortageEnvironment::populate_sets() const
+{
+    Lock l(_imp->world_mutex);
+    add_set(SetName("world::environment"), SetName("world"), std::tr1::bind(&make_world_set, this, _imp->world_file), true);
+}
+
diff --git a/paludis/environments/portage/portage_environment.hh b/paludis/environments/portage/portage_environment.hh
index c8c5512..67f8d24 100644
--- a/paludis/environments/portage/portage_environment.hh
+++ b/paludis/environments/portage/portage_environment.hh
@@ -80,13 +80,8 @@ namespace paludis
             void _remove_string_from_world(const std::string &) const;
 
         protected:
-            virtual const std::tr1::shared_ptr<const SetSpecTree> local_set(const SetName &) const
-                PALUDIS_ATTRIBUTE((warn_unused_result));
-
-            virtual const std::tr1::shared_ptr<const SetSpecTree> world_set() const
-                PALUDIS_ATTRIBUTE((warn_unused_result));
-
             virtual void need_keys_added() const;
+            virtual void populate_sets() const;
 
         public:
             ///\name Basic operations
@@ -170,9 +165,6 @@ namespace paludis
 
             virtual void remove_from_world(const SetName &) const;
 
-            virtual std::tr1::shared_ptr<const SetNameSet> set_names() const
-                PALUDIS_ATTRIBUTE((warn_unused_result));
-
             virtual const std::tr1::shared_ptr<const MetadataValueKey<std::string> > format_key() const;
             virtual const std::tr1::shared_ptr<const MetadataValueKey<FSEntry> > config_location_key() const;
 
diff --git a/paludis/environments/test/test_environment.cc b/paludis/environments/test/test_environment.cc
index 0930d13..5dadd6a 100644
--- a/paludis/environments/test/test_environment.cc
+++ b/paludis/environments/test/test_environment.cc
@@ -130,16 +130,6 @@ TestEnvironment::fetch_package_id(const QualifiedPackageName & q,
     throw NoSuchPackageError(stringify(q) + "-" + stringify(v) + "::" + stringify(r));
 }
 
-const std::tr1::shared_ptr<const SetSpecTree>
-TestEnvironment::local_set(const SetName & s) const
-{
-    Sets::const_iterator i(_imp->sets.find(s));
-    if (_imp->sets.end() == i)
-        return make_null_shared_ptr();
-    else
-        return i->second;
-}
-
 uid_t
 TestEnvironment::reduced_uid() const
 {
@@ -202,12 +192,6 @@ TestEnvironment::unmasked_by_user(const PackageID &) const
     return false;
 }
 
-const std::tr1::shared_ptr<const SetSpecTree>
-TestEnvironment::world_set() const
-{
-    return local_set(SetName("world"));
-}
-
 void
 TestEnvironment::add_to_world(const QualifiedPackageName &) const
 {
@@ -305,3 +289,8 @@ TestEnvironment::set_want_choice_enabled(const ChoicePrefixName & p, const Unpre
     _imp->override_want_choice_enabled[stringify(p) + ":" + stringify(n)] = v;
 }
 
+void
+TestEnvironment::populate_sets() const
+{
+}
+
diff --git a/paludis/environments/test/test_environment.hh b/paludis/environments/test/test_environment.hh
index 52f661f..311f35e 100644
--- a/paludis/environments/test/test_environment.hh
+++ b/paludis/environments/test/test_environment.hh
@@ -47,13 +47,8 @@ namespace paludis
             PrivateImplementationPattern<TestEnvironment>::ImpPtr & _imp;
 
         protected:
-            virtual const std::tr1::shared_ptr<const SetSpecTree> local_set(const SetName &) const
-                PALUDIS_ATTRIBUTE((warn_unused_result));
-
-            virtual const std::tr1::shared_ptr<const SetSpecTree> world_set() const
-                PALUDIS_ATTRIBUTE((warn_unused_result));
-
             virtual void need_keys_added() const;
+            virtual void populate_sets() const;
 
         public:
             ///\name Basic operations
diff --git a/paludis/name.cc b/paludis/name.cc
index 2ad4bc6..7f9641e 100644
--- a/paludis/name.cc
+++ b/paludis/name.cc
@@ -1,7 +1,7 @@
 /* vim: set sw=4 sts=4 et foldmethod=syntax : */
 
 /*
- * Copyright (c) 2005, 2006, 2007, 2008 Ciaran McCreesh
+ * Copyright (c) 2005, 2006, 2007, 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
@@ -343,7 +343,7 @@ SetNameValidator::validate(const std::string & s)
     static const std::string allowed_chars(
             "abcdefghijklmnopqrstuvwxyz"
             "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
-            "0123456789-+_");
+            "0123456789-+_:");
 
     do
     {
@@ -363,6 +363,20 @@ SetNameValidator::validate(const std::string & s)
         if (std::string::npos != s.find_first_not_of(allowed_chars))
             break;
 
+        std::string::size_type p(s.find(':'));
+        if (std::string::npos != p)
+        {
+            if (++p >= s.length())
+                break;
+            if (s[p] != ':')
+                break;
+
+            if (++p >= s.length())
+                break;
+            if (std::string::npos != s.find(':', p))
+                break;
+        }
+
         return;
 
     } while (false);
diff --git a/paludis/name_TEST.cc b/paludis/name_TEST.cc
index b150557..9813b38 100644
--- a/paludis/name_TEST.cc
+++ b/paludis/name_TEST.cc
@@ -1,7 +1,7 @@
 /* vim: set sw=4 sts=4 et foldmethod=syntax : */
 
 /*
- * Copyright (c) 2005, 2006, 2007, 2008 Ciaran McCreesh
+ * Copyright (c) 2005, 2006, 2007, 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
@@ -312,6 +312,8 @@ namespace test_cases
             SetName k("set0_-");
             SetName k1("set0_-");
             SetName k2("set0*");
+            SetName k3("set::foo");
+            SetName k4("set::foo*");
             TEST_CHECK_THROWS(k = SetName(""), NameError);
             TEST_CHECK_THROWS(k = SetName("!!!"), NameError);
             TEST_CHECK_THROWS(k = SetName("~"), NameError);
@@ -323,6 +325,12 @@ namespace test_cases
             TEST_CHECK_THROWS(k = SetName("set**"), NameError);
             TEST_CHECK_THROWS(k = SetName("set*?"), NameError);
             TEST_CHECK_THROWS(k = SetName("set?"), NameError);
+            TEST_CHECK_THROWS(k = SetName("set:::"), NameError);
+            TEST_CHECK_THROWS(k = SetName("set::"), NameError);
+            TEST_CHECK_THROWS(k = SetName("set:"), NameError);
+            TEST_CHECK_THROWS(k = SetName("set:foo"), NameError);
+            TEST_CHECK_THROWS(k = SetName("set:::foo"), NameError);
+            TEST_CHECK_THROWS(k = SetName("set::foo::bar"), NameError);
         }
     } test_set_name_validator;
 }
diff --git a/paludis/report_task.cc b/paludis/report_task.cc
index 9590529..9c310be 100644
--- a/paludis/report_task.cc
+++ b/paludis/report_task.cc
@@ -147,28 +147,19 @@ ReportTask::execute()
     bool once(true);
 
     VulnerableChecker vuln(*e);
-    for (PackageDatabase::RepositoryConstIterator r(e->package_database()->begin_repositories()),
-            r_end(e->package_database()->end_repositories()) ; r != r_end ; ++r)
+    try
     {
-        std::tr1::shared_ptr<const Repository> rr(e->package_database()->fetch_repository((*r)->name()));
-        if (! (*rr).sets_interface())
-            continue;
-
-        try
-        {
-            std::tr1::shared_ptr<const SetSpecTree> insecure((*rr).sets_interface()->package_set(SetName("insecurity")));
-            if (! insecure)
-                continue;
+        std::tr1::shared_ptr<const SetSpecTree> insecure(_imp->env->set(SetName("insecurity")));
+        if (insecure)
             insecure->root()->accept(vuln);
-        }
-        catch (const NotAvailableError &)
+    }
+    catch (const NotAvailableError &)
+    {
+        if (once)
         {
-            if (once)
-            {
-                Log::get_instance()->message("report_task.skipping_glsas", ll_warning, lc_no_context)
-                        << "Skipping GLSA checks because Paludis was built without XML support";
-                once = false;
-            }
+            Log::get_instance()->message("report_task.skipping_glsas", ll_warning, lc_no_context)
+                << "Skipping GLSA checks because Paludis was built without XML support";
+            once = false;
         }
     }
 
diff --git a/paludis/repositories/accounts/accounts_repository.cc b/paludis/repositories/accounts/accounts_repository.cc
index e501d5a..ee4e955 100644
--- a/paludis/repositories/accounts/accounts_repository.cc
+++ b/paludis/repositories/accounts/accounts_repository.cc
@@ -29,11 +29,15 @@
 #include <paludis/util/active_object_ptr.hh>
 #include <paludis/util/deferred_construction_ptr.hh>
 #include <paludis/util/stringify.hh>
+#include <paludis/util/log.hh>
 #include <paludis/dep_tag.hh>
 #include <paludis/literal_metadata_key.hh>
 #include <paludis/action.hh>
 #include <paludis/package_id.hh>
 #include <paludis/environment.hh>
+#include <paludis/generator.hh>
+#include <paludis/selection.hh>
+#include <paludis/filtered_generator.hh>
 
 using namespace paludis;
 using namespace paludis::accounts_repository;
@@ -114,7 +118,6 @@ AccountsRepository::AccountsRepository(const AccountsRepositoryParams & p) :
                 value_for<n::mirrors_interface>(static_cast<RepositoryMirrorsInterface *>(0)),
                 value_for<n::provides_interface>(static_cast<RepositoryProvidesInterface *>(0)),
                 value_for<n::qa_interface>(static_cast<RepositoryQAInterface *>(0)),
-                value_for<n::sets_interface>(this),
                 value_for<n::syncable_interface>(static_cast<RepositorySyncableInterface *>(0)),
                 value_for<n::virtuals_interface>(static_cast<RepositoryVirtualsInterface *>(0))
                 )),
@@ -138,7 +141,6 @@ AccountsRepository::AccountsRepository(const InstalledAccountsRepositoryParams &
                 value_for<n::mirrors_interface>(static_cast<RepositoryMirrorsInterface *>(0)),
                 value_for<n::provides_interface>(static_cast<RepositoryProvidesInterface *>(0)),
                 value_for<n::qa_interface>(static_cast<RepositoryQAInterface *>(0)),
-                value_for<n::sets_interface>(this),
                 value_for<n::syncable_interface>(static_cast<RepositorySyncableInterface *>(0)),
                 value_for<n::virtuals_interface>(static_cast<RepositoryVirtualsInterface *>(0))
                 )),
@@ -422,51 +424,46 @@ AccountsRepository::merge(const MergeParams & m)
     _imp->handler_if_installed->merge(m);
 }
 
-const std::tr1::shared_ptr<const SetSpecTree>
-AccountsRepository::package_set(const SetName & s) const
+namespace
 {
-    using namespace std::tr1::placeholders;
-
-    Context context("When fetching package set '" + stringify(s) + "' from '" +
-            stringify(name()) + "':");
-
-    if ("everything" == s.data() && _imp->params_if_installed)
+    std::tr1::shared_ptr<SetSpecTree> get_everything_set(
+            const Environment * const env,
+            const AccountsRepository * const repo)
     {
+        Context context("When making 'everything' set from '" + stringify(repo->name()) + "':");
+
         std::tr1::shared_ptr<SetSpecTree> result(new SetSpecTree(make_shared_ptr(new AllDepSpec)));
-        std::tr1::shared_ptr<GeneralSetDepTag> tag(new GeneralSetDepTag(s, stringify(name())));
 
-        std::tr1::shared_ptr<const CategoryNamePartSet> cats(category_names());
-        for (CategoryNamePartSet::ConstIterator c(cats->begin()), c_end(cats->end()) ;
-                c != c_end ; ++c)
-        {
-            std::tr1::shared_ptr<const QualifiedPackageNameSet> pkgs(package_names(*c));
-            for (QualifiedPackageNameSet::ConstIterator e(pkgs->begin()), e_end(pkgs->end()) ;
-                    e != e_end ; ++e)
-            {
-                std::tr1::shared_ptr<PackageDepSpec> spec(new PackageDepSpec(make_package_dep_spec(
-                                PartiallyMadePackageDepSpecOptions()).package(QualifiedPackageName(*e))));
-                spec->set_tag(tag);
-                result->root()->append(spec);
-            }
-        }
+        std::tr1::shared_ptr<const PackageIDSequence> ids((*env)[selection::BestVersionOnly(
+                    generator::InRepository(repo->name()))]);
+        for (PackageIDSequence::ConstIterator i(ids->begin()), i_end(ids->end()) ;
+                i != i_end ; ++i)
+            result->root()->append(make_shared_ptr(new PackageDepSpec(
+                            make_package_dep_spec(PartiallyMadePackageDepSpecOptions())
+                            .package((*i)->name())
+                            )));
 
         return result;
     }
-    else
-        return make_null_shared_ptr();
 }
 
-std::tr1::shared_ptr<const SetNameSet>
-AccountsRepository::sets_list() const
+void
+AccountsRepository::populate_sets() const
 {
-    Context context("While generating the list of sets:");
-
-    std::tr1::shared_ptr<SetNameSet> result(new SetNameSet);
-    if (_imp->params_if_installed)
-        result->insert(SetName("everything"));
-    return result;
+    if (_imp->params_if_not_installed)
+    {
+        /* no sets */
+    }
+    else
+    {
+        /* everything */
+        _imp->params_if_installed->environment()->add_set(
+                SetName("everything"),
+                SetName("everything::" + stringify(name())),
+                std::tr1::bind(get_everything_set, _imp->params_if_installed->environment(), this),
+                true);
+    }
 }
 
-
 template class PrivateImplementationPattern<AccountsRepository>;
 
diff --git a/paludis/repositories/accounts/accounts_repository.hh b/paludis/repositories/accounts/accounts_repository.hh
index a25153c..c9d2d22 100644
--- a/paludis/repositories/accounts/accounts_repository.hh
+++ b/paludis/repositories/accounts/accounts_repository.hh
@@ -56,7 +56,6 @@ namespace paludis
             private PrivateImplementationPattern<AccountsRepository>,
             public Repository,
             public RepositoryDestinationInterface,
-            public RepositorySetsInterface,
             public std::tr1::enable_shared_from_this<AccountsRepository>
         {
             private:
@@ -154,12 +153,10 @@ namespace paludis
 
                 ///\}
 
-                ///\name Set queries
+                ///\name Set methods
                 ///\{
 
-                virtual const std::tr1::shared_ptr<const SetSpecTree> package_set(const SetName & s) const;
-                virtual std::tr1::shared_ptr<const SetNameSet> sets_list() const
-                    PALUDIS_ATTRIBUTE((warn_unused_result));
+                virtual void populate_sets() const;
 
                 ///\}
         };
diff --git a/paludis/repositories/cran/cran_installed_repository.cc b/paludis/repositories/cran/cran_installed_repository.cc
index 397e490..bf0384c 100644
--- a/paludis/repositories/cran/cran_installed_repository.cc
+++ b/paludis/repositories/cran/cran_installed_repository.cc
@@ -27,6 +27,10 @@
 #include <paludis/action.hh>
 #include <paludis/literal_metadata_key.hh>
 #include <paludis/user_dep_spec.hh>
+#include <paludis/generator.hh>
+#include <paludis/filtered_generator.hh>
+#include <paludis/filter.hh>
+#include <paludis/selection.hh>
 #include <paludis/repositories/cran/cran_package_id.hh>
 #include <paludis/repositories/cran/cran_dep_parser.hh>
 #include <paludis/repositories/cran/cran_installed_repository.hh>
@@ -167,7 +171,6 @@ CRANInstalledRepository::CRANInstalledRepository(const CRANInstalledRepositoryPa
                 value_for<n::mirrors_interface>(static_cast<RepositoryMirrorsInterface *>(0)),
                 value_for<n::provides_interface>(static_cast<RepositoryProvidesInterface *>(0)),
                 value_for<n::qa_interface>(static_cast<RepositoryQAInterface *>(0)),
-                value_for<n::sets_interface>(this),
                 value_for<n::syncable_interface>(static_cast<RepositorySyncableInterface *>(0)),
                 value_for<n::virtuals_interface>(static_cast<RepositoryVirtualsInterface *>(0))
                 )),
@@ -444,41 +447,6 @@ CRANInstalledRepository::do_uninstall(const QualifiedPackageName & q, const Vers
 }
 #endif
 
-const std::tr1::shared_ptr<const SetSpecTree>
-CRANInstalledRepository::package_set(const SetName & s) const
-{
-    Context context("When fetching package set '" + stringify(s) + "' from '" +
-            stringify(name()) + "':");
-
-    if ("everything" == s.data())
-    {
-        std::tr1::shared_ptr<SetSpecTree> result(new SetSpecTree(make_shared_ptr(new AllDepSpec)));
-
-        need_ids();
-
-        for (IDMap::const_iterator p(_imp->ids.begin()), p_end(_imp->ids.end()) ;
-                p != p_end ; ++p)
-        {
-            std::tr1::shared_ptr<PackageDepSpec> spec(new PackageDepSpec(cranrepository::parse_cran_package_dep_spec(stringify(p->first.package()))));
-            result->root()->append(spec);
-        }
-
-        return result;
-    }
-    else
-        return make_null_shared_ptr();
-}
-
-std::tr1::shared_ptr<const SetNameSet>
-CRANInstalledRepository::sets_list() const
-{
-    Context context("While generating the list of sets:");
-
-    std::tr1::shared_ptr<SetNameSet> result(new SetNameSet);
-    result->insert(SetName("everything"));
-    return result;
-}
-
 void
 CRANInstalledRepository::invalidate()
 {
@@ -601,4 +569,36 @@ CRANInstalledRepository::installed_root_key() const
     return _imp->installed_root_key;
 }
 
+namespace
+{
+    std::tr1::shared_ptr<SetSpecTree> get_everything_set(
+            const Environment * const env,
+            const Repository * const repo)
+    {
+        Context context("When making 'everything' set from '" + stringify(repo->name()) + "':");
+
+        std::tr1::shared_ptr<SetSpecTree> result(new SetSpecTree(make_shared_ptr(new AllDepSpec)));
+
+        std::tr1::shared_ptr<const PackageIDSequence> ids((*env)[selection::BestVersionOnly(
+                    generator::InRepository(repo->name()))]);
+        for (PackageIDSequence::ConstIterator i(ids->begin()), i_end(ids->end()) ;
+                i != i_end ; ++i)
+            result->root()->append(make_shared_ptr(new PackageDepSpec(
+                            make_package_dep_spec(PartiallyMadePackageDepSpecOptions())
+                            .package((*i)->name())
+                            )));
+
+        return result;
+    }
+}
+
+void
+CRANInstalledRepository::populate_sets() const
+{
+    _imp->params.environment()->add_set(
+            SetName("everything"),
+            SetName("everything::" + stringify(name())),
+            std::tr1::bind(get_everything_set, _imp->params.environment(), this),
+            true);
+}
 
diff --git a/paludis/repositories/cran/cran_installed_repository.hh b/paludis/repositories/cran/cran_installed_repository.hh
index 80b3627..bba0019 100644
--- a/paludis/repositories/cran/cran_installed_repository.hh
+++ b/paludis/repositories/cran/cran_installed_repository.hh
@@ -2,7 +2,7 @@
 
 /*
  * Copyright (c) 2006 Danny van Dyk
- * Copyright (c) 2007, 2008 Ciaran McCreesh
+ * Copyright (c) 2007, 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
@@ -64,7 +64,6 @@ namespace paludis
      */
     class PALUDIS_VISIBLE CRANInstalledRepository :
         public Repository,
-        public RepositorySetsInterface,
         public RepositoryDestinationInterface,
         public PrivateImplementationPattern<CRANInstalledRepository>
     {
@@ -108,11 +107,6 @@ namespace paludis
             virtual void invalidate();
             virtual void invalidate_masks();
 
-            /* RepositorySetsInterface */
-
-            virtual std::tr1::shared_ptr<const SetNameSet> sets_list() const
-                PALUDIS_ATTRIBUTE((warn_unused_result));
-
             /* RepositoryDestinationInterface */
 
             virtual bool is_suitable_destination_for(const PackageID &) const
@@ -147,16 +141,18 @@ namespace paludis
 
             virtual bool some_ids_might_support_action(const SupportsActionTestBase &) const;
 
-            /* RepositorySetsInterface */
-
-            virtual const std::tr1::shared_ptr<const SetSpecTree> package_set(const SetName & id) const
-                PALUDIS_ATTRIBUTE((warn_unused_result));
-
             /* Keys */
 
             virtual const std::tr1::shared_ptr<const MetadataValueKey<std::string> > format_key() const;
             virtual const std::tr1::shared_ptr<const MetadataValueKey<FSEntry> > location_key() const;
             virtual const std::tr1::shared_ptr<const MetadataValueKey<FSEntry> > installed_root_key() const;
+
+            ///\name Set methods
+            ///\{
+
+            virtual void populate_sets() const;
+
+            ///\}
     };
 
     /**
diff --git a/paludis/repositories/cran/cran_repository.cc b/paludis/repositories/cran/cran_repository.cc
index 4d6713b..3bdde14 100644
--- a/paludis/repositories/cran/cran_repository.cc
+++ b/paludis/repositories/cran/cran_repository.cc
@@ -116,7 +116,6 @@ CRANRepository::CRANRepository(const CRANRepositoryParams & p) :
                 value_for<n::mirrors_interface>(static_cast<RepositoryMirrorsInterface *>(0)),
                 value_for<n::provides_interface>(static_cast<RepositoryProvidesInterface *>(0)),
                 value_for<n::qa_interface>(static_cast<RepositoryQAInterface *>(0)),
-                value_for<n::sets_interface>(this),
                 value_for<n::syncable_interface>(this),
                 value_for<n::virtuals_interface>(static_cast<RepositoryVirtualsInterface *>(0))
                 )),
@@ -342,31 +341,6 @@ CRANRepository::do_install(const std::tr1::shared_ptr<const PackageID> & id_unca
 }
 #endif
 
-const std::tr1::shared_ptr<const SetSpecTree>
-CRANRepository::package_set(const SetName & s) const
-{
-    if ("base" == s.data())
-    {
-        /**
-         * \todo Implement system as all package which are installed
-         * by dev-lang/R by default.
-         */
-        return make_shared_ptr(new SetSpecTree(make_shared_ptr(new AllDepSpec)));
-    }
-    else
-        return make_null_shared_ptr();
-}
-
-std::tr1::shared_ptr<const SetNameSet>
-CRANRepository::sets_list() const
-{
-    Context context("While generating the list of sets:");
-
-    std::tr1::shared_ptr<SetNameSet> result(new SetNameSet);
-    result->insert(SetName("base"));
-    return result;
-}
-
 bool
 CRANRepository::sync(const std::tr1::shared_ptr<OutputManager> & output_manager) const
 {
@@ -571,3 +545,8 @@ CRANRepository::installed_root_key() const
     return std::tr1::shared_ptr<const MetadataValueKey<FSEntry> >();
 }
 
+void
+CRANRepository::populate_sets() const
+{
+}
+
diff --git a/paludis/repositories/cran/cran_repository.hh b/paludis/repositories/cran/cran_repository.hh
index 9baef2a..bbd5578 100644
--- a/paludis/repositories/cran/cran_repository.hh
+++ b/paludis/repositories/cran/cran_repository.hh
@@ -76,7 +76,6 @@ namespace paludis
     class PALUDIS_VISIBLE CRANRepository :
         public Repository,
         public RepositorySyncableInterface,
-        public RepositorySetsInterface,
         private PrivateImplementationPattern<CRANRepository>,
         public std::tr1::enable_shared_from_this<CRANRepository>
     {
@@ -128,12 +127,6 @@ namespace paludis
 
             /* RepositorySyncableInterface */
 
-            virtual const std::tr1::shared_ptr<const SetSpecTree> package_set(const SetName &) const;
-
-            virtual std::tr1::shared_ptr<const SetNameSet> sets_list() const;
-
-            /* RepositorySyncableInterface */
-
             virtual bool sync(const std::tr1::shared_ptr<OutputManager> & output_deviant) const;
 
             /* Repository */
@@ -162,6 +155,13 @@ namespace paludis
             virtual const std::tr1::shared_ptr<const MetadataValueKey<std::string> > format_key() const;
             virtual const std::tr1::shared_ptr<const MetadataValueKey<FSEntry> > location_key() const;
             virtual const std::tr1::shared_ptr<const MetadataValueKey<FSEntry> > installed_root_key() const;
+
+            ///\name Set methods
+            ///\{
+
+            virtual void populate_sets() const;
+
+            ///\}
     };
 
     /**
diff --git a/paludis/repositories/e/e_installed_repository.cc b/paludis/repositories/e/e_installed_repository.cc
index 21ed732..861dcd1 100644
--- a/paludis/repositories/e/e_installed_repository.cc
+++ b/paludis/repositories/e/e_installed_repository.cc
@@ -46,6 +46,10 @@
 #include <paludis/hook.hh>
 #include <paludis/dep_tag.hh>
 #include <paludis/user_dep_spec.hh>
+#include <paludis/generator.hh>
+#include <paludis/filter.hh>
+#include <paludis/filtered_generator.hh>
+#include <paludis/selection.hh>
 
 using namespace paludis;
 using namespace paludis::erepository;
@@ -158,50 +162,6 @@ EInstalledRepository::perform_hook(const Hook & hook) const
     return make_named_values<HookResult>(value_for<n::max_exit_status>(0), value_for<n::output>(""));
 }
 
-const std::tr1::shared_ptr<const SetSpecTree>
-EInstalledRepository::package_set(const SetName & s) const
-{
-    using namespace std::tr1::placeholders;
-
-    Context context("When fetching package set '" + stringify(s) + "' from '" +
-            stringify(name()) + "':");
-
-    if ("everything" == s.data())
-    {
-        std::tr1::shared_ptr<SetSpecTree> result(new SetSpecTree(make_shared_ptr(new AllDepSpec)));
-        std::tr1::shared_ptr<GeneralSetDepTag> tag(new GeneralSetDepTag(SetName("everything"), stringify(name())));
-
-        std::tr1::shared_ptr<const CategoryNamePartSet> cats(category_names());
-        for (CategoryNamePartSet::ConstIterator i(cats->begin()), i_end(cats->end()) ;
-                i != i_end ; ++i)
-        {
-            std::tr1::shared_ptr<const QualifiedPackageNameSet> pkgs(package_names(*i));
-            for (QualifiedPackageNameSet::ConstIterator e(pkgs->begin()), e_end(pkgs->end()) ;
-                    e != e_end ; ++e)
-            {
-                std::tr1::shared_ptr<PackageDepSpec> spec(new PackageDepSpec(make_package_dep_spec(
-                                PartiallyMadePackageDepSpecOptions()).package(*e)));
-                spec->set_tag(tag);
-                result->root()->append(spec);
-            }
-        }
-
-        return result;
-    }
-    else
-        return make_null_shared_ptr();
-}
-
-std::tr1::shared_ptr<const SetNameSet>
-EInstalledRepository::sets_list() const
-{
-    Context context("While generating the list of sets:");
-
-    std::tr1::shared_ptr<SetNameSet> result(new SetNameSet);
-    result->insert(SetName("everything"));
-    return result;
-}
-
 std::tr1::shared_ptr<const CategoryNamePartSet>
 EInstalledRepository::unimportant_category_names() const
 {
@@ -413,3 +373,36 @@ EInstalledRepository::perform_info(
     }
 }
 
+namespace
+{
+    std::tr1::shared_ptr<SetSpecTree> get_everything_set(
+            const Environment * const env,
+            const Repository * const repo)
+    {
+        Context context("When making 'everything' set from '" + stringify(repo->name()) + "':");
+
+        std::tr1::shared_ptr<SetSpecTree> result(new SetSpecTree(make_shared_ptr(new AllDepSpec)));
+
+        std::tr1::shared_ptr<const PackageIDSequence> ids((*env)[selection::BestVersionOnly(
+                    generator::InRepository(repo->name()))]);
+        for (PackageIDSequence::ConstIterator i(ids->begin()), i_end(ids->end()) ;
+                i != i_end ; ++i)
+            result->root()->append(make_shared_ptr(new PackageDepSpec(
+                            make_package_dep_spec(PartiallyMadePackageDepSpecOptions())
+                            .package((*i)->name())
+                            )));
+
+        return result;
+    }
+}
+
+void
+EInstalledRepository::populate_sets() const
+{
+    _imp->params.environment()->add_set(
+            SetName("everything"),
+            SetName("everything::" + stringify(name())),
+            std::tr1::bind(get_everything_set, _imp->params.environment(), this),
+            true);
+}
+
diff --git a/paludis/repositories/e/e_installed_repository.hh b/paludis/repositories/e/e_installed_repository.hh
index ca1adba..4b9660c 100644
--- a/paludis/repositories/e/e_installed_repository.hh
+++ b/paludis/repositories/e/e_installed_repository.hh
@@ -43,7 +43,6 @@ namespace paludis
 
         class EInstalledRepository :
             public Repository,
-            public RepositorySetsInterface,
             public RepositoryEnvironmentVariableInterface,
             public RepositoryDestinationInterface,
             public RepositoryHookInterface,
@@ -57,14 +56,6 @@ namespace paludis
                 ~EInstalledRepository();
 
             public:
-                /* RepositorySetsInterface */
-
-                virtual const std::tr1::shared_ptr<const SetSpecTree> package_set(const SetName & id) const
-                    PALUDIS_ATTRIBUTE((warn_unused_result));
-
-                virtual std::tr1::shared_ptr<const SetNameSet> sets_list() const
-                    PALUDIS_ATTRIBUTE((warn_unused_result));
-
                 /* RepositoryEnvironmentVariableInterface */
 
                 virtual std::string get_environment_variable(
@@ -110,6 +101,13 @@ namespace paludis
                         const InfoAction &) const;
 
                 ///\}
+
+                ///\name Set methods
+                ///\{
+
+                virtual void populate_sets() const;
+
+                ///\}
         };
     }
 }
diff --git a/paludis/repositories/e/e_repository.cc b/paludis/repositories/e/e_repository.cc
index 021dafc..d2d753c 100644
--- a/paludis/repositories/e/e_repository.cc
+++ b/paludis/repositories/e/e_repository.cc
@@ -509,7 +509,6 @@ ERepository::ERepository(const ERepositoryParams & p) :
 #else
                 value_for<n::qa_interface>(static_cast<RepositoryQAInterface *>(0)),
 #endif
-                value_for<n::sets_interface>(this),
                 value_for<n::syncable_interface>(this),
                 value_for<n::virtuals_interface>((*DistributionData::get_instance()->distribution_from_string(p.environment()->distribution())).support_old_style_virtuals() ? this : 0)
                 )),
@@ -733,24 +732,6 @@ ERepository::need_mirrors() const
     }
 }
 
-const std::tr1::shared_ptr<const SetSpecTree>
-ERepository::package_set(const SetName & s) const
-{
-    if (s.data() == "system")
-    {
-        _imp->need_profiles();
-        return _imp->profile_ptr->system_packages();
-    }
-
-    return _imp->sets_ptr->package_set(s);
-}
-
-std::tr1::shared_ptr<const SetNameSet>
-ERepository::sets_list() const
-{
-    return _imp->sets_ptr->sets_list();
-}
-
 bool
 ERepository::sync(const std::tr1::shared_ptr<OutputManager> & output_manager) const
 {
@@ -1758,3 +1739,52 @@ ERepository::eapi_for_file(const FSEntry & f) const
     return i->second;
 }
 
+namespace
+{
+    std::tr1::shared_ptr<const SetSpecTree> get_system_set(const std::tr1::shared_ptr<const SetSpecTree> s)
+    {
+        return s;
+    }
+
+    std::tr1::shared_ptr<const SetSpecTree> get_set(
+            const std::tr1::shared_ptr<const ERepositorySets> & s,
+            const SetName & n)
+    {
+        return s->package_set(n);
+    }
+}
+
+void
+ERepository::populate_sets() const
+{
+    const std::tr1::shared_ptr<const SetNameSet> sets(_imp->sets_ptr->sets_list());
+    for (SetNameSet::ConstIterator s(sets->begin()), s_end(sets->end()) ;
+            s != s_end ; ++s)
+    {
+        if (stringify(*s) == "system")
+        {
+            _imp->need_profiles();
+            _imp->params.environment()->add_set(
+                    *s,
+                    SetName(stringify(*s) + "::" + stringify(name())),
+                    std::tr1::bind(&get_system_set, _imp->profile_ptr->system_packages()),
+                    true);
+        }
+        else
+        {
+            _imp->params.environment()->add_set(
+                    *s,
+                    SetName(stringify(*s) + "::" + stringify(name())),
+                    std::tr1::bind(&get_set, _imp->sets_ptr, *s),
+                    true);
+
+            if (stringify(*s) != "security" && stringify(*s) != "insecurity")
+                _imp->params.environment()->add_set(
+                        SetName(stringify(*s) + "*"),
+                        SetName(stringify(*s) + "::" + stringify(name()) + "*"),
+                        std::tr1::bind(&get_set, _imp->sets_ptr, SetName(stringify(*s) + "*")),
+                        true);
+        }
+    }
+}
+
diff --git a/paludis/repositories/e/e_repository.hh b/paludis/repositories/e/e_repository.hh
index 5977a2b..4a5981f 100644
--- a/paludis/repositories/e/e_repository.hh
+++ b/paludis/repositories/e/e_repository.hh
@@ -52,7 +52,6 @@ namespace paludis
     class PALUDIS_VISIBLE ERepository :
         public Repository,
         public RepositorySyncableInterface,
-        public RepositorySetsInterface,
         public RepositoryEnvironmentVariableInterface,
         public RepositoryMirrorsInterface,
         public RepositoryVirtualsInterface,
@@ -127,12 +126,6 @@ namespace paludis
             /* RepositoryManifestInterface */
             virtual void make_manifest(const QualifiedPackageName & qpn);
 
-            /* RepositorySetsInterface */
-
-            virtual const std::tr1::shared_ptr<const SetSpecTree> package_set(const SetName & id) const;
-
-            virtual std::tr1::shared_ptr<const SetNameSet> sets_list() const;
-
             /* RepositorySyncableInterface */
 
             virtual bool sync(const std::tr1::shared_ptr<OutputManager> &) const;
@@ -238,6 +231,13 @@ namespace paludis
             const std::tr1::shared_ptr<const UseDesc> use_desc() const PALUDIS_ATTRIBUTE((warn_unused_result));
 
             const std::string eapi_for_file(const FSEntry &) const PALUDIS_ATTRIBUTE((warn_unused_result));
+
+            ///\name Set methods
+            ///\{
+
+            virtual void populate_sets() const;
+
+            ///\}
     };
 }
 
diff --git a/paludis/repositories/e/e_repository_sets_TEST.cc b/paludis/repositories/e/e_repository_sets_TEST.cc
index a5cc45b..d138eb8 100644
--- a/paludis/repositories/e/e_repository_sets_TEST.cc
+++ b/paludis/repositories/e/e_repository_sets_TEST.cc
@@ -62,13 +62,12 @@ namespace test_cases
             keys->insert("profiles", "e_repository_sets_TEST_dir/repo1/profiles/profile");
             std::tr1::shared_ptr<Repository> repo(ERepository::repository_factory_create(&env,
                         std::tr1::bind(from_keys, keys, std::tr1::placeholders::_1)));
+            env.package_database()->add_repository(1, repo);
 
-            std::tr1::shared_ptr<const SetNameSet> sets_list(repo->sets_interface()->sets_list());
-            TEST_CHECK_EQUAL(sets_list->size(), 4U);
-            TEST_CHECK(sets_list->end() != sets_list->find(SetName("system")));
-            TEST_CHECK(sets_list->end() != sets_list->find(SetName("security")));
-            TEST_CHECK(sets_list->end() != sets_list->find(SetName("insecurity")));
-            TEST_CHECK(sets_list->end() != sets_list->find(SetName("set1")));
+            std::tr1::shared_ptr<const SetNameSet> sets_list(env.set_names());
+            TEST_CHECK_EQUAL(join(sets_list->begin(), sets_list->end(), " "), "everything everything::default insecurity "
+                    "insecurity::test-repo-1 security security::test-repo-1 set1 set1* set1::test-repo-1 set1::test-repo-1* "
+                    "system system::test-repo-1 world world::default");
         }
     } test_e_repository_sets_sets_list;
 
@@ -90,8 +89,10 @@ namespace test_cases
                 new FakeInstalledRepository(&env, RepositoryName("installed")));
             installed->add_version("cat-two", "bar", "1.5");
             env.package_database()->add_repository(0, installed);
+            env.package_database()->add_repository(1, repo);
 
-            std::tr1::shared_ptr<const SetSpecTree> set1(repo->sets_interface()->package_set(SetName("set1")));
+            std::tr1::shared_ptr<const SetSpecTree> set1(env.set(SetName("set1::test-repo-1")));
+            TEST_CHECK(set1);
             StringifyFormatter ff;
             erepository::DepSpecPrettyPrinter pretty(0, std::tr1::shared_ptr<const PackageID>(), ff, 0, false, false);
             set1->root()->accept(pretty);
@@ -121,7 +122,7 @@ namespace test_cases
                         std::tr1::bind(from_keys, keys, std::tr1::placeholders::_1)));
             env.package_database()->add_repository(1, repo);
 
-            std::tr1::shared_ptr<const SetSpecTree> insecurity(repo->sets_interface()->package_set(SetName("insecurity")));
+            std::tr1::shared_ptr<const SetSpecTree> insecurity(env.set(SetName("insecurity::test-repo-1")));
             StringifyFormatter ff;
             erepository::DepSpecPrettyPrinter pretty(0, std::tr1::shared_ptr<const PackageID>(), ff, 0, false, false);
             insecurity->root()->accept(pretty);
@@ -161,7 +162,7 @@ namespace test_cases
             installed->add_version("cat-four", "xyzzy", "2.0.1")->set_slot(SlotName("2"));
             env.package_database()->add_repository(0, installed);
 
-            std::tr1::shared_ptr<const SetSpecTree> security(repo->sets_interface()->package_set(SetName("security")));
+            std::tr1::shared_ptr<const SetSpecTree> security(env.set(SetName("security::test-repo-1")));
             StringifyFormatter ff;
             erepository::DepSpecPrettyPrinter pretty(0, std::tr1::shared_ptr<const PackageID>(), ff, 0, false, false);
             security->root()->accept(pretty);
diff --git a/paludis/repositories/e/exndbam_repository.cc b/paludis/repositories/e/exndbam_repository.cc
index 6c5489c..34a18c7 100644
--- a/paludis/repositories/e/exndbam_repository.cc
+++ b/paludis/repositories/e/exndbam_repository.cc
@@ -112,7 +112,6 @@ ExndbamRepository::ExndbamRepository(const RepositoryName & n, const ExndbamRepo
                 value_for<n::mirrors_interface>(static_cast<RepositoryMirrorsInterface *>(0)),
                 value_for<n::provides_interface>(static_cast<RepositoryProvidesInterface *>(0)),
                 value_for<n::qa_interface>(static_cast<RepositoryQAInterface *>(0)),
-                value_for<n::sets_interface>(this),
                 value_for<n::syncable_interface>(static_cast<RepositorySyncableInterface *>(0)),
                 value_for<n::virtuals_interface>(static_cast<RepositoryVirtualsInterface *>(0))
             )),
diff --git a/paludis/repositories/e/vdb_repository.cc b/paludis/repositories/e/vdb_repository.cc
index 1d4eaed..ee0a1bd 100644
--- a/paludis/repositories/e/vdb_repository.cc
+++ b/paludis/repositories/e/vdb_repository.cc
@@ -167,7 +167,6 @@ VDBRepository::VDBRepository(const VDBRepositoryParams & p) :
                 value_for<n::mirrors_interface>(static_cast<RepositoryMirrorsInterface *>(0)),
                 value_for<n::provides_interface>(this),
                 value_for<n::qa_interface>(static_cast<RepositoryQAInterface *>(0)),
-                value_for<n::sets_interface>(this),
                 value_for<n::syncable_interface>(static_cast<RepositorySyncableInterface *>(0)),
                 value_for<n::virtuals_interface>(static_cast<RepositoryVirtualsInterface *>(0))
             )),
diff --git a/paludis/repositories/fake/fake_installed_repository.cc b/paludis/repositories/fake/fake_installed_repository.cc
index 5a7f23e..814b729 100644
--- a/paludis/repositories/fake/fake_installed_repository.cc
+++ b/paludis/repositories/fake/fake_installed_repository.cc
@@ -65,7 +65,6 @@ FakeInstalledRepository::FakeInstalledRepository(const Environment * const e, co
                 value_for<n::mirrors_interface>(static_cast<RepositoryMirrorsInterface *>(0)),
                 value_for<n::provides_interface>(this),
                 value_for<n::qa_interface>(static_cast<RepositoryQAInterface *>(0)),
-                value_for<n::sets_interface>(this),
                 value_for<n::syncable_interface>(static_cast<RepositorySyncableInterface *>(0)),
                 value_for<n::virtuals_interface>(static_cast<RepositoryVirtualsInterface *>(0))
                 )),
diff --git a/paludis/repositories/fake/fake_repository.cc b/paludis/repositories/fake/fake_repository.cc
index 9bca810..765fb28 100644
--- a/paludis/repositories/fake/fake_repository.cc
+++ b/paludis/repositories/fake/fake_repository.cc
@@ -1,7 +1,7 @@
 /* vim: set sw=4 sts=4 et foldmethod=syntax : */
 
 /*
- * Copyright (c) 2005, 2006, 2007, 2008 Ciaran McCreesh
+ * Copyright (c) 2005, 2006, 2007, 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
@@ -68,7 +68,6 @@ FakeRepository::FakeRepository(const Environment * const env, const RepositoryNa
                 value_for<n::mirrors_interface>(this),
                 value_for<n::provides_interface>(static_cast<RepositoryProvidesInterface *>(0)),
                 value_for<n::qa_interface>(static_cast<RepositoryQAInterface *>(0)),
-                value_for<n::sets_interface>(this),
                 value_for<n::syncable_interface>(static_cast<RepositorySyncableInterface *>(0)),
                 value_for<n::virtuals_interface>((*DistributionData::get_instance()->distribution_from_string(
                             env->distribution())).support_old_style_virtuals() ? this : 0)
@@ -90,7 +89,6 @@ FakeRepository::FakeRepository(const FakeRepositoryParams & params) :
                 value_for<n::mirrors_interface>(this),
                 value_for<n::provides_interface>(static_cast<RepositoryProvidesInterface *>(0)),
                 value_for<n::qa_interface>(static_cast<RepositoryQAInterface *>(0)),
-                value_for<n::sets_interface>(this),
                 value_for<n::syncable_interface>(static_cast<RepositorySyncableInterface *>(0)),
                 value_for<n::virtuals_interface>((*DistributionData::get_instance()->distribution_from_string(
                             params.environment()->distribution())).support_old_style_virtuals() ? this : 0)
diff --git a/paludis/repositories/fake/fake_repository_base.cc b/paludis/repositories/fake/fake_repository_base.cc
index 8f0515b..51ce369 100644
--- a/paludis/repositories/fake/fake_repository_base.cc
+++ b/paludis/repositories/fake/fake_repository_base.cc
@@ -48,7 +48,6 @@ namespace paludis
         std::tr1::shared_ptr<CategoryNamePartSet> category_names;
         std::map<CategoryNamePart, std::tr1::shared_ptr<PackageNamePartSet> > package_names;
         std::map<QualifiedPackageName, std::tr1::shared_ptr<PackageIDSequence> > ids;
-        std::map<SetName, std::tr1::shared_ptr<const SetSpecTree> > sets;
 
         const Environment * const env;
 
@@ -164,31 +163,6 @@ FakeRepositoryBase::invalidate_masks()
             (*it2)->invalidate_masks();
 }
 
-void
-FakeRepositoryBase::add_package_set(const SetName & n, const std::tr1::shared_ptr<const SetSpecTree> & s)
-{
-    _imp->sets.insert(std::make_pair(n, s));
-}
-
-const std::tr1::shared_ptr<const SetSpecTree>
-FakeRepositoryBase::package_set(const SetName & id) const
-{
-    std::map<SetName, std::tr1::shared_ptr<const SetSpecTree> >::const_iterator i(_imp->sets.find(id));
-    if (_imp->sets.end() == i)
-        return std::tr1::shared_ptr<const SetSpecTree>();
-    else
-        return i->second;
-}
-
-std::tr1::shared_ptr<const SetNameSet>
-FakeRepositoryBase::sets_list() const
-{
-    std::tr1::shared_ptr<SetNameSet> result(new SetNameSet);
-    std::transform(_imp->sets.begin(), _imp->sets.end(), result->inserter(),
-            std::tr1::mem_fn(&std::pair<const SetName, std::tr1::shared_ptr<const SetSpecTree> >::first));
-    return result;
-}
-
 const Environment *
 FakeRepositoryBase::environment() const
 {
@@ -200,3 +174,8 @@ FakeRepositoryBase::need_keys_added() const
 {
 }
 
+void
+FakeRepositoryBase::populate_sets() const
+{
+}
+
diff --git a/paludis/repositories/fake/fake_repository_base.hh b/paludis/repositories/fake/fake_repository_base.hh
index 136530a..b2548b5 100644
--- a/paludis/repositories/fake/fake_repository_base.hh
+++ b/paludis/repositories/fake/fake_repository_base.hh
@@ -44,7 +44,6 @@ namespace paludis
      */
     class PALUDIS_VISIBLE FakeRepositoryBase :
         public Repository,
-        public RepositorySetsInterface,
         private PrivateImplementationPattern<FakeRepositoryBase>,
         public std::tr1::enable_shared_from_this<FakeRepositoryBase>
     {
@@ -90,11 +89,6 @@ namespace paludis
             std::tr1::shared_ptr<FakePackageID> add_version(const std::string & c, const std::string & p,
                     const std::string & v);
 
-            /**
-             * Add a package set.
-             */
-            void add_package_set(const SetName &, const std::tr1::shared_ptr<const SetSpecTree> &);
-
             virtual void invalidate();
 
             virtual void invalidate_masks();
@@ -104,14 +98,6 @@ namespace paludis
              */
             const Environment * environment() const;
 
-            /* RepositorySetsInterface */
-
-            virtual const std::tr1::shared_ptr<const SetSpecTree> package_set(const SetName & id) const
-                PALUDIS_ATTRIBUTE((warn_unused_result));
-
-            virtual std::tr1::shared_ptr<const SetNameSet> sets_list() const
-                PALUDIS_ATTRIBUTE((warn_unused_result));
-
             /* Repository */
 
             virtual std::tr1::shared_ptr<const PackageIDSequence> package_ids(
@@ -130,6 +116,13 @@ namespace paludis
 
             virtual bool has_category_named(const CategoryNamePart &) const
                 PALUDIS_ATTRIBUTE((warn_unused_result));
+
+            ///\name Set methods
+            ///\{
+
+            virtual void populate_sets() const;
+
+            ///\}
     };
 }
 
diff --git a/paludis/repositories/gems/gems_repository.cc b/paludis/repositories/gems/gems_repository.cc
index d021eb9..13530b5 100644
--- a/paludis/repositories/gems/gems_repository.cc
+++ b/paludis/repositories/gems/gems_repository.cc
@@ -100,7 +100,6 @@ GemsRepository::GemsRepository(const gems::RepositoryParams & params) :
                 value_for<n::mirrors_interface>(static_cast<RepositoryMirrorsInterface *>(0)),
                 value_for<n::provides_interface>(static_cast<RepositoryProvidesInterface *>(0)),
                 value_for<n::qa_interface>(static_cast<RepositoryQAInterface *>(0)),
-                value_for<n::sets_interface>(static_cast<RepositorySetsInterface *>(0)),
                 value_for<n::syncable_interface>(static_cast<RepositorySyncableInterface *>(0)),
                 value_for<n::virtuals_interface>(static_cast<RepositoryVirtualsInterface *>(0))
             )),
@@ -406,3 +405,8 @@ GemsRepository::repository_factory_dependencies(
     return make_shared_ptr(new RepositoryNameSet);
 }
 
+void
+GemsRepository::populate_sets() const
+{
+}
+
diff --git a/paludis/repositories/gems/gems_repository.hh b/paludis/repositories/gems/gems_repository.hh
index e380e78..1d5ac0d 100644
--- a/paludis/repositories/gems/gems_repository.hh
+++ b/paludis/repositories/gems/gems_repository.hh
@@ -1,7 +1,7 @@
 /* vim: set sw=4 sts=4 et foldmethod=syntax : */
 
 /*
- * Copyright (c) 2007, 2008 Ciaran McCreesh
+ * Copyright (c) 2007, 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
@@ -106,6 +106,13 @@ namespace paludis
                     const std::tr1::function<std::string (const std::string &)> &);
 
             ///\}
+
+            ///\name Set methods
+            ///\{
+
+            virtual void populate_sets() const;
+
+            ///\}
     };
 }
 
diff --git a/paludis/repositories/gems/installed_gems_repository.cc b/paludis/repositories/gems/installed_gems_repository.cc
index a7026ba..96c5e09 100644
--- a/paludis/repositories/gems/installed_gems_repository.cc
+++ b/paludis/repositories/gems/installed_gems_repository.cc
@@ -41,6 +41,10 @@
 #include <paludis/literal_metadata_key.hh>
 #include <paludis/distribution.hh>
 #include <paludis/action.hh>
+#include <paludis/generator.hh>
+#include <paludis/filter.hh>
+#include <paludis/filtered_generator.hh>
+#include <paludis/selection.hh>
 #include <tr1/unordered_map>
 
 using namespace paludis;
@@ -100,7 +104,6 @@ InstalledGemsRepository::InstalledGemsRepository(const gems::InstalledRepository
                 value_for<n::mirrors_interface>(static_cast<RepositoryMirrorsInterface *>(0)),
                 value_for<n::provides_interface>(static_cast<RepositoryProvidesInterface *>(0)),
                 value_for<n::qa_interface>(static_cast<RepositoryQAInterface *>(0)),
-                value_for<n::sets_interface>(static_cast<RepositorySetsInterface *>(0)),
                 value_for<n::syncable_interface>(static_cast<RepositorySyncableInterface *>(0)),
                 value_for<n::virtuals_interface>(static_cast<RepositoryVirtualsInterface *>(0))
             )),
@@ -418,3 +421,36 @@ InstalledGemsRepository::repository_factory_create(
                 )));
 }
 
+namespace
+{
+    std::tr1::shared_ptr<SetSpecTree> get_everything_set(
+            const Environment * const env,
+            const Repository * const repo)
+    {
+        Context context("When making 'everything' set from '" + stringify(repo->name()) + "':");
+
+        std::tr1::shared_ptr<SetSpecTree> result(new SetSpecTree(make_shared_ptr(new AllDepSpec)));
+
+        std::tr1::shared_ptr<const PackageIDSequence> ids((*env)[selection::BestVersionOnly(
+                    generator::InRepository(repo->name()))]);
+        for (PackageIDSequence::ConstIterator i(ids->begin()), i_end(ids->end()) ;
+                i != i_end ; ++i)
+            result->root()->append(make_shared_ptr(new PackageDepSpec(
+                            make_package_dep_spec(PartiallyMadePackageDepSpecOptions())
+                            .package((*i)->name())
+                            )));
+
+        return result;
+    }
+}
+
+void
+InstalledGemsRepository::populate_sets() const
+{
+    _imp->params.environment()->add_set(
+            SetName("everything"),
+            SetName("everything::" + stringify(name())),
+            std::tr1::bind(get_everything_set, _imp->params.environment(), this),
+            true);
+}
+
diff --git a/paludis/repositories/gems/installed_gems_repository.hh b/paludis/repositories/gems/installed_gems_repository.hh
index 2b7323e..22a9fc0 100644
--- a/paludis/repositories/gems/installed_gems_repository.hh
+++ b/paludis/repositories/gems/installed_gems_repository.hh
@@ -1,7 +1,7 @@
 /* vim: set sw=4 sts=4 et foldmethod=syntax : */
 
 /*
- * Copyright (c) 2007, 2008 Ciaran McCreesh
+ * Copyright (c) 2007, 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
@@ -121,6 +121,13 @@ namespace paludis
                     const std::tr1::function<std::string (const std::string &)> &);
 
             ///\}
+
+            ///\name Set methods
+            ///\{
+
+            virtual void populate_sets() const;
+
+            ///\}
     };
 }
 
diff --git a/paludis/repositories/unavailable/unavailable_repository.cc b/paludis/repositories/unavailable/unavailable_repository.cc
index ed26457..2ed4b43 100644
--- a/paludis/repositories/unavailable/unavailable_repository.cc
+++ b/paludis/repositories/unavailable/unavailable_repository.cc
@@ -94,7 +94,6 @@ UnavailableRepository::UnavailableRepository(const UnavailableRepositoryParams &
                 value_for<n::mirrors_interface>(static_cast<RepositoryMirrorsInterface *>(0)),
                 value_for<n::provides_interface>(static_cast<RepositoryProvidesInterface *>(0)),
                 value_for<n::qa_interface>(static_cast<RepositoryQAInterface *>(0)),
-                value_for<n::sets_interface>(static_cast<RepositorySetsInterface *>(0)),
                 value_for<n::syncable_interface>(this),
                 value_for<n::virtuals_interface>(static_cast<RepositoryVirtualsInterface *>(0))
                 )),
@@ -345,5 +344,10 @@ UnavailableRepository::repository_factory_dependencies(
     return make_shared_ptr(new RepositoryNameSet);
 }
 
+void
+UnavailableRepository::populate_sets() const
+{
+}
+
 template class PrivateImplementationPattern<unavailable_repository::UnavailableRepository>;
 
diff --git a/paludis/repositories/unavailable/unavailable_repository.hh b/paludis/repositories/unavailable/unavailable_repository.hh
index 68a15fb..657093b 100644
--- a/paludis/repositories/unavailable/unavailable_repository.hh
+++ b/paludis/repositories/unavailable/unavailable_repository.hh
@@ -110,7 +110,14 @@ namespace paludis
                         const std::tr1::function<std::string (const std::string &)> &);
 
                 ///\}
-        };
+
+                ///\name Set methods
+                ///\{
+
+                virtual void populate_sets() const;
+
+                ///\}
+            };
     }
 
 #ifdef PALUDIS_HAVE_EXTERN_TEMPLATE
diff --git a/paludis/repositories/unpackaged/installed_repository.cc b/paludis/repositories/unpackaged/installed_repository.cc
index dc154ab..c8431e3 100644
--- a/paludis/repositories/unpackaged/installed_repository.cc
+++ b/paludis/repositories/unpackaged/installed_repository.cc
@@ -42,6 +42,10 @@
 #include <paludis/metadata_key.hh>
 #include <paludis/literal_metadata_key.hh>
 #include <paludis/user_dep_spec.hh>
+#include <paludis/generator.hh>
+#include <paludis/filtered_generator.hh>
+#include <paludis/filter.hh>
+#include <paludis/selection.hh>
 #include <sstream>
 #include <sys/time.h>
 
@@ -95,7 +99,6 @@ InstalledUnpackagedRepository::InstalledUnpackagedRepository(
                 value_for<n::mirrors_interface>(static_cast<RepositoryMirrorsInterface *>(0)),
                 value_for<n::provides_interface>(static_cast<RepositoryProvidesInterface *>(0)),
                 value_for<n::qa_interface>(static_cast<RepositoryQAInterface *>(0)),
-                value_for<n::sets_interface>(this),
                 value_for<n::syncable_interface>(static_cast<RepositorySyncableInterface *>(0)),
                 value_for<n::virtuals_interface>(static_cast<RepositoryVirtualsInterface *>(0))
             )),
@@ -417,50 +420,6 @@ InstalledUnpackagedRepository::deindex(const QualifiedPackageName & q) const
     _imp->ndbam.deindex(q);
 }
 
-const std::tr1::shared_ptr<const SetSpecTree>
-InstalledUnpackagedRepository::package_set(const SetName & s) const
-{
-    using namespace std::tr1::placeholders;
-
-    Context context("When fetching package set '" + stringify(s) + "' from '" +
-            stringify(name()) + "':");
-
-    if ("everything" == s.data())
-    {
-        std::tr1::shared_ptr<SetSpecTree> result(new SetSpecTree(make_shared_ptr(new AllDepSpec)));
-        std::tr1::shared_ptr<GeneralSetDepTag> tag(new GeneralSetDepTag(s, stringify(name())));
-
-        std::tr1::shared_ptr<const CategoryNamePartSet> cats(category_names());
-        for (CategoryNamePartSet::ConstIterator c(cats->begin()), c_end(cats->end()) ;
-                c != c_end ; ++c)
-        {
-            std::tr1::shared_ptr<const QualifiedPackageNameSet> pkgs(package_names(*c));
-            for (QualifiedPackageNameSet::ConstIterator e(pkgs->begin()), e_end(pkgs->end()) ;
-                    e != e_end ; ++e)
-            {
-                std::tr1::shared_ptr<PackageDepSpec> spec(new PackageDepSpec(make_package_dep_spec(PartiallyMadePackageDepSpecOptions()
-                                ).package(QualifiedPackageName(*e))));
-                spec->set_tag(tag);
-                result->root()->append(spec);
-            }
-        }
-
-        return result;
-    }
-    else
-        return make_null_shared_ptr();
-}
-
-std::tr1::shared_ptr<const SetNameSet>
-InstalledUnpackagedRepository::sets_list() const
-{
-    Context context("While generating the list of sets:");
-
-    std::tr1::shared_ptr<SetNameSet> result(new SetNameSet);
-    result->insert(SetName("everything"));
-    return result;
-}
-
 void
 InstalledUnpackagedRepository::need_keys_added() const
 {
@@ -523,3 +482,36 @@ InstalledUnpackagedRepository::repository_factory_dependencies(
     return make_shared_ptr(new RepositoryNameSet);
 }
 
+namespace
+{
+    std::tr1::shared_ptr<SetSpecTree> get_everything_set(
+            const Environment * const env,
+            const Repository * const repo)
+    {
+        Context context("When making 'everything' set from '" + stringify(repo->name()) + "':");
+
+        std::tr1::shared_ptr<SetSpecTree> result(new SetSpecTree(make_shared_ptr(new AllDepSpec)));
+
+        std::tr1::shared_ptr<const PackageIDSequence> ids((*env)[selection::BestVersionOnly(
+                    generator::InRepository(repo->name()))]);
+        for (PackageIDSequence::ConstIterator i(ids->begin()), i_end(ids->end()) ;
+                i != i_end ; ++i)
+            result->root()->append(make_shared_ptr(new PackageDepSpec(
+                            make_package_dep_spec(PartiallyMadePackageDepSpecOptions())
+                            .package((*i)->name())
+                            )));
+
+        return result;
+    }
+}
+
+void
+InstalledUnpackagedRepository::populate_sets() const
+{
+    _imp->params.environment()->add_set(
+            SetName("everything"),
+            SetName("everything::" + stringify(name())),
+            std::tr1::bind(get_everything_set, _imp->params.environment(), this),
+            true);
+}
+
diff --git a/paludis/repositories/unpackaged/installed_repository.hh b/paludis/repositories/unpackaged/installed_repository.hh
index 11f7dc2..1189e8b 100644
--- a/paludis/repositories/unpackaged/installed_repository.hh
+++ b/paludis/repositories/unpackaged/installed_repository.hh
@@ -1,7 +1,7 @@
 /* vim: set sw=4 sts=4 et foldmethod=syntax : */
 
 /*
- * Copyright (c) 2007, 2008 Ciaran McCreesh
+ * Copyright (c) 2007, 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
@@ -47,8 +47,7 @@ namespace paludis
     class PALUDIS_VISIBLE InstalledUnpackagedRepository :
         private PrivateImplementationPattern<InstalledUnpackagedRepository>,
         public Repository,
-        public RepositoryDestinationInterface,
-        public RepositorySetsInterface
+        public RepositoryDestinationInterface
     {
         private:
             PrivateImplementationPattern<InstalledUnpackagedRepository>::ImpPtr & _imp;
@@ -80,9 +79,6 @@ namespace paludis
 
             void deindex(const QualifiedPackageName &) const;
 
-            virtual std::tr1::shared_ptr<const SetNameSet> sets_list() const
-                PALUDIS_ATTRIBUTE((warn_unused_result));
-
             virtual std::tr1::shared_ptr<const PackageIDSequence> package_ids(
                     const QualifiedPackageName &) const
                 PALUDIS_ATTRIBUTE((warn_unused_result));
@@ -106,9 +102,6 @@ namespace paludis
 
             virtual bool some_ids_might_support_action(const SupportsActionTestBase &) const;
 
-            virtual const std::tr1::shared_ptr<const SetSpecTree> package_set(const SetName & id) const
-                PALUDIS_ATTRIBUTE((warn_unused_result));
-
             /* Keys */
 
             virtual const std::tr1::shared_ptr<const MetadataValueKey<std::string> > format_key() const;
@@ -131,6 +124,13 @@ namespace paludis
                     const std::tr1::function<std::string (const std::string &)> &);
 
             ///\}
+
+            ///\name Set methods
+            ///\{
+
+            virtual void populate_sets() const;
+
+            ///\}
     };
 }
 
diff --git a/paludis/repositories/unpackaged/unpackaged_repository.cc b/paludis/repositories/unpackaged/unpackaged_repository.cc
index e3ca4c4..05022ca 100644
--- a/paludis/repositories/unpackaged/unpackaged_repository.cc
+++ b/paludis/repositories/unpackaged/unpackaged_repository.cc
@@ -104,7 +104,6 @@ UnpackagedRepository::UnpackagedRepository(const RepositoryName & n,
                 value_for<n::mirrors_interface>(static_cast<RepositoryMirrorsInterface *>(0)),
                 value_for<n::provides_interface>(static_cast<RepositoryProvidesInterface *>(0)),
                 value_for<n::qa_interface>(static_cast<RepositoryQAInterface *>(0)),
-                value_for<n::sets_interface>(static_cast<RepositorySetsInterface *>(0)),
                 value_for<n::syncable_interface>(static_cast<RepositorySyncableInterface *>(0)),
                 value_for<n::virtuals_interface>(static_cast<RepositoryVirtualsInterface *>(0))
             )),
@@ -278,3 +277,8 @@ UnpackagedRepository::repository_factory_dependencies(
     return make_shared_ptr(new RepositoryNameSet);
 }
 
+void
+UnpackagedRepository::populate_sets() const
+{
+}
+
diff --git a/paludis/repositories/unpackaged/unpackaged_repository.hh b/paludis/repositories/unpackaged/unpackaged_repository.hh
index 826cadc..2b60131 100644
--- a/paludis/repositories/unpackaged/unpackaged_repository.hh
+++ b/paludis/repositories/unpackaged/unpackaged_repository.hh
@@ -1,7 +1,7 @@
 /* vim: set sw=4 sts=4 et foldmethod=syntax : */
 
 /*
- * Copyright (c) 2007, 2008 Ciaran McCreesh
+ * Copyright (c) 2007, 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
@@ -123,6 +123,13 @@ namespace paludis
                     const std::tr1::function<std::string (const std::string &)> &);
 
             ///\}
+
+            ///\name Set methods
+            ///\{
+
+            virtual void populate_sets() const;
+
+            ///\}
     };
 }
 
diff --git a/paludis/repositories/unwritten/unwritten_repository.cc b/paludis/repositories/unwritten/unwritten_repository.cc
index 4eed1d9..7c7f032 100644
--- a/paludis/repositories/unwritten/unwritten_repository.cc
+++ b/paludis/repositories/unwritten/unwritten_repository.cc
@@ -94,7 +94,6 @@ UnwrittenRepository::UnwrittenRepository(const UnwrittenRepositoryParams & p) :
                 value_for<n::mirrors_interface>(static_cast<RepositoryMirrorsInterface *>(0)),
                 value_for<n::provides_interface>(static_cast<RepositoryProvidesInterface *>(0)),
                 value_for<n::qa_interface>(static_cast<RepositoryQAInterface *>(0)),
-                value_for<n::sets_interface>(static_cast<RepositorySetsInterface *>(0)),
                 value_for<n::syncable_interface>(this),
                 value_for<n::virtuals_interface>(static_cast<RepositoryVirtualsInterface *>(0))
                 )),
@@ -345,6 +344,11 @@ UnwrittenRepository::repository_factory_dependencies(
     return make_shared_ptr(new RepositoryNameSet);
 }
 
+void
+UnwrittenRepository::populate_sets() const
+{
+}
+
 template class PrivateImplementationPattern<unwritten_repository::UnwrittenRepository>;
 
 
diff --git a/paludis/repositories/unwritten/unwritten_repository.hh b/paludis/repositories/unwritten/unwritten_repository.hh
index f61a687..bcb9a38 100644
--- a/paludis/repositories/unwritten/unwritten_repository.hh
+++ b/paludis/repositories/unwritten/unwritten_repository.hh
@@ -109,6 +109,13 @@ namespace paludis
                         const std::tr1::function<std::string (const std::string &)> &);
 
                 ///\}
+
+                ///\name Set methods
+                ///\{
+
+                virtual void populate_sets() const;
+
+                ///\}
         };
     }
 
diff --git a/paludis/repositories/virtuals/installed_virtuals_repository.cc b/paludis/repositories/virtuals/installed_virtuals_repository.cc
index 60820bf..98bf8bd 100644
--- a/paludis/repositories/virtuals/installed_virtuals_repository.cc
+++ b/paludis/repositories/virtuals/installed_virtuals_repository.cc
@@ -119,7 +119,6 @@ InstalledVirtualsRepository::InstalledVirtualsRepository(const Environment * con
                 value_for<n::mirrors_interface>(static_cast<RepositoryMirrorsInterface *>(0)),
                 value_for<n::provides_interface>(static_cast<RepositoryProvidesInterface *>(0)),
                 value_for<n::qa_interface>(static_cast<RepositoryQAInterface *>(0)),
-                value_for<n::sets_interface>(static_cast<RepositorySetsInterface *>(0)),
                 value_for<n::syncable_interface>(static_cast<RepositorySyncableInterface *>(0)),
                 value_for<n::virtuals_interface>(static_cast<RepositoryVirtualsInterface *>(0))
             )),
@@ -389,3 +388,8 @@ InstalledVirtualsRepository::merge(const MergeParams &)
     throw InternalError(PALUDIS_HERE, "can't merge to installed virtuals");
 }
 
+void
+InstalledVirtualsRepository::populate_sets() const
+{
+}
+
diff --git a/paludis/repositories/virtuals/installed_virtuals_repository.hh b/paludis/repositories/virtuals/installed_virtuals_repository.hh
index af9e9e0..5a72619 100644
--- a/paludis/repositories/virtuals/installed_virtuals_repository.hh
+++ b/paludis/repositories/virtuals/installed_virtuals_repository.hh
@@ -126,6 +126,11 @@ namespace paludis
 
             virtual void merge(const MergeParams &) PALUDIS_ATTRIBUTE((noreturn));
 
+            ///\name Set methods
+            ///\{
+
+            virtual void populate_sets() const;
+
             ///\}
     };
 }
diff --git a/paludis/repositories/virtuals/virtuals_repository.cc b/paludis/repositories/virtuals/virtuals_repository.cc
index 9bbb64d..f88c59c 100644
--- a/paludis/repositories/virtuals/virtuals_repository.cc
+++ b/paludis/repositories/virtuals/virtuals_repository.cc
@@ -130,7 +130,6 @@ VirtualsRepository::VirtualsRepository(const Environment * const env) :
                 value_for<n::mirrors_interface>(static_cast<RepositoryMirrorsInterface *>(0)),
                 value_for<n::provides_interface>(static_cast<RepositoryProvidesInterface *>(0)),
                 value_for<n::qa_interface>(static_cast<RepositoryQAInterface *>(0)),
-                value_for<n::sets_interface>(static_cast<RepositorySetsInterface *>(0)),
                 value_for<n::syncable_interface>(static_cast<RepositorySyncableInterface *>(0)),
                 value_for<n::virtuals_interface>(static_cast<RepositoryVirtualsInterface *>(0))
             )),
@@ -459,3 +458,8 @@ VirtualsRepository::repository_factory_dependencies(
     return make_shared_ptr(new RepositoryNameSet);
 }
 
+void
+VirtualsRepository::populate_sets() const
+{
+}
+
diff --git a/paludis/repositories/virtuals/virtuals_repository.hh b/paludis/repositories/virtuals/virtuals_repository.hh
index ce7e26e..cf33555 100644
--- a/paludis/repositories/virtuals/virtuals_repository.hh
+++ b/paludis/repositories/virtuals/virtuals_repository.hh
@@ -1,7 +1,7 @@
 /* vim: set sw=4 sts=4 et foldmethod=syntax : */
 
 /*
- * Copyright (c) 2006, 2007, 2008 Ciaran McCreesh
+ * Copyright (c) 2006, 2007, 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
@@ -114,6 +114,13 @@ namespace paludis
             virtual const std::tr1::shared_ptr<const MetadataValueKey<std::string> > format_key() const;
             virtual const std::tr1::shared_ptr<const MetadataValueKey<FSEntry> > location_key() const;
             virtual const std::tr1::shared_ptr<const MetadataValueKey<FSEntry> > installed_root_key() const;
+
+            ///\name Set methods
+            ///\{
+
+            virtual void populate_sets() const;
+
+            ///\}
     };
 }
 
diff --git a/paludis/repository-fwd.hh b/paludis/repository-fwd.hh
index f014b35..7cdc8cd 100644
--- a/paludis/repository-fwd.hh
+++ b/paludis/repository-fwd.hh
@@ -42,7 +42,6 @@ namespace paludis
     class HookResult;
 
     class Repository;
-    class RepositorySetsInterface;
     class RepositorySyncableInterface;
     class RepositoryEnvironmentVariableInterface;
     class RepositoryMirrorsInterface;
diff --git a/paludis/repository.cc b/paludis/repository.cc
index 671907c..e2df2d0 100644
--- a/paludis/repository.cc
+++ b/paludis/repository.cc
@@ -65,12 +65,20 @@ NoSuchSetError::NoSuchSetError(const std::string & our_name) throw () :
 {
 }
 
+NoSuchSetError::~NoSuchSetError() throw ()
+{
+}
+
 RecursivelyDefinedSetError::RecursivelyDefinedSetError(const std::string & our_name) throw () :
     Exception("Set '" + our_name + "' is recursively defined"),
     _name(our_name)
 {
 }
 
+RecursivelyDefinedSetError::~RecursivelyDefinedSetError() throw ()
+{
+}
+
 namespace paludis
 {
     namespace n
@@ -185,10 +193,6 @@ Repository::purge_invalid_cache() const
 {
 }
 
-RepositorySetsInterface::~RepositorySetsInterface()
-{
-}
-
 RepositorySyncableInterface::~RepositorySyncableInterface()
 {
 }
diff --git a/paludis/repository.hh b/paludis/repository.hh
index 7d873e0..34ca5d2 100644
--- a/paludis/repository.hh
+++ b/paludis/repository.hh
@@ -76,7 +76,6 @@ namespace paludis
         struct provided_by_spec;
         struct provides_interface;
         struct qa_interface;
-        struct sets_interface;
         struct status;
         struct syncable_interface;
         struct used_this_for_config_protect;
@@ -102,7 +101,6 @@ namespace paludis
         NamedValue<n::mirrors_interface, RepositoryMirrorsInterface *> mirrors_interface;
         NamedValue<n::provides_interface, RepositoryProvidesInterface *> provides_interface;
         NamedValue<n::qa_interface, RepositoryQAInterface *> qa_interface;
-        NamedValue<n::sets_interface, RepositorySetsInterface *> sets_interface;
         NamedValue<n::syncable_interface, RepositorySyncableInterface *> syncable_interface;
         NamedValue<n::virtuals_interface, RepositoryVirtualsInterface *> virtuals_interface;
     };
@@ -206,19 +204,14 @@ namespace paludis
 
             NoSuchSetError(const std::string & name) throw ();
 
-            virtual ~NoSuchSetError() throw ()
-            {
-            }
+            virtual ~NoSuchSetError() throw ();
 
             ///\}
 
             /**
              * Name of the set.
              */
-            const std::string & name() const
-            {
-                return _name;
-            }
+            const std::string name() const;
     };
 
     /**
@@ -240,19 +233,14 @@ namespace paludis
 
             RecursivelyDefinedSetError(const std::string & name) throw ();
 
-            virtual ~RecursivelyDefinedSetError() throw ()
-            {
-            }
+            virtual ~RecursivelyDefinedSetError() throw ();
 
             ///\}
 
             /**
              * Name of the set.
              */
-            const std::string & name() const
-            {
-                return _name;
-            }
+            const std::string name() const;
     };
 
     /**
@@ -407,35 +395,20 @@ namespace paludis
 
             ///\}
 
-    };
-
-    /**
-     * Interface for package sets for repositories.
-     *
-     * \see Repository
-     * \ingroup g_repository
-     * \nosubgrouping
-     */
-    class PALUDIS_VISIBLE RepositorySetsInterface
-    {
-        public:
-            ///\name Set queries
+            ///\name Set methods
             ///\{
 
             /**
-             * Fetch a package set.
-             */
-            virtual const std::tr1::shared_ptr<const SetSpecTree> package_set(const SetName & s) const = 0;
-
-            /**
-             * Gives a list of the names of all the sets provided by this repo.
+             * Call Environment::add_set for every set we define.
+             *
+             * Environment will call this method at most once, so no cache or check for
+             * repeats is required. Nothing else should call this method.
+             *
+             * \since 0.40
              */
-            virtual std::tr1::shared_ptr<const SetNameSet> sets_list() const
-                PALUDIS_ATTRIBUTE((warn_unused_result)) = 0;
+            virtual void populate_sets() const = 0;
 
             ///\}
-
-            virtual ~RepositorySetsInterface();
     };
 
     /**
diff --git a/paludis/uninstall_list_TEST.cc b/paludis/uninstall_list_TEST.cc
index 957c554..0a81968 100644
--- a/paludis/uninstall_list_TEST.cc
+++ b/paludis/uninstall_list_TEST.cc
@@ -46,6 +46,18 @@ namespace paludis
         s << *e.package_id();
         return s;
     }
+
+    template <typename T_>
+    T_ make_k_result(T_ t)
+    {
+        return t;
+    }
+
+    template <typename T_>
+    std::tr1::function<T_ ()> make_k(T_ t)
+    {
+        return std::tr1::bind(&make_k_result<T_>, t);
+    }
 }
 
 #ifdef ENABLE_VIRTUALS_REPOSITORY
@@ -373,7 +385,7 @@ namespace test_cases
         {
             std::tr1::shared_ptr<SetSpecTree> world(new SetSpecTree(make_shared_ptr(new AllDepSpec)));
             world->root()->append(make_shared_ptr(new PackageDepSpec(parse_user_package_dep_spec("foo/moo", &env, UserPackageDepSpecOptions()))));
-            installed_repo->add_package_set(SetName("world"), world);
+            env.add_set(SetName("world"), SetName("world"), make_k<std::tr1::shared_ptr<const SetSpecTree> >(world), false);
         }
 
         void populate_targets()
@@ -413,7 +425,7 @@ namespace test_cases
             std::tr1::shared_ptr<SetSpecTree> world(new SetSpecTree(make_shared_ptr(new AllDepSpec)));
             world->root()->append(make_shared_ptr(new PackageDepSpec(parse_user_package_dep_spec("foo/moo", &env, UserPackageDepSpecOptions()))));
             world->root()->append(make_shared_ptr(new PackageDepSpec(parse_user_package_dep_spec("foo/bar", &env, UserPackageDepSpecOptions()))));
-            installed_repo->add_package_set(SetName("world"), world);
+            env.add_set(SetName("world"), SetName("world"), make_k(world), false);
         }
 
         void populate_targets()
@@ -455,7 +467,7 @@ namespace test_cases
             world->root()->append(make_shared_ptr(new PackageDepSpec(parse_user_package_dep_spec("cat/needs-b", &env, UserPackageDepSpecOptions()))));
             world->root()->append(make_shared_ptr(new PackageDepSpec(parse_user_package_dep_spec("cat/needs-c", &env, UserPackageDepSpecOptions()))));
             world->root()->append(make_shared_ptr(new PackageDepSpec(parse_user_package_dep_spec("cat/needs-d", &env, UserPackageDepSpecOptions()))));
-            installed_repo->add_package_set(SetName("world"), world);
+            env.add_set(SetName("world"), SetName("world"), make_k(world), false);
         }
 
         void populate_targets()
diff --git a/paludis/user_dep_spec.cc b/paludis/user_dep_spec.cc
index 8d0bf66..bcc85e8 100644
--- a/paludis/user_dep_spec.cc
+++ b/paludis/user_dep_spec.cc
@@ -79,7 +79,7 @@ namespace
         if (s.empty())
             throw PackageDepSpecError("Got empty dep spec");
 
-        if (options[updso_throw_if_set] && std::string::npos == s.find_first_of("/:[<>=~"))
+        if (options[updso_throw_if_set] && std::string::npos == s.find_first_of("/[<>=~"))
             try
             {
                 SetName sn(s);
diff --git a/python/environment.cc b/python/environment.cc
index ff44881..043bb39 100644
--- a/python/environment.cc
+++ b/python/environment.cc
@@ -48,19 +48,22 @@ class EnvironmentImplementationWrapper :
     private:
         std::tr1::shared_ptr<PackageDatabase> _db;
 
-    protected:
-        virtual const std::tr1::shared_ptr<const SetSpecTree> local_set(const SetName & s) const
-            PALUDIS_ATTRIBUTE((warn_unused_result))
-        {
-            return make_null_shared_ptr();
-        }
-
     public:
         EnvironmentImplementationWrapper() :
             _db(new PackageDatabase(this))
         {
         }
 
+        virtual void populate_sets() const
+        {
+            Lock l(get_mutex());
+
+            if (bp::override f = get_override("populate_sets"))
+                f();
+            else
+                throw PythonMethodNotImplemented("EnvironmentImplementation", "populate_sets");
+        }
+
         virtual bool accept_license(const std::string & s, const PackageID & p) const
             PALUDIS_ATTRIBUTE((warn_unused_result))
         {
@@ -357,15 +360,6 @@ class EnvironmentImplementationWrapper :
                 throw PythonMethodNotImplemented("EnvironmentImplementation", "remove_from_world");
         }
 
-        virtual const std::tr1::shared_ptr<const SetSpecTree> world_set() const
-        {
-            Lock l(get_mutex());
-            if (bp::override f = get_override("world_set"))
-                return f();
-            else
-                throw PythonMethodNotImplemented("EnvironmentImplementation", "world_set");
-        }
-
         virtual std::tr1::shared_ptr<PackageIDSequence> operator[] (const Selection & fg) const
             PALUDIS_ATTRIBUTE((warn_unused_result))
         {
@@ -566,8 +560,6 @@ void expose_environment()
          "This class can be subclassed in Python.",
          bp::init<>()
         )
-        //FIXME - local_set is protected
-        //.def("local_set", bp::pure_virtual(&EnvImp::local_set))
 
         .def("accept_license", bp::pure_virtual(&EnvImp::accept_license),
                 "accept_license(str, PackageID) -> bool\n"
diff --git a/python/repository.cc b/python/repository.cc
index b343c73..67df17d 100644
--- a/python/repository.cc
+++ b/python/repository.cc
@@ -39,12 +39,6 @@ struct RepositoryWrapper :
     Repository,
     bp::wrapper<Repository>
 {
-    static RepositorySetsInterface *
-    get_sets_interface(const Repository & self)
-    {
-        return self.sets_interface();
-    }
-
     static RepositorySyncableInterface *
     get_syncable_interface(const Repository & self)
     {
@@ -216,11 +210,6 @@ void expose_repository()
                 "entirely when looking for installable packages."
             )
 
-        .add_property("sets_interface", bp::make_function(&RepositoryWrapper::get_sets_interface,
-                    bp::return_internal_reference<>()),
-                "[ro] RepositorySetsInterface"
-                )
-
         .add_property("syncable_interface", bp::make_function(&RepositoryWrapper::get_syncable_interface,
                     bp::return_internal_reference<>()),
                 "[ro] RepositorySyncableInterface"
@@ -308,16 +297,6 @@ void expose_repository()
         ;
 
     /**
-     * RepositorySetsInterface
-     */
-    bp::class_<RepositorySetsInterface, boost::noncopyable>
-        (
-         "RepositorySetsInterface",
-         "Interface for package sets for repositories.",
-         bp::no_init
-        );
-
-    /**
      * RepositorySyncableInterface
      */
     bp::class_<RepositorySyncableInterface, boost::noncopyable>
diff --git a/python/repository_TEST.py b/python/repository_TEST.py
index 3a34d6f..510312b 100755
--- a/python/repository_TEST.py
+++ b/python/repository_TEST.py
@@ -109,10 +109,6 @@ class TestCase_02_RepositoryInterfaces(unittest.TestCase):
         repo = db.fetch_repository("testrepo")
         irepo = db.fetch_repository("installed")
 
-    def test_02_sets_interface(self):
-        si = repo.sets_interface
-        self.assert_(isinstance(si, RepositorySetsInterface))
-
     def test_03_syncable_interface(self):
         si = repo.syncable_interface
         self.assert_(isinstance(si, RepositorySyncableInterface))
diff --git a/ruby/repository.cc b/ruby/repository.cc
index eebb6cc..dbdc6a8 100644
--- a/ruby/repository.cc
+++ b/ruby/repository.cc
@@ -311,14 +311,6 @@ namespace
      * Returns self if the repository supports the interface, otherwise Nil.
      */
     /*
-     * Document-method: sets_interface
-     *
-     * call-seq:
-     *     sets_interface -> self or Nil
-     *
-     * Returns self if the repository supports the interface, otherwise Nil.
-     */
-    /*
      * Document-method: uninstallable_interface
      *
      * call-seq:
@@ -951,8 +943,6 @@ namespace
         rb_define_method(c_repository, "package_names", RUBY_FUNC_CAST(&repository_package_names), 1);
         rb_define_method(c_repository, "package_ids", RUBY_FUNC_CAST(&repository_package_ids), 1);
 
-        rb_define_method(c_repository, "sets_interface", RUBY_FUNC_CAST((&Interface<
-                        n::sets_interface, RepositorySetsInterface, &Repository::sets_interface>::fetch)), 0);
         rb_define_method(c_repository, "syncable_interface", RUBY_FUNC_CAST((&Interface<
                         n::syncable_interface, RepositorySyncableInterface, &Repository::syncable_interface>::fetch)), 0);
         rb_define_method(c_repository, "mirrors_interface", RUBY_FUNC_CAST((&Interface<
diff --git a/ruby/repository_TEST.rb b/ruby/repository_TEST.rb
index 477c060..122f475 100644
--- a/ruby/repository_TEST.rb
+++ b/ruby/repository_TEST.rb
@@ -165,7 +165,7 @@ module Paludis
 
         def test_responds
             repo = no_config_testrepo.main_repository
-            [:sets_interface, :syncable_interface,
+            [:syncable_interface,
                 :mirrors_interface, :environment_variable_interface,
                 :provides_interface, :virtuals_interface, :e_interface,
                 :qa_interface].each do |sym|
diff --git a/src/clients/adjutrix/find_insecure_packages.cc b/src/clients/adjutrix/find_insecure_packages.cc
index 4952084..452d213 100644
--- a/src/clients/adjutrix/find_insecure_packages.cc
+++ b/src/clients/adjutrix/find_insecure_packages.cc
@@ -1,7 +1,7 @@
 /* vim: set sw=4 sts=4 et foldmethod=syntax : */
 
 /*
- * Copyright (c) 2006, 2007, 2008 Ciaran McCreesh
+ * Copyright (c) 2006, 2007, 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
@@ -164,14 +164,13 @@ void do_find_insecure_packages(const NoConfigEnvironment & env)
         if (env.master_repository() && r->name() == env.master_repository()->name())
             continue;
 
-        if (! (*r).sets_interface())
+        std::tr1::shared_ptr<const SetSpecTree> all_insecure(env.set(SetName("insecurity::"
+                        + stringify(r->name()))));
+        if (! all_insecure)
             continue;
 
         write_repository_header(r->name());
 
-        std::tr1::shared_ptr<const SetSpecTree> all_insecure((*r).sets_interface()->package_set(SetName("insecurity")));
-        if (! all_insecure)
-            continue;
         ListInsecureVisitor v(env);
         all_insecure->root()->accept(v);
         cout << v << endl;
diff --git a/src/clients/cave/cmd_print_sets.cc b/src/clients/cave/cmd_print_sets.cc
index b00f360..21339c0 100644
--- a/src/clients/cave/cmd_print_sets.cc
+++ b/src/clients/cave/cmd_print_sets.cc
@@ -81,25 +81,7 @@ PrintSetsCommand::run(
     if (cmdline.begin_parameters() != cmdline.end_parameters())
         throw args::DoHelp("print-sets takes no parameters");
 
-    std::set<SetName> sets;
-
-    for (IndirectIterator<PackageDatabase::RepositoryConstIterator, const Repository>
-            r(env->package_database()->begin_repositories()), r_end(env->package_database()->end_repositories());
-            r != r_end; ++r)
-    {
-        if ((*r).sets_interface() == 0)
-            continue;
-
-        std::tr1::shared_ptr<const SetNameSet> set_names((*r).sets_interface()->sets_list());
-
-        std::copy(set_names->begin(), set_names->end(), std::inserter(sets, sets.begin()));
-    }
-
-    std::tr1::shared_ptr<const SetNameSet> user_sets(env->set_names());
-    if (user_sets)
-        std::copy(user_sets->begin(), user_sets->end(), std::inserter(sets, sets.begin()));
-
-    std::copy(sets.begin(), sets.end(), std::ostream_iterator<SetName>(cout, "\n"));
+    std::copy(env->set_names()->begin(), env->set_names()->end(), std::ostream_iterator<SetName>(cout, "\n"));
 
     return EXIT_SUCCESS;
 }
diff --git a/src/clients/paludis/list.cc b/src/clients/paludis/list.cc
index 9c3d3a3..bc306e7 100644
--- a/src/clients/paludis/list.cc
+++ b/src/clients/paludis/list.cc
@@ -1,7 +1,7 @@
 /* vim: set sw=4 sts=4 et foldmethod=syntax : */
 
 /*
- * Copyright (c) 2006, 2007, 2008 Ciaran McCreesh
+ * Copyright (c) 2006, 2007, 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
@@ -194,58 +194,19 @@ do_list_sets(const std::tr1::shared_ptr<Environment> & env)
 
     Context context("While performing list-sets action from command line:");
 
-    std::map<SetName, std::list<std::string> > sets;
-
-    for (IndirectIterator<PackageDatabase::RepositoryConstIterator, const Repository>
-            r(env->package_database()->begin_repositories()), r_end(env->package_database()->end_repositories()) ;
-            r != r_end ; ++r)
-    {
-        if ((*r).sets_interface() == 0)
-            continue;
-
-        if (CommandLine::get_instance()->a_repository.specified())
-            if (CommandLine::get_instance()->a_repository.end_args() == std::find(
-                        CommandLine::get_instance()->a_repository.begin_args(),
-                        CommandLine::get_instance()->a_repository.end_args(),
-                        stringify(r->name())))
-                continue;
-        if (CommandLine::get_instance()->a_repository_format.specified())
-            if (CommandLine::get_instance()->a_repository_format.end_args() == std::find(
-                        CommandLine::get_instance()->a_repository_format.begin_args(),
-                        CommandLine::get_instance()->a_repository_format.end_args(),
-                        r->format_key() ? r->format_key()->value() : "?"))
-                continue;
-
-        std::tr1::shared_ptr<const SetNameSet> set_names((*r).sets_interface()->sets_list());
-        for (SetNameSet::ConstIterator s(set_names->begin()), s_end(set_names->end()) ;
-                s != s_end ; ++s)
-            sets[*s].push_back(stringify(r->name()));
-    }
-
-    if (! CommandLine::get_instance()->a_repository.specified())
-    {
-        std::tr1::shared_ptr<const SetNameSet> set_names(env->set_names());
-        for (SetNameSet::ConstIterator s(set_names->begin()), s_end(set_names->end()) ;
-                s != s_end ; ++s)
-            sets[*s].push_back("environment");
-    }
-
-    for (std::map<SetName, std::list<std::string> >::const_iterator
-            s(sets.begin()), s_end(sets.end()) ; s != s_end ; ++s)
+    for (SetNameSet::ConstIterator s(env->set_names()->begin()), s_end(env->set_names()->end()) ;
+            s != s_end ; ++s)
     {
         if (CommandLine::get_instance()->a_set.specified())
             if (CommandLine::get_instance()->a_set.end_args() == std::find(
                         CommandLine::get_instance()->a_set.begin_args(),
                         CommandLine::get_instance()->a_set.end_args(),
-                        stringify(s->first)))
+                        stringify(*s)))
                 continue;
 
         ret_code = 0;
 
-        std::cout << "* " << colour(cl_package_name, s->first) << std::endl;
-        std::cout << "    " << std::setw(22) << std::left << "found in:" <<
-            std::setw(0) << " " << join(s->second.begin(), s->second.end(), ", ") << std::endl;
-        std::cout << std::endl;
+        std::cout << "* " << colour(cl_package_name, *s) << std::endl;
     }
 
     return ret_code;