[ADT] Allow `llvm::enumerate` to enumerate over multiple ranges

[kuhar]

Summary

This does not work by a mere composition of enumerate and zip_equal,
because C++17 does not allow for recursive expansion of structured
bindings.

This implementation uses zippy to manage the iteratees and adds the
stream of indices as the first zipped range. Because we have an upfront
assertion that all input ranges are of the same length, we only need to
check if the second range has ended during iteration.

As a consequence of using zippy, enumerate will now follow the
reference and lifetime semantics of the zip* family of functions. The
main difference is that enumerate exposes each tuple of references
through a new tuple-like type enumerate_result, with the familiar
.index() and .value() member functions.

Because the enumerate_result returned on dereference is a
temporary, enumeration result can no longer be used through an
lvalue ref.

[kuhar]

Clean up

[zero9178]

Implementation makes sense to me and matches my expectation. Wouldn't really know how to do this any simpler than the current state myself to be honest.

llvm/include/llvm/ADT/STLExtras.h

29

Watch out, this is not a standard C++ header but an implementation detail from libstdc++

2222

Any reason to explicitly default these? IIRC doing so even deletes the move constructors and move assignment

2237

Am I correct that these casts here are only necassery since zip only ever uses the ranges const iterator? I don't see any other reasons since these are otherwise noop casts.
Fixing zip would also "fix" needing the const below in the test case on Range. Possibly out of scope for this patch.

2240

I believe you meant this to be range_reference_tuple instead of value_reference_tuple, in which case you can just directly do return get_values(...));

Otherwise this 1) does not compile if calling .value() on the result with more than one range 2) would otherwise return a tuple with the value returned by index() in the first position.

Please add a test case for this case as well.

2249

ditto with copy constructor here

llvm/unittests/ADT/STLExtrasTest.cpp

168

Can you elaborate what you mean with const reference here? As far as I can tell, from all the types involved in the ranged for below none of them are const references.

[kuhar]

llvm/include/llvm/ADT/STLExtras.h

29

Gah, clangd end up pulling in funny includes sometimes...

2237

Exactly. I've struggled with const references in my implementation, I'll try your suggestion to see if it simplifies things.

llvm/unittests/ADT/STLExtrasTest.cpp

168

Thanks, the comment is out of sync with the code.

[kuhar]

Address comments from @zero9178

[dblaikie]

C++17 does not allow for recursive expansion of structured bindings.

Could we address this issue more directly, perhaps - like having a "flatten" (maybe it only goes one level deep - a range over pair or tuple and any of the elements of that tuple that are themselves tuples would be flattened into one big tuple (but only that one layer deep - could use the wrapper multiple times if you wanted to flatten even deeper))?

[kuhar]

In D144503#4142656, @dblaikie wrote:

C++17 does not allow for recursive expansion of structured bindings.

Could we address this issue more directly, perhaps - like having a "flatten" (maybe it only goes one level deep - a range over pair or tuple and any of the elements of that tuple that are themselves tuples would be flattened into one big tuple (but only that one layer deep - could use the wrapper multiple times if you wanted to flatten even deeper))?

Can you give an example? I don't see how this would work. My starting point is that I would like to enable this: for (auto [Idx, X, Y, Z] : ...(Xs, Ys, Zs)...).

If we tried to compose enumerate and zip_equal, we would end up with flatten used like this: for (auto [Idx, X, Y, Z] : flatten(enumerate(zip_equal(Xs, Ys, Zs)))). Here flatten would have to a map_range-style range adaptor, and I think we would lose it.index()?

[dblaikie]

In D144503#4142807, @kuhar wrote:

In D144503#4142656, @dblaikie wrote:

C++17 does not allow for recursive expansion of structured bindings.

Could we address this issue more directly, perhaps - like having a "flatten" (maybe it only goes one level deep - a range over pair or tuple and any of the elements of that tuple that are themselves tuples would be flattened into one big tuple (but only that one layer deep - could use the wrapper multiple times if you wanted to flatten even deeper))?

Can you give an example? I don't see how this would work. My starting point is that I would like to enable this: for (auto [Idx, X, Y, Z] : ...(Xs, Ys, Zs)...).

If we tried to compose enumerate and zip_equal, we would end up with flatten used like this: for (auto [Idx, X, Y, Z] : flatten(enumerate(zip_equal(Xs, Ys, Zs)))). Here flatten would have to a map_range-style range adaptor, and I think we would lose it.index()?

