RewriteRule.cpp revision 1.1.1.2
1//===--- Transformer.cpp - Transformer library implementation ---*- C++ -*-===// 2// 3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4// See https://llvm.org/LICENSE.txt for license information. 5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6// 7//===----------------------------------------------------------------------===// 8 9#include "clang/Tooling/Transformer/RewriteRule.h" 10#include "clang/AST/ASTTypeTraits.h" 11#include "clang/AST/Stmt.h" 12#include "clang/ASTMatchers/ASTMatchFinder.h" 13#include "clang/ASTMatchers/ASTMatchers.h" 14#include "clang/Basic/SourceLocation.h" 15#include "clang/Tooling/Transformer/SourceCode.h" 16#include "llvm/ADT/Optional.h" 17#include "llvm/ADT/StringRef.h" 18#include "llvm/Support/Errc.h" 19#include "llvm/Support/Error.h" 20#include <map> 21#include <string> 22#include <utility> 23#include <vector> 24 25using namespace clang; 26using namespace transformer; 27 28using ast_matchers::MatchFinder; 29using ast_matchers::internal::DynTypedMatcher; 30 31using MatchResult = MatchFinder::MatchResult; 32 33const char transformer::RootID[] = "___root___"; 34 35static Expected<SmallVector<transformer::Edit, 1>> 36translateEdits(const MatchResult &Result, ArrayRef<ASTEdit> ASTEdits) { 37 SmallVector<transformer::Edit, 1> Edits; 38 for (const auto &E : ASTEdits) { 39 Expected<CharSourceRange> Range = E.TargetRange(Result); 40 if (!Range) 41 return Range.takeError(); 42 llvm::Optional<CharSourceRange> EditRange = 43 tooling::getRangeForEdit(*Range, *Result.Context); 44 // FIXME: let user specify whether to treat this case as an error or ignore 45 // it as is currently done. This behavior is problematic in that it hides 46 // failures from bad ranges. Also, the behavior here differs from 47 // `flatten`. Here, we abort (without error), whereas flatten, if it hits an 48 // empty list, does not abort. As a result, `editList({A,B})` is not 49 // equivalent to `flatten(edit(A), edit(B))`. The former will abort if `A` 50 // produces a bad range, whereas the latter will simply ignore A. 51 if (!EditRange) 52 return SmallVector<Edit, 0>(); 53 auto Replacement = E.Replacement->eval(Result); 54 if (!Replacement) 55 return Replacement.takeError(); 56 auto Metadata = E.Metadata(Result); 57 if (!Metadata) 58 return Metadata.takeError(); 59 transformer::Edit T; 60 T.Kind = E.Kind; 61 T.Range = *EditRange; 62 T.Replacement = std::move(*Replacement); 63 T.Metadata = std::move(*Metadata); 64 Edits.push_back(std::move(T)); 65 } 66 return Edits; 67} 68 69EditGenerator transformer::editList(SmallVector<ASTEdit, 1> Edits) { 70 return [Edits = std::move(Edits)](const MatchResult &Result) { 71 return translateEdits(Result, Edits); 72 }; 73} 74 75EditGenerator transformer::edit(ASTEdit Edit) { 76 return [Edit = std::move(Edit)](const MatchResult &Result) { 77 return translateEdits(Result, {Edit}); 78 }; 79} 80 81EditGenerator transformer::noopEdit(RangeSelector Anchor) { 82 return [Anchor = std::move(Anchor)](const MatchResult &Result) 83 -> Expected<SmallVector<transformer::Edit, 1>> { 84 Expected<CharSourceRange> Range = Anchor(Result); 85 if (!Range) 86 return Range.takeError(); 87 // In case the range is inside a macro expansion, map the location back to a 88 // "real" source location. 89 SourceLocation Begin = 90 Result.SourceManager->getSpellingLoc(Range->getBegin()); 91 Edit E; 92 // Implicitly, leave `E.Replacement` as the empty string. 93 E.Kind = EditKind::Range; 94 E.Range = CharSourceRange::getCharRange(Begin, Begin); 95 return SmallVector<Edit, 1>{E}; 96 }; 97} 98 99EditGenerator 100transformer::flattenVector(SmallVector<EditGenerator, 2> Generators) { 101 if (Generators.size() == 1) 102 return std::move(Generators[0]); 103 return 104 [Gs = std::move(Generators)]( 105 const MatchResult &Result) -> llvm::Expected<SmallVector<Edit, 1>> { 106 SmallVector<Edit, 1> AllEdits; 107 for (const auto &G : Gs) { 108 llvm::Expected<SmallVector<Edit, 1>> Edits = G(Result); 109 if (!Edits) 110 return Edits.takeError(); 111 AllEdits.append(Edits->begin(), Edits->end()); 112 } 113 return AllEdits; 114 }; 115} 116 117ASTEdit transformer::changeTo(RangeSelector Target, TextGenerator Replacement) { 118 ASTEdit E; 119 E.TargetRange = std::move(Target); 120 E.Replacement = std::move(Replacement); 121 return E; 122} 123 124namespace { 125/// A \c TextGenerator that always returns a fixed string. 126class SimpleTextGenerator : public MatchComputation<std::string> { 127 std::string S; 128 129public: 130 SimpleTextGenerator(std::string S) : S(std::move(S)) {} 131 llvm::Error eval(const ast_matchers::MatchFinder::MatchResult &, 132 std::string *Result) const override { 133 Result->append(S); 134 return llvm::Error::success(); 135 } 136 std::string toString() const override { 137 return (llvm::Twine("text(\"") + S + "\")").str(); 138 } 139}; 140} // namespace 141 142static TextGenerator makeText(std::string S) { 143 return std::make_shared<SimpleTextGenerator>(std::move(S)); 144} 145 146ASTEdit transformer::remove(RangeSelector S) { 147 return change(std::move(S), makeText("")); 148} 149 150static std::string formatHeaderPath(StringRef Header, IncludeFormat Format) { 151 switch (Format) { 152 case transformer::IncludeFormat::Quoted: 153 return Header.str(); 154 case transformer::IncludeFormat::Angled: 155 return ("<" + Header + ">").str(); 156 } 157 llvm_unreachable("Unknown transformer::IncludeFormat enum"); 158} 159 160ASTEdit transformer::addInclude(RangeSelector Target, StringRef Header, 161 IncludeFormat Format) { 162 ASTEdit E; 163 E.Kind = EditKind::AddInclude; 164 E.TargetRange = Target; 165 E.Replacement = makeText(formatHeaderPath(Header, Format)); 166 return E; 167} 168 169RewriteRule transformer::makeRule(DynTypedMatcher M, EditGenerator Edits, 170 TextGenerator Explanation) { 171 return RewriteRule{{RewriteRule::Case{std::move(M), std::move(Edits), 172 std::move(Explanation)}}}; 173} 174 175namespace { 176 177/// Unconditionally binds the given node set before trying `InnerMatcher` and 178/// keeps the bound nodes on a successful match. 179template <typename T> 180class BindingsMatcher : public ast_matchers::internal::MatcherInterface<T> { 181 ast_matchers::BoundNodes Nodes; 182 const ast_matchers::internal::Matcher<T> InnerMatcher; 183 184public: 185 explicit BindingsMatcher(ast_matchers::BoundNodes Nodes, 186 ast_matchers::internal::Matcher<T> InnerMatcher) 187 : Nodes(std::move(Nodes)), InnerMatcher(std::move(InnerMatcher)) {} 188 189 bool matches( 190 const T &Node, ast_matchers::internal::ASTMatchFinder *Finder, 191 ast_matchers::internal::BoundNodesTreeBuilder *Builder) const override { 192 ast_matchers::internal::BoundNodesTreeBuilder Result(*Builder); 193 for (const auto &N : Nodes.getMap()) 194 Result.setBinding(N.first, N.second); 195 if (InnerMatcher.matches(Node, Finder, &Result)) { 196 *Builder = std::move(Result); 197 return true; 198 } 199 return false; 200 } 201}; 202 203/// Matches nodes of type T that have at least one descendant node for which the 204/// given inner matcher matches. Will match for each descendant node that 205/// matches. Based on ForEachDescendantMatcher, but takes a dynamic matcher, 206/// instead of a static one, because it is used by RewriteRule, which carries 207/// (only top-level) dynamic matchers. 208template <typename T> 209class DynamicForEachDescendantMatcher 210 : public ast_matchers::internal::MatcherInterface<T> { 211 const DynTypedMatcher DescendantMatcher; 212 213public: 214 explicit DynamicForEachDescendantMatcher(DynTypedMatcher DescendantMatcher) 215 : DescendantMatcher(std::move(DescendantMatcher)) {} 216 217 bool matches( 218 const T &Node, ast_matchers::internal::ASTMatchFinder *Finder, 219 ast_matchers::internal::BoundNodesTreeBuilder *Builder) const override { 220 return Finder->matchesDescendantOf( 221 Node, this->DescendantMatcher, Builder, 222 ast_matchers::internal::ASTMatchFinder::BK_All); 223 } 224}; 225 226template <typename T> 227ast_matchers::internal::Matcher<T> 228forEachDescendantDynamically(ast_matchers::BoundNodes Nodes, 229 DynTypedMatcher M) { 230 return ast_matchers::internal::makeMatcher(new BindingsMatcher<T>( 231 std::move(Nodes), 232 ast_matchers::internal::makeMatcher( 233 new DynamicForEachDescendantMatcher<T>(std::move(M))))); 234} 235 236class ApplyRuleCallback : public MatchFinder::MatchCallback { 237public: 238 ApplyRuleCallback(RewriteRule Rule) : Rule(std::move(Rule)) {} 239 240 template <typename T> 241 void registerMatchers(const ast_matchers::BoundNodes &Nodes, 242 MatchFinder *MF) { 243 for (auto &Matcher : transformer::detail::buildMatchers(Rule)) 244 MF->addMatcher(forEachDescendantDynamically<T>(Nodes, Matcher), this); 245 } 246 247 void run(const MatchFinder::MatchResult &Result) override { 248 if (!Edits) 249 return; 250 transformer::RewriteRule::Case Case = 251 transformer::detail::findSelectedCase(Result, Rule); 252 auto Transformations = Case.Edits(Result); 253 if (!Transformations) { 254 Edits = Transformations.takeError(); 255 return; 256 } 257 Edits->append(Transformations->begin(), Transformations->end()); 258 } 259 260 RewriteRule Rule; 261 262 // Initialize to a non-error state. 263 Expected<SmallVector<Edit, 1>> Edits = SmallVector<Edit, 1>(); 264}; 265} // namespace 266 267template <typename T> 268llvm::Expected<SmallVector<clang::transformer::Edit, 1>> 269rewriteDescendantsImpl(const T &Node, RewriteRule Rule, 270 const MatchResult &Result) { 271 ApplyRuleCallback Callback(std::move(Rule)); 272 MatchFinder Finder; 273 Callback.registerMatchers<T>(Result.Nodes, &Finder); 274 Finder.match(Node, *Result.Context); 275 return std::move(Callback.Edits); 276} 277 278llvm::Expected<SmallVector<clang::transformer::Edit, 1>> 279transformer::detail::rewriteDescendants(const Decl &Node, RewriteRule Rule, 280 const MatchResult &Result) { 281 return rewriteDescendantsImpl(Node, std::move(Rule), Result); 282} 283 284llvm::Expected<SmallVector<clang::transformer::Edit, 1>> 285transformer::detail::rewriteDescendants(const Stmt &Node, RewriteRule Rule, 286 const MatchResult &Result) { 287 return rewriteDescendantsImpl(Node, std::move(Rule), Result); 288} 289 290llvm::Expected<SmallVector<clang::transformer::Edit, 1>> 291transformer::detail::rewriteDescendants(const TypeLoc &Node, RewriteRule Rule, 292 const MatchResult &Result) { 293 return rewriteDescendantsImpl(Node, std::move(Rule), Result); 294} 295 296llvm::Expected<SmallVector<clang::transformer::Edit, 1>> 297transformer::detail::rewriteDescendants(const DynTypedNode &DNode, 298 RewriteRule Rule, 299 const MatchResult &Result) { 300 if (const auto *Node = DNode.get<Decl>()) 301 return rewriteDescendantsImpl(*Node, std::move(Rule), Result); 302 if (const auto *Node = DNode.get<Stmt>()) 303 return rewriteDescendantsImpl(*Node, std::move(Rule), Result); 304 if (const auto *Node = DNode.get<TypeLoc>()) 305 return rewriteDescendantsImpl(*Node, std::move(Rule), Result); 306 307 return llvm::make_error<llvm::StringError>( 308 llvm::errc::invalid_argument, 309 "type unsupported for recursive rewriting, Kind=" + 310 DNode.getNodeKind().asStringRef()); 311} 312 313EditGenerator transformer::rewriteDescendants(std::string NodeId, 314 RewriteRule Rule) { 315 return [NodeId = std::move(NodeId), 316 Rule = std::move(Rule)](const MatchResult &Result) 317 -> llvm::Expected<SmallVector<clang::transformer::Edit, 1>> { 318 const ast_matchers::BoundNodes::IDToNodeMap &NodesMap = 319 Result.Nodes.getMap(); 320 auto It = NodesMap.find(NodeId); 321 if (It == NodesMap.end()) 322 return llvm::make_error<llvm::StringError>(llvm::errc::invalid_argument, 323 "ID not bound: " + NodeId); 324 return detail::rewriteDescendants(It->second, std::move(Rule), Result); 325 }; 326} 327 328void transformer::addInclude(RewriteRule &Rule, StringRef Header, 329 IncludeFormat Format) { 330 for (auto &Case : Rule.Cases) 331 Case.Edits = flatten(std::move(Case.Edits), addInclude(Header, Format)); 332} 333 334#ifndef NDEBUG 335// Filters for supported matcher kinds. FIXME: Explicitly list the allowed kinds 336// (all node matcher types except for `QualType` and `Type`), rather than just 337// banning `QualType` and `Type`. 338static bool hasValidKind(const DynTypedMatcher &M) { 339 return !M.canConvertTo<QualType>(); 340} 341#endif 342 343// Binds each rule's matcher to a unique (and deterministic) tag based on 344// `TagBase` and the id paired with the case. All of the returned matchers have 345// their traversal kind explicitly set, either based on a pre-set kind or to the 346// provided `DefaultTraversalKind`. 347static std::vector<DynTypedMatcher> taggedMatchers( 348 StringRef TagBase, 349 const SmallVectorImpl<std::pair<size_t, RewriteRule::Case>> &Cases, 350 TraversalKind DefaultTraversalKind) { 351 std::vector<DynTypedMatcher> Matchers; 352 Matchers.reserve(Cases.size()); 353 for (const auto &Case : Cases) { 354 std::string Tag = (TagBase + Twine(Case.first)).str(); 355 // HACK: Many matchers are not bindable, so ensure that tryBind will work. 356 DynTypedMatcher BoundMatcher(Case.second.Matcher); 357 BoundMatcher.setAllowBind(true); 358 auto M = *BoundMatcher.tryBind(Tag); 359 Matchers.push_back(!M.getTraversalKind() 360 ? M.withTraversalKind(DefaultTraversalKind) 361 : std::move(M)); 362 } 363 return Matchers; 364} 365 366// Simply gathers the contents of the various rules into a single rule. The 367// actual work to combine these into an ordered choice is deferred to matcher 368// registration. 369RewriteRule transformer::applyFirst(ArrayRef<RewriteRule> Rules) { 370 RewriteRule R; 371 for (auto &Rule : Rules) 372 R.Cases.append(Rule.Cases.begin(), Rule.Cases.end()); 373 return R; 374} 375 376std::vector<DynTypedMatcher> 377transformer::detail::buildMatchers(const RewriteRule &Rule) { 378 // Map the cases into buckets of matchers -- one for each "root" AST kind, 379 // which guarantees that they can be combined in a single anyOf matcher. Each 380 // case is paired with an identifying number that is converted to a string id 381 // in `taggedMatchers`. 382 std::map<ASTNodeKind, SmallVector<std::pair<size_t, RewriteRule::Case>, 1>> 383 Buckets; 384 const SmallVectorImpl<RewriteRule::Case> &Cases = Rule.Cases; 385 for (int I = 0, N = Cases.size(); I < N; ++I) { 386 assert(hasValidKind(Cases[I].Matcher) && 387 "Matcher must be non-(Qual)Type node matcher"); 388 Buckets[Cases[I].Matcher.getSupportedKind()].emplace_back(I, Cases[I]); 389 } 390 391 // Each anyOf explicitly controls the traversal kind. The anyOf itself is set 392 // to `TK_AsIs` to ensure no nodes are skipped, thereby deferring to the kind 393 // of the branches. Then, each branch is either left as is, if the kind is 394 // already set, or explicitly set to `TK_AsIs`. We choose this setting because 395 // it is the default interpretation of matchers. 396 std::vector<DynTypedMatcher> Matchers; 397 for (const auto &Bucket : Buckets) { 398 DynTypedMatcher M = DynTypedMatcher::constructVariadic( 399 DynTypedMatcher::VO_AnyOf, Bucket.first, 400 taggedMatchers("Tag", Bucket.second, TK_AsIs)); 401 M.setAllowBind(true); 402 // `tryBind` is guaranteed to succeed, because `AllowBind` was set to true. 403 Matchers.push_back(M.tryBind(RootID)->withTraversalKind(TK_AsIs)); 404 } 405 return Matchers; 406} 407 408DynTypedMatcher transformer::detail::buildMatcher(const RewriteRule &Rule) { 409 std::vector<DynTypedMatcher> Ms = buildMatchers(Rule); 410 assert(Ms.size() == 1 && "Cases must have compatible matchers."); 411 return Ms[0]; 412} 413 414SourceLocation transformer::detail::getRuleMatchLoc(const MatchResult &Result) { 415 auto &NodesMap = Result.Nodes.getMap(); 416 auto Root = NodesMap.find(RootID); 417 assert(Root != NodesMap.end() && "Transformation failed: missing root node."); 418 llvm::Optional<CharSourceRange> RootRange = tooling::getRangeForEdit( 419 CharSourceRange::getTokenRange(Root->second.getSourceRange()), 420 *Result.Context); 421 if (RootRange) 422 return RootRange->getBegin(); 423 // The match doesn't have a coherent range, so fall back to the expansion 424 // location as the "beginning" of the match. 425 return Result.SourceManager->getExpansionLoc( 426 Root->second.getSourceRange().getBegin()); 427} 428 429// Finds the case that was "selected" -- that is, whose matcher triggered the 430// `MatchResult`. 431const RewriteRule::Case & 432transformer::detail::findSelectedCase(const MatchResult &Result, 433 const RewriteRule &Rule) { 434 if (Rule.Cases.size() == 1) 435 return Rule.Cases[0]; 436 437 auto &NodesMap = Result.Nodes.getMap(); 438 for (size_t i = 0, N = Rule.Cases.size(); i < N; ++i) { 439 std::string Tag = ("Tag" + Twine(i)).str(); 440 if (NodesMap.find(Tag) != NodesMap.end()) 441 return Rule.Cases[i]; 442 } 443 llvm_unreachable("No tag found for this rule."); 444} 445 446const llvm::StringRef RewriteRule::RootID = ::clang::transformer::RootID; 447