LCOV - code coverage report
Current view: top level - clang/tools/extra/clangd/index - Index.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 0 18 0.0 %
Date: 2018-06-17 00:07:59 Functions: 0 9 0.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===--- Index.h ------------------------------------------------*- C++-*-===//
       2             : //
       3             : //                     The LLVM Compiler Infrastructure
       4             : //
       5             : // This file is distributed under the University of Illinois Open Source
       6             : // License. See LICENSE.TXT for details.
       7             : //
       8             : //===---------------------------------------------------------------------===//
       9             : 
      10             : #ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_INDEX_H
      11             : #define LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_INDEX_H
      12             : 
      13             : #include "clang/Index/IndexSymbol.h"
      14             : #include "clang/Lex/Lexer.h"
      15             : #include "llvm/ADT/DenseMap.h"
      16             : #include "llvm/ADT/DenseSet.h"
      17             : #include "llvm/ADT/Hashing.h"
      18             : #include "llvm/ADT/Optional.h"
      19             : #include "llvm/ADT/StringExtras.h"
      20             : #include <array>
      21             : #include <string>
      22             : 
      23             : namespace clang {
      24             : namespace clangd {
      25             : 
      26             : struct SymbolLocation {
      27             :   // Specify a position (Line, Column) of symbol. Using Line/Column allows us to
      28             :   // build LSP responses without reading the file content.
      29           0 :   struct Position {
      30             :     uint32_t Line = 0; // 0-based
      31             :     // Using UTF-16 code units.
      32             :     uint32_t Column = 0; // 0-based
      33             :   };
      34             : 
      35             :   // The URI of the source file where a symbol occurs.
      36             :   llvm::StringRef FileURI;
      37             : 
      38             :   /// The symbol range, using half-open range [Start, End).
      39             :   Position Start;
      40             :   Position End;
      41             : 
      42             :   operator bool() const { return !FileURI.empty(); }
      43             : };
      44             : llvm::raw_ostream &operator<<(llvm::raw_ostream &, const SymbolLocation &);
      45             : 
      46             : // The class identifies a particular C++ symbol (class, function, method, etc).
      47             : //
      48             : // As USRs (Unified Symbol Resolution) could be large, especially for functions
      49             : // with long type arguments, SymbolID is using 160-bits SHA1(USR) values to
      50             : // guarantee the uniqueness of symbols while using a relatively small amount of
      51             : // memory (vs storing USRs directly).
      52             : //
      53             : // SymbolID can be used as key in the symbol indexes to lookup the symbol.
      54             : class SymbolID {
      55             : public:
      56             :   SymbolID() = default;
      57             :   explicit SymbolID(llvm::StringRef USR);
      58             : 
      59             :   bool operator==(const SymbolID &Sym) const {
      60             :     return HashValue == Sym.HashValue;
      61             :   }
      62             :   bool operator<(const SymbolID &Sym) const {
      63             :     return HashValue < Sym.HashValue;
      64             :   }
      65             : 
      66             :   // Returns a 40-bytes hex encoded string.
      67             :   std::string str() const;
      68             : 
      69             : private:
      70             :   static constexpr unsigned HashByteLength = 20;
      71             : 
      72             :   friend llvm::hash_code hash_value(const SymbolID &ID) {
      73             :     // We already have a good hash, just return the first bytes.
      74             :     static_assert(sizeof(size_t) <= HashByteLength, "size_t longer than SHA1!");
      75             :     size_t Result;
      76           0 :     memcpy(&Result, ID.HashValue.data(), sizeof(size_t));
      77             :     return llvm::hash_code(Result);
      78             :   }
      79             :   friend llvm::raw_ostream &operator<<(llvm::raw_ostream &OS,
      80             :                                        const SymbolID &ID);
      81             :   friend void operator>>(llvm::StringRef Str, SymbolID &ID);
      82             : 
      83             :   std::array<uint8_t, HashByteLength> HashValue;
      84             : };
      85             : 
      86             : // Write SymbolID into the given stream. SymbolID is encoded as a 40-bytes
      87             : // hex string.
      88             : llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const SymbolID &ID);
      89             : 
      90             : // Construct SymbolID from a hex string.
      91             : // The HexStr is required to be a 40-bytes hex string, which is encoded from the
      92             : // "<<" operator.
      93             : void operator>>(llvm::StringRef HexStr, SymbolID &ID);
      94             : 
      95             : } // namespace clangd
      96             : } // namespace clang
      97             : namespace llvm {
      98             : // Support SymbolIDs as DenseMap keys.
      99             : template <> struct DenseMapInfo<clang::clangd::SymbolID> {
     100           0 :   static inline clang::clangd::SymbolID getEmptyKey() {
     101           0 :     static clang::clangd::SymbolID EmptyKey("EMPTYKEY");
     102           0 :     return EmptyKey;
     103             :   }
     104           0 :   static inline clang::clangd::SymbolID getTombstoneKey() {
     105           0 :     static clang::clangd::SymbolID TombstoneKey("TOMBSTONEKEY");
     106           0 :     return TombstoneKey;
     107             :   }
     108             :   static unsigned getHashValue(const clang::clangd::SymbolID &Sym) {
     109           0 :     return hash_value(Sym);
     110             :   }
     111             :   static bool isEqual(const clang::clangd::SymbolID &LHS,
     112             :                       const clang::clangd::SymbolID &RHS) {
     113             :     return LHS == RHS;
     114             :   }
     115             : };
     116             : } // namespace llvm
     117             : namespace clang {
     118             : namespace clangd {
     119             : 
     120             : // The class presents a C++ symbol, e.g. class, function.
     121             : //
     122             : // WARNING: Symbols do not own much of their underlying data - typically strings
     123             : // are owned by a SymbolSlab. They should be treated as non-owning references.
     124             : // Copies are shallow.
     125             : // When adding new unowned data fields to Symbol, remember to update:
     126             : //   - SymbolSlab::Builder in Index.cpp, to copy them to the slab's storage.
     127             : //   - mergeSymbol in Merge.cpp, to properly combine two Symbols.
     128           0 : struct Symbol {
     129             :   // The ID of the symbol.
     130             :   SymbolID ID;
     131             :   // The symbol information, like symbol kind.
     132             :   index::SymbolInfo SymInfo;
     133             :   // The unqualified name of the symbol, e.g. "bar" (for ns::bar).
     134             :   llvm::StringRef Name;
     135             :   // The containing namespace. e.g. "" (global), "ns::" (top-level namespace).
     136             :   llvm::StringRef Scope;
     137             :   // The location of the symbol's definition, if one was found.
     138             :   // This just covers the symbol name (e.g. without class/function body).
     139             :   SymbolLocation Definition;
     140             :   // The location of the preferred declaration of the symbol.
     141             :   // This just covers the symbol name.
     142             :   // This may be the same as Definition.
     143             :   //
     144             :   // A C++ symbol may have multiple declarations, and we pick one to prefer.
     145             :   //   * For classes, the canonical declaration should be the definition.
     146             :   //   * For non-inline functions, the canonical declaration typically appears
     147             :   //     in the ".h" file corresponding to the definition.
     148             :   SymbolLocation CanonicalDeclaration;
     149             :   // The number of translation units that reference this symbol from their main
     150             :   // file. This number is only meaningful if aggregated in an index.
     151             :   unsigned References = 0;
     152             :   /// Whether or not this symbol is meant to be used for the code completion.
     153             :   /// See also isIndexedForCodeCompletion().
     154             :   bool IsIndexedForCodeCompletion = false;
     155             :   /// A brief description of the symbol that can be displayed in the completion
     156             :   /// candidate list. For example, "Foo(X x, Y y) const" is a label for a
     157             :   /// function.
     158             :   llvm::StringRef CompletionLabel;
     159             :   /// The piece of text that the user is expected to type to match the
     160             :   /// code-completion string, typically a keyword or the name of a declarator or
     161             :   /// macro.
     162             :   llvm::StringRef CompletionFilterText;
     163             :   /// What to insert when completing this symbol (plain text version).
     164             :   llvm::StringRef CompletionPlainInsertText;
     165             :   /// What to insert when completing this symbol (snippet version). This is
     166             :   /// empty if it is the same as the plain insert text above.
     167             :   llvm::StringRef CompletionSnippetInsertText;
     168             : 
     169             :   /// Optional symbol details that are not required to be set. For example, an
     170             :   /// index fuzzy match can return a large number of symbol candidates, and it
     171             :   /// is preferable to send only core symbol information in the batched results
     172             :   /// and have clients resolve full symbol information for a specific candidate
     173             :   /// if needed.
     174             :   struct Details {
     175             :     /// Documentation including comment for the symbol declaration.
     176             :     llvm::StringRef Documentation;
     177             :     /// This is what goes into the LSP detail field in a completion item. For
     178             :     /// example, the result type of a function.
     179             :     llvm::StringRef CompletionDetail;
     180             :     /// This can be either a URI of the header to be #include'd for this symbol,
     181             :     /// or a literal header quoted with <> or "" that is suitable to be included
     182             :     /// directly. When this is a URI, the exact #include path needs to be
     183             :     /// calculated according to the URI scheme.
     184             :     ///
     185             :     /// This is a canonical include for the symbol and can be different from
     186             :     /// FileURI in the CanonicalDeclaration.
     187             :     llvm::StringRef IncludeHeader;
     188             :   };
     189             : 
     190             :   // Optional details of the symbol.
     191             :   const Details *Detail = nullptr;
     192             : 
     193             :   // FIXME: add all occurrences support.
     194             :   // FIXME: add extra fields for index scoring signals.
     195             : };
     196             : llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const Symbol &S);
     197             : 
     198             : // Computes query-independent quality score for a Symbol.
     199             : // This currently falls in the range [1, ln(#indexed documents)].
     200             : // FIXME: this should probably be split into symbol -> signals
     201             : //        and signals -> score, so it can be reused for Sema completions.
     202             : double quality(const Symbol &S);
     203             : 
     204             : // An immutable symbol container that stores a set of symbols.
     205             : // The container will maintain the lifetime of the symbols.
     206           0 : class SymbolSlab {
     207             : public:
     208             :   using const_iterator = std::vector<Symbol>::const_iterator;
     209             :   using iterator = const_iterator;
     210             : 
     211             :   SymbolSlab() = default;
     212             : 
     213           0 :   const_iterator begin() const { return Symbols.begin(); }
     214           0 :   const_iterator end() const { return Symbols.end(); }
     215             :   const_iterator find(const SymbolID &SymID) const;
     216             : 
     217             :   size_t size() const { return Symbols.size(); }
     218             :   // Estimates the total memory usage.
     219             :   size_t bytes() const {
     220             :     return sizeof(*this) + Arena.getTotalMemory() +
     221             :            Symbols.capacity() * sizeof(Symbol);
     222             :   }
     223             : 
     224             :   // SymbolSlab::Builder is a mutable container that can 'freeze' to SymbolSlab.
     225             :   // The frozen SymbolSlab will use less memory.
     226           0 :   class Builder {
     227             :   public:
     228             :     // Adds a symbol, overwriting any existing one with the same ID.
     229             :     // This is a deep copy: underlying strings will be owned by the slab.
     230             :     void insert(const Symbol &S);
     231             : 
     232             :     // Returns the symbol with an ID, if it exists. Valid until next insert().
     233           0 :     const Symbol *find(const SymbolID &ID) {
     234           0 :       auto I = SymbolIndex.find(ID);
     235           0 :       return I == SymbolIndex.end() ? nullptr : &Symbols[I->second];
     236             :     }
     237             : 
     238             :     // Consumes the builder to finalize the slab.
     239             :     SymbolSlab build() &&;
     240             : 
     241             :   private:
     242             :     llvm::BumpPtrAllocator Arena;
     243             :     // Intern table for strings. Contents are on the arena.
     244             :     llvm::DenseSet<llvm::StringRef> Strings;
     245             :     std::vector<Symbol> Symbols;
     246             :     // Values are indices into Symbols vector.
     247             :     llvm::DenseMap<SymbolID, size_t> SymbolIndex;
     248             :   };
     249             : 
     250             : private:
     251             :   SymbolSlab(llvm::BumpPtrAllocator Arena, std::vector<Symbol> Symbols)
     252             :       : Arena(std::move(Arena)), Symbols(std::move(Symbols)) {}
     253             : 
     254             :   llvm::BumpPtrAllocator Arena; // Owns Symbol data that the Symbols do not.
     255             :   std::vector<Symbol> Symbols;  // Sorted by SymbolID to allow lookup.
     256             : };
     257             : 
     258           0 : struct FuzzyFindRequest {
     259             :   /// \brief A query string for the fuzzy find. This is matched against symbols'
     260             :   /// un-qualified identifiers and should not contain qualifiers like "::".
     261             :   std::string Query;
     262             :   /// \brief If this is non-empty, symbols must be in at least one of the scopes
     263             :   /// (e.g. namespaces) excluding nested scopes. For example, if a scope "xyz::"
     264             :   /// is provided, the matched symbols must be defined in namespace xyz but not
     265             :   /// namespace xyz::abc.
     266             :   ///
     267             :   /// The global scope is "", a top level scope is "foo::", etc.
     268             :   std::vector<std::string> Scopes;
     269             :   /// \brief The number of top candidates to return. The index may choose to
     270             :   /// return more than this, e.g. if it doesn't know which candidates are best.
     271             :   size_t MaxCandidateCount = UINT_MAX;
     272             :   /// If set to true, only symbols for completion support will be considered.
     273             :   bool RestrictForCodeCompletion = false;
     274             :   /// Contextually relevant files (e.g. the file we're code-completing in).
     275             :   /// Paths should be absolute.
     276             :   std::vector<std::string> ProximityPaths;
     277             : };
     278             : 
     279             : struct LookupRequest {
     280             :   llvm::DenseSet<SymbolID> IDs;
     281             : };
     282             : 
     283             : /// \brief Interface for symbol indexes that can be used for searching or
     284             : /// matching symbols among a set of symbols based on names or unique IDs.
     285             : class SymbolIndex {
     286             : public:
     287             :   virtual ~SymbolIndex() = default;
     288             : 
     289             :   /// \brief Matches symbols in the index fuzzily and applies \p Callback on
     290             :   /// each matched symbol before returning.
     291             :   /// If returned Symbols are used outside Callback, they must be deep-copied!
     292             :   ///
     293             :   /// Returns true if there may be more results (limited by MaxCandidateCount).
     294             :   virtual bool
     295             :   fuzzyFind(const FuzzyFindRequest &Req,
     296             :             llvm::function_ref<void(const Symbol &)> Callback) const = 0;
     297             : 
     298             :   /// Looks up symbols with any of the given symbol IDs and applies \p Callback
     299             :   /// on each matched symbol.
     300             :   /// The returned symbol must be deep-copied if it's used outside Callback.
     301             :   virtual void
     302             :   lookup(const LookupRequest &Req,
     303             :          llvm::function_ref<void(const Symbol &)> Callback) const = 0;
     304             : 
     305             :   // FIXME: add interfaces for more index use cases:
     306             :   //  - getAllOccurrences(SymbolID);
     307             : };
     308             : 
     309             : } // namespace clangd
     310             : } // namespace clang
     311             : #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_INDEX_H

Generated by: LCOV version 1.13