TreeBuilder.cpp 22 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513
  1. /*
  2. * Copyright (c) 2018-2022, Andreas Kling <kling@serenityos.org>
  3. * Copyright (c) 2022, Sam Atkins <atkinssj@serenityos.org>
  4. * Copyright (c) 2022, MacDue <macdue@dueutil.tech>
  5. *
  6. * SPDX-License-Identifier: BSD-2-Clause
  7. */
  8. #include <AK/Optional.h>
  9. #include <AK/TemporaryChange.h>
  10. #include <LibWeb/DOM/Document.h>
  11. #include <LibWeb/DOM/Element.h>
  12. #include <LibWeb/DOM/ParentNode.h>
  13. #include <LibWeb/DOM/ShadowRoot.h>
  14. #include <LibWeb/Dump.h>
  15. #include <LibWeb/HTML/HTMLProgressElement.h>
  16. #include <LibWeb/Layout/InitialContainingBlock.h>
  17. #include <LibWeb/Layout/ListItemBox.h>
  18. #include <LibWeb/Layout/ListItemMarkerBox.h>
  19. #include <LibWeb/Layout/Node.h>
  20. #include <LibWeb/Layout/Progress.h>
  21. #include <LibWeb/Layout/TableBox.h>
  22. #include <LibWeb/Layout/TableCellBox.h>
  23. #include <LibWeb/Layout/TableRowBox.h>
  24. #include <LibWeb/Layout/TextNode.h>
  25. #include <LibWeb/Layout/TreeBuilder.h>
  26. namespace Web::Layout {
  27. TreeBuilder::TreeBuilder() = default;
  28. static bool has_inline_or_in_flow_block_children(Layout::Node const& layout_node)
  29. {
  30. for (auto const* child = layout_node.first_child(); child; child = child->next_sibling()) {
  31. if (child->is_inline())
  32. return true;
  33. if (!child->is_floating() && !child->is_absolutely_positioned())
  34. return true;
  35. }
  36. return false;
  37. }
  38. static bool has_in_flow_block_children(Layout::Node const& layout_node)
  39. {
  40. if (layout_node.children_are_inline())
  41. return false;
  42. for (auto const* child = layout_node.first_child(); child; child = child->next_sibling()) {
  43. if (child->is_inline())
  44. continue;
  45. if (!child->is_floating() && !child->is_absolutely_positioned())
  46. return true;
  47. }
  48. return false;
  49. }
  50. // The insertion_parent_for_*() functions maintain the invariant that the in-flow children of
  51. // block-level boxes must be either all block-level or all inline-level.
  52. static Layout::Node& insertion_parent_for_inline_node(Layout::NodeWithStyle& layout_parent)
  53. {
  54. if (layout_parent.display().is_inline_outside() && layout_parent.display().is_flow_inside())
  55. return layout_parent;
  56. if (layout_parent.display().is_flex_inside()) {
  57. layout_parent.append_child(layout_parent.create_anonymous_wrapper());
  58. return *layout_parent.last_child();
  59. }
  60. if (!has_in_flow_block_children(layout_parent) || layout_parent.children_are_inline())
  61. return layout_parent;
  62. // Parent has block-level children, insert into an anonymous wrapper block (and create it first if needed)
  63. if (!layout_parent.last_child()->is_anonymous() || !layout_parent.last_child()->children_are_inline()) {
  64. layout_parent.append_child(layout_parent.create_anonymous_wrapper());
  65. }
  66. return *layout_parent.last_child();
  67. }
  68. static Layout::Node& insertion_parent_for_block_node(Layout::NodeWithStyle& layout_parent, Layout::Node& layout_node)
  69. {
  70. if (!has_inline_or_in_flow_block_children(layout_parent)) {
  71. // Parent block has no children, insert this block into parent.
  72. return layout_parent;
  73. }
  74. if (!layout_parent.children_are_inline()) {
  75. // Parent block has block-level children, insert this block into parent.
  76. return layout_parent;
  77. }
  78. if (layout_node.is_floating() || layout_node.is_absolutely_positioned()) {
  79. // Block is out-of-flow, it can have inline siblings if necessary.
  80. return layout_parent;
  81. }
  82. // Parent block has inline-level children (our siblings).
  83. // First move these siblings into an anonymous wrapper block.
  84. NonnullRefPtrVector<Layout::Node> children;
  85. while (RefPtr<Layout::Node> child = layout_parent.first_child()) {
  86. layout_parent.remove_child(*child);
  87. children.append(child.release_nonnull());
  88. }
  89. layout_parent.append_child(layout_parent.create_anonymous_wrapper());
  90. layout_parent.set_children_are_inline(false);
  91. for (auto& child : children) {
  92. layout_parent.last_child()->append_child(child);
  93. }
  94. layout_parent.last_child()->set_children_are_inline(true);
  95. // Then it's safe to insert this block into parent.
  96. return layout_parent;
  97. }
  98. void TreeBuilder::insert_node_into_inline_or_block_ancestor(Layout::Node& node, CSS::Display display, AppendOrPrepend mode)
  99. {
  100. if (display.is_inline_outside()) {
  101. // Inlines can be inserted into the nearest ancestor.
  102. auto& insertion_point = insertion_parent_for_inline_node(m_ancestor_stack.last());
  103. if (mode == AppendOrPrepend::Prepend)
  104. insertion_point.prepend_child(node);
  105. else
  106. insertion_point.append_child(node);
  107. insertion_point.set_children_are_inline(true);
  108. } else {
  109. // Non-inlines can't be inserted into an inline parent, so find the nearest non-inline ancestor.
  110. auto& nearest_non_inline_ancestor = [&]() -> Layout::NodeWithStyle& {
  111. for (auto& ancestor : m_ancestor_stack.in_reverse()) {
  112. if (!ancestor.display().is_inline_outside())
  113. return ancestor;
  114. if (!ancestor.display().is_flow_inside())
  115. return ancestor;
  116. }
  117. VERIFY_NOT_REACHED();
  118. }();
  119. auto& insertion_point = insertion_parent_for_block_node(nearest_non_inline_ancestor, node);
  120. if (mode == AppendOrPrepend::Prepend)
  121. insertion_point.prepend_child(node);
  122. else
  123. insertion_point.append_child(node);
  124. // After inserting an in-flow block-level box into a parent, mark the parent as having non-inline children.
  125. if (!node.is_floating() && !node.is_absolutely_positioned())
  126. insertion_point.set_children_are_inline(false);
  127. }
  128. }
  129. void TreeBuilder::create_pseudo_element_if_needed(DOM::Element& element, CSS::Selector::PseudoElement pseudo_element, AppendOrPrepend mode)
  130. {
  131. auto& document = element.document();
  132. auto& style_computer = document.style_computer();
  133. auto pseudo_element_style = style_computer.compute_style(element, pseudo_element);
  134. auto pseudo_element_content = pseudo_element_style->content();
  135. auto pseudo_element_display = pseudo_element_style->display();
  136. // ::before and ::after only exist if they have content. `content: normal` computes to `none` for them.
  137. // We also don't create them if they are `display: none`.
  138. if (pseudo_element_display.is_none()
  139. || pseudo_element_content.type == CSS::ContentData::Type::Normal
  140. || pseudo_element_content.type == CSS::ContentData::Type::None)
  141. return;
  142. auto pseudo_element_node = DOM::Element::create_layout_node_for_display_type(document, pseudo_element_display, pseudo_element_style, nullptr);
  143. if (!pseudo_element_node)
  144. return;
  145. pseudo_element_node->set_generated(true);
  146. // FIXME: Handle images, and multiple values
  147. if (pseudo_element_content.type == CSS::ContentData::Type::String) {
  148. auto* text = document.heap().allocate<DOM::Text>(document.realm(), document, pseudo_element_content.data);
  149. auto text_node = adopt_ref(*new TextNode(document, *text));
  150. text_node->set_generated(true);
  151. push_parent(verify_cast<NodeWithStyle>(*pseudo_element_node));
  152. insert_node_into_inline_or_block_ancestor(text_node, text_node->display(), AppendOrPrepend::Append);
  153. pop_parent();
  154. } else {
  155. TODO();
  156. }
  157. element.set_pseudo_element_node({}, pseudo_element, pseudo_element_node);
  158. insert_node_into_inline_or_block_ancestor(*pseudo_element_node, pseudo_element_display, mode);
  159. }
  160. void TreeBuilder::create_layout_tree(DOM::Node& dom_node, TreeBuilder::Context& context)
  161. {
  162. // If the parent doesn't have a layout node, we don't need one either.
  163. if (dom_node.parent_or_shadow_host() && !dom_node.parent_or_shadow_host()->layout_node())
  164. return;
  165. Optional<TemporaryChange<bool>> has_svg_root_change;
  166. if (dom_node.is_svg_container()) {
  167. has_svg_root_change.emplace(context.has_svg_root, true);
  168. } else if (dom_node.requires_svg_container() && !context.has_svg_root) {
  169. return;
  170. }
  171. auto& document = dom_node.document();
  172. auto& style_computer = document.style_computer();
  173. RefPtr<Layout::Node> layout_node;
  174. RefPtr<CSS::StyleProperties> style;
  175. CSS::Display display;
  176. if (is<DOM::Element>(dom_node)) {
  177. auto& element = static_cast<DOM::Element&>(dom_node);
  178. element.clear_pseudo_element_nodes({});
  179. VERIFY(!element.needs_style_update());
  180. style = element.computed_css_values();
  181. display = style->display();
  182. if (display.is_none())
  183. return;
  184. layout_node = element.create_layout_node(*style);
  185. } else if (is<DOM::Document>(dom_node)) {
  186. style = style_computer.create_document_style();
  187. display = style->display();
  188. layout_node = adopt_ref(*new Layout::InitialContainingBlock(static_cast<DOM::Document&>(dom_node), *style));
  189. } else if (is<DOM::Text>(dom_node)) {
  190. layout_node = adopt_ref(*new Layout::TextNode(document, static_cast<DOM::Text&>(dom_node)));
  191. display = CSS::Display(CSS::Display::Outside::Inline, CSS::Display::Inside::Flow);
  192. } else if (is<DOM::ShadowRoot>(dom_node)) {
  193. layout_node = adopt_ref(*new Layout::BlockContainer(document, &static_cast<DOM::ShadowRoot&>(dom_node), CSS::ComputedValues {}));
  194. display = CSS::Display(CSS::Display::Outside::Block, CSS::Display::Inside::FlowRoot);
  195. }
  196. if (!layout_node)
  197. return;
  198. if (!dom_node.parent_or_shadow_host()) {
  199. m_layout_root = layout_node;
  200. } else if (layout_node->is_svg_box()) {
  201. m_ancestor_stack.last().append_child(*layout_node);
  202. } else {
  203. insert_node_into_inline_or_block_ancestor(*layout_node, display, AppendOrPrepend::Append);
  204. }
  205. auto* shadow_root = is<DOM::Element>(dom_node) ? verify_cast<DOM::Element>(dom_node).shadow_root() : nullptr;
  206. if ((dom_node.has_children() || shadow_root) && layout_node->can_have_children()) {
  207. push_parent(verify_cast<NodeWithStyle>(*layout_node));
  208. if (shadow_root)
  209. create_layout_tree(*shadow_root, context);
  210. verify_cast<DOM::ParentNode>(dom_node).for_each_child([&](auto& dom_child) {
  211. create_layout_tree(dom_child, context);
  212. });
  213. pop_parent();
  214. }
  215. // Add nodes for the ::before and ::after pseudo-elements.
  216. if (is<DOM::Element>(dom_node)) {
  217. auto& element = static_cast<DOM::Element&>(dom_node);
  218. push_parent(verify_cast<NodeWithStyle>(*layout_node));
  219. create_pseudo_element_if_needed(element, CSS::Selector::PseudoElement::Before, AppendOrPrepend::Prepend);
  220. create_pseudo_element_if_needed(element, CSS::Selector::PseudoElement::After, AppendOrPrepend::Append);
  221. pop_parent();
  222. }
  223. if (is<ListItemBox>(*layout_node)) {
  224. auto& element = static_cast<DOM::Element&>(dom_node);
  225. int child_index = layout_node->parent()->index_of_child<ListItemBox>(*layout_node).value();
  226. auto marker_style = style_computer.compute_style(element, CSS::Selector::PseudoElement::Marker);
  227. auto list_item_marker = adopt_ref(*new ListItemMarkerBox(document, layout_node->computed_values().list_style_type(), child_index + 1, *marker_style));
  228. static_cast<ListItemBox&>(*layout_node).set_marker(list_item_marker);
  229. element.set_pseudo_element_node({}, CSS::Selector::PseudoElement::Marker, list_item_marker);
  230. layout_node->append_child(move(list_item_marker));
  231. }
  232. if (is<HTML::HTMLProgressElement>(dom_node)) {
  233. auto& progress = static_cast<HTML::HTMLProgressElement&>(dom_node);
  234. if (!progress.using_system_appearance()) {
  235. auto bar_style = style_computer.compute_style(progress, CSS::Selector::PseudoElement::ProgressBar);
  236. bar_style->set_property(CSS::PropertyID::Display, CSS::IdentifierStyleValue::create(CSS::ValueID::InlineBlock));
  237. auto value_style = style_computer.compute_style(progress, CSS::Selector::PseudoElement::ProgressValue);
  238. value_style->set_property(CSS::PropertyID::Display, CSS::IdentifierStyleValue::create(CSS::ValueID::Block));
  239. auto position = progress.position();
  240. value_style->set_property(CSS::PropertyID::Width, CSS::PercentageStyleValue::create(CSS::Percentage(position >= 0 ? round_to<int>(100 * position) : 0)));
  241. auto bar_display = bar_style->display();
  242. auto value_display = value_style->display();
  243. auto progress_bar = DOM::Element::create_layout_node_for_display_type(document, bar_display, bar_style, nullptr);
  244. auto progress_value = DOM::Element::create_layout_node_for_display_type(document, value_display, value_style, nullptr);
  245. push_parent(verify_cast<NodeWithStyle>(*layout_node));
  246. push_parent(verify_cast<NodeWithStyle>(*progress_bar));
  247. insert_node_into_inline_or_block_ancestor(*progress_value, value_display, AppendOrPrepend::Append);
  248. pop_parent();
  249. insert_node_into_inline_or_block_ancestor(*progress_bar, bar_display, AppendOrPrepend::Append);
  250. pop_parent();
  251. progress.set_pseudo_element_node({}, CSS::Selector::PseudoElement::ProgressBar, progress_bar);
  252. progress.set_pseudo_element_node({}, CSS::Selector::PseudoElement::ProgressValue, progress_value);
  253. }
  254. }
  255. }
  256. RefPtr<Node> TreeBuilder::build(DOM::Node& dom_node)
  257. {
  258. VERIFY(dom_node.is_document());
  259. Context context;
  260. create_layout_tree(dom_node, context);
  261. if (auto* root = dom_node.document().layout_node())
  262. fixup_tables(*root);
  263. return move(m_layout_root);
  264. }
  265. template<CSS::Display::Internal internal, typename Callback>
  266. void TreeBuilder::for_each_in_tree_with_internal_display(NodeWithStyle& root, Callback callback)
  267. {
  268. root.for_each_in_inclusive_subtree_of_type<Box>([&](auto& box) {
  269. auto const display = box.display();
  270. if (display.is_internal() && display.internal() == internal)
  271. callback(box);
  272. return IterationDecision::Continue;
  273. });
  274. }
  275. template<CSS::Display::Inside inside, typename Callback>
  276. void TreeBuilder::for_each_in_tree_with_inside_display(NodeWithStyle& root, Callback callback)
  277. {
  278. root.for_each_in_inclusive_subtree_of_type<Box>([&](auto& box) {
  279. auto const display = box.display();
  280. if (display.is_outside_and_inside() && display.inside() == inside)
  281. callback(box);
  282. return IterationDecision::Continue;
  283. });
  284. }
  285. void TreeBuilder::fixup_tables(NodeWithStyle& root)
  286. {
  287. remove_irrelevant_boxes(root);
  288. generate_missing_child_wrappers(root);
  289. generate_missing_parents(root);
  290. }
  291. void TreeBuilder::remove_irrelevant_boxes(NodeWithStyle& root)
  292. {
  293. // The following boxes are discarded as if they were display:none:
  294. NonnullRefPtrVector<Node> to_remove;
  295. // Children of a table-column.
  296. for_each_in_tree_with_internal_display<CSS::Display::Internal::TableColumn>(root, [&](Box& table_column) {
  297. table_column.for_each_child([&](auto& child) {
  298. to_remove.append(child);
  299. });
  300. });
  301. // Children of a table-column-group which are not a table-column.
  302. for_each_in_tree_with_internal_display<CSS::Display::Internal::TableColumnGroup>(root, [&](Box& table_column_group) {
  303. table_column_group.for_each_child([&](auto& child) {
  304. if (child.display().is_table_column())
  305. to_remove.append(child);
  306. });
  307. });
  308. // FIXME:
  309. // Anonymous inline boxes which contain only white space and are between two immediate siblings each of which is a table-non-root box.
  310. // Anonymous inline boxes which meet all of the following criteria:
  311. // - they contain only white space
  312. // - they are the first and/or last child of a tabular container
  313. // - whose immediate sibling, if any, is a table-non-root box
  314. for (auto& box : to_remove)
  315. box.parent()->remove_child(box);
  316. }
  317. static bool is_table_track(CSS::Display display)
  318. {
  319. return display.is_table_row() || display.is_table_column();
  320. }
  321. static bool is_table_track_group(CSS::Display display)
  322. {
  323. // Unless explicitly mentioned otherwise, mentions of table-row-groups in this spec also encompass the specialized
  324. // table-header-groups and table-footer-groups.
  325. return display.is_table_row_group()
  326. || display.is_table_header_group()
  327. || display.is_table_footer_group()
  328. || display.is_table_column_group();
  329. }
  330. static bool is_not_proper_table_child(Node const& node)
  331. {
  332. if (!node.has_style())
  333. return true;
  334. auto const display = node.display();
  335. return !is_table_track_group(display) && !is_table_track(display) && !display.is_table_caption();
  336. }
  337. static bool is_not_table_row(Node const& node)
  338. {
  339. if (!node.has_style())
  340. return true;
  341. auto const display = node.display();
  342. return !display.is_table_row();
  343. }
  344. static bool is_not_table_cell(Node const& node)
  345. {
  346. if (!node.has_style())
  347. return true;
  348. auto const display = node.display();
  349. return !display.is_table_cell();
  350. }
  351. static bool is_ignorable_whitespace(Layout::Node const& node)
  352. {
  353. if (node.is_text_node() && static_cast<TextNode const&>(node).text_for_rendering().is_whitespace())
  354. return true;
  355. if (node.is_anonymous() && node.is_block_container() && static_cast<BlockContainer const&>(node).children_are_inline()) {
  356. bool contains_only_white_space = true;
  357. node.for_each_in_inclusive_subtree_of_type<TextNode>([&contains_only_white_space](auto& text_node) {
  358. if (!text_node.text_for_rendering().is_whitespace()) {
  359. contains_only_white_space = false;
  360. return IterationDecision::Break;
  361. }
  362. return IterationDecision::Continue;
  363. });
  364. if (contains_only_white_space)
  365. return true;
  366. }
  367. return false;
  368. }
  369. template<typename Matcher, typename Callback>
  370. static void for_each_sequence_of_consecutive_children_matching(NodeWithStyle& parent, Matcher matcher, Callback callback)
  371. {
  372. NonnullRefPtrVector<Node> sequence;
  373. auto sequence_is_all_ignorable_whitespace = [&]() -> bool {
  374. for (auto& node : sequence) {
  375. if (!is_ignorable_whitespace(node))
  376. return false;
  377. }
  378. return true;
  379. };
  380. Node* next_sibling = nullptr;
  381. for (auto* child = parent.first_child(); child; child = next_sibling) {
  382. next_sibling = child->next_sibling();
  383. if (matcher(*child)) {
  384. sequence.append(*child);
  385. } else {
  386. if (!sequence.is_empty()) {
  387. if (!sequence_is_all_ignorable_whitespace())
  388. callback(sequence, next_sibling);
  389. sequence.clear();
  390. }
  391. }
  392. }
  393. if (sequence.is_empty() && !sequence_is_all_ignorable_whitespace())
  394. callback(sequence, nullptr);
  395. }
  396. template<typename WrapperBoxType>
  397. static void wrap_in_anonymous(NonnullRefPtrVector<Node>& sequence, Node* nearest_sibling)
  398. {
  399. VERIFY(!sequence.is_empty());
  400. auto& parent = *sequence.first().parent();
  401. auto computed_values = parent.computed_values().clone_inherited_values();
  402. static_cast<CSS::MutableComputedValues&>(computed_values).set_display(WrapperBoxType::static_display());
  403. auto wrapper = adopt_ref(*new WrapperBoxType(parent.document(), nullptr, move(computed_values)));
  404. for (auto& child : sequence) {
  405. parent.remove_child(child);
  406. wrapper->append_child(child);
  407. }
  408. if (nearest_sibling)
  409. parent.insert_before(move(wrapper), *nearest_sibling);
  410. else
  411. parent.append_child(move(wrapper));
  412. }
  413. void TreeBuilder::generate_missing_child_wrappers(NodeWithStyle& root)
  414. {
  415. // An anonymous table-row box must be generated around each sequence of consecutive children of a table-root box which are not proper table child boxes.
  416. for_each_in_tree_with_inside_display<CSS::Display::Inside::Table>(root, [&](auto& parent) {
  417. for_each_sequence_of_consecutive_children_matching(parent, is_not_proper_table_child, [&](auto sequence, auto nearest_sibling) {
  418. wrap_in_anonymous<TableRowBox>(sequence, nearest_sibling);
  419. });
  420. });
  421. // An anonymous table-row box must be generated around each sequence of consecutive children of a table-row-group box which are not table-row boxes.
  422. for_each_in_tree_with_internal_display<CSS::Display::Internal::TableRowGroup>(root, [&](auto& parent) {
  423. for_each_sequence_of_consecutive_children_matching(parent, is_not_table_row, [&](auto& sequence, auto nearest_sibling) {
  424. wrap_in_anonymous<TableRowBox>(sequence, nearest_sibling);
  425. });
  426. });
  427. // Unless explicitly mentioned otherwise, mentions of table-row-groups in this spec also encompass the specialized
  428. // table-header-groups and table-footer-groups.
  429. for_each_in_tree_with_internal_display<CSS::Display::Internal::TableHeaderGroup>(root, [&](auto& parent) {
  430. for_each_sequence_of_consecutive_children_matching(parent, is_not_table_row, [&](auto& sequence, auto nearest_sibling) {
  431. wrap_in_anonymous<TableRowBox>(sequence, nearest_sibling);
  432. });
  433. });
  434. for_each_in_tree_with_internal_display<CSS::Display::Internal::TableFooterGroup>(root, [&](auto& parent) {
  435. for_each_sequence_of_consecutive_children_matching(parent, is_not_table_row, [&](auto& sequence, auto nearest_sibling) {
  436. wrap_in_anonymous<TableRowBox>(sequence, nearest_sibling);
  437. });
  438. });
  439. // An anonymous table-cell box must be generated around each sequence of consecutive children of a table-row box which are not table-cell boxes. !Testcase
  440. for_each_in_tree_with_internal_display<CSS::Display::Internal::TableRow>(root, [&](auto& parent) {
  441. for_each_sequence_of_consecutive_children_matching(parent, is_not_table_cell, [&](auto& sequence, auto nearest_sibling) {
  442. wrap_in_anonymous<TableCellBox>(sequence, nearest_sibling);
  443. });
  444. });
  445. }
  446. void TreeBuilder::generate_missing_parents(NodeWithStyle&)
  447. {
  448. // FIXME: Implement.
  449. }
  450. }