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