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 (
8
	"bytes"
9
	"errors"
10
	"fmt"
11
	"sort"
12

13
	"golang.org/x/text/internal/tag"
14
)
15

16
// isAlpha returns true if the byte is not a digit.
17
// b must be an ASCII letter or digit.
18
func isAlpha(b byte) bool {
19
	return b > '9'
20
}
21

22
// isAlphaNum returns true if the string contains only ASCII letters or digits.
23
func isAlphaNum(s []byte) bool {
24
	for _, c := range s {
25
		if !('a' <= c && c <= 'z' || 'A' <= c && c <= 'Z' || '0' <= c && c <= '9') {
26
			return false
27
		}
28
	}
29
	return true
30
}
31

32
// ErrSyntax is returned by any of the parsing functions when the
33
// input is not well-formed, according to BCP 47.
34
// TODO: return the position at which the syntax error occurred?
35
var ErrSyntax = errors.New("language: tag is not well-formed")
36

37
// ErrDuplicateKey is returned when a tag contains the same key twice with
38
// different values in the -u section.
39
var ErrDuplicateKey = errors.New("language: different values for same key in -u extension")
40

41
// ValueError is returned by any of the parsing functions when the
42
// input is well-formed but the respective subtag is not recognized
43
// as a valid value.
44
type ValueError struct {
45
	v [8]byte
46
}
47

48
// NewValueError creates a new ValueError.
49
func NewValueError(tag []byte) ValueError {
50
	var e ValueError
51
	copy(e.v[:], tag)
52
	return e
53
}
54

55
func (e ValueError) tag() []byte {
56
	n := bytes.IndexByte(e.v[:], 0)
57
	if n == -1 {
58
		n = 8
59
	}
60
	return e.v[:n]
61
}
62

63
// Error implements the error interface.
64
func (e ValueError) Error() string {
65
	return fmt.Sprintf("language: subtag %q is well-formed but unknown", e.tag())
66
}
67

68
// Subtag returns the subtag for which the error occurred.
69
func (e ValueError) Subtag() string {
70
	return string(e.tag())
71
}
72

73
// scanner is used to scan BCP 47 tokens, which are separated by _ or -.
74
type scanner struct {
75
	b     []byte
76
	bytes [max99thPercentileSize]byte
77
	token []byte
78
	start int // start position of the current token
79
	end   int // end position of the current token
80
	next  int // next point for scan
81
	err   error
82
	done  bool
83
}
84

85
func makeScannerString(s string) scanner {
86
	scan := scanner{}
87
	if len(s) <= len(scan.bytes) {
88
		scan.b = scan.bytes[:copy(scan.bytes[:], s)]
89
	} else {
90
		scan.b = []byte(s)
91
	}
92
	scan.init()
93
	return scan
94
}
95

96
// makeScanner returns a scanner using b as the input buffer.
97
// b is not copied and may be modified by the scanner routines.
98
func makeScanner(b []byte) scanner {
99
	scan := scanner{b: b}
100
	scan.init()
101
	return scan
102
}
103

104
func (s *scanner) init() {
105
	for i, c := range s.b {
106
		if c == '_' {
107
			s.b[i] = '-'
108
		}
109
	}
110
	s.scan()
111
}
112

113
// restToLower converts the string between start and end to lower case.
114
func (s *scanner) toLower(start, end int) {
115
	for i := start; i < end; i++ {
116
		c := s.b[i]
117
		if 'A' <= c && c <= 'Z' {
118
			s.b[i] += 'a' - 'A'
119
		}
120
	}
121
}
122

123
func (s *scanner) setError(e error) {
124
	if s.err == nil || (e == ErrSyntax && s.err != ErrSyntax) {
125
		s.err = e
126
	}
127
}
128

129
// resizeRange shrinks or grows the array at position oldStart such that
130
// a new string of size newSize can fit between oldStart and oldEnd.
131
// Sets the scan point to after the resized range.
132
func (s *scanner) resizeRange(oldStart, oldEnd, newSize int) {
133
	s.start = oldStart
134
	if end := oldStart + newSize; end != oldEnd {
135
		diff := end - oldEnd
136
		var b []byte
137
		if n := len(s.b) + diff; n > cap(s.b) {
138
			b = make([]byte, n)
139
			copy(b, s.b[:oldStart])
140
		} else {
141
			b = s.b[:n]
142
		}
143
		copy(b[end:], s.b[oldEnd:])
144
		s.b = b
145
		s.next = end + (s.next - s.end)
146
		s.end = end
147
	}
148
}
149

