[RFC] A C++ pseudo parser for tooling

[Xazax-hun]

I support this effort and would love to see fuzzy parser experiments upstream. The main reason is that Clang already provides some IDE functionality (e.g. clangd, but even before that). And some (most?) proprietary IDEs have tiered parsers. I.e., they start with something primitive but fast so go to definition and some other features can work within milliseconds after opening a new file (at least for the most common scenarios) and they start a full-fledged more precise parser in the background and fall back to the results from that parser after it is done.

If Clang wants to provide all the language related facilities for IDEs, I think a fuzzy parser would fit this use case pretty well and it has the potential of significantly improving the user experience when working on big projects.

[sam-mccall]

@davrec

I support your effort given the first point but have to disagree strongly on this point. Clang represents almost all syntax in the AST, so much so that the few frustrating exceptions should probably be considered bugs.

Among these is as you mention int a, b; being represented as two separate decls; also if I recall some attributes are moved around silently during parsing, and of course macros aren’t represented. (Any others? Can’t be more than a handful.)

Sure there can I agree we should try to reduce the gaps, but I don’t think the clang AST’s ad-hoc space-saving design is really compatible with getting to 100% and staying there.

Some completely missing:

• no distinction between foo() the expression and foo(); the statement, so semicolons are not tracked. (This ties to Expr being a subclass of Stmt). (Deliberate, presumably to save memory)
• QualifiedTypeLoc does not retain the location of const. (Deliberate, presumably to save memory).
• Many nodes are missing “less-critical” punctuation or other tokens, such as commas in FunctionTypeLoc, the lparen in decltype(auto), public in class T : virtual public S {}…
• explicit function/variable template instantiations: there’s no node that carries the locations of the explicit instantiation at all. (bug? class templates are OK IIRC)
• Representation of broken code is lossy due to lack of redundancy. e.g. node bounds are calculated from token locations, so a missing ) means RParenLoc is null and we don’t know where node ends. (Tradeoff of the design)
• Representation of broken code is missing due to forcing invariants. e.g. vector<invalid, 2> is represented as BuiltinType: int. (Consequence of AST being semantics-first)

Some where important abstractions like “range” break down, leaving you to crawl the whole AST:

• declarators and decl-specifier-sequences are not represented directly in the AST. Technically the information is present in the typelocs but to analyze the syntax you need to reconstruct these syntactic parts, it’s extremely fiddly.
• AttributedTypeLoc’s range is often attribute’s range (excluding the attributed type)
• the range of Decls with attributes often excludes the attribute

Clang represents almost all syntax in the AST

Clang has pointers from semantics → tokens that cover most tokens (I think <90%), and this is valuable.

However there’s more to representing the syntax than this. One useful test is whether you can implement a tree walk over (range, interpretation) pairs such that ranges nest properly. This is effectively impossible with clang’s AST (It’s highly desirable and obvious, and AFAIK nobody’s managed to do it. I’d love to be proven wrong!)

You could construct a syntactic model (clang::syntax::Tree) from a clang AST, and this was the first thing we tried. (buildSyntaxTree). This made a nice demo but we couldn’t make it robust without building most of a parser and using the AST as a guide, at which point why make the AST mandatory?

[davrec]

Thanks for this perspective, I had not considered the need for fine-grained syntax details (distinguishing char const from const char etc), and was simply not aware of some of the others you mention. While each of these is solvable, the larger point – that it is not necessarily a virtue to cram more and more details into the AST which are not needed by the ordinary compilations for which the AST must be optimized – is well taken.

Btw @LegalizeAdulthood, check out https://github.com/llvm/llvm-project/commit/7c1ee5e95f3159e13edef644db0509a7d49921c3#diff-e00e863c6535c300cda470a712e903b1bb064f07127558d1c087600ddacb9aebR59 recently introduced by @sam-mccall for this new parser, that might be what you were describing in the other thread.

[AaronBallman]

