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 #ifndef SRC_TRACE_PROCESSOR_PERFETTO_SQL_INTRINSICS_FUNCTIONS_STRUCTURAL_TREE_PARTITION_H_
18 #define SRC_TRACE_PROCESSOR_PERFETTO_SQL_INTRINSICS_FUNCTIONS_STRUCTURAL_TREE_PARTITION_H_
19 
20 #include "src/trace_processor/containers/string_pool.h"
21 #include "src/trace_processor/sqlite/bindings/sqlite_aggregate_function.h"
22 
23 namespace perfetto::trace_processor {
24 
25 // An SQL aggregate-function which partitions a tree into a forest of trees
26 // based on a given grouping key (i.e. group) for each node.
27 //
28 // # Arguments:
29 //  1) |node_id|: The id of the node. Should be a non-null uint32.
30 //  2) |parent_node_ids|:  The id of the parent node in the tree. Should be a
31 //     possibly null uint32. Should be null iff it is the root of the tree.
32 //  3) |group|: The group of the node. Should be a non-null uint32 and dense
33 //     for performance reasons.
34 //
35 // # Returns:
36 //  A value table with the schema (id, parent_id, group) containing a forest of
37 //  trees created by partitioning the tree based on the value of |groups|.
38 //
39 //  Specifically, for each tree in the forest, all the node in the tree have the
40 //  same |group| and all ancestor and descendants of that node are precisely the
41 //  the same ancestors and descendants in the original tree which have the same
42 //  |group|.
43 //
44 // # Example
45 // ## Input
46 //   id | parent_id | group
47 //   ---+-----------+--------
48 //   1  | NULL      | 1
49 //   2  | 1         | 1
50 //   3  | 2         | 2
51 //   4  | 2         | 2
52 //   5  | 4         | 1
53 //   6  | 4         | 3
54 //   7  | 4         | 2
55 //
56 // Or as a graph:
57 //         1 (1)
58 //        /
59 //       2 (1)
60 //      /    |
61 //     3 (2) 4 (2)
62 //            |
63 //             5 (1)
64 //            /   |
65 //         6 (3)  7 (2)
66 //
67 // ## Possible Output (order of rows is implementation-defined)
68 //   id | parent_id | group
69 //   ---+-----------+-------
70 //   1  | NULL      | 1
71 //   2  | 1         | 1
72 //   3  | NULL      | 2
73 //   4  | NULL      | 2
74 //   5  | 2         | 1
75 //   6  | NULL      | 3
76 //   7  | 4         | 2
77 //
78 // Or as a forest:
79 //    1 (1)       3 (2)      4 (2)        6 (3)
80 //     |                      |
81 //    2 (1)                  7 (2)
82 //     |
83 //    5 (1)
84 //
85 // # Notes:
86 // - Exactly one input node must have |parent_id| NULL with that node acting
87 //   as the root of the tree.
88 // - Every node *must* have a valid parent id which appears somewhere in |ids|.
89 // - The ordering of output rows is not guaranteed and should not be relied
90 //   upon.
91 // - This function is not intended to be used directly from SQL: instead macros
92 //   exist in the standard library, wrapping it and making it user-friendly.
93 struct StructuralTreePartition
94     : public SqliteAggregateFunction<StructuralTreePartition> {
95   static constexpr char kName[] = "__intrinsic_structural_tree_partition";
96   static constexpr int kArgCount = 3;
97   using UserDataContext = StringPool;
98 
99   static void Step(sqlite3_context*, int argc, sqlite3_value** argv);
100   static void Final(sqlite3_context* ctx);
101 };
102 
103 }  // namespace perfetto::trace_processor
104 
105 #endif  // SRC_TRACE_PROCESSOR_PERFETTO_SQL_INTRINSICS_FUNCTIONS_STRUCTURAL_TREE_PARTITION_H_
106