1-- 2-- Copyright 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-- https://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 16INCLUDE PERFETTO MODULE graphs.search; 17 18-- It's very typical to filter the flow table on either incoming or outgoing slice ids. 19-- 20-- Ideally, this should be automatic and shouldn't require any additional imports, however we 21-- can't add it to prelude (because it is initialised before the trace is loaded and the indexes 22-- are not rebuilt when the new data is loaded), so the interested parties should remember to import 23-- this module. 24CREATE PERFETTO INDEX flow_in ON flow(slice_in); 25 26CREATE PERFETTO INDEX flow_out ON flow(slice_out); 27 28-- Computes the "reachable" set of slices from the |flows| table, starting from slice ids 29-- specified in |source_table|. This provides a more efficient result than with the in-built 30-- following_flow operator. 31CREATE PERFETTO MACRO _slice_following_flow( 32 -- A table/view/subquery corresponding to the nodes to start the reachability search. 33 -- This table must have a uint32 "id" column. 34 source_table TableOrSubquery 35) 36-- The returned table has the schema (root_node_id, node_id LONG, parent_node_id LONG). 37-- |root_node_id| is the id of the starting node under which this edge was encountered. 38-- |node_id| is the id of the node from the input graph and |parent_node_id| 39-- is the id of the node which was the first encountered predecessor in a DFS 40-- search of the graph. 41RETURNS TableOrSubquery AS 42( 43 SELECT 44 * 45 FROM graph_reachable_weight_bounded_dfs 46 !((SELECT slice_out AS source_node_id, slice_in AS dest_node_id, 0 AS edge_weight FROM flow), 47 ( 48 SELECT slice_out AS root_node_id, 1 AS root_target_weight 49 FROM flow 50 JOIN (SELECT id FROM $source_table) source 51 ON slice_out = source.id 52 ), 53 1) 54); 55