[include-cleaner] Show includes matched by refs in HTML report.

[sammccall]

Summary

Demo: https://htmlpreview.github.io/?https://gist.githubusercontent.com/sam-mccall/ecee6869e37af3db28089b64d8dce806/raw/8736e64c45af411e2c2d72adaed2dfc4410a5b36/ASTTests.html%25202

[hokein]

Thanks, I like the idea of marking missing-include refs.

I haven't read the code yet, and below are all my findings when I played with the demo html (some of them are unrelated to the current patch, just want to dump all):

1. size_t shows duplicated entries, line 465
2. we are missing refs in some using declarations (line 31, line32), but line 33 does have a link which seems weird
3. UI related:
   • it would be nice to highlight the whole line, if user clicks the line link from the shown-up panel;
   • for Included path/to/header.h, I think adding the ""/<> around the spelling string will be nicer;
   • for main-file symbols, showing (Header ASTTests.cpp) is suboptimal, but I don't have better solution;
4. The handling of std symbols seems inconsistent:
   • click on a vector push_back will give the mapping vector header;
   • click on the type std::vector will give the iosfwd header;
5. I was confused why the type Annotation has the Included file, but not the method call .code(), since both shown-up panel are showing Annotations.h header, then I realized that the code is from the base class llvm::Annotation. This brings up a policy question (Not sure it has been discussed before): If we have already included the header of a subclass, and we have some base-class method calls via the subclass object, do we need to insert the header of the base class?

[sammccall]

In D138219#3936279, @hokein wrote:

Thanks, I like the idea of marking missing-include refs.

I haven't read the code yet, and below are all my findings when I played with the demo html (some of them are unrelated to the current patch, just want to dump all):

Sure thing, here are my notes :-)

1. size_t shows duplicated entries, line 465

This is because we're using the same decl-specifier with multiple declarators, but the AST doesn't model that. I don't think this is a big deal, we should deduplicate before actually displaying/applying findings but no need in this too imo.

2. we are missing refs in some using declarations (line 31, line32), but line 33 does have a link which seems weird

They are different types of symbol (template vs function), may make a difference?

3. UI related:
   • it would be nice to highlight the whole line, if user clicks the line link from the shown-up panel;

Hmm, i think i can do this with CSS3 :target. Otherwise I don't think it's worth adding extra JS for.

• for Included path/to/header.h, I think adding the ""/<> around the spelling string will be nicer;

Agree, but we don't know which, and i don't think it's worth adding it to the library for that purpose only.

• for main-file symbols, showing (Header ASTTests.cpp) is suboptimal, but I don't have better solution;

I think MainFile should be a Header variant maybe. (Not just for this)

4. The handling of std symbols seems inconsistent:
   • click on a vector push_back will give the mapping vector header;
   • click on the type std::vector will give the iosfwd header;

At first glance this indeed looks like a bug (not in this patch i guess)

5. I was confused why the type Annotation has the Included file, but not the method call .code(), since both shown-up panel are showing Annotations.h header, then I realized that the code is from the base class llvm::Annotation. This brings up a policy question (Not sure it has been discussed before): If we have already included the header of a subclass, and we have some base-class method calls via the subclass object, do we need to insert the header of the base class?

Right, that's silly. I do think policy on member access in general is still a bit up in the air.

[hokein]

we are missing refs in some using declarations (line 31, line32), but line 33 does have a link which seems weird

They are different types of symbol (template vs function), may make a difference?

You're right, the template is the reason here. Taking a closing look, the logic of in WalkAST.cpp doesn't seem to handle well on this case.

E.g. for the following case, the UsingShadowDecl refers to the *primary* template decl, which is not marked as used or referenced. The used/referenced bit is only set for specialized FunctionDecl, so WalkAST doesn't report this UsingDecl location. (EnumDecl also has this problem).

namespace ns {
template<typename T>
int func();
}

using ns::func; 

int k = func<int>();

[sammccall]

(I do think the outstanding issues are not related to this patch, so this is ready for review)

In D138219#3945954, @hokein wrote:

E.g. for the following case, the UsingShadowDecl refers to the *primary* template decl, which is not marked as used or referenced. The used/referenced bit is only set for specialized FunctionDecl, so WalkAST doesn't report this UsingDecl location. (EnumDecl also has this problem).