FWIW, I’m also concerned about adding an additional parser. The goal of being to parse partial or broken code is one we’ve wanted to support before (like in clang-format), but is really difficult when you consider just how many C and C++ extensions exist in the wild. Both C and C++ are being continually updated, so this secondary parser is likely to be a pretty significant maintenance burden.

This is a fair point. We expect that adding new features in the pseudo parser is relatively cheap by modifying the grammar (which is already provided by the standard C++).

Yes, but the point is, it’s not clear that the community should pay that burden. As a concrete example, when we added the _ExtInt datatype to Clang, would a reviewer have been correct to suggest “you also need to update the pseudo parser”? If so, when we renamed _ExtInt to _BitInt, would we have to do it in both places as well? If the answer to both of these is “no”, then what’s to prevent this parser from falling so far out of line with the rest of the compiler that we then need to consider ripping it out (which is the point I’m at with the -ast-print option that’s only updated on a best-faith effort, as an example).

No, we don’t intend to reimplement a real preprocessor.

That’s good to hear!

These are not in our scope of the pseudo parser.

So this new parser won’t support templates or concepts? That seems like a surprise for a C++ pseudo parsing tool.

Based on our previous work of RecoveryAST, scaling the whole clang AST for erroneous constructs is not feasible.

Okay, that’s certainly good feedback. I remember some of the issues that RecoveryExpr have caused, and I can imagine it’d be hard to shoe-horn your needs on top of what Clang’s AST needs are without some really hard tension between the scenarios.

I’m still concerned about the amount of burden having two C++ parsers in the project puts on the community as a whole. Given that Clang and LLVM are designed to be consumed as a library, have you considered making this a separate tool in clang-tools-extra? (I’m presuming that you don’t expect the community to update the pseudo parser every time we add a new extension or implement a new standard feature, and having the project in clang-tools-extra makes it more clear that Clang doesn’t maintain the other parser.) Or a downstream project rather than an upstream one?

[sam-mccall]

@AaronBallman

Yes, but the point is, it’s not clear that the community should pay that burden. As a concrete example, when we added the _ExtInt datatype to Clang, would a reviewer have been correct to suggest “you also need to update the pseudo parser”?

I don’t think so, no. My expectation is the basic guarantee “don’t break the build or the tests” applies. So to rename a clang::tok::Kind that was already used in the grammar, you’d have you do something. Feature-wise, the pseudoparser may lag (or lead!) clang.

This seems comparable to when people modifying AST must/must not update clang-tidy, clangd etc. It’s definitely not zero!

@AaronBallman

If the answer to both of these is “no”, then what’s to prevent this parser from falling so far out of line with the rest of the compiler that we then need to consider ripping it out

Only that there’s no hard requirement they match.

• In particular, no plans to depend on this from clang, and I’d consider that a large shift that would need its own RFC to consider this question
• it’s hard to have such a requirement because a heuristic parser is always going to misparse some code and so diverge from clang anyway

Being unreliable enough that it gets removed from the tree would constitute failure. We should be careful that such a failure doesn’t damage clang, but we needn’t avoid any project that might fail.

@AaronBallman

So this new parser won’t support templates or concepts? That seems like a surprise for a C++ pseudo parsing tool.

Parsing templates and concepts (and their usages) is certainly in scope. You originally asked about template instantiation and concept satisfaction, which are semantic questions, right?

(Of course, parsing depends on template instantiation, but not for a parser that’s willing to guess and be wrong sometimes…)

@AaronBallman

Given that Clang and LLVM are designed to be consumed as a library, have you considered making this a separate tool in clang-tools-extra?

Yes, and we’re open to moving it. I agree it’d send a useful signal. The reasons we put it under lib/Tooling/ instead:

• precedent that clang-tools-extra standalone tools and clang/lib/ contains libraries. (Accidental?)
• relatedness to existing libraries under lib/Tooling, particularly lib/Tooling/Syntax
• nobody mentioned this until after code started landing

