new: persistent ptree (-write-ptree) and klee-ptree

Introduce three different kinds of process trees:
1. Noop: does nothing (e.g. no allocations for DFS)
2. InMemory: same behaviour as before (e.g. RandomPathSearcher)
3. Persistent: similar to InMemory but writes nodes to ptree.db
     and tracks information such as branch type, termination
     type or source location (asm) in nodes. Enabled with
     -write-ptree

ptree.db files can be analysed/plotted with the new "klee-ptree"
tool.

1 files changed, 46 insertions, 0 deletions

diff --git a/tools/klee-ptree/DFSVisitor.cpp b/tools/klee-ptree/DFSVisitor.cpp
new file mode 100644
index 00000000..c87afc3e
--- /dev/null
+++ b/tools/klee-ptree/DFSVisitor.cpp
@@ -0,0 +1,46 @@
+//===-- DFSVisitor.cpp ------------------------------------------*- C++ -*-===//
+//
+//                     The KLEE Symbolic Virtual Machine
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "DFSVisitor.h"
+
+#include <utility>
+
+DFSVisitor::DFSVisitor(const Tree &tree, callbackT cb_intermediate,
+                       callbackT cb_leaf) noexcept
+    : tree{tree},
+      cb_intermediate{std::move(cb_intermediate)}, cb_leaf{std::move(cb_leaf)} {
+  run();
+}
+
+void DFSVisitor::run() const noexcept {
+  // empty tree
+  if (tree.nodes.size() <= 1)
+    return;
+
+  std::vector<std::tuple<std::uint32_t, std::uint32_t>> stack{
+      {1, 1}}; // (id, depth)
+  while (!stack.empty()) {
+    std::uint32_t id, depth;
+    std::tie(id, depth) = stack.back();
+    stack.pop_back();
+    const auto &node = tree.nodes[id];
+
+    if (node.left || node.right) {
+      if (cb_intermediate)
+        cb_intermediate(id, node, depth);
+      if (node.right)
+        stack.emplace_back(node.right, depth + 1);
+      if (node.left)
+        stack.emplace_back(node.left, depth + 1);
+    } else {
+      if (cb_leaf)
+        cb_leaf(id, node, depth);
+    }
+  }
+}