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
24using namespace clang;
25using namespace transformer;
26
27using ast_matchers::MatchFinder;
28using ast_matchers::internal::DynTypedMatcher;
29
30using MatchResult = MatchFinder::MatchResult;
31
32const char transformer::RootID[] = "___root___";
33
34static Expected<SmallVector<transformer::Edit, 1>>
35translateEdits(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(EditRange: *Range, Context: *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(R: 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(R: 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(Elt: std::move(T));
74 }
75 return Edits;
76}
77
78EditGenerator transformer::editList(SmallVector<ASTEdit, 1> Edits) {
79 return [Edits = std::move(Edits)](const MatchResult &Result) {
80 return translateEdits(Result, ASTEdits: Edits);
81 };
82}
83
84EditGenerator transformer::edit(ASTEdit Edit) {
85 return [Edit = std::move(Edit)](const MatchResult &Result) {
86 return translateEdits(Result, ASTEdits: {Edit});
87 };
88}
89
90EditGenerator 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(Loc: Range->getBegin());
100 Edit E;
101 // Implicitly, leave `E.Replacement` as the empty string.
102 E.Kind = EditKind::Range;
103 E.Range = CharSourceRange::getCharRange(B: Begin, E: Begin);
104 return SmallVector<Edit, 1>{E};
105 };
106}
107
108EditGenerator
109transformer::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(in_start: Edits->begin(), in_end: Edits->end());
121 }
122 return AllEdits;
123 };
124}
125
126ASTEdit 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
133ASTEdit transformer::note(RangeSelector Anchor, TextGenerator Note) {
134 ASTEdit E;
135 E.TargetRange = transformer::before(Selector: Anchor);
136 E.Note = std::move(Note);
137 return E;
138}
139
140namespace {
141/// A \c TextGenerator that always returns a fixed string.
142class SimpleTextGenerator : public MatchComputation<std::string> {
143 std::string S;
144
145public:
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(str: 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
158static TextGenerator makeText(std::string S) {
159 return std::make_shared<SimpleTextGenerator>(args: std::move(S));
160}
161
162ASTEdit transformer::remove(RangeSelector S) {
163 return change(Target: std::move(S), Replacement: makeText(S: ""));
164}
165
166static 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
176ASTEdit 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(S: formatHeaderPath(Header, Format));
182 return E;
183}
184
185EditGenerator
186transformer::detail::makeEditGenerator(llvm::SmallVector<ASTEdit, 1> Edits) {
187 return editList(Edits: std::move(Edits));
188}
189
190EditGenerator transformer::detail::makeEditGenerator(ASTEdit Edit) {
191 return edit(Edit: std::move(Edit));
192}
193
194RewriteRule transformer::detail::makeRule(DynTypedMatcher M,
195 EditGenerator Edits) {
196 RewriteRule R;
197 R.Cases = {{.Matcher: std::move(M), .Edits: std::move(Edits)}};
198 return R;
199}
200
201RewriteRule transformer::makeRule(ast_matchers::internal::DynTypedMatcher M,
202 std::initializer_list<ASTEdit> Edits) {
203 return detail::makeRule(M: std::move(M),
204 Edits: detail::makeEditGenerator(Edits: std::move(Edits)));
205}
206
207namespace {
208
209/// Unconditionally binds the given node set before trying `InnerMatcher` and
210/// keeps the bound nodes on a successful match.
211template <typename T>
212class BindingsMatcher : public ast_matchers::internal::MatcherInterface<T> {
213 ast_matchers::BoundNodes Nodes;
214 const ast_matchers::internal::Matcher<T> InnerMatcher;
215
216public:
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(Id: N.first, DynNode: 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.
240template <typename T>
241class DynamicForEachDescendantMatcher
242 : public ast_matchers::internal::MatcherInterface<T> {
243 const DynTypedMatcher DescendantMatcher;
244
245public:
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
258template <typename T>
259ast_matchers::internal::Matcher<T>
260forEachDescendantDynamically(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
268class ApplyRuleCallback : public MatchFinder::MatchCallback {
269public:
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(in_start: Transformations->begin(), in_end: 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
298template <typename T>
299llvm::Expected<SmallVector<clang::transformer::Edit, 1>>
300rewriteDescendantsImpl(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
309llvm::Expected<SmallVector<clang::transformer::Edit, 1>>
310transformer::detail::rewriteDescendants(const Decl &Node, RewriteRule Rule,
311 const MatchResult &Result) {
312 return rewriteDescendantsImpl(Node, Rule: std::move(Rule), Result);
313}
314
315llvm::Expected<SmallVector<clang::transformer::Edit, 1>>
316transformer::detail::rewriteDescendants(const Stmt &Node, RewriteRule Rule,
317 const MatchResult &Result) {
318 return rewriteDescendantsImpl(Node, Rule: std::move(Rule), Result);
319}
320
321llvm::Expected<SmallVector<clang::transformer::Edit, 1>>
322transformer::detail::rewriteDescendants(const TypeLoc &Node, RewriteRule Rule,
323 const MatchResult &Result) {
324 return rewriteDescendantsImpl(Node, Rule: std::move(Rule), Result);
325}
326
327llvm::Expected<SmallVector<clang::transformer::Edit, 1>>
328transformer::detail::rewriteDescendants(const DynTypedNode &DNode,
329 RewriteRule Rule,
330 const MatchResult &Result) {
331 if (const auto *Node = DNode.get<Decl>())
332 return rewriteDescendantsImpl(Node: *Node, Rule: std::move(Rule), Result);
333 if (const auto *Node = DNode.get<Stmt>())
334 return rewriteDescendantsImpl(Node: *Node, Rule: std::move(Rule), Result);
335 if (const auto *Node = DNode.get<TypeLoc>())
336 return rewriteDescendantsImpl(Node: *Node, Rule: std::move(Rule), Result);
337
338 return llvm::make_error<llvm::StringError>(
339 Args: llvm::errc::invalid_argument,
340 Args: "type unsupported for recursive rewriting, Kind=" +
341 DNode.getNodeKind().asStringRef());
342}
343
344EditGenerator 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(x: NodeId);
352 if (It == NodesMap.end())
353 return llvm::make_error<llvm::StringError>(Args: llvm::errc::invalid_argument,
354 Args: "ID not bound: " + NodeId);
355 return detail::rewriteDescendants(It->second, std::move(Rule), Result);
356 };
357}
358
359void transformer::addInclude(RewriteRuleBase &Rule, StringRef Header,
360 IncludeFormat Format) {
361 for (auto &Case : Rule.Cases)
362 Case.Edits = flatten(Edits: std::move(Case.Edits), 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`.
369static 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`.
378static 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(n: 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(ID: Tag);
390 Matchers.push_back(x: !M.getTraversalKind()
391 ? M.withTraversalKind(TK: 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.
400template <>
401RewriteRuleWith<void>
402transformer::applyFirst(ArrayRef<RewriteRuleWith<void>> Rules) {
403 RewriteRule R;
404 for (auto &Rule : Rules)
405 R.Cases.append(in_start: Rule.Cases.begin(), in_end: Rule.Cases.end());
406 return R;
407}
408
409std::vector<DynTypedMatcher>
410transformer::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(Args&: I, Args: 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 Op: DynTypedMatcher::VO_AnyOf, SupportedKind: Bucket.first,
434 InnerMatchers: taggedMatchers(TagBase: "Tag", Cases: Bucket.second, DefaultTraversalKind: TK_AsIs));
435 M.setAllowBind(true);
436 // `tryBind` is guaranteed to succeed, because `AllowBind` was set to true.
437 Matchers.push_back(x: M.tryBind(ID: RootID)->withTraversalKind(TK: TK_AsIs));
438 }
439 return Matchers;
440}
441
442DynTypedMatcher 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
448SourceLocation transformer::detail::getRuleMatchLoc(const MatchResult &Result) {
449 auto &NodesMap = Result.Nodes.getMap();
450 auto Root = NodesMap.find(x: 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 Loc: Root->second.getSourceRange().getBegin());
461}
462
463// Finds the case that was "selected" -- that is, whose matcher triggered the
464// `MatchResult`.
465size_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(x: Tag) != NodesMap.end())
474 return i;
475 }
476 llvm_unreachable("No tag found for this rule.");
477}
478

source code of clang/lib/Tooling/Transformer/RewriteRule.cpp