.config/coc/extensions/coc-go-data/tools/pkg/mod/golang.org/x/tools@v0.1.1-0.20210319172145-bda8f5cee399/go/analysis/passes/fieldalignment/fieldalignment.go

   1 // Copyright 2020 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 fieldalignment defines an Analyzer that detects structs that would take less
   6 // memory if their fields were sorted.
   7 package fieldalignment
   8
   9 import (
  10         "bytes"
  11         "fmt"
  12         "go/ast"
  13         "go/format"
  14         "go/token"
  15         "go/types"
  16         "sort"
  17
  18         "golang.org/x/tools/go/analysis"
  19         "golang.org/x/tools/go/analysis/passes/inspect"
  20         "golang.org/x/tools/go/ast/inspector"
  21 )
  22
  23 const Doc = `find structs that would take less memory if their fields were sorted
  24
  25 This analyzer find structs that can be rearranged to take less memory, and provides
  26 a suggested edit with the optimal order.
  27 `
  28
  29 var Analyzer = &analysis.Analyzer{
  30         Name:     "fieldalignment",
  31         Doc:      Doc,
  32         Requires: []*analysis.Analyzer{inspect.Analyzer},
  33         Run:      run,
  34 }
  35
  36 func run(pass *analysis.Pass) (interface{}, error) {
  37         inspect := pass.ResultOf[inspect.Analyzer].(*inspector.Inspector)
  38         nodeFilter := []ast.Node{
  39                 (*ast.StructType)(nil),
  40         }
  41         inspect.Preorder(nodeFilter, func(node ast.Node) {
  42                 var s *ast.StructType
  43                 var ok bool
  44                 if s, ok = node.(*ast.StructType); !ok {
  45                         return
  46                 }
  47                 if tv, ok := pass.TypesInfo.Types[s]; ok {
  48                         fieldalignment(pass, s, tv.Type.(*types.Struct))
  49                 }
  50         })
  51         return nil, nil
  52 }
  53
  54 var unsafePointerTyp = types.Unsafe.Scope().Lookup("Pointer").(*types.TypeName).Type()
  55
  56 func fieldalignment(pass *analysis.Pass, node *ast.StructType, typ *types.Struct) {
  57         wordSize := pass.TypesSizes.Sizeof(unsafePointerTyp)
  58         maxAlign := pass.TypesSizes.Alignof(unsafePointerTyp)
  59
  60         s := gcSizes{wordSize, maxAlign}
  61         optimal, indexes := optimalOrder(typ, &s)
  62         optsz, optptrs := s.Sizeof(optimal), s.ptrdata(optimal)
  63
  64         var message string
  65         if sz := s.Sizeof(typ); sz != optsz {
  66                 message = fmt.Sprintf("struct of size %d could be %d", sz, optsz)
  67         } else if ptrs := s.ptrdata(typ); ptrs != optptrs {
  68                 message = fmt.Sprintf("struct with %d pointer bytes could be %d", ptrs, optptrs)
  69         } else {
  70                 // Already optimal order.
  71                 return
  72         }
  73
  74         // Flatten the ast node since it could have multiple field names per list item while
  75         // *types.Struct only have one item per field.
  76         // TODO: Preserve multi-named fields instead of flattening.
  77         var flat []*ast.Field
  78         for _, f := range node.Fields.List {
  79                 // TODO: Preserve comment, for now get rid of them.
  80                 //       See https://github.com/golang/go/issues/20744
  81                 f.Comment = nil
  82                 f.Doc = nil
  83                 if len(f.Names) <= 1 {
  84                         flat = append(flat, f)
  85                         continue
  86                 }
  87                 for _, name := range f.Names {
  88                         flat = append(flat, &ast.Field{
  89                                 Names: []*ast.Ident{name},
  90                                 Type:  f.Type,
  91                         })
  92                 }
  93         }
  94
  95         // Sort fields according to the optimal order.
  96         var reordered []*ast.Field
  97         for _, index := range indexes {
  98                 reordered = append(reordered, flat[index])
  99         }
 100
 101         newStr := &ast.StructType{
 102                 Fields: &ast.FieldList{
 103                         List: reordered,
 104                 },
 105         }
 106
 107         // Write the newly aligned struct node to get the content for suggested fixes.
 108         var buf bytes.Buffer
 109         if err := format.Node(&buf, token.NewFileSet(), newStr); err != nil {
 110                 return
 111         }
 112
 113         pass.Report(analysis.Diagnostic{
 114                 Pos:     node.Pos(),
 115                 End:     node.Pos() + token.Pos(len("struct")),
 116                 Message: message,
 117                 SuggestedFixes: []analysis.SuggestedFix{{
 118                         Message: "Rearrange fields",
 119                         TextEdits: []analysis.TextEdit{{
 120                                 Pos:     node.Pos(),
 121                                 End:     node.End(),
 122                                 NewText: buf.Bytes(),
 123                         }},
 124                 }},
 125         })
 126 }
 127
 128 func optimalOrder(str *types.Struct, sizes *gcSizes) (*types.Struct, []int) {
 129         nf := str.NumFields()
 130
 131         type elem struct {
 132                 index   int
 133                 alignof int64
 134                 sizeof  int64
 135                 ptrdata int64
 136         }
 137
 138         elems := make([]elem, nf)
 139         for i := 0; i < nf; i++ {
 140                 field := str.Field(i)
 141                 ft := field.Type()
 142                 elems[i] = elem{
 143                         i,
 144                         sizes.Alignof(ft),
 145                         sizes.Sizeof(ft),
 146                         sizes.ptrdata(ft),
 147                 }
 148         }
 149
 150         sort.Slice(elems, func(i, j int) bool {
 151                 ei := &elems[i]
 152                 ej := &elems[j]
 153
 154                 // Place zero sized objects before non-zero sized objects.
 155                 zeroi := ei.sizeof == 0
 156                 zeroj := ej.sizeof == 0
 157                 if zeroi != zeroj {
 158                         return zeroi
 159                 }
 160
 161                 // Next, place more tightly aligned objects before less tightly aligned objects.
 162                 if ei.alignof != ej.alignof {
 163                         return ei.alignof > ej.alignof
 164                 }
 165
 166                 // Place pointerful objects before pointer-free objects.
 167                 noptrsi := ei.ptrdata == 0
 168                 noptrsj := ej.ptrdata == 0
 169                 if noptrsi != noptrsj {
 170                         return noptrsj
 171                 }
 172
 173                 if !noptrsi {
 174                         // If both have pointers...
 175
 176                         // ... then place objects with less trailing
 177                         // non-pointer bytes earlier. That is, place
 178                         // the field with the most trailing
 179                         // non-pointer bytes at the end of the
 180                         // pointerful section.
 181                         traili := ei.sizeof - ei.ptrdata
 182                         trailj := ej.sizeof - ej.ptrdata
 183                         if traili != trailj {
 184                                 return traili < trailj
 185                         }
 186                 }
 187
 188                 // Lastly, order by size.
 189                 if ei.sizeof != ej.sizeof {
 190                         return ei.sizeof > ej.sizeof
 191                 }
 192
 193                 return false
 194         })
 195
 196         fields := make([]*types.Var, nf)
 197         indexes := make([]int, nf)
 198         for i, e := range elems {
 199                 fields[i] = str.Field(e.index)
 200                 indexes[i] = e.index
 201         }
 202         return types.NewStruct(fields, nil), indexes
 203 }
 204
 205 // Code below based on go/types.StdSizes.
 206
 207 type gcSizes struct {
 208         WordSize int64
 209         MaxAlign int64
 210 }
 211
 212 func (s *gcSizes) Alignof(T types.Type) int64 {
 213         // For arrays and structs, alignment is defined in terms
 214         // of alignment of the elements and fields, respectively.
 215         switch t := T.Underlying().(type) {
 216         case *types.Array:
 217                 // spec: "For a variable x of array type: unsafe.Alignof(x)
 218                 // is the same as unsafe.Alignof(x[0]), but at least 1."
 219                 return s.Alignof(t.Elem())
 220         case *types.Struct:
 221                 // spec: "For a variable x of struct type: unsafe.Alignof(x)
 222                 // is the largest of the values unsafe.Alignof(x.f) for each
 223                 // field f of x, but at least 1."
 224                 max := int64(1)
 225                 for i, nf := 0, t.NumFields(); i < nf; i++ {
 226                         if a := s.Alignof(t.Field(i).Type()); a > max {
 227                                 max = a
 228                         }
 229                 }
 230                 return max
 231         }
 232         a := s.Sizeof(T) // may be 0
 233         // spec: "For a variable x of any type: unsafe.Alignof(x) is at least 1."
 234         if a < 1 {
 235                 return 1
 236         }
 237         if a > s.MaxAlign {
 238                 return s.MaxAlign
 239         }
 240         return a
 241 }
 242
 243 var basicSizes = [...]byte{
 244         types.Bool:       1,
 245         types.Int8:       1,
 246         types.Int16:      2,
 247         types.Int32:      4,
 248         types.Int64:      8,
 249         types.Uint8:      1,
 250         types.Uint16:     2,
 251         types.Uint32:     4,
 252         types.Uint64:     8,
 253         types.Float32:    4,
 254         types.Float64:    8,
 255         types.Complex64:  8,
 256         types.Complex128: 16,
 257 }
 258
 259 func (s *gcSizes) Sizeof(T types.Type) int64 {
 260         switch t := T.Underlying().(type) {
 261         case *types.Basic:
 262                 k := t.Kind()
 263                 if int(k) < len(basicSizes) {
 264                         if s := basicSizes[k]; s > 0 {
 265                                 return int64(s)
 266                         }
 267                 }
 268                 if k == types.String {
 269                         return s.WordSize * 2
 270                 }
 271         case *types.Array:
 272                 return t.Len() * s.Sizeof(t.Elem())
 273         case *types.Slice:
 274                 return s.WordSize * 3
 275         case *types.Struct:
 276                 nf := t.NumFields()
 277                 if nf == 0 {
 278                         return 0
 279                 }
 280
 281                 var o int64
 282                 max := int64(1)
 283                 for i := 0; i < nf; i++ {
 284                         ft := t.Field(i).Type()
 285                         a, sz := s.Alignof(ft), s.Sizeof(ft)
 286                         if a > max {
 287                                 max = a
 288                         }
 289                         if i == nf-1 && sz == 0 && o != 0 {
 290                                 sz = 1
 291                         }
 292                         o = align(o, a) + sz
 293                 }
 294                 return align(o, max)
 295         case *types.Interface:
 296                 return s.WordSize * 2
 297         }
 298         return s.WordSize // catch-all
 299 }
 300
 301 // align returns the smallest y >= x such that y % a == 0.
 302 func align(x, a int64) int64 {
 303         y := x + a - 1
 304         return y - y%a
 305 }
 306
 307 func (s *gcSizes) ptrdata(T types.Type) int64 {
 308         switch t := T.Underlying().(type) {
 309         case *types.Basic:
 310                 switch t.Kind() {
 311                 case types.String, types.UnsafePointer:
 312                         return s.WordSize
 313                 }
 314                 return 0
 315         case *types.Chan, *types.Map, *types.Pointer, *types.Signature, *types.Slice:
 316                 return s.WordSize
 317         case *types.Interface:
 318                 return 2 * s.WordSize
 319         case *types.Array:
 320                 n := t.Len()
 321                 if n == 0 {
 322                         return 0
 323                 }
 324                 a := s.ptrdata(t.Elem())
 325                 if a == 0 {
 326                         return 0
 327                 }
 328                 z := s.Sizeof(t.Elem())
 329                 return (n-1)*z + a
 330         case *types.Struct:
 331                 nf := t.NumFields()
 332                 if nf == 0 {
 333                         return 0
 334                 }
 335
 336                 var o, p int64
 337                 for i := 0; i < nf; i++ {
 338                         ft := t.Field(i).Type()
 339                         a, sz := s.Alignof(ft), s.Sizeof(ft)
 340                         fp := s.ptrdata(ft)
 341                         o = align(o, a)
 342                         if fp != 0 {
 343                                 p = o + fp
 344                         }
 345                         o += sz
 346                 }
 347                 return p
 348         }
 349
 350         panic("impossible")
 351 }