/*
 * Copyright (c) Meta Platforms, Inc. and affiliates.
 *
 * This source code is licensed under the MIT license found in the
 * LICENSE file in the root directory of this source tree.
 */

package com.facebook.hermes.intl;

import java.util.ArrayList;
import java.util.Collections;
import java.util.TreeMap;

class LanguageTagsGenerated {

  public static final boolean UsePreprocessedCLDRData = false;

  // Note:: This data is autogenerated using the tool whose source is kept at
  // hermes/utils/IntlGen/IntlGen.java
  public static String[] regularGrandfatheredKeys = null;

  public static String[] regularGrandfatheredReplacements = null;

  public static String[] languageAliasKeys2 = null;

  public static String[] languageAliasReplacements2 = null;

  public static String[] languageAliasKeys3 = null;

  public static String[] languageAliasReplacements3 = null;

  public static String[] complexLanguageAliasKeys2 = null;

  public static String[] complexLanguageAliasReplacementsLanguage2 = null;

  public static String[] complexLanguageAliasReplacementsScript2 = null;

  public static String[] complexLanguageAliasReplacementsRegion2 = null;

  public static String[] complexLanguageAliasKeys3 = null;

  public static String[] complexLanguageAliasReplacementsLanguage3 = null;

  public static String[] complexLanguageAliasReplacementsScript3 = null;

  public static String[] complexLanguageAliasReplacementsRegion3 = null;

  public static String[] regionAliasKeys2 = null;

  public static String[] regionAliasReplacements2 = null;

  public static String[] regionAliasKeys3 = null;

  public static String[] regionAliasReplacements3 = null;

