1 // Copyright (c) 2019 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #include "quiche/quic/core/quic_interval.h"
6
7 #include <sstream>
8 #include <string>
9 #include <type_traits>
10 #include <utility>
11
12 #include "quiche/quic/core/quic_time.h"
13 #include "quiche/quic/platform/api/quic_test.h"
14
15 namespace quic {
16 namespace test {
17 namespace {
18
19 template <typename ForwardIterator>
STLDeleteContainerPointers(ForwardIterator begin,ForwardIterator end)20 void STLDeleteContainerPointers(ForwardIterator begin, ForwardIterator end) {
21 while (begin != end) {
22 auto temp = begin;
23 ++begin;
24 delete *temp;
25 }
26 }
27
28 template <typename T>
STLDeleteElements(T * container)29 void STLDeleteElements(T* container) {
30 if (!container) return;
31 STLDeleteContainerPointers(container->begin(), container->end());
32 container->clear();
33 }
34
35 class ConstructorListener {
36 public:
ConstructorListener(int * copy_construct_counter,int * move_construct_counter)37 ConstructorListener(int* copy_construct_counter, int* move_construct_counter)
38 : copy_construct_counter_(copy_construct_counter),
39 move_construct_counter_(move_construct_counter) {
40 *copy_construct_counter_ = 0;
41 *move_construct_counter_ = 0;
42 }
ConstructorListener(const ConstructorListener & other)43 ConstructorListener(const ConstructorListener& other) {
44 copy_construct_counter_ = other.copy_construct_counter_;
45 move_construct_counter_ = other.move_construct_counter_;
46 ++*copy_construct_counter_;
47 }
ConstructorListener(ConstructorListener && other)48 ConstructorListener(ConstructorListener&& other) {
49 copy_construct_counter_ = other.copy_construct_counter_;
50 move_construct_counter_ = other.move_construct_counter_;
51 ++*move_construct_counter_;
52 }
operator <(const ConstructorListener &)53 bool operator<(const ConstructorListener&) { return false; }
operator >(const ConstructorListener &)54 bool operator>(const ConstructorListener&) { return false; }
operator <=(const ConstructorListener &)55 bool operator<=(const ConstructorListener&) { return true; }
operator >=(const ConstructorListener &)56 bool operator>=(const ConstructorListener&) { return true; }
operator ==(const ConstructorListener &)57 bool operator==(const ConstructorListener&) { return true; }
58
59 private:
60 int* copy_construct_counter_;
61 int* move_construct_counter_;
62 };
63
TEST(QuicIntervalConstructorTest,Move)64 TEST(QuicIntervalConstructorTest, Move) {
65 int object1_copy_count, object1_move_count;
66 ConstructorListener object1(&object1_copy_count, &object1_move_count);
67 int object2_copy_count, object2_move_count;
68 ConstructorListener object2(&object2_copy_count, &object2_move_count);
69
70 QuicInterval<ConstructorListener> interval(object1, std::move(object2));
71 EXPECT_EQ(1, object1_copy_count);
72 EXPECT_EQ(0, object1_move_count);
73 EXPECT_EQ(0, object2_copy_count);
74 EXPECT_EQ(1, object2_move_count);
75 }
76
TEST(QuicIntervalConstructorTest,ImplicitConversion)77 TEST(QuicIntervalConstructorTest, ImplicitConversion) {
78 struct WrappedInt {
79 WrappedInt(int value) : value(value) {}
80 bool operator<(const WrappedInt& other) { return value < other.value; }
81 bool operator>(const WrappedInt& other) { return value > other.value; }
82 bool operator<=(const WrappedInt& other) { return value <= other.value; }
83 bool operator>=(const WrappedInt& other) { return value >= other.value; }
84 bool operator==(const WrappedInt& other) { return value == other.value; }
85 int value;
86 };
87
88 static_assert(std::is_convertible<int, WrappedInt>::value, "");
89 static_assert(
90 std::is_constructible<QuicInterval<WrappedInt>, int, int>::value, "");
91
92 QuicInterval<WrappedInt> i(10, 20);
93 EXPECT_EQ(10, i.min().value);
94 EXPECT_EQ(20, i.max().value);
95 }
96
97 class QuicIntervalTest : public QuicTest {
98 protected:
99 // Test intersection between the two intervals i1 and i2. Tries
100 // i1.IntersectWith(i2) and vice versa. The intersection should change i1 iff
101 // changes_i1 is true, and the same for changes_i2. The resulting
102 // intersection should be result.
TestIntersect(const QuicInterval<int64_t> & i1,const QuicInterval<int64_t> & i2,bool changes_i1,bool changes_i2,const QuicInterval<int64_t> & result)103 void TestIntersect(const QuicInterval<int64_t>& i1,
104 const QuicInterval<int64_t>& i2, bool changes_i1,
105 bool changes_i2, const QuicInterval<int64_t>& result) {
106 QuicInterval<int64_t> i;
107 i = i1;
108 EXPECT_TRUE(i.IntersectWith(i2) == changes_i1 && i == result);
109 i = i2;
110 EXPECT_TRUE(i.IntersectWith(i1) == changes_i2 && i == result);
111 }
112 };
113
TEST_F(QuicIntervalTest,ConstructorsCopyAndClear)114 TEST_F(QuicIntervalTest, ConstructorsCopyAndClear) {
115 QuicInterval<int32_t> empty;
116 EXPECT_TRUE(empty.Empty());
117
118 QuicInterval<int32_t> d2(0, 100);
119 EXPECT_EQ(0, d2.min());
120 EXPECT_EQ(100, d2.max());
121 EXPECT_EQ(QuicInterval<int32_t>(0, 100), d2);
122 EXPECT_NE(QuicInterval<int32_t>(0, 99), d2);
123
124 empty = d2;
125 EXPECT_EQ(0, d2.min());
126 EXPECT_EQ(100, d2.max());
127 EXPECT_TRUE(empty == d2);
128 EXPECT_EQ(empty, d2);
129 EXPECT_TRUE(d2 == empty);
130 EXPECT_EQ(d2, empty);
131
132 QuicInterval<int32_t> max_less_than_min(40, 20);
133 EXPECT_TRUE(max_less_than_min.Empty());
134 EXPECT_EQ(40, max_less_than_min.min());
135 EXPECT_EQ(20, max_less_than_min.max());
136
137 QuicInterval<int> d3(10, 20);
138 d3.Clear();
139 EXPECT_TRUE(d3.Empty());
140 }
141
TEST_F(QuicIntervalTest,MakeQuicInterval)142 TEST_F(QuicIntervalTest, MakeQuicInterval) {
143 static_assert(
144 std::is_same<QuicInterval<int>, decltype(MakeQuicInterval(0, 3))>::value,
145 "Type is deduced incorrectly.");
146 static_assert(std::is_same<QuicInterval<double>,
147 decltype(MakeQuicInterval(0., 3.))>::value,
148 "Type is deduced incorrectly.");
149
150 EXPECT_EQ(MakeQuicInterval(0., 3.), QuicInterval<double>(0, 3));
151 }
152
TEST_F(QuicIntervalTest,GettersSetters)153 TEST_F(QuicIntervalTest, GettersSetters) {
154 QuicInterval<int32_t> d1(100, 200);
155
156 // SetMin:
157 d1.SetMin(30);
158 EXPECT_EQ(30, d1.min());
159 EXPECT_EQ(200, d1.max());
160
161 // SetMax:
162 d1.SetMax(220);
163 EXPECT_EQ(30, d1.min());
164 EXPECT_EQ(220, d1.max());
165
166 // Set:
167 d1.Clear();
168 d1.Set(30, 220);
169 EXPECT_EQ(30, d1.min());
170 EXPECT_EQ(220, d1.max());
171
172 // SpanningUnion:
173 QuicInterval<int32_t> d2;
174 EXPECT_TRUE(!d1.SpanningUnion(d2));
175 EXPECT_EQ(30, d1.min());
176 EXPECT_EQ(220, d1.max());
177
178 EXPECT_TRUE(d2.SpanningUnion(d1));
179 EXPECT_EQ(30, d2.min());
180 EXPECT_EQ(220, d2.max());
181
182 d2.SetMin(40);
183 d2.SetMax(100);
184 EXPECT_TRUE(!d1.SpanningUnion(d2));
185 EXPECT_EQ(30, d1.min());
186 EXPECT_EQ(220, d1.max());
187
188 d2.SetMin(20);
189 d2.SetMax(100);
190 EXPECT_TRUE(d1.SpanningUnion(d2));
191 EXPECT_EQ(20, d1.min());
192 EXPECT_EQ(220, d1.max());
193
194 d2.SetMin(50);
195 d2.SetMax(300);
196 EXPECT_TRUE(d1.SpanningUnion(d2));
197 EXPECT_EQ(20, d1.min());
198 EXPECT_EQ(300, d1.max());
199
200 d2.SetMin(0);
201 d2.SetMax(500);
202 EXPECT_TRUE(d1.SpanningUnion(d2));
203 EXPECT_EQ(0, d1.min());
204 EXPECT_EQ(500, d1.max());
205
206 d2.SetMin(100);
207 d2.SetMax(0);
208 EXPECT_TRUE(!d1.SpanningUnion(d2));
209 EXPECT_EQ(0, d1.min());
210 EXPECT_EQ(500, d1.max());
211 EXPECT_TRUE(d2.SpanningUnion(d1));
212 EXPECT_EQ(0, d2.min());
213 EXPECT_EQ(500, d2.max());
214 }
215
TEST_F(QuicIntervalTest,CoveringOps)216 TEST_F(QuicIntervalTest, CoveringOps) {
217 const QuicInterval<int64_t> empty;
218 const QuicInterval<int64_t> d(100, 200);
219 const QuicInterval<int64_t> d1(0, 50);
220 const QuicInterval<int64_t> d2(50, 110);
221 const QuicInterval<int64_t> d3(110, 180);
222 const QuicInterval<int64_t> d4(180, 220);
223 const QuicInterval<int64_t> d5(220, 300);
224 const QuicInterval<int64_t> d6(100, 150);
225 const QuicInterval<int64_t> d7(150, 200);
226 const QuicInterval<int64_t> d8(0, 300);
227
228 // Intersection:
229 EXPECT_TRUE(d.Intersects(d));
230 EXPECT_TRUE(!empty.Intersects(d) && !d.Intersects(empty));
231 EXPECT_TRUE(!d.Intersects(d1) && !d1.Intersects(d));
232 EXPECT_TRUE(d.Intersects(d2) && d2.Intersects(d));
233 EXPECT_TRUE(d.Intersects(d3) && d3.Intersects(d));
234 EXPECT_TRUE(d.Intersects(d4) && d4.Intersects(d));
235 EXPECT_TRUE(!d.Intersects(d5) && !d5.Intersects(d));
236 EXPECT_TRUE(d.Intersects(d6) && d6.Intersects(d));
237 EXPECT_TRUE(d.Intersects(d7) && d7.Intersects(d));
238 EXPECT_TRUE(d.Intersects(d8) && d8.Intersects(d));
239
240 QuicInterval<int64_t> i;
241 EXPECT_TRUE(d.Intersects(d, &i) && d == i);
242 EXPECT_TRUE(!empty.Intersects(d, nullptr) && !d.Intersects(empty, nullptr));
243 EXPECT_TRUE(!d.Intersects(d1, nullptr) && !d1.Intersects(d, nullptr));
244 EXPECT_TRUE(d.Intersects(d2, &i) && i == QuicInterval<int64_t>(100, 110));
245 EXPECT_TRUE(d2.Intersects(d, &i) && i == QuicInterval<int64_t>(100, 110));
246 EXPECT_TRUE(d.Intersects(d3, &i) && i == d3);
247 EXPECT_TRUE(d3.Intersects(d, &i) && i == d3);
248 EXPECT_TRUE(d.Intersects(d4, &i) && i == QuicInterval<int64_t>(180, 200));
249 EXPECT_TRUE(d4.Intersects(d, &i) && i == QuicInterval<int64_t>(180, 200));
250 EXPECT_TRUE(!d.Intersects(d5, nullptr) && !d5.Intersects(d, nullptr));
251 EXPECT_TRUE(d.Intersects(d6, &i) && i == d6);
252 EXPECT_TRUE(d6.Intersects(d, &i) && i == d6);
253 EXPECT_TRUE(d.Intersects(d7, &i) && i == d7);
254 EXPECT_TRUE(d7.Intersects(d, &i) && i == d7);
255 EXPECT_TRUE(d.Intersects(d8, &i) && i == d);
256 EXPECT_TRUE(d8.Intersects(d, &i) && i == d);
257
258 // Test IntersectsWith().
259 // Arguments are TestIntersect(i1, i2, changes_i1, changes_i2, result).
260 TestIntersect(empty, d, false, true, empty);
261 TestIntersect(d, d1, true, true, empty);
262 TestIntersect(d1, d2, true, true, empty);
263 TestIntersect(d, d2, true, true, QuicInterval<int64_t>(100, 110));
264 TestIntersect(d8, d, true, false, d);
265 TestIntersect(d8, d1, true, false, d1);
266 TestIntersect(d8, d5, true, false, d5);
267
268 // Contains:
269 EXPECT_TRUE(!empty.Contains(d) && !d.Contains(empty));
270 EXPECT_TRUE(d.Contains(d));
271 EXPECT_TRUE(!d.Contains(d1) && !d1.Contains(d));
272 EXPECT_TRUE(!d.Contains(d2) && !d2.Contains(d));
273 EXPECT_TRUE(d.Contains(d3) && !d3.Contains(d));
274 EXPECT_TRUE(!d.Contains(d4) && !d4.Contains(d));
275 EXPECT_TRUE(!d.Contains(d5) && !d5.Contains(d));
276 EXPECT_TRUE(d.Contains(d6) && !d6.Contains(d));
277 EXPECT_TRUE(d.Contains(d7) && !d7.Contains(d));
278 EXPECT_TRUE(!d.Contains(d8) && d8.Contains(d));
279
280 EXPECT_TRUE(d.Contains(100));
281 EXPECT_TRUE(!d.Contains(200));
282 EXPECT_TRUE(d.Contains(150));
283 EXPECT_TRUE(!d.Contains(99));
284 EXPECT_TRUE(!d.Contains(201));
285
286 // Difference:
287 std::vector<QuicInterval<int64_t>*> diff;
288
289 EXPECT_TRUE(!d.Difference(empty, &diff));
290 EXPECT_EQ(1u, diff.size());
291 EXPECT_EQ(100, diff[0]->min());
292 EXPECT_EQ(200, diff[0]->max());
293 STLDeleteElements(&diff);
294 EXPECT_TRUE(!empty.Difference(d, &diff) && diff.empty());
295
296 EXPECT_TRUE(d.Difference(d, &diff) && diff.empty());
297 EXPECT_TRUE(!d.Difference(d1, &diff));
298 EXPECT_EQ(1u, diff.size());
299 EXPECT_EQ(100, diff[0]->min());
300 EXPECT_EQ(200, diff[0]->max());
301 STLDeleteElements(&diff);
302
303 QuicInterval<int64_t> lo;
304 QuicInterval<int64_t> hi;
305
306 EXPECT_TRUE(d.Difference(d2, &lo, &hi));
307 EXPECT_TRUE(lo.Empty());
308 EXPECT_EQ(110, hi.min());
309 EXPECT_EQ(200, hi.max());
310 EXPECT_TRUE(d.Difference(d2, &diff));
311 EXPECT_EQ(1u, diff.size());
312 EXPECT_EQ(110, diff[0]->min());
313 EXPECT_EQ(200, diff[0]->max());
314 STLDeleteElements(&diff);
315
316 EXPECT_TRUE(d.Difference(d3, &lo, &hi));
317 EXPECT_EQ(100, lo.min());
318 EXPECT_EQ(110, lo.max());
319 EXPECT_EQ(180, hi.min());
320 EXPECT_EQ(200, hi.max());
321 EXPECT_TRUE(d.Difference(d3, &diff));
322 EXPECT_EQ(2u, diff.size());
323 EXPECT_EQ(100, diff[0]->min());
324 EXPECT_EQ(110, diff[0]->max());
325 EXPECT_EQ(180, diff[1]->min());
326 EXPECT_EQ(200, diff[1]->max());
327 STLDeleteElements(&diff);
328
329 EXPECT_TRUE(d.Difference(d4, &lo, &hi));
330 EXPECT_EQ(100, lo.min());
331 EXPECT_EQ(180, lo.max());
332 EXPECT_TRUE(hi.Empty());
333 EXPECT_TRUE(d.Difference(d4, &diff));
334 EXPECT_EQ(1u, diff.size());
335 EXPECT_EQ(100, diff[0]->min());
336 EXPECT_EQ(180, diff[0]->max());
337 STLDeleteElements(&diff);
338
339 EXPECT_FALSE(d.Difference(d5, &lo, &hi));
340 EXPECT_EQ(100, lo.min());
341 EXPECT_EQ(200, lo.max());
342 EXPECT_TRUE(hi.Empty());
343 EXPECT_FALSE(d.Difference(d5, &diff));
344 EXPECT_EQ(1u, diff.size());
345 EXPECT_EQ(100, diff[0]->min());
346 EXPECT_EQ(200, diff[0]->max());
347 STLDeleteElements(&diff);
348
349 EXPECT_TRUE(d.Difference(d6, &lo, &hi));
350 EXPECT_TRUE(lo.Empty());
351 EXPECT_EQ(150, hi.min());
352 EXPECT_EQ(200, hi.max());
353 EXPECT_TRUE(d.Difference(d6, &diff));
354 EXPECT_EQ(1u, diff.size());
355 EXPECT_EQ(150, diff[0]->min());
356 EXPECT_EQ(200, diff[0]->max());
357 STLDeleteElements(&diff);
358
359 EXPECT_TRUE(d.Difference(d7, &lo, &hi));
360 EXPECT_EQ(100, lo.min());
361 EXPECT_EQ(150, lo.max());
362 EXPECT_TRUE(hi.Empty());
363 EXPECT_TRUE(d.Difference(d7, &diff));
364 EXPECT_EQ(1u, diff.size());
365 EXPECT_EQ(100, diff[0]->min());
366 EXPECT_EQ(150, diff[0]->max());
367 STLDeleteElements(&diff);
368
369 EXPECT_TRUE(d.Difference(d8, &lo, &hi));
370 EXPECT_TRUE(lo.Empty());
371 EXPECT_TRUE(hi.Empty());
372 EXPECT_TRUE(d.Difference(d8, &diff) && diff.empty());
373 }
374
TEST_F(QuicIntervalTest,Separated)375 TEST_F(QuicIntervalTest, Separated) {
376 using QI = QuicInterval<int>;
377 EXPECT_FALSE(QI(100, 200).Separated(QI(100, 200)));
378 EXPECT_FALSE(QI(100, 200).Separated(QI(200, 300)));
379 EXPECT_TRUE(QI(100, 200).Separated(QI(201, 300)));
380 EXPECT_FALSE(QI(100, 200).Separated(QI(0, 100)));
381 EXPECT_TRUE(QI(100, 200).Separated(QI(0, 99)));
382 EXPECT_FALSE(QI(100, 200).Separated(QI(150, 170)));
383 EXPECT_FALSE(QI(150, 170).Separated(QI(100, 200)));
384 EXPECT_FALSE(QI(100, 200).Separated(QI(150, 250)));
385 EXPECT_FALSE(QI(150, 250).Separated(QI(100, 200)));
386 }
387
TEST_F(QuicIntervalTest,Length)388 TEST_F(QuicIntervalTest, Length) {
389 const QuicInterval<int> empty1;
390 const QuicInterval<int> empty2(1, 1);
391 const QuicInterval<int> empty3(1, 0);
392 const QuicInterval<QuicTime> empty4(
393 QuicTime::Zero() + QuicTime::Delta::FromSeconds(1), QuicTime::Zero());
394 const QuicInterval<int> d1(1, 2);
395 const QuicInterval<int> d2(0, 50);
396 const QuicInterval<QuicTime> d3(
397 QuicTime::Zero(), QuicTime::Zero() + QuicTime::Delta::FromSeconds(1));
398 const QuicInterval<QuicTime> d4(
399 QuicTime::Zero() + QuicTime::Delta::FromSeconds(3600),
400 QuicTime::Zero() + QuicTime::Delta::FromSeconds(5400));
401
402 EXPECT_EQ(0, empty1.Length());
403 EXPECT_EQ(0, empty2.Length());
404 EXPECT_EQ(0, empty3.Length());
405 EXPECT_EQ(QuicTime::Delta::Zero(), empty4.Length());
406 EXPECT_EQ(1, d1.Length());
407 EXPECT_EQ(50, d2.Length());
408 EXPECT_EQ(QuicTime::Delta::FromSeconds(1), d3.Length());
409 EXPECT_EQ(QuicTime::Delta::FromSeconds(1800), d4.Length());
410 }
411
TEST_F(QuicIntervalTest,IntervalOfTypeWithNoOperatorMinus)412 TEST_F(QuicIntervalTest, IntervalOfTypeWithNoOperatorMinus) {
413 // QuicInterval<T> should work even if T does not support operator-(). We
414 // just can't call QuicInterval<T>::Length() for such types.
415 const QuicInterval<std::string> d1("a", "b");
416 const QuicInterval<std::pair<int, int>> d2({1, 2}, {4, 3});
417 EXPECT_EQ("a", d1.min());
418 EXPECT_EQ("b", d1.max());
419 EXPECT_EQ(std::make_pair(1, 2), d2.min());
420 EXPECT_EQ(std::make_pair(4, 3), d2.max());
421 }
422
423 struct NoEquals {
NoEqualsquic::test::__anonfdd075650111::NoEquals424 NoEquals(int v) : value(v) {} // NOLINT
425 int value;
operator <quic::test::__anonfdd075650111::NoEquals426 bool operator<(const NoEquals& other) const { return value < other.value; }
427 };
428
TEST_F(QuicIntervalTest,OrderedComparisonForTypeWithoutEquals)429 TEST_F(QuicIntervalTest, OrderedComparisonForTypeWithoutEquals) {
430 const QuicInterval<NoEquals> d1(0, 4);
431 const QuicInterval<NoEquals> d2(0, 3);
432 const QuicInterval<NoEquals> d3(1, 4);
433 const QuicInterval<NoEquals> d4(1, 5);
434 const QuicInterval<NoEquals> d6(0, 4);
435 EXPECT_TRUE(d1 < d2);
436 EXPECT_TRUE(d1 < d3);
437 EXPECT_TRUE(d1 < d4);
438 EXPECT_FALSE(d1 < d6);
439 }
440
TEST_F(QuicIntervalTest,OutputReturnsOstreamRef)441 TEST_F(QuicIntervalTest, OutputReturnsOstreamRef) {
442 std::stringstream ss;
443 const QuicInterval<int> v(1, 2);
444 // If (ss << v) were to return a value, it wouldn't match the signature of
445 // return_type_is_a_ref() function.
446 auto return_type_is_a_ref = [](std::ostream&) {};
447 return_type_is_a_ref(ss << v);
448 }
449
450 struct NotOstreamable {
operator <quic::test::__anonfdd075650111::NotOstreamable451 bool operator<(const NotOstreamable&) const { return false; }
operator >=quic::test::__anonfdd075650111::NotOstreamable452 bool operator>=(const NotOstreamable&) const { return true; }
operator ==quic::test::__anonfdd075650111::NotOstreamable453 bool operator==(const NotOstreamable&) const { return true; }
454 };
455
TEST_F(QuicIntervalTest,IntervalOfTypeWithNoOstreamSupport)456 TEST_F(QuicIntervalTest, IntervalOfTypeWithNoOstreamSupport) {
457 const NotOstreamable v;
458 const QuicInterval<NotOstreamable> d(v, v);
459 // EXPECT_EQ builds a string representation of d. If d::operator<<() would be
460 // defined then this test would not compile because NotOstreamable objects
461 // lack the operator<<() support.
462 EXPECT_EQ(d, d);
463 }
464
465 } // namespace
466 } // namespace test
467 } // namespace quic
468