TreeMapWidget.cpp 17 KB

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