Attachment 360910 Details for Bug 185557 – Patch

[patch] Patch

bug-185557-20190201161439.patch (text/plain), 5.21 KB, created by Andy VanWagoner on 2019-02-01 15:14:40 PST

(hide)

Description:

Filename:

MIME Type:

Creator: Andy VanWagoner

Created: 2019-02-01 15:14:40 PST

Size: 5.21 KB

patch

obsolete

>Subversion Revision: 240859
>diff --git a/Source/JavaScriptCore/ChangeLog b/Source/JavaScriptCore/ChangeLog
>index 67ff36be04f4cb5a023ab85f6e6243546a25a3e2..300951e1cc05979e415fcee11693f6025f6176e0 100644
>--- a/Source/JavaScriptCore/ChangeLog
>+++ b/Source/JavaScriptCore/ChangeLog
>@@ -1,3 +1,19 @@
>+2019-02-01  Andy VanWagoner  <andy@vanwagoner.family>
>+
>+        [INTL] improve efficiency of Intl.NumberFormat formatToParts
>+        https://bugs.webkit.org/show_bug.cgi?id=185557
>+
>+        Reviewed by NOBODY (OOPS!).
>+
>+        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-01  Yusuke Suzuki  <ysuzuki@apple.com>
> 
>         [JSC] Remove cellJSValueOOBSpace
>diff --git a/Source/JavaScriptCore/runtime/IntlNumberFormat.cpp b/Source/JavaScriptCore/runtime/IntlNumberFormat.cpp
>index 4d41845d9d2f5f93c90357e6cac82ca4090b2c76..2ff975d090460791c2bf1d53f1b9129af32023d2 100644
>--- a/Source/JavaScriptCore/runtime/IntlNumberFormat.cpp
>+++ b/Source/JavaScriptCore/runtime/IntlNumberFormat.cpp
>@@ -510,16 +510,18 @@ JSValue IntlNumberFormat::formatToParts(ExecState& exec, double value)
>     if (U_FAILURE(status))
>         return throwTypeError(&exec, scope, "failed to format a number."_s);
> 
>-    Vector<IntlNumberFormatField> fields;
>+    auto literalField = std::make_pair(-1, resultLength);
>+    Vector<std::pair<int32_t, int32_t>> 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].second >= size)
>+                fields[i] = std::make_pair(fieldType, size);
>+        }
>         fieldType = ufieldpositer_next(fieldItr.get(), &beginIndex, &endIndex);
>     }
> 
>@@ -533,29 +535,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].first;
>+        while (currentIndex < resultLength && fields[currentIndex].first == fieldType)
>+            ++currentIndex;
>+        auto partType = fieldType < 0 ? 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..a24f5b4461fd9599a65be3dfc043bed56df9b91b 100644
>--- a/Source/JavaScriptCore/runtime/IntlNumberFormat.h
>+++ b/Source/JavaScriptCore/runtime/IntlNumberFormat.h
>@@ -94,16 +94,6 @@ private:
>         void operator()(UFieldPositionIterator*) const;
>     };
> 
>-    struct IntlNumberFormatField {
>-        UNumberFormatFields type;
>-        int32_t beginIndex { 0 };
>-        int32_t endIndex { 0 };
>-        int32_t size() const
>-        {
>-            return endIndex - beginIndex;
>-        };
>-    };
>-
>     static ASCIILiteral partTypeString(UNumberFormatFields, double);
> #endif
> };

Actions: View | Formatted Diff | Diff

Attachments on bug 185557: 360910 | 361205