tree.go

Documentation: golang.org/x/text/internal/cldrtree

     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  
     5  package cldrtree
     6  
     7  import (
     8  	"golang.org/x/text/internal/language/compact"
     9  	"golang.org/x/text/language"
    10  )
    11  
    12  const (
    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.
    21  type 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.
    33  func (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.
    39  func (t *Tree) LookupFeature(tag compact.ID, path ...uint16) string {
    40  	return t.lookup(tag, true, path...)
    41  }
    42  
    43  func (t *Tree) lookup(tag compact.ID, isFeature bool, path ...uint16) string {
    44  	origLang := tag
    45  outer:
    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  
    94  func 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  
   125  type indexBuilder struct {
   126  	index []uint16
   127  }
   128  
   129  func (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
View as plain text