gen.go 14 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525
  1. // Copyright 2016 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. // +build ignore
  5. package main
  6. // This file generates data for the CLDR plural rules, as defined in
  7. // https://unicode.org/reports/tr35/tr35-numbers.html#Language_Plural_Rules
  8. //
  9. // We assume a slightly simplified grammar:
  10. //
  11. // condition = and_condition ('or' and_condition)* samples
  12. // and_condition = relation ('and' relation)*
  13. // relation = expr ('=' | '!=') range_list
  14. // expr = operand ('%' '10' '0'* )?
  15. // operand = 'n' | 'i' | 'f' | 't' | 'v' | 'w'
  16. // range_list = (range | value) (',' range_list)*
  17. // range = value'..'value
  18. // value = digit+
  19. // digit = 0|1|2|3|4|5|6|7|8|9
  20. //
  21. // samples = ('@integer' sampleList)?
  22. // ('@decimal' sampleList)?
  23. // sampleList = sampleRange (',' sampleRange)* (',' ('…'|'...'))?
  24. // sampleRange = decimalValue ('~' decimalValue)?
  25. // decimalValue = value ('.' value)?
  26. //
  27. // Symbol Value
  28. // n absolute value of the source number (integer and decimals).
  29. // i integer digits of n.
  30. // v number of visible fraction digits in n, with trailing zeros.
  31. // w number of visible fraction digits in n, without trailing zeros.
  32. // f visible fractional digits in n, with trailing zeros.
  33. // t visible fractional digits in n, without trailing zeros.
  34. //
  35. // The algorithm for which the data is generated is based on the following
  36. // observations
  37. //
  38. // - the number of different sets of numbers which the plural rules use to
  39. // test inclusion is limited,
  40. // - most numbers that are tested on are < 100
  41. //
  42. // This allows us to define a bitmap for each number < 100 where a bit i
  43. // indicates whether this number is included in some defined set i.
  44. // The function matchPlural in plural.go defines how we can subsequently use
  45. // this data to determine inclusion.
  46. //
  47. // There are a few languages for which this doesn't work. For one Italian and
  48. // Azerbaijan, which both test against numbers > 100 for ordinals and Breton,
  49. // which considers whether numbers are multiples of hundreds. The model here
  50. // could be extended to handle Italian and Azerbaijan fairly easily (by
  51. // considering the numbers 100, 200, 300, ..., 800, 900 in addition to the first
  52. // 100), but for now it seems easier to just hard-code these cases.
  53. import (
  54. "bufio"
  55. "bytes"
  56. "flag"
  57. "fmt"
  58. "log"
  59. "strconv"
  60. "strings"
  61. "golang.org/x/text/internal/gen"
  62. "golang.org/x/text/internal/language"
  63. "golang.org/x/text/internal/language/compact"
  64. "golang.org/x/text/unicode/cldr"
  65. )
  66. var (
  67. test = flag.Bool("test", false,
  68. "test existing tables; can be used to compare web data with package data.")
  69. outputFile = flag.String("output", "tables.go", "output file")
  70. outputTestFile = flag.String("testoutput", "data_test.go", "output file")
  71. draft = flag.String("draft",
  72. "contributed",
  73. `Minimal draft requirements (approved, contributed, provisional, unconfirmed).`)
  74. )
  75. func main() {
  76. gen.Init()
  77. const pkg = "plural"
  78. gen.Repackage("gen_common.go", "common.go", pkg)
  79. // Read the CLDR zip file.
  80. r := gen.OpenCLDRCoreZip()
  81. defer r.Close()
  82. d := &cldr.Decoder{}
  83. d.SetDirFilter("supplemental", "main")
  84. d.SetSectionFilter("numbers", "plurals")
  85. data, err := d.DecodeZip(r)
  86. if err != nil {
  87. log.Fatalf("DecodeZip: %v", err)
  88. }
  89. w := gen.NewCodeWriter()
  90. defer w.WriteGoFile(*outputFile, pkg)
  91. gen.WriteCLDRVersion(w)
  92. genPlurals(w, data)
  93. w = gen.NewCodeWriter()
  94. defer w.WriteGoFile(*outputTestFile, pkg)
  95. genPluralsTests(w, data)
  96. }
  97. type pluralTest struct {
  98. locales string // space-separated list of locales for this test
  99. form int // Use int instead of Form to simplify generation.
  100. integer []string // Entries of the form \d+ or \d+~\d+
  101. decimal []string // Entries of the form \f+ or \f+ +~\f+, where f is \d+\.\d+
  102. }
  103. func genPluralsTests(w *gen.CodeWriter, data *cldr.CLDR) {
  104. w.WriteType(pluralTest{})
  105. for _, plurals := range data.Supplemental().Plurals {
  106. if plurals.Type == "" {
  107. // The empty type is reserved for plural ranges.
  108. continue
  109. }
  110. tests := []pluralTest{}
  111. for _, pRules := range plurals.PluralRules {
  112. for _, rule := range pRules.PluralRule {
  113. test := pluralTest{
  114. locales: pRules.Locales,
  115. form: int(countMap[rule.Count]),
  116. }
  117. scan := bufio.NewScanner(strings.NewReader(rule.Data()))
  118. scan.Split(splitTokens)
  119. var p *[]string
  120. for scan.Scan() {
  121. switch t := scan.Text(); t {
  122. case "@integer":
  123. p = &test.integer
  124. case "@decimal":
  125. p = &test.decimal
  126. case ",", "…":
  127. default:
  128. if p != nil {
  129. *p = append(*p, t)
  130. }
  131. }
  132. }
  133. tests = append(tests, test)
  134. }
  135. }
  136. w.WriteVar(plurals.Type+"Tests", tests)
  137. }
  138. }
  139. func genPlurals(w *gen.CodeWriter, data *cldr.CLDR) {
  140. for _, plurals := range data.Supplemental().Plurals {
  141. if plurals.Type == "" {
  142. continue
  143. }
  144. // Initialize setMap and inclusionMasks. They are already populated with
  145. // a few entries to serve as an example and to assign nice numbers to
  146. // common cases.
  147. // setMap contains sets of numbers represented by boolean arrays where
  148. // a true value for element i means that the number i is included.
  149. setMap := map[[numN]bool]int{
  150. // The above init func adds an entry for including all numbers.
  151. [numN]bool{1: true}: 1, // fix {1} to a nice value
  152. [numN]bool{2: true}: 2, // fix {2} to a nice value
  153. [numN]bool{0: true}: 3, // fix {0} to a nice value
  154. }
  155. // inclusionMasks contains bit masks for every number under numN to
  156. // indicate in which set the number is included. Bit 1 << x will be set
  157. // if it is included in set x.
  158. inclusionMasks := [numN]uint64{
  159. // Note: these entries are not complete: more bits will be set along the way.
  160. 0: 1 << 3,
  161. 1: 1 << 1,
  162. 2: 1 << 2,
  163. }
  164. // Create set {0..99}. We will assign this set the identifier 0.
  165. var all [numN]bool
  166. for i := range all {
  167. // Mark number i as being included in the set (which has identifier 0).
  168. inclusionMasks[i] |= 1 << 0
  169. // Mark number i as included in the set.
  170. all[i] = true
  171. }
  172. // Register the identifier for the set.
  173. setMap[all] = 0
  174. rules := []pluralCheck{}
  175. index := []byte{0}
  176. langMap := map[compact.ID]byte{0: 0}
  177. for _, pRules := range plurals.PluralRules {
  178. // Parse the rules.
  179. var conds []orCondition
  180. for _, rule := range pRules.PluralRule {
  181. form := countMap[rule.Count]
  182. conds = parsePluralCondition(conds, rule.Data(), form)
  183. }
  184. // Encode the rules.
  185. for _, c := range conds {
  186. // If an or condition only has filters, we create an entry for
  187. // this filter and the set that contains all values.
  188. empty := true
  189. for _, b := range c.used {
  190. empty = empty && !b
  191. }
  192. if empty {
  193. rules = append(rules, pluralCheck{
  194. cat: byte(opMod<<opShift) | byte(c.form),
  195. setID: 0, // all values
  196. })
  197. continue
  198. }
  199. // We have some entries with values.
  200. for i, set := range c.set {
  201. if !c.used[i] {
  202. continue
  203. }
  204. index, ok := setMap[set]
  205. if !ok {
  206. index = len(setMap)
  207. setMap[set] = index
  208. for i := range inclusionMasks {
  209. if set[i] {
  210. inclusionMasks[i] |= 1 << uint64(index)
  211. }
  212. }
  213. }
  214. rules = append(rules, pluralCheck{
  215. cat: byte(i<<opShift | andNext),
  216. setID: byte(index),
  217. })
  218. }
  219. // Now set the last entry to the plural form the rule matches.
  220. rules[len(rules)-1].cat &^= formMask
  221. rules[len(rules)-1].cat |= byte(c.form)
  222. }
  223. // Point the relevant locales to the created entries.
  224. for _, loc := range strings.Split(pRules.Locales, " ") {
  225. if strings.TrimSpace(loc) == "" {
  226. continue
  227. }
  228. lang, ok := compact.FromTag(language.MustParse(loc))
  229. if !ok {
  230. log.Printf("No compact index for locale %q", loc)
  231. }
  232. langMap[lang] = byte(len(index) - 1)
  233. }
  234. index = append(index, byte(len(rules)))
  235. }
  236. w.WriteVar(plurals.Type+"Rules", rules)
  237. w.WriteVar(plurals.Type+"Index", index)
  238. // Expand the values: first by using the parent relationship.
  239. langToIndex := make([]byte, compact.NumCompactTags)
  240. for i := range langToIndex {
  241. for p := compact.ID(i); ; p = p.Parent() {
  242. if x, ok := langMap[p]; ok {
  243. langToIndex[i] = x
  244. break
  245. }
  246. }
  247. }
  248. // Now expand by including entries with identical languages for which
  249. // one isn't set.
  250. for i, v := range langToIndex {
  251. if v == 0 {
  252. id, _ := compact.FromTag(language.Tag{
  253. LangID: compact.ID(i).Tag().LangID,
  254. })
  255. if p := langToIndex[id]; p != 0 {
  256. langToIndex[i] = p
  257. }
  258. }
  259. }
  260. w.WriteVar(plurals.Type+"LangToIndex", langToIndex)
  261. // Need to convert array to slice because of golang.org/issue/7651.
  262. // This will allow tables to be dropped when unused. This is especially
  263. // relevant for the ordinal data, which I suspect won't be used as much.
  264. w.WriteVar(plurals.Type+"InclusionMasks", inclusionMasks[:])
  265. if len(rules) > 0xFF {
  266. log.Fatalf("Too many entries for rules: %#x", len(rules))
  267. }
  268. if len(index) > 0xFF {
  269. log.Fatalf("Too many entries for index: %#x", len(index))
  270. }
  271. if len(setMap) > 64 { // maximum number of bits.
  272. log.Fatalf("Too many entries for setMap: %d", len(setMap))
  273. }
  274. w.WriteComment(
  275. "Slots used for %s: %X of 0xFF rules; %X of 0xFF indexes; %d of 64 sets",
  276. plurals.Type, len(rules), len(index), len(setMap))
  277. // Prevent comment from attaching to the next entry.
  278. fmt.Fprint(w, "\n\n")
  279. }
  280. }
  281. type orCondition struct {
  282. original string // for debugging
  283. form Form
  284. used [32]bool
  285. set [32][numN]bool
  286. }
  287. func (o *orCondition) add(op opID, mod int, v []int) (ok bool) {
  288. ok = true
  289. for _, x := range v {
  290. if x >= maxMod {
  291. ok = false
  292. break
  293. }
  294. }
  295. for i := 0; i < numN; i++ {
  296. m := i
  297. if mod != 0 {
  298. m = i % mod
  299. }
  300. if !intIn(m, v) {
  301. o.set[op][i] = false
  302. }
  303. }
  304. if ok {
  305. o.used[op] = true
  306. }
  307. return ok
  308. }
  309. func intIn(x int, a []int) bool {
  310. for _, y := range a {
  311. if x == y {
  312. return true
  313. }
  314. }
  315. return false
  316. }
  317. var operandIndex = map[string]opID{
  318. "i": opI,
  319. "n": opN,
  320. "f": opF,
  321. "v": opV,
  322. "w": opW,
  323. }
  324. // parsePluralCondition parses the condition of a single pluralRule and appends
  325. // the resulting or conditions to conds.
  326. //
  327. // Example rules:
  328. // // Category "one" in English: only allow 1 with no visible fraction
  329. // i = 1 and v = 0 @integer 1
  330. //
  331. // // Category "few" in Czech: all numbers with visible fractions
  332. // v != 0 @decimal ...
  333. //
  334. // // Category "zero" in Latvian: all multiples of 10 or the numbers 11-19 or
  335. // // numbers with a fraction 11..19 and no trailing zeros.
  336. // n % 10 = 0 or n % 100 = 11..19 or v = 2 and f % 100 = 11..19 @integer ...
  337. //
  338. // @integer and @decimal are followed by examples and are not relevant for the
  339. // rule itself. The are used here to signal the termination of the rule.
  340. func parsePluralCondition(conds []orCondition, s string, f Form) []orCondition {
  341. scan := bufio.NewScanner(strings.NewReader(s))
  342. scan.Split(splitTokens)
  343. for {
  344. cond := orCondition{original: s, form: f}
  345. // Set all numbers to be allowed for all number classes and restrict
  346. // from here on.
  347. for i := range cond.set {
  348. for j := range cond.set[i] {
  349. cond.set[i][j] = true
  350. }
  351. }
  352. andLoop:
  353. for {
  354. var token string
  355. scan.Scan() // Must exist.
  356. switch class := scan.Text(); class {
  357. case "t":
  358. class = "w" // equal to w for t == 0
  359. fallthrough
  360. case "n", "i", "f", "v", "w":
  361. op := scanToken(scan)
  362. opCode := operandIndex[class]
  363. mod := 0
  364. if op == "%" {
  365. opCode |= opMod
  366. switch v := scanUint(scan); v {
  367. case 10, 100:
  368. mod = v
  369. case 1000:
  370. // A more general solution would be to allow checking
  371. // against multiples of 100 and include entries for the
  372. // numbers 100..900 in the inclusion masks. At the
  373. // moment this would only help Azerbaijan and Italian.
  374. // Italian doesn't use '%', so this must be Azerbaijan.
  375. cond.used[opAzerbaijan00s] = true
  376. return append(conds, cond)
  377. case 1000000:
  378. cond.used[opBretonM] = true
  379. return append(conds, cond)
  380. default:
  381. log.Fatalf("Modulo value not supported %d", v)
  382. }
  383. op = scanToken(scan)
  384. }
  385. if op != "=" && op != "!=" {
  386. log.Fatalf("Unexpected op %q", op)
  387. }
  388. if op == "!=" {
  389. opCode |= opNotEqual
  390. }
  391. a := []int{}
  392. v := scanUint(scan)
  393. if class == "w" && v != 0 {
  394. log.Fatalf("Must compare against zero for operand type %q", class)
  395. }
  396. token = scanToken(scan)
  397. for {
  398. switch token {
  399. case "..":
  400. end := scanUint(scan)
  401. for ; v <= end; v++ {
  402. a = append(a, v)
  403. }
  404. token = scanToken(scan)
  405. default: // ",", "or", "and", "@..."
  406. a = append(a, v)
  407. }
  408. if token != "," {
  409. break
  410. }
  411. v = scanUint(scan)
  412. token = scanToken(scan)
  413. }
  414. if !cond.add(opCode, mod, a) {
  415. // Detected large numbers. As we ruled out Azerbaijan, this
  416. // must be the many rule for Italian ordinals.
  417. cond.set[opItalian800] = cond.set[opN]
  418. cond.used[opItalian800] = true
  419. }
  420. case "@integer", "@decimal": // "other" entry: tests only.
  421. return conds
  422. default:
  423. log.Fatalf("Unexpected operand class %q (%s)", class, s)
  424. }
  425. switch token {
  426. case "or":
  427. conds = append(conds, cond)
  428. break andLoop
  429. case "@integer", "@decimal": // examples
  430. // There is always an example in practice, so we always terminate here.
  431. if err := scan.Err(); err != nil {
  432. log.Fatal(err)
  433. }
  434. return append(conds, cond)
  435. case "and":
  436. // keep accumulating
  437. default:
  438. log.Fatalf("Unexpected token %q", token)
  439. }
  440. }
  441. }
  442. }
  443. func scanToken(scan *bufio.Scanner) string {
  444. scan.Scan()
  445. return scan.Text()
  446. }
  447. func scanUint(scan *bufio.Scanner) int {
  448. scan.Scan()
  449. val, err := strconv.ParseUint(scan.Text(), 10, 32)
  450. if err != nil {
  451. log.Fatal(err)
  452. }
  453. return int(val)
  454. }
  455. // splitTokens can be used with bufio.Scanner to tokenize CLDR plural rules.
  456. func splitTokens(data []byte, atEOF bool) (advance int, token []byte, err error) {
  457. condTokens := [][]byte{
  458. []byte(".."),
  459. []byte(","),
  460. []byte("!="),
  461. []byte("="),
  462. }
  463. advance, token, err = bufio.ScanWords(data, atEOF)
  464. for _, t := range condTokens {
  465. if len(t) >= len(token) {
  466. continue
  467. }
  468. switch p := bytes.Index(token, t); {
  469. case p == -1:
  470. case p == 0:
  471. advance = len(t)
  472. token = token[:len(t)]
  473. return advance - len(token) + len(t), token[:len(t)], err
  474. case p < advance:
  475. // Don't split when "=" overlaps "!=".
  476. if t[0] == '=' && token[p-1] == '!' {
  477. continue
  478. }
  479. advance = p
  480. token = token[:p]
  481. }
  482. }
  483. return advance, token, err
  484. }