1 //===- EditedSource.cpp - Collection of source edits ----------------------===//
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/Edit/EditedSource.h"
10 #include "clang/Basic/CharInfo.h"
11 #include "clang/Basic/LLVM.h"
12 #include "clang/Basic/SourceLocation.h"
13 #include "clang/Basic/SourceManager.h"
14 #include "clang/Edit/Commit.h"
15 #include "clang/Edit/EditsReceiver.h"
16 #include "clang/Edit/FileOffset.h"
17 #include "clang/Lex/Lexer.h"
18 #include "llvm/ADT/STLExtras.h"
19 #include "llvm/ADT/SmallString.h"
20 #include "llvm/ADT/StringRef.h"
21 #include "llvm/ADT/Twine.h"
22 #include <algorithm>
23 #include <cassert>
24 #include <tuple>
25 #include <utility>
26 
27 using namespace clang;
28 using namespace edit;
29 
30 void EditsReceiver::remove(CharSourceRange range) {
31   replace(range, StringRef());
32 }
33 
34 void EditedSource::deconstructMacroArgLoc(SourceLocation Loc,
35                                           SourceLocation &ExpansionLoc,
36                                           MacroArgUse &ArgUse) {
37   assert(SourceMgr.isMacroArgExpansion(Loc));
38   SourceLocation DefArgLoc =
39       SourceMgr.getImmediateExpansionRange(Loc).getBegin();
40   SourceLocation ImmediateExpansionLoc =
41       SourceMgr.getImmediateExpansionRange(DefArgLoc).getBegin();
42   ExpansionLoc = ImmediateExpansionLoc;
43   while (SourceMgr.isMacroBodyExpansion(ExpansionLoc))
44     ExpansionLoc =
45         SourceMgr.getImmediateExpansionRange(ExpansionLoc).getBegin();
46   SmallString<20> Buf;
47   StringRef ArgName = Lexer::getSpelling(SourceMgr.getSpellingLoc(DefArgLoc),
48                                          Buf, SourceMgr, LangOpts);
49   ArgUse = MacroArgUse{nullptr, SourceLocation(), SourceLocation()};
50   if (!ArgName.empty())
51     ArgUse = {&IdentTable.get(ArgName), ImmediateExpansionLoc,
52               SourceMgr.getSpellingLoc(DefArgLoc)};
53 }
54 
55 void EditedSource::startingCommit() {}
56 
57 void EditedSource::finishedCommit() {
58   for (auto &ExpArg : CurrCommitMacroArgExps) {
59     SourceLocation ExpLoc;
60     MacroArgUse ArgUse;
61     std::tie(ExpLoc, ArgUse) = ExpArg;
62     auto &ArgUses = ExpansionToArgMap[ExpLoc];
63     if (!llvm::is_contained(ArgUses, ArgUse))
64       ArgUses.push_back(ArgUse);
65   }
66   CurrCommitMacroArgExps.clear();
67 }
68 
69 StringRef EditedSource::copyString(const Twine &twine) {
70   SmallString<128> Data;
71   return copyString(twine.toStringRef(Data));
72 }
73 
74 bool EditedSource::canInsertInOffset(SourceLocation OrigLoc, FileOffset Offs) {
75   FileEditsTy::iterator FA = getActionForOffset(Offs);
76   if (FA != FileEdits.end()) {
77     if (FA->first != Offs)
78       return false; // position has been removed.
79   }
80 
81   if (SourceMgr.isMacroArgExpansion(OrigLoc)) {
82     SourceLocation ExpLoc;
83     MacroArgUse ArgUse;
84     deconstructMacroArgLoc(OrigLoc, ExpLoc, ArgUse);
85     auto I = ExpansionToArgMap.find(ExpLoc);
86     if (I != ExpansionToArgMap.end() &&
87         find_if(I->second, [&](const MacroArgUse &U) {
88           return ArgUse.Identifier == U.Identifier &&
89                  std::tie(ArgUse.ImmediateExpansionLoc, ArgUse.UseLoc) !=
90                      std::tie(U.ImmediateExpansionLoc, U.UseLoc);
91         }) != I->second.end()) {
92       // Trying to write in a macro argument input that has already been
93       // written by a previous commit for another expansion of the same macro
94       // argument name. For example:
95       //
96       // \code
97       //   #define MAC(x) ((x)+(x))
98       //   MAC(a)
99       // \endcode
100       //
101       // A commit modified the macro argument 'a' due to the first '(x)'
102       // expansion inside the macro definition, and a subsequent commit tried
103       // to modify 'a' again for the second '(x)' expansion. The edits of the
104       // second commit will be rejected.
105       return false;
106     }
107   }
108   return true;
109 }
110 
111 bool EditedSource::commitInsert(SourceLocation OrigLoc,
112                                 FileOffset Offs, StringRef text,
113                                 bool beforePreviousInsertions) {
114   if (!canInsertInOffset(OrigLoc, Offs))
115     return false;
116   if (text.empty())
117     return true;
118 
119   if (SourceMgr.isMacroArgExpansion(OrigLoc)) {
120     MacroArgUse ArgUse;
121     SourceLocation ExpLoc;
122     deconstructMacroArgLoc(OrigLoc, ExpLoc, ArgUse);
123     if (ArgUse.Identifier)
124       CurrCommitMacroArgExps.emplace_back(ExpLoc, ArgUse);
125   }
126 
127   FileEdit &FA = FileEdits[Offs];
128   if (FA.Text.empty()) {
129     FA.Text = copyString(text);
130     return true;
131   }
132 
133   if (beforePreviousInsertions)
134     FA.Text = copyString(Twine(text) + FA.Text);
135   else
136     FA.Text = copyString(Twine(FA.Text) + text);
137 
138   return true;
139 }
140 
141 bool EditedSource::commitInsertFromRange(SourceLocation OrigLoc,
142                                    FileOffset Offs,
143                                    FileOffset InsertFromRangeOffs, unsigned Len,
144                                    bool beforePreviousInsertions) {
145   if (Len == 0)
146     return true;
147 
148   SmallString<128> StrVec;
149   FileOffset BeginOffs = InsertFromRangeOffs;
150   FileOffset EndOffs = BeginOffs.getWithOffset(Len);
151   FileEditsTy::iterator I = FileEdits.upper_bound(BeginOffs);
152   if (I != FileEdits.begin())
153     --I;
154 
155   for (; I != FileEdits.end(); ++I) {
156     FileEdit &FA = I->second;
157     FileOffset B = I->first;
158     FileOffset E = B.getWithOffset(FA.RemoveLen);
159 
160     if (BeginOffs == B)
161       break;
162 
163     if (BeginOffs < E) {
164       if (BeginOffs > B) {
165         BeginOffs = E;
166         ++I;
167       }
168       break;
169     }
170   }
171 
172   for (; I != FileEdits.end() && EndOffs > I->first; ++I) {
173     FileEdit &FA = I->second;
174     FileOffset B = I->first;
175     FileOffset E = B.getWithOffset(FA.RemoveLen);
176 
177     if (BeginOffs < B) {
178       bool Invalid = false;
179       StringRef text = getSourceText(BeginOffs, B, Invalid);
180       if (Invalid)
181         return false;
182       StrVec += text;
183     }
184     StrVec += FA.Text;
185     BeginOffs = E;
186   }
187 
188   if (BeginOffs < EndOffs) {
189     bool Invalid = false;
190     StringRef text = getSourceText(BeginOffs, EndOffs, Invalid);
191     if (Invalid)
192       return false;
193     StrVec += text;
194   }
195 
196   return commitInsert(OrigLoc, Offs, StrVec, beforePreviousInsertions);
197 }
198 
199 void EditedSource::commitRemove(SourceLocation OrigLoc,
200                                 FileOffset BeginOffs, unsigned Len) {
201   if (Len == 0)
202     return;
203 
204   FileOffset EndOffs = BeginOffs.getWithOffset(Len);
205   FileEditsTy::iterator I = FileEdits.upper_bound(BeginOffs);
206   if (I != FileEdits.begin())
207     --I;
208 
209   for (; I != FileEdits.end(); ++I) {
210     FileEdit &FA = I->second;
211     FileOffset B = I->first;
212     FileOffset E = B.getWithOffset(FA.RemoveLen);
213 
214     if (BeginOffs < E)
215       break;
216   }
217 
218   FileOffset TopBegin, TopEnd;
219   FileEdit *TopFA = nullptr;
220 
221   if (I == FileEdits.end()) {
222     FileEditsTy::iterator
223       NewI = FileEdits.insert(I, std::make_pair(BeginOffs, FileEdit()));
224     NewI->second.RemoveLen = Len;
225     return;
226   }
227 
228   FileEdit &FA = I->second;
229   FileOffset B = I->first;
230   FileOffset E = B.getWithOffset(FA.RemoveLen);
231   if (BeginOffs < B) {
232     FileEditsTy::iterator
233       NewI = FileEdits.insert(I, std::make_pair(BeginOffs, FileEdit()));
234     TopBegin = BeginOffs;
235     TopEnd = EndOffs;
236     TopFA = &NewI->second;
237     TopFA->RemoveLen = Len;
238   } else {
239     TopBegin = B;
240     TopEnd = E;
241     TopFA = &I->second;
242     if (TopEnd >= EndOffs)
243       return;
244     unsigned diff = EndOffs.getOffset() - TopEnd.getOffset();
245     TopEnd = EndOffs;
246     TopFA->RemoveLen += diff;
247     if (B == BeginOffs)
248       TopFA->Text = StringRef();
249     ++I;
250   }
251 
252   while (I != FileEdits.end()) {
253     FileEdit &FA = I->second;
254     FileOffset B = I->first;
255     FileOffset E = B.getWithOffset(FA.RemoveLen);
256 
257     if (B >= TopEnd)
258       break;
259 
260     if (E <= TopEnd) {
261       FileEdits.erase(I++);
262       continue;
263     }
264 
265     if (B < TopEnd) {
266       unsigned diff = E.getOffset() - TopEnd.getOffset();
267       TopEnd = E;
268       TopFA->RemoveLen += diff;
269       FileEdits.erase(I);
270     }
271 
272     break;
273   }
274 }
275 
276 bool EditedSource::commit(const Commit &commit) {
277   if (!commit.isCommitable())
278     return false;
279 
280   struct CommitRAII {
281     EditedSource &Editor;
282 
283     CommitRAII(EditedSource &Editor) : Editor(Editor) {
284       Editor.startingCommit();
285     }
286 
287     ~CommitRAII() {
288       Editor.finishedCommit();
289     }
290   } CommitRAII(*this);
291 
292   for (edit::Commit::edit_iterator
293          I = commit.edit_begin(), E = commit.edit_end(); I != E; ++I) {
294     const edit::Commit::Edit &edit = *I;
295     switch (edit.Kind) {
296     case edit::Commit::Act_Insert:
297       commitInsert(edit.OrigLoc, edit.Offset, edit.Text, edit.BeforePrev);
298       break;
299     case edit::Commit::Act_InsertFromRange:
300       commitInsertFromRange(edit.OrigLoc, edit.Offset,
301                             edit.InsertFromRangeOffs, edit.Length,
302                             edit.BeforePrev);
303       break;
304     case edit::Commit::Act_Remove:
305       commitRemove(edit.OrigLoc, edit.Offset, edit.Length);
306       break;
307     }
308   }
309 
310   return true;
311 }
312 
313 // Returns true if it is ok to make the two given characters adjacent.
314 static bool canBeJoined(char left, char right, const LangOptions &LangOpts) {
315   // FIXME: Should use TokenConcatenation to make sure we don't allow stuff like
316   // making two '<' adjacent.
317   return !(Lexer::isAsciiIdentifierContinueChar(left, LangOpts) &&
318            Lexer::isAsciiIdentifierContinueChar(right, LangOpts));
319 }
320 
321 /// Returns true if it is ok to eliminate the trailing whitespace between
322 /// the given characters.
323 static bool canRemoveWhitespace(char left, char beforeWSpace, char right,
324                                 const LangOptions &LangOpts) {
325   if (!canBeJoined(left, right, LangOpts))
326     return false;
327   if (isWhitespace(left) || isWhitespace(right))
328     return true;
329   if (canBeJoined(beforeWSpace, right, LangOpts))
330     return false; // the whitespace was intentional, keep it.
331   return true;
332 }
333 
334 /// Check the range that we are going to remove and:
335 /// -Remove any trailing whitespace if possible.
336 /// -Insert a space if removing the range is going to mess up the source tokens.
337 static void adjustRemoval(const SourceManager &SM, const LangOptions &LangOpts,
338                           SourceLocation Loc, FileOffset offs,
339                           unsigned &len, StringRef &text) {
340   assert(len && text.empty());
341   SourceLocation BeginTokLoc = Lexer::GetBeginningOfToken(Loc, SM, LangOpts);
342   if (BeginTokLoc != Loc)
343     return; // the range is not at the beginning of a token, keep the range.
344 
345   bool Invalid = false;
346   StringRef buffer = SM.getBufferData(offs.getFID(), &Invalid);
347   if (Invalid)
348     return;
349 
350   unsigned begin = offs.getOffset();
351   unsigned end = begin + len;
352 
353   // Do not try to extend the removal if we're at the end of the buffer already.
354   if (end == buffer.size())
355     return;
356 
357   assert(begin < buffer.size() && end < buffer.size() && "Invalid range!");
358 
359   // FIXME: Remove newline.
360 
361   if (begin == 0) {
362     if (buffer[end] == ' ')
363       ++len;
364     return;
365   }
366 
367   if (buffer[end] == ' ') {
368     assert((end + 1 != buffer.size() || buffer.data()[end + 1] == 0) &&
369            "buffer not zero-terminated!");
370     if (canRemoveWhitespace(/*left=*/buffer[begin-1],
371                             /*beforeWSpace=*/buffer[end-1],
372                             /*right=*/buffer.data()[end + 1], // zero-terminated
373                             LangOpts))
374       ++len;
375     return;
376   }
377 
378   if (!canBeJoined(buffer[begin-1], buffer[end], LangOpts))
379     text = " ";
380 }
381 
382 static void applyRewrite(EditsReceiver &receiver,
383                          StringRef text, FileOffset offs, unsigned len,
384                          const SourceManager &SM, const LangOptions &LangOpts,
385                          bool shouldAdjustRemovals) {
386   assert(offs.getFID().isValid());
387   SourceLocation Loc = SM.getLocForStartOfFile(offs.getFID());
388   Loc = Loc.getLocWithOffset(offs.getOffset());
389   assert(Loc.isFileID());
390 
391   if (text.empty() && shouldAdjustRemovals)
392     adjustRemoval(SM, LangOpts, Loc, offs, len, text);
393 
394   CharSourceRange range = CharSourceRange::getCharRange(Loc,
395                                                      Loc.getLocWithOffset(len));
396 
397   if (text.empty()) {
398     assert(len);
399     receiver.remove(range);
400     return;
401   }
402 
403   if (len)
404     receiver.replace(range, text);
405   else
406     receiver.insert(Loc, text);
407 }
408 
409 void EditedSource::applyRewrites(EditsReceiver &receiver,
410                                  bool shouldAdjustRemovals) {
411   SmallString<128> StrVec;
412   FileOffset CurOffs, CurEnd;
413   unsigned CurLen;
414 
415   if (FileEdits.empty())
416     return;
417 
418   FileEditsTy::iterator I = FileEdits.begin();
419   CurOffs = I->first;
420   StrVec = I->second.Text;
421   CurLen = I->second.RemoveLen;
422   CurEnd = CurOffs.getWithOffset(CurLen);
423   ++I;
424 
425   for (FileEditsTy::iterator E = FileEdits.end(); I != E; ++I) {
426     FileOffset offs = I->first;
427     FileEdit act = I->second;
428     assert(offs >= CurEnd);
429 
430     if (offs == CurEnd) {
431       StrVec += act.Text;
432       CurLen += act.RemoveLen;
433       CurEnd.getWithOffset(act.RemoveLen);
434       continue;
435     }
436 
437     applyRewrite(receiver, StrVec, CurOffs, CurLen, SourceMgr, LangOpts,
438                  shouldAdjustRemovals);
439     CurOffs = offs;
440     StrVec = act.Text;
441     CurLen = act.RemoveLen;
442     CurEnd = CurOffs.getWithOffset(CurLen);
443   }
444 
445   applyRewrite(receiver, StrVec, CurOffs, CurLen, SourceMgr, LangOpts,
446                shouldAdjustRemovals);
447 }
448 
449 void EditedSource::clearRewrites() {
450   FileEdits.clear();
451   StrAlloc.Reset();
452 }
453 
454 StringRef EditedSource::getSourceText(FileOffset BeginOffs, FileOffset EndOffs,
455                                       bool &Invalid) {
456   assert(BeginOffs.getFID() == EndOffs.getFID());
457   assert(BeginOffs <= EndOffs);
458   SourceLocation BLoc = SourceMgr.getLocForStartOfFile(BeginOffs.getFID());
459   BLoc = BLoc.getLocWithOffset(BeginOffs.getOffset());
460   assert(BLoc.isFileID());
461   SourceLocation
462     ELoc = BLoc.getLocWithOffset(EndOffs.getOffset() - BeginOffs.getOffset());
463   return Lexer::getSourceText(CharSourceRange::getCharRange(BLoc, ELoc),
464                               SourceMgr, LangOpts, &Invalid);
465 }
466 
467 EditedSource::FileEditsTy::iterator
468 EditedSource::getActionForOffset(FileOffset Offs) {
469   FileEditsTy::iterator I = FileEdits.upper_bound(Offs);
470   if (I == FileEdits.begin())
471     return FileEdits.end();
472   --I;
473   FileEdit &FA = I->second;
474   FileOffset B = I->first;
475   FileOffset E = B.getWithOffset(FA.RemoveLen);
476   if (Offs >= B && Offs < E)
477     return I;
478 
479   return FileEdits.end();
480 }
481