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, TestAssertion
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, assertion, lineNo, variables):
27    self.assertion = assertion
28    self.lineNo = lineNo
29    self.variables = variables
30
31def splitIntoGroups(assertions):
32  """ Breaks up a list of assertions, grouping instructions which should be
33      tested in the same scope (consecutive DAG and NOT instructions).
34   """
35  splitAssertions = []
36  lastVariant = None
37  for assertion in assertions:
38    if (assertion.variant == lastVariant and
39        assertion.variant in [TestAssertion.Variant.DAG, TestAssertion.Variant.Not]):
40      splitAssertions[-1].append(assertion)
41    else:
42      splitAssertions.append([assertion])
43      lastVariant = assertion.variant
44  return splitAssertions
45
46def findMatchingLine(assertion, c1Pass, scope, variables, excludeLines=[]):
47  """ Finds the first line in `c1Pass` which matches `assertion`.
48
49  Scan only lines numbered between `scope.start` and `scope.end` and not on the
50  `excludeLines` list.
51
52  Returns the index of the `c1Pass` line matching the assertion and variables
53  values after the match.
54
55  Raises MatchFailedException if no such `c1Pass` line can be found.
56  """
57  for i in range(scope.start, scope.end):
58    if i in excludeLines: continue
59    newVariables = MatchLines(assertion, c1Pass.body[i], variables)
60    if newVariables is not None:
61      return MatchInfo(MatchScope(i, i), newVariables)
62  raise MatchFailedException(assertion, scope.start, variables)
63
64def matchDagGroup(assertions, c1Pass, scope, variables):
65  """ Attempts to find matching `c1Pass` lines for a group of DAG assertions.
66
67  Assertions are matched in the list order and variable values propagated. Only
68  lines in `scope` are scanned and each line can only match one assertion.
69
70  Returns the range of `c1Pass` lines covered by this group (min/max of matching
71  line numbers) and the variable values after the match of the last assertion.
72
73  Raises MatchFailedException when an assertion cannot be satisfied.
74  """
75  matchedLines = []
76  for assertion in assertions:
77    assert assertion.variant == TestAssertion.Variant.DAG
78    match = findMatchingLine(assertion, c1Pass, scope, variables, matchedLines)
79    variables = match.variables
80    assert match.scope.start == match.scope.end
81    assert match.scope.start not in matchedLines
82    matchedLines.append(match.scope.start)
83  return MatchInfo(MatchScope(min(matchedLines), max(matchedLines)), variables)
84
85def testNotGroup(assertions, c1Pass, scope, variables):
86  """ Verifies that none of the given NOT assertions matches a line inside
87      the given `scope` of `c1Pass` lines.
88
89  Raises MatchFailedException if an assertion matches a line in the scope.
90  """
91  for i in range(scope.start, scope.end):
92    line = c1Pass.body[i]
93    for assertion in assertions:
94      assert assertion.variant == TestAssertion.Variant.Not
95      if MatchLines(assertion, line, variables) is not None:
96        raise MatchFailedException(assertion, i, variables)
97
98def testEvalGroup(assertions, scope, variables):
99  for assertion in assertions:
100    if not EvaluateLine(assertion, variables):
101      raise MatchFailedException(assertion, scope.start, variables)
102
103def MatchTestCase(testCase, c1Pass):
104  """ Runs a test case against a C1visualizer graph dump.
105
106  Raises MatchFailedException when an assertion cannot be satisfied.
107  """
108  assert testCase.name == c1Pass.name
109
110  matchFrom = 0
111  variables = ImmutableDict()
112  c1Length = len(c1Pass.body)
113
114  # NOT assertions are verified retrospectively, once the scope is known.
115  pendingNotAssertions = None
116
117  # Prepare assertions by grouping those that are verified in the same scope.
118  # We also add None as an EOF assertion that will set scope for NOTs.
119  assertionGroups = splitIntoGroups(testCase.assertions)
120  assertionGroups.append(None)
121
122  for assertionGroup in assertionGroups:
123    if assertionGroup is None:
124      # EOF marker always matches the last+1 line of c1Pass.
125      match = MatchInfo(MatchScope(c1Length, c1Length), None)
126    elif assertionGroup[0].variant == TestAssertion.Variant.Not:
127      # NOT assertions will be tested together with the next group.
128      assert not pendingNotAssertions
129      pendingNotAssertions = assertionGroup
130      continue
131    elif assertionGroup[0].variant == TestAssertion.Variant.InOrder:
132      # Single in-order assertion. Find the first line that matches.
133      assert len(assertionGroup) == 1
134      scope = MatchScope(matchFrom, c1Length)
135      match = findMatchingLine(assertionGroup[0], c1Pass, scope, variables)
136    elif assertionGroup[0].variant == TestAssertion.Variant.NextLine:
137      # Single next-line assertion. Test if the current line matches.
138      assert len(assertionGroup) == 1
139      scope = MatchScope(matchFrom, matchFrom + 1)
140      match = findMatchingLine(assertionGroup[0], c1Pass, scope, variables)
141    elif assertionGroup[0].variant == TestAssertion.Variant.DAG:
142      # A group of DAG assertions. Match them all starting from the same point.
143      scope = MatchScope(matchFrom, c1Length)
144      match = matchDagGroup(assertionGroup, c1Pass, scope, variables)
145    else:
146      assert assertionGroup[0].variant == TestAssertion.Variant.Eval
147      scope = MatchScope(matchFrom, c1Length)
148      testEvalGroup(assertionGroup, scope, variables)
149      continue
150
151    if pendingNotAssertions:
152      # Previous group were NOT assertions. Make sure they don't match any lines
153      # in the [matchFrom, match.start) scope.
154      scope = MatchScope(matchFrom, match.scope.start)
155      testNotGroup(pendingNotAssertions, c1Pass, scope, variables)
156      pendingNotAssertions = None
157
158    # Update state.
159    assert matchFrom <= match.scope.end
160    matchFrom = match.scope.end + 1
161    variables = match.variables
162
163def MatchFiles(checkerFile, c1File, targetArch, debuggableMode):
164  for testCase in checkerFile.testCases:
165    if testCase.testArch not in [None, targetArch]:
166      continue
167    if testCase.forDebuggable != debuggableMode:
168      continue
169
170    # TODO: Currently does not handle multiple occurrences of the same group
171    # name, e.g. when a pass is run multiple times. It will always try to
172    # match a check group against the first output group of the same name.
173    c1Pass = c1File.findPass(testCase.name)
174    if c1Pass is None:
175      Logger.fail("Test case not found in the CFG file",
176                  testCase.fileName, testCase.startLineNo, testCase.name)
177
178    Logger.startTest(testCase.name)
179    try:
180      MatchTestCase(testCase, c1Pass)
181      Logger.testPassed()
182    except MatchFailedException as e:
183      lineNo = c1Pass.startLineNo + e.lineNo
184      if e.assertion.variant == TestAssertion.Variant.Not:
185        msg = "NOT assertion matched line {}"
186      else:
187        msg = "Assertion could not be matched starting from line {}"
188      msg = msg.format(lineNo)
189      Logger.testFailed(msg, e.assertion, e.variables)
190