// 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 (
	
	
	
)

// 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 ( *MethodSet) () string {
	if .Len() == 0 {
		return "MethodSet {}"
	}

	var  strings.Builder
	fmt.Fprintln(&, "MethodSet {")
	for ,  := range .list {
		fmt.Fprintf(&, "\t%s\n", )
	}
	fmt.Fprintln(&, "}")
	return .String()
}

// Len returns the number of methods in s.
func ( *MethodSet) () int { return len(.list) }

// At returns the i'th method in s for 0 <= i < s.Len().
func ( *MethodSet) ( int) *Selection { return .list[] }

// Lookup returns the method with matching package and name, or nil if not found.
func ( *MethodSet) ( *Package,  string) *Selection {
	if .Len() == 0 {
		return nil
	}

	 := Id(, )
	 := sort.Search(len(.list), func( int) bool {
		 := .list[]
		return .obj.Id() >= 
	})
	if  < len(.list) {
		 := .list[]
		if .obj.Id() ==  {
			return 
		}
	}
	return nil
}

// Shared empty method set.
var emptyMethodSet MethodSet

// Note: NewMethodSet is intended for external use only as it
//       requires interfaces to be complete. It may be used
//       internally if LookupFieldOrMethod completed the same
//       interfaces beforehand.

// NewMethodSet returns the method set for the given type T.
// It always returns a non-nil method set, even if it is empty.
func ( Type) *MethodSet {
	// WARNING: The code in this function is extremely subtle - do not modify casually!
	//          This function and lookupFieldOrMethod should be kept in sync.

	// TODO(rfindley) confirm that this code is in sync with lookupFieldOrMethod
	//                with respect to type params.

	// Methods cannot be associated with a named pointer type.
	// (spec: "The type denoted by T is called the receiver base type;
	// it must not be a pointer or interface type and it must be declared
	// in the same package as the method.").
	if  := asNamed();  != nil && isPointer() {
		return &emptyMethodSet
	}

	// method set up to the current depth, allocated lazily
	var  methodSet

	,  := deref()

	// *typ where typ is an interface has no methods.
	if  && IsInterface() {
		return &emptyMethodSet
	}

	// Start with typ as single entry at shallowest depth.
	 := []embeddedType{{, nil, , false}}

	// seen tracks named types that we have seen already, allocated lazily.
	// Used to avoid endless searches in case of recursive types.
	//
	// We must use a lookup on identity rather than a simple map[*Named]bool as
	// instantiated types may be identical but not equal.
	var  instanceLookup

	// collect methods at current depth
	for len() > 0 {
		var  []embeddedType // embedded types found at current depth

		// field and method sets at current depth, indexed by names (Id's), and allocated lazily
		var  map[string]bool // we only care about the field names
		var  methodSet

		for ,  := range  {
			 := .typ

			// If we have a named type, we may have associated methods.
			// Look for those first.
			if  := asNamed();  != nil {
				if  := .lookup();  != nil {
					// 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
				}
				.add()

				for  := 0;  < .NumMethods(); ++ {
					 = .addOne(.Method(), concat(.index, ), .indirect, .multiples)
				}
			}

			switch t := under().(type) {
			case *Struct:
				for ,  := range .fields {
					if  == nil {
						 = make(map[string]bool)
					}
					[.Id()] = true

					// 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 .embedded {
						,  := deref(.typ)
						// TODO(gri) optimization: ignore types that can't
						// have fields or methods (only Named, Struct, and
						// Interface types need to be considered).
						 = append(, embeddedType{, concat(.index, ), .indirect || , .multiples})
					}
				}

			case *Interface:
				 = .add(.typeSet().methods, .index, true, .multiples)
			}
		}

		// Add methods and collisions at this depth to base if no entries with matching
		// names exist already.
		for ,  := range  {
			if ,  := []; ! {
				// Fields collide with methods of the same name at this depth.
				if [] {
					 = nil // collision
				}
				if  == nil {
					 = make(methodSet)
				}
				[] = 
			}
		}

		// Add all (remaining) fields at this depth as collisions (since they will
		// hide any method further down) if no entries with matching names exist already.
		for  := range  {
			if ,  := []; ! {
				if  == nil {
					 = make(methodSet)
				}
				[] = nil // collision
			}
		}

		 = consolidateMultiples()
	}

	if len() == 0 {
		return &emptyMethodSet
	}

	// collect methods
	var  []*Selection
	for ,  := range  {
		if  != nil {
			.recv = 
			 = append(, )
		}
	}
	// sort by unique name
	sort.Slice(, func(,  int) bool {
		return [].obj.Id() < [].obj.Id()
	})
	return &MethodSet{}
}

// A methodSet is a set of methods and name collisions.
// A collision indicates that multiple methods with the
// same unique id, or a field with that 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 ( methodSet) ( []*Func,  []int,  bool,  bool) methodSet {
	if len() == 0 {
		return 
	}
	for ,  := range  {
		 = .addOne(, concat(, ), , )
	}
	return 
}

func ( methodSet) ( *Func,  []int,  bool,  bool) methodSet {
	if  == nil {
		 = make(methodSet)
	}
	 := .Id()
	// if f is not in the set, add it
	if ! {
		// TODO(gri) A found method may not be added because it's not in the method set
		// (!indirect && f.hasPtrRecv()). 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 ,  := []; ! && ( || !.hasPtrRecv()) {
			[] = &Selection{MethodVal, nil, , , }
			return 
		}
	}
	[] = nil // collision
	return 
}