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                IntrusiveRefCntPtr<DynMatcherInterface> InnerMatcher)
  78       : ID(ID), InnerMatcher(std::move(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 =
 214       new IdDynMatcher(ID, std::move(Result.Implementation));
 215   return std::move(Result);
 216 }
 217
 218 bool DynTypedMatcher::canConvertTo(ast_type_traits::ASTNodeKind To) const {
 219   const auto From = getSupportedKind();
 220   auto QualKind = ast_type_traits::ASTNodeKind::getFromNodeKind<QualType>();
 221   auto TypeKind = ast_type_traits::ASTNodeKind::getFromNodeKind<Type>();
 222   /// Mimic the implicit conversions of Matcher<>.
 223   /// - From Matcher<Type> to Matcher<QualType>
 224   if (From.isSame(TypeKind) && To.isSame(QualKind)) return true;
 225   /// - From Matcher<Base> to Matcher<Derived>
 226   return From.isBaseOf(To);
 227 }
 228
 229 void BoundNodesTreeBuilder::addMatch(const BoundNodesTreeBuilder &Other) {
 230   Bindings.append(Other.Bindings.begin(), Other.Bindings.end());
 231 }
 232
 233 bool NotUnaryOperator(const ast_type_traits::DynTypedNode &DynNode,
 234                       ASTMatchFinder *Finder, BoundNodesTreeBuilder *Builder,
 235                       ArrayRef<DynTypedMatcher> InnerMatchers) {
 236   if (InnerMatchers.size() != 1)
 237     return false;
 238
 239   // The 'unless' matcher will always discard the result:
 240   // If the inner matcher doesn't match, unless returns true,
 241   // but the inner matcher cannot have bound anything.
 242   // If the inner matcher matches, the result is false, and
 243   // any possible binding will be discarded.
 244   // We still need to hand in all the bound nodes up to this
 245   // point so the inner matcher can depend on bound nodes,
 246   // and we need to actively discard the bound nodes, otherwise
 247   // the inner matcher will reset the bound nodes if it doesn't
 248   // match, but this would be inversed by 'unless'.
 249   BoundNodesTreeBuilder Discard(*Builder);
 250   return !InnerMatchers[0].matches(DynNode, Finder, &Discard);
 251 }
 252
 253 bool AllOfVariadicOperator(const ast_type_traits::DynTypedNode &DynNode,
 254                            ASTMatchFinder *Finder,
 255                            BoundNodesTreeBuilder *Builder,
 256                            ArrayRef<DynTypedMatcher> InnerMatchers) {
 257   // allOf leads to one matcher for each alternative in the first
 258   // matcher combined with each alternative in the second matcher.
 259   // Thus, we can reuse the same Builder.
 260   for (const DynTypedMatcher &InnerMatcher : InnerMatchers) {
 261     if (!InnerMatcher.matchesNoKindCheck(DynNode, Finder, Builder))
 262       return false;
 263   }
 264   return true;
 265 }
 266
 267 bool EachOfVariadicOperator(const ast_type_traits::DynTypedNode &DynNode,
 268                             ASTMatchFinder *Finder,
 269                             BoundNodesTreeBuilder *Builder,
 270                             ArrayRef<DynTypedMatcher> InnerMatchers) {
 271   BoundNodesTreeBuilder Result;
 272   bool Matched = false;
 273   for (const DynTypedMatcher &InnerMatcher : InnerMatchers) {
 274     BoundNodesTreeBuilder BuilderInner(*Builder);
 275     if (InnerMatcher.matches(DynNode, Finder, &BuilderInner)) {
 276       Matched = true;
 277       Result.addMatch(BuilderInner);
 278     }
 279   }
 280   *Builder = std::move(Result);
 281   return Matched;
 282 }
 283
 284 bool AnyOfVariadicOperator(const ast_type_traits::DynTypedNode &DynNode,
 285                            ASTMatchFinder *Finder,
 286                            BoundNodesTreeBuilder *Builder,
 287                            ArrayRef<DynTypedMatcher> InnerMatchers) {
 288   for (const DynTypedMatcher &InnerMatcher : InnerMatchers) {
 289     BoundNodesTreeBuilder Result = *Builder;
 290     if (InnerMatcher.matches(DynNode, Finder, &Result)) {
 291       *Builder = std::move(Result);
 292       return true;
 293     }
 294   }
 295   return false;
 296 }
 297
 298 Matcher<NamedDecl> hasAnyNameFunc(ArrayRef<const StringRef *> NameRefs) {
 299   std::vector<std::string> Names;
 300   for (auto *Name : NameRefs)
 301     Names.emplace_back(*Name);
 302   return internal::Matcher<NamedDecl>(
 303       new internal::HasNameMatcher(std::move(Names)));
 304 }
 305
 306 HasNameMatcher::HasNameMatcher(std::vector<std::string> N)
 307     : UseUnqualifiedMatch(std::all_of(
 308           N.begin(), N.end(),
 309           [](StringRef Name) { return Name.find("::") == Name.npos; })),
 310       Names(std::move(N)) {
 311 #ifndef NDEBUG
 312   for (StringRef Name : Names)
 313     assert(!Name.empty());
 314 #endif
 315 }
 316
 317 namespace {
 318
 319 bool consumeNameSuffix(StringRef &FullName, StringRef Suffix) {
 320   StringRef Name = FullName;
 321   if (!Name.endswith(Suffix))
 322     return false;
 323   Name = Name.drop_back(Suffix.size());
 324   if (!Name.empty()) {
 325     if (!Name.endswith("::"))
 326       return false;
 327     Name = Name.drop_back(2);
 328   }
 329   FullName = Name;
 330   return true;
 331 }
 332
 333 StringRef getNodeName(const NamedDecl &Node, llvm::SmallString<128> &Scratch) {
 334   // Simple name.
 335   if (Node.getIdentifier())
 336     return Node.getName();
 337
 338   if (Node.getDeclName()) {
 339     // Name needs to be constructed.
 340     Scratch.clear();
 341     llvm::raw_svector_ostream OS(Scratch);
 342     Node.printName(OS);
 343     return OS.str();
 344   }
 345
 346   return "(anonymous)";
 347 }
 348
 349 StringRef getNodeName(const RecordDecl &Node, llvm::SmallString<128> &Scratch) {
 350   if (Node.getIdentifier()) {
 351     return Node.getName();
 352   }
 353   Scratch.clear();
 354   return ("(anonymous " + Node.getKindName() + ")").toStringRef(Scratch);
 355 }
 356
 357 StringRef getNodeName(const NamespaceDecl &Node,
 358                       llvm::SmallString<128> &Scratch) {
 359   return Node.isAnonymousNamespace() ? "(anonymous namespace)" : Node.getName();
 360 }
 361
 362
 363 class PatternSet {
 364 public:
 365   PatternSet(ArrayRef<std::string> Names) {
 366     for (StringRef Name : Names)
 367       Patterns.push_back({Name, Name.startswith("::")});
 368   }
 369
 370   /// Consumes the name suffix from each pattern in the set and removes the ones
 371   /// that didn't match.
 372   /// Return true if there are still any patterns left.
 373   bool consumeNameSuffix(StringRef NodeName, bool CanSkip) {
 374     for (size_t I = 0; I < Patterns.size();) {
 375       if (internal::consumeNameSuffix(Patterns[I].P, NodeName) ||
 376           CanSkip) {
 377         ++I;
 378       } else {
 379         Patterns.erase(Patterns.begin() + I);
 380       }
 381     }
 382     return !Patterns.empty();
 383   }
 384
 385   /// Check if any of the patterns are a match.
 386   /// A match will be a pattern that was fully consumed, that also matches the
 387   /// 'fully qualified' requirement.
 388   bool foundMatch(bool AllowFullyQualified) const {
 389     for (auto& P: Patterns)
 390       if (P.P.empty() && (AllowFullyQualified || !P.IsFullyQualified))
 391         return true;
 392     return false;
 393   }
 394
 395 private:
 396   struct Pattern {
 397     StringRef P;
 398     bool IsFullyQualified;
 399   };
 400   llvm::SmallVector<Pattern, 8> Patterns;
 401 };
 402
 403 }  // namespace
 404
 405 bool HasNameMatcher::matchesNodeUnqualified(const NamedDecl &Node) const {
 406   assert(UseUnqualifiedMatch);
 407   llvm::SmallString<128> Scratch;
 408   StringRef NodeName = getNodeName(Node, Scratch);
 409   return std::any_of(Names.begin(), Names.end(), [&](StringRef Name) {
 410     return consumeNameSuffix(Name, NodeName) && Name.empty();
 411   });
 412 }
 413
 414 bool HasNameMatcher::matchesNodeFullFast(const NamedDecl &Node) const {
 415   PatternSet Patterns(Names);
 416   llvm::SmallString<128> Scratch;
 417
 418   // This function is copied and adapted from NamedDecl::printQualifiedName()
 419   // By matching each part individually we optimize in a couple of ways:
 420   //  - We can exit early on the first failure.
 421   //  - We can skip inline/anonymous namespaces without another pass.
 422   //  - We print one name at a time, reducing the chance of overflowing the
 423   //    inlined space of the SmallString.
 424
 425   // First, match the name.
 426   if (!Patterns.consumeNameSuffix(getNodeName(Node, Scratch),
 427                                   /*CanSkip=*/false))
 428     return false;
 429
 430   // Try to match each declaration context.
 431   // We are allowed to skip anonymous and inline namespaces if they don't match.
 432   const DeclContext *Ctx = Node.getDeclContext();
 433
 434   if (Ctx->isFunctionOrMethod())
 435     return Patterns.foundMatch(/*AllowFullyQualified=*/false);
 436
 437   for (; Ctx && isa<NamedDecl>(Ctx); Ctx = Ctx->getParent()) {
 438     if (Patterns.foundMatch(/*AllowFullyQualified=*/false))
 439       return true;
 440
 441     if (const auto *ND = dyn_cast<NamespaceDecl>(Ctx)) {
 442       // If it matches (or we can skip it), continue.
 443       if (Patterns.consumeNameSuffix(getNodeName(*ND, Scratch),
 444                                      /*CanSkip=*/ND->isAnonymousNamespace() ||
 445                                          ND->isInline()))
 446         continue;
 447       return false;
 448     }
 449     if (const auto *RD = dyn_cast<RecordDecl>(Ctx)) {
 450       if (!isa<ClassTemplateSpecializationDecl>(Ctx)) {
 451         if (Patterns.consumeNameSuffix(getNodeName(*RD, Scratch),
 452                                        /*CanSkip=*/false))
 453           continue;
 454
 455         return false;
 456       }
 457     }
 458
 459     // We don't know how to deal with this DeclContext.
 460     // Fallback to the slow version of the code.
 461     return matchesNodeFullSlow(Node);
 462   }
 463
 464   return Patterns.foundMatch(/*AllowFullyQualified=*/true);
 465 }
 466
 467 bool HasNameMatcher::matchesNodeFullSlow(const NamedDecl &Node) const {
 468   const bool SkipUnwrittenCases[] = {false, true};
 469   for (bool SkipUnwritten : SkipUnwrittenCases) {
 470     llvm::SmallString<128> NodeName = StringRef("::");
 471     llvm::raw_svector_ostream OS(NodeName);
 472
 473     if (SkipUnwritten) {
 474       PrintingPolicy Policy = Node.getASTContext().getPrintingPolicy();
 475       Policy.SuppressUnwrittenScope = true;
 476       Node.printQualifiedName(OS, Policy);
 477     } else {
 478       Node.printQualifiedName(OS);
 479     }
 480
 481     const StringRef FullName = OS.str();
 482
 483     for (const StringRef Pattern : Names) {
 484       if (Pattern.startswith("::")) {
 485         if (FullName == Pattern)
 486           return true;
 487       } else if (FullName.endswith(Pattern) &&
 488                  FullName.drop_back(Pattern.size()).endswith("::")) {
 489         return true;
 490       }
 491     }
 492   }
 493
 494   return false;
 495 }
 496
 497 bool HasNameMatcher::matchesNode(const NamedDecl &Node) const {
 498   assert(matchesNodeFullFast(Node) == matchesNodeFullSlow(Node));
 499   if (UseUnqualifiedMatch) {
 500     assert(matchesNodeUnqualified(Node) == matchesNodeFullFast(Node));
 501     return matchesNodeUnqualified(Node);
 502   }
 503   return matchesNodeFullFast(Node);
 504 }
 505
 506 } // end namespace internal
 507 } // end namespace ast_matchers
 508 } // end namespace clang