@alexr wasn’t convinced upthread that placing it under clang-tools-extra would improve the maintenance burden, maybe we should couple it with an explicit doc laying out expectations?

@AaronBallman

Or a downstream project rather than an upstream one?

We’d have to take clangd out of tree to depend on it. clangd benefits a lot from being in-tree, and I think clang benefits too (it encourages us to fix things in clang rather than work around them).

[AaronBallman]

I don’t think so, no. My expectation is the basic guarantee “don’t break the build or the tests” applies. So to rename a clang::tok::Kind that was already used in the grammar, you’d have you do something. Feature-wise, the pseudoparser may lag (or lead!) clang.
This seems comparable to when people modifying AST must/must not update clang-tidy, clangd etc. It’s definitely not zero!

I read this as more of a yes than a no, at least based on the practices in Clang of having a switch statement with an llvm_unreachable() at the bottom of it for a fair amount of parsing work. When a new token kind is added, we’ll have to update both parsers because of “don’t break the build or the tests”. Even without reaching an unreachable, there will be additional warnings about no longer having a fully covered switch (in -Werror configurations), etc. So in practice, it seems likely that changes to Clang’s parser will require code reviewers and authors to consider impacts on both parsers.

Being unreliable enough that it gets removed from the tree would constitute failure. We should be careful that such a failure doesn’t damage clang, but we needn’t avoid any project that might fail.

Maybe I was unclear, so I’ll try again with different words. Currently, it seems like you’re envisioning the maintenance of this to be a best-faith effort for people changing Clang’s parser (if you change Clang’s parser, it’d be nice if you also changed the pseudo parser, but not strictly required). We have other things that are best-faith effort like this, such as -ast-print. My experience with those best-faith efforts is that they all bit rot (almost every time – C indexing, AST dumping, and JSON node dumping are three other examples of this). Because of these experiences, I think we should be more conservative with adding new best-faith efforts to the compiler libraries. (This is somewhat orthogonal to your RFC and is more a statement about keeping maintenance costs in mind in general.)

@alexr wasn’t convinced upthread that placing it under clang-tools-extra would improve the maintenance burden, maybe we should couple it with an explicit doc laying out expectations?

I don’t think it eliminates the maintenance burdens – it’s still likely to be easy to break the pseudo parser unintentionally and that will require someone to go fix it. So my personal preference is for this to live out-of-tree until it’s far closer to completion and these sort of kinks are worked out downstream rather than upstream. However…

We’d have to take clangd out of tree to depend on it. clangd benefits a lot from being in-tree, and I think clang benefits too (it encourages us to fix things in clang rather than work around them).

This is may be a compelling reason for it to live in-tree. I see the relationship between clang and clangd as much more mutually beneficial. However, I don’t think you’d have to take clangd out of tree; couldn’t you allow in-tree clangd to optionally use the out-of-tree pseudo parser in the same way we allow other optional dependencies in tree (like Z3)? This shifts the burden from “clang proper” to “folks who maintain clangd now need to work with two parsers”, but that seems like where the burden largely belongs too.

[beanz]

A question that comes to mind for me: Is the new parser going to support all of the languages that the current parser supports?

Clang’s parser today doesn’t just support C++. It supports C, OpenCL, Objective-C, and more.

If the new parser isn’t going to support all of the languages the current parser supports, what is the plan for maintaining clangd support for those languages?

[sam-mccall]

There’s definitely a tension between wanting to ensure parity with clang, and not wanting to impose a burden on clang maintenance.
There is no way to avoid this without abandoning the effort. Trying to unify the parsers will be a huge burden on clang parser contributors.

To be clear: we propose to resolve this in favor of low clang maintenance burden by decoupling from clang. This is very similar to how clang-format works.

• they share a dependency on the lexer only. clangParse changes cannot break clang-format
• there’s no expectation that a clang parser change is paired with a clang-format change
• in practice the set of contributors is different (may overlap)
• they approximately converge based on wanting to parse standard code and real-world extensions, guided by what clang chooses to support

I think empirically this has been pretty successful.

