Skip to main content

layout/flow/inline/
line.rs

1/* This Source Code Form is subject to the terms of the Mozilla Public
2 * License, v. 2.0. If a copy of the MPL was not distributed with this
3 * file, You can obtain one at https://mozilla.org/MPL/2.0/. */
4
5use std::ops::Range;
6use std::rc::Rc;
7use std::sync::Arc;
8
9use app_units::Au;
10use bitflags::bitflags;
11use fonts::{ShapedTextSlice, TrailingWhiteSpace};
12use itertools::Either;
13use servo_base::text::Utf32CodeUnits;
14use style::Zero;
15use style::computed_values::position::T as Position;
16use style::values::computed::BaselineShift;
17use style::values::generics::box_::BaselineShiftKeyword;
18use style::values::specified::align::AlignFlags;
19use style::values::specified::box_::DisplayOutside;
20use unicode_bidi::{BidiInfo, Level};
21
22use super::inline_box::{InlineBoxContainerState, InlineBoxIdentifier, InlineBoxTreePathToken};
23use super::{InlineFormattingContextLayout, LineBlockSizes, line_height};
24use crate::cell::ArcRefCell;
25use crate::containing_block::{ContainingBlock, ContainingBlockSize};
26use crate::flow::inline::text_run::{FontAndScriptInfo, SharedTextRunData};
27use crate::fragment_tree::{
28    BaseFragment, BaseFragmentInfo, BoxFragment, Fragment, FragmentAndLogicalRect,
29    FragmentChildren, FragmentFlags, TextFragment,
30};
31use crate::geom::{LogicalRect, LogicalSides, LogicalVec2, PhysicalRect, PhysicalSize};
32use crate::positioned::{
33    AbsolutelyPositionedBox, PositioningContext, PositioningContextLength, StaticPositionRect,
34    relative_adjustement,
35};
36
37pub(super) struct LineMetrics {
38    /// The block offset of the line start in the containing
39    /// [`crate::flow::InlineFormattingContext`].
40    pub block_offset: Au,
41
42    /// The block size of this line.
43    pub block_size: Au,
44
45    /// The block offset of this line's baseline from [`Self::block_offset`].
46    pub baseline_block_offset: Au,
47}
48
49bitflags! {
50    struct LineLayoutInlineContainerFlags: u8 {
51        /// Whether or not any line items were processed for this inline box, this includes
52        /// any child inline boxes.
53        const HAD_ANY_LINE_ITEMS = 1 << 0;
54        /// Whether or not the starting inline border, padding, or margin of the inline box
55        /// was encountered.
56        const HAD_INLINE_START_PBM = 1 << 2;
57        /// Whether or not the ending inline border, padding, or margin of the inline box
58        /// was encountered.
59        const HAD_INLINE_END_PBM = 1 << 3;
60        /// Whether or not any floats were encountered while laying out this inline box.
61        const HAD_ANY_FLOATS = 1 << 4;
62    }
63}
64
65struct FragmentAndData {
66    /// The [`FragmentAndLogicalRect`] used to determine this fragment's final physical
67    /// rectangle.
68    fragment_and_rect: FragmentAndLogicalRect,
69    /// If the fragment is for an inline box, this is the list of floats which are either
70    /// direct children or descendants within other inline boxes. Once the final physical
71    /// rect of the fragment is known, the position of these floats needs to be adjusted.
72    propagated_floats: Vec<Arc<BoxFragment>>,
73}
74
75impl FragmentAndData {
76    fn new(fragment_and_rect: FragmentAndLogicalRect) -> Self {
77        Self::new_with_propagated_floats(fragment_and_rect, Vec::new())
78    }
79
80    fn new_with_propagated_floats(
81        fragment_and_rect: FragmentAndLogicalRect,
82        propagated_floats: Vec<Arc<BoxFragment>>,
83    ) -> Self {
84        Self {
85            fragment_and_rect,
86            propagated_floats,
87        }
88    }
89
90    /// Updates the physical rect of the fragment, by resolving the logical rect against the
91    /// size and writing mode of the container.
92    /// Note that the container isn't necessarily the containing block, it can be a fragment
93    /// of an inline box.
94    /// This shouldn't be used for floats, since they are anchored to a side of the inline
95    /// formatting context, not to their container.
96    fn resolve_physical_rect_and_adjust_floats(&self, container: &ContainingBlock) {
97        debug_assert!(!matches!(
98            self.fragment_and_rect.fragment,
99            Fragment::Float(_)
100        ));
101
102        let Some(base) = self.fragment_and_rect.fragment.base() else {
103            return;
104        };
105
106        // We do not know the actual physical position of a logically laid out inline element, until
107        // we know the width of the containing inline block. This step converts the logical rectangle
108        // into a physical one based on the inline formatting context width.
109        let rect = self
110            .fragment_and_rect
111            .logical_rect
112            .as_physical_deprecated(container);
113        base.set_rect(rect);
114
115        // Floats are anchored to a side of the inline formatting context, but in the box tree
116        // they can still be children of an inline box. Since the coordinates will be relative
117        // to their parent, when setting the final position of that parent, we need to adjust
118        // the float in order to keep it at the desired position.
119        let float_offset = -rect.origin.to_vector().to_size();
120        for float_fragment in &self.propagated_floats {
121            float_fragment.base.translate_rect(float_offset);
122        }
123    }
124
125    /// Given a vector of [`FragmentAndData`], this resolves the final physical rect for each
126    /// non-floating fragment (storing it), and adjusts the position of the floats inside it,
127    /// then returns a vector with the [`Fragment`]s.
128    fn resolve_physical_rects_and_adjust_floats(
129        fragments_and_data: Vec<Self>,
130        container: &ContainingBlock,
131    ) -> Vec<Fragment> {
132        let mut fragments = Vec::with_capacity(fragments_and_data.len());
133        for fragment_and_data in fragments_and_data {
134            if !matches!(
135                fragment_and_data.fragment_and_rect.fragment,
136                Fragment::Float(_)
137            ) {
138                fragment_and_data.resolve_physical_rect_and_adjust_floats(container)
139            }
140            fragments.push(fragment_and_data.fragment_and_rect.fragment);
141        }
142        fragments
143    }
144
145    /// Same as [`resolve_physical_rects_and_adjust_floats()`], but additionally it takes
146    /// a relative adjustment that will be applied to floats. And the return value is a
147    /// pair of the [`Fragment`]s and the propagated floats.
148    fn resolve_physical_rects_and_adjust_and_collect_floats(
149        fragments_and_data: Vec<Self>,
150        container: &ContainingBlock,
151        relative_adjustement: PhysicalSize<Au>,
152    ) -> (Vec<Fragment>, Vec<Arc<BoxFragment>>) {
153        let mut fragments = Vec::with_capacity(fragments_and_data.len());
154        let mut propagated_floats = Vec::new();
155        for mut fragment_and_data in fragments_and_data {
156            if let Fragment::Float(ref float) = fragment_and_data.fragment_and_rect.fragment {
157                if relative_adjustement != PhysicalSize::zero() {
158                    float.base.translate_rect(relative_adjustement);
159                }
160                propagated_floats.push(float.clone());
161            } else {
162                fragment_and_data.resolve_physical_rect_and_adjust_floats(container)
163            }
164            fragments.push(fragment_and_data.fragment_and_rect.fragment);
165            propagated_floats.append(&mut fragment_and_data.propagated_floats);
166        }
167        (fragments, propagated_floats)
168    }
169}
170
171/// The state used when laying out a collection of [`LineItem`]s into a line. This state is stored
172/// per-inline container. For instance, when laying out the conents of a `<span>` a fresh
173/// [`LineItemLayoutInlineContainerState`] is pushed onto [`LineItemLayout`]'s stack of states.
174pub(super) struct LineItemLayoutInlineContainerState {
175    /// If this inline container is not the root inline container, the identifier of the [`super::InlineBox`]
176    /// that is currently being laid out.
177    pub identifier: Option<InlineBoxIdentifier>,
178
179    /// The fragments and their associated data.
180    fragments_and_data: Vec<FragmentAndData>,
181
182    /// The current inline advance of the layout in the coordinates of this inline box.
183    pub inline_advance: Au,
184
185    /// Flags which track various features during layout.
186    flags: LineLayoutInlineContainerFlags,
187
188    /// The offset of the parent, relative to the start position of the line, not including
189    /// any inline start and end padding/border/margin, which are only processed when the
190    /// inline box is finished. However, it includes padding/border in the block axis.
191    pub parent_offset: LogicalVec2<Au>,
192
193    /// The block offset of the parent's baseline relative to the block start of the line. This
194    /// is often the same as [`Self::parent_offset`], but can be different for the root
195    /// element.
196    pub baseline_offset: Au,
197
198    /// If this inline box establishes a containing block for positioned elements, this
199    /// is a fresh positioning context to contain them. Otherwise, this holds the starting
200    /// offset in the *parent* positioning context so that static positions can be updated
201    /// at the end of layout.
202    pub positioning_context_or_start_offset_in_parent:
203        Either<PositioningContext, PositioningContextLength>,
204}
205
206impl LineItemLayoutInlineContainerState {
207    fn new(
208        identifier: Option<InlineBoxIdentifier>,
209        parent_offset: LogicalVec2<Au>,
210        baseline_offset: Au,
211        positioning_context_or_start_offset_in_parent: Either<
212            PositioningContext,
213            PositioningContextLength,
214        >,
215    ) -> Self {
216        Self {
217            identifier,
218            fragments_and_data: Vec::new(),
219            inline_advance: Au::zero(),
220            flags: LineLayoutInlineContainerFlags::empty(),
221            parent_offset,
222            baseline_offset,
223            positioning_context_or_start_offset_in_parent,
224        }
225    }
226
227    fn root(starting_inline_advance: Au, baseline_offset: Au) -> Self {
228        let mut state = Self::new(
229            None,
230            LogicalVec2::zero(),
231            baseline_offset,
232            Either::Right(PositioningContextLength::zero()),
233        );
234        state.inline_advance = starting_inline_advance;
235        state
236    }
237}
238
239/// The second phase of [`super::InlineFormattingContext`] layout: once items are gathered
240/// for a line, we must lay them out and create fragments for them, properly positioning them
241/// according to their baselines and also handling absolutely positioned children.
242pub(super) struct LineItemLayout<'layout_data, 'layout> {
243    /// The state of the overall [`super::InlineFormattingContext`] layout.
244    layout: &'layout mut InlineFormattingContextLayout<'layout_data>,
245
246    /// The set of [`LineItemLayoutInlineContainerState`] created while laying out items
247    /// on this line. This does not include the current level of recursion.
248    pub state_stack: Vec<LineItemLayoutInlineContainerState>,
249
250    /// The current [`LineItemLayoutInlineContainerState`].
251    pub current_state: LineItemLayoutInlineContainerState,
252
253    /// The metrics of this line, which should remain constant throughout the
254    /// layout process.
255    pub line_metrics: LineMetrics,
256
257    /// The amount of space to add to each justification opportunity in order to implement
258    /// `text-align: justify`.
259    pub justification_adjustment: Au,
260
261    /// Whether this is a phantom line box.
262    /// <https://drafts.csswg.org/css-inline-3/#invisible-line-boxes>
263    is_phantom_line: bool,
264
265    /// Whether this line contains only a block-level box.
266    for_block_level: bool,
267}
268
269impl LineItemLayout<'_, '_> {
270    pub(super) fn layout_line_items(
271        layout: &mut InlineFormattingContextLayout,
272        line_items: Vec<LineItem>,
273        start_position: LogicalVec2<Au>,
274        effective_block_advance: &LineBlockSizes,
275        justification_adjustment: Au,
276        is_phantom_line: bool,
277        for_block_level: bool,
278    ) -> Vec<Fragment> {
279        let baseline_offset = effective_block_advance.find_baseline_offset();
280        LineItemLayout {
281            layout,
282            state_stack: Vec::new(),
283            current_state: LineItemLayoutInlineContainerState::root(
284                start_position.inline,
285                baseline_offset,
286            ),
287            line_metrics: LineMetrics {
288                block_offset: start_position.block,
289                block_size: effective_block_advance.resolve(),
290                baseline_block_offset: baseline_offset,
291            },
292            justification_adjustment,
293            is_phantom_line,
294            for_block_level,
295        }
296        .layout(line_items)
297    }
298
299    /// Start and end inline boxes in tree order, so that it reflects the given inline box.
300    fn prepare_layout_for_inline_box(&mut self, new_inline_box: Option<InlineBoxIdentifier>) {
301        // Optimize the case where we are moving to the root of the inline box stack.
302        let Some(new_inline_box) = new_inline_box else {
303            while !self.state_stack.is_empty() {
304                self.end_inline_box();
305            }
306            return;
307        };
308
309        // Otherwise, follow the path given to us by our collection of inline boxes, so we know which
310        // inline boxes to start and end.
311        let path = self
312            .layout
313            .ifc
314            .inline_boxes
315            .get_path(self.current_state.identifier, new_inline_box);
316        for token in path {
317            match token {
318                InlineBoxTreePathToken::Start(ref identifier) => self.start_inline_box(identifier),
319                InlineBoxTreePathToken::End(_) => self.end_inline_box(),
320            }
321        }
322    }
323
324    /// If the inline formatting context that this line is being laid out for had
325    /// right-to-left content, reorder the line contents according to their pre-calculated
326    /// BiDi levels.
327    ///
328    /// Returns an iterator over the line contents.
329    fn reorder_line_items_for_bidi(
330        &self,
331        mut line_items: Vec<LineItem>,
332    ) -> impl Iterator<Item = LineItem> + use<> {
333        let iterator = |line_items: Vec<LineItem>| {
334            // `BidiInfo::reorder_visual` will reorder the contents of the line so that they
335            // are in the correct order as if one was looking at the line from left-to-right.
336            // During this layout we do not lay out from left to right. Instead we lay out
337            // from inline-start to inline-end. If the overall line contents have been flipped
338            // for BiDi, flip them again so that they are in line start-to-end order rather
339            // than left-to-right order.
340            if self.containing_block().style.writing_mode.is_bidi_ltr() {
341                Either::Left(line_items.into_iter())
342            } else {
343                Either::Right(line_items.into_iter().rev())
344            }
345        };
346
347        if !self.layout.ifc.has_right_to_left_content {
348            // Even if the actual content of the inline formatting context does not
349            // contain internal right-to-left text, the overall direction of the inline
350            // formatting context might be right-to-left. In that case we still want to
351            // return a reverse iterator.
352            return iterator(line_items);
353        }
354
355        let mut last_level = Level::ltr();
356        let levels: Vec<_> = line_items
357            .iter()
358            .map(|item| {
359                let level = match item {
360                    LineItem::TextRun(_, text_run) => text_run.info.font_info.bidi_level,
361                    // TODO: This level needs either to be last_level, or if there were
362                    // unicode characters inserted for the inline box, we need to get the
363                    // level from them.
364                    LineItem::InlineStartBoxPaddingBorderMargin(_) => last_level,
365                    LineItem::InlineEndBoxPaddingBorderMargin(_) => last_level,
366                    LineItem::Atomic(_, atomic) => atomic.bidi_level,
367                    LineItem::AbsolutelyPositioned(..) => last_level,
368                    LineItem::Float(..) => {
369                        // At this point the float is already positioned, so it doesn't really matter what
370                        // position it's fragment has in the order of line items.
371                        last_level
372                    },
373                    LineItem::BlockLevel(..) => last_level,
374                    LineItem::Tab { bidi_level, .. } => *bidi_level,
375                };
376                last_level = level;
377                level
378            })
379            .collect();
380
381        sort_by_indices_in_place(&mut line_items, BidiInfo::reorder_visual(&levels));
382        iterator(line_items)
383    }
384
385    pub(super) fn layout(&mut self, line_items: Vec<LineItem>) -> Vec<Fragment> {
386        let line_item_iterator = self.reorder_line_items_for_bidi(line_items);
387        for item in line_item_iterator.into_iter().by_ref() {
388            // When preparing to lay out a new line item, start and end inline boxes, so that the current
389            // inline box state reflects the item's parent. Items in the line are not necessarily in tree
390            // order due to BiDi and other reordering so the inline box of the item could potentially be
391            // any in the inline formatting context.
392            self.prepare_layout_for_inline_box(item.inline_box_identifier());
393
394            self.current_state
395                .flags
396                .insert(LineLayoutInlineContainerFlags::HAD_ANY_LINE_ITEMS);
397            match item {
398                LineItem::InlineStartBoxPaddingBorderMargin(_) => {
399                    self.current_state
400                        .flags
401                        .insert(LineLayoutInlineContainerFlags::HAD_INLINE_START_PBM);
402                },
403                LineItem::InlineEndBoxPaddingBorderMargin(_) => {
404                    self.current_state
405                        .flags
406                        .insert(LineLayoutInlineContainerFlags::HAD_INLINE_END_PBM);
407                },
408                LineItem::TextRun(_, text_run) => self.layout_text_run(text_run),
409                LineItem::Atomic(_, atomic) => self.layout_atomic(atomic),
410                LineItem::AbsolutelyPositioned(_, absolute) => self.layout_absolute(absolute),
411                LineItem::Float(_, float) => self.layout_float(float),
412                LineItem::BlockLevel(_, block_level) => self.layout_block_level(block_level),
413                LineItem::Tab { advance, .. } => self.layout_tab(advance),
414            }
415        }
416
417        // Move back to the root of the inline box tree, so that all boxes are ended.
418        self.prepare_layout_for_inline_box(None);
419
420        FragmentAndData::resolve_physical_rects_and_adjust_floats(
421            std::mem::take(&mut self.current_state.fragments_and_data),
422            self.layout.containing_block(),
423        )
424    }
425
426    fn current_positioning_context_mut(&mut self) -> &mut PositioningContext {
427        if let Either::Left(ref mut positioning_context) = self
428            .current_state
429            .positioning_context_or_start_offset_in_parent
430        {
431            return positioning_context;
432        }
433        self.state_stack
434            .iter_mut()
435            .rev()
436            .find_map(
437                |state| match state.positioning_context_or_start_offset_in_parent {
438                    Either::Left(ref mut positioning_context) => Some(positioning_context),
439                    Either::Right(_) => None,
440                },
441            )
442            .unwrap_or(self.layout.positioning_context)
443    }
444
445    fn start_inline_box(&mut self, identifier: &InlineBoxIdentifier) {
446        let inline_box_state =
447            &*self.layout.inline_box_states[identifier.index_in_inline_boxes as usize];
448        let inline_box = self.layout.ifc.inline_boxes.get(identifier);
449        let inline_box = &*(inline_box.borrow());
450
451        let space_above_baseline = inline_box_state.calculate_space_above_baseline();
452        let block_start_offset =
453            self.calculate_inline_box_block_start(inline_box_state, space_above_baseline);
454
455        let positioning_context_or_start_offset_in_parent =
456            match PositioningContext::new_for_layout_box_base(&inline_box.base) {
457                Some(positioning_context) => Either::Left(positioning_context),
458                None => Either::Right(self.current_positioning_context_mut().len()),
459            };
460
461        let parent_offset = LogicalVec2 {
462            inline: self.current_state.inline_advance + self.current_state.parent_offset.inline,
463            block: block_start_offset,
464        };
465
466        let outer_state = std::mem::replace(
467            &mut self.current_state,
468            LineItemLayoutInlineContainerState::new(
469                Some(*identifier),
470                parent_offset,
471                block_start_offset + space_above_baseline,
472                positioning_context_or_start_offset_in_parent,
473            ),
474        );
475
476        self.state_stack.push(outer_state);
477    }
478
479    fn end_inline_box(&mut self) {
480        let outer_state = self.state_stack.pop().expect("Ended unknown inline box");
481        let inner_state = std::mem::replace(&mut self.current_state, outer_state);
482
483        let identifier = inner_state.identifier.expect("Ended unknown inline box");
484        let inline_box_state =
485            &*self.layout.inline_box_states[identifier.index_in_inline_boxes as usize];
486        let inline_box = self.layout.ifc.inline_boxes.get(&identifier);
487        let inline_box = &*(inline_box.borrow());
488
489        let containing_block = self.layout.containing_block();
490        let containing_block_writing_mode = containing_block.style.writing_mode;
491
492        let mut padding = inline_box_state.pbm.padding;
493        let mut border = inline_box_state.pbm.border;
494        let mut margin = inline_box_state.pbm.margin.auto_is(Au::zero);
495        // PBM must not be cloned onto lines that exist only to support a block-level box.
496        // See https://github.com/w3c/csswg-drafts/issues/14104
497        if self.for_block_level {
498            padding = LogicalSides::zero();
499            border = LogicalSides::zero();
500            margin = LogicalSides::zero();
501        } else if !inline_box_state.should_clone_pbm() {
502            let mut had_start = inner_state
503                .flags
504                .contains(LineLayoutInlineContainerFlags::HAD_INLINE_START_PBM);
505            let mut had_end = inner_state
506                .flags
507                .contains(LineLayoutInlineContainerFlags::HAD_INLINE_END_PBM);
508
509            if containing_block_writing_mode.is_bidi_ltr() !=
510                inline_box.base.style.writing_mode.is_bidi_ltr()
511            {
512                std::mem::swap(&mut had_start, &mut had_end)
513            }
514
515            if !had_start {
516                padding.inline_start = Au::zero();
517                border.inline_start = Au::zero();
518                margin.inline_start = Au::zero();
519            }
520            if !had_end {
521                padding.inline_end = Au::zero();
522                border.inline_end = Au::zero();
523                margin.inline_end = Au::zero();
524            }
525        }
526        let pbm_sums = padding + border + margin;
527
528        // Make `content_rect` relative to the parent Fragment.
529        let mut content_rect = LogicalRect {
530            start_corner: LogicalVec2 {
531                inline: self.current_state.inline_advance + pbm_sums.inline_start,
532                block: inner_state.parent_offset.block - self.current_state.parent_offset.block,
533            },
534            size: LogicalVec2 {
535                inline: inner_state.inline_advance,
536                block: if self.is_phantom_line {
537                    Au::zero()
538                } else {
539                    inline_box_state.base.font_metrics.line_gap
540                },
541            },
542        };
543
544        // Relative adjustment should not affect the rest of line layout, so we can
545        // do it right before creating the Fragment.
546        let style = &inline_box.base.style;
547        let relative_adjustement = if style.get_box().position == Position::Relative {
548            let relative_adjustement = relative_adjustement(style, containing_block);
549            content_rect.start_corner += relative_adjustement;
550            relative_adjustement
551                .to_physical_offset_deprecated(containing_block_writing_mode)
552                .to_size()
553        } else {
554            PhysicalSize::zero()
555        };
556
557        let (fragments, propagated_floats) =
558            FragmentAndData::resolve_physical_rects_and_adjust_and_collect_floats(
559                inner_state.fragments_and_data,
560                &ContainingBlock {
561                    size: ContainingBlockSize::new(
562                        content_rect.size.inline,
563                        Default::default(), /* block_size */
564                    ),
565                    style: containing_block.style,
566                },
567                relative_adjustement,
568            );
569
570        let mut fragment = BoxFragment::new(
571            inline_box.base.base_fragment_info,
572            style.clone(),
573            FragmentChildren::PhysicalDeprecated(fragments),
574            // Previously all the fragment's children were positioned relative to the linebox,
575            // but they need to be made relative to this fragment.
576            content_rect.as_physical_deprecated(containing_block),
577            padding.to_physical(containing_block_writing_mode),
578            border.to_physical(containing_block_writing_mode),
579            margin.to_physical(containing_block_writing_mode),
580            None, /* specific_layout_info */
581        );
582        if self.for_block_level {
583            fragment.base.flags.insert(FragmentFlags::DO_NOT_PAINT);
584        }
585
586        match inner_state.positioning_context_or_start_offset_in_parent {
587            Either::Left(mut positioning_context) => {
588                positioning_context
589                    .layout_collected_children(self.layout.layout_context, &mut fragment);
590                positioning_context.adjust_static_position_of_hoisted_fragments(
591                    &content_rect,
592                    containing_block_writing_mode,
593                    PositioningContextLength::zero(),
594                );
595                self.current_positioning_context_mut()
596                    .append(positioning_context);
597            },
598            Either::Right(start_offset) => {
599                self.current_positioning_context_mut()
600                    .adjust_static_position_of_hoisted_fragments(
601                        &content_rect,
602                        containing_block_writing_mode,
603                        start_offset,
604                    );
605            },
606        }
607
608        self.current_state.inline_advance += inner_state.inline_advance + pbm_sums.inline_sum();
609
610        let fragment = Fragment::Box(Arc::new(fragment));
611        inline_box.base.add_fragment(fragment.clone());
612        self.current_state
613            .fragments_and_data
614            .push(FragmentAndData::new_with_propagated_floats(
615                FragmentAndLogicalRect::new(fragment, content_rect),
616                propagated_floats,
617            ));
618    }
619
620    fn calculate_inline_box_block_start(
621        &self,
622        inline_box_state: &InlineBoxContainerState,
623        space_above_baseline: Au,
624    ) -> Au {
625        if self.is_phantom_line {
626            return Au::zero();
627        };
628        let font_metrics = &inline_box_state.base.font_metrics;
629        let style = &inline_box_state.base.style;
630        let line_gap = font_metrics.line_gap;
631
632        // The baseline offset that we have in `Self::baseline_offset` is relative to the line
633        // baseline, so we need to make it relative to the line block start.
634        match inline_box_state.base.style.get_baseline_shift() {
635            BaselineShift::Keyword(BaselineShiftKeyword::Top) => {
636                let line_height = line_height(style, font_metrics, &inline_box_state.base.flags);
637                (line_height - line_gap).scale_by(0.5)
638            },
639            BaselineShift::Keyword(BaselineShiftKeyword::Center) => {
640                (self.line_metrics.block_size - line_gap).scale_by(0.5)
641            },
642            BaselineShift::Keyword(BaselineShiftKeyword::Bottom) => {
643                let line_height = line_height(style, font_metrics, &inline_box_state.base.flags);
644                let half_leading = (line_height - line_gap).scale_by(0.5);
645                self.line_metrics.block_size - line_height + half_leading
646            },
647            _ => {
648                self.line_metrics.baseline_block_offset + inline_box_state.base.baseline_offset -
649                    space_above_baseline
650            },
651        }
652    }
653
654    fn layout_text_run(&mut self, text_item: TextRunLineItem) {
655        if text_item.text.is_empty() && !text_item.is_empty_for_text_cursor {
656            return;
657        }
658
659        let mut number_of_justification_opportunities = 0;
660        let mut inline_advance = text_item
661            .text
662            .iter()
663            .map(|shaped_text_slice| {
664                number_of_justification_opportunities += shaped_text_slice.total_word_separators();
665                shaped_text_slice.total_advance()
666            })
667            .sum();
668
669        if !self.justification_adjustment.is_zero() {
670            inline_advance += self
671                .justification_adjustment
672                .scale_by(number_of_justification_opportunities as f32);
673        }
674
675        // The block start of the TextRun is often zero (meaning it has the same font metrics as the
676        // inline box's strut), but for children of the inline formatting context root or for
677        // fallback fonts that use baseline relative alignment, it might be different.
678        let font_metrics = text_item.info.font_info.font.metrics();
679        let start_corner = LogicalVec2 {
680            inline: self.current_state.inline_advance,
681            block: self.current_state.baseline_offset -
682                font_metrics.ascent -
683                self.current_state.parent_offset.block,
684        };
685        let content_rect = LogicalRect {
686            start_corner,
687            size: LogicalVec2 {
688                block: font_metrics.line_gap,
689                inline: inline_advance,
690            },
691        };
692
693        let font_key = text_item.info.font_info.font.key(
694            self.layout.layout_context.painter_id,
695            &self.layout.layout_context.font_context,
696        );
697
698        self.current_state.inline_advance += inline_advance;
699        self.current_state
700            .fragments_and_data
701            .push(FragmentAndData::new(FragmentAndLogicalRect::new(
702                Fragment::Text(Arc::new(TextFragment {
703                    base: BaseFragment::new(text_item.base_fragment_info, PhysicalRect::zero()),
704                    run_data: text_item.text_fragment_run_data,
705                    font_metrics: font_metrics.clone(),
706                    font_key,
707                    glyphs: text_item.text,
708                    justification_adjustment: self.justification_adjustment,
709                    character_range_in_dom_node: text_item.character_range_in_dom_node,
710                    is_empty_for_text_cursor: text_item.is_empty_for_text_cursor,
711                })),
712                content_rect,
713            )));
714    }
715
716    fn layout_atomic(&mut self, atomic: AtomicLineItem) {
717        // The initial `start_corner` of the Fragment is only the PaddingBorderMargin sum start
718        // offset, which is the sum of the start component of the padding, border, and margin.
719        // This needs to be added to the calculated block and inline positions.
720        // Make the final result relative to the parent box.
721        let containing_block = self.containing_block();
722        let ifc_writing_mode = containing_block.style.writing_mode;
723        let content_rect = {
724            let atomic_fragment = &atomic.fragment;
725            let block_start = atomic.calculate_block_start(&self.line_metrics);
726            let padding_border_margin_sides = LogicalSides::from_physical(
727                &atomic_fragment.padding_border_margin(),
728                ifc_writing_mode,
729            );
730
731            let mut atomic_offset = LogicalVec2 {
732                inline: self.current_state.inline_advance +
733                    padding_border_margin_sides.inline_start,
734                block: block_start - self.current_state.parent_offset.block +
735                    padding_border_margin_sides.block_start,
736            };
737
738            let style = atomic_fragment.style();
739            if style.get_box().position == Position::Relative {
740                atomic_offset += relative_adjustement(&style, containing_block);
741            }
742
743            // Reconstruct a logical rectangle relative to the inline box container that will be used
744            // after the inline box is processed to find a final physical rectangle.
745            LogicalRect {
746                start_corner: atomic_offset,
747                size: LogicalVec2::from_physical_size(
748                    &atomic_fragment.content_rect().size,
749                    ifc_writing_mode,
750                ),
751            }
752        };
753
754        if let Some(mut positioning_context) = atomic.positioning_context {
755            positioning_context.adjust_static_position_of_hoisted_fragments(
756                &content_rect,
757                containing_block.style.writing_mode,
758                PositioningContextLength::zero(),
759            );
760
761            self.current_positioning_context_mut()
762                .append(positioning_context);
763        }
764
765        self.current_state.inline_advance += atomic.size.inline;
766
767        self.current_state
768            .fragments_and_data
769            .push(FragmentAndData::new(FragmentAndLogicalRect::new(
770                Fragment::Box(atomic.fragment),
771                content_rect,
772            )));
773    }
774
775    fn layout_absolute(&mut self, absolute: AbsolutelyPositionedLineItem) {
776        let absolutely_positioned_box = (*absolute.absolutely_positioned_box).borrow();
777        let style = absolutely_positioned_box.context.style();
778
779        // From https://drafts.csswg.org/css2/#abs-non-replaced-width
780        // > The static-position containing block is the containing block of a
781        // > hypothetical box that would have been the first box of the element if its
782        // > specified position value had been static and its specified float had been
783        // > none. (Note that due to the rules in section 9.7 this hypothetical
784        // > calculation might require also assuming a different computed value for
785        // > display.)
786        //
787        // This box is different based on the original `display` value of the
788        // absolutely positioned element. If it's `inline` it would be placed inline
789        // at the top of the line, but if it's block it would be placed in a new
790        // block position after the linebox established by this line.
791        let block_position = self.layout.placement_state.current_margin.solve() -
792            self.current_state.parent_offset.block;
793        let initial_start_corner =
794            if style.get_box().original_display.outside() == DisplayOutside::Inline {
795                // Top of the line at the current inline position.
796                LogicalVec2 {
797                    inline: self.current_state.inline_advance,
798                    block: block_position,
799                }
800            } else {
801                // After the bottom of the line at the start of the inline formatting context.
802                // Note that phantom lines are treated as being zero-height for this purpose.
803                // <https://drafts.csswg.org/css-inline-3/#invisible-line-boxes>
804                LogicalVec2 {
805                    inline: -self.current_state.parent_offset.inline,
806                    block: if absolute.preceding_line_content_would_produce_phantom_line {
807                        block_position
808                    } else {
809                        block_position + self.line_metrics.block_size
810                    },
811                }
812            };
813
814        // Since alignment of absolutes in inlines is currently always `start`, the size of
815        // of the static position rectangle does not matter.
816        let containing_block = self.containing_block();
817        let containing_block_writing_mode = containing_block.style.writing_mode;
818        let static_position_rect = LogicalRect {
819            start_corner: initial_start_corner,
820            size: LogicalVec2::zero(),
821        };
822
823        let hoisted_box = AbsolutelyPositionedBox::to_hoisted(
824            absolute.absolutely_positioned_box.clone(),
825            StaticPositionRect::new(static_position_rect, containing_block_writing_mode),
826            LogicalVec2 {
827                inline: AlignFlags::START,
828                block: AlignFlags::START,
829            },
830            containing_block_writing_mode,
831        );
832
833        let hoisted_fragment = hoisted_box.fragment.clone();
834        self.current_positioning_context_mut().push(hoisted_box);
835        self.current_state
836            .fragments_and_data
837            .push(FragmentAndData::new(FragmentAndLogicalRect::new(
838                Fragment::AbsoluteOrFixedPositionedPlaceholder(hoisted_fragment),
839                LogicalRect::zero(),
840            )));
841    }
842
843    fn layout_float(&mut self, float: FloatLineItem) {
844        self.current_state
845            .flags
846            .insert(LineLayoutInlineContainerFlags::HAD_ANY_FLOATS);
847        // The `BoxFragment` for this float is positioned relative to the IFC, so we need
848        // to move it to be positioned relative to our parent InlineBox line item. Float
849        // fragments are children of these InlineBoxes and not children of the inline
850        // formatting context, so that they are parented properly for StackingContext
851        // properties such as opacity & filters.
852        // Note that `self.current_state.parent_offset` includes padding/border/margin of
853        // inline ancestors in the block axis, but not in the inline one, since that's not
854        // known yet. Therefore, in `end_inline_box()` we will need to adjust the inline
855        // position of the float, for each inline ancestor.
856        let offset = LogicalVec2 {
857            inline: Au::zero(),
858            block: -self.line_metrics.block_offset,
859        };
860        float
861            .fragment
862            .base
863            .translate_rect(offset.to_physical_size(self.containing_block().style.writing_mode));
864        self.current_state
865            .fragments_and_data
866            .push(FragmentAndData::new(FragmentAndLogicalRect::new(
867                Fragment::Float(float.fragment),
868                LogicalRect::zero(),
869            )));
870    }
871
872    fn layout_block_level(&mut self, block_level: Arc<BoxFragment>) {
873        let containing_block = self.containing_block();
874        let mut content_rect =
875            LogicalRect::from_physical_deprecated(block_level.content_rect(), containing_block);
876        // Block-level boxes are always placed at the logical origin of the line.
877        content_rect.start_corner.inline -= self.current_state.parent_offset.inline;
878        content_rect.start_corner.block -= self.line_metrics.block_offset;
879        self.current_state
880            .fragments_and_data
881            .push(FragmentAndData::new(FragmentAndLogicalRect::new(
882                Fragment::Box(block_level),
883                content_rect,
884            )));
885    }
886
887    #[inline]
888    fn containing_block(&self) -> &ContainingBlock<'_> {
889        self.layout.containing_block()
890    }
891
892    fn layout_tab(&mut self, advance: Au) {
893        self.current_state.inline_advance += advance;
894    }
895}
896
897pub(super) enum LineItem {
898    InlineStartBoxPaddingBorderMargin(Rc<InlineBoxContainerState>),
899    InlineEndBoxPaddingBorderMargin(Rc<InlineBoxContainerState>),
900    TextRun(Option<InlineBoxIdentifier>, TextRunLineItem),
901    Atomic(Option<InlineBoxIdentifier>, AtomicLineItem),
902    AbsolutelyPositioned(Option<InlineBoxIdentifier>, AbsolutelyPositionedLineItem),
903    Float(Option<InlineBoxIdentifier>, FloatLineItem),
904    BlockLevel(Option<InlineBoxIdentifier>, Arc<BoxFragment>),
905    Tab {
906        inline_box_identifier: Option<InlineBoxIdentifier>,
907        advance: Au,
908        bidi_level: Level,
909        conditionally_hangs: bool,
910    },
911}
912
913impl LineItem {
914    pub(crate) fn is_in_flow_content(&self) -> bool {
915        matches!(
916            self,
917            Self::TextRun(..) | Self::Atomic(..) | Self::BlockLevel(..)
918        )
919    }
920
921    fn inline_box_identifier(&self) -> Option<InlineBoxIdentifier> {
922        match self {
923            LineItem::InlineStartBoxPaddingBorderMargin(state) => Some(state.identifier),
924            LineItem::InlineEndBoxPaddingBorderMargin(state) => Some(state.identifier),
925            LineItem::TextRun(identifier, _) => *identifier,
926            LineItem::Atomic(identifier, _) => *identifier,
927            LineItem::AbsolutelyPositioned(identifier, _) => *identifier,
928            LineItem::Float(identifier, _) => *identifier,
929            LineItem::BlockLevel(identifier, _) => *identifier,
930            LineItem::Tab {
931                inline_box_identifier,
932                ..
933            } => *inline_box_identifier,
934        }
935    }
936
937    pub(super) fn trim_whitespace_at_start(&mut self, whitespace_trimmed: &mut Au) -> bool {
938        match self {
939            LineItem::InlineStartBoxPaddingBorderMargin(_) => true,
940            LineItem::InlineEndBoxPaddingBorderMargin(_) => true,
941            LineItem::TextRun(_, item) => item.trim_whitespace_at_start(whitespace_trimmed),
942            LineItem::Atomic(..) => false,
943            LineItem::AbsolutelyPositioned(..) => true,
944            LineItem::Float(..) => true,
945            LineItem::BlockLevel(..) => true,
946            LineItem::Tab { .. } => false,
947        }
948    }
949}
950
951pub(super) struct TextRunLineItem {
952    pub text_fragment_run_data: Arc<SharedTextRunData>,
953    pub info: FontAndScriptInfo,
954    pub base_fragment_info: BaseFragmentInfo,
955    pub text: Vec<Arc<ShapedTextSlice>>,
956    /// The range of characters this [`TextRunLineItem`] represents within the text of its
957    /// original DOM node (modified by text transformation).
958    pub character_range_in_dom_node: Range<Utf32CodeUnits>,
959    /// Whether or not this [`TextFragment`] is an empty fragment added for the
960    /// benefit of placing a text cursor on an otherwise empty editable line.
961    pub is_empty_for_text_cursor: bool,
962}
963
964impl TextRunLineItem {
965    /// Trim the removable white space at the end of this [`TextRunLineItem`].
966    pub(crate) fn trim_removable_white_space_at_end(&mut self) {
967        while let Some(last) = self.text.last_mut() {
968            if last.all_removable() {
969                self.text.pop();
970                continue;
971            }
972            *last = last.without_removable_white_space();
973            break;
974        }
975    }
976
977    fn trim_whitespace_at_start(&mut self, whitespace_trimmed: &mut Au) -> bool {
978        let index_of_first_non_whitespace = self
979            .text
980            .iter()
981            .position(|slice| !slice.all_removable())
982            .unwrap_or(self.text.len());
983
984        *whitespace_trimmed += self
985            .text
986            .drain(0..index_of_first_non_whitespace)
987            .map(|glyph| glyph.total_advance())
988            .sum();
989
990        // Only keep going if we only encountered whitespace.
991        self.text.is_empty()
992    }
993
994    /// Returns a [`TrailingWhiteSpace`] with the measurement of hanging
995    /// and removable white space and boolean saying whether or not there
996    /// was preceding content.
997    pub(crate) fn trailing_white_space(&self) -> (TrailingWhiteSpace<Au>, bool) {
998        let mut hangable = Au::zero();
999        let mut removable = Au::zero();
1000        let mut preceded_by_content = false;
1001
1002        for slice in self.text.iter().rev() {
1003            if hangable.is_zero() {
1004                removable += slice.removable_advance();
1005            } else {
1006                hangable += slice.removable_advance();
1007            }
1008            hangable += slice.hangable_advance();
1009
1010            if slice.has_non_hangable_non_removable_content() {
1011                preceded_by_content = true;
1012                break;
1013            }
1014        }
1015
1016        (
1017            TrailingWhiteSpace {
1018                hangable,
1019                removable,
1020            },
1021            preceded_by_content,
1022        )
1023    }
1024}
1025
1026pub(super) struct AtomicLineItem {
1027    pub fragment: Arc<BoxFragment>,
1028    pub size: LogicalVec2<Au>,
1029    pub positioning_context: Option<PositioningContext>,
1030
1031    /// The block offset of this items' baseline relative to the baseline of the line.
1032    /// This will be zero for boxes with `vertical-align: top` and `vertical-align:
1033    /// bottom` since their baselines are calculated late in layout.
1034    pub baseline_offset_in_parent: Au,
1035
1036    /// The offset of the baseline inside this item.
1037    pub baseline_offset_in_item: Au,
1038
1039    /// The BiDi level of this [`AtomicLineItem`] to enable reordering.
1040    pub bidi_level: Level,
1041}
1042
1043impl AtomicLineItem {
1044    /// Given the metrics for a line, our vertical alignment, and our block size, find a block start
1045    /// position relative to the top of the line.
1046    fn calculate_block_start(&self, line_metrics: &LineMetrics) -> Au {
1047        match self.fragment.style().get_baseline_shift() {
1048            BaselineShift::Keyword(BaselineShiftKeyword::Top) => Au::zero(),
1049            BaselineShift::Keyword(BaselineShiftKeyword::Center) => {
1050                (line_metrics.block_size - self.size.block).scale_by(0.5)
1051            },
1052            BaselineShift::Keyword(BaselineShiftKeyword::Bottom) => {
1053                line_metrics.block_size - self.size.block
1054            },
1055
1056            // This covers all baseline-relative vertical alignment.
1057            _ => {
1058                let baseline = line_metrics.baseline_block_offset + self.baseline_offset_in_parent;
1059                baseline - self.baseline_offset_in_item
1060            },
1061        }
1062    }
1063}
1064
1065pub(super) struct AbsolutelyPositionedLineItem {
1066    pub absolutely_positioned_box: ArcRefCell<AbsolutelyPositionedBox>,
1067    /// Whether the line would be phantom if it were to end before the abspos.
1068    /// This is used when computing the static position (in the block axis) of
1069    /// an abspos whose original display had a block outer display type.
1070    pub preceding_line_content_would_produce_phantom_line: bool,
1071}
1072
1073pub(super) struct FloatLineItem {
1074    pub fragment: Arc<BoxFragment>,
1075    /// Whether or not this float Fragment has been placed yet. Fragments that
1076    /// do not fit on a line need to be placed after the hypothetical block start
1077    /// of the next line.
1078    pub needs_placement: bool,
1079    /// The range of indices of the absolutes that escaped this `FloatBox`.
1080    /// This is used to adjust their static positioning rect once the final
1081    /// position of this float is known.
1082    pub range: Range<PositioningContextLength>,
1083}
1084
1085/// Sort a mutable slice by the given indices array in place, reording the slice so that final
1086/// value of `slice[x]` is `slice[indices[x]]`.
1087fn sort_by_indices_in_place<T>(data: &mut [T], mut indices: Vec<usize>) {
1088    for idx in 0..data.len() {
1089        if indices[idx] == idx {
1090            continue;
1091        }
1092
1093        let mut current_idx = idx;
1094        loop {
1095            let target_idx = indices[current_idx];
1096            indices[current_idx] = current_idx;
1097            if indices[target_idx] == target_idx {
1098                break;
1099            }
1100            data.swap(current_idx, target_idx);
1101            current_idx = target_idx;
1102        }
1103    }
1104}