blob: f734921349ca6b45a2a8274160d70e66fa145b56 [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
Scott Baker8461e152019-10-01 14:44:30 -07007import (
8 "errors"
9 "strings"
10
11 "golang.org/x/text/internal/language"
12)
khenaidooac637102019-01-14 15:44:34 -050013
14// A MatchOption configures a Matcher.
15type MatchOption func(*matcher)
16
17// PreferSameScript will, in the absence of a match, result in the first
18// preferred tag with the same script as a supported tag to match this supported
19// tag. The default is currently true, but this may change in the future.
20func PreferSameScript(preferSame bool) MatchOption {
21 return func(m *matcher) { m.preferSameScript = preferSame }
22}
23
24// TODO(v1.0.0): consider making Matcher a concrete type, instead of interface.
25// There doesn't seem to be too much need for multiple types.
26// Making it a concrete type allows MatchStrings to be a method, which will
27// improve its discoverability.
28
29// MatchStrings parses and matches the given strings until one of them matches
30// the language in the Matcher. A string may be an Accept-Language header as
31// handled by ParseAcceptLanguage. The default language is returned if no
32// other language matched.
33func MatchStrings(m Matcher, lang ...string) (tag Tag, index int) {
34 for _, accept := range lang {
35 desired, _, err := ParseAcceptLanguage(accept)
36 if err != nil {
37 continue
38 }
39 if tag, index, conf := m.Match(desired...); conf != No {
40 return tag, index
41 }
42 }
43 tag, index, _ = m.Match()
44 return
45}
46
47// Matcher is the interface that wraps the Match method.
48//
49// Match returns the best match for any of the given tags, along with
50// a unique index associated with the returned tag and a confidence
51// score.
52type Matcher interface {
53 Match(t ...Tag) (tag Tag, index int, c Confidence)
54}
55
56// Comprehends reports the confidence score for a speaker of a given language
57// to being able to comprehend the written form of an alternative language.
58func Comprehends(speaker, alternative Tag) Confidence {
59 _, _, c := NewMatcher([]Tag{alternative}).Match(speaker)
60 return c
61}
62
63// NewMatcher returns a Matcher that matches an ordered list of preferred tags
64// against a list of supported tags based on written intelligibility, closeness
65// of dialect, equivalence of subtags and various other rules. It is initialized
66// with the list of supported tags. The first element is used as the default
67// value in case no match is found.
68//
69// Its Match method matches the first of the given Tags to reach a certain
70// confidence threshold. The tags passed to Match should therefore be specified
71// in order of preference. Extensions are ignored for matching.
72//
73// The index returned by the Match method corresponds to the index of the
74// matched tag in t, but is augmented with the Unicode extension ('u')of the
75// corresponding preferred tag. This allows user locale options to be passed
76// transparently.
77func NewMatcher(t []Tag, options ...MatchOption) Matcher {
78 return newMatcher(t, options)
79}
80
81func (m *matcher) Match(want ...Tag) (t Tag, index int, c Confidence) {
Scott Baker8461e152019-10-01 14:44:30 -070082 var tt language.Tag
khenaidooac637102019-01-14 15:44:34 -050083 match, w, c := m.getBest(want...)
84 if match != nil {
Scott Baker8461e152019-10-01 14:44:30 -070085 tt, index = match.tag, match.index
khenaidooac637102019-01-14 15:44:34 -050086 } else {
87 // TODO: this should be an option
Scott Baker8461e152019-10-01 14:44:30 -070088 tt = m.default_.tag
khenaidooac637102019-01-14 15:44:34 -050089 if m.preferSameScript {
90 outer:
91 for _, w := range want {
92 script, _ := w.Script()
93 if script.scriptID == 0 {
94 // Don't do anything if there is no script, such as with
95 // private subtags.
96 continue
97 }
98 for i, h := range m.supported {
99 if script.scriptID == h.maxScript {
Scott Baker8461e152019-10-01 14:44:30 -0700100 tt, index = h.tag, i
khenaidooac637102019-01-14 15:44:34 -0500101 break outer
102 }
103 }
104 }
105 }
106 // TODO: select first language tag based on script.
107 }
Scott Baker8461e152019-10-01 14:44:30 -0700108 if w.RegionID != tt.RegionID && w.RegionID != 0 {
109 if w.RegionID != 0 && tt.RegionID != 0 && tt.RegionID.Contains(w.RegionID) {
110 tt.RegionID = w.RegionID
111 tt.RemakeString()
112 } else if r := w.RegionID.String(); len(r) == 2 {
113 // TODO: also filter macro and deprecated.
114 tt, _ = tt.SetTypeForKey("rg", strings.ToLower(r)+"zzzz")
115 }
khenaidooac637102019-01-14 15:44:34 -0500116 }
117 // Copy options from the user-provided tag into the result tag. This is hard
118 // to do after the fact, so we do it here.
119 // TODO: add in alternative variants to -u-va-.
120 // TODO: add preferred region to -u-rg-.
121 if e := w.Extensions(); len(e) > 0 {
Scott Baker8461e152019-10-01 14:44:30 -0700122 b := language.Builder{}
123 b.SetTag(tt)
124 for _, e := range e {
125 b.AddExt(e)
126 }
127 tt = b.Make()
khenaidooac637102019-01-14 15:44:34 -0500128 }
Scott Baker8461e152019-10-01 14:44:30 -0700129 return makeTag(tt), index, c
khenaidooac637102019-01-14 15:44:34 -0500130}
131
132// ErrMissingLikelyTagsData indicates no information was available
133// to compute likely values of missing tags.
134var ErrMissingLikelyTagsData = errors.New("missing likely tags data")
135
Scott Baker8461e152019-10-01 14:44:30 -0700136// func (t *Tag) setTagsFrom(id Tag) {
137// t.LangID = id.LangID
138// t.ScriptID = id.ScriptID
139// t.RegionID = id.RegionID
140// }
khenaidooac637102019-01-14 15:44:34 -0500141
142// Tag Matching
143// CLDR defines an algorithm for finding the best match between two sets of language
144// tags. The basic algorithm defines how to score a possible match and then find
145// the match with the best score
Scott Baker8461e152019-10-01 14:44:30 -0700146// (see https://www.unicode.org/reports/tr35/#LanguageMatching).
khenaidooac637102019-01-14 15:44:34 -0500147// Using scoring has several disadvantages. The scoring obfuscates the importance of
148// the various factors considered, making the algorithm harder to understand. Using
149// scoring also requires the full score to be computed for each pair of tags.
150//
151// We will use a different algorithm which aims to have the following properties:
152// - clarity on the precedence of the various selection factors, and
153// - improved performance by allowing early termination of a comparison.
154//
155// Matching algorithm (overview)
156// Input:
157// - supported: a set of supported tags
158// - default: the default tag to return in case there is no match
159// - desired: list of desired tags, ordered by preference, starting with
160// the most-preferred.
161//
162// Algorithm:
163// 1) Set the best match to the lowest confidence level
164// 2) For each tag in "desired":
165// a) For each tag in "supported":
166// 1) compute the match between the two tags.
167// 2) if the match is better than the previous best match, replace it
168// with the new match. (see next section)
169// b) if the current best match is Exact and pin is true the result will be
170// frozen to the language found thusfar, although better matches may
171// still be found for the same language.
172// 3) If the best match so far is below a certain threshold, return "default".
173//
174// Ranking:
175// We use two phases to determine whether one pair of tags are a better match
176// than another pair of tags. First, we determine a rough confidence level. If the
177// levels are different, the one with the highest confidence wins.
178// Second, if the rough confidence levels are identical, we use a set of tie-breaker
179// rules.
180//
181// The confidence level of matching a pair of tags is determined by finding the
182// lowest confidence level of any matches of the corresponding subtags (the
183// result is deemed as good as its weakest link).
184// We define the following levels:
185// Exact - An exact match of a subtag, before adding likely subtags.
186// MaxExact - An exact match of a subtag, after adding likely subtags.
187// [See Note 2].
188// High - High level of mutual intelligibility between different subtag
189// variants.
190// Low - Low level of mutual intelligibility between different subtag
191// variants.
192// No - No mutual intelligibility.
193//
194// The following levels can occur for each type of subtag:
195// Base: Exact, MaxExact, High, Low, No
196// Script: Exact, MaxExact [see Note 3], Low, No
197// Region: Exact, MaxExact, High
198// Variant: Exact, High
199// Private: Exact, No
200//
201// Any result with a confidence level of Low or higher is deemed a possible match.
202// Once a desired tag matches any of the supported tags with a level of MaxExact
203// or higher, the next desired tag is not considered (see Step 2.b).
204// Note that CLDR provides languageMatching data that defines close equivalence
205// classes for base languages, scripts and regions.
206//
207// Tie-breaking
208// If we get the same confidence level for two matches, we apply a sequence of
209// tie-breaking rules. The first that succeeds defines the result. The rules are
210// applied in the following order.
211// 1) Original language was defined and was identical.
212// 2) Original region was defined and was identical.
213// 3) Distance between two maximized regions was the smallest.
214// 4) Original script was defined and was identical.
215// 5) Distance from want tag to have tag using the parent relation [see Note 5.]
216// If there is still no winner after these rules are applied, the first match
217// found wins.
218//
219// Notes:
220// [2] In practice, as matching of Exact is done in a separate phase from
221// matching the other levels, we reuse the Exact level to mean MaxExact in
222// the second phase. As a consequence, we only need the levels defined by
223// the Confidence type. The MaxExact confidence level is mapped to High in
224// the public API.
225// [3] We do not differentiate between maximized script values that were derived
226// from suppressScript versus most likely tag data. We determined that in
227// ranking the two, one ranks just after the other. Moreover, the two cannot
228// occur concurrently. As a consequence, they are identical for practical
229// purposes.
230// [4] In case of deprecated, macro-equivalents and legacy mappings, we assign
231// the MaxExact level to allow iw vs he to still be a closer match than
232// en-AU vs en-US, for example.
233// [5] In CLDR a locale inherits fields that are unspecified for this locale
234// from its parent. Therefore, if a locale is a parent of another locale,
235// it is a strong measure for closeness, especially when no other tie
236// breaker rule applies. One could also argue it is inconsistent, for
237// example, when pt-AO matches pt (which CLDR equates with pt-BR), even
238// though its parent is pt-PT according to the inheritance rules.
239//
240// Implementation Details:
241// There are several performance considerations worth pointing out. Most notably,
242// we preprocess as much as possible (within reason) at the time of creation of a
243// matcher. This includes:
244// - creating a per-language map, which includes data for the raw base language
245// and its canonicalized variant (if applicable),
246// - expanding entries for the equivalence classes defined in CLDR's
247// languageMatch data.
248// The per-language map ensures that typically only a very small number of tags
249// need to be considered. The pre-expansion of canonicalized subtags and
250// equivalence classes reduces the amount of map lookups that need to be done at
251// runtime.
252
253// matcher keeps a set of supported language tags, indexed by language.
254type matcher struct {
255 default_ *haveTag
256 supported []*haveTag
Scott Baker8461e152019-10-01 14:44:30 -0700257 index map[language.Language]*matchHeader
khenaidooac637102019-01-14 15:44:34 -0500258 passSettings bool
259 preferSameScript bool
260}
261
262// matchHeader has the lists of tags for exact matches and matches based on
263// maximized and canonicalized tags for a given language.
264type matchHeader struct {
265 haveTags []*haveTag
266 original bool
267}
268
269// haveTag holds a supported Tag and its maximized script and region. The maximized
270// or canonicalized language is not stored as it is not needed during matching.
271type haveTag struct {
Scott Baker8461e152019-10-01 14:44:30 -0700272 tag language.Tag
khenaidooac637102019-01-14 15:44:34 -0500273
274 // index of this tag in the original list of supported tags.
275 index int
276
277 // conf is the maximum confidence that can result from matching this haveTag.
278 // When conf < Exact this means it was inserted after applying a CLDR equivalence rule.
279 conf Confidence
280
281 // Maximized region and script.
Scott Baker8461e152019-10-01 14:44:30 -0700282 maxRegion language.Region
283 maxScript language.Script
khenaidooac637102019-01-14 15:44:34 -0500284
285 // altScript may be checked as an alternative match to maxScript. If altScript
286 // matches, the confidence level for this match is Low. Theoretically there
287 // could be multiple alternative scripts. This does not occur in practice.
Scott Baker8461e152019-10-01 14:44:30 -0700288 altScript language.Script
khenaidooac637102019-01-14 15:44:34 -0500289
290 // nextMax is the index of the next haveTag with the same maximized tags.
291 nextMax uint16
292}
293
Scott Baker8461e152019-10-01 14:44:30 -0700294func makeHaveTag(tag language.Tag, index int) (haveTag, language.Language) {
khenaidooac637102019-01-14 15:44:34 -0500295 max := tag
Scott Baker8461e152019-10-01 14:44:30 -0700296 if tag.LangID != 0 || tag.RegionID != 0 || tag.ScriptID != 0 {
297 max, _ = canonicalize(All, max)
298 max, _ = max.Maximize()
299 max.RemakeString()
khenaidooac637102019-01-14 15:44:34 -0500300 }
Scott Baker8461e152019-10-01 14:44:30 -0700301 return haveTag{tag, index, Exact, max.RegionID, max.ScriptID, altScript(max.LangID, max.ScriptID), 0}, max.LangID
khenaidooac637102019-01-14 15:44:34 -0500302}
303
304// altScript returns an alternative script that may match the given script with
305// a low confidence. At the moment, the langMatch data allows for at most one
306// script to map to another and we rely on this to keep the code simple.
Scott Baker8461e152019-10-01 14:44:30 -0700307func altScript(l language.Language, s language.Script) language.Script {
khenaidooac637102019-01-14 15:44:34 -0500308 for _, alt := range matchScript {
309 // TODO: also match cases where language is not the same.
Scott Baker8461e152019-10-01 14:44:30 -0700310 if (language.Language(alt.wantLang) == l || language.Language(alt.haveLang) == l) &&
311 language.Script(alt.haveScript) == s {
312 return language.Script(alt.wantScript)
khenaidooac637102019-01-14 15:44:34 -0500313 }
314 }
315 return 0
316}
317
318// addIfNew adds a haveTag to the list of tags only if it is a unique tag.
319// Tags that have the same maximized values are linked by index.
320func (h *matchHeader) addIfNew(n haveTag, exact bool) {
321 h.original = h.original || exact
322 // Don't add new exact matches.
323 for _, v := range h.haveTags {
Scott Baker8461e152019-10-01 14:44:30 -0700324 if equalsRest(v.tag, n.tag) {
khenaidooac637102019-01-14 15:44:34 -0500325 return
326 }
327 }
328 // Allow duplicate maximized tags, but create a linked list to allow quickly
329 // comparing the equivalents and bail out.
330 for i, v := range h.haveTags {
331 if v.maxScript == n.maxScript &&
332 v.maxRegion == n.maxRegion &&
Scott Baker8461e152019-10-01 14:44:30 -0700333 v.tag.VariantOrPrivateUseTags() == n.tag.VariantOrPrivateUseTags() {
khenaidooac637102019-01-14 15:44:34 -0500334 for h.haveTags[i].nextMax != 0 {
335 i = int(h.haveTags[i].nextMax)
336 }
337 h.haveTags[i].nextMax = uint16(len(h.haveTags))
338 break
339 }
340 }
341 h.haveTags = append(h.haveTags, &n)
342}
343
344// header returns the matchHeader for the given language. It creates one if
345// it doesn't already exist.
Scott Baker8461e152019-10-01 14:44:30 -0700346func (m *matcher) header(l language.Language) *matchHeader {
khenaidooac637102019-01-14 15:44:34 -0500347 if h := m.index[l]; h != nil {
348 return h
349 }
350 h := &matchHeader{}
351 m.index[l] = h
352 return h
353}
354
355func toConf(d uint8) Confidence {
356 if d <= 10 {
357 return High
358 }
359 if d < 30 {
360 return Low
361 }
362 return No
363}
364
365// newMatcher builds an index for the given supported tags and returns it as
366// a matcher. It also expands the index by considering various equivalence classes
367// for a given tag.
368func newMatcher(supported []Tag, options []MatchOption) *matcher {
369 m := &matcher{
Scott Baker8461e152019-10-01 14:44:30 -0700370 index: make(map[language.Language]*matchHeader),
khenaidooac637102019-01-14 15:44:34 -0500371 preferSameScript: true,
372 }
373 for _, o := range options {
374 o(m)
375 }
376 if len(supported) == 0 {
377 m.default_ = &haveTag{}
378 return m
379 }
380 // Add supported languages to the index. Add exact matches first to give
381 // them precedence.
382 for i, tag := range supported {
Scott Baker8461e152019-10-01 14:44:30 -0700383 tt := tag.tag()
384 pair, _ := makeHaveTag(tt, i)
385 m.header(tt.LangID).addIfNew(pair, true)
khenaidooac637102019-01-14 15:44:34 -0500386 m.supported = append(m.supported, &pair)
387 }
Scott Baker8461e152019-10-01 14:44:30 -0700388 m.default_ = m.header(supported[0].lang()).haveTags[0]
khenaidooac637102019-01-14 15:44:34 -0500389 // Keep these in two different loops to support the case that two equivalent
390 // languages are distinguished, such as iw and he.
391 for i, tag := range supported {
Scott Baker8461e152019-10-01 14:44:30 -0700392 tt := tag.tag()
393 pair, max := makeHaveTag(tt, i)
394 if max != tt.LangID {
khenaidooac637102019-01-14 15:44:34 -0500395 m.header(max).addIfNew(pair, true)
396 }
397 }
398
399 // update is used to add indexes in the map for equivalent languages.
400 // update will only add entries to original indexes, thus not computing any
401 // transitive relations.
402 update := func(want, have uint16, conf Confidence) {
Scott Baker8461e152019-10-01 14:44:30 -0700403 if hh := m.index[language.Language(have)]; hh != nil {
khenaidooac637102019-01-14 15:44:34 -0500404 if !hh.original {
405 return
406 }
Scott Baker8461e152019-10-01 14:44:30 -0700407 hw := m.header(language.Language(want))
khenaidooac637102019-01-14 15:44:34 -0500408 for _, ht := range hh.haveTags {
409 v := *ht
410 if conf < v.conf {
411 v.conf = conf
412 }
413 v.nextMax = 0 // this value needs to be recomputed
414 if v.altScript != 0 {
Scott Baker8461e152019-10-01 14:44:30 -0700415 v.altScript = altScript(language.Language(want), v.maxScript)
khenaidooac637102019-01-14 15:44:34 -0500416 }
417 hw.addIfNew(v, conf == Exact && hh.original)
418 }
419 }
420 }
421
422 // Add entries for languages with mutual intelligibility as defined by CLDR's
423 // languageMatch data.
424 for _, ml := range matchLang {
425 update(ml.want, ml.have, toConf(ml.distance))
426 if !ml.oneway {
427 update(ml.have, ml.want, toConf(ml.distance))
428 }
429 }
430
431 // Add entries for possible canonicalizations. This is an optimization to
432 // ensure that only one map lookup needs to be done at runtime per desired tag.
433 // First we match deprecated equivalents. If they are perfect equivalents
434 // (their canonicalization simply substitutes a different language code, but
435 // nothing else), the match confidence is Exact, otherwise it is High.
Scott Baker8461e152019-10-01 14:44:30 -0700436 for i, lm := range language.AliasMap {
khenaidooac637102019-01-14 15:44:34 -0500437 // If deprecated codes match and there is no fiddling with the script or
438 // or region, we consider it an exact match.
439 conf := Exact
Scott Baker8461e152019-10-01 14:44:30 -0700440 if language.AliasTypes[i] != language.Macro {
441 if !isExactEquivalent(language.Language(lm.From)) {
khenaidooac637102019-01-14 15:44:34 -0500442 conf = High
443 }
Scott Baker8461e152019-10-01 14:44:30 -0700444 update(lm.To, lm.From, conf)
khenaidooac637102019-01-14 15:44:34 -0500445 }
Scott Baker8461e152019-10-01 14:44:30 -0700446 update(lm.From, lm.To, conf)
khenaidooac637102019-01-14 15:44:34 -0500447 }
448 return m
449}
450
451// getBest gets the best matching tag in m for any of the given tags, taking into
452// account the order of preference of the given tags.
Scott Baker8461e152019-10-01 14:44:30 -0700453func (m *matcher) getBest(want ...Tag) (got *haveTag, orig language.Tag, c Confidence) {
khenaidooac637102019-01-14 15:44:34 -0500454 best := bestMatch{}
Scott Baker8461e152019-10-01 14:44:30 -0700455 for i, ww := range want {
456 w := ww.tag()
457 var max language.Tag
khenaidooac637102019-01-14 15:44:34 -0500458 // Check for exact match first.
Scott Baker8461e152019-10-01 14:44:30 -0700459 h := m.index[w.LangID]
460 if w.LangID != 0 {
khenaidooac637102019-01-14 15:44:34 -0500461 if h == nil {
462 continue
463 }
464 // Base language is defined.
Scott Baker8461e152019-10-01 14:44:30 -0700465 max, _ = canonicalize(Legacy|Deprecated|Macro, w)
khenaidooac637102019-01-14 15:44:34 -0500466 // A region that is added through canonicalization is stronger than
467 // a maximized region: set it in the original (e.g. mo -> ro-MD).
Scott Baker8461e152019-10-01 14:44:30 -0700468 if w.RegionID != max.RegionID {
469 w.RegionID = max.RegionID
khenaidooac637102019-01-14 15:44:34 -0500470 }
471 // TODO: should we do the same for scripts?
472 // See test case: en, sr, nl ; sh ; sr
Scott Baker8461e152019-10-01 14:44:30 -0700473 max, _ = max.Maximize()
khenaidooac637102019-01-14 15:44:34 -0500474 } else {
475 // Base language is not defined.
476 if h != nil {
477 for i := range h.haveTags {
478 have := h.haveTags[i]
Scott Baker8461e152019-10-01 14:44:30 -0700479 if equalsRest(have.tag, w) {
khenaidooac637102019-01-14 15:44:34 -0500480 return have, w, Exact
481 }
482 }
483 }
Scott Baker8461e152019-10-01 14:44:30 -0700484 if w.ScriptID == 0 && w.RegionID == 0 {
khenaidooac637102019-01-14 15:44:34 -0500485 // We skip all tags matching und for approximate matching, including
486 // private tags.
487 continue
488 }
Scott Baker8461e152019-10-01 14:44:30 -0700489 max, _ = w.Maximize()
490 if h = m.index[max.LangID]; h == nil {
khenaidooac637102019-01-14 15:44:34 -0500491 continue
492 }
493 }
494 pin := true
495 for _, t := range want[i+1:] {
Scott Baker8461e152019-10-01 14:44:30 -0700496 if w.LangID == t.lang() {
khenaidooac637102019-01-14 15:44:34 -0500497 pin = false
498 break
499 }
500 }
501 // Check for match based on maximized tag.
502 for i := range h.haveTags {
503 have := h.haveTags[i]
Scott Baker8461e152019-10-01 14:44:30 -0700504 best.update(have, w, max.ScriptID, max.RegionID, pin)
khenaidooac637102019-01-14 15:44:34 -0500505 if best.conf == Exact {
506 for have.nextMax != 0 {
507 have = h.haveTags[have.nextMax]
Scott Baker8461e152019-10-01 14:44:30 -0700508 best.update(have, w, max.ScriptID, max.RegionID, pin)
khenaidooac637102019-01-14 15:44:34 -0500509 }
510 return best.have, best.want, best.conf
511 }
512 }
513 }
514 if best.conf <= No {
515 if len(want) != 0 {
Scott Baker8461e152019-10-01 14:44:30 -0700516 return nil, want[0].tag(), No
khenaidooac637102019-01-14 15:44:34 -0500517 }
Scott Baker8461e152019-10-01 14:44:30 -0700518 return nil, language.Tag{}, No
khenaidooac637102019-01-14 15:44:34 -0500519 }
520 return best.have, best.want, best.conf
521}
522
523// bestMatch accumulates the best match so far.
524type bestMatch struct {
525 have *haveTag
Scott Baker8461e152019-10-01 14:44:30 -0700526 want language.Tag
khenaidooac637102019-01-14 15:44:34 -0500527 conf Confidence
Scott Baker8461e152019-10-01 14:44:30 -0700528 pinnedRegion language.Region
khenaidooac637102019-01-14 15:44:34 -0500529 pinLanguage bool
530 sameRegionGroup bool
531 // Cached results from applying tie-breaking rules.
532 origLang bool
533 origReg bool
534 paradigmReg bool
535 regGroupDist uint8
536 origScript bool
537}
538
539// update updates the existing best match if the new pair is considered to be a
540// better match. To determine if the given pair is a better match, it first
541// computes the rough confidence level. If this surpasses the current match, it
542// will replace it and update the tie-breaker rule cache. If there is a tie, it
543// proceeds with applying a series of tie-breaker rules. If there is no
544// conclusive winner after applying the tie-breaker rules, it leaves the current
545// match as the preferred match.
546//
547// If pin is true and have and tag are a strong match, it will henceforth only
548// consider matches for this language. This corresponds to the nothing that most
549// users have a strong preference for the first defined language. A user can
550// still prefer a second language over a dialect of the preferred language by
551// explicitly specifying dialects, e.g. "en, nl, en-GB". In this case pin should
552// be false.
Scott Baker8461e152019-10-01 14:44:30 -0700553func (m *bestMatch) update(have *haveTag, tag language.Tag, maxScript language.Script, maxRegion language.Region, pin bool) {
khenaidooac637102019-01-14 15:44:34 -0500554 // Bail if the maximum attainable confidence is below that of the current best match.
555 c := have.conf
556 if c < m.conf {
557 return
558 }
559 // Don't change the language once we already have found an exact match.
Scott Baker8461e152019-10-01 14:44:30 -0700560 if m.pinLanguage && tag.LangID != m.want.LangID {
khenaidooac637102019-01-14 15:44:34 -0500561 return
562 }
563 // Pin the region group if we are comparing tags for the same language.
Scott Baker8461e152019-10-01 14:44:30 -0700564 if tag.LangID == m.want.LangID && m.sameRegionGroup {
565 _, sameGroup := regionGroupDist(m.pinnedRegion, have.maxRegion, have.maxScript, m.want.LangID)
khenaidooac637102019-01-14 15:44:34 -0500566 if !sameGroup {
567 return
568 }
569 }
570 if c == Exact && have.maxScript == maxScript {
571 // If there is another language and then another entry of this language,
572 // don't pin anything, otherwise pin the language.
573 m.pinLanguage = pin
574 }
Scott Baker8461e152019-10-01 14:44:30 -0700575 if equalsRest(have.tag, tag) {
khenaidooac637102019-01-14 15:44:34 -0500576 } else if have.maxScript != maxScript {
577 // There is usually very little comprehension between different scripts.
578 // In a few cases there may still be Low comprehension. This possibility
579 // is pre-computed and stored in have.altScript.
580 if Low < m.conf || have.altScript != maxScript {
581 return
582 }
583 c = Low
584 } else if have.maxRegion != maxRegion {
585 if High < c {
586 // There is usually a small difference between languages across regions.
587 c = High
588 }
589 }
590
591 // We store the results of the computations of the tie-breaker rules along
592 // with the best match. There is no need to do the checks once we determine
593 // we have a winner, but we do still need to do the tie-breaker computations.
594 // We use "beaten" to keep track if we still need to do the checks.
595 beaten := false // true if the new pair defeats the current one.
596 if c != m.conf {
597 if c < m.conf {
598 return
599 }
600 beaten = true
601 }
602
603 // Tie-breaker rules:
604 // We prefer if the pre-maximized language was specified and identical.
Scott Baker8461e152019-10-01 14:44:30 -0700605 origLang := have.tag.LangID == tag.LangID && tag.LangID != 0
khenaidooac637102019-01-14 15:44:34 -0500606 if !beaten && m.origLang != origLang {
607 if m.origLang {
608 return
609 }
610 beaten = true
611 }
612
613 // We prefer if the pre-maximized region was specified and identical.
Scott Baker8461e152019-10-01 14:44:30 -0700614 origReg := have.tag.RegionID == tag.RegionID && tag.RegionID != 0
khenaidooac637102019-01-14 15:44:34 -0500615 if !beaten && m.origReg != origReg {
616 if m.origReg {
617 return
618 }
619 beaten = true
620 }
621
Scott Baker8461e152019-10-01 14:44:30 -0700622 regGroupDist, sameGroup := regionGroupDist(have.maxRegion, maxRegion, maxScript, tag.LangID)
khenaidooac637102019-01-14 15:44:34 -0500623 if !beaten && m.regGroupDist != regGroupDist {
624 if regGroupDist > m.regGroupDist {
625 return
626 }
627 beaten = true
628 }
629
Scott Baker8461e152019-10-01 14:44:30 -0700630 paradigmReg := isParadigmLocale(tag.LangID, have.maxRegion)
khenaidooac637102019-01-14 15:44:34 -0500631 if !beaten && m.paradigmReg != paradigmReg {
632 if !paradigmReg {
633 return
634 }
635 beaten = true
636 }
637
638 // Next we prefer if the pre-maximized script was specified and identical.
Scott Baker8461e152019-10-01 14:44:30 -0700639 origScript := have.tag.ScriptID == tag.ScriptID && tag.ScriptID != 0
khenaidooac637102019-01-14 15:44:34 -0500640 if !beaten && m.origScript != origScript {
641 if m.origScript {
642 return
643 }
644 beaten = true
645 }
646
647 // Update m to the newly found best match.
648 if beaten {
649 m.have = have
650 m.want = tag
651 m.conf = c
652 m.pinnedRegion = maxRegion
653 m.sameRegionGroup = sameGroup
654 m.origLang = origLang
655 m.origReg = origReg
656 m.paradigmReg = paradigmReg
657 m.origScript = origScript
658 m.regGroupDist = regGroupDist
659 }
660}
661
Scott Baker8461e152019-10-01 14:44:30 -0700662func isParadigmLocale(lang language.Language, r language.Region) bool {
khenaidooac637102019-01-14 15:44:34 -0500663 for _, e := range paradigmLocales {
Scott Baker8461e152019-10-01 14:44:30 -0700664 if language.Language(e[0]) == lang && (r == language.Region(e[1]) || r == language.Region(e[2])) {
khenaidooac637102019-01-14 15:44:34 -0500665 return true
666 }
667 }
668 return false
669}
670
671// regionGroupDist computes the distance between two regions based on their
672// CLDR grouping.
Scott Baker8461e152019-10-01 14:44:30 -0700673func regionGroupDist(a, b language.Region, script language.Script, lang language.Language) (dist uint8, same bool) {
khenaidooac637102019-01-14 15:44:34 -0500674 const defaultDistance = 4
675
676 aGroup := uint(regionToGroups[a]) << 1
677 bGroup := uint(regionToGroups[b]) << 1
678 for _, ri := range matchRegion {
Scott Baker8461e152019-10-01 14:44:30 -0700679 if language.Language(ri.lang) == lang && (ri.script == 0 || language.Script(ri.script) == script) {
khenaidooac637102019-01-14 15:44:34 -0500680 group := uint(1 << (ri.group &^ 0x80))
681 if 0x80&ri.group == 0 {
682 if aGroup&bGroup&group != 0 { // Both regions are in the group.
683 return ri.distance, ri.distance == defaultDistance
684 }
685 } else {
686 if (aGroup|bGroup)&group == 0 { // Both regions are not in the group.
687 return ri.distance, ri.distance == defaultDistance
688 }
689 }
690 }
691 }
692 return defaultDistance, true
693}
694
khenaidooac637102019-01-14 15:44:34 -0500695// equalsRest compares everything except the language.
Scott Baker8461e152019-10-01 14:44:30 -0700696func equalsRest(a, b language.Tag) bool {
khenaidooac637102019-01-14 15:44:34 -0500697 // TODO: don't include extensions in this comparison. To do this efficiently,
698 // though, we should handle private tags separately.
Scott Baker8461e152019-10-01 14:44:30 -0700699 return a.ScriptID == b.ScriptID && a.RegionID == b.RegionID && a.VariantOrPrivateUseTags() == b.VariantOrPrivateUseTags()
khenaidooac637102019-01-14 15:44:34 -0500700}
701
702// isExactEquivalent returns true if canonicalizing the language will not alter
703// the script or region of a tag.
Scott Baker8461e152019-10-01 14:44:30 -0700704func isExactEquivalent(l language.Language) bool {
khenaidooac637102019-01-14 15:44:34 -0500705 for _, o := range notEquivalent {
706 if o == l {
707 return false
708 }
709 }
710 return true
711}
712
Scott Baker8461e152019-10-01 14:44:30 -0700713var notEquivalent []language.Language
khenaidooac637102019-01-14 15:44:34 -0500714
715func init() {
716 // Create a list of all languages for which canonicalization may alter the
717 // script or region.
Scott Baker8461e152019-10-01 14:44:30 -0700718 for _, lm := range language.AliasMap {
719 tag := language.Tag{LangID: language.Language(lm.From)}
720 if tag, _ = canonicalize(All, tag); tag.ScriptID != 0 || tag.RegionID != 0 {
721 notEquivalent = append(notEquivalent, language.Language(lm.From))
khenaidooac637102019-01-14 15:44:34 -0500722 }
723 }
724 // Maximize undefined regions of paradigm locales.
725 for i, v := range paradigmLocales {
Scott Baker8461e152019-10-01 14:44:30 -0700726 t := language.Tag{LangID: language.Language(v[0])}
727 max, _ := t.Maximize()
khenaidooac637102019-01-14 15:44:34 -0500728 if v[1] == 0 {
Scott Baker8461e152019-10-01 14:44:30 -0700729 paradigmLocales[i][1] = uint16(max.RegionID)
khenaidooac637102019-01-14 15:44:34 -0500730 }
731 if v[2] == 0 {
Scott Baker8461e152019-10-01 14:44:30 -0700732 paradigmLocales[i][2] = uint16(max.RegionID)
khenaidooac637102019-01-14 15:44:34 -0500733 }
734 }
735}