1// Copyright 2013 The Go Authors. All rights reserved. 2// Use of this source code is governed by a BSD-style 3// license that can be found in the LICENSE file. 4 5package language 6 7import "errors" 8 9// A MatchOption configures a Matcher. 10type MatchOption func(*matcher) 11 12// PreferSameScript will, in the absence of a match, result in the first 13// preferred tag with the same script as a supported tag to match this supported 14// tag. The default is currently true, but this may change in the future. 15func PreferSameScript(preferSame bool) MatchOption { 16 return func(m *matcher) { m.preferSameScript = preferSame } 17} 18 19// TODO(v1.0.0): consider making Matcher a concrete type, instead of interface. 20// There doesn't seem to be too much need for multiple types. 21// Making it a concrete type allows MatchStrings to be a method, which will 22// improve its discoverability. 23 24// MatchStrings parses and matches the given strings until one of them matches 25// the language in the Matcher. A string may be an Accept-Language header as 26// handled by ParseAcceptLanguage. The default language is returned if no 27// other language matched. 28func MatchStrings(m Matcher, lang ...string) (tag Tag, index int) { 29 for _, accept := range lang { 30 desired, _, err := ParseAcceptLanguage(accept) 31 if err != nil { 32 continue 33 } 34 if tag, index, conf := m.Match(desired...); conf != No { 35 return tag, index 36 } 37 } 38 tag, index, _ = m.Match() 39 return 40} 41 42// Matcher is the interface that wraps the Match method. 43// 44// Match returns the best match for any of the given tags, along with 45// a unique index associated with the returned tag and a confidence 46// score. 47type Matcher interface { 48 Match(t ...Tag) (tag Tag, index int, c Confidence) 49} 50 51// Comprehends reports the confidence score for a speaker of a given language 52// to being able to comprehend the written form of an alternative language. 53func Comprehends(speaker, alternative Tag) Confidence { 54 _, _, c := NewMatcher([]Tag{alternative}).Match(speaker) 55 return c 56} 57 58// NewMatcher returns a Matcher that matches an ordered list of preferred tags 59// against a list of supported tags based on written intelligibility, closeness 60// of dialect, equivalence of subtags and various other rules. It is initialized 61// with the list of supported tags. The first element is used as the default 62// value in case no match is found. 63// 64// Its Match method matches the first of the given Tags to reach a certain 65// confidence threshold. The tags passed to Match should therefore be specified 66// in order of preference. Extensions are ignored for matching. 67// 68// The index returned by the Match method corresponds to the index of the 69// matched tag in t, but is augmented with the Unicode extension ('u')of the 70// corresponding preferred tag. This allows user locale options to be passed 71// transparently. 72func NewMatcher(t []Tag, options ...MatchOption) Matcher { 73 return newMatcher(t, options) 74} 75 76func (m *matcher) Match(want ...Tag) (t Tag, index int, c Confidence) { 77 match, w, c := m.getBest(want...) 78 if match != nil { 79 t, index = match.tag, match.index 80 } else { 81 // TODO: this should be an option 82 t = m.default_.tag 83 if m.preferSameScript { 84 outer: 85 for _, w := range want { 86 script, _ := w.Script() 87 if script.scriptID == 0 { 88 // Don't do anything if there is no script, such as with 89 // private subtags. 90 continue 91 } 92 for i, h := range m.supported { 93 if script.scriptID == h.maxScript { 94 t, index = h.tag, i 95 break outer 96 } 97 } 98 } 99 } 100 // TODO: select first language tag based on script. 101 } 102 if w.region != 0 && t.region != 0 && t.region.contains(w.region) { 103 t, _ = Raw.Compose(t, Region{w.region}) 104 } 105 // Copy options from the user-provided tag into the result tag. This is hard 106 // to do after the fact, so we do it here. 107 // TODO: add in alternative variants to -u-va-. 108 // TODO: add preferred region to -u-rg-. 109 if e := w.Extensions(); len(e) > 0 { 110 t, _ = Raw.Compose(t, e) 111 } 112 return t, index, c 113} 114 115type scriptRegionFlags uint8 116 117const ( 118 isList = 1 << iota 119 scriptInFrom 120 regionInFrom 121) 122 123func (t *Tag) setUndefinedLang(id langID) { 124 if t.lang == 0 { 125 t.lang = id 126 } 127} 128 129func (t *Tag) setUndefinedScript(id scriptID) { 130 if t.script == 0 { 131 t.script = id 132 } 133} 134 135func (t *Tag) setUndefinedRegion(id regionID) { 136 if t.region == 0 || t.region.contains(id) { 137 t.region = id 138 } 139} 140 141// ErrMissingLikelyTagsData indicates no information was available 142// to compute likely values of missing tags. 143var ErrMissingLikelyTagsData = errors.New("missing likely tags data") 144 145// addLikelySubtags sets subtags to their most likely value, given the locale. 146// In most cases this means setting fields for unknown values, but in some 147// cases it may alter a value. It returns an ErrMissingLikelyTagsData error 148// if the given locale cannot be expanded. 149func (t Tag) addLikelySubtags() (Tag, error) { 150 id, err := addTags(t) 151 if err != nil { 152 return t, err 153 } else if id.equalTags(t) { 154 return t, nil 155 } 156 id.remakeString() 157 return id, nil 158} 159 160// specializeRegion attempts to specialize a group region. 161func specializeRegion(t *Tag) bool { 162 if i := regionInclusion[t.region]; i < nRegionGroups { 163 x := likelyRegionGroup[i] 164 if langID(x.lang) == t.lang && scriptID(x.script) == t.script { 165 t.region = regionID(x.region) 166 } 167 return true 168 } 169 return false 170} 171 172func addTags(t Tag) (Tag, error) { 173 // We leave private use identifiers alone. 174 if t.private() { 175 return t, nil 176 } 177 if t.script != 0 && t.region != 0 { 178 if t.lang != 0 { 179 // already fully specified 180 specializeRegion(&t) 181 return t, nil 182 } 183 // Search matches for und-script-region. Note that for these cases 184 // region will never be a group so there is no need to check for this. 185 list := likelyRegion[t.region : t.region+1] 186 if x := list[0]; x.flags&isList != 0 { 187 list = likelyRegionList[x.lang : x.lang+uint16(x.script)] 188 } 189 for _, x := range list { 190 // Deviating from the spec. See match_test.go for details. 191 if scriptID(x.script) == t.script { 192 t.setUndefinedLang(langID(x.lang)) 193 return t, nil 194 } 195 } 196 } 197 if t.lang != 0 { 198 // Search matches for lang-script and lang-region, where lang != und. 199 if t.lang < langNoIndexOffset { 200 x := likelyLang[t.lang] 201 if x.flags&isList != 0 { 202 list := likelyLangList[x.region : x.region+uint16(x.script)] 203 if t.script != 0 { 204 for _, x := range list { 205 if scriptID(x.script) == t.script && x.flags&scriptInFrom != 0 { 206 t.setUndefinedRegion(regionID(x.region)) 207 return t, nil 208 } 209 } 210 } else if t.region != 0 { 211 count := 0 212 goodScript := true 213 tt := t 214 for _, x := range list { 215 // We visit all entries for which the script was not 216 // defined, including the ones where the region was not 217 // defined. This allows for proper disambiguation within 218 // regions. 219 if x.flags&scriptInFrom == 0 && t.region.contains(regionID(x.region)) { 220 tt.region = regionID(x.region) 221 tt.setUndefinedScript(scriptID(x.script)) 222 goodScript = goodScript && tt.script == scriptID(x.script) 223 count++ 224 } 225 } 226 if count == 1 { 227 return tt, nil 228 } 229 // Even if we fail to find a unique Region, we might have 230 // an unambiguous script. 231 if goodScript { 232 t.script = tt.script 233 } 234 } 235 } 236 } 237 } else { 238 // Search matches for und-script. 239 if t.script != 0 { 240 x := likelyScript[t.script] 241 if x.region != 0 { 242 t.setUndefinedRegion(regionID(x.region)) 243 t.setUndefinedLang(langID(x.lang)) 244 return t, nil 245 } 246 } 247 // Search matches for und-region. If und-script-region exists, it would 248 // have been found earlier. 249 if t.region != 0 { 250 if i := regionInclusion[t.region]; i < nRegionGroups { 251 x := likelyRegionGroup[i] 252 if x.region != 0 { 253 t.setUndefinedLang(langID(x.lang)) 254 t.setUndefinedScript(scriptID(x.script)) 255 t.region = regionID(x.region) 256 } 257 } else { 258 x := likelyRegion[t.region] 259 if x.flags&isList != 0 { 260 x = likelyRegionList[x.lang] 261 } 262 if x.script != 0 && x.flags != scriptInFrom { 263 t.setUndefinedLang(langID(x.lang)) 264 t.setUndefinedScript(scriptID(x.script)) 265 return t, nil 266 } 267 } 268 } 269 } 270 271 // Search matches for lang. 272 if t.lang < langNoIndexOffset { 273 x := likelyLang[t.lang] 274 if x.flags&isList != 0 { 275 x = likelyLangList[x.region] 276 } 277 if x.region != 0 { 278 t.setUndefinedScript(scriptID(x.script)) 279 t.setUndefinedRegion(regionID(x.region)) 280 } 281 specializeRegion(&t) 282 if t.lang == 0 { 283 t.lang = _en // default language 284 } 285 return t, nil 286 } 287 return t, ErrMissingLikelyTagsData 288} 289 290func (t *Tag) setTagsFrom(id Tag) { 291 t.lang = id.lang 292 t.script = id.script 293 t.region = id.region 294} 295 296// minimize removes the region or script subtags from t such that 297// t.addLikelySubtags() == t.minimize().addLikelySubtags(). 298func (t Tag) minimize() (Tag, error) { 299 t, err := minimizeTags(t) 300 if err != nil { 301 return t, err 302 } 303 t.remakeString() 304 return t, nil 305} 306 307// minimizeTags mimics the behavior of the ICU 51 C implementation. 308func minimizeTags(t Tag) (Tag, error) { 309 if t.equalTags(und) { 310 return t, nil 311 } 312 max, err := addTags(t) 313 if err != nil { 314 return t, err 315 } 316 for _, id := range [...]Tag{ 317 {lang: t.lang}, 318 {lang: t.lang, region: t.region}, 319 {lang: t.lang, script: t.script}, 320 } { 321 if x, err := addTags(id); err == nil && max.equalTags(x) { 322 t.setTagsFrom(id) 323 break 324 } 325 } 326 return t, nil 327} 328 329// Tag Matching 330// CLDR defines an algorithm for finding the best match between two sets of language 331// tags. The basic algorithm defines how to score a possible match and then find 332// the match with the best score 333// (see http://www.unicode.org/reports/tr35/#LanguageMatching). 334// Using scoring has several disadvantages. The scoring obfuscates the importance of 335// the various factors considered, making the algorithm harder to understand. Using 336// scoring also requires the full score to be computed for each pair of tags. 337// 338// We will use a different algorithm which aims to have the following properties: 339// - clarity on the precedence of the various selection factors, and 340// - improved performance by allowing early termination of a comparison. 341// 342// Matching algorithm (overview) 343// Input: 344// - supported: a set of supported tags 345// - default: the default tag to return in case there is no match 346// - desired: list of desired tags, ordered by preference, starting with 347// the most-preferred. 348// 349// Algorithm: 350// 1) Set the best match to the lowest confidence level 351// 2) For each tag in "desired": 352// a) For each tag in "supported": 353// 1) compute the match between the two tags. 354// 2) if the match is better than the previous best match, replace it 355// with the new match. (see next section) 356// b) if the current best match is Exact and pin is true the result will be 357// frozen to the language found thusfar, although better matches may 358// still be found for the same language. 359// 3) If the best match so far is below a certain threshold, return "default". 360// 361// Ranking: 362// We use two phases to determine whether one pair of tags are a better match 363// than another pair of tags. First, we determine a rough confidence level. If the 364// levels are different, the one with the highest confidence wins. 365// Second, if the rough confidence levels are identical, we use a set of tie-breaker 366// rules. 367// 368// The confidence level of matching a pair of tags is determined by finding the 369// lowest confidence level of any matches of the corresponding subtags (the 370// result is deemed as good as its weakest link). 371// We define the following levels: 372// Exact - An exact match of a subtag, before adding likely subtags. 373// MaxExact - An exact match of a subtag, after adding likely subtags. 374// [See Note 2]. 375// High - High level of mutual intelligibility between different subtag 376// variants. 377// Low - Low level of mutual intelligibility between different subtag 378// variants. 379// No - No mutual intelligibility. 380// 381// The following levels can occur for each type of subtag: 382// Base: Exact, MaxExact, High, Low, No 383// Script: Exact, MaxExact [see Note 3], Low, No 384// Region: Exact, MaxExact, High 385// Variant: Exact, High 386// Private: Exact, No 387// 388// Any result with a confidence level of Low or higher is deemed a possible match. 389// Once a desired tag matches any of the supported tags with a level of MaxExact 390// or higher, the next desired tag is not considered (see Step 2.b). 391// Note that CLDR provides languageMatching data that defines close equivalence 392// classes for base languages, scripts and regions. 393// 394// Tie-breaking 395// If we get the same confidence level for two matches, we apply a sequence of 396// tie-breaking rules. The first that succeeds defines the result. The rules are 397// applied in the following order. 398// 1) Original language was defined and was identical. 399// 2) Original region was defined and was identical. 400// 3) Distance between two maximized regions was the smallest. 401// 4) Original script was defined and was identical. 402// 5) Distance from want tag to have tag using the parent relation [see Note 5.] 403// If there is still no winner after these rules are applied, the first match 404// found wins. 405// 406// Notes: 407// [2] In practice, as matching of Exact is done in a separate phase from 408// matching the other levels, we reuse the Exact level to mean MaxExact in 409// the second phase. As a consequence, we only need the levels defined by 410// the Confidence type. The MaxExact confidence level is mapped to High in 411// the public API. 412// [3] We do not differentiate between maximized script values that were derived 413// from suppressScript versus most likely tag data. We determined that in 414// ranking the two, one ranks just after the other. Moreover, the two cannot 415// occur concurrently. As a consequence, they are identical for practical 416// purposes. 417// [4] In case of deprecated, macro-equivalents and legacy mappings, we assign 418// the MaxExact level to allow iw vs he to still be a closer match than 419// en-AU vs en-US, for example. 420// [5] In CLDR a locale inherits fields that are unspecified for this locale 421// from its parent. Therefore, if a locale is a parent of another locale, 422// it is a strong measure for closeness, especially when no other tie 423// breaker rule applies. One could also argue it is inconsistent, for 424// example, when pt-AO matches pt (which CLDR equates with pt-BR), even 425// though its parent is pt-PT according to the inheritance rules. 426// 427// Implementation Details: 428// There are several performance considerations worth pointing out. Most notably, 429// we preprocess as much as possible (within reason) at the time of creation of a 430// matcher. This includes: 431// - creating a per-language map, which includes data for the raw base language 432// and its canonicalized variant (if applicable), 433// - expanding entries for the equivalence classes defined in CLDR's 434// languageMatch data. 435// The per-language map ensures that typically only a very small number of tags 436// need to be considered. The pre-expansion of canonicalized subtags and 437// equivalence classes reduces the amount of map lookups that need to be done at 438// runtime. 439 440// matcher keeps a set of supported language tags, indexed by language. 441type matcher struct { 442 default_ *haveTag 443 supported []*haveTag 444 index map[langID]*matchHeader 445 passSettings bool 446 preferSameScript bool 447} 448 449// matchHeader has the lists of tags for exact matches and matches based on 450// maximized and canonicalized tags for a given language. 451type matchHeader struct { 452 haveTags []*haveTag 453 original bool 454} 455 456// haveTag holds a supported Tag and its maximized script and region. The maximized 457// or canonicalized language is not stored as it is not needed during matching. 458type haveTag struct { 459 tag Tag 460 461 // index of this tag in the original list of supported tags. 462 index int 463 464 // conf is the maximum confidence that can result from matching this haveTag. 465 // When conf < Exact this means it was inserted after applying a CLDR equivalence rule. 466 conf Confidence 467 468 // Maximized region and script. 469 maxRegion regionID 470 maxScript scriptID 471 472 // altScript may be checked as an alternative match to maxScript. If altScript 473 // matches, the confidence level for this match is Low. Theoretically there 474 // could be multiple alternative scripts. This does not occur in practice. 475 altScript scriptID 476 477 // nextMax is the index of the next haveTag with the same maximized tags. 478 nextMax uint16 479} 480 481func makeHaveTag(tag Tag, index int) (haveTag, langID) { 482 max := tag 483 if tag.lang != 0 || tag.region != 0 || tag.script != 0 { 484 max, _ = max.canonicalize(All) 485 max, _ = addTags(max) 486 max.remakeString() 487 } 488 return haveTag{tag, index, Exact, max.region, max.script, altScript(max.lang, max.script), 0}, max.lang 489} 490 491// altScript returns an alternative script that may match the given script with 492// a low confidence. At the moment, the langMatch data allows for at most one 493// script to map to another and we rely on this to keep the code simple. 494func altScript(l langID, s scriptID) scriptID { 495 for _, alt := range matchScript { 496 // TODO: also match cases where language is not the same. 497 if (langID(alt.wantLang) == l || langID(alt.haveLang) == l) && 498 scriptID(alt.haveScript) == s { 499 return scriptID(alt.wantScript) 500 } 501 } 502 return 0 503} 504 505// addIfNew adds a haveTag to the list of tags only if it is a unique tag. 506// Tags that have the same maximized values are linked by index. 507func (h *matchHeader) addIfNew(n haveTag, exact bool) { 508 h.original = h.original || exact 509 // Don't add new exact matches. 510 for _, v := range h.haveTags { 511 if v.tag.equalsRest(n.tag) { 512 return 513 } 514 } 515 // Allow duplicate maximized tags, but create a linked list to allow quickly 516 // comparing the equivalents and bail out. 517 for i, v := range h.haveTags { 518 if v.maxScript == n.maxScript && 519 v.maxRegion == n.maxRegion && 520 v.tag.variantOrPrivateTagStr() == n.tag.variantOrPrivateTagStr() { 521 for h.haveTags[i].nextMax != 0 { 522 i = int(h.haveTags[i].nextMax) 523 } 524 h.haveTags[i].nextMax = uint16(len(h.haveTags)) 525 break 526 } 527 } 528 h.haveTags = append(h.haveTags, &n) 529} 530 531// header returns the matchHeader for the given language. It creates one if 532// it doesn't already exist. 533func (m *matcher) header(l langID) *matchHeader { 534 if h := m.index[l]; h != nil { 535 return h 536 } 537 h := &matchHeader{} 538 m.index[l] = h 539 return h 540} 541 542func toConf(d uint8) Confidence { 543 if d <= 10 { 544 return High 545 } 546 if d < 30 { 547 return Low 548 } 549 return No 550} 551 552// newMatcher builds an index for the given supported tags and returns it as 553// a matcher. It also expands the index by considering various equivalence classes 554// for a given tag. 555func newMatcher(supported []Tag, options []MatchOption) *matcher { 556 m := &matcher{ 557 index: make(map[langID]*matchHeader), 558 preferSameScript: true, 559 } 560 for _, o := range options { 561 o(m) 562 } 563 if len(supported) == 0 { 564 m.default_ = &haveTag{} 565 return m 566 } 567 // Add supported languages to the index. Add exact matches first to give 568 // them precedence. 569 for i, tag := range supported { 570 pair, _ := makeHaveTag(tag, i) 571 m.header(tag.lang).addIfNew(pair, true) 572 m.supported = append(m.supported, &pair) 573 } 574 m.default_ = m.header(supported[0].lang).haveTags[0] 575 // Keep these in two different loops to support the case that two equivalent 576 // languages are distinguished, such as iw and he. 577 for i, tag := range supported { 578 pair, max := makeHaveTag(tag, i) 579 if max != tag.lang { 580 m.header(max).addIfNew(pair, true) 581 } 582 } 583 584 // update is used to add indexes in the map for equivalent languages. 585 // update will only add entries to original indexes, thus not computing any 586 // transitive relations. 587 update := func(want, have uint16, conf Confidence) { 588 if hh := m.index[langID(have)]; hh != nil { 589 if !hh.original { 590 return 591 } 592 hw := m.header(langID(want)) 593 for _, ht := range hh.haveTags { 594 v := *ht 595 if conf < v.conf { 596 v.conf = conf 597 } 598 v.nextMax = 0 // this value needs to be recomputed 599 if v.altScript != 0 { 600 v.altScript = altScript(langID(want), v.maxScript) 601 } 602 hw.addIfNew(v, conf == Exact && hh.original) 603 } 604 } 605 } 606 607 // Add entries for languages with mutual intelligibility as defined by CLDR's 608 // languageMatch data. 609 for _, ml := range matchLang { 610 update(ml.want, ml.have, toConf(ml.distance)) 611 if !ml.oneway { 612 update(ml.have, ml.want, toConf(ml.distance)) 613 } 614 } 615 616 // Add entries for possible canonicalizations. This is an optimization to 617 // ensure that only one map lookup needs to be done at runtime per desired tag. 618 // First we match deprecated equivalents. If they are perfect equivalents 619 // (their canonicalization simply substitutes a different language code, but 620 // nothing else), the match confidence is Exact, otherwise it is High. 621 for i, lm := range langAliasMap { 622 // If deprecated codes match and there is no fiddling with the script or 623 // or region, we consider it an exact match. 624 conf := Exact 625 if langAliasTypes[i] != langMacro { 626 if !isExactEquivalent(langID(lm.from)) { 627 conf = High 628 } 629 update(lm.to, lm.from, conf) 630 } 631 update(lm.from, lm.to, conf) 632 } 633 return m 634} 635 636// getBest gets the best matching tag in m for any of the given tags, taking into 637// account the order of preference of the given tags. 638func (m *matcher) getBest(want ...Tag) (got *haveTag, orig Tag, c Confidence) { 639 best := bestMatch{} 640 for i, w := range want { 641 var max Tag 642 // Check for exact match first. 643 h := m.index[w.lang] 644 if w.lang != 0 { 645 if h == nil { 646 continue 647 } 648 // Base language is defined. 649 max, _ = w.canonicalize(Legacy | Deprecated | Macro) 650 // A region that is added through canonicalization is stronger than 651 // a maximized region: set it in the original (e.g. mo -> ro-MD). 652 if w.region != max.region { 653 w.region = max.region 654 } 655 // TODO: should we do the same for scripts? 656 // See test case: en, sr, nl ; sh ; sr 657 max, _ = addTags(max) 658 } else { 659 // Base language is not defined. 660 if h != nil { 661 for i := range h.haveTags { 662 have := h.haveTags[i] 663 if have.tag.equalsRest(w) { 664 return have, w, Exact 665 } 666 } 667 } 668 if w.script == 0 && w.region == 0 { 669 // We skip all tags matching und for approximate matching, including 670 // private tags. 671 continue 672 } 673 max, _ = addTags(w) 674 if h = m.index[max.lang]; h == nil { 675 continue 676 } 677 } 678 pin := true 679 for _, t := range want[i+1:] { 680 if w.lang == t.lang { 681 pin = false 682 break 683 } 684 } 685 // Check for match based on maximized tag. 686 for i := range h.haveTags { 687 have := h.haveTags[i] 688 best.update(have, w, max.script, max.region, pin) 689 if best.conf == Exact { 690 for have.nextMax != 0 { 691 have = h.haveTags[have.nextMax] 692 best.update(have, w, max.script, max.region, pin) 693 } 694 return best.have, best.want, best.conf 695 } 696 } 697 } 698 if best.conf <= No { 699 if len(want) != 0 { 700 return nil, want[0], No 701 } 702 return nil, Tag{}, No 703 } 704 return best.have, best.want, best.conf 705} 706 707// bestMatch accumulates the best match so far. 708type bestMatch struct { 709 have *haveTag 710 want Tag 711 conf Confidence 712 pinnedRegion regionID 713 pinLanguage bool 714 sameRegionGroup bool 715 // Cached results from applying tie-breaking rules. 716 origLang bool 717 origReg bool 718 paradigmReg bool 719 regGroupDist uint8 720 origScript bool 721} 722 723// update updates the existing best match if the new pair is considered to be a 724// better match. To determine if the given pair is a better match, it first 725// computes the rough confidence level. If this surpasses the current match, it 726// will replace it and update the tie-breaker rule cache. If there is a tie, it 727// proceeds with applying a series of tie-breaker rules. If there is no 728// conclusive winner after applying the tie-breaker rules, it leaves the current 729// match as the preferred match. 730// 731// If pin is true and have and tag are a strong match, it will henceforth only 732// consider matches for this language. This corresponds to the nothing that most 733// users have a strong preference for the first defined language. A user can 734// still prefer a second language over a dialect of the preferred language by 735// explicitly specifying dialects, e.g. "en, nl, en-GB". In this case pin should 736// be false. 737func (m *bestMatch) update(have *haveTag, tag Tag, maxScript scriptID, maxRegion regionID, pin bool) { 738 // Bail if the maximum attainable confidence is below that of the current best match. 739 c := have.conf 740 if c < m.conf { 741 return 742 } 743 // Don't change the language once we already have found an exact match. 744 if m.pinLanguage && tag.lang != m.want.lang { 745 return 746 } 747 // Pin the region group if we are comparing tags for the same language. 748 if tag.lang == m.want.lang && m.sameRegionGroup { 749 _, sameGroup := regionGroupDist(m.pinnedRegion, have.maxRegion, have.maxScript, m.want.lang) 750 if !sameGroup { 751 return 752 } 753 } 754 if c == Exact && have.maxScript == maxScript { 755 // If there is another language and then another entry of this language, 756 // don't pin anything, otherwise pin the language. 757 m.pinLanguage = pin 758 } 759 if have.tag.equalsRest(tag) { 760 } else if have.maxScript != maxScript { 761 // There is usually very little comprehension between different scripts. 762 // In a few cases there may still be Low comprehension. This possibility 763 // is pre-computed and stored in have.altScript. 764 if Low < m.conf || have.altScript != maxScript { 765 return 766 } 767 c = Low 768 } else if have.maxRegion != maxRegion { 769 if High < c { 770 // There is usually a small difference between languages across regions. 771 c = High 772 } 773 } 774 775 // We store the results of the computations of the tie-breaker rules along 776 // with the best match. There is no need to do the checks once we determine 777 // we have a winner, but we do still need to do the tie-breaker computations. 778 // We use "beaten" to keep track if we still need to do the checks. 779 beaten := false // true if the new pair defeats the current one. 780 if c != m.conf { 781 if c < m.conf { 782 return 783 } 784 beaten = true 785 } 786 787 // Tie-breaker rules: 788 // We prefer if the pre-maximized language was specified and identical. 789 origLang := have.tag.lang == tag.lang && tag.lang != 0 790 if !beaten && m.origLang != origLang { 791 if m.origLang { 792 return 793 } 794 beaten = true 795 } 796 797 // We prefer if the pre-maximized region was specified and identical. 798 origReg := have.tag.region == tag.region && tag.region != 0 799 if !beaten && m.origReg != origReg { 800 if m.origReg { 801 return 802 } 803 beaten = true 804 } 805 806 regGroupDist, sameGroup := regionGroupDist(have.maxRegion, maxRegion, maxScript, tag.lang) 807 if !beaten && m.regGroupDist != regGroupDist { 808 if regGroupDist > m.regGroupDist { 809 return 810 } 811 beaten = true 812 } 813 814 paradigmReg := isParadigmLocale(tag.lang, have.maxRegion) 815 if !beaten && m.paradigmReg != paradigmReg { 816 if !paradigmReg { 817 return 818 } 819 beaten = true 820 } 821 822 // Next we prefer if the pre-maximized script was specified and identical. 823 origScript := have.tag.script == tag.script && tag.script != 0 824 if !beaten && m.origScript != origScript { 825 if m.origScript { 826 return 827 } 828 beaten = true 829 } 830 831 // Update m to the newly found best match. 832 if beaten { 833 m.have = have 834 m.want = tag 835 m.conf = c 836 m.pinnedRegion = maxRegion 837 m.sameRegionGroup = sameGroup 838 m.origLang = origLang 839 m.origReg = origReg 840 m.paradigmReg = paradigmReg 841 m.origScript = origScript 842 m.regGroupDist = regGroupDist 843 } 844} 845 846func isParadigmLocale(lang langID, r regionID) bool { 847 for _, e := range paradigmLocales { 848 if langID(e[0]) == lang && (r == regionID(e[1]) || r == regionID(e[2])) { 849 return true 850 } 851 } 852 return false 853} 854 855// regionGroupDist computes the distance between two regions based on their 856// CLDR grouping. 857func regionGroupDist(a, b regionID, script scriptID, lang langID) (dist uint8, same bool) { 858 const defaultDistance = 4 859 860 aGroup := uint(regionToGroups[a]) << 1 861 bGroup := uint(regionToGroups[b]) << 1 862 for _, ri := range matchRegion { 863 if langID(ri.lang) == lang && (ri.script == 0 || scriptID(ri.script) == script) { 864 group := uint(1 << (ri.group &^ 0x80)) 865 if 0x80&ri.group == 0 { 866 if aGroup&bGroup&group != 0 { // Both regions are in the group. 867 return ri.distance, ri.distance == defaultDistance 868 } 869 } else { 870 if (aGroup|bGroup)&group == 0 { // Both regions are not in the group. 871 return ri.distance, ri.distance == defaultDistance 872 } 873 } 874 } 875 } 876 return defaultDistance, true 877} 878 879func (t Tag) variants() string { 880 if t.pVariant == 0 { 881 return "" 882 } 883 return t.str[t.pVariant:t.pExt] 884} 885 886// variantOrPrivateTagStr returns variants or private use tags. 887func (t Tag) variantOrPrivateTagStr() string { 888 if t.pExt > 0 { 889 return t.str[t.pVariant:t.pExt] 890 } 891 return t.str[t.pVariant:] 892} 893 894// equalsRest compares everything except the language. 895func (a Tag) equalsRest(b Tag) bool { 896 // TODO: don't include extensions in this comparison. To do this efficiently, 897 // though, we should handle private tags separately. 898 return a.script == b.script && a.region == b.region && a.variantOrPrivateTagStr() == b.variantOrPrivateTagStr() 899} 900 901// isExactEquivalent returns true if canonicalizing the language will not alter 902// the script or region of a tag. 903func isExactEquivalent(l langID) bool { 904 for _, o := range notEquivalent { 905 if o == l { 906 return false 907 } 908 } 909 return true 910} 911 912var notEquivalent []langID 913 914func init() { 915 // Create a list of all languages for which canonicalization may alter the 916 // script or region. 917 for _, lm := range langAliasMap { 918 tag := Tag{lang: langID(lm.from)} 919 if tag, _ = tag.canonicalize(All); tag.script != 0 || tag.region != 0 { 920 notEquivalent = append(notEquivalent, langID(lm.from)) 921 } 922 } 923 // Maximize undefined regions of paradigm locales. 924 for i, v := range paradigmLocales { 925 max, _ := addTags(Tag{lang: langID(v[0])}) 926 if v[1] == 0 { 927 paradigmLocales[i][1] = uint16(max.region) 928 } 929 if v[2] == 0 { 930 paradigmLocales[i][2] = uint16(max.region) 931 } 932 } 933} 934