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>>
translateEdits(const MatchResult & Result,ArrayRef<ASTEdit> ASTEdits)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
editList(SmallVector<ASTEdit,1> Edits)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
edit(ASTEdit Edit)84 EditGenerator transformer::edit(ASTEdit Edit) {
85 return [Edit = std::move(Edit)](const MatchResult &Result) {
86 return translateEdits(Result, {Edit});
87 };
88 }
89
noopEdit(RangeSelector Anchor)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
flattenVector(SmallVector<EditGenerator,2> Generators)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
changeTo(RangeSelector Target,TextGenerator Replacement)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
note(RangeSelector Anchor,TextGenerator Note)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:
SimpleTextGenerator(std::string S)146 SimpleTextGenerator(std::string S) : S(std::move(S)) {}
eval(const ast_matchers::MatchFinder::MatchResult &,std::string * Result) const147 llvm::Error eval(const ast_matchers::MatchFinder::MatchResult &,
148 std::string *Result) const override {
149 Result->append(S);
150 return llvm::Error::success();
151 }
toString() const152 std::string toString() const override {
153 return (llvm::Twine("text(\"") + S + "\")").str();
154 }
155 };
156 } // namespace
157
makeText(std::string S)158 static TextGenerator makeText(std::string S) {
159 return std::make_shared<SimpleTextGenerator>(std::move(S));
160 }
161
remove(RangeSelector S)162 ASTEdit transformer::remove(RangeSelector S) {
163 return change(std::move(S), makeText(""));
164 }
165
formatHeaderPath(StringRef Header,IncludeFormat Format)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
addInclude(RangeSelector Target,StringRef Header,IncludeFormat Format)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
makeEditGenerator(llvm::SmallVector<ASTEdit,1> Edits)186 transformer::detail::makeEditGenerator(llvm::SmallVector<ASTEdit, 1> Edits) {
187 return editList(std::move(Edits));
188 }
189
makeEditGenerator(ASTEdit Edit)190 EditGenerator transformer::detail::makeEditGenerator(ASTEdit Edit) {
191 return edit(std::move(Edit));
192 }
193
makeRule(DynTypedMatcher M,EditGenerator Edits)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
makeRule(ast_matchers::internal::DynTypedMatcher M,std::initializer_list<ASTEdit> Edits)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:
BindingsMatcher(ast_matchers::BoundNodes Nodes,ast_matchers::internal::Matcher<T> InnerMatcher)217 explicit BindingsMatcher(ast_matchers::BoundNodes Nodes,
218 ast_matchers::internal::Matcher<T> InnerMatcher)
219 : Nodes(std::move(Nodes)), InnerMatcher(std::move(InnerMatcher)) {}
220
matches(const T & Node,ast_matchers::internal::ASTMatchFinder * Finder,ast_matchers::internal::BoundNodesTreeBuilder * Builder) const221 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:
DynamicForEachDescendantMatcher(DynTypedMatcher DescendantMatcher)246 explicit DynamicForEachDescendantMatcher(DynTypedMatcher DescendantMatcher)
247 : DescendantMatcher(std::move(DescendantMatcher)) {}
248
matches(const T & Node,ast_matchers::internal::ASTMatchFinder * Finder,ast_matchers::internal::BoundNodesTreeBuilder * Builder) const249 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>
forEachDescendantDynamically(ast_matchers::BoundNodes Nodes,DynTypedMatcher M)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:
ApplyRuleCallback(RewriteRule Rule)270 ApplyRuleCallback(RewriteRule Rule) : Rule(std::move(Rule)) {}
271
272 template <typename T>
registerMatchers(const ast_matchers::BoundNodes & Nodes,MatchFinder * MF)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
run(const MatchFinder::MatchResult & Result)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>>
rewriteDescendantsImpl(const T & Node,RewriteRule Rule,const MatchResult & Result)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>>
rewriteDescendants(const Decl & Node,RewriteRule Rule,const MatchResult & Result)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>>
rewriteDescendants(const Stmt & Node,RewriteRule Rule,const MatchResult & Result)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>>
rewriteDescendants(const TypeLoc & Node,RewriteRule Rule,const MatchResult & Result)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>>
rewriteDescendants(const DynTypedNode & DNode,RewriteRule Rule,const MatchResult & Result)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
rewriteDescendants(std::string NodeId,RewriteRule Rule)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
addInclude(RewriteRuleBase & Rule,StringRef Header,IncludeFormat Format)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`.
hasValidKind(const DynTypedMatcher & M)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`.
taggedMatchers(StringRef TagBase,const SmallVectorImpl<std::pair<size_t,RewriteRule::Case>> & Cases,TraversalKind 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>
applyFirst(ArrayRef<RewriteRuleWith<void>> Rules)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>
buildMatchers(const RewriteRuleBase & Rule)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
buildMatcher(const RewriteRuleBase & Rule)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
getRuleMatchLoc(const MatchResult & Result)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`.
findSelectedCase(const MatchResult & Result,const RewriteRuleBase & Rule)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 }
478