Merge remote-tracking branch 'aosp/upstream-master' into up-shaderc2ndk-r21endk-r21dndk-r21cndk-r21bndk-r21-rc1ndk-r21-beta2ndk-r21-beta1ndk-r21ndk-release-r21

Initial drop of google/effcee from GitHub

Test: checkbuild.py on Linux; unit tests on Windows
Change-Id: Id931fb12867fc221e3f449fc32bec428f54f5c70

35 files changed, 4002 insertions, 0 deletions

diff --git a/.appveyor.yml b/.appveyor.yml
new file mode 100644
index 0000000..6fb6bc5
--- /dev/null
+++ b/.appveyor.yml
@@ -0,0 +1,56 @@
+# Windows Build Configuration for AppVeyor
+# http://www.appveyor.com/docs/appveyor-yml
+
+# version format
+version: "{build}"
+
+os:
+  - Visual Studio 2017
+  - Visual Studio 2015
+
+platform:
+  - x64
+
+configuration:
+  - Debug
+  - Release
+
+branches:
+  only:
+    - master
+
+matrix:
+  fast_finish: true
+  exclude:
+    - os: Visual Studio 2015
+      configuration: Debug
+
+# scripts that run after cloning repository
+install:
+  - git clone --depth=1 https://github.com/google/googletest.git      third_party/googletest
+  - git clone --depth=1 https://github.com/google/re2.git             third_party/re2
+
+before_build:
+  - if "%APPVEYOR_BUILD_WORKER_IMAGE%"=="Visual Studio 2015" (call "C:\Program Files (x86)\Microsoft Visual Studio 14.0\VC\vcvarsall.bat" x86_amd64)
+  - if "%APPVEYOR_BUILD_WORKER_IMAGE%"=="Visual Studio 2017" (call "C:\Program Files (x86)\Microsoft Visual Studio\2017\Community\VC\Auxiliary\Build\vcvarsall.bat" x86_amd64)
+
+build:
+  parallel: true  # enable MSBuild parallel builds
+  verbosity: minimal
+
+build_script:
+  - mkdir build && cd build
+  - cmake .. -DCMAKE_INSTALL_PREFIX=install -DRE2_BUILD_TESTING=OFF
+  - cmake --build . --target install --config %CONFIGURATION%
+
+test_script:
+  - ctest -C %CONFIGURATION% --output-on-failure
+
+notifications:
+  - provider: Email
+    to:
+      - dneto@google.com
+    subject: 'Effcee Windows Build #{{buildVersion}}: {{status}}'
+    on_build_success: false
+    on_build_failure: true
+    on_build_status_changed: true
diff --git a/.clang-format b/.clang-format
new file mode 100644
index 0000000..dd860a0
--- /dev/null
+++ b/.clang-format
@@ -0,0 +1,6 @@
+---
+Language: Cpp
+BasedOnStyle: Google
+DerivePointerAlignment: false
+PointerAlignment: Left
+...
diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..acde7b6
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1,12 @@
+build/
+build-*/
+out/
+*.pyc
+*.swp
+*~
+compile_commands.json
+.ycm_extra_conf.py
+cscope.*
+third_party/re2/
+third_party/googletest/
+.DS_Store
diff --git a/.travis.yml b/.travis.yml
new file mode 100644
index 0000000..ed046b6
--- /dev/null
+++ b/.travis.yml
@@ -0,0 +1,67 @@
+# Linux Build Configuration for Travis
+
+language: cpp
+
+os:
+  - linux
+  - osx
+
+# Use Ubuntu 14.04 LTS (Trusty) as the Linux testing environment.
+sudo: required
+dist: trusty
+
+env:
+  - EFFCEE_BUILD_TYPE=Release
+  - EFFCEE_BUILD_TYPE=Debug
+
+compiler:
+  - clang
+  - gcc
+
+matrix:
+  fast_finish: true # Show final status immediately if a test fails.
+  exclude:
+    # Skip GCC builds on macOS.
+    - os: osx
+      compiler: gcc
+
+cache:
+  apt: true
+
+branches:
+  only:
+    - master
+
+addons:
+  apt:
+    packages:
+      - clang
+      - ninja-build
+
+before_install:
+  # Install ninja on macOS.
+  - if [[ "$TRAVIS_OS_NAME" == "osx" ]]; then brew install ninja; fi
+
+install:
+  - if [[ "$TRAVIS_OS_NAME" == "linux" && "$CC" == "clang" ]]; then
+      export CC=clang CXX=clang++;
+    fi
+
+before_script:
+  - git clone --depth=1 https://github.com/google/googletest  third_party/googletest
+  - git clone --depth=1 https://github.com/google/re2         third_party/re2
+
+script:
+  - mkdir build && cd build
+  - cmake -DCMAKE_BUILD_TYPE=${EFFCEE_BUILD_TYPE:-Debug}
+          -DRE2_BUILD_TESTING=OFF
+          -GNinja ..;
+  - ninja
+  - ctest
+
+notifications:
+  email:
+    recipients:
+      - dneto@google.com
+    on_success: change
+    on_failure: always
diff --git a/AUTHORS b/AUTHORS
new file mode 100644
index 0000000..ec817af
--- /dev/null
+++ b/AUTHORS
@@ -0,0 +1,9 @@
+# This is the official list of Effcee authors for copyright purposes.
+# This file is distinct from the CONTRIBUTORS files.
+# See the latter for an explanation.
+
+# Names should be added to this file as:
+# Name or Organization <email address>
+# The email address is not required for organizations.
+
+Google Inc.
diff --git a/CHANGES b/CHANGES
new file mode 100644
index 0000000..4fbd0c7
--- /dev/null
+++ b/CHANGES
@@ -0,0 +1,13 @@
+Revision history for Effcee
+
+v2018.2-dev 2018-10-05
+ - Fixes:
+   #23: Avoid StringPiece::as_string to enhance portability.
+
+v2018.1 2018-10-05
+ - Require CMake 3.1 or later
+ - Require C++11
+ - Travis-CI testing uses stock clang, instead of clang-3.6 (which is old by now)
+
+v2018.0 2018-10-05
+ - Mature enough for production use by third party projects such as DXC and SPIRV-Tools.
diff --git a/CMakeLists.txt b/CMakeLists.txt
new file mode 100644
index 0000000..67087b7
--- /dev/null
+++ b/CMakeLists.txt
@@ -0,0 +1,40 @@
+cmake_minimum_required(VERSION 3.1)
+project(effcee C CXX)
+enable_testing()
+
+set(CMAKE_CXX_STANDARD 11)
+set(CMAKE_CXX_STANDARD_REQUIRED ON)
+
+option(EFFCEE_BUILD_TESTING "Enable testing for Effcee" ON)
+if(${EFFCEE_BUILD_TESTING})
+  message(STATUS "Configuring Effcee to build tests.")
+  if(MSVC)
+    # Our tests use ::testing::Combine.  Force the ability to use it, working
+    # around googletest's possibly faulty compiler detection logic.
+    # See https://github.com/google/googletest/issues/1352
+    add_definitions(-DGTEST_HAS_COMBINE=1)
+  endif(MSVC)
+else()
+  message(STATUS "Configuring Effcee to avoid building tests.")
+endif()
+
+option(EFFCEE_BUILD_SAMPLES "Enable building sample Effcee programs" ON)
+if(${EFFCEE_BUILD_SAMPLES})
+  message(STATUS "Configuring Effcee to build samples.")
+else()
+  message(STATUS "Configuring Effcee to avoid building samples.")
+endif()
+
+# RE2 needs Pthreads on non-WIN32
+set(CMAKE_THREAD_LIBS_INIT "")
+find_package(Threads)
+
+include(cmake/setup_build.cmake)
+include(cmake/utils.cmake)
+
+add_subdirectory(third_party)
+add_subdirectory(effcee)
+
+if(${EFFCEE_BUILD_SAMPLES})
+  add_subdirectory(examples)
+endif()
diff --git a/CONTRIBUTING.md b/CONTRIBUTING.md
new file mode 100644
index 0000000..96cf672
--- /dev/null
+++ b/CONTRIBUTING.md
@@ -0,0 +1,27 @@
+# Contributing to Effcee
+
+Want to contribute?  Great!  First, read this page (including the small print at
+the end).  Then, have a look at [`DEVELOPMENT.howto.md`](DEVELOPMENT.howto.md),
+which contains useful info to guide you along the way.
+
+## Before you contribute
+
+Before we can use your code, you must sign the
+[Google Individual Contributor License Agreement](https://developers.google.com/open-source/cla/individual?csw=1)
+(CLA), which you can do online. The CLA is necessary mainly because you own the
+copyright to your changes, even after your contribution becomes part of our
+codebase, so we need your permission to use and distribute your code. We also
+need to be sure of various other things -- for instance that you'll tell us if
+you know that your code infringes on other people's patents. You don't have to
+sign the CLA until after you've submitted your code for review and a member has
+approved it, but you must do it before we can put your code into our codebase.
+
+Before you start working on a larger contribution, you should get in touch with
+us first through the issue tracker with your idea so that we can help out and
+possibly guide you. Coordinating up front makes it much easier to avoid
+frustration later on.
+
+## The small print
+
+Contributions made by corporations are covered by a different agreement than
+the one above, the Software Grant and Corporate Contributor License Agreement.
diff --git a/CONTRIBUTORS b/CONTRIBUTORS
new file mode 100644
index 0000000..087914a
--- /dev/null
+++ b/CONTRIBUTORS
@@ -0,0 +1,15 @@
+# People who have agreed to one of the CLAs and can contribute patches.
+# The AUTHORS file lists the copyright holders; this file
+# lists people.  For example, Google employees are listed here
+# but not in AUTHORS, because Google holds the copyright.
+#
+# https://developers.google.com/open-source/cla/individual
+# https://developers.google.com/open-source/cla/corporate
+#
+# Names should be added to this file as:
+#     Name <email address>
+
+Alan Baker <alanbaker@google.com>
+Ehsan Nasiri <ehsannas@gmail.com>
+David Neto <dneto@google.com>
+Lei Zhang <antiagainst@google.com>
diff --git a/DEVELOPMENT.howto.md b/DEVELOPMENT.howto.md
new file mode 100644
index 0000000..ce2afdd
--- /dev/null
+++ b/DEVELOPMENT.howto.md
@@ -0,0 +1,61 @@
+# Developing for Effcee
+
+Thank you for considering Effcee development!  Please make sure you review
+[`CONTRIBUTING.md`](CONTRIBUTING.md) for important preliminary info.
+
+## Building
+
+Instructions for first-time building can be found in [`README.md`](README.md).
+Incremental build after a source change can be done using `ninja` (or
+`cmake --build`) and `ctest` exactly as in the first-time procedure.
+
+## Issue tracking
+
+We use GitHub issues to track bugs, enhancement requests, and questions.
+See [the project's Issues page](https://github.com/google/effcee/issues).
+
+For all but the most trivial changes, we prefer that you file an issue before
+submitting a pull request.  An issue gives us context for your change: what
+problem are you solving, and why.  It also allows us to provide feedback on
+your proposed solution before you invest a lot of effort implementing it.
+
+## Code reviews
+
+All submissions are subject to review via the GitHub pull review process.
+Reviews will cover:
+
+* *Correctness:* Does it work?  Does it work in a multithreaded context?
+* *Testing:* New functionality should be accompanied by tests.
+* *Testability:* Can it easily be tested?  This is proven with accompanying tests.
+* *Design:* Is the solution fragile? Does it fit with the existing code?
+  Would it easily accommodate anticipated changes?
+* *Ease of use:* Can a client get their work done with a minimum of fuss?
+  Are there unnecessarily surprising details?
+* *Consistency:* Does it follow the style guidelines and the rest of the code?
+  Consistency reduces the work of future readers and maintainers.
+* *Portability:* Does it work in many environments?
+
+To respond to feedback, submit one or more *new* commits to the pull request
+branch. The project maintainer will normally clean up the submission by
+squashing feedback response commits.  We maintain a linear commit history,
+so submission will be rebased onto master before merging.
+
+## Testing
+
+There is a lot we won't say about testing. However:
+
+* Most tests should be small scale, i.e. unit tests.
+* Tests should run quickly.
+* A test should:
+  * Check a single behaviour.  This often corresponds to a use case.
+  * Have a three phase structure: setup, action, check.
+
+## Coding style
+
+For C++, we follow the
+[Google C++ style guide](https://google.github.io/styleguide/cppguide.html).
+
+Use `clang-format` to format the code.
+
+For our Python files, we aim to follow the
+[Google Python style guide](https://google.github.io/styleguide/pyguide.html).
diff --git a/LICENSE b/LICENSE
new file mode 100644
index 0000000..261eeb9
--- /dev/null
+++ b/LICENSE
@@ -0,0 +1,201 @@
+                                 Apache License
+                           Version 2.0, January 2004
+                        http://www.apache.org/licenses/
+
+   TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION
+
+   1. Definitions.
+
+      "License" shall mean the terms and conditions for use, reproduction,
+      and distribution as defined by Sections 1 through 9 of this document.
+
+      "Licensor" shall mean the copyright owner or entity authorized by
+      the copyright owner that is granting the License.
+
+      "Legal Entity" shall mean the union of the acting entity and all
+      other entities that control, are controlled by, or are under common
+      control with that entity. For the purposes of this definition,
+      "control" means (i) the power, direct or indirect, to cause the
+      direction or management of such entity, whether by contract or
+      otherwise, or (ii) ownership of fifty percent (50%) or more of the
+      outstanding shares, or (iii) beneficial ownership of such entity.
+
+      "You" (or "Your") shall mean an individual or Legal Entity
+      exercising permissions granted by this License.
+
+      "Source" form shall mean the preferred form for making modifications,
+      including but not limited to software source code, documentation
+      source, and configuration files.
+
+      "Object" form shall mean any form resulting from mechanical
+      transformation or translation of a Source form, including but
+      not limited to compiled object code, generated documentation,
+      and conversions to other media types.
+
+      "Work" shall mean the work of authorship, whether in Source or
+      Object form, made available under the License, as indicated by a
+      copyright notice that is included in or attached to the work
+      (an example is provided in the Appendix below).
+
+      "Derivative Works" shall mean any work, whether in Source or Object
+      form, that is based on (or derived from) the Work and for which the
+      editorial revisions, annotations, elaborations, or other modifications
+      represent, as a whole, an original work of authorship. For the purposes
+      of this License, Derivative Works shall not include works that remain
+      separable from, or merely link (or bind by name) to the interfaces of,
+      the Work and Derivative Works thereof.
+
+      "Contribution" shall mean any work of authorship, including
+      the original version of the Work and any modifications or additions
+      to that Work or Derivative Works thereof, that is intentionally
+      submitted to Licensor for inclusion in the Work by the copyright owner
+      or by an individual or Legal Entity authorized to submit on behalf of
+      the copyright owner. For the purposes of this definition, "submitted"
+      means any form of electronic, verbal, or written communication sent
+      to the Licensor or its representatives, including but not limited to
+      communication on electronic mailing lists, source code control systems,
+      and issue tracking systems that are managed by, or on behalf of, the
+      Licensor for the purpose of discussing and improving the Work, but
+      excluding communication that is conspicuously marked or otherwise
+      designated in writing by the copyright owner as "Not a Contribution."
+
+      "Contributor" shall mean Licensor and any individual or Legal Entity
+      on behalf of whom a Contribution has been received by Licensor and
+      subsequently incorporated within the Work.
+
+   2. Grant of Copyright License. Subject to the terms and conditions of
+      this License, each Contributor hereby grants to You a perpetual,
+      worldwide, non-exclusive, no-charge, royalty-free, irrevocable
+      copyright license to reproduce, prepare Derivative Works of,
+      publicly display, publicly perform, sublicense, and distribute the
+      Work and such Derivative Works in Source or Object form.
+
+   3. Grant of Patent License. Subject to the terms and conditions of
+      this License, each Contributor hereby grants to You a perpetual,
+      worldwide, non-exclusive, no-charge, royalty-free, irrevocable
+      (except as stated in this section) patent license to make, have made,
+      use, offer to sell, sell, import, and otherwise transfer the Work,
+      where such license applies only to those patent claims licensable
+      by such Contributor that are necessarily infringed by their
+      Contribution(s) alone or by combination of their Contribution(s)
+      with the Work to which such Contribution(s) was submitted. If You
+      institute patent litigation against any entity (including a
+      cross-claim or counterclaim in a lawsuit) alleging that the Work
+      or a Contribution incorporated within the Work constitutes direct
+      or contributory patent infringement, then any patent licenses
+      granted to You under this License for that Work shall terminate
+      as of the date such litigation is filed.
+
+   4. Redistribution. You may reproduce and distribute copies of the
+      Work or Derivative Works thereof in any medium, with or without
+      modifications, and in Source or Object form, provided that You
+      meet the following conditions:
+
+      (a) You must give any other recipients of the Work or
+          Derivative Works a copy of this License; and
+
+      (b) You must cause any modified files to carry prominent notices
+          stating that You changed the files; and
+
+      (c) You must retain, in the Source form of any Derivative Works
+          that You distribute, all copyright, patent, trademark, and
+          attribution notices from the Source form of the Work,
+          excluding those notices that do not pertain to any part of
+          the Derivative Works; and
+
+      (d) If the Work includes a "NOTICE" text file as part of its
+          distribution, then any Derivative Works that You distribute must
+          include a readable copy of the attribution notices contained
+          within such NOTICE file, excluding those notices that do not
+          pertain to any part of the Derivative Works, in at least one
+          of the following places: within a NOTICE text file distributed
+          as part of the Derivative Works; within the Source form or
+          documentation, if provided along with the Derivative Works; or,
+          within a display generated by the Derivative Works, if and
+          wherever such third-party notices normally appear. The contents
+          of the NOTICE file are for informational purposes only and
+          do not modify the License. You may add Your own attribution
+          notices within Derivative Works that You distribute, alongside
+          or as an addendum to the NOTICE text from the Work, provided
+          that such additional attribution notices cannot be construed
+          as modifying the License.
+
+      You may add Your own copyright statement to Your modifications and
+      may provide additional or different license terms and conditions
+      for use, reproduction, or distribution of Your modifications, or
+      for any such Derivative Works as a whole, provided Your use,
+      reproduction, and distribution of the Work otherwise complies with
+      the conditions stated in this License.
+
+   5. Submission of Contributions. Unless You explicitly state otherwise,
+      any Contribution intentionally submitted for inclusion in the Work
+      by You to the Licensor shall be under the terms and conditions of
+      this License, without any additional terms or conditions.
+      Notwithstanding the above, nothing herein shall supersede or modify
+      the terms of any separate license agreement you may have executed
+      with Licensor regarding such Contributions.
+
+   6. Trademarks. This License does not grant permission to use the trade
+      names, trademarks, service marks, or product names of the Licensor,
+      except as required for reasonable and customary use in describing the
+      origin of the Work and reproducing the content of the NOTICE file.
+
+   7. Disclaimer of Warranty. Unless required by applicable law or
+      agreed to in writing, Licensor provides the Work (and each
+      Contributor provides its Contributions) on an "AS IS" BASIS,
+      WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
+      implied, including, without limitation, any warranties or conditions
+      of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A
+      PARTICULAR PURPOSE. You are solely responsible for determining the
+      appropriateness of using or redistributing the Work and assume any
+      risks associated with Your exercise of permissions under this License.
+
+   8. Limitation of Liability. In no event and under no legal theory,
+      whether in tort (including negligence), contract, or otherwise,
+      unless required by applicable law (such as deliberate and grossly
+      negligent acts) or agreed to in writing, shall any Contributor be
+      liable to You for damages, including any direct, indirect, special,
+      incidental, or consequential damages of any character arising as a
+      result of this License or out of the use or inability to use the
+      Work (including but not limited to damages for loss of goodwill,
+      work stoppage, computer failure or malfunction, or any and all
+      other commercial damages or losses), even if such Contributor
+      has been advised of the possibility of such damages.
+
+   9. Accepting Warranty or Additional Liability. While redistributing
+      the Work or Derivative Works thereof, You may choose to offer,
+      and charge a fee for, acceptance of support, warranty, indemnity,
+      or other liability obligations and/or rights consistent with this
+      License. However, in accepting such obligations, You may act only
+      on Your own behalf and on Your sole responsibility, not on behalf
+      of any other Contributor, and only if You agree to indemnify,
+      defend, and hold each Contributor harmless for any liability
+      incurred by, or claims asserted against, such Contributor by reason
+      of your accepting any such warranty or additional liability.
+
+   END OF TERMS AND CONDITIONS
+
+   APPENDIX: How to apply the Apache License to your work.
+
+      To apply the Apache License to your work, attach the following
+      boilerplate notice, with the fields enclosed by brackets "[]"
+      replaced with your own identifying information. (Don't include
+      the brackets!)  The text should be enclosed in the appropriate
+      comment syntax for the file format. We also recommend that a
+      file or class name and description of purpose be included on the
+      same "printed page" as the copyright notice for easier
+      identification within third-party archives.
+
+   Copyright [yyyy] [name of copyright owner]
+
+   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/README.md b/README.md
new file mode 100644
index 0000000..b7cd0ac
--- /dev/null
+++ b/README.md
@@ -0,0 +1,284 @@
+# Effcee
+
+[![Linux and OSX Build Status](https://travis-ci.org/google/effcee.svg)](https://travis-ci.org/google/effcee "Linux and OSX Build Status")
+
+Effcee is a C++ library for stateful pattern matching of strings,
+inspired by LLVM's [FileCheck][FileCheck] command.
+
+Effcee:
+- Is a library, so it can be used for quickly running tests in your own process.
+- Is largely compatible with FileCheck, so tests and test-writing skills are
+  transferable.
+- Has few dependencies:
+  - The C++11 standard library, and
+  - [RE2][RE2] for regular expression matching.
+
+## Example
+
+The following is from [examples/main.cc](examples/main.cc):
+
+```C++
+
+    #include <iostream>
+    #include <sstream>
+
+    #include "effcee/effcee.h"
+
+    // Checks standard input against the list of checks provided as command line
+    // arguments.
+    //
+    // Example:
+    //    cat <<EOF >sample_data.txt
+    //    Bees
+    //    Make
+    //    Delicious Honey
+    //    EOF
+    //    effcee-example <sample_data.txt "CHECK: Bees" "CHECK-NOT:Sting" "CHECK: Honey"
+    int main(int argc, char* argv[]) {
+      // Read the command arguments as a list of check rules.
+      std::ostringstream checks_stream;
+      for (int i = 1; i < argc; ++i) {
+        checks_stream << argv[i] << "\n";
+      }
+      // Read stdin as the input to match.
+      std::stringstream input_stream;
+      std::cin >> input_stream.rdbuf();
+
+      // Attempt to match.  The input and checks arguments can be provided as
+      // std::string or pointer to char.
+      auto result = effcee::Match(input_stream.str(), checks_stream.str(),
+                                  effcee::Options().SetChecksName("checks"));
+
+      // Successful match result converts to true.
+      if (result) {
+        std::cout << "The input matched your check list!" << std::endl;
+      } else {
+        // Otherwise, you can get a status code and a detailed message.
+        switch (result.status()) {
+          case effcee::Result::Status::NoRules:
+            std::cout << "error: Expected check rules as command line arguments\n";
+            break;
+          case effcee::Result::Status::Fail:
+            std::cout << "The input failed to match your check rules:\n";
+            break;
+          default:
+            break;
+        }
+        std::cout << result.message() << std::endl;
+        return 1;
+      }
+      return 0;
+    }
+
+```
+
+For more examples, see the matching tests
+in [effcee/match_test.cc](effcee/match_test.cc).
+
+## Status
+
+Effcee is mature enough to be relied upon by
+[third party projects](#what-uses-effcee), but could be improved.
+
+What works:
+* All check types: CHECK, CHECK-NEXT, CHECK-SAME, CHECK-DAG, CHECK-LABEL, CHECK-NOT.
+* Check strings can contain:
+  * fixed strings
+  * regular expressions
+  * variable definitions and uses
+* Setting a custom check prefix.
+* Accurate and helpful reporting of match failures.
+
+What is left to do:
+* Add an option to define shorthands for regular expressions.
+  * For example, you could express that if the string `%%` appears where a
+    regular expression is expected, then it expands to the regular expression
+    for a local identifier in LLVM assembly language, i.e.
+    `%[-a-zA-Z$._][-a-zA-Z$._0-9]*`.
+    This enables you to write precise tests with less fuss.
+* Better error reporting for failure to parse the checks list.
+* Write a check language reference and tutorial.
+
+What is left to do, but lower priority:
+* Match full lines.
+* Strict whitespace.
+* Implicit check-not.
+* Variable scoping.
+
+## Licensing and contributing
+
+Effcee is licensed under terms of the [Apache 2.0 license](LICENSE).  If you
+are interested in contributing to this project, please see
+[`CONTRIBUTING.md`](CONTRIBUTING.md).
+
+This is not an official Google product (experimental or otherwise), it is just
+code that happens to be owned by Google.  That may change if Effcee gains
+contributions from others.  See the [`CONTRIBUTING.md`](CONTRIBUTING.md) file
+for more information. See also the [`AUTHORS`](AUTHORS) and
+[`CONTRIBUTORS`](CONTRIBUTORS) files.
+
+## File organization
+
+- [`effcee`/](effcee) : library source code, and tests
+- `third_party/`: third party open source packages, downloaded
+  separately
+- [`examples/`](examples): example programs
+
+Effcee depends on the [RE2][RE2] regular expression library.
+
+Effcee tests depend on [Googletest][Googletest] and [Python][Python].
+
+In the following sections, `$SOURCE_DIR` is the directory containing the
+Effcee source code.
+
+## Getting and building Effcee
+
+1) Check out the source code:
+
+```sh
+git clone https://github.com/google/effcee $SOURCE_DIR
+cd $SOURCE_DIR/third_party
+git clone https://github.com/google/googletest.git
+git clone https://github.com/google/re2.git
+cd $SOURCE_DIR/
+```
+
+Note: There are two other ways to manage third party sources:
+- If you are building Effcee as part of a larger CMake-based project,
+  add the RE2 and `googletest` projects before adding Effcee.
+- Otherwise, you can set CMake variables to point to third party sources
+  if they are located somewhere else.  See the [Build options](#build-options) below.
+
+2) Ensure you have the requisite tools -- see the tools subsection below.
+
+3) Decide where to place the build output. In the following steps, we'll call it
+   `$BUILD_DIR`. Any new directory should work. We recommend building outside
+   the source tree, but it is also common to build in a (new) subdirectory of
+   `$SOURCE_DIR`, such as `$SOURCE_DIR/build`.
+
+4a) Build and test with Ninja on Linux or Windows:
+
+```sh
+cd $BUILD_DIR
+cmake -GNinja -DCMAKE_BUILD_TYPE={Debug|Release|RelWithDebInfo} $SOURCE_DIR
+ninja
+ctest
+```
+
+4b) Or build and test with MSVC on Windows:
+
+```sh
+cd $BUILD_DIR
+cmake $SOURCE_DIR
+cmake --build . --config {Release|Debug|MinSizeRel|RelWithDebInfo}
+ctest -C {Release|Debug|MinSizeRel|RelWithDebInfo}
+```
+
+4c) Or build with MinGW on Linux for Windows:
+(Skip building threaded unit tests due to
+[Googletest bug 606](https://github.com/google/googletest/issues/606))
+
+```sh
+cd $BUILD_DIR
+cmake -GNinja -DCMAKE_BUILD_TYPE={Debug|Release|RelWithDebInfo} $SOURCE_DIR \
+   -DCMAKE_TOOLCHAIN_FILE=$SOURCE_DIR/cmake/linux-mingw-toolchain.cmake \
+   -Dgtest_disable_pthreads=ON
+ninja
+```
+
+After a successful build, you should have a `libeffcee` library under
+the `$BUILD_DIR/effcee/` directory.
+
+The default behavior on MSVC is to link with the static CRT. If you would like
+to change this behavior `-DEFFCEE_ENABLE_SHARED_CRT` may be passed on the
+cmake configure line.
+
+### Tests
+
+By default, Effcee registers two tests with `ctest`:
+
+* `effcee-test`: All library tests, based on Googletest.
+* `effcee-example`: Executes the example executable with sample inputs.
+
+Running `ctest` without arguments will run the tests for Effcee as well as for
+RE2.
+
+You can disable Effcee's tests by using `-DEFFCEE_BUILD_TESTING=OFF` at
+configuration time:
+
+```sh
+cmake -GNinja -DEFFCEE_BUILD_TESTING=OFF ...
+```
+
+The RE2 tests run much longer, so if you're working on Effcee alone, we
+suggest limiting ctest to tests with prefix `effcee`:
+
+    ctest -R effcee
+
+Alternately, you can turn off RE2 tests entirely by using
+`-DRE2_BUILD_TESTING=OFF` at configuration time:
+
+```sh
+cmake -GNinja -DRE2_BUILD_TESTING=OFF ...
+```
+
+### Tools you'll need
+
+For building, testing, and profiling Effcee, the following tools should be
+installed regardless of your OS:
+
+- A compiler supporting C++11.
+- [CMake][CMake]: for generating compilation targets.
+- [Python][Python]: for a test script.
+
+On Linux, if cross compiling to Windows:
+- [MinGW][MinGW]: A GCC-based cross compiler targeting Windows
+    so that generated executables use the Microsoft C runtime libraries.
+
+On Windows, the following tools should be installed and available on your path:
+
+- Visual Studio 2015 or later. Previous versions of Visual Studio are not usable
+  with RE2 or Googletest.
+- Git - including the associated tools, Bash, `diff`.
+
+### Build options
+
+Third party source locations:
+- `EFFCEE_GOOGLETEST_DIR`: Location of `googletest` sources, if not under
+  `third_party`.
+- `EFFCEE_RE2_DIR`: Location of `re2` sources, if not under `third_party`.
+- `EFFCEE_THIRD_PARTY_ROOT_DIR`: Alternate location for `googletest` and
+  `re2` subdirectories.  This is used if the sources are not located under
+  the `third_party` directory, and if the previous two variables are not set.
+
+Compilation options:
+- `DISABLE_RTTI`. Disable runtime type information. Default is enabled.
+- `DISABLE_EXCEPTIONS`.  Disable exceptions. Default is enabled.
+- `EFFCEE_ENABLE_SHARED_CRT`. See above.
+
+Controlling samples and tests:
+- `EFFCEE_BUILD_SAMPLES`. Should Effcee examples be built?  Defaults to `ON`.
+- `EFFCEE_BUILD_TESTING`. Should Effcee tests be built?  Defaults to `ON`.
+- `RE2_BUILD_TESTING`. Should RE2 tests be built?  Defaults to `ON`.
+
+## Bug tracking
+
+We track bugs using GitHub -- click on the "Issues" button on
+[the project's GitHub page](https://github.com/google/effcee).
+
+## What uses Effcee?
+
+- [Tests](https://github.com/Microsoft/DirectXShaderCompiler/tree/master/tools/clang/test/CodeGenSPIRV)
+  for SPIR-V code generation in the [DXC][DXC] HLSL compiler.
+- Tests for [SPIRV-Tools][SPIRV-Tools]
+
+## References
+
+[CMake]: https://cmake.org/
+[DXC]: https://github.com/Microsoft/DirectXShaderCompiler
+[FileCheck]: http://llvm.org/docs/CommandGuide/FileCheck.html
+[Googletest]: https://github.com/google/googletest
+[MinGW]: http://www.mingw.org/
+[Python]: https://www.python.org/
+[RE2]: https://github.com/google/re2
+[SPIRV-Tools]: https://github.com/KhronosGroup/SPIRV-Tools
diff --git a/cmake/linux-mingw-toolchain.cmake b/cmake/linux-mingw-toolchain.cmake
new file mode 100644
index 0000000..9f7f676
--- /dev/null
+++ b/cmake/linux-mingw-toolchain.cmake
@@ -0,0 +1,35 @@
+# Copyright 2017 The Effcee Authors.
+#
+# 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.
+
+SET(CMAKE_SYSTEM_NAME Windows)
+
+set(MINGW_COMPILER_PREFIX "i686-w64-mingw32" CACHE STRING
+    "What compiler prefix to use for mingw")
+
+set(MINGW_SYSROOT "/usr/${MINGW_COMPILER_PREFIX}" CACHE STRING
+    "What sysroot to use for mingw")
+
+# Which compilers to use for C and C++
+find_program(CMAKE_RC_COMPILER NAMES ${MINGW_COMPILER_PREFIX}-windres)
+find_program(CMAKE_C_COMPILER NAMES ${MINGW_COMPILER_PREFIX}-gcc)
+find_program(CMAKE_CXX_COMPILER NAMES ${MINGW_COMPILER_PREFIX}-g++)
+
+SET(CMAKE_FIND_ROOT_PATH ${MINGW_SYSROOT})
+
+# Adjust the default behaviour of the FIND_XXX() commands:
+# Search headers and libraries in the target environment; search
+# programs in the host environment.
+set(CMAKE_FIND_ROOT_PATH_MODE_PROGRAM NEVER)
+set(CMAKE_FIND_ROOT_PATH_MODE_LIBRARY ONLY)
+set(CMAKE_FIND_ROOT_PATH_MODE_INCLUDE ONLY)
diff --git a/cmake/setup_build.cmake b/cmake/setup_build.cmake
new file mode 100644
index 0000000..40749fc
--- /dev/null
+++ b/cmake/setup_build.cmake
@@ -0,0 +1,83 @@
+# Copyright 2017 The Effcee Authors.
+#
+# 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.
+
+# For cross-compilation, we need to use find_host_package
+# in the remaining setup. But if not cross-compiling, then we
+# need to alias find_host_package to find_package.
+# Similar for find_host_program.
+if(NOT COMMAND find_host_package)
+  macro(find_host_package)
+    find_package(${ARGN})
+  endmacro()
+endif()
+if(NOT COMMAND find_host_program)
+  macro(find_host_program)
+    find_program(${ARGN})
+  endmacro()
+endif()
+
+if (ANDROID)
+  # For android let's preemptively find the correct packages so that
+  # child projects (e.g. googletest) do not fail to find them.
+  find_host_package(PythonInterp)
+endif()
+
+foreach(PROGRAM echo python)
+  string(TOUPPER ${PROGRAM} PROG_UC)
+  if (ANDROID)
+    find_host_program(${PROG_UC}_EXE ${PROGRAM} REQUIRED)
+  else()
+    find_program(${PROG_UC}_EXE ${PROGRAM} REQUIRED)
+  endif()
+endforeach(PROGRAM)
+
+option(DISABLE_RTTI "Disable RTTI in builds")
+if(DISABLE_RTTI)
+  if(UNIX)
+    set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS}  -fno-rtti")
+  endif(UNIX)
+endif(DISABLE_RTTI)
+
+option(DISABLE_EXCEPTIONS "Disables exceptions in builds")
+if(DISABLE_EXCEPTIONS)
+  if(UNIX)
+    set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -fno-exceptions")
+  endif(UNIX)
+endif(DISABLE_EXCEPTIONS)
+
+if(WIN32)
+  # Ensure that gmock compiles the same as the rest of the code, otherwise
+  # failures will occur.
+  set(gtest_force_shared_crt ON CACHE BOOL "" FORCE)
+endif(WIN32)
+
+if(WIN32)
+# On Windows, CMake by default compiles with the shared CRT.
+# Default it to the static CRT.
+  option(EFFCEE_ENABLE_SHARED_CRT
+	 "Use the shared CRT with MSVC instead of the static CRT"
+	 ${EFFCEE_ENABLE_SHARED_CRT})
+  if (NOT EFFCEE_ENABLE_SHARED_CRT)
+    if(MSVC)
+      # Link executables statically by replacing /MD with /MT everywhere.
+      foreach(flag_var
+	  CMAKE_CXX_FLAGS CMAKE_CXX_FLAGS_DEBUG CMAKE_CXX_FLAGS_RELEASE
+	  CMAKE_CXX_FLAGS_MINSIZEREL CMAKE_CXX_FLAGS_RELWITHDEBINFO)
+	if(${flag_var} MATCHES "/MD")
+	  string(REGEX REPLACE "/MD" "/MT" ${flag_var} "${${flag_var}}")
+	endif(${flag_var} MATCHES "/MD")
+      endforeach(flag_var)
+    endif(MSVC)
+  endif(NOT EFFCEE_ENABLE_SHARED_CRT)
+endif(WIN32)
diff --git a/cmake/utils.cmake b/cmake/utils.cmake
new file mode 100644
index 0000000..291be3c
--- /dev/null
+++ b/cmake/utils.cmake
@@ -0,0 +1,61 @@
+# Copyright 2017 The Effcee Authors.
+#
+# 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.
+
+# Utility functions
+
+function(effcee_default_c_compile_options TARGET)
+  if (NOT "${MSVC}")
+    target_compile_options(${TARGET} PRIVATE -Wall -Werror)
+    if (ENABLE_CODE_COVERAGE)
+      # The --coverage option is a synonym for -fprofile-arcs -ftest-coverage
+      # when compiling.
+      target_compile_options(${TARGET} PRIVATE -g -O0 --coverage)
+      # The --coverage option is a synonym for -lgcov when linking for gcc.
+      # For clang, it links in a different library, libclang_rt.profile, which
+      # requires clang to be built with compiler-rt.
+      target_link_libraries(${TARGET} PRIVATE --coverage)
+    endif()
+    if (NOT EFFCEE_ENABLE_SHARED_CRT)
+      if (WIN32)
+        # For MinGW cross compile, statically link to the libgcc runtime.
+        # But it still depends on MSVCRT.dll.
+        set_target_properties(${TARGET} PROPERTIES
+          LINK_FLAGS "-static -static-libgcc")
+      endif(WIN32)
+    endif(NOT EFFCEE_ENABLE_SHARED_CRT)
+    if (UNIX AND NOT MINGW)
+      target_link_libraries(${TARGET} PUBLIC -pthread)
+    endif()
+  else()
+    # disable warning C4800: 'int' : forcing value to bool 'true' or 'false'
+    # (performance warning)
+    target_compile_options(${TARGET} PRIVATE /wd4800)
+  endif()
+endfunction(effcee_default_c_compile_options)
+
+function(effcee_default_compile_options TARGET)
+  effcee_default_c_compile_options(${TARGET})
+  if (NOT "${MSVC}")
+    # RE2's public header requires C++11.  So publicly required C++11
+    target_compile_options(${TARGET} PUBLIC -std=c++11)
+    if (NOT EFFCEE_ENABLE_SHARED_CRT)
+      if (WIN32)
+        # For MinGW cross compile, statically link to the C++ runtime.
+        # But it still depends on MSVCRT.dll.
+        set_target_properties(${TARGET} PROPERTIES
+          LINK_FLAGS "-static -static-libgcc -static-libstdc++")
+      endif(WIN32)
+    endif(NOT EFFCEE_ENABLE_SHARED_CRT)
+  endif()
+endfunction(effcee_default_compile_options)
diff --git a/effcee/CMakeLists.txt b/effcee/CMakeLists.txt
new file mode 100644
index 0000000..149f932
--- /dev/null
+++ b/effcee/CMakeLists.txt
@@ -0,0 +1,34 @@
+add_library(effcee
+            check.cc
+            match.cc)
+effcee_default_compile_options(effcee)
+# We need to expose RE2's StringPiece.
+target_include_directories(effcee
+  PUBLIC ${CMAKE_CURRENT_SOURCE_DIR}/.. ${EFFCEE_RE2_DIR})
+target_link_libraries(effcee PUBLIC re2 ${CMAKE_THREADS_LIB_INIT})
+
+# TODO(dneto): Avoid installing gtest and gtest_main. ?!
+install(
+  FILES
+    effcee.h
+  DESTINATION
+    include/effcee)
+install(TARGETS effcee
+  LIBRARY DESTINATION lib
+  ARCHIVE DESTINATION lib)
+
+if(EFFCEE_BUILD_TESTING)
+  add_executable(effcee-test
+                 check_test.cc
+                 cursor_test.cc
+                 diagnostic_test.cc
+                 match_test.cc
+                 options_test.cc
+                 result_test.cc)
+  effcee_default_compile_options(effcee-test)
+  target_include_directories(effcee-test PRIVATE
+                             ${gmock_SOURCE_DIR}/include
+                             ${gtest_SOURCE_DIR}/include)
+  target_link_libraries(effcee-test PRIVATE effcee gmock gtest_main)
+  add_test(NAME effcee-test COMMAND effcee-test)
+endif(EFFCEE_BUILD_TESTING)
diff --git a/effcee/check.cc b/effcee/check.cc
new file mode 100644
index 0000000..2751801
--- /dev/null
+++ b/effcee/check.cc
@@ -0,0 +1,257 @@
+// Copyright 2017 The Effcee Authors.
+//
+// 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.
+
+#include "check.h"
+
+#include <algorithm>
+#include <cassert>
+#include <memory>
+#include <sstream>
+#include <string>
+#include <utility>
+
+#include "cursor.h"
+#include "effcee.h"
+#include "make_unique.h"
+#include "to_string.h"
+
+using Status = effcee::Result::Status;
+using StringPiece = effcee::StringPiece;
+using Type = effcee::Check::Type;
+
+namespace {
+
+// Returns a table of suffix to type mappings.
+const std::vector<std::pair<StringPiece, Type>>& TypeStringTable() {
+  static std::vector<std::pair<StringPiece, Type>> type_str_table{
+      {"", Type::Simple},  {"-NEXT", Type::Next},   {"-SAME", Type::Same},
+      {"-DAG", Type::DAG}, {"-LABEL", Type::Label}, {"-NOT", Type::Not}};
+  return type_str_table;
+}
+
+// Returns the Check::Type value matching the suffix part of a check rule
+// prefix.  Assumes |suffix| is valid.
+Type TypeForSuffix(StringPiece suffix) {
+  const auto& type_str_table = TypeStringTable();
+  const auto pair_iter =
+      std::find_if(type_str_table.begin(), type_str_table.end(),
+                   [suffix](const std::pair<StringPiece, Type>& elem) {
+                     return suffix == elem.first;
+                   });
+  assert(pair_iter != type_str_table.end());
+  return pair_iter->second;
+}
+}  // namespace
+
+namespace effcee {
+
+int Check::Part::CountCapturingGroups() {
+  if (type_ == Type::Regex) return RE2(param_).NumberOfCapturingGroups();
+  if (type_ == Type::VarDef) return RE2(expression_).NumberOfCapturingGroups();
+  return 0;
+}
+
+Check::Check(Type type, StringPiece param) : type_(type), param_(param) {
+  parts_.push_back(make_unique<Check::Part>(Part::Type::Fixed, param));
+}
+
+bool Check::Part::MightMatch(const VarMapping& vars) const {
+  return type_ != Type::VarUse ||
+         vars.find(ToString(VarUseName())) != vars.end();
+}
+
+std::string Check::Part::Regex(const VarMapping& vars) const {
+  switch (type_) {
+    case Type::Fixed:
+      return RE2::QuoteMeta(param_);
+    case Type::Regex:
+      return ToString(param_);
+    case Type::VarDef:
+      return std::string("(") + ToString(expression_) + ")";
+    case Type::VarUse: {
+      auto where = vars.find(ToString(VarUseName()));
+      if (where != vars.end()) {
+        // Return the escaped form of the current value of the variable.
+        return RE2::QuoteMeta((*where).second);
+      } else {
+        // The variable is not yet set.  Should not get here.
+        return "";
+      }
+    }
+  }
+  return "";  // Unreachable.  But we need to satisfy GCC.
+}
+
+bool Check::Matches(StringPiece* input, StringPiece* captured,
+                    VarMapping* vars) const {
+  if (parts_.empty()) return false;
+  for (auto& part : parts_) {
+    if (!part->MightMatch(*vars)) return false;
+  }
+
+  std::unordered_map<int, std::string> var_def_indices;
+
+  std::ostringstream consume_regex;
+  int num_captures = 1;  // The outer capture.
+  for (auto& part : parts_) {
+    consume_regex << part->Regex(*vars);
+    const auto var_def_name = part->VarDefName();
+    if (!var_def_name.empty()) {
+      var_def_indices[num_captures++] = ToString(var_def_name);
+    }
+    num_captures += part->NumCapturingGroups();
+  }
+  std::unique_ptr<StringPiece[]> captures(new StringPiece[num_captures]);
+  const bool matched = RE2(consume_regex.str())
+                           .Match(*input, 0, input->size(), RE2::UNANCHORED,
+                                  captures.get(), num_captures);
+  if (matched) {
+    *captured = captures[0];
+    input->remove_prefix(captured->end() - input->begin());
+    // Update the variable mapping.
+    for (auto& var_def_index : var_def_indices) {
+      const int index = var_def_index.first;
+      (*vars)[var_def_index.second] = ToString(captures[index]);
+    }
+  }
+
+  return matched;
+}
+
+namespace {
+// Returns a parts list for the given pattern.  This splits out regular
+// expressions as delimited by {{ and }}, and also variable uses and
+// definitions.
+Check::Parts PartsForPattern(StringPiece pattern) {
+  Check::Parts parts;
+  StringPiece fixed, regex, var;
+
+  using Type = Check::Part::Type;
+
+  while (!pattern.empty()) {
+    const auto regex_start = pattern.find("{{");
+    const auto regex_end = pattern.find("}}");
+    const auto var_start = pattern.find("[[");
+    const auto var_end = pattern.find("]]");
+    const bool regex_exists =
+        regex_start < regex_end && regex_end < StringPiece::npos;
+    const bool var_exists = var_start < var_end && var_end < StringPiece::npos;
+
+    if (regex_exists && (!var_exists || regex_start < var_start)) {
+      const auto consumed =
+          RE2::Consume(&pattern, "(.*?){{(.*?)}}", &fixed, &regex);
+      if (!consumed) {
+        assert(consumed &&
+               "Did not make forward progress for regex in check rule");
+      }
+      if (!fixed.empty()) {
+        parts.emplace_back(make_unique<Check::Part>(Type::Fixed, fixed));
+      }
+      if (!regex.empty()) {
+        parts.emplace_back(make_unique<Check::Part>(Type::Regex, regex));
+      }
+    } else if (var_exists && (!regex_exists || var_start < regex_start)) {
+      const auto consumed =
+          RE2::Consume(&pattern, "(.*?)\\[\\[(.*?)\\]\\]", &fixed, &var);
+      if (!consumed) {
+        assert(consumed &&
+               "Did not make forward progress for var in check rule");
+      }
+      if (!fixed.empty()) {
+        parts.emplace_back(make_unique<Check::Part>(Type::Fixed, fixed));
+      }
+      if (!var.empty()) {
+        auto colon = var.find(":");
+        // A colon at the end is useless anyway, so just make it a variable
+        // use.
+        if (colon == StringPiece::npos || colon == var.size() - 1) {
+          parts.emplace_back(make_unique<Check::Part>(Type::VarUse, var));
+        } else {
+          StringPiece name = var.substr(0, colon);
+          StringPiece expression = var.substr(colon + 1, StringPiece::npos);
+          parts.emplace_back(
+              make_unique<Check::Part>(Type::VarDef, var, name, expression));
+        }
+      }
+    } else {
+      // There is no regex, no var def, no var use.  Must be a fixed string.
+      parts.push_back(make_unique<Check::Part>(Type::Fixed, pattern));
+      break;
+    }
+  }
+
+  return parts;
+}
+
+}  // namespace
+
+std::pair<Result, CheckList> ParseChecks(StringPiece str,
+                                         const Options& options) {
+  // Returns a pair whose first member is a result constructed from the
+  // given status and message, and the second member is an empy pattern.
+  auto failure = [](Status status, StringPiece message) {
+    return std::make_pair(Result(status, message), CheckList{});
+  };
+
+  if (options.prefix().size() == 0)
+    return failure(Status::BadOption, "Rule prefix is empty");
+  if (RE2::FullMatch(options.prefix(), "\\s+"))
+    return failure(Status::BadOption,
+                   "Rule prefix is whitespace.  That's silly.");
+
+  CheckList check_list;
+
+  const auto quoted_prefix = RE2::QuoteMeta(options.prefix());
+  // Match the following parts:
+  //    .*?               - Text that is not the rule prefix
+  //    quoted_prefix     - A Simple Check prefix
+  //    (-NEXT|-SAME)?    - An optional check type suffix. Two shown here.
+  //    :                 - Colon
+  //    \s*               - Whitespace
+  //    (.*?)             - Captured parameter
+  //    \s*               - Whitespace
+  //    $                 - End of line
+
+  const RE2 regexp(std::string(".*?") + quoted_prefix +
+                   "(-NEXT|-SAME|-DAG|-LABEL|-NOT)?"
+                   ":\\s*(.*?)\\s*$");
+  Cursor cursor(str);
+  while (!cursor.Exhausted()) {
+    const auto line = cursor.RestOfLine();
+
+    StringPiece matched_param;
+    StringPiece suffix;
+    if (RE2::PartialMatch(line, regexp, &suffix, &matched_param)) {
+      const Type type = TypeForSuffix(suffix);
+      auto parts(PartsForPattern(matched_param));
+      check_list.push_back(Check(type, matched_param, std::move(parts)));
+    }
+    cursor.AdvanceLine();
+  }
+
+  if (check_list.empty()) {
+    return failure(
+        Status::NoRules,
+        std::string("No check rules specified. Looking for prefix ") +
+            options.prefix());
+  }
+
+  if (check_list[0].type() == Type::Same) {
+    return failure(Status::BadRule, std::string(options.prefix()) +
+                                        "-SAME can't be the first check rule");
+  }
+
+  return std::make_pair(Result(Result::Status::Ok), check_list);
+}
+}  // namespace effcee
diff --git a/effcee/check.h b/effcee/check.h
new file mode 100644
index 0000000..35a5c0b
--- /dev/null
+++ b/effcee/check.h
@@ -0,0 +1,203 @@
+// Copyright 2017 The Effcee Authors.
+//
+// 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.
+
+#ifndef EFFCEE_CHECK_H
+#define EFFCEE_CHECK_H
+
+#include <memory>
+#include <string>
+#include <unordered_map>
+#include <utility>
+#include <vector>
+
+#include "effcee.h"
+#include "make_unique.h"
+
+namespace effcee {
+
+// A mapping from a name to a string value.
+using VarMapping = std::unordered_map<std::string, std::string>;
+
+// A single check indicating something to be matched.
+//
+// A _positive_ check is _resolved_ when its parameter is matches a part of the
+// in the input text.  A _negative_ check is _resolved_ when its parameter does
+// _not_ match a section of the input between context-dependent start and end
+// points.
+class Check {
+ public:
+  // The type Determines when the check is satisfied.  The Not type denotes
+  // a negative check.  The other types denote positive checks.
+  enum class Type {
+    Simple,  // Matches a string.
+    Next,    // Matches a string, on the line following previous match.
+    Same,    // Matches a string, on the same line as the previous metch.
+    DAG,     // Matches a string, unordered with respect to other
+    Label,   // Like Simple, but resets local variables.
+    Not,     // Given string is not found before next positive match.
+  };
+
+  // A Part is a contiguous segment of the check pattern.  A part is
+  // distinguished by how it matches against input.
+  class Part {
+   public:
+    enum class Type {
+      Fixed,   // A fixed string: characters are matched exactly, in sequence.
+      Regex,   // A regular expression
+      VarDef,  // A variable definition
+      VarUse,  // A variable use
+    };
+
+    Part(Type type, StringPiece param)
+        : type_(type),
+          param_(param),
+          name_(),
+          expression_(),
+          num_capturing_groups_(CountCapturingGroups()) {}
+
+    // A constructor for a VarDef variant.
+    Part(Type type, StringPiece param, StringPiece name, StringPiece expr)
+        : type_(type),
+          param_(param),
+          name_(name),
+          expression_(expr),
+          num_capturing_groups_(CountCapturingGroups()) {}
+
+    // Returns true if this part might match a target string.  The only case where
+    // this is false is for a VarUse part where the variable is not yet defined.
+    bool MightMatch(const VarMapping& vars) const;
+
+    // Returns a regular expression to match this part, given a mapping of
+    // variable names to values.  If this part is a fixed string or variable use
+    // then quoting has been applied.
+    std::string Regex(const VarMapping& vars) const;
+
+    // Returns number of capturing subgroups in the regex for a Regex or VarDef
+    // part, and 0 for other parts.
+    int NumCapturingGroups() const { return num_capturing_groups_; }
+
+    // If this is a VarDef, then returns the name of the variable. Otherwise
+    // returns an empty string.
+    StringPiece VarDefName() const { return name_; }
+
+    // If this is a VarUse, then returns the name of the variable. Otherwise
+    // returns an empty string.
+    StringPiece VarUseName() const {
+      return type_ == Type::VarUse ? param_ : "";
+    }
+
+   private:
+    // Computes the number of capturing groups in this part. This is zero
+    // for Fixed and VarUse parts.
+    int CountCapturingGroups();
+
+    // The part type.
+    Type type_;
+    // The part parameter.  For a Regex, VarDef, and VarUse, this does not
+    // have the delimiters.
+    StringPiece param_;
+
+    // For a VarDef, the name of the variable.
+    StringPiece name_;
+    // For a VarDef, the regex matching the new value for the variable.
+    StringPiece expression_;
+    // The number of capturing subgroups in the regex for a Regex or VarDef
+    // part, and 0 for other kinds of parts.
+    int num_capturing_groups_;
+  };
+
+  using Parts = std::vector<std::unique_ptr<Part>>;
+
+  // MSVC needs a default constructor.  However, a default-constructed Check
+  // instance can't be used for matching.
+  Check() : type_(Type::Simple) {}
+
+  // Construct a Check object of the given type and fixed parameter string.
+  // In particular, this retains a StringPiece reference to the |param|
+  // contents, so that string storage should remain valid for the duration
+  // of this object.
+  Check(Type type, StringPiece param);
+
+  // Construct a Check object of the given type, with given parameter string
+  // and specified parts.
+  Check(Type type, StringPiece param, Parts&& parts)
+      : type_(type), param_(param), parts_(std::move(parts)) {}
+
+  // Move constructor.
+  Check(Check&& other) : type_(other.type_), param_(other.param_) {
+    parts_.swap(other.parts_);
+  }
+  // Copy constructor.
+  Check(const Check& other) : type_(other.type_), param_(other.param_) {
+    for (const auto& part : other.parts_) {
+      parts_.push_back(make_unique<Part>(*part));
+    }
+  }
+  // Copy and move assignment.
+  Check& operator=(Check other) {
+    type_ = other.type_;
+    param_ = other.param_;
+    std::swap(parts_, other.parts_);
+    return *this;
+  }
+
+  // Accessors.
+  Type type() const { return type_; }
+  StringPiece param() const { return param_; }
+  const Parts& parts() const { return parts_; }
+
+  // Tries to match the given string, using |vars| as the variable mapping
+  // context.  A variable use, e.g. '[[X]]', matches the current value for
+  // that variable in vars, 'X' in this case.  A variable definition,
+  // e.g. '[[XYZ:[0-9]+]]', will match against the regex provdided after the
+  // colon.  If successful, returns true, advances |str| past the matched
+  // portion, saves the captured substring in |captured|, and sets the value
+  // of named variables in |vars| with the strings they matched. Otherwise
+  // returns false and does not update |str| or |captured|.  Assumes this
+  // instance is not default-constructed.
+  bool Matches(StringPiece* str, StringPiece* captured, VarMapping* vars) const;
+
+ private:
+  // The type of check.
+  Type type_;
+
+  // The parameter as given in user input, if any.
+  StringPiece param_;
+
+  // The parameter, broken down into parts.
+  Parts parts_;
+};
+
+// Equality operator for Check.
+inline bool operator==(const Check& lhs, const Check& rhs) {
+  return lhs.type() == rhs.type() && lhs.param() == rhs.param();
+}
+
+// Inequality operator for Check.
+inline bool operator!=(const Check& lhs, const Check& rhs) {
+  return !(lhs == rhs);
+}
+
+using CheckList = std::vector<Check>;
+
+// Parses |checks_string|, returning a Result status object and the sequence
+// of recognized checks, taking |options| into account.  The result status
+// object indicates success, or failure with a message.
+// TODO(dneto): Only matches simple checks for now.
+std::pair<Result, CheckList> ParseChecks(StringPiece checks_string,
+                                         const Options& options);
+
+}  // namespace effcee
+
+#endif
diff --git a/effcee/check_test.cc b/effcee/check_test.cc
new file mode 100644
index 0000000..c9d0674
--- /dev/null
+++ b/effcee/check_test.cc
@@ -0,0 +1,342 @@
+// Copyright 2017 The Effcee Authors.
+//
+// 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.
+
+#include <vector>
+#include "gmock/gmock.h"
+
+#include "check.h"
+
+namespace {
+
+using effcee::Check;
+using effcee::Options;
+using effcee::CheckList;
+using effcee::ParseChecks;
+using effcee::Result;
+using effcee::StringPiece;
+using ::testing::Combine;
+using ::testing::Eq;
+using ::testing::HasSubstr;
+using ::testing::ValuesIn;
+
+using Part = effcee::Check::Part;
+using Status = effcee::Result::Status;
+using Type = Check::Type;
+using VarMapping = effcee::VarMapping;
+
+// Check class
+
+// Returns a vector of all Check types.
+std::vector<Type> AllTypes() {
+  return {Type::Simple, Type::Next,  Type::Same,
+          Type::DAG,    Type::Label, Type::Not};
+}
+
+using CheckTypeTest = ::testing::TestWithParam<Type>;
+
+TEST_P(CheckTypeTest, ConstructWithAnyType) {
+  Check check(GetParam(), "");
+  EXPECT_THAT(check.type(), Eq(GetParam()));
+}
+
+INSTANTIATE_TEST_SUITE_P(AllTypes, CheckTypeTest, ValuesIn(AllTypes()));
+
+using CheckParamTest = ::testing::TestWithParam<StringPiece>;
+
+TEST_P(CheckParamTest, ConstructWithSampleParamValue) {
+  Check check(Type::Simple, GetParam());
+  // The contents are the same.
+  EXPECT_THAT(check.param(), Eq(GetParam()));
+  // The referenced storage is the same.
+  EXPECT_THAT(check.param().data(), Eq(GetParam().data()));
+}
+
+INSTANTIATE_TEST_SUITE_P(SampleParams, CheckParamTest,
+                         ValuesIn(std::vector<StringPiece>{
+                             "", "a b c", "The wind {{in}} the willows\n",
+                             "Bring me back to the mountains of yore."}));
+
+// Equality operator
+TEST(CheckEqualityTest, TrueWhenAllComponentsSame) {
+  EXPECT_TRUE(Check(Type::Simple, "abc") == Check(Type::Simple, "abc"));
+}
+
+TEST(CheckEqualityTest, FalseWhenTypeDifferent) {
+  EXPECT_FALSE(Check(Type::Simple, "abc") == Check(Type::Next, "abc"));
+}
+
+TEST(CheckEqualityTest, FalseWhenParamDifferent) {
+  EXPECT_FALSE(Check(Type::Simple, "abc") == Check(Type::Simple, "def"));
+}
+
+// Inequality operator
+TEST(CheckInequalityTest, FalseWhenAllComponentsSame) {
+  EXPECT_FALSE(Check(Type::Simple, "abc") != Check(Type::Simple, "abc"));
+}
+
+TEST(CheckInequalityTest, TrueWhenTypeDifferent) {
+  EXPECT_TRUE(Check(Type::Simple, "abc") != Check(Type::Next, "abc"));
+}
+
+TEST(CheckInequalityTest, TrueWhenParamDifferent) {
+  EXPECT_TRUE(Check(Type::Simple, "abc") != Check(Type::Simple, "def"));
+}
+
+// ParseChecks free function
+
+TEST(ParseChecks, FreeFunctionLinks) {
+  std::pair<Result, CheckList> parsed(ParseChecks("", Options()));
+}
+
+TEST(ParseChecks, FailWhenRulePrefixIsEmpty) {
+  const auto parsed(ParseChecks("CHECK: now", Options().SetPrefix("")));
+  const Result& result = parsed.first;
+  const CheckList& pattern = parsed.second;
+  EXPECT_THAT(result.status(), Eq(Status::BadOption));
+  EXPECT_THAT(result.message(), Eq("Rule prefix is empty"));
+  EXPECT_THAT(pattern.size(), Eq(0));
+}
+
+TEST(ParseChecks, FailWhenRulePrefixIsWhitespace) {
+  const auto parsed(ParseChecks("CHECK: now", Options().SetPrefix("\t\n ")));
+  const Result& result = parsed.first;
+  const CheckList& pattern = parsed.second;
+  EXPECT_THAT(result.status(), Eq(Status::BadOption));
+  EXPECT_THAT(result.message(),
+              Eq("Rule prefix is whitespace.  That's silly."));
+  EXPECT_THAT(pattern.size(), Eq(0));
+}
+
+TEST(ParseChecks, FailWhenChecksAbsent) {
+  const auto parsed(ParseChecks("no checks", Options()));
+  const Result& result = parsed.first;
+  const CheckList& pattern = parsed.second;
+  EXPECT_THAT(result.status(), Eq(Status::NoRules));
+  EXPECT_THAT(result.message(),
+              Eq("No check rules specified. Looking for prefix CHECK"));
+  EXPECT_THAT(pattern.size(), Eq(0));
+}
+
+TEST(ParseChecks, FailWhenChecksAbsentWithCustomPrefix) {
+  const auto parsed(ParseChecks("CHECK: now", Options().SetPrefix("FOO")));
+  const Result& result = parsed.first;
+  const CheckList& pattern = parsed.second;
+  EXPECT_THAT(result.status(), Eq(Status::NoRules));
+  EXPECT_THAT(result.message(),
+              Eq("No check rules specified. Looking for prefix FOO"));
+  EXPECT_THAT(pattern.size(), Eq(0));
+}
+
+TEST(ParseChecks, FindSimpleCheck) {
+  const auto parsed = ParseChecks("CHECK: now", Options());
+  EXPECT_THAT(parsed.first.status(), Eq(Status::Ok));
+  EXPECT_THAT(parsed.second, Eq(CheckList({Check(Type::Simple, "now")})));
+}
+
+TEST(ParseChecks, FindSimpleCheckWithCustomPrefix) {
+  const auto parsed = ParseChecks("FOO: how", Options().SetPrefix("FOO"));
+  EXPECT_THAT(parsed.first.status(), Eq(Status::Ok));
+  EXPECT_THAT(parsed.second, Eq(CheckList({Check(Type::Simple, "how")})));
+}
+
+TEST(ParseChecks, FindSimpleCheckWithCustomPrefixHavingRegexpMetachars) {
+  const auto parsed = ParseChecks("[::alpha::]^\\d: how",
+                                  Options().SetPrefix("[::alpha::]^\\d"));
+  EXPECT_THAT(parsed.first.status(), Eq(Status::Ok));
+  EXPECT_THAT(parsed.second, Eq(CheckList({Check(Type::Simple, "how")})));
+}
+
+TEST(ParseChecks, FindSimpleCheckPartwayThroughLine) {
+  const auto parsed = ParseChecks("some other garbageCHECK: now", Options());
+  EXPECT_THAT(parsed.first.status(), Eq(Status::Ok));
+  EXPECT_THAT(parsed.second, Eq(CheckList({Check(Type::Simple, "now")})));
+}
+
+TEST(ParseChecks, FindSimpleCheckCheckListWithoutSurroundingWhitespace) {
+  const auto parsed = ParseChecks("CHECK:now", Options());
+  EXPECT_THAT(parsed.first.status(), Eq(Status::Ok));
+  EXPECT_THAT(parsed.second, Eq(CheckList({Check(Type::Simple, "now")})));
+}
+
+TEST(ParseChecks, FindSimpleCheckCheckListWhileStrippingSurroundingWhitespace) {
+  const auto parsed = ParseChecks("CHECK: \t   now\t\t  ", Options());
+  EXPECT_THAT(parsed.first.status(), Eq(Status::Ok));
+  EXPECT_THAT(parsed.second, Eq(CheckList({Check(Type::Simple, "now")})));
+}
+
+TEST(ParseChecks, FindSimpleCheckCountsLinesCorrectly) {
+  const auto parsed = ParseChecks("\n\nCHECK: now", Options());
+  EXPECT_THAT(parsed.first.status(), Eq(Status::Ok));
+  EXPECT_THAT(parsed.second, Eq(CheckList({Check(Type::Simple, "now")})));
+}
+
+TEST(ParseChecks, FindSimpleChecksOnSeparateLines) {
+  const auto parsed =
+      ParseChecks("CHECK: now\n\n\nCHECK: and \n CHECK: then", Options());
+  EXPECT_THAT(parsed.first.status(), Eq(Status::Ok));
+  EXPECT_THAT(parsed.second, Eq(CheckList({Check(Type::Simple, "now"),
+                                           Check(Type::Simple, "and"),
+                                           Check(Type::Simple, "then")})));
+}
+
+TEST(ParseChecks, FindSimpleChecksOnlyOncePerLine) {
+  const auto parsed = ParseChecks("CHECK: now CHECK: then", Options());
+  EXPECT_THAT(parsed.first.status(), Eq(Status::Ok));
+  EXPECT_THAT(parsed.second,
+              Eq(CheckList({Check(Type::Simple, "now CHECK: then")})));
+}
+
+// Test parsing of the different check rule types.
+
+using ParseChecksTypeTest = ::testing::TestWithParam<
+    std::tuple<std::string, std::pair<std::string, Type>>>;
+
+TEST_P(ParseChecksTypeTest, Successful) {
+  const auto& prefix = std::get<0>(GetParam());
+  const auto& type_str = std::get<0>(std::get<1>(GetParam()));
+  const Type& type = std::get<1>(std::get<1>(GetParam()));
+  // A CHECK-SAME rule can't appear first, so insert a CHECK: rule first.
+  const std::string input = prefix + ": here\n" + prefix + type_str + ": now";
+  const auto parsed = ParseChecks(input, Options().SetPrefix(prefix));
+  EXPECT_THAT(parsed.first.status(), Eq(Status::Ok));
+  EXPECT_THAT(parsed.second,
+              Eq(CheckList({Check(Type::Simple, "here"), Check(type, "now")})));
+}
+
+// Returns a vector of pairs. Each pair has first member being a check type
+// suffix, and the second member is the corresponding check type.
+std::vector<std::pair<std::string, Type>> AllCheckTypesAsPairs() {
+  return {
+      {"", Type::Simple},  {"-NEXT", Type::Next},   {"-SAME", Type::Same},
+      {"-DAG", Type::DAG}, {"-LABEL", Type::Label}, {"-NOT", Type::Not},
+  };
+}
+
+INSTANTIATE_TEST_SUITE_P(AllCheckTypes, ParseChecksTypeTest,
+                         Combine(ValuesIn(std::vector<std::string>{"CHECK",
+                                                                   "FOO"}),
+                                 ValuesIn(AllCheckTypesAsPairs())));
+
+using ParseChecksTypeFailTest = ::testing::TestWithParam<
+    std::tuple<std::string, std::pair<std::string, Type>>>;
+
+// This is just one way to fail.
+TEST_P(ParseChecksTypeFailTest, FailureWhenNoColon) {
+  const auto& prefix = std::get<0>(GetParam());
+  const auto& type_str = std::get<0>(std::get<1>(GetParam()));
+  const std::string input = prefix + type_str + "BAD now";
+  const auto parsed = ParseChecks(input, Options().SetPrefix(prefix));
+  EXPECT_THAT(parsed.first.status(), Eq(Status::NoRules));
+  EXPECT_THAT(parsed.second, Eq(CheckList{}));
+}
+
+INSTANTIATE_TEST_SUITE_P(AllCheckTypes, ParseChecksTypeFailTest,
+                         Combine(ValuesIn(std::vector<std::string>{"CHECK",
+                                                                   "FOO"}),
+                                 ValuesIn(AllCheckTypesAsPairs())));
+
+TEST(ParseChecks, CheckSameCantBeFirst) {
+  const auto parsed = ParseChecks("CHECK-SAME: now", Options());
+  EXPECT_THAT(parsed.first.status(), Eq(Status::BadRule));
+  EXPECT_THAT(parsed.first.message(),
+              HasSubstr("CHECK-SAME can't be the first check rule"));
+  EXPECT_THAT(parsed.second, Eq(CheckList({})));
+}
+
+TEST(ParseChecks, CheckSameCantBeFirstDifferentPrefix) {
+  const auto parsed = ParseChecks("BOO-SAME: now", Options().SetPrefix("BOO"));
+  EXPECT_THAT(parsed.first.status(), Eq(Status::BadRule));
+  EXPECT_THAT(parsed.first.message(),
+              HasSubstr("BOO-SAME can't be the first check rule"));
+  EXPECT_THAT(parsed.second, Eq(CheckList({})));
+}
+
+// Check::Matches
+struct CheckMatchCase {
+  std::string input;
+  Check check;
+  bool expected;
+  std::string remaining;
+  std::string captured;
+};
+
+using CheckMatchTest = ::testing::TestWithParam<CheckMatchCase>;
+
+TEST_P(CheckMatchTest, Samples) {
+  StringPiece str = GetParam().input;
+  StringPiece captured;
+  VarMapping vars;
+  const bool matched = GetParam().check.Matches(&str, &captured, &vars);
+  EXPECT_THAT(matched, Eq(GetParam().expected))
+      << "Failed on input " << GetParam().input;
+  EXPECT_THAT(std::string(str.data(), str.size()), Eq(GetParam().remaining));
+  EXPECT_THAT(std::string(captured.data(), captured.size()),
+              Eq(GetParam().captured));
+  EXPECT_TRUE(vars.empty());
+}
+
+INSTANTIATE_TEST_SUITE_P(
+    Simple, CheckMatchTest,
+    ValuesIn(std::vector<CheckMatchCase>{
+        {"hello", Check(Type::Simple, "hello"), true, "", "hello"},
+        {"world", Check(Type::Simple, "hello"), false, "world", ""},
+        {"in hello now", Check(Type::Simple, "hello"), true, " now", "hello"},
+        {"hello", Check(Type::Same, "hello"), true, "", "hello"},
+        {"world", Check(Type::Same, "hello"), false, "world", ""},
+        {"in hello now", Check(Type::Same, "hello"), true, " now", "hello"},
+        {"hello", Check(Type::Next, "hello"), true, "", "hello"},
+        {"world", Check(Type::Next, "hello"), false, "world", ""},
+        {"in hello now", Check(Type::Next, "hello"), true, " now", "hello"},
+        {"hello", Check(Type::DAG, "hello"), true, "", "hello"},
+        {"world", Check(Type::DAG, "hello"), false, "world", ""},
+        {"in hello now", Check(Type::DAG, "hello"), true, " now", "hello"},
+        {"hello", Check(Type::Label, "hello"), true, "", "hello"},
+        {"world", Check(Type::Label, "hello"), false, "world", ""},
+        {"in hello now", Check(Type::Label, "hello"), true, " now", "hello"},
+        {"hello", Check(Type::Label, "hello"), true, "", "hello"},
+        {"world", Check(Type::Label, "hello"), false, "world", ""},
+        {"in hello now", Check(Type::Label, "hello"), true, " now", "hello"},
+        {"hello", Check(Type::Not, "hello"), true, "", "hello"},
+        {"world", Check(Type::Not, "hello"), false, "world", ""},
+        {"in hello now", Check(Type::Not, "hello"), true, " now", "hello"},
+    }));
+
+// Check::Part::Regex
+
+TEST(CheckPart, FixedPartRegex) {
+  VarMapping vm;
+  EXPECT_THAT(Part(Part::Type::Fixed, "abc").Regex(vm), Eq("abc"));
+  EXPECT_THAT(Part(Part::Type::Fixed, "a.bc").Regex(vm), Eq("a\\.bc"));
+  EXPECT_THAT(Part(Part::Type::Fixed, "a?bc").Regex(vm), Eq("a\\?bc"));
+  EXPECT_THAT(Part(Part::Type::Fixed, "a+bc").Regex(vm), Eq("a\\+bc"));
+  EXPECT_THAT(Part(Part::Type::Fixed, "a*bc").Regex(vm), Eq("a\\*bc"));
+  EXPECT_THAT(Part(Part::Type::Fixed, "a[b]").Regex(vm), Eq("a\\[b\\]"));
+  EXPECT_THAT(Part(Part::Type::Fixed, "a[-]").Regex(vm), Eq("a\\[\\-\\]"));
+  EXPECT_THAT(Part(Part::Type::Fixed, "a(-)b").Regex(vm), Eq("a\\(\\-\\)b"));
+}
+
+TEST(CheckPart, RegexPartRegex) {
+  VarMapping vm;
+  EXPECT_THAT(Part(Part::Type::Regex, "abc").Regex(vm), Eq("abc"));
+  EXPECT_THAT(Part(Part::Type::Regex, "a.bc").Regex(vm), Eq("a.bc"));
+  EXPECT_THAT(Part(Part::Type::Regex, "a?bc").Regex(vm), Eq("a?bc"));
+  EXPECT_THAT(Part(Part::Type::Regex, "a+bc").Regex(vm), Eq("a+bc"));
+  EXPECT_THAT(Part(Part::Type::Regex, "a*bc").Regex(vm), Eq("a*bc"));
+  EXPECT_THAT(Part(Part::Type::Regex, "a[b]").Regex(vm), Eq("a[b]"));
+  EXPECT_THAT(Part(Part::Type::Regex, "a[-]").Regex(vm), Eq("a[-]"));
+  EXPECT_THAT(Part(Part::Type::Regex, "a(-)b").Regex(vm), Eq("a(-)b"));
+}
+
+}  // namespace
+
diff --git a/effcee/cursor.h b/effcee/cursor.h
new file mode 100644
index 0000000..82133f9
--- /dev/null
+++ b/effcee/cursor.h
@@ -0,0 +1,97 @@
+// Copyright 2017 The Effcee Authors.
+//
+// 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.
+
+#ifndef EFFCEE_CURSOR_H
+#define EFFCEE_CURSOR_H
+
+#include <sstream>
+#include <string>
+
+#include "re2/stringpiece.h"
+
+namespace effcee {
+
+using StringPiece = re2::StringPiece;
+
+// Represents a position in a StringPiece, while tracking line number.
+class Cursor {
+
+ public:
+  explicit Cursor(StringPiece str)
+      : remaining_(str), line_num_(1) {}
+
+  StringPiece remaining() const { return remaining_; }
+  // Returns the current 1-based line number.
+  int line_num() const { return line_num_; }
+
+  // Returns true if the remaining text is empty.
+  bool Exhausted() const { return remaining_.empty(); }
+
+  // Returns a string piece from the current position until the end of the line
+  // or the end of input, up to and including the newline.
+  StringPiece RestOfLine() const {
+    const auto newline_pos = remaining_.find('\n');
+    return remaining_.substr(0, newline_pos + (newline_pos != StringPiece::npos));
+  }
+
+  // Advance |n| characters.  Does not adjust line count.  The next |n|
+  // characters should not contain newlines if line numbering is to remain
+  // up to date.  Returns this object.
+  Cursor& Advance(size_t n) { remaining_.remove_prefix(n); return *this; }
+
+  // Advances the cursor by a line.  If no text remains, then does nothing.
+  // Otherwise removes the first line (including newline) and increments the
+  // line count.  If there is no newline then the remaining string becomes
+  // empty.  Returns this object.
+  Cursor& AdvanceLine() {
+    if (remaining_.size()) {
+      Advance(RestOfLine().size());
+      ++line_num_;
+    }
+    return *this;
+  };
+
+ private:
+  // The remaining text, after all previous advancements.  References the
+  // original string storage.
+  StringPiece remaining_;
+  // The current 1-based line number.
+  int line_num_;
+};
+
+// Returns string containing a description of the line containing a given
+// subtext, with a message, and a caret displaying the subtext position.
+// Assumes subtext does not contain a newline.
+inline std::string LineMessage(StringPiece text, StringPiece subtext,
+                               StringPiece message) {
+  Cursor c(text);
+  StringPiece full_line = c.RestOfLine();
+  while (subtext.end() - full_line.end() > 0) {
+    c.AdvanceLine();
+    full_line = c.RestOfLine();
+  }
+  const char* full_line_newline =
+      full_line.find('\n') == StringPiece::npos ? "\n" : "";
+  const size_t column = subtext.begin() - full_line.begin();
+
+  std::ostringstream out;
+  out << ":" << c.line_num() << ":" << (1 + column) << ": " << message << "\n"
+      << full_line << full_line_newline << std::string(column, ' ') << "^\n";
+
+  return out.str();
+}
+
+}  // namespace effcee
+
+#endif
diff --git a/effcee/cursor_test.cc b/effcee/cursor_test.cc
new file mode 100644
index 0000000..ea2016d
--- /dev/null
+++ b/effcee/cursor_test.cc
@@ -0,0 +1,179 @@
+// Copyright 2017 The Effcee Authors.
+//
+// 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.
+
+#include "gmock/gmock.h"
+
+#include "cursor.h"
+
+namespace {
+
+using effcee::Cursor;
+using effcee::LineMessage;
+using effcee::StringPiece;
+using ::testing::Eq;
+using ::testing::HasSubstr;
+
+// text method
+
+// remaining and Advance methods
+TEST(Cursor, AdvanceReturnsTheCursorItself) {
+  Cursor c("foo");
+  EXPECT_THAT(&c.Advance(1), Eq(&c));
+}
+
+TEST(Cursor, RemainingBeginsEqualToText) {
+  const char* original = "The Smiths";
+  Cursor c(original);
+  EXPECT_THAT(c.remaining().begin(), Eq(original));
+}
+
+TEST(Cursor, RemainingDiminishesByPreviousAdvanceCalls) {
+  const char* original = "The Smiths are a great 80s band";
+  Cursor c(original);
+  c.Advance(4);
+  EXPECT_THAT(c.remaining(), Eq("Smiths are a great 80s band"));
+  EXPECT_THAT(c.remaining().begin(), Eq(original + 4));
+  c.Advance(11);
+  EXPECT_THAT(c.remaining(), Eq("a great 80s band"));
+  EXPECT_THAT(c.remaining().begin(), Eq(original + 15));
+  c.Advance(c.remaining().size());
+  EXPECT_THAT(c.remaining(), Eq(""));
+  EXPECT_THAT(c.remaining().begin(), Eq(original + 31));
+}
+
+// Exhausted method
+
+TEST(Cursor, ExhaustedImmediatelyWhenStartingWithEmptyString) {
+  Cursor c("");
+  EXPECT_TRUE(c.Exhausted());
+}
+
+TEST(Cursor, ExhaustedWhenRemainingIsEmpty) {
+  Cursor c("boo");
+  EXPECT_FALSE(c.Exhausted());
+  c.Advance(2);
+  EXPECT_FALSE(c.Exhausted());
+  c.Advance(1);
+  EXPECT_TRUE(c.Exhausted());
+}
+
+// RestOfLine method
+
+TEST(Cursor, RestOfLineOnEmptyReturnsEmpty) {
+  const char* original = "";
+  Cursor c(original);
+  EXPECT_THAT(c.RestOfLine(), Eq(""));
+  EXPECT_THAT(c.RestOfLine().begin(), Eq(original));
+}
+
+TEST(Cursor, RestOfLineWithoutNewline) {
+  Cursor c("The end");
+  EXPECT_THAT(c.RestOfLine(), Eq("The end"));
+}
+
+TEST(Cursor, RestOfLineGetsLineUpToAndIncludingNewline) {
+  Cursor c("The end\nOf an era");
+  EXPECT_THAT(c.RestOfLine(), Eq("The end\n"));
+}
+
+TEST(Cursor, RestOfLineGetsOnlyFromRemainingText) {
+  Cursor c("The end\nOf an era");
+  c.Advance(4);
+  EXPECT_THAT(c.remaining(), Eq("end\nOf an era"));
+  EXPECT_THAT(c.RestOfLine(), Eq("end\n"));
+}
+
+// AdvanceLine and line_num methods
+
+TEST(Cursor, AdvanceLineReturnsTheCursorItself) {
+  Cursor c("foo\nbar");
+  EXPECT_THAT(&c.AdvanceLine(), Eq(&c));
+}
+
+TEST(Cursor, AdvanceLineWalksThroughTextByLineAndCountsLines) {
+  const char* original = "The end\nOf an era\nIs here";
+  Cursor c(original);
+  EXPECT_THAT(c.line_num(), Eq(1));
+  c.AdvanceLine();
+  EXPECT_THAT(c.line_num(), Eq(2));
+  EXPECT_THAT(c.remaining(), Eq("Of an era\nIs here"));
+  EXPECT_THAT(c.remaining().begin(), Eq(original + 8));
+  c.AdvanceLine();
+  EXPECT_THAT(c.line_num(), Eq(3));
+  EXPECT_THAT(c.remaining(), Eq("Is here"));
+  EXPECT_THAT(c.remaining().begin(), Eq(original + 18));
+  c.AdvanceLine();
+  EXPECT_THAT(c.line_num(), Eq(4));
+  EXPECT_THAT(c.remaining(), Eq(""));
+  EXPECT_THAT(c.remaining().begin(), Eq(original + 25));
+}
+
+TEST(Cursor, AdvanceLineIsNoopAfterEndIsReached) {
+  Cursor c("One\nTwo");
+  c.AdvanceLine();
+  EXPECT_THAT(c.line_num(), Eq(2));
+  EXPECT_THAT(c.remaining(), Eq("Two"));
+  c.AdvanceLine();
+  EXPECT_THAT(c.line_num(), Eq(3));
+  EXPECT_THAT(c.remaining(), Eq(""));
+  c.AdvanceLine();
+  EXPECT_THAT(c.line_num(), Eq(3));
+  EXPECT_THAT(c.remaining(), Eq(""));
+}
+
+// LineMessage free function.
+
+TEST(LineMessage, SubtextIsFirst) {
+  StringPiece text("Foo\nBar");
+  StringPiece subtext(text.begin(), 3);
+  EXPECT_THAT(LineMessage(text, subtext, "loves quiche"),
+              Eq(":1:1: loves quiche\nFoo\n^\n"));
+}
+
+TEST(LineMessage, SubtextDoesNotEndInNewline) {
+  StringPiece text("Foo\nBar");
+  StringPiece subtext(text.begin()+4, 3);
+  EXPECT_THAT(LineMessage(text, subtext, "loves quiche"),
+              Eq(":2:1: loves quiche\nBar\n^\n"));
+}
+
+TEST(LineMessage, SubtextPartwayThroughItsLine) {
+  StringPiece text("Food Life\nBar");
+  StringPiece subtext(text.begin() + 5, 3); // "Lif"
+  EXPECT_THAT(LineMessage(text, subtext, "loves quiche"),
+              Eq(":1:6: loves quiche\nFood Life\n     ^\n"));
+}
+
+TEST(LineMessage, SubtextOnSubsequentLine) {
+  StringPiece text("Food Life\nBar Fight\n");
+  StringPiece subtext(text.begin() + 14, 5); // "Fight"
+  EXPECT_THAT(LineMessage(text, subtext, "loves quiche"),
+              Eq(":2:5: loves quiche\nBar Fight\n    ^\n"));
+}
+
+TEST(LineMessage, SubtextIsEmptyAndInMiddle) {
+  StringPiece text("Food");
+  StringPiece subtext(text.begin() + 2, 0);
+  EXPECT_THAT(LineMessage(text, subtext, "loves quiche"),
+              Eq(":1:3: loves quiche\nFood\n  ^\n"));
+}
+
+TEST(LineMessage, SubtextIsEmptyAndAtVeryEnd) {
+  StringPiece text("Food");
+  StringPiece subtext(text.begin() + 4, 0);
+  EXPECT_THAT(LineMessage(text, subtext, "loves quiche"),
+              Eq(":1:5: loves quiche\nFood\n    ^\n"));
+}
+
+}  // namespace
diff --git a/effcee/diagnostic.h b/effcee/diagnostic.h
new file mode 100644
index 0000000..b348687
--- /dev/null
+++ b/effcee/diagnostic.h
@@ -0,0 +1,59 @@
+// Copyright 2017 The Effcee Authors.
+//
+// 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.
+
+#ifndef EFFCEE_DIAGNOSTIC_H
+#define EFFCEE_DIAGNOSTIC_H
+
+#include <sstream>
+
+#include "effcee/effcee.h"
+
+namespace effcee {
+
+// A Diagnostic contains a Result::Status value and can accumulate message
+// values via operator<<.  It is convertible to a Result object containing the
+// status and the stringified message.
+class Diagnostic {
+ public:
+  explicit Diagnostic(Result::Status status) : status_(status) {}
+
+  // Copy constructor.
+  Diagnostic(const Diagnostic& other) : status_(other.status_), message_() {
+    // We can't move an ostringstream.  As a fallback, we'd like to use the
+    // std::ostringstream(std::string init_string) constructor.  However, that
+    // initial string disappears inexplicably the first time we shift onto
+    // the |message_| member.  So fall back further and use the default
+    // constructor and later use an explicit shift.
+    message_ << other.message_.str();
+  }
+
+  // Appends the given value to the accumulated message.
+  template <typename T>
+  Diagnostic& operator<<(const T& value) {
+    message_ << value;
+    return *this;
+  }
+
+  // Converts this object to a result value containing the stored status and a
+  // stringified copy of the message.
+  operator Result() const { return Result(status_, message_.str()); }
+
+ private:
+  Result::Status status_;
+  std::ostringstream message_;
+};
+
+}  // namespace effcee
+
+#endif
diff --git a/effcee/diagnostic_test.cc b/effcee/diagnostic_test.cc
new file mode 100644
index 0000000..acc89e9
--- /dev/null
+++ b/effcee/diagnostic_test.cc
@@ -0,0 +1,75 @@
+// Copyright 2017 The Effcee Authors.
+//
+// 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.
+
+#include "gmock/gmock.h"
+
+#include "diagnostic.h"
+
+namespace {
+
+using effcee::Diagnostic;
+using effcee::Result;
+using testing::Eq;
+
+using Status = effcee::Result::Status;
+
+// Check conversion preserves status.
+TEST(Diagnostic, ConvertsToResultWithSameOkStatus) {
+  const Diagnostic d(Status::Ok);
+  const Result r(d);
+  EXPECT_THAT(r.status(), Eq(Status::Ok));
+}
+
+TEST(Diagnostic, ConvertsToResultWithSameFailStatus) {
+  const Diagnostic d(Status::Fail);
+  const Result r(d);
+  EXPECT_THAT(r.status(), Eq(Status::Fail));
+}
+
+// Check conversion, with messages.
+
+TEST(Diagnostic, MessageDefaultsToEmpty) {
+  const Diagnostic d(Status::Ok);
+  const Result r(d);
+  EXPECT_THAT(r.message(), Eq(""));
+}
+
+TEST(Diagnostic, MessageAccumulatesValuesOfDifferentTypes) {
+  Diagnostic d(Status::Ok);
+  d << "hello" << ' ' << 42 << " and " << 32u << " and " << 1.25;
+  const Result r(d);
+  EXPECT_THAT(r.message(), Eq("hello 42 and 32 and 1.25"));
+}
+
+// Check copying
+
+TEST(Diagnostic, CopyRetainsOriginalMessage) {
+  Diagnostic d(Status::Ok);
+  d << "hello";
+  Diagnostic d2 = d;
+  const Result r(d2);
+  EXPECT_THAT(r.message(), Eq("hello"));
+}
+
+TEST(Diagnostic, ShiftOnCopyAppendsToOriginalMessage) {
+  Diagnostic d(Status::Ok);
+  d << "hello";
+  Diagnostic d2 = d;
+  d2 << " world";
+  const Result r(d2);
+  EXPECT_THAT(r.message(), Eq("hello world"));
+}
+
+
+}  // namespace
diff --git a/effcee/effcee.h b/effcee/effcee.h
new file mode 100644
index 0000000..eb1b1bb
--- /dev/null
+++ b/effcee/effcee.h
@@ -0,0 +1,113 @@
+// Copyright 2017 The Effcee Authors.
+//
+// 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.
+
+#ifndef EFFCEE_EFFCEE_H
+#define EFFCEE_EFFCEE_H
+
+#include <string>
+#include "re2/re2.h"
+
+namespace effcee {
+
+// TODO(dneto): Provide a check language tutorial / manual.
+
+// This does not implement the equivalents of FileCheck options:
+//   --match-full-lines
+//   --strict-whitespace
+//   --implicit-ch3eck-not
+//   --enable-var-scope
+
+using StringPiece = re2::StringPiece;
+
+// Options for matching.
+class Options {
+ public:
+  Options()
+      : prefix_("CHECK"), input_name_("<stdin>"), checks_name_("<stdin>") {}
+
+  // Sets rule prefix to a copy of |prefix|.  Returns this object.
+  Options& SetPrefix(StringPiece prefix) {
+    prefix_ = std::string(prefix.begin(), prefix.end());
+    return *this;
+  }
+  const std::string& prefix() const { return prefix_; }
+
+  // Sets the input name.  Returns this object.
+  // Use this for file names, for example.
+  Options& SetInputName(StringPiece name) {
+    input_name_ = std::string(name.begin(), name.end());
+    return *this;
+  }
+  const std::string& input_name() const { return input_name_; }
+
+  // Sets the checks input name.  Returns this object.
+  // Use this for file names, for example.
+  Options& SetChecksName(StringPiece name) {
+    checks_name_ = std::string(name.begin(), name.end());
+    return *this;
+  }
+  const std::string& checks_name() const { return checks_name_; }
+
+ private:
+  std::string prefix_;
+  std::string input_name_;
+  std::string checks_name_;
+};
+
+// The result of an attempted match.
+class Result {
+ public:
+  enum class Status {
+    Ok = 0,
+    Fail,       // A failure to match
+    BadOption,  // A bad option was specified
+    NoRules,    // No rules were specified
+    BadRule,    // A bad rule was specified
+  };
+
+  // Constructs a result with a given status.
+  explicit Result(Status status) : status_(status) {}
+  // Constructs a result with the given message.  Keeps a copy of the message.
+  Result(Status status, StringPiece message)
+      : status_(status), message_({message.begin(), message.end()}) {}
+
+  Status status() const { return status_; }
+
+  // Returns true if the match was successful.
+  operator bool() const { return status_ == Status::Ok; }
+
+  const std::string& message() const { return message_; }
+
+  // Sets the error message to a copy of |message|.  Returns this object.
+  Result& SetMessage(StringPiece message) {
+    message_ = std::string(message.begin(), message.end());
+    return *this;
+  }
+
+ private:
+  // Status code indicating success, or kind of failure.
+  Status status_;
+
+  // Message describing the failure, if any.  On success, this is empty.
+  std::string message_;
+};
+
+// Returns the result of attempting to match |text| against the pattern
+// program in |checks|, with the given |options|.
+Result Match(StringPiece text, StringPiece checks,
+             const Options& options = Options());
+
+}  // namespace effcee
+
+#endif
diff --git a/effcee/make_unique.h b/effcee/make_unique.h
new file mode 100644
index 0000000..f0b351d
--- /dev/null
+++ b/effcee/make_unique.h
@@ -0,0 +1,32 @@
+// Copyright 2017 The Effcee Authors.
+//
+// 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.
+
+#ifndef EFFCEE_MAKE_UNIQUE_H
+#define EFFCEE_MAKE_UNIQUE_H
+
+#include <memory>
+
+namespace effcee {
+
+// Constructs an object of type T and wraps it in a std::unique_ptr.
+// This functionality comes with C++14.  The following is the standard
+// recipe for use with C++11.
+template <typename T, typename... Args>
+std::unique_ptr<T> make_unique(Args&&... args) {
+  return std::unique_ptr<T>(new T(std::forward<Args>(args)...));
+}
+
+}  // namespace effcee
+
+#endif
diff --git a/effcee/match.cc b/effcee/match.cc
new file mode 100644
index 0000000..cb9517f
--- /dev/null
+++ b/effcee/match.cc
@@ -0,0 +1,265 @@
+// Copyright 2017 The Effcee Authors.
+//
+// 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.
+
+#include <algorithm>
+#include <cassert>
+#include <sstream>
+#include <string>
+#include <vector>
+
+#include "check.h"
+#include "cursor.h"
+#include "diagnostic.h"
+#include "effcee.h"
+#include "to_string.h"
+
+using effcee::Check;
+using Status = effcee::Result::Status;
+using Type = effcee::Check::Type;
+
+namespace effcee {
+
+Result Match(StringPiece input, StringPiece checks, const Options& options) {
+  const auto& parse_result = ParseChecks(checks, options);
+  if (!parse_result.first) return parse_result.first;
+
+  // A mapping from variable names to values.  This is updated when a check rule
+  // matches a variable definition.
+  VarMapping vars;
+
+  // We think of the input string as a sequence of lines that can satisfy
+  // the checks.  Walk through the rules until no unsatisfied checks are left.
+  // We will erase a check when it has been satisifed.
+  const CheckList& pattern = parse_result.second;
+  assert(pattern.size() > 0);
+
+  // What checks are resolved?  Entry |i| is true when check |i| in the
+  // pattern is resolved.
+  std::vector<bool> resolved(pattern.size(), false);
+
+  // The matching algorithm scans both the input and the pattern from start
+  // to finish.  At the start, all checks are unresolved.  We try to match
+  // each line in the input against the unresolved checks in a sliding window
+  // in the pattern.  When a positive check matches, we mark it as resolved.
+  // When a negative check matches, the algorithm terminates with failure.
+  // We mark a negative check as resolved when it is the earliest unresolved
+  // check and the first positive check after it is resolved.
+
+  // Initially the pattern window is just the first element.
+  // |first_check| is the first unresolved check.
+  size_t first_check = 0;
+  const size_t num_checks = pattern.size();
+
+  // The 1-based line number of the most recent successful match.
+  int matched_line_num = 0;
+
+  // Set up a cursor to scan the input, and helpers for generating diagnostics.
+  Cursor cursor(input);
+  // Points to the end of the previous positive match.
+  StringPiece previous_match_end = input.substr(0, 0);
+
+  // Returns a failure diagnostic without a message.;
+  auto fail = []() { return Diagnostic(Status::Fail); };
+  // Returns a string describing the filename, line, and column of a check rule,
+  // including the text of the check rule and a caret pointing to the parameter
+  // string.
+  auto check_msg = [&checks, &options](StringPiece where, StringPiece message) {
+    std::ostringstream out;
+    out << options.checks_name() << LineMessage(checks, where, message);
+    return out.str();
+  };
+  // Returns a string describing the filename, line, and column of an input
+  // string position, including the full line containing the position, and a
+  // caret pointing to the position.
+  auto input_msg = [&input, &options](StringPiece where, StringPiece message) {
+    std::ostringstream out;
+    out << options.input_name() << LineMessage(input, where, message);
+    return out.str();
+  };
+  // Returns a string describing the value of each variable use in the
+  // given check, in the context of the |where| portion of the input line.
+  auto var_notes = [&input_msg, &vars](StringPiece where, const Check& check) {
+    std::ostringstream out;
+    for (const auto& part : check.parts()) {
+      const auto var_use = part->VarUseName();
+      if (!var_use.empty()) {
+        std::ostringstream phrase;
+        std::string var_use_str(ToString(var_use));
+        if (vars.find(var_use_str) != vars.end()) {
+          phrase << "note: with variable \"" << var_use << "\" equal to \""
+                 << vars[var_use_str] << "\"";
+        } else {
+          phrase << "note: uses undefined variable \"" << var_use << "\"";
+        }
+        out << input_msg(where, phrase.str());
+      }
+    }
+    return out.str();
+  };
+
+  // For each line.
+  for (; !cursor.Exhausted(); cursor.AdvanceLine()) {
+    // Try to match the current line against the unresolved checks.
+
+    // The number of characters the cursor should advance to accommodate a
+    // recent DAG check match.
+    size_t deferred_advance = 0;
+
+    bool scan_this_line = true;
+    while (scan_this_line) {
+      // Skip the initial segment of resolved checks.  Slides the left end of
+      // the pattern window toward the right.
+      while (first_check < num_checks && resolved[first_check]) ++first_check;
+      // We've reached the end of the pattern.  Declare success.
+      if (first_check == num_checks) return Result(Result::Status::Ok);
+
+      size_t first_unresolved_dag = num_checks;
+      size_t first_unresolved_negative = num_checks;
+
+      bool resolved_something = false;
+
+      for (size_t i = first_check; i < num_checks; ++i) {
+        if (resolved[i]) continue;
+
+        const Check& check = pattern[i];
+
+        if (check.type() != Type::DAG) {
+          cursor.Advance(deferred_advance);
+          deferred_advance = 0;
+        }
+        const StringPiece rest_of_line = cursor.RestOfLine();
+        StringPiece unconsumed = rest_of_line;
+        StringPiece captured;
+
+        if (check.Matches(&unconsumed, &captured, &vars)) {
+          if (check.type() == Type::Not) {
+            return fail() << input_msg(captured,
+                                       "error: CHECK-NOT: string occurred!")
+                          << check_msg(
+                                 check.param(),
+                                 "note: CHECK-NOT: pattern specified here")
+                          << var_notes(captured, check);
+          }
+
+          if (check.type() == Type::Same &&
+              cursor.line_num() != matched_line_num) {
+            return fail()
+                   << check_msg(check.param(),
+                                "error: CHECK-SAME: is not on the same line as "
+                                "previous match")
+                   << input_msg(captured, "note: 'next' match was here")
+                   << input_msg(previous_match_end,
+                                "note: previous match ended here");
+          }
+
+          if (check.type() == Type::Next) {
+            if (cursor.line_num() == matched_line_num) {
+              return fail()
+                     << check_msg(check.param(),
+                                  "error: CHECK-NEXT: is on the same line as "
+                                  "previous match")
+                     << input_msg(captured, "note: 'next' match was here")
+                     << input_msg(previous_match_end,
+                                  "note: previous match ended here")
+                     << var_notes(previous_match_end, check);
+            }
+            if (cursor.line_num() > 1 + matched_line_num) {
+              // This must be valid since there was an intervening line.
+              const auto non_match =
+                  Cursor(input)
+                      .Advance(previous_match_end.begin() - input.begin())
+                      .AdvanceLine()
+                      .RestOfLine();
+
+              return fail()
+                     << check_msg(check.param(),
+                                  "error: CHECK-NEXT: is not on the line after "
+                                  "the previous match")
+                     << input_msg(captured, "note: 'next' match was here")
+                     << input_msg(previous_match_end,
+                                  "note: previous match ended here")
+                     << input_msg(non_match,
+                                  "note: non-matching line after previous "
+                                  "match is here")
+                     << var_notes(previous_match_end, check);
+            }
+          }
+
+          if (check.type() != Type::DAG && first_unresolved_dag < i) {
+            return fail()
+                   << check_msg(pattern[first_unresolved_dag].param(),
+                                "error: expected string not found in input")
+                   << input_msg(previous_match_end, "note: scanning from here")
+                   << input_msg(captured, "note: next check matches here")
+                   << var_notes(previous_match_end, check);
+          }
+
+          resolved[i] = true;
+          matched_line_num = cursor.line_num();
+          previous_match_end = unconsumed;
+          resolved_something = true;
+
+          // Resolve any prior negative checks that precede an unresolved DAG.
+          for (auto j = first_unresolved_negative,
+                    limit = std::min(first_unresolved_dag, i);
+               j < limit; ++j) {
+            resolved[j] = true;
+          }
+
+          // Normally advance past the matched text.  But DAG checks might need
+          // to match out of order on the same line.  So only advance for
+          // non-DAG cases.
+
+          const size_t advance_proposal =
+              rest_of_line.size() - unconsumed.size();
+          if (check.type() == Type::DAG) {
+            deferred_advance = std::max(deferred_advance, advance_proposal);
+          } else {
+            cursor.Advance(advance_proposal);
+          }
+
+        } else {
+          // This line did not match the check.
+          if (check.type() == Type::Not) {
+            first_unresolved_negative = std::min(first_unresolved_negative, i);
+            // An unresolved Not check stops the search for more DAG checks.
+            if (first_unresolved_dag < num_checks) i = num_checks;
+          } else if (check.type() == Type::DAG) {
+            first_unresolved_dag = std::min(first_unresolved_dag, i);
+          } else {
+            // An unresolved non-DAG check check stops this pass over the
+            // checks.
+            i = num_checks;
+          }
+        }
+      }
+      scan_this_line = resolved_something;
+    }
+  }
+
+  // Fail if there are any unresolved positive checks.
+  for (auto i = first_check; i < num_checks; ++i) {
+    if (resolved[i]) continue;
+    const auto check = pattern[i];
+    if (check.type() == Type::Not) continue;
+
+    return fail() << check_msg(check.param(),
+                               "error: expected string not found in input")
+                  << input_msg(previous_match_end, "note: scanning from here")
+                  << var_notes(previous_match_end, check);
+  }
+
+  return Result(Result::Status::Ok);
+}
+}  // namespace effcee
diff --git a/effcee/match_test.cc b/effcee/match_test.cc
new file mode 100644
index 0000000..65350f0
--- /dev/null
+++ b/effcee/match_test.cc
@@ -0,0 +1,894 @@
+// Copyright 2017 The Effcee Authors.
+//
+// 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.
+
+#include "gmock/gmock.h"
+
+#include "effcee.h"
+
+namespace {
+
+using effcee::Match;
+using effcee::Options;
+using ::testing::Eq;
+using ::testing::HasSubstr;
+
+const char* kNotFound = "error: expected string not found in input";
+const char* kMissedSame =
+    "error: CHECK-SAME: is not on the same line as previous match";
+const char* kNextOnSame =
+    "error: CHECK-NEXT: is on the same line as previous match";
+const char* kNextTooLate =
+    "error: CHECK-NEXT: is not on the line after the previous match";
+const char* kNotStrFound = "error: CHECK-NOT: string occurred!";
+
+// Match free function
+
+TEST(Match, FreeFunctionLinks) {
+  Match("", "");
+  Match("", "", effcee::Options());
+}
+
+// Simple checks
+
+TEST(Match, OneSimpleCheckPass) {
+  const auto result = Match("Hello", "CHECK: Hello");
+  EXPECT_TRUE(result) << result.message();
+}
+
+TEST(Match, OneSimpleCheckFail) {
+  const auto result = Match("World", "CHECK: Hello");
+  EXPECT_FALSE(result) << result.message();
+  EXPECT_THAT(result.message(), HasSubstr(kNotFound));
+  EXPECT_THAT(result.message(), HasSubstr("CHECK: Hello"));
+}
+
+TEST(Match, TwoSimpleChecksPass) {
+  const auto result = Match("Hello\nWorld", "CHECK: Hello\nCHECK: World");
+  EXPECT_TRUE(result) << result.message();
+}
+
+TEST(Match, RepeatedCheckFails) {
+  const auto result = Match("Hello\nWorld", "CHECK: Hello\nCHECK: Hello");
+  EXPECT_FALSE(result) << result.message();
+  EXPECT_THAT(result.message(), HasSubstr(kNotFound));
+}
+
+TEST(Match, TwoSimpleChecksPassWithSurroundingText) {
+  const auto input = R"(Say
+                        Hello
+                        World
+                        Today)";
+  const auto result = Match(input, "CHECK: Hello\nCHECK: World");
+  EXPECT_TRUE(result) << result.message();
+}
+
+TEST(Match, TwoSimpleChecksPassWithInterveningText) {
+  const auto input = R"(Hello
+                        Between
+                        World)";
+  const auto result = Match(input, "CHECK: Hello\nCHECK: World");
+  EXPECT_TRUE(result) << result.message();
+}
+
+TEST(Match, TwoSimpleChecksPassWhenInSequenceSameLine) {
+  const auto result = Match("HelloWorld", "CHECK: Hello\nCHECK: World");
+  EXPECT_TRUE(result) << result.message();
+}
+
+TEST(Match, TwoSimpleChecksFailWhenReversed) {
+  const auto result = Match("HelloWorld", "CHECK: World\nCHECK: Hello");
+  EXPECT_FALSE(result) << result.message();
+  EXPECT_THAT(result.message(), HasSubstr(kNotFound));
+  EXPECT_THAT(result.message(), HasSubstr("CHECK: Hello"));
+}
+
+TEST(Match, SimpleThenSamePasses) {
+  const auto result = Match("HelloWorld", "CHECK: Hello\nCHECK-SAME: World");
+  EXPECT_TRUE(result) << result.message();
+}
+
+TEST(Match, SimpleThenSamePassesWithInterveningOnSameLine) {
+  const auto result = Match("Hello...World", "CHECK: Hello\nCHECK-SAME: World");
+  EXPECT_TRUE(result) << result.message();
+}
+
+TEST(Match, SimpleThenSameFailsIfOnNextLine) {
+  const auto result = Match("Hello\nWorld", "CHECK: Hello\nCHECK-SAME: World");
+  EXPECT_FALSE(result) << result.message();
+  EXPECT_THAT(result.message(),HasSubstr(kMissedSame));
+  EXPECT_THAT(result.message(), HasSubstr("CHECK-SAME: World"));
+}
+
+TEST(Match, SimpleThenSameFailsIfOnMuchLaterLine) {
+  const auto result =
+      Match("Hello\n\nz\n\nWorld", "CHECK: Hello\nCHECK-SAME: World");
+  EXPECT_FALSE(result) << result.message();
+  EXPECT_THAT(result.message(), HasSubstr(kMissedSame));
+  EXPECT_THAT(result.message(), HasSubstr("CHECK-SAME: World"));
+}
+
+TEST(Match, SimpleThenSameFailsIfNeverMatched) {
+  const auto result = Match("Hello\nHome", "CHECK: Hello\nCHECK-SAME: World");
+  EXPECT_FALSE(result) << result.message();
+  EXPECT_THAT(result.message(), HasSubstr(kNotFound));
+  EXPECT_THAT(result.message(), HasSubstr("CHECK-SAME: World"));
+}
+
+TEST(Match, SimpleThenNextOnSameLineFails) {
+  const auto result = Match("HelloWorld", "CHECK: Hello\nCHECK-NEXT: World");
+  EXPECT_FALSE(result);
+  EXPECT_THAT(result.message(), HasSubstr(kNextOnSame));
+  EXPECT_THAT(result.message(), HasSubstr("CHECK-NEXT: World"));
+}
+
+TEST(Match, SimpleThenNextPassesIfOnNextLine) {
+  const auto result = Match("Hello\nWorld", "CHECK: Hello\nCHECK-NEXT: World");
+  EXPECT_TRUE(result) << result.message();
+}
+
+TEST(Match, SimpleThenNextFailsIfOnAfterNextLine) {
+  const auto result = Match("Hello\nfoo\nWorld", "CHECK: Hello\nCHECK-NEXT: World");
+  EXPECT_THAT(result.message(), HasSubstr(kNextTooLate));
+  EXPECT_THAT(result.message(), HasSubstr("CHECK-NEXT: World"));
+}
+
+TEST(Match, SimpleThenNextFailsIfNeverMatched) {
+  const auto result =
+      Match("Hello\nHome", "CHECK: Hello\nCHECK-NEXT: World");
+  EXPECT_FALSE(result) << result.message();
+  EXPECT_THAT(result.message(), HasSubstr(kNotFound));
+  EXPECT_THAT(result.message(), HasSubstr("CHECK-NEXT: World"));
+}
+
+// TODO: CHECK-NOT
+
+TEST(Match, AloneNotNeverSeenPasses) {
+  const auto result = Match("Hello", "CHECK-NOT: Borg");
+  EXPECT_TRUE(result);
+}
+
+TEST(Match, LeadingNotNeverSeenPasses) {
+  const auto result = Match("Hello", "CHECK-NOT: Borg\nCHECK: Hello");
+  EXPECT_TRUE(result);
+}
+
+TEST(Match, BetweenNotNeverSeenPasses) {
+  const auto result =
+      Match("HelloWorld", "CHECK: Hello\nCHECK-NOT: Borg\nCHECK: World");
+  EXPECT_TRUE(result);
+}
+
+TEST(Match, BetweenNotDotsNeverSeenPasses) {
+  // The before and after matches occur on the same line.
+  const auto result =
+      Match("Hello...World", "CHECK: Hello\nCHECK-NOT: Borg\nCHECK: World");
+  EXPECT_TRUE(result);
+}
+
+TEST(Match, BetweenNotLinesNeverSeenPasses) {
+  // The before and after matches occur on different lines.
+  const auto result =
+      Match("Hello\nz\nWorld", "CHECK: Hello\nCHECK-NOT: Borg\nCHECK: World");
+  EXPECT_TRUE(result);
+}
+
+TEST(Match, NotBetweenMatchesPasses) {
+  const auto result =
+      Match("Hello\nWorld\nBorg\n", "CHECK: Hello\nCHECK-NOT: Borg\nCHECK: World");
+  EXPECT_TRUE(result);
+}
+
+TEST(Match, NotBeforeFirstMatchPasses) {
+  const auto result =
+      Match("Hello\nWorld\nBorg\n", "CHECK-NOT: World\nCHECK: Hello");
+  EXPECT_TRUE(result);
+}
+
+TEST(Match, NotAfterLastMatchPasses) {
+  const auto result =
+      Match("Hello\nWorld\nBorg\n", "CHECK: World\nCHECK-NOT: Hello");
+  EXPECT_TRUE(result);
+}
+
+TEST(Match, NotBeforeFirstMatchFails) {
+  const auto result =
+      Match("Hello\nWorld\n", "CHECK-NOT: Hello\nCHECK: World");
+  EXPECT_FALSE(result);
+}
+
+TEST(Match, NotBetweenMatchesFails) {
+  const auto result =
+      Match("Hello\nWorld\nBorg\n", "CHECK: Hello\nCHECK-NOT: World\nCHECK: Borg");
+  EXPECT_FALSE(result);
+}
+
+TEST(Match, NotAfterLastMatchFails) {
+  const auto result =
+      Match("Hello\nWorld\n", "CHECK: Hello\nCHECK-NOT: World");
+  EXPECT_FALSE(result);
+}
+
+TEST(Match, TrailingNotNeverSeenPasses) {
+  const auto result = Match("Hello", "CHECK: Hello\nCHECK-NOT: Borg");
+  EXPECT_TRUE(result);
+}
+
+TEST(Match, AloneNotSeenFails) {
+  const auto result = Match("Borg", "CHECK-NOT: Borg");
+  EXPECT_FALSE(result);
+  EXPECT_THAT(result.message(), HasSubstr(kNotStrFound));
+  EXPECT_THAT(result.message(), HasSubstr("CHECK-NOT: Borg"));
+}
+
+TEST(Match, LeadingNotSeenFails) {
+  const auto result = Match("Borg", "CHECK-NOT: Borg\nCHECK: Hello");
+  EXPECT_FALSE(result);
+  EXPECT_THAT(result.message(), HasSubstr(kNotStrFound));
+  EXPECT_THAT(result.message(), HasSubstr("CHECK-NOT: Borg"));
+}
+
+TEST(Match, BetweenNotSeenFails) {
+  const auto result =
+      Match("HelloBorgWorld", "CHECK: Hello\nCHECK-NOT: Borg\nCHECK: World");
+  EXPECT_FALSE(result);
+  EXPECT_THAT(result.message(), HasSubstr(kNotStrFound));
+  EXPECT_THAT(result.message(), HasSubstr("CHECK-NOT: Borg"));
+}
+
+TEST(Match, BetweenNotDotsSeenFails) {
+  const auto result =
+      Match("Hello.Borg.World", "CHECK: Hello\nCHECK-NOT: Borg\nCHECK: World");
+  EXPECT_FALSE(result);
+  EXPECT_THAT(result.message(), HasSubstr(kNotStrFound));
+  EXPECT_THAT(result.message(), HasSubstr("CHECK-NOT: Borg"));
+}
+
+TEST(Match, BetweenNotLinesSeenFails) {
+  const auto result = Match("Hello\nBorg\nWorld",
+                            "CHECK: Hello\nCHECK-NOT: Borg\nCHECK: World");
+  EXPECT_FALSE(result);
+  EXPECT_THAT(result.message(), HasSubstr(kNotStrFound));
+  EXPECT_THAT(result.message(), HasSubstr("CHECK-NOT: Borg"));
+}
+
+TEST(Match, TrailingNotSeenFails) {
+  const auto result = Match("HelloBorg", "CHECK: Hello\nCHECK-NOT: Borg");
+  EXPECT_FALSE(result);
+  EXPECT_THAT(result.message(), HasSubstr(kNotStrFound));
+  EXPECT_THAT(result.message(), HasSubstr("CHECK-NOT: Borg"));
+}
+
+// WIP: CHECK-LABEL
+
+TEST(Match, OneLabelCheckPass) {
+  const auto result = Match("Hello", "CHECK-LABEL: Hello");
+  EXPECT_TRUE(result) << result.message();
+}
+
+TEST(Match, OneLabelCheckFail) {
+  const auto result = Match("World", "CHECK-LABEL: Hello");
+  EXPECT_FALSE(result) << result.message();
+  EXPECT_THAT(result.message(), HasSubstr(kNotFound));
+  EXPECT_THAT(result.message(), HasSubstr("CHECK-LABEL: Hello"));
+}
+
+TEST(Match, TwoLabelChecksPass) {
+  const auto result =
+      Match("Hello\nWorld", "CHECK-LABEL: Hello\nCHECK-LABEL: World");
+  EXPECT_TRUE(result) << result.message();
+}
+
+TEST(Match, TwoLabelChecksPassWithSurroundingText) {
+  const auto input = R"(Say
+                        Hello
+                        World
+                        Today)";
+  const auto result = Match(input, "CHECK-LABEL: Hello\nCHECK-LABEL: World");
+  EXPECT_TRUE(result) << result.message();
+}
+
+TEST(Match, TwoLabelChecksPassWithInterveningText) {
+  const auto input = R"(Hello
+                        Between
+                        World)";
+  const auto result = Match(input, "CHECK-LABEL: Hello\nCHECK-LABEL: World");
+  EXPECT_TRUE(result) << result.message();
+}
+
+TEST(Match, TwoLabelChecksPassWhenInSequenceSameLine) {
+  const auto result =
+      Match("HelloWorld", "CHECK-LABEL: Hello\nCHECK-LABEL: World");
+  EXPECT_TRUE(result) << result.message();
+}
+
+TEST(Match, TwoLabelChecksFailWhenReversed) {
+  const auto result =
+      Match("HelloWorld", "CHECK-LABEL: World\nCHECK-LABEL: Hello");
+  EXPECT_FALSE(result) << result.message();
+  EXPECT_THAT(result.message(), HasSubstr(kNotFound));
+  EXPECT_THAT(result.message(), HasSubstr("CHECK-LABEL: Hello"));
+}
+
+// WIP: Mixture of Simple and Label checks
+
+TEST(Match, SimpleAndLabelChecksPass) {
+  const auto result = Match("Hello\nWorld", "CHECK: Hello\nCHECK-LABEL: World");
+  EXPECT_TRUE(result) << result.message();
+}
+
+TEST(Match, LabelAndSimpleChecksPass) {
+  const auto result = Match("Hello\nWorld", "CHECK-LABEL: Hello\nCHECK: World");
+  EXPECT_TRUE(result) << result.message();
+}
+
+TEST(Match, SimpleAndLabelChecksFails) {
+  const auto result = Match("Hello\nWorld", "CHECK: Hello\nCHECK-LABEL: Band");
+  EXPECT_FALSE(result) << result.message();
+  EXPECT_THAT(result.message(), HasSubstr(kNotFound));
+  EXPECT_THAT(result.message(), HasSubstr("CHECK-LABEL: Band"));
+}
+
+TEST(Match, LabelAndSimpleChecksFails) {
+  const auto result = Match("Hello\nWorld", "CHECK-LABEL: Hello\nCHECK: Band");
+  EXPECT_FALSE(result) << result.message();
+  EXPECT_THAT(result.message(), HasSubstr(kNotFound));
+  EXPECT_THAT(result.message(), HasSubstr("CHECK: Band"));
+}
+
+// DAG checks: Part 1: Tests simlar to simple checks tests
+
+TEST(Match, OneDAGCheckPass) {
+  const auto result = Match("Hello", "CHECK-DAG: Hello");
+  EXPECT_TRUE(result) << result.message();
+}
+
+TEST(Match, OneDAGCheckFail) {
+  const auto result = Match("World", "CHECK-DAG: Hello");
+  EXPECT_FALSE(result) << result.message();
+  EXPECT_THAT(result.message(), HasSubstr(kNotFound));
+  EXPECT_THAT(result.message(), HasSubstr("CHECK-DAG: Hello"));
+}
+
+TEST(Match, TwoDAGChecksPass) {
+  const auto result = Match("Hello\nWorld", "CHECK-DAG: Hello\nCHECK-DAG: World");
+  EXPECT_TRUE(result) << result.message();
+}
+
+TEST(Match, TwoDAGChecksPassWithSurroundingText) {
+  const auto input = R"(Say
+                        Hello
+                        World
+                        Today)";
+  const auto result = Match(input, "CHECK-DAG: Hello\nCHECK-DAG: World");
+  EXPECT_TRUE(result) << result.message();
+}
+
+TEST(Match, TwoDAGChecksPassWithInterveningText) {
+  const auto input = R"(Hello
+                        Between
+                        World)";
+  const auto result = Match(input, "CHECK-DAG: Hello\nCHECK-DAG: World");
+  EXPECT_TRUE(result) << result.message();
+}
+
+TEST(Match, TwoDAGChecksPassWhenInSequenceSameLine) {
+  const auto result = Match("HelloWorld", "CHECK-DAG: Hello\nCHECK-DAG: World");
+  EXPECT_TRUE(result) << result.message();
+}
+
+TEST(Match, DAGThenSamePasses) {
+  const auto result = Match("HelloWorld", "CHECK-DAG: Hello\nCHECK-SAME: World");
+  EXPECT_TRUE(result) << result.message();
+}
+
+TEST(Match, DAGThenSamePassesWithInterveningOnSameLine) {
+  const auto result = Match("Hello...World", "CHECK-DAG: Hello\nCHECK-SAME: World");
+  EXPECT_TRUE(result) << result.message();
+}
+
+TEST(Match, DAGThenSameFailsIfOnNextLine) {
+  const auto result = Match("Hello\nWorld", "CHECK-DAG: Hello\nCHECK-SAME: World");
+  EXPECT_FALSE(result) << result.message();
+  EXPECT_THAT(result.message(), HasSubstr(kMissedSame));
+  EXPECT_THAT(result.message(), HasSubstr("CHECK-SAME: World"));
+}
+
+TEST(Match, DAGThenSameFailsIfOnMuchLaterLine) {
+  const auto result =
+      Match("Hello\n\nz\n\nWorld", "CHECK-DAG: Hello\nCHECK-SAME: World");
+  EXPECT_FALSE(result) << result.message();
+  EXPECT_THAT(result.message(), HasSubstr(kMissedSame));
+  EXPECT_THAT(result.message(), HasSubstr("CHECK-SAME: World"));
+}
+
+TEST(Match, DAGThenSameFailsIfNeverMatched) {
+  const auto result = Match("Hello\nHome", "CHECK-DAG: Hello\nCHECK-SAME: World");
+  EXPECT_FALSE(result) << result.message();
+  EXPECT_THAT(result.message(), HasSubstr(kNotFound));
+  EXPECT_THAT(result.message(), HasSubstr("CHECK-SAME: World"));
+}
+
+TEST(Match, DAGThenNextOnSameLineFails) {
+  const auto result = Match("HelloWorld", "CHECK-DAG: Hello\nCHECK-NEXT: World");
+  EXPECT_FALSE(result);
+  EXPECT_THAT(result.message(), HasSubstr(kNextOnSame));
+  EXPECT_THAT(result.message(), HasSubstr("CHECK-NEXT: World"));
+}
+
+TEST(Match, DAGThenNextPassesIfOnNextLine) {
+  const auto result = Match("Hello\nWorld", "CHECK-DAG: Hello\nCHECK-NEXT: World");
+  EXPECT_TRUE(result) << result.message();
+}
+
+TEST(Match, DAGThenNextPassesIfOnAfterNextLine) {
+  const auto result = Match("Hello\nWorld", "CHECK-DAG: Hello\nCHECK-NEXT: World");
+  EXPECT_TRUE(result) << result.message();
+}
+
+TEST(Match, DAGThenNextFailsIfNeverMatched) {
+  const auto result =
+      Match("Hello\nHome", "CHECK-DAG: Hello\nCHECK-NEXT: World");
+  EXPECT_FALSE(result) << result.message();
+  EXPECT_THAT(result.message(), HasSubstr(kNotFound));
+  EXPECT_THAT(result.message(), HasSubstr("CHECK-NEXT: World"));
+}
+
+// DAG checks: Part 2: Out of order matching
+
+TEST(Match, TwoDAGMatchedOutOfOrderPasses) {
+  const auto result = Match("Hello\nWorld", "CHECK-DAG: World\nCHECK-DAG: Hello");
+  EXPECT_TRUE(result) << result.message();
+}
+
+TEST(Match, ThreeDAGMatchedOutOfOrderPasses) {
+  const auto result =
+      Match("Hello\nWorld\nNow",
+            "CHECK-DAG: Now\nCHECK-DAG: World\nCHECK-DAG: Hello");
+  EXPECT_TRUE(result) << result.message();
+}
+
+TEST(Match, TwoDAGChecksPassWhenReversedMatchingSameLine) {
+  const auto result = Match("HelloWorld", "CHECK-DAG: World\nCHECK-DAG: Hello");
+  EXPECT_TRUE(result) << result.message();
+}
+
+TEST(Match, DAGChecksGreedilyConsumeInput) {
+  const auto result =
+      Match("Hello\nBlocker\nWorld\n",
+            "CHECK-DAG: Hello\nCHECK-DAG: World\nCHECK: Blocker");
+  EXPECT_FALSE(result) << result.message();
+  EXPECT_THAT(result.message(), HasSubstr(kNotFound));
+  EXPECT_THAT(result.message(), HasSubstr("CHECK-DAG: World"));
+}
+
+// DAG checks: Part 3: Interaction with Not checks
+
+TEST(Match, DAGsAreSeparatedByNot) {
+  // In this case the search for "Before" consumes the entire input.
+  const auto result =
+      Match("After\nBlocker\nBefore\n",
+            "CHECK-DAG: Before\nCHECK-NOT: nothing\nCHECK-DAG: After");
+  EXPECT_FALSE(result) << result.message();
+  EXPECT_THAT(result.message(), HasSubstr(kNotFound));
+  EXPECT_THAT(result.message(), HasSubstr("CHECK-DAG: After"));
+}
+
+TEST(Match, TwoDAGsAreSeparatedByNot) {
+  const auto result = Match("After\nApres\nBlocker\nBefore\nAnte",
+                            "CHECK-DAG: Ante\nCHECK-DAG: Before\nCHECK-NOT: "
+                            "nothing\nCHECK-DAG: Apres\nCHECK-DAG: After");
+  EXPECT_FALSE(result) << result.message();
+  EXPECT_THAT(result.message(), HasSubstr(kNotFound));
+  EXPECT_THAT(result.message(), HasSubstr("CHECK-DAG: Apres"));
+}
+
+// DAG checks: Part 4: Interaction with simple checks
+
+TEST(Match, DAGsAreTerminatedBySimple) {
+  const auto result =
+      Match("After\nsimple\nBefore\n",
+            "CHECK-DAG: Before\nCHECK: simple\nCHECK-DAG: After");
+  EXPECT_FALSE(result) << result.message();
+  EXPECT_THAT(result.message(), HasSubstr(kNotFound));
+  EXPECT_THAT(result.message(), HasSubstr("CHECK-DAG: Before"));
+}
+
+TEST(Match, TwoDAGsAreTerminatedBySimple) {
+  const auto result = Match("After\nApres\nBlocker\nBefore\nAnte",
+                            "CHECK-DAG: Ante\nCHECK-DAG: Before\nCHECK: "
+                            "Blocker\nCHECK-DAG: Apres\nCHECK-DAG: After");
+  EXPECT_FALSE(result) << result.message();
+  EXPECT_THAT(result.message(), HasSubstr(kNotFound));
+  EXPECT_THAT(result.message(), HasSubstr("CHECK-DAG: Ante"));
+}
+
+// Test detailed message text
+
+TEST(Match, MessageStringNotFoundWhenNeverMatchedAnything) {
+  const char* input = R"(Begin
+Hello
+ World)";
+  const char* checks = R"(
+Hello
+  ;  CHECK: Needle
+)";
+  const char* expected = R"(chklist:3:13: error: expected string not found in input
+  ;  CHECK: Needle
+            ^
+myin.txt:1:1: note: scanning from here
+Begin
+^
+)";
+  const auto result =
+      Match(input, checks,
+            Options().SetInputName("myin.txt").SetChecksName("chklist"));
+  EXPECT_FALSE(result);
+  EXPECT_THAT(result.message(), Eq(expected)) << result.message();
+}
+
+TEST(Match, MessageStringNotFoundAfterInitialMatch) {
+  const char* input = R"(Begin
+Hello
+ World)";
+  const char* checks = R"(
+Hello
+  ;  CHECK-LABEL: Hel
+  ;  CHECK: Needle
+)";
+  const char* expected = R"(chklist:4:13: error: expected string not found in input
+  ;  CHECK: Needle
+            ^
+myin.txt:2:4: note: scanning from here
+Hello
+   ^
+)";
+  const auto result =
+      Match(input, checks,
+            Options().SetInputName("myin.txt").SetChecksName("chklist"));
+  EXPECT_FALSE(result);
+  EXPECT_THAT(result.message(), Eq(expected)) << result.message();
+}
+
+TEST(Match, MessageCheckNotStringFoundAtStart) {
+  const auto result =
+      Match("  Cheese", "CHECK-NOT: Cheese",
+            Options().SetInputName("in").SetChecksName("checks"));
+  EXPECT_FALSE(result);
+  const char* expected = R"(in:1:3: error: CHECK-NOT: string occurred!
+  Cheese
+  ^
+checks:1:12: note: CHECK-NOT: pattern specified here
+CHECK-NOT: Cheese
+           ^
+)";
+  EXPECT_THAT(result.message(), Eq(expected)) << result.message();
+}
+
+TEST(Match, MessageCheckNotStringFoundAfterInitialMatch) {
+  const auto result =
+      Match("Cream    Cheese", "CHECK: Cream\nCHECK-NOT: Cheese",
+            Options().SetInputName("in").SetChecksName("checks"));
+  EXPECT_FALSE(result);
+  const char* expected = R"(in:1:10: error: CHECK-NOT: string occurred!
+Cream    Cheese
+         ^
+checks:2:12: note: CHECK-NOT: pattern specified here
+CHECK-NOT: Cheese
+           ^
+)";
+  EXPECT_THAT(result.message(), Eq(expected)) << result.message();
+}
+
+TEST(Match, MessageCheckSameFails) {
+  const char* input = R"(
+Bees
+Make
+Delicious Honey
+)";
+  const char* checks = R"(
+CHECK: Make
+CHECK-SAME: Honey
+)";
+
+  const auto result = Match(
+      input, checks, Options().SetInputName("in").SetChecksName("checks"));
+  EXPECT_FALSE(result);
+  const char* expected = R"(checks:3:13: error: CHECK-SAME: is not on the same line as previous match
+CHECK-SAME: Honey
+            ^
+in:4:11: note: 'next' match was here
+Delicious Honey
+          ^
+in:3:5: note: previous match ended here
+Make
+    ^
+)";
+  EXPECT_THAT(result.message(), Eq(expected)) << result.message();
+}
+
+TEST(Match, MessageCheckNextFailsSinceOnSameLine) {
+  const char* input = R"(
+Bees
+Make
+Delicious Honey
+)";
+  const char* checks = R"(
+CHECK: Bees
+CHECK-NEXT: Honey
+)";
+
+  const auto result = Match(
+      input, checks, Options().SetInputName("in").SetChecksName("checks"));
+  EXPECT_FALSE(result);
+  const char* expected = R"(checks:3:13: error: CHECK-NEXT: is not on the line after the previous match
+CHECK-NEXT: Honey
+            ^
+in:4:11: note: 'next' match was here
+Delicious Honey
+          ^
+in:2:5: note: previous match ended here
+Bees
+    ^
+in:3:1: note: non-matching line after previous match is here
+Make
+^
+)";
+  EXPECT_THAT(result.message(), Eq(expected)) << result.message();
+}
+
+TEST(Match, MessageCheckNextFailsSinceLaterLine) {
+  const char* input = R"(
+Bees Make Delicious Honey
+)";
+  const char* checks = R"(
+CHECK: Make
+CHECK-NEXT: Honey
+)";
+
+  const auto result = Match(
+      input, checks, Options().SetInputName("in").SetChecksName("checks"));
+  EXPECT_FALSE(result);
+  const char* expected = R"(checks:3:13: error: CHECK-NEXT: is on the same line as previous match
+CHECK-NEXT: Honey
+            ^
+in:2:21: note: 'next' match was here
+Bees Make Delicious Honey
+                    ^
+in:2:10: note: previous match ended here
+Bees Make Delicious Honey
+         ^
+)";
+  EXPECT_THAT(result.message(), Eq(expected)) << result.message();
+}
+
+TEST(Match, MessageUnresolvedDAG) {
+  const char* input = R"(
+Bees
+Make
+Delicious Honey
+)";
+  const char* checks = R"(
+CHECK: ees
+CHECK-DAG: Flowers
+CHECK: Honey
+)";
+
+  const auto result = Match(
+      input, checks, Options().SetInputName("in").SetChecksName("checks"));
+  EXPECT_FALSE(result);
+  const char* expected = R"(checks:3:12: error: expected string not found in input
+CHECK-DAG: Flowers
+           ^
+in:2:5: note: scanning from here
+Bees
+    ^
+in:4:11: note: next check matches here
+Delicious Honey
+          ^
+)";
+  EXPECT_THAT(result.message(), Eq(expected)) << result.message();
+}
+
+
+// Regexp
+
+TEST(Match, CheckRegexPass) {
+  const auto result = Match("Hello", "CHECK: He{{ll}}o");
+  EXPECT_TRUE(result) << result.message();
+}
+
+TEST(Match, CheckRegexWithFalseStartPass) {
+  // This examples has three false starts.  That is, we match the first
+  // few parts of the pattern before we finally match it.
+  const auto result = Match("He Hel Hell Hello Helloo", "CHECK: He{{ll}}oo");
+  EXPECT_TRUE(result) << result.message();
+}
+
+TEST(Match, CheckRegexWithRangePass) {
+  const auto result = Match("Hello", "CHECK: He{{[a-z]+}}o");
+  EXPECT_TRUE(result) << result.message();
+}
+
+TEST(Match, CheckRegexMatchesEmptyPass) {
+  const auto result = Match("Heo", "CHECK: He{{[a-z]*}}o");
+  EXPECT_TRUE(result) << result.message();
+}
+
+TEST(Match, CheckThreeRegexPass) {
+  // This proves that we parsed the check correctly, finding matching pairs
+  // of regexp delimiters {{ and }}.
+  const auto result = Match("Hello World", "CHECK: He{{[a-z]+}}o{{ +}}{{[Ww]}}orld");
+  EXPECT_TRUE(result) << result.message();
+}
+
+TEST(Match, CheckRegexFail) {
+  const auto result = Match("Heo", "CHECK: He{{[a-z]*}}o");
+  EXPECT_TRUE(result) << result.message();
+}
+
+TEST(Match, MessageStringRegexRegexWithFalseStartFail) {
+  const char* input = "He Hel Hell Hello Hello";
+  const char* checks = "CHECK: He{{ll}}oo";
+  const char* expected = R"(chklist:1:8: error: expected string not found in input
+CHECK: He{{ll}}oo
+       ^
+myin.txt:1:1: note: scanning from here
+He Hel Hell Hello Hello
+^
+)";
+  const auto result =
+      Match(input, checks,
+            Options().SetInputName("myin.txt").SetChecksName("chklist"));
+  EXPECT_FALSE(result);
+  EXPECT_THAT(result.message(), Eq(expected)) << result.message();
+}
+
+TEST(Match, MessageStringRegexNotFoundWhenNeverMatchedAnything) {
+  const char* input = R"(Begin
+Hello
+ World)";
+  const char* checks = R"(
+Hello
+  ;  CHECK: He{{[0-9]+}}llo
+)";
+  const char* expected = R"(chklist:3:13: error: expected string not found in input
+  ;  CHECK: He{{[0-9]+}}llo
+            ^
+myin.txt:1:1: note: scanning from here
+Begin
+^
+)";
+  const auto result =
+      Match(input, checks,
+            Options().SetInputName("myin.txt").SetChecksName("chklist"));
+  EXPECT_FALSE(result);
+  EXPECT_THAT(result.message(), Eq(expected)) << result.message();
+}
+
+
+// Statefulness: variable definitions and uses
+
+TEST(Match, VarDefFollowedByUsePass) {
+  const auto result =
+      Match("Hello\nHello", "CHECK: H[[X:[a-z]+]]o\nCHECK-NEXT: H[[X]]o");
+  EXPECT_TRUE(result) << result.message();
+}
+
+TEST(Match, VarDefFollowedByUseFail) {
+  const auto result =
+      Match("Hello\n\nWorld", "CHECK: H[[X:[a-z]+]]o\nCHECK: H[[X]]o");
+  EXPECT_FALSE(result) << result.message();
+  EXPECT_THAT(result.message(),
+              HasSubstr(":2:8: error: expected string not found in input"));
+  EXPECT_THAT(result.message(),
+              HasSubstr("note: with variable \"X\" equal to \"ell\""));
+}
+
+TEST(Match, VarDefFollowedByUseFailAfterDAG) {
+  const auto result =
+      Match("Hello\nWorld",
+            "CHECK: H[[X:[a-z]+]]o\nCHECK-DAG: box[[X]]\nCHECK: H[[X]]o");
+  EXPECT_FALSE(result) << result.message();
+  EXPECT_THAT(result.message(),
+              HasSubstr(":2:12: error: expected string not found in input"));
+  EXPECT_THAT(result.message(),
+              HasSubstr("note: with variable \"X\" equal to \"ell\""));
+}
+
+TEST(Match, VarDefFollowedByUseInNotCheck) {
+  const auto result =
+      Match("Hello\nHello", "CHECK: H[[X:[a-z]+]]o\nCHECK-NOT: H[[X]]o");
+  EXPECT_FALSE(result) << result.message();
+  EXPECT_THAT(result.message(), HasSubstr("CHECK-NOT: string occurred"));
+  EXPECT_THAT(result.message(),
+              HasSubstr("note: with variable \"X\" equal to \"ell\""));
+}
+
+TEST(Match, VarDefFollowedByUseInNextCheckRightLine) {
+  const auto result =
+      Match("Hello\nHello", "CHECK: H[[X:[a-z]+]]o\nCHECK-NEXT: Blad[[X]]");
+  EXPECT_FALSE(result) << result.message();
+  EXPECT_THAT(result.message(),
+              HasSubstr(":2:13: error: expected string not found in input"));
+  EXPECT_THAT(result.message(),
+              HasSubstr("note: with variable \"X\" equal to \"ell\""));
+}
+
+TEST(Match, VarDefFollowedByUseInNextCheckBadLine) {
+  const auto result =
+      Match("Hello\n\nHello", "CHECK: H[[X:[a-z]+]]o\nCHECK-NEXT: H[[X]]o");
+  EXPECT_FALSE(result) << result.message();
+  EXPECT_THAT(result.message(),
+              HasSubstr(":2:13: error: CHECK-NEXT: is not on the line after"));
+  EXPECT_THAT(result.message(),
+              HasSubstr("note: with variable \"X\" equal to \"ell\""));
+}
+
+TEST(Match, UndefinedVarNeverMatches) {
+  const auto result = Match("Hello HeXllo", "CHECK: He[[X]]llo");
+  EXPECT_FALSE(result) << result.message();
+  EXPECT_THAT(result.message(),
+              HasSubstr("note: uses undefined variable \"X\""));
+}
+
+TEST(Match, NoteSeveralUndefinedVariables) {
+  const auto result = Match("Hello HeXllo", "CHECK: He[[X]]l[[YZ]]lo[[Q]]");
+  EXPECT_FALSE(result) << result.message();
+  const char* substr = R"(
+<stdin>:1:1: note: uses undefined variable "X"
+Hello HeXllo
+^
+<stdin>:1:1: note: uses undefined variable "YZ"
+Hello HeXllo
+^
+<stdin>:1:1: note: uses undefined variable "Q"
+Hello HeXllo
+^
+)";
+  EXPECT_THAT(result.message(), HasSubstr(substr));
+}
+
+TEST(Match, OutOfOrderDefAndUseViaDAGChecks) {
+  // In this example the X variable should be set to 'l', and then match
+  // the earlier occurrence in 'Hello'.
+  const auto result = Match(
+      "Hello\nWorld", "CHECK-DAG: Wor[[X:[a-z]+]]d\nCHECK-DAG: He[[X]]lo");
+  EXPECT_FALSE(result) << result.message();
+}
+
+TEST(Match, VarDefRegexCountsParenthesesProperlyPass) {
+  const auto result = Match(
+      "FirstabababSecondcdcd\n1ababab2cdcd",
+      "CHECK: First[[X:(ab)+]]Second[[Y:(cd)+]]\nCHECK: 1[[X]]2[[Y]]");
+  EXPECT_TRUE(result) << result.message();
+}
+
+TEST(Match, VarDefRegexCountsParenthesesProperlyFail) {
+  const auto result =
+      Match("Firstababab1abab", "CHECK: First[[X:(ab)+]]\nCHECK: 1[[X]]");
+  EXPECT_FALSE(result) << result.message();
+  const char* substr = R"(<stdin>:2:8: error: expected string not found in input
+CHECK: 1[[X]]
+       ^
+<stdin>:1:12: note: scanning from here
+Firstababab1abab
+           ^
+<stdin>:1:12: note: with variable "X" equal to "ababab"
+Firstababab1abab
+           ^
+)";
+  EXPECT_THAT(result.message(), HasSubstr(substr));
+}
+
+}  // namespace
diff --git a/effcee/options_test.cc b/effcee/options_test.cc
new file mode 100644
index 0000000..efbb94b
--- /dev/null
+++ b/effcee/options_test.cc
@@ -0,0 +1,143 @@
+// Copyright 2017 The Effcee Authors.
+//
+// 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.
+
+#include "gmock/gmock.h"
+
+#include "effcee.h"
+
+namespace {
+
+using effcee::Options;
+using ::testing::Eq;
+using ::testing::Not;
+
+// Options class
+
+// Prefix property
+
+TEST(Options, DefaultPrefixIsCHECK) {
+  EXPECT_THAT(Options().prefix(), "CHECK");
+}
+
+TEST(Options, SetPrefixReturnsSelf) {
+  Options options;
+  const Options& other = options.SetPrefix("");
+  EXPECT_THAT(&other, &options);
+}
+
+TEST(Options, SetPrefixOnceSetsPrefix) {
+  Options options;
+  options.SetPrefix("foo");
+  EXPECT_THAT(options.prefix(), Eq("foo"));
+}
+
+TEST(Options, SetPrefixCopiesString) {
+  Options options;
+  std::string original("foo");
+  options.SetPrefix(original);
+  EXPECT_THAT(options.prefix().data(), Not(Eq(original.data())));
+}
+
+TEST(Options, SetPrefixEmptyStringPossible) {
+  Options options;
+  // This is not useful.
+  options.SetPrefix("");
+  EXPECT_THAT(options.prefix(), Eq(""));
+}
+
+TEST(Options, SetPrefixTwiceRetainsLastPrefix) {
+  Options options;
+  options.SetPrefix("foo");
+  options.SetPrefix("bar baz");
+  EXPECT_THAT(options.prefix(), Eq("bar baz"));
+}
+
+
+// Input name property
+
+TEST(Options, DefaultInputNameIsStdin) {
+  EXPECT_THAT(Options().input_name(), "<stdin>");
+}
+
+TEST(Options, SetInputNameReturnsSelf) {
+  Options options;
+  const Options& other = options.SetInputName("");
+  EXPECT_THAT(&other, &options);
+}
+
+TEST(Options, SetInputNameOnceSetsInputName) {
+  Options options;
+  options.SetInputName("foo");
+  EXPECT_THAT(options.input_name(), Eq("foo"));
+}
+
+TEST(Options, SetInputNameCopiesString) {
+  Options options;
+  std::string original("foo");
+  options.SetInputName(original);
+  EXPECT_THAT(options.input_name().data(), Not(Eq(original.data())));
+}
+
+TEST(Options, SetInputNameEmptyStringPossible) {
+  Options options;
+  options.SetInputName("");
+  EXPECT_THAT(options.input_name(), Eq(""));
+}
+
+TEST(Options, SetInputNameTwiceRetainsLastInputName) {
+  Options options;
+  options.SetInputName("foo");
+  options.SetInputName("bar baz");
+  EXPECT_THAT(options.input_name(), Eq("bar baz"));
+}
+
+// Checks name property
+
+TEST(Options, DefaultChecksNameIsStdin) {
+  EXPECT_THAT(Options().checks_name(), "<stdin>");
+}
+
+TEST(Options, SetChecksNameReturnsSelf) {
+  Options options;
+  const Options& other = options.SetChecksName("");
+  EXPECT_THAT(&other, &options);
+}
+
+TEST(Options, SetChecksNameOnceSetsChecksName) {
+  Options options;
+  options.SetChecksName("foo");
+  EXPECT_THAT(options.checks_name(), Eq("foo"));
+}
+
+TEST(Options, SetChecksNameCopiesString) {
+  Options options;
+  std::string original("foo");
+  options.SetChecksName(original);
+  EXPECT_THAT(options.checks_name().data(), Not(Eq(original.data())));
+}
+
+TEST(Options, SetChecksNameEmptyStringPossible) {
+  Options options;
+  options.SetChecksName("");
+  EXPECT_THAT(options.checks_name(), Eq(""));
+}
+
+TEST(Options, SetChecksNameTwiceRetainsLastChecksName) {
+  Options options;
+  options.SetChecksName("foo");
+  options.SetChecksName("bar baz");
+  EXPECT_THAT(options.checks_name(), Eq("bar baz"));
+}
+
+}  // namespace
diff --git a/effcee/result_test.cc b/effcee/result_test.cc
new file mode 100644
index 0000000..32cb741
--- /dev/null
+++ b/effcee/result_test.cc
@@ -0,0 +1,130 @@
+// Copyright 2017 The Effcee Authors.
+//
+// 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.
+
+#include <vector>
+#include "gmock/gmock.h"
+
+#include "effcee.h"
+
+namespace {
+
+using effcee::Result;
+using ::testing::Combine;
+using ::testing::Eq;
+using ::testing::Not;
+using ::testing::ValuesIn;
+
+using Status = effcee::Result::Status;
+
+// Result class
+
+// Returns a vector of all failure status values.
+std::vector<Status> AllFailStatusValues() {
+  return {Status::NoRules, Status::BadRule};
+}
+
+// Returns a vector of all status values.
+std::vector<Status> AllStatusValues() {
+  auto result = AllFailStatusValues();
+  result.push_back(Status::Ok);
+  return result;
+}
+
+// Test one-argument constructor.
+
+using ResultStatusTest = ::testing::TestWithParam<Status>;
+
+TEST_P(ResultStatusTest, ConstructWithAnyStatus) {
+  Result result(GetParam());
+  EXPECT_THAT(result.status(), Eq(GetParam()));
+}
+
+INSTANTIATE_TEST_SUITE_P(AllStatus, ResultStatusTest,
+                         ValuesIn(AllStatusValues()));
+
+// Test two-argument constructor.
+
+using ResultStatusMessageCase = std::tuple<Status, std::string>;
+
+using ResultStatusMessageTest =
+    ::testing::TestWithParam<ResultStatusMessageCase>;
+
+TEST_P(ResultStatusMessageTest, ConstructWithStatusAndMessage) {
+  Result result(std::get<0>(GetParam()), std::get<1>(GetParam()));
+  EXPECT_THAT(result.status(), Eq(std::get<0>(GetParam())));
+  EXPECT_THAT(result.message(), Eq(std::get<1>(GetParam())));
+}
+
+INSTANTIATE_TEST_SUITE_P(SampleStatusAndMessage, ResultStatusMessageTest,
+                         Combine(ValuesIn(AllStatusValues()),
+                                 ValuesIn(std::vector<std::string>{
+                                     "", "foo bar", "and, how!\n"})));
+
+TEST(ResultConversionTest, OkStatusConvertsToTrue) {
+  Result result(Status::Ok);
+  bool as_bool = result;
+  EXPECT_THAT(as_bool, Eq(true));
+}
+
+// Test conversion to bool.
+
+using ResultFailConversionTest = ::testing::TestWithParam<Status>;
+
+TEST_P(ResultFailConversionTest, AnyFailStatusConvertsToFalse) {
+  Result result(GetParam());
+  bool as_bool = result;
+  EXPECT_THAT(as_bool, Eq(false));
+}
+
+INSTANTIATE_TEST_SUITE_P(FailStatus, ResultFailConversionTest,
+                         ValuesIn(AllFailStatusValues()));
+
+TEST(ResultMessage, SetMessageReturnsSelf) {
+  Result result(Status::Ok);
+  Result& other = result.SetMessage("");
+  EXPECT_THAT(&other, Eq(&result));
+}
+
+TEST(ResultMessage, MessageDefaultsToEmpty) {
+  Result result(Status::Ok);
+  EXPECT_THAT(result.message(), Eq(""));
+}
+
+TEST(ResultMessage, SetMessageOnceSetsMessage) {
+  Result result(Status::Ok);
+  result.SetMessage("foo");
+  EXPECT_THAT(result.message(), Eq("foo"));
+}
+
+TEST(ResultMessage, SetMessageCopiesString) {
+  Result result(Status::Ok);
+  std::string original("foo");
+  result.SetMessage(original);
+  EXPECT_THAT(result.message().data(), Not(Eq(original.data())));
+}
+
+TEST(ResultMessage, SetMessageEmtpyStringPossible) {
+  Result result(Status::Ok);
+  result.SetMessage("");
+  EXPECT_THAT(result.message(), Eq(""));
+}
+
+TEST(ResultMessage, SetMessageTwiceRetainsLastMessage) {
+  Result result(Status::Ok);
+  result.SetMessage("foo");
+  result.SetMessage("bar baz");
+  EXPECT_THAT(result.message(), Eq("bar baz"));
+}
+
+}  // namespace
diff --git a/effcee/to_string.h b/effcee/to_string.h
new file mode 100644
index 0000000..b2ccc4f
--- /dev/null
+++ b/effcee/to_string.h
@@ -0,0 +1,29 @@
+// Copyright 2018 The Effcee Authors.
+//
+// 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.
+
+#ifndef EFFCEE_TO_STRING_H
+#define EFFCEE_TO_STRING_H
+
+#include <string>
+#include "effcee.h"
+
+namespace effcee {
+
+// Returns a copy of a StringPiece, as a std::string.
+inline std::string ToString(effcee::StringPiece s) {
+  return std::string(s.data(), s.size());
+}
+}  // namespace effcee
+
+#endif
diff --git a/examples/CMakeLists.txt b/examples/CMakeLists.txt
new file mode 100644
index 0000000..32cdd29
--- /dev/null
+++ b/examples/CMakeLists.txt
@@ -0,0 +1,26 @@
+add_executable(effcee-example main.cc)
+
+target_link_libraries(effcee-example effcee)
+if(UNIX AND NOT MINGW)
+  set_target_properties(effcee-example PROPERTIES LINK_FLAGS -pthread)
+endif()
+if (WIN32 AND NOT MSVC)
+  # For MinGW cross-compile, statically link to the C++ runtime
+  set_target_properties(effcee-example PROPERTIES
+	  LINK_FLAGS "-static -static-libgcc -static-libstdc++")
+endif(WIN32 AND NOT MSVC)
+
+
+if(EFFCEE_BUILD_TESTING)
+  add_test(NAME effcee-example
+          COMMAND ${PYTHON_EXE}
+                  effcee-example-driver.py
+                  $<TARGET_FILE:effcee-example>
+                  example_data.txt
+                  "CHECK: Hello"
+                  "CHECK-SAME: world"
+                  "CHECK-NEXT: Bees"
+                  "CHECK-NOT: Sting"
+                  "CHECK: Honey"
+          WORKING_DIRECTORY ${CMAKE_CURRENT_SOURCE_DIR})
+endif(EFFCEE_BUILD_TESTING)
diff --git a/examples/effcee-example-driver.py b/examples/effcee-example-driver.py
new file mode 100644
index 0000000..e1b0eff
--- /dev/null
+++ b/examples/effcee-example-driver.py
@@ -0,0 +1,42 @@
+#!/usr/bin/env python
+
+# Copyright 2017 The Effcee Authors.
+#
+# 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.
+
+"""Execute the effcee-example program, where the arguments are
+the location of the example program, the input file, and a
+list of check rules to match against the input.
+
+Args:
+    effcee-example:   Path to the effcee-example executable
+    input_file:       Data file containing the input to match
+    check1 .. checkN: Check rules to match
+"""
+
+import subprocess
+import sys
+
+def main():
+    cmd = sys.argv[1]
+    input_file = sys.argv[2]
+    checks = sys.argv[3:]
+    args = [cmd]
+    args.extend(checks)
+    print(args)
+    with open(input_file) as input_stream:
+        sys.exit(subprocess.call(args, stdin=input_stream))
+    sys.exit(1)
+
+if __name__ == '__main__':
+    main()
diff --git a/examples/example_data.txt b/examples/example_data.txt
new file mode 100644
index 0000000..f702057
--- /dev/null
+++ b/examples/example_data.txt
@@ -0,0 +1,4 @@
+Hello world
+Bees
+Make
+Delicious Honey
diff --git a/examples/main.cc b/examples/main.cc
new file mode 100644
index 0000000..ea0a343
--- /dev/null
+++ b/examples/main.cc
@@ -0,0 +1,64 @@
+// Copyright 2017 The Effcee Authors.
+//
+// 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.
+
+#include <iostream>
+#include <sstream>
+
+#include "effcee/effcee.h"
+
+// Checks standard input against the list of checks provided as command line
+// arguments.
+//
+// Example:
+//    cat <<EOF >sample_data.txt
+//    Bees
+//    Make
+//    Delicious Honey
+//    EOF
+//    effcee-example <sample_data.txt "CHECK: Bees" "CHECK-NOT:Sting" "CHECK: Honey"
+int main(int argc, char* argv[]) {
+  // Read the command arguments as a list of check rules.
+  std::ostringstream checks_stream;
+  for (int i = 1; i < argc; ++i) {
+    checks_stream << argv[i] << "\n";
+  }
+  // Read stdin as the input to match.
+  std::stringstream input_stream;
+  std::cin >> input_stream.rdbuf();
+
+  // Attempt to match.  The input and checks arguments can be provided as
+  // std::string or pointer to char.
+  auto result = effcee::Match(input_stream.str(), checks_stream.str(),
+                              effcee::Options().SetChecksName("checks"));
+
+  // Successful match result converts to true.
+  if (result) {
+    std::cout << "The input matched your check list!" << std::endl;
+  } else {
+    // Otherwise, you can get a status code and a detailed message.
+    switch (result.status()) {
+      case effcee::Result::Status::NoRules:
+        std::cout << "error: Expected check rules as command line arguments\n";
+        break;
+      case effcee::Result::Status::Fail:
+        std::cout << "The input failed to match your check rules:\n";
+        break;
+      default:
+        break;
+    }
+    std::cout << result.message() << std::endl;
+    return 1;
+  }
+  return 0;
+}
diff --git a/third_party/CMakeLists.txt b/third_party/CMakeLists.txt
new file mode 100644
index 0000000..9ef4a22
--- /dev/null
+++ b/third_party/CMakeLists.txt
@@ -0,0 +1,44 @@
+# Suppress all warnings from third-party projects.
+set_property(DIRECTORY APPEND PROPERTY COMPILE_OPTIONS -w)
+
+# Set alternate root directory for third party sources.
+set(EFFCEE_THIRD_PARTY_ROOT_DIR "${CMAKE_CURRENT_SOURCE_DIR}" CACHE STRING
+  "Root location of all third_party projects")
+
+# Find googletest and gmock
+if(${googletest-distribution_SOURCE_DIR})
+  set(EFFCEE_GOOGLETEST_DIR "${googletest-distribution_SOURCE_DIR}" CACHE STRING
+	  "Location of googletest source")
+else()
+  set(EFFCEE_GOOGLETEST_DIR "${EFFCEE_THIRD_PARTY_ROOT_DIR}/googletest" CACHE STRING
+          "Location of googletest source")
+endif()
+
+# Find re2
+if(RE2_SOURCE_DIR)
+  set(EFFCEE_RE2_DIR "${RE2_SOURCE_DIR}" CACHE STRING "Location of re2 source" FORCE)
+else()
+  set(EFFCEE_RE2_DIR "${EFFCEE_THIRD_PARTY_ROOT_DIR}/re2" CACHE STRING
+    "Location of re2 source")
+endif()
+
+# Configure third party projects.
+if(EFFCEE_BUILD_TESTING)
+  if (NOT TARGET gmock)
+    if (IS_DIRECTORY ${EFFCEE_GOOGLETEST_DIR})
+      add_subdirectory(${EFFCEE_GOOGLETEST_DIR} googletest EXCLUDE_FROM_ALL)
+    endif()
+  endif()
+  if (NOT TARGET gmock)
+    message(FATAL_ERROR "gmock was not found - required for tests")
+  endif()
+endif()
+
+if (NOT TARGET re2)
+  if (IS_DIRECTORY ${EFFCEE_RE2_DIR})
+    add_subdirectory(${EFFCEE_RE2_DIR} re2 EXCLUDE_FROM_ALL)
+  endif()
+endif()
+if (NOT TARGET re2)
+  message(FATAL_ERROR "re2 was not found - required for compilation")
+endif()