  static {

    // We are relying on the effect of using "static const boolean" for conditional compilation in
    // java ..
    // Ref: http://www.javapractices.com/topic/TopicAction.do?Id=64
    if (UsePreprocessedCLDRData) {

      regularGrandfatheredKeys =
          new String[] {
            "art-lojban",
            "cel-gaulish",
            "i-default",
            "i-enochian",
            "i-mingo",
            "zh-guoyu",
            "zh-hakka",
            "zh-min",
            "zh-xiang"
          };

      regularGrandfatheredReplacements =
          new String[] {
            "jbo",
            "xtg-x-cel-gaulish",
            "en-x-i-default",
            "und-x-i-enochian",
            "see-x-i-mingo",
            "zh",
            "hak",
            "nan-x-zh-min",
            "hsn"
          };

      languageAliasKeys2 = new String[] {"bh", "in", "iw", "ji", "jw", "mo", "no", "tl", "tw"};

      languageAliasReplacements2 =
          new String[] {"bho", "id", "he", "yi", "jv", "ro", "nb", "fil", "ak"};

      complexLanguageAliasKeys2 = new String[] {"cnr"};

      complexLanguageAliasKeys2 = new String[] {"sh"};

      complexLanguageAliasReplacementsLanguage2 = new String[] {"sr"};

      complexLanguageAliasReplacementsScript2 = new String[] {"Latn"};

      complexLanguageAliasReplacementsRegion2 = new String[] {null};

      complexLanguageAliasKeys3 = new String[] {"cnr", "drw", "hbs", "prs", "swc", "tnf"};

      complexLanguageAliasReplacementsLanguage3 = new String[] {"sr", "fa", "sr", "fa", "sw", "fa"};

      complexLanguageAliasReplacementsScript3 = new String[] {null, null, "Latn", null, null, null};

      complexLanguageAliasReplacementsRegion3 = new String[] {"ME", "af", null, "AF", "CD", "af"};

      languageAliasKeys3 =
          new String[] {
            "aam", "aar", "abk", "adp", "afr", "aju", "aka", "alb", "als", "amh", "ara", "arb",
            "arg", "arm", "asd", "asm", "aue", "ava", "ave", "aym", "ayr", "ayx", "aze", "azj",
            "bak", "bam", "baq", "bcc", "bcl", "bel", "ben", "bgm", "bih", "bis", "bjd", "bod",
            "bos", "bre", "bul", "bur", "bxk", "bxr", "cat", "ccq", "ces", "cha", "che", "chi",
            "chu", "chv", "cjr", "cka", "cld", "cmk", "cmn", "cor", "cos", "coy", "cqu", "cre",
            "cwd", "cym", "cze", "dan", "deu", "dgo", "dhd", "dik", "diq", "dit", "div", "drh",
            "dut", "dzo", "ekk", "ell", "emk", "eng", "epo", "esk", "est", "eus", "ewe", "fao",
            "fas", "fat", "fij", "fin", "fra", "fre", "fry", "fuc", "ful", "gav", "gaz", "gbo",
            "geo", "ger", "gfx", "ggn", "gla", "gle", "glg", "glv", "gno", "gre", "grn", "gti",
            "gug", "guj", "guv", "gya", "hat", "hau", "hdn", "hea", "heb", "her", "him", "hin",
            "hmo", "hrr", "hrv", "hun", "hye", "ibi", "ibo", "ice", "ido", "iii", "ike", "iku",
            "ile", "ilw", "ina", "ind", "ipk", "isl", "ita", "jav", "jeg", "jpn", "kal", "kan",
            "kas", "kat", "kau", "kaz", "kgc", "kgh", "khk", "khm", "kik", "kin", "kir", "kmr",
            "knc", "kng", "knn", "koj", "kom", "kon", "kor", "kpv", "krm", "ktr", "kua", "kur",
            "kvs", "kwq", "kxe", "kzj", "kzt", "lao", "lat", "lav", "lbk", "lii", "lim", "lin",
            "lit", "llo", "lmm", "ltz", "lub", "lug", "lvs", "mac", "mah", "mal", "mao", "mar",
            "may", "meg", "mhr", "mkd", "mlg", "mlt", "mnk", "mol", "mon", "mri", "msa", "mst",
            "mup", "mwj", "mya", "myd", "myt", "nad", "nau", "nav", "nbl", "ncp", "nde", "ndo",
            "nep", "nld", "nno", "nns", "nnx", "nob", "nor", "npi", "nts", "nya", "oci", "ojg",
            "oji", "ori", "orm", "ory", "oss", "oun", "pan", "pbu", "pcr", "per", "pes", "pli",
            "plt", "pmc", "pmu", "pnb", "pol", "por", "ppa", "ppr", "pry", "pus", "puz", "que",
            "quz", "rmy", "roh", "ron", "rum", "run", "rus", "sag", "san", "sca", "scc", "scr",
            "sin", "skk", "slk", "slo", "slv", "sme", "smo", "sna", "snd", "som", "sot", "spa",
            "spy", "sqi", "src", "srd", "srp", "ssw", "sun", "swa", "swe", "swh", "tah", "tam",
            "tat", "tdu", "tel", "tgk", "tgl", "tha", "thc", "thx", "tib", "tie", "tir", "tkk",
            "tlw", "tmp", "tne", "ton", "tsf", "tsn", "tso", "ttq", "tuk", "tur", "twi", "uig",
            "ukr", "umu", "uok", "urd", "uzb", "uzn", "ven", "vie", "vol", "wel", "wln", "wol",
            "xba", "xho", "xia", "xkh", "xpe", "xsj", "xsl", "ybd", "ydd", "yid", "yma", "ymt",
            "yor", "yos", "yuu", "zai", "zha", "zho", "zsm", "zul", "zyb"
          };

      languageAliasReplacements3 =
          new String[] {
            "aas", "aa", "ab", "dz", "af", "jrb", "ak", "sq", "sq", "am", "ar", "ar", "an", "hy",
            "snz", "as", "ktz", "av", "ae", "ay", "ay", "nun", "az", "az", "ba", "bm", "eu", "bal",
            "bik", "be", "bn", "bcg", "bho", "bi", "drl", "bo", "bs", "br", "bg", "my", "luy",
            "bua", "ca", "rki", "cs", "ch", "ce", "zh", "cu", "cv", "mom", "cmr", "syr", "xch",
            "zh", "kw", "co", "pij", "quh", "cr", "cr", "cy", "cs", "da", "de", "doi", "mwr", "din",
            "zza", "dif", "dv", "mn", "nl", "dz", "et", "el", "man", "en", "eo", "ik", "et", "eu",
            "ee", "fo", "fa", "ak", "fj", "fi", "fr", "fr", "fy", "ff", "ff", "dev", "om", "grb",
            "ka", "de", "vaj", "gvr", "gd", "ga", "gl", "gv", "gon", "el", "gn", "nyc", "gn", "gu",
            "duz", "gba", "ht", "ha", "hai", "hmn", "he", "hz", "srx", "hi", "ho", "jal", "hr",
            "hu", "hy", "opa", "ig", "is", "io", "ii", "iu", "iu", "ie", "gal", "ia", "id", "ik",
            "is", "it", "jv", "oyb", "ja", "kl", "kn", "ks", "ka", "kr", "kk", "tdf", "kml", "mn",
            "km", "ki", "rw", "ky", "ku", "kr", "kg", "kok", "kwv", "kv", "kg", "ko", "kv", "bmf",
            "dtp", "kj", "ku", "gdj", "yam", "tvd", "dtp", "dtp", "lo", "la", "lv", "bnc", "raq",
            "li", "ln", "lt", "ngt", "rmx", "lb", "lu", "lg", "lv", "mk", "mh", "ml", "mi", "mr",
            "ms", "cir", "chm", "mk", "mg", "mt", "man", "ro", "mn", "mi", "ms", "mry", "raj",
            "vaj", "my", "aog", "mry", "xny", "na", "nv", "nr", "kdz", "nd", "ng", "ne", "nl", "nn",
            "nbr", "ngv", "nb", "nb", "ne", "pij", "ny", "oc", "oj", "oj", "or", "om", "or", "os",
            "vaj", "pa", "ps", "adx", "fa", "fa", "pi", "mg", "huw", "phr", "lah", "pl", "pt",
            "bfy", "lcq", "prt", "ps", "pub", "qu", "qu", "rom", "rm", "ro", "ro", "rn", "ru", "sg",
            "sa", "hle", "sr", "hr", "si", "oyb", "sk", "sk", "sl", "se", "sm", "sn", "sd", "so",
            "st", "es", "kln", "sq", "sc", "sc", "sr", "ss", "su", "sw", "sv", "sw", "ty", "ta",
            "tt", "dtp", "te", "tg", "fil", "th", "tpo", "oyb", "bo", "ras", "ti", "twm", "weo",
            "tyj", "kak", "to", "taj", "tn", "ts", "tmh", "tk", "tr", "ak", "ug", "uk", "del",
            "ema", "ur", "uz", "uz", "ve", "vi", "vo", "cy", "wa", "wo", "cax", "xh", "acn", "waw",
            "kpe", "suj", "den", "rki", "yi", "yi", "lrr", "mtm", "yo", "zom", "yug", "zap", "za",
            "zh", "ms", "zu", "za"
          };

      regionAliasKeys2 =
          new String[] {
            "BU", "CT", "DD", "DY", "FX", "HV", "JT", "MI", "NH", "NQ", "PU", "PZ", "QU", "RH",
            "TP", "UK", "VD", "WK", "YD", "ZR"
          };

      regionAliasReplacements2 =
          new String[] {
            "MM", "KI", "DE", "BJ", "FR", "BF", "UM", "UM", "VU", "AQ", "UM", "PA", "EU", "ZW",
            "TL", "GB", "VN", "UM", "YE", "CD"
          };

      regionAliasKeys3 =
          new String[] {
            "004", "008", "010", "012", "016", "020", "024", "028", "031", "032", "036", "040",
            "044", "048", "050", "051", "052", "056", "060", "064", "068", "070", "072", "074",
            "076", "084", "086", "090", "092", "096", "100", "104", "108", "112", "116", "120",
            "124", "132", "136", "140", "144", "148", "152", "156", "158", "162", "166", "170",
            "174", "175", "178", "180", "184", "188", "191", "192", "196", "203", "204", "208",
            "212", "214", "218", "222", "226", "230", "231", "232", "233", "234", "238", "239",
            "242", "246", "248", "249", "250", "254", "258", "260", "262", "266", "268", "270",
            "275", "276", "278", "280", "288", "292", "296", "300", "304", "308", "312", "316",
            "320", "324", "328", "332", "334", "336", "340", "344", "348", "352", "356", "360",
            "364", "368", "372", "376", "380", "384", "388", "392", "398", "400", "404", "408",
            "410", "414", "417", "418", "422", "426", "428", "430", "434", "438", "440", "442",
            "446", "450", "454", "458", "462", "466", "470", "474", "478", "480", "484", "492",
            "496", "498", "499", "500", "504", "508", "512", "516", "520", "524", "528", "531",
            "533", "534", "535", "540", "548", "554", "558", "562", "566", "570", "574", "578",
            "580", "581", "583", "584", "585", "586", "591", "598", "600", "604", "608", "612",
            "616", "620", "624", "626", "630", "634", "638", "642", "643", "646", "652", "654",
            "659", "660", "662", "663", "666", "670", "674", "678", "682", "686", "688", "690",
            "694", "702", "703", "704", "705", "706", "710", "716", "720", "724", "728", "729",
            "732", "736", "740", "744", "748", "752", "756", "760", "762", "764", "768", "772",
            "776", "780", "784", "788", "792", "795", "796", "798", "800", "804", "807", "818",
            "826", "831", "832", "833", "834", "840", "850", "854", "858", "860", "862", "876",
            "882", "886", "887", "894", "958", "959", "960", "962", "963", "964", "965", "966",
            "967", "968", "969", "970", "971", "972", "973", "974", "975", "976", "977", "978",
            "979", "980", "981", "982", "983", "984", "985", "986", "987", "988", "989", "990",
            "991", "992", "993", "994", "995", "996", "997", "998", "999", "AAA", "ABW", "AFG",
            "AGO", "AIA", "ALA", "ALB", "AND", "ARE", "ARG", "ARM", "ASC", "ASM", "ATA", "ATF",
            "ATG", "AUS", "AUT", "AZE", "BDI", "BEL", "BEN", "BES", "BFA", "BGD", "BGR", "BHR",
            "BHS", "BIH", "BLM", "BLR", "BLZ", "BMU", "BOL", "BRA", "BRB", "BRN", "BTN", "BUR",
            "BVT", "BWA", "CAF", "CAN", "CCK", "CHE", "CHL", "CHN", "CIV", "CMR", "COD", "COG",
            "COK", "COL", "COM", "CPT", "CPV", "CRI", "CUB", "CUW", "CXR", "CYM", "CYP", "CZE",
            "DDR", "DEU", "DGA", "DJI", "DMA", "DNK", "DOM", "DZA", "ECU", "EGY", "ERI", "ESH",
            "ESP", "EST", "ETH", "FIN", "FJI", "FLK", "FRA", "FRO", "FSM", "FXX", "GAB", "GBR",
            "GEO", "GGY", "GHA", "GIB", "GIN", "GLP", "GMB", "GNB", "GNQ", "GRC", "GRD", "GRL",
            "GTM", "GUF", "GUM", "GUY", "HKG", "HMD", "HND", "HRV", "HTI", "HUN", "IDN", "IMN",
            "IND", "IOT", "IRL", "IRN", "IRQ", "ISL", "ISR", "ITA", "JAM", "JEY", "JOR", "JPN",
            "KAZ", "KEN", "KGZ", "KHM", "KIR", "KNA", "KOR", "KWT", "LAO", "LBN", "LBR", "LBY",
            "LCA", "LIE", "LKA", "LSO", "LTU", "LUX", "LVA", "MAC", "MAF", "MAR", "MCO", "MDA",
            "MDG", "MDV", "MEX", "MHL", "MKD", "MLI", "MLT", "MMR", "MNE", "MNG", "MNP", "MOZ",
            "MRT", "MSR", "MTQ", "MUS", "MWI", "MYS", "MYT", "NAM", "NCL", "NER", "NFK", "NGA",
            "NIC", "NIU", "NLD", "NOR", "NPL", "NRU", "NZL", "OMN", "PAK", "PAN", "PCN", "PER",
            "PHL", "PLW", "PNG", "POL", "PRI", "PRK", "PRT", "PRY", "PSE", "PYF", "QAT", "QMM",
            "QNN", "QPP", "QQQ", "QRR", "QSS", "QTT", "QUU", "QVV", "QWW", "QXX", "QYY", "QZZ",
            "REU", "ROU", "RUS", "RWA", "SAU", "SDN", "SEN", "SGP", "SGS", "SHN", "SJM", "SLB",
            "SLE", "SLV", "SMR", "SOM", "SPM", "SRB", "SSD", "STP", "SUR", "SVK", "SVN", "SWE",
            "SWZ", "SXM", "SYC", "SYR", "TAA", "TCA", "TCD", "TGO", "THA", "TJK", "TKL", "TKM",
            "TLS", "TMP", "TON", "TTO", "TUN", "TUR", "TUV", "TWN", "TZA", "UGA", "UKR", "UMI",
            "URY", "USA", "UZB", "VAT", "VCT", "VEN", "VGB", "VIR", "VNM", "VUT", "WLF", "WSM",
            "XAA", "XBB", "XCC", "XDD", "XEE", "XFF", "XGG", "XHH", "XII", "XJJ", "XKK", "XLL",
            "XMM", "XNN", "XOO", "XPP", "XQQ", "XRR", "XSS", "XTT", "XUU", "XVV", "XWW", "XXX",
            "XYY", "XZZ", "YEM", "YMD", "ZAF", "ZAR", "ZMB", "ZWE", "ZZZ"
          };

      regionAliasReplacements3 =
          new String[] {
            "AF", "AL", "AQ", "DZ", "AS", "AD", "AO", "AG", "AZ", "AR", "AU", "AT", "BS", "BH",
            "BD", "AM", "BB", "BE", "BM", "BT", "BO", "BA", "BW", "BV", "BR", "BZ", "IO", "SB",
            "VG", "BN", "BG", "MM", "BI", "BY", "KH", "CM", "CA", "CV", "KY", "CF", "LK", "TD",
            "CL", "CN", "TW", "CX", "CC", "CO", "KM", "YT", "CG", "CD", "CK", "CR", "HR", "CU",
            "CY", "CZ", "BJ", "DK", "DM", "DO", "EC", "SV", "GQ", "ET", "ET", "ER", "EE", "FO",
            "FK", "GS", "FJ", "FI", "AX", "FR", "FR", "GF", "PF", "TF", "DJ", "GA", "GE", "GM",
            "PS", "DE", "DE", "DE", "GH", "GI", "KI", "GR", "GL", "GD", "GP", "GU", "GT", "GN",
            "GY", "HT", "HM", "VA", "HN", "HK", "HU", "IS", "IN", "ID", "IR", "IQ", "IE", "IL",
            "IT", "CI", "JM", "JP", "KZ", "JO", "KE", "KP", "KR", "KW", "KG", "LA", "LB", "LS",
            "LV", "LR", "LY", "LI", "LT", "LU", "MO", "MG", "MW", "MY", "MV", "ML", "MT", "MQ",
            "MR", "MU", "MX", "MC", "MN", "MD", "ME", "MS", "MA", "MZ", "OM", "NA", "NR", "NP",
            "NL", "CW", "AW", "SX", "BQ", "NC", "VU", "NZ", "NI", "NE", "NG", "NU", "NF", "NO",
            "MP", "UM", "FM", "MH", "PW", "PK", "PA", "PG", "PY", "PE", "PH", "PN", "PL", "PT",
            "GW", "TL", "PR", "QA", "RE", "RO", "RU", "RW", "BL", "SH", "KN", "AI", "LC", "MF",
            "PM", "VC", "SM", "ST", "SA", "SN", "RS", "SC", "SL", "SG", "SK", "VN", "SI", "SO",
            "ZA", "ZW", "YE", "ES", "SS", "SD", "EH", "SD", "SR", "SJ", "SZ", "SE", "CH", "SY",
            "TJ", "TH", "TG", "TK", "TO", "TT", "AE", "TN", "TR", "TM", "TC", "TV", "UG", "UA",
            "MK", "EG", "GB", "GG", "JE", "IM", "TZ", "US", "VI", "BF", "UY", "UZ", "VE", "WF",
            "WS", "YE", "YE", "ZM", "AA", "QM", "QN", "QP", "QQ", "QR", "QS", "QT", "EU", "QV",
            "QW", "QX", "QY", "QZ", "XA", "XB", "XC", "XD", "XE", "XF", "XG", "XH", "XI", "XJ",
            "XK", "XL", "XM", "XN", "XO", "XP", "XQ", "XR", "XS", "XT", "XU", "XV", "XW", "XX",
            "XY", "XZ", "ZZ", "AA", "AW", "AF", "AO", "AI", "AX", "AL", "AD", "AE", "AR", "AM",
            "AC", "AS", "AQ", "TF", "AG", "AU", "AT", "AZ", "BI", "BE", "BJ", "BQ", "BF", "BD",
            "BG", "BH", "BS", "BA", "BL", "BY", "BZ", "BM", "BO", "BR", "BB", "BN", "BT", "MM",
            "BV", "BW", "CF", "CA", "CC", "CH", "CL", "CN", "CI", "CM", "CD", "CG", "CK", "CO",
            "KM", "CP", "CV", "CR", "CU", "CW", "CX", "KY", "CY", "CZ", "DE", "DE", "DG", "DJ",
            "DM", "DK", "DO", "DZ", "EC", "EG", "ER", "EH", "ES", "EE", "ET", "FI", "FJ", "FK",
            "FR", "FO", "FM", "FR", "GA", "GB", "GE", "GG", "GH", "GI", "GN", "GP", "GM", "GW",
            "GQ", "GR", "GD", "GL", "GT", "GF", "GU", "GY", "HK", "HM", "HN", "HR", "HT", "HU",
            "ID", "IM", "IN", "IO", "IE", "IR", "IQ", "IS", "IL", "IT", "JM", "JE", "JO", "JP",
            "KZ", "KE", "KG", "KH", "KI", "KN", "KR", "KW", "LA", "LB", "LR", "LY", "LC", "LI",
            "LK", "LS", "LT", "LU", "LV", "MO", "MF", "MA", "MC", "MD", "MG", "MV", "MX", "MH",
            "MK", "ML", "MT", "MM", "ME", "MN", "MP", "MZ", "MR", "MS", "MQ", "MU", "MW", "MY",
            "YT", "NA", "NC", "NE", "NF", "NG", "NI", "NU", "NL", "NO", "NP", "NR", "NZ", "OM",
            "PK", "PA", "PN", "PE", "PH", "PW", "PG", "PL", "PR", "KP", "PT", "PY", "PS", "PF",
            "QA", "QM", "QN", "QP", "QQ", "QR", "QS", "QT", "EU", "QV", "QW", "QX", "QY", "QZ",
            "RE", "RO", "RU", "RW", "SA", "SD", "SN", "SG", "GS", "SH", "SJ", "SB", "SL", "SV",
            "SM", "SO", "PM", "RS", "SS", "ST", "SR", "SK", "SI", "SE", "SZ", "SX", "SC", "SY",
            "TA", "TC", "TD", "TG", "TH", "TJ", "TK", "TM", "TL", "TL", "TO", "TT", "TN", "TR",
            "TV", "TW", "TZ", "UG", "UA", "UM", "UY", "US", "UZ", "VA", "VC", "VE", "VG", "VI",
            "VN", "VU", "WF", "WS", "XA", "XB", "XC", "XD", "XE", "XF", "XG", "XH", "XI", "XJ",
            "XK", "XL", "XM", "XN", "XO", "XP", "XQ", "XR", "XS", "XT", "XU", "XV", "XW", "XX",
            "XY", "XZ", "YE", "YE", "ZA", "CD", "ZM", "ZW", "ZZ"
          };
    }
  }
}

