executor.go

package graphql

import (
	"context"
	"errors"
	"fmt"
	"reflect"
	"slices"
	"strings"
	"sync"
	"time"

	"github.com/sprucehealth/graphql/gqlerrors"
	"github.com/sprucehealth/graphql/language/ast"
)

type ExecuteParams struct {
	Schema            Schema
	Root              any
	AST               *ast.Document
	OperationName     string
	Args              map[string]any
	DeprecatedFieldFn func(ctx context.Context, parent *Object, fieldDef *FieldDefinition) error
	// TODO: Abstract this to possibly handle more types
	FieldDefinitionDirectiveHandler func(context.Context, *ast.Directive, *FieldDefinition) error
	DisallowIntrospection           bool
	EnableCoroutines                bool
	// TimeoutWait is the amount of time to allow for resolvers to handle
	// a context deadline error before the executor does.
	TimeoutWait time.Duration
	Tracer      Tracer
}

func Execute(ctx context.Context, p ExecuteParams) (result *Result) {
	exeContext, err := buildExecutionContext(BuildExecutionCtxParams{
		Schema:                          p.Schema,
		Root:                            p.Root,
		AST:                             p.AST,
		OperationName:                   p.OperationName,
		Args:                            p.Args,
		Errors:                          nil,
		Result:                          result,
		DeprecatedFieldFn:               p.DeprecatedFieldFn,
		FieldDefinitionDirectiveHandler: p.FieldDefinitionDirectiveHandler,
		DisallowIntrospection:           p.DisallowIntrospection,
		Tracer:                          p.Tracer,
		EnableCoroutines:                p.EnableCoroutines,
	})
	if err != nil {
		return &Result{Errors: []gqlerrors.FormattedError{gqlerrors.FormatError(err)}}
	}

	result = &Result{}
	defer func() {
		if r := recover(); r != nil {
			err := gqlerrors.FormatPanic(r)
			exeContext.Errors = append(exeContext.Errors, gqlerrors.FormatError(err))
			result.Errors = exeContext.Errors
		}
	}()

	return executeOperation(ctx, ExecuteOperationParams{
		ExecutionContext: exeContext,
		Root:             p.Root,
		Operation:        exeContext.Operation,
	})
}

type BuildExecutionCtxParams struct {
	Schema            Schema
	Root              any
	AST               *ast.Document
	OperationName     string
	Args              map[string]any
	Errors            []gqlerrors.FormattedError
	Result            *Result
	DeprecatedFieldFn func(context.Context, *Object, *FieldDefinition) error
	// TODO: Abstract this to possibly handle more types
	FieldDefinitionDirectiveHandler func(context.Context, *ast.Directive, *FieldDefinition) error
	DisallowIntrospection           bool
	Tracer                          Tracer
	EnableCoroutines                bool
}

type ExecutionContext struct {
	Schema            Schema
	Fragments         map[string]*ast.FragmentDefinition
	Root              any
	Operation         ast.Definition
	VariableValues    map[string]any
	Errors            []gqlerrors.FormattedError
	DeprecatedFieldFn func(context.Context, *Object, *FieldDefinition) error
	// TODO: Abstract this to possibly handle more types
	FieldDefinitionDirectiveHandler func(context.Context, *ast.Directive, *FieldDefinition) error
	DisallowIntrospection           bool
	Tracer                          Tracer
	EnableCoroutines                bool

	pendingCoroutines queue[*pendingCoroutine]
}

type pendingCoroutine struct {
	resMap     map[string]any
	resKey     string
	path       []string
	runtime    time.Duration
	returnType Type
	fieldASTs  []*ast.Field
	info       ResolveInfo
	co         *coroutine
}

func safeNodeType(n ast.Node) string {
	return strings.TrimPrefix(reflect.TypeOf(n).String(), "*ast.")
}

