[dataflow] HTMLLogger - show the value of the current expr

[sammccall]

Summary

Looks like this:

[mboehme]

clang/lib/Analysis/FlowSensitive/HTMLLogger.cpp

96

IIUC, this places properties on the current HTML element as attributes, just like the built-in attributes that we add for other purposes (e.g. "value_id", "kind").

• What happens if we have a property whose name conflicts with one of the built-in attributes?
• Even if we don't have a naming conflict, I think it could be potentially confusing to have user-defined properties appear in the same list and in the same way as built-in attributes.

Suggestion: Can we nest all properties inside of a "properties" attribute?

Edit: Having looked at the HTML template now, I see that we exclude certain attributes there ('kind', 'value_id', 'type', 'location') when listing properties. I still think naming conflicts are a potential problem though. I think it would also be clearer to explicitly pick the properties out of a properties attribute rather than excluding a blocklist of attributes.

121–123

122

Same rationale as for properties above: can we nest the fields inside of a fields attribute?

I think it would also be useful to distinguish between properties and fields in the HTML output; probably not with another nesting level (yikes!), but just rendered differently. This could easily be done if they were separated into properties and fields attributes.

149

clang/unittests/Analysis/FlowSensitive/LoggerTest.cpp

179

Can you add some additional tests for the following?

• Pointers
• References
• Properties
• Struct fields

Ideally, other value kinds too (see copy-paste error above for BiconditionalValue).

[sammccall]

clang/lib/Analysis/FlowSensitive/HTMLLogger.cpp

96

Right, the data model is: a value (really, a Value/StorageLocation mashed together) is just a bag of attributes.

I don't think making it more complicated is an improvement: being built-in isn't the same thing as being custom-rendered.
e.g. "pointee" and "truth" want the default key-value rendering despite being built-in.
Having the exclude list in the template is ugly, but either you end up encoding the rendering info twice in the template like that, or you encode it once in the template and once in the JSON generation (by what goes in the "properties" map vs the main map). I'd rather call this purely a template concern.

Namespace conflict could be a problem: the current behavior is that the last value wins (per JS rules).
IMO the simplest fix is to prepend "p:" and "f:" to properties/struct fields. These would be shown - otherwise the user can't distinguish between a property & field with the same name.

I had this in the prototype, but dropped them because they seemed a bit ugly and conflicts unlikely in practice. WDYT?

121–123

this is neat but capturing the structured binding Val is a C++20 feature

149

