1 //===-- HTMLLogger.cpp ----------------------------------------------------===//
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
7 //===----------------------------------------------------------------------===//
9 // This file implements the HTML logger. Given a directory dir/, we write
10 // dir/0.html for the first analysis, etc.
11 // These files contain a visualization that allows inspecting the CFG and the
12 // state of the analysis at each point.
13 // Static assets (HTMLLogger.js, HTMLLogger.css) and SVG graphs etc are embedded
14 // so each output file is self-contained.
18 // The timeline and function view are always shown. These allow selecting basic
19 // blocks, statements within them, and processing iterations (BBs are visited
20 // multiple times when e.g. loops are involved).
21 // These are written directly into the HTML body.
23 // There are also listings of particular basic blocks, and dumps of the state
24 // at particular analysis points (i.e. BB2 iteration 3 statement 2).
25 // These are only shown when the relevant BB/analysis point is *selected*.
29 // The HTML proper is mostly static.
30 // The analysis data is in a JSON object HTMLLoggerData which is embedded as
31 // a <script> in the <head>.
32 // This gets rendered into DOM by a simple template processor which substitutes
33 // the data into <template> tags embedded in the HTML. (see inflate() in JS).
37 // This is the only real interactive mechanism.
39 // At any given time, there are several named selections, e.g.:
40 // bb: B2 (basic block 0 is selected)
41 // elt: B2.4 (statement 4 is selected)
42 // iter: B2:1 (iteration 1 of the basic block is selected)
43 // hover: B3 (hovering over basic block 3)
45 // The selection is updated by mouse events: hover by moving the mouse and
46 // others by clicking. Elements that are click targets generally have attributes
47 // (id or data-foo) that define what they should select.
48 // See watchSelection() in JS for the exact logic.
50 // When the "bb" selection is set to "B2":
51 // - sections <section data-selection="bb"> get shown
52 // - templates under such sections get re-rendered
53 // - elements with class/id "B2" get class "bb-select"
55 //===----------------------------------------------------------------------===//
57 #include "clang/Analysis/FlowSensitive/ControlFlowContext.h"
58 #include "clang/Analysis/FlowSensitive/DebugSupport.h"
59 #include "clang/Analysis/FlowSensitive/Logger.h"
60 #include "clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h"
61 #include "clang/Analysis/FlowSensitive/Value.h"
62 #include "clang/Basic/SourceManager.h"
63 #include "clang/Lex/Lexer.h"
64 #include "llvm/ADT/DenseMap.h"
65 #include "llvm/ADT/ScopeExit.h"
66 #include "llvm/Support/Error.h"
67 #include "llvm/Support/FormatVariadic.h"
68 #include "llvm/Support/JSON.h"
69 #include "llvm/Support/Program.h"
70 #include "llvm/Support/ScopedPrinter.h"
71 #include "llvm/Support/raw_ostream.h"
72 // Defines assets: HTMLLogger_{html_js,css}
73 #include "HTMLLogger.inc"
75 namespace clang::dataflow
{
78 // Render a graphviz graph specification to SVG using the `dot` tool.
79 llvm::Expected
<std::string
> renderSVG(llvm::StringRef DotGraph
);
81 using StreamFactory
= std::function
<std::unique_ptr
<llvm::raw_ostream
>()>;
83 // Recursively dumps Values/StorageLocations as JSON
86 ModelDumper(llvm::json::OStream
&JOS
, const Environment
&Env
)
87 : JOS(JOS
), Env(Env
) {}
90 JOS
.attribute("value_id", llvm::to_string(&V
));
91 if (!Visited
.insert(&V
).second
)
94 JOS
.attribute("kind", debugString(V
.getKind()));
96 switch (V
.getKind()) {
97 case Value::Kind::Integer
:
98 case Value::Kind::Record
:
99 case Value::Kind::TopBool
:
100 case Value::Kind::AtomicBool
:
101 case Value::Kind::FormulaBool
:
103 case Value::Kind::Pointer
:
105 "pointee", [&] { dump(cast
<PointerValue
>(V
).getPointeeLoc()); });
109 for (const auto& Prop
: V
.properties())
110 JOS
.attributeObject(("p:" + Prop
.first()).str(),
111 [&] { dump(*Prop
.second
); });
113 // Running the SAT solver is expensive, but knowing which booleans are
114 // guaranteed true/false here is valuable and hard to determine by hand.
115 if (auto *B
= llvm::dyn_cast
<BoolValue
>(&V
)) {
116 JOS
.attribute("formula", llvm::to_string(B
->formula()));
117 JOS
.attribute("truth", Env
.proves(B
->formula()) ? "true"
118 : Env
.proves(Env
.arena().makeNot(B
->formula()))
123 void dump(const StorageLocation
&L
) {
124 JOS
.attribute("location", llvm::to_string(&L
));
125 if (!Visited
.insert(&L
).second
)
128 JOS
.attribute("type", L
.getType().getAsString());
129 if (auto *V
= Env
.getValue(L
))
132 if (auto *RLoc
= dyn_cast
<RecordStorageLocation
>(&L
)) {
133 for (const auto &Child
: RLoc
->children())
134 JOS
.attributeObject("f:" + Child
.first
->getNameAsString(), [&] {
136 if (Value
*Val
= Env
.getValue(*Child
.second
))
142 llvm::DenseSet
<const void*> Visited
;
143 llvm::json::OStream
&JOS
;
144 const Environment
&Env
;
147 class HTMLLogger
: public Logger
{
149 const CFGBlock
*Block
;
155 StreamFactory Streams
;
156 std::unique_ptr
<llvm::raw_ostream
> OS
;
157 std::optional
<llvm::json::OStream
> JOS
;
159 const ControlFlowContext
*CFG
;
160 // Timeline of iterations of CFG block visitation.
161 std::vector
<Iteration
> Iters
;
162 // Indexes in `Iters` of the iterations for each block.
163 llvm::DenseMap
<const CFGBlock
*, llvm::SmallVector
<size_t>> BlockIters
;
164 // The messages logged in the current context but not yet written.
165 std::string ContextLogs
;
166 // The number of elements we have visited within the current CFG block.
167 unsigned ElementIndex
;
170 explicit HTMLLogger(StreamFactory Streams
) : Streams(std::move(Streams
)) {}
171 void beginAnalysis(const ControlFlowContext
&CFG
,
172 TypeErasedDataflowAnalysis
&A
) override
{
175 *OS
<< llvm::StringRef(HTMLLogger_html
).split("<?INJECT?>").first
;
177 const auto &D
= CFG
.getDecl();
178 const auto &SM
= A
.getASTContext().getSourceManager();
180 if (const auto *ND
= dyn_cast
<NamedDecl
>(&D
))
181 *OS
<< ND
->getNameAsString() << " at ";
182 *OS
<< SM
.getFilename(D
.getLocation()) << ":"
183 << SM
.getSpellingLineNumber(D
.getLocation());
186 *OS
<< "<style>" << HTMLLogger_css
<< "</style>\n";
187 *OS
<< "<script>" << HTMLLogger_js
<< "</script>\n";
192 *OS
<< "<script>var HTMLLoggerData = \n";
193 JOS
.emplace(*OS
, /*Indent=*/2);
195 JOS
->attributeBegin("states");
198 // Between beginAnalysis() and endAnalysis() we write all the states for
199 // particular analysis points into the `timeline` array.
200 void endAnalysis() override
{
204 JOS
->attributeArray("timeline", [&] {
205 for (const auto &E
: Iters
) {
207 JOS
->attribute("block", blockID(E
.Block
->getBlockID()));
208 JOS
->attribute("iter", E
.Iter
);
209 JOS
->attribute("post_visit", E
.PostVisit
);
210 JOS
->attribute("converged", E
.Converged
);
214 JOS
->attributeObject("cfg", [&] {
215 for (const auto &E
: BlockIters
)
216 writeBlock(*E
.first
, E
.second
);
221 *OS
<< ";\n</script>\n";
222 *OS
<< llvm::StringRef(HTMLLogger_html
).split("<?INJECT?>").second
;
225 void enterBlock(const CFGBlock
&B
, bool PostVisit
) override
{
226 llvm::SmallVector
<size_t> &BIter
= BlockIters
[&B
];
227 unsigned IterNum
= BIter
.size() + 1;
228 BIter
.push_back(Iters
.size());
229 Iters
.push_back({&B
, IterNum
, PostVisit
, /*Converged=*/false});
232 void enterElement(const CFGElement
&E
) override
{
236 static std::string
blockID(unsigned Block
) {
237 return llvm::formatv("B{0}", Block
);
239 static std::string
eltID(unsigned Block
, unsigned Element
) {
240 return llvm::formatv("B{0}.{1}", Block
, Element
);
242 static std::string
iterID(unsigned Block
, unsigned Iter
) {
243 return llvm::formatv("B{0}:{1}", Block
, Iter
);
245 static std::string
elementIterID(unsigned Block
, unsigned Iter
,
247 return llvm::formatv("B{0}:{1}_B{0}.{2}", Block
, Iter
, Element
);
250 // Write the analysis state associated with a particular analysis point.
251 // FIXME: this dump is fairly opaque. We should show:
252 // - values associated with the current Stmt
253 // - values associated with its children
254 // - meaningful names for values
255 // - which boolean values are implied true/false by the flow condition
256 void recordState(TypeErasedDataflowAnalysisState
&State
) override
{
257 unsigned Block
= Iters
.back().Block
->getBlockID();
258 unsigned Iter
= Iters
.back().Iter
;
259 bool PostVisit
= Iters
.back().PostVisit
;
260 JOS
->attributeObject(elementIterID(Block
, Iter
, ElementIndex
), [&] {
261 JOS
->attribute("block", blockID(Block
));
262 JOS
->attribute("iter", Iter
);
263 JOS
->attribute("post_visit", PostVisit
);
264 JOS
->attribute("element", ElementIndex
);
266 // If this state immediately follows an Expr, show its built-in model.
267 if (ElementIndex
> 0) {
269 Iters
.back().Block
->Elements
[ElementIndex
- 1].getAs
<CFGStmt
>();
270 if (const Expr
*E
= S
? llvm::dyn_cast
<Expr
>(S
->getStmt()) : nullptr) {
271 if (E
->isPRValue()) {
272 if (auto *V
= State
.Env
.getValue(*E
))
273 JOS
->attributeObject(
274 "value", [&] { ModelDumper(*JOS
, State
.Env
).dump(*V
); });
276 if (auto *Loc
= State
.Env
.getStorageLocation(*E
))
277 JOS
->attributeObject(
278 "value", [&] { ModelDumper(*JOS
, State
.Env
).dump(*Loc
); });
282 if (!ContextLogs
.empty()) {
283 JOS
->attribute("logs", ContextLogs
);
287 std::string BuiltinLattice
;
288 llvm::raw_string_ostream
BuiltinLatticeS(BuiltinLattice
);
289 State
.Env
.dump(BuiltinLatticeS
);
290 JOS
->attribute("builtinLattice", BuiltinLattice
);
294 void blockConverged() override
{ Iters
.back().Converged
= true; }
296 void logText(llvm::StringRef S
) override
{
297 ContextLogs
.append(S
.begin(), S
.end());
298 ContextLogs
.push_back('\n');
302 // Write the CFG block details.
303 // Currently this is just the list of elements in execution order.
304 // FIXME: an AST dump would be a useful view, too.
305 void writeBlock(const CFGBlock
&B
, llvm::ArrayRef
<size_t> ItersForB
) {
306 JOS
->attributeObject(blockID(B
.getBlockID()), [&] {
307 JOS
->attributeArray("iters", [&] {
308 for (size_t IterIdx
: ItersForB
) {
309 const Iteration
&Iter
= Iters
[IterIdx
];
311 JOS
->attribute("iter", Iter
.Iter
);
312 JOS
->attribute("post_visit", Iter
.PostVisit
);
313 JOS
->attribute("converged", Iter
.Converged
);
317 JOS
->attributeArray("elements", [&] {
318 for (const auto &Elt
: B
.Elements
) {
320 llvm::raw_string_ostream
DumpS(Dump
);
321 Elt
.dumpToStream(DumpS
);
328 // Write the code of function being examined.
329 // We want to overlay the code with <span>s that mark which BB particular
330 // tokens are associated with, and even which BB element (so that clicking
331 // can select the right element).
333 const auto &AST
= CFG
->getDecl().getASTContext();
334 bool Invalid
= false;
336 // Extract the source code from the original file.
337 // Pretty-printing from the AST would probably be nicer (no macros or
338 // indentation to worry about), but we need the boundaries of particular
339 // AST nodes and the printer doesn't provide this.
340 auto Range
= clang::Lexer::makeFileCharRange(
341 CharSourceRange::getTokenRange(CFG
->getDecl().getSourceRange()),
342 AST
.getSourceManager(), AST
.getLangOpts());
343 if (Range
.isInvalid())
345 llvm::StringRef Code
= clang::Lexer::getSourceText(
346 Range
, AST
.getSourceManager(), AST
.getLangOpts(), &Invalid
);
350 static constexpr unsigned Missing
= -1;
351 // TokenInfo stores the BB and set of elements that a token is part of.
353 // The basic block this is part of.
354 // This is the BB of the stmt with the smallest containing range.
355 unsigned BB
= Missing
;
356 unsigned BBPriority
= 0;
357 // The most specific stmt this is part of (smallest range).
358 unsigned Elt
= Missing
;
359 unsigned EltPriority
= 0;
360 // All stmts this is part of.
361 SmallVector
<unsigned> Elts
;
363 // Mark this token as being part of BB.Elt.
364 // RangeLen is the character length of the element's range, used to
365 // distinguish inner vs outer statements.
366 // For example in `a==0`, token "a" is part of the stmts "a" and "a==0".
367 // However "a" has a smaller range, so is more specific. Clicking on the
368 // token "a" should select the stmt "a".
369 void assign(unsigned BB
, unsigned Elt
, unsigned RangeLen
) {
370 // A worse BB (larger range) => ignore.
371 if (this->BB
!= Missing
&& BB
!= this->BB
&& BBPriority
<= RangeLen
)
373 if (BB
!= this->BB
) {
376 BBPriority
= RangeLen
;
378 BBPriority
= std::min(BBPriority
, RangeLen
);
380 if (this->Elt
== Missing
|| EltPriority
> RangeLen
)
383 bool operator==(const TokenInfo
&Other
) const {
384 return std::tie(BB
, Elt
, Elts
) ==
385 std::tie(Other
.BB
, Other
.Elt
, Other
.Elts
);
387 // Write the attributes for the <span> on this token.
388 void write(llvm::raw_ostream
&OS
) const {
391 OS
<< " " << blockID(BB
);
392 for (unsigned Elt
: Elts
)
393 OS
<< " " << eltID(BB
, Elt
);
397 OS
<< " data-elt='" << eltID(BB
, Elt
) << "'";
399 OS
<< " data-bb='" << blockID(BB
) << "'";
403 // Construct one TokenInfo per character in a flat array.
404 // This is inefficient (chars in a token all have the same info) but simple.
405 std::vector
<TokenInfo
> State(Code
.size());
406 for (const auto *Block
: CFG
->getCFG()) {
407 unsigned EltIndex
= 0;
408 for (const auto& Elt
: *Block
) {
410 if (const auto S
= Elt
.getAs
<CFGStmt
>()) {
411 auto EltRange
= clang::Lexer::makeFileCharRange(
412 CharSourceRange::getTokenRange(S
->getStmt()->getSourceRange()),
413 AST
.getSourceManager(), AST
.getLangOpts());
414 if (EltRange
.isInvalid())
416 if (EltRange
.getBegin() < Range
.getBegin() ||
417 EltRange
.getEnd() >= Range
.getEnd() ||
418 EltRange
.getEnd() < Range
.getBegin() ||
419 EltRange
.getEnd() >= Range
.getEnd())
421 unsigned Off
= EltRange
.getBegin().getRawEncoding() -
422 Range
.getBegin().getRawEncoding();
423 unsigned Len
= EltRange
.getEnd().getRawEncoding() -
424 EltRange
.getBegin().getRawEncoding();
425 for (unsigned I
= 0; I
< Len
; ++I
)
426 State
[Off
+ I
].assign(Block
->getBlockID(), EltIndex
, Len
);
431 // Finally, write the code with the correct <span>s.
433 AST
.getSourceManager().getSpellingLineNumber(Range
.getBegin());
434 *OS
<< "<template data-copy='code'>\n";
435 *OS
<< "<code class='filename'>";
436 llvm::printHTMLEscaped(
437 llvm::sys::path::filename(
438 AST
.getSourceManager().getFilename(Range
.getBegin())),
441 *OS
<< "<code class='line' data-line='" << Line
++ << "'>";
442 for (unsigned I
= 0; I
< Code
.size(); ++I
) {
443 // Don't actually write a <span> around each character, only break spans
444 // when the TokenInfo changes.
445 bool NeedOpen
= I
== 0 || !(State
[I
] == State
[I
-1]);
446 bool NeedClose
= I
+ 1 == Code
.size() || !(State
[I
] == State
[I
+ 1]);
453 *OS
<< "</code>\n<code class='line' data-line='" << Line
++ << "'>";
455 llvm::printHTMLEscaped(Code
.substr(I
, 1), *OS
);
456 if (NeedClose
) *OS
<< "</span>";
459 *OS
<< "</template>";
462 // Write the CFG diagram, a graph of basic blocks.
463 // Laying out graphs is hard, so we construct a graphviz description and shell
464 // out to `dot` to turn it into an SVG.
466 *OS
<< "<template data-copy='cfg'>\n";
467 if (auto SVG
= renderSVG(buildCFGDot(CFG
->getCFG())))
470 *OS
<< "Can't draw CFG: " << toString(SVG
.takeError());
471 *OS
<< "</template>\n";
474 // Produce a graphviz description of a CFG.
475 static std::string
buildCFGDot(const clang::CFG
&CFG
) {
477 llvm::raw_string_ostream
GraphS(Graph
);
478 // Graphviz likes to add unhelpful tooltips everywhere, " " suppresses.
479 GraphS
<< R
"(digraph {
481 node[class=bb, shape=square, fontname="sans
-serif
", tooltip=" "]
484 for (unsigned I
= 0; I
< CFG
.getNumBlockIDs(); ++I
)
485 GraphS
<< " " << blockID(I
) << " [id=" << blockID(I
) << "]\n";
486 for (const auto *Block
: CFG
) {
487 for (const auto &Succ
: Block
->succs()) {
488 if (Succ
.getReachableBlock())
489 GraphS
<< " " << blockID(Block
->getBlockID()) << " -> "
490 << blockID(Succ
.getReachableBlock()->getBlockID()) << "\n";
498 // Nothing interesting here, just subprocess/temp-file plumbing.
499 llvm::Expected
<std::string
> renderSVG(llvm::StringRef DotGraph
) {
501 if (const auto *FromEnv
= ::getenv("GRAPHVIZ_DOT"))
504 auto FromPath
= llvm::sys::findProgramByName("dot");
506 return llvm::createStringError(FromPath
.getError(),
507 "'dot' not found on PATH");
508 DotPath
= FromPath
.get();
511 // Create input and output files for `dot` subprocess.
512 // (We create the output file as empty, to reserve the temp filename).
513 llvm::SmallString
<256> Input
, Output
;
515 if (auto EC
= llvm::sys::fs::createTemporaryFile("analysis", ".dot", InputFD
,
517 return llvm::createStringError(EC
, "failed to create `dot` temp input");
518 llvm::raw_fd_ostream(InputFD
, /*shouldClose=*/true) << DotGraph
;
520 llvm::make_scope_exit([&] { llvm::sys::fs::remove(Input
); });
521 if (auto EC
= llvm::sys::fs::createTemporaryFile("analysis", ".svg", Output
))
522 return llvm::createStringError(EC
, "failed to create `dot` temp output");
524 llvm::make_scope_exit([&] { llvm::sys::fs::remove(Output
); });
526 std::vector
<std::optional
<llvm::StringRef
>> Redirects
= {
528 /*stderr=*/std::nullopt
};
530 int Code
= llvm::sys::ExecuteAndWait(
531 DotPath
, {"dot", "-Tsvg"}, /*Env=*/std::nullopt
, Redirects
,
532 /*SecondsToWait=*/0, /*MemoryLimit=*/0, &ErrMsg
);
534 return llvm::createStringError(llvm::inconvertibleErrorCode(),
535 "'dot' failed: " + ErrMsg
);
537 return llvm::createStringError(llvm::inconvertibleErrorCode(),
538 "'dot' failed (" + llvm::Twine(Code
) + ")");
540 auto Buf
= llvm::MemoryBuffer::getFile(Output
);
542 return llvm::createStringError(Buf
.getError(), "Can't read `dot` output");
544 // Output has <?xml> prefix we don't want. Skip to <svg> tag.
545 llvm::StringRef Result
= Buf
.get()->getBuffer();
546 auto Pos
= Result
.find("<svg");
547 if (Pos
== llvm::StringRef::npos
)
548 return llvm::createStringError(llvm::inconvertibleErrorCode(),
549 "Can't find <svg> tag in `dot` output");
550 return Result
.substr(Pos
).str();
555 std::unique_ptr
<Logger
>
556 Logger::html(std::function
<std::unique_ptr
<llvm::raw_ostream
>()> Streams
) {
557 return std::make_unique
<HTMLLogger
>(std::move(Streams
));
560 } // namespace clang::dataflow