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

   1 //===--- HTMLReport.cpp - Explain the analysis for humans -----------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // If we're debugging this tool or trying to explain its conclusions, we need to
  10 // be able to identify specific facts about the code and the inferences made.
  11 //
  12 // This library prints an annotated version of the code
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #include "AnalysisInternal.h"
  17 #include "clang-include-cleaner/Types.h"
  18 #include "clang/AST/ASTContext.h"
  19 #include "clang/AST/PrettyPrinter.h"
  20 #include "clang/Basic/SourceManager.h"
  21 #include "clang/Lex/HeaderSearch.h"
  22 #include "clang/Lex/Lexer.h"
  23 #include "clang/Tooling/Inclusions/StandardLibrary.h"
  24 #include "llvm/Support/ScopedPrinter.h"
  25 #include "llvm/Support/raw_ostream.h"
  26 #include <numeric>
  27
  28 namespace clang::include_cleaner {
  29 namespace {
  30
  31 constexpr llvm::StringLiteral CSS = R"css(
  32   body { margin: 0; }
  33   pre { line-height: 1.5em; counter-reset: line; margin: 0; }
  34   pre .line:not(.added) { counter-increment: line; }
  35   pre .line::before {
  36     content: counter(line);
  37     display: inline-block;
  38     background-color: #eee; border-right: 1px solid #ccc;
  39     text-align: right;
  40     width: 3em; padding-right: 0.5em; margin-right: 0.5em;
  41   }
  42   pre .line.added::before { content: '+' }
  43   .ref, .inc { text-decoration: underline; color: #008; }
  44   .sel { position: relative; cursor: pointer; }
  45   .ref.implicit { background-color: #ff8; }
  46   #hover {
  47     color: black;
  48     background-color: #aaccff; border: 1px solid #444;
  49     z-index: 1;
  50     position: absolute; top: 100%; left: 0;
  51     font-family: sans-serif;
  52     padding: 0.5em;
  53   }
  54   #hover p, #hover pre { margin: 0; }
  55   #hover .target.implicit, .provides .implicit { background-color: #bbb; }
  56   #hover .target.ambiguous, .provides .ambiguous { background-color: #caf; }
  57   .missing, .unused { background-color: #faa !important; }
  58   .inserted { background-color: #bea !important; }
  59   .semiused { background-color: #888 !important; }
  60   #hover th { color: #008; text-align: right; padding-right: 0.5em; }
  61   #hover .target:not(:first-child) {
  62     margin-top: 1em;
  63     padding-top: 1em;
  64     border-top: 1px solid #444;
  65   }
  66   .ref.missing #hover .insert { background-color: #bea; }
  67   .ref:not(.missing) #hover .insert { font-style: italic; }
  68 )css";
  69
  70 constexpr llvm::StringLiteral JS = R"js(
  71   // Recreate the #hover div inside whichever target .sel element was clicked.
  72   function select(event) {
  73     var target = event.target.closest('.sel');
  74     var hover = document.getElementById('hover');
  75     if (hover) {
  76       if (hover.parentElement == target) return;
  77       hover.parentNode.removeChild(hover);
  78     }
  79     if (target == null) return;
  80     hover = document.createElement('div');
  81     hover.id = 'hover';
  82     fillHover(hover, target);
  83     target.appendChild(hover);
  84   }
  85   // Fill the #hover div with the templates named by data-hover in the target.
  86   function fillHover(hover, target) {
  87     target.dataset.hover?.split(',').forEach(function(id) {
  88       for (c of document.getElementById(id).content.childNodes)
  89         hover.appendChild(c.cloneNode(true));
  90     })
  91   }
  92 )js";
  93
  94 // Categorize the symbol, like FunctionDecl or Macro
  95 llvm::StringRef describeSymbol(const Symbol &Sym) {
  96   switch (Sym.kind()) {
  97   case Symbol::Declaration:
  98     return Sym.declaration().getDeclKindName();
  99   case Symbol::Macro:
 100     return "Macro";
 101   }
 102   llvm_unreachable("unhandled symbol kind");
 103 }
 104
 105 // Return detailed symbol description (declaration), if we have any.
 106 std::string printDetails(const Symbol &Sym) {
 107   std::string S;
 108   if (Sym.kind() == Symbol::Declaration) {
 109     // Print the declaration of the symbol, e.g. to disambiguate overloads.
 110     const auto &D = Sym.declaration();
 111     PrintingPolicy PP = D.getASTContext().getPrintingPolicy();
 112     PP.FullyQualifiedName = true;
 113     PP.TerseOutput = true;
 114     PP.SuppressInitializers = true;
 115     llvm::raw_string_ostream SS(S);
 116     D.print(SS, PP);
 117   }
 118   return S;
 119 }
 120
 121 llvm::StringRef refType(RefType T) {
 122   switch (T) {
 123   case RefType::Explicit:
 124     return "explicit";
 125   case RefType::Implicit:
 126     return "implicit";
 127   case RefType::Ambiguous:
 128     return "ambiguous";
 129   }
 130   llvm_unreachable("unhandled RefType enum");
 131 }
 132
 133 class Reporter {
 134   llvm::raw_ostream &OS;
 135   const ASTContext &Ctx;
 136   const SourceManager &SM;
 137   const HeaderSearch &HS;
 138   const include_cleaner::Includes &Includes;
 139   const PragmaIncludes *PI;
 140   FileID MainFile;
 141   const FileEntry *MainFE;
 142
 143   // Points within the main file that reference a Symbol.
 144   // Implicit refs will be marked with a symbol just before the token.
 145   struct Ref {
 146     unsigned Offset;
 147     RefType Type;
 148     Symbol Sym;
 149     SmallVector<SymbolLocation> Locations = {};
 150     SmallVector<Header> Headers = {};
 151     SmallVector<const Include *> Includes = {};
 152     bool Satisfied = false;  // Is the include present?
 153     std::string Insert = {}; // If we had no includes, what would we insert?
 154   };
 155   std::vector<Ref> Refs;
 156   llvm::DenseMap<const Include *, std::vector<unsigned>> IncludeRefs;
 157   llvm::StringMap<std::vector</*RefIndex*/ unsigned>> Insertion;
 158
 159   llvm::StringRef includeType(const Include *I) {
 160     auto &List = IncludeRefs[I];
 161     if (List.empty())
 162       return "unused";
 163     if (llvm::any_of(List, [&](unsigned I) {
 164           return Refs[I].Type == RefType::Explicit;
 165         }))
 166       return "used";
 167     return "semiused";
 168   }
 169
 170   std::string spellHeader(const Header &H) {
 171     switch (H.kind()) {
 172     case Header::Physical: {
 173       bool IsAngled = false;
 174       std::string Path = HS.suggestPathToFileForDiagnostics(
 175           H.physical(), MainFE->tryGetRealPathName(), &IsAngled);
 176       return IsAngled ? "<" + Path + ">" : "\"" + Path + "\"";
 177     }
 178     case Header::Standard:
 179       return H.standard().name().str();
 180     case Header::Verbatim:
 181       return H.verbatim().str();
 182     }
 183     llvm_unreachable("Unknown Header kind");
 184   }
 185
 186   void fillTarget(Ref &R) {
 187     // Duplicates logic from walkUsed(), which doesn't expose SymbolLocations.
 188     for (auto &Loc : locateSymbol(R.Sym))
 189       R.Locations.push_back(Loc);
 190     R.Headers = headersForSymbol(R.Sym, SM, PI);
 191
 192     for (const auto &H : R.Headers) {
 193       R.Includes.append(Includes.match(H));
 194       // FIXME: library should signal main-file refs somehow.
 195       // Non-physical refs to the main-file should be possible.
 196       if (H.kind() == Header::Physical && H.physical() == MainFE)
 197         R.Satisfied = true;
 198     }
 199     if (!R.Includes.empty())
 200       R.Satisfied = true;
 201     // Include pointers are meaningfully ordered as they are backed by a vector.
 202     llvm::sort(R.Includes);
 203     R.Includes.erase(std::unique(R.Includes.begin(), R.Includes.end()),
 204                      R.Includes.end());
 205
 206     if (!R.Headers.empty())
 207       R.Insert = spellHeader(R.Headers.front());
 208   }
 209
 210 public:
 211   Reporter(llvm::raw_ostream &OS, ASTContext &Ctx, const HeaderSearch &HS,
 212            const include_cleaner::Includes &Includes, const PragmaIncludes *PI,
 213            FileID MainFile)
 214       : OS(OS), Ctx(Ctx), SM(Ctx.getSourceManager()), HS(HS),
 215         Includes(Includes), PI(PI), MainFile(MainFile),
 216         MainFE(SM.getFileEntryForID(MainFile)) {}
 217
 218   void addRef(const SymbolReference &SR) {
 219     auto [File, Offset] = SM.getDecomposedLoc(SM.getFileLoc(SR.RefLocation));
 220     if (File != this->MainFile) {
 221       // Can get here e.g. if there's an #include inside a root Decl.
 222       // FIXME: do something more useful than this.
 223       llvm::errs() << "Ref location outside file! " << SR.Target << " at "
 224                    << SR.RefLocation.printToString(SM) << "\n";
 225       return;
 226     }
 227
 228     int RefIndex = Refs.size();
 229     Refs.emplace_back(Ref{Offset, SR.RT, SR.Target});
 230     Ref &R = Refs.back();
 231     fillTarget(R);
 232     for (const auto *I : R.Includes)
 233       IncludeRefs[I].push_back(RefIndex);
 234     if (R.Type == RefType::Explicit && !R.Satisfied && !R.Insert.empty())
 235       Insertion[R.Insert].push_back(RefIndex);
 236   }
 237
 238   void write() {
 239     OS << "<!doctype html>\n";
 240     OS << "<html>\n";
 241     OS << "<head>\n";
 242     OS << "<style>" << CSS << "</style>\n";
 243     OS << "<script>" << JS << "</script>\n";
 244     for (const auto &Ins : Insertion) {
 245       OS << "<template id='i";
 246       escapeString(Ins.first());
 247       OS << "'>";
 248       writeInsertion(Ins.first(), Ins.second);
 249       OS << "</template>\n";
 250     }
 251     for (auto &Inc : Includes.all()) {
 252       OS << "<template id='i" << Inc.Line << "'>";
 253       writeInclude(Inc);
 254       OS << "</template>\n";
 255     }
 256     for (unsigned I = 0; I < Refs.size(); ++I) {
 257       OS << "<template id='t" << I << "'>";
 258       writeTarget(Refs[I]);
 259       OS << "</template>\n";
 260     }
 261     OS << "</head>\n";
 262     OS << "<body>\n";
 263     writeCode();
 264     OS << "</body>\n";
 265     OS << "</html>\n";
 266   }
 267
 268 private:
 269   void escapeChar(char C) {
 270     switch (C) {
 271     case '<':
 272       OS << "&lt;";
 273       break;
 274     case '&':
 275       OS << "&amp;";
 276       break;
 277     default:
 278       OS << C;
 279     }
 280   }
 281
 282   void escapeString(llvm::StringRef S) {
 283     for (char C : S)
 284       escapeChar(C);
 285   }
 286
 287   // Abbreviate a path ('path/to/Foo.h') to just the filename ('Foo.h').
 288   // The full path is available on hover.
 289   void printFilename(llvm::StringRef Path) {
 290     llvm::StringRef File = llvm::sys::path::filename(Path);
 291     if (File == Path)
 292       return escapeString(Path);
 293     OS << "<span title='";
 294     escapeString(Path);
 295     OS << "'>";
 296     escapeString(File);
 297     OS << "</span>";
 298   }
 299
 300   // Print a source location in compact style.
 301   void printSourceLocation(SourceLocation Loc) {
 302     if (Loc.isInvalid())
 303       return escapeString("<invalid>");
 304     if (!Loc.isMacroID())
 305       return printFilename(Loc.printToString(SM));
 306
 307     // Replicating printToString() is a bit simpler than parsing/reformatting.
 308     printFilename(SM.getExpansionLoc(Loc).printToString(SM));
 309     OS << " &lt;Spelling=";
 310     printFilename(SM.getSpellingLoc(Loc).printToString(SM));
 311     OS << ">";
 312   }
 313
 314   // Write "Provides: " rows of an include or include-insertion table.
 315   // These describe the symbols the header provides, referenced by RefIndices.
 316   void writeProvides(llvm::ArrayRef<unsigned> RefIndices) {
 317     // We show one ref for each symbol: first by (RefType != Explicit, Sequence)
 318     llvm::DenseMap<Symbol, /*RefIndex*/ unsigned> FirstRef;
 319     for (unsigned RefIndex : RefIndices) {
 320       const Ref &R = Refs[RefIndex];
 321       auto I = FirstRef.try_emplace(R.Sym, RefIndex);
 322       if (!I.second && R.Type == RefType::Explicit &&
 323           Refs[I.first->second].Type != RefType::Explicit)
 324         I.first->second = RefIndex;
 325     }
 326     std::vector<std::pair<Symbol, unsigned>> Sorted = {FirstRef.begin(),
 327                                                        FirstRef.end()};
 328     llvm::stable_sort(Sorted, llvm::less_second{});
 329     for (auto &[S, RefIndex] : Sorted) {
 330       auto &R = Refs[RefIndex];
 331       OS << "<tr class='provides'><th>Provides</td><td>";
 332       std::string Details = printDetails(S);
 333       if (!Details.empty()) {
 334         OS << "<span class='" << refType(R.Type) << "' title='";
 335         escapeString(Details);
 336         OS << "'>";
 337       }
 338       escapeString(llvm::to_string(S));
 339       if (!Details.empty())
 340         OS << "</span>";
 341
 342       unsigned Line = SM.getLineNumber(MainFile, R.Offset);
 343       OS << ", <a href='#line" << Line << "'>line " << Line << "</a>";
 344       OS << "</td></tr>";
 345     }
 346   }
 347
 348   void writeInclude(const Include &Inc) {
 349     OS << "<table class='include'>";
 350     if (Inc.Resolved) {
 351       OS << "<tr><th>Resolved</td><td>";
 352       escapeString(Inc.Resolved->getName());
 353       OS << "</td></tr>\n";
 354       writeProvides(IncludeRefs[&Inc]);
 355     }
 356     OS << "</table>";
 357   }
 358
 359   void writeInsertion(llvm::StringRef Text, llvm::ArrayRef<unsigned> Refs) {
 360     OS << "<table class='insertion'>";
 361     writeProvides(Refs);
 362     OS << "</table>";
 363   }
 364
 365   void writeTarget(const Ref &R) {
 366     OS << "<table class='target " << refType(R.Type) << "'>";
 367
 368     OS << "<tr><th>Symbol</th><td>";
 369     OS << describeSymbol(R.Sym) << " <code>";
 370     escapeString(llvm::to_string(R.Sym));
 371     OS << "</code></td></tr>\n";
 372
 373     std::string Details = printDetails(R.Sym);
 374     if (!Details.empty()) {
 375       OS << "<tr><td></td><td><code>";
 376       escapeString(Details);
 377       OS << "</code></td></tr>\n";
 378     }
 379
 380     for (const auto &Loc : R.Locations) {
 381       OS << "<tr><th>Location</th><td>";
 382       if (Loc.kind() == SymbolLocation::Physical) // needs SM to print properly.
 383         printSourceLocation(Loc.physical());
 384       else
 385         escapeString(llvm::to_string(Loc));
 386       OS << "</td></tr>\n";
 387     }
 388
 389     for (const auto &H : R.Headers) {
 390       OS << "<tr><th>Header</th><td>";
 391       switch (H.kind()) {
 392       case Header::Physical:
 393         printFilename(H.physical().getName());
 394         break;
 395       case Header::Standard:
 396         OS << "stdlib " << H.standard().name();
 397         break;
 398       case Header::Verbatim:
 399         OS << "verbatim ";
 400         escapeString(H.verbatim());
 401         break;
 402       }
 403       OS << "</td></tr>\n";
 404     }
 405
 406     for (const auto *I : R.Includes) {
 407       OS << "<tr><th>Included</th><td>";
 408       escapeString(I->quote());
 409       OS << ", <a href='#line" << I->Line << "'>line " << I->Line << "</a>";
 410       OS << "</td></tr>";
 411     }
 412
 413     if (!R.Insert.empty()) {
 414       OS << "<tr><th>Insert</th><td class='insert'>";
 415       escapeString(R.Insert);
 416       OS << "</td></tr>";
 417     }
 418
 419     OS << "</table>";
 420   }
 421
 422   void writeCode() {
 423     llvm::StringRef Code = SM.getBufferData(MainFile);
 424
 425     OS << "<pre onclick='select(event)' class='code'>";
 426
 427     std::vector<llvm::StringRef> Insertions{Insertion.keys().begin(),
 428                                             Insertion.keys().end()};
 429     llvm::sort(Insertions);
 430     for (llvm::StringRef Insertion : Insertions) {
 431       OS << "<code class='line added'>"
 432          << "<span class='inc sel inserted' data-hover='i";
 433       escapeString(Insertion);
 434       OS << "'>#include ";
 435       escapeString(Insertion);
 436       OS << "</span></code>\n";
 437     }
 438
 439     const Include *Inc = nullptr;
 440     unsigned LineNum = 0;
 441     // Lines are <code>, include lines have an inner <span>.
 442     auto StartLine = [&] {
 443       ++LineNum;
 444       OS << "<code class='line' id='line" << LineNum << "'>";
 445       if ((Inc = Includes.atLine(LineNum)))
 446         OS << "<span class='inc sel " << includeType(Inc) << "' data-hover='i"
 447            << Inc->Line << "'>";
 448     };
 449     auto EndLine = [&] {
 450       if (Inc)
 451         OS << "</span>";
 452       OS << "</code>\n";
 453     };
 454
 455     std::vector<unsigned> RefOrder(Refs.size());
 456     std::iota(RefOrder.begin(), RefOrder.end(), 0);
 457     llvm::stable_sort(RefOrder, [&](unsigned A, unsigned B) {
 458       return std::make_pair(Refs[A].Offset, Refs[A].Type != RefType::Implicit) <
 459              std::make_pair(Refs[B].Offset, Refs[B].Type != RefType::Implicit);
 460     });
 461     auto Rest = llvm::ArrayRef(RefOrder);
 462     unsigned End = 0;
 463     StartLine();
 464     for (unsigned I = 0; I < Code.size(); ++I) {
 465       // Finish refs early at EOL to avoid dealing with splitting the span.
 466       if (End && (End == I || Code[I] == '\n')) {
 467         OS << "</span>";
 468         End = 0;
 469       }
 470       // Handle implicit refs, which are rendered *before* the token.
 471       while (!Rest.empty() && Refs[Rest.front()].Offset == I &&
 472              Refs[Rest.front()].Type == RefType::Implicit) {
 473         const Ref &R = Refs[Rest.front()];
 474         OS << "<span class='ref sel implicit "
 475            << (R.Satisfied ? "satisfied" : "missing") << "' data-hover='t"
 476            << Rest.front() << "'>&loz;</span>";
 477         Rest = Rest.drop_front();
 478       };
 479       // Accumulate all explicit refs that appear on the same token.
 480       std::string TargetList;
 481       bool Unsatisfied = false;
 482       Rest = Rest.drop_while([&](unsigned RefIndex) {
 483         const Ref &R = Refs[RefIndex];
 484         if (R.Offset != I)
 485           return false;
 486         if (!TargetList.empty())
 487           TargetList.push_back(',');
 488         TargetList.push_back('t');
 489         TargetList.append(std::to_string(RefIndex));
 490         Unsatisfied = Unsatisfied || !R.Satisfied;
 491         return true;
 492       });
 493       if (!TargetList.empty()) {
 494         assert(End == 0 && "Overlapping tokens!");
 495         OS << "<span class='ref sel" << (Unsatisfied ? " missing" : "")
 496            << "' data-hover='" << TargetList << "'>";
 497         End = I + Lexer::MeasureTokenLength(SM.getComposedLoc(MainFile, I), SM,
 498                                             Ctx.getLangOpts());
 499       }
 500       if (Code[I] == '\n') {
 501         EndLine();
 502         StartLine();
 503       } else
 504         escapeChar(Code[I]);
 505     }
 506     EndLine();
 507     OS << "</pre>\n";
 508   }
 509 };
 510
 511 } // namespace
 512
 513 void writeHTMLReport(FileID File, const include_cleaner::Includes &Includes,
 514                      llvm::ArrayRef<Decl *> Roots,
 515                      llvm::ArrayRef<SymbolReference> MacroRefs, ASTContext &Ctx,
 516                      const HeaderSearch &HS, PragmaIncludes *PI,
 517                      llvm::raw_ostream &OS) {
 518   Reporter R(OS, Ctx, HS, Includes, PI, File);
 519   const auto& SM = Ctx.getSourceManager();
 520   for (Decl *Root : Roots)
 521     walkAST(*Root, [&](SourceLocation Loc, const NamedDecl &D, RefType T) {
 522       if(!SM.isWrittenInMainFile(SM.getSpellingLoc(Loc)))
 523         return;
 524       R.addRef(SymbolReference{D, Loc, T});
 525     });
 526   for (const SymbolReference &Ref : MacroRefs) {
 527     if (!SM.isWrittenInMainFile(SM.getSpellingLoc(Ref.RefLocation)))
 528       continue;
 529     R.addRef(Ref);
 530   }
 531   R.write();
 532 }
 533
 534 } // namespace clang::include_cleaner