[ADT] Add new type traits for type pack indexes

[scott.linder]

Summary

Similar versions of these already exist, this effectively just just
factors them out into STLExtras. I plan to use these in future patches.

[scott.linder]

Moved tests to STLExtrasTest.cpp from STLShimsTest.cpp

[dblaikie]

Are there (future) STL equivalents of TypesAreDistinct or FirsntIndexOfType?

llvm/include/llvm/ADT/STLExtras.h

151–154

Could this be replaced with:

return llvm::find(Matches, true) - std::begin(Matches);

or something like that?
(similarly below in "AreTypesDistinct")?

Hmm, what's the purpose of the first element of the array being 'false', and then iterating from the second element and subtracting one from the index before returning?

Oh, that's to support the zero-length case? Fair enough. I don't mind either way, but maybe it'd be simpler/more obvious if that were done via specialization? - oh, what happens if you put the buffer value at the end rather than the beginning. In this algorithm you could put "true" at the end (and remove "false" from the start) and then it'd return 1 when sizeof...(Ts) is zero?

163

Any concerns about the quadratic complexity here? Any more efficient way to write this, maybe? (what's the libc++ equivalent implementation look like, I wonder?)

[scott.linder]

In D100672#2696022, @dblaikie wrote:

Are there (future) STL equivalents of TypesAreDistinct or FirsntIndexOfType?

There aren't, as far as I'm aware. I didn't do an exhaustive search, but at the very least I don't see anything equivalent in <type_traits>

llvm/include/llvm/ADT/STLExtras.h

151–154

Sure, I think llvm::find would need to be constexpr then? I assume that will ripple through some other things in STLExtras.h, so maybe I should do a pass to add constexpr wherever possible in STLExtras.h? Or in this case would just marking what I need be better?

Putting the extra element at the end and having it defined to return a size >= sizeof...(Ts) seems reasonable, especially as it is just a detail function. I'll make that change, thank you!

163

I couldn't think of any in a constexpr context, but there very well may be.

My hope is that this is only needed once per instantiation of a type that cares about this property. I.e. once you assert that IntrusiveVariant<Foo, Bar, Baz> has distinct alternative types, I believe the compiler does not need to re-check that assertion. Incidentally we previously didn't assert this at all PointerUnion, although it seems to be a requirement?

[dblaikie]

llvm/include/llvm/ADT/STLExtras.h

151–154

oh, sure if there's stuff that needs to be constexpr and isn't - if it's not a ton of stuff, can probably include it in this patch (adding the constexpr keyword as needed) - if it's a lot, maybe a separate preliminary patch. (I probably wouldn't bother adding unit tests for constexpr-ness, but treat it as a quasi-NFC change). (if you want to include only what's needed in this patch and also separately submit a patch to constexpr the rest (then maybe some testing may be needed, to ensure all the implementation details got constexpr'd correctly))

[scott.linder]

llvm/include/llvm/ADT/STLExtras.h

151–154

It looks like std::find isn't constexpr until C++20, and llvm::find just wraps it. I think I could change llvm::find to have a standalone implementation and make it constexpr, but I don't know how often this will be useful. Do you have a preference on how I approach this?

[dblaikie]

Sounds good - thanks!

llvm/include/llvm/ADT/STLExtras.h

151–154

Nah, that's OK. Whichever's cool - making our llvm::find constexpr would be nice (separate patch, though) - but equally if that's beyond what you want to do here - a comment saying "use find once it's constexpr/in C++20" or something like that.

[stella.stamenova]

This broke some windows bots:

https://lab.llvm.org/buildbot/#/builders/13/builds/8180
https://lab.llvm.org/buildbot/#/builders/83/builds/6640

[scott.linder]

In D100672#2764758, @stella.stamenova wrote:

This broke some windows bots:

https://lab.llvm.org/buildbot/#/builders/13/builds/8180
https://lab.llvm.org/buildbot/#/builders/83/builds/6640

Thank you for reverting, and for the links to the builds! I'll take a look

[scott.linder]

I also neglected to move the extra element to the end of the array, so I'll make that change when I fix the build failure on Windows

[scott.linder]

This seems like a bug in parameter pack expansion in older versions of MSVC, compare 19.10 https://godbolt.org/z/TMd3K8WoK with 19.14 https://godbolt.org/z/9c9TT8bnb

@stella.stamenova is there any possibility the build bots could be updated to the latest MSVC 2017 update? https://llvm.org/docs/GettingStartedVS.html#software says "Visual Studio 2017 or higher, with the latest Update installed", but I could also see us wanting to support any VS 2017 release if possible.

If we want to support all updates of VS 2017 I can just substitute in the old definition of llvm::TypeIndex in place of the new llvm::FirstIndexOfType, but I might have to think more about how to work around this in llvm::TypesAreDistinct

[scott.linder]

Replace constexpr functions with recursively defined templates, working around
an MSVC bug.

[dblaikie]

In D100672#2766442, @scott.linder wrote:

This seems like a bug in parameter pack expansion in older versions of MSVC, compare 19.10 https://godbolt.org/z/TMd3K8WoK with 19.14 https://godbolt.org/z/9c9TT8bnb

@stella.stamenova is there any possibility the build bots could be updated to the latest MSVC 2017 update? https://llvm.org/docs/GettingStartedVS.html#software says "Visual Studio 2017 or higher, with the latest Update installed", but I could also see us wanting to support any VS 2017 release if possible.

If we want to support all updates of VS 2017 I can just substitute in the old definition of llvm::TypeIndex in place of the new llvm::FirstIndexOfType, but I might have to think more about how to work around this in llvm::TypesAreDistinct

I'd generally be happy to stick with the original requirement. @stella.stamenova - any chance you could update the bot(s) here?

[stella.stamenova]

In D100672#2767612, @dblaikie wrote:

In D100672#2766442, @scott.linder wrote:

This seems like a bug in parameter pack expansion in older versions of MSVC, compare 19.10 https://godbolt.org/z/TMd3K8WoK with 19.14 https://godbolt.org/z/9c9TT8bnb

@stella.stamenova is there any possibility the build bots could be updated to the latest MSVC 2017 update? https://llvm.org/docs/GettingStartedVS.html#software says "Visual Studio 2017 or higher, with the latest Update installed", but I could also see us wanting to support any VS 2017 release if possible.

If we want to support all updates of VS 2017 I can just substitute in the old definition of llvm::TypeIndex in place of the new llvm::FirstIndexOfType, but I might have to think more about how to work around this in llvm::TypesAreDistinct

I'd generally be happy to stick with the original requirement. @stella.stamenova - any chance you could update the bot(s) here?

I can update these two buildbots (mlir and lldb). I am not sure whether there are other Windows buildbots that were affected and if they can be updated since we don't own them. I'll let you know once they are updated.

[stella.stamenova]

@dblaikie @scott.linder I updated VS on both the mlir and lldb windows buildbots (from 15.9.30 to 15.9.36), but this update does not have an update to the compiler and indeed the compiler version was already `Microsoft (R) C/C++ Optimizing Compiler Version 19.16.27045```. You can see from the logs of the broken builds as well:

-- The C compiler identification is MSVC 19.16.27045.0
-- The CXX compiler identification is MSVC 19.16.27045.0

I think the issue is rather C++ 14 vs. C++ 17. It is my understanding that C++ 14 is required for LLVM, but not C++ 17, is that the case?

[scott.linder]

In D100672#2768909, @stella.stamenova wrote:

@dblaikie @scott.linder I updated VS on both the mlir and lldb windows buildbots (from 15.9.30 to 15.9.36), but this update does not have an update to the compiler and indeed the compiler version was already `Microsoft (R) C/C++ Optimizing Compiler Version 19.16.27045```. You can see from the logs of the broken builds as well:

-- The C compiler identification is MSVC 19.16.27045.0
-- The CXX compiler identification is MSVC 19.16.27045.0

I think the issue is rather C++ 14 vs. C++ 17. It is my understanding that C++ 14 is required for LLVM, but not C++ 17, is that the case?

That's my understanding too, but even adding /std:c++14 to the command-line doesn't cause the failure, at least on godbolt: https://godbolt.org/z/zPTGjMsKa

I'm not sure what to make of it now, and I'm not particularly familiar with Windows or MSVC. I'm still amenable to changing the code, but I also fear the changes I made won't actually fix the issue as I am only testing on godbolt. Is there any shortcut to testing with the Windows buildbots? Or do I have to install Windows somewhere and try to reproduce it?

[stella.stamenova]

I'm not sure what to make of it now, and I'm not particularly familiar with Windows or MSVC. I'm still amenable to changing the code, but I also fear the changes I made won't actually fix the issue as I am only testing on godbolt. Is there any shortcut to testing with the Windows buildbots? Or do I have to install Windows somewhere and try to reproduce it?

There is no way to test on the official buildbots, you'd have to install Windows. If you have a change that's ready to test, I could run it locally for you.

[scott.linder]

In D100672#2769781, @stella.stamenova wrote:

I'm not sure what to make of it now, and I'm not particularly familiar with Windows or MSVC. I'm still amenable to changing the code, but I also fear the changes I made won't actually fix the issue as I am only testing on godbolt. Is there any shortcut to testing with the Windows buildbots? Or do I have to install Windows somewhere and try to reproduce it?

There is no way to test on the official buildbots, you'd have to install Windows. If you have a change that's ready to test, I could run it locally for you.

Yes, if you could test a change for me I would greatly appreciate it! It would save me a lot of headache

The current diff of this review is what I believe should work on any version of MSVC with /std:c++14

Could you run test the current diff and let me know the results? Thank you!

[scott.linder]

Rebase

[scott.linder]

Rebase and fix uses in PointerUnion.h

[scott.linder]

@stella.stamenova do you still think you'd be able to test this before it lands, to see if the current version of the patch works on the MSVC build bots?

If not, would it be reasonable for me to land it and revert if it causes issues?

[scott.linder]

In D100672#2767612, @dblaikie wrote:

In D100672#2766442, @scott.linder wrote:

This seems like a bug in parameter pack expansion in older versions of MSVC, compare 19.10 https://godbolt.org/z/TMd3K8WoK with 19.14 https://godbolt.org/z/9c9TT8bnb

@stella.stamenova is there any possibility the build bots could be updated to the latest MSVC 2017 update? https://llvm.org/docs/GettingStartedVS.html#software says "Visual Studio 2017 or higher, with the latest Update installed", but I could also see us wanting to support any VS 2017 release if possible.

If we want to support all updates of VS 2017 I can just substitute in the old definition of llvm::TypeIndex in place of the new llvm::FirstIndexOfType, but I might have to think more about how to work around this in llvm::TypesAreDistinct

I'd generally be happy to stick with the original requirement. @stella.stamenova - any chance you could update the bot(s) here?

Would you mind taking a look at the current diff and seeing if it is acceptable? I am fairly confident this will work with any reasonably modern MSVC, and I don't think there is a substantial hit to readability. There may be some compile-time performance cost, but I don't know how to quantify it.

Edit - meant to direct this to @dblaikie, but of course I would also appreciate feedback from anyone!

[scott.linder]

Ping, @dblaikie are you OK with the patch as-is? I think it is likely not worth the effort of tracking down what MSVC configurations will accept the constexpr version.

[dblaikie]

In D100672#3119829, @scott.linder wrote:

Ping, @dblaikie are you OK with the patch as-is? I think it is likely not worth the effort of tracking down what MSVC configurations will accept the constexpr version.

Fair enough. I really don't like to workaround unknown issues (ends up with a form of "fear based programming" - "let's not write code that looks like that because there are issues /somewhere/ in there" - haunted graveyards ( https://www.usenix.org/sites/default/files/conference/protected-files/srecon17americas_slides_reese.pdf ) , etc) - so I think there's significant value in figuring out exactly what the limitations are/what's being worked around - but I won't insist on it.

[scott.linder]

In D100672#3119835, @dblaikie wrote:

In D100672#3119829, @scott.linder wrote:

Ping, @dblaikie are you OK with the patch as-is? I think it is likely not worth the effort of tracking down what MSVC configurations will accept the constexpr version.

Fair enough. I really don't like to workaround unknown issues (ends up with a form of "fear based programming" - "let's not write code that looks like that because there are issues /somewhere/ in there" - haunted graveyards ( https://www.usenix.org/sites/default/files/conference/protected-files/srecon17americas_slides_reese.pdf ) , etc) - so I think there's significant value in figuring out exactly what the limitations are/what's being worked around - but I won't insist on it.

I wholeheartedly agree, but I think it will require (trivially) reproducible developer builds for all supported configurations to make that possible. As it stands, I can't access the builds which reproduce the failure, and my attempts at reproducing it with what I do have access to haven't amounted to anything :(

Thank you for the leeway, I won't make a habit of asking for it

[scott.linder]

Rebase

llvm/include/llvm/ADT/PointerUnion.h

namespace pointer_union_detail {
   constexpr int bitsRequired(unsigned n) {
     return n > 1 ? 1 + bitsRequired((n + 1) / 2) : 0;
   }
 
   template <typename... Ts> constexpr int lowBitsAvailable() {
     return std::min<int>({PointerLikeTypeTraits<Ts>::NumLowBitsAvailable...});
   }
 
-  /// Find the index of a type in a list of types. TypeIndex<T, Us...>::Index
-  /// is the index of T in Us, or sizeof...(Us) if T does not appear in the
-  /// list.
-  template <typename T, typename ...Us> struct TypeIndex;
-  template <typename T, typename ...Us> struct TypeIndex<T, T, Us...> {
-    static constexpr int Index = 0;
-  };
-  template <typename T, typename U, typename... Us>
-  struct TypeIndex<T, U, Us...> {
-    static constexpr int Index = 1 + TypeIndex<T, Us...>::Index;
-  };
-  template <typename T> struct TypeIndex<T> {
-    static constexpr int Index = 0;
-  };
-
   /// Find the first type in a list of types.
   template <typename T, typename...> struct GetFirstType {
     using type = T;
   };
 
   /// Provide PointerLikeTypeTraits for void* that is used by PointerUnion
   /// for the template arguments.
   template <typename ...PTs> class PointerUnionUIntTraits {

 ///    P = (int*)0;
 ///    printf("%d %d", P.is<int*>(), P.is<float*>());  // prints "1 0"
 ///    X = P.get<int*>();     // ok.
 ///    Y = P.get<float*>();   // runtime assertion failure.
 ///    Z = P.get<double*>();  // compile time failure.
 ///    P = (float*)0;
 ///    Y = P.get<float*>();   // ok.
 ///    X = P.get<int*>();     // runtime assertion failure.
+///    PointerUnion<int*, int*> Q; // compile time failure.
 template <typename... PTs>
 class PointerUnion
     : public pointer_union_detail::PointerUnionMembers<
           PointerUnion<PTs...>,
           PointerIntPair<
               void *, pointer_union_detail::bitsRequired(sizeof...(PTs)), int,
               pointer_union_detail::PointerUnionUIntTraits<PTs...>>,
           0, PTs...> {
+  static_assert(TypesAreDistinct<PTs...>(),
+                "PointerUnion alternative types cannot be repeated");
   // The first type is special because we want to directly cast a pointer to a
   // default-initialized union to a pointer to the first type. But we don't
   // want PointerUnion to be a 'template <typename First, typename ...Rest>'
   // because it's much more convenient to have a name for the whole pack. So
   // split off the first type here.
-  using First = typename pointer_union_detail::GetFirstType<PTs...>::type;
+  using First = TypeAtIndex<0, PTs...>;
   using Base = typename PointerUnion::PointerUnionMembers;
 
 public:
   PointerUnion() = default;
 
   PointerUnion(std::nullptr_t) : PointerUnion() {}
   using Base::Base;
 
   /// Test if the pointer held in the union is null, regardless of
   /// which type it is.
   bool isNull() const { return !this->Val.getPointer(); }
 
   explicit operator bool() const { return !isNull(); }
 
   /// Test if the Union currently holds the type matching T.
   template <typename T> bool is() const {
-    constexpr int Index = pointer_union_detail::TypeIndex<T, PTs...>::Index;
-    static_assert(Index < sizeof...(PTs),
-                  "PointerUnion::is<T> given type not in the union");
-    return this->Val.getInt() == Index;
+    return this->Val.getInt() == FirstIndexOfType<T, PTs...>{};
   }
 
   /// Returns the value of the specified pointer type.
   ///
   /// If the specified pointer type is incorrect, assert.
   template <typename T> T get() const {
     assert(is<T>() && "Invalid accessor called");
     return PointerLikeTypeTraits<T>::getFromVoidPointer(this->Val.getPointer());

llvm/include/llvm/ADT/STLExtras.h

struct function_traits<ReturnType (*)(Args...), false> {
   template <size_t i>
   using arg_t = typename std::tuple_element<i, std::tuple<Args...>>::type;
 };
 /// Overload for non-class function type references.
 template <typename ReturnType, typename... Args>
 struct function_traits<ReturnType (&)(Args...), false>
     : public function_traits<ReturnType (*)(Args...)> {};
 
+namespace detail {
+template <typename T, typename... Ts>
+constexpr size_t getFirstIndexOfTypeImpl() {
+  constexpr bool Matches[] = {false, std::is_same<T, Ts>{}...};
+  for (size_t I = 1; I <= sizeof...(Ts); ++I)
+    if (Matches[I])
+      return I - 1;
+  return sizeof...(Ts);
+}
+template <typename T, typename... Ts> constexpr size_t getFirstIndexOfType() {
+  constexpr size_t Index = getFirstIndexOfTypeImpl<T, Ts...>();
+  static_assert(Index != sizeof...(Ts),
+                "type T is not present in type pack Ts");
+  return Index;
+}
+template <typename... Ts> static constexpr bool areTypesDistinct() {
+  constexpr size_t IndexOf[] = {0, getFirstIndexOfType<Ts, Ts...>()...};
+  for (size_t I = 1; I <= sizeof...(Ts); ++I)
+    if (I - 1 != IndexOf[I])
+      return false;
+  return true;
+}
+} // namespace detail
+
+/// Determine if all types in Ts are distinct.
+///
+/// Useful to statically assert when Ts is intended to describe a non-multi set
+/// of types.
+template <typename... Ts>
+using TypesAreDistinct =
+    std::integral_constant<bool, detail::areTypesDistinct<Ts...>()>;
+
+/// Find the first index where a type appears in a list of types.
+///
+/// FirstIndexOfType<T, Ts...>::value is the first index of T in Ts.
+///
+/// Typically only meaningful when it is otherwise statically known that the
+/// type pack has no duplicate types. This should be guaranteed explicitly with
+/// static_assert(TypesAreDistinct<Ts...>{}).
+///
+/// It is a compile-time error to instantiate when T is not present in Ts, i.e.
+/// if is_one_of<T, Ts...>::value is false.
+template <typename T, typename... Ts>
+using FirstIndexOfType =
+    std::integral_constant<size_t, detail::getFirstIndexOfType<T, Ts...>()>;
+
+/// Find the type at a given index in a list of types.
+///
+/// TypeAtIndex<I, Ts...> is the type at index I in Ts.
+template <size_t I, typename... Ts>
+using TypeAtIndex = std::tuple_element_t<I, std::tuple<Ts...>>;
+
 //===----------------------------------------------------------------------===//
 //     Extra additions to <functional>
 //===----------------------------------------------------------------------===//
 
 template <class Ty> struct identity {
   using argument_type = Ty;
 
   Ty &operator()(Ty &self) const {

llvm/unittests/ADT/STLShimsTest.cpp

#define REMOVE_CVREF_CASE(FROM, TO)                                            \
   REMOVE_CVREF_CASE(const volatile int &, int);
   REMOVE_CVREF_CASE(int *, int *);
   REMOVE_CVREF_CASE(int *const, int *);
   REMOVE_CVREF_CASE(const int *, const int *);
   REMOVE_CVREF_CASE(int *&, int *);
 #undef REMOVE_CVREF_CASE
 }
 
+TEST(STLShims, TypesAreDistinct) {
+  EXPECT_TRUE((llvm::TypesAreDistinct<>::value));
+  EXPECT_TRUE((llvm::TypesAreDistinct<int>::value));
+  EXPECT_FALSE((llvm::TypesAreDistinct<int, int>::value));
+  EXPECT_TRUE((llvm::TypesAreDistinct<int, float>::value));
+  EXPECT_FALSE((llvm::TypesAreDistinct<int, float, int>::value));
+  EXPECT_TRUE((llvm::TypesAreDistinct<int, float, double>::value));
+  EXPECT_FALSE((llvm::TypesAreDistinct<int, float, double, float>::value));
+  EXPECT_TRUE((llvm::TypesAreDistinct<int, int *>::value));
+  EXPECT_TRUE((llvm::TypesAreDistinct<int, int &>::value));
+  EXPECT_TRUE((llvm::TypesAreDistinct<int, int &&>::value));
+  EXPECT_TRUE((llvm::TypesAreDistinct<int, const int>::value));
+}
+
+TEST(STLShims, FirstIndexOfType) {
+  EXPECT_EQ((llvm::FirstIndexOfType<int, int>::value), 0u);
+  EXPECT_EQ((llvm::FirstIndexOfType<int, int, int>::value), 0u);
+  EXPECT_EQ((llvm::FirstIndexOfType<int, float, int>::value), 1u);
+  EXPECT_EQ((llvm::FirstIndexOfType<int const *, float, int, int const *,
+                                    const int>::value),
+            2u);
+}
+
+TEST(STLShims, TypeAtIndex) {
+  EXPECT_TRUE((std::is_same<int, llvm::TypeAtIndex<0, int>>::value));
+  EXPECT_TRUE((std::is_same<int, llvm::TypeAtIndex<0, int, float>>::value));
+  EXPECT_TRUE((std::is_same<float, llvm::TypeAtIndex<1, int, float>>::value));
+  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));
+}
+
 } // namespace