clang  12.0.0git
RewriteRule.cpp
Go to the documentation of this file.
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 
11 #include "clang/AST/Stmt.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 
29 using ast_matchers::internal::DynTypedMatcher;
30 
32 
33 const char transformer::RootID[] = "___root___";
34 
36 translateEdits(const MatchResult &Result, ArrayRef<ASTEdit> ASTEdits) {
38  for (const auto &E : ASTEdits) {
39  Expected<CharSourceRange> Range = E.TargetRange(Result);
40  if (!Range)
41  return Range.takeError();
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.
46  if (!EditRange)
47  return SmallVector<Edit, 0>();
48  auto Replacement = E.Replacement->eval(Result);
49  if (!Replacement)
50  return Replacement.takeError();
51  auto Metadata = E.Metadata(Result);
52  if (!Metadata)
53  return Metadata.takeError();
55  T.Kind = E.Kind;
56  T.Range = *EditRange;
57  T.Replacement = std::move(*Replacement);
58  T.Metadata = std::move(*Metadata);
59  Edits.push_back(std::move(T));
60  }
61  return Edits;
62 }
63 
65  return [Edits = std::move(Edits)](const MatchResult &Result) {
66  return translateEdits(Result, Edits);
67  };
68 }
69 
71  return [Edit = std::move(Edit)](const MatchResult &Result) {
72  return translateEdits(Result, {Edit});
73  };
74 }
75 
77  return [Anchor = std::move(Anchor)](const MatchResult &Result)
79  Expected<CharSourceRange> Range = Anchor(Result);
80  if (!Range)
81  return Range.takeError();
82  // In case the range is inside a macro expansion, map the location back to a
83  // "real" source location.
85  Result.SourceManager->getSpellingLoc(Range->getBegin());
86  Edit E;
87  // Implicitly, leave `E.Replacement` as the empty string.
90  return SmallVector<Edit, 1>{E};
91  };
92 }
93 
96  if (Generators.size() == 1)
97  return std::move(Generators[0]);
98  return
99  [Gs = std::move(Generators)](
100  const MatchResult &Result) -> llvm::Expected<SmallVector<Edit, 1>> {
101  SmallVector<Edit, 1> AllEdits;
102  for (const auto &G : Gs) {
103  llvm::Expected<SmallVector<Edit, 1>> Edits = G(Result);
104  if (!Edits)
105  return Edits.takeError();
106  AllEdits.append(Edits->begin(), Edits->end());
107  }
108  return AllEdits;
109  };
110 }
111 
113  ASTEdit E;
114  E.TargetRange = std::move(Target);
115  E.Replacement = std::move(Replacement);
116  return E;
117 }
118 
119 namespace {
120 /// A \c TextGenerator that always returns a fixed string.
121 class SimpleTextGenerator : public MatchComputation<std::string> {
122  std::string S;
123 
124 public:
125  SimpleTextGenerator(std::string S) : S(std::move(S)) {}
127  std::string *Result) const override {
128  Result->append(S);
129  return llvm::Error::success();
130  }
131  std::string toString() const override {
132  return (llvm::Twine("text(\"") + S + "\")").str();
133  }
134 };
135 } // namespace
136 
137 static TextGenerator makeText(std::string S) {
138  return std::make_shared<SimpleTextGenerator>(std::move(S));
139 }
140 
142  return change(std::move(S), makeText(""));
143 }
144 
145 static std::string formatHeaderPath(StringRef Header, IncludeFormat Format) {
146  switch (Format) {
148  return Header.str();
150  return ("<" + Header + ">").str();
151  }
152  llvm_unreachable("Unknown transformer::IncludeFormat enum");
153 }
154 
156  IncludeFormat Format) {
157  ASTEdit E;
159  E.TargetRange = Target;
160  E.Replacement = makeText(formatHeaderPath(Header, Format));
161  return E;
162 }
163 
164 RewriteRule transformer::makeRule(DynTypedMatcher M, EditGenerator Edits,
165  TextGenerator Explanation) {
166  return RewriteRule{{RewriteRule::Case{std::move(M), std::move(Edits),
167  std::move(Explanation)}}};
168 }
169 
170 namespace {
171 
172 /// Unconditionally binds the given node set before trying `InnerMatcher` and
173 /// keeps the bound nodes on a successful match.
174 template <typename T>
175 class BindingsMatcher : public ast_matchers::internal::MatcherInterface<T> {
177  const ast_matchers::internal::Matcher<T> InnerMatcher;
178 
179 public:
180  explicit BindingsMatcher(ast_matchers::BoundNodes Nodes,
181  ast_matchers::internal::Matcher<T> InnerMatcher)
182  : Nodes(std::move(Nodes)), InnerMatcher(std::move(InnerMatcher)) {}
183 
184  bool matches(
185  const T &Node, ast_matchers::internal::ASTMatchFinder *Finder,
186  ast_matchers::internal::BoundNodesTreeBuilder *Builder) const override {
187  ast_matchers::internal::BoundNodesTreeBuilder Result(*Builder);
188  for (const auto &N : Nodes.getMap())
189  Result.setBinding(N.first, N.second);
190  if (InnerMatcher.matches(Node, Finder, &Result)) {
191  *Builder = std::move(Result);
192  return true;
193  }
194  return false;
195  }
196 };
197 
198 /// Matches nodes of type T that have at least one descendant node for which the
199 /// given inner matcher matches. Will match for each descendant node that
200 /// matches. Based on ForEachDescendantMatcher, but takes a dynamic matcher,
201 /// instead of a static one, because it is used by RewriteRule, which carries
202 /// (only top-level) dynamic matchers.
203 template <typename T>
204 class DynamicForEachDescendantMatcher
205  : public ast_matchers::internal::MatcherInterface<T> {
206  const DynTypedMatcher DescendantMatcher;
207 
208 public:
209  explicit DynamicForEachDescendantMatcher(DynTypedMatcher DescendantMatcher)
210  : DescendantMatcher(std::move(DescendantMatcher)) {}
211 
212  bool matches(
213  const T &Node, ast_matchers::internal::ASTMatchFinder *Finder,
214  ast_matchers::internal::BoundNodesTreeBuilder *Builder) const override {
215  return Finder->matchesDescendantOf(
216  Node, this->DescendantMatcher, Builder,
217  ast_matchers::internal::ASTMatchFinder::BK_All);
218  }
219 };
220 
221 template <typename T>
222 ast_matchers::internal::Matcher<T>
223 forEachDescendantDynamically(ast_matchers::BoundNodes Nodes,
224  DynTypedMatcher M) {
225  return ast_matchers::internal::makeMatcher(new BindingsMatcher<T>(
226  std::move(Nodes),
227  ast_matchers::internal::makeMatcher(
228  new DynamicForEachDescendantMatcher<T>(std::move(M)))));
229 }
230 
231 class ApplyRuleCallback : public MatchFinder::MatchCallback {
232 public:
233  ApplyRuleCallback(RewriteRule Rule) : Rule(std::move(Rule)) {}
234 
235  template <typename T>
236  void registerMatchers(const ast_matchers::BoundNodes &Nodes,
237  MatchFinder *MF) {
238  for (auto &Matcher : transformer::detail::buildMatchers(Rule))
239  MF->addMatcher(forEachDescendantDynamically<T>(Nodes, Matcher), this);
240  }
241 
242  void run(const MatchFinder::MatchResult &Result) override {
243  if (!Edits)
244  return;
247  auto Transformations = Case.Edits(Result);
248  if (!Transformations) {
249  Edits = Transformations.takeError();
250  return;
251  }
252  Edits->append(Transformations->begin(), Transformations->end());
253  }
254 
255  RewriteRule Rule;
256 
257  // Initialize to a non-error state.
259 };
260 } // namespace
261 
262 template <typename T>
265  const MatchResult &Result) {
266  ApplyRuleCallback Callback(std::move(Rule));
267  MatchFinder Finder;
268  Callback.registerMatchers<T>(Result.Nodes, &Finder);
269  Finder.match(Node, *Result.Context);
270  return std::move(Callback.Edits);
271 }
272 
275  const MatchResult &Result) {
276  return rewriteDescendantsImpl(Node, std::move(Rule), Result);
277 }
278 
281  const MatchResult &Result) {
282  return rewriteDescendantsImpl(Node, std::move(Rule), Result);
283 }
284 
287  const MatchResult &Result) {
288  return rewriteDescendantsImpl(Node, std::move(Rule), Result);
289 }
290 
293  RewriteRule Rule,
294  const MatchResult &Result) {
295  if (const auto *Node = DNode.get<Decl>())
296  return rewriteDescendantsImpl(*Node, std::move(Rule), Result);
297  if (const auto *Node = DNode.get<Stmt>())
298  return rewriteDescendantsImpl(*Node, std::move(Rule), Result);
299  if (const auto *Node = DNode.get<TypeLoc>())
300  return rewriteDescendantsImpl(*Node, std::move(Rule), Result);
301 
302  return llvm::make_error<llvm::StringError>(
303  llvm::errc::invalid_argument,
304  "type unsupported for recursive rewriting, Kind=" +
305  DNode.getNodeKind().asStringRef());
306 }
307 
309  RewriteRule Rule) {
310  return [NodeId = std::move(NodeId),
311  Rule = std::move(Rule)](const MatchResult &Result)
313  const ast_matchers::BoundNodes::IDToNodeMap &NodesMap =
314  Result.Nodes.getMap();
315  auto It = NodesMap.find(NodeId);
316  if (It == NodesMap.end())
317  return llvm::make_error<llvm::StringError>(llvm::errc::invalid_argument,
318  "ID not bound: " + NodeId);
319  return detail::rewriteDescendants(It->second, std::move(Rule), Result);
320  };
321 }
322 
323 void transformer::addInclude(RewriteRule &Rule, StringRef Header,
324  IncludeFormat Format) {
325  for (auto &Case : Rule.Cases)
326  Case.Edits = flatten(std::move(Case.Edits), addInclude(Header, Format));
327 }
328 
329 #ifndef NDEBUG
330 // Filters for supported matcher kinds. FIXME: Explicitly list the allowed kinds
331 // (all node matcher types except for `QualType` and `Type`), rather than just
332 // banning `QualType` and `Type`.
333 static bool hasValidKind(const DynTypedMatcher &M) {
334  return !M.canConvertTo<QualType>();
335 }
336 #endif
337 
338 // Binds each rule's matcher to a unique (and deterministic) tag based on
339 // `TagBase` and the id paired with the case. All of the returned matchers have
340 // their traversal kind explicitly set, either based on a pre-set kind or to the
341 // provided `DefaultTraversalKind`.
342 static std::vector<DynTypedMatcher> taggedMatchers(
343  StringRef TagBase,
344  const SmallVectorImpl<std::pair<size_t, RewriteRule::Case>> &Cases,
345  ast_type_traits::TraversalKind DefaultTraversalKind) {
346  std::vector<DynTypedMatcher> Matchers;
347  Matchers.reserve(Cases.size());
348  for (const auto &Case : Cases) {
349  std::string Tag = (TagBase + Twine(Case.first)).str();
350  // HACK: Many matchers are not bindable, so ensure that tryBind will work.
351  DynTypedMatcher BoundMatcher(Case.second.Matcher);
352  BoundMatcher.setAllowBind(true);
353  auto M = *BoundMatcher.tryBind(Tag);
354  Matchers.push_back(!M.getTraversalKind()
355  ? M.withTraversalKind(DefaultTraversalKind)
356  : std::move(M));
357  }
358  return Matchers;
359 }
360 
361 // Simply gathers the contents of the various rules into a single rule. The
362 // actual work to combine these into an ordered choice is deferred to matcher
363 // registration.
365  RewriteRule R;
366  for (auto &Rule : Rules)
367  R.Cases.append(Rule.Cases.begin(), Rule.Cases.end());
368  return R;
369 }
370 
371 std::vector<DynTypedMatcher>
373  // Map the cases into buckets of matchers -- one for each "root" AST kind,
374  // which guarantees that they can be combined in a single anyOf matcher. Each
375  // case is paired with an identifying number that is converted to a string id
376  // in `taggedMatchers`.
377  std::map<ASTNodeKind, SmallVector<std::pair<size_t, RewriteRule::Case>, 1>>
378  Buckets;
379  const SmallVectorImpl<RewriteRule::Case> &Cases = Rule.Cases;
380  for (int I = 0, N = Cases.size(); I < N; ++I) {
381  assert(hasValidKind(Cases[I].Matcher) &&
382  "Matcher must be non-(Qual)Type node matcher");
383  Buckets[Cases[I].Matcher.getSupportedKind()].emplace_back(I, Cases[I]);
384  }
385 
386  // Each anyOf explicitly controls the traversal kind. The anyOf itself is set
387  // to `TK_AsIs` to ensure no nodes are skipped, thereby deferring to the kind
388  // of the branches. Then, each branch is either left as is, if the kind is
389  // already set, or explicitly set to `TK_AsIs`. We choose this setting because
390  // it is the default interpretation of matchers.
391  std::vector<DynTypedMatcher> Matchers;
392  for (const auto &Bucket : Buckets) {
393  DynTypedMatcher M = DynTypedMatcher::constructVariadic(
394  DynTypedMatcher::VO_AnyOf, Bucket.first,
395  taggedMatchers("Tag", Bucket.second, TK_AsIs));
396  M.setAllowBind(true);
397  // `tryBind` is guaranteed to succeed, because `AllowBind` was set to true.
398  Matchers.push_back(M.tryBind(RootID)->withTraversalKind(TK_AsIs));
399  }
400  return Matchers;
401 }
402 
403 DynTypedMatcher transformer::detail::buildMatcher(const RewriteRule &Rule) {
404  std::vector<DynTypedMatcher> Ms = buildMatchers(Rule);
405  assert(Ms.size() == 1 && "Cases must have compatible matchers.");
406  return Ms[0];
407 }
408 
410  auto &NodesMap = Result.Nodes.getMap();
411  auto Root = NodesMap.find(RootID);
412  assert(Root != NodesMap.end() && "Transformation failed: missing root node.");
414  CharSourceRange::getTokenRange(Root->second.getSourceRange()),
415  *Result.Context);
416  if (RootRange)
417  return RootRange->getBegin();
418  // The match doesn't have a coherent range, so fall back to the expansion
419  // location as the "beginning" of the match.
420  return Result.SourceManager->getExpansionLoc(
421  Root->second.getSourceRange().getBegin());
422 }
423 
424 // Finds the case that was "selected" -- that is, whose matcher triggered the
425 // `MatchResult`.
426 const RewriteRule::Case &
428  const RewriteRule &Rule) {
429  if (Rule.Cases.size() == 1)
430  return Rule.Cases[0];
431 
432  auto &NodesMap = Result.Nodes.getMap();
433  for (size_t i = 0, N = Rule.Cases.size(); i < N; ++i) {
434  std::string Tag = ("Tag" + Twine(i)).str();
435  if (NodesMap.find(Tag) != NodesMap.end())
436  return Rule.Cases[i];
437  }
438  llvm_unreachable("No tag found for this rule.");
439 }
440 
441 const llvm::StringRef RewriteRule::RootID = ::clang::transformer::RootID;
A class to allow finding matches over the Clang AST.
A (possibly-)qualified type.
Definition: Type.h:661
Stmt - This represents one statement.
Definition: Stmt.h:68
static CharSourceRange getTokenRange(SourceRange R)
ast_matchers::internal::DynTypedMatcher buildMatcher(const RewriteRule &Rule)
Builds a single matcher for the rule, covering all of the rule's cases.
EditGenerator rewriteDescendants(std::string NodeId, RewriteRule Rule)
Applies Rule to all descendants of the node bound to NodeId.
internal::BoundNodesMap::IDToNodeMap IDToNodeMap
Type of mapping from binding identifiers to bound nodes.
Definition: ASTMatchers.h:121
Decl - This represents one declaration (or definition), e.g.
Definition: DeclBase.h:89
TraversalKind
Defines how we descend a level in the AST when we pass through expressions.
Definition: ASTTypeTraits.h:39
Description of a source-code transformation.
Definition: RewriteRule.h:276
MatchFinder::MatchResult MatchResult
Will traverse all child nodes.
Definition: ASTTypeTraits.h:41
IncludeFormat
Format of the path in an include directive – angle brackets or quotes.
Definition: RewriteRule.h:53
BoundNodesTreeBuilder Nodes
Base wrapper for a particular "section" of type source info.
Definition: TypeLoc.h:58
MatchFinder::MatchResult MatchResult
Definition: RewriteRule.cpp:31
Definition: Format.h:2835
llvm::Expected< SmallVector< clang::transformer::Edit, 1 > > rewriteDescendantsImpl(const T &Node, RewriteRule Rule, const MatchResult &Result)
MatchConsumer< llvm::SmallVector< Edit, 1 > > EditGenerator
Maps a match result to a list of concrete edits (with possible failure).
Definition: RewriteRule.h:62
EditGenerator editList(llvm::SmallVector< ASTEdit, 1 > Edits)
Lifts a list of ASTEdits into an EditGenerator.
Definition: RewriteRule.cpp:64
void addMatcher(const DeclarationMatcher &NodeMatch, MatchCallback *Action)
Adds a matcher to execute when running over the AST.
static std::string formatHeaderPath(StringRef Header, IncludeFormat Format)
static Expected< SmallVector< transformer::Edit, 1 > > translateEdits(const MatchResult &Result, ArrayRef< ASTEdit > ASTEdits)
Definition: RewriteRule.cpp:36
SmallVector< Case, 1 > Cases
Definition: RewriteRule.h:283
static std::vector< DynTypedMatcher > taggedMatchers(StringRef TagBase, const SmallVectorImpl< std::pair< size_t, RewriteRule::Case >> &Cases, ast_type_traits::TraversalKind DefaultTraversalKind)
A concrete description of a source edit, represented by a character range in the source to be replace...
Definition: RewriteRule.h:45
DynTypedNode Node
static TextGenerator makeText(std::string S)
CharSourceRange Range
Definition: RewriteRule.h:47
SourceLocation Begin
const RewriteRule::Case & findSelectedCase(const ast_matchers::MatchFinder::MatchResult &Result, const RewriteRule &Rule)
Returns the Case of Rule that was selected in the match result.
Contains all information for a given match.
EditGenerator flatten(Ts &&...Edits)
Definition: RewriteRule.h:165
ASTEdit remove(RangeSelector S)
Removes the source selected by S.
std::vector< ast_matchers::internal::DynTypedMatcher > buildMatchers(const RewriteRule &Rule)
Builds a set of matchers that cover the rule.
static CharSourceRange getCharRange(SourceRange R)
MatchConsumer< CharSourceRange > RangeSelector
Definition: RangeSelector.h:27
Maps string IDs to AST nodes matched by parts of a matcher.
Definition: ASTMatchers.h:107
ASTEdit change(RangeSelector Target, TextGenerator Replacement)
DEPRECATED: use changeTo.
Definition: RewriteRule.h:177
Encodes a location in the source.
ASTNodeKind getNodeKind() const
const char RootID[]
Definition: RewriteRule.cpp:33
static const llvm::StringRef RootID
DEPRECATED: use clang::transformer::RootID instead.
Definition: RewriteRule.h:286
StringRef asStringRef() const
String representation of the kind.
ast_matchers::internal::DynTypedMatcher Matcher
Definition: RewriteRule.h:278
RewriteRule makeRule(ast_matchers::internal::DynTypedMatcher M, EditGenerator Edits, TextGenerator Explanation=nullptr)
Constructs a simple RewriteRule.
A dynamically typed AST node container.
llvm::Expected< SmallVector< Edit, 1 > > rewriteDescendants(const Decl &Node, RewriteRule Rule, const ast_matchers::MatchFinder::MatchResult &Result)
The following overload set is a version of rewriteDescendants that operates directly on the AST,...
RewriteRule applyFirst(ArrayRef< RewriteRule > Rules)
Applies the first rule whose pattern matches; other rules are ignored.
Dataflow Directional Tag Classes.
llvm::Optional< CharSourceRange > getRangeForEdit(const CharSourceRange &EditRange, const SourceManager &SM, const LangOptions &LangOpts)
Attempts to resolve the given range to one that can be edited by a rewrite; generally,...
Definition: SourceCode.cpp:82
EditGenerator noopEdit(RangeSelector Anchor)
Generates a single, no-op edit anchored at the start location of the specified range.
Definition: RewriteRule.cpp:76
SourceLocation getRuleMatchLoc(const ast_matchers::MatchFinder::MatchResult &Result)
Gets the beginning location of the source matched by a rewrite rule.
Stencil run(MatchConsumer< std::string > C)
Wraps a MatchConsumer in a Stencil, so that it can be used in a Stencil.
Definition: Stencil.cpp:372
std::string toString(const til::SExpr *E)
std::shared_ptr< MatchComputation< std::string > > TextGenerator
Definition: RewriteRule.h:64
EditGenerator flattenVector(SmallVector< EditGenerator, 2 > Generators)
Flattens a list of generators into a single generator whose elements are the concatenation of the res...
Definition: RewriteRule.cpp:95
Defines the clang::SourceLocation class and associated facilities.
ASTEdit changeTo(RangeSelector Target, TextGenerator Replacement)
Replaces a portion of the source text with Replacement.
Called when the Match registered for it was successfully found in the AST.
bool matches(const til::SExpr *E1, const til::SExpr *E2)
EditGenerator edit(ASTEdit E)
Generates a single (specified) edit.
Definition: RewriteRule.cpp:70
const T * get() const
Retrieve the stored node as type T.
A failable computation over nodes bound by AST matchers, with (limited) reflection via the toString m...
Definition: MatchConsumer.h:64
static bool hasValidKind(const DynTypedMatcher &M)
ASTEdit addInclude(RangeSelector Target, StringRef Header, IncludeFormat Format=IncludeFormat::Quoted)
Adds an include directive for the given header to the file of Target.
Defines the RewriteRule class and related functions for creating, modifying and interpreting RewriteR...