⚠ Archived content — this site is no longer maintained.   Current WebKit documentation is at docs.webkit.org.

Changeset 276225 in webkit


Ignore:
Timestamp:
Apr 18, 2021, 12:43:33 AM (5 years ago)
Author:
ysuzuki@apple.com
Message:

Use binary-search in LocaleToScriptMapping
​https://bugs.webkit.org/show_bug.cgi?id=224727

Reviewed by Darin Adler.

This patch removes HashMaps in LocaleToScriptMapping, and binary-search onto the constant data arrays.
These maps are not frequently used. Keys of the maps can be encoded into uint32_t or uint64_t so that
comparison becomes super cheap and we can initialize this array at compile-time.

We introduce ScriptName(uint32_t) and LocaleName(uint64_t) instead of String. And ues it and generate
sorted constant data array for mappings. We use binary-search to look entry up. Since # of entries are
not huge (~200), comparisons are extremely cheap (uint32_t / uint64_t comparison), and this is not a
hot code, we can just use binary-search here and eliminate HashMaps' memory allocation.

  • platform/text/LocaleToScriptMapping.cpp:

(WebCore::PackedASCIILowerCodes::PackedASCIILowerCodes):
(WebCore::PackedASCIILowerCodes::parse):
(WebCore::PackedASCIILowerCodes::operator==):
(WebCore::PackedASCIILowerCodes::operator!=):
(WebCore::PackedASCIILowerCodes::operator<):
(WebCore::PackedASCIILowerCodes::operator<=):
(WebCore::PackedASCIILowerCodes::operator>):
(WebCore::PackedASCIILowerCodes::operator>=):
(WebCore::PackedASCIILowerCodes::value const):
(WebCore::scriptNameToCode):
(WebCore::localeToScriptCodeForFontSelection):

Location:
trunk/Source/WebCore
Files:
2 edited

Legend:

