...
Run Format

Source file src/go/types/methodset.go

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

View as plain text