contrib/llvm/tools/clang/lib/ASTMatchers/ASTMatchersInternal.cpp

   1 //===--- ASTMatchersInternal.cpp - Structural query framework -------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 //  Implements the base layer of the matcher framework.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "clang/ASTMatchers/ASTMatchers.h"
  15 #include "clang/ASTMatchers/ASTMatchersInternal.h"
  16 #include "llvm/ADT/SmallString.h"
  17 #include "llvm/Support/ManagedStatic.h"
  18
  19 namespace clang {
  20 namespace ast_matchers {
  21 namespace internal {
  22
  23 bool NotUnaryOperator(const ast_type_traits::DynTypedNode DynNode,
  24                       ASTMatchFinder *Finder, BoundNodesTreeBuilder *Builder,
  25                       ArrayRef<DynTypedMatcher> InnerMatchers);
  26
  27 bool AllOfVariadicOperator(const ast_type_traits::DynTypedNode DynNode,
  28                            ASTMatchFinder *Finder,
  29                            BoundNodesTreeBuilder *Builder,
  30                            ArrayRef<DynTypedMatcher> InnerMatchers);
  31
  32 bool EachOfVariadicOperator(const ast_type_traits::DynTypedNode DynNode,
  33                             ASTMatchFinder *Finder,
  34                             BoundNodesTreeBuilder *Builder,
  35                             ArrayRef<DynTypedMatcher> InnerMatchers);
  36
  37 bool AnyOfVariadicOperator(const ast_type_traits::DynTypedNode DynNode,
  38                            ASTMatchFinder *Finder,
  39                            BoundNodesTreeBuilder *Builder,
  40                            ArrayRef<DynTypedMatcher> InnerMatchers);
  41
  42
  43 void BoundNodesTreeBuilder::visitMatches(Visitor *ResultVisitor) {
  44   if (Bindings.empty())
  45     Bindings.push_back(BoundNodesMap());
  46   for (BoundNodesMap &Binding : Bindings) {
  47     ResultVisitor->visitMatch(BoundNodes(Binding));
  48   }
  49 }
  50
  51 namespace {
  52
  53 typedef bool (*VariadicOperatorFunction)(
  54     const ast_type_traits::DynTypedNode DynNode, ASTMatchFinder *Finder,
  55     BoundNodesTreeBuilder *Builder, ArrayRef<DynTypedMatcher> InnerMatchers);
  56
  57 template <VariadicOperatorFunction Func>
  58 class VariadicMatcher : public DynMatcherInterface {
  59 public:
  60   VariadicMatcher(std::vector<DynTypedMatcher> InnerMatchers)
  61       : InnerMatchers(std::move(InnerMatchers)) {}
  62
  63   bool dynMatches(const ast_type_traits::DynTypedNode &DynNode,
  64                   ASTMatchFinder *Finder,
  65                   BoundNodesTreeBuilder *Builder) const override {
  66     return Func(DynNode, Finder, Builder, InnerMatchers);
  67   }
  68
  69 private:
  70   std::vector<DynTypedMatcher> InnerMatchers;
  71 };
  72
  73 class IdDynMatcher : public DynMatcherInterface {
  74  public:
  75   IdDynMatcher(StringRef ID,
  76                const IntrusiveRefCntPtr<DynMatcherInterface> &InnerMatcher)
  77       : ID(ID), InnerMatcher(InnerMatcher) {}
  78
  79   bool dynMatches(const ast_type_traits::DynTypedNode &DynNode,
  80                   ASTMatchFinder *Finder,
  81                   BoundNodesTreeBuilder *Builder) const override {
  82     bool Result = InnerMatcher->dynMatches(DynNode, Finder, Builder);
  83     if (Result) Builder->setBinding(ID, DynNode);
  84     return Result;
  85   }
  86
  87  private:
  88   const std::string ID;
  89   const IntrusiveRefCntPtr<DynMatcherInterface> InnerMatcher;
  90 };
  91
  92 /// \brief A matcher that always returns true.
  93 ///
  94 /// We only ever need one instance of this matcher, so we create a global one
  95 /// and reuse it to reduce the overhead of the matcher and increase the chance
  96 /// of cache hits.
  97 class TrueMatcherImpl : public DynMatcherInterface {
  98 public:
  99   TrueMatcherImpl() {
 100     Retain(); // Reference count will never become zero.
 101   }
 102   bool dynMatches(const ast_type_traits::DynTypedNode &, ASTMatchFinder *,
 103                   BoundNodesTreeBuilder *) const override {
 104     return true;
 105   }
 106 };
 107 static llvm::ManagedStatic<TrueMatcherImpl> TrueMatcherInstance;
 108
 109 }  // namespace
 110
 111 DynTypedMatcher DynTypedMatcher::constructVariadic(
 112     DynTypedMatcher::VariadicOperator Op,
 113     std::vector<DynTypedMatcher> InnerMatchers) {
 114   assert(InnerMatchers.size() > 0 && "Array must not be empty.");
 115   assert(std::all_of(InnerMatchers.begin(), InnerMatchers.end(),
 116                      [&InnerMatchers](const DynTypedMatcher &M) {
 117            return InnerMatchers[0].SupportedKind.isSame(M.SupportedKind);
 118          }) &&
 119          "SupportedKind must match!");
 120
 121   auto SupportedKind = InnerMatchers[0].SupportedKind;
 122   // We must relax the restrict kind here.
 123   // The different operators might deal differently with a mismatch.
 124   // Make it the same as SupportedKind, since that is the broadest type we are
 125   // allowed to accept.
 126   auto RestrictKind = SupportedKind;
 127
 128   switch (Op) {
 129   case VO_AllOf:
 130     // In the case of allOf() we must pass all the checks, so making
 131     // RestrictKind the most restrictive can save us time. This way we reject
 132     // invalid types earlier and we can elide the kind checks inside the
 133     // matcher.
 134     for (auto &IM : InnerMatchers) {
 135       RestrictKind = ast_type_traits::ASTNodeKind::getMostDerivedType(
 136           RestrictKind, IM.RestrictKind);
 137     }
 138     return DynTypedMatcher(
 139         SupportedKind, RestrictKind,
 140         new VariadicMatcher<AllOfVariadicOperator>(std::move(InnerMatchers)));
 141
 142   case VO_AnyOf:
 143     return DynTypedMatcher(
 144         SupportedKind, RestrictKind,
 145         new VariadicMatcher<AnyOfVariadicOperator>(std::move(InnerMatchers)));
 146
 147   case VO_EachOf:
 148     return DynTypedMatcher(
 149         SupportedKind, RestrictKind,
 150         new VariadicMatcher<EachOfVariadicOperator>(std::move(InnerMatchers)));
 151
 152   case VO_UnaryNot:
 153     // FIXME: Implement the Not operator to take a single matcher instead of a
 154     // vector.
 155     return DynTypedMatcher(
 156         SupportedKind, RestrictKind,
 157         new VariadicMatcher<NotUnaryOperator>(std::move(InnerMatchers)));
 158   }
 159   llvm_unreachable("Invalid Op value.");
 160 }
 161
 162 DynTypedMatcher DynTypedMatcher::trueMatcher(
 163     ast_type_traits::ASTNodeKind NodeKind) {
 164   return DynTypedMatcher(NodeKind, NodeKind, &*TrueMatcherInstance);
 165 }
 166
 167 bool DynTypedMatcher::canMatchNodesOfKind(
 168     ast_type_traits::ASTNodeKind Kind) const {
 169   return RestrictKind.isBaseOf(Kind);
 170 }
 171
 172 DynTypedMatcher DynTypedMatcher::dynCastTo(
 173     const ast_type_traits::ASTNodeKind Kind) const {
 174   auto Copy = *this;
 175   Copy.SupportedKind = Kind;
 176   Copy.RestrictKind =
 177       ast_type_traits::ASTNodeKind::getMostDerivedType(Kind, RestrictKind);
 178   return Copy;
 179 }
 180
 181 bool DynTypedMatcher::matches(const ast_type_traits::DynTypedNode &DynNode,
 182                               ASTMatchFinder *Finder,
 183                               BoundNodesTreeBuilder *Builder) const {
 184   if (RestrictKind.isBaseOf(DynNode.getNodeKind()) &&
 185       Implementation->dynMatches(DynNode, Finder, Builder)) {
 186     return true;
 187   }
 188   // Delete all bindings when a matcher does not match.
 189   // This prevents unexpected exposure of bound nodes in unmatches
 190   // branches of the match tree.
 191   Builder->removeBindings([](const BoundNodesMap &) { return true; });
 192   return false;
 193 }
 194
 195 bool DynTypedMatcher::matchesNoKindCheck(
 196     const ast_type_traits::DynTypedNode &DynNode, ASTMatchFinder *Finder,
 197     BoundNodesTreeBuilder *Builder) const {
 198   assert(RestrictKind.isBaseOf(DynNode.getNodeKind()));
 199   if (Implementation->dynMatches(DynNode, Finder, Builder)) {
 200     return true;
 201   }
 202   // Delete all bindings when a matcher does not match.
 203   // This prevents unexpected exposure of bound nodes in unmatches
 204   // branches of the match tree.
 205   Builder->removeBindings([](const BoundNodesMap &) { return true; });
 206   return false;
 207 }
 208
 209 llvm::Optional<DynTypedMatcher> DynTypedMatcher::tryBind(StringRef ID) const {
 210   if (!AllowBind) return llvm::None;
 211   auto Result = *this;
 212   Result.Implementation = new IdDynMatcher(ID, Result.Implementation);
 213   return Result;
 214 }
 215
 216 bool DynTypedMatcher::canConvertTo(ast_type_traits::ASTNodeKind To) const {
 217   const auto From = getSupportedKind();
 218   auto QualKind = ast_type_traits::ASTNodeKind::getFromNodeKind<QualType>();
 219   auto TypeKind = ast_type_traits::ASTNodeKind::getFromNodeKind<Type>();
 220   /// Mimic the implicit conversions of Matcher<>.
 221   /// - From Matcher<Type> to Matcher<QualType>
 222   if (From.isSame(TypeKind) && To.isSame(QualKind)) return true;
 223   /// - From Matcher<Base> to Matcher<Derived>
 224   return From.isBaseOf(To);
 225 }
 226
 227 void BoundNodesTreeBuilder::addMatch(const BoundNodesTreeBuilder &Other) {
 228   Bindings.append(Other.Bindings.begin(), Other.Bindings.end());
 229 }
 230
 231 bool NotUnaryOperator(const ast_type_traits::DynTypedNode DynNode,
 232                       ASTMatchFinder *Finder, BoundNodesTreeBuilder *Builder,
 233                       ArrayRef<DynTypedMatcher> InnerMatchers) {
 234   if (InnerMatchers.size() != 1)
 235     return false;
 236
 237   // The 'unless' matcher will always discard the result:
 238   // If the inner matcher doesn't match, unless returns true,
 239   // but the inner matcher cannot have bound anything.
 240   // If the inner matcher matches, the result is false, and
 241   // any possible binding will be discarded.
 242   // We still need to hand in all the bound nodes up to this
 243   // point so the inner matcher can depend on bound nodes,
 244   // and we need to actively discard the bound nodes, otherwise
 245   // the inner matcher will reset the bound nodes if it doesn't
 246   // match, but this would be inversed by 'unless'.
 247   BoundNodesTreeBuilder Discard(*Builder);
 248   return !InnerMatchers[0].matches(DynNode, Finder, &Discard);
 249 }
 250
 251 bool AllOfVariadicOperator(const ast_type_traits::DynTypedNode DynNode,
 252                            ASTMatchFinder *Finder,
 253                            BoundNodesTreeBuilder *Builder,
 254                            ArrayRef<DynTypedMatcher> InnerMatchers) {
 255   // allOf leads to one matcher for each alternative in the first
 256   // matcher combined with each alternative in the second matcher.
 257   // Thus, we can reuse the same Builder.
 258   for (const DynTypedMatcher &InnerMatcher : InnerMatchers) {
 259     if (!InnerMatcher.matchesNoKindCheck(DynNode, Finder, Builder))
 260       return false;
 261   }
 262   return true;
 263 }
 264
 265 bool EachOfVariadicOperator(const ast_type_traits::DynTypedNode DynNode,
 266                             ASTMatchFinder *Finder,
 267                             BoundNodesTreeBuilder *Builder,
 268                             ArrayRef<DynTypedMatcher> InnerMatchers) {
 269   BoundNodesTreeBuilder Result;
 270   bool Matched = false;
 271   for (const DynTypedMatcher &InnerMatcher : InnerMatchers) {
 272     BoundNodesTreeBuilder BuilderInner(*Builder);
 273     if (InnerMatcher.matches(DynNode, Finder, &BuilderInner)) {
 274       Matched = true;
 275       Result.addMatch(BuilderInner);
 276     }
 277   }
 278   *Builder = std::move(Result);
 279   return Matched;
 280 }
 281
 282 bool AnyOfVariadicOperator(const ast_type_traits::DynTypedNode DynNode,
 283                            ASTMatchFinder *Finder,
 284                            BoundNodesTreeBuilder *Builder,
 285                            ArrayRef<DynTypedMatcher> InnerMatchers) {
 286   for (const DynTypedMatcher &InnerMatcher : InnerMatchers) {
 287     BoundNodesTreeBuilder Result = *Builder;
 288     if (InnerMatcher.matches(DynNode, Finder, &Result)) {
 289       *Builder = std::move(Result);
 290       return true;
 291     }
 292   }
 293   return false;
 294 }
 295
 296 HasNameMatcher::HasNameMatcher(StringRef NameRef)
 297     : UseUnqualifiedMatch(NameRef.find("::") == NameRef.npos), Name(NameRef) {
 298   assert(!Name.empty());
 299 }
 300
 301 bool HasNameMatcher::matchesNodeUnqualified(const NamedDecl &Node) const {
 302   assert(UseUnqualifiedMatch);
 303   if (Node.getIdentifier()) {
 304     // Simple name.
 305     return Name == Node.getName();
 306   }
 307   if (Node.getDeclName()) {
 308     // Name needs to be constructed.
 309     llvm::SmallString<128> NodeName;
 310     llvm::raw_svector_ostream OS(NodeName);
 311     Node.printName(OS);
 312     return Name == OS.str();
 313   }
 314   return false;
 315 }
 316
 317 bool HasNameMatcher::matchesNodeFull(const NamedDecl &Node) const {
 318   llvm::SmallString<128> NodeName = StringRef("::");
 319   llvm::raw_svector_ostream OS(NodeName);
 320   Node.printQualifiedName(OS);
 321   const StringRef FullName = OS.str();
 322   const StringRef Pattern = Name;
 323
 324   if (Pattern.startswith("::"))
 325     return FullName == Pattern;
 326
 327   return FullName.endswith(Pattern) &&
 328          FullName.drop_back(Pattern.size()).endswith("::");
 329 }
 330
 331 bool HasNameMatcher::matchesNode(const NamedDecl &Node) const {
 332   // FIXME: There is still room for improvement, but it would require copying a
 333   // lot of the logic from NamedDecl::printQualifiedName(). The benchmarks do
 334   // not show like that extra complexity is needed right now.
 335   if (UseUnqualifiedMatch) {
 336     assert(matchesNodeUnqualified(Node) == matchesNodeFull(Node));
 337     return matchesNodeUnqualified(Node);
 338   }
 339   return matchesNodeFull(Node);
 340 }
 341
 342 } // end namespace internal
 343 } // end namespace ast_matchers
 344 } // end namespace clang