[clangd] Add line and column number to the index symbol.

[hokein]

Summary

LSP is using Line & column as symbol position, clangd needs to transfer file
offset to Line & column when sending results back to LSP client, which is a high
cost, especially for finding workspace symbol -- we have to read the file
content from disk (if it isn't loaded in memory).

Saving these information in the index will make the clangd life eaiser.

[sammccall]

clangd/index/Index.h

27

There are 4 of these per symbol, if we can keep line + character to 32 bits we save 16 bytes per symbol.

That looks like it might still be ~10% of non-string size. WDYT?
(12 bits for column and 20 bits for line seems like a reasonable guess)

28

These comments seem pretty obvious, I think
int Line=0, Character=0 // zero-based is enough, but up to you.

I would like a comment explaining why we're storing these redundant representations though.
e.g. // Storing Line/Character allows us to build LSP responses without reading the file content.

32

Column?

LSP calls this "character" but this is nonstandard and I find it very confusing with offset.

39

I don't think we should remove them, we'll just have the same problem in reverse.
Could position have have line/col/offset, and have Position Start, End?

clangd/index/SymbolCollector.cpp

205

I don't think this works, tokens can be split across lines.

I believe you want to compute NameLoc.locWithOffset(TokenLength) and then decompose that into line/col.
(getLocForEndOfToken, confusingly, is different)

[hokein]

Address review comments.

[hokein]

clangd/index/Index.h

39

As discussed offline, we decide to remove them as we don't have real use case of them (we could add them back when needed).
I removed all the references of them in clangd. And remove these fields in a separate patch.

clangd/index/SymbolCollector.cpp

205

Good catch. Done, added a test.

[sammccall]

clangd/index/Index.h

27

after some offline discussion, I no longer think this is a good idea.
We should strive to keep memory usage reasonable with the current naive index implementation, but "giant vector of Symbol structs in memory" isn't a case to micro-optimize for in the long run.

32

We should document what this is an offset into: bytes, utf-16 code units, or unicode codepoints. (Or even grid offsets - glyphs and doublewidth are a thing)

Given that we intend to send it over LSP without reading the source, only utf-16 code units is really correct. Unicode codepoints is "nicer" and will give correct results in the BMP, while bytes will be correct for ASCII only.

I'd vote for making this utf-16 code units.

It's OK if the code populating it doesn't get this right (confuses bytes and code units) but add a fixme.

39

After offline discussion: we don't actually plan to do math on these ever, we just send them to LSP clients.
So removing sounds fine. We can add later if there are clear use cases.

45

Not sure about the abbreviation - maybe just start/end? Since offsets are going away.

[sammccall]

LG, with

• consider reverting the bitpacking stuff
• comment about utf-16
• clang-format :)

clangd/index/SymbolCollector.cpp

202

nit: SourceManager is 1-based (or returns 1-based data here).
SourceLocation uses 0-based offsets, not 1-based line/column.

[hokein]

Update the patch, address remaining issues.

clangd/index/Index.h

32

Done. Added FIXME.

[MaskRay]

clangd/index/Index.h

32

I'd vote for Unicode code points.

I haven't looked into this closely. But UTF-8 vs UTF-16 vs Unicode code points should not be a big issue here. Unless you use emojis or some uncommon characters, the usage of UTF-16 code units in LSP does not have a lot of harm.

//  😹😹👻 anything weird hidden in line comments can be ignored because they don't affect offset calculation

And Microsoft might change the spec one day https://github.com/Microsoft/language-server-protocol/issues/376

[MaskRay]

Just my 2 cents. Calculation of line/character for each occurrence may not take a lot of computation. cquery/ccls computes the

clangd/index/Index.h

39

Yes. StartOffset and EndOffset should be removed some day. a line->offset mapping should be sufficient for documents that have stale index.

[hokein]

clangd/index/Index.h

32

Yeah, It'd be nicer if LSP spec is changed to use UTF-8. The Column is intended to align with Character of LSP's Position, let's keep it as it is at the moment.

