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/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(EditRange: *Range, Context: *Result.Context);
42 // FIXME: let user specify whether to treat this case as an error or ignore
43 // it as is currently done. This behavior is problematic in that it hides
44 // failures from bad ranges. Also, the behavior here differs from
45 // `flatten`. Here, we abort (without error), whereas flatten, if it hits an
46 // empty list, does not abort. As a result, `editList({A,B})` is not
47 // 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(R: 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(R: 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(Elt: 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, ASTEdits: Edits);
80 };
81}
82
83EditGenerator transformer::edit(ASTEdit Edit) {
84 return [Edit = std::move(Edit)](const MatchResult &Result) {
85 return translateEdits(Result, ASTEdits: {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 a
96 // "real" source location.
97 SourceLocation Begin =
98 Result.SourceManager->getSpellingLoc(Loc: Range->getBegin());
99 Edit E;
100 // Implicitly, leave `E.Replacement` as the empty string.
101 E.Kind = EditKind::Range;
102 E.Range = CharSourceRange::getCharRange(B: Begin, E: Begin);
103 return SmallVector<Edit, 1>{E};
104 };
105}
106
107EditGenerator
108transformer::flattenVector(SmallVector<EditGenerator, 2> Generators) {
109 if (Generators.size() == 1)
110 return std::move(Generators[0]);
111 return
112 [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(in_start: Edits->begin(), in_end: 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(Selector: 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(str: S);
149 return llvm::Error::success();
150 }
151 std::string toString() const override {
152 return (llvm::Twine("text(\"") + S + "\")").str();
153 }
154};
155} // namespace
156
157static TextGenerator makeText(std::string S) {
158 return std::make_shared<SimpleTextGenerator>(args: std::move(S));
159}
160
161ASTEdit transformer::remove(RangeSelector S) {
162 return change(Target: std::move(S), Replacement: makeText(S: ""));
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(S: formatHeaderPath(Header, Format));
181 return E;
182}
183
184EditGenerator
185transformer::detail::makeEditGenerator(llvm::SmallVector<ASTEdit, 1> Edits) {
186 return editList(Edits: std::move(Edits));
187}
188
189EditGenerator transformer::detail::makeEditGenerator(ASTEdit Edit) {
190 return edit(Edit: std::move(Edit));
191}
192
193RewriteRule transformer::detail::makeRule(DynTypedMatcher M,
194 EditGenerator Edits) {
195 RewriteRule R;
196 R.Cases = {{.Matcher: std::move(M), .Edits: 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(M: std::move(M),
203 Edits: detail::makeEditGenerator(Edits: std::move(Edits)));
204}
205
206namespace {
207
208/// Unconditionally binds the given node set before trying `InnerMatcher` and
209/// 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(Id: N.first, DynNode: 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 the
235/// given inner matcher matches. Will match for each descendant node that
236/// matches. Based on ForEachDescendantMatcher, but takes a dynamic matcher,
237/// instead of a static one, because it is used by RewriteRule, which carries
238/// (only top-level) dynamic matchers.
239template <typename T>
240class DynamicForEachDescendantMatcher
241 : 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::makeMatcher(new BindingsMatcher<T>(
262 std::move(Nodes),
263 ast_matchers::internal::makeMatcher(
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(in_start: Transformations->begin(), in_end: 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} // namespace
296
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, Rule: 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, Rule: 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, Rule: 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: *Node, Rule: std::move(Rule), Result);
332 if (const auto *Node = DNode.get<Stmt>())
333 return rewriteDescendantsImpl(Node: *Node, Rule: std::move(Rule), Result);
334 if (const auto *Node = DNode.get<TypeLoc>())
335 return rewriteDescendantsImpl(Node: *Node, Rule: std::move(Rule), Result);
336
337 return llvm::make_error<llvm::StringError>(
338 Args: llvm::errc::invalid_argument,
339 Args: "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(x: NodeId);
351 if (It == NodesMap.end())
352 return llvm::make_error<llvm::StringError>(Args: llvm::errc::invalid_argument,
353 Args: "ID not bound: " + NodeId);
354 return detail::rewriteDescendants(DNode: It->second, Rule: 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(Edits: std::move(Case.Edits), Edits: addInclude(Header, Format));
362}
363
364#ifndef NDEBUG
365// Filters for supported matcher kinds. FIXME: Explicitly list the allowed kinds
366// (all node matcher types except for `QualType` and `Type`), rather than just
367// banning `QualType` and `Type`.
368static bool hasValidKind(const DynTypedMatcher &M) {
369 return !M.canConvertTo<QualType>();
370}
371#endif
372
373// Binds each rule's matcher to a unique (and deterministic) tag based on
374// `TagBase` and the id paired with the case. All of the returned matchers have
375// their traversal kind explicitly set, either based on a pre-set kind or to the
376// 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(n: 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(ID: Tag);
389 Matchers.push_back(x: !M.getTraversalKind()
390 ? M.withTraversalKind(TK: DefaultTraversalKind)
391 : std::move(M));
392 }
393 return Matchers;
394}
395
396// Simply gathers the contents of the various rules into a single rule. The
397// actual work to combine these into an ordered choice is deferred to matcher
398// registration.
399template <>
400RewriteRuleWith<void>
401transformer::applyFirst(ArrayRef<RewriteRuleWith<void>> Rules) {
402 RewriteRule R;
403 for (auto &Rule : Rules)
404 R.Cases.append(in_start: Rule.Cases.begin(), in_end: 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. Each
412 // case is paired with an identifying number that is converted to a string id
413 // 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(Args&: I, Args: Cases[I]);
422 }
423
424 // Each anyOf explicitly controls the traversal kind. The anyOf itself is set
425 // to `TK_AsIs` to ensure no nodes are skipped, thereby deferring to the kind
426 // of the branches. Then, each branch is either left as is, if the kind is
427 // already set, or explicitly set to `TK_AsIs`. We choose this setting because
428 // it is the default interpretation of matchers.
429 std::vector<DynTypedMatcher> Matchers;
430 for (const auto &Bucket : Buckets) {
431 DynTypedMatcher M = DynTypedMatcher::constructVariadic(
432 Op: DynTypedMatcher::VO_AnyOf, SupportedKind: Bucket.first,
433 InnerMatchers: taggedMatchers(TagBase: "Tag", Cases: Bucket.second, DefaultTraversalKind: TK_AsIs));
434 M.setAllowBind(true);
435 // `tryBind` is guaranteed to succeed, because `AllowBind` was set to true.
436 Matchers.push_back(x: M.tryBind(ID: RootID)->withTraversalKind(TK: 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(x: RootID);
450 assert(Root != NodesMap.end() && "Transformation failed: missing root node.");
451 std::optional<CharSourceRange> RootRange = tooling::getFileRangeForEdit(
452 EditRange: CharSourceRange::getTokenRange(R: Root->second.getSourceRange()),
453 Context: *Result.Context);
454 if (RootRange)
455 return RootRange->getBegin();
456 // The match doesn't have a coherent range, so fall back to the expansion
457 // location as the "beginning" of the match.
458 return Result.SourceManager->getExpansionLoc(
459 Loc: Root->second.getSourceRange().getBegin());
460}
461
462// Finds the case that was "selected" -- that is, whose matcher triggered the
463// `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(x: Tag) != NodesMap.end())
473 return i;
474 }
475 llvm_unreachable("No tag found for this rule.");
476}
477