jcs.org
Serenity Operating System
1/*
2 * Copyright (c) 2022, Andreas Kling <kling@serenityos.org>
3 *
4 * SPDX-License-Identifier: BSD-2-Clause
5 */
6
7#include <LibWeb/Layout/BlockFormattingContext.h>
8#include <LibWeb/Layout/LineBuilder.h>
9#include <LibWeb/Layout/TextNode.h>
10
11namespace Web::Layout {
12
13LineBuilder::LineBuilder(InlineFormattingContext& context, LayoutState& layout_state)
14 : m_context(context)
15 , m_layout_state(layout_state)
16 , m_containing_block_state(layout_state.get_mutable(context.containing_block()))
17{
18 begin_new_line(false);
19}
20
21LineBuilder::~LineBuilder()
22{
23 if (m_last_line_needs_update)
24 update_last_line();
25}
26
27void LineBuilder::break_line(Optional<CSSPixels> next_item_width)
28{
29 update_last_line();
30 size_t break_count = 0;
31 bool floats_intrude_at_current_y = false;
32 do {
33 m_containing_block_state.line_boxes.append(LineBox());
34 begin_new_line(true, break_count == 0);
35 break_count++;
36 floats_intrude_at_current_y = m_context.any_floats_intrude_at_y(m_current_y);
37 } while ((floats_intrude_at_current_y && !m_context.can_fit_new_line_at_y(m_current_y))
38 || (next_item_width.has_value()
39 && next_item_width.value() > m_available_width_for_current_line
40 && floats_intrude_at_current_y));
41}
42
43void LineBuilder::begin_new_line(bool increment_y, bool is_first_break_in_sequence)
44{
45 if (increment_y) {
46 if (is_first_break_in_sequence) {
47 // First break is simple, just go to the start of the next line.
48 m_current_y += max(m_max_height_on_current_line, m_context.containing_block().line_height());
49 } else {
50 // We're doing more than one break in a row.
51 // This means we're trying to squeeze past intruding floats.
52 // Scan 1px at a time until we find a Y value where a new line can fit.
53 // FIXME: This is super dumb and inefficient.
54 CSSPixels candidate_y = m_current_y + 1;
55 while (true) {
56 if (m_context.can_fit_new_line_at_y(candidate_y))
57 break;
58 ++candidate_y;
59 }
60 m_current_y = candidate_y;
61 }
62 }
63 recalculate_available_space();
64 m_max_height_on_current_line = 0;
65 m_last_line_needs_update = true;
66}
67
68LineBox& LineBuilder::ensure_last_line_box()
69{
70 auto& line_boxes = m_containing_block_state.line_boxes;
71 if (line_boxes.is_empty())
72 line_boxes.append(LineBox {});
73 return line_boxes.last();
74}
75
76void LineBuilder::append_box(Box const& box, CSSPixels leading_size, CSSPixels trailing_size, CSSPixels leading_margin, CSSPixels trailing_margin)
77{
78 auto& box_state = m_layout_state.get_mutable(box);
79 auto& line_box = ensure_last_line_box();
80 line_box.add_fragment(box, 0, 0, leading_size, trailing_size, leading_margin, trailing_margin, box_state.content_width(), box_state.content_height(), box_state.border_box_top(), box_state.border_box_bottom());
81 m_max_height_on_current_line = max(m_max_height_on_current_line, box_state.border_box_height());
82
83 box_state.containing_line_box_fragment = LineBoxFragmentCoordinate {
84 .line_box_index = m_containing_block_state.line_boxes.size() - 1,
85 .fragment_index = line_box.fragments().size() - 1,
86 };
87}
88
89void LineBuilder::append_text_chunk(TextNode const& text_node, size_t offset_in_node, size_t length_in_node, CSSPixels leading_size, CSSPixels trailing_size, CSSPixels leading_margin, CSSPixels trailing_margin, CSSPixels content_width, CSSPixels content_height)
90{
91 ensure_last_line_box().add_fragment(text_node, offset_in_node, length_in_node, leading_size, trailing_size, leading_margin, trailing_margin, content_width, content_height, 0, 0);
92 m_max_height_on_current_line = max(m_max_height_on_current_line, content_height);
93}
94
95CSSPixels LineBuilder::y_for_float_to_be_inserted_here(Box const& box)
96{
97 auto const& box_state = m_layout_state.get(box);
98 CSSPixels const width = box_state.margin_box_width();
99 CSSPixels const height = box_state.margin_box_height();
100
101 CSSPixels candidate_y = m_current_y;
102
103 CSSPixels current_line_width = ensure_last_line_box().width();
104 // If there's already inline content on the current line, check if the new float can fit
105 // alongside the content. If not, place it on the next line.
106 if (current_line_width > 0 && (current_line_width + width) > m_available_width_for_current_line)
107 candidate_y += m_context.containing_block().line_height();
108
109 // Then, look for the next Y position where we can fit the new float.
110 // FIXME: This is super dumb, we move 1px downwards per iteration and stop
111 // when we find an Y value where we don't collide with other floats.
112 while (true) {
113 auto space_at_y_top = m_context.available_space_for_line(candidate_y);
114 auto space_at_y_bottom = m_context.available_space_for_line(candidate_y + height);
115 if (width > space_at_y_top || width > space_at_y_bottom) {
116 if (!m_context.any_floats_intrude_at_y(candidate_y) && !m_context.any_floats_intrude_at_y(candidate_y + height)) {
117 return candidate_y;
118 }
119 } else {
120 return candidate_y;
121 }
122 candidate_y += 1;
123 }
124}
125
126bool LineBuilder::should_break(CSSPixels next_item_width)
127{
128 if (!isfinite(m_available_width_for_current_line.value()))
129 return false;
130
131 auto const& line_boxes = m_containing_block_state.line_boxes;
132 if (line_boxes.is_empty() || line_boxes.last().is_empty()) {
133 // If we don't have a single line box yet *and* there are no floats intruding
134 // at this Y coordinate, we don't need to break before inserting anything.
135 if (!m_context.any_floats_intrude_at_y(m_current_y))
136 return false;
137 if (!m_context.any_floats_intrude_at_y(m_current_y + m_context.containing_block().line_height()))
138 return false;
139 }
140 auto current_line_width = ensure_last_line_box().width();
141 return (current_line_width + next_item_width) > m_available_width_for_current_line;
142}
143
144void LineBuilder::update_last_line()
145{
146 m_last_line_needs_update = false;
147 auto& line_boxes = m_containing_block_state.line_boxes;
148
149 if (line_boxes.is_empty())
150 return;
151
152 auto& line_box = line_boxes.last();
153
154 auto text_align = m_context.containing_block().computed_values().text_align();
155
156 auto current_line_height = max(m_max_height_on_current_line, m_context.containing_block().line_height());
157 CSSPixels x_offset_top = m_context.leftmost_x_offset_at(m_current_y);
158 CSSPixels x_offset_bottom = m_context.leftmost_x_offset_at(m_current_y + current_line_height - 1);
159 CSSPixels x_offset = max(x_offset_top, x_offset_bottom);
160
161 // If the IFC's containing block has left-side margin, it has already been shifted to the right by that amount.
162 // We subtract the margin-left here to ensure that the left-side "space used by floats" doesn't get applied twice.
163 x_offset = max(CSSPixels(0), x_offset - m_containing_block_state.margin_left);
164
165 CSSPixels excess_horizontal_space = m_available_width_for_current_line - line_box.width();
166
167 switch (text_align) {
168 case CSS::TextAlign::Center:
169 case CSS::TextAlign::LibwebCenter:
170 x_offset += excess_horizontal_space / 2;
171 break;
172 case CSS::TextAlign::Right:
173 x_offset += excess_horizontal_space;
174 break;
175 case CSS::TextAlign::Left:
176 case CSS::TextAlign::Justify:
177 default:
178 break;
179 }
180
181 auto strut_baseline = [&] {
182 auto& font = m_context.containing_block().font();
183 auto const line_height = m_context.containing_block().line_height();
184 auto const font_metrics = font.pixel_metrics();
185 auto const typographic_height = font_metrics.ascent + font_metrics.descent;
186 auto const leading = line_height - typographic_height;
187 auto const half_leading = leading / 2;
188 return CSSPixels(font_metrics.ascent) + half_leading;
189 }();
190
191 auto line_box_baseline = [&] {
192 CSSPixels line_box_baseline = strut_baseline;
193 for (auto& fragment : line_box.fragments()) {
194 auto const& font = fragment.layout_node().font();
195 auto const line_height = fragment.layout_node().line_height();
196 auto const font_metrics = font.pixel_metrics();
197 auto const typographic_height = CSSPixels(font_metrics.ascent + font_metrics.descent);
198 auto const leading = line_height - typographic_height;
199 auto const half_leading = leading / 2;
200
201 // The CSS specification calls this AD (A+D, Ascent + Descent).
202
203 CSSPixels fragment_baseline = 0;
204 if (fragment.layout_node().is_text_node()) {
205 fragment_baseline = CSSPixels(font_metrics.ascent) + half_leading;
206 } else {
207 auto const& box = verify_cast<Layout::Box>(fragment.layout_node());
208 fragment_baseline = box_baseline(m_layout_state, box);
209 }
210
211 // Remember the baseline used for this fragment. This will be used when painting the fragment.
212 fragment.set_baseline(fragment_baseline);
213
214 // NOTE: For fragments with a <length> vertical-align, shift the line box baseline down by the length.
215 // This ensures that we make enough vertical space on the line for any manually-aligned fragments.
216 if (auto length_percentage = fragment.layout_node().computed_values().vertical_align().template get_pointer<CSS::LengthPercentage>(); length_percentage && length_percentage->is_length())
217 fragment_baseline += length_percentage->length().to_px(fragment.layout_node());
218
219 line_box_baseline = max(line_box_baseline, fragment_baseline);
220 }
221 return line_box_baseline;
222 }();
223
224 // Start with the "strut", an imaginary zero-width box at the start of each line box.
225 auto strut_top = m_current_y;
226 auto strut_bottom = m_current_y + m_context.containing_block().line_height();
227
228 CSSPixels uppermost_box_top = strut_top;
229 CSSPixels lowermost_box_bottom = strut_bottom;
230
231 for (size_t i = 0; i < line_box.fragments().size(); ++i) {
232 auto& fragment = line_box.fragments()[i];
233
234 CSSPixels new_fragment_x = round(x_offset + fragment.offset().x());
235 CSSPixels new_fragment_y = 0;
236
237 auto y_value_for_alignment = [&](CSS::VerticalAlign vertical_align) {
238 switch (vertical_align) {
239 case CSS::VerticalAlign::Baseline:
240 return m_current_y + line_box_baseline - fragment.baseline() + fragment.border_box_top();
241 case CSS::VerticalAlign::Top:
242 return m_current_y + fragment.border_box_top();
243 case CSS::VerticalAlign::Middle:
244 case CSS::VerticalAlign::Bottom:
245 case CSS::VerticalAlign::Sub:
246 case CSS::VerticalAlign::Super:
247 case CSS::VerticalAlign::TextBottom:
248 case CSS::VerticalAlign::TextTop:
249 // FIXME: These are all 'baseline'
250 return m_current_y + line_box_baseline - fragment.baseline() + fragment.border_box_top();
251 }
252 VERIFY_NOT_REACHED();
253 };
254
255 auto const& vertical_align = fragment.layout_node().computed_values().vertical_align();
256 if (vertical_align.has<CSS::VerticalAlign>()) {
257 new_fragment_y = y_value_for_alignment(vertical_align.get<CSS::VerticalAlign>());
258 } else {
259 if (auto length_percentage = vertical_align.get_pointer<CSS::LengthPercentage>(); length_percentage && length_percentage->is_length()) {
260 auto vertical_align_amount = length_percentage->length().to_px(fragment.layout_node());
261 new_fragment_y = y_value_for_alignment(CSS::VerticalAlign::Baseline) - vertical_align_amount;
262 }
263 }
264
265 fragment.set_offset({ new_fragment_x, floor(new_fragment_y) });
266
267 CSSPixels top_of_inline_box = 0;
268 CSSPixels bottom_of_inline_box = 0;
269 {
270 // FIXME: Support inline-table elements.
271 if (fragment.layout_node().is_replaced_box() || (fragment.layout_node().display().is_inline_outside() && !fragment.layout_node().display().is_flow_inside())) {
272 auto const& fragment_box_state = m_layout_state.get(static_cast<Box const&>(fragment.layout_node()));
273 top_of_inline_box = (fragment.offset().y() - fragment_box_state.margin_box_top());
274 bottom_of_inline_box = (fragment.offset().y() + fragment_box_state.content_height() + fragment_box_state.margin_box_bottom());
275 } else {
276 auto font_metrics = fragment.layout_node().font().pixel_metrics();
277 auto typographic_height = font_metrics.ascent + font_metrics.descent;
278 auto leading = fragment.layout_node().line_height() - typographic_height;
279 auto half_leading = leading / 2;
280 top_of_inline_box = (fragment.offset().y() + fragment.baseline() - font_metrics.ascent - half_leading);
281 bottom_of_inline_box = (fragment.offset().y() + fragment.baseline() + font_metrics.descent + half_leading);
282 }
283 if (auto length_percentage = fragment.layout_node().computed_values().vertical_align().template get_pointer<CSS::LengthPercentage>(); length_percentage && length_percentage->is_length())
284 bottom_of_inline_box += length_percentage->length().to_px(fragment.layout_node());
285 }
286
287 uppermost_box_top = min(uppermost_box_top, top_of_inline_box);
288 lowermost_box_bottom = max(lowermost_box_bottom, bottom_of_inline_box);
289 }
290
291 // 3. The line box height is the distance between the uppermost box top and the lowermost box bottom.
292 line_box.m_height = lowermost_box_bottom - uppermost_box_top;
293
294 line_box.m_bottom = m_current_y + line_box.m_height;
295 line_box.m_baseline = line_box_baseline;
296}
297
298void LineBuilder::remove_last_line_if_empty()
299{
300 // If there's an empty line box at the bottom, just remove it instead of giving it height.
301 auto& line_boxes = m_containing_block_state.line_boxes;
302 if (!line_boxes.is_empty() && line_boxes.last().fragments().is_empty()) {
303 line_boxes.take_last();
304 m_last_line_needs_update = false;
305 }
306}
307
308void LineBuilder::recalculate_available_space()
309{
310 auto current_line_height = max(m_max_height_on_current_line, m_context.containing_block().line_height());
311 auto available_at_top_of_line_box = m_context.available_space_for_line(m_current_y);
312 auto available_at_bottom_of_line_box = m_context.available_space_for_line(m_current_y + current_line_height - 1);
313 m_available_width_for_current_line = min(available_at_bottom_of_line_box, available_at_top_of_line_box);
314}
315
316}