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