...

Source file src/go/types/interfaces.go

Documentation: go/types

     1  // Copyright 2017 The Go Authors. All rights reserved.
     2  // Use of this src code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  package types
     6  
     7  import (
     8  	"bytes"
     9  	"fmt"
    10  	"go/ast"
    11  	"go/token"
    12  )
    13  
    14  // This file implements the collection of an interface's methods
    15  // without relying on partially computed types of methods or interfaces
    16  // for interface types declared at the package level.
    17  //
    18  // Because interfaces must not embed themselves, directly or indirectly,
    19  // the method set of a valid interface can always be computed independent
    20  // of any cycles that might exist via method signatures (see also issue #18395).
    21  //
    22  // Except for blank method name and interface cycle errors, no errors
    23  // are reported. Affected methods or embedded interfaces are silently
    24  // dropped. Subsequent type-checking of the interface will check
    25  // signatures and embedded interfaces and report errors at that time.
    26  //
    27  // Only infoFromTypeLit should be called directly from code outside this file
    28  // to compute an ifaceInfo.
    29  
    30  // ifaceInfo describes the method set for an interface.
    31  // The zero value for an ifaceInfo is a ready-to-use ifaceInfo representing
    32  // the empty interface.
    33  type ifaceInfo struct {
    34  	explicits int           // number of explicitly declared methods
    35  	methods   []*methodInfo // all methods, starting with explicitly declared ones in source order
    36  }
    37  
    38  // emptyIfaceInfo represents the ifaceInfo for the empty interface.
    39  var emptyIfaceInfo ifaceInfo
    40  
    41  func (info *ifaceInfo) String() string {
    42  	var buf bytes.Buffer
    43  	fmt.Fprintf(&buf, "interface{")
    44  	for i, m := range info.methods {
    45  		if i > 0 {
    46  			fmt.Fprint(&buf, " ")
    47  		}
    48  		fmt.Fprint(&buf, m)
    49  	}
    50  	fmt.Fprintf(&buf, "}")
    51  	return buf.String()
    52  }
    53  
    54  // methodInfo represents an interface method.
    55  // At least one of src or fun must be non-nil.
    56  // (Methods declared in the current package have a non-nil scope
    57  // and src, and eventually a non-nil fun field; imported and pre-
    58  // declared methods have a nil scope and src, and only a non-nil
    59  // fun field.)
    60  type methodInfo struct {
    61  	scope *Scope     // scope of interface method; or nil
    62  	src   *ast.Field // syntax tree representation of interface method; or nil
    63  	fun   *Func      // corresponding fully type-checked method type; or nil
    64  }
    65  
    66  func (info *methodInfo) String() string {
    67  	if info.fun != nil {
    68  		return info.fun.name
    69  	}
    70  	return info.src.Names[0].Name
    71  }
    72  
    73  func (info *methodInfo) Pos() token.Pos {
    74  	if info.fun != nil {
    75  		return info.fun.Pos()
    76  	}
    77  	return info.src.Pos()
    78  }
    79  
    80  func (info *methodInfo) id(pkg *Package) string {
    81  	if info.fun != nil {
    82  		return info.fun.Id()
    83  	}
    84  	return Id(pkg, info.src.Names[0].Name)
    85  }
    86  
    87  // A methodInfoSet maps method ids to methodInfos.
    88  // It is used to determine duplicate declarations.
    89  // (A methodInfo set is the equivalent of an objset
    90  // but for methodInfos rather than Objects.)
    91  type methodInfoSet map[string]*methodInfo
    92  
    93  // insert attempts to insert an method m into the method set s.
    94  // If s already contains an alternative method alt with
    95  // the same name, insert leaves s unchanged and returns alt.
    96  // Otherwise it inserts m and returns nil.
    97  func (s *methodInfoSet) insert(pkg *Package, m *methodInfo) *methodInfo {
    98  	id := m.id(pkg)
    99  	if alt := (*s)[id]; alt != nil {
   100  		return alt
   101  	}
   102  	if *s == nil {
   103  		*s = make(methodInfoSet)
   104  	}
   105  	(*s)[id] = m
   106  	return nil
   107  }
   108  
   109  // like Checker.declareInSet but for method infos.
   110  func (check *Checker) declareInMethodSet(mset *methodInfoSet, pos token.Pos, m *methodInfo) bool {
   111  	if alt := mset.insert(check.pkg, m); alt != nil {
   112  		check.errorf(pos, "%s redeclared", m)
   113  		check.reportAltMethod(alt)
   114  		return false
   115  	}
   116  	return true
   117  }
   118  
   119  // like Checker.reportAltDecl but for method infos.
   120  func (check *Checker) reportAltMethod(m *methodInfo) {
   121  	if pos := m.Pos(); pos.IsValid() {
   122  		// We use "other" rather than "previous" here because
   123  		// the first declaration seen may not be textually
   124  		// earlier in the source.
   125  		check.errorf(pos, "\tother declaration of %s", m) // secondary error, \t indented
   126  	}
   127  }
   128  
   129  // infoFromTypeLit computes the method set for the given interface iface
   130  // declared in scope.
   131  // If a corresponding type name exists (tname != nil), it is used for
   132  // cycle detection and to cache the method set.
   133  // The result is the method set, or nil if there is a cycle via embedded
   134  // interfaces. A non-nil result doesn't mean that there were no errors,
   135  // but they were either reported (e.g., blank methods), or will be found
   136  // (again) when computing the interface's type.
   137  // If tname is not nil it must be the last element in path.
   138  func (check *Checker) infoFromTypeLit(scope *Scope, iface *ast.InterfaceType, tname *TypeName, path []*TypeName) (info *ifaceInfo) {
   139  	assert(iface != nil)
   140  
   141  	// lazy-allocate interfaces map
   142  	if check.interfaces == nil {
   143  		check.interfaces = make(map[*TypeName]*ifaceInfo)
   144  	}
   145  
   146  	if trace {
   147  		check.trace(iface.Pos(), "-- collect methods for %v (path = %s, objPath = %s)", iface, pathString(path), objPathString(check.objPath))
   148  		check.indent++
   149  		defer func() {
   150  			check.indent--
   151  			check.trace(iface.Pos(), "=> %s", info)
   152  		}()
   153  	}
   154  
   155  	// If the interface is named, check if we computed info already.
   156  	//
   157  	// This is not simply an optimization; we may run into stack
   158  	// overflow with recursive interface declarations. Example:
   159  	//
   160  	//      type T interface {
   161  	//              m() interface { T }
   162  	//      }
   163  	//
   164  	// (Since recursive definitions can only be expressed via names,
   165  	// it is sufficient to track named interfaces here.)
   166  	//
   167  	// While at it, use the same mechanism to detect cycles. (We still
   168  	// have the path-based cycle check because we want to report the
   169  	// entire cycle if present.)
   170  	if tname != nil {
   171  		assert(path[len(path)-1] == tname) // tname must be last path element
   172  		var found bool
   173  		if info, found = check.interfaces[tname]; found {
   174  			if info == nil {
   175  				// We have a cycle and use check.cycle to report it.
   176  				// We are guaranteed that check.cycle also finds the
   177  				// cycle because when infoFromTypeLit is called, any
   178  				// tname that's already in check.interfaces was also
   179  				// added to the path. (But the converse is not true:
   180  				// A non-nil tname is always the last element in path.)
   181  				ok := check.cycle(tname, path, true)
   182  				assert(ok)
   183  			}
   184  			return
   185  		}
   186  		check.interfaces[tname] = nil // computation started but not complete
   187  	}
   188  
   189  	if iface.Methods.List == nil {
   190  		// fast track for empty interface
   191  		info = &emptyIfaceInfo
   192  	} else {
   193  		// (syntactically) non-empty interface
   194  		info = new(ifaceInfo)
   195  
   196  		// collect explicitly declared methods and embedded interfaces
   197  		var mset methodInfoSet
   198  		var embeddeds []*ifaceInfo
   199  		var positions []token.Pos // entries correspond to positions of embeddeds; used for error reporting
   200  		for _, f := range iface.Methods.List {
   201  			if len(f.Names) > 0 {
   202  				// We have a method with name f.Names[0].
   203  				// (The parser ensures that there's only one method
   204  				// and we don't care if a constructed AST has more.)
   205  
   206  				// spec: "As with all method sets, in an interface type,
   207  				// each method must have a unique non-blank name."
   208  				if name := f.Names[0]; name.Name == "_" {
   209  					check.errorf(name.Pos(), "invalid method name _")
   210  					continue // ignore
   211  				}
   212  
   213  				m := &methodInfo{scope: scope, src: f}
   214  				if check.declareInMethodSet(&mset, f.Pos(), m) {
   215  					info.methods = append(info.methods, m)
   216  				}
   217  			} else {
   218  				// We have an embedded interface and f.Type is its
   219  				// (possibly qualified) embedded type name. Collect
   220  				// it if it's a valid interface.
   221  				var e *ifaceInfo
   222  				switch ename := f.Type.(type) {
   223  				case *ast.Ident:
   224  					e = check.infoFromTypeName(scope, ename, path)
   225  				case *ast.SelectorExpr:
   226  					e = check.infoFromQualifiedTypeName(scope, ename)
   227  				default:
   228  					// The parser makes sure we only see one of the above.
   229  					// Constructed ASTs may contain other (invalid) nodes;
   230  					// we simply ignore them. The full type-checking pass
   231  					// will report those as errors later.
   232  				}
   233  				if e != nil {
   234  					embeddeds = append(embeddeds, e)
   235  					positions = append(positions, f.Type.Pos())
   236  				}
   237  			}
   238  		}
   239  		info.explicits = len(info.methods)
   240  
   241  		// collect methods of embedded interfaces
   242  		for i, e := range embeddeds {
   243  			pos := positions[i] // position of type name of embedded interface
   244  			for _, m := range e.methods {
   245  				if check.declareInMethodSet(&mset, pos, m) {
   246  					info.methods = append(info.methods, m)
   247  				}
   248  			}
   249  		}
   250  	}
   251  
   252  	// mark check.interfaces as complete
   253  	assert(info != nil)
   254  	if tname != nil {
   255  		check.interfaces[tname] = info
   256  	}
   257  
   258  	return
   259  }
   260  
   261  // infoFromTypeName computes the method set for the given type name
   262  // which must denote a type whose underlying type is an interface.
   263  // The same result qualifications apply as for infoFromTypeLit.
   264  // infoFromTypeName should only be called from infoFromTypeLit.
   265  func (check *Checker) infoFromTypeName(scope *Scope, name *ast.Ident, path []*TypeName) *ifaceInfo {
   266  	// A single call of infoFromTypeName handles a sequence of (possibly
   267  	// recursive) type declarations connected via unqualified type names.
   268  	// Each type declaration leading to another typename causes a "tail call"
   269  	// (goto) of this function. The general scenario looks like this:
   270  	//
   271  	//      ...
   272  	//      type Pn T        // previous declarations leading to T, path = [..., Pn]
   273  	//      type T interface { T0; ... }  // T0 leads to call of infoFromTypeName
   274  	//
   275  	//      // infoFromTypeName(name = T0, path = [..., Pn, T])
   276  	//      type T0 T1       // path = [..., Pn, T, T0]
   277  	//      type T1 T2  <-+  // path = [..., Pn, T, T0, T1]
   278  	//      type T2 ...   |  // path = [..., Pn, T, T0, T1, T2]
   279  	//      type Tn T1  --+  // path = [..., Pn, T, T0, T1, T2, Tn] and T1 is in path => cycle
   280  	//
   281  	// infoFromTypeName returns nil when such a cycle is detected. But in
   282  	// contrast to cycles involving interfaces, we must not report the
   283  	// error for "type name only" cycles because they will be found again
   284  	// during type-checking of embedded interfaces. Reporting those cycles
   285  	// here would lead to double reporting. Cycles involving embedding are
   286  	// not reported again later because type-checking of interfaces relies
   287  	// on the ifaceInfos computed here which are cycle-free by design.
   288  	//
   289  	// Remember the path length to detect "type name only" cycles.
   290  	start := len(path)
   291  
   292  typenameLoop:
   293  	// name must be a type name denoting a type whose underlying type is an interface
   294  	_, obj := scope.LookupParent(name.Name, check.pos)
   295  	if obj == nil {
   296  		return nil
   297  	}
   298  	tname, _ := obj.(*TypeName)
   299  	if tname == nil {
   300  		return nil
   301  	}
   302  
   303  	// We have a type name. It may be predeclared (error type),
   304  	// imported (dot import), or declared by a type declaration.
   305  	// It may not be an interface (e.g., predeclared type int).
   306  	// Resolve it by analyzing each possible case.
   307  
   308  	// Abort but don't report an error if we have a "type name only"
   309  	// cycle (see big function comment).
   310  	if check.cycle(tname, path[start:], false) {
   311  		return nil
   312  	}
   313  
   314  	// Abort and report an error if we have a general cycle.
   315  	if check.cycle(tname, path, true) {
   316  		return nil
   317  	}
   318  
   319  	path = append(path, tname)
   320  
   321  	// If tname is a package-level type declaration, it must be
   322  	// in the objMap. Follow the RHS of that declaration if so.
   323  	// The RHS may be a literal type (likely case), or another
   324  	// (possibly parenthesized and/or qualified) type name.
   325  	// (The declaration may be an alias declaration, but it
   326  	// doesn't matter for the purpose of determining the under-
   327  	// lying interface.)
   328  	if decl := check.objMap[tname]; decl != nil {
   329  		switch typ := unparen(decl.typ).(type) {
   330  		case *ast.Ident:
   331  			// type tname T
   332  			name = typ
   333  			goto typenameLoop
   334  		case *ast.SelectorExpr:
   335  			// type tname p.T
   336  			return check.infoFromQualifiedTypeName(decl.file, typ)
   337  		case *ast.InterfaceType:
   338  			// type tname interface{...}
   339  			// If tname is fully type-checked at this point (tname.color() == black)
   340  			// we could use infoFromType here. But in this case, the interface must
   341  			// be in the check.interfaces cache as well, which will be hit when we
   342  			// call infoFromTypeLit below, and which will be faster. It is important
   343  			// that we use that previously computed interface because its methods
   344  			// have the correct receiver type (for go/types clients). Thus, the
   345  			// check.interfaces cache must be up-to-date across even across multiple
   346  			// check.Files calls (was bug - see issue #29029).
   347  			return check.infoFromTypeLit(decl.file, typ, tname, path)
   348  		}
   349  		// type tname X // and X is not an interface type
   350  		return nil
   351  	}
   352  
   353  	// If tname is not a package-level declaration, in a well-typed
   354  	// program it should be a predeclared (error type), imported (dot
   355  	// import), or function local declaration. Either way, it should
   356  	// have been fully declared before use, except if there is a direct
   357  	// cycle, and direct cycles will be caught above. Also, the denoted
   358  	// type should be an interface (e.g., int is not an interface).
   359  	if typ := tname.typ; typ != nil {
   360  		// typ should be an interface
   361  		if ityp, _ := typ.Underlying().(*Interface); ityp != nil {
   362  			return infoFromType(ityp)
   363  		}
   364  	}
   365  
   366  	// In all other cases we have some error.
   367  	return nil
   368  }
   369  
   370  // infoFromQualifiedTypeName computes the method set for the given qualified type name, or nil.
   371  func (check *Checker) infoFromQualifiedTypeName(scope *Scope, qname *ast.SelectorExpr) *ifaceInfo {
   372  	// see also Checker.selector
   373  	name, _ := qname.X.(*ast.Ident)
   374  	if name == nil {
   375  		return nil
   376  	}
   377  	_, obj1 := scope.LookupParent(name.Name, check.pos)
   378  	if obj1 == nil {
   379  		return nil
   380  	}
   381  	pname, _ := obj1.(*PkgName)
   382  	if pname == nil {
   383  		return nil
   384  	}
   385  	assert(pname.pkg == check.pkg)
   386  	obj2 := pname.imported.scope.Lookup(qname.Sel.Name)
   387  	if obj2 == nil || !obj2.Exported() {
   388  		return nil
   389  	}
   390  	tname, _ := obj2.(*TypeName)
   391  	if tname == nil {
   392  		return nil
   393  	}
   394  	ityp, _ := tname.typ.Underlying().(*Interface)
   395  	if ityp == nil {
   396  		return nil
   397  	}
   398  	return infoFromType(ityp)
   399  }
   400  
   401  // infoFromType computes the method set for the given interface type.
   402  // The result is never nil.
   403  func infoFromType(typ *Interface) *ifaceInfo {
   404  	assert(typ.allMethods != nil) // typ must be completely set up
   405  
   406  	// fast track for empty interface
   407  	n := len(typ.allMethods)
   408  	if n == 0 {
   409  		return &emptyIfaceInfo
   410  	}
   411  
   412  	info := new(ifaceInfo)
   413  	info.explicits = len(typ.methods)
   414  	info.methods = make([]*methodInfo, n)
   415  
   416  	// If there are no embedded interfaces, simply collect the
   417  	// explicitly declared methods (optimization of common case).
   418  	if len(typ.methods) == n {
   419  		for i, m := range typ.methods {
   420  			info.methods[i] = &methodInfo{fun: m}
   421  		}
   422  		return info
   423  	}
   424  
   425  	// Interface types have a separate list for explicitly declared methods
   426  	// which shares its methods with the list of all (explicitly declared or
   427  	// embedded) methods. Collect all methods in a set so we can separate
   428  	// the embedded methods from the explicitly declared ones.
   429  	all := make(map[*Func]bool, n)
   430  	for _, m := range typ.allMethods {
   431  		all[m] = true
   432  	}
   433  	assert(len(all) == n) // methods must be unique
   434  
   435  	// collect explicitly declared methods
   436  	info.methods = make([]*methodInfo, n)
   437  	for i, m := range typ.methods {
   438  		info.methods[i] = &methodInfo{fun: m}
   439  		delete(all, m)
   440  	}
   441  
   442  	// collect remaining (embedded) methods
   443  	i := len(typ.methods)
   444  	for m := range all {
   445  		info.methods[i] = &methodInfo{fun: m}
   446  		i++
   447  	}
   448  	assert(i == n)
   449  
   450  	return info
   451  }
   452  

View as plain text