[clangd] Implement end-definition-comment inlay hints

[daiyousei-qz]

Summary

This patch implements a new inlay hint feature proposed in https://github.com/clangd/clangd/issues/1634. It introduces a new inlay hint kind BlockEnd which shows a comment-like hint after a definition brace pair, including function/type/namespace. For example,

void foo() {
} ^

In the code shown above, a hint should be displayed at ^ labelling // foo. Such hint only shows when there's no trailing character after the position except whitespaces and optionally ';'.

Also, new configurations are introduced in the inlay hints block

InlayHints:
    BlockEnd: Yes # toggling the feature

[sammccall]

clang-tools-extra/clangd/InlayHints.cpp

653

I don't really like this signature change.

I understand the goal to avoid duplicating the range computation but it seems unlikely to be critical.
Also, the caller could get the line numbers of the {} from the SourceManager and compare those, which should be cheaper than computing the range, so we wouldn't be duplicating all of the work.

[daiyousei-qz]

• addressed many review comment

[daiyousei-qz]

@zyounan np! Feel free to leave your review comments!

@sammccall Thank you for you insightful and detailed review! I addressed many review comments in the updated patch and left things I'm not very sure.

Regarding to Naming, I agree that EndDefinitionComment sounds so tedious but I couldn't come up with a better name. However, I think EndBlock also feel a little strange to me as a public name. If I come across a setting key in InlayHints section named EndBlock, honestly I would be confused by what it would do ("end" could be a verb, and "block" usually make me to think of the local scope block). What about AfterBlock or AfterDefinition?

Regarding to Configuration, I suppose the minimum line number of definition is a very natural parameter for this feature. I doubt we could come up with some good heuristic to conditionally show this hint. Considering how straightforward this parameter its implementation is, I'd prefer to having this around if possible. But I'll let you to decide.

clang-tools-extra/clangd/InlayHints.cpp

745

I agree. What do you think is a good way get the range of the definition block? What I can think of is to walking backwards the expanded token buffer from the ending '}' and searching for the balanced '}'.

753

I'm using printName here to print names for operator overload. Do you have any advice?

759–763

Fixed enum struct. Honestly, just learnt there's such a thing, lol.

clang-tools-extra/clangd/unittests/InlayHintTests.cpp

1564

Added template function. I don't quite understand what you mean by "the function name is an operator". I'm assuming you meant operator overload so closing this one as covered below.

1574

I think just // foo is good enough. Having no "qualifier" could be a privilege for functions since they are usually the majority of the source code. When reading through the source code, people will get that if no prefix is attached, then it's a function. (OFC they'll also see // namespace and .etc, but rare)

Honestly, IMO // foo() is worse than just the name. It could mislead me to think that this may be a complete signature while it is definitely not.

1578

I would argue we don't need hint for a lambda. This hint is only added to long definitions that may introduce a symbol. It is helpful to highlight the boundaries of different declarations. Because of the implementation assumes the hint is added to a NamedDecl, lambda should be safe.

1615

I agree we should avoid very long hints being displayed. Instead of a length cutoff on type, however, I suppose a limit on the entire hint would be much simpler to implement. Do you think that's okay?

[daiyousei-qz]

For a quick peek to the hint:

[zyounan]

Thank you for the update. A few questions:

• Can you add a test with macro expansion? Would we get two inlay hints right after the spelling location? e.g.,

