clang-tools-extra/clangd/Format.cpp

   1 //===--- Format.cpp -----------------------------------------*- C++-*------===//
   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 #include "Format.h"
   9 #include "support/Logger.h"
  10 #include "clang/Basic/SourceManager.h"
  11 #include "clang/Format/Format.h"
  12 #include "clang/Lex/Lexer.h"
  13 #include "clang/Tooling/Core/Replacement.h"
  14 #include "llvm/Support/Unicode.h"
  15
  16 namespace clang {
  17 namespace clangd {
  18 namespace {
  19
  20 /// Append closing brackets )]} to \p Code to make it well-formed.
  21 /// Clang-format conservatively refuses to format files with unmatched brackets
  22 /// as it isn't sure where the errors are and so can't correct.
  23 /// When editing, it's reasonable to assume code before the cursor is complete.
  24 void closeBrackets(std::string &Code, const format::FormatStyle &Style) {
  25   SourceManagerForFile FileSM("mock_file.cpp", Code);
  26   auto &SM = FileSM.get();
  27   FileID FID = SM.getMainFileID();
  28   LangOptions LangOpts = format::getFormattingLangOpts(Style);
  29   Lexer Lex(FID, SM.getBufferOrFake(FID), SM, LangOpts);
  30   Token Tok;
  31   std::vector<char> Brackets;
  32   while (!Lex.LexFromRawLexer(Tok)) {
  33     switch(Tok.getKind()) {
  34       case tok::l_paren:
  35         Brackets.push_back(')');
  36         break;
  37       case tok::l_brace:
  38         Brackets.push_back('}');
  39         break;
  40       case tok::l_square:
  41         Brackets.push_back(']');
  42         break;
  43       case tok::r_paren:
  44         if (!Brackets.empty() && Brackets.back() == ')')
  45           Brackets.pop_back();
  46         break;
  47       case tok::r_brace:
  48         if (!Brackets.empty() && Brackets.back() == '}')
  49           Brackets.pop_back();
  50         break;
  51       case tok::r_square:
  52         if (!Brackets.empty() && Brackets.back() == ']')
  53           Brackets.pop_back();
  54         break;
  55       default:
  56         continue;
  57     }
  58   }
  59   // Attempt to end any open comments first.
  60   Code.append("\n// */\n");
  61   Code.append(Brackets.rbegin(), Brackets.rend());
  62 }
  63
  64 static StringRef commentMarker(llvm::StringRef Line) {
  65   for (StringRef Marker : {"///", "//"}){
  66     auto I = Line.rfind(Marker);
  67     if (I != StringRef::npos)
  68       return Line.substr(I, Marker.size());
  69   }
  70   return "";
  71 }
  72
  73 llvm::StringRef firstLine(llvm::StringRef Code) {
  74   return Code.take_until([](char C) { return C == '\n'; });
  75 }
  76
  77 llvm::StringRef lastLine(llvm::StringRef Code) {
  78   llvm::StringRef Rest = Code;
  79   while (!Rest.empty() && Rest.back() != '\n')
  80     Rest = Rest.drop_back();
  81   return Code.substr(Rest.size());
  82 }
  83
  84 // Filename is needed for tooling::Replacement and some overloads of reformat().
  85 // Its value should not affect the outcome. We use the default from reformat().
  86 llvm::StringRef Filename = "<stdin>";
  87
  88 // tooling::Replacement from overlapping StringRefs: From must be part of Code.
  89 tooling::Replacement replacement(llvm::StringRef Code, llvm::StringRef From,
  90                                  llvm::StringRef To) {
  91   assert(From.begin() >= Code.begin() && From.end() <= Code.end());
  92   // The filename is required but ignored.
  93   return tooling::Replacement(Filename, From.data() - Code.data(),
  94                               From.size(), To);
  95 }
  96
  97 // High-level representation of incremental formatting changes.
  98 // The changes are made in two steps.
  99 // 1) a (possibly-empty) set of changes synthesized by clangd (e.g. adding
 100 //    comment markers when splitting a line comment with a newline).
 101 // 2) a selective clang-format run:
 102 //    - the "source code" passed to clang format is the code up to the cursor,
 103 //      a placeholder for the cursor, and some closing brackets
 104 //    - the formatting is restricted to the cursor and (possibly) other ranges
 105 //      (e.g. the old line when inserting a newline).
 106 //    - changes before the cursor are applied, those after are discarded.
 107 struct IncrementalChanges {
 108   // Changes that should be applied before running clang-format.
 109   tooling::Replacements Changes;
 110   // Ranges of the original source code that should be clang-formatted.
 111   // The CursorProxyText will also be formatted.
 112   std::vector<tooling::Range> FormatRanges;
 113   // The source code that should stand in for the cursor when clang-formatting.
 114   // e.g. after inserting a newline, a line-comment at the cursor is used to
 115   // ensure that the newline is preserved.
 116   std::string CursorPlaceholder;
 117 };
 118
 119 // The two functions below, columnWidth() and columnWidthWithTabs(), were
 120 // adapted from similar functions in clang/lib/Format/Encoding.h.
 121 // FIXME: Move those functions to clang/include/clang/Format.h and reuse them?
 122
 123 // Helper function for columnWidthWithTabs().
 124 inline unsigned columnWidth(StringRef Text) {
 125   int ContentWidth = llvm::sys::unicode::columnWidthUTF8(Text);
 126   if (ContentWidth < 0)
 127     return Text.size(); // fallback for unprintable characters
 128   return ContentWidth;
 129 }
 130
 131 // Returns the number of columns required to display the \p Text on a terminal
 132 // with the \p TabWidth.
 133 inline unsigned columnWidthWithTabs(StringRef Text, unsigned TabWidth) {
 134   unsigned TotalWidth = 0;
 135   StringRef Tail = Text;
 136   for (;;) {
 137     StringRef::size_type TabPos = Tail.find('\t');
 138     if (TabPos == StringRef::npos)
 139       return TotalWidth + columnWidth(Tail);
 140     TotalWidth += columnWidth(Tail.substr(0, TabPos));
 141     if (TabWidth)
 142       TotalWidth += TabWidth - TotalWidth % TabWidth;
 143     Tail = Tail.substr(TabPos + 1);
 144   }
 145 }
 146
 147 // After a newline:
 148 //  - we continue any line-comment that was split
 149 //  - we format the old line in addition to the cursor
 150 //  - we represent the cursor with a line comment to preserve the newline
 151 IncrementalChanges getIncrementalChangesAfterNewline(llvm::StringRef Code,
 152                                                      unsigned Cursor,
 153                                                      unsigned TabWidth) {
 154   IncrementalChanges Result;
 155   // Before newline, code looked like:
 156   //    leading^trailing
 157   // After newline, code looks like:
 158   //    leading
 159   //    indentation^trailing
 160   // Where indentation was added by the editor.
 161   StringRef Trailing = firstLine(Code.substr(Cursor));
 162   StringRef Indentation = lastLine(Code.take_front(Cursor));
 163   if (Indentation.data() == Code.data()) {
 164     vlog("Typed a newline, but we're still on the first line!");
 165     return Result;
 166   }
 167   StringRef Leading =
 168       lastLine(Code.take_front(Indentation.data() - Code.data() - 1));
 169   StringRef NextLine = firstLine(Code.substr(Cursor + Trailing.size() + 1));
 170
 171   // Strip leading whitespace on trailing line.
 172   StringRef TrailingTrim = Trailing.ltrim();
 173   if (unsigned TrailWS = Trailing.size() - TrailingTrim.size())
 174     cantFail(Result.Changes.add(
 175         replacement(Code, StringRef(Trailing.begin(), TrailWS), "")));
 176
 177   // If we split a comment, replace indentation with a comment marker.
 178   // If the editor made the new line a comment, also respect that.
 179   StringRef CommentMarker = commentMarker(Leading);
 180   bool NewLineIsComment = !commentMarker(Indentation).empty();
 181   if (!CommentMarker.empty() &&
 182       (NewLineIsComment || !commentMarker(NextLine).empty() ||
 183        (!TrailingTrim.empty() && !TrailingTrim.starts_with("//")))) {
 184     // We indent the new comment to match the previous one.
 185     StringRef PreComment =
 186         Leading.take_front(CommentMarker.data() - Leading.data());
 187     std::string IndentAndComment =
 188         (std::string(columnWidthWithTabs(PreComment, TabWidth), ' ') +
 189          CommentMarker + " ")
 190             .str();
 191     cantFail(
 192         Result.Changes.add(replacement(Code, Indentation, IndentAndComment)));
 193   } else {
 194     // Remove any indentation and let clang-format re-add it.
 195     // This prevents the cursor marker dragging e.g. an aligned comment with it.
 196     cantFail(Result.Changes.add(replacement(Code, Indentation, "")));
 197   }
 198
 199   // If we put a the newline inside a {} pair, put } on its own line...
 200   if (CommentMarker.empty() && Leading.ends_with("{") &&
 201       Trailing.starts_with("}")) {
 202     cantFail(
 203         Result.Changes.add(replacement(Code, Trailing.take_front(1), "\n}")));
 204     // ...and format it.
 205     Result.FormatRanges.push_back(
 206         tooling::Range(Trailing.data() - Code.data() + 1, 1));
 207   }
 208
 209   // Format the whole leading line.
 210   Result.FormatRanges.push_back(
 211       tooling::Range(Leading.data() - Code.data(), Leading.size()));
 212
 213   // We use a comment to represent the cursor, to preserve the newline.
 214   // A trailing identifier improves parsing of e.g. for without braces.
 215   // Exception: if the previous line has a trailing comment, we can't use one
 216   // as the cursor (they will be aligned). But in this case we don't need to.
 217   Result.CursorPlaceholder = !CommentMarker.empty() ? "ident" : "//==\nident";
 218
 219   return Result;
 220 }
 221
 222 IncrementalChanges getIncrementalChanges(llvm::StringRef Code, unsigned Cursor,
 223                                          llvm::StringRef InsertedText,
 224                                          unsigned TabWidth) {
 225   IncrementalChanges Result;
 226   if (InsertedText == "\n")
 227     return getIncrementalChangesAfterNewline(Code, Cursor, TabWidth);
 228
 229   Result.CursorPlaceholder = " /**/";
 230   return Result;
 231 }
 232
 233 // Returns equivalent replacements that preserve the correspondence between
 234 // OldCursor and NewCursor. If OldCursor lies in a replaced region, that
 235 // replacement will be split.
 236 std::vector<tooling::Replacement>
 237 split(const tooling::Replacements &Replacements, unsigned OldCursor,
 238       unsigned NewCursor) {
 239   std::vector<tooling::Replacement> Result;
 240   int LengthChange = 0;
 241   for (const tooling::Replacement &R : Replacements) {
 242     if (R.getOffset() + R.getLength() <= OldCursor) { // before cursor
 243       Result.push_back(R);
 244       LengthChange += R.getReplacementText().size() - R.getLength();
 245     } else if (R.getOffset() < OldCursor) { // overlaps cursor
 246       int ReplacementSplit = NewCursor - LengthChange - R.getOffset();
 247       assert(ReplacementSplit >= 0 &&
 248              ReplacementSplit <= int(R.getReplacementText().size()) &&
 249              "NewCursor incompatible with OldCursor!");
 250       Result.push_back(tooling::Replacement(
 251           R.getFilePath(), R.getOffset(), OldCursor - R.getOffset(),
 252           R.getReplacementText().take_front(ReplacementSplit)));
 253       Result.push_back(tooling::Replacement(
 254           R.getFilePath(), OldCursor,
 255           R.getLength() - (OldCursor - R.getOffset()),
 256           R.getReplacementText().drop_front(ReplacementSplit)));
 257     } else if (R.getOffset() >= OldCursor) { // after cursor
 258       Result.push_back(R);
 259     }
 260   }
 261   return Result;
 262 }
 263
 264 } // namespace
 265
 266 // We're simulating the following sequence of changes:
 267 //   - apply the pre-formatting edits (see getIncrementalChanges)
 268 //   - insert a placeholder for the cursor
 269 //   - format some of the resulting code
 270 //   - remove the cursor placeholder again
 271 // The replacements we return are produced by composing these.
 272 //
 273 // The text we actually pass to clang-format is slightly different from this,
 274 // e.g. we have to close brackets. We ensure these differences are *after*
 275 // all the regions we want to format, and discard changes in them.
 276 std::vector<tooling::Replacement>
 277 formatIncremental(llvm::StringRef OriginalCode, unsigned OriginalCursor,
 278                   llvm::StringRef InsertedText, format::FormatStyle Style) {
 279   IncrementalChanges Incremental = getIncrementalChanges(
 280       OriginalCode, OriginalCursor, InsertedText, Style.TabWidth);
 281   // Never *remove* lines in response to pressing enter! This annoys users.
 282   if (InsertedText == "\n") {
 283     Style.MaxEmptyLinesToKeep = 1000;
 284     Style.KeepEmptyLines.AtStartOfBlock = true;
 285   }
 286
 287   // Compute the code we want to format:
 288   // 1) Start with code after the pre-formatting edits.
 289   std::string CodeToFormat = cantFail(
 290       tooling::applyAllReplacements(OriginalCode, Incremental.Changes));
 291   unsigned Cursor = Incremental.Changes.getShiftedCodePosition(OriginalCursor);
 292   // 2) Truncate code after the last interesting range.
 293   unsigned FormatLimit = Cursor;
 294   for (tooling::Range &R : Incremental.FormatRanges)
 295     FormatLimit = std::max(FormatLimit, R.getOffset() + R.getLength());
 296   CodeToFormat.resize(FormatLimit);
 297   // 3) Insert a placeholder for the cursor.
 298   CodeToFormat.insert(Cursor, Incremental.CursorPlaceholder);
 299   // 4) Append brackets after FormatLimit so the code is well-formed.
 300   closeBrackets(CodeToFormat, Style);
 301
 302   // Determine the ranges to format:
 303   std::vector<tooling::Range> RangesToFormat = Incremental.FormatRanges;
 304   // Ranges after the cursor need to be adjusted for the placeholder.
 305   for (auto &R : RangesToFormat) {
 306     if (R.getOffset() > Cursor)
 307       R = tooling::Range(R.getOffset() + Incremental.CursorPlaceholder.size(),
 308                          R.getLength());
 309   }
 310   // We also format the cursor.
 311   RangesToFormat.push_back(
 312       tooling::Range(Cursor, Incremental.CursorPlaceholder.size()));
 313   // Also update FormatLimit for the placeholder, we'll use this later.
 314   FormatLimit += Incremental.CursorPlaceholder.size();
 315
 316   // Run clang-format, and truncate changes at FormatLimit.
 317   tooling::Replacements FormattingChanges;
 318   format::FormattingAttemptStatus Status;
 319   for (const tooling::Replacement &R : format::reformat(
 320            Style, CodeToFormat, RangesToFormat, Filename, &Status)) {
 321     if (R.getOffset() + R.getLength() <= FormatLimit) // Before limit.
 322       cantFail(FormattingChanges.add(R));
 323     else if(R.getOffset() < FormatLimit) { // Overlaps limit.
 324       if (R.getReplacementText().empty()) // Deletions are easy to handle.
 325         cantFail(FormattingChanges.add(tooling::Replacement(Filename,
 326             R.getOffset(), FormatLimit - R.getOffset(), "")));
 327       else
 328         // Hopefully won't happen in practice?
 329         elog("Incremental clang-format edit overlapping cursor @ {0}!\n{1}",
 330              Cursor, CodeToFormat);
 331     }
 332   }
 333   if (!Status.FormatComplete)
 334     vlog("Incremental format incomplete at line {0}", Status.Line);
 335
 336   // Now we are ready to compose the changes relative to OriginalCode.
 337   //   edits -> insert placeholder -> format -> remove placeholder.
 338   // We must express insert/remove as Replacements.
 339   tooling::Replacements InsertCursorPlaceholder(
 340       tooling::Replacement(Filename, Cursor, 0, Incremental.CursorPlaceholder));
 341   unsigned FormattedCursorStart =
 342                FormattingChanges.getShiftedCodePosition(Cursor),
 343            FormattedCursorEnd = FormattingChanges.getShiftedCodePosition(
 344                Cursor + Incremental.CursorPlaceholder.size());
 345   tooling::Replacements RemoveCursorPlaceholder(
 346       tooling::Replacement(Filename, FormattedCursorStart,
 347                            FormattedCursorEnd - FormattedCursorStart, ""));
 348
 349   // We can't simply merge() and return: tooling::Replacements will combine
 350   // adjacent edits left and right of the cursor. This gives the right source
 351   // code, but loses information about where the cursor is!
 352   // Fortunately, none of the individual passes lose information, so:
 353   //  - we use merge() to compute the final Replacements
 354   //  - we chain getShiftedCodePosition() to compute final cursor position
 355   //  - we split the final Replacements at the cursor position, so that
 356   //    each Replacement lies either before or after the cursor.
 357   tooling::Replacements Final;
 358   unsigned FinalCursor = OriginalCursor;
 359 #ifndef NDEBUG
 360   std::string FinalCode = std::string(OriginalCode);
 361   dlog("Initial code: {0}", FinalCode);
 362 #endif
 363   for (auto Pass :
 364        std::vector<std::pair<const char *, const tooling::Replacements *>>{
 365            {"Pre-formatting changes", &Incremental.Changes},
 366            {"Insert placeholder", &InsertCursorPlaceholder},
 367            {"clang-format", &FormattingChanges},
 368            {"Remove placeholder", &RemoveCursorPlaceholder}}) {
 369     Final = Final.merge(*Pass.second);
 370     FinalCursor = Pass.second->getShiftedCodePosition(FinalCursor);
 371 #ifndef NDEBUG
 372     FinalCode =
 373         cantFail(tooling::applyAllReplacements(FinalCode, *Pass.second));
 374     dlog("After {0}:\n{1}^{2}", Pass.first,
 375          StringRef(FinalCode).take_front(FinalCursor),
 376          StringRef(FinalCode).drop_front(FinalCursor));
 377 #endif
 378   }
 379   return split(Final, OriginalCursor, FinalCursor);
 380 }
 381
 382 unsigned
 383 transformCursorPosition(unsigned Offset,
 384                         const std::vector<tooling::Replacement> &Replacements) {
 385   unsigned OriginalOffset = Offset;
 386   for (const auto &R : Replacements) {
 387     if (R.getOffset() + R.getLength() <= OriginalOffset) {
 388       // Replacement is before cursor.
 389       Offset += R.getReplacementText().size();
 390       Offset -= R.getLength();
 391     } else if (R.getOffset() < OriginalOffset) {
 392       // Replacement overlaps cursor.
 393       // Preserve position within replacement text, as far as possible.
 394       unsigned PositionWithinReplacement = Offset - R.getOffset();
 395       if (PositionWithinReplacement > R.getReplacementText().size()) {
 396         Offset += R.getReplacementText().size();
 397         Offset -= PositionWithinReplacement;
 398       }
 399     } else {
 400       // Replacement after cursor.
 401       break; // Replacements are sorted, the rest are also after the cursor.
 402     }
 403   }
 404   return Offset;
 405 }
 406
 407 } // namespace clangd
 408 } // namespace clang