1 /*
2 * Copyright (C) 2024 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/functions/dfs.h"
18
19 #include <algorithm>
20 #include <cstddef>
21 #include <cstdint>
22 #include <memory>
23 #include <optional>
24 #include <vector>
25
26 #include "perfetto/base/logging.h"
27 #include "perfetto/public/compiler.h"
28 #include "src/trace_processor/perfetto_sql/intrinsics/functions/tables_py.h"
29 #include "src/trace_processor/sqlite/bindings/sqlite_aggregate_function.h"
30 #include "src/trace_processor/sqlite/bindings/sqlite_result.h"
31
32 namespace perfetto::trace_processor {
33 namespace tables {
34 DfsTable::~DfsTable() = default;
35 } // namespace tables
36
37 namespace {
38
39 using Destinations = std::vector<uint32_t>;
40
41 struct AggCtx : SqliteAggregateContext<AggCtx> {
42 std::vector<Destinations> source_to_destinations_map;
43 std::optional<uint32_t> start_id;
44 };
45
46 } // namespace
47
Step(sqlite3_context * ctx,int argc,sqlite3_value ** argv)48 void Dfs::Step(sqlite3_context* ctx, int argc, sqlite3_value** argv) {
49 if (argc != kArgCount) {
50 return sqlite::result::Error(ctx, "dfs: incorrect number of arguments");
51 }
52
53 auto& agg_ctx = AggCtx::GetOrCreateContextForStep(ctx);
54 auto source = static_cast<uint32_t>(sqlite3_value_int64(argv[0]));
55 auto dest = static_cast<uint32_t>(sqlite3_value_int64(argv[1]));
56
57 // For every source node, create a mapping to the destination nodes.
58 agg_ctx.source_to_destinations_map.resize(
59 std::max<size_t>(agg_ctx.source_to_destinations_map.size(),
60 std::max(source + 1, dest + 1)));
61 agg_ctx.source_to_destinations_map[source].push_back(dest);
62 if (PERFETTO_UNLIKELY(!agg_ctx.start_id)) {
63 agg_ctx.start_id = static_cast<uint32_t>(sqlite3_value_int64(argv[2]));
64 }
65 }
66
Final(sqlite3_context * ctx)67 void Dfs::Final(sqlite3_context* ctx) {
68 auto raw_agg_ctx = AggCtx::GetContextOrNullForFinal(ctx);
69 auto table = std::make_unique<tables::DfsTable>(GetUserData(ctx));
70 if (auto* agg_ctx = raw_agg_ctx.get(); agg_ctx) {
71 std::vector<uint8_t> seen(agg_ctx->source_to_destinations_map.size());
72 struct StackState {
73 uint32_t id;
74 std::optional<uint32_t> parent_id;
75 };
76
77 std::vector<StackState> stack{{*agg_ctx->start_id, std::nullopt}};
78 while (!stack.empty()) {
79 StackState state = stack.back();
80 stack.pop_back();
81
82 if (seen[state.id]) {
83 continue;
84 }
85 seen[state.id] = true;
86
87 tables::DfsTable::Row row;
88 row.node_id = state.id;
89 row.parent_node_id = state.parent_id;
90 table->Insert(row);
91
92 PERFETTO_DCHECK(state.id < agg_ctx->source_to_destinations_map.size());
93 const auto& children = agg_ctx->source_to_destinations_map[state.id];
94 for (auto it = children.rbegin(); it != children.rend(); ++it) {
95 stack.emplace_back(StackState{*it, state.id});
96 }
97 }
98 }
99 return sqlite::result::RawPointer(
100 ctx, table.release(), "TABLE",
101 [](void* ptr) { delete static_cast<tables::DfsTable*>(ptr); });
102 }
103
104 } // namespace perfetto::trace_processor
105