#define Decl_Record \
  struct Widget {  \
    [very long definition that reach `EndDefinitionCommentMinLines`]. \
    struct SubWidget { \
      [another chunk of members.] \
    // not ending with a bracket here!

//  but appears here:
//          v                       v
Decl_Record } // struct SubWidget ; } // struct Widget (Hmm...) ;

• I was thinking if we should add some test cases for C. (I have learned that it is allowed to write a declaration in an expression while C++ doesn't.) For example,

int main(void) {
  _Alignof(struct S {
    [long definition]
  } // Is it suitable to hint here? What do you think?
  );
}

clang-tools-extra/clangd/InlayHints.cpp

285–286

nit: bail out early?

758

nit: assert(Label.empty() && "Label should be empty with FunctionDecl"). might be helpful for debugging.

clang-tools-extra/clangd/unittests/InlayHintTests.cpp

1714

typo: becaus -> because?

[sammccall]

In D150635#4348702, @daiyousei-qz wrote:

Regarding to Naming, I agree that EndDefinitionComment sounds so tedious but I couldn't come up with a better name. However, I think EndBlock also feel a little strange to me as a public name. If I come across a setting key in InlayHints section named EndBlock, honestly I would be confused by what it would do ("end" could be a verb, and "block" usually make me to think of the local scope block). What about AfterBlock or AfterDefinition?

Agreed that "End" looks too much like a verb here. "After" isn't quite right, again because we're trying to describe the thing we're hinting, not where the hint is positioned.
I prefer "Block" over "Definition" exactly because this sort of hint should also be added to local scope blocks (e.g. if bodies) later.

Does BlockEnd address your concern? ("Block" can be a verb but I think there's no risk of confusion here)

Regarding to Configuration, I suppose the minimum line number of definition is a very natural parameter for this feature. I doubt we could come up with some good heuristic to conditionally show this hint. Considering how straightforward this parameter its implementation is, I'd prefer to having this around if possible. But I'll let you to decide.

Right: It's tempting to make it an option, because we don't know what the value should be, and an option is easy to implement.

But these are not good reasons to make it an option:

• an option doesn't substantially change the importance of picking a good default heuristic, because 95+% of people will use it anyway. If we can't find a good default, we shouldn't implement the feature.
• the vast majority of the cost of an option is maintenance and user-facing complexity, rather than implementation

clang-tools-extra/clangd/InlayHints.cpp

278

I think this is a wrong/incomplete check, e.g. Foo(const Foo&) = default is a definition but doesn't have a brace range.

Maybe it's less redundant just to try to get the brace range and then check if it's valid.

292

This is marked done but isn't done.
I'd suggest something like

VisitTagDecl(*D) {
  if (...) {
    string Kind = D->getKindName();
    if (auto *ED = dyn_cast<EnumDecl>(D); ED->isScoped())
     S += ED->isScopedUsingClassTag() ? " class" : " struct";
    addEndDefinitionCommentHint(*D, Kind);
  }
}

738

SkipSemicolon doesn't need to be optional, a trailing semicolon never adds any ambiguity about what the hint is for

744

This is too much arithmetic and fiddly coupling between this function and shouldHintEndDefinitionComment.

Among other things, it allows for confusion between unicode characters (UTF-32), clang bytes (UTF-8), and LSP characters (usually UTF-16). And we do have a bug here: shouldHintEndDefinition provides SkippedChars in clang bytes, but you add it to end.character below which is in LSP characters.

---

Let's redesign a little...

We have a } on some line. We want to compute a sensible part of that line to attach to.
A suitable range may not exist, in which case we're going to omit the hint.

• The line consists of text we don't care about , the }, and then some mix of whitespace, "trivial" punctuation, and "nontrivial" chars.
• the range should always start at the }, since that's what we're really hinting
• to get the hint in the right place, the range should end after the trivial chars, but before any trailing whitespace
• if there are any nontrivial chars, there's no suitable range

so something like:

optional<Range> findBraceTargetRange(SourceLocation CloseBrace) {
  auto [File, Offset] = SM.getDecomposedLoc(SM.getFileLoc(CloseBrace));
  if (File != MainFileID) return std::nullopt;
  StringRef RestOfLine = MainFileBuf.substr(Offset).split('\n').first.rtrim();
  if (!RestOfLine.consume_front("{")) return;
  if (StringRef::npos != Punctuation.find_first_of(" ,;")) return std::nullopt;
  return {offsetToPosition(MainFileBuf, Offset), offsetToPosition(MainFileBuf, Result.bytes_end() - MainFileBuf.bytes_end()};
}

and then call from addEndDefinitionComment, the result is LSPRange already.

745

What do you think is a good way get the range of the definition block?

For class etc: TagDecl::getBraceRange()
For function: getBody()->get{L,R}BracLoc().
For namespace, I don't see a way in the AST. I think it's fine to use the full range, as the namespace and { will almost always be on the same line.

These ranges can be extracted from the specific types in the Visit* methods and passed into addEndDefinitionCommentHint

753

only to be consistent: either print in the same way here vs below, or document why you're doing different things.

(From what's written in the code, it's not clear what the downside is to printName such that we don't use it everywhere)

753

I would print the DeclarationName only, probably
and try to avoid doing different things for different types of decl

754

this is not quite done: we're still passing in the NamedDecl which offers the opportunity to go digging back into the class hierarchy. I think it's better to pass the name and source range in directly to make it clear we're not doing that.

clang-tools-extra/clangd/unittests/InlayHintTests.cpp

1564

oops, indeed it is - can you move one of the operator tests into "methods" and add a non-method one to "functions"?
(Operators aren't really different enough to be separated out, I think)

1574

I'm skeptical, but let's give this a try, we can always add it later.

1578

Up to you, I think a hint would be helpful but no hint is also fine.

In any case, please add a test showing the behavior.

This hint is only added to long definitions that may introduce a symbol

FWIW I don't think this is the greatest value from the hint - rather that *when the scope changes* we get some extra context that the local syntax doesn't provide. (This is why I think lambdas, for loops etc should eventually be hinted)

1610

I think we *probably* just want method2 here: showing qualifiers seems inconsistent with how we otherwise prefer brevity over disambiguation (e.g. not showing params etc)

[daiyousei-qz]

Address review comments

[daiyousei-qz]

Addressed most review comments.

I'm currently using the name "BlockEnd" as suggested. Though I'm proposing a name like "DeclBlockEnd" to make it clearer. What do you think? If we want to broaden the hint, maybe another one named "StmtBlockEnd" could be added.

clang-tools-extra/clangd/InlayHints.cpp

285–286

No longer needed as merged into VisitTagDecl

653

As per another comment below, this change is kept.

738

Yes, no ambiguity. But the following hint looks weird to me:

void foo() {
}; // foo

Since this isn't that complicated to filter them out, I'd prefer making it more precise.

742

Now targeting

1. "}" if this is the only character
2. "};" or "} ;" or alike for enum/class/struct

744

Done, also moved min-line and max-length logic to this function. Btw, I think we should avoid offsetToPosition as much as possible. It is a large overhead considering inlay hints are recomputed throughout the entire file for each edit. I frequently work with source code that's nearly 1MB large (Yes, I don't think we should have source file this large, but it is what it is).

754

Done

758

No longer needed as this assert is removed.

clang-tools-extra/clangd/unittests/InlayHintTests.cpp

1564

Merged test cases

1578

I agree, but the threshold of showing such hint should probably be more conservative since the number could blow up really quickly. I definitely think a hint for a long long if/for/while statement could be very helpful to understand the code structure.

Added test case for lambda. Close this for now since it's not going to be resolved in this patch.

1610

I disagree with this and think the current behavior is consistent. The name we show is exactly the same with what is used to define the symbol. Also, I think the type name is an essential part of a method name.

1615

Added a max length limit of 50 for now.

1714

Good catch!

[sammccall]

Though I'm proposing a name like "DeclBlockEnd" to make it clearer

I prefer the current name. DeclBlockEnd is both too long and contains a cryptic abbreviation (should be DeclarationBlockEnd). And I don't think distinguishing between declaration blocks and flow-control blocks is likely to be helpful.

clang-tools-extra/clangd/InlayHints.cpp

575

can you move this function below the related addBlockEndHint?

578

We actually already have a configurable inlay hint length limit.
It has the wrong name (TypeNameLimit) , but I think we should use it anyway (and maybe try to fix the name later).

(I'm not sure making this configurable was a great idea, but given that it exists, people will expect it to effectively limit the length of hints)

590

nit: Trimed => Trimmed, or just shorten the name

scope of var can be reduced here:

if (StringRef TrailingText = ...; !TrailingText.empty() && ...)
  return std::nullopt

597

this should be getFileLoc(BraceRange.getBegin()), I think?

598

we can drop all the invalid checks. These are ~never going to fire, and aren't the best condition to check when they do fire.

For RBrace, we already know it's in the main file (can't be invalid)
For LBrace, something weird like token-pasting or an inline #include needs to happen for this to be invalid. But if you want to check this, a better test would be to decompose LBrace like you do RBrace and check that the FileID is right. Because if you somehow end up in a different file, the line number will be "valid" but the comparison is not meaningful.

605

motivating comment would be useful here:
// Don't show hints on trivial blocks like class X {};

616

please don't do this, call sourceLocToPosition unless you have benchmarks showing this is a bottleneck on real-world code.

lspLength and direct manipulation of line/character is unneccesarily subtle.
(If the performance matters, there's no need to be computing the LSP line of the lbrace at all - we never use it - this is one reason I think this function has the wrong signature)

653

Please revert this unless you can show a significant performance difference in a real-world setting.

744

also moved min-line and max-length logic to this function

I'd prefer you to move them back. As specified, that function is otherwise strictly about examining the textual source code around the closing brace. Now it's muddled: it also looks at the opening brace, and does lookups into line tables.

You seem to be aiming to optimize an operation that you think is expensive, but I don't see any evidence (measurements) that this implementation is actually faster or that the difference matters.

Btw, I think we should avoid offsetToPosition as much as possible

I understand the concern: computing inlay hints is quadratic. However things are *universally* done this way in clangd, and diverging here won't significantly improve performance but makes the code much harder to understand in context.

In practice we haven't found places where overheads that are length(file)*length(LSP response) are significant compared to parse times. If you have such examples, it would be great to gather & share profiles and propose a solution.
I suspect we could maintain some line lookup data structure that gets updated when source code updates come in over LSP, or something. But micro-optimizing individual codepaths isn't going to get us there: if two offsetToPosition() calls are bad, then one is still bad.

clang-tools-extra/clangd/Protocol.h

1656

nit: update the comment syntax

[daiyousei-qz]

clang-tools-extra/clangd/InlayHints.cpp

616

I argue performance does matter here. I eye-balled inlay hint compute time in clangd's output window from vscode. On "./clang/lib/Sema/SemaOpenMP.cpp" which is around 1MB, using sourceLocToPosition roughly takes around 1250~1350ms. However, using two offsetLocToPosition usually use 1400~1500ms. I think 100ms delta is already a noticeable difference.

[sammccall]

Thanks, I'll try to repro those results.
100ms is significant in absolute terms, but >1s seems unacceptably slow.
I believe VSCode always sends ranges along with latency-sensitive hint requests, I think we currently just post-filter. If we propagate the limits deeper we should be able to filter much earlier and never hit these codepaths at all for 99% of the file.

[sammccall]

clang-tools-extra/clangd/InlayHints.cpp

616

I'm unable to reproduce these results. After verifying EndBlock hints work in an editor:

$ bin/clangd --check=../clang/lib/Sema/SemaOpenMP.cpp
I[15:50:26.357] clangd version 17.0.0
I[15:50:26.358] Features: linux+debug-tidy
...
 I[15:50:26.358] Testing on source file /usr/local/google/home/sammccall/src/llvm-project/clang/lib/Sema/SemaOpenMP.cpp
...
I[15:50:26.428] Building preamble...
I[15:50:31.097] Indexing headers...
I[15:50:32.027] Built preamble of size 53468188 for file /usr/local/google/home/sammccall/src/llvm-project/clang/lib/Sema/SemaOpenMP.cpp version null in 5.60 seconds
I[15:50:32.032] Building AST...
I[15:50:38.857] Indexing AST...
I[15:50:38.975] Building inlay hints
I[15:50:38.993] Building semantic highlighting
I[15:50:39.050] Testing features at each token (may be slow in large files)
...

So that's 18ms for inlay hints after 5.6 seconds to parse the preamble and 6 seconds to parse the main file. (This is a debug build, opt must be faster).

This is on a fairly powerful machine, but surely it can't be 1000x faster than yours - something else must be going on.

[daiyousei-qz]

I'm not sure but 18ms is definitely wrong here, especially for a debug build. In your log, even semantic highlighting builds in 60ms, which looks incorrect. I tried again with TOT clangd and noticed the following pattern.

• If I scroll with vscode, inlay hints typically computes in 10~20ms
• If I edit the source code, inlay hints computes in around 600ms

I'm not sure why that's happening. Maybe @nridge could have a better answer. Somehow, this patch seems introduce a significant slowdown. I'll investigate further to see why that's happening.

[sammccall]

In D150635#4366730, @daiyousei-qz wrote:

I'm not sure but 18ms is definitely wrong here, especially for a debug build. In your log, even semantic highlighting builds in 60ms, which looks incorrect. I tried again with TOT clangd and noticed the following pattern.

• If I scroll with vscode, inlay hints typically computes in 10~20ms
• If I edit the source code, inlay hints computes in around 600ms

That sounds exactly like rebuilding the AST takes ~600ms and computing inlay hints takes <20ms.

After an edit, a request for inlay hints will wait while the AST rebuilds before computing inlay hints, so the request latency will show as ~620ms.

If you think you're seeing something else, please provide repro instructions and logs (with -log=verbose)

[daiyousei-qz]

Yeah, makes sense. Thank you for your insight! I missed the fact that this time include AST build time.

I manually injected a time region into inlayHints, here's part of logs printed for scrolling "offsetToPosition" build:

I[23:36:43.055] <-- textDocument/hover(21)
I[23:36:43.057] --> reply:textDocument/hover(21) 1 ms
I[23:36:43.057] --> textDocument/clangd.fileStatus
I[23:36:44.422] <-- textDocument/inlayHint(22)
E[23:36:44.612] ++++++ Inlay hints takes 189 ms to compute
I[23:36:44.612] --> reply:textDocument/inlayHint(22) 189 ms
I[23:36:44.612] --> textDocument/clangd.fileStatus
I[23:36:44.875] <-- textDocument/inlayHint(23)
E[23:36:45.053] ++++++ Inlay hints takes 178 ms to compute
I[23:36:45.054] --> reply:textDocument/inlayHint(23) 179 ms
I[23:36:45.054] --> textDocument/clangd.fileStatus
I[23:36:45.686] <-- textDocument/inlayHint(24)
E[23:36:45.865] ++++++ Inlay hints takes 178 ms to compute
I[23:36:45.865] --> reply:textDocument/inlayHint(24) 179 ms
I[23:36:45.865] --> textDocument/clangd.fileStatus

And here's logs scrolling "sourceLocToPosition" + "lspLength":

I[23:48:22.875] <-- textDocument/inlayHint(20)
E[23:48:22.890] ++++++ Inlay hints takes 14 ms to compute
I[23:48:22.890] --> reply:textDocument/inlayHint(20) 14 ms
I[23:48:22.890] --> textDocument/clangd.fileStatus
I[23:48:22.907] <-- textDocument/inlayHint(21)
E[23:48:22.922] ++++++ Inlay hints takes 14 ms to compute
I[23:48:22.923] --> reply:textDocument/inlayHint(21) 15 ms
I[23:48:22.923] --> textDocument/clangd.fileStatus
I[23:48:22.974] <-- textDocument/inlayHint(22)
E[23:48:22.988] ++++++ Inlay hints takes 13 ms to compute
I[23:48:22.989] --> reply:textDocument/inlayHint(22) 14 ms
I[23:48:22.989] --> textDocument/clangd.fileStatus
I[23:48:23.787] --> $/progress
I[23:48:23.941] <-- textDocument/inlayHint(23)
E[23:48:23.955] ++++++ Inlay hints takes 14 ms to compute
I[23:48:23.956] --> reply:textDocument/inlayHint(23) 14 ms
I[23:48:23.956] --> textDocument/clangd.fileStatus

(edited, sorry I forgot to restart server)

As this is more than 10x slower, I'm holding my position that we shouldn't use offsetToPosition for LSP features triggered per edit/scroll. 150ms is more than noticeable.

If you want to repro on your side, replace computation of HintStart/HintEnd with the following code

Position HintStart = offsetToPosition(MainFileBuf, RBraceOffset);
Position HintEnd =
    offsetToPosition(MainFileBuf, RBraceOffset + HintRangeText.size());

Btw, it's always fascinating to see how modern computer system is so fast, and in the meantime still so "underpowered" :)

[daiyousei-qz]

• Move computeBlockEndHintRange
• Correct label length limit logic
• Correct line number computation for '{'
• Address other review comments

[daiyousei-qz]

Addressed review comments except for those we don't have an agreement yet.

clang-tools-extra/clangd/InlayHints.cpp

578

TypeNameLimit was introduced to limit the length of "DeducedTypes" only. I don't think using that number for all hints is a good idea because different hints appear in different contexts. For deduced type hint, it is displayed in the middle of the actual code, so it must be concise to not overwhelm the actual code. However, this hint is usually displayed at the end of an almost empty line. A much larger number of characters should be allowed.

(I'm not arguing here, but IMO such options are definitely helpful. Not everybody would fork llvm-project and build their own version of clangd binary. Without options to configure length of hints, people would disable "DeducedTypes" entirely if they cannot tolerate the default length limit, while this feature is definitely a cool thing to turn on. Personally, I actually think clangd has too little option compared to say rust-analyzer. But it's just my understanding)

597

Thanks for pointing out! As per comments below, calling getLineNumber instead of getSpellingLineNumber in the latest version.

744

I'd prefer you to move them back. As specified, that function is otherwise strictly about examining the textual source code around the closing brace. Now it's muddled: it also looks at the opening brace, and does lookups into line tables.

Moved max-length logic back, but kept the block line number check there because the line number of RBrace is readily available in this function. I don't see why we need to duplicate code to obtain that line number.

[nridge]

clang-tools-extra/clangd/InlayHints.cpp

578

For deduced type hint, it is displayed in the middle of the actual code, so it must be concise to not overwhelm the actual code. However, this hint is usually displayed at the end of an almost empty line. A much larger number of characters should be allowed.

Another consideration besides the location of the hint that is worth keeping in mind, is what type of content is being printed.

Type names in C++ are composable in ways that identifiers are not (e.g. vector<basic_string<char, char_traits<char>, allocator<char>, allocator<basic_string<...>> etc.), such that there is a need to limit type hints that doesn't really apply to say, parameter hints.

So, a question I have here is: can template argument lists appear in an end-definition-comment hint?

For example, for:

template <typename T>
struct S {
  void foo();
};

template <typename T>
void S::foo() {
}  // <--- HERE

is the hint at the indicated location S::foo(), or S<T>::foo()? In the latter case, we can imagine the hint getting long due to the type parameters, and we may want to consider either limiting its length, or tweaking the code to not print the type parameters.

[daiyousei-qz]

clang-tools-extra/clangd/InlayHints.cpp

578

Yes, currently this hint is only shown if the total length of hint label is less than 60 characters. I believe what we display should be exactly what is used to define the symbol. In your example,

template <typename T>
struct S {
  void foo();
};

template <typename T>
void S<T>::foo() {
}  // S<T>::foo

Basically, "[A]" and "[B]" is the same text (OFC excluding whitespaces).

void [A]() {
} // [B]

The hint won't be displayed if "[B]" is more than 60 characters.

[sammccall]

150ms is more than noticeable

Fair enough. I also see we *are* avoiding the quadratic algorithm in other places in inlay hints, and that we can't easily reuse the getHintRange() function in any case without switching to handling tokens instead of strings. So overall I think the current version is fine. Thanks for digging into this!

clang-tools-extra/clangd/Config.h

150

this needs to be false initially (a month or so?) so we have a chance to try it out in practice, ensure it's not too spammy/has crashes etc, then we can flip on by default

clang-tools-extra/clangd/InlayHints.cpp

578

OK, I'm sold on wanting a higher limit here, and a hard-coded 60 as a limit on the hint seems simple and reasonable for now. We can iterate on this.

(There's another case with arbitrary types being printed: operator vector<int> or so)

653

OK, I'm convinced we need this. Not for performance, but because it's not natural to obtain a closed token range in this case where we're manipulating character by character.

802

I'd prefer sourceLocToPosition(SM, RBraceLoc.getLocationWithOffset(HintRangeText.size())) which would avoids such low-level conversion between coordinate systems, and seems to perform just fine (we're going to hit SourceManager's caches).

Will leave this up to you though.

clang-tools-extra/clangd/Protocol.cpp

1438

nit: move the comment to the return statement rather than repeating it

[daiyousei-qz]

• Address remaining comments

[daiyousei-qz]

Addressed the remaining comments. Thanks everyone for helping review and improve this patch!

clang-tools-extra/clangd/InlayHints.cpp

802

Yeah, this is definitely clearer. Updated.