vendor/golang.org/x/text/unicode/cldr/resolve.go

   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 cldr
   6
   7 // This file implements the various inheritance constructs defined by LDML.
   8 // See http://www.unicode.org/reports/tr35/#Inheritance_and_Validity
   9 // for more details.
  10
  11 import (
  12         "fmt"
  13         "log"
  14         "reflect"
  15         "regexp"
  16         "sort"
  17         "strings"
  18 )
  19
  20 // fieldIter iterates over fields in a struct. It includes
  21 // fields of embedded structs.
  22 type fieldIter struct {
  23         v        reflect.Value
  24         index, n []int
  25 }
  26
  27 func iter(v reflect.Value) fieldIter {
  28         if v.Kind() != reflect.Struct {
  29                 log.Panicf("value %v must be a struct", v)
  30         }
  31         i := fieldIter{
  32                 v:     v,
  33                 index: []int{0},
  34                 n:     []int{v.NumField()},
  35         }
  36         i.descent()
  37         return i
  38 }
  39
  40 func (i *fieldIter) descent() {
  41         for f := i.field(); f.Anonymous && f.Type.NumField() > 0; f = i.field() {
  42                 i.index = append(i.index, 0)
  43                 i.n = append(i.n, f.Type.NumField())
  44         }
  45 }
  46
  47 func (i *fieldIter) done() bool {
  48         return len(i.index) == 1 && i.index[0] >= i.n[0]
  49 }
  50
  51 func skip(f reflect.StructField) bool {
  52         return !f.Anonymous && (f.Name[0] < 'A' || f.Name[0] > 'Z')
  53 }
  54
  55 func (i *fieldIter) next() {
  56         for {
  57                 k := len(i.index) - 1
  58                 i.index[k]++
  59                 if i.index[k] < i.n[k] {
  60                         if !skip(i.field()) {
  61                                 break
  62                         }
  63                 } else {
  64                         if k == 0 {
  65                                 return
  66                         }
  67                         i.index = i.index[:k]
  68                         i.n = i.n[:k]
  69                 }
  70         }
  71         i.descent()
  72 }
  73
  74 func (i *fieldIter) value() reflect.Value {
  75         return i.v.FieldByIndex(i.index)
  76 }
  77
  78 func (i *fieldIter) field() reflect.StructField {
  79         return i.v.Type().FieldByIndex(i.index)
  80 }
  81
  82 type visitor func(v reflect.Value) error
  83
  84 var stopDescent = fmt.Errorf("do not recurse")
  85
  86 func (f visitor) visit(x interface{}) error {
  87         return f.visitRec(reflect.ValueOf(x))
  88 }
  89
  90 // visit recursively calls f on all nodes in v.
  91 func (f visitor) visitRec(v reflect.Value) error {
  92         if v.Kind() == reflect.Ptr {
  93                 if v.IsNil() {
  94                         return nil
  95                 }
  96                 return f.visitRec(v.Elem())
  97         }
  98         if err := f(v); err != nil {
  99                 if err == stopDescent {
 100                         return nil
 101                 }
 102                 return err
 103         }
 104         switch v.Kind() {
 105         case reflect.Struct:
 106                 for i := iter(v); !i.done(); i.next() {
 107                         if err := f.visitRec(i.value()); err != nil {
 108                                 return err
 109                         }
 110                 }
 111         case reflect.Slice:
 112                 for i := 0; i < v.Len(); i++ {
 113                         if err := f.visitRec(v.Index(i)); err != nil {
 114                                 return err
 115                         }
 116                 }
 117         }
 118         return nil
 119 }
 120
 121 // getPath is used for error reporting purposes only.
 122 func getPath(e Elem) string {
 123         if e == nil {
 124                 return "<nil>"
 125         }
 126         if e.enclosing() == nil {
 127                 return e.GetCommon().name
 128         }
 129         if e.GetCommon().Type == "" {
 130                 return fmt.Sprintf("%s.%s", getPath(e.enclosing()), e.GetCommon().name)
 131         }
 132         return fmt.Sprintf("%s.%s[type=%s]", getPath(e.enclosing()), e.GetCommon().name, e.GetCommon().Type)
 133 }
 134
 135 // xmlName returns the xml name of the element or attribute
 136 func xmlName(f reflect.StructField) (name string, attr bool) {
 137         tags := strings.Split(f.Tag.Get("xml"), ",")
 138         for _, s := range tags {
 139                 attr = attr || s == "attr"
 140         }
 141         return tags[0], attr
 142 }
 143
 144 func findField(v reflect.Value, key string) (reflect.Value, error) {
 145         v = reflect.Indirect(v)
 146         for i := iter(v); !i.done(); i.next() {
 147                 if n, _ := xmlName(i.field()); n == key {
 148                         return i.value(), nil
 149                 }
 150         }
 151         return reflect.Value{}, fmt.Errorf("cldr: no field %q in element %#v", key, v.Interface())
 152 }
 153
 154 var xpathPart = regexp.MustCompile(`(\pL+)(?:\[@(\pL+)='([\w-]+)'\])?`)
 155
 156 func walkXPath(e Elem, path string) (res Elem, err error) {
 157         for _, c := range strings.Split(path, "/") {
 158                 if c == ".." {
 159                         if e = e.enclosing(); e == nil {
 160                                 panic("path ..")
 161                                 return nil, fmt.Errorf(`cldr: ".." moves past root in path %q`, path)
 162                         }
 163                         continue
 164                 } else if c == "" {
 165                         continue
 166                 }
 167                 m := xpathPart.FindStringSubmatch(c)
 168                 if len(m) == 0 || len(m[0]) != len(c) {
 169                         return nil, fmt.Errorf("cldr: syntax error in path component %q", c)
 170                 }
 171                 v, err := findField(reflect.ValueOf(e), m[1])
 172                 if err != nil {
 173                         return nil, err
 174                 }
 175                 switch v.Kind() {
 176                 case reflect.Slice:
 177                         i := 0
 178                         if m[2] != "" || v.Len() > 1 {
 179                                 if m[2] == "" {
 180                                         m[2] = "type"
 181                                         if m[3] = e.GetCommon().Default(); m[3] == "" {
 182                                                 return nil, fmt.Errorf("cldr: type selector or default value needed for element %s", m[1])
 183                                         }
 184                                 }
 185                                 for ; i < v.Len(); i++ {
 186                                         vi := v.Index(i)
 187                                         key, err := findField(vi.Elem(), m[2])
 188                                         if err != nil {
 189                                                 return nil, err
 190                                         }
 191                                         key = reflect.Indirect(key)
 192                                         if key.Kind() == reflect.String && key.String() == m[3] {
 193                                                 break
 194                                         }
 195                                 }
 196                         }
 197                         if i == v.Len() || v.Index(i).IsNil() {
 198                                 return nil, fmt.Errorf("no %s found with %s==%s", m[1], m[2], m[3])
 199                         }
 200                         e = v.Index(i).Interface().(Elem)
 201                 case reflect.Ptr:
 202                         if v.IsNil() {
 203                                 return nil, fmt.Errorf("cldr: element %q not found within element %q", m[1], e.GetCommon().name)
 204                         }
 205                         var ok bool
 206                         if e, ok = v.Interface().(Elem); !ok {
 207                                 return nil, fmt.Errorf("cldr: %q is not an XML element", m[1])
 208                         } else if m[2] != "" || m[3] != "" {
 209                                 return nil, fmt.Errorf("cldr: no type selector allowed for element %s", m[1])
 210                         }
 211                 default:
 212                         return nil, fmt.Errorf("cldr: %q is not an XML element", m[1])
 213                 }
 214         }
 215         return e, nil
 216 }
 217
 218 const absPrefix = "//ldml/"
 219
 220 func (cldr *CLDR) resolveAlias(e Elem, src, path string) (res Elem, err error) {
 221         if src != "locale" {
 222                 if !strings.HasPrefix(path, absPrefix) {
 223                         return nil, fmt.Errorf("cldr: expected absolute path, found %q", path)
 224                 }
 225                 path = path[len(absPrefix):]
 226                 if e, err = cldr.resolve(src); err != nil {
 227                         return nil, err
 228                 }
 229         }
 230         return walkXPath(e, path)
 231 }
 232
 233 func (cldr *CLDR) resolveAndMergeAlias(e Elem) error {
 234         alias := e.GetCommon().Alias
 235         if alias == nil {
 236                 return nil
 237         }
 238         a, err := cldr.resolveAlias(e, alias.Source, alias.Path)
 239         if err != nil {
 240                 return fmt.Errorf("%v: error evaluating path %q: %v", getPath(e), alias.Path, err)
 241         }
 242         // Ensure alias node was already evaluated. TODO: avoid double evaluation.
 243         err = cldr.resolveAndMergeAlias(a)
 244         v := reflect.ValueOf(e).Elem()
 245         for i := iter(reflect.ValueOf(a).Elem()); !i.done(); i.next() {
 246                 if vv := i.value(); vv.Kind() != reflect.Ptr || !vv.IsNil() {
 247                         if _, attr := xmlName(i.field()); !attr {
 248                                 v.FieldByIndex(i.index).Set(vv)
 249                         }
 250                 }
 251         }
 252         return err
 253 }
 254
 255 func (cldr *CLDR) aliasResolver() visitor {
 256         return func(v reflect.Value) (err error) {
 257                 if e, ok := v.Addr().Interface().(Elem); ok {
 258                         err = cldr.resolveAndMergeAlias(e)
 259                         if err == nil && blocking[e.GetCommon().name] {
 260                                 return stopDescent
 261                         }
 262                 }
 263                 return err
 264         }
 265 }
 266
 267 // elements within blocking elements do not inherit.
 268 // Taken from CLDR's supplementalMetaData.xml.
 269 var blocking = map[string]bool{
 270         "identity":         true,
 271         "supplementalData": true,
 272         "cldrTest":         true,
 273         "collation":        true,
 274         "transform":        true,
 275 }
 276
 277 // Distinguishing attributes affect inheritance; two elements with different
 278 // distinguishing attributes are treated as different for purposes of inheritance,
 279 // except when such attributes occur in the indicated elements.
 280 // Taken from CLDR's supplementalMetaData.xml.
 281 var distinguishing = map[string][]string{
 282         "key":        nil,
 283         "request_id": nil,
 284         "id":         nil,
 285         "registry":   nil,
 286         "alt":        nil,
 287         "iso4217":    nil,
 288         "iso3166":    nil,
 289         "mzone":      nil,
 290         "from":       nil,
 291         "to":         nil,
 292         "type": []string{
 293                 "abbreviationFallback",
 294                 "default",
 295                 "mapping",
 296                 "measurementSystem",
 297                 "preferenceOrdering",
 298         },
 299         "numberSystem": nil,
 300 }
 301
 302 func in(set []string, s string) bool {
 303         for _, v := range set {
 304                 if v == s {
 305                         return true
 306                 }
 307         }
 308         return false
 309 }
 310
 311 // attrKey computes a key based on the distinguishable attributes of
 312 // an element and it's values.
 313 func attrKey(v reflect.Value, exclude ...string) string {
 314         parts := []string{}
 315         ename := v.Interface().(Elem).GetCommon().name
 316         v = v.Elem()
 317         for i := iter(v); !i.done(); i.next() {
 318                 if name, attr := xmlName(i.field()); attr {
 319                         if except, ok := distinguishing[name]; ok && !in(exclude, name) && !in(except, ename) {
 320                                 v := i.value()
 321                                 if v.Kind() == reflect.Ptr {
 322                                         v = v.Elem()
 323                                 }
 324                                 if v.IsValid() {
 325                                         parts = append(parts, fmt.Sprintf("%s=%s", name, v.String()))
 326                                 }
 327                         }
 328                 }
 329         }
 330         sort.Strings(parts)
 331         return strings.Join(parts, ";")
 332 }
 333
 334 // Key returns a key for e derived from all distinguishing attributes
 335 // except those specified by exclude.
 336 func Key(e Elem, exclude ...string) string {
 337         return attrKey(reflect.ValueOf(e), exclude...)
 338 }
 339
 340 // linkEnclosing sets the enclosing element as well as the name
 341 // for all sub-elements of child, recursively.
 342 func linkEnclosing(parent, child Elem) {
 343         child.setEnclosing(parent)
 344         v := reflect.ValueOf(child).Elem()
 345         for i := iter(v); !i.done(); i.next() {
 346                 vf := i.value()
 347                 if vf.Kind() == reflect.Slice {
 348                         for j := 0; j < vf.Len(); j++ {
 349                                 linkEnclosing(child, vf.Index(j).Interface().(Elem))
 350                         }
 351                 } else if vf.Kind() == reflect.Ptr && !vf.IsNil() && vf.Elem().Kind() == reflect.Struct {
 352                         linkEnclosing(child, vf.Interface().(Elem))
 353                 }
 354         }
 355 }
 356
 357 func setNames(e Elem, name string) {
 358         e.setName(name)
 359         v := reflect.ValueOf(e).Elem()
 360         for i := iter(v); !i.done(); i.next() {
 361                 vf := i.value()
 362                 name, _ = xmlName(i.field())
 363                 if vf.Kind() == reflect.Slice {
 364                         for j := 0; j < vf.Len(); j++ {
 365                                 setNames(vf.Index(j).Interface().(Elem), name)
 366                         }
 367                 } else if vf.Kind() == reflect.Ptr && !vf.IsNil() && vf.Elem().Kind() == reflect.Struct {
 368                         setNames(vf.Interface().(Elem), name)
 369                 }
 370         }
 371 }
 372
 373 // deepCopy copies elements of v recursively.  All elements of v that may
 374 // be modified by inheritance are explicitly copied.
 375 func deepCopy(v reflect.Value) reflect.Value {
 376         switch v.Kind() {
 377         case reflect.Ptr:
 378                 if v.IsNil() || v.Elem().Kind() != reflect.Struct {
 379                         return v
 380                 }
 381                 nv := reflect.New(v.Elem().Type())
 382                 nv.Elem().Set(v.Elem())
 383                 deepCopyRec(nv.Elem(), v.Elem())
 384                 return nv
 385         case reflect.Slice:
 386                 nv := reflect.MakeSlice(v.Type(), v.Len(), v.Len())
 387                 for i := 0; i < v.Len(); i++ {
 388                         deepCopyRec(nv.Index(i), v.Index(i))
 389                 }
 390                 return nv
 391         }
 392         panic("deepCopy: must be called with pointer or slice")
 393 }
 394
 395 // deepCopyRec is only called by deepCopy.
 396 func deepCopyRec(nv, v reflect.Value) {
 397         if v.Kind() == reflect.Struct {
 398                 t := v.Type()
 399                 for i := 0; i < v.NumField(); i++ {
 400                         if name, attr := xmlName(t.Field(i)); name != "" && !attr {
 401                                 deepCopyRec(nv.Field(i), v.Field(i))
 402                         }
 403                 }
 404         } else {
 405                 nv.Set(deepCopy(v))
 406         }
 407 }
 408
 409 // newNode is used to insert a missing node during inheritance.
 410 func (cldr *CLDR) newNode(v, enc reflect.Value) reflect.Value {
 411         n := reflect.New(v.Type())
 412         for i := iter(v); !i.done(); i.next() {
 413                 if name, attr := xmlName(i.field()); name == "" || attr {
 414                         n.Elem().FieldByIndex(i.index).Set(i.value())
 415                 }
 416         }
 417         n.Interface().(Elem).GetCommon().setEnclosing(enc.Addr().Interface().(Elem))
 418         return n
 419 }
 420
 421 // v, parent must be pointers to struct
 422 func (cldr *CLDR) inheritFields(v, parent reflect.Value) (res reflect.Value, err error) {
 423         t := v.Type()
 424         nv := reflect.New(t)
 425         nv.Elem().Set(v)
 426         for i := iter(v); !i.done(); i.next() {
 427                 vf := i.value()
 428                 f := i.field()
 429                 name, attr := xmlName(f)
 430                 if name == "" || attr {
 431                         continue
 432                 }
 433                 pf := parent.FieldByIndex(i.index)
 434                 if blocking[name] {
 435                         if vf.IsNil() {
 436                                 vf = pf
 437                         }
 438                         nv.Elem().FieldByIndex(i.index).Set(deepCopy(vf))
 439                         continue
 440                 }
 441                 switch f.Type.Kind() {
 442                 case reflect.Ptr:
 443                         if f.Type.Elem().Kind() == reflect.Struct {
 444                                 if !vf.IsNil() {
 445                                         if vf, err = cldr.inheritStructPtr(vf, pf); err != nil {
 446                                                 return reflect.Value{}, err
 447                                         }
 448                                         vf.Interface().(Elem).setEnclosing(nv.Interface().(Elem))
 449                                         nv.Elem().FieldByIndex(i.index).Set(vf)
 450                                 } else if !pf.IsNil() {
 451                                         n := cldr.newNode(pf.Elem(), v)
 452                                         if vf, err = cldr.inheritStructPtr(n, pf); err != nil {
 453                                                 return reflect.Value{}, err
 454                                         }
 455                                         vf.Interface().(Elem).setEnclosing(nv.Interface().(Elem))
 456                                         nv.Elem().FieldByIndex(i.index).Set(vf)
 457                                 }
 458                         }
 459                 case reflect.Slice:
 460                         vf, err := cldr.inheritSlice(nv.Elem(), vf, pf)
 461                         if err != nil {
 462                                 return reflect.Zero(t), err
 463                         }
 464                         nv.Elem().FieldByIndex(i.index).Set(vf)
 465                 }
 466         }
 467         return nv, nil
 468 }
 469
 470 func root(e Elem) *LDML {
 471         for ; e.enclosing() != nil; e = e.enclosing() {
 472         }
 473         return e.(*LDML)
 474 }
 475
 476 // inheritStructPtr first merges possible aliases in with v and then inherits
 477 // any underspecified elements from parent.
 478 func (cldr *CLDR) inheritStructPtr(v, parent reflect.Value) (r reflect.Value, err error) {
 479         if !v.IsNil() {
 480                 e := v.Interface().(Elem).GetCommon()
 481                 alias := e.Alias
 482                 if alias == nil && !parent.IsNil() {
 483                         alias = parent.Interface().(Elem).GetCommon().Alias
 484                 }
 485                 if alias != nil {
 486                         a, err := cldr.resolveAlias(v.Interface().(Elem), alias.Source, alias.Path)
 487                         if a != nil {
 488                                 if v, err = cldr.inheritFields(v.Elem(), reflect.ValueOf(a).Elem()); err != nil {
 489                                         return reflect.Value{}, err
 490                                 }
 491                         }
 492                 }
 493                 if !parent.IsNil() {
 494                         return cldr.inheritFields(v.Elem(), parent.Elem())
 495                 }
 496         } else if parent.IsNil() {
 497                 panic("should not reach here")
 498         }
 499         return v, nil
 500 }
 501
 502 // Must be slice of struct pointers.
 503 func (cldr *CLDR) inheritSlice(enc, v, parent reflect.Value) (res reflect.Value, err error) {
 504         t := v.Type()
 505         index := make(map[string]reflect.Value)
 506         if !v.IsNil() {
 507                 for i := 0; i < v.Len(); i++ {
 508                         vi := v.Index(i)
 509                         key := attrKey(vi)
 510                         index[key] = vi
 511                 }
 512         }
 513         if !parent.IsNil() {
 514                 for i := 0; i < parent.Len(); i++ {
 515                         vi := parent.Index(i)
 516                         key := attrKey(vi)
 517                         if w, ok := index[key]; ok {
 518                                 index[key], err = cldr.inheritStructPtr(w, vi)
 519                         } else {
 520                                 n := cldr.newNode(vi.Elem(), enc)
 521                                 index[key], err = cldr.inheritStructPtr(n, vi)
 522                         }
 523                         index[key].Interface().(Elem).setEnclosing(enc.Addr().Interface().(Elem))
 524                         if err != nil {
 525                                 return v, err
 526                         }
 527                 }
 528         }
 529         keys := make([]string, 0, len(index))
 530         for k, _ := range index {
 531                 keys = append(keys, k)
 532         }
 533         sort.Strings(keys)
 534         sl := reflect.MakeSlice(t, len(index), len(index))
 535         for i, k := range keys {
 536                 sl.Index(i).Set(index[k])
 537         }
 538         return sl, nil
 539 }
 540
 541 func parentLocale(loc string) string {
 542         parts := strings.Split(loc, "_")
 543         if len(parts) == 1 {
 544                 return "root"
 545         }
 546         parts = parts[:len(parts)-1]
 547         key := strings.Join(parts, "_")
 548         return key
 549 }
 550
 551 func (cldr *CLDR) resolve(loc string) (res *LDML, err error) {
 552         if r := cldr.resolved[loc]; r != nil {
 553                 return r, nil
 554         }
 555         x := cldr.RawLDML(loc)
 556         if x == nil {
 557                 return nil, fmt.Errorf("cldr: unknown locale %q", loc)
 558         }
 559         var v reflect.Value
 560         if loc == "root" {
 561                 x = deepCopy(reflect.ValueOf(x)).Interface().(*LDML)
 562                 linkEnclosing(nil, x)
 563                 err = cldr.aliasResolver().visit(x)
 564         } else {
 565                 key := parentLocale(loc)
 566                 var parent *LDML
 567                 for ; cldr.locale[key] == nil; key = parentLocale(key) {
 568                 }
 569                 if parent, err = cldr.resolve(key); err != nil {
 570                         return nil, err
 571                 }
 572                 v, err = cldr.inheritFields(reflect.ValueOf(x).Elem(), reflect.ValueOf(parent).Elem())
 573                 x = v.Interface().(*LDML)
 574                 linkEnclosing(nil, x)
 575         }
 576         if err != nil {
 577                 return nil, err
 578         }
 579         cldr.resolved[loc] = x
 580         return x, err
 581 }
 582
 583 // finalize finalizes the initialization of the raw LDML structs.  It also
 584 // removed unwanted fields, as specified by filter, so that they will not
 585 // be unnecessarily evaluated.
 586 func (cldr *CLDR) finalize(filter []string) {
 587         for _, x := range cldr.locale {
 588                 if filter != nil {
 589                         v := reflect.ValueOf(x).Elem()
 590                         t := v.Type()
 591                         for i := 0; i < v.NumField(); i++ {
 592                                 f := t.Field(i)
 593                                 name, _ := xmlName(f)
 594                                 if name != "" && name != "identity" && !in(filter, name) {
 595                                         v.Field(i).Set(reflect.Zero(f.Type))
 596                                 }
 597                         }
 598                 }
 599                 linkEnclosing(nil, x) // for resolving aliases and paths
 600                 setNames(x, "ldml")
 601         }
 602 }