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/ADT/SmallVector.h"
  18 #include "llvm/Support/ManagedStatic.h"
  19
  20 namespace clang {
  21 namespace ast_matchers {
  22 namespace internal {
  23
  24 bool NotUnaryOperator(const ast_type_traits::DynTypedNode &DynNode,
  25                       ASTMatchFinder *Finder, BoundNodesTreeBuilder *Builder,
  26                       ArrayRef<DynTypedMatcher> InnerMatchers);
  27
  28 bool AllOfVariadicOperator(const ast_type_traits::DynTypedNode &DynNode,
  29                            ASTMatchFinder *Finder,
  30                            BoundNodesTreeBuilder *Builder,
  31                            ArrayRef<DynTypedMatcher> InnerMatchers);
  32
  33 bool EachOfVariadicOperator(const ast_type_traits::DynTypedNode &DynNode,
  34                             ASTMatchFinder *Finder,
  35                             BoundNodesTreeBuilder *Builder,
  36                             ArrayRef<DynTypedMatcher> InnerMatchers);
  37
  38 bool AnyOfVariadicOperator(const ast_type_traits::DynTypedNode &DynNode,
  39                            ASTMatchFinder *Finder,
  40                            BoundNodesTreeBuilder *Builder,
  41                            ArrayRef<DynTypedMatcher> InnerMatchers);
  42
  43
  44 void BoundNodesTreeBuilder::visitMatches(Visitor *ResultVisitor) {
  45   if (Bindings.empty())
  46     Bindings.push_back(BoundNodesMap());
  47   for (BoundNodesMap &Binding : Bindings) {
  48     ResultVisitor->visitMatch(BoundNodes(Binding));
  49   }
  50 }
  51
  52 namespace {
  53
  54 typedef bool (*VariadicOperatorFunction)(
  55     const ast_type_traits::DynTypedNode &DynNode, ASTMatchFinder *Finder,
  56     BoundNodesTreeBuilder *Builder, ArrayRef<DynTypedMatcher> InnerMatchers);
  57
  58 template <VariadicOperatorFunction Func>
  59 class VariadicMatcher : public DynMatcherInterface {
  60 public:
  61   VariadicMatcher(std::vector<DynTypedMatcher> InnerMatchers)
  62       : InnerMatchers(std::move(InnerMatchers)) {}
  63
  64   bool dynMatches(const ast_type_traits::DynTypedNode &DynNode,
  65                   ASTMatchFinder *Finder,
  66                   BoundNodesTreeBuilder *Builder) const override {
  67     return Func(DynNode, Finder, Builder, InnerMatchers);
  68   }
  69
  70 private:
  71   std::vector<DynTypedMatcher> InnerMatchers;
  72 };
  73
  74 class IdDynMatcher : public DynMatcherInterface {
  75  public:
  76   IdDynMatcher(StringRef ID,
  77                const IntrusiveRefCntPtr<DynMatcherInterface> &InnerMatcher)
  78       : ID(ID), InnerMatcher(InnerMatcher) {}
  79
  80   bool dynMatches(const ast_type_traits::DynTypedNode &DynNode,
  81                   ASTMatchFinder *Finder,
  82                   BoundNodesTreeBuilder *Builder) const override {
  83     bool Result = InnerMatcher->dynMatches(DynNode, Finder, Builder);
  84     if (Result) Builder->setBinding(ID, DynNode);
  85     return Result;
  86   }
  87
  88  private:
  89   const std::string ID;
  90   const IntrusiveRefCntPtr<DynMatcherInterface> InnerMatcher;
  91 };
  92
  93 /// \brief A matcher that always returns true.
  94 ///
  95 /// We only ever need one instance of this matcher, so we create a global one
  96 /// and reuse it to reduce the overhead of the matcher and increase the chance
  97 /// of cache hits.
  98 class TrueMatcherImpl : public DynMatcherInterface {
  99 public:
 100   TrueMatcherImpl() {
 101     Retain(); // Reference count will never become zero.
 102   }
 103   bool dynMatches(const ast_type_traits::DynTypedNode &, ASTMatchFinder *,
 104                   BoundNodesTreeBuilder *) const override {
 105     return true;
 106   }
 107 };
 108 static llvm::ManagedStatic<TrueMatcherImpl> TrueMatcherInstance;
 109
 110 }  // namespace
 111
 112 DynTypedMatcher DynTypedMatcher::constructVariadic(
 113     DynTypedMatcher::VariadicOperator Op,
 114     ast_type_traits::ASTNodeKind SupportedKind,
 115     std::vector<DynTypedMatcher> InnerMatchers) {
 116   assert(InnerMatchers.size() > 0 && "Array must not be empty.");
 117   assert(std::all_of(InnerMatchers.begin(), InnerMatchers.end(),
 118                      [SupportedKind](const DynTypedMatcher &M) {
 119                        return M.canConvertTo(SupportedKind);
 120                      }) &&
 121          "InnerMatchers must be convertible to SupportedKind!");
 122
 123   // We must relax the restrict kind here.
 124   // The different operators might deal differently with a mismatch.
 125   // Make it the same as SupportedKind, since that is the broadest type we are
 126   // allowed to accept.
 127   auto RestrictKind = SupportedKind;
 128
 129   switch (Op) {
 130   case VO_AllOf:
 131     // In the case of allOf() we must pass all the checks, so making
 132     // RestrictKind the most restrictive can save us time. This way we reject
 133     // invalid types earlier and we can elide the kind checks inside the
 134     // matcher.
 135     for (auto &IM : InnerMatchers) {
 136       RestrictKind = ast_type_traits::ASTNodeKind::getMostDerivedType(
 137           RestrictKind, IM.RestrictKind);
 138     }
 139     return DynTypedMatcher(
 140         SupportedKind, RestrictKind,
 141         new VariadicMatcher<AllOfVariadicOperator>(std::move(InnerMatchers)));
 142
 143   case VO_AnyOf:
 144     return DynTypedMatcher(
 145         SupportedKind, RestrictKind,
 146         new VariadicMatcher<AnyOfVariadicOperator>(std::move(InnerMatchers)));
 147
 148   case VO_EachOf:
 149     return DynTypedMatcher(
 150         SupportedKind, RestrictKind,
 151         new VariadicMatcher<EachOfVariadicOperator>(std::move(InnerMatchers)));
 152
 153   case VO_UnaryNot:
 154     // FIXME: Implement the Not operator to take a single matcher instead of a
 155     // vector.
 156     return DynTypedMatcher(
 157         SupportedKind, RestrictKind,
 158         new VariadicMatcher<NotUnaryOperator>(std::move(InnerMatchers)));
 159   }
 160   llvm_unreachable("Invalid Op value.");
 161 }
 162
 163 DynTypedMatcher DynTypedMatcher::trueMatcher(
 164     ast_type_traits::ASTNodeKind NodeKind) {
 165   return DynTypedMatcher(NodeKind, NodeKind, &*TrueMatcherInstance);
 166 }
 167
 168 bool DynTypedMatcher::canMatchNodesOfKind(
 169     ast_type_traits::ASTNodeKind Kind) const {
 170   return RestrictKind.isBaseOf(Kind);
 171 }
 172
 173 DynTypedMatcher DynTypedMatcher::dynCastTo(
 174     const ast_type_traits::ASTNodeKind Kind) const {
 175   auto Copy = *this;
 176   Copy.SupportedKind = Kind;
 177   Copy.RestrictKind =
 178       ast_type_traits::ASTNodeKind::getMostDerivedType(Kind, RestrictKind);
 179   return Copy;
 180 }
 181
 182 bool DynTypedMatcher::matches(const ast_type_traits::DynTypedNode &DynNode,
 183                               ASTMatchFinder *Finder,
 184                               BoundNodesTreeBuilder *Builder) const {
 185   if (RestrictKind.isBaseOf(DynNode.getNodeKind()) &&
 186       Implementation->dynMatches(DynNode, Finder, Builder)) {
 187     return true;
 188   }
 189   // Delete all bindings when a matcher does not match.
 190   // This prevents unexpected exposure of bound nodes in unmatches
 191   // branches of the match tree.
 192   Builder->removeBindings([](const BoundNodesMap &) { return true; });
 193   return false;
 194 }
 195
 196 bool DynTypedMatcher::matchesNoKindCheck(
 197     const ast_type_traits::DynTypedNode &DynNode, ASTMatchFinder *Finder,
 198     BoundNodesTreeBuilder *Builder) const {
 199   assert(RestrictKind.isBaseOf(DynNode.getNodeKind()));
 200   if (Implementation->dynMatches(DynNode, Finder, Builder)) {
 201     return true;
 202   }
 203   // Delete all bindings when a matcher does not match.
 204   // This prevents unexpected exposure of bound nodes in unmatches
 205   // branches of the match tree.
 206   Builder->removeBindings([](const BoundNodesMap &) { return true; });
 207   return false;
 208 }
 209
 210 llvm::Optional<DynTypedMatcher> DynTypedMatcher::tryBind(StringRef ID) const {
 211   if (!AllowBind) return llvm::None;
 212   auto Result = *this;
 213   Result.Implementation = new IdDynMatcher(ID, Result.Implementation);
 214   return Result;
 215 }
 216
 217 bool DynTypedMatcher::canConvertTo(ast_type_traits::ASTNodeKind To) const {
 218   const auto From = getSupportedKind();
 219   auto QualKind = ast_type_traits::ASTNodeKind::getFromNodeKind<QualType>();
 220   auto TypeKind = ast_type_traits::ASTNodeKind::getFromNodeKind<Type>();
 221   /// Mimic the implicit conversions of Matcher<>.
 222   /// - From Matcher<Type> to Matcher<QualType>
 223   if (From.isSame(TypeKind) && To.isSame(QualKind)) return true;
 224   /// - From Matcher<Base> to Matcher<Derived>
 225   return From.isBaseOf(To);
 226 }
 227
 228 void BoundNodesTreeBuilder::addMatch(const BoundNodesTreeBuilder &Other) {
 229   Bindings.append(Other.Bindings.begin(), Other.Bindings.end());
 230 }
 231
 232 bool NotUnaryOperator(const ast_type_traits::DynTypedNode &DynNode,
 233                       ASTMatchFinder *Finder, BoundNodesTreeBuilder *Builder,
 234                       ArrayRef<DynTypedMatcher> InnerMatchers) {
 235   if (InnerMatchers.size() != 1)
 236     return false;
 237
 238   // The 'unless' matcher will always discard the result:
 239   // If the inner matcher doesn't match, unless returns true,
 240   // but the inner matcher cannot have bound anything.
 241   // If the inner matcher matches, the result is false, and
 242   // any possible binding will be discarded.
 243   // We still need to hand in all the bound nodes up to this
 244   // point so the inner matcher can depend on bound nodes,
 245   // and we need to actively discard the bound nodes, otherwise
 246   // the inner matcher will reset the bound nodes if it doesn't
 247   // match, but this would be inversed by 'unless'.
 248   BoundNodesTreeBuilder Discard(*Builder);
 249   return !InnerMatchers[0].matches(DynNode, Finder, &Discard);
 250 }
 251
 252 bool AllOfVariadicOperator(const ast_type_traits::DynTypedNode &DynNode,
 253                            ASTMatchFinder *Finder,
 254                            BoundNodesTreeBuilder *Builder,
 255                            ArrayRef<DynTypedMatcher> InnerMatchers) {
 256   // allOf leads to one matcher for each alternative in the first
 257   // matcher combined with each alternative in the second matcher.
 258   // Thus, we can reuse the same Builder.
 259   for (const DynTypedMatcher &InnerMatcher : InnerMatchers) {
 260     if (!InnerMatcher.matchesNoKindCheck(DynNode, Finder, Builder))
 261       return false;
 262   }
 263   return true;
 264 }
 265
 266 bool EachOfVariadicOperator(const ast_type_traits::DynTypedNode &DynNode,
 267                             ASTMatchFinder *Finder,
 268                             BoundNodesTreeBuilder *Builder,
 269                             ArrayRef<DynTypedMatcher> InnerMatchers) {
 270   BoundNodesTreeBuilder Result;
 271   bool Matched = false;
 272   for (const DynTypedMatcher &InnerMatcher : InnerMatchers) {
 273     BoundNodesTreeBuilder BuilderInner(*Builder);
 274     if (InnerMatcher.matches(DynNode, Finder, &BuilderInner)) {
 275       Matched = true;
 276       Result.addMatch(BuilderInner);
 277     }
 278   }
 279   *Builder = std::move(Result);
 280   return Matched;
 281 }
 282
 283 bool AnyOfVariadicOperator(const ast_type_traits::DynTypedNode &DynNode,
 284                            ASTMatchFinder *Finder,
 285                            BoundNodesTreeBuilder *Builder,
 286                            ArrayRef<DynTypedMatcher> InnerMatchers) {
 287   for (const DynTypedMatcher &InnerMatcher : InnerMatchers) {
 288     BoundNodesTreeBuilder Result = *Builder;
 289     if (InnerMatcher.matches(DynNode, Finder, &Result)) {
 290       *Builder = std::move(Result);
 291       return true;
 292     }
 293   }
 294   return false;
 295 }
 296
 297 Matcher<NamedDecl> hasAnyNameFunc(ArrayRef<const StringRef *> NameRefs) {
 298   std::vector<std::string> Names;
 299   for (auto *Name : NameRefs)
 300     Names.emplace_back(*Name);
 301   return internal::Matcher<NamedDecl>(
 302       new internal::HasNameMatcher(std::move(Names)));
 303 }
 304
 305 HasNameMatcher::HasNameMatcher(std::vector<std::string> N)
 306     : UseUnqualifiedMatch(std::all_of(
 307           N.begin(), N.end(),
 308           [](StringRef Name) { return Name.find("::") == Name.npos; })),
 309       Names(std::move(N)) {
 310 #ifndef NDEBUG
 311   for (StringRef Name : Names)
 312     assert(!Name.empty());
 313 #endif
 314 }
 315
 316 namespace {
 317
 318 bool consumeNameSuffix(StringRef &FullName, StringRef Suffix) {
 319   StringRef Name = FullName;
 320   if (!Name.endswith(Suffix))
 321     return false;
 322   Name = Name.drop_back(Suffix.size());
 323   if (!Name.empty()) {
 324     if (!Name.endswith("::"))
 325       return false;
 326     Name = Name.drop_back(2);
 327   }
 328   FullName = Name;
 329   return true;
 330 }
 331
 332 StringRef getNodeName(const NamedDecl &Node, llvm::SmallString<128> &Scratch) {
 333   // Simple name.
 334   if (Node.getIdentifier())
 335     return Node.getName();
 336
 337   if (Node.getDeclName()) {
 338     // Name needs to be constructed.
 339     Scratch.clear();
 340     llvm::raw_svector_ostream OS(Scratch);
 341     Node.printName(OS);
 342     return OS.str();
 343   }
 344
 345   return "(anonymous)";
 346 }
 347
 348 StringRef getNodeName(const RecordDecl &Node, llvm::SmallString<128> &Scratch) {
 349   if (Node.getIdentifier()) {
 350     return Node.getName();
 351   }
 352   Scratch.clear();
 353   return ("(anonymous " + Node.getKindName() + ")").toStringRef(Scratch);
 354 }
 355
 356 StringRef getNodeName(const NamespaceDecl &Node,
 357                       llvm::SmallString<128> &Scratch) {
 358   return Node.isAnonymousNamespace() ? "(anonymous namespace)" : Node.getName();
 359 }
 360
 361
 362 class PatternSet {
 363 public:
 364   PatternSet(ArrayRef<std::string> Names) {
 365     for (StringRef Name : Names)
 366       Patterns.push_back({Name, Name.startswith("::")});
 367   }
 368
 369   /// Consumes the name suffix from each pattern in the set and removes the ones
 370   /// that didn't match.
 371   /// Return true if there are still any patterns left.
 372   bool consumeNameSuffix(StringRef NodeName, bool CanSkip) {
 373     for (size_t I = 0; I < Patterns.size();) {
 374       if (internal::consumeNameSuffix(Patterns[I].P, NodeName) ||
 375           CanSkip) {
 376         ++I;
 377       } else {
 378         Patterns.erase(Patterns.begin() + I);
 379       }
 380     }
 381     return !Patterns.empty();
 382   }
 383
 384   /// Check if any of the patterns are a match.
 385   /// A match will be a pattern that was fully consumed, that also matches the
 386   /// 'fully qualified' requirement.
 387   bool foundMatch(bool AllowFullyQualified) const {
 388     for (auto& P: Patterns)
 389       if (P.P.empty() && (AllowFullyQualified || !P.IsFullyQualified))
 390         return true;
 391     return false;
 392   }
 393
 394 private:
 395   struct Pattern {
 396     StringRef P;
 397     bool IsFullyQualified;
 398   };
 399   llvm::SmallVector<Pattern, 8> Patterns;
 400 };
 401
 402 }  // namespace
 403
 404 bool HasNameMatcher::matchesNodeUnqualified(const NamedDecl &Node) const {
 405   assert(UseUnqualifiedMatch);
 406   llvm::SmallString<128> Scratch;
 407   StringRef NodeName = getNodeName(Node, Scratch);
 408   return std::any_of(Names.begin(), Names.end(), [&](StringRef Name) {
 409     return consumeNameSuffix(Name, NodeName) && Name.empty();
 410   });
 411 }
 412
 413 bool HasNameMatcher::matchesNodeFullFast(const NamedDecl &Node) const {
 414   PatternSet Patterns(Names);
 415   llvm::SmallString<128> Scratch;
 416
 417   // This function is copied and adapted from NamedDecl::printQualifiedName()
 418   // By matching each part individually we optimize in a couple of ways:
 419   //  - We can exit early on the first failure.
 420   //  - We can skip inline/anonymous namespaces without another pass.
 421   //  - We print one name at a time, reducing the chance of overflowing the
 422   //    inlined space of the SmallString.
 423
 424   // First, match the name.
 425   if (!Patterns.consumeNameSuffix(getNodeName(Node, Scratch),
 426                                   /*CanSkip=*/false))
 427     return false;
 428
 429   // Try to match each declaration context.
 430   // We are allowed to skip anonymous and inline namespaces if they don't match.
 431   const DeclContext *Ctx = Node.getDeclContext();
 432
 433   if (Ctx->isFunctionOrMethod())
 434     return Patterns.foundMatch(/*AllowFullyQualified=*/false);
 435
 436   for (; Ctx && isa<NamedDecl>(Ctx); Ctx = Ctx->getParent()) {
 437     if (Patterns.foundMatch(/*AllowFullyQualified=*/false))
 438       return true;
 439
 440     if (const auto *ND = dyn_cast<NamespaceDecl>(Ctx)) {
 441       // If it matches (or we can skip it), continue.
 442       if (Patterns.consumeNameSuffix(getNodeName(*ND, Scratch),
 443                                      /*CanSkip=*/ND->isAnonymousNamespace() ||
 444                                          ND->isInline()))
 445         continue;
 446       return false;
 447     }
 448     if (const auto *RD = dyn_cast<RecordDecl>(Ctx)) {
 449       if (!isa<ClassTemplateSpecializationDecl>(Ctx)) {
 450         if (Patterns.consumeNameSuffix(getNodeName(*RD, Scratch),
 451                                        /*CanSkip=*/false))
 452           continue;
 453
 454         return false;
 455       }
 456     }
 457
 458     // We don't know how to deal with this DeclContext.
 459     // Fallback to the slow version of the code.
 460     return matchesNodeFullSlow(Node);
 461   }
 462
 463   return Patterns.foundMatch(/*AllowFullyQualified=*/true);
 464 }
 465
 466 bool HasNameMatcher::matchesNodeFullSlow(const NamedDecl &Node) const {
 467   const bool SkipUnwrittenCases[] = {false, true};
 468   for (bool SkipUnwritten : SkipUnwrittenCases) {
 469     llvm::SmallString<128> NodeName = StringRef("::");
 470     llvm::raw_svector_ostream OS(NodeName);
 471
 472     if (SkipUnwritten) {
 473       PrintingPolicy Policy = Node.getASTContext().getPrintingPolicy();
 474       Policy.SuppressUnwrittenScope = true;
 475       Node.printQualifiedName(OS, Policy);
 476     } else {
 477       Node.printQualifiedName(OS);
 478     }
 479
 480     const StringRef FullName = OS.str();
 481
 482     for (const StringRef Pattern : Names) {
 483       if (Pattern.startswith("::")) {
 484         if (FullName == Pattern)
 485           return true;
 486       } else if (FullName.endswith(Pattern) &&
 487                  FullName.drop_back(Pattern.size()).endswith("::")) {
 488         return true;
 489       }
 490     }
 491   }
 492
 493   return false;
 494 }
 495
 496 bool HasNameMatcher::matchesNode(const NamedDecl &Node) const {
 497   assert(matchesNodeFullFast(Node) == matchesNodeFullSlow(Node));
 498   if (UseUnqualifiedMatch) {
 499     assert(matchesNodeUnqualified(Node) == matchesNodeFullFast(Node));
 500     return matchesNodeUnqualified(Node);
 501   }
 502   return matchesNodeFullFast(Node);
 503 }
 504
 505 } // end namespace internal
 506 } // end namespace ast_matchers
 507 } // end namespace clang