[clangd] Store xref for Macros in ParsedAST.

[usaxena95]

Summary

This patch adds the cross references for Macros in the MainFile.
We add references for the main file to the ParsedAST. We query the
references from it using the SymbolID.
Xref outside main file will be added to the index in a separate patch.

[usaxena95]

Please ignore the changes from patch https://reviews.llvm.org/D69937
Will fix this.

[usaxena95]

Removing changes from different patch.

[hokein]

clang-tools-extra/clangd/CollectMacros.h

29

I think the Ranges and MacrosRefs have a lot of duplications, it is wasteful to store a same range twice. We don't need the MainFilePath, the callers should know the corresponding file path for the AST. Something like llvm::DenseMap<SymbolID, std::vector<Range>> Refs; should be enough.

symbol id for macro generation is required the definition location, but only defined macros have it, we may need an extra vector to store ranges for undefined macros.

#ifndef abc // there is no macro info* for abc, so getSymbolID will fail, but we still want it, e.g. in semantic highlighting.
#endif

There may be more tricky cases, it would be nice to have in the test.

#define abc 1
#undef abc

#define abc 2
#undef abc

clang-tools-extra/clangd/XRefs.cpp

900

this is not completed, it only shows the macro refs in main file, we still need to query the index to get the rest (but our index doesn't collect macro at the moment). I'd prefer not doing this in this patch until our index is ready.

For testing, I think we can create a new test file for CollectMainFileMacros.

[usaxena95]

Rebase

[usaxena95]

clang-tools-extra/clangd/XRefs.cpp

900

Yup. This patch is just for the main file. The index and the lookup will be modified in the next patch. Wanted to keep this small.

[merge_guards_bot]

Build result: pass - 59967 tests passed, 0 failed and 763 were skipped.
Log files: console-log.txt, CMakeCache.txt

[usaxena95]

Added tests for CollectMacros.h
Addressed comments.

[usaxena95]

Fixed typos.

[usaxena95]

clang-tools-extra/clangd/CollectMacros.h

29

• using llvm::DenseMap<SymbolID, std::set<Range>> Refs; as de-duplication is easier.
• Iterating on all the ranges is a pain. Let me know if you want to provide a different method to return all the ranges (sad part: lot of copying).
• I had multiple definitions of a macro in the test case, but I have shifted to its separate test case.

[merge_guards_bot]

Build result: pass - 59989 tests passed, 0 failed and 763 were skipped.
Log files: console-log.txt, CMakeCache.txt

[merge_guards_bot]

Build result: pass - 59989 tests passed, 0 failed and 763 were skipped.
Log files: console-log.txt, CMakeCache.txt

[hokein]

clang-tools-extra/clangd/CollectMacros.h

29

as de-duplication is easier.

will we encounter duplications? My theory is that we should not. I think it is fine to use vector. And you also use vector for the UnknownMacros below.

clang-tools-extra/clangd/SemanticHighlighting.cpp

313–314

nit: the document was stale, expansions => references.

clang-tools-extra/clangd/XRefs.cpp

900

this would enable the xref for macros, but the feature is not ready yet. I think we'd better add this code when everything is ready.

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

57

could you add test case where there is an undefined macro reference before the macro definition, like

#ifndef abc
#define abc
#endif
#endif

I think the first abc is unknown, the second abc is defined?

81

I might be missing something, I didn't get the motivation of using numbers in the annotation, the code seems just collecting all annotated ranges regardless the value of the number and compare to the actual ranges. it doesn't verify that e.g. in your 2rd cases, the two macros abc are different symbols.

How about just verifying a single defined macro for each case? e.g. the below case, we try to get the symbol id (call locatedMacroAt) from the T.point(), retrieve the responding ranges from the MainFileMacros, compare to the annotated ranges.

#define [[F^oo]] 1
int abc = [[Foo]];
#undef [[Foo]]

[usaxena95]

clang-tools-extra/clangd/XRefs.cpp

900

Removed looking up xref.

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

81

Since the output of CollectMacros is a mapping from SymbolID -> vector, I wanted to verify that we form correct groups of ranges (grouped by SymbolID).
So a single macro per test case wouldn't be able to test this.

I didn't get the motivation of using numbers in the annotation, the code seems just collecting all annotated ranges regardless the value of the number and compare to the actual ranges. it doesn't verify that e.g. in your 2rd cases, the two macros abc are different symbols.

We actually group the ranges by their annotation and form Matcher <std::vector<Matcher <std::vector<Range>>>>. So it checks for the correct grouping too.

[hokein]

looks like you forgot to upload the latest patch.

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

81

I see, having a complex Matcher <std::vector<Matcher <std::vector<Range>>>> would hurt code readability, and the error message is also not friendly when there are failed testcases.

How about extending it like below? To improve the error message, I think we should do a string comparison: the test annotation v.s the raw code with the actual macro references annotated (we'd need to write some code to compute this actual annotated code, you can see SemanticHighlightingTests.cpp for reference).

#define $1[[a$1^bc]] 1
#undef $1[[abc]]

#define $2[[a$2^bc]] 2
#undef $2[[abc]]

#ifdef $Unknown[[abc]]
#endif

[usaxena95]

Uploading latest patch

[merge_guards_bot]

Build result: pass - 60093 tests passed, 0 failed and 729 were skipped.
Log files: console-log.txt, CMakeCache.txt

[usaxena95]

Modified tests for better error messages.

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

81

I have tried to check against each group now. Also verifies the SymbolID. Failures will point the annotation for which the testcase failed.
Recreating the annotated code from the raw code would become more complex as it would involve maintaining a mapping from SymbolId->Annotation. Works quite nicely for SemanticHighlighting as we have the whole Token stream. Creating the replacements does not sound trivial to me.

[merge_guards_bot]

Build result: pass - 60093 tests passed, 0 failed and 729 were skipped.
Log files: console-log.txt, CMakeCache.txt

[usaxena95]

Minor change: Resued variable.

[merge_guards_bot]

Build result: pass - 60093 tests passed, 0 failed and 729 were skipped.
Log files: console-log.txt, CMakeCache.txt

[hokein]

Thanks, looks mostly good, a few more nits.

clang-tools-extra/clangd/CollectMacros.h

90–96

nit: abstract MacroNameTok.getIdentifierInfo()->getName() to a variable? we also used this on line 90.

clang-tools-extra/clangd/XRefs.cpp

898

nit: remove this change.

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

2

nit: add missing license.

29

This is interesting, by "doesn't work", you mean the function could not locate the correct definitions for (the first & second abc)?

50

could you add one more test case where there is a macro reference in another macro argument, like:

#define M(X) X;
#define $1[[abc]] 123
int s = M($1[[abc]]);

75

nit: const auto &

81

Thanks, this looks better now.

110

nit: we need newline at EOF.

[usaxena95]

Addressed comments.

[usaxena95]

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

29

It is not able to locate the macro for second definition.
Causes assertion failure at line 93: assert(Macro);

75

ranges returns a copy and not a reference. I would expect copy elision here and & would be unnecessary.

[hokein]

lgtm, thanks!

clang-tools-extra/clangd/CollectMacros.h

 //===--- CollectMacros.h -----------------------------------------*- C++-*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_COLLECTEDMACROS_H
 #define LLVM_CLANG_TOOLS_EXTRA_CLANGD_COLLECTEDMACROS_H
 
+#include "AST.h"
 #include "Protocol.h"
 #include "SourceCode.h"
+#include "index/SymbolID.h"
 #include "clang/Basic/IdentifierTable.h"
 #include "clang/Lex/PPCallbacks.h"
+#include "llvm/ADT/DenseMap.h"
 #include <string>
 
 namespace clang {
 namespace clangd {
 
 struct MainFileMacros {
   llvm::StringSet<> Names;
   // Instead of storing SourceLocation, we have to store the token range because
   // SourceManager from preamble is not available when we build the AST.
-  std::vector<Range> Ranges;
+  llvm::DenseMap<SymbolID, std::vector<Range>> MacroRefs;
+  // Somtimes it is not possible to compute the SymbolID for the Macro, e.g. a
+  // reference to an undefined macro. Store them separately, e.g. for semantic
+  // highlighting.
+  std::vector<Range> UnknownMacros;
 };
 
 /// Collects macro references (e.g. definitions, expansions) in the main file.
 /// It is used to:
 ///  - collect macros in the preamble section of the main file (in Preamble.cpp)
 ///  - collect macros after the preamble of the main file (in ParsedAST.cpp)
 class CollectMainFileMacros : public PPCallbacks {
 public:
private:
   void add(const Token &MacroNameTok, const MacroInfo *MI) {
     if (!InMainFile)
       return;
     auto Loc = MacroNameTok.getLocation();
     if (Loc.isMacroID())
       return;
 
     if (auto Range = getTokenRange(SM, LangOpts, Loc)) {
-      Out.Names.insert(MacroNameTok.getIdentifierInfo()->getName());
-      Out.Ranges.push_back(*Range);
+      auto Name = MacroNameTok.getIdentifierInfo()->getName();
+      Out.Names.insert(Name);
+      if (auto SID = getSymbolID(Name, MI, SM))
+        Out.MacroRefs[*SID].push_back(*Range);
+      else
+        Out.UnknownMacros.push_back(*Range);
     }
   }
   const SourceManager &SM;
   const LangOptions &LangOpts;
   bool InMainFile = true;
   MainFileMacros &Out;
 };
 
 } // namespace clangd
 } // namespace clang
 
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_COLLECTEDMACROS_H

clang-tools-extra/clangd/SemanticHighlighting.cpp

std::vector<HighlightingToken> getSemanticHighlightings(ParsedAST &AST) {
   // Add highlightings for AST nodes.
   HighlightingsBuilder Builder(AST.getSourceManager(), C.getLangOpts());
   // Highlight 'decltype' and 'auto' as their underlying types.
   CollectExtraHighlightings(Builder).TraverseAST(C);
   // Highlight all decls and references coming from the AST.
   findExplicitReferences(C, [&](ReferenceLoc R) {
     if (auto Kind = kindForReference(R))
       Builder.addToken(R.NameLoc, *Kind);
   });
-  // Add highlightings for macro expansions.
-  for (const auto &M : AST.getMacros().Ranges)
+  // Add highlightings for macro references.
+  for (const auto &SIDToRefs : AST.getMacros().MacroRefs) {
+    for (const auto &M : SIDToRefs.second)
       Builder.addToken({HighlightingKind::Macro, M});
+  }
+  for (const auto &M : AST.getMacros().UnknownMacros)
+    Builder.addToken({HighlightingKind::Macro, M});
+
   return std::move(Builder).collect();
 }
 
 llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, HighlightingKind K) {
   switch (K) {
   case HighlightingKind::Variable:
     return OS << "Variable";
   case HighlightingKind::LocalVariable:

clang-tools-extra/clangd/XRefs.cpp

std::vector<Location> findReferences(ParsedAST &AST, Position Pos,
   auto MainFilePath =
       getCanonicalPath(SM.getFileEntryForID(SM.getMainFileID()), SM);
   if (!MainFilePath) {
     elog("Failed to get a path for the main file, so no references");
     return Results;
   }
   auto Loc = SM.getMacroArgExpandedLocation(
       getBeginningOfIdentifier(Pos, SM, AST.getASTContext().getLangOpts()));
   // TODO: should we handle macros, too?
   // We also show references to the targets of using-decls, so we include
   // DeclRelation::Underlying.
   DeclRelationSet Relations = DeclRelation::TemplatePattern |
                               DeclRelation::Alias | DeclRelation::Underlying;
   auto Decls = getDeclAtPosition(AST, Loc, Relations);
 
   // We traverse the AST to find references in the main file.
   auto MainFileRefs = findRefs(Decls, AST);
   // We may get multiple refs with the same location and different Roles, as
   // cross-reference is only interested in locations, we deduplicate them
   // by the location to avoid emitting duplicated locations.
   MainFileRefs.erase(std::unique(MainFileRefs.begin(), MainFileRefs.end(),
                                  [](const ReferenceFinder::Reference &L,
                                     const ReferenceFinder::Reference &R) {
                                    return L.Loc == R.Loc;
                                  }),
                      MainFileRefs.end());
   for (const auto &Ref : MainFileRefs) {
     if (auto Range =
-            getTokenRange(AST.getASTContext().getSourceManager(),
-                          AST.getASTContext().getLangOpts(), Ref.Loc)) {
+            getTokenRange(SM, AST.getASTContext().getLangOpts(), Ref.Loc)) {
       Location Result;
       Result.range = *Range;
       Result.uri = URIForFile::canonicalize(*MainFilePath, *MainFilePath);
       Results.push_back(std::move(Result));
     }
   }
 
   // Now query the index for references from other files.

clang-tools-extra/clangd/unittests/CMakeLists.txt

add_unittest(ClangdUnitTests ClangdTests
   Annotations.cpp
   ASTTests.cpp
   BackgroundIndexTests.cpp
   CancellationTests.cpp
   CanonicalIncludesTests.cpp
   ClangdTests.cpp
   CodeCompleteTests.cpp
   CodeCompletionStringsTests.cpp
+  CollectMacrosTests.cpp
   ContextTests.cpp
   DexTests.cpp
   DiagnosticsTests.cpp
   DraftStoreTests.cpp
   ExpectedTypeTest.cpp
   FileDistanceTests.cpp
   FileIndexTests.cpp
   FindSymbolsTests.cpp

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

+//===-- CollectMacrosTests.cpp ----------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+#include "Annotations.h"
+#include "CollectMacros.h"
+#include "Matchers.h"
+#include "SourceCode.h"
+#include "TestTU.h"
+#include "index/SymbolID.h"
+#include "clang/Basic/SourceLocation.h"
+#include "llvm/Support/ScopedPrinter.h"
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+
+namespace clang {
+namespace clangd {
+namespace {
+
+using testing::UnorderedElementsAreArray;
+
+TEST(CollectMainFileMacros, SelectedMacros) {
+  // References of the same symbol must have the ranges with the same
+  // name(integer). If there are N different symbols then they must be named
+  // from 1 to N. Macros for which SymbolID cannot be computed must be named
+  // "Unknown".
+  const char *Tests[] = {
+      R"cpp(// Macros: Cursor on definition.
+        #define $1[[FOO]](x,y) (x + y)
+        int main() { int x = $1[[FOO]]($1[[FOO]](3, 4), $1[[FOO]](5, 6)); }
+      )cpp",
+      R"cpp(
+        #define $1[[M]](X) X;
+        #define $2[[abc]] 123
+        int s = $1[[M]]($2[[abc]]);
+      )cpp",
+      // FIXME: Locating macro in duplicate definitions doesn't work. Enable
+      // this once LocateMacro is fixed.
+      // R"cpp(// Multiple definitions.
+      //   #define $1[[abc]] 1
+      //   int func1() { int a = $1[[abc]];}
+      //   #undef $1[[abc]]
+
+      //   #define $2[[abc]] 2
+      //   int func2() { int a = $2[[abc]];}
+      //   #undef $2[[abc]]
+      // )cpp",
+      R"cpp(
+        #ifdef $Unknown[[UNDEFINED]]
+        #endif
+      )cpp",
+      R"cpp(
+        #ifndef $Unknown[[abc]]
+        #define $1[[abc]]
+        #ifdef $1[[abc]]
+        #endif
+        #endif
+      )cpp",
+      R"cpp(
+        // Macros from token concatenations not included.
+        #define $1[[CONCAT]](X) X##A()
+        #define $2[[PREPEND]](X) MACRO##X()
+        #define $3[[MACROA]]() 123
+        int B = $1[[CONCAT]](MACRO);
+        int D = $2[[PREPEND]](A)
+      )cpp",
+      R"cpp(
+        // FIXME: Macro names in a definition are not detected.
+        #define $1[[MACRO_ARGS2]](X, Y) X Y
+        #define $2[[FOO]] BAR
+        #define $3[[BAR]] 1
+        int A = $2[[FOO]];
+      )cpp"};
+  for (const char *Test : Tests) {
+    Annotations T(Test);
+    auto AST = TestTU::withCode(T.code()).build();
+    auto ActualMacroRefs = AST.getMacros();
+    auto &SM = AST.getSourceManager();
+    auto &PP = AST.getPreprocessor();
+
+    // Known macros.
+    for (int I = 1;; I++) {
+      const auto ExpectedRefs = T.ranges(llvm::to_string(I));
+      if (ExpectedRefs.empty())
+        break;
+
+      auto Loc = getBeginningOfIdentifier(ExpectedRefs.begin()->start, SM,
+                                          AST.getASTContext().getLangOpts());
+      auto Macro = locateMacroAt(Loc, PP);
+      assert(Macro);
+      auto SID = getSymbolID(Macro->Name, Macro->Info, SM);
+
+      EXPECT_THAT(ExpectedRefs,
+                  UnorderedElementsAreArray(ActualMacroRefs.MacroRefs[*SID]))
+          << "Annotation=" << I << ", MacroName=" << Macro->Name
+          << ", Test = " << Test;
+    }
+    // Unkown macros.
+    EXPECT_THAT(AST.getMacros().UnknownMacros,
+                UnorderedElementsAreArray(T.ranges("Unknown")))
+        << "Unknown macros doesn't match in " << Test;
+  }
+}
+} // namespace
+} // namespace clangd
+} // namespace clang

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

