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"
73#include "HTMLLogger.inc"
79llvm::Expected<std::string> renderSVG(llvm::StringRef DotGraph);
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)
96 switch (
V.getKind()) {
108 for (
const auto& Prop :
V.properties())
109 JOS.attributeObject((
"p:" + Prop.first()).str(),
110 [&] { dump(*Prop.second); });
114 if (
auto *B = llvm::dyn_cast<BoolValue>(&
V)) {
115 JOS.attribute(
"formula", llvm::to_string(B->formula()));
116 JOS.attribute(
"truth", Env.proves(B->formula()) ?
"true"
117 : Env.proves(Env.arena().makeNot(B->formula()))
122 void dump(
const StorageLocation &L) {
123 JOS.attribute(
"location", llvm::to_string(&L));
124 if (!Visited.insert(&L).second)
127 JOS.attribute(
"type", L.getType().getAsString());
128 if (!L.getType()->isRecordType())
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(), [&] {
139 for (
const auto &SyntheticField : RLoc->synthetic_fields())
140 JOS.attributeObject((
"sf:" + SyntheticField.first()).str(),
141 [&] { dump(*SyntheticField.second); });
145 llvm::DenseSet<const void*> Visited;
146 llvm::json::OStream &JOS;
147 const Environment &Env;
150class HTMLLogger :
public Logger {
152 const CFGBlock *Block;
158 StreamFactory Streams;
159 std::unique_ptr<llvm::raw_ostream> OS;
161 llvm::raw_string_ostream JStringStream{JSON};
162 llvm::json::OStream JOS{JStringStream, 2};
164 const AdornedCFG *ACFG;
166 std::vector<Iteration> Iters;
168 llvm::DenseMap<const CFGBlock *, llvm::SmallVector<size_t>> BlockIters;
170 llvm::BitVector BlockConverged;
172 std::string ContextLogs;
174 unsigned ElementIndex;
177 explicit HTMLLogger(StreamFactory Streams) : Streams(std::move(Streams)) {}
178 void beginAnalysis(
const AdornedCFG &ACFG,
179 TypeErasedDataflowAnalysis &A)
override {
182 *OS << llvm::StringRef(HTMLLogger_html).split(
"<?INJECT?>").first;
184 BlockConverged.resize(ACFG.getCFG().getNumBlockIDs());
186 const auto &D = ACFG.getDecl();
187 const auto &
SM = A.getASTContext().getSourceManager();
189 if (
const auto *ND = dyn_cast<NamedDecl>(&D))
190 *OS << ND->getNameAsString() <<
" at ";
191 *OS <<
SM.getFilename(D.getLocation()) <<
":"
192 <<
SM.getSpellingLineNumber(D.getLocation());
195 *OS <<
"<style>" << HTMLLogger_css <<
"</style>\n";
196 *OS <<
"<script>" << HTMLLogger_js <<
"</script>\n";
200 JOS.attributeBegin(
"states");
205 void endAnalysis()
override {
209 JOS.attributeArray(
"timeline", [&] {
210 for (
const auto &E : Iters) {
212 JOS.attribute(
"block", blockID(E.Block->getBlockID()));
213 JOS.attribute(
"iter", E.Iter);
214 JOS.attribute(
"post_visit", E.PostVisit);
215 JOS.attribute(
"converged", E.Converged);
219 JOS.attributeObject(
"cfg", [&] {
220 for (
const auto &E : BlockIters)
221 writeBlock(*E.first, E.second);
228 *OS <<
"<script>var HTMLLoggerData = \n";
230 *OS <<
";\n</script>\n";
231 *OS << llvm::StringRef(HTMLLogger_html).split(
"<?INJECT?>").second;
234 void enterBlock(
const CFGBlock &B,
bool PostVisit)
override {
235 llvm::SmallVector<size_t> &BIter = BlockIters[&B];
236 unsigned IterNum = BIter.size() + 1;
237 BIter.push_back(Iters.size());
238 Iters.push_back({&B, IterNum, PostVisit,
false});
240 BlockConverged[B.getBlockID()] =
false;
243 void enterElement(
const CFGElement &E)
override {
247 static std::string blockID(
unsigned Block) {
248 return llvm::formatv(
"B{0}",
Block);
250 static std::string eltID(
unsigned Block,
unsigned Element) {
251 return llvm::formatv(
"B{0}.{1}",
Block, Element);
253 static std::string iterID(
unsigned Block,
unsigned Iter) {
254 return llvm::formatv(
"B{0}:{1}",
Block, Iter);
256 static std::string elementIterID(
unsigned Block,
unsigned Iter,
258 return llvm::formatv(
"B{0}:{1}_B{0}.{2}",
Block, Iter, Element);
267 void recordState(TypeErasedDataflowAnalysisState &State)
override {
268 unsigned Block = Iters.back().Block->getBlockID();
269 unsigned Iter = Iters.back().Iter;
270 bool PostVisit = Iters.back().PostVisit;
271 JOS.attributeObject(elementIterID(
Block, Iter, ElementIndex), [&] {
272 JOS.attribute(
"block", blockID(
Block));
273 JOS.attribute(
"iter", Iter);
274 JOS.attribute(
"post_visit", PostVisit);
275 JOS.attribute(
"element", ElementIndex);
278 if (ElementIndex > 0) {
280 Iters.back().Block->Elements[ElementIndex - 1].getAs<CFGStmt>();
281 if (
const Expr *E = S ? llvm::dyn_cast<Expr>(S->getStmt()) :
nullptr) {
282 if (E->isPRValue()) {
283 if (!E->getType()->isRecordType())
284 if (
auto *
V = State.Env.getValue(*E))
286 "value", [&] { ModelDumper(JOS, State.Env).dump(*
V); });
288 if (
auto *Loc = State.Env.getStorageLocation(*E))
290 "value", [&] { ModelDumper(JOS, State.Env).dump(*Loc); });
294 if (!ContextLogs.empty()) {
295 JOS.attribute(
"logs", ContextLogs);
299 std::string BuiltinLattice;
300 llvm::raw_string_ostream BuiltinLatticeS(BuiltinLattice);
301 State.Env.dump(BuiltinLatticeS);
302 JOS.attribute(
"builtinLattice", BuiltinLattice);
306 void blockConverged()
override {
307 Iters.back().Converged =
true;
308 BlockConverged[Iters.back().Block->getBlockID()] =
true;
311 void logText(llvm::StringRef S)
override {
312 ContextLogs.append(S.begin(), S.end());
313 ContextLogs.push_back(
'\n');
320 void writeBlock(
const CFGBlock &B, llvm::ArrayRef<size_t> ItersForB) {
321 JOS.attributeObject(blockID(B.getBlockID()), [&] {
322 JOS.attributeArray(
"iters", [&] {
323 for (size_t IterIdx : ItersForB) {
324 const Iteration &Iter = Iters[IterIdx];
326 JOS.attribute(
"iter", Iter.Iter);
327 JOS.attribute(
"post_visit", Iter.PostVisit);
328 JOS.attribute(
"converged", Iter.Converged);
332 JOS.attributeArray(
"elements", [&] {
333 for (
const auto &Elt : B.Elements) {
335 llvm::raw_string_ostream DumpS(Dump);
336 Elt.dumpToStream(DumpS);
348 const auto &AST = ACFG->getDecl().getASTContext();
357 AST.getSourceManager(), AST.getLangOpts());
358 if (
Range.isInvalid())
361 Range, AST.getSourceManager(), AST.getLangOpts(), &
Invalid);
367 enum :
unsigned { Missing =
static_cast<unsigned>(-1) };
371 unsigned BB = Missing;
372 unsigned BBPriority = 0;
374 unsigned Elt = Missing;
375 unsigned EltPriority = 0;
377 SmallVector<unsigned> Elts;
385 void assign(
unsigned BB,
unsigned Elt,
unsigned RangeLen) {
387 if (this->BB != Missing && BB != this->BB && BBPriority <= RangeLen)
389 if (BB != this->BB) {
392 BBPriority = RangeLen;
394 BBPriority = std::min(BBPriority, RangeLen);
396 if (this->Elt == Missing || EltPriority > RangeLen)
399 bool operator==(
const TokenInfo &Other)
const {
400 return std::tie(BB, Elt, Elts) ==
404 void write(llvm::raw_ostream &OS)
const {
407 OS <<
" " << blockID(BB);
408 for (
unsigned Elt : Elts)
409 OS <<
" " << eltID(BB, Elt);
413 OS <<
" data-elt='" << eltID(BB, Elt) <<
"'";
415 OS <<
" data-bb='" << blockID(BB) <<
"'";
421 std::vector<TokenInfo> State(Code.size());
422 for (
const auto *
Block : ACFG->getCFG()) {
423 unsigned EltIndex = 0;
424 for (
const auto& Elt : *
Block) {
426 if (
const auto S = Elt.getAs<CFGStmt>()) {
429 AST.getSourceManager(), AST.getLangOpts());
430 if (EltRange.isInvalid())
432 if (EltRange.getBegin() <
Range.getBegin() ||
433 EltRange.getEnd() >=
Range.getEnd() ||
434 EltRange.getEnd() <
Range.getBegin() ||
435 EltRange.getEnd() >=
Range.getEnd())
437 unsigned Off = EltRange.getBegin().getRawEncoding() -
438 Range.getBegin().getRawEncoding();
439 unsigned Len = EltRange.getEnd().getRawEncoding() -
440 EltRange.getBegin().getRawEncoding();
441 for (
unsigned I = 0; I < Len; ++I)
442 State[Off + I].assign(
Block->getBlockID(), EltIndex, Len);
449 AST.getSourceManager().getSpellingLineNumber(
Range.getBegin());
450 *
OS <<
"<template data-copy='code'>\n";
451 *
OS <<
"<code class='filename'>";
452 llvm::printHTMLEscaped(
453 llvm::sys::path::filename(
454 AST.getSourceManager().getFilename(
Range.getBegin())),
457 *
OS <<
"<code class='line' data-line='" <<
Line++ <<
"'>";
458 for (
unsigned I = 0; I < Code.size(); ++I) {
461 bool NeedOpen = I == 0 || !(State[I] == State[I-1]);
462 bool NeedClose = I + 1 == Code.size() || !(State[I] == State[I + 1]);
469 *
OS <<
"</code>\n<code class='line' data-line='" <<
Line++ <<
"'>";
471 llvm::printHTMLEscaped(Code.substr(I, 1), *OS);
472 if (NeedClose) *
OS <<
"</span>";
475 *
OS <<
"</template>";
482 *
OS <<
"<template data-copy='cfg'>\n";
483 if (
auto SVG = renderSVG(buildCFGDot(ACFG->getCFG())))
486 *
OS <<
"Can't draw CFG: " <<
toString(SVG.takeError());
487 *
OS <<
"</template>\n";
491 std::string buildCFGDot(
const clang::CFG &CFG) {
493 llvm::raw_string_ostream GraphS(Graph);
495 GraphS << R
"(digraph {
497 node[class=bb, shape=square, fontname="sans-serif", tooltip=" "]
501 std::string Name = blockID(I);
503 const char *ConvergenceMarker = (
const char *)u8
"\\n\u2192\u007c";
504 if (BlockConverged[I])
505 Name += ConvergenceMarker;
506 GraphS <<
" " << blockID(I) <<
" [id=" << blockID(I) <<
" label=\""
509 for (
const auto *
Block : CFG) {
510 for (
const auto &Succ :
Block->succs()) {
511 if (Succ.getReachableBlock())
512 GraphS <<
" " << blockID(
Block->getBlockID()) <<
" -> "
513 << blockID(Succ.getReachableBlock()->getBlockID()) <<
"\n";
522llvm::Expected<std::string> renderSVG(llvm::StringRef DotGraph) {
524 if (
const auto *FromEnv = ::getenv(
"GRAPHVIZ_DOT"))
527 auto FromPath = llvm::sys::findProgramByName(
"dot");
529 return llvm::createStringError(FromPath.getError(),
530 "'dot' not found on PATH");
531 DotPath = FromPath.get();
536 llvm::SmallString<256> Input, Output;
538 if (
auto EC = llvm::sys::fs::createTemporaryFile(
"analysis",
".dot", InputFD,
540 return llvm::createStringError(EC,
"failed to create `dot` temp input");
541 llvm::raw_fd_ostream(InputFD,
true) << DotGraph;
543 llvm::make_scope_exit([&] { llvm::sys::fs::remove(Input); });
544 if (
auto EC = llvm::sys::fs::createTemporaryFile(
"analysis",
".svg", Output))
545 return llvm::createStringError(EC,
"failed to create `dot` temp output");
547 llvm::make_scope_exit([&] { llvm::sys::fs::remove(Output); });
549 std::vector<std::optional<llvm::StringRef>> Redirects = {
553 int Code = llvm::sys::ExecuteAndWait(
554 DotPath, {
"dot",
"-Tsvg"}, std::nullopt, Redirects,
557 return llvm::createStringError(llvm::inconvertibleErrorCode(),
558 "'dot' failed: " + ErrMsg);
560 return llvm::createStringError(llvm::inconvertibleErrorCode(),
561 "'dot' failed (" + llvm::Twine(Code) +
")");
563 auto Buf = llvm::MemoryBuffer::getFile(Output);
565 return llvm::createStringError(Buf.getError(),
"Can't read `dot` output");
568 llvm::StringRef
Result = Buf.get()->getBuffer();
569 auto Pos =
Result.find(
"<svg");
570 if (Pos == llvm::StringRef::npos)
571 return llvm::createStringError(llvm::inconvertibleErrorCode(),
572 "Can't find <svg> tag in `dot` output");
573 return Result.substr(Pos).str();
578std::unique_ptr<Logger>
580 return std::make_unique<HTMLLogger>(std::move(Streams));
static void dump(llvm::raw_ostream &OS, StringRef FunctionName, ArrayRef< CounterExpression > Expressions, ArrayRef< CounterMappingRegion > Regions)
static std::string toString(const clang::SanitizerSet &Sanitizers)
Produce a string containing comma-separated names of sanitizers in Sanitizers set.
Defines the SourceManager interface.
unsigned getNumBlockIDs() const
Returns the total number of BlockIDs allocated (which start at 0).
static CharSourceRange getTokenRange(SourceRange R)
static StringRef getSourceText(CharSourceRange Range, const SourceManager &SM, const LangOptions &LangOpts, bool *Invalid=nullptr)
Returns a string for the source that the range encompasses.
static CharSourceRange makeFileCharRange(CharSourceRange Range, const SourceManager &SM, const LangOptions &LangOpts)
Accepts a range and returns a character range with file locations.
A logger is notified as the analysis progresses.
static std::unique_ptr< Logger > html(std::function< std::unique_ptr< llvm::raw_ostream >()>)
A logger that builds an HTML UI to inspect the analysis results.
Dataflow Directional Tag Classes.
llvm::StringRef debugString(Value::Kind Kind)
Returns a string representation of a value kind.
@ OS
Indicates that the tracking object is a descendant of a referenced-counted OSObject,...
bool Dump(InterpState &S, CodePtr OpPC)
bool operator==(const CallGraphNode::CallRecord &LHS, const CallGraphNode::CallRecord &RHS)
@ Result
The result type of a method or function.
U cast(CodeGen::Address addr)
@ Other
Other implicit parameter.
int const char * function