1 // Protocol Buffers - Google's data interchange format
2 // Copyright 2008 Google Inc.  All rights reserved.
3 // https://developers.google.com/protocol-buffers/
4 //
5 // Redistribution and use in source and binary forms, with or without
6 // modification, are permitted provided that the following conditions are
7 // met:
8 //
9 //     * Redistributions of source code must retain the above copyright
10 // notice, this list of conditions and the following disclaimer.
11 //     * Redistributions in binary form must reproduce the above
12 // copyright notice, this list of conditions and the following disclaimer
13 // in the documentation and/or other materials provided with the
14 // distribution.
15 //     * Neither the name of Google Inc. nor the names of its
16 // contributors may be used to endorse or promote products derived from
17 // this software without specific prior written permission.
18 //
19 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
20 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
21 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
22 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
23 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
24 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
25 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
26 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
27 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
28 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
29 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30 
31 // Author: kenton@google.com (Kenton Varda)
32 //  Based on original Protocol Buffers design by
33 //  Sanjay Ghemawat, Jeff Dean, and others.
34 //
35 // TODO(kenton):  Improve this unittest to bring it up to the standards of
36 //   other proto2 unittests.
37 
38 #include <algorithm>
39 #include <limits>
40 #include <list>
41 #include <vector>
42 
43 #include <google/protobuf/repeated_field.h>
44 
45 #include <google/protobuf/stubs/common.h>
46 #include <google/protobuf/unittest.pb.h>
47 #include <google/protobuf/stubs/strutil.h>
48 #include <google/protobuf/testing/googletest.h>
49 #include <gtest/gtest.h>
50 #include <google/protobuf/stubs/stl_util.h>
51 
52 namespace google {
53 using protobuf_unittest::TestAllTypes;
54 
55 namespace protobuf {
56 namespace {
57 
58 // Test operations on a small RepeatedField.
TEST(RepeatedField,Small)59 TEST(RepeatedField, Small) {
60   RepeatedField<int> field;
61 
62   EXPECT_TRUE(field.empty());
63   EXPECT_EQ(field.size(), 0);
64 
65   field.Add(5);
66 
67   EXPECT_FALSE(field.empty());
68   EXPECT_EQ(field.size(), 1);
69   EXPECT_EQ(field.Get(0), 5);
70 
71   field.Add(42);
72 
73   EXPECT_FALSE(field.empty());
74   EXPECT_EQ(field.size(), 2);
75   EXPECT_EQ(field.Get(0), 5);
76   EXPECT_EQ(field.Get(1), 42);
77 
78   field.Set(1, 23);
79 
80   EXPECT_FALSE(field.empty());
81   EXPECT_EQ(field.size(), 2);
82   EXPECT_EQ(field.Get(0), 5);
83   EXPECT_EQ(field.Get(1), 23);
84 
85   field.RemoveLast();
86 
87   EXPECT_FALSE(field.empty());
88   EXPECT_EQ(field.size(), 1);
89   EXPECT_EQ(field.Get(0), 5);
90 
91   field.Clear();
92 
93   EXPECT_TRUE(field.empty());
94   EXPECT_EQ(field.size(), 0);
95   int expected_usage = 4 * sizeof(int);
96   EXPECT_EQ(field.SpaceUsedExcludingSelf(), expected_usage);
97 }
98 
99 
100 // Test operations on a RepeatedField which is large enough to allocate a
101 // separate array.
TEST(RepeatedField,Large)102 TEST(RepeatedField, Large) {
103   RepeatedField<int> field;
104 
105   for (int i = 0; i < 16; i++) {
106     field.Add(i * i);
107   }
108 
109   EXPECT_FALSE(field.empty());
110   EXPECT_EQ(field.size(), 16);
111 
112   for (int i = 0; i < 16; i++) {
113     EXPECT_EQ(field.Get(i), i * i);
114   }
115 
116   int expected_usage = 16 * sizeof(int);
117   EXPECT_GE(field.SpaceUsedExcludingSelf(), expected_usage);
118 }
119 
120 // Test swapping between various types of RepeatedFields.
TEST(RepeatedField,SwapSmallSmall)121 TEST(RepeatedField, SwapSmallSmall) {
122   RepeatedField<int> field1;
123   RepeatedField<int> field2;
124 
125   field1.Add(5);
126   field1.Add(42);
127 
128   EXPECT_FALSE(field1.empty());
129   EXPECT_EQ(field1.size(), 2);
130   EXPECT_EQ(field1.Get(0), 5);
131   EXPECT_EQ(field1.Get(1), 42);
132 
133   EXPECT_TRUE(field2.empty());
134   EXPECT_EQ(field2.size(), 0);
135 
136   field1.Swap(&field2);
137 
138   EXPECT_TRUE(field1.empty());
139   EXPECT_EQ(field1.size(), 0);
140 
141   EXPECT_FALSE(field2.empty());
142   EXPECT_EQ(field2.size(), 2);
143   EXPECT_EQ(field2.Get(0), 5);
144   EXPECT_EQ(field2.Get(1), 42);
145 }
146 
TEST(RepeatedField,SwapLargeSmall)147 TEST(RepeatedField, SwapLargeSmall) {
148   RepeatedField<int> field1;
149   RepeatedField<int> field2;
150 
151   for (int i = 0; i < 16; i++) {
152     field1.Add(i * i);
153   }
154   field2.Add(5);
155   field2.Add(42);
156   field1.Swap(&field2);
157 
158   EXPECT_EQ(field1.size(), 2);
159   EXPECT_EQ(field1.Get(0), 5);
160   EXPECT_EQ(field1.Get(1), 42);
161   EXPECT_EQ(field2.size(), 16);
162   for (int i = 0; i < 16; i++) {
163     EXPECT_EQ(field2.Get(i), i * i);
164   }
165 }
166 
TEST(RepeatedField,SwapLargeLarge)167 TEST(RepeatedField, SwapLargeLarge) {
168   RepeatedField<int> field1;
169   RepeatedField<int> field2;
170 
171   field1.Add(5);
172   field1.Add(42);
173   for (int i = 0; i < 16; i++) {
174     field1.Add(i);
175     field2.Add(i * i);
176   }
177   field2.Swap(&field1);
178 
179   EXPECT_EQ(field1.size(), 16);
180   for (int i = 0; i < 16; i++) {
181     EXPECT_EQ(field1.Get(i), i * i);
182   }
183   EXPECT_EQ(field2.size(), 18);
184   EXPECT_EQ(field2.Get(0), 5);
185   EXPECT_EQ(field2.Get(1), 42);
186   for (int i = 2; i < 18; i++) {
187     EXPECT_EQ(field2.Get(i), i - 2);
188   }
189 }
190 
191 // Determines how much space was reserved by the given field by adding elements
192 // to it until it re-allocates its space.
ReservedSpace(RepeatedField<int> * field)193 static int ReservedSpace(RepeatedField<int>* field) {
194   const int* ptr = field->data();
195   do {
196     field->Add(0);
197   } while (field->data() == ptr);
198 
199   return field->size() - 1;
200 }
201 
TEST(RepeatedField,ReserveMoreThanDouble)202 TEST(RepeatedField, ReserveMoreThanDouble) {
203   // Reserve more than double the previous space in the field and expect the
204   // field to reserve exactly the amount specified.
205   RepeatedField<int> field;
206   field.Reserve(20);
207 
208   EXPECT_EQ(20, ReservedSpace(&field));
209 }
210 
TEST(RepeatedField,ReserveLessThanDouble)211 TEST(RepeatedField, ReserveLessThanDouble) {
212   // Reserve less than double the previous space in the field and expect the
213   // field to grow by double instead.
214   RepeatedField<int> field;
215   field.Reserve(20);
216   field.Reserve(30);
217 
218   EXPECT_EQ(40, ReservedSpace(&field));
219 }
220 
TEST(RepeatedField,ReserveLessThanExisting)221 TEST(RepeatedField, ReserveLessThanExisting) {
222   // Reserve less than the previous space in the field and expect the
223   // field to not re-allocate at all.
224   RepeatedField<int> field;
225   field.Reserve(20);
226   const int* previous_ptr = field.data();
227   field.Reserve(10);
228 
229   EXPECT_EQ(previous_ptr, field.data());
230   EXPECT_EQ(20, ReservedSpace(&field));
231 }
232 
TEST(RepeatedField,Resize)233 TEST(RepeatedField, Resize) {
234   RepeatedField<int> field;
235   field.Resize(2, 1);
236   EXPECT_EQ(2, field.size());
237   field.Resize(5, 2);
238   EXPECT_EQ(5, field.size());
239   field.Resize(4, 3);
240   ASSERT_EQ(4, field.size());
241   EXPECT_EQ(1, field.Get(0));
242   EXPECT_EQ(1, field.Get(1));
243   EXPECT_EQ(2, field.Get(2));
244   EXPECT_EQ(2, field.Get(3));
245   field.Resize(0, 4);
246   EXPECT_TRUE(field.empty());
247 }
248 
TEST(RepeatedField,MergeFrom)249 TEST(RepeatedField, MergeFrom) {
250   RepeatedField<int> source, destination;
251   source.Add(4);
252   source.Add(5);
253   destination.Add(1);
254   destination.Add(2);
255   destination.Add(3);
256 
257   destination.MergeFrom(source);
258 
259   ASSERT_EQ(5, destination.size());
260   EXPECT_EQ(1, destination.Get(0));
261   EXPECT_EQ(2, destination.Get(1));
262   EXPECT_EQ(3, destination.Get(2));
263   EXPECT_EQ(4, destination.Get(3));
264   EXPECT_EQ(5, destination.Get(4));
265 }
266 
267 #ifdef PROTOBUF_HAS_DEATH_TEST
TEST(RepeatedField,MergeFromSelf)268 TEST(RepeatedField, MergeFromSelf) {
269   RepeatedField<int> me;
270   me.Add(3);
271   EXPECT_DEATH(me.MergeFrom(me), "");
272 }
273 #endif  // PROTOBUF_HAS_DEATH_TEST
274 
TEST(RepeatedField,CopyFrom)275 TEST(RepeatedField, CopyFrom) {
276   RepeatedField<int> source, destination;
277   source.Add(4);
278   source.Add(5);
279   destination.Add(1);
280   destination.Add(2);
281   destination.Add(3);
282 
283   destination.CopyFrom(source);
284 
285   ASSERT_EQ(2, destination.size());
286   EXPECT_EQ(4, destination.Get(0));
287   EXPECT_EQ(5, destination.Get(1));
288 }
289 
TEST(RepeatedField,CopyFromSelf)290 TEST(RepeatedField, CopyFromSelf) {
291   RepeatedField<int> me;
292   me.Add(3);
293   me.CopyFrom(me);
294   ASSERT_EQ(1, me.size());
295   EXPECT_EQ(3, me.Get(0));
296 }
297 
TEST(RepeatedField,CopyConstruct)298 TEST(RepeatedField, CopyConstruct) {
299   RepeatedField<int> source;
300   source.Add(1);
301   source.Add(2);
302 
303   RepeatedField<int> destination(source);
304 
305   ASSERT_EQ(2, destination.size());
306   EXPECT_EQ(1, destination.Get(0));
307   EXPECT_EQ(2, destination.Get(1));
308 }
309 
TEST(RepeatedField,IteratorConstruct)310 TEST(RepeatedField, IteratorConstruct) {
311   vector<int> values;
312   values.push_back(1);
313   values.push_back(2);
314 
315   RepeatedField<int> field(values.begin(), values.end());
316   ASSERT_EQ(values.size(), field.size());
317   EXPECT_EQ(values[0], field.Get(0));
318   EXPECT_EQ(values[1], field.Get(1));
319 
320   RepeatedField<int> other(field.begin(), field.end());
321   ASSERT_EQ(values.size(), other.size());
322   EXPECT_EQ(values[0], other.Get(0));
323   EXPECT_EQ(values[1], other.Get(1));
324 }
325 
TEST(RepeatedField,CopyAssign)326 TEST(RepeatedField, CopyAssign) {
327   RepeatedField<int> source, destination;
328   source.Add(4);
329   source.Add(5);
330   destination.Add(1);
331   destination.Add(2);
332   destination.Add(3);
333 
334   destination = source;
335 
336   ASSERT_EQ(2, destination.size());
337   EXPECT_EQ(4, destination.Get(0));
338   EXPECT_EQ(5, destination.Get(1));
339 }
340 
TEST(RepeatedField,SelfAssign)341 TEST(RepeatedField, SelfAssign) {
342   // Verify that assignment to self does not destroy data.
343   RepeatedField<int> source, *p;
344   p = &source;
345   source.Add(7);
346   source.Add(8);
347 
348   *p = source;
349 
350   ASSERT_EQ(2, source.size());
351   EXPECT_EQ(7, source.Get(0));
352   EXPECT_EQ(8, source.Get(1));
353 }
354 
TEST(RepeatedField,MutableDataIsMutable)355 TEST(RepeatedField, MutableDataIsMutable) {
356   RepeatedField<int> field;
357   field.Add(1);
358   EXPECT_EQ(1, field.Get(0));
359   // The fact that this line compiles would be enough, but we'll check the
360   // value anyway.
361   *field.mutable_data() = 2;
362   EXPECT_EQ(2, field.Get(0));
363 }
364 
TEST(RepeatedField,Truncate)365 TEST(RepeatedField, Truncate) {
366   RepeatedField<int> field;
367 
368   field.Add(12);
369   field.Add(34);
370   field.Add(56);
371   field.Add(78);
372   EXPECT_EQ(4, field.size());
373 
374   field.Truncate(3);
375   EXPECT_EQ(3, field.size());
376 
377   field.Add(90);
378   EXPECT_EQ(4, field.size());
379   EXPECT_EQ(90, field.Get(3));
380 
381   // Truncations that don't change the size are allowed, but growing is not
382   // allowed.
383   field.Truncate(field.size());
384 #ifdef PROTOBUF_HAS_DEATH_TEST
385   EXPECT_DEBUG_DEATH(field.Truncate(field.size() + 1), "new_size");
386 #endif
387 }
388 
389 
TEST(RepeatedField,ExtractSubrange)390 TEST(RepeatedField, ExtractSubrange) {
391   // Exhaustively test every subrange in arrays of all sizes from 0 through 9.
392   for (int sz = 0; sz < 10; ++sz) {
393     for (int num = 0; num <= sz; ++num) {
394       for (int start = 0; start < sz - num; ++start) {
395         // Create RepeatedField with sz elements having values 0 through sz-1.
396         RepeatedField<int32> field;
397         for (int i = 0; i < sz; ++i)
398           field.Add(i);
399         EXPECT_EQ(field.size(), sz);
400 
401         // Create a catcher array and call ExtractSubrange.
402         int32 catcher[10];
403         for (int i = 0; i < 10; ++i)
404           catcher[i] = -1;
405         field.ExtractSubrange(start, num, catcher);
406 
407         // Does the resulting array have the right size?
408         EXPECT_EQ(field.size(), sz - num);
409 
410         // Were the removed elements extracted into the catcher array?
411         for (int i = 0; i < num; ++i)
412           EXPECT_EQ(catcher[i], start + i);
413         EXPECT_EQ(catcher[num], -1);
414 
415         // Does the resulting array contain the right values?
416         for (int i = 0; i < start; ++i)
417           EXPECT_EQ(field.Get(i), i);
418         for (int i = start; i < field.size(); ++i)
419           EXPECT_EQ(field.Get(i), i + num);
420       }
421     }
422   }
423 }
424 
425 // ===================================================================
426 // RepeatedPtrField tests.  These pretty much just mirror the RepeatedField
427 // tests above.
428 
TEST(RepeatedPtrField,Small)429 TEST(RepeatedPtrField, Small) {
430   RepeatedPtrField<string> field;
431 
432   EXPECT_TRUE(field.empty());
433   EXPECT_EQ(field.size(), 0);
434 
435   field.Add()->assign("foo");
436 
437   EXPECT_FALSE(field.empty());
438   EXPECT_EQ(field.size(), 1);
439   EXPECT_EQ(field.Get(0), "foo");
440 
441   field.Add()->assign("bar");
442 
443   EXPECT_FALSE(field.empty());
444   EXPECT_EQ(field.size(), 2);
445   EXPECT_EQ(field.Get(0), "foo");
446   EXPECT_EQ(field.Get(1), "bar");
447 
448   field.Mutable(1)->assign("baz");
449 
450   EXPECT_FALSE(field.empty());
451   EXPECT_EQ(field.size(), 2);
452   EXPECT_EQ(field.Get(0), "foo");
453   EXPECT_EQ(field.Get(1), "baz");
454 
455   field.RemoveLast();
456 
457   EXPECT_FALSE(field.empty());
458   EXPECT_EQ(field.size(), 1);
459   EXPECT_EQ(field.Get(0), "foo");
460 
461   field.Clear();
462 
463   EXPECT_TRUE(field.empty());
464   EXPECT_EQ(field.size(), 0);
465 }
466 
TEST(RepeatedPtrField,Large)467 TEST(RepeatedPtrField, Large) {
468   RepeatedPtrField<string> field;
469 
470   for (int i = 0; i < 16; i++) {
471     *field.Add() += 'a' + i;
472   }
473 
474   EXPECT_EQ(field.size(), 16);
475 
476   for (int i = 0; i < 16; i++) {
477     EXPECT_EQ(field.Get(i).size(), 1);
478     EXPECT_EQ(field.Get(i)[0], 'a' + i);
479   }
480 
481   int min_expected_usage = 16 * sizeof(string);
482   EXPECT_GE(field.SpaceUsedExcludingSelf(), min_expected_usage);
483 }
484 
TEST(RepeatedPtrField,SwapSmallSmall)485 TEST(RepeatedPtrField, SwapSmallSmall) {
486   RepeatedPtrField<string> field1;
487   RepeatedPtrField<string> field2;
488 
489   EXPECT_TRUE(field1.empty());
490   EXPECT_EQ(field1.size(), 0);
491   EXPECT_TRUE(field2.empty());
492   EXPECT_EQ(field2.size(), 0);
493 
494   field1.Add()->assign("foo");
495   field1.Add()->assign("bar");
496 
497   EXPECT_FALSE(field1.empty());
498   EXPECT_EQ(field1.size(), 2);
499   EXPECT_EQ(field1.Get(0), "foo");
500   EXPECT_EQ(field1.Get(1), "bar");
501 
502   EXPECT_TRUE(field2.empty());
503   EXPECT_EQ(field2.size(), 0);
504 
505   field1.Swap(&field2);
506 
507   EXPECT_TRUE(field1.empty());
508   EXPECT_EQ(field1.size(), 0);
509 
510   EXPECT_EQ(field2.size(), 2);
511   EXPECT_EQ(field2.Get(0), "foo");
512   EXPECT_EQ(field2.Get(1), "bar");
513 }
514 
TEST(RepeatedPtrField,SwapLargeSmall)515 TEST(RepeatedPtrField, SwapLargeSmall) {
516   RepeatedPtrField<string> field1;
517   RepeatedPtrField<string> field2;
518 
519   field2.Add()->assign("foo");
520   field2.Add()->assign("bar");
521   for (int i = 0; i < 16; i++) {
522     *field1.Add() += 'a' + i;
523   }
524   field1.Swap(&field2);
525 
526   EXPECT_EQ(field1.size(), 2);
527   EXPECT_EQ(field1.Get(0), "foo");
528   EXPECT_EQ(field1.Get(1), "bar");
529   EXPECT_EQ(field2.size(), 16);
530   for (int i = 0; i < 16; i++) {
531     EXPECT_EQ(field2.Get(i).size(), 1);
532     EXPECT_EQ(field2.Get(i)[0], 'a' + i);
533   }
534 }
535 
TEST(RepeatedPtrField,SwapLargeLarge)536 TEST(RepeatedPtrField, SwapLargeLarge) {
537   RepeatedPtrField<string> field1;
538   RepeatedPtrField<string> field2;
539 
540   field1.Add()->assign("foo");
541   field1.Add()->assign("bar");
542   for (int i = 0; i < 16; i++) {
543     *field1.Add() += 'A' + i;
544     *field2.Add() += 'a' + i;
545   }
546   field2.Swap(&field1);
547 
548   EXPECT_EQ(field1.size(), 16);
549   for (int i = 0; i < 16; i++) {
550     EXPECT_EQ(field1.Get(i).size(), 1);
551     EXPECT_EQ(field1.Get(i)[0], 'a' + i);
552   }
553   EXPECT_EQ(field2.size(), 18);
554   EXPECT_EQ(field2.Get(0), "foo");
555   EXPECT_EQ(field2.Get(1), "bar");
556   for (int i = 2; i < 18; i++) {
557     EXPECT_EQ(field2.Get(i).size(), 1);
558     EXPECT_EQ(field2.Get(i)[0], 'A' + i - 2);
559   }
560 }
561 
ReservedSpace(RepeatedPtrField<string> * field)562 static int ReservedSpace(RepeatedPtrField<string>* field) {
563   const string* const* ptr = field->data();
564   do {
565     field->Add();
566   } while (field->data() == ptr);
567 
568   return field->size() - 1;
569 }
570 
TEST(RepeatedPtrField,ReserveMoreThanDouble)571 TEST(RepeatedPtrField, ReserveMoreThanDouble) {
572   RepeatedPtrField<string> field;
573   field.Reserve(20);
574 
575   EXPECT_EQ(20, ReservedSpace(&field));
576 }
577 
TEST(RepeatedPtrField,ReserveLessThanDouble)578 TEST(RepeatedPtrField, ReserveLessThanDouble) {
579   RepeatedPtrField<string> field;
580   field.Reserve(20);
581   field.Reserve(30);
582 
583   EXPECT_EQ(40, ReservedSpace(&field));
584 }
585 
TEST(RepeatedPtrField,ReserveLessThanExisting)586 TEST(RepeatedPtrField, ReserveLessThanExisting) {
587   RepeatedPtrField<string> field;
588   field.Reserve(20);
589   const string* const* previous_ptr = field.data();
590   field.Reserve(10);
591 
592   EXPECT_EQ(previous_ptr, field.data());
593   EXPECT_EQ(20, ReservedSpace(&field));
594 }
595 
TEST(RepeatedPtrField,ReserveDoesntLoseAllocated)596 TEST(RepeatedPtrField, ReserveDoesntLoseAllocated) {
597   // Check that a bug is fixed:  An earlier implementation of Reserve()
598   // failed to copy pointers to allocated-but-cleared objects, possibly
599   // leading to segfaults.
600   RepeatedPtrField<string> field;
601   string* first = field.Add();
602   field.RemoveLast();
603 
604   field.Reserve(20);
605   EXPECT_EQ(first, field.Add());
606 }
607 
608 // Clearing elements is tricky with RepeatedPtrFields since the memory for
609 // the elements is retained and reused.
TEST(RepeatedPtrField,ClearedElements)610 TEST(RepeatedPtrField, ClearedElements) {
611   RepeatedPtrField<string> field;
612 
613   string* original = field.Add();
614   *original = "foo";
615 
616   EXPECT_EQ(field.ClearedCount(), 0);
617 
618   field.RemoveLast();
619   EXPECT_TRUE(original->empty());
620   EXPECT_EQ(field.ClearedCount(), 1);
621 
622   EXPECT_EQ(field.Add(), original);  // Should return same string for reuse.
623 
624   EXPECT_EQ(field.ReleaseLast(), original);  // We take ownership.
625   EXPECT_EQ(field.ClearedCount(), 0);
626 
627   EXPECT_NE(field.Add(), original);  // Should NOT return the same string.
628   EXPECT_EQ(field.ClearedCount(), 0);
629 
630   field.AddAllocated(original);  // Give ownership back.
631   EXPECT_EQ(field.ClearedCount(), 0);
632   EXPECT_EQ(field.Mutable(1), original);
633 
634   field.Clear();
635   EXPECT_EQ(field.ClearedCount(), 2);
636   EXPECT_EQ(field.ReleaseCleared(), original);  // Take ownership again.
637   EXPECT_EQ(field.ClearedCount(), 1);
638   EXPECT_NE(field.Add(), original);
639   EXPECT_EQ(field.ClearedCount(), 0);
640   EXPECT_NE(field.Add(), original);
641   EXPECT_EQ(field.ClearedCount(), 0);
642 
643   field.AddCleared(original);  // Give ownership back, but as a cleared object.
644   EXPECT_EQ(field.ClearedCount(), 1);
645   EXPECT_EQ(field.Add(), original);
646   EXPECT_EQ(field.ClearedCount(), 0);
647 }
648 
649 // Test all code paths in AddAllocated().
TEST(RepeatedPtrField,AddAlocated)650 TEST(RepeatedPtrField, AddAlocated) {
651   RepeatedPtrField<string> field;
652   while (field.size() < field.Capacity()) {
653     field.Add()->assign("filler");
654   }
655 
656   int index = field.size();
657 
658   // First branch:  Field is at capacity with no cleared objects.
659   string* foo = new string("foo");
660   field.AddAllocated(foo);
661   EXPECT_EQ(index + 1, field.size());
662   EXPECT_EQ(0, field.ClearedCount());
663   EXPECT_EQ(foo, &field.Get(index));
664 
665   // Last branch:  Field is not at capacity and there are no cleared objects.
666   string* bar = new string("bar");
667   field.AddAllocated(bar);
668   ++index;
669   EXPECT_EQ(index + 1, field.size());
670   EXPECT_EQ(0, field.ClearedCount());
671   EXPECT_EQ(bar, &field.Get(index));
672 
673   // Third branch:  Field is not at capacity and there are no cleared objects.
674   field.RemoveLast();
675   string* baz = new string("baz");
676   field.AddAllocated(baz);
677   EXPECT_EQ(index + 1, field.size());
678   EXPECT_EQ(1, field.ClearedCount());
679   EXPECT_EQ(baz, &field.Get(index));
680 
681   // Second branch:  Field is at capacity but has some cleared objects.
682   while (field.size() < field.Capacity()) {
683     field.Add()->assign("filler2");
684   }
685   field.RemoveLast();
686   index = field.size();
687   string* qux = new string("qux");
688   field.AddAllocated(qux);
689   EXPECT_EQ(index + 1, field.size());
690   // We should have discarded the cleared object.
691   EXPECT_EQ(0, field.ClearedCount());
692   EXPECT_EQ(qux, &field.Get(index));
693 }
694 
TEST(RepeatedPtrField,MergeFrom)695 TEST(RepeatedPtrField, MergeFrom) {
696   RepeatedPtrField<string> source, destination;
697   source.Add()->assign("4");
698   source.Add()->assign("5");
699   destination.Add()->assign("1");
700   destination.Add()->assign("2");
701   destination.Add()->assign("3");
702 
703   destination.MergeFrom(source);
704 
705   ASSERT_EQ(5, destination.size());
706   EXPECT_EQ("1", destination.Get(0));
707   EXPECT_EQ("2", destination.Get(1));
708   EXPECT_EQ("3", destination.Get(2));
709   EXPECT_EQ("4", destination.Get(3));
710   EXPECT_EQ("5", destination.Get(4));
711 }
712 
713 #ifdef PROTOBUF_HAS_DEATH_TEST
TEST(RepeatedPtrField,MergeFromSelf)714 TEST(RepeatedPtrField, MergeFromSelf) {
715   RepeatedPtrField<string> me;
716   me.Add()->assign("1");
717   EXPECT_DEATH(me.MergeFrom(me), "");
718 }
719 #endif  // PROTOBUF_HAS_DEATH_TEST
720 
TEST(RepeatedPtrField,CopyFrom)721 TEST(RepeatedPtrField, CopyFrom) {
722   RepeatedPtrField<string> source, destination;
723   source.Add()->assign("4");
724   source.Add()->assign("5");
725   destination.Add()->assign("1");
726   destination.Add()->assign("2");
727   destination.Add()->assign("3");
728 
729   destination.CopyFrom(source);
730 
731   ASSERT_EQ(2, destination.size());
732   EXPECT_EQ("4", destination.Get(0));
733   EXPECT_EQ("5", destination.Get(1));
734 }
735 
TEST(RepeatedPtrField,CopyFromSelf)736 TEST(RepeatedPtrField, CopyFromSelf) {
737   RepeatedPtrField<string> me;
738   me.Add()->assign("1");
739   me.CopyFrom(me);
740   ASSERT_EQ(1, me.size());
741   EXPECT_EQ("1", me.Get(0));
742 }
743 
TEST(RepeatedPtrField,CopyConstruct)744 TEST(RepeatedPtrField, CopyConstruct) {
745   RepeatedPtrField<string> source;
746   source.Add()->assign("1");
747   source.Add()->assign("2");
748 
749   RepeatedPtrField<string> destination(source);
750 
751   ASSERT_EQ(2, destination.size());
752   EXPECT_EQ("1", destination.Get(0));
753   EXPECT_EQ("2", destination.Get(1));
754 }
755 
TEST(RepeatedPtrField,IteratorConstruct_String)756 TEST(RepeatedPtrField, IteratorConstruct_String) {
757   vector<string> values;
758   values.push_back("1");
759   values.push_back("2");
760 
761   RepeatedPtrField<string> field(values.begin(), values.end());
762   ASSERT_EQ(values.size(), field.size());
763   EXPECT_EQ(values[0], field.Get(0));
764   EXPECT_EQ(values[1], field.Get(1));
765 
766   RepeatedPtrField<string> other(field.begin(), field.end());
767   ASSERT_EQ(values.size(), other.size());
768   EXPECT_EQ(values[0], other.Get(0));
769   EXPECT_EQ(values[1], other.Get(1));
770 }
771 
TEST(RepeatedPtrField,IteratorConstruct_Proto)772 TEST(RepeatedPtrField, IteratorConstruct_Proto) {
773   typedef TestAllTypes::NestedMessage Nested;
774   vector<Nested> values;
775   values.push_back(Nested());
776   values.back().set_bb(1);
777   values.push_back(Nested());
778   values.back().set_bb(2);
779 
780   RepeatedPtrField<Nested> field(values.begin(), values.end());
781   ASSERT_EQ(values.size(), field.size());
782   EXPECT_EQ(values[0].bb(), field.Get(0).bb());
783   EXPECT_EQ(values[1].bb(), field.Get(1).bb());
784 
785   RepeatedPtrField<Nested> other(field.begin(), field.end());
786   ASSERT_EQ(values.size(), other.size());
787   EXPECT_EQ(values[0].bb(), other.Get(0).bb());
788   EXPECT_EQ(values[1].bb(), other.Get(1).bb());
789 }
790 
TEST(RepeatedPtrField,CopyAssign)791 TEST(RepeatedPtrField, CopyAssign) {
792   RepeatedPtrField<string> source, destination;
793   source.Add()->assign("4");
794   source.Add()->assign("5");
795   destination.Add()->assign("1");
796   destination.Add()->assign("2");
797   destination.Add()->assign("3");
798 
799   destination = source;
800 
801   ASSERT_EQ(2, destination.size());
802   EXPECT_EQ("4", destination.Get(0));
803   EXPECT_EQ("5", destination.Get(1));
804 }
805 
TEST(RepeatedPtrField,SelfAssign)806 TEST(RepeatedPtrField, SelfAssign) {
807   // Verify that assignment to self does not destroy data.
808   RepeatedPtrField<string> source, *p;
809   p = &source;
810   source.Add()->assign("7");
811   source.Add()->assign("8");
812 
813   *p = source;
814 
815   ASSERT_EQ(2, source.size());
816   EXPECT_EQ("7", source.Get(0));
817   EXPECT_EQ("8", source.Get(1));
818 }
819 
TEST(RepeatedPtrField,MutableDataIsMutable)820 TEST(RepeatedPtrField, MutableDataIsMutable) {
821   RepeatedPtrField<string> field;
822   *field.Add() = "1";
823   EXPECT_EQ("1", field.Get(0));
824   // The fact that this line compiles would be enough, but we'll check the
825   // value anyway.
826   string** data = field.mutable_data();
827   **data = "2";
828   EXPECT_EQ("2", field.Get(0));
829 }
830 
TEST(RepeatedPtrField,ExtractSubrange)831 TEST(RepeatedPtrField, ExtractSubrange) {
832   // Exhaustively test every subrange in arrays of all sizes from 0 through 9
833   // with 0 through 3 cleared elements at the end.
834   for (int sz = 0; sz < 10; ++sz) {
835     for (int num = 0; num <= sz; ++num) {
836       for (int start = 0; start < sz - num; ++start) {
837         for (int extra = 0; extra < 4; ++extra) {
838           vector<string*> subject;
839 
840           // Create an array with "sz" elements and "extra" cleared elements.
841           RepeatedPtrField<string> field;
842           for (int i = 0; i < sz + extra; ++i) {
843             subject.push_back(new string());
844             field.AddAllocated(subject[i]);
845           }
846           EXPECT_EQ(field.size(), sz + extra);
847           for (int i = 0; i < extra; ++i)
848             field.RemoveLast();
849           EXPECT_EQ(field.size(), sz);
850           EXPECT_EQ(field.ClearedCount(), extra);
851 
852           // Create a catcher array and call ExtractSubrange.
853           string* catcher[10];
854           for (int i = 0; i < 10; ++i)
855             catcher[i] = NULL;
856           field.ExtractSubrange(start, num, catcher);
857 
858           // Does the resulting array have the right size?
859           EXPECT_EQ(field.size(), sz - num);
860 
861           // Were the removed elements extracted into the catcher array?
862           for (int i = 0; i < num; ++i)
863             EXPECT_EQ(catcher[i], subject[start + i]);
864           EXPECT_EQ(NULL, catcher[num]);
865 
866           // Does the resulting array contain the right values?
867           for (int i = 0; i < start; ++i)
868             EXPECT_EQ(field.Mutable(i), subject[i]);
869           for (int i = start; i < field.size(); ++i)
870             EXPECT_EQ(field.Mutable(i), subject[i + num]);
871 
872           // Reinstate the cleared elements.
873           EXPECT_EQ(field.ClearedCount(), extra);
874           for (int i = 0; i < extra; ++i)
875             field.Add();
876           EXPECT_EQ(field.ClearedCount(), 0);
877           EXPECT_EQ(field.size(), sz - num + extra);
878 
879           // Make sure the extra elements are all there (in some order).
880           for (int i = sz; i < sz + extra; ++i) {
881             int count = 0;
882             for (int j = sz; j < sz + extra; ++j) {
883               if (field.Mutable(j - num) == subject[i])
884                 count += 1;
885             }
886             EXPECT_EQ(count, 1);
887           }
888 
889           // Release the caught elements.
890           for (int i = 0; i < num; ++i)
891             delete catcher[i];
892         }
893       }
894     }
895   }
896 }
897 
TEST(RepeatedPtrField,DeleteSubrange)898 TEST(RepeatedPtrField, DeleteSubrange) {
899   // DeleteSubrange is a trivial extension of ExtendSubrange.
900 }
901 
902 // ===================================================================
903 
904 // Iterator tests stolen from net/proto/proto-array_unittest.
905 class RepeatedFieldIteratorTest : public testing::Test {
906  protected:
SetUp()907   virtual void SetUp() {
908     for (int i = 0; i < 3; ++i) {
909       proto_array_.Add(i);
910     }
911   }
912 
913   RepeatedField<int> proto_array_;
914 };
915 
TEST_F(RepeatedFieldIteratorTest,Convertible)916 TEST_F(RepeatedFieldIteratorTest, Convertible) {
917   RepeatedField<int>::iterator iter = proto_array_.begin();
918   RepeatedField<int>::const_iterator c_iter = iter;
919   RepeatedField<int>::value_type value = *c_iter;
920   EXPECT_EQ(0, value);
921 }
922 
TEST_F(RepeatedFieldIteratorTest,MutableIteration)923 TEST_F(RepeatedFieldIteratorTest, MutableIteration) {
924   RepeatedField<int>::iterator iter = proto_array_.begin();
925   EXPECT_EQ(0, *iter);
926   ++iter;
927   EXPECT_EQ(1, *iter++);
928   EXPECT_EQ(2, *iter);
929   ++iter;
930   EXPECT_TRUE(proto_array_.end() == iter);
931 
932   EXPECT_EQ(2, *(proto_array_.end() - 1));
933 }
934 
TEST_F(RepeatedFieldIteratorTest,ConstIteration)935 TEST_F(RepeatedFieldIteratorTest, ConstIteration) {
936   const RepeatedField<int>& const_proto_array = proto_array_;
937   RepeatedField<int>::const_iterator iter = const_proto_array.begin();
938   EXPECT_EQ(0, *iter);
939   ++iter;
940   EXPECT_EQ(1, *iter++);
941   EXPECT_EQ(2, *iter);
942   ++iter;
943   EXPECT_TRUE(proto_array_.end() == iter);
944   EXPECT_EQ(2, *(proto_array_.end() - 1));
945 }
946 
TEST_F(RepeatedFieldIteratorTest,Mutation)947 TEST_F(RepeatedFieldIteratorTest, Mutation) {
948   RepeatedField<int>::iterator iter = proto_array_.begin();
949   *iter = 7;
950   EXPECT_EQ(7, proto_array_.Get(0));
951 }
952 
953 // -------------------------------------------------------------------
954 
955 class RepeatedPtrFieldIteratorTest : public testing::Test {
956  protected:
SetUp()957   virtual void SetUp() {
958     proto_array_.Add()->assign("foo");
959     proto_array_.Add()->assign("bar");
960     proto_array_.Add()->assign("baz");
961   }
962 
963   RepeatedPtrField<string> proto_array_;
964 };
965 
TEST_F(RepeatedPtrFieldIteratorTest,Convertible)966 TEST_F(RepeatedPtrFieldIteratorTest, Convertible) {
967   RepeatedPtrField<string>::iterator iter = proto_array_.begin();
968   RepeatedPtrField<string>::const_iterator c_iter = iter;
969   RepeatedPtrField<string>::value_type value = *c_iter;
970   EXPECT_EQ("foo", value);
971 }
972 
TEST_F(RepeatedPtrFieldIteratorTest,MutableIteration)973 TEST_F(RepeatedPtrFieldIteratorTest, MutableIteration) {
974   RepeatedPtrField<string>::iterator iter = proto_array_.begin();
975   EXPECT_EQ("foo", *iter);
976   ++iter;
977   EXPECT_EQ("bar", *(iter++));
978   EXPECT_EQ("baz", *iter);
979   ++iter;
980   EXPECT_TRUE(proto_array_.end() == iter);
981   EXPECT_EQ("baz", *(--proto_array_.end()));
982 }
983 
TEST_F(RepeatedPtrFieldIteratorTest,ConstIteration)984 TEST_F(RepeatedPtrFieldIteratorTest, ConstIteration) {
985   const RepeatedPtrField<string>& const_proto_array = proto_array_;
986   RepeatedPtrField<string>::const_iterator iter = const_proto_array.begin();
987   EXPECT_EQ("foo", *iter);
988   ++iter;
989   EXPECT_EQ("bar", *(iter++));
990   EXPECT_EQ("baz", *iter);
991   ++iter;
992   EXPECT_TRUE(const_proto_array.end() == iter);
993   EXPECT_EQ("baz", *(--const_proto_array.end()));
994 }
995 
TEST_F(RepeatedPtrFieldIteratorTest,MutableReverseIteration)996 TEST_F(RepeatedPtrFieldIteratorTest, MutableReverseIteration) {
997   RepeatedPtrField<string>::reverse_iterator iter = proto_array_.rbegin();
998   EXPECT_EQ("baz", *iter);
999   ++iter;
1000   EXPECT_EQ("bar", *(iter++));
1001   EXPECT_EQ("foo", *iter);
1002   ++iter;
1003   EXPECT_TRUE(proto_array_.rend() == iter);
1004   EXPECT_EQ("foo", *(--proto_array_.rend()));
1005 }
1006 
TEST_F(RepeatedPtrFieldIteratorTest,ConstReverseIteration)1007 TEST_F(RepeatedPtrFieldIteratorTest, ConstReverseIteration) {
1008   const RepeatedPtrField<string>& const_proto_array = proto_array_;
1009   RepeatedPtrField<string>::const_reverse_iterator iter
1010       = const_proto_array.rbegin();
1011   EXPECT_EQ("baz", *iter);
1012   ++iter;
1013   EXPECT_EQ("bar", *(iter++));
1014   EXPECT_EQ("foo", *iter);
1015   ++iter;
1016   EXPECT_TRUE(const_proto_array.rend() == iter);
1017   EXPECT_EQ("foo", *(--const_proto_array.rend()));
1018 }
1019 
TEST_F(RepeatedPtrFieldIteratorTest,RandomAccess)1020 TEST_F(RepeatedPtrFieldIteratorTest, RandomAccess) {
1021   RepeatedPtrField<string>::iterator iter = proto_array_.begin();
1022   RepeatedPtrField<string>::iterator iter2 = iter;
1023   ++iter2;
1024   ++iter2;
1025   EXPECT_TRUE(iter + 2 == iter2);
1026   EXPECT_TRUE(iter == iter2 - 2);
1027   EXPECT_EQ("baz", iter[2]);
1028   EXPECT_EQ("baz", *(iter + 2));
1029   EXPECT_EQ(3, proto_array_.end() - proto_array_.begin());
1030 }
1031 
TEST_F(RepeatedPtrFieldIteratorTest,Comparable)1032 TEST_F(RepeatedPtrFieldIteratorTest, Comparable) {
1033   RepeatedPtrField<string>::const_iterator iter = proto_array_.begin();
1034   RepeatedPtrField<string>::const_iterator iter2 = iter + 1;
1035   EXPECT_TRUE(iter == iter);
1036   EXPECT_TRUE(iter != iter2);
1037   EXPECT_TRUE(iter < iter2);
1038   EXPECT_TRUE(iter <= iter2);
1039   EXPECT_TRUE(iter <= iter);
1040   EXPECT_TRUE(iter2 > iter);
1041   EXPECT_TRUE(iter2 >= iter);
1042   EXPECT_TRUE(iter >= iter);
1043 }
1044 
1045 // Uninitialized iterator does not point to any of the RepeatedPtrField.
TEST_F(RepeatedPtrFieldIteratorTest,UninitializedIterator)1046 TEST_F(RepeatedPtrFieldIteratorTest, UninitializedIterator) {
1047   RepeatedPtrField<string>::iterator iter;
1048   EXPECT_TRUE(iter != proto_array_.begin());
1049   EXPECT_TRUE(iter != proto_array_.begin() + 1);
1050   EXPECT_TRUE(iter != proto_array_.begin() + 2);
1051   EXPECT_TRUE(iter != proto_array_.begin() + 3);
1052   EXPECT_TRUE(iter != proto_array_.end());
1053 }
1054 
TEST_F(RepeatedPtrFieldIteratorTest,STLAlgorithms_lower_bound)1055 TEST_F(RepeatedPtrFieldIteratorTest, STLAlgorithms_lower_bound) {
1056   proto_array_.Clear();
1057   proto_array_.Add()->assign("a");
1058   proto_array_.Add()->assign("c");
1059   proto_array_.Add()->assign("d");
1060   proto_array_.Add()->assign("n");
1061   proto_array_.Add()->assign("p");
1062   proto_array_.Add()->assign("x");
1063   proto_array_.Add()->assign("y");
1064 
1065   string v = "f";
1066   RepeatedPtrField<string>::const_iterator it =
1067       lower_bound(proto_array_.begin(), proto_array_.end(), v);
1068 
1069   EXPECT_EQ(*it, "n");
1070   EXPECT_TRUE(it == proto_array_.begin() + 3);
1071 }
1072 
TEST_F(RepeatedPtrFieldIteratorTest,Mutation)1073 TEST_F(RepeatedPtrFieldIteratorTest, Mutation) {
1074   RepeatedPtrField<string>::iterator iter = proto_array_.begin();
1075   *iter = "qux";
1076   EXPECT_EQ("qux", proto_array_.Get(0));
1077 }
1078 
1079 // -------------------------------------------------------------------
1080 
1081 class RepeatedPtrFieldPtrsIteratorTest : public testing::Test {
1082  protected:
SetUp()1083   virtual void SetUp() {
1084     proto_array_.Add()->assign("foo");
1085     proto_array_.Add()->assign("bar");
1086     proto_array_.Add()->assign("baz");
1087     const_proto_array_ = &proto_array_;
1088   }
1089 
1090   RepeatedPtrField<string> proto_array_;
1091   const RepeatedPtrField<string>* const_proto_array_;
1092 };
1093 
TEST_F(RepeatedPtrFieldPtrsIteratorTest,ConvertiblePtr)1094 TEST_F(RepeatedPtrFieldPtrsIteratorTest, ConvertiblePtr) {
1095   RepeatedPtrField<string>::pointer_iterator iter =
1096       proto_array_.pointer_begin();
1097   static_cast<void>(iter);
1098 }
1099 
TEST_F(RepeatedPtrFieldPtrsIteratorTest,ConvertibleConstPtr)1100 TEST_F(RepeatedPtrFieldPtrsIteratorTest, ConvertibleConstPtr) {
1101   RepeatedPtrField<string>::const_pointer_iterator iter =
1102       const_proto_array_->pointer_begin();
1103   static_cast<void>(iter);
1104 }
1105 
TEST_F(RepeatedPtrFieldPtrsIteratorTest,MutablePtrIteration)1106 TEST_F(RepeatedPtrFieldPtrsIteratorTest, MutablePtrIteration) {
1107   RepeatedPtrField<string>::pointer_iterator iter =
1108       proto_array_.pointer_begin();
1109   EXPECT_EQ("foo", **iter);
1110   ++iter;
1111   EXPECT_EQ("bar", **(iter++));
1112   EXPECT_EQ("baz", **iter);
1113   ++iter;
1114   EXPECT_TRUE(proto_array_.pointer_end() == iter);
1115   EXPECT_EQ("baz", **(--proto_array_.pointer_end()));
1116 }
1117 
TEST_F(RepeatedPtrFieldPtrsIteratorTest,MutableConstPtrIteration)1118 TEST_F(RepeatedPtrFieldPtrsIteratorTest, MutableConstPtrIteration) {
1119   RepeatedPtrField<string>::const_pointer_iterator iter =
1120       const_proto_array_->pointer_begin();
1121   EXPECT_EQ("foo", **iter);
1122   ++iter;
1123   EXPECT_EQ("bar", **(iter++));
1124   EXPECT_EQ("baz", **iter);
1125   ++iter;
1126   EXPECT_TRUE(const_proto_array_->pointer_end() == iter);
1127   EXPECT_EQ("baz", **(--const_proto_array_->pointer_end()));
1128 }
1129 
TEST_F(RepeatedPtrFieldPtrsIteratorTest,RandomPtrAccess)1130 TEST_F(RepeatedPtrFieldPtrsIteratorTest, RandomPtrAccess) {
1131   RepeatedPtrField<string>::pointer_iterator iter =
1132       proto_array_.pointer_begin();
1133   RepeatedPtrField<string>::pointer_iterator iter2 = iter;
1134   ++iter2;
1135   ++iter2;
1136   EXPECT_TRUE(iter + 2 == iter2);
1137   EXPECT_TRUE(iter == iter2 - 2);
1138   EXPECT_EQ("baz", *iter[2]);
1139   EXPECT_EQ("baz", **(iter + 2));
1140   EXPECT_EQ(3, proto_array_.end() - proto_array_.begin());
1141 }
1142 
TEST_F(RepeatedPtrFieldPtrsIteratorTest,RandomConstPtrAccess)1143 TEST_F(RepeatedPtrFieldPtrsIteratorTest, RandomConstPtrAccess) {
1144   RepeatedPtrField<string>::const_pointer_iterator iter =
1145       const_proto_array_->pointer_begin();
1146   RepeatedPtrField<string>::const_pointer_iterator iter2 = iter;
1147   ++iter2;
1148   ++iter2;
1149   EXPECT_TRUE(iter + 2 == iter2);
1150   EXPECT_TRUE(iter == iter2 - 2);
1151   EXPECT_EQ("baz", *iter[2]);
1152   EXPECT_EQ("baz", **(iter + 2));
1153   EXPECT_EQ(3, const_proto_array_->end() - const_proto_array_->begin());
1154 }
1155 
TEST_F(RepeatedPtrFieldPtrsIteratorTest,ComparablePtr)1156 TEST_F(RepeatedPtrFieldPtrsIteratorTest, ComparablePtr) {
1157   RepeatedPtrField<string>::pointer_iterator iter =
1158       proto_array_.pointer_begin();
1159   RepeatedPtrField<string>::pointer_iterator iter2 = iter + 1;
1160   EXPECT_TRUE(iter == iter);
1161   EXPECT_TRUE(iter != iter2);
1162   EXPECT_TRUE(iter < iter2);
1163   EXPECT_TRUE(iter <= iter2);
1164   EXPECT_TRUE(iter <= iter);
1165   EXPECT_TRUE(iter2 > iter);
1166   EXPECT_TRUE(iter2 >= iter);
1167   EXPECT_TRUE(iter >= iter);
1168 }
1169 
TEST_F(RepeatedPtrFieldPtrsIteratorTest,ComparableConstPtr)1170 TEST_F(RepeatedPtrFieldPtrsIteratorTest, ComparableConstPtr) {
1171   RepeatedPtrField<string>::const_pointer_iterator iter =
1172       const_proto_array_->pointer_begin();
1173   RepeatedPtrField<string>::const_pointer_iterator iter2 = iter + 1;
1174   EXPECT_TRUE(iter == iter);
1175   EXPECT_TRUE(iter != iter2);
1176   EXPECT_TRUE(iter < iter2);
1177   EXPECT_TRUE(iter <= iter2);
1178   EXPECT_TRUE(iter <= iter);
1179   EXPECT_TRUE(iter2 > iter);
1180   EXPECT_TRUE(iter2 >= iter);
1181   EXPECT_TRUE(iter >= iter);
1182 }
1183 
1184 // Uninitialized iterator does not point to any of the RepeatedPtrOverPtrs.
1185 // Dereferencing an uninitialized iterator crashes the process.
TEST_F(RepeatedPtrFieldPtrsIteratorTest,UninitializedPtrIterator)1186 TEST_F(RepeatedPtrFieldPtrsIteratorTest, UninitializedPtrIterator) {
1187   RepeatedPtrField<string>::pointer_iterator iter;
1188   EXPECT_TRUE(iter != proto_array_.pointer_begin());
1189   EXPECT_TRUE(iter != proto_array_.pointer_begin() + 1);
1190   EXPECT_TRUE(iter != proto_array_.pointer_begin() + 2);
1191   EXPECT_TRUE(iter != proto_array_.pointer_begin() + 3);
1192   EXPECT_TRUE(iter != proto_array_.pointer_end());
1193 }
1194 
TEST_F(RepeatedPtrFieldPtrsIteratorTest,UninitializedConstPtrIterator)1195 TEST_F(RepeatedPtrFieldPtrsIteratorTest, UninitializedConstPtrIterator) {
1196   RepeatedPtrField<string>::const_pointer_iterator iter;
1197   EXPECT_TRUE(iter != const_proto_array_->pointer_begin());
1198   EXPECT_TRUE(iter != const_proto_array_->pointer_begin() + 1);
1199   EXPECT_TRUE(iter != const_proto_array_->pointer_begin() + 2);
1200   EXPECT_TRUE(iter != const_proto_array_->pointer_begin() + 3);
1201   EXPECT_TRUE(iter != const_proto_array_->pointer_end());
1202 }
1203 
1204 // This comparison functor is required by the tests for RepeatedPtrOverPtrs.
1205 // They operate on strings and need to compare strings as strings in
1206 // any stl algorithm, even though the iterator returns a pointer to a string
1207 // - i.e. *iter has type string*.
1208 struct StringLessThan {
operator ()google::protobuf::__anon42b75c540111::StringLessThan1209   bool operator()(const string* z, const string& y) {
1210     return *z < y;
1211   }
operator ()google::protobuf::__anon42b75c540111::StringLessThan1212   bool operator()(const string* z, const string* y) const { return *z < *y; }
1213 };
1214 
TEST_F(RepeatedPtrFieldPtrsIteratorTest,PtrSTLAlgorithms_lower_bound)1215 TEST_F(RepeatedPtrFieldPtrsIteratorTest, PtrSTLAlgorithms_lower_bound) {
1216   proto_array_.Clear();
1217   proto_array_.Add()->assign("a");
1218   proto_array_.Add()->assign("c");
1219   proto_array_.Add()->assign("d");
1220   proto_array_.Add()->assign("n");
1221   proto_array_.Add()->assign("p");
1222   proto_array_.Add()->assign("x");
1223   proto_array_.Add()->assign("y");
1224 
1225   {
1226     string v = "f";
1227     RepeatedPtrField<string>::pointer_iterator it =
1228         lower_bound(proto_array_.pointer_begin(), proto_array_.pointer_end(),
1229                     &v, StringLessThan());
1230 
1231     GOOGLE_CHECK(*it != NULL);
1232 
1233     EXPECT_EQ(**it, "n");
1234     EXPECT_TRUE(it == proto_array_.pointer_begin() + 3);
1235   }
1236   {
1237     string v = "f";
1238     RepeatedPtrField<string>::const_pointer_iterator it =
1239         lower_bound(const_proto_array_->pointer_begin(),
1240                     const_proto_array_->pointer_end(),
1241                     &v, StringLessThan());
1242 
1243     GOOGLE_CHECK(*it != NULL);
1244 
1245     EXPECT_EQ(**it, "n");
1246     EXPECT_TRUE(it == const_proto_array_->pointer_begin() + 3);
1247   }
1248 }
1249 
TEST_F(RepeatedPtrFieldPtrsIteratorTest,PtrMutation)1250 TEST_F(RepeatedPtrFieldPtrsIteratorTest, PtrMutation) {
1251   RepeatedPtrField<string>::pointer_iterator iter =
1252       proto_array_.pointer_begin();
1253   **iter = "qux";
1254   EXPECT_EQ("qux", proto_array_.Get(0));
1255 
1256   EXPECT_EQ("bar", proto_array_.Get(1));
1257   EXPECT_EQ("baz", proto_array_.Get(2));
1258   ++iter;
1259   delete *iter;
1260   *iter = new string("a");
1261   ++iter;
1262   delete *iter;
1263   *iter = new string("b");
1264   EXPECT_EQ("a", proto_array_.Get(1));
1265   EXPECT_EQ("b", proto_array_.Get(2));
1266 }
1267 
TEST_F(RepeatedPtrFieldPtrsIteratorTest,Sort)1268 TEST_F(RepeatedPtrFieldPtrsIteratorTest, Sort) {
1269   proto_array_.Add()->assign("c");
1270   proto_array_.Add()->assign("d");
1271   proto_array_.Add()->assign("n");
1272   proto_array_.Add()->assign("p");
1273   proto_array_.Add()->assign("a");
1274   proto_array_.Add()->assign("y");
1275   proto_array_.Add()->assign("x");
1276   EXPECT_EQ("foo", proto_array_.Get(0));
1277   EXPECT_EQ("n", proto_array_.Get(5));
1278   EXPECT_EQ("x", proto_array_.Get(9));
1279   sort(proto_array_.pointer_begin(),
1280        proto_array_.pointer_end(),
1281        StringLessThan());
1282   EXPECT_EQ("a", proto_array_.Get(0));
1283   EXPECT_EQ("baz", proto_array_.Get(2));
1284   EXPECT_EQ("y", proto_array_.Get(9));
1285 }
1286 
1287 
1288 // -----------------------------------------------------------------------------
1289 // Unit-tests for the insert iterators
1290 // google::protobuf::RepeatedFieldBackInserter,
1291 // google::protobuf::AllocatedRepeatedPtrFieldBackInserter
1292 // Ported from util/gtl/proto-array-iterators_unittest.
1293 
1294 class RepeatedFieldInsertionIteratorsTest : public testing::Test {
1295  protected:
1296   std::list<double> halves;
1297   std::list<int> fibonacci;
1298   std::vector<string> words;
1299   typedef TestAllTypes::NestedMessage Nested;
1300   Nested nesteds[2];
1301   std::vector<Nested*> nested_ptrs;
1302   TestAllTypes protobuffer;
1303 
SetUp()1304   virtual void SetUp() {
1305     fibonacci.push_back(1);
1306     fibonacci.push_back(1);
1307     fibonacci.push_back(2);
1308     fibonacci.push_back(3);
1309     fibonacci.push_back(5);
1310     fibonacci.push_back(8);
1311     std::copy(fibonacci.begin(), fibonacci.end(),
1312               RepeatedFieldBackInserter(protobuffer.mutable_repeated_int32()));
1313 
1314     halves.push_back(1.0);
1315     halves.push_back(0.5);
1316     halves.push_back(0.25);
1317     halves.push_back(0.125);
1318     halves.push_back(0.0625);
1319     std::copy(halves.begin(), halves.end(),
1320               RepeatedFieldBackInserter(protobuffer.mutable_repeated_double()));
1321 
1322     words.push_back("Able");
1323     words.push_back("was");
1324     words.push_back("I");
1325     words.push_back("ere");
1326     words.push_back("I");
1327     words.push_back("saw");
1328     words.push_back("Elba");
1329     std::copy(words.begin(), words.end(),
1330               RepeatedFieldBackInserter(protobuffer.mutable_repeated_string()));
1331 
1332     nesteds[0].set_bb(17);
1333     nesteds[1].set_bb(4711);
1334     std::copy(&nesteds[0], &nesteds[2],
1335               RepeatedFieldBackInserter(
1336                   protobuffer.mutable_repeated_nested_message()));
1337 
1338     nested_ptrs.push_back(new Nested);
1339     nested_ptrs.back()->set_bb(170);
1340     nested_ptrs.push_back(new Nested);
1341     nested_ptrs.back()->set_bb(47110);
1342     std::copy(nested_ptrs.begin(), nested_ptrs.end(),
1343               RepeatedFieldBackInserter(
1344                   protobuffer.mutable_repeated_nested_message()));
1345 
1346   }
1347 
TearDown()1348   virtual void TearDown() {
1349     STLDeleteContainerPointers(nested_ptrs.begin(), nested_ptrs.end());
1350   }
1351 };
1352 
TEST_F(RepeatedFieldInsertionIteratorsTest,Fibonacci)1353 TEST_F(RepeatedFieldInsertionIteratorsTest, Fibonacci) {
1354   EXPECT_TRUE(std::equal(fibonacci.begin(),
1355                          fibonacci.end(),
1356                          protobuffer.repeated_int32().begin()));
1357   EXPECT_TRUE(std::equal(protobuffer.repeated_int32().begin(),
1358                          protobuffer.repeated_int32().end(),
1359                          fibonacci.begin()));
1360 }
1361 
TEST_F(RepeatedFieldInsertionIteratorsTest,Halves)1362 TEST_F(RepeatedFieldInsertionIteratorsTest, Halves) {
1363   EXPECT_TRUE(std::equal(halves.begin(),
1364                          halves.end(),
1365                          protobuffer.repeated_double().begin()));
1366   EXPECT_TRUE(std::equal(protobuffer.repeated_double().begin(),
1367                          protobuffer.repeated_double().end(),
1368                          halves.begin()));
1369 }
1370 
TEST_F(RepeatedFieldInsertionIteratorsTest,Words)1371 TEST_F(RepeatedFieldInsertionIteratorsTest, Words) {
1372   ASSERT_EQ(words.size(), protobuffer.repeated_string_size());
1373   for (int i = 0; i < words.size(); ++i)
1374     EXPECT_EQ(words.at(i), protobuffer.repeated_string(i));
1375 }
1376 
TEST_F(RepeatedFieldInsertionIteratorsTest,Words2)1377 TEST_F(RepeatedFieldInsertionIteratorsTest, Words2) {
1378   words.clear();
1379   words.push_back("sing");
1380   words.push_back("a");
1381   words.push_back("song");
1382   words.push_back("of");
1383   words.push_back("six");
1384   words.push_back("pence");
1385   protobuffer.mutable_repeated_string()->Clear();
1386   std::copy(words.begin(), words.end(), RepeatedPtrFieldBackInserter(
1387       protobuffer.mutable_repeated_string()));
1388   ASSERT_EQ(words.size(), protobuffer.repeated_string_size());
1389   for (int i = 0; i < words.size(); ++i)
1390     EXPECT_EQ(words.at(i), protobuffer.repeated_string(i));
1391 }
1392 
TEST_F(RepeatedFieldInsertionIteratorsTest,Nesteds)1393 TEST_F(RepeatedFieldInsertionIteratorsTest, Nesteds) {
1394   ASSERT_EQ(protobuffer.repeated_nested_message_size(), 4);
1395   EXPECT_EQ(protobuffer.repeated_nested_message(0).bb(), 17);
1396   EXPECT_EQ(protobuffer.repeated_nested_message(1).bb(), 4711);
1397   EXPECT_EQ(protobuffer.repeated_nested_message(2).bb(), 170);
1398   EXPECT_EQ(protobuffer.repeated_nested_message(3).bb(), 47110);
1399 }
1400 
TEST_F(RepeatedFieldInsertionIteratorsTest,AllocatedRepeatedPtrFieldWithStringIntData)1401 TEST_F(RepeatedFieldInsertionIteratorsTest,
1402        AllocatedRepeatedPtrFieldWithStringIntData) {
1403   vector<Nested*> data;
1404   TestAllTypes goldenproto;
1405   for (int i = 0; i < 10; ++i) {
1406     Nested* new_data = new Nested;
1407     new_data->set_bb(i);
1408     data.push_back(new_data);
1409 
1410     new_data = goldenproto.add_repeated_nested_message();
1411     new_data->set_bb(i);
1412   }
1413   TestAllTypes testproto;
1414   copy(data.begin(), data.end(),
1415        AllocatedRepeatedPtrFieldBackInserter(
1416            testproto.mutable_repeated_nested_message()));
1417   EXPECT_EQ(testproto.DebugString(), goldenproto.DebugString());
1418 }
1419 
TEST_F(RepeatedFieldInsertionIteratorsTest,AllocatedRepeatedPtrFieldWithString)1420 TEST_F(RepeatedFieldInsertionIteratorsTest,
1421        AllocatedRepeatedPtrFieldWithString) {
1422   vector<string*> data;
1423   TestAllTypes goldenproto;
1424   for (int i = 0; i < 10; ++i) {
1425     string* new_data = new string;
1426     *new_data = "name-" + SimpleItoa(i);
1427     data.push_back(new_data);
1428 
1429     new_data = goldenproto.add_repeated_string();
1430     *new_data = "name-" + SimpleItoa(i);
1431   }
1432   TestAllTypes testproto;
1433   copy(data.begin(), data.end(),
1434        AllocatedRepeatedPtrFieldBackInserter(
1435            testproto.mutable_repeated_string()));
1436   EXPECT_EQ(testproto.DebugString(), goldenproto.DebugString());
1437 }
1438 
1439 }  // namespace
1440 
1441 }  // namespace protobuf
1442 }  // namespace google
1443