[LibTooling] Add NodeId, a strong type for AST-matcher node identifiers.

[ymandel]

Summary

The standard matcher API uses StringRefs to identify bound nodes. This patch
introduces a strong type thats allows distinguishing ids from arbitrary text in
APIs. It additionally adds a templated version which can indicate the AST type
to which the id is bound.

This patch is the second in a series intended to improve the abstractions
available to users for writing source-to-source transformations. A full
discussion of the end goal can be found on the cfe-dev list with subject "[RFC]
Easier source-to-source transformations with clang tooling".

[ymandel]

This comment was removed by ymandel.

[ymandel]

"Revert" to original diff. This undoes the previous diff, which associated with the wrong revision.

[ymandel]

gentle ping...

[ilya-biryukov]

clang/include/clang/Tooling/Refactoring/NodeId.h

30

What are the use-cases for passing a custom id to this class?
If the purpose is to hide the IDs from the user, exposing this constructor seems to be against this goal.

clang/lib/Tooling/Refactoring/NodeId.cpp

13

NIT: change to using namespace for consistency

25

Suggestion from @klimek :

could we get the unique string by printing a pointer of this instead?
(And disallow copies and moves of this class for this to be correct)

[ilya-biryukov]

Could you provide the rationale for having NodeID vs just using strings for the binds?
Is this just a more type-safe way to do the same thing or is that actually required to solve a particular problem?

[ymandel]

clang/include/clang/Tooling/Refactoring/NodeId.h

30