(There’s a particular use case that challenges this layering: using a clang AST to produce an accurate syntactic parse with links between syntactic and semantic trees. It’s solvable, and this conversation has convinced me we need to be careful not to end up coupled)

@AaronBallman

When a new token kind is added, we’ll have to update both parsers because of “don’t break the build or the tests”. Even without reaching an unreachable, there will be additional warnings about no longer having a fully covered switch (in -Werror configurations), etc. So in practice, it seems likely that changes to Clang’s parser will require code reviewers and authors to consider impacts on both parsers.

I don’t think this is likely.

There’s no switch over all kinds. There’s a grammar, a new TokenKind is (automatically) a new terminal that doesn’t match any grammar rules - it gets sucked up by error recovery.
c.f. no change to Format/ here.
Breaking changes would be removal of used token kinds, these are vanishingly rare.

@AaronBallman

Currently, it seems like you’re envisioning the maintenance of this to be a best-faith effort for
people changing Clang’s parser (if you change Clang’s parser, it’d be nice if you also changed the pseudo parser, but not strictly required).

Not really. I’m expecting this to be maintained by a different (possibly overlapping) set of people. It wouldn’t be appropriate to make changes to both in the same commit, nor to gate approval of one on willingness to work on the other. If you’re working on a coroutines and want to add it to clang, define matchers, add clang-format support, and implement clangd then that’s great, but there’s no expectation you should.

@AaronBallman

My experience with those best-faith efforts is that they all bit rot (almost every time – C indexing, AST dumping, and JSON node dumping are three other examples of this).

This seems like an argument for decoupling: if there’s not enough interest to keep a peripheral feature up-to-date for its own sake, do we want it to fall behind, or put it on the critical path for clang changes, or rip it out immediately if it’s hard to keep in lockstep?

(It’s certainly also a good argument not to accept marginal features!)

@AaronBallman

my personal preference is for this to live out-of-tree until it’s far closer to completion

We did consider this option, but the developer policy specifically requests the opposite. It’s not useful as an optional dependency - we’d be better to either move clangd out of tree or drop the whole thing.

@beanz

Clang’s parser today doesn’t just support C++. It supports C, OpenCL, Objective-C, and more.

If the new parser isn’t going to support all of the languages the current parser supports, what is the plan for maintaining clangd support for those languages?

The rough plan would be:

• in principle, supporting all clang’s languages is in scope
• build the infrastructure for distinguishing between languages/versions
• Haojian and I would initially focus on C++, that’s where the most pain is (slow parse, complicated syntax) and where our day job pulls us
• ensure basic support for C and ObjC, we’re not experts, accept bug reports and patches (@DavidGoldman has contributed lots of ObjC support in clangd)
• OpenCL, CUDA etc… patches welcome

Today in clangd things work pretty well in C/C++/ObjC, leaning heavily on the fact that the clang parser unifies them. CUDA doesn’t work well (mostly driver & library discovery issues). Demand for anything else seems very low.
I’d expect much the same here: defining compatible & maintainable C/C++ grammar will be the hard part. CUDA should be easier to support

[AaronBallman]

Trying to unify the parsers will be a huge burden on clang parser contributors.

Agreed!

I don’t think this is likely.
There’s no switch over all kinds. There’s a grammar, a new TokenKind is (automatically) a new terminal that doesn’t match any grammar rules - it gets sucked up by error recovery.
c.f. no change to Format/ here.
Breaking changes would be removal of used token kinds, these are vanishingly rare.

Okay, that’s good to know. It doesn’t match my experience with the Clang parser (adding tokens has definitely caused fully-covered switch diagnostics for me in the past), but so long as the new parser is designed with this problem in mind, I think it should be fine. I agree that removing token kinds is quite rare and not a burden I’m worried about.

Not really. I’m expecting this to be maintained by a different (possibly overlapping) set of people. It wouldn’t be appropriate to make changes to both in the same commit, nor to gate approval of one on willingness to work on the other. If you’re working on a coroutines and want to add it to clang, define matchers, add clang-format support, and implement clangd then that’s great, but there’s no expectation you should.

