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