Scott Baker | 2d89798 | 2019-09-24 11:50:08 -0700 | [diff] [blame] | 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 | |
| 5 | package language |
| 6 | |
| 7 | import "errors" |
| 8 | |
| 9 | // A MatchOption configures a Matcher. |
| 10 | type 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. |
| 15 | func 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. |
| 28 | func 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. |
| 47 | type 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. |
| 53 | func 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. |
| 72 | func NewMatcher(t []Tag, options ...MatchOption) Matcher { |
| 73 | return newMatcher(t, options) |
| 74 | } |
| 75 | |
| 76 | func (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 | |
| 115 | type scriptRegionFlags uint8 |
| 116 | |
| 117 | const ( |
| 118 | isList = 1 << iota |
| 119 | scriptInFrom |
| 120 | regionInFrom |
| 121 | ) |
| 122 | |
| 123 | func (t *Tag) setUndefinedLang(id langID) { |
| 124 | if t.lang == 0 { |
| 125 | t.lang = id |
| 126 | } |
| 127 | } |
| 128 | |
| 129 | func (t *Tag) setUndefinedScript(id scriptID) { |
| 130 | if t.script == 0 { |
| 131 | t.script = id |
| 132 | } |
| 133 | } |
| 134 | |
| 135 | func (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. |
| 143 | var 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. |
| 149 | func (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. |
| 161 | func 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 | |
| 172 | func 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 | |
| 290 | func (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(). |
| 298 | func (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. |
| 308 | func 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. |
| 441 | type 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. |
| 451 | type 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. |
| 458 | type 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 | |
| 481 | func 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. |
| 494 | func 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. |
| 507 | func (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. |
| 533 | func (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 | |
| 542 | func 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. |
| 555 | func 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. |
| 638 | func (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. |
| 708 | type 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. |
| 737 | func (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 | |
| 846 | func 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. |
| 857 | func 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 | |
| 879 | func (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. |
| 887 | func (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. |
| 895 | func (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. |
| 903 | func isExactEquivalent(l langID) bool { |
| 904 | for _, o := range notEquivalent { |
| 905 | if o == l { |
| 906 | return false |
| 907 | } |
| 908 | } |
| 909 | return true |
| 910 | } |
| 911 | |
| 912 | var notEquivalent []langID |
| 913 | |
| 914 | func 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 | } |