func buildExecutionContext(p BuildExecutionCtxParams) (*ExecutionContext, error) {
	var operation *ast.OperationDefinition
	fragments := make(map[string]*ast.FragmentDefinition)
	for _, definition := range p.AST.Definitions {
		switch definition := definition.(type) {
		case *ast.OperationDefinition:
			if p.OperationName == "" && operation != nil {
				return nil, errors.New("Must provide operation name if query contains multiple operations.")
			}
			if p.OperationName == "" || definition.GetName() != nil && definition.GetName().Value == p.OperationName {
				operation = definition
			}
		case *ast.FragmentDefinition:
			var key string
			if definition.GetName() != nil && definition.GetName().Value != "" {
				key = definition.GetName().Value
			}
			fragments[key] = definition
		default:
			return nil, fmt.Errorf("GraphQL cannot execute a request containing a %s", safeNodeType(definition))
		}
	}

	if operation == nil {
		if p.OperationName != "" {
			return nil, fmt.Errorf("Unknown operation named %q.", p.OperationName)
		}
		return nil, errors.New("Must provide an operation.")
	}

	variableValues, err := getVariableValues(p.Schema, operation.GetVariableDefinitions(), p.Args)
	if err != nil {
		return nil, err
	}

	return &ExecutionContext{
		Schema:                          p.Schema,
		Fragments:                       fragments,
		Root:                            p.Root,
		Operation:                       operation,
		VariableValues:                  variableValues,
		Errors:                          p.Errors,
		DeprecatedFieldFn:               p.DeprecatedFieldFn,
		FieldDefinitionDirectiveHandler: p.FieldDefinitionDirectiveHandler,
		DisallowIntrospection:           p.DisallowIntrospection,
		Tracer:                          p.Tracer,
		EnableCoroutines:                p.EnableCoroutines,
	}, nil
}

type ExecuteOperationParams struct {
	ExecutionContext *ExecutionContext
	Root             any
	Operation        ast.Definition
}

func executeOperation(ctx context.Context, p ExecuteOperationParams) *Result {
	operationType, err := getOperationRootType(p.ExecutionContext.Schema, p.Operation)
	if err != nil {
		return &Result{Errors: gqlerrors.FormatErrors(err)}
	}

	fields, _ := collectFields(CollectFieldsParams{
		ExeContext:   p.ExecutionContext,
		RuntimeType:  operationType,
		SelectionSet: p.Operation.GetSelectionSet(),
	})

	executeFieldsParams := ExecuteFieldsParams{
		ExecutionContext: p.ExecutionContext,
		ParentType:       operationType,
		Source:           p.Root,
		Fields:           fields,
	}

	res := executeFieldsSerially(ctx, executeFieldsParams, nil)
	eCtx := executeFieldsParams.ExecutionContext
	// Continue any pending coroutines in the order they were paused. The same
	// coroutine may pause again or there may be other coroutines added. This continues
	// until all coroutines complete or the context ends.
	for pend := range eCtx.pendingCoroutines.all() {
		if err := ctx.Err(); err != nil {
			pend.co.stop()
			// Continue looping through all the coroutines to stop them. Each iteration checks
			// the context but that's fine.
			continue
		}
		st := time.Now()
		coSt := pend.co.run()
		pend.runtime += time.Since(st)
		if coSt.done {
			if coSt.err != nil {
				panic(gqlerrors.FormatError(coSt.err))
			}

			completed := completeValueCatchingError(ctx, eCtx, pend.returnType, pend.fieldASTs, pend.info, coSt.res, pend.path)
			pend.resMap[pend.resKey] = completed

			if p.ExecutionContext.Tracer != nil {
				eCtx.Tracer.Trace(ctx, pend.path, time.Since(st))
			}
		} else {
			eCtx.pendingCoroutines.push(pend)
		}
	}
	return res
}

// Extracts the root type of the operation from the schema.
func getOperationRootType(schema Schema, operation ast.Definition) (*Object, error) {
	if operation == nil {
		return nil, errors.New("graphql: can only execute queries and mutations")
	}

	switch operation.GetOperation() {
	case ast.OperationTypeQuery:
		return schema.QueryType(), nil
	case ast.OperationTypeMutation:
		mutationType := schema.MutationType()
		if mutationType.PrivateName == "" {
			return nil, gqlerrors.NewError(
				gqlerrors.ErrorTypeBadQuery,
				"Schema is not configured for mutations",
				[]ast.Node{operation},
				"",
				nil,
				[]int{},
				nil,
			)
		}
		return mutationType, nil
	case ast.OperationTypeSubscription:
		subscriptionType := schema.SubscriptionType()
		if subscriptionType.PrivateName == "" {
			return nil, gqlerrors.NewError(
				gqlerrors.ErrorTypeBadQuery,
				"Schema is not configured for subscriptions",
				[]ast.Node{operation},
				"",
				nil,
				[]int{},
				nil,
			)
		}
		return subscriptionType, nil
	}
	return nil, gqlerrors.NewError(
		gqlerrors.ErrorTypeBadQuery,
		"Can only execute queries, mutations and subscription",
		[]ast.Node{operation},
		"",
		nil,
		[]int{},
		nil,
	)
}

