Branch: refs/heads/main
Home: https://github.com/WebKit/WebKit
Commit: 13ce6a6997552903710c15201202a8fb7907d5df
https://github.com/WebKit/WebKit/commit/13ce6a6997552903710c15201202a8fb7907d5df
Author: Issac Roy <[email protected]>
Date: 2026-09-01 (Tue, 01 Sep 2026)
Changed paths:
M LayoutTests/TestExpectations
M
LayoutTests/imported/w3c/web-platform-tests/css/css-flexbox/balance/balance-negative-margin-002-expected.txt
M Source/WebCore/Headers.cmake
M Source/WebCore/Sources.txt
M Source/WebCore/WebCore.xcodeproj/project.pbxproj
M Source/WebCore/layout/formattingContexts/flex/FlexFormattingContext.cpp
A Source/WebCore/layout/formattingContexts/flex/FlexLineBreaker.cpp
A Source/WebCore/layout/formattingContexts/flex/FlexLineBreaker.h
Log Message:
-----------
Implement the flex-wrap: balance line breaker
https://bugs.webkit.org/show_bug.cgi?id=323010
rdar://186274279
Reviewed by Alan Baradlay.
css-flexbox-2 9.7 asks `flex-wrap: balance` to divide flex items into lines
that minimize the sum of squared free space, instead of greedily filling each
line.
New FlexLineBreaker.{h,cpp} holds both breakers as free functions over
std::span<const LayoutUnit>, so neither needs a FlexLayoutItem or a formatting
context and both are unit-testable. greedyLineBreaks is the existing loop from
computeFlexLines moved verbatim. computeFlexLines now flattens the outer
hypothetical main sizes once, picks a breaker, and shares one loop to build
ranges and hypotheticalMainSizes.
balancedLineBreaks is a dynamic program over suffixes: minScores[start] is the
best total for items start..n, and bestEndForStart records where that line ends.
The suffix direction is what gets the tie-break right. The spec breaks ties
front-to-back -- most items on the first line, then the second -- so among equal
minima the line starting at `start` must be the longest one, which the `<=`
comparison records as the scan walks `end` upward.
Costs O(n * L) for L items on the fullest line, so quadratic only when one line
can hold most of the items. In the case that we lack performance, a better
solution for such cases is LARSCH, which is O(n) but costs a few hundred lines.
Item sizes are floored at 0 when building the prefix sums, per 9.7's closing
line. greedyLineBreaks deliberately does not floor: CSS Flexbox 1 9.3 sums outer
hypothetical main sizes as-is, and negative margins legitimately shorten a line
there. Squared free space reaches 2^62, so five near-empty lines can overflow a
uint64_t sum; totalScore saturates instead, and a saturated total never compares
better than a real one.
Two bounds keep the search off its worst case. lastFittingEnd[start] is one
two-pointer sweep giving the last item that still fits, so the inner loop runs
over items-per-line rather than n, making the whole thing O(n * L). And a
container that fits everything returns a single line immediately: no line of any
split has a smaller error, and a split sums at least as many of them.
flex-line-count is not implemented, so the 17 balance expectations that remain
are the tests requiring it. They need a second dimension on the DP plus a
measurement pass that divides the available size by the line count, and are
left for a follow-up.
Tests: imported/w3c/web-platform-tests/css/css-flexbox/balance/
* LayoutTests/TestExpectations:
*
LayoutTests/imported/w3c/web-platform-tests/css/css-flexbox/balance/balance-negative-margin-002-expected.txt:
* Source/WebCore/Headers.cmake:
* Source/WebCore/Sources.txt:
* Source/WebCore/WebCore.xcodeproj/project.pbxproj:
* Source/WebCore/layout/formattingContexts/flex/FlexFormattingContext.cpp:
(WebCore::FlexFormattingContext::computeFlexLines):
* Source/WebCore/layout/formattingContexts/flex/FlexLineBreaker.cpp: Added.
(WebCore::greedyLineBreaks):
(WebCore::balancedLineBreaks):
* Source/WebCore/layout/formattingContexts/flex/FlexLineBreaker.h: Added.
Canonical link: https://commits.webkit.org/320259@main
To unsubscribe from these emails, change your notification settings at
https://github.com/WebKit/WebKit/settings/notifications
