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 ast_type_traits::ASTNodeKind SupportedKind, 114 std::vector<DynTypedMatcher> InnerMatchers) { 115 assert(InnerMatchers.size() > 0 && "Array must not be empty."); 116 assert(std::all_of(InnerMatchers.begin(), InnerMatchers.end(), 117 [SupportedKind](const DynTypedMatcher &M) { 118 return M.canConvertTo(SupportedKind); 119 }) && 120 "InnerMatchers must be convertible to SupportedKind!"); 121 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 345