type ExecuteFieldsParams struct {
	ExecutionContext *ExecutionContext
	ParentType       *Object
	Source           any
	Fields           map[string][]*ast.Field
}

// childPath returns the path extended with name for use by the Tracer. The
// path is only ever read by eCtx.Tracer.Trace, so when no tracer is configured
// it returns the parent path unchanged to avoid a per-field slice allocation.
// When a tracer is set it clips before appending so sibling fields don't share
// a backing-array slot.
func childPath(eCtx *ExecutionContext, path []string, name string) []string {
	if eCtx.Tracer == nil {
		return path
	}
	return append(slices.Clip(path), name)
}

func executeFieldsSerially(ctx context.Context, p ExecuteFieldsParams, path []string) *Result {
	if p.Source == nil {
		p.Source = make(map[string]any)
	}
	if p.Fields == nil {
		p.Fields = make(map[string][]*ast.Field)
	}

	finalResults := make(map[string]any, len(p.Fields))
	for responseName, fieldASTs := range p.Fields {
		name := responseName
		if len(fieldASTs) != 0 && fieldASTs[0].Name != nil {
			name = fieldASTs[0].Name.Value
		}
		resolved, state := resolveField(ctx, p.ExecutionContext, p.ParentType, p.Source, fieldASTs, childPath(p.ExecutionContext, path, name))
		if state.hasNoFieldDefs {
			continue
		}
		if pend, ok := resolved.(*pendingCoroutine); ok {
			pend.resMap = finalResults
			pend.resKey = responseName
			p.ExecutionContext.pendingCoroutines.push(pend)
		}
		finalResults[responseName] = resolved
	}

	return &Result{
		Data:   finalResults,
		Errors: p.ExecutionContext.Errors,
	}
}

type CollectFieldsParams struct {
	ExeContext           *ExecutionContext
	RuntimeType          *Object // previously known as OperationType
	SelectionSet         *ast.SelectionSet
	Fields               map[string][]*ast.Field
	VisitedFragmentNames map[string]struct{}
}

// Given a selectionSet, adds all of the fields in that selection to
// the passed in map of fields, and returns it at the end.
// CollectFields requires the "runtime type" of an object. For a field which
// returns and Interface or Union type, the "runtime type" will be the actual
// Object type returned by that field.
// collectFields returns the collected fields and the set of visited fragment
// names. The visited set is allocated lazily and is only non-nil once a fragment
// spread has been seen, so spread-free queries allocate no set.
func collectFields(p CollectFieldsParams) (map[string][]*ast.Field, map[string]struct{}) {
	fields := p.Fields
	if fields == nil {
		fields = make(map[string][]*ast.Field)
	}
	visited := p.VisitedFragmentNames
	if p.SelectionSet == nil {
		return fields, visited
	}
	for _, iSelection := range p.SelectionSet.Selections {
		switch selection := iSelection.(type) {
		case *ast.Field:
			if !shouldIncludeNode(p.ExeContext, selection.Directives) {
				continue
			}
			name := getFieldEntryKey(selection)
			fields[name] = append(fields[name], selection)
		case *ast.InlineFragment:
			if !shouldIncludeNode(p.ExeContext, selection.Directives) ||
				!doesFragmentConditionMatch(p.ExeContext, selection, p.RuntimeType) {
				continue
			}
			innerParams := CollectFieldsParams{
				ExeContext:           p.ExeContext,
				RuntimeType:          p.RuntimeType,
				SelectionSet:         selection.SelectionSet,
				Fields:               fields,
				VisitedFragmentNames: visited,
			}
			fields, visited = collectFields(innerParams)
		case *ast.FragmentSpread:
			fragName := ""
			if selection.Name != nil {
				fragName = selection.Name.Value
			}
			if _, ok := visited[fragName]; ok ||
				!shouldIncludeNode(p.ExeContext, selection.Directives) {
				continue
			}
			if visited == nil {
				visited = make(map[string]struct{})
			}
			visited[fragName] = struct{}{}
			fragment, hasFragment := p.ExeContext.Fragments[fragName]
			if !hasFragment {
				continue
			}

			if !doesFragmentConditionMatch(p.ExeContext, fragment, p.RuntimeType) {
				continue
			}
			innerParams := CollectFieldsParams{
				ExeContext:           p.ExeContext,
				RuntimeType:          p.RuntimeType,
				SelectionSet:         fragment.GetSelectionSet(),
				Fields:               fields,
				VisitedFragmentNames: visited,
			}
			fields, visited = collectFields(innerParams)
		}
	}
	return fields, visited
}

