[clangd] Support `#pragma mark` in the outline

[dgoldman]

Summary

Xcode uses #pragma mark - to draw a divider in the outline view
and #pragma mark Note to add Note in the outline view. For more
information, see https://nshipster.com/pragma/.

Since the LSP spec doesn't contain dividers for the symbol outline,
instead we treat #pragma mark - as a group with children - the
decls that come after it.

Work left to do:

• Support some edge cases where the document symbols may not be nested / sorted properly.

• Consider supporting #pragma marks before any decls

• Consider supporting the following:

#pragma mark -
#pragma mark Bar

by treating it like #pragma mark - Bar instead of an unnamed
group followed by a named mark.

[dgoldman]

Minor TODO change

[dgoldman]

Fix clang tidy warnings

[kadircet]

So first of all, it is not clear to me if this is a useful enough improvement to justify all the new code, but looking at your investment I'll assume this is really common in ObjC land and gonna be useful for developers working with ObjC. That's enough of a justification for me, but I'd be more than happy to see some real data if you have any.

That being said, reading the code it seems like the intent is enabling #pragma mark directives the introduce symbols that are either leaves or containers:

• Leaf case is obvious and straightforward, it is just like a normal declaration happening at that particular location. It is unclear which kind should be used. It seems you've went with File but I don't think it is suitable in this case. I would suggest using Null.
• Container case is more sophisticated. One thing is for sure, they are nested under the same symbol a declaration occuring at that point would be. They also seem to contain all the symbols that would nest under current subtree and spelled after the mark and spelled before any other marks. Hence there is no way to explicitly terminate the scope of a mark. They are implicitly terminated by hitting the end of the container containing the mark or hitting a new mark directive. This also implies one cannot have multiple levels of nesting just by pragma directives, but it can be achieved if there are usual containers with more mark directives (see my comment around tests for an example).

Can you verify that I understood the intent correctly and make it more explicit in the comments as well?