150
// replace replaces the current token with repl.
151
func (s *scanner) replace(repl string) {
152
	s.resizeRange(s.start, s.end, len(repl))
153
	copy(s.b[s.start:], repl)
154
}
155

156
// gobble removes the current token from the input.
157
// Caller must call scan after calling gobble.
158
func (s *scanner) gobble(e error) {
159
	s.setError(e)
160
	if s.start == 0 {
161
		s.b = s.b[:+copy(s.b, s.b[s.next:])]
162
		s.end = 0
163
	} else {
164
		s.b = s.b[:s.start-1+copy(s.b[s.start-1:], s.b[s.end:])]
165
		s.end = s.start - 1
166
	}
167
	s.next = s.start
168
}
169

170
// deleteRange removes the given range from s.b before the current token.
171
func (s *scanner) deleteRange(start, end int) {
172
	s.b = s.b[:start+copy(s.b[start:], s.b[end:])]
173
	diff := end - start
174
	s.next -= diff
175
	s.start -= diff
176
	s.end -= diff
177
}
178

179
// scan parses the next token of a BCP 47 string.  Tokens that are larger
180
// than 8 characters or include non-alphanumeric characters result in an error
181
// and are gobbled and removed from the output.
182
// It returns the end position of the last token consumed.
183
func (s *scanner) scan() (end int) {
184
	end = s.end
185
	s.token = nil
186
	for s.start = s.next; s.next < len(s.b); {
187
		i := bytes.IndexByte(s.b[s.next:], '-')
188
		if i == -1 {
189
			s.end = len(s.b)
190
			s.next = len(s.b)
191
			i = s.end - s.start
192
		} else {
193
			s.end = s.next + i
194
			s.next = s.end + 1
195
		}
196
		token := s.b[s.start:s.end]
197
		if i < 1 || i > 8 || !isAlphaNum(token) {
198
			s.gobble(ErrSyntax)
199
			continue
200
		}
201
		s.token = token
202
		return end
203
	}
204
	if n := len(s.b); n > 0 && s.b[n-1] == '-' {
205
		s.setError(ErrSyntax)
206
		s.b = s.b[:len(s.b)-1]
207
	}
208
	s.done = true
209
	return end
210
}
211

212
// acceptMinSize parses multiple tokens of the given size or greater.
213
// It returns the end position of the last token consumed.
214
func (s *scanner) acceptMinSize(min int) (end int) {
215
	end = s.end
216
	s.scan()
217
	for ; len(s.token) >= min; s.scan() {
218
		end = s.end
219
	}
220
	return end
221
}
222

223
// Parse parses the given BCP 47 string and returns a valid Tag. If parsing
224
// failed it returns an error and any part of the tag that could be parsed.
225
// If parsing succeeded but an unknown value was found, it returns
226
// ValueError. The Tag returned in this case is just stripped of the unknown
227
// value. All other values are preserved. It accepts tags in the BCP 47 format
228
// and extensions to this standard defined in
229
// https://www.unicode.org/reports/tr35/#Unicode_Language_and_Locale_Identifiers.
230
func Parse(s string) (t Tag, err error) {
231
	// TODO: consider supporting old-style locale key-value pairs.
232
	if s == "" {
233
		return Und, ErrSyntax
234
	}
235
	defer func() {
236
		if recover() != nil {
237
			t = Und
238
			err = ErrSyntax
239
			return
240
		}
241
	}()
242
	if len(s) <= maxAltTaglen {
243
		b := [maxAltTaglen]byte{}
244
		for i, c := range s {
245
			// Generating invalid UTF-8 is okay as it won't match.
246
			if 'A' <= c && c <= 'Z' {
247
				c += 'a' - 'A'
248
			} else if c == '_' {
249
				c = '-'
250
			}
251
			b[i] = byte(c)
252
		}
253
		if t, ok := grandfathered(b); ok {
254
			return t, nil
255
		}
256
	}
257
	scan := makeScannerString(s)
258
	return parse(&scan, s)
259
}
260