// Determines if a field should be included based on the @include and @skip
// directives, where @skip has higher precedence than @include.
func shouldIncludeNode(eCtx *ExecutionContext, directives []*ast.Directive) bool {
	defaultReturnValue := true

	var skipAST *ast.Directive
	var includeAST *ast.Directive
	for _, directive := range directives {
		if directive == nil || directive.Name == nil {
			continue
		}
		if directive.Name.Value == SkipDirective.Name {
			skipAST = directive
			break
		}
	}
	if skipAST != nil {
		argValues, err := getArgumentValues(
			SkipDirective.Args,
			skipAST.Arguments,
			eCtx.VariableValues,
		)
		if err != nil {
			panic(gqlerrors.FormatError(err))
		}
		if skipIf, ok := argValues["if"].(bool); ok {
			if skipIf {
				return false
			}
		}
	}
	for _, directive := range directives {
		if directive == nil || directive.Name == nil {
			continue
		}
		if directive.Name.Value == IncludeDirective.Name {
			includeAST = directive
			break
		}
	}
	if includeAST != nil {
		argValues, err := getArgumentValues(
			IncludeDirective.Args,
			includeAST.Arguments,
			eCtx.VariableValues,
		)
		if err != nil {
			panic(gqlerrors.FormatError(err))
		}
		if includeIf, ok := argValues["if"].(bool); ok {
			if !includeIf {
				return false
			}
		}
	}
	return defaultReturnValue
}

// Determines if a fragment is applicable to the given type.
func doesFragmentConditionMatch(eCtx *ExecutionContext, fragment ast.Node, ttype *Object) bool {
	switch fragment := fragment.(type) {
	case *ast.FragmentDefinition:
		if fragment.TypeCondition == nil {
			return true
		}
		conditionalType, err := typeFromAST(eCtx.Schema, fragment.TypeCondition)
		if err != nil {
			return false
		}
		if conditionalType == ttype {
			return true
		}
		if conditionalType.Name() == ttype.Name() {
			return true
		}
		if conditionalType, ok := conditionalType.(*Interface); ok {
			return eCtx.Schema.IsPossibleType(conditionalType, ttype)
		}
		if conditionalType, ok := conditionalType.(*Union); ok {
			return eCtx.Schema.IsPossibleType(conditionalType, ttype)
		}
	case *ast.InlineFragment:
		if fragment.TypeCondition == nil {
			return true
		}
		conditionalType, err := typeFromAST(eCtx.Schema, fragment.TypeCondition)
		if err != nil {
			return false
		}
		if conditionalType == ttype {
			return true
		}
		if conditionalType.Name() == ttype.Name() {
			return true
		}
		if conditionalType, ok := conditionalType.(*Interface); ok {
			return eCtx.Schema.IsPossibleType(conditionalType, ttype)
		}
		if conditionalType, ok := conditionalType.(*Union); ok {
			return eCtx.Schema.IsPossibleType(conditionalType, ttype)
		}
	}

	return false
}

// Implements the logic to compute the key of a given field’s entry
func getFieldEntryKey(node *ast.Field) string {
	if node.Alias != nil && node.Alias.Value != "" {
		return node.Alias.Value
	}
	if node.Name != nil && node.Name.Value != "" {
		return node.Name.Value
	}
	return ""
}

// Internal resolveField state
type resolveFieldResultState struct {
	hasNoFieldDefs bool
}

// raiseFieldError handles a field-level error. For a nullable field it records
// the error and the field resolves to null. For a NonNull field it panics to
// bubble the null up to the nearest nullable ancestor, where it is recovered by
// completeValueCatchingError. panic is used here solely as that cross-frame
// null-propagation mechanism.
func raiseFieldError(eCtx *ExecutionContext, returnType Type, err error) {
	fe := gqlerrors.FormatError(err)
	if _, ok := returnType.(*NonNull); ok {
		panic(fe)
	}
	eCtx.Errors = append(eCtx.Errors, fe)
}

// recoverFieldPanic converts a value recovered from a resolver panic into an
// error. A raw string panic is turned into a located error; anything else is
// formatted as a panic.
func recoverFieldPanic(r any, fieldASTs []*ast.Field) error {
	if s, ok := r.(string); ok {
		return NewLocatedError(s, FieldASTsToNodeASTs(fieldASTs))
	}
	return gqlerrors.FormatPanic(r)
}

