ART: Split Checker into smaller files

Checker code has become too messy and incomprehensible. This patch
splits it into more manageable and better structured units.
Functionality remains unchanged.

Change-Id: I870c69827d2be2d09196a51382a3f47f31cd2ba3

23 files changed, 1731 insertions, 1253 deletions

diff --git a/test/run-test b/test/run-test
index 2873a35c83..239681ff4e 100755
--- a/test/run-test
+++ b/test/run-test
@@ -39,7 +39,7 @@ if [ -z "$TMPDIR" ]; then
 else
   tmp_dir="${TMPDIR}/$USER/${test_dir}"
 fi
-checker="${progdir}/../tools/checker.py"
+checker="${progdir}/../tools/checker/checker.py"
 
 export JAVA="java"
 export JAVAC="javac -g"
diff --git a/tools/checker.py b/tools/checker.py
deleted file mode 100755
index 08ad57b798..0000000000
--- a/tools/checker.py
+++ /dev/null
@@ -1,778 +0,0 @@
-#!/usr/bin/env python2
-#
-# Copyright (C) 2014 The Android Open Source Project
-#
-# Licensed under the Apache License, Version 2.0 (the "License");
-# you may not use this file except in compliance with the License.
-# You may obtain a copy of the License at
-#
-#   http://www.apache.org/licenses/LICENSE-2.0
-#
-# Unless required by applicable law or agreed to in writing, software
-# distributed under the License is distributed on an "AS IS" BASIS,
-# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-# See the License for the specific language governing permissions and
-# limitations under the License.
-
-
-# Checker is a testing tool which compiles a given test file and compares the
-# state of the control-flow graph before and after each optimization pass
-# against a set of assertions specified alongside the tests.
-#
-# Tests are written in Java, turned into DEX and compiled with the Optimizing
-# compiler. "Check lines" are assertions formatted as comments of the Java file.
-# They begin with prefix 'CHECK' followed by a pattern that the engine attempts
-# to match in the compiler-generated output.
-#
-# Assertions are tested in groups which correspond to the individual compiler
-# passes. Each group of check lines therefore must start with a 'CHECK-START'
-# header which specifies the output group it should be tested against. The group
-# name must exactly match one of the groups recognized in the output (they can
-# be listed with the '--list-groups' command-line flag).
-#
-# Matching of check lines is carried out in the order of appearance in the
-# source file. There are three types of check lines:
-#  - CHECK:     Must match an output line which appears in the output group
-#               later than lines matched against any preceeding checks. Output
-#               lines must therefore match the check lines in the same order.
-#               These are referred to as "in-order" checks in the code.
-#  - CHECK-DAG: Must match an output line which appears in the output group
-#               later than lines matched against any preceeding in-order checks.
-#               In other words, the order of output lines does not matter
-#               between consecutive DAG checks.
-#  - CHECK-NOT: Must not match any output line which appears in the output group
-#               later than lines matched against any preceeding checks and
-#               earlier than lines matched against any subsequent checks.
-#               Surrounding non-negative checks (or boundaries of the group)
-#               therefore create a scope within which the assertion is verified.
-#
-# Check-line patterns are treated as plain text rather than regular expressions
-# but are whitespace agnostic.
-#
-# Actual regex patterns can be inserted enclosed in '{{' and '}}' brackets. If
-# curly brackets need to be used inside the body of the regex, they need to be
-# enclosed in round brackets. For example, the pattern '{{foo{2}}}' will parse
-# the invalid regex 'foo{2', but '{{(fo{2})}}' will match 'foo'.
-#
-# Regex patterns can be named and referenced later. A new variable is defined
-# with '[[name:regex]]' and can be referenced with '[[name]]'. Variables are
-# only valid within the scope of the defining group. Within a group they cannot
-# be redefined or used undefined.
-#
-# Example:
-#   The following assertions can be placed in a Java source file:
-#
-#   // CHECK-START: int MyClass.MyMethod() constant_folding (after)
-#   // CHECK:         [[ID:i[0-9]+]] IntConstant {{11|22}}
-#   // CHECK:                        Return [ [[ID]] ]
-#
-#   The engine will attempt to match the check lines against the output of the
-#   group named on the first line. Together they verify that the CFG after
-#   constant folding returns an integer constant with value either 11 or 22.
-#
-
-from __future__ import print_function
-import argparse
-import os
-import re
-import shutil
-import sys
-import tempfile
-
-class Logger(object):
-
-  class Level(object):
-    NoOutput, Error, Info = range(3)
-
-  class Color(object):
-    Default, Blue, Gray, Purple, Red = range(5)
-
-    @staticmethod
-    def terminalCode(color, out=sys.stdout):
-      if not out.isatty():
-        return ''
-      elif color == Logger.Color.Blue:
-        return '\033[94m'
-      elif color == Logger.Color.Gray:
-        return '\033[37m'
-      elif color == Logger.Color.Purple:
-        return '\033[95m'
-      elif color == Logger.Color.Red:
-        return '\033[91m'
-      else:
-        return '\033[0m'
-
-  Verbosity = Level.Info
-
-  @staticmethod
-  def log(text, level=Level.Info, color=Color.Default, newLine=True, out=sys.stdout):
-    if level <= Logger.Verbosity:
-      text = Logger.Color.terminalCode(color, out) + text + \
-             Logger.Color.terminalCode(Logger.Color.Default, out)
-      if newLine:
-        print(text, file=out)
-      else:
-        print(text, end="", file=out)
-      out.flush()
-
-  @staticmethod
-  def fail(msg, file=None, line=-1):
-    location = ""
-    if file:
-      location += file + ":"
-    if line > 0:
-      location += str(line) + ":"
-    if location:
-      location += " "
-
-    Logger.log(location, Logger.Level.Error, color=Logger.Color.Gray, newLine=False, out=sys.stderr)
-    Logger.log("error: ", Logger.Level.Error, color=Logger.Color.Red, newLine=False, out=sys.stderr)
-    Logger.log(msg, Logger.Level.Error, out=sys.stderr)
-    sys.exit(msg)
-
-  @staticmethod
-  def startTest(name):
-    Logger.log("TEST ", color=Logger.Color.Purple, newLine=False)
-    Logger.log(name + "... ", newLine=False)
-
-  @staticmethod
-  def testPassed():
-    Logger.log("PASS", color=Logger.Color.Blue)
-
-  @staticmethod
-  def testFailed(msg, file=None, line=-1):
-    Logger.log("FAIL", color=Logger.Color.Red)
-    Logger.fail(msg, file, line)
-
-class CommonEqualityMixin:
-  """Mixin for class equality as equality of the fields."""
-  def __eq__(self, other):
-    return (isinstance(other, self.__class__)
-           and self.__dict__ == other.__dict__)
-
-  def __ne__(self, other):
-    return not self.__eq__(other)
-
-  def __repr__(self):
-    return "<%s: %s>" % (type(self).__name__, str(self.__dict__))
-
-
-class CheckElement(CommonEqualityMixin):
-  """Single element of the check line."""
-
-  class Variant(object):
-    """Supported language constructs."""
-    Text, Pattern, VarRef, VarDef, Separator = range(5)
-
-  rStartOptional = r"("
-  rEndOptional = r")?"
-
-  rName = r"([a-zA-Z][a-zA-Z0-9]*)"
-  rRegex = r"(.+?)"
-  rPatternStartSym = r"(\{\{)"
-  rPatternEndSym = r"(\}\})"
-  rVariableStartSym = r"(\[\[)"
-  rVariableEndSym = r"(\]\])"
-  rVariableSeparator = r"(:)"
-
-  regexPattern = rPatternStartSym + rRegex + rPatternEndSym
-  regexVariable = rVariableStartSym + \
-                    rName + \
-                    (rStartOptional + rVariableSeparator + rRegex + rEndOptional) + \
-                  rVariableEndSym
-
-  def __init__(self, variant, name, pattern):
-    self.variant = variant
-    self.name = name
-    self.pattern = pattern
-
-  @staticmethod
-  def newSeparator():
-    return CheckElement(CheckElement.Variant.Separator, None, None)
-
-  @staticmethod
-  def parseText(text):
-    return CheckElement(CheckElement.Variant.Text, None, re.escape(text))
-
-  @staticmethod
-  def parsePattern(patternElem):
-    return CheckElement(CheckElement.Variant.Pattern, None, patternElem[2:-2])
-
-  @staticmethod
-  def parseVariable(varElem):
-    colonPos = varElem.find(":")
-    if colonPos == -1:
-      # Variable reference
-      name = varElem[2:-2]
-      return CheckElement(CheckElement.Variant.VarRef, name, None)
-    else:
-      # Variable definition
-      name = varElem[2:colonPos]
-      body = varElem[colonPos+1:-2]
-      return CheckElement(CheckElement.Variant.VarDef, name, body)
-
-class CheckLine(CommonEqualityMixin):
-  """Representation of a single assertion in the check file formed of one or
-     more regex elements. Matching against an output line is successful only
-     if all regex elements can be matched in the given order."""
-
-  class Variant(object):
-    """Supported types of assertions."""
-    InOrder, DAG, Not = range(3)
-
-  def __init__(self, content, variant=Variant.InOrder, fileName=None, lineNo=-1):
-    self.fileName = fileName
-    self.lineNo = lineNo
-    self.content = content.strip()
-
-    self.variant = variant
-    self.lineParts = self.__parse(self.content)
-    if not self.lineParts:
-      Logger.fail("Empty check line", self.fileName, self.lineNo)
-
-    if self.variant == CheckLine.Variant.Not:
-      for elem in self.lineParts:
-        if elem.variant == CheckElement.Variant.VarDef:
-          Logger.fail("CHECK-NOT lines cannot define variables", self.fileName, self.lineNo)
-
-  def __eq__(self, other):
-    return (isinstance(other, self.__class__) and
-            self.variant == other.variant and
-            self.lineParts == other.lineParts)
-
-  # Returns True if the given Match object was at the beginning of the line.
-  def __isMatchAtStart(self, match):
-    return (match is not None) and (match.start() == 0)
-
-  # Takes in a list of Match objects and returns the minimal start point among
-  # them. If there aren't any successful matches it returns the length of
-  # the searched string.
-  def __firstMatch(self, matches, string):
-    starts = map(lambda m: len(string) if m is None else m.start(), matches)
-    return min(starts)
-
-  # This method parses the content of a check line stripped of the initial
-  # comment symbol and the CHECK keyword.
-  def __parse(self, line):
-    lineParts = []
-    # Loop as long as there is something to parse.
-    while line:
-      # Search for the nearest occurrence of the special markers.
-      matchWhitespace = re.search(r"\s+", line)
-      matchPattern = re.search(CheckElement.regexPattern, line)
-      matchVariable = re.search(CheckElement.regexVariable, line)
-
-      # If one of the above was identified at the current position, extract them
-      # from the line, parse them and add to the list of line parts.
-      if self.__isMatchAtStart(matchWhitespace):
-        # A whitespace in the check line creates a new separator of line parts.
-        # This allows for ignored output between the previous and next parts.
-        line = line[matchWhitespace.end():]
-        lineParts.append(CheckElement.newSeparator())
-      elif self.__isMatchAtStart(matchPattern):
-        pattern = line[0:matchPattern.end()]
-        line = line[matchPattern.end():]
-        lineParts.append(CheckElement.parsePattern(pattern))
-      elif self.__isMatchAtStart(matchVariable):
-        var = line[0:matchVariable.end()]
-        line = line[matchVariable.end():]
-        lineParts.append(CheckElement.parseVariable(var))
-      else:
-        # If we're not currently looking at a special marker, this is a plain
-        # text match all the way until the first special marker (or the end
-        # of the line).
-        firstMatch = self.__firstMatch([ matchWhitespace, matchPattern, matchVariable ], line)
-        text = line[0:firstMatch]
-        line = line[firstMatch:]
-        lineParts.append(CheckElement.parseText(text))
-    return lineParts
-
-  # Returns the regex pattern to be matched in the output line. Variable
-  # references are substituted with their current values provided in the
-  # 'varState' argument.
-  # An exception is raised if a referenced variable is undefined.
-  def __generatePattern(self, linePart, varState):
-    if linePart.variant == CheckElement.Variant.VarRef:
-      try:
-        return re.escape(varState[linePart.name])
-      except KeyError:
-        Logger.testFailed("Use of undefined variable \"" + linePart.name + "\"",
-                          self.fileName, self.lineNo)
-    else:
-      return linePart.pattern
-
-  def __isSeparated(self, outputLine, matchStart):
-    return (matchStart == 0) or (outputLine[matchStart - 1:matchStart].isspace())
-
-  # Attempts to match the check line against a line from the output file with
-  # the given initial variable values. It returns the new variable state if
-  # successful and None otherwise.
-  def match(self, outputLine, initialVarState):
-    # Do the full matching on a shadow copy of the variable state. If the
-    # matching fails half-way, we will not need to revert the state.
-    varState = dict(initialVarState)
-
-    matchStart = 0
-    isAfterSeparator = True
-
-    # Now try to parse all of the parts of the check line in the right order.
-    # Variable values are updated on-the-fly, meaning that a variable can
-    # be referenced immediately after its definition.
-    for part in self.lineParts:
-      if part.variant == CheckElement.Variant.Separator:
-        isAfterSeparator = True
-        continue
-
-      # Find the earliest match for this line part.
-      pattern = self.__generatePattern(part, varState)
-      while True:
-        match = re.search(pattern, outputLine[matchStart:])
-        if (match is None) or (not isAfterSeparator and not self.__isMatchAtStart(match)):
-          return None
-        matchEnd = matchStart + match.end()
-        matchStart += match.start()
-
-        # Check if this is a valid match if we expect a whitespace separator
-        # before the matched text. Otherwise loop and look for another match.
-        if not isAfterSeparator or self.__isSeparated(outputLine, matchStart):
-          break
-        else:
-          matchStart += 1
-
-      if part.variant == CheckElement.Variant.VarDef:
-        if part.name in varState:
-          Logger.testFailed("Multiple definitions of variable \"" + part.name + "\"",
-                            self.fileName, self.lineNo)
-        varState[part.name] = outputLine[matchStart:matchEnd]
-
-      matchStart = matchEnd
-      isAfterSeparator = False
-
-    # All parts were successfully matched. Return the new variable state.
-    return varState
-
-
-class CheckGroup(CommonEqualityMixin):
-  """Represents a named collection of check lines which are to be matched
-     against an output group of the same name."""
-
-  def __init__(self, name, lines, fileName=None, lineNo=-1):
-    self.fileName = fileName
-    self.lineNo = lineNo
-
-    if not name:
-      Logger.fail("Check group does not have a name", self.fileName, self.lineNo)
-    if not lines:
-      Logger.fail("Check group does not have a body", self.fileName, self.lineNo)
-
-    self.name = name
-    self.lines = lines
-
-  def __eq__(self, other):
-    return (isinstance(other, self.__class__) and
-            self.name == other.name and
-            self.lines == other.lines)
-
-  def __headAndTail(self, list):
-    return list[0], list[1:]
-
-  # 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.
-  def __splitByVariant(self, lines, variant):
-    i = 0
-    while i < len(lines) and lines[i].variant == variant:
-      i += 1
-    return lines[:i], lines[i:]
-
-  # 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 __nextIndependentChecks(self, checkLines):
-    notChecks, checkLines = self.__splitByVariant(checkLines, CheckLine.Variant.Not)
-    if not checkLines:
-      return notChecks, [], []
-
-    head, tail = self.__headAndTail(checkLines)
-    if head.variant == CheckLine.Variant.InOrder:
-      return notChecks, [head], tail
-    else:
-      assert head.variant == CheckLine.Variant.DAG
-      independentChecks, checkLines = self.__splitByVariant(checkLines, CheckLine.Variant.DAG)
-      return notChecks, independentChecks, checkLines
-
-  # 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.
-  def __findFirstMatch(self, checkLine, outputLines, startLineNo, lineFilter, varState):
-    matchLineNo = startLineNo
-    for outputLine in outputLines:
-      if matchLineNo not in lineFilter:
-        newVarState = checkLine.match(outputLine, varState)
-        if newVarState is not None:
-          return matchLineNo, newVarState
-      matchLineNo += 1
-    return -1, None
-
-  # 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.
-  def __matchIndependentChecks(self, checkLines, outputLines, startLineNo, varState):
-    # 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 = []
-
-    # Find first unused output line which matches each check line.
-    for checkLine in checkLines:
-      matchLineNo, varState = \
-        self.__findFirstMatch(checkLine, outputLines, startLineNo, matchedLines, varState)
-      if varState is None:
-        Logger.testFailed("Could not match check line \"" + checkLine.content + "\" " +
-                          "starting from output line " + str(startLineNo),
-                          self.fileName, checkLine.lineNo)
-      matchedLines.append(matchLineNo)
-
-    # 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
-
-  # Makes sure that the given check lines do not match any of the given output
-  # lines. Variable state does not change.
-  def __matchNotLines(self, checkLines, outputLines, startLineNo, varState):
-    for checkLine in checkLines:
-      assert checkLine.variant == CheckLine.Variant.Not
-      matchLineNo, matchVarState = \
-        self.__findFirstMatch(checkLine, outputLines, startLineNo, [], varState)
-      if matchVarState is not None:
-        Logger.testFailed("CHECK-NOT line \"" + checkLine.content + "\" matches output line " + \
-                          str(matchLineNo), self.fileName, checkLine.lineNo)
-
-  # 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 match(self, outputGroup):
-    varState = {}
-    checkLines = self.lines
-    outputLines = outputGroup.body
-    startLineNo = outputGroup.lineNo
-
-    while checkLines:
-      # Extract the next sequence of location-independent checks to be matched.
-      notChecks, independentChecks, checkLines = self.__nextIndependentChecks(checkLines)
-
-      # Match the independent checks.
-      notOutput, outputLines, newStartLineNo, newVarState = \
-        self.__matchIndependentChecks(independentChecks, outputLines, startLineNo, varState)
-
-      # Run the Not checks against the output lines which lie between the last
-      # two independent groups or the bounds of the output.
-      self.__matchNotLines(notChecks, notOutput, startLineNo, varState)
-
-      # Update variable state.
-      startLineNo = newStartLineNo
-      varState = newVarState
-
-class OutputGroup(CommonEqualityMixin):
-  """Represents a named part of the test output against which a check group of
-     the same name is to be matched."""
-
-  def __init__(self, name, body, fileName=None, lineNo=-1):
-    if not name:
-      Logger.fail("Output group does not have a name", fileName, lineNo)
-    if not body:
-      Logger.fail("Output group does not have a body", fileName, lineNo)
-
-    self.name = name
-    self.body = body
-    self.lineNo = lineNo
-
-  def __eq__(self, other):
-    return (isinstance(other, self.__class__) and
-            self.name == other.name and
-            self.body == other.body)
-
-
-class FileSplitMixin(object):
-  """Mixin for representing text files which need to be split into smaller
-     chunks before being parsed."""
-
-  def _parseStream(self, stream):
-    lineNo = 0
-    allGroups = []
-    currentGroup = None
-
-    for line in stream:
-      lineNo += 1
-      line = line.strip()
-      if not line:
-        continue
-
-      # Let the child class process the line and return information about it.
-      # The _processLine method can modify the content of the line (or delete it
-      # entirely) and specify whether it starts a new group.
-      processedLine, newGroupName = self._processLine(line, lineNo)
-      if newGroupName is not None:
-        currentGroup = (newGroupName, [], lineNo)
-        allGroups.append(currentGroup)
-      if processedLine is not None:
-        if currentGroup is not None:
-          currentGroup[1].append(processedLine)
-        else:
-          self._exceptionLineOutsideGroup(line, lineNo)
-
-    # Finally, take the generated line groups and let the child class process
-    # each one before storing the final outcome.
-    return list(map(lambda group: self._processGroup(group[0], group[1], group[2]), allGroups))
-
-
-class CheckFile(FileSplitMixin):
-  """Collection of check groups extracted from the input test file."""
-
-  def __init__(self, prefix, checkStream, fileName=None):
-    self.fileName = fileName
-    self.prefix = prefix
-    self.groups = self._parseStream(checkStream)
-
-  # Attempts to parse a check line. The regex searches for a comment symbol
-  # followed by the CHECK keyword, given attribute and a colon at the very
-  # beginning of the line. Whitespaces are ignored.
-  def _extractLine(self, prefix, line):
-    rIgnoreWhitespace = r"\s*"
-    rCommentSymbols = [r"//", r"#"]
-    regexPrefix = rIgnoreWhitespace + \
-                  r"(" + r"|".join(rCommentSymbols) + r")" + \
-                  rIgnoreWhitespace + \
-                  prefix + r":"
-
-    # The 'match' function succeeds only if the pattern is matched at the
-    # beginning of the line.
-    match = re.match(regexPrefix, line)
-    if match is not None:
-      return line[match.end():].strip()
-    else:
-      return None
-
-  # This function is invoked on each line of the check file and returns a pair
-  # which instructs the parser how the line should be handled. If the line is to
-  # be included in the current check group, it is returned in the first value.
-  # If the line starts a new check group, the name of the group is returned in
-  # the second value.
-  def _processLine(self, line, lineNo):
-    # Lines beginning with 'CHECK-START' start a new check group.
-    startLine = self._extractLine(self.prefix + "-START", line)
-    if startLine is not None:
-      return None, startLine
-
-    # Lines starting only with 'CHECK' are matched in order.
-    plainLine = self._extractLine(self.prefix, line)
-    if plainLine is not None:
-      return (plainLine, CheckLine.Variant.InOrder, lineNo), None
-
-    # 'CHECK-DAG' lines are no-order assertions.
-    dagLine = self._extractLine(self.prefix + "-DAG", line)
-    if dagLine is not None:
-      return (dagLine, CheckLine.Variant.DAG, lineNo), None
-
-    # 'CHECK-NOT' lines are no-order negative assertions.
-    notLine = self._extractLine(self.prefix + "-NOT", line)
-    if notLine is not None:
-      return (notLine, CheckLine.Variant.Not, lineNo), None
-
-    # Other lines are ignored.
-    return None, None
-
-  def _exceptionLineOutsideGroup(self, line, lineNo):
-    Logger.fail("Check line not inside a group", self.fileName, lineNo)
-
-  # Constructs a check group from the parser-collected check lines.
-  def _processGroup(self, name, lines, lineNo):
-    checkLines = list(map(lambda line: CheckLine(line[0], line[1], self.fileName, line[2]), lines))
-    return CheckGroup(name, checkLines, self.fileName, lineNo)
-
-  def match(self, outputFile):
-    for checkGroup in self.groups:
-      # TODO: Currently does not handle multiple occurrences of the same group
-      # name, e.g. when a pass is run multiple times. It will always try to
-      # match a check group against the first output group of the same name.
-      outputGroup = outputFile.findGroup(checkGroup.name)
-      if outputGroup is None:
-        Logger.fail("Group \"" + checkGroup.name + "\" not found in the output",
-                    self.fileName, checkGroup.lineNo)
-      Logger.startTest(checkGroup.name)
-      checkGroup.match(outputGroup)
-      Logger.testPassed()
-
-
-class OutputFile(FileSplitMixin):
-  """Representation of the output generated by the test and split into groups
-     within which the checks are performed.
-
-     C1visualizer format is parsed with a state machine which differentiates
-     between the 'compilation' and 'cfg' blocks. The former marks the beginning
-     of a method. It is parsed for the method's name but otherwise ignored. Each
-     subsequent CFG block represents one stage of the compilation pipeline and
-     is parsed into an output group named "<method name> <pass name>".
-     """
-
-  class ParsingState:
-    OutsideBlock, InsideCompilationBlock, StartingCfgBlock, InsideCfgBlock = range(4)
-
-  def __init__(self, outputStream, fileName=None):
-    self.fileName = fileName
-
-    # Initialize the state machine
-    self.lastMethodName = None
-    self.state = OutputFile.ParsingState.OutsideBlock
-    self.groups = self._parseStream(outputStream)
-
-  # This function is invoked on each line of the output file and returns a pair
-  # which instructs the parser how the line should be handled. If the line is to
-  # be included in the current group, it is returned in the first value. If the
-  # line starts a new output group, the name of the group is returned in the
-  # second value.
-  def _processLine(self, line, lineNo):
-    if self.state == OutputFile.ParsingState.StartingCfgBlock:
-      # Previous line started a new 'cfg' block which means that this one must
-      # contain the name of the pass (this is enforced by C1visualizer).
-      if re.match("name\s+\"[^\"]+\"", line):
-        # Extract the pass name, prepend it with the name of the method and
-        # return as the beginning of a new group.
-        self.state = OutputFile.ParsingState.InsideCfgBlock
-        return (None, self.lastMethodName + " " + line.split("\"")[1])
-      else:
-        Logger.fail("Expected output group name", self.fileName, lineNo)
-
-    elif self.state == OutputFile.ParsingState.InsideCfgBlock:
-      if line == "end_cfg":
-        self.state = OutputFile.ParsingState.OutsideBlock
-        return (None, None)
-      else:
-        return (line, None)
-
-    elif self.state == OutputFile.ParsingState.InsideCompilationBlock:
-      # Search for the method's name. Format: method "<name>"
-      if re.match("method\s+\"[^\"]*\"", line):
-        methodName = line.split("\"")[1].strip()
-        if not methodName:
-          Logger.fail("Empty method name in output", self.fileName, lineNo)
-        self.lastMethodName = methodName
-      elif line == "end_compilation":
-        self.state = OutputFile.ParsingState.OutsideBlock
-      return (None, None)
-
-    else:
-      assert self.state == OutputFile.ParsingState.OutsideBlock
-      if line == "begin_cfg":
-        # The line starts a new group but we'll wait until the next line from
-        # which we can extract the name of the pass.
-        if self.lastMethodName is None:
-          Logger.fail("Expected method header", self.fileName, lineNo)
-        self.state = OutputFile.ParsingState.StartingCfgBlock
-        return (None, None)
-      elif line == "begin_compilation":
-        self.state = OutputFile.ParsingState.InsideCompilationBlock
-        return (None, None)
-      else:
-        Logger.fail("Output line not inside a group", self.fileName, lineNo)
-
-  # Constructs an output group from the parser-collected output lines.
-  def _processGroup(self, name, lines, lineNo):
-    return OutputGroup(name, lines, self.fileName, lineNo + 1)
-
-  def findGroup(self, name):
-    for group in self.groups:
-      if group.name == name:
-        return group
-    return None
-
-
-def ParseArguments():
-  parser = argparse.ArgumentParser()
-  parser.add_argument("tested_file",
-                      help="text file the checks should be verified against")
-  parser.add_argument("source_path", nargs="?",
-                      help="path to file/folder with checking annotations")
-  parser.add_argument("--check-prefix", dest="check_prefix", default="CHECK", metavar="PREFIX",
-                      help="prefix of checks in the test files (default: CHECK)")
-  parser.add_argument("--list-groups", dest="list_groups", action="store_true",
-                      help="print a list of all groups found in the tested file")
-  parser.add_argument("--dump-group", dest="dump_group", metavar="GROUP",
-                      help="print the contents of an output group")
-  parser.add_argument("-q", "--quiet", action="store_true",
-                      help="print only errors")
-  return parser.parse_args()
-
-
-def ListGroups(outputFilename):
-  outputFile = OutputFile(open(outputFilename, "r"))
-  for group in outputFile.groups:
-    Logger.log(group.name)
-
-
-def DumpGroup(outputFilename, groupName):
-  outputFile = OutputFile(open(outputFilename, "r"))
-  group = outputFile.findGroup(groupName)
-  if group:
-    lineNo = group.lineNo
-    maxLineNo = lineNo + len(group.body)
-    lenLineNo = len(str(maxLineNo)) + 2
-    for line in group.body:
-      Logger.log((str(lineNo) + ":").ljust(lenLineNo) + line)
-      lineNo += 1
-  else:
-    Logger.fail("Group \"" + groupName + "\" not found in the output")
-
-
-# Returns a list of files to scan for check annotations in the given path. Path
-# to a file is returned as a single-element list, directories are recursively
-# traversed and all '.java' files returned.
-def FindCheckFiles(path):
-  if not path:
-    Logger.fail("No source path provided")
-  elif os.path.isfile(path):
-    return [ path ]
-  elif os.path.isdir(path):
-    foundFiles = []
-    for root, dirs, files in os.walk(path):
-      for file in files:
-        extension = os.path.splitext(file)[1]
-        if extension in [".java", ".smali"]:
-          foundFiles.append(os.path.join(root, file))
-    return foundFiles
-  else:
-    Logger.fail("Source path \"" + path + "\" not found")
-
-
-def RunChecks(checkPrefix, checkPath, outputFilename):
-  outputBaseName = os.path.basename(outputFilename)
-  outputFile = OutputFile(open(outputFilename, "r"), outputBaseName)
-
-  for checkFilename in FindCheckFiles(checkPath):
-    checkBaseName = os.path.basename(checkFilename)
-    checkFile = CheckFile(checkPrefix, open(checkFilename, "r"), checkBaseName)
-    checkFile.match(outputFile)
-
-
-if __name__ == "__main__":
-  args = ParseArguments()
-
-  if args.quiet:
-    Logger.Verbosity = Logger.Level.Error
-
-  if args.list_groups:
-    ListGroups(args.tested_file)
-  elif args.dump_group:
-    DumpGroup(args.tested_file, args.dump_group)
-  else:
-    RunChecks(args.check_prefix, args.source_path, args.tested_file)
diff --git a/tools/checker/README b/tools/checker/README
new file mode 100644
index 0000000000..9b23ae9299
--- /dev/null
+++ b/tools/checker/README
@@ -0,0 +1,54 @@
+Checker is a testing tool which compiles a given test file and compares the
+state of the control-flow graph before and after each optimization pass
+against a set of assertions specified alongside the tests.
+
+Tests are written in Java, turned into DEX and compiled with the Optimizing
+compiler. "Check lines" are assertions formatted as comments of the Java file.
+They begin with prefix 'CHECK' followed by a pattern that the engine attempts
+to match in the compiler-generated output.
+
+Assertions are tested in groups which correspond to the individual compiler
+passes. Each group of check lines therefore must start with a 'CHECK-START'
+header which specifies the output group it should be tested against. The group
+name must exactly match one of the groups recognized in the output (they can
+be listed with the '--list-groups' command-line flag).
+
+Matching of check lines is carried out in the order of appearance in the
+source file. There are three types of check lines:
+ - CHECK:     Must match an output line which appears in the output group
+              later than lines matched against any preceeding checks. Output
+              lines must therefore match the check lines in the same order.
+              These are referred to as "in-order" checks in the code.
+ - CHECK-DAG: Must match an output line which appears in the output group
+              later than lines matched against any preceeding in-order checks.
+              In other words, the order of output lines does not matter
+              between consecutive DAG checks.
+ - CHECK-NOT: Must not match any output line which appears in the output group
+              later than lines matched against any preceeding checks and
+              earlier than lines matched against any subsequent checks.
+              Surrounding non-negative checks (or boundaries of the group)
+              therefore create a scope within which the assertion is verified.
+
+Check-line patterns are treated as plain text rather than regular expressions
+but are whitespace agnostic.
+
+Actual regex patterns can be inserted enclosed in '{{' and '}}' brackets. If
+curly brackets need to be used inside the body of the regex, they need to be
+enclosed in round brackets. For example, the pattern '{{foo{2}}}' will parse
+the invalid regex 'foo{2', but '{{(fo{2})}}' will match 'foo'.
+
+Regex patterns can be named and referenced later. A new variable is defined
+with '[[name:regex]]' and can be referenced with '[[name]]'. Variables are
+only valid within the scope of the defining group. Within a group they cannot
+be redefined or used undefined.
+
+Example:
+  The following assertions can be placed in a Java source file:
+
+  // CHECK-START: int MyClass.MyMethod() constant_folding (after)
+  // CHECK:         [[ID:i\d+]]  IntConstant {{11|22}}
+  // CHECK:                      Return [ [[ID]] ]
+
+  The engine will attempt to match the check lines against the output of the
+  group named on the first line. Together they verify that the CFG after
+  constant folding returns an integer constant with value either 11 or 22.
diff --git a/tools/checker/checker.py b/tools/checker/checker.py
new file mode 100755
index 0000000000..d6c3059ef5
--- /dev/null
+++ b/tools/checker/checker.py
@@ -0,0 +1,103 @@
+#!/usr/bin/env python2
+#
+# Copyright (C) 2015 The Android Open Source Project
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+#   http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+
+import argparse
+import os
+
+from common.logger                    import Logger
+from file_format.c1visualizer.parser  import ParseC1visualizerStream
+from file_format.checker.parser       import ParseCheckerStream
+from match.file                       import MatchFiles
+
+def ParseArguments():
+  parser = argparse.ArgumentParser()
+  parser.add_argument("tested_file",
+                      help="text file the checks should be verified against")
+  parser.add_argument("source_path", nargs="?",
+                      help="path to file/folder with checking annotations")
+  parser.add_argument("--check-prefix", dest="check_prefix", default="CHECK", metavar="PREFIX",
+                      help="prefix of checks in the test files (default: CHECK)")
+  parser.add_argument("--list-passes", dest="list_passes", action="store_true",
+                      help="print a list of all passes found in the tested file")
+  parser.add_argument("--dump-pass", dest="dump_pass", metavar="PASS",
+                      help="print a compiler pass dump")
+  parser.add_argument("-q", "--quiet", action="store_true",
+                      help="print only errors")
+  return parser.parse_args()
+
+
+def ListPasses(outputFilename):
+  c1File = ParseC1visualizerStream(os.path.basename(outputFilename), open(outputFilename, "r"))
+  for compiler_pass in c1File.passes:
+    Logger.log(compiler_pass.name)
+
+
+def DumpPass(outputFilename, passName):
+  c1File = ParseC1visualizerStream(os.path.basename(outputFilename), open(outputFilename, "r"))
+  compiler_pass = c1File.findPass(passName)
+  if compiler_pass:
+    maxLineNo = compiler_pass.startLineNo + len(compiler_pass.body)
+    lenLineNo = len(str(maxLineNo)) + 2
+    curLineNo = compiler_pass.startLineNo
+    for line in compiler_pass.body:
+      Logger.log((str(curLineNo) + ":").ljust(lenLineNo) + line)
+      curLineNo += 1
+  else:
+    Logger.fail("Pass \"" + passName + "\" not found in the output")
+
+
+def FindCheckerFiles(path):
+  """ Returns a list of files to scan for check annotations in the given path.
+      Path to a file is returned as a single-element list, directories are
+      recursively traversed and all '.java' files returned.
+  """
+  if not path:
+    Logger.fail("No source path provided")
+  elif os.path.isfile(path):
+    return [ path ]
+  elif os.path.isdir(path):
+    foundFiles = []
+    for root, dirs, files in os.walk(path):
+      for file in files:
+        extension = os.path.splitext(file)[1]
+        if extension in [".java", ".smali"]:
+          foundFiles.append(os.path.join(root, file))
+    return foundFiles
+  else:
+    Logger.fail("Source path \"" + path + "\" not found")
+
+
+def RunTests(checkPrefix, checkPath, outputFilename):
+  c1File = ParseC1visualizerStream(os.path.basename(outputFilename), open(outputFilename, "r"))
+  for checkFilename in FindCheckerFiles(checkPath):
+    checkerFile = ParseCheckerStream(os.path.basename(checkFilename),
+                                     checkPrefix,
+                                     open(checkFilename, "r"))
+    MatchFiles(checkerFile, c1File)
+
+
+if __name__ == "__main__":
+  args = ParseArguments()
+
+  if args.quiet:
+    Logger.Verbosity = Logger.Level.Error
+
+  if args.list_passes:
+    ListPasses(args.tested_file)
+  elif args.dump_pass:
+    DumpPass(args.tested_file, args.dump_pass)
+  else:
+    RunTests(args.check_prefix, args.source_path, args.tested_file)
diff --git a/tools/checker/common/__init__.py b/tools/checker/common/__init__.py
new file mode 100644
index 0000000000..33ef6de4ac
--- /dev/null
+++ b/tools/checker/common/__init__.py
@@ -0,0 +1,13 @@
+# Copyright (C) 2015 The Android Open Source Project
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+#   http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
diff --git a/tools/checker/common/logger.py b/tools/checker/common/logger.py
new file mode 100644
index 0000000000..6f71f78d91
--- /dev/null
+++ b/tools/checker/common/logger.py
@@ -0,0 +1,81 @@
+# Copyright (C) 2015 The Android Open Source Project
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+#   http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+
+from __future__ import print_function
+import sys
+
+class Logger(object):
+
+  class Level(object):
+    NoOutput, Error, Info = range(3)
+
+  class Color(object):
+    Default, Blue, Gray, Purple, Red = range(5)
+
+    @staticmethod
+    def terminalCode(color, out=sys.stdout):
+      if not out.isatty():
+        return ''
+      elif color == Logger.Color.Blue:
+        return '\033[94m'
+      elif color == Logger.Color.Gray:
+        return '\033[37m'
+      elif color == Logger.Color.Purple:
+        return '\033[95m'
+      elif color == Logger.Color.Red:
+        return '\033[91m'
+      else:
+        return '\033[0m'
+
+  Verbosity = Level.Info
+
+  @staticmethod
+  def log(text, level=Level.Info, color=Color.Default, newLine=True, out=sys.stdout):
+    if level <= Logger.Verbosity:
+      text = Logger.Color.terminalCode(color, out) + text + \
+             Logger.Color.terminalCode(Logger.Color.Default, out)
+      if newLine:
+        print(text, file=out)
+      else:
+        print(text, end="", file=out)
+      out.flush()
+
+  @staticmethod
+  def fail(msg, file=None, line=-1):
+    location = ""
+    if file:
+      location += file + ":"
+    if line > 0:
+      location += str(line) + ":"
+    if location:
+      location += " "
+
+    Logger.log(location, Logger.Level.Error, color=Logger.Color.Gray, newLine=False, out=sys.stderr)
+    Logger.log("error: ", Logger.Level.Error, color=Logger.Color.Red, newLine=False, out=sys.stderr)
+    Logger.log(msg, Logger.Level.Error, out=sys.stderr)
+    sys.exit(msg)
+
+  @staticmethod
+  def startTest(name):
+    Logger.log("TEST ", color=Logger.Color.Purple, newLine=False)
+    Logger.log(name + "... ", newLine=False)
+
+  @staticmethod
+  def testPassed():
+    Logger.log("PASS", color=Logger.Color.Blue)
+
+  @staticmethod
+  def testFailed(msg, file=None, line=-1):
+    Logger.log("FAIL", color=Logger.Color.Red)
+    Logger.fail(msg, file, line)
diff --git a/tools/checker/common/mixins.py b/tools/checker/common/mixins.py
new file mode 100644
index 0000000000..f44e46d2e0
--- /dev/null
+++ b/tools/checker/common/mixins.py
@@ -0,0 +1,26 @@
+# Copyright (C) 2015 The Android Open Source Project
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+#   http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+
+class EqualityMixin:
+  """ Object equality via equality of dictionaries. """
+
+  def __eq__(self, other):
+    return isinstance(other, self.__class__) \
+       and self.__dict__ == other.__dict__
+
+class PrintableMixin:
+  """ Prints object as name-dictionary pair. """
+
+  def __repr__(self):
+    return "<%s: %s>" % (type(self).__name__, str(self.__dict__))
diff --git a/tools/checker/common/testing.py b/tools/checker/common/testing.py
new file mode 100644
index 0000000000..2014afeeac
--- /dev/null
+++ b/tools/checker/common/testing.py
@@ -0,0 +1,22 @@
+# Copyright (C) 2015 The Android Open Source Project
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+#   http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+
+def ToUnicode(string):
+  """ Converts a string into Unicode.
+
+  This is a delegate function for the built-in `unicode`. It checks if the input
+  is not `None`, because `unicode` turns it into an actual "None" string.
+  """
+  assert string is not None
+  return unicode(string)
diff --git a/tools/checker/file_format/__init__.py b/tools/checker/file_format/__init__.py
new file mode 100644
index 0000000000..33ef6de4ac
--- /dev/null
+++ b/tools/checker/file_format/__init__.py
@@ -0,0 +1,13 @@
+# Copyright (C) 2015 The Android Open Source Project
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+#   http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
diff --git a/tools/checker/file_format/c1visualizer/__init__.py b/tools/checker/file_format/c1visualizer/__init__.py
new file mode 100644
index 0000000000..33ef6de4ac
--- /dev/null
+++ b/tools/checker/file_format/c1visualizer/__init__.py
@@ -0,0 +1,13 @@
+# Copyright (C) 2015 The Android Open Source Project
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+#   http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
diff --git a/tools/checker/file_format/c1visualizer/parser.py b/tools/checker/file_format/c1visualizer/parser.py
new file mode 100644
index 0000000000..f34161b297
--- /dev/null
+++ b/tools/checker/file_format/c1visualizer/parser.py
@@ -0,0 +1,87 @@
+# Copyright (C) 2015 The Android Open Source Project
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+#   http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+
+from common.logger                   import Logger
+from file_format.common              import SplitStream
+from file_format.c1visualizer.struct import C1visualizerFile, C1visualizerPass
+
+import re
+
+class C1ParserState:
+  OutsideBlock, InsideCompilationBlock, StartingCfgBlock, InsideCfgBlock = range(4)
+
+  def __init__(self):
+    self.currentState = C1ParserState.OutsideBlock
+    self.lastMethodName = None
+
+def __parseC1Line(line, lineNo, state, fileName):
+  """ This function is invoked on each line of the output file and returns
+      a pair which instructs the parser how the line should be handled. If the
+      line is to be included in the current group, it is returned in the first
+      value. If the line starts a new output group, the name of the group is
+      returned in the second value.
+  """
+  if state.currentState == C1ParserState.StartingCfgBlock:
+    # Previous line started a new 'cfg' block which means that this one must
+    # contain the name of the pass (this is enforced by C1visualizer).
+    if re.match("name\s+\"[^\"]+\"", line):
+      # Extract the pass name, prepend it with the name of the method and
+      # return as the beginning of a new group.
+      state.currentState = C1ParserState.InsideCfgBlock
+      return (None, state.lastMethodName + " " + line.split("\"")[1])
+    else:
+      Logger.fail("Expected output group name", fileName, lineNo)
+
+  elif state.currentState == C1ParserState.InsideCfgBlock:
+    if line == "end_cfg":
+      state.currentState = C1ParserState.OutsideBlock
+      return (None, None)
+    else:
+      return (line, None)
+
+  elif state.currentState == C1ParserState.InsideCompilationBlock:
+    # Search for the method's name. Format: method "<name>"
+    if re.match("method\s+\"[^\"]*\"", line):
+      methodName = line.split("\"")[1].strip()
+      if not methodName:
+        Logger.fail("Empty method name in output", fileName, lineNo)
+      state.lastMethodName = methodName
+    elif line == "end_compilation":
+      state.currentState = C1ParserState.OutsideBlock
+    return (None, None)
+
+  else:
+    assert state.currentState == C1ParserState.OutsideBlock
+    if line == "begin_cfg":
+      # The line starts a new group but we'll wait until the next line from
+      # which we can extract the name of the pass.
+      if state.lastMethodName is None:
+        Logger.fail("Expected method header", fileName, lineNo)
+      state.currentState = C1ParserState.StartingCfgBlock
+      return (None, None)
+    elif line == "begin_compilation":
+      state.currentState = C1ParserState.InsideCompilationBlock
+      return (None, None)
+    else:
+      Logger.fail("C1visualizer line not inside a group", fileName, lineNo)
+
+def ParseC1visualizerStream(fileName, stream):
+  c1File = C1visualizerFile(fileName)
+  state = C1ParserState()
+  fnProcessLine = lambda line, lineNo: __parseC1Line(line, lineNo, state, fileName)
+  fnLineOutsideChunk = lambda line, lineNo: \
+      Logger.fail("C1visualizer line not inside a group", fileName, lineNo)
+  for passName, passLines, startLineNo in SplitStream(stream, fnProcessLine, fnLineOutsideChunk):
+    C1visualizerPass(c1File, passName, passLines, startLineNo + 1)
+  return c1File
diff --git a/tools/checker/file_format/c1visualizer/struct.py b/tools/checker/file_format/c1visualizer/struct.py
new file mode 100644
index 0000000000..0462765f19
--- /dev/null
+++ b/tools/checker/file_format/c1visualizer/struct.py
@@ -0,0 +1,60 @@
+# Copyright (C) 2015 The Android Open Source Project
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+#   http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+
+from common.logger import Logger
+from common.mixins import PrintableMixin
+
+class C1visualizerFile(PrintableMixin):
+
+  def __init__(self, fileName):
+    self.fileName = fileName
+    self.passes = []
+
+  def addPass(self, new_pass):
+    self.passes.append(new_pass)
+
+  def findPass(self, name):
+    for entry in self.passes:
+      if entry.name == name:
+        return entry
+    return None
+
+  def __eq__(self, other):
+    return isinstance(other, self.__class__) \
+       and self.passes == other.passes
+
+
+class C1visualizerPass(PrintableMixin):
+
+  def __init__(self, parent, name, body, startLineNo):
+    self.parent = parent
+    self.name = name
+    self.body = body
+    self.startLineNo = startLineNo
+
+    if not self.name:
+      Logger.fail("C1visualizer pass does not have a name", self.fileName, self.startLineNo)
+    if not self.body:
+      Logger.fail("C1visualizer pass does not have a body", self.fileName, self.startLineNo)
+
+    self.parent.addPass(self)
+
+  @property
+  def fileName(self):
+    return self.parent.fileName
+
+  def __eq__(self, other):
+    return isinstance(other, self.__class__) \
+       and self.name == other.name \
+       and self.body == other.body
diff --git a/tools/checker/file_format/c1visualizer/test.py b/tools/checker/file_format/c1visualizer/test.py
new file mode 100644
index 0000000000..812a4cf9ce
--- /dev/null
+++ b/tools/checker/file_format/c1visualizer/test.py
@@ -0,0 +1,105 @@
+#!/usr/bin/env python2
+#
+# Copyright (C) 2014 The Android Open Source Project
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+#   http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+
+from common.testing                  import ToUnicode
+from file_format.c1visualizer.parser import ParseC1visualizerStream
+from file_format.c1visualizer.struct import C1visualizerFile, C1visualizerPass
+
+import io
+import unittest
+
+class C1visualizerParser_Test(unittest.TestCase):
+
+  def createFile(self, passList):
+    """ Creates an instance of CheckerFile from provided info.
+
+    Data format: [ ( <case-name>, [ ( <text>, <assert-variant> ), ... ] ), ... ]
+    """
+    c1File = C1visualizerFile("<c1_file>")
+    for passEntry in passList:
+      passName = passEntry[0]
+      passBody = passEntry[1]
+      c1Pass = C1visualizerPass(c1File, passName, passBody, 0)
+    return c1File
+
+  def assertParsesTo(self, c1Text, expectedData):
+    expectedFile = self.createFile(expectedData)
+    actualFile = ParseC1visualizerStream("<c1_file>", io.StringIO(ToUnicode(c1Text)))
+    return self.assertEqual(expectedFile, actualFile)
+
+  def test_EmptyFile(self):
+    self.assertParsesTo("", [])
+
+  def test_SingleGroup(self):
+    self.assertParsesTo(
+      """
+        begin_compilation
+          method "MyMethod"
+        end_compilation
+        begin_cfg
+          name "pass1"
+          foo
+          bar
+        end_cfg
+      """,
+      [ ( "MyMethod pass1", [ "foo", "bar" ] ) ])
+
+  def test_MultipleGroups(self):
+    self.assertParsesTo(
+      """
+        begin_compilation
+          name "xyz1"
+          method "MyMethod1"
+          date 1234
+        end_compilation
+        begin_cfg
+          name "pass1"
+          foo
+          bar
+        end_cfg
+        begin_cfg
+          name "pass2"
+          abc
+          def
+        end_cfg
+      """,
+      [ ( "MyMethod1 pass1", [ "foo", "bar" ] ),
+        ( "MyMethod1 pass2", [ "abc", "def" ] ) ])
+    self.assertParsesTo(
+      """
+        begin_compilation
+          name "xyz1"
+          method "MyMethod1"
+          date 1234
+        end_compilation
+        begin_cfg
+          name "pass1"
+          foo
+          bar
+        end_cfg
+        begin_compilation
+          name "xyz2"
+          method "MyMethod2"
+          date 5678
+        end_compilation
+        begin_cfg
+          name "pass2"
+          abc
+          def
+        end_cfg
+      """,
+      [ ( "MyMethod1 pass1", [ "foo", "bar" ] ),
+        ( "MyMethod2 pass2", [ "abc", "def" ] ) ])
diff --git a/tools/checker/file_format/checker/__init__.py b/tools/checker/file_format/checker/__init__.py
new file mode 100644
index 0000000000..33ef6de4ac
--- /dev/null
+++ b/tools/checker/file_format/checker/__init__.py
@@ -0,0 +1,13 @@
+# Copyright (C) 2015 The Android Open Source Project
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+#   http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
diff --git a/tools/checker/file_format/checker/parser.py b/tools/checker/file_format/checker/parser.py
new file mode 100644
index 0000000000..93fa0934f5
--- /dev/null
+++ b/tools/checker/file_format/checker/parser.py
@@ -0,0 +1,142 @@
+# Copyright (C) 2015 The Android Open Source Project
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+#   http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+
+from file_format.common         import SplitStream
+from file_format.checker.struct import CheckerFile, TestCase, TestAssertion, RegexExpression
+
+import re
+
+def __extractLine(prefix, line):
+  """ Attempts to parse a check line. The regex searches for a comment symbol
+      followed by the CHECK keyword, given attribute and a colon at the very
+      beginning of the line. Whitespaces are ignored.
+  """
+  rIgnoreWhitespace = r"\s*"
+  rCommentSymbols = [r"//", r"#"]
+  regexPrefix = rIgnoreWhitespace + \
+                r"(" + r"|".join(rCommentSymbols) + r")" + \
+                rIgnoreWhitespace + \
+                prefix + r":"
+
+  # The 'match' function succeeds only if the pattern is matched at the
+  # beginning of the line.
+  match = re.match(regexPrefix, line)
+  if match is not None:
+    return line[match.end():].strip()
+  else:
+    return None
+
+def __processLine(line, lineNo, prefix):
+  """ This function is invoked on each line of the check file and returns a pair
+      which instructs the parser how the line should be handled. If the line is
+      to be included in the current check group, it is returned in the first
+      value. If the line starts a new check group, the name of the group is
+      returned in the second value.
+  """
+  # Lines beginning with 'CHECK-START' start a new test case.
+  startLine = __extractLine(prefix + "-START", line)
+  if startLine is not None:
+    return None, startLine
+
+  # Lines starting only with 'CHECK' are matched in order.
+  plainLine = __extractLine(prefix, line)
+  if plainLine is not None:
+    return (plainLine, TestAssertion.Variant.InOrder, lineNo), None
+
+  # 'CHECK-DAG' lines are no-order assertions.
+  dagLine = __extractLine(prefix + "-DAG", line)
+  if dagLine is not None:
+    return (dagLine, TestAssertion.Variant.DAG, lineNo), None
+
+  # 'CHECK-NOT' lines are no-order negative assertions.
+  notLine = __extractLine(prefix + "-NOT", line)
+  if notLine is not None:
+    return (notLine, TestAssertion.Variant.Not, lineNo), None
+
+  # Other lines are ignored.
+  return None, None
+
+def __isMatchAtStart(match):
+  """ Tests if the given Match occurred at the beginning of the line. """
+  return (match is not None) and (match.start() == 0)
+
+def __firstMatch(matches, string):
+  """ Takes in a list of Match objects and returns the minimal start point among
+      them. If there aren't any successful matches it returns the length of
+      the searched string.
+  """
+  starts = map(lambda m: len(string) if m is None else m.start(), matches)
+  return min(starts)
+
+def ParseCheckerAssertion(parent, line, variant, lineNo):
+  """ This method parses the content of a check line stripped of the initial
+      comment symbol and the CHECK keyword.
+  """
+  assertion = TestAssertion(parent, variant, line, lineNo)
+  # Loop as long as there is something to parse.
+  while line:
+    # Search for the nearest occurrence of the special markers.
+    matchWhitespace = re.search(r"\s+", line)
+    matchPattern = re.search(RegexExpression.Regex.regexPattern, line)
+    matchVariableReference = re.search(RegexExpression.Regex.regexVariableReference, line)
+    matchVariableDefinition = re.search(RegexExpression.Regex.regexVariableDefinition, line)
+
+    # If one of the above was identified at the current position, extract them
+    # from the line, parse them and add to the list of line parts.
+    if __isMatchAtStart(matchWhitespace):
+      # A whitespace in the check line creates a new separator of line parts.
+      # This allows for ignored output between the previous and next parts.
+      line = line[matchWhitespace.end():]
+      assertion.addExpression(RegexExpression.createSeparator())
+    elif __isMatchAtStart(matchPattern):
+      pattern = line[0:matchPattern.end()]
+      pattern = pattern[2:-2]
+      line = line[matchPattern.end():]
+      assertion.addExpression(RegexExpression.createPattern(pattern))
+    elif __isMatchAtStart(matchVariableReference):
+      var = line[0:matchVariableReference.end()]
+      line = line[matchVariableReference.end():]
+      name = var[2:-2]
+      assertion.addExpression(RegexExpression.createVariableReference(name))
+    elif __isMatchAtStart(matchVariableDefinition):
+      var = line[0:matchVariableDefinition.end()]
+      line = line[matchVariableDefinition.end():]
+      colonPos = var.find(":")
+      name = var[2:colonPos]
+      body = var[colonPos+1:-2]
+      assertion.addExpression(RegexExpression.createVariableDefinition(name, body))
+    else:
+      # If we're not currently looking at a special marker, this is a plain
+      # text match all the way until the first special marker (or the end
+      # of the line).
+      firstMatch = __firstMatch([ matchWhitespace,
+                                  matchPattern,
+                                  matchVariableReference,
+                                  matchVariableDefinition ],
+                                line)
+      text = line[0:firstMatch]
+      line = line[firstMatch:]
+      assertion.addExpression(RegexExpression.createText(text))
+  return assertion
+
+def ParseCheckerStream(fileName, prefix, stream):
+  checkerFile = CheckerFile(fileName)
+  fnProcessLine = lambda line, lineNo: __processLine(line, lineNo, prefix)
+  fnLineOutsideChunk = lambda line, lineNo: \
+      Logger.fail("C1visualizer line not inside a group", fileName, lineNo)
+  for caseName, caseLines, startLineNo in SplitStream(stream, fnProcessLine, fnLineOutsideChunk):
+    testCase = TestCase(checkerFile, caseName, startLineNo)
+    for caseLine in caseLines:
+      ParseCheckerAssertion(testCase, caseLine[0], caseLine[1], caseLine[2])
+  return checkerFile
diff --git a/tools/checker/file_format/checker/struct.py b/tools/checker/file_format/checker/struct.py
new file mode 100644
index 0000000000..d5cdc3bcc4
--- /dev/null
+++ b/tools/checker/file_format/checker/struct.py
@@ -0,0 +1,156 @@
+# Copyright (C) 2015 The Android Open Source Project
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+#   http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+
+from common.logger import Logger
+from common.mixins import EqualityMixin, PrintableMixin
+
+import re
+
+class CheckerFile(PrintableMixin):
+
+  def __init__(self, fileName):
+    self.fileName = fileName
+    self.testCases = []
+
+  def addTestCase(self, new_test_case):
+    self.testCases.append(new_test_case)
+
+  def __eq__(self, other):
+    return isinstance(other, self.__class__) \
+       and self.testCases == other.testCases
+
+
+class TestCase(PrintableMixin):
+
+  def __init__(self, parent, name, startLineNo):
+    assert isinstance(parent, CheckerFile)
+
+    self.parent = parent
+    self.name = name
+    self.assertions = []
+    self.startLineNo = startLineNo
+
+    if not self.name:
+      Logger.fail("Test case does not have a name", self.parent.fileName, self.startLineNo)
+
+    self.parent.addTestCase(self)
+
+  @property
+  def fileName(self):
+    return self.parent.fileName
+
+  def addAssertion(self, new_assertion):
+    self.assertions.append(new_assertion)
+
+  def __eq__(self, other):
+    return isinstance(other, self.__class__) \
+       and self.name == other.name \
+       and self.assertions == other.assertions
+
+
+class TestAssertion(PrintableMixin):
+
+  class Variant(object):
+    """Supported types of assertions."""
+    InOrder, DAG, Not = range(3)
+
+  def __init__(self, parent, variant, originalText, lineNo):
+    assert isinstance(parent, TestCase)
+
+    self.parent = parent
+    self.variant = variant
+    self.expressions = []
+    self.lineNo = lineNo
+    self.originalText = originalText
+
+    self.parent.addAssertion(self)
+
+  @property
+  def fileName(self):
+    return self.parent.fileName
+
+  def addExpression(self, new_expression):
+    assert isinstance(new_expression, RegexExpression)
+    if self.variant == TestAssertion.Variant.Not:
+      if new_expression.variant == RegexExpression.Variant.VarDef:
+        Logger.fail("CHECK-NOT lines cannot define variables", self.fileName, self.lineNo)
+    self.expressions.append(new_expression)
+
+  def toRegex(self):
+    """ Returns a regex pattern for this entire assertion. Only used in tests. """
+    regex = ""
+    for expression in self.expressions:
+      if expression.variant == RegexExpression.Variant.Separator:
+        regex = regex + ", "
+      else:
+        regex = regex + "(" + expression.pattern + ")"
+    return regex
+
+  def __eq__(self, other):
+    return isinstance(other, self.__class__) \
+       and self.variant == other.variant \
+       and self.expressions == other.expressions
+
+
+class RegexExpression(EqualityMixin, PrintableMixin):
+
+  class Variant(object):
+    """Supported language constructs."""
+    Text, Pattern, VarRef, VarDef, Separator = range(5)
+
+  class Regex(object):
+    rName = r"([a-zA-Z][a-zA-Z0-9]*)"
+    rRegex = r"(.+?)"
+    rPatternStartSym = r"(\{\{)"
+    rPatternEndSym = r"(\}\})"
+    rVariableStartSym = r"(\[\[)"
+    rVariableEndSym = r"(\]\])"
+    rVariableSeparator = r"(:)"
+
+    regexPattern = rPatternStartSym + rRegex + rPatternEndSym
+    regexVariableReference = rVariableStartSym + rName + rVariableEndSym
+    regexVariableDefinition = rVariableStartSym + rName + rVariableSeparator + rRegex + rVariableEndSym
+
+  def __init__(self, variant, name, pattern):
+    self.variant = variant
+    self.name = name
+    self.pattern = pattern
+
+  def __eq__(self, other):
+    return isinstance(other, self.__class__) \
+       and self.variant == other.variant \
+       and self.name == other.name \
+       and self.pattern == other.pattern
+
+  @staticmethod
+  def createSeparator():
+    return RegexExpression(RegexExpression.Variant.Separator, None, None)
+
+  @staticmethod
+  def createText(text):
+    return RegexExpression(RegexExpression.Variant.Text, None, re.escape(text))
+
+  @staticmethod
+  def createPattern(pattern):
+    return RegexExpression(RegexExpression.Variant.Pattern, None, pattern)
+
+  @staticmethod
+  def createVariableReference(name):
+    assert re.match(RegexExpression.Regex.rName, name)
+    return RegexExpression(RegexExpression.Variant.VarRef, name, None)
+
+  @staticmethod
+  def createVariableDefinition(name, pattern):
+    assert re.match(RegexExpression.Regex.rName, name)
+    return RegexExpression(RegexExpression.Variant.VarDef, name, pattern)
diff --git a/tools/checker/file_format/checker/test.py b/tools/checker/file_format/checker/test.py
new file mode 100644
index 0000000000..167c8880e9
--- /dev/null
+++ b/tools/checker/file_format/checker/test.py
@@ -0,0 +1,238 @@
+#!/usr/bin/env python2
+#
+# Copyright (C) 2014 The Android Open Source Project
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+#   http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+
+from common.testing             import ToUnicode
+from file_format.checker.parser import ParseCheckerStream
+from file_format.checker.struct import CheckerFile, TestCase, TestAssertion, RegexExpression
+
+import io
+import unittest
+
+CheckerException = SystemExit
+
+class CheckerParser_PrefixTest(unittest.TestCase):
+
+  def tryParse(self, string):
+    checkerText = u"// CHECK-START: pass\n" + ToUnicode(string)
+    checkFile = ParseCheckerStream("<test-file>", "CHECK", io.StringIO(checkerText))
+    self.assertEqual(len(checkFile.testCases), 1)
+    testCase = checkFile.testCases[0]
+    return len(testCase.assertions) != 0
+
+  def test_InvalidFormat(self):
+    self.assertFalse(self.tryParse("CHECK"))
+    self.assertFalse(self.tryParse(":CHECK"))
+    self.assertFalse(self.tryParse("CHECK:"))
+    self.assertFalse(self.tryParse("//CHECK"))
+    self.assertFalse(self.tryParse("#CHECK"))
+
+    self.assertTrue(self.tryParse("//CHECK:foo"))
+    self.assertTrue(self.tryParse("#CHECK:bar"))
+
+  def test_InvalidLabel(self):
+    self.assertFalse(self.tryParse("//ACHECK:foo"))
+    self.assertFalse(self.tryParse("#ACHECK:foo"))
+
+  def test_NotFirstOnTheLine(self):
+    self.assertFalse(self.tryParse("A// CHECK: foo"))
+    self.assertFalse(self.tryParse("A # CHECK: foo"))
+    self.assertFalse(self.tryParse("// // CHECK: foo"))
+    self.assertFalse(self.tryParse("# # CHECK: foo"))
+
+  def test_WhitespaceAgnostic(self):
+    self.assertTrue(self.tryParse("  //CHECK: foo"))
+    self.assertTrue(self.tryParse("//  CHECK: foo"))
+    self.assertTrue(self.tryParse("    //CHECK: foo"))
+    self.assertTrue(self.tryParse("//    CHECK: foo"))
+
+
+class CheckerParser_RegexExpressionTest(unittest.TestCase):
+
+  def parseAssertion(self, string, variant=""):
+    checkerText = u"// CHECK-START: pass\n// CHECK" + ToUnicode(variant) + u": " + ToUnicode(string)
+    checkerFile = ParseCheckerStream("<test-file>", "CHECK", io.StringIO(checkerText))
+    self.assertEqual(len(checkerFile.testCases), 1)
+    testCase = checkerFile.testCases[0]
+    self.assertEqual(len(testCase.assertions), 1)
+    return testCase.assertions[0]
+
+  def parseExpression(self, string):
+    line = self.parseAssertion(string)
+    self.assertEqual(1, len(line.expressions))
+    return line.expressions[0]
+
+  def assertEqualsRegex(self, string, expected):
+    self.assertEqual(expected, self.parseAssertion(string).toRegex())
+
+  def assertEqualsText(self, string, text):
+    self.assertEqual(self.parseExpression(string), RegexExpression.createText(text))
+
+  def assertEqualsPattern(self, string, pattern):
+    self.assertEqual(self.parseExpression(string), RegexExpression.createPattern(pattern))
+
+  def assertEqualsVarRef(self, string, name):
+    self.assertEqual(self.parseExpression(string), RegexExpression.createVariableReference(name))
+
+  def assertEqualsVarDef(self, string, name, pattern):
+    self.assertEqual(self.parseExpression(string),
+                     RegexExpression.createVariableDefinition(name, pattern))
+
+  def assertVariantNotEqual(self, string, variant):
+    self.assertNotEqual(variant, self.parseExpression(string).variant)
+
+  # Test that individual parts of the line are recognized
+
+  def test_TextOnly(self):
+    self.assertEqualsText("foo", "foo")
+    self.assertEqualsText("  foo  ", "foo")
+    self.assertEqualsRegex("f$o^o", "(f\$o\^o)")
+
+  def test_PatternOnly(self):
+    self.assertEqualsPattern("{{a?b.c}}", "a?b.c")
+
+  def test_VarRefOnly(self):
+    self.assertEqualsVarRef("[[ABC]]", "ABC")
+
+  def test_VarDefOnly(self):
+    self.assertEqualsVarDef("[[ABC:a?b.c]]", "ABC", "a?b.c")
+
+  def test_TextWithWhitespace(self):
+    self.assertEqualsRegex("foo bar", "(foo), (bar)")
+    self.assertEqualsRegex("foo   bar", "(foo), (bar)")
+
+  def test_TextWithRegex(self):
+    self.assertEqualsRegex("foo{{abc}}bar", "(foo)(abc)(bar)")
+
+  def test_TextWithVar(self):
+    self.assertEqualsRegex("foo[[ABC:abc]]bar", "(foo)(abc)(bar)")
+
+  def test_PlainWithRegexAndWhitespaces(self):
+    self.assertEqualsRegex("foo {{abc}}bar", "(foo), (abc)(bar)")
+    self.assertEqualsRegex("foo{{abc}} bar", "(foo)(abc), (bar)")
+    self.assertEqualsRegex("foo {{abc}} bar", "(foo), (abc), (bar)")
+
+  def test_PlainWithVarAndWhitespaces(self):
+    self.assertEqualsRegex("foo [[ABC:abc]]bar", "(foo), (abc)(bar)")
+    self.assertEqualsRegex("foo[[ABC:abc]] bar", "(foo)(abc), (bar)")
+    self.assertEqualsRegex("foo [[ABC:abc]] bar", "(foo), (abc), (bar)")
+
+  def test_AllKinds(self):
+    self.assertEqualsRegex("foo [[ABC:abc]]{{def}}bar", "(foo), (abc)(def)(bar)")
+    self.assertEqualsRegex("foo[[ABC:abc]] {{def}}bar", "(foo)(abc), (def)(bar)")
+    self.assertEqualsRegex("foo [[ABC:abc]] {{def}} bar", "(foo), (abc), (def), (bar)")
+
+  # # Test that variables and patterns are parsed correctly
+
+  def test_ValidPattern(self):
+    self.assertEqualsPattern("{{abc}}", "abc")
+    self.assertEqualsPattern("{{a[b]c}}", "a[b]c")
+    self.assertEqualsPattern("{{(a{bc})}}", "(a{bc})")
+
+  def test_ValidRef(self):
+    self.assertEqualsVarRef("[[ABC]]", "ABC")
+    self.assertEqualsVarRef("[[A1BC2]]", "A1BC2")
+
+  def test_ValidDef(self):
+    self.assertEqualsVarDef("[[ABC:abc]]", "ABC", "abc")
+    self.assertEqualsVarDef("[[ABC:ab:c]]", "ABC", "ab:c")
+    self.assertEqualsVarDef("[[ABC:a[b]c]]", "ABC", "a[b]c")
+    self.assertEqualsVarDef("[[ABC:(a[bc])]]", "ABC", "(a[bc])")
+
+  def test_Empty(self):
+    self.assertVariantNotEqual("{{}}", RegexExpression.Variant.Pattern)
+    self.assertVariantNotEqual("[[]]", RegexExpression.Variant.VarRef)
+    self.assertVariantNotEqual("[[:]]", RegexExpression.Variant.VarDef)
+
+  def test_InvalidVarName(self):
+    self.assertVariantNotEqual("[[0ABC]]", RegexExpression.Variant.VarRef)
+    self.assertVariantNotEqual("[[AB=C]]", RegexExpression.Variant.VarRef)
+    self.assertVariantNotEqual("[[ABC=]]", RegexExpression.Variant.VarRef)
+    self.assertVariantNotEqual("[[0ABC:abc]]", RegexExpression.Variant.VarDef)
+    self.assertVariantNotEqual("[[AB=C:abc]]", RegexExpression.Variant.VarDef)
+    self.assertVariantNotEqual("[[ABC=:abc]]", RegexExpression.Variant.VarDef)
+
+  def test_BodyMatchNotGreedy(self):
+    self.assertEqualsRegex("{{abc}}{{def}}", "(abc)(def)")
+    self.assertEqualsRegex("[[ABC:abc]][[DEF:def]]", "(abc)(def)")
+
+  def test_NoVarDefsInNotChecks(self):
+    with self.assertRaises(CheckerException):
+      self.parseAssertion("[[ABC:abc]]", "-NOT")
+
+
+class CheckerParser_FileLayoutTest(unittest.TestCase):
+
+  # Creates an instance of CheckerFile from provided info.
+  # Data format: [ ( <case-name>, [ ( <text>, <assert-variant> ), ... ] ), ... ]
+  def createFile(self, caseList):
+    testFile = CheckerFile("<test_file>")
+    for caseEntry in caseList:
+      caseName = caseEntry[0]
+      testCase = TestCase(testFile, caseName, 0)
+      assertionList = caseEntry[1]
+      for assertionEntry in assertionList:
+        content = assertionEntry[0]
+        variant = assertionEntry[1]
+        assertion = TestAssertion(testCase, variant, content, 0)
+        assertion.addExpression(RegexExpression.createText(content))
+    return testFile
+
+  def assertParsesTo(self, checkerText, expectedData):
+    expectedFile = self.createFile(expectedData)
+    actualFile = ParseCheckerStream("<test_file>", "CHECK", io.StringIO(ToUnicode(checkerText)))
+    return self.assertEqual(expectedFile, actualFile)
+
+  def test_EmptyFile(self):
+    self.assertParsesTo("", [])
+
+  def test_SingleGroup(self):
+    self.assertParsesTo(
+      """
+        // CHECK-START: Example Group
+        // CHECK:  foo
+        // CHECK:    bar
+      """,
+      [ ( "Example Group", [ ("foo", TestAssertion.Variant.InOrder),
+                             ("bar", TestAssertion.Variant.InOrder) ] ) ])
+
+  def test_MultipleGroups(self):
+    self.assertParsesTo(
+      """
+        // CHECK-START: Example Group1
+        // CHECK: foo
+        // CHECK: bar
+        // CHECK-START: Example Group2
+        // CHECK: abc
+        // CHECK: def
+      """,
+      [ ( "Example Group1", [ ("foo", TestAssertion.Variant.InOrder),
+                              ("bar", TestAssertion.Variant.InOrder) ] ),
+        ( "Example Group2", [ ("abc", TestAssertion.Variant.InOrder),
+                              ("def", TestAssertion.Variant.InOrder) ] ) ])
+
+  def test_AssertionVariants(self):
+    self.assertParsesTo(
+      """
+        // CHECK-START: Example Group
+        // CHECK:     foo
+        // CHECK-NOT: bar
+        // CHECK-DAG: abc
+        // CHECK-DAG: def
+      """,
+      [ ( "Example Group", [ ("foo", TestAssertion.Variant.InOrder),
+                             ("bar", TestAssertion.Variant.Not),
+                             ("abc", TestAssertion.Variant.DAG),
+                             ("def", TestAssertion.Variant.DAG) ] ) ])
diff --git a/tools/checker/match/__init__.py b/tools/checker/match/__init__.py
new file mode 100644
index 0000000000..33ef6de4ac
--- /dev/null
+++ b/tools/checker/match/__init__.py
@@ -0,0 +1,13 @@
+# Copyright (C) 2015 The Android Open Source Project
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+#   http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
diff --git a/tools/checker/match/file.py b/tools/checker/match/file.py
new file mode 100644
index 0000000000..d787fe5bfd
--- /dev/null
+++ b/tools/checker/match/file.py
@@ -0,0 +1,147 @@
+# Copyright (C) 2015 The Android Open Source Project
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+#   http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+
+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:]
+
+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.
+  """
+  i = 0
+  while i < len(lines) and lines[i].variant == variant:
+    i += 1
+  return lines[:i], lines[i:]
+
+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.
+  """
+  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 = []
+
+  # 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)
+
+  # 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.
+  """
+  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)
+
+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.
+  """
+  varState = {}
+  checkLines = checkGroup.assertions
+  outputLines = outputGroup.body
+  startLineNo = outputGroup.startLineNo
+
+  while checkLines:
+    # Extract the next sequence of location-independent checks to be matched.
+    notChecks, independentChecks, checkLines = __nextIndependentChecks(checkLines)
+
+    # Match the independent checks.
+    notOutput, outputLines, newStartLineNo, newVarState = \
+      __matchIndependentChecks(independentChecks, outputLines, startLineNo, varState)
+
+    # 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)
+
+    # Update variable state.
+    startLineNo = newStartLineNo
+    varState = newVarState
+
+def MatchFiles(checkerFile, c1File):
+  for testCase in checkerFile.testCases:
+    # TODO: Currently does not handle multiple occurrences of the same group
+    # name, e.g. when a pass is run multiple times. It will always try to
+    # 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",
+                  testCase.fileName, testCase.lineNo)
+    Logger.startTest(testCase.name)
+    __matchGroups(testCase, c1Pass)
+    Logger.testPassed()
diff --git a/tools/checker/match/line.py b/tools/checker/match/line.py
new file mode 100644
index 0000000000..eb1ab827eb
--- /dev/null
+++ b/tools/checker/match/line.py
@@ -0,0 +1,89 @@
+# Copyright (C) 2015 The Android Open Source Project
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+#   http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+
+from common.logger              import Logger
+from file_format.checker.struct import TestAssertion, RegexExpression
+
+import re
+
+def __isMatchAtStart(match):
+  """ Tests if the given Match occurred at the beginning of the line. """
+  return (match is not None) and (match.start() == 0)
+
+def __generatePattern(checkLine, linePart, varState):
+  """ Returns the regex pattern to be matched in the output line. Variable
+      references are substituted with their current values provided in the
+      'varState' argument.
+
+  An exception is raised if a referenced variable is undefined.
+  """
+  if linePart.variant == RegexExpression.Variant.VarRef:
+    try:
+      return re.escape(varState[linePart.name])
+    except KeyError:
+      Logger.testFailed("Use of undefined variable \"" + linePart.name + "\"",
+                        checkLine.fileName, checkLine.lineNo)
+  else:
+    return linePart.pattern
+
+def __isSeparated(outputLine, matchStart):
+  return (matchStart == 0) or (outputLine[matchStart - 1:matchStart].isspace())
+
+def MatchLines(checkLine, outputLine, initialVarState):
+  """ Attempts to match the check line against a line from the output file with
+      the given initial variable values. It returns the new variable state if
+      successful and None otherwise.
+  """
+  # Do the full matching on a shadow copy of the variable state. If the
+  # matching fails half-way, we will not need to revert the state.
+  varState = dict(initialVarState)
+
+  matchStart = 0
+  isAfterSeparator = True
+
+  # Now try to parse all of the parts of the check line in the right order.
+  # Variable values are updated on-the-fly, meaning that a variable can
+  # be referenced immediately after its definition.
+  for part in checkLine.expressions:
+    if part.variant == RegexExpression.Variant.Separator:
+      isAfterSeparator = True
+      continue
+
+    # Find the earliest match for this line part.
+    pattern = __generatePattern(checkLine, part, varState)
+    while True:
+      match = re.search(pattern, outputLine[matchStart:])
+      if (match is None) or (not isAfterSeparator and not __isMatchAtStart(match)):
+        return None
+      matchEnd = matchStart + match.end()
+      matchStart += match.start()
+
+      # Check if this is a valid match if we expect a whitespace separator
+      # before the matched text. Otherwise loop and look for another match.
+      if not isAfterSeparator or __isSeparated(outputLine, matchStart):
+        break
+      else:
+        matchStart += 1
+
+    if part.variant == RegexExpression.Variant.VarDef:
+      if part.name in varState:
+        Logger.testFailed("Multiple definitions of variable \"" + part.name + "\"",
+                          checkLine.fileName, checkLine.lineNo)
+      varState[part.name] = outputLine[matchStart:matchEnd]
+
+    matchStart = matchEnd
+    isAfterSeparator = False
+
+  # All parts were successfully matched. Return the new variable state.
+  return varState
diff --git a/tools/checker/match/test.py b/tools/checker/match/test.py
new file mode 100644
index 0000000000..976a87f914
--- /dev/null
+++ b/tools/checker/match/test.py
@@ -0,0 +1,326 @@
+# Copyright (C) 2015 The Android Open Source Project
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+#   http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+
+from common.testing                  import ToUnicode
+from file_format.c1visualizer.parser import ParseC1visualizerStream
+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.line                      import MatchLines
+
+import io
+import unittest
+
+CheckerException = SystemExit
+
+class MatchLines_Test(unittest.TestCase):
+
+  def createTestAssertion(self, checkerString):
+    checkerFile = CheckerFile("<checker-file>")
+    testCase = TestCase(checkerFile, "TestMethod TestPass", 0)
+    return ParseCheckerAssertion(testCase, checkerString, TestAssertion.Variant.InOrder, 0)
+
+  def tryMatch(self, checkerString, c1String, varState={}):
+    return MatchLines(self.createTestAssertion(checkerString), ToUnicode(c1String), varState)
+
+  def matches(self, checkerString, c1String, varState={}):
+    return self.tryMatch(checkerString, c1String, varState) is not None
+
+  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.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.assertTrue(self.matches("foo bar", "foo X bar"))
+    self.assertFalse(self.matches("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"))
+
+  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"}))
+    with self.assertRaises(CheckerException):
+      self.assertTrue(self.matches("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"))
+
+    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"))
+
+  def test_NoVariableRedefinition(self):
+    with self.assertRaises(CheckerException):
+      self.matches("[[X:...]][[X]][[X:...]][[X]]", "foofoobarbar")
+
+  def test_EnvNotChangedOnPartialMatch(self):
+    env = {"Y": "foo"}
+    self.assertFalse(self.matches("[[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"))
+
+
+class MatchFiles_Test(unittest.TestCase):
+
+  def matches(self, checkerString, c1String):
+    checkerString = \
+      """
+        // CHECK-START: MyMethod MyPass
+      """ + checkerString
+    c1String = \
+      """
+        begin_compilation
+          name "MyMethod"
+          method "MyMethod"
+          date 1234
+        end_compilation
+        begin_cfg
+          name "MyPass"
+      """ + c1String + \
+      """
+        end_cfg
+      """
+    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
+
+  def test_Text(self):
+    self.assertTrue(self.matches( "// CHECK: foo bar", "foo bar"))
+    self.assertFalse(self.matches("// 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"))
+
+  def test_Variables(self):
+    self.assertTrue(self.matches(
+    """
+      // CHECK: foo[[X:.]]bar
+      // CHECK: abc[[X]]def
+    """,
+    """
+      foo bar
+      abc def
+    """))
+    self.assertTrue(self.matches(
+    """
+      // CHECK: foo[[X:([0-9]+)]]bar
+      // CHECK: abc[[X]]def
+      // CHECK: ### [[X]] ###
+    """,
+    """
+      foo1234bar
+      abc1234def
+      ### 1234 ###
+    """))
+    self.assertFalse(self.matches(
+    """
+      // CHECK: foo[[X:([0-9]+)]]bar
+      // CHECK: abc[[X]]def
+    """,
+    """
+      foo1234bar
+      abc1235def
+    """))
+
+  def test_InOrderAssertions(self):
+    self.assertTrue(self.matches(
+    """
+      // CHECK: foo
+      // CHECK: bar
+    """,
+    """
+      foo
+      bar
+    """))
+    self.assertFalse(self.matches(
+    """
+      // CHECK: foo
+      // CHECK: bar
+    """,
+    """
+      bar
+      foo
+    """))
+
+  def test_DagAssertions(self):
+    self.assertTrue(self.matches(
+    """
+      // CHECK-DAG: foo
+      // CHECK-DAG: bar
+    """,
+    """
+      foo
+      bar
+    """))
+    self.assertTrue(self.matches(
+    """
+      // CHECK-DAG: foo
+      // CHECK-DAG: bar
+    """,
+    """
+      bar
+      foo
+    """))
+
+  def test_DagAssertionsScope(self):
+    self.assertTrue(self.matches(
+    """
+      // CHECK:     foo
+      // CHECK-DAG: abc
+      // CHECK-DAG: def
+      // CHECK:     bar
+    """,
+    """
+      foo
+      def
+      abc
+      bar
+    """))
+    self.assertFalse(self.matches(
+    """
+      // CHECK:     foo
+      // CHECK-DAG: abc
+      // CHECK-DAG: def
+      // CHECK:     bar
+    """,
+    """
+      foo
+      abc
+      bar
+      def
+    """))
+    self.assertFalse(self.matches(
+    """
+      // CHECK:     foo
+      // CHECK-DAG: abc
+      // CHECK-DAG: def
+      // CHECK:     bar
+    """,
+    """
+      foo
+      def
+      bar
+      abc
+    """))
+
+  def test_NotAssertions(self):
+    self.assertTrue(self.matches(
+    """
+      // CHECK-NOT: foo
+    """,
+    """
+      abc
+      def
+    """))
+    self.assertFalse(self.matches(
+    """
+      // CHECK-NOT: foo
+    """,
+    """
+      abc foo
+      def
+    """))
+    self.assertFalse(self.matches(
+    """
+      // CHECK-NOT: foo
+      // CHECK-NOT: bar
+    """,
+    """
+      abc
+      def bar
+    """))
+
+  def test_NotAssertionsScope(self):
+    self.assertTrue(self.matches(
+    """
+      // CHECK:     abc
+      // CHECK-NOT: foo
+      // CHECK:     def
+    """,
+    """
+      abc
+      def
+    """))
+    self.assertTrue(self.matches(
+    """
+      // CHECK:     abc
+      // CHECK-NOT: foo
+      // CHECK:     def
+    """,
+    """
+      abc
+      def
+      foo
+    """))
+    self.assertFalse(self.matches(
+    """
+      // CHECK:     abc
+      // CHECK-NOT: foo
+      // CHECK:     def
+    """,
+    """
+      abc
+      foo
+      def
+    """))
+
+  def test_LineOnlyMatchesOnce(self):
+    self.assertTrue(self.matches(
+    """
+      // CHECK-DAG: foo
+      // CHECK-DAG: foo
+    """,
+    """
+      foo
+      abc
+      foo
+    """))
+    self.assertFalse(self.matches(
+    """
+      // CHECK-DAG: foo
+      // CHECK-DAG: foo
+    """,
+    """
+      foo
+      abc
+      bar
+    """))
diff --git a/tools/checker/run_unit_tests.py b/tools/checker/run_unit_tests.py
new file mode 100755
index 0000000000..01708dbd27
--- /dev/null
+++ b/tools/checker/run_unit_tests.py
@@ -0,0 +1,29 @@
+#!/usr/bin/env python2
+#
+# Copyright (C) 2014 The Android Open Source Project
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+#   http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+
+from common.logger                 import Logger
+from file_format.c1visualizer.test import C1visualizerParser_Test
+from file_format.checker.test      import CheckerParser_PrefixTest, \
+                                          CheckerParser_RegexExpressionTest, \
+                                          CheckerParser_FileLayoutTest
+from match.test                    import MatchLines_Test, \
+                                          MatchFiles_Test
+
+import unittest
+
+if __name__ == '__main__':
+  Logger.Verbosity = Logger.Level.NoOutput
+  unittest.main(verbosity=2)
diff --git a/tools/checker_test.py b/tools/checker_test.py
deleted file mode 100755
index 667ca90079..0000000000
--- a/tools/checker_test.py
+++ /dev/null
@@ -1,474 +0,0 @@
-#!/usr/bin/env python2
-#
-# Copyright (C) 2014 The Android Open Source Project
-#
-# Licensed under the Apache License, Version 2.0 (the "License");
-# you may not use this file except in compliance with the License.
-# You may obtain a copy of the License at
-#
-#   http://www.apache.org/licenses/LICENSE-2.0
-#
-# Unless required by applicable law or agreed to in writing, software
-# distributed under the License is distributed on an "AS IS" BASIS,
-# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-# See the License for the specific language governing permissions and
-# limitations under the License.
-
-# This is a test file which exercises all feautres supported by the domain-
-# specific markup language implemented by Checker.
-
-import checker
-import io
-import unittest
-
-# The parent type of exception expected to be thrown by Checker during tests.
-# It must be specific enough to not cover exceptions thrown due to actual flaws
-# in Checker.
-CheckerException = SystemExit
-
-
-class TestCheckFile_PrefixExtraction(unittest.TestCase):
-  def __tryParse(self, string):
-    checkFile = checker.CheckFile(None, [])
-    return checkFile._extractLine("CHECK", string)
-
-  def test_InvalidFormat(self):
-    self.assertIsNone(self.__tryParse("CHECK"))
-    self.assertIsNone(self.__tryParse(":CHECK"))
-    self.assertIsNone(self.__tryParse("CHECK:"))
-    self.assertIsNone(self.__tryParse("//CHECK"))
-    self.assertIsNone(self.__tryParse("#CHECK"))
-
-    self.assertIsNotNone(self.__tryParse("//CHECK:foo"))
-    self.assertIsNotNone(self.__tryParse("#CHECK:bar"))
-
-  def test_InvalidLabel(self):
-    self.assertIsNone(self.__tryParse("//ACHECK:foo"))
-    self.assertIsNone(self.__tryParse("#ACHECK:foo"))
-
-  def test_NotFirstOnTheLine(self):
-    self.assertIsNone(self.__tryParse("A// CHECK: foo"))
-    self.assertIsNone(self.__tryParse("A # CHECK: foo"))
-    self.assertIsNone(self.__tryParse("// // CHECK: foo"))
-    self.assertIsNone(self.__tryParse("# # CHECK: foo"))
-
-  def test_WhitespaceAgnostic(self):
-    self.assertIsNotNone(self.__tryParse("  //CHECK: foo"))
-    self.assertIsNotNone(self.__tryParse("//  CHECK: foo"))
-    self.assertIsNotNone(self.__tryParse("    //CHECK: foo"))
-    self.assertIsNotNone(self.__tryParse("//    CHECK: foo"))
-
-
-class TestCheckLine_Parse(unittest.TestCase):
-  def __getPartPattern(self, linePart):
-    if linePart.variant == checker.CheckElement.Variant.Separator:
-      return "\s+"
-    else:
-      return linePart.pattern
-
-  def __getRegex(self, checkLine):
-    return "".join(map(lambda x: "(" + self.__getPartPattern(x) + ")", checkLine.lineParts))
-
-  def __tryParse(self, string):
-    return checker.CheckLine(string)
-
-  def __parsesTo(self, string, expected):
-    self.assertEqual(expected, self.__getRegex(self.__tryParse(string)))
-
-  def __tryParseNot(self, string):
-    return checker.CheckLine(string, checker.CheckLine.Variant.Not)
-
-  def __parsesPattern(self, string, pattern):
-    line = self.__tryParse(string)
-    self.assertEqual(1, len(line.lineParts))
-    self.assertEqual(checker.CheckElement.Variant.Pattern, line.lineParts[0].variant)
-    self.assertEqual(pattern, line.lineParts[0].pattern)
-
-  def __parsesVarRef(self, string, name):
-    line = self.__tryParse(string)
-    self.assertEqual(1, len(line.lineParts))
-    self.assertEqual(checker.CheckElement.Variant.VarRef, line.lineParts[0].variant)
-    self.assertEqual(name, line.lineParts[0].name)
-
-  def __parsesVarDef(self, string, name, body):
-    line = self.__tryParse(string)
-    self.assertEqual(1, len(line.lineParts))
-    self.assertEqual(checker.CheckElement.Variant.VarDef, line.lineParts[0].variant)
-    self.assertEqual(name, line.lineParts[0].name)
-    self.assertEqual(body, line.lineParts[0].pattern)
-
-  def __doesNotParse(self, string, partType):
-    line = self.__tryParse(string)
-    self.assertEqual(1, len(line.lineParts))
-    self.assertNotEqual(partType, line.lineParts[0].variant)
-
-  # Test that individual parts of the line are recognized
-
-  def test_TextOnly(self):
-    self.__parsesTo("foo", "(foo)")
-    self.__parsesTo("  foo  ", "(foo)")
-    self.__parsesTo("f$o^o", "(f\$o\^o)")
-
-  def test_TextWithWhitespace(self):
-    self.__parsesTo("foo bar", "(foo)(\s+)(bar)")
-    self.__parsesTo("foo   bar", "(foo)(\s+)(bar)")
-
-  def test_RegexOnly(self):
-    self.__parsesPattern("{{a?b.c}}", "a?b.c")
-
-  def test_VarRefOnly(self):
-    self.__parsesVarRef("[[ABC]]", "ABC")
-
-  def test_VarDefOnly(self):
-    self.__parsesVarDef("[[ABC:a?b.c]]", "ABC", "a?b.c")
-
-  def test_TextWithRegex(self):
-    self.__parsesTo("foo{{abc}}bar", "(foo)(abc)(bar)")
-
-  def test_TextWithVar(self):
-    self.__parsesTo("foo[[ABC:abc]]bar", "(foo)(abc)(bar)")
-
-  def test_PlainWithRegexAndWhitespaces(self):
-    self.__parsesTo("foo {{abc}}bar", "(foo)(\s+)(abc)(bar)")
-    self.__parsesTo("foo{{abc}} bar", "(foo)(abc)(\s+)(bar)")
-    self.__parsesTo("foo {{abc}} bar", "(foo)(\s+)(abc)(\s+)(bar)")
-
-  def test_PlainWithVarAndWhitespaces(self):
-    self.__parsesTo("foo [[ABC:abc]]bar", "(foo)(\s+)(abc)(bar)")
-    self.__parsesTo("foo[[ABC:abc]] bar", "(foo)(abc)(\s+)(bar)")
-    self.__parsesTo("foo [[ABC:abc]] bar", "(foo)(\s+)(abc)(\s+)(bar)")
-
-  def test_AllKinds(self):
-    self.__parsesTo("foo [[ABC:abc]]{{def}}bar", "(foo)(\s+)(abc)(def)(bar)")
-    self.__parsesTo("foo[[ABC:abc]] {{def}}bar", "(foo)(abc)(\s+)(def)(bar)")
-    self.__parsesTo("foo [[ABC:abc]] {{def}} bar", "(foo)(\s+)(abc)(\s+)(def)(\s+)(bar)")
-
-  # Test that variables and patterns are parsed correctly
-
-  def test_ValidPattern(self):
-    self.__parsesPattern("{{abc}}", "abc")
-    self.__parsesPattern("{{a[b]c}}", "a[b]c")
-    self.__parsesPattern("{{(a{bc})}}", "(a{bc})")
-
-  def test_ValidRef(self):
-    self.__parsesVarRef("[[ABC]]", "ABC")
-    self.__parsesVarRef("[[A1BC2]]", "A1BC2")
-
-  def test_ValidDef(self):
-    self.__parsesVarDef("[[ABC:abc]]", "ABC", "abc")
-    self.__parsesVarDef("[[ABC:ab:c]]", "ABC", "ab:c")
-    self.__parsesVarDef("[[ABC:a[b]c]]", "ABC", "a[b]c")
-    self.__parsesVarDef("[[ABC:(a[bc])]]", "ABC", "(a[bc])")
-
-  def test_Empty(self):
-    self.__doesNotParse("{{}}", checker.CheckElement.Variant.Pattern)
-    self.__doesNotParse("[[]]", checker.CheckElement.Variant.VarRef)
-    self.__doesNotParse("[[:]]", checker.CheckElement.Variant.VarDef)
-
-  def test_InvalidVarName(self):
-    self.__doesNotParse("[[0ABC]]", checker.CheckElement.Variant.VarRef)
-    self.__doesNotParse("[[AB=C]]", checker.CheckElement.Variant.VarRef)
-    self.__doesNotParse("[[ABC=]]", checker.CheckElement.Variant.VarRef)
-    self.__doesNotParse("[[0ABC:abc]]", checker.CheckElement.Variant.VarDef)
-    self.__doesNotParse("[[AB=C:abc]]", checker.CheckElement.Variant.VarDef)
-    self.__doesNotParse("[[ABC=:abc]]", checker.CheckElement.Variant.VarDef)
-
-  def test_BodyMatchNotGreedy(self):
-    self.__parsesTo("{{abc}}{{def}}", "(abc)(def)")
-    self.__parsesTo("[[ABC:abc]][[DEF:def]]", "(abc)(def)")
-
-  def test_NoVarDefsInNotChecks(self):
-    with self.assertRaises(CheckerException):
-      self.__tryParseNot("[[ABC:abc]]")
-
-class TestCheckLine_Match(unittest.TestCase):
-  def __matchSingle(self, checkString, outputString, varState={}):
-    checkLine = checker.CheckLine(checkString)
-    newVarState = checkLine.match(outputString, varState)
-    self.assertIsNotNone(newVarState)
-    return newVarState
-
-  def __notMatchSingle(self, checkString, outputString, varState={}):
-    checkLine = checker.CheckLine(checkString)
-    self.assertIsNone(checkLine.match(outputString, varState))
-
-  def test_TextAndWhitespace(self):
-    self.__matchSingle("foo", "foo")
-    self.__matchSingle("foo", "  foo  ")
-    self.__matchSingle("foo", "foo bar")
-    self.__notMatchSingle("foo", "XfooX")
-    self.__notMatchSingle("foo", "zoo")
-
-    self.__matchSingle("foo bar", "foo   bar")
-    self.__matchSingle("foo bar", "abc foo bar def")
-    self.__matchSingle("foo bar", "foo foo bar bar")
-
-    self.__matchSingle("foo bar", "foo X bar")
-    self.__notMatchSingle("foo bar", "foo Xbar")
-
-  def test_Pattern(self):
-    self.__matchSingle("foo{{A|B}}bar", "fooAbar")
-    self.__matchSingle("foo{{A|B}}bar", "fooBbar")
-    self.__notMatchSingle("foo{{A|B}}bar", "fooCbar")
-
-  def test_VariableReference(self):
-    self.__matchSingle("foo[[X]]bar", "foobar", {"X": ""})
-    self.__matchSingle("foo[[X]]bar", "fooAbar", {"X": "A"})
-    self.__matchSingle("foo[[X]]bar", "fooBbar", {"X": "B"})
-    self.__notMatchSingle("foo[[X]]bar", "foobar", {"X": "A"})
-    self.__notMatchSingle("foo[[X]]bar", "foo bar", {"X": "A"})
-    with self.assertRaises(CheckerException):
-      self.__matchSingle("foo[[X]]bar", "foobar", {})
-
-  def test_VariableDefinition(self):
-    self.__matchSingle("foo[[X:A|B]]bar", "fooAbar")
-    self.__matchSingle("foo[[X:A|B]]bar", "fooBbar")
-    self.__notMatchSingle("foo[[X:A|B]]bar", "fooCbar")
-
-    env = self.__matchSingle("foo[[X:A.*B]]bar", "fooABbar", {})
-    self.assertEqual(env, {"X": "AB"})
-    env = self.__matchSingle("foo[[X:A.*B]]bar", "fooAxxBbar", {})
-    self.assertEqual(env, {"X": "AxxB"})
-
-    self.__matchSingle("foo[[X:A|B]]bar[[X]]baz", "fooAbarAbaz")
-    self.__matchSingle("foo[[X:A|B]]bar[[X]]baz", "fooBbarBbaz")
-    self.__notMatchSingle("foo[[X:A|B]]bar[[X]]baz", "fooAbarBbaz")
-
-  def test_NoVariableRedefinition(self):
-    with self.assertRaises(CheckerException):
-      self.__matchSingle("[[X:...]][[X]][[X:...]][[X]]", "foofoobarbar")
-
-  def test_EnvNotChangedOnPartialMatch(self):
-    env = {"Y": "foo"}
-    self.__notMatchSingle("[[X:A]]bar", "Abaz", env)
-    self.assertFalse("X" in env.keys())
-
-  def test_VariableContentEscaped(self):
-    self.__matchSingle("[[X:..]]foo[[X]]", ".*foo.*")
-    self.__notMatchSingle("[[X:..]]foo[[X]]", ".*fooAAAA")
-
-
-CheckVariant = checker.CheckLine.Variant
-
-def prepareSingleCheck(line):
-  if isinstance(line, str):
-    return checker.CheckLine(line)
-  else:
-    return checker.CheckLine(line[0], line[1])
-
-def prepareChecks(lines):
-  if isinstance(lines, str):
-    lines = lines.splitlines()
-  return list(map(lambda line: prepareSingleCheck(line), lines))
-
-
-class TestCheckGroup_Match(unittest.TestCase):
-  def __matchMulti(self, checkLines, outputString):
-    checkGroup = checker.CheckGroup("MyGroup", prepareChecks(checkLines))
-    outputGroup = checker.OutputGroup("MyGroup", outputString.splitlines())
-    return checkGroup.match(outputGroup)
-
-  def __notMatchMulti(self, checkString, outputString):
-    with self.assertRaises(CheckerException):
-      self.__matchMulti(checkString, outputString)
-
-  def test_TextAndPattern(self):
-    self.__matchMulti("""foo bar
-                         abc {{def}}""",
-                      """foo bar
-                         abc def""");
-    self.__matchMulti("""foo bar
-                         abc {{de.}}""",
-                      """=======
-                         foo bar
-                         =======
-                         abc de#
-                         =======""");
-    self.__notMatchMulti("""//XYZ: foo bar
-                            //XYZ: abc {{def}}""",
-                         """=======
-                            foo bar
-                            =======
-                            abc de#
-                            =======""");
-
-  def test_Variables(self):
-    self.__matchMulti("""foo[[X:.]]bar
-                         abc[[X]]def""",
-                      """foo bar
-                         abc def""");
-    self.__matchMulti("""foo[[X:([0-9]+)]]bar
-                         abc[[X]]def
-                         ### [[X]] ###""",
-                      """foo1234bar
-                         abc1234def
-                         ### 1234 ###""");
-
-  def test_Ordering(self):
-    self.__matchMulti([("foo", CheckVariant.InOrder),
-                       ("bar", CheckVariant.InOrder)],
-                      """foo
-                         bar""")
-    self.__notMatchMulti([("foo", CheckVariant.InOrder),
-                          ("bar", CheckVariant.InOrder)],
-                         """bar
-                            foo""")
-    self.__matchMulti([("abc", CheckVariant.DAG),
-                       ("def", CheckVariant.DAG)],
-                      """abc
-                         def""")
-    self.__matchMulti([("abc", CheckVariant.DAG),
-                       ("def", CheckVariant.DAG)],
-                      """def
-                         abc""")
-    self.__matchMulti([("foo", CheckVariant.InOrder),
-                       ("abc", CheckVariant.DAG),
-                       ("def", CheckVariant.DAG),
-                       ("bar", CheckVariant.InOrder)],
-                      """foo
-                         def
-                         abc
-                         bar""")
-    self.__notMatchMulti([("foo", CheckVariant.InOrder),
-                          ("abc", CheckVariant.DAG),
-                          ("def", CheckVariant.DAG),
-                          ("bar", CheckVariant.InOrder)],
-                         """foo
-                            abc
-                            bar""")
-    self.__notMatchMulti([("foo", CheckVariant.InOrder),
-                          ("abc", CheckVariant.DAG),
-                          ("def", CheckVariant.DAG),
-                          ("bar", CheckVariant.InOrder)],
-                         """foo
-                            def
-                            bar""")
-
-  def test_NotAssertions(self):
-    self.__matchMulti([("foo", CheckVariant.Not)],
-                      """abc
-                         def""")
-    self.__notMatchMulti([("foo", CheckVariant.Not)],
-                         """abc foo
-                            def""")
-    self.__notMatchMulti([("foo", CheckVariant.Not),
-                          ("bar", CheckVariant.Not)],
-                         """abc
-                            def bar""")
-
-  def test_LineOnlyMatchesOnce(self):
-    self.__matchMulti([("foo", CheckVariant.DAG),
-                       ("foo", CheckVariant.DAG)],
-                       """foo
-                          foo""")
-    self.__notMatchMulti([("foo", CheckVariant.DAG),
-                          ("foo", CheckVariant.DAG)],
-                          """foo
-                             bar""")
-
-class TestOutputFile_Parse(unittest.TestCase):
-  def __parsesTo(self, string, expected):
-    if isinstance(string, str):
-      string = unicode(string)
-    outputStream = io.StringIO(string)
-    return self.assertEqual(checker.OutputFile(outputStream).groups, expected)
-
-  def test_NoInput(self):
-    self.__parsesTo(None, [])
-    self.__parsesTo("", [])
-
-  def test_SingleGroup(self):
-    self.__parsesTo("""begin_compilation
-                         method "MyMethod"
-                       end_compilation
-                       begin_cfg
-                         name "pass1"
-                         foo
-                         bar
-                       end_cfg""",
-                    [ checker.OutputGroup("MyMethod pass1", [ "foo", "bar" ]) ])
-
-  def test_MultipleGroups(self):
-    self.__parsesTo("""begin_compilation
-                         name "xyz1"
-                         method "MyMethod1"
-                         date 1234
-                       end_compilation
-                       begin_cfg
-                         name "pass1"
-                         foo
-                         bar
-                       end_cfg
-                       begin_cfg
-                         name "pass2"
-                         abc
-                         def
-                       end_cfg""",
-                    [ checker.OutputGroup("MyMethod1 pass1", [ "foo", "bar" ]),
-                      checker.OutputGroup("MyMethod1 pass2", [ "abc", "def" ]) ])
-
-    self.__parsesTo("""begin_compilation
-                         name "xyz1"
-                         method "MyMethod1"
-                         date 1234
-                       end_compilation
-                       begin_cfg
-                         name "pass1"
-                         foo
-                         bar
-                       end_cfg
-                       begin_compilation
-                         name "xyz2"
-                         method "MyMethod2"
-                         date 5678
-                       end_compilation
-                       begin_cfg
-                         name "pass2"
-                         abc
-                         def
-                       end_cfg""",
-                    [ checker.OutputGroup("MyMethod1 pass1", [ "foo", "bar" ]),
-                      checker.OutputGroup("MyMethod2 pass2", [ "abc", "def" ]) ])
-
-class TestCheckFile_Parse(unittest.TestCase):
-  def __parsesTo(self, string, expected):
-    if isinstance(string, str):
-      string = unicode(string)
-    checkStream = io.StringIO(string)
-    return self.assertEqual(checker.CheckFile("CHECK", checkStream).groups, expected)
-
-  def test_NoInput(self):
-    self.__parsesTo(None, [])
-    self.__parsesTo("", [])
-
-  def test_SingleGroup(self):
-    self.__parsesTo("""// CHECK-START: Example Group
-                       // CHECK:  foo
-                       // CHECK:    bar""",
-                    [ checker.CheckGroup("Example Group", prepareChecks([ "foo", "bar" ])) ])
-
-  def test_MultipleGroups(self):
-    self.__parsesTo("""// CHECK-START: Example Group1
-                       // CHECK: foo
-                       // CHECK: bar
-                       // CHECK-START: Example Group2
-                       // CHECK: abc
-                       // CHECK: def""",
-                    [ checker.CheckGroup("Example Group1", prepareChecks([ "foo", "bar" ])),
-                      checker.CheckGroup("Example Group2", prepareChecks([ "abc", "def" ])) ])
-
-  def test_CheckVariants(self):
-    self.__parsesTo("""// CHECK-START: Example Group
-                       // CHECK:     foo
-                       // CHECK-NOT: bar
-                       // CHECK-DAG: abc
-                       // CHECK-DAG: def""",
-                    [ checker.CheckGroup("Example Group",
-                                         prepareChecks([ ("foo", CheckVariant.InOrder),
-                                                         ("bar", CheckVariant.Not),
-                                                         ("abc", CheckVariant.DAG),
-                                                         ("def", CheckVariant.DAG) ])) ])
-
-if __name__ == '__main__':
-  checker.Logger.Verbosity = checker.Logger.Level.NoOutput
-  unittest.main()