class LocaleIdTokenizer {

  public class LocaleIdSubtagIterationFailed extends Exception {
    public LocaleIdSubtagIterationFailed() {
      super();
    }
  }

  public class LocaleIdSubtag {

    private CharSequence mLocaleIdBuffer = "";
    private int mSubtagStart = 0, mSubtagEnd = 0;

    LocaleIdSubtag(CharSequence localeIdBuffer, int subtagStart, int subtagEnd) {
      mLocaleIdBuffer = localeIdBuffer;
      mSubtagStart = subtagStart;
      mSubtagEnd = subtagEnd;
    }

    public void reset() {
      mLocaleIdBuffer = "";
      mSubtagStart = 0;
      mSubtagEnd = 0;
    }

    public String toString() {
      return mLocaleIdBuffer.subSequence(mSubtagStart, mSubtagEnd + 1).toString();
    }

    public String toLowerString() {

      StringBuffer destination = new StringBuffer();
      for (int idx = mSubtagStart; idx <= mSubtagEnd; idx++) {
        destination.append(Character.toLowerCase(mLocaleIdBuffer.charAt(idx)));
      }

      return destination.toString();
    }

    public String toUpperString() {
      StringBuffer destination = new StringBuffer();
      for (int idx = mSubtagStart; idx <= mSubtagEnd; idx++) {
        destination.append(Character.toUpperCase(mLocaleIdBuffer.charAt(idx)));
      }

      return destination.toString();
    }

