[ADT] add initializer list specialization for is_contained

[beanz]

Summary

Adding an initializer list specialization for is_contained allows for compile-time evaluation when called with a constant or runtime evaluation for non-constant values.

This patch doesn't add any uses of this template, but that is coming in
a subsequent patch.

[pete]

llvm/include/llvm/ADT/EnumMatcher.h

10 ↗

(On Diff #416723)

Probably shouldn’t have DXIL in the comment. Otherwise LGTM

[arsenm]

llvm/include/llvm/ADT/EnumMatcher.h

1 ↗

(On Diff #416723)

Missing license header

llvm/unittests/ADT/EnumMatcherTests.cpp

28 ↗

(On Diff #416723)

EXPECT_TRUE

[kuhar]

A few thoughts:

1. Is the requirement for this to be constant folded by the optimizer?
2. This could be made constexpr if we wanted.
3. The function name suggests this handles enums only but it works with any copybale & comparable type. I think we should either restrict it to enum types or make the name more general.
4. Since this function is not constexpr now, how about we added an overload to is_contained accepting an initializer list as the second element, e.g.: is_constained(MyEnum::A, {MyEnum::A, MyEnum::B, MyEnum::C})?

[beanz]

In D122079#3396156, @kuhar wrote:

A few thoughts:

1. Is the requirement for this to be constant folded by the optimizer?

It isn't strictly a requirement. If the code is called with a non-constant value the optimizer will convert it to nice range checks.

2. This could be made constexpr if we wanted.

I had another place that I wanted to use this in clang where the input parameter isn't constant.

4. The function name suggests this handles enums only but it works with any copybale & comparable type. I think we should either restrict it to enum types or make the name more general.

That is totally reasonable. It's really a compile-time set matcher :).

5. Since this function is not constexpr now, how about we added an overload to is_contained accepting an initializer list as the second element, e.g.: is_constained(MyEnum::A, {MyEnum::A, MyEnum::B, MyEnum::C})?

I realize this is probably a bit overkill, but isInEnumSet<Numbers, One, Two, Three, Four, Five>(Val) will actually optimize down to roughly if( Val >= One && Val <= Five) (assuming sequential values), and that really only works reliably with the template parameter unrolling.

[MaskRay]

Does the template compile to efficient code? lld/ELF has a utility which seems pretty efficient https://reviews.llvm.org/D112385#3084969

[MaskRay]

This patch doesn't add any uses of this template, but that is coming in a subsequent patch.

Usage link is usually directly mentioned to justify an addition to ADT/ or Support/.

[beanz]

In D122079#3401411, @MaskRay wrote:

Does the template compile to efficient code? lld/ELF has a utility which seems pretty efficient https://reviews.llvm.org/D112385#3084969

With a constant value it will fold to true/false, with non-constant values it optimizes to minimal range checks.

In D122079#3401413, @MaskRay wrote:

Usage link is usually directly mentioned to justify an addition to ADT/ or Support/.

This is part of a commit stack. The next commit in the stack which uses it is https://reviews.llvm.org/D122081. :)

[kuhar]

In D122079#3401001, @beanz wrote:

In D122079#3396156, @kuhar wrote:

2. This could be made constexpr if we wanted.

I had another place that I wanted to use this in clang where the input parameter isn't constant.

constexpr works with both constant-evaluated contexts and runtime calls.

5. Since this function is not constexpr now, how about we added an overload to is_contained accepting an initializer list as the second element, e.g.: is_constained(MyEnum::A, {MyEnum::A, MyEnum::B, MyEnum::C})?

I realize this is probably a bit overkill, but isInEnumSet<Numbers, One, Two, Three, Four, Five>(Val) will actually optimize down to roughly if( Val >= One && Val <= Five) (assuming sequential values), and that really only works reliably with the template parameter unrolling.

I've checked and it seems to work just as well when passing in an array. With initializer_list, there are still some branches left. See https://godbolt.org/z/o7hKnKen5.

Overall, I'd lean towards the array or initializer_list version (either re-using is_contained or introducing a new name like is_in) to keep things more familiar and avoid recursion.

[beanz]

In D122079#3401426, @kuhar wrote:

constexpr works with both constant-evaluated contexts and runtime calls.

Fair point.

I've checked and it seems to work just as well when passing in an array. With initializer_list, there are still some branches left. See https://godbolt.org/z/o7hKnKen5.

Ah! I had tried using this with the existing is_contained definition, and it wasn’t folding. I think it was the std::find call, I can adjust.

Overall, I'd lean towards the array or initializer_list version (either re-using is_contained or introducing a new name like is_in to keep things more familiar and avoid recursion.

Makes sense to me. Will rework tomorrow.

Thank you!

[beanz]

Updating to be a specialization on is_contained rather than a standalone thing.

[kuhar]

Could you also add some tests that make sure this can be constant-evaluated? (e.g., with static_assert)

Also, would be good to have a couple of tests with non-enum types (e.g., some trivial type like int and some class with a copy constructor etc.)

llvm/unittests/ADT/STLExtrasTest.cpp

976

Can you add an extra test case with an empty set of things to match against?

979

These should be EXPECT_TRUE.

ASSERT_TRUE are for when you can't continue executing a test after a failure

979

Also, put the call directly inside the check: EXPECT_TRUE(is_contained(...)).

[kuhar]

llvm/include/llvm/ADT/STLExtras.h

1661

This function arguments are backwards compared to the other overloads. Could we keep it consistent?

[beanz]

Updating based on feedback from @kuhar. Thank you!

[kuhar]

LGTM, thanks for the fixes.

[kuhar]

llvm/unittests/ADT/STLExtrasTest.cpp

985–989

nit: make sure to run this through clang-format if you haven't already. It looks to me like some spaces might be missing.

[kuhar]

llvm/include/llvm/ADT/STLExtras.h

1661

nit: variable names should be capitalized in this function

llvm/include/llvm/ADT/STLExtras.h

 
 /// Wrapper function around std::find to detect if an element exists
 /// in a container.
 template <typename R, typename E>
 bool is_contained(R &&Range, const E &Element) {
   return std::find(adl_begin(Range), adl_end(Range), Element) != adl_end(Range);
 }
 
+template <typename T>
+constexpr bool is_contained(std::initializer_list<T> Set, T Value) {
+  // TODO: Use std::find when we switch to C++20.
+  for (T V : Set)
+    if (V == Value)
+      return true;
+  return false;
+}
+
 /// Wrapper function around std::is_sorted to check if elements in a range \p R
 /// are sorted with respect to a comparator \p C.
 template <typename R, typename Compare> bool is_sorted(R &&Range, Compare C) {
   return std::is_sorted(adl_begin(Range), adl_end(Range), C);
 }
 
 /// Wrapper function around std::is_sorted to check if elements in a range \p R
 /// are sorted in non-descending order.

llvm/unittests/ADT/STLExtrasTest.cpp

TEST(STLExtrasTest, TypeAtIndex) {
   EXPECT_TRUE(
       (std::is_same<float, llvm::TypeAtIndex<1, int, float, double>>::value));
   EXPECT_TRUE(
       (std::is_same<float, llvm::TypeAtIndex<1, int, float, double>>::value));
   EXPECT_TRUE(
       (std::is_same<double, llvm::TypeAtIndex<2, int, float, double>>::value));
 }
 
+enum Doggos {
+  Floofer,
+  Woofer,
+  SubWoofer,
+  Pupper,
+  Pupperino,
+  Longboi,
+};
+
+TEST(STLExtrasTest, IsContainedInitializerList) {
+  EXPECT_TRUE(is_contained({Woofer, SubWoofer}, Woofer));
+  EXPECT_TRUE(is_contained({Woofer, SubWoofer}, SubWoofer));
+  EXPECT_FALSE(is_contained({Woofer, SubWoofer}, Pupper));
+  EXPECT_FALSE(is_contained({}, Longboi));
+
+  static_assert(is_contained({Woofer, SubWoofer}, SubWoofer), "SubWoofer!");
+  static_assert(!is_contained({Woofer, SubWoofer}, Pupper), "Missing Pupper!");
+
+  EXPECT_TRUE(is_contained({1, 2, 3, 4}, 3));
+  EXPECT_FALSE(is_contained({1, 2, 3, 4}, 5));
+
+  static_assert(is_contained({1, 2, 3, 4}, 3), "It's there!");
+  static_assert(!is_contained({1, 2, 3, 4}, 5), "It's not there :(");
+}
+
 } // namespace