// callResolver invokes a resolver, recovering any panic from the (untrusted)
// resolver code and returning it as an error.
func callResolver(ctx context.Context, resolveFn FieldResolveFn, fieldASTs []*ast.Field, params ResolveParams) (result any, err error) {
	defer func() {
		if r := recover(); r != nil {
			err = recoverFieldPanic(r, fieldASTs)
		}
	}()
	return resolveFn(ctx, params)
}

// Resolves the field on the given source object. In particular, this
// figures out the value that the field returns by calling its resolve function,
// then calls completeValue to complete promises, serialize scalars, or execute
// the sub-selection-set for objects.
func resolveField(ctx context.Context, eCtx *ExecutionContext, parentType *Object, source any, fieldASTs []*ast.Field, path []string) (result any, resultState resolveFieldResultState) {
	if err := ctx.Err(); err != nil {
		// Jump straight to the top-level recover to void anymore work.
		panic(gqlerrors.FormatError(err))
	}

	fieldAST := fieldASTs[0]

	var fieldName string
	if fieldAST.Name != nil {
		fieldName = fieldAST.Name.Value
	}

	fieldDef := getFieldDef(eCtx.Schema, parentType, fieldName, eCtx.DisallowIntrospection)
	if fieldDef == nil {
		// A field not defined in the schema was selected.
		resultState.hasNoFieldDefs = true
		return nil, resultState
	}
	returnType := fieldDef.Type

	if fieldDef.DeprecationReason != "" && eCtx.DeprecatedFieldFn != nil {
		if err := eCtx.DeprecatedFieldFn(ctx, parentType, fieldDef); err != nil {
			raiseFieldError(eCtx, returnType, err)
			return nil, resultState
		}
	}

	if len(fieldDef.Directives) != 0 && eCtx.FieldDefinitionDirectiveHandler != nil {
		for _, d := range fieldDef.Directives {
			if err := eCtx.FieldDefinitionDirectiveHandler(ctx, d, fieldDef); err != nil {
				raiseFieldError(eCtx, returnType, err)
				return nil, resultState
			}
		}
	}

	var customResolver bool
	resolveFn := fieldDef.Resolve
	if resolveFn == nil {
		resolveFn = defaultResolveFn
	} else {
		customResolver = true
	}

	// Build a map of arguments from the field.arguments AST, using the
	// variables scope to fulfill any variable references.
	// TODO: find a way to memoize, in case this field is within a List type.
	args, err := getArgumentValues(fieldDef.Args, fieldAST.Arguments, eCtx.VariableValues)
	if err != nil {
		raiseFieldError(eCtx, returnType, err)
		return nil, resultState
	}

	info := ResolveInfo{
		FieldName:      fieldName,
		FieldASTs:      fieldASTs,
		ReturnType:     returnType,
		ParentType:     parentType,
		Schema:         eCtx.Schema,
		Fragments:      eCtx.Fragments,
		RootValue:      eCtx.Root,
		Operation:      eCtx.Operation,
		VariableValues: eCtx.VariableValues,
	}

	params := ResolveParams{
		Source: source,
		Args:   args,
		Info:   info,
	}

	var resolveFnError error

	if customResolver {
		var st time.Time
		if eCtx.Tracer != nil {
			st = time.Now()
		}
		if eCtx.EnableCoroutines {
			co := startCoroutine(ctx, func(ctx context.Context) (res any, err error) {
				defer func() {
					if r := recover(); r != nil {
						err = recoverFieldPanic(r, fieldASTs)
					}
				}()
				return resolveFn(ctx, ResolveParams{
					Source: source,
					Args:   args,
					Info:   info,
				})
			})
			coSt := co.run()
			if !coSt.done {
				pendCo := &pendingCoroutine{
					co:         co,
					path:       slices.Clone(path),
					returnType: returnType,
					fieldASTs:  fieldASTs,
					info:       info,
				}
				if eCtx.Tracer != nil {
					pendCo.runtime = time.Since(st)
				}
				return pendCo, resultState
			} else if eCtx.Tracer != nil {
				eCtx.Tracer.Trace(ctx, path, time.Since(st))
			}
			result = coSt.res
			resolveFnError = coSt.err
		} else {
			result, resolveFnError = callResolver(ctx, resolveFn, fieldASTs, params)
			if eCtx.Tracer != nil {
				eCtx.Tracer.Trace(ctx, path, time.Since(st))
			}
		}
	} else {
		result, resolveFnError = callResolver(ctx, resolveFn, fieldASTs, params)
	}

	if resolveFnError != nil {
		raiseFieldError(eCtx, returnType, resolveFnError)
		return nil, resultState
	}

	completed := completeValueCatchingError(ctx, eCtx, returnType, fieldASTs, info, result, path)
	return completed, resultState
}

