key requirements to constraints

28 files changed, 947 insertions, 621 deletions

diff --git a/paludis/dep_spec.cc b/paludis/dep_spec.cc
index 432f0fb..ec1d075 100644
--- a/paludis/dep_spec.cc
+++ b/paludis/dep_spec.cc
@@ -620,6 +620,12 @@ PackageDepSpec::additional_requirements_ptr() const
     return _imp->data->additional_requirements_ptr();
 }
 
+const std::shared_ptr<const KeyConstraintSequence>
+PackageDepSpec::all_key_constraints() const
+{
+    return _imp->data->all_key_constraints();
+}
+
 std::string
 PackageDepSpec::_as_string() const
 {
diff --git a/paludis/dep_spec.hh b/paludis/dep_spec.hh
index 9c6bb9a..9682bdb 100644
--- a/paludis/dep_spec.hh
+++ b/paludis/dep_spec.hh
@@ -403,6 +403,14 @@ namespace paludis
             const std::shared_ptr<const InstallableToPathConstraint> installable_to_path_constraint() const;
 
             /**
+             * Fetch all our KeyConstraints, if we have any, or
+             * a null pointer otherwise.
+             *
+             * \since 0.61
+             */
+            const std::shared_ptr<const KeyConstraintSequence> all_key_constraints() const;
+
+            /**
              * Fetch any additional requirements (may be a zero pointer).
              */
             std::shared_ptr<const AdditionalPackageDepSpecRequirements> additional_requirements_ptr() const;
diff --git a/paludis/dep_spec_data.hh b/paludis/dep_spec_data.hh
index 6f4dc64..864a5a8 100644
--- a/paludis/dep_spec_data.hh
+++ b/paludis/dep_spec_data.hh
@@ -203,6 +203,14 @@ namespace paludis
             virtual const std::shared_ptr<const InstallableToPathConstraint> installable_to_path_constraint() const = 0;
 
             /**
+             * Fetch all our KeyConstraints, if we have any, or
+             * a null pointer otherwise.
+             *
+             * \since 0.61
+             */
+            virtual const std::shared_ptr<const KeyConstraintSequence> all_key_constraints() const = 0;
+
+            /**
              * Fetch the additional requirements (may be a zero pointer).
              */
             virtual std::shared_ptr<const AdditionalPackageDepSpecRequirements> additional_requirements_ptr() const = 0;
diff --git a/paludis/elike_package_dep_spec.cc b/paludis/elike_package_dep_spec.cc
index 1c70cdb..7ff1474 100644
--- a/paludis/elike_package_dep_spec.cc
+++ b/paludis/elike_package_dep_spec.cc
@@ -196,8 +196,9 @@ paludis::elike_remove_trailing_square_bracket_if_exists(std::string & s, Partial
                         Log::get_instance()->message("e.package_dep_spec.key_not_allowed", ll_warning, lc_context)
                             << "Key requirements not safe for use here";
                 }
-                std::shared_ptr<const AdditionalPackageDepSpecRequirement> req(std::make_shared<UserKeyRequirement>(flag.substr(1)));
-                result.additional_requirement(req);
+
+                auto k(parse_user_key_constraint(flag.substr(1)));
+                result.key_constraint(std::get<0>(k), std::get<1>(k), std::get<2>(k));
             }
             break;
 
