1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
2 /* This Source Code Form is subject to the terms of the Mozilla Public
3 * License, v. 2.0. If a copy of the MPL was not distributed with this
4 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
5
6 #include <stdio.h>
7 #include <stdlib.h>
8
9 #include <set>
10
11 #include "ChunkSet.h"
12 #include "mozilla/ArrayUtils.h"
13
14 #include "Common.h"
15
TEST(UrlClassifierChunkSet,Empty)16 TEST(UrlClassifierChunkSet, Empty)
17 {
18 mozilla::safebrowsing::ChunkSet chunkSet;
19 mozilla::safebrowsing::ChunkSet removeSet;
20
21 removeSet.Set(0);
22
23 ASSERT_FALSE(chunkSet.Has(0));
24 ASSERT_FALSE(chunkSet.Has(1));
25 ASSERT_TRUE(chunkSet.Remove(removeSet) == NS_OK);
26 ASSERT_TRUE(chunkSet.Length() == 0);
27
28 chunkSet.Set(0);
29
30 ASSERT_TRUE(chunkSet.Has(0));
31 ASSERT_TRUE(chunkSet.Length() == 1);
32 ASSERT_TRUE(chunkSet.Remove(removeSet) == NS_OK);
33 ASSERT_FALSE(chunkSet.Has(0));
34 ASSERT_TRUE(chunkSet.Length() == 0);
35 }
36
TEST(UrlClassifierChunkSet,Main)37 TEST(UrlClassifierChunkSet, Main)
38 {
39 static int testVals[] = {2, 1, 5, 6, 8, 7, 14, 10, 12, 13};
40
41 mozilla::safebrowsing::ChunkSet chunkSet;
42
43 for (size_t i = 0; i < MOZ_ARRAY_LENGTH(testVals); i++) {
44 chunkSet.Set(testVals[i]);
45 }
46
47 for (size_t i = 0; i < MOZ_ARRAY_LENGTH(testVals); i++) {
48 ASSERT_TRUE(chunkSet.Has(testVals[i]));
49 }
50
51 ASSERT_FALSE(chunkSet.Has(3));
52 ASSERT_FALSE(chunkSet.Has(4));
53 ASSERT_FALSE(chunkSet.Has(9));
54 ASSERT_FALSE(chunkSet.Has(11));
55
56 ASSERT_TRUE(chunkSet.Length() == MOZ_ARRAY_LENGTH(testVals));
57 }
58
TEST(UrlClassifierChunkSet,Merge)59 TEST(UrlClassifierChunkSet, Merge)
60 {
61 static int testVals[] = {2, 1, 5, 6, 8, 7, 14, 10, 12, 13};
62 static int mergeVals[] = {9, 3, 4, 20, 14, 16};
63
64 mozilla::safebrowsing::ChunkSet chunkSet;
65 mozilla::safebrowsing::ChunkSet mergeSet;
66
67 for (size_t i = 0; i < MOZ_ARRAY_LENGTH(testVals); i++) {
68 chunkSet.Set(testVals[i]);
69 }
70
71 for (size_t i = 0; i < MOZ_ARRAY_LENGTH(mergeVals); i++) {
72 mergeSet.Set(mergeVals[i]);
73 }
74
75 chunkSet.Merge(mergeSet);
76
77 for (size_t i = 0; i < MOZ_ARRAY_LENGTH(testVals); i++) {
78 ASSERT_TRUE(chunkSet.Has(testVals[i]));
79 }
80 for (size_t i = 0; i < MOZ_ARRAY_LENGTH(mergeVals); i++) {
81 ASSERT_TRUE(chunkSet.Has(mergeVals[i]));
82 }
83
84 // -1 because 14 is duplicated in both sets
85 ASSERT_TRUE(chunkSet.Length() ==
86 MOZ_ARRAY_LENGTH(testVals) + MOZ_ARRAY_LENGTH(mergeVals) - 1);
87
88 ASSERT_FALSE(chunkSet.Has(11));
89 ASSERT_FALSE(chunkSet.Has(15));
90 ASSERT_FALSE(chunkSet.Has(17));
91 ASSERT_FALSE(chunkSet.Has(18));
92 ASSERT_FALSE(chunkSet.Has(19));
93 }
94
TEST(UrlClassifierChunkSet,Merge2)95 TEST(UrlClassifierChunkSet, Merge2)
96 {
97 static int testVals[] = {2, 1, 5, 6, 8, 7, 14, 10, 12, 13};
98 static int mergeVals[] = {9, 3, 4, 20, 14, 16};
99 static int mergeVals2[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11};
100
101 mozilla::safebrowsing::ChunkSet chunkSet;
102 mozilla::safebrowsing::ChunkSet mergeSet;
103 mozilla::safebrowsing::ChunkSet mergeSet2;
104
105 for (size_t i = 0; i < MOZ_ARRAY_LENGTH(testVals); i++) {
106 chunkSet.Set(testVals[i]);
107 }
108
109 for (size_t i = 0; i < MOZ_ARRAY_LENGTH(mergeVals); i++) {
110 mergeSet.Set(mergeVals[i]);
111 }
112 for (size_t i = 0; i < MOZ_ARRAY_LENGTH(mergeVals2); i++) {
113 mergeSet2.Set(mergeVals2[i]);
114 }
115
116 chunkSet.Merge(mergeSet);
117 chunkSet.Merge(mergeSet2);
118
119 for (size_t i = 0; i < MOZ_ARRAY_LENGTH(testVals); i++) {
120 ASSERT_TRUE(chunkSet.Has(testVals[i]));
121 }
122 for (size_t i = 0; i < MOZ_ARRAY_LENGTH(mergeVals); i++) {
123 ASSERT_TRUE(chunkSet.Has(mergeVals[i]));
124 }
125 for (size_t i = 0; i < MOZ_ARRAY_LENGTH(mergeVals2); i++) {
126 ASSERT_TRUE(chunkSet.Has(mergeVals2[i]));
127 }
128
129 ASSERT_FALSE(chunkSet.Has(15));
130 ASSERT_FALSE(chunkSet.Has(17));
131 ASSERT_FALSE(chunkSet.Has(18));
132 ASSERT_FALSE(chunkSet.Has(19));
133 }
134
TEST(UrlClassifierChunkSet,Stress)135 TEST(UrlClassifierChunkSet, Stress)
136 {
137 mozilla::safebrowsing::ChunkSet chunkSet;
138 mozilla::safebrowsing::ChunkSet mergeSet;
139 std::set<int> refSet;
140 std::set<int> refMergeSet;
141 static const int TEST_ITERS = 7000;
142 static const int REMOVE_ITERS = 3000;
143 static const int TEST_RANGE = 10000;
144
145 // Construction by Set
146 for (int i = 0; i < TEST_ITERS; i++) {
147 int chunk = rand() % TEST_RANGE;
148 chunkSet.Set(chunk);
149 refSet.insert(chunk);
150 }
151
152 // Same elements as reference set
153 for (auto it = refSet.begin(); it != refSet.end(); ++it) {
154 ASSERT_TRUE(chunkSet.Has(*it));
155 }
156
157 // Hole punching via Remove
158 for (int i = 0; i < REMOVE_ITERS; i++) {
159 int chunk = rand() % TEST_RANGE;
160 mozilla::safebrowsing::ChunkSet helpChunk;
161 helpChunk.Set(chunk);
162
163 chunkSet.Remove(helpChunk);
164 refSet.erase(chunk);
165
166 ASSERT_FALSE(chunkSet.Has(chunk));
167 }
168
169 // Should have chunks present in reference set
170 // Should not have chunks absent in reference set
171 for (int it = 0; it < TEST_RANGE; ++it) {
172 auto found = refSet.find(it);
173 if (chunkSet.Has(it)) {
174 ASSERT_FALSE(found == refSet.end());
175 } else {
176 ASSERT_TRUE(found == refSet.end());
177 }
178 }
179
180 // Construct set to merge with
181 for (int i = 0; i < TEST_ITERS; i++) {
182 int chunk = rand() % TEST_RANGE;
183 mergeSet.Set(chunk);
184 refMergeSet.insert(chunk);
185 }
186
187 // Merge set constructed correctly
188 for (auto it = refMergeSet.begin(); it != refMergeSet.end(); ++it) {
189 ASSERT_TRUE(mergeSet.Has(*it));
190 }
191
192 mozilla::safebrowsing::ChunkSet origSet;
193 origSet = chunkSet.InfallibleClone();
194
195 chunkSet.Merge(mergeSet);
196 refSet.insert(refMergeSet.begin(), refMergeSet.end());
197
198 // Check for presence of elements from both source
199 // Should not have chunks absent in reference set
200 for (int it = 0; it < TEST_RANGE; ++it) {
201 auto found = refSet.find(it);
202 if (chunkSet.Has(it)) {
203 ASSERT_FALSE(found == refSet.end());
204 } else {
205 ASSERT_TRUE(found == refSet.end());
206 }
207 }
208
209 // Unmerge
210 chunkSet.Remove(origSet);
211 for (int it = 0; it < TEST_RANGE; ++it) {
212 if (origSet.Has(it)) {
213 ASSERT_FALSE(chunkSet.Has(it));
214 } else if (mergeSet.Has(it)) {
215 ASSERT_TRUE(chunkSet.Has(it));
216 }
217 }
218 }
219
TEST(UrlClassifierChunkSet,RemoveClear)220 TEST(UrlClassifierChunkSet, RemoveClear)
221 {
222 static int testVals[] = {2, 1, 5, 6, 8, 7, 14, 10, 12, 13};
223 static int mergeVals[] = {3, 4, 9, 16, 20};
224
225 mozilla::safebrowsing::ChunkSet chunkSet;
226 mozilla::safebrowsing::ChunkSet mergeSet;
227 mozilla::safebrowsing::ChunkSet removeSet;
228
229 for (size_t i = 0; i < MOZ_ARRAY_LENGTH(testVals); i++) {
230 chunkSet.Set(testVals[i]);
231 removeSet.Set(testVals[i]);
232 }
233
234 for (size_t i = 0; i < MOZ_ARRAY_LENGTH(mergeVals); i++) {
235 mergeSet.Set(mergeVals[i]);
236 }
237
238 ASSERT_TRUE(chunkSet.Merge(mergeSet) == NS_OK);
239 ASSERT_TRUE(chunkSet.Remove(removeSet) == NS_OK);
240
241 for (size_t i = 0; i < MOZ_ARRAY_LENGTH(mergeVals); i++) {
242 ASSERT_TRUE(chunkSet.Has(mergeVals[i]));
243 }
244 for (size_t i = 0; i < MOZ_ARRAY_LENGTH(testVals); i++) {
245 ASSERT_FALSE(chunkSet.Has(testVals[i]));
246 }
247
248 chunkSet.Clear();
249
250 for (size_t i = 0; i < MOZ_ARRAY_LENGTH(mergeVals); i++) {
251 ASSERT_FALSE(chunkSet.Has(mergeVals[i]));
252 }
253 }
254
TEST(UrlClassifierChunkSet,Serialize)255 TEST(UrlClassifierChunkSet, Serialize)
256 {
257 static int testVals[] = {2, 1, 5, 6, 8, 7, 14, 10, 12, 13};
258 static int mergeVals[] = {3, 4, 9, 16, 20};
259
260 mozilla::safebrowsing::ChunkSet chunkSet;
261 mozilla::safebrowsing::ChunkSet mergeSet;
262
263 for (size_t i = 0; i < MOZ_ARRAY_LENGTH(testVals); i++) {
264 chunkSet.Set(testVals[i]);
265 }
266
267 for (size_t i = 0; i < MOZ_ARRAY_LENGTH(mergeVals); i++) {
268 mergeSet.Set(mergeVals[i]);
269 }
270
271 chunkSet.Merge(mergeSet);
272
273 nsAutoCString mergeResult;
274 chunkSet.Serialize(mergeResult);
275
276 printf("mergeResult: %s\n", mergeResult.get());
277
278 nsAutoCString expected(NS_LITERAL_CSTRING("1-10,12-14,16,20"));
279
280 ASSERT_TRUE(mergeResult.Equals(expected));
281 }
282