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
16from common.immutables                import ImmutableDict
17from common.logger                    import Logger
18from file_format.c1visualizer.struct  import C1visualizerFile, C1visualizerPass
19from file_format.checker.struct       import CheckerFile, TestCase, TestStatement
20from match.line                       import MatchLines, EvaluateLine
21
22MatchScope = namedtuple("MatchScope", ["start", "end"])
23MatchInfo = namedtuple("MatchInfo", ["scope", "variables"])
24
25class MatchFailedException(Exception):
26  def __init__(self, statement, lineNo, variables):
27    self.statement = statement
28    self.lineNo = lineNo
29    self.variables = variables
30
31class BadStructureException(Exception):
32  def __init__(self, msg, lineNo):
33    self.msg = msg
34    self.lineNo = lineNo
35
36class IfStack:
37  """
38  The purpose of this class is to keep track of which branch the cursor is in.
39  This will let us know if the line read by the cursor should be processed or not.
40  Furthermore, this class contains the methods to handle the CHECK-[IF, ELIF, ELSE, FI]
41  statements, and consequently update the stack with new information.
42
43  The following elements can appear on the stack:
44  - BranchTaken: a branch is taken if its condition evaluates to true and
45    its parent branch was also previously taken.
46  - BranchNotTakenYet: the branch's parent was taken, but this branch wasn't as its
47    condition did not evaluate to true.
48  - BranchNotTaken: a branch is not taken when its parent was either NotTaken or NotTakenYet.
49    It doesn't matter if the condition would evaluate to true, that's not even checked.
50
51  CHECK-IF is the only instruction that pushes a new element on the stack. CHECK-ELIF
52  and CHECK-ELSE will update the top of the stack to keep track of what's been seen.
53  That means that we can check if the line currently pointed to by the cursor should be
54  processed just by looking at the top of the stack.
55  CHECK-FI will pop the last element.
56
57  `BranchTaken`, `BranchNotTaken`, `BranchNotTakenYet` are implemented as positive integers.
58  Negated values of `BranchTaken` and `BranchNotTaken` may be appear; `-BranchTaken` and
59  `-BranchNotTaken` have the same meaning as `BranchTaken` and `BranchNotTaken`
60  (respectively), but they indicate that we went past the ELSE branch. Knowing that, we can
61  output a precise error message if the user creates a malformed branching structure.
62  """
63
64  BranchTaken, BranchNotTaken, BranchNotTakenYet = range(1, 4)
65
66  def __init__(self):
67    self.stack = []
68
69  def CanExecute(self):
70    """
71    Returns true if we're not in any branch, or the branch we're
72    currently in was taken.
73    """
74    if self.__isEmpty():
75      return True
76    return abs(self.__peek()) == IfStack.BranchTaken
77
78  def Handle(self, statement, variables):
79    """
80    This function is invoked if the cursor is pointing to a
81    CHECK-[IF, ELIF, ELSE, FI] line.
82    """
83    variant = statement.variant
84    if variant is TestStatement.Variant.If:
85      self.__if(statement, variables)
86    elif variant is TestStatement.Variant.Elif:
87      self.__elif(statement, variables)
88    elif variant is TestStatement.Variant.Else:
89      self.__else(statement)
90    else:
91      assert variant is TestStatement.Variant.Fi
92      self.__fi(statement)
93
94  def Eof(self):
95    """
96    The last line the cursor points to is always EOF.
97    """
98    if not self.__isEmpty():
99      raise BadStructureException("Missing CHECK-FI", -1)
100
101  def __isEmpty(self):
102    return len(self.stack) == 0
103
104  def __if(self, statement, variables):
105    if not self.__isEmpty() and abs(self.__peek()) in [ IfStack.BranchNotTaken,
106                                                        IfStack.BranchNotTakenYet ]:
107      self.__push(IfStack.BranchNotTaken)
108    elif EvaluateLine(statement, variables):
109      self.__push(IfStack.BranchTaken)
110    else:
111      self.__push(IfStack.BranchNotTakenYet)
112
113  def __elif(self, statement, variables):
114    if self.__isEmpty():
115      raise BadStructureException("CHECK-ELIF must be after CHECK-IF or CHECK-ELIF",
116                                  statement.lineNo)
117    if self.__peek() < 0:
118      raise BadStructureException("CHECK-ELIF cannot be after CHECK-ELSE", statement.lineNo)
119    if self.__peek() == IfStack.BranchTaken:
120      self.__setLast(IfStack.BranchNotTaken)
121    elif self.__peek() == IfStack.BranchNotTakenYet:
122      if EvaluateLine(statement, variables):
123        self.__setLast(IfStack.BranchTaken)
124      # else, the CHECK-ELIF condition is False, so do nothing: the last element on the stack is
125      # already set to BranchNotTakenYet.
126    else:
127      assert self.__peek() == IfStack.BranchNotTaken
128
129  def __else(self, statement):
130    if self.__isEmpty():
131      raise BadStructureException("CHECK-ELSE must be after CHECK-IF or CHECK-ELIF",
132                                  statement.lineNo)
133    if self.__peek() < 0:
134      raise BadStructureException("Consecutive CHECK-ELSE statements", statement.lineNo)
135    if self.__peek() in [ IfStack.BranchTaken, IfStack.BranchNotTaken ]:
136      # Notice that we're setting -BranchNotTaken rather that BranchNotTaken as we went past the
137      # ELSE branch.
138      self.__setLast(-IfStack.BranchNotTaken)
139    else:
140      assert self.__peek() == IfStack.BranchNotTakenYet
141      # Setting -BranchTaken rather BranchTaken for the same reason.
142      self.__setLast(-IfStack.BranchTaken)
143
144  def __fi(self, statement):
145    if self.__isEmpty():
146      raise BadStructureException("CHECK-FI does not have a matching CHECK-IF", statement.lineNo)
147    self.stack.pop()
148
149  def __peek(self):
150    assert not self.__isEmpty()
151    return self.stack[-1]
152
153  def __push(self, element):
154    self.stack.append(element)
155
156  def __setLast(self, element):
157    self.stack[-1] = element
158
159def findMatchingLine(statement, c1Pass, scope, variables, excludeLines=[]):
160  """ Finds the first line in `c1Pass` which matches `statement`.
161
162  Scan only lines numbered between `scope.start` and `scope.end` and not on the
163  `excludeLines` list.
164
165  Returns the index of the `c1Pass` line matching the statement and variables
166  values after the match.
167
168  Raises MatchFailedException if no such `c1Pass` line can be found.
169  """
170  for i in range(scope.start, scope.end):
171    if i in excludeLines: continue
172    newVariables = MatchLines(statement, c1Pass.body[i], variables)
173    if newVariables is not None:
174      return MatchInfo(MatchScope(i, i), newVariables)
175  raise MatchFailedException(statement, scope.start, variables)
176
177class ExecutionState(object):
178  def __init__(self, c1Pass, variables={}):
179    self.cursor = 0
180    self.c1Pass = c1Pass
181    self.c1Length = len(c1Pass.body)
182    self.variables = ImmutableDict(variables)
183    self.dagQueue = []
184    self.notQueue = []
185    self.ifStack = IfStack()
186    self.lastVariant = None
187
188  def moveCursor(self, match):
189    assert self.cursor <= match.scope.end
190
191    # Handle any pending NOT statements before moving the cursor
192    self.handleNotQueue(MatchScope(self.cursor, match.scope.start))
193
194    self.cursor = match.scope.end + 1
195    self.variables = match.variables
196
197  def handleDagQueue(self, scope):
198    """ Attempts to find matching `c1Pass` lines for a group of DAG statements.
199
200    Statements are matched in the list order and variable values propagated. Only
201    lines in `scope` are scanned and each line can only match one statement.
202
203    Returns the range of `c1Pass` lines covered by this group (min/max of matching
204    line numbers) and the variable values after the match of the last statement.
205
206    Raises MatchFailedException when a statement cannot be satisfied.
207    """
208    if not self.dagQueue:
209      return
210
211    matchedLines = []
212    variables = self.variables
213
214    for statement in self.dagQueue:
215      assert statement.variant == TestStatement.Variant.DAG
216      match = findMatchingLine(statement, self.c1Pass, scope, variables, matchedLines)
217      variables = match.variables
218      assert match.scope.start == match.scope.end
219      assert match.scope.start not in matchedLines
220      matchedLines.append(match.scope.start)
221
222    match = MatchInfo(MatchScope(min(matchedLines), max(matchedLines)), variables)
223    self.dagQueue = []
224    self.moveCursor(match)
225
226  def handleNotQueue(self, scope):
227    """ Verifies that none of the given NOT statements matches a line inside
228        the given `scope` of `c1Pass` lines.
229
230    Raises MatchFailedException if a statement matches a line in the scope.
231    """
232    for statement in self.notQueue:
233      assert statement.variant == TestStatement.Variant.Not
234      for i in range(scope.start, scope.end):
235        if MatchLines(statement, self.c1Pass.body[i], self.variables) is not None:
236          raise MatchFailedException(statement, i, self.variables)
237    self.notQueue = []
238
239  def handleEOF(self):
240    """ EOF marker always moves the cursor to the end of the file."""
241    match = MatchInfo(MatchScope(self.c1Length, self.c1Length), None)
242    self.moveCursor(match)
243
244  def handleInOrder(self, statement):
245    """ Single in-order statement. Find the first line that matches and move
246        the cursor to the subsequent line.
247
248    Raises MatchFailedException if no such line can be found.
249    """
250    scope = MatchScope(self.cursor, self.c1Length)
251    match = findMatchingLine(statement, self.c1Pass, scope, self.variables)
252    self.moveCursor(match)
253
254  def handleNextLine(self, statement):
255    """ Single next-line statement. Test if the current line matches and move
256        the cursor to the next line if it does.
257
258    Raises MatchFailedException if the current line does not match.
259    """
260    if self.lastVariant not in [ TestStatement.Variant.InOrder, TestStatement.Variant.NextLine ]:
261      raise BadStructureException("A next-line statement can only be placed "
262                  "after an in-order statement or another next-line statement.",
263                  statement.lineNo)
264
265    scope = MatchScope(self.cursor, self.cursor + 1)
266    match = findMatchingLine(statement, self.c1Pass, scope, self.variables)
267    self.moveCursor(match)
268
269  def handleEval(self, statement):
270    """ Evaluates the statement in the current context.
271
272    Raises MatchFailedException if the expression evaluates to False.
273    """
274    if not EvaluateLine(statement, self.variables):
275      raise MatchFailedException(statement, self.cursor, self.variables)
276
277  def handle(self, statement):
278    variant = None if statement is None else statement.variant
279
280    if variant in [ TestStatement.Variant.If,
281                    TestStatement.Variant.Elif,
282                    TestStatement.Variant.Else,
283                    TestStatement.Variant.Fi ]:
284      self.ifStack.Handle(statement, self.variables)
285      return
286
287    if variant is None:
288      self.ifStack.Eof()
289
290    if not self.ifStack.CanExecute():
291      return
292
293    # First non-DAG statement always triggers execution of any preceding
294    # DAG statements.
295    if variant is not TestStatement.Variant.DAG:
296      self.handleDagQueue(MatchScope(self.cursor, self.c1Length))
297
298    if variant is None:
299      self.handleEOF()
300    elif variant is TestStatement.Variant.InOrder:
301      self.handleInOrder(statement)
302    elif variant is TestStatement.Variant.NextLine:
303      self.handleNextLine(statement)
304    elif variant is TestStatement.Variant.DAG:
305      self.dagQueue.append(statement)
306    elif variant is TestStatement.Variant.Not:
307      self.notQueue.append(statement)
308    else:
309      assert variant is TestStatement.Variant.Eval
310      self.handleEval(statement)
311
312    self.lastVariant = variant
313
314def MatchTestCase(testCase, c1Pass, instructionSetFeatures):
315  """ Runs a test case against a C1visualizer graph dump.
316
317  Raises MatchFailedException when a statement cannot be satisfied.
318  """
319  assert testCase.name == c1Pass.name
320
321  initialVariables = {"ISA_FEATURES": instructionSetFeatures}
322  state = ExecutionState(c1Pass, initialVariables)
323  testStatements = testCase.statements + [ None ]
324  for statement in testStatements:
325    state.handle(statement)
326
327def MatchFiles(checkerFile, c1File, targetArch, debuggableMode):
328  for testCase in checkerFile.testCases:
329    if testCase.testArch not in [None, targetArch]:
330      continue
331    if testCase.forDebuggable != debuggableMode:
332      continue
333
334    # TODO: Currently does not handle multiple occurrences of the same group
335    # name, e.g. when a pass is run multiple times. It will always try to
336    # match a check group against the first output group of the same name.
337    c1Pass = c1File.findPass(testCase.name)
338    if c1Pass is None:
339      with file(c1File.fileName) as cfgFile:
340        Logger.log(''.join(cfgFile), Logger.Level.Error)
341      Logger.fail("Test case not found in the CFG file",
342                  testCase.fileName, testCase.startLineNo, testCase.name)
343
344    Logger.startTest(testCase.name)
345    try:
346      MatchTestCase(testCase, c1Pass, c1File.instructionSetFeatures)
347      Logger.testPassed()
348    except MatchFailedException as e:
349      lineNo = c1Pass.startLineNo + e.lineNo
350      if e.statement.variant == TestStatement.Variant.Not:
351        msg = "NOT statement matched line {}"
352      else:
353        msg = "Statement could not be matched starting from line {}"
354      msg = msg.format(lineNo)
355      with file(c1File.fileName) as cfgFile:
356        Logger.log(''.join(cfgFile), Logger.Level.Error)
357      Logger.testFailed(msg, e.statement, e.variables)
358