right, thanks :-(
Can't wait to get rid of this stuff :-)

clang/unittests/Analysis/FlowSensitive/LoggerTest.cpp

179

There isn't a reasonable way to test in that level of detail without paying a lot for it.
String assertions on the HTML are not suitable for testing nontrivial structures in the JSON.

If we restructure to allow such assertions on the JSON:

• it would be significantly expensive/intrusive
• we would be relying on details of the analysis itself and setting them up indirectly - quite brittle
• we would spend a lot on testing and still not look at all at what matters (the rendering)

My experience is that not having proper tests for these kind of tools is the least-worst option: better than brittle tests where true vs spurious errors are unclear, and better than expensive+still incomplete tests.
The debugging tools tend to get changed infrequently, manually verified, and sometimes an annoying regression creeps in.

[sammccall]

fix bad cast

[sammccall]

use p: and f: prefixes for properties/fields respectively

(we can remove these again if too annoying)

[mboehme]

clang/lib/Analysis/FlowSensitive/HTMLLogger.cpp

96

Namespace conflict could be a problem: the current behavior is that the last value wins (per JS rules).
IMO the simplest fix is to prepend "p:" and "f:" to properties/struct fields. These would be shown - otherwise the user can't distinguish between a property & field with the same name.

Yes, this makes sense to me. I looked at your example screenshot and wasn't sure whether they were both fields or whether one of them was a property -- I think there's value in indicating explicitly what they are.

I had this in the prototype, but dropped them because they seemed a bit ugly and conflicts unlikely in practice. WDYT?

I do think there's a fair chance of conflicts -- many of the attribute names here are short and generic and look like likely field names (e.g. kind, type). Even if the chance of a conflict is relatively low, a conflict will be pretty confusing when it does happen -- and given that we'll be using this feature when we're debugging (i.e. already confused), I think this is worth avoiding.

One more question: How do the "p:" and "f:" items sort in the output? I think these should be sorted together and grouped -- e.g. builtins first, then fields, then properties. (Yes, I know this is more work... but I think it's worth it.)

121–123

Are you sure? I can see nothing here that would indicate this:

https://en.cppreference.com/w/cpp/language/structured_binding

And Clang doesn't complain in -std=c++17:

https://godbolt.org/z/jvYE3cTdq

[sammccall]

display properties at the end of the kv list

clang/lib/Analysis/FlowSensitive/HTMLLogger.cpp

96

One more question: How do the "p:" and "f:" items sort in the output? I think these should be sorted together and grouped -- e.g. builtins first, then fields, then properties. (Yes, I know this is more work... but I think it's worth it.)

Javascript objects are ordered these days, so they'll display in the order we output them here.
So they're already grouped, I rearranged to put properties at the end.

121–123

Hmm, what about this :-)

Structured bindings cannot be captured by lambda expressions: (until C++20)

https://godbolt.org/z/jvYE3cTdq

The capture is the problem: https://godbolt.org/z/e5P43G754

[mboehme]

clang/lib/Analysis/FlowSensitive/HTMLLogger.cpp

96

One more question: How do the "p:" and "f:" items sort in the output? I think these should be sorted together and grouped -- e.g. builtins first, then fields, then properties. (Yes, I know this is more work... but I think it's worth it.)

Javascript objects are ordered these days, so they'll display in the order we output them here.

Got it, thanks.

So they're already grouped, I rearranged to put properties at the end.

SG

121–123

Ah, thanks -- that's the bit I didn't understand.

clang/include/clang/Analysis/FlowSensitive/Value.h

public:
   }
 
   /// Assigns `Val` as the value of the synthetic property with the given
   /// `Name`.
   void setProperty(llvm::StringRef Name, Value &Val) {
     Properties.insert_or_assign(Name, &Val);
   }
 
+  llvm::iterator_range<llvm::StringMap<Value *>::const_iterator>
+  properties() const {
+    return {Properties.begin(), Properties.end()};
+  }
+
 private:
   Kind ValKind;
   llvm::StringMap<Value *> Properties;
 };
 
 /// An equivalence relation for values. It obeys reflexivity, symmetry and
 /// transitivity. It does *not* include comparison of `Properties`.
 ///
Value *getChild(const ValueDecl &D) const {
     if (It == Children.end())
       return nullptr;
     return It->second;
   }
 
   /// Assigns `Val` as the child value for `D`.
   void setChild(const ValueDecl &D, Value &Val) { Children[&D] = &Val; }
 
+  llvm::iterator_range<
+      llvm::DenseMap<const ValueDecl *, Value *>::const_iterator>
+  children() const {
+    return {Children.begin(), Children.end()};
+  }
+
 private:
   llvm::DenseMap<const ValueDecl *, Value *> Children;
 };
 
 raw_ostream &operator<<(raw_ostream &OS, const Value &Val);
 
 } // namespace dataflow
 } // namespace clang
 
 #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_VALUE_H

clang/lib/Analysis/FlowSensitive/HTMLLogger.html

 <!doctype html>
 <html>
 <!-- HTMLLogger.cpp ----------------------------------------------------
 
  Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
  See https://llvm.org/LICENSE.txt for license information.
  SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 
 //===------------------------------------------------------------------------>
 
 <head>
 <?INJECT?>
+
+<template id="value-template">
+  <details class="value" open>
+    <summary>
+      <span>{{v.kind}}
+        <template data-if="v.value_id"><span class="address">#{{v.value_id}}</span></template>
+      </span>
+      <template data-if="v.location">
+        <span>{{v.type}} <span class="address">@{{v.location}}</span></span>
+      </template>
+    </summary>
+    <template
+        data-for="kv in Object.entries(v)"
+        data-if="['kind', 'value_id', 'type', 'location'].indexOf(kv[0]) < 0">
+      <div class="property"><span class="key">{{kv[0]}}</span>
+        <template data-if="typeof(kv[1]) != 'object'">{{kv[1]}}</template>
+        <template data-if="typeof(kv[1]) == 'object'" data-let="v = kv[1]">
+          <template data-use="value-template"></template>
+        </template>
+      </div>
+    </template>
+  </details>
+</template>
+
 </head>
 
 <body>
 
 <section id="timeline" data-selection="">
 <header>Timeline</header>
 <template data-for="entry in timeline">
   <div id="{{entry.block}}:{{entry.iter}}" data-bb="{{entry.block}}" class="entry">{{entry.block}} ({{entry.iter}})</div>

 </section>
 
 <section id="element" data-selection="iter,elt">
 <template data-let="state = states[selection.iter + '_' + selection.elt]">
 <header>
   <template data-if="state.element == 0">{{state.block}} (iteration {{state.iter}}) initial state</template>
   <template data-if="state.element != 0">Element {{selection.elt}} (iteration {{state.iter}})</template>
 </header>
