.config/coc/extensions/coc-go-data/tools/pkg/mod/github.com/!burnt!sushi/toml@v0.3.1/type_fields.go

   1 package toml
   2
   3 // Struct field handling is adapted from code in encoding/json:
   4 //
   5 // Copyright 2010 The Go Authors.  All rights reserved.
   6 // Use of this source code is governed by a BSD-style
   7 // license that can be found in the Go distribution.
   8
   9 import (
  10         "reflect"
  11         "sort"
  12         "sync"
  13 )
  14
  15 // A field represents a single field found in a struct.
  16 type field struct {
  17         name  string       // the name of the field (`toml` tag included)
  18         tag   bool         // whether field has a `toml` tag
  19         index []int        // represents the depth of an anonymous field
  20         typ   reflect.Type // the type of the field
  21 }
  22
  23 // byName sorts field by name, breaking ties with depth,
  24 // then breaking ties with "name came from toml tag", then
  25 // breaking ties with index sequence.
  26 type byName []field
  27
  28 func (x byName) Len() int { return len(x) }
  29
  30 func (x byName) Swap(i, j int) { x[i], x[j] = x[j], x[i] }
  31
  32 func (x byName) Less(i, j int) bool {
  33         if x[i].name != x[j].name {
  34                 return x[i].name < x[j].name
  35         }
  36         if len(x[i].index) != len(x[j].index) {
  37                 return len(x[i].index) < len(x[j].index)
  38         }
  39         if x[i].tag != x[j].tag {
  40                 return x[i].tag
  41         }
  42         return byIndex(x).Less(i, j)
  43 }
  44
  45 // byIndex sorts field by index sequence.
  46 type byIndex []field
  47
  48 func (x byIndex) Len() int { return len(x) }
  49
  50 func (x byIndex) Swap(i, j int) { x[i], x[j] = x[j], x[i] }
  51
  52 func (x byIndex) Less(i, j int) bool {
  53         for k, xik := range x[i].index {
  54                 if k >= len(x[j].index) {
  55                         return false
  56                 }
  57                 if xik != x[j].index[k] {
  58                         return xik < x[j].index[k]
  59                 }
  60         }
  61         return len(x[i].index) < len(x[j].index)
  62 }
  63
  64 // typeFields returns a list of fields that TOML should recognize for the given
  65 // type. The algorithm is breadth-first search over the set of structs to
  66 // include - the top struct and then any reachable anonymous structs.
  67 func typeFields(t reflect.Type) []field {
  68         // Anonymous fields to explore at the current level and the next.
  69         current := []field{}
  70         next := []field{{typ: t}}
  71
  72         // Count of queued names for current level and the next.
  73         count := map[reflect.Type]int{}
  74         nextCount := map[reflect.Type]int{}
  75
  76         // Types already visited at an earlier level.
  77         visited := map[reflect.Type]bool{}
  78
  79         // Fields found.
  80         var fields []field
  81
  82         for len(next) > 0 {
  83                 current, next = next, current[:0]
  84                 count, nextCount = nextCount, map[reflect.Type]int{}
  85
  86                 for _, f := range current {
  87                         if visited[f.typ] {
  88                                 continue
  89                         }
  90                         visited[f.typ] = true
  91
  92                         // Scan f.typ for fields to include.
  93                         for i := 0; i < f.typ.NumField(); i++ {
  94                                 sf := f.typ.Field(i)
  95                                 if sf.PkgPath != "" && !sf.Anonymous { // unexported
  96                                         continue
  97                                 }
  98                                 opts := getOptions(sf.Tag)
  99                                 if opts.skip {
 100                                         continue
 101                                 }
 102                                 index := make([]int, len(f.index)+1)
 103                                 copy(index, f.index)
 104                                 index[len(f.index)] = i
 105
 106                                 ft := sf.Type
 107                                 if ft.Name() == "" && ft.Kind() == reflect.Ptr {
 108                                         // Follow pointer.
 109                                         ft = ft.Elem()
 110                                 }
 111
 112                                 // Record found field and index sequence.
 113                                 if opts.name != "" || !sf.Anonymous || ft.Kind() != reflect.Struct {
 114                                         tagged := opts.name != ""
 115                                         name := opts.name
 116                                         if name == "" {
 117                                                 name = sf.Name
 118                                         }
 119                                         fields = append(fields, field{name, tagged, index, ft})
 120                                         if count[f.typ] > 1 {
 121                                                 // If there were multiple instances, add a second,
 122                                                 // so that the annihilation code will see a duplicate.
 123                                                 // It only cares about the distinction between 1 or 2,
 124                                                 // so don't bother generating any more copies.
 125                                                 fields = append(fields, fields[len(fields)-1])
 126                                         }
 127                                         continue
 128                                 }
 129
 130                                 // Record new anonymous struct to explore in next round.
 131                                 nextCount[ft]++
 132                                 if nextCount[ft] == 1 {
 133                                         f := field{name: ft.Name(), index: index, typ: ft}
 134                                         next = append(next, f)
 135                                 }
 136                         }
 137                 }
 138         }
 139
 140         sort.Sort(byName(fields))
 141
 142         // Delete all fields that are hidden by the Go rules for embedded fields,
 143         // except that fields with TOML tags are promoted.
 144
 145         // The fields are sorted in primary order of name, secondary order
 146         // of field index length. Loop over names; for each name, delete
 147         // hidden fields by choosing the one dominant field that survives.
 148         out := fields[:0]
 149         for advance, i := 0, 0; i < len(fields); i += advance {
 150                 // One iteration per name.
 151                 // Find the sequence of fields with the name of this first field.
 152                 fi := fields[i]
 153                 name := fi.name
 154                 for advance = 1; i+advance < len(fields); advance++ {
 155                         fj := fields[i+advance]
 156                         if fj.name != name {
 157                                 break
 158                         }
 159                 }
 160                 if advance == 1 { // Only one field with this name
 161                         out = append(out, fi)
 162                         continue
 163                 }
 164                 dominant, ok := dominantField(fields[i : i+advance])
 165                 if ok {
 166                         out = append(out, dominant)
 167                 }
 168         }
 169
 170         fields = out
 171         sort.Sort(byIndex(fields))
 172
 173         return fields
 174 }
 175
 176 // dominantField looks through the fields, all of which are known to
 177 // have the same name, to find the single field that dominates the
 178 // others using Go's embedding rules, modified by the presence of
 179 // TOML tags. If there are multiple top-level fields, the boolean
 180 // will be false: This condition is an error in Go and we skip all
 181 // the fields.
 182 func dominantField(fields []field) (field, bool) {
 183         // The fields are sorted in increasing index-length order. The winner
 184         // must therefore be one with the shortest index length. Drop all
 185         // longer entries, which is easy: just truncate the slice.
 186         length := len(fields[0].index)
 187         tagged := -1 // Index of first tagged field.
 188         for i, f := range fields {
 189                 if len(f.index) > length {
 190                         fields = fields[:i]
 191                         break
 192                 }
 193                 if f.tag {
 194                         if tagged >= 0 {
 195                                 // Multiple tagged fields at the same level: conflict.
 196                                 // Return no field.
 197                                 return field{}, false
 198                         }
 199                         tagged = i
 200                 }
 201         }
 202         if tagged >= 0 {
 203                 return fields[tagged], true
 204         }
 205         // All remaining fields have the same length. If there's more than one,
 206         // we have a conflict (two fields named "X" at the same level) and we
 207         // return no field.
 208         if len(fields) > 1 {
 209                 return field{}, false
 210         }
 211         return fields[0], true
 212 }
 213
 214 var fieldCache struct {
 215         sync.RWMutex
 216         m map[reflect.Type][]field
 217 }
 218
 219 // cachedTypeFields is like typeFields but uses a cache to avoid repeated work.
 220 func cachedTypeFields(t reflect.Type) []field {
 221         fieldCache.RLock()
 222         f := fieldCache.m[t]
 223         fieldCache.RUnlock()
 224         if f != nil {
 225                 return f
 226         }
 227
 228         // Compute fields without lock.
 229         // Might duplicate effort but won't hold other computations back.
 230         f = typeFields(t)
 231         if f == nil {
 232                 f = []field{}
 233         }
 234
 235         fieldCache.Lock()
 236         if fieldCache.m == nil {
 237                 fieldCache.m = map[reflect.Type][]field{}
 238         }
 239         fieldCache.m[t] = f
 240         fieldCache.Unlock()
 241         return f
 242 }