(Terminating containers implicitly sounds like an unfortunate limitation to me. I'd rather only enable termination of them explicitly) but I suppose there's a lot of code that's already existing out in the world with the assumption of XCode's implicit termination rules, so this is probably not gonna be helpful in reality. Hence we can't do much.)

Before diving into the details of the implementation it looks like we are doing some post-processing to incorporate mark pragmas into the tree, why can't we just insert them while building the tree as we do with macros? for example:

• when inserting a symbol we look for a possible mark-pragma container (similar to macro case), a mark pragma is only eligible as a container if it is contained within the range of the parent && spelled before current declaration at hand && is a group.
• as for insertion of leaves, after traversal of all the children we can just add any mark pragmas that occured within the current symbol's range as a child. we can also drop any mark pragmas occuring inside symbols that doesn't require child traversal this way.

This approach relies on the fact that range calculated by declToSym will be correct enough. I think it should be good in most cases, but might require some adjustments around macros, as usual (can't think of a problematic example right now though).
This brings out the question about ordering of children in DocumentSymbol, lsp doesn't say anything about it today, but during rendering we can just order these based on the selectionRange (probably during build) and hope that clients will preserve it.

I believe implementing it as part of the traversal rather than as post processing both makes code easier to reason about and more efficient. So WDYT about going in that direction?

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

1053

probably a little mix of token vs char ranges.

1055

can you also add something like:

#pragma mark - Foo
struct Foo {
  #pragma mark - Bar
  void bar() {
     #pragma mark - NotTopDecl // I don't think we want this to be part of documentsymbol.
  }
};
void bar() {}

1122

yikes, this looks bad, but also a little bit confusing to be added with this change. Can you move it to a separate one? (or just create a bug report in github/clangd/clangd).

[dgoldman]

In D105904#2877184, @kadircet wrote:

So first of all, it is not clear to me if this is a useful enough improvement to justify all the new code, but looking at your investment I'll assume this is really common in ObjC land and gonna be useful for developers working with ObjC. That's enough of a justification for me, but I'd be more than happy to see some real data if you have any.

Yep, I can you send you some searches internally with how prevalent they are.

That being said, reading the code it seems like the intent is enabling #pragma mark directives the introduce symbols that are either leaves or containers:

• Leaf case is obvious and straightforward, it is just like a normal declaration happening at that particular location. It is unclear which kind should be used. It seems you've went with File but I don't think it is suitable in this case. I would suggest using Null.
• Container case is more sophisticated. One thing is for sure, they are nested under the same symbol a declaration occuring at that point would be. They also seem to contain all the symbols that would nest under current subtree and spelled after the mark and spelled before any other marks. Hence there is no way to explicitly terminate the scope of a mark. They are implicitly terminated by hitting the end of the container containing the mark or hitting a new mark directive. This also implies one cannot have multiple levels of nesting just by pragma directives, but it can be achieved if there are usual containers with more mark directives (see my comment around tests for an example).

Can you verify that I understood the intent correctly and make it more explicit in the comments as well?

Yep, although there are some TODOs there, we could allow letting leaf nodes to be contained in a group parent as well as potentially merging them in the #pragma mark - followed by #pragma mark Foo case.

There's no good kind at the moment IMO, I don't really have a preference as long as it doesn't render awkwardly in VS Code.

(Terminating containers implicitly sounds like an unfortunate limitation to me. I'd rather only enable termination of them explicitly) but I suppose there's a lot of code that's already existing out in the world with the assumption of XCode's implicit termination rules, so this is probably not gonna be helpful in reality. Hence we can't do much.)

I don't think this an Xcode limitation really - more of an LSP spec limitation. If we create a group inside of another symbol, we are effectively contained in it and cannot escape without violating the spec, right? To be clear, Xcode rules are a bit different - see the link above - the #pragma mark - just creates a divider which we can't mirror.

Before diving into the details of the implementation it looks like we are doing some post-processing to incorporate mark pragmas into the tree, why can't we just insert them while building the tree as we do with macros? for example:

• when inserting a symbol we look for a possible mark-pragma container (similar to macro case), a mark pragma is only eligible as a container if it is contained within the range of the parent && spelled before current declaration at hand && is a group.

This assumes (like this code today) that the nodes are sorted properly and the ranges of the parent are accurate. I was thinking of adding a proper sort in a post-processing phase but maybe we could do it + range fix up during insertion. Seems complicated to move everything over to insertion, but if you think that's reasonable, I can try that out.

And that case generally works but we need to be sure to handle multiple pragmas next to each other. #pragma mark - Foo\n#pragma mark - Bar turns Foo into an empty group and Bar takes decls after. And then, currently, a #pragma mark Third would end the group as well.

• as for insertion of leaves, after traversal of all the children we can just add any mark pragmas that occured within the current symbol's range as a child. we can also drop any mark pragmas occuring inside symbols that doesn't require child traversal this way.

I think it's a bit more complicated since the leaf nodes terminate the groups. As long as we do that it should be fine, assuming editors don't require it to be sorted.

This approach relies on the fact that range calculated by declToSym will be correct enough. I think it should be good in most cases, but might require some adjustments around macros, as usual (can't think of a problematic example right now though).
This brings out the question about ordering of children in DocumentSymbol, lsp doesn't say anything about it today, but during rendering we can just order these based on the selectionRange (probably during build) and hope that clients will preserve it.

I believe implementing it as part of the traversal rather than as post processing both makes code easier to reason about and more efficient. So WDYT about going in that direction?

We could - I considered it, but with the existing behavior and potential subtle ordering issues I thought it would be simpler, but less efficient to do it after. I took a look at the Macro Expansion code and didn't understand it + potential edge cases well enough to add it there.

[kadircet]

In D105904#2877281, @dgoldman wrote:

Yep, I can you send you some searches internally with how prevalent they are.

Thanks!

I don't think this an Xcode limitation really - more of an LSP spec limitation. If we create a group inside of another symbol, we are effectively contained in it and cannot escape without violating the spec, right? To be clear, Xcode rules are a bit different - see the link above - the #pragma mark - just creates a divider which we can't mirror.

Sorry I don't follow what you mean here. I was talking about inability to have something like:

#pragma mark -Foo
  #pragma mark -Bar
  #pragma mark SPECIAL_BAR_END
#pragma mark SPECIAL_FOO_END

By making sure groups are terminated explicitly we gain the ability to nest them, whereas otherwise -Bar above will always terminate the previous group implicitly.

This assumes (like this code today) that the nodes are sorted properly and the ranges of the parent are accurate.

Well it is not as strong as that. We'll mostly rely on the fact that symbols are nested properly. Since we just need to figure out the mark container for a symbol, we don't care about the ordering (or am I missing something here?).
OTOH, range of the parent being accurate is indeed required. I think today it is only broken for macro parents, but hopefully it shouldn't cause as any troubles as in all the practical cases these are still contained inside an AST node (I think), e.g:

#define FOO(X) class X
FOO(Bar) {
#pragma mark -Test
void bar();
}

-Test mark is contained in class X so it can be nested properly. I don't think it is ever possible to have it nest directly under a macro name since you can't have other PP directives expanded from macros (even though it is probably possible via weird tricks like __pragma/_Pragma).
Now ranges for the pragma-mark containers will also be broken, but again it is not a problem as we are never going to attach any pragma-mark symbols directly into another pragma-mark (they'll either be siblings or there'll be a regular AST node in between, as explained previously).

I was thinking of adding a proper sort in a post-processing phase but maybe we could do it + range fix up during insertion. Seems complicated to move everything over to insertion, but if you think that's reasonable, I can try that out.

As explained above, I think we can just keep adjusting the ranges after building the tree as we do today. Let me know if I am missing something though.

I think it's a bit more complicated since the leaf nodes terminate the groups. As long as we do that it should be fine, assuming editors don't require it to be sorted.

Well actually handling the leafs that terminate the group they are contained in is easy (since we'll make use of the closest mark-pragma to the declaration), but the other way around is hard, e.g:

#pragma mark -Foo
class X {
  #pragma mark -Bar
};
void foo();

foo above needs to be nested under Foo, even though the closest mark-pragma is Bar. I think these can be handled more naturally by making sure we throw away mark-pragmas contained inside a symbol after processing the containing symbol (e.g. Bar will be dropped from our container after X has been inserted into the tree).

We could - I considered it, but with the existing behavior and potential subtle ordering issues I thought it would be simpler, but less efficient to do it after.

Does my new set of comments help clarify things a little more? I don't think we need any ordering guarantees, we mostly rely on the fact that mark-pragmas will be sorted properly and symbols are nested correctly.

I took a look at the Macro Expansion code and didn't understand it + potential edge cases well enough to add it there.

I don't think this should directly go into the macro parent logic, but rather be orthogonal. Then we can just chain them, by first looking for a macro container and then looking for a mark-pragma one above that container (since we know the other-way around is not possible, i.e. a mark-pragma cannot nest directly under a macro).

[sammccall]

In D105904#2877184, @kadircet wrote:

So first of all, it is not clear to me if this is a useful enough improvement to justify all the new code, but looking at your investment I'll assume this is really common in ObjC land and gonna be useful for developers working with ObjC. That's enough of a justification for me, but I'd be more than happy to see some real data if you have any.

+1. I think the key for this kind of feature is isolating the complexity so it doesn't need to be part of the core mental model of how the feature works.
For macros I basically failed to do this, but I think we can do better here.

Can you verify that I understood the intent correctly and make it more explicit in the comments as well?

Yes, I think the comments should explain how these marks are used without assuming any prior knowledge.
Simplest reason for this is that the impl language for clangd is not objc, and the technique seems basically unknown elsewhere.

Before diving into the details of the implementation it looks like we are doing some post-processing to incorporate mark pragmas into the tree, why can't we just insert them while building the tree as we do with macros?

OK, this is why I'm jumping in here...
I think the fact that we do macros as-we-go is bad but unavoidable. It forces the core algorithm to think about symbol nesting and macro expansion at the same time, and makes the code much harder to reason about than if they were completely separate.

I didn't manage to separate them because macros are so complicated - we need the detailed SourceLocation info, to account for cases where they don't nest concentrically, etc. But this failure isn't something we should be consistent about - the more features that are part of the central algorithm, the exponentially more interactions there are to worry about.

However those difficulties don't apply here - I believe you can take the current final representation (vector<DocumentSymbol>) + the list of marks and produce a markified vector<DocumentSymbol> via a fairly natural tree walk. And this does a *really* good job of isolating this feature - we literally run the rest of the algorithm without it.
(This is slightly different to what's done in the patch, I would actually take it out of the DocumentOutline class entirely).
I don't think this hurts efficiency much (I think/hope this ends up being a move rather than a copy for most nodes). And I think it actually makes the markifying code easier to reason about in this case, as it just deals with line numbers/positions, without having the distraction of SourceLocation.

@kadircet WDYT of this argument, before we make David go back and forth?

clang-tools-extra/clangd/ParsedAST.cpp

430

You'll need to do this with marks as well (collect + merge), or you'll miss marks from the preamble region.
Make sure there's a test for this (it's not necessary to actually have any includes, I think)

clang-tools-extra/clangd/Protocol.h

198 ↗

(On Diff #358606)

This doesn't belong in Protocol.h, rather in SourceCode.h or so - these aren't domain objects and adding logic to them can end up causing layering issues in general.
(There are some exceptions for good and bad reasons, but not many. I'm not sure why Range::contains is here)

Maybe union() to be a little less ambiguous?

clang-tools-extra/clangd/TextMarks.h

22 ↗

(On Diff #358606)

This seems like premature abstraction - you don't handle TODOs here, nor are they appropriate for the single use case we have. Moreover they don't satisfy the definition here: int foo; // TODO: turn into a float the TODO doesn't occupy the whole line.

If we need it, the appropriate generalization seems just as likely to be "pragmas" or "directives" as "textual marks".

Similarly, it's not clear that the logic around interpreting the strings e.g. as groups needs to be shared across features, nor is it terribly complicated.
So the interface here seems like it could be much simpler:

struct PragmaMark {
  unsigned Line;
  string Text;
}
unique_ptr<PPCallbacks> collectPragmaMarksCallback(const SourceManager&, vector<PragmaMark> &Out);

I'd suggest putting this in CollectMacros.h (which would be misnamed but not terribly, or we could always rename) rather than adding a new header.

45 ↗

(On Diff #358606)

please avoid puttng bodies inline unless trivial or hot

[kadircet]

However those difficulties don't apply here - I believe you can take the current final representation (vector<DocumentSymbol>) + the list of marks and produce a markified vector<DocumentSymbol> via a fairly natural tree walk. And this does a *really* good job of isolating this feature - we literally run the rest of the algorithm without it.
(This is slightly different to what's done in the patch, I would actually take it out of the DocumentOutline class entirely).
I don't think this hurts efficiency much (I think/hope this ends up being a move rather than a copy for most nodes). And I think it actually makes the markifying code easier to reason about in this case, as it just deals with line numbers/positions, without having the distraction of SourceLocation.
@kadircet WDYT of this argument, before we make David go back and forth?

As discussed offline, I am sold. In the end both this approach and inserting marks as we build the tree share a lot in common. In both cases when inserting a node into the tree we need to figure out whether it should go under the current parent or there's a mark that should contain that node, which is possibly not present in the tree yet. Instead of looking at ast nodes, it is definitely more reasonable to look at the document symbol nodes. Also as you mentioned doing this afterwards definitely does a better job at isolating this from the rest + enables us to fix up ranges/ordering of the tree produced from ast.

Sorry for the hassle here David :/

[dgoldman]

Rebase

[dgoldman]

In D105904#2879445, @kadircet wrote:

In D105904#2877281, @dgoldman wrote:

Yep, I can you send you some searches internally with how prevalent they are.

Thanks!

I don't think this an Xcode limitation really - more of an LSP spec limitation. If we create a group inside of another symbol, we are effectively contained in it and cannot escape without violating the spec, right? To be clear, Xcode rules are a bit different - see the link above - the #pragma mark - just creates a divider which we can't mirror.

Sorry I don't follow what you mean here. I was talking about inability to have something like:

#pragma mark -Foo
  #pragma mark -Bar
  #pragma mark SPECIAL_BAR_END
#pragma mark SPECIAL_FOO_END

By making sure groups are terminated explicitly we gain the ability to nest them, whereas otherwise -Bar above will always terminate the previous group implicitly.

Ah I see what you mean. Xcode has implicit termination - the #pragma mark - Foo just makes a horizontal line and labels Foo after, so a subsequent #pragma mark - Bar ends up creating a new line, ending the previous. There's too much relying on this behavior for us to change it. My point was we can't avoid an implicit end here of the Foo mark due to how we nest things, so either way we'd have some form of implicit termination:

@interface Foo
#pragma mark - Foo
@end

In D105904#2879750, @sammccall wrote:

However those difficulties don't apply here - I believe you can take the current final representation (vector<DocumentSymbol>) + the list of marks and produce a markified vector<DocumentSymbol> via a fairly natural tree walk. And this does a *really* good job of isolating this feature - we literally run the rest of the algorithm without it.
(This is slightly different to what's done in the patch, I would actually take it out of the DocumentOutline class entirely).
I don't think this hurts efficiency much (I think/hope this ends up being a move rather than a copy for most nodes). And I think it actually makes the markifying code easier to reason about in this case, as it just deals with line numbers/positions, without having the distraction of SourceLocation.

That seems reasonable, it seems quite similar to this, we can probably simplify it if we remove the requirement that the children are in order. Note that my current approach doesn't really add much overhead if the absence of the TextMarks, but we should be able to special case that there as well.

clang-tools-extra/clangd/TextMarks.h

22 ↗

(On Diff #358606)

We don't handle them at the moment, but Xcode does (for both Swift + ObjC): https://medium.com/@cboynton/todo-make-your-notes-on-xcode-stand-out-5f5124ec064c. You're right that they don't necessarily have to occupy the whole line though, it's possible to have multiple per line although I'm not sure how often that is used in practice.

[sammccall]

clang-tools-extra/clangd/TextMarks.h

22 ↗

(On Diff #358606)

This seems like a very different case, and I'm not convinced we should support it.

That #pragma marks are used for grouping seems like the strongest argument for including them in the outline. TODOs are not used for grouping.

The majority of #pragma marks are written with XCode's conventions in mind, the majority of TODO comments are not. So there's a real question of whether authors want this. (And whether it should include all comments, or other kinds of structured comments...)

I'd suggest keeping the scope small and concrete. If you'd like to add abstractions because more cases are imminent, we probably need to get consensus on (some of) these cases first.

[dgoldman]

clang-tools-extra/clangd/TextMarks.h

22 ↗

(On Diff #358606)

Technically Xcode also supports // MARK comments as well, but almost all users internally use #pragma mark. I do think the TODO/FIXME in the outline could be useful (Xcode does it...), but if you're against it I'll remove this.

[dgoldman]

Well it is not as strong as that. We'll mostly rely on the fact that symbols are nested properly. Since we just need to figure out the mark container for a symbol, we don't care about the ordering (or am I missing something here?).
OTOH, range of the parent being accurate is indeed required. I think today it is only broken for macro parents, but hopefully it shouldn't cause as any troubles as in all the practical cases these are still contained inside an AST node (I think), e.g:

I think the difficulty is when you "figure out the mark container for a symbol" since we implicitly scope the mark containers based on their location, it's possible the closest #pragma isn't the right container. I'm not sure of a simple way to do that without sorting, LMK if you have some ideas.

[dgoldman]

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

1122

I'm not sure this is worth disregarding just yet, if we're not able to fix this at the clang level we might want to consider a clangd-style fix here (which actually would behave similar to what we have right now with the text marks needing to be merged in).

[dgoldman]

Fetch marks from preamble as well

Move Range helper into SourceCode.h

[sammccall]

Thanks. AFAIK this is now waiting on you David with Kadir to review impl.

In D105904#2881329, @dgoldman wrote:

I think the difficulty is when you "figure out the mark container for a symbol" since we implicitly scope the mark containers based on their location, it's possible the closest #pragma isn't the right container. I'm not sure of a simple way to do that without sorting, LMK if you have some ideas.

I tried to work through this and yes I think you need the containers to be sorted. (If only because otherwise you have to reorder children within a container to group them, which is bizarre). If we do this with postprocessing, then where we fix-up the ranges is a good time to sort too. And mark insertion can preserve range nesting/sorting.
If the nesting is "incorrect" (siblings are not disjoint as in the function-in-@implementation example you gave) there doesn't seem to always be a great answer. For now I think it's OK to do something "wrong" in that case, as long as it's not infloop/crash.

clang-tools-extra/clangd/TextMarks.h

22 ↗

(On Diff #358606)

I think // MARK is so rarely used to be worth ignoring for now.

I think including TODO/FIXME is *probably* not great (unlike xcode, we can't tailor the UI to it and it doesn't seem to fit LSP).

We can always discuss and work out generalize later though, mostly I'm against adding the abstraction now just in case we have the discussion later.

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

1122

Let's not disregard it, but we definitely need to think about it in a comprehensive way that isn't specific to this patch.

e.g. all selection operations (hover, go-to-definition, etc) fail inside such a function, because it violates the almost-rule that the AST corresponds to the lexical structure.

[dgoldman]

Rebase and remove TextMark files

[dgoldman]

Removed the TextMarks file, just need to swap over how the insertions are done

clang-tools-extra/clangd/TextMarks.h

45 ↗

(On Diff #358606)

Ah CollectMacros has lots of stuff inline, so I mirrored that, doesn't look like many other file do that though

[dgoldman]

Merge pragmas outside of the DocumentOutline

[dgoldman]

Misc vector changes

[dgoldman]

PTAL, now merge outside of DocumentOutline although the algorithm I've used is roughly the same

[sammccall]

clang-tools-extra/clangd/CollectMacros.cpp

23

Interpretation of the marks belongs with the rest of the DocumentSymbol code too, I think - until we have some evidence that this is structure we want to share.

52

This code belongs with the rest of the DocumentSymbol code

clang-tools-extra/clangd/CollectMacros.h

106

Line number is enough, right?
Column is not interesting, and pragma marks expanded from macros are not possible (and wouldn't be in the main file for our purposes)

115

this should be tested in CollectMacrosTests.cpp or ParsedASTTests.cpp
(It's fine to test via TestTU though, and this will let you test both the preamble and non-preamble case)

[sammccall]

clang-tools-extra/clangd/FindSymbols.cpp

535

FWIW the flow control/how we make progress seem hard to follow here to me.

In particular I think I'm struggling with the statefulness of "is there an open mark group".

Possible simplifications:

• define a dummy root symbol, which seems clearer than the vector<symbols> + range
• avoid reverse-sorting the list of pragma symbols, and just consume from the front of an ArrayRef instead
• make the outer loop over pragmas, rather than symbols. It would first check if the pragma belongs directly here or not, and if so, loop over symbols to work out which should become children. This seems very likely to be efficient enough in practice (few pragmas, or most children are grouped into pragmas)

[dgoldman]

Fixes for review

[dgoldman]

clang-tools-extra/clangd/CollectMacros.h

106

No, I think the column is useful, ideally we would point directly to the text that the user has although currently we point to the mark symbol.

clang-tools-extra/clangd/FindSymbols.cpp

535

define a dummy root symbol, which seems clearer than the vector<symbols> + range

I guess? Then we'd take in a `DocumentSymbol & and a ArrayRef<PragmaMarkSymbol> & (or just by value and then return it as well). The rest would be the same though

In particular I think I'm struggling with the statefulness of "is there an open mark group".

We need to track the current open group if there is one in order to move children to it.

make the outer loop over pragmas, rather than symbols. It would first check if the pragma belongs directly here or not, and if so, loop over symbols to work out which should become children. This seems very likely to be efficient enough in practice (few pragmas, or most children are grouped into pragmas)

The important thing here is knowing where the pragma mark ends - if it doesn't, it actually gets all of the children. So we'd have to peak at the next pragma mark, add all symbols before it to us as children, and then potentially recurse to nest it inside of a symbol. I'll try it out and see if it's simpler.

[dgoldman]

Add in suggested algorithm

[dgoldman]

clang-tools-extra/clangd/FindSymbols.cpp

535

I've implemented your suggestion. I don't think it's simpler, but LMK, maybe it can be improved.

[dgoldman]

minor comment fix

[dgoldman]

Test collectPragmaMarksCallback + preamble merging

[dgoldman]

clang-tools-extra/clangd/TextMarks.h

22 ↗

(On Diff #358606)

Thought of another use case - for code folding it would be nice to let the #pragma marks fold. Not sure if ya'll are planning to ship clangd's code folding though.

[kadircet]

clang-tools-extra/clangd/CollectMacros.cpp

13

can you nest this inside clang::clangd and drop the qualifiers ?

20

nit: drop braces

clang-tools-extra/clangd/CollectMacros.h

106

okay then let's store a Range here instead, and get rid of the dependency on a SourceManager for rendering it maybe?

clang-tools-extra/clangd/FindSymbols.cpp

535

while(Pragmas) {
// We'll figure out where the Pragmas.front() should go.
Pragma P = Pragmas.front();
DocumentSymbol *Cur = Root;
while(Cur->contains(P)) {
  auto *OldCur = Cur;
  for(auto *C : Cur->children) {
     // We assume at most 1 child can contain the pragma (as pragmas are on a single line, and children have disjoint ranges)
     if (C->contains(P)) {
         Cur = C;
         break;
     }
  }
  // Cur is immediate parent of P
  if (OldCur == Cur) {
    // Just insert P into children if it is not a group and we are done.
    // Otherwise we need to figure out when current pragma is terminated:
// if next pragma is not contained in Cur, or is contained in one of the children, It is at the end of Cur, nest all the children that appear after P under the symbol node for P.
// Otherwise nest all the children that appear after P but before next pragma under the symbol node for P.
// Pop Pragmas and break
  }
}
}

Does that make sense, i hope i am not missing something obvious? Complexity-wise in the worst case we'll go all the way down to a leaf once per pragma, since there will only be a handful of pragmas most of the time it shouldn't be too bad.

682

I think this reads easier:

bool IsGroup = Name.consume_front("-");
Name = Name.ltrim();
if (Name.empty())
  Name = IsGroup ? "unnamed group" : ...;

[kadircet]

clang-tools-extra/clangd/FindSymbols.cpp

535

oops, i was looking into an older revision and missed mergepragmas2, i think it looks quite similar to this one but we can probably get rid of the recursion as well and simplify a couple more cases

[dgoldman]

clang-tools-extra/clangd/FindSymbols.cpp

535

This makes sense, I think that works for the most part besides dropping the recursion, specifically for

// Next pragma is contained in the Sym, it belongs there and doesn't
// affect us at all.
if (Sym.range.contains(NextPragma.DocSym.range)) {
  Sym.children = mergePragmas2(Sym.children, Pragmas, Sym.range);
  continue;
}

I guess we could explicitly forbid 3+ layers of nesting and handle it inline there? But I'm not sure it's worth the effort to rewrite all of this - the recursion shouldn't be deep and we avoid needing to shift vector elements over by recreating a new one.

[dgoldman]

More fixes for review

clang-tools-extra/clangd/CollectMacros.cpp

13

Done, had to keep clangd qualifier to prevent mixup with the function below, otherwise I get error: call to non-static member function without an object argument

clang-tools-extra/clangd/FindSymbols.cpp

682

That behavior is slightly different, we want to treat #pragma mark -Foo as -Foo non group but #pragma mark - Foo as Foo group.

[kadircet]

clang-tools-extra/clangd/FindSymbols.cpp

535

Sorry I don't follow why we can't get rid of the recursion in this case.

Two loop solution I described above literally tries to find the document symbol node, such that the current pragma is contained in that node && current pragma isn't contained in any of that node's children. Afterwards it inserts the pragma into that node and starts traversing the tree from root again for the next pragma.

Again I don't follow where the 3+ layers of nesting constraint came from. But I do feel like the iterative version is somewhat easier to reason about (especially keeping track of what's happening with pragmas.front() and the way it bails out via parentrange check). Shifting of the vector is definitely unfortunate but I think it shouldn't imply big performance hits in practice as we are only shifting the children of a single node.

682

oh I see. I indeed missed the \s+ in the comment assumed it was \s*.
Is it really important to have that difference? If so, it might be useful to spell it out explicitly (e.g. -Foo is not considered as a group)

[dgoldman]

clang-tools-extra/clangd/FindSymbols.cpp

535

Yeah, I understand the first part, I think specifically handling the group case after you discover where it needs to be inserted is a bit more complicated, something like the following:

// Pragma is a group, so we need to figure out where it terminates:
// - If the next Pragma is not contained in Cur, P owns all of its
//   parent's children which occur after P.
// - If the next pragma is contained in Cur but actually belongs to one
//   of the parent's children, we temporarily skip over it and look at
//   the next pragma to decide where we end.
// - Otherwise nest all of its parent's children which occur after P but
//   before the next pragma.

And yeah, shifting in the worst case is definitely worst (due to repeat shifting) although it shouldn't be too common in practice (things like a large @implementation block would probably have the most children).

[kadircet]

clang-tools-extra/clangd/FindSymbols.cpp

535

we temporarily skip over it and look at the next pragma to decide where we end.

Ah you are right I was missing this part. As you suggested we'll need to loop over all the remaining pragmas, which will make the complexity ((quadratic in terms of # of pragmas) * (depth of document symbol tree)) I think it is still acceptable in practice. I don't think there'll be more than a dozen pragmas in a file. (moreover i think this problem exists with the current implementation you've provided, see my comment below)

Are you fine with reshaping the implementation in that way then? Because I still feel like the code will end up looking a lot more straightforward, even if not the most optimal and we can try to optimize the rest if it shows up in the latency graphs.

664

I suppose this is not correct in cases like.

#pragma mark - Outer
foo {
  #pragma mark - Foo
}
bar {
  # pragma mark - Bar
}
baz {
  # pragma mark - Baz
}

We'll first move foo under Outer, then start processing bar we notice that It comes after pragma Foo, and then also notice that pragma Foo is not contained in bar hence break. but all of foo,bar,baz should've been moved to be under Outer instead.

[dgoldman]

clang-tools-extra/clangd/FindSymbols.cpp

535

Implementing this now - there's one other edge case here, in that we don't want to treat #pragma mark Blah as a group. I guess I can maintain state similar to the first solution to solve that.

664

Yeah that's a good point, we'd have to do something like your suggested solution or maintain more state to consider the children that were moved.

[dgoldman]

clang-tools-extra/clangd/FindSymbols.cpp

535

Wait nevermind, I don't think that's a problem since the pragmas should never overlap, just have some other issue in my code I need to figure out

[dgoldman]

the third time is the charm

[dgoldman]

Okay I think this is what you had in mind. LMK, if it's good I'll go ahead and delete the other ones

[kadircet]

Thanks! I think it looks good, I've suggested some more simplifications to termination detection. If you can delete the rest I'd like to take a final look at the rest of the details.

clang-tools-extra/clangd/FindSymbols.cpp

680

nit: std::move

712

bool TerminatedByNextPragma = false;
for (auto &NextPragma : Pragmas) {
  // If we hit a pragma outside of Cur, the rest will be outside as well.
  if (!Cur->contains(NextPragma))
       break;

  // NextPragma cannot terminate P if it is nested inside a children, look for the next one.
  if (any_of(Cur->children, [](...) { return Child->contains(NextPragma); })
      continue;

  // Pragma owns all the children between P and NextPragma
  auto It = std::partition(....);
  P.children.assign(make_move_iterator(It), make_move_iterator(Cur->children.end()));
  Cur->children.erase(It, ...);
  TerminatedByNextPragma = true;
  break;
}
if(!TerminatedByNextPragma) {
  // P is terminated by the end of current symbol, hence it owns all the children after P.
  auto It = std::partition(....);
  P.children.assign(make_move_iterator(It), make_move_iterator(Cur->children.end()));
  Cur->children.erase(It, ...);  
}
// Update the range for P to cover children and append to Cur.

[dgoldman]

Simplify children moving

[dgoldman]

PTAL, also updated the test to no longer check the children's order

[kadircet]

thanks, mostly looks good couple of nits!

clang-tools-extra/clangd/CollectMacros.cpp

60

are we fine with these annotations spanning #pragma [[mark XX]] rather than the whole line or just XX ?

clang-tools-extra/clangd/FindSymbols.cpp

581

nit: s/std::partition(Cur->children.begin(), Cur->children.end()/llvm::partition(Cur->children/

707

nit: Pragmas.reserve

711

nit: 0,0 should suffice + makes sure the range is valid (in theory these are zero-based)

717

nit: llvm::makeArrayRef(Pragmas)

clang-tools-extra/clangd/FindTarget.cpp

655

this change does not look relevant, can you please revert?

clang-tools-extra/clangd/ParsedAST.cpp

441

We are not patching marks for stale preambles, which I believe is fine but worth a FIXME. If you are interested please take a look at https://github.com/llvm/llvm-project/blob/main/clang-tools-extra/clangd/Preamble.cpp#L427, it should be fairly easy to handle movements of #pragma marks in preamble section.

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

1055

can you add these cases as well to make sure details of the merge logic are working as expected?

[dgoldman]

Address nits

clang-tools-extra/clangd/CollectMacros.cpp

60

I think it's okay for now, I added a FIXME which I'll address in a follow up

clang-tools-extra/clangd/FindTarget.cpp

655

Reverted, will send out another change to fix the warning

clang-tools-extra/clangd/ParsedAST.cpp

441

Added a FIXME. Does something similar need to be done for MainFileMacros?

[kadircet]

thanks, lgtm!

clang-tools-extra/clangd/ParsedAST.cpp

441

we already handle macros today in https://github.com/llvm/llvm-project/blob/main/clang-tools-extra/clangd/Preamble.cpp#L208. we just need to handle pragma mark in the callbacks and generate the relevant patch.

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

1100

nit: drop AllOf

1102

nit: drop AllOf

[dgoldman]

Remove unnecessary AllOf

[dgoldman]

Remove more AllOfs

[dgoldman]

Rebase

[fmayer]

This broke the UBsan buildbot: https://lab.llvm.org/buildbot/#/builders/85/builds/6103/steps/10/logs/stdio

clang-tools-extra/clangd/CollectMacros.h

 private:
   void add(const Token &MacroNameTok, const MacroInfo *MI,
            bool IsDefinition = false);
   const SourceManager &SM;
   bool InMainFile = true;
   MainFileMacros &Out;
 };
 
+/// Represents a `#pragma mark` in the main file.
+///
+/// There can be at most one pragma mark per line.
+struct PragmaMark {
+  SourceLocation Loc;
+  std::string Trivia;
+};
+
+/// Collect all pragma marks from the main file.
+std::unique_ptr<PPCallbacks>
+collectPragmaMarksCallback(const SourceManager &, std::vector<PragmaMark> &Out);
+
 } // namespace clangd
 } // namespace clang
 
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_COLLECTEDMACROS_H

clang-tools-extra/clangd/CollectMacros.cpp

 //===--- CollectMacros.cpp ---------------------------------------*- C++-*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "CollectMacros.h"
 #include "clang/Basic/SourceLocation.h"
 #include "clang/Lex/Lexer.h"
 
+namespace {
+class CollectPragmaMarks : public clang::PPCallbacks {
+public:
+  explicit CollectPragmaMarks(const clang::SourceManager &SM,
+                              std::vector<clang::clangd::PragmaMark> &Out)
+      : SM(SM), Out(Out) {}
+  void PragmaMark(clang::SourceLocation Loc, clang::StringRef Trivia) override {
+    if (clang::clangd::isInsideMainFile(Loc, SM)) {
+      Out.emplace_back(clang::clangd::PragmaMark{Loc, Trivia.str()});
+    }
+  }
+
+private:
+  const clang::SourceManager &SM;
+  std::vector<clang::clangd::PragmaMark> &Out;
+};
+} // namespace
+
 namespace clang {
 namespace clangd {
 
 void CollectMainFileMacros::add(const Token &MacroNameTok, const MacroInfo *MI,
                                 bool IsDefinition) {
   if (!InMainFile)
     return;
   auto Loc = MacroNameTok.getLocation();
   if (Loc.isInvalid() || Loc.isMacroID())
     return;
 
   auto Name = MacroNameTok.getIdentifierInfo()->getName();
   Out.Names.insert(Name);
   auto Range = halfOpenToRange(
       SM, CharSourceRange::getCharRange(Loc, MacroNameTok.getEndLoc()));
   if (auto SID = getSymbolID(Name, MI, SM))
     Out.MacroRefs[SID].push_back({Range, IsDefinition});
   else
     Out.UnknownMacros.push_back({Range, IsDefinition});
 }
+
+std::unique_ptr<PPCallbacks>
+collectPragmaMarksCallback(const SourceManager &SM,
+                           std::vector<PragmaMark> &Out) {
+  return std::make_unique<CollectPragmaMarks>(SM, Out);
+}
+
 } // namespace clangd
 } // namespace clang

clang-tools-extra/clangd/FindSymbols.cpp

VisitKind shouldVisit(Decl *D) {
     }
     // For all other cases, visit both the children and the decl.
     return VisitKind::DeclAndChildren;
   }
 
   ParsedAST *
 };
 
+struct PragmaMarkSymbol {
+  DocumentSymbol DocSym;
+  bool IsGroup;
+};
+
+/// Merge in `PragmaMarkSymbols` into the given `DocumentSymbols`. All symbols
+/// should be sorted in ascending order by range.
+std::vector<DocumentSymbol> mergePragmas(std::vector<DocumentSymbol> &Syms,
+                                         ArrayRef<PragmaMarkSymbol> &Pragmas,
+                                         Range ParentRange) {
+  std::vector<DocumentSymbol> Res;
+  size_t MarkIndex = 0;
+  bool HaveOpenMarkGroup = false;
+  auto It = Syms.begin();
+
+  while (It != Syms.end() && !Pragmas.empty()) {
+    auto &Sym = *It;
+    const auto &Pragma = Pragmas.front();
+
+    // Pragma mark is contained in the current symbol, we need to recurse to
+    // nest it inside the symbol.
+    if (Sym.range.contains(Pragma.DocSym.range)) {
+      Sym.children = mergePragmas(Sym.children, Pragmas, Sym.range);
+      continue;
+    }
+    // Pragma mark is after the current symbol.
+    if (Sym.range < Pragma.DocSym.range) {
+      if (HaveOpenMarkGroup) { // Sym belongs to the previous TextMark group.
+        unionRanges(Res[MarkIndex].range, Sym.range);
+        Res[MarkIndex].children.push_back(std::move(Sym));
+      } else { // Sym doesn't belong to a group.
+        Res.push_back(std::move(Sym));
+      }
+      It++;
+      continue;
+    }
+    // Pragma mark is before the current symbol, add in a node for the mark.
+    assert(Pragma.DocSym.range < Sym.range && "Mark should be before Sym");
+    if (Pragma.IsGroup) {
+      MarkIndex = Res.size();
+      HaveOpenMarkGroup = true;
+    } else { // New mark ends the previous group if one existed.
+      HaveOpenMarkGroup = false;
+    }
+    Res.push_back(std::move(Pragma.DocSym));
+    Pragmas = Pragmas.drop_front();
+  }
+
+  // If we ran out of Symbols, we add any leftover marks as long as they are
+  // contained in our parent. Otherwise, we can't add them, since they belong
+  // to a different ancestor besides our parent.
+  while (!Pragmas.empty()) {
+    const auto &Pragma = Pragmas.back();
+    if (!ParentRange.contains(Pragma.DocSym.range))
+      break;
+    Res.push_back(std::move(Pragma.DocSym));
+    Pragmas = Pragmas.drop_front();
+  }
+
+  // If we ran out of marks, but still have symbols left, add them. If we have
+  // a group open, leftover symbols belong to that group.
+  for (; It != Syms.end(); It++) {
+    auto &Sym = *It;
+    if (HaveOpenMarkGroup) {
+      unionRanges(Res[MarkIndex].range, Sym.range);
+      Res[MarkIndex].children.push_back(std::move(Sym));
+    } else {
+      Res.push_back(std::move(Sym));
+    }
+  }
+  return Res;
+}
+
+/// Merge in `PragmaMarkSymbols` into the given `DocumentSymbols`. All symbols
+/// should be sorted in ascending order by range.
+std::vector<DocumentSymbol> mergePragmas2(std::vector<DocumentSymbol> &Syms,
+                                          ArrayRef<PragmaMarkSymbol> &Pragmas,
+                                          Range ParentRange) {
+  std::vector<DocumentSymbol> Res;
+  auto It = Syms.begin();
+
+  while (!Pragmas.empty()) {
+    const auto &Pragma = Pragmas.front();
+    // If the Pragma isn't contained in our parent, we're done, it must belong
+    // to a different ancestor.
+    if (!ParentRange.contains(Pragma.DocSym.range))
+      break;
+
+    // No more symbols left, just add the pragma.
+    if (It == Syms.end()) {
+      Res.push_back(std::move(Pragma.DocSym));
+      Pragmas = Pragmas.drop_front();
+      continue;
+    }
+    auto &Sym = *It;
+
+    // Pragma mark is contained in the current symbol, we need to recurse to
+    // nest it inside the symbol.
+    if (Sym.range.contains(Pragma.DocSym.range)) {
+      Sym.children = mergePragmas2(Sym.children, Pragmas, Sym.range);
+      continue;
+    }
+    // Pragma mark is after the child node, so we can process the child, it
+    // doesn't belong to a group.
+    if (Sym.range < Pragma.DocSym.range) {
+      Res.push_back(std::move(Sym));
+      It++;
+      continue;
+    }
+    // Pragma mark is before the current symbol, add in a node for the mark, and
+    // any Syms who should belong to the group, if it is one.
+    assert(Pragma.DocSym.range < Sym.range && "Mark should be before Sym");
+    if (!Pragma.IsGroup) {
+      Res.push_back(std::move(Pragma.DocSym));
+      Pragmas = Pragmas.drop_front();
+      continue;
+    }
+    DocumentSymbol PragmaSym = Pragma.DocSym;
+    Pragmas = Pragmas.drop_front();
+    // We've got a pragma which is a group. We add all Syms we encounter to our
+    // group until it ends; our group will end if there's a pragma after us
+    // which implicitly ends our group.
+    while (It != Syms.end() && PragmaSym.range < It->range) {
+      auto &Sym = *It;
+      if (Pragmas.empty() ||
+          It->range < Pragmas.front().DocSym.range) { // Sym is ours.
+        unionRanges(PragmaSym.range, Sym.range);
+        PragmaSym.children.push_back(std::move(Sym));
+        ++It;
+        continue;
+      }
+      const auto &NextPragma = Pragmas.front();
+      // Next pragma is contained in the Sym, it belongs there and doesn't
+      // affect us at all.
+      if (Sym.range.contains(NextPragma.DocSym.range)) {
+        Sym.children = mergePragmas2(Sym.children, Pragmas, Sym.range);
+        continue;
+      }
+      // NextPragma is after us but before the next symbol. Our reign is over.
+      break;
+    }
+    Res.push_back(PragmaSym);
+  }
+  // If we ran out of marks, but still have symbols left, add them.
+  for (; It != Syms.end(); It++) {
+    Res.push_back(std::move(*It));
+  }
+  return Res;
+}
+
+PragmaMarkSymbol markToSymbol(const PragmaMark &P, const SourceManager &SM) {
+  StringRef Name = StringRef(P.Trivia).trim();
+  bool IsGroup = false;
+  // "-\s+<group name>" or "<name>" after an initial trim. The former is
+  // considered a group, the latter just a mark. We need to include a name
+  // here since editors won't properly render the symbol otherwise.
+  StringRef MaybeGroupName = Name;
+  if (MaybeGroupName.consume_front("-") &&
+      (MaybeGroupName.ltrim() != MaybeGroupName || MaybeGroupName.empty())) {
+    Name = MaybeGroupName.empty() ? "(unnamed group)" : MaybeGroupName.ltrim();
+    IsGroup = true;
+  } else if (Name.empty()) {
+    Name = "(unnamed mark)";
+  }
+  DocumentSymbol Sym;
+  Sym.name = Name.str();
+  Sym.kind = SymbolKind::File;
+  Position Start = sourceLocToPosition(SM, P.Loc);
+  Position End = {Start.line + 1, 0};
+  Sym.range = Range{Start, End};
+  Sym.selectionRange = Range{Start, End};
+  return {Sym, IsGroup};
+}
+
 std::vector<DocumentSymbol> collectDocSymbols(ParsedAST &AST) {
-  return DocumentOutline(AST).build();
+  std::vector<DocumentSymbol> Syms = DocumentOutline(AST).build();
+
+  const auto &PragmaMarks = AST.getMarks();
+  if (PragmaMarks.empty())
+    return Syms;
+
+  const auto &SM = AST.getSourceManager();
+  std::vector<PragmaMarkSymbol> Pragmas;
+  for (const auto &P : PragmaMarks)
+    Pragmas.push_back(markToSymbol(P, SM));
+  Range EntireFile = {
+      {-1, -1},
+      {std::numeric_limits<int>::max(), std::numeric_limits<int>::max()}};
+  ArrayRef<PragmaMarkSymbol> PragmasRef(Pragmas);
+  return mergePragmas2(Syms, PragmasRef, EntireFile);
 }
+
 } // namespace
 
 llvm::Expected<std::vector<DocumentSymbol>> getDocumentSymbols(ParsedAST &AST) {
   return collectDocSymbols(AST);
 }
 
 } // namespace clangd
 } // namespace clang

clang-tools-extra/clangd/FindTarget.cpp

void VisitObjCMethodDecl(const ObjCMethodDecl *OMD) {
                                   OMD->getSelectorStartLoc(),
                                   /*IsDecl=*/true,
                                   {OMD}});
     }
 
     void visitProtocolList(
         llvm::iterator_range<ObjCProtocolList::iterator> Protocols,
         llvm::iterator_range<const SourceLocation *> Locations) {
-      for (const auto &P : llvm::zip(Protocols, Locations)) {
+      for (auto P : llvm::zip(Protocols, Locations)) {
         Refs.push_back(ReferenceLoc{NestedNameSpecifierLoc(),
                                     std::get<1>(P),
                                     /*IsDecl=*/false,
                                     {std::get<0>(P)}});
       }
     }
 
     void VisitObjCInterfaceDecl(const ObjCInterfaceDecl *OID) {

clang-tools-extra/clangd/ParsedAST.h

public:
   /// bytes. Does not include the size of the preamble.
   std::size_t getUsedBytes() const;
   const IncludeStructure &getIncludeStructure() const;
   const CanonicalIncludes &getCanonicalIncludes() const;
 
   /// Gets all macro references (definition, expansions) present in the main
   /// file, including those in the preamble region.
   const MainFileMacros &getMacros() const;
+  /// Gets all pragma marks in the main file.
+  const std::vector<PragmaMark> &getMarks() const;
   /// Tokens recorded while parsing the main file.
   /// (!) does not have tokens from the preamble.
   const syntax::TokenBuffer &getTokens() const { return Tokens; }
 
   /// Returns the version of the ParseInputs this AST was built from.
   llvm::StringRef version() const { return Version; }
 
   /// Returns the version of the ParseInputs used to build Preamble part of this
   /// AST. Might be None if no Preamble is used.
   llvm::Optional<llvm::StringRef> preambleVersion() const;
 
   const HeuristicResolver *getHeuristicResolver() const {
     return Resolver.get();
   }
 
 private:
   ParsedAST(llvm::StringRef Version,
             std::shared_ptr<const PreambleData> Preamble,
             std::unique_ptr<CompilerInstance> Clang,
             std::unique_ptr<FrontendAction> Action, syntax::TokenBuffer Tokens,
-            MainFileMacros Macros, std::vector<Decl *> LocalTopLevelDecls,
+            MainFileMacros Macros, std::vector<PragmaMark> Marks,
+            std::vector<Decl *> LocalTopLevelDecls,
             llvm::Optional<std::vector<Diag>> Diags, IncludeStructure Includes,
             CanonicalIncludes CanonIncludes);
 
   std::string Version;
   // In-memory preambles must outlive the AST, it is important that this member
   // goes before Clang and Action.
   std::shared_ptr<const PreambleData> Preamble;
   // We store an "incomplete" FrontendAction (i.e. no EndSourceFile was called
   // on it) and CompilerInstance used to run it. That way we don't have to do
   // complex memory management of all Clang structures on our own. (They are
   // stored in CompilerInstance and cleaned up by
   // FrontendAction.EndSourceFile).
   std::unique_ptr<CompilerInstance> Clang;
   std::unique_ptr<FrontendAction> Action;
   /// Tokens recorded after the preamble finished.
   ///   - Includes all spelled tokens for the main file.
   ///   - Includes expanded tokens produced **after** preamble.
   ///   - Does not have spelled or expanded tokens for files from preamble.
   syntax::TokenBuffer Tokens;
 
   /// All macro definitions and expansions in the main file.
   MainFileMacros Macros;
+  // Pragma marks in the main file.
+  std::vector<PragmaMark> Marks;
   // Data, stored after parsing. None if AST was built with a stale preamble.
   llvm::Optional<std::vector<Diag>> Diags;
   // Top-level decls inside the current file. Not that this does not include
   // top-level decls from the preamble.
   std::vector<Decl *> LocalTopLevelDecls;
   IncludeStructure Includes;
   CanonicalIncludes CanonIncludes;
   std::unique_ptr<HeuristicResolver> Resolver;
 };
 
 } // namespace clangd
 } // namespace clang
 
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_PARSEDAST_H

clang-tools-extra/clangd/ParsedAST.cpp

if (Preamble) {
     ReplayPreamble::attach(Patch->preambleIncludes(), *Clang,
                            Patch->modifiedBounds());
   }
   // Important: collectIncludeStructure is registered *after* ReplayPreamble!
   // Otherwise we would collect the replayed includes again...
   // (We can't *just* use the replayed includes, they don't have Resolved path).
   Clang->getPreprocessor().addPPCallbacks(
       collectIncludeStructureCallback(Clang->getSourceManager(), &Includes));
   // Copy over the macros in the preamble region of the main file, and combine
   // with non-preamble macros below.
   MainFileMacros Macros;
   if (Preamble)
     Macros = Preamble->Macros;
   Clang->getPreprocessor().addPPCallbacks(
       std::make_unique<CollectMainFileMacros>(Clang->getSourceManager(),
                                               Macros));
 
+  std::vector<PragmaMark> Marks;
+  if (Preamble)
+    Marks = Preamble->Marks;
+  Clang->getPreprocessor().addPPCallbacks(
+      collectPragmaMarksCallback(Clang->getSourceManager(), Marks));
+
   // Copy over the includes from the preamble, then combine with the
   // non-preamble includes below.
   CanonicalIncludes CanonIncludes;
   if (Preamble)
     CanonIncludes = Preamble->CanonIncludes;
   else
     CanonIncludes.addSystemHeadersMapping(Clang->getLangOpts());
   std::unique_ptr<CommentHandler> IWYUHandler =
if (PreserveDiags) {
     // Finally, add diagnostics coming from the AST.
     {
       std::vector<Diag> D = ASTDiags.take(CTContext.getPointer());
       Diags->insert(Diags->end(), D.begin(), D.end());
     }
   }
   return ParsedAST(Inputs.Version, std::move(Preamble), std::move(Clang),
                    std::move(Action), std::move(Tokens), std::move(Macros),
-                   std::move(ParsedDecls), std::move(Diags),
+                   std::move(Marks), std::move(ParsedDecls), std::move(Diags),
                    std::move(Includes), std::move(CanonIncludes));
 }
 
 ParsedAST::ParsedAST(ParsedAST &&Other) = default;
 
 ParsedAST &ParsedAST::operator=(ParsedAST &&Other) = default;
 
 ParsedAST::~ParsedAST() {
const Preprocessor &ParsedAST::getPreprocessor() const {
   return Clang->getPreprocessor();
 }
 
 llvm::ArrayRef<Decl *> ParsedAST::getLocalTopLevelDecls() {
   return LocalTopLevelDecls;
 }
 
 const MainFileMacros &ParsedAST::getMacros() const { return Macros; }
+const std::vector<PragmaMark> &ParsedAST::getMarks() const { return Marks; }
 
 std::size_t ParsedAST::getUsedBytes() const {
   auto &AST = getASTContext();
   // FIXME(ibiryukov): we do not account for the dynamically allocated part of
   // Message and Fixes inside each diagnostic.
   std::size_t Total = clangd::getUsedBytes(LocalTopLevelDecls) +
                       (Diags ? clangd::getUsedBytes(*Diags) : 0);
 
const CanonicalIncludes &ParsedAST::getCanonicalIncludes() const {
   return CanonIncludes;
 }
 
 ParsedAST::ParsedAST(llvm::StringRef Version,
                      std::shared_ptr<const PreambleData> Preamble,
                      std::unique_ptr<CompilerInstance> Clang,
                      std::unique_ptr<FrontendAction> Action,
                      syntax::TokenBuffer Tokens, MainFileMacros Macros,
+                     std::vector<PragmaMark> Marks,
                      std::vector<Decl *> LocalTopLevelDecls,
                      llvm::Optional<std::vector<Diag>> Diags,
                      IncludeStructure Includes, CanonicalIncludes CanonIncludes)
     : Version(Version), Preamble(std::move(Preamble)), Clang(std::move(Clang)),
       Action(std::move(Action)), Tokens(std::move(Tokens)),
-      Macros(std::move(Macros)), Diags(std::move(Diags)),
+      Macros(std::move(Macros)), Marks(std::move(Marks)),
+      Diags(std::move(Diags)),
       LocalTopLevelDecls(std::move(LocalTopLevelDecls)),
       Includes(std::move(Includes)), CanonIncludes(std::move(CanonIncludes)) {
   Resolver = std::make_unique<HeuristicResolver>(getASTContext());
   assert(this->Clang);
   assert(this->Action);
 }
 
 llvm::Optional<llvm::StringRef> ParsedAST::preambleVersion() const {
   if (!Preamble)
     return llvm::None;
   return llvm::StringRef(Preamble->Version);
 }
 } // namespace clangd
 } // namespace clang

clang-tools-extra/clangd/Preamble.h

struct PreambleData {
   std::vector<Diag> Diags;
   // Processes like code completions and go-to-definitions will need #include
   // information, and their compile action skips preamble range.
   IncludeStructure Includes;
   // Macros defined in the preamble section of the main file.
   // Users care about headers vs main-file, not preamble vs non-preamble.
   // These should be treated as main-file entities e.g. for code completion.
   MainFileMacros Macros;
+  // Pragma marks defined in the preamble section of the main file.
+  std::vector<PragmaMark> Marks;
   // Cache of FS operations performed when building the preamble.
   // When reusing a preamble, this cache can be consumed to save IO.
   std::unique_ptr<PreambleFileStatusCache> StatCache;
   CanonicalIncludes CanonIncludes;
   // Whether there was a (possibly-incomplete) include-guard on the main file.
   // We need to propagate this information "by hand" to subsequent parses.
   bool MainIsIncludeGuarded = false;
 };

clang-tools-extra/clangd/Preamble.cpp

 public:
   CppFilePreambleCallbacks(PathRef File, PreambleParsedCallback ParsedCallback)
       : File(File), ParsedCallback(ParsedCallback) {}
 
   IncludeStructure takeIncludes() { return std::move(Includes); }
 
   MainFileMacros takeMacros() { return std::move(Macros); }
 
+  std::vector<PragmaMark> takeMarks() { return std::move(Marks); }
+
   CanonicalIncludes takeCanonicalIncludes() { return std::move(CanonIncludes); }
 
   bool isMainFileIncludeGuarded() const { return IsMainFileIncludeGuarded; }
 
   void AfterExecute(CompilerInstance &CI) override {
     if (ParsedCallback) {
       trace::Span Tracer("Running PreambleCallback");
       ParsedCallback(CI.getASTContext(), CI.getPreprocessorPtr(),
public:
   }
 
   std::unique_ptr<PPCallbacks> createPPCallbacks() override {
     assert(SourceMgr && LangOpts &&
            "SourceMgr and LangOpts must be set at this point");
 
     return std::make_unique<PPChainedCallbacks>(
         collectIncludeStructureCallback(*SourceMgr, &Includes),
-        std::make_unique<CollectMainFileMacros>(*SourceMgr, Macros));
+        std::make_unique<PPChainedCallbacks>(
+            std::make_unique<CollectMainFileMacros>(*SourceMgr, Macros),
+            collectPragmaMarksCallback(*SourceMgr, Marks)));
   }
 
   CommentHandler *getCommentHandler() override {
     IWYUHandler = collectIWYUHeaderMaps(&CanonIncludes);
     return IWYUHandler.get();
   }
 
   bool shouldSkipFunctionBody(Decl *D) override {
public:
   }
 
 private:
   PathRef File;
   PreambleParsedCallback ParsedCallback;
   IncludeStructure Includes;
   CanonicalIncludes CanonIncludes;
   MainFileMacros Macros;
+  std::vector<PragmaMark> Marks;
   bool IsMainFileIncludeGuarded = false;
   std::unique_ptr<CommentHandler> IWYUHandler = nullptr;
   const clang::LangOptions *LangOpts = nullptr;
   const SourceManager *SourceMgr = nullptr;
 };
 
 // Represents directives other than includes, where basic textual information is
 // enough.
vlog("Built preamble of size {0} for file {1} version {2}",
          BuiltPreamble->getSize(), FileName, Inputs.Version);
     std::vector<Diag> Diags = PreambleDiagnostics.take();
     auto Result = std::make_shared<PreambleData>(std::move(*BuiltPreamble));
     Result->Version = Inputs.Version;
     Result->CompileCommand = Inputs.CompileCommand;
     Result->Diags = std::move(Diags);
     Result->Includes = CapturedInfo.takeIncludes();
     Result->Macros = CapturedInfo.takeMacros();
+    Result->Marks = CapturedInfo.takeMarks();
     Result->CanonIncludes = CapturedInfo.takeCanonicalIncludes();
     Result->StatCache = std::move(StatCache);
     Result->MainIsIncludeGuarded = CapturedInfo.isMainFileIncludeGuarded();
     return Result;
   }
 
   elog("Could not build a preamble for file {0} version {1}: {2}", FileName,
        Inputs.Version, BuiltPreamble.getError().message());

clang-tools-extra/clangd/SourceCode.h

 /// Returns the source code covered by the source range.
 /// EXPECTS: isValidFileRange(R) == true.
 llvm::StringRef toSourceCode(const SourceManager &SM, SourceRange R);
 
 // Converts a half-open clang source range to an LSP range.
 // Note that clang also uses closed source ranges, which this can't handle!
 Range halfOpenToRange(const SourceManager &SM, CharSourceRange R);
 
+// Expand range `A` to also contain `B`.
+void unionRanges(Range &A, Range B);
+
 // Converts an offset to a clang line/column (1-based, columns are bytes).
 // The offset must be in range [0, Code.size()].
 // Prefer to use SourceManager if one is available.
 std::pair<size_t, size_t> offsetToClangLineColumn(llvm::StringRef Code,
                                                   size_t Offset);
 
 /// From "a::b::c", return {"a::b::", "c"}. Scope is empty if there's no
 /// qualifier.

clang-tools-extra/clangd/SourceCode.cpp

 Range halfOpenToRange(const SourceManager &SM, CharSourceRange R) {
   // Clang is 1-based, LSP uses 0-based indexes.
   Position Begin = sourceLocToPosition(SM, R.getBegin());
   Position End = sourceLocToPosition(SM, R.getEnd());
 
   return {Begin, End};
 }
 
+void unionRanges(Range &A, Range B) {
+  if (B.start < A.start)
+    A.start = B.start;
+  if (A.end < B.end)
+    A.end = B.end;
+}
+
 std::pair<size_t, size_t> offsetToClangLineColumn(llvm::StringRef Code,
                                                   size_t Offset) {
   Offset = std::min(Code.size(), Offset);
   llvm::StringRef Before = Code.substr(0, Offset);
   int Lines = Before.count('\n');
   size_t PrevNL = Before.rfind('\n');
   size_t StartOfLine = (PrevNL == llvm::StringRef::npos) ? 0 : (PrevNL + 1);
   return {Lines + 1, Offset - StartOfLine + 1};

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

EXPECT_THAT(
           AllOf(
               WithName("Cat()"), SymRange(Main.range("MeowCat")),
               Children(AllOf(WithName("-meow"), WithKind(SymbolKind::Method)))),
           AllOf(WithName("Cat()"), SymRange(Main.range("PurCat")),
                 Children(
                     AllOf(WithName("-pur"), WithKind(SymbolKind::Method))))));
 }
 
+TEST(DocumentSymbolsTest, PragmaMarkGroups) {
+  TestTU TU;
+  TU.ExtraArgs = {"-xobjective-c++", "-Wno-objc-root-class"};
+  Annotations Main(R"cpp(
+      $DogDef[[@interface Dog
+      @end]]
+
+      $DogImpl[[@implementation Dog
+
+      + (id)sharedDoggo { return 0; }
+
+      #pragma $Overrides[[mark - Overrides
+
+      - (id)init {
+        return self;
+      }
+      - (void)bark {}]]
+
+      #pragma $Specifics[[mark - Dog Specifics
+
+      - (int)isAGoodBoy {
+        return 1;
+      }]]
+      @]]end  // FIXME: Why doesn't this include the 'end'?
+
+      #pragma $End[[mark - End
+]]
+    )cpp");
+  TU.Code = Main.code().str();
+  EXPECT_THAT(
+      getSymbols(TU.build()),
+      ElementsAre(
+          AllOf(WithName("Dog"), SymRange(Main.range("DogDef"))),
+          AllOf(WithName("Dog"), SymRange(Main.range("DogImpl")),
+                Children(AllOf(WithName("+sharedDoggo"),
+                               WithKind(SymbolKind::Method)),
+                         AllOf(WithName("Overrides"),
+                               SymRange(Main.range("Overrides")),
+                               Children(AllOf(WithName("-init"),
+                                              WithKind(SymbolKind::Method)),
+                                        AllOf(WithName("-bark"),
+                                              WithKind(SymbolKind::Method)))),
+                         AllOf(WithName("Dog Specifics"),
+                               SymRange(Main.range("Specifics")),
+                               Children(AllOf(WithName("-isAGoodBoy"),
+                                              WithKind(SymbolKind::Method)))))),
+          AllOf(WithName("End"), SymRange(Main.range("End")))));
+}
+
+TEST(DocumentSymbolsTest, PragmaMarkGroupsNoNesting) {
+  TestTU TU;
+  TU.ExtraArgs = {"-xobjective-c++", "-Wno-objc-root-class"};
+  Annotations Main(R"cpp(
+      #pragma mark Helpers
+      void helpA(id obj) {}
+
+      #pragma mark -
+      #pragma mark Core
+
+      void coreMethod() {}
+    )cpp");
+  TU.Code = Main.code().str();
+  EXPECT_THAT(getSymbols(TU.build()),
+              ElementsAre(AllOf(WithName("Helpers")), AllOf(WithName("helpA")),
+                          AllOf(WithName("(unnamed group)")),
+                          AllOf(WithName("Core")),
+                          AllOf(WithName("coreMethod"))));
+}
+
+TEST(DocumentSymbolsTest, SymbolsAreSorted) {
+  TestTU TU;
+  TU.ExtraArgs = {"-xobjective-c++", "-Wno-objc-root-class"};
+  Annotations Main(R"cpp(
+      @interface MYObject
+      @end
+
+      void someFunctionAbove() {}
+
+      @implementation MYObject
+      - (id)init { return self; }
+
+      void someHelperFunction() {}
+
+      - (void)retain {}
+      - (void)release {}
+      @end
+    )cpp");
+  TU.Code = Main.code().str();
+  EXPECT_THAT(getSymbols(TU.build()),
+              ElementsAre(AllOf(WithName("MYObject")),
+                          AllOf(WithName("someFunctionAbove")),
+                          // FIXME: This should be nested under MYObject below.
+                          AllOf(WithName("someHelperFunction")),
+                          AllOf(WithName("MYObject"),
+                                Children(AllOf(WithName("-init")),
+                                         AllOf(WithName("-retain")),
+                                         AllOf(WithName("-release"))))));
+}
+
 } // namespace
 } // namespace clangd
 } // namespace clang

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

