// WalkExprs calls the function f on all expressions under x. If the function f
// returns true, AST nodes under the last node will not be visited.
557033
func WalkExprs(x interface{}, f func(*Expr) bool) {
	vis := &GenericVisitor{func(x interface{}) bool {
		if r, ok := x.(*Expr); ok {
			return f(r)
		}
		return false
	}}
	Walk(vis, x)
}
334790
func (m *FuncNode) Expr() *Expr {
	fe := &Expr{Op: lex.TokenUdfExpr.String()}
	if len(m.Args) > 0 {
		fe.Args = []*Expr{{Identity: m.Name}}
		fe.Args = append(fe.Args, ExprsFromNodes(m.Args)...)
	}
	return fe
}
645272
func check_type_expr(e ast.Expr) bool {
	switch t := e.(type) {
	case *ast.StarExpr:
		return check_type_expr(t.X)
	case *ast.ArrayType:
		return check_type_expr(t.Elt)
	case *ast.SelectorExpr:
		return check_type_expr(t.X)
	case *ast.FuncType:
		a := check_func_field_list(t.Params)
		b := check_func_field_list(t.Results)
		return a && b
	case *ast.MapType:
		a := check_type_expr(t.Key)
		b := check_type_expr(t.Value)
		return a && b
	case *ast.Ellipsis:
		return check_type_expr(t.Elt)
	case *ast.ChanType:
		return check_type_expr(t.Value)
	case *ast.BadExpr:
		return false
	default:
		return true
	}
}
20788
func (p *parser) parseFilterExpr(n node) node {
	opnd := p.parsePrimaryExpr(n)
	if p.r.typ == itemLBracket {
		opnd = newFilterNode(opnd, p.parsePredicate(opnd))
	}
	return opnd
}
300280
func Inspect(expr Expression, f func(Expression) bool) {
	Walk(inspector(f), expr)
}
1241386
func (p *parser) checkExpr(x ast.Expr) ast.Expr {
	switch t := unparen(x).(type) {
	case *ast.BadExpr:
	case *ast.Ident:
	case *ast.BasicLit:
	case *ast.FuncLit:
	case *ast.CompositeLit:
	case *ast.ParenExpr:
		panic("unreachable")
	case *ast.SelectorExpr:
	case *ast.IndexExpr:
	case *ast.SliceExpr:
	case *ast.TypeAssertExpr:
		if t.Type == nil {
			// the form X.(type) is only allowed in type switch expressions
			p.errorExpected(x.Pos(), "expression")
			x = &ast.BadExpr{x.Pos(), x.End()}
		}
	case *ast.CallExpr:
	case *ast.StarExpr:
	case *ast.UnaryExpr:
		if t.Op == token.RANGE {
			// the range operator is only allowed at the top of a for statement
			p.errorExpected(x.Pos(), "expression")
			x = &ast.BadExpr{x.Pos(), x.End()}
		}
	case *ast.BinaryExpr:
	default:
		// all other nodes are not proper expressions
		p.errorExpected(x.Pos(), "expression")
		x = &ast.BadExpr{x.Pos(), x.End()}
	}
	return x
}
1182972
func Walk(n Node, f func(Node) bool) {
	if !f(n) {
		return
	}

	// TODO(adonovan): opt: order cases using profile data.
	switch n := n.(type) {
	case *File:
		walkStmts(n.Stmts, f)

	case *ExprStmt:
		Walk(n.X, f)

	case *BranchStmt:
		// no-op

	case *IfStmt:
		Walk(n.Cond, f)
		walkStmts(n.True, f)
		walkStmts(n.False, f)

	case *AssignStmt:
		Walk(n.RHS, f)
		Walk(n.LHS, f)

	case *DefStmt:
		Walk(n.Name, f)
		for _, param := range n.Function.Params {
			Walk(param, f)
		}
		walkStmts(n.Function.Body, f)

	case *ForStmt:
		Walk(n.Vars, f)
		Walk(n.X, f)
		walkStmts(n.Body, f)

	case *ReturnStmt:
		if n.Result != nil {
			Walk(n.Result, f)
		}

	case *LoadStmt:
		Walk(n.Module, f)
		for _, from := range n.From {
			Walk(from, f)
		}
		for _, to := range n.To {
			Walk(to, f)
		}

	case *Ident, *Literal:
		// no-op

	case *ListExpr:
		for _, x := range n.List {
			Walk(x, f)
		}

	case *ParenExpr:
		Walk(n.X, f)

	case *CondExpr:
		Walk(n.Cond, f)
		Walk(n.True, f)
		Walk(n.False, f)

	case *IndexExpr:
		Walk(n.X, f)
		Walk(n.Y, f)

	case *DictEntry:
		Walk(n.Key, f)
		Walk(n.Value, f)

	case *SliceExpr:
		Walk(n.X, f)
		if n.Lo != nil {
			Walk(n.Lo, f)
		}
		if n.Hi != nil {
			Walk(n.Hi, f)
		}
		if n.Step != nil {
			Walk(n.Step, f)
		}

	case *Comprehension:
		for _, clause := range n.Clauses {
			Walk(clause, f)
		}
		Walk(n.Body, f)

	case *IfClause:
		Walk(n.Cond, f)

	case *ForClause:
		Walk(n.Vars, f)
		Walk(n.X, f)

	case *TupleExpr:
		for _, x := range n.List {
			Walk(x, f)
		}

	case *DictExpr:
		for _, entry := range n.List {
			entry := entry.(*DictEntry)
			Walk(entry.Key, f)
			Walk(entry.Value, f)
		}

	case *UnaryExpr:
		Walk(n.X, f)

	case *BinaryExpr:
		Walk(n.X, f)
		Walk(n.Y, f)

	case *DotExpr:
		Walk(n.X, f)
		Walk(n.Name, f)

	case *CallExpr:
		Walk(n.Fn, f)
		for _, arg := range n.Args {
			Walk(arg, f)
		}

	case *LambdaExpr:
		for _, param := range n.Function.Params {
			Walk(param, f)
		}
		walkStmts(n.Function.Body, f)

	default:
		panic(n)
	}

	f(nil)
}
342666
func WalkTerms(x interface{}, f func(*Term) bool) {
	vis := &GenericVisitor{func(x interface{}) bool {
		if term, ok := x.(*Term); ok {
			return f(term)
		}
		return false
	}}
	Walk(vis, x)
}
931566
func WalkRefs(x interface{}, f func(Ref) bool) {
	vis := &GenericVisitor{func(x interface{}) bool {
		if r, ok := x.(Ref); ok {
			return f(r)
		}
		return false
	}}
	Walk(vis, x)
}
1345305
func NewTypeExprFromAst(pkgName string, expr ast.Expr) TypeExpr {
	error := ""
	switch t := expr.(type) {
	case *ast.Ident:
		if IsBuiltinType(t.Name) {
			pkgName = ""
		}
		return TypeExpr{t.Name, pkgName, 0, true}
	case *ast.SelectorExpr:
		e := NewTypeExprFromAst(pkgName, t.X)
		return NewTypeExprFromData(t.Sel.Name, e.Expr, 0, e.Valid)
	case *ast.StarExpr:
		e := NewTypeExprFromAst(pkgName, t.X)
		return NewTypeExprFromData("*"+e.Expr, e.PkgName, e.pkgIndex+1, e.Valid)
	case *ast.ArrayType:
		e := NewTypeExprFromAst(pkgName, t.Elt)
		return NewTypeExprFromData("[]"+e.Expr, e.PkgName, e.pkgIndex+2, e.Valid)
	case *ast.MapType:
		if identKey, ok := t.Key.(*ast.Ident); ok && IsBuiltinType(identKey.Name) {
			e := NewTypeExprFromAst(pkgName, t.Value)
			return NewTypeExprFromData("map["+identKey.Name+"]"+e.Expr, e.PkgName, e.pkgIndex+len("map["+identKey.Name+"]"), e.Valid)
		}
		error = fmt.Sprintf("Failed to generate name for Map field :%v. Make sure the field name is valid.", t.Key)
	case *ast.Ellipsis:
		e := NewTypeExprFromAst(pkgName, t.Elt)
		return NewTypeExprFromData("[]"+e.Expr, e.PkgName, e.pkgIndex+2, e.Valid)
	default:
		error = fmt.Sprintf("Failed to generate name for field: %v Package: %v. Make sure the field name is valid.", expr, pkgName)

	}
	return NewTypeExprFromData(error, "", 0, false)
}
494135
func walkNames(exp Expr) []string {
	switch expr := exp.(type) {
	case *VarRef:
		return []string{expr.Val}
	case *Call:
		var a []string
		for _, expr := range expr.Args {
			if ref, ok := expr.(*VarRef); ok {
				a = append(a, ref.Val)
			}
		}
		return a
	case *BinaryExpr:
		var ret []string
		ret = append(ret, walkNames(expr.LHS)...)
		ret = append(ret, walkNames(expr.RHS)...)
		return ret
	case *ParenExpr:
		return walkNames(expr.Expr)
	}

	return nil
}
184095
func (v *evalVisitor) curExpr() *ast.Expression {
	if len(v.exprs) == 0 {
		return nil
	}

	return v.exprs[len(v.exprs)-1]
}
888225
func walkRefs(exp Expr) []VarRef {
	refs := make(map[VarRef]struct{})
	var walk func(exp Expr)
	walk = func(exp Expr) {
		switch expr := exp.(type) {
		case *VarRef:
			refs[*expr] = struct{}{}
		case *Call:
			for _, expr := range expr.Args {
				if ref, ok := expr.(*VarRef); ok {
					refs[*ref] = struct{}{}
				}
			}
		case *BinaryExpr:
			walk(expr.LHS)
			walk(expr.RHS)
		case *ParenExpr:
			walk(expr.Expr)
		}
	}
	walk(exp)

	// Turn the map into a slice.
	a := make([]VarRef, 0, len(refs))
	for ref := range refs {
		a = append(a, ref)
	}
	return a
}
1185293
func (a *aggregationEliminateChecker) rewriteExpr(ctx sessionctx.Context, aggFunc *aggregation.AggFuncDesc) expression.Expression {
	switch aggFunc.Name {
	case ast.AggFuncCount:
		if aggFunc.Mode == aggregation.FinalMode {
			return a.wrapCastFunction(ctx, aggFunc.Args[0], aggFunc.RetTp)
		}
		return a.rewriteCount(ctx, aggFunc.Args, aggFunc.RetTp)
	case ast.AggFuncSum, ast.AggFuncAvg, ast.AggFuncFirstRow, ast.AggFuncMax, ast.AggFuncMin, ast.AggFuncGroupConcat:
		return a.wrapCastFunction(ctx, aggFunc.Args[0], aggFunc.RetTp)
	case ast.AggFuncBitAnd, ast.AggFuncBitOr, ast.AggFuncBitXor:
		return a.rewriteBitFunc(ctx, aggFunc.Name, aggFunc.Args[0], aggFunc.RetTp)
	default:
		panic("Unsupported function")
	}
}
657751
func Walk(node Node, f func(Node) bool) {
	if !f(node) {
		return
	}

	switch x := node.(type) {
	case *File:
		walkStmts(x.Stmts, x.Last, f)
	case *Comment:
	case *Stmt:
		for _, c := range x.Comments {
			if !x.End().After(c.Pos()) {
				defer Walk(&c, f)
				break
			}
			Walk(&c, f)
		}
		if x.Cmd != nil {
			Walk(x.Cmd, f)
		}
		for _, r := range x.Redirs {
			Walk(r, f)
		}
	case *Assign:
		if x.Name != nil {
			Walk(x.Name, f)
		}
		if x.Value != nil {
			Walk(x.Value, f)
		}
		if x.Index != nil {
			Walk(x.Index, f)
		}
		if x.Array != nil {
			Walk(x.Array, f)
		}
	case *Redirect:
		if x.N != nil {
			Walk(x.N, f)
		}
		Walk(x.Word, f)
		if x.Hdoc != nil {
			Walk(x.Hdoc, f)
		}
	case *CallExpr:
		for _, a := range x.Assigns {
			Walk(a, f)
		}
		walkWords(x.Args, f)
	case *Subshell:
		walkStmts(x.Stmts, x.Last, f)
	case *Block:
		walkStmts(x.Stmts, x.Last, f)
	case *IfClause:
		walkStmts(x.Cond, x.CondLast, f)
		walkStmts(x.Then, x.ThenLast, f)
		if x.Else != nil {
			Walk(x.Else, f)
		}
	case *WhileClause:
		walkStmts(x.Cond, x.CondLast, f)
		walkStmts(x.Do, x.DoLast, f)
	case *ForClause:
		Walk(x.Loop, f)
		walkStmts(x.Do, x.DoLast, f)
	case *WordIter:
		Walk(x.Name, f)
		walkWords(x.Items, f)
	case *CStyleLoop:
		if x.Init != nil {
			Walk(x.Init, f)
		}
		if x.Cond != nil {
			Walk(x.Cond, f)
		}
		if x.Post != nil {
			Walk(x.Post, f)
		}
	case *BinaryCmd:
		Walk(x.X, f)
		Walk(x.Y, f)
	case *FuncDecl:
		Walk(x.Name, f)
		Walk(x.Body, f)
	case *Word:
		for _, wp := range x.Parts {
			Walk(wp, f)
		}
	case *Lit:
	case *SglQuoted:
	case *DblQuoted:
		for _, wp := range x.Parts {
			Walk(wp, f)
		}
	case *CmdSubst:
		walkStmts(x.Stmts, x.Last, f)
	case *ParamExp:
		Walk(x.Param, f)
		if x.Index != nil {
			Walk(x.Index, f)
		}
		if x.Repl != nil {
			if x.Repl.Orig != nil {
				Walk(x.Repl.Orig, f)
			}
			if x.Repl.With != nil {
				Walk(x.Repl.With, f)
			}
		}
		if x.Exp != nil && x.Exp.Word != nil {
			Walk(x.Exp.Word, f)
		}
	case *ArithmExp:
		Walk(x.X, f)
	case *ArithmCmd:
		Walk(x.X, f)
	case *BinaryArithm:
		Walk(x.X, f)
		Walk(x.Y, f)
	case *BinaryTest:
		Walk(x.X, f)
		Walk(x.Y, f)
	case *UnaryArithm:
		Walk(x.X, f)
	case *UnaryTest:
		Walk(x.X, f)
	case *ParenArithm:
		Walk(x.X, f)
	case *ParenTest:
		Walk(x.X, f)
	case *CaseClause:
		Walk(x.Word, f)
		for _, ci := range x.Items {
			Walk(ci, f)
		}
		for _, c := range x.Last {
			Walk(&c, f)
		}
	case *CaseItem:
		for _, c := range x.Comments {
			if c.Pos().After(x.Pos()) {
				defer Walk(&c, f)
				break
			}
			Walk(&c, f)
		}
		walkWords(x.Patterns, f)
		walkStmts(x.Stmts, x.Last, f)
	case *TestClause:
		Walk(x.X, f)
	case *DeclClause:
		walkWords(x.Opts, f)
		for _, a := range x.Assigns {
			Walk(a, f)
		}
	case *ArrayExpr:
		for _, el := range x.Elems {
			Walk(el, f)
		}
		for _, c := range x.Last {
			Walk(&c, f)
		}
	case *ArrayElem:
		for _, c := range x.Comments {
			if c.Pos().After(x.Pos()) {
				defer Walk(&c, f)
				break
			}
			Walk(&c, f)
		}
		if x.Index != nil {
			Walk(x.Index, f)
		}
		if x.Value != nil {
			Walk(x.Value, f)
		}
	case *ExtGlob:
		Walk(x.Pattern, f)
	case *ProcSubst:
		walkStmts(x.Stmts, x.Last, f)
	case *TimeClause:
		if x.Stmt != nil {
			Walk(x.Stmt, f)
		}
	case *CoprocClause:
		if x.Name != nil {
			Walk(x.Name, f)
		}
		Walk(x.Stmt, f)
	case *LetClause:
		for _, expr := range x.Exprs {
			Walk(expr, f)
		}
	default:
		panic(fmt.Sprintf("syntax.Walk: unexpected node type %T", x))
	}

	f(nil)
}
81353
func (xft *XFastTrie) walkUpPredecessor(root, node, predecessor *node) {
	n := predecessor.parent
	for n != nil && n != root {
		if !isInternal(n.children[1]) && n.children[1] != predecessor {
			n.children[1] = node
		}
		n = n.parent
	}
}
934982
func (exp *FuncExpr) All() []Node {
	res := make([]Node, len(exp.Args))
	for i, n := range exp.Args {
		res[i] = n
	}
	return res
}