ART: Refactor and simplify matching in Checker
Change-Id: Ib8a2b51488f66a7239e799f5fa5910b4ac2dfe08
diff --git a/tools/checker/match/file.py b/tools/checker/match/file.py
index 116fe9a..6cff2bf 100644
--- a/tools/checker/match/file.py
+++ b/tools/checker/match/file.py
@@ -12,127 +12,138 @@
# See the License for the specific language governing permissions and
# limitations under the License.
+from collections import namedtuple
from common.immutables import ImmutableDict
from common.logger import Logger
from file_format.c1visualizer.struct import C1visualizerFile, C1visualizerPass
from file_format.checker.struct import CheckerFile, TestCase, TestAssertion
from match.line import MatchLines
-def __headAndTail(list):
- return list[0], list[1:]
+MatchScope = namedtuple("MatchScope", ["start", "end"])
+MatchInfo = namedtuple("MatchInfo", ["scope", "variables"])
-def __splitByVariant(lines, variant):
- """ Splits a list of check lines at index 'i' such that lines[i] is the first
- element whose variant is not equal to the given parameter.
+class MatchFailedException(Exception):
+ def __init__(self, assertion, lineNo):
+ self.assertion = assertion
+ self.lineNo = lineNo
+
+def splitIntoGroups(assertions):
+ """ Breaks up a list of assertions, grouping instructions which should be
+ tested in the same scope (consecutive DAG and NOT instructions).
+ """
+ splitAssertions = []
+ lastVariant = None
+ for assertion in assertions:
+ if (assertion.variant == lastVariant and
+ assertion.variant in [TestAssertion.Variant.DAG, TestAssertion.Variant.Not]):
+ splitAssertions[-1].append(assertion)
+ else:
+ splitAssertions.append([assertion])
+ lastVariant = assertion.variant
+ return splitAssertions
+
+def findMatchingLine(assertion, c1Pass, scope, variables, excludeLines=[]):
+ """ Finds the first line in `c1Pass` which matches `assertion`.
+
+ Scan only lines numbered between `scope.start` and `scope.end` and not on the
+ `excludeLines` list.
+
+ Returns the index of the `c1Pass` line matching the assertion and variables
+ values after the match.
+
+ Raises MatchFailedException if no such `c1Pass` line can be found.
"""
- i = 0
- while i < len(lines) and lines[i].variant == variant:
- i += 1
- return lines[:i], lines[i:]
+ for i in range(scope.start, scope.end):
+ if i in excludeLines: continue
+ newVariables = MatchLines(assertion, c1Pass.body[i], variables)
+ if newVariables is not None:
+ return MatchInfo(MatchScope(i, i), newVariables)
+ raise MatchFailedException(assertion, scope.start)
-def __nextIndependentChecks(checkLines):
- """ Extracts the first sequence of check lines which are independent of each
- other's match location, i.e. either consecutive DAG lines or a single
- InOrder line. Any Not lines preceeding this sequence are also extracted.
+def matchDagGroup(assertions, c1Pass, scope, variables):
+ """ Attempts to find matching `c1Pass` lines for a group of DAG assertions.
+
+ Assertions are matched in the list order and variable values propagated. Only
+ lines in `scope` are scanned and each line can only match one assertion.
+
+ Returns the range of `c1Pass` lines covered by this group (min/max of matching
+ line numbers) and the variable values after the match of the last assertion.
+
+ Raises MatchFailedException when an assertion cannot be satisfied.
"""
- notChecks, checkLines = __splitByVariant(checkLines, TestAssertion.Variant.Not)
- if not checkLines:
- return notChecks, [], []
-
- head, tail = __headAndTail(checkLines)
- if head.variant == TestAssertion.Variant.InOrder:
- return notChecks, [head], tail
- else:
- assert head.variant == TestAssertion.Variant.DAG
- independentChecks, checkLines = __splitByVariant(checkLines, TestAssertion.Variant.DAG)
- return notChecks, independentChecks, checkLines
-
-def __findFirstMatch(checkLine, outputLines, startLineNo, lineFilter, varState):
- """ If successful, returns the line number of the first output line matching
- the check line and the updated variable state. Otherwise returns -1 and
- None, respectively. The 'lineFilter' parameter can be used to supply a
- list of line numbers (counting from 1) which should be skipped.
- """
- matchLineNo = startLineNo
- for outputLine in outputLines:
- if matchLineNo not in lineFilter:
- newVarState = MatchLines(checkLine, outputLine, varState)
- if newVarState is not None:
- return matchLineNo, newVarState
- matchLineNo += 1
- return -1, None
-
-def __matchIndependentChecks(checkLines, outputLines, startLineNo, varState):
- """ Matches the given positive check lines against the output in order of
- appearance. Variable state is propagated but the scope of the search
- remains the same for all checks. Each output line can only be matched
- once. If all check lines are matched, the resulting variable state is
- returned together with the remaining output. The function also returns
- output lines which appear before either of the matched lines so they can
- be tested against Not checks.
- """
- # If no checks are provided, skip over the entire output.
- if not checkLines:
- return outputLines, [], startLineNo + len(outputLines), varState
-
- # Keep track of which lines have been matched.
matchedLines = []
+ for assertion in assertions:
+ assert assertion.variant == TestAssertion.Variant.DAG
+ match = findMatchingLine(assertion, c1Pass, scope, variables, matchedLines)
+ variables = match.variables
+ assert match.scope.start == match.scope.end
+ assert match.scope.start not in matchedLines
+ matchedLines.append(match.scope.start)
+ return MatchInfo(MatchScope(min(matchedLines), max(matchedLines)), variables)
- # Find first unused output line which matches each check line.
- for checkLine in checkLines:
- matchLineNo, varState = \
- __findFirstMatch(checkLine, outputLines, startLineNo, matchedLines, varState)
- if varState is None:
- Logger.testFailed("Could not match check line \"" + checkLine.originalText + "\" " +
- "starting from output line " + str(startLineNo),
- checkLine.fileName, checkLine.lineNo)
- matchedLines.append(matchLineNo)
+def testNotGroup(assertions, c1Pass, scope, variables):
+ """ Verifies that none of the given NOT assertions matches a line inside
+ the given `scope` of `c1Pass` lines.
- # Return new variable state and the output lines which lie outside the
- # match locations of this independent group.
- minMatchLineNo = min(matchedLines)
- maxMatchLineNo = max(matchedLines)
- preceedingLines = outputLines[:minMatchLineNo - startLineNo]
- remainingLines = outputLines[maxMatchLineNo - startLineNo + 1:]
- return preceedingLines, remainingLines, maxMatchLineNo + 1, varState
-
-def __matchNotLines(checkLines, outputLines, startLineNo, varState):
- """ Makes sure that the given check lines do not match any of the given output
- lines. Variable state does not change.
+ Raises MatchFailedException if an assertion matches a line in the scope.
"""
- for checkLine in checkLines:
- assert checkLine.variant == TestAssertion.Variant.Not
- matchLineNo, matchVarState = \
- __findFirstMatch(checkLine, outputLines, startLineNo, [], varState)
- if matchVarState is not None:
- Logger.testFailed("CHECK-NOT line \"" + checkLine.originalText + "\" matches output line " + \
- str(matchLineNo), checkLine.fileName, checkLine.lineNo)
+ for i in range(scope.start, scope.end):
+ line = c1Pass.body[i]
+ for assertion in assertions:
+ assert assertion.variant == TestAssertion.Variant.Not
+ if MatchLines(assertion, line, variables) is not None:
+ raise MatchFailedException(assertion, i)
-def __matchGroups(checkGroup, outputGroup):
- """ Matches the check lines in this group against an output group. It is
- responsible for running the checks in the right order and scope, and
- for propagating the variable state between the check lines.
+def MatchTestCase(testCase, c1Pass):
+ """ Runs a test case against a C1visualizer graph dump.
+
+ Raises MatchFailedException when an assertion cannot be satisfied.
"""
- varState = ImmutableDict()
- checkLines = checkGroup.assertions
- outputLines = outputGroup.body
- startLineNo = outputGroup.startLineNo
+ assert testCase.name == c1Pass.name
- while checkLines:
- # Extract the next sequence of location-independent checks to be matched.
- notChecks, independentChecks, checkLines = __nextIndependentChecks(checkLines)
+ matchFrom = 0
+ variables = ImmutableDict()
+ c1Length = len(c1Pass.body)
- # Match the independent checks.
- notOutput, outputLines, newStartLineNo, newVarState = \
- __matchIndependentChecks(independentChecks, outputLines, startLineNo, varState)
+ # NOT assertions are verified retrospectively, once the scope is known.
+ pendingNotAssertions = None
- # Run the Not checks against the output lines which lie between the last
- # two independent groups or the bounds of the output.
- __matchNotLines(notChecks, notOutput, startLineNo, varState)
+ # Prepare assertions by grouping those that are verified in the same scope.
+ # We also add None as an EOF assertion that will set scope for NOTs.
+ assertionGroups = splitIntoGroups(testCase.assertions)
+ assertionGroups.append(None)
- # Update variable state.
- startLineNo = newStartLineNo
- varState = newVarState
+ for assertionGroup in assertionGroups:
+ if assertionGroup is None:
+ # EOF marker always matches the last+1 line of c1Pass.
+ match = MatchInfo(MatchScope(c1Length, c1Length), None)
+ elif assertionGroup[0].variant == TestAssertion.Variant.Not:
+ # NOT assertions will be tested together with the next group.
+ assert not pendingNotAssertions
+ pendingNotAssertions = assertionGroup
+ continue
+ elif assertionGroup[0].variant == TestAssertion.Variant.InOrder:
+ # Single in-order assertion. Find the first line that matches.
+ assert len(assertionGroup) == 1
+ scope = MatchScope(matchFrom, c1Length)
+ match = findMatchingLine(assertionGroup[0], c1Pass, scope, variables)
+ else:
+ # A group of DAG assertions. Match them all starting from the same point.
+ assert assertionGroup[0].variant == TestAssertion.Variant.DAG
+ scope = MatchScope(matchFrom, c1Length)
+ match = matchDagGroup(assertionGroup, c1Pass, scope, variables)
+
+ if pendingNotAssertions:
+ # Previous group were NOT assertions. Make sure they don't match any lines
+ # in the [matchFrom, match.start) scope.
+ scope = MatchScope(matchFrom, match.scope.start)
+ testNotGroup(pendingNotAssertions, c1Pass, scope, variables)
+ pendingNotAssertions = None
+
+ # Update state.
+ assert matchFrom <= match.scope.end
+ matchFrom = match.scope.end + 1
+ variables = match.variables
def MatchFiles(checkerFile, c1File):
for testCase in checkerFile.testCases:
@@ -141,8 +152,18 @@
# match a check group against the first output group of the same name.
c1Pass = c1File.findPass(testCase.name)
if c1Pass is None:
- Logger.fail("Test case \"" + testCase.name + "\" not found in the C1visualizer output",
+ Logger.fail("Test case \"{}\" not found in the CFG file".format(testCase.name),
testCase.fileName, testCase.startLineNo)
+
Logger.startTest(testCase.name)
- __matchGroups(testCase, c1Pass)
- Logger.testPassed()
+ try:
+ MatchTestCase(testCase, c1Pass)
+ Logger.testPassed()
+ except MatchFailedException as e:
+ lineNo = c1Pass.startLineNo + e.lineNo
+ if e.assertion.variant == TestAssertion.Variant.Not:
+ Logger.testFailed("NOT assertion matched line {}".format(lineNo),
+ e.assertion.fileName, e.assertion.lineNo)
+ else:
+ Logger.testFailed("Assertion could not be matched starting from line {}".format(lineNo),
+ e.assertion.fileName, e.assertion.lineNo)
diff --git a/tools/checker/match/test.py b/tools/checker/match/test.py
index 97725ad..e4dd784 100644
--- a/tools/checker/match/test.py
+++ b/tools/checker/match/test.py
@@ -18,7 +18,7 @@
from file_format.c1visualizer.struct import C1visualizerFile, C1visualizerPass
from file_format.checker.parser import ParseCheckerStream, ParseCheckerAssertion
from file_format.checker.struct import CheckerFile, TestCase, TestAssertion, RegexExpression
-from match.file import MatchFiles
+from match.file import MatchTestCase, MatchFailedException
from match.line import MatchLines
import io
@@ -38,68 +38,71 @@
ToUnicode(c1String),
ImmutableDict(varState))
- def matches(self, checkerString, c1String, varState={}):
- return self.tryMatch(checkerString, c1String, varState) is not None
+ def assertMatches(self, checkerString, c1String, varState={}):
+ self.assertIsNotNone(self.tryMatch(checkerString, c1String, varState))
+
+ def assertDoesNotMatch(self, checkerString, c1String, varState={}):
+ self.assertIsNone(self.tryMatch(checkerString, c1String, varState))
def test_TextAndWhitespace(self):
- self.assertTrue(self.matches("foo", "foo"))
- self.assertTrue(self.matches("foo", " foo "))
- self.assertTrue(self.matches("foo", "foo bar"))
- self.assertFalse(self.matches("foo", "XfooX"))
- self.assertFalse(self.matches("foo", "zoo"))
+ self.assertMatches("foo", "foo")
+ self.assertMatches("foo", " foo ")
+ self.assertMatches("foo", "foo bar")
+ self.assertDoesNotMatch("foo", "XfooX")
+ self.assertDoesNotMatch("foo", "zoo")
- self.assertTrue(self.matches("foo bar", "foo bar"))
- self.assertTrue(self.matches("foo bar", "abc foo bar def"))
- self.assertTrue(self.matches("foo bar", "foo foo bar bar"))
+ self.assertMatches("foo bar", "foo bar")
+ self.assertMatches("foo bar", "abc foo bar def")
+ self.assertMatches("foo bar", "foo foo bar bar")
- self.assertTrue(self.matches("foo bar", "foo X bar"))
- self.assertFalse(self.matches("foo bar", "foo Xbar"))
+ self.assertMatches("foo bar", "foo X bar")
+ self.assertDoesNotMatch("foo bar", "foo Xbar")
def test_Pattern(self):
- self.assertTrue(self.matches("foo{{A|B}}bar", "fooAbar"))
- self.assertTrue(self.matches("foo{{A|B}}bar", "fooBbar"))
- self.assertFalse(self.matches("foo{{A|B}}bar", "fooCbar"))
+ self.assertMatches("foo{{A|B}}bar", "fooAbar")
+ self.assertMatches("foo{{A|B}}bar", "fooBbar")
+ self.assertDoesNotMatch("foo{{A|B}}bar", "fooCbar")
def test_VariableReference(self):
- self.assertTrue(self.matches("foo<<X>>bar", "foobar", {"X": ""}))
- self.assertTrue(self.matches("foo<<X>>bar", "fooAbar", {"X": "A"}))
- self.assertTrue(self.matches("foo<<X>>bar", "fooBbar", {"X": "B"}))
- self.assertFalse(self.matches("foo<<X>>bar", "foobar", {"X": "A"}))
- self.assertFalse(self.matches("foo<<X>>bar", "foo bar", {"X": "A"}))
+ self.assertMatches("foo<<X>>bar", "foobar", {"X": ""})
+ self.assertMatches("foo<<X>>bar", "fooAbar", {"X": "A"})
+ self.assertMatches("foo<<X>>bar", "fooBbar", {"X": "B"})
+ self.assertDoesNotMatch("foo<<X>>bar", "foobar", {"X": "A"})
+ self.assertDoesNotMatch("foo<<X>>bar", "foo bar", {"X": "A"})
with self.assertRaises(CheckerException):
- self.assertTrue(self.matches("foo<<X>>bar", "foobar", {}))
+ self.tryMatch("foo<<X>>bar", "foobar", {})
def test_VariableDefinition(self):
- self.assertTrue(self.matches("foo<<X:A|B>>bar", "fooAbar"))
- self.assertTrue(self.matches("foo<<X:A|B>>bar", "fooBbar"))
- self.assertFalse(self.matches("foo<<X:A|B>>bar", "fooCbar"))
+ self.assertMatches("foo<<X:A|B>>bar", "fooAbar")
+ self.assertMatches("foo<<X:A|B>>bar", "fooBbar")
+ self.assertDoesNotMatch("foo<<X:A|B>>bar", "fooCbar")
env = self.tryMatch("foo<<X:A.*B>>bar", "fooABbar", {})
self.assertEqual(env, {"X": "AB"})
env = self.tryMatch("foo<<X:A.*B>>bar", "fooAxxBbar", {})
self.assertEqual(env, {"X": "AxxB"})
- self.assertTrue(self.matches("foo<<X:A|B>>bar<<X>>baz", "fooAbarAbaz"))
- self.assertTrue(self.matches("foo<<X:A|B>>bar<<X>>baz", "fooBbarBbaz"))
- self.assertFalse(self.matches("foo<<X:A|B>>bar<<X>>baz", "fooAbarBbaz"))
+ self.assertMatches("foo<<X:A|B>>bar<<X>>baz", "fooAbarAbaz")
+ self.assertMatches("foo<<X:A|B>>bar<<X>>baz", "fooBbarBbaz")
+ self.assertDoesNotMatch("foo<<X:A|B>>bar<<X>>baz", "fooAbarBbaz")
def test_NoVariableRedefinition(self):
with self.assertRaises(CheckerException):
- self.matches("<<X:...>><<X>><<X:...>><<X>>", "foofoobarbar")
+ self.tryMatch("<<X:...>><<X>><<X:...>><<X>>", "foofoobarbar")
def test_EnvNotChangedOnPartialMatch(self):
env = {"Y": "foo"}
- self.assertFalse(self.matches("<<X:A>>bar", "Abaz", env))
+ self.assertDoesNotMatch("<<X:A>>bar", "Abaz", env)
self.assertFalse("X" in env.keys())
def test_VariableContentEscaped(self):
- self.assertTrue(self.matches("<<X:..>>foo<<X>>", ".*foo.*"))
- self.assertFalse(self.matches("<<X:..>>foo<<X>>", ".*fooAAAA"))
+ self.assertMatches("<<X:..>>foo<<X>>", ".*foo.*")
+ self.assertDoesNotMatch("<<X:..>>foo<<X>>", ".*fooAAAA")
class MatchFiles_Test(unittest.TestCase):
- def matches(self, checkerString, c1String):
+ def assertMatches(self, checkerString, c1String):
checkerString = \
"""
// CHECK-START: MyMethod MyPass
@@ -119,22 +122,24 @@
"""
checkerFile = ParseCheckerStream("<test-file>", "CHECK", io.StringIO(ToUnicode(checkerString)))
c1File = ParseC1visualizerStream("<c1-file>", io.StringIO(ToUnicode(c1String)))
- try:
- MatchFiles(checkerFile, c1File)
- return True
- except CheckerException:
- return False
+ assert len(checkerFile.testCases) == 1
+ assert len(c1File.passes) == 1
+ MatchTestCase(checkerFile.testCases[0], c1File.passes[0])
+
+ def assertDoesNotMatch(self, checkerString, c1String):
+ with self.assertRaises(MatchFailedException):
+ self.assertMatches(checkerString, c1String)
def test_Text(self):
- self.assertTrue(self.matches( "// CHECK: foo bar", "foo bar"))
- self.assertFalse(self.matches("// CHECK: foo bar", "abc def"))
+ self.assertMatches("// CHECK: foo bar", "foo bar")
+ self.assertDoesNotMatch("// CHECK: foo bar", "abc def")
def test_Pattern(self):
- self.assertTrue(self.matches( "// CHECK: abc {{de.}}", "abc de#"))
- self.assertFalse(self.matches("// CHECK: abc {{de.}}", "abc d#f"))
+ self.assertMatches("// CHECK: abc {{de.}}", "abc de#")
+ self.assertDoesNotMatch("// CHECK: abc {{de.}}", "abc d#f")
def test_Variables(self):
- self.assertTrue(self.matches(
+ self.assertMatches(
"""
// CHECK: foo<<X:.>>bar
// CHECK: abc<<X>>def
@@ -142,8 +147,8 @@
"""
foo0bar
abc0def
- """))
- self.assertTrue(self.matches(
+ """)
+ self.assertMatches(
"""
// CHECK: foo<<X:([0-9]+)>>bar
// CHECK: abc<<X>>def
@@ -153,8 +158,8 @@
foo1234bar
abc1234def
### 1234 ###
- """))
- self.assertFalse(self.matches(
+ """)
+ self.assertDoesNotMatch(
"""
// CHECK: foo<<X:([0-9]+)>>bar
// CHECK: abc<<X>>def
@@ -162,16 +167,16 @@
"""
foo1234bar
abc1235def
- """))
+ """)
def test_WholeWordMustMatch(self):
- self.assertTrue(self.matches( "// CHECK: b{{.}}r", "abc bar def"))
- self.assertFalse(self.matches( "// CHECK: b{{.}}r", "abc Xbar def"))
- self.assertFalse(self.matches( "// CHECK: b{{.}}r", "abc barX def"))
- self.assertFalse(self.matches( "// CHECK: b{{.}}r", "abc b r def"))
+ self.assertMatches("// CHECK: b{{.}}r", "abc bar def")
+ self.assertDoesNotMatch("// CHECK: b{{.}}r", "abc Xbar def")
+ self.assertDoesNotMatch("// CHECK: b{{.}}r", "abc barX def")
+ self.assertDoesNotMatch("// CHECK: b{{.}}r", "abc b r def")
def test_InOrderAssertions(self):
- self.assertTrue(self.matches(
+ self.assertMatches(
"""
// CHECK: foo
// CHECK: bar
@@ -179,8 +184,8 @@
"""
foo
bar
- """))
- self.assertFalse(self.matches(
+ """)
+ self.assertDoesNotMatch(
"""
// CHECK: foo
// CHECK: bar
@@ -188,10 +193,10 @@
"""
bar
foo
- """))
+ """)
def test_DagAssertions(self):
- self.assertTrue(self.matches(
+ self.assertMatches(
"""
// CHECK-DAG: foo
// CHECK-DAG: bar
@@ -199,8 +204,8 @@
"""
foo
bar
- """))
- self.assertTrue(self.matches(
+ """)
+ self.assertMatches(
"""
// CHECK-DAG: foo
// CHECK-DAG: bar
@@ -208,10 +213,10 @@
"""
bar
foo
- """))
+ """)
def test_DagAssertionsScope(self):
- self.assertTrue(self.matches(
+ self.assertMatches(
"""
// CHECK: foo
// CHECK-DAG: abc
@@ -223,8 +228,8 @@
def
abc
bar
- """))
- self.assertFalse(self.matches(
+ """)
+ self.assertDoesNotMatch(
"""
// CHECK: foo
// CHECK-DAG: abc
@@ -236,8 +241,8 @@
abc
bar
def
- """))
- self.assertFalse(self.matches(
+ """)
+ self.assertDoesNotMatch(
"""
// CHECK: foo
// CHECK-DAG: abc
@@ -249,26 +254,26 @@
def
bar
abc
- """))
+ """)
def test_NotAssertions(self):
- self.assertTrue(self.matches(
+ self.assertMatches(
"""
// CHECK-NOT: foo
""",
"""
abc
def
- """))
- self.assertFalse(self.matches(
+ """)
+ self.assertDoesNotMatch(
"""
// CHECK-NOT: foo
""",
"""
abc foo
def
- """))
- self.assertFalse(self.matches(
+ """)
+ self.assertDoesNotMatch(
"""
// CHECK-NOT: foo
// CHECK-NOT: bar
@@ -276,10 +281,10 @@
"""
abc
def bar
- """))
+ """)
def test_NotAssertionsScope(self):
- self.assertTrue(self.matches(
+ self.assertMatches(
"""
// CHECK: abc
// CHECK-NOT: foo
@@ -288,8 +293,8 @@
"""
abc
def
- """))
- self.assertTrue(self.matches(
+ """)
+ self.assertMatches(
"""
// CHECK: abc
// CHECK-NOT: foo
@@ -299,8 +304,8 @@
abc
def
foo
- """))
- self.assertFalse(self.matches(
+ """)
+ self.assertDoesNotMatch(
"""
// CHECK: abc
// CHECK-NOT: foo
@@ -310,10 +315,10 @@
abc
foo
def
- """))
+ """)
def test_LineOnlyMatchesOnce(self):
- self.assertTrue(self.matches(
+ self.assertMatches(
"""
// CHECK-DAG: foo
// CHECK-DAG: foo
@@ -322,8 +327,8 @@
foo
abc
foo
- """))
- self.assertFalse(self.matches(
+ """)
+ self.assertDoesNotMatch(
"""
// CHECK-DAG: foo
// CHECK-DAG: foo
@@ -332,4 +337,4 @@
foo
abc
bar
- """))
+ """)
