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/id_storage.h"
17
18 #include <cstdint>
19 #include <limits>
20 #include <vector>
21
22 #include "perfetto/trace_processor/basic_types.h"
23 #include "src/trace_processor/containers/bit_vector.h"
24 #include "src/trace_processor/db/column/data_layer.h"
25 #include "src/trace_processor/db/column/types.h"
26 #include "src/trace_processor/db/column/utils.h"
27 #include "test/gtest_and_gmock.h"
28
29 namespace perfetto::trace_processor {
30
operator ==(const Range & a,const Range & b)31 inline bool operator==(const Range& a, const Range& b) {
32 return std::tie(a.start, a.end) == std::tie(b.start, b.end);
33 }
34
operator ==(const BitVector & a,const BitVector & b)35 inline bool operator==(const BitVector& a, const BitVector& b) {
36 return a.size() == b.size() && a.CountSetBits() == b.CountSetBits();
37 }
38
39 namespace column {
40 namespace {
41
42 using testing::ElementsAre;
43 using testing::IsEmpty;
44
45 using Indices = DataLayerChain::Indices;
46 using OrderedIndices = DataLayerChain::OrderedIndices;
47
TEST(IdStorage,InvalidSearchConstraints)48 TEST(IdStorage, InvalidSearchConstraints) {
49 IdStorage storage;
50 auto chain = storage.MakeChain();
51
52 // NULL checks
53 ASSERT_EQ(chain->ValidateSearchConstraints(FilterOp::kIsNull, SqlValue()),
54 SearchValidationResult::kNoData);
55 ASSERT_EQ(chain->ValidateSearchConstraints(FilterOp::kIsNotNull, SqlValue()),
56 SearchValidationResult::kAllData);
57
58 // FilterOp checks
59 ASSERT_EQ(
60 chain->ValidateSearchConstraints(FilterOp::kGlob, SqlValue::Long(15)),
61 SearchValidationResult::kNoData);
62 ASSERT_EQ(
63 chain->ValidateSearchConstraints(FilterOp::kRegex, SqlValue::Long(15)),
64 SearchValidationResult::kNoData);
65
66 // Type checks
67 ASSERT_EQ(chain->ValidateSearchConstraints(FilterOp::kGe,
68 SqlValue::String("cheese")),
69 SearchValidationResult::kNoData);
70
71 // With double
72 ASSERT_EQ(
73 chain->ValidateSearchConstraints(FilterOp::kGe, SqlValue::Double(-1)),
74 SearchValidationResult::kAllData);
75
76 // Value bounds
77 SqlValue max_val = SqlValue::Long(
78 static_cast<int64_t>(std::numeric_limits<uint32_t>::max()) + 10);
79 ASSERT_EQ(chain->ValidateSearchConstraints(FilterOp::kGe, max_val),
80 SearchValidationResult::kNoData);
81 ASSERT_EQ(chain->ValidateSearchConstraints(FilterOp::kGt, max_val),
82 SearchValidationResult::kNoData);
83 ASSERT_EQ(chain->ValidateSearchConstraints(FilterOp::kEq, max_val),
84 SearchValidationResult::kNoData);
85
86 ASSERT_EQ(chain->ValidateSearchConstraints(FilterOp::kLe, max_val),
87 SearchValidationResult::kAllData);
88 ASSERT_EQ(chain->ValidateSearchConstraints(FilterOp::kLt, max_val),
89 SearchValidationResult::kAllData);
90 ASSERT_EQ(chain->ValidateSearchConstraints(FilterOp::kNe, max_val),
91 SearchValidationResult::kAllData);
92
93 SqlValue min_val = SqlValue::Long(-1);
94 ASSERT_EQ(chain->ValidateSearchConstraints(FilterOp::kGe, min_val),
95 SearchValidationResult::kAllData);
96 ASSERT_EQ(chain->ValidateSearchConstraints(FilterOp::kGt, min_val),
97 SearchValidationResult::kAllData);
98 ASSERT_EQ(chain->ValidateSearchConstraints(FilterOp::kNe, min_val),
99 SearchValidationResult::kAllData);
100
101 ASSERT_EQ(chain->ValidateSearchConstraints(FilterOp::kLe, min_val),
102 SearchValidationResult::kNoData);
103 ASSERT_EQ(chain->ValidateSearchConstraints(FilterOp::kLt, min_val),
104 SearchValidationResult::kNoData);
105 ASSERT_EQ(chain->ValidateSearchConstraints(FilterOp::kEq, min_val),
106 SearchValidationResult::kNoData);
107 }
108
TEST(IdStorage,SinglSearch)109 TEST(IdStorage, SinglSearch) {
110 IdStorage storage;
111 auto chain = storage.MakeChain();
112
113 ASSERT_EQ(chain->SingleSearch(FilterOp::kEq, SqlValue::Long(5), 5),
114 SingleSearchResult::kMatch);
115 ASSERT_EQ(chain->SingleSearch(FilterOp::kEq, SqlValue::Long(5), 3),
116 SingleSearchResult::kNoMatch);
117
118 ASSERT_EQ(chain->SingleSearch(FilterOp::kNe, SqlValue::Long(5), 3),
119 SingleSearchResult::kMatch);
120 ASSERT_EQ(chain->SingleSearch(FilterOp::kNe, SqlValue::Long(5), 5),
121 SingleSearchResult::kNoMatch);
122
123 ASSERT_EQ(chain->SingleSearch(FilterOp::kLe, SqlValue::Long(5), 5),
124 SingleSearchResult::kMatch);
125 ASSERT_EQ(chain->SingleSearch(FilterOp::kLe, SqlValue::Long(5), 6),
126 SingleSearchResult::kNoMatch);
127
128 ASSERT_EQ(chain->SingleSearch(FilterOp::kLt, SqlValue::Long(5), 4),
129 SingleSearchResult::kMatch);
130 ASSERT_EQ(chain->SingleSearch(FilterOp::kLt, SqlValue::Long(5), 6),
131 SingleSearchResult::kNoMatch);
132
133 ASSERT_EQ(chain->SingleSearch(FilterOp::kGe, SqlValue::Long(5), 5),
134 SingleSearchResult::kMatch);
135 ASSERT_EQ(chain->SingleSearch(FilterOp::kGe, SqlValue::Long(5), 4),
136 SingleSearchResult::kNoMatch);
137
138 ASSERT_EQ(chain->SingleSearch(FilterOp::kGt, SqlValue::Long(5), 6),
139 SingleSearchResult::kMatch);
140 ASSERT_EQ(chain->SingleSearch(FilterOp::kGt, SqlValue::Long(5), 4),
141 SingleSearchResult::kNoMatch);
142
143 ASSERT_EQ(chain->SingleSearch(FilterOp::kEq, SqlValue::Double(5), 4),
144 SingleSearchResult::kNeedsFullSearch);
145 ASSERT_EQ(chain->SingleSearch(FilterOp::kEq, SqlValue::String(""), 4),
146 SingleSearchResult::kNeedsFullSearch);
147 ASSERT_EQ(chain->SingleSearch(FilterOp::kGlob, SqlValue::Long(5), 4),
148 SingleSearchResult::kNoMatch);
149 }
150
TEST(IdStorage,SearchEqSimple)151 TEST(IdStorage, SearchEqSimple) {
152 IdStorage storage;
153 auto chain = storage.MakeChain();
154 Range range = chain->Search(FilterOp::kEq, SqlValue::Long(15), Range(10, 20))
155 .TakeIfRange();
156 ASSERT_EQ(range.size(), 1u);
157 ASSERT_EQ(range.start, 15u);
158 ASSERT_EQ(range.end, 16u);
159 }
160
TEST(IdStorage,SearchEqOnRangeBoundary)161 TEST(IdStorage, SearchEqOnRangeBoundary) {
162 IdStorage storage;
163 auto chain = storage.MakeChain();
164 Range range = chain->Search(FilterOp::kEq, SqlValue::Long(20), Range(10, 20))
165 .TakeIfRange();
166 ASSERT_EQ(range.size(), 0u);
167 }
168
TEST(IdStorage,SearchEqOutsideRange)169 TEST(IdStorage, SearchEqOutsideRange) {
170 IdStorage storage;
171 auto chain = storage.MakeChain();
172 Range range = chain->Search(FilterOp::kEq, SqlValue::Long(25), Range(10, 20))
173 .TakeIfRange();
174 ASSERT_EQ(range.size(), 0u);
175 }
176
TEST(IdStorage,SearchEqTooBig)177 TEST(IdStorage, SearchEqTooBig) {
178 IdStorage storage;
179 auto chain = storage.MakeChain();
180 Range range = chain->Search(FilterOp::kEq, SqlValue::Long(125), Range(10, 20))
181 .TakeIfRange();
182 ASSERT_EQ(range.size(), 0u);
183 }
184
TEST(IdStorage,SearchSimple)185 TEST(IdStorage, SearchSimple) {
186 IdStorage storage;
187 auto chain = storage.MakeChain();
188 SqlValue val = SqlValue::Long(5);
189 Range filter_range(3, 7);
190
191 FilterOp op = FilterOp::kEq;
192 auto res = chain->Search(op, val, filter_range);
193 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(5));
194
195 op = FilterOp::kNe;
196 res = chain->Search(op, val, filter_range);
197 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(3, 4, 6));
198
199 op = FilterOp::kLe;
200 res = chain->Search(op, val, filter_range);
201 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(3, 4, 5));
202
203 op = FilterOp::kLt;
204 res = chain->Search(op, val, filter_range);
205 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(3, 4));
206
207 op = FilterOp::kGe;
208 res = chain->Search(op, val, filter_range);
209 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(5, 6));
210
211 op = FilterOp::kGt;
212 res = chain->Search(op, val, filter_range);
213 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(6));
214 }
215
TEST(IdStorage,IndexSearchSimple)216 TEST(IdStorage, IndexSearchSimple) {
217 IdStorage storage;
218 auto chain = storage.MakeChain();
219 SqlValue val = SqlValue::Long(5);
220
221 auto common_indices = Indices::CreateWithIndexPayloadForTesting(
222 {5, 4, 3, 9, 8, 7}, Indices::State::kNonmonotonic);
223
224 auto indices = common_indices;
225 chain->IndexSearch(FilterOp::kEq, val, indices);
226 ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(0));
227
228 indices = common_indices;
229 chain->IndexSearch(FilterOp::kNe, val, indices);
230 ASSERT_THAT(utils::ExtractPayloadForTesting(indices),
231 ElementsAre(1, 2, 3, 4, 5));
232
233 indices = common_indices;
234 chain->IndexSearch(FilterOp::kLe, val, indices);
235 ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(0, 1, 2));
236
237 indices = common_indices;
238 chain->IndexSearch(FilterOp::kLt, val, indices);
239 ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(1, 2));
240
241 indices = common_indices;
242 chain->IndexSearch(FilterOp::kGe, val, indices);
243 ASSERT_THAT(utils::ExtractPayloadForTesting(indices),
244 ElementsAre(0, 3, 4, 5));
245
246 indices = common_indices;
247 chain->IndexSearch(FilterOp::kGt, val, indices);
248 ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(3, 4, 5));
249 }
250
TEST(IdStorage,OrderedIndexSearch)251 TEST(IdStorage, OrderedIndexSearch) {
252 IdStorage storage;
253 auto chain = storage.MakeChain();
254
255 std::vector<uint32_t> indices_vec{0, 1, 2, 4, 4};
256 OrderedIndices indices{indices_vec.data(), 5, Indices::State::kMonotonic};
257
258 Range range =
259 chain->OrderedIndexSearch(FilterOp::kEq, SqlValue::Long(2), indices);
260 ASSERT_EQ(range.start, 2u);
261 ASSERT_EQ(range.end, 3u);
262
263 range = chain->OrderedIndexSearch(FilterOp::kGt, SqlValue::Long(2), indices);
264 ASSERT_EQ(range.start, 3u);
265 ASSERT_EQ(range.end, 5u);
266
267 range = chain->OrderedIndexSearch(FilterOp::kGe, SqlValue::Long(2), indices);
268 ASSERT_EQ(range.start, 2u);
269 ASSERT_EQ(range.end, 5u);
270
271 range = chain->OrderedIndexSearch(FilterOp::kLt, SqlValue::Long(2), indices);
272 ASSERT_EQ(range.start, 0u);
273 ASSERT_EQ(range.end, 2u);
274
275 range = chain->OrderedIndexSearch(FilterOp::kLe, SqlValue::Long(2), indices);
276 ASSERT_EQ(range.start, 0u);
277 ASSERT_EQ(range.end, 3u);
278 }
279
TEST(IdStorage,IndexSearchEqTooBig)280 TEST(IdStorage, IndexSearchEqTooBig) {
281 IdStorage storage;
282 auto chain = storage.MakeChain();
283
284 auto indices = Indices::CreateWithIndexPayloadForTesting(
285 {1, 3, 5, 7, 9, 11, 2, 4}, Indices::State::kNonmonotonic);
286 chain->IndexSearch(FilterOp::kEq, SqlValue::Long(20), indices);
287 ASSERT_THAT(utils::ExtractPayloadForTesting(indices), IsEmpty());
288 }
289
TEST(IdStorage,SearchWithIdAsDoubleSimple)290 TEST(IdStorage, SearchWithIdAsDoubleSimple) {
291 IdStorage storage;
292 auto chain = storage.MakeChain();
293 SqlValue double_val = SqlValue::Double(15.0);
294 SqlValue long_val = SqlValue::Long(15);
295 Range range(10, 20);
296
297 auto res_double = chain->Search(FilterOp::kEq, double_val, range);
298 auto res_long = chain->Search(FilterOp::kEq, long_val, range);
299 ASSERT_EQ(utils::ToIndexVectorForTests(res_double),
300 utils::ToIndexVectorForTests(res_long));
301
302 res_double = chain->Search(FilterOp::kNe, double_val, range);
303 res_long = chain->Search(FilterOp::kNe, long_val, range);
304 ASSERT_EQ(utils::ToIndexVectorForTests(res_double),
305 utils::ToIndexVectorForTests(res_long));
306
307 res_double = chain->Search(FilterOp::kLe, double_val, range);
308 res_long = chain->Search(FilterOp::kLe, long_val, range);
309 ASSERT_EQ(utils::ToIndexVectorForTests(res_double),
310 utils::ToIndexVectorForTests(res_long));
311
312 res_double = chain->Search(FilterOp::kLt, double_val, range);
313 res_long = chain->Search(FilterOp::kLt, long_val, range);
314 ASSERT_EQ(utils::ToIndexVectorForTests(res_double),
315 utils::ToIndexVectorForTests(res_long));
316
317 res_double = chain->Search(FilterOp::kGe, double_val, range);
318 res_long = chain->Search(FilterOp::kGe, long_val, range);
319 ASSERT_EQ(utils::ToIndexVectorForTests(res_double),
320 utils::ToIndexVectorForTests(res_long));
321
322 res_double = chain->Search(FilterOp::kGt, double_val, range);
323 res_long = chain->Search(FilterOp::kGt, long_val, range);
324 ASSERT_EQ(utils::ToIndexVectorForTests(res_double),
325 utils::ToIndexVectorForTests(res_long));
326 }
327
TEST(IdStorage,SearchWithIdAsDouble)328 TEST(IdStorage, SearchWithIdAsDouble) {
329 IdStorage storage;
330 auto chain = storage.MakeChain();
331 Range range(10, 20);
332 SqlValue val = SqlValue::Double(15.5);
333
334 auto res = chain->Search(FilterOp::kEq, val, range);
335 ASSERT_THAT(utils::ToIndexVectorForTests(res), IsEmpty());
336
337 res = chain->Search(FilterOp::kNe, val, range);
338 ASSERT_EQ(utils::ToIndexVectorForTests(res).size(), 20u);
339
340 res = chain->Search(FilterOp::kLe, val, range);
341 ASSERT_THAT(utils::ToIndexVectorForTests(res),
342 ElementsAre(10, 11, 12, 13, 14, 15));
343
344 res = chain->Search(FilterOp::kLt, val, range);
345 ASSERT_THAT(utils::ToIndexVectorForTests(res),
346 ElementsAre(10, 11, 12, 13, 14, 15));
347
348 res = chain->Search(FilterOp::kGe, val, range);
349 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(16, 17, 18, 19));
350
351 res = chain->Search(FilterOp::kGt, val, range);
352 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(16, 17, 18, 19));
353 }
354
TEST(IdStorage,StableSort)355 TEST(IdStorage, StableSort) {
356 IdStorage storage;
357 auto chain = storage.MakeChain();
358 std::vector tokens{
359 Token{0, 0}, Token{1, 1}, Token{2, 2}, Token{3, 3}, Token{4, 4},
360 };
361 chain->StableSort(tokens.data(), tokens.data() + tokens.size(),
362 SortDirection::kAscending);
363 ASSERT_THAT(utils::ExtractPayloadForTesting(tokens),
364 ElementsAre(0, 1, 2, 3, 4));
365
366 chain->StableSort(tokens.data(), tokens.data() + tokens.size(),
367 SortDirection::kDescending);
368 ASSERT_THAT(utils::ExtractPayloadForTesting(tokens),
369 ElementsAre(4, 3, 2, 1, 0));
370 }
371
TEST(IdStorage,Distinct)372 TEST(IdStorage, Distinct) {
373 IdStorage storage;
374 auto chain = storage.MakeChain();
375
376 auto indices = Indices::CreateWithIndexPayloadForTesting(
377 {1, 1, 0, 3}, Indices::State::kNonmonotonic);
378 chain->Distinct(indices);
379 ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(0, 2, 3));
380 }
381
382 } // namespace
383 } // namespace column
384 } // namespace perfetto::trace_processor
385