.config/coc/extensions/coc-go-data/tools/pkg/mod/golang.org/x/tools@v0.1.0/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                 if len(f.Names) <= 1 {
  83                         flat = append(flat, f)
  84                         continue
  85                 }
  86                 for _, name := range f.Names {
  87                         flat = append(flat, &ast.Field{
  88                                 Names: []*ast.Ident{name},
  89                                 Type:  f.Type,
  90                         })
  91                 }
  92         }
  93
  94         // Sort fields according to the optimal order.
  95         var reordered []*ast.Field
  96         for _, index := range indexes {
  97                 reordered = append(reordered, flat[index])
  98         }
  99
 100         newStr := &ast.StructType{
 101                 Fields: &ast.FieldList{
 102                         List: reordered,
 103                 },
 104         }
 105
 106         // Write the newly aligned struct node to get the content for suggested fixes.
 107         var buf bytes.Buffer
 108         if err := format.Node(&buf, token.NewFileSet(), newStr); err != nil {
 109                 return
 110         }
 111
 112         pass.Report(analysis.Diagnostic{
 113                 Pos:     node.Pos(),
 114                 End:     node.Pos() + token.Pos(len("struct")),
 115                 Message: message,
 116                 SuggestedFixes: []analysis.SuggestedFix{{
 117                         Message: "Rearrange fields",
 118                         TextEdits: []analysis.TextEdit{{
 119                                 Pos:     node.Pos(),
 120                                 End:     node.End(),
 121                                 NewText: buf.Bytes(),
 122                         }},
 123                 }},
 124         })
 125 }
 126
 127 func optimalOrder(str *types.Struct, sizes *gcSizes) (*types.Struct, []int) {
 128         nf := str.NumFields()
 129
 130         type elem struct {
 131                 index   int
 132                 alignof int64
 133                 sizeof  int64
 134                 ptrdata int64
 135         }
 136
 137         elems := make([]elem, nf)
 138         for i := 0; i < nf; i++ {
 139                 field := str.Field(i)
 140                 ft := field.Type()
 141                 elems[i] = elem{
 142                         i,
 143                         sizes.Alignof(ft),
 144                         sizes.Sizeof(ft),
 145                         sizes.ptrdata(ft),
 146                 }
 147         }
 148
 149         sort.Slice(elems, func(i, j int) bool {
 150                 ei := &elems[i]
 151                 ej := &elems[j]
 152
 153                 // Place zero sized objects before non-zero sized objects.
 154                 zeroi := ei.sizeof == 0
 155                 zeroj := ej.sizeof == 0
 156                 if zeroi != zeroj {
 157                         return zeroi
 158                 }
 159
 160                 // Next, place more tightly aligned objects before less tightly aligned objects.
 161                 if ei.alignof != ej.alignof {
 162                         return ei.alignof > ej.alignof
 163                 }
 164
 165                 // Place pointerful objects before pointer-free objects.
 166                 noptrsi := ei.ptrdata == 0
 167                 noptrsj := ej.ptrdata == 0
 168                 if noptrsi != noptrsj {
 169                         return noptrsj
 170                 }
 171
 172                 if !noptrsi {
 173                         // If both have pointers...
 174
 175                         // ... then place objects with less trailing
 176                         // non-pointer bytes earlier. That is, place
 177                         // the field with the most trailing
 178                         // non-pointer bytes at the end of the
 179                         // pointerful section.
 180                         traili := ei.sizeof - ei.ptrdata
 181                         trailj := ej.sizeof - ej.ptrdata
 182                         if traili != trailj {
 183                                 return traili < trailj
 184                         }
 185                 }
 186
 187                 // Lastly, order by size.
 188                 if ei.sizeof != ej.sizeof {
 189                         return ei.sizeof > ej.sizeof
 190                 }
 191
 192                 return false
 193         })
 194
 195         fields := make([]*types.Var, nf)
 196         indexes := make([]int, nf)
 197         for i, e := range elems {
 198                 fields[i] = str.Field(e.index)
 199                 indexes[i] = e.index
 200         }
 201         return types.NewStruct(fields, nil), indexes
 202 }
 203
 204 // Code below based on go/types.StdSizes.
 205
 206 type gcSizes struct {
 207         WordSize int64
 208         MaxAlign int64
 209 }
 210
 211 func (s *gcSizes) Alignof(T types.Type) int64 {
 212         // For arrays and structs, alignment is defined in terms
 213         // of alignment of the elements and fields, respectively.
 214         switch t := T.Underlying().(type) {
 215         case *types.Array:
 216                 // spec: "For a variable x of array type: unsafe.Alignof(x)
 217                 // is the same as unsafe.Alignof(x[0]), but at least 1."
 218                 return s.Alignof(t.Elem())
 219         case *types.Struct:
 220                 // spec: "For a variable x of struct type: unsafe.Alignof(x)
 221                 // is the largest of the values unsafe.Alignof(x.f) for each
 222                 // field f of x, but at least 1."
 223                 max := int64(1)
 224                 for i, nf := 0, t.NumFields(); i < nf; i++ {
 225                         if a := s.Alignof(t.Field(i).Type()); a > max {
 226                                 max = a
 227                         }
 228                 }
 229                 return max
 230         }
 231         a := s.Sizeof(T) // may be 0
 232         // spec: "For a variable x of any type: unsafe.Alignof(x) is at least 1."
 233         if a < 1 {
 234                 return 1
 235         }
 236         if a > s.MaxAlign {
 237                 return s.MaxAlign
 238         }
 239         return a
 240 }
 241
 242 var basicSizes = [...]byte{
 243         types.Bool:       1,
 244         types.Int8:       1,
 245         types.Int16:      2,
 246         types.Int32:      4,
 247         types.Int64:      8,
 248         types.Uint8:      1,
 249         types.Uint16:     2,
 250         types.Uint32:     4,
 251         types.Uint64:     8,
 252         types.Float32:    4,
 253         types.Float64:    8,
 254         types.Complex64:  8,
 255         types.Complex128: 16,
 256 }
 257
 258 func (s *gcSizes) Sizeof(T types.Type) int64 {
 259         switch t := T.Underlying().(type) {
 260         case *types.Basic:
 261                 k := t.Kind()
 262                 if int(k) < len(basicSizes) {
 263                         if s := basicSizes[k]; s > 0 {
 264                                 return int64(s)
 265                         }
 266                 }
 267                 if k == types.String {
 268                         return s.WordSize * 2
 269                 }
 270         case *types.Array:
 271                 return t.Len() * s.Sizeof(t.Elem())
 272         case *types.Slice:
 273                 return s.WordSize * 3
 274         case *types.Struct:
 275                 nf := t.NumFields()
 276                 if nf == 0 {
 277                         return 0
 278                 }
 279
 280                 var o int64
 281                 max := int64(1)
 282                 for i := 0; i < nf; i++ {
 283                         ft := t.Field(i).Type()
 284                         a, sz := s.Alignof(ft), s.Sizeof(ft)
 285                         if a > max {
 286                                 max = a
 287                         }
 288                         if i == nf-1 && sz == 0 && o != 0 {
 289                                 sz = 1
 290                         }
 291                         o = align(o, a) + sz
 292                 }
 293                 return align(o, max)
 294         case *types.Interface:
 295                 return s.WordSize * 2
 296         }
 297         return s.WordSize // catch-all
 298 }
 299
 300 // align returns the smallest y >= x such that y % a == 0.
 301 func align(x, a int64) int64 {
 302         y := x + a - 1
 303         return y - y%a
 304 }
 305
 306 func (s *gcSizes) ptrdata(T types.Type) int64 {
 307         switch t := T.Underlying().(type) {
 308         case *types.Basic:
 309                 switch t.Kind() {
 310                 case types.String, types.UnsafePointer:
 311                         return s.WordSize
 312                 }
 313                 return 0
 314         case *types.Chan, *types.Map, *types.Pointer, *types.Signature, *types.Slice:
 315                 return s.WordSize
 316         case *types.Interface:
 317                 return 2 * s.WordSize
 318         case *types.Array:
 319                 n := t.Len()
 320                 if n == 0 {
 321                         return 0
 322                 }
 323                 a := s.ptrdata(t.Elem())
 324                 if a == 0 {
 325                         return 0
 326                 }
 327                 z := s.Sizeof(t.Elem())
 328                 return (n-1)*z + a
 329         case *types.Struct:
 330                 nf := t.NumFields()
 331                 if nf == 0 {
 332                         return 0
 333                 }
 334
 335                 var o, p int64
 336                 for i := 0; i < nf; i++ {
 337                         ft := t.Field(i).Type()
 338                         a, sz := s.Alignof(ft), s.Sizeof(ft)
 339                         fp := s.ptrdata(ft)
 340                         o = align(o, a)
 341                         if fp != 0 {
 342                                 p = o + fp
 343                         }
 344                         o += sz
 345                 }
 346                 return p
 347         }
 348
 349         panic("impossible")
 350 }