clangd/index/Index.h

 #include "llvm/ADT/StringExtras.h"
 #include <array>
 #include <string>
 
 namespace clang {
 namespace clangd {
 
 struct SymbolLocation {
+  // Specify a position (Line, Column) of symbol. Using Line/Column allows us to
+  // build LSP responses without reading the file content.
+  struct Position {
+    uint32_t Line = 0; // 0-based
+    // Using UTF-16 code units.
+    uint32_t Column = 0; // 0-based
+  };
+
   // The URI of the source file where a symbol occurs.
   llvm::StringRef FileURI;
   // The 0-based offsets of the symbol from the beginning of the source file,
   // using half-open range, [StartOffset, EndOffset).
+  // DO NOT use these fields, as they will be removed immediately.
+  // FIXME(hokein): remove these fields in favor of Position.
   unsigned StartOffset = 0;
   unsigned EndOffset = 0;
 
+  /// The symbol range, using half-open range [Start, End).
+  Position Start;
+  Position End;
+
   operator bool() const { return !FileURI.empty(); }
 };
 llvm::raw_ostream &operator<<(llvm::raw_ostream &, const SymbolLocation &);
 
 // The class identifies a particular C++ symbol (class, function, method, etc).
 //
 // As USRs (Unified Symbol Resolution) could be large, especially for functions
 // with long type arguments, SymbolID is using 160-bits SHA1(USR) values to

clangd/index/Index.cpp

 
 namespace clang {
 namespace clangd {
 using namespace llvm;
 
 raw_ostream &operator<<(raw_ostream &OS, const SymbolLocation &L) {
   if (!L)
     return OS << "(none)";
-  return OS << L.FileURI << "[" << L.StartOffset << "-" << L.EndOffset << ")";
+  return OS << L.FileURI << "[" << L.Start.Line << ":" << L.Start.Column << "-"
+            << L.End.Line << ":" << L.End.Column << ")";
 }
 
 SymbolID::SymbolID(StringRef USR)
     : HashValue(SHA1::hash(arrayRefFromStringRef(USR))) {}
 
 raw_ostream &operator<<(raw_ostream &OS, const SymbolID &ID) {
   OS << toHex(toStringRef(ID.HashValue));
   return OS;

clangd/index/SymbolCollector.cpp

llvm::Optional<SymbolLocation> getSymbolLocation(
     const clang::LangOptions &LangOpts, std::string &FileURIStorage) {
   SourceLocation NameLoc = findNameLoc(&D);
   auto U = toURI(SM, SM.getFilename(NameLoc), Opts);
   if (!U)
     return llvm::None;
   FileURIStorage = std::move(*U);
   SymbolLocation Result;
   Result.FileURI = FileURIStorage;
-  Result.StartOffset = SM.getFileOffset(NameLoc);
-  Result.EndOffset = Result.StartOffset + clang::Lexer::MeasureTokenLength(
-                                              NameLoc, SM, LangOpts);
+  auto TokenLength = clang::Lexer::MeasureTokenLength(NameLoc, SM, LangOpts);
+
+  auto CreatePosition = [&SM](SourceLocation Loc) {
+    auto FileIdAndOffset = SM.getDecomposedLoc(Loc);
+    auto FileId = FileIdAndOffset.first;
+    auto Offset = FileIdAndOffset.second;
+    SymbolLocation::Position Pos;
+    // Position is 0-based while SourceManager is 1-based.
+    Pos.Line = SM.getLineNumber(FileId, Offset) - 1;
+    // FIXME: Use UTF-16 code units, not UTF-8 bytes.
+    Pos.Column = SM.getColumnNumber(FileId, Offset) - 1;
+    return Pos;
+  };
+
+  Result.Start = CreatePosition(NameLoc);
+  auto EndLoc = NameLoc.getLocWithOffset(TokenLength);
+  Result.End = CreatePosition(EndLoc);
+
   return std::move(Result);
 }
 
 // Checks whether \p ND is a definition of a TagDecl (class/struct/enum/union)
 // in a header file, in which case clangd would prefer to use ND as a canonical
 // declaration.
 // FIXME: handle symbol types that are not TagDecl (e.g. functions), if using
 // the first seen declaration as canonical declaration is not a good enough

clangd/index/SymbolYAML.cpp

SymbolID denormalize(IO&) {
     SymbolID ID;
     HexString >> ID;
     return ID;
   }
 
   std::string HexString;
 };
 
+template <> struct MappingTraits<SymbolLocation::Position> {
+  static void mapping(IO &IO, SymbolLocation::Position &Value) {
+    IO.mapRequired("Line", Value.Line);
+    IO.mapRequired("Column", Value.Column);
+  }
+};
+
 template <> struct MappingTraits<SymbolLocation> {
   static void mapping(IO &IO, SymbolLocation &Value) {
-    IO.mapRequired("StartOffset", Value.StartOffset);
-    IO.mapRequired("EndOffset", Value.EndOffset);
     IO.mapRequired("FileURI", Value.FileURI);
+    IO.mapRequired("Start", Value.Start);
+    IO.mapRequired("End", Value.End);
   }
 };
 
 template <> struct MappingTraits<SymbolInfo> {
   static void mapping(IO &io, SymbolInfo &SymInfo) {
     // FIXME: expose other fields?
     io.mapRequired("Kind", SymInfo.Kind);
     io.mapRequired("Lang", SymInfo.Lang);

unittests/clangd/Annotations.h

public:
   std::vector<Position> points(llvm::StringRef Name = "") const;
 
   // Returns the location of the range marked by [[ ]] (or $name[[ ]]).
   // Crashes if there isn't exactly one.
   Range range(llvm::StringRef Name = "") const;
   // Returns the location of all ranges marked by [[ ]] (or $name[[ ]]).
   std::vector<Range> ranges(llvm::StringRef Name = "") const;
 
-  // The same to `range` method, but returns range in offsets [start, end).
-  std::pair<std::size_t, std::size_t>
-  offsetRange(llvm::StringRef Name = "") const;
-
 private:
   std::string Code;
   llvm::StringMap<llvm::SmallVector<Position, 1>> Points;
   llvm::StringMap<llvm::SmallVector<Range, 1>> Ranges;
 };
 
 } // namespace clangd
 } // namespace clang
 #endif

unittests/clangd/Annotations.cpp

require(I != Ranges.end() && I->getValue().size() == 1,
           "expected exactly one range", Code);
   return I->getValue()[0];
 }
 std::vector<Range> Annotations::ranges(llvm::StringRef Name) const {
   auto R = Ranges.lookup(Name);
   return {R.begin(), R.end()};
 }
 
-std::pair<std::size_t, std::size_t>
-Annotations::offsetRange(llvm::StringRef Name) const {
-  auto R = range(Name);
-  llvm::Expected<size_t> Start = positionToOffset(Code, R.start);
-  llvm::Expected<size_t> End = positionToOffset(Code, R.end);
-  assert(Start);
-  assert(End);
-  return {*Start, *End};
-}
-
 } // namespace clangd
 } // namespace clang

