Index: clang-tools-extra/trunk/clangd/index/dex/Dex.h =================================================================== --- clang-tools-extra/trunk/clangd/index/dex/Dex.h +++ clang-tools-extra/trunk/clangd/index/dex/Dex.h @@ -6,15 +6,16 @@ // License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// -// -// This defines Dex - a symbol index implementation based on query iterators -// over symbol tokens, such as fuzzy matching trigrams, scopes, types, etc. -// While consuming more memory and having longer build stage due to -// preprocessing, Dex will have substantially lower latency. It will also allow -// efficient symbol searching which is crucial for operations like code -// completion, and can be very important for a number of different code -// transformations which will be eventually supported by Clangd. -// +/// +/// \file +/// This defines Dex - a symbol index implementation based on query iterators +/// over symbol tokens, such as fuzzy matching trigrams, scopes, types, etc. +/// While consuming more memory and having longer build stage due to +/// preprocessing, Dex will have substantially lower latency. It will also allow +/// efficient symbol searching which is crucial for operations like code +/// completion, and can be very important for a number of different code +/// transformations which will be eventually supported by Clangd. +/// //===----------------------------------------------------------------------===// #ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_DEX_DEX_H Index: clang-tools-extra/trunk/clangd/index/dex/Dex.cpp =================================================================== --- clang-tools-extra/trunk/clangd/index/dex/Dex.cpp +++ clang-tools-extra/trunk/clangd/index/dex/Dex.cpp @@ -23,7 +23,7 @@ namespace { // Mark symbols which are can be used for code completion. -static const Token RestrictedForCodeCompletion = +const Token RestrictedForCodeCompletion = Token(Token::Kind::Sentinel, "Restricted For Code Completion"); // Returns the tokens which are given symbol's characteristics. Currently, the Index: clang-tools-extra/trunk/clangd/index/dex/Iterator.h =================================================================== --- clang-tools-extra/trunk/clangd/index/dex/Iterator.h +++ clang-tools-extra/trunk/clangd/index/dex/Iterator.h @@ -6,25 +6,26 @@ // License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// -// -// Symbol index queries consist of specific requirements for the requested -// symbol, such as high fuzzy matching score, scope, type etc. The lists of all -// symbols matching some criteria (e.g. belonging to "clang::clangd::" scope) -// are expressed in a form of Search Tokens which are stored in the inverted -// index. Inverted index maps these tokens to the posting lists - sorted (by -// symbol quality) sequences of symbol IDs matching the token, e.g. scope token -// "clangd::clangd::" is mapped to the list of IDs of all symbols which are -// declared in this namespace. Search queries are build from a set of -// requirements which can be combined with each other forming the query trees. -// The leafs of such trees are posting lists, and the nodes are operations on -// these posting lists, e.g. intersection or union. Efficient processing of -// these multi-level queries is handled by Iterators. Iterators advance through -// all leaf posting lists producing the result of search query, which preserves -// the sorted order of IDs. Having the resulting IDs sorted is important, -// because it allows receiving a certain number of the most valuable items (e.g. -// symbols with highest quality which was the sorting key in the first place) -// without processing all items with requested properties (this might not be -// computationally effective if search request is not very restrictive). +/// +/// \file +/// Symbol index queries consist of specific requirements for the requested +/// symbol, such as high fuzzy matching score, scope, type etc. The lists of all +/// symbols matching some criteria (e.g. belonging to "clang::clangd::" scope) +/// are expressed in a form of Search Tokens which are stored in the inverted +/// index. Inverted index maps these tokens to the posting lists - sorted (by +/// symbol quality) sequences of symbol IDs matching the token, e.g. scope token +/// "clangd::clangd::" is mapped to the list of IDs of all symbols which are +/// declared in this namespace. Search queries are build from a set of +/// requirements which can be combined with each other forming the query trees. +/// The leafs of such trees are posting lists, and the nodes are operations on +/// these posting lists, e.g. intersection or union. Efficient processing of +/// these multi-level queries is handled by Iterators. Iterators advance through +/// all leaf posting lists producing the result of search query, which preserves +/// the sorted order of IDs. Having the resulting IDs sorted is important, +/// because it allows receiving a certain number of the most valuable items +/// (e.g. symbols with highest quality which was the sorting key in the first +/// place) without processing all items with requested properties (this might +/// not be computationally effective if search request is not very restrictive). // //===----------------------------------------------------------------------===// Index: clang-tools-extra/trunk/clangd/index/dex/Iterator.cpp =================================================================== --- clang-tools-extra/trunk/clangd/index/dex/Iterator.cpp +++ clang-tools-extra/trunk/clangd/index/dex/Iterator.cpp @@ -64,11 +64,10 @@ float consume() override { assert(!reachedEnd() && "AND iterator can't consume() at the end."); - return std::accumulate( - begin(Children), end(Children), DEFAULT_BOOST_SCORE, - [&](float Current, const std::unique_ptr &Child) { - return Current * Child->consume(); - }); + float Boost = DEFAULT_BOOST_SCORE; + for (const auto &Child : Children) + Boost *= Child->consume(); + return Boost; } size_t estimateSize() const override { @@ -140,10 +139,10 @@ /// Returns true if all children are exhausted. bool reachedEnd() const override { - return std::all_of(begin(Children), end(Children), - [](const std::unique_ptr &Child) { - return Child->reachedEnd(); - }); + for (const auto &Child : Children) + if (!Child->reachedEnd()) + return false; + return true; } /// Moves each child pointing to the smallest DocID to the next item. @@ -181,21 +180,18 @@ float consume() override { assert(!reachedEnd() && "OR iterator can't consume() at the end."); const DocID ID = peek(); - return std::accumulate( - begin(Children), end(Children), DEFAULT_BOOST_SCORE, - [&](float Boost, const std::unique_ptr &Child) { - return (!Child->reachedEnd() && Child->peek() == ID) - ? std::max(Boost, Child->consume()) - : Boost; - }); + float Boost = DEFAULT_BOOST_SCORE; + for (const auto &Child : Children) + if (!Child->reachedEnd() && Child->peek() == ID) + Boost = std::max(Boost, Child->consume()); + return Boost; } size_t estimateSize() const override { - return std::accumulate( - begin(Children), end(Children), Children.front()->estimateSize(), - [&](size_t Current, const std::unique_ptr &Child) { - return std::max(Current, Child->estimateSize()); - }); + size_t Size = 0; + for (const auto &Child : Children) + Size = std::max(Size, Child->estimateSize()); + return Size; } private: Index: clang-tools-extra/trunk/clangd/index/dex/Token.h =================================================================== --- clang-tools-extra/trunk/clangd/index/dex/Token.h +++ clang-tools-extra/trunk/clangd/index/dex/Token.h @@ -6,17 +6,18 @@ // License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// -// -// Token objects represent a characteristic of a symbol, which can be used to -// perform efficient search. Tokens are keys for inverted index which are mapped -// to the corresponding posting lists. -// -// The symbol std::cout might have the tokens: -// * Scope "std::" -// * Trigram "cou" -// * Trigram "out" -// * Type "std::ostream" -// +/// +/// \file +/// Token objects represent a characteristic of a symbol, which can be used to +/// perform efficient search. Tokens are keys for inverted index which are +/// mapped to the corresponding posting lists. +/// +/// The symbol std::cout might have the tokens: +/// * Scope "std::" +/// * Trigram "cou" +/// * Trigram "out" +/// * Type "std::ostream" +/// //===----------------------------------------------------------------------===// #ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_DEX_TOKEN_H Index: clang-tools-extra/trunk/clangd/index/dex/Trigram.h =================================================================== --- clang-tools-extra/trunk/clangd/index/dex/Trigram.h +++ clang-tools-extra/trunk/clangd/index/dex/Trigram.h @@ -6,18 +6,19 @@ // License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// -// -// Trigrams are attributes of the symbol unqualified name used to effectively -// extract symbols which can be fuzzy-matched given user query from the inverted -// index. To match query with the extracted set of trigrams Q, the set of -// generated trigrams T for identifier (unqualified symbol name) should contain -// all items of Q, i.e. Q ⊆ T. -// -// Trigram sets extracted from unqualified name and from query are different: -// the set of query trigrams only contains consecutive sequences of three -// characters (which is only a subset of all trigrams generated for an -// identifier). -// +/// +/// \file +/// Trigrams are attributes of the symbol unqualified name used to effectively +/// extract symbols which can be fuzzy-matched given user query from the +/// inverted index. To match query with the extracted set of trigrams Q, the set +/// of generated trigrams T for identifier (unqualified symbol name) should +/// contain all items of Q, i.e. Q ⊆ T. +/// +/// Trigram sets extracted from unqualified name and from query are different: +/// the set of query trigrams only contains consecutive sequences of three +/// characters (which is only a subset of all trigrams generated for an +/// identifier). +/// //===----------------------------------------------------------------------===// #ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_DEX_TRIGRAM_H