    public String toTitleString() {
      StringBuffer destination = new StringBuffer();
      for (int idx = mSubtagStart; idx <= mSubtagEnd; idx++) {
        if (idx == mSubtagStart)
          destination.append(Character.toUpperCase((mLocaleIdBuffer.charAt(idx))));
        else destination.append(Character.toLowerCase(mLocaleIdBuffer.charAt(idx)));
      }

      return destination.toString();
    }

    public boolean isUnicodeLanguageSubtag() {
      return IntlTextUtils.isUnicodeLanguageSubtag(mLocaleIdBuffer, mSubtagStart, mSubtagEnd);
    }

    public boolean isExtensionSingleton() {
      return IntlTextUtils.isExtensionSingleton(mLocaleIdBuffer, mSubtagStart, mSubtagEnd);
    }

    public boolean isUnicodeScriptSubtag() {
      // https://unicode.org/reports/tr35/#Unicode_Language_and_Locale_Identifiers
      // = alpha{4};
      return IntlTextUtils.isUnicodeScriptSubtag(mLocaleIdBuffer, mSubtagStart, mSubtagEnd);
    }

    public boolean isUnicodeRegionSubtag() {
      // https://unicode.org/reports/tr35/#Unicode_Language_and_Locale_Identifiers
      // = (alpha{2} | digit{3}) ;
      return IntlTextUtils.isUnicodeRegionSubtag(mLocaleIdBuffer, mSubtagStart, mSubtagEnd);
    }

    public boolean isUnicodeVariantSubtag() {
      // https://unicode.org/reports/tr35/#Unicode_Language_and_Locale_Identifiers
      // = (alphanum{5,8}
      // | digit alphanum{3}) ;
      return IntlTextUtils.isUnicodeVariantSubtag(mLocaleIdBuffer, mSubtagStart, mSubtagEnd);
    }

    public boolean isUnicodeExtensionAttribute() {
      // https://unicode.org/reports/tr35/#Unicode_Language_and_Locale_Identifiers
      // = (alphanum{3,8}
      return IntlTextUtils.isUnicodeExtensionAttribute(mLocaleIdBuffer, mSubtagStart, mSubtagEnd);
    }

    public boolean isUnicodeExtensionKey() {
      // https://unicode.org/reports/tr35/#Unicode_Language_and_Locale_Identifiers
      // = alphanum alpha ;

      return IntlTextUtils.isUnicodeExtensionKey(mLocaleIdBuffer, mSubtagStart, mSubtagEnd);
    }

    public boolean isUnicodeExtensionKeyTypeItem() {
      // https://unicode.org/reports/tr35/#Unicode_Language_and_Locale_Identifiers
      // = alphanum alpha ;
      return IntlTextUtils.isUnicodeExtensionKeyTypeItem(mLocaleIdBuffer, mSubtagStart, mSubtagEnd);
    }

    public boolean isTranformedExtensionTKey() {
      // https://unicode.org/reports/tr35/#Unicode_Language_and_Locale_Identifiers
      //  	= alpha digit ;
      return IntlTextUtils.isTranformedExtensionTKey(mLocaleIdBuffer, mSubtagStart, mSubtagEnd);
    }

    public boolean isTranformedExtensionTValueItem() {
      // https://unicode.org/reports/tr35/#Unicode_Language_and_Locale_Identifiers
      // = (sep alphanum{3,8})+ ;
      return IntlTextUtils.isTranformedExtensionTValueItem(
          mLocaleIdBuffer, mSubtagStart, mSubtagEnd);
    }

    public boolean isPrivateUseExtension() {
      // https://unicode.org/reports/tr35/#Unicode_Language_and_Locale_Identifiers
      // = (sep alphanum{1,8})+ ;
      return IntlTextUtils.isPrivateUseExtension(mLocaleIdBuffer, mSubtagStart, mSubtagEnd);
    }