That makes sense, I can imagine a few ways to fix this (change the bits in the AST, walk over specializations, drop the used||referenced approach).

[sammccall]

In D138219#3946020, @sammccall wrote:

In D138219#3945954, @hokein wrote:

E.g. for the following case, the UsingShadowDecl refers to the *primary* template decl, which is not marked as used or referenced. The used/referenced bit is only set for specialized FunctionDecl, so WalkAST doesn't report this UsingDecl location. (EnumDecl also has this problem).

That makes sense, I can imagine a few ways to fix this (change the bits in the AST, walk over specializations, drop the used||referenced approach).

Filed https://github.com/llvm/llvm-project/issues/59147

[hokein]

In D138219#3946020, @sammccall wrote:

(I do think the outstanding issues are not related to this patch, so this is ready for review)

Agree (sorry, I didn't mean we should address in this patch). We have found a few issues, I think we should record them in the issue tracker so that we don't lose them.

clang-tools-extra/include-cleaner/lib/HTMLReport.cpp

117

nit: the FE can be removed -- we have the FileID, we can retrieve it by SM.getFileEntryByID(File)

127

Worth to add a comment on the meaning of Satisfied.

161

The current behaivor looks fine to me, but this is not the final state, right? We will revisit it when we have all the ranking/included-header bits in the library, if so, probably add a FIXME?

163

a comment -- this is for the target symbol defined in the main file?

[sammccall]

clang-tools-extra/include-cleaner/lib/HTMLReport.cpp

117

Sure, I'd just rather do that in the constructor than in the inner loop

161

Ranking isn't relevant whether a ref is satisfied or not.

If we add the concept of one provider dominating another, this logic might change. (e.g. for std::vector accept <iosfwd> but not if <vector> is included). But this is up in the air and also would probably be encapsulated in a signature change to Includes.match.

Added a FIXME to avoid the brittle main-file check.

163

Defined or declared or otherwise provided by the main file.
Renamed FE => MainFE. Beyond that I think such a comment just echoes the code.

[sammccall]

address comments

[hokein]

clang-tools-extra/include-cleaner/lib/HTMLReport.cpp

116–117

nit: maybe rename to MainFile to correspond to the MainFE

clang-tools-extra/include-cleaner/lib/AnalysisInternal.h

 
 /// Finds the headers that provide the symbol location.
 // FIXME: expose signals
 llvm::SmallVector<Header> findHeaders(const SymbolLocation &Loc,
                                       const SourceManager &SM,
                                       const PragmaIncludes *PI);
 
 /// Write an HTML summary of the analysis to the given stream.
-void writeHTMLReport(FileID File, llvm::ArrayRef<Decl *> Roots,
+void writeHTMLReport(FileID File, const RecordedPP::RecordedIncludes &Includes,
+                     llvm::ArrayRef<Decl *> Roots,
                      llvm::ArrayRef<SymbolReference> MacroRefs, ASTContext &Ctx,
                      PragmaIncludes *PI, llvm::raw_ostream &OS);
 
 } // namespace include_cleaner
 } // namespace clang
 
 #endif

clang-tools-extra/include-cleaner/lib/HTMLReport.cpp

#hover {
     z-index: 1;
     position: absolute; top: 100%; left: 0;
     font-family: sans-serif;
     padding: 0.5em;
   }
   #hover p, #hover pre { margin: 0; }
   #hover .target.implicit { background-color: #bbb; }
   #hover .target.ambiguous { background-color: #caf; }
+  .missing, .unused { background-color: #faa !important; }
   #hover th { color: #008; text-align: right; padding-right: 0.5em; }
   #hover .target:not(:first-child) {
     margin-top: 1em;
     padding-top: 1em;
     border-top: 1px solid #444;
   }
 )css";
 
