[clang] Add tryToAttachCommentsToDecls method to ASTContext

[jkorous]

Summary

Loading external comments and sorting them is expensive - mostly due to getDecomposedLoc() begin expensive. For modules with very large number of comments (~100k) this is prohibitively expensive.
In this particular case we are actually not at all interested in getting comments for declarations - just using a side-effect of the implementation which causes documentation comments to be parsed (doxygen) and attached to relevant declarations.

The FIXME in tests is fixed now.

[gribozavr]

The FIXME in tests is fixed now.

... so instead of deleting the test, could you change it to show the current, better diagnostic?

clang/include/clang/AST/ASTContext.h

818

Please add a period.

818

Please add a period.

clang/lib/AST/ASTContext.cpp

494

Would be great to explain why (because we assume that the decls and their comments were parsed just now). Otherwise the comment could enumerate a lot of other things that we are not calling here either...

564

getCommentForDecl checks D->isInvalidDecl() first.

584

Scanning all comments for every decl? Isn't that O(n^2)?

Also logic duplication below. I was expecting a call to getRawCommentForDeclNoCache, with an appropriate flag to disable loading external comments (it is a low-level API, users generally don't call it).

[jkorous]

clang/lib/AST/ASTContext.cpp

494

Haha, you're absolutely right! Thanks.

584

The important thing is that the expensive operation is source location decomposition. That's why I cache everything - GetCachedCommentBegin etc.

So while you're right that iteration-wise it's O(iteration*c*d) it`s actually O(decompose*c + decompose*d) because of the caching. The current code (which is sorting all the comments) is at least O(decompose*c*ln(c)) once you have more comments than sqrt(300) (==MagicCacheSize in SourceManager::getInBeforeInTUCache()).

That being said - you're right that just not-loading external comments in getRawCommentForDeclNoCache definitely has it's appeal. I'm running a test now get some idea about performance of both approaches.

BTW in theory we could also do one of these:

1. Allow clients to transparently set MagicCacheSize in SourceManager::getInBeforeInTUCache() which is used for SourceLocation sorting (BeforeThanCompare<RawComment>) is currently hard-coded to 300 while we are comparing ~100k x ~100k locations.
2. Change caching strategies in SourceManager::getFileID and SourceManager::getLineNumber.

[jkorous]

• clang-format
• comments

[jkorous]

Also, IIUC the test case that I deleted wasn't actually supposed to produce any diagnostics and the fact that it did was a bug. We could keep it as a regression test but I think it has a rather low value. WDYT?

[gribozavr]

Also, IIUC the test case that I deleted wasn't actually supposed to produce any diagnostics and the fact that it did was a bug. We could keep it as a regression test but I think it has a rather low value. WDYT?

What do you mean? The issue that the test is trying to show is that a single -line in a /-comment breaks the doc comment and produces weird errors. Instead it should tell the user that it looks like there's an unintended //-line.

[gribozavr]

clang/lib/AST/ASTContext.cpp

584

So while you're right that iteration-wise it's O(iteration*c*d) it`s actually O(decompose*c + decompose*d) because of the caching.

The cost of decomposing is non-trivial, but the cost of each iteration is still at least a hash table lookup.

That being said - you're right that just not-loading external comments in getRawCommentForDeclNoCache definitely has it's appeal. I'm running a test now get some idea about performance of both approaches.

Reopening, waiting for the results.

[jkorous]

Abandoned in favor of https://reviews.llvm.org/D65301

clang/include/clang/AST/ASTContext.h

public:
   /// Returns nullptr if no comment is attached.
   ///
   /// \param OriginalDecl if not nullptr, is set to declaration AST node that
   /// had the comment, if the comment we found comes from a redeclaration.
   const RawComment *
   getRawCommentForAnyRedecl(const Decl *D,
                             const Decl **OriginalDecl = nullptr) const;
 
+  /// For every comment not attached to any decl check if it should be attached
+  /// to any of \param Decls.
+  ///
+  /// \param PP the Preprocessor used with this TU.  Could be nullptr if
+  /// preprocessor is not available.
+  void tryToAttachCommentsToDecls(ArrayRef<Decl *> Decls,
+                                  const Preprocessor *PP);
+
   /// Return parsed documentation comment attached to a given declaration.
   /// Returns nullptr if no comment is attached.
   ///
   /// \param PP the Preprocessor used with this TU.  Could be nullptr if
   /// preprocessor is not available.
   comments::FullComment *getCommentForDecl(const Decl *D,
                                            const Preprocessor *PP) const;
 

clang/lib/AST/ASTContext.cpp

for (auto I : D->redecls()) {
     RawCommentAndCacheFlags &R = RedeclComments[I];
     if (R.getKind() == RawCommentAndCacheFlags::NoCommentInDecl)
       R = Raw;
   }
 
   return RC;
 }
 
