jcs.org
Serenity Operating System
1/*
2 * Copyright (c) 2021-2022, the SerenityOS developers.
3 * Copyright (c) 2022-2023, Sam Atkins <atkinssj@serenityos.org>
4 *
5 * SPDX-License-Identifier: BSD-2-Clause
6 */
7
8#include "TreeMapWidget.h"
9#include "ProgressWindow.h"
10#include "Tree.h"
11#include <AK/Array.h>
12#include <AK/DeprecatedString.h>
13#include <AK/NumberFormat.h>
14#include <LibGUI/ConnectionToWindowServer.h>
15#include <LibGUI/Painter.h>
16#include <LibGUI/Statusbar.h>
17#include <LibGfx/Font/Font.h>
18#include <WindowServer/WindowManager.h>
19
20REGISTER_WIDGET(SpaceAnalyzer, TreeMapWidget)
21
22namespace SpaceAnalyzer {
23
24static constexpr Array colors = {
25 Color(253, 231, 37),
26 Color(148, 216, 64),
27 Color(60, 188, 117),
28 Color(31, 150, 139),
29 Color(45, 112, 142),
30 Color(63, 71, 136),
31 Color(85, 121, 104),
32};
33
34static float get_normalized_aspect_ratio(float a, float b)
35{
36 if (a < b) {
37 return a / b;
38 } else {
39 return b / a;
40 }
41}
42
43static bool node_is_leaf(TreeNode const& node)
44{
45 return node.num_children() == 0;
46}
47
48bool TreeMapWidget::rect_can_contain_label(Gfx::IntRect const& rect) const
49{
50 return rect.height() >= font().presentation_size() && rect.width() > 20;
51}
52
53void TreeMapWidget::paint_cell_frame(GUI::Painter& painter, TreeNode const& node, Gfx::IntRect const& cell_rect, Gfx::IntRect const& inner_rect, int depth, HasLabel has_label) const
54{
55 if (cell_rect.width() <= 2 || cell_rect.height() <= 2) {
56 painter.fill_rect(cell_rect, Color::Black);
57 return;
58 }
59 Gfx::IntRect remainder = cell_rect;
60
61 Color color = colors[depth % (sizeof(colors) / sizeof(colors[0]))];
62 if (m_selected_node_cache == &node) {
63 color = color.darkened(0.8f);
64 }
65
66 // Draw borders.
67 painter.fill_rect(remainder.take_from_right(1), Color::Black);
68 painter.fill_rect(remainder.take_from_bottom(1), Color::Black);
69 // Draw highlights.
70 painter.fill_rect(remainder.take_from_right(1), color.darkened());
71 painter.fill_rect(remainder.take_from_bottom(1), color.darkened());
72 painter.fill_rect(remainder.take_from_top(1), color.lightened());
73 painter.fill_rect(remainder.take_from_left(1), color.lightened());
74
75 // Paint the background.
76 if (inner_rect.is_empty()) {
77 painter.fill_rect(remainder, color);
78 } else {
79 // Draw black edges above and to the left of the inner_rect.
80 Gfx::IntRect border_rect = inner_rect.inflated(2, 2);
81 Gfx::IntRect hammer_rect = border_rect;
82 hammer_rect.set_width(hammer_rect.width() - 1);
83 hammer_rect.set_height(hammer_rect.height() - 1);
84 painter.fill_rect(border_rect.take_from_top(1), Color::Black);
85 painter.fill_rect(border_rect.take_from_left(1), Color::Black);
86 for (auto& shard : remainder.shatter(hammer_rect)) {
87 painter.fill_rect(shard, color);
88 }
89 }
90
91 // Paint text.
92 if (has_label == HasLabel::Yes) {
93 Gfx::IntRect text_rect = remainder;
94 text_rect.shrink(4, 4);
95 painter.clear_clip_rect();
96 painter.add_clip_rect(text_rect);
97 if (node_is_leaf(node)) {
98 painter.draw_text(text_rect, node.name(), font(), Gfx::TextAlignment::TopLeft, Color::Black);
99 text_rect.take_from_top(font().presentation_size() + 1);
100 painter.draw_text(text_rect, human_readable_size(node.area()), font(), Gfx::TextAlignment::TopLeft, Color::Black);
101 } else {
102 painter.draw_text(text_rect, DeprecatedString::formatted("{} - {}", node.name(), human_readable_size(node.area())), font(), Gfx::TextAlignment::TopLeft, Color::Black);
103 }
104 painter.clear_clip_rect();
105 }
106}
107
108template<typename Function>
109void TreeMapWidget::lay_out_children(TreeNode const& node, Gfx::IntRect const& rect, int depth, Function callback)
110{
111 if (node.num_children() == 0) {
112 return;
113 }
114
115 // Check if the children are sorted yet, if not do that now.
116 for (size_t k = 0; k < node.num_children() - 1; k++) {
117 if (node.child_at(k).area() < node.child_at(k + 1).area()) {
118 node.sort_children_by_area();
119 break;
120 }
121 }
122
123 i64 total_area = node.area();
124 Gfx::IntRect canvas = rect;
125 bool remaining_nodes_are_too_small = false;
126 for (size_t i = 0; !remaining_nodes_are_too_small && i < node.num_children(); i++) {
127 const i64 i_node_area = node.child_at(i).area();
128 if (i_node_area == 0)
129 break;
130
131 const size_t long_side_size = max(canvas.width(), canvas.height());
132 const size_t short_side_size = min(canvas.width(), canvas.height());
133
134 size_t row_or_column_size = long_side_size * i_node_area / total_area;
135 i64 node_area_sum = i_node_area;
136 size_t k = i + 1;
137
138 // Try to add nodes to this row or column so long as the worst aspect ratio of
139 // the new set of nodes is better than the worst aspect ratio of the current set.
140 {
141 float best_worst_aspect_ratio_so_far = get_normalized_aspect_ratio(row_or_column_size, short_side_size);
142 for (; k < node.num_children(); k++) {
143 // Do a preliminary calculation of the worst aspect ratio of the nodes at index i and k
144 // if that aspect ratio is better than the 'best_worst_aspect_ratio_so_far' we keep it,
145 // otherwise it is discarded.
146 i64 k_node_area = node.child_at(k).area();
147 if (k_node_area == 0) {
148 break;
149 }
150 i64 new_node_area_sum = node_area_sum + k_node_area;
151 size_t new_row_or_column_size = long_side_size * new_node_area_sum / total_area;
152 size_t i_node_size = short_side_size * i_node_area / new_node_area_sum;
153 size_t k_node_size = short_side_size * k_node_area / new_node_area_sum;
154 float i_node_aspect_ratio = get_normalized_aspect_ratio(new_row_or_column_size, i_node_size);
155 float k_node_aspect_ratio = get_normalized_aspect_ratio(new_row_or_column_size, k_node_size);
156 float new_worst_aspect_ratio = min(i_node_aspect_ratio, k_node_aspect_ratio);
157 if (new_worst_aspect_ratio < best_worst_aspect_ratio_so_far) {
158 break;
159 }
160 best_worst_aspect_ratio_so_far = new_worst_aspect_ratio;
161 node_area_sum = new_node_area_sum;
162 row_or_column_size = new_row_or_column_size;
163 }
164 }
165
166 // Paint the elements from 'i' up to and including 'k-1'.
167 {
168 const size_t fixed_side_size = row_or_column_size;
169 i64 placement_area = node_area_sum;
170 size_t main_dim = short_side_size;
171
172 // Lay out nodes in a row or column.
173 Orientation orientation = canvas.width() > canvas.height() ? Orientation::Horizontal : Orientation::Vertical;
174 Gfx::IntRect layout_rect = canvas;
175 layout_rect.set_primary_size_for_orientation(orientation, fixed_side_size);
176 for (size_t q = i; q < k; q++) {
177 auto& child = node.child_at(q);
178 size_t node_size = main_dim * child.area() / placement_area;
179 Gfx::IntRect cell_rect = layout_rect;
180 cell_rect.set_secondary_size_for_orientation(orientation, node_size);
181 Gfx::IntRect inner_rect;
182 HasLabel has_label = HasLabel::No;
183 if (child.num_children() != 0 && rect.height() >= 8 && rect.width() >= 8) {
184 inner_rect = cell_rect;
185 inner_rect.shrink(4, 4); // border and shading
186 if (rect_can_contain_label(inner_rect)) {
187 int const margin = 5;
188 has_label = HasLabel::Yes;
189 inner_rect.set_y(inner_rect.y() + font().presentation_size() + margin);
190 inner_rect.set_height(inner_rect.height() - (font().presentation_size() + margin * 2));
191 inner_rect.set_x(inner_rect.x() + margin);
192 inner_rect.set_width(inner_rect.width() - margin * 2);
193 }
194 } else if (rect_can_contain_label(cell_rect)) {
195 has_label = HasLabel::Yes;
196 }
197 callback(child, q, cell_rect, inner_rect, depth, has_label, IsRemainder::No);
198 if (cell_rect.width() * cell_rect.height() < 16) {
199 remaining_nodes_are_too_small = true;
200 } else if (!inner_rect.is_empty()) {
201 lay_out_children(child, inner_rect, depth + 1, callback);
202 }
203 layout_rect.set_secondary_offset_for_orientation(orientation, layout_rect.secondary_offset_for_orientation(orientation) + node_size);
204 main_dim -= node_size;
205 placement_area -= child.area();
206 }
207 canvas.set_primary_offset_for_orientation(orientation, canvas.primary_offset_for_orientation(orientation) + fixed_side_size);
208 canvas.set_primary_size_for_orientation(orientation, canvas.primary_size_for_orientation(orientation) - fixed_side_size);
209 }
210
211 // Consume nodes that were added to this row or column.
212 i = k - 1;
213 total_area -= node_area_sum;
214 }
215
216 // If not the entire canvas was filled with nodes, fill the remaining area with a dither pattern.
217 if (!canvas.is_empty()) {
218 callback(node, 0, canvas, Gfx::IntRect(), depth, HasLabel::No, IsRemainder::Yes);
219 }
220}
221
222TreeNode const* TreeMapWidget::path_node(size_t n) const
223{
224 if (!m_tree.ptr())
225 return nullptr;
226 TreeNode const* iter = &m_tree->root();
227 size_t path_index = 0;
228 while (iter && path_index < m_path_segments.size() && path_index < n) {
229 auto child_name = m_path_segments[path_index];
230 auto maybe_child = iter->child_with_name(child_name);
231 if (!maybe_child.has_value())
232 return nullptr;
233 iter = &maybe_child.release_value();
234 path_index++;
235 }
236 return iter;
237}
238
239void TreeMapWidget::paint_event(GUI::PaintEvent& event)
240{
241 GUI::Frame::paint_event(event);
242 GUI::Painter painter(*this);
243
244 m_selected_node_cache = path_node(m_path_segments.size());
245
246 TreeNode const* node = path_node(m_viewpoint);
247 if (!node) {
248 painter.fill_rect(frame_inner_rect(), Color::MidGray);
249 } else if (node_is_leaf(*node)) {
250 paint_cell_frame(painter, *node, frame_inner_rect(), Gfx::IntRect(), m_viewpoint - 1, HasLabel::Yes);
251 } else {
252 lay_out_children(*node, frame_inner_rect(), m_viewpoint, [&](TreeNode const& node, int, Gfx::IntRect const& rect, Gfx::IntRect const& inner_rect, int depth, HasLabel has_label, IsRemainder remainder) {
253 if (remainder == IsRemainder::No) {
254 paint_cell_frame(painter, node, rect, inner_rect, depth, has_label);
255 } else {
256 Color color = colors[depth % (sizeof(colors) / sizeof(colors[0]))];
257 Gfx::IntRect dither_rect = rect;
258 painter.fill_rect(dither_rect.take_from_right(1), Color::Black);
259 painter.fill_rect(dither_rect.take_from_bottom(1), Color::Black);
260 painter.fill_rect_with_dither_pattern(dither_rect, color, Color::Black);
261 }
262 });
263 }
264}
265
266Vector<DeprecatedString> TreeMapWidget::path_to_position(Gfx::IntPoint position)
267{
268 TreeNode const* node = path_node(m_viewpoint);
269 if (!node) {
270 return {};
271 }
272 Vector<DeprecatedString> path;
273 lay_out_children(*node, frame_inner_rect(), m_viewpoint, [&](TreeNode const& node, int, Gfx::IntRect const& rect, Gfx::IntRect const&, int, HasLabel, IsRemainder is_remainder) {
274 if (is_remainder == IsRemainder::No && rect.contains(position)) {
275 path.append(node.name());
276 }
277 });
278 return path;
279}
280
281void TreeMapWidget::mousemove_event(GUI::MouseEvent& event)
282{
283 auto* node = path_node(m_viewpoint);
284 if (!node) {
285 set_tooltip({});
286 return;
287 }
288
289 auto* hovered_node = node;
290 lay_out_children(*node, frame_inner_rect(), m_viewpoint, [&](TreeNode const&, int index, Gfx::IntRect const& rect, Gfx::IntRect const&, int, HasLabel, IsRemainder is_remainder) {
291 if (is_remainder == IsRemainder::No && rect.contains(event.position())) {
292 hovered_node = &hovered_node->child_at(index);
293 }
294 });
295
296 set_tooltip(DeprecatedString::formatted("{}\n{}", hovered_node->name(), human_readable_size(hovered_node->area())));
297}
298
299void TreeMapWidget::mousedown_event(GUI::MouseEvent& event)
300{
301 TreeNode const* node = path_node(m_viewpoint);
302 if (node && !node_is_leaf(*node)) {
303 auto path = path_to_position(event.position());
304 if (!path.is_empty()) {
305 m_path_segments.shrink(m_viewpoint);
306 m_path_segments.extend(path);
307 update();
308 }
309 }
310}
311
312void TreeMapWidget::doubleclick_event(GUI::MouseEvent& event)
313{
314 if (event.button() != GUI::MouseButton::Primary)
315 return;
316 TreeNode const* node = path_node(m_viewpoint);
317 if (node && !node_is_leaf(*node)) {
318 auto path = path_to_position(event.position());
319 m_path_segments.shrink(m_viewpoint);
320 m_path_segments.extend(path);
321 m_viewpoint = m_path_segments.size();
322 if (on_path_change) {
323 on_path_change();
324 }
325 update();
326 }
327}
328
329void TreeMapWidget::keydown_event(GUI::KeyEvent& event)
330{
331 if (event.key() == KeyCode::Key_Left)
332 set_viewpoint(m_viewpoint == 0 ? m_path_segments.size() : m_viewpoint - 1);
333 else if (event.key() == KeyCode::Key_Right)
334 set_viewpoint(m_viewpoint == m_path_segments.size() ? 0 : m_viewpoint + 1);
335 else
336 event.ignore();
337}
338
339void TreeMapWidget::mousewheel_event(GUI::MouseEvent& event)
340{
341 int delta = event.wheel_raw_delta_y();
342 if (delta > 0) {
343 size_t step_back = delta;
344 if (step_back > m_viewpoint)
345 step_back = m_viewpoint;
346 set_viewpoint(m_viewpoint - step_back);
347 } else {
348 size_t step_up = -delta;
349 set_viewpoint(m_viewpoint + step_up);
350 }
351}
352
353void TreeMapWidget::context_menu_event(GUI::ContextMenuEvent& context_menu_event)
354{
355 if (on_context_menu_request)
356 on_context_menu_request(context_menu_event);
357}
358
359void TreeMapWidget::recalculate_path_for_new_tree()
360{
361 TreeNode const* current = &m_tree->root();
362 size_t new_path_length = 0;
363 for (auto& segment : m_path_segments) {
364 auto maybe_child = current->child_with_name(segment);
365 if (!maybe_child.has_value())
366 break;
367 new_path_length++;
368 current = &maybe_child.release_value();
369 }
370 m_path_segments.shrink(new_path_length);
371 if (new_path_length < m_viewpoint)
372 m_viewpoint = new_path_length - 1;
373}
374
375static ErrorOr<void> fill_mounts(Vector<MountInfo>& output)
376{
377 // Output info about currently mounted filesystems.
378 auto file = TRY(Core::File::open("/sys/kernel/df"sv, Core::File::OpenMode::Read));
379
380 auto content = TRY(file->read_until_eof());
381 auto json = TRY(JsonValue::from_string(content));
382
383 TRY(json.as_array().try_for_each([&output](JsonValue const& value) -> ErrorOr<void> {
384 auto& filesystem_object = value.as_object();
385 MountInfo mount_info;
386 mount_info.mount_point = filesystem_object.get_deprecated_string("mount_point"sv).value_or({});
387 mount_info.source = filesystem_object.get_deprecated_string("source"sv).value_or("none");
388 TRY(output.try_append(mount_info));
389 return {};
390 }));
391
392 return {};
393}
394
395ErrorOr<void> TreeMapWidget::analyze(GUI::Statusbar& statusbar)
396{
397 statusbar.set_text("");
398 auto progress_window = TRY(ProgressWindow::try_create("Space Analyzer"sv));
399 progress_window->show();
400
401 // Build an in-memory tree mirroring the filesystem and for each node
402 // calculate the sum of the file size for all its descendants.
403 auto tree = TRY(Tree::create(""));
404 Vector<MountInfo> mounts;
405 TRY(fill_mounts(mounts));
406 auto errors = tree->root().populate_filesize_tree(mounts, [&](size_t processed_file_count) {
407 progress_window->update_progress_label(processed_file_count);
408 });
409
410 progress_window->close();
411
412 // Display an error summary in the statusbar.
413 if (!errors.is_empty()) {
414 StringBuilder builder;
415 bool first = true;
416 builder.append("Some directories were not analyzed: "sv);
417 for (auto& key : errors.keys()) {
418 if (!first) {
419 builder.append(", "sv);
420 }
421 auto const* error = strerror(key);
422 builder.append({ error, strlen(error) });
423 builder.append(" ("sv);
424 int value = errors.get(key).value();
425 builder.append(DeprecatedString::number(value));
426 if (value == 1) {
427 builder.append(" time"sv);
428 } else {
429 builder.append(" times"sv);
430 }
431 builder.append(')');
432 first = false;
433 }
434 statusbar.set_text(builder.to_deprecated_string());
435 } else {
436 statusbar.set_text("No errors");
437 }
438
439 m_tree = move(tree);
440 recalculate_path_for_new_tree();
441
442 if (on_path_change) {
443 on_path_change();
444 }
445 update();
446
447 return {};
448}
449
450void TreeMapWidget::set_viewpoint(size_t viewpoint)
451{
452 if (m_viewpoint == viewpoint)
453 return;
454 if (viewpoint > m_path_segments.size())
455 viewpoint = m_path_segments.size();
456 m_viewpoint = viewpoint;
457 if (on_path_change) {
458 on_path_change();
459 }
460 update();
461}
462
463size_t TreeMapWidget::path_size() const
464{
465 return m_path_segments.size() + 1;
466}
467
468size_t TreeMapWidget::viewpoint() const
469{
470 return m_viewpoint;
471}
472
473}