llvm::StringRef refType(RefType T) {
   }
   llvm_unreachable("unhandled RefType enum");
 }
 
 class Reporter {
   llvm::raw_ostream &OS;
   const ASTContext &Ctx;
   const SourceManager &SM;
+  const RecordedPP::RecordedIncludes &Includes;
   const PragmaIncludes *PI;
-  FileID File;
+  FileID MainFile;
+  const FileEntry *MainFE;
 
   // References to symbols from the main file.
   // FIXME: should we deduplicate these?
   struct Target {
     Symbol Sym;
     RefType Type;
     SmallVector<SymbolLocation> Locations;
     SmallVector<Header> Headers;
+    SmallVector<const Include *> Includes;
+    bool Satisfied = false; // Is the include present?
   };
   std::vector<Target> Targets;
   // Points within the main file that reference a Target.
   // Implicit refs will be marked with a symbol just before the token.
   struct Ref {
     unsigned Offset;
     bool Implicit;
     size_t TargetIndex;
     bool operator<(const Ref &Other) const {
       return std::forward_as_tuple(Offset, !Implicit, TargetIndex) <
              std::forward_as_tuple(Other.Offset, !Other.Implicit, TargetIndex);
     }
   };
   std::vector<Ref> Refs;
 
   Target makeTarget(const SymbolReference &SR) {
-    Target T{SR.Target, SR.RT, {}, {}};
+    Target T{SR.Target, SR.RT, {}, {}, {}};
 
     // Duplicates logic from walkUsed(), which doesn't expose SymbolLocations.
     // FIXME: use locateDecl and friends once implemented.
     // This doesn't use stdlib::Recognizer, but locateDecl will soon do that.
     switch (SR.Target.kind()) {
     case Symbol::Declaration:
       T.Locations.push_back(SR.Target.declaration().getLocation());
       break;
     case Symbol::Macro:
       T.Locations.push_back(SR.Target.macro().Definition);
       break;
     }
 
     for (const auto &Loc : T.Locations)
-      T.Headers = findHeaders(Loc, SM, PI);
+      T.Headers.append(findHeaders(Loc, SM, PI));
+
+    for (const auto &H : T.Headers) {
+      T.Includes.append(Includes.match(H));
+      // FIXME: library should signal main-file refs somehow.
+      // Non-physical refs to the main-file should be possible.
+      if (H.kind() == Header::Physical && H.physical() == MainFE)
+        T.Satisfied = true;
+    }
+    if (!T.Includes.empty())
+      T.Satisfied = true;
+    // Include pointers are meaningfully ordered as they are backed by a vector.
+    llvm::sort(T.Includes);
+    T.Includes.erase(std::unique(T.Includes.begin(), T.Includes.end()),
+                     T.Includes.end());
 
     return T;
   }
 
 public:
-  Reporter(llvm::raw_ostream &OS, ASTContext &Ctx, const PragmaIncludes *PI,
-           FileID File)
-      : OS(OS), Ctx(Ctx), SM(Ctx.getSourceManager()), PI(PI), File(File) {}
+  Reporter(llvm::raw_ostream &OS, ASTContext &Ctx,
+           const RecordedPP::RecordedIncludes &Includes,
+           const PragmaIncludes *PI, FileID MainFile)
+      : OS(OS), Ctx(Ctx), SM(Ctx.getSourceManager()), Includes(Includes),
+        PI(PI), MainFile(MainFile), MainFE(SM.getFileEntryForID(MainFile)) {}
 
   void addRef(const SymbolReference &SR) {
     auto [File, Offset] = SM.getDecomposedLoc(SM.getFileLoc(SR.RefLocation));
-    if (File != this->File) {
+    if (File != this->MainFile) {
       // Can get here e.g. if there's an #include inside a root Decl.
       // FIXME: do something more useful than this.
       llvm::errs() << "Ref location outside file! " << SR.Target << " at "
                    << SR.RefLocation.printToString(SM) << "\n";
       return;
     }
 
     Refs.push_back({Offset, SR.RT == RefType::Implicit, Targets.size()});
for (const auto &H : T.Headers) {
       case Header::Verbatim:
         OS << "verbatim ";
         escapeString(H.verbatim());
         break;
       }
       OS << "</td></tr>\n";
     }
 
+    for (const auto *I : T.Includes) {
+      OS << "<tr><th>Included</th><td>";
+      escapeString(I->Spelled);
+      OS << ", <a href='#line" << I->Line << "'>line " << I->Line << "</a>";
+      OS << "</td></tr>";
+    }
+
     OS << "</table>";
   }
 
   void writeCode() {
     llvm::sort(Refs);
-    llvm::StringRef Code = SM.getBufferData(File);
+    llvm::StringRef Code = SM.getBufferData(MainFile);
 
     OS << "<pre onclick='select(event)' class='code'>";
-    OS << "<code class='line'>";
+    OS << "<code class='line' id='line1'>";
+    unsigned LineNum = 1;
     auto Rest = llvm::makeArrayRef(Refs);
     unsigned End = 0;
     for (unsigned I = 0; I < Code.size(); ++I) {
       // Finish refs early at EOL to avoid dealing with splitting the span.
       if (End && (End == I || Code[I] == '\n')) {
         OS << "</span>";
         End = 0;
       }
       // Handle implicit refs, which are rendered *before* the token.
       while (!Rest.empty() && Rest.front().Offset == I &&
              Rest.front().Implicit) {
         const Ref &R = Rest.front();
-        OS << "<span class='ref sel implicit' data-hover='t" << R.TargetIndex
-           << "'>&loz;</span>";
+        OS << "<span class='ref sel implicit"
+           << (Targets[R.TargetIndex].Satisfied ? "" : " missing")
+           << "' data-hover='t" << R.TargetIndex << "'>&loz;</span>";
         Rest = Rest.drop_front();
       };
       // Accumulate all explicit refs that appear on the same token.
       std::string TargetList;
+      bool Unsatisfied = false;
       Rest = Rest.drop_while([&](const Ref &R) {
         if (R.Offset != I)
           return false;
         if (!TargetList.empty())
           TargetList.push_back(',');
         TargetList.push_back('t');
         TargetList.append(std::to_string(R.TargetIndex));
+        Unsatisfied = Unsatisfied || !Targets[R.TargetIndex].Satisfied;
         return true;
       });
       if (!TargetList.empty()) {
         assert(End == 0 && "Overlapping tokens!");
-        OS << "<span class='ref sel' data-hover='" << TargetList << "'>";
-        End = I + Lexer::MeasureTokenLength(SM.getComposedLoc(File, I), SM,
+        OS << "<span class='ref sel" << (Unsatisfied ? " missing" : "")
+           << "' data-hover='" << TargetList << "'>";
+        End = I + Lexer::MeasureTokenLength(SM.getComposedLoc(MainFile, I), SM,
                                             Ctx.getLangOpts());
       }
       if (Code[I] == '\n')
-        OS << "</code>\n<code class='line'>";
+        OS << "</code>\n<code class='line' id='line" << (++LineNum) << "'>";
       else
         escapeChar(Code[I]);
     }
     OS << "</code></pre>\n";
   }
 };
 
 } // namespace
 
