language: improve compliance of matcher
- fix und-TW bug
- remove region distance
- deemphasizes exact matches:
Most people are not fully bilingual so a language
in first position should be a strong preference.
User may still define bilingual support by explicitly
ordering second language among dialects
Change-Id: I2ee8721e11764370e4f937fd2ee979586b1aa1a5
Reviewed-on: https://go-review.googlesource.com/55750
Run-TryBot: Marcel van Lohuizen <mpvl@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Nigel Tao <nigeltao@golang.org>
diff --git a/language/examples_test.go b/language/examples_test.go
index e20c225..8655699 100644
--- a/language/examples_test.go
+++ b/language/examples_test.go
@@ -331,11 +331,13 @@
// af 3 High
// ----
// iw 9 Exact
- // iw-IL 8 Exact
+ // he 10 Exact
// ----
// fr-u-cu-frf 2 Exact
// fr-u-cu-frf 2 High
// en-u-co-phonebk 0 No
+
+ // TODO: "he" should be "he-u-rg-IL High"
}
func ExampleComprehends() {
diff --git a/language/match.go b/language/match.go
index 16128a4..2f14436 100644
--- a/language/match.go
+++ b/language/match.go
@@ -331,8 +331,9 @@
// 1) compute the match between the two tags.
// 2) if the match is better than the previous best match, replace it
// with the new match. (see next section)
-// b) if the current best match is above a certain threshold, return this
-// match without proceeding to the next tag in "desired". [See Note 1]
+// b) if the current best match is Exact and pin is true the result will be
+// frozen to the language found thusfar, although better matches may
+// still be found for the same language.
// 3) If the best match so far is below a certain threshold, return "default".
//
// Ranking:
@@ -381,9 +382,6 @@
// found wins.
//
// Notes:
-// [1] Note that even if we may not have a perfect match, if a match is above a
-// certain threshold, it is considered a better match than any other match
-// to a tag later in the list of preferred language tags.
// [2] In practice, as matching of Exact is done in a separate phase from
// matching the other levels, we reuse the Exact level to mean MaxExact in
// the second phase. As a consequence, we only need the levels defined by
@@ -429,8 +427,8 @@
// matchHeader has the lists of tags for exact matches and matches based on
// maximized and canonicalized tags for a given language.
type matchHeader struct {
- exact []*haveTag
- max []*haveTag
+ haveTags []*haveTag
+ original bool
}
// haveTag holds a supported Tag and its maximized script and region. The maximized
@@ -460,7 +458,7 @@
func makeHaveTag(tag Tag, index int) (haveTag, langID) {
max := tag
- if tag.lang != 0 {
+ if tag.lang != 0 || tag.region != 0 || tag.script != 0 {
max, _ = max.canonicalize(All)
max, _ = addTags(max)
max.remakeString()
@@ -485,29 +483,27 @@
// addIfNew adds a haveTag to the list of tags only if it is a unique tag.
// Tags that have the same maximized values are linked by index.
func (h *matchHeader) addIfNew(n haveTag, exact bool) {
+ h.original = h.original || exact
// Don't add new exact matches.
- for _, v := range h.exact {
+ for _, v := range h.haveTags {
if v.tag.equalsRest(n.tag) {
return
}
}
- if exact {
- h.exact = append(h.exact, &n)
- }
// Allow duplicate maximized tags, but create a linked list to allow quickly
// comparing the equivalents and bail out.
- for i, v := range h.max {
+ for i, v := range h.haveTags {
if v.maxScript == n.maxScript &&
v.maxRegion == n.maxRegion &&
v.tag.variantOrPrivateTagStr() == n.tag.variantOrPrivateTagStr() {
- for h.max[i].nextMax != 0 {
- i = int(h.max[i].nextMax)
+ for h.haveTags[i].nextMax != 0 {
+ i = int(h.haveTags[i].nextMax)
}
- h.max[i].nextMax = uint16(len(h.max))
+ h.haveTags[i].nextMax = uint16(len(h.haveTags))
break
}
}
- h.max = append(h.max, &n)
+ h.haveTags = append(h.haveTags, &n)
}
// header returns the matchHeader for the given language. It creates one if
@@ -553,11 +549,13 @@
m.header(tag.lang).addIfNew(pair, true)
m.supported = append(m.supported, &pair)
}
- m.default_ = m.header(supported[0].lang).exact[0]
+ m.default_ = m.header(supported[0].lang).haveTags[0]
+ // Keep these in two different loops to support the case that two equivalent
+ // languages are distinguished, such as iw and he.
for i, tag := range supported {
pair, max := makeHaveTag(tag, i)
if max != tag.lang {
- m.header(max).addIfNew(pair, false)
+ m.header(max).addIfNew(pair, true)
}
}
@@ -565,15 +563,15 @@
// - don't replace regions, but allow regions to be made more specific.
// update is used to add indexes in the map for equivalent languages.
- // If force is true, the update will also apply to derived entries. To
- // avoid applying a "transitive closure", use false.
- update := func(want, have uint16, conf Confidence, force bool) {
+ // update will only add entries to original indexes, thus not computing any
+ // transitive relations.
+ update := func(want, have uint16, conf Confidence) {
if hh := m.index[langID(have)]; hh != nil {
- if !force && len(hh.exact) == 0 {
+ if !hh.original {
return
}
hw := m.header(langID(want))
- for _, ht := range hh.max {
+ for _, ht := range hh.haveTags {
v := *ht
if conf < v.conf {
v.conf = conf
@@ -582,7 +580,7 @@
if v.altScript != 0 {
v.altScript = altScript(langID(want), v.maxScript)
}
- hw.addIfNew(v, conf == Exact && len(hh.exact) > 0)
+ hw.addIfNew(v, conf == Exact && hh.original)
}
}
}
@@ -590,9 +588,9 @@
// Add entries for languages with mutual intelligibility as defined by CLDR's
// languageMatch data.
for _, ml := range matchLang {
- update(ml.want, ml.have, toConf(ml.distance), false)
+ update(ml.want, ml.have, toConf(ml.distance))
if !ml.oneway {
- update(ml.have, ml.want, toConf(ml.distance), false)
+ update(ml.have, ml.want, toConf(ml.distance))
}
}
@@ -609,9 +607,9 @@
if !isExactEquivalent(langID(lm.from)) {
conf = High
}
- update(lm.to, lm.from, conf, true)
+ update(lm.to, lm.from, conf)
}
- update(lm.from, lm.to, conf, true)
+ update(lm.from, lm.to, conf)
}
return m
}
@@ -620,28 +618,29 @@
// account the order of preference of the given tags.
func (m *matcher) getBest(want ...Tag) (got *haveTag, orig Tag, c Confidence) {
best := bestMatch{}
- for _, w := range want {
+ for i, w := range want {
var max Tag
// Check for exact match first.
h := m.index[w.lang]
if w.lang != 0 {
- // Base language is defined.
if h == nil {
continue
}
- for i := range h.exact {
- have := h.exact[i]
- if have.tag.equalsRest(w) {
- return have, w, Exact
- }
+ // Base language is defined.
+ max, _ = w.canonicalize(Legacy | Deprecated | Macro)
+ // A region that is added through canonicalization is stronger than
+ // a maximized region: set it in the original (e.g. mo -> ro-MD).
+ if w.region != max.region {
+ w.region = max.region
}
- max, _ = w.canonicalize(Legacy | Deprecated)
+ // TODO: should we do the same for scripts?
+ // See test case: en, sr, nl ; sh ; sr
max, _ = addTags(max)
} else {
// Base language is not defined.
if h != nil {
- for i := range h.exact {
- have := h.exact[i]
+ for i := range h.haveTags {
+ have := h.haveTags[i]
if have.tag.equalsRest(w) {
return have, w, Exact
}
@@ -657,16 +656,23 @@
continue
}
}
+ pin := true
+ for _, t := range want[i+1:] {
+ if w.lang == t.lang {
+ pin = false
+ break
+ }
+ }
// Check for match based on maximized tag.
- for i := range h.max {
- have := h.max[i]
- best.update(have, w, max.script, max.region)
+ for i := range h.haveTags {
+ have := h.haveTags[i]
+ best.update(have, w, max.script, max.region, pin)
if best.conf == Exact {
for have.nextMax != 0 {
- have = h.max[have.nextMax]
- best.update(have, w, max.script, max.region)
+ have = h.haveTags[have.nextMax]
+ best.update(have, w, max.script, max.region, pin)
}
- return best.have, best.want, High
+ return best.have, best.want, best.conf
}
}
}
@@ -681,35 +687,51 @@
// bestMatch accumulates the best match so far.
type bestMatch struct {
- have *haveTag
- want Tag
- conf Confidence
+ have *haveTag
+ want Tag
+ conf Confidence
+ pinLanguage bool
// Cached results from applying tie-breaking rules.
origLang bool
origReg bool
regGroupDist uint8
- regDist uint8
origScript bool
parentDist uint8 // 255 if have is not an ancestor of want tag.
}
// update updates the existing best match if the new pair is considered to be a
-// better match.
-// To determine if the given pair is a better match, it first computes the rough
-// confidence level. If this surpasses the current match, it will replace it and
-// update the tie-breaker rule cache. If there is a tie, it proceeds with applying
-// a series of tie-breaker rules. If there is no conclusive winner after applying
-// the tie-breaker rules, it leaves the current match as the preferred match.
-func (m *bestMatch) update(have *haveTag, tag Tag, maxScript scriptID, maxRegion regionID) {
+// better match. To determine if the given pair is a better match, it first
+// computes the rough confidence level. If this surpasses the current match, it
+// will replace it and update the tie-breaker rule cache. If there is a tie, it
+// proceeds with applying a series of tie-breaker rules. If there is no
+// conclusive winner after applying the tie-breaker rules, it leaves the current
+// match as the preferred match.
+//
+// If pin is true and have and tag are a strong match, it will henceforth only
+// consider matches for this language. This corresponds to the nothing that most
+// users have a strong preference for the first defined language. A user can
+// still prefer a second language over a dialect of the preferred language by
+// explicitly specifying dialects, e.g. "en, nl, en-GB". In this case pin should
+// be false.
+func (m *bestMatch) update(have *haveTag, tag Tag, maxScript scriptID, maxRegion regionID, pin bool) {
// Bail if the maximum attainable confidence is below that of the current best match.
c := have.conf
if c < m.conf {
return
}
- if have.maxScript != maxScript {
+ // Don't change the language once we already have found an exact match.
+ if m.pinLanguage && tag.lang != m.want.lang {
+ return
+ }
+ if c == Exact && have.tag.script == tag.script {
+ m.pinLanguage = pin
+ }
+ if have.tag.equalsRest(tag) {
+ } else if have.maxScript != maxScript {
+ // fmt.Println("FFFFF", maxScript, have.maxScript)
// There is usually very little comprehension between different scripts.
- // In a few cases there may still be Low comprehension. This possibility is
- // pre-computed and stored in have.altScript.
+ // In a few cases there may still be Low comprehension. This possibility
+ // is pre-computed and stored in have.altScript.
if Low < m.conf || have.altScript != maxScript {
return
}
@@ -761,29 +783,6 @@
beaten = true
}
- // TODO: remove the region distance rule. Region distance has been replaced
- // by the region grouping rule. For now we leave it as it still seems to
- // have a net positive effect when applied after the grouping rule.
- // Possible solutions:
- // - apply the primary locale rule first to effectively disable region
- // region distance if groups are defined.
- // - express the following errors in terms of grouping (if possible)
- // - find another method of handling the following cases.
- // maximization of legacy: find mo in
- // "sr-Cyrl, sr-Latn, ro, ro-MD": have ro; want ro-MD (High)
- // region distance French: find fr-US in
- // "en, fr, fr-CA, fr-CH": have fr; want fr-CA (High)
-
- // Next we prefer smaller distances between regions, as defined by
- // regionDist.
- regDist := uint8(regionDistance(have.maxRegion, maxRegion))
- if !beaten && m.regDist != regDist {
- if regDist > m.regDist {
- return
- }
- beaten = true
- }
-
// Next we prefer if the pre-maximized script was specified and identical.
origScript := have.tag.script == tag.script && tag.script != 0
if !beaten && m.origScript != origScript {
@@ -793,10 +792,7 @@
beaten = true
}
- // Finally we prefer tags which have a closer parent relationship.
- // TODO: the parent relationship no longer seems necessary. It doesn't hurt
- // to leave it in as the final tie-breaker, though, especially until the
- // grouping data has further matured.
+ // TODO: remove parent distance once primary locales are implemented.
parentDist := parentDistance(have.tag.region, tag)
if !beaten && m.parentDist != parentDist {
if parentDist > m.parentDist {
@@ -814,7 +810,6 @@
m.origReg = origReg
m.origScript = origScript
m.regGroupDist = regGroupDist
- m.regDist = regDist
m.parentDist = parentDist
}
}
@@ -859,29 +854,6 @@
return defaultDistance
}
-// regionDistance computes the distance between two regions based on the
-// distance in the graph of region containments as defined in CLDR. It iterates
-// over increasingly inclusive sets of groups, represented as bit vectors, until
-// the source bit vector has bits in common with the destination vector.
-func regionDistance(a, b regionID) int {
- if a == b {
- return 0
- }
- p, q := regionInclusion[a], regionInclusion[b]
- if p < nRegionGroups {
- p, q = q, p
- }
- set := regionInclusionBits
- if q < nRegionGroups && set[p]&(1<<q) != 0 {
- return 1
- }
- d := 2
- for goal := set[q]; set[p]&goal == 0; p = regionInclusionNext[p] {
- d++
- }
- return d
-}
-
func (t Tag) variants() string {
if t.pVariant == 0 {
return ""
diff --git a/language/match_test.go b/language/match_test.go
index ae9a2f6..ca77115 100644
--- a/language/match_test.go
+++ b/language/match_test.go
@@ -37,16 +37,16 @@
t.Run(info.Name()+"/"+name, func(t *testing.T) {
supported := makeTagList(p.String(0))
desired := makeTagList(p.String(1))
- gotCombined, index, _ := NewMatcher(supported).Match(desired...)
+ gotCombined, index, conf := NewMatcher(supported).Match(desired...)
gotMatch := supported[index]
wantMatch := mk(p.String(2))
if gotMatch != wantMatch {
- t.Fatalf("match: got %q; want %q", gotMatch, wantMatch)
+ t.Fatalf("match: got %q; want %q (%v)", gotMatch, wantMatch, conf)
}
wantCombined, err := Raw.Parse(p.String(3))
if err == nil && gotCombined != wantCombined {
- t.Errorf("combined: got %q; want %q", gotCombined, wantCombined)
+ t.Errorf("combined: got %q; want %q (%v)", gotCombined, wantCombined, conf)
}
})
})
@@ -56,9 +56,6 @@
var skip = map[string]bool{
// TODO: bugs
- // und-<region> is not expanded to the appropriate language.
- "en-Hant-TW,und-TW/zh-Hant": true, // match: got "en-Hant-TW"; want "und-TW"
- "en-Hant-TW,und-TW/zh": true, // match: got "en-Hant-TW"; want "und-TW"
// Honor the wildcard match. This may only be useful to select non-exact
// stuff.
"mul,af/nl": true, // match: got "af"; want "mul"
@@ -67,17 +64,17 @@
// combined: got "en-GB-u-ca-buddhist-nu-arab"; want "en-GB-fonipa-t-m0-iso-i0-pinyin-u-ca-buddhist-nu-arab"
"und,en-GB-u-sd-gbsct/en-fonipa-u-nu-Arab-ca-buddhist-t-m0-iso-i0-pinyin": true,
- // Inconsistencies with Mark Davis' implementation where it is not clear
- // which is better.
-
// Go prefers exact matches over less exact preferred ones.
// Preferring desired ones might be better.
- "en,de,fr,ja/de-CH,fr": true, // match: got "fr"; want "de"
- "en-GB,en,de,fr,ja/de-CH,fr": true, // match: got "fr"; want "de"
+ // NOTE: allow users to distinguish languages is a good solution.
+ // the remaining cases are due to preferred locale rules.
"pt-PT,pt-BR,es,es-419/pt-US,pt-PT": true, // match: got "pt-PT"; want "pt-BR"
"pt-PT,pt,es,es-419/pt-US,pt-PT,pt": true, // match: got "pt-PT"; want "pt"
- "en,sv/en-GB,sv": true, // match: got "sv"; want "en"
- "en-NZ,en-IT/en-US": true, // match: got "en-IT"; want "en-NZ"
+ // TODO: implement prefer primary locales.
+ "und,en,en-GU,en-IN,en-GB/en-ZA": true, // match: got "en-IN"; want "en-GB"
+
+ // Inconsistencies with Mark Davis' implementation where it is not clear
+ // which is better.
// Inconsistencies in combined. I think the Go approach is more appropriate.
// We could use -u-rg- and -u-va- as alternative.
@@ -87,20 +84,8 @@
"und,no/nn-BE-fonipa": true, // combined: got "no"; want "no-BE-fonipa"
"50,und,fr-CA-fonupa/fr-BE-fonipa": true, // combined: got "fr-CA-fonupa"; want "fr-BE-fonipa"
- // Spec says prefer primary locales. But what is the benefit? Shouldn't
- // the developer just not specify the primary locale first in the list?
- // TODO: consider adding a SortByPreferredLocale function to ensure tags
- // are ordered such that the preferred locale rule is observed.
- // TODO: most of these cases are solved by getting rid of the region
- // distance tie-breaker rule (see comments there).
- "und,es,es-MA,es-MX,es-419/es-EA": true, // match: got "es-MA"; want "es"
- "und,es-MA,es,es-419,es-MX/es-EA": true, // match: got "es-MA"; want "es"
- "und,en,en-GU,en-IN,en-GB/en-ZA": true, // match: got "en-IN"; want "en-GB"
- "und,en,en-GU,en-IN,en-GB/en-VI": true, // match: got "en-GU"; want "en"
- "und,en-GU,en,en-GB,en-IN/en-VI": true, // match: got "en-GU"; want "en"
-
- // Falling back to the default seems more appropriate than falling back
- // on a language with the same script.
+ // The initial number is a threshold. As we don't use scoring, we will not
+ // implement this.
"50,und,fr-Cyrl-CA-fonupa/fr-BE-fonipa": true,
// match: got "und"; want "fr-Cyrl-CA-fonupa"
// combined: got "und"; want "fr-Cyrl-BE-fonipa"
@@ -139,6 +124,7 @@
{"und-YT", "fr-Latn-YT"},
{"und-Arab", "ar-Arab-EG"},
{"und-AM", "hy-Armn-AM"},
+ {"und-TW", "zh-Hant-TW"},
{"und-002", "en-Latn-NG"},
{"und-Latn-002", "en-Latn-NG"},
{"en-Latn-002", "en-Latn-NG"},
@@ -291,40 +277,6 @@
}
}
-func TestRegionDistance(t *testing.T) {
- tests := []struct {
- a, b string
- d int
- }{
- {"NL", "NL", 0},
- {"NL", "EU", 1},
- {"EU", "NL", 1},
- {"005", "005", 0},
- {"NL", "BE", 2},
- {"CO", "005", 1},
- {"005", "CO", 1},
- {"CO", "419", 2},
- {"419", "CO", 2},
- {"005", "419", 1},
- {"419", "005", 1},
- {"001", "013", 2},
- {"013", "001", 2},
- {"CO", "CW", 4},
- {"CO", "PW", 6},
- {"CO", "BV", 6},
- {"ZZ", "QQ", 2},
- }
- for i, tt := range tests {
- testtext.Run(t, tt.a+"/"+tt.b, func(t *testing.T) {
- ra, _ := getRegionID([]byte(tt.a))
- rb, _ := getRegionID([]byte(tt.b))
- if d := regionDistance(ra, rb); d != tt.d {
- t.Errorf("%d: d(%s, %s) = %v; want %v", i, tt.a, tt.b, d, tt.d)
- }
- })
- }
-}
-
func TestParentDistance(t *testing.T) {
tests := []struct {
parent string
@@ -362,12 +314,8 @@
func (h *matchHeader) String() string {
w := &bytes.Buffer{}
- fmt.Fprintf(w, "exact: ")
- for _, h := range h.exact {
- fmt.Fprintf(w, "%v, ", h)
- }
- fmt.Fprint(w, "; max: ")
- for _, h := range h.max {
+ fmt.Fprint(w, "haveTag: ")
+ for _, h := range h.haveTags {
fmt.Fprintf(w, "%v, ", h)
}
return w.String()
diff --git a/language/testdata/GoLocaleMatcherTest.txt b/language/testdata/GoLocaleMatcherTest.txt
index 7817979..cc42009 100644
--- a/language/testdata/GoLocaleMatcherTest.txt
+++ b/language/testdata/GoLocaleMatcherTest.txt
@@ -13,7 +13,7 @@
# language-specific script fallbacks 1
en, sr, nl ; sr-Latn ; sr
-en, sr, nl ; sh ; en
+en, sr, nl ; sh ; sr # different script, but seems okay and is as CLDR suggests
en, sr, nl ; hr ; en
en, sr, nl ; bs ; en
en, sr, nl ; nl-Cyrl ; sr
@@ -66,7 +66,7 @@
# legacy equivalent is closer than same language with other differences
nl, fil, en-GB ; tl, en-US ; fil
-# exact over equivalent
+# distinguish near equivalents
en, ro, mo, ro-MD ; ro ; ro
en, ro, mo, ro-MD ; mo ; mo
en, ro, mo, ro-MD ; ro-MD ; ro-MD
@@ -87,8 +87,6 @@
fr, i-klingon, en-Latn-US ; en-GB-oed ; en-Latn-US
fr, i-klingon, en-Latn-US ; i-klingon ; tlh
-# exact match
-fr, en-GB, ja, es-ES, es-MX ; ja, de ; ja
# simple variant match
fr, en-GB, ja, es-ES, es-MX ; de, en-US ; en-GB
@@ -126,8 +124,8 @@
# region distance Portuguese
pt, pt-PT ; pt-ES ; pt-PT
-# region distance French
-en, fr, fr-CA, fr-CH ; fr-US ; fr-CA
+# if no preferred locale specified, pick top language, not regional
+en, fr, fr-CA, fr-CH ; fr-US ; fr #TODO: ; fr-u-rg-US
# region distance German
de-AT, de-DE, de-CH ; de ; de-DE
@@ -167,8 +165,11 @@
ja, ja-Jpan, ja-JP, en, ru ; ja-Jpan-JP, ru ; ja-JP
ja, ja-Jpan, ja-JP, en, ru ; ja-Jpan, ru ; ja-Jpan
-# no match on maximized
-en, de, fr, ja ; de-CH, fr ; fr
+# same language over exact, but distinguish when user is explicit
+fr, en-GB, ja, es-ES, es-MX ; ja, de ; ja
+en, de, fr, ja ; de-CH, fr ; de # TODO: ; de-u-rg-CH
+en-GB, nl ; en, nl ; en-GB
+en-GB, nl ; en, nl, en-GB ; nl
# parent relation preserved
en, en-US, en-GB, es, es-419, pt, pt-BR, pt-PT, zh, zh-Hant, zh-Hant-HK ; en-150 ; en-GB
