Attachment 425457 Details for Bug 224047 – Patch

[patch] Patch

bug-224047-20210407165738.patch (text/plain), 10.55 KB, created by Yusuke Suzuki on 2021-04-07 16:57:39 PDT

(hide)

Description:

Filename:

MIME Type:

Creator: Yusuke Suzuki

Created: 2021-04-07 16:57:39 PDT

Size: 10.55 KB

patch

obsolete

>Subversion Revision: 275626
>diff --git a/Source/JavaScriptCore/ChangeLog b/Source/JavaScriptCore/ChangeLog
>index 8036e009e002f293259b3541d7260ac6be6229d9..8387f67019493582dca550f7f61c04ec7c15b6dc 100644
>--- a/Source/JavaScriptCore/ChangeLog
>+++ b/Source/JavaScriptCore/ChangeLog
>@@ -1,3 +1,29 @@
>+2021-04-07  Yusuke Suzuki  <ysuzuki@apple.com>
>+
>+        [JSC] DUCET level-1 weighs are equal if characters are alphabets
>+        https://bugs.webkit.org/show_bug.cgi?id=224047
>+
>+        Reviewed by Saam Barati and Mark Lam.
>+
>+        ASCII comparison optimization was based on that DUCET level-1 weights are all different (except for 0000 case), but this was wrong.
>+        If we have the same latin letters with different capitalization, then they have the same level-1 weight ('A' v.s. 'a').
>+        In this patch,
>+
>+            1. If we found that the result of level-1 weight comparison is equal, and characters are not equal, then we do level-3 weight comparison.
>+               We do not perform level-2 since they are all the same weight in ASCII (excluding control characters) region.
>+            2. We do not perform level-4 weight comparison since level-1 and level-3 comparison must distinguish the strings. Level-1 weights are equal
>+               only when characters are the same latin letters. And level-3 weight puts different weights for capital latin letters. Since we already know
>+               that these strings are different while they are equal in level-1 weight comparison, the only case is that they have same latin letters in
>+               the same position. In that case, level-3 weight must say different results for these characters so that we never meet "equal" status in
>+               level-3 weight comparison if characters are different.
>+
>+        * runtime/IntlObject.cpp:
>+        * runtime/IntlObject.h:
>+        * runtime/IntlObjectInlines.h:
>+        (JSC::canUseASCIIUCADUCETComparison):
>+        (JSC::compareASCIIWithUCADUCETLevel3):
>+        (JSC::compareASCIIWithUCADUCET):
>+
> 2021-04-07  Yusuke Suzuki  <ysuzuki@apple.com>
> 
>         [JSC] Use FixedVector more in bytecode dir and JumpTable
>diff --git a/Source/JavaScriptCore/runtime/IntlObject.cpp b/Source/JavaScriptCore/runtime/IntlObject.cpp
>index 9d536d74c019d18da75837d59ab738796eed6029..d5acce0346e9eef02c31cc31c1c344aa7c503c3a 100644
>--- a/Source/JavaScriptCore/runtime/IntlObject.cpp
>+++ b/Source/JavaScriptCore/runtime/IntlObject.cpp
>@@ -432,11 +432,16 @@ const LocaleSet& intlAvailableLocales()
> //     3. If an input is an ASCII string, no multiple character collation elements exist. So no special handling in UCA step-2 is required. For example, "LÂ·" is not ASCII.
> //     4. UCA step-3 handles 0000 weighted characters specially. And ASCII contains these characters. But 0000 elements are used only for rare control characters.
> //        We can ignore this special handling if ASCII strings do not include control characters.
>-//     5. Except 0000 cases, all characters' level-1 weights are different. And level-2 weights are always 0020, which is lower than any level-1 weights.
>-//        This means that binary comparison in UCA step-4 do not need to check level 2~ weights.
>+//     5. Level-1 weights are different except for 0000 cases and capital / lower ASCII characters. All non-0000 elements are larger than 0000.
>+//     6. Level-2 weights are always 0020 except for 0000 cases. So if we include 0000 characters, we do not need to perform level-2 weight comparison.
>+//     7. In all levels, characters have non-0000 weights if it does not have 0000 weight in level-1.
>+//     8. In level-1, weights are the same only when characters are the same latin letters ('A' v.s. 'a'). If level-1 weight comparison says EQUAL, and if characters are not binary-equal,
>+//        then, the only case is they are including the same latin letters with different capitalization at the same position. Level-3 weight comparison must distinguish them since level-3
>+//        weight is set only for latin capital letters. Thus, we do not need to perform level-4 weight comparison.
> //
>-//  Based on the above observation, our fast path handles ASCII strings excluding control characters. The following weight is recomputed weights from level-1 weights.
>-const uint8_t ducetWeights[128] = {
>+//  Based on the above observation, our fast path handles ASCII strings excluding control characters. We first compare strings with level-1 weights. And then,
>+//  if we found they are the same and if we found they are not binary-equal strings, then we perform comparison with level-3 and level-4 weights.
>+const uint8_t ducetLevel1Weights[128] = {
>     0, 0, 0, 0, 0, 0, 0, 0,
>     0, 1, 2, 3, 4, 5, 0, 0,
>     0, 0, 0, 0, 0, 0, 0, 0,
>@@ -445,14 +450,35 @@ const uint8_t ducetWeights[128] = {
>     17, 18, 24, 32, 9, 8, 14, 25,
>     39, 40, 41, 42, 43, 44, 45, 46,
>     47, 48, 11, 10, 33, 34, 35, 13,
>-    23, 50, 52, 54, 56, 58, 60, 62,
>-    64, 66, 68, 70, 72, 74, 76, 78,
>-    80, 82, 84, 86, 88, 90, 92, 94,
>-    96, 98, 100, 19, 26, 20, 31, 7,
>-    30, 49, 51, 53, 55, 57, 59, 61,
>-    63, 65, 67, 69, 71, 73, 75, 77,
>-    79, 81, 83, 85, 87, 89, 91, 93,
>-    95, 97, 99, 21, 36, 22, 37, 0,
>+    23, 49, 50, 51, 52, 53, 54, 55,
>+    56, 57, 58, 59, 60, 61, 62, 63,
>+    64, 65, 66, 67, 68, 69, 70, 71,
>+    72, 73, 74, 19, 26, 20, 31, 7,
>+    30, 49, 50, 51, 52, 53, 54, 55,
>+    56, 57, 58, 59, 60, 61, 62, 63,
>+    64, 65, 66, 67, 68, 69, 70, 71,
>+    72, 73, 74, 21, 36, 22, 37, 0,
>+};
>+
>+// Level 2 are all zeros.
>+
>+const uint8_t ducetLevel3Weights[128] = {
>+    0, 0, 0, 0, 0, 0, 0, 0,
>+    0, 0, 0, 0, 0, 0, 0, 0,
>+    0, 0, 0, 0, 0, 0, 0, 0,
>+    0, 0, 0, 0, 0, 0, 0, 0,
>+    0, 0, 0, 0, 0, 0, 0, 0,
>+    0, 0, 0, 0, 0, 0, 0, 0,
>+    0, 0, 0, 0, 0, 0, 0, 0,
>+    0, 0, 0, 0, 0, 0, 0, 0,
>+    0, 1, 1, 1, 1, 1, 1, 1,
>+    1, 1, 1, 1, 1, 1, 1, 1,
>+    1, 1, 1, 1, 1, 1, 1, 1,
>+    1, 1, 1, 0, 0, 0, 0, 0,
>+    0, 0, 0, 0, 0, 0, 0, 0,
>+    0, 0, 0, 0, 0, 0, 0, 0,
>+    0, 0, 0, 0, 0, 0, 0, 0,
>+    0, 0, 0, 0, 0, 0, 0, 0,
> };
> 
> const LocaleSet& intlCollatorAvailableLocales()
>diff --git a/Source/JavaScriptCore/runtime/IntlObject.h b/Source/JavaScriptCore/runtime/IntlObject.h
>index 6140c20d6fd3e8e8b528975d63848ff183fcab71..e93c9be84481eef4c3f75f7635d9816f1e87da97 100644
>--- a/Source/JavaScriptCore/runtime/IntlObject.h
>+++ b/Source/JavaScriptCore/runtime/IntlObject.h
>@@ -35,7 +35,8 @@ struct UFieldPositionIterator;
> 
> namespace JSC {
> 
>-extern const uint8_t ducetWeights[128];
>+extern const uint8_t ducetLevel1Weights[128];
>+extern const uint8_t ducetLevel3Weights[128];
> 
> enum class LocaleMatcher : uint8_t {
>     Lookup,
>diff --git a/Source/JavaScriptCore/runtime/IntlObjectInlines.h b/Source/JavaScriptCore/runtime/IntlObjectInlines.h
>index 2639bd055bb6c39ab6cab789ffaa8b64cd4641d7..2adb85b5411ec754fd779b63664025b5b2f951d0 100644
>--- a/Source/JavaScriptCore/runtime/IntlObjectInlines.h
>+++ b/Source/JavaScriptCore/runtime/IntlObjectInlines.h
>@@ -154,27 +154,49 @@ ResultType intlOption(JSGlobalObject* globalObject, Optional<JSObject&> options,
> 
> ALWAYS_INLINE bool canUseASCIIUCADUCETComparison(UChar character)
> {
>-    return isASCII(character) && ducetWeights[character];
>+    return isASCII(character) && ducetLevel1Weights[character];
>+}
>+
>+template<typename CharacterType1, typename CharacterType2>
>+UCollationResult compareASCIIWithUCADUCETLevel3(const CharacterType1* characters1, const CharacterType2* characters2, unsigned length)
>+{
>+    for (unsigned position = 0; position < length; ++position) {
>+        auto lhs = characters1[position];
>+        auto rhs = characters2[position];
>+        uint8_t leftWeight = ducetLevel3Weights[lhs];
>+        uint8_t rightWeight = ducetLevel3Weights[rhs];
>+        if (leftWeight == rightWeight)
>+            continue;
>+        return leftWeight > rightWeight ? UCOL_GREATER : UCOL_LESS;
>+    }
>+    return UCOL_EQUAL;
> }
> 
> template<typename CharacterType1, typename CharacterType2>
> inline UCollationResult compareASCIIWithUCADUCET(const CharacterType1* characters1, unsigned length1, const CharacterType2* characters2, unsigned length2)
> {
>+    bool notSameCharacters = false;
>     unsigned commonLength = std::min(length1, length2);
>     for (unsigned position = 0; position < commonLength; ++position) {
>         auto lhs = characters1[position];
>         auto rhs = characters2[position];
>         ASSERT(canUseASCIIUCADUCETComparison(lhs));
>         ASSERT(canUseASCIIUCADUCETComparison(rhs));
>-        uint8_t leftWeight = ducetWeights[lhs];
>-        uint8_t rightWeight = ducetWeights[rhs];
>+        if (lhs == rhs)
>+            continue;
>+        notSameCharacters = true;
>+        uint8_t leftWeight = ducetLevel1Weights[lhs];
>+        uint8_t rightWeight = ducetLevel1Weights[rhs];
>         if (leftWeight == rightWeight)
>             continue;
>         return leftWeight > rightWeight ? UCOL_GREATER : UCOL_LESS;
>     }
> 
>-    if (length1 == length2)
>+    if (length1 == length2) {
>+        if (notSameCharacters)
>+            return compareASCIIWithUCADUCETLevel3(characters1, characters2, length1);
>         return UCOL_EQUAL;
>+    }
>     return length1 > length2 ? UCOL_GREATER : UCOL_LESS;
> }
> 
>diff --git a/JSTests/ChangeLog b/JSTests/ChangeLog
>index a0903110e2bccadf147892b4e375a5aba68f3c65..b2c9615619bc5ac64059903d1e7c271e1f5a973e 100644
>--- a/JSTests/ChangeLog
>+++ b/JSTests/ChangeLog
>@@ -1,3 +1,13 @@
>+2021-04-07  Yusuke Suzuki  <ysuzuki@apple.com>
>+
>+        [JSC] DUCET level-1 weighs are equal if characters are alphabets
>+        https://bugs.webkit.org/show_bug.cgi?id=224047
>+
>+        Reviewed by Saam Barati and Mark Lam.
>+
>+        * stress/ducet-level-3-or-4-comparison.js: Added.
>+        (shouldBe):
>+
> 2021-04-07  Yusuke Suzuki  <ysuzuki@apple.com>
> 
>         [JSC] Update test262
>diff --git a/JSTests/stress/ducet-level-3-or-4-comparison.js b/JSTests/stress/ducet-level-3-or-4-comparison.js
>new file mode 100644
>index 0000000000000000000000000000000000000000..a42b3b57aee4a6e849f19cb2c1d5cdf1ecfbf8c9
>--- /dev/null
>+++ b/JSTests/stress/ducet-level-3-or-4-comparison.js
>@@ -0,0 +1,17 @@
>+function shouldBe(actual, expected) {
>+    if (actual !== expected)
>+        throw new Error('bad value: ' + actual);
>+}
>+
>+var collator = new Intl.Collator('en-US');
>+
>+shouldBe(collator.compare("ABC", "ABD Ã"), -1);
>+shouldBe(collator.compare("ABD Ã", "AbE"), -1);
>+shouldBe(collator.compare("AbE", "ABC"), 1);
>+shouldBe(collator.compare("ABC", "abc"), 1);
>+shouldBe(collator.compare("ABC", "ABC"), 0);
>+shouldBe(collator.compare("abc", "abc"), 0);
>+
>+shouldBe(collator.compare("AB - AS Foobar", "AB - AS Pulheim KÃÆÃÂ¤ther"), -1);
>+shouldBe(collator.compare("AB - AS Pulheim KÃÆÃÂ¤ther", "Abz - Baz Qux"), -1);
>+shouldBe(collator.compare("Abz - Baz Qux", "AB - AS Foobar"), 1);

Actions: View | Formatted Diff | Diff

Attachments on bug 224047: 424894 | 425441 | 425444 | 425454 | 425457