⎇ devin/1785205225-fix-grid-track-limit-overflow
src/compute/float.rs
Ñawpa willay
Pi imata llamkarqan
ch'uya
Fix panic in FloatContext::subdivide_segment and enforce CSS2 float rule 5 (#988)
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::{debug::debug_log, sys::Vec, 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 debug_log!("old_segment", dbg:&mut *old_segment);
212 debug_log!("divide_at_y", 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 in either direction (CSS2 float rule 5:
268 // "The outer top of a floating box may not be higher than the outer top of any block
269 // or floated box generated by an element earlier in the source document")
270 // - Respects "clear"
271 let float_start = self.last_placed_floats[0].start.max(self.last_placed_floats[1].start);
272 let hwm = match clear {
273 Clear::Left => {
274 let left_end = self.last_placed_floats[0].end;
275 float_start.max(left_end + 1)
276 }
277 Clear::Right => {
278 let right_end = self.last_placed_floats[1].end;
279 float_start.max(right_end + 1)
280 }
281 Clear::Both => {
282 let left_end = self.last_placed_floats[0].end;
283 let right_end = self.last_placed_floats[1].end;
284 left_end.max(right_end) + 1
285 }
286 Clear::None => float_start,
287 };
288
289 // Ensure that float is placed in a segment at or below "min_y"
290 // (ensuring that it is placed at or below min_y within it's segment happens below)
291 let start_idx = self
292 .segments
293 .get(hwm..)
294 .and_then(|segments| segments.iter().position(|segment| segment.y.end > min_y).map(|idx| idx + hwm));
295
296 let mut start_idx = start_idx.unwrap_or(self.segments.len());
297 let mut start_y = min_y;
298 let mut end_idx = start_idx;
299 // let mut end_y = min_y;
300
301 // Loop over remaining segments, trying to place the float in a position
302 // that has space to accomodate it.
303 let (start, mut end, placed_inset) = 'outer: loop {
304 // Start segment does not exist:
305 //
306 // This means no existing segment can accomodate the float so we must create a new
307 // segment below all existing segments. A new segment will always have space for
308 // the float, so we can exit the loop at this point.
309 let Some(start_segment) = self.segments.get(start_idx) else {
310 break (None, None, containing_block_insets[slot]);
311 };
312
313 // Candidate start segment doesn't have (horizontal) space for the float:
314 // => retry with the next segment
315 if !start_segment.fits_float_width(floated_box, direction, self.available_width) {
316 start_idx += 1;
317 end_idx = end_idx.max(start_idx);
318 continue;
319 }
320
321 start_y = start_y.max(start_segment.y.start);
322 let available_height = start_segment.y.end - start_y;
323 let mut fitter = FloatFitter::new(self.available_width, available_height, containing_block_insets);
324 fitter.union_insets(start_segment.insets);
325
326 // Pinning the start segment, loop over segments starting with the start segment
327 // to find the end segment:
328 // - The selected segment range must have enough height to contain the float
329 // - All of the segments in the range must have enough horizontal width to contain the float
330 // TODO: must ensure that width is in the correct place.
331 loop {
332 // End segment does not exist:
333 //
334 // This means no existing segment can accomodate the float so we must create a new
335 // segment below all existing segments
336 let Some(end_segment) = self.segments.get(end_idx) else {
337 let inset = fitter.insets[slot];
338 break 'outer (Some(start_idx), None, inset);
339 };
340
341 // Check horizontal fit
342 //
343 // If it does not fit horizontally then it will never fit in this position, so
344 // continue the outer loop to find and check a new position
345 fitter.union_insets(end_segment.insets);
346 if !fitter.fits_horiontally(floated_box.width) {
347 start_idx += 1;
348 end_idx = end_idx.max(start_idx);
349 continue 'outer;
350 }
351
352 // Check vertical fit
353 //
354 // If it does not (yet) fit vertically then continue the inner loop to add another
355 // segment to the range of segments we are placing the float in
356 if end_idx != start_idx {
357 fitter.add_height(end_segment.y.end - end_segment.y.start);
358 }
359 if !fitter.fits_vertically(floated_box.height) {
360 end_idx += 1;
361 continue;
362 }
363
364 let inset = fitter.insets[slot];
365 break 'outer (Some(start_idx), Some(end_idx), inset);
366 }
367 };
368
369 // Short-circuit for zero-sized boxes
370 if floated_box.width == 0.0 || floated_box.height == 0.0 {
371 // TODO: need to update last_placed_float?
372
373 return PlacedFloatedBox {
374 width: floated_box.width,
375 height: floated_box.height,
376 y: start_y,
377 x_inset: placed_inset,
378 };
379 }
380
381 // Handle case where floated box is placed after all existing segments
382 if start.is_none() {
383 let last_y_end = self.segments.last().map(|seg| seg.y.end).unwrap_or(0.0);
384 if start_y > last_y_end {
385 self.segments.push(Segment { y: last_y_end..start_y, insets: [0.0, 0.0] });
386 }
387
388 let start_y = last_y_end.max(start_y);
389
390 let mut insets = containing_block_insets;
391 insets[slot] += floated_box.width;
392 self.segments.push(Segment { y: start_y..(start_y + floated_box.height), insets });
393
394 // Update last_placed_float
395 let start_idx = self.segments.len() - 1;
396 let end_idx = start_idx + 1;
397 self.update_last_placed_float(direction, start_idx..end_idx);
398
399 return PlacedFloatedBox {
400 width: floated_box.width,
401 height: floated_box.height,
402 y: start_y,
403 x_inset: containing_block_insets[slot],
404 };
405 }
406
407 // Else unwrap the index of the segment that the start of the floating box is placed in
408 let mut start_idx = start.unwrap();
409
410 // If the floated box doesn't start at the exact same y-offset as the segment it starts in, then
411 // subdivide that segment into two segments at the y-offset that the floated box starts at, and increment
412 // `start_idx` so that the floating box is placed in the second of the two segments.
413 if start_y != self.segments[start_idx].y.start {
414 self.subdivide_segment(start_idx, start_y);
415 start_idx += 1;
416 if let Some(end_idx) = end.as_mut() {
417 *end_idx += 1;
418 }
419 }
420
421 let end_idx = match end {
422 None => {
423 let last_y_end = self.segments.last().map(|seg| seg.y.end).unwrap_or(0.0);
424 if min_y > last_y_end {
425 self.segments.push(Segment { y: last_y_end..min_y, insets: [0.0, 0.0] });
426 }
427 self.segments.len() - 1
428 }
429 Some(mut end_idx) => {
430 let end_y = start_y + floated_box.height;
431
432 // Due to floating point imprecision, `end_y` may coincide with (or fall before)
433 // the start of the end segment even though the sum of the candidate segment
434 // heights was computed as sufficient. In that case the float effectively ends at
435 // the boundary of the previous segment, so walk back to the segment that actually
436 // contains `end_y`.
437 while end_idx > start_idx && end_y <= self.segments[end_idx].y.start {
438 end_idx -= 1;
439 }
440
441 // Only subdivide if `end_y` falls strictly within the segment. If it lands on
442 // (or, due to floating point imprecision, beyond) a segment boundary then no
443 // subdivision is needed.
444 if self.segments[end_idx].y.start < end_y && end_y < self.segments[end_idx].y.end {
445 self.subdivide_segment(end_idx, end_y);
446 }
447
448 end_idx
449 }
450 };
451
452 // Update inset for the range of segments that the float is placed in
453 let placed_inset_plus_width = placed_inset + floated_box.width;
454 for segment in &mut self.segments[start_idx..=end_idx] {
455 segment.insets[slot] = placed_inset_plus_width;
456 }
457
458 // Update last_placed_float
459 self.update_last_placed_float(direction, start_idx..(end_idx + 1));
460
461 PlacedFloatedBox { width: floated_box.width, height: floated_box.height, y: start_y, x_inset: placed_inset }
462 }
463
464 /// Get the end segment of the last float on side(s) specified by the clear parameter (if any)
465 fn cleared_segment(&self, clear: Clear) -> Option<usize> {
466 match clear {
467 Clear::Left => Some(self.last_placed_floats[0].end),
468 Clear::Right => Some(self.last_placed_floats[1].end),
469 Clear::Both => {
470 let left_end = self.last_placed_floats[0].end;
471 let right_end = self.last_placed_floats[1].end;
472 Some(left_end.max(right_end))
473 }
474 Clear::None => None,
475 }
476 }
477
478 /// Get the bottom of lowest relevant float for the specific clear property
479 pub fn cleared_threshold(&self, clear: Clear) -> Option<f32> {
480 self.cleared_segment(clear).and_then(|idx| self.segments.get(idx.max(1) - 1)).map(|seg| seg.y.end)
481 }
482
483 /// Search for a space suitable for laying out non-floated content into
484 pub fn find_content_slot(
485 &self,
486 min_y: f32,
487 containing_block_insets: [f32; 2],
488 clear: Clear,
489 after: Option<usize>,
490 ) -> ContentSlot {
491 if !self.has_active_floats(min_y) {
492 return ContentSlot {
493 segment_id: None,
494 x: containing_block_insets[0],
495 y: min_y,
496 width: self.available_width - containing_block_insets[0] - containing_block_insets[1],
497 height: f32::INFINITY,
498 };
499 }
500
501 // The min starting segment index
502 let at_least = after.map(|idx| idx + 1).unwrap_or(0);
503 let hwm = at_least.max(self.cleared_segment(clear).map(|idx| idx + 1).unwrap_or(0));
504
505 let start_idx = self
506 .segments
507 .get(hwm..)
508 .and_then(|segments| segments.iter().position(|segment| segment.y.end > min_y).map(|idx| idx + hwm));
509 let start_idx = start_idx.unwrap_or(self.segments.len());
510 let segment = self.segments.get(start_idx);
511 match segment {
512 Some(segment) => {
513 let inset_left = segment.insets[0].max(containing_block_insets[0]);
514 let inset_right = segment.insets[1].max(containing_block_insets[1]);
515 ContentSlot {
516 segment_id: Some(start_idx),
517 x: inset_left,
518 y: segment.y.start.max(min_y),
519 width: self.available_width - inset_left - inset_right,
520 height: f32::INFINITY,
521 }
522 }
523 None => ContentSlot {
524 segment_id: None,
525 x: containing_block_insets[0],
526 y: min_y,
527 width: self.available_width - containing_block_insets[0] - containing_block_insets[1],
528 height: f32::INFINITY,
529 },
530 }
531 }
532}
533
534/// Context for computing the intrinsic width contribution of a set of floats
535pub struct FloatIntrinsicWidthCalculator {
536 /// The available width of the container
537 available_width: AvailableSpace,
538 /// The running total intrinsic width contribution
539 contribution: f32,
540}
541
542impl FloatIntrinsicWidthCalculator {
543 /// Create a new `FloatIntrinsicWidthCalculator`
544 pub fn new(available_width: AvailableSpace) -> Self {
545 Self { available_width, contribution: 0.0 }
546 }
547
548 /// Add a float to the computation
549 pub fn add_float(&mut self, width: f32, _direction: FloatDirection, _clear: Clear) {
550 match self.available_width {
551 AvailableSpace::Definite(_) => {
552 // We will never hit this code path with definite available space
553 }
554 AvailableSpace::MinContent => self.contribution = self.contribution.max(width),
555 AvailableSpace::MaxContent => self.contribution += width,
556 };
557 }
558
559 /// Get the computed float contribution to intrinsic width
560 pub fn result(&self) -> f32 {
561 self.contribution
562 }
563}