diff --git a/cc/toolchains/feature_constraint.bzl b/cc/toolchains/feature_constraint.bzl
new file mode 100644
index 0000000..b02d420
--- /dev/null
+++ b/cc/toolchains/feature_constraint.bzl
@@ -0,0 +1,54 @@
+# Copyright 2024 The Bazel Authors. All rights reserved.
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+#     http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+"""Implementation of the cc_feature_constraint rule."""
+
+load(
+    "//cc/toolchains/impl:collect.bzl",
+    "collect_features",
+    "collect_provider",
+)
+load("//cc/toolchains/impl:features_attr.bzl", "disallow_features_attr")
+load(
+    ":cc_toolchain_info.bzl",
+    "FeatureConstraintInfo",
+    "FeatureSetInfo",
+)
+
+def _cc_feature_constraint_impl(ctx):
+    all_of = collect_provider(ctx.attr.all_of, FeatureConstraintInfo)
+    none_of = [collect_features(ctx.attr.none_of)]
+    none_of.extend([fc.none_of for fc in all_of])
+    return [FeatureConstraintInfo(
+        label = ctx.label,
+        all_of = depset(transitive = [fc.all_of for fc in all_of]),
+        none_of = depset(transitive = none_of),
+    )]
+
+_cc_feature_constraint = rule(
+    implementation = _cc_feature_constraint_impl,
+    attrs = {
+        "all_of": attr.label_list(
+            providers = [FeatureConstraintInfo],
+        ),
+        "none_of": attr.label_list(
+            providers = [FeatureSetInfo],
+        ),
+    },
+    provides = [FeatureConstraintInfo],
+    doc = """Defines a constraint on features.
+
+Can be used with require_any_of to specify that something is only enabled when
+a constraint is met.""",
+)
+cc_feature_constraint = disallow_features_attr(_cc_feature_constraint)
diff --git a/cc/toolchains/feature_set.bzl b/cc/toolchains/feature_set.bzl
new file mode 100644
index 0000000..369de9c
--- /dev/null
+++ b/cc/toolchains/feature_set.bzl
@@ -0,0 +1,57 @@
+# Copyright 2024 The Bazel Authors. All rights reserved.
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+#     http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+"""Implementation of the cc_feature_set rule."""
+
+load("//cc/toolchains/impl:collect.bzl", "collect_features")
+load("//cc/toolchains/impl:features_attr.bzl", "require_features_attr")
+load(
+    ":cc_toolchain_info.bzl",
+    "FeatureConstraintInfo",
+    "FeatureSetInfo",
+)
+
+def _cc_feature_set_impl(ctx):
+    features = collect_features(ctx.attr.features_)
+    return [
+        FeatureSetInfo(label = ctx.label, features = features),
+        FeatureConstraintInfo(
+            label = ctx.label,
+            all_of = features,
+            none_of = depset([]),
+        ),
+    ]
+
+_cc_feature_set = rule(
+    implementation = _cc_feature_set_impl,
+    attrs = {
+        "features_": attr.label_list(
+            providers = [FeatureSetInfo],
+            doc = "A set of features",
+        ),
+    },
+    provides = [FeatureSetInfo],
+    doc = """Defines a set of features.
+
+Example:
+
+    cc_feature_set(
+        name = "thin_lto_requirements",
+        all_of = [
+            ":thin_lto",
+            ":opt",
+        ],
+    )
+""",
+)
+cc_feature_set = require_features_attr(_cc_feature_set)
diff --git a/cc/toolchains/impl/features_attr.bzl b/cc/toolchains/impl/features_attr.bzl
new file mode 100644
index 0000000..ab8d83a
--- /dev/null
+++ b/cc/toolchains/impl/features_attr.bzl
@@ -0,0 +1,29 @@
+# Copyright 2024 The Bazel Authors. All rights reserved.
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+#    http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+"""Helpers for dealing with the fact that features is a reserved attribute."""
+
+# buildifier: disable=unnamed-macro
+def disallow_features_attr(rule):
+    def rule_wrapper(*, name, **kwargs):
+        if "features" in kwargs:
+            fail("Cannot use features in %s" % native.package_relative_label(name))
+        rule(name = name, **kwargs)
+
+    return rule_wrapper
+
+def require_features_attr(rule):
+    def rule_wrapper(*, name, features, **kwargs):
+        rule(name = name, features_ = features, **kwargs)
+
+    return rule_wrapper
diff --git a/tests/rule_based_toolchain/features/BUILD b/tests/rule_based_toolchain/features/BUILD
index 0d9f5cd..701d478 100644
--- a/tests/rule_based_toolchain/features/BUILD
+++ b/tests/rule_based_toolchain/features/BUILD
@@ -1,6 +1,8 @@
 load("@rules_testing//lib:util.bzl", "util")
 load("//cc/toolchains:args.bzl", "cc_args")
 load("//cc/toolchains:feature.bzl", "cc_feature")