Okay, good to know, that also makes me more comfortable.

This seems like an argument for decoupling: if there’s not enough interest to keep a peripheral feature up-to-date for its own sake, do we want it to fall behind, or put it on the critical path for clang changes, or rip it out immediately if it’s hard to keep in lockstep?

Oh, yes, definitely an argument for decoupling. Sorry if I was unclear on that; my hope was that this parser would be as fully decoupled as possible (aka, not in the tree at all), not that we would find a way to mash the existing parser into working for the RFC needs as well as typical Clang compilation needs.

(I’m coming more and more around to the idea of “rip it out immediately” btw; Clang and LLVM are extremely large projects that are amazingly slow to compile and require an inordinate amount of resources. Removing unsupported functionality and not adding unmotivated tools goes a long ways towards improving this problem. And I think we definitely need to improve this problem – hard for us to have a particularly inclusive community when the only people who can build the project require a build farm to do so, which is basically the point we’re almost at today.)

(It’s certainly also a good argument not to accept marginal features!)

+∞

We did consider this option, but the developer policy specifically requests the opposite

Yes and no. Once we know we want something in-tree, then we definitely don’t want it to be dropped on us in one huge code dump. But if we don’t know we want something in-tree yet, keeping it out of tree to prove the concept out is far less disruptive than doing experimental work in-tree. The waters are muddy here because of clangd, which we already said we wanted in-tree (but it wasn’t clear to me when we said yes to that it meant we’d be duplicating the entire parser).

It’s not useful as an optional dependency - we’d be better to either move clangd out of tree or drop the whole thing.

That’s a fair perspective.

I’m feeling a bit less worried about the burdens this will add to the Clang community than I was before, but I’m still not particularly in love with the RFC. However, if the pseudo parser lives in clang-tools-extra (which is where clangd lives), I think it’s probably reasonable. That said, please try to keep build times in mind when working on the pseudo parser as best you can (e.g., be careful/thoughtful about adding tablegen or other dependencies that are known to hurt build times). So, I consider my “no go” issues to be addressed and am in (reluctant) support of this RFC.

[sam-mccall]

Thanks Aaron, we’re going to move the code out of clang and into clang-tools-extra.
I’m working on a patch with the exact layout, probably clang-tools-extra/pseudo with #include "clang-pseudo/Token.h" as the public interface, and clang-pseudo kept as the name for the standalone tool.

EDIT: review is up: ⚙ D121233 [pseudo] Move pseudoparser from clang to clang-tools-extra

@AaronBallman

That said, please try to keep build times in mind when working on the pseudo parser as best you can (e.g., be careful/thoughtful about adding tablegen or other dependencies that are known to hurt build times).

Will do. There is likely to be a step where a header needs to be generated from the grammar (to allow code to refer directly to grammar rules). Ensuring that both its dependencies and its includers are minimized should minimize the impact on incremental builds at least. (And no impact on check-clang, which is a benefit we forgot to mention).

[ltcmelo]

Hi everyone.

I’ve worked a bit with the analysis of incomplete C programs. Of course, C is simpler than C++ to tackle, but I think that the both languages can rely on the same foundations for this task (at least on the syntactic level—on the semantic level C++ poses additional difficulties). Here are a few pointers to what I believe is contextual to this discussion.

• A formal discussion about ambiguous syntax: Fig.2 (page 5) and Section 3 (page 8) of Type Inference for C: Applications to Static Analysis of Incomplete Programs, published in TOPLAS.

• An implementation that incorporates the ideas from the above paper, keeping strict separation between syntax and semantics: the Psyche-C compiler frontend (the master branch is going through a major overhaul).

• An article highlighting the matter of precise AST rewrite, using the two-declarator—one of an object and another of a function—declaration int v, f(int d); as an example of clang’s “imprecise” (for the purpose in question) AST.