1 /*
2 * Copyright 2018 The WebRTC project authors. All Rights Reserved.
3 *
4 * Use of this source code is governed by a BSD-style license
5 * that can be found in the LICENSE file in the root of the source
6 * tree. An additional intellectual property rights grant can be found
7 * in the file PATENTS. All contributing project authors may
8 * be found in the AUTHORS file in the root of the source tree.
9 */
10
11 #include "rtc_base/unique_id_generator.h"
12
13 #include <string>
14 #include <vector>
15
16 #include "absl/algorithm/container.h"
17 #include "absl/functional/any_invocable.h"
18 #include "api/array_view.h"
19 #include "api/task_queue/task_queue_base.h"
20 #include "api/units/time_delta.h"
21 #include "rtc_base/gunit.h"
22 #include "rtc_base/helpers.h"
23 #include "test/gmock.h"
24
25 using ::testing::IsEmpty;
26 using ::testing::Test;
27
28 namespace rtc {
29 namespace {
30 // Utility class that registers itself as the currently active task queue.
31 class FakeTaskQueue : public webrtc::TaskQueueBase {
32 public:
FakeTaskQueue()33 FakeTaskQueue() : task_queue_setter_(this) {}
34
Delete()35 void Delete() override {}
PostTask(absl::AnyInvocable<void ()&&> task)36 void PostTask(absl::AnyInvocable<void() &&> task) override {}
PostDelayedTask(absl::AnyInvocable<void ()&&> task,webrtc::TimeDelta delay)37 void PostDelayedTask(absl::AnyInvocable<void() &&> task,
38 webrtc::TimeDelta delay) override {}
PostDelayedHighPrecisionTask(absl::AnyInvocable<void ()&&> task,webrtc::TimeDelta delay)39 void PostDelayedHighPrecisionTask(absl::AnyInvocable<void() &&> task,
40 webrtc::TimeDelta delay) override {}
41
42 private:
43 CurrentTaskQueueSetter task_queue_setter_;
44 };
45 } // namespace
46
47 template <typename Generator>
48 class UniqueIdGeneratorTest : public Test {};
49
50 using test_types = ::testing::Types<UniqueNumberGenerator<uint8_t>,
51 UniqueNumberGenerator<uint16_t>,
52 UniqueNumberGenerator<uint32_t>,
53 UniqueNumberGenerator<int>,
54 UniqueRandomIdGenerator,
55 UniqueStringGenerator>;
56
57 TYPED_TEST_SUITE(UniqueIdGeneratorTest, test_types);
58
TYPED_TEST(UniqueIdGeneratorTest,ElementsDoNotRepeat)59 TYPED_TEST(UniqueIdGeneratorTest, ElementsDoNotRepeat) {
60 typedef TypeParam Generator;
61 const size_t num_elements = 255;
62 Generator generator;
63 std::vector<typename Generator::value_type> values;
64 for (size_t i = 0; i < num_elements; i++) {
65 values.push_back(generator());
66 }
67
68 EXPECT_EQ(num_elements, values.size());
69 // Use a set to check uniqueness.
70 std::set<typename Generator::value_type> set(values.begin(), values.end());
71 EXPECT_EQ(values.size(), set.size()) << "Returned values were not unique.";
72 }
73
TYPED_TEST(UniqueIdGeneratorTest,KnownElementsAreNotGenerated)74 TYPED_TEST(UniqueIdGeneratorTest, KnownElementsAreNotGenerated) {
75 typedef TypeParam Generator;
76 const size_t num_elements = 100;
77 rtc::InitRandom(0);
78 Generator generator1;
79 std::vector<typename Generator::value_type> known_values;
80 for (size_t i = 0; i < num_elements; i++) {
81 known_values.push_back(generator1());
82 }
83 EXPECT_EQ(num_elements, known_values.size());
84
85 rtc::InitRandom(0);
86 Generator generator2(known_values);
87
88 std::vector<typename Generator::value_type> values;
89 for (size_t i = 0; i < num_elements; i++) {
90 values.push_back(generator2());
91 }
92 EXPECT_THAT(values, ::testing::SizeIs(num_elements));
93 absl::c_sort(values);
94 absl::c_sort(known_values);
95 std::vector<typename Generator::value_type> intersection;
96 absl::c_set_intersection(values, known_values,
97 std::back_inserter(intersection));
98 EXPECT_THAT(intersection, IsEmpty());
99 }
100
TYPED_TEST(UniqueIdGeneratorTest,AddedElementsAreNotGenerated)101 TYPED_TEST(UniqueIdGeneratorTest, AddedElementsAreNotGenerated) {
102 typedef TypeParam Generator;
103 const size_t num_elements = 100;
104 rtc::InitRandom(0);
105 Generator generator1;
106 std::vector<typename Generator::value_type> known_values;
107 for (size_t i = 0; i < num_elements; i++) {
108 known_values.push_back(generator1());
109 }
110 EXPECT_EQ(num_elements, known_values.size());
111
112 rtc::InitRandom(0);
113 Generator generator2;
114
115 for (const typename Generator::value_type& value : known_values) {
116 generator2.AddKnownId(value);
117 }
118
119 std::vector<typename Generator::value_type> values;
120 for (size_t i = 0; i < num_elements; i++) {
121 values.push_back(generator2());
122 }
123 EXPECT_THAT(values, ::testing::SizeIs(num_elements));
124 absl::c_sort(values);
125 absl::c_sort(known_values);
126 std::vector<typename Generator::value_type> intersection;
127 absl::c_set_intersection(values, known_values,
128 std::back_inserter(intersection));
129 EXPECT_THAT(intersection, IsEmpty());
130 }
131
TYPED_TEST(UniqueIdGeneratorTest,AddKnownIdOnNewIdReturnsTrue)132 TYPED_TEST(UniqueIdGeneratorTest, AddKnownIdOnNewIdReturnsTrue) {
133 typedef TypeParam Generator;
134
135 rtc::InitRandom(0);
136 Generator generator1;
137 const typename Generator::value_type id = generator1();
138
139 rtc::InitRandom(0);
140 Generator generator2;
141 EXPECT_TRUE(generator2.AddKnownId(id));
142 }
143
TYPED_TEST(UniqueIdGeneratorTest,AddKnownIdCalledAgainForSameIdReturnsFalse)144 TYPED_TEST(UniqueIdGeneratorTest, AddKnownIdCalledAgainForSameIdReturnsFalse) {
145 typedef TypeParam Generator;
146
147 rtc::InitRandom(0);
148 Generator generator1;
149 const typename Generator::value_type id = generator1();
150
151 rtc::InitRandom(0);
152 Generator generator2;
153 ASSERT_TRUE(generator2.AddKnownId(id));
154 EXPECT_FALSE(generator2.AddKnownId(id));
155 }
156
TYPED_TEST(UniqueIdGeneratorTest,AddKnownIdOnIdProvidedAsKnownToCtorReturnsFalse)157 TYPED_TEST(UniqueIdGeneratorTest,
158 AddKnownIdOnIdProvidedAsKnownToCtorReturnsFalse) {
159 typedef TypeParam Generator;
160
161 rtc::InitRandom(0);
162 Generator generator1;
163 const typename Generator::value_type id = generator1();
164 std::vector<typename Generator::value_type> known_values = {id};
165
166 rtc::InitRandom(0);
167 Generator generator2(known_values);
168 EXPECT_FALSE(generator2.AddKnownId(id));
169 }
170
171 // Tests that it's OK to construct the generator in one execution environment
172 // (thread/task queue) but use it in another.
TEST(UniqueNumberGenerator,UsedOnSecondaryThread)173 TEST(UniqueNumberGenerator, UsedOnSecondaryThread) {
174 const auto* current_tq = webrtc::TaskQueueBase::Current();
175 // Construct the generator before `fake_task_queue` to ensure that it is
176 // constructed in a different execution environment than what
177 // `fake_task_queue` will represent.
178 UniqueNumberGenerator<uint32_t> generator;
179
180 FakeTaskQueue fake_task_queue;
181 // Sanity check to make sure we're in a different runtime environment.
182 ASSERT_NE(current_tq, webrtc::TaskQueueBase::Current());
183
184 // Generating an id should be fine in this context.
185 generator.GenerateNumber();
186 }
187
188 #if RTC_DCHECK_IS_ON && GTEST_HAS_DEATH_TEST && !defined(WEBRTC_ANDROID)
TEST(UniqueNumberGeneratorDeathTest,FailsWhenUsedInWrongContext)189 TEST(UniqueNumberGeneratorDeathTest, FailsWhenUsedInWrongContext) {
190 // Instantiate the generator before the `loop`. This ensures that
191 // thread/sequence checkers will pick up a different thread environment than
192 // `fake_task_queue` will represent.
193 UniqueNumberGenerator<uint32_t> generator;
194
195 // Instantiate a fake task queue that will register itself as the current tq.
196 FakeTaskQueue initial_fake_task_queue;
197 // Generate an ID on the current thread. This causes the generator to attach
198 // to the current thread context.
199 generator.GenerateNumber();
200
201 // Instantiate a fake task queue that will register itself as the current tq.
202 FakeTaskQueue fake_task_queue;
203
204 // Attempting to generate an id should now trigger a dcheck.
205 EXPECT_DEATH(generator.GenerateNumber(), "");
206 }
207 #endif
208
209 } // namespace rtc
210