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