    public boolean isOtherExtension() {
      // https://unicode.org/reports/tr35/#Unicode_Language_and_Locale_Identifiers
      // = (sep alphanum{2,8})+ ;
      return IntlTextUtils.isOtherExtension(mLocaleIdBuffer, mSubtagStart, mSubtagEnd);
    }
  }

  private CharSequence mLocaleIdBuffer;
  int mCurrentSubtagStart = 0, mCurrentSubtagEnd = -1;

  private static boolean isSubtagSeparator(char c) {
    return c == '-';
  }

  public LocaleIdTokenizer(CharSequence localeIdBuffer) {
    mLocaleIdBuffer = localeIdBuffer;
  }

  public boolean hasMoreSubtags() {
    return mLocaleIdBuffer.length() > 0 && mCurrentSubtagEnd < mLocaleIdBuffer.length() - 1;
  }

  public LocaleIdSubtag nextSubtag() throws LocaleIdSubtagIterationFailed {

    if (!hasMoreSubtags()) {
      throw new LocaleIdSubtagIterationFailed();
    }

    // Jump over the separator if not the first subtag.
    if (mCurrentSubtagEnd >= mCurrentSubtagStart) {
      if (!isSubtagSeparator(mLocaleIdBuffer.charAt(mCurrentSubtagEnd + 1))) {
        throw new LocaleIdSubtagIterationFailed();
      }

      // If there is not tokens after the separator.
      if (mCurrentSubtagEnd + 2 == mLocaleIdBuffer.length()) {
        throw new LocaleIdSubtagIterationFailed();
      }

      mCurrentSubtagStart = mCurrentSubtagEnd + 2;
    }

    for (mCurrentSubtagEnd = mCurrentSubtagStart;
        mCurrentSubtagEnd < mLocaleIdBuffer.length()
            && !isSubtagSeparator(mLocaleIdBuffer.charAt(mCurrentSubtagEnd));
        mCurrentSubtagEnd++) ;

    if (mCurrentSubtagEnd > mCurrentSubtagStart) {
      mCurrentSubtagEnd--;
      return new LocaleIdSubtag(mLocaleIdBuffer, mCurrentSubtagStart, mCurrentSubtagEnd);
    } else {
      throw new LocaleIdSubtagIterationFailed();
    }
  }
}

public class LocaleIdentifier {

  private static void addVariantSubtag(
      String variantSubtag,
      ParsedLocaleIdentifier.ParsedLanguageIdentifier parsedLanguageIdentifier)
      throws JSRangeErrorException {
    if (parsedLanguageIdentifier.variantSubtagList != null) {
      int position =
          Collections.binarySearch(parsedLanguageIdentifier.variantSubtagList, variantSubtag);
      if (position < 0) {
        // parsedLocaleIdentifier.languageIdentifier.variantSubtagList.ensureCapacity(variantSubtagList.size() + 1); // todo:: check whether this is needed ?
        parsedLanguageIdentifier.variantSubtagList.add(-1 * position - 1, variantSubtag);
      } else {
        throw new JSRangeErrorException("Duplicate variant");
      }
    } else {
      parsedLanguageIdentifier.variantSubtagList = new ArrayList<>();
      parsedLanguageIdentifier.variantSubtagList.add(variantSubtag);
    }
  }

  public static void replaceLanguageSubtagIfNeeded(
      StringBuffer languageSubtagBuffer,
      StringBuffer scriptSubtagBuffer,
      StringBuffer regionSubtagBuffer) {

    // If mappings are not available .. return early.
    if (LanguageTagsGenerated.languageAliasKeys2 == null) return;

    String[] languageAliasKeys = null, languageAliasReplacements = null;
    String[] complexLanguageAliasKeys = null,
        complexLanguageAliasReplacementsLanguage = null,
        complexLanguageAliasReplacementsScript = null,
        complexLanguageAliasReplacementsRegion = null;

    if (languageSubtagBuffer.length() == 2) {
      languageAliasKeys = LanguageTagsGenerated.languageAliasKeys2;
      languageAliasReplacements = LanguageTagsGenerated.languageAliasReplacements2;

      complexLanguageAliasKeys = LanguageTagsGenerated.complexLanguageAliasKeys2;
      complexLanguageAliasReplacementsLanguage =
          LanguageTagsGenerated.complexLanguageAliasReplacementsLanguage2;
      complexLanguageAliasReplacementsScript =
          LanguageTagsGenerated.complexLanguageAliasReplacementsScript2;
      complexLanguageAliasReplacementsRegion =
          LanguageTagsGenerated.complexLanguageAliasReplacementsRegion2;
    } else {
      languageAliasKeys = LanguageTagsGenerated.languageAliasKeys3;
      languageAliasReplacements = LanguageTagsGenerated.languageAliasReplacements3;

      complexLanguageAliasKeys = LanguageTagsGenerated.complexLanguageAliasKeys3;
      complexLanguageAliasReplacementsLanguage =
          LanguageTagsGenerated.complexLanguageAliasReplacementsLanguage3;
      complexLanguageAliasReplacementsScript =
          LanguageTagsGenerated.complexLanguageAliasReplacementsScript3;
      complexLanguageAliasReplacementsRegion =
          LanguageTagsGenerated.complexLanguageAliasReplacementsRegion3;
    }

    int found = java.util.Arrays.binarySearch(languageAliasKeys, languageSubtagBuffer.toString());
    if (found >= 0) {
      languageSubtagBuffer.delete(0, languageSubtagBuffer.length());
      languageSubtagBuffer.append(languageAliasReplacements[found]);
    } else {
      // Try complex replacement
      found =
          java.util.Arrays.binarySearch(complexLanguageAliasKeys, languageSubtagBuffer.toString());
      if (found >= 0) {
        String languageSubtagReplacement = complexLanguageAliasReplacementsLanguage[found];
        String scriptSubtagReplacement = complexLanguageAliasReplacementsScript[found];
        String regionSubtagReplacement = complexLanguageAliasReplacementsRegion[found];

        assert (languageSubtagReplacement != null && languageSubtagReplacement.length() > 0);
        // Overwrite languageSubtag buffer
        languageSubtagBuffer.delete(0, languageSubtagBuffer.length());
        languageSubtagBuffer.append(languageSubtagReplacement);

        if (scriptSubtagBuffer.length() == 0 && scriptSubtagReplacement != null) {
          scriptSubtagBuffer.append(scriptSubtagReplacement);
        }

        if (regionSubtagBuffer.length() == 0 && regionSubtagReplacement != null) {
          regionSubtagBuffer.append(regionSubtagReplacement);
        }
      }
    }
  }

  public static String replaceRegionSubtagIfNeeded(StringBuffer regionSubtag) {
    if (LanguageTagsGenerated.regionAliasKeys2 == null) return regionSubtag.toString();

    if (regionSubtag.length() == 2) {
      int found =
          java.util.Arrays.binarySearch(
              LanguageTagsGenerated.regionAliasKeys2, regionSubtag.toString());
      if (found >= 0) {
        return LanguageTagsGenerated.regionAliasReplacements2[found];
      } else {
        return regionSubtag.toString();
      }
    } else {
      int found =
          java.util.Arrays.binarySearch(
              LanguageTagsGenerated.regionAliasKeys3, regionSubtag.toString());
      if (found >= 0) {
        return LanguageTagsGenerated.regionAliasReplacements3[found];
      } else {
        return regionSubtag.toString();
      }
    }

    // Note: We don't do complex region replacement as it is expensive to do.
  }

