[clangd] Allow consuming limited number of items

[kbobyrev]

Summary

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.

[ioeric]

Could you add test? ;)

clang-tools-extra/clangd/index/dex/Iterator.cpp

223

Where do we increment Retrieved?

223

nit: s/Retreived/Retrieved/

clang-tools-extra/clangd/index/dex/Iterator.h

108

nit: I think Size of the returned ... is just repeating the first two sentences. Maybe drop?

[kbobyrev]

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

[kbobyrev]

Fix the implementation and add test coverage.

[ioeric]

clang-tools-extra/unittests/clangd/DexIndexTests.cpp

252 ↗

(On Diff #159959)

nit: maybe use the default parameter here?

260 ↗

(On Diff #159959)

The AND iterator case doesn't seem to add more coverage. Maybe drop?

clang-tools-extra/clangd/index/dex/Iterator.h

friend llvm::raw_ostream &operator<<(llvm::raw_ostream &OS,
                                        const Iterator &Iterator) {
     return Iterator.dump(OS);
   }
 
 private:
   virtual llvm::raw_ostream &dump(llvm::raw_ostream &OS) const = 0;
 };
 
-/// Exhausts given iterator and returns all processed DocIDs. The result
-/// contains sorted DocumentIDs.
-std::vector<DocID> consume(Iterator &It);
+/// Advances the iterator until it is either exhausted or the number of
+/// requested items is reached. The result contains sorted DocumentIDs. Size of
+/// the returned vector is min(Limit, IteratorSize) where IteratorSize stands
+/// for the number of elements obtained before the iterator is exhausted.
+std::vector<DocID> consume(Iterator &It,
+                           size_t Limit = std::numeric_limits<size_t>::max());
 
 /// Returns a document iterator over given PostingList.
 std::unique_ptr<Iterator> create(PostingListRef Documents);
 
 /// Returns AND Iterator which performs the intersection of the PostingLists of
 /// its children.
 std::unique_ptr<Iterator>
 createAnd(std::vector<std::unique_ptr<Iterator>> Children);

clang-tools-extra/clangd/index/dex/Iterator.cpp

 
 private:
   // FIXME(kbobyrev): Would storing Children in min-heap be faster?
   std::vector<std::unique_ptr<Iterator>> Children;
 };
 
 } // end namespace
 
-std::vector<DocID> consume(Iterator &It) {
+std::vector<DocID> consume(Iterator &It, size_t Limit) {
   std::vector<DocID> Result;
-  for (; !It.reachedEnd(); It.advance())
+  for (size_t Retreived = 0; !It.reachedEnd() && Retreived < Limit;
+       It.advance())
     Result.push_back(It.peek());
   return Result;
 }
 
 std::unique_ptr<Iterator> create(PostingListRef Documents) {
   return llvm::make_unique<DocumentIterator>(Documents);
 }