diff --git a/paludis/files.m4 b/paludis/files.m4
index 7b69c2d..4d4f7d1 100644
--- a/paludis/files.m4
+++ b/paludis/files.m4
@@ -75,7 +75,7 @@ add(`output_manager',                              `hh', `fwd', `cc', `se')
 add(`output_manager_factory',                      `hh', `fwd', `cc')
 add(`output_manager_from_environment',             `hh', `fwd', `cc')
 add(`package_dep_spec_collection',                 `hh', `cc', `fwd')
-add(`package_dep_spec_constraint',                 `hh', `cc', `fwd')
+add(`package_dep_spec_constraint',                 `hh', `cc', `fwd', `se')
 add(`package_dep_spec_properties',                 `hh', `cc', `fwd')
 add(`package_id',                                  `hh', `cc', `fwd', `se')
 add(`paludis',                                     `hh')
diff --git a/paludis/generator.cc b/paludis/generator.cc
index bc5dcda..4f40639 100644
--- a/paludis/generator.cc
+++ b/paludis/generator.cc
@@ -314,6 +314,7 @@ namespace
                             n::has_installable_to_path() = indeterminate,
                             n::has_installable_to_repository() = indeterminate,
                             n::has_installed_at_path() = false,
+                            n::has_key_requirements() = indeterminate,
                             n::has_package() = indeterminate,
                             n::has_package_name_part() = indeterminate,
                             n::has_tag() = indeterminate,
diff --git a/paludis/match_package.cc b/paludis/match_package.cc
index 424628f..9e51e81 100644
--- a/paludis/match_package.cc
+++ b/paludis/match_package.cc
@@ -28,6 +28,7 @@
 #include <paludis/repository.hh>
 #include <paludis/additional_package_dep_spec_requirement.hh>
 #include <paludis/package_dep_spec_constraint.hh>
+#include <paludis/contents.hh>
 
 #include <paludis/util/set.hh>
 #include <paludis/util/options.hh>
@@ -36,6 +37,9 @@
 #include <paludis/util/indirect_iterator-impl.hh>
 #include <paludis/util/make_null_shared_ptr.hh>
 #include <paludis/util/stringify.hh>
+#include <paludis/util/accept_visitor.hh>
+#include <paludis/util/destringify.hh>
+#include <paludis/util/join.hh>
 
 #include <functional>
 #include <algorithm>
@@ -46,6 +50,577 @@ using namespace paludis;
 
 #include <paludis/match_package-se.cc>
 
+namespace
+{
+    std::string stringify_contents_entry(const ContentsEntry & e)
+    {
+        return stringify(e.location_key()->value());
+    }
+
+    struct StringifyEqual
+    {
+        const std::string pattern;
+
+        StringifyEqual(const std::string & p) :
+            pattern(p)
+        {
+        }
+
+        template <typename T_>
+        bool operator() (const T_ & t) const
+        {
+            return stringify(t) == pattern;
+        }
+
+        bool operator() (const ContentsEntry & e) const
+        {
+            return stringify_contents_entry(e) == pattern;
+        }
+    };
+
+    struct SpecTreeSearcher
+    {
+        const Environment * const env;
+        const std::shared_ptr<const PackageID> id;
+        const std::string pattern;
+
+        SpecTreeSearcher(const Environment * const e, const std::shared_ptr<const PackageID> & i, const std::string & p) :
+            env(e),
+            id(i),
+            pattern(p)
+        {
+        }
+
+        bool visit(const GenericSpecTree::NodeType<AllDepSpec>::Type & n) const
+        {
+            return indirect_iterator(n.end()) != std::find_if(indirect_iterator(n.begin()), indirect_iterator(n.end()),
+                    accept_visitor_returning<bool>(*this));
+        }
+
+        bool visit(const GenericSpecTree::NodeType<AnyDepSpec>::Type & n) const
+        {
+            return indirect_iterator(n.end()) != std::find_if(indirect_iterator(n.begin()), indirect_iterator(n.end()),
+                    accept_visitor_returning<bool>(*this));
+        }
+
+        bool visit(const GenericSpecTree::NodeType<ExactlyOneDepSpec>::Type & n) const
+        {
+            return indirect_iterator(n.end()) != std::find_if(indirect_iterator(n.begin()), indirect_iterator(n.end()),
+                    accept_visitor_returning<bool>(*this));
+        }
+
+        bool visit(const GenericSpecTree::NodeType<ConditionalDepSpec>::Type & n) const
+        {
+            if (n.spec()->condition_met(env, id))
+                return indirect_iterator(n.end()) != std::find_if(indirect_iterator(n.begin()), indirect_iterator(n.end()),
+                        accept_visitor_returning<bool>(*this));
+            else
+                return false;
+        }
+
+        bool visit(const GenericSpecTree::NodeType<NamedSetDepSpec>::Type & n) const
+        {
+            return stringify(*n.spec()) == pattern;
+        }
+
+        bool visit(const GenericSpecTree::NodeType<PlainTextDepSpec>::Type & n) const
+        {
+            return stringify(*n.spec()) == pattern;
+        }
+
+        bool visit(const GenericSpecTree::NodeType<PackageDepSpec>::Type & n) const
+        {
+            return stringify(*n.spec()) == pattern;
+        }
+
+        bool visit(const GenericSpecTree::NodeType<BlockDepSpec>::Type & n) const
+        {
+            return stringify(*n.spec()) == pattern;
+        }
+
+        bool visit(const GenericSpecTree::NodeType<LicenseDepSpec>::Type & n) const
+        {
+            return stringify(*n.spec()) == pattern;
+        }
+
+        bool visit(const GenericSpecTree::NodeType<SimpleURIDepSpec>::Type & n) const
+        {
+            return stringify(*n.spec()) == pattern;
+        }
+
+        bool visit(const GenericSpecTree::NodeType<FetchableURIDepSpec>::Type & n) const
+        {
+            return stringify(*n.spec()) == pattern;
+        }
+
+        bool visit(const GenericSpecTree::NodeType<DependenciesLabelsDepSpec>::Type & n) const
+        {
+            return indirect_iterator(n.spec()->end()) != std::find_if(indirect_iterator(n.spec()->begin()),
+                    indirect_iterator(n.spec()->end()), StringifyEqual(pattern));
+        }
+
+        bool visit(const GenericSpecTree::NodeType<URILabelsDepSpec>::Type & n) const
+        {
+            return indirect_iterator(n.spec()->end()) != std::find_if(indirect_iterator(n.spec()->begin()),
+                    indirect_iterator(n.spec()->end()), StringifyEqual(pattern));
+        }
+
+        bool visit(const GenericSpecTree::NodeType<PlainTextLabelDepSpec>::Type & n) const
+        {
+            return stringify(*n.spec()) == pattern;
+        }
+    };
+
+    struct KeyComparator
+    {
+        const Environment * const env;
+        const std::shared_ptr<const PackageID> id;
+        const std::string pattern;
+        const KeyConstraintOperation op;
+
+        KeyComparator(const Environment * const e, const std::shared_ptr<const PackageID> & i,
+                const std::string & p, const KeyConstraintOperation o) :
+            env(e),
+            id(i),
+            pattern(p),
+            op(o)
+        {
+        }
+
+        bool visit(const MetadataSectionKey &) const
+        {
+            return false;
+        }
+
+        bool visit(const MetadataTimeKey & k) const
+        {
+            switch (op)
+            {
+                case kco_equals:
+                    return pattern == stringify(k.value().seconds());
+                case kco_less_than:
+                    return k.value().seconds() < destringify<time_t>(pattern);
+                case kco_greater_than:
+                    return k.value().seconds() > destringify<time_t>(pattern);
+                case kco_question:
+                case last_kco:
+                    break;
+            }
+
+            return false;
+        }
+
+        bool visit(const MetadataValueKey<std::string> & k) const
+        {
+            return pattern == stringify(k.value());
+        }
+
+        bool visit(const MetadataValueKey<SlotName> & k) const
+        {
+            return pattern == stringify(k.value());
+        }
+
+        bool visit(const MetadataValueKey<FSPath> & k) const
+        {
+            return pattern == stringify(k.value());
+        }
+
+        bool visit(const MetadataValueKey<bool> & k) const
+        {
+            return pattern == stringify(k.value());
+        }
+
+        bool visit(const MetadataValueKey<long> & k) const
+        {
+            switch (op)
+            {
+                case kco_equals:
+                    return pattern == stringify(k.value());
+                case kco_less_than:
+                    return k.value() < destringify<long>(pattern);
+                case kco_greater_than:
+                    return k.value() > destringify<long>(pattern);
+                case kco_question:
+                case last_kco:
+                    break;
+            }
+
+            return false;
+        }
+
+        bool visit(const MetadataValueKey<std::shared_ptr<const Choices> > &) const
+        {
+            return false;
+        }
+
+        bool visit(const MetadataValueKey<std::shared_ptr<const Contents> > & s) const
+        {
+            switch (op)
+            {
+                case kco_equals:
+                    return pattern == join(indirect_iterator(s.value()->begin()), indirect_iterator(s.value()->end()), " ",
+                            stringify_contents_entry);
+                case kco_less_than:
+                    return indirect_iterator(s.value()->end()) != std::find_if(
+                            indirect_iterator(s.value()->begin()),
+                            indirect_iterator(s.value()->end()),
+                            StringifyEqual(pattern));
+
+                case kco_greater_than:
+                case kco_question:
+                case last_kco:
+                    break;
+            }
+
+            return false;
+        }
+
+        bool visit(const MetadataValueKey<std::shared_ptr<const PackageID> > & k) const
+        {
+            return pattern == stringify(*k.value());
+        }
+
+        bool visit(const MetadataSpecTreeKey<DependencySpecTree> & s) const
+        {
+            switch (op)
+            {
+                case kco_equals:
+                    return false;
+                case kco_less_than:
+                    return s.value()->top()->accept_returning<bool>(SpecTreeSearcher(env, id, pattern));
+
+                case kco_greater_than:
+                case kco_question:
+                case last_kco:
+                    break;
+            }
+
+            return false;
+        }
+
+        bool visit(const MetadataSpecTreeKey<SetSpecTree> & s) const
+        {
+            switch (op)
+            {
+                case kco_equals:
+                    return false;
+                case kco_less_than:
+                    return s.value()->top()->accept_returning<bool>(SpecTreeSearcher(env, id, pattern));
+
+                case kco_greater_than:
+                case kco_question:
+                case last_kco:
+                    break;
+            }
+
+            return false;
+        }
+
+        bool visit(const MetadataSpecTreeKey<PlainTextSpecTree> & s) const
+        {
+            switch (op)
+            {
+                case kco_equals:
+                    return false;
+                case kco_less_than:
+                    return s.value()->top()->accept_returning<bool>(SpecTreeSearcher(env, id, pattern));
+
+                case kco_greater_than:
+                case kco_question:
+                case last_kco:
+                    break;
+            }
+
+            return false;
+        }
+
+        bool visit(const MetadataSpecTreeKey<RequiredUseSpecTree> & s) const
+        {
+            switch (op)
+            {
+                case kco_equals:
+                    return false;
+                case kco_less_than:
+                    return s.value()->top()->accept_returning<bool>(SpecTreeSearcher(env, id, pattern));
+
+                case kco_greater_than:
+                case kco_question:
+                case last_kco:
+                    break;
+            }
+
+            return false;
+        }
+
+        bool visit(const MetadataSpecTreeKey<ProvideSpecTree> & s) const
+        {
+            switch (op)
+            {
+                case kco_equals:
+                    return false;
+                case kco_less_than:
+                    return s.value()->top()->accept_returning<bool>(SpecTreeSearcher(env, id, pattern));
+
+                case kco_greater_than:
+                case kco_question:
+                case last_kco:
+                    break;
+            }
+
+            return false;
+        }
+
+        bool visit(const MetadataSpecTreeKey<SimpleURISpecTree> & s) const
+        {
+            switch (op)
+            {
+                case kco_equals:
+                    return false;
+                case kco_less_than:
+                    return s.value()->top()->accept_returning<bool>(SpecTreeSearcher(env, id, pattern));
+
+                case kco_greater_than:
+                case kco_question:
+                case last_kco:
+                    break;
+            }
+
+            return false;
+        }
+
+        bool visit(const MetadataSpecTreeKey<FetchableURISpecTree> & s) const
+        {
+            switch (op)
+            {
+                case kco_equals:
+                    return false;
+                case kco_less_than:
+                    return s.value()->top()->accept_returning<bool>(SpecTreeSearcher(env, id, pattern));
+
+                case kco_greater_than:
+                case kco_question:
+                case last_kco:
+                    break;
+            }
+
+            return false;
+        }
+
+        bool visit(const MetadataSpecTreeKey<LicenseSpecTree> & s) const
+        {
+            switch (op)
+            {
+                case kco_equals:
+                    return false;
+                case kco_less_than:
+                    return s.value()->top()->accept_returning<bool>(SpecTreeSearcher(env, id, pattern));
+
+                case kco_greater_than:
+                case kco_question:
+                case last_kco:
+                    break;
+            }
+
+            return false;
+        }
+
+        bool visit(const MetadataCollectionKey<FSPathSequence> & s) const
+        {
+            switch (op)
+            {
+                case kco_equals:
+                    return pattern == join(s.value()->begin(), s.value()->end(), " ");
+                case kco_less_than:
+                    return s.value()->end() != std::find_if(s.value()->begin(), s.value()->end(),
+                            StringifyEqual(pattern));
+
+                case kco_greater_than:
+                case kco_question:
+                case last_kco:
+                    break;
+            }
+
+            return false;
+        }
+
+        bool visit(const MetadataCollectionKey<PackageIDSequence> & s) const
+        {
+            switch (op)
+            {
+                case kco_equals:
+                    return pattern == join(indirect_iterator(s.value()->begin()), indirect_iterator(s.value()->end()), " ");
+                case kco_less_than:
+                    return indirect_iterator(s.value()->end()) != std::find_if(
+                            indirect_iterator(s.value()->begin()),
+                            indirect_iterator(s.value()->end()),
+                            StringifyEqual(pattern));
+
+                case kco_greater_than:
+                case kco_question:
+                case last_kco:
+                    break;
+            }
+
+            return false;
+        }
+
+        bool visit(const MetadataCollectionKey<Sequence<std::string> > & s) const
+        {
+            switch (op)
+            {
+                case kco_equals:
+                    return pattern == join(s.value()->begin(), s.value()->end(), " ");
+                case kco_less_than:
+                    return s.value()->end() != std::find_if(s.value()->begin(), s.value()->end(),
+                            StringifyEqual(pattern));
+
+                case kco_greater_than:
+                case kco_question:
+                case last_kco:
+                    break;
+            }
+
+            return false;
+        }
+
+        bool visit(const MetadataCollectionKey<Set<std::string> > & s) const
+        {
+            switch (op)
+            {
+                case kco_equals:
+                    return pattern == join(s.value()->begin(), s.value()->end(), " ");
+                case kco_less_than:
+                    return s.value()->end() != std::find_if(s.value()->begin(), s.value()->end(),
+                            StringifyEqual(pattern));
+
+                case kco_greater_than:
+                case kco_question:
+                case last_kco:
+                    break;
+            }
+
+            return false;
+        }
+
+        bool visit(const MetadataCollectionKey<Map<std::string, std::string> > &) const
+        {
+            return false;
+        }
+
+        bool visit(const MetadataCollectionKey<KeywordNameSet> & s) const
+        {
+            switch (op)
+            {
+                case kco_equals:
+                    return pattern == join(s.value()->begin(), s.value()->end(), " ");
+                case kco_less_than:
+                    return s.value()->end() != std::find_if(s.value()->begin(), s.value()->end(),
+                            StringifyEqual(pattern));
+
+                case kco_greater_than:
+                case kco_question:
+                case last_kco:
+                    break;
+            }
+
+            return false;
+        }
+    };
+
+    bool
+    match_key_constraint(
+            const Environment * const env,
+            const std::shared_ptr<const PackageID> & id,
+            const std::shared_ptr<const PackageID> &,
+            const std::shared_ptr<const KeyConstraint> & constraint)
+    {
+        const MetadataKey * key(0);
+
+        auto repo(env->fetch_repository(id->repository_name()));
+        if (0 == constraint->key().compare(0, 3, "::$"))
+        {
+            if (constraint->key() == "::$format")
+                key = repo->format_key().get();
+            else if (constraint->key() == "::$location")
+                key = repo->location_key().get();
+            else if (constraint->key() == "::$installed_root")
+                key = repo->installed_root_key().get();
+            else if (constraint->key() == "::$accept_keywords")
+                key = repo->accept_keywords_key().get();
+            else if (constraint->key() == "::$sync_host")
+                key = repo->sync_host_key().get();
+        }
+        else if (0 == constraint->key().compare(0, 1, "$"))
+        {
+            if (constraint->key() == "$behaviours")
+                key = id->behaviours_key().get();
+            else if (constraint->key() == "$build_dependencies")
+                key = id->build_dependencies_key().get();
+            else if (constraint->key() == "$choices")
+                key = id->choices_key().get();
+            else if (constraint->key() == "$contained_in")
+                key = id->contained_in_key().get();
+            else if (constraint->key() == "$contains")
+                key = id->contains_key().get();
+            else if (constraint->key() == "$contents")
+                key = id->contents_key().get();
+            else if (constraint->key() == "$dependencies")
+                key = id->dependencies_key().get();
+            else if (constraint->key() == "$fetches")
+                key = id->fetches_key().get();
+            else if (constraint->key() == "$from_repositories")
+                key = id->from_repositories_key().get();
+            else if (constraint->key() == "$fs_location")
+                key = id->fs_location_key().get();
+            else if (constraint->key() == "$homepage")
+                key = id->homepage_key().get();
+            else if (constraint->key() == "$installed_time")
+                key = id->installed_time_key().get();
+            else if (constraint->key() == "$keywords")
+                key = id->keywords_key().get();
+            else if (constraint->key() == "$long_description")
+                key = id->long_description_key().get();
+            else if (constraint->key() == "$post_dependencies")
+                key = id->post_dependencies_key().get();
+            else if (constraint->key() == "$provide")
+                key = id->provide_key().get();
+            else if (constraint->key() == "$run_dependencies")
+                key = id->run_dependencies_key().get();
+            else if (constraint->key() == "$short_description")
+                key = id->short_description_key().get();
+            else if (constraint->key() == "$slot")
+                key = id->slot_key().get();
+            else if (constraint->key() == "$suggested_dependencies")
+                key = id->suggested_dependencies_key().get();
+            else if (constraint->key() == "$virtual_for")
+                key = id->virtual_for_key().get();
+        }
+        else if (0 == constraint->key().compare(0, 2, "::"))
+        {
+            Repository::MetadataConstIterator m(repo->find_metadata(constraint->key().substr(2)));
+            if (m != repo->end_metadata())
+                key = m->get();
+        }
+        else
+        {
+            PackageID::MetadataConstIterator m(id->find_metadata(constraint->key()));
+            if (m != id->end_metadata())
+                key = m->get();
+        }
+
+        if (! key)
+            return false;
+
+        if (constraint->operation() == kco_question)
+            return true;
+        else
+        {
+            KeyComparator c(env, id, constraint->pattern(), constraint->operation());
+            return key->accept_returning<bool>(c);
+        }
+    }
+}
+
 bool
 paludis::match_package_with_maybe_changes(
         const Environment & env,
@@ -185,6 +760,16 @@ paludis::match_package_with_maybe_changes(
         }
     }
 
+    if (spec.all_key_constraints())
+    {
+        for (auto c(spec.all_key_constraints()->begin()), c_end(spec.all_key_constraints()->end()) ;
+                c != c_end ; ++c)
+        {
+            if (! match_key_constraint(&env, id, from_id, *c))
+                return false;
+        }
+    }
+
     return true;
 }
 
diff --git a/paludis/package_dep_spec_constraint-fwd.hh b/paludis/package_dep_spec_constraint-fwd.hh
index b8c43a6..6eb748d 100644
--- a/paludis/package_dep_spec_constraint-fwd.hh
+++ b/paludis/package_dep_spec_constraint-fwd.hh
@@ -21,6 +21,10 @@
 #define PALUDIS_GUARD_PALUDIS_PACKAGE_DEP_SPEC_CONSTRAINT_FWD_HH 1
 
 #include <paludis/util/pool-fwd.hh>
+#include <paludis/util/attributes.hh>
+#include <paludis/util/sequence-fwd.hh>
+#include <iosfwd>
+#include <memory>
 
 namespace paludis
 {
@@ -55,6 +59,14 @@ namespace paludis
 
     class AnySlotConstraint;
     typedef Pool<AnySlotConstraint> AnySlotConstraintPool;
+
+    class KeyConstraint;
+    typedef Pool<KeyConstraint> KeyConstraintPool;
+
+    typedef Sequence<std::shared_ptr<const KeyConstraint> > KeyConstraintSequence;
+
+#include <paludis/package_dep_spec_constraint-se.hh>
+
 }
 
 #endif
diff --git a/paludis/package_dep_spec_constraint.cc b/paludis/package_dep_spec_constraint.cc
index 22b20e0..85d3979 100644
--- a/paludis/package_dep_spec_constraint.cc
+++ b/paludis/package_dep_spec_constraint.cc
@@ -21,9 +21,18 @@
 #include <paludis/util/pool-impl.hh>
 #include <paludis/util/pimp-impl.hh>
 #include <paludis/util/singleton-impl.hh>
+#include <paludis/util/stringify.hh>
+#include <paludis/util/exception.hh>
+#include <paludis/util/sequence-impl.hh>
+#include <paludis/util/wrapped_forward_iterator-impl.hh>
+
+#include <istream>
+#include <ostream>
 
 using namespace paludis;
 
+#include <paludis/package_dep_spec_constraint-se.cc>
+
 PackageDepSpecConstraint::~PackageDepSpecConstraint() = default;
 
 NameConstraint::NameConstraint(const QualifiedPackageName & n) :
@@ -225,3 +234,36 @@ template class Pool<AnySlotConstraint>;
 template class Singleton<Pool<AnySlotConstraint> >;
 template const std::shared_ptr<const AnySlotConstraint> Pool<AnySlotConstraint>::create(const bool &) const;
 
+KeyConstraint::KeyConstraint(const std::string & k, const KeyConstraintOperation o, const std::string & p) :
+    _key(k),
+    _operation(o),
+    _pattern(p)
+{
+}
+
+KeyConstraint::~KeyConstraint() = default;
+
+const std::string
+KeyConstraint::key() const
+{
+    return _key;
+}
+
+KeyConstraintOperation
+KeyConstraint::operation() const
+{
+    return _operation;
+}
+
+const std::string
+KeyConstraint::pattern() const
+{
+    return _pattern;
+}
+
+template class Pool<KeyConstraint>;
+template class Singleton<Pool<KeyConstraint> >;
+template const std::shared_ptr<const KeyConstraint> Pool<KeyConstraint>::create(const std::string &, const KeyConstraintOperation &, const std::string &) const;
+template class Sequence<std::shared_ptr<const KeyConstraint> >;
+template class WrappedForwardIterator<Sequence<std::shared_ptr<const KeyConstraint> >::ConstIteratorTag, const std::shared_ptr<const KeyConstraint> >;
+
diff --git a/paludis/package_dep_spec_constraint.hh b/paludis/package_dep_spec_constraint.hh
index f23ba66..1736b40 100644
--- a/paludis/package_dep_spec_constraint.hh
+++ b/paludis/package_dep_spec_constraint.hh
@@ -42,7 +42,8 @@ namespace paludis
             InstallableToPathConstraint,
             InstallableToRepositoryConstraint,
             AnySlotConstraint,
-            ExactSlotConstraint
+            ExactSlotConstraint,
+            KeyConstraint
         >::Type>
     {
         public:
@@ -245,6 +246,29 @@ namespace paludis
             bool locking() const PALUDIS_ATTRIBUTE((warn_unused_result));
     };
 
+    class PALUDIS_VISIBLE KeyConstraint :
+        public PackageDepSpecConstraint,
+        public ImplementAcceptMethods<PackageDepSpecConstraint, KeyConstraint>
+    {
+        friend class Pool<KeyConstraint>;
+
+        private:
+            std::string _key;
+            KeyConstraintOperation _operation;
+            std::string _pattern;
+
+            KeyConstraint(const std::string &, const KeyConstraintOperation, const std::string &);
+
+            KeyConstraint(const KeyConstraint &) = delete;
+
+        public:
+            ~KeyConstraint();
+
+            const std::string key() const PALUDIS_ATTRIBUTE((warn_unused_result));
+            KeyConstraintOperation operation() const PALUDIS_ATTRIBUTE((warn_unused_result));
+            const std::string pattern() const PALUDIS_ATTRIBUTE((warn_unused_result));
+    };
+
     extern template class Pool<NameConstraint>;
     extern template class Pool<PackageNamePartConstraint>;
     extern template class Pool<CategoryNamePartConstraint>;
@@ -255,6 +279,7 @@ namespace paludis
     extern template class Pool<InstallableToRepositoryConstraint>;
     extern template class Pool<ExactSlotConstraint>;
     extern template class Pool<AnySlotConstraint>;
+    extern template class Pool<KeyConstraint>;
 }
 
 #endif
diff --git a/paludis/package_dep_spec_constraint.se b/paludis/package_dep_spec_constraint.se
new file mode 100644
index 0000000..75e6e2c
--- /dev/null
+++ b/paludis/package_dep_spec_constraint.se
@@ -0,0 +1,13 @@
+#!/usr/bin/env bash
+# vim: set sw=4 sts=4 et ft=sh :
+
+make_enum_KeyConstraintOperation()
+{
+    prefix kco
+
+    key kco_equals             "An = constraint"
+    key kco_less_than          "A less than constraint"
+    key kco_greater_than       "A greater than constraint"
+    key kco_question           "A question constraint"
+}
+
diff --git a/paludis/package_dep_spec_properties.cc b/paludis/package_dep_spec_properties.cc
index 000b20c..f4f4af1 100644
--- a/paludis/package_dep_spec_properties.cc
+++ b/paludis/package_dep_spec_properties.cc
@@ -44,6 +44,7 @@ paludis::package_dep_spec_has_properties(const PackageDepSpec & spec, const Pack
     result = result && check(bool(spec.additional_requirements_ptr()) && ! spec.additional_requirements_ptr()->empty(), properties.has_additional_requirements());
     result = result && check(bool(spec.category_name_part_constraint()), properties.has_category_name_part());
     result = result && check(bool(spec.from_repository_constraint()), properties.has_from_repository());
+    result = result && check(bool(spec.all_key_constraints()) && ! spec.all_key_constraints()->empty(), properties.has_key_requirements());
     result = result && check(bool(spec.in_repository_constraint()), properties.has_in_repository());
     result = result && check(bool(spec.installable_to_path_constraint()), properties.has_installable_to_path());
     result = result && check(bool(spec.installable_to_repository_constraint()), properties.has_installable_to_repository());
diff --git a/paludis/package_dep_spec_properties.hh b/paludis/package_dep_spec_properties.hh
index e9eff06..4e877b4 100644
--- a/paludis/package_dep_spec_properties.hh
+++ b/paludis/package_dep_spec_properties.hh
@@ -37,6 +37,7 @@ namespace paludis
         typedef Name<struct name_has_installable_to_path> has_installable_to_path;
         typedef Name<struct name_has_installable_to_repository> has_installable_to_repository;
         typedef Name<struct name_has_installed_at_path> has_installed_at_path;
+        typedef Name<struct name_has_key_requirements> has_key_requirements;
         typedef Name<struct name_has_package> has_package;
         typedef Name<struct name_has_package_name_part> has_package_name_part;
         typedef Name<struct name_has_tag> has_tag;
@@ -60,6 +61,7 @@ namespace paludis
         NamedValue<n::has_installable_to_path, Tribool> has_installable_to_path;
         NamedValue<n::has_installable_to_repository, Tribool> has_installable_to_repository;
         NamedValue<n::has_installed_at_path, Tribool> has_installed_at_path;
+        NamedValue<n::has_key_requirements, Tribool> has_key_requirements;
         NamedValue<n::has_package, Tribool> has_package;
         NamedValue<n::has_package_name_part, Tribool> has_package_name_part;
         NamedValue<n::has_tag, Tribool> has_tag;
diff --git a/paludis/paludislike_options_conf.cc b/paludis/paludislike_options_conf.cc
index 8af91db..004a6e1 100644
--- a/paludis/paludislike_options_conf.cc
+++ b/paludis/paludislike_options_conf.cc
@@ -350,6 +350,7 @@ namespace
                     n::has_installable_to_path() = false,
                     n::has_installable_to_repository() = false,
                     n::has_installed_at_path() = false,
+                    n::has_key_requirements() = false,
                     n::has_package() = false,
                     n::has_package_name_part() = false,
                     n::has_tag() = false,
diff --git a/paludis/partially_made_package_dep_spec.cc b/paludis/partially_made_package_dep_spec.cc
index b070d0c..37d8c0f 100644
--- a/paludis/partially_made_package_dep_spec.cc
+++ b/paludis/partially_made_package_dep_spec.cc
@@ -60,6 +60,7 @@ namespace
         std::shared_ptr<const InstallableToRepositoryConstraint> installable_to_repository;
         std::shared_ptr<const InstalledAtPathConstraint> installed_at_path;
         std::shared_ptr<const InstallableToPathConstraint> installable_to_path;
+        std::shared_ptr<KeyConstraintSequence> all_keys;
         std::shared_ptr<AdditionalPackageDepSpecRequirements> additional_requirements;
         PartiallyMadePackageDepSpecOptions options_for_partially_made_package_dep_spec_v;
 
@@ -84,6 +85,7 @@ namespace
             installable_to_repository(other.installable_to_repository_constraint()),
             installed_at_path(other.installed_at_path_constraint()),
             installable_to_path(other.installable_to_path_constraint()),
+            all_keys(other.all_key_constraints() ? new KeyConstraintSequence : 0),
             additional_requirements(other.additional_requirements_ptr() ? new AdditionalPackageDepSpecRequirements : 0),
             options_for_partially_made_package_dep_spec_v(other.options_for_partially_made_package_dep_spec())
         {
@@ -91,6 +93,10 @@ namespace
                 std::copy(other.version_requirements_ptr()->begin(), other.version_requirements_ptr()->end(),
                         version_requirements->back_inserter());
 
+            if (all_keys)
+                std::copy(other.all_key_constraints()->begin(), other.all_key_constraints()->end(),
+                        all_keys->back_inserter());
+
             if (additional_requirements)
                 std::copy(other.additional_requirements_ptr()->begin(), other.additional_requirements_ptr()->end(),
                         additional_requirements->back_inserter());
@@ -110,6 +116,7 @@ namespace
             installable_to_repository(other.installable_to_repository),
             installed_at_path(other.installed_at_path),
             installable_to_path(other.installable_to_path),
+            all_keys(other.all_keys),
             additional_requirements(other.additional_requirements),
             options_for_partially_made_package_dep_spec_v(other.options_for_partially_made_package_dep_spec_v)
         {
@@ -293,6 +300,25 @@ namespace
                         u_end(additional_requirements_ptr()->end()) ; u != u_end ; ++u)
                     s << (*u)->as_raw_string();
 
+            if (all_key_constraints())
+                for (auto u(all_key_constraints()->begin()), u_end(all_key_constraints()->end()) ; u != u_end ; ++u)
+                {
+                    s << "[" << (*u)->key();
+
+                    switch ((*u)->operation())
+                    {
+                        case kco_equals:         s << "=" << (*u)->pattern(); break;
+                        case kco_less_than:      s << "<" << (*u)->pattern(); break;
+                        case kco_greater_than:   s << ">" << (*u)->pattern(); break;
+                        case kco_question:       s << "?";                    break;
+
+                        case last_kco:
+                            throw InternalError(PALUDIS_HERE, "Bad KeyConstraintOperation");
+                    }
+
+                    s << "]";
+                }
+
             return s.str();
         }
 
@@ -361,6 +387,11 @@ namespace
             return additional_requirements;
         }
 
+        virtual const std::shared_ptr<const KeyConstraintSequence> all_key_constraints() const
+        {
+            return all_keys;
+        }
+
         virtual const PartiallyMadePackageDepSpecOptions options_for_partially_made_package_dep_spec() const
         {
             return options_for_partially_made_package_dep_spec_v;
@@ -584,6 +615,15 @@ PartiallyMadePackageDepSpec::additional_requirement(const std::shared_ptr<const
 }
 
 PartiallyMadePackageDepSpec &
+PartiallyMadePackageDepSpec::key_constraint(const std::string & k, const KeyConstraintOperation o, const std::string & p)
+{
+    if (! _imp->data->all_keys)
+        _imp->data->all_keys = std::make_shared<KeyConstraintSequence>();
+    _imp->data->all_keys->push_back(KeyConstraintPool::get_instance()->create(k, o, p));
+    return *this;
+}
+
+PartiallyMadePackageDepSpec &
 PartiallyMadePackageDepSpec::clear_additional_requirements()
 {
     _imp->data->additional_requirements.reset();
diff --git a/paludis/partially_made_package_dep_spec.hh b/paludis/partially_made_package_dep_spec.hh
index 78f7d16..14d2c5a 100644
--- a/paludis/partially_made_package_dep_spec.hh
+++ b/paludis/partially_made_package_dep_spec.hh
@@ -206,6 +206,12 @@ namespace paludis
                     const std::shared_ptr<const AdditionalPackageDepSpecRequirement> &);
 
             /**
+             * Add a key requirement, return ourself.
+             */
+            PartiallyMadePackageDepSpec & key_constraint(
+                    const std::string & key, const KeyConstraintOperation, const std::string & pattern);
+
+            /**
              * Clear additional requirements, return ourself.
              *
              * \since 0.41
diff --git a/paludis/resolver/match_qpns.cc b/paludis/resolver/match_qpns.cc
index 2af1ee3..f1aa35f 100644
--- a/paludis/resolver/match_qpns.cc
+++ b/paludis/resolver/match_qpns.cc
@@ -50,6 +50,7 @@ paludis::resolver::match_qpns(
                     n::has_installable_to_path() = false,
                     n::has_installable_to_repository() = false,
                     n::has_installed_at_path() = false,
+                    n::has_key_requirements() = false,
                     n::has_package() = indeterminate,
                     n::has_package_name_part() = indeterminate,
                     n::has_tag() = false,
diff --git a/paludis/user_dep_spec-fwd.hh b/paludis/user_dep_spec-fwd.hh
index c31ce08..5c10ea9 100644
--- a/paludis/user_dep_spec-fwd.hh
+++ b/paludis/user_dep_spec-fwd.hh
@@ -63,8 +63,6 @@ namespace paludis
             ///\}
     };
 
-    struct UserKeyRequirement;
-
     /**
      * The VersionSpecOptions to use for parsing a user spec.
      *
diff --git a/paludis/user_dep_spec.cc b/paludis/user_dep_spec.cc
index c2de828..59310c4 100644
--- a/paludis/user_dep_spec.cc
+++ b/paludis/user_dep_spec.cc
@@ -35,7 +35,6 @@
 #include <paludis/util/options.hh>
 #include <paludis/util/log.hh>
 #include <paludis/util/make_named_values.hh>
-#include <paludis/util/pimp-impl.hh>
 #include <paludis/util/set.hh>
 #include <paludis/util/sequence.hh>
 #include <paludis/util/indirect_iterator-impl.hh>
@@ -221,8 +220,8 @@ namespace
 
             case '.':
                 {
-                    std::shared_ptr<const AdditionalPackageDepSpecRequirement> req(std::make_shared<UserKeyRequirement>(flag.substr(1)));
-                    result.additional_requirement(req);
+                    auto k(parse_user_key_constraint(flag.substr(1)));
+                    result.key_constraint(std::get<0>(k), std::get<1>(k), std::get<2>(k));
                 }
                 break;
 
@@ -381,585 +380,39 @@ GotASetNotAPackageDepSpec::GotASetNotAPackageDepSpec(const std::string & s) thro
 {
 }
 
-namespace paludis
-{
-    template <>
-    struct Imp<UserKeyRequirement>
-    {
-        std::string key;
-        std::string value;
-        char op;
-
-        Imp(const std::string & s)
-        {
-            std::string::size_type p(s.find_first_of("=<>?"));
-            if (std::string::npos == p)
-                throw PackageDepSpecError("Expected an =, a <, a > or a ? inside '[." + s + "]'");
-
-            key = s.substr(0, p);
-            value = s.substr(p + 1);
-            op = s.at(p);
-
-            if (op == '?' && ! value.empty())
-                throw PackageDepSpecError("Operator '?' takes no value inside '[." + s + "]'");
-        }
-    };
-}
-
-UserKeyRequirement::UserKeyRequirement(const std::string & s) :
-    _imp(s)
+VersionSpecOptions
+paludis::user_version_spec_options()
 {
+    return { vso_flexible_dashes, vso_flexible_dots,
+        vso_ignore_case, vso_letters_anywhere, vso_dotted_suffixes };
 }
 
-UserKeyRequirement::~UserKeyRequirement()
+std::tuple<std::string, KeyConstraintOperation, std::string>
+paludis::parse_user_key_constraint(const std::string & s)
 {
-}
+    std::string::size_type p(s.find_first_of("=<>?"));
+    if (std::string::npos == p)
+        throw PackageDepSpecError("[." + s + "] contains no operator");
 
-namespace
-{
-    std::string stringify_contents_entry(const ContentsEntry & e)
+    if (s.at(p) == '?')
     {
-        return stringify(e.location_key()->value());
+        if (s.length() - 1 != p)
+            throw PackageDepSpecError("[." + s + "] uses a key with operator '?'");
+        else
+            return std::make_tuple(s.substr(0, p), kco_question, "");
     }
-
-    struct StringifyEqual
-    {
-        const std::string pattern;
-
-        StringifyEqual(const std::string & p) :
-            pattern(p)
-        {
-        }
-
-        template <typename T_>
-        bool operator() (const T_ & t) const
-        {
-            return stringify(t) == pattern;
-        }
-
-        bool operator() (const ContentsEntry & e) const
-        {
-            return stringify_contents_entry(e) == pattern;
-        }
-    };
-
-    struct SpecTreeSearcher
-    {
-        const Environment * const env;
-        const std::shared_ptr<const PackageID> id;
-        const std::string pattern;
-
-        SpecTreeSearcher(const Environment * const e, const std::shared_ptr<const PackageID> & i, const std::string & p) :
-            env(e),
-            id(i),
-            pattern(p)
-        {
-        }
-
-        bool visit(const GenericSpecTree::NodeType<AllDepSpec>::Type & n) const
-        {
-            return indirect_iterator(n.end()) != std::find_if(indirect_iterator(n.begin()), indirect_iterator(n.end()),
-                    accept_visitor_returning<bool>(*this));
-        }
-
-        bool visit(const GenericSpecTree::NodeType<AnyDepSpec>::Type & n) const
-        {
-            return indirect_iterator(n.end()) != std::find_if(indirect_iterator(n.begin()), indirect_iterator(n.end()),
-                    accept_visitor_returning<bool>(*this));
-        }
-
-        bool visit(const GenericSpecTree::NodeType<ExactlyOneDepSpec>::Type & n) const
-        {
-            return indirect_iterator(n.end()) != std::find_if(indirect_iterator(n.begin()), indirect_iterator(n.end()),
-                    accept_visitor_returning<bool>(*this));
-        }
-
-        bool visit(const GenericSpecTree::NodeType<ConditionalDepSpec>::Type & n) const
-        {
-            if (n.spec()->condition_met(env, id))
-                return indirect_iterator(n.end()) != std::find_if(indirect_iterator(n.begin()), indirect_iterator(n.end()),
-                        accept_visitor_returning<bool>(*this));
-            else
-                return false;
-        }
-
-        bool visit(const GenericSpecTree::NodeType<NamedSetDepSpec>::Type & n) const
-        {
-            return stringify(*n.spec()) == pattern;
-        }
-
-        bool visit(const GenericSpecTree::NodeType<PlainTextDepSpec>::Type & n) const
-        {
-            return stringify(*n.spec()) == pattern;
-        }
-
-        bool visit(const GenericSpecTree::NodeType<PackageDepSpec>::Type & n) const
-        {
-            return stringify(*n.spec()) == pattern;
-        }
-
-        bool visit(const GenericSpecTree::NodeType<BlockDepSpec>::Type & n) const
-        {
-            return stringify(*n.spec()) == pattern;
-        }
-
-        bool visit(const GenericSpecTree::NodeType<LicenseDepSpec>::Type & n) const
-        {
-            return stringify(*n.spec()) == pattern;
-        }
-
-        bool visit(const GenericSpecTree::NodeType<SimpleURIDepSpec>::Type & n) const
-        {
-            return stringify(*n.spec()) == pattern;
-        }
-
-        bool visit(const GenericSpecTree::NodeType<FetchableURIDepSpec>::Type & n) const
-        {
-            return stringify(*n.spec()) == pattern;
-        }
-
-        bool visit(const GenericSpecTree::NodeType<DependenciesLabelsDepSpec>::Type & n) const
-        {
-            return indirect_iterator(n.spec()->end()) != std::find_if(indirect_iterator(n.spec()->begin()),
-                    indirect_iterator(n.spec()->end()), StringifyEqual(pattern));
-        }
-
-        bool visit(const GenericSpecTree::NodeType<URILabelsDepSpec>::Type & n) const
-        {
-            return indirect_iterator(n.spec()->end()) != std::find_if(indirect_iterator(n.spec()->begin()),
-                    indirect_iterator(n.spec()->end()), StringifyEqual(pattern));
-        }
-
-        bool visit(const GenericSpecTree::NodeType<PlainTextLabelDepSpec>::Type & n) const
-        {
-            return stringify(*n.spec()) == pattern;
-        }
-    };
-
-    struct KeyComparator
+    else
     {
-        const Environment * const env;
-        const std::shared_ptr<const PackageID> id;
-        const std::string pattern;
-        const char op;
-
-        KeyComparator(const Environment * const e, const std::shared_ptr<const PackageID> & i,
-                const std::string & p, const char o) :
-            env(e),
-            id(i),
-            pattern(p),
-            op(o)
-        {
-        }
-
-        bool visit(const MetadataSectionKey &) const
-        {
-            return false;
-        }
-
-        bool visit(const MetadataTimeKey & k) const
-        {
-            switch (op)
-            {
-                case '=':
-                    return pattern == stringify(k.value().seconds());
-                case '<':
-                    return k.value().seconds() < destringify<time_t>(pattern);
-                case '>':
-                    return k.value().seconds() > destringify<time_t>(pattern);
-            }
-
-            return false;
-        }
-
-        bool visit(const MetadataValueKey<std::string> & k) const
-        {
-            return pattern == stringify(k.value());
-        }
-
-        bool visit(const MetadataValueKey<SlotName> & k) const
-        {
-            return pattern == stringify(k.value());
-        }
-
-        bool visit(const MetadataValueKey<FSPath> & k) const
-        {
-            return pattern == stringify(k.value());
-        }
-
-        bool visit(const MetadataValueKey<bool> & k) const
-        {
-            return pattern == stringify(k.value());
-        }
-
-        bool visit(const MetadataValueKey<long> & k) const
-        {
-            switch (op)
-            {
-                case '=':
-                    return pattern == stringify(k.value());
-                case '<':
-                    return k.value() < destringify<long>(pattern);
-                case '>':
-                    return k.value() > destringify<long>(pattern);
-            }
-
-            return false;
-        }
-
-        bool visit(const MetadataValueKey<std::shared_ptr<const Choices> > &) const
-        {
-            return false;
-        }
-
-        bool visit(const MetadataValueKey<std::shared_ptr<const Contents> > & s) const
-        {
-            switch (op)
-            {
-                case '=':
-                    return pattern == join(indirect_iterator(s.value()->begin()), indirect_iterator(s.value()->end()), " ",
-                            stringify_contents_entry);
-                case '<':
-                    return indirect_iterator(s.value()->end()) != std::find_if(
-                            indirect_iterator(s.value()->begin()),
-                            indirect_iterator(s.value()->end()),
-                            StringifyEqual(pattern));
-            }
-
-            return false;
-        }
-
-        bool visit(const MetadataValueKey<std::shared_ptr<const PackageID> > & k) const
-        {
-            return pattern == stringify(*k.value());
-        }
-
-        bool visit(const MetadataSpecTreeKey<DependencySpecTree> & s) const
-        {
-            switch (op)
-            {
-                case '=':
-                    return false;
-                case '<':
-                    return s.value()->top()->accept_returning<bool>(SpecTreeSearcher(env, id, pattern));
-            }
-
-            return false;
-        }
-
-        bool visit(const MetadataSpecTreeKey<SetSpecTree> & s) const
-        {
-            switch (op)
-            {
-                case '=':
-                    return false;
-                case '<':
-                    return s.value()->top()->accept_returning<bool>(SpecTreeSearcher(env, id, pattern));
-            }
-
-            return false;
-        }
-
-        bool visit(const MetadataSpecTreeKey<PlainTextSpecTree> & s) const
-        {
-            switch (op)
-            {
-                case '=':
-                    return false;
-                case '<':
-                    return s.value()->top()->accept_returning<bool>(SpecTreeSearcher(env, id, pattern));
-            }
-
-            return false;
-        }
-
-        bool visit(const MetadataSpecTreeKey<RequiredUseSpecTree> & s) const
+        KeyConstraintOperation op(last_kco);
+        switch (s.at(p))
         {
-            switch (op)
-            {
-                case '=':
-                    return false;
-                case '<':
-                    return s.value()->top()->accept_returning<bool>(SpecTreeSearcher(env, id, pattern));
-            }
-
-            return false;
-        }
-
-        bool visit(const MetadataSpecTreeKey<ProvideSpecTree> & s) const
-        {
-            switch (op)
-            {
-                case '=':
-                    return false;
-                case '<':
-                    return s.value()->top()->accept_returning<bool>(SpecTreeSearcher(env, id, pattern));
-            }
-
-            return false;
-        }
-
-        bool visit(const MetadataSpecTreeKey<SimpleURISpecTree> & s) const
-        {
-            switch (op)
-            {
-                case '=':
-                    return false;
-                case '<':
-                    return s.value()->top()->accept_returning<bool>(SpecTreeSearcher(env, id, pattern));
-            }
-
-            return false;
-        }
-
-        bool visit(const MetadataSpecTreeKey<FetchableURISpecTree> & s) const
-        {
-            switch (op)
-            {
-                case '=':
-                    return false;
-                case '<':
-                    return s.value()->top()->accept_returning<bool>(SpecTreeSearcher(env, id, pattern));
-            }
-
-            return false;
-        }
-
-        bool visit(const MetadataSpecTreeKey<LicenseSpecTree> & s) const
-        {
-            switch (op)
-            {
-                case '=':
-                    return false;
-                case '<':
-                    return s.value()->top()->accept_returning<bool>(SpecTreeSearcher(env, id, pattern));
-            }
-
-            return false;
-        }
-
-        bool visit(const MetadataCollectionKey<FSPathSequence> & s) const
-        {
-            switch (op)
-            {
-                case '=':
-                    return pattern == join(s.value()->begin(), s.value()->end(), " ");
-                case '<':
-                    return s.value()->end() != std::find_if(s.value()->begin(), s.value()->end(),
-                            StringifyEqual(pattern));
-            }
-
-            return false;
-        }
-
-        bool visit(const MetadataCollectionKey<PackageIDSequence> & s) const
-        {
-            switch (op)
-            {
-                case '=':
-                    return pattern == join(indirect_iterator(s.value()->begin()), indirect_iterator(s.value()->end()), " ");
-                case '<':
-                    return indirect_iterator(s.value()->end()) != std::find_if(
-                            indirect_iterator(s.value()->begin()),
-                            indirect_iterator(s.value()->end()),
-                            StringifyEqual(pattern));
-            }
-
-            return false;
-        }
-
-        bool visit(const MetadataCollectionKey<Sequence<std::string> > & s) const
-        {
-            switch (op)
-            {
-                case '=':
-                    return pattern == join(s.value()->begin(), s.value()->end(), " ");
-                case '<':
-                    return s.value()->end() != std::find_if(s.value()->begin(), s.value()->end(),
-                            StringifyEqual(pattern));
-            }
-
-            return false;
-        }
-
-        bool visit(const MetadataCollectionKey<Set<std::string> > & s) const
-        {
-            switch (op)
-            {
-                case '=':
-                    return pattern == join(s.value()->begin(), s.value()->end(), " ");
-                case '<':
-                    return s.value()->end() != std::find_if(s.value()->begin(), s.value()->end(),
-                            StringifyEqual(pattern));
-            }
-
-            return false;
-        }
-
-        bool visit(const MetadataCollectionKey<Map<std::string, std::string> > &) const
-        {
-            return false;
-        }
-
-        bool visit(const MetadataCollectionKey<KeywordNameSet> & s) const
-        {
-            switch (op)
-            {
-                case '=':
-                    return pattern == join(s.value()->begin(), s.value()->end(), " ");
-                case '<':
-                    return s.value()->end() != std::find_if(s.value()->begin(), s.value()->end(),
-                            StringifyEqual(pattern));
-            }
-
-            return false;
+            case '=': op = kco_equals;        break;
+            case '<': op = kco_less_than;     break;
+            case '>': op = kco_greater_than;  break;
+            default:
+                throw PackageDepSpecError("[." + s + "] unknown operator");
         }
-    };
-}
-
-const std::pair<bool, std::string>
-UserKeyRequirement::requirement_met(
-        const Environment * const env,
-        const ChangedChoices * const,
-        const std::shared_ptr<const PackageID> & id,
-        const std::shared_ptr<const PackageID> & from_id,
-        const ChangedChoices * const) const
-{
-    Context context("When working out whether '" + stringify(*id) + "' matches " + as_raw_string() + ":");
-
-    const MetadataKey * key(0);
-
-    auto repo(env->fetch_repository(id->repository_name()));
-    if (0 == _imp->key.compare(0, 3, "::$"))
-    {
-        if (_imp->key == "::$format")
-            key = repo->format_key().get();
-        else if (_imp->key == "::$location")
-            key = repo->location_key().get();
-        else if (_imp->key == "::$installed_root")
-            key = repo->installed_root_key().get();
-        else if (_imp->key == "::$accept_keywords")
-            key = repo->accept_keywords_key().get();
-        else if (_imp->key == "::$sync_host")
-            key = repo->sync_host_key().get();
-    }
-    else if (0 == _imp->key.compare(0, 1, "$"))
-    {
-        if (_imp->key == "$behaviours")
-            key = id->behaviours_key().get();
-        else if (_imp->key == "$build_dependencies")
-            key = id->build_dependencies_key().get();
-        else if (_imp->key == "$choices")
-            key = id->choices_key().get();
-        else if (_imp->key == "$contained_in")
-            key = id->contained_in_key().get();
-        else if (_imp->key == "$contains")
-            key = id->contains_key().get();
-        else if (_imp->key == "$contents")
-            key = id->contents_key().get();
-        else if (_imp->key == "$dependencies")
-            key = id->dependencies_key().get();
-        else if (_imp->key == "$fetches")
-            key = id->fetches_key().get();
-        else if (_imp->key == "$from_repositories")
-            key = id->from_repositories_key().get();
-        else if (_imp->key == "$fs_location")
-            key = id->fs_location_key().get();
-        else if (_imp->key == "$homepage")
-            key = id->homepage_key().get();
-        else if (_imp->key == "$installed_time")
-            key = id->installed_time_key().get();
-        else if (_imp->key == "$keywords")
-            key = id->keywords_key().get();
-        else if (_imp->key == "$long_description")
-            key = id->long_description_key().get();
-        else if (_imp->key == "$post_dependencies")
-            key = id->post_dependencies_key().get();
-        else if (_imp->key == "$provide")
-            key = id->provide_key().get();
-        else if (_imp->key == "$run_dependencies")
-            key = id->run_dependencies_key().get();
-        else if (_imp->key == "$short_description")
-            key = id->short_description_key().get();
-        else if (_imp->key == "$slot")
-            key = id->slot_key().get();
-        else if (_imp->key == "$suggested_dependencies")
-            key = id->suggested_dependencies_key().get();
-        else if (_imp->key == "$virtual_for")
-            key = id->virtual_for_key().get();
+        return std::make_tuple(s.substr(0, p), op, s.substr(p + 1));
     }
-    else if (0 == _imp->key.compare(0, 2, "::"))
-    {
-        Repository::MetadataConstIterator m(repo->find_metadata(_imp->key.substr(2)));
-        if (m != repo->end_metadata())
-            key = m->get();
-    }
-    else
-    {
-        PackageID::MetadataConstIterator m(id->find_metadata(_imp->key));
-        if (m != id->end_metadata())
-            key = m->get();
-    }
-
-    if (! key)
-        return std::make_pair(false, as_human_string(from_id));
-
-    if (_imp->op == '?')
-        return std::make_pair(true, as_human_string(from_id));
-    else
-    {
-        KeyComparator c(env, id, _imp->value, _imp->op);
-        return std::make_pair(key->accept_returning<bool>(c), as_human_string(from_id));
-    }
-}
-
-const std::string
-UserKeyRequirement::as_human_string(const std::shared_ptr<const PackageID> &) const
-{
-    std::string key_str;
-    if ((! _imp->key.empty()) && (_imp->key.at(0) == '$'))
-        key_str = "with role '" + _imp->key.substr(1) + "'";
-    else
-        key_str = "'" + _imp->key + "'";
-
-    switch (_imp->op)
-    {
-        case '=':
-            return "Key " + key_str + " has simple string value '" + _imp->value + "'";
-        case '<':
-            return "Key " + key_str + " contains or is less than '" + _imp->value + "'";
-        case '>':
-            return "Key " + key_str + " is greater than '" + _imp->value + "'";
-        case '?':
-            return "Key " + key_str + " exists";
-    }
-
-    throw InternalError(PALUDIS_HERE, "unknown op");
-}
-
-const std::string
-UserKeyRequirement::as_raw_string() const
-{
-    return "[." + _imp->key + std::string(1, _imp->op) + _imp->value + "]";
-}
-
-Tribool
-UserKeyRequirement::accumulate_changes_to_make_met(
-        const Environment * const,
-        const ChangedChoices * const,
-        const std::shared_ptr<const PackageID> &,
-        const std::shared_ptr<const PackageID> &,
-        ChangedChoices &) const
-{
-    return false;
 }
 
-VersionSpecOptions
-paludis::user_version_spec_options()
-{
-    return { vso_flexible_dashes, vso_flexible_dots,
-        vso_ignore_case, vso_letters_anywhere, vso_dotted_suffixes };
-}
-
-template class Pimp<UserKeyRequirement>;
-
diff --git a/paludis/user_dep_spec.hh b/paludis/user_dep_spec.hh
index 6567911..0398c5e 100644
--- a/paludis/user_dep_spec.hh
+++ b/paludis/user_dep_spec.hh
@@ -23,9 +23,12 @@
 #include <paludis/user_dep_spec-fwd.hh>
 #include <paludis/dep_spec.hh>
 #include <paludis/filter.hh>
-#include <paludis/additional_package_dep_spec_requirement.hh>
+#include <paludis/package_dep_spec_constraint-fwd.hh>
+
 #include <paludis/util/pimp.hh>
 
+#include <tuple>
+
 namespace paludis
 {
     /**
@@ -53,46 +56,13 @@ namespace paludis
             const std::string &) PALUDIS_VISIBLE;
 
     /**
-     * A key requirement for a user PackageDepSpec.
+     * Split up a [.key=value] into its component parts.
      *
-     * \since 0.36
      * \ingroup g_dep_spec
+     * \since 0.61
      */
-    class PALUDIS_VISIBLE UserKeyRequirement :
-        public AdditionalPackageDepSpecRequirement
-    {
-        private:
-            Pimp<UserKeyRequirement> _imp;
-
-        public:
-            ///\name Basic operations
-            ///\{
-
-            UserKeyRequirement(const std::string &);
-            ~UserKeyRequirement();
-
-            ///\}
-
-            virtual const std::pair<bool, std::string> requirement_met(
-                    const Environment * const, const ChangedChoices *,
-                    const std::shared_ptr<const PackageID> &,
-                    const std::shared_ptr<const PackageID> &,
-                    const ChangedChoices * const) const PALUDIS_ATTRIBUTE((warn_unused_result));
-
-            virtual const std::string as_human_string(
-                    const std::shared_ptr<const PackageID> &) const PALUDIS_ATTRIBUTE((warn_unused_result));
-
-            virtual const std::string as_raw_string() const PALUDIS_ATTRIBUTE((warn_unused_result));
-
-            virtual Tribool accumulate_changes_to_make_met(
-                    const Environment * const,
-                    const ChangedChoices * const,
-                    const std::shared_ptr<const PackageID> &,
-                    const std::shared_ptr<const PackageID> &,
-                    ChangedChoices &) const PALUDIS_ATTRIBUTE((warn_unused_result));
-    };
-
-    extern template class Pimp<UserKeyRequirement>;
+    std::tuple<std::string, KeyConstraintOperation, std::string> parse_user_key_constraint(
+            const std::string &) PALUDIS_VISIBLE PALUDIS_ATTRIBUTE((warn_unused_result));
 }
 
 #endif
diff --git a/paludis/user_dep_spec_TEST.cc b/paludis/user_dep_spec_TEST.cc
index 2fa1e6e..2da7b49 100644
--- a/paludis/user_dep_spec_TEST.cc
+++ b/paludis/user_dep_spec_TEST.cc
@@ -51,6 +51,24 @@ namespace
         return stringify(v.version_operator()) + stringify(v.version_spec());
     }
 
+    std::string stringify_key_constraint(const KeyConstraint & k)
+    {
+        std::string result(k.key());
+
+        switch (k.operation())
+        {
+            case kco_question:     result.append("?"); break;
+            case kco_equals:       result.append("="); break;
+            case kco_less_than:    result.append("<"); break;
+            case kco_greater_than: result.append(">"); break;
+            case last_kco:
+                break;
+        }
+
+        result.append(k.pattern());
+        return "[." + result + "]";
+    }
+
     class UserDepSpecTest :
         public testing::Test
     {
@@ -154,10 +172,17 @@ UserDepSpecTest::check_spec(
         EXPECT_TRUE((! spec.additional_requirements_ptr()) || spec.additional_requirements_ptr()->empty());
     else
     {
-        ASSERT_TRUE(bool(spec.additional_requirements_ptr()));
-        EXPECT_EQ(additional_requirement, stringify(join(
-                        indirect_iterator(spec.additional_requirements_ptr()->begin()),
-                        indirect_iterator(spec.additional_requirements_ptr()->end()), ", ")));
+        ASSERT_TRUE(bool(spec.additional_requirements_ptr()) || bool(spec.all_key_constraints()));
+        std::string x;
+        if (spec.additional_requirements_ptr())
+            x.append(stringify(join(
+                            indirect_iterator(spec.additional_requirements_ptr()->begin()),
+                            indirect_iterator(spec.additional_requirements_ptr()->end()), ", ")));
+        if (spec.all_key_constraints())
+            x.append(stringify(join(
+                            indirect_iterator(spec.all_key_constraints()->begin()),
+                            indirect_iterator(spec.all_key_constraints()->end()), ", ", &stringify_key_constraint)));
+        EXPECT_EQ(additional_requirement, x);
     }
 
     if (installed_at_path.empty())
diff --git a/python/dep_spec.cc b/python/dep_spec.cc
index ab05cfb..beb8fa0 100644
--- a/python/dep_spec.cc
+++ b/python/dep_spec.cc
@@ -83,6 +83,7 @@ namespace paludis
         std::shared_ptr<const InRepositoryConstraint> in_repository;
         std::shared_ptr<const FromRepositoryConstraint> from_repository;
         std::shared_ptr<const AdditionalPackageDepSpecRequirements> additional_requirements;
+        std::shared_ptr<const KeyConstraintSequence> all_keys;
         const std::string str;
 
         Imp(
@@ -96,6 +97,7 @@ namespace paludis
                 const std::shared_ptr<const InRepositoryConstraint> & ri,
                 const std::shared_ptr<const FromRepositoryConstraint> & rf,
                 const std::shared_ptr<const AdditionalPackageDepSpecRequirements> & u,
+                const std::shared_ptr<const KeyConstraintSequence> & k,
                 const std::string & st) :
             package_name_constraint(q),
             category_name_part_constraint(c),
@@ -107,6 +109,7 @@ namespace paludis
             in_repository(ri),
             from_repository(rf),
             additional_requirements(u),
+            all_keys(k),
             str(st)
         {
         }
@@ -236,6 +239,7 @@ PythonPackageDepSpec::PythonPackageDepSpec(const PackageDepSpec & p) :
             p.in_repository_constraint(),
             p.from_repository_constraint(),
             p.additional_requirements_ptr(),
+            p.all_key_constraints(),
             stringify(p))
 {
     if (p.version_requirements_ptr())
@@ -258,6 +262,7 @@ PythonPackageDepSpec::PythonPackageDepSpec(const PythonPackageDepSpec & p) :
             p.in_repository_constraint(),
             p.from_repository_constraint(),
             p.additional_requirements_ptr(),
+            p.all_key_constraints(),
             p.py_str())
 {
     std::copy(p.version_requirements_ptr()->begin(), p.version_requirements_ptr()->end(),
@@ -302,6 +307,13 @@ PythonPackageDepSpec::operator PackageDepSpec() const
             p.additional_requirement(*i);
     }
 
+    if (all_key_constraints())
+    {
+        for (auto i(all_key_constraints()->begin()), i_end(all_key_constraints()->end()) ;
+                i != i_end ; ++i)
+            p.key_constraint((*i)->key(), (*i)->operation(), (*i)->pattern());
+    }
+
     if (version_requirements_ptr())
     {
         for (VersionRequirements::ConstIterator i(version_requirements_ptr()->begin()),
@@ -384,6 +396,12 @@ PythonPackageDepSpec::additional_requirements_ptr() const
     return _imp->additional_requirements;
 }
 
+const std::shared_ptr<const KeyConstraintSequence>
+PythonPackageDepSpec::all_key_constraints() const
+{
+    return _imp->all_keys;
+}
+
 std::string
 PythonPackageDepSpec::py_str() const
 {
diff --git a/python/dep_spec.hh b/python/dep_spec.hh
index d53d4eb..07f8986 100644
--- a/python/dep_spec.hh
+++ b/python/dep_spec.hh
@@ -179,6 +179,7 @@ namespace paludis
                 const std::shared_ptr<const FromRepositoryConstraint> from_repository_constraint() const;
                 const std::shared_ptr<const ExactSlotConstraint> exact_slot_constraint() const;
                 const std::shared_ptr<const AnySlotConstraint> any_slot_constraint() const;
+                const std::shared_ptr<const KeyConstraintSequence> all_key_constraints() const;
 
                 std::shared_ptr<const VersionRequirements> version_requirements_ptr() const;
                 VersionRequirementsMode version_requirements_mode() const;
diff --git a/python/package_dep_spec_constraint.cc b/python/package_dep_spec_constraint.cc
index c78ba41..7385ec2 100644
--- a/python/package_dep_spec_constraint.cc
+++ b/python/package_dep_spec_constraint.cc
@@ -46,6 +46,12 @@ class class_package_dep_spec_constraint :
 void expose_package_dep_spec_constraint()
 {
     /**
+     * Enums
+     */
+    enum_auto("KeyConstraintOperation", last_kco,
+            "The operation for a KeyConstraint");
+
+    /**
      * PackageDepSpecConstraint
      */
     bp::register_ptr_to_python<std::shared_ptr<const PackageDepSpecConstraint> >();
@@ -220,5 +226,28 @@ void expose_package_dep_spec_constraint()
                 "[RO] The slot name"
             )
         ;
+
+    /**
+     * KeyConstraint
+     */
+    class_package_dep_spec_constraint<KeyConstraint>
+        (
+         "KeyConstraint",
+         "A [.key=value] constraint for a PackageDepSpec.",
+         bp::no_init
+        )
+
+        .add_property("key", &KeyConstraint::key,
+                "[RO] The key"
+            )
+
+        .add_property("pattern", &KeyConstraint::pattern,
+                "[RO] The pattern"
+            )
+
+        .add_property("operation", &KeyConstraint::operation,
+                "[RO] The operation"
+            )
+        ;
 }
 
diff --git a/ruby/package_dep_spec_constraint.cc b/ruby/package_dep_spec_constraint.cc
index 6279908..52109a5 100644
--- a/ruby/package_dep_spec_constraint.cc
+++ b/ruby/package_dep_spec_constraint.cc
@@ -41,6 +41,9 @@ namespace
     static VALUE c_installable_to_repository_constraint;
     static VALUE c_any_slot_constraint;
     static VALUE c_exact_slot_constraint;
+    static VALUE c_key_constraint;
+
+    static VALUE c_key_constraint_operation;
 
     struct V
     {
@@ -111,6 +114,12 @@ namespace
             value = Data_Wrap_Struct(c_exact_slot_constraint, 0, &Common<std::shared_ptr<const PackageDepSpecConstraint> >::free,
                     new std::shared_ptr<const PackageDepSpecConstraint>(mm));
         }
+
+        void visit(const KeyConstraint &)
+        {
+            value = Data_Wrap_Struct(c_key_constraint, 0, &Common<std::shared_ptr<const PackageDepSpecConstraint> >::free,
+                    new std::shared_ptr<const PackageDepSpecConstraint>(mm));
+        }
     };
 
     /*
@@ -282,6 +291,45 @@ namespace
         return rb_str_new2(stringify((std::static_pointer_cast<const ExactSlotConstraint>(*ptr))->name()).c_str());
     }
 
+    /*
+     * Document-method: key
+     *
+     * The key constraint.
+     */
+    static VALUE
+    key_constraint_key(VALUE self)
+    {
+        std::shared_ptr<const PackageDepSpecConstraint> * ptr;
+        Data_Get_Struct(self, std::shared_ptr<const PackageDepSpecConstraint>, ptr);
+        return rb_str_new2(stringify((std::static_pointer_cast<const KeyConstraint>(*ptr))->key()).c_str());
+    }
+
+    /*
+     * Document-method: pattern
+     *
+     * The pattern constraint.
+     */
+    static VALUE
+    key_constraint_pattern(VALUE self)
+    {
+        std::shared_ptr<const PackageDepSpecConstraint> * ptr;
+        Data_Get_Struct(self, std::shared_ptr<const PackageDepSpecConstraint>, ptr);
+        return rb_str_new2(stringify((std::static_pointer_cast<const KeyConstraint>(*ptr))->pattern()).c_str());
+    }
+
+    /*
+     * Document-method: operation
+     *
+     * The operation constraint.
+     */
+    static VALUE
+    key_constraint_operation(VALUE self)
+    {
+        std::shared_ptr<const PackageDepSpecConstraint> * ptr;
+        Data_Get_Struct(self, std::shared_ptr<const PackageDepSpecConstraint>, ptr);
+        return INT2FIX((std::static_pointer_cast<const KeyConstraint>(*ptr))->operation());
+    }
+
     void do_register_package_dep_spec_constraint()
     {
         /*
@@ -406,6 +454,33 @@ namespace
                     &exact_slot_constraint_locked), 0);
         rb_define_method(c_exact_slot_constraint, "name", RUBY_FUNC_CAST(
                     &exact_slot_constraint_name), 0);
+
+        /*
+         * Document-class: Paludis::KeyConstraint
+         *
+         * Represents a [.key=value] constraint in a PackageDepSpec.
+         */
+        c_key_constraint = rb_define_class_under(
+                paludis_module(), "KeyConstraint", c_package_dep_spec_constraint);
+        rb_funcall(c_key_constraint, rb_intern("private_class_method"), 1, rb_str_new2("new"));
+        rb_define_method(c_key_constraint, "key", RUBY_FUNC_CAST(
+                    &key_constraint_key), 0);
+        rb_define_method(c_key_constraint, "pattern", RUBY_FUNC_CAST(
+                    &key_constraint_pattern), 0);
+        rb_define_method(c_key_constraint, "operation", RUBY_FUNC_CAST(
+                    &key_constraint_operation), 0);
+
+        /*
+         * Document-module: Paludis::KeyConstraintOperation
+         *
+         * The operation for a KeyConstraint.
+         */
+        c_key_constraint_operation = rb_define_module_under(paludis_module(), "KeyConstraintOperation");
+        for (KeyConstraintOperation l(static_cast<KeyConstraintOperation>(0)), l_end(last_kco) ; l != l_end ;
+                l = static_cast<KeyConstraintOperation>(static_cast<int>(l) + 1))
+            rb_define_const(c_key_constraint_operation, value_case_to_RubyCase(stringify(l)).c_str(), INT2FIX(l));
+
+        // cc_enum_special<paludis/package_dep_spec_constraint-se.hh, KeyConstraint, c_key_constraint_operation>
     }
 }
 
diff --git a/src/clients/cave/cmd_display_resolution.cc b/src/clients/cave/cmd_display_resolution.cc
index 0d9cea2..8ac3a3f 100755
--- a/src/clients/cave/cmd_display_resolution.cc
+++ b/src/clients/cave/cmd_display_resolution.cc
@@ -79,6 +79,7 @@
 #include <paludis/changed_choices.hh>
 #include <paludis/mask_utils.hh>
 #include <paludis/dep_spec_annotations.hh>
+#include <paludis/additional_package_dep_spec_requirement.hh>
 
 #include <set>
 #include <iterator>
diff --git a/src/clients/cave/cmd_execute_resolution.cc b/src/clients/cave/cmd_execute_resolution.cc
index d72dc11..2e63b19 100644
--- a/src/clients/cave/cmd_execute_resolution.cc
+++ b/src/clients/cave/cmd_execute_resolution.cc
@@ -694,6 +694,7 @@ namespace
                                 n::has_installable_to_path() = false,
                                 n::has_installable_to_repository() = false,
                                 n::has_installed_at_path() = false,
+                                n::has_key_requirements() = false,
                                 n::has_package() = true,
                                 n::has_package_name_part() = false,
                                 n::has_tag() = indeterminate,
diff --git a/src/clients/cave/cmd_print_spec.cc b/src/clients/cave/cmd_print_spec.cc
index a693bcf..a967aec 100644
--- a/src/clients/cave/cmd_print_spec.cc
+++ b/src/clients/cave/cmd_print_spec.cc
@@ -258,7 +258,10 @@ namespace
                     a_end(cmdline.a_additional_requirement.end_args()) ;
                     a != a_end ; ++a)
                 if (! a->empty())
-                    s.additional_requirement(std::make_shared<UserKeyRequirement>(*a));
+                {
+                    auto k(parse_user_key_constraint(*a));
+                    s.key_constraint(std::get<0>(k), std::get<1>(k), std::get<2>(k));
+                }
         }
 
         cout << PackageDepSpec(s) << endl;