// completeValueCatchingError is the recover boundary for GraphQL null
// propagation. A field error panics from deeper in completeValue (or from
// raiseFieldError); this catches it and, for a nullable field, records the error
// and resolves the field to null. For a NonNull field it re-panics to bubble the
// null up to the nearest nullable ancestor. This is the only place execution
// errors are intended to be recovered.
func completeValueCatchingError(ctx context.Context, eCtx *ExecutionContext, returnType Type, fieldASTs []*ast.Field, info ResolveInfo, result any, path []string) (completed any) {
	defer func() any {
		if r := recover(); r != nil {
			if _, ok := returnType.(*NonNull); ok {
				panic(r)
			}
			if err, ok := r.(gqlerrors.FormattedError); ok {
				eCtx.Errors = append(eCtx.Errors, err)
				return completed
			}
			panic(r)
		}
		return completed
	}()

	return completeValue(ctx, eCtx, returnType, fieldASTs, info, result, path)
}

func completeValue(ctx context.Context, eCtx *ExecutionContext, returnType Type, fieldASTs []*ast.Field, info ResolveInfo, result any, path []string) any {
	if err := ctx.Err(); err != nil {
		panic(gqlerrors.FormatError(err))
	}
	if propertyFn, ok := result.(func() any); ok {
		return propertyFn()
	}

	// If field type is NonNull, complete for inner type, and throw field error
	// if result is null.
	if nonNull, ok := returnType.(*NonNull); ok {
		completed := completeValue(ctx, eCtx, nonNull.OfType, fieldASTs, info, result, path)
		if completed == nil {
			err := NewLocatedError(
				fmt.Sprintf("Cannot return null for non-nullable field %v.%v.", info.ParentType, info.FieldName),
				FieldASTsToNodeASTs(fieldASTs),
			)
			panic(gqlerrors.FormatError(err))
		}
		return completed
	}

	// If result value is null-ish (null, undefined, or NaN) then return null.
	if isNullish(result) {
		return nil
	}

	switch returnType := returnType.(type) {
	case *List:
		// Complete each item in the list with the inner type.
		return completeListValue(ctx, eCtx, returnType, fieldASTs, info, result, path)
	case *Scalar, *Enum:
		// Leaf type: serialize to a valid value, returning null if not possible.
		serialized, err := completeLeafValue(returnType.(Leaf), result)
		if err != nil {
			// Bubble the serialization error via completeValueCatchingError.
			panic(err)
		}
		return serialized
	case *Union:
		// Abstract type: determine the runtime Object type and complete for it.
		return completeAbstractValue(ctx, eCtx, returnType, fieldASTs, info, result, path)
	case *Interface:
		return completeAbstractValue(ctx, eCtx, returnType, fieldASTs, info, result, path)
	case *Object:
		// Execute and complete all sub-selections.
		return completeObjectValue(ctx, eCtx, returnType, fieldASTs, info, result, path)
	}

	// Not reachable. All possible output types have been considered.
	panic(gqlerrors.NewFormattedError(fmt.Sprintf(`Cannot complete value of unexpected type "%v."`, returnType)))
}

// completeAbstractValue completes value of an Abstract type (Union / Interface) by determining the runtime type
// of that value, then completing based on that type.
func completeAbstractValue(ctx context.Context, eCtx *ExecutionContext, returnType Abstract, fieldASTs []*ast.Field, info ResolveInfo, result any, path []string) any {
	var runtimeType *Object

	resolveTypeParams := ResolveTypeParams{
		Value: result,
		Info:  info,
	}
	if unionReturnType, ok := returnType.(*Union); ok && unionReturnType.ResolveType != nil {
		runtimeType = unionReturnType.ResolveType(ctx, resolveTypeParams)
	} else if interfaceReturnType, ok := returnType.(*Interface); ok && interfaceReturnType.ResolveType != nil {
		runtimeType = interfaceReturnType.ResolveType(ctx, resolveTypeParams)
	} else {
		runtimeType = defaultResolveTypeFn(resolveTypeParams, returnType)
	}

	if runtimeType == nil {
		panic(gqlerrors.NewFormattedError(
			fmt.Sprintf(`Abstract type %v must resolve to an Object type at runtime `+
				`for field %v.%v with value "%v", received "%v".`,
				returnType, info.ParentType, info.FieldName, result, runtimeType)))
	}

	if !eCtx.Schema.IsPossibleType(returnType, runtimeType) {
		panic(gqlerrors.NewFormattedError(
			fmt.Sprintf(`Runtime Object type "%v" is not a possible type `+
				`for "%v".`, runtimeType, returnType),
		))
	}

	return completeObjectValue(ctx, eCtx, runtimeType, fieldASTs, info, result, path)
}

