1# Copyright (C) 2014 The Android Open Source Project
2#
3# Licensed under the Apache License, Version 2.0 (the "License");
4# you may not use this file except in compliance with the License.
5# You may obtain a copy of the License at
6#
7#   http://www.apache.org/licenses/LICENSE-2.0
8#
9# Unless required by applicable law or agreed to in writing, software
10# distributed under the License is distributed on an "AS IS" BASIS,
11# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12# See the License for the specific language governing permissions and
13# limitations under the License.
14
15from collections import namedtuple
16
17from common.immutables import ImmutableDict
18from common.logger import Logger
19from file_format.checker.struct import TestStatement
20from match.line import match_lines, evaluate_line
21
22MatchScope = namedtuple("MatchScope", ["start", "end"])
23MatchInfo = namedtuple("MatchInfo", ["scope", "variables"])
24
25
26class MatchFailedException(Exception):
27  def __init__(self, statement, line_no, variables):
28    self.statement = statement
29    self.line_no = line_no
30    self.variables = variables
31
32
33class BadStructureException(Exception):
34  def __init__(self, msg, line_no):
35    self.msg = msg
36    self.line_no = line_no
37
38
39class IfStack:
40  """
41  The purpose of this class is to keep track of which branch the cursor is in.
42  This will let us know if the line read by the cursor should be processed or not.
43  Furthermore, this class contains the methods to handle the CHECK-[IF, ELIF, ELSE, FI]
44  statements, and consequently update the stack with new information.
45
46  The following elements can appear on the stack:
47  - BRANCH_TAKEN: a branch is taken if its condition evaluates to true and
48    its parent branch was also previously taken.
49  - BRANCH_NOT_TAKEN_YET: the branch's parent was taken, but this branch wasn't as its
50    condition did not evaluate to true.
51  - BRANCH_NOT_TAKEN: a branch is not taken when its parent was either NotTaken or NotTakenYet.
52    It doesn't matter if the condition would evaluate to true, that's not even checked.
53
54  CHECK-IF is the only instruction that pushes a new element on the stack. CHECK-ELIF
55  and CHECK-ELSE will update the top of the stack to keep track of what's been seen.
56  That means that we can check if the line currently pointed to by the cursor should be
57  processed just by looking at the top of the stack.
58  CHECK-FI will pop the last element.
59
60  `BRANCH_TAKEN`, `BRANCH_NOT_TAKEN`, `BRANCH_NOT_TAKEN_YET` are implemented as positive integers.
61  Negated values of `BRANCH_TAKEN` and `BRANCH_NOT_TAKEN` may be appear; `-BRANCH_TAKEN` and
62  `-BRANCH_NOT_TAKEN` have the same meaning as `BRANCH_TAKEN` and `BRANCH_NOT_TAKEN`
63  (respectively), but they indicate that we went past the ELSE branch. Knowing that, we can
64  output a precise error message if the user creates a malformed branching structure.
65  """
66
67  BRANCH_TAKEN, BRANCH_NOT_TAKEN, BRANCH_NOT_TAKEN_YET = range(1, 4)
68
69  def __init__(self):
70    self.stack = []
71
72  def can_execute(self):
73    """
74    Returns true if we're not in any branch, or the branch we're
75    currently in was taken.
76    """
77    if self._is_empty():
78      return True
79    return abs(self._peek()) == IfStack.BRANCH_TAKEN
80
81  def handle(self, statement, variables):
82    """
83    This function is invoked if the cursor is pointing to a
84    CHECK-[IF, ELIF, ELSE, FI] line.
85    """
86    variant = statement.variant
87    if variant is TestStatement.Variant.IF:
88      self._if(statement, variables)
89    elif variant is TestStatement.Variant.ELIF:
90      self._elif(statement, variables)
91    elif variant is TestStatement.Variant.ELSE:
92      self._else(statement)
93    else:
94      assert variant is TestStatement.Variant.FI
95      self._fi(statement)
96
97  def eof(self):
98    """
99    The last line the cursor points to is always EOF.
100    """
101    if not self._is_empty():
102      raise BadStructureException("Missing CHECK-FI", -1)
103
104  def _is_empty(self):
105    return not self.stack
106
107  def _if(self, statement, variables):
108    if not self._is_empty() and abs(self._peek()) in [IfStack.BRANCH_NOT_TAKEN,
109                                                      IfStack.BRANCH_NOT_TAKEN_YET]:
110      self._push(IfStack.BRANCH_NOT_TAKEN)
111    elif evaluate_line(statement, variables):
112      self._push(IfStack.BRANCH_TAKEN)
113    else:
114      self._push(IfStack.BRANCH_NOT_TAKEN_YET)
115
116  def _elif(self, statement, variables):
117    if self._is_empty():
118      raise BadStructureException("CHECK-ELIF must be after CHECK-IF or CHECK-ELIF",
119                                  statement.line_no)
120    if self._peek() < 0:
121      raise BadStructureException("CHECK-ELIF cannot be after CHECK-ELSE", statement.line_no)
122    if self._peek() == IfStack.BRANCH_TAKEN:
123      self._set_last(IfStack.BRANCH_NOT_TAKEN)
124    elif self._peek() == IfStack.BRANCH_NOT_TAKEN_YET:
125      if evaluate_line(statement, variables):
126        self._set_last(IfStack.BRANCH_TAKEN)
127      # else, the CHECK-ELIF condition is False, so do nothing: the last element on the stack is
128      # already set to BRANCH_NOT_TAKEN_YET.
129    else:
130      assert self._peek() == IfStack.BRANCH_NOT_TAKEN
131
132  def _else(self, statement):
133    if self._is_empty():
134      raise BadStructureException("CHECK-ELSE must be after CHECK-IF or CHECK-ELIF",
135                                  statement.line_no)
136    if self._peek() < 0:
137      raise BadStructureException("Consecutive CHECK-ELSE statements", statement.line_no)
138    if self._peek() in [IfStack.BRANCH_TAKEN, IfStack.BRANCH_NOT_TAKEN]:
139      # Notice that we're setting -BRANCH_NOT_TAKEN rather that BRANCH_NOT_TAKEN as we went past the
140      # ELSE branch.
141      self._set_last(-IfStack.BRANCH_NOT_TAKEN)
142    else:
143      assert self._peek() == IfStack.BRANCH_NOT_TAKEN_YET
144      # Setting -BRANCH_TAKEN rather BRANCH_TAKEN for the same reason.
145      self._set_last(-IfStack.BRANCH_TAKEN)
146
147  def _fi(self, statement):
148    if self._is_empty():
149      raise BadStructureException("CHECK-FI does not have a matching CHECK-IF", statement.line_no)
150    self.stack.pop()
151
152  def _peek(self):
153    assert not self._is_empty()
154    return self.stack[-1]
155
156  def _push(self, element):
157    self.stack.append(element)
158
159  def _set_last(self, element):
160    self.stack[-1] = element
161
162
163def find_matching_line(statement, c1_pass, scope, variables, exclude_lines=[]):
164  """ Finds the first line in `c1_pass` which matches `statement`.
165
166  Scan only lines numbered between `scope.start` and `scope.end` and not on the
167  `excludeLines` list.
168
169  Returns the index of the `c1Pass` line matching the statement and variables
170  values after the match.
171
172  Raises MatchFailedException if no such `c1Pass` line can be found.
173  """
174  for i in range(scope.start, scope.end):
175    if i in exclude_lines:
176      continue
177    new_variables = match_lines(statement, c1_pass.body[i], variables)
178    if new_variables is not None:
179      return MatchInfo(MatchScope(i, i), new_variables)
180  raise MatchFailedException(statement, scope.start, variables)
181
182
183class ExecutionState(object):
184  def __init__(self, c1_pass, variables={}):
185    self.cursor = 0
186    self.c1_pass = c1_pass
187    self.c1_length = len(c1_pass.body)
188    self.variables = ImmutableDict(variables)
189    self.dag_queue = []
190    self.not_queue = []
191    self.if_stack = IfStack()
192    self.last_variant = None
193
194  def move_cursor(self, match):
195    assert self.cursor <= match.scope.end
196
197    # Handle any pending NOT statements before moving the cursor
198    self.handle_not_queue(MatchScope(self.cursor, match.scope.start))
199
200    self.cursor = match.scope.end + 1
201    self.variables = match.variables
202
203  def handle_dag_queue(self, scope):
204    """ Attempts to find matching `c1Pass` lines for a group of DAG statements.
205
206    Statements are matched in the list order and variable values propagated. Only
207    lines in `scope` are scanned and each line can only match one statement.
208
209    Returns the range of `c1Pass` lines covered by this group (min/max of matching
210    line numbers) and the variable values after the match of the last statement.
211
212    Raises MatchFailedException when a statement cannot be satisfied.
213    """
214    if not self.dag_queue:
215      return
216
217    matched_lines = []
218    variables = self.variables
219
220    for statement in self.dag_queue:
221      assert statement.variant == TestStatement.Variant.DAG
222      match = find_matching_line(statement, self.c1_pass, scope, variables, matched_lines)
223      variables = match.variables
224      assert match.scope.start == match.scope.end
225      assert match.scope.start not in matched_lines
226      matched_lines.append(match.scope.start)
227
228    match = MatchInfo(MatchScope(min(matched_lines), max(matched_lines)), variables)
229    self.dag_queue = []
230    self.move_cursor(match)
231
232  def handle_not_queue(self, scope):
233    """ Verifies that none of the given NOT statements matches a line inside
234        the given `scope` of `c1Pass` lines.
235
236    Raises MatchFailedException if a statement matches a line in the scope.
237    """
238    for statement in self.not_queue:
239      assert statement.variant == TestStatement.Variant.NOT
240      for i in range(scope.start, scope.end):
241        if match_lines(statement, self.c1_pass.body[i], self.variables) is not None:
242          raise MatchFailedException(statement, i, self.variables)
243    self.not_queue = []
244
245  def handle_eof(self):
246    """ EOF marker always moves the cursor to the end of the file."""
247    match = MatchInfo(MatchScope(self.c1_length, self.c1_length), None)
248    self.move_cursor(match)
249
250  def handle_in_order(self, statement):
251    """ Single in-order statement. Find the first line that matches and move
252        the cursor to the subsequent line.
253
254    Raises MatchFailedException if no such line can be found.
255    """
256    scope = MatchScope(self.cursor, self.c1_length)
257    match = find_matching_line(statement, self.c1_pass, scope, self.variables)
258    self.move_cursor(match)
259
260  def handle_next_line(self, statement):
261    """ Single next-line statement. Test if the current line matches and move
262        the cursor to the next line if it does.
263
264    Raises MatchFailedException if the current line does not match.
265    """
266    if self.last_variant not in [TestStatement.Variant.IN_ORDER, TestStatement.Variant.NEXT_LINE]:
267      raise BadStructureException("A next-line statement can only be placed "
268                                  "after an in-order statement or another next-line statement.",
269                                  statement.line_no)
270
271    scope = MatchScope(self.cursor, self.cursor + 1)
272    match = find_matching_line(statement, self.c1_pass, scope, self.variables)
273    self.move_cursor(match)
274
275  def handle_eval(self, statement):
276    """ Evaluates the statement in the current context.
277
278    Raises MatchFailedException if the expression evaluates to False.
279    """
280    if not evaluate_line(statement, self.variables):
281      raise MatchFailedException(statement, self.cursor, self.variables)
282
283  def handle(self, statement):
284    variant = None if statement is None else statement.variant
285
286    if variant in [TestStatement.Variant.IF,
287                   TestStatement.Variant.ELIF,
288                   TestStatement.Variant.ELSE,
289                   TestStatement.Variant.FI]:
290      self.if_stack.handle(statement, self.variables)
291      return
292
293    if variant is None:
294      self.if_stack.eof()
295
296    if not self.if_stack.can_execute():
297      return
298
299    # First non-DAG statement always triggers execution of any preceding
300    # DAG statements.
301    if variant is not TestStatement.Variant.DAG:
302      self.handle_dag_queue(MatchScope(self.cursor, self.c1_length))
303
304    if variant is None:
305      self.handle_eof()
306    elif variant is TestStatement.Variant.IN_ORDER:
307      self.handle_in_order(statement)
308    elif variant is TestStatement.Variant.NEXT_LINE:
309      self.handle_next_line(statement)
310    elif variant is TestStatement.Variant.DAG:
311      self.dag_queue.append(statement)
312    elif variant is TestStatement.Variant.NOT:
313      self.not_queue.append(statement)
314    else:
315      assert variant is TestStatement.Variant.EVAL
316      self.handle_eval(statement)
317
318    self.last_variant = variant
319
320
321def match_test_case(test_case, c1_pass, instruction_set_features):
322  """ Runs a test case against a C1visualizer graph dump.
323
324  Raises MatchFailedException when a statement cannot be satisfied.
325  """
326  assert test_case.name == c1_pass.name
327
328  initial_variables = {"ISA_FEATURES": instruction_set_features}
329  state = ExecutionState(c1_pass, initial_variables)
330  test_statements = test_case.statements + [None]
331  for statement in test_statements:
332    state.handle(statement)
333
334
335def match_files(checker_file, c1_file, target_arch, debuggable_mode, print_cfg):
336  for test_case in checker_file.test_cases:
337    if test_case.test_arch not in [None, target_arch]:
338      continue
339    if test_case.for_debuggable != debuggable_mode:
340      continue
341
342    # TODO: Currently does not handle multiple occurrences of the same group
343    # name, e.g. when a pass is run multiple times. It will always try to
344    # match a check group against the first output group of the same name.
345    c1_pass = c1_file.find_pass(test_case.name)
346    if c1_pass is None:
347      with open(c1_file.full_file_name) as cfg_file:
348        Logger.log("".join(cfg_file), Logger.Level.ERROR)
349      Logger.fail("Test case not found in the CFG file",
350                  c1_file.full_file_name, test_case.start_line_no, test_case.name)
351
352    Logger.start_test(test_case.name)
353    try:
354      match_test_case(test_case, c1_pass, c1_file.instruction_set_features)
355      Logger.test_passed()
356    except MatchFailedException as e:
357      line_no = c1_pass.start_line_no + e.line_no
358      if e.statement.variant == TestStatement.Variant.NOT:
359        msg = "NOT statement matched line {}"
360      else:
361        msg = "Statement could not be matched starting from line {}"
362      msg = msg.format(line_no)
363      if print_cfg:
364        with open(c1_file.full_file_name) as cfg_file:
365          Logger.log("".join(cfg_file), Logger.Level.ERROR)
366      Logger.test_failed(msg, e.statement, e.variables)
367