555 lines · python
1# DExTer : Debugging Experience Tester2# ~~~~~~ ~ ~~ ~ ~~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-exception7"""Parse a DExTer command. In particular, ensure that only a very limited8subset of Python is allowed, in order to prevent the possibility of unsafe9Python code being embedded within DExTer commands.10"""11 12import os13import unittest14from copy import copy15from pathlib import PurePath16from collections import defaultdict, OrderedDict, namedtuple17 18from dex.utils.Exceptions import CommandParseError, NonFloatValueInCommand19 20from dex.command.CommandBase import CommandBase21from dex.command.commands.DexCommandLine import DexCommandLine22from dex.command.commands.DexDeclareFile import DexDeclareFile23from dex.command.commands.DexDeclareAddress import DexDeclareAddress24from dex.command.commands.DexExpectProgramState import DexExpectProgramState25from dex.command.commands.DexExpectStepKind import DexExpectStepKind26from dex.command.commands.DexExpectStepOrder import DexExpectStepOrder27from dex.command.commands.DexExpectWatchType import DexExpectWatchType28from dex.command.commands.DexExpectWatchValue import DexExpectWatchValue29from dex.command.commands.DexExpectWatchBase import (30 AddressExpression,31 DexExpectWatchBase,32)33from dex.command.commands.DexLabel import DexLabel34from dex.command.commands.DexLimitSteps import DexLimitSteps35from dex.command.commands.DexFinishTest import DexFinishTest36from dex.command.commands.DexUnreachable import DexUnreachable37from dex.command.commands.DexWatch import DexWatch38from dex.command.commands.DexStepFunction import DexStepFunction39from dex.command.commands.DexContinue import DexContinue40from dex.utils import Timer41from dex.utils.Exceptions import CommandParseError, DebuggerException42 43 44def _get_valid_commands():45 """Return all top level DExTer test commands.46 47 Returns:48 { name (str): command (class) }49 """50 return {51 DexCommandLine.get_name(): DexCommandLine,52 DexDeclareAddress.get_name(): DexDeclareAddress,53 DexDeclareFile.get_name(): DexDeclareFile,54 DexExpectProgramState.get_name(): DexExpectProgramState,55 DexExpectStepKind.get_name(): DexExpectStepKind,56 DexExpectStepOrder.get_name(): DexExpectStepOrder,57 DexExpectWatchType.get_name(): DexExpectWatchType,58 DexExpectWatchValue.get_name(): DexExpectWatchValue,59 DexLabel.get_name(): DexLabel,60 DexLimitSteps.get_name(): DexLimitSteps,61 DexFinishTest.get_name(): DexFinishTest,62 DexUnreachable.get_name(): DexUnreachable,63 DexWatch.get_name(): DexWatch,64 DexStepFunction.get_name(): DexStepFunction,65 DexContinue.get_name(): DexContinue,66 }67 68 69def _get_command_name(command_raw: str) -> str:70 """Return command name by splitting up DExTer command contained in71 command_raw on the first opening paranthesis and further stripping72 any potential leading or trailing whitespace.73 """74 return command_raw.split("(", 1)[0].rstrip()75 76 77def _merge_subcommands(command_name: str, valid_commands: dict) -> dict:78 """Merge valid_commands and command_name's subcommands into a new dict.79 80 Returns:81 { name (str): command (class) }82 """83 subcommands = valid_commands[command_name].get_subcommands()84 if subcommands:85 return {**valid_commands, **subcommands}86 return valid_commands87 88 89def _build_command(90 command_type, labels, addresses, raw_text: str, path, lineno: str91) -> CommandBase:92 """Build a command object from raw text.93 94 This function will call eval().95 96 Raises:97 Any exception that eval() can raise.98 99 Returns:100 A dexter command object.101 """102 103 def label_to_line(label_name: str) -> int:104 line = labels.get(label_name, None)105 if line is not None:106 return line107 raise format_unresolved_label_err(label_name, raw_text, path.base, lineno)108 109 def get_address_object(address_name: str, offset: int = 0):110 if address_name not in addresses:111 raise format_undeclared_address_err(112 address_name, raw_text, path.base, lineno113 )114 return AddressExpression(address_name, offset)115 116 valid_commands = _merge_subcommands(117 command_type.get_name(),118 {119 "ref": label_to_line,120 "address": get_address_object,121 command_type.get_name(): command_type,122 },123 )124 125 # pylint: disable=eval-used126 command = eval(raw_text, valid_commands)127 # pylint: enable=eval-used128 command.raw_text = raw_text129 command.path = path.declared130 command.lineno = lineno131 return command132 133 134def _search_line_for_cmd_start(line: str, start: int, valid_commands: dict) -> int:135 r"""Scan `line` for a string matching any key in `valid_commands`.136 137 Start searching from `start`.138 Commands escaped with `\` (E.g. `\DexLabel('a')`) are ignored.139 140 Returns:141 int: the index of the first character of the matching string in `line`142 or -1 if no command is found.143 """144 for command in valid_commands:145 idx = line.find(command, start)146 if idx != -1:147 # Ignore escaped '\' commands.148 if idx > 0 and line[idx - 1] == "\\":149 continue150 return idx151 return -1152 153 154def _search_line_for_cmd_end(line: str, start: int, paren_balance: int) -> (int, int):155 """Find the end of a command by looking for balanced parentheses.156 157 Args:158 line: String to scan.159 start: Index into `line` to start looking.160 paren_balance(int): paren_balance after previous call.161 162 Note:163 On the first call `start` should point at the opening parenthesis and164 `paren_balance` should be set to 0. Subsequent calls should pass in the165 returned `paren_balance`.166 167 Returns:168 ( end, paren_balance )169 Where end is 1 + the index of the last char in the command or, if the170 parentheses are not balanced, the end of the line.171 172 paren_balance will be 0 when the parentheses are balanced.173 """174 for end in range(start, len(line)):175 ch = line[end]176 if ch == "(":177 paren_balance += 1178 elif ch == ")":179 paren_balance -= 1180 if paren_balance == 0:181 break182 end += 1183 return (end, paren_balance)184 185 186class TextPoint:187 def __init__(self, line, char):188 self.line = line189 self.char = char190 191 def get_lineno(self):192 return self.line + 1193 194 def get_column(self):195 return self.char + 1196 197 198def format_unresolved_label_err(199 label: str, src: str, filename: str, lineno200) -> CommandParseError:201 err = CommandParseError()202 err.src = src203 err.caret = "" # Don't bother trying to point to the bad label.204 err.filename = filename205 err.lineno = lineno206 err.info = f"Unresolved label: '{label}'"207 return err208 209 210def format_undeclared_address_err(211 address: str, src: str, filename: str, lineno212) -> CommandParseError:213 err = CommandParseError()214 err.src = src215 err.caret = "" # Don't bother trying to point to the bad address.216 err.filename = filename217 err.lineno = lineno218 err.info = f"Undeclared address: '{address}'"219 return err220 221 222def format_parse_err(223 msg: str, path: str, lines: list, point: TextPoint224) -> CommandParseError:225 err = CommandParseError()226 err.filename = path227 err.src = lines[point.line].rstrip()228 err.lineno = point.get_lineno()229 err.info = msg230 err.caret = "{}<r>^</>".format(" " * (point.char))231 return err232 233 234def skip_horizontal_whitespace(line, point):235 for idx, char in enumerate(line[point.char :]):236 if char not in " \t":237 point.char += idx238 return239 240 241def add_line_label(labels, label, cmd_path, cmd_lineno):242 # Enforce unique line labels.243 if label.eval() in labels:244 err = CommandParseError()245 err.info = f"Found duplicate line label: '{label.eval()}'"246 err.lineno = cmd_lineno247 err.filename = cmd_path248 err.src = label.raw_text249 # Don't both trying to point to it since we're only printing the raw250 # command, which isn't much text.251 err.caret = ""252 raise err253 labels[label.eval()] = label.get_line()254 255 256def add_address(addresses, address, cmd_path, cmd_lineno):257 # Enforce unique address variables.258 address_name = address.get_address_name()259 if address_name in addresses:260 err = CommandParseError()261 err.info = f"Found duplicate address: '{address_name}'"262 err.lineno = cmd_lineno263 err.filename = cmd_path264 err.src = address.raw_text265 # Don't both trying to point to it since we're only printing the raw266 # command, which isn't much text.267 err.caret = ""268 raise err269 addresses.append(address_name)270 271 272def _find_all_commands_in_file(path, file_lines, valid_commands, source_root_dir):273 labels = {} # dict of {name: line}.274 addresses = [] # list of addresses.275 address_resolutions = {}276 CmdPath = namedtuple("cmd_path", "base declared")277 cmd_path = CmdPath(path, path)278 declared_files = set()279 commands = defaultdict(dict)280 paren_balance = 0281 region_start = TextPoint(0, 0)282 283 for region_start.line in range(len(file_lines)):284 line = file_lines[region_start.line]285 region_start.char = 0286 287 # Search this line till we find no more commands.288 while True:289 # If parens are currently balanced we can look for a new command.290 if paren_balance == 0:291 region_start.char = _search_line_for_cmd_start(292 line, region_start.char, valid_commands293 )294 if region_start.char == -1:295 break # Read next line.296 297 command_name = _get_command_name(line[region_start.char :])298 cmd_point = copy(region_start)299 cmd_text_list = [command_name]300 301 region_start.char += len(302 command_name303 ) # Start searching for parens after cmd.304 skip_horizontal_whitespace(line, region_start)305 if region_start.char >= len(line) or line[region_start.char] != "(":306 raise format_parse_err(307 "Missing open parenthesis", path, file_lines, region_start308 )309 310 end, paren_balance = _search_line_for_cmd_end(311 line, region_start.char, paren_balance312 )313 # Add this text blob to the command.314 cmd_text_list.append(line[region_start.char : end])315 # Move parse ptr to end of line or parens.316 region_start.char = end317 318 # If the parens are unbalanced start reading the next line in an attempt319 # to find the end of the command.320 if paren_balance != 0:321 break # Read next line.322 323 # Parens are balanced, we have a full command to evaluate.324 raw_text = "".join(cmd_text_list)325 try:326 command = _build_command(327 valid_commands[command_name],328 labels,329 addresses,330 raw_text,331 cmd_path,332 cmd_point.get_lineno(),333 )334 except SyntaxError as e:335 # This err should point to the problem line.336 err_point = copy(cmd_point)337 # To e the command start is the absolute start, so use as offset.338 err_point.line += e.lineno - 1 # e.lineno is a position, not index.339 err_point.char += e.offset - 1 # e.offset is a position, not index.340 raise format_parse_err(e.msg, path, file_lines, err_point)341 except TypeError as e:342 # This err should always point to the end of the command name.343 err_point = copy(cmd_point)344 err_point.char += len(command_name)345 raise format_parse_err(str(e), path, file_lines, err_point)346 except NonFloatValueInCommand as e:347 err_point = copy(cmd_point)348 err_point.char += len(command_name)349 raise format_parse_err(str(e), path, file_lines, err_point)350 else:351 if type(command) is DexLabel:352 add_line_label(labels, command, path, cmd_point.get_lineno())353 elif type(command) is DexDeclareAddress:354 add_address(addresses, command, path, cmd_point.get_lineno())355 elif type(command) is DexDeclareFile:356 declared_path = command.declared_file357 if not os.path.isabs(declared_path):358 source_dir = (359 source_root_dir360 if source_root_dir361 else os.path.dirname(path)362 )363 declared_path = os.path.join(source_dir, declared_path)364 cmd_path = CmdPath(cmd_path.base, str(PurePath(declared_path)))365 declared_files.add(cmd_path.declared)366 elif type(command) is DexCommandLine and "DexCommandLine" in commands:367 msg = "More than one DexCommandLine in file"368 raise format_parse_err(msg, path, file_lines, err_point)369 370 assert (path, cmd_point) not in commands[command_name], (371 command_name,372 commands[command_name],373 )374 commands[command_name][path, cmd_point] = command375 376 if paren_balance != 0:377 # This err should always point to the end of the command name.378 err_point = copy(cmd_point)379 err_point.char += len(command_name)380 msg = "Unbalanced parenthesis starting here"381 raise format_parse_err(msg, path, file_lines, err_point)382 return dict(commands), declared_files383 384 385def _find_all_commands(test_files, source_root_dir):386 commands = defaultdict(dict)387 valid_commands = _get_valid_commands()388 new_source_files = set()389 for test_file in test_files:390 with open(test_file) as fp:391 lines = fp.readlines()392 file_commands, declared_files = _find_all_commands_in_file(393 test_file, lines, valid_commands, source_root_dir394 )395 for command_name in file_commands:396 commands[command_name].update(file_commands[command_name])397 new_source_files |= declared_files398 399 return dict(commands), new_source_files400 401 402def get_command_infos(test_files, source_root_dir):403 with Timer("parsing commands"):404 try:405 commands, new_source_files = _find_all_commands(test_files, source_root_dir)406 command_infos = OrderedDict()407 for command_type in commands:408 for command in commands[command_type].values():409 if command_type not in command_infos:410 command_infos[command_type] = []411 command_infos[command_type].append(command)412 return OrderedDict(command_infos), new_source_files413 except CommandParseError as e:414 msg = "parser error: <d>{}({}):</> {}\n{}\n{}\n".format(415 e.filename, e.lineno, e.info, e.src, e.caret416 )417 raise DebuggerException(msg)418 419 420class TestParseCommand(unittest.TestCase):421 class MockCmd(CommandBase):422 """A mock DExTer command for testing parsing.423 424 Args:425 value (str): Unique name for this instance.426 """427 428 def __init__(self, *args):429 self.value = args[0]430 431 def get_name():432 return __class__.__name__433 434 def eval(this):435 pass436 437 def __init__(self, *args):438 super().__init__(*args)439 440 self.valid_commands = {441 TestParseCommand.MockCmd.get_name(): TestParseCommand.MockCmd442 }443 444 def _find_all_commands_in_lines(self, lines):445 """Use DExTer parsing methods to find all the mock commands in lines.446 447 Returns:448 { cmd_name: { (path, line): command_obj } }449 """450 cmds, declared_files = _find_all_commands_in_file(451 __file__, lines, self.valid_commands, None452 )453 return cmds454 455 def _find_all_mock_values_in_lines(self, lines):456 """Use DExTer parsing methods to find all mock command values in lines.457 458 Returns:459 values (list(str)): MockCmd values found in lines.460 """461 cmds = self._find_all_commands_in_lines(lines)462 mocks = cmds.get(TestParseCommand.MockCmd.get_name(), None)463 return [v.value for v in mocks.values()] if mocks else []464 465 def test_parse_inline(self):466 """Commands can be embedded in other text."""467 468 lines = [469 'MockCmd("START") Lorem ipsum dolor sit amet, consectetur\n',470 'adipiscing elit, MockCmd("EMBEDDED") sed doeiusmod tempor,\n',471 "incididunt ut labore et dolore magna aliqua.\n",472 ]473 474 values = self._find_all_mock_values_in_lines(lines)475 476 self.assertTrue("START" in values)477 self.assertTrue("EMBEDDED" in values)478 479 def test_parse_multi_line_comment(self):480 """Multi-line commands can embed comments."""481 482 lines = [483 "Lorem ipsum dolor sit amet, consectetur\n",484 "adipiscing elit, sed doeiusmod tempor,\n",485 "incididunt ut labore et MockCmd(\n",486 ' "WITH_COMMENT" # THIS IS A COMMENT\n',487 ") dolore magna aliqua. Ut enim ad minim\n",488 ]489 490 values = self._find_all_mock_values_in_lines(lines)491 492 self.assertTrue("WITH_COMMENT" in values)493 494 def test_parse_empty(self):495 """Empty files are silently ignored."""496 497 lines = []498 values = self._find_all_mock_values_in_lines(lines)499 self.assertTrue(len(values) == 0)500 501 def test_parse_bad_whitespace(self):502 """Throw exception when parsing badly formed whitespace."""503 lines = [504 "MockCmd\n",505 '("XFAIL_CMD_LF_PAREN")\n',506 ]507 508 with self.assertRaises(CommandParseError):509 values = self._find_all_mock_values_in_lines(lines)510 511 def test_parse_good_whitespace(self):512 """Try to emulate python whitespace rules"""513 514 lines = [515 'MockCmd("NONE")\n',516 'MockCmd ("SPACE")\n',517 'MockCmd\t\t("TABS")\n',518 'MockCmd( "ARG_SPACE" )\n',519 'MockCmd(\t\t"ARG_TABS"\t\t)\n',520 "MockCmd(\n",521 '"CMD_PAREN_LF")\n',522 ]523 524 values = self._find_all_mock_values_in_lines(lines)525 526 self.assertTrue("NONE" in values)527 self.assertTrue("SPACE" in values)528 self.assertTrue("TABS" in values)529 self.assertTrue("ARG_SPACE" in values)530 self.assertTrue("ARG_TABS" in values)531 self.assertTrue("CMD_PAREN_LF" in values)532 533 def test_parse_share_line(self):534 """More than one command can appear on one line."""535 536 lines = [537 'MockCmd("START") MockCmd("CONSECUTIVE") words '538 'MockCmd("EMBEDDED") more words\n'539 ]540 541 values = self._find_all_mock_values_in_lines(lines)542 543 self.assertTrue("START" in values)544 self.assertTrue("CONSECUTIVE" in values)545 self.assertTrue("EMBEDDED" in values)546 547 def test_parse_escaped(self):548 """Escaped commands are ignored."""549 550 lines = ['words \\MockCmd("IGNORED") words words words\n']551 552 values = self._find_all_mock_values_in_lines(lines)553 554 self.assertFalse("IGNORED" in values)555