[INTL] Implement Intl.Collator.prototype.resolvedOptions ()
[WebKit-https.git] / Source / JavaScriptCore / runtime / IntlObject.cpp
1 /*
2  * Copyright (C) 2015 Andy VanWagoner (thetalecrafter@gmail.com)
3  * Copyright (C) 2015 Sukolsak Sakshuwong (sukolsak@gmail.com)
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions
7  * are met:
8  * 1. Redistributions of source code must retain the above copyright
9  *    notice, this list of conditions and the following disclaimer.
10  * 2. Redistributions in binary form must reproduce the above copyright
11  *    notice, this list of conditions and the following disclaimer in the
12  *    documentation and/or other materials provided with the distribution.
13  *
14  * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
15  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
16  * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
17  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
18  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
19  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
20  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
21  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
22  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
23  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
24  * THE POSSIBILITY OF SUCH DAMAGE.
25  */
26
27 #include "config.h"
28 #include "IntlObject.h"
29
30 #if ENABLE(INTL)
31
32 #include "Error.h"
33 #include "FunctionPrototype.h"
34 #include "IntlCollator.h"
35 #include "IntlCollatorConstructor.h"
36 #include "IntlCollatorPrototype.h"
37 #include "IntlDateTimeFormat.h"
38 #include "IntlDateTimeFormatConstructor.h"
39 #include "IntlDateTimeFormatPrototype.h"
40 #include "IntlNumberFormat.h"
41 #include "IntlNumberFormatConstructor.h"
42 #include "IntlNumberFormatPrototype.h"
43 #include "JSCInlines.h"
44 #include "JSCJSValueInlines.h"
45 #include "Lookup.h"
46 #include "ObjectPrototype.h"
47 #include <unicode/uloc.h>
48 #include <wtf/Assertions.h>
49
50 namespace JSC {
51
52 STATIC_ASSERT_IS_TRIVIALLY_DESTRUCTIBLE(IntlObject);
53
54 }
55
56 namespace JSC {
57
58 struct MatcherResult {
59     String locale;
60     String extension;
61     size_t extensionIndex;
62 };
63
64 const ClassInfo IntlObject::s_info = { "Object", &Base::s_info, 0, CREATE_METHOD_TABLE(IntlObject) };
65
66 IntlObject::IntlObject(VM& vm, Structure* structure)
67     : JSNonFinalObject(vm, structure)
68 {
69 }
70
71 IntlObject* IntlObject::create(VM& vm, JSGlobalObject* globalObject, Structure* structure)
72 {
73     IntlObject* object = new (NotNull, allocateCell<IntlObject>(vm.heap)) IntlObject(vm, structure);
74     object->finishCreation(vm, globalObject);
75     return object;
76 }
77
78 void IntlObject::finishCreation(VM& vm, JSGlobalObject* globalObject)
79 {
80     Base::finishCreation(vm);
81     ASSERT(inherits(info()));
82
83     // Set up Collator.
84     IntlCollatorPrototype* collatorPrototype = IntlCollatorPrototype::create(vm, globalObject, IntlCollatorPrototype::createStructure(vm, globalObject, globalObject->objectPrototype()));
85     Structure* collatorStructure = IntlCollator::createStructure(vm, globalObject, collatorPrototype);
86     IntlCollatorConstructor* collatorConstructor = IntlCollatorConstructor::create(vm, IntlCollatorConstructor::createStructure(vm, globalObject, globalObject->functionPrototype()), collatorPrototype, collatorStructure);
87
88     collatorPrototype->putDirectWithoutTransition(vm, vm.propertyNames->constructor, collatorConstructor, DontEnum);
89
90     // Set up NumberFormat.
91     IntlNumberFormatPrototype* numberFormatPrototype = IntlNumberFormatPrototype::create(vm, globalObject, IntlNumberFormatPrototype::createStructure(vm, globalObject, globalObject->objectPrototype()));
92     Structure* numberFormatStructure = IntlNumberFormat::createStructure(vm, globalObject, numberFormatPrototype);
93     IntlNumberFormatConstructor* numberFormatConstructor = IntlNumberFormatConstructor::create(vm, IntlNumberFormatConstructor::createStructure(vm, globalObject, globalObject->functionPrototype()), numberFormatPrototype, numberFormatStructure);
94
95     numberFormatPrototype->putDirectWithoutTransition(vm, vm.propertyNames->constructor, numberFormatConstructor, DontEnum);
96
97     // Set up DateTimeFormat.
98     IntlDateTimeFormatPrototype* dateTimeFormatPrototype = IntlDateTimeFormatPrototype::create(vm, globalObject, IntlDateTimeFormatPrototype::createStructure(vm, globalObject, globalObject->objectPrototype()));
99     Structure* dateTimeFormatStructure = IntlDateTimeFormat::createStructure(vm, globalObject, dateTimeFormatPrototype);
100     IntlDateTimeFormatConstructor* dateTimeFormatConstructor = IntlDateTimeFormatConstructor::create(vm, IntlDateTimeFormatConstructor::createStructure(vm, globalObject, globalObject->functionPrototype()), dateTimeFormatPrototype, dateTimeFormatStructure);
101
102     dateTimeFormatPrototype->putDirectWithoutTransition(vm, vm.propertyNames->constructor, dateTimeFormatConstructor, DontEnum);
103
104     // 8.1 Properties of the Intl Object (ECMA-402 2.0)
105     putDirectWithoutTransition(vm, vm.propertyNames->Collator, collatorConstructor, DontEnum);
106     putDirectWithoutTransition(vm, vm.propertyNames->NumberFormat, numberFormatConstructor, DontEnum);
107     putDirectWithoutTransition(vm, vm.propertyNames->DateTimeFormat, dateTimeFormatConstructor, DontEnum);
108 }
109
110 Structure* IntlObject::createStructure(VM& vm, JSGlobalObject* globalObject, JSValue prototype)
111 {
112     return Structure::create(vm, globalObject, prototype, TypeInfo(ObjectType, StructureFlags), info());
113 }
114
115 static String defaultLocale()
116 {
117     // 6.2.4 DefaultLocale ()
118     // FIXME: Implement this method.
119     return ASCIILiteral("en");
120 }
121
122 bool getIntlBooleanOption(ExecState* exec, JSValue options, PropertyName property, bool& usesFallback)
123 {
124     // 9.2.9 GetOption (options, property, type, values, fallback)
125     // For type="boolean". values is always undefined.
126
127     // 1. Let opts be ToObject(options).
128     JSObject* opts = options.toObject(exec);
129
130     // 2. ReturnIfAbrupt(opts).
131     if (exec->hadException())
132         return false;
133
134     // 3. Let value be Get(opts, property).
135     JSValue value = opts->get(exec, property);
136
137     // 4. ReturnIfAbrupt(value).
138     if (exec->hadException())
139         return false;
140
141     // 5. If value is not undefined, then
142     if (!value.isUndefined()) {
143         // a. Assert: type is "boolean" or "string".
144         // Function dedicated to "boolean".
145
146         // b. If type is "boolean", then
147         // i. Let value be ToBoolean(value).
148         bool booleanValue = value.toBoolean(exec);
149
150         // e. Return value.
151         usesFallback = false;
152         return booleanValue;
153     }
154
155     // 6. Else return fallback.
156     // Because fallback can be undefined, we let the caller handle it instead.
157     usesFallback = true;
158     return false;
159 }
160
161 String getIntlStringOption(ExecState* exec, JSValue options, PropertyName property, const HashSet<String>& values, const char* notFound, String fallback)
162 {
163     // 9.2.9 GetOption (options, property, type, values, fallback)
164     // For type="string".
165
166     // 1. Let opts be ToObject(options).
167     JSObject* opts = options.toObject(exec);
168
169     // 2. ReturnIfAbrupt(opts).
170     if (exec->hadException())
171         return String();
172
173     // 3. Let value be Get(opts, property).
174     JSValue value = opts->get(exec, property);
175
176     // 4. ReturnIfAbrupt(value).
177     if (exec->hadException())
178         return String();
179
180     // 5. If value is not undefined, then
181     if (!value.isUndefined()) {
182         // a. Assert: type is "boolean" or "string".
183         // Function dedicated to "string".
184
185         // c. If type is "string", then
186         // i. Let value be ToString(value).
187         JSString* stringValue = value.toString(exec);
188
189         // ii. ReturnIfAbrupt(value).
190         if (exec->hadException())
191             return String();
192
193         // d. If values is not undefined, then
194         // i. If values does not contain an element equal to value, throw a RangeError exception.
195         if (!values.isEmpty() && !values.contains(stringValue->value(exec))) {
196             exec->vm().throwException(exec, createRangeError(exec, String(notFound)));
197             return String();
198         }
199
200         // e. Return value.
201         return stringValue->value(exec);
202     }
203
204     // 6. Else return fallback.
205     return fallback;
206 }
207
208 static String getPrivateUseLangTag(const Vector<String>& parts, size_t startIndex)
209 {
210     size_t numParts = parts.size();
211     size_t currentIndex = startIndex;
212
213     // Check for privateuse.
214     // privateuse = "x" 1*("-" (2*8alphanum))
215     StringBuilder privateuse;
216     while (currentIndex < numParts) {
217         const String& singleton = parts[currentIndex];
218         unsigned singletonLength = singleton.length();
219         bool isValid = (singletonLength == 1 && (singleton == "x" || singleton == "X"));
220         if (!isValid)
221             break;
222
223         if (currentIndex != startIndex)
224             privateuse.append('-');
225
226         ++currentIndex;
227         unsigned numExtParts = 0;
228         privateuse.append('x');
229         while (currentIndex < numParts) {
230             const String& extPart = parts[currentIndex];
231             unsigned extPartLength = extPart.length();
232
233             bool isValid = (extPartLength >= 2 && extPartLength <= 8 && extPart.isAllSpecialCharacters<isASCIIAlphanumeric>());
234             if (!isValid)
235                 break;
236
237             ++currentIndex;
238             ++numExtParts;
239             privateuse.append('-');
240             privateuse.append(extPart.convertToASCIILowercase());
241         }
242
243         // Requires at least one production.
244         if (!numExtParts)
245             return String();
246     }
247
248     // Leftovers makes it invalid.
249     if (currentIndex < numParts)
250         return String();
251
252     return privateuse.toString();
253 }
254
255 static String getCanonicalLangTag(const Vector<String>& parts)
256 {
257     ASSERT(!parts.isEmpty());
258
259     // Follows the grammar at https://www.rfc-editor.org/rfc/bcp/bcp47.txt
260     // langtag = language ["-" script] ["-" region] *("-" variant) *("-" extension) ["-" privateuse]
261
262     size_t numParts = parts.size();
263     // Check for language.
264     // language = 2*3ALPHA ["-" extlang] / 4ALPHA / 5*8ALPHA
265     size_t currentIndex = 0;
266     const String& language = parts[currentIndex];
267     unsigned languageLength = language.length();
268     bool canHaveExtlang = languageLength >= 2 && languageLength <= 3;
269     bool isValidLanguage = languageLength >= 2 && languageLength <= 8 && language.isAllSpecialCharacters<isASCIIAlpha>();
270     if (!isValidLanguage)
271         return String();
272
273     ++currentIndex;
274     StringBuilder canonical;
275     canonical.append(language.convertToASCIILowercase());
276
277     // Check for extlang.
278     // extlang = 3ALPHA *2("-" 3ALPHA)
279     if (canHaveExtlang) {
280         for (unsigned times = 0; times < 3 && currentIndex < numParts; ++times) {
281             const String& extlang = parts[currentIndex];
282             unsigned extlangLength = extlang.length();
283             if (extlangLength == 3 && extlang.isAllSpecialCharacters<isASCIIAlpha>()) {
284                 ++currentIndex;
285                 canonical.append('-');
286                 canonical.append(extlang.convertToASCIILowercase());
287             } else
288                 break;
289         }
290     }
291
292     // Check for script.
293     // script = 4ALPHA
294     if (currentIndex < numParts) {
295         const String& script = parts[currentIndex];
296         unsigned scriptLength = script.length();
297         if (scriptLength == 4 && script.isAllSpecialCharacters<isASCIIAlpha>()) {
298             ++currentIndex;
299             canonical.append('-');
300             canonical.append(toASCIIUpper(script[0]));
301             canonical.append(script.substring(1, 3).convertToASCIILowercase());
302         }
303     }
304
305     // Check for region.
306     // region = 2ALPHA / 3DIGIT
307     if (currentIndex < numParts) {
308         const String& region = parts[currentIndex];
309         unsigned regionLength = region.length();
310         bool isValidRegion = (
311             (regionLength == 2 && region.isAllSpecialCharacters<isASCIIAlpha>())
312             || (regionLength == 3 && region.isAllSpecialCharacters<isASCIIDigit>())
313         );
314         if (isValidRegion) {
315             ++currentIndex;
316             canonical.append('-');
317             canonical.append(region.upper());
318         }
319     }
320
321     // Check for variant.
322     // variant = 5*8alphanum / (DIGIT 3alphanum)
323     HashSet<String> subtags;
324     while (currentIndex < numParts) {
325         const String& variant = parts[currentIndex];
326         unsigned variantLength = variant.length();
327         bool isValidVariant = (
328             (variantLength >= 5 && variantLength <= 8 && variant.isAllSpecialCharacters<isASCIIAlphanumeric>())
329             || (variantLength == 4 && isASCIIDigit(variant[0]) && variant.substring(1, 3).isAllSpecialCharacters<isASCIIAlphanumeric>())
330         );
331         if (!isValidVariant)
332             break;
333
334         // Cannot include duplicate subtags (case insensitive).
335         String lowerVariant = variant.convertToASCIILowercase();
336         if (!subtags.add(lowerVariant).isNewEntry)
337             return String();
338
339         ++currentIndex;
340
341         // Reordering variant subtags is not required in the spec.
342         canonical.append('-');
343         canonical.append(lowerVariant);
344     }
345
346     // Check for extension.
347     // extension = singleton 1*("-" (2*8alphanum))
348     // singleton = alphanum except x or X
349     subtags.clear();
350     Vector<String> extensions;
351     while (currentIndex < numParts) {
352         const String& possibleSingleton = parts[currentIndex];
353         unsigned singletonLength = possibleSingleton.length();
354         bool isValidSingleton = (singletonLength == 1 && possibleSingleton != "x" && possibleSingleton != "X" && isASCIIAlphanumeric(possibleSingleton[0]));
355         if (!isValidSingleton)
356             break;
357
358         // Cannot include duplicate singleton (case insensitive).
359         String singleton = possibleSingleton.convertToASCIILowercase();
360         if (!subtags.add(singleton).isNewEntry)
361             return String();
362
363         ++currentIndex;
364         int numExtParts = 0;
365         StringBuilder extension;
366         extension.append(singleton);
367         while (currentIndex < numParts) {
368             const String& extPart = parts[currentIndex];
369             unsigned extPartLength = extPart.length();
370
371             bool isValid = (extPartLength >= 2 && extPartLength <= 8 && extPart.isAllSpecialCharacters<isASCIIAlphanumeric>());
372             if (!isValid)
373                 break;
374
375             ++currentIndex;
376             ++numExtParts;
377             extension.append('-');
378             extension.append(extPart.convertToASCIILowercase());
379         }
380
381         // Requires at least one production.
382         if (!numExtParts)
383             return String();
384
385         extensions.append(extension.toString());
386     }
387
388     // Add extensions to canonical sorted by singleton.
389     std::sort(
390         extensions.begin(),
391         extensions.end(),
392         [] (const String& a, const String& b) -> bool {
393             return a[0] < b[0];
394         }
395     );
396     size_t numExtenstions = extensions.size();
397     for (size_t i = 0; i < numExtenstions; ++i) {
398         canonical.append('-');
399         canonical.append(extensions[i]);
400     }
401
402     // Check for privateuse.
403     if (currentIndex < numParts) {
404         String privateuse = getPrivateUseLangTag(parts, currentIndex);
405         if (privateuse.isNull())
406             return String();
407         canonical.append('-');
408         canonical.append(privateuse);
409     }
410
411     // FIXME: Replace subtags with their preferred values.
412
413     return canonical.toString();
414 }
415
416 static String getGrandfatheredLangTag(const String& locale)
417 {
418     // grandfathered = irregular / regular
419     // FIXME: convert to a compile time hash table if this is causing performance issues.
420     HashMap<String, String> tagMap = {
421         // Irregular.
422         { ASCIILiteral("en-gb-oed"), ASCIILiteral("en-GB-oed") },
423         { ASCIILiteral("i-ami"), ASCIILiteral("ami") },
424         { ASCIILiteral("i-bnn"), ASCIILiteral("bnn") },
425         { ASCIILiteral("i-default"), ASCIILiteral("i-default") },
426         { ASCIILiteral("i-enochian"), ASCIILiteral("i-enochian") },
427         { ASCIILiteral("i-hak"), ASCIILiteral("hak") },
428         { ASCIILiteral("i-klingon"), ASCIILiteral("tlh") },
429         { ASCIILiteral("i-lux"), ASCIILiteral("lb") },
430         { ASCIILiteral("i-mingo"), ASCIILiteral("i-mingo") },
431         { ASCIILiteral("i-navajo"), ASCIILiteral("nv") },
432         { ASCIILiteral("i-pwn"), ASCIILiteral("pwn") },
433         { ASCIILiteral("i-tao"), ASCIILiteral("tao") },
434         { ASCIILiteral("i-tay"), ASCIILiteral("tay") },
435         { ASCIILiteral("i-tsu"), ASCIILiteral("tsu") },
436         { ASCIILiteral("sgn-be-fr"), ASCIILiteral("sfb") },
437         { ASCIILiteral("sgn-be-nl"), ASCIILiteral("vgt") },
438         { ASCIILiteral("sgn-ch-de"), ASCIILiteral("sgg") },
439         // Regular.
440         { ASCIILiteral("art-lojban"), ASCIILiteral("jbo") },
441         { ASCIILiteral("cel-gaulish"), ASCIILiteral("cel-gaulish") },
442         { ASCIILiteral("no-bok"), ASCIILiteral("nb") },
443         { ASCIILiteral("no-nyn"), ASCIILiteral("nn") },
444         { ASCIILiteral("zh-guoyu"), ASCIILiteral("cmn") },
445         { ASCIILiteral("zh-hakka"), ASCIILiteral("hak") },
446         { ASCIILiteral("zh-min"), ASCIILiteral("zh-min") },
447         { ASCIILiteral("zh-min-nan"), ASCIILiteral("nan") },
448         { ASCIILiteral("zh-xiang"), ASCIILiteral("hsn") }
449     };
450
451     return tagMap.get(locale.convertToASCIILowercase());
452 }
453
454 static String canonicalizeLanguageTag(const String& locale)
455 {
456     // 6.2.2 IsStructurallyValidLanguageTag (locale)
457     // 6.2.3 CanonicalizeLanguageTag (locale)
458     // These are done one after another in CanonicalizeLocaleList, so they are combined here to reduce duplication.
459     // https://www.rfc-editor.org/rfc/bcp/bcp47.txt
460
461     // Language-Tag = langtag / privateuse / grandfathered
462     String grandfather = getGrandfatheredLangTag(locale);
463     if (!grandfather.isNull())
464         return grandfather;
465
466     // FIXME: Replace redundant tags [RFC4647].
467
468     Vector<String> parts;
469     locale.split('-', true, parts);
470     if (!parts.isEmpty()) {
471         String langtag = getCanonicalLangTag(parts);
472         if (!langtag.isNull())
473             return langtag;
474
475         String privateuse = getPrivateUseLangTag(parts, 0);
476         if (!privateuse.isNull())
477             return privateuse;
478     }
479
480     return String();
481 }
482
483 Vector<String> canonicalizeLocaleList(ExecState* exec, JSValue locales)
484 {
485     // 9.2.1 CanonicalizeLocaleList (locales)
486     VM& vm = exec->vm();
487     JSGlobalObject* globalObject = exec->callee()->globalObject();
488     Vector<String> seen;
489
490     // 1. If locales is undefined, then a. Return a new empty List.
491     if (locales.isUndefined())
492         return seen;
493
494     // 2. Let seen be an empty List.
495     // Done before to also return in step 1, if needed.
496
497     // 3. If Type(locales) is String, then
498     JSObject* localesObject;
499     if (locales.isString()) {
500         //  a. Let aLocales be CreateArrayFromList(«locales»).
501         JSArray* localesArray = JSArray::tryCreateUninitialized(vm, globalObject->arrayStructureForIndexingTypeDuringAllocation(ArrayWithContiguous), 1);
502         localesArray->initializeIndex(vm, 0, locales);
503         // 4. Let O be ToObject(aLocales).
504         localesObject = localesArray;
505     } else {
506         // 4. Let O be ToObject(aLocales).
507         localesObject = locales.toObject(exec);
508     }
509
510     // 5. ReturnIfAbrupt(O).
511     if (exec->hadException())
512         return Vector<String>();
513
514     // 6. Let len be ToLength(Get(O, "length")).
515     JSValue lengthProperty = localesObject->get(exec, vm.propertyNames->length);
516     if (exec->hadException())
517         return Vector<String>();
518
519     double length = lengthProperty.toLength(exec);
520     if (exec->hadException())
521         return Vector<String>();
522
523     // Keep track of locales that have been added to the list.
524     HashSet<String> seenSet;
525
526     // 7. Let k be 0.
527     // 8. Repeat, while k < len
528     for (double k = 0; k < length; ++k) {
529         // a. Let Pk be ToString(k).
530         // Not needed because hasProperty and get take an int for numeric key.
531
532         // b. Let kPresent be HasProperty(O, Pk).
533         bool kPresent = localesObject->hasProperty(exec, k);
534
535         // c. ReturnIfAbrupt(kPresent).
536         if (exec->hadException())
537             return Vector<String>();
538
539         // d. If kPresent is true, then
540         if (kPresent) {
541             // i. Let kValue be Get(O, Pk).
542             JSValue kValue = localesObject->get(exec, k);
543
544             // ii. ReturnIfAbrupt(kValue).
545             if (exec->hadException())
546                 return Vector<String>();
547
548             // iii. If Type(kValue) is not String or Object, throw a TypeError exception.
549             if (!kValue.isString() && !kValue.isObject()) {
550                 throwTypeError(exec, ASCIILiteral("locale value must be a string or object"));
551                 return Vector<String>();
552             }
553
554             // iv. Let tag be ToString(kValue).
555             JSString* tag = kValue.toString(exec);
556
557             // v. ReturnIfAbrupt(tag).
558             if (exec->hadException())
559                 return Vector<String>();
560
561             // vi. If IsStructurallyValidLanguageTag(tag) is false, throw a RangeError exception.
562             // vii. Let canonicalizedTag be CanonicalizeLanguageTag(tag).
563             String canonicalizedTag = canonicalizeLanguageTag(tag->value(exec));
564             if (canonicalizedTag.isNull()) {
565                 exec->vm().throwException(exec, createRangeError(exec, String::format("invalid language tag: %s", tag->value(exec).utf8().data())));
566                 return Vector<String>();
567             }
568
569             // viii. If canonicalizedTag is not an element of seen, append canonicalizedTag as the last element of seen.
570             if (seenSet.add(canonicalizedTag).isNewEntry)
571                 seen.append(canonicalizedTag);
572         }
573         // e. Increase k by 1.
574     }
575
576     return seen;
577 }
578
579 static String bestAvailableLocale(const HashSet<String>& availableLocales, const String& locale)
580 {
581     // 9.2.2 BestAvailableLocale (availableLocales, locale)
582     // 1. Let candidate be locale.
583     String candidate = locale;
584
585     // 2. Repeat
586     while (!candidate.isEmpty()) {
587         // a. If availableLocales contains an element equal to candidate, then return candidate.
588         if (availableLocales.contains(candidate))
589             return candidate;
590
591         // b. Let pos be the character index of the last occurrence of "-" (U+002D) within candidate. If that character does not occur, return undefined.
592         size_t pos = candidate.reverseFind('-');
593         if (pos == notFound)
594             return String();
595
596         // c. If pos ≥ 2 and the character "-" occurs at index pos-2 of candidate, then decrease pos by 2.
597         if (pos >= 2 && candidate[pos - 2] == '-')
598             pos -= 2;
599
600         // d. Let candidate be the substring of candidate from position 0, inclusive, to position pos, exclusive.
601         candidate = candidate.substring(0, pos);
602     }
603
604     return String();
605 }
606
607 static String removeUnicodeLocaleExtension(const String& locale)
608 {
609     Vector<String> parts;
610     locale.split('-', parts);
611     StringBuilder builder;
612     size_t partsSize = parts.size();
613     if (partsSize > 0)
614         builder.append(parts[0]);
615     for (size_t p = 1; p < partsSize; ++p) {
616         if (parts[p] == "u") {
617             // Skip the u- and anything that follows until another singleton.
618             // While the next part is part of the unicode extension, skip it.
619             while (p + 1 < partsSize && parts[p + 1].length() > 1)
620                 ++p;
621         } else {
622             builder.append('-');
623             builder.append(parts[p]);
624         }
625     }
626     return builder.toString();
627 }
628
629 static MatcherResult lookupMatcher(const HashSet<String>& availableLocales, const Vector<String>& requestedLocales)
630 {
631     // 9.2.3 LookupMatcher (availableLocales, requestedLocales) (ECMA-402 2.0)
632     String locale;
633     String noExtensionsLocale;
634     String availableLocale;
635     for (size_t i = 0; i < requestedLocales.size() && availableLocale.isNull(); ++i) {
636         locale = requestedLocales[i];
637         noExtensionsLocale = removeUnicodeLocaleExtension(locale);
638         availableLocale = bestAvailableLocale(availableLocales, noExtensionsLocale);
639     }
640
641     MatcherResult result;
642     if (!availableLocale.isNull()) {
643         result.locale = availableLocale;
644         if (locale != noExtensionsLocale) {
645             // i. Let extension be the String value consisting of the first substring of locale that is a Unicode locale extension sequence.
646             // ii. Let extensionIndex be the character position of the initial "-" extension sequence within locale.
647             size_t extensionIndex = locale.find("-u-");
648             RELEASE_ASSERT(extensionIndex != notFound);
649
650             size_t extensionLength = locale.length() - extensionIndex;
651             size_t end = extensionIndex + 3;
652             while (end < locale.length()) {
653                 end = locale.find('-', end);
654                 if (end == notFound)
655                     break;
656                 if (end + 2 < locale.length() && locale[end + 2] == '-') {
657                     extensionLength = end - extensionIndex;
658                     break;
659                 }
660                 end++;
661             }
662             result.extension = locale.substring(extensionIndex, extensionLength);
663             result.extensionIndex = extensionIndex;
664         }
665     } else
666         result.locale = defaultLocale();
667     return result;
668 }
669
670 static MatcherResult bestFitMatcher(const HashSet<String>& availableLocales, const Vector<String>& requestedLocales)
671 {
672     // 9.2.4 BestFitMatcher (availableLocales, requestedLocales) (ECMA-402 2.0)
673     // FIXME: Implement something better than lookup.
674     return lookupMatcher(availableLocales, requestedLocales);
675 }
676
677 HashMap<String, String> resolveLocale(const HashSet<String>& availableLocales, const Vector<String>& requestedLocales, const HashMap<String, String>& options, const Vector<String>& relevantExtensionKeys, Vector<String> (*localeData)(const String&, const String&))
678 {
679     // 9.2.5 ResolveLocale (availableLocales, requestedLocales, options, relevantExtensionKeys, localeData) (ECMA-402 2.0)
680     // 1. Let matcher be the value of options.[[localeMatcher]].
681     const String& matcher = options.get(ASCIILiteral("localeMatcher"));
682
683     // 2. If matcher is "lookup", then
684     MatcherResult (*matcherOperation)(const HashSet<String>&, const Vector<String>&);
685     if (matcher == "lookup") {
686         // a. Let MatcherOperation be the abstract operation LookupMatcher.
687         matcherOperation = lookupMatcher;
688     } else { // 3. Else
689         // a. Let MatcherOperation be the abstract operation BestFitMatcher.
690         matcherOperation = bestFitMatcher;
691     }
692
693     // 4. Let r be MatcherOperation(availableLocales, requestedLocales).
694     MatcherResult matcherResult = matcherOperation(availableLocales, requestedLocales);
695
696     // 5. Let foundLocale be the value of r.[[locale]].
697     String foundLocale = matcherResult.locale;
698
699     // 6. If r has an [[extension]] field, then
700     Vector<String> extensionSubtags;
701     if (!matcherResult.extension.isNull()) {
702         // a. Let extension be the value of r.[[extension]].
703         // b. Let extensionIndex be the value of r.[[extensionIndex]].
704         // c. Let extensionSubtags be Call(%StringProto_split%, extension, «"-"») .
705         // d. Let extensionSubtagsLength be Get(CreateArrayFromList(extensionSubtags), "length").
706         matcherResult.extension.split('-', extensionSubtags);
707     }
708
709     // 7. Let result be a new Record.
710     HashMap<String, String> result;
711
712     // 8. Set result.[[dataLocale]] to foundLocale.
713     result.set(ASCIILiteral("dataLocale"), foundLocale);
714
715     // 9. Let supportedExtension be "-u".
716     String supportedExtension = ASCIILiteral("-u");
717
718     // 10. Let k be 0.
719     // 11. Let rExtensionKeys be ToObject(CreateArrayFromList(relevantExtensionKeys)).
720     // 12. ReturnIfAbrupt(rExtensionKeys).
721     // 13. Let len be ToLength(Get(rExtensionKeys, "length")).
722     // 14. Repeat while k < len
723     for (size_t k = 0; k < relevantExtensionKeys.size(); ++k) {
724         // a. Let key be Get(rExtensionKeys, ToString(k)).
725         // b. ReturnIfAbrupt(key).
726         const String& key = relevantExtensionKeys[k];
727
728         // c. Let foundLocaleData be Get(localeData, foundLocale).
729         // d. ReturnIfAbrupt(foundLocaleData).
730         // e. Let keyLocaleData be ToObject(Get(foundLocaleData, key)).
731         // f. ReturnIfAbrupt(keyLocaleData).
732         Vector<String> keyLocaleData = localeData(foundLocale, key);
733
734         // g. Let value be ToString(Get(keyLocaleData, "0")).
735         // h. ReturnIfAbrupt(value).
736         ASSERT(!keyLocaleData.isEmpty());
737         String value = keyLocaleData[0];
738
739         // i. Let supportedExtensionAddition be "".
740         String supportedExtensionAddition;
741
742         // j. If extensionSubtags is not undefined, then
743         if (!extensionSubtags.isEmpty()) {
744             // i. Let keyPos be Call(%ArrayProto_indexOf%, extensionSubtags, «key») .
745             size_t keyPos = extensionSubtags.find(key);
746             // ii. If keyPos != -1, then
747             if (keyPos != notFound) {
748                 // 1. If keyPos + 1 < extensionSubtagsLength and the length of the result of Get(extensionSubtags, ToString(keyPos +1)) is greater than 2, then
749                 if (keyPos + 1 < extensionSubtags.size() && extensionSubtags[keyPos + 1].length() > 2) {
750                     const String& requestedValue = extensionSubtags[keyPos + 1];
751                     if (keyLocaleData.contains(requestedValue)) {
752                         value = requestedValue;
753                         supportedExtensionAddition = "-" + key + '-' + value;
754                     }
755                 } else if (keyLocaleData.contains(static_cast<String>(ASCIILiteral("true")))) {
756                     // 2. Else, if the result of Call(%StringProto_includes%, keyLocaleData, «"true"») is true, then
757                     value = ASCIILiteral("true");
758                 }
759             }
760         }
761
762         // k. If options has a field [[<key>]], then
763         HashMap<String, String>::const_iterator iterator = options.find(key);
764         if (iterator != options.end()) {
765             // i. Let optionsValue be the value of ToString(options.[[<key>]]).
766             // ii. ReturnIfAbrupt(optionsValue).
767             const String& optionsValue = iterator->value;
768             // iii. If the result of Call(%StringProto_includes%, keyLocaleData, «optionsValue») is true, then
769             if (!optionsValue.isNull() && keyLocaleData.contains(optionsValue)) {
770                 // 1. If optionsValue is not equal to value, then
771                 if (optionsValue != value) {
772                     value = optionsValue;
773                     supportedExtensionAddition = String();
774                 }
775             }
776         }
777
778         // l. Set result.[[<key>]] to value.
779         result.set(key, value);
780
781         // m. Append supportedExtensionAddition to supportedExtension.
782         supportedExtension.append(supportedExtensionAddition);
783
784         // n. Increase k by 1.
785     }
786
787     // 15. If the number of elements in supportedExtension is greater than 2, then
788     if (supportedExtension.length() > 2) {
789         // a. Let preExtension be the substring of foundLocale from position 0, inclusive, to position extensionIndex, exclusive.
790         // b. Let postExtension be the substring of foundLocale from position extensionIndex to the end of the string.
791         // c. Let foundLocale be the concatenation of preExtension, supportedExtension, and postExtension.
792         String preExtension = foundLocale.substring(0, matcherResult.extensionIndex);
793         String postExtension = foundLocale.substring(matcherResult.extensionIndex);
794         foundLocale = preExtension + supportedExtension + postExtension;
795     }
796
797     // 16. Set result.[[locale]] to foundLocale.
798     result.set(ASCIILiteral("locale"), foundLocale);
799
800     // 17. Return result.
801     return result;
802 }
803
804 static JSArray* lookupSupportedLocales(ExecState* exec, const HashSet<String>& availableLocales, const Vector<String>& requestedLocales)
805 {
806     // 9.2.6 LookupSupportedLocales (availableLocales, requestedLocales)
807
808     // 1. Let rLocales be CreateArrayFromList(requestedLocales).
809     // Already an array.
810
811     // 2. Let len be ToLength(Get(rLocales, "length")).
812     size_t len = requestedLocales.size();
813
814     // 3. Let subset be an empty List.
815     VM& vm = exec->vm();
816     JSGlobalObject* globalObject = exec->callee()->globalObject();
817     JSArray* subset = JSArray::tryCreateUninitialized(vm, globalObject->arrayStructureForIndexingTypeDuringAllocation(ArrayWithUndecided), 0);
818     if (!subset) {
819         throwOutOfMemoryError(exec);
820         return nullptr;
821     }
822
823     // 4. Let k be 0.
824     // 5. Repeat while k < len
825     for (size_t k = 0; k < len; ++k) {
826         // a. Let Pk be ToString(k).
827         // b. Let locale be Get(rLocales, Pk).
828         // c. ReturnIfAbrupt(locale).
829         const String& locale = requestedLocales[k];
830
831         // d. Let noExtensionsLocale be the String value that is locale with all Unicode locale extension sequences removed.
832         String noExtensionsLocale = removeUnicodeLocaleExtension(locale);
833
834         // e. Let availableLocale be BestAvailableLocale(availableLocales, noExtensionsLocale).
835         String availableLocale = bestAvailableLocale(availableLocales, noExtensionsLocale);
836
837         // f. If availableLocale is not undefined, then append locale to the end of subset.
838         if (!availableLocale.isNull())
839             subset->push(exec, jsString(exec, locale));
840
841         // g. Increment k by 1.
842     }
843
844     // 6. Return subset.
845     return subset;
846 }
847
848 static JSArray* bestFitSupportedLocales(ExecState* exec, const HashSet<String>& availableLocales, const Vector<String>& requestedLocales)
849 {
850     // 9.2.7 BestFitSupportedLocales (availableLocales, requestedLocales)
851     // FIXME: Implement something better than lookup.
852     return lookupSupportedLocales(exec, availableLocales, requestedLocales);
853 }
854
855 JSValue supportedLocales(ExecState* exec, const HashSet<String>& availableLocales, const Vector<String>& requestedLocales, JSValue options)
856 {
857     // 9.2.8 SupportedLocales (availableLocales, requestedLocales, options)
858     VM& vm = exec->vm();
859     String matcher;
860
861     // 1. If options is not undefined, then
862     if (!options.isUndefined()) {
863         // a. Let matcher be GetOption(options, "localeMatcher", "string", « "lookup", "best fit" », "best fit").
864         const HashSet<String> matchers({ ASCIILiteral("lookup"), ASCIILiteral("best fit") });
865         matcher = getIntlStringOption(exec, options, vm.propertyNames->localeMatcher, matchers, "localeMatcher must be either \"lookup\" or \"best fit\"", ASCIILiteral("best fit"));
866         // b. ReturnIfAbrupt(matcher).
867         if (exec->hadException())
868             return jsUndefined();
869     } else {
870         // 2. Else, let matcher be "best fit".
871         matcher = ASCIILiteral("best fit");
872     }
873
874     JSArray* supportedLocales;
875     // 3. If matcher is "best fit",
876     if (matcher == "best fit") {
877         // a. Let MatcherOperation be the abstract operation BestFitSupportedLocales.
878         // 5. Let supportedLocales be MatcherOperation(availableLocales, requestedLocales).
879         supportedLocales = bestFitSupportedLocales(exec, availableLocales, requestedLocales);
880     } else {
881         // 4. Else
882         // a. Let MatcherOperation be the abstract operation LookupSupportedLocales.
883         // 5. Let supportedLocales be MatcherOperation(availableLocales, requestedLocales).
884         supportedLocales = lookupSupportedLocales(exec, availableLocales, requestedLocales);
885     }
886
887     if (exec->hadException())
888         return jsUndefined();
889
890     // 6. Let subset be CreateArrayFromList(supportedLocales).
891     // Already an array.
892
893     // 7. Let keys be subset.[[OwnPropertyKeys]]().
894     PropertyNameArray keys(exec, PropertyNameMode::Strings);
895     supportedLocales->getOwnPropertyNames(supportedLocales, exec, keys, EnumerationMode());
896
897     PropertyDescriptor desc;
898     desc.setConfigurable(false);
899     desc.setWritable(false);
900
901     // 8. Repeat for each element P of keys in List order,
902     size_t len = keys.size();
903     for (size_t i = 0; i < len; ++i) {
904         // a. Let desc be PropertyDescriptor { [[Configurable]]: false, [[Writable]]: false }.
905         // Created above for reuse.
906
907         // b. Let status be DefinePropertyOrThrow(subset, P, desc).
908         supportedLocales->defineOwnProperty(supportedLocales, exec, keys[i], desc, true);
909
910         // c. Assert: status is not abrupt completion.
911         if (exec->hadException())
912             return jsUndefined();
913     }
914
915     // 9. Return subset.
916     return supportedLocales;
917 }
918
919 } // namespace JSC
920
921 #endif // ENABLE(INTL)