slicesbackward.go

     1  // Copyright 2025 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 modernize
     6  
     7  import (
     8  	"fmt"
     9  	"go/ast"
    10  	"go/token"
    11  	"go/types"
    12  	"strings"
    13  
    14  	"golang.org/x/tools/go/analysis"
    15  	"golang.org/x/tools/go/analysis/passes/inspect"
    16  	"golang.org/x/tools/go/ast/edge"
    17  	"golang.org/x/tools/go/types/typeutil"
    18  	"golang.org/x/tools/internal/analysis/analyzerutil"
    19  	typeindexanalyzer "golang.org/x/tools/internal/analysis/typeindex"
    20  	"golang.org/x/tools/internal/astutil"
    21  	"golang.org/x/tools/internal/refactor"
    22  	"golang.org/x/tools/internal/typesinternal"
    23  	"golang.org/x/tools/internal/typesinternal/typeindex"
    24  	"golang.org/x/tools/internal/versions"
    25  )
    26  
    27  // TODO(adonovan): needs a proposal for a public symbol.
    28  var slicesBackwardAnalyzer = &analysis.Analyzer{
    29  	Name: "slicesbackward",
    30  	Doc:  analyzerutil.MustExtractDoc(doc, "slicesbackward"),
    31  	Requires: []*analysis.Analyzer{
    32  		inspect.Analyzer,
    33  		typeindexanalyzer.Analyzer,
    34  	},
    35  	Run: slicesbackward,
    36  	URL: "https://pkg.go.dev/golang.org/x/tools/go/analysis/passes/modernize#hdr-Analyzer_slicesbackward",
    37  }
    38  
    39  // slicesbackward offers a fix to replace a manually-written backward loop:
    40  //
    41  //	for i := len(s) - 1; i >= 0; i-- {
    42  //	    use(s[i])
    43  //	}
    44  //
    45  // with a range loop using slices.Backward (added in Go 1.23):
    46  //
    47  //	for _, v := range slices.Backward(s) {
    48  //	    use(v)
    49  //	}
    50  //
    51  // If the loop index is needed beyond just indexing into the slice, both
    52  // the index and value variables are kept:
    53  //
    54  //	for i, v := range slices.Backward(s) { ... }
    55  func slicesbackward(pass *analysis.Pass) (any, error) {
    56  	// Skip packages that are in the slices stdlib dependency tree to
    57  	// avoid import cycles.
    58  	if within(pass, "slices") {
    59  		return nil, nil
    60  	}
    61  
    62  	var (
    63  		info  = pass.TypesInfo
    64  		index = pass.ResultOf[typeindexanalyzer.Analyzer].(*typeindex.Index)
    65  	)
    66  
    67  	for curFile := range filesUsingGoVersion(pass, versions.Go1_23) {
    68  		file := curFile.Node().(*ast.File)
    69  
    70  	nextLoop:
    71  		for curLoop := range curFile.Preorder((*ast.ForStmt)(nil)) {
    72  			loop := curLoop.Node().(*ast.ForStmt)
    73  
    74  			// Match init:  i := len(s) - 1   or   i = len(s) - 1
    75  			init, ok := loop.Init.(*ast.AssignStmt)
    76  			if !ok || !isSimpleAssign(init) {
    77  				continue
    78  			}
    79  			indexIdent, ok := init.Lhs[0].(*ast.Ident)
    80  			if !ok {
    81  				continue
    82  			}
    83  			indexObj := info.ObjectOf(indexIdent).(*types.Var)
    84  
    85  			// RHS must be len(s) - 1.
    86  			binRhs, ok := init.Rhs[0].(*ast.BinaryExpr)
    87  			if !ok || binRhs.Op != token.SUB {
    88  				continue
    89  			}
    90  			if !isIntLiteral(info, binRhs.Y, 1) {
    91  				continue
    92  			}
    93  			lenCall, ok := binRhs.X.(*ast.CallExpr)
    94  			if !ok || typeutil.Callee(info, lenCall) != builtinLen {
    95  				continue
    96  			}
    97  			if len(lenCall.Args) != 1 {
    98  				continue
    99  			}
   100  			sliceExpr := lenCall.Args[0]
   101  			if _, ok := info.TypeOf(sliceExpr).Underlying().(*types.Slice); !ok {
   102  				continue
   103  			}
   104  
   105  			// Match cond:  i >= 0
   106  			cond, ok := loop.Cond.(*ast.BinaryExpr)
   107  			if !ok || cond.Op != token.GEQ {
   108  				continue
   109  			}
   110  			if !astutil.EqualSyntax(cond.X, indexIdent) {
   111  				continue
   112  			}
   113  			if !isZeroIntConst(info, cond.Y) {
   114  				continue
   115  			}
   116  
   117  			// Match post:  i--
   118  			dec, ok := loop.Post.(*ast.IncDecStmt)
   119  			if !ok || dec.Tok != token.DEC {
   120  				continue
   121  			}
   122  			if !astutil.EqualSyntax(dec.X, indexIdent) {
   123  				continue
   124  			}
   125  
   126  			// Check that i is not used as an lvalue in the loop body.
   127  			// If init is = (not :=), i is a pre-existing variable; also
   128  			// check that it is not used as an lvalue outside the loop
   129  			// (e.g. &i before the loop).
   130  			bodyCur := curLoop.Child(loop.Body)
   131  			for curUse := range index.Uses(indexObj) {
   132  				if !typesinternal.IsAssignedOrAddressTaken(info, curUse) {
   133  					continue
   134  				}
   135  				if bodyCur.Contains(curUse) {
   136  					continue nextLoop // i is mutated in loop body
   137  				}
   138  				if init.Tok == token.ASSIGN && !curLoop.Contains(curUse) {
   139  					continue nextLoop // pre-existing i is an lvalue outside the loop
   140  				}
   141  			}
   142  
   143  			// Find all uses of i in the loop body. Classify as:
   144  			//   s[i] — pure element accesses that can be replaced by the value var
   145  			//   other — index used for non-indexing purposes
   146  			var (
   147  				// First assignment in the loop body of the form "name := s[i]"; or nil.
   148  				firstSliceIdxAssign *ast.AssignStmt
   149  				// List of s[i] expressions to replace by the value var (excludes firstSliceIdxAssign, which will be entirely removed).
   150  				sliceIdxsReplace []*ast.IndexExpr
   151  				// Total count of s[i] usages.
   152  				sliceIdxs int
   153  				// Non-indexing uses of i.
   154  				otherUses int
   155  			)
   156  			for curUse := range index.Uses(indexObj) {
   157  				if !bodyCur.Contains(curUse) {
   158  					continue
   159  				}
   160  				// Is i in the Index position of an s[i] expression?
   161  				// If so, we also need to check whether s[i] is an lvalue. If we're
   162  				// mutating the slice or taking an element's address, a fix will not
   163  				// be offered.
   164  				// Modernization to "for _, v := range slices.Backward(s)" is unsafe if
   165  				// s[i] is mutated or address-taken (since v would be a local copy of
   166  				// the element so s[i] wouldn't get mutated).
   167  				// We don't need to worry about indirect selections (e.g. s[i].n++ where
   168  				// s is []*item) or indirect references like indexing a slice of slices.
   169  				if curUse.ParentEdgeKind() == edge.IndexExpr_Index {
   170  					curIdx := curUse.Parent()
   171  					if typesinternal.IsAssignedOrAddressTaken(info, curIdx) {
   172  						continue nextLoop
   173  					}
   174  					idxExpr := curIdx.Node().(*ast.IndexExpr)
   175  					if astutil.EqualSyntax(idxExpr.X, sliceExpr) {
   176  						sliceIdxs++
   177  						// If the current statement is the first in the body of the form
   178  						// "name := s[i]", save it so we can use "name" as the value
   179  						// variable in slices.Backward. We can also remove the entire assign
   180  						// statement.
   181  						if firstSliceIdxAssign == nil && curIdx.ParentEdgeKind() == edge.AssignStmt_Rhs {
   182  							assignStmt := curIdx.Parent().Node().(*ast.AssignStmt)
   183  							if len(assignStmt.Lhs) == 1 && assignStmt.Tok == token.DEFINE {
   184  								// The condition above implies that assignStmt.Lhs[0] is a valid
   185  								// identifier.
   186  								firstSliceIdxAssign = assignStmt
   187  								// We don't need to replace the index expr with the value variable
   188  								// name if we are going to remove the entire assignment.
   189  								continue
   190  							}
   191  						}
   192  						sliceIdxsReplace = append(sliceIdxsReplace, idxExpr)
   193  						continue
   194  					}
   195  				}
   196  				otherUses++
   197  			}
   198  
   199  			// Build the suggested fix.
   200  			//
   201  			// for i := len(s) - 1;     i >= 0; i-- { ... s[i] ... }
   202  			//     --------------------------------       ----
   203  			// for _, v := range slices.Backward(s) { ... v    ... }
   204  			sliceStr := astutil.Format(pass.Fset, sliceExpr)
   205  			prefix, edits := refactor.AddImport(info, file, "slices", "slices", "Backward", loop.Pos())
   206  			elemName := chooseValueName(firstSliceIdxAssign, sliceStr)
   207  			elemName = freshName(info, index, info.Scopes[loop], loop.Pos(), bodyCur, bodyCur, token.NoPos, elemName)
   208  
   209  			// Replace each s[i] with elemName (except for in the statement of the
   210  			// form "name := s[i]" where we might have gotten elemName from - we will
   211  			// delete this entire statement instead).
   212  			for _, sx := range sliceIdxsReplace {
   213  				edits = append(edits, analysis.TextEdit{
   214  					Pos:     sx.Pos(),
   215  					End:     sx.End(),
   216  					NewText: []byte(elemName),
   217  				})
   218  			}
   219  
   220  			if firstSliceIdxAssign != nil {
   221  				edits = append(edits, analysis.TextEdit{
   222  					Pos: firstSliceIdxAssign.Pos(),
   223  					End: firstSliceIdxAssign.End(),
   224  				})
   225  			}
   226  
   227  			// Replace the loop header with a range over slices.Backward. In
   228  			// well-typed code, at least one of the index or value variables must be
   229  			// referenced inside the loop body (otherUses + sliceIndexes > 0).
   230  			var vars string
   231  			if otherUses == 0 { // sliceIdxs > 0
   232  				// All uses of i are s[i]; drop the index variable.
   233  				vars = fmt.Sprintf("_, %s", elemName)
   234  			} else if sliceIdxs == 0 { // otherUses > 0
   235  				// Index i is not used in any s[i] expressions; drop the value variable.
   236  				vars = indexIdent.Name
   237  			} else { // otherUses > 0 && sliceIdxs > 0, keep both variables.
   238  				vars = fmt.Sprintf("%s, %s", indexIdent.Name, elemName)
   239  			}
   240  			header := fmt.Sprintf("%s := range %sBackward(%s)", vars, prefix, sliceStr)
   241  			edits = append(edits, analysis.TextEdit{
   242  				Pos:     loop.Init.Pos(),
   243  				End:     loop.Post.End(),
   244  				NewText: []byte(header),
   245  			})
   246  
   247  			pass.Report(analysis.Diagnostic{
   248  				Pos:     loop.Init.Pos(),
   249  				End:     loop.Post.End(),
   250  				Message: "backward loop over slice can be modernized using slices.Backward",
   251  				SuggestedFixes: []analysis.SuggestedFix{{
   252  					Message:   fmt.Sprintf("Replace with range slices.Backward(%s)", sliceStr),
   253  					TextEdits: edits,
   254  				}},
   255  			})
   256  		}
   257  	}
   258  	return nil, nil
   259  }
   260  
   261  // chooseValueName uses a heuristic to generate a name for the value variable in
   262  // the call to slices.Backward.
   263  func chooseValueName(assign *ast.AssignStmt, sliceStr string) string {
   264  	if assign != nil {
   265  		return assign.Lhs[0].(*ast.Ident).Name
   266  	}
   267  	// Heuristic: remove plural s suffix from slice var
   268  	// if present, otherwise use first letter.
   269  	if token.IsIdentifier(sliceStr) && len(sliceStr) > 1 {
   270  		if single, ok := strings.CutSuffix(sliceStr, "s"); ok {
   271  			return single
   272  		}
   273  		return sliceStr[:1] // first letter (assuming ASCII)
   274  	}
   275  	return "v"
   276  }
   277
View as plain text