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