1#!/usr/bin/env python3 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 a 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 16from python.generators.diff_tests.testing import DataPath 17from python.generators.diff_tests.testing import Csv 18from python.generators.diff_tests.testing import DiffTestBlueprint 19from python.generators.diff_tests.testing import TestSuite 20 21 22class GraphSearchTests(TestSuite): 23 24 def test_empty_table(self): 25 return DiffTestBlueprint( 26 trace=DataPath('counters.json'), 27 query=""" 28 INCLUDE PERFETTO MODULE graphs.search; 29 30 WITH foo AS ( 31 SELECT 0 as source_node_id, 0 AS dest_node_id 32 WHERE FALSE 33 ) 34 SELECT * FROM graph_reachable_dfs!(foo, NULL) 35 """, 36 out=Csv(""" 37 "node_id","parent_node_id" 38 """)) 39 40 def test_one_node(self): 41 return DiffTestBlueprint( 42 trace=DataPath('counters.json'), 43 query=""" 44 INCLUDE PERFETTO MODULE graphs.search; 45 46 WITH foo AS ( 47 SELECT 5 AS source_node_id, 10 AS dest_node_id 48 UNION ALL 49 SELECT 10, 10 50 ) 51 SELECT * FROM graph_reachable_dfs!(foo, 5); 52 """, 53 out=Csv(""" 54 "node_id","parent_node_id" 55 5,"[NULL]" 56 10,5 57 """)) 58 59 def test_two_nodes(self): 60 return DiffTestBlueprint( 61 trace=DataPath('counters.json'), 62 query=""" 63 INCLUDE PERFETTO MODULE graphs.search; 64 65 CREATE PERFETTO TABLE foo AS 66 SELECT NULL AS source_node_id, NULL AS dest_node_id WHERE FALSE 67 UNION ALL 68 VALUES (10, 11) 69 UNION ALL 70 VALUES (0, 10); 71 72 SELECT * FROM graph_reachable_dfs!(foo, 0); 73 """, 74 out=Csv(""" 75 "node_id","parent_node_id" 76 0,"[NULL]" 77 10,0 78 11,10 79 """)) 80 81 def test_lengauer_tarjan_example(self): 82 return DiffTestBlueprint( 83 trace=DataPath('counters.json'), 84 query=""" 85 INCLUDE PERFETTO MODULE graphs.search; 86 87 CREATE PERFETTO TABLE foo AS 88 SELECT NULL AS source, NULL AS dest WHERE FALSE 89 UNION ALL 90 VALUES ('R', 'A'), ('R', 'B'), ('R', 'C'), ('A', 'D') 91 UNION ALL 92 VALUES ('B', 'A'), ('B', 'D'), ('B', 'E'), ('C', 'F') 93 UNION ALL 94 VALUES ('C', 'G'), ('D', 'L'), ('E', 'H'), ('F', 'I') 95 UNION ALL 96 VALUES ('G', 'I'), ('G', 'J'), ('H', 'E'), ('H', 'K') 97 UNION ALL 98 VALUES ('I', 'K'), ('J', 'I'), ('K', 'I'), ('K', 'R') 99 UNION ALL 100 VALUES ('L', 'H'); 101 102 WITH bar AS ( 103 SELECT 104 unicode(source) AS source_node_id, 105 unicode(dest) AS dest_node_id 106 FROM foo 107 ) 108 SELECT 109 char(node_id) AS node_id, 110 IIF( 111 parent_node_id IS NULL, 112 NULL, 113 char(parent_node_id) 114 ) AS parent_node_id 115 FROM graph_reachable_dfs!(bar, unicode('R')) 116 ORDER BY node_id; 117 """, 118 out=Csv(""" 119 "node_id","parent_node_id" 120 "A","R" 121 "B","R" 122 "C","R" 123 "D","A" 124 "E","H" 125 "F","C" 126 "G","C" 127 "H","L" 128 "I","K" 129 "J","G" 130 "K","H" 131 "L","D" 132 "R","[NULL]" 133 """)) 134 135 def test_next_sibling(self): 136 return DiffTestBlueprint( 137 trace=DataPath('counters.json'), 138 query=""" 139 INCLUDE PERFETTO MODULE graphs.search; 140 141 CREATE PERFETTO TABLE foo AS 142 SELECT 1 AS node_id, 0 AS node_parent_id, 1 AS sort_key 143 UNION ALL 144 SELECT 2 AS node_id, 1 AS node_parent_id, 2 AS sort_key 145 UNION ALL 146 SELECT 3 AS node_id, 1 AS node_parent_id, 1 AS sort_key; 147 148 SELECT * FROM graph_next_sibling!(foo); 149 """, 150 out=Csv(""" 151 "node_id","next_node_id" 152 1,"[NULL]" 153 3,2 154 2,"[NULL]" 155 """)) 156 157 def test_weight_bounded_dfs_floor(self): 158 return DiffTestBlueprint( 159 trace=DataPath('counters.json'), 160 query=""" 161 INCLUDE PERFETTO MODULE graphs.search; 162 163 CREATE PERFETTO TABLE foo AS 164 SELECT 0 AS source_node_id, 0 AS dest_node_id, 0 AS edge_weight 165 UNION ALL 166 VALUES (1, 2, 1) 167 UNION ALL 168 VALUES (1, 3, 1) 169 UNION ALL 170 VALUES (3, 4, 1) 171 UNION ALL 172 VALUES (3, 5, 0) 173 UNION ALL 174 VALUES (5, 6, 0); 175 176 CREATE PERFETTO TABLE roots AS 177 SELECT 0 AS root_node_id, 0 AS root_target_weight 178 UNION ALL 179 VALUES (1, 2) 180 UNION ALL 181 VALUES (3, 1) 182 UNION ALL 183 VALUES (2, 0); 184 185 SELECT * FROM graph_reachable_weight_bounded_dfs!(foo, roots, 1); 186 """, 187 out=Csv(""" 188 "root_node_id","node_id","parent_node_id" 189 0,0,"[NULL]" 190 1,1,"[NULL]" 191 1,2,1 192 1,3,1 193 1,4,3 194 3,3,"[NULL]" 195 3,4,3 196 3,5,3 197 3,6,5 198 2,2,"[NULL]" 199 """)) 200 201 def test_weight_bounded_dfs_ceiling(self): 202 return DiffTestBlueprint( 203 trace=DataPath('counters.json'), 204 query=""" 205 INCLUDE PERFETTO MODULE graphs.search; 206 207 CREATE PERFETTO TABLE foo AS 208 SELECT 0 AS source_node_id, 0 AS dest_node_id, 0 AS edge_weight 209 UNION ALL 210 VALUES (1, 2, 1) 211 UNION ALL 212 VALUES (1, 3, 1) 213 UNION ALL 214 VALUES (3, 4, 1) 215 UNION ALL 216 VALUES (3, 5, 0) 217 UNION ALL 218 VALUES (5, 6, 0); 219 220 CREATE PERFETTO TABLE roots AS 221 SELECT 0 AS root_node_id, 0 AS root_target_weight 222 UNION ALL 223 VALUES (1, 2) 224 UNION ALL 225 VALUES (3, 1) 226 UNION ALL 227 VALUES (2, 0); 228 229 SELECT * FROM graph_reachable_weight_bounded_dfs!(foo, roots, 0); 230 """, 231 out=Csv(""" 232 "root_node_id","node_id","parent_node_id" 233 0,0,"[NULL]" 234 1,1,"[NULL]" 235 1,2,1 236 1,3,1 237 3,3,"[NULL]" 238 3,4,3 239 3,5,3 240 3,6,5 241 2,2,"[NULL]" 242 """)) 243