Closed Bug 1781178 Opened 2 years ago Closed 1 year ago

Improve Searchfox's ability to resolve symbol definitions in templated C++ code

Categories

(Webtools :: Searchfox, enhancement)

enhancement

Tracking

(Not tracked)

RESOLVED FIXED

People

(Reporter: botond, Assigned: botond)

References

(Blocks 4 open bugs)

Details

(Keywords: meta)

Providing accurate code navigation in templated C++ code is a hard problem. Many symbol names in templated code are "dependent names" (meaning, they depend in some way on a template parameter), which the compiler only resolves to a symbol definition during instantiation -- but we read and write and want to navigate uninstantiated code.

Tools typically employ heuristics to provide navigation features in templated code, and Searchfox has some good ones already.

As someone who also uses clangd to navigate and edit mozilla-central locally, I've noticed that there are some cases that clangd's heuristics handle but Searchfox's currently do not.

I'd like to port over the missing pieces of clangd's template heuristics (many of which I implemented in clangd) to Searchfox. Since clangd and Searchfox are both based on clang's C++ API, Searchfox should in principle be able to implement anything that clangd does.

Here are some examples of symbol names in templated code which Searchfox currently does not resolve to a symbol definition but clangd does:

  • Function/method names
    • ProjectPoint() here
    • HasPositiveWCoord() here
    • FromUnknownMatrix() and ToUnknownMatrix() here
    • (Other similar examples in our Matrix library, these likely have a small set of common root causes.)
    • TransformPoint() here
      • Here, clangd's current behaviour isn't ideal either (it offers all the overloads of the target function, not just the relevant one), but better than nothing
    • Cases using the template disambiguator, such as downcast here
    • format here (maybe related to the use of a union?)
  • Type names

(Note 1: I provided permalinks to protect against code rot, but testing Searchfox's navigation behaviour requires clicking "Go to latest revision" first, since only the latest revision is indexed semantically.)

(Note 2: There are also cases where Searchfox is able to resolve a definition that clangd doesn't! In some cases, this is due to known limitations of clangd, such as only indexing code on one platform at a time. In other cases, I imagine Searchfox knows some tricks that clangd doesn't, which I'm hoping to learn about and port back over to clangd in turn :))

In this bug, I plan to focus on Searchfox's "go to definition" feature. "Find references" in templated code could also use improvement (e.g. bug 1535149 and related), but I suspect that's less a matter of porting over heuristics from clangd (which unfortunately also doesn't handle this very well), and more a matter of getting Searchfox to index template instantiations.

Over the course of this work, I would also like to keep an eye out for possible opportunities to "upstream" code implementing relevant heuristics to a place that both clangd and Searchfox can reuse (e.g. libclangAST/libclangSema).

My plan here is to fix this incrementally in dependent bugs, treating this as a meta bug.

(In reply to Botond Ballo [:botond] from comment #0)

Here are some examples of symbol names in templated code which Searchfox currently does not resolve to a symbol definition but clangd does:

  • Function/method names
    • ProjectPoint() here

Reduced as bug 1799579.

Depends on: 1799579
Keywords: meta

(In reply to Botond Ballo [:botond] from comment #0)

  • ProjectPoint() here

Confirmed fixed by bug 1799579.

Depends on: 1828223

(In reply to Botond Ballo [:botond] from comment #0)

  • HasPositiveWCoord() here

Reduced as bug 1828223.

Depends on: 1833072

(In reply to Botond Ballo [:botond] from comment #0)

  • FromUnknownMatrix() and ToUnknownMatrix() here

Reduced ToUnknownMatrix() as bug 1833072.

Depends on: 1833073

(In reply to Botond Ballo [:botond] from comment #0)

  • FromUnknownMatrix() and ToUnknownMatrix() here

Reduced FromUnknownMatrix() as bug 1833073.

Depends on: 1833272

(In reply to Botond Ballo [:botond] from comment #0)

  • TransformPoint() here

Reduced as bug 1833272.

Blocks: 1833548
Blocks: 1833552
Blocks: 1833555

(In reply to Botond Ballo [:botond] from comment #0)

  • Cases using the template disambiguator, such as downcast here

With bug 1833272, this is now highlighted as a symbol use, but the only (semantic) context menu item offered for it is "search", and while the symbol name displayed in that context menu item (mozilla::SafeRefPtr::downcast) looks correct, the only search result is the original use itself, not a definition or declaration (or other uses).

Unfortunately, this has resisted my attempts to reduce it to a minimal testcase for debugging purposes (i.e. single-file testcases that I've tried to prepare with code that has similar structure do not exhibit this issue).

I did spot check other uses of the template disambiguator (such as this one, this one, this one, and this one), and those seem to be working well, so I'm going to defer this particular one for future investigation, without being concerned that we're overlooking an important category of template uses.

Depends on: 1834859

(In reply to Botond Ballo [:botond] from comment #0)

  • format here (maybe related to the use of a union?)

Reduced as bug 1834859.

Note that, while I listed this under "function/method names" in comment 0, this is actually a field name, and the issue is likely related to the fact that the heuristics added for previous cases handle methods but not fields.

Depends on: 1833529
Depends on: 1835433
Depends on: 1621789
No longer depends on: 1835433

(In reply to Botond Ballo [:botond] from comment #0)

Posted reduced testcase in bug 1621789. (I'm not sure why I categorized this one under "type names"; this is an enumerator name, not a type name.)

Blocks: 1835692
Depends on: 1835694
Depends on: 1835696

(In reply to Botond Ballo [:botond] from comment #0)

  • const_iterator here

Reduced as bug 1835696.

(In reply to Botond Ballo [:botond] from comment #0)

This one is fixed by the patch in bug 1835696 as well.

As the examples listed in comment 0 have now been addressed, I'm going to close this bug. There are opportunities for further improvement in this area, some of which are tracked in the bugs this one is marked as blocking.

A couple of closing notes:

(In reply to Botond Ballo [:botond] from comment #0)

(Note 2: There are also cases where Searchfox is able to resolve a definition that clangd doesn't! In some cases, this is due to known limitations of clangd, such as only indexing code on one platform at a time. In other cases, I imagine Searchfox knows some tricks that clangd doesn't, which I'm hoping to learn about and port back over to clangd in turn :))

The main trick that Searchfox knows that clangd doesn't that I've come across is the "AutoTemplateContext" machinery to traverse known instantiations of templates and associate uses in the template body with the targets they resolve to in those instantiations (what I've been calling "concrete results" in places like bug 1833552).

Clangd would benefit from machinery like this as well, and I plan to explore adding that as time permits.

Over the course of this work, I would also like to keep an eye out for possible opportunities to "upstream" code implementing relevant heuristics to a place that both clangd and Searchfox can reuse (e.g. libclangAST/libclangSema).

HeuristicResolver is a nice standalone component that Searchfox currently uses a copy of, which would be nice to upstream from clangd to the clang libraries and make it public API, allowing Searchfox to consume the copy inside the clang libraries directly. I plan to explore this upstreaming as time permits. A prerequisite for this is writing a dedicated test suite for HeuristicResolver, whose code is currently tested indirectly via tests that exercise its clients in clangd (and Searchfox).

Status: NEW → RESOLVED
Closed: 1 year ago
Resolution: --- → FIXED
Assignee: nobody → botond
You need to log in before you can comment on or make changes to this bug.