-void writeHTMLReport(FileID File, llvm::ArrayRef<Decl *> Roots,
+void writeHTMLReport(FileID File, const RecordedPP::RecordedIncludes &Includes,
+                     llvm::ArrayRef<Decl *> Roots,
                      llvm::ArrayRef<SymbolReference> MacroRefs, ASTContext &Ctx,
                      PragmaIncludes *PI, llvm::raw_ostream &OS) {
-  Reporter R(OS, Ctx, PI, File);
+  Reporter R(OS, Ctx, Includes, PI, File);
   for (Decl *Root : Roots)
     walkAST(*Root, [&](SourceLocation Loc, const NamedDecl &D, RefType T) {
       R.addRef(SymbolReference{Loc, D, T});
     });
   for (const SymbolReference &Ref : MacroRefs)
     R.addRef(Ref);
   R.write();
 }
 
 } // namespace clang::include_cleaner

clang-tools-extra/include-cleaner/tool/IncludeCleaner.cpp

class HTMLReportAction : public clang::ASTFrontendAction {
   void EndSourceFile() override {
     std::error_code EC;
     llvm::raw_fd_ostream OS(HTMLReportPath, EC);
     if (EC) {
       llvm::errs() << "Unable to write HTML report to " << HTMLReportPath
                    << ": " << EC.message() << "\n";
       exit(1);
     }
-    writeHTMLReport(AST.Ctx->getSourceManager().getMainFileID(), AST.Roots,
-                    PP.MacroReferences, *AST.Ctx, &PI, OS);
+    writeHTMLReport(AST.Ctx->getSourceManager().getMainFileID(), PP.Includes,
+                    AST.Roots, PP.MacroReferences, *AST.Ctx, &PI, OS);
   }
 };
 
 } // namespace
 } // namespace include_cleaner
 } // namespace clang
 
 int main(int argc, const char **argv) {