再帰関数の呼び出しをGraphvizで可視化する

#include <iostream>
#include <vector>
#include <string>
#include <fstream>
#include <optional>

struct TraceNode {
   std::string name;
   std::string retval;
   std::optional<std::string> text;
   std::vector<TraceNode> children;
};

class RecursiveTrace {

   TraceNode root;
   std::vector<TraceNode*> stack;
public:
   void setText(std::string text) {
      stack.back()->text = text;
   }
   void addText(std::string text) {
      stack.back()->text = stack.back()->text.value() + text;
   }
   RecursiveTrace() {
      stack.push_back(&root);
   }
   TraceNode* getRoot() {
      return &root;
   }
   void push(std::string name="") {
      stack.back()->children.emplace_back();
      stack.push_back(&stack.back()->children.back());
      stack.back()->name = name;
   }
   void pop() {
      stack.pop_back();
   }
   void setReturn(std::string retval) {
      stack.back()->retval = retval;
   }

};

RecursiveTrace ftrace;

int fibonacci(int n) {

   if (n <= 1) return n; // 基底条件

   ftrace.setText( std::string("in=") + std::to_string(n)+"\\n");

   ftrace.push(std::string("a:")+std::to_string(n) + "-1");
   int a = fibonacci(n - 1);// 再帰呼び出し
   ftrace.pop();

   ftrace.push(std::string("b:") + std::to_string(n) + "-2");
   int b = fibonacci(n - 2);// 再帰呼び出し
   ftrace.pop();

   ftrace.addText("a:"+std::to_string(a)+", b:"+std::to_string(b));
   
   ftrace.setReturn(std::to_string(a+b));
   return a + b;
}

////////////////////////////////////////////////
////////////////////////////////////////////////
////////////////////////////////////////////////

// ノードを再帰的に出力する
void writeNodes(std::ofstream& file, const TraceNode& node, int& nodeId) {

   if (!node.text) return; // 無効なノードで出力を終了

   // ノードの名前を出力
   std::string name = (node.name.length()==0)?"":node.name + "\\n";
   std::string text = (node.text.value().length()==0)?"":node.text.value() + "\\n";
   std::string retval = (node.retval.length()==0)?"":"("+node.retval + ")";

   // ノードのテキストを出力
   int currentId = nodeId++;
   file << "    " << currentId << " [label=\"" 
      << name 
      << text
      << retval
      << "\"];\n";

   // 子ノードの出力
   for (const auto& child : node.children) {
      if (child.text) { // 子ノードが有効か確認
         int childId = nodeId;
         file << "    " << currentId << " -> " << childId << ";\n";
         writeNodes(file, child, nodeId);
      }
   }
}

// Graphviz用のDOTファイルを生成する
void generateDotFile(const TraceNode& root, const std::string& filename) {
   std::ofstream file(filename);
   file << "digraph TraceTree {\n";
   file << "    node [shape=circle];\n";

   int nodeId = 0; // ノードIDのカウンタ
   writeNodes(file, root, nodeId);

   file << "}\n";
   file.close();
}

////////////////////////////////////////////////
////////////////////////////////////////////////
////////////////////////////////////////////////

int main()
{
   int ret = fibonacci(7);

   auto rr = ftrace.getRoot();

   // dotコマンドで画像を生成できる
   // 例
   // dot -Tpng RecursiveTrace.dot -o RecursiveTrace.png

   generateDotFile(*rr, "RecursiveTrace.dot");
}