261
func parse(scan *scanner, s string) (t Tag, err error) {
262
	t = Und
263
	var end int
264
	if n := len(scan.token); n <= 1 {
265
		scan.toLower(0, len(scan.b))
266
		if n == 0 || scan.token[0] != 'x' {
267
			return t, ErrSyntax
268
		}
269
		end = parseExtensions(scan)
270
	} else if n >= 4 {
271
		return Und, ErrSyntax
272
	} else { // the usual case
273
		t, end = parseTag(scan, true)
274
		if n := len(scan.token); n == 1 {
275
			t.pExt = uint16(end)
276
			end = parseExtensions(scan)
277
		} else if end < len(scan.b) {
278
			scan.setError(ErrSyntax)
279
			scan.b = scan.b[:end]
280
		}
281
	}
282
	if int(t.pVariant) < len(scan.b) {
283
		if end < len(s) {
284
			s = s[:end]
285
		}
286
		if len(s) > 0 && tag.Compare(s, scan.b) == 0 {
287
			t.str = s
288
		} else {
289
			t.str = string(scan.b)
290
		}
291
	} else {
292
		t.pVariant, t.pExt = 0, 0
293
	}
294
	return t, scan.err
295
}
296

297
// parseTag parses language, script, region and variants.
298
// It returns a Tag and the end position in the input that was parsed.
299
// If doNorm is true, then <lang>-<extlang> will be normalized to <extlang>.
300
func parseTag(scan *scanner, doNorm bool) (t Tag, end int) {
301
	var e error
302
	// TODO: set an error if an unknown lang, script or region is encountered.
303
	t.LangID, e = getLangID(scan.token)
304
	scan.setError(e)
305
	scan.replace(t.LangID.String())
306
	langStart := scan.start
307
	end = scan.scan()
308
	for len(scan.token) == 3 && isAlpha(scan.token[0]) {
309
		// From http://tools.ietf.org/html/bcp47, <lang>-<extlang> tags are equivalent
310
		// to a tag of the form <extlang>.
311
		if doNorm {
312
			lang, e := getLangID(scan.token)
313
			if lang != 0 {
314
				t.LangID = lang
315
				langStr := lang.String()
316
				copy(scan.b[langStart:], langStr)
317
				scan.b[langStart+len(langStr)] = '-'
318
				scan.start = langStart + len(langStr) + 1
319
			}
320
			scan.gobble(e)
321
		}
322
		end = scan.scan()
323
	}
324
	if len(scan.token) == 4 && isAlpha(scan.token[0]) {
325
		t.ScriptID, e = getScriptID(script, scan.token)
326
		if t.ScriptID == 0 {
327
			scan.gobble(e)
328
		}
329
		end = scan.scan()
330
	}
331
	if n := len(scan.token); n >= 2 && n <= 3 {
332
		t.RegionID, e = getRegionID(scan.token)
333
		if t.RegionID == 0 {
334
			scan.gobble(e)
335
		} else {
336
			scan.replace(t.RegionID.String())
337
		}
338
		end = scan.scan()
339
	}
340
	scan.toLower(scan.start, len(scan.b))
341
	t.pVariant = byte(end)
342
	end = parseVariants(scan, end, t)
343
	t.pExt = uint16(end)
344
	return t, end
345
}
346

347
var separator = []byte{'-'}
348

