internal/analysisinternal/analysis.go - tools.git - Git at Google

 // Copyright 2020 The Go Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style
 // license that can be found in the LICENSE file.

 // Package analysisinternal provides gopls' internal analyses with a
 // number of helper functions that operate on typed syntax trees.
 package analysisinternal

 import (
 	"cmp"
 	"fmt"
 	"go/ast"
 	"go/token"
 	"go/types"
 	"slices"
 	"strings"

 	"golang.org/x/tools/go/analysis"
 )

 // MatchingIdents finds the names of all identifiers in 'node' that match any of the given types.
 // 'pos' represents the position at which the identifiers may be inserted. 'pos' must be within
 // the scope of each of identifier we select. Otherwise, we will insert a variable at 'pos' that
 // is unrecognized.
 //
 // TODO(adonovan): this is only used by gopls/internal/analysis/fill{returns,struct}. Move closer.
 func MatchingIdents(typs []types.Type, node ast.Node, pos token.Pos, info *types.Info, pkg *types.Package) map[types.Type][]string {

 	// Initialize matches to contain the variable types we are searching for.
 	matches := make(map[types.Type][]string)
 	for _, typ := range typs {
 		if typ == nil {
 			continue // TODO(adonovan): is this reachable?
 		}
 		matches[typ] = nil // create entry
 	}

 	seen := map[types.Object]struct{}{}
 	ast.Inspect(node, func(n ast.Node) bool {
 		if n == nil {
 			return false
 		}
 		// Prevent circular definitions. If 'pos' is within an assignment statement, do not
 		// allow any identifiers in that assignment statement to be selected. Otherwise,
 		// we could do the following, where 'x' satisfies the type of 'f0':
 		//
 		// x := fakeStruct{f0: x}
 		//
 		if assign, ok := n.(*ast.AssignStmt); ok && pos > assign.Pos() && pos <= assign.End() {
 			return false
 		}
 		if n.End() > pos {
 			return n.Pos() <= pos
 		}
 		ident, ok := n.(*ast.Ident)
 		if !ok || ident.Name == "_" {
 			return true
 		}
 		obj := info.Defs[ident]
 		if obj == nil || obj.Type() == nil {
 			return true
 		}
 		if _, ok := obj.(*types.TypeName); ok {
 			return true
 		}
 		// Prevent duplicates in matches' values.
 		if _, ok = seen[obj]; ok {
 			return true
 		}
 		seen[obj] = struct{}{}
 		// Find the scope for the given position. Then, check whether the object
 		// exists within the scope.
 		innerScope := pkg.Scope().Innermost(pos)
 		if innerScope == nil {
 			return true
 		}
 		_, foundObj := innerScope.LookupParent(ident.Name, pos)
 		if foundObj != obj {
 			return true
 		}
 		// The object must match one of the types that we are searching for.
 		// TODO(adonovan): opt: use typeutil.Map?
 		if names, ok := matches[obj.Type()]; ok {
 			matches[obj.Type()] = append(names, ident.Name)
 		} else {
 			// If the object type does not exactly match
 			// any of the target types, greedily find the first
 			// target type that the object type can satisfy.
 			for typ := range matches {
 				if equivalentTypes(obj.Type(), typ) {
 					matches[typ] = append(matches[typ], ident.Name)
 				}
 			}
 		}
 		return true
 	})
 	return matches
 }

 func equivalentTypes(want, got types.Type) bool {
 	if types.Identical(want, got) {
 		return true
 	}
 	// Code segment to help check for untyped equality from (golang/go#32146).
 	if rhs, ok := want.(*types.Basic); ok && rhs.Info()&types.IsUntyped > 0 {
 		if lhs, ok := got.Underlying().(*types.Basic); ok {
 			return rhs.Info()&types.IsConstType == lhs.Info()&types.IsConstType
 		}
 	}
 	return types.AssignableTo(want, got)
 }

 // A ReadFileFunc is a function that returns the
 // contents of a file, such as [os.ReadFile].
 type ReadFileFunc = func(filename string) ([]byte, error)

 // CheckedReadFile returns a wrapper around a Pass.ReadFile
 // function that performs the appropriate checks.
 func CheckedReadFile(pass *analysis.Pass, readFile ReadFileFunc) ReadFileFunc {
 	return func(filename string) ([]byte, error) {
 		if err := CheckReadable(pass, filename); err != nil {
 			return nil, err
 		}
 		return readFile(filename)
 	}
 }

 // CheckReadable enforces the access policy defined by the ReadFile field of [analysis.Pass].
 func CheckReadable(pass *analysis.Pass, filename string) error {
 	if slices.Contains(pass.OtherFiles, filename) ||
 		slices.Contains(pass.IgnoredFiles, filename) {
 		return nil
 	}
 	for _, f := range pass.Files {
 		if pass.Fset.File(f.FileStart).Name() == filename {
 			return nil
 		}
 	}
 	return fmt.Errorf("Pass.ReadFile: %s is not among OtherFiles, IgnoredFiles, or names of Files", filename)
 }

 // ValidateFixes validates the set of fixes for a single diagnostic.
 // Any error indicates a bug in the originating analyzer.
 //
 // It updates fixes so that fixes[*].End.IsValid().
 //
 // It may be used as part of an analysis driver implementation.
 func ValidateFixes(fset *token.FileSet, a *analysis.Analyzer, fixes []analysis.SuggestedFix) error {
 	fixMessages := make(map[string]bool)
 	for i := range fixes {
 		fix := &fixes[i]
 		if fixMessages[fix.Message] {
 			return fmt.Errorf("analyzer %q suggests two fixes with same Message (%s)", a.Name, fix.Message)
 		}
 		fixMessages[fix.Message] = true
 		if err := validateFix(fset, fix); err != nil {
 			return fmt.Errorf("analyzer %q suggests invalid fix (%s): %v", a.Name, fix.Message, err)
 		}
 	}
 	return nil
 }

 // validateFix validates a single fix.
 // Any error indicates a bug in the originating analyzer.
 //
 // It updates fix so that fix.End.IsValid().
 func validateFix(fset *token.FileSet, fix *analysis.SuggestedFix) error {

 	// Stably sort edits by Pos. This ordering puts insertions
 	// (end = start) before deletions (end > start) at the same
 	// point, but uses a stable sort to preserve the order of
 	// multiple insertions at the same point.
 	slices.SortStableFunc(fix.TextEdits, func(x, y analysis.TextEdit) int {
 		if sign := cmp.Compare(x.Pos, y.Pos); sign != 0 {
 			return sign
 		}
 		return cmp.Compare(x.End, y.End)
 	})

 	var prev *analysis.TextEdit
 	for i := range fix.TextEdits {
 		edit := &fix.TextEdits[i]

 		// Validate edit individually.
 		start := edit.Pos
 		file := fset.File(start)
 		if file == nil {
 			return fmt.Errorf("no token.File for TextEdit.Pos (%v)", edit.Pos)
 		}
 		fileEnd := token.Pos(file.Base() + file.Size())
 		if end := edit.End; end.IsValid() {
 			if end < start {
 				return fmt.Errorf("TextEdit.Pos (%v) > TextEdit.End (%v)", edit.Pos, edit.End)
 			}
 			endFile := fset.File(end)
 			if endFile != file && end < fileEnd+10 {
 				// Relax the checks below in the special case when the end position
 				// is only slightly beyond EOF, as happens when End is computed
 				// (as in ast.{Struct,Interface}Type) rather than based on
 				// actual token positions. In such cases, truncate end to EOF.
 				//
 				// This is a workaround for #71659; see:
 				// https://github.com/golang/go/issues/71659#issuecomment-2651606031
 				// A better fix would be more faithful recording of token
 				// positions (or their absence) in the AST.
 				edit.End = fileEnd
 				continue
 			}
 			if endFile == nil {
 				return fmt.Errorf("no token.File for TextEdit.End (%v; File(start).FileEnd is %d)", end, file.Base()+file.Size())
 			}
 			if endFile != file {
 				return fmt.Errorf("edit #%d spans files (%v and %v)",
 					i, file.Position(edit.Pos), endFile.Position(edit.End))
 			}
 		} else {
 			edit.End = start // update the SuggestedFix
 		}
 		if eof := fileEnd; edit.End > eof {
 			return fmt.Errorf("end is (%v) beyond end of file (%v)", edit.End, eof)
 		}

 		// Validate the sequence of edits:
 		// properly ordered, no overlapping deletions
 		if prev != nil && edit.Pos < prev.End {
 			xpos := fset.Position(prev.Pos)
 			xend := fset.Position(prev.End)
 			ypos := fset.Position(edit.Pos)
 			yend := fset.Position(edit.End)
 			return fmt.Errorf("overlapping edits to %s (%d:%d-%d:%d and %d:%d-%d:%d)",
 				xpos.Filename,
 				xpos.Line, xpos.Column,
 				xend.Line, xend.Column,
 				ypos.Line, ypos.Column,
 				yend.Line, yend.Column,
 			)
 		}
 		prev = edit
 	}

 	return nil
 }

 // Range returns an [analysis.Range] for the specified start and end positions.
 func Range(pos, end token.Pos) analysis.Range {
 	return tokenRange{pos, end}
 }

 // tokenRange is an implementation of the [analysis.Range] interface.
 type tokenRange struct{ StartPos, EndPos token.Pos }

 func (r tokenRange) Pos() token.Pos { return r.StartPos }
 func (r tokenRange) End() token.Pos { return r.EndPos }

 // TODO(adonovan): the import-related functions below don't depend on
 // analysis (or even on go/types or go/ast). Move somewhere more logical.

 // CanImport reports whether one package is allowed to import another.
 //
 // TODO(adonovan): allow customization of the accessibility relation
 // (e.g. for Bazel).
 func CanImport(from, to string) bool {
 	// TODO(adonovan): better segment hygiene.
 	if to == "internal" || strings.HasPrefix(to, "internal/") {
 		// Special case: only std packages may import internal/...
 		// We can't reliably know whether we're in std, so we
 		// use a heuristic on the first segment.
 		first, _, _ := strings.Cut(from, "/")
 		if strings.Contains(first, ".") {
 			return false // example.com/foo ∉ std
 		}
 		if first == "testdata" {
 			return false // testdata/foo ∉ std
 		}
 	}
 	if strings.HasSuffix(to, "/internal") {
 		return strings.HasPrefix(from, to[:len(to)-len("/internal")])
 	}
 	if i := strings.LastIndex(to, "/internal/"); i >= 0 {
 		return strings.HasPrefix(from, to[:i])
 	}
 	return true
 }

 // IsStdPackage reports whether the specified package path belongs to a
 // package in the standard library (including internal dependencies).
 func IsStdPackage(path string) bool {
 	// A standard package has no dot in its first segment.
 	// (It may yet have a dot, e.g. "vendor/golang.org/x/foo".)
 	slash := strings.IndexByte(path, '/')
 	if slash < 0 {
 		slash = len(path)
 	}
 	return !strings.Contains(path[:slash], ".") && path != "testdata"
 }
	// Copyright 2020 The Go Authors. All rights reserved.
	// Use of this source code is governed by a BSD-style
	// license that can be found in the LICENSE file.

	// Package analysisinternal provides gopls' internal analyses with a
	// number of helper functions that operate on typed syntax trees.
	package analysisinternal

	import (
	"cmp"
	"fmt"
	"go/ast"
	"go/token"
	"go/types"
	"slices"
	"strings"

	"golang.org/x/tools/go/analysis"
	)

	// MatchingIdents finds the names of all identifiers in 'node' that match any of the given types.
	// 'pos' represents the position at which the identifiers may be inserted. 'pos' must be within
	// the scope of each of identifier we select. Otherwise, we will insert a variable at 'pos' that
	// is unrecognized.
	//
	// TODO(adonovan): this is only used by gopls/internal/analysis/fill{returns,struct}. Move closer.
	func MatchingIdents(typs []types.Type, node ast.Node, pos token.Pos, info types.Info, pkg types.Package) map[types.Type][]string {

	// Initialize matches to contain the variable types we are searching for.
	matches := make(map[types.Type][]string)
	for _, typ := range typs {
	if typ == nil {
	continue // TODO(adonovan): is this reachable?
	}
	matches[typ] = nil // create entry
	}

	seen := map[types.Object]struct{}{}
	ast.Inspect(node, func(n ast.Node) bool {
	if n == nil {
	return false
	}
	// Prevent circular definitions. If 'pos' is within an assignment statement, do not
	// allow any identifiers in that assignment statement to be selected. Otherwise,
	// we could do the following, where 'x' satisfies the type of 'f0':
	//
	// x := fakeStruct{f0: x}
	//
	if assign, ok := n.(*ast.AssignStmt); ok && pos > assign.Pos() && pos <= assign.End() {
	return false
	}
	if n.End() > pos {
	return n.Pos() <= pos
	}
	ident, ok := n.(*ast.Ident)
	if !ok \|\| ident.Name == "_" {
	return true
	}
	obj := info.Defs[ident]
	if obj == nil \|\| obj.Type() == nil {
	return true
	}
	if _, ok := obj.(*types.TypeName); ok {
	return true
	}
	// Prevent duplicates in matches' values.
	if _, ok = seen[obj]; ok {
	return true
	}
	seen[obj] = struct{}{}
	// Find the scope for the given position. Then, check whether the object
	// exists within the scope.
	innerScope := pkg.Scope().Innermost(pos)
	if innerScope == nil {
	return true
	}
	_, foundObj := innerScope.LookupParent(ident.Name, pos)
	if foundObj != obj {
	return true
	}
	// The object must match one of the types that we are searching for.
	// TODO(adonovan): opt: use typeutil.Map?
	if names, ok := matches[obj.Type()]; ok {
	matches[obj.Type()] = append(names, ident.Name)
	} else {
	// If the object type does not exactly match
	// any of the target types, greedily find the first
	// target type that the object type can satisfy.
	for typ := range matches {
	if equivalentTypes(obj.Type(), typ) {
	matches[typ] = append(matches[typ], ident.Name)
	}
	}
	}
	return true
	})
	return matches
	}

	func equivalentTypes(want, got types.Type) bool {
	if types.Identical(want, got) {
	return true
	}
	// Code segment to help check for untyped equality from (golang/go#32146).
	if rhs, ok := want.(*types.Basic); ok && rhs.Info()&types.IsUntyped > 0 {
	if lhs, ok := got.Underlying().(*types.Basic); ok {
	return rhs.Info()&types.IsConstType == lhs.Info()&types.IsConstType
	}
	}
	return types.AssignableTo(want, got)
	}

	// A ReadFileFunc is a function that returns the
	// contents of a file, such as [os.ReadFile].
	type ReadFileFunc = func(filename string) ([]byte, error)

	// CheckedReadFile returns a wrapper around a Pass.ReadFile
	// function that performs the appropriate checks.
	func CheckedReadFile(pass *analysis.Pass, readFile ReadFileFunc) ReadFileFunc {
	return func(filename string) ([]byte, error) {
	if err := CheckReadable(pass, filename); err != nil {
	return nil, err
	}
	return readFile(filename)
	}
	}

	// CheckReadable enforces the access policy defined by the ReadFile field of [analysis.Pass].
	func CheckReadable(pass *analysis.Pass, filename string) error {
	if slices.Contains(pass.OtherFiles, filename) \|\|
	slices.Contains(pass.IgnoredFiles, filename) {
	return nil
	}
	for _, f := range pass.Files {
	if pass.Fset.File(f.FileStart).Name() == filename {
	return nil
	}
	}
	return fmt.Errorf("Pass.ReadFile: %s is not among OtherFiles, IgnoredFiles, or names of Files", filename)
	}

	// ValidateFixes validates the set of fixes for a single diagnostic.
	// Any error indicates a bug in the originating analyzer.
	//
	// It updates fixes so that fixes[*].End.IsValid().
	//
	// It may be used as part of an analysis driver implementation.
	func ValidateFixes(fset token.FileSet, a analysis.Analyzer, fixes []analysis.SuggestedFix) error {
	fixMessages := make(map[string]bool)
	for i := range fixes {
	fix := &fixes[i]
	if fixMessages[fix.Message] {
	return fmt.Errorf("analyzer %q suggests two fixes with same Message (%s)", a.Name, fix.Message)
	}
	fixMessages[fix.Message] = true
	if err := validateFix(fset, fix); err != nil {
	return fmt.Errorf("analyzer %q suggests invalid fix (%s): %v", a.Name, fix.Message, err)
	}
	}
	return nil
	}

	// validateFix validates a single fix.
	// Any error indicates a bug in the originating analyzer.
	//
	// It updates fix so that fix.End.IsValid().
	func validateFix(fset token.FileSet, fix analysis.SuggestedFix) error {

	// Stably sort edits by Pos. This ordering puts insertions
	// (end = start) before deletions (end > start) at the same
	// point, but uses a stable sort to preserve the order of
	// multiple insertions at the same point.
	slices.SortStableFunc(fix.TextEdits, func(x, y analysis.TextEdit) int {
	if sign := cmp.Compare(x.Pos, y.Pos); sign != 0 {
	return sign
	}
	return cmp.Compare(x.End, y.End)
	})

	var prev *analysis.TextEdit
	for i := range fix.TextEdits {
	edit := &fix.TextEdits[i]

	// Validate edit individually.
	start := edit.Pos
	file := fset.File(start)
	if file == nil {
	return fmt.Errorf("no token.File for TextEdit.Pos (%v)", edit.Pos)
	}
	fileEnd := token.Pos(file.Base() + file.Size())
	if end := edit.End; end.IsValid() {
	if end < start {
	return fmt.Errorf("TextEdit.Pos (%v) > TextEdit.End (%v)", edit.Pos, edit.End)
	}
	endFile := fset.File(end)
	if endFile != file && end < fileEnd+10 {
	// Relax the checks below in the special case when the end position
	// is only slightly beyond EOF, as happens when End is computed
	// (as in ast.{Struct,Interface}Type) rather than based on
	// actual token positions. In such cases, truncate end to EOF.
	//
	// This is a workaround for #71659; see:
	// https://github.com/golang/go/issues/71659#issuecomment-2651606031
	// A better fix would be more faithful recording of token
	// positions (or their absence) in the AST.
	edit.End = fileEnd
	continue
	}
	if endFile == nil {
	return fmt.Errorf("no token.File for TextEdit.End (%v; File(start).FileEnd is %d)", end, file.Base()+file.Size())
	}
	if endFile != file {
	return fmt.Errorf("edit #%d spans files (%v and %v)",
	i, file.Position(edit.Pos), endFile.Position(edit.End))
	}
	} else {
	edit.End = start // update the SuggestedFix
	}
	if eof := fileEnd; edit.End > eof {
	return fmt.Errorf("end is (%v) beyond end of file (%v)", edit.End, eof)
	}

	// Validate the sequence of edits:
	// properly ordered, no overlapping deletions
	if prev != nil && edit.Pos < prev.End {
	xpos := fset.Position(prev.Pos)
	xend := fset.Position(prev.End)
	ypos := fset.Position(edit.Pos)
	yend := fset.Position(edit.End)
	return fmt.Errorf("overlapping edits to %s (%d:%d-%d:%d and %d:%d-%d:%d)",
	xpos.Filename,
	xpos.Line, xpos.Column,
	xend.Line, xend.Column,
	ypos.Line, ypos.Column,
	yend.Line, yend.Column,
	)
	}
	prev = edit
	}

	return nil
	}

	// Range returns an [analysis.Range] for the specified start and end positions.
	func Range(pos, end token.Pos) analysis.Range {
	return tokenRange{pos, end}
	}

	// tokenRange is an implementation of the [analysis.Range] interface.
	type tokenRange struct{ StartPos, EndPos token.Pos }

	func (r tokenRange) Pos() token.Pos { return r.StartPos }
	func (r tokenRange) End() token.Pos { return r.EndPos }

	// TODO(adonovan): the import-related functions below don't depend on
	// analysis (or even on go/types or go/ast). Move somewhere more logical.

	// CanImport reports whether one package is allowed to import another.
	//
	// TODO(adonovan): allow customization of the accessibility relation
	// (e.g. for Bazel).
	func CanImport(from, to string) bool {
	// TODO(adonovan): better segment hygiene.
	if to == "internal" \|\| strings.HasPrefix(to, "internal/") {
	// Special case: only std packages may import internal/...
	// We can't reliably know whether we're in std, so we
	// use a heuristic on the first segment.
	first, _, _ := strings.Cut(from, "/")
	if strings.Contains(first, ".") {
	return false // example.com/foo ∉ std
	}
	if first == "testdata" {
	return false // testdata/foo ∉ std
	}
	}
	if strings.HasSuffix(to, "/internal") {
	return strings.HasPrefix(from, to[:len(to)-len("/internal")])
	}
	if i := strings.LastIndex(to, "/internal/"); i >= 0 {
	return strings.HasPrefix(from, to[:i])
	}
	return true
	}

	// IsStdPackage reports whether the specified package path belongs to a
	// package in the standard library (including internal dependencies).
	func IsStdPackage(path string) bool {
	// A standard package has no dot in its first segment.
	// (It may yet have a dot, e.g. "vendor/golang.org/x/foo".)
	slash := strings.IndexByte(path, '/')
	if slash < 0 {
	slash = len(path)
	}
	return !strings.Contains(path[:slash], ".") && path != "testdata"
	}