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