349
// parseVariants scans tokens as long as each token is a valid variant string.
350
// Duplicate variants are removed.
351
func parseVariants(scan *scanner, end int, t Tag) int {
352
	start := scan.start
353
	varIDBuf := [4]uint8{}
354
	variantBuf := [4][]byte{}
355
	varID := varIDBuf[:0]
356
	variant := variantBuf[:0]
357
	last := -1
358
	needSort := false
359
	for ; len(scan.token) >= 4; scan.scan() {
360
		// TODO: measure the impact of needing this conversion and redesign
361
		// the data structure if there is an issue.
362
		v, ok := variantIndex[string(scan.token)]
363
		if !ok {
364
			// unknown variant
365
			// TODO: allow user-defined variants?
366
			scan.gobble(NewValueError(scan.token))
367
			continue
368
		}
369
		varID = append(varID, v)
370
		variant = append(variant, scan.token)
371
		if !needSort {
372
			if last < int(v) {
373
				last = int(v)
374
			} else {
375
				needSort = true
376
				// There is no legal combinations of more than 7 variants
377
				// (and this is by no means a useful sequence).
378
				const maxVariants = 8
379
				if len(varID) > maxVariants {
380
					break
381
				}
382
			}
383
		}
384
		end = scan.end
385
	}
386
	if needSort {
387
		sort.Sort(variantsSort{varID, variant})
388
		k, l := 0, -1
389
		for i, v := range varID {
390
			w := int(v)
391
			if l == w {
392
				// Remove duplicates.
393
				continue
394
			}
395
			varID[k] = varID[i]
396
			variant[k] = variant[i]
397
			k++
398
			l = w
399
		}
400
		if str := bytes.Join(variant[:k], separator); len(str) == 0 {
401
			end = start - 1
402
		} else {
403
			scan.resizeRange(start, end, len(str))
404
			copy(scan.b[scan.start:], str)
405
			end = scan.end
406
		}
407
	}
408
	return end
409
}
410

411
type variantsSort struct {
412
	i []uint8
413
	v [][]byte
414
}
415

416
func (s variantsSort) Len() int {
417
	return len(s.i)
418
}
419

420
func (s variantsSort) Swap(i, j int) {
421
	s.i[i], s.i[j] = s.i[j], s.i[i]
422
	s.v[i], s.v[j] = s.v[j], s.v[i]
423
}
424

425
func (s variantsSort) Less(i, j int) bool {
426
	return s.i[i] < s.i[j]
427
}
428

429
type bytesSort struct {
430
	b [][]byte
431
	n int // first n bytes to compare
432
}
433

434
func (b bytesSort) Len() int {
435
	return len(b.b)
436
}
437

438
func (b bytesSort) Swap(i, j int) {
439
	b.b[i], b.b[j] = b.b[j], b.b[i]
440
}
441

442
func (b bytesSort) Less(i, j int) bool {
443
	for k := 0; k < b.n; k++ {
444
		if b.b[i][k] == b.b[j][k] {
445
			continue
446
		}
447
		return b.b[i][k] < b.b[j][k]
448
	}
449
	return false
450
}
451

452
// parseExtensions parses and normalizes the extensions in the buffer.
453
// It returns the last position of scan.b that is part of any extension.
454
// It also trims scan.b to remove excess parts accordingly.
455
func parseExtensions(scan *scanner) int {
456
	start := scan.start
457
	exts := [][]byte{}
458
	private := []byte{}
459
	end := scan.end
460
	for len(scan.token) == 1 {
461
		extStart := scan.start
462
		ext := scan.token[0]
463
		end = parseExtension(scan)
464
		extension := scan.b[extStart:end]
465
		if len(extension) < 3 || (ext != 'x' && len(extension) < 4) {
466
			scan.setError(ErrSyntax)
467
			end = extStart
468
			continue
469
		} else if start == extStart && (ext == 'x' || scan.start == len(scan.b)) {
470
			scan.b = scan.b[:end]
471
			return end
472
		} else if ext == 'x' {
473
			private = extension
474
			break
475
		}
476
		exts = append(exts, extension)
477
	}
478
	sort.Sort(bytesSort{exts, 1})
479
	if len(private) > 0 {
480
		exts = append(exts, private)
481
	}
482
	scan.b = scan.b[:start]
483
	if len(exts) > 0 {
484
		scan.b = append(scan.b, bytes.Join(exts, separator)...)
485
	} else if start > 0 {
486
		// Strip trailing '-'.
487
		scan.b = scan.b[:start-1]
488
	}
489
	return end
490
}
491