// completeObjectValue complete an Object value by executing all sub-selections.
func completeObjectValue(ctx context.Context, eCtx *ExecutionContext, returnType *Object, fieldASTs []*ast.Field, info ResolveInfo, result any, path []string) any {
	// If there is an isTypeOf predicate function, call it with the
	// current result. If isTypeOf returns false, then raise an error rather
	// than continuing execution.
	if returnType.IsTypeOf != nil {
		p := IsTypeOfParams{
			Value: result,
			Info:  info,
		}
		if !returnType.IsTypeOf(p) {
			panic(gqlerrors.NewFormattedError(
				fmt.Sprintf(`Expected value of type "%v" but got: %T.`, returnType, result),
			))
		}
	}

	// Collect sub-fields to execute to complete this value. visitedFragmentNames
	// is left nil and allocated lazily by collectFields only when a fragment
	// spread is encountered (most queries have none).
	subFieldASTs := make(map[string][]*ast.Field, len(fieldASTs))
	var visitedFragmentNames map[string]struct{}
	for _, fieldAST := range fieldASTs {
		if fieldAST == nil {
			continue
		}
		selectionSet := fieldAST.SelectionSet
		if selectionSet != nil {
			innerParams := CollectFieldsParams{
				ExeContext:           eCtx,
				RuntimeType:          returnType,
				SelectionSet:         selectionSet,
				Fields:               subFieldASTs,
				VisitedFragmentNames: visitedFragmentNames,
			}
			subFieldASTs, visitedFragmentNames = collectFields(innerParams)
		}
	}
	executeFieldsParams := ExecuteFieldsParams{
		ExecutionContext: eCtx,
		ParentType:       returnType,
		Source:           result,
		Fields:           subFieldASTs,
	}
	results := executeFieldsSerially(ctx, executeFieldsParams, path)
	return results.Data
}

// completeLeafValue completes a leaf value (Scalar / Enum) by serializing it to
// a valid value, returning nil if serialization yields a null-ish value. A
// serialization failure is returned as an error for the caller to propagate.
func completeLeafValue(returnType Leaf, result any) (any, error) {
	// Unwrap pointer values so scalars are serialized by value, matching the
	// behavior when resolvers return plain values (e.g. via a map) rather than
	// pointer struct fields.
	if rv := reflect.ValueOf(result); rv.Kind() == reflect.Pointer {
		if rv.IsNil() {
			return nil, nil
		}
		result = rv.Elem().Interface()
	}
	serializedResult, err := returnType.Serialize(result)
	if err != nil {
		return nil, gqlerrors.FormatError(err)
	}
	if isNullish(serializedResult) {
		return nil, nil
	}
	return serializedResult, nil
}

// completeListValue complete a list value by completing each item in the list with the inner type
func completeListValue(ctx context.Context, eCtx *ExecutionContext, returnType *List, fieldASTs []*ast.Field, info ResolveInfo, result any, path []string) any {
	resultVal := reflect.ValueOf(result)
	parentTypeName := ""
	if info.ParentType != nil {
		parentTypeName = info.ParentType.Name()
	}
	if !resultVal.IsValid() || resultVal.Type().Kind() != reflect.Slice {
		panic(gqlerrors.NewFormattedError(fmt.Sprintf("User Error: expected iterable, but did not find one for field %v.%v.", parentTypeName, info.FieldName)))
	}

	itemType := returnType.OfType
	completedResults := make([]any, 0, resultVal.Len())
	for i := range resultVal.Len() {
		val := resultVal.Index(i).Interface()
		completedItem := completeValueCatchingError(ctx, eCtx, itemType, fieldASTs, info, val, path)
		completedResults = append(completedResults, completedItem)
	}
	return completedResults
}

