blob: 15b74d125ceae0c647df881f2ba34edf996c17c3 [file] [log] [blame]
khenaidooac637102019-01-14 15:44:34 -05001// 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}