[ADT] Make concat able to handle ranges with iterators that return by value (such as zip) (#112783)

If any iterator in the concatenation returns by value, the result must
return by value otherwise

[ADT] Make concat able to handle ranges with iterators that return by value (such as zip) (#112783)

If any iterator in the concatenation returns by value, the result must
return by value otherwise it'll produce dangling references.

(some context that may or may not be relevant to this part of the code
may be in
https://github.com/llvm/llvm-project/commit/981ce8fa15afa11d083033240edb1daff29081c7
)

An alternative to #112441

show more ...

[ADT] Relax iterator constraints on all_equal (#106400)

The previous `all_equal` implementation contained `Begin + 1`, which
implicitly requires `Begin` to model the
[random_access_iterator](https

[ADT] Relax iterator constraints on all_equal (#106400)

The previous `all_equal` implementation contained `Begin + 1`, which
implicitly requires `Begin` to model the
[random_access_iterator](https://en.cppreference.com/w/cpp/iterator/random_access_iterator)
concept due to the usage of the `+` operator. By swapping this out with
`std::next`, this method can be used with weaker iterator concepts, such
as
[forward_iterator](https://en.cppreference.com/w/cpp/iterator/forward_iterator).

---------

Co-authored-by: Jakub Kuderski <kubakuderski@gmail.com>

show more ...

[NFC][ADT] Add unit test for llvm::mismatch. (#105459)

- Add basic unit test for llvm::mismatch.

[ADT] Allow reverse to find free rbegin/rend functions (#87840)

Lift the requirement that rbegin/rend must be member functions. Also
allow the rbegin/rend to be found through Argument Dependent Loo

[ADT] Allow reverse to find free rbegin/rend functions (#87840)

Lift the requirement that rbegin/rend must be member functions. Also
allow the rbegin/rend to be found through Argument Dependent Lookup
(ADL) and add `adl_rbegin`/`adl_rend` to STLExtras.

show more ...

[LLVM][unittests] Fix type issue in STLExtrasTest.cpp

Fixes a type error in UniqueNoPred test, that is causing the
ppc64le-lld-multistage-test buildbot to fail.

[LLVM][ADT] Put both vesions of 'unique' into STLExtras.h (#82312)

Currently there are two versions of llvm::unique, one that requires a
predicate, and is in STLExtras.h; and one that does not requ

[LLVM][ADT] Put both vesions of 'unique' into STLExtras.h (#82312)

Currently there are two versions of llvm::unique, one that requires a
predicate, and is in STLExtras.h; and one that does not require a
predicate, and is in GenericUniformityImpl.h. This moves the one from
GenericUniformityImp.h to STlExtras.h, so they are both together, and
can both be easily called from other places inside LLVM.

show more ...

[ADT] Support appending multiple values (#69891)

This is so that we can append multiple values at once without having to
create a temporary array or repeatedly call `push_back`.

Use the new func

[ADT] Support appending multiple values (#69891)

This is so that we can append multiple values at once without having to
create a temporary array or repeatedly call `push_back`.

Use the new function `append_values` to clean up the SPIR-V serializer
code. (NFC)

show more ...

[ADT] Add detection utility for incomplete types (#65495)

This allows us to produce better error messages for types that were only
forward-declared, but where a full definition was expected.

The

[ADT] Add detection utility for incomplete types (#65495)

This allows us to produce better error messages for types that were only
forward-declared, but where a full definition was expected.

The first user will be https://reviews.llvm.org/D159013; this change is
sent to review separately to reduce the scope of the other patch.

show more ...

[ADT] Add `llvm::range_size` function for generic ranges

This function follows `std::ranges::size` from C++20. It is intended
mainly for generic code that does not know the exact range type.
I did n

[ADT] Add `llvm::range_size` function for generic ranges

This function follows `std::ranges::size` from C++20. It is intended
mainly for generic code that does not know the exact range type.
I did not modify the existing `llvm::size` function because it has a strict
guarantee of O(1) running time, and we cannot guarantee that when we delegate
size check to user-defined size functions.

Use `range_size` to optimize size checks in `zip`* and `enumerate`
functions. Before that, we would have to perform linear scans for ranges
without random access iterators.

This is the last change I have planned in the series that overhauls
`zip`* and `enumerate`.

Reviewed By: dblaikie, zero9178

Differential Revision: https://reviews.llvm.org/D146231

show more ...

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

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

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

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.

Reviewed By: dblaikie, zero9178

Differential Revision: https://reviews.llvm.org/D144503

show more ...

[ADT] Make llvm::is_contained call member `contains` or `find` when available

This makes it so that calling `llvm::is_contained` no longer degrades
performance over member contains, even though both

[ADT] Make llvm::is_contained call member `contains` or `find` when available

This makes it so that calling `llvm::is_contained` no longer degrades
performance over member contains, even though both have almost identical
names. This would be the case in most set/map classes that can check for
an element being present in O(1) or O(log n) time vs. linear scan with
`std::find`. For C++17 maps/sets without `.contains`, use `.find` when available,
falling back to a linear scan with `std::find`.

I also considered detecting member contains and triggering a
`static_assert` instead, but decided against it because it's just as easy
to do the right thing and call `.contains`. This would also make some code fail
only when compiled in the C++20 mode when more container types come with
`.contains` member functions.

This was actually already the case with `CommandLine.h` calling `is_contained`
on `SmallPtrSet` and in a recent BOLT patch.

Reviewed By: kazu, dblaikie, MaskRay

Differential Revision: https://reviews.llvm.org/D146061

show more ...

[STLExtras] Use std::get in less_first,less_second to support more types

Update less_first,less_second to use std::get to access the first and
second component. This extends support to any type impl

[STLExtras] Use std::get in less_first,less_second to support more types

Update less_first,less_second to use std::get to access the first and
second component. This extends support to any type implementing
std::get, like tuples.

Reviewed By: dblaikie

Differential Revision: https://reviews.llvm.org/D145489

show more ...

[ADT] Drop append_range test that doesn't compile with EXPENSIVE_CHECKS

The issue seems to be caused by the definition of `SafeIntIterator` and
is otherwise unrelated to the implementation of `appen

[ADT] Drop append_range test that doesn't compile with EXPENSIVE_CHECKS

The issue seems to be caused by the definition of `SafeIntIterator` and
is otherwise unrelated to the implementation of `append_range`.

We have a simialr test below, so this does not meaningfully decrease the
test coverage of `append_range`.

See the discussion in: https://reviews.llvm.org/D144420#4164373

Issue: https://github.com/llvm/llvm-project/issues/61122

show more ...

[ADT] Use `adl_begin`/`end` in `enumerate`

This allows `enumerate` to work with range types that expose custom
`begin`/`end` functions.

This is a cleanup in preparation for future changes in
https:

[ADT] Use `adl_begin`/`end` in `enumerate`

This allows `enumerate` to work with range types that expose custom
`begin`/`end` functions.

This is a cleanup in preparation for future changes in
https://reviews.llvm.org/D144503.

Reviewed By: zero9178

Differential Revision: https://reviews.llvm.org/D145026

show more ...

[ADT] Fix definition of `adl_begin`/`adl_end` and `Iter`/`ValueOfRange`

- Make `IterOfRange` and `ValueOfRange` work with types that require
custom `begin`/`end` functions.
- Allow for `adl_begin`

[ADT] Fix definition of `adl_begin`/`adl_end` and `Iter`/`ValueOfRange`

- Make `IterOfRange` and `ValueOfRange` work with types that require
custom `begin`/`end` functions.
- Allow for `adl_begin`/`adl_end` to be used in constant-evaluated
contexts.
- Use SFINAE-friendly trailing return type deductions `adl_begin`/`adl_end` so that they are useable in template argument deduction.
- Add missing documentation comments.

This is required for future work in https://reviews.llvm.org/D144503.

Reviewed By: dblaikie, zero9178

Differential Revision: https://reviews.llvm.org/D144583

show more ...

Reland "[ADT] Relax type requirements for `is_contained`"

Revert "[ADT] Relax type requirements for `is_contained`"

This reverts commit 75272d5c1299db93aa619fc9e616832f578726c2.

This fails to compile on the clang-debian-cpp20 buildbot:
https://lab.llvm.or

Revert "[ADT] Relax type requirements for `is_contained`"

This reverts commit 75272d5c1299db93aa619fc9e616832f578726c2.

This fails to compile on the clang-debian-cpp20 buildbot:
https://lab.llvm.org/buildbot#builders/249/builds/945.

show more ...

[STLExtras] Allow for non-member `begin`/`end` in `append_range`

This makes `append_range` useable with, C arrays and types with custom
`begin`/`end` functions.

Reviewed By: kazu

Differential Revi

[STLExtras] Allow for non-member `begin`/`end` in `append_range`

This makes `append_range` useable with, C arrays and types with custom
`begin`/`end` functions.

Reviewed By: kazu

Differential Revision: https://reviews.llvm.org/D144420

show more ...

[ADT] Relax type requirements for `is_contained`

- Do not require both the `Set` and `Element` to be exactly the same type and, instead, only require them to be comparable.
- Do not require `Element

[ADT] Relax type requirements for `is_contained`

- Do not require both the `Set` and `Element` to be exactly the same type and, instead, only require them to be comparable.
- Do not require `Element` to be copyable.
- Add missing documentation comment.

Reviewed By: beanz

Differential Revision: https://reviews.llvm.org/D144416

show more ...

[llvm] Deprecate llvm::empty (NFC)

This patch deprecates llvm::empty as I've migrated all known uses of
llvm::empty(x) to x.empty().

Differential Revision: https://reviews.llvm.org/D134141

[ADT] Deprecate is_splat and replace all uses with all_equal

See the discussion thread for more details:
https://discourse.llvm.org/t/adt-is-splat-and-empty-ranges/64692

Reviewed By: dblaikie

Diff

[ADT] Deprecate is_splat and replace all uses with all_equal

See the discussion thread for more details:
https://discourse.llvm.org/t/adt-is-splat-and-empty-ranges/64692

Reviewed By: dblaikie

Differential Revision: https://reviews.llvm.org/D132335

show more ...

[ADT] Add all_equal predicate

`llvm::all_equal` checks if all values in the given range are equal, i.e., there are no two elements that are not equal.
Similar to `llvm::all_of`, it returns `true` wh

[ADT] Add all_equal predicate

`llvm::all_equal` checks if all values in the given range are equal, i.e., there are no two elements that are not equal.
Similar to `llvm::all_of`, it returns `true` when the range is empty.

`llvm::all_equal` is intended to supersede `llvm::is_splat`, which will be deprecated and removed in future patches.
See the discussion thread for more details:
https://discourse.llvm.org/t/adt-is-splat-and-empty-ranges/64692.

Reviewed By: dblaikie, shchenz

Differential Revision: https://reviews.llvm.org/D132334

show more ...

[llvm][ADT] Allow using structured bindings with `llvm::enumerate`

This patch adds the ability to deconstruct the `value_type` returned by `llvm::enumarate` into index and value of the wrapping rang

[llvm][ADT] Allow using structured bindings with `llvm::enumerate`

This patch adds the ability to deconstruct the `value_type` returned by `llvm::enumarate` into index and value of the wrapping range. Main use case is the common occurence of using it during loop iteration. After this patch it'd then be possible to write code such as:
```
for (auto [index, value] : enumerate(container)) {
...
}
```
where `index` is the current index and `value` a reference to elements in the given container.

Differential Revision: https://reviews.llvm.org/D131486

show more ...

[ADT] Retire llvm::apply_tuple in favor of C++17 std::apply

[ADT] Add is_splat overload accepting initializer_list

Allow for `is_splat` to be used inline, similar to `is_contained`, e.g.,
```
if (is_splat({type1, type2, type3, type4}))
...
```

which is mu

[ADT] Add is_splat overload accepting initializer_list

Allow for `is_splat` to be used inline, similar to `is_contained`, e.g.,
```
if (is_splat({type1, type2, type3, type4}))
...
```

which is much more concise and less typo-prone than an equivalent chain of equality comparisons.

My immediate motivation is to clean up some code in the SPIR-V dialect that currently needs to either construct a temporary container or use `makeArrayRef` before calling `is_splat`.

Reviewed By: dblaikie

Differential Revision: https://reviews.llvm.org/D131289

show more ...