From 8e6d4a17385734f8080ffdf4e81b107fcf770cb4 Mon Sep 17 00:00:00 2001
From: Milian Wolff <mail@milianw.de>
Date: Tue, 1 Sep 2015 23:39:19 +0200
Subject: [PATCH] Build a top-down flame graph.

The layouting is still wrong, but this gives us the data at least.
---
 gui/flamegraph.cpp |  8 ++++----
 gui/flamegraph.h   |  8 ++++----
 gui/parser.cpp     | 44 +++++++++++++++++++++++++-------------------
 3 files changed, 33 insertions(+), 27 deletions(-)

diff --git a/gui/flamegraph.cpp b/gui/flamegraph.cpp
index f3f2f07..b504021 100644
--- a/gui/flamegraph.cpp
+++ b/gui/flamegraph.cpp
@@ -61,7 +61,7 @@ void aggregateStack(TreeLeafItem* item, StackData* data)
 class FrameGraphicsItem : public QGraphicsRectItem
 {
 public:
-    FrameGraphicsItem(const QRectF& rect, const quint64 cost, const QByteArray& function)
+    FrameGraphicsItem(const QRectF& rect, const quint64 cost, const QString& function)
         : QGraphicsRectItem(rect)
     {
         static const QString emptyLabel = QStringLiteral("???");
@@ -69,7 +69,7 @@ public:
         m_label = i18nc("%1: memory cost, %2: function label",
                         "%2: %1",
                         cost,
-                        function.isEmpty() ? emptyLabel : QString::fromUtf8(function));
+                        function.isEmpty() ? emptyLabel : function);
         setToolTip(m_label);
     }
 
@@ -186,9 +186,9 @@ void FlameGraph::setData(const FlameGraphData& data)
     }
 
     qDebug() << m_scene->itemsBoundingRect() << m_scene->sceneRect() << m_view->rect() << m_view->contentsRect();
-    m_view->fitInView( m_scene->itemsBoundingRect(), Qt::KeepAspectRatio );
+//     m_view->fitInView( m_scene->itemsBoundingRect(), Qt::KeepAspectRatio );
     // TODO: what is the correct scale value here?! without it, the contents in the view are teeny tiny!
-    m_view->scale(5, 5);
+//     m_view->scale(1, 1);
 
     qDebug() << "took me: " << t.elapsed();
 }
diff --git a/gui/flamegraph.h b/gui/flamegraph.h
index 4ca0fdf..1e6571f 100644
--- a/gui/flamegraph.h
+++ b/gui/flamegraph.h
@@ -29,11 +29,11 @@ class QGraphicsView;
 struct FlameGraphData
 {
     struct Frame {
-        quint64 cost;
-        QMap<QByteArray, Frame> children;
+        quint64 cost = 0;
+        using Stack = QMap<QString, Frame>;
+        Stack children;
     };
-
-    using Stack = QMap<QByteArray, Frame>;
+    using Stack = Frame::Stack;
 
     Stack stack;
 };
diff --git a/gui/parser.cpp b/gui/parser.cpp
index 0254b59..703e475 100644
--- a/gui/parser.cpp
+++ b/gui/parser.cpp
@@ -180,25 +180,27 @@ Parser::Parser(QObject* parent)
 
 Parser::~Parser() = default;
 
-static FlameGraphData::Stack fakeStack(int children, int recurse, int* id = 0, quint64* parentCost = 0)
+static void buildFrameGraph(const QVector<RowData>& mergedAllocations, FlameGraphData::Stack* topStack, QSet<const RowData*>* coveredRows)
 {
-    int stack_id = 1;
-    FlameGraphData::Stack data;
-    if (!id) {
-        id = &stack_id;
-    }
-    for (int i = 0; i < children; ++i) {
-        FlameGraphData::Frame frame;
-        frame.cost = (i + 1) * 2;
-        if (recurse) {
-            frame.children = fakeStack(children - 1, recurse - 1, id, &frame.cost);
-        }
-        if (parentCost) {
-            parentCost += frame.cost;
+    foreach (const auto& row, mergedAllocations) {
+        if (row.children.isEmpty()) {
+            // leaf node found, bubble up the parent chain to build a top-down tree
+            auto node = &row;
+            auto stack = topStack;
+            while (node) {
+                auto& data = (*stack)[node->location.function];
+                if (!coveredRows->contains(node)) {
+                    data.cost += node->allocations;
+                    coveredRows->insert(node);
+                }
+                stack = &data.children;
+                node = node->parent;
+            }
+        } else {
+            // recurse to find a leaf
+            buildFrameGraph(row.children, topStack, coveredRows);
         }
-        data[QByteArray::number((*id)++)] = frame;
     }
-    return data;
 }
 
 void Parser::parse(const QString& path)
@@ -208,10 +210,14 @@ void Parser::parse(const QString& path)
         ParserData data;
         data.read(path.toStdString());
         emit summaryAvailable(generateSummary(data));
-        emit bottomUpDataAvailable(mergeAllocations(data));
+        const auto mergedAllocations = mergeAllocations(data);
+        emit bottomUpDataAvailable(mergedAllocations);
         emit chartDataAvailable(data.chartData);
-        // TODO: implement this
-        emit flameGraphDataAvailable({fakeStack(4, 4)});
+        FlameGraphData::Stack stack;
+        QSet<const RowData*> coveredRows;
+        buildFrameGraph(mergedAllocations, &stack, &coveredRows);
+        qDebug() << data.totalAllocations;
+        emit flameGraphDataAvailable({stack});
         emit finished();
     });
 }
-- 
2.7.4