...
Run Format

Source file src/go/types/methodset.go

Documentation: go/types

  // Copyright 2013 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.
  
  // This file implements method sets.
  
  package types
  
  import (
  	"bytes"
  	"fmt"
  	"sort"
  )
  
  // A MethodSet is an ordered set of concrete or abstract (interface) methods;
  // a method is a MethodVal selection, and they are ordered by ascending m.Obj().Id().
  // The zero value for a MethodSet is a ready-to-use empty method set.
  type MethodSet struct {
  	list []*Selection
  }
  
  func (s *MethodSet) String() string {
  	if s.Len() == 0 {
  		return "MethodSet {}"
  	}
  
  	var buf bytes.Buffer
  	fmt.Fprintln(&buf, "MethodSet {")
  	for _, f := range s.list {
  		fmt.Fprintf(&buf, "\t%s\n", f)
  	}
  	fmt.Fprintln(&buf, "}")
  	return buf.String()
  }
  
  // Len returns the number of methods in s.
  func (s *MethodSet) Len() int { return len(s.list) }
  
  // At returns the i'th method in s for 0 <= i < s.Len().
  func (s *MethodSet) At(i int) *Selection { return s.list[i] }
  
  // Lookup returns the method with matching package and name, or nil if not found.
  func (s *MethodSet) Lookup(pkg *Package, name string) *Selection {
  	if s.Len() == 0 {
  		return nil
  	}
  
  	key := Id(pkg, name)
  	i := sort.Search(len(s.list), func(i int) bool {
  		m := s.list[i]
  		return m.obj.Id() >= key
  	})
  	if i < len(s.list) {
  		m := s.list[i]
  		if m.obj.Id() == key {
  			return m
  		}
  	}
  	return nil
  }
  
  // Shared empty method set.
  var emptyMethodSet MethodSet
  
  // NewMethodSet returns the method set for the given type T.
  // It always returns a non-nil method set, even if it is empty.
  func NewMethodSet(T Type) *MethodSet {
  	// WARNING: The code in this function is extremely subtle - do not modify casually!
  	//          This function and lookupFieldOrMethod should be kept in sync.
  
  	// method set up to the current depth, allocated lazily
  	var base methodSet
  
  	typ, isPtr := deref(T)
  
  	// *typ where typ is an interface has no methods.
  	if isPtr && IsInterface(typ) {
  		return &emptyMethodSet
  	}
  
  	// Start with typ as single entry at shallowest depth.
  	current := []embeddedType{{typ, nil, isPtr, false}}
  
  	// Named types that we have seen already, allocated lazily.
  	// Used to avoid endless searches in case of recursive types.
  	// Since only Named types can be used for recursive types, we
  	// only need to track those.
  	// (If we ever allow type aliases to construct recursive types,
  	// we must use type identity rather than pointer equality for
  	// the map key comparison, as we do in consolidateMultiples.)
  	var seen map[*Named]bool
  
  	// collect methods at current depth
  	for len(current) > 0 {
  		var next []embeddedType // embedded types found at current depth
  
  		// field and method sets at current depth, allocated lazily
  		var fset fieldSet
  		var mset methodSet
  
  		for _, e := range current {
  			typ := e.typ
  
  			// If we have a named type, we may have associated methods.
  			// Look for those first.
  			if named, _ := typ.(*Named); named != nil {
  				if seen[named] {
  					// We have seen this type before, at a more shallow depth
  					// (note that multiples of this type at the current depth
  					// were consolidated before). The type at that depth shadows
  					// this same type at the current depth, so we can ignore
  					// this one.
  					continue
  				}
  				if seen == nil {
  					seen = make(map[*Named]bool)
  				}
  				seen[named] = true
  
  				mset = mset.add(named.methods, e.index, e.indirect, e.multiples)
  
  				// continue with underlying type
  				typ = named.underlying
  			}
  
  			switch t := typ.(type) {
  			case *Struct:
  				for i, f := range t.fields {
  					fset = fset.add(f, e.multiples)
  
  					// Embedded fields are always of the form T or *T where
  					// T is a type name. If typ appeared multiple times at
  					// this depth, f.Type appears multiple times at the next
  					// depth.
  					if f.anonymous {
  						typ, isPtr := deref(f.typ)
  						// TODO(gri) optimization: ignore types that can't
  						// have fields or methods (only Named, Struct, and
  						// Interface types need to be considered).
  						next = append(next, embeddedType{typ, concat(e.index, i), e.indirect || isPtr, e.multiples})
  					}
  				}
  
  			case *Interface:
  				mset = mset.add(t.allMethods, e.index, true, e.multiples)
  			}
  		}
  
  		// Add methods and collisions at this depth to base if no entries with matching
  		// names exist already.
  		for k, m := range mset {
  			if _, found := base[k]; !found {
  				// Fields collide with methods of the same name at this depth.
  				if _, found := fset[k]; found {
  					m = nil // collision
  				}
  				if base == nil {
  					base = make(methodSet)
  				}
  				base[k] = m
  			}
  		}
  
  		// Multiple fields with matching names collide at this depth and shadow all
  		// entries further down; add them as collisions to base if no entries with
  		// matching names exist already.
  		for k, f := range fset {
  			if f == nil {
  				if _, found := base[k]; !found {
  					if base == nil {
  						base = make(methodSet)
  					}
  					base[k] = nil // collision
  				}
  			}
  		}
  
  		current = consolidateMultiples(next)
  	}
  
  	if len(base) == 0 {
  		return &emptyMethodSet
  	}
  
  	// collect methods
  	var list []*Selection
  	for _, m := range base {
  		if m != nil {
  			m.recv = T
  			list = append(list, m)
  		}
  	}
  	sort.Sort(byUniqueName(list))
  	return &MethodSet{list}
  }
  
  // A fieldSet is a set of fields and name collisions.
  // A collision indicates that multiple fields with the
  // same unique id appeared.
  type fieldSet map[string]*Var // a nil entry indicates a name collision
  
  // Add adds field f to the field set s.
  // If multiples is set, f appears multiple times
  // and is treated as a collision.
  func (s fieldSet) add(f *Var, multiples bool) fieldSet {
  	if s == nil {
  		s = make(fieldSet)
  	}
  	key := f.Id()
  	// if f is not in the set, add it
  	if !multiples {
  		if _, found := s[key]; !found {
  			s[key] = f
  			return s
  		}
  	}
  	s[key] = nil // collision
  	return s
  }
  
  // A methodSet is a set of methods and name collisions.
  // A collision indicates that multiple methods with the
  // same unique id appeared.
  type methodSet map[string]*Selection // a nil entry indicates a name collision
  
  // Add adds all functions in list to the method set s.
  // If multiples is set, every function in list appears multiple times
  // and is treated as a collision.
  func (s methodSet) add(list []*Func, index []int, indirect bool, multiples bool) methodSet {
  	if len(list) == 0 {
  		return s
  	}
  	if s == nil {
  		s = make(methodSet)
  	}
  	for i, f := range list {
  		key := f.Id()
  		// if f is not in the set, add it
  		if !multiples {
  			// TODO(gri) A found method may not be added because it's not in the method set
  			// (!indirect && ptrRecv(f)). A 2nd method on the same level may be in the method
  			// set and may not collide with the first one, thus leading to a false positive.
  			// Is that possible? Investigate.
  			if _, found := s[key]; !found && (indirect || !ptrRecv(f)) {
  				s[key] = &Selection{MethodVal, nil, f, concat(index, i), indirect}
  				continue
  			}
  		}
  		s[key] = nil // collision
  	}
  	return s
  }
  
  // ptrRecv reports whether the receiver is of the form *T.
  // The receiver must exist.
  func ptrRecv(f *Func) bool {
  	_, isPtr := deref(f.typ.(*Signature).recv.typ)
  	return isPtr
  }
  
  // byUniqueName function lists can be sorted by their unique names.
  type byUniqueName []*Selection
  
  func (a byUniqueName) Len() int           { return len(a) }
  func (a byUniqueName) Less(i, j int) bool { return a[i].obj.Id() < a[j].obj.Id() }
  func (a byUniqueName) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
  

View as plain text