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