[clangd] DexIndex implementation prototype

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

0 files changed, 0 insertions, 0 deletions