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