Horrible performance when formating a large file with many changes

[daiyousei-qz]

Say a file of size S has N independent ranges of changes. When formatting it via LSP, N independent requests are issued and for each request, in clang::format::internal::reformat, clang::tooling::applyAllReplacements is called M times where M is the number of formatting passes. In applyAllReplacements, the entire file content is at least copied once. So at least S * N * M bytes will be copied. Depending on the size of the file and the number of independent ranges, this number could easily reach gigabytes and basically editor will hang.

This is technically not a clangd issue, but a defect from clang-format and LSP. Note someone has already proposed a change to LSP to solve the issue. See also microsoft/vscode#158776 and microsoft/language-server-protocol#1536. I suppose clangd should add support for that once it lands.

[tom-anders]

Looks like clang-format already supports multiple ranges, so seems like implementation in clangd would be rather straightforward, here's a draft implementing the protocol changes proposed in microsoft/language-server-protocol#1536.