1 /*
2 * Copyright (C) 2020 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/prelude/table_functions/experimental_slice_layout.h"
18
19 #include <algorithm>
20
21 #include "src/trace_processor/containers/bit_vector.h"
22 #include "src/trace_processor/prelude/table_functions/tables_py.h"
23 #include "test/gtest_and_gmock.h"
24
25 namespace perfetto {
26 namespace trace_processor {
27 namespace {
28
29 constexpr uint32_t kColumn =
30 tables::ExperimentalSliceLayoutTable::ColumnIndex::filter_track_ids;
31
ToVis(const Table & table)32 std::string ToVis(const Table& table) {
33 const Column* layout_depth_column = table.GetColumnByName("layout_depth");
34 const Column* ts_column = table.GetColumnByName("ts");
35 const Column* dur_column = table.GetColumnByName("dur");
36 const Column* filter_track_ids_column =
37 table.GetColumnByName("filter_track_ids");
38
39 std::vector<std::string> lines;
40 for (uint32_t i = 0; i < table.row_count(); ++i) {
41 int64_t layout_depth = layout_depth_column->Get(i).long_value;
42 int64_t ts = ts_column->Get(i).long_value;
43 int64_t dur = dur_column->Get(i).long_value;
44 const char* filter_track_ids = filter_track_ids_column->Get(i).AsString();
45 if (std::string("") == filter_track_ids) {
46 continue;
47 }
48 for (int64_t j = 0; j < dur; ++j) {
49 size_t y = static_cast<size_t>(layout_depth);
50 size_t x = static_cast<size_t>(ts + j);
51 while (lines.size() <= y) {
52 lines.push_back("");
53 }
54 if (lines[y].size() <= x) {
55 lines[y].resize(x + 1, ' ');
56 }
57 lines[y][x] = '#';
58 }
59 }
60
61 std::string output = "";
62 output += "\n";
63 for (const std::string& line : lines) {
64 output += line;
65 output += "\n";
66 }
67 return output;
68 }
69
ExpectOutput(const Table & table,const std::string & expected)70 void ExpectOutput(const Table& table, const std::string& expected) {
71 const auto& actual = ToVis(table);
72 EXPECT_EQ(actual, expected)
73 << "Actual:" << actual << "\nExpected:" << expected;
74 }
75
Insert(tables::SliceTable * table,int64_t ts,int64_t dur,uint32_t track_id,StringId name,std::optional<tables::SliceTable::Id> parent_id)76 tables::SliceTable::Id Insert(tables::SliceTable* table,
77 int64_t ts,
78 int64_t dur,
79 uint32_t track_id,
80 StringId name,
81 std::optional<tables::SliceTable::Id> parent_id) {
82 tables::SliceTable::Row row;
83 row.ts = ts;
84 row.dur = dur;
85 row.depth = 0;
86 std::optional<tables::SliceTable::Id> id = parent_id;
87 while (id) {
88 row.depth++;
89 id = table->parent_id()[id.value().value];
90 }
91 row.track_id = tables::TrackTable::Id{track_id};
92 row.name = name;
93 row.parent_id = parent_id;
94 return table->Insert(row).id;
95 }
96
TEST(ExperimentalSliceLayoutTest,SingleRow)97 TEST(ExperimentalSliceLayoutTest, SingleRow) {
98 StringPool pool;
99 tables::SliceTable slice_table(&pool);
100 StringId name = pool.InternString("SingleRow");
101
102 Insert(&slice_table, 1 /*ts*/, 5 /*dur*/, 1 /*track_id*/, name,
103 std::nullopt /*parent*/);
104
105 ExperimentalSliceLayout gen(&pool, &slice_table);
106
107 std::unique_ptr<Table> table;
108 auto status = gen.ComputeTable(
109 {Constraint{kColumn, FilterOp::kEq, SqlValue::String("1")}}, {},
110 BitVector(), table);
111 EXPECT_TRUE(status.ok());
112 ExpectOutput(*table, R"(
113 #####
114 )");
115 }
116
TEST(ExperimentalSliceLayoutTest,DoubleRow)117 TEST(ExperimentalSliceLayoutTest, DoubleRow) {
118 StringPool pool;
119 tables::SliceTable slice_table(&pool);
120 StringId name = pool.InternString("SingleRow");
121
122 auto id = Insert(&slice_table, 1 /*ts*/, 5 /*dur*/, 1 /*track_id*/, name,
123 std::nullopt);
124 Insert(&slice_table, 1 /*ts*/, 5 /*dur*/, 1 /*track_id*/, name, id);
125
126 ExperimentalSliceLayout gen(&pool, &slice_table);
127
128 std::unique_ptr<Table> table;
129 auto status = gen.ComputeTable(
130 {Constraint{kColumn, FilterOp::kEq, SqlValue::String("1")}}, {},
131 BitVector(), table);
132 EXPECT_TRUE(status.ok());
133 ExpectOutput(*table, R"(
134 #####
135 #####
136 )");
137 }
138
TEST(ExperimentalSliceLayoutTest,MultipleRows)139 TEST(ExperimentalSliceLayoutTest, MultipleRows) {
140 StringPool pool;
141 tables::SliceTable slice_table(&pool);
142 StringId name = pool.InternString("MultipleRows");
143
144 auto a = Insert(&slice_table, 1 /*ts*/, 5 /*dur*/, 1 /*track_id*/, name,
145 std::nullopt);
146 auto b = Insert(&slice_table, 1 /*ts*/, 4 /*dur*/, 1 /*track_id*/, name, a);
147 auto c = Insert(&slice_table, 1 /*ts*/, 3 /*dur*/, 1 /*track_id*/, name, b);
148 auto d = Insert(&slice_table, 1 /*ts*/, 2 /*dur*/, 1 /*track_id*/, name, c);
149 auto e = Insert(&slice_table, 1 /*ts*/, 1 /*dur*/, 1 /*track_id*/, name, d);
150 base::ignore_result(e);
151
152 ExperimentalSliceLayout gen(&pool, &slice_table);
153
154 std::unique_ptr<Table> table;
155 auto status = gen.ComputeTable(
156 {Constraint{kColumn, FilterOp::kEq, SqlValue::String("1")}}, {},
157 BitVector(), table);
158 EXPECT_TRUE(status.ok());
159 ExpectOutput(*table, R"(
160 #####
161 ####
162 ###
163 ##
164 #
165 )");
166 }
167
TEST(ExperimentalSliceLayoutTest,MultipleTracks)168 TEST(ExperimentalSliceLayoutTest, MultipleTracks) {
169 StringPool pool;
170 tables::SliceTable slice_table(&pool);
171 StringId name1 = pool.InternString("Slice1");
172 StringId name2 = pool.InternString("Slice2");
173 StringId name3 = pool.InternString("Slice3");
174 StringId name4 = pool.InternString("Track4");
175
176 auto a = Insert(&slice_table, 1 /*ts*/, 4 /*dur*/, 1 /*track_id*/, name1,
177 std::nullopt);
178 auto b = Insert(&slice_table, 1 /*ts*/, 2 /*dur*/, 1 /*track_id*/, name2, a);
179 auto x = Insert(&slice_table, 4 /*ts*/, 4 /*dur*/, 2 /*track_id*/, name3,
180 std::nullopt);
181 auto y = Insert(&slice_table, 4 /*ts*/, 2 /*dur*/, 2 /*track_id*/, name4, x);
182 base::ignore_result(b);
183 base::ignore_result(y);
184
185 ExperimentalSliceLayout gen(&pool, &slice_table);
186
187 std::unique_ptr<Table> table;
188 auto status = gen.ComputeTable(
189 {Constraint{kColumn, FilterOp::kEq, SqlValue::String("1,2")}}, {},
190 BitVector(), table);
191 EXPECT_TRUE(status.ok());
192 ExpectOutput(*table, R"(
193 ####
194 ##
195 ####
196 ##
197 )");
198 }
199
TEST(ExperimentalSliceLayoutTest,MultipleTracksWithGap)200 TEST(ExperimentalSliceLayoutTest, MultipleTracksWithGap) {
201 StringPool pool;
202 tables::SliceTable slice_table(&pool);
203 StringId name1 = pool.InternString("Slice1");
204 StringId name2 = pool.InternString("Slice2");
205 StringId name3 = pool.InternString("Slice3");
206 StringId name4 = pool.InternString("Slice4");
207 StringId name5 = pool.InternString("Slice5");
208 StringId name6 = pool.InternString("Slice6");
209
210 auto a = Insert(&slice_table, 0 /*ts*/, 4 /*dur*/, 1 /*track_id*/, name1,
211 std::nullopt);
212 auto b = Insert(&slice_table, 0 /*ts*/, 2 /*dur*/, 1 /*track_id*/, name2, a);
213 auto p = Insert(&slice_table, 3 /*ts*/, 4 /*dur*/, 2 /*track_id*/, name3,
214 std::nullopt);
215 auto q = Insert(&slice_table, 3 /*ts*/, 2 /*dur*/, 2 /*track_id*/, name4, p);
216 auto x = Insert(&slice_table, 5 /*ts*/, 4 /*dur*/, 1 /*track_id*/, name5,
217 std::nullopt);
218 auto y = Insert(&slice_table, 5 /*ts*/, 2 /*dur*/, 1 /*track_id*/, name6, x);
219 base::ignore_result(b);
220 base::ignore_result(q);
221 base::ignore_result(y);
222
223 ExperimentalSliceLayout gen(&pool, &slice_table);
224
225 std::unique_ptr<Table> table;
226 auto status = gen.ComputeTable(
227 {Constraint{kColumn, FilterOp::kEq, SqlValue::String("1,2")}}, {},
228 BitVector(), table);
229 EXPECT_TRUE(status.ok());
230 ExpectOutput(*table, R"(
231 #### ####
232 ## ##
233 ####
234 ##
235 )");
236 }
237
TEST(ExperimentalSliceLayoutTest,PreviousGroupFullyNested)238 TEST(ExperimentalSliceLayoutTest, PreviousGroupFullyNested) {
239 StringPool pool;
240 tables::SliceTable slice_table(&pool);
241 StringId name = pool.InternString("Slice");
242
243 // This test ensures that our bounding box logic works when the bounding box
244 // of an earlier group is nested inside bounding box of a later group.
245 // In that case, we should still layout in a way which avoids overlaps.
246
247 // Group 1 exists just to create push group 2 down one row.
248 auto a = Insert(&slice_table, 0 /*ts*/, 1 /*dur*/, 1 /*track_id*/, name,
249 std::nullopt);
250 base::ignore_result(a);
251
252 // Group 2 has a depth of 2 so it theoretically "nests" inside a group of
253 // depth 4.
254 auto c = Insert(&slice_table, 0 /*ts*/, 10 /*dur*/, 2 /*track_id*/, name,
255 std::nullopt);
256 auto d = Insert(&slice_table, 0 /*ts*/, 9 /*dur*/, 2 /*track_id*/, name, c);
257 base::ignore_result(d);
258
259 // Group 3 has a depth of 4 so it could cause group 2 to "nest" if our
260 // layout algorithm did not work correctly.
261 auto p = Insert(&slice_table, 3 /*ts*/, 4 /*dur*/, 3 /*track_id*/, name,
262 std::nullopt);
263 auto q = Insert(&slice_table, 3 /*ts*/, 3 /*dur*/, 3 /*track_id*/, name, p);
264 auto r = Insert(&slice_table, 3 /*ts*/, 2 /*dur*/, 3 /*track_id*/, name, q);
265 auto s = Insert(&slice_table, 3 /*ts*/, 1 /*dur*/, 3 /*track_id*/, name, r);
266 base::ignore_result(s);
267
268 ExperimentalSliceLayout gen(&pool, &slice_table);
269
270 std::unique_ptr<Table> table;
271 auto status = gen.ComputeTable(
272 {Constraint{kColumn, FilterOp::kEq, SqlValue::String("1,2,3")}}, {},
273 BitVector(), table);
274 EXPECT_TRUE(status.ok());
275 ExpectOutput(*table, R"(
276 #
277 ##########
278 #########
279 ####
280 ###
281 ##
282 #
283 )");
284 }
285
TEST(ExperimentalSliceLayoutTest,FilterOutTracks)286 TEST(ExperimentalSliceLayoutTest, FilterOutTracks) {
287 StringPool pool;
288 tables::SliceTable slice_table(&pool);
289 StringId name1 = pool.InternString("Slice1");
290 StringId name2 = pool.InternString("Slice2");
291 StringId name3 = pool.InternString("Slice3");
292 StringId name4 = pool.InternString("Slice4");
293 StringId name5 = pool.InternString("Slice5");
294
295 auto a = Insert(&slice_table, 0 /*ts*/, 4 /*dur*/, 1 /*track_id*/, name1,
296 std::nullopt);
297 auto b = Insert(&slice_table, 0 /*ts*/, 2 /*dur*/, 1 /*track_id*/, name2, a);
298 auto p = Insert(&slice_table, 3 /*ts*/, 4 /*dur*/, 2 /*track_id*/, name3,
299 std::nullopt);
300 auto q = Insert(&slice_table, 3 /*ts*/, 2 /*dur*/, 2 /*track_id*/, name4, p);
301 // This slice should be ignored as it's not in the filter below:
302 Insert(&slice_table, 0 /*ts*/, 9 /*dur*/, 3 /*track_id*/, name5,
303 std::nullopt);
304 base::ignore_result(b);
305 base::ignore_result(q);
306
307 ExperimentalSliceLayout gen(&pool, &slice_table);
308 std::unique_ptr<Table> table;
309 auto status = gen.ComputeTable(
310 {Constraint{kColumn, FilterOp::kEq, SqlValue::String("1,2")}}, {},
311 BitVector(), table);
312 EXPECT_TRUE(status.ok());
313 ExpectOutput(*table, R"(
314 ####
315 ##
316 ####
317 ##
318 )");
319 }
320
321 } // namespace
322 } // namespace trace_processor
323 } // namespace perfetto
324