xref: /openbsd-src/gnu/llvm/clang/lib/Tooling/Core/Replacement.cpp (revision 12c855180aad702bbcca06e0398d774beeafb155)
1e5dd7070Spatrick //===- Replacement.cpp - Framework for clang refactoring tools ------------===//
2e5dd7070Spatrick //
3e5dd7070Spatrick // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4e5dd7070Spatrick // See https://llvm.org/LICENSE.txt for license information.
5e5dd7070Spatrick // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6e5dd7070Spatrick //
7e5dd7070Spatrick //===----------------------------------------------------------------------===//
8e5dd7070Spatrick //
9e5dd7070Spatrick //  Implements classes to support/store refactorings.
10e5dd7070Spatrick //
11e5dd7070Spatrick //===----------------------------------------------------------------------===//
12e5dd7070Spatrick 
13e5dd7070Spatrick #include "clang/Tooling/Core/Replacement.h"
14e5dd7070Spatrick #include "clang/Basic/Diagnostic.h"
15e5dd7070Spatrick #include "clang/Basic/DiagnosticIDs.h"
16e5dd7070Spatrick #include "clang/Basic/DiagnosticOptions.h"
17e5dd7070Spatrick #include "clang/Basic/FileManager.h"
18e5dd7070Spatrick #include "clang/Basic/FileSystemOptions.h"
19e5dd7070Spatrick #include "clang/Basic/SourceLocation.h"
20e5dd7070Spatrick #include "clang/Basic/SourceManager.h"
21e5dd7070Spatrick #include "clang/Lex/Lexer.h"
22e5dd7070Spatrick #include "clang/Rewrite/Core/RewriteBuffer.h"
23e5dd7070Spatrick #include "clang/Rewrite/Core/Rewriter.h"
24e5dd7070Spatrick #include "llvm/ADT/IntrusiveRefCntPtr.h"
25e5dd7070Spatrick #include "llvm/ADT/SmallPtrSet.h"
26e5dd7070Spatrick #include "llvm/ADT/StringRef.h"
27e5dd7070Spatrick #include "llvm/Support/Error.h"
28e5dd7070Spatrick #include "llvm/Support/ErrorHandling.h"
29e5dd7070Spatrick #include "llvm/Support/MemoryBuffer.h"
30e5dd7070Spatrick #include "llvm/Support/VirtualFileSystem.h"
31e5dd7070Spatrick #include "llvm/Support/raw_ostream.h"
32e5dd7070Spatrick #include <algorithm>
33e5dd7070Spatrick #include <cassert>
34e5dd7070Spatrick #include <limits>
35e5dd7070Spatrick #include <map>
36e5dd7070Spatrick #include <string>
37e5dd7070Spatrick #include <utility>
38e5dd7070Spatrick #include <vector>
39e5dd7070Spatrick 
40e5dd7070Spatrick using namespace clang;
41e5dd7070Spatrick using namespace tooling;
42e5dd7070Spatrick 
43e5dd7070Spatrick static const char * const InvalidLocation = "";
44e5dd7070Spatrick 
Replacement()45e5dd7070Spatrick Replacement::Replacement() : FilePath(InvalidLocation) {}
46e5dd7070Spatrick 
Replacement(StringRef FilePath,unsigned Offset,unsigned Length,StringRef ReplacementText)47e5dd7070Spatrick Replacement::Replacement(StringRef FilePath, unsigned Offset, unsigned Length,
48e5dd7070Spatrick                          StringRef ReplacementText)
49ec727ea7Spatrick     : FilePath(std::string(FilePath)), ReplacementRange(Offset, Length),
50ec727ea7Spatrick       ReplacementText(std::string(ReplacementText)) {}
51e5dd7070Spatrick 
Replacement(const SourceManager & Sources,SourceLocation Start,unsigned Length,StringRef ReplacementText)52e5dd7070Spatrick Replacement::Replacement(const SourceManager &Sources, SourceLocation Start,
53e5dd7070Spatrick                          unsigned Length, StringRef ReplacementText) {
54e5dd7070Spatrick   setFromSourceLocation(Sources, Start, Length, ReplacementText);
55e5dd7070Spatrick }
56e5dd7070Spatrick 
Replacement(const SourceManager & Sources,const CharSourceRange & Range,StringRef ReplacementText,const LangOptions & LangOpts)57e5dd7070Spatrick Replacement::Replacement(const SourceManager &Sources,
58e5dd7070Spatrick                          const CharSourceRange &Range,
59e5dd7070Spatrick                          StringRef ReplacementText,
60e5dd7070Spatrick                          const LangOptions &LangOpts) {
61e5dd7070Spatrick   setFromSourceRange(Sources, Range, ReplacementText, LangOpts);
62e5dd7070Spatrick }
63e5dd7070Spatrick 
isApplicable() const64e5dd7070Spatrick bool Replacement::isApplicable() const {
65e5dd7070Spatrick   return FilePath != InvalidLocation;
66e5dd7070Spatrick }
67e5dd7070Spatrick 
apply(Rewriter & Rewrite) const68e5dd7070Spatrick bool Replacement::apply(Rewriter &Rewrite) const {
69e5dd7070Spatrick   SourceManager &SM = Rewrite.getSourceMgr();
70e5dd7070Spatrick   auto Entry = SM.getFileManager().getFile(FilePath);
71e5dd7070Spatrick   if (!Entry)
72e5dd7070Spatrick     return false;
73e5dd7070Spatrick 
74e5dd7070Spatrick   FileID ID = SM.getOrCreateFileID(*Entry, SrcMgr::C_User);
75e5dd7070Spatrick   const SourceLocation Start =
76e5dd7070Spatrick     SM.getLocForStartOfFile(ID).
77e5dd7070Spatrick     getLocWithOffset(ReplacementRange.getOffset());
78e5dd7070Spatrick   // ReplaceText returns false on success.
79e5dd7070Spatrick   // ReplaceText only fails if the source location is not a file location, in
80e5dd7070Spatrick   // which case we already returned false earlier.
81e5dd7070Spatrick   bool RewriteSucceeded = !Rewrite.ReplaceText(
82e5dd7070Spatrick       Start, ReplacementRange.getLength(), ReplacementText);
83e5dd7070Spatrick   assert(RewriteSucceeded);
84e5dd7070Spatrick   return RewriteSucceeded;
85e5dd7070Spatrick }
86e5dd7070Spatrick 
toString() const87e5dd7070Spatrick std::string Replacement::toString() const {
88e5dd7070Spatrick   std::string Result;
89e5dd7070Spatrick   llvm::raw_string_ostream Stream(Result);
90e5dd7070Spatrick   Stream << FilePath << ": " << ReplacementRange.getOffset() << ":+"
91e5dd7070Spatrick          << ReplacementRange.getLength() << ":\"" << ReplacementText << "\"";
92e5dd7070Spatrick   return Stream.str();
93e5dd7070Spatrick }
94e5dd7070Spatrick 
95e5dd7070Spatrick namespace clang {
96e5dd7070Spatrick namespace tooling {
97e5dd7070Spatrick 
operator <(const Replacement & LHS,const Replacement & RHS)98e5dd7070Spatrick bool operator<(const Replacement &LHS, const Replacement &RHS) {
99e5dd7070Spatrick   if (LHS.getOffset() != RHS.getOffset())
100e5dd7070Spatrick     return LHS.getOffset() < RHS.getOffset();
101e5dd7070Spatrick 
102e5dd7070Spatrick   if (LHS.getLength() != RHS.getLength())
103e5dd7070Spatrick     return LHS.getLength() < RHS.getLength();
104e5dd7070Spatrick 
105e5dd7070Spatrick   if (LHS.getFilePath() != RHS.getFilePath())
106e5dd7070Spatrick     return LHS.getFilePath() < RHS.getFilePath();
107e5dd7070Spatrick   return LHS.getReplacementText() < RHS.getReplacementText();
108e5dd7070Spatrick }
109e5dd7070Spatrick 
operator ==(const Replacement & LHS,const Replacement & RHS)110e5dd7070Spatrick bool operator==(const Replacement &LHS, const Replacement &RHS) {
111e5dd7070Spatrick   return LHS.getOffset() == RHS.getOffset() &&
112e5dd7070Spatrick          LHS.getLength() == RHS.getLength() &&
113e5dd7070Spatrick          LHS.getFilePath() == RHS.getFilePath() &&
114e5dd7070Spatrick          LHS.getReplacementText() == RHS.getReplacementText();
115e5dd7070Spatrick }
116e5dd7070Spatrick 
117e5dd7070Spatrick } // namespace tooling
118e5dd7070Spatrick } // namespace clang
119e5dd7070Spatrick 
setFromSourceLocation(const SourceManager & Sources,SourceLocation Start,unsigned Length,StringRef ReplacementText)120e5dd7070Spatrick void Replacement::setFromSourceLocation(const SourceManager &Sources,
121e5dd7070Spatrick                                         SourceLocation Start, unsigned Length,
122e5dd7070Spatrick                                         StringRef ReplacementText) {
123e5dd7070Spatrick   const std::pair<FileID, unsigned> DecomposedLocation =
124e5dd7070Spatrick       Sources.getDecomposedLoc(Start);
125e5dd7070Spatrick   const FileEntry *Entry = Sources.getFileEntryForID(DecomposedLocation.first);
126ec727ea7Spatrick   this->FilePath = std::string(Entry ? Entry->getName() : InvalidLocation);
127e5dd7070Spatrick   this->ReplacementRange = Range(DecomposedLocation.second, Length);
128ec727ea7Spatrick   this->ReplacementText = std::string(ReplacementText);
129e5dd7070Spatrick }
130e5dd7070Spatrick 
131e5dd7070Spatrick // FIXME: This should go into the Lexer, but we need to figure out how
132e5dd7070Spatrick // to handle ranges for refactoring in general first - there is no obvious
133e5dd7070Spatrick // good way how to integrate this into the Lexer yet.
getRangeSize(const SourceManager & Sources,const CharSourceRange & Range,const LangOptions & LangOpts)134e5dd7070Spatrick static int getRangeSize(const SourceManager &Sources,
135e5dd7070Spatrick                         const CharSourceRange &Range,
136e5dd7070Spatrick                         const LangOptions &LangOpts) {
137e5dd7070Spatrick   SourceLocation SpellingBegin = Sources.getSpellingLoc(Range.getBegin());
138e5dd7070Spatrick   SourceLocation SpellingEnd = Sources.getSpellingLoc(Range.getEnd());
139e5dd7070Spatrick   std::pair<FileID, unsigned> Start = Sources.getDecomposedLoc(SpellingBegin);
140e5dd7070Spatrick   std::pair<FileID, unsigned> End = Sources.getDecomposedLoc(SpellingEnd);
141e5dd7070Spatrick   if (Start.first != End.first) return -1;
142e5dd7070Spatrick   if (Range.isTokenRange())
143e5dd7070Spatrick     End.second += Lexer::MeasureTokenLength(SpellingEnd, Sources, LangOpts);
144e5dd7070Spatrick   return End.second - Start.second;
145e5dd7070Spatrick }
146e5dd7070Spatrick 
setFromSourceRange(const SourceManager & Sources,const CharSourceRange & Range,StringRef ReplacementText,const LangOptions & LangOpts)147e5dd7070Spatrick void Replacement::setFromSourceRange(const SourceManager &Sources,
148e5dd7070Spatrick                                      const CharSourceRange &Range,
149e5dd7070Spatrick                                      StringRef ReplacementText,
150e5dd7070Spatrick                                      const LangOptions &LangOpts) {
151e5dd7070Spatrick   setFromSourceLocation(Sources, Sources.getSpellingLoc(Range.getBegin()),
152e5dd7070Spatrick                         getRangeSize(Sources, Range, LangOpts),
153e5dd7070Spatrick                         ReplacementText);
154e5dd7070Spatrick }
155e5dd7070Spatrick 
156e5dd7070Spatrick Replacement
getReplacementInChangedCode(const Replacement & R) const157e5dd7070Spatrick Replacements::getReplacementInChangedCode(const Replacement &R) const {
158e5dd7070Spatrick   unsigned NewStart = getShiftedCodePosition(R.getOffset());
159e5dd7070Spatrick   unsigned NewEnd = getShiftedCodePosition(R.getOffset() + R.getLength());
160e5dd7070Spatrick   return Replacement(R.getFilePath(), NewStart, NewEnd - NewStart,
161e5dd7070Spatrick                      R.getReplacementText());
162e5dd7070Spatrick }
163e5dd7070Spatrick 
getReplacementErrString(replacement_error Err)164e5dd7070Spatrick static std::string getReplacementErrString(replacement_error Err) {
165e5dd7070Spatrick   switch (Err) {
166e5dd7070Spatrick   case replacement_error::fail_to_apply:
167e5dd7070Spatrick     return "Failed to apply a replacement.";
168e5dd7070Spatrick   case replacement_error::wrong_file_path:
169e5dd7070Spatrick     return "The new replacement's file path is different from the file path of "
170e5dd7070Spatrick            "existing replacements";
171e5dd7070Spatrick   case replacement_error::overlap_conflict:
172e5dd7070Spatrick     return "The new replacement overlaps with an existing replacement.";
173e5dd7070Spatrick   case replacement_error::insert_conflict:
174e5dd7070Spatrick     return "The new insertion has the same insert location as an existing "
175e5dd7070Spatrick            "replacement.";
176e5dd7070Spatrick   }
177e5dd7070Spatrick   llvm_unreachable("A value of replacement_error has no message.");
178e5dd7070Spatrick }
179e5dd7070Spatrick 
message() const180e5dd7070Spatrick std::string ReplacementError::message() const {
181e5dd7070Spatrick   std::string Message = getReplacementErrString(Err);
182*12c85518Srobert   if (NewReplacement)
183e5dd7070Spatrick     Message += "\nNew replacement: " + NewReplacement->toString();
184*12c85518Srobert   if (ExistingReplacement)
185e5dd7070Spatrick     Message += "\nExisting replacement: " + ExistingReplacement->toString();
186e5dd7070Spatrick   return Message;
187e5dd7070Spatrick }
188e5dd7070Spatrick 
189e5dd7070Spatrick char ReplacementError::ID = 0;
190e5dd7070Spatrick 
getCanonicalReplacements() const191e5dd7070Spatrick Replacements Replacements::getCanonicalReplacements() const {
192e5dd7070Spatrick   std::vector<Replacement> NewReplaces;
193e5dd7070Spatrick   // Merge adjacent replacements.
194e5dd7070Spatrick   for (const auto &R : Replaces) {
195e5dd7070Spatrick     if (NewReplaces.empty()) {
196e5dd7070Spatrick       NewReplaces.push_back(R);
197e5dd7070Spatrick       continue;
198e5dd7070Spatrick     }
199e5dd7070Spatrick     auto &Prev = NewReplaces.back();
200e5dd7070Spatrick     unsigned PrevEnd = Prev.getOffset() + Prev.getLength();
201e5dd7070Spatrick     if (PrevEnd < R.getOffset()) {
202e5dd7070Spatrick       NewReplaces.push_back(R);
203e5dd7070Spatrick     } else {
204e5dd7070Spatrick       assert(PrevEnd == R.getOffset() &&
205e5dd7070Spatrick              "Existing replacements must not overlap.");
206e5dd7070Spatrick       Replacement NewR(
207e5dd7070Spatrick           R.getFilePath(), Prev.getOffset(), Prev.getLength() + R.getLength(),
208e5dd7070Spatrick           (Prev.getReplacementText() + R.getReplacementText()).str());
209e5dd7070Spatrick       Prev = NewR;
210e5dd7070Spatrick     }
211e5dd7070Spatrick   }
212e5dd7070Spatrick   ReplacementsImpl NewReplacesImpl(NewReplaces.begin(), NewReplaces.end());
213e5dd7070Spatrick   return Replacements(NewReplacesImpl.begin(), NewReplacesImpl.end());
214e5dd7070Spatrick }
215e5dd7070Spatrick 
216e5dd7070Spatrick // `R` and `Replaces` are order-independent if applying them in either order
217e5dd7070Spatrick // has the same effect, so we need to compare replacements associated to
218e5dd7070Spatrick // applying them in either order.
219e5dd7070Spatrick llvm::Expected<Replacements>
mergeIfOrderIndependent(const Replacement & R) const220e5dd7070Spatrick Replacements::mergeIfOrderIndependent(const Replacement &R) const {
221e5dd7070Spatrick   Replacements Rs(R);
222e5dd7070Spatrick   // A Replacements set containing a single replacement that is `R` referring to
223e5dd7070Spatrick   // the code after the existing replacements `Replaces` are applied.
224e5dd7070Spatrick   Replacements RsShiftedByReplaces(getReplacementInChangedCode(R));
225e5dd7070Spatrick   // A Replacements set that is `Replaces` referring to the code after `R` is
226e5dd7070Spatrick   // applied.
227e5dd7070Spatrick   Replacements ReplacesShiftedByRs;
228e5dd7070Spatrick   for (const auto &Replace : Replaces)
229e5dd7070Spatrick     ReplacesShiftedByRs.Replaces.insert(
230e5dd7070Spatrick         Rs.getReplacementInChangedCode(Replace));
231e5dd7070Spatrick   // This is equivalent to applying `Replaces` first and then `R`.
232e5dd7070Spatrick   auto MergeShiftedRs = merge(RsShiftedByReplaces);
233e5dd7070Spatrick   // This is equivalent to applying `R` first and then `Replaces`.
234e5dd7070Spatrick   auto MergeShiftedReplaces = Rs.merge(ReplacesShiftedByRs);
235e5dd7070Spatrick 
236e5dd7070Spatrick   // Since empty or segmented replacements around existing replacements might be
237e5dd7070Spatrick   // produced above, we need to compare replacements in canonical forms.
238e5dd7070Spatrick   if (MergeShiftedRs.getCanonicalReplacements() ==
239e5dd7070Spatrick       MergeShiftedReplaces.getCanonicalReplacements())
240e5dd7070Spatrick     return MergeShiftedRs;
241e5dd7070Spatrick   return llvm::make_error<ReplacementError>(replacement_error::overlap_conflict,
242e5dd7070Spatrick                                             R, *Replaces.begin());
243e5dd7070Spatrick }
244e5dd7070Spatrick 
add(const Replacement & R)245e5dd7070Spatrick llvm::Error Replacements::add(const Replacement &R) {
246e5dd7070Spatrick   // Check the file path.
247e5dd7070Spatrick   if (!Replaces.empty() && R.getFilePath() != Replaces.begin()->getFilePath())
248e5dd7070Spatrick     return llvm::make_error<ReplacementError>(
249e5dd7070Spatrick         replacement_error::wrong_file_path, R, *Replaces.begin());
250e5dd7070Spatrick 
251e5dd7070Spatrick   // Special-case header insertions.
252e5dd7070Spatrick   if (R.getOffset() == std::numeric_limits<unsigned>::max()) {
253e5dd7070Spatrick     Replaces.insert(R);
254e5dd7070Spatrick     return llvm::Error::success();
255e5dd7070Spatrick   }
256e5dd7070Spatrick 
257e5dd7070Spatrick   // This replacement cannot conflict with replacements that end before
258e5dd7070Spatrick   // this replacement starts or start after this replacement ends.
259e5dd7070Spatrick   // We also know that there currently are no overlapping replacements.
260e5dd7070Spatrick   // Thus, we know that all replacements that start after the end of the current
261e5dd7070Spatrick   // replacement cannot overlap.
262e5dd7070Spatrick   Replacement AtEnd(R.getFilePath(), R.getOffset() + R.getLength(), 0, "");
263e5dd7070Spatrick 
264e5dd7070Spatrick   // Find the first entry that starts after or at the end of R. Note that
265e5dd7070Spatrick   // entries that start at the end can still be conflicting if R is an
266e5dd7070Spatrick   // insertion.
267e5dd7070Spatrick   auto I = Replaces.lower_bound(AtEnd);
268e5dd7070Spatrick   // If `I` starts at the same offset as `R`, `R` must be an insertion.
269e5dd7070Spatrick   if (I != Replaces.end() && R.getOffset() == I->getOffset()) {
270e5dd7070Spatrick     assert(R.getLength() == 0);
271e5dd7070Spatrick     // `I` is also an insertion, `R` and `I` conflict.
272e5dd7070Spatrick     if (I->getLength() == 0) {
273*12c85518Srobert       // Check if two insertions are order-independent: if inserting them in
274e5dd7070Spatrick       // either order produces the same text, they are order-independent.
275e5dd7070Spatrick       if ((R.getReplacementText() + I->getReplacementText()).str() !=
276e5dd7070Spatrick           (I->getReplacementText() + R.getReplacementText()).str())
277e5dd7070Spatrick         return llvm::make_error<ReplacementError>(
278e5dd7070Spatrick             replacement_error::insert_conflict, R, *I);
279e5dd7070Spatrick       // If insertions are order-independent, we can merge them.
280e5dd7070Spatrick       Replacement NewR(
281e5dd7070Spatrick           R.getFilePath(), R.getOffset(), 0,
282e5dd7070Spatrick           (R.getReplacementText() + I->getReplacementText()).str());
283e5dd7070Spatrick       Replaces.erase(I);
284e5dd7070Spatrick       Replaces.insert(std::move(NewR));
285e5dd7070Spatrick       return llvm::Error::success();
286e5dd7070Spatrick     }
287e5dd7070Spatrick     // Insertion `R` is adjacent to a non-insertion replacement `I`, so they
288e5dd7070Spatrick     // are order-independent. It is safe to assume that `R` will not conflict
289e5dd7070Spatrick     // with any replacement before `I` since all replacements before `I` must
290e5dd7070Spatrick     // either end before `R` or end at `R` but has length > 0 (if the
291e5dd7070Spatrick     // replacement before `I` is an insertion at `R`, it would have been `I`
292e5dd7070Spatrick     // since it is a lower bound of `AtEnd` and ordered before the current `I`
293e5dd7070Spatrick     // in the set).
294e5dd7070Spatrick     Replaces.insert(R);
295e5dd7070Spatrick     return llvm::Error::success();
296e5dd7070Spatrick   }
297e5dd7070Spatrick 
298e5dd7070Spatrick   // `I` is the smallest iterator (after `R`) whose entry cannot overlap.
299e5dd7070Spatrick   // If that is begin(), there are no overlaps.
300e5dd7070Spatrick   if (I == Replaces.begin()) {
301e5dd7070Spatrick     Replaces.insert(R);
302e5dd7070Spatrick     return llvm::Error::success();
303e5dd7070Spatrick   }
304e5dd7070Spatrick   --I;
305e5dd7070Spatrick   auto Overlap = [](const Replacement &R1, const Replacement &R2) -> bool {
306e5dd7070Spatrick     return Range(R1.getOffset(), R1.getLength())
307e5dd7070Spatrick         .overlapsWith(Range(R2.getOffset(), R2.getLength()));
308e5dd7070Spatrick   };
309e5dd7070Spatrick   // If the previous entry does not overlap, we know that entries before it
310e5dd7070Spatrick   // can also not overlap.
311e5dd7070Spatrick   if (!Overlap(R, *I)) {
312e5dd7070Spatrick     // If `R` and `I` do not have the same offset, it is safe to add `R` since
313e5dd7070Spatrick     // it must come after `I`. Otherwise:
314e5dd7070Spatrick     //   - If `R` is an insertion, `I` must not be an insertion since it would
315e5dd7070Spatrick     //   have come after `AtEnd`.
316e5dd7070Spatrick     //   - If `R` is not an insertion, `I` must be an insertion; otherwise, `R`
317e5dd7070Spatrick     //   and `I` would have overlapped.
318e5dd7070Spatrick     // In either case, we can safely insert `R`.
319e5dd7070Spatrick     Replaces.insert(R);
320e5dd7070Spatrick   } else {
321e5dd7070Spatrick     // `I` overlaps with `R`. We need to check `R` against all overlapping
322*12c85518Srobert     // replacements to see if they are order-independent. If they are, merge `R`
323e5dd7070Spatrick     // with them and replace them with the merged replacements.
324e5dd7070Spatrick     auto MergeBegin = I;
325e5dd7070Spatrick     auto MergeEnd = std::next(I);
326e5dd7070Spatrick     while (I != Replaces.begin()) {
327e5dd7070Spatrick       --I;
328e5dd7070Spatrick       // If `I` doesn't overlap with `R`, don't merge it.
329e5dd7070Spatrick       if (!Overlap(R, *I))
330e5dd7070Spatrick         break;
331e5dd7070Spatrick       MergeBegin = I;
332e5dd7070Spatrick     }
333e5dd7070Spatrick     Replacements OverlapReplaces(MergeBegin, MergeEnd);
334e5dd7070Spatrick     llvm::Expected<Replacements> Merged =
335e5dd7070Spatrick         OverlapReplaces.mergeIfOrderIndependent(R);
336e5dd7070Spatrick     if (!Merged)
337e5dd7070Spatrick       return Merged.takeError();
338e5dd7070Spatrick     Replaces.erase(MergeBegin, MergeEnd);
339e5dd7070Spatrick     Replaces.insert(Merged->begin(), Merged->end());
340e5dd7070Spatrick   }
341e5dd7070Spatrick   return llvm::Error::success();
342e5dd7070Spatrick }
343e5dd7070Spatrick 
344e5dd7070Spatrick namespace {
345e5dd7070Spatrick 
346e5dd7070Spatrick // Represents a merged replacement, i.e. a replacement consisting of multiple
347e5dd7070Spatrick // overlapping replacements from 'First' and 'Second' in mergeReplacements.
348e5dd7070Spatrick //
349e5dd7070Spatrick // Position projection:
350e5dd7070Spatrick // Offsets and lengths of the replacements can generally refer to two different
351e5dd7070Spatrick // coordinate spaces. Replacements from 'First' refer to the original text
352e5dd7070Spatrick // whereas replacements from 'Second' refer to the text after applying 'First'.
353e5dd7070Spatrick //
354e5dd7070Spatrick // MergedReplacement always operates in the coordinate space of the original
355e5dd7070Spatrick // text, i.e. transforms elements from 'Second' to take into account what was
356e5dd7070Spatrick // changed based on the elements from 'First'.
357e5dd7070Spatrick //
358e5dd7070Spatrick // We can correctly calculate this projection as we look at the replacements in
359e5dd7070Spatrick // order of strictly increasing offsets.
360e5dd7070Spatrick //
361e5dd7070Spatrick // Invariants:
362e5dd7070Spatrick // * We always merge elements from 'First' into elements from 'Second' and vice
363e5dd7070Spatrick //   versa. Within each set, the replacements are non-overlapping.
364e5dd7070Spatrick // * We only extend to the right, i.e. merge elements with strictly increasing
365e5dd7070Spatrick //   offsets.
366e5dd7070Spatrick class MergedReplacement {
367e5dd7070Spatrick public:
MergedReplacement(const Replacement & R,bool MergeSecond,int D)368e5dd7070Spatrick   MergedReplacement(const Replacement &R, bool MergeSecond, int D)
369e5dd7070Spatrick       : MergeSecond(MergeSecond), Delta(D), FilePath(R.getFilePath()),
370ec727ea7Spatrick         Offset(R.getOffset() + (MergeSecond ? 0 : Delta)),
371ec727ea7Spatrick         Length(R.getLength()), Text(std::string(R.getReplacementText())) {
372e5dd7070Spatrick     Delta += MergeSecond ? 0 : Text.size() - Length;
373e5dd7070Spatrick     DeltaFirst = MergeSecond ? Text.size() - Length : 0;
374e5dd7070Spatrick   }
375e5dd7070Spatrick 
376e5dd7070Spatrick   // Merges the next element 'R' into this merged element. As we always merge
377e5dd7070Spatrick   // from 'First' into 'Second' or vice versa, the MergedReplacement knows what
378e5dd7070Spatrick   // set the next element is coming from.
merge(const Replacement & R)379e5dd7070Spatrick   void merge(const Replacement &R) {
380e5dd7070Spatrick     if (MergeSecond) {
381e5dd7070Spatrick       unsigned REnd = R.getOffset() + Delta + R.getLength();
382e5dd7070Spatrick       unsigned End = Offset + Text.size();
383e5dd7070Spatrick       if (REnd > End) {
384e5dd7070Spatrick         Length += REnd - End;
385e5dd7070Spatrick         MergeSecond = false;
386e5dd7070Spatrick       }
387e5dd7070Spatrick       StringRef TextRef = Text;
388e5dd7070Spatrick       StringRef Head = TextRef.substr(0, R.getOffset() + Delta - Offset);
389e5dd7070Spatrick       StringRef Tail = TextRef.substr(REnd - Offset);
390e5dd7070Spatrick       Text = (Head + R.getReplacementText() + Tail).str();
391e5dd7070Spatrick       Delta += R.getReplacementText().size() - R.getLength();
392e5dd7070Spatrick     } else {
393e5dd7070Spatrick       unsigned End = Offset + Length;
394e5dd7070Spatrick       StringRef RText = R.getReplacementText();
395e5dd7070Spatrick       StringRef Tail = RText.substr(End - R.getOffset());
396e5dd7070Spatrick       Text = (Text + Tail).str();
397e5dd7070Spatrick       if (R.getOffset() + RText.size() > End) {
398e5dd7070Spatrick         Length = R.getOffset() + R.getLength() - Offset;
399e5dd7070Spatrick         MergeSecond = true;
400e5dd7070Spatrick       } else {
401e5dd7070Spatrick         Length += R.getLength() - RText.size();
402e5dd7070Spatrick       }
403e5dd7070Spatrick       DeltaFirst += RText.size() - R.getLength();
404e5dd7070Spatrick     }
405e5dd7070Spatrick   }
406e5dd7070Spatrick 
407e5dd7070Spatrick   // Returns 'true' if 'R' starts strictly after the MergedReplacement and thus
408e5dd7070Spatrick   // doesn't need to be merged.
endsBefore(const Replacement & R) const409e5dd7070Spatrick   bool endsBefore(const Replacement &R) const {
410e5dd7070Spatrick     if (MergeSecond)
411e5dd7070Spatrick       return Offset + Text.size() < R.getOffset() + Delta;
412e5dd7070Spatrick     return Offset + Length < R.getOffset();
413e5dd7070Spatrick   }
414e5dd7070Spatrick 
415e5dd7070Spatrick   // Returns 'true' if an element from the second set should be merged next.
mergeSecond() const416e5dd7070Spatrick   bool mergeSecond() const { return MergeSecond; }
417e5dd7070Spatrick 
deltaFirst() const418e5dd7070Spatrick   int deltaFirst() const { return DeltaFirst; }
asReplacement() const419e5dd7070Spatrick   Replacement asReplacement() const { return {FilePath, Offset, Length, Text}; }
420e5dd7070Spatrick 
421e5dd7070Spatrick private:
422e5dd7070Spatrick   bool MergeSecond;
423e5dd7070Spatrick 
424e5dd7070Spatrick   // Amount of characters that elements from 'Second' need to be shifted by in
425e5dd7070Spatrick   // order to refer to the original text.
426e5dd7070Spatrick   int Delta;
427e5dd7070Spatrick 
428e5dd7070Spatrick   // Sum of all deltas (text-length - length) of elements from 'First' merged
429e5dd7070Spatrick   // into this element. This is used to update 'Delta' once the
430e5dd7070Spatrick   // MergedReplacement is completed.
431e5dd7070Spatrick   int DeltaFirst;
432e5dd7070Spatrick 
433e5dd7070Spatrick   // Data of the actually merged replacement. FilePath and Offset aren't changed
434e5dd7070Spatrick   // as the element is only extended to the right.
435e5dd7070Spatrick   const StringRef FilePath;
436e5dd7070Spatrick   const unsigned Offset;
437e5dd7070Spatrick   unsigned Length;
438e5dd7070Spatrick   std::string Text;
439e5dd7070Spatrick };
440e5dd7070Spatrick 
441e5dd7070Spatrick } // namespace
442e5dd7070Spatrick 
merge(const Replacements & ReplacesToMerge) const443e5dd7070Spatrick Replacements Replacements::merge(const Replacements &ReplacesToMerge) const {
444e5dd7070Spatrick   if (empty() || ReplacesToMerge.empty())
445e5dd7070Spatrick     return empty() ? ReplacesToMerge : *this;
446e5dd7070Spatrick 
447e5dd7070Spatrick   auto &First = Replaces;
448e5dd7070Spatrick   auto &Second = ReplacesToMerge.Replaces;
449e5dd7070Spatrick   // Delta is the amount of characters that replacements from 'Second' need to
450e5dd7070Spatrick   // be shifted so that their offsets refer to the original text.
451e5dd7070Spatrick   int Delta = 0;
452e5dd7070Spatrick   ReplacementsImpl Result;
453e5dd7070Spatrick 
454e5dd7070Spatrick   // Iterate over both sets and always add the next element (smallest total
455e5dd7070Spatrick   // Offset) from either 'First' or 'Second'. Merge that element with
456e5dd7070Spatrick   // subsequent replacements as long as they overlap. See more details in the
457e5dd7070Spatrick   // comment on MergedReplacement.
458e5dd7070Spatrick   for (auto FirstI = First.begin(), SecondI = Second.begin();
459e5dd7070Spatrick        FirstI != First.end() || SecondI != Second.end();) {
460e5dd7070Spatrick     bool NextIsFirst = SecondI == Second.end() ||
461e5dd7070Spatrick                        (FirstI != First.end() &&
462e5dd7070Spatrick                         FirstI->getOffset() < SecondI->getOffset() + Delta);
463e5dd7070Spatrick     MergedReplacement Merged(NextIsFirst ? *FirstI : *SecondI, NextIsFirst,
464e5dd7070Spatrick                              Delta);
465e5dd7070Spatrick     ++(NextIsFirst ? FirstI : SecondI);
466e5dd7070Spatrick 
467e5dd7070Spatrick     while ((Merged.mergeSecond() && SecondI != Second.end()) ||
468e5dd7070Spatrick            (!Merged.mergeSecond() && FirstI != First.end())) {
469e5dd7070Spatrick       auto &I = Merged.mergeSecond() ? SecondI : FirstI;
470e5dd7070Spatrick       if (Merged.endsBefore(*I))
471e5dd7070Spatrick         break;
472e5dd7070Spatrick       Merged.merge(*I);
473e5dd7070Spatrick       ++I;
474e5dd7070Spatrick     }
475e5dd7070Spatrick     Delta -= Merged.deltaFirst();
476e5dd7070Spatrick     Result.insert(Merged.asReplacement());
477e5dd7070Spatrick   }
478e5dd7070Spatrick   return Replacements(Result.begin(), Result.end());
479e5dd7070Spatrick }
480e5dd7070Spatrick 
481e5dd7070Spatrick // Combines overlapping ranges in \p Ranges and sorts the combined ranges.
482e5dd7070Spatrick // Returns a set of non-overlapping and sorted ranges that is equivalent to
483e5dd7070Spatrick // \p Ranges.
combineAndSortRanges(std::vector<Range> Ranges)484e5dd7070Spatrick static std::vector<Range> combineAndSortRanges(std::vector<Range> Ranges) {
485e5dd7070Spatrick   llvm::sort(Ranges, [](const Range &LHS, const Range &RHS) {
486e5dd7070Spatrick     if (LHS.getOffset() != RHS.getOffset())
487e5dd7070Spatrick       return LHS.getOffset() < RHS.getOffset();
488e5dd7070Spatrick     return LHS.getLength() < RHS.getLength();
489e5dd7070Spatrick   });
490e5dd7070Spatrick   std::vector<Range> Result;
491e5dd7070Spatrick   for (const auto &R : Ranges) {
492e5dd7070Spatrick     if (Result.empty() ||
493e5dd7070Spatrick         Result.back().getOffset() + Result.back().getLength() < R.getOffset()) {
494e5dd7070Spatrick       Result.push_back(R);
495e5dd7070Spatrick     } else {
496e5dd7070Spatrick       unsigned NewEnd =
497e5dd7070Spatrick           std::max(Result.back().getOffset() + Result.back().getLength(),
498e5dd7070Spatrick                    R.getOffset() + R.getLength());
499e5dd7070Spatrick       Result[Result.size() - 1] =
500e5dd7070Spatrick           Range(Result.back().getOffset(), NewEnd - Result.back().getOffset());
501e5dd7070Spatrick     }
502e5dd7070Spatrick   }
503e5dd7070Spatrick   return Result;
504e5dd7070Spatrick }
505e5dd7070Spatrick 
506e5dd7070Spatrick namespace clang {
507e5dd7070Spatrick namespace tooling {
508e5dd7070Spatrick 
509e5dd7070Spatrick std::vector<Range>
calculateRangesAfterReplacements(const Replacements & Replaces,const std::vector<Range> & Ranges)510e5dd7070Spatrick calculateRangesAfterReplacements(const Replacements &Replaces,
511e5dd7070Spatrick                                  const std::vector<Range> &Ranges) {
512e5dd7070Spatrick   // To calculate the new ranges,
513e5dd7070Spatrick   //   - Turn \p Ranges into Replacements at (offset, length) with an empty
514e5dd7070Spatrick   //     (unimportant) replacement text of length "length".
515e5dd7070Spatrick   //   - Merge with \p Replaces.
516e5dd7070Spatrick   //   - The new ranges will be the affected ranges of the merged replacements.
517e5dd7070Spatrick   auto MergedRanges = combineAndSortRanges(Ranges);
518e5dd7070Spatrick   if (Replaces.empty())
519e5dd7070Spatrick     return MergedRanges;
520e5dd7070Spatrick   tooling::Replacements FakeReplaces;
521e5dd7070Spatrick   for (const auto &R : MergedRanges) {
522e5dd7070Spatrick     llvm::cantFail(
523e5dd7070Spatrick         FakeReplaces.add(Replacement(Replaces.begin()->getFilePath(),
524e5dd7070Spatrick                                      R.getOffset(), R.getLength(),
525e5dd7070Spatrick                                      std::string(R.getLength(), ' '))),
526e5dd7070Spatrick         "Replacements must not conflict since ranges have been merged.");
527e5dd7070Spatrick   }
528e5dd7070Spatrick   return FakeReplaces.merge(Replaces).getAffectedRanges();
529e5dd7070Spatrick }
530e5dd7070Spatrick 
531e5dd7070Spatrick } // namespace tooling
532e5dd7070Spatrick } // namespace clang
533e5dd7070Spatrick 
getAffectedRanges() const534e5dd7070Spatrick std::vector<Range> Replacements::getAffectedRanges() const {
535e5dd7070Spatrick   std::vector<Range> ChangedRanges;
536e5dd7070Spatrick   int Shift = 0;
537e5dd7070Spatrick   for (const auto &R : Replaces) {
538e5dd7070Spatrick     unsigned Offset = R.getOffset() + Shift;
539e5dd7070Spatrick     unsigned Length = R.getReplacementText().size();
540e5dd7070Spatrick     Shift += Length - R.getLength();
541e5dd7070Spatrick     ChangedRanges.push_back(Range(Offset, Length));
542e5dd7070Spatrick   }
543e5dd7070Spatrick   return combineAndSortRanges(ChangedRanges);
544e5dd7070Spatrick }
545e5dd7070Spatrick 
getShiftedCodePosition(unsigned Position) const546e5dd7070Spatrick unsigned Replacements::getShiftedCodePosition(unsigned Position) const {
547e5dd7070Spatrick   unsigned Offset = 0;
548e5dd7070Spatrick   for (const auto &R : Replaces) {
549e5dd7070Spatrick     if (R.getOffset() + R.getLength() <= Position) {
550e5dd7070Spatrick       Offset += R.getReplacementText().size() - R.getLength();
551e5dd7070Spatrick       continue;
552e5dd7070Spatrick     }
553e5dd7070Spatrick     if (R.getOffset() < Position &&
554e5dd7070Spatrick         R.getOffset() + R.getReplacementText().size() <= Position) {
555e5dd7070Spatrick       Position = R.getOffset() + R.getReplacementText().size();
556e5dd7070Spatrick       if (!R.getReplacementText().empty())
557e5dd7070Spatrick         Position--;
558e5dd7070Spatrick     }
559e5dd7070Spatrick     break;
560e5dd7070Spatrick   }
561e5dd7070Spatrick   return Position + Offset;
562e5dd7070Spatrick }
563e5dd7070Spatrick 
564e5dd7070Spatrick namespace clang {
565e5dd7070Spatrick namespace tooling {
566e5dd7070Spatrick 
applyAllReplacements(const Replacements & Replaces,Rewriter & Rewrite)567e5dd7070Spatrick bool applyAllReplacements(const Replacements &Replaces, Rewriter &Rewrite) {
568e5dd7070Spatrick   bool Result = true;
569e5dd7070Spatrick   for (auto I = Replaces.rbegin(), E = Replaces.rend(); I != E; ++I) {
570e5dd7070Spatrick     if (I->isApplicable()) {
571e5dd7070Spatrick       Result = I->apply(Rewrite) && Result;
572e5dd7070Spatrick     } else {
573e5dd7070Spatrick       Result = false;
574e5dd7070Spatrick     }
575e5dd7070Spatrick   }
576e5dd7070Spatrick   return Result;
577e5dd7070Spatrick }
578e5dd7070Spatrick 
applyAllReplacements(StringRef Code,const Replacements & Replaces)579e5dd7070Spatrick llvm::Expected<std::string> applyAllReplacements(StringRef Code,
580e5dd7070Spatrick                                                 const Replacements &Replaces) {
581e5dd7070Spatrick   if (Replaces.empty())
582e5dd7070Spatrick     return Code.str();
583e5dd7070Spatrick 
584e5dd7070Spatrick   IntrusiveRefCntPtr<llvm::vfs::InMemoryFileSystem> InMemoryFileSystem(
585e5dd7070Spatrick       new llvm::vfs::InMemoryFileSystem);
586e5dd7070Spatrick   FileManager Files(FileSystemOptions(), InMemoryFileSystem);
587e5dd7070Spatrick   DiagnosticsEngine Diagnostics(
588e5dd7070Spatrick       IntrusiveRefCntPtr<DiagnosticIDs>(new DiagnosticIDs),
589e5dd7070Spatrick       new DiagnosticOptions);
590e5dd7070Spatrick   SourceManager SourceMgr(Diagnostics, Files);
591e5dd7070Spatrick   Rewriter Rewrite(SourceMgr, LangOptions());
592e5dd7070Spatrick   InMemoryFileSystem->addFile(
593e5dd7070Spatrick       "<stdin>", 0, llvm::MemoryBuffer::getMemBuffer(Code, "<stdin>"));
594a9ac8606Spatrick   FileID ID = SourceMgr.createFileID(*Files.getOptionalFileRef("<stdin>"),
595e5dd7070Spatrick                                      SourceLocation(),
596e5dd7070Spatrick                                      clang::SrcMgr::C_User);
597e5dd7070Spatrick   for (auto I = Replaces.rbegin(), E = Replaces.rend(); I != E; ++I) {
598e5dd7070Spatrick     Replacement Replace("<stdin>", I->getOffset(), I->getLength(),
599e5dd7070Spatrick                         I->getReplacementText());
600e5dd7070Spatrick     if (!Replace.apply(Rewrite))
601e5dd7070Spatrick       return llvm::make_error<ReplacementError>(
602e5dd7070Spatrick           replacement_error::fail_to_apply, Replace);
603e5dd7070Spatrick   }
604e5dd7070Spatrick   std::string Result;
605e5dd7070Spatrick   llvm::raw_string_ostream OS(Result);
606e5dd7070Spatrick   Rewrite.getEditBuffer(ID).write(OS);
607e5dd7070Spatrick   OS.flush();
608e5dd7070Spatrick   return Result;
609e5dd7070Spatrick }
610e5dd7070Spatrick 
groupReplacementsByFile(FileManager & FileMgr,const std::map<std::string,Replacements> & FileToReplaces)611e5dd7070Spatrick std::map<std::string, Replacements> groupReplacementsByFile(
612e5dd7070Spatrick     FileManager &FileMgr,
613e5dd7070Spatrick     const std::map<std::string, Replacements> &FileToReplaces) {
614e5dd7070Spatrick   std::map<std::string, Replacements> Result;
615e5dd7070Spatrick   llvm::SmallPtrSet<const FileEntry *, 16> ProcessedFileEntries;
616e5dd7070Spatrick   for (const auto &Entry : FileToReplaces) {
617e5dd7070Spatrick     auto FE = FileMgr.getFile(Entry.first);
618e5dd7070Spatrick     if (!FE)
619e5dd7070Spatrick       llvm::errs() << "File path " << Entry.first << " is invalid.\n";
620e5dd7070Spatrick     else if (ProcessedFileEntries.insert(*FE).second)
621e5dd7070Spatrick       Result[Entry.first] = std::move(Entry.second);
622e5dd7070Spatrick   }
623e5dd7070Spatrick   return Result;
624e5dd7070Spatrick }
625e5dd7070Spatrick 
626e5dd7070Spatrick } // namespace tooling
627e5dd7070Spatrick } // namespace clang
628