func deopt(typ Type) (Type, bool) {
	if p, _ := typ.(*Optional); p != nil {
		return p.elem, true
	}
	return typ, false
}
deopt dereferences typ if it is a *Optioanl and returns its elem and true.
Otherwise it returns (typ, false).
package types
import (
	"fmt"
	"strings"
)
func LookupFieldOrMethod(T Type, addressable bool, pkg *Package, name string) (obj Object, index []int, indirect bool) {
	if t, _ := T.(*Named); t != nil {
		var t Type = t
		if o, _ := t.Underlying().(*Optional); o != nil {
			t = o.elem
		}
		if p, _ := t.Underlying().(*Pointer); p != nil {
			obj, index, indirect = lookupFieldOrMethod(p, false, pkg, name)
			if _, ok := obj.(*Func); ok {
				return nil, nil, false
			}
			return
		}
	}
	return lookupFieldOrMethod(T, addressable, pkg, name)
}
func lookupFieldOrMethod(T Type, addressable bool, pkg *Package, name string) (obj Object, index []int, indirect bool) {
	if name == "_" {
		return  
	}
	typ, isOpt := deopt(T)
	typ, isPtr := deref(typ)
	if isPtr && IsInterface(typ) {
		return
	}
	current := []embeddedType{{typ, nil, isPtr, isOpt, false}}
	var seen map[*Named]bool
	for len(current) > 0 {
		var next []embeddedType  
		for _, e := range current {
			typ := e.typ
			if named, _ := typ.(*Named); named != nil {
				if seen[named] {
					continue
				}
				if seen == nil {
					seen = make(map[*Named]bool)
				}
				seen[named] = true
				if i, m := lookupMethod(named.methods, pkg, name); m != nil {
					assert(m.typ != nil)
					index = concat(e.index, i)
					if obj != nil || e.multiples {
						return nil, index, false  
					}
					if e.opt && !isOptional(m.typ.(*Signature).recv.typ) {
						continue
					}
					obj = m
					indirect = e.indirect
					continue  
				}
				typ = named.underlying
			}
			switch t := typ.(type) {
			case *Struct:
				for i, f := range t.fields {
					if !isOpt && f.sameId(pkg, name) {
						assert(f.typ != nil)
						index = concat(e.index, i)
						if obj != nil || e.multiples {
							return nil, index, false  
						}
						obj = f
						indirect = e.indirect
						continue  
					}
					if obj == nil && f.anonymous {
						typ, isOpt := deopt(f.typ)
						typ, isPtr := deref(f.typ)
						next = append(next, embeddedType{typ, concat(e.index, i), e.indirect || isPtr, isOpt, e.multiples})
					}
				}
			case *Interface:
				if i, m := lookupMethod(t.allMethods, pkg, name); m != nil {
					assert(m.typ != nil)
					index = concat(e.index, i)
					if obj != nil || e.multiples {
						return nil, index, false  
					}
					obj = m
					indirect = e.indirect
				}
			}
		}
		if obj != nil {
			if f, _ := obj.(*Func); f != nil {
				var isPtrRecv bool
				if optRecv(f) {
					unwrapped, _ := deopt(f.typ.(*Signature).recv.typ)
					_, isPtrRecv = unwrapped.(*Pointer)
				} else if isOpt {
					return nil, nil, true  
				} else {
					isPtrRecv = ptrRecv(f)
				}
				if isPtrRecv && !indirect && !addressable {
					return nil, nil, true  
				}
			}
			return
		}
		current = consolidateMultiples(next)
	}
	return nil, nil, false  
}
type embeddedType struct {
	typ       Type
	index     []int  
	indirect  bool   
	opt       bool   
	multiples bool   
}
func consolidateMultiples(list []embeddedType) []embeddedType {
	if len(list) <= 1 {
		return list  
	}
	n := 0                      
	prev := make(map[Type]int)  
	for _, e := range list {
		if i, found := lookupType(prev, e.typ); found {
			list[i].multiples = true
		} else {
			prev[e.typ] = n
			list[n] = e
			n++
		}
	}
	return list[:n]
}
func lookupType(m map[Type]int, typ Type) (int, bool) {
	if i, found := m[typ]; found {
		return i, true
	}
	for t, i := range m {
		if Identical(t, typ) {
			return i, true
		}
	}
	return 0, false
}
func MissingMethod(V Type, T *Interface, static bool) (method *Func, wrongType bool) {
	if T.Empty() {
		return
	}
	if ityp, _ := V.Underlying().(*Interface); ityp != nil {
		for _, m := range T.allMethods {
			_, obj := lookupMethod(ityp.allMethods, m.pkg, m.name)
			switch {
			case obj == nil:
				if static {
					return m, false
				}
			case !Identical(obj.Type(), m.typ):
				return m, true
			}
		}
		return
	}
	for _, m := range T.allMethods {
		obj, _, _ := lookupFieldOrMethod(V, false, m.pkg, m.name)
		f, _ := obj.(*Func)
		if f == nil {
			return m, false
		}
		if !Identical(f.typ, m.typ) {
			return m, true
		}
	}
	return
}
func assertableTo(V *Interface, T Type) (method *Func, wrongType bool, needsOptional []OptionablePath) {
	_, needsOptional = FindOptionables(T)
	if len(needsOptional) > 0 {
		return
	}
	if _, ok := T.Underlying().(*Interface); ok && !strict {
		return
	}
	method, wrongType = MissingMethod(T, V, false)
	return
}
type OptionablePath []OptionablePathStep
func (p OptionablePath) String() string {
	var s []string
	for _, st := range p {
		s = append(s, st.String())
	}
	return strings.Join(s, "'s ")
}
type OptionablePathStep struct {
	Type Type
	Key bool
	Field int
	Param int
}
func (st OptionablePathStep) String() string {
	switch typ := st.Type.(type) {
	case *Pointer:
		return "pointee"
	case *Map:
		if st.Key {
			return "key"
		}
		return "value"
	case *Struct:
		return "field " + typ.Field(st.Field).Name()
	case *Interface:
		argOrRet := "argument"
		i := st.Param + 1
		if st.Param < 0 {
			argOrRet = "return type"
			i = -st.Param
		}
		return fmt.Sprintf("method %s's #%d %s", typ.Method(st.Field).Name(), i, argOrRet)
	case *Signature:
		argOrRet := "argument"
		i := st.Param + 1
		if st.Param < 0 {
			argOrRet = "return type"
			i = -st.Param
		}
		return fmt.Sprintf("#%d %s", i, argOrRet)
	default:
		return "element"
	}
}
func FindOptionables(T Type) (checkable, uncheckable []OptionablePath) {
	findOptionables2(T, nil, false, false, &checkable, &uncheckable)
	return
}
func findOptionables2(T Type, path []OptionablePathStep, allUncheckable bool, wrapped bool, checkable, uncheckable *[]OptionablePath) {
	if allUncheckable {
		checkable = uncheckable
	}
	switch T := T.(type) {
	case *Pointer:
		if !wrapped {
			*checkable = append(*checkable, path)
		}
		findOptionables2(T.Elem(), append(path, OptionablePathStep{Type: T}), allUncheckable, false, checkable, uncheckable)
	case *Map:
		if !wrapped {
			*checkable = append(*checkable, path)
		}
		findOptionables2(T.Key(), append(path, OptionablePathStep{Key: true, Type: T}), true, false, checkable, uncheckable)
		findOptionables2(T.Elem(), append(path, OptionablePathStep{Type: T}), true, false, checkable, uncheckable)
	case *Signature:
		if !wrapped {
			*checkable = append(*checkable, path)
		}
		for i := 0; i < T.Params().Len(); i++ {
			findOptionables2(T.Params().At(i).Type(), append(path, OptionablePathStep{Param: i, Type: T}), true, false, checkable, uncheckable)
		}
		for i := 0; i < T.Results().Len(); i++ {
			findOptionables2(T.Results().At(i).Type(), append(path, OptionablePathStep{Param: -1 - i, Type: T}), true, false, checkable, uncheckable)
		}
	case *Interface:
		if !wrapped {
			*checkable = append(*checkable, path)
		}
		for mi := 0; mi < T.NumMethods(); mi++ {
			f := T.Method(mi).Type().(*Signature)
			for i := 0; i < f.Params().Len(); i++ {
				findOptionables2(f.Params().At(i).Type(), append(path, OptionablePathStep{Field: mi, Param: i, Type: T}), true, false, checkable, uncheckable)
			}
			for i := 0; i < f.Results().Len(); i++ {
				findOptionables2(f.Results().At(i).Type(), append(path, OptionablePathStep{Field: mi, Param: -1 - i, Type: T}), true, false, checkable, uncheckable)
			}
		}
	case *Slice:
		findOptionables2(T.Elem(), append(path, OptionablePathStep{Type: T}), true, false, checkable, uncheckable)
	case *Array:
		findOptionables2(T.Elem(), append(path, OptionablePathStep{Type: T}), true, false, checkable, uncheckable)
	case *Chan:
		if !wrapped {
			*checkable = append(*checkable, path)
		}
		findOptionables2(T.Elem(), append(path, OptionablePathStep{Type: T}), true, false, checkable, uncheckable)
	case *Struct:
		for i, f := range T.fields {
			findOptionables2(f.Type(), append(path, OptionablePathStep{Field: i, Type: T}), allUncheckable, false, checkable, uncheckable)
		}
	case *Named:
		if !wrapped && IsOptionable(T.Underlying()) {
			*checkable = append(*checkable, path)
		}
	case *Optional:
		findOptionables2(T.Elem(), path, allUncheckable, true, checkable, uncheckable)
	}
	return
}
func deref(typ Type) (Type, bool) {
	if p, _ := typ.(*Pointer); p != nil {
		return p.base, true
	}
	return typ, false
}