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.
5 // Package fieldalignment defines an Analyzer that detects structs that would take less
6 // memory if their fields were sorted.
18 "golang.org/x/tools/go/analysis"
19 "golang.org/x/tools/go/analysis/passes/inspect"
20 "golang.org/x/tools/go/ast/inspector"
23 const Doc = `find structs that would take less memory if their fields were sorted
25 This analyzer find structs that can be rearranged to take less memory, and provides
26 a suggested edit with the optimal order.
29 var Analyzer = &analysis.Analyzer{
30 Name: "fieldalignment",
32 Requires: []*analysis.Analyzer{inspect.Analyzer},
36 func run(pass *analysis.Pass) (interface{}, error) {
37 inspect := pass.ResultOf[inspect.Analyzer].(*inspector.Inspector)
38 nodeFilter := []ast.Node{
39 (*ast.StructType)(nil),
41 inspect.Preorder(nodeFilter, func(node ast.Node) {
44 if s, ok = node.(*ast.StructType); !ok {
47 if tv, ok := pass.TypesInfo.Types[s]; ok {
48 fieldalignment(pass, s, tv.Type.(*types.Struct))
54 var unsafePointerTyp = types.Unsafe.Scope().Lookup("Pointer").(*types.TypeName).Type()
56 func fieldalignment(pass *analysis.Pass, node *ast.StructType, typ *types.Struct) {
57 wordSize := pass.TypesSizes.Sizeof(unsafePointerTyp)
58 maxAlign := pass.TypesSizes.Alignof(unsafePointerTyp)
60 s := gcSizes{wordSize, maxAlign}
61 optimal, indexes := optimalOrder(typ, &s)
62 optsz, optptrs := s.Sizeof(optimal), s.ptrdata(optimal)
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)
70 // Already optimal order.
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.
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
82 if len(f.Names) <= 1 {
83 flat = append(flat, f)
86 for _, name := range f.Names {
87 flat = append(flat, &ast.Field{
88 Names: []*ast.Ident{name},
94 // Sort fields according to the optimal order.
95 var reordered []*ast.Field
96 for _, index := range indexes {
97 reordered = append(reordered, flat[index])
100 newStr := &ast.StructType{
101 Fields: &ast.FieldList{
106 // Write the newly aligned struct node to get the content for suggested fixes.
108 if err := format.Node(&buf, token.NewFileSet(), newStr); err != nil {
112 pass.Report(analysis.Diagnostic{
114 End: node.Pos() + token.Pos(len("struct")),
116 SuggestedFixes: []analysis.SuggestedFix{{
117 Message: "Rearrange fields",
118 TextEdits: []analysis.TextEdit{{
121 NewText: buf.Bytes(),
127 func optimalOrder(str *types.Struct, sizes *gcSizes) (*types.Struct, []int) {
128 nf := str.NumFields()
137 elems := make([]elem, nf)
138 for i := 0; i < nf; i++ {
139 field := str.Field(i)
149 sort.Slice(elems, func(i, j int) bool {
153 // Place zero sized objects before non-zero sized objects.
154 zeroi := ei.sizeof == 0
155 zeroj := ej.sizeof == 0
160 // Next, place more tightly aligned objects before less tightly aligned objects.
161 if ei.alignof != ej.alignof {
162 return ei.alignof > ej.alignof
165 // Place pointerful objects before pointer-free objects.
166 noptrsi := ei.ptrdata == 0
167 noptrsj := ej.ptrdata == 0
168 if noptrsi != noptrsj {
173 // If both have pointers...
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
187 // Lastly, order by size.
188 if ei.sizeof != ej.sizeof {
189 return ei.sizeof > ej.sizeof
195 fields := make([]*types.Var, nf)
196 indexes := make([]int, nf)
197 for i, e := range elems {
198 fields[i] = str.Field(e.index)
201 return types.NewStruct(fields, nil), indexes
204 // Code below based on go/types.StdSizes.
206 type gcSizes struct {
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) {
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())
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."
224 for i, nf := 0, t.NumFields(); i < nf; i++ {
225 if a := s.Alignof(t.Field(i).Type()); a > max {
231 a := s.Sizeof(T) // may be 0
232 // spec: "For a variable x of any type: unsafe.Alignof(x) is at least 1."
242 var basicSizes = [...]byte{
255 types.Complex128: 16,
258 func (s *gcSizes) Sizeof(T types.Type) int64 {
259 switch t := T.Underlying().(type) {
262 if int(k) < len(basicSizes) {
263 if s := basicSizes[k]; s > 0 {
267 if k == types.String {
268 return s.WordSize * 2
271 return t.Len() * s.Sizeof(t.Elem())
273 return s.WordSize * 3
282 for i := 0; i < nf; i++ {
283 ft := t.Field(i).Type()
284 a, sz := s.Alignof(ft), s.Sizeof(ft)
288 if i == nf-1 && sz == 0 && o != 0 {
294 case *types.Interface:
295 return s.WordSize * 2
297 return s.WordSize // catch-all
300 // align returns the smallest y >= x such that y % a == 0.
301 func align(x, a int64) int64 {
306 func (s *gcSizes) ptrdata(T types.Type) int64 {
307 switch t := T.Underlying().(type) {
310 case types.String, types.UnsafePointer:
314 case *types.Chan, *types.Map, *types.Pointer, *types.Signature, *types.Slice:
316 case *types.Interface:
317 return 2 * s.WordSize
323 a := s.ptrdata(t.Elem())
327 z := s.Sizeof(t.Elem())
336 for i := 0; i < nf; i++ {
337 ft := t.Field(i).Type()
338 a, sz := s.Alignof(ft), s.Sizeof(ft)