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 15 from collections import namedtuple 16 from common.immutables import ImmutableDict 17 from common.logger import Logger 18 from file_format.c1visualizer.struct import C1visualizerFile, C1visualizerPass 19 from file_format.checker.struct import CheckerFile, TestCase, TestAssertion 20 from match.line import MatchLines, EvaluateLine 21 22 MatchScope = namedtuple("MatchScope", ["start", "end"]) 23 MatchInfo = namedtuple("MatchInfo", ["scope", "variables"]) 24 25 class MatchFailedException(Exception): 26 def __init__(self, assertion, lineNo, variables): 27 self.assertion = assertion 28 self.lineNo = lineNo 29 self.variables = variables 30 31 def 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 46 def 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 64 def 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 85 def 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 98 def testEvalGroup(assertions, scope, variables): 99 for assertion in assertions: 100 if not EvaluateLine(assertion, variables): 101 raise MatchFailedException(assertion, scope.start, variables) 102 103 def 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 163 def 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
