1 package sa4010
2 3 import (
4 "honnef.co/go/tools/analysis/lint"
5 "honnef.co/go/tools/analysis/report"
6 "honnef.co/go/tools/go/ir"
7 "honnef.co/go/tools/internal/passes/buildir"
8 9 "golang.org/x/tools/go/analysis"
10 )
11 12 var SCAnalyzer = lint.InitializeAnalyzer(&lint.Analyzer{
13 Analyzer: &analysis.Analyzer{
14 Name: "SA4010",
15 Run: run,
16 Requires: []*analysis.Analyzer{buildir.Analyzer},
17 },
18 Doc: &lint.RawDocumentation{
19 Title: `The result of \'append\' will never be observed anywhere`,
20 Since: "2017.1",
21 Severity: lint.SeverityWarning,
22 MergeIf: lint.MergeIfAll,
23 },
24 })
25 26 var Analyzer = SCAnalyzer.Analyzer
27 28 func run(pass *analysis.Pass) (interface{}, error) {
29 isAppend := func(ins ir.Value) bool {
30 call, ok := ins.(*ir.Call)
31 if !ok {
32 return false
33 }
34 if call.Call.IsInvoke() {
35 return false
36 }
37 if builtin, ok := call.Call.Value.(*ir.Builtin); !ok || builtin.Name() != "append" {
38 return false
39 }
40 return true
41 }
42 43 // We have to be careful about aliasing.
44 // Multiple slices may refer to the same backing array,
45 // making appends observable even when we don't see the result of append be used anywhere.
46 //
47 // We will have to restrict ourselves to slices that have been allocated within the function,
48 // haven't been sliced,
49 // and haven't been passed anywhere that could retain them (such as function calls or memory stores).
50 //
51 // We check whether an append should be flagged in two steps.
52 //
53 // In the first step, we look at the data flow graph, starting in reverse from the argument to append, till we reach the root.
54 // This graph must only consist of the following instructions:
55 //
56 // - phi
57 // - sigma
58 // - slice
59 // - const nil
60 // - MakeSlice
61 // - Alloc
62 // - calls to append
63 //
64 // If this step succeeds, we look at all referrers of the values found in the first step, recursively.
65 // These referrers must either be in the set of values found in the first step,
66 // be DebugRefs,
67 // or fulfill the same type requirements as step 1, with the exception of appends, which are forbidden.
68 //
69 // If both steps succeed then we know that the backing array hasn't been aliased in an observable manner.
70 //
71 // We could relax these restrictions by making use of additional information:
72 // - if we passed the slice to a function that doesn't retain the slice then we can still flag it
73 // - if a slice has been sliced but is dead afterwards, we can flag appends to the new slice
74 75 // OPT(dh): We could cache the results of both validate functions.
76 // However, we only use these functions on values that we otherwise want to flag, which are very few.
77 // Not caching values hasn't increased the runtimes for the standard library nor k8s.
78 var validateArgument func(v ir.Value, seen map[ir.Value]struct{}) bool
79 validateArgument = func(v ir.Value, seen map[ir.Value]struct{}) bool {
80 if _, ok := seen[v]; ok {
81 // break cycle
82 return true
83 }
84 seen[v] = struct{}{}
85 switch v := v.(type) {
86 case *ir.Phi:
87 for _, edge := range v.Edges {
88 if !validateArgument(edge, seen) {
89 return false
90 }
91 }
92 return true
93 case *ir.Sigma:
94 return validateArgument(v.X, seen)
95 case *ir.Slice:
96 return validateArgument(v.X, seen)
97 case *ir.Const:
98 return true
99 case *ir.MakeSlice:
100 return true
101 case *ir.Alloc:
102 return true
103 case *ir.Call:
104 if isAppend(v) {
105 return validateArgument(v.Call.Args[0], seen)
106 }
107 return false
108 default:
109 return false
110 }
111 }
112 113 var validateReferrers func(v ir.Value, seen map[ir.Instruction]struct{}) bool
114 validateReferrers = func(v ir.Value, seen map[ir.Instruction]struct{}) bool {
115 for _, ref := range *v.Referrers() {
116 if _, ok := seen[ref]; ok {
117 continue
118 }
119 120 seen[ref] = struct{}{}
121 switch ref.(type) {
122 case *ir.Phi:
123 case *ir.Sigma:
124 case *ir.Slice:
125 case *ir.Const:
126 case *ir.MakeSlice:
127 case *ir.Alloc:
128 case *ir.DebugRef:
129 default:
130 return false
131 }
132 133 if ref, ok := ref.(ir.Value); ok {
134 if !validateReferrers(ref, seen) {
135 return false
136 }
137 }
138 }
139 return true
140 }
141 142 for _, fn := range pass.ResultOf[buildir.Analyzer].(*buildir.IR).SrcFuncs {
143 for _, block := range fn.Blocks {
144 for _, ins := range block.Instrs {
145 val, ok := ins.(ir.Value)
146 if !ok || !isAppend(val) {
147 continue
148 }
149 150 isUsed := false
151 visited := map[ir.Instruction]bool{}
152 var walkRefs func(refs []ir.Instruction)
153 walkRefs = func(refs []ir.Instruction) {
154 loop:
155 for _, ref := range refs {
156 if visited[ref] {
157 continue
158 }
159 visited[ref] = true
160 if _, ok := ref.(*ir.DebugRef); ok {
161 continue
162 }
163 switch ref := ref.(type) {
164 case *ir.Phi:
165 walkRefs(*ref.Referrers())
166 case *ir.Sigma:
167 walkRefs(*ref.Referrers())
168 case ir.Value:
169 if !isAppend(ref) {
170 isUsed = true
171 } else {
172 walkRefs(*ref.Referrers())
173 }
174 case ir.Instruction:
175 isUsed = true
176 break loop
177 }
178 }
179 }
180 181 refs := val.Referrers()
182 if refs == nil {
183 continue
184 }
185 walkRefs(*refs)
186 187 if isUsed {
188 continue
189 }
190 191 seen := map[ir.Value]struct{}{}
192 if !validateArgument(ins.(*ir.Call).Call.Args[0], seen) {
193 continue
194 }
195 196 seen2 := map[ir.Instruction]struct{}{}
197 for k := range seen {
198 // the only values we allow are also instructions, so this type assertion cannot fail
199 seen2[k.(ir.Instruction)] = struct{}{}
200 }
201 seen2[ins] = struct{}{}
202 failed := false
203 for v := range seen {
204 if !validateReferrers(v, seen2) {
205 failed = true
206 break
207 }
208 }
209 if !failed {
210 report.Report(pass, ins, "this result of append is never used, except maybe in other appends")
211 }
212 }
213 }
214 }
215 return nil, nil
216 }
217