+<template data-if="state.value" data-let="v = state.value">
+  <h2>Value</h2>
+  <template data-use="value-template"></template>
+</template>
 <template data-if="state.logs">
   <h2>Logs</h2>
   <pre>{{state.logs}}</pre>
 </template>
 <h2>Built-in lattice</h2>
 <pre>{{state.builtinLattice}}</pre>
 </template>
 </section>

clang/lib/Analysis/FlowSensitive/HTMLLogger.cpp

 #include "clang/Basic/SourceManager.h"
 #include "clang/Lex/Lexer.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/ScopeExit.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Support/FormatVariadic.h"
 #include "llvm/Support/JSON.h"
 #include "llvm/Support/Program.h"
+#include "llvm/Support/ScopedPrinter.h"
 #include "llvm/Support/raw_ostream.h"
 // Defines assets: HTMLLogger_{html_js,css}
 #include "HTMLLogger.inc"
 
 namespace clang::dataflow {
 namespace {
 
 // Render a graphviz graph specification to SVG using the `dot` tool.
 llvm::Expected<std::string> renderSVG(llvm::StringRef DotGraph);
 
 using StreamFactory = std::function<std::unique_ptr<llvm::raw_ostream>()>;
 
+// Recursively dumps Values/StorageLocations as JSON
+class ModelDumper {
+public:
+  ModelDumper(llvm::json::OStream &JOS, const Environment &Env)
+      : JOS(JOS), Env(Env) {}
+
+  void dump(Value &V) {
+    JOS.attribute("value_id", llvm::to_string(&V));
+    if (!Visited.insert(&V).second)
+      return;
+
+    JOS.attribute("kind", debugString(V.getKind()));
+
+    switch (V.getKind()) {
+    case Value::Kind::Integer:
+    case Value::Kind::TopBool:
+    case Value::Kind::AtomicBool:
+      break;
+    case Value::Kind::Reference:
+      JOS.attributeObject(
+          "referent", [&] { dump(cast<ReferenceValue>(V).getReferentLoc()); });
+      break;
+    case Value::Kind::Pointer:
+      JOS.attributeObject(
+          "pointee", [&] { dump(cast<PointerValue>(V).getPointeeLoc()); });
+      break;
+    case Value::Kind::Struct:
+      for (const auto &Child : cast<StructValue>(V).children())
+        JOS.attributeObject("f:" + Child.first->getNameAsString(),
+                            [&] { dump(*Child.second); });
+      break;
+    case Value::Kind::Disjunction: {
+      auto &VV = cast<DisjunctionValue>(V);
+      JOS.attributeObject("lhs", [&] { dump(VV.getLeftSubValue()); });
+      JOS.attributeObject("rhs", [&] { dump(VV.getRightSubValue()); });
+      break;
+    }
+    case Value::Kind::Conjunction: {
+      auto &VV = cast<ConjunctionValue>(V);
+      JOS.attributeObject("lhs", [&] { dump(VV.getLeftSubValue()); });
+      JOS.attributeObject("rhs", [&] { dump(VV.getRightSubValue()); });
+      break;
+    }
+    case Value::Kind::Negation: {
+      auto &VV = cast<NegationValue>(V);
+      JOS.attributeObject("not", [&] { dump(VV.getSubVal()); });
+      break;
+    }
+    case Value::Kind::Implication: {
+      auto &VV = cast<ImplicationValue>(V);
+      JOS.attributeObject("if", [&] { dump(VV.getLeftSubValue()); });
+      JOS.attributeObject("then", [&] { dump(VV.getRightSubValue()); });
+      break;
+    }
+    case Value::Kind::Biconditional: {
+      auto &VV = cast<BiconditionalValue>(V);
+      JOS.attributeObject("lhs", [&] { dump(VV.getLeftSubValue()); });
+      JOS.attributeObject("rhs", [&] { dump(VV.getRightSubValue()); });
+      break;
+    }
+    }
+
+    for (const auto& Prop : V.properties())
+      JOS.attributeObject(("p:" + Prop.first()).str(),
+                          [&] { dump(*Prop.second); });
+
+    // Running the SAT solver is expensive, but knowing which booleans are
+    // guaranteed true/false here is valuable and hard to determine by hand.
+    if (auto *B = llvm::dyn_cast<BoolValue>(&V)) {
+      JOS.attribute("truth", Env.flowConditionImplies(*B) ? "true"
+                             : Env.flowConditionImplies(Env.makeNot(*B))
+                                 ? "false"
+                                 : "unknown");
+    }
+  }
+  void dump(const StorageLocation &L) {
+    JOS.attribute("location", llvm::to_string(&L));
+    if (!Visited.insert(&L).second)
+      return;
+
+    JOS.attribute("type", L.getType().getAsString());
+    if (auto *V = Env.getValue(L))
+      dump(*V);
+  }
+
+  llvm::DenseSet<const void*> Visited;
+  llvm::json::OStream &JOS;
+  const Environment &Env;
+};
+
 class HTMLLogger : public Logger {
   StreamFactory Streams;
   std::unique_ptr<llvm::raw_ostream> OS;
   std::optional<llvm::json::OStream> JOS;
 
   const ControlFlowContext *CFG;
   // Timeline of iterations of CFG block visitation.
   std::vector<std::pair<const CFGBlock *, unsigned>> Iters;
public:
   //  - which boolean values are implied true/false by the flow condition
   void recordState(TypeErasedDataflowAnalysisState &State) override {
     unsigned Block = Iters.back().first->getBlockID();
     unsigned Iter = Iters.back().second;
     JOS->attributeObject(elementIterID(Block, Iter, ElementIndex), [&] {
       JOS->attribute("block", blockID(Block));
       JOS->attribute("iter", Iter);
       JOS->attribute("element", ElementIndex);
+
+      // If this state immediately follows an Expr, show its built-in model.
+      if (ElementIndex > 0) {
+        auto S =
+            Iters.back().first->Elements[ElementIndex - 1].getAs<CFGStmt>();
+        if (const Expr *E = S ? llvm::dyn_cast<Expr>(S->getStmt()) : nullptr)
+          if (auto *Loc = State.Env.getStorageLocation(*E, SkipPast::None))
+            JOS->attributeObject(
+                "value", [&] { ModelDumper(*JOS, State.Env).dump(*Loc); });
+      }
       if (!ContextLogs.empty()) {
         JOS->attribute("logs", ContextLogs);
         ContextLogs.clear();
       }
       {
         std::string BuiltinLattice;
         llvm::raw_string_ostream BuiltinLatticeS(BuiltinLattice);
         State.Env.dump(BuiltinLatticeS);

clang/lib/Analysis/FlowSensitive/HTMLLogger.css

.bb.bb-select polygon {
   filter: brightness(70%) saturate(150%);
 }
 .bb { user-select: none; }
 .bb polygon { fill: white; }
 #cfg {
   position: relative;
   margin-left: 0.5em;
 }
+
+.value {
+  border: 1px solid #888;
+  font-size: x-small;
+  flex-grow: 1;
+}
+.value summary {
+  background-color: #ace;
+  display: flex;
+  justify-content: space-between;
+}
+.value .address {
+  font-size: xx-small;
+  font-family: monospace;
+  color: #888;
+}
+.value .property {
+  display: flex;
+  margin-top: 0.5em;
+}
+.value .property .key {
+  font-weight: bold;
+  min-width: 5em;
+}

clang/lib/Analysis/FlowSensitive/HTMLLogger.js

if (tmpl.nodeName != 'TEMPLATE') {
     if (clone instanceof Element) {
       for (attr of clone.attributes)
         attr.value = interpolate(attr.value, data);
       for (c of tmpl.childNodes)
         inflate(c, data, clone, /*next=*/null);
     }
     return parent.insertBefore(clone, next);
   }
+  // data-use="xyz": use <template id="xyz"> instead. (Allows recursion.)
+  if ('use' in tmpl.dataset)
+    return inflate(document.getElementById(tmpl.dataset.use), data, parent, next);
   // <template> tag handling. Base case: recursively inflate.
   function handle(data) {
     for (c of tmpl.content.childNodes)
       inflate(c, data, parent, next);
   }
   // Directives on <template> tags modify behavior.
   const directives = {
     // data-for="x in expr": expr is enumerable, bind x to each in turn

clang/unittests/Analysis/FlowSensitive/LoggerTest.cpp

TEST(LoggerTest, HTML) {
   ASSERT_THAT(Logs, testing::SizeIs(1));
   EXPECT_THAT(Logs[0], HasSubstr("function updateSelection")) << "embeds JS";
   EXPECT_THAT(Logs[0], HasSubstr("html {")) << "embeds CSS";
   EXPECT_THAT(Logs[0], HasSubstr("b (ImplicitCastExpr")) << "has CFG elements";
   EXPECT_THAT(Logs[0], HasSubstr("\"B3:1_B3.1\":"))
       << "has analysis point state";
   EXPECT_THAT(Logs[0], HasSubstr("transferBranch(0)")) << "has analysis logs";
   EXPECT_THAT(Logs[0], HasSubstr("LocToVal")) << "has built-in lattice dump";
+  EXPECT_THAT(Logs[0], HasSubstr("\"type\": \"int\"")) << "has value dump";
 }
 
 } // namespace
 } // namespace clang::dataflow::test