type structFieldInfo struct {
	index     int
	omitempty bool
}

var (
	structTypeCacheMu sync.RWMutex
	structTypeCache   = make(map[reflect.Type]map[string]structFieldInfo) // struct type -> field name -> field info
)

func fieldInfoForStruct(structType reflect.Type) map[string]structFieldInfo {
	structTypeCacheMu.RLock()
	sm := structTypeCache[structType]
	structTypeCacheMu.RUnlock()
	if sm != nil {
		return sm
	}

	// Cache a mapping of fields for the struct

	structTypeCacheMu.Lock()
	defer structTypeCacheMu.Unlock()

	// Check again in case someone beat us
	sm = structTypeCache[structType]
	if sm != nil {
		return sm
	}

	sm = make(map[string]structFieldInfo)
	for i := range structType.NumField() {
		field := structType.Field(i)
		if field.PkgPath != "" && !field.Anonymous {
			continue
		}
		tag := field.Tag
		t := tag.Get("graphql")
		if t == "" {
			t = tag.Get("json")
		}
		tOpts := strings.Split(t, ",")
		if len(tOpts) == 0 {
			sm[field.Name] = structFieldInfo{index: i}
		} else {
			omitempty := len(tOpts) > 1 && tOpts[1] == "omitempty"
			sm[field.Name] = structFieldInfo{index: i, omitempty: omitempty}
			sm[tOpts[0]] = structFieldInfo{index: i, omitempty: omitempty}
		}
	}
	structTypeCache[structType] = sm
	return sm
}

// defaultResolveTypeFn If a resolveType function is not given, then a default resolve behavior is
// used which tests each possible type for the abstract type by calling
// isTypeOf for the object being coerced, returning the first type that matches.
func defaultResolveTypeFn(p ResolveTypeParams, abstractType Abstract) *Object {
	possibleTypes := p.Info.Schema.PossibleTypes(abstractType)
	for _, possibleType := range possibleTypes {
		if possibleType.IsTypeOf == nil {
			continue
		}
		if res := possibleType.IsTypeOf(IsTypeOfParams(p)); res {
			return possibleType
		}
	}
	return nil
}

// defaultResolveFn If a resolve function is not given, then a default resolve behavior is used
// which takes the property of the source object of the same name as the field
// and returns it as the result, or if it's a function, returns the result
// of calling that function.
func defaultResolveFn(ctx context.Context, p ResolveParams) (any, error) {
	// try p.Source as a map[string]interface
	if sourceMap, ok := p.Source.(map[string]any); ok {
		property := sourceMap[p.Info.FieldName]
		if fn, ok := property.(func() any); ok {
			return fn(), nil
		}
		return property, nil
	}

	// try to resolve p.Source as a struct first
	sourceVal := reflect.ValueOf(p.Source)
	if sourceVal.IsValid() && sourceVal.Type().Kind() == reflect.Pointer {
		sourceVal = sourceVal.Elem()
	}
	if !sourceVal.IsValid() {
		return nil, nil
	}
	sourceType := sourceVal.Type()
	if sourceType.Kind() == reflect.Struct {
		sm := fieldInfoForStruct(sourceType)
		if field, ok := sm[p.Info.FieldName]; ok {
			valueField := sourceVal.Field(field.index)
			if field.omitempty && isEmptyValue(valueField) {
				return nil, nil
			}
			return valueField.Interface(), nil
		}
		return nil, nil
	}

	// last resort, return nil
	return nil, nil
}

// getFieldDef looks up the field on the given type definition.
// It has special casing for the two introspection fields, __schema
// and __typename. __typename is special because it can always be
// queried as a field, even in situations where no other fields
// are allowed, like on a Union. __schema could get automatically
// added to the query type, but that would require mutating type
// definitions, which would cause issues.
func getFieldDef(schema Schema, parentType *Object, fieldName string, disallowIntrospection bool) *FieldDefinition {
	if parentType == nil {
		return nil
	}

	if !disallowIntrospection {
		if fieldName == SchemaMetaFieldDef.Name &&
			schema.QueryType() == parentType {
			return SchemaMetaFieldDef
		}
		if fieldName == TypeMetaFieldDef.Name &&
			schema.QueryType() == parentType {
			return TypeMetaFieldDef
		}
	}
	if fieldName == TypeNameMetaFieldDef.Name {
		return TypeNameMetaFieldDef
	}
	return parentType.Fields()[fieldName]
}