package interp

import (
	
	
)

// adot produces an AST dot(1) directed acyclic graph for the given node. For debugging only.
// func (n *node) adot() { n.astDot(dotWriter(n.interp.dotCmd), n.ident) }

// genAST returns a new AST where generic types are replaced by instantiated types.
func genAST( *scope,  *node,  []*itype) (*node, bool, error) {
	 := map[string]*node{}
	 := 0
	 := ""
	 := ""
	 := false
	 := []*node{}
	var  func(*node, *node) (*node, error)
	 := .child[0].ident + "["
	if .kind == funcDecl {
		 = .child[1].ident + "["
	}

	// Input type parameters must be resolved prior AST generation, as compilation
	// of generated AST may occur in a different scope.
	for ,  := range  {
		 += .id() + ","
	}
	 = strings.TrimSuffix(, ",") + "]"

	 = func(,  *node) (*node, error) {
		 := copyNode(, , false)
		switch .kind {
		case funcDecl, funcType:
			.val = 

		case identExpr:
			// Replace generic type by instantiated one.
			,  := [.ident]
			if ! {
				break
			}
			 = copyNode(, , true)
			.typ = .typ

		case indexExpr:
			// Catch a possible recursive generic type definition
			if .kind != typeSpec {
				break
			}
			if .child[0].ident != .child[0].ident {
				break
			}
			 := copyNode(.child[0], , false)
			 = append(, )
			return , nil

		case fieldList:
			//  Node is the type parameters list of a generic function.
			if .kind == funcDecl && .anc == .child[2] && childPos() == 0 {
				// Fill the types lookup table used for type substitution.
				for ,  := range .child {
					 := len(.child) - 1
					for ,  := range .child[:] {
						if  >= len() {
							return nil, .cfgErrorf("undefined type for %s", .ident)
						}
						,  := nodeType(.interp, , .child[])
						if  != nil {
							return nil, 
						}
						if  := checkConstraint([], );  != nil {
							return nil, 
						}
						[.ident] = copyNode(, .anc, false)
						[.ident].ident = [].id()
						[.ident].typ = []
						++
					}
				}
				// Skip type parameters specification, so generated func doesn't look generic.
				return , nil
			}

			// Node is the receiver of a generic method.
			if .kind == funcDecl && .anc ==  && childPos() == 0 && len(.child) > 0 {
				 := .child[0].child[1]
				// Method receiver is a generic type if it takes some type parameters.
				if .kind == indexExpr || .kind == indexListExpr || (.kind == starExpr && (.child[0].kind == indexExpr || .child[0].kind == indexListExpr)) {
					if .kind == starExpr {
						// Method receiver is a pointer on a generic type.
						 = .child[0]
						 = true
					}
					 = .child[0].ident + "["
					for ,  := range .child[1:] {
						if  >= len() {
							return nil, .cfgErrorf("undefined type for %s", .ident)
						}
						 := []
						[.ident] = copyNode(, .anc, false)
						[.ident].ident = .id()
						[.ident].typ = 
						 += .id() + ","
						++
					}
					 = strings.TrimSuffix(, ",") + "]"
				}
			}

			// Node is the type parameters list of a generic type.
			if .kind == typeSpec && .anc ==  && childPos() == 1 {
				// Fill the types lookup table used for type substitution.
				 = .anc.child[0].ident + "["
				for ,  := range .child {
					 := len(.child) - 1
					for ,  := range .child[:] {
						if  >= len() {
							return nil, .cfgErrorf("undefined type for %s", .ident)
						}
						 := []
						,  := nodeType(.interp, , .child[])
						if  != nil {
							return nil, 
						}
						if  := checkConstraint([], );  != nil {
							return nil, 
						}
						[.ident] = copyNode(, .anc, false)
						[.ident].ident = .id()
						[.ident].typ = 
						 += .id() + ","
						++
					}
				}
				 = strings.TrimSuffix(, ",") + "]"
				return , nil
			}
		}

		for ,  := range .child {
			,  := (, )
			if  != nil {
				return nil, 
			}
			.child = append(.child, )
		}
		return , nil
	}

	if ,  := .interp.generic[];  {
		return , true, nil
	}

	,  := (, .anc)
	if  != nil {
		return nil, false, 
	}
	.interp.generic[] = 
	.param = append(.param, ...)
	if  != "" {
		for ,  := range  {
			.ident = 
		}
		.child[0].ident = 
	}
	if  != "" {
		// Replace method receiver type by synthetized ident.
		 := .child[0].child[0].child[1]
		if  {
			 = .child[0]
		}
		.kind = identExpr
		.ident = 
		.child = nil
	}
	// r.adot() // Used for debugging only.
	return , false, nil
}

func copyNode(,  *node,  bool) *node {
	var  interface{}
	 := atomic.AddInt64(&.interp.nindex, 1)
	 := &node{
		debug:  .debug,
		anc:    ,
		interp: .interp,
		index:  ,
		level:  .level,
		nleft:  .nleft,
		nright: .nright,
		kind:   .kind,
		pos:    .pos,
		action: .action,
		gen:    .gen,
		val:    &,
		rval:   .rval,
		ident:  .ident,
		meta:   .meta,
	}
	.start = 
	if  {
		for ,  := range .child {
			.child = append(.child, (, , true))
		}
	}
	return 
}

func inferTypesFromCall( *scope,  *node,  []*node) ([]*itype, error) {
	 := .typ.node
	// Fill the map of parameter types, indexed by type param ident.
	 := map[string]*itype{}
	for ,  := range .child[0].child {
		,  := nodeType(.interp, , .lastChild())
		if  != nil {
			return nil, 
		}
		for ,  := range .child[:len(.child)-1] {
			[.ident] = 
		}
	}

	var  func(*itype, *itype) ([]*itype, error)
	 = func(,  *itype) ([]*itype, error) {
		switch .cat {
		case chanT, ptrT, sliceT:
			return (.val, .val)

		case mapT:
			,  := (.key, .key)
			if  != nil {
				return nil, 
			}
			,  := (.val, .val)
			if  != nil {
				return nil, 
			}
			return append(, ...), nil

		case structT:
			 := []*itype{}
			for ,  := range .field {
				,  := (.typ, .field[].typ)
				if  != nil {
					return nil, 
				}
				 = append(, ...)
			}
			return , nil

		case funcT:
			 := []*itype{}
			for ,  := range .arg {
				if  >= len(.arg) {
					break
				}
				,  := (, .arg[])
				if  != nil {
					return nil, 
				}
				 = append(, ...)
			}
			for ,  := range .ret {
				if  >= len(.ret) {
					break
				}
				,  := (, .ret[])
				if  != nil {
					return nil, 
				}
				 = append(, ...)
			}
			return , nil

		case nilT:
			if [.name] != nil {
				return []*itype{}, nil
			}

		case genericT:
			return []*itype{}, nil
		}
		return nil, nil
	}

	 := []*itype{}
	for ,  := range .child[1].child {
		,  := nodeType(.interp, , .lastChild())
		if  != nil {
			return nil, 
		}
		,  := (, [].typ)
		if  != nil {
			return nil, 
		}
		 = append(, ...)
	}

	return , nil
}

func checkConstraint(,  *itype) error {
	if len(.constraint) == 0 && len(.ulconstraint) == 0 {
		return nil
	}
	for ,  := range .constraint {
		if .equals() || .matchDefault() {
			return nil
		}
	}
	for ,  := range .ulconstraint {
		if .underlying().equals() || .matchDefault() {
			return nil
		}
	}
	return .node.cfgErrorf("%s does not implement %s", .id(), .id())
}