Unmodified
Added
Removed

  • trunk/Source/WebCore/ChangeLog

    r276220 r276225  
     12021-04-17  Yusuke Suzuki  <ysuzuki@apple.com>
     2
     3        Use binary-search in LocaleToScriptMapping
     4        https://bugs.webkit.org/show_bug.cgi?id=224727
     5
     6        Reviewed by Darin Adler.
     7
     8        This patch removes HashMaps in LocaleToScriptMapping, and binary-search onto the constant data arrays.
     9        These maps are not frequently used. Keys of the maps can be encoded into uint32_t or uint64_t so that
     10        comparison becomes super cheap and we can initialize this array at compile-time.
     11
     12        We introduce ScriptName(uint32_t) and LocaleName(uint64_t) instead of String. And ues it and generate
     13        sorted constant data array for mappings. We use binary-search to look entry up. Since # of entries are
     14        not huge (~200), comparisons are extremely cheap (uint32_t / uint64_t comparison), and this is not a
     15        hot code, we can just use binary-search here and eliminate HashMaps' memory allocation.
     16
     17        * platform/text/LocaleToScriptMapping.cpp:
     18        (WebCore::PackedASCIILowerCodes::PackedASCIILowerCodes):
     19        (WebCore::PackedASCIILowerCodes::parse):
     20        (WebCore::PackedASCIILowerCodes::operator==):
     21        (WebCore::PackedASCIILowerCodes::operator!=):
     22        (WebCore::PackedASCIILowerCodes::operator<):
     23        (WebCore::PackedASCIILowerCodes::operator<=):
     24        (WebCore::PackedASCIILowerCodes::operator>):
     25        (WebCore::PackedASCIILowerCodes::operator>=):
     26        (WebCore::PackedASCIILowerCodes::value const):
     27        (WebCore::scriptNameToCode):
     28        (WebCore::localeToScriptCodeForFontSelection):
     29
    1302021-04-17  Wenson Hsieh  <wenson_hsieh@apple.com>
    231

  • trunk/Source/WebCore/platform/text/LocaleToScriptMapping.cpp

    r267126 r276225  
    11/*
    22 * Copyright (C) 2011 Google Inc. All rights reserved.
     3 * Copyright (C) 2021 Apple Inc. All rights reserved.
    34 *
    45 * Redistribution and use in source and binary forms, with or without
    … …  
    3839namespace WebCore {
    3940
     41template<typename StorageInteger>
     42class PackedASCIILowerCodes {
     43public:
     44    static_assert(std::is_unsigned_v<StorageInteger>);
     45
     46    template<unsigned characterCountPlusOne>
     47    constexpr PackedASCIILowerCodes(const char (&string)[characterCountPlusOne])
     48    {
     49        constexpr unsigned length = characterCountPlusOne - 1;
     50        ASSERT_UNDER_CONSTEXPR_CONTEXT(length <= sizeof(StorageInteger));
     51        ASSERT_UNDER_CONSTEXPR_CONTEXT(!string[length]);
     52        StorageInteger result = 0;
     53        for (unsigned index = 0; index < length; ++index) {
     54            uint8_t code = static_cast<uint8_t>(string[index]);
     55            result |= static_cast<StorageInteger>(code) << ((sizeof(StorageInteger) - index - 1) * 8);
     56        }
     57        m_value = result;
     58    }
     59
     60    static Optional<PackedASCIILowerCodes> parse(StringView string)
     61    {
     62        if (string.length() > sizeof(StorageInteger))
     63            return WTF::nullopt;
     64        StorageInteger result = 0;
     65        for (unsigned index = 0; index < string.length(); ++index) {
     66            UChar code = string[index];
     67            if (!isASCII(code))
     68                return WTF::nullopt;
     69            result |= static_cast<StorageInteger>(toASCIILower(code)) << ((sizeof(StorageInteger) - index - 1) * 8);
     70        }
     71        return PackedASCIILowerCodes(result);
     72    }
     73
     74    friend constexpr bool operator==(PackedASCIILowerCodes lhs, PackedASCIILowerCodes rhs)
     75    {
     76        return lhs.m_value == rhs.m_value;
     77    }
     78
     79    friend constexpr bool operator!=(PackedASCIILowerCodes lhs, PackedASCIILowerCodes rhs)
     80    {
     81        return lhs.m_value != rhs.m_value;
     82    }
     83
     84    friend constexpr bool operator<(PackedASCIILowerCodes lhs, PackedASCIILowerCodes rhs)
     85    {
     86        return lhs.m_value < rhs.m_value;
     87    }
     88
     89    friend constexpr bool operator<=(PackedASCIILowerCodes lhs, PackedASCIILowerCodes rhs)
     90    {
     91        return lhs.m_value <= rhs.m_value;
     92    }
     93
     94    friend constexpr bool operator>(PackedASCIILowerCodes lhs, PackedASCIILowerCodes rhs)
     95    {
     96        return lhs.m_value > rhs.m_value;
     97    }
     98
     99    friend constexpr bool operator>=(PackedASCIILowerCodes lhs, PackedASCIILowerCodes rhs)
     100    {
     101        return lhs.m_value >= rhs.m_value;
     102    }
     103
     104    constexpr StorageInteger value() const { return m_value; }
     105
     106private:
     107    explicit constexpr PackedASCIILowerCodes(StorageInteger value)
     108        : m_value(value)
     109    {
     110    }
     111
     112    StorageInteger m_value { 0 };
     113};
     114
     115using ScriptName = PackedASCIILowerCodes<uint32_t>;
    40116struct ScriptNameCode {
    41     ASCIILiteral name;
     117    ScriptName name;
    42118    UScriptCode code;
    43119};
    44120
    45 // This generally maps an ISO 15924 script code to its UScriptCode, but certain families of script codes are
    46 // treated as a single script for assigning a per-script font in Settings. For example, "hira" is mapped to
    47 // USCRIPT_KATAKANA_OR_HIRAGANA instead of USCRIPT_HIRAGANA, since we want all Japanese scripts to be rendered
    48 // using the same font setting.
    49 static const ScriptNameCode scriptNameCodeList[] = {
    50     { "zyyy"_s, USCRIPT_COMMON },
    51     { "qaai"_s, USCRIPT_INHERITED },
    52     { "arab"_s, USCRIPT_ARABIC },
    53     { "armn"_s, USCRIPT_ARMENIAN },
    54     { "beng"_s, USCRIPT_BENGALI },
    55     { "bopo"_s, USCRIPT_BOPOMOFO },
    56     { "cher"_s, USCRIPT_CHEROKEE },
    57     { "copt"_s, USCRIPT_COPTIC },
    58     { "cyrl"_s, USCRIPT_CYRILLIC },
    59     { "dsrt"_s, USCRIPT_DESERET },
    60     { "deva"_s, USCRIPT_DEVANAGARI },
    61     { "ethi"_s, USCRIPT_ETHIOPIC },
    62     { "geor"_s, USCRIPT_GEORGIAN },
    63     { "goth"_s, USCRIPT_GOTHIC },
    64     { "grek"_s, USCRIPT_GREEK },
    65     { "gujr"_s, USCRIPT_GUJARATI },
    66     { "guru"_s, USCRIPT_GURMUKHI },
    67     { "hani"_s, USCRIPT_HAN },
    68     { "hang"_s, USCRIPT_HANGUL },
    69     { "hebr"_s, USCRIPT_HEBREW },
    70     { "hira"_s, USCRIPT_KATAKANA_OR_HIRAGANA },
    71     { "knda"_s, USCRIPT_KANNADA },
    72     { "kana"_s, USCRIPT_KATAKANA_OR_HIRAGANA },
    73     { "khmr"_s, USCRIPT_KHMER },
    74     { "laoo"_s, USCRIPT_LAO },
    75     { "latn"_s, USCRIPT_LATIN },
    76     { "mlym"_s, USCRIPT_MALAYALAM },
    77     { "mong"_s, USCRIPT_MONGOLIAN },
    78     { "mymr"_s, USCRIPT_MYANMAR },
    79     { "ogam"_s, USCRIPT_OGHAM },
    80     { "ital"_s, USCRIPT_OLD_ITALIC },
    81     { "orya"_s, USCRIPT_ORIYA },
    82     { "runr"_s, USCRIPT_RUNIC },
    83     { "sinh"_s, USCRIPT_SINHALA },
    84     { "syrc"_s, USCRIPT_SYRIAC },
    85     { "taml"_s, USCRIPT_TAMIL },
    86     { "telu"_s, USCRIPT_TELUGU },
    87     { "thaa"_s, USCRIPT_THAANA },
    88     { "thai"_s, USCRIPT_THAI },
    89     { "tibt"_s, USCRIPT_TIBETAN },
    90     { "cans"_s, USCRIPT_CANADIAN_ABORIGINAL },
    91     { "yiii"_s, USCRIPT_YI },
    92     { "tglg"_s, USCRIPT_TAGALOG },
    93     { "hano"_s, USCRIPT_HANUNOO },
    94     { "buhd"_s, USCRIPT_BUHID },
    95     { "tagb"_s, USCRIPT_TAGBANWA },
    96     { "brai"_s, USCRIPT_BRAILLE },
    97     { "cprt"_s, USCRIPT_CYPRIOT },
    98     { "limb"_s, USCRIPT_LIMBU },
    99     { "linb"_s, USCRIPT_LINEAR_B },
    100     { "osma"_s, USCRIPT_OSMANYA },
    101     { "shaw"_s, USCRIPT_SHAVIAN },
    102     { "tale"_s, USCRIPT_TAI_LE },
    103     { "ugar"_s, USCRIPT_UGARITIC },
    104     { "hrkt"_s, USCRIPT_KATAKANA_OR_HIRAGANA },
    105     { "bugi"_s, USCRIPT_BUGINESE },
    106     { "glag"_s, USCRIPT_GLAGOLITIC },
    107     { "khar"_s, USCRIPT_KHAROSHTHI },
    108     { "sylo"_s, USCRIPT_SYLOTI_NAGRI },
    109     { "talu"_s, USCRIPT_NEW_TAI_LUE },
    110     { "tfng"_s, USCRIPT_TIFINAGH },
    111     { "xpeo"_s, USCRIPT_OLD_PERSIAN },
    112     { "bali"_s, USCRIPT_BALINESE },
    113     { "batk"_s, USCRIPT_BATAK },
    114     { "blis"_s, USCRIPT_BLISSYMBOLS },
    115     { "brah"_s, USCRIPT_BRAHMI },
    116     { "cham"_s, USCRIPT_CHAM },
    117     { "cirt"_s, USCRIPT_CIRTH },
    118     { "cyrs"_s, USCRIPT_OLD_CHURCH_SLAVONIC_CYRILLIC },
    119     { "egyd"_s, USCRIPT_DEMOTIC_EGYPTIAN },
    120     { "egyh"_s, USCRIPT_HIERATIC_EGYPTIAN },
    121     { "egyp"_s, USCRIPT_EGYPTIAN_HIEROGLYPHS },
    122     { "geok"_s, USCRIPT_KHUTSURI },
    123     { "hans"_s, USCRIPT_SIMPLIFIED_HAN },
    124     { "hant"_s, USCRIPT_TRADITIONAL_HAN },
    125     { "hmng"_s, USCRIPT_PAHAWH_HMONG },
    126     { "hung"_s, USCRIPT_OLD_HUNGARIAN },
    127     { "inds"_s, USCRIPT_HARAPPAN_INDUS },
    128     { "java"_s, USCRIPT_JAVANESE },
    129     { "kali"_s, USCRIPT_KAYAH_LI },
    130     { "latf"_s, USCRIPT_LATIN_FRAKTUR },
    131     { "latg"_s, USCRIPT_LATIN_GAELIC },
    132     { "lepc"_s, USCRIPT_LEPCHA },
    133     { "lina"_s, USCRIPT_LINEAR_A },
    134     { "mand"_s, USCRIPT_MANDAEAN },
    135     { "maya"_s, USCRIPT_MAYAN_HIEROGLYPHS },
    136     { "mero"_s, USCRIPT_MEROITIC },
    137     { "nkoo"_s, USCRIPT_NKO },
    138     { "orkh"_s, USCRIPT_ORKHON },
    139     { "perm"_s, USCRIPT_OLD_PERMIC },
    140     { "phag"_s, USCRIPT_PHAGS_PA },
    141     { "phnx"_s, USCRIPT_PHOENICIAN },
    142     { "plrd"_s, USCRIPT_PHONETIC_POLLARD },
    143     { "roro"_s, USCRIPT_RONGORONGO },
    144     { "sara"_s, USCRIPT_SARATI },
    145     { "syre"_s, USCRIPT_ESTRANGELO_SYRIAC },
    146     { "syrj"_s, USCRIPT_WESTERN_SYRIAC },
    147     { "syrn"_s, USCRIPT_EASTERN_SYRIAC },
    148     { "teng"_s, USCRIPT_TENGWAR },
    149     { "vaii"_s, USCRIPT_VAI },
    150     { "visp"_s, USCRIPT_VISIBLE_SPEECH },
    151     { "xsux"_s, USCRIPT_CUNEIFORM },
    152     { "jpan"_s, USCRIPT_KATAKANA_OR_HIRAGANA },
    153     { "kore"_s, USCRIPT_HANGUL },
    154     { "zxxx"_s, USCRIPT_UNWRITTEN_LANGUAGES },
    155     { "zzzz"_s, USCRIPT_UNKNOWN }
    156 };
    157 
    158 struct ScriptNameCodeMapHashTraits : public HashTraits<String> {
    159     static const int minimumTableSize = WTF::HashTableCapacityForSize<WTF_ARRAY_LENGTH(scriptNameCodeList)>::value;
    160 };
    161 
    162121UScriptCode scriptNameToCode(const String& scriptName)
    163122{
    164     static const auto scriptNameCodeMap = makeNeverDestroyed([] {
    165         HashMap<String, UScriptCode, ASCIICaseInsensitiveHash, ScriptNameCodeMapHashTraits> map;
    166         for (auto& nameAndCode : scriptNameCodeList)
    167             map.add(nameAndCode.name, nameAndCode.code);
    168         return map;
    169     }());
    170 
    171     auto it = scriptNameCodeMap.get().find(scriptName);
    172     if (it != scriptNameCodeMap.get().end())
    173         return it->value;
     123    // This generally maps an ISO 15924 script code to its UScriptCode, but certain families of script codes are
     124    // treated as a single script for assigning a per-script font in Settings. For example, "hira" is mapped to
     125    // USCRIPT_KATAKANA_OR_HIRAGANA instead of USCRIPT_HIRAGANA, since we want all Japanese scripts to be rendered
     126    // using the same font setting.
     127    static constexpr ScriptNameCode scriptNameCodeList[] = {
     128        { "arab", USCRIPT_ARABIC },
     129        { "armn", USCRIPT_ARMENIAN },
     130        { "bali", USCRIPT_BALINESE },
     131        { "batk", USCRIPT_BATAK },
     132        { "beng", USCRIPT_BENGALI },
     133        { "blis", USCRIPT_BLISSYMBOLS },
     134        { "bopo", USCRIPT_BOPOMOFO },
     135        { "brah", USCRIPT_BRAHMI },
     136        { "brai", USCRIPT_BRAILLE },
     137        { "bugi", USCRIPT_BUGINESE },
     138        { "buhd", USCRIPT_BUHID },
     139        { "cans", USCRIPT_CANADIAN_ABORIGINAL },
     140        { "cham", USCRIPT_CHAM },
     141        { "cher", USCRIPT_CHEROKEE },
     142        { "cirt", USCRIPT_CIRTH },
     143        { "copt", USCRIPT_COPTIC },
     144        { "cprt", USCRIPT_CYPRIOT },
     145        { "cyrl", USCRIPT_CYRILLIC },
     146        { "cyrs", USCRIPT_OLD_CHURCH_SLAVONIC_CYRILLIC },
     147        { "deva", USCRIPT_DEVANAGARI },
     148        { "dsrt", USCRIPT_DESERET },
     149        { "egyd", USCRIPT_DEMOTIC_EGYPTIAN },
     150        { "egyh", USCRIPT_HIERATIC_EGYPTIAN },
     151        { "egyp", USCRIPT_EGYPTIAN_HIEROGLYPHS },
     152        { "ethi", USCRIPT_ETHIOPIC },
     153        { "geok", USCRIPT_KHUTSURI },
     154        { "geor", USCRIPT_GEORGIAN },
     155        { "glag", USCRIPT_GLAGOLITIC },
     156        { "goth", USCRIPT_GOTHIC },
     157        { "grek", USCRIPT_GREEK },
     158        { "gujr", USCRIPT_GUJARATI },
     159        { "guru", USCRIPT_GURMUKHI },
     160        { "hang", USCRIPT_HANGUL },
     161        { "hani", USCRIPT_HAN },
     162        { "hano", USCRIPT_HANUNOO },
     163        { "hans", USCRIPT_SIMPLIFIED_HAN },
     164        { "hant", USCRIPT_TRADITIONAL_HAN },
     165        { "hebr", USCRIPT_HEBREW },
     166        { "hira", USCRIPT_KATAKANA_OR_HIRAGANA },
     167        { "hmng", USCRIPT_PAHAWH_HMONG },
     168        { "hrkt", USCRIPT_KATAKANA_OR_HIRAGANA },
     169        { "hung", USCRIPT_OLD_HUNGARIAN },
     170        { "inds", USCRIPT_HARAPPAN_INDUS },
     171        { "ital", USCRIPT_OLD_ITALIC },
     172        { "java", USCRIPT_JAVANESE },
     173        { "jpan", USCRIPT_KATAKANA_OR_HIRAGANA },
     174        { "kali", USCRIPT_KAYAH_LI },
     175        { "kana", USCRIPT_KATAKANA_OR_HIRAGANA },
     176        { "khar", USCRIPT_KHAROSHTHI },
     177        { "khmr", USCRIPT_KHMER },
     178        { "knda", USCRIPT_KANNADA },
     179        { "kore", USCRIPT_HANGUL },
     180        { "laoo", USCRIPT_LAO },
     181        { "latf", USCRIPT_LATIN_FRAKTUR },
     182        { "latg", USCRIPT_LATIN_GAELIC },
     183        { "latn", USCRIPT_LATIN },
     184        { "lepc", USCRIPT_LEPCHA },
     185        { "limb", USCRIPT_LIMBU },
     186        { "lina", USCRIPT_LINEAR_A },
     187        { "linb", USCRIPT_LINEAR_B },
     188        { "mand", USCRIPT_MANDAEAN },
     189        { "maya", USCRIPT_MAYAN_HIEROGLYPHS },
     190        { "mero", USCRIPT_MEROITIC },
     191        { "mlym", USCRIPT_MALAYALAM },
     192        { "mong", USCRIPT_MONGOLIAN },
     193        { "mymr", USCRIPT_MYANMAR },
     194        { "nkoo", USCRIPT_NKO },
     195        { "ogam", USCRIPT_OGHAM },
     196        { "orkh", USCRIPT_ORKHON },
     197        { "orya", USCRIPT_ORIYA },
     198        { "osma", USCRIPT_OSMANYA },
     199        { "perm", USCRIPT_OLD_PERMIC },
     200        { "phag", USCRIPT_PHAGS_PA },
     201        { "phnx", USCRIPT_PHOENICIAN },
     202        { "plrd", USCRIPT_PHONETIC_POLLARD },
     203        { "qaai", USCRIPT_INHERITED },
     204        { "roro", USCRIPT_RONGORONGO },
     205        { "runr", USCRIPT_RUNIC },
     206        { "sara", USCRIPT_SARATI },
     207        { "shaw", USCRIPT_SHAVIAN },
     208        { "sinh", USCRIPT_SINHALA },
     209        { "sylo", USCRIPT_SYLOTI_NAGRI },
     210        { "syrc", USCRIPT_SYRIAC },
     211        { "syre", USCRIPT_ESTRANGELO_SYRIAC },
     212        { "syrj", USCRIPT_WESTERN_SYRIAC },
     213        { "syrn", USCRIPT_EASTERN_SYRIAC },
     214        { "tagb", USCRIPT_TAGBANWA },
     215        { "tale", USCRIPT_TAI_LE },
     216        { "talu", USCRIPT_NEW_TAI_LUE },
     217        { "taml", USCRIPT_TAMIL },
     218        { "telu", USCRIPT_TELUGU },
     219        { "teng", USCRIPT_TENGWAR },
     220        { "tfng", USCRIPT_TIFINAGH },
     221        { "tglg", USCRIPT_TAGALOG },
     222        { "thaa", USCRIPT_THAANA },
     223        { "thai", USCRIPT_THAI },
     224        { "tibt", USCRIPT_TIBETAN },
     225        { "ugar", USCRIPT_UGARITIC },
     226        { "vaii", USCRIPT_VAI },
     227        { "visp", USCRIPT_VISIBLE_SPEECH },
     228        { "xpeo", USCRIPT_OLD_PERSIAN },
     229        { "xsux", USCRIPT_CUNEIFORM },
     230        { "yiii", USCRIPT_YI },
     231        { "zxxx", USCRIPT_UNWRITTEN_LANGUAGES },
     232        { "zyyy", USCRIPT_COMMON },
     233        { "zzzz", USCRIPT_UNKNOWN },
     234    };
     235
     236    static_assert(ScriptName("arab").value() == 0x61726162U);
     237    static_assert(ScriptName("zzzz").value() == 0x7a7a7a7aU);
     238
     239    ASSERT(
     240        std::is_sorted(std::begin(scriptNameCodeList), std::end(scriptNameCodeList),
     241            [](const ScriptNameCode& a, const ScriptNameCode& b) {
     242                return a.name < b.name;
     243            }));
     244
     245    auto name = ScriptName::parse(scriptName);
     246    if (!name)
     247        return USCRIPT_INVALID_CODE;
     248
     249    auto* element = tryBinarySearch<ScriptNameCode>(scriptNameCodeList, std::size(scriptNameCodeList), name.value(),
     250        [](const ScriptNameCode* scriptNameCode) {
     251            return scriptNameCode->name;
     252        });
     253    if (element)
     254        return element->code;
    174255    return USCRIPT_INVALID_CODE;
    175256}
    176257
     258using LocaleName = PackedASCIILowerCodes<uint64_t>;
    177259struct LocaleScript {
    178     ASCIILiteral locale;
     260    LocaleName locale;
    179261    UScriptCode script;
    180262};
    181263
    182 static const LocaleScript localeScriptList[] = {
    183     { "aa"_s, USCRIPT_LATIN },
    184     { "ab"_s, USCRIPT_CYRILLIC },
    185     { "ady"_s, USCRIPT_CYRILLIC },
    186     { "af"_s, USCRIPT_LATIN },
    187     { "ak"_s, USCRIPT_LATIN },
    188     { "am"_s, USCRIPT_ETHIOPIC },
    189     { "ar"_s, USCRIPT_ARABIC },
    190     { "as"_s, USCRIPT_BENGALI },
    191     { "ast"_s, USCRIPT_LATIN },
    192     { "av"_s, USCRIPT_CYRILLIC },
    193     { "ay"_s, USCRIPT_LATIN },
    194     { "az"_s, USCRIPT_LATIN },
    195     { "ba"_s, USCRIPT_CYRILLIC },
    196     { "be"_s, USCRIPT_CYRILLIC },
    197     { "bg"_s, USCRIPT_CYRILLIC },
    198     { "bi"_s, USCRIPT_LATIN },
    199     { "bn"_s, USCRIPT_BENGALI },
    200     { "bo"_s, USCRIPT_TIBETAN },
    201     { "bs"_s, USCRIPT_LATIN },
    202     { "ca"_s, USCRIPT_LATIN },
    203     { "ce"_s, USCRIPT_CYRILLIC },
    204     { "ceb"_s, USCRIPT_LATIN },
    205     { "ch"_s, USCRIPT_LATIN },
    206     { "chk"_s, USCRIPT_LATIN },
    207     { "cs"_s, USCRIPT_LATIN },
    208     { "cy"_s, USCRIPT_LATIN },
    209     { "da"_s, USCRIPT_LATIN },
    210     { "de"_s, USCRIPT_LATIN },
    211     { "dv"_s, USCRIPT_THAANA },
    212     { "dz"_s, USCRIPT_TIBETAN },
    213     { "ee"_s, USCRIPT_LATIN },
    214     { "efi"_s, USCRIPT_LATIN },
    215     { "el"_s, USCRIPT_GREEK },
    216     { "en"_s, USCRIPT_LATIN },
    217     { "es"_s, USCRIPT_LATIN },
    218     { "et"_s, USCRIPT_LATIN },
    219     { "eu"_s, USCRIPT_LATIN },
    220     { "fa"_s, USCRIPT_ARABIC },
    221     { "fi"_s, USCRIPT_LATIN },
    222     { "fil"_s, USCRIPT_LATIN },
    223     { "fj"_s, USCRIPT_LATIN },
    224     { "fo"_s, USCRIPT_LATIN },
    225     { "fr"_s, USCRIPT_LATIN },
    226     { "fur"_s, USCRIPT_LATIN },
    227     { "fy"_s, USCRIPT_LATIN },
    228     { "ga"_s, USCRIPT_LATIN },
    229     { "gaa"_s, USCRIPT_LATIN },
    230     { "gd"_s, USCRIPT_LATIN },
    231     { "gil"_s, USCRIPT_LATIN },
    232     { "gl"_s, USCRIPT_LATIN },
    233     { "gn"_s, USCRIPT_LATIN },
    234     { "gsw"_s, USCRIPT_LATIN },
    235     { "gu"_s, USCRIPT_GUJARATI },
    236     { "ha"_s, USCRIPT_LATIN },
    237     { "haw"_s, USCRIPT_LATIN },
    238     { "he"_s, USCRIPT_HEBREW },
    239     { "hi"_s, USCRIPT_DEVANAGARI },
    240     { "hil"_s, USCRIPT_LATIN },
    241     { "ho"_s, USCRIPT_LATIN },
    242     { "hr"_s, USCRIPT_LATIN },
    243     { "ht"_s, USCRIPT_LATIN },
    244     { "hu"_s, USCRIPT_LATIN },
    245     { "hy"_s, USCRIPT_ARMENIAN },
    246     { "id"_s, USCRIPT_LATIN },
    247     { "ig"_s, USCRIPT_LATIN },
    248     { "ii"_s, USCRIPT_YI },
    249     { "ilo"_s, USCRIPT_LATIN },
    250     { "inh"_s, USCRIPT_CYRILLIC },
    251     { "is"_s, USCRIPT_LATIN },
    252     { "it"_s, USCRIPT_LATIN },
    253     { "iu"_s, USCRIPT_CANADIAN_ABORIGINAL },
    254     { "ja"_s, USCRIPT_KATAKANA_OR_HIRAGANA },
    255     { "jv"_s, USCRIPT_LATIN },
    256     { "ka"_s, USCRIPT_GEORGIAN },
    257     { "kaj"_s, USCRIPT_LATIN },
    258     { "kam"_s, USCRIPT_LATIN },
    259     { "kbd"_s, USCRIPT_CYRILLIC },
    260     { "kha"_s, USCRIPT_LATIN },
    261     { "kk"_s, USCRIPT_CYRILLIC },
    262     { "kl"_s, USCRIPT_LATIN },
    263     { "km"_s, USCRIPT_KHMER },
    264     { "kn"_s, USCRIPT_KANNADA },
    265     { "ko"_s, USCRIPT_HANGUL },
    266     { "kok"_s, USCRIPT_DEVANAGARI },
    267     { "kos"_s, USCRIPT_LATIN },
    268     { "kpe"_s, USCRIPT_LATIN },
    269     { "krc"_s, USCRIPT_CYRILLIC },
    270     { "ks"_s, USCRIPT_ARABIC },
    271     { "ku"_s, USCRIPT_ARABIC },
    272     { "kum"_s, USCRIPT_CYRILLIC },
    273     { "ky"_s, USCRIPT_CYRILLIC },
    274     { "la"_s, USCRIPT_LATIN },
    275     { "lah"_s, USCRIPT_ARABIC },
    276     { "lb"_s, USCRIPT_LATIN },
    277     { "lez"_s, USCRIPT_CYRILLIC },
    278     { "ln"_s, USCRIPT_LATIN },
    279     { "lo"_s, USCRIPT_LAO },
    280     { "lt"_s, USCRIPT_LATIN },
    281     { "lv"_s, USCRIPT_LATIN },
    282     { "mai"_s, USCRIPT_DEVANAGARI },
    283     { "mdf"_s, USCRIPT_CYRILLIC },
    284     { "mg"_s, USCRIPT_LATIN },
    285     { "mh"_s, USCRIPT_LATIN },
    286     { "mi"_s, USCRIPT_LATIN },
    287     { "mk"_s, USCRIPT_CYRILLIC },
    288     { "ml"_s, USCRIPT_MALAYALAM },
    289     { "mn"_s, USCRIPT_CYRILLIC },
    290     { "mr"_s, USCRIPT_DEVANAGARI },
    291     { "ms"_s, USCRIPT_LATIN },
    292     { "mt"_s, USCRIPT_LATIN },
    293     { "my"_s, USCRIPT_MYANMAR },
    294     { "myv"_s, USCRIPT_CYRILLIC },
    295     { "na"_s, USCRIPT_LATIN },
    296     { "nb"_s, USCRIPT_LATIN },
    297     { "ne"_s, USCRIPT_DEVANAGARI },
    298     { "niu"_s, USCRIPT_LATIN },
    299     { "nl"_s, USCRIPT_LATIN },
    300     { "nn"_s, USCRIPT_LATIN },
    301     { "nr"_s, USCRIPT_LATIN },
    302     { "nso"_s, USCRIPT_LATIN },
    303     { "ny"_s, USCRIPT_LATIN },
    304     { "oc"_s, USCRIPT_LATIN },
    305     { "om"_s, USCRIPT_LATIN },
    306     { "or"_s, USCRIPT_ORIYA },
    307     { "os"_s, USCRIPT_CYRILLIC },
    308     { "pa"_s, USCRIPT_GURMUKHI },
    309     { "pag"_s, USCRIPT_LATIN },
    310     { "pap"_s, USCRIPT_LATIN },
    311     { "pau"_s, USCRIPT_LATIN },
    312     { "pl"_s, USCRIPT_LATIN },
    313     { "pon"_s, USCRIPT_LATIN },
    314     { "ps"_s, USCRIPT_ARABIC },
    315     { "pt"_s, USCRIPT_LATIN },
    316     { "qu"_s, USCRIPT_LATIN },
    317     { "rm"_s, USCRIPT_LATIN },
    318     { "rn"_s, USCRIPT_LATIN },
    319     { "ro"_s, USCRIPT_LATIN },
    320     { "ru"_s, USCRIPT_CYRILLIC },
    321     { "rw"_s, USCRIPT_LATIN },
    322     { "sa"_s, USCRIPT_DEVANAGARI },
    323     { "sah"_s, USCRIPT_CYRILLIC },
    324     { "sat"_s, USCRIPT_LATIN },
    325     { "sd"_s, USCRIPT_ARABIC },
    326     { "se"_s, USCRIPT_LATIN },
    327     { "sg"_s, USCRIPT_LATIN },
    328     { "si"_s, USCRIPT_SINHALA },
    329     { "sid"_s, USCRIPT_LATIN },
    330     { "sk"_s, USCRIPT_LATIN },
    331     { "sl"_s, USCRIPT_LATIN },
    332     { "sm"_s, USCRIPT_LATIN },
    333     { "so"_s, USCRIPT_LATIN },
    334     { "sq"_s, USCRIPT_LATIN },
    335     { "sr"_s, USCRIPT_CYRILLIC },
    336     { "ss"_s, USCRIPT_LATIN },
    337     { "st"_s, USCRIPT_LATIN },
    338     { "su"_s, USCRIPT_LATIN },
    339     { "sv"_s, USCRIPT_LATIN },
    340     { "sw"_s, USCRIPT_LATIN },
    341     { "ta"_s, USCRIPT_TAMIL },
    342     { "te"_s, USCRIPT_TELUGU },
    343     { "tet"_s, USCRIPT_LATIN },
    344     { "tg"_s, USCRIPT_CYRILLIC },
    345     { "th"_s, USCRIPT_THAI },
    346     { "ti"_s, USCRIPT_ETHIOPIC },
    347     { "tig"_s, USCRIPT_ETHIOPIC },
    348     { "tk"_s, USCRIPT_LATIN },
    349     { "tkl"_s, USCRIPT_LATIN },
    350     { "tl"_s, USCRIPT_LATIN },
    351     { "tn"_s, USCRIPT_LATIN },
    352     { "to"_s, USCRIPT_LATIN },
    353     { "tpi"_s, USCRIPT_LATIN },
    354     { "tr"_s, USCRIPT_LATIN },
    355     { "trv"_s, USCRIPT_LATIN },
    356     { "ts"_s, USCRIPT_LATIN },
    357     { "tt"_s, USCRIPT_CYRILLIC },
    358     { "tvl"_s, USCRIPT_LATIN },
    359     { "tw"_s, USCRIPT_LATIN },
    360     { "ty"_s, USCRIPT_LATIN },
    361     { "tyv"_s, USCRIPT_CYRILLIC },
    362     { "udm"_s, USCRIPT_CYRILLIC },
    363     { "ug"_s, USCRIPT_ARABIC },
    364     { "uk"_s, USCRIPT_CYRILLIC },
    365     { "und"_s, USCRIPT_LATIN },
    366     { "ur"_s, USCRIPT_ARABIC },
    367     { "uz"_s, USCRIPT_CYRILLIC },
    368     { "ve"_s, USCRIPT_LATIN },
    369     { "vi"_s, USCRIPT_LATIN },
    370     { "wal"_s, USCRIPT_ETHIOPIC },
    371     { "war"_s, USCRIPT_LATIN },
    372     { "wo"_s, USCRIPT_LATIN },
    373     { "xh"_s, USCRIPT_LATIN },
    374     { "yap"_s, USCRIPT_LATIN },
    375     { "yo"_s, USCRIPT_LATIN },
    376     { "za"_s, USCRIPT_LATIN },
    377     { "zh"_s, USCRIPT_HAN },
    378     { "zh_hk"_s, USCRIPT_TRADITIONAL_HAN },
    379     { "zh_tw"_s, USCRIPT_TRADITIONAL_HAN },
    380     { "zu"_s, USCRIPT_LATIN }
    381 };
    382 
    383 struct LocaleScriptMapHashTraits : public HashTraits<String> {
    384     static const int minimumTableSize = WTF::HashTableCapacityForSize<WTF_ARRAY_LENGTH(localeScriptList)>::value;
    385 };
    386 
    387264UScriptCode localeToScriptCodeForFontSelection(const String& locale)
    388265{
    389     static const auto localeScriptMap = makeNeverDestroyed([] {
    390         HashMap<String, UScriptCode, ASCIICaseInsensitiveHash, LocaleScriptMapHashTraits> map;
    391         for (auto& localeAndScript : localeScriptList)
    392             map.add(localeAndScript.locale, localeAndScript.script);
    393         return map;
    394     }());
     266    static constexpr LocaleScript localeScriptList[] = {
     267        { "aa", USCRIPT_LATIN },
     268        { "ab", USCRIPT_CYRILLIC },
     269        { "ady", USCRIPT_CYRILLIC },
     270        { "af", USCRIPT_LATIN },
     271        { "ak", USCRIPT_LATIN },
     272        { "am", USCRIPT_ETHIOPIC },
     273        { "ar", USCRIPT_ARABIC },
     274        { "as", USCRIPT_BENGALI },
     275        { "ast", USCRIPT_LATIN },
     276        { "av", USCRIPT_CYRILLIC },
     277        { "ay", USCRIPT_LATIN },
     278        { "az", USCRIPT_LATIN },
     279        { "ba", USCRIPT_CYRILLIC },
     280        { "be", USCRIPT_CYRILLIC },
     281        { "bg", USCRIPT_CYRILLIC },
     282        { "bi", USCRIPT_LATIN },
     283        { "bn", USCRIPT_BENGALI },
     284        { "bo", USCRIPT_TIBETAN },
     285        { "bs", USCRIPT_LATIN },
     286        { "ca", USCRIPT_LATIN },
     287        { "ce", USCRIPT_CYRILLIC },
     288        { "ceb", USCRIPT_LATIN },
     289        { "ch", USCRIPT_LATIN },
     290        { "chk", USCRIPT_LATIN },
     291        { "cs", USCRIPT_LATIN },
     292        { "cy", USCRIPT_LATIN },
     293        { "da", USCRIPT_LATIN },
     294        { "de", USCRIPT_LATIN },
     295        { "dv", USCRIPT_THAANA },
     296        { "dz", USCRIPT_TIBETAN },
     297        { "ee", USCRIPT_LATIN },
     298        { "efi", USCRIPT_LATIN },
     299        { "el", USCRIPT_GREEK },
     300        { "en", USCRIPT_LATIN },
     301        { "es", USCRIPT_LATIN },
     302        { "et", USCRIPT_LATIN },
     303        { "eu", USCRIPT_LATIN },
     304        { "fa", USCRIPT_ARABIC },
     305        { "fi", USCRIPT_LATIN },
     306        { "fil", USCRIPT_LATIN },
     307        { "fj", USCRIPT_LATIN },
     308        { "fo", USCRIPT_LATIN },
     309        { "fr", USCRIPT_LATIN },
     310        { "fur", USCRIPT_LATIN },
     311        { "fy", USCRIPT_LATIN },
     312        { "ga", USCRIPT_LATIN },
     313        { "gaa", USCRIPT_LATIN },
     314        { "gd", USCRIPT_LATIN },
     315        { "gil", USCRIPT_LATIN },
     316        { "gl", USCRIPT_LATIN },
     317        { "gn", USCRIPT_LATIN },
     318        { "gsw", USCRIPT_LATIN },
     319        { "gu", USCRIPT_GUJARATI },
     320        { "ha", USCRIPT_LATIN },
     321        { "haw", USCRIPT_LATIN },
     322        { "he", USCRIPT_HEBREW },
     323        { "hi", USCRIPT_DEVANAGARI },
     324        { "hil", USCRIPT_LATIN },
     325        { "ho", USCRIPT_LATIN },
     326        { "hr", USCRIPT_LATIN },
     327        { "ht", USCRIPT_LATIN },
     328        { "hu", USCRIPT_LATIN },
     329        { "hy", USCRIPT_ARMENIAN },
     330        { "id", USCRIPT_LATIN },
     331        { "ig", USCRIPT_LATIN },
     332        { "ii", USCRIPT_YI },
     333        { "ilo", USCRIPT_LATIN },
     334        { "inh", USCRIPT_CYRILLIC },
     335        { "is", USCRIPT_LATIN },
     336        { "it", USCRIPT_LATIN },
     337        { "iu", USCRIPT_CANADIAN_ABORIGINAL },
     338        { "ja", USCRIPT_KATAKANA_OR_HIRAGANA },
     339        { "jv", USCRIPT_LATIN },
     340        { "ka", USCRIPT_GEORGIAN },
     341        { "kaj", USCRIPT_LATIN },
     342        { "kam", USCRIPT_LATIN },
     343        { "kbd", USCRIPT_CYRILLIC },
     344        { "kha", USCRIPT_LATIN },
     345        { "kk", USCRIPT_CYRILLIC },
     346        { "kl", USCRIPT_LATIN },
     347        { "km", USCRIPT_KHMER },
     348        { "kn", USCRIPT_KANNADA },
     349        { "ko", USCRIPT_HANGUL },
     350        { "kok", USCRIPT_DEVANAGARI },
     351        { "kos", USCRIPT_LATIN },
     352        { "kpe", USCRIPT_LATIN },
     353        { "krc", USCRIPT_CYRILLIC },
     354        { "ks", USCRIPT_ARABIC },
     355        { "ku", USCRIPT_ARABIC },
     356        { "kum", USCRIPT_CYRILLIC },
     357        { "ky", USCRIPT_CYRILLIC },
     358        { "la", USCRIPT_LATIN },
     359        { "lah", USCRIPT_ARABIC },
     360        { "lb", USCRIPT_LATIN },
     361        { "lez", USCRIPT_CYRILLIC },
     362        { "ln", USCRIPT_LATIN },
     363        { "lo", USCRIPT_LAO },
     364        { "lt", USCRIPT_LATIN },
     365        { "lv", USCRIPT_LATIN },
     366        { "mai", USCRIPT_DEVANAGARI },
     367        { "mdf", USCRIPT_CYRILLIC },
     368        { "mg", USCRIPT_LATIN },
     369        { "mh", USCRIPT_LATIN },
     370        { "mi", USCRIPT_LATIN },
     371        { "mk", USCRIPT_CYRILLIC },
     372        { "ml", USCRIPT_MALAYALAM },
     373        { "mn", USCRIPT_CYRILLIC },
     374        { "mr", USCRIPT_DEVANAGARI },
     375        { "ms", USCRIPT_LATIN },
     376        { "mt", USCRIPT_LATIN },
     377        { "my", USCRIPT_MYANMAR },
     378        { "myv", USCRIPT_CYRILLIC },
     379        { "na", USCRIPT_LATIN },
     380        { "nb", USCRIPT_LATIN },
     381        { "ne", USCRIPT_DEVANAGARI },
     382        { "niu", USCRIPT_LATIN },
     383        { "nl", USCRIPT_LATIN },
     384        { "nn", USCRIPT_LATIN },
     385        { "nr", USCRIPT_LATIN },
     386        { "nso", USCRIPT_LATIN },
     387        { "ny", USCRIPT_LATIN },
     388        { "oc", USCRIPT_LATIN },
     389        { "om", USCRIPT_LATIN },
     390        { "or", USCRIPT_ORIYA },
     391        { "os", USCRIPT_CYRILLIC },
     392        { "pa", USCRIPT_GURMUKHI },
     393        { "pag", USCRIPT_LATIN },
     394        { "pap", USCRIPT_LATIN },
     395        { "pau", USCRIPT_LATIN },
     396        { "pl", USCRIPT_LATIN },
     397        { "pon", USCRIPT_LATIN },
     398        { "ps", USCRIPT_ARABIC },
     399        { "pt", USCRIPT_LATIN },
     400        { "qu", USCRIPT_LATIN },
     401        { "rm", USCRIPT_LATIN },
     402        { "rn", USCRIPT_LATIN },
     403        { "ro", USCRIPT_LATIN },
     404        { "ru", USCRIPT_CYRILLIC },
     405        { "rw", USCRIPT_LATIN },
     406        { "sa", USCRIPT_DEVANAGARI },
     407        { "sah", USCRIPT_CYRILLIC },
     408        { "sat", USCRIPT_LATIN },
     409        { "sd", USCRIPT_ARABIC },
     410        { "se", USCRIPT_LATIN },
     411        { "sg", USCRIPT_LATIN },
     412        { "si", USCRIPT_SINHALA },
     413        { "sid", USCRIPT_LATIN },
     414        { "sk", USCRIPT_LATIN },
     415        { "sl", USCRIPT_LATIN },
     416        { "sm", USCRIPT_LATIN },
     417        { "so", USCRIPT_LATIN },
     418        { "sq", USCRIPT_LATIN },
     419        { "sr", USCRIPT_CYRILLIC },
     420        { "ss", USCRIPT_LATIN },
     421        { "st", USCRIPT_LATIN },
     422        { "su", USCRIPT_LATIN },
     423        { "sv", USCRIPT_LATIN },
     424        { "sw", USCRIPT_LATIN },
     425        { "ta", USCRIPT_TAMIL },
     426        { "te", USCRIPT_TELUGU },
     427        { "tet", USCRIPT_LATIN },
     428        { "tg", USCRIPT_CYRILLIC },
     429        { "th", USCRIPT_THAI },
     430        { "ti", USCRIPT_ETHIOPIC },
     431        { "tig", USCRIPT_ETHIOPIC },
     432        { "tk", USCRIPT_LATIN },
     433        { "tkl", USCRIPT_LATIN },
     434        { "tl", USCRIPT_LATIN },
     435        { "tn", USCRIPT_LATIN },
     436        { "to", USCRIPT_LATIN },
     437        { "tpi", USCRIPT_LATIN },
     438        { "tr", USCRIPT_LATIN },
     439        { "trv", USCRIPT_LATIN },
     440        { "ts", USCRIPT_LATIN },
     441        { "tt", USCRIPT_CYRILLIC },
     442        { "tvl", USCRIPT_LATIN },
     443        { "tw", USCRIPT_LATIN },
     444        { "ty", USCRIPT_LATIN },
     445        { "tyv", USCRIPT_CYRILLIC },
     446        { "udm", USCRIPT_CYRILLIC },
     447        { "ug", USCRIPT_ARABIC },
     448        { "uk", USCRIPT_CYRILLIC },
     449        { "und", USCRIPT_LATIN },
     450        { "ur", USCRIPT_ARABIC },
     451        { "uz", USCRIPT_CYRILLIC },
     452        { "ve", USCRIPT_LATIN },
     453        { "vi", USCRIPT_LATIN },
     454        { "wal", USCRIPT_ETHIOPIC },
     455        { "war", USCRIPT_LATIN },
     456        { "wo", USCRIPT_LATIN },
     457        { "xh", USCRIPT_LATIN },
     458        { "yap", USCRIPT_LATIN },
     459        { "yo", USCRIPT_LATIN },
     460        { "za", USCRIPT_LATIN },
     461        { "zh", USCRIPT_HAN },
     462        { "zh_hk", USCRIPT_TRADITIONAL_HAN },
     463        { "zh_tw", USCRIPT_TRADITIONAL_HAN },
     464        { "zu", USCRIPT_LATIN },
     465    };
     466
     467    static_assert(LocaleName("aa").value() == 0x6161000000000000ULL);
     468    static_assert(LocaleName("zh_tw").value() == 0x7a685f7477000000ULL);
     469
     470    ASSERT(
     471        std::is_sorted(std::begin(localeScriptList), std::end(localeScriptList),
     472            [](const LocaleScript& a, const LocaleScript& b) {
     473                return a.locale < b.locale;
     474            }));
     475
     476    auto tryFindScriptCode = [&] (const String& string) -> Optional<UScriptCode> {
     477        auto localeName = LocaleName::parse(string);
     478        if (!localeName)
     479            return WTF::nullopt;
     480
     481        auto* element = tryBinarySearch<LocaleScript>(localeScriptList, std::size(localeScriptList), localeName.value(),
     482            [](const LocaleScript* localeScript) {
     483                return localeScript->locale;
     484            });
     485        if (element)
     486            return element->script;
     487        return WTF::nullopt;
     488    };
    395489
    396490    String canonicalLocale = locale;
    397491    canonicalLocale.replace('-', '_');
    398492    while (!canonicalLocale.isEmpty()) {
    399         auto it = localeScriptMap.get().find(canonicalLocale);
    400         if (it != localeScriptMap.get().end())
    401             return it->value;
     493        if (auto scriptCode = tryFindScriptCode(canonicalLocale))
     494            return scriptCode.value();
    402495        auto underscorePosition = canonicalLocale.reverseFind('_');
    403496        if (underscorePosition == notFound)
Note: See TracChangeset for help on using the changeset viewer.