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