[webkit-changes] [WebKit/WebKit] 2d299a: Provide an initial implementation of `text-wrap: b...

[Commit Queue]

  Branch: refs/heads/main
  Home:   https://github.com/WebKit/WebKit
  Commit: 2d299a2dd8bbf0374011075326ffb8c83433cc4a
      https://github.com/WebKit/WebKit/commit/2d299a2dd8bbf0374011075326ffb8c83433cc4a
  Author: David Choi <david_choi5 at apple.com>
  Date:   2023-08-16 (Wed, 16 Aug 2023)

  Changed paths:
    M LayoutTests/TestExpectations
    M LayoutTests/platform/mac-wk2/TestExpectations
    M Source/WebCore/Sources.txt
    M Source/WebCore/WebCore.xcodeproj/project.pbxproj
    A Source/WebCore/layout/formattingContexts/inline/InlineContentBalancer.cpp
    A Source/WebCore/layout/formattingContexts/inline/InlineContentBalancer.h
    M Source/WebCore/layout/formattingContexts/inline/InlineFormattingContext.cpp
    M Source/WebCore/layout/formattingContexts/inline/TextOnlySimpleLineBuilder.cpp
    M Source/WebCore/layout/integration/LayoutIntegrationCoverage.cpp

  Log Message:
  -----------
  Provide an initial implementation of `text-wrap: balance`
https://bugs.webkit.org/show_bug.cgi?id=249840
rdar://problem/103663513

Reviewed by Alan Baradlay.

This patch implements `text-wrap: balance` in IFC. It uses a Knuth-Plass
style dynamic programming algorithm to minimize the variance of all the
line lengths. There is no line limit imposed on this implementation.

Ideally, the act of balancing inline content will use the same number of
lines as if the inline content was laid out via `text-wrap: wrap`. However,
adhering to this ideal is expensive, and not caring about this ideal will
allow us to use a more efficient algorithm. Since inline content spanning
many lines is less likely to care about the exact preservation of vertical
space (i.e. number of lines used), we ignore this ideal number of lines
requirement beyond a certain line count (tentatively set to 12 lines for now).

There are two implementations of the Knuth-Plass style algorithm:
    (1) one which attempts to preserve the number of lines used, and
    (2) one that ignores that requirement.
If we let N denote the number of break opportunities, let L denote the
number of lines used, and let K denote the maximum number of inline items
that can fit in a single line, then algorithm (1) has a time complexity of
O(N * L * K), while algorithm (2) has a time complexity of O(N * K).

We use algorithm (1) when we want to preserve the number of lines used,
and we use algorithm (2) when we want to prioritize performance (i.e. when
inline content spans many lines). It is worth noting that algorithm (2)
will often also preserve the number of lines used. In the case that it
does not, the number of lines will differ only by a small amount.

This is an initial implementation, and not all features are supported.
Unsupported features include (and are not limited to):
- first-line styling
- indentation
- white-space-collapse
- tabs
- hyphens
- floats (including initial-letter)

* LayoutTests/TestExpectations:
* LayoutTests/platform/mac-wk2/TestExpectations:
* Source/WebCore/Sources.txt:
* Source/WebCore/WebCore.xcodeproj/project.pbxproj:
* Source/WebCore/layout/formattingContexts/inline/InlineContentBalancer.cpp: Added.
(WebCore::Layout::computeBreakOpportunities):
(WebCore::Layout::computeCost):
(WebCore::Layout::InlineContentBalancer::InlineContentBalancer):
(WebCore::Layout::InlineContentBalancer::initialize):
(WebCore::Layout::InlineContentBalancer::computeBalanceConstraints):
(WebCore::Layout::InlineContentBalancer::balanceRangeWithLineRequirement):
(WebCore::Layout::InlineContentBalancer::balanceRangeWithNoLineRequirement):
(WebCore::Layout::InlineContentBalancer::inlineItemWidth const):
(WebCore::Layout::InlineContentBalancer::shouldTrimLeading const):
(WebCore::Layout::InlineContentBalancer::shouldTrimTrailing const):
(WebCore::Layout::InlineContentBalancer::SlidingWidth::SlidingWidth):
(WebCore::Layout::InlineContentBalancer::SlidingWidth::width):
(WebCore::Layout::InlineContentBalancer::SlidingWidth::advanceStart):
(WebCore::Layout::InlineContentBalancer::SlidingWidth::advanceStartTo):
(WebCore::Layout::InlineContentBalancer::SlidingWidth::advanceEnd):
(WebCore::Layout::InlineContentBalancer::SlidingWidth::advanceEndTo):
* Source/WebCore/layout/formattingContexts/inline/InlineContentBalancer.h: Added.
* Source/WebCore/layout/formattingContexts/inline/InlineFormattingContext.cpp:
(WebCore::Layout::InlineFormattingContext::layoutInFlowAndFloatContent):
* Source/WebCore/layout/formattingContexts/inline/TextOnlySimpleLineBuilder.cpp:
(WebCore::Layout::TextOnlySimpleLineBuilder::isEligibleForSimplifiedTextOnlyInlineLayout):
* Source/WebCore/layout/integration/LayoutIntegrationCoverage.cpp:
(WebCore::LayoutIntegration::shouldInvalidateLineLayoutPathAfterChangeFor):

Canonical link: https://commits.webkit.org/266980@main