Modified: trunk/Source/_javascript_Core/ChangeLog (240991 => 240992)
--- trunk/Source/_javascript_Core/ChangeLog 2019-02-05 21:59:52 UTC (rev 240991)
+++ trunk/Source/_javascript_Core/ChangeLog 2019-02-05 22:09:32 UTC (rev 240992)
@@ -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-05 Mark Lam <mark....@apple.com>
Move DFG nodes that clobberize() says will write(Heap) to the doesGC() list that returns true.
Modified: trunk/Source/_javascript_Core/runtime/IntlNumberFormat.cpp (240991 => 240992)
--- trunk/Source/_javascript_Core/runtime/IntlNumberFormat.cpp 2019-02-05 21:59:52 UTC (rev 240991)
+++ trunk/Source/_javascript_Core/runtime/IntlNumberFormat.cpp 2019-02-05 22:09:32 UTC (rev 240992)
@@ -510,16 +510,19 @@
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 @@
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
Modified: trunk/Source/_javascript_Core/runtime/IntlNumberFormat.h (240991 => 240992)
--- trunk/Source/_javascript_Core/runtime/IntlNumberFormat.h 2019-02-05 21:59:52 UTC (rev 240991)
+++ trunk/Source/_javascript_Core/runtime/IntlNumberFormat.h 2019-02-05 22:09:32 UTC (rev 240992)
@@ -95,13 +95,12 @@
};
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);
