• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 //===--- Replacement.cpp - Framework for clang refactoring tools ----------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 //  Implements classes to support/store refactorings.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #include "clang/Tooling/Core/Replacement.h"
15 
16 #include "clang/Basic/Diagnostic.h"
17 #include "clang/Basic/DiagnosticIDs.h"
18 #include "clang/Basic/DiagnosticOptions.h"
19 #include "clang/Basic/FileManager.h"
20 #include "clang/Basic/SourceManager.h"
21 #include "clang/Lex/Lexer.h"
22 #include "clang/Rewrite/Core/Rewriter.h"
23 #include "llvm/Support/FileSystem.h"
24 #include "llvm/Support/Path.h"
25 #include "llvm/Support/raw_os_ostream.h"
26 
27 namespace clang {
28 namespace tooling {
29 
30 static const char * const InvalidLocation = "";
31 
Replacement()32 Replacement::Replacement()
33   : FilePath(InvalidLocation) {}
34 
Replacement(StringRef FilePath,unsigned Offset,unsigned Length,StringRef ReplacementText)35 Replacement::Replacement(StringRef FilePath, unsigned Offset, unsigned Length,
36                          StringRef ReplacementText)
37     : FilePath(FilePath), ReplacementRange(Offset, Length),
38       ReplacementText(ReplacementText) {}
39 
Replacement(const SourceManager & Sources,SourceLocation Start,unsigned Length,StringRef ReplacementText)40 Replacement::Replacement(const SourceManager &Sources, SourceLocation Start,
41                          unsigned Length, StringRef ReplacementText) {
42   setFromSourceLocation(Sources, Start, Length, ReplacementText);
43 }
44 
Replacement(const SourceManager & Sources,const CharSourceRange & Range,StringRef ReplacementText,const LangOptions & LangOpts)45 Replacement::Replacement(const SourceManager &Sources,
46                          const CharSourceRange &Range,
47                          StringRef ReplacementText,
48                          const LangOptions &LangOpts) {
49   setFromSourceRange(Sources, Range, ReplacementText, LangOpts);
50 }
51 
isApplicable() const52 bool Replacement::isApplicable() const {
53   return FilePath != InvalidLocation;
54 }
55 
apply(Rewriter & Rewrite) const56 bool Replacement::apply(Rewriter &Rewrite) const {
57   SourceManager &SM = Rewrite.getSourceMgr();
58   const FileEntry *Entry = SM.getFileManager().getFile(FilePath);
59   if (!Entry)
60     return false;
61 
62   FileID ID = SM.getOrCreateFileID(Entry, SrcMgr::C_User);
63   const SourceLocation Start =
64     SM.getLocForStartOfFile(ID).
65     getLocWithOffset(ReplacementRange.getOffset());
66   // ReplaceText returns false on success.
67   // ReplaceText only fails if the source location is not a file location, in
68   // which case we already returned false earlier.
69   bool RewriteSucceeded = !Rewrite.ReplaceText(
70       Start, ReplacementRange.getLength(), ReplacementText);
71   assert(RewriteSucceeded);
72   return RewriteSucceeded;
73 }
74 
toString() const75 std::string Replacement::toString() const {
76   std::string Result;
77   llvm::raw_string_ostream Stream(Result);
78   Stream << FilePath << ": " << ReplacementRange.getOffset() << ":+"
79          << ReplacementRange.getLength() << ":\"" << ReplacementText << "\"";
80   return Stream.str();
81 }
82 
operator <(const Replacement & LHS,const Replacement & RHS)83 bool operator<(const Replacement &LHS, const Replacement &RHS) {
84   if (LHS.getOffset() != RHS.getOffset())
85     return LHS.getOffset() < RHS.getOffset();
86 
87   // Apply longer replacements first, specifically so that deletions are
88   // executed before insertions. It is (hopefully) never the intention to
89   // delete parts of newly inserted code.
90   if (LHS.getLength() != RHS.getLength())
91     return LHS.getLength() > RHS.getLength();
92 
93   if (LHS.getFilePath() != RHS.getFilePath())
94     return LHS.getFilePath() < RHS.getFilePath();
95   return LHS.getReplacementText() < RHS.getReplacementText();
96 }
97 
operator ==(const Replacement & LHS,const Replacement & RHS)98 bool operator==(const Replacement &LHS, const Replacement &RHS) {
99   return LHS.getOffset() == RHS.getOffset() &&
100          LHS.getLength() == RHS.getLength() &&
101          LHS.getFilePath() == RHS.getFilePath() &&
102          LHS.getReplacementText() == RHS.getReplacementText();
103 }
104 
setFromSourceLocation(const SourceManager & Sources,SourceLocation Start,unsigned Length,StringRef ReplacementText)105 void Replacement::setFromSourceLocation(const SourceManager &Sources,
106                                         SourceLocation Start, unsigned Length,
107                                         StringRef ReplacementText) {
108   const std::pair<FileID, unsigned> DecomposedLocation =
109       Sources.getDecomposedLoc(Start);
110   const FileEntry *Entry = Sources.getFileEntryForID(DecomposedLocation.first);
111   this->FilePath = Entry ? Entry->getName() : InvalidLocation;
112   this->ReplacementRange = Range(DecomposedLocation.second, Length);
113   this->ReplacementText = ReplacementText;
114 }
115 
116 // FIXME: This should go into the Lexer, but we need to figure out how
117 // to handle ranges for refactoring in general first - there is no obvious
118 // good way how to integrate this into the Lexer yet.
getRangeSize(const SourceManager & Sources,const CharSourceRange & Range,const LangOptions & LangOpts)119 static int getRangeSize(const SourceManager &Sources,
120                         const CharSourceRange &Range,
121                         const LangOptions &LangOpts) {
122   SourceLocation SpellingBegin = Sources.getSpellingLoc(Range.getBegin());
123   SourceLocation SpellingEnd = Sources.getSpellingLoc(Range.getEnd());
124   std::pair<FileID, unsigned> Start = Sources.getDecomposedLoc(SpellingBegin);
125   std::pair<FileID, unsigned> End = Sources.getDecomposedLoc(SpellingEnd);
126   if (Start.first != End.first) return -1;
127   if (Range.isTokenRange())
128     End.second += Lexer::MeasureTokenLength(SpellingEnd, Sources, LangOpts);
129   return End.second - Start.second;
130 }
131 
setFromSourceRange(const SourceManager & Sources,const CharSourceRange & Range,StringRef ReplacementText,const LangOptions & LangOpts)132 void Replacement::setFromSourceRange(const SourceManager &Sources,
133                                      const CharSourceRange &Range,
134                                      StringRef ReplacementText,
135                                      const LangOptions &LangOpts) {
136   setFromSourceLocation(Sources, Sources.getSpellingLoc(Range.getBegin()),
137                         getRangeSize(Sources, Range, LangOpts),
138                         ReplacementText);
139 }
140 
141 template <typename T>
shiftedCodePositionInternal(const T & Replaces,unsigned Position)142 unsigned shiftedCodePositionInternal(const T &Replaces, unsigned Position) {
143   unsigned Offset = 0;
144   for (const auto& R : Replaces) {
145     if (R.getOffset() + R.getLength() <= Position) {
146       Offset += R.getReplacementText().size() - R.getLength();
147       continue;
148     }
149     if (R.getOffset() < Position &&
150         R.getOffset() + R.getReplacementText().size() <= Position) {
151       Position = R.getOffset() + R.getReplacementText().size() - 1;
152     }
153     break;
154   }
155   return Position + Offset;
156 }
157 
shiftedCodePosition(const Replacements & Replaces,unsigned Position)158 unsigned shiftedCodePosition(const Replacements &Replaces, unsigned Position) {
159   return shiftedCodePositionInternal(Replaces, Position);
160 }
161 
162 // FIXME: Remove this function when Replacements is implemented as std::vector
163 // instead of std::set.
shiftedCodePosition(const std::vector<Replacement> & Replaces,unsigned Position)164 unsigned shiftedCodePosition(const std::vector<Replacement> &Replaces,
165                              unsigned Position) {
166   return shiftedCodePositionInternal(Replaces, Position);
167 }
168 
deduplicate(std::vector<Replacement> & Replaces,std::vector<Range> & Conflicts)169 void deduplicate(std::vector<Replacement> &Replaces,
170                  std::vector<Range> &Conflicts) {
171   if (Replaces.empty())
172     return;
173 
174   auto LessNoPath = [](const Replacement &LHS, const Replacement &RHS) {
175     if (LHS.getOffset() != RHS.getOffset())
176       return LHS.getOffset() < RHS.getOffset();
177     if (LHS.getLength() != RHS.getLength())
178       return LHS.getLength() < RHS.getLength();
179     return LHS.getReplacementText() < RHS.getReplacementText();
180   };
181 
182   auto EqualNoPath = [](const Replacement &LHS, const Replacement &RHS) {
183     return LHS.getOffset() == RHS.getOffset() &&
184            LHS.getLength() == RHS.getLength() &&
185            LHS.getReplacementText() == RHS.getReplacementText();
186   };
187 
188   // Deduplicate. We don't want to deduplicate based on the path as we assume
189   // that all replacements refer to the same file (or are symlinks).
190   std::sort(Replaces.begin(), Replaces.end(), LessNoPath);
191   Replaces.erase(std::unique(Replaces.begin(), Replaces.end(), EqualNoPath),
192                  Replaces.end());
193 
194   // Detect conflicts
195   Range ConflictRange(Replaces.front().getOffset(),
196                       Replaces.front().getLength());
197   unsigned ConflictStart = 0;
198   unsigned ConflictLength = 1;
199   for (unsigned i = 1; i < Replaces.size(); ++i) {
200     Range Current(Replaces[i].getOffset(), Replaces[i].getLength());
201     if (ConflictRange.overlapsWith(Current)) {
202       // Extend conflicted range
203       ConflictRange = Range(ConflictRange.getOffset(),
204                             std::max(ConflictRange.getLength(),
205                                      Current.getOffset() + Current.getLength() -
206                                          ConflictRange.getOffset()));
207       ++ConflictLength;
208     } else {
209       if (ConflictLength > 1)
210         Conflicts.push_back(Range(ConflictStart, ConflictLength));
211       ConflictRange = Current;
212       ConflictStart = i;
213       ConflictLength = 1;
214     }
215   }
216 
217   if (ConflictLength > 1)
218     Conflicts.push_back(Range(ConflictStart, ConflictLength));
219 }
220 
applyAllReplacements(const Replacements & Replaces,Rewriter & Rewrite)221 bool applyAllReplacements(const Replacements &Replaces, Rewriter &Rewrite) {
222   bool Result = true;
223   for (Replacements::const_iterator I = Replaces.begin(),
224                                     E = Replaces.end();
225        I != E; ++I) {
226     if (I->isApplicable()) {
227       Result = I->apply(Rewrite) && Result;
228     } else {
229       Result = false;
230     }
231   }
232   return Result;
233 }
234 
235 // FIXME: Remove this function when Replacements is implemented as std::vector
236 // instead of std::set.
applyAllReplacements(const std::vector<Replacement> & Replaces,Rewriter & Rewrite)237 bool applyAllReplacements(const std::vector<Replacement> &Replaces,
238                           Rewriter &Rewrite) {
239   bool Result = true;
240   for (std::vector<Replacement>::const_iterator I = Replaces.begin(),
241                                                 E = Replaces.end();
242        I != E; ++I) {
243     if (I->isApplicable()) {
244       Result = I->apply(Rewrite) && Result;
245     } else {
246       Result = false;
247     }
248   }
249   return Result;
250 }
251 
applyAllReplacements(StringRef Code,const Replacements & Replaces)252 llvm::Expected<std::string> applyAllReplacements(StringRef Code,
253                                                 const Replacements &Replaces) {
254   if (Replaces.empty())
255     return Code.str();
256 
257   IntrusiveRefCntPtr<vfs::InMemoryFileSystem> InMemoryFileSystem(
258       new vfs::InMemoryFileSystem);
259   FileManager Files(FileSystemOptions(), InMemoryFileSystem);
260   DiagnosticsEngine Diagnostics(
261       IntrusiveRefCntPtr<DiagnosticIDs>(new DiagnosticIDs),
262       new DiagnosticOptions);
263   SourceManager SourceMgr(Diagnostics, Files);
264   Rewriter Rewrite(SourceMgr, LangOptions());
265   InMemoryFileSystem->addFile(
266       "<stdin>", 0, llvm::MemoryBuffer::getMemBuffer(Code, "<stdin>"));
267   FileID ID = SourceMgr.createFileID(Files.getFile("<stdin>"), SourceLocation(),
268                                      clang::SrcMgr::C_User);
269   for (Replacements::const_iterator I = Replaces.begin(), E = Replaces.end();
270        I != E; ++I) {
271     Replacement Replace("<stdin>", I->getOffset(), I->getLength(),
272                         I->getReplacementText());
273     if (!Replace.apply(Rewrite))
274       return llvm::make_error<llvm::StringError>(
275           "Failed to apply replacement: " + Replace.toString(),
276           llvm::inconvertibleErrorCode());
277   }
278   std::string Result;
279   llvm::raw_string_ostream OS(Result);
280   Rewrite.getEditBuffer(ID).write(OS);
281   OS.flush();
282   return Result;
283 }
284 
285 // Merge and sort overlapping ranges in \p Ranges.
mergeAndSortRanges(std::vector<Range> Ranges)286 static std::vector<Range> mergeAndSortRanges(std::vector<Range> Ranges) {
287   std::sort(Ranges.begin(), Ranges.end(),
288             [](const Range &LHS, const Range &RHS) {
289               if (LHS.getOffset() != RHS.getOffset())
290                 return LHS.getOffset() < RHS.getOffset();
291               return LHS.getLength() < RHS.getLength();
292             });
293   std::vector<Range> Result;
294   for (const auto &R : Ranges) {
295     if (Result.empty() ||
296         Result.back().getOffset() + Result.back().getLength() < R.getOffset()) {
297       Result.push_back(R);
298     } else {
299       unsigned NewEnd =
300           std::max(Result.back().getOffset() + Result.back().getLength(),
301                    R.getOffset() + R.getLength());
302       Result[Result.size() - 1] =
303           Range(Result.back().getOffset(), NewEnd - Result.back().getOffset());
304     }
305   }
306   return Result;
307 }
308 
calculateChangedRanges(const Replacements & Replaces)309 std::vector<Range> calculateChangedRanges(const Replacements &Replaces) {
310   std::vector<Range> ChangedRanges;
311   int Shift = 0;
312   for (const Replacement &R : Replaces) {
313     unsigned Offset = R.getOffset() + Shift;
314     unsigned Length = R.getReplacementText().size();
315     Shift += Length - R.getLength();
316     ChangedRanges.push_back(Range(Offset, Length));
317   }
318   return mergeAndSortRanges(ChangedRanges);
319 }
320 
321 std::vector<Range>
calculateRangesAfterReplacements(const Replacements & Replaces,const std::vector<Range> & Ranges)322 calculateRangesAfterReplacements(const Replacements &Replaces,
323                                  const std::vector<Range> &Ranges) {
324   auto MergedRanges = mergeAndSortRanges(Ranges);
325   tooling::Replacements FakeReplaces;
326   for (const auto &R : MergedRanges)
327     FakeReplaces.insert(Replacement(Replaces.begin()->getFilePath(),
328                                     R.getOffset(), R.getLength(),
329                                     std::string(R.getLength(), ' ')));
330   tooling::Replacements NewReplaces = mergeReplacements(FakeReplaces, Replaces);
331   return calculateChangedRanges(NewReplaces);
332 }
333 
334 namespace {
335 // Represents a merged replacement, i.e. a replacement consisting of multiple
336 // overlapping replacements from 'First' and 'Second' in mergeReplacements.
337 //
338 // Position projection:
339 // Offsets and lengths of the replacements can generally refer to two different
340 // coordinate spaces. Replacements from 'First' refer to the original text
341 // whereas replacements from 'Second' refer to the text after applying 'First'.
342 //
343 // MergedReplacement always operates in the coordinate space of the original
344 // text, i.e. transforms elements from 'Second' to take into account what was
345 // changed based on the elements from 'First'.
346 //
347 // We can correctly calculate this projection as we look at the replacements in
348 // order of strictly increasing offsets.
349 //
350 // Invariants:
351 // * We always merge elements from 'First' into elements from 'Second' and vice
352 //   versa. Within each set, the replacements are non-overlapping.
353 // * We only extend to the right, i.e. merge elements with strictly increasing
354 //   offsets.
355 class MergedReplacement {
356 public:
MergedReplacement(const Replacement & R,bool MergeSecond,int D)357   MergedReplacement(const Replacement &R, bool MergeSecond, int D)
358       : MergeSecond(MergeSecond), Delta(D), FilePath(R.getFilePath()),
359         Offset(R.getOffset() + (MergeSecond ? 0 : Delta)), Length(R.getLength()),
360         Text(R.getReplacementText()) {
361     Delta += MergeSecond ? 0 : Text.size() - Length;
362     DeltaFirst = MergeSecond ? Text.size() - Length : 0;
363   }
364 
365   // Merges the next element 'R' into this merged element. As we always merge
366   // from 'First' into 'Second' or vice versa, the MergedReplacement knows what
367   // set the next element is coming from.
merge(const Replacement & R)368   void merge(const Replacement &R) {
369     if (MergeSecond) {
370       unsigned REnd = R.getOffset() + Delta + R.getLength();
371       unsigned End = Offset + Text.size();
372       if (REnd > End) {
373         Length += REnd - End;
374         MergeSecond = false;
375       }
376       StringRef TextRef = Text;
377       StringRef Head = TextRef.substr(0, R.getOffset() + Delta - Offset);
378       StringRef Tail = TextRef.substr(REnd - Offset);
379       Text = (Head + R.getReplacementText() + Tail).str();
380       Delta += R.getReplacementText().size() - R.getLength();
381     } else {
382       unsigned End = Offset + Length;
383       StringRef RText = R.getReplacementText();
384       StringRef Tail = RText.substr(End - R.getOffset());
385       Text = (Text + Tail).str();
386       if (R.getOffset() + RText.size() > End) {
387         Length = R.getOffset() + R.getLength() - Offset;
388         MergeSecond = true;
389       } else {
390         Length += R.getLength() - RText.size();
391       }
392       DeltaFirst += RText.size() - R.getLength();
393     }
394   }
395 
396   // Returns 'true' if 'R' starts strictly after the MergedReplacement and thus
397   // doesn't need to be merged.
endsBefore(const Replacement & R) const398   bool endsBefore(const Replacement &R) const {
399     if (MergeSecond)
400       return Offset + Text.size() < R.getOffset() + Delta;
401     return Offset + Length < R.getOffset();
402   }
403 
404   // Returns 'true' if an element from the second set should be merged next.
mergeSecond() const405   bool mergeSecond() const { return MergeSecond; }
deltaFirst() const406   int deltaFirst() const { return DeltaFirst; }
asReplacement() const407   Replacement asReplacement() const { return {FilePath, Offset, Length, Text}; }
408 
409 private:
410   bool MergeSecond;
411 
412   // Amount of characters that elements from 'Second' need to be shifted by in
413   // order to refer to the original text.
414   int Delta;
415 
416   // Sum of all deltas (text-length - length) of elements from 'First' merged
417   // into this element. This is used to update 'Delta' once the
418   // MergedReplacement is completed.
419   int DeltaFirst;
420 
421   // Data of the actually merged replacement. FilePath and Offset aren't changed
422   // as the element is only extended to the right.
423   const StringRef FilePath;
424   const unsigned Offset;
425   unsigned Length;
426   std::string Text;
427 };
428 } // namespace
429 
430 std::map<std::string, Replacements>
groupReplacementsByFile(const Replacements & Replaces)431 groupReplacementsByFile(const Replacements &Replaces) {
432   std::map<std::string, Replacements> FileToReplaces;
433   for (const auto &Replace : Replaces) {
434     FileToReplaces[Replace.getFilePath()].insert(Replace);
435   }
436   return FileToReplaces;
437 }
438 
mergeReplacements(const Replacements & First,const Replacements & Second)439 Replacements mergeReplacements(const Replacements &First,
440                                const Replacements &Second) {
441   if (First.empty() || Second.empty())
442     return First.empty() ? Second : First;
443 
444   // Delta is the amount of characters that replacements from 'Second' need to
445   // be shifted so that their offsets refer to the original text.
446   int Delta = 0;
447   Replacements Result;
448 
449   // Iterate over both sets and always add the next element (smallest total
450   // Offset) from either 'First' or 'Second'. Merge that element with
451   // subsequent replacements as long as they overlap. See more details in the
452   // comment on MergedReplacement.
453   for (auto FirstI = First.begin(), SecondI = Second.begin();
454        FirstI != First.end() || SecondI != Second.end();) {
455     bool NextIsFirst = SecondI == Second.end() ||
456                        (FirstI != First.end() &&
457                         FirstI->getOffset() < SecondI->getOffset() + Delta);
458     MergedReplacement Merged(NextIsFirst ? *FirstI : *SecondI, NextIsFirst,
459                              Delta);
460     ++(NextIsFirst ? FirstI : SecondI);
461 
462     while ((Merged.mergeSecond() && SecondI != Second.end()) ||
463            (!Merged.mergeSecond() && FirstI != First.end())) {
464       auto &I = Merged.mergeSecond() ? SecondI : FirstI;
465       if (Merged.endsBefore(*I))
466         break;
467       Merged.merge(*I);
468       ++I;
469     }
470     Delta -= Merged.deltaFirst();
471     Result.insert(Merged.asReplacement());
472   }
473   return Result;
474 }
475 
476 } // end namespace tooling
477 } // end namespace clang
478