  static String canonicalizeLocaleId(String inLocaleId) throws JSRangeErrorException {

    // A quick comparative study with other implementations.
    // The canonical way to canonicalize a localeId string is to roundtrip it through the
    // icu::Locale object using forLanguageTag/toLanguageTag functions.
    // V8 relies on icu4c implementation of the above functions, but augmented with private tables
    // and code for handling special cases and error scenarios
    // https://github.com/v8/v8/blob/4b9b23521e6fd42373ebbcb20ebe03bf445494f9/src/objects/intl-objects.cc
    // Also, note that Chromium applies a few patches
    // (https://chromium.googlesource.com/chromium/deps/icu/+/refs/heads/master/patches/) over icu,
    // which may also result in subtle behaviour differences.
    //
    // Firefox doesn't seem to rely on ICU much but custom implemented most code and tables
    // https://dxr.mozilla.org/mozilla-central/rev/c68fe15a81fc2dc9fc5765f3be2573519c09b6c1/js/src/builtin/intl/Locale.cpp#1233
    // Firefox has intentionally reimplemented them for performance as documented here:
    // https://dxr.mozilla.org/mozilla-central/rev/c68fe15a81fc2dc9fc5765f3be2573519c09b6c1/js/src/builtin/intl/LanguageTag.cpp#1034
    //
    // Chakra official releases links to Windows.Globalization libraries available in Windows,
    // But has an ICU variant which roundtrips the localId through icu::Locale as mentioned before
    // with no other custom code around.
    //
    // Note:: icu4j is not a JNI wrapper around icu4c, but a reimplementation using Java.
    // Even though they have similar APIs, there are subtle deviations for e.g. in error handling.
    // Unlike the icu4c equivalents, the forLanguageTag in icu4j doesn't report any errors while
    // parsing ..
    // For e.g. icu4c identifies bogus locids.. and report failure when part of the loclid can't be
    // parsed.
    // (https://github.com/unicode-org/icu/blob/79fac501010d63231c258dc0d4fb9a9e87ddb8d8/icu4c/source/common/locid.cpp#L816)
    // This results in our implementation a bit more leniant (i.e. not throwing RangeError for
    // certain invalid inputs) campared to V8/Chakra
    // Both icu4c and icu4j implementations use private tables and mappings embedded in code for
    // special cases such as deprecated and grandfathered  language code.
    // icu4c:
    // https://github.com/unicode-org/icu/blob/9219c6ae038a3556dffca880e93d2f2ca00e685a/icu4c/source/common/uloc_tag.cpp#L103
    // icu4j:
    // https://github.com/unicode-org/icu/blob/79fac501010d63231c258dc0d4fb9a9e87ddb8d8/icu4j/main/classes/core/src/com/ibm/icu/impl/locale/LanguageTag.java#L43
    // Android-icu4j:
    // https://android.googlesource.com/platform/external/icu/+/refs/heads/master/android_icu4j/
    //
    // Clearly icu4c implementation has a few more private tables implementated, for e.g. the
    // deprecated languages and regions. This results in subtle behavioural differences between our
    // implemenation and say, V8.
    //
    // As of now, Firefox seems to be by far the most compliant engine out there.
    //
    // Our current implementation is leveraging icu4j available with Android platform, but
    // augmented with our own structure validation and some table lookups (grandfathered tags,
    // simple language and region replacements etc.).
    //
    // Ref:
    // https://unicode-org.github.io/icu-docs/apidoc/released/icu4j/com/ibm/icu/util/ULocale.html#forLanguageTag-java.lang.String-
    // Ref:
    // https://unicode-org.github.io/icu-docs/apidoc/released/icu4c/classicu_1_1Locale.html#af76028775e37fd75a30209aaede551e2
    // Ref: https://developer.android.com/reference/android/icu/util/ULocale.Builder

    // We could have a much simpler implementation completely relying on icu4j. But that had the
    // following deficiencies,
    // 1. icu4j roundtripping with forLanguageTag constructor does almost no error validation. None
    // of the negative test cases passes and many structurally invalid tags passes through.
    // It essentially forces us to do structural validation ourselves.
    // 2. Unicode CLDR has various mapping which needs to be applied prior to canonicalization.
    //    icu implementations could either lookup those mappings in CLDR (not advisable) or keep
    // those mapping privately in code. icu4c and icu4j does keep private mapping but to different
    // degrees,
    //    which results in subtle behaviour differences, even between different versions of ICU.
    // 3. forLanguageTag constructor internally parses the tag again, which is wasteful as we've
    // already parsed the tag for structure validation.
    //    ULocale.Builder approach comes to rescue in icu4j as it allows us to create ULocale object
    // using subtags, which we've got while parsing.
    // 4. But, ULocale.Builder code path lacks some tag mappings, for e.g. grandfathered locale id,
    // which forced us to add more private tables and mapping.
    //
    // Essentially, we ended up with slightly more complicated and less space efficient (due to
    // added tables, but mostly static, not runtime allocations) traded against correctlness and
    // predictability.

    return LocaleObject.createFromLocaleId(inLocaleId).toCanonicalTag();
  }

  // unicode_locale_extensions = sep [uU]
  // ((sep keyword)+
  // |(sep attribute)+ (sep keyword)*) ;
  //
  // keyword = = key (sep type)? ;
  //
  // key = = alphanum alpha ;
  //
  // type = = alphanum{3,8}
  //  (sep alphanum{3,8})* ;
  //
  // attribute = alphanum{3,8} ;
  static void parseUnicodeExtensions(
      CharSequence inLocaleId,
      LocaleIdTokenizer localeIdTokenizer,
      ParsedLocaleIdentifier parsedLocaleIdentifier)
      throws JSRangeErrorException, LocaleIdTokenizer.LocaleIdSubtagIterationFailed {
    if (!localeIdTokenizer.hasMoreSubtags())
      throw new JSRangeErrorException("Extension sequence expected.");

    LocaleIdTokenizer.LocaleIdSubtag nextSubtag = localeIdTokenizer.nextSubtag();

    if (parsedLocaleIdentifier.unicodeExtensionAttributes != null
        || parsedLocaleIdentifier.unicodeExtensionKeywords != null) {
      throw new JSRangeErrorException(
          String.format("Duplicate unicode extension sequence in [%s]", inLocaleId));
    }

    // Read out all attributes first ..
    while (nextSubtag.isUnicodeExtensionAttribute()) {
      if (parsedLocaleIdentifier.unicodeExtensionAttributes == null)
        parsedLocaleIdentifier.unicodeExtensionAttributes = new ArrayList<>();

      parsedLocaleIdentifier.unicodeExtensionAttributes.add(nextSubtag.toString());

      if (!localeIdTokenizer.hasMoreSubtags()) return;

      nextSubtag = localeIdTokenizer.nextSubtag();
    }

    if (nextSubtag.isUnicodeExtensionKey()) {

      if (parsedLocaleIdentifier.unicodeExtensionKeywords == null) {
        parsedLocaleIdentifier.unicodeExtensionKeywords = new TreeMap<>();
      }

      do {
        String key = nextSubtag.toString();
        ArrayList<String> extensionKeyTypes = new ArrayList<>();
        parsedLocaleIdentifier.unicodeExtensionKeywords.put(key, extensionKeyTypes);

        // Read out all key types
        if (!localeIdTokenizer.hasMoreSubtags()) {
          return;
        } else {
          nextSubtag = localeIdTokenizer.nextSubtag();

          while (nextSubtag.isUnicodeExtensionKeyTypeItem()) {
            extensionKeyTypes.add(nextSubtag.toString());

            if (!localeIdTokenizer.hasMoreSubtags()) return;

            nextSubtag = localeIdTokenizer.nextSubtag();
          }
        }
      } while (nextSubtag.isUnicodeExtensionKey());
    }

    if (nextSubtag.isExtensionSingleton()) {
      parseExtensions(inLocaleId, nextSubtag, localeIdTokenizer, parsedLocaleIdentifier);
      return;
    } else {
      throw new JSRangeErrorException("Malformed sequence expected.");
    }
  }

