1 /*
2 * Copyright (C) 2023 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16 #include "src/trace_processor/db/column/set_id_storage.h"
17
18 #include <cstdint>
19 #include <limits>
20 #include <tuple>
21 #include <vector>
22
23 #include "perfetto/trace_processor/basic_types.h"
24 #include "src/trace_processor/containers/bit_vector.h"
25 #include "src/trace_processor/db/column/data_layer.h"
26 #include "src/trace_processor/db/column/numeric_storage.h"
27 #include "src/trace_processor/db/column/types.h"
28 #include "src/trace_processor/db/column/utils.h"
29 #include "test/gtest_and_gmock.h"
30
31 namespace perfetto::trace_processor {
32
operator ==(const Range & a,const Range & b)33 inline bool operator==(const Range& a, const Range& b) {
34 return std::tie(a.start, a.end) == std::tie(b.start, b.end);
35 }
36
operator ==(const BitVector & a,const BitVector & b)37 inline bool operator==(const BitVector& a, const BitVector& b) {
38 return a.size() == b.size() && a.CountSetBits() == b.CountSetBits();
39 }
40
41 namespace column {
42 namespace {
43
44 using testing::ElementsAre;
45 using testing::IsEmpty;
46
47 using Indices = DataLayerChain::Indices;
48 using OrderedIndices = DataLayerChain::OrderedIndices;
49
TEST(SetIdStorage,SearchSingle)50 TEST(SetIdStorage, SearchSingle) {
51 std::vector<uint32_t> storage_data{0, 0, 2, 2, 4, 4, 6, 6};
52 SetIdStorage storage(&storage_data);
53 auto chain = storage.MakeChain();
54
55 ASSERT_EQ(chain->SingleSearch(FilterOp::kEq, SqlValue::Long(4), 4),
56 SingleSearchResult::kMatch);
57 ASSERT_EQ(chain->SingleSearch(FilterOp::kEq, SqlValue::Long(4), 3),
58 SingleSearchResult::kNoMatch);
59
60 ASSERT_EQ(chain->SingleSearch(FilterOp::kNe, SqlValue::Long(4), 3),
61 SingleSearchResult::kMatch);
62 ASSERT_EQ(chain->SingleSearch(FilterOp::kNe, SqlValue::Long(4), 4),
63 SingleSearchResult::kNoMatch);
64
65 ASSERT_EQ(chain->SingleSearch(FilterOp::kGe, SqlValue::Long(4), 4),
66 SingleSearchResult::kMatch);
67 ASSERT_EQ(chain->SingleSearch(FilterOp::kGe, SqlValue::Long(4), 1),
68 SingleSearchResult::kNoMatch);
69
70 ASSERT_EQ(chain->SingleSearch(FilterOp::kGt, SqlValue::Long(4), 6),
71 SingleSearchResult::kMatch);
72 ASSERT_EQ(chain->SingleSearch(FilterOp::kGt, SqlValue::Long(4), 4),
73 SingleSearchResult::kNoMatch);
74
75 ASSERT_EQ(chain->SingleSearch(FilterOp::kLe, SqlValue::Long(4), 4),
76 SingleSearchResult::kMatch);
77 ASSERT_EQ(chain->SingleSearch(FilterOp::kLe, SqlValue::Long(4), 6),
78 SingleSearchResult::kNoMatch);
79
80 ASSERT_EQ(chain->SingleSearch(FilterOp::kLt, SqlValue::Long(4), 3),
81 SingleSearchResult::kMatch);
82 ASSERT_EQ(chain->SingleSearch(FilterOp::kLt, SqlValue::Long(4), 4),
83 SingleSearchResult::kNoMatch);
84 }
85
TEST(SetIdStorage,InvalidSearchConstraints)86 TEST(SetIdStorage, InvalidSearchConstraints) {
87 std::vector<uint32_t> storage_data{0, 0, 0, 3, 3, 3, 6, 6, 6, 9, 9, 9};
88 SetIdStorage storage(&storage_data);
89 auto chain = storage.MakeChain();
90
91 // NULL checks
92 ASSERT_EQ(chain->ValidateSearchConstraints(FilterOp::kIsNull, SqlValue()),
93 SearchValidationResult::kNoData);
94 ASSERT_EQ(chain->ValidateSearchConstraints(FilterOp::kIsNotNull, SqlValue()),
95 SearchValidationResult::kAllData);
96
97 // FilterOp checks
98 ASSERT_EQ(
99 chain->ValidateSearchConstraints(FilterOp::kGlob, SqlValue::Long(15)),
100 SearchValidationResult::kNoData);
101 ASSERT_EQ(
102 chain->ValidateSearchConstraints(FilterOp::kRegex, SqlValue::Long(15)),
103 SearchValidationResult::kNoData);
104
105 // Type checks
106 ASSERT_EQ(chain->ValidateSearchConstraints(FilterOp::kGe,
107 SqlValue::String("cheese")),
108 SearchValidationResult::kNoData);
109
110 // Value bounds
111 SqlValue max_val = SqlValue::Long(
112 static_cast<int64_t>(std::numeric_limits<uint32_t>::max()) + 10);
113 ASSERT_EQ(chain->ValidateSearchConstraints(FilterOp::kGe, max_val),
114 SearchValidationResult::kNoData);
115 ASSERT_EQ(chain->ValidateSearchConstraints(FilterOp::kGt, max_val),
116 SearchValidationResult::kNoData);
117 ASSERT_EQ(chain->ValidateSearchConstraints(FilterOp::kEq, max_val),
118 SearchValidationResult::kNoData);
119
120 ASSERT_EQ(chain->ValidateSearchConstraints(FilterOp::kLe, max_val),
121 SearchValidationResult::kAllData);
122 ASSERT_EQ(chain->ValidateSearchConstraints(FilterOp::kLt, max_val),
123 SearchValidationResult::kAllData);
124 ASSERT_EQ(chain->ValidateSearchConstraints(FilterOp::kNe, max_val),
125 SearchValidationResult::kAllData);
126
127 SqlValue min_val = SqlValue::Long(
128 static_cast<int64_t>(std::numeric_limits<uint32_t>::min()) - 1);
129 ASSERT_EQ(chain->ValidateSearchConstraints(FilterOp::kGe, min_val),
130 SearchValidationResult::kAllData);
131 ASSERT_EQ(chain->ValidateSearchConstraints(FilterOp::kGt, min_val),
132 SearchValidationResult::kAllData);
133 ASSERT_EQ(chain->ValidateSearchConstraints(FilterOp::kNe, min_val),
134 SearchValidationResult::kAllData);
135
136 ASSERT_EQ(chain->ValidateSearchConstraints(FilterOp::kLe, min_val),
137 SearchValidationResult::kNoData);
138 ASSERT_EQ(chain->ValidateSearchConstraints(FilterOp::kLt, min_val),
139 SearchValidationResult::kNoData);
140 ASSERT_EQ(chain->ValidateSearchConstraints(FilterOp::kEq, min_val),
141 SearchValidationResult::kNoData);
142 }
143
TEST(SetIdStorage,SearchSimple)144 TEST(SetIdStorage, SearchSimple) {
145 std::vector<uint32_t> storage_data{0, 0, 2, 2, 4, 4, 6, 6};
146 SetIdStorage storage(&storage_data);
147 auto chain = storage.MakeChain();
148 SqlValue val = SqlValue::Long(4);
149 Range filter_range(1, 7);
150
151 FilterOp op = FilterOp::kEq;
152 auto res = chain->Search(op, val, filter_range);
153 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(4, 5));
154
155 op = FilterOp::kNe;
156 res = chain->Search(op, val, filter_range);
157 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(1, 2, 3, 6));
158
159 op = FilterOp::kLe;
160 res = chain->Search(op, val, filter_range);
161 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(1, 2, 3, 4, 5));
162
163 op = FilterOp::kLt;
164 res = chain->Search(op, val, filter_range);
165 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(1, 2, 3));
166
167 op = FilterOp::kGe;
168 res = chain->Search(op, val, filter_range);
169 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(4, 5, 6));
170
171 op = FilterOp::kGt;
172 res = chain->Search(op, val, filter_range);
173 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(6));
174 }
175
TEST(SetIdStorage,IndexSearchSimple)176 TEST(SetIdStorage, IndexSearchSimple) {
177 std::vector<uint32_t> storage_data{0, 0, 2, 2, 4, 4, 6, 6};
178 SetIdStorage storage(&storage_data);
179 auto chain = storage.MakeChain();
180 SqlValue val = SqlValue::Long(4);
181 // 6, 4, 2, 0
182 auto common_indices = Indices::CreateWithIndexPayloadForTesting(
183 {6, 4, 2, 0}, Indices::State::kNonmonotonic);
184
185 auto indices = common_indices;
186 chain->IndexSearch(FilterOp::kEq, val, indices);
187 ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(1));
188
189 indices = common_indices;
190 chain->IndexSearch(FilterOp::kNe, val, indices);
191 ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(0, 2, 3));
192
193 indices = common_indices;
194 chain->IndexSearch(FilterOp::kLe, val, indices);
195 ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(1, 2, 3));
196
197 indices = common_indices;
198 chain->IndexSearch(FilterOp::kLt, val, indices);
199 ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(2, 3));
200
201 indices = common_indices;
202 chain->IndexSearch(FilterOp::kGe, val, indices);
203 ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(0, 1));
204
205 indices = common_indices;
206 chain->IndexSearch(FilterOp::kGt, val, indices);
207 ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(0));
208 }
209
TEST(SetIdStorage,OrderedIndexSearchSimple)210 TEST(SetIdStorage, OrderedIndexSearchSimple) {
211 std::vector<uint32_t> storage_data{0, 0, 2, 2, 4, 4, 6, 6};
212 SetIdStorage storage(&storage_data);
213 auto chain = storage.MakeChain();
214
215 // 0, 2, 2, 4
216 std::vector<uint32_t> indices_vec{0, 3, 3, 5};
217 OrderedIndices indices{indices_vec.data(), 4, Indices::State::kMonotonic};
218
219 Range range =
220 chain->OrderedIndexSearch(FilterOp::kEq, SqlValue::Long(2), indices);
221 ASSERT_EQ(range.start, 1u);
222 ASSERT_EQ(range.end, 3u);
223
224 range = chain->OrderedIndexSearch(FilterOp::kGt, SqlValue::Long(2), indices);
225 ASSERT_EQ(range.start, 3u);
226 ASSERT_EQ(range.end, 4u);
227
228 range = chain->OrderedIndexSearch(FilterOp::kGe, SqlValue::Long(2), indices);
229 ASSERT_EQ(range.start, 1u);
230 ASSERT_EQ(range.end, 4u);
231
232 range = chain->OrderedIndexSearch(FilterOp::kLt, SqlValue::Long(2), indices);
233 ASSERT_EQ(range.start, 0u);
234 ASSERT_EQ(range.end, 1u);
235
236 range = chain->OrderedIndexSearch(FilterOp::kLe, SqlValue::Long(2), indices);
237 ASSERT_EQ(range.start, 0u);
238 ASSERT_EQ(range.end, 3u);
239 }
240
TEST(SetIdStorage,SearchEqSimple)241 TEST(SetIdStorage, SearchEqSimple) {
242 std::vector<uint32_t> storage_data{0, 0, 0, 3, 3, 3, 6, 6, 6, 9, 9, 9};
243
244 SetIdStorage storage(&storage_data);
245 auto chain = storage.MakeChain();
246 Range range = chain->Search(FilterOp::kEq, SqlValue::Long(3), Range(4, 10))
247 .TakeIfRange();
248
249 ASSERT_EQ(range.size(), 2u);
250 ASSERT_EQ(range.start, 4u);
251 ASSERT_EQ(range.end, 6u);
252 }
253
TEST(SetIdStorageUnittest,SearchEqFalse)254 TEST(SetIdStorageUnittest, SearchEqFalse) {
255 std::vector<uint32_t> storage_data{0, 0, 0, 3, 3, 3, 6, 6, 6, 9, 9, 9};
256 SetIdStorage storage(&storage_data);
257 auto chain = storage.MakeChain();
258
259 Range range = chain->Search(FilterOp::kEq, SqlValue::Long(5), Range(4, 10))
260 .TakeIfRange();
261
262 ASSERT_TRUE(range.empty());
263 }
264
TEST(SetIdStorage,SearchEqOnRangeBoundary)265 TEST(SetIdStorage, SearchEqOnRangeBoundary) {
266 std::vector<uint32_t> storage_data{0, 0, 0, 3, 3, 3, 6, 6, 6, 9, 9, 9};
267
268 SetIdStorage storage(&storage_data);
269 auto chain = storage.MakeChain();
270 Range range = chain->Search(FilterOp::kEq, SqlValue::Long(9), Range(6, 9))
271 .TakeIfRange();
272 ASSERT_EQ(range.size(), 0u);
273 }
274
TEST(SetIdStorage,SearchEqOutsideRange)275 TEST(SetIdStorage, SearchEqOutsideRange) {
276 std::vector<uint32_t> storage_data{0, 0, 0, 3, 3, 3, 6, 6, 6, 9, 9, 9};
277
278 SetIdStorage storage(&storage_data);
279 auto chain = storage.MakeChain();
280 Range range = chain->Search(FilterOp::kEq, SqlValue::Long(12), Range(6, 9))
281 .TakeIfRange();
282 ASSERT_EQ(range.size(), 0u);
283 }
284
TEST(SetIdStorage,SearchEqTooBig)285 TEST(SetIdStorage, SearchEqTooBig) {
286 std::vector<uint32_t> storage_data{0, 0, 0, 3, 3, 3, 6, 6, 6, 9, 9, 9};
287
288 SetIdStorage storage(&storage_data);
289 auto chain = storage.MakeChain();
290 Range range = chain->Search(FilterOp::kEq, SqlValue::Long(100), Range(6, 9))
291 .TakeIfRange();
292 ASSERT_EQ(range.size(), 0u);
293 }
294
TEST(SetIdStorage,IndexSearchEqTooBig)295 TEST(SetIdStorage, IndexSearchEqTooBig) {
296 std::vector<uint32_t> storage_data{0, 0, 0, 3, 3, 3, 6, 6, 6, 9, 9, 9};
297 SetIdStorage storage(&storage_data);
298 auto chain = storage.MakeChain();
299
300 // {0, 3, 3, 6, 9, 9, 0, 3}
301 auto indices = Indices::CreateWithIndexPayloadForTesting(
302 {1, 3, 5, 7, 9, 11, 2, 4}, Indices::State::kNonmonotonic);
303 chain->IndexSearch(FilterOp::kEq, SqlValue::Long(10), indices);
304 ASSERT_THAT(utils::ExtractPayloadForTesting(indices), IsEmpty());
305 }
306
TEST(SetIdStorageUnittest,IndexSearchEqFalse)307 TEST(SetIdStorageUnittest, IndexSearchEqFalse) {
308 std::vector<uint32_t> storage_data{0, 0, 0, 3, 3, 3, 6, 6, 6, 9, 9, 9};
309 SetIdStorage storage(&storage_data);
310 auto chain = storage.MakeChain();
311
312 // {0, 3, 3, 6, 9, 9, 0, 3}
313 auto indices = Indices::CreateWithIndexPayloadForTesting(
314 {1, 3, 5, 7, 9, 11, 2, 4}, Indices::State::kNonmonotonic);
315 chain->IndexSearch(FilterOp::kEq, SqlValue::Long(5), indices);
316
317 ASSERT_THAT(utils::ExtractPayloadForTesting(indices), IsEmpty());
318 }
319
TEST(SetIdStorage,SearchWithIdAsSimpleDoubleIsInt)320 TEST(SetIdStorage, SearchWithIdAsSimpleDoubleIsInt) {
321 std::vector<uint32_t> storage_data{0, 0, 0, 3, 3, 3, 6, 6, 6, 9, 9, 9};
322 SetIdStorage storage(&storage_data);
323 auto chain = storage.MakeChain();
324 SqlValue double_val = SqlValue::Double(7.0);
325 SqlValue long_val = SqlValue::Long(7);
326 Range range(1, 9);
327
328 FilterOp op = FilterOp::kEq;
329 auto double_res = chain->Search(op, double_val, range);
330 auto int_res = chain->Search(op, long_val, range);
331 ASSERT_EQ(utils::ToIndexVectorForTests(double_res),
332 utils::ToIndexVectorForTests(int_res));
333
334 op = FilterOp::kNe;
335 double_res = chain->Search(op, double_val, range);
336 int_res = chain->Search(op, long_val, range);
337 ASSERT_EQ(utils::ToIndexVectorForTests(double_res),
338 utils::ToIndexVectorForTests(int_res));
339
340 op = FilterOp::kLe;
341 double_res = chain->Search(op, double_val, range);
342 int_res = chain->Search(op, long_val, range);
343 ASSERT_EQ(utils::ToIndexVectorForTests(double_res),
344 utils::ToIndexVectorForTests(int_res));
345
346 op = FilterOp::kLt;
347 double_res = chain->Search(op, double_val, range);
348 int_res = chain->Search(op, long_val, range);
349 ASSERT_EQ(utils::ToIndexVectorForTests(double_res),
350 utils::ToIndexVectorForTests(int_res));
351
352 op = FilterOp::kGe;
353 double_res = chain->Search(op, double_val, range);
354 int_res = chain->Search(op, long_val, range);
355 ASSERT_EQ(utils::ToIndexVectorForTests(double_res),
356 utils::ToIndexVectorForTests(int_res));
357
358 op = FilterOp::kGt;
359 double_res = chain->Search(op, double_val, range);
360 int_res = chain->Search(op, long_val, range);
361 ASSERT_EQ(utils::ToIndexVectorForTests(double_res),
362 utils::ToIndexVectorForTests(int_res));
363 }
364
TEST(SetIdStorage,SearchWithIdAsDouble)365 TEST(SetIdStorage, SearchWithIdAsDouble) {
366 std::vector<uint32_t> storage_data{0, 0, 0, 3, 3, 3, 6, 6, 6, 9, 9, 9};
367 SetIdStorage storage(&storage_data);
368 auto chain = storage.MakeChain();
369 SqlValue val = SqlValue::Double(7.5);
370 Range range(5, 10);
371
372 Range res = chain->Search(FilterOp::kEq, val, range).TakeIfRange();
373 ASSERT_EQ(res, Range());
374
375 res = chain->Search(FilterOp::kNe, val, range).TakeIfRange();
376 ASSERT_EQ(res, Range(0, 10));
377
378 res = chain->Search(FilterOp::kLe, val, range).TakeIfRange();
379 ASSERT_EQ(res, Range(5, 9));
380
381 res = chain->Search(FilterOp::kLt, val, range).TakeIfRange();
382 ASSERT_EQ(res, Range(5, 9));
383
384 res = chain->Search(FilterOp::kGe, val, range).TakeIfRange();
385 ASSERT_EQ(res, Range(9, 10));
386
387 res = chain->Search(FilterOp::kGt, val, range).TakeIfRange();
388 ASSERT_EQ(res, Range(9, 10));
389 }
390
TEST(SetIdStorage,StableSort)391 TEST(SetIdStorage, StableSort) {
392 std::vector<uint32_t> storage_data{0, 0, 0, 3, 3};
393 SetIdStorage storage(&storage_data);
394 auto chain = storage.MakeChain();
395 auto make_tokens = []() {
396 return std::vector{
397 Token{3, 3}, Token{2, 2}, Token{1, 1}, Token{0, 0}, Token{4, 4},
398 };
399 };
400 {
401 auto tokens = make_tokens();
402 chain->StableSort(tokens.data(), tokens.data() + tokens.size(),
403 SortDirection::kAscending);
404 ASSERT_THAT(utils::ExtractPayloadForTesting(tokens),
405 ElementsAre(2, 1, 0, 3, 4));
406 }
407 {
408 auto tokens = make_tokens();
409 chain->StableSort(tokens.data(), tokens.data() + tokens.size(),
410 SortDirection::kDescending);
411 ASSERT_THAT(utils::ExtractPayloadForTesting(tokens),
412 ElementsAre(3, 4, 2, 1, 0));
413 }
414 }
415
TEST(SetIdStorage,Distinct)416 TEST(SetIdStorage, Distinct) {
417 std::vector<uint32_t> storage_data{0, 0, 0, 3, 3, 3, 6, 6, 6, 9, 9, 9};
418 SetIdStorage storage(&storage_data);
419 auto chain = storage.MakeChain();
420
421 auto indices = Indices::CreateWithIndexPayloadForTesting(
422 {10, 9, 0, 1, 4}, Indices::State::kNonmonotonic);
423 chain->Distinct(indices);
424 ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(0, 2, 4));
425 }
426
427 } // namespace
428 } // namespace column
429 } // namespace perfetto::trace_processor
430