clang/lib/Analysis/FlowSensitive/HTMLLogger.cpp

   1 //===-- HTMLLogger.cpp ----------------------------------------------------===//
   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 // 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.
  15 //
  16 // VIEWS
  17 //
  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.
  22 //
  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*.
  26 //
  27 // DATA AND TEMPLATES
  28 //
  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).
  34 //
  35 // SELECTION
  36 //
  37 // This is the only real interactive mechanism.
  38 //
  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)
  44 //
  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.
  49 //
  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"
  54 //
  55 //===----------------------------------------------------------------------===//
  56
  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"
  74
  75 namespace clang::dataflow {
  76 namespace {
  77
  78 // Render a graphviz graph specification to SVG using the `dot` tool.
  79 llvm::Expected<std::string> renderSVG(llvm::StringRef DotGraph);
  80
  81 using StreamFactory = std::function<std::unique_ptr<llvm::raw_ostream>()>;
  82
  83 // Recursively dumps Values/StorageLocations as JSON
  84 class ModelDumper {
  85 public:
  86   ModelDumper(llvm::json::OStream &JOS, const Environment &Env)
  87       : JOS(JOS), Env(Env) {}
  88
  89   void dump(Value &V) {
  90     JOS.attribute("value_id", llvm::to_string(&V));
  91     if (!Visited.insert(&V).second)
  92       return;
  93
  94     JOS.attribute("kind", debugString(V.getKind()));
  95
  96     switch (V.getKind()) {
  97     case Value::Kind::Integer:
  98     case Value::Kind::TopBool:
  99     case Value::Kind::AtomicBool:
 100     case Value::Kind::FormulaBool:
 101       break;
 102     case Value::Kind::Pointer:
 103       JOS.attributeObject(
 104           "pointee", [&] { dump(cast<PointerValue>(V).getPointeeLoc()); });
 105       break;
 106     case Value::Kind::Record:
 107       for (const auto &Child : cast<RecordValue>(V).getLoc().children())
 108         JOS.attributeObject("f:" + Child.first->getNameAsString(), [&] {
 109           if (Child.second)
 110             if (Value *Val = Env.getValue(*Child.second))
 111               dump(*Val);
 112         });
 113       break;
 114     }
 115
 116     for (const auto& Prop : V.properties())
 117       JOS.attributeObject(("p:" + Prop.first()).str(),
 118                           [&] { dump(*Prop.second); });
 119
 120     // Running the SAT solver is expensive, but knowing which booleans are
 121     // guaranteed true/false here is valuable and hard to determine by hand.
 122     if (auto *B = llvm::dyn_cast<BoolValue>(&V)) {
 123       JOS.attribute("formula", llvm::to_string(B->formula()));
 124       JOS.attribute(
 125           "truth", Env.flowConditionImplies(B->formula()) ? "true"
 126                    : Env.flowConditionImplies(Env.arena().makeNot(B->formula()))
 127                        ? "false"
 128                        : "unknown");
 129     }
 130   }
 131   void dump(const StorageLocation &L) {
 132     JOS.attribute("location", llvm::to_string(&L));
 133     if (!Visited.insert(&L).second)
 134       return;
 135
 136     JOS.attribute("type", L.getType().getAsString());
 137     if (auto *V = Env.getValue(L))
 138       dump(*V);
 139   }
 140
 141   llvm::DenseSet<const void*> Visited;
 142   llvm::json::OStream &JOS;
 143   const Environment &Env;
 144 };
 145
 146 class HTMLLogger : public Logger {
 147   StreamFactory Streams;
 148   std::unique_ptr<llvm::raw_ostream> OS;
 149   std::optional<llvm::json::OStream> JOS;
 150
 151   const ControlFlowContext *CFG;
 152   // Timeline of iterations of CFG block visitation.
 153   std::vector<std::pair<const CFGBlock *, unsigned>> Iters;
 154   // Number of times each CFG block has been seen.
 155   llvm::DenseMap<const CFGBlock *, unsigned> BlockIters;
 156   // The messages logged in the current context but not yet written.
 157   std::string ContextLogs;
 158   // The number of elements we have visited within the current CFG block.
 159   unsigned ElementIndex;
 160
 161 public:
 162   explicit HTMLLogger(StreamFactory Streams) : Streams(std::move(Streams)) {}
 163   void beginAnalysis(const ControlFlowContext &CFG,
 164                      TypeErasedDataflowAnalysis &A) override {
 165     OS = Streams();
 166     this->CFG = &CFG;
 167     *OS << llvm::StringRef(HTMLLogger_html).split("<?INJECT?>").first;
 168
 169     const auto &D = CFG.getDecl();
 170     const auto &SM = A.getASTContext().getSourceManager();
 171     *OS << "<title>";
 172     if (const auto *ND = dyn_cast<NamedDecl>(&D))
 173       *OS << ND->getNameAsString() << " at ";
 174     *OS << SM.getFilename(D.getLocation()) << ":"
 175         << SM.getSpellingLineNumber(D.getLocation());
 176     *OS << "</title>\n";
 177
 178     *OS << "<style>" << HTMLLogger_css << "</style>\n";
 179     *OS << "<script>" << HTMLLogger_js << "</script>\n";
 180
 181     writeCode();
 182     writeCFG();
 183
 184     *OS << "<script>var HTMLLoggerData = \n";
 185     JOS.emplace(*OS, /*Indent=*/2);
 186     JOS->objectBegin();
 187     JOS->attributeBegin("states");
 188     JOS->objectBegin();
 189   }
 190   // Between beginAnalysis() and endAnalysis() we write all the states for
 191   // particular analysis points into the `timeline` array.
 192   void endAnalysis() override {
 193     JOS->objectEnd();
 194     JOS->attributeEnd();
 195
 196     JOS->attributeArray("timeline", [&] {
 197       for (const auto &E : Iters) {
 198         JOS->object([&] {
 199           JOS->attribute("block", blockID(E.first->getBlockID()));
 200           JOS->attribute("iter", E.second);
 201         });
 202       }
 203     });
 204     JOS->attributeObject("cfg", [&] {
 205       for (const auto &E : BlockIters)
 206         writeBlock(*E.first, E.second);
 207     });
 208
 209     JOS->objectEnd();
 210     JOS.reset();
 211     *OS << ";\n</script>\n";
 212     *OS << llvm::StringRef(HTMLLogger_html).split("<?INJECT?>").second;
 213   }
 214
 215   void enterBlock(const CFGBlock &B) override {
 216     Iters.emplace_back(&B, ++BlockIters[&B]);
 217     ElementIndex = 0;
 218   }
 219   void enterElement(const CFGElement &E) override {
 220     ++ElementIndex;
 221   }
 222
 223   static std::string blockID(unsigned Block) {
 224     return llvm::formatv("B{0}", Block);
 225   }
 226   static std::string eltID(unsigned Block, unsigned Element) {
 227     return llvm::formatv("B{0}.{1}", Block, Element);
 228   }
 229   static std::string iterID(unsigned Block, unsigned Iter) {
 230     return llvm::formatv("B{0}:{1}", Block, Iter);
 231   }
 232   static std::string elementIterID(unsigned Block, unsigned Iter,
 233                                    unsigned Element) {
 234     return llvm::formatv("B{0}:{1}_B{0}.{2}", Block, Iter, Element);
 235   }
 236
 237   // Write the analysis state associated with a particular analysis point.
 238   // FIXME: this dump is fairly opaque. We should show:
 239   //  - values associated with the current Stmt
 240   //  - values associated with its children
 241   //  - meaningful names for values
 242   //  - which boolean values are implied true/false by the flow condition
 243   void recordState(TypeErasedDataflowAnalysisState &State) override {
 244     unsigned Block = Iters.back().first->getBlockID();
 245     unsigned Iter = Iters.back().second;
 246     JOS->attributeObject(elementIterID(Block, Iter, ElementIndex), [&] {
 247       JOS->attribute("block", blockID(Block));
 248       JOS->attribute("iter", Iter);
 249       JOS->attribute("element", ElementIndex);
 250
 251       // If this state immediately follows an Expr, show its built-in model.
 252       if (ElementIndex > 0) {
 253         auto S =
 254             Iters.back().first->Elements[ElementIndex - 1].getAs<CFGStmt>();
 255         if (const Expr *E = S ? llvm::dyn_cast<Expr>(S->getStmt()) : nullptr) {
 256           if (E->isPRValue()) {
 257             if (auto *V = State.Env.getValue(*E))
 258               JOS->attributeObject(
 259                   "value", [&] { ModelDumper(*JOS, State.Env).dump(*V); });
 260           } else {
 261             if (auto *Loc = State.Env.getStorageLocation(*E))
 262               JOS->attributeObject(
 263                   "value", [&] { ModelDumper(*JOS, State.Env).dump(*Loc); });
 264           }
 265         }
 266       }
 267       if (!ContextLogs.empty()) {
 268         JOS->attribute("logs", ContextLogs);
 269         ContextLogs.clear();
 270       }
 271       {
 272         std::string BuiltinLattice;
 273         llvm::raw_string_ostream BuiltinLatticeS(BuiltinLattice);
 274         State.Env.dump(BuiltinLatticeS);
 275         JOS->attribute("builtinLattice", BuiltinLattice);
 276       }
 277     });
 278   }
 279   void blockConverged() override { logText("Block converged"); }
 280
 281   void logText(llvm::StringRef S) override {
 282     ContextLogs.append(S.begin(), S.end());
 283     ContextLogs.push_back('\n');
 284   }
 285
 286 private:
 287   // Write the CFG block details.
 288   // Currently this is just the list of elements in execution order.
 289   // FIXME: an AST dump would be a useful view, too.
 290   void writeBlock(const CFGBlock &B, unsigned Iters) {
 291     JOS->attributeObject(blockID(B.getBlockID()), [&] {
 292       JOS->attribute("iters", Iters);
 293       JOS->attributeArray("elements", [&] {
 294         for (const auto &Elt : B.Elements) {
 295           std::string Dump;
 296           llvm::raw_string_ostream DumpS(Dump);
 297           Elt.dumpToStream(DumpS);
 298           JOS->value(Dump);
 299         }
 300       });
 301     });
 302   }
 303
 304   // Write the code of function being examined.
 305   // We want to overlay the code with <span>s that mark which BB particular
 306   // tokens are associated with, and even which BB element (so that clicking
 307   // can select the right element).
 308   void writeCode() {
 309     const auto &AST = CFG->getDecl().getASTContext();
 310     bool Invalid = false;
 311
 312     // Extract the source code from the original file.
 313     // Pretty-printing from the AST would probably be nicer (no macros or
 314     // indentation to worry about), but we need the boundaries of particular
 315     // AST nodes and the printer doesn't provide this.
 316     auto Range = clang::Lexer::makeFileCharRange(
 317         CharSourceRange::getTokenRange(CFG->getDecl().getSourceRange()),
 318         AST.getSourceManager(), AST.getLangOpts());
 319     if (Range.isInvalid())
 320       return;
 321     llvm::StringRef Code = clang::Lexer::getSourceText(
 322         Range, AST.getSourceManager(), AST.getLangOpts(), &Invalid);
 323     if (Invalid)
 324       return;
 325
 326     static constexpr unsigned Missing = -1;
 327     // TokenInfo stores the BB and set of elements that a token is part of.
 328     struct TokenInfo {
 329       // The basic block this is part of.
 330       // This is the BB of the stmt with the smallest containing range.
 331       unsigned BB = Missing;
 332       unsigned BBPriority = 0;
 333       // The most specific stmt this is part of (smallest range).
 334       unsigned Elt = Missing;
 335       unsigned EltPriority = 0;
 336       // All stmts this is part of.
 337       SmallVector<unsigned> Elts;
 338
 339       // Mark this token as being part of BB.Elt.
 340       // RangeLen is the character length of the element's range, used to
 341       // distinguish inner vs outer statements.
 342       // For example in `a==0`, token "a" is part of the stmts "a" and "a==0".
 343       // However "a" has a smaller range, so is more specific. Clicking on the
 344       // token "a" should select the stmt "a".
 345       void assign(unsigned BB, unsigned Elt, unsigned RangeLen) {
 346         // A worse BB (larger range) => ignore.
 347         if (this->BB != Missing && BB != this->BB && BBPriority <= RangeLen)
 348           return;
 349         if (BB != this->BB) {
 350           this->BB = BB;
 351           Elts.clear();
 352           BBPriority = RangeLen;
 353         }
 354         BBPriority = std::min(BBPriority, RangeLen);
 355         Elts.push_back(Elt);
 356         if (this->Elt == Missing || EltPriority > RangeLen)
 357           this->Elt = Elt;
 358       }
 359       bool operator==(const TokenInfo &Other) const {
 360         return std::tie(BB, Elt, Elts) ==
 361                std::tie(Other.BB, Other.Elt, Other.Elts);
 362       }
 363       // Write the attributes for the <span> on this token.
 364       void write(llvm::raw_ostream &OS) const {
 365         OS << "class='c";
 366         if (BB != Missing)
 367           OS << " " << blockID(BB);
 368         for (unsigned Elt : Elts)
 369           OS << " " << eltID(BB, Elt);
 370         OS << "'";
 371
 372         if (Elt != Missing)
 373           OS << " data-elt='" << eltID(BB, Elt) << "'";
 374         if (BB != Missing)
 375           OS << " data-bb='" << blockID(BB) << "'";
 376       }
 377     };
 378
 379     // Construct one TokenInfo per character in a flat array.
 380     // This is inefficient (chars in a token all have the same info) but simple.
 381     std::vector<TokenInfo> State(Code.size());
 382     for (const auto *Block : CFG->getCFG()) {
 383       unsigned EltIndex = 0;
 384       for (const auto& Elt : *Block) {
 385         ++EltIndex;
 386         if (const auto S = Elt.getAs<CFGStmt>()) {
 387           auto EltRange = clang::Lexer::makeFileCharRange(
 388               CharSourceRange::getTokenRange(S->getStmt()->getSourceRange()),
 389               AST.getSourceManager(), AST.getLangOpts());
 390           if (EltRange.isInvalid())
 391             continue;
 392           if (EltRange.getBegin() < Range.getBegin() ||
 393               EltRange.getEnd() >= Range.getEnd() ||
 394               EltRange.getEnd() < Range.getBegin() ||
 395               EltRange.getEnd() >= Range.getEnd())
 396             continue;
 397           unsigned Off = EltRange.getBegin().getRawEncoding() -
 398                          Range.getBegin().getRawEncoding();
 399           unsigned Len = EltRange.getEnd().getRawEncoding() -
 400                          EltRange.getBegin().getRawEncoding();
 401           for (unsigned I = 0; I < Len; ++I)
 402             State[Off + I].assign(Block->getBlockID(), EltIndex, Len);
 403         }
 404       }
 405     }
 406
 407     // Finally, write the code with the correct <span>s.
 408     unsigned Line =
 409         AST.getSourceManager().getSpellingLineNumber(Range.getBegin());
 410     *OS << "<template data-copy='code'>\n";
 411     *OS << "<code class='filename'>";
 412     llvm::printHTMLEscaped(
 413         llvm::sys::path::filename(
 414             AST.getSourceManager().getFilename(Range.getBegin())),
 415         *OS);
 416     *OS << "</code>";
 417     *OS << "<code class='line' data-line='" << Line++ << "'>";
 418     for (unsigned I = 0; I < Code.size(); ++I) {
 419       // Don't actually write a <span> around each character, only break spans
 420       // when the TokenInfo changes.
 421       bool NeedOpen = I == 0 || !(State[I] == State[I-1]);
 422       bool NeedClose = I + 1 == Code.size() || !(State[I] == State[I + 1]);
 423       if (NeedOpen) {
 424         *OS << "<span ";
 425         State[I].write(*OS);
 426         *OS << ">";
 427       }
 428       if (Code[I] == '\n')
 429         *OS << "</code>\n<code class='line' data-line='" << Line++ << "'>";
 430       else
 431         llvm::printHTMLEscaped(Code.substr(I, 1), *OS);
 432       if (NeedClose) *OS << "</span>";
 433     }
 434     *OS << "</code>\n";
 435     *OS << "</template>";
 436   }
 437
 438   // Write the CFG diagram, a graph of basic blocks.
 439   // Laying out graphs is hard, so we construct a graphviz description and shell
 440   // out to `dot` to turn it into an SVG.
 441   void writeCFG() {
 442     *OS << "<template data-copy='cfg'>\n";
 443     if (auto SVG = renderSVG(buildCFGDot(CFG->getCFG())))
 444       *OS << *SVG;
 445     else
 446       *OS << "Can't draw CFG: " << toString(SVG.takeError());
 447     *OS << "</template>\n";
 448   }
 449
 450   // Produce a graphviz description of a CFG.
 451   static std::string buildCFGDot(const clang::CFG &CFG) {
 452     std::string Graph;
 453     llvm::raw_string_ostream GraphS(Graph);
 454     // Graphviz likes to add unhelpful tooltips everywhere, " " suppresses.
 455     GraphS << R"(digraph {
 456       tooltip=" "
 457       node[class=bb, shape=square, fontname="sans-serif", tooltip=" "]
 458       edge[tooltip = " "]
 459 )";
 460     for (unsigned I = 0; I < CFG.getNumBlockIDs(); ++I)
 461       GraphS << "  " << blockID(I) << " [id=" << blockID(I) << "]\n";
 462     for (const auto *Block : CFG) {
 463       for (const auto &Succ : Block->succs()) {
 464         if (Succ.getReachableBlock())
 465           GraphS << "  " << blockID(Block->getBlockID()) << " -> "
 466                  << blockID(Succ.getReachableBlock()->getBlockID()) << "\n";
 467       }
 468     }
 469     GraphS << "}\n";
 470     return Graph;
 471   }
 472 };
 473
 474 // Nothing interesting here, just subprocess/temp-file plumbing.
 475 llvm::Expected<std::string> renderSVG(llvm::StringRef DotGraph) {
 476   std::string DotPath;
 477   if (const auto *FromEnv = ::getenv("GRAPHVIZ_DOT"))
 478     DotPath = FromEnv;
 479   else {
 480     auto FromPath = llvm::sys::findProgramByName("dot");
 481     if (!FromPath)
 482       return llvm::createStringError(FromPath.getError(),
 483                                      "'dot' not found on PATH");
 484     DotPath = FromPath.get();
 485   }
 486
 487   // Create input and output files for `dot` subprocess.
 488   // (We create the output file as empty, to reserve the temp filename).
 489   llvm::SmallString<256> Input, Output;
 490   int InputFD;
 491   if (auto EC = llvm::sys::fs::createTemporaryFile("analysis", ".dot", InputFD,
 492                                                    Input))
 493     return llvm::createStringError(EC, "failed to create `dot` temp input");
 494   llvm::raw_fd_ostream(InputFD, /*shouldClose=*/true) << DotGraph;
 495   auto DeleteInput =
 496       llvm::make_scope_exit([&] { llvm::sys::fs::remove(Input); });
 497   if (auto EC = llvm::sys::fs::createTemporaryFile("analysis", ".svg", Output))
 498     return llvm::createStringError(EC, "failed to create `dot` temp output");
 499   auto DeleteOutput =
 500       llvm::make_scope_exit([&] { llvm::sys::fs::remove(Output); });
 501
 502   std::vector<std::optional<llvm::StringRef>> Redirects = {
 503       Input, Output,
 504       /*stderr=*/std::nullopt};
 505   std::string ErrMsg;
 506   int Code = llvm::sys::ExecuteAndWait(
 507       DotPath, {"dot", "-Tsvg"}, /*Env=*/std::nullopt, Redirects,
 508       /*SecondsToWait=*/0, /*MemoryLimit=*/0, &ErrMsg);
 509   if (!ErrMsg.empty())
 510     return llvm::createStringError(llvm::inconvertibleErrorCode(),
 511                                    "'dot' failed: " + ErrMsg);
 512   if (Code != 0)
 513     return llvm::createStringError(llvm::inconvertibleErrorCode(),
 514                                    "'dot' failed (" + llvm::Twine(Code) + ")");
 515
 516   auto Buf = llvm::MemoryBuffer::getFile(Output);
 517   if (!Buf)
 518     return llvm::createStringError(Buf.getError(), "Can't read `dot` output");
 519
 520   // Output has <?xml> prefix we don't want. Skip to <svg> tag.
 521   llvm::StringRef Result = Buf.get()->getBuffer();
 522   auto Pos = Result.find("<svg");
 523   if (Pos == llvm::StringRef::npos)
 524     return llvm::createStringError(llvm::inconvertibleErrorCode(),
 525                                    "Can't find <svg> tag in `dot` output");
 526   return Result.substr(Pos).str();
 527 }
 528
 529 } // namespace
 530
 531 std::unique_ptr<Logger>
 532 Logger::html(std::function<std::unique_ptr<llvm::raw_ostream>()> Streams) {
 533   return std::make_unique<HTMLLogger>(std::move(Streams));
 534 }
 535
 536 } // namespace clang::dataflow