Fix build when block_layout is enabled bu float_layout isn't
1//! Computes the position of floats in a block formatting context
2//!
3//! Here are the precise rules that govern the behavior of floats:
4//!
5//! 1. The left outer edge of a left-floating box may not be to the left of the left edge of its containing block. An analogous rule
6//! holds for right-floating elements.
7//! 2. If the current box is left-floating, and there are any left-floating boxes generated by elements earlier in the source document,
8//! then for each such earlier box, either the left outer edge of the current box must be to the right of the right outer edge of the earlier box,
9//! or its top must be lower than the bottom of the earlier box. Analogous rules hold for right-floating boxes.
10//! 3. The right outer edge of a left-floating box may not be to the right of the left outer edge of any right-floating box that is next to it.
11//! Analogous rules hold for right-floating elements.
12//! 4. A floating box's outer top may not be higher than the top of its containing block. When the float occurs between two collapsing margins,
13//! the float is positioned as if it had an otherwise empty anonymous block parent taking part in the flow. The position of such a parent is defined
14//! by the rules in the section on margin collapsing.
15//! 5. The outer top of a floating box may not be higher than the outer top of any block or floated box generated by an element earlier in the source document.
16//! 6. The outer top of an element's floating box may not be higher than the top of any line-box containing a box generated by
17//! an element earlier in the source document.
18//! 7. A left-floating box that has another left-floating box to its left may not have its right outer edge to the right of its containing block's
19//! right edge. (Loosely: a left float may not stick out at the right edge, unless it is already as far to the left as possible.) An analogous rule
20//! holds for right-floating elements.
21//! 8. A floating box must be placed as high as possible.
22//! 9. A left-floating box must be put as far to the left as possible, a right-floating box as far to the right as possible. A higher position is
23//! preferred over one that is further to the left/right.
24//!
25//! But in CSS 2.2, if, within the block formatting context, there is an in-flow negative vertical margin such that the float's position is above the position it would be at were all such negative margins set to zero, the position of the float is undefined.
26//!
27//! <https://www.w3.org/TR/CSS22/visuren.html#floats>
28
29use core::ops::Range;
30
31use crate::{AvailableSpace, Clear, ContentSlot, FloatDirection, Point, Size};
32
33/// A floated box
34#[derive(Debug, Clone, Default)]
35pub struct PlacedFloatedBox {
36 /// A user defined ID for the box
37 // id: u64,
38 /// The width of the box
39 pub width: f32,
40 /// The height of the box
41 pub height: f32,
42 /// Horizontal distance from the edge of the container that the box is floated towards
43 /// (distance from the left for left floats, from the right for right floats)
44 pub x_inset: f32,
45 /// Vertical distance from top edge of the container
46 pub y: f32,
47}
48
49/// A non-overlapping horizontal segment of the Block Formatting Context container
50#[derive(Debug, Clone)]
51struct Segment {
52 /// The vertical start and end points of the segment
53 y: Range<f32>,
54 /// Left inset in slot 0. Right inset in slot 1.
55 insets: [f32; 2],
56}
57
58impl Segment {
59 /// Whether the segment can fit the passed floated box (in the horizontal axis)
60 fn fits_float_width(&self, floated_box: Size<f32>, direction: FloatDirection, bfc_width: f32) -> bool {
61 let slot = direction as usize;
62 self.insets[slot] == 0.0 || (bfc_width - floated_box.width - self.inset_sum()) >= 0.0
63 }
64
65 /// The total space taken up by both insets
66 #[inline(always)]
67 fn inset_sum(&self) -> f32 {
68 self.insets[0] + self.insets[1]
69 }
70}
71
72/// Helper type for placing a single floated box
73///
74/// Given a pinned starting y position, this type helps determine if there is any x position
75/// such that there is sufficient horizontal space for the box accross it's entire height.
76#[derive(Debug, Clone)]
77struct FloatFitter {
78 /// The overall width of the Block Formatting Context
79 bfc_width: f32,
80 /// The total height of the set of segments currently being considered
81 slot_height: f64,
82 /// The union of the insets of the set of segments currently being considered
83 insets: [f32; 2],
84}
85
86impl FloatFitter {
87 /// Create a new `FloatFitter`
88 fn new(bfc_width: f32, slot_height: f32, insets: [f32; 2]) -> Self {
89 Self { bfc_width, slot_height: slot_height as f64, insets }
90 }
91
92 // Horizontal fitting
93
94 /// Union the insets of another segment. This is a "max" of the insets on each side.
95 fn union_insets(&mut self, insets: [f32; 2]) {
96 self.insets[0] = self.insets[0].max(insets[0]);
97 self.insets[1] = self.insets[1].max(insets[1]);
98 }
99
100 /// Given the currently accounted for insets, check whether there is an x position
101 /// such that the box fits horizontally
102 fn fits_horiontally(&self, width: f32) -> bool {
103 self.insets == [0.0, 0.0] || self.bfc_width - self.insets[0] - self.insets[1] - width >= 0.0
104 }
105
106 // Vertical fitting
107
108 /// Add the height of another segment.
109 fn add_height(&mut self, height: f32) {
110 self.slot_height += height as f64;
111 }
112
113 /// Given the currently accounted for height, check whether the box fits vertically
114 fn fits_vertically(&mut self, height: f32) -> bool {
115 self.slot_height >= height as f64
116 }
117}
118
119/// A context for placing floated boxes
120#[derive(Debug, Clone)]
121pub struct FloatContext {
122 /// The available space constraint that applies to the root Block Formatting Context
123 /// for which this `FloatContext` manages floats.
124 available_width: f32,
125 /// Whether the float context contains any floats
126 has_floats: bool,
127 /// A list of left-floated boxes within the context
128 left_floats: Vec<PlacedFloatedBox>,
129 /// A list of right-floated boxes within the context
130 right_floats: Vec<PlacedFloatedBox>,
131 /// A list of non-overlapping horizontal "segments" within the context.
132 /// Each segment has the same available width for it's entire height.
133 segments: Vec<Segment>,
134 /// A closed-open range indicating which segment the last placed float
135 /// was placed(on each side).
136 last_placed_floats: [Range<usize>; 2],
137 // Left hwm in slot 0. Right hwm in slot 1.
138 // high_water_marks: [usize; 2],
139 // left_float_high_water_mark: usize,
140 // right_float_high_water_mark: usize,
141}
142
143impl Default for FloatContext {
144 fn default() -> Self {
145 Self {
146 available_width: 0.0,
147 has_floats: false,
148 left_floats: Vec::new(),
149 right_floats: Vec::new(),
150 segments: Vec::new(),
151 last_placed_floats: [0..0, 0..0], // high_water_marks: [0, 0],
152 }
153 }
154}
155
156impl FloatContext {
157 /// Create a new empty `FloatContext`
158 pub fn new() -> Self {
159 Default::default()
160 }
161
162 /// Whether the float context contains any floats
163 #[inline(always)]
164 pub fn has_floats(&self) -> bool {
165 self.has_floats
166 }
167
168 /// Whether the float context contains any floats that extend to or below min_y
169 #[inline(always)]
170 pub fn has_active_floats(&self, min_y: f32) -> bool {
171 self.has_floats && self.segments.last().map(|seg| seg.y.end).unwrap_or(0.0) > min_y
172 }
173
174 /// Set the width of the `FloatContext`
175 pub fn set_width(&mut self, available_width: f32) {
176 self.available_width = available_width;
177 }
178
179 /// Returns a slice of placed left floats
180 pub fn left_floats(&self) -> &[PlacedFloatedBox] {
181 &self.left_floats
182 }
183
184 /// Returns a slice of placed right floats
185 pub fn right_floats(&self) -> &[PlacedFloatedBox] {
186 &self.right_floats
187 }
188
189 /// Divide a segment into two segments so that a new float can be placed and have it's
190 /// vertical start and end at exact segment boundaries
191 fn subdivide_segment(&mut self, idx: usize, divide_at_y: f32) {
192 let old_segment = &mut self.segments[idx];
193 let new_segment = Segment { insets: old_segment.insets, y: divide_at_y..old_segment.y.end };
194 if !old_segment.y.contains(÷_at_y) || old_segment.y.start == divide_at_y {
195 dbg!(&old_segment);
196 dbg!(divide_at_y);
197 assert!(old_segment.y.contains(÷_at_y) && old_segment.y.start != divide_at_y);
198 }
199 old_segment.y.end = divide_at_y;
200
201 self.segments.splice((idx + 1)..(idx + 1), core::iter::once(new_segment));
202 }
203
204 /// Update the last placed float start and end values
205 fn update_last_placed_float(&mut self, direction: FloatDirection, placement: Range<usize>) {
206 let slot = direction as usize;
207 self.last_placed_floats[slot].start = self.last_placed_floats[slot].start.max(placement.start);
208 self.last_placed_floats[slot].end = self.last_placed_floats[slot].end.max(placement.end);
209 }
210
211 /// Position a floated box with the context, returning the (x, y) coordinates
212 pub fn place_floated_box(
213 &mut self,
214 floated_box: Size<f32>,
215 min_y: f32,
216 containing_block_insets: [f32; 2],
217 direction: FloatDirection,
218 clear: Clear,
219 ) -> Point<f32> {
220 self.has_floats = true;
221
222 let placed_floated_box =
223 self.place_floated_box_inner(floated_box, min_y, containing_block_insets, direction, clear);
224
225 let x_inset = placed_floated_box.x_inset;
226 let y = placed_floated_box.y;
227 match direction {
228 FloatDirection::Left => {
229 self.left_floats.push(placed_floated_box);
230 Point { x: x_inset, y }
231 }
232 FloatDirection::Right => {
233 self.right_floats.push(placed_floated_box);
234 Point { x: self.available_width - x_inset - floated_box.width, y }
235 }
236 }
237 }
238
239 /// Inner implementation of float placement, split into a separate function so that it can early-return
240 fn place_floated_box_inner(
241 &mut self,
242 floated_box: Size<f32>,
243 min_y: f32,
244 containing_block_insets: [f32; 2],
245 direction: FloatDirection,
246 clear: Clear,
247 ) -> PlacedFloatedBox {
248 let slot = direction as usize;
249
250 // Ensure that float:
251 // - Starts at or after the last placed float that was floated in the same direction as it
252 // - Respects "clear"
253 let hwm = match clear {
254 Clear::Left => {
255 let float_dir_start = self.last_placed_floats[slot].start;
256 let left_end = self.last_placed_floats[0].end;
257 float_dir_start.max(left_end + 1)
258 }
259 Clear::Right => {
260 let float_dir_start = self.last_placed_floats[slot].start;
261 let right_end = self.last_placed_floats[1].end;
262 float_dir_start.max(right_end + 1)
263 }
264 Clear::Both => {
265 let left_end = self.last_placed_floats[0].end;
266 let right_end = self.last_placed_floats[1].end;
267 left_end.max(right_end) + 1
268 }
269 Clear::None => {
270 // float_dir_start
271 self.last_placed_floats[slot].start
272 }
273 };
274
275 // Ensure that float is placed in a segment at or below "min_y"
276 // (ensuring that it is placed at or below min_y within it's segment happens below)
277 let start_idx = self
278 .segments
279 .get(hwm..)
280 .and_then(|segments| segments.iter().position(|segment| segment.y.end > min_y).map(|idx| idx + hwm));
281
282 let mut start_idx = start_idx.unwrap_or(self.segments.len());
283 let mut start_y = min_y;
284 let mut end_idx = start_idx;
285 // let mut end_y = min_y;
286
287 // Loop over remaining segments, trying to place the float in a position
288 // that has space to accomodate it.
289 let (start, mut end, placed_inset) = 'outer: loop {
290 // Start segment does not exist:
291 //
292 // This means no existing segment can accomodate the float so we must create a new
293 // segment below all existing segments. A new segment will always have space for
294 // the float, so we can exit the loop at this point.
295 let Some(start_segment) = self.segments.get(start_idx) else {
296 break (None, None, containing_block_insets[slot]);
297 };
298
299 // Candidate start segment doesn't have (horizontal) space for the float:
300 // => retry with the next segment
301 if !start_segment.fits_float_width(floated_box, direction, self.available_width) {
302 start_idx += 1;
303 end_idx = end_idx.max(start_idx);
304 continue;
305 }
306
307 start_y = start_y.max(start_segment.y.start);
308 let available_height = start_segment.y.end - start_y;
309 let mut fitter = FloatFitter::new(self.available_width, available_height, containing_block_insets);
310 fitter.union_insets(start_segment.insets);
311
312 // Pinning the start segment, loop over segments starting with the start segment
313 // to find the end segment:
314 // - The selected segment range must have enough height to contain the float
315 // - All of the segments in the range must have enough horizontal width to contain the float
316 // TODO: must ensure that width is in the correct place.
317 loop {
318 // End segment does not exist:
319 //
320 // This means no existing segment can accomodate the float so we must create a new
321 // segment below all existing segments
322 let Some(end_segment) = self.segments.get(end_idx) else {
323 let inset = fitter.insets[slot];
324 break 'outer (Some(start_idx), None, inset);
325 };
326
327 // Check horizontal fit
328 //
329 // If it does not fit horizontally then it will never fit in this position, so
330 // continue the outer loop to find and check a new position
331 fitter.union_insets(end_segment.insets);
332 if !fitter.fits_horiontally(floated_box.width) {
333 start_idx += 1;
334 end_idx = end_idx.max(start_idx);
335 continue 'outer;
336 }
337
338 // Check vertical fit
339 //
340 // If it does not (yet) fit vertically then continue the inner loop to add another
341 // segment to the range of segments we are placing the float in
342 if end_idx != start_idx {
343 fitter.add_height(end_segment.y.end - end_segment.y.start);
344 }
345 if !fitter.fits_vertically(floated_box.height) {
346 end_idx += 1;
347 continue;
348 }
349
350 let inset = fitter.insets[slot];
351 break 'outer (Some(start_idx), Some(end_idx), inset);
352 }
353 };
354
355 // Short-circuit for zero-sized boxes
356 if floated_box.width == 0.0 || floated_box.height == 0.0 {
357 // TODO: need to update last_placed_float?
358
359 return PlacedFloatedBox {
360 width: floated_box.width,
361 height: floated_box.height,
362 y: start_y,
363 x_inset: placed_inset,
364 };
365 }
366
367 // Handle case where floated box is placed after all existing segments
368 if start.is_none() {
369 let last_y_end = self.segments.last().map(|seg| seg.y.end).unwrap_or(0.0);
370 if start_y > last_y_end {
371 self.segments.push(Segment { y: last_y_end..start_y, insets: [0.0, 0.0] });
372 }
373
374 let start_y = last_y_end.max(start_y);
375
376 let mut insets = containing_block_insets;
377 insets[slot] += floated_box.width;
378 self.segments.push(Segment { y: start_y..(start_y + floated_box.height), insets });
379
380 // Update last_placed_float
381 let start_idx = self.segments.len() - 1;
382 let end_idx = start_idx + 1;
383 self.update_last_placed_float(direction, start_idx..end_idx);
384
385 return PlacedFloatedBox {
386 width: floated_box.width,
387 height: floated_box.height,
388 y: start_y,
389 x_inset: containing_block_insets[slot],
390 };
391 }
392
393 // Else unwrap the index of the segment that the start of the floating box is placed in
394 let mut start_idx = start.unwrap();
395
396 // If the floated box doesn't start at the exact same y-offset as the segment it starts in, then
397 // subdivide that segment into two segments at the y-offset that the floated box starts at, and increment
398 // `start_idx` so that the floating box is placed in the second of the two segments.
399 if start_y != self.segments[start_idx].y.start {
400 self.subdivide_segment(start_idx, start_y);
401 start_idx += 1;
402 if let Some(end_idx) = end.as_mut() {
403 *end_idx += 1;
404 }
405 }
406
407 let end_idx = match end {
408 None => {
409 let last_y_end = self.segments.last().map(|seg| seg.y.end).unwrap_or(0.0);
410 if min_y > last_y_end {
411 self.segments.push(Segment { y: last_y_end..min_y, insets: [0.0, 0.0] });
412 }
413 self.segments.len() - 1
414 }
415 Some(end_idx) => {
416 let end_y = start_y + floated_box.height;
417 if end_y != self.segments[end_idx].y.end {
418 self.subdivide_segment(end_idx, end_y);
419 }
420
421 end_idx
422 }
423 };
424
425 // Update inset for the range of segments that the float is placed in
426 let placed_inset_plus_width = placed_inset + floated_box.width;
427 for segment in &mut self.segments[start_idx..=end_idx] {
428 segment.insets[slot] = placed_inset_plus_width;
429 }
430
431 // Update last_placed_float
432 self.update_last_placed_float(direction, start_idx..(end_idx + 1));
433
434 PlacedFloatedBox { width: floated_box.width, height: floated_box.height, y: start_y, x_inset: placed_inset }
435 }
436
437 /// Get the end segment of the last float on side(s) specified by the clear parameter (if any)
438 fn cleared_segment(&self, clear: Clear) -> Option<usize> {
439 match clear {
440 Clear::Left => Some(self.last_placed_floats[0].end),
441 Clear::Right => Some(self.last_placed_floats[1].end),
442 Clear::Both => {
443 let left_end = self.last_placed_floats[0].end;
444 let right_end = self.last_placed_floats[1].end;
445 Some(left_end.max(right_end))
446 }
447 Clear::None => None,
448 }
449 }
450
451 /// Get the bottom of lowest relevant float for the specific clear property
452 pub fn cleared_threshold(&self, clear: Clear) -> Option<f32> {
453 self.cleared_segment(clear).and_then(|idx| self.segments.get(idx.max(1) - 1)).map(|seg| seg.y.end)
454 }
455
456 /// Search for a space suitable for laying out non-floated content into
457 pub fn find_content_slot(
458 &self,
459 min_y: f32,
460 containing_block_insets: [f32; 2],
461 clear: Clear,
462 after: Option<usize>,
463 ) -> ContentSlot {
464 if !self.has_active_floats(min_y) {
465 return ContentSlot {
466 segment_id: None,
467 x: containing_block_insets[0],
468 y: min_y,
469 width: self.available_width - containing_block_insets[0] - containing_block_insets[1],
470 height: f32::INFINITY,
471 };
472 }
473
474 // The min starting segment index
475 let at_least = after.map(|idx| idx + 1).unwrap_or(0);
476 let hwm = at_least.max(self.cleared_segment(clear).map(|idx| idx + 1).unwrap_or(0));
477
478 let start_idx = self
479 .segments
480 .get(hwm..)
481 .and_then(|segments| segments.iter().position(|segment| segment.y.end > min_y).map(|idx| idx + hwm));
482 let start_idx = start_idx.unwrap_or(self.segments.len());
483 let segment = self.segments.get(start_idx);
484 match segment {
485 Some(segment) => {
486 let inset_left = segment.insets[0].max(containing_block_insets[0]);
487 let inset_right = segment.insets[1].max(containing_block_insets[1]);
488 ContentSlot {
489 segment_id: Some(start_idx),
490 x: inset_left,
491 y: segment.y.start.max(min_y),
492 width: self.available_width - inset_left - inset_right,
493 height: f32::INFINITY,
494 }
495 }
496 None => ContentSlot {
497 segment_id: None,
498 x: containing_block_insets[0],
499 y: min_y,
500 width: self.available_width - containing_block_insets[0] - containing_block_insets[1],
501 height: f32::INFINITY,
502 },
503 }
504 }
505}
506
507/// Context for computing the intrinsic width contribution of a set of floats
508pub struct FloatIntrinsicWidthCalculator {
509 /// The available width of the container
510 available_width: AvailableSpace,
511 /// The running total intrinsic width contribution
512 contribution: f32,
513}
514
515impl FloatIntrinsicWidthCalculator {
516 /// Create a new `FloatIntrinsicWidthCalculator`
517 pub fn new(available_width: AvailableSpace) -> Self {
518 Self { available_width, contribution: 0.0 }
519 }
520
521 /// Add a float to the computation
522 pub fn add_float(&mut self, width: f32, _direction: FloatDirection, _clear: Clear) {
523 match self.available_width {
524 AvailableSpace::Definite(_) => {
525 // We will never hit this code path with definite available space
526 }
527 AvailableSpace::MinContent => self.contribution = self.contribution.max(width),
528 AvailableSpace::MaxContent => self.contribution += width,
529 };
530 }
531
532 /// Get the computed float contribution to intrinsic width
533 pub fn result(&self) -> f32 {
534 self.contribution
535 }
536}