1// Copyright 2017 The Go Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style
3// license that can be found in the LICENSE file.
4
5package cldrtree
6
7import (
8	"golang.org/x/text/internal/language/compact"
9	"golang.org/x/text/language"
10)
11
12const (
13	inheritOffsetShift        = 12
14	inheritMask        uint16 = 0x8000
15	inheritValueMask   uint16 = 0x0FFF
16
17	missingValue uint16 = 0xFFFF
18)
19
20// Tree holds a tree of CLDR data.
21type Tree struct {
22	Locales []uint32
23	Indices []uint16
24	Buckets []string
25}
26
27// Lookup looks up CLDR data for the given path. The lookup adheres to the alias
28// and locale inheritance rules as defined in CLDR.
29//
30// Each subsequent element in path indicates which subtree to select data from.
31// The last element of the path must select a leaf node. All other elements
32// of the path select a subindex.
33func (t *Tree) Lookup(tag compact.ID, path ...uint16) string {
34	return t.lookup(tag, false, path...)
35}
36
37// LookupFeature is like Lookup, but will first check whether a value of "other"
38// as a fallback before traversing the inheritance chain.
39func (t *Tree) LookupFeature(tag compact.ID, path ...uint16) string {
40	return t.lookup(tag, true, path...)
41}
42
43func (t *Tree) lookup(tag compact.ID, isFeature bool, path ...uint16) string {
44	origLang := tag
45outer:
46	for {
47		index := t.Indices[t.Locales[tag]:]
48
49		k := uint16(0)
50		for i := range path {
51			max := index[k]
52			if i < len(path)-1 {
53				// index (non-leaf)
54				if path[i] >= max {
55					break
56				}
57				k = index[k+1+path[i]]
58				if k == 0 {
59					break
60				}
61				if v := k &^ inheritMask; k != v {
62					offset := v >> inheritOffsetShift
63					value := v & inheritValueMask
64					path[uint16(i)-offset] = value
65					tag = origLang
66					continue outer
67				}
68			} else {
69				// leaf value
70				offset := missingValue
71				if path[i] < max {
72					offset = index[k+2+path[i]]
73				}
74				if offset == missingValue {
75					if !isFeature {
76						break
77					}
78					// "other" feature must exist
79					offset = index[k+2]
80				}
81				data := t.Buckets[index[k+1]]
82				n := uint16(data[offset])
83				return data[offset+1 : offset+n+1]
84			}
85		}
86		if tag == 0 {
87			break
88		}
89		tag = tag.Parent()
90	}
91	return ""
92}
93
94func build(b *Builder) (*Tree, error) {
95	var t Tree
96
97	t.Locales = make([]uint32, language.NumCompactTags)
98
99	for _, loc := range b.locales {
100		tag, _ := language.CompactIndex(loc.tag)
101		t.Locales[tag] = uint32(len(t.Indices))
102		var x indexBuilder
103		x.add(loc.root)
104		t.Indices = append(t.Indices, x.index...)
105	}
106	// Set locales for which we don't have data to the parent's data.
107	for i, v := range t.Locales {
108		p := compact.ID(i)
109		for v == 0 && p != 0 {
110			p = p.Parent()
111			v = t.Locales[p]
112		}
113		t.Locales[i] = v
114	}
115
116	for _, b := range b.buckets {
117		t.Buckets = append(t.Buckets, string(b))
118	}
119	if b.err != nil {
120		return nil, b.err
121	}
122	return &t, nil
123}
124
125type indexBuilder struct {
126	index []uint16
127}
128
129func (b *indexBuilder) add(i *Index) uint16 {
130	offset := len(b.index)
131
132	max := enumIndex(0)
133	switch {
134	case len(i.values) > 0:
135		for _, v := range i.values {
136			if v.key > max {
137				max = v.key
138			}
139		}
140		b.index = append(b.index, make([]uint16, max+3)...)
141
142		b.index[offset] = uint16(max) + 1
143
144		b.index[offset+1] = i.values[0].value.bucket
145		for i := offset + 2; i < len(b.index); i++ {
146			b.index[i] = missingValue
147		}
148		for _, v := range i.values {
149			b.index[offset+2+int(v.key)] = v.value.bucketPos
150		}
151		return uint16(offset)
152
153	case len(i.subIndex) > 0:
154		for _, s := range i.subIndex {
155			if s.meta.index > max {
156				max = s.meta.index
157			}
158		}
159		b.index = append(b.index, make([]uint16, max+2)...)
160
161		b.index[offset] = uint16(max) + 1
162
163		for _, s := range i.subIndex {
164			x := b.add(s)
165			b.index[offset+int(s.meta.index)+1] = x
166		}
167		return uint16(offset)
168
169	case i.meta.inheritOffset < 0:
170		v := uint16(-(i.meta.inheritOffset + 1)) << inheritOffsetShift
171		p := i.meta
172		for k := i.meta.inheritOffset; k < 0; k++ {
173			p = p.parent
174		}
175		v += uint16(p.typeInfo.enum.lookup(i.meta.inheritIndex))
176		v |= inheritMask
177		return v
178	}
179
180	return 0
181}
182