aboutsummaryrefslogtreecommitdiff
path: root/vendor/honnef.co/go/tools/staticcheck
diff options
context:
space:
mode:
authorJoseph Richey <joerichey@google.com>2018-08-30 13:41:49 -0700
committerGitHub <noreply@github.com>2018-08-30 13:41:49 -0700
commit0f451a722918f39fa07bd9337e4a14ca154b13ae (patch)
tree9868ffed8cb74357a06e63b88c56d71b13b415af /vendor/honnef.co/go/tools/staticcheck
parent1e1b67dae6c3ae3b5acb5ce377b01b286c3e676b (diff)
parent1c9bafdec78b8f238a82314b6d9c566a951486c2 (diff)
Merge pull request #107 from google/mod
Use Go Modules and support Go 1.11 building
Diffstat (limited to 'vendor/honnef.co/go/tools/staticcheck')
-rw-r--r--vendor/honnef.co/go/tools/staticcheck/buildtag.go21
-rw-r--r--vendor/honnef.co/go/tools/staticcheck/lint.go2738
-rw-r--r--vendor/honnef.co/go/tools/staticcheck/rules.go321
-rw-r--r--vendor/honnef.co/go/tools/staticcheck/vrp/channel.go73
-rw-r--r--vendor/honnef.co/go/tools/staticcheck/vrp/int.go476
-rw-r--r--vendor/honnef.co/go/tools/staticcheck/vrp/slice.go273
-rw-r--r--vendor/honnef.co/go/tools/staticcheck/vrp/string.go258
-rw-r--r--vendor/honnef.co/go/tools/staticcheck/vrp/vrp.go1049
8 files changed, 0 insertions, 5209 deletions
diff --git a/vendor/honnef.co/go/tools/staticcheck/buildtag.go b/vendor/honnef.co/go/tools/staticcheck/buildtag.go
deleted file mode 100644
index 27c31c0..0000000
--- a/vendor/honnef.co/go/tools/staticcheck/buildtag.go
+++ /dev/null
@@ -1,21 +0,0 @@
-package staticcheck
-
-import (
- "go/ast"
- "strings"
-
- "honnef.co/go/tools/lint"
-)
-
-func buildTags(f *ast.File) [][]string {
- var out [][]string
- for _, line := range strings.Split(lint.Preamble(f), "\n") {
- if !strings.HasPrefix(line, "+build ") {
- continue
- }
- line = strings.TrimSpace(strings.TrimPrefix(line, "+build "))
- fields := strings.Fields(line)
- out = append(out, fields)
- }
- return out
-}
diff --git a/vendor/honnef.co/go/tools/staticcheck/lint.go b/vendor/honnef.co/go/tools/staticcheck/lint.go
deleted file mode 100644
index fdc395e..0000000
--- a/vendor/honnef.co/go/tools/staticcheck/lint.go
+++ /dev/null
@@ -1,2738 +0,0 @@
-// Package staticcheck contains a linter for Go source code.
-package staticcheck // import "honnef.co/go/tools/staticcheck"
-
-import (
- "fmt"
- "go/ast"
- "go/constant"
- "go/token"
- "go/types"
- htmltemplate "html/template"
- "net/http"
- "regexp"
- "sort"
- "strconv"
- "strings"
- "sync"
- texttemplate "text/template"
-
- "honnef.co/go/tools/deprecated"
- "honnef.co/go/tools/functions"
- "honnef.co/go/tools/internal/sharedcheck"
- "honnef.co/go/tools/lint"
- "honnef.co/go/tools/ssa"
- "honnef.co/go/tools/staticcheck/vrp"
-
- "golang.org/x/tools/go/ast/astutil"
-)
-
-func validRegexp(call *Call) {
- arg := call.Args[0]
- err := ValidateRegexp(arg.Value)
- if err != nil {
- arg.Invalid(err.Error())
- }
-}
-
-type runeSlice []rune
-
-func (rs runeSlice) Len() int { return len(rs) }
-func (rs runeSlice) Less(i int, j int) bool { return rs[i] < rs[j] }
-func (rs runeSlice) Swap(i int, j int) { rs[i], rs[j] = rs[j], rs[i] }
-
-func utf8Cutset(call *Call) {
- arg := call.Args[1]
- if InvalidUTF8(arg.Value) {
- arg.Invalid(MsgInvalidUTF8)
- }
-}
-
-func uniqueCutset(call *Call) {
- arg := call.Args[1]
- if !UniqueStringCutset(arg.Value) {
- arg.Invalid(MsgNonUniqueCutset)
- }
-}
-
-func unmarshalPointer(name string, arg int) CallCheck {
- return func(call *Call) {
- if !Pointer(call.Args[arg].Value) {
- call.Args[arg].Invalid(fmt.Sprintf("%s expects to unmarshal into a pointer, but the provided value is not a pointer", name))
- }
- }
-}
-
-func pointlessIntMath(call *Call) {
- if ConvertedFromInt(call.Args[0].Value) {
- call.Invalid(fmt.Sprintf("calling %s on a converted integer is pointless", lint.CallName(call.Instr.Common())))
- }
-}
-
-func checkValidHostPort(arg int) CallCheck {
- return func(call *Call) {
- if !ValidHostPort(call.Args[arg].Value) {
- call.Args[arg].Invalid(MsgInvalidHostPort)
- }
- }
-}
-
-var (
- checkRegexpRules = map[string]CallCheck{
- "regexp.MustCompile": validRegexp,
- "regexp.Compile": validRegexp,
- }
-
- checkTimeParseRules = map[string]CallCheck{
- "time.Parse": func(call *Call) {
- arg := call.Args[0]
- err := ValidateTimeLayout(arg.Value)
- if err != nil {
- arg.Invalid(err.Error())
- }
- },
- }
-
- checkEncodingBinaryRules = map[string]CallCheck{
- "encoding/binary.Write": func(call *Call) {
- arg := call.Args[2]
- if !CanBinaryMarshal(call.Job, arg.Value) {
- arg.Invalid(fmt.Sprintf("value of type %s cannot be used with binary.Write", arg.Value.Value.Type()))
- }
- },
- }
-
- checkURLsRules = map[string]CallCheck{
- "net/url.Parse": func(call *Call) {
- arg := call.Args[0]
- err := ValidateURL(arg.Value)
- if err != nil {
- arg.Invalid(err.Error())
- }
- },
- }
-
- checkSyncPoolValueRules = map[string]CallCheck{
- "(*sync.Pool).Put": func(call *Call) {
- arg := call.Args[0]
- typ := arg.Value.Value.Type()
- if !lint.IsPointerLike(typ) {
- arg.Invalid("argument should be pointer-like to avoid allocations")
- }
- },
- }
-
- checkRegexpFindAllRules = map[string]CallCheck{
- "(*regexp.Regexp).FindAll": RepeatZeroTimes("a FindAll method", 1),
- "(*regexp.Regexp).FindAllIndex": RepeatZeroTimes("a FindAll method", 1),
- "(*regexp.Regexp).FindAllString": RepeatZeroTimes("a FindAll method", 1),
- "(*regexp.Regexp).FindAllStringIndex": RepeatZeroTimes("a FindAll method", 1),
- "(*regexp.Regexp).FindAllStringSubmatch": RepeatZeroTimes("a FindAll method", 1),
- "(*regexp.Regexp).FindAllStringSubmatchIndex": RepeatZeroTimes("a FindAll method", 1),
- "(*regexp.Regexp).FindAllSubmatch": RepeatZeroTimes("a FindAll method", 1),
- "(*regexp.Regexp).FindAllSubmatchIndex": RepeatZeroTimes("a FindAll method", 1),
- }
-
- checkUTF8CutsetRules = map[string]CallCheck{
- "strings.IndexAny": utf8Cutset,
- "strings.LastIndexAny": utf8Cutset,
- "strings.ContainsAny": utf8Cutset,
- "strings.Trim": utf8Cutset,
- "strings.TrimLeft": utf8Cutset,
- "strings.TrimRight": utf8Cutset,
- }
-
- checkUniqueCutsetRules = map[string]CallCheck{
- "strings.Trim": uniqueCutset,
- "strings.TrimLeft": uniqueCutset,
- "strings.TrimRight": uniqueCutset,
- }
-
- checkUnmarshalPointerRules = map[string]CallCheck{
- "encoding/xml.Unmarshal": unmarshalPointer("xml.Unmarshal", 1),
- "(*encoding/xml.Decoder).Decode": unmarshalPointer("Decode", 0),
- "encoding/json.Unmarshal": unmarshalPointer("json.Unmarshal", 1),
- "(*encoding/json.Decoder).Decode": unmarshalPointer("Decode", 0),
- }
-
- checkUnbufferedSignalChanRules = map[string]CallCheck{
- "os/signal.Notify": func(call *Call) {
- arg := call.Args[0]
- if UnbufferedChannel(arg.Value) {
- arg.Invalid("the channel used with signal.Notify should be buffered")
- }
- },
- }
-
- checkMathIntRules = map[string]CallCheck{
- "math.Ceil": pointlessIntMath,
- "math.Floor": pointlessIntMath,
- "math.IsNaN": pointlessIntMath,
- "math.Trunc": pointlessIntMath,
- "math.IsInf": pointlessIntMath,
- }
-
- checkStringsReplaceZeroRules = map[string]CallCheck{
- "strings.Replace": RepeatZeroTimes("strings.Replace", 3),
- "bytes.Replace": RepeatZeroTimes("bytes.Replace", 3),
- }
-
- checkListenAddressRules = map[string]CallCheck{
- "net/http.ListenAndServe": checkValidHostPort(0),
- "net/http.ListenAndServeTLS": checkValidHostPort(0),
- }
-
- checkBytesEqualIPRules = map[string]CallCheck{
- "bytes.Equal": func(call *Call) {
- if ConvertedFrom(call.Args[0].Value, "net.IP") && ConvertedFrom(call.Args[1].Value, "net.IP") {
- call.Invalid("use net.IP.Equal to compare net.IPs, not bytes.Equal")
- }
- },
- }
-
- checkRegexpMatchLoopRules = map[string]CallCheck{
- "regexp.Match": loopedRegexp("regexp.Match"),
- "regexp.MatchReader": loopedRegexp("regexp.MatchReader"),
- "regexp.MatchString": loopedRegexp("regexp.MatchString"),
- }
-)
-
-type Checker struct {
- CheckGenerated bool
- funcDescs *functions.Descriptions
- deprecatedObjs map[types.Object]string
- nodeFns map[ast.Node]*ssa.Function
-}
-
-func NewChecker() *Checker {
- return &Checker{}
-}
-
-func (*Checker) Name() string { return "staticcheck" }
-func (*Checker) Prefix() string { return "SA" }
-
-func (c *Checker) Funcs() map[string]lint.Func {
- return map[string]lint.Func{
- "SA1000": c.callChecker(checkRegexpRules),
- "SA1001": c.CheckTemplate,
- "SA1002": c.callChecker(checkTimeParseRules),
- "SA1003": c.callChecker(checkEncodingBinaryRules),
- "SA1004": c.CheckTimeSleepConstant,
- "SA1005": c.CheckExec,
- "SA1006": c.CheckUnsafePrintf,
- "SA1007": c.callChecker(checkURLsRules),
- "SA1008": c.CheckCanonicalHeaderKey,
- "SA1009": nil,
- "SA1010": c.callChecker(checkRegexpFindAllRules),
- "SA1011": c.callChecker(checkUTF8CutsetRules),
- "SA1012": c.CheckNilContext,
- "SA1013": c.CheckSeeker,
- "SA1014": c.callChecker(checkUnmarshalPointerRules),
- "SA1015": c.CheckLeakyTimeTick,
- "SA1016": c.CheckUntrappableSignal,
- "SA1017": c.callChecker(checkUnbufferedSignalChanRules),
- "SA1018": c.callChecker(checkStringsReplaceZeroRules),
- "SA1019": c.CheckDeprecated,
- "SA1020": c.callChecker(checkListenAddressRules),
- "SA1021": c.callChecker(checkBytesEqualIPRules),
- "SA1022": nil,
- "SA1023": c.CheckWriterBufferModified,
- "SA1024": c.callChecker(checkUniqueCutsetRules),
-
- "SA2000": c.CheckWaitgroupAdd,
- "SA2001": c.CheckEmptyCriticalSection,
- "SA2002": c.CheckConcurrentTesting,
- "SA2003": c.CheckDeferLock,
-
- "SA3000": c.CheckTestMainExit,
- "SA3001": c.CheckBenchmarkN,
-
- "SA4000": c.CheckLhsRhsIdentical,
- "SA4001": c.CheckIneffectiveCopy,
- "SA4002": c.CheckDiffSizeComparison,
- "SA4003": c.CheckUnsignedComparison,
- "SA4004": c.CheckIneffectiveLoop,
- "SA4005": nil,
- "SA4006": c.CheckUnreadVariableValues,
- // "SA4007": c.CheckPredeterminedBooleanExprs,
- "SA4007": nil,
- "SA4008": c.CheckLoopCondition,
- "SA4009": c.CheckArgOverwritten,
- "SA4010": c.CheckIneffectiveAppend,
- "SA4011": c.CheckScopedBreak,
- "SA4012": c.CheckNaNComparison,
- "SA4013": c.CheckDoubleNegation,
- "SA4014": c.CheckRepeatedIfElse,
- "SA4015": c.callChecker(checkMathIntRules),
- "SA4016": c.CheckSillyBitwiseOps,
- "SA4017": c.CheckPureFunctions,
- "SA4018": c.CheckSelfAssignment,
- "SA4019": c.CheckDuplicateBuildConstraints,
-
- "SA5000": c.CheckNilMaps,
- "SA5001": c.CheckEarlyDefer,
- "SA5002": c.CheckInfiniteEmptyLoop,
- "SA5003": c.CheckDeferInInfiniteLoop,
- "SA5004": c.CheckLoopEmptyDefault,
- "SA5005": c.CheckCyclicFinalizer,
- // "SA5006": c.CheckSliceOutOfBounds,
- "SA5007": c.CheckInfiniteRecursion,
-
- "SA6000": c.callChecker(checkRegexpMatchLoopRules),
- "SA6001": c.CheckMapBytesKey,
- "SA6002": c.callChecker(checkSyncPoolValueRules),
- "SA6003": c.CheckRangeStringRunes,
- "SA6004": nil,
-
- "SA9000": nil,
- "SA9001": c.CheckDubiousDeferInChannelRangeLoop,
- "SA9002": c.CheckNonOctalFileMode,
- "SA9003": c.CheckEmptyBranch,
- }
-}
-
-func (c *Checker) filterGenerated(files []*ast.File) []*ast.File {
- if c.CheckGenerated {
- return files
- }
- var out []*ast.File
- for _, f := range files {
- if !lint.IsGenerated(f) {
- out = append(out, f)
- }
- }
- return out
-}
-
-func (c *Checker) deprecateObject(m map[types.Object]string, prog *lint.Program, obj types.Object) {
- if obj.Pkg() == nil {
- return
- }
-
- f := prog.File(obj)
- if f == nil {
- return
- }
- msg := c.deprecationMessage(f, prog.Prog.Fset, obj)
- if msg != "" {
- m[obj] = msg
- }
-}
-
-func (c *Checker) Init(prog *lint.Program) {
- wg := &sync.WaitGroup{}
- wg.Add(3)
- go func() {
- c.funcDescs = functions.NewDescriptions(prog.SSA)
- for _, fn := range prog.AllFunctions {
- if fn.Blocks != nil {
- applyStdlibKnowledge(fn)
- ssa.OptimizeBlocks(fn)
- }
- }
- wg.Done()
- }()
-
- go func() {
- c.nodeFns = lint.NodeFns(prog.Packages)
- wg.Done()
- }()
-
- go func() {
- c.deprecatedObjs = map[types.Object]string{}
- for _, ssapkg := range prog.SSA.AllPackages() {
- ssapkg := ssapkg
- for _, member := range ssapkg.Members {
- obj := member.Object()
- if obj == nil {
- continue
- }
- c.deprecateObject(c.deprecatedObjs, prog, obj)
- if typ, ok := obj.Type().(*types.Named); ok {
- for i := 0; i < typ.NumMethods(); i++ {
- meth := typ.Method(i)
- c.deprecateObject(c.deprecatedObjs, prog, meth)
- }
-
- if iface, ok := typ.Underlying().(*types.Interface); ok {
- for i := 0; i < iface.NumExplicitMethods(); i++ {
- meth := iface.ExplicitMethod(i)
- c.deprecateObject(c.deprecatedObjs, prog, meth)
- }
- }
- }
- if typ, ok := obj.Type().Underlying().(*types.Struct); ok {
- n := typ.NumFields()
- for i := 0; i < n; i++ {
- // FIXME(dh): This code will not find deprecated
- // fields in anonymous structs.
- field := typ.Field(i)
- c.deprecateObject(c.deprecatedObjs, prog, field)
- }
- }
- }
- }
- wg.Done()
- }()
-
- wg.Wait()
-}
-
-func (c *Checker) deprecationMessage(file *ast.File, fset *token.FileSet, obj types.Object) (message string) {
- pos := obj.Pos()
- path, _ := astutil.PathEnclosingInterval(file, pos, pos)
- if len(path) <= 2 {
- return ""
- }
- var docs []*ast.CommentGroup
- switch n := path[1].(type) {
- case *ast.FuncDecl:
- docs = append(docs, n.Doc)
- case *ast.Field:
- docs = append(docs, n.Doc)
- case *ast.ValueSpec:
- docs = append(docs, n.Doc)
- if len(path) >= 3 {
- if n, ok := path[2].(*ast.GenDecl); ok {
- docs = append(docs, n.Doc)
- }
- }
- case *ast.TypeSpec:
- docs = append(docs, n.Doc)
- if len(path) >= 3 {
- if n, ok := path[2].(*ast.GenDecl); ok {
- docs = append(docs, n.Doc)
- }
- }
- default:
- return ""
- }
-
- for _, doc := range docs {
- if doc == nil {
- continue
- }
- parts := strings.Split(doc.Text(), "\n\n")
- last := parts[len(parts)-1]
- if !strings.HasPrefix(last, "Deprecated: ") {
- continue
- }
- alt := last[len("Deprecated: "):]
- alt = strings.Replace(alt, "\n", " ", -1)
- return alt
- }
- return ""
-}
-
-func (c *Checker) isInLoop(b *ssa.BasicBlock) bool {
- sets := c.funcDescs.Get(b.Parent()).Loops
- for _, set := range sets {
- if set[b] {
- return true
- }
- }
- return false
-}
-
-func applyStdlibKnowledge(fn *ssa.Function) {
- if len(fn.Blocks) == 0 {
- return
- }
-
- // comma-ok receiving from a time.Tick channel will never return
- // ok == false, so any branching on the value of ok can be
- // replaced with an unconditional jump. This will primarily match
- // `for range time.Tick(x)` loops, but it can also match
- // user-written code.
- for _, block := range fn.Blocks {
- if len(block.Instrs) < 3 {
- continue
- }
- if len(block.Succs) != 2 {
- continue
- }
- var instrs []*ssa.Instruction
- for i, ins := range block.Instrs {
- if _, ok := ins.(*ssa.DebugRef); ok {
- continue
- }
- instrs = append(instrs, &block.Instrs[i])
- }
-
- for i, ins := range instrs {
- unop, ok := (*ins).(*ssa.UnOp)
- if !ok || unop.Op != token.ARROW {
- continue
- }
- call, ok := unop.X.(*ssa.Call)
- if !ok {
- continue
- }
- if !lint.IsCallTo(call.Common(), "time.Tick") {
- continue
- }
- ex, ok := (*instrs[i+1]).(*ssa.Extract)
- if !ok || ex.Tuple != unop || ex.Index != 1 {
- continue
- }
-
- ifstmt, ok := (*instrs[i+2]).(*ssa.If)
- if !ok || ifstmt.Cond != ex {
- continue
- }
-
- *instrs[i+2] = ssa.NewJump(block)
- succ := block.Succs[1]
- block.Succs = block.Succs[0:1]
- succ.RemovePred(block)
- }
- }
-}
-
-func hasType(j *lint.Job, expr ast.Expr, name string) bool {
- return types.TypeString(j.Program.Info.TypeOf(expr), nil) == name
-}
-
-func (c *Checker) CheckUntrappableSignal(j *lint.Job) {
- fn := func(node ast.Node) bool {
- call, ok := node.(*ast.CallExpr)
- if !ok {
- return true
- }
- if !j.IsCallToAnyAST(call,
- "os/signal.Ignore", "os/signal.Notify", "os/signal.Reset") {
- return true
- }
- for _, arg := range call.Args {
- if conv, ok := arg.(*ast.CallExpr); ok && isName(j, conv.Fun, "os.Signal") {
- arg = conv.Args[0]
- }
-
- if isName(j, arg, "os.Kill") || isName(j, arg, "syscall.SIGKILL") {
- j.Errorf(arg, "%s cannot be trapped (did you mean syscall.SIGTERM?)", j.Render(arg))
- }
- if isName(j, arg, "syscall.SIGSTOP") {
- j.Errorf(arg, "%s signal cannot be trapped", j.Render(arg))
- }
- }
- return true
- }
- for _, f := range j.Program.Files {
- ast.Inspect(f, fn)
- }
-}
-
-func (c *Checker) CheckTemplate(j *lint.Job) {
- fn := func(node ast.Node) bool {
- call, ok := node.(*ast.CallExpr)
- if !ok {
- return true
- }
- var kind string
- if j.IsCallToAST(call, "(*text/template.Template).Parse") {
- kind = "text"
- } else if j.IsCallToAST(call, "(*html/template.Template).Parse") {
- kind = "html"
- } else {
- return true
- }
- sel := call.Fun.(*ast.SelectorExpr)
- if !j.IsCallToAST(sel.X, "text/template.New") &&
- !j.IsCallToAST(sel.X, "html/template.New") {
- // TODO(dh): this is a cheap workaround for templates with
- // different delims. A better solution with less false
- // negatives would use data flow analysis to see where the
- // template comes from and where it has been
- return true
- }
- s, ok := j.ExprToString(call.Args[0])
- if !ok {
- return true
- }
- var err error
- switch kind {
- case "text":
- _, err = texttemplate.New("").Parse(s)
- case "html":
- _, err = htmltemplate.New("").Parse(s)
- }
- if err != nil {
- // TODO(dominikh): whitelist other parse errors, if any
- if strings.Contains(err.Error(), "unexpected") {
- j.Errorf(call.Args[0], "%s", err)
- }
- }
- return true
- }
- for _, f := range j.Program.Files {
- ast.Inspect(f, fn)
- }
-}
-
-func (c *Checker) CheckTimeSleepConstant(j *lint.Job) {
- fn := func(node ast.Node) bool {
- call, ok := node.(*ast.CallExpr)
- if !ok {
- return true
- }
- if !j.IsCallToAST(call, "time.Sleep") {
- return true
- }
- lit, ok := call.Args[0].(*ast.BasicLit)
- if !ok {
- return true
- }
- n, err := strconv.Atoi(lit.Value)
- if err != nil {
- return true
- }
- if n == 0 || n > 120 {
- // time.Sleep(0) is a seldomly used pattern in concurrency
- // tests. >120 might be intentional. 120 was chosen
- // because the user could've meant 2 minutes.
- return true
- }
- recommendation := "time.Sleep(time.Nanosecond)"
- if n != 1 {
- recommendation = fmt.Sprintf("time.Sleep(%d * time.Nanosecond)", n)
- }
- j.Errorf(call.Args[0], "sleeping for %d nanoseconds is probably a bug. Be explicit if it isn't: %s", n, recommendation)
- return true
- }
- for _, f := range j.Program.Files {
- ast.Inspect(f, fn)
- }
-}
-
-func (c *Checker) CheckWaitgroupAdd(j *lint.Job) {
- fn := func(node ast.Node) bool {
- g, ok := node.(*ast.GoStmt)
- if !ok {
- return true
- }
- fun, ok := g.Call.Fun.(*ast.FuncLit)
- if !ok {
- return true
- }
- if len(fun.Body.List) == 0 {
- return true
- }
- stmt, ok := fun.Body.List[0].(*ast.ExprStmt)
- if !ok {
- return true
- }
- call, ok := stmt.X.(*ast.CallExpr)
- if !ok {
- return true
- }
- sel, ok := call.Fun.(*ast.SelectorExpr)
- if !ok {
- return true
- }
- fn, ok := j.Program.Info.ObjectOf(sel.Sel).(*types.Func)
- if !ok {
- return true
- }
- if fn.FullName() == "(*sync.WaitGroup).Add" {
- j.Errorf(sel, "should call %s before starting the goroutine to avoid a race",
- j.Render(stmt))
- }
- return true
- }
- for _, f := range j.Program.Files {
- ast.Inspect(f, fn)
- }
-}
-
-func (c *Checker) CheckInfiniteEmptyLoop(j *lint.Job) {
- fn := func(node ast.Node) bool {
- loop, ok := node.(*ast.ForStmt)
- if !ok || len(loop.Body.List) != 0 || loop.Post != nil {
- return true
- }
-
- if loop.Init != nil {
- // TODO(dh): this isn't strictly necessary, it just makes
- // the check easier.
- return true
- }
- // An empty loop is bad news in two cases: 1) The loop has no
- // condition. In that case, it's just a loop that spins
- // forever and as fast as it can, keeping a core busy. 2) The
- // loop condition only consists of variable or field reads and
- // operators on those. The only way those could change their
- // value is with unsynchronised access, which constitutes a
- // data race.
- //
- // If the condition contains any function calls, its behaviour
- // is dynamic and the loop might terminate. Similarly for
- // channel receives.
-
- if loop.Cond != nil && hasSideEffects(loop.Cond) {
- return true
- }
-
- j.Errorf(loop, "this loop will spin, using 100%% CPU")
- if loop.Cond != nil {
- j.Errorf(loop, "loop condition never changes or has a race condition")
- }
-
- return true
- }
- for _, f := range j.Program.Files {
- ast.Inspect(f, fn)
- }
-}
-
-func (c *Checker) CheckDeferInInfiniteLoop(j *lint.Job) {
- fn := func(node ast.Node) bool {
- mightExit := false
- var defers []ast.Stmt
- loop, ok := node.(*ast.ForStmt)
- if !ok || loop.Cond != nil {
- return true
- }
- fn2 := func(node ast.Node) bool {
- switch stmt := node.(type) {
- case *ast.ReturnStmt:
- mightExit = true
- case *ast.BranchStmt:
- // TODO(dominikh): if this sees a break in a switch or
- // select, it doesn't check if it breaks the loop or
- // just the select/switch. This causes some false
- // negatives.
- if stmt.Tok == token.BREAK {
- mightExit = true
- }
- case *ast.DeferStmt:
- defers = append(defers, stmt)
- case *ast.FuncLit:
- // Don't look into function bodies
- return false
- }
- return true
- }
- ast.Inspect(loop.Body, fn2)
- if mightExit {
- return true
- }
- for _, stmt := range defers {
- j.Errorf(stmt, "defers in this infinite loop will never run")
- }
- return true
- }
- for _, f := range j.Program.Files {
- ast.Inspect(f, fn)
- }
-}
-
-func (c *Checker) CheckDubiousDeferInChannelRangeLoop(j *lint.Job) {
- fn := func(node ast.Node) bool {
- loop, ok := node.(*ast.RangeStmt)
- if !ok {
- return true
- }
- typ := j.Program.Info.TypeOf(loop.X)
- _, ok = typ.Underlying().(*types.Chan)
- if !ok {
- return true
- }
- fn2 := func(node ast.Node) bool {
- switch stmt := node.(type) {
- case *ast.DeferStmt:
- j.Errorf(stmt, "defers in this range loop won't run unless the channel gets closed")
- case *ast.FuncLit:
- // Don't look into function bodies
- return false
- }
- return true
- }
- ast.Inspect(loop.Body, fn2)
- return true
- }
- for _, f := range j.Program.Files {
- ast.Inspect(f, fn)
- }
-}
-
-func (c *Checker) CheckTestMainExit(j *lint.Job) {
- fn := func(node ast.Node) bool {
- if !isTestMain(j, node) {
- return true
- }
-
- arg := j.Program.Info.ObjectOf(node.(*ast.FuncDecl).Type.Params.List[0].Names[0])
- callsRun := false
- fn2 := func(node ast.Node) bool {
- call, ok := node.(*ast.CallExpr)
- if !ok {
- return true
- }
- sel, ok := call.Fun.(*ast.SelectorExpr)
- if !ok {
- return true
- }
- ident, ok := sel.X.(*ast.Ident)
- if !ok {
- return true
- }
- if arg != j.Program.Info.ObjectOf(ident) {
- return true
- }
- if sel.Sel.Name == "Run" {
- callsRun = true
- return false
- }
- return true
- }
- ast.Inspect(node.(*ast.FuncDecl).Body, fn2)
-
- callsExit := false
- fn3 := func(node ast.Node) bool {
- if j.IsCallToAST(node, "os.Exit") {
- callsExit = true
- return false
- }
- return true
- }
- ast.Inspect(node.(*ast.FuncDecl).Body, fn3)
- if !callsExit && callsRun {
- j.Errorf(node, "TestMain should call os.Exit to set exit code")
- }
- return true
- }
- for _, f := range j.Program.Files {
- ast.Inspect(f, fn)
- }
-}
-
-func isTestMain(j *lint.Job, node ast.Node) bool {
- decl, ok := node.(*ast.FuncDecl)
- if !ok {
- return false
- }
- if decl.Name.Name != "TestMain" {
- return false
- }
- if len(decl.Type.Params.List) != 1 {
- return false
- }
- arg := decl.Type.Params.List[0]
- if len(arg.Names) != 1 {
- return false
- }
- typ := j.Program.Info.TypeOf(arg.Type)
- return typ != nil && typ.String() == "*testing.M"
-}
-
-func (c *Checker) CheckExec(j *lint.Job) {
- fn := func(node ast.Node) bool {
- call, ok := node.(*ast.CallExpr)
- if !ok {
- return true
- }
- if !j.IsCallToAST(call, "os/exec.Command") {
- return true
- }
- val, ok := j.ExprToString(call.Args[0])
- if !ok {
- return true
- }
- if !strings.Contains(val, " ") || strings.Contains(val, `\`) || strings.Contains(val, "/") {
- return true
- }
- j.Errorf(call.Args[0], "first argument to exec.Command looks like a shell command, but a program name or path are expected")
- return true
- }
- for _, f := range j.Program.Files {
- ast.Inspect(f, fn)
- }
-}
-
-func (c *Checker) CheckLoopEmptyDefault(j *lint.Job) {
- fn := func(node ast.Node) bool {
- loop, ok := node.(*ast.ForStmt)
- if !ok || len(loop.Body.List) != 1 || loop.Cond != nil || loop.Init != nil {
- return true
- }
- sel, ok := loop.Body.List[0].(*ast.SelectStmt)
- if !ok {
- return true
- }
- for _, c := range sel.Body.List {
- if comm, ok := c.(*ast.CommClause); ok && comm.Comm == nil && len(comm.Body) == 0 {
- j.Errorf(comm, "should not have an empty default case in a for+select loop. The loop will spin.")
- }
- }
- return true
- }
- for _, f := range j.Program.Files {
- ast.Inspect(f, fn)
- }
-}
-
-func (c *Checker) CheckLhsRhsIdentical(j *lint.Job) {
- fn := func(node ast.Node) bool {
- op, ok := node.(*ast.BinaryExpr)
- if !ok {
- return true
- }
- switch op.Op {
- case token.EQL, token.NEQ:
- if basic, ok := j.Program.Info.TypeOf(op.X).(*types.Basic); ok {
- if kind := basic.Kind(); kind == types.Float32 || kind == types.Float64 {
- // f == f and f != f might be used to check for NaN
- return true
- }
- }
- case token.SUB, token.QUO, token.AND, token.REM, token.OR, token.XOR, token.AND_NOT,
- token.LAND, token.LOR, token.LSS, token.GTR, token.LEQ, token.GEQ:
- default:
- // For some ops, such as + and *, it can make sense to
- // have identical operands
- return true
- }
-
- if j.Render(op.X) != j.Render(op.Y) {
- return true
- }
- j.Errorf(op, "identical expressions on the left and right side of the '%s' operator", op.Op)
- return true
- }
- for _, f := range j.Program.Files {
- ast.Inspect(f, fn)
- }
-}
-
-func (c *Checker) CheckScopedBreak(j *lint.Job) {
- fn := func(node ast.Node) bool {
- var body *ast.BlockStmt
- switch node := node.(type) {
- case *ast.ForStmt:
- body = node.Body
- case *ast.RangeStmt:
- body = node.Body
- default:
- return true
- }
- for _, stmt := range body.List {
- var blocks [][]ast.Stmt
- switch stmt := stmt.(type) {
- case *ast.SwitchStmt:
- for _, c := range stmt.Body.List {
- blocks = append(blocks, c.(*ast.CaseClause).Body)
- }
- case *ast.SelectStmt:
- for _, c := range stmt.Body.List {
- blocks = append(blocks, c.(*ast.CommClause).Body)
- }
- default:
- continue
- }
-
- for _, body := range blocks {
- if len(body) == 0 {
- continue
- }
- lasts := []ast.Stmt{body[len(body)-1]}
- // TODO(dh): unfold all levels of nested block
- // statements, not just a single level if statement
- if ifs, ok := lasts[0].(*ast.IfStmt); ok {
- if len(ifs.Body.List) == 0 {
- continue
- }
- lasts[0] = ifs.Body.List[len(ifs.Body.List)-1]
-
- if block, ok := ifs.Else.(*ast.BlockStmt); ok {
- if len(block.List) != 0 {
- lasts = append(lasts, block.List[len(block.List)-1])
- }
- }
- }
- for _, last := range lasts {
- branch, ok := last.(*ast.BranchStmt)
- if !ok || branch.Tok != token.BREAK || branch.Label != nil {
- continue
- }
- j.Errorf(branch, "ineffective break statement. Did you mean to break out of the outer loop?")
- }
- }
- }
- return true
- }
- for _, f := range j.Program.Files {
- ast.Inspect(f, fn)
- }
-}
-
-func (c *Checker) CheckUnsafePrintf(j *lint.Job) {
- fn := func(node ast.Node) bool {
- call, ok := node.(*ast.CallExpr)
- if !ok {
- return true
- }
- if !j.IsCallToAnyAST(call, "fmt.Printf", "fmt.Sprintf", "log.Printf") {
- return true
- }
- if len(call.Args) != 1 {
- return true
- }
- switch call.Args[0].(type) {
- case *ast.CallExpr, *ast.Ident:
- default:
- return true
- }
- j.Errorf(call.Args[0], "printf-style function with dynamic first argument and no further arguments should use print-style function instead")
- return true
- }
- for _, f := range j.Program.Files {
- ast.Inspect(f, fn)
- }
-}
-
-func (c *Checker) CheckEarlyDefer(j *lint.Job) {
- fn := func(node ast.Node) bool {
- block, ok := node.(*ast.BlockStmt)
- if !ok {
- return true
- }
- if len(block.List) < 2 {
- return true
- }
- for i, stmt := range block.List {
- if i == len(block.List)-1 {
- break
- }
- assign, ok := stmt.(*ast.AssignStmt)
- if !ok {
- continue
- }
- if len(assign.Rhs) != 1 {
- continue
- }
- if len(assign.Lhs) < 2 {
- continue
- }
- if lhs, ok := assign.Lhs[len(assign.Lhs)-1].(*ast.Ident); ok && lhs.Name == "_" {
- continue
- }
- call, ok := assign.Rhs[0].(*ast.CallExpr)
- if !ok {
- continue
- }
- sig, ok := j.Program.Info.TypeOf(call.Fun).(*types.Signature)
- if !ok {
- continue
- }
- if sig.Results().Len() < 2 {
- continue
- }
- last := sig.Results().At(sig.Results().Len() - 1)
- // FIXME(dh): check that it's error from universe, not
- // another type of the same name
- if last.Type().String() != "error" {
- continue
- }
- lhs, ok := assign.Lhs[0].(*ast.Ident)
- if !ok {
- continue
- }
- def, ok := block.List[i+1].(*ast.DeferStmt)
- if !ok {
- continue
- }
- sel, ok := def.Call.Fun.(*ast.SelectorExpr)
- if !ok {
- continue
- }
- ident, ok := selectorX(sel).(*ast.Ident)
- if !ok {
- continue
- }
- if ident.Obj != lhs.Obj {
- continue
- }
- if sel.Sel.Name != "Close" {
- continue
- }
- j.Errorf(def, "should check returned error before deferring %s", j.Render(def.Call))
- }
- return true
- }
- for _, f := range j.Program.Files {
- ast.Inspect(f, fn)
- }
-}
-
-func selectorX(sel *ast.SelectorExpr) ast.Node {
- switch x := sel.X.(type) {
- case *ast.SelectorExpr:
- return selectorX(x)
- default:
- return x
- }
-}
-
-func (c *Checker) CheckEmptyCriticalSection(j *lint.Job) {
- // Initially it might seem like this check would be easier to
- // implement in SSA. After all, we're only checking for two
- // consecutive method calls. In reality, however, there may be any
- // number of other instructions between the lock and unlock, while
- // still constituting an empty critical section. For example,
- // given `m.x().Lock(); m.x().Unlock()`, there will be a call to
- // x(). In the AST-based approach, this has a tiny potential for a
- // false positive (the second call to x might be doing work that
- // is protected by the mutex). In an SSA-based approach, however,
- // it would miss a lot of real bugs.
-
- mutexParams := func(s ast.Stmt) (x ast.Expr, funcName string, ok bool) {
- expr, ok := s.(*ast.ExprStmt)
- if !ok {
- return nil, "", false
- }
- call, ok := expr.X.(*ast.CallExpr)
- if !ok {
- return nil, "", false
- }
- sel, ok := call.Fun.(*ast.SelectorExpr)
- if !ok {
- return nil, "", false
- }
-
- fn, ok := j.Program.Info.ObjectOf(sel.Sel).(*types.Func)
- if !ok {
- return nil, "", false
- }
- sig := fn.Type().(*types.Signature)
- if sig.Params().Len() != 0 || sig.Results().Len() != 0 {
- return nil, "", false
- }
-
- return sel.X, fn.Name(), true
- }
-
- fn := func(node ast.Node) bool {
- block, ok := node.(*ast.BlockStmt)
- if !ok {
- return true
- }
- if len(block.List) < 2 {
- return true
- }
- for i := range block.List[:len(block.List)-1] {
- sel1, method1, ok1 := mutexParams(block.List[i])
- sel2, method2, ok2 := mutexParams(block.List[i+1])
-
- if !ok1 || !ok2 || j.Render(sel1) != j.Render(sel2) {
- continue
- }
- if (method1 == "Lock" && method2 == "Unlock") ||
- (method1 == "RLock" && method2 == "RUnlock") {
- j.Errorf(block.List[i+1], "empty critical section")
- }
- }
- return true
- }
- for _, f := range j.Program.Files {
- ast.Inspect(f, fn)
- }
-}
-
-// cgo produces code like fn(&*_Cvar_kSomeCallbacks) which we don't
-// want to flag.
-var cgoIdent = regexp.MustCompile(`^_C(func|var)_.+$`)
-
-func (c *Checker) CheckIneffectiveCopy(j *lint.Job) {
- fn := func(node ast.Node) bool {
- if unary, ok := node.(*ast.UnaryExpr); ok {
- if star, ok := unary.X.(*ast.StarExpr); ok && unary.Op == token.AND {
- ident, ok := star.X.(*ast.Ident)
- if !ok || !cgoIdent.MatchString(ident.Name) {
- j.Errorf(unary, "&*x will be simplified to x. It will not copy x.")
- }
- }
- }
-
- if star, ok := node.(*ast.StarExpr); ok {
- if unary, ok := star.X.(*ast.UnaryExpr); ok && unary.Op == token.AND {
- j.Errorf(star, "*&x will be simplified to x. It will not copy x.")
- }
- }
- return true
- }
- for _, f := range j.Program.Files {
- ast.Inspect(f, fn)
- }
-}
-
-func (c *Checker) CheckDiffSizeComparison(j *lint.Job) {
- for _, ssafn := range j.Program.InitialFunctions {
- for _, b := range ssafn.Blocks {
- for _, ins := range b.Instrs {
- binop, ok := ins.(*ssa.BinOp)
- if !ok {
- continue
- }
- if binop.Op != token.EQL && binop.Op != token.NEQ {
- continue
- }
- _, ok1 := binop.X.(*ssa.Slice)
- _, ok2 := binop.Y.(*ssa.Slice)
- if !ok1 && !ok2 {
- continue
- }
- r := c.funcDescs.Get(ssafn).Ranges
- r1, ok1 := r.Get(binop.X).(vrp.StringInterval)
- r2, ok2 := r.Get(binop.Y).(vrp.StringInterval)
- if !ok1 || !ok2 {
- continue
- }
- if r1.Length.Intersection(r2.Length).Empty() {
- j.Errorf(binop, "comparing strings of different sizes for equality will always return false")
- }
- }
- }
- }
-}
-
-func (c *Checker) CheckCanonicalHeaderKey(j *lint.Job) {
- fn := func(node ast.Node) bool {
- assign, ok := node.(*ast.AssignStmt)
- if ok {
- // TODO(dh): This risks missing some Header reads, for
- // example in `h1["foo"] = h2["foo"]` – these edge
- // cases are probably rare enough to ignore for now.
- for _, expr := range assign.Lhs {
- op, ok := expr.(*ast.IndexExpr)
- if !ok {
- continue
- }
- if hasType(j, op.X, "net/http.Header") {
- return false
- }
- }
- return true
- }
- op, ok := node.(*ast.IndexExpr)
- if !ok {
- return true
- }
- if !hasType(j, op.X, "net/http.Header") {
- return true
- }
- s, ok := j.ExprToString(op.Index)
- if !ok {
- return true
- }
- if s == http.CanonicalHeaderKey(s) {
- return true
- }
- j.Errorf(op, "keys in http.Header are canonicalized, %q is not canonical; fix the constant or use http.CanonicalHeaderKey", s)
- return true
- }
- for _, f := range j.Program.Files {
- ast.Inspect(f, fn)
- }
-}
-
-func (c *Checker) CheckBenchmarkN(j *lint.Job) {
- fn := func(node ast.Node) bool {
- assign, ok := node.(*ast.AssignStmt)
- if !ok {
- return true
- }
- if len(assign.Lhs) != 1 || len(assign.Rhs) != 1 {
- return true
- }
- sel, ok := assign.Lhs[0].(*ast.SelectorExpr)
- if !ok {
- return true
- }
- if sel.Sel.Name != "N" {
- return true
- }
- if !hasType(j, sel.X, "*testing.B") {
- return true
- }
- j.Errorf(assign, "should not assign to %s", j.Render(sel))
- return true
- }
- for _, f := range j.Program.Files {
- ast.Inspect(f, fn)
- }
-}
-
-func (c *Checker) CheckUnreadVariableValues(j *lint.Job) {
- fn := func(node ast.Node) bool {
- switch node.(type) {
- case *ast.FuncDecl, *ast.FuncLit:
- default:
- return true
- }
-
- ssafn := c.nodeFns[node]
- if ssafn == nil {
- return true
- }
- if lint.IsExample(ssafn) {
- return true
- }
- ast.Inspect(node, func(node ast.Node) bool {
- assign, ok := node.(*ast.AssignStmt)
- if !ok {
- return true
- }
- if len(assign.Lhs) > 1 && len(assign.Rhs) == 1 {
- // Either a function call with multiple return values,
- // or a comma-ok assignment
-
- val, _ := ssafn.ValueForExpr(assign.Rhs[0])
- if val == nil {
- return true
- }
- refs := val.Referrers()
- if refs == nil {
- return true
- }
- for _, ref := range *refs {
- ex, ok := ref.(*ssa.Extract)
- if !ok {
- continue
- }
- exrefs := ex.Referrers()
- if exrefs == nil {
- continue
- }
- if len(lint.FilterDebug(*exrefs)) == 0 {
- lhs := assign.Lhs[ex.Index]
- if ident, ok := lhs.(*ast.Ident); !ok || ok && ident.Name == "_" {
- continue
- }
- j.Errorf(lhs, "this value of %s is never used", lhs)
- }
- }
- return true
- }
- for i, lhs := range assign.Lhs {
- rhs := assign.Rhs[i]
- if ident, ok := lhs.(*ast.Ident); !ok || ok && ident.Name == "_" {
- continue
- }
- val, _ := ssafn.ValueForExpr(rhs)
- if val == nil {
- continue
- }
-
- refs := val.Referrers()
- if refs == nil {
- // TODO investigate why refs can be nil
- return true
- }
- if len(lint.FilterDebug(*refs)) == 0 {
- j.Errorf(lhs, "this value of %s is never used", lhs)
- }
- }
- return true
- })
- return true
- }
- for _, f := range j.Program.Files {
- ast.Inspect(f, fn)
- }
-}
-
-func (c *Checker) CheckPredeterminedBooleanExprs(j *lint.Job) {
- for _, ssafn := range j.Program.InitialFunctions {
- for _, block := range ssafn.Blocks {
- for _, ins := range block.Instrs {
- ssabinop, ok := ins.(*ssa.BinOp)
- if !ok {
- continue
- }
- switch ssabinop.Op {
- case token.GTR, token.LSS, token.EQL, token.NEQ, token.LEQ, token.GEQ:
- default:
- continue
- }
-
- xs, ok1 := consts(ssabinop.X, nil, nil)
- ys, ok2 := consts(ssabinop.Y, nil, nil)
- if !ok1 || !ok2 || len(xs) == 0 || len(ys) == 0 {
- continue
- }
-
- trues := 0
- for _, x := range xs {
- for _, y := range ys {
- if x.Value == nil {
- if y.Value == nil {
- trues++
- }
- continue
- }
- if constant.Compare(x.Value, ssabinop.Op, y.Value) {
- trues++
- }
- }
- }
- b := trues != 0
- if trues == 0 || trues == len(xs)*len(ys) {
- j.Errorf(ssabinop, "binary expression is always %t for all possible values (%s %s %s)",
- b, xs, ssabinop.Op, ys)
- }
- }
- }
- }
-}
-
-func (c *Checker) CheckNilMaps(j *lint.Job) {
- for _, ssafn := range j.Program.InitialFunctions {
- for _, block := range ssafn.Blocks {
- for _, ins := range block.Instrs {
- mu, ok := ins.(*ssa.MapUpdate)
- if !ok {
- continue
- }
- c, ok := mu.Map.(*ssa.Const)
- if !ok {
- continue
- }
- if c.Value != nil {
- continue
- }
- j.Errorf(mu, "assignment to nil map")
- }
- }
- }
-}
-
-func (c *Checker) CheckUnsignedComparison(j *lint.Job) {
- fn := func(node ast.Node) bool {
- expr, ok := node.(*ast.BinaryExpr)
- if !ok {
- return true
- }
- tx := j.Program.Info.TypeOf(expr.X)
- basic, ok := tx.Underlying().(*types.Basic)
- if !ok {
- return true
- }
- if (basic.Info() & types.IsUnsigned) == 0 {
- return true
- }
- lit, ok := expr.Y.(*ast.BasicLit)
- if !ok || lit.Value != "0" {
- return true
- }
- switch expr.Op {
- case token.GEQ:
- j.Errorf(expr, "unsigned values are always >= 0")
- case token.LSS:
- j.Errorf(expr, "unsigned values are never < 0")
- }
- return true
- }
- for _, f := range j.Program.Files {
- ast.Inspect(f, fn)
- }
-}
-
-func consts(val ssa.Value, out []*ssa.Const, visitedPhis map[string]bool) ([]*ssa.Const, bool) {
- if visitedPhis == nil {
- visitedPhis = map[string]bool{}
- }
- var ok bool
- switch val := val.(type) {
- case *ssa.Phi:
- if visitedPhis[val.Name()] {
- break
- }
- visitedPhis[val.Name()] = true
- vals := val.Operands(nil)
- for _, phival := range vals {
- out, ok = consts(*phival, out, visitedPhis)
- if !ok {
- return nil, false
- }
- }
- case *ssa.Const:
- out = append(out, val)
- case *ssa.Convert:
- out, ok = consts(val.X, out, visitedPhis)
- if !ok {
- return nil, false
- }
- default:
- return nil, false
- }
- if len(out) < 2 {
- return out, true
- }
- uniq := []*ssa.Const{out[0]}
- for _, val := range out[1:] {
- if val.Value == uniq[len(uniq)-1].Value {
- continue
- }
- uniq = append(uniq, val)
- }
- return uniq, true
-}
-
-func (c *Checker) CheckLoopCondition(j *lint.Job) {
- fn := func(node ast.Node) bool {
- loop, ok := node.(*ast.ForStmt)
- if !ok {
- return true
- }
- if loop.Init == nil || loop.Cond == nil || loop.Post == nil {
- return true
- }
- init, ok := loop.Init.(*ast.AssignStmt)
- if !ok || len(init.Lhs) != 1 || len(init.Rhs) != 1 {
- return true
- }
- cond, ok := loop.Cond.(*ast.BinaryExpr)
- if !ok {
- return true
- }
- x, ok := cond.X.(*ast.Ident)
- if !ok {
- return true
- }
- lhs, ok := init.Lhs[0].(*ast.Ident)
- if !ok {
- return true
- }
- if x.Obj != lhs.Obj {
- return true
- }
- if _, ok := loop.Post.(*ast.IncDecStmt); !ok {
- return true
- }
-
- ssafn := c.nodeFns[cond]
- if ssafn == nil {
- return true
- }
- v, isAddr := ssafn.ValueForExpr(cond.X)
- if v == nil || isAddr {
- return true
- }
- switch v := v.(type) {
- case *ssa.Phi:
- ops := v.Operands(nil)
- if len(ops) != 2 {
- return true
- }
- _, ok := (*ops[0]).(*ssa.Const)
- if !ok {
- return true
- }
- sigma, ok := (*ops[1]).(*ssa.Sigma)
- if !ok {
- return true
- }
- if sigma.X != v {
- return true
- }
- case *ssa.UnOp:
- return true
- }
- j.Errorf(cond, "variable in loop condition never changes")
-
- return true
- }
- for _, f := range j.Program.Files {
- ast.Inspect(f, fn)
- }
-}
-
-func (c *Checker) CheckArgOverwritten(j *lint.Job) {
- fn := func(node ast.Node) bool {
- var typ *ast.FuncType
- var body *ast.BlockStmt
- switch fn := node.(type) {
- case *ast.FuncDecl:
- typ = fn.Type
- body = fn.Body
- case *ast.FuncLit:
- typ = fn.Type
- body = fn.Body
- }
- if body == nil {
- return true
- }
- ssafn := c.nodeFns[node]
- if ssafn == nil {
- return true
- }
- if len(typ.Params.List) == 0 {
- return true
- }
- for _, field := range typ.Params.List {
- for _, arg := range field.Names {
- obj := j.Program.Info.ObjectOf(arg)
- var ssaobj *ssa.Parameter
- for _, param := range ssafn.Params {
- if param.Object() == obj {
- ssaobj = param
- break
- }
- }
- if ssaobj == nil {
- continue
- }
- refs := ssaobj.Referrers()
- if refs == nil {
- continue
- }
- if len(lint.FilterDebug(*refs)) != 0 {
- continue
- }
-
- assigned := false
- ast.Inspect(body, func(node ast.Node) bool {
- assign, ok := node.(*ast.AssignStmt)
- if !ok {
- return true
- }
- for _, lhs := range assign.Lhs {
- ident, ok := lhs.(*ast.Ident)
- if !ok {
- continue
- }
- if j.Program.Info.ObjectOf(ident) == obj {
- assigned = true
- return false
- }
- }
- return true
- })
- if assigned {
- j.Errorf(arg, "argument %s is overwritten before first use", arg)
- }
- }
- }
- return true
- }
- for _, f := range j.Program.Files {
- ast.Inspect(f, fn)
- }
-}
-
-func (c *Checker) CheckIneffectiveLoop(j *lint.Job) {
- // This check detects some, but not all unconditional loop exits.
- // We give up in the following cases:
- //
- // - a goto anywhere in the loop. The goto might skip over our
- // return, and we don't check that it doesn't.
- //
- // - any nested, unlabelled continue, even if it is in another
- // loop or closure.
- fn := func(node ast.Node) bool {
- var body *ast.BlockStmt
- switch fn := node.(type) {
- case *ast.FuncDecl:
- body = fn.Body
- case *ast.FuncLit:
- body = fn.Body
- default:
- return true
- }
- if body == nil {
- return true
- }
- labels := map[*ast.Object]ast.Stmt{}
- ast.Inspect(body, func(node ast.Node) bool {
- label, ok := node.(*ast.LabeledStmt)
- if !ok {
- return true
- }
- labels[label.Label.Obj] = label.Stmt
- return true
- })
-
- ast.Inspect(body, func(node ast.Node) bool {
- var loop ast.Node
- var body *ast.BlockStmt
- switch node := node.(type) {
- case *ast.ForStmt:
- body = node.Body
- loop = node
- case *ast.RangeStmt:
- typ := j.Program.Info.TypeOf(node.X)
- if _, ok := typ.Underlying().(*types.Map); ok {
- // looping once over a map is a valid pattern for
- // getting an arbitrary element.
- return true
- }
- body = node.Body
- loop = node
- default:
- return true
- }
- if len(body.List) < 2 {
- // avoid flagging the somewhat common pattern of using
- // a range loop to get the first element in a slice,
- // or the first rune in a string.
- return true
- }
- var unconditionalExit ast.Node
- hasBranching := false
- for _, stmt := range body.List {
- switch stmt := stmt.(type) {
- case *ast.BranchStmt:
- switch stmt.Tok {
- case token.BREAK:
- if stmt.Label == nil || labels[stmt.Label.Obj] == loop {
- unconditionalExit = stmt
- }
- case token.CONTINUE:
- if stmt.Label == nil || labels[stmt.Label.Obj] == loop {
- unconditionalExit = nil
- return false
- }
- }
- case *ast.ReturnStmt:
- unconditionalExit = stmt
- case *ast.IfStmt, *ast.ForStmt, *ast.RangeStmt, *ast.SwitchStmt, *ast.SelectStmt:
- hasBranching = true
- }
- }
- if unconditionalExit == nil || !hasBranching {
- return false
- }
- ast.Inspect(body, func(node ast.Node) bool {
- if branch, ok := node.(*ast.BranchStmt); ok {
-
- switch branch.Tok {
- case token.GOTO:
- unconditionalExit = nil
- return false
- case token.CONTINUE:
- if branch.Label != nil && labels[branch.Label.Obj] != loop {
- return true
- }
- unconditionalExit = nil
- return false
- }
- }
- return true
- })
- if unconditionalExit != nil {
- j.Errorf(unconditionalExit, "the surrounding loop is unconditionally terminated")
- }
- return true
- })
- return true
- }
- for _, f := range j.Program.Files {
- ast.Inspect(f, fn)
- }
-}
-
-func (c *Checker) CheckNilContext(j *lint.Job) {
- fn := func(node ast.Node) bool {
- call, ok := node.(*ast.CallExpr)
- if !ok {
- return true
- }
- if len(call.Args) == 0 {
- return true
- }
- if typ, ok := j.Program.Info.TypeOf(call.Args[0]).(*types.Basic); !ok || typ.Kind() != types.UntypedNil {
- return true
- }
- sig, ok := j.Program.Info.TypeOf(call.Fun).(*types.Signature)
- if !ok {
- return true
- }
- if sig.Params().Len() == 0 {
- return true
- }
- if types.TypeString(sig.Params().At(0).Type(), nil) != "context.Context" {
- return true
- }
- j.Errorf(call.Args[0],
- "do not pass a nil Context, even if a function permits it; pass context.TODO if you are unsure about which Context to use")
- return true
- }
- for _, f := range j.Program.Files {
- ast.Inspect(f, fn)
- }
-}
-
-func (c *Checker) CheckSeeker(j *lint.Job) {
- fn := func(node ast.Node) bool {
- call, ok := node.(*ast.CallExpr)
- if !ok {
- return true
- }
- sel, ok := call.Fun.(*ast.SelectorExpr)
- if !ok {
- return true
- }
- if sel.Sel.Name != "Seek" {
- return true
- }
- if len(call.Args) != 2 {
- return true
- }
- arg0, ok := call.Args[0].(*ast.SelectorExpr)
- if !ok {
- return true
- }
- switch arg0.Sel.Name {
- case "SeekStart", "SeekCurrent", "SeekEnd":
- default:
- return true
- }
- pkg, ok := arg0.X.(*ast.Ident)
- if !ok {
- return true
- }
- if pkg.Name != "io" {
- return true
- }
- j.Errorf(call, "the first argument of io.Seeker is the offset, but an io.Seek* constant is being used instead")
- return true
- }
- for _, f := range j.Program.Files {
- ast.Inspect(f, fn)
- }
-}
-
-func (c *Checker) CheckIneffectiveAppend(j *lint.Job) {
- isAppend := func(ins ssa.Value) bool {
- call, ok := ins.(*ssa.Call)
- if !ok {
- return false
- }
- if call.Call.IsInvoke() {
- return false
- }
- if builtin, ok := call.Call.Value.(*ssa.Builtin); !ok || builtin.Name() != "append" {
- return false
- }
- return true
- }
-
- for _, ssafn := range j.Program.InitialFunctions {
- for _, block := range ssafn.Blocks {
- for _, ins := range block.Instrs {
- val, ok := ins.(ssa.Value)
- if !ok || !isAppend(val) {
- continue
- }
-
- isUsed := false
- visited := map[ssa.Instruction]bool{}
- var walkRefs func(refs []ssa.Instruction)
- walkRefs = func(refs []ssa.Instruction) {
- loop:
- for _, ref := range refs {
- if visited[ref] {
- continue
- }
- visited[ref] = true
- if _, ok := ref.(*ssa.DebugRef); ok {
- continue
- }
- switch ref := ref.(type) {
- case *ssa.Phi:
- walkRefs(*ref.Referrers())
- case *ssa.Sigma:
- walkRefs(*ref.Referrers())
- case ssa.Value:
- if !isAppend(ref) {
- isUsed = true
- } else {
- walkRefs(*ref.Referrers())
- }
- case ssa.Instruction:
- isUsed = true
- break loop
- }
- }
- }
- refs := val.Referrers()
- if refs == nil {
- continue
- }
- walkRefs(*refs)
- if !isUsed {
- j.Errorf(ins, "this result of append is never used, except maybe in other appends")
- }
- }
- }
- }
-}
-
-func (c *Checker) CheckConcurrentTesting(j *lint.Job) {
- for _, ssafn := range j.Program.InitialFunctions {
- for _, block := range ssafn.Blocks {
- for _, ins := range block.Instrs {
- gostmt, ok := ins.(*ssa.Go)
- if !ok {
- continue
- }
- var fn *ssa.Function
- switch val := gostmt.Call.Value.(type) {
- case *ssa.Function:
- fn = val
- case *ssa.MakeClosure:
- fn = val.Fn.(*ssa.Function)
- default:
- continue
- }
- if fn.Blocks == nil {
- continue
- }
- for _, block := range fn.Blocks {
- for _, ins := range block.Instrs {
- call, ok := ins.(*ssa.Call)
- if !ok {
- continue
- }
- if call.Call.IsInvoke() {
- continue
- }
- callee := call.Call.StaticCallee()
- if callee == nil {
- continue
- }
- recv := callee.Signature.Recv()
- if recv == nil {
- continue
- }
- if types.TypeString(recv.Type(), nil) != "*testing.common" {
- continue
- }
- fn, ok := call.Call.StaticCallee().Object().(*types.Func)
- if !ok {
- continue
- }
- name := fn.Name()
- switch name {
- case "FailNow", "Fatal", "Fatalf", "SkipNow", "Skip", "Skipf":
- default:
- continue
- }
- j.Errorf(gostmt, "the goroutine calls T.%s, which must be called in the same goroutine as the test", name)
- }
- }
- }
- }
- }
-}
-
-func (c *Checker) CheckCyclicFinalizer(j *lint.Job) {
- for _, ssafn := range j.Program.InitialFunctions {
- node := c.funcDescs.CallGraph.CreateNode(ssafn)
- for _, edge := range node.Out {
- if edge.Callee.Func.RelString(nil) != "runtime.SetFinalizer" {
- continue
- }
- arg0 := edge.Site.Common().Args[0]
- if iface, ok := arg0.(*ssa.MakeInterface); ok {
- arg0 = iface.X
- }
- unop, ok := arg0.(*ssa.UnOp)
- if !ok {
- continue
- }
- v, ok := unop.X.(*ssa.Alloc)
- if !ok {
- continue
- }
- arg1 := edge.Site.Common().Args[1]
- if iface, ok := arg1.(*ssa.MakeInterface); ok {
- arg1 = iface.X
- }
- mc, ok := arg1.(*ssa.MakeClosure)
- if !ok {
- continue
- }
- for _, b := range mc.Bindings {
- if b == v {
- pos := j.Program.DisplayPosition(mc.Fn.Pos())
- j.Errorf(edge.Site, "the finalizer closes over the object, preventing the finalizer from ever running (at %s)", pos)
- }
- }
- }
- }
-}
-
-func (c *Checker) CheckSliceOutOfBounds(j *lint.Job) {
- for _, ssafn := range j.Program.InitialFunctions {
- for _, block := range ssafn.Blocks {
- for _, ins := range block.Instrs {
- ia, ok := ins.(*ssa.IndexAddr)
- if !ok {
- continue
- }
- if _, ok := ia.X.Type().Underlying().(*types.Slice); !ok {
- continue
- }
- sr, ok1 := c.funcDescs.Get(ssafn).Ranges[ia.X].(vrp.SliceInterval)
- idxr, ok2 := c.funcDescs.Get(ssafn).Ranges[ia.Index].(vrp.IntInterval)
- if !ok1 || !ok2 || !sr.IsKnown() || !idxr.IsKnown() || sr.Length.Empty() || idxr.Empty() {
- continue
- }
- if idxr.Lower.Cmp(sr.Length.Upper) >= 0 {
- j.Errorf(ia, "index out of bounds")
- }
- }
- }
- }
-}
-
-func (c *Checker) CheckDeferLock(j *lint.Job) {
- for _, ssafn := range j.Program.InitialFunctions {
- for _, block := range ssafn.Blocks {
- instrs := lint.FilterDebug(block.Instrs)
- if len(instrs) < 2 {
- continue
- }
- for i, ins := range instrs[:len(instrs)-1] {
- call, ok := ins.(*ssa.Call)
- if !ok {
- continue
- }
- if !lint.IsCallTo(call.Common(), "(*sync.Mutex).Lock") && !lint.IsCallTo(call.Common(), "(*sync.RWMutex).RLock") {
- continue
- }
- nins, ok := instrs[i+1].(*ssa.Defer)
- if !ok {
- continue
- }
- if !lint.IsCallTo(&nins.Call, "(*sync.Mutex).Lock") && !lint.IsCallTo(&nins.Call, "(*sync.RWMutex).RLock") {
- continue
- }
- if call.Common().Args[0] != nins.Call.Args[0] {
- continue
- }
- name := shortCallName(call.Common())
- alt := ""
- switch name {
- case "Lock":
- alt = "Unlock"
- case "RLock":
- alt = "RUnlock"
- }
- j.Errorf(nins, "deferring %s right after having locked already; did you mean to defer %s?", name, alt)
- }
- }
- }
-}
-
-func (c *Checker) CheckNaNComparison(j *lint.Job) {
- isNaN := func(v ssa.Value) bool {
- call, ok := v.(*ssa.Call)
- if !ok {
- return false
- }
- return lint.IsCallTo(call.Common(), "math.NaN")
- }
- for _, ssafn := range j.Program.InitialFunctions {
- for _, block := range ssafn.Blocks {
- for _, ins := range block.Instrs {
- ins, ok := ins.(*ssa.BinOp)
- if !ok {
- continue
- }
- if isNaN(ins.X) || isNaN(ins.Y) {
- j.Errorf(ins, "no value is equal to NaN, not even NaN itself")
- }
- }
- }
- }
-}
-
-func (c *Checker) CheckInfiniteRecursion(j *lint.Job) {
- for _, ssafn := range j.Program.InitialFunctions {
- node := c.funcDescs.CallGraph.CreateNode(ssafn)
- for _, edge := range node.Out {
- if edge.Callee != node {
- continue
- }
- if _, ok := edge.Site.(*ssa.Go); ok {
- // Recursively spawning goroutines doesn't consume
- // stack space infinitely, so don't flag it.
- continue
- }
-
- block := edge.Site.Block()
- canReturn := false
- for _, b := range ssafn.Blocks {
- if block.Dominates(b) {
- continue
- }
- if len(b.Instrs) == 0 {
- continue
- }
- if _, ok := b.Instrs[len(b.Instrs)-1].(*ssa.Return); ok {
- canReturn = true
- break
- }
- }
- if canReturn {
- continue
- }
- j.Errorf(edge.Site, "infinite recursive call")
- }
- }
-}
-
-func objectName(obj types.Object) string {
- if obj == nil {
- return "<nil>"
- }
- var name string
- if obj.Pkg() != nil && obj.Pkg().Scope().Lookup(obj.Name()) == obj {
- var s string
- s = obj.Pkg().Path()
- if s != "" {
- name += s + "."
- }
- }
- name += obj.Name()
- return name
-}
-
-func isName(j *lint.Job, expr ast.Expr, name string) bool {
- var obj types.Object
- switch expr := expr.(type) {
- case *ast.Ident:
- obj = j.Program.Info.ObjectOf(expr)
- case *ast.SelectorExpr:
- obj = j.Program.Info.ObjectOf(expr.Sel)
- }
- return objectName(obj) == name
-}
-
-func (c *Checker) CheckLeakyTimeTick(j *lint.Job) {
- for _, ssafn := range j.Program.InitialFunctions {
- if j.IsInMain(ssafn) || j.IsInTest(ssafn) {
- continue
- }
- for _, block := range ssafn.Blocks {
- for _, ins := range block.Instrs {
- call, ok := ins.(*ssa.Call)
- if !ok || !lint.IsCallTo(call.Common(), "time.Tick") {
- continue
- }
- if c.funcDescs.Get(call.Parent()).Infinite {
- continue
- }
- j.Errorf(call, "using time.Tick leaks the underlying ticker, consider using it only in endless functions, tests and the main package, and use time.NewTicker here")
- }
- }
- }
-}
-
-func (c *Checker) CheckDoubleNegation(j *lint.Job) {
- fn := func(node ast.Node) bool {
- unary1, ok := node.(*ast.UnaryExpr)
- if !ok {
- return true
- }
- unary2, ok := unary1.X.(*ast.UnaryExpr)
- if !ok {
- return true
- }
- if unary1.Op != token.NOT || unary2.Op != token.NOT {
- return true
- }
- j.Errorf(unary1, "negating a boolean twice has no effect; is this a typo?")
- return true
- }
- for _, f := range j.Program.Files {
- ast.Inspect(f, fn)
- }
-}
-
-func hasSideEffects(node ast.Node) bool {
- dynamic := false
- ast.Inspect(node, func(node ast.Node) bool {
- switch node := node.(type) {
- case *ast.CallExpr:
- dynamic = true
- return false
- case *ast.UnaryExpr:
- if node.Op == token.ARROW {
- dynamic = true
- return false
- }
- }
- return true
- })
- return dynamic
-}
-
-func (c *Checker) CheckRepeatedIfElse(j *lint.Job) {
- seen := map[ast.Node]bool{}
-
- var collectConds func(ifstmt *ast.IfStmt, inits []ast.Stmt, conds []ast.Expr) ([]ast.Stmt, []ast.Expr)
- collectConds = func(ifstmt *ast.IfStmt, inits []ast.Stmt, conds []ast.Expr) ([]ast.Stmt, []ast.Expr) {
- seen[ifstmt] = true
- if ifstmt.Init != nil {
- inits = append(inits, ifstmt.Init)
- }
- conds = append(conds, ifstmt.Cond)
- if elsestmt, ok := ifstmt.Else.(*ast.IfStmt); ok {
- return collectConds(elsestmt, inits, conds)
- }
- return inits, conds
- }
- fn := func(node ast.Node) bool {
- ifstmt, ok := node.(*ast.IfStmt)
- if !ok {
- return true
- }
- if seen[ifstmt] {
- return true
- }
- inits, conds := collectConds(ifstmt, nil, nil)
- if len(inits) > 0 {
- return true
- }
- for _, cond := range conds {
- if hasSideEffects(cond) {
- return true
- }
- }
- counts := map[string]int{}
- for _, cond := range conds {
- s := j.Render(cond)
- counts[s]++
- if counts[s] == 2 {
- j.Errorf(cond, "this condition occurs multiple times in this if/else if chain")
- }
- }
- return true
- }
- for _, f := range j.Program.Files {
- ast.Inspect(f, fn)
- }
-}
-
-func (c *Checker) CheckSillyBitwiseOps(j *lint.Job) {
- for _, ssafn := range j.Program.InitialFunctions {
- for _, block := range ssafn.Blocks {
- for _, ins := range block.Instrs {
- ins, ok := ins.(*ssa.BinOp)
- if !ok {
- continue
- }
-
- if c, ok := ins.Y.(*ssa.Const); !ok || c.Value == nil || c.Value.Kind() != constant.Int || c.Uint64() != 0 {
- continue
- }
- switch ins.Op {
- case token.AND, token.OR, token.XOR:
- default:
- // we do not flag shifts because too often, x<<0 is part
- // of a pattern, x<<0, x<<8, x<<16, ...
- continue
- }
- path, _ := astutil.PathEnclosingInterval(j.File(ins), ins.Pos(), ins.Pos())
- if len(path) == 0 {
- continue
- }
- if node, ok := path[0].(*ast.BinaryExpr); !ok || !lint.IsZero(node.Y) {
- continue
- }
-
- switch ins.Op {
- case token.AND:
- j.Errorf(ins, "x & 0 always equals 0")
- case token.OR, token.XOR:
- j.Errorf(ins, "x %s 0 always equals x", ins.Op)
- }
- }
- }
- }
-}
-
-func (c *Checker) CheckNonOctalFileMode(j *lint.Job) {
- fn := func(node ast.Node) bool {
- call, ok := node.(*ast.CallExpr)
- if !ok {
- return true
- }
- sig, ok := j.Program.Info.TypeOf(call.Fun).(*types.Signature)
- if !ok {
- return true
- }
- n := sig.Params().Len()
- var args []int
- for i := 0; i < n; i++ {
- typ := sig.Params().At(i).Type()
- if types.TypeString(typ, nil) == "os.FileMode" {
- args = append(args, i)
- }
- }
- for _, i := range args {
- lit, ok := call.Args[i].(*ast.BasicLit)
- if !ok {
- continue
- }
- if len(lit.Value) == 3 &&
- lit.Value[0] != '0' &&
- lit.Value[0] >= '0' && lit.Value[0] <= '7' &&
- lit.Value[1] >= '0' && lit.Value[1] <= '7' &&
- lit.Value[2] >= '0' && lit.Value[2] <= '7' {
-
- v, err := strconv.ParseInt(lit.Value, 10, 64)
- if err != nil {
- continue
- }
- j.Errorf(call.Args[i], "file mode '%s' evaluates to %#o; did you mean '0%s'?", lit.Value, v, lit.Value)
- }
- }
- return true
- }
- for _, f := range j.Program.Files {
- ast.Inspect(f, fn)
- }
-}
-
-func (c *Checker) CheckPureFunctions(j *lint.Job) {
-fnLoop:
- for _, ssafn := range j.Program.InitialFunctions {
- if j.IsInTest(ssafn) {
- params := ssafn.Signature.Params()
- for i := 0; i < params.Len(); i++ {
- param := params.At(i)
- if types.TypeString(param.Type(), nil) == "*testing.B" {
- // Ignore discarded pure functions in code related
- // to benchmarks. Instead of matching BenchmarkFoo
- // functions, we match any function accepting a
- // *testing.B. Benchmarks sometimes call generic
- // functions for doing the actual work, and
- // checking for the parameter is a lot easier and
- // faster than analyzing call trees.
- continue fnLoop
- }
- }
- }
-
- for _, b := range ssafn.Blocks {
- for _, ins := range b.Instrs {
- ins, ok := ins.(*ssa.Call)
- if !ok {
- continue
- }
- refs := ins.Referrers()
- if refs == nil || len(lint.FilterDebug(*refs)) > 0 {
- continue
- }
- callee := ins.Common().StaticCallee()
- if callee == nil {
- continue
- }
- if c.funcDescs.Get(callee).Pure && !c.funcDescs.Get(callee).Stub {
- j.Errorf(ins, "%s is a pure function but its return value is ignored", callee.Name())
- continue
- }
- }
- }
- }
-}
-
-func (c *Checker) isDeprecated(j *lint.Job, ident *ast.Ident) (bool, string) {
- obj := j.Program.Info.ObjectOf(ident)
- if obj.Pkg() == nil {
- return false, ""
- }
- alt := c.deprecatedObjs[obj]
- return alt != "", alt
-}
-
-func selectorName(j *lint.Job, expr *ast.SelectorExpr) string {
- sel := j.Program.Info.Selections[expr]
- if sel == nil {
- if x, ok := expr.X.(*ast.Ident); ok {
- pkg, ok := j.Program.Info.ObjectOf(x).(*types.PkgName)
- if !ok {
- // This shouldn't happen
- return fmt.Sprintf("%s.%s", x.Name, expr.Sel.Name)
- }
- return fmt.Sprintf("%s.%s", pkg.Imported().Path(), expr.Sel.Name)
- }
- panic(fmt.Sprintf("unsupported selector: %v", expr))
- }
- return fmt.Sprintf("(%s).%s", sel.Recv(), sel.Obj().Name())
-}
-
-func (c *Checker) enclosingFunc(sel *ast.SelectorExpr) *ssa.Function {
- fn := c.nodeFns[sel]
- if fn == nil {
- return nil
- }
- for fn.Parent() != nil {
- fn = fn.Parent()
- }
- return fn
-}
-
-func (c *Checker) CheckDeprecated(j *lint.Job) {
- fn := func(node ast.Node) bool {
- sel, ok := node.(*ast.SelectorExpr)
- if !ok {
- return true
- }
-
- obj := j.Program.Info.ObjectOf(sel.Sel)
- if obj.Pkg() == nil {
- return true
- }
- nodePkg := j.NodePackage(node).Pkg
- if nodePkg == obj.Pkg() || obj.Pkg().Path()+"_test" == nodePkg.Path() {
- // Don't flag stuff in our own package
- return true
- }
- if ok, alt := c.isDeprecated(j, sel.Sel); ok {
- // Look for the first available alternative, not the first
- // version something was deprecated in. If a function was
- // deprecated in Go 1.6, an alternative has been available
- // already in 1.0, and we're targetting 1.2, it still
- // makes sense to use the alternative from 1.0, to be
- // future-proof.
- minVersion := deprecated.Stdlib[selectorName(j, sel)].AlternativeAvailableSince
- if !j.IsGoVersion(minVersion) {
- return true
- }
-
- if fn := c.enclosingFunc(sel); fn != nil {
- if _, ok := c.deprecatedObjs[fn.Object()]; ok {
- // functions that are deprecated may use deprecated
- // symbols
- return true
- }
- }
- j.Errorf(sel, "%s is deprecated: %s", j.Render(sel), alt)
- return true
- }
- return true
- }
- for _, f := range j.Program.Files {
- ast.Inspect(f, fn)
- }
-}
-
-func (c *Checker) callChecker(rules map[string]CallCheck) func(j *lint.Job) {
- return func(j *lint.Job) {
- c.checkCalls(j, rules)
- }
-}
-
-func (c *Checker) checkCalls(j *lint.Job, rules map[string]CallCheck) {
- for _, ssafn := range j.Program.InitialFunctions {
- node := c.funcDescs.CallGraph.CreateNode(ssafn)
- for _, edge := range node.Out {
- callee := edge.Callee.Func
- obj, ok := callee.Object().(*types.Func)
- if !ok {
- continue
- }
-
- r, ok := rules[obj.FullName()]
- if !ok {
- continue
- }
- var args []*Argument
- ssaargs := edge.Site.Common().Args
- if callee.Signature.Recv() != nil {
- ssaargs = ssaargs[1:]
- }
- for _, arg := range ssaargs {
- if iarg, ok := arg.(*ssa.MakeInterface); ok {
- arg = iarg.X
- }
- vr := c.funcDescs.Get(edge.Site.Parent()).Ranges[arg]
- args = append(args, &Argument{Value: Value{arg, vr}})
- }
- call := &Call{
- Job: j,
- Instr: edge.Site,
- Args: args,
- Checker: c,
- Parent: edge.Site.Parent(),
- }
- r(call)
- for idx, arg := range call.Args {
- _ = idx
- for _, e := range arg.invalids {
- // path, _ := astutil.PathEnclosingInterval(f.File, edge.Site.Pos(), edge.Site.Pos())
- // if len(path) < 2 {
- // continue
- // }
- // astcall, ok := path[0].(*ast.CallExpr)
- // if !ok {
- // continue
- // }
- // j.Errorf(astcall.Args[idx], "%s", e)
-
- j.Errorf(edge.Site, "%s", e)
- }
- }
- for _, e := range call.invalids {
- j.Errorf(call.Instr.Common(), "%s", e)
- }
- }
- }
-}
-
-func unwrapFunction(val ssa.Value) *ssa.Function {
- switch val := val.(type) {
- case *ssa.Function:
- return val
- case *ssa.MakeClosure:
- return val.Fn.(*ssa.Function)
- default:
- return nil
- }
-}
-
-func shortCallName(call *ssa.CallCommon) string {
- if call.IsInvoke() {
- return ""
- }
- switch v := call.Value.(type) {
- case *ssa.Function:
- fn, ok := v.Object().(*types.Func)
- if !ok {
- return ""
- }
- return fn.Name()
- case *ssa.Builtin:
- return v.Name()
- }
- return ""
-}
-
-func hasCallTo(block *ssa.BasicBlock, name string) bool {
- for _, ins := range block.Instrs {
- call, ok := ins.(*ssa.Call)
- if !ok {
- continue
- }
- if lint.IsCallTo(call.Common(), name) {
- return true
- }
- }
- return false
-}
-
-// deref returns a pointer's element type; otherwise it returns typ.
-func deref(typ types.Type) types.Type {
- if p, ok := typ.Underlying().(*types.Pointer); ok {
- return p.Elem()
- }
- return typ
-}
-
-func (c *Checker) CheckWriterBufferModified(j *lint.Job) {
- // TODO(dh): this might be a good candidate for taint analysis.
- // Taint the argument as MUST_NOT_MODIFY, then propagate that
- // through functions like bytes.Split
-
- for _, ssafn := range j.Program.InitialFunctions {
- sig := ssafn.Signature
- if ssafn.Name() != "Write" || sig.Recv() == nil || sig.Params().Len() != 1 || sig.Results().Len() != 2 {
- continue
- }
- tArg, ok := sig.Params().At(0).Type().(*types.Slice)
- if !ok {
- continue
- }
- if basic, ok := tArg.Elem().(*types.Basic); !ok || basic.Kind() != types.Byte {
- continue
- }
- if basic, ok := sig.Results().At(0).Type().(*types.Basic); !ok || basic.Kind() != types.Int {
- continue
- }
- if named, ok := sig.Results().At(1).Type().(*types.Named); !ok || types.TypeString(named, nil) != "error" {
- continue
- }
-
- for _, block := range ssafn.Blocks {
- for _, ins := range block.Instrs {
- switch ins := ins.(type) {
- case *ssa.Store:
- addr, ok := ins.Addr.(*ssa.IndexAddr)
- if !ok {
- continue
- }
- if addr.X != ssafn.Params[1] {
- continue
- }
- j.Errorf(ins, "io.Writer.Write must not modify the provided buffer, not even temporarily")
- case *ssa.Call:
- if !lint.IsCallTo(ins.Common(), "append") {
- continue
- }
- if ins.Common().Args[0] != ssafn.Params[1] {
- continue
- }
- j.Errorf(ins, "io.Writer.Write must not modify the provided buffer, not even temporarily")
- }
- }
- }
- }
-}
-
-func loopedRegexp(name string) CallCheck {
- return func(call *Call) {
- if len(extractConsts(call.Args[0].Value.Value)) == 0 {
- return
- }
- if !call.Checker.isInLoop(call.Instr.Block()) {
- return
- }
- call.Invalid(fmt.Sprintf("calling %s in a loop has poor performance, consider using regexp.Compile", name))
- }
-}
-
-func (c *Checker) CheckEmptyBranch(j *lint.Job) {
- fn := func(node ast.Node) bool {
- ifstmt, ok := node.(*ast.IfStmt)
- if !ok {
- return true
- }
- ssafn := c.nodeFns[node]
- if lint.IsExample(ssafn) {
- return true
- }
- if ifstmt.Else != nil {
- b, ok := ifstmt.Else.(*ast.BlockStmt)
- if !ok || len(b.List) != 0 {
- return true
- }
- j.Errorf(ifstmt.Else, "empty branch")
- }
- if len(ifstmt.Body.List) != 0 {
- return true
- }
- j.Errorf(ifstmt, "empty branch")
- return true
- }
- for _, f := range c.filterGenerated(j.Program.Files) {
- ast.Inspect(f, fn)
- }
-}
-
-func (c *Checker) CheckMapBytesKey(j *lint.Job) {
- for _, fn := range j.Program.InitialFunctions {
- for _, b := range fn.Blocks {
- insLoop:
- for _, ins := range b.Instrs {
- // find []byte -> string conversions
- conv, ok := ins.(*ssa.Convert)
- if !ok || conv.Type() != types.Universe.Lookup("string").Type() {
- continue
- }
- if s, ok := conv.X.Type().(*types.Slice); !ok || s.Elem() != types.Universe.Lookup("byte").Type() {
- continue
- }
- refs := conv.Referrers()
- // need at least two (DebugRef) references: the
- // conversion and the *ast.Ident
- if refs == nil || len(*refs) < 2 {
- continue
- }
- ident := false
- // skip first reference, that's the conversion itself
- for _, ref := range (*refs)[1:] {
- switch ref := ref.(type) {
- case *ssa.DebugRef:
- if _, ok := ref.Expr.(*ast.Ident); !ok {
- // the string seems to be used somewhere
- // unexpected; the default branch should
- // catch this already, but be safe
- continue insLoop
- } else {
- ident = true
- }
- case *ssa.Lookup:
- default:
- // the string is used somewhere else than a
- // map lookup
- continue insLoop
- }
- }
-
- // the result of the conversion wasn't assigned to an
- // identifier
- if !ident {
- continue
- }
- j.Errorf(conv, "m[string(key)] would be more efficient than k := string(key); m[k]")
- }
- }
- }
-}
-
-func (c *Checker) CheckRangeStringRunes(j *lint.Job) {
- sharedcheck.CheckRangeStringRunes(c.nodeFns, j)
-}
-
-func (c *Checker) CheckSelfAssignment(j *lint.Job) {
- fn := func(node ast.Node) bool {
- assign, ok := node.(*ast.AssignStmt)
- if !ok {
- return true
- }
- if assign.Tok != token.ASSIGN || len(assign.Lhs) != len(assign.Rhs) {
- return true
- }
- for i, stmt := range assign.Lhs {
- rlh := j.Render(stmt)
- rrh := j.Render(assign.Rhs[i])
- if rlh == rrh {
- j.Errorf(assign, "self-assignment of %s to %s", rrh, rlh)
- }
- }
- return true
- }
- for _, f := range c.filterGenerated(j.Program.Files) {
- ast.Inspect(f, fn)
- }
-}
-
-func buildTagsIdentical(s1, s2 []string) bool {
- if len(s1) != len(s2) {
- return false
- }
- s1s := make([]string, len(s1))
- copy(s1s, s1)
- sort.Strings(s1s)
- s2s := make([]string, len(s2))
- copy(s2s, s2)
- sort.Strings(s2s)
- for i, s := range s1s {
- if s != s2s[i] {
- return false
- }
- }
- return true
-}
-
-func (c *Checker) CheckDuplicateBuildConstraints(job *lint.Job) {
- for _, f := range c.filterGenerated(job.Program.Files) {
- constraints := buildTags(f)
- for i, constraint1 := range constraints {
- for j, constraint2 := range constraints {
- if i >= j {
- continue
- }
- if buildTagsIdentical(constraint1, constraint2) {
- job.Errorf(f, "identical build constraints %q and %q",
- strings.Join(constraint1, " "),
- strings.Join(constraint2, " "))
- }
- }
- }
- }
-}
diff --git a/vendor/honnef.co/go/tools/staticcheck/rules.go b/vendor/honnef.co/go/tools/staticcheck/rules.go
deleted file mode 100644
index 60cc00c..0000000
--- a/vendor/honnef.co/go/tools/staticcheck/rules.go
+++ /dev/null
@@ -1,321 +0,0 @@
-package staticcheck
-
-import (
- "fmt"
- "go/constant"
- "go/types"
- "net"
- "net/url"
- "regexp"
- "sort"
- "strconv"
- "strings"
- "time"
- "unicode/utf8"
-
- "honnef.co/go/tools/lint"
- "honnef.co/go/tools/ssa"
- "honnef.co/go/tools/staticcheck/vrp"
-)
-
-const (
- MsgInvalidHostPort = "invalid port or service name in host:port pair"
- MsgInvalidUTF8 = "argument is not a valid UTF-8 encoded string"
- MsgNonUniqueCutset = "cutset contains duplicate characters"
-)
-
-type Call struct {
- Job *lint.Job
- Instr ssa.CallInstruction
- Args []*Argument
-
- Checker *Checker
- Parent *ssa.Function
-
- invalids []string
-}
-
-func (c *Call) Invalid(msg string) {
- c.invalids = append(c.invalids, msg)
-}
-
-type Argument struct {
- Value Value
- invalids []string
-}
-
-func (arg *Argument) Invalid(msg string) {
- arg.invalids = append(arg.invalids, msg)
-}
-
-type Value struct {
- Value ssa.Value
- Range vrp.Range
-}
-
-type CallCheck func(call *Call)
-
-func extractConsts(v ssa.Value) []*ssa.Const {
- switch v := v.(type) {
- case *ssa.Const:
- return []*ssa.Const{v}
- case *ssa.MakeInterface:
- return extractConsts(v.X)
- default:
- return nil
- }
-}
-
-func ValidateRegexp(v Value) error {
- for _, c := range extractConsts(v.Value) {
- if c.Value == nil {
- continue
- }
- if c.Value.Kind() != constant.String {
- continue
- }
- s := constant.StringVal(c.Value)
- if _, err := regexp.Compile(s); err != nil {
- return err
- }
- }
- return nil
-}
-
-func ValidateTimeLayout(v Value) error {
- for _, c := range extractConsts(v.Value) {
- if c.Value == nil {
- continue
- }
- if c.Value.Kind() != constant.String {
- continue
- }
- s := constant.StringVal(c.Value)
- s = strings.Replace(s, "_", " ", -1)
- s = strings.Replace(s, "Z", "-", -1)
- _, err := time.Parse(s, s)
- if err != nil {
- return err
- }
- }
- return nil
-}
-
-func ValidateURL(v Value) error {
- for _, c := range extractConsts(v.Value) {
- if c.Value == nil {
- continue
- }
- if c.Value.Kind() != constant.String {
- continue
- }
- s := constant.StringVal(c.Value)
- _, err := url.Parse(s)
- if err != nil {
- return fmt.Errorf("%q is not a valid URL: %s", s, err)
- }
- }
- return nil
-}
-
-func IntValue(v Value, z vrp.Z) bool {
- r, ok := v.Range.(vrp.IntInterval)
- if !ok || !r.IsKnown() {
- return false
- }
- if r.Lower != r.Upper {
- return false
- }
- if r.Lower.Cmp(z) == 0 {
- return true
- }
- return false
-}
-
-func InvalidUTF8(v Value) bool {
- for _, c := range extractConsts(v.Value) {
- if c.Value == nil {
- continue
- }
- if c.Value.Kind() != constant.String {
- continue
- }
- s := constant.StringVal(c.Value)
- if !utf8.ValidString(s) {
- return true
- }
- }
- return false
-}
-
-func UnbufferedChannel(v Value) bool {
- r, ok := v.Range.(vrp.ChannelInterval)
- if !ok || !r.IsKnown() {
- return false
- }
- if r.Size.Lower.Cmp(vrp.NewZ(0)) == 0 &&
- r.Size.Upper.Cmp(vrp.NewZ(0)) == 0 {
- return true
- }
- return false
-}
-
-func Pointer(v Value) bool {
- switch v.Value.Type().Underlying().(type) {
- case *types.Pointer, *types.Interface:
- return true
- }
- return false
-}
-
-func ConvertedFromInt(v Value) bool {
- conv, ok := v.Value.(*ssa.Convert)
- if !ok {
- return false
- }
- b, ok := conv.X.Type().Underlying().(*types.Basic)
- if !ok {
- return false
- }
- if (b.Info() & types.IsInteger) == 0 {
- return false
- }
- return true
-}
-
-func validEncodingBinaryType(j *lint.Job, typ types.Type) bool {
- typ = typ.Underlying()
- switch typ := typ.(type) {
- case *types.Basic:
- switch typ.Kind() {
- case types.Uint8, types.Uint16, types.Uint32, types.Uint64,
- types.Int8, types.Int16, types.Int32, types.Int64,
- types.Float32, types.Float64, types.Complex64, types.Complex128, types.Invalid:
- return true
- case types.Bool:
- return j.IsGoVersion(8)
- }
- return false
- case *types.Struct:
- n := typ.NumFields()
- for i := 0; i < n; i++ {
- if !validEncodingBinaryType(j, typ.Field(i).Type()) {
- return false
- }
- }
- return true
- case *types.Array:
- return validEncodingBinaryType(j, typ.Elem())
- case *types.Interface:
- // we can't determine if it's a valid type or not
- return true
- }
- return false
-}
-
-func CanBinaryMarshal(j *lint.Job, v Value) bool {
- typ := v.Value.Type().Underlying()
- if ttyp, ok := typ.(*types.Pointer); ok {
- typ = ttyp.Elem().Underlying()
- }
- if ttyp, ok := typ.(interface {
- Elem() types.Type
- }); ok {
- if _, ok := ttyp.(*types.Pointer); !ok {
- typ = ttyp.Elem()
- }
- }
-
- return validEncodingBinaryType(j, typ)
-}
-
-func RepeatZeroTimes(name string, arg int) CallCheck {
- return func(call *Call) {
- arg := call.Args[arg]
- if IntValue(arg.Value, vrp.NewZ(0)) {
- arg.Invalid(fmt.Sprintf("calling %s with n == 0 will return no results, did you mean -1?", name))
- }
- }
-}
-
-func validateServiceName(s string) bool {
- if len(s) < 1 || len(s) > 15 {
- return false
- }
- if s[0] == '-' || s[len(s)-1] == '-' {
- return false
- }
- if strings.Contains(s, "--") {
- return false
- }
- hasLetter := false
- for _, r := range s {
- if (r >= 'A' && r <= 'Z') || (r >= 'a' && r <= 'z') {
- hasLetter = true
- continue
- }
- if r >= '0' && r <= '9' {
- continue
- }
- return false
- }
- return hasLetter
-}
-
-func validatePort(s string) bool {
- n, err := strconv.ParseInt(s, 10, 64)
- if err != nil {
- return validateServiceName(s)
- }
- return n >= 0 && n <= 65535
-}
-
-func ValidHostPort(v Value) bool {
- for _, k := range extractConsts(v.Value) {
- if k.Value == nil {
- continue
- }
- if k.Value.Kind() != constant.String {
- continue
- }
- s := constant.StringVal(k.Value)
- _, port, err := net.SplitHostPort(s)
- if err != nil {
- return false
- }
- // TODO(dh): check hostname
- if !validatePort(port) {
- return false
- }
- }
- return true
-}
-
-// ConvertedFrom reports whether value v was converted from type typ.
-func ConvertedFrom(v Value, typ string) bool {
- change, ok := v.Value.(*ssa.ChangeType)
- return ok && types.TypeString(change.X.Type(), nil) == typ
-}
-
-func UniqueStringCutset(v Value) bool {
- for _, c := range extractConsts(v.Value) {
- if c.Value == nil {
- continue
- }
- if c.Value.Kind() != constant.String {
- continue
- }
- s := constant.StringVal(c.Value)
- rs := runeSlice(s)
- if len(rs) < 2 {
- continue
- }
- sort.Sort(rs)
- for i, r := range rs[1:] {
- if rs[i] == r {
- return false
- }
- }
- }
- return true
-}
diff --git a/vendor/honnef.co/go/tools/staticcheck/vrp/channel.go b/vendor/honnef.co/go/tools/staticcheck/vrp/channel.go
deleted file mode 100644
index c8fbacb..0000000
--- a/vendor/honnef.co/go/tools/staticcheck/vrp/channel.go
+++ /dev/null
@@ -1,73 +0,0 @@
-package vrp
-
-import (
- "fmt"
-
- "honnef.co/go/tools/ssa"
-)
-
-type ChannelInterval struct {
- Size IntInterval
-}
-
-func (c ChannelInterval) Union(other Range) Range {
- i, ok := other.(ChannelInterval)
- if !ok {
- i = ChannelInterval{EmptyIntInterval}
- }
- if c.Size.Empty() || !c.Size.IsKnown() {
- return i
- }
- if i.Size.Empty() || !i.Size.IsKnown() {
- return c
- }
- return ChannelInterval{
- Size: c.Size.Union(i.Size).(IntInterval),
- }
-}
-
-func (c ChannelInterval) String() string {
- return c.Size.String()
-}
-
-func (c ChannelInterval) IsKnown() bool {
- return c.Size.IsKnown()
-}
-
-type MakeChannelConstraint struct {
- aConstraint
- Buffer ssa.Value
-}
-type ChannelChangeTypeConstraint struct {
- aConstraint
- X ssa.Value
-}
-
-func NewMakeChannelConstraint(buffer, y ssa.Value) Constraint {
- return &MakeChannelConstraint{NewConstraint(y), buffer}
-}
-func NewChannelChangeTypeConstraint(x, y ssa.Value) Constraint {
- return &ChannelChangeTypeConstraint{NewConstraint(y), x}
-}
-
-func (c *MakeChannelConstraint) Operands() []ssa.Value { return []ssa.Value{c.Buffer} }
-func (c *ChannelChangeTypeConstraint) Operands() []ssa.Value { return []ssa.Value{c.X} }
-
-func (c *MakeChannelConstraint) String() string {
- return fmt.Sprintf("%s = make(chan, %s)", c.Y().Name, c.Buffer.Name())
-}
-func (c *ChannelChangeTypeConstraint) String() string {
- return fmt.Sprintf("%s = changetype(%s)", c.Y().Name, c.X.Name())
-}
-
-func (c *MakeChannelConstraint) Eval(g *Graph) Range {
- i, ok := g.Range(c.Buffer).(IntInterval)
- if !ok {
- return ChannelInterval{NewIntInterval(NewZ(0), PInfinity)}
- }
- if i.Lower.Sign() == -1 {
- i.Lower = NewZ(0)
- }
- return ChannelInterval{i}
-}
-func (c *ChannelChangeTypeConstraint) Eval(g *Graph) Range { return g.Range(c.X) }
diff --git a/vendor/honnef.co/go/tools/staticcheck/vrp/int.go b/vendor/honnef.co/go/tools/staticcheck/vrp/int.go
deleted file mode 100644
index 926bb7a..0000000
--- a/vendor/honnef.co/go/tools/staticcheck/vrp/int.go
+++ /dev/null
@@ -1,476 +0,0 @@
-package vrp
-
-import (
- "fmt"
- "go/token"
- "go/types"
- "math/big"
-
- "honnef.co/go/tools/ssa"
-)
-
-type Zs []Z
-
-func (zs Zs) Len() int {
- return len(zs)
-}
-
-func (zs Zs) Less(i int, j int) bool {
- return zs[i].Cmp(zs[j]) == -1
-}
-
-func (zs Zs) Swap(i int, j int) {
- zs[i], zs[j] = zs[j], zs[i]
-}
-
-type Z struct {
- infinity int8
- integer *big.Int
-}
-
-func NewZ(n int64) Z {
- return NewBigZ(big.NewInt(n))
-}
-
-func NewBigZ(n *big.Int) Z {
- return Z{integer: n}
-}
-
-func (z1 Z) Infinite() bool {
- return z1.infinity != 0
-}
-
-func (z1 Z) Add(z2 Z) Z {
- if z2.Sign() == -1 {
- return z1.Sub(z2.Negate())
- }
- if z1 == NInfinity {
- return NInfinity
- }
- if z1 == PInfinity {
- return PInfinity
- }
- if z2 == PInfinity {
- return PInfinity
- }
-
- if !z1.Infinite() && !z2.Infinite() {
- n := &big.Int{}
- n.Add(z1.integer, z2.integer)
- return NewBigZ(n)
- }
-
- panic(fmt.Sprintf("%s + %s is not defined", z1, z2))
-}
-
-func (z1 Z) Sub(z2 Z) Z {
- if z2.Sign() == -1 {
- return z1.Add(z2.Negate())
- }
- if !z1.Infinite() && !z2.Infinite() {
- n := &big.Int{}
- n.Sub(z1.integer, z2.integer)
- return NewBigZ(n)
- }
-
- if z1 != PInfinity && z2 == PInfinity {
- return NInfinity
- }
- if z1.Infinite() && !z2.Infinite() {
- return Z{infinity: z1.infinity}
- }
- if z1 == PInfinity && z2 == PInfinity {
- return PInfinity
- }
- panic(fmt.Sprintf("%s - %s is not defined", z1, z2))
-}
-
-func (z1 Z) Mul(z2 Z) Z {
- if (z1.integer != nil && z1.integer.Sign() == 0) ||
- (z2.integer != nil && z2.integer.Sign() == 0) {
- return NewBigZ(&big.Int{})
- }
-
- if z1.infinity != 0 || z2.infinity != 0 {
- return Z{infinity: int8(z1.Sign() * z2.Sign())}
- }
-
- n := &big.Int{}
- n.Mul(z1.integer, z2.integer)
- return NewBigZ(n)
-}
-
-func (z1 Z) Negate() Z {
- if z1.infinity == 1 {
- return NInfinity
- }
- if z1.infinity == -1 {
- return PInfinity
- }
- n := &big.Int{}
- n.Neg(z1.integer)
- return NewBigZ(n)
-}
-
-func (z1 Z) Sign() int {
- if z1.infinity != 0 {
- return int(z1.infinity)
- }
- return z1.integer.Sign()
-}
-
-func (z1 Z) String() string {
- if z1 == NInfinity {
- return "-∞"
- }
- if z1 == PInfinity {
- return "∞"
- }
- return fmt.Sprintf("%d", z1.integer)
-}
-
-func (z1 Z) Cmp(z2 Z) int {
- if z1.infinity == z2.infinity && z1.infinity != 0 {
- return 0
- }
- if z1 == PInfinity {
- return 1
- }
- if z1 == NInfinity {
- return -1
- }
- if z2 == NInfinity {
- return 1
- }
- if z2 == PInfinity {
- return -1
- }
- return z1.integer.Cmp(z2.integer)
-}
-
-func MaxZ(zs ...Z) Z {
- if len(zs) == 0 {
- panic("Max called with no arguments")
- }
- if len(zs) == 1 {
- return zs[0]
- }
- ret := zs[0]
- for _, z := range zs[1:] {
- if z.Cmp(ret) == 1 {
- ret = z
- }
- }
- return ret
-}
-
-func MinZ(zs ...Z) Z {
- if len(zs) == 0 {
- panic("Min called with no arguments")
- }
- if len(zs) == 1 {
- return zs[0]
- }
- ret := zs[0]
- for _, z := range zs[1:] {
- if z.Cmp(ret) == -1 {
- ret = z
- }
- }
- return ret
-}
-
-var NInfinity = Z{infinity: -1}
-var PInfinity = Z{infinity: 1}
-var EmptyIntInterval = IntInterval{true, PInfinity, NInfinity}
-
-func InfinityFor(v ssa.Value) IntInterval {
- if b, ok := v.Type().Underlying().(*types.Basic); ok {
- if (b.Info() & types.IsUnsigned) != 0 {
- return NewIntInterval(NewZ(0), PInfinity)
- }
- }
- return NewIntInterval(NInfinity, PInfinity)
-}
-
-type IntInterval struct {
- known bool
- Lower Z
- Upper Z
-}
-
-func NewIntInterval(l, u Z) IntInterval {
- if u.Cmp(l) == -1 {
- return EmptyIntInterval
- }
- return IntInterval{known: true, Lower: l, Upper: u}
-}
-
-func (i IntInterval) IsKnown() bool {
- return i.known
-}
-
-func (i IntInterval) Empty() bool {
- return i.Lower == PInfinity && i.Upper == NInfinity
-}
-
-func (i IntInterval) IsMaxRange() bool {
- return i.Lower == NInfinity && i.Upper == PInfinity
-}
-
-func (i1 IntInterval) Intersection(i2 IntInterval) IntInterval {
- if !i1.IsKnown() {
- return i2
- }
- if !i2.IsKnown() {
- return i1
- }
- if i1.Empty() || i2.Empty() {
- return EmptyIntInterval
- }
- i3 := NewIntInterval(MaxZ(i1.Lower, i2.Lower), MinZ(i1.Upper, i2.Upper))
- if i3.Lower.Cmp(i3.Upper) == 1 {
- return EmptyIntInterval
- }
- return i3
-}
-
-func (i1 IntInterval) Union(other Range) Range {
- i2, ok := other.(IntInterval)
- if !ok {
- i2 = EmptyIntInterval
- }
- if i1.Empty() || !i1.IsKnown() {
- return i2
- }
- if i2.Empty() || !i2.IsKnown() {
- return i1
- }
- return NewIntInterval(MinZ(i1.Lower, i2.Lower), MaxZ(i1.Upper, i2.Upper))
-}
-
-func (i1 IntInterval) Add(i2 IntInterval) IntInterval {
- if i1.Empty() || i2.Empty() {
- return EmptyIntInterval
- }
- l1, u1, l2, u2 := i1.Lower, i1.Upper, i2.Lower, i2.Upper
- return NewIntInterval(l1.Add(l2), u1.Add(u2))
-}
-
-func (i1 IntInterval) Sub(i2 IntInterval) IntInterval {
- if i1.Empty() || i2.Empty() {
- return EmptyIntInterval
- }
- l1, u1, l2, u2 := i1.Lower, i1.Upper, i2.Lower, i2.Upper
- return NewIntInterval(l1.Sub(u2), u1.Sub(l2))
-}
-
-func (i1 IntInterval) Mul(i2 IntInterval) IntInterval {
- if i1.Empty() || i2.Empty() {
- return EmptyIntInterval
- }
- x1, x2 := i1.Lower, i1.Upper
- y1, y2 := i2.Lower, i2.Upper
- return NewIntInterval(
- MinZ(x1.Mul(y1), x1.Mul(y2), x2.Mul(y1), x2.Mul(y2)),
- MaxZ(x1.Mul(y1), x1.Mul(y2), x2.Mul(y1), x2.Mul(y2)),
- )
-}
-
-func (i1 IntInterval) String() string {
- if !i1.IsKnown() {
- return "[⊥, ⊥]"
- }
- if i1.Empty() {
- return "{}"
- }
- return fmt.Sprintf("[%s, %s]", i1.Lower, i1.Upper)
-}
-
-type IntArithmeticConstraint struct {
- aConstraint
- A ssa.Value
- B ssa.Value
- Op token.Token
- Fn func(IntInterval, IntInterval) IntInterval
-}
-
-type IntAddConstraint struct{ *IntArithmeticConstraint }
-type IntSubConstraint struct{ *IntArithmeticConstraint }
-type IntMulConstraint struct{ *IntArithmeticConstraint }
-
-type IntConversionConstraint struct {
- aConstraint
- X ssa.Value
-}
-
-type IntIntersectionConstraint struct {
- aConstraint
- ranges Ranges
- A ssa.Value
- B ssa.Value
- Op token.Token
- I IntInterval
- resolved bool
-}
-
-type IntIntervalConstraint struct {
- aConstraint
- I IntInterval
-}
-
-func NewIntArithmeticConstraint(a, b, y ssa.Value, op token.Token, fn func(IntInterval, IntInterval) IntInterval) *IntArithmeticConstraint {
- return &IntArithmeticConstraint{NewConstraint(y), a, b, op, fn}
-}
-func NewIntAddConstraint(a, b, y ssa.Value) Constraint {
- return &IntAddConstraint{NewIntArithmeticConstraint(a, b, y, token.ADD, IntInterval.Add)}
-}
-func NewIntSubConstraint(a, b, y ssa.Value) Constraint {
- return &IntSubConstraint{NewIntArithmeticConstraint(a, b, y, token.SUB, IntInterval.Sub)}
-}
-func NewIntMulConstraint(a, b, y ssa.Value) Constraint {
- return &IntMulConstraint{NewIntArithmeticConstraint(a, b, y, token.MUL, IntInterval.Mul)}
-}
-func NewIntConversionConstraint(x, y ssa.Value) Constraint {
- return &IntConversionConstraint{NewConstraint(y), x}
-}
-func NewIntIntersectionConstraint(a, b ssa.Value, op token.Token, ranges Ranges, y ssa.Value) Constraint {
- return &IntIntersectionConstraint{
- aConstraint: NewConstraint(y),
- ranges: ranges,
- A: a,
- B: b,
- Op: op,
- }
-}
-func NewIntIntervalConstraint(i IntInterval, y ssa.Value) Constraint {
- return &IntIntervalConstraint{NewConstraint(y), i}
-}
-
-func (c *IntArithmeticConstraint) Operands() []ssa.Value { return []ssa.Value{c.A, c.B} }
-func (c *IntConversionConstraint) Operands() []ssa.Value { return []ssa.Value{c.X} }
-func (c *IntIntersectionConstraint) Operands() []ssa.Value { return []ssa.Value{c.A} }
-func (s *IntIntervalConstraint) Operands() []ssa.Value { return nil }
-
-func (c *IntArithmeticConstraint) String() string {
- return fmt.Sprintf("%s = %s %s %s", c.Y().Name(), c.A.Name(), c.Op, c.B.Name())
-}
-func (c *IntConversionConstraint) String() string {
- return fmt.Sprintf("%s = %s(%s)", c.Y().Name(), c.Y().Type(), c.X.Name())
-}
-func (c *IntIntersectionConstraint) String() string {
- return fmt.Sprintf("%s = %s %s %s (%t branch)", c.Y().Name(), c.A.Name(), c.Op, c.B.Name(), c.Y().(*ssa.Sigma).Branch)
-}
-func (c *IntIntervalConstraint) String() string { return fmt.Sprintf("%s = %s", c.Y().Name(), c.I) }
-
-func (c *IntArithmeticConstraint) Eval(g *Graph) Range {
- i1, i2 := g.Range(c.A).(IntInterval), g.Range(c.B).(IntInterval)
- if !i1.IsKnown() || !i2.IsKnown() {
- return IntInterval{}
- }
- return c.Fn(i1, i2)
-}
-func (c *IntConversionConstraint) Eval(g *Graph) Range {
- s := &types.StdSizes{
- // XXX is it okay to assume the largest word size, or do we
- // need to be platform specific?
- WordSize: 8,
- MaxAlign: 1,
- }
- fromI := g.Range(c.X).(IntInterval)
- toI := g.Range(c.Y()).(IntInterval)
- fromT := c.X.Type().Underlying().(*types.Basic)
- toT := c.Y().Type().Underlying().(*types.Basic)
- fromB := s.Sizeof(c.X.Type())
- toB := s.Sizeof(c.Y().Type())
-
- if !fromI.IsKnown() {
- return toI
- }
- if !toI.IsKnown() {
- return fromI
- }
-
- // uint<N> -> sint/uint<M>, M > N: [max(0, l1), min(2**N-1, u2)]
- if (fromT.Info()&types.IsUnsigned != 0) &&
- toB > fromB {
-
- n := big.NewInt(1)
- n.Lsh(n, uint(fromB*8))
- n.Sub(n, big.NewInt(1))
- return NewIntInterval(
- MaxZ(NewZ(0), fromI.Lower),
- MinZ(NewBigZ(n), toI.Upper),
- )
- }
-
- // sint<N> -> sint<M>, M > N; [max(-∞, l1), min(2**N-1, u2)]
- if (fromT.Info()&types.IsUnsigned == 0) &&
- (toT.Info()&types.IsUnsigned == 0) &&
- toB > fromB {
-
- n := big.NewInt(1)
- n.Lsh(n, uint(fromB*8))
- n.Sub(n, big.NewInt(1))
- return NewIntInterval(
- MaxZ(NInfinity, fromI.Lower),
- MinZ(NewBigZ(n), toI.Upper),
- )
- }
-
- return fromI
-}
-func (c *IntIntersectionConstraint) Eval(g *Graph) Range {
- xi := g.Range(c.A).(IntInterval)
- if !xi.IsKnown() {
- return c.I
- }
- return xi.Intersection(c.I)
-}
-func (c *IntIntervalConstraint) Eval(*Graph) Range { return c.I }
-
-func (c *IntIntersectionConstraint) Futures() []ssa.Value {
- return []ssa.Value{c.B}
-}
-
-func (c *IntIntersectionConstraint) Resolve() {
- r, ok := c.ranges[c.B].(IntInterval)
- if !ok {
- c.I = InfinityFor(c.Y())
- return
- }
-
- switch c.Op {
- case token.EQL:
- c.I = r
- case token.GTR:
- c.I = NewIntInterval(r.Lower.Add(NewZ(1)), PInfinity)
- case token.GEQ:
- c.I = NewIntInterval(r.Lower, PInfinity)
- case token.LSS:
- // TODO(dh): do we need 0 instead of NInfinity for uints?
- c.I = NewIntInterval(NInfinity, r.Upper.Sub(NewZ(1)))
- case token.LEQ:
- c.I = NewIntInterval(NInfinity, r.Upper)
- case token.NEQ:
- c.I = InfinityFor(c.Y())
- default:
- panic("unsupported op " + c.Op.String())
- }
-}
-
-func (c *IntIntersectionConstraint) IsKnown() bool {
- return c.I.IsKnown()
-}
-
-func (c *IntIntersectionConstraint) MarkUnresolved() {
- c.resolved = false
-}
-
-func (c *IntIntersectionConstraint) MarkResolved() {
- c.resolved = true
-}
-
-func (c *IntIntersectionConstraint) IsResolved() bool {
- return c.resolved
-}
diff --git a/vendor/honnef.co/go/tools/staticcheck/vrp/slice.go b/vendor/honnef.co/go/tools/staticcheck/vrp/slice.go
deleted file mode 100644
index 40658dd..0000000
--- a/vendor/honnef.co/go/tools/staticcheck/vrp/slice.go
+++ /dev/null
@@ -1,273 +0,0 @@
-package vrp
-
-// TODO(dh): most of the constraints have implementations identical to
-// that of strings. Consider reusing them.
-
-import (
- "fmt"
- "go/types"
-
- "honnef.co/go/tools/ssa"
-)
-
-type SliceInterval struct {
- Length IntInterval
-}
-
-func (s SliceInterval) Union(other Range) Range {
- i, ok := other.(SliceInterval)
- if !ok {
- i = SliceInterval{EmptyIntInterval}
- }
- if s.Length.Empty() || !s.Length.IsKnown() {
- return i
- }
- if i.Length.Empty() || !i.Length.IsKnown() {
- return s
- }
- return SliceInterval{
- Length: s.Length.Union(i.Length).(IntInterval),
- }
-}
-func (s SliceInterval) String() string { return s.Length.String() }
-func (s SliceInterval) IsKnown() bool { return s.Length.IsKnown() }
-
-type SliceAppendConstraint struct {
- aConstraint
- A ssa.Value
- B ssa.Value
-}
-
-type SliceSliceConstraint struct {
- aConstraint
- X ssa.Value
- Lower ssa.Value
- Upper ssa.Value
-}
-
-type ArraySliceConstraint struct {
- aConstraint
- X ssa.Value
- Lower ssa.Value
- Upper ssa.Value
-}
-
-type SliceIntersectionConstraint struct {
- aConstraint
- X ssa.Value
- I IntInterval
-}
-
-type SliceLengthConstraint struct {
- aConstraint
- X ssa.Value
-}
-
-type MakeSliceConstraint struct {
- aConstraint
- Size ssa.Value
-}
-
-type SliceIntervalConstraint struct {
- aConstraint
- I IntInterval
-}
-
-func NewSliceAppendConstraint(a, b, y ssa.Value) Constraint {
- return &SliceAppendConstraint{NewConstraint(y), a, b}
-}
-func NewSliceSliceConstraint(x, lower, upper, y ssa.Value) Constraint {
- return &SliceSliceConstraint{NewConstraint(y), x, lower, upper}
-}
-func NewArraySliceConstraint(x, lower, upper, y ssa.Value) Constraint {
- return &ArraySliceConstraint{NewConstraint(y), x, lower, upper}
-}
-func NewSliceIntersectionConstraint(x ssa.Value, i IntInterval, y ssa.Value) Constraint {
- return &SliceIntersectionConstraint{NewConstraint(y), x, i}
-}
-func NewSliceLengthConstraint(x, y ssa.Value) Constraint {
- return &SliceLengthConstraint{NewConstraint(y), x}
-}
-func NewMakeSliceConstraint(size, y ssa.Value) Constraint {
- return &MakeSliceConstraint{NewConstraint(y), size}
-}
-func NewSliceIntervalConstraint(i IntInterval, y ssa.Value) Constraint {
- return &SliceIntervalConstraint{NewConstraint(y), i}
-}
-
-func (c *SliceAppendConstraint) Operands() []ssa.Value { return []ssa.Value{c.A, c.B} }
-func (c *SliceSliceConstraint) Operands() []ssa.Value {
- ops := []ssa.Value{c.X}
- if c.Lower != nil {
- ops = append(ops, c.Lower)
- }
- if c.Upper != nil {
- ops = append(ops, c.Upper)
- }
- return ops
-}
-func (c *ArraySliceConstraint) Operands() []ssa.Value {
- ops := []ssa.Value{c.X}
- if c.Lower != nil {
- ops = append(ops, c.Lower)
- }
- if c.Upper != nil {
- ops = append(ops, c.Upper)
- }
- return ops
-}
-func (c *SliceIntersectionConstraint) Operands() []ssa.Value { return []ssa.Value{c.X} }
-func (c *SliceLengthConstraint) Operands() []ssa.Value { return []ssa.Value{c.X} }
-func (c *MakeSliceConstraint) Operands() []ssa.Value { return []ssa.Value{c.Size} }
-func (s *SliceIntervalConstraint) Operands() []ssa.Value { return nil }
-
-func (c *SliceAppendConstraint) String() string {
- return fmt.Sprintf("%s = append(%s, %s)", c.Y().Name(), c.A.Name(), c.B.Name())
-}
-func (c *SliceSliceConstraint) String() string {
- var lname, uname string
- if c.Lower != nil {
- lname = c.Lower.Name()
- }
- if c.Upper != nil {
- uname = c.Upper.Name()
- }
- return fmt.Sprintf("%s[%s:%s]", c.X.Name(), lname, uname)
-}
-func (c *ArraySliceConstraint) String() string {
- var lname, uname string
- if c.Lower != nil {
- lname = c.Lower.Name()
- }
- if c.Upper != nil {
- uname = c.Upper.Name()
- }
- return fmt.Sprintf("%s[%s:%s]", c.X.Name(), lname, uname)
-}
-func (c *SliceIntersectionConstraint) String() string {
- return fmt.Sprintf("%s = %s.%t ⊓ %s", c.Y().Name(), c.X.Name(), c.Y().(*ssa.Sigma).Branch, c.I)
-}
-func (c *SliceLengthConstraint) String() string {
- return fmt.Sprintf("%s = len(%s)", c.Y().Name(), c.X.Name())
-}
-func (c *MakeSliceConstraint) String() string {
- return fmt.Sprintf("%s = make(slice, %s)", c.Y().Name(), c.Size.Name())
-}
-func (c *SliceIntervalConstraint) String() string { return fmt.Sprintf("%s = %s", c.Y().Name(), c.I) }
-
-func (c *SliceAppendConstraint) Eval(g *Graph) Range {
- l1 := g.Range(c.A).(SliceInterval).Length
- var l2 IntInterval
- switch r := g.Range(c.B).(type) {
- case SliceInterval:
- l2 = r.Length
- case StringInterval:
- l2 = r.Length
- default:
- return SliceInterval{}
- }
- if !l1.IsKnown() || !l2.IsKnown() {
- return SliceInterval{}
- }
- return SliceInterval{
- Length: l1.Add(l2),
- }
-}
-func (c *SliceSliceConstraint) Eval(g *Graph) Range {
- lr := NewIntInterval(NewZ(0), NewZ(0))
- if c.Lower != nil {
- lr = g.Range(c.Lower).(IntInterval)
- }
- ur := g.Range(c.X).(SliceInterval).Length
- if c.Upper != nil {
- ur = g.Range(c.Upper).(IntInterval)
- }
- if !lr.IsKnown() || !ur.IsKnown() {
- return SliceInterval{}
- }
-
- ls := []Z{
- ur.Lower.Sub(lr.Lower),
- ur.Upper.Sub(lr.Lower),
- ur.Lower.Sub(lr.Upper),
- ur.Upper.Sub(lr.Upper),
- }
- // TODO(dh): if we don't truncate lengths to 0 we might be able to
- // easily detect slices with high < low. we'd need to treat -∞
- // specially, though.
- for i, l := range ls {
- if l.Sign() == -1 {
- ls[i] = NewZ(0)
- }
- }
-
- return SliceInterval{
- Length: NewIntInterval(MinZ(ls...), MaxZ(ls...)),
- }
-}
-func (c *ArraySliceConstraint) Eval(g *Graph) Range {
- lr := NewIntInterval(NewZ(0), NewZ(0))
- if c.Lower != nil {
- lr = g.Range(c.Lower).(IntInterval)
- }
- var l int64
- switch typ := c.X.Type().(type) {
- case *types.Array:
- l = typ.Len()
- case *types.Pointer:
- l = typ.Elem().(*types.Array).Len()
- }
- ur := NewIntInterval(NewZ(l), NewZ(l))
- if c.Upper != nil {
- ur = g.Range(c.Upper).(IntInterval)
- }
- if !lr.IsKnown() || !ur.IsKnown() {
- return SliceInterval{}
- }
-
- ls := []Z{
- ur.Lower.Sub(lr.Lower),
- ur.Upper.Sub(lr.Lower),
- ur.Lower.Sub(lr.Upper),
- ur.Upper.Sub(lr.Upper),
- }
- // TODO(dh): if we don't truncate lengths to 0 we might be able to
- // easily detect slices with high < low. we'd need to treat -∞
- // specially, though.
- for i, l := range ls {
- if l.Sign() == -1 {
- ls[i] = NewZ(0)
- }
- }
-
- return SliceInterval{
- Length: NewIntInterval(MinZ(ls...), MaxZ(ls...)),
- }
-}
-func (c *SliceIntersectionConstraint) Eval(g *Graph) Range {
- xi := g.Range(c.X).(SliceInterval)
- if !xi.IsKnown() {
- return c.I
- }
- return SliceInterval{
- Length: xi.Length.Intersection(c.I),
- }
-}
-func (c *SliceLengthConstraint) Eval(g *Graph) Range {
- i := g.Range(c.X).(SliceInterval).Length
- if !i.IsKnown() {
- return NewIntInterval(NewZ(0), PInfinity)
- }
- return i
-}
-func (c *MakeSliceConstraint) Eval(g *Graph) Range {
- i, ok := g.Range(c.Size).(IntInterval)
- if !ok {
- return SliceInterval{NewIntInterval(NewZ(0), PInfinity)}
- }
- if i.Lower.Sign() == -1 {
- i.Lower = NewZ(0)
- }
- return SliceInterval{i}
-}
-func (c *SliceIntervalConstraint) Eval(*Graph) Range { return SliceInterval{c.I} }
diff --git a/vendor/honnef.co/go/tools/staticcheck/vrp/string.go b/vendor/honnef.co/go/tools/staticcheck/vrp/string.go
deleted file mode 100644
index e05877f..0000000
--- a/vendor/honnef.co/go/tools/staticcheck/vrp/string.go
+++ /dev/null
@@ -1,258 +0,0 @@
-package vrp
-
-import (
- "fmt"
- "go/token"
- "go/types"
-
- "honnef.co/go/tools/ssa"
-)
-
-type StringInterval struct {
- Length IntInterval
-}
-
-func (s StringInterval) Union(other Range) Range {
- i, ok := other.(StringInterval)
- if !ok {
- i = StringInterval{EmptyIntInterval}
- }
- if s.Length.Empty() || !s.Length.IsKnown() {
- return i
- }
- if i.Length.Empty() || !i.Length.IsKnown() {
- return s
- }
- return StringInterval{
- Length: s.Length.Union(i.Length).(IntInterval),
- }
-}
-
-func (s StringInterval) String() string {
- return s.Length.String()
-}
-
-func (s StringInterval) IsKnown() bool {
- return s.Length.IsKnown()
-}
-
-type StringSliceConstraint struct {
- aConstraint
- X ssa.Value
- Lower ssa.Value
- Upper ssa.Value
-}
-
-type StringIntersectionConstraint struct {
- aConstraint
- ranges Ranges
- A ssa.Value
- B ssa.Value
- Op token.Token
- I IntInterval
- resolved bool
-}
-
-type StringConcatConstraint struct {
- aConstraint
- A ssa.Value
- B ssa.Value
-}
-
-type StringLengthConstraint struct {
- aConstraint
- X ssa.Value
-}
-
-type StringIntervalConstraint struct {
- aConstraint
- I IntInterval
-}
-
-func NewStringSliceConstraint(x, lower, upper, y ssa.Value) Constraint {
- return &StringSliceConstraint{NewConstraint(y), x, lower, upper}
-}
-func NewStringIntersectionConstraint(a, b ssa.Value, op token.Token, ranges Ranges, y ssa.Value) Constraint {
- return &StringIntersectionConstraint{
- aConstraint: NewConstraint(y),
- ranges: ranges,
- A: a,
- B: b,
- Op: op,
- }
-}
-func NewStringConcatConstraint(a, b, y ssa.Value) Constraint {
- return &StringConcatConstraint{NewConstraint(y), a, b}
-}
-func NewStringLengthConstraint(x ssa.Value, y ssa.Value) Constraint {
- return &StringLengthConstraint{NewConstraint(y), x}
-}
-func NewStringIntervalConstraint(i IntInterval, y ssa.Value) Constraint {
- return &StringIntervalConstraint{NewConstraint(y), i}
-}
-
-func (c *StringSliceConstraint) Operands() []ssa.Value {
- vs := []ssa.Value{c.X}
- if c.Lower != nil {
- vs = append(vs, c.Lower)
- }
- if c.Upper != nil {
- vs = append(vs, c.Upper)
- }
- return vs
-}
-func (c *StringIntersectionConstraint) Operands() []ssa.Value { return []ssa.Value{c.A} }
-func (c StringConcatConstraint) Operands() []ssa.Value { return []ssa.Value{c.A, c.B} }
-func (c *StringLengthConstraint) Operands() []ssa.Value { return []ssa.Value{c.X} }
-func (s *StringIntervalConstraint) Operands() []ssa.Value { return nil }
-
-func (c *StringSliceConstraint) String() string {
- var lname, uname string
- if c.Lower != nil {
- lname = c.Lower.Name()
- }
- if c.Upper != nil {
- uname = c.Upper.Name()
- }
- return fmt.Sprintf("%s[%s:%s]", c.X.Name(), lname, uname)
-}
-func (c *StringIntersectionConstraint) String() string {
- return fmt.Sprintf("%s = %s %s %s (%t branch)", c.Y().Name(), c.A.Name(), c.Op, c.B.Name(), c.Y().(*ssa.Sigma).Branch)
-}
-func (c StringConcatConstraint) String() string {
- return fmt.Sprintf("%s = %s + %s", c.Y().Name(), c.A.Name(), c.B.Name())
-}
-func (c *StringLengthConstraint) String() string {
- return fmt.Sprintf("%s = len(%s)", c.Y().Name(), c.X.Name())
-}
-func (c *StringIntervalConstraint) String() string { return fmt.Sprintf("%s = %s", c.Y().Name(), c.I) }
-
-func (c *StringSliceConstraint) Eval(g *Graph) Range {
- lr := NewIntInterval(NewZ(0), NewZ(0))
- if c.Lower != nil {
- lr = g.Range(c.Lower).(IntInterval)
- }
- ur := g.Range(c.X).(StringInterval).Length
- if c.Upper != nil {
- ur = g.Range(c.Upper).(IntInterval)
- }
- if !lr.IsKnown() || !ur.IsKnown() {
- return StringInterval{}
- }
-
- ls := []Z{
- ur.Lower.Sub(lr.Lower),
- ur.Upper.Sub(lr.Lower),
- ur.Lower.Sub(lr.Upper),
- ur.Upper.Sub(lr.Upper),
- }
- // TODO(dh): if we don't truncate lengths to 0 we might be able to
- // easily detect slices with high < low. we'd need to treat -∞
- // specially, though.
- for i, l := range ls {
- if l.Sign() == -1 {
- ls[i] = NewZ(0)
- }
- }
-
- return StringInterval{
- Length: NewIntInterval(MinZ(ls...), MaxZ(ls...)),
- }
-}
-func (c *StringIntersectionConstraint) Eval(g *Graph) Range {
- var l IntInterval
- switch r := g.Range(c.A).(type) {
- case StringInterval:
- l = r.Length
- case IntInterval:
- l = r
- }
-
- if !l.IsKnown() {
- return StringInterval{c.I}
- }
- return StringInterval{
- Length: l.Intersection(c.I),
- }
-}
-func (c StringConcatConstraint) Eval(g *Graph) Range {
- i1, i2 := g.Range(c.A).(StringInterval), g.Range(c.B).(StringInterval)
- if !i1.Length.IsKnown() || !i2.Length.IsKnown() {
- return StringInterval{}
- }
- return StringInterval{
- Length: i1.Length.Add(i2.Length),
- }
-}
-func (c *StringLengthConstraint) Eval(g *Graph) Range {
- i := g.Range(c.X).(StringInterval).Length
- if !i.IsKnown() {
- return NewIntInterval(NewZ(0), PInfinity)
- }
- return i
-}
-func (c *StringIntervalConstraint) Eval(*Graph) Range { return StringInterval{c.I} }
-
-func (c *StringIntersectionConstraint) Futures() []ssa.Value {
- return []ssa.Value{c.B}
-}
-
-func (c *StringIntersectionConstraint) Resolve() {
- if (c.A.Type().Underlying().(*types.Basic).Info() & types.IsString) != 0 {
- // comparing two strings
- r, ok := c.ranges[c.B].(StringInterval)
- if !ok {
- c.I = NewIntInterval(NewZ(0), PInfinity)
- return
- }
- switch c.Op {
- case token.EQL:
- c.I = r.Length
- case token.GTR, token.GEQ:
- c.I = NewIntInterval(r.Length.Lower, PInfinity)
- case token.LSS, token.LEQ:
- c.I = NewIntInterval(NewZ(0), r.Length.Upper)
- case token.NEQ:
- default:
- panic("unsupported op " + c.Op.String())
- }
- } else {
- r, ok := c.ranges[c.B].(IntInterval)
- if !ok {
- c.I = NewIntInterval(NewZ(0), PInfinity)
- return
- }
- // comparing two lengths
- switch c.Op {
- case token.EQL:
- c.I = r
- case token.GTR:
- c.I = NewIntInterval(r.Lower.Add(NewZ(1)), PInfinity)
- case token.GEQ:
- c.I = NewIntInterval(r.Lower, PInfinity)
- case token.LSS:
- c.I = NewIntInterval(NInfinity, r.Upper.Sub(NewZ(1)))
- case token.LEQ:
- c.I = NewIntInterval(NInfinity, r.Upper)
- case token.NEQ:
- default:
- panic("unsupported op " + c.Op.String())
- }
- }
-}
-
-func (c *StringIntersectionConstraint) IsKnown() bool {
- return c.I.IsKnown()
-}
-
-func (c *StringIntersectionConstraint) MarkUnresolved() {
- c.resolved = false
-}
-
-func (c *StringIntersectionConstraint) MarkResolved() {
- c.resolved = true
-}
-
-func (c *StringIntersectionConstraint) IsResolved() bool {
- return c.resolved
-}
diff --git a/vendor/honnef.co/go/tools/staticcheck/vrp/vrp.go b/vendor/honnef.co/go/tools/staticcheck/vrp/vrp.go
deleted file mode 100644
index cb17f04..0000000
--- a/vendor/honnef.co/go/tools/staticcheck/vrp/vrp.go
+++ /dev/null
@@ -1,1049 +0,0 @@
-package vrp
-
-// TODO(dh) widening and narrowing have a lot of code in common. Make
-// it reusable.
-
-import (
- "fmt"
- "go/constant"
- "go/token"
- "go/types"
- "math/big"
- "sort"
- "strings"
-
- "honnef.co/go/tools/ssa"
-)
-
-type Future interface {
- Constraint
- Futures() []ssa.Value
- Resolve()
- IsKnown() bool
- MarkUnresolved()
- MarkResolved()
- IsResolved() bool
-}
-
-type Range interface {
- Union(other Range) Range
- IsKnown() bool
-}
-
-type Constraint interface {
- Y() ssa.Value
- isConstraint()
- String() string
- Eval(*Graph) Range
- Operands() []ssa.Value
-}
-
-type aConstraint struct {
- y ssa.Value
-}
-
-func NewConstraint(y ssa.Value) aConstraint {
- return aConstraint{y}
-}
-
-func (aConstraint) isConstraint() {}
-func (c aConstraint) Y() ssa.Value { return c.y }
-
-type PhiConstraint struct {
- aConstraint
- Vars []ssa.Value
-}
-
-func NewPhiConstraint(vars []ssa.Value, y ssa.Value) Constraint {
- uniqm := map[ssa.Value]struct{}{}
- for _, v := range vars {
- uniqm[v] = struct{}{}
- }
- var uniq []ssa.Value
- for v := range uniqm {
- uniq = append(uniq, v)
- }
- return &PhiConstraint{
- aConstraint: NewConstraint(y),
- Vars: uniq,
- }
-}
-
-func (c *PhiConstraint) Operands() []ssa.Value {
- return c.Vars
-}
-
-func (c *PhiConstraint) Eval(g *Graph) Range {
- i := Range(nil)
- for _, v := range c.Vars {
- i = g.Range(v).Union(i)
- }
- return i
-}
-
-func (c *PhiConstraint) String() string {
- names := make([]string, len(c.Vars))
- for i, v := range c.Vars {
- names[i] = v.Name()
- }
- return fmt.Sprintf("%s = φ(%s)", c.Y().Name(), strings.Join(names, ", "))
-}
-
-func isSupportedType(typ types.Type) bool {
- switch typ := typ.Underlying().(type) {
- case *types.Basic:
- switch typ.Kind() {
- case types.String, types.UntypedString:
- return true
- default:
- if (typ.Info() & types.IsInteger) == 0 {
- return false
- }
- }
- case *types.Chan:
- return true
- case *types.Slice:
- return true
- default:
- return false
- }
- return true
-}
-
-func ConstantToZ(c constant.Value) Z {
- s := constant.ToInt(c).ExactString()
- n := &big.Int{}
- n.SetString(s, 10)
- return NewBigZ(n)
-}
-
-func sigmaInteger(g *Graph, ins *ssa.Sigma, cond *ssa.BinOp, ops []*ssa.Value) Constraint {
- op := cond.Op
- if !ins.Branch {
- op = (invertToken(op))
- }
-
- switch op {
- case token.EQL, token.GTR, token.GEQ, token.LSS, token.LEQ:
- default:
- return nil
- }
- var a, b ssa.Value
- if (*ops[0]) == ins.X {
- a = *ops[0]
- b = *ops[1]
- } else {
- a = *ops[1]
- b = *ops[0]
- op = flipToken(op)
- }
- return NewIntIntersectionConstraint(a, b, op, g.ranges, ins)
-}
-
-func sigmaString(g *Graph, ins *ssa.Sigma, cond *ssa.BinOp, ops []*ssa.Value) Constraint {
- op := cond.Op
- if !ins.Branch {
- op = (invertToken(op))
- }
-
- switch op {
- case token.EQL, token.GTR, token.GEQ, token.LSS, token.LEQ:
- default:
- return nil
- }
-
- if ((*ops[0]).Type().Underlying().(*types.Basic).Info() & types.IsString) == 0 {
- var a, b ssa.Value
- call, ok := (*ops[0]).(*ssa.Call)
- if ok && call.Common().Args[0] == ins.X {
- a = *ops[0]
- b = *ops[1]
- } else {
- a = *ops[1]
- b = *ops[0]
- op = flipToken(op)
- }
- return NewStringIntersectionConstraint(a, b, op, g.ranges, ins)
- }
- var a, b ssa.Value
- if (*ops[0]) == ins.X {
- a = *ops[0]
- b = *ops[1]
- } else {
- a = *ops[1]
- b = *ops[0]
- op = flipToken(op)
- }
- return NewStringIntersectionConstraint(a, b, op, g.ranges, ins)
-}
-
-func sigmaSlice(g *Graph, ins *ssa.Sigma, cond *ssa.BinOp, ops []*ssa.Value) Constraint {
- // TODO(dh) sigmaSlice and sigmaString are a lot alike. Can they
- // be merged?
- //
- // XXX support futures
-
- op := cond.Op
- if !ins.Branch {
- op = (invertToken(op))
- }
-
- k, ok := (*ops[1]).(*ssa.Const)
- // XXX investigate in what cases this wouldn't be a Const
- //
- // XXX what if left and right are swapped?
- if !ok {
- return nil
- }
-
- call, ok := (*ops[0]).(*ssa.Call)
- if !ok {
- return nil
- }
- builtin, ok := call.Common().Value.(*ssa.Builtin)
- if !ok {
- return nil
- }
- if builtin.Name() != "len" {
- return nil
- }
- callops := call.Operands(nil)
-
- v := ConstantToZ(k.Value)
- c := NewSliceIntersectionConstraint(*callops[1], IntInterval{}, ins).(*SliceIntersectionConstraint)
- switch op {
- case token.EQL:
- c.I = NewIntInterval(v, v)
- case token.GTR, token.GEQ:
- off := int64(0)
- if cond.Op == token.GTR {
- off = 1
- }
- c.I = NewIntInterval(
- v.Add(NewZ(off)),
- PInfinity,
- )
- case token.LSS, token.LEQ:
- off := int64(0)
- if cond.Op == token.LSS {
- off = -1
- }
- c.I = NewIntInterval(
- NInfinity,
- v.Add(NewZ(off)),
- )
- default:
- return nil
- }
- return c
-}
-
-func BuildGraph(f *ssa.Function) *Graph {
- g := &Graph{
- Vertices: map[interface{}]*Vertex{},
- ranges: Ranges{},
- }
-
- var cs []Constraint
-
- ops := make([]*ssa.Value, 16)
- seen := map[ssa.Value]bool{}
- for _, block := range f.Blocks {
- for _, ins := range block.Instrs {
- ops = ins.Operands(ops[:0])
- for _, op := range ops {
- if c, ok := (*op).(*ssa.Const); ok {
- if seen[c] {
- continue
- }
- seen[c] = true
- if c.Value == nil {
- switch c.Type().Underlying().(type) {
- case *types.Slice:
- cs = append(cs, NewSliceIntervalConstraint(NewIntInterval(NewZ(0), NewZ(0)), c))
- }
- continue
- }
- switch c.Value.Kind() {
- case constant.Int:
- v := ConstantToZ(c.Value)
- cs = append(cs, NewIntIntervalConstraint(NewIntInterval(v, v), c))
- case constant.String:
- s := constant.StringVal(c.Value)
- n := NewZ(int64(len(s)))
- cs = append(cs, NewStringIntervalConstraint(NewIntInterval(n, n), c))
- }
- }
- }
- }
- }
- for _, block := range f.Blocks {
- for _, ins := range block.Instrs {
- switch ins := ins.(type) {
- case *ssa.Convert:
- switch v := ins.Type().Underlying().(type) {
- case *types.Basic:
- if (v.Info() & types.IsInteger) == 0 {
- continue
- }
- cs = append(cs, NewIntConversionConstraint(ins.X, ins))
- }
- case *ssa.Call:
- if static := ins.Common().StaticCallee(); static != nil {
- if fn, ok := static.Object().(*types.Func); ok {
- switch fn.FullName() {
- case "bytes.Index", "bytes.IndexAny", "bytes.IndexByte",
- "bytes.IndexFunc", "bytes.IndexRune", "bytes.LastIndex",
- "bytes.LastIndexAny", "bytes.LastIndexByte", "bytes.LastIndexFunc",
- "strings.Index", "strings.IndexAny", "strings.IndexByte",
- "strings.IndexFunc", "strings.IndexRune", "strings.LastIndex",
- "strings.LastIndexAny", "strings.LastIndexByte", "strings.LastIndexFunc":
- // TODO(dh): instead of limiting by +∞,
- // limit by the upper bound of the passed
- // string
- cs = append(cs, NewIntIntervalConstraint(NewIntInterval(NewZ(-1), PInfinity), ins))
- case "bytes.Title", "bytes.ToLower", "bytes.ToTitle", "bytes.ToUpper",
- "strings.Title", "strings.ToLower", "strings.ToTitle", "strings.ToUpper":
- cs = append(cs, NewCopyConstraint(ins.Common().Args[0], ins))
- case "bytes.ToLowerSpecial", "bytes.ToTitleSpecial", "bytes.ToUpperSpecial",
- "strings.ToLowerSpecial", "strings.ToTitleSpecial", "strings.ToUpperSpecial":
- cs = append(cs, NewCopyConstraint(ins.Common().Args[1], ins))
- case "bytes.Compare", "strings.Compare":
- cs = append(cs, NewIntIntervalConstraint(NewIntInterval(NewZ(-1), NewZ(1)), ins))
- case "bytes.Count", "strings.Count":
- // TODO(dh): instead of limiting by +∞,
- // limit by the upper bound of the passed
- // string.
- cs = append(cs, NewIntIntervalConstraint(NewIntInterval(NewZ(0), PInfinity), ins))
- case "bytes.Map", "bytes.TrimFunc", "bytes.TrimLeft", "bytes.TrimLeftFunc",
- "bytes.TrimRight", "bytes.TrimRightFunc", "bytes.TrimSpace",
- "strings.Map", "strings.TrimFunc", "strings.TrimLeft", "strings.TrimLeftFunc",
- "strings.TrimRight", "strings.TrimRightFunc", "strings.TrimSpace":
- // TODO(dh): lower = 0, upper = upper of passed string
- case "bytes.TrimPrefix", "bytes.TrimSuffix",
- "strings.TrimPrefix", "strings.TrimSuffix":
- // TODO(dh) range between "unmodified" and len(cutset) removed
- case "(*bytes.Buffer).Cap", "(*bytes.Buffer).Len", "(*bytes.Reader).Len", "(*bytes.Reader).Size":
- cs = append(cs, NewIntIntervalConstraint(NewIntInterval(NewZ(0), PInfinity), ins))
- }
- }
- }
- builtin, ok := ins.Common().Value.(*ssa.Builtin)
- ops := ins.Operands(nil)
- if !ok {
- continue
- }
- switch builtin.Name() {
- case "len":
- switch op1 := (*ops[1]).Type().Underlying().(type) {
- case *types.Basic:
- if op1.Kind() == types.String || op1.Kind() == types.UntypedString {
- cs = append(cs, NewStringLengthConstraint(*ops[1], ins))
- }
- case *types.Slice:
- cs = append(cs, NewSliceLengthConstraint(*ops[1], ins))
- }
-
- case "append":
- cs = append(cs, NewSliceAppendConstraint(ins.Common().Args[0], ins.Common().Args[1], ins))
- }
- case *ssa.BinOp:
- ops := ins.Operands(nil)
- basic, ok := (*ops[0]).Type().Underlying().(*types.Basic)
- if !ok {
- continue
- }
- switch basic.Kind() {
- case types.Int, types.Int8, types.Int16, types.Int32, types.Int64,
- types.Uint, types.Uint8, types.Uint16, types.Uint32, types.Uint64, types.UntypedInt:
- fns := map[token.Token]func(ssa.Value, ssa.Value, ssa.Value) Constraint{
- token.ADD: NewIntAddConstraint,
- token.SUB: NewIntSubConstraint,
- token.MUL: NewIntMulConstraint,
- // XXX support QUO, REM, SHL, SHR
- }
- fn, ok := fns[ins.Op]
- if ok {
- cs = append(cs, fn(*ops[0], *ops[1], ins))
- }
- case types.String, types.UntypedString:
- if ins.Op == token.ADD {
- cs = append(cs, NewStringConcatConstraint(*ops[0], *ops[1], ins))
- }
- }
- case *ssa.Slice:
- typ := ins.X.Type().Underlying()
- switch typ := typ.(type) {
- case *types.Basic:
- cs = append(cs, NewStringSliceConstraint(ins.X, ins.Low, ins.High, ins))
- case *types.Slice:
- cs = append(cs, NewSliceSliceConstraint(ins.X, ins.Low, ins.High, ins))
- case *types.Array:
- cs = append(cs, NewArraySliceConstraint(ins.X, ins.Low, ins.High, ins))
- case *types.Pointer:
- if _, ok := typ.Elem().(*types.Array); !ok {
- continue
- }
- cs = append(cs, NewArraySliceConstraint(ins.X, ins.Low, ins.High, ins))
- }
- case *ssa.Phi:
- if !isSupportedType(ins.Type()) {
- continue
- }
- ops := ins.Operands(nil)
- dops := make([]ssa.Value, len(ops))
- for i, op := range ops {
- dops[i] = *op
- }
- cs = append(cs, NewPhiConstraint(dops, ins))
- case *ssa.Sigma:
- pred := ins.Block().Preds[0]
- instrs := pred.Instrs
- cond, ok := instrs[len(instrs)-1].(*ssa.If).Cond.(*ssa.BinOp)
- ops := cond.Operands(nil)
- if !ok {
- continue
- }
- switch typ := ins.Type().Underlying().(type) {
- case *types.Basic:
- var c Constraint
- switch typ.Kind() {
- case types.Int, types.Int8, types.Int16, types.Int32, types.Int64,
- types.Uint, types.Uint8, types.Uint16, types.Uint32, types.Uint64, types.UntypedInt:
- c = sigmaInteger(g, ins, cond, ops)
- case types.String, types.UntypedString:
- c = sigmaString(g, ins, cond, ops)
- }
- if c != nil {
- cs = append(cs, c)
- }
- case *types.Slice:
- c := sigmaSlice(g, ins, cond, ops)
- if c != nil {
- cs = append(cs, c)
- }
- default:
- //log.Printf("unsupported sigma type %T", typ) // XXX
- }
- case *ssa.MakeChan:
- cs = append(cs, NewMakeChannelConstraint(ins.Size, ins))
- case *ssa.MakeSlice:
- cs = append(cs, NewMakeSliceConstraint(ins.Len, ins))
- case *ssa.ChangeType:
- switch ins.X.Type().Underlying().(type) {
- case *types.Chan:
- cs = append(cs, NewChannelChangeTypeConstraint(ins.X, ins))
- }
- }
- }
- }
-
- for _, c := range cs {
- if c == nil {
- panic("nil constraint")
- }
- // If V is used in constraint C, then we create an edge V->C
- for _, op := range c.Operands() {
- g.AddEdge(op, c, false)
- }
- if c, ok := c.(Future); ok {
- for _, op := range c.Futures() {
- g.AddEdge(op, c, true)
- }
- }
- // If constraint C defines variable V, then we create an edge
- // C->V
- g.AddEdge(c, c.Y(), false)
- }
-
- g.FindSCCs()
- g.sccEdges = make([][]Edge, len(g.SCCs))
- g.futures = make([][]Future, len(g.SCCs))
- for _, e := range g.Edges {
- g.sccEdges[e.From.SCC] = append(g.sccEdges[e.From.SCC], e)
- if !e.control {
- continue
- }
- if c, ok := e.To.Value.(Future); ok {
- g.futures[e.From.SCC] = append(g.futures[e.From.SCC], c)
- }
- }
- return g
-}
-
-func (g *Graph) Solve() Ranges {
- var consts []Z
- off := NewZ(1)
- for _, n := range g.Vertices {
- if c, ok := n.Value.(*ssa.Const); ok {
- basic, ok := c.Type().Underlying().(*types.Basic)
- if !ok {
- continue
- }
- if (basic.Info() & types.IsInteger) != 0 {
- z := ConstantToZ(c.Value)
- consts = append(consts, z)
- consts = append(consts, z.Add(off))
- consts = append(consts, z.Sub(off))
- }
- }
-
- }
- sort.Sort(Zs(consts))
-
- for scc, vertices := range g.SCCs {
- n := 0
- n = len(vertices)
- if n == 1 {
- g.resolveFutures(scc)
- v := vertices[0]
- if v, ok := v.Value.(ssa.Value); ok {
- switch typ := v.Type().Underlying().(type) {
- case *types.Basic:
- switch typ.Kind() {
- case types.String, types.UntypedString:
- if !g.Range(v).(StringInterval).IsKnown() {
- g.SetRange(v, StringInterval{NewIntInterval(NewZ(0), PInfinity)})
- }
- default:
- if !g.Range(v).(IntInterval).IsKnown() {
- g.SetRange(v, InfinityFor(v))
- }
- }
- case *types.Chan:
- if !g.Range(v).(ChannelInterval).IsKnown() {
- g.SetRange(v, ChannelInterval{NewIntInterval(NewZ(0), PInfinity)})
- }
- case *types.Slice:
- if !g.Range(v).(SliceInterval).IsKnown() {
- g.SetRange(v, SliceInterval{NewIntInterval(NewZ(0), PInfinity)})
- }
- }
- }
- if c, ok := v.Value.(Constraint); ok {
- g.SetRange(c.Y(), c.Eval(g))
- }
- } else {
- uses := g.uses(scc)
- entries := g.entries(scc)
- for len(entries) > 0 {
- v := entries[len(entries)-1]
- entries = entries[:len(entries)-1]
- for _, use := range uses[v] {
- if g.widen(use, consts) {
- entries = append(entries, use.Y())
- }
- }
- }
-
- g.resolveFutures(scc)
-
- // XXX this seems to be necessary, but shouldn't be.
- // removing it leads to nil pointer derefs; investigate
- // where we're not setting values correctly.
- for _, n := range vertices {
- if v, ok := n.Value.(ssa.Value); ok {
- i, ok := g.Range(v).(IntInterval)
- if !ok {
- continue
- }
- if !i.IsKnown() {
- g.SetRange(v, InfinityFor(v))
- }
- }
- }
-
- actives := g.actives(scc)
- for len(actives) > 0 {
- v := actives[len(actives)-1]
- actives = actives[:len(actives)-1]
- for _, use := range uses[v] {
- if g.narrow(use) {
- actives = append(actives, use.Y())
- }
- }
- }
- }
- // propagate scc
- for _, edge := range g.sccEdges[scc] {
- if edge.control {
- continue
- }
- if edge.From.SCC == edge.To.SCC {
- continue
- }
- if c, ok := edge.To.Value.(Constraint); ok {
- g.SetRange(c.Y(), c.Eval(g))
- }
- if c, ok := edge.To.Value.(Future); ok {
- if !c.IsKnown() {
- c.MarkUnresolved()
- }
- }
- }
- }
-
- for v, r := range g.ranges {
- i, ok := r.(IntInterval)
- if !ok {
- continue
- }
- if (v.Type().Underlying().(*types.Basic).Info() & types.IsUnsigned) == 0 {
- if i.Upper != PInfinity {
- s := &types.StdSizes{
- // XXX is it okay to assume the largest word size, or do we
- // need to be platform specific?
- WordSize: 8,
- MaxAlign: 1,
- }
- bits := (s.Sizeof(v.Type()) * 8) - 1
- n := big.NewInt(1)
- n = n.Lsh(n, uint(bits))
- upper, lower := &big.Int{}, &big.Int{}
- upper.Sub(n, big.NewInt(1))
- lower.Neg(n)
-
- if i.Upper.Cmp(NewBigZ(upper)) == 1 {
- i = NewIntInterval(NInfinity, PInfinity)
- } else if i.Lower.Cmp(NewBigZ(lower)) == -1 {
- i = NewIntInterval(NInfinity, PInfinity)
- }
- }
- }
-
- g.ranges[v] = i
- }
-
- return g.ranges
-}
-
-func VertexString(v *Vertex) string {
- switch v := v.Value.(type) {
- case Constraint:
- return v.String()
- case ssa.Value:
- return v.Name()
- case nil:
- return "BUG: nil vertex value"
- default:
- panic(fmt.Sprintf("unexpected type %T", v))
- }
-}
-
-type Vertex struct {
- Value interface{} // one of Constraint or ssa.Value
- SCC int
- index int
- lowlink int
- stack bool
-
- Succs []Edge
-}
-
-type Ranges map[ssa.Value]Range
-
-func (r Ranges) Get(x ssa.Value) Range {
- if x == nil {
- return nil
- }
- i, ok := r[x]
- if !ok {
- switch x := x.Type().Underlying().(type) {
- case *types.Basic:
- switch x.Kind() {
- case types.String, types.UntypedString:
- return StringInterval{}
- default:
- return IntInterval{}
- }
- case *types.Chan:
- return ChannelInterval{}
- case *types.Slice:
- return SliceInterval{}
- }
- }
- return i
-}
-
-type Graph struct {
- Vertices map[interface{}]*Vertex
- Edges []Edge
- SCCs [][]*Vertex
- ranges Ranges
-
- // map SCCs to futures
- futures [][]Future
- // map SCCs to edges
- sccEdges [][]Edge
-}
-
-func (g Graph) Graphviz() string {
- var lines []string
- lines = append(lines, "digraph{")
- ids := map[interface{}]int{}
- i := 1
- for _, v := range g.Vertices {
- ids[v] = i
- shape := "box"
- if _, ok := v.Value.(ssa.Value); ok {
- shape = "oval"
- }
- lines = append(lines, fmt.Sprintf(`n%d [shape="%s", label=%q, colorscheme=spectral11, style="filled", fillcolor="%d"]`,
- i, shape, VertexString(v), (v.SCC%11)+1))
- i++
- }
- for _, e := range g.Edges {
- style := "solid"
- if e.control {
- style = "dashed"
- }
- lines = append(lines, fmt.Sprintf(`n%d -> n%d [style="%s"]`, ids[e.From], ids[e.To], style))
- }
- lines = append(lines, "}")
- return strings.Join(lines, "\n")
-}
-
-func (g *Graph) SetRange(x ssa.Value, r Range) {
- g.ranges[x] = r
-}
-
-func (g *Graph) Range(x ssa.Value) Range {
- return g.ranges.Get(x)
-}
-
-func (g *Graph) widen(c Constraint, consts []Z) bool {
- setRange := func(i Range) {
- g.SetRange(c.Y(), i)
- }
- widenIntInterval := func(oi, ni IntInterval) (IntInterval, bool) {
- if !ni.IsKnown() {
- return oi, false
- }
- nlc := NInfinity
- nuc := PInfinity
- for _, co := range consts {
- if co.Cmp(ni.Lower) <= 0 {
- nlc = co
- break
- }
- }
- for _, co := range consts {
- if co.Cmp(ni.Upper) >= 0 {
- nuc = co
- break
- }
- }
-
- if !oi.IsKnown() {
- return ni, true
- }
- if ni.Lower.Cmp(oi.Lower) == -1 && ni.Upper.Cmp(oi.Upper) == 1 {
- return NewIntInterval(nlc, nuc), true
- }
- if ni.Lower.Cmp(oi.Lower) == -1 {
- return NewIntInterval(nlc, oi.Upper), true
- }
- if ni.Upper.Cmp(oi.Upper) == 1 {
- return NewIntInterval(oi.Lower, nuc), true
- }
- return oi, false
- }
- switch oi := g.Range(c.Y()).(type) {
- case IntInterval:
- ni := c.Eval(g).(IntInterval)
- si, changed := widenIntInterval(oi, ni)
- if changed {
- setRange(si)
- return true
- }
- return false
- case StringInterval:
- ni := c.Eval(g).(StringInterval)
- si, changed := widenIntInterval(oi.Length, ni.Length)
- if changed {
- setRange(StringInterval{si})
- return true
- }
- return false
- case SliceInterval:
- ni := c.Eval(g).(SliceInterval)
- si, changed := widenIntInterval(oi.Length, ni.Length)
- if changed {
- setRange(SliceInterval{si})
- return true
- }
- return false
- default:
- return false
- }
-}
-
-func (g *Graph) narrow(c Constraint) bool {
- narrowIntInterval := func(oi, ni IntInterval) (IntInterval, bool) {
- oLower := oi.Lower
- oUpper := oi.Upper
- nLower := ni.Lower
- nUpper := ni.Upper
-
- if oLower == NInfinity && nLower != NInfinity {
- return NewIntInterval(nLower, oUpper), true
- }
- if oUpper == PInfinity && nUpper != PInfinity {
- return NewIntInterval(oLower, nUpper), true
- }
- if oLower.Cmp(nLower) == 1 {
- return NewIntInterval(nLower, oUpper), true
- }
- if oUpper.Cmp(nUpper) == -1 {
- return NewIntInterval(oLower, nUpper), true
- }
- return oi, false
- }
- switch oi := g.Range(c.Y()).(type) {
- case IntInterval:
- ni := c.Eval(g).(IntInterval)
- si, changed := narrowIntInterval(oi, ni)
- if changed {
- g.SetRange(c.Y(), si)
- return true
- }
- return false
- case StringInterval:
- ni := c.Eval(g).(StringInterval)
- si, changed := narrowIntInterval(oi.Length, ni.Length)
- if changed {
- g.SetRange(c.Y(), StringInterval{si})
- return true
- }
- return false
- case SliceInterval:
- ni := c.Eval(g).(SliceInterval)
- si, changed := narrowIntInterval(oi.Length, ni.Length)
- if changed {
- g.SetRange(c.Y(), SliceInterval{si})
- return true
- }
- return false
- default:
- return false
- }
-}
-
-func (g *Graph) resolveFutures(scc int) {
- for _, c := range g.futures[scc] {
- c.Resolve()
- }
-}
-
-func (g *Graph) entries(scc int) []ssa.Value {
- var entries []ssa.Value
- for _, n := range g.Vertices {
- if n.SCC != scc {
- continue
- }
- if v, ok := n.Value.(ssa.Value); ok {
- // XXX avoid quadratic runtime
- //
- // XXX I cannot think of any code where the future and its
- // variables aren't in the same SCC, in which case this
- // code isn't very useful (the variables won't be resolved
- // yet). Before we have a cross-SCC example, however, we
- // can't really verify that this code is working
- // correctly, or indeed doing anything useful.
- for _, on := range g.Vertices {
- if c, ok := on.Value.(Future); ok {
- if c.Y() == v {
- if !c.IsResolved() {
- g.SetRange(c.Y(), c.Eval(g))
- c.MarkResolved()
- }
- break
- }
- }
- }
- if g.Range(v).IsKnown() {
- entries = append(entries, v)
- }
- }
- }
- return entries
-}
-
-func (g *Graph) uses(scc int) map[ssa.Value][]Constraint {
- m := map[ssa.Value][]Constraint{}
- for _, e := range g.sccEdges[scc] {
- if e.control {
- continue
- }
- if v, ok := e.From.Value.(ssa.Value); ok {
- c := e.To.Value.(Constraint)
- sink := c.Y()
- if g.Vertices[sink].SCC == scc {
- m[v] = append(m[v], c)
- }
- }
- }
- return m
-}
-
-func (g *Graph) actives(scc int) []ssa.Value {
- var actives []ssa.Value
- for _, n := range g.Vertices {
- if n.SCC != scc {
- continue
- }
- if v, ok := n.Value.(ssa.Value); ok {
- if _, ok := v.(*ssa.Const); !ok {
- actives = append(actives, v)
- }
- }
- }
- return actives
-}
-
-func (g *Graph) AddEdge(from, to interface{}, ctrl bool) {
- vf, ok := g.Vertices[from]
- if !ok {
- vf = &Vertex{Value: from}
- g.Vertices[from] = vf
- }
- vt, ok := g.Vertices[to]
- if !ok {
- vt = &Vertex{Value: to}
- g.Vertices[to] = vt
- }
- e := Edge{From: vf, To: vt, control: ctrl}
- g.Edges = append(g.Edges, e)
- vf.Succs = append(vf.Succs, e)
-}
-
-type Edge struct {
- From, To *Vertex
- control bool
-}
-
-func (e Edge) String() string {
- return fmt.Sprintf("%s -> %s", VertexString(e.From), VertexString(e.To))
-}
-
-func (g *Graph) FindSCCs() {
- // use Tarjan to find the SCCs
-
- index := 1
- var s []*Vertex
-
- scc := 0
- var strongconnect func(v *Vertex)
- strongconnect = func(v *Vertex) {
- // set the depth index for v to the smallest unused index
- v.index = index
- v.lowlink = index
- index++
- s = append(s, v)
- v.stack = true
-
- for _, e := range v.Succs {
- w := e.To
- if w.index == 0 {
- // successor w has not yet been visited; recurse on it
- strongconnect(w)
- if w.lowlink < v.lowlink {
- v.lowlink = w.lowlink
- }
- } else if w.stack {
- // successor w is in stack s and hence in the current scc
- if w.index < v.lowlink {
- v.lowlink = w.index
- }
- }
- }
-
- if v.lowlink == v.index {
- for {
- w := s[len(s)-1]
- s = s[:len(s)-1]
- w.stack = false
- w.SCC = scc
- if w == v {
- break
- }
- }
- scc++
- }
- }
- for _, v := range g.Vertices {
- if v.index == 0 {
- strongconnect(v)
- }
- }
-
- g.SCCs = make([][]*Vertex, scc)
- for _, n := range g.Vertices {
- n.SCC = scc - n.SCC - 1
- g.SCCs[n.SCC] = append(g.SCCs[n.SCC], n)
- }
-}
-
-func invertToken(tok token.Token) token.Token {
- switch tok {
- case token.LSS:
- return token.GEQ
- case token.GTR:
- return token.LEQ
- case token.EQL:
- return token.NEQ
- case token.NEQ:
- return token.EQL
- case token.GEQ:
- return token.LSS
- case token.LEQ:
- return token.GTR
- default:
- panic(fmt.Sprintf("unsupported token %s", tok))
- }
-}
-
-func flipToken(tok token.Token) token.Token {
- switch tok {
- case token.LSS:
- return token.GTR
- case token.GTR:
- return token.LSS
- case token.EQL:
- return token.EQL
- case token.NEQ:
- return token.NEQ
- case token.GEQ:
- return token.LEQ
- case token.LEQ:
- return token.GEQ
- default:
- panic(fmt.Sprintf("unsupported token %s", tok))
- }
-}
-
-type CopyConstraint struct {
- aConstraint
- X ssa.Value
-}
-
-func (c *CopyConstraint) String() string {
- return fmt.Sprintf("%s = copy(%s)", c.Y().Name(), c.X.Name())
-}
-
-func (c *CopyConstraint) Eval(g *Graph) Range {
- return g.Range(c.X)
-}
-
-func (c *CopyConstraint) Operands() []ssa.Value {
- return []ssa.Value{c.X}
-}
-
-func NewCopyConstraint(x, y ssa.Value) Constraint {
- return &CopyConstraint{
- aConstraint: aConstraint{
- y: y,
- },
- X: x,
- }
-}