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/string_storage.h"
17
18 #include <cstdint>
19 #include <string>
20 #include <vector>
21
22 #include "perfetto/base/build_config.h"
23 #include "perfetto/ext/base/string_view.h"
24 #include "perfetto/trace_processor/basic_types.h"
25 #include "src/trace_processor/containers/bit_vector.h"
26 #include "src/trace_processor/containers/string_pool.h"
27 #include "src/trace_processor/db/column/data_layer.h"
28 #include "src/trace_processor/db/column/types.h"
29 #include "src/trace_processor/db/column/utils.h"
30 #include "test/gtest_and_gmock.h"
31
32 namespace perfetto::trace_processor::column {
33 namespace {
34
35 using testing::ElementsAre;
36 using testing::IsEmpty;
37
38 using Indices = DataLayerChain::Indices;
39 using OrderedIndices = DataLayerChain::OrderedIndices;
40
TEST(StringStorage,SearchOneElement)41 TEST(StringStorage, SearchOneElement) {
42 std::vector<std::string> strings{"cheese", "pasta", "pizza",
43 "pierogi", "onion", "fries"};
44 std::vector<StringPool::Id> ids;
45 StringPool pool;
46 for (const auto& string : strings) {
47 ids.push_back(pool.InternString(base::StringView(string)));
48 }
49 ids.insert(ids.begin() + 3, StringPool::Id::Null());
50 // 0:"cheese", 1:"pasta", 2:"pizza", 3:NULL, 4:"pierogi", 5:"onion", 6:"fries"
51 StringStorage storage(&pool, &ids);
52 auto chain = storage.MakeChain();
53
54 ASSERT_EQ(chain->SingleSearch(FilterOp::kEq, SqlValue::String("pierogi"), 4),
55 SingleSearchResult::kMatch);
56 ASSERT_EQ(chain->SingleSearch(FilterOp::kEq, SqlValue::String("pierogi"), 3),
57 SingleSearchResult::kNoMatch);
58
59 ASSERT_EQ(chain->SingleSearch(FilterOp::kNe, SqlValue::String("foo"), 0),
60 SingleSearchResult::kMatch);
61 ASSERT_EQ(chain->SingleSearch(FilterOp::kNe, SqlValue::String("pierogi"), 0),
62 SingleSearchResult::kMatch);
63 ASSERT_EQ(chain->SingleSearch(FilterOp::kNe, SqlValue::String("pierogi"), 4),
64 SingleSearchResult::kNoMatch);
65
66 ASSERT_EQ(chain->SingleSearch(FilterOp::kGe, SqlValue::String("pierogi"), 4),
67 SingleSearchResult::kMatch);
68 ASSERT_EQ(chain->SingleSearch(FilterOp::kGe, SqlValue::String("pierogi"), 1),
69 SingleSearchResult::kNoMatch);
70
71 ASSERT_EQ(chain->SingleSearch(FilterOp::kGt, SqlValue::String("pierogi"), 2),
72 SingleSearchResult::kMatch);
73 ASSERT_EQ(chain->SingleSearch(FilterOp::kGt, SqlValue::String("pierogi"), 5),
74 SingleSearchResult::kNoMatch);
75
76 ASSERT_EQ(chain->SingleSearch(FilterOp::kLe, SqlValue::String("pierogi"), 4),
77 SingleSearchResult::kMatch);
78 ASSERT_EQ(chain->SingleSearch(FilterOp::kLe, SqlValue::String("pierogi"), 2),
79 SingleSearchResult::kNoMatch);
80
81 ASSERT_EQ(chain->SingleSearch(FilterOp::kLt, SqlValue::String("pierogi"), 0),
82 SingleSearchResult::kMatch);
83 ASSERT_EQ(chain->SingleSearch(FilterOp::kLt, SqlValue::String("pierogi"), 4),
84 SingleSearchResult::kNoMatch);
85
86 ASSERT_EQ(chain->SingleSearch(FilterOp::kIsNull, SqlValue(), 3),
87 SingleSearchResult::kMatch);
88 ASSERT_EQ(chain->SingleSearch(FilterOp::kIsNull, SqlValue(), 4),
89 SingleSearchResult::kNoMatch);
90
91 ASSERT_EQ(chain->SingleSearch(FilterOp::kIsNotNull, SqlValue(), 4),
92 SingleSearchResult::kMatch);
93 ASSERT_EQ(chain->SingleSearch(FilterOp::kIsNotNull, SqlValue(), 3),
94 SingleSearchResult::kNoMatch);
95
96 ASSERT_EQ(chain->SingleSearch(FilterOp::kGlob, SqlValue::String("p*"), 1),
97 SingleSearchResult::kMatch);
98 ASSERT_EQ(chain->SingleSearch(FilterOp::kGlob, SqlValue::String("p*"), 0),
99 SingleSearchResult::kNoMatch);
100 }
101
TEST(StringStorage,Search)102 TEST(StringStorage, Search) {
103 std::vector<std::string> strings{"cheese", "pasta", "pizza",
104 "pierogi", "onion", "fries"};
105 std::vector<StringPool::Id> ids;
106 StringPool pool;
107 ids.reserve(strings.size());
108 for (const auto& string : strings) {
109 ids.push_back(pool.InternString(base::StringView(string)));
110 }
111 ids.insert(ids.begin() + 3, StringPool::Id::Null());
112 StringStorage storage(&pool, &ids);
113 auto chain = storage.MakeChain();
114 SqlValue val = SqlValue::String("pierogi");
115 Range filter_range(0, 7);
116
117 FilterOp op = FilterOp::kEq;
118 auto res = chain->Search(op, val, filter_range);
119 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(4));
120
121 op = FilterOp::kNe;
122 res = chain->Search(op, val, filter_range);
123 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 1, 2, 5, 6));
124
125 op = FilterOp::kLt;
126 res = chain->Search(op, val, filter_range);
127 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 1, 5, 6));
128
129 op = FilterOp::kLe;
130 res = chain->Search(op, val, filter_range);
131 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 1, 4, 5, 6));
132
133 op = FilterOp::kGt;
134 res = chain->Search(op, val, filter_range);
135 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(2));
136
137 op = FilterOp::kGe;
138 res = chain->Search(op, val, filter_range);
139 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(2, 4));
140
141 op = FilterOp::kIsNull;
142 res = chain->Search(op, SqlValue(), filter_range);
143 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(3));
144
145 op = FilterOp::kIsNotNull;
146 res = chain->Search(op, SqlValue(), filter_range);
147 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 1, 2, 4, 5, 6));
148
149 op = FilterOp::kGlob;
150 res = chain->Search(op, SqlValue::String("p*"), filter_range);
151 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(1, 2, 4));
152 }
153
TEST(StringStorage,IndexSearch)154 TEST(StringStorage, IndexSearch) {
155 std::vector<std::string> strings{"cheese", "pasta", "pizza",
156 "pierogi", "onion", "fries"};
157 std::vector<StringPool::Id> ids;
158 StringPool pool;
159 for (const auto& string : strings) {
160 ids.push_back(pool.InternString(base::StringView(string)));
161 }
162 ids.insert(ids.begin() + 3, StringPool::Id::Null());
163 StringStorage storage(&pool, &ids);
164 auto chain = storage.MakeChain();
165 SqlValue val = SqlValue::String("pierogi");
166 // "fries", "onion", "pierogi", NULL, "pizza", "pasta", "cheese"
167 Indices common_indices = Indices::CreateWithIndexPayloadForTesting(
168 {6, 5, 4, 3, 2, 1, 0}, Indices::State::kNonmonotonic);
169
170 auto indices = common_indices;
171 chain->IndexSearch(FilterOp::kEq, val, indices);
172 ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(2));
173
174 indices = common_indices;
175 chain->IndexSearch(FilterOp::kNe, val, indices);
176 ASSERT_THAT(utils::ExtractPayloadForTesting(indices),
177 ElementsAre(0, 1, 4, 5, 6));
178
179 indices = common_indices;
180 chain->IndexSearch(FilterOp::kLt, val, indices);
181 ASSERT_THAT(utils::ExtractPayloadForTesting(indices),
182 ElementsAre(0, 1, 5, 6));
183
184 indices = common_indices;
185 chain->IndexSearch(FilterOp::kLe, val, indices);
186 ASSERT_THAT(utils::ExtractPayloadForTesting(indices),
187 ElementsAre(0, 1, 2, 5, 6));
188
189 indices = common_indices;
190 chain->IndexSearch(FilterOp::kGt, val, indices);
191 ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(4));
192
193 indices = common_indices;
194 chain->IndexSearch(FilterOp::kGe, val, indices);
195 ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(2, 4));
196
197 indices = common_indices;
198 chain->IndexSearch(FilterOp::kIsNull, SqlValue(), indices);
199 ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(3));
200
201 indices = common_indices;
202 chain->IndexSearch(FilterOp::kIsNotNull, SqlValue(), indices);
203 ASSERT_THAT(utils::ExtractPayloadForTesting(indices),
204 ElementsAre(0, 1, 2, 4, 5, 6));
205
206 indices = common_indices;
207 chain->IndexSearch(FilterOp::kGlob, SqlValue::String("p*"), indices);
208 ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(2, 4, 5));
209 }
210
211 #if !PERFETTO_BUILDFLAG(PERFETTO_OS_WIN)
TEST(StringStorage,LinearSearchRegex)212 TEST(StringStorage, LinearSearchRegex) {
213 std::vector<std::string> strings{"cheese", "pasta", "pizza",
214 "pierogi", "onion", "fries"};
215 std::vector<StringPool::Id> ids;
216 StringPool pool;
217 for (const auto& string : strings) {
218 ids.push_back(pool.InternString(base::StringView(string)));
219 }
220 ids.insert(ids.begin() + 3, StringPool::Id::Null());
221
222 StringStorage storage(&pool, &ids);
223 auto chain = storage.MakeChain();
224 BitVector bv =
225 chain->Search(FilterOp::kRegex, SqlValue::String(".*zz.*"), Range(0, 7))
226 .TakeIfBitVector();
227
228 ASSERT_EQ(bv.CountSetBits(), 1u);
229 }
230
TEST(StringStorage,LinearSearchRegexMalformed)231 TEST(StringStorage, LinearSearchRegexMalformed) {
232 std::vector<std::string> strings{"cheese", "pasta", "pizza",
233 "pierogi", "onion", "fries"};
234 std::vector<StringPool::Id> ids;
235 StringPool pool;
236 for (const auto& string : strings) {
237 ids.push_back(pool.InternString(base::StringView(string)));
238 }
239 ids.insert(ids.begin() + 3, StringPool::Id::Null());
240
241 StringStorage storage(&pool, &ids);
242 auto chain = storage.MakeChain();
243 BitVector bv =
244 chain->Search(FilterOp::kRegex, SqlValue::String("*"), Range(0, 7))
245 .TakeIfBitVector();
246
247 ASSERT_EQ(bv.CountSetBits(), 0u);
248 }
249 #endif
250
TEST(StringStorage,SearchEmptyString)251 TEST(StringStorage, SearchEmptyString) {
252 std::vector<std::string> strings{"", "apple"};
253 std::vector<StringPool::Id> ids(3, StringPool::Id::Null());
254 StringPool pool;
255 for (const auto& string : strings) {
256 ids.push_back(pool.InternString(base::StringView(string)));
257 }
258 StringStorage storage(&pool, &ids, true);
259 auto chain = storage.MakeChain();
260
261 auto res = chain->Search(FilterOp::kEq, SqlValue::String(""), {0, 5});
262 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(3));
263 }
264
TEST(StringStorage,SearchEmptyStringIsNull)265 TEST(StringStorage, SearchEmptyStringIsNull) {
266 std::vector<std::string> strings{"", "apple"};
267 std::vector<StringPool::Id> ids(3, StringPool::Id::Null());
268 StringPool pool;
269 for (const auto& string : strings) {
270 ids.push_back(pool.InternString(base::StringView(string)));
271 }
272 StringStorage storage(&pool, &ids, true);
273 auto chain = storage.MakeChain();
274
275 auto res = chain->Search(FilterOp::kIsNull, SqlValue(), {0, 5});
276 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 1, 2));
277 }
278
TEST(StringStorage,SearchSorted)279 TEST(StringStorage, SearchSorted) {
280 std::vector<std::string> strings{"apple", "burger", "cheese",
281 "doughnut", "eggplant", "fries"};
282 std::vector<StringPool::Id> ids(3, StringPool::Id::Null());
283 StringPool pool;
284 for (const auto& string : strings) {
285 ids.push_back(pool.InternString(base::StringView(string)));
286 }
287 StringStorage storage(&pool, &ids, true);
288 auto chain = storage.MakeChain();
289 SqlValue val = SqlValue::String("cheese");
290 // 1:NULL, 2:NULL, 3:apple, 4:burger, 5:cheese, 6:doughnut, 7:eggplant,
291 Range filter_range(1, 8);
292
293 FilterOp op = FilterOp::kEq;
294 auto res = chain->Search(op, val, filter_range);
295 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(5));
296
297 op = FilterOp::kNe;
298 res = chain->Search(op, val, filter_range);
299 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(3, 4, 6, 7));
300
301 op = FilterOp::kLt;
302 res = chain->Search(op, val, filter_range);
303 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(3, 4));
304
305 op = FilterOp::kLe;
306 res = chain->Search(op, val, filter_range);
307 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(3, 4, 5));
308
309 op = FilterOp::kGt;
310 res = chain->Search(op, val, filter_range);
311 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(6, 7));
312
313 op = FilterOp::kGe;
314 res = chain->Search(op, val, filter_range);
315 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(5, 6, 7));
316
317 op = FilterOp::kGlob;
318 res = chain->Search(op, SqlValue::String("*e"), filter_range);
319 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(3, 5));
320 }
321
TEST(StringStorage,IndexSearchSorted)322 TEST(StringStorage, IndexSearchSorted) {
323 std::vector<std::string> strings{"apple", "burger", "cheese",
324 "doughnut", "eggplant", "fries"};
325 std::vector<StringPool::Id> ids;
326 StringPool pool;
327 for (const auto& string : strings) {
328 ids.push_back(pool.InternString(base::StringView(string)));
329 }
330 StringStorage storage(&pool, &ids, true);
331 auto chain = storage.MakeChain();
332 SqlValue val = SqlValue::String("cheese");
333 Indices common_indices = Indices::CreateWithIndexPayloadForTesting(
334 {5, 4, 2, 1}, Indices::State::kNonmonotonic);
335
336 auto indices = common_indices;
337 chain->IndexSearch(FilterOp::kEq, val, indices);
338 ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(2));
339
340 indices = common_indices;
341 chain->IndexSearch(FilterOp::kNe, val, indices);
342 ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(0, 1, 3));
343
344 indices = common_indices;
345 chain->IndexSearch(FilterOp::kLt, val, indices);
346 ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(3));
347
348 indices = common_indices;
349 chain->IndexSearch(FilterOp::kLe, val, indices);
350 ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(2, 3));
351
352 indices = common_indices;
353 chain->IndexSearch(FilterOp::kGt, val, indices);
354 ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(0, 1));
355
356 indices = common_indices;
357 chain->IndexSearch(FilterOp::kGe, val, indices);
358 ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(0, 1, 2));
359
360 indices = common_indices;
361 chain->IndexSearch(FilterOp::kGlob, SqlValue::String("*e"), indices);
362 ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(2));
363 }
364
TEST(StringStorage,OrderedIndexSearch)365 TEST(StringStorage, OrderedIndexSearch) {
366 std::vector<std::string> strings{"cheese", "pasta", "pizza",
367 "pierogi", "onion", "fries"};
368 std::vector<StringPool::Id> ids(1, StringPool::Id::Null());
369 StringPool pool;
370 for (const auto& string : strings) {
371 ids.push_back(pool.InternString(base::StringView(string)));
372 }
373 StringStorage storage(&pool, &ids);
374 auto chain = storage.MakeChain();
375 SqlValue val = SqlValue::String("pierogi");
376 std::vector<uint32_t> indices_vec{0, 6, 5, 2, 4, 3};
377 OrderedIndices indices{indices_vec.data(), 6, Indices::State::kNonmonotonic};
378
379 FilterOp op = FilterOp::kEq;
380 Range res = chain->OrderedIndexSearch(op, val, indices);
381 ASSERT_EQ(res.start, 4u);
382 ASSERT_EQ(res.end, 5u);
383
384 op = FilterOp::kLt;
385 res = chain->OrderedIndexSearch(op, val, indices);
386 ASSERT_EQ(res.start, 0u);
387 ASSERT_EQ(res.end, 4u);
388
389 op = FilterOp::kLe;
390 res = chain->OrderedIndexSearch(op, val, indices);
391 ASSERT_EQ(res.start, 0u);
392 ASSERT_EQ(res.end, 5u);
393
394 op = FilterOp::kGt;
395 res = chain->OrderedIndexSearch(op, val, indices);
396 ASSERT_EQ(res.start, 5u);
397 ASSERT_EQ(res.end, 6u);
398
399 op = FilterOp::kGe;
400 res = chain->OrderedIndexSearch(op, val, indices);
401 ASSERT_EQ(res.start, 4u);
402 ASSERT_EQ(res.end, 6u);
403
404 op = FilterOp::kIsNull;
405 val = SqlValue();
406 res = chain->OrderedIndexSearch(op, val, indices);
407 ASSERT_EQ(res.start, 0u);
408 ASSERT_EQ(res.end, 1u);
409 }
410
TEST(StringStorage,OrderedIndexSearchLowerBoundWithNulls)411 TEST(StringStorage, OrderedIndexSearchLowerBoundWithNulls) {
412 std::vector<std::string> strings{"cheese", "pasta", "pizza",
413 "pierogi", "onion", "fries"};
414 std::vector<StringPool::Id> ids(3, StringPool::Id::Null());
415 StringPool pool;
416 for (const auto& string : strings) {
417 ids.push_back(pool.InternString(base::StringView(string)));
418 }
419 StringStorage storage(&pool, &ids);
420 auto chain = storage.MakeChain();
421
422 // NULL, NULL, cheese, pizza
423 std::vector<uint32_t> indices_vec{0, 2, 3, 7};
424 OrderedIndices indices{indices_vec.data(), 4, Indices::State::kNonmonotonic};
425 auto res = chain->OrderedIndexSearch(FilterOp::kEq,
426 SqlValue::String("cheese"), indices);
427 ASSERT_EQ(res.start, 2u);
428 ASSERT_EQ(res.end, 3u);
429 }
430
TEST(StringStorage,OrderedIndexSearchIsNull)431 TEST(StringStorage, OrderedIndexSearchIsNull) {
432 std::vector<std::string> strings{"cheese", "pasta", "pizza",
433 "pierogi", "onion", "fries"};
434 std::vector<StringPool::Id> ids(3, StringPool::Id::Null());
435 StringPool pool;
436 for (const auto& string : strings) {
437 ids.push_back(pool.InternString(base::StringView(string)));
438 }
439 StringStorage storage(&pool, &ids);
440 auto chain = storage.MakeChain();
441
442 std::vector<uint32_t> indices_vec{0, 2, 5, 7};
443 OrderedIndices indices{indices_vec.data(), 4, Indices::State::kNonmonotonic};
444 auto res = chain->OrderedIndexSearch(FilterOp::kIsNull, SqlValue(), indices);
445 ASSERT_EQ(res.start, 0u);
446 ASSERT_EQ(res.end, 2u);
447 }
448
TEST(StringStorage,OrderedIndexSearchIsNotNull)449 TEST(StringStorage, OrderedIndexSearchIsNotNull) {
450 std::vector<std::string> strings{"cheese", "pasta", "pizza",
451 "pierogi", "onion", "fries"};
452 std::vector<StringPool::Id> ids(3, StringPool::Id::Null());
453 StringPool pool;
454 for (const auto& string : strings) {
455 ids.push_back(pool.InternString(base::StringView(string)));
456 }
457 StringStorage storage(&pool, &ids);
458 auto chain = storage.MakeChain();
459
460 std::vector<uint32_t> indices_vec{0, 2, 5, 7};
461 OrderedIndices indices{indices_vec.data(), 4, Indices::State::kNonmonotonic};
462 auto res =
463 chain->OrderedIndexSearch(FilterOp::kIsNotNull, SqlValue(), indices);
464 ASSERT_EQ(res.start, 2u);
465 ASSERT_EQ(res.end, 4u);
466 }
467
TEST(StringStorage,StableSort)468 TEST(StringStorage, StableSort) {
469 std::vector<std::string> strings{"cheese", "pasta", "pizza",
470 "pierogi", "onion", "fries"};
471 std::vector<StringPool::Id> ids(3, StringPool::Id::Null());
472 StringPool pool;
473 for (const auto& string : strings) {
474 ids.push_back(pool.InternString(base::StringView(string)));
475 }
476 StringStorage storage(&pool, &ids);
477 auto chain = storage.MakeChain();
478 auto make_tokens = []() {
479 return std::vector{
480 Token{0, 0}, Token{1, 1}, Token{2, 2}, Token{3, 3}, Token{4, 4},
481 Token{5, 5}, Token{6, 6}, Token{7, 7}, Token{8, 8},
482 };
483 };
484 {
485 auto tokens = make_tokens();
486 chain->StableSort(tokens.data(), tokens.data() + tokens.size(),
487 SortDirection::kAscending);
488 ASSERT_THAT(utils::ExtractPayloadForTesting(tokens),
489 ElementsAre(0, 1, 2, 3, 8, 7, 4, 6, 5));
490 }
491 {
492 auto tokens = make_tokens();
493 chain->StableSort(tokens.data(), tokens.data() + tokens.size(),
494 SortDirection::kDescending);
495 ASSERT_THAT(utils::ExtractPayloadForTesting(tokens),
496 ElementsAre(5, 6, 4, 7, 8, 3, 0, 1, 2));
497 }
498 }
499
TEST(StringStorage,DistinctFromIndexVector)500 TEST(StringStorage, DistinctFromIndexVector) {
501 std::vector<std::string> strings{"cheese", "pasta", "cheese",
502 "fries", "pasta", "fries"};
503 std::vector<StringPool::Id> ids(2, StringPool::Id::Null());
504 StringPool pool;
505 for (const auto& string : strings) {
506 ids.push_back(pool.InternString(base::StringView(string)));
507 }
508 StringStorage storage(&pool, &ids);
509 auto chain = storage.MakeChain();
510
511 auto indices = Indices::CreateWithIndexPayloadForTesting(
512 {1, 0, 6, 3}, Indices::State::kNonmonotonic);
513 chain->Distinct(indices);
514 ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(0, 2));
515 }
516
517 } // namespace
518 } // namespace perfetto::trace_processor::column
519