If there are errors relating to the id (say, referencing it in a stencil when it wasn't bound in the match), the errors are hard to understand when the id is auto-generated. In general, I'd say that best practice is to explicitly specify the id so that dynamic failures print a meaningful id. The default constructor is a compromise and perhaps shouldn't be exported.

that said, if we could find another way to give good error messages (for example, if we could somehow grab the line number of the declaration), then the default construction would be the preferred approach.

clang/include/clang/Tooling/Refactoring/NodeId.h

+//===--- NodeId.h - NodeId class ------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+///
+/// \file This file defines abstractions for the bound identifiers used in AST
+/// matchers.
+///
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_TOOLING_REFACTOR_NODE_ID_H_
+#define LLVM_CLANG_TOOLING_REFACTOR_NODE_ID_H_
+
+#include "clang/ASTMatchers/ASTMatchFinder.h"
+#include "llvm/ADT/StringRef.h"
+#include <string>
+
+namespace clang {
+namespace tooling {
+
+/// A strong type for AST node identifiers.  The standard API uses StringRefs
+/// for identifiers.  The strong type allows us to distinguish ids from
+/// arbitrary text snippets in various APIs.
+class NodeId {
+public:
+  explicit NodeId(std::string Id) : Id(std::move(Id)) {}
+
+  /// Creates a NodeId whose name is based on \p Id. Guarantees that unique ids
+  /// map to unique NodeIds.
+  explicit NodeId(size_t Id) : Id("id" + std::to_string(Id)) {}
+
+  /// Creates a NodeId with a generated name. The name is guaranteed to be
+  /// unique with respect to other generated names.
+  NodeId();
+
+  llvm::StringRef id() const { return Id; }
+
+  /// Gets the AST node in \p Result corresponding to this NodeId, if
+  /// any. Otherwise, returns null.
+  template <typename Node>
+  const Node *
+  getNodeAs(const ast_matchers::MatchFinder::MatchResult &Result) const {
+    return Result.Nodes.getNodeAs<Node>(Id);
+  }
+
+private:
+  std::string Id;
+};
+
+/// Refinement of NodeId that identifies the intended node type for the id. This
+/// additional information allows us to select appropriate overloads or
+/// constrain use of various combinators. It also allows us to distinguish when
+/// a \c Expr node is intended as a \c Stmt, which influences the intended
+/// source range for the node.  \p Node is the AST node type corresponding to
+/// this id.
+template <typename Node> class TypedNodeId : public NodeId {
+public:
+  using NodeId::NodeId;
+  using MatcherType = ast_matchers::internal::Matcher<Node>;
+
+  /// Creates a matcher corresponding to the AST-node type of this id and bound
+  /// to this id. Intended for settings where the type of matcher is
+  /// obvious/uninteresting. For example,
+  ///
+  ///   ExprId Arg;
+  ///   auto Matcher = callExpr(callee(isFunctionNamed("foo")),
+  ///                           hasArgument(0, Arg.bind()));
+  MatcherType bind() const {
+    return ast_matchers::internal::BindableMatcher<Node>(
+               ast_matchers::internal::TrueMatcher())
+        .bind(id());
+  }
+};
+
+using ExprId = TypedNodeId<Expr>;
+using StmtId = TypedNodeId<Stmt>;
+using DeclId = TypedNodeId<Decl>;
+using TypeId = TypedNodeId<Type>;
+
+} // namespace tooling
+} // namespace clang
+#endif // LLVM_CLANG_TOOLING_REFACTOR_NODE_ID_H_

clang/include/clang/Tooling/Refactoring/Stencil.h

+//===--- Stencil.h - Stencil class ------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+///
+/// /file
+/// This file defines the *Stencil* abstraction: a code-generating object,
+/// parameterized by named references to (bound) AST nodes.  Given a match
+/// result, a stencil can be evaluated to a string of source code.
+///
+/// A stencil is similar in spirit to a format string: it is composed of a
+/// series of raw text strings, references to nodes (the parameters) and helper
+/// code-generation operations.
+///
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_TOOLING_REFACTOR_STENCIL_H_
+#define LLVM_CLANG_TOOLING_REFACTOR_STENCIL_H_
+
+#include "NodeId.h"
+#include "clang/AST/ASTContext.h"
+#include "clang/AST/ASTTypeTraits.h"
+#include "clang/ASTMatchers/ASTMatchFinder.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/Support/Error.h"
+#include <string>
+#include <vector>
+
+namespace clang {
+namespace tooling {
+
+/// A stencil is represented as a sequence of "parts" that can each individually
+/// generate a code string based on a match result.  The different kinds of
+/// parts include (raw) text, references to bound nodes and assorted operations
+/// on bound nodes.
+///
+/// Users can create custom Stencil operations by implementing this interface.
+class StencilPartInterface {
+public:
+  virtual ~StencilPartInterface() = default;
+
+  /// Evaluates this part to a string and appends it to `result`.
+  virtual llvm::Error eval(const ast_matchers::MatchFinder::MatchResult &Match,
+                           std::string *Result) const = 0;
+
+  virtual std::unique_ptr<StencilPartInterface> clone() const = 0;
+
+  virtual bool isEqual(const StencilPartInterface &other) const = 0;
+
+  const void *typeId() const { return TypeId; }
+
+protected:
+  StencilPartInterface(const void *DerivedId) : TypeId(DerivedId) {}
+
+  // Since this is an abstract class, copying/assigning only make sense for
+  // derived classes implementing `clone()`.
+  StencilPartInterface(const StencilPartInterface &) = default;
+  StencilPartInterface &operator=(const StencilPartInterface &) = default;
+
+  /// Unique identifier of the concrete type of this instance.  Supports safe
+  /// downcasting.
+  const void *TypeId;
+};
+
+/// A copyable facade for a std::unique_ptr<StencilPartInterface>. Copies result
+/// in a copy of the underlying pointee object.
+class StencilPart {
+public:
+  explicit StencilPart(std::unique_ptr<StencilPartInterface> Impl)
+      : Impl(std::move(Impl)) {}
+
+  // Copy constructor/assignment produce a deep copy.
+  StencilPart(const StencilPart &P) : Impl(P.Impl->clone()) {}
+  StencilPart(StencilPart &&) = default;
+  StencilPart &operator=(const StencilPart &P) {
+    Impl = P.Impl->clone();
+    return *this;
+  }
+  StencilPart &operator=(StencilPart &&) = default;
+
+  /// See `StencilPartInterface::eval()`.
+  llvm::Error eval(const ast_matchers::MatchFinder::MatchResult &Match,
+                   std::string *Result) const {
+    return Impl->eval(Match, Result);
+  }
+
+  bool operator==(const StencilPart &Other) const {
+    if (Impl == Other.Impl)
+      return true;
+    if (Impl == nullptr || Other.Impl == nullptr)
+      return false;
+    return Impl->isEqual(*(Other.Impl));
+  }
+
+private:
+  std::unique_ptr<StencilPartInterface> Impl;
+};
+
+/// A sequence of code fragments, references to parameters and code-generation
+/// operations that together can be evaluated to (a fragment of) source code,
+/// given a match result.
+class Stencil {
+public:
+  Stencil() = default;
+
+  Stencil(const Stencil &) = default;
+  Stencil(Stencil &&) = default;
+  Stencil &operator=(const Stencil &) = default;
+  Stencil &operator=(Stencil &&) = default;
+
+  /// Composes a stencil from a series of parts.
+  template <typename... Ts> static Stencil cat(Ts &&... Parts) {
+    Stencil Stencil;
+    Stencil.Parts.reserve(sizeof...(Parts));
+    auto Unused = {(Stencil.push(std::forward<Ts>(Parts)), true)...};
+    (void)Unused;
+    return Stencil;
+  }
+
+  /// Appends data from a \p OtherStencil to this stencil.
+  void append(Stencil OtherStencil);
+
+  // Evaluates the stencil given a match result. Requires that the nodes in the
+  // result includes any ids referenced in the stencil. References to missing
+  // nodes will result in an invalid_argument error.
+  llvm::Expected<std::string>
+  eval(const ast_matchers::MatchFinder::MatchResult &Match) const;
+
+  bool operator==(const Stencil &Other) const {
+    return Parts == Other.Parts;
+  }
+
+  bool operator!=(const Stencil &Other) const { return !(*this == Other); }
+
+private:
+  void push(const NodeId &Id);
+  void push(const ExprId &Id);
+  void push(llvm::StringRef Text);
+  void push(StencilPart Part) { Parts.push_back(std::move(Part)); }
+
+  std::vector<StencilPart> Parts;
+};
+
+// Functions for conveniently building stencil parts.
+namespace stencil_generators {
+/// Abbreviation for NodeId construction allowing for more concise references to
+/// node ids in stencils.
+inline NodeId id(llvm::StringRef Id) { return NodeId(Id); }
+
+/// \returns exactly the text provided.
+StencilPart text(llvm::StringRef Text);
+
+/// \returns the source corresponding to the identified node.
+StencilPart node(const NodeId &Id);
+/// Specialization for expressions to indicate that the node should be
+/// interepreted as an expression, as opposed to a statement.
+StencilPart node(const ExprId &Id);
+StencilPart node(llvm::StringRef Id);
+
+/// For debug use only; semantics are not guaranteed.
+///
+/// \returns the string resulting from calling the node's print() method.
+StencilPart dPrint(const NodeId &Id);
+StencilPart dPrint(llvm::StringRef Id);
+} // namespace stencil_generators
+} // namespace tooling
+} // namespace clang
+#endif // LLVM_CLANG_TOOLING_REFACTOR_STENCIL_H_

clang/lib/Tooling/Refactoring/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS Support)
 
 add_clang_library(clangToolingRefactor
   ASTSelection.cpp
   ASTSelectionRequirements.cpp
   AtomicChange.cpp
   Extract/Extract.cpp
   Extract/SourceExtraction.cpp
   RefactoringActions.cpp
   Rename/RenamingAction.cpp
   Rename/SymbolOccurrences.cpp
   Rename/USRFinder.cpp
   Rename/USRFindingAction.cpp
   Rename/USRLocFinder.cpp
+  NodeId.cpp
+  Stencil.cpp
 
   LINK_LIBS
   clangAST
   clangASTMatchers
   clangBasic
   clangFormat
   clangIndex
   clangLex
   clangRewrite
   clangToolingCore
   )

