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