  static void parseTransformedExtensionFields(
      CharSequence inLocaleId,
      LocaleIdTokenizer localeIdTokenizer,
      LocaleIdTokenizer.LocaleIdSubtag nextSubtag,
      ParsedLocaleIdentifier parsedLocaleIdentifier)
      throws JSRangeErrorException, LocaleIdTokenizer.LocaleIdSubtagIterationFailed {

    if (nextSubtag.isTranformedExtensionTKey()) {

      if (parsedLocaleIdentifier.transformedExtensionFields != null) {
        throw new JSRangeErrorException(
            String.format("Duplicate transformed extension sequence in [%s]", inLocaleId));
      }

      if (parsedLocaleIdentifier.transformedExtensionFields == null) {
        parsedLocaleIdentifier.transformedExtensionFields = new TreeMap<>();
      }

      do {
        String tkey = nextSubtag.toString();
        ArrayList<String> tValues = new ArrayList<>();
        parsedLocaleIdentifier.transformedExtensionFields.put(tkey, tValues);

        // Read out all key types
        if (localeIdTokenizer.hasMoreSubtags()) {
          nextSubtag = localeIdTokenizer.nextSubtag();

          while (nextSubtag.isTranformedExtensionTValueItem()) {
            tValues.add(nextSubtag.toString());

            if (!localeIdTokenizer.hasMoreSubtags()) return;

            nextSubtag = localeIdTokenizer.nextSubtag();
          }

        } else {
          throw new JSRangeErrorException(
              String.format("Malformated transformed key in : %s", inLocaleId));
        }

      } while (nextSubtag.isTranformedExtensionTKey());
    }

    if (nextSubtag.isExtensionSingleton()) {
      parseExtensions(inLocaleId, nextSubtag, localeIdTokenizer, parsedLocaleIdentifier);
      return;
    } else {
      throw new JSRangeErrorException("Malformed extension sequence.");
    }
  }

  // transformed_extensions= sep [tT]
  // ((sep tlang (sep tfield)*)
  // | (sep tfield)+) ;
  //
  // tlang = unicode_language_subtag
  //  (sep unicode_script_subtag)?
  //  (sep unicode_region_subtag)?
  //  (sep unicode_variant_subtag)* ;
  //
  //  tfield = tkey tvalue;
  //
  // tkey =  	= alpha digit ;
  //
  // tvalue = (sep alphanum{3,8})+ ;
  static void parseTransformedExtensions(
      CharSequence inLocaleId,
      LocaleIdTokenizer localeIdTokenizer,
      ParsedLocaleIdentifier parsedLocaleIdentifier)
      throws JSRangeErrorException, LocaleIdTokenizer.LocaleIdSubtagIterationFailed {

    if (!localeIdTokenizer.hasMoreSubtags())
      throw new JSRangeErrorException("Extension sequence expected.");

    LocaleIdTokenizer.LocaleIdSubtag nextSubtag = localeIdTokenizer.nextSubtag();

    if (nextSubtag.isUnicodeLanguageSubtag()) {
      parseLanguageId(inLocaleId, localeIdTokenizer, nextSubtag, true, parsedLocaleIdentifier);
      // nextSubtag = localeIdTokenizer.currentSubtag();
    } else if (nextSubtag.isTranformedExtensionTKey()) {
      parseTransformedExtensionFields(
          inLocaleId, localeIdTokenizer, nextSubtag, parsedLocaleIdentifier);
    } else {
      throw new JSRangeErrorException(
          String.format(
              "Unexpected token [%s] in transformed extension sequence [%s]",
              nextSubtag.toString(), inLocaleId));
    }
  }

  static void parsePrivateUseExtensions(
      CharSequence inLocaleId,
      LocaleIdTokenizer localeIdTokenizer,
      ParsedLocaleIdentifier parsedLocaleIdentifier)
      throws JSRangeErrorException, LocaleIdTokenizer.LocaleIdSubtagIterationFailed {

    if (!localeIdTokenizer.hasMoreSubtags())
      throw new JSRangeErrorException("Extension sequence expected.");

    LocaleIdTokenizer.LocaleIdSubtag nextSubtag = localeIdTokenizer.nextSubtag();

    if (parsedLocaleIdentifier.puExtensions == null) {
      parsedLocaleIdentifier.puExtensions = new ArrayList<>();
    }

    while (nextSubtag.isPrivateUseExtension()) {

      parsedLocaleIdentifier.puExtensions.add(nextSubtag.toString());

      if (!localeIdTokenizer.hasMoreSubtags()) return;

      nextSubtag = localeIdTokenizer.nextSubtag();
    }

    throw new JSRangeErrorException("Tokens are not expected after pu extension.");
  }

  static void parseOtherExtensions(
      CharSequence inLocaleId,
      LocaleIdTokenizer localeIdTokenizer,
      ParsedLocaleIdentifier parsedLocaleIdentifier,
      char singleton)
      throws JSRangeErrorException, LocaleIdTokenizer.LocaleIdSubtagIterationFailed {

    if (!localeIdTokenizer.hasMoreSubtags())
      throw new JSRangeErrorException("Extension sequence expected.");

    LocaleIdTokenizer.LocaleIdSubtag nextSubtag = localeIdTokenizer.nextSubtag();

    if (parsedLocaleIdentifier.otherExtensionsMap == null) {
      parsedLocaleIdentifier.otherExtensionsMap = new TreeMap<>();
    }

    ArrayList<String> otherExtensions = new ArrayList<>();
    parsedLocaleIdentifier.otherExtensionsMap.put(new Character(singleton), otherExtensions);

    while (nextSubtag.isOtherExtension()) {

      otherExtensions.add(nextSubtag.toString());

      if (!localeIdTokenizer.hasMoreSubtags()) return;

      nextSubtag = localeIdTokenizer.nextSubtag();
    }

    if (nextSubtag.isExtensionSingleton()) {
      parseExtensions(inLocaleId, nextSubtag, localeIdTokenizer, parsedLocaleIdentifier);
      return;
    } else {
      throw new JSRangeErrorException("Malformed sequence expected.");
    }
  }

