In D50703#1205049, @malaperle wrote:

I hadn't marked it as done because without symbols in main files I found it quite lacking.

I should create another patch with True iterator to address the last comment.

Address all the comment, except the one about True iterators.

Thank you for the feedback! I will fuzz over the weekend just in case and update the benchmark before submitting.

Address another round of comments.

Fix anonymous namespace beginning placement in Clangd driver.

Address another round of comments.

As Eric suggested, such change might reduce the quality of code completion. A more generic approach is yet to be investigated and requires significantly more time resources, we should try it after we get other parts of the index to work as expected.

Add couple tests, fix formatting issues, use __builtin_trap() instead of assert in fuzzer so that it's more transparent.

Address a round of comments.

I tried to rewrite the loop, but IMO it looks even worse now.

Upload version which is IMO readable.

Use consistent Regex matchers naming: don't append "Matcher" at the end.

Very good point by @lebedev.ri! I have added a very simple fuzzer for the parser. So far, there were no issues with the current implementation. I have not exposed the regexp matcher to the header, though, because it won't be used anywhere.

Sorry, the last diff was the old one. Should be correct now.

Improved wording to prevent confusion: no more IDX (which is the one pointed to by the iterator) and IDN; just mention that the element being pointed to is the one enclosed in {} braces.

I have updated the patch so that it only affects comments, header guards and inserts few newlines. Actual source code is not affected so that git blame log could be less cryptic.

Don't separate the logic for "long" and "short" queries: D50517 (rCTE339548) introduced incomplete trigrams which can be used on for "short" queries, too.

Treat leading underscores as additional signals and don't extract two heads in that case.

As discussed offline, I should update the patch to reflect changes accepted in https://reviews.llvm.org/D50517.

As discussed, this is not a very clean API for the user interaction and it's OK to leave consume() as is.

Address the post-LGTM comment.

Address a round of comments.

Store symbol qualities (so that it's not computed each time when requested which might be expensive). Use operator[] to construct the value for inverted index when key is not inserted yet.

Address issues we have discussed with Eric.

Address most comments.

Address issues we discussed with Eric.

In D50517#1194990, @ioeric wrote:

In D50517#1194976, @kbobyrev wrote:

As discussed offline with @ilya-biryukov, the better approach would be to prefix match first symbols of each distinct identifier piece instead of prefix matching (just looking at the first letter of the identifier) the whole identifier.

Example:

• Query: "u"
• Symbols: "unique_ptr", "user", "super_user"
  
  Current implementation would match "unique_ptr" and "user" only. Proposed implementation would match all three symbols, because the second piece of "super_user" starts with u.

And in the case where users want to match super_user, I think it's reasonable to have users type two more characters and match it with use.

Address a round of comments.

@ilya-biryukov I have changed the approach to the one we discussed before.

As discussed offline with @ilya-biryukov, the better approach would be to prefix match first symbols of each distinct identifier piece instead of prefix matching (just looking at the first letter of the identifier) the whole identifier.

Complete the tests, finish the implementation.

Fix the implementation and add test coverage.

Oops, I thought I pushed "Plan Changes" for this one.

This patch is in preview mode and can be useful for the discussion. It's not functional yet, but this will be changed in the future.

Address a round of comments. Also put FIXMEs where appropriate for the future changes.

Minor code cleanup. This is now a fully functional symbol index.

Continue implementing Proof of Concept Dex-based static index replacement.

As discussed offline, incomplete trigrams (unigrams and bigrams generation) should be a blocker for this patch, because otherwise it isn't functional. Once incomplete trigrams are in, MemIndex tests can be reused for DexIndex to ensure stability.

Don't resize retrieved symbols vector, simply let callback process at most MaxCandidateCount items.

The patch is currently in preview-mode; I have to make few changes:

Address post-lg round of comments.

Rebase on top of https://reviews.llvm.org/rL337901

Addressed a round of comments: cleaned up the code, improved documentation and properly introduced such terms like Posting List and Query Tree. Tests are now more modular and each specific piece tests a certain part of implementation.

Typo: "Returns false if ..., false otherwise" ->"Returns false if ..., true otherwise".

Addressed two comments, added an example of running the tool over a number of source files without providing compile_commands.json; added a note about collecting files from headers only.

Choose better wording in a couple of places.

Slightly refactored the code, improved documentation. This patch is ready for review.

Address the last round of comments.

Address last round of comments.

Address all comments, refine tests.

Refactored unit tests in few places.

As discussed offline: I simplified the implementation and cleaned up unit tests. Should look better now.

Wrong diff, should be correct now.

Address all comments from the last iteration.

• Implemented convenient dumping via llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, QueryIterator &Iterator), which dumps iterator tree in human-readable format, e.g. (&& [1, 2, 3] (|| [3, 4, 5] []))
• Implemented rather straightforward iterator cost for more efficient AndIterator iterations

Upcoming changes:

• Switched from std::shared_ptr to std::unique_ptr for iterator's children: iterators own their subtrees, the lifetime should depend on the root
• Store PostingListRefin DocumentIterator: the lifetime of underlying PostingList should be longer than the DocumentIterator anyway, DocumentIterator can not retrieve results from an incomplete inverted index
• Refined API of different iterators: wipe getIndex(), reset() from DocumentIterator, getChildren from AndIterator and OrIterator
• Not exposing DocumentIterator, AndIterator, OrIterator to the User API anymore: helper functions like std::unique_ptr<QueryIterator> constructDocumentIterator which return a unique pointer and perform type erasure are provided instead
• Improved variable naming, applied refactorings where necessary