if (const NamedDecl *ND = dyn_cast<NamedDecl>(arg))
     return printTemplateSpecializationArgs(*ND) == ArgName;
   return false;
 }
 
 MATCHER_P(RangeIs, R, "") {
   return arg.beginOffset() == R.Begin && arg.endOffset() == R.End;
 }
 
+MATCHER_P(PragmaTrivia, P, "") { return arg.Trivia == P; }
+
 MATCHER(EqInc, "") {
   Inclusion Actual = testing::get<0>(arg);
   Inclusion Expected = testing::get<1>(arg);
   return std::tie(Actual.HashLine, Actual.Written) ==
          std::tie(Expected.HashLine, Expected.Written);
 }
 
 TEST(ParsedASTTest, TopLevelDecls) {
TEST(ParsedASTTest, HeaderGuardsImplIface) {
   TU.AdditionalFiles = {{"iface.h", once(Interface)}};
   AST = TU.build();
   EXPECT_THAT(*AST.getDiagnostics(),
               ElementsAre(Diag("in included file: main file cannot be included "
                                "recursively when building a preamble")));
   EXPECT_FALSE(mainIsGuarded(AST));
 }
 
+TEST(ParsedASTTest, DiscoversPragmaMarks) {
+  TestTU TU;
+  TU.AdditionalFiles["Header.h"] = R"(
+    #pragma mark - Something API
+    int something();
+    #pragma mark Something else
+  )";
+  TU.Code = R"cpp(
+    #include "Header.h"
+    #pragma mark In Preamble
+    #pragma mark - Something Impl
+    int something() { return 1; }
+    #pragma mark End
+  )cpp";
+  auto AST = TU.build();
+
+  EXPECT_THAT(AST.getMarks(), ElementsAre(PragmaTrivia(" In Preamble"),
+                                          PragmaTrivia(" - Something Impl"),
+                                          PragmaTrivia(" End")));
+}
+
 } // namespace
 } // namespace clangd
 } // namespace clang

clang/include/clang/Lex/PPCallbacks.h

public:
   }
 
   void PragmaComment(SourceLocation Loc, const IdentifierInfo *Kind,
                      StringRef Str) override {
     First->PragmaComment(Loc, Kind, Str);
     Second->PragmaComment(Loc, Kind, Str);
   }
 
+  void PragmaMark(SourceLocation Loc, StringRef Trivia) override {
+    First->PragmaMark(Loc, Trivia);
+    Second->PragmaMark(Loc, Trivia);
+  }
+
   void PragmaDetectMismatch(SourceLocation Loc, StringRef Name,
                             StringRef Value) override {
     First->PragmaDetectMismatch(Loc, Name, Value);
     Second->PragmaDetectMismatch(Loc, Name, Value);
   }
 
   void PragmaDebug(SourceLocation Loc, StringRef DebugType) override {
     First->PragmaDebug(Loc, DebugType);