1# DExTer : Debugging Experience Tester 2# ~~~~~~ ~ ~~ ~ ~~ 3# 4# Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 5# See https://llvm.org/LICENSE.txt for license information. 6# SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 7"""Parse a DExTer command. In particular, ensure that only a very limited 8subset of Python is allowed, in order to prevent the possibility of unsafe 9Python code being embedded within DExTer commands. 10""" 11 12import os 13import unittest 14from copy import copy 15from pathlib import PurePath 16from collections import defaultdict, OrderedDict 17 18from dex.utils.Exceptions import CommandParseError 19 20from dex.command.CommandBase import CommandBase 21from dex.command.commands.DexDeclareFile import DexDeclareFile 22from dex.command.commands.DexExpectProgramState import DexExpectProgramState 23from dex.command.commands.DexExpectStepKind import DexExpectStepKind 24from dex.command.commands.DexExpectStepOrder import DexExpectStepOrder 25from dex.command.commands.DexExpectWatchType import DexExpectWatchType 26from dex.command.commands.DexExpectWatchValue import DexExpectWatchValue 27from dex.command.commands.DexLabel import DexLabel 28from dex.command.commands.DexLimitSteps import DexLimitSteps 29from dex.command.commands.DexFinishTest import DexFinishTest 30from dex.command.commands.DexUnreachable import DexUnreachable 31from dex.command.commands.DexWatch import DexWatch 32from dex.utils import Timer 33from dex.utils.Exceptions import CommandParseError, DebuggerException 34 35def _get_valid_commands(): 36 """Return all top level DExTer test commands. 37 38 Returns: 39 { name (str): command (class) } 40 """ 41 return { 42 DexDeclareFile.get_name() : DexDeclareFile, 43 DexExpectProgramState.get_name() : DexExpectProgramState, 44 DexExpectStepKind.get_name() : DexExpectStepKind, 45 DexExpectStepOrder.get_name() : DexExpectStepOrder, 46 DexExpectWatchType.get_name() : DexExpectWatchType, 47 DexExpectWatchValue.get_name() : DexExpectWatchValue, 48 DexLabel.get_name() : DexLabel, 49 DexLimitSteps.get_name() : DexLimitSteps, 50 DexFinishTest.get_name() : DexFinishTest, 51 DexUnreachable.get_name() : DexUnreachable, 52 DexWatch.get_name() : DexWatch 53 } 54 55 56def _get_command_name(command_raw: str) -> str: 57 """Return command name by splitting up DExTer command contained in 58 command_raw on the first opening paranthesis and further stripping 59 any potential leading or trailing whitespace. 60 """ 61 return command_raw.split('(', 1)[0].rstrip() 62 63 64def _merge_subcommands(command_name: str, valid_commands: dict) -> dict: 65 """Merge valid_commands and command_name's subcommands into a new dict. 66 67 Returns: 68 { name (str): command (class) } 69 """ 70 subcommands = valid_commands[command_name].get_subcommands() 71 if subcommands: 72 return { **valid_commands, **subcommands } 73 return valid_commands 74 75 76def _build_command(command_type, labels, raw_text: str, path: str, lineno: str) -> CommandBase: 77 """Build a command object from raw text. 78 79 This function will call eval(). 80 81 Raises: 82 Any exception that eval() can raise. 83 84 Returns: 85 A dexter command object. 86 """ 87 def label_to_line(label_name: str) -> int: 88 line = labels.get(label_name, None) 89 if line != None: 90 return line 91 raise format_unresolved_label_err(label_name, raw_text, path, lineno) 92 93 valid_commands = _merge_subcommands( 94 command_type.get_name(), { 95 'ref': label_to_line, 96 command_type.get_name(): command_type, 97 }) 98 99 # pylint: disable=eval-used 100 command = eval(raw_text, valid_commands) 101 # pylint: enable=eval-used 102 command.raw_text = raw_text 103 command.path = path 104 command.lineno = lineno 105 return command 106 107 108def _search_line_for_cmd_start(line: str, start: int, valid_commands: dict) -> int: 109 """Scan `line` for a string matching any key in `valid_commands`. 110 111 Start searching from `start`. 112 Commands escaped with `\` (E.g. `\DexLabel('a')`) are ignored. 113 114 Returns: 115 int: the index of the first character of the matching string in `line` 116 or -1 if no command is found. 117 """ 118 for command in valid_commands: 119 idx = line.find(command, start) 120 if idx != -1: 121 # Ignore escaped '\' commands. 122 if idx > 0 and line[idx - 1] == '\\': 123 continue 124 return idx 125 return -1 126 127 128def _search_line_for_cmd_end(line: str, start: int, paren_balance: int) -> (int, int): 129 """Find the end of a command by looking for balanced parentheses. 130 131 Args: 132 line: String to scan. 133 start: Index into `line` to start looking. 134 paren_balance(int): paren_balance after previous call. 135 136 Note: 137 On the first call `start` should point at the opening parenthesis and 138 `paren_balance` should be set to 0. Subsequent calls should pass in the 139 returned `paren_balance`. 140 141 Returns: 142 ( end, paren_balance ) 143 Where end is 1 + the index of the last char in the command or, if the 144 parentheses are not balanced, the end of the line. 145 146 paren_balance will be 0 when the parentheses are balanced. 147 """ 148 for end in range(start, len(line)): 149 ch = line[end] 150 if ch == '(': 151 paren_balance += 1 152 elif ch == ')': 153 paren_balance -=1 154 if paren_balance == 0: 155 break 156 end += 1 157 return (end, paren_balance) 158 159 160class TextPoint(): 161 def __init__(self, line, char): 162 self.line = line 163 self.char = char 164 165 def get_lineno(self): 166 return self.line + 1 167 168 def get_column(self): 169 return self.char + 1 170 171 172def format_unresolved_label_err(label: str, src: str, filename: str, lineno) -> CommandParseError: 173 err = CommandParseError() 174 err.src = src 175 err.caret = '' # Don't bother trying to point to the bad label. 176 err.filename = filename 177 err.lineno = lineno 178 err.info = f'Unresolved label: \'{label}\'' 179 return err 180 181 182def format_parse_err(msg: str, path: str, lines: list, point: TextPoint) -> CommandParseError: 183 err = CommandParseError() 184 err.filename = path 185 err.src = lines[point.line].rstrip() 186 err.lineno = point.get_lineno() 187 err.info = msg 188 err.caret = '{}<r>^</>'.format(' ' * (point.char)) 189 return err 190 191 192def skip_horizontal_whitespace(line, point): 193 for idx, char in enumerate(line[point.char:]): 194 if char not in ' \t': 195 point.char += idx 196 return 197 198 199def add_line_label(labels, label, cmd_path, cmd_lineno): 200 # Enforce unique line labels. 201 if label.eval() in labels: 202 err = CommandParseError() 203 err.info = f'Found duplicate line label: \'{label.eval()}\'' 204 err.lineno = cmd_lineno 205 err.filename = cmd_path 206 err.src = label.raw_text 207 # Don't both trying to point to it since we're only printing the raw 208 # command, which isn't much text. 209 err.caret = '' 210 raise err 211 labels[label.eval()] = label.get_line() 212 213 214def _find_all_commands_in_file(path, file_lines, valid_commands, source_root_dir): 215 labels = {} # dict of {name: line}. 216 cmd_path = path 217 declared_files = set() 218 commands = defaultdict(dict) 219 paren_balance = 0 220 region_start = TextPoint(0, 0) 221 222 for region_start.line in range(len(file_lines)): 223 line = file_lines[region_start.line] 224 region_start.char = 0 225 226 # Search this line till we find no more commands. 227 while True: 228 # If parens are currently balanced we can look for a new command. 229 if paren_balance == 0: 230 region_start.char = _search_line_for_cmd_start(line, region_start.char, valid_commands) 231 if region_start.char == -1: 232 break # Read next line. 233 234 command_name = _get_command_name(line[region_start.char:]) 235 cmd_point = copy(region_start) 236 cmd_text_list = [command_name] 237 238 region_start.char += len(command_name) # Start searching for parens after cmd. 239 skip_horizontal_whitespace(line, region_start) 240 if region_start.char >= len(line) or line[region_start.char] != '(': 241 raise format_parse_err( 242 "Missing open parenthesis", path, file_lines, region_start) 243 244 end, paren_balance = _search_line_for_cmd_end(line, region_start.char, paren_balance) 245 # Add this text blob to the command. 246 cmd_text_list.append(line[region_start.char:end]) 247 # Move parse ptr to end of line or parens. 248 region_start.char = end 249 250 # If the parens are unbalanced start reading the next line in an attempt 251 # to find the end of the command. 252 if paren_balance != 0: 253 break # Read next line. 254 255 # Parens are balanced, we have a full command to evaluate. 256 raw_text = "".join(cmd_text_list) 257 try: 258 command = _build_command( 259 valid_commands[command_name], 260 labels, 261 raw_text, 262 cmd_path, 263 cmd_point.get_lineno(), 264 ) 265 except SyntaxError as e: 266 # This err should point to the problem line. 267 err_point = copy(cmd_point) 268 # To e the command start is the absolute start, so use as offset. 269 err_point.line += e.lineno - 1 # e.lineno is a position, not index. 270 err_point.char += e.offset - 1 # e.offset is a position, not index. 271 raise format_parse_err(e.msg, path, file_lines, err_point) 272 except TypeError as e: 273 # This err should always point to the end of the command name. 274 err_point = copy(cmd_point) 275 err_point.char += len(command_name) 276 raise format_parse_err(str(e), path, file_lines, err_point) 277 else: 278 if type(command) is DexLabel: 279 add_line_label(labels, command, path, cmd_point.get_lineno()) 280 elif type(command) is DexDeclareFile: 281 cmd_path = command.declared_file 282 if not os.path.isabs(cmd_path): 283 source_dir = (source_root_dir if source_root_dir else 284 os.path.dirname(path)) 285 cmd_path = os.path.join(source_dir, cmd_path) 286 # TODO: keep stored paths as PurePaths for 'longer'. 287 cmd_path = str(PurePath(cmd_path)) 288 declared_files.add(cmd_path) 289 assert (path, cmd_point) not in commands[command_name], ( 290 command_name, commands[command_name]) 291 commands[command_name][path, cmd_point] = command 292 293 if paren_balance != 0: 294 # This err should always point to the end of the command name. 295 err_point = copy(cmd_point) 296 err_point.char += len(command_name) 297 msg = "Unbalanced parenthesis starting here" 298 raise format_parse_err(msg, path, file_lines, err_point) 299 return dict(commands), declared_files 300 301def _find_all_commands(test_files, source_root_dir): 302 commands = defaultdict(dict) 303 valid_commands = _get_valid_commands() 304 new_source_files = set() 305 for test_file in test_files: 306 with open(test_file) as fp: 307 lines = fp.readlines() 308 file_commands, declared_files = _find_all_commands_in_file( 309 test_file, lines, valid_commands, source_root_dir) 310 for command_name in file_commands: 311 commands[command_name].update(file_commands[command_name]) 312 new_source_files |= declared_files 313 314 return dict(commands), new_source_files 315 316def get_command_infos(test_files, source_root_dir): 317 with Timer('parsing commands'): 318 try: 319 commands, new_source_files = _find_all_commands(test_files, source_root_dir) 320 command_infos = OrderedDict() 321 for command_type in commands: 322 for command in commands[command_type].values(): 323 if command_type not in command_infos: 324 command_infos[command_type] = [] 325 command_infos[command_type].append(command) 326 return OrderedDict(command_infos), new_source_files 327 except CommandParseError as e: 328 msg = 'parser error: <d>{}({}):</> {}\n{}\n{}\n'.format( 329 e.filename, e.lineno, e.info, e.src, e.caret) 330 raise DebuggerException(msg) 331 332class TestParseCommand(unittest.TestCase): 333 class MockCmd(CommandBase): 334 """A mock DExTer command for testing parsing. 335 336 Args: 337 value (str): Unique name for this instance. 338 """ 339 340 def __init__(self, *args): 341 self.value = args[0] 342 343 def get_name(): 344 return __class__.__name__ 345 346 def eval(this): 347 pass 348 349 350 def __init__(self, *args): 351 super().__init__(*args) 352 353 self.valid_commands = { 354 TestParseCommand.MockCmd.get_name() : TestParseCommand.MockCmd 355 } 356 357 358 def _find_all_commands_in_lines(self, lines): 359 """Use DExTer parsing methods to find all the mock commands in lines. 360 361 Returns: 362 { cmd_name: { (path, line): command_obj } } 363 """ 364 cmds, declared_files = _find_all_commands_in_file(__file__, lines, self.valid_commands, None) 365 return cmds 366 367 368 def _find_all_mock_values_in_lines(self, lines): 369 """Use DExTer parsing methods to find all mock command values in lines. 370 371 Returns: 372 values (list(str)): MockCmd values found in lines. 373 """ 374 cmds = self._find_all_commands_in_lines(lines) 375 mocks = cmds.get(TestParseCommand.MockCmd.get_name(), None) 376 return [v.value for v in mocks.values()] if mocks else [] 377 378 379 def test_parse_inline(self): 380 """Commands can be embedded in other text.""" 381 382 lines = [ 383 'MockCmd("START") Lorem ipsum dolor sit amet, consectetur\n', 384 'adipiscing elit, MockCmd("EMBEDDED") sed doeiusmod tempor,\n', 385 'incididunt ut labore et dolore magna aliqua.\n' 386 ] 387 388 values = self._find_all_mock_values_in_lines(lines) 389 390 self.assertTrue('START' in values) 391 self.assertTrue('EMBEDDED' in values) 392 393 394 def test_parse_multi_line_comment(self): 395 """Multi-line commands can embed comments.""" 396 397 lines = [ 398 'Lorem ipsum dolor sit amet, consectetur\n', 399 'adipiscing elit, sed doeiusmod tempor,\n', 400 'incididunt ut labore et MockCmd(\n', 401 ' "WITH_COMMENT" # THIS IS A COMMENT\n', 402 ') dolore magna aliqua. Ut enim ad minim\n', 403 ] 404 405 values = self._find_all_mock_values_in_lines(lines) 406 407 self.assertTrue('WITH_COMMENT' in values) 408 409 def test_parse_empty(self): 410 """Empty files are silently ignored.""" 411 412 lines = [] 413 values = self._find_all_mock_values_in_lines(lines) 414 self.assertTrue(len(values) == 0) 415 416 def test_parse_bad_whitespace(self): 417 """Throw exception when parsing badly formed whitespace.""" 418 lines = [ 419 'MockCmd\n', 420 '("XFAIL_CMD_LF_PAREN")\n', 421 ] 422 423 with self.assertRaises(CommandParseError): 424 values = self._find_all_mock_values_in_lines(lines) 425 426 def test_parse_good_whitespace(self): 427 """Try to emulate python whitespace rules""" 428 429 lines = [ 430 'MockCmd("NONE")\n', 431 'MockCmd ("SPACE")\n', 432 'MockCmd\t\t("TABS")\n', 433 'MockCmd( "ARG_SPACE" )\n', 434 'MockCmd(\t\t"ARG_TABS"\t\t)\n', 435 'MockCmd(\n', 436 '"CMD_PAREN_LF")\n', 437 ] 438 439 values = self._find_all_mock_values_in_lines(lines) 440 441 self.assertTrue('NONE' in values) 442 self.assertTrue('SPACE' in values) 443 self.assertTrue('TABS' in values) 444 self.assertTrue('ARG_SPACE' in values) 445 self.assertTrue('ARG_TABS' in values) 446 self.assertTrue('CMD_PAREN_LF' in values) 447 448 449 def test_parse_share_line(self): 450 """More than one command can appear on one line.""" 451 452 lines = [ 453 'MockCmd("START") MockCmd("CONSECUTIVE") words ' 454 'MockCmd("EMBEDDED") more words\n' 455 ] 456 457 values = self._find_all_mock_values_in_lines(lines) 458 459 self.assertTrue('START' in values) 460 self.assertTrue('CONSECUTIVE' in values) 461 self.assertTrue('EMBEDDED' in values) 462 463 464 def test_parse_escaped(self): 465 """Escaped commands are ignored.""" 466 467 lines = [ 468 'words \MockCmd("IGNORED") words words words\n' 469 ] 470 471 values = self._find_all_mock_values_in_lines(lines) 472 473 self.assertFalse('IGNORED' in values) 474