492
// parseExtension parses a single extension and returns the position of
493
// the extension end.
494
func parseExtension(scan *scanner) int {
495
	start, end := scan.start, scan.end
496
	switch scan.token[0] {
497
	case 'u': // https://www.ietf.org/rfc/rfc6067.txt
498
		attrStart := end
499
		scan.scan()
500
		for last := []byte{}; len(scan.token) > 2; scan.scan() {
501
			if bytes.Compare(scan.token, last) != -1 {
502
				// Attributes are unsorted. Start over from scratch.
503
				p := attrStart + 1
504
				scan.next = p
505
				attrs := [][]byte{}
506
				for scan.scan(); len(scan.token) > 2; scan.scan() {
507
					attrs = append(attrs, scan.token)
508
					end = scan.end
509
				}
510
				sort.Sort(bytesSort{attrs, 3})
511
				copy(scan.b[p:], bytes.Join(attrs, separator))
512
				break
513
			}
514
			last = scan.token
515
			end = scan.end
516
		}
517
		// Scan key-type sequences. A key is of length 2 and may be followed
518
		// by 0 or more "type" subtags from 3 to the maximum of 8 letters.
519
		var last, key []byte
520
		for attrEnd := end; len(scan.token) == 2; last = key {
521
			key = scan.token
522
			end = scan.end
523
			for scan.scan(); end < scan.end && len(scan.token) > 2; scan.scan() {
524
				end = scan.end
525
			}
526
			// TODO: check key value validity
527
			if bytes.Compare(key, last) != 1 || scan.err != nil {
528
				// We have an invalid key or the keys are not sorted.
529
				// Start scanning keys from scratch and reorder.
530
				p := attrEnd + 1
531
				scan.next = p
532
				keys := [][]byte{}
533
				for scan.scan(); len(scan.token) == 2; {
534
					keyStart := scan.start
535
					end = scan.end
536
					for scan.scan(); end < scan.end && len(scan.token) > 2; scan.scan() {
537
						end = scan.end
538
					}
539
					keys = append(keys, scan.b[keyStart:end])
540
				}
541
				sort.Stable(bytesSort{keys, 2})
542
				if n := len(keys); n > 0 {
543
					k := 0
544
					for i := 1; i < n; i++ {
545
						if !bytes.Equal(keys[k][:2], keys[i][:2]) {
546
							k++
547
							keys[k] = keys[i]
548
						} else if !bytes.Equal(keys[k], keys[i]) {
549
							scan.setError(ErrDuplicateKey)
550
						}
551
					}
552
					keys = keys[:k+1]
553
				}
554
				reordered := bytes.Join(keys, separator)
555
				if e := p + len(reordered); e < end {
556
					scan.deleteRange(e, end)
557
					end = e
558
				}
559
				copy(scan.b[p:], reordered)
560
				break
561
			}
562
		}
563
	case 't': // https://www.ietf.org/rfc/rfc6497.txt
564
		scan.scan()
565
		if n := len(scan.token); n >= 2 && n <= 3 && isAlpha(scan.token[1]) {
566
			_, end = parseTag(scan, false)
567
			scan.toLower(start, end)
568
		}
569
		for len(scan.token) == 2 && !isAlpha(scan.token[1]) {
570
			end = scan.acceptMinSize(3)
571
		}
572
	case 'x':
573
		end = scan.acceptMinSize(1)
574
	default:
575
		end = scan.acceptMinSize(2)
576
	}
577
	return end
578
}
579

580
// getExtension returns the name, body and end position of the extension.
581
func getExtension(s string, p int) (end int, ext string) {
582
	if s[p] == '-' {
583
		p++
584
	}
585
	if s[p] == 'x' {
586
		return len(s), s[p:]
587
	}
588
	end = nextExtension(s, p)
589
	return end, s[p:end]
590
}
591

592
// nextExtension finds the next extension within the string, searching
593
// for the -<char>- pattern from position p.
594
// In the fast majority of cases, language tags will have at most
595
// one extension and extensions tend to be small.
596
func nextExtension(s string, p int) int {
597
	for n := len(s) - 3; p < n; {
598
		if s[p] == '-' {
599
			if s[p+2] == '-' {
600
				return p
601
			}
602
			p += 3
603
		} else {
604
			p++
605
		}
606
	}
607
	return len(s)
608
}
609

610