clang/lib/Tooling/Transformer/RewriteRule.cpp

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