| 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) (any, 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 |
} |