shift.go

     1  // Copyright 2014 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  // Package shift defines an Analyzer that checks for shifts that exceed
     6  // the width of an integer.
     7  package shift
     8  
     9  // TODO(adonovan): integrate with ctrflow (CFG-based) dead code analysis. May
    10  // have impedance mismatch due to its (non-)treatment of constant
    11  // expressions (such as runtime.GOARCH=="386").
    12  
    13  import (
    14  	"go/ast"
    15  	"go/constant"
    16  	"go/token"
    17  	"go/types"
    18  	"math"
    19  
    20  	"golang.org/x/tools/go/analysis"
    21  	"golang.org/x/tools/go/analysis/passes/inspect"
    22  	"golang.org/x/tools/go/analysis/passes/internal/analysisutil"
    23  	"golang.org/x/tools/go/ast/inspector"
    24  	"golang.org/x/tools/internal/aliases"
    25  	"golang.org/x/tools/internal/typeparams"
    26  )
    27  
    28  const Doc = "check for shifts that equal or exceed the width of the integer"
    29  
    30  var Analyzer = &analysis.Analyzer{
    31  	Name:     "shift",
    32  	Doc:      Doc,
    33  	URL:      "https://pkg.go.dev/golang.org/x/tools/go/analysis/passes/shift",
    34  	Requires: []*analysis.Analyzer{inspect.Analyzer},
    35  	Run:      run,
    36  }
    37  
    38  func run(pass *analysis.Pass) (interface{}, error) {
    39  	inspect := pass.ResultOf[inspect.Analyzer].(*inspector.Inspector)
    40  
    41  	// Do a complete pass to compute dead nodes.
    42  	dead := make(map[ast.Node]bool)
    43  	nodeFilter := []ast.Node{
    44  		(*ast.IfStmt)(nil),
    45  		(*ast.SwitchStmt)(nil),
    46  	}
    47  	inspect.Preorder(nodeFilter, func(n ast.Node) {
    48  		// TODO(adonovan): move updateDead into this file.
    49  		updateDead(pass.TypesInfo, dead, n)
    50  	})
    51  
    52  	nodeFilter = []ast.Node{
    53  		(*ast.AssignStmt)(nil),
    54  		(*ast.BinaryExpr)(nil),
    55  	}
    56  	inspect.Preorder(nodeFilter, func(node ast.Node) {
    57  		if dead[node] {
    58  			// Skip shift checks on unreachable nodes.
    59  			return
    60  		}
    61  
    62  		switch node := node.(type) {
    63  		case *ast.BinaryExpr:
    64  			if node.Op == token.SHL || node.Op == token.SHR {
    65  				checkLongShift(pass, node, node.X, node.Y)
    66  			}
    67  		case *ast.AssignStmt:
    68  			if len(node.Lhs) != 1 || len(node.Rhs) != 1 {
    69  				return
    70  			}
    71  			if node.Tok == token.SHL_ASSIGN || node.Tok == token.SHR_ASSIGN {
    72  				checkLongShift(pass, node, node.Lhs[0], node.Rhs[0])
    73  			}
    74  		}
    75  	})
    76  	return nil, nil
    77  }
    78  
    79  // checkLongShift checks if shift or shift-assign operations shift by more than
    80  // the length of the underlying variable.
    81  func checkLongShift(pass *analysis.Pass, node ast.Node, x, y ast.Expr) {
    82  	if pass.TypesInfo.Types[x].Value != nil {
    83  		// Ignore shifts of constants.
    84  		// These are frequently used for bit-twiddling tricks
    85  		// like ^uint(0) >> 63 for 32/64 bit detection and compatibility.
    86  		return
    87  	}
    88  
    89  	v := pass.TypesInfo.Types[y].Value
    90  	if v == nil {
    91  		return
    92  	}
    93  	u := constant.ToInt(v) // either an Int or Unknown
    94  	amt, ok := constant.Int64Val(u)
    95  	if !ok {
    96  		return
    97  	}
    98  	t := pass.TypesInfo.Types[x].Type
    99  	if t == nil {
   100  		return
   101  	}
   102  	var structuralTypes []types.Type
   103  	switch t := aliases.Unalias(t).(type) {
   104  	case *types.TypeParam:
   105  		terms, err := typeparams.StructuralTerms(t)
   106  		if err != nil {
   107  			return // invalid type
   108  		}
   109  		for _, term := range terms {
   110  			structuralTypes = append(structuralTypes, term.Type())
   111  		}
   112  	default:
   113  		structuralTypes = append(structuralTypes, t)
   114  	}
   115  	sizes := make(map[int64]struct{})
   116  	for _, t := range structuralTypes {
   117  		size := 8 * pass.TypesSizes.Sizeof(t)
   118  		sizes[size] = struct{}{}
   119  	}
   120  	minSize := int64(math.MaxInt64)
   121  	for size := range sizes {
   122  		if size < minSize {
   123  			minSize = size
   124  		}
   125  	}
   126  	if amt >= minSize {
   127  		ident := analysisutil.Format(pass.Fset, x)
   128  		qualifier := ""
   129  		if len(sizes) > 1 {
   130  			qualifier = "may be "
   131  		}
   132  		pass.ReportRangef(node, "%s (%s%d bits) too small for shift of %d", ident, qualifier, minSize, amt)
   133  	}
   134  }
   135
View as plain text