[ADT] Remove O(1) requirement to range passed to llvm::size

[abrachet]

Summary

None of the other wrappers around the algorithms have this requirement that the iterators should be random access, llvm::size shouldn't either.

[jhenderson]

How many places use this and in what context? I'm conscious of std::size which becomes available in C++17, and the natural implementation of that is to simply use the standard .size() method on a container (see https://en.cppreference.com/w/cpp/iterator/size). It also does something else for fixed-sized arrays, but this particular version doesn't work for that. Finally, why do you need llvm::size() instead of a container.size() method?

[MaskRay]

In D65788#1616378, @jhenderson wrote:

How many places use this and in what context? I'm conscious of std::size which becomes available in C++17, and the natural implementation of that is to simply use the standard .size() method on a container (see https://en.cppreference.com/w/cpp/iterator/size). It also does something else for fixed-sized arrays, but this particular version doesn't work for that. Finally, why do you need llvm::size() instead of a container.size() method?

My language server says there are 5 references:

https://github.com/llvm/llvm-project/blob/1177bc597d5f1bab4f4ed79b2fe88ae1d2461c39/llvm/lib/CodeGen/GlobalISel/RegBankSelect.cpp#L138
https://github.com/llvm/llvm-project/blob/1177bc597d5f1bab4f4ed79b2fe88ae1d2461c39/llvm/lib/Analysis/LazyCallGraph.cpp#L1288
https://github.com/llvm/llvm-project/blob/1177bc597d5f1bab4f4ed79b2fe88ae1d2461c39/llvm/lib/Analysis/LazyCallGraph.cpp#L1754 (I'll delete this one)
https://github.com/llvm/llvm-project/blob/1177bc597d5f1bab4f4ed79b2fe88ae1d2461c39/llvm/lib/Analysis/LazyCallGraph.cpp#L1762 (I'll delete this one)
https://github.com/llvm/llvm-project/blob/1177bc597d5f1bab4f4ed79b2fe88ae1d2461c39/llvm/lib/Transforms/Scalar/GVNHoist.cpp#L580

After deleting the 2 references, the remaining 3 are all iterator_range<T>. is_splat, which calls size, has other 4 references.

CC @vsk who implemented llvm::size in D46976

[abrachet]

In D65788#1616378, @jhenderson wrote:

How many places use this and in what context? I'm conscious of std::size which becomes available in C++17, and the natural implementation of that is to simply use the standard .size() method on a container (see https://en.cppreference.com/w/cpp/iterator/size). It also does something else for fixed-sized arrays, but this particular version doesn't work for that. Finally, why do you need llvm::size() instead of a container.size() method?

I was also curious about the use of llvm::size() instead of the containers size method, seems like ranges which can be computed in O(1) are almost always going to be in containers which have a size method. My particular use is with the iterators in ObjectFile::sections(), symbols() etc. which are not in a container with a size method and may not even be contiguous in memory.

I've added @dblaikie as a subscriber as it seems from D46976 it was his idea to give this restriction to llvm::size().

[dblaikie]

In D65788#1616674, @abrachet wrote:

In D65788#1616378, @jhenderson wrote:

How many places use this and in what context? I'm conscious of std::size which becomes available in C++17, and the natural implementation of that is to simply use the standard .size() method on a container (see https://en.cppreference.com/w/cpp/iterator/size). It also does something else for fixed-sized arrays, but this particular version doesn't work for that. Finally, why do you need llvm::size() instead of a container.size() method?

I was also curious about the use of llvm::size() instead of the containers size method, seems like ranges which can be computed in O(1) are almost always going to be in containers which have a size method. My particular use is with the iterators in ObjectFile::sections(), symbols() etc. which are not in a container with a size method and may not even be contiguous in memory.

I've added @dblaikie as a subscriber as it seems from D46976 it was his idea to give this restriction to llvm::size().

I'm still inclined to stick with my original sentiment, that this shouldn't be usable on non-constant-time size operations.

Changing llvm::size to match C++20 is going to move the problem - then we'd need to define a "size()" member of llvm::iterator_range & have the same debate there about whether it should be limited to O(1) cases or not. (it /sounds/ like the C++20 ranges will have such a limit but I'm not entirely sure/familiar with them)

My preference would be to use std::distance(begin, end) for O(N) size computations to make it clear that they're "interesting", as I mentioned in the original review/discussion.

[abrachet]

My preference would be to use std::distance(begin, end) for O(N) size computations to make it clear that they're "interesting", as I mentioned in the original review/discussion.

This makes a lot of sense to me.

[vsk]

+1 to @dblaikie’s comment. I don’t want to encourage folks to write code the slow/wrong way by making that way ergonomic. D54686 was an attempt to move away from that.

llvm/include/llvm/ADT/STLExtras.h

 /// deletes the second elements and then clears the container.
 template<typename Container>
 void DeleteContainerSeconds(Container &C) {
   for (auto &V : C)
     delete V.second;
   C.clear();
 }
 
-/// Get the size of a range. This is a wrapper function around std::distance
-/// which is only enabled when the operation is O(1).
+/// Provide wrappers to std::distance which take ranges instead of having to
+/// pass begin/end explicitly.
 template <typename R>
-auto size(R &&Range, typename std::enable_if<
-                         std::is_same<typename std::iterator_traits<decltype(
-                                          Range.begin())>::iterator_category,
-                                      std::random_access_iterator_tag>::value,
-                         void>::type * = nullptr)
-    -> decltype(std::distance(Range.begin(), Range.end())) {
+auto size(R &&Range) -> decltype(std::distance(Range.begin(), Range.end())) {
   return std::distance(Range.begin(), Range.end());
 }
 
 /// Provide wrappers to std::for_each which take ranges instead of having to
 /// pass begin/end explicitly.
 template <typename R, typename UnaryPredicate>
 UnaryPredicate for_each(R &&Range, UnaryPredicate P) {
   return std::for_each(adl_begin(Range), adl_end(Range), P);