Profiler: Add a flamegraph view for the stack

The flamegraph makes it easier to quickly spot expensive functions,
based on the width of their bar.

4 files changed, 312 insertions, 10 deletions

diff --git a/Userland/DevTools/Profiler/CMakeLists.txt b/Userland/DevTools/Profiler/CMakeLists.txt
index 427a8340cb..c9b29e4602 100644
--- a/Userland/DevTools/Profiler/CMakeLists.txt
+++ b/Userland/DevTools/Profiler/CMakeLists.txt
@@ -8,6 +8,7 @@ set(SOURCES
         DisassemblyModel.cpp
         main.cpp
         IndividualSampleModel.cpp
+        FlameGraphView.cpp
         Process.cpp
         Profile.cpp
         ProfileModel.cpp
diff --git a/Userland/DevTools/Profiler/FlameGraphView.cpp b/Userland/DevTools/Profiler/FlameGraphView.cpp
new file mode 100644
index 0000000000..5634dbc9a2
--- /dev/null
+++ b/Userland/DevTools/Profiler/FlameGraphView.cpp
@@ -0,0 +1,220 @@
+/*
+ * Copyright (c) 2021, Nicholas Hollett <niax@niax.co.uk>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include "FlameGraphView.h"
+#include "DevTools/Profiler/Profile.h"
+#include "LibGfx/Forward.h"
+#include <AK/Function.h>
+#include <LibGUI/Painter.h>
+#include <LibGfx/FontDatabase.h>
+#include <LibGfx/Palette.h>
+
+namespace Profiler {
+
+constexpr int bar_rounding = 2;
+constexpr int bar_margin = 2;
+constexpr int bar_padding = 8;
+constexpr int bar_height = 20;
+constexpr int text_threshold = 30;
+
+Vector<Gfx::Color> s_colors;
+
+static Vector<Gfx::Color> const& get_colors()
+{
+    if (s_colors.size() == 0) {
+        // Start with a nice orange, then make shades of it
+        Gfx::Color midpoint(255, 94, 19);
+        s_colors.extend(midpoint.shades(3, 0.5f));
+        s_colors.append(midpoint);
+        s_colors.extend(midpoint.tints(3, 0.5f));
+    }
+
+    return s_colors;
+}
+
+FlameGraphView::FlameGraphView(GUI::Model& model, int text_column, int width_column)
+    : m_model(model)
+    , m_text_column(text_column)
+    , m_width_column(width_column)
+{
+    set_fill_with_background_color(true);
+    set_background_role(Gfx::ColorRole::Base);
+
+    m_model.register_client(*this);
+
+    m_colors = get_colors();
+    layout_bars();
+}
+
+FlameGraphView::~FlameGraphView()
+{
+}
+
+GUI::ModelIndex const FlameGraphView::hovered_index() const
+{
+    if (!m_hovered_bar)
+        return GUI::ModelIndex();
+    return m_hovered_bar->index;
+}
+
+void FlameGraphView::model_did_update(unsigned)
+{
+    m_selected_indexes.clear();
+    layout_bars();
+    update();
+}
+
+void FlameGraphView::mousemove_event(GUI::MouseEvent& event)
+{
+    StackBar* hovered_bar = nullptr;
+
+    for (size_t i = 0; i < m_bars.size(); ++i) {
+        auto& bar = m_bars[i];
+        if (bar.rect.contains(event.x(), event.y())) {
+            hovered_bar = &bar;
+            break;
+        }
+    }
+
+    if (m_hovered_bar == hovered_bar)
+        return;
+
+    m_hovered_bar = hovered_bar;
+
+    if (on_hover_change)
+        on_hover_change();
+
+    update();
+}
+
+void FlameGraphView::mousedown_event(GUI::MouseEvent& event)
+{
+    if (event.button() != GUI::MouseButton::Left)
+        return;
+
+    if (!m_hovered_bar)
+        return;
+
+    m_selected_indexes.clear();
+    GUI::ModelIndex selected_index = m_hovered_bar->index;
+    while (selected_index.is_valid()) {
+        m_selected_indexes.append(selected_index);
+        selected_index = selected_index.parent();
+    }
+
+    layout_bars();
+    update();
+}
+
+void FlameGraphView::resize_event(GUI::ResizeEvent&)
+{
+    layout_bars();
+}
+
+void FlameGraphView::paint_event(GUI::PaintEvent& event)
+{
+    GUI::Painter painter(*this);
+    painter.add_clip_rect(event.rect());
+
+    for (auto& bar : m_bars) {
+        auto label_index = bar.index.sibling_at_column(m_text_column);
+        String label = "All";
+        if (label_index.is_valid()) {
+            label = m_model.data(label_index).to_string();
+        }
+
+        auto color = m_colors[label.hash() % m_colors.size()];
+
+        if (&bar == m_hovered_bar)
+            color = color.lightened(1.2f);
+
+        if (bar.selected)
+            color = color.with_alpha(128);
+
+        // Do rounded corners if the node will draw with enough width
+        if (bar.rect.width() > (bar_rounding * 3))
+            painter.fill_rect_with_rounded_corners(bar.rect.shrunken(0, bar_margin), color, bar_rounding);
+        else
+            painter.fill_rect(bar.rect.shrunken(0, bar_margin), color);
+
+        if (bar.rect.width() > text_threshold) {
+            painter.draw_text(
+                bar.rect.shrunken(bar_padding, 0),
+                label,
+                painter.font(),
+                Gfx::TextAlignment::CenterLeft,
+                Gfx::Color::Black,
+                Gfx::TextElision::Right);
+        }
+    }
+}
+
+void FlameGraphView::layout_bars()
+{
+    m_bars.clear();
+
+    // Explicit copy here so the layout can multate
+    Vector<GUI::ModelIndex> selected = m_selected_indexes;
+    GUI::ModelIndex null_index;
+    layout_children(null_index, 0, 0, this->width(), selected);
+}
+
+void FlameGraphView::layout_children(GUI::ModelIndex& index, int depth, int left, int right, Vector<GUI::ModelIndex>& selected_nodes)
+{
+    auto available_width = right - left;
+    if (available_width < 1)
+        return;
+
+    auto y = this->height() - (bar_height * depth) - bar_height;
+    if (y < 0)
+        return;
+
+    u32 node_event_count = 0;
+    if (!index.is_valid()) {
+        // We're at the root, so calculate the event count across all roots
+        for (auto i = 0; i < m_model.row_count(index); ++i) {
+            auto& root = *static_cast<ProfileNode*>(m_model.index(i).internal_data());
+            node_event_count += root.event_count();
+        }
+        m_bars.append({ {}, { left, y, available_width, bar_height }, false });
+    } else {
+        auto node = static_cast<ProfileNode*>(index.internal_data());
+
+        bool selected = !selected_nodes.is_empty();
+        if (selected) {
+            VERIFY(selected_nodes.take_last() == index);
+        }
+
+        node_event_count = node->event_count();
+
+        Gfx::IntRect node_rect { left, y, available_width, bar_height };
+        m_bars.append({ index, node_rect, selected });
+    }
+
+    float width_per_sample = static_cast<float>(available_width) / node_event_count;
+    float new_left = static_cast<float>(left);
+
+    for (auto i = 0; i < m_model.row_count(index); ++i) {
+        auto child_index = m_model.index(i, 0, index);
+        if (!child_index.is_valid())
+            continue;
+
+        if (!selected_nodes.is_empty()) {
+            if (selected_nodes.last() != child_index)
+                continue;
+
+            layout_children(child_index, depth + 1, left, right, selected_nodes);
+            return;
+        }
+
+        auto child = static_cast<ProfileNode*>(child_index.internal_data());
+        float child_width = width_per_sample * child->event_count();
+        layout_children(child_index, depth + 1, static_cast<int>(new_left), static_cast<int>(new_left + child_width), selected_nodes);
+        new_left += child_width;
+    }
+}
+
+}
diff --git a/Userland/DevTools/Profiler/FlameGraphView.h b/Userland/DevTools/Profiler/FlameGraphView.h
new file mode 100644
index 0000000000..2b9dd4eaf5
--- /dev/null
+++ b/Userland/DevTools/Profiler/FlameGraphView.h
@@ -0,0 +1,60 @@
+/*
+ * Copyright (c) 2021, Nicholas Hollett <niax@niax.co.uk>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#pragma once
+
+#include "Profile.h"
+#include <AK/Function.h>
+#include <AK/Optional.h>
+#include <LibGUI/Model.h>
+#include <LibGUI/Painter.h>
+#include <LibGUI/Widget.h>
+#include <LibGfx/Color.h>
+
+namespace Profiler {
+
+class FlameGraphView final : public GUI::Widget
+    , GUI::ModelClient {
+    C_OBJECT(FlameGraphView);
+
+public:
+    virtual ~FlameGraphView() override;
+
+    Function<void()> on_hover_change;
+
+    GUI::ModelIndex const hovered_index() const;
+
+protected:
+    virtual void model_did_update(unsigned flags) override;
+
+    virtual void mousemove_event(GUI::MouseEvent&) override;
+    virtual void mousedown_event(GUI::MouseEvent&) override;
+
+    virtual void resize_event(GUI::ResizeEvent&) override;
+    virtual void paint_event(GUI::PaintEvent&) override;
+
+private:
+    explicit FlameGraphView(GUI::Model&, int text_column, int width_column);
+
+    struct StackBar {
+        GUI::ModelIndex const index;
+        Gfx::IntRect rect;
+        bool selected;
+    };
+
+    void layout_bars();
+    void layout_children(GUI::ModelIndex& parent, int depth, int left, int right, Vector<GUI::ModelIndex>& selected);
+
+    GUI::Model& m_model;
+    int m_text_column { -1 };
+    int m_width_column { -1 };
+    Vector<Gfx::Color> m_colors;
+    Vector<StackBar> m_bars;
+    StackBar* m_hovered_bar {};
+    Vector<GUI::ModelIndex> m_selected_indexes;
+};
+
+}
diff --git a/Userland/DevTools/Profiler/main.cpp b/Userland/DevTools/Profiler/main.cpp
index 344fac6350..8ae0f7ee6f 100644
--- a/Userland/DevTools/Profiler/main.cpp
+++ b/Userland/DevTools/Profiler/main.cpp
@@ -4,8 +4,10 @@
  * SPDX-License-Identifier: BSD-2-Clause
  */
 
+#include "FlameGraphView.h"
 #include "IndividualSampleModel.h"
 #include "Profile.h"
+#include "ProfileModel.h"
 #include "TimelineContainer.h"
 #include "TimelineHeader.h"
 #include "TimelineTrack.h"
@@ -191,6 +193,12 @@ int main(int argc, char** argv)
         individual_signpost_view.set_model(move(model));
     };
 
