llvm-project

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
535