[clang][Modules] Serialize decl to comment mapping to speed up code completion.

[jkorous]

Summary

The original motivation for this use-case was code-completion invoked via libclang.

Currently what we do is this:

1. We build a module and construct the the comment -> decl mapping.
2. We serialize the module to disk (without preserving the mapping).
3. We deserialize the module and reconstruct the mapping.

Construction of the mapping isn't exactly cheap - there are expensive SourceLocation decompositions and SourceLocation-based search. While we managed to turn the search into bisection in recent patch, preserving the information still seems a reasonable speed:module size tradeoff.

Original commit by Michael Spencer.

[Bigcheese]

clang/include/clang/Serialization/ASTBitCodes.h

794

COMMENTLESS

clang/lib/Serialization/ASTReader.cpp

9739–9752

I think these two cases need tests.

[sammccall]

+ilya because I know he's wrestled with these before, and because I'm OOO sick

[ilya-biryukov]

Overall this makes sense. If we choose to have this mapping in the ASTContext, serializing and deserializing it is probably a good idea (unless it means deserializing more decls eagerly...)

This patch mentions there is code currently that "reconstructs the mapping". Why not remove it in this patch? Where is it used if we actually serialize the mapping?
Do we have any measurements? How faster is this in particular use-cases? How bigger is the module now?

[ilya-biryukov]

clang/lib/Serialization/ASTReader.cpp

9733

GetDecl can cause deserialization of a corresponding decl.

Does that mean we are deserializing more decls solely because they had comments after this patch?
If not, why?

[gribozavr]

clang/include/clang/Serialization/ASTBitCodes.h

793

80 columns, please.

clang/lib/Serialization/ASTReader.cpp

9750

s/RedeclChainComments/CommentlessRedeclChains/

If this code passed tests as-is, it definitely needs more tests.

9750

I'm not certain that it is valid to serialize these caches, especially the CommentlessRedeclChains one. Here's why I think so. The result stored in CommentlessRedeclChains depends on all declarations that preceded LastCommentlessRedecl, that is, the cache relies on the fact that the redeclaration chain is fixed up to that point.

However, when we deserialize a module, that is not true -- I don't know how exactly redeclaration chains are merged, but since modules are compiled once and can be imported in arbitrary order, the redeclaration chain is definitely not fixed.

[bruno]

I'm curious to know if you measured the impact on the PCM size after this change (example: PCMs from building macOS public SDK)? For instance, PPD_SKIPPED_RANGES currently explodes for some specific inputs, just wonder what's the story here.

clang/lib/Serialization/ASTReader.cpp

9739–9752

+1

clang/include/clang/Serialization/ASTBitCodes.h

enum SubmoduleRecordTypes {
 
       /// Specifies the name of the module that will eventually
       /// re-export the entities in this module.
       SUBMODULE_EXPORT_AS = 17,
     };
 
     /// Record types used within a comments block.
     enum CommentRecordTypes {
-      COMMENTS_RAW_COMMENT = 0
+      COMMENTS_RAW_COMMENT = 0,
+
+      /// Maps from a decl to the comment that documents it.
+      COMMENTS_DECL_TO_COMMENT = 1,
+
+      /// Maps from a canonical decl to a redecl in the chain that has comment attached.
+      COMMENTS_CANON_DECL_TO_COMMENTED_DECL = 2,
+
+      /// For redecl chains with no comment attached maps from a canonical decl to the last redecl in the chain that has no comment attached.
+      COMMENTS_CANON_DECL_TO_LAST_COMMENLESS_REDECL = 3
     };
 
     /// \defgroup ASTAST AST file AST constants
     ///
     /// The constants in this group describe various components of the
     /// abstract syntax tree within an AST file.
     ///
     /// @{

clang/lib/Serialization/ASTReader.cpp

while (true) {
         RawComment::CommentKind Kind =
             (RawComment::CommentKind) Record[Idx++];
         bool IsTrailingComment = Record[Idx++];
         bool IsAlmostTrailingComment = Record[Idx++];
         Comments.push_back(new (Context) RawComment(
             SR, Kind, IsTrailingComment, IsAlmostTrailingComment));
         break;
       }
