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
25using namespace clang;
26using namespace transformer;
27
28using ast_matchers::MatchFinder;
29using ast_matchers::internal::DynTypedMatcher;
30
31using MatchResult = MatchFinder::MatchResult;
32
33const char transformer::RootID[] = "___root___";
34
35static Expected<SmallVector<transformer::Edit, 1>>
36translateEdits(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
69EditGenerator transformer::editList(SmallVector<ASTEdit, 1> Edits) {
70  return [Edits = std::move(Edits)](const MatchResult &Result) {
71    return translateEdits(Result, Edits);
72  };
73}
74
75EditGenerator transformer::edit(ASTEdit Edit) {
76  return [Edit = std::move(Edit)](const MatchResult &Result) {
77    return translateEdits(Result, {Edit});
78  };
79}
80
81EditGenerator 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
99EditGenerator
100transformer::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
117ASTEdit 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
124namespace {
125/// A \c TextGenerator that always returns a fixed string.
126class SimpleTextGenerator : public MatchComputation<std::string> {
127  std::string S;
128
129public:
130  SimpleTextGenerator(std::string S) : S(std::move(S)) {}
131  llvm::Error eval(const ast_matchers::MatchFinder::MatchResult &,
132                   std::string *Result) const override {
133    Result->append(S);
134    return llvm::Error::success();
135  }
136  std::string toString() const override {
137    return (llvm::Twine("text(\"") + S + "\")").str();
138  }
139};
140} // namespace
141
142static TextGenerator makeText(std::string S) {
143  return std::make_shared<SimpleTextGenerator>(std::move(S));
144}
145
146ASTEdit transformer::remove(RangeSelector S) {
147  return change(std::move(S), makeText(""));
148}
149
150static 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
160ASTEdit 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
169RewriteRule 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
175namespace {
176
177/// Unconditionally binds the given node set before trying `InnerMatcher` and
178/// keeps the bound nodes on a successful match.
179template <typename T>
180class BindingsMatcher : public ast_matchers::internal::MatcherInterface<T> {
181  ast_matchers::BoundNodes Nodes;
182  const ast_matchers::internal::Matcher<T> InnerMatcher;
183
184public:
185  explicit BindingsMatcher(ast_matchers::BoundNodes Nodes,
186                           ast_matchers::internal::Matcher<T> InnerMatcher)
187      : Nodes(std::move(Nodes)), InnerMatcher(std::move(InnerMatcher)) {}
188
189  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.
208template <typename T>
209class DynamicForEachDescendantMatcher
210    : public ast_matchers::internal::MatcherInterface<T> {
211  const DynTypedMatcher DescendantMatcher;
212
213public:
214  explicit DynamicForEachDescendantMatcher(DynTypedMatcher DescendantMatcher)
215      : DescendantMatcher(std::move(DescendantMatcher)) {}
216
217  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
226template <typename T>
227ast_matchers::internal::Matcher<T>
228forEachDescendantDynamically(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
236class ApplyRuleCallback : public MatchFinder::MatchCallback {
237public:
238  ApplyRuleCallback(RewriteRule Rule) : Rule(std::move(Rule)) {}
239
240  template <typename T>
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
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
267template <typename T>
268llvm::Expected<SmallVector<clang::transformer::Edit, 1>>
269rewriteDescendantsImpl(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
278llvm::Expected<SmallVector<clang::transformer::Edit, 1>>
279transformer::detail::rewriteDescendants(const Decl &Node, RewriteRule Rule,
280                                        const MatchResult &Result) {
281  return rewriteDescendantsImpl(Node, std::move(Rule), Result);
282}
283
284llvm::Expected<SmallVector<clang::transformer::Edit, 1>>
285transformer::detail::rewriteDescendants(const Stmt &Node, RewriteRule Rule,
286                                        const MatchResult &Result) {
287  return rewriteDescendantsImpl(Node, std::move(Rule), Result);
288}
289
290llvm::Expected<SmallVector<clang::transformer::Edit, 1>>
291transformer::detail::rewriteDescendants(const TypeLoc &Node, RewriteRule Rule,
292                                        const MatchResult &Result) {
293  return rewriteDescendantsImpl(Node, std::move(Rule), Result);
294}
295
296llvm::Expected<SmallVector<clang::transformer::Edit, 1>>
297transformer::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
313EditGenerator 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
328void 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`.
338static 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`.
347static 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.
369RewriteRule 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
376std::vector<DynTypedMatcher>
377transformer::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
408DynTypedMatcher 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
414SourceLocation 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`.
431const RewriteRule::Case &
432transformer::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
446const llvm::StringRef RewriteRule::RootID = ::clang::transformer::RootID;
447