clang/lib/Tooling/Refactoring/NodeId.cpp

+//===--- NodeId.cpp - NodeId implementation ---------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/Tooling/Refactoring/NodeId.h"
+#include <atomic>
+
+namespace clang {
+namespace tooling {
+
+// For guaranteeing unique ids on NodeId creation.
+static size_t nextId() {
+  // Start with a relatively high number to avoid bugs if the user mixes
+  // explicitly-numbered ids with those generated with `NextId()`. Similarly, we
+  // choose a number that allows generated ids to be easily recognized.
+  static std::atomic<size_t> Next(2222);
+  return Next.fetch_add(1, std::memory_order_relaxed);
+}
+
+NodeId::NodeId() : NodeId(nextId()) {}
+
+} // namespace tooling
+} // namespace clang

clang/lib/Tooling/Refactoring/Stencil.cpp

+//===--- Stencil.cpp - Stencil implementation -------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/Tooling/Refactoring/Stencil.h"
+#include "clang/AST/ASTContext.h"
+#include "clang/AST/ASTTypeTraits.h"
+#include "clang/AST/Expr.h"
+#include "clang/ASTMatchers/ASTMatchFinder.h"
+#include "clang/ASTMatchers/ASTMatchers.h"
+#include "clang/Lex/Lexer.h"
+#include "clang/Tooling/FixIt.h"
+#include "llvm/Support/Errc.h"
+#include <atomic>
+#include <string>
+
+namespace clang {
+namespace tooling {
+
+// A down_cast function to safely down cast a StencilPartInterface to a subclass
+// D. Returns nullptr if P is not an instance of D.
+template <typename D> const D *down_cast(const StencilPartInterface *P) {
+  if (P == nullptr || D::typeId() != P->typeId())
+    return nullptr;
+  return static_cast<const D *>(P);
+}
+
+static llvm::Expected<ast_type_traits::DynTypedNode>
+getNode(const ast_matchers::BoundNodes &Nodes, StringRef Id) {
+  auto &NodesMap = Nodes.getMap();
+  auto It = NodesMap.find(Id);
+  if (It == NodesMap.end())
+    return llvm::make_error<llvm::StringError>(llvm::errc::invalid_argument,
+                                               "Id not bound: " + Id);
+  return It->second;
+}
+
+namespace {
+using ::clang::ast_matchers::MatchFinder;
+using ::llvm::Error;
+
+// An arbitrary fragment of code within a stencil.
+struct RawTextData {
+  explicit RawTextData(std::string T) : Text(std::move(T)) {}
+  std::string Text;
+};
+}
+
+static bool operator==(const RawTextData &A, const RawTextData &B) {
+  return A.Text == B.Text;
+}
+
+namespace {
+// A debugging operation to dump the AST for a particular (bound) AST node.
+struct DebugPrintNodeOpData {
+  explicit DebugPrintNodeOpData(std::string S) : Id(std::move(S)) {}
+  std::string Id;
+};
+} // namespace
+
+static bool operator==(const DebugPrintNodeOpData &A,
+                       const DebugPrintNodeOpData &B) {
+  return A.Id == B.Id;
+}
+
+namespace {
+// Whether to associate a trailing semicolon with a node when identifying it's
+// text.  This flag is needed for expressions (clang::Expr), because their role
+// is ambiguous when they are also complete statements.  When this flag is
+// `Always`, an expression node will be treated like a statement, and will
+// therefore be associated with any trailing semicolon.
+enum class SemiAssociation : bool {
+  Never,
+  AsAppropriate,
+};
+
+// A reference to a particular (bound) AST node.
+struct NodeRefData {
+  explicit NodeRefData(std::string S, SemiAssociation SA)
+      : Id(std::move(S)), SemiAssoc(SA) {}
+  std::string Id;
+  SemiAssociation SemiAssoc;
+};
+} // namespace
+
+static bool operator==(const NodeRefData &A, const NodeRefData &B) {
+  return A.Id == B.Id && A.SemiAssoc == B.SemiAssoc;
+}
+
+static Error evalData(const RawTextData &Data, const MatchFinder::MatchResult &,
+                      std::string *Result) {
+  Result->append(Data.Text);
+  return Error::success();
+}
+
+static Error evalData(const DebugPrintNodeOpData &Data,
+           const MatchFinder::MatchResult &Match, std::string *Result) {
+  std::string Output;
+  llvm::raw_string_ostream Os(Output);
+  auto NodeOrErr = getNode(Match.Nodes, Data.Id);
+  if (auto Err = NodeOrErr.takeError())
+    return Err;
+  NodeOrErr->print(Os, PrintingPolicy(Match.Context->getLangOpts()));
+  *Result += Os.str();
+  return Error::success();
+}
+
+static Error evalData(const NodeRefData &Data,
+                      const MatchFinder::MatchResult &Match,
+                      std::string *Result) {
+  auto NodeOrErr = getNode(Match.Nodes, Data.Id);
+  if (auto Err = NodeOrErr.takeError())
+    return Err;
+  auto& Node = *NodeOrErr;
+  switch (Data.SemiAssoc) {
+  case SemiAssociation::AsAppropriate:
+    *Result += Node.get<Stmt>() != nullptr
+                   ? fixit::getExtendedText(
+                         NodeOrErr.get(), tok::TokenKind::semi, *Match.Context)
+                   : fixit::getText(NodeOrErr.get(), *Match.Context);
+    break;
+  case SemiAssociation::Never:
+    *Result += fixit::getText(NodeOrErr.get(), *Match.Context);
+    break;
+  }
+  return Error::success();
+}
+
+namespace {
+template <typename T>
+class StencilPartImpl : public StencilPartInterface {
+ public:
+  template <typename... Ps>
+  explicit StencilPartImpl(Ps &&... Args)
+      : StencilPartInterface(StencilPartImpl::typeId()),
+        Data(std::forward<Ps>(Args)...) {}
+
+  StencilPartImpl(const StencilPartImpl &) = default;
+  StencilPartImpl(StencilPartImpl &&) = default;
+  StencilPartImpl &operator=(const StencilPartImpl &) = default;
+  StencilPartImpl &operator=(StencilPartImpl &&) = default;
+
+  // Generates a unique identifier for this class (specifically, one per
+  // instantiation of the template).
+  static const void* typeId() {
+    static bool b;
+    return &b;
+  }
+
+  Error eval(const MatchFinder::MatchResult &Match,
+             std::string *Result) const override {
+    return evalData(Data, Match, Result);
+  }
+
+  std::unique_ptr<StencilPartInterface> clone() const override {
+    return llvm::make_unique<StencilPartImpl>(*this);
+  }
+
+  bool isEqual(const StencilPartInterface &Other) const override {
+    if (const auto *OtherPtr = down_cast<StencilPartImpl>(&Other))
+      return Data == OtherPtr->Data;
+    return false;
+  }
+
+ private:
+  T Data;
+};
+
+using RawText = StencilPartImpl<RawTextData>;
+using DebugPrintNodeOp = StencilPartImpl<DebugPrintNodeOpData>;
+using NodeRef = StencilPartImpl<NodeRefData>;
+} // namespace
+
+void Stencil::push(const NodeId &Id) {
+  Parts.emplace_back(stencil_generators::node(Id));
+}
+
+void Stencil::push(const ExprId &Id) {
+  Parts.emplace_back(stencil_generators::node(Id));
+}
+
+void Stencil::push(StringRef Text) {
+  Parts.emplace_back(llvm::make_unique<RawText>(Text));
+}
+
+void Stencil::append(Stencil OtherStencil) {
+  for (auto &Part : OtherStencil.Parts)
+    Parts.push_back(std::move(Part));
+}
+
+llvm::Expected<std::string>
+Stencil::eval(const MatchFinder::MatchResult &Match) const {
+  std::string Result;
+  for (const auto &Part : Parts)
+    if (auto Err = Part.eval(Match, &Result))
+      return std::move(Err);
+  return Result;
+}
+
+namespace stencil_generators {
+StencilPart text(StringRef Text) {
+  return StencilPart(llvm::make_unique<RawText>(Text));
+}
+
+StencilPart node(llvm::StringRef Id) {
+  return StencilPart(
+      llvm::make_unique<NodeRef>(Id, SemiAssociation::AsAppropriate));
+}
+StencilPart node(const NodeId &Id) { return node(Id.id()); }
+StencilPart node(const ExprId &Id) {
+  return StencilPart(
+      llvm::make_unique<NodeRef>(Id.id(), SemiAssociation::Never));
+}
+
+StencilPart dPrint(StringRef Id) {
+  return StencilPart(llvm::make_unique<DebugPrintNodeOp>(Id));
+}
+StencilPart dPrint(const NodeId &Id) { return dPrint(Id.id()); }
+} // namespace stencil_generators
+} // namespace tooling
+} // namespace clang

