Black Lives Matter. Support the Equal Justice Initiative.

Source file src/go/types/methodset.go

Documentation: go/types

     1  // Copyright 2013 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  // This file implements method sets.
     6  
     7  package types
     8  
     9  import (
    10  	"fmt"
    11  	"sort"
    12  	"strings"
    13  )
    14  
    15  // A MethodSet is an ordered set of concrete or abstract (interface) methods;
    16  // a method is a MethodVal selection, and they are ordered by ascending m.Obj().Id().
    17  // The zero value for a MethodSet is a ready-to-use empty method set.
    18  type MethodSet struct {
    19  	list []*Selection
    20  }
    21  
    22  func (s *MethodSet) String() string {
    23  	if s.Len() == 0 {
    24  		return "MethodSet {}"
    25  	}
    26  
    27  	var buf strings.Builder
    28  	fmt.Fprintln(&buf, "MethodSet {")
    29  	for _, f := range s.list {
    30  		fmt.Fprintf(&buf, "\t%s\n", f)
    31  	}
    32  	fmt.Fprintln(&buf, "}")
    33  	return buf.String()
    34  }
    35  
    36  // Len returns the number of methods in s.
    37  func (s *MethodSet) Len() int { return len(s.list) }
    38  
    39  // At returns the i'th method in s for 0 <= i < s.Len().
    40  func (s *MethodSet) At(i int) *Selection { return s.list[i] }
    41  
    42  // Lookup returns the method with matching package and name, or nil if not found.
    43  func (s *MethodSet) Lookup(pkg *Package, name string) *Selection {
    44  	if s.Len() == 0 {
    45  		return nil
    46  	}
    47  
    48  	key := Id(pkg, name)
    49  	i := sort.Search(len(s.list), func(i int) bool {
    50  		m := s.list[i]
    51  		return m.obj.Id() >= key
    52  	})
    53  	if i < len(s.list) {
    54  		m := s.list[i]
    55  		if m.obj.Id() == key {
    56  			return m
    57  		}
    58  	}
    59  	return nil
    60  }
    61  
    62  // Shared empty method set.
    63  var emptyMethodSet MethodSet
    64  
    65  // Note: NewMethodSet is intended for external use only as it
    66  //       requires interfaces to be complete. If may be used
    67  //       internally if LookupFieldOrMethod completed the same
    68  //       interfaces beforehand.
    69  
    70  // NewMethodSet returns the method set for the given type T.
    71  // It always returns a non-nil method set, even if it is empty.
    72  func NewMethodSet(T Type) *MethodSet {
    73  	// WARNING: The code in this function is extremely subtle - do not modify casually!
    74  	//          This function and lookupFieldOrMethod should be kept in sync.
    75  
    76  	// method set up to the current depth, allocated lazily
    77  	var base methodSet
    78  
    79  	typ, isPtr := deref(T)
    80  
    81  	// *typ where typ is an interface has no methods.
    82  	if isPtr && IsInterface(typ) {
    83  		return &emptyMethodSet
    84  	}
    85  
    86  	// Start with typ as single entry at shallowest depth.
    87  	current := []embeddedType{{typ, nil, isPtr, false}}
    88  
    89  	// Named types that we have seen already, allocated lazily.
    90  	// Used to avoid endless searches in case of recursive types.
    91  	// Since only Named types can be used for recursive types, we
    92  	// only need to track those.
    93  	// (If we ever allow type aliases to construct recursive types,
    94  	// we must use type identity rather than pointer equality for
    95  	// the map key comparison, as we do in consolidateMultiples.)
    96  	var seen map[*Named]bool
    97  
    98  	// collect methods at current depth
    99  	for len(current) > 0 {
   100  		var next []embeddedType // embedded types found at current depth
   101  
   102  		// field and method sets at current depth, allocated lazily
   103  		var fset fieldSet
   104  		var mset methodSet
   105  
   106  		for _, e := range current {
   107  			typ := e.typ
   108  
   109  			// If we have a named type, we may have associated methods.
   110  			// Look for those first.
   111  			if named, _ := typ.(*Named); named != nil {
   112  				if seen[named] {
   113  					// We have seen this type before, at a more shallow depth
   114  					// (note that multiples of this type at the current depth
   115  					// were consolidated before). The type at that depth shadows
   116  					// this same type at the current depth, so we can ignore
   117  					// this one.
   118  					continue
   119  				}
   120  				if seen == nil {
   121  					seen = make(map[*Named]bool)
   122  				}
   123  				seen[named] = true
   124  
   125  				mset = mset.add(named.methods, e.index, e.indirect, e.multiples)
   126  
   127  				// continue with underlying type
   128  				typ = named.underlying
   129  			}
   130  
   131  			switch t := typ.(type) {
   132  			case *Struct:
   133  				for i, f := range t.fields {
   134  					fset = fset.add(f, e.multiples)
   135  
   136  					// Embedded fields are always of the form T or *T where
   137  					// T is a type name. If typ appeared multiple times at
   138  					// this depth, f.Type appears multiple times at the next
   139  					// depth.
   140  					if f.embedded {
   141  						typ, isPtr := deref(f.typ)
   142  						// TODO(gri) optimization: ignore types that can't
   143  						// have fields or methods (only Named, Struct, and
   144  						// Interface types need to be considered).
   145  						next = append(next, embeddedType{typ, concat(e.index, i), e.indirect || isPtr, e.multiples})
   146  					}
   147  				}
   148  
   149  			case *Interface:
   150  				mset = mset.add(t.allMethods, e.index, true, e.multiples)
   151  			}
   152  		}
   153  
   154  		// Add methods and collisions at this depth to base if no entries with matching
   155  		// names exist already.
   156  		for k, m := range mset {
   157  			if _, found := base[k]; !found {
   158  				// Fields collide with methods of the same name at this depth.
   159  				if _, found := fset[k]; found {
   160  					m = nil // collision
   161  				}
   162  				if base == nil {
   163  					base = make(methodSet)
   164  				}
   165  				base[k] = m
   166  			}
   167  		}
   168  
   169  		// Multiple fields with matching names collide at this depth and shadow all
   170  		// entries further down; add them as collisions to base if no entries with
   171  		// matching names exist already.
   172  		for k, f := range fset {
   173  			if f == nil {
   174  				if _, found := base[k]; !found {
   175  					if base == nil {
   176  						base = make(methodSet)
   177  					}
   178  					base[k] = nil // collision
   179  				}
   180  			}
   181  		}
   182  
   183  		// It's ok to call consolidateMultiples with a nil *Checker because
   184  		// MethodSets are not used internally (outside debug mode). When used
   185  		// externally, interfaces are expected to be completed and then we do
   186  		// not need a *Checker to complete them when (indirectly) calling
   187  		// Checker.identical via consolidateMultiples.
   188  		current = (*Checker)(nil).consolidateMultiples(next)
   189  	}
   190  
   191  	if len(base) == 0 {
   192  		return &emptyMethodSet
   193  	}
   194  
   195  	// collect methods
   196  	var list []*Selection
   197  	for _, m := range base {
   198  		if m != nil {
   199  			m.recv = T
   200  			list = append(list, m)
   201  		}
   202  	}
   203  	// sort by unique name
   204  	sort.Slice(list, func(i, j int) bool {
   205  		return list[i].obj.Id() < list[j].obj.Id()
   206  	})
   207  	return &MethodSet{list}
   208  }
   209  
   210  // A fieldSet is a set of fields and name collisions.
   211  // A collision indicates that multiple fields with the
   212  // same unique id appeared.
   213  type fieldSet map[string]*Var // a nil entry indicates a name collision
   214  
   215  // Add adds field f to the field set s.
   216  // If multiples is set, f appears multiple times
   217  // and is treated as a collision.
   218  func (s fieldSet) add(f *Var, multiples bool) fieldSet {
   219  	if s == nil {
   220  		s = make(fieldSet)
   221  	}
   222  	key := f.Id()
   223  	// if f is not in the set, add it
   224  	if !multiples {
   225  		if _, found := s[key]; !found {
   226  			s[key] = f
   227  			return s
   228  		}
   229  	}
   230  	s[key] = nil // collision
   231  	return s
   232  }
   233  
   234  // A methodSet is a set of methods and name collisions.
   235  // A collision indicates that multiple methods with the
   236  // same unique id appeared.
   237  type methodSet map[string]*Selection // a nil entry indicates a name collision
   238  
   239  // Add adds all functions in list to the method set s.
   240  // If multiples is set, every function in list appears multiple times
   241  // and is treated as a collision.
   242  func (s methodSet) add(list []*Func, index []int, indirect bool, multiples bool) methodSet {
   243  	if len(list) == 0 {
   244  		return s
   245  	}
   246  	if s == nil {
   247  		s = make(methodSet)
   248  	}
   249  	for i, f := range list {
   250  		key := f.Id()
   251  		// if f is not in the set, add it
   252  		if !multiples {
   253  			// TODO(gri) A found method may not be added because it's not in the method set
   254  			// (!indirect && ptrRecv(f)). A 2nd method on the same level may be in the method
   255  			// set and may not collide with the first one, thus leading to a false positive.
   256  			// Is that possible? Investigate.
   257  			if _, found := s[key]; !found && (indirect || !ptrRecv(f)) {
   258  				s[key] = &Selection{MethodVal, nil, f, concat(index, i), indirect}
   259  				continue
   260  			}
   261  		}
   262  		s[key] = nil // collision
   263  	}
   264  	return s
   265  }
   266  
   267  // ptrRecv reports whether the receiver is of the form *T.
   268  func ptrRecv(f *Func) bool {
   269  	// If a method's receiver type is set, use that as the source of truth for the receiver.
   270  	// Caution: Checker.funcDecl (decl.go) marks a function by setting its type to an empty
   271  	// signature. We may reach here before the signature is fully set up: we must explicitly
   272  	// check if the receiver is set (we cannot just look for non-nil f.typ).
   273  	if sig, _ := f.typ.(*Signature); sig != nil && sig.recv != nil {
   274  		_, isPtr := deref(sig.recv.typ)
   275  		return isPtr
   276  	}
   277  
   278  	// If a method's type is not set it may be a method/function that is:
   279  	// 1) client-supplied (via NewFunc with no signature), or
   280  	// 2) internally created but not yet type-checked.
   281  	// For case 1) we can't do anything; the client must know what they are doing.
   282  	// For case 2) we can use the information gathered by the resolver.
   283  	return f.hasPtrRecv
   284  }
   285  

View as plain text