This is an archive of the discontinued LLVM Phabricator instance.

[clang][clangd] Use reverse header map lookup in suggestPathToFileForDiagnostics
ClosedPublic

Authored by DmitryPolukhin on May 26 2021, 1:50 AM.

Details

Summary

suggestPathToFileForDiagnostics is actively used in clangd for converting
an absolute path to a header file to a header name as it should be spelled
in the sources. Current approach converts absolute path to relative path.
This diff implements missing logic that makes a reverse lookup from the
relative path to the key in the header map that should be used in the sources.

Prerequisite diff https://reviews.llvm.org/D103229

Test Plan: check-clang

Diff Detail

Event Timeline

DmitryPolukhin created this revision.May 26 2021, 1:50 AM
DmitryPolukhin requested review of this revision.May 26 2021, 1:50 AM

Fix clang-format issue

bruno added inline comments.
clang/lib/Lex/HeaderSearch.cpp
1858–1865

-> filename

1862

Can we save some dir scanning time by adding this logic to the previous loop? Shouldn't get hard to read if you early continue for each failed condition.

1866

I guess one of the rationale behind this change is that whatever is consuming your diagnostics is expecting the hmap key entry as an actionable path they could use.

I wonder whether other consumers of suggestPathToFileForDiagnostics expect an actual mapped value or just don't care. If the former, this might be better under some flag.

@dexonsmith @vsapsai @JDevlieghere @arphaman how does this relate with what you expect out of suggestPathToFileForDiagnostics? (If at all).

Naively, this sounds like it could be a non-trivial tax on build times. But it looks like it's only called in Clang from Sema::diagnoseMissingImport, which only happens on error anyway.

clang/unittests/Lex/HeaderMapTest.cpp
9 ↗(On Diff #347864)

Splitting this out seems like a great idea, but please split it out to a separate prep commit that's NFC.

DmitryPolukhin marked 2 inline comments as done.

Split changes into NFC https://reviews.llvm.org/D103229 and the rest

Naively, this sounds like it could be a non-trivial tax on build times. But it looks like it's only called in Clang from Sema::diagnoseMissingImport, which only happens on error anyway.

Yes, in Clang suggestPathToFileForDiagnostics is used only in Sema::diagnoseMissingImport. In addition to clangd this function is also used in clang-include-fixer but new logic should also work there too (add @bkramer author of clang-include-fixer). This diff builds reverse index lazy only when it is required so it shouldn't normal build speed.

clang/lib/Lex/HeaderSearch.cpp
1862

It seems that unfortunately no, because we need the previous loop to convert absolute path into relative and this loop to convert relative path to key in header map. Normal header lookup also happens as two lookups: first lookup uses header map to convert key to relative path and then another lookup of the relative path.

1862

It seems that unfortunately no, because we need the previous loop to convert absolute path into relative and this loop to convert relative path to key in header map. Normal header lookup also happens as two lookups: first lookup uses header map to convert key to relative path and then another lookup of the relative path.

1866

I think it is safe to change default behaviour without introducing new flag/option because I don't expect that anyone really needs value from header map search in the source.

clang/unittests/Lex/HeaderMapTest.cpp
9 ↗(On Diff #347864)
DmitryPolukhin edited the summary of this revision. (Show Details)May 27 2021, 2:01 AM

Fix forgotten comment

bruno requested changes to this revision.May 27 2021, 5:32 PM

Overall looks good, few remaining nitpicks.

clang/lib/Lex/HeaderMap.cpp
245

Please rewrite this to early return in case this isn't empty.

clang/lib/Lex/HeaderSearch.cpp
1863

Similar from above: rewrite to early continue if it's not meeting the conditions.

This revision now requires changes to proceed.May 27 2021, 5:32 PM
DmitryPolukhin marked 2 inline comments as done.

Resolved comments

clang/lib/Lex/HeaderMap.cpp
245

Done, but it causes a bit of code duplication due to second lookup. Please let me know if you thought about rewriting it somehow else.

Rebase + try build on Windows again

bruno added inline comments.Jun 1 2021, 1:01 PM
clang/lib/Lex/HeaderMap.cpp
265

How about something along the lines of:

...
StringRef Key;
for (unsigned i = 0; i != NumBuckets; ++i) {
    HMapBucket B = getBucket(i);
    if (B.Key == HMAP_EmptyBucketKey)
      continue;

    Key = getString(B.Key);
    Optional<StringRef> Prefix = getString(B.Prefix);
    Optional<StringRef> Suffix = getString(B.Suffix);
    if (!Key.empty() && Prefix && Suffix) {
      SmallVector<char, 1024> Buf;
      Buf.append(Prefix->begin(), Prefix->end());
      Buf.append(Suffix->begin(), Suffix->end());
      ReverseMap[StringRef(Buf.begin(), Buf.size())] = Key;
      break;
    }
}
assert(!Key.empty() && "expected valid key");
return Key;

While proposing this change I've noticed that it would keep looking for other buckets even in face of a valid result, so I've added a break. Was that intentional?

Updated HeaderMapImpl::reverseLookupFilename according to the review comment

DmitryPolukhin added inline comments.Jun 2 2021, 2:08 AM
clang/lib/Lex/HeaderMap.cpp
265

Yes, keep iterating over all key-value pairs in the header map is important to add all elements to the map for subsequent lookups. If we stop on the current match, next lookup will not even try to populate the reverse lookup map (because the map is not empty) but not all elements are in the map due to early return from previous lookup, so subsequent lookup may not find the match even if it exists in the header map. We also cannot expect that DestPath is present in the given header map, so we cannot assert if it is missing. This function should return empty string as an indication that DestPath is not found.

Updated implementation with the review suggestion, please take another look.

bruno accepted this revision.Jun 2 2021, 9:31 AM

LGTM!

This revision is now accepted and ready to land.Jun 2 2021, 9:31 AM

@bruno and @dexonsmith thank you for the review!