1	//===- STLExtrasTest.cpp - Unit tests for STL extras ----------------------===//
2	//
3	// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4	// See https://llvm.org/LICENSE.txt for license information.
5	// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6	//
7	//===----------------------------------------------------------------------===//
8
9	#include "llvm/ADT/STLExtras.h"
10	#include "llvm/ADT/StringRef.h"
11	#include "gmock/gmock.h"
12	#include "gtest/gtest.h"
13
14	#include <array>
15	#include <climits>
16	#include <cstddef>
17	#include <initializer_list>
18	#include <list>
19	#include <tuple>
20	#include <type_traits>
21	#include <unordered_set>
22	#include <utility>
23	#include <vector>
24
25	using namespace llvm;
26
27	using testing::ElementsAre;
28	using testing::UnorderedElementsAre;
29
30	namespace {
31
32	int f(rank<0>) { return 0; }
33	int f(rank<1>) { return 1; }
34	int f(rank<2>) { return 2; }
35	int f(rank<4>) { return 4; }
36
37	TEST(STLExtrasTest, Rank) {
38	// We shouldn't get ambiguities and should select the overload of the same
39	// rank as the argument.
40	EXPECT_EQ(0, f(rank<0>()));
41	EXPECT_EQ(1, f(rank<1>()));
42	EXPECT_EQ(2, f(rank<2>()));
43
44	// This overload is missing so we end up back at 2.
45	EXPECT_EQ(2, f(rank<3>()));
46
47	// But going past 3 should work fine.
48	EXPECT_EQ(4, f(rank<4>()));
49
50	// And we can even go higher and just fall back to the last overload.
51	EXPECT_EQ(4, f(rank<5>()));
52	EXPECT_EQ(4, f(rank<6>()));
53	}
54
55	TEST(STLExtrasTest, EnumerateLValue) {
56	// Test that a simple LValue can be enumerated and gives correct results with
57	// multiple types, including the empty container.
58	std::vector<char> foo = {'a', 'b', 'c'};
59	typedef std::pair<std::size_t, char> CharPairType;
60	std::vector<CharPairType> CharResults;
61
62	for (auto [index, value] : llvm::enumerate(First&: foo)) {
63	CharResults.emplace_back(args&: index, args&: value);
64	}
65
66	EXPECT_THAT(CharResults,
67	ElementsAre(CharPairType(0u, 'a'), CharPairType(1u, 'b'),
68	CharPairType(2u, 'c')));
69
70	// Test a const range of a different type.
71	typedef std::pair<std::size_t, int> IntPairType;
72	std::vector<IntPairType> IntResults;
73	const std::vector<int> bar = {1, 2, 3};
74	for (auto [index, value] : llvm::enumerate(First: bar)) {
75	IntResults.emplace_back(args&: index, args: value);
76	}
77	EXPECT_THAT(IntResults, ElementsAre(IntPairType(0u, 1), IntPairType(1u, 2),
78	IntPairType(2u, 3)));
79
80	// Test an empty range.
81	IntResults.clear();
82	const std::vector<int> baz{};
83	for (auto [index, value] : llvm::enumerate(First: baz)) {
84	IntResults.emplace_back(args&: index, args: value);
85	}
86	EXPECT_TRUE(IntResults.empty());
87	}
88
89	TEST(STLExtrasTest, EnumerateModifyLValue) {
90	// Test that you can modify the underlying entries of an lvalue range through
91	// the enumeration iterator.
92	std::vector<char> foo = {'a', 'b', 'c'};
93
94	for (auto X : llvm::enumerate(First&: foo)) {
95	++X.value();
96	}
97	EXPECT_THAT(foo, ElementsAre('b', 'c', 'd'));
98
99	// Also test if this works with structured bindings.
100	foo = {'a', 'b', 'c'};
101
102	for (auto [index, value] : llvm::enumerate(First&: foo)) {
103	++value;
104	}
105	EXPECT_THAT(foo, ElementsAre('b', 'c', 'd'));
106	}
107
108	TEST(STLExtrasTest, EnumerateRValueRef) {
109	// Test that an rvalue can be enumerated.
110	typedef std::pair<std::size_t, int> PairType;
111	std::vector<PairType> Results;
112
113	auto Enumerator = llvm::enumerate(First: std::vector<int>{1, 2, 3});
114
115	for (auto X : llvm::enumerate(First: std::vector<int>{1, 2, 3})) {
116	Results.emplace_back(args: X.index(), args&: X.value());
117	}
118
119	EXPECT_THAT(Results,
120	ElementsAre(PairType(0u, 1), PairType(1u, 2), PairType(2u, 3)));
121
122	// Also test if this works with structured bindings.
123	Results.clear();
124
125	for (auto [index, value] : llvm::enumerate(First: std::vector<int>{1, 2, 3})) {
126	Results.emplace_back(args&: index, args&: value);
127	}
128
129	EXPECT_THAT(Results,
130	ElementsAre(PairType(0u, 1), PairType(1u, 2), PairType(2u, 3)));
131	}
132
133	TEST(STLExtrasTest, EnumerateModifyRValue) {
134	// Test that when enumerating an rvalue, modification still works (even if
135	// this isn't terribly useful, it at least shows that we haven't snuck an
136	// extra const in there somewhere.
137	typedef std::pair<std::size_t, char> PairType;
138	std::vector<PairType> Results;
139
140	for (auto X : llvm::enumerate(First: std::vector<char>{'1', '2', '3'})) {
141	++X.value();
142	Results.emplace_back(args: X.index(), args&: X.value());
143	}
144
145	EXPECT_THAT(Results, ElementsAre(PairType(0u, '2'), PairType(1u, '3'),
146	PairType(2u, '4')));
147
148	// Also test if this works with structured bindings.
149	Results.clear();
150
151	for (auto [index, value] :
152	llvm::enumerate(First: std::vector<char>{'1', '2', '3'})) {
153	++value;
154	Results.emplace_back(args&: index, args&: value);
155	}
156
157	EXPECT_THAT(Results, ElementsAre(PairType(0u, '2'), PairType(1u, '3'),
158	PairType(2u, '4')));
159	}
160
161	TEST(STLExtrasTest, EnumerateTwoRanges) {
162	using Tuple = std::tuple<size_t, int, bool>;
163
164	std::vector<int> Ints = {1, 2};
165	std::vector<bool> Bools = {true, false};
166	EXPECT_THAT(llvm::enumerate(Ints, Bools),
167	ElementsAre(Tuple(0, 1, true), Tuple(1, 2, false)));
168
169	// Check that we can modify the values when the temporary is a const
170	// reference.
171	for (const auto &[Idx, Int, Bool] : llvm::enumerate(First&: Ints, Rest&: Bools)) {
172	(void)Idx;
173	Bool = false;
174	Int = -1;
175	}
176
177	EXPECT_THAT(Ints, ElementsAre(-1, -1));
178	EXPECT_THAT(Bools, ElementsAre(false, false));
179
180	// Check that we can modify the values when the result gets copied.
181	for (auto [Idx, Bool, Int] : llvm::enumerate(First&: Bools, Rest&: Ints)) {
182	(void)Idx;
183	Int = 3;
184	Bool = true;
185	}
186
187	EXPECT_THAT(Ints, ElementsAre(3, 3));
188	EXPECT_THAT(Bools, ElementsAre(true, true));
189
190	// Check that we can modify the values through `.value()`.
191	size_t Iters = 0;
192	for (auto It : llvm::enumerate(First&: Bools, Rest&: Ints)) {
193	EXPECT_EQ(It.index(), Iters);
194	++Iters;
195
196	std::get<0>(t: It.value()) = false;
197	std::get<1>(t: It.value()) = 4;
198	}
199
200	EXPECT_THAT(Ints, ElementsAre(4, 4));
201	EXPECT_THAT(Bools, ElementsAre(false, false));
202	}
203
204	TEST(STLExtrasTest, EnumerateThreeRanges) {
205	using Tuple = std::tuple<size_t, int, bool, char>;
206
207	std::vector<int> Ints = {1, 2};
208	std::vector<bool> Bools = {true, false};
209	char Chars[] = {'X', 'D'};
210	EXPECT_THAT(llvm::enumerate(Ints, Bools, Chars),
211	ElementsAre(Tuple(0, 1, true, 'X'), Tuple(1, 2, false, 'D')));
212
213	for (auto [Idx, Int, Bool, Char] : llvm::enumerate(First&: Ints, Rest&: Bools, Rest&: Chars)) {
214	(void)Idx;
215	Int = 0;
216	Bool = true;
217	Char = '!';
218	}
219
220	EXPECT_THAT(Ints, ElementsAre(0, 0));
221	EXPECT_THAT(Bools, ElementsAre(true, true));
222	EXPECT_THAT(Chars, ElementsAre('!', '!'));
223
224	// Check that we can modify the values through `.values()`.
225	size_t Iters = 0;
226	for (auto It : llvm::enumerate(First&: Ints, Rest&: Bools, Rest&: Chars)) {
227	EXPECT_EQ(It.index(), Iters);
228	++Iters;
229	auto [Int, Bool, Char] = It.value();
230	Int = 42;
231	Bool = false;
232	Char = '$';
233	}
234
235	EXPECT_THAT(Ints, ElementsAre(42, 42));
236	EXPECT_THAT(Bools, ElementsAre(false, false));
237	EXPECT_THAT(Chars, ElementsAre('$', '$'));
238	}
239
240	TEST(STLExtrasTest, EnumerateTemporaries) {
241	using Tuple = std::tuple<size_t, int, bool>;
242
243	EXPECT_THAT(
244	llvm::enumerate(llvm::SmallVector<int>({1, 2, 3}),
245	std::vector<bool>({true, false, true})),
246	ElementsAre(Tuple(0, 1, true), Tuple(1, 2, false), Tuple(2, 3, true)));
247
248	size_t Iters = 0;
249	// This is fine from the point of view of range lifetimes because `zippy` will
250	// move all temporaries into its storage. No lifetime extension is necessary.
251	for (auto [Idx, Int, Bool] :
252	llvm::enumerate(First: llvm::SmallVector<int>({1, 2, 3}),
253	Rest: std::vector<bool>({true, false, true}))) {
254	EXPECT_EQ(Idx, Iters);
255	++Iters;
256	Int = 0;
257	Bool = true;
258	}
259
260	Iters = 0;
261	// The same thing but with the result as a const reference.
262	for (const auto &[Idx, Int, Bool] :
263	llvm::enumerate(First: llvm::SmallVector<int>({1, 2, 3}),
264	Rest: std::vector<bool>({true, false, true}))) {
265	EXPECT_EQ(Idx, Iters);
266	++Iters;
267	Int = 0;
268	Bool = true;
269	}
270	}
271
272	#if defined(GTEST_HAS_DEATH_TEST) && !defined(NDEBUG)
273	TEST(STLExtrasTest, EnumerateDifferentLengths) {
274	std::vector<int> Ints = {0, 1};
275	bool Bools[] = {true, false, true};
276	std::string Chars = "abc";
277	EXPECT_DEATH(llvm::enumerate(Ints, Bools, Chars),
278	"Ranges have different length");
279	EXPECT_DEATH(llvm::enumerate(Bools, Ints, Chars),
280	"Ranges have different length");
281	EXPECT_DEATH(llvm::enumerate(Bools, Chars, Ints),
282	"Ranges have different length");
283	}
284	#endif
285
286	template <bool B> struct CanMove {};
287	template <> struct CanMove<false> {
288	CanMove(CanMove &&) = delete;
289
290	CanMove() = default;
291	CanMove(const CanMove &) = default;
292	};
293
294	template <bool B> struct CanCopy {};
295	template <> struct CanCopy<false> {
296	CanCopy(const CanCopy &) = delete;
297
298	CanCopy() = default;
299	CanCopy(CanCopy &&) = default;
300	};
301
302	template <bool Moveable, bool Copyable>
303	class Counted : CanMove<Moveable>, CanCopy<Copyable> {
304	int &C;
305	int &M;
306	int &D;
307
308	public:
309	explicit Counted(int &C, int &M, int &D) : C(C), M(M), D(D) {}
310	Counted(const Counted &O) : CanCopy<Copyable>(O), C(O.C), M(O.M), D(O.D) {
311	++C;
312	}
313	Counted(Counted &&O)
314	: CanMove<Moveable>(std::move(O)), C(O.C), M(O.M), D(O.D) {
315	++M;
316	}
317	~Counted() { ++D; }
318	};
319
320	template <bool Moveable, bool Copyable>
321	struct Range : Counted<Moveable, Copyable> {
322	using Counted<Moveable, Copyable>::Counted;
323	int *begin() const { return nullptr; }
324	int *end() const { return nullptr; }
325	};
326
327	TEST(STLExtrasTest, EnumerateLifetimeSemanticsPRValue) {
328	int Copies = 0;
329	int Moves = 0;
330	int Destructors = 0;
331	{
332	auto E = enumerate(First: Range<true, false>(Copies, Moves, Destructors));
333	(void)E;
334	// Doesn't compile. rvalue ranges must be moveable.
335	// auto E2 = enumerate(Range<false, true>(Copies, Moves, Destructors));
336	EXPECT_EQ(0, Copies);
337	EXPECT_EQ(1, Moves);
338	EXPECT_EQ(1, Destructors);
339	}
340	EXPECT_EQ(0, Copies);
341	EXPECT_EQ(1, Moves);
342	EXPECT_EQ(2, Destructors);
343	}
344
345	TEST(STLExtrasTest, EnumerateLifetimeSemanticsRValue) {
346	// With an rvalue, it should not be destroyed until the end of the scope.
347	int Copies = 0;
348	int Moves = 0;
349	int Destructors = 0;
350	{
351	Range<true, false> R(Copies, Moves, Destructors);
352	{
353	auto E = enumerate(First: std::move(R));
354	(void)E;
355	// Doesn't compile. rvalue ranges must be moveable.
356	// auto E2 = enumerate(Range<false, true>(Copies, Moves, Destructors));
357	EXPECT_EQ(0, Copies);
358	EXPECT_EQ(1, Moves);
359	EXPECT_EQ(0, Destructors);
360	}
361	EXPECT_EQ(0, Copies);
362	EXPECT_EQ(1, Moves);
363	EXPECT_EQ(1, Destructors);
364	}
365	EXPECT_EQ(0, Copies);
366	EXPECT_EQ(1, Moves);
367	EXPECT_EQ(2, Destructors);
368	}
369
370	TEST(STLExtrasTest, EnumerateLifetimeSemanticsLValue) {
371	// With an lvalue, it should not be destroyed even after the end of the scope.
372	// lvalue ranges need be neither copyable nor moveable.
373	int Copies = 0;
374	int Moves = 0;
375	int Destructors = 0;
376	{
377	Range<false, false> R(Copies, Moves, Destructors);
378	{
379	auto E = enumerate(First&: R);
380	(void)E;
381	EXPECT_EQ(0, Copies);
382	EXPECT_EQ(0, Moves);
383	EXPECT_EQ(0, Destructors);
384	}
385	EXPECT_EQ(0, Copies);
386	EXPECT_EQ(0, Moves);
387	EXPECT_EQ(0, Destructors);
388	}
389	EXPECT_EQ(0, Copies);
390	EXPECT_EQ(0, Moves);
391	EXPECT_EQ(1, Destructors);
392	}
393
394	namespace some_namespace {
395	struct some_struct {
396	std::vector<int> data;
397	std::string swap_val;
398	};
399
400	std::vector<int>::const_iterator begin(const some_struct &s) {
401	return s.data.begin();
402	}
403
404	std::vector<int>::const_iterator end(const some_struct &s) {
405	return s.data.end();
406	}
407
408	std::vector<int>::const_reverse_iterator rbegin(const some_struct &s) {
409	return s.data.rbegin();
410	}
411
412	std::vector<int>::const_reverse_iterator rend(const some_struct &s) {
413	return s.data.rend();
414	}
415
416	void swap(some_struct &lhs, some_struct &rhs) {
417	// make swap visible as non-adl swap would even seem to
418	// work with std::swap which defaults to moving
419	lhs.swap_val = "lhs";
420	rhs.swap_val = "rhs";
421	}
422
423	struct requires_move {};
424	int *begin(requires_move &&) { return nullptr; }
425	int *end(requires_move &&) { return nullptr; }
426	} // namespace some_namespace
427
428	TEST(STLExtrasTest, EnumerateCustomBeginEnd) {
429	// Check that `enumerate` uses ADL to find `begin`/`end` iterators
430	// of the enumerated type.
431	some_namespace::some_struct X{};
432	X.data = {1, 2, 3};
433
434	unsigned Iters = 0;
435	for (auto [Idx, Val] : enumerate(First&: X)) {
436	EXPECT_EQ(Val, X.data[Idx]);
437	++Iters;
438	}
439	EXPECT_EQ(Iters, 3u);
440	}
441
442	TEST(STLExtrasTest, CountAdaptor) {
443	std::vector<int> v;
444
445	v.push_back(x: 1);
446	v.push_back(x: 2);
447	v.push_back(x: 1);
448	v.push_back(x: 4);
449	v.push_back(x: 3);
450	v.push_back(x: 2);
451	v.push_back(x: 1);
452
453	EXPECT_EQ(3, count(v, 1));
454	EXPECT_EQ(2, count(v, 2));
455	EXPECT_EQ(1, count(v, 3));
456	EXPECT_EQ(1, count(v, 4));
457	}
458
459	TEST(STLExtrasTest, for_each) {
460	std::vector<int> v{0, 1, 2, 3, 4};
461	int count = 0;
462
463	llvm::for_each(Range&: v, F: [&count](int) { ++count; });
464	EXPECT_EQ(5, count);
465	}
466
467	TEST(STLExtrasTest, ToVector) {
468	std::vector<char> v = {'a', 'b', 'c'};
469	auto Enumerated = to_vector<4>(Range: enumerate(First&: v));
470	ASSERT_EQ(3u, Enumerated.size());
471	for (size_t I = 0; I < v.size(); ++I) {
472	EXPECT_EQ(I, Enumerated[I].index());
473	EXPECT_EQ(v[I], Enumerated[I].value());
474	}
475
476	auto EnumeratedImplicitSize = to_vector(Range: enumerate(First&: v));
477	ASSERT_EQ(3u, EnumeratedImplicitSize.size());
478	for (size_t I = 0; I < v.size(); ++I) {
479	EXPECT_EQ(I, EnumeratedImplicitSize[I].index());
480	EXPECT_EQ(v[I], EnumeratedImplicitSize[I].value());
481	}
482	}
483
484	TEST(STLExtrasTest, ConcatRange) {
485	std::vector<int> Expected = {1, 2, 3, 4, 5, 6, 7, 8};
486	std::vector<int> Test;
487
488	std::vector<int> V1234 = {1, 2, 3, 4};
489	std::list<int> L56 = {5, 6};
490	SmallVector<int, 2> SV78 = {7, 8};
491
492	// Use concat across different sized ranges of different types with different
493	// iterators.
494	for (int &i : concat<int>(Ranges&: V1234, Ranges&: L56, Ranges&: SV78))
495	Test.push_back(x: i);
496	EXPECT_EQ(Expected, Test);
497
498	// Use concat between a temporary, an L-value, and an R-value to make sure
499	// complex lifetimes work well.
500	Test.clear();
501	for (int &i : concat<int>(Ranges: std::vector<int>(V1234), Ranges&: L56, Ranges: std::move(SV78)))
502	Test.push_back(x: i);
503	EXPECT_EQ(Expected, Test);
504	}
505
506	TEST(STLExtrasTest, PartitionAdaptor) {
507	std::vector<int> V = {1, 2, 3, 4, 5, 6, 7, 8};
508
509	auto I = partition(Range&: V, P: [](int i) { return i % 2 == 0; });
510	ASSERT_EQ(V.begin() + 4, I);
511
512	// Sort the two halves as partition may have messed with the order.
513	llvm::sort(Start: V.begin(), End: I);
514	llvm::sort(Start: I, End: V.end());
515
516	EXPECT_EQ(2, V[0]);
517	EXPECT_EQ(4, V[1]);
518	EXPECT_EQ(6, V[2]);
519	EXPECT_EQ(8, V[3]);
520	EXPECT_EQ(1, V[4]);
521	EXPECT_EQ(3, V[5]);
522	EXPECT_EQ(5, V[6]);
523	EXPECT_EQ(7, V[7]);
524	}
525
526	TEST(STLExtrasTest, EraseIf) {
527	std::vector<int> V = {1, 2, 3, 4, 5, 6, 7, 8};
528
529	erase_if(C&: V, P: [](int i) { return i % 2 == 0; });
530	EXPECT_EQ(4u, V.size());
531	EXPECT_EQ(1, V[0]);
532	EXPECT_EQ(3, V[1]);
533	EXPECT_EQ(5, V[2]);
534	EXPECT_EQ(7, V[3]);
535	}
536
537	TEST(STLExtrasTest, AppendRange) {
538	std::vector<int> V = {1, 2};
539	auto AppendVals1 = {3};
540	append_range(C&: V, R&: AppendVals1);
541	EXPECT_THAT(V, ElementsAre(1, 2, 3));
542
543	int AppendVals2[] = {4, 5};
544	append_range(C&: V, R&: AppendVals2);
545	EXPECT_THAT(V, ElementsAre(1, 2, 3, 4, 5));
546
547	std::string Str;
548	append_range(C&: Str, R: "abc");
549	EXPECT_THAT(Str, ElementsAre('a', 'b', 'c', '\0'));
550	append_range(C&: Str, R: "def");
551	EXPECT_THAT(Str, ElementsAre('a', 'b', 'c', '\0', 'd', 'e', 'f', '\0'));
552	}
553
554	TEST(STLExtrasTest, AppendValues) {
555	std::vector<int> Vals = {1, 2};
556	append_values(C&: Vals, Values: 3);
557	EXPECT_THAT(Vals, ElementsAre(1, 2, 3));
558
559	append_values(C&: Vals, Values: 4, Values: 5);
560	EXPECT_THAT(Vals, ElementsAre(1, 2, 3, 4, 5));
561
562	std::vector<StringRef> Strs;
563	std::string A = "A";
564	std::string B = "B";
565	std::string C = "C";
566	append_values(C&: Strs, Values&: A, Values&: B);
567	EXPECT_THAT(Strs, ElementsAre(A, B));
568	append_values(C&: Strs, Values&: C);
569	EXPECT_THAT(Strs, ElementsAre(A, B, C));
570
571	std::unordered_set<int> Set;
572	append_values(C&: Set, Values: 1, Values: 2);
573	EXPECT_THAT(Set, UnorderedElementsAre(1, 2));
574	append_values(C&: Set, Values: 3, Values: 1);
575	EXPECT_THAT(Set, UnorderedElementsAre(1, 2, 3));
576	}
577
578	TEST(STLExtrasTest, ADLTest) {
579	some_namespace::some_struct s{.data: {1, 2, 3, 4, 5}, .swap_val: ""};
580	some_namespace::some_struct s2{.data: {2, 4, 6, 8, 10}, .swap_val: ""};
581
582	EXPECT_EQ(*adl_begin(s), 1);
583	EXPECT_EQ(*(adl_end(s) - 1), 5);
584	EXPECT_EQ(*adl_rbegin(s), 5);
585	EXPECT_EQ(*(adl_rend(s) - 1), 1);
586
587	adl_swap(lhs&: s, rhs&: s2);
588	EXPECT_EQ(s.swap_val, "lhs");
589	EXPECT_EQ(s2.swap_val, "rhs");
590
591	int count = 0;
592	llvm::for_each(Range&: s, F: [&count](int) { ++count; });
593	EXPECT_EQ(count, 5);
594	}
595
596	TEST(STLExtrasTest, ADLTestTemporaryRange) {
597	EXPECT_EQ(adl_begin(some_namespace::requires_move{}), nullptr);
598	EXPECT_EQ(adl_end(some_namespace::requires_move{}), nullptr);
599	}
600
601	TEST(STLExtrasTest, ADLTestConstexpr) {
602	// `std::begin`/`std::end` are marked as `constexpr`; check that
603	// `adl_begin`/`adl_end` also work in constant-evaluated contexts.
604	static constexpr int c_arr[] = {7, 8, 9};
605	static_assert(adl_begin(range: c_arr) == c_arr);
606	static_assert(adl_end(range: c_arr) == c_arr + 3);
607
608	static constexpr std::array<int, 2> std_arr = {1, 2};
609	static_assert(adl_begin(range: std_arr) == std_arr.begin());
610	static_assert(adl_end(range: std_arr) == std_arr.end());
611	SUCCEED();
612	}
613
614	struct FooWithMemberSize {
615	size_t size() const { return 42; }
616	auto begin() { return Data.begin(); }
617	auto end() { return Data.end(); }
618
619	std::set<int> Data;
620	};
621
622	namespace some_namespace {
623	struct FooWithFreeSize {
624	auto begin() { return Data.begin(); }
625	auto end() { return Data.end(); }
626
627	std::set<int> Data;
628	};
629
630	size_t size(const FooWithFreeSize &) { return 13; }
631	} // namespace some_namespace
632
633	TEST(STLExtrasTest, ADLSizeTest) {
634	FooWithMemberSize foo1;
635	EXPECT_EQ(adl_size(foo1), 42u);
636
637	some_namespace::FooWithFreeSize foo2;
638	EXPECT_EQ(adl_size(foo2), 13u);
639
640	static constexpr int c_arr[] = {1, 2, 3};
641	static_assert(adl_size(range: c_arr) == 3u);
642
643	static constexpr std::array<int, 4> cpp_arr = {};
644	static_assert(adl_size(range: cpp_arr) == 4u);
645	}
646
647	TEST(STLExtrasTest, DropBeginTest) {
648	SmallVector<int, 5> vec{0, 1, 2, 3, 4};
649
650	for (int n = 0; n < 5; ++n) {
651	int i = n;
652	for (auto &v : drop_begin(RangeOrContainer&: vec, N: n)) {
653	EXPECT_EQ(v, i);
654	i += 1;
655	}
656	EXPECT_EQ(i, 5);
657	}
658	}
659
660	TEST(STLExtrasTest, DropBeginDefaultTest) {
661	SmallVector<int, 5> vec{0, 1, 2, 3, 4};
662
663	int i = 1;
664	for (auto &v : drop_begin(RangeOrContainer&: vec)) {
665	EXPECT_EQ(v, i);
666	i += 1;
667	}
668	EXPECT_EQ(i, 5);
669	}
670
671	TEST(STLExtrasTest, DropEndTest) {
672	SmallVector<int, 5> vec{0, 1, 2, 3, 4};
673
674	for (int n = 0; n < 5; ++n) {
675	int i = 0;
676	for (auto &v : drop_end(RangeOrContainer&: vec, N: n)) {
677	EXPECT_EQ(v, i);
678	i += 1;
679	}
680	EXPECT_EQ(i, 5 - n);
681	}
682	}
683
684	TEST(STLExtrasTest, DropEndDefaultTest) {
685	SmallVector<int, 5> vec{0, 1, 2, 3, 4};
686
687	int i = 0;
688	for (auto &v : drop_end(RangeOrContainer&: vec)) {
689	EXPECT_EQ(v, i);
690	i += 1;
691	}
692	EXPECT_EQ(i, 4);
693	}
694
695	TEST(STLExtrasTest, EarlyIncrementTest) {
696	std::list<int> L = {1, 2, 3, 4};
697
698	auto EIR = make_early_inc_range(Range&: L);
699
700	auto I = EIR.begin();
701	auto EI = EIR.end();
702	EXPECT_NE(I, EI);
703
704	EXPECT_EQ(1, *I);
705	#if LLVM_ENABLE_ABI_BREAKING_CHECKS
706	#ifndef NDEBUG
707	// Repeated dereferences are not allowed.
708	EXPECT_DEATH(*I, "Cannot dereference");
709	// Comparison after dereference is not allowed.
710	EXPECT_DEATH((void)(I == EI), "Cannot compare");
711	EXPECT_DEATH((void)(I != EI), "Cannot compare");
712	#endif
713	#endif
714
715	++I;
716	EXPECT_NE(I, EI);
717	#if LLVM_ENABLE_ABI_BREAKING_CHECKS
718	#ifndef NDEBUG
719	// You cannot increment prior to dereference.
720	EXPECT_DEATH(++I, "Cannot increment");
721	#endif
722	#endif
723	EXPECT_EQ(2, *I);
724	#if LLVM_ENABLE_ABI_BREAKING_CHECKS
725	#ifndef NDEBUG
726	// Repeated dereferences are not allowed.
727	EXPECT_DEATH(*I, "Cannot dereference");
728	#endif
729	#endif
730
731	// Inserting shouldn't break anything. We should be able to keep dereferencing
732	// the currrent iterator and increment. The increment to go to the "next"
733	// iterator from before we inserted.
734	L.insert(position: std::next(x: L.begin(), n: 2), x: -1);
735	++I;
736	EXPECT_EQ(3, *I);
737
738	// Erasing the front including the current doesn't break incrementing.
739	L.erase(first: L.begin(), last: std::prev(x: L.end()));
740	++I;
741	EXPECT_EQ(4, *I);
742	++I;
743	EXPECT_EQ(EIR.end(), I);
744	}
745
746	// A custom iterator that returns a pointer when dereferenced. This is used to
747	// test make_early_inc_range with iterators that do not return a reference on
748	// dereferencing.
749	struct CustomPointerIterator
750	: public iterator_adaptor_base<CustomPointerIterator,
751	std::list<int>::iterator,
752	std::forward_iterator_tag> {
753	using base_type =
754	iterator_adaptor_base<CustomPointerIterator, std::list<int>::iterator,
755	std::forward_iterator_tag>;
756
757	explicit CustomPointerIterator(std::list<int>::iterator I) : base_type(I) {}
758
759	// Retrieve a pointer to the current int.
760	int *operator*() const { return &*base_type::wrapped(); }
761	};
762
763	// Make sure make_early_inc_range works with iterators that do not return a
764	// reference on dereferencing. The test is similar to EarlyIncrementTest, but
765	// uses CustomPointerIterator.
766	TEST(STLExtrasTest, EarlyIncrementTestCustomPointerIterator) {
767	std::list<int> L = {1, 2, 3, 4};
768
769	auto CustomRange = make_range(x: CustomPointerIterator(L.begin()),
770	y: CustomPointerIterator(L.end()));
771	auto EIR = make_early_inc_range(Range&: CustomRange);
772
773	auto I = EIR.begin();
774	auto EI = EIR.end();
775	EXPECT_NE(I, EI);
776
777	EXPECT_EQ(&*L.begin(), *I);
778	#if LLVM_ENABLE_ABI_BREAKING_CHECKS
779	#ifndef NDEBUG
780	// Repeated dereferences are not allowed.
781	EXPECT_DEATH(*I, "Cannot dereference");
782	// Comparison after dereference is not allowed.
783	EXPECT_DEATH((void)(I == EI), "Cannot compare");
784	EXPECT_DEATH((void)(I != EI), "Cannot compare");
785	#endif
786	#endif
787
788	++I;
789	EXPECT_NE(I, EI);
790	#if LLVM_ENABLE_ABI_BREAKING_CHECKS
791	#ifndef NDEBUG
792	// You cannot increment prior to dereference.
793	EXPECT_DEATH(++I, "Cannot increment");
794	#endif
795	#endif
796	EXPECT_EQ(&*std::next(L.begin()), *I);
797	#if LLVM_ENABLE_ABI_BREAKING_CHECKS
798	#ifndef NDEBUG
799	// Repeated dereferences are not allowed.
800	EXPECT_DEATH(*I, "Cannot dereference");
801	#endif
802	#endif
803
804	// Inserting shouldn't break anything. We should be able to keep dereferencing
805	// the currrent iterator and increment. The increment to go to the "next"
806	// iterator from before we inserted.
807	L.insert(position: std::next(x: L.begin(), n: 2), x: -1);
808	++I;
809	EXPECT_EQ(&*std::next(L.begin(), 3), *I);
810
811	// Erasing the front including the current doesn't break incrementing.
812	L.erase(first: L.begin(), last: std::prev(x: L.end()));
813	++I;
814	EXPECT_EQ(&*L.begin(), *I);
815	++I;
816	EXPECT_EQ(EIR.end(), I);
817	}
818
819	TEST(STLExtrasTest, AllEqual) {
820	std::vector<int> V;
821	EXPECT_TRUE(all_equal(V));
822
823	V.push_back(x: 1);
824	EXPECT_TRUE(all_equal(V));
825
826	V.push_back(x: 1);
827	V.push_back(x: 1);
828	EXPECT_TRUE(all_equal(V));
829
830	V.push_back(x: 2);
831	EXPECT_FALSE(all_equal(V));
832	}
833
834	TEST(STLExtrasTest, AllEqualInitializerList) {
835	EXPECT_TRUE(all_equal({1}));
836	EXPECT_TRUE(all_equal({1, 1}));
837	EXPECT_FALSE(all_equal({1, 2}));
838	EXPECT_FALSE(all_equal({2, 1}));
839	EXPECT_TRUE(all_equal({1, 1, 1}));
840	}
841
842	TEST(STLExtrasTest, to_address) {
843	int *V1 = new int;
844	EXPECT_EQ(V1, to_address(V1));
845
846	// Check fancy pointer overload for unique_ptr
847	std::unique_ptr<int> V2 = std::make_unique<int>(args: 0);
848	EXPECT_EQ(V2.get(), llvm::to_address(V2));
849
850	V2.reset(p: V1);
851	EXPECT_EQ(V1, llvm::to_address(V2));
852	V2.release();
853
854	// Check fancy pointer overload for shared_ptr
855	std::shared_ptr<int> V3 = std::make_shared<int>(args: 0);
856	std::shared_ptr<int> V4 = V3;
857	EXPECT_EQ(V3.get(), V4.get());
858	EXPECT_EQ(V3.get(), llvm::to_address(V3));
859	EXPECT_EQ(V4.get(), llvm::to_address(V4));
860
861	V3.reset(p: V1);
862	EXPECT_EQ(V1, llvm::to_address(V3));
863	}
864
865	TEST(STLExtrasTest, partition_point) {
866	std::vector<int> V = {1, 3, 5, 7, 9};
867
868	// Range version.
869	EXPECT_EQ(V.begin() + 3,
870	partition_point(V, [](unsigned X) { return X < 7; }));
871	EXPECT_EQ(V.begin(), partition_point(V, [](unsigned X) { return X < 1; }));
872	EXPECT_EQ(V.end(), partition_point(V, [](unsigned X) { return X < 50; }));
873	}
874
875	TEST(STLExtrasTest, hasSingleElement) {
876	const std::vector<int> V0 = {}, V1 = {1}, V2 = {1, 2};
877	const std::vector<int> V10(10);
878
879	EXPECT_EQ(hasSingleElement(V0), false);
880	EXPECT_EQ(hasSingleElement(V1), true);
881	EXPECT_EQ(hasSingleElement(V2), false);
882	EXPECT_EQ(hasSingleElement(V10), false);
883	}
884
885	TEST(STLExtrasTest, hasNItems) {
886	const std::list<int> V0 = {}, V1 = {1}, V2 = {1, 2};
887	const std::list<int> V3 = {1, 3, 5};
888
889	EXPECT_TRUE(hasNItems(V0, 0));
890	EXPECT_FALSE(hasNItems(V0, 2));
891	EXPECT_TRUE(hasNItems(V1, 1));
892	EXPECT_FALSE(hasNItems(V1, 2));
893
894	EXPECT_TRUE(hasNItems(V3.begin(), V3.end(), 3, [](int x) { return x < 10; }));
895	EXPECT_TRUE(hasNItems(V3.begin(), V3.end(), 0, [](int x) { return x > 10; }));
896	EXPECT_TRUE(hasNItems(V3.begin(), V3.end(), 2, [](int x) { return x < 5; }));
897	}
898
899	TEST(STLExtras, hasNItemsOrMore) {
900	const std::list<int> V0 = {}, V1 = {1}, V2 = {1, 2};
901	const std::list<int> V3 = {1, 3, 5};
902
903	EXPECT_TRUE(hasNItemsOrMore(V1, 1));
904	EXPECT_FALSE(hasNItemsOrMore(V1, 2));
905
906	EXPECT_TRUE(hasNItemsOrMore(V2, 1));
907	EXPECT_TRUE(hasNItemsOrMore(V2, 2));
908	EXPECT_FALSE(hasNItemsOrMore(V2, 3));
909
910	EXPECT_TRUE(hasNItemsOrMore(V3, 3));
911	EXPECT_FALSE(hasNItemsOrMore(V3, 4));
912
913	EXPECT_TRUE(
914	hasNItemsOrMore(V3.begin(), V3.end(), 3, [](int x) { return x < 10; }));
915	EXPECT_FALSE(
916	hasNItemsOrMore(V3.begin(), V3.end(), 3, [](int x) { return x > 10; }));
917	EXPECT_TRUE(
918	hasNItemsOrMore(V3.begin(), V3.end(), 2, [](int x) { return x < 5; }));
919	}
920
921	TEST(STLExtras, hasNItemsOrLess) {
922	const std::list<int> V0 = {}, V1 = {1}, V2 = {1, 2};
923	const std::list<int> V3 = {1, 3, 5};
924
925	EXPECT_TRUE(hasNItemsOrLess(V0, 0));
926	EXPECT_TRUE(hasNItemsOrLess(V0, 1));
927	EXPECT_TRUE(hasNItemsOrLess(V0, 2));
928
929	EXPECT_FALSE(hasNItemsOrLess(V1, 0));
930	EXPECT_TRUE(hasNItemsOrLess(V1, 1));
931	EXPECT_TRUE(hasNItemsOrLess(V1, 2));
932
933	EXPECT_FALSE(hasNItemsOrLess(V2, 0));
934	EXPECT_FALSE(hasNItemsOrLess(V2, 1));
935	EXPECT_TRUE(hasNItemsOrLess(V2, 2));
936	EXPECT_TRUE(hasNItemsOrLess(V2, 3));
937
938	EXPECT_FALSE(hasNItemsOrLess(V3, 0));
939	EXPECT_FALSE(hasNItemsOrLess(V3, 1));
940	EXPECT_FALSE(hasNItemsOrLess(V3, 2));
941	EXPECT_TRUE(hasNItemsOrLess(V3, 3));
942	EXPECT_TRUE(hasNItemsOrLess(V3, 4));
943
944	EXPECT_TRUE(
945	hasNItemsOrLess(V3.begin(), V3.end(), 1, [](int x) { return x == 1; }));
946	EXPECT_TRUE(
947	hasNItemsOrLess(V3.begin(), V3.end(), 2, [](int x) { return x < 5; }));
948	EXPECT_TRUE(
949	hasNItemsOrLess(V3.begin(), V3.end(), 5, [](int x) { return x < 5; }));
950	EXPECT_FALSE(
951	hasNItemsOrLess(V3.begin(), V3.end(), 2, [](int x) { return x < 10; }));
952	}
953
954	TEST(STLExtras, MoveRange) {
955	class Foo {
956	bool A;
957
958	public:
959	Foo() : A(true) {}
960	Foo(const Foo &) = delete;
961	Foo(Foo &&Other) : A(Other.A) { Other.A = false; }
962	Foo &operator=(const Foo &) = delete;
963	Foo &operator=(Foo &&Other) {
964	if (this != &Other) {
965	A = Other.A;
966	Other.A = false;
967	}
968	return *this;
969	}
970	operator bool() const { return A; }
971	};
972	SmallVector<Foo, 4U> V1, V2, V3, V4;
973	auto HasVal = [](const Foo &Item) { return static_cast<bool>(Item); };
974	auto Build = [&] {
975	SmallVector<Foo, 4U> Foos;
976	Foos.resize(N: 4U);
977	return Foos;
978	};
979
980	V1.resize(N: 4U);
981	EXPECT_TRUE(llvm::all_of(V1, HasVal));
982
983	llvm::move(Range&: V1, Out: std::back_inserter(x&: V2));
984
985	// Ensure input container is same size, but its contents were moved out.
986	EXPECT_EQ(V1.size(), 4U);
987	EXPECT_TRUE(llvm::none_of(V1, HasVal));
988
989	// Ensure output container has the contents of the input container.
990	EXPECT_EQ(V2.size(), 4U);
991	EXPECT_TRUE(llvm::all_of(V2, HasVal));
992
993	llvm::move(Range: std::move(V2), Out: std::back_inserter(x&: V3));
994
995	EXPECT_TRUE(llvm::none_of(V2, HasVal));
996	EXPECT_EQ(V3.size(), 4U);
997	EXPECT_TRUE(llvm::all_of(V3, HasVal));
998
999	llvm::move(Range: Build(), Out: std::back_inserter(x&: V4));
1000	EXPECT_EQ(V4.size(), 4U);
1001	EXPECT_TRUE(llvm::all_of(V4, HasVal));
1002	}
1003
1004	TEST(STLExtras, Unique) {
1005	std::vector<int> V = {1, 5, 5, 4, 3, 3, 3};
1006
1007	auto I = llvm::unique(R&: V, P: [](int a, int b) { return a == b; });
1008
1009	EXPECT_EQ(I, V.begin() + 4);
1010
1011	EXPECT_EQ(1, V[0]);
1012	EXPECT_EQ(5, V[1]);
1013	EXPECT_EQ(4, V[2]);
1014	EXPECT_EQ(3, V[3]);
1015	}
1016
1017	TEST(STLExtras, UniqueNoPred) {
1018	std::vector<int> V = {1, 5, 5, 4, 3, 3, 3};
1019
1020	auto I = llvm::unique(R&: V);
1021
1022	EXPECT_EQ(I, V.begin() + 4);
1023
1024	EXPECT_EQ(1, V[0]);
1025	EXPECT_EQ(5, V[1]);
1026	EXPECT_EQ(4, V[2]);
1027	EXPECT_EQ(3, V[3]);
1028	}
1029
1030	TEST(STLExtrasTest, MakeVisitorOneCallable) {
1031	auto IdentityLambda = [](auto X) { return X; };
1032	auto IdentityVisitor = makeVisitor(Callables&: IdentityLambda);
1033	EXPECT_EQ(IdentityLambda(1), IdentityVisitor(1));
1034	EXPECT_EQ(IdentityLambda(2.0f), IdentityVisitor(2.0f));
1035	EXPECT_TRUE((std::is_same<decltype(IdentityLambda(IdentityLambda)),
1036	decltype(IdentityLambda)>::value));
1037	EXPECT_TRUE((std::is_same<decltype(IdentityVisitor(IdentityVisitor)),
1038	decltype(IdentityVisitor)>::value));
1039	}
1040
1041	TEST(STLExtrasTest, MakeVisitorTwoCallables) {
1042	auto Visitor =
1043	makeVisitor(Callables: [](int) { return 0; }, Callables: [](std::string) { return 1; });
1044	EXPECT_EQ(Visitor(42), 0);
1045	EXPECT_EQ(Visitor("foo"), 1);
1046	}
1047
1048	TEST(STLExtrasTest, MakeVisitorCallableMultipleOperands) {
1049	auto Second = makeVisitor(Callables: [](int I, float F) { return F; },
1050	Callables: [](float F, int I) { return I; });
1051	EXPECT_EQ(Second(1.f, 1), 1);
1052	EXPECT_EQ(Second(1, 1.f), 1.f);
1053	}
1054
1055	TEST(STLExtrasTest, MakeVisitorDefaultCase) {
1056	{
1057	auto Visitor = makeVisitor(Callables: [](int I) { return I + 100; },
1058	Callables: [](float F) { return F * 2; },
1059	Callables: [](auto) { return -1; });
1060	EXPECT_EQ(Visitor(24), 124);
1061	EXPECT_EQ(Visitor(2.f), 4.f);
1062	EXPECT_EQ(Visitor(2.), -1);
1063	EXPECT_EQ(Visitor(Visitor), -1);
1064	}
1065	{
1066	auto Visitor = makeVisitor(Callables: [](auto) { return -1; },
1067	Callables: [](int I) { return I + 100; },
1068	Callables: [](float F) { return F * 2; });
1069	EXPECT_EQ(Visitor(24), 124);
1070	EXPECT_EQ(Visitor(2.f), 4.f);
1071	EXPECT_EQ(Visitor(2.), -1);
1072	EXPECT_EQ(Visitor(Visitor), -1);
1073	}
1074	}
1075
1076	template <bool Moveable, bool Copyable>
1077	struct Functor : Counted<Moveable, Copyable> {
1078	using Counted<Moveable, Copyable>::Counted;
1079	void operator()() {}
1080	};
1081
1082	TEST(STLExtrasTest, MakeVisitorLifetimeSemanticsPRValue) {
1083	int Copies = 0;
1084	int Moves = 0;
1085	int Destructors = 0;
1086	{
1087	auto V = makeVisitor(Callables: Functor<true, false>(Copies, Moves, Destructors));
1088	(void)V;
1089	EXPECT_EQ(0, Copies);
1090	EXPECT_EQ(1, Moves);
1091	EXPECT_EQ(1, Destructors);
1092	}
1093	EXPECT_EQ(0, Copies);
1094	EXPECT_EQ(1, Moves);
1095	EXPECT_EQ(2, Destructors);
1096	}
1097
1098	TEST(STLExtrasTest, MakeVisitorLifetimeSemanticsRValue) {
1099	int Copies = 0;
1100	int Moves = 0;
1101	int Destructors = 0;
1102	{
1103	Functor<true, false> F(Copies, Moves, Destructors);
1104	{
1105	auto V = makeVisitor(Callables: std::move(F));
1106	(void)V;
1107	EXPECT_EQ(0, Copies);
1108	EXPECT_EQ(1, Moves);
1109	EXPECT_EQ(0, Destructors);
1110	}
1111	EXPECT_EQ(0, Copies);
1112	EXPECT_EQ(1, Moves);
1113	EXPECT_EQ(1, Destructors);
1114	}
1115	EXPECT_EQ(0, Copies);
1116	EXPECT_EQ(1, Moves);
1117	EXPECT_EQ(2, Destructors);
1118	}
1119
1120	TEST(STLExtrasTest, MakeVisitorLifetimeSemanticsLValue) {
1121	int Copies = 0;
1122	int Moves = 0;
1123	int Destructors = 0;
1124	{
1125	Functor<true, true> F(Copies, Moves, Destructors);
1126	{
1127	auto V = makeVisitor(Callables&: F);
1128	(void)V;
1129	EXPECT_EQ(1, Copies);
1130	EXPECT_EQ(0, Moves);
1131	EXPECT_EQ(0, Destructors);
1132	}
1133	EXPECT_EQ(1, Copies);
1134	EXPECT_EQ(0, Moves);
1135	EXPECT_EQ(1, Destructors);
1136	}
1137	EXPECT_EQ(1, Copies);
1138	EXPECT_EQ(0, Moves);
1139	EXPECT_EQ(2, Destructors);
1140	}
1141
1142	TEST(STLExtrasTest, AllOfZip) {
1143	std::vector<int> v1 = {0, 4, 2, 1};
1144	std::vector<int> v2 = {1, 4, 3, 6};
1145	EXPECT_TRUE(all_of_zip(v1, v2, [](int v1, int v2) { return v1 <= v2; }));
1146	EXPECT_FALSE(all_of_zip(v1, v2, [](int L, int R) { return L < R; }));
1147
1148	// Triple vectors
1149	std::vector<int> v3 = {1, 6, 5, 7};
1150	EXPECT_EQ(true, all_of_zip(v1, v2, v3, [](int a, int b, int c) {
1151	return a <= b && b <= c;
1152	}));
1153	EXPECT_EQ(false, all_of_zip(v1, v2, v3, [](int a, int b, int c) {
1154	return a < b && b < c;
1155	}));
1156
1157	// Shorter vector should fail even with an always-true predicate.
1158	std::vector<int> v_short = {1, 4};
1159	EXPECT_EQ(false, all_of_zip(v1, v_short, [](int, int) { return true; }));
1160	EXPECT_EQ(false,
1161	all_of_zip(v1, v2, v_short, [](int, int, int) { return true; }));
1162	}
1163
1164	TEST(STLExtrasTest, TypesAreDistinct) {
1165	EXPECT_TRUE((llvm::TypesAreDistinct<>::value));
1166	EXPECT_TRUE((llvm::TypesAreDistinct<int>::value));
1167	EXPECT_FALSE((llvm::TypesAreDistinct<int, int>::value));
1168	EXPECT_TRUE((llvm::TypesAreDistinct<int, float>::value));
1169	EXPECT_FALSE((llvm::TypesAreDistinct<int, float, int>::value));
1170	EXPECT_TRUE((llvm::TypesAreDistinct<int, float, double>::value));
1171	EXPECT_FALSE((llvm::TypesAreDistinct<int, float, double, float>::value));
1172	EXPECT_TRUE((llvm::TypesAreDistinct<int, int *>::value));
1173	EXPECT_TRUE((llvm::TypesAreDistinct<int, int &>::value));
1174	EXPECT_TRUE((llvm::TypesAreDistinct<int, int &&>::value));
1175	EXPECT_TRUE((llvm::TypesAreDistinct<int, const int>::value));
1176	}
1177
1178	TEST(STLExtrasTest, FirstIndexOfType) {
1179	EXPECT_EQ((llvm::FirstIndexOfType<int, int>::value), 0u);
1180	EXPECT_EQ((llvm::FirstIndexOfType<int, int, int>::value), 0u);
1181	EXPECT_EQ((llvm::FirstIndexOfType<int, float, int>::value), 1u);
1182	EXPECT_EQ((llvm::FirstIndexOfType<int const *, float, int, int const *,
1183	const int>::value),
1184	2u);
1185	}
1186
1187	TEST(STLExtrasTest, TypeAtIndex) {
1188	EXPECT_TRUE((std::is_same<int, llvm::TypeAtIndex<0, int>>::value));
1189	EXPECT_TRUE((std::is_same<int, llvm::TypeAtIndex<0, int, float>>::value));
1190	EXPECT_TRUE((std::is_same<float, llvm::TypeAtIndex<1, int, float>>::value));
1191	EXPECT_TRUE(
1192	(std::is_same<float, llvm::TypeAtIndex<1, int, float, double>>::value));
1193	EXPECT_TRUE(
1194	(std::is_same<float, llvm::TypeAtIndex<1, int, float, double>>::value));
1195	EXPECT_TRUE(
1196	(std::is_same<double, llvm::TypeAtIndex<2, int, float, double>>::value));
1197	}
1198
1199	enum Doggos {
1200	Floofer,
1201	Woofer,
1202	SubWoofer,
1203	Pupper,
1204	Pupperino,
1205	Longboi,
1206	};
1207
1208	struct WooferCmp {
1209	// Not copyable.
1210	WooferCmp() = default;
1211	WooferCmp(const WooferCmp &) = delete;
1212	WooferCmp &operator=(const WooferCmp &) = delete;
1213
1214	friend bool operator==(const Doggos &Doggo, const WooferCmp &) {
1215	return Doggo == Doggos::Woofer;
1216	}
1217	};
1218
1219	TEST(STLExtrasTest, IsContainedInitializerList) {
1220	EXPECT_TRUE(is_contained({Woofer, SubWoofer}, Woofer));
1221	EXPECT_TRUE(is_contained({Woofer, SubWoofer}, SubWoofer));
1222	EXPECT_FALSE(is_contained({Woofer, SubWoofer}, Pupper));
1223
1224	// Check that the initializer list type and the element type do not have to
1225	// match exactly.
1226	EXPECT_TRUE(is_contained({Floofer, Woofer, SubWoofer}, WooferCmp{}));
1227	EXPECT_FALSE(is_contained({Floofer, SubWoofer}, WooferCmp{}));
1228
1229	EXPECT_TRUE(is_contained({"a", "bb", "ccc", "dddd"}, llvm::StringRef("ccc")));
1230	EXPECT_FALSE(is_contained({"a", "bb", "ccc", "dddd"}, llvm::StringRef("x")));
1231
1232	static_assert(is_contained(Set: {Woofer, SubWoofer}, Element: SubWoofer), "SubWoofer!");
1233	static_assert(!is_contained(Set: {Woofer, SubWoofer}, Element: Pupper), "Missing Pupper!");
1234
1235	EXPECT_TRUE(is_contained({1, 2, 3, 4}, 3));
1236	EXPECT_FALSE(is_contained({1, 2, 3, 4}, 5));
1237
1238	static_assert(is_contained(Set: {1, 2, 3, 4}, Element: 3), "It's there!");
1239	static_assert(!is_contained(Set: {1, 2, 3, 4}, Element: 5), "It's not there :(");
1240	}
1241
1242	TEST(STLExtrasTest, IsContainedMemberContains) {
1243	// Check that `llvm::is_contained` uses the member `.contains()` when
1244	// available. Check that `.contains()` is preferred over `.find()`.
1245	struct Foo {
1246	bool contains(int) const {
1247	++NumContainsCalls;
1248	return ContainsResult;
1249	}
1250	int *begin() { return nullptr; }
1251	int *end() { return nullptr; }
1252	int *find(int) { return nullptr; }
1253
1254	bool ContainsResult = false;
1255	mutable unsigned NumContainsCalls = 0;
1256	} Container;
1257
1258	EXPECT_EQ(Container.NumContainsCalls, 0u);
1259	EXPECT_FALSE(is_contained(Container, 1));
1260	EXPECT_EQ(Container.NumContainsCalls, 1u);
1261
1262	Container.ContainsResult = true;
1263	EXPECT_TRUE(is_contained(Container, 1));
1264	EXPECT_EQ(Container.NumContainsCalls, 2u);
1265	}
1266
1267	TEST(STLExtrasTest, IsContainedMemberFind) {
1268	// Check that `llvm::is_contained` uses the member `.find(x)` when available.
1269	struct Foo {
1270	auto begin() { return Data.begin(); }
1271	auto end() { return Data.end(); }
1272	auto find(int X) {
1273	++NumFindCalls;
1274	return std::find(first: begin(), last: end(), val: X);
1275	}
1276
1277	std::vector<int> Data;
1278	mutable unsigned NumFindCalls = 0;
1279	} Container;
1280
1281	Container.Data = {1, 2, 3};
1282
1283	EXPECT_EQ(Container.NumFindCalls, 0u);
1284	EXPECT_TRUE(is_contained(Container, 1));
1285	EXPECT_TRUE(is_contained(Container, 3));
1286	EXPECT_EQ(Container.NumFindCalls, 2u);
1287
1288	EXPECT_FALSE(is_contained(Container, 4));
1289	EXPECT_EQ(Container.NumFindCalls, 3u);
1290	}
1291
1292	TEST(STLExtrasTest, addEnumValues) {
1293	enum A { Zero = 0, One = 1 };
1294	enum B { IntMax = INT_MAX, ULongLongMax = ULLONG_MAX };
1295	enum class C : unsigned { Two = 2 };
1296
1297	// Non-fixed underlying types, with same underlying types
1298	static_assert(addEnumValues(LHS: Zero, RHS: One) == 1,
1299	"addEnumValues(Zero, One) failed.");
1300	static_assert(addEnumValues(LHS: IntMax, RHS: ULongLongMax) ==
1301	INT_MAX + static_cast<unsigned long long>(ULLONG_MAX),
1302	"addEnumValues(IntMax, ULongLongMax) failed.");
1303	// Non-fixed underlying types, with different underlying types
1304	static_assert(addEnumValues(LHS: Zero, RHS: IntMax) == INT_MAX,
1305	"addEnumValues(Zero, IntMax) failed.");
1306	static_assert(addEnumValues(LHS: One, RHS: ULongLongMax) ==
1307	1 + static_cast<unsigned long long>(ULLONG_MAX),
1308	"addEnumValues(One, ULongLongMax) failed.");
1309	// Non-fixed underlying type enum and fixed underlying type enum, with same
1310	// underlying types
1311	static_assert(addEnumValues(LHS: One, RHS: C::Two) == 3,
1312	"addEnumValues(One, C::Two) failed.");
1313	// Non-fixed underlying type enum and fixed underlying type enum, with
1314	// different underlying types
1315	static_assert(addEnumValues(LHS: ULongLongMax, RHS: C::Two) ==
1316	static_cast<unsigned long long>(ULLONG_MAX) + 2,
1317	"addEnumValues(ULongLongMax, C::Two) failed.");
1318	}
1319
1320	TEST(STLExtrasTest, LessFirst) {
1321	{
1322	std::pair<int, int> A(0, 1);
1323	std::pair<int, int> B(1, 0);
1324	EXPECT_TRUE(less_first()(A, B));
1325	EXPECT_FALSE(less_first()(B, A));
1326	}
1327
1328	{
1329	std::tuple<int, int> A(0, 1);
1330	std::tuple<int, int> B(1, 0);
1331	EXPECT_TRUE(less_first()(A, B));
1332	EXPECT_FALSE(less_first()(B, A));
1333	}
1334	}
1335
1336	TEST(STLExtrasTest, LessSecond) {
1337	{
1338	std::pair<int, int> A(0, 1);
1339	std::pair<int, int> B(1, 0);
1340	EXPECT_FALSE(less_second()(A, B));
1341	EXPECT_TRUE(less_second()(B, A));
1342	}
1343
1344	{
1345	std::tuple<int, int> A(0, 1);
1346	std::tuple<int, int> B(1, 0);
1347	EXPECT_FALSE(less_second()(A, B));
1348	EXPECT_TRUE(less_second()(B, A));
1349	}
1350	}
1351
1352	struct Foo;
1353	struct Bar {};
1354
1355	static_assert(is_incomplete_v<Foo>, "Foo is incomplete");
1356	static_assert(!is_incomplete_v<Bar>, "Bar is defined");
1357
1358	} // namespace
1359