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
17 #include "src/trace_processor/db/column/arrangement_overlay.h"
18
19 #include <array>
20 #include <cstdint>
21 #include <utility>
22 #include <vector>
23
24 #include "perfetto/trace_processor/basic_types.h"
25 #include "src/trace_processor/containers/bit_vector.h"
26 #include "src/trace_processor/db/column/data_layer.h"
27 #include "src/trace_processor/db/column/fake_storage.h"
28 #include "src/trace_processor/db/column/numeric_storage.h"
29 #include "src/trace_processor/db/column/types.h"
30 #include "src/trace_processor/db/column/utils.h"
31 #include "test/gtest_and_gmock.h"
32
33 namespace perfetto::trace_processor::column {
34 namespace {
35
36 using testing::ElementsAre;
37 using testing::IsEmpty;
38
39 using Indices = DataLayerChain::Indices;
40 using OrderedIndices = DataLayerChain::OrderedIndices;
41
TEST(ArrangementOverlay,SingleSearch)42 TEST(ArrangementOverlay, SingleSearch) {
43 std::vector<uint32_t> arrangement{1, 1, 2, 2, 3, 3, 4, 4, 1, 1};
44 auto fake = FakeStorageChain::SearchSubset(5, std::vector<uint32_t>{1, 2});
45 ArrangementOverlay storage(&arrangement, Indices::State::kNonmonotonic);
46 auto chain = storage.MakeChain(std::move(fake));
47
48 ASSERT_EQ(chain->SingleSearch(FilterOp::kGe, SqlValue::Long(0u), 8),
49 SingleSearchResult::kMatch);
50 ASSERT_EQ(chain->SingleSearch(FilterOp::kGe, SqlValue::Long(0u), 4),
51 SingleSearchResult::kNoMatch);
52 }
53
TEST(ArrangementOverlay,SearchAll)54 TEST(ArrangementOverlay, SearchAll) {
55 std::vector<uint32_t> arrangement{1, 1, 2, 2, 3, 3, 4, 4, 1, 1};
56 auto fake = FakeStorageChain::SearchAll(5);
57 ArrangementOverlay storage(&arrangement, Indices::State::kNonmonotonic);
58 auto chain = storage.MakeChain(std::move(fake));
59
60 auto res = chain->Search(FilterOp::kGe, SqlValue::Long(0u), Range(2, 4));
61 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(2u, 3u));
62 }
63
TEST(ArrangementOverlay,SearchNone)64 TEST(ArrangementOverlay, SearchNone) {
65 std::vector<uint32_t> arrangement{1, 1, 2, 2, 3, 3, 4, 4, 1, 1};
66 auto fake = FakeStorageChain::SearchNone(5);
67 ArrangementOverlay storage(&arrangement, Indices::State::kNonmonotonic);
68 auto chain = storage.MakeChain(std::move(fake));
69
70 auto res = chain->Search(FilterOp::kGe, SqlValue::Long(0u), Range(2, 4));
71 ASSERT_THAT(utils::ToIndexVectorForTests(res), IsEmpty());
72 }
73
TEST(ArrangementOverlay,DISABLED_SearchLimited)74 TEST(ArrangementOverlay, DISABLED_SearchLimited) {
75 std::vector<uint32_t> arrangement{1, 1, 2, 2, 3, 3, 4, 4, 1, 1};
76 auto fake = FakeStorageChain::SearchSubset(5, Range(4, 5));
77 ArrangementOverlay storage(&arrangement, Indices::State::kNonmonotonic);
78 auto chain = storage.MakeChain(std::move(fake));
79
80 auto res = chain->Search(FilterOp::kGe, SqlValue::Long(0u), Range(2, 7));
81 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(6u));
82 }
83
TEST(ArrangementOverlay,SearchBitVector)84 TEST(ArrangementOverlay, SearchBitVector) {
85 std::vector<uint32_t> arrangement{1, 1, 2, 2, 3, 3, 4, 4, 1, 1};
86 auto fake = FakeStorageChain::SearchSubset(
87 5, BitVector({false, true, false, true, false}));
88 ArrangementOverlay storage(&arrangement, Indices::State::kNonmonotonic);
89 auto chain = storage.MakeChain(std::move(fake));
90
91 // Table bv:
92 // 1, 1, 0, 0, 1, 1, 0, 0, 1, 1
93 auto res = chain->Search(FilterOp::kGe, SqlValue::Long(0u), Range(0, 10));
94 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 1, 4, 5, 8, 9));
95 }
96
TEST(ArrangementOverlay,IndexSearch)97 TEST(ArrangementOverlay, IndexSearch) {
98 std::vector<uint32_t> arrangement{1, 1, 2, 2, 3, 3, 4, 4, 1, 1};
99 auto fake = FakeStorageChain::SearchSubset(
100 5, BitVector({false, true, false, true, false}));
101 ArrangementOverlay storage(&arrangement, Indices::State::kNonmonotonic);
102 auto chain = storage.MakeChain(std::move(fake));
103
104 Indices indices = Indices::CreateWithIndexPayloadForTesting(
105 {7u, 1u, 3u}, Indices::State::kNonmonotonic);
106 chain->IndexSearch(FilterOp::kGe, SqlValue::Long(0u), indices);
107 ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(1u));
108 }
109
TEST(ArrangementOverlay,OrderingSearch)110 TEST(ArrangementOverlay, OrderingSearch) {
111 std::vector<uint32_t> numeric_data{0, 1, 2, 0, 1, 0};
112 NumericStorage<uint32_t> numeric(&numeric_data, ColumnType::kUint32, false);
113
114 std::vector<uint32_t> arrangement{0, 3, 5, 1, 4, 2};
115 ArrangementOverlay storage(&arrangement, Indices::State::kNonmonotonic);
116 auto chain = storage.MakeChain(numeric.MakeChain(),
117 DataLayer::ChainCreationArgs(true));
118
119 RangeOrBitVector res =
120 chain->Search(FilterOp::kGe, SqlValue::Long(1u), Range(0, 5));
121 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(3, 4));
122
123 res = chain->Search(FilterOp::kNe, SqlValue::Long(1u), Range(1, 6));
124 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(1, 2, 5));
125 }
126
TEST(ArrangementOverlay,StableSort)127 TEST(ArrangementOverlay, StableSort) {
128 std::vector<uint32_t> numeric_data{0, 1, 2, 3, 4};
129 NumericStorage<uint32_t> numeric(&numeric_data, ColumnType::kUint32, false);
130
131 std::vector<uint32_t> arrangement{0, 2, 4, 1, 3};
132 ArrangementOverlay storage(&arrangement, Indices::State::kNonmonotonic);
133 auto chain = storage.MakeChain(numeric.MakeChain());
134
135 std::vector tokens{
136 Token{0, 0}, Token{1, 1}, Token{2, 2}, Token{3, 3}, Token{4, 4},
137 };
138 chain->StableSort(tokens.data(), tokens.data() + tokens.size(),
139 SortDirection::kAscending);
140 ASSERT_THAT(utils::ExtractPayloadForTesting(tokens),
141 ElementsAre(0, 3, 1, 4, 2));
142 }
143
TEST(ArrangementOverlay,Distinct)144 TEST(ArrangementOverlay, Distinct) {
145 std::vector<uint32_t> numeric_data{10, 20, 10, 20, 30};
146 NumericStorage<uint32_t> numeric(&numeric_data, ColumnType::kUint32, false);
147
148 // 30, 30, 10, 20, 10, 20
149 std::vector<uint32_t> arrangement{4, 4, 0, 1, 2, 3};
150 ArrangementOverlay storage(&arrangement, Indices::State::kNonmonotonic);
151 auto chain = storage.MakeChain(numeric.MakeChain());
152
153 // 30, 30, 20, 20
154 auto indices = Indices::CreateWithIndexPayloadForTesting(
155 {0, 1, 3, 3}, Indices::State::kNonmonotonic);
156 chain->Distinct(indices);
157 ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(0, 2));
158 }
159
160 } // namespace
161 } // namespace perfetto::trace_processor::column
162