[Text autosizing] [iPadOS] Further adjust our heuristics to determine text autosizing...
authorwenson_hsieh@apple.com <wenson_hsieh@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Sun, 14 Jul 2019 03:36:19 +0000 (03:36 +0000)
committerwenson_hsieh@apple.com <wenson_hsieh@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Sun, 14 Jul 2019 03:36:19 +0000 (03:36 +0000)
https://bugs.webkit.org/show_bug.cgi?id=199780
<rdar://problem/52289088>

Reviewed by Simon Fraser.

Source/WebCore:

Our current idempotent text autosizing candidate heuristic makes the right judgment call most of the time, but
there is still a large batch of text autosizing bugs left unfixed by the first iteration of the heuristic added
in r246781. This patch attempts to address most of these bugs by adjusting the decision-tree-based heuristic
once again, mostly with improvements to the model generation pipeline.

During the first iteration, I placed emphasis on tuning the max tree depth and min leaf size hyperparameters
when coming up with my decision tree, and didn't consider the inclusion or exclusion of each feature as a
hyperparameters. As such, the trees generated using the pipeline tended to use too many features, and as a
result, tended to have cross-validation overall accuracy scores hovering around 73%.

In this revised model generation pipeline, I now consider the inclusion of each feature (along with max depth
and min leaf size, as before) as a hyperparameter. Since this increases the number of hyperparameters by many
orders of magnitude, a naive grid search (as described in the prior ChangeLog entry) is no longer a tractible
procedure for tuning hyperparameters to the training algorithm.

Instead, I now use a stochastic greedy algorithm to search for good sets of hyperparameters; this process begins
with seeding some number (usually 20-24) of "searchers" with completely randomized sets of hyperparameters (i.e.
random max depth, random leaf size, and random subsets of features). I then evaluate the average performance of
each set of hyperparameters by using them to generate 2000 decision trees over 90% of the training data, and
then cross-validating these trees against the remaining 10%. These cross-validation scores are aggregated into a
single confusion matrix, which is then passed into a loss function that computes a single value indicating how
well training with the set of hyperparameters generalized to cross-validation data. After experimenting with
various loss functions, I settled on the following:

`k(false positive rate)^2 + (false negative rate)^2`

...where a constant k is chosen to penalize false positives (i.e. broken layout) more harshly than false
negatives (small text). Additionally, squaring the false negative and false positive rates seems to help avoid
converging on solutions that heavily favor reducing only false positives or false negatives, or vice versa.

The stochastic algorithm starts by computing a loss value for the randomly generated configuration. Then, for
an indefinite number of iterations, it randomly mutates the configuration (e.g. by adding or removing features,
or changing min leaf size or max tree depth) and computes a new loss value for the mutated configuration. If the
mutated configuration performs better (i.e. achieves lower loss) than the current configuration, I set the
current configuration to be the mutated configuration. Otherwise, I keep the current (non-mutated) configuration
as-is. The stochastic algorithm then proceeds, ad-infinitum, with this current configuration.

Of course, since each mutation is small, this strategy so far is prone to leaving each searcher stuck in local
optima. To mitigate this, for each searcher, I keep track of a side-table of configurations that have already
been tested; when random mutations would normally lead to testing a configuration that has already been tested,
each searcher instead increases the chance of applying additional mutations. This has the effect of searchers
initially exhausting similar configurations, and expanding to test more and more dissimilar configurations as
the local alternatives all turn out to be worse. This allows searchers to effectively jump out of local optima
after being stuck for a long time.

So, using these strategies, I simultaneously ran a handful of searchers until they all appeared to converge
(a process that takes 8-12 hours on my current dataset). Many of the searchers achieved configurations with
cross-validation scores of 81% and above, up from the 73% of the previous attempt. These additionally have the
added bonus of reducing the number of features, often making the final trees themselves shallower and simpler to
understand than before.

This patch introduces one such decision tree generated using a set of hyperparameters acquired via this
stochasic search algorithm; it appears to simultaneously use fewer features, and achieve better cross-validation
performance.

Test: fast/text-autosizing/ios/idempotentmode/idempotent-autosizing-candidates.html

* css/StyleResolver.cpp:
(WebCore::StyleResolver::adjustRenderStyleForTextAutosizing):

