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