1# Copyright 2019 Google LLC 2# 3# Licensed under the Apache License, Version 2.0 (the "License"); 4# you may not use this file except in compliance with the License. 5# You may obtain a copy of the License at 6# 7# https://www.apache.org/licenses/LICENSE-2.0 8# 9# Unless required by applicable law or agreed to in writing, software 10# distributed under the License is distributed on an "AS IS" BASIS, 11# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12# See the License for the specific language governing permissions and 13# limitations under the License. 14 15"""Tests for dependency_checker.py.""" 16 17import unittest 18from compiler.front_end import dependency_checker 19from compiler.front_end import glue 20from compiler.util import error 21from compiler.util import test_util 22 23 24def _parse_snippet(emb_file): 25 ir, unused_debug_info, errors = glue.parse_emboss_file( 26 "m.emb", 27 test_util.dict_file_reader({"m.emb": emb_file}), 28 stop_before_step="find_dependency_cycles") 29 assert not errors 30 return ir 31 32 33def _find_dependencies_for_snippet(emb_file): 34 ir, unused_debug_info, errors = glue.parse_emboss_file( 35 "m.emb", 36 test_util.dict_file_reader({ 37 "m.emb": emb_file 38 }), 39 stop_before_step="set_dependency_order") 40 assert not errors, errors 41 return ir 42 43 44class DependencyCheckerTest(unittest.TestCase): 45 46 def test_error_on_simple_field_cycle(self): 47 ir = _parse_snippet("struct Foo:\n" 48 " 0 [+field2] UInt field1\n" 49 " 0 [+field1] UInt field2\n") 50 struct = ir.module[0].type[0].structure 51 self.assertEqual([[ 52 error.error("m.emb", struct.field[0].source_location, 53 "Dependency cycle\nfield1"), 54 error.note("m.emb", struct.field[1].source_location, "field2") 55 ]], dependency_checker.find_dependency_cycles(ir)) 56 57 def test_error_on_self_cycle(self): 58 ir = _parse_snippet("struct Foo:\n" 59 " 0 [+field1] UInt field1\n") 60 struct = ir.module[0].type[0].structure 61 self.assertEqual([[ 62 error.error("m.emb", struct.field[0].source_location, 63 "Dependency cycle\nfield1") 64 ]], dependency_checker.find_dependency_cycles(ir)) 65 66 def test_error_on_triple_field_cycle(self): 67 ir = _parse_snippet("struct Foo:\n" 68 " 0 [+field2] UInt field1\n" 69 " 0 [+field3] UInt field2\n" 70 " 0 [+field1] UInt field3\n") 71 struct = ir.module[0].type[0].structure 72 self.assertEqual([[ 73 error.error("m.emb", struct.field[0].source_location, 74 "Dependency cycle\nfield1"), 75 error.note("m.emb", struct.field[1].source_location, "field2"), 76 error.note("m.emb", struct.field[2].source_location, "field3"), 77 ]], dependency_checker.find_dependency_cycles(ir)) 78 79 def test_error_on_complex_field_cycle(self): 80 ir = _parse_snippet("struct Foo:\n" 81 " 0 [+field2] UInt field1\n" 82 " 0 [+field3+field4] UInt field2\n" 83 " 0 [+field1] UInt field3\n" 84 " 0 [+field2] UInt field4\n") 85 struct = ir.module[0].type[0].structure 86 self.assertEqual([[ 87 error.error("m.emb", struct.field[0].source_location, 88 "Dependency cycle\nfield1"), 89 error.note("m.emb", struct.field[1].source_location, "field2"), 90 error.note("m.emb", struct.field[2].source_location, "field3"), 91 error.note("m.emb", struct.field[3].source_location, "field4"), 92 ]], dependency_checker.find_dependency_cycles(ir)) 93 94 def test_error_on_simple_enum_value_cycle(self): 95 ir = _parse_snippet("enum Foo:\n" 96 " XX = YY\n" 97 " YY = XX\n") 98 enum = ir.module[0].type[0].enumeration 99 self.assertEqual([[ 100 error.error("m.emb", enum.value[0].source_location, 101 "Dependency cycle\nXX"), 102 error.note("m.emb", enum.value[1].source_location, "YY") 103 ]], dependency_checker.find_dependency_cycles(ir)) 104 105 def test_no_error_on_no_cycle(self): 106 ir = _parse_snippet("enum Foo:\n" 107 " XX = 0\n" 108 " YY = XX\n") 109 self.assertEqual([], dependency_checker.find_dependency_cycles(ir)) 110 111 def test_error_on_cycle_nested(self): 112 ir = _parse_snippet("struct Foo:\n" 113 " struct Bar:\n" 114 " 0 [+field2] UInt field1\n" 115 " 0 [+field1] UInt field2\n" 116 " 0 [+1] UInt field\n") 117 struct = ir.module[0].type[0].subtype[0].structure 118 self.assertEqual([[ 119 error.error("m.emb", struct.field[0].source_location, 120 "Dependency cycle\nfield1"), 121 error.note("m.emb", struct.field[1].source_location, "field2") 122 ]], dependency_checker.find_dependency_cycles(ir)) 123 124 def test_error_on_import_cycle(self): 125 ir, unused_debug_info, errors = glue.parse_emboss_file( 126 "m.emb", 127 test_util.dict_file_reader({"m.emb": 'import "n.emb" as n\n', 128 "n.emb": 'import "m.emb" as m\n'}), 129 stop_before_step="find_dependency_cycles") 130 assert not errors 131 self.assertEqual([[ 132 error.error("m.emb", ir.module[0].source_location, 133 "Import dependency cycle\nm.emb"), 134 error.note("n.emb", ir.module[2].source_location, "n.emb") 135 ]], dependency_checker.find_dependency_cycles(ir)) 136 137 def test_error_on_import_cycle_and_field_cycle(self): 138 ir, unused_debug_info, errors = glue.parse_emboss_file( 139 "m.emb", 140 test_util.dict_file_reader({"m.emb": 'import "n.emb" as n\n' 141 "struct Foo:\n" 142 " 0 [+field1] UInt field1\n", 143 "n.emb": 'import "m.emb" as m\n'}), 144 stop_before_step="find_dependency_cycles") 145 assert not errors 146 struct = ir.module[0].type[0].structure 147 self.assertEqual([[ 148 error.error("m.emb", ir.module[0].source_location, 149 "Import dependency cycle\nm.emb"), 150 error.note("n.emb", ir.module[2].source_location, "n.emb") 151 ], [ 152 error.error("m.emb", struct.field[0].source_location, 153 "Dependency cycle\nfield1") 154 ]], dependency_checker.find_dependency_cycles(ir)) 155 156 def test_error_on_field_existence_self_cycle(self): 157 ir = _parse_snippet("struct Foo:\n" 158 " if x == 1:\n" 159 " 0 [+1] UInt x\n") 160 struct = ir.module[0].type[0].structure 161 self.assertEqual([[ 162 error.error("m.emb", struct.field[0].source_location, 163 "Dependency cycle\nx") 164 ]], dependency_checker.find_dependency_cycles(ir)) 165 166 def test_error_on_field_existence_cycle(self): 167 ir = _parse_snippet("struct Foo:\n" 168 " if y == 1:\n" 169 " 0 [+1] UInt x\n" 170 " if x == 0:\n" 171 " 1 [+1] UInt y\n") 172 struct = ir.module[0].type[0].structure 173 self.assertEqual([[ 174 error.error("m.emb", struct.field[0].source_location, 175 "Dependency cycle\nx"), 176 error.note("m.emb", struct.field[1].source_location, "y") 177 ]], dependency_checker.find_dependency_cycles(ir)) 178 179 def test_error_on_virtual_field_cycle(self): 180 ir = _parse_snippet("struct Foo:\n" 181 " let x = y\n" 182 " let y = x\n") 183 struct = ir.module[0].type[0].structure 184 self.assertEqual([[ 185 error.error("m.emb", struct.field[0].source_location, 186 "Dependency cycle\nx"), 187 error.note("m.emb", struct.field[1].source_location, "y") 188 ]], dependency_checker.find_dependency_cycles(ir)) 189 190 def test_error_on_virtual_non_virtual_field_cycle(self): 191 ir = _parse_snippet("struct Foo:\n" 192 " let x = y\n" 193 " x [+4] UInt y\n") 194 struct = ir.module[0].type[0].structure 195 self.assertEqual([[ 196 error.error("m.emb", struct.field[0].source_location, 197 "Dependency cycle\nx"), 198 error.note("m.emb", struct.field[1].source_location, "y") 199 ]], dependency_checker.find_dependency_cycles(ir)) 200 201 def test_error_on_non_virtual_virtual_field_cycle(self): 202 ir = _parse_snippet("struct Foo:\n" 203 " y [+4] UInt x\n" 204 " let y = x\n") 205 struct = ir.module[0].type[0].structure 206 self.assertEqual([[ 207 error.error("m.emb", struct.field[0].source_location, 208 "Dependency cycle\nx"), 209 error.note("m.emb", struct.field[1].source_location, "y") 210 ]], dependency_checker.find_dependency_cycles(ir)) 211 212 def test_error_on_cycle_involving_subfield(self): 213 ir = _parse_snippet("struct Bar:\n" 214 " foo_b.x [+4] Foo foo_a\n" 215 " foo_a.x [+4] Foo foo_b\n" 216 "struct Foo:\n" 217 " 0 [+4] UInt x\n") 218 struct = ir.module[0].type[0].structure 219 self.assertEqual([[ 220 error.error("m.emb", struct.field[0].source_location, 221 "Dependency cycle\nfoo_a"), 222 error.note("m.emb", struct.field[1].source_location, "foo_b") 223 ]], dependency_checker.find_dependency_cycles(ir)) 224 225 def test_dependency_ordering_with_no_dependencies(self): 226 ir = _find_dependencies_for_snippet("struct Foo:\n" 227 " 0 [+4] UInt a\n" 228 " 4 [+4] UInt b\n") 229 self.assertEqual([], dependency_checker.set_dependency_order(ir)) 230 struct = ir.module[0].type[0].structure 231 self.assertEqual([0, 1], struct.fields_in_dependency_order[:2]) 232 233 def test_dependency_ordering_with_dependency_in_order(self): 234 ir = _find_dependencies_for_snippet("struct Foo:\n" 235 " 0 [+4] UInt a\n" 236 " a [+4] UInt b\n") 237 self.assertEqual([], dependency_checker.set_dependency_order(ir)) 238 struct = ir.module[0].type[0].structure 239 self.assertEqual([0, 1], struct.fields_in_dependency_order[:2]) 240 241 def test_dependency_ordering_with_dependency_in_reverse_order(self): 242 ir = _find_dependencies_for_snippet("struct Foo:\n" 243 " b [+4] UInt a\n" 244 " 0 [+4] UInt b\n") 245 self.assertEqual([], dependency_checker.set_dependency_order(ir)) 246 struct = ir.module[0].type[0].structure 247 self.assertEqual([1, 0], struct.fields_in_dependency_order[:2]) 248 249 def test_dependency_ordering_with_extra_fields(self): 250 ir = _find_dependencies_for_snippet("struct Foo:\n" 251 " d [+4] UInt a\n" 252 " 4 [+4] UInt b\n" 253 " 8 [+4] UInt c\n" 254 " 12 [+4] UInt d\n") 255 self.assertEqual([], dependency_checker.set_dependency_order(ir)) 256 struct = ir.module[0].type[0].structure 257 self.assertEqual([1, 2, 3, 0], struct.fields_in_dependency_order[:4]) 258 259 def test_dependency_ordering_scrambled(self): 260 ir = _find_dependencies_for_snippet("struct Foo:\n" 261 " d [+4] UInt a\n" 262 " c [+4] UInt b\n" 263 " a [+4] UInt c\n" 264 " 12 [+4] UInt d\n") 265 self.assertEqual([], dependency_checker.set_dependency_order(ir)) 266 struct = ir.module[0].type[0].structure 267 self.assertEqual([3, 0, 2, 1], struct.fields_in_dependency_order[:4]) 268 269 def test_dependency_ordering_multiple_dependents(self): 270 ir = _find_dependencies_for_snippet("struct Foo:\n" 271 " d [+4] UInt a\n" 272 " d [+4] UInt b\n" 273 " d [+4] UInt c\n" 274 " 12 [+4] UInt d\n") 275 self.assertEqual([], dependency_checker.set_dependency_order(ir)) 276 struct = ir.module[0].type[0].structure 277 self.assertEqual([3, 0, 1, 2], struct.fields_in_dependency_order[:4]) 278 279 def test_dependency_ordering_multiple_dependencies(self): 280 ir = _find_dependencies_for_snippet("struct Foo:\n" 281 " b+c [+4] UInt a\n" 282 " 4 [+4] UInt b\n" 283 " 8 [+4] UInt c\n" 284 " a [+4] UInt d\n") 285 self.assertEqual([], dependency_checker.set_dependency_order(ir)) 286 struct = ir.module[0].type[0].structure 287 self.assertEqual([1, 2, 0, 3], struct.fields_in_dependency_order[:4]) 288 289 def test_dependency_ordering_with_parameter(self): 290 ir = _find_dependencies_for_snippet("struct Foo:\n" 291 " 0 [+1] Bar(x) b\n" 292 " 1 [+1] UInt x\n" 293 "struct Bar(x: UInt:8):\n" 294 " x [+1] UInt y\n") 295 self.assertEqual([], dependency_checker.set_dependency_order(ir)) 296 struct = ir.module[0].type[0].structure 297 self.assertEqual([1, 0], struct.fields_in_dependency_order[:2]) 298 299 def test_dependency_ordering_with_local_parameter(self): 300 ir = _find_dependencies_for_snippet("struct Foo(x: Int:13):\n" 301 " 0 [+x] Int b\n") 302 self.assertEqual([], dependency_checker.set_dependency_order(ir)) 303 struct = ir.module[0].type[0].structure 304 self.assertEqual([0], struct.fields_in_dependency_order[:1]) 305 306 307if __name__ == "__main__": 308 unittest.main() 309