free.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 free defines utilities for computing the free variables of
     6  // a syntax tree without type information. This is inherently
     7  // heuristic because of the T{f: x} ambiguity, in which f may or may
     8  // not be a lexical reference depending on whether T is a struct type.
     9  package free
    10  
    11  import (
    12  	"go/ast"
    13  	"go/token"
    14  )
    15  
    16  // Copied, with considerable changes, from go/parser/resolver.go
    17  // at af53bd2c03.
    18  
    19  // Names computes an approximation to the set of free names of the AST
    20  // at node n based solely on syntax.
    21  //
    22  // In the absence of composite literals, the set of free names is exact. Composite
    23  // literals introduce an ambiguity that can only be resolved with type information:
    24  // whether F is a field name or a value in `T{F: ...}`.
    25  // If includeComplitIdents is true, this function conservatively assumes
    26  // T is not a struct type, so freeishNames overapproximates: the resulting
    27  // set may contain spurious entries that are not free lexical references
    28  // but are references to struct fields.
    29  // If includeComplitIdents is false, this function assumes that T *is*
    30  // a struct type, so freeishNames underapproximates: the resulting set
    31  // may omit names that are free lexical references.
    32  //
    33  // TODO(adonovan): includeComplitIdents is a crude hammer: the caller
    34  // may have partial or heuristic information about whether a given T
    35  // is struct type. Replace includeComplitIdents with a hook to query
    36  // the caller.
    37  //
    38  // The code is based on go/parser.resolveFile, but heavily simplified. Crucial
    39  // differences are:
    40  //   - Instead of resolving names to their objects, this function merely records
    41  //     whether they are free.
    42  //   - Labels are ignored: they do not refer to values.
    43  //   - This is never called on ImportSpecs, so the function panics if it sees one.
    44  func Names(n ast.Node, includeComplitIdents bool) map[string]bool {
    45  	v := &freeVisitor{
    46  		free:                 make(map[string]bool),
    47  		includeComplitIdents: includeComplitIdents,
    48  	}
    49  	// Begin with a scope, even though n might not be a form that establishes a scope.
    50  	// For example, n might be:
    51  	//    x := ...
    52  	// Then we need to add the first x to some scope.
    53  	v.openScope()
    54  	ast.Walk(v, n)
    55  	v.closeScope()
    56  	if v.scope != nil {
    57  		panic("unbalanced scopes")
    58  	}
    59  	return v.free
    60  }
    61  
    62  // A freeVisitor holds state for a free-name analysis.
    63  type freeVisitor struct {
    64  	scope                *scope          // the current innermost scope
    65  	free                 map[string]bool // free names seen so far
    66  	includeComplitIdents bool            // include identifier key in composite literals
    67  }
    68  
    69  // scope contains all the names defined in a lexical scope.
    70  // It is like ast.Scope, but without deprecation warnings.
    71  type scope struct {
    72  	names map[string]bool
    73  	outer *scope
    74  }
    75  
    76  func (s *scope) defined(name string) bool {
    77  	for ; s != nil; s = s.outer {
    78  		if s.names[name] {
    79  			return true
    80  		}
    81  	}
    82  	return false
    83  }
    84  
    85  func (v *freeVisitor) Visit(n ast.Node) ast.Visitor {
    86  	switch n := n.(type) {
    87  
    88  	// Expressions.
    89  	case *ast.Ident:
    90  		v.use(n)
    91  
    92  	case *ast.FuncLit:
    93  		v.openScope()
    94  		defer v.closeScope()
    95  		v.walkFuncType(nil, n.Type)
    96  		v.walkBody(n.Body)
    97  
    98  	case *ast.SelectorExpr:
    99  		v.walk(n.X)
   100  		// Skip n.Sel: it cannot be free.
   101  
   102  	case *ast.StructType:
   103  		v.openScope()
   104  		defer v.closeScope()
   105  		v.walkFieldList(n.Fields)
   106  
   107  	case *ast.FuncType:
   108  		v.openScope()
   109  		defer v.closeScope()
   110  		v.walkFuncType(nil, n)
   111  
   112  	case *ast.CompositeLit:
   113  		v.walk(n.Type)
   114  		for _, e := range n.Elts {
   115  			if kv, _ := e.(*ast.KeyValueExpr); kv != nil {
   116  				if ident, _ := kv.Key.(*ast.Ident); ident != nil {
   117  					// It is not possible from syntax alone to know whether
   118  					// an identifier used as a composite literal key is
   119  					// a struct field (if n.Type is a struct) or a value
   120  					// (if n.Type is a map, slice or array).
   121  					if v.includeComplitIdents {
   122  						// Over-approximate by treating both cases as potentially
   123  						// free names.
   124  						v.use(ident)
   125  					} else {
   126  						// Under-approximate by ignoring potentially free names.
   127  					}
   128  				} else {
   129  					v.walk(kv.Key)
   130  				}
   131  				v.walk(kv.Value)
   132  			} else {
   133  				v.walk(e)
   134  			}
   135  		}
   136  
   137  	case *ast.InterfaceType:
   138  		v.openScope()
   139  		defer v.closeScope()
   140  		v.walkFieldList(n.Methods)
   141  
   142  	// Statements
   143  	case *ast.AssignStmt:
   144  		walkSlice(v, n.Rhs)
   145  		if n.Tok == token.DEFINE {
   146  			v.shortVarDecl(n.Lhs)
   147  		} else {
   148  			walkSlice(v, n.Lhs)
   149  		}
   150  
   151  	case *ast.LabeledStmt:
   152  		// Ignore labels.
   153  		v.walk(n.Stmt)
   154  
   155  	case *ast.BranchStmt:
   156  		// Ignore labels.
   157  
   158  	case *ast.BlockStmt:
   159  		v.openScope()
   160  		defer v.closeScope()
   161  		walkSlice(v, n.List)
   162  
   163  	case *ast.IfStmt:
   164  		v.openScope()
   165  		defer v.closeScope()
   166  		v.walk(n.Init)
   167  		v.walk(n.Cond)
   168  		v.walk(n.Body)
   169  		v.walk(n.Else)
   170  
   171  	case *ast.CaseClause:
   172  		walkSlice(v, n.List)
   173  		v.openScope()
   174  		defer v.closeScope()
   175  		walkSlice(v, n.Body)
   176  
   177  	case *ast.SwitchStmt:
   178  		v.openScope()
   179  		defer v.closeScope()
   180  		v.walk(n.Init)
   181  		v.walk(n.Tag)
   182  		v.walkBody(n.Body)
   183  
   184  	case *ast.TypeSwitchStmt:
   185  		v.openScope()
   186  		defer v.closeScope()
   187  		if n.Init != nil {
   188  			v.walk(n.Init)
   189  		}
   190  		v.walk(n.Assign)
   191  		// We can use walkBody here because we don't track label scopes.
   192  		v.walkBody(n.Body)
   193  
   194  	case *ast.CommClause:
   195  		v.openScope()
   196  		defer v.closeScope()
   197  		v.walk(n.Comm)
   198  		walkSlice(v, n.Body)
   199  
   200  	case *ast.SelectStmt:
   201  		v.walkBody(n.Body)
   202  
   203  	case *ast.ForStmt:
   204  		v.openScope()
   205  		defer v.closeScope()
   206  		v.walk(n.Init)
   207  		v.walk(n.Cond)
   208  		v.walk(n.Post)
   209  		v.walk(n.Body)
   210  
   211  	case *ast.RangeStmt:
   212  		v.openScope()
   213  		defer v.closeScope()
   214  		v.walk(n.X)
   215  		var lhs []ast.Expr
   216  		if n.Key != nil {
   217  			lhs = append(lhs, n.Key)
   218  		}
   219  		if n.Value != nil {
   220  			lhs = append(lhs, n.Value)
   221  		}
   222  		if len(lhs) > 0 {
   223  			if n.Tok == token.DEFINE {
   224  				v.shortVarDecl(lhs)
   225  			} else {
   226  				walkSlice(v, lhs)
   227  			}
   228  		}
   229  		v.walk(n.Body)
   230  
   231  	// Declarations
   232  	case *ast.GenDecl:
   233  		switch n.Tok {
   234  		case token.CONST, token.VAR:
   235  			for _, spec := range n.Specs {
   236  				spec := spec.(*ast.ValueSpec)
   237  				walkSlice(v, spec.Values)
   238  				v.walk(spec.Type)
   239  				v.declare(spec.Names...)
   240  			}
   241  
   242  		case token.TYPE:
   243  			for _, spec := range n.Specs {
   244  				spec := spec.(*ast.TypeSpec)
   245  				// Go spec: The scope of a type identifier declared inside a
   246  				// function begins at the identifier in the TypeSpec and ends
   247  				// at the end of the innermost containing block.
   248  				v.declare(spec.Name)
   249  				if spec.TypeParams != nil {
   250  					v.openScope()
   251  					defer v.closeScope()
   252  					v.walkTypeParams(spec.TypeParams)
   253  				}
   254  				v.walk(spec.Type)
   255  			}
   256  
   257  		case token.IMPORT:
   258  			panic("encountered import declaration in free analysis")
   259  		}
   260  
   261  	case *ast.FuncDecl:
   262  		if n.Recv == nil && n.Name.Name != "init" { // package-level function
   263  			v.declare(n.Name)
   264  		}
   265  		v.openScope()
   266  		defer v.closeScope()
   267  		v.walkTypeParams(n.Type.TypeParams)
   268  		v.walkFuncType(n.Recv, n.Type)
   269  		v.walkBody(n.Body)
   270  
   271  	default:
   272  		return v
   273  	}
   274  
   275  	return nil
   276  }
   277  
   278  func (v *freeVisitor) openScope() {
   279  	v.scope = &scope{map[string]bool{}, v.scope}
   280  }
   281  
   282  func (v *freeVisitor) closeScope() {
   283  	v.scope = v.scope.outer
   284  }
   285  
   286  func (v *freeVisitor) walk(n ast.Node) {
   287  	if n != nil {
   288  		ast.Walk(v, n)
   289  	}
   290  }
   291  
   292  func (v *freeVisitor) walkFuncType(recv *ast.FieldList, typ *ast.FuncType) {
   293  	// First use field types...
   294  	v.walkRecvFieldType(recv)
   295  	v.walkFieldTypes(typ.Params)
   296  	v.walkFieldTypes(typ.Results)
   297  
   298  	// ...then declare field names.
   299  	v.declareFieldNames(recv)
   300  	v.declareFieldNames(typ.Params)
   301  	v.declareFieldNames(typ.Results)
   302  }
   303  
   304  // A receiver field is not like a param or result field because
   305  // "func (recv R[T]) method()" uses R but declares T.
   306  func (v *freeVisitor) walkRecvFieldType(list *ast.FieldList) {
   307  	if list == nil {
   308  		return
   309  	}
   310  	for _, f := range list.List { // valid => len=1
   311  		typ := f.Type
   312  		if ptr, ok := typ.(*ast.StarExpr); ok {
   313  			typ = ptr.X
   314  		}
   315  
   316  		// Analyze receiver type as Base[Index, ...]
   317  		var (
   318  			base    ast.Expr
   319  			indices []ast.Expr
   320  		)
   321  		switch typ := typ.(type) {
   322  		case *ast.IndexExpr: // B[T]
   323  			base, indices = typ.X, []ast.Expr{typ.Index}
   324  		case *ast.IndexListExpr: // B[K, V]
   325  			base, indices = typ.X, typ.Indices
   326  		default: // B
   327  			base = typ
   328  		}
   329  		for _, expr := range indices {
   330  			if id, ok := expr.(*ast.Ident); ok {
   331  				v.declare(id)
   332  			}
   333  		}
   334  		v.walk(base)
   335  	}
   336  }
   337  
   338  // walkTypeParams is like walkFieldList, but declares type parameters eagerly so
   339  // that they may be resolved in the constraint expressions held in the field
   340  // Type.
   341  func (v *freeVisitor) walkTypeParams(list *ast.FieldList) {
   342  	v.declareFieldNames(list)
   343  	v.walkFieldTypes(list) // constraints
   344  }
   345  
   346  func (v *freeVisitor) walkBody(body *ast.BlockStmt) {
   347  	if body == nil {
   348  		return
   349  	}
   350  	walkSlice(v, body.List)
   351  }
   352  
   353  func (v *freeVisitor) walkFieldList(list *ast.FieldList) {
   354  	if list == nil {
   355  		return
   356  	}
   357  	v.walkFieldTypes(list)    // .Type may contain references
   358  	v.declareFieldNames(list) // .Names declares names
   359  }
   360  
   361  func (v *freeVisitor) shortVarDecl(lhs []ast.Expr) {
   362  	// Go spec: A short variable declaration may redeclare variables provided
   363  	// they were originally declared in the same block with the same type, and
   364  	// at least one of the non-blank variables is new.
   365  	//
   366  	// However, it doesn't matter to free analysis whether a variable is declared
   367  	// fresh or redeclared.
   368  	for _, x := range lhs {
   369  		// In a well-formed program each expr must be an identifier,
   370  		// but be forgiving.
   371  		if id, ok := x.(*ast.Ident); ok {
   372  			v.declare(id)
   373  		}
   374  	}
   375  }
   376  
   377  func walkSlice[S ~[]E, E ast.Node](r *freeVisitor, list S) {
   378  	for _, e := range list {
   379  		r.walk(e)
   380  	}
   381  }
   382  
   383  // walkFieldTypes resolves the types of the walkFieldTypes in list.
   384  // The companion method declareFieldList declares the names of the walkFieldTypes.
   385  func (v *freeVisitor) walkFieldTypes(list *ast.FieldList) {
   386  	if list != nil {
   387  		for _, f := range list.List {
   388  			v.walk(f.Type)
   389  		}
   390  	}
   391  }
   392  
   393  // declareFieldNames declares the names of the fields in list.
   394  // (Names in a FieldList always establish new bindings.)
   395  // The companion method resolveFieldList resolves the types of the fields.
   396  func (v *freeVisitor) declareFieldNames(list *ast.FieldList) {
   397  	if list != nil {
   398  		for _, f := range list.List {
   399  			v.declare(f.Names...)
   400  		}
   401  	}
   402  }
   403  
   404  // use marks ident as free if it is not in scope.
   405  func (v *freeVisitor) use(ident *ast.Ident) {
   406  	if s := ident.Name; s != "_" && !v.scope.defined(s) {
   407  		v.free[s] = true
   408  	}
   409  }
   410  
   411  // declare adds each non-blank ident to the current scope.
   412  func (v *freeVisitor) declare(idents ...*ast.Ident) {
   413  	for _, id := range idents {
   414  		if id.Name != "_" {
   415  			v.scope.names[id.Name] = true
   416  		}
   417  	}
   418  }
   419
View as plain text