+    auto& flamegraph_tab = tab_widget.add_tab<GUI::Widget>("Flame Graph");
+    flamegraph_tab.set_layout<GUI::VerticalBoxLayout>();
+    flamegraph_tab.layout()->set_margins({ 4, 4, 4, 4 });
+
+    auto& flamegraph_view = flamegraph_tab.add<FlameGraphView>(profile->model(), ProfileModel::Column::StackFrame, ProfileModel::Column::SampleCount);
+
     const u64 start_of_trace = profile->first_timestamp();
     const u64 end_of_trace = start_of_trace + profile->length_in_ms();
     const auto clamp_timestamp = [start_of_trace, end_of_trace](u64 timestamp) -> u64 {
@@ -198,21 +206,34 @@ int main(int argc, char** argv)
     };
 
     auto& statusbar = main_widget.add<GUI::Statusbar>();
-    timeline_view->on_selection_change = [&] {
+    auto statusbar_update = [&] {
         auto& view = *timeline_view;
         StringBuilder builder;
-        u64 normalized_start_time = clamp_timestamp(min(view.select_start_time(), view.select_end_time()));
-        u64 normalized_end_time = clamp_timestamp(max(view.select_start_time(), view.select_end_time()));
-        u64 normalized_hover_time = clamp_timestamp(view.hover_time());
-        builder.appendff("Time: {} ms", normalized_hover_time - start_of_trace);
-        if (normalized_start_time != normalized_end_time) {
-            auto start = normalized_start_time - start_of_trace;
-            auto end = normalized_end_time - start_of_trace;
-            builder.appendff(", Selection: {} - {} ms", start, end);
-            builder.appendff(", Duration: {} ms", end - start);
+
+        auto flamegraph_hovered_index = flamegraph_view.hovered_index();
+        if (flamegraph_hovered_index.is_valid()) {
+            auto stack = profile->model().data(flamegraph_hovered_index.sibling_at_column(ProfileModel::Column::StackFrame)).to_string();
+            auto sample_count = profile->model().data(flamegraph_hovered_index.sibling_at_column(ProfileModel::Column::SampleCount)).to_i32();
+            auto self_count = profile->model().data(flamegraph_hovered_index.sibling_at_column(ProfileModel::Column::SelfCount)).to_i32();
+            builder.appendff("{}, ", stack);
+            builder.appendff("Samples: {}{}, ", sample_count, profile->show_percentages() ? "%" : " Samples");
+            builder.appendff("Self: {}{}", self_count, profile->show_percentages() ? "%" : " Samples");
+        } else {
+            u64 normalized_start_time = clamp_timestamp(min(view.select_start_time(), view.select_end_time()));
+            u64 normalized_end_time = clamp_timestamp(max(view.select_start_time(), view.select_end_time()));
+            u64 normalized_hover_time = clamp_timestamp(view.hover_time());
+            builder.appendff("Time: {} ms", normalized_hover_time - start_of_trace);
+            if (normalized_start_time != normalized_end_time) {
+                auto start = normalized_start_time - start_of_trace;
+                auto end = normalized_end_time - start_of_trace;
+                builder.appendff(", Selection: {} - {} ms", start, end);
+                builder.appendff(", Duration: {} ms", end - start);
+            }
         }
         statusbar.set_text(builder.to_string());
     };
+    timeline_view->on_selection_change = [&] { statusbar_update(); };
+    flamegraph_view.on_hover_change = [&] { statusbar_update(); };
 
     auto& file_menu = window->add_menu("&File");
     file_menu.add_action(GUI::CommonActions::make_quit_action([&](auto&) { app->quit(); }));