unittests/clangd/SymbolCollectorTests.cpp

MATCHER_P(Snippet, S, "") {
   return arg.CompletionSnippetInsertText == S;
 }
 MATCHER_P(QName, Name, "") { return (arg.Scope + arg.Name).str() == Name; }
 MATCHER_P(DeclURI, P, "") { return arg.CanonicalDeclaration.FileURI == P; }
 MATCHER_P(DefURI, P, "") { return arg.Definition.FileURI == P; }
 MATCHER_P(IncludeHeader, P, "") {
   return arg.Detail && arg.Detail->IncludeHeader == P;
 }
-MATCHER_P(DeclRange, Offsets, "") {
-  return arg.CanonicalDeclaration.StartOffset == Offsets.first &&
-      arg.CanonicalDeclaration.EndOffset == Offsets.second;
-}
-MATCHER_P(DefRange, Offsets, "") {
-  return arg.Definition.StartOffset == Offsets.first &&
-         arg.Definition.EndOffset == Offsets.second;
+MATCHER_P(DeclRange, Pos, "") {
+  return std::tie(arg.CanonicalDeclaration.Start.Line,
+                  arg.CanonicalDeclaration.Start.Column,
+                  arg.CanonicalDeclaration.End.Line,
+                  arg.CanonicalDeclaration.End.Column) ==
+         std::tie(Pos.start.line, Pos.start.character, Pos.end.line,
+                  Pos.end.character);
+}
+MATCHER_P(DefRange, Pos, "") {
+  return std::tie(arg.Definition.Start.Line,
+                  arg.Definition.Start.Column, arg.Definition.End.Line,
+                  arg.Definition.End.Column) ==
+         std::tie(Pos.start.line, Pos.start.character, Pos.end.line,
+                  Pos.end.character);
 }
 MATCHER_P(Refs, R, "") { return int(arg.References) == R; }
 
 namespace clang {
 namespace clangd {
 
 namespace {
 class SymbolIndexActionFactory : public tooling::FrontendActionFactory {
Annotations Header(R"(
     // Template is indexed, specialization and instantiation is not.
     template <class T> struct [[Tmpl]] {T x = 0;};
     template <> struct Tmpl<int> {};
     extern template struct Tmpl<float>;
     template struct Tmpl<double>;
   )");
   runSymbolCollector(Header.code(), /*Main=*/"");
   EXPECT_THAT(Symbols, UnorderedElementsAreArray({AllOf(
-                           QName("Tmpl"), DeclRange(Header.offsetRange()))}));
+                           QName("Tmpl"), DeclRange(Header.range()))}));
 }
 
 TEST_F(SymbolCollectorTest, Locations) {
   Annotations Header(R"cpp(
     // Declared in header, defined in main.
     extern int $xdecl[[X]];
     class $clsdecl[[Cls]];
     void $printdecl[[print]]();
 
     // Declared in header, defined nowhere.
     extern int $zdecl[[Z]];
+
+    void $foodecl[[fo\
+o]]();
   )cpp");
   Annotations Main(R"cpp(
     int $xdef[[X]] = 42;
     class $clsdef[[Cls]] {};
     void $printdef[[print]]() {}
 
     // Declared/defined in main only.
     int Y;
   )cpp");
   runSymbolCollector(Header.code(), Main.code());
   EXPECT_THAT(
       Symbols,
       UnorderedElementsAre(
-          AllOf(QName("X"), DeclRange(Header.offsetRange("xdecl")),
-                DefRange(Main.offsetRange("xdef"))),
-          AllOf(QName("Cls"), DeclRange(Header.offsetRange("clsdecl")),
-                DefRange(Main.offsetRange("clsdef"))),
-          AllOf(QName("print"), DeclRange(Header.offsetRange("printdecl")),
-                DefRange(Main.offsetRange("printdef"))),
-          AllOf(QName("Z"), DeclRange(Header.offsetRange("zdecl")))));
+          AllOf(QName("X"), DeclRange(Header.range("xdecl")),
+                DefRange(Main.range("xdef"))),
+          AllOf(QName("Cls"), DeclRange(Header.range("clsdecl")),
+                DefRange(Main.range("clsdef"))),
+          AllOf(QName("print"), DeclRange(Header.range("printdecl")),
+                DefRange(Main.range("printdef"))),
+          AllOf(QName("Z"), DeclRange(Header.range("zdecl"))),
+          AllOf(QName("foo"), DeclRange(Header.range("foodecl")))
+          ));
 }
 
 TEST_F(SymbolCollectorTest, References) {
   const std::string Header = R"(
     class W;
     class X {};
     class Y;
     class Z {}; // not used anywhere
Annotations Header(R"(
 
     FF2();
   )");
 
   runSymbolCollector(Header.code(), /*Main=*/"");
   EXPECT_THAT(
       Symbols,
       UnorderedElementsAre(
-          AllOf(QName("abc_Test"), DeclRange(Header.offsetRange("expansion")),
+          AllOf(QName("abc_Test"), DeclRange(Header.range("expansion")),
                 DeclURI(TestHeaderURI)),
-          AllOf(QName("Test"), DeclRange(Header.offsetRange("spelling")),
+          AllOf(QName("Test"), DeclRange(Header.range("spelling")),
                 DeclURI(TestHeaderURI))));
 }
 
 TEST_F(SymbolCollectorTest, SymbolFormedByCLI) {
   Annotations Header(R"(
     #ifdef NAME
     class $expansion[[NAME]] {};
     #endif
   )");
 
   runSymbolCollector(Header.code(), /*Main=*/"",
                      /*ExtraArgs=*/{"-DNAME=name"});
   EXPECT_THAT(Symbols,
               UnorderedElementsAre(AllOf(
-                  QName("name"), DeclRange(Header.offsetRange("expansion")),
+                  QName("name"),
+                  DeclRange(Header.range("expansion")),
                   DeclURI(TestHeaderURI))));
 }
 
 TEST_F(SymbolCollectorTest, IgnoreSymbolsInMainFile) {
   const std::string Header = R"(
     class Foo {};
     void f1();
     inline void f2() {}

 ---
 ID: 057557CEBF6E6B2DD437FBF60CC58F352D1DF856
 Name:   'Foo1'
 Scope:   'clang::'
 SymInfo:
   Kind:            Function
   Lang:            Cpp
 CanonicalDeclaration:
-  StartOffset:     0
-  EndOffset:       1
   FileURI:        file:///path/foo.h
+  Start:
+    Line: 1
+    Column: 0
+  End:
+    Line: 1
+    Column: 1
 CompletionLabel:    'Foo1-label'
 CompletionFilterText:    'filter'
 CompletionPlainInsertText:    'plain'
 Detail:
   Documentation:    'Foo doc'
   CompletionDetail:    'int'
 ...
 )";
   const std::string YAML2 = R"(
 ---
 ID: 057557CEBF6E6B2DD437FBF60CC58F352D1DF858
 Name:   'Foo2'
 Scope:   'clang::'
 SymInfo:
   Kind:            Function
   Lang:            Cpp
 CanonicalDeclaration:
-  StartOffset:     10
-  EndOffset:       12
   FileURI:        file:///path/bar.h
+  Start:
+    Line: 1
+    Column: 0
+  End:
+    Line: 1
+    Column: 1
 CompletionLabel:    'Foo2-label'
 CompletionFilterText:    'filter'
 CompletionPlainInsertText:    'plain'
 CompletionSnippetInsertText:    'snippet'
 ...
 )";
 
   auto Symbols1 = SymbolsFromYAML(YAML1);
+
   EXPECT_THAT(Symbols1,
               UnorderedElementsAre(AllOf(
                   QName("clang::Foo1"), Labeled("Foo1-label"), Doc("Foo doc"),
                   Detail("int"), DeclURI("file:///path/foo.h"))));
   auto Symbols2 = SymbolsFromYAML(YAML2);
   EXPECT_THAT(Symbols2, UnorderedElementsAre(AllOf(
                             QName("clang::Foo2"), Labeled("Foo2-label"),
                             Not(HasDetail()), DeclURI("file:///path/bar.h"))));
Annotations Header(R"(
     class $cdecl[[C]] {};
     struct $sdecl[[S]] {};
     union $udecl[[U]] {int x; bool y;};
   )");
   runSymbolCollector(Header.code(), /*Main=*/"");
   EXPECT_THAT(Symbols,
               UnorderedElementsAre(
                   AllOf(QName("C"), DeclURI(TestHeaderURI),
-                        DeclRange(Header.offsetRange("cdecl")),
+                        DeclRange(Header.range("cdecl")),
                         IncludeHeader(TestHeaderURI), DefURI(TestHeaderURI),
-                        DefRange(Header.offsetRange("cdecl"))),
+                        DefRange(Header.range("cdecl"))),
                   AllOf(QName("S"), DeclURI(TestHeaderURI),
-                        DeclRange(Header.offsetRange("sdecl")),
+                        DeclRange(Header.range("sdecl")),
                         IncludeHeader(TestHeaderURI), DefURI(TestHeaderURI),
-                        DefRange(Header.offsetRange("sdecl"))),
+                        DefRange(Header.range("sdecl"))),
                   AllOf(QName("U"), DeclURI(TestHeaderURI),
-                        DeclRange(Header.offsetRange("udecl")),
+                        DeclRange(Header.range("udecl")),
                         IncludeHeader(TestHeaderURI), DefURI(TestHeaderURI),
-                        DefRange(Header.offsetRange("udecl")))));
+                        DefRange(Header.range("udecl")))));
 }
 
 TEST_F(SymbolCollectorTest, ClassForwardDeclarationIsCanonical) {
   CollectorOpts.CollectIncludePath = true;
   runSymbolCollector(/*Header=*/"class X;", /*Main=*/"class X {};");
   EXPECT_THAT(Symbols, UnorderedElementsAre(AllOf(
                            QName("X"), DeclURI(TestHeaderURI),
                            IncludeHeader(TestHeaderURI), DefURI(TestFileURI))));
 }
 
 } // namespace
 } // namespace clangd
 } // namespace clang