1 // Protocol Buffers - Google's data interchange format
2 // Copyright 2023 Google LLC. All rights reserved.
3 //
4 // Use of this source code is governed by a BSD-style
5 // license that can be found in the LICENSE file or at
6 // https://developers.google.com/open-source/licenses/bsd
7
8 #include "google/protobuf/hpb/repeated_field_iterator.h"
9
10 #include <algorithm>
11 #include <array>
12 #include <numeric>
13 #include <tuple>
14 #include <type_traits>
15 #include <utility>
16 #include <vector>
17
18 #include <gmock/gmock.h>
19 #include <gtest/gtest.h>
20 #include "absl/strings/string_view.h"
21 #include "google/protobuf/hpb/hpb.h"
22 #include "upb/message/array.h"
23
24 using ::testing::ElementsAre;
25
26 namespace hpb {
27 namespace internal {
28
29 template <typename T>
30 using ScalarRef = ReferenceProxy<ScalarIteratorPolicy<T>>;
31 template <typename T>
32 using ScalarIterator = Iterator<ScalarIteratorPolicy<T>>;
33
34 template <typename T>
35 using StringRef = ReferenceProxy<StringIteratorPolicy<T>>;
36 template <typename T>
37 using StringIterator = Iterator<StringIteratorPolicy<T>>;
38
39 struct IteratorTestPeer {
40 template <typename T>
MakeScalarRefProxyhpb::internal::IteratorTestPeer41 static ScalarRef<T> MakeScalarRefProxy(T& ref) {
42 return ScalarRef<T>({&ref});
43 }
44
45 template <typename T>
MakeScalarIteratorhpb::internal::IteratorTestPeer46 static ScalarIterator<T> MakeScalarIterator(T* ptr) {
47 return ScalarIterator<T>({ptr});
48 }
49
50 template <typename T>
MakeStringRefProxyhpb::internal::IteratorTestPeer51 static StringRef<T> MakeStringRefProxy(upb_Array* arr, hpb::Arena& arena) {
52 return StringRef<T>({arr, arena.ptr(), 0});
53 }
54
55 template <typename T>
MakeStringIteratorhpb::internal::IteratorTestPeer56 static StringIterator<T> MakeStringIterator(upb_Array* arr,
57 hpb::Arena& arena) {
58 return StringIterator<T>({arr, arena.ptr()});
59 }
60 };
61
62 namespace {
63
TEST(ScalarReferenceTest,BasicOperationsWork)64 TEST(ScalarReferenceTest, BasicOperationsWork) {
65 int i = 0;
66 ScalarRef<int> p = IteratorTestPeer::MakeScalarRefProxy(i);
67 ScalarRef<const int> cp =
68 IteratorTestPeer::MakeScalarRefProxy(std::as_const(i));
69 EXPECT_EQ(i, 0);
70 p = 17;
71 EXPECT_EQ(i, 17);
72 EXPECT_EQ(p, 17);
73 EXPECT_EQ(cp, 17);
74 i = 13;
75 EXPECT_EQ(p, 13);
76 EXPECT_EQ(cp, 13);
77
78 EXPECT_FALSE((std::is_assignable<decltype(cp), int>::value));
79
80 // Check that implicit conversion works T -> const T
81 ScalarRef<const int> cp2 = p;
82 EXPECT_EQ(cp2, 13);
83
84 EXPECT_FALSE((std::is_convertible<decltype(cp), ScalarRef<int>>::value));
85 }
86
TEST(ScalarReferenceTest,AssignmentAndSwap)87 TEST(ScalarReferenceTest, AssignmentAndSwap) {
88 int i = 3;
89 int j = 5;
90 ScalarRef<int> p = IteratorTestPeer::MakeScalarRefProxy(i);
91 ScalarRef<int> p2 = IteratorTestPeer::MakeScalarRefProxy(j);
92
93 EXPECT_EQ(p, 3);
94 EXPECT_EQ(p2, 5);
95 swap(p, p2);
96 EXPECT_EQ(p, 5);
97 EXPECT_EQ(p2, 3);
98
99 p = p2;
100 EXPECT_EQ(p, 3);
101 EXPECT_EQ(p2, 3);
102 }
103
104 template <typename T, typename U>
RunCompares(const T & a,const U & b)105 std::array<bool, 6> RunCompares(const T& a, const U& b) {
106 // Verify some basic properties here.
107 // Equivalencies
108 EXPECT_EQ((a == b), (b == a));
109 EXPECT_EQ((a != b), (b != a));
110 EXPECT_EQ((a < b), (b > a));
111 EXPECT_EQ((a > b), (b < a));
112 EXPECT_EQ((a <= b), (b >= a));
113 EXPECT_EQ((a >= b), (b <= a));
114
115 // Opposites
116 EXPECT_NE((a == b), (a != b));
117 EXPECT_NE((a < b), (a >= b));
118 EXPECT_NE((a > b), (a <= b));
119
120 return {{
121 (a == b),
122 (a != b),
123 (a < b),
124 (a <= b),
125 (a > b),
126 (a >= b),
127 }};
128 }
129
130 template <typename T>
TestScalarIterator(T * array)131 void TestScalarIterator(T* array) {
132 ScalarIterator<T> it = IteratorTestPeer::MakeScalarIterator(array);
133 // Copy
134 auto it2 = it;
135
136 EXPECT_THAT(RunCompares(it, it2),
137 ElementsAre(true, false, false, true, false, true));
138
139 // Increment
140 EXPECT_EQ(*++it, 11);
141 EXPECT_EQ(*it2, 10);
142 EXPECT_EQ(*it++, 11);
143 EXPECT_EQ(*it2, 10);
144 EXPECT_EQ(*it, 12);
145 EXPECT_EQ(*it2, 10);
146
147 EXPECT_THAT(RunCompares(it, it2),
148 ElementsAre(false, true, false, false, true, true));
149
150 // Assign
151 it2 = it;
152 EXPECT_EQ(*it, 12);
153 EXPECT_EQ(*it2, 12);
154
155 // Decrement
156 EXPECT_EQ(*--it, 11);
157 EXPECT_EQ(*it--, 11);
158 EXPECT_EQ(*it, 10);
159
160 it += 5;
161 EXPECT_EQ(*it, 15);
162 EXPECT_EQ(it - it2, 3);
163 EXPECT_EQ(it2 - it, -3);
164 it -= 3;
165 EXPECT_EQ(*it, 12);
166 EXPECT_EQ(it[6], 18);
167 EXPECT_EQ(it[-1], 11);
168 }
169
TEST(ScalarIteratorTest,BasicOperationsWork)170 TEST(ScalarIteratorTest, BasicOperationsWork) {
171 int array[10] = {10, 11, 12, 13, 14, 15, 16, 17, 18, 19};
172 TestScalarIterator<const int>(array);
173 TestScalarIterator<int>(array);
174 }
175
TEST(ScalarIteratorTest,Convertibility)176 TEST(ScalarIteratorTest, Convertibility) {
177 int array[10] = {10, 11, 12, 13, 14, 15, 16, 17, 18, 19};
178 ScalarIterator<int> it = IteratorTestPeer::MakeScalarIterator(array);
179 it += 4;
180 ScalarIterator<const int> cit = it;
181 EXPECT_EQ(*it, 14);
182 EXPECT_EQ(*cit, 14);
183 it += 2;
184 EXPECT_EQ(*it, 16);
185 EXPECT_EQ(*cit, 14);
186 cit = it;
187 EXPECT_EQ(*it, 16);
188 EXPECT_EQ(*cit, 16);
189
190 EXPECT_FALSE((std::is_convertible<ScalarIterator<const int>,
191 ScalarIterator<int>>::value));
192 EXPECT_FALSE((std::is_assignable<ScalarIterator<int>,
193 ScalarIterator<const int>>::value));
194 }
195
TEST(ScalarIteratorTest,MutabilityOnlyWorksOnMutable)196 TEST(ScalarIteratorTest, MutabilityOnlyWorksOnMutable) {
197 int array[10] = {10, 11, 12, 13, 14, 15, 16, 17, 18, 19};
198 ScalarIterator<int> it = IteratorTestPeer::MakeScalarIterator(array);
199 EXPECT_EQ(array[3], 13);
200 it[3] = 113;
201 EXPECT_EQ(array[3], 113);
202 ScalarIterator<const int> cit = it;
203 EXPECT_FALSE((std::is_assignable<decltype(*cit), int>::value));
204 EXPECT_FALSE((std::is_assignable<decltype(cit[1]), int>::value));
205 }
206
TEST(ScalarIteratorTest,IteratorReferenceInteraction)207 TEST(ScalarIteratorTest, IteratorReferenceInteraction) {
208 int array[10] = {10, 11, 12, 13, 14, 15, 16, 17, 18, 19};
209 ScalarIterator<int> it = IteratorTestPeer::MakeScalarIterator(array);
210 EXPECT_EQ(it[4], 14);
211 // op& from references goes back to iterator.
212 ScalarIterator<int> it2 = &it[4];
213 EXPECT_EQ(it + 4, it2);
214 }
215
TEST(ScalarIteratorTest,IteratorBasedAlgorithmsWork)216 TEST(ScalarIteratorTest, IteratorBasedAlgorithmsWork) {
217 // We use a vector here to make testing it easier.
218 std::vector<int> v(10, 0);
219 ScalarIterator<int> it = IteratorTestPeer::MakeScalarIterator(v.data());
220 EXPECT_THAT(v, ElementsAre(0, 0, 0, 0, 0, 0, 0, 0, 0, 0));
221 std::iota(it, it + 10, 10);
222 EXPECT_THAT(v, ElementsAre(10, 11, 12, 13, 14, 15, 16, 17, 18, 19));
223 EXPECT_EQ(it + 5, std::find(it, it + 10, 15));
224 EXPECT_EQ(145, std::accumulate(it, it + 10, 0));
225 std::sort(it, it + 10, [](int a, int b) {
226 return std::tuple(a % 2, a) < std::tuple(b % 2, b);
227 });
228 EXPECT_THAT(v, ElementsAre(10, 12, 14, 16, 18, 11, 13, 15, 17, 19));
229 }
230
CloneString(hpb::Arena & arena,absl::string_view str)231 const char* CloneString(hpb::Arena& arena, absl::string_view str) {
232 char* data = (char*)upb_Arena_Malloc(arena.ptr(), str.size());
233 memcpy(data, str.data(), str.size());
234 return data;
235 }
MakeStringArray(hpb::Arena & arena,const std::vector<std::string> & input)236 upb_Array* MakeStringArray(hpb::Arena& arena,
237 const std::vector<std::string>& input) {
238 upb_Array* arr = upb_Array_New(arena.ptr(), kUpb_CType_String);
239 for (absl::string_view str : input) {
240 upb_MessageValue message_value;
241 message_value.str_val =
242 upb_StringView_FromDataAndSize(CloneString(arena, str), str.size());
243 upb_Array_Append(arr, message_value, arena.ptr());
244 }
245 return arr;
246 }
247
TEST(StringReferenceTest,BasicOperationsWork)248 TEST(StringReferenceTest, BasicOperationsWork) {
249 hpb::Arena arena;
250 upb_Array* arr = MakeStringArray(arena, {""});
251
252 auto read = [&] {
253 upb_MessageValue message_value = upb_Array_Get(arr, 0);
254 return absl::string_view(message_value.str_val.data,
255 message_value.str_val.size);
256 };
257
258 StringRef<absl::string_view> p =
259 IteratorTestPeer::MakeStringRefProxy<absl::string_view>(arr, arena);
260 StringRef<const absl::string_view> cp =
261 IteratorTestPeer::MakeStringRefProxy<const absl::string_view>(arr, arena);
262 EXPECT_EQ(read(), "");
263 EXPECT_EQ(p, "");
264 p = "ABC";
265 EXPECT_EQ(read(), "ABC");
266 EXPECT_EQ(p, "ABC");
267 EXPECT_EQ(cp, "ABC");
268 const_cast<char*>(read().data())[0] = 'X';
269 EXPECT_EQ(read(), "XBC");
270 EXPECT_EQ(p, "XBC");
271 EXPECT_EQ(cp, "XBC");
272
273 EXPECT_FALSE((std::is_assignable<decltype(cp), int>::value));
274
275 // Check that implicit conversion works T -> const T
276 StringRef<const absl::string_view> cp2 = p;
277 EXPECT_EQ(cp2, "XBC");
278
279 EXPECT_FALSE(
280 (std::is_convertible<decltype(cp), StringRef<absl::string_view>>::value));
281
282 EXPECT_THAT(RunCompares(p, "XBC"),
283 ElementsAre(true, false, false, true, false, true));
284 EXPECT_THAT(RunCompares(p, "YBC"),
285 ElementsAre(false, true, true, true, false, false));
286 EXPECT_THAT(RunCompares(p, "RBC"),
287 ElementsAre(false, true, false, false, true, true));
288 EXPECT_THAT(RunCompares(p, "XB"),
289 ElementsAre(false, true, false, false, true, true));
290 EXPECT_THAT(RunCompares(p, "XBCD"),
291 ElementsAre(false, true, true, true, false, false));
292 }
293
TEST(StringReferenceTest,AssignmentAndSwap)294 TEST(StringReferenceTest, AssignmentAndSwap) {
295 hpb::Arena arena;
296 upb_Array* arr1 = MakeStringArray(arena, {"ABC"});
297 upb_Array* arr2 = MakeStringArray(arena, {"DEF"});
298
299 auto p = IteratorTestPeer::MakeStringRefProxy<absl::string_view>(arr1, arena);
300 auto p2 =
301 IteratorTestPeer::MakeStringRefProxy<absl::string_view>(arr2, arena);
302
303 EXPECT_EQ(p, "ABC");
304 EXPECT_EQ(p2, "DEF");
305 swap(p, p2);
306 EXPECT_EQ(p, "DEF");
307 EXPECT_EQ(p2, "ABC");
308
309 p = p2;
310 EXPECT_EQ(p, "ABC");
311 EXPECT_EQ(p2, "ABC");
312 }
313
314 template <typename T>
TestStringIterator(hpb::Arena & arena,upb_Array * array)315 void TestStringIterator(hpb::Arena& arena, upb_Array* array) {
316 StringIterator<T> it = IteratorTestPeer::MakeStringIterator<T>(array, arena);
317 // Copy
318 auto it2 = it;
319
320 EXPECT_THAT(RunCompares(it, it2),
321 ElementsAre(true, false, false, true, false, true));
322
323 // Increment
324 EXPECT_EQ(*++it, "11");
325 EXPECT_EQ(*it2, "10");
326 EXPECT_EQ(*it++, "11");
327 EXPECT_EQ(*it2, "10");
328 EXPECT_EQ(*it, "12");
329 EXPECT_EQ(*it2, "10");
330
331 EXPECT_THAT(RunCompares(it, it2),
332 ElementsAre(false, true, false, false, true, true));
333
334 // Assign
335 it2 = it;
336 EXPECT_EQ(*it, "12");
337 EXPECT_EQ(*it2, "12");
338
339 // Decrement
340 EXPECT_EQ(*--it, "11");
341 EXPECT_EQ(*it--, "11");
342 EXPECT_EQ(*it, "10");
343
344 it += 5;
345 EXPECT_EQ(*it, "15");
346 EXPECT_EQ(it - it2, 3);
347 EXPECT_EQ(it2 - it, -3);
348 it -= 3;
349 EXPECT_EQ(*it, "12");
350 EXPECT_EQ(it[6], "18");
351 EXPECT_EQ(it[-1], "11");
352 }
353
TEST(StringIteratorTest,BasicOperationsWork)354 TEST(StringIteratorTest, BasicOperationsWork) {
355 hpb::Arena arena;
356 auto* array = MakeStringArray(
357 arena, {"10", "11", "12", "13", "14", "15", "16", "17", "18", "19"});
358 TestStringIterator<const absl::string_view>(arena, array);
359 TestStringIterator<absl::string_view>(arena, array);
360 }
361
TEST(StringIteratorTest,Convertibility)362 TEST(StringIteratorTest, Convertibility) {
363 hpb::Arena arena;
364 auto* array = MakeStringArray(
365 arena, {"10", "11", "12", "13", "14", "15", "16", "17", "18", "19"});
366 StringIterator<absl::string_view> it =
367 IteratorTestPeer::MakeStringIterator<absl::string_view>(array, arena);
368 it += 4;
369 StringIterator<const absl::string_view> cit = it;
370 EXPECT_EQ(*it, "14");
371 EXPECT_EQ(*cit, "14");
372 it += 2;
373 EXPECT_EQ(*it, "16");
374 EXPECT_EQ(*cit, "14");
375 cit = it;
376 EXPECT_EQ(*it, "16");
377 EXPECT_EQ(*cit, "16");
378
379 EXPECT_FALSE((std::is_convertible<StringIterator<const absl::string_view>,
380 StringIterator<absl::string_view>>::value));
381 EXPECT_FALSE(
382 (std::is_assignable<StringIterator<absl::string_view>,
383 StringIterator<const absl::string_view>>::value));
384 }
385
TEST(StringIteratorTest,MutabilityOnlyWorksOnMutable)386 TEST(StringIteratorTest, MutabilityOnlyWorksOnMutable) {
387 hpb::Arena arena;
388 auto* array = MakeStringArray(
389 arena, {"10", "11", "12", "13", "14", "15", "16", "17", "18", "19"});
390 StringIterator<absl::string_view> it =
391 IteratorTestPeer::MakeStringIterator<absl::string_view>(array, arena);
392
393 auto read = [&] {
394 upb_MessageValue message_value = upb_Array_Get(array, 3);
395 return absl::string_view(message_value.str_val.data,
396 message_value.str_val.size);
397 };
398
399 EXPECT_EQ(read(), "13");
400 it[3] = "113";
401 EXPECT_EQ(read(), "113");
402 StringIterator<const absl::string_view> cit = it;
403 EXPECT_FALSE((std::is_assignable<decltype(*cit), absl::string_view>::value));
404 EXPECT_FALSE(
405 (std::is_assignable<decltype(cit[1]), absl::string_view>::value));
406 }
407
TEST(StringIteratorTest,IteratorReferenceInteraction)408 TEST(StringIteratorTest, IteratorReferenceInteraction) {
409 hpb::Arena arena;
410 auto* array = MakeStringArray(
411 arena, {"10", "11", "12", "13", "14", "15", "16", "17", "18", "19"});
412 StringIterator<absl::string_view> it =
413 IteratorTestPeer::MakeStringIterator<absl::string_view>(array, arena);
414 EXPECT_EQ(it[4], "14");
415 // op& from references goes back to iterator.
416 StringIterator<absl::string_view> it2 = &it[4];
417 EXPECT_EQ(it + 4, it2);
418 }
419
TEST(StringIteratorTest,IteratorBasedAlgorithmsWork)420 TEST(StringIteratorTest, IteratorBasedAlgorithmsWork) {
421 hpb::Arena arena;
422 auto* array = MakeStringArray(
423 arena, {"10", "11", "12", "13", "14", "15", "16", "17", "18", "19"});
424 StringIterator<absl::string_view> it =
425 IteratorTestPeer::MakeStringIterator<absl::string_view>(array, arena);
426
427 auto read = [&] {
428 std::vector<absl::string_view> v;
429 for (int i = 0; i < 10; ++i) {
430 upb_MessageValue message_value = upb_Array_Get(array, i);
431 v.emplace_back(message_value.str_val.data, message_value.str_val.size);
432 }
433 return v;
434 };
435
436 EXPECT_THAT(read(), ElementsAre("10", "11", "12", "13", "14", //
437 "15", "16", "17", "18", "19"));
438 std::sort(it, it + 10, [](absl::string_view a, absl::string_view b) {
439 return std::tuple(a[1] % 2, a) < std::tuple(b[1] % 2, b);
440 });
441 EXPECT_THAT(read(), ElementsAre("10", "12", "14", "16", "18", //
442 "11", "13", "15", "17", "19"));
443 // Now sort with the default less.
444 std::sort(it, it + 10);
445 EXPECT_THAT(read(), ElementsAre("10", "11", "12", "13", "14", //
446 "15", "16", "17", "18", "19"));
447
448 // Mutable algorithm
449 std::generate(it, it + 10,
450 [i = 0]() mutable { return std::string(i++, 'x'); });
451 EXPECT_THAT(read(),
452 ElementsAre("", "x", "xx", "xxx", "xxxx", "xxxxx", "xxxxxx",
453 "xxxxxxx", "xxxxxxxx", "xxxxxxxxx"));
454 }
455
456 } // namespace
457 } // namespace internal
458 } // namespace hpb
459