+load("//cc/toolchains:feature_constraint.bzl", "cc_feature_constraint")
+load("//cc/toolchains:feature_set.bzl", "cc_feature_set")
 load("//tests/rule_based_toolchain:analysis_test_suite.bzl", "analysis_test_suite")
 load(":features_test.bzl", "TARGETS", "TESTS")
 
@@ -23,11 +25,28 @@
 
 util.helper_target(
     cc_feature,
+    name = "simple2",
+    args = [":c_compile"],
+    enabled = False,
+    feature_name = "simple2",
+)
+
+util.helper_target(
+    cc_feature_set,
+    name = "feature_set",
+    features = [
+        ":simple",
+        ":simple2",
+    ],
+)
+
+util.helper_target(
+    cc_feature,
     name = "requires",
     args = [":c_compile"],
     enabled = True,
     feature_name = "requires",
-    requires_any_of = [":simple"],
+    requires_any_of = [":feature_set"],
 )
 
 util.helper_target(
@@ -48,6 +67,23 @@
     mutually_exclusive = [":simple"],
 )
 
+util.helper_target(
+    cc_feature_constraint,
+    name = "direct_constraint",
+    all_of = [":simple"],
+    none_of = [":simple2"],
+)
+
+util.helper_target(
+    cc_feature_constraint,
+    name = "transitive_constraint",
+    all_of = [
+        ":direct_constraint",
+        ":requires",
+    ],
+    none_of = [":implies"],
+)
+
 analysis_test_suite(
     name = "test_suite",
     targets = TARGETS,
diff --git a/tests/rule_based_toolchain/features/features_test.bzl b/tests/rule_based_toolchain/features/features_test.bzl
index 75ae7ee..b6a7db6 100644
--- a/tests/rule_based_toolchain/features/features_test.bzl
+++ b/tests/rule_based_toolchain/features/features_test.bzl
@@ -16,7 +16,9 @@
 load(
     "//cc/toolchains:cc_toolchain_info.bzl",
     "ArgsInfo",
+    "FeatureConstraintInfo",
     "FeatureInfo",
+    "FeatureSetInfo",
     "MutuallyExclusiveCategoryInfo",
 )
 
@@ -43,7 +45,7 @@
     env.expect.that_target(targets.requires).provider(
         FeatureInfo,
     ).requires_any_of().contains_exactly([
-        targets.simple.label,
+        targets.feature_set.label,
     ])
 
 def _feature_collects_implies_test(env, targets):
@@ -63,12 +65,44 @@
         targets.simple.label,
     ])
 
+def _feature_set_collects_features_test(env, targets):
+    env.expect.that_target(targets.feature_set).provider(
+        FeatureSetInfo,
+    ).features().contains_exactly([
+        targets.simple.label,
+        targets.simple2.label,
+    ])
+
+def _feature_constraint_collects_direct_features_test(env, targets):
+    constraint = env.expect.that_target(targets.direct_constraint).provider(
+        FeatureConstraintInfo,
+    )
+    constraint.all_of().contains_exactly([targets.simple.label])
+    constraint.none_of().contains_exactly([targets.simple2.label])
+
+def _feature_constraint_collects_transitive_features_test(env, targets):
+    constraint = env.expect.that_target(targets.transitive_constraint).provider(
+        FeatureConstraintInfo,
+    )
+    constraint.all_of().contains_exactly([
+        targets.simple.label,
+        targets.requires.label,
+    ])
+    constraint.none_of().contains_exactly([
+        targets.simple2.label,
+        targets.implies.label,
+    ])
+
 TARGETS = [
     ":c_compile",
     ":simple",
+    ":simple2",
+    ":feature_set",
     ":requires",
     ":implies",
     ":mutual_exclusion_feature",
+    ":direct_constraint",
+    ":transitive_constraint",
 ]
 
 # @unsorted-dict-items
@@ -77,4 +111,7 @@
     "feature_collects_requirements_test": _feature_collects_requirements_test,
     "feature_collects_implies_test": _feature_collects_implies_test,
     "feature_collects_mutual_exclusion_test": _feature_collects_mutual_exclusion_test,
+    "feature_set_collects_features_test": _feature_set_collects_features_test,
+    "feature_constraint_collects_direct_features_test": _feature_constraint_collects_direct_features_test,
+    "feature_constraint_collects_transitive_features_test": _feature_constraint_collects_transitive_features_test,
 }
diff --git a/tests/rule_based_toolchain/subjects.bzl b/tests/rule_based_toolchain/subjects.bzl
index 23f5ec7..2525887 100644
--- a/tests/rule_based_toolchain/subjects.bzl
+++ b/tests/rule_based_toolchain/subjects.bzl
@@ -88,7 +88,7 @@
 _FeatureSetFactory = generate_factory(
     FeatureSetInfo,
     "FeatureSetInfo",
-    dict(features = _FakeFeatureFactory),
+    dict(features = ProviderDepset(_FakeFeatureFactory)),
 )
 
 # buildifier: disable=name-conventions