+void ASTContext::tryToAttachCommentsToDecls(ArrayRef<Decl *> Decls,
+                                            const Preprocessor *PP) {
+  // Explicitly not calling ExternalSource->ReadComments() as we're interested
+  // only in comments and decls that were parsed just now.
+  ArrayRef<RawComment *> RawComments = Comments.getComments();
+  if (RawComments.empty())
+    return;
+
+  auto CacheCommentForDecl = [this, PP](const Decl *D, const RawComment *C) {
+    RawCommentAndCacheFlags CacheEntry;
+    CacheEntry.setKind(RawCommentAndCacheFlags::FromDecl);
+    CacheEntry.setRaw(C);
+    CacheEntry.setOriginalDecl(D);
+    RedeclComments[D] = CacheEntry;
+
+    // Always try to parse in order to eventually produce diagnostics.
+    comments::FullComment *FC = C->parse(*this, PP, D);
+    // But cache only if we don't have a comment yet
+    const Decl *Canonical = D->getCanonicalDecl();
+    auto ParsedComment = ParsedComments.find(Canonical);
+    if (ParsedComment != ParsedComments.end())
+      ParsedComment->second = FC;
+  };
+
+  // explicit comment location caching
+  std::unordered_map<RawComment *, std::pair<FileID, unsigned>>
+      DecomposedCommentBegin;
+  std::unordered_map<RawComment *, std::pair<FileID, unsigned>>
+      DecomposedCommentEnd;
+  std::unordered_map<unsigned, std::unordered_map<unsigned, unsigned>>
+      CommentBeginLine;
+
+  // Don't store the result for long - might go dangling.
+  auto GetCachedCommentBegin =
+      [&DecomposedCommentBegin,
+       this](RawComment *RC) -> const std::pair<FileID, unsigned> & {
+    assert(RC);
+    auto BeginIt = DecomposedCommentBegin.find(RC);
+    if (BeginIt != DecomposedCommentBegin.end()) {
+      return BeginIt->second;
+    }
+    DecomposedCommentBegin[RC] =
+        SourceMgr.getDecomposedLoc(RC->getSourceRange().getBegin());
+    return DecomposedCommentBegin[RC];
+  };
+  // Don't store the result for long - might go dangling.
+  auto GetCachedCommentEnd =
+      [&DecomposedCommentEnd,
+       this](RawComment *RC) -> const std::pair<FileID, unsigned> & {
+    assert(RC);
+    auto EndIt = DecomposedCommentEnd.find(RC);
+    if (EndIt != DecomposedCommentEnd.end()) {
+      return EndIt->second;
+    }
+    DecomposedCommentEnd[RC] =
+        SourceMgr.getDecomposedLoc(RC->getSourceRange().getEnd());
+    return DecomposedCommentEnd[RC];
+  };
+  auto GetCachedCommentBeginLine =
+      [&CommentBeginLine,
+       this](const std::pair<FileID, unsigned> &CommentBeginLoc) -> unsigned {
+    auto BeginFileIt =
+        CommentBeginLine.find(CommentBeginLoc.first.getHashValue());
+    if (BeginFileIt != CommentBeginLine.end()) {
+      auto BeginLineIt = BeginFileIt->second.find(CommentBeginLoc.second);
+      if (BeginLineIt != BeginFileIt->second.end()) {
+        return BeginLineIt->second;
+      }
+    }
+    CommentBeginLine[CommentBeginLoc.first.getHashValue()]
+                    [CommentBeginLoc.second] = SourceMgr.getLineNumber(
+                        CommentBeginLoc.first, CommentBeginLoc.second);
+    return CommentBeginLine[CommentBeginLoc.first.getHashValue()]
+                           [CommentBeginLoc.second];
+  };
+
+  for (const Decl *D : Decls) {
+    D = adjustDeclToTemplate(D);
+    if (!CanDeclHaveDocComment(D))
+      continue;
+
+    {
+      auto CIt = RedeclComments.find(D);
+      if (CIt != RedeclComments.end() && CIt->second.getOriginalDecl() == D) {
+        continue;
+      }
+    }
+
+    llvm::Optional<SourceLocation> OptCandidateCommentLoc =
+        getCandidateCommentLocation(SourceMgr, D);
+    if (!OptCandidateCommentLoc)
+      continue;
+
+    const std::pair<FileID, unsigned> DeclLocDecomp =
+        SourceMgr.getDecomposedLoc(OptCandidateCommentLoc.getValue());
+
+    // FIXME: We might optimize by keeping count of unattached comments and
+    // terminating early.
+    for (auto CIt = RawComments.begin(); CIt != RawComments.end(); ++CIt) {
+      RawComment *C = *CIt;
+      if (!C->isDocumentation() && !LangOpts.CommentOpts.ParseAllComments)
+        continue;
+
+      if (C->isAttached())
+        continue;
+
+      if (C->isTrailingComment()) {
+        if (isa<FieldDecl>(D) || isa<EnumConstantDecl>(D) || isa<VarDecl>(D) ||
+            isa<ObjCMethodDecl>(D) || isa<ObjCPropertyDecl>(D)) {
+          const std::pair<FileID, unsigned> &CommentBeginDecomp =
+              GetCachedCommentBegin(C);
+          // Check that Doxygen trailing comment comes after the declaration,
+          // starts on the same line and in the same file as the declaration.
+          if (DeclLocDecomp.first == CommentBeginDecomp.first &&
+              SourceMgr.getLineNumber(DeclLocDecomp.first,
+                                      DeclLocDecomp.second) ==
+                  GetCachedCommentBeginLine(CommentBeginDecomp)) {
+            C->setAttached();
+            CacheCommentForDecl(D, C);
+            break;
+          }
+        }
+      } else {
+        if (IsCommentBeforeDecl(SourceMgr, GetCachedCommentEnd(C),
+                                DeclLocDecomp)) {
+          C->setAttached();
+          CacheCommentForDecl(D, C);
+          break;
+        }
+      }
+    }
+  }
+}
+
 static void addRedeclaredMethods(const ObjCMethodDecl *ObjCMethod,
                    SmallVectorImpl<const NamedDecl *> &Redeclared) {
   const DeclContext *DC = ObjCMethod->getDeclContext();
   if (const auto *IMD = dyn_cast<ObjCImplDecl>(DC)) {
     const ObjCInterfaceDecl *ID = IMD->getClassInterface();
     if (!ID)
       return;
     // Add redeclared method here.

clang/lib/Sema/SemaDecl.cpp

if (Group.size() >= 2) {
     // FinalizeDeclaratorGroup adds these as separate declarations.
     Decl *MaybeTagDecl = Group[0];
     if (MaybeTagDecl && isa<TagDecl>(MaybeTagDecl)) {
       Group = Group.slice(1);
     }
   }
 
   // See if there are any new comments that are not attached to a decl.
-  ArrayRef<RawComment *> Comments = Context.getRawCommentList().getComments();
-  if (!Comments.empty() &&
-      !Comments.back()->isAttached()) {
-    // There is at least one comment that not attached to a decl.
-    // Maybe it should be attached to one of these decls?
-    //
-    // Note that this way we pick up not only comments that precede the
-    // declaration, but also comments that *follow* the declaration -- thanks to
-    // the lookahead in the lexer: we've consumed the semicolon and looked
-    // ahead through comments.
-    for (unsigned i = 0, e = Group.size(); i != e; ++i)
-      Context.getCommentForDecl(Group[i], &PP);
-  }
+  Context.tryToAttachCommentsToDecls(Group, &PP);
 }
 
 /// ActOnParamDeclarator - Called from Parser::ParseFunctionDeclarator()
 /// to introduce parameters into function prototype scope.
 Decl *Sema::ActOnParamDeclarator(Scope *S, Declarator &D) {
   const DeclSpec &DS = D.getDeclSpec();
 
   // Verify C99 6.7.5.3p2: The only SCS allowed is 'register'.

clang/test/Sema/warn-documentation.cpp

 // expected-warning@+1 {{'\endverbatim' command does not terminate a verbatim text block}}
 /// \endverbatim
 int test_verbatim_1();
 
 // expected-warning@+1 {{'\endcode' command does not terminate a verbatim text block}}
 /// \endcode
 int test_verbatim_2();
 
-// FIXME: we give a bad diagnostic here because we throw away non-documentation
-// comments early.
-//
-// expected-warning@+3 {{'\endcode' command does not terminate a verbatim text block}}
-/// \code
-//  foo
-/// \endcode
-int test_verbatim_3();
-
-
 // expected-warning@+1 {{empty paragraph passed to '\brief' command}}
 int test1; ///< \brief\author Aaa
 
 // expected-warning@+2 {{empty paragraph passed to '\brief' command}}
 // expected-warning@+2 {{empty paragraph passed to '\brief' command}}
 int test2, ///< \brief\author Aaa
     test3; ///< \brief\author Aaa