  static void parseExtensions(
      CharSequence inLocaleId,
      LocaleIdTokenizer.LocaleIdSubtag singletonSubtag,
      LocaleIdTokenizer localeIdTokenizer,
      ParsedLocaleIdentifier parsedLocaleIdentifier)
      throws JSRangeErrorException, LocaleIdTokenizer.LocaleIdSubtagIterationFailed {

    if (!localeIdTokenizer.hasMoreSubtags())
      throw new JSRangeErrorException("Extension sequence expected.");

    char singleton = singletonSubtag.toString().charAt(0);

    if (singleton == 'u') {
      parseUnicodeExtensions(inLocaleId, localeIdTokenizer, parsedLocaleIdentifier);
    } else if (singleton == 't') {
      parseTransformedExtensions(inLocaleId, localeIdTokenizer, parsedLocaleIdentifier);
    } else if (singleton == 'x') {
      parsePrivateUseExtensions(inLocaleId, localeIdTokenizer, parsedLocaleIdentifier);
    } else {
      parseOtherExtensions(inLocaleId, localeIdTokenizer, parsedLocaleIdentifier, singleton);
    }
  }

  static boolean handleExtensions(
      CharSequence inLocaleId,
      LocaleIdTokenizer localeIdTokenizer,
      LocaleIdTokenizer.LocaleIdSubtag nextSubtag,
      boolean transformedExtMode,
      ParsedLocaleIdentifier parsedLocaleIdentifier)
      throws JSRangeErrorException, LocaleIdTokenizer.LocaleIdSubtagIterationFailed {

    if (transformedExtMode && nextSubtag.isTranformedExtensionTKey()) {
      parseTransformedExtensionFields(
          inLocaleId, localeIdTokenizer, nextSubtag, parsedLocaleIdentifier);
      return true;
    }

    // https://en.wikipedia.org/wiki/IETF_language_tag#Extensions
    if (nextSubtag.isExtensionSingleton()) {
      if (!transformedExtMode) {
        parseExtensions(inLocaleId, nextSubtag, localeIdTokenizer, parsedLocaleIdentifier);
        return true;
      } else {
        throw new JSRangeErrorException(
            String.format(
                "Extension singletons in transformed extension language tag: %s", inLocaleId));
      }
    }

    return false;
  }

  static void parseLanguageId(
      CharSequence inLocaleId,
      LocaleIdTokenizer localeIdTokenizer,
      LocaleIdTokenizer.LocaleIdSubtag nextSubtag,
      boolean transformedExtMode,
      ParsedLocaleIdentifier parsedLocaleIdentifier)
      throws JSRangeErrorException, LocaleIdTokenizer.LocaleIdSubtagIterationFailed {

    ParsedLocaleIdentifier.ParsedLanguageIdentifier parsedLanguageIdentifier =
        new ParsedLocaleIdentifier.ParsedLanguageIdentifier();

    if (transformedExtMode)
      parsedLocaleIdentifier.transformedLanguageIdentifier = parsedLanguageIdentifier;
    else parsedLocaleIdentifier.languageIdentifier = parsedLanguageIdentifier;

    try {
      // We expect at least one subtag.
      // We assume the languageId starts with language subtag, but LDML allows languageId starting
      // with script subtag: https://unicode.org/reports/tr35/#BCP_47_Conformance
      if (!nextSubtag.isUnicodeLanguageSubtag())
        throw new JSRangeErrorException(
            String.format("Language subtag expected at %s: %s", nextSubtag.toString(), inLocaleId));

      parsedLanguageIdentifier.languageSubtag = nextSubtag.toLowerString();

      if (!localeIdTokenizer.hasMoreSubtags()) {
        return;
      }

      nextSubtag = localeIdTokenizer.nextSubtag();

      // Note: According to BCP47, the language subtag can be followed by extlang subtags which are
      // sequence of upto 3 3-letter alphabetic codes.
      // But unicode LDML spec disallows it: https://unicode.org/reports/tr35/#BCP_47_Conformance

      if (handleExtensions(
          inLocaleId, localeIdTokenizer, nextSubtag, transformedExtMode, parsedLocaleIdentifier))
        return;

      if (nextSubtag.isUnicodeScriptSubtag()) {
        parsedLanguageIdentifier.scriptSubtag = nextSubtag.toTitleString();

        if (!localeIdTokenizer.hasMoreSubtags()) {
          return;
        }

        nextSubtag = localeIdTokenizer.nextSubtag();
      }

      if (nextSubtag.isUnicodeRegionSubtag()) {
        parsedLanguageIdentifier.regionSubtag = nextSubtag.toUpperString();

        if (!localeIdTokenizer.hasMoreSubtags()) {
          return;
        }
        nextSubtag = localeIdTokenizer.nextSubtag();
      }

      do {
        if (handleExtensions(
            inLocaleId, localeIdTokenizer, nextSubtag, transformedExtMode, parsedLocaleIdentifier))
          return;

        if (!nextSubtag.isUnicodeVariantSubtag())
          throw new JSRangeErrorException(
              String.format(
                  "Unknown token [%s] found in locale id: %s", nextSubtag.toString(), inLocaleId));
        else {
          addVariantSubtag(nextSubtag.toString(), parsedLanguageIdentifier);
        }

        if (!localeIdTokenizer.hasMoreSubtags()) {
          return;
        }
        nextSubtag = localeIdTokenizer.nextSubtag();

      } while (true);

    } catch (LocaleIdTokenizer.LocaleIdSubtagIterationFailed localeIdSubtagIterationFailed) {
      throw new JSRangeErrorException(
          String.format("Locale Identifier subtag iteration failed: %s", inLocaleId));
    }
  }

  static ParsedLocaleIdentifier parseLocaleId(
      String inLocaleId, LocaleIdTokenizer localeIdTokenizer) throws JSRangeErrorException {
    ParsedLocaleIdentifier parsedLocaleIdentifier = new ParsedLocaleIdentifier();

    try {

      if (!localeIdTokenizer.hasMoreSubtags())
        throw new JSRangeErrorException(String.format("Language subtag not found: %s", inLocaleId));

      LocaleIdTokenizer.LocaleIdSubtag nextSubtag = localeIdTokenizer.nextSubtag();

      parseLanguageId(inLocaleId, localeIdTokenizer, nextSubtag, false, parsedLocaleIdentifier);

      return parsedLocaleIdentifier;

    } catch (LocaleIdTokenizer.LocaleIdSubtagIterationFailed localeIdSubtagIterationFailed) {
      throw new JSRangeErrorException(
          String.format("Locale Identifier subtag iteration failed: %s", inLocaleId));
    }
  }

  // This method parses a given locale id to constituent subtags.
  // Note that the extension sequence is not yet parsed, but the whole extension sequence is
  // returned as a buffer.
  // https://tc39.es/ecma402/#sec-isstructurallyvalidlanguagetag
  // https://unicode.org/reports/tr35/#Unicode_Language_and_Locale_Identifiers
  static ParsedLocaleIdentifier parseLocaleId(String inLocaleId) throws JSRangeErrorException {

    // Handle grandfathered locales ..
    if (LanguageTagsGenerated.regularGrandfatheredKeys != null) {
      int grandfatheredIndex =
          java.util.Arrays.binarySearch(
              LanguageTagsGenerated.regularGrandfatheredKeys, inLocaleId.toString());
      if (grandfatheredIndex >= 0) {
        inLocaleId = LanguageTagsGenerated.regularGrandfatheredReplacements[grandfatheredIndex];
      }
    }

    // Normalize input to lower case.
    inLocaleId = inLocaleId.toLowerCase();

    LocaleIdTokenizer localeIdTokenizer = new LocaleIdTokenizer(inLocaleId);
    return parseLocaleId(inLocaleId, localeIdTokenizer);
  }
}