clang/unittests/Tooling/CMakeLists.txt

add_clang_unittest(ToolingTests
   RecursiveASTVisitorTestDeclVisitor.cpp
   RecursiveASTVisitorTestPostOrderVisitor.cpp
   RecursiveASTVisitorTestTypeLocVisitor.cpp
   RefactoringActionRulesTest.cpp
   RefactoringCallbacksTest.cpp
   RefactoringTest.cpp
   ReplacementsYamlTest.cpp
   RewriterTest.cpp
+  StencilTest.cpp
   ToolingTest.cpp
   )
 
 target_link_libraries(ToolingTests
   PRIVATE
   clangAST
   clangASTMatchers
   clangBasic

clang/unittests/Tooling/StencilTest.cpp

+//===- unittest/Tooling/StencilTest.cpp -----------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/Tooling/Refactoring/Stencil.h"
+#include "clang/ASTMatchers/ASTMatchers.h"
+#include "clang/Tooling/FixIt.h"
+#include "clang/Tooling/Tooling.h"
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+
+namespace clang {
+namespace tooling {
+namespace {
+
+using ::clang::ast_matchers::compoundStmt;
+using ::clang::ast_matchers::decl;
+using ::clang::ast_matchers::declStmt;
+using ::clang::ast_matchers::expr;
+using ::clang::ast_matchers::hasAnySubstatement;
+using ::clang::ast_matchers::hasCondition;
+using ::clang::ast_matchers::hasDescendant;
+using ::clang::ast_matchers::hasElse;
+using ::clang::ast_matchers::hasInitializer;
+using ::clang::ast_matchers::hasName;
+using ::clang::ast_matchers::hasReturnValue;
+using ::clang::ast_matchers::hasSingleDecl;
+using ::clang::ast_matchers::hasThen;
+using ::clang::ast_matchers::ifStmt;
+using ::clang::ast_matchers::ignoringImplicit;
+using ::clang::ast_matchers::returnStmt;
+using ::clang::ast_matchers::stmt;
+using ::clang::ast_matchers::varDecl;
+
+using MatchResult = ::clang::ast_matchers::MatchFinder::MatchResult;
+
+using ::clang::tooling::stencil_generators::node;
+using ::clang::tooling::stencil_generators::text;
+
+using ::testing::Eq;
+
+// In tests, we can't directly match on llvm::Expected since its accessors
+// mutate the object. So, we collapse it to an Optional.
+llvm::Optional<std::string> toOptional(llvm::Expected<std::string> V) {
+  if (V)
+    return *V;
+  ADD_FAILURE() << "Losing error in conversion to IsSomething: "
+                << llvm::toString(V.takeError());
+  return llvm::None;
+}
+
+// A very simple matcher for llvm::Optional values.
+MATCHER_P(IsSomething, ValueMatcher, "") {
+  if (!arg)
+    return false;
+  return ::testing::ExplainMatchResult(ValueMatcher, *arg, result_listener);
+}
+
+// Create a valid translation-unit from a statement.
+std::string wrapSnippet(llvm::Twine StatementCode) {
+  return ("auto stencil_test_snippet = []{" + StatementCode + "};").str();
+}
+
+clang::ast_matchers::DeclarationMatcher
+wrapMatcher(const clang::ast_matchers::StatementMatcher &Matcher) {
+  return varDecl(hasName("stencil_test_snippet"),
+                 hasDescendant(compoundStmt(hasAnySubstatement(Matcher))));
+}
+
+struct TestMatch {
+  // The AST unit from which `result` is built. We bundle it because it backs
+  // the result. Users are not expected to access it.
+  std::unique_ptr<clang::ASTUnit> AstUnit;
+  // The result to use in the test. References `ast_unit`.
+  MatchResult Result;
+};
+
+// Matches `Matcher` against the statement `StatementCode` and returns the
+// result. Handles putting the statement inside a function and modifying the
+// matcher correspondingly. `Matcher` should match `StatementCode` exactly --
+// that is, produce exactly one match.
+llvm::Optional<TestMatch>
+matchStmt(llvm::Twine StatementCode,
+          clang::ast_matchers::StatementMatcher Matcher) {
+  auto AstUnit = buildASTFromCode(wrapSnippet(StatementCode));
+  if (AstUnit == nullptr) {
+    ADD_FAILURE() << "AST construction failed";
+    return llvm::None;
+  }
+  clang::ASTContext &Context = AstUnit->getASTContext();
+  auto Matches = clang::ast_matchers::match(wrapMatcher(Matcher), Context);
+  // We expect a single, exact match for the statement.
+  if (Matches.size() != 1) {
+    ADD_FAILURE() << "Wrong number of matches: " << Matches.size();
+    return llvm::None;
+  }
+  return TestMatch{std::move(AstUnit), MatchResult(Matches[0], &Context)};
+}
+
+class StencilTest : public ::testing::Test {
+protected:
+  // Verifies that the given stencil fails when evaluated on a valid match
+  // result. Binds a statement to "stmt", a (non-member) ctor-initializer to
+  // "init", an expression to "expr" and a (nameless) declaration to "decl".
+  void testError(const Stencil &Stencil,
+                 testing::Matcher<std::string> Matcher) {
+    using ::clang::ast_matchers::cxxConstructExpr;
+    using ::clang::ast_matchers::cxxCtorInitializer;
+    using ::clang::ast_matchers::hasDeclaration;
+    using ::clang::ast_matchers::isBaseInitializer;
+
+    const std::string Snippet = R"cc(
+      struct A {};
+      class F : public A {
+       public:
+        F(int) {}
+      };
+      F(1);
+    )cc";
+    auto StmtMatch = matchStmt(
+        Snippet,
+        stmt(hasDescendant(
+                 cxxConstructExpr(
+                     hasDeclaration(decl(hasDescendant(cxxCtorInitializer(
+                                                           isBaseInitializer())
+                                                           .bind("init")))
+                                        .bind("decl")))
+                     .bind("expr")))
+            .bind("stmt"));
+    ASSERT_TRUE(StmtMatch);
+    if (auto ResultOrErr = Stencil.eval(StmtMatch->Result)) {
+      ADD_FAILURE() << "Expected failure but succeeded: " << *ResultOrErr;
+    } else {
+      auto Err = llvm::handleErrors(ResultOrErr.takeError(),
+                                    [&Matcher](const llvm::StringError &Err) {
+                                      EXPECT_THAT(Err.getMessage(), Matcher);
+                                    });
+      if (Err) {
+        ADD_FAILURE() << "Unhandled error: " << llvm::toString(std::move(Err));
+      }
+    }
+  }
+
+  // Tests failures caused by references to unbound nodes. `unbound_id` is the
+  // id that will cause the failure.
+  void testUnboundNodeError(const Stencil &Stencil, llvm::StringRef UnboundId) {
+    testError(Stencil, testing::AllOf(testing::HasSubstr(UnboundId),
+                                      testing::HasSubstr("not bound")));
+  }
+};
+
+TEST_F(StencilTest, SingleStatement) {
+  StmtId Condition("C"), Then("T"), Else("E");
+  const std::string Snippet = R"cc(
+    if (true)
+      return 1;
+    else
+      return 0;
+  )cc";
+  auto StmtMatch =
+      matchStmt(Snippet, ifStmt(hasCondition(Condition.bind()),
+                                hasThen(Then.bind()), hasElse(Else.bind())));
+  ASSERT_TRUE(StmtMatch);
+  // Invert the if-then-else.
+  auto Stencil =
+      Stencil::cat("if (!", Condition, ") ", Else, " else ", Then);
+  EXPECT_THAT(toOptional(Stencil.eval(StmtMatch->Result)),
+              IsSomething(Eq("if (!true) return 0; else return 1;")));
+}
+
+TEST_F(StencilTest, SingleStatementWithRawIds) {
+  using stencil_generators::id;
+
+  const std::string Snippet = R"cc(
+    if (true)
+      return 1;
+    else
+      return 0;
+  )cc";
+  auto StmtMatch = matchStmt(Snippet, ifStmt(hasCondition(stmt().bind("a1")),
+                                             hasThen(stmt().bind("a2")),
+                                             hasElse(stmt().bind("a3"))));
+  ASSERT_TRUE(StmtMatch);
+  auto Stencil =
+      Stencil::cat("if (!", id("a1"), ") ", id("a3"), " else ", id("a2"));
+  EXPECT_THAT(toOptional(Stencil.eval(StmtMatch->Result)),
+              IsSomething(Eq("if (!true) return 0; else return 1;")));
+}
+
+TEST_F(StencilTest, UnboundNode) {
+  using stencil_generators::id;
+
+  const std::string Snippet = R"cc(
+    if (true)
+      return 1;
+    else
+      return 0;
+  )cc";
+  auto StmtMatch = matchStmt(Snippet, ifStmt(hasCondition(stmt().bind("a1")),
+                                             hasThen(stmt().bind("a2"))));
+  ASSERT_TRUE(StmtMatch);
+  auto Stencil = Stencil::cat("if(!", id("a1"), ") ", id("UNBOUND"), ";");
+  auto ResultOrErr = Stencil.eval(StmtMatch->Result);
+  EXPECT_TRUE(llvm::errorToBool(ResultOrErr.takeError()))
+      << "Expected unbound node, got " << *ResultOrErr;
+}
+
+// Tests that a stencil with a single parameter (`Id`) evaluates to the expected
+// string, when `Id` is bound to the expression-statement in `Snippet`.
+void testExpr(const NodeId &Id, llvm::StringRef Snippet, const Stencil &Stencil,
+              llvm::StringRef Expected) {
+  auto StmtMatch = matchStmt(Snippet, expr().bind(Id.id()));
+  ASSERT_TRUE(StmtMatch);
+  EXPECT_THAT(toOptional(Stencil.eval(StmtMatch->Result)),
+              IsSomething(Expected));
+}
+
+TEST_F(StencilTest, NodeOp) {
+  NodeId Id("id");
+  ExprId EId("eid");
+  testExpr(Id, "3;", Stencil::cat(node(Id)), "3;");
+  testExpr(Id, "3;", Stencil::cat(node(Id.id())), "3;");
+  testExpr(EId, "3;", Stencil::cat(node(EId)), "3");
+}
+
+TEST(StencilEqualityTest, Equality) {
+  using stencil_generators::dPrint;
+  auto Lhs = Stencil::cat("foo", node("node"), dPrint("dprint_id"));
+  auto Rhs = Lhs;
+  EXPECT_EQ(Lhs, Rhs);
+}
+
+TEST(StencilEqualityTest, InEqualityDifferentOrdering) {
+  auto Lhs = Stencil::cat("foo", node("node"));
+  auto Rhs = Stencil::cat(node("node"), "foo");
+  EXPECT_NE(Lhs, Rhs);
+}
+
+TEST(StencilEqualityTest, InEqualityDifferentSizes) {
+  auto Lhs = Stencil::cat("foo", node("node"), "bar", "baz");
+  auto Rhs = Stencil::cat("foo", node("node"), "bar");
+  EXPECT_NE(Lhs, Rhs);
+}
+} // namespace
+} // namespace tooling
+} // namespace clang