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
27using namespace clang;
28using namespace edit;
29
30void EditsReceiver::remove(CharSourceRange range) {
31  replace(range, StringRef());
32}
33
34void 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
55void EditedSource::startingCommit() {}
56
57void 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::find(ArgUses, ArgUse) == ArgUses.end())
64      ArgUses.push_back(ArgUse);
65  }
66  CurrCommitMacroArgExps.clear();
67}
68
69StringRef EditedSource::copyString(const Twine &twine) {
70  SmallString<128> Data;
71  return copyString(twine.toStringRef(Data));
72}
73
74bool 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
111bool 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
141bool 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
199void 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
276bool 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.
314static 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::isIdentifierBodyChar(left, LangOpts) &&
318           Lexer::isIdentifierBodyChar(right, LangOpts));
319}
320
321/// Returns true if it is ok to eliminate the trailing whitespace between
322/// the given characters.
323static 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.
337static 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
382static 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
409void 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
449void EditedSource::clearRewrites() {
450  FileEdits.clear();
451  StrAlloc.Reset();
452}
453
454StringRef 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
467EditedSource::FileEditsTy::iterator
468EditedSource::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