Attachment 361205 Details for Bug 185557 – Patch

[patch] Patch

bug-185557-20190205121618.patch (text/plain), 5.39 KB, created by Andy VanWagoner on 2019-02-05 11:16:18 PST

(hide)

Description:

Filename:

MIME Type:

Creator: Andy VanWagoner

Created: 2019-02-05 11:16:18 PST

Size: 5.39 KB

patch

obsolete

>Subversion Revision: 240975
>diff --git a/Source/JavaScriptCore/ChangeLog b/Source/JavaScriptCore/ChangeLog
>index 17fc4efc0e2b12455432f4f88187635cf22e4b81..cb53b71467dc2ec82db9be5c12d5ebd7e1d50287 100644
>--- a/Source/JavaScriptCore/ChangeLog
>+++ b/Source/JavaScriptCore/ChangeLog
>@@ -1,3 +1,19 @@
>+2019-02-05  Andy VanWagoner  <andy@vanwagoner.family>
>+
>+        [INTL] improve efficiency of Intl.NumberFormat formatToParts
>+        https://bugs.webkit.org/show_bug.cgi?id=185557
>+
>+        Reviewed by Mark Lam.
>+
>+        Since field nesting depth is minimal, this algorithm should be effectively O(n),
>+        where n is the number of characters in the formatted string.
>+        It may be less memory efficient than the previous impl, since the intermediate Vector
>+        is the length of the string, instead of the count of the fields.
>+
>+        * runtime/IntlNumberFormat.cpp:
>+        (JSC::IntlNumberFormat::formatToParts):
>+        * runtime/IntlNumberFormat.h:
>+
> 2019-02-04  Yusuke Suzuki  <ysuzuki@apple.com>
> 
>         Unreviewed, add missing exception checks after r240637
>diff --git a/Source/JavaScriptCore/runtime/IntlNumberFormat.cpp b/Source/JavaScriptCore/runtime/IntlNumberFormat.cpp
>index 4d41845d9d2f5f93c90357e6cac82ca4090b2c76..e0158a3f96353e99181d4fd4cb747b3618710b38 100644
>--- a/Source/JavaScriptCore/runtime/IntlNumberFormat.cpp
>+++ b/Source/JavaScriptCore/runtime/IntlNumberFormat.cpp
>@@ -510,16 +510,19 @@ JSValue IntlNumberFormat::formatToParts(ExecState& exec, double value)
>     if (U_FAILURE(status))
>         return throwTypeError(&exec, scope, "failed to format a number."_s);
> 
>-    Vector<IntlNumberFormatField> fields;
>+    int32_t literalFieldType = -1;
>+    auto literalField = IntlNumberFormatField(literalFieldType, resultLength);
>+    Vector<IntlNumberFormatField> fields(resultLength, literalField);
>     int32_t beginIndex = 0;
>     int32_t endIndex = 0;
>     auto fieldType = ufieldpositer_next(fieldItr.get(), &beginIndex, &endIndex);
>     while (fieldType >= 0) {
>-        IntlNumberFormatField field;
>-        field.type = UNumberFormatFields(fieldType);
>-        field.beginIndex = beginIndex;
>-        field.endIndex = endIndex;
>-        fields.append(field);
>+        auto size = endIndex - beginIndex;
>+        for (auto i = beginIndex; i < endIndex; ++i) {
>+            // Only override previous value if new value is more specific.
>+            if (fields[i].size >= size)
>+                fields[i] = IntlNumberFormatField(fieldType, size);
>+        }
>         fieldType = ufieldpositer_next(fieldItr.get(), &beginIndex, &endIndex);
>     }
> 
>@@ -533,29 +536,21 @@ JSValue IntlNumberFormat::formatToParts(ExecState& exec, double value)
>     auto typePropertyName = Identifier::fromString(&vm, "type");
>     auto literalString = jsString(&exec, "literal"_s);
> 
>-    // FIXME: <http://webkit.org/b/185557> This is O(N^2) and could be done in O(N log N).
>     int32_t currentIndex = 0;
>     while (currentIndex < resultLength) {
>-        IntlNumberFormatField field;
>-        int32_t nextStartIndex = resultLength;
>-        for (const auto &candidate : fields) {
>-            if (candidate.beginIndex <= currentIndex && currentIndex < candidate.endIndex && (!field.size() || candidate.size() < field.size()))
>-                field = candidate;
>-            if (currentIndex < candidate.beginIndex && candidate.beginIndex < nextStartIndex)
>-                nextStartIndex = candidate.beginIndex;
>-        }
>-        auto nextIndex = field.size() ? std::min(field.endIndex, nextStartIndex) : nextStartIndex;
>-        auto type = field.size() ? jsString(&exec, partTypeString(field.type, value)) : literalString;
>-        auto value = jsSubstring(&vm, resultString, currentIndex, nextIndex - currentIndex);
>+        auto startIndex = currentIndex;
>+        auto fieldType = fields[currentIndex].type;
>+        while (currentIndex < resultLength && fields[currentIndex].type == fieldType)
>+            ++currentIndex;
>+        auto partType = fieldType == literalFieldType ? literalString : jsString(&exec, partTypeString(UNumberFormatFields(fieldType), value));
>+        auto partValue = jsSubstring(&vm, resultString, startIndex, currentIndex - startIndex);
>         JSObject* part = constructEmptyObject(&exec);
>-        part->putDirect(vm, typePropertyName, type);
>-        part->putDirect(vm, vm.propertyNames->value, value);
>+        part->putDirect(vm, typePropertyName, partType);
>+        part->putDirect(vm, vm.propertyNames->value, partValue);
>         parts->putDirectIndex(&exec, index++, part);
>         RETURN_IF_EXCEPTION(scope, { });
>-        currentIndex = nextIndex;
>     }
> 
>-
>     return parts;
> }
> #endif
>diff --git a/Source/JavaScriptCore/runtime/IntlNumberFormat.h b/Source/JavaScriptCore/runtime/IntlNumberFormat.h
>index 1d9c4843725228bd22b3929a31f3e8cf95aa947a..9d4f47d6f3199f3d1a5f3161c0b2e03ab8c83ae6 100644
>--- a/Source/JavaScriptCore/runtime/IntlNumberFormat.h
>+++ b/Source/JavaScriptCore/runtime/IntlNumberFormat.h
>@@ -95,13 +95,12 @@ private:
>     };
> 
>     struct IntlNumberFormatField {
>-        UNumberFormatFields type;
>-        int32_t beginIndex { 0 };
>-        int32_t endIndex { 0 };
>-        int32_t size() const
>-        {
>-            return endIndex - beginIndex;
>-        };
>+        int32_t type;
>+        int32_t size;
>+        IntlNumberFormatField(int32_t type, int32_t size)
>+            : type(type)
>+            , size(size)
>+        { }
>     };
> 
>     static ASCIILiteral partTypeString(UNumberFormatFields, double);

Actions: View | Formatted Diff | Diff

Attachments on bug 185557: 360910 | 361205