[PATCH] D144730: [FlowSensitive] Log analysis progress for debugging purposes

[Sam McCall via Phabricator via cfe-commits]

This revision was automatically updated to reflect the committed changes.
Closed by commit rG48f97e575137: [FlowSensitive] Log analysis progress for 
debugging purposes (authored by sammccall).

Changed prior to commit:
  https://reviews.llvm.org/D144730?vs=507418=507678#toc

Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D144730/new/

https://reviews.llvm.org/D144730

Files:
  clang/include/clang/Analysis/FlowSensitive/DataflowAnalysisContext.h
  clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h
  clang/include/clang/Analysis/FlowSensitive/Logger.h
  clang/lib/Analysis/FlowSensitive/CMakeLists.txt
  clang/lib/Analysis/FlowSensitive/DataflowAnalysisContext.cpp
  clang/lib/Analysis/FlowSensitive/Logger.cpp
  clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp
  clang/unittests/Analysis/FlowSensitive/CMakeLists.txt
  clang/unittests/Analysis/FlowSensitive/LoggerTest.cpp

Index: clang/unittests/Analysis/FlowSensitive/LoggerTest.cpp
===
--- /dev/null
+++ clang/unittests/Analysis/FlowSensitive/LoggerTest.cpp
@@ -0,0 +1,152 @@
+#include "TestingSupport.h"
+#include "clang/ASTMatchers/ASTMatchers.h"
+#include "clang/Analysis/FlowSensitive/DataflowAnalysis.h"
+#include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
+#include "clang/Analysis/FlowSensitive/DataflowLattice.h"
+#include "llvm/Testing/Support/Error.h"
+#include "gtest/gtest.h"
+#include 
+
+namespace clang::dataflow::test {
+namespace {
+
+struct TestLattice {
+  int Elements = 0;
+  int Branches = 0;
+  int Joins = 0;
+
+  LatticeJoinEffect join(const TestLattice ) {
+if (Joins < 3) {
+  ++Joins;
+  Elements += Other.Elements;
+  Branches += Other.Branches;
+  return LatticeJoinEffect::Changed;
+}
+return LatticeJoinEffect::Unchanged;
+  }
+  friend bool operator==(const TestLattice , const TestLattice ) {
+return std::tie(LHS.Elements, LHS.Branches, LHS.Joins) ==
+   std::tie(RHS.Elements, RHS.Branches, RHS.Joins);
+  }
+};
+
+class TestAnalysis : public DataflowAnalysis {
+public:
+  using DataflowAnalysis::DataflowAnalysis;
+
+  static TestLattice initialElement() { return TestLattice{}; }
+  void transfer(const CFGElement &, TestLattice , Environment ) {
+E.logger().log([](llvm::raw_ostream ) { OS << "transfer()"; });
+++L.Elements;
+  }
+  void transferBranch(bool Branch, const Stmt *S, TestLattice ,
+  Environment ) {
+E.logger().log([&](llvm::raw_ostream ) {
+  OS << "transferBranch(" << Branch << ")";
+});
+++L.Branches;
+  }
+};
+
+class TestLogger : public Logger {
+public:
+  TestLogger(std::string ) : OS(S) {}
+
+private:
+  llvm::raw_string_ostream OS;
+
+  void beginAnalysis(const ControlFlowContext &,
+ TypeErasedDataflowAnalysis &) override {
+logText("beginAnalysis()");
+  }
+  void endAnalysis() override { logText("\nendAnalysis()"); }
+
+  void enterBlock(const CFGBlock ) override {
+OS << "\nenterBlock(" << B.BlockID << ")\n";
+  }
+  void enterElement(const CFGElement ) override {
+// we don't want the trailing \n
+std::string S;
+llvm::raw_string_ostream SS(S);
+E.dumpToStream(SS);
+
+OS << "enterElement(" << llvm::StringRef(S).trim() << ")\n";
+  }
+  void recordState(TypeErasedDataflowAnalysisState ) override {
+const TestLattice  = llvm::any_cast(S.Lattice.Value);
+OS << "recordState(Elements=" << L.Elements << ", Branches=" << L.Branches
+   << ", Joins=" << L.Joins << ")\n";
+  }
+  /// Records that the analysis state for the current block is now final.
+  void blockConverged() override { logText("blockConverged()"); }
+
+  void logText(llvm::StringRef Text) override { OS << Text << "\n"; }
+};
+
+TEST(LoggerTest, Sequence) {
+  const char *Code = R"cpp(
+int target(bool b, int p, int q) {
+  return b ? p : q;
+}
+)cpp";
+
+  auto Inputs = AnalysisInputs(
+  Code, ast_matchers::hasName("target"),
+  [](ASTContext , Environment &) { return TestAnalysis(C); });
+  std::vector Args = {
+  "-fsyntax-only", "-fno-delayed-template-parsing", "-std=c++17"};
+  Inputs.ASTBuildArgs = Args;
+  std::string Log;
+  TestLogger Logger(Log);
+  Inputs.BuiltinOptions.Log = 
+
+  ASSERT_THAT_ERROR(checkDataflow(std::move(Inputs),
+[](const AnalysisOutputs &) {}),
+llvm::Succeeded());
+
+  EXPECT_EQ(Log, R"(beginAnalysis()
+
+enterBlock(4)
+recordState(Elements=0, Branches=0, Joins=0)
+enterElement(b)
+transfer()
+recordState(Elements=1, Branches=0, Joins=0)
+enterElement(b (ImplicitCastExpr, LValueToRValue, _Bool))
+transfer()
+recordState(Elements=2, Branches=0, Joins=0)
+
+enterBlock(3)
+transferBranch(0)
+recordState(Elements=2, Branches=1, Joins=0)
+enterElement(q)
+transfer()
+recordState(Elements=3, Branches=1, Joins=0)
+
+enterBlock(2)
+transferBranch(1)

[PATCH] D144730: [FlowSensitive] Log analysis progress for debugging purposes

[Yitzhak Mandelbaum via Phabricator via cfe-commits]

ymandel accepted this revision.
ymandel added a comment.

Awesome, thanks!




Comment at: clang/include/clang/Analysis/FlowSensitive/Logger.h:18
+
+class ControlFlowContext;
+class TypeErasedDataflowAnalysis;

Maybe comment on the need for these vs including the headers.



Comment at: clang/lib/Analysis/FlowSensitive/DataflowAnalysisContext.cpp:393
+  if (Opts.Log == nullptr) {
+if (DataflowLog.getNumOccurrences()) {
+  LogOwner = Logger::textual(llvm::errs());

nit: `> 0`?


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D144730/new/

https://reviews.llvm.org/D144730

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D144730: [FlowSensitive] Log analysis progress for debugging purposes

[Sam McCall via Phabricator via cfe-commits]

sammccall added inline comments.



Comment at: clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h:186
+  Logger () const {
+return DACtx->getOptions().Log ? *DACtx->getOptions().Log : Logger::null();
+  }

xazax.hun wrote:
> If we already have a `NullLogger`, I wonder if making 
> `DACtx->getOptions().Log` a reference that points to NullLogger when logging 
> is disabled would be less confusing (and fewer branches).
Made the DataAnalysisContext constructor fill in this field with NullLogger if 
there isn't anything else, to avoid the branch. (Added a comment on the field).

It's still a pointer because of the ergonomic problems with ref fields in 
structs like this (can't initialize incrementally), and because we need a value 
for "no programmatic logging requested, feel free to respect the -dataflow-log 
flag" and using Logger::null() as a sentinel seems pretty surprising.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D144730/new/

https://reviews.llvm.org/D144730

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D144730: [FlowSensitive] Log analysis progress for debugging purposes

[Sam McCall via Phabricator via cfe-commits]

sammccall updated this revision to Diff 507418.
sammccall marked 3 inline comments as done.
sammccall added a comment.

address review comments


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D144730/new/

https://reviews.llvm.org/D144730

Files:
  clang/include/clang/Analysis/FlowSensitive/DataflowAnalysisContext.h
  clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h
  clang/include/clang/Analysis/FlowSensitive/Logger.h
  clang/lib/Analysis/FlowSensitive/CMakeLists.txt
  clang/lib/Analysis/FlowSensitive/DataflowAnalysisContext.cpp
  clang/lib/Analysis/FlowSensitive/Logger.cpp
  clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp
  clang/unittests/Analysis/FlowSensitive/CMakeLists.txt
  clang/unittests/Analysis/FlowSensitive/LoggerTest.cpp

Index: clang/unittests/Analysis/FlowSensitive/LoggerTest.cpp
===
--- /dev/null
+++ clang/unittests/Analysis/FlowSensitive/LoggerTest.cpp
@@ -0,0 +1,152 @@
+#include "TestingSupport.h"
+#include "clang/ASTMatchers/ASTMatchers.h"
+#include "clang/Analysis/FlowSensitive/DataflowAnalysis.h"
+#include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
+#include "clang/Analysis/FlowSensitive/DataflowLattice.h"
+#include "llvm/Testing/Support/Error.h"
+#include "gtest/gtest.h"
+#include 
+
+namespace clang::dataflow::test {
+namespace {
+
+struct TestLattice {
+  int Elements = 0;
+  int Branches = 0;
+  int Joins = 0;
+
+  LatticeJoinEffect join(const TestLattice ) {
+if (Joins < 3) {
+  ++Joins;
+  Elements += Other.Elements;
+  Branches += Other.Branches;
+  return LatticeJoinEffect::Changed;
+}
+return LatticeJoinEffect::Unchanged;
+  }
+  friend bool operator==(const TestLattice , const TestLattice ) {
+return std::tie(LHS.Elements, LHS.Branches, LHS.Joins) ==
+   std::tie(RHS.Elements, RHS.Branches, RHS.Joins);
+  }
+};
+
+class TestAnalysis : public DataflowAnalysis {
+public:
+  using DataflowAnalysis::DataflowAnalysis;
+
+  static TestLattice initialElement() { return TestLattice{}; }
+  void transfer(const CFGElement &, TestLattice , Environment ) {
+E.logger().log([](llvm::raw_ostream ) { OS << "transfer()"; });
+++L.Elements;
+  }
+  void transferBranch(bool Branch, const Stmt *S, TestLattice ,
+  Environment ) {
+E.logger().log([&](llvm::raw_ostream ) {
+  OS << "transferBranch(" << Branch << ")";
+});
+++L.Branches;
+  }
+};
+
+class TestLogger : public Logger {
+public:
+  TestLogger(std::string ) : OS(S) {}
+
+private:
+  llvm::raw_string_ostream OS;
+
+  void beginAnalysis(const ControlFlowContext &,
+ TypeErasedDataflowAnalysis &) override {
+logText("beginAnalysis()");
+  }
+  void endAnalysis() override { logText("\nendAnalysis()"); }
+
+  void enterBlock(const CFGBlock ) override {
+OS << "\nenterBlock(" << B.BlockID << ")\n";
+  }
+  void enterElement(const CFGElement ) override {
+// we don't want the trailing \n
+std::string S;
+llvm::raw_string_ostream SS(S);
+E.dumpToStream(SS);
+
+OS << "enterElement(" << llvm::StringRef(S).trim() << ")\n";
+  }
+  void recordState(TypeErasedDataflowAnalysisState ) override {
+const TestLattice  = llvm::any_cast(S.Lattice.Value);
+OS << "recordState(Elements=" << L.Elements << ", Branches=" << L.Branches
+   << ", Joins=" << L.Joins << ")\n";
+  }
+  /// Records that the analysis state for the current block is now final.
+  void blockConverged() override { logText("blockConverged()"); }
+
+  void logText(llvm::StringRef Text) override { OS << Text << "\n"; }
+};
+
+TEST(LoggerTest, Sequence) {
+  const char *Code = R"cpp(
+int target(bool b, int p, int q) {
+  return b ? p : q;
+}
+)cpp";
+
+  auto Inputs = AnalysisInputs(
+  Code, ast_matchers::hasName("target"),
+  [](ASTContext , Environment &) { return TestAnalysis(C); });
+  std::vector Args = {
+  "-fsyntax-only", "-fno-delayed-template-parsing", "-std=c++17"};
+  Inputs.ASTBuildArgs = Args;
+  std::string Log;
+  TestLogger Logger(Log);
+  Inputs.BuiltinOptions.Log = 
+
+  ASSERT_THAT_ERROR(checkDataflow(std::move(Inputs),
+[](const AnalysisOutputs &) {}),
+llvm::Succeeded());
+
+  EXPECT_EQ(Log, R"(beginAnalysis()
+
+enterBlock(4)
+recordState(Elements=0, Branches=0, Joins=0)
+enterElement(b)
+transfer()
+recordState(Elements=1, Branches=0, Joins=0)
+enterElement(b (ImplicitCastExpr, LValueToRValue, _Bool))
+transfer()
+recordState(Elements=2, Branches=0, Joins=0)
+
+enterBlock(3)
+transferBranch(0)
+recordState(Elements=2, Branches=1, Joins=0)
+enterElement(q)
+transfer()
+recordState(Elements=3, Branches=1, Joins=0)
+
+enterBlock(2)
+transferBranch(1)
+recordState(Elements=2, Branches=1, Joins=0)
+enterElement(p)
+transfer()
+recordState(Elements=3, Branches=1, Joins=0)
+
+enterBlock(1)

[PATCH] D144730: [FlowSensitive] Log analysis progress for debugging purposes

[Gábor Horváth via Phabricator via cfe-commits]

xazax.hun added inline comments.



Comment at: clang/lib/Analysis/FlowSensitive/Logger.cpp:17
+Logger ::null() {
+  struct NullLogger : Logger {};
+  static auto *Instance = new NullLogger();

Adding `final`? Just in case it can help with devirtualization. 



Comment at: clang/lib/Analysis/FlowSensitive/Logger.cpp:23
+namespace {
+struct TextualLogger : Logger {
+  llvm::raw_ostream 

`final`?


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D144730/new/

https://reviews.llvm.org/D144730

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D144730: [FlowSensitive] Log analysis progress for debugging purposes

[Gábor Horváth via Phabricator via cfe-commits]

xazax.hun added inline comments.



Comment at: clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h:186
+  Logger () const {
+return DACtx->getOptions().Log ? *DACtx->getOptions().Log : Logger::null();
+  }

If we already have a `NullLogger`, I wonder if making `DACtx->getOptions().Log` 
a reference that points to NullLogger when logging is disabled would be less 
confusing (and fewer branches).


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D144730/new/

https://reviews.llvm.org/D144730

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D144730: [FlowSensitive] Log analysis progress for debugging purposes

[Sam McCall via Phabricator via cfe-commits]

sammccall added a comment.

In D144730#4211222 , @NoQ wrote:

> I love such debugging facilities! They're a massive boost to developer 
> productivity compared to ad-hoc debug prints, and they allow new contributors 
> to study how the tool works. I'm excited to see how this thing turns out.

Thanks! It's great to know this is a problem worth some attention, as any tools 
here will carry some complexity.

> In the static analyzer's path-sensitive engine we've settled on a Graphviz 
> printout of the analysis graph, with an extra python script to filter and 
> "prettify" it. In our case these graphs are much larger than CFGs (on 
> real-world code they often contain over 20 nodes) so filtering and 
> searching becomes essential. And we usually don't have an option to debug a 
> reduced toy example, because it's typically very hard to define the notion of 
> "false positive" in a way suitable for a `creduce` predicate, and even when 
> reducing manually it's easy to miss the point entirely and end up with a 
> completely different problem. So we had to learn how to deal with these 
> massive graphs, and these days we're pretty good at that. In your case the 
> graphs probably aren't that massive, but other considerations probably still 
> apply.

Yeah, as I understand the dataflow analysis proper is scoped to a function, so 
dealing with larger CFGs but not on that scale. I'm hoping that graphviz 
renderings of the CFG + overlaying it on the code are enough. Text dumps are 
indeed too difficult to read until you're really zeroed in on the bit you want 
to look at.

> If you're stuck with real-world code as much as we are in the static 
> analyzer, it might be very convenient to somehow include a graphical 
> representation of the CFG alongside your reports. Given that CFGs are 
> relatively small, you might be able to get away with an ad-hoc graph 
> visualizer scripted into your HTML page, so that to avoid relying on Graphviz.

Here's a prototype I put together: 
https://htmlpreview.github.io/?https://gist.githubusercontent.com/sam-mccall/c03943495d2ca493be8f3087c22e3b70/raw/986a1d7d9e1ff37e46fc9b6808f0650ae28cc8d3/analyze_optional.html

I tried the ad-hoc method like you suggest to avoid the dependency, but working 
out how to place the nodes & arcs reasonably quickly looked too much for me. 
Ended up going back to shelling out to graphviz but embedding the result in the 
page.

> Then I guess you can try adding your abstract state information directly to 
> the graphical CFG blocks, and build a timeline of such partially analyzed 
> CFGs, from the starting state to the fully converged state, brightly 
> highlighting changes made on every step 樂Dunno, just dreaming at this point.

Yes! This is very much where I want to go. I'll have an initial version up soon 
with basic functionality (timeline, CFG, simple textual dump at each point) but 
showing the most relevant state and changes at each point would be really 
useful.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D144730/new/

https://reviews.llvm.org/D144730

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D144730: [FlowSensitive] Log analysis progress for debugging purposes

[Artem Dergachev via Phabricator via cfe-commits]

NoQ added a comment.

I love such debugging facilities! They're a massive boost to developer 
productivity compared to ad-hoc debug prints, and they allow new contributors 
to study how the tool works. I'm excited to see how this thing turns out.

In the static analyzer's path-sensitive engine we've settled on a Graphviz 
printout of the analysis graph, with an extra python script to filter and 
"prettify" it. In our case these graphs are much larger than CFGs (on 
real-world code they often contain over 20 nodes) so filtering and 
searching becomes essential. And we usually don't have an option to debug a 
reduced toy example, because it's typically very hard to define the notion of 
"false positive" in a way suitable for a `creduce` predicate, and even when 
reducing manually it's easy to miss the point entirely and end up with a 
completely different problem. So we had to learn how to deal with these massive 
graphs, and these days we're pretty good at that. In your case the graphs 
probably aren't that massive, but other considerations probably still apply.

I found textual CFG dumps of real-world functions to be very hard to read; it's 
annoying to figure out in which order you're supposed to read the blocks. Most 
of the time I prefer Graphviz dumps of the CFG. If you're stuck with real-world 
code as much as we are in the static analyzer, it might be very convenient to 
somehow include a graphical representation of the CFG alongside your reports. 
Given that CFGs are relatively small, you might be able to get away with an 
ad-hoc graph visualizer scripted into your HTML page, so that to avoid relying 
on Graphviz.

Then I guess you can try adding your abstract state information directly to the 
graphical CFG blocks, and build a timeline of such partially analyzed CFGs, 
from the starting state to the fully converged state, brightly highlighting 
changes made on every step 樂Dunno, just dreaming at this point.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D144730/new/

https://reviews.llvm.org/D144730

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D144730: [FlowSensitive] Log analysis progress for debugging purposes

[Sam McCall via Phabricator via cfe-commits]

sammccall added a reviewer: xazax.hun.
sammccall added a comment.
Herald added a subscriber: rnkovacs.

Thanks! I cleaned up a bit and added tests, as well as a `-dataflow-log` flag 
to make this easy to access when running unit tests, tidy checks etc.
The HTML experiments seem to have validated that the logging API is sufficient 
to produce something useful there.

I think this is ready for proper review now.




Comment at: clang/include/clang/Analysis/FlowSensitive/Logger.h:38
+  // Forms a pair with endAnalysis().
+  virtual void beginAnalysis(const ControlFlowContext &,
+ TypeErasedDataflowAnalysis &) {}

gribozavr2 wrote:
> Why not DataflowAnalysisContext instead of ControlFlowContext?
> 
> You can reach the latter from the former, but not vice versa.
The idea here is "we're starting to analyze a CFG", so passing in the CFG is 
what we need and seems natural.
DataflowAnalysisContext provides more facilities than we need, and none of the 
extra stuff seems useful.
It's also more awkward to use for our purposes (you can get the CFG, but only 
if you know the right FunctionDecl, and the framework is unclear about whether 
there's always a FunctionDecl).


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D144730/new/

https://reviews.llvm.org/D144730

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D144730: [FlowSensitive] Log analysis progress for debugging purposes

[Sam McCall via Phabricator via cfe-commits]

sammccall updated this revision to Diff 507067.
sammccall marked 2 inline comments as done.
sammccall retitled this revision from "[FlowSensitive][WIP] log analysis 
progress for debugging purposes" to "[FlowSensitive] Log analysis progress for 
debugging purposes".
sammccall edited the summary of this revision.
sammccall added a comment.

Address review comments
Added -dataflow-log flag to enable logging without code changes
Removed example tool from this patch


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D144730/new/

https://reviews.llvm.org/D144730

Files:
  clang/include/clang/Analysis/FlowSensitive/DataflowAnalysisContext.h
  clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h
  clang/include/clang/Analysis/FlowSensitive/Logger.h
  clang/lib/Analysis/FlowSensitive/CMakeLists.txt
  clang/lib/Analysis/FlowSensitive/DataflowAnalysisContext.cpp
  clang/lib/Analysis/FlowSensitive/Logger.cpp
  clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp
  clang/unittests/Analysis/FlowSensitive/CMakeLists.txt
  clang/unittests/Analysis/FlowSensitive/LoggerTest.cpp

Index: clang/unittests/Analysis/FlowSensitive/LoggerTest.cpp
===
--- /dev/null
+++ clang/unittests/Analysis/FlowSensitive/LoggerTest.cpp
@@ -0,0 +1,152 @@
+#include "TestingSupport.h"
+#include "clang/ASTMatchers/ASTMatchers.h"
+#include "clang/Analysis/FlowSensitive/DataflowAnalysis.h"
+#include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
+#include "clang/Analysis/FlowSensitive/DataflowLattice.h"
+#include "llvm/Testing/Support/Error.h"
+#include "gtest/gtest.h"
+#include 
+
+namespace clang::dataflow::test {
+namespace {
+
+struct TestLattice {
+  int Elements = 0;
+  int Branches = 0;
+  int Joins = 0;
+
+  LatticeJoinEffect join(const TestLattice ) {
+if (Joins < 3) {
+  ++Joins;
+  Elements += Other.Elements;
+  Branches += Other.Branches;
+  return LatticeJoinEffect::Changed;
+}
+return LatticeJoinEffect::Unchanged;
+  }
+  friend bool operator==(const TestLattice , const TestLattice ) {
+return std::tie(LHS.Elements, LHS.Branches, LHS.Joins) ==
+   std::tie(RHS.Elements, RHS.Branches, RHS.Joins);
+  }
+};
+
+class TestAnalysis : public DataflowAnalysis {
+public:
+  using DataflowAnalysis::DataflowAnalysis;
+
+  static TestLattice initialElement() { return TestLattice{}; }
+  void transfer(const CFGElement &, TestLattice , Environment ) {
+E.logger().log([](llvm::raw_ostream ) { OS << "transfer()"; });
+++L.Elements;
+  }
+  void transferBranch(bool Branch, const Stmt *S, TestLattice ,
+  Environment ) {
+E.logger().log([&](llvm::raw_ostream ) {
+  OS << "transferBranch(" << Branch << ")";
+});
+++L.Branches;
+  }
+};
+
+class TestLogger : public Logger {
+public:
+  TestLogger(std::string ) : OS(S) {}
+
+private:
+  llvm::raw_string_ostream OS;
+
+  void beginAnalysis(const ControlFlowContext &,
+ TypeErasedDataflowAnalysis &) override {
+logText("beginAnalysis()");
+  }
+  void endAnalysis() override { logText("\nendAnalysis()"); }
+
+  void enterBlock(const CFGBlock ) override {
+OS << "\nenterBlock(" << B.BlockID << ")\n";
+  }
+  void enterElement(const CFGElement ) override {
+// we don't want the trailing \n
+std::string S;
+llvm::raw_string_ostream SS(S);
+E.dumpToStream(SS);
+
+OS << "enterElement(" << llvm::StringRef(S).trim() << ")\n";
+  }
+  void recordState(TypeErasedDataflowAnalysisState ) override {
+const TestLattice  = llvm::any_cast(S.Lattice.Value);
+OS << "recordState(Elements=" << L.Elements << ", Branches=" << L.Branches
+   << ", Joins=" << L.Joins << ")\n";
+  }
+  /// Records that the analysis state for the current block is now final.
+  void blockConverged() override { logText("blockConverged()"); }
+
+  void logText(llvm::StringRef Text) override { OS << Text << "\n"; }
+};
+
+TEST(LoggerTest, Sequence) {
+  const char *Code = R"cpp(
+int target(bool b, int p, int q) {
+  return b ? p : q;
+}
+)cpp";
+
+  auto Inputs = AnalysisInputs(
+  Code, ast_matchers::hasName("target"),
+  [](ASTContext , Environment &) { return TestAnalysis(C); });
+  std::vector Args = {
+  "-fsyntax-only", "-fno-delayed-template-parsing", "-std=c++17"};
+  Inputs.ASTBuildArgs = Args;
+  std::string Log;
+  TestLogger Logger(Log);
+  Inputs.BuiltinOptions.Log = 
+
+  ASSERT_THAT_ERROR(checkDataflow(std::move(Inputs),
+[](const AnalysisOutputs &) {}),
+llvm::Succeeded());
+
+  EXPECT_EQ(Log, R"(beginAnalysis()
+
+enterBlock(4)
+recordState(Elements=0, Branches=0, Joins=0)
+enterElement(b)
+transfer()
+recordState(Elements=1, Branches=0, Joins=0)
+enterElement(b (ImplicitCastExpr, LValueToRValue, _Bool))
+transfer()
+recordState(Elements=2, Branches=0, Joins=0)
+
+enterBlock(3)