Yep, something along those lines - yep, would lose a nice spelling for index on the iterator (it'd just be a tuple) - but given structured bindings, do people much want/need that naming anyway?

[kuhar]

In D144503#4142824, @dblaikie wrote:

In D144503#4142807, @kuhar wrote:

Can you give an example? I don't see how this would work. My starting point is that I would like to enable this: for (auto [Idx, X, Y, Z] : ...(Xs, Ys, Zs)...).

If we tried to compose enumerate and zip_equal, we would end up with flatten used like this: for (auto [Idx, X, Y, Z] : flatten(enumerate(zip_equal(Xs, Ys, Zs)))). Here flatten would have to a map_range-style range adaptor, and I think we would lose it.index()?

Yep, something along those lines - yep, would lose a nice spelling for index on the iterator (it'd just be a tuple) - but given structured bindings, do people much want/need that naming anyway?

I see. I think in this specific case the ergonomics make this work in real world. We have a considerable amount of code in MLIR and IREE that iterates over multidimensional stuff in lockstep, and it's nice to have a concise and safe way to manage that. I don't think that flatten achieves that given the total amount of nesting. Instead, one could unpack the values in the first statement inside the loop like so:

for (auto [Idx, Val] : enumerate(zip_equal(...))) {
  auto [X, Y, Z] = Val.value()

Another issue I see is unintentionally unpacking a single element in generic code -- a single range can contain tuple values, and I don't think we can tell this apart from zip(...) without checking the range/iterator type.

[dblaikie]

In D144503#4142911, @kuhar wrote:

In D144503#4142824, @dblaikie wrote:

In D144503#4142807, @kuhar wrote:

Can you give an example? I don't see how this would work. My starting point is that I would like to enable this: for (auto [Idx, X, Y, Z] : ...(Xs, Ys, Zs)...).

If we tried to compose enumerate and zip_equal, we would end up with flatten used like this: for (auto [Idx, X, Y, Z] : flatten(enumerate(zip_equal(Xs, Ys, Zs)))). Here flatten would have to a map_range-style range adaptor, and I think we would lose it.index()?

Yep, something along those lines - yep, would lose a nice spelling for index on the iterator (it'd just be a tuple) - but given structured bindings, do people much want/need that naming anyway?

I see. I think in this specific case the ergonomics make this work in real world. We have a considerable amount of code in MLIR and IREE that iterates over multidimensional stuff in lockstep, and it's nice to have a concise and safe way to manage that. I don't think that flatten achieves that given the total amount of nesting.

The total amount of nesting in the call? 3, in this case - flatten+enumerate+zip - I wouldn't be against having a wrapper, I guess, that does those things together - while still having tehm implemented as independent features, rather than having enumerate or zip being aware of each other.

Instead, one could unpack the values in the first statement inside the loop like so:

for (auto [Idx, Val] : enumerate(zip_equal(...))) {
  auto [X, Y, Z] = Val.value()

That seems fine too as a solution to the issue, rather than introducing this enumerate+zip special case?

Another issue I see is unintentionally unpacking a single element in generic code -- a single range can contain tuple values, and I don't think we can tell this apart from zip(...) without checking the range/iterator type.

Not sure I follow - the generic code would be using flatten(enumerate(zip...)) so it'd still always be flattening the enumerate+zip, if the generic code were calling flatten+enumerate, without knowing the contents of the enumerate - it'd be asking to flatten whatever was being enumerated. I don't follow there being an unintentional ambiguity between the two.

[kuhar]

In D144503#4145802, @dblaikie wrote:

The total amount of nesting in the call? 3, in this case - flatten+enumerate+zip - I wouldn't be against having a wrapper, I guess, that does those things together - while still having tehm implemented as independent features, rather than having enumerate or zip being aware of each other.

Your comments got me thinking about a different solution; I'd like to try to decompose this as follows something like this:

• use the zippy to take care of enumeration of all subranges, including the index. Drop all the custom iterator/enumerator types etc.
• add a wrapper reference type that produces a nice interface over each tuple of elements from zippy (very similar to enumerator_result here)
• use something like map_range to expose the zipped ranges via this wrapper element reference type

In pseudocode:

auto enumerate(ranges...) {
  return map_range(zippy<zip_second>(index_stream{}, ranges...), to_enumerate_result);
}

WDYT?

Not sure I follow - the generic code would be using flatten(enumerate(zip...)) so it'd still always be flattening the enumerate+zip, if the generic code were calling flatten+enumerate, without knowing the contents of the enumerate - it'd be asking to flatten whatever was being enumerated. I don't follow there being an unintentional ambiguity between the two.

I was worried about code that takes a variadic number of ranges and passes them to enumerate, but you are right that this is a non-issue if we leave enumerate unary and have a new wrapper function.

So a potential solution would be to introduce enumerate_zip that takes 2 or more ranges and is implemented like this:

auto enumerate_zip(first, second, rest...) {
  return zippy<zip_second>(index_stream{}, first, second, rest...);
}

and does not support .index() and .value(). I think that's also a viable option and doesn't even need flatten if we give up on those two accessors anyway.

[dblaikie]

In D144503#4145819, @kuhar wrote:

In D144503#4145802, @dblaikie wrote:

The total amount of nesting in the call? 3, in this case - flatten+enumerate+zip - I wouldn't be against having a wrapper, I guess, that does those things together - while still having tehm implemented as independent features, rather than having enumerate or zip being aware of each other.

Your comments got me thinking about a different solution; I'd like to try to decompose this as follows something like this:

• use the zippy to take care of enumeration of all subranges, including the index. Drop all the custom iterator/enumerator types etc.
• add a wrapper reference type that produces a nice interface over each tuple of elements from zippy (very similar to enumerator_result here)
• use something like map_range to expose the zipped ranges via this wrapper element reference type

In pseudocode:

auto enumerate(ranges...) {
  return map_range(zippy<zip_second>(index_stream{}, ranges...), to_enumerate_result);
}

WDYT?

Not sure I follow - the generic code would be using flatten(enumerate(zip...)) so it'd still always be flattening the enumerate+zip, if the generic code were calling flatten+enumerate, without knowing the contents of the enumerate - it'd be asking to flatten whatever was being enumerated. I don't follow there being an unintentional ambiguity between the two.

I was worried about code that takes a variadic number of ranges and passes them to enumerate, but you are right that this is a non-issue if we leave enumerate unary and have a new wrapper function.

So a potential solution would be to introduce enumerate_zip that takes 2 or more ranges and is implemented like this:

auto enumerate_zip(first, second, rest...) {
  return zippy<zip_second>(index_stream{}, first, second, rest...);
}

and does not support .index() and .value(). I think that's also a viable option and doesn't even need flatten if we give up on those two accessors anyway.

Yeah, either of these sound OK to me - thanks for working through them.

(be nice if enumerate_resulrt or equivalent were a bit simpler, but I haven't looked closely at all the complexities/understood their motivation)

I guess llvm::enumerate doesn't have any particular API it's trying to emulate (like I don't immediately see a standardized version on the horizon? Is there a boost or other one that we should be trying to keep this looking similar to)? If there is some similar one we're trying to stay close to, does that one support N-ary enumerate? if it doesn't, then I'd be happy to keep the current enumerate as singular, and add the separate enumerate_zip, probably. As much as the "wrapping it in a nice result with index() and value()" is a bit of a pain/bunch of work compared to the generic tuple, I guess having the index named is worthwhile - even with the prevalence of structured bindings, so I don't object to the enumerate_result or equivalent being implemented)

[Mogball]

+1 finally I'm happy to see this

[kuhar]

Implement enumerate in terms of zippy with a custom zip iterator.

Fix issues with constness.

[kuhar]

I iterated on this a fair bit and come up with this implementation that uses zippy to manage iterators and ranges. This way all we need to do is to define a zip iterator type that returns an enumeration result on dereference. This enumeration result is essentially a tuple of references that exposes the enumeration interface (.index() and .value()). This way, we do not duplicate similar iteration machinery across multiple APIs: zip*, enumerate, or enumerate_zip, and do not have to duplicate tests cases either.

I guess llvm::enumerate doesn't have any particular API it's trying to emulate (like I don't immediately see a standardized version on the horizon? Is there a boost or other one that we should be trying to keep this looking similar to)? If there is some similar one we're trying to stay close to, does that one support N-ary enumerate? if it doesn't, then I'd be happy to keep the current enumerate as singular, and add the separate enumerate_zip, probably.

I looked at Python and a few newer languages, but it seems like they can avoid this complexity by supporting 'nested structured bindings', which C++17 does not have. IMO, n-ary enumeration is a pretty natural extension -- the evidence for that is the number of loops that already do enumerate(zip(...)), despite its current clunkiness.

I tried wrapping results of enumerate(zip(args...)) with flatten or similar functions, and found this to be much more complicated and have some clear drawbacks like multiple moves of the input ranges, unclear lifetime semantics when composing multiple range adaptors, etc. The new implementation in this revision avoids that by reusing what zippy already handles and passes existing enumerate tests that check for the expected semantics.

[kuhar]

Rebase. Update commit description.

[dblaikie]

Because the enumerate_result returned on dereference is a temporary, enumeration result can no longer be used through an lvalue ref.

Is it valid to have a value-returning iterator? (what about op->, which needs a pointer returned?) I thought that wasn't valid for most iterator categories & you had to resort to storing an object inside the iterator to return a pointer to in op*/op->

[kuhar]

In D144503#4174097, @dblaikie wrote:

Because the enumerate_result returned on dereference is a temporary, enumeration result can no longer be used through an lvalue ref.

Is it valid to have a value-returning iterator? (what about op->, which needs a pointer returned?) I thought that wasn't valid for most iterator categories

This is already the case with other iterators returned from zip* functions -- their reference type is the same as value type (tuple of references). Other common iterators that return values that come to my mind are SafeIntIterator (from llvm::seq and llvm::iota_range), vector<bool>::iterator (reference wrapper). If I understand '[forward.iterators]' correctly, this seems fine as long as reference is *some* reference type convertible to the value type:

— if X is a mutable iterator, reference is a reference to T; if X is a constant iterator, reference is a reference to const T,
— the expressions in Table 97 are valid and have the indicated semantics, and

In table 97:

Expression | Return type
*r++ | reference

And in '[input.iterators]:

A class or pointer type X satisfies the requirements of an input iterator for the value type T if X satisfies the
Iterator (27.2.2) and EqualityComparable (Table 20) requirements and the expressions in Table 95 are
valid and have the indicated semantics.

In table 95:

Expression | Return type
*a | reference, convertible to T

Right now, enumerate is returns only forward_iterators, but we should be able to make it bidirectional and probably random in the future without having to change the iterator reference type (provided that all nested iterators have the required categories).

[dblaikie]

I think it's the InputIterator (ForwardIterators must be InputIterators) requirement is the one that makes value returns not possible in practice because they're required to support i->m as being equivalent to (*i).m`, which isn't possible, as far as I recall/understand without backing storage to return a pointer to?

Oh, and ForwardIterator also says (on cppreference):

Let T be the value type of It. The type std::iterator_traits<It>::reference must be either
  T& or T&& (since C++11) if It satisfies LegacyOutputIterator (It is mutable), or
  const T& or const T&& (since C++11) otherwise (It is constant),
(where T is the type denoted by std::iterator_traits<It>::value_type)

[dblaikie]

I don't totally object - though, for myself (I think this was discussed previously, but I don't fully understand the refutation/disagreement) I think I'd prefer to expose the compositions themselves and probably not have a special return type, so the end result is:

for (auto &[index, v1, v2] : zip(index{}, r1, r2))

And drop "enumerate" entirely? It doesn't seem like it adds enough - though I guess having a name for it is useful. *shrug*

llvm/include/llvm/ADT/STLExtras.h

2288–2289

Could this be conforming/have a real reference type (& Return ref from op*)?

2297–2302

prefer non-member (can be a friend) op overloads where possible - makes sure implicit conversions happen equally on LHS and RHS

[kuhar]

In D144503#4179026, @dblaikie wrote:

I think it's the InputIterator (ForwardIterators must be InputIterators) requirement is the one that makes value returns not possible in practice because they're required to support i->m as being equivalent to (*i).m`, which isn't possible, as far as I recall/understand without backing storage to return a pointer to?

Oh, and ForwardIterator also says (on cppreference):

Let T be the value type of It. The type std::iterator_traits<It>::reference must be either
  T& or T&& (since C++11) if It satisfies LegacyOutputIterator (It is mutable), or
  const T& or const T&& (since C++11) otherwise (It is constant),
(where T is the type denoted by std::iterator_traits<It>::value_type)

David and I talked offline and this interpretation of the standard is probably the correct one. To conform to the iterator requirements, we would have to store something like std::optional<TupleOfReferences> inside zip_common and materialize it on the first dereference. This would be a proper fix for all zip functions, but it doesn't seem like any part of llvm relies on reference being an actual reference right now, so it doesn't seem like a blocker.

I will update all uses of for (auto &it : enumerate(...)) in a separate revision before landing this and leave a FIXME for the reference type issues.

[zero9178]

In D144503#4179099, @kuhar wrote:

In D144503#4179026, @dblaikie wrote:

I think it's the InputIterator (ForwardIterators must be InputIterators) requirement is the one that makes value returns not possible in practice because they're required to support i->m as being equivalent to (*i).m`, which isn't possible, as far as I recall/understand without backing storage to return a pointer to?

Oh, and ForwardIterator also says (on cppreference):

Let T be the value type of It. The type std::iterator_traits<It>::reference must be either
  T& or T&& (since C++11) if It satisfies LegacyOutputIterator (It is mutable), or
  const T& or const T&& (since C++11) otherwise (It is constant),
(where T is the type denoted by std::iterator_traits<It>::value_type)

David and I talked offline and this interpretation of the standard is probably the correct one. To conform to the iterator requirements, we would have to store something like std::optional<TupleOfReferences> inside zip_common and materialize it on the first dereference. This would be a proper fix for all zip functions, but it doesn't seem like any part of llvm relies on reference being an actual reference right now, so it doesn't seem like a blocker.

I will update all uses of for (auto &it : enumerate(...)) in a separate revision before landing this and leave a FIXME for the reference type issues.

I think its also fair to say that this is somewhat a historical mistake that was never properly followed (see std::vector<bool>) which is probably why this requirement was dropped in C++20 concepts for forward iterators: https://en.cppreference.com/w/cpp/iterator/forward_iterator

[dblaikie]

In D144503#4179141, @zero9178 wrote:

In D144503#4179099, @kuhar wrote:

In D144503#4179026, @dblaikie wrote:

I think it's the InputIterator (ForwardIterators must be InputIterators) requirement is the one that makes value returns not possible in practice because they're required to support i->m as being equivalent to (*i).m`, which isn't possible, as far as I recall/understand without backing storage to return a pointer to?

Oh, and ForwardIterator also says (on cppreference):

Let T be the value type of It. The type std::iterator_traits<It>::reference must be either
  T& or T&& (since C++11) if It satisfies LegacyOutputIterator (It is mutable), or
  const T& or const T&& (since C++11) otherwise (It is constant),
(where T is the type denoted by std::iterator_traits<It>::value_type)

David and I talked offline and this interpretation of the standard is probably the correct one. To conform to the iterator requirements, we would have to store something like std::optional<TupleOfReferences> inside zip_common and materialize it on the first dereference. This would be a proper fix for all zip functions, but it doesn't seem like any part of llvm relies on reference being an actual reference right now, so it doesn't seem like a blocker.

I will update all uses of for (auto &it : enumerate(...)) in a separate revision before landing this and leave a FIXME for the reference type issues.

I think its also fair to say that this is somewhat a historical mistake that was never properly followed (see std::vector<bool>) which is probably why this requirement was dropped in C++20 concepts for forward iterators: https://en.cppreference.com/w/cpp/iterator/forward_iterator

Yeah, sort of nice to see (insofar as I can see it/read the concepts as best I can) - op-> is awkward & weird when it's not supported, but probably the best tradeoff to lose that consistency for the greater flexibility. (Not sure what to make of comments like "Pointers and references obtained from a forward iterator into a range remain valid while the range exists.".

[kuhar]

Rebase. Add comments clarifying iterator reference_type requirments.

llvm/include/llvm/ADT/STLExtras.h

2288–2289

I looked into returning the reference to the index but this breaks the requirement of references being valid as long as the range is valid:

Pointers and references obtained from a forward iterator into a range remain valid while the range exists.

I kept this as-is and added a comment.

[kuhar]

My plan is to land a series of clean-up commits removing lvalue references to enumerate elements and once these are in land this patch (probably end of this week or beginning of the next week).

[kuhar]

Rebase. Update existing uses of enumerate with non-const lvalue refs.
Replace some enumerate(zip* patterns with n-ary enumerate.

[dblaikie]

llvm/unittests/ADT/STLExtrasTest.cpp

222

[zero9178]

LGTM!

llvm/include/llvm/ADT/STLExtras.h

2206

2242

nit: remove trivial braces here and below

[kuhar]

Address comments.

[kuhar]

Fix outdated usage in AArch64PerfectShuffle

[srj]

According to git bisect, this change appears to have broken llvm-tblgen when building under MSVC

C:\build_bot\worker\llvm-17-x86-64-windows\llvm-project\llvm\utils\TableGen\IntrinsicEmitter.cpp(845): error C2440: 'initializing':
cannot convert from 'size_t' to '_This'
        with
        [
            _This=const llvm::SmallVector<llvm::CodeGenIntrinsic::ArgAttribute,0> &
        ]
C:\build_bot\worker\llvm-17-x86-64-windows\llvm-project\llvm\utils\TableGen\IntrinsicEmitter.cpp(845): note: Reason: cannot convert
from 'size_t' to 'const T'
        with
        [
            T=llvm::SmallVector<llvm::CodeGenIntrinsic::ArgAttribute,0>
        ]
C:\build_bot\worker\llvm-17-x86-64-windows\llvm-project\llvm\utils\TableGen\IntrinsicEmitter.cpp(845): note: Constructor for class '
llvm::SmallVector<llvm::CodeGenIntrinsic::ArgAttribute,0>' is declared 'explicit'

this has rendered all Windows-based testing of Halide impossible; I urge someone to fix (or revert) this change as soon as conveniently possible.

[srj]

There is also a similar breakage in InstrInfoEmitter.cpp:

C:\build_bot\worker\llvm-17-x86-32-windows\llvm-project\llvm\utils\TableGen\InstrInfoEmitter.cpp(120): error C2440: 'initializing': cannot convert from 'size_t' to '_This'
        with
        [
            _This=llvm::Record *const &
        ]

[kuhar]

In D144503#4201034, @srj wrote:

There is also a similar breakage in InstrInfoEmitter.cpp:

C:\build_bot\worker\llvm-17-x86-32-windows\llvm-project\llvm\utils\TableGen\InstrInfoEmitter.cpp(120): error C2440: 'initializing': cannot convert from 'size_t' to '_This'
        with
        [
            _This=llvm::Record *const &
        ]

Hi @srj,

Is there some public buildbot that experienced the same failure? Do you have some info on the build environment, version of the compiler, etc? I haven't seen this affect other windows buildbots.
If this is blocking you and you need a quick fix isolated to these two places, I suggest patching these two loops something like this:

for (const auto &En :
     enumerate(Intrinsic.ArgumentAttributes)) {
     size_t AttrIdx = En.index();
     auto& Attrs = En.value();

or even with manual indexing:

size_t AttrIdx = 0;
 for (const auto &Attrs : Intrinsic.ArgumentAttributes) {
      
  ...
  ++AttIdx;
}

[srj]

In D144503#4201043, @kuhar wrote:

Is there some public buildbot that experienced the same failure?

You can see the build logs here: https://buildbot.halide-lang.org/master/#/builders/105/builds/8

Do you have some info on the build environment, version of the compiler, etc? I haven't seen this affect other windows buildbots.

Build environment is fairly stock Visual Studio Community 2022 on Windows 10. (I'll go check to see if there are updates that need installing, but they should be pretty close to the latest.)

If this is blocking you and you need a quick fix isolated to these two places, I suggest patching these two loops something like this:

Thanks, but we need to figure out if this is a problem in our build environment or a corner case of broken code -- we rely on testing unchanged LLVM versions.

[srj]

In D144503#4201046, @srj wrote:

Build environment is fairly stock Visual Studio Community 2022 on Windows 10. (I'll go check to see if there are updates that need installing, but they should be pretty close to the latest.)

EDIT: looks like there are some uninstalled updates -- I'll get those installed and re-check, maybe this is just an MSVC bug.

[srj]

In D144503#4201050, @srj wrote:

In D144503#4201046, @srj wrote:

Build environment is fairly stock Visual Studio Community 2022 on Windows 10. (I'll go check to see if there are updates that need installing, but they should be pretty close to the latest.)

EDIT: looks like there are some uninstalled updates -- I'll get those installed and re-check, maybe this is just an MSVC bug.

So after installing the latest VS2022 updates, things appear to be working smoothly!

I was not expecting this at all -- it's been a long time since I've seen a miscompilation of this sort in any modern compiler so I didn't even think to check this.

Sorry for the noise!

[aprantl]

This somehow broke the -DLLVM_ENABLE_MODULES=1 build:

Can you take a look?

https://green.lab.llvm.org/green/view/LLDB/job/lldb-cmake/52513/consoleFull#-458239162a1ca8a51-895e-46c6-af87-ce24fa4cd561

[aprantl]

In module 'LLVM_Utils' imported from /Users/buildslave/jenkins/workspace/lldb-cmake@2/llvm-project/llvm/tools/llvm-pdbutil/StreamUtil.h:12:
/Users/buildslave/jenkins/workspace/lldb-cmake@2/llvm-project/llvm/include/llvm/ADT/STLExtras.h:2389:11: error: no matching function for call to 'all_equal'
          all_equal({std::distance(adl_begin(First), adl_end(First)),
          ^~~~~~~~~
/Applications/Xcode.app/Contents/Developer/Platforms/MacOSX.platform/Developer/SDKs/MacOSX11.3.sdk/usr/include/assert.h:93:25: note: expanded from macro 'assert'
    (__builtin_expect(!(e), 0) ? __assert_rtn(__func__, __FILE__, __LINE__, #e) : (void)0)
                        ^
/Users/buildslave/jenkins/workspace/lldb-cmake@2/llvm-project/llvm/tools/llvm-pdbutil/ExplainOutputStyle.cpp:129:28: note: in instantiation of function template specialization 'llvm::enumerate<const std::__1::vector<llvm::ArrayRef<llvm::support::detail::packed_endian_specific_integral<unsigned int, llvm::support::little, 1, 1>>> &>' requested here
  for (const auto &Entry : enumerate(Layout.StreamMap)) {
                           ^
/Users/buildslave/jenkins/workspace/lldb-cmake@2/llvm-project/llvm/include/llvm/ADT/STLExtras.h:2056:28: note: candidate template ignored: couldn't infer template argument 'R'
template <typename R> bool all_equal(R &&Range) {
                           ^
/Users/buildslave/jenkins/workspace/lldb-cmake@2/llvm-project/llvm/include/llvm/ADT/STLExtras.h:2064:28: note: candidate template ignored: couldn't infer template argument 'T'
template <typename T> bool all_equal(std::initializer_list<T> Values) {
                           ^
1 error generated.

[kuhar]

In D144503#4203254, @aprantl wrote:

This somehow broke the -DLLVM_ENABLE_MODULES=1 build:

Can you take a look?

https://green.lab.llvm.org/green/view/LLDB/job/lldb-cmake/52513/consoleFull#-458239162a1ca8a51-895e-46c6-af87-ce24fa4cd561

Hi @aprantl,

What are the requirements for building with modules enabled? I tried this locally but it didn't get very far, not sure if my system compiler & standard library are new enough (clang14).
If you can reproduce it on your end, could you check if applying D146231 fixes it? My guess is that we may need to 'normalize' types passed to all_equal to size_t.

[kuhar]

Edit: Ah no, now I see that only one range is passed to the enumerate in ExplainOutputStyle.cpp. In that case we have exactly one type passed to the initialized list so I don't see how that'd fail. Checking other things...

[kuhar]

I've just tried on my mac and can reproduce it with clang from xcode

$ clang --version
Apple clang version 14.0.0 (clang-1400.0.29.202)
Target: arm64-apple-darwin22.3.0
Thread model: posix
InstalledDir: /Library/Developer/CommandLineTools/usr/bin

CMake command: cmake ../llvm-project/llvm -GNinja -DCMAKE_BUILD_TYPE=Release -DLLVM_ENABLE_ASSERTIONS=1 -DLLVM_ENABLE_MODULES=1
Build command: ninja llvm-pdbutil

[kuhar]

@aprantl This seems to me like a host compiler bug. I came up with a workaround: https://reviews.llvm.org/D146340.

[ronlieb]

also seeing similar error in downstream windows build of llvm.

In D144503#4201034, @srj wrote:

There is also a similar breakage in InstrInfoEmitter.cpp:

C:\build_bot\worker\llvm-17-x86-32-windows\llvm-project\llvm\utils\TableGen\InstrInfoEmitter.cpp(120): error C2440: 'initializing': cannot convert from 'size_t' to '_This'
        with
        [
            _This=llvm::Record *const &
        ]

[dstuttard]

In D144503#4204120, @ronlieb wrote:

also seeing similar error in downstream windows build of llvm.

In D144503#4201034, @srj wrote:

There is also a similar breakage in InstrInfoEmitter.cpp:

C:\build_bot\worker\llvm-17-x86-32-windows\llvm-project\llvm\utils\TableGen\InstrInfoEmitter.cpp(120): error C2440: 'initializing': cannot convert from 'size_t' to '_This'
        with
        [
            _This=llvm::Record *const &
        ]

I note from an earlier comment that updating VS2022 with latest patches solved this issue for @srj
But is the issue similar for the minimum required version of MSVC (currently Visual Studio 2019 / v16.0 )??

[kuhar]

In D144503#4206725, @dstuttard wrote:

In D144503#4204120, @ronlieb wrote:

also seeing similar error in downstream windows build of llvm.

In D144503#4201034, @srj wrote:

There is also a similar breakage in InstrInfoEmitter.cpp:

C:\build_bot\worker\llvm-17-x86-32-windows\llvm-project\llvm\utils\TableGen\InstrInfoEmitter.cpp(120): error C2440: 'initializing': cannot convert from 'size_t' to '_This'
        with
        [
            _This=llvm::Record *const &
        ]

I note from an earlier comment that updating VS2022 with latest patches solved this issue for @srj
But is the issue similar for the minimum required version of MSVC (currently Visual Studio 2019 / v16.0 )??

It passed across all windows buildbots, which includes VS 2019. Example: https://lab.llvm.org/buildbot/#/builders/13/builds/33254

[dstuttard]

I note from an earlier comment that updating VS2022 with latest patches solved this issue for @srj
But is the issue similar for the minimum required version of MSVC (currently Visual Studio 2019 / v16.0 )??

It passed across all windows buildbots, which includes VS 2019. Example: https://lab.llvm.org/buildbot/#/builders/13/builds/33254

I think that build bot is using 1929 (which is VS2019 16.10 ??) I get confused by the different ways the versions are described :(
The minimum required is v16.0 - which is 1920 I think.

Needless to say, we're seeing the same build error. I'll do some digging and see if updating to a newer VS2019 fixes the issue for us too (although if it does I guess the min required version will need updating).

[dstuttard]

In D144503#4206820, @dstuttard wrote:

I note from an earlier comment that updating VS2022 with latest patches solved this issue for @srj
But is the issue similar for the minimum required version of MSVC (currently Visual Studio 2019 / v16.0 )??

It passed across all windows buildbots, which includes VS 2019. Example: https://lab.llvm.org/buildbot/#/builders/13/builds/33254

I think that build bot is using 1929 (which is VS2019 16.10 ??) I get confused by the different ways the versions are described :(
The minimum required is v16.0 - which is 1920 I think.

Needless to say, we're seeing the same build error. I'll do some digging and see if updating to a newer VS2019 fixes the issue for us too (although if it does I guess the min required version will need updating).

Apologies - I was mistaken. We are actually seeing the issue with VS 2022 and not VS2019. I've done a bit more investigation and have discovered:
19.29.30133 (VS 2019 16.11.0) - works
19.31.31107 (VS2022 17.1) - fails
19.34.31933 (VS2022 17.4) - works

[kuhar]

In D144503#4216485, @dstuttard wrote:

In D144503#4206820, @dstuttard wrote:

I note from an earlier comment that updating VS2022 with latest patches solved this issue for @srj
But is the issue similar for the minimum required version of MSVC (currently Visual Studio 2019 / v16.0 )??

It passed across all windows buildbots, which includes VS 2019. Example: https://lab.llvm.org/buildbot/#/builders/13/builds/33254

I think that build bot is using 1929 (which is VS2019 16.10 ??) I get confused by the different ways the versions are described :(
The minimum required is v16.0 - which is 1920 I think.

Needless to say, we're seeing the same build error. I'll do some digging and see if updating to a newer VS2019 fixes the issue for us too (although if it does I guess the min required version will need updating).

Apologies - I was mistaken. We are actually seeing the issue with VS 2022 and not VS2019. I've done a bit more investigation and have discovered:
19.29.30133 (VS 2019 16.11.0) - works
19.31.31107 (VS2022 17.1) - fails
19.34.31933 (VS2022 17.4) - works

I tried reproducing this but I don't know where to get this specific version from. I tried the earliest VS2022 release (17.0.0) from https://learn.microsoft.com/en-us/visualstudio/releases/2022/release-history#fixed-version-bootstrappers:

Microsoft (R) C/C++ Optimizing Compiler Version 19.30.30705 for x64

And llvm compiled fine for me.

[kuhar]

@dstuttard I was able to reproduce it on 17.1 and submited a fix for review: https://reviews.llvm.org/D146893. Could you check this resolved the build failures that you see?

The exact version that I used was: 17.1.0 February 15, 2022, 17.1.32210.238, MSVC (19.31.31104).

llvm/include/llvm/ADT/STLExtras.h

 #include "llvm/ADT/STLForwardCompat.h"
 #include "llvm/ADT/STLFunctionalExtras.h"
 #include "llvm/ADT/identity.h"
 #include "llvm/ADT/iterator.h"
 #include "llvm/ADT/iterator_range.h"
 #include "llvm/Config/abi-breaking.h"
 #include "llvm/Support/ErrorHandling.h"
 #include <algorithm>
 #include <cassert>
 #include <cstddef>
 #include <cstdint>
 #include <cstdlib>
 #include <functional>
 #include <initializer_list>
 #include <iterator>
 #include <limits>
 #include <memory>

 using std::declval;
 
 // We have to alias this since inlining the actual type at the usage site
 // in the parameter list of iterator_facade_base<> below ICEs MSVC 2017.
 template<typename... Iters> struct ZipTupleType {
   using type = std::tuple<decltype(*declval<Iters>())...>;
 };
 
-template <typename ZipType, typename... Iters>
+template <typename ZipType, typename ReferenceTupleType, typename... Iters>
 using zip_traits = iterator_facade_base<
     ZipType,
     std::common_type_t<
         std::bidirectional_iterator_tag,
         typename std::iterator_traits<Iters>::iterator_category...>,
     // ^ TODO: Implement random access methods.
-    typename ZipTupleType<Iters...>::type,
+    ReferenceTupleType,
     typename std::iterator_traits<
         std::tuple_element_t<0, std::tuple<Iters...>>>::difference_type,
     // ^ FIXME: This follows boost::make_zip_iterator's assumption that all
     // inner iterators have the same difference_type. It would fail if, for
     // instance, the second field's difference_type were non-numeric while the
     // first is.
-    typename ZipTupleType<Iters...>::type *,
-    typename ZipTupleType<Iters...>::type>;
+    ReferenceTupleType *, ReferenceTupleType>;
 
-template <typename ZipType, typename... Iters>
-struct zip_common : public zip_traits<ZipType, Iters...> {
-  using Base = zip_traits<ZipType, Iters...>;
+template <typename ZipType, typename ReferenceTupleType, typename... Iters>
+struct zip_common : public zip_traits<ZipType, ReferenceTupleType, Iters...> {
+  using Base = zip_traits<ZipType, ReferenceTupleType, Iters...>;
   using IndexSequence = std::index_sequence_for<Iters...>;
   using value_type = typename Base::value_type;
 
   std::tuple<Iters...> iterators;
 
 protected:
   template <size_t... Ns> value_type deref(std::index_sequence<Ns...>) const {
     return value_type(*std::get<Ns>(iterators)...);
public:
 
   /// Return true if all the iterator are matching `other`'s iterators.
   bool all_equals(zip_common &other) {
     return test_all_equals(other, IndexSequence{});
   }
 };
 
 template <typename... Iters>
-struct zip_first : zip_common<zip_first<Iters...>, Iters...> {
-  using zip_common<zip_first, Iters...>::zip_common;
+struct zip_first : zip_common<zip_first<Iters...>,
+                              typename ZipTupleType<Iters...>::type, Iters...> {
+  using zip_common<zip_first, typename ZipTupleType<Iters...>::type,
+                   Iters...>::zip_common;
 
   bool operator==(const zip_first &other) const {
     return std::get<0>(this->iterators) == std::get<0>(other.iterators);
   }
 };
 
 template <typename... Iters>
-struct zip_shortest : zip_common<zip_shortest<Iters...>, Iters...> {
-  using zip_common<zip_shortest, Iters...>::zip_common;
+struct zip_shortest
+    : zip_common<zip_shortest<Iters...>, typename ZipTupleType<Iters...>::type,
+                 Iters...> {
+  using zip_common<zip_shortest, typename ZipTupleType<Iters...>::type,
+                   Iters...>::zip_common;
 
   bool operator==(const zip_shortest &other) const {
     return any_iterator_equals(other, std::index_sequence_for<Iters...>{});
   }
 
 private:
   template <size_t... Ns>
   bool any_iterator_equals(const zip_shortest &other,
template <typename A, typename B> auto operator()(A &lhs, B &rhs) const {
     assert(lhs);
     assert(rhs);
     return func(*lhs, *rhs);
   }
 };
 
 namespace detail {
 
-template <typename R> class enumerator_iter;
+/// Tuple-like type for `zip_enumerator` dereference.
+template <typename... Refs> struct enumerator_result;
 
-template <typename R> struct result_pair {
-  using value_reference =
-      typename std::iterator_traits<IterOfRange<R>>::reference;
-
-  friend class enumerator_iter<R>;
-
-  result_pair(std::size_t Index, IterOfRange<R> Iter)
-      : Index(Index), Iter(Iter) {}
+template <typename... Iters>
+using EnumeratorTupleType = enumerator_result<decltype(*declval<Iters>())...>;
 
-  std::size_t index() const { return Index; }
-  value_reference value() const { return *Iter; }
+/// Zippy iterator that uses the second iterator for comparisons. For the
+/// increment to be safe, the second range has to be the shortest.
+/// Returns `enumerator_result` on dereference to provide `.index()` and
+/// `.value()` member functions.
+/// Note: Because the dereference operator returns `enumerator_result` as a
+/// value instead of a reference and does not strictly conform to the C++17's
+/// definition of forward iterator. However, it satisfies all the
+/// forward_iterator requirements that the `zip_common` and `zippy` depend on
+/// and fully conforms to the C++20 definition of forward iterator.
+/// This is similar to `std::vector<bool>>::iterator` that returns bit reference
+/// wrappers on dereference.
+template <typename... Iters>
+struct zip_enumerator : zip_common<zip_enumerator<Iters...>,
+                                   EnumeratorTupleType<Iters...>, Iters...> {
+  static_assert(sizeof...(Iters) >= 2, "Expected at least two iteratees");
+  using zip_common<zip_enumerator<Iters...>, EnumeratorTupleType<Iters...>,
+                   Iters...>::zip_common;
 
-private:
-  std::size_t Index = std::numeric_limits<std::size_t>::max();
-  IterOfRange<R> Iter;
+  bool operator==(const zip_enumerator &Other) const {
+    return std::get<1>(this->iterators) == std::get<1>(Other.iterators);
+  }
 };
 
-template <std::size_t i, typename R>
-decltype(auto) get(const result_pair<R> &Pair) {
-  static_assert(i < 2);
-  if constexpr (i == 0) {
-    return Pair.index();
-  } else {
-    return Pair.value();
-  }
-}
+template <typename... Refs> struct enumerator_result<std::size_t, Refs...> {
+  static constexpr std::size_t NumRefs = sizeof...(Refs);
+  static_assert(NumRefs != 0);
+  // `NumValues` includes the index.
+  static constexpr std::size_t NumValues = NumRefs + 1;
 
-template <typename R>
-class enumerator_iter
-    : public iterator_facade_base<enumerator_iter<R>, std::forward_iterator_tag,
-                                  const result_pair<R>> {
-  using result_type = result_pair<R>;
+  // Tuple type whose element types are references for each `Ref`.
+  using range_reference_tuple = std::tuple<Refs...>;
+  // Tuple type who elements are references to all values, including both
+  // the index and `Refs` reference types.
+  using value_reference_tuple = std::tuple<std::size_t, Refs...>;
 
-public:
-  explicit enumerator_iter(IterOfRange<R> EndIter)
-      : Result(std::numeric_limits<size_t>::max(), EndIter) {}
+  enumerator_result(std::size_t Index, Refs &&...Rs)
+      : Idx(Index), Storage(std::forward<Refs>(Rs)...) {}
 
-  enumerator_iter(std::size_t Index, IterOfRange<R> Iter)
-      : Result(Index, Iter) {}
+  /// Returns the 0-based index of the current position within the original
+  /// input range(s).
+  std::size_t index() const { return Idx; }
 
-  const result_type &operator*() const { return Result; }
+  /// Returns the value(s) for the current iterator. This does not include the
+  /// index.
+  decltype(auto) value() const {
+    if constexpr (NumRefs == 1) {
+      return std::get<0>(Storage);
+    } else {
+      return Storage;
+    }
+  }
 
-  enumerator_iter &operator++() {
-    assert(Result.Index != std::numeric_limits<size_t>::max());
-    ++Result.Iter;
-    ++Result.Index;
-    return *this;
+  /// Returns the value at index `I`. This includes the index.
+  template <std::size_t I>
+  friend decltype(auto) get(const enumerator_result &Result) {
+    static_assert(I < NumValues, "Index out of bounds");
+    if constexpr (I == 0) {
+      return Result.Idx;
+    } else {
+      return std::get<I - 1>(Result.Storage);
+    }
   }
 
-  bool operator==(const enumerator_iter &RHS) const {
-    // Don't compare indices here, only iterators.  It's possible for an end
-    // iterator to have different indices depending on whether it was created
-    // by calling std::end() versus incrementing a valid iterator.
-    return Result.Iter == RHS.Result.Iter;
+  template <typename... Ts>
+  friend bool operator==(const enumerator_result &Result,
+                         const std::tuple<std::size_t, Ts...> &Other) {
+    static_assert(NumRefs == sizeof...(Ts), "Size mismatch");
+    if (Result.Idx != std::get<0>(Other))
+      return false;
+    return Result.is_value_equal(Other, std::make_index_sequence<NumRefs>{});
   }
 
 private:
-  result_type Result;
-};
+  template <typename Tuple, std::size_t... Idx>
+  bool is_value_equal(const Tuple &Other, std::index_sequence<Idx...>) const {
+    return ((std::get<Idx>(Storage) == std::get<Idx + 1>(Other)) && ...);
+  }
+
+  std::size_t Idx;
+  // Make this tuple mutable to avoid casts that obfuscate const-correctness
+  // issues. Const-correctness of references is taken care of by `zippy` that
+  // defines const-non and const iterator types that will propagate down to
+  // `enumerator_result`'s `Refs`.
+  //  Note that unlike the results of `zip*` functions, `enumerate`'s result are
+  //  supposed to be modifiable even when defined as
+  // `const`.
+  mutable range_reference_tuple Storage;
+};
+
+/// Infinite stream of increasing 0-based `size_t` indices.
+struct index_stream {
+  struct iterator : iterator_facade_base<iterator, std::forward_iterator_tag,
+                                         const iterator> {
+    iterator &operator++() {
+      assert(Index != std::numeric_limits<std::size_t>::max() &&
+             "Attempting to increment end iterator");
+      ++Index;
+      return *this;
+    }
 
-template <typename R> class enumerator {
-public:
-  explicit enumerator(R &&Range) : TheRange(std::forward<R>(Range)) {}
+    // Note: This dereference operator returns a value instead of a reference
+    // and does not strictly conform to the C++17's definition of forward
+    // iterator. However, it satisfies all the forward_iterator requirements
+    // that the `zip_common` depends on and fully conforms to the C++20
+    // definition of forward iterator.
+    std::size_t operator*() const { return Index; }
 
-  enumerator_iter<R> begin() {
-    return enumerator_iter<R>(0, adl_begin(TheRange));
-  }
-  enumerator_iter<R> begin() const {
-    return enumerator_iter<R>(0, adl_begin(TheRange));
+    friend bool operator==(const iterator &Lhs, const iterator &Rhs) {
+      return Lhs.Index == Rhs.Index;
     }
 
-  enumerator_iter<R> end() { return enumerator_iter<R>(adl_end(TheRange)); }
-  enumerator_iter<R> end() const {
-    return enumerator_iter<R>(adl_end(TheRange));
-  }
+    std::size_t Index = 0;
+  };
 
-private:
-  R TheRange;
+  iterator begin() const { return {}; }
+  iterator end() const {
+    // We approximate 'infinity' with the max size_t value, which should be good
+    // enough to index over any container.
+    iterator It;
+    It.Index = std::numeric_limits<std::size_t>::max();
+    return It;
+  }
 };
 
 } // end namespace detail
 
-/// Given an input range, returns a new range whose values are are pair (A,B)
-/// such that A is the 0-based index of the item in the sequence, and B is
-/// the value from the original sequence.  Example:
-///
-/// std::vector<char> Items = {'A', 'B', 'C', 'D'};
-/// for (auto X : enumerate(Items)) {
-///   printf("Item %zu - %c\n", X.index(), X.value());
+/// Given two or more input ranges, returns a new range whose values are are
+/// tuples (A, B, C, ...), such that A is the 0-based index of the item in the
+/// sequence, and B, C, ..., are the values from the original input ranges. All
+/// input ranges are required to have equal lengths. Note that the returned
+/// iterator allows for the values (B, C, ...) to be modified.  Example:
+///
+/// ```c++
+/// std::vector<char> Letters = {'A', 'B', 'C', 'D'};
+/// std::vector<int> Vals = {10, 11, 12, 13};
+///
+/// for (auto [Index, Letter, Value] : enumerate(Letters, Vals)) {
+///   printf("Item %zu - %c: %d\n", Index, Letter, Value);
+///   Value -= 10;
 /// }
+/// ```
 ///
-/// or using structured bindings:
-///
-/// for (auto [Index, Value] : enumerate(Items)) {
-///   printf("Item %zu - %c\n", Index, Value);
+/// Output:
+///   Item 0 - A: 10
+///   Item 1 - B: 11
+///   Item 2 - C: 12
+///   Item 3 - D: 13
+///
+/// or using an iterator:
+/// ```c++
+/// for (auto it : enumerate(Vals)) {
+///   it.value() += 10;
+///   printf("Item %zu: %d\n", it.index(), it.value());
 /// }
+/// ```
 ///
 /// Output:
-///   Item 0 - A
-///   Item 1 - B
-///   Item 2 - C
-///   Item 3 - D
-///
-template <typename R> detail::enumerator<R> enumerate(R &&TheRange) {
-  return detail::enumerator<R>(std::forward<R>(TheRange));
+///   Item 0: 20
+///   Item 1: 21
+///   Item 2: 22
+///   Item 3: 23
+///
+template <typename FirstRange, typename... RestRanges>
+auto enumerate(FirstRange &&First, RestRanges &&...Rest) {
+  assert((sizeof...(Rest) == 0 ||
+          all_equal({std::distance(adl_begin(First), adl_end(First)),
+                     std::distance(adl_begin(Rest), adl_end(Rest))...})) &&
+         "Ranges have different length");
+  using zip = detail::zippy<detail::zip_enumerator, detail::index_stream,
+                            FirstRange, RestRanges...>;
+  return zip(detail::index_stream{}, std::forward<FirstRange>(First),
+             std::forward<RestRanges>(Rest)...);
 }
 
 namespace detail {
 
 template <typename Predicate, typename... Args>
 bool all_of_zip_predicate_first(Predicate &&P, Args &&...args) {
   auto z = zip(args...);
   auto it = z.begin();

 /// The std::pointer_traits<>::to_address(p) variations of these overloads has
 /// not been implemented.
 template <class Ptr> auto to_address(const Ptr &P) { return P.operator->(); }
 template <class T> constexpr T *to_address(T *P) { return P; }
 
 } // end namespace llvm
 
 namespace std {
-template <typename R>
-struct tuple_size<llvm::detail::result_pair<R>>
-    : std::integral_constant<std::size_t, 2> {};
-
-template <std::size_t i, typename R>
-struct tuple_element<i, llvm::detail::result_pair<R>>
-    : std::conditional<i == 0, std::size_t,
-                       typename llvm::detail::result_pair<R>::value_reference> {
-};
+template <typename... Refs>
+struct tuple_size<llvm::detail::enumerator_result<Refs...>>
+    : std::integral_constant<std::size_t, sizeof...(Refs)> {};
+
+template <std::size_t I, typename... Refs>
+struct tuple_element<I, llvm::detail::enumerator_result<Refs...>>
+    : std::tuple_element<I, std::tuple<Refs...>> {};
+
+template <std::size_t I, typename... Refs>
+struct tuple_element<I, const llvm::detail::enumerator_result<Refs...>>
+    : std::tuple_element<I, std::tuple<Refs...>> {};
 
 } // namespace std
 
 #endif // LLVM_ADT_STLEXTRAS_H

llvm/unittests/ADT/STLExtrasTest.cpp

 //===- STLExtrasTest.cpp - Unit tests for STL extras ----------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/StringRef.h"
 #include "gmock/gmock.h"
 #include "gtest/gtest.h"
 
 #include <array>
 #include <climits>
+#include <cstddef>
+#include <initializer_list>
 #include <list>
 #include <tuple>
+#include <type_traits>
 #include <utility>
 #include <vector>
 
 using namespace llvm;
 
 using testing::ElementsAre;
 
 namespace {
for (auto [index, value] :
     ++value;
     Results.emplace_back(index, value);
   }
 
   EXPECT_THAT(Results, ElementsAre(PairType(0u, '2'), PairType(1u, '3'),
                                    PairType(2u, '4')));
 }
 
+TEST(STLExtrasTest, EnumerateTwoRanges) {
+  using Tuple = std::tuple<size_t, int, bool>;
+
+  std::vector<int> Ints = {1, 2};
+  std::vector<bool> Bools = {true, false};
+  EXPECT_THAT(llvm::enumerate(Ints, Bools),
+              ElementsAre(Tuple(0, 1, true), Tuple(1, 2, false)));
+
+  // Check that we can modify the values when the temporary is a const
+  // reference.
+  for (const auto &[Idx, Int, Bool] : llvm::enumerate(Ints, Bools)) {
+    (void)Idx;
+    Bool = false;
+    Int = -1;
+  }
+
+  EXPECT_THAT(Ints, ElementsAre(-1, -1));
+  EXPECT_THAT(Bools, ElementsAre(false, false));
+
+  // Check that we can modify the values when the result gets copied.
+  for (auto [Idx, Bool, Int] : llvm::enumerate(Bools, Ints)) {
+    (void)Idx;
+    Int = 3;
+    Bool = true;
+  }
+
+  EXPECT_THAT(Ints, ElementsAre(3, 3));
+  EXPECT_THAT(Bools, ElementsAre(true, true));
+
+  // Check that we can modify the values through `.values()`.
+  size_t Iters = 0;
+  for (auto It : llvm::enumerate(Bools, Ints)) {
+    EXPECT_EQ(It.index(), Iters);
+    ++Iters;
+
+    std::get<0>(It.value()) = false;
+    std::get<1>(It.value()) = 4;
+  }
+
+  EXPECT_THAT(Ints, ElementsAre(4, 4));
+  EXPECT_THAT(Bools, ElementsAre(false, false));
+}
+
+TEST(STLExtrasTest, EnumerateThreeRanges) {
+  using Tuple = std::tuple<size_t, int, bool, char>;
+
+  std::vector<int> Ints = {1, 2};
+  std::vector<bool> Bools = {true, false};
+  char Chars[] = {'X', 'D'};
+  EXPECT_THAT(llvm::enumerate(Ints, Bools, Chars),
+              ElementsAre(Tuple(0, 1, true, 'X'), Tuple(1, 2, false, 'D')));
+
+  for (auto [Idx, Int, Bool, Char] : llvm::enumerate(Ints, Bools, Chars)) {
+    (void)Idx;
+    Int = 0;
+    Bool = true;
+    Char = '!';
+  }
+
+  EXPECT_THAT(Ints, ElementsAre(0, 0));
+  EXPECT_THAT(Bools, ElementsAre(true, true));
+  EXPECT_THAT(Chars, ElementsAre('!', '!'));
+
+  // Check that we can modify the values through `.values()`.
+  size_t Iters = 0;
+  for (auto It : llvm::enumerate(Ints, Bools, Chars)) {
+    EXPECT_EQ(It.index(), Iters);
+    ++Iters;
+    auto [Int, Bool, Char] = It.value();
+    Int = 42;
+    Bool = false;
+    Char = '$';
+  }
+
+  EXPECT_THAT(Ints, ElementsAre(42, 42));
+  EXPECT_THAT(Bools, ElementsAre(false, false));
+  EXPECT_THAT(Chars, ElementsAre('$', '$'));
+}
+
+TEST(STLExtrasTest, EnumerateTemporaries) {
+  using Tuple = std::tuple<size_t, int, bool>;
+
+  EXPECT_THAT(
+      llvm::enumerate(llvm::SmallVector<int>({1, 2, 3}),
+                      std::vector<bool>({true, false, true})),
+      ElementsAre(Tuple(0, 1, true), Tuple(1, 2, false), Tuple(2, 3, true)));
+
+  size_t Iters = 0;
+  // This is fine from the point of view of range lifetimes because `zippy` will
+  // move all temporaries into its storage. No lifetime extension is necessary.
+  for (auto [Idx, Int, Bool] :
+       llvm::enumerate(llvm::SmallVector<int>({1, 2, 3}),
+                       std::vector<bool>({true, false, true}))) {
+    EXPECT_EQ(Idx, Iters);
+    ++Iters;
+    Int = 0;
+    Bool = true;
+  }
+
+  Iters = 0;
+  // The same thing but with the result as a const reference.
+  for (const auto &[Idx, Int, Bool] :
+       llvm::enumerate(llvm::SmallVector<int>({1, 2, 3}),
+                       std::vector<bool>({true, false, true}))) {
+    EXPECT_EQ(Idx, Iters);
+    ++Iters;
+    Int = 0;
+    Bool = true;
+  }
+}
+
+#if defined(GTEST_HAS_DEATH_TEST) && !defined(NDEBUG)
+TEST(STLExtrasTest, EnumerateDifferentLengths) {
+  std::vector<int> Ints = {0, 1};
+  bool Bools[] = {true, false, true};
+  std::string Chars = "abc";
+  EXPECT_DEATH(llvm::enumerate(Ints, Bools, Chars),
+               "Ranges have different length");
+  EXPECT_DEATH(llvm::enumerate(Bools, Ints, Chars),
+               "Ranges have different length");
+  EXPECT_DEATH(llvm::enumerate(Bools, Chars, Ints),
+               "Ranges have different length");
+}
+#endif
+
 template <bool B> struct CanMove {};
 template <> struct CanMove<false> {
   CanMove(CanMove &&) = delete;
 
   CanMove() = default;
   CanMove(const CanMove &) = default;
 };
 
Counted(Counted &&O)
     ++M;
   }
   ~Counted() { ++D; }
 };
 
 template <bool Moveable, bool Copyable>
 struct Range : Counted<Moveable, Copyable> {
   using Counted<Moveable, Copyable>::Counted;
-  int *begin() { return nullptr; }
-  int *end() { return nullptr; }
+  int *begin() const { return nullptr; }
+  int *end() const { return nullptr; }
 };
 
 TEST(STLExtrasTest, EnumerateLifetimeSemanticsPRValue) {
   int Copies = 0;
   int Moves = 0;
   int Destructors = 0;
   {
     auto E = enumerate(Range<true, false>(Copies, Moves, Destructors));

llvm/utils/TableGen/GlobalISel/GIMatchTree.cpp

GIMatchTreeBuilderLeafInfo::GIMatchTreeBuilderLeafInfo(
     const GIMatchDag &MatchDag, void *Data)
     : Builder(Builder), Info(Name, RootIdx, Data), MatchDag(MatchDag),
       RemainingInstrNodes(BitVector(MatchDag.getNumInstrNodes(), true)),
       RemainingEdges(BitVector(MatchDag.getNumEdges(), true)),
       RemainingPredicates(BitVector(MatchDag.getNumPredicates(), true)),
       TraversableEdges(MatchDag.getNumEdges()),
       TestablePredicates(MatchDag.getNumPredicates()) {
   // Number all the predicates in this DAG
-  for (auto &P : enumerate(MatchDag.predicates())) {
+  for (auto &&P : enumerate(MatchDag.predicates())) {
     PredicateIDs.insert(std::make_pair(P.value(), P.index()));
   }
 
   // Number all the predicate dependencies in this DAG and set up a bitvector
   // for each predicate indicating the unsatisfied dependencies.
-  for (auto &Dep : enumerate(MatchDag.predicate_edges())) {
+  for (auto &&Dep : enumerate(MatchDag.predicate_edges())) {
     PredicateDepIDs.insert(std::make_pair(Dep.value(), Dep.index()));
   }
   UnsatisfiedPredDepsForPred.resize(MatchDag.getNumPredicates(),
                                     BitVector(PredicateDepIDs.size()));
-  for (auto &Dep : enumerate(MatchDag.predicate_edges())) {
+  for (auto &&Dep : enumerate(MatchDag.predicate_edges())) {
     unsigned ID = PredicateIDs.lookup(Dep.value()->getPredicate());
     UnsatisfiedPredDepsForPred[ID].set(Dep.index());
   }
 }
 
 void GIMatchTreeBuilderLeafInfo::declareInstr(const GIMatchDagInstr *Instr, unsigned ID) {
   // Record the assignment of this instr to the given ID.
   auto InfoI = InstrNodeToInfo.insert(std::make_pair(
void GIMatchTreeBuilderLeafInfo::declareInstr(const GIMatchDagInstr *Instr, unsigned ID) {
   // When we declare an instruction, we don't expose any traversable edges just
   // yet. A partitioner has to check they exist and are registers before they
   // are traversable.
 
   // When we declare an instruction, we potentially activate some predicates.
   // Mark the dependencies that are now satisfied as a result of this
   // instruction and mark any predicates whose dependencies are fully
   // satisfied.
-  for (auto &Dep : enumerate(MatchDag.predicate_edges())) {
+  for (auto &&Dep : enumerate(MatchDag.predicate_edges())) {
     if (Dep.value()->getRequiredMI() == Instr &&
         Dep.value()->getRequiredMO() == nullptr) {
-      for (auto &DepsFor : enumerate(UnsatisfiedPredDepsForPred)) {
+      for (auto &&DepsFor : enumerate(UnsatisfiedPredDepsForPred)) {
         DepsFor.value().reset(Dep.index());
         if (DepsFor.value().none())
           TestablePredicates.set(DepsFor.index());
       }
     }
   }
 }
 
 void GIMatchTreeBuilderLeafInfo::declareOperand(unsigned InstrID,
                                                 unsigned OpIdx) {
   const GIMatchDagInstr *Instr = InstrIDToInfo.lookup(InstrID)->getInstrNode();
 
   OperandIDToInfo.insert(std::make_pair(
       std::make_pair(InstrID, OpIdx),
       GIMatchTreeOperandInfo(Instr, OpIdx)));
 
   // When an operand becomes reachable, we potentially activate some traversals.
   // Record the edges that can now be followed as a result of this
   // instruction.
-  for (auto &E : enumerate(MatchDag.edges())) {
+  for (auto &&E : enumerate(MatchDag.edges())) {
     if (E.value()->getFromMI() == Instr &&
         E.value()->getFromMO()->getIdx() == OpIdx) {
       TraversableEdges.set(E.index());
     }
   }
 
   // When an operand becomes reachable, we potentially activate some predicates.
   // Clear the dependencies that are now satisfied as a result of this
   // operand and activate any predicates whose dependencies are fully
   // satisfied.
-  for (auto &Dep : enumerate(MatchDag.predicate_edges())) {
+  for (auto &&Dep : enumerate(MatchDag.predicate_edges())) {
     if (Dep.value()->getRequiredMI() == Instr && Dep.value()->getRequiredMO() &&
         Dep.value()->getRequiredMO()->getIdx() == OpIdx) {
-      for (auto &DepsFor : enumerate(UnsatisfiedPredDepsForPred)) {
+      for (auto &&DepsFor : enumerate(UnsatisfiedPredDepsForPred)) {
         DepsFor.value().reset(Dep.index());
         if (DepsFor.value().none())
           TestablePredicates.set(DepsFor.index());
       }
     }
   }
 }
 
#endif // ifndef NDEBUG
   Partitioners.erase(PartitionerI);
   LLVM_DEBUG(dbgs() << "  Selected partitioner: ";
              Partitioner->emitDescription(dbgs()); dbgs() << "\n");
 
   assert(Partitioner->getNumPartitions() > 0 &&
          "Must always partition into at least one partition");
 
   TreeNode->setNumChildren(Partitioner->getNumPartitions());
-  for (auto &C : enumerate(TreeNode->children())) {
+  for (auto &&C : enumerate(TreeNode->children())) {
     SubtreeBuilders.emplace_back(&C.value(), NextInstrID);
     Partitioner->applyForPartition(C.index(), *this, SubtreeBuilders.back());
   }
 
   TreeNode->setPartitioner(std::move(Partitioner));
 
   // Recurse into the subtree builders. Each one must get a copy of the
   // remaining partitioners as each path has to check everything.

 
 void GIMatchTreeOpcodePartitioner::applyForPartition(
     unsigned PartitionIdx, GIMatchTreeBuilder &Builder, GIMatchTreeBuilder &SubBuilder) {
   LLVM_DEBUG(dbgs() << "  Making partition " << PartitionIdx << "\n");
   const CodeGenInstruction *CGI = PartitionToInstr[PartitionIdx];
 
   BitVector PossibleLeaves = getPossibleLeavesForPartition(PartitionIdx);
   // Consume any predicates we handled.
-  for (auto &EnumeratedLeaf : enumerate(Builder.getPossibleLeaves())) {
+  for (auto &&EnumeratedLeaf : enumerate(Builder.getPossibleLeaves())) {
     if (!PossibleLeaves[EnumeratedLeaf.index()])
       continue;
 
     auto &Leaf = EnumeratedLeaf.value();
     const auto &TestedPredicatesForLeaf =
         TestedPredicates[EnumeratedLeaf.index()];
 
     for (unsigned PredIdx : TestedPredicatesForLeaf.set_bits()) {
void GIMatchTreeOpcodePartitioner::applyForPartition(
   // that check the number of operands.
   BitVector ReferencedOperands(1);
   for (auto &Leaf : NewLeaves) {
     GIMatchTreeInstrInfo *InstrInfo = Leaf.getInstrInfo(InstrID);
     // Skip any leaves that don't care about this instruction.
     if (!InstrInfo)
       continue;
     const GIMatchDagInstr *Instr = InstrInfo->getInstrNode();
-    for (auto &E : enumerate(Leaf.getMatchDag().edges())) {
+    for (auto &&E : enumerate(Leaf.getMatchDag().edges())) {
       if (E.value()->getFromMI() == Instr &&
           E.value()->getFromMO()->getIdx() < CGI->Operands.size()) {
         ReferencedOperands.resize(E.value()->getFromMO()->getIdx() + 1);
         ReferencedOperands.set(E.value()->getFromMO()->getIdx());
       }
     }
   }
   for (auto &Leaf : NewLeaves) {

 
 void GIMatchTreeVRegDefPartitioner::applyForPartition(
     unsigned PartitionIdx, GIMatchTreeBuilder &Builder,
     GIMatchTreeBuilder &SubBuilder) {
   BitVector PossibleLeaves = getPossibleLeavesForPartition(PartitionIdx);
 
   std::vector<BitVector> TraversedEdgesByNewLeaves;
   // Consume any edges we handled.
-  for (auto &EnumeratedLeaf : enumerate(Builder.getPossibleLeaves())) {
+  for (auto &&EnumeratedLeaf : enumerate(Builder.getPossibleLeaves())) {
     if (!PossibleLeaves[EnumeratedLeaf.index()])
       continue;
 
     auto &Leaf = EnumeratedLeaf.value();
     const auto &TraversedEdgesForLeaf = TraversedEdges[EnumeratedLeaf.index()];
     TraversedEdgesByNewLeaves.push_back(TraversedEdgesForLeaf);
     Leaf.RemainingEdges.reset(TraversedEdgesForLeaf);
     Leaf.TraversableEdges.reset(TraversedEdgesForLeaf);