summaryrefslogtreecommitdiffstats
path: root/clang-tools-extra/unittests/clangd/DexIndexTests.cpp
Commit message (Collapse)AuthorAgeFilesLines
* [clangd] NFC: Rename DexIndex to DexKirill Bobyrev2018-09-101-615/+0
| | | | | | | | | | Also, cleanup some redundant includes. Reviewed By: sammccall Differential Revision: https://reviews.llvm.org/D51774 llvm-svn: 341784
* [clangd] Implement proximity path boosting for DexKirill Bobyrev2018-09-061-16/+80
| | | | | | | | | | | | | | | This patch introduces `PathURI` Search Token kind and utilizes it to uprank symbols which are defined in files with small distance to the directory where the fuzzy find request is coming from (e.g. files user is editing). Reviewed By: ioeric Reviewers: ioeric, sammccall Differential Revision: https://reviews.llvm.org/D51481 llvm-svn: 341542
* [clangd] Factor out the data-swapping functionality from MemIndex/DexIndex.Sam McCall2018-09-031-73/+43
| | | | | | | | | | | | | | | | | | | | | | | Summary: This is now handled by a wrapper class SwapIndex, so MemIndex/DexIndex can be immutable and focus on their job. Old and busted: I have a MemIndex, which holds a shared_ptr<vector<Symbol*>>, which keeps the symbol slab alive. I update by calling build(shared_ptr<vector<Symbol*>>). New hotness: I have a SwapIndex, which holds a unique_ptr<SymbolIndex>, which holds a MemIndex, which holds a shared_ptr<void>, which keeps backing data alive. I update by building a new MemIndex and calling SwapIndex::reset(). Reviewers: kbobyrev, ioeric Subscribers: ilya-biryukov, ioeric, MaskRay, jkorous, mgrang, arphaman, kadircet, cfe-commits Differential Revision: https://reviews.llvm.org/D51422 llvm-svn: 341318
* [clangd] Fix tests after rL341057Kirill Bobyrev2018-08-301-1/+1
| | | | | | | Since OR iterator children are not longer sorted by the estimated size, string representation should be different. llvm-svn: 341060
* [clangd] Implement iterator costKirill Bobyrev2018-08-301-2/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This patch introduces iterator cost concept to improve the performance of Dex query iterators (mainly, AND iterator). Benchmarks show that the queries become ~10% faster. Before ``` ------------------------------------------------------- Benchmark Time CPU Iteration ------------------------------------------------------- DexAdHocQueries 5883074 ns 5883018 ns 117 DexRealQ 959904457 ns 959898507 ns 1 ``` After ``` ------------------------------------------------------- Benchmark Time CPU Iteration ------------------------------------------------------- DexAdHocQueries 5238403 ns 5238361 ns 130 DexRealQ 873275207 ns 873269453 ns 1 ``` Reviewed by: sammccall Differential Revision: https://reviews.llvm.org/D51310 llvm-svn: 341057
* Cleanup after rL340729Kirill Bobyrev2018-08-271-13/+12
| | | | llvm-svn: 340759
* [clangd] Implement LIMIT iteratorKirill Bobyrev2018-08-241-24/+22
| | | | | | | | | | | | | This patch introduces LIMIT iterator, which is very important for improving the quality of search query. LIMIT iterators can be applied on top of BOOST iterators to prevent populating query request with a huge number of low-quality symbols. Reviewed by: sammccall Differential Revision: https://reviews.llvm.org/D51029 llvm-svn: 340605
* [clangd] Implement BOOST iteratorKirill Bobyrev2018-08-221-27/+72
| | | | | | | | | | | | | | | This patch introduces BOOST iterator - a substantial block for efficient and high-quality symbol retrieval. The concept of boosting allows performing computationally inexpensive scoring on the query side so that the final (expensive) scoring can only be applied on the items with the highest preliminary score while eliminating the need to score too many items. Reviewed by: ilya-biryukov Differential Revision: https://reviews.llvm.org/D50970 llvm-svn: 340409
* [clangd] DexIndex implementation prototypeKirill Bobyrev2018-08-201-2/+177
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This patch is a proof-of-concept Dex index implementation. It has several flaws, which don't allow replacing static MemIndex yet, such as: * Not being able to handle queries of small size (less than 3 symbols); a way to solve this is generating trigrams of smaller size and having such incomplete trigrams in the index structure. * Speed measurements: while manually editing files in Vim and requesting autocompletion gives an impression that the performance is at least comparable with the current static index, having actual numbers is important because we don't want to hurt the users and roll out slow code. Eric (@ioeric) suggested that we should only replace MemIndex as soon as we have the evidence that this is not a regression in terms of performance. An approach which is likely to be successful here is to wait until we have benchmark library in the LLVM core repository, which is something I have suggested in the LLVM mailing lists, received positive feedback on and started working on. I will add a dependency as soon as the suggested patch is out for a review (currently there's at least one complication which is being addressed by https://github.com/google/benchmark/pull/649). Key performance improvements for iterators are sorting by cost and the limit iterator. * Quality measurements: currently, boosting iterator and two-phase lookup stage are not implemented, without these the quality is likely to be worse than the current implementation can yield. Measuring quality is tricky, but another suggestion in the offline discussion was that the drop-in replacement should only happen after Boosting iterators implementation (and subsequent query enhancement). The proposed changes do not affect Clangd functionality or performance, `DexIndex` is only used in unit tests and not in production code. Reviewed by: ioeric Differential Revision: https://reviews.llvm.org/D50337 llvm-svn: 340175
* [clangd] NFC: Cleanup Dex Iterator comments and simplify testsKirill Bobyrev2018-08-201-19/+19
| | | | | | | | | | | | | | | | | | | | | Proposed changes: * Cleanup comments in `clangd/index/dex/Iterator.h`: Vim's `gq` formatting added redundant spaces instead of newlines in few places * Few comments in `OrIterator` are wrong * Use `EXPECT_TRUE(Condition)` instead of `EXPECT_THAT(Condition, true)` (same with `EXPECT_FALSE`) * Don't expose `dump()` method to the public by misplacing `private:` This patch does not affect functionality. Reviewed by: ioeric Differential Revision: https://reviews.llvm.org/D50956 llvm-svn: 340157
* [clangd] Implement TRUE IteratorKirill Bobyrev2018-08-201-0/+13
| | | | | | | | | | | This patch introduces TRUE Iterator which efficiently handles posting lists containing all items within `[0, Size)` range. Reviewed by: ioeric Differential Revision: https://reviews.llvm.org/D50955 llvm-svn: 340155
* [clangd] NFC: Improve Dex Iterators debugging traitsKirill Bobyrev2018-08-161-2/+3
| | | | | | | | | | | | This patch improves `dex::Iterator` string representation by incorporating the information about the element which is currently being pointed to by the `DocumentIterator`. Reviewed by: ioeric Differential Revision: https://reviews.llvm.org/D50689 llvm-svn: 339877
* [clangd] Generate incomplete trigrams for the Dex indexKirill Bobyrev2018-08-131-24/+36
| | | | | | | | | | | | | | This patch handles trigram generation "short" identifiers and queries. Trigram generator produces incomplete trigrams for short names so that the same query iterator API can be used to match symbols which don't have enough symbols to form a trigram and correctly handle queries which also are not sufficient for generating a full trigram. Reviewed by: ioeric Differential revision: https://reviews.llvm.org/D50517 llvm-svn: 339548
* [clangd] Allow consuming limited number of itemsKirill Bobyrev2018-08-101-0/+21
| | | | | | | | | | | | | | | | | This patch modifies `consume` function to allow retrieval of limited number of symbols. This is the "cheap" implementation of top-level limiting iterator. In the future we would like to have a complete limit iterator implementation to insert it into the query subtrees, but in the meantime this version would be enough for a fully-functional proof-of-concept Dex implementation. Reviewers: ioeric, ilya-biryukov Reviewed by: ioeric Differential Revision: https://reviews.llvm.org/D50500 llvm-svn: 339426
* [clangd] Return Dex IteratorsKirill Bobyrev2018-07-271-1/+220
| | | | | | | | | | | | | | | The original Dex Iterators patch (https://reviews.llvm.org/rL338017) caused problems for Clang 3.6 and Clang 3.7 due to the compiler bug which prevented inferring template parameter (`Size`) in create(And|Or)? functions. It was reverted in https://reviews.llvm.org/rL338054. In this revision the mentioned helper functions were replaced with variadic templated versions. Proposed changes were tested on multiple compiler versions, including Clang 3.6 which originally caused the failure. llvm-svn: 338116
* Revert Clangd Dex Iterators patchKirill Bobyrev2018-07-261-223/+1
| | | | | | | | | | | | This reverts two revisions: * https://reviews.llvm.org/rL338017 * https://reviews.llvm.org/rL338028 They caused crash for Clang 3.6 & Clang 3.7 buildbots, it was reported by Jeremy Morse. llvm-svn: 338054
* [clangd] Fix unit tests for DexKirill Bobyrev2018-07-261-7/+20
| | | | | | | Iterators took temporary objects in constructors, objects were invalidated when built with recent Clang which resulted in crashes. llvm-svn: 338028
* [clangd] Proof-of-concept query iterators for Dex symbol indexKirill Bobyrev2018-07-261-1/+212
| | | | | | | | | | | | | | | | | | | | | | | | | | This patch introduces three essential types of query iterators: `DocumentIterator`, `AndIterator`, `OrIterator`. It provides a convenient API for query tree generation and serves as a building block for the next generation symbol index - Dex. Currently, many optimizations are missed to improve code readability and to serve as the reference implementation. Potential improvements are briefly mentioned in `FIXME`s and will be addressed in the following patches. Dex RFC in the mailing list: http://lists.llvm.org/pipermail/clangd-dev/2018-July/000022.html Iterators, their applications and potential extensions are explained in detail in the design proposal: https://docs.google.com/document/d/1C-A6PGT6TynyaX4PXyExNMiGmJ2jL1UwV91Kyx11gOI/edit#heading=h.903u1zon9nkj Reviewers: ioeric, sammccall, ilya-biryukov Subscribers: cfe-commits, klimek, jfb, mgrang, mgorny, MaskRay, jkorous, arphaman Differential Revision: https://reviews.llvm.org/D49546 llvm-svn: 338017
* [clangd] Introduce Dex symbol index search tokensKirill Bobyrev2018-07-251-0/+96
This patch introduces the core building block of the next-generation Clangd symbol index - Dex. Search tokens are the keys in the inverted index and represent a characteristic of a specific symbol: examples of search token types (Token Namespaces) are * Trigrams - these are essential for unqualified symbol name fuzzy search * Scopes for filtering the symbols by the namespace * Paths, e.g. these can be used to uprank symbols defined close to the edited file This patch outlines the generic for such token namespaces, but only implements trigram generation. The intuition behind trigram generation algorithm is that each extracted trigram is a valid sequence for Fuzzy Matcher jumps, proposed implementation utilize existing FuzzyMatcher API for segmentation and trigram extraction. However, trigrams generation algorithm for the query string is different from the previous one: it simply yields sequences of 3 consecutive lowercased valid characters (letters, digits). Dex RFC in the mailing list: http://lists.llvm.org/pipermail/clangd-dev/2018-July/000022.html The trigram generation techniques are described in detail in the proposal: https://docs.google.com/document/d/1C-A6PGT6TynyaX4PXyExNMiGmJ2jL1UwV91Kyx11gOI/edit#heading=h.903u1zon9nkj Reviewers: sammccall, ioeric, ilya-biryukovA Subscribers: cfe-commits, klimek, mgorny, MaskRay, jkorous, arphaman Differential Revision: https://reviews.llvm.org/D49591 llvm-svn: 337901
OpenPOWER on IntegriCloud