198 lines · c
1//===--- Iterator.h - Query Symbol Retrieval --------------------*- C++ -*-===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8///9/// \file10/// Symbol index queries consist of specific requirements for the requested11/// symbol, such as high fuzzy matching score, scope, type etc. The lists of all12/// symbols matching some criteria (e.g. belonging to "clang::clangd::" scope)13/// are expressed in a form of Search Tokens which are stored in the inverted14/// index. Inverted index maps these tokens to the posting lists - sorted (by15/// symbol quality) sequences of symbol IDs matching the token, e.g. scope token16/// "clangd::clangd::" is mapped to the list of IDs of all symbols which are17/// declared in this namespace. Search queries are build from a set of18/// requirements which can be combined with each other forming the query trees.19/// The leafs of such trees are posting lists, and the nodes are operations on20/// these posting lists, e.g. intersection or union. Efficient processing of21/// these multi-level queries is handled by Iterators. Iterators advance through22/// all leaf posting lists producing the result of search query, which preserves23/// the sorted order of IDs. Having the resulting IDs sorted is important,24/// because it allows receiving a certain number of the most valuable items25/// (e.g. symbols with highest quality which was the sorting key in the first26/// place) without processing all items with requested properties (this might27/// not be computationally effective if search request is not very restrictive).28//29//===----------------------------------------------------------------------===//30 31#ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_DEX_ITERATOR_H32#define LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_DEX_ITERATOR_H33 34#include "llvm/Support/raw_ostream.h"35#include <algorithm>36#include <memory>37#include <vector>38 39namespace clang {40namespace clangd {41namespace dex {42 43/// Symbol position in the list of all index symbols sorted by a pre-computed44/// symbol quality.45using DocID = uint32_t;46 47/// Iterator is the interface for Query Tree node. The simplest type of Iterator48/// is DocumentIterator which is simply a wrapper around PostingList iterator49/// and serves as the Query Tree leaf. More sophisticated examples of iterators50/// can manage intersection, union of the elements produced by other iterators51/// (their children) to form a multi-level Query Tree. The interface is designed52/// to be extensible in order to support multiple types of iterators.53class Iterator {54public:55 /// Returns true if all valid DocIDs were processed and hence the iterator is56 /// exhausted.57 virtual bool reachedEnd() const = 0;58 /// Moves to next valid DocID. If it doesn't exist, the iterator is exhausted59 /// and proceeds to the END.60 ///61 /// Note: reachedEnd() must be false.62 virtual void advance() = 0;63 /// Moves to the first valid DocID which is equal or higher than given ID. If64 /// it doesn't exist, the iterator is exhausted and proceeds to the END.65 ///66 /// Note: reachedEnd() must be false.67 virtual void advanceTo(DocID ID) = 0;68 /// Returns the current element this iterator points to.69 ///70 /// Note: reachedEnd() must be false.71 virtual DocID peek() const = 0;72 /// Informs the iterator that the current document was consumed, and returns73 /// its boost.74 ///75 /// Note: If this iterator has any child iterators that contain the document,76 /// consume() should be called on those and their boosts incorporated.77 /// consume() must *not* be called on children that don't contain the current78 /// doc.79 virtual float consume() = 0;80 /// Returns an estimate of advance() calls before the iterator is exhausted.81 virtual size_t estimateSize() const = 0;82 83 virtual ~Iterator() {}84 85 /// Prints a convenient human-readable iterator representation by recursively86 /// dumping iterators in the following format:87 ///88 /// (Type Child1 Child2 ...)89 ///90 /// Where Type is the iterator type representation: "&" for And, "|" for Or,91 /// ChildN is N-th iterator child. Raw iterators over PostingList are92 /// represented as "[... CurID ...]" where CurID is the current PostingList93 /// entry being inspected.94 friend llvm::raw_ostream &operator<<(llvm::raw_ostream &OS,95 const Iterator &Iterator) {96 return Iterator.dump(OS);97 }98 99 /// Inspect iterator type, used internally for optimizing query trees.100 enum class Kind { And, Or, True, False, Other };101 Kind kind() const { return MyKind; }102 103protected:104 Iterator(Kind MyKind = Kind::Other) : MyKind(MyKind) {}105 106private:107 virtual llvm::raw_ostream &dump(llvm::raw_ostream &OS) const = 0;108 Kind MyKind;109};110 111/// Advances the iterator until it is exhausted. Returns pairs of document IDs112/// with the corresponding boosting score.113///114/// Boosting can be seen as a compromise between retrieving too many items and115/// calculating finals score for each of them (which might be very expensive)116/// and not retrieving enough items so that items with very high final score117/// would not be processed. Boosting score is a computationally efficient way118/// to acquire preliminary scores of requested items.119std::vector<std::pair<DocID, float>> consume(Iterator &It);120 121namespace detail {122// Variadic template machinery.123inline void populateChildren(std::vector<std::unique_ptr<Iterator>> &) {}124template <typename... TailT>125void populateChildren(std::vector<std::unique_ptr<Iterator>> &Children,126 std::unique_ptr<Iterator> Head, TailT... Tail) {127 Children.push_back(std::move(Head));128 populateChildren(Children, std::move(Tail)...);129}130} // namespace detail131 132// A corpus is a set of documents, and a factory for iterators over them.133class Corpus {134 DocID Size;135 136public:137 explicit Corpus(DocID Size) : Size(Size) {}138 139 /// Returns AND Iterator which performs the intersection of the PostingLists140 /// of its children.141 ///142 /// consume(): AND Iterator returns the product of Childrens' boosting143 /// scores.144 std::unique_ptr<Iterator>145 intersect(std::vector<std::unique_ptr<Iterator>> Children) const;146 147 /// Returns OR Iterator which performs the union of the PostingLists of its148 /// children.149 ///150 /// consume(): OR Iterator returns the highest boost value among children151 /// containing the requested item.152 std::unique_ptr<Iterator>153 unionOf(std::vector<std::unique_ptr<Iterator>> Children) const;154 155 /// Returns TRUE Iterator which iterates over "virtual" PostingList156 /// containing all items in range [0, Size) in an efficient manner.157 std::unique_ptr<Iterator> all() const;158 159 /// Returns FALSE Iterator which iterates over no documents.160 std::unique_ptr<Iterator> none() const;161 162 /// Returns BOOST iterator which multiplies the score of each item by given163 /// factor. Boosting can be used as a computationally inexpensive filtering.164 /// Users can return significantly more items using consumeAndBoost() and165 /// then trim Top K using retrieval score.166 std::unique_ptr<Iterator> boost(std::unique_ptr<Iterator> Child,167 float Factor) const;168 169 /// Returns LIMIT iterator, which yields up to N elements of its child170 /// iterator. Elements only count towards the limit if they are part of the171 /// final result set. Therefore the following iterator (AND (2) (LIMIT (1 2)172 /// 1)) yields (2), not ().173 std::unique_ptr<Iterator> limit(std::unique_ptr<Iterator> Child,174 size_t Limit) const;175 176 /// This allows intersect(create(...), create(...)) syntax.177 template <typename... Args>178 std::unique_ptr<Iterator> intersect(Args... args) const {179 std::vector<std::unique_ptr<Iterator>> Children;180 detail::populateChildren(Children, std::forward<Args>(args)...);181 return intersect(std::move(Children));182 }183 184 /// This allows unionOf(create(...), create(...)) syntax.185 template <typename... Args>186 std::unique_ptr<Iterator> unionOf(Args... args) const {187 std::vector<std::unique_ptr<Iterator>> Children;188 detail::populateChildren(Children, std::forward<Args>(args)...);189 return unionOf(std::move(Children));190 }191};192 193} // namespace dex194} // namespace clangd195} // namespace clang196 197#endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_DEX_ITERATOR_H198