+      case COMMENTS_DECL_TO_COMMENT: {
+        unsigned Idx = 0;
+        const Decl *D = GetDecl(Record[Idx++]);
+        RawComment *RC = Comments[Record[Idx++]];
+        RC->setAttached();
+        Context.DeclRawComments[D] = RC;
+        break;
+      }
+      case COMMENTS_CANON_DECL_TO_COMMENTED_DECL : {
+        unsigned Idx = 0;
+        const Decl *CanonD = GetDecl(Record[Idx++]);
+        const Decl *CommentedD = GetDecl(Record[Idx++]);
+        Context.RedeclChainComments[CanonD] = CommentedD;
+        break;
+      }
+      case COMMENTS_CANON_DECL_TO_LAST_COMMENLESS_REDECL : {
+        unsigned Idx = 0;
+        const Decl *CanonD = GetDecl(Record[Idx++]);
+        const Decl *LastCommentlessRedecl = GetDecl(Record[Idx++]);
+        Context.RedeclChainComments[CanonD] = LastCommentlessRedecl;
+        break;
+      }
       }
     }
   NextCursor:
     llvm::DenseMap<FileID, std::map<unsigned, RawComment *>>
         FileToOffsetToComment;
     for (RawComment *C : Comments) {
       SourceLocation CommentLoc = C->getBeginLoc();
       if (CommentLoc.isValid()) {

clang/lib/Serialization/ASTWriter.cpp

void ASTWriter::WriteFileDeclIDsMap() {
   Stream.EmitRecordWithBlob(AbbrevCode, Record, bytes(FileGroupedDeclIDs));
 }
 
 void ASTWriter::WriteComments() {
   Stream.EnterSubblock(COMMENTS_BLOCK_ID, 3);
   auto _ = llvm::make_scope_exit([this] { Stream.ExitBlock(); });
   if (!PP->getPreprocessorOpts().WriteCommentListToPCH)
     return;
+
+  llvm::DenseMap<const RawComment *, uint32_t> RawCommentIndex;
+  uint32_t NextCommentIndex = 0;
+
   RecordData Record;
-  for (const auto &FO : Context->Comments.OrderedComments) {
-    for (const auto &OC : FO.second) {
+  for (const auto& FO : Context->Comments.OrderedComments) {
+    for (const auto& OC : FO.second) {
       const RawComment *I = OC.second;
       Record.clear();
       AddSourceRange(I->getSourceRange(), Record);
       Record.push_back(I->getKind());
       Record.push_back(I->isTrailingComment());
       Record.push_back(I->isAlmostTrailingComment());
       Stream.EmitRecord(COMMENTS_RAW_COMMENT, Record);
-    }
+      RawCommentIndex[I] = NextCommentIndex++;
+    }
+  }
+
+  for (const auto I : Context->DeclRawComments) {
+    Record.clear();
+    AddDeclRef(I.getFirst(), Record);
+    Record.push_back(RawCommentIndex[I.getSecond()]);
+    Stream.EmitRecord(COMMENTS_DECL_TO_COMMENT, Record);
+
+  for (const auto I : Context->RedeclChainComments) {
+    Record.clear();
+    AddDeclRef(I.getFirst(), Record);
+    AddDeclRef(I.getSecond(), Record);
+    Stream.EmitRecord(COMMENTS_CANON_DECL_TO_COMMENTED_DECL, Record);
+  }
+
+  for (const auto I : Context->CommentlessRedeclChains) {
+    Record.clear();
+    AddDeclRef(I.getFirst(), Record);
+    AddDeclRef(I.getSecond(), Record);
+    Stream.EmitRecord(COMMENTS_CANON_DECL_TO_LAST_COMMENLESS_REDECL, Record);
   }
 }
 
 //===----------------------------------------------------------------------===//
 // Global Method Pool and Selector Serialization
 //===----------------------------------------------------------------------===//
 
 namespace {

clang/test/Modules/Inputs/documentation.h

+/// This function is really cool
+void foo() {
+
+}
+
+/// But this one is at least 20% cooler
+void bar() {
+
+}

clang/test/Modules/Inputs/module.map

 module c_library [extern_c] { module inner { header "c-header.h" } }
 module cxx_library { header "cxx-header.h" requires cplusplus }
 module c_library_bad [extern_c] { header "c-header-bad.h" }
 module diamond_top { header "diamond_top.h" }
 module diamond_left { 
   header "diamond_left.h" 
   export diamond_top
 }
 module diamond_right { 
   header "diamond_right.h" 
   export diamond_top
 }
 module diamond_bottom { 
   header "diamond_bottom.h" 
   export *
 }
+module documentation { header "documentation.h" }
 module irgen { header "irgen.h" }
 module cxx_irgen_top { header "cxx-irgen-top.h" }
 module cxx_irgen_left { header "cxx-irgen-left.h" }
 module cxx_irgen_right { header "cxx-irgen-right.h" }
 module lookup_left_objc { header "lookup_left.h" }
 module lookup_right_objc { header "lookup_right.h" }
 module lookup_left_cxx { header "lookup_left.hpp" }
 module lookup_right_cxx { header "lookup_right.hpp" }

clang/test/Modules/documentation.cpp

+// Note: the run lines follow their respective tests, since line/column matter
+// in this test.
+
+#include "documentation.h"
+
+void other() {
+    
+}
+
+// RUN: rm -rf %t
+// RUN: %clang_cc1 -fmodules -fmodule-map-file=%S/Inputs/module.map \
+// RUN:     -fmodules-cache-path=%t -code-completion-brief-comments \
+// RUN:     -code-completion-at=%s:7:1 -o - -Wdocumentation -I%S/Inputs %s \
+// RUN:   | FileCheck %s
+
+// CHECK: COMPLETION: bar : [#void#]bar() : But this one is at least 20% cooler
+// CHECK: COMPLETION: foo : [#void#]foo() : This function is really cool