Annotations TestCase(R"cpp(
     #include "foo.inc"
 
     #define ^assert(COND) if (!(COND)) { printf("%s", #COND); exit(0); }
 
     void test() {
       // Includes macro expansions in arguments that are expressions
       ^assert(0 <= ^BAR);
     }
+
+    #ifdef ^UNDEFINED
+    #endif
+
+    #define ^MULTIPLE_DEFINITION 1
+    #undef ^MULTIPLE_DEFINITION
+
+    #define ^MULTIPLE_DEFINITION 2
+    #undef ^MULTIPLE_DEFINITION
   )cpp");
   auto TU = TestTU::withCode(TestCase.code());
   TU.HeaderCode = R"cpp(
     #define ID(X) X
     #define MACRO_EXP(X) ID(X)
     MACRO_EXP(int B);
   )cpp";
   TU.AdditionalFiles["foo.inc"] = R"cpp(
     int C = ID(1);
     #define DEF 1
     int D = DEF;
   )cpp";
   ParsedAST AST = TU.build();
   std::vector<Position> MacroExpansionPositions;
-  for (const auto &R : AST.getMacros().Ranges)
+  for (const auto &SIDToRefs : AST.getMacros().MacroRefs) {
+    for (const auto &R : SIDToRefs.second)
+      MacroExpansionPositions.push_back(R.start);
+  }
+  for (const auto &R : AST.getMacros().UnknownMacros)
     MacroExpansionPositions.push_back(R.start);
   EXPECT_THAT(MacroExpansionPositions,
               testing::UnorderedElementsAreArray(TestCase.points()));
 }
 
 } // namespace
 } // namespace clangd
 } // namespace clang