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/Path.h"
70#include "llvm/Support/Program.h"
71#include "llvm/Support/ScopedPrinter.h"
72#include "llvm/Support/raw_ostream.h"
74#include "HTMLLogger.inc"
80llvm::Expected<std::string> renderSVG(llvm::StringRef DotGraph);
87 ModelDumper(llvm::json::OStream &JOS,
const Environment &Env)
88 : JOS(JOS), Env(Env) {}
91 JOS.attribute(
"value_id", llvm::to_string(&
V));
92 if (!Visited.insert(&
V).second)
97 switch (
V.getKind()) {
98 case Value::Kind::Integer:
99 case Value::Kind::TopBool:
100 case Value::Kind::AtomicBool:
101 case Value::Kind::FormulaBool:
103 case Value::Kind::Pointer:
109 for (
const auto& Prop :
V.properties())
110 JOS.attributeObject((
"p:" + Prop.first()).str(),
111 [&] { dump(*Prop.second); });
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 (!L.getType()->isRecordType())
130 if (
auto *
V = Env.getValue(L))
133 if (
auto *RLoc = dyn_cast<RecordStorageLocation>(&L)) {
134 for (
const auto &Child : RLoc->children())
135 JOS.attributeObject(
"f:" + Child.first->getNameAsString(), [&] {
140 for (
const auto &SyntheticField : RLoc->synthetic_fields())
141 JOS.attributeObject((
"sf:" + SyntheticField.first()).str(),
142 [&] { dump(*SyntheticField.second); });
146 llvm::DenseSet<const void*> Visited;
147 llvm::json::OStream &JOS;
148 const Environment &Env;
151class HTMLLogger :
public Logger {
153 const CFGBlock *Block;
159 StreamFactory Streams;
160 std::unique_ptr<llvm::raw_ostream> OS;
162 llvm::raw_string_ostream JStringStream{JSON};
163 llvm::json::OStream JOS{JStringStream, 2};
165 const AdornedCFG *ACFG;
167 std::vector<Iteration> Iters;
169 llvm::DenseMap<const CFGBlock *, llvm::SmallVector<size_t>> BlockIters;
171 llvm::BitVector BlockConverged;
173 std::string ContextLogs;
175 unsigned ElementIndex;
178 explicit HTMLLogger(StreamFactory Streams) : Streams(std::move(Streams)) {}
179 void beginAnalysis(
const AdornedCFG &ACFG,
180 TypeErasedDataflowAnalysis &A)
override {
183 *OS << llvm::StringRef(HTMLLogger_html).split(
"<?INJECT?>").first;
185 BlockConverged.resize(ACFG.getCFG().getNumBlockIDs());
187 const auto &D = ACFG.getDecl();
188 const auto &SM = A.getASTContext().getSourceManager();
190 if (
const auto *ND = dyn_cast<NamedDecl>(&D))
191 *OS << ND->getNameAsString() <<
" at ";
192 *OS << SM.getFilename(D.getLocation()) <<
":"
193 << SM.getSpellingLineNumber(D.getLocation());
196 *OS <<
"<style>" << HTMLLogger_css <<
"</style>\n";
197 *OS <<
"<script>" << HTMLLogger_js <<
"</script>\n";
201 JOS.attributeBegin(
"states");
206 void endAnalysis()
override {
210 JOS.attributeArray(
"timeline", [&] {
211 for (
const auto &E : Iters) {
213 JOS.attribute(
"block", blockID(E.Block->getBlockID()));
214 JOS.attribute(
"iter", E.Iter);
215 JOS.attribute(
"post_visit", E.PostVisit);
216 JOS.attribute(
"converged", E.Converged);
220 JOS.attributeObject(
"cfg", [&] {
221 for (
const auto &E : BlockIters)
222 writeBlock(*E.first, E.second);
229 *OS <<
"<script>var HTMLLoggerData = \n";
231 *OS <<
";\n</script>\n";
232 *OS << llvm::StringRef(HTMLLogger_html).split(
"<?INJECT?>").second;
235 void enterBlock(
const CFGBlock &B,
bool PostVisit)
override {
236 llvm::SmallVector<size_t> &BIter = BlockIters[&B];
237 unsigned IterNum = BIter.size() + 1;
238 BIter.push_back(Iters.size());
239 Iters.push_back({&B, IterNum, PostVisit,
false});
241 BlockConverged[B.getBlockID()] =
false;
244 void enterElement(
const CFGElement &E)
override {
248 static std::string blockID(
unsigned Block) {
249 return llvm::formatv(
"B{0}",
Block);
251 static std::string eltID(
unsigned Block,
unsigned Element) {
252 return llvm::formatv(
"B{0}.{1}",
Block, Element);
254 static std::string iterID(
unsigned Block,
unsigned Iter) {
255 return llvm::formatv(
"B{0}:{1}",
Block, Iter);
257 static std::string elementIterID(
unsigned Block,
unsigned Iter,
259 return llvm::formatv(
"B{0}:{1}_B{0}.{2}",
Block, Iter, Element);
268 void recordState(TypeErasedDataflowAnalysisState &State)
override {
269 unsigned Block = Iters.back().Block->getBlockID();
270 unsigned Iter = Iters.back().Iter;
271 bool PostVisit = Iters.back().PostVisit;
272 JOS.attributeObject(elementIterID(
Block, Iter, ElementIndex), [&] {
273 JOS.attribute(
"block", blockID(
Block));
274 JOS.attribute(
"iter", Iter);
275 JOS.attribute(
"post_visit", PostVisit);
276 JOS.attribute(
"element", ElementIndex);
279 if (ElementIndex > 0) {
281 Iters.back().Block->Elements[ElementIndex - 1].getAs<CFGStmt>();
282 if (
const Expr *E = S ? llvm::dyn_cast<Expr>(S->getStmt()) :
nullptr) {
283 if (E->isPRValue()) {
284 if (!E->getType()->isRecordType())
285 if (
auto *
V = State.Env.getValue(*E))
287 "value", [&] { ModelDumper(JOS, State.Env).dump(*
V); });
289 if (
auto *Loc = State.Env.getStorageLocation(*E))
291 "value", [&] { ModelDumper(JOS, State.Env).dump(*Loc); });
295 if (!ContextLogs.empty()) {
296 JOS.attribute(
"logs", ContextLogs);
300 std::string BuiltinLattice;
301 llvm::raw_string_ostream BuiltinLatticeS(BuiltinLattice);
302 State.Env.dump(BuiltinLatticeS);
303 JOS.attribute(
"builtinLattice", BuiltinLattice);
307 void blockConverged()
override {
308 Iters.back().Converged =
true;
309 BlockConverged[Iters.back().Block->getBlockID()] =
true;
312 void logText(llvm::StringRef S)
override {
313 ContextLogs.append(S.begin(), S.end());
314 ContextLogs.push_back(
'\n');
321 void writeBlock(
const CFGBlock &B, llvm::ArrayRef<size_t> ItersForB) {
322 JOS.attributeObject(blockID(B.getBlockID()), [&] {
323 JOS.attributeArray(
"iters", [&] {
324 for (size_t IterIdx : ItersForB) {
325 const Iteration &Iter = Iters[IterIdx];
327 JOS.attribute(
"iter", Iter.Iter);
328 JOS.attribute(
"post_visit", Iter.PostVisit);
329 JOS.attribute(
"converged", Iter.Converged);
333 JOS.attributeArray(
"elements", [&] {
334 for (
const auto &Elt : B.Elements) {
336 llvm::raw_string_ostream DumpS(Dump);
337 Elt.dumpToStream(DumpS);
349 const auto &AST = ACFG->getDecl().getASTContext();
358 AST.getSourceManager(), AST.getLangOpts());
359 if (
Range.isInvalid())
362 Range, AST.getSourceManager(), AST.getLangOpts(), &
Invalid);
368 enum :
unsigned { Missing =
static_cast<unsigned>(-1) };
372 unsigned BB = Missing;
373 unsigned BBPriority = 0;
375 unsigned Elt = Missing;
376 unsigned EltPriority = 0;
378 SmallVector<unsigned> Elts;
386 void assign(
unsigned BB,
unsigned Elt,
unsigned RangeLen) {
388 if (this->BB != Missing && BB != this->BB && BBPriority <= RangeLen)
390 if (BB != this->BB) {
393 BBPriority = RangeLen;
395 BBPriority = std::min(BBPriority, RangeLen);
397 if (this->Elt == Missing || EltPriority > RangeLen)
400 bool operator==(
const TokenInfo &Other)
const {
401 return std::tie(BB, Elt, Elts) ==
405 void write(llvm::raw_ostream &OS)
const {
408 OS <<
" " << blockID(BB);
409 for (
unsigned Elt : Elts)
410 OS <<
" " << eltID(BB, Elt);
414 OS <<
" data-elt='" << eltID(BB, Elt) <<
"'";
416 OS <<
" data-bb='" << blockID(BB) <<
"'";
422 std::vector<TokenInfo> State(Code.size());
423 for (
const auto *
Block : ACFG->getCFG()) {
424 unsigned EltIndex = 0;
425 for (
const auto& Elt : *
Block) {
427 if (
const auto S = Elt.getAs<CFGStmt>()) {
430 AST.getSourceManager(), AST.getLangOpts());
431 if (EltRange.isInvalid())
433 if (EltRange.getBegin() <
Range.getBegin() ||
434 EltRange.getEnd() >=
Range.getEnd() ||
435 EltRange.getEnd() <
Range.getBegin() ||
436 EltRange.getEnd() >=
Range.getEnd())
438 unsigned Off = EltRange.getBegin().getRawEncoding() -
439 Range.getBegin().getRawEncoding();
440 unsigned Len = EltRange.getEnd().getRawEncoding() -
441 EltRange.getBegin().getRawEncoding();
442 for (
unsigned I = 0; I < Len; ++I)
443 State[
Off + I].assign(
Block->getBlockID(), EltIndex, Len);
450 AST.getSourceManager().getSpellingLineNumber(
Range.getBegin());
451 *
OS <<
"<template data-copy='code'>\n";
452 *
OS <<
"<code class='filename'>";
453 llvm::printHTMLEscaped(
454 llvm::sys::path::filename(
455 AST.getSourceManager().getFilename(
Range.getBegin())),
458 *
OS <<
"<code class='line' data-line='" <<
Line++ <<
"'>";
459 for (
unsigned I = 0; I < Code.size(); ++I) {
462 bool NeedOpen = I == 0 || !(State[I] == State[I-1]);
463 bool NeedClose = I + 1 == Code.size() || !(State[I] == State[I + 1]);
470 *
OS <<
"</code>\n<code class='line' data-line='" <<
Line++ <<
"'>";
472 llvm::printHTMLEscaped(Code.substr(I, 1), *OS);
473 if (NeedClose) *
OS <<
"</span>";
476 *
OS <<
"</template>";
483 *
OS <<
"<template data-copy='cfg'>\n";
484 if (
auto SVG = renderSVG(buildCFGDot(ACFG->getCFG())))
487 *
OS <<
"Can't draw CFG: " <<
toString(SVG.takeError());
488 *
OS <<
"</template>\n";
492 std::string buildCFGDot(
const clang::CFG &CFG) {
494 llvm::raw_string_ostream GraphS(Graph);
496 GraphS << R
"(digraph {
498 node[class=bb, shape=square, fontname="sans-serif", tooltip=" "]
502 std::string Name = blockID(I);
504 const char *ConvergenceMarker = (
const char *)u8
"\\n\u2192\u007c";
505 if (BlockConverged[I])
506 Name += ConvergenceMarker;
507 GraphS <<
" " << blockID(I) <<
" [id=" << blockID(I) <<
" label=\""
510 for (
const auto *
Block : CFG) {
511 for (
const auto &Succ :
Block->succs()) {
512 if (Succ.getReachableBlock())
513 GraphS <<
" " << blockID(
Block->getBlockID()) <<
" -> "
514 << blockID(Succ.getReachableBlock()->getBlockID()) <<
"\n";
523llvm::Expected<std::string> renderSVG(llvm::StringRef DotGraph) {
525 if (
const auto *FromEnv = ::getenv(
"GRAPHVIZ_DOT"))
528 auto FromPath = llvm::sys::findProgramByName(
"dot");
530 return llvm::createStringError(FromPath.getError(),
531 "'dot' not found on PATH");
532 DotPath = FromPath.get();
537 llvm::SmallString<256> Input, Output;
539 if (
auto EC = llvm::sys::fs::createTemporaryFile(
"analysis",
".dot", InputFD,
541 return llvm::createStringError(EC,
"failed to create `dot` temp input");
542 llvm::raw_fd_ostream(InputFD,
true) << DotGraph;
543 llvm::scope_exit DeleteInput([&] { 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");
546 llvm::scope_exit DeleteOutput([&] { llvm::sys::fs::remove(Output); });
548 std::vector<std::optional<llvm::StringRef>> Redirects = {
552 int Code = llvm::sys::ExecuteAndWait(
553 DotPath, {
"dot",
"-Tsvg"}, std::nullopt, Redirects,
556 return llvm::createStringError(llvm::inconvertibleErrorCode(),
557 "'dot' failed: " + ErrMsg);
559 return llvm::createStringError(llvm::inconvertibleErrorCode(),
560 "'dot' failed (" + llvm::Twine(Code) +
")");
562 auto Buf = llvm::MemoryBuffer::getFile(Output);
564 return llvm::createStringError(Buf.getError(),
"Can't read `dot` output");
567 llvm::StringRef
Result = Buf.get()->getBuffer();
568 auto Pos =
Result.find(
"<svg");
569 if (Pos == llvm::StringRef::npos)
570 return llvm::createStringError(llvm::inconvertibleErrorCode(),
571 "Can't find <svg> tag in `dot` output");
572 return Result.substr(Pos).str();
577std::unique_ptr<Logger>
579 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)
bool operator==(const ValueType &a, const ValueType &b)
@ Result
The result type of a method or function.
@ Off
Never emit colors regardless of the output stream.
U cast(CodeGen::Address addr)
@ Other
Other implicit parameter.
int const char * function