Adjust the early return to bail if either (1) the element is a candidate and the computed size is already equal
to the boosted size, or (2) the element is not a candidate and the computed size is already equal to the
specified size. Since the autosizing candidate heuristic depends on styles specified on the element itself (as
opposed to styles on any element in the ancestor chain), a parent may be an autosizing candidate, but a child of
it may not.

* rendering/style/RenderStyle.cpp:
(WebCore::RenderStyle::isIdempotentTextAutosizingCandidate const):

Revamp the idempotent text autosizing candidate heuristic. See the explanation above for more details.

* rendering/style/RenderStyle.h:

Remove some bits from RenderStyle's autosizeStatus, now that we care about fewer bits of information from the
inherited flags.

* rendering/style/TextSizeAdjustment.cpp:
(WebCore::AutosizeStatus::updateStatus):
* rendering/style/TextSizeAdjustment.h:

LayoutTests:

Rebaseline an existing idempotent text autosizing test, and add an additional test case.

* fast/text-autosizing/ios/idempotentmode/idempotent-autosizing-candidates-expected.txt:
* fast/text-autosizing/ios/idempotentmode/idempotent-autosizing-candidates.html:

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@247421 268f45cc-cd09-0410-ab3c-d52691b4dbfc

LayoutTests/ChangeLog
LayoutTests/fast/text-autosizing/ios/idempotentmode/idempotent-autosizing-candidates-expected.txt
LayoutTests/fast/text-autosizing/ios/idempotentmode/idempotent-autosizing-candidates.html
Source/WebCore/ChangeLog
Source/WebCore/css/StyleResolver.cpp
Source/WebCore/rendering/style/RenderStyle.cpp
Source/WebCore/rendering/style/RenderStyle.h
Source/WebCore/rendering/style/TextSizeAdjustment.cpp
Source/WebCore/rendering/style/TextSizeAdjustment.h

index ba636e0..0ac5b32 100644 (file)
@@ -1,3 +1,16 @@
+2019-07-13  Wenson Hsieh  <wenson_hsieh@apple.com>
+
+        [Text autosizing] [iPadOS] Further adjust our heuristics to determine text autosizing candidates
+        https://bugs.webkit.org/show_bug.cgi?id=199780
+        <rdar://problem/52289088>
+
+        Reviewed by Simon Fraser.
+
+        Rebaseline an existing idempotent text autosizing test, and add an additional test case.
+
+        * fast/text-autosizing/ios/idempotentmode/idempotent-autosizing-candidates-expected.txt:
+        * fast/text-autosizing/ios/idempotentmode/idempotent-autosizing-candidates.html:
+
 2019-07-13  Simon Fraser  <simon.fraser@apple.com>
 
         Don't do async overflow scrolling for visibility:hidden scrollers
index 0a6c89e..6207278 100644 (file)
@@ -13,7 +13,7 @@ PASS result is 12
 Checking target7:
 PASS result is >= result2
 Checking target8:
-PASS result is >= 13
+PASS result is 12
 Checking target9:
 PASS result is >= 13
 Checking target10:
@@ -21,15 +21,17 @@ PASS result is >= 13
 Checking target11:
 PASS result is >= 13
 Checking target12:
-PASS result is 12
-Checking target13:
 PASS result is >= 13
+Checking target13:
+PASS result is 12
 Checking target14:
 PASS result is 12
 Checking target15:
 PASS result is >= 13
 Checking target16:
 PASS result is >= 13
+Checking target17:
+PASS result is 12
 PASS successfullyParsed is true
 
 TEST COMPLETE
@@ -48,3 +50,4 @@ Test
 Test
 Test
 Test
+Test
index 96f7faf..90ae44a 100644 (file)
@@ -25,8 +25,9 @@ if (window.internals) {
 <div style="background: green;"><span id="target12" style="font-size: 12px; height: 20px; position: fixed; float: right;">Test</span></div>
 <div style="background: green;"><span id="target13" style="font-size: 12px; height: 20px; position: fixed; float: right; overflow-x: hidden; width: 100px;">Test</span></div>
 <div style="background: green;"><span id="target14" style="font-size: 12px; height: 20px; width: 100px; float: right;">Test</span></div>
-<div style="background: green;"><span id="target15" style="overflow-y: hidden; float: right;">Test</span></div>
-<div style="background: green;"><span id="target16" style="float: right;">Test</span></div>
+<div style="background: green;"><span id="target15" style="font-size: 12px; overflow-y: hidden; float: right;">Test</span></div>
+<div style="background: green;"><span id="target16" style="font-size: 12px; float: right;">Test</span></div>
+<div style="background: green;"><span id="target17" style="font-size: 12px; -webkit-text-size-adjust: 100%;">Test</span></div>
 <script>
 let result;
 function check(name, shouldGetAutosized) {
@@ -55,18 +56,19 @@ result = Number.parseInt(window.getComputedStyle(target).getPropertyValue("font-
 let result2 = Number.parseInt(window.getComputedStyle(comparison).getPropertyValue("font-size"));
 shouldBeGreaterThanOrEqual("result", "result2");
 
-check("target8", true);
+check("target8", false);
 check("target9", true);
 check("target10", true);
 
 // Below are some common scenarios where we prefer (or prefer to not) adjust text size. These examples are inspired by
 // common patterns in real webpages.
 check("target11", true);
-check("target12", false);
-check("target13", true);
+check("target12", true);
+check("target13", false);
 check("target14", false);
 check("target15", true);
 check("target16", true);
+check("target17", false);
 </script>
 <script src="../../../../resources/js-test-post.js"></script>
 </body>
index f276240..7ac2fc0 100644 (file)
@@ -1,3 +1,91 @@
+2019-07-13  Wenson Hsieh  <wenson_hsieh@apple.com>
+
+        [Text autosizing] [iPadOS] Further adjust our heuristics to determine text autosizing candidates
+        https://bugs.webkit.org/show_bug.cgi?id=199780
+        <rdar://problem/52289088>
+
+        Reviewed by Simon Fraser.
+
+        Our current idempotent text autosizing candidate heuristic makes the right judgment call most of the time, but
+        there is still a large batch of text autosizing bugs left unfixed by the first iteration of the heuristic added
+        in r246781. This patch attempts to address most of these bugs by adjusting the decision-tree-based heuristic
+        once again, mostly with improvements to the model generation pipeline.
+
+        During the first iteration, I placed emphasis on tuning the max tree depth and min leaf size hyperparameters
+        when coming up with my decision tree, and didn't consider the inclusion or exclusion of each feature as a
+        hyperparameters. As such, the trees generated using the pipeline tended to use too many features, and as a
+        result, tended to have cross-validation overall accuracy scores hovering around 73%.
+
+        In this revised model generation pipeline, I now consider the inclusion of each feature (along with max depth
+        and min leaf size, as before) as a hyperparameter. Since this increases the number of hyperparameters by many
+        orders of magnitude, a naive grid search (as described in the prior ChangeLog entry) is no longer a tractible
+        procedure for tuning hyperparameters to the training algorithm.
+
+        Instead, I now use a stochastic greedy algorithm to search for good sets of hyperparameters; this process begins
+        with seeding some number (usually 20-24) of "searchers" with completely randomized sets of hyperparameters (i.e.
+        random max depth, random leaf size, and random subsets of features). I then evaluate the average performance of
+        each set of hyperparameters by using them to generate 2000 decision trees over 90% of the training data, and
+        then cross-validating these trees against the remaining 10%. These cross-validation scores are aggregated into a
+        single confusion matrix, which is then passed into a loss function that computes a single value indicating how
+        well training with the set of hyperparameters generalized to cross-validation data. After experimenting with
+        various loss functions, I settled on the following:
+
+        `k(false positive rate)^2 + (false negative rate)^2`
+
+        ...where a constant k is chosen to penalize false positives (i.e. broken layout) more harshly than false
+        negatives (small text). Additionally, squaring the false negative and false positive rates seems to help avoid
+        converging on solutions that heavily favor reducing only false positives or false negatives, or vice versa.
+
+        The stochastic algorithm starts by computing a loss value for the randomly generated configuration. Then, for
+        an indefinite number of iterations, it randomly mutates the configuration (e.g. by adding or removing features,
+        or changing min leaf size or max tree depth) and computes a new loss value for the mutated configuration. If the
+        mutated configuration performs better (i.e. achieves lower loss) than the current configuration, I set the
+        current configuration to be the mutated configuration. Otherwise, I keep the current (non-mutated) configuration
+        as-is. The stochastic algorithm then proceeds, ad-infinitum, with this current configuration.
+
+        Of course, since each mutation is small, this strategy so far is prone to leaving each searcher stuck in local
+        optima. To mitigate this, for each searcher, I keep track of a side-table of configurations that have already
+        been tested; when random mutations would normally lead to testing a configuration that has already been tested,
+        each searcher instead increases the chance of applying additional mutations. This has the effect of searchers
+        initially exhausting similar configurations, and expanding to test more and more dissimilar configurations as
+        the local alternatives all turn out to be worse. This allows searchers to effectively jump out of local optima
+        after being stuck for a long time.
+
+        So, using these strategies, I simultaneously ran a handful of searchers until they all appeared to converge
+        (a process that takes 8-12 hours on my current dataset). Many of the searchers achieved configurations with
+        cross-validation scores of 81% and above, up from the 73% of the previous attempt. These additionally have the
+        added bonus of reducing the number of features, often making the final trees themselves shallower and simpler to
+        understand than before.
+
+        This patch introduces one such decision tree generated using a set of hyperparameters acquired via this
+        stochasic search algorithm; it appears to simultaneously use fewer features, and achieve better cross-validation
+        performance.
+
+        Test: fast/text-autosizing/ios/idempotentmode/idempotent-autosizing-candidates.html
+
+        * css/StyleResolver.cpp:
+        (WebCore::StyleResolver::adjustRenderStyleForTextAutosizing):
+
+        Adjust the early return to bail if either (1) the element is a candidate and the computed size is already equal
+        to the boosted size, or (2) the element is not a candidate and the computed size is already equal to the
+        specified size. Since the autosizing candidate heuristic depends on styles specified on the element itself (as
+        opposed to styles on any element in the ancestor chain), a parent may be an autosizing candidate, but a child of
+        it may not.
+
+        * rendering/style/RenderStyle.cpp:
+        (WebCore::RenderStyle::isIdempotentTextAutosizingCandidate const):
+
+        Revamp the idempotent text autosizing candidate heuristic. See the explanation above for more details.
+
+        * rendering/style/RenderStyle.h:
+
+        Remove some bits from RenderStyle's autosizeStatus, now that we care about fewer bits of information from the
+        inherited flags.
+
+        * rendering/style/TextSizeAdjustment.cpp:
+        (WebCore::AutosizeStatus::updateStatus):
+        * rendering/style/TextSizeAdjustment.h:
+
 2019-07-13  Simon Fraser  <simon.fraser@apple.com>
 
         Don't do async overflow scrolling for visibility:hidden scrollers
index 8901ab0..46f4f26 100644 (file)
@@ -907,16 +907,18 @@ void StyleResolver::adjustRenderStyleForTextAutosizing(RenderStyle& style, const
         style.setLineHeight({ minimumLineHeight, Fixed });
     };
 
-    if (!style.isIdempotentTextAutosizingCandidate())
-        return adjustLineHeightIfNeeded(style.computedFontSize());
-
     auto fontDescription = style.fontDescription();
-    auto initialComputedFontSize = fontDescription.computedSize(); 
+    auto initialComputedFontSize = fontDescription.computedSize();
+    auto specifiedFontSize = fontDescription.specifiedSize();
+    bool isCandidate = style.isIdempotentTextAutosizingCandidate();
+    if (!isCandidate && WTF::areEssentiallyEqual(initialComputedFontSize, specifiedFontSize))
+        return;
+
     auto adjustedFontSize = AutosizeStatus::idempotentTextSize(fontDescription.specifiedSize(), initialScale);
-    if (initialComputedFontSize == adjustedFontSize)
+    if (isCandidate && WTF::areEssentiallyEqual(initialComputedFontSize, adjustedFontSize))
         return;
 
-    fontDescription.setComputedSize(adjustedFontSize);
+    fontDescription.setComputedSize(isCandidate ? adjustedFontSize : specifiedFontSize);
     style.setFontDescription(WTFMove(fontDescription));
     style.fontCascade().update(&document().fontSelector());
     adjustLineHeightIfNeeded(adjustedFontSize);
index b0e288b..2d2e83a 100644 (file)
@@ -500,23 +500,47 @@ bool RenderStyle::isIdempotentTextAutosizingCandidate() const
         return false;
 
     if (fields.contains(AutosizeStatus::Fields::FixedHeight)) {
-        if (whiteSpace() == WhiteSpace::NoWrap)
+        if (fields.contains(AutosizeStatus::Fields::FixedWidth)) {
+            if (whiteSpace() == WhiteSpace::NoWrap) {
+                if (width().isFixed())
+                    return false;
+
+                return true;
+            }
+
+            if (fields.contains(AutosizeStatus::Fields::Floating))
+                return false;
+
+            if (fields.contains(AutosizeStatus::Fields::OverflowXHidden))
+                return false;
+
             return true;
+        }
 
-        if (fields.contains(AutosizeStatus::Fields::Floating))
-            return fields.contains(AutosizeStatus::Fields::OutOfFlowPosition) && fields.contains(AutosizeStatus::Fields::OverflowXHidden);
+        if (fields.contains(AutosizeStatus::Fields::OverflowXHidden)) {
+            if (fields.contains(AutosizeStatus::Fields::Floating))
+                return false;
 
-        if (fields.contains(AutosizeStatus::Fields::FixedWidth))
-            return !fields.contains(AutosizeStatus::Fields::OutOfFlowPosition);
-    }
+            return true;
+        }
 
-    if (fields.contains(AutosizeStatus::Fields::Floating))
         return true;
+    }
+
+    if (width().isFixed())
+        return false;
+
+    if (textSizeAdjust().isPercentage() && textSizeAdjust().percentage() == 100) {
+        if (fields.contains(AutosizeStatus::Fields::Floating))
+            return true;
 
-    if (fields.contains(AutosizeStatus::Fields::FixedWidth))
-        return fields.contains(AutosizeStatus::Fields::OverflowYHidden);
+        if (fields.contains(AutosizeStatus::Fields::FixedWidth))
+            return true;
+
+        return false;
+    }
 
-    return !fields.contains(AutosizeStatus::Fields::OverflowYHidden) && !fields.contains(AutosizeStatus::Fields::FixedMaxWidth);
+    return true;
 }
 
 AutosizeStatus RenderStyle::autosizeStatus() const
index c0d837d..70defad 100644 (file)
@@ -1835,9 +1835,9 @@ private:
         // 48 bits
 
 #if ENABLE(TEXT_AUTOSIZING)
-        unsigned autosizeStatus : 8;
+        unsigned autosizeStatus : 5;
 #endif
-        // 56 bits
+        // 53 bits
     };
 
     // This constructor is used to implement the replace operation.
index cc1da80..bd2130e 100644 (file)
@@ -49,24 +49,15 @@ void AutosizeStatus::updateStatus(RenderStyle& style)
     if (style.display() == DisplayType::None)
         result.add(Fields::DisplayNone);
 
-    if (style.hasOutOfFlowPosition())
-        result.add(Fields::OutOfFlowPosition);
-
     if (style.height().isFixed())
         result.add(Fields::FixedHeight);
 
     if (style.width().isFixed())
         result.add(Fields::FixedWidth);
 
-    if (style.maxWidth().isFixed())
-        result.add(Fields::FixedMaxWidth);
-
     if (style.overflowX() == Overflow::Hidden)
         result.add(Fields::OverflowXHidden);
 
-    if (style.overflowY() == Overflow::Hidden)
-        result.add(Fields::OverflowYHidden);
-
     if (style.isFloating())
         result.add(Fields::Floating);
 
index ffc0344..55f2f62 100644 (file)
@@ -57,9 +57,6 @@ public:
         FixedWidth = 1 << 2,
         Floating = 1 << 3,
         OverflowXHidden = 1 << 4,
-        OverflowYHidden = 1 << 5,
-        OutOfFlowPosition = 1 << 6,
-        FixedMaxWidth = 1 << 7
         // Adding new values requires giving RenderStyle::InheritedFlags::autosizeStatus additional bits.
     };