Skip to main content

layout/flow/
float.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
5//! Float layout.
6//!
7//! See CSS 2.1 § 9.5.1: <https://www.w3.org/TR/CSS2/visuren.html#float-position>
8
9use std::collections::VecDeque;
10use std::fmt::Debug;
11use std::mem;
12use std::ops::Range;
13
14use app_units::{Au, MAX_AU, MIN_AU};
15use euclid::num::Zero;
16use malloc_size_of_derive::MallocSizeOf;
17use servo_arc::Arc;
18use style::computed_values::float::T as FloatProperty;
19use style::computed_values::position::T as Position;
20use style::logical_geometry::WritingMode;
21use style::properties::ComputedValues;
22use style::values::computed::Clear as StyleClear;
23
24use crate::PropagatedBoxTreeData;
25use crate::containing_block::ContainingBlock;
26use crate::context::LayoutContext;
27use crate::dom_traversal::{Contents, NodeAndStyleInfo};
28use crate::formatting_contexts::IndependentFormattingContext;
29use crate::fragment_tree::{BoxFragment, CollapsedMargin};
30use crate::geom::{LogicalRect, LogicalSides, LogicalVec2};
31use crate::positioned::{PositioningContext, relative_adjustement};
32use crate::style_ext::{DisplayInside, PaddingBorderMargin};
33
34/// A floating box.
35#[derive(Debug, MallocSizeOf)]
36pub(crate) struct FloatBox {
37    /// The formatting context that makes up the content of this box.
38    pub contents: IndependentFormattingContext,
39}
40
41/// `FloatContext` positions floats relative to the independent block formatting
42/// context which contains the floating elements. The Fragment tree positions
43/// elements relative to their containing blocks. This data structure is used to
44/// help map between these two coordinate systems.
45#[derive(Clone, Copy, Debug)]
46pub struct ContainingBlockPositionInfo {
47    /// The distance from the block start of the independent block formatting
48    /// context that contains the floats and the block start of the current
49    /// containing block, excluding uncollapsed block start margins. Note that
50    /// this does not include uncollapsed block start margins because we don't
51    /// know the value of collapsed margins until we lay out children.
52    pub(crate) block_start: Au,
53    /// Any uncollapsed block start margins that we have collected between the
54    /// block start of the float containing independent block formatting context
55    /// and this containing block, including for this containing block.
56    pub(crate) block_start_margins_not_collapsed: CollapsedMargin,
57    /// The distance from the inline start position of the float containing
58    /// independent formatting context and the inline start of this containing
59    /// block.
60    pub inline_start: Au,
61    /// The offset from the inline start position of the float containing
62    /// independent formatting context to the inline end of this containing
63    /// block.
64    pub inline_end: Au,
65}
66
67impl ContainingBlockPositionInfo {
68    pub fn new_with_inline_offsets(inline_start: Au, inline_end: Au) -> Self {
69        Self {
70            block_start: Au::zero(),
71            block_start_margins_not_collapsed: CollapsedMargin::zero(),
72            inline_start,
73            inline_end,
74        }
75    }
76}
77
78/// This data strucure is used to try to place non-floating content among float content.
79/// This is used primarily to place replaced content and independent formatting contexts
80/// next to floats, as the specifcation dictates.
81pub(crate) struct PlacementAmongFloats<'a> {
82    /// The [FloatContext] to use for this placement.
83    float_context: &'a FloatContext,
84    /// The current bands we are considering for this placement.
85    current_bands: VecDeque<FloatBand>,
86    /// The next band, needed to know the height of the last band in current_bands.
87    next_band: FloatBand,
88    /// The size of the object to place.
89    object_size: LogicalVec2<Au>,
90    /// The minimum position in the block direction for the placement. Objects should not
91    /// be placed before this point.
92    ceiling: Au,
93    /// The inline position where the object would be if there were no floats. The object
94    /// can be placed after it due to floats, but not before it.
95    min_inline_start: Au,
96    /// The maximum inline position that the object can attain when avoiding floats.
97    max_inline_end: Au,
98}
99
100impl<'a> PlacementAmongFloats<'a> {
101    pub(crate) fn new(
102        float_context: &'a FloatContext,
103        ceiling: Au,
104        object_size: LogicalVec2<Au>,
105        pbm: &PaddingBorderMargin,
106    ) -> Self {
107        let mut ceiling_band = float_context.bands.find(ceiling).unwrap();
108        let (current_bands, next_band) = if ceiling == MAX_AU {
109            (VecDeque::new(), ceiling_band)
110        } else {
111            ceiling_band.top = ceiling;
112            let current_bands = VecDeque::from([ceiling_band]);
113            let next_band = float_context.bands.find_next(ceiling).unwrap();
114            (current_bands, next_band)
115        };
116        let min_inline_start = float_context.containing_block_info.inline_start +
117            pbm.margin.inline_start.auto_is(Au::zero);
118        let max_inline_end = (float_context.containing_block_info.inline_end -
119            pbm.margin.inline_end.auto_is(Au::zero))
120        .max(min_inline_start + object_size.inline);
121        PlacementAmongFloats {
122            float_context,
123            current_bands,
124            next_band,
125            object_size,
126            ceiling,
127            min_inline_start,
128            max_inline_end,
129        }
130    }
131
132    /// The top of the bands under consideration. This is initially the ceiling provided
133    /// during creation of this [`PlacementAmongFloats`], but may be larger if the top
134    /// band is discarded.
135    fn top_of_bands(&self) -> Option<Au> {
136        self.current_bands.front().map(|band| band.top)
137    }
138
139    /// The height of the bands under consideration.
140    fn current_bands_height(&self) -> Au {
141        if self.next_band.top == MAX_AU {
142            // Treat MAX_AU as infinity.
143            MAX_AU
144        } else {
145            let top = self
146                .top_of_bands()
147                .expect("Should have bands before reaching the end");
148            self.next_band.top - top
149        }
150    }
151
152    /// Add a single band to the bands under consideration and calculate the new
153    /// [`PlacementAmongFloats::next_band`].
154    fn add_one_band(&mut self) {
155        assert!(self.next_band.top != MAX_AU);
156        self.current_bands.push_back(self.next_band);
157        self.next_band = self
158            .float_context
159            .bands
160            .find_next(self.next_band.top)
161            .unwrap();
162    }
163
164    /// Adds bands to the set of bands under consideration until their block size is at
165    /// least large enough to contain the block size of the object being placed.
166    fn accumulate_enough_bands_for_block_size(&mut self) {
167        while self.current_bands_height() < self.object_size.block {
168            self.add_one_band();
169        }
170    }
171
172    /// Find the start and end of the inline space provided by the current set of bands
173    /// under consideration.
174    fn calculate_inline_start_and_end(&self) -> (Au, Au) {
175        let mut max_inline_start = self.min_inline_start;
176        let mut min_inline_end = self.max_inline_end;
177        for band in self.current_bands.iter() {
178            if let Some(inline_start) = band.inline_start {
179                max_inline_start.max_assign(inline_start);
180            }
181            if let Some(inline_end) = band.inline_end {
182                min_inline_end.min_assign(inline_end);
183            }
184        }
185        (max_inline_start, min_inline_end)
186    }
187
188    /// Find the total inline size provided by the current set of bands under consideration.
189    fn calculate_viable_inline_size(&self) -> Au {
190        let (inline_start, inline_end) = self.calculate_inline_start_and_end();
191        inline_end - inline_start
192    }
193
194    fn try_place_once(&mut self) -> Option<LogicalRect<Au>> {
195        assert!(!self.current_bands.is_empty());
196        self.accumulate_enough_bands_for_block_size();
197        let (inline_start, inline_end) = self.calculate_inline_start_and_end();
198        let available_inline_size = inline_end - inline_start;
199        if available_inline_size < self.object_size.inline {
200            return None;
201        }
202        Some(LogicalRect {
203            start_corner: LogicalVec2 {
204                inline: inline_start,
205                block: self.top_of_bands().unwrap(),
206            },
207            size: LogicalVec2 {
208                inline: available_inline_size,
209                block: self.current_bands_height(),
210            },
211        })
212    }
213
214    /// Checks if we either have bands or we have gone past all of them.
215    /// This is an invariant that should hold, otherwise we are in a broken state.
216    fn has_bands_or_at_end(&self) -> bool {
217        !self.current_bands.is_empty() || self.next_band.top == MAX_AU
218    }
219
220    fn pop_front_band_ensuring_has_bands_or_at_end(&mut self) {
221        self.current_bands.pop_front();
222        if !self.has_bands_or_at_end() {
223            self.add_one_band();
224        }
225    }
226
227    /// Run the placement algorithm for this [PlacementAmongFloats].
228    pub(crate) fn place(&mut self) -> LogicalRect<Au> {
229        debug_assert!(self.has_bands_or_at_end());
230        while !self.current_bands.is_empty() {
231            if let Some(result) = self.try_place_once() {
232                return result;
233            }
234            self.pop_front_band_ensuring_has_bands_or_at_end();
235        }
236        debug_assert!(self.has_bands_or_at_end());
237
238        // We could not fit the object in among the floats, so we place it as if it
239        // cleared all floats.
240        LogicalRect {
241            start_corner: LogicalVec2 {
242                inline: self.min_inline_start,
243                block: self
244                    .ceiling
245                    .max(self.float_context.clear_inline_start_position)
246                    .max(self.float_context.clear_inline_end_position),
247            },
248            size: LogicalVec2 {
249                inline: self.max_inline_end - self.min_inline_start,
250                block: MAX_AU,
251            },
252        }
253    }
254
255    /// After placing an object with `height: auto` (and using the minimum inline and
256    /// block size as the object size) and then laying it out, try to fit the object into
257    /// the current set of bands, given block size after layout and the available inline
258    /// space from the original placement. This will return true if the object fits at the
259    /// original placement location or false if the placement and layout must be run again
260    /// (with this [PlacementAmongFloats]).
261    pub(crate) fn try_to_expand_for_auto_block_size(
262        &mut self,
263        block_size_after_layout: Au,
264        size_from_placement: &LogicalVec2<Au>,
265    ) -> bool {
266        debug_assert!(self.has_bands_or_at_end());
267        debug_assert_eq!(size_from_placement.block, self.current_bands_height());
268        debug_assert_eq!(
269            size_from_placement.inline,
270            self.calculate_viable_inline_size()
271        );
272
273        // If the object after layout fits into the originally calculated placement, then
274        // it fits without any more work.
275        if block_size_after_layout <= size_from_placement.block {
276            return true;
277        }
278
279        // Keep searching until we have found an area with enough height
280        // to contain the block after layout.
281        let old_num_bands = self.current_bands.len();
282        assert!(old_num_bands > 0);
283        while self.current_bands_height() < block_size_after_layout {
284            self.add_one_band();
285
286            // If the new inline size is narrower, we must stop and run layout again.
287            // Normally, a narrower block size means a bigger height, but in some
288            // circumstances, such as when aspect ratio is used a narrower inline size
289            // can counter-interuitively lead to a smaller block size after layout!
290            let available_inline_size = self.calculate_viable_inline_size();
291            if available_inline_size < size_from_placement.inline {
292                // If the inline size becomes smaller than the minimum inline size, then
293                // the current set of bands will never work and we must try removing the
294                // first and searching starting from the second.
295                if available_inline_size < self.object_size.inline {
296                    self.next_band = self.current_bands[old_num_bands];
297                    self.current_bands.truncate(old_num_bands);
298                    self.pop_front_band_ensuring_has_bands_or_at_end();
299                }
300                return false;
301            }
302        }
303        true
304    }
305}
306
307/// Data kept during layout about the floats in a given block formatting context.
308///
309/// This is a persistent data structure. Each float has its own private copy of the float context,
310/// although such copies may share portions of the `bands` tree.
311#[derive(Clone, Debug)]
312pub struct FloatContext {
313    /// A persistent AA tree of float bands.
314    ///
315    /// This tree is immutable; modification operations return the new tree, which may share nodes
316    /// with previous versions of the tree.
317    pub bands: FloatBandTree,
318    /// The block-direction "ceiling" defined by the placement of other floated content of
319    /// this FloatContext. No new floats can be placed at a lower block start than this value.
320    pub ceiling_from_floats: Au,
321    /// The block-direction "ceiling" defined by the placement of non-floated content that
322    /// precedes floated content in the document. Note that this may actually decrease as
323    /// content is laid out in the case that content overflows its container.
324    pub ceiling_from_non_floats: Au,
325    /// Details about the position of the containing block relative to the
326    /// independent block formatting context that contains all of the floats
327    /// this `FloatContext` positions.
328    pub containing_block_info: ContainingBlockPositionInfo,
329    /// The (logically) lowest margin edge of the last inline-start float.
330    pub clear_inline_start_position: Au,
331    /// The (logically) lowest margin edge of the last inline-end float.
332    pub clear_inline_end_position: Au,
333}
334
335impl FloatContext {
336    /// Returns a new float context representing a containing block with the given content
337    /// inline-size.
338    pub fn new(max_inline_size: Au) -> Self {
339        let mut bands = FloatBandTree::new();
340        bands = bands.insert(FloatBand {
341            top: MIN_AU,
342            inline_start: None,
343            inline_end: None,
344        });
345        bands = bands.insert(FloatBand {
346            top: MAX_AU,
347            inline_start: None,
348            inline_end: None,
349        });
350        FloatContext {
351            bands,
352            ceiling_from_floats: Au::zero(),
353            ceiling_from_non_floats: Au::zero(),
354            containing_block_info: ContainingBlockPositionInfo::new_with_inline_offsets(
355                Au::zero(),
356                max_inline_size,
357            ),
358            clear_inline_start_position: Au::zero(),
359            clear_inline_end_position: Au::zero(),
360        }
361    }
362
363    /// (Logically) lowers the ceiling to at least `new_ceiling` units.
364    ///
365    /// If the ceiling is already logically lower (i.e. larger) than this, does nothing.
366    pub fn set_ceiling_from_non_floats(&mut self, new_ceiling: Au) {
367        self.ceiling_from_non_floats = new_ceiling;
368    }
369
370    /// The "ceiling" used for float placement. This is the minimum block position value
371    /// that should be used for placing any new float.
372    fn ceiling(&mut self) -> Au {
373        self.ceiling_from_floats.max(self.ceiling_from_non_floats)
374    }
375
376    /// Determines where a float with the given placement would go, but leaves the float context
377    /// unmodified. Returns the start corner of its margin box.
378    ///
379    /// This should be used for placing inline elements and block formatting contexts so that they
380    /// don't collide with floats.
381    pub(crate) fn place_object(&self, object: &PlacementInfo, ceiling: Au) -> LogicalVec2<Au> {
382        let ceiling = match object.clear {
383            Clear::None => ceiling,
384            Clear::InlineStart => ceiling.max(self.clear_inline_start_position),
385            Clear::InlineEnd => ceiling.max(self.clear_inline_end_position),
386            Clear::Both => ceiling
387                .max(self.clear_inline_start_position)
388                .max(self.clear_inline_end_position),
389        };
390
391        // Find the first band this float fits in.
392        let mut first_band = self.bands.find(ceiling).unwrap();
393        while !first_band.object_fits(object, &self.containing_block_info) {
394            let next_band = self.bands.find_next(first_band.top).unwrap();
395            if next_band.top == MAX_AU {
396                break;
397            }
398            first_band = next_band;
399        }
400
401        // The object fits perfectly here. Place it.
402        match object.side {
403            FloatSide::InlineStart => {
404                let inline_start_object_edge = match first_band.inline_start {
405                    Some(inline_start) => inline_start.max(self.containing_block_info.inline_start),
406                    None => self.containing_block_info.inline_start,
407                };
408                LogicalVec2 {
409                    inline: inline_start_object_edge,
410                    block: first_band.top.max(ceiling),
411                }
412            },
413            FloatSide::InlineEnd => {
414                let inline_end_object_edge = match first_band.inline_end {
415                    Some(inline_end) => inline_end.min(self.containing_block_info.inline_end),
416                    None => self.containing_block_info.inline_end,
417                };
418                LogicalVec2 {
419                    inline: inline_end_object_edge - object.size.inline,
420                    block: first_band.top.max(ceiling),
421                }
422            },
423        }
424    }
425
426    /// Places a new float and adds it to the list. Returns the start corner of its margin box.
427    pub fn add_float(&mut self, new_float: &PlacementInfo) -> LogicalVec2<Au> {
428        // Place the float.
429        let ceiling = self.ceiling();
430        let new_float_origin = self.place_object(new_float, ceiling);
431        let new_float_extent = match new_float.side {
432            FloatSide::InlineStart => new_float_origin.inline + new_float.size.inline,
433            FloatSide::InlineEnd => new_float_origin.inline,
434        };
435
436        let new_float_rect = LogicalRect {
437            start_corner: new_float_origin,
438            // If this float has a negative margin, we should only consider its non-negative
439            // block size contribution when determing where to place it. When the margin is
440            // so negative that it's placed completely above the current float ceiling, then
441            // we should position it as if it had zero block size.
442            size: LogicalVec2 {
443                inline: new_float.size.inline.max(Au::zero()),
444                block: new_float.size.block.max(Au::zero()),
445            },
446        };
447
448        // Update clear.
449        match new_float.side {
450            FloatSide::InlineStart => {
451                self.clear_inline_start_position
452                    .max_assign(new_float_rect.max_block_position());
453            },
454            FloatSide::InlineEnd => {
455                self.clear_inline_end_position
456                    .max_assign(new_float_rect.max_block_position());
457            },
458        }
459
460        // Split the first band if necessary.
461        let mut first_band = self.bands.find(new_float_rect.start_corner.block).unwrap();
462        first_band.top = new_float_rect.start_corner.block;
463        self.bands = self.bands.insert(first_band);
464
465        // Split the last band if necessary.
466        let mut last_band = self
467            .bands
468            .find(new_float_rect.max_block_position())
469            .unwrap();
470        last_band.top = new_float_rect.max_block_position();
471        self.bands = self.bands.insert(last_band);
472
473        // Update all bands that contain this float to reflect the new available size.
474        let block_range = new_float_rect.start_corner.block..new_float_rect.max_block_position();
475        self.bands = self
476            .bands
477            .set_range(&block_range, new_float.side, new_float_extent);
478
479        // CSS 2.1 § 9.5.1 rule 6: The outer top of a floating box may not be higher than the outer
480        // top of any block or floated box generated by an element earlier in the source document.
481        self.ceiling_from_floats
482            .max_assign(new_float_rect.start_corner.block);
483
484        new_float_rect.start_corner
485    }
486}
487
488#[derive(Clone, Copy, Debug, PartialEq)]
489pub enum Clear {
490    None,
491    InlineStart,
492    InlineEnd,
493    Both,
494}
495
496impl Clear {
497    pub(crate) fn from_style_and_container_writing_mode(
498        style: &ComputedValues,
499        container_writing_mode: WritingMode,
500    ) -> Self {
501        match style.get_box().clear {
502            StyleClear::None => Self::None,
503            StyleClear::Both => Self::Both,
504            StyleClear::InlineStart => Self::InlineStart,
505            StyleClear::InlineEnd => Self::InlineEnd,
506            StyleClear::Left if container_writing_mode.is_bidi_ltr() => Self::InlineStart,
507            StyleClear::Left => Self::InlineEnd,
508            StyleClear::Right if container_writing_mode.is_bidi_ltr() => Self::InlineEnd,
509            StyleClear::Right => Self::InlineStart,
510        }
511    }
512}
513
514/// Information needed to place a float so that it doesn't collide with existing floats.
515#[derive(Clone, Debug)]
516pub struct PlacementInfo {
517    /// The *margin* box size of the float.
518    pub size: LogicalVec2<Au>,
519    /// Which side of the containing block the float is aligned to.
520    pub side: FloatSide,
521    /// Which side or sides to clear existing floats on.
522    pub clear: Clear,
523}
524
525/// Whether the float is aligned to the inline-start or inline-end side of its containing block.
526///
527/// See CSS 2.1 § 9.5.1: <https://www.w3.org/TR/CSS2/visuren.html#float-position>
528#[derive(Clone, Copy, Debug, PartialEq)]
529pub enum FloatSide {
530    InlineStart,
531    InlineEnd,
532}
533
534/// Internal data structure that describes a nonoverlapping vertical region in which floats may be placed.
535/// Floats must go between "inline-start edge + `inline_start`" and "inline-end edge - `inline_end`".
536#[derive(Clone, Copy, Debug, PartialEq)]
537pub struct FloatBand {
538    /// The logical vertical position of the top of this band.
539    pub top: Au,
540    /// The distance from the inline-start edge of the block formatting context to the first legal
541    /// (logically) horizontal position where floats may be placed. If `None`, there are no floats
542    /// to the inline-start; distinguishing between the cases of "a zero-width float is present" and
543    /// "no floats at all are present" is necessary to, for example, clear past zero-width floats.
544    pub inline_start: Option<Au>,
545    /// The distance from the *inline-start* edge of the block formatting context to the last legal
546    /// (logically) horizontal position where floats may be placed. If `None`, there are no floats
547    /// to the inline-end; distinguishing between the cases of "a zero-width float is present" and
548    /// "no floats at all are present" is necessary to, for example, clear past zero-width floats.
549    pub inline_end: Option<Au>,
550}
551
552impl FloatSide {
553    pub(crate) fn from_style_and_container_writing_mode(
554        style: &ComputedValues,
555        container_writing_mode: WritingMode,
556    ) -> Option<FloatSide> {
557        Some(match style.get_box().float {
558            FloatProperty::None => return None,
559            FloatProperty::InlineStart => Self::InlineStart,
560            FloatProperty::InlineEnd => Self::InlineEnd,
561            FloatProperty::Left if container_writing_mode.is_bidi_ltr() => Self::InlineStart,
562            FloatProperty::Left => Self::InlineEnd,
563            FloatProperty::Right if container_writing_mode.is_bidi_ltr() => Self::InlineEnd,
564            FloatProperty::Right => Self::InlineStart,
565        })
566    }
567}
568
569impl FloatBand {
570    /// Determines whether an object fits in a band. Returns true if the object fits.
571    fn object_fits(&self, object: &PlacementInfo, walls: &ContainingBlockPositionInfo) -> bool {
572        match object.side {
573            FloatSide::InlineStart => {
574                // Compute a candidate inline-start position for the object.
575                let candidate_inline_start = match self.inline_start {
576                    None => walls.inline_start,
577                    Some(inline_start) => inline_start.max(walls.inline_start),
578                };
579
580                // If this band has an existing inline-start float in it, then make sure that the object
581                // doesn't stick out past the inline-end edge (rule 7).
582                if self.inline_start.is_some() &&
583                    candidate_inline_start + object.size.inline > walls.inline_end
584                {
585                    return false;
586                }
587
588                // If this band has an existing inline-end float in it, make sure we don't collide with
589                // it (rule 3).
590                match self.inline_end {
591                    None => true,
592                    Some(inline_end) => object.size.inline <= inline_end - candidate_inline_start,
593                }
594            },
595
596            FloatSide::InlineEnd => {
597                // Compute a candidate inline-end position for the object.
598                let candidate_inline_end = match self.inline_end {
599                    None => walls.inline_end,
600                    Some(inline_end) => inline_end.min(walls.inline_end),
601                };
602
603                // If this band has an existing inline-end float in it, then make sure that the new
604                // object doesn't stick out past the inline-start edge (rule 7).
605                if self.inline_end.is_some() &&
606                    candidate_inline_end - object.size.inline < walls.inline_start
607                {
608                    return false;
609                }
610
611                // If this band has an existing inline-start float in it, make sure we don't collide with
612                // it (rule 3).
613                match self.inline_start {
614                    None => true,
615                    Some(inline_start) => object.size.inline <= candidate_inline_end - inline_start,
616                }
617            },
618        }
619    }
620}
621
622// Float band storage
623
624/// A persistent AA tree for float band storage.
625///
626/// Bands here are nonoverlapping, and there is guaranteed to be a band at block-position 0 and
627/// another band at block-position infinity.
628///
629/// AA trees were chosen for simplicity.
630///
631/// See: <https://en.wikipedia.org/wiki/AA_tree>
632///      <https://arxiv.org/pdf/1412.4882.pdf>
633#[derive(Clone, Debug)]
634pub struct FloatBandTree {
635    pub root: FloatBandLink,
636}
637
638/// A single edge (or lack thereof) in the float band tree.
639#[derive(Clone, Debug)]
640pub struct FloatBandLink(pub Option<Arc<FloatBandNode>>);
641
642/// A single node in the float band tree.
643#[derive(Clone, Debug)]
644pub struct FloatBandNode {
645    /// The actual band.
646    pub band: FloatBand,
647    /// The left child.
648    pub left: FloatBandLink,
649    /// The right child.
650    pub right: FloatBandLink,
651    /// The level, which increases as you go up the tree.
652    ///
653    /// This value is needed for tree balancing.
654    pub level: i32,
655}
656
657impl FloatBandTree {
658    /// Creates a new float band tree.
659    pub fn new() -> FloatBandTree {
660        FloatBandTree {
661            root: FloatBandLink(None),
662        }
663    }
664
665    /// Returns the first band whose top is less than or equal to the given `block_position`.
666    pub fn find(&self, block_position: Au) -> Option<FloatBand> {
667        self.root.find(block_position)
668    }
669
670    /// Returns the first band whose top is strictly greater than to the given `block_position`.
671    pub fn find_next(&self, block_position: Au) -> Option<FloatBand> {
672        self.root.find_next(block_position)
673    }
674
675    /// Sets the side values of all bands within the given half-open range to be at least
676    /// `new_value`.
677    #[must_use]
678    pub fn set_range(&self, range: &Range<Au>, side: FloatSide, new_value: Au) -> FloatBandTree {
679        FloatBandTree {
680            root: FloatBandLink(
681                self.root
682                    .0
683                    .as_ref()
684                    .map(|root| root.set_range(range, side, new_value)),
685            ),
686        }
687    }
688
689    /// Inserts a new band into the tree. If the band has the same level as a pre-existing one,
690    /// replaces the existing band with the new one.
691    #[must_use]
692    pub fn insert(&self, band: FloatBand) -> FloatBandTree {
693        FloatBandTree {
694            root: self.root.insert(band),
695        }
696    }
697}
698
699impl Default for FloatBandTree {
700    fn default() -> Self {
701        Self::new()
702    }
703}
704
705impl FloatBandNode {
706    fn new(band: FloatBand) -> FloatBandNode {
707        FloatBandNode {
708            band,
709            left: FloatBandLink(None),
710            right: FloatBandLink(None),
711            level: 1,
712        }
713    }
714
715    /// Sets the side values of all bands within the given half-open range to be at least
716    /// `new_value`.
717    fn set_range(&self, range: &Range<Au>, side: FloatSide, new_value: Au) -> Arc<FloatBandNode> {
718        let mut new_band = self.band;
719        if self.band.top >= range.start && self.band.top < range.end {
720            match side {
721                FloatSide::InlineStart => {
722                    new_band.inline_start = match new_band.inline_start {
723                        Some(old_value) => Some(std::cmp::max(old_value, new_value)),
724                        None => Some(new_value),
725                    };
726                },
727                FloatSide::InlineEnd => {
728                    new_band.inline_end = match new_band.inline_end {
729                        Some(old_value) => Some(std::cmp::min(old_value, new_value)),
730                        None => Some(new_value),
731                    };
732                },
733            }
734        }
735
736        let new_left = match self.left.0 {
737            None => FloatBandLink(None),
738            Some(ref old_left) if range.start < new_band.top => {
739                FloatBandLink(Some(old_left.set_range(range, side, new_value)))
740            },
741            Some(ref old_left) => FloatBandLink(Some((*old_left).clone())),
742        };
743
744        let new_right = match self.right.0 {
745            None => FloatBandLink(None),
746            Some(ref old_right) if range.end > new_band.top => {
747                FloatBandLink(Some(old_right.set_range(range, side, new_value)))
748            },
749            Some(ref old_right) => FloatBandLink(Some((*old_right).clone())),
750        };
751
752        Arc::new(FloatBandNode {
753            band: new_band,
754            left: new_left,
755            right: new_right,
756            level: self.level,
757        })
758    }
759}
760
761impl FloatBandLink {
762    /// Returns the first band whose top is less than or equal to the given `block_position`.
763    fn find(&self, block_position: Au) -> Option<FloatBand> {
764        let this = self.0.as_ref()?;
765
766        if block_position < this.band.top {
767            return this.left.find(block_position);
768        }
769
770        // It's somewhere in this subtree, but we aren't sure whether it's here or in the right
771        // subtree.
772        if let Some(band) = this.right.find(block_position) {
773            return Some(band);
774        }
775
776        Some(this.band)
777    }
778
779    /// Returns the first band whose top is strictly greater than the given `block_position`.
780    fn find_next(&self, block_position: Au) -> Option<FloatBand> {
781        let this = self.0.as_ref()?;
782
783        if block_position >= this.band.top {
784            return this.right.find_next(block_position);
785        }
786
787        // It's somewhere in this subtree, but we aren't sure whether it's here or in the left
788        // subtree.
789        if let Some(band) = this.left.find_next(block_position) {
790            return Some(band);
791        }
792
793        Some(this.band)
794    }
795
796    /// Inserts a new band into the tree. If the band has the same level as a pre-existing one,
797    /// replaces the existing band with the new one.
798    fn insert(&self, band: FloatBand) -> FloatBandLink {
799        let mut this = match self.0 {
800            None => return FloatBandLink(Some(Arc::new(FloatBandNode::new(band)))),
801            Some(ref this) => (**this).clone(),
802        };
803
804        if band.top < this.band.top {
805            this.left = this.left.insert(band);
806            return FloatBandLink(Some(Arc::new(this))).skew().split();
807        }
808        if band.top > this.band.top {
809            this.right = this.right.insert(band);
810            return FloatBandLink(Some(Arc::new(this))).skew().split();
811        }
812
813        this.band = band;
814        FloatBandLink(Some(Arc::new(this)))
815    }
816
817    /// Corrects tree balance:
818    ///```text
819    ///         T          L
820    ///        / \        / \
821    ///       L   R  →   A   T      if level(T) = level(L)
822    ///      / \            / \
823    ///     A   B          B   R
824    /// ```
825    fn skew(&self) -> FloatBandLink {
826        if let Some(ref this) = self.0 &&
827            let Some(ref left) = this.left.0 &&
828            this.level == left.level
829        {
830            return FloatBandLink(Some(Arc::new(FloatBandNode {
831                level: this.level,
832                left: left.left.clone(),
833                band: left.band,
834                right: FloatBandLink(Some(Arc::new(FloatBandNode {
835                    level: this.level,
836                    left: left.right.clone(),
837                    band: this.band,
838                    right: this.right.clone(),
839                }))),
840            })));
841        }
842
843        (*self).clone()
844    }
845
846    /// Corrects tree balance:
847    ///```text
848    ///         T            R
849    ///        / \          / \
850    ///       A   R   →    T   X    if level(T) = level(X)
851    ///          / \      / \
852    ///         B   X    A   B
853    /// ```
854    fn split(&self) -> FloatBandLink {
855        if let Some(ref this) = self.0 &&
856            let Some(ref right) = this.right.0 &&
857            let Some(ref right_right) = right.right.0 &&
858            this.level == right_right.level
859        {
860            return FloatBandLink(Some(Arc::new(FloatBandNode {
861                level: this.level + 1,
862                left: FloatBandLink(Some(Arc::new(FloatBandNode {
863                    level: this.level,
864                    left: this.left.clone(),
865                    band: this.band,
866                    right: right.left.clone(),
867                }))),
868                band: right.band,
869                right: right.right.clone(),
870            })));
871        }
872
873        (*self).clone()
874    }
875}
876
877impl FloatBox {
878    /// Creates a new float box.
879    pub fn construct(
880        context: &LayoutContext,
881        info: &NodeAndStyleInfo<'_>,
882        display_inside: DisplayInside,
883        contents: Contents,
884        propagated_data: PropagatedBoxTreeData,
885    ) -> Self {
886        Self {
887            contents: IndependentFormattingContext::construct(
888                context,
889                info,
890                display_inside,
891                contents,
892                propagated_data,
893            ),
894        }
895    }
896
897    /// Lay out this float box and its children. Note that the position will be relative to
898    /// the float containing block formatting context. A later step adjusts the position
899    /// to be relative to the containing block.
900    pub fn layout(
901        &self,
902        layout_context: &LayoutContext,
903        positioning_context: &mut PositioningContext,
904        containing_block: &ContainingBlock,
905    ) -> BoxFragment {
906        positioning_context.layout_maybe_position_relative_fragment(
907            layout_context,
908            containing_block,
909            &self.contents.base,
910            |positioning_context| {
911                self.contents
912                    .layout_float_or_atomic_inline(
913                        layout_context,
914                        positioning_context,
915                        containing_block,
916                    )
917                    .fragment
918            },
919        )
920    }
921}
922
923/// Layout state that we maintain when doing sequential traversals of the box tree in document
924/// order.
925///
926/// This data is only needed for float placement and float interaction, and as such is only present
927/// if the current block formatting context contains floats.
928///
929/// All coordinates here are relative to the start of the nearest ancestor block formatting context.
930///
931/// This structure is expected to be cheap to clone, in order to allow for "snapshots" that enable
932/// restarting layout at any point in the tree.
933#[derive(Clone)]
934pub(crate) struct SequentialLayoutState {
935    /// Holds all floats in this block formatting context.
936    pub(crate) floats: FloatContext,
937    /// The (logically) bottom border edge or top padding edge of the last in-flow block. Floats
938    /// cannot be placed above this line.
939    ///
940    /// This is often, but not always, the same as the float ceiling. The float ceiling can be lower
941    /// than this value because this value is calculated based on in-flow boxes only, while
942    /// out-of-flow floats can affect the ceiling as well (see CSS 2.1 § 9.5.1 rule 6).
943    pub(crate) bfc_relative_block_position: Au,
944    /// Any collapsible margins that we've encountered after `bfc_relative_block_position`.
945    pub(crate) current_margin: CollapsedMargin,
946}
947
948impl SequentialLayoutState {
949    /// Creates a new empty `SequentialLayoutState`.
950    pub(crate) fn new(max_inline_size: Au) -> SequentialLayoutState {
951        SequentialLayoutState {
952            floats: FloatContext::new(max_inline_size),
953            current_margin: CollapsedMargin::zero(),
954            bfc_relative_block_position: Au::zero(),
955        }
956    }
957
958    /// Moves the current block position (logically) down by `block_distance`. This may be
959    /// a negative advancement in the case that that block content overflows its
960    /// container, when the container is adjusting the block position of the
961    /// [`SequentialLayoutState`] after processing its overflowing content.
962    ///
963    /// Floats may not be placed higher than the current block position.
964    pub(crate) fn advance_block_position(&mut self, block_distance: Au) {
965        self.bfc_relative_block_position += block_distance;
966        self.floats
967            .set_ceiling_from_non_floats(self.bfc_relative_block_position);
968    }
969
970    /// Replace the entire [ContainingBlockPositionInfo] data structure stored
971    /// by this [SequentialLayoutState]. Return the old data structure.
972    pub(crate) fn replace_containing_block_position_info(
973        &mut self,
974        mut position_info: ContainingBlockPositionInfo,
975    ) -> ContainingBlockPositionInfo {
976        mem::swap(&mut position_info, &mut self.floats.containing_block_info);
977        position_info
978    }
979
980    /// Return the current block position in the float containing block formatting
981    /// context and any uncollapsed block margins.
982    pub(crate) fn current_block_position_including_margins(&self) -> Au {
983        self.bfc_relative_block_position + self.current_margin.solve()
984    }
985
986    /// Commits margins, moving the block position down by the collapsed value of `current_margin`
987    /// and resetting `current_margin` to zero.
988    ///
989    /// Call this method before laying out children when it is known that the start margin of the
990    /// current fragment can't collapse with the margins of any of its children.
991    pub(crate) fn commit_margin(&mut self) {
992        self.advance_block_position(self.current_margin.solve());
993        self.current_margin = CollapsedMargin::zero();
994    }
995
996    /// Computes the position of the block-start border edge of an element
997    /// with the provided `block_start_margin`, assuming no clearance.
998    pub(crate) fn position_without_clearance(&self, block_start_margin: &CollapsedMargin) -> Au {
999        // Adjoin `current_margin` and `block_start_margin` since there is no clearance.
1000        self.bfc_relative_block_position + self.current_margin.adjoin(block_start_margin).solve()
1001    }
1002
1003    /// Computes the position of the block-start border edge of an element
1004    /// with the provided `block_start_margin`, assuming a clearance of 0px.
1005    pub(crate) fn position_with_zero_clearance(&self, block_start_margin: &CollapsedMargin) -> Au {
1006        // Clearance prevents `current_margin` and `block_start_margin` from being
1007        // adjoining, so we need to solve them separately and then sum.
1008        self.bfc_relative_block_position + self.current_margin.solve() + block_start_margin.solve()
1009    }
1010
1011    /// Returns the block-end outer edge of the lowest float that is to be cleared (if any)
1012    /// by an element with the provided `clear` and `block_start_margin`.
1013    pub(crate) fn calculate_clear_position(
1014        &self,
1015        clear: Clear,
1016        block_start_margin: &CollapsedMargin,
1017    ) -> Option<Au> {
1018        if clear == Clear::None {
1019            return None;
1020        }
1021
1022        // Calculate the hypothetical position where the element's top border edge
1023        // would have been if the element's `clear` property had been `none`.
1024        let hypothetical_block_position = self.position_without_clearance(block_start_margin);
1025
1026        // Check if the hypothetical position is past the relevant floats,
1027        // in that case we don't need to add clearance.
1028        let clear_position = match clear {
1029            Clear::None => unreachable!(),
1030            Clear::InlineStart => self.floats.clear_inline_start_position,
1031            Clear::InlineEnd => self.floats.clear_inline_end_position,
1032            Clear::Both => self
1033                .floats
1034                .clear_inline_start_position
1035                .max(self.floats.clear_inline_end_position),
1036        };
1037        if hypothetical_block_position >= clear_position {
1038            None
1039        } else {
1040            Some(clear_position)
1041        }
1042    }
1043
1044    /// Returns the amount of clearance (if any) that a block with the given `clear` value
1045    /// needs to have at `current_block_position_including_margins()`.
1046    /// `block_start_margin` is the top margin of the block, after collapsing (if possible)
1047    /// with the margin of its contents. This must not be included in `current_margin`,
1048    /// since adding clearance will prevent `current_margin` and `block_start_margin`
1049    /// from collapsing together.
1050    ///
1051    /// <https://www.w3.org/TR/2011/REC-CSS2-20110607/visuren.html#flow-control>
1052    pub(crate) fn calculate_clearance(
1053        &self,
1054        clear: Clear,
1055        block_start_margin: &CollapsedMargin,
1056    ) -> Option<Au> {
1057        self.calculate_clear_position(clear, block_start_margin)
1058            .map(|offset| offset - self.position_with_zero_clearance(block_start_margin))
1059    }
1060
1061    /// Adds a new adjoining margin.
1062    pub(crate) fn adjoin_assign(&mut self, margin: &CollapsedMargin) {
1063        self.current_margin.adjoin_assign(margin)
1064    }
1065
1066    /// Get the offset of the current containing block and any uncollapsed margins.
1067    pub(crate) fn current_containing_block_offset(&self) -> Au {
1068        self.floats.containing_block_info.block_start +
1069            self.floats
1070                .containing_block_info
1071                .block_start_margins_not_collapsed
1072                .solve()
1073    }
1074
1075    /// This function places a Fragment that has been created for a FloatBox. Returns the logical
1076    /// content rectangle of the float in the containing block.
1077    pub(crate) fn place_float_fragment(
1078        &mut self,
1079        box_fragment: &BoxFragment,
1080        containing_block: &ContainingBlock,
1081        margins_collapsing_with_parent_containing_block: CollapsedMargin,
1082        block_offset_from_containing_block_top: Au,
1083    ) -> LogicalRect<Au> {
1084        let block_start_of_containing_block_in_bfc = self.floats.containing_block_info.block_start +
1085            self.floats
1086                .containing_block_info
1087                .block_start_margins_not_collapsed
1088                .adjoin(&margins_collapsing_with_parent_containing_block)
1089                .solve();
1090
1091        self.floats.set_ceiling_from_non_floats(
1092            block_start_of_containing_block_in_bfc + block_offset_from_containing_block_top,
1093        );
1094
1095        let style = box_fragment.style().clone();
1096        let container_writing_mode = containing_block.style.writing_mode;
1097        let logical_float_size = LogicalVec2::from_physical_size(
1098            &box_fragment.content_rect().size,
1099            container_writing_mode,
1100        );
1101        let pbm_sums = LogicalSides::from_physical(
1102            &box_fragment.padding_border_margin(),
1103            container_writing_mode,
1104        );
1105        let margin_box_start_corner = self.floats.add_float(&PlacementInfo {
1106            size: logical_float_size + pbm_sums.sum(),
1107            side: FloatSide::from_style_and_container_writing_mode(&style, container_writing_mode)
1108                .expect("Float box wasn't floated!"),
1109            clear: Clear::from_style_and_container_writing_mode(&style, container_writing_mode),
1110        });
1111
1112        // Re-calculate relative adjustment so that it is not lost when the BoxFragment's
1113        // `content_rect` is overwritten below.
1114        let relative_offset = match style.get_box().position {
1115            Position::Relative => relative_adjustement(&style, containing_block),
1116            _ => LogicalVec2::zero(),
1117        };
1118
1119        // This is the position of the float in the float-containing block formatting context. We add the
1120        // existing start corner here because we may have already gotten some relative positioning offset.
1121        let new_position_in_bfc =
1122            margin_box_start_corner + pbm_sums.start_offset() + relative_offset;
1123
1124        // This is the position of the float relative to the containing block start.
1125        let new_position_in_containing_block = LogicalVec2 {
1126            inline: new_position_in_bfc.inline - self.floats.containing_block_info.inline_start,
1127            block: new_position_in_bfc.block - block_start_of_containing_block_in_bfc,
1128        };
1129
1130        let rect = LogicalRect {
1131            start_corner: new_position_in_containing_block,
1132            size: LogicalVec2::from_physical_size(
1133                &box_fragment.content_rect().size,
1134                container_writing_mode,
1135            ),
1136        };
1137        box_fragment
1138            .base
1139            .set_rect(rect.as_physical_deprecated(containing_block));
1140        rect
1141    }
1142}