...
Run Format

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  	"bytes"
    11  	"fmt"
    12  	"sort"
    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 bytes.Buffer
    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  // NewMethodSet returns the method set for the given type T.
    66  // It always returns a non-nil method set, even if it is empty.
    67  func NewMethodSet(T Type) *MethodSet {
    68  	// WARNING: The code in this function is extremely subtle - do not modify casually!
    69  	//          This function and lookupFieldOrMethod should be kept in sync.
    70  
    71  	// method set up to the current depth, allocated lazily
    72  	var base methodSet
    73  
    74  	typ, isPtr := deref(T)
    75  
    76  	// *typ where typ is an interface has no methods.
    77  	if isPtr && IsInterface(typ) {
    78  		return &emptyMethodSet
    79  	}
    80  
    81  	// Start with typ as single entry at shallowest depth.
    82  	current := []embeddedType{{typ, nil, isPtr, false}}
    83  
    84  	// Named types that we have seen already, allocated lazily.
    85  	// Used to avoid endless searches in case of recursive types.
    86  	// Since only Named types can be used for recursive types, we
    87  	// only need to track those.
    88  	// (If we ever allow type aliases to construct recursive types,
    89  	// we must use type identity rather than pointer equality for
    90  	// the map key comparison, as we do in consolidateMultiples.)
    91  	var seen map[*Named]bool
    92  
    93  	// collect methods at current depth
    94  	for len(current) > 0 {
    95  		var next []embeddedType // embedded types found at current depth
    96  
    97  		// field and method sets at current depth, allocated lazily
    98  		var fset fieldSet
    99  		var mset methodSet
   100  
   101  		for _, e := range current {
   102  			typ := e.typ
   103  
   104  			// If we have a named type, we may have associated methods.
   105  			// Look for those first.
   106  			if named, _ := typ.(*Named); named != nil {
   107  				if seen[named] {
   108  					// We have seen this type before, at a more shallow depth
   109  					// (note that multiples of this type at the current depth
   110  					// were consolidated before). The type at that depth shadows
   111  					// this same type at the current depth, so we can ignore
   112  					// this one.
   113  					continue
   114  				}
   115  				if seen == nil {
   116  					seen = make(map[*Named]bool)
   117  				}
   118  				seen[named] = true
   119  
   120  				mset = mset.add(named.methods, e.index, e.indirect, e.multiples)
   121  
   122  				// continue with underlying type
   123  				typ = named.underlying
   124  			}
   125  
   126  			switch t := typ.(type) {
   127  			case *Struct:
   128  				for i, f := range t.fields {
   129  					fset = fset.add(f, e.multiples)
   130  
   131  					// Embedded fields are always of the form T or *T where
   132  					// T is a type name. If typ appeared multiple times at
   133  					// this depth, f.Type appears multiple times at the next
   134  					// depth.
   135  					if f.anonymous {
   136  						typ, isPtr := deref(f.typ)
   137  						// TODO(gri) optimization: ignore types that can't
   138  						// have fields or methods (only Named, Struct, and
   139  						// Interface types need to be considered).
   140  						next = append(next, embeddedType{typ, concat(e.index, i), e.indirect || isPtr, e.multiples})
   141  					}
   142  				}
   143  
   144  			case *Interface:
   145  				mset = mset.add(t.allMethods, e.index, true, e.multiples)
   146  			}
   147  		}
   148  
   149  		// Add methods and collisions at this depth to base if no entries with matching
   150  		// names exist already.
   151  		for k, m := range mset {
   152  			if _, found := base[k]; !found {
   153  				// Fields collide with methods of the same name at this depth.
   154  				if _, found := fset[k]; found {
   155  					m = nil // collision
   156  				}
   157  				if base == nil {
   158  					base = make(methodSet)
   159  				}
   160  				base[k] = m
   161  			}
   162  		}
   163  
   164  		// Multiple fields with matching names collide at this depth and shadow all
   165  		// entries further down; add them as collisions to base if no entries with
   166  		// matching names exist already.
   167  		for k, f := range fset {
   168  			if f == nil {
   169  				if _, found := base[k]; !found {
   170  					if base == nil {
   171  						base = make(methodSet)
   172  					}
   173  					base[k] = nil // collision
   174  				}
   175  			}
   176  		}
   177  
   178  		current = consolidateMultiples(next)
   179  	}
   180  
   181  	if len(base) == 0 {
   182  		return &emptyMethodSet
   183  	}
   184  
   185  	// collect methods
   186  	var list []*Selection
   187  	for _, m := range base {
   188  		if m != nil {
   189  			m.recv = T
   190  			list = append(list, m)
   191  		}
   192  	}
   193  	// sort by unique name
   194  	sort.Slice(list, func(i, j int) bool {
   195  		return list[i].obj.Id() < list[j].obj.Id()
   196  	})
   197  	return &MethodSet{list}
   198  }
   199  
   200  // A fieldSet is a set of fields and name collisions.
   201  // A collision indicates that multiple fields with the
   202  // same unique id appeared.
   203  type fieldSet map[string]*Var // a nil entry indicates a name collision
   204  
   205  // Add adds field f to the field set s.
   206  // If multiples is set, f appears multiple times
   207  // and is treated as a collision.
   208  func (s fieldSet) add(f *Var, multiples bool) fieldSet {
   209  	if s == nil {
   210  		s = make(fieldSet)
   211  	}
   212  	key := f.Id()
   213  	// if f is not in the set, add it
   214  	if !multiples {
   215  		if _, found := s[key]; !found {
   216  			s[key] = f
   217  			return s
   218  		}
   219  	}
   220  	s[key] = nil // collision
   221  	return s
   222  }
   223  
   224  // A methodSet is a set of methods and name collisions.
   225  // A collision indicates that multiple methods with the
   226  // same unique id appeared.
   227  type methodSet map[string]*Selection // a nil entry indicates a name collision
   228  
   229  // Add adds all functions in list to the method set s.
   230  // If multiples is set, every function in list appears multiple times
   231  // and is treated as a collision.
   232  func (s methodSet) add(list []*Func, index []int, indirect bool, multiples bool) methodSet {
   233  	if len(list) == 0 {
   234  		return s
   235  	}
   236  	if s == nil {
   237  		s = make(methodSet)
   238  	}
   239  	for i, f := range list {
   240  		key := f.Id()
   241  		// if f is not in the set, add it
   242  		if !multiples {
   243  			// TODO(gri) A found method may not be added because it's not in the method set
   244  			// (!indirect && ptrRecv(f)). A 2nd method on the same level may be in the method
   245  			// set and may not collide with the first one, thus leading to a false positive.
   246  			// Is that possible? Investigate.
   247  			if _, found := s[key]; !found && (indirect || !ptrRecv(f)) {
   248  				s[key] = &Selection{MethodVal, nil, f, concat(index, i), indirect}
   249  				continue
   250  			}
   251  		}
   252  		s[key] = nil // collision
   253  	}
   254  	return s
   255  }
   256  
   257  // ptrRecv reports whether the receiver is of the form *T.
   258  // The receiver must exist.
   259  func ptrRecv(f *Func) bool {
   260  	_, isPtr := deref(f.typ.(*Signature).recv.typ)
   261  	return isPtr
   262  }
   263  

View as plain text