validator.go

package walle

import (
	"encoding/json"
	"fmt"
	"sort"
	"strconv"
	"strings"
)

type KeywordValidatorFunc func(any, *validationContext, schemaPath) error

type schemaValidator struct {
	context              *validationContext
	keywordValidators    map[string]KeywordValidatorFunc
	validateLengthRange  KeywordValidatorFunc
	validateNumericRange KeywordValidatorFunc
	validateItemsRange   KeywordValidatorFunc
	defDepths            map[string]int
	totalPropKeys        int
	terminationMemo      map[string]bool
	refWalkSteps         int
	utils                *validateUtils
	config               SchemaValidatorConfig
}

// maxRefWalkSteps caps the total number of nodes the reference walkers (defs
// depth computation and reference termination checking) may visit during one
// validation. Chains of definitions forming diamonds -- or diamonds closing a
// long cycle -- cost 2^n walks without memoization; past this budget
// validation fails closed instead of hanging on adversarial schemas. Honest
// schemas stay orders of magnitude below it: memoized walks are linear in the
// number of definitions.
const maxRefWalkSteps = 500000

func newSchemaValidator(options ...SchemaValidatorOption) *schemaValidator {
	config := DefaultValidatorConfig()
	for _, option := range options {
		option(&config)
	}

	kv := newKeywordValidators(&config)
	validator := &schemaValidator{
		context:           newValidationContext(),
		keywordValidators: make(map[string]KeywordValidatorFunc),
		defDepths:         make(map[string]int),
		totalPropKeys:     0,
		utils:             &validateUtils{},
		config:            config,
	}

	// Register keyword validators
	validator.keywordValidators[Type] = kv.ValidateType
	validator.keywordValidators[Properties] = kv.ValidateProperties
	validator.keywordValidators[Required] = kv.ValidateRequired
	validator.keywordValidators[Enum] = kv.ValidateEnum
	validator.keywordValidators[Items] = kv.ValidateItems
	validator.keywordValidators[Ref] = kv.ValidateRef
	validator.keywordValidators[Description] = kv.ValidateDescription
	validator.keywordValidators[Title] = kv.ValidateTitle
	validator.keywordValidators[AnyOf] = kv.ValidateAnyOf
	validator.keywordValidators[AdditionalProperties] = kv.ValidateAdditionalProperties
	validator.keywordValidators[Defs] = kv.ValidateDefs
	validator.keywordValidators[Id] = kv.ValidateID
	validator.keywordValidators[Pattern] = kv.ValidatePattern
	validator.keywordValidators[Default] = kv.ValidateDefault
	validator.validateLengthRange = kv.ValidateLengthRange
	validator.validateNumericRange = kv.ValidateNumericRange
	validator.validateItemsRange = kv.ValidateItemsRange

	return validator
}

// Reset resets the validator state
func (v *schemaValidator) Reset() {
	v.context = newValidationContext()
	v.defDepths = make(map[string]int)
	v.totalPropKeys = 0
	v.terminationMemo = nil
	v.refWalkSteps = 0
	// won't reset config
}

func (v *schemaValidator) MakePath(base schemaPath, parts ...string) schemaPath {
	if base.IsRoot() {
		return newSchemaPathFromParts(parts)
	}
	return base.Append(parts...)
}

func (v *schemaValidator) CheckAnyOfConflicts(schema SchemaDict, path schemaPath) error {
	anyOf, ok := schema[AnyOf]
	if !ok {
		return nil
	}

	// Get outer keywords (excluding anyOf itself)
	outerKeywords := make(map[string]struct{})
	for k := range schema {
		if k != AnyOf {
			outerKeywords[k] = struct{}{}
		}
	}

	// Check each anyOf branch
	anyOfSchemas, ok := anyOf.(SchemaList)
	if !ok {
		return v.context.RaiseErrorWithSimplify("anyOf must be an array", path.Append(AnyOf), SimplifyRemoveAnyOf)
	}

	for _, subschema := range anyOfSchemas {
		schemaObj, ok := subschema.(SchemaDict)
		if !ok {
			return v.context.RaiseErrorWithSimplify("schema in anyOf must be an object", path.Append(AnyOf), SimplifyRemoveAnyOf)
		}

		// Check branch keywords against outer keywords
		branchKeywords := make(map[string]struct{})
		for k := range schemaObj {
			branchKeywords[k] = struct{}{}
		}

		var conflicts []string
		for k := range branchKeywords {
			if _, exists := outerKeywords[k]; exists {
				// Constraining an instance both directly and inside a branch is legal
				// under 2020-12: both apply and the effective constraint is their
				// conjunction. Only the canonicalising levels report it, so that
				// Canonical distributes the parent copy into the branches while looser
				// levels accept the schema as written.
				if !(v.config.IsUltra() || v.config.IsTest()) {
					continue
				}
				conflicts = append(conflicts, k)
			}
		}

		if len(conflicts) > 0 {
			sort.Strings(conflicts)
			return v.context.RaiseErrorWithSimplify(
				fmt.Sprintf(
					`conflicting keywords found in anyOf with parent: keywords (%s) are defined on the parent schema and inside anyOf; remove them from the parent or from anyOf branches`,
					strings.Join(conflicts, ", "),
				),
				path, simplifyFuncForAnyOfParentConflicts(conflicts),
			)
		}
	}

	return nil
}

// TraverseSchema traverses and validates a schema
func (v *schemaValidator) TraverseSchema(schema SchemaDict, path schemaPath, currentDepth int) (int, error) {
	maxDepth := currentDepth

	if currentDepth > v.config.MaxSchemaDepth {
		return currentDepth, v.context.RaiseError(fmt.Sprintf("schema depth exceeds maximum limit of %d", v.config.MaxSchemaDepth), path)
	}

	if schema == nil {
		return currentDepth, nil
	}

	// Verify if it contains unsupported keywords
	var unsupported []string
	for k := range schema {
		if _, ok := SupportedKeywords[k]; !ok && !FutureKeywords[k] {
			unsupported = append(unsupported, k)
		}
	}

	if len(unsupported) > 0 && (v.config.IsUltra() || v.config.IsTest()) {
		sort.Strings(unsupported)
		// Drop just the unsupported keywords; the enforcer ignores keys it does not
		// know, so keeping the rest of the schema is both safe and closer to intent.
		return currentDepth, v.context.RaiseErrorWithSimplify(
			fmt.Sprintf("unsupported keywords: %s", strings.Join(unsupported, ", ")),
			path, SimplifyRemoveSchemaKeys(unsupported),
		)
	}

	// Process $defs first
	if defs, ok := schema[Defs].(SchemaDict); ok {
		keywords := make([]string, 0, len(defs))
		for keyword := range defs {
			keywords = append(keywords, keyword)
		}
		sort.Strings(keywords)
		for _, keyword := range keywords {
			value := defs[keyword]
			defSchemaObj, ok := value.(SchemaDict)
			if !ok {
				return currentDepth, v.context.RaiseErrorWithSimplify("$defs schema must be object", path.Append(Defs), SimplifyRemoveDefs)
			}
			depth, err := v.TraverseSchema(
				defSchemaObj,
				v.MakePath(path, Defs, keyword),
				currentDepth,
			)
			if err != nil {
				return currentDepth, err
			}
			if depth > maxDepth {
				maxDepth = depth
			}
		}
	}

	// A contradiction between $ref and its siblings is reported before any other
	// $ref rule. The rules below delete siblings to canonicalise the node, and
	// once a contradicting sibling is gone the remaining schema happily accepts
	// what the original rejected.
	//
	// Strict and above reject it, matching how a lower bound above its upper bound
	// is handled: both are contradictions inside one node, and neither used to
	// stop lite. Looser levels accept the schema and rely on canonicalisation to
	// drop the contradicting keyword.
	if _, hasRef := schema[Ref]; hasRef && v.config.IsGreaterThanStrict() {
		if keyword := v.refSiblingContradiction(schema, path); keyword != "" {
			return currentDepth, v.context.RaiseErrorWithSimplify(
				fmt.Sprintf(
					"%s conflicts with the referenced schema: the intersection is empty, so no instance can satisfy both",
					keyword,
				),
				path, SimplifyDropContradictingRefSibling,
			)
		}
	}

	// Check type and anyOf/ref conflicts
	if _, hasType := schema[Type]; hasType {
		if _, hasAnyOf := schema[AnyOf]; hasAnyOf {
			// A type beside anyOf is legal under 2020-12: it applies on top of
			// whichever branch matches. The enforcer's anyOf cannot carry a conjunct,
			// so only the canonicalising levels report it and the type is pushed into
			// the branches; looser levels accept the schema as written.
			if v.config.IsUltra() || v.config.IsTest() {
				return currentDepth, v.context.RaiseErrorWithSimplify(
					"when using anyOf, type should be defined in anyOf items instead of the parent schema",
					path, SimplifyDistributeAnyOfParent,
				)
			}
		}
		if _, hasRef := schema[Ref]; hasRef {
			// A compatible type next to $ref is legal under 2020-12: both assertions
			// apply and the intersection is non-empty, which the check above already
			// established. Only the canonicalising levels fold it away, so looser
			// levels accept the schema as written.
			if v.config.IsUltra() || v.config.IsTest() {
				return currentDepth, v.context.RaiseErrorWithSimplify(
					"when using $ref, type should be defined in the referenced schema instead of the parent schema",
					path, SimplifyRemoveType,
				)
			}
		}

		if typeList, ok := schema[Type].(SchemaList); ok && len(typeList) > 1 {
			if _, hasEnum := schema[Enum]; hasEnum {
				for _, t := range typeList {
					if typeStr, ok := t.(string); ok {
						if typeStr == Object || typeStr == Array {
							return currentDepth, v.context.RaiseErrorWithSimplify(
								fmt.Sprintf("type %s is not allowed in combination with enum", typeStr),
								path, SimplifyRemoveParentSchema,
							)
						}
					}
				}
			}
		}
	}
	// else {
	// Empty schema {} is valid
	// isAnySchema := false
	// isAdditional := false
	// if path.Last() == AdditionalProperties {
	// 	isAdditional = true
	// }

	// if len(schema) == 0 && isAdditional {
	// 	isAnySchema = true
	// }

	// if _, hasAnyOf := schema[AnyOf]; !hasAnyOf {
	// 	if _, hasRef := schema[Ref]; !hasRef {
	// 		if !isAnySchema {
	// 			return currentDepth, v.context.RaiseErrorWithSimplify("type need to be defined explicitly", path, SimplifyRemoveSubSchema)
	// 		}
	// 	}
	// }
	// }

	// Type keyword validation
	if err := v.validateTypeAndKeywords(schema, path); err != nil {
		return currentDepth, err
	}

	// Other keywords validation
	keywords := make([]string, 0, len(schema))
	for keyword := range schema {
		keywords = append(keywords, keyword)
	}
	sort.Strings(keywords)
	for _, keyword := range keywords {
		value := schema[keyword]
		if validator, ok := v.keywordValidators[keyword]; ok {
			if err := validator(value, v.context, v.MakePath(path, keyword)); err != nil {
				return currentDepth, err
			}
		}
	}

	// Check anyOf conflicts
	if err := v.CheckAnyOfConflicts(schema, path); err != nil {
		return currentDepth, err
	}

	// process $ref depth
	if ref, ok := schema[Ref].(string); ok {
		refDepth, exists := v.defDepths[ref]
		if !exists {
			refDepth = 0
		}
		if currentDepth+refDepth > maxDepth {
			maxDepth = currentDepth + refDepth
		}
	}

	// Recursive verify sub-schema
	// properties
	if props, ok := schema[Properties].(SchemaDict); ok {
		propsDepth := currentDepth + 1
		v.totalPropKeys += len(props)
		if v.totalPropKeys > v.config.MaxTotalPropertiesKeysNum {
			return currentDepth, v.context.RaiseError(
				fmt.Sprintf("total number of properties keys(%d) across all objects exceeds maximum limit of %d",
					v.totalPropKeys, v.config.MaxTotalPropertiesKeysNum),
				path,
			)
		}

		for propName, propSchema := range props {
			propSchemaObj, ok := propSchema.(SchemaDict)
			if !ok {
				continue
			}
			depth, err := v.TraverseSchema(propSchemaObj, v.MakePath(path, Properties, propName), propsDepth)
			if err != nil {
				return currentDepth, err
			}
			if depth > maxDepth {
				maxDepth = depth
			}
		}
	}

	// items
	if items, ok := schema[Items].(SchemaDict); ok {
		depth, err := v.TraverseSchema(items, v.MakePath(path, Items), currentDepth)
		if err != nil {
			return currentDepth, err
		}
		if depth > maxDepth {
			maxDepth = depth
		}
	}

	// additionalProperties
	if addProps, ok := schema[AdditionalProperties].(SchemaDict); ok {
		depth, err := v.TraverseSchema(
			addProps,
			v.MakePath(path, AdditionalProperties),
			currentDepth,
		)
		if err != nil {
			return currentDepth, err
		}
		if depth > maxDepth {
			maxDepth = depth
		}
	}

	// anyOf
	if anyOf, ok := schema[AnyOf].(SchemaList); ok {
		for i, subSchema := range anyOf {
			subSchemaObj, ok := subSchema.(SchemaDict)
			if !ok {
				continue
			}
			depth, err := v.TraverseSchema(
				subSchemaObj,
				v.MakePath(path, fmt.Sprintf("anyOf{%d}", i)),
				currentDepth,
			)
			if err != nil {
				return currentDepth, err
			}
			if depth > maxDepth {
				maxDepth = depth
			}
		}
	}

	return maxDepth, nil
}

func (v *schemaValidator) validateTypeAndKeywords(schema SchemaDict, path schemaPath) error {
	if typeVal, ok := schema[Type]; ok {
		var types []string

		switch t := typeVal.(type) {
		case string:
			if !ValidTypes[t] {
				return v.context.RaiseErrorWithSimplify("invalid type", path, SimplifyRemoveParentSchema)
			}
			types = append(types, t)
		case SchemaList:
			for _, item := range t {
				if str, ok := item.(string); !ok || !ValidTypes[str] {
					return v.context.RaiseErrorWithSimplify("invalid type in type array", path, SimplifyRemoveParentSchema)
				}
				types = append(types, item.(string))
			}
			if len(types) == 0 {
				return v.context.RaiseErrorWithSimplify("type array cannot be empty", path, SimplifyRemoveParentSchema)
			}
		}

		if len(types) > 1 {
			allowedEnum := false
			if len(types) == 2 && schema[Enum] != nil {
				for _, t := range types {
					if t == Object || t == Array {
						return v.context.RaiseErrorWithSimplify("object and array cannot be used in combination with multiple types", path, SimplifyRemoveParentSchema)
					}
				}
				allowedEnum = true
			}

			if v.config.IsGreaterThanStrict() {
				for k := range schema {
					if path.IsRoot() {
						if !TopLevelOnlyKeywords[k] && !CommonKeywords[k] && k != Type && !allowedEnum {
							return v.context.RaiseErrorWithSimplify(fmt.Sprintf("keyword %s is not allowed in combination with multiple types", k), path, SimplifyRemoveParentSchema)
						}
					} else {
						if !CommonKeywords[k] && k != Type && !allowedEnum {
							return v.context.RaiseErrorWithSimplify(fmt.Sprintf("keyword %s is not allowed in combination with multiple types", k), path, SimplifyRemoveParentSchema)
						}
					}
				}
			}
		}

		// lite only needs this for JSON-null bounds. Other mistyped or
		// contradictory bounds stay strict-and-above, as they did before.
		if len(types) >= 1 && (v.config.IsLite() || v.config.IsStrict()) {
			if allowedKeywords, err := v.computeAllowedKeywordsForTypes(path, types); err == nil {
				if err := v.validateRangeKeywordsForAllowedTypes(schema, path, allowedKeywords); err != nil {
					return err
				}
			}
		}

		if len(types) >= 1 && (v.config.IsUltra() || v.config.IsTest()) {
			// Check $defs and $id are only at top level
			if !path.IsRoot() {
				for k := range schema {
					if TopLevelOnlyKeywords[k] {
						return v.context.RaiseErrorWithSimplify(fmt.Sprintf("keyword %s must be at root level", k), path, SimplifyRemoveSchemaKeys([]string{k}))
					}
				}
			}

			allowedKeywords, err := v.computeAllowedKeywordsForTypes(path, types)
			if err != nil {
				return err
			}

			var invalidKeys []string
			for k := range schema {
				if _, exists := allowedKeywords[k]; !exists {
					invalidKeys = append(invalidKeys, k)
				}
			}

			if len(invalidKeys) > 0 {
				sort.Strings(invalidKeys)
				return v.context.RaiseErrorWithSimplify(
					fmt.Sprintf("invalid keywords: %s", strings.Join(invalidKeys, ", ")),
					path, SimplifyRemoveSchemaKeys(invalidKeys),
				)
			}

			if err := v.validateRangeKeywordsForAllowedTypes(schema, path, allowedKeywords); err != nil {
				return err
			}
		}
	}

	return nil
}

func (v *schemaValidator) computeAllowedKeywordsForTypes(path schemaPath, types []string) (map[string]struct{}, error) {
	allowedKeywords := make(map[string]struct{})
	if path.IsRoot() {
		for k := range TopLevelOnlyKeywords {
			allowedKeywords[k] = struct{}{}
		}
	}

	if len(types) == 1 {
		allowed, err := v.allowedKeywordsForSingleType(types[0], path)
		if err != nil {
			return nil, err
		}
		for k := range allowed {
			allowedKeywords[k] = struct{}{}
		}
		return allowedKeywords, nil
	}

	var intersection map[string]bool
	for _, schemaType := range types {
		allowed, err := v.allowedKeywordsForSingleType(schemaType, path)
		if err != nil {
			return nil, err
		}

		if intersection == nil {
			intersection = make(map[string]bool, len(allowed))
			for k := range allowed {
				intersection[k] = true
			}
			continue
		}

		for k := range intersection {
			if !allowed[k] {
				delete(intersection, k)
			}
		}
	}

	for k := range intersection {
		allowedKeywords[k] = struct{}{}
	}
	return allowedKeywords, nil
}

func (v *schemaValidator) allowedKeywordsForSingleType(schemaType string, path schemaPath) (map[string]bool, error) {
	switch schemaType {
	case Object:
		return ObjectAllowedKeywords, nil
	case Array:
		return ArrayAllowedKeywords, nil
	case String:
		return StringAllowedKeywords, nil
	case Number, Integer:
		return NumberAllowedKeywords, nil
	case Boolean:
		return BooleanAllowedKeywords, nil
	case Null:
		return NullAllowedKeywords, nil
	default:
		return nil, v.context.RaiseErrorWithSimplify(
			fmt.Sprintf("invalid type: %s", schemaType),
			path,
			SimplifyRemoveParentSchema,
		)
	}
}

func (v *schemaValidator) validateRangeKeywordsForAllowedTypes(schema SchemaDict, path schemaPath, allowedKeywords map[string]struct{}) error {
	_, hasMinLength := schema[MinLength]
	_, hasMaxLength := schema[MaxLength]
	if hasMinLength || hasMaxLength {
		if _, ok := allowedKeywords[MinLength]; ok {
			if err := v.validateLengthRange(schema, v.context, path); err != nil {
				return err
			}
		}
	}

	_, hasMinimum := schema[Minimum]
	_, hasMaximum := schema[Maximum]
	if hasMinimum || hasMaximum {
		if _, ok := allowedKeywords[Minimum]; ok {
			if err := v.validateNumericRange(schema, v.context, path); err != nil {
				return err
			}
		}
	}

	_, hasMinItems := schema[MinItems]
	_, hasMaxItems := schema[MaxItems]
	if hasMinItems || hasMaxItems {
		if _, ok := allowedKeywords[MinItems]; ok {
			if err := v.validateItemsRange(schema, v.context, path); err != nil {
				return err
			}
		}
	}

	return nil
}

// Validate validates a JSON schema
func (v *schemaValidator) Validate(schema any) error {
	switch s := schema.(type) {
	case string:
		var schemaDict SchemaDict
		err := json.Unmarshal([]byte(s), &schemaDict)
		if err != nil {
			switch e := err.(type) {
			case *json.SyntaxError:
				return NewUnmarshalError(fmt.Errorf("JSON syntax error at offset %d: %s", e.Offset, e.Error()))
			case *json.UnmarshalTypeError:
				return NewUnmarshalError(fmt.Errorf("JSON type error at offset %d: expected %s but got %s",
					e.Offset, e.Type, e.Value))
			default:
				return NewUnmarshalError(err)
			}
		}
		return v.validateSchemaDict(schemaDict)
	case SchemaDict:
		return v.validateSchemaDict(s)
	case Schema:
		return v.validateSchemaDict(s)
	default:
		return v.context.RaiseError("input schema must be a string or map", rootSchemaPath)
	}
}

func (v *schemaValidator) CanonicalWithMaxAttempts(schema Schema, maxAttempts int) (string, error) {
	// Fold sibling constraints into their $ref target or anyOf branches before
	// validating. Left to the retry loop these siblings would simply be deleted,
	// which silently loosens the schema whenever the sibling was the stricter of
	// the two. anyOf is distributed first because doing so can leave a constraint
	// beside a branch's $ref, which is what the inlining pass then folds in.
	inlined, droppedSiblings := inlineConflictingRefSiblings(
		distributeAnyOfParentKeywords(hoistLocalRefs(schema)),
		v.config.MaxSchemaSize,
	)
	currentSchema := Schema(inlined)

	// Siblings the copy budget could not fold in were dropped in one pass rather
	// than one retry at a time; surface exactly what was lost as the warning.
	var rawErr error
	if len(droppedSiblings) > 0 {
		const maxReported = 5
		shown := droppedSiblings
		if len(shown) > maxReported {
			shown = droppedSiblings[:maxReported]
		}
		rawErr = fmt.Errorf(
			"inlining every $ref would exceed the schema size limit, so %d sibling constraint(s) were dropped instead: %s",
			len(droppedSiblings), strings.Join(shown, ", "),
		)
	}

	for i := 0; i < maxAttempts; i++ {
		err := v.Validate(currentSchema)
		if i == 0 && err != nil {
			rawErr = err
		}
		if err == nil {
			schemaStr, _ := json.Marshal(currentSchema)
			return string(schemaStr), rawErr
		}

		if schemaErr, ok := err.(*SchemaError); ok && schemaErr.SimplifyFunc != nil {
			pathObj := newSchemaPath(schemaErr.Path)
			currentSchema = schemaErr.SimplifyFunc(currentSchema, pathObj)
		} else {
			return "{}", rawErr
		}
	}

	return "{}", rawErr
}

func (v *schemaValidator) validateSchemaDict(schema SchemaDict) error {
	// Reset state
	v.Reset()

	if schema == nil {
		return v.context.RaiseError("schema must be a dict", rootSchemaPath)
	}

	// Empty schema {} is valid
	if len(schema) == 0 {
		return nil
	}

	// Callers such as chatapis Validate without Canonical. Hoist first so that
	// "#/properties/..." is not rejected here by ValidateRef.
	schema = hoistLocalRefs(schema)

	v.context.SchemaRoot = schema

	// Verify schema string length
	if v.utils.CalculateSchemaSize(schema) > v.config.MaxSchemaSize {
		return v.context.RaiseError("schema exceeds maximum allowed size", rootSchemaPath)
	}

	// Precompute defs depth
	defDepths, err := v.CalculateDefDepths()
	if err != nil {
		return err
	}
	v.defDepths = defDepths

	// Verify schema
	maxDepth, err := v.TraverseSchema(schema, rootSchemaPath, 0)
	if err != nil {
		return err
	}

	if maxDepth > v.config.MaxSchemaDepth {
		return v.context.RaiseError(fmt.Sprintf("schema depth exceeds maximum limit of %d", v.config.MaxSchemaDepth), rootSchemaPath)
	}

	// Verify ref path is valid
	return v.PostValidateRefs()
}

// refSiblingContradiction names a keyword that the node and the schema it
// references constrain in ways that cannot both hold, or "" when they can. A
// reference that cannot be resolved is not a contradiction; PostValidateRefs
// reports that separately.
func (v *schemaValidator) refSiblingContradiction(schema SchemaDict, path schemaPath) string {
	refStr, ok := schema[Ref].(string)
	if !ok {
		return ""
	}

	target, err := v.utils.ResolveRef(v.context.SchemaRoot, refStr, v.context, path)
	if err != nil || target == nil {
		return ""
	}

	return unsatisfiableOverlap(schema, target)
}

// PostValidateRefs validates all references after schema traversal
func (v *schemaValidator) PostValidateRefs() error {
	// Verify all ref paths exist
	for refPath := range v.context.RefPaths {
		if _, err := v.utils.ResolveRef(v.context.SchemaRoot, refPath, v.context, rootSchemaPath); err != nil {
			return v.context.RaiseError(fmt.Sprintf("invalid $ref path: %s", refPath), rootSchemaPath)
		}
	}

	// Every $ref has to be able to terminate. Short-circuiting on the root was not
	// enough: the root normally terminates because its own properties are optional,
	// which masked non-terminating definitions nested inside $defs.
	return v.TraverseAndCheckRefs(v.context.SchemaRoot, true, nil, rootSchemaPath)
}

// TraverseAndCheckRefs traverses the schema and checks all references
func (v *schemaValidator) TraverseAndCheckRefs(schema SchemaDict, needCheckTermination bool, requiredList SchemaList, path schemaPath) error {
	if schema == nil {
		return nil
	}

	if _, hasRef := schema[Ref]; hasRef {
		expanded, err := v.ExpandRef(schema, make(map[string]struct{}), path)
		if err != nil {
			return err
		}

		if err := v.CheckRefContext(schema, expanded, path); err != nil {
			return err
		}

		// Check that all refs can be terminated
		if needCheckTermination {
			terminates, err := v.CheckRefTermination(expanded, make(map[string]struct{}), path)
			if err != nil {
				return err
			}
			if !terminates {
				return v.context.RaiseError("detected infinite recursion without termination condition", path)
			}
		}
	}

	for key, value := range schema {
		if key == Defs {
			continue
		}

		var newPath schemaPath
		if path.IsRoot() {
			newPath = schemaPath{Parts: []string{key}}
		} else {
			newPath = path.Append(key)
		}

		switch schemaValue := value.(type) {
		case SchemaDict:
			// skip some conditions that do not need to check termination
			if key == Properties {
				if required, ok := schema[Required]; ok {
					if requiredList, ok := required.(SchemaList); ok {
						if len(requiredList) == 0 {
							needCheckTermination = false
						}
					}
				}
			} else if key == AdditionalProperties {
				needCheckTermination = false
			} else if len(requiredList) > 0 {
				findRequired := false
				for _, req := range requiredList {
					if key == req {
						findRequired = true
						break
					}
				}
				if !findRequired {
					needCheckTermination = false
				}
			}

			if err := v.TraverseAndCheckRefs(schemaValue, needCheckTermination, requiredList, newPath); err != nil {
				return err
			}
		case SchemaList:
			if key == AnyOf {
				for i, item := range schemaValue {
					if itemSchema, ok := item.(SchemaDict); ok {
						if err := v.TraverseAndCheckRefs(
							itemSchema,
							needCheckTermination,
							nil,
							newPath.ModifyAnyOfPart(i),
						); err != nil {
							return err
						}
					}
				}
			}
		}
	}

	return nil
}

// CalculateDefDepths computes the nesting depth each definition expands to.
// Like the termination check it memoizes expanded definitions -- keyed by the
// same purity rule, a depth computed without running into the path stack -- and
// gives up with an error past the shared step budget.
func (v *schemaValidator) CalculateDefDepths() (map[string]int, error) {
	defDepths := make(map[string]int)
	memo := make(map[string]int)

	var calculateDepthsRecursive func(schema SchemaDict, currentPath string, visitedRefs map[string]struct{}) (int, bool, error)
	calculateDepthsRecursive = func(schema SchemaDict, currentPath string, visitedRefs map[string]struct{}) (int, bool, error) {
		v.refWalkSteps++
		if v.refWalkSteps > maxRefWalkSteps {
			return 0, false, v.context.RaiseError("reference graph is too complex to validate within the step budget", rootSchemaPath)
		}

		// The depth of basic type or empty schema is 0
		if len(schema) == 0 {
			return 0, false, nil
		}

		// Record the depth of current path
		defDepths[currentPath] = 0 // Initial depth is 0
		maxDepth := 0
		cut := false

		if ref, ok := schema[Ref].(string); ok {
			if _, exists := visitedRefs[ref]; exists {
				// Cycle guard: the ref contributes no depth, and the result may
				// depend on the entry stack, so it must not be cached.
				cut = true
			} else if depth, done := memo[ref]; done {
				maxDepth = depth
			} else {
				visitedRefs[ref] = struct{}{}
				resolved, err := v.utils.ResolveRef(v.context.SchemaRoot, ref, v.context, rootSchemaPath)
				if err == nil && resolved != nil {
					depth, refCut, err := calculateDepthsRecursive(resolved, ref, visitedRefs)
					if err != nil {
						return 0, false, err
					}
					if !refCut {
						memo[ref] = depth
					}
					cut = cut || refCut
					maxDepth = depth
				}
			}
		}

		if props, ok := schema[Properties].(SchemaDict); ok {
			propsDepth := 1
			for propName, propSchema := range props {
				propSchemaObj, ok := propSchema.(SchemaDict)
				if !ok {
					continue
				}
				propPath := fmt.Sprintf("%s/properties/%s", currentPath, propName)

				// Create a new copy of visited refs for each property
				propVisited := make(map[string]struct{})
				for k, v := range visitedRefs {
					propVisited[k] = v
				}

				subDepth, propCut, err := calculateDepthsRecursive(propSchemaObj, propPath, propVisited)
				if err != nil {
					return 0, false, err
				}
				cut = cut || propCut
				if 1+subDepth > propsDepth {
					propsDepth = 1 + subDepth
				}
			}
			if propsDepth > maxDepth {
				maxDepth = propsDepth
			}
		}

		if anyOf, ok := schema[AnyOf].(SchemaList); ok {
			for i, subschema := range anyOf {
				subSchemaObj, ok := subschema.(SchemaDict)
				if !ok {
					continue
				}
				subPath := fmt.Sprintf("%s/anyOf/%d", currentPath, i)

				// Create a new copy of visited refs for each anyOf branch
				branchVisited := make(map[string]struct{})
				for k, v := range visitedRefs {
					branchVisited[k] = v
				}

				subDepth, branchCut, err := calculateDepthsRecursive(subSchemaObj, subPath, branchVisited)
				if err != nil {
					return 0, false, err
				}
				cut = cut || branchCut
				if subDepth > maxDepth {
					maxDepth = subDepth
				}
			}
		}

		if addProps, ok := schema[AdditionalProperties].(SchemaDict); ok {
			addPropsPath := fmt.Sprintf("%s/additionalProperties", currentPath)

			// Create a new copy of visited refs
			addPropsVisited := make(map[string]struct{})
			for k, v := range visitedRefs {
				addPropsVisited[k] = v
			}

			subDepth, addPropsCut, err := calculateDepthsRecursive(addProps, addPropsPath, addPropsVisited)
			if err != nil {
				return 0, false, err
			}
			cut = cut || addPropsCut
			if subDepth > maxDepth {
				maxDepth = subDepth
			}
		}

		// Update the final depth of current path
		defDepths[currentPath] = maxDepth
		return maxDepth, cut, nil
	}

	// Traverse from $defs
	if defs, ok := v.context.SchemaRoot[Defs].(SchemaDict); ok {
		for defName, defSchema := range defs {
			defSchemaObj, ok := defSchema.(SchemaDict)
			if !ok {
				continue
			}
			basePath := fmt.Sprintf("#/$defs/%s", defName)
			if _, _, err := calculateDepthsRecursive(defSchemaObj, basePath, make(map[string]struct{})); err != nil {
				return nil, err
			}
		}
	}

	return defDepths, nil
}

// CheckRefTermination checks if a reference can be terminated
func (v *schemaValidator) CheckRefTermination(schema SchemaDict, visitedRefs map[string]struct{}, path schemaPath) (bool, error) {
	// The memo is shared across every call of one validation, so a definition
	// is expanded once no matter how many use sites point at it.
	if v.terminationMemo == nil {
		v.terminationMemo = make(map[string]bool)
	}
	terminates, _, err := v.checkRefTermination(schema, visitedRefs, v.terminationMemo, path)
	return terminates, err
}

// checkRefTermination is the recursive body of CheckRefTermination. The memo
// caches the verdict of each fully expanded $ref, so sibling properties that
// point at the same definition do not each re-walk its whole subgraph --
// without it a chain of definitions referenced twice per level costs 2^n walks.
//
// A verdict is cached only when computing it never ran into a reference already
// on the path stack: such a verdict is a property of the definition alone and
// holds for every later entry point. A walk that did run into the stack may
// have been cut short by entry-specific state, so its verdict is used but not
// cached. The second return value reports whether that happened.
func (v *schemaValidator) checkRefTermination(schema SchemaDict, visitedRefs map[string]struct{}, memo map[string]bool, path schemaPath) (bool, bool, error) {
	v.refWalkSteps++
	if v.refWalkSteps > maxRefWalkSteps {
		return false, false, v.context.RaiseError("reference graph is too complex to validate within the step budget", path)
	}

	// Non-object/array basic types can terminate
	var checkType string
	if typeVal, ok := schema[Type]; ok {
		switch t := typeVal.(type) {
		case string:
			if t != Object && t != Array {
				return true, false, nil
			}
			checkType = t
		case SchemaList:
			for _, typ := range t {
				if typeStr, ok := typ.(string); ok && typeStr != Object && typeStr != Array {
					return true, false, nil
				}

				// should be object or array and len(t) == 1/2
				checkType = typ.(string)
			}
		}
	}

	cut := false

	// Array items if empty can terminate
	if checkType == Array {
		// Without a positive minItems the empty array is a valid instance, so the
		// array terminates no matter what items demands. Only a non-empty lower
		// bound forces us to prove that items itself can terminate.
		if minItems, ok := schema[MinItems].(float64); !ok || minItems <= 0 {
			return true, false, nil
		}

		items, exists := schema[Items]
		if !exists || items == nil {
			return true, false, nil
		}

		if itemsDict, ok := items.(SchemaDict); ok && len(itemsDict) == 0 {
			return true, false, nil
		}

		// check array items whether it can terminate
		if itemsDict, ok := items.(SchemaDict); ok {
			terminates, itemsCut, err := v.checkRefTermination(itemsDict, visitedRefs, memo, path.Append(Items))
			if err != nil {
				return false, false, err
			}
			if terminates {
				return true, itemsCut, nil
			}
			cut = cut || itemsCut
		}
	}

	// Object required
	if checkType == Object {
		required, exists := schema[Required]
		// required if empty can terminate
		if !exists || required == nil {
			return true, false, nil
		}

		if requiredList, ok := required.(SchemaList); ok && len(requiredList) == 0 {
			return true, false, nil
		}

		// if properties is empty, it can terminate
		props, hasProps := schema[Properties].(SchemaDict)
		if !hasProps || len(props) == 0 {
			return true, false, nil
		}

		// iterate properties
		requiredSet := make(map[string]struct{})
		for _, req := range required.(SchemaList) {
			if reqStr, ok := req.(string); ok {
				requiredSet[reqStr] = struct{}{}
			}
		}

		// Every required property has to be present in a valid instance, so the
		// object only terminates when all of them do. A single non-terminating
		// required property makes the object unsatisfiable by any finite document.
		for propName, propSchema := range props {
			propSchemaObj, ok := propSchema.(SchemaDict)
			if !ok {
				return false, false, v.context.RaiseErrorWithSimplify("property schema must be an object", path.Append(propName), SimplifyRemoveProperties)
			}

			// only check required properties
			if _, exists := requiredSet[propName]; !exists {
				continue
			}

			// Each property walks its own visited set; two sibling properties
			// pointing at the same $ref is not a cycle.
			propRefs := make(map[string]struct{})
			for k := range visitedRefs {
				propRefs[k] = struct{}{}
			}

			terminates, propCut, err := v.checkRefTermination(propSchemaObj, propRefs, memo, path.Append(Properties, propName))
			if err != nil {
				return false, false, err
			}
			if !terminates {
				return false, propCut, nil
			}
			cut = cut || propCut
		}

		return true, cut, nil
	}

	// Check anyOf branches
	if anyOf, ok := schema[AnyOf].(SchemaList); ok {
		// if anyOf is empty, it can terminate
		if len(anyOf) == 0 {
			return true, false, nil
		}

		allRefs := make(map[string]struct{})
		for i, item := range anyOf {
			itemSchema, ok := item.(SchemaDict)
			if !ok {
				return false, false, v.context.RaiseErrorWithSimplify("schema in anyOf must be an object", path.Append(AnyOf), SimplifyRemoveAnyOf)
			}

			// Create a new copy of visited refs for each branch
			branchRefs := make(map[string]struct{})
			for k := range visitedRefs {
				branchRefs[k] = struct{}{}
			}

			terminates, branchCut, err := v.checkRefTermination(itemSchema, branchRefs, memo, path.Append(AnyOf, strconv.Itoa(i)))
			if err != nil {
				return false, false, err
			}
			if terminates {
				// Update visited refs with branch refs
				for k := range branchRefs {
					visitedRefs[k] = struct{}{}
				}
				return true, branchCut, nil
			}
			cut = cut || branchCut

			// Collect all refs from this branch
			for k := range branchRefs {
				allRefs[k] = struct{}{}
			}
		}

		// Update visited refs with all collected refs
		for k := range allRefs {
			visitedRefs[k] = struct{}{}
		}
	}

	// Check ref
	if ref, ok := schema[Ref].(string); ok {
		if _, exists := visitedRefs[ref]; exists {
			return false, true, nil
		}

		if result, done := memo[ref]; done {
			return result, false, nil
		}

		visitedRefs[ref] = struct{}{}
		target, err := v.utils.ResolveRef(v.context.SchemaRoot, ref, v.context, path)
		if err != nil {
			return false, false, v.context.RaiseError(fmt.Sprintf("invalid $ref path: %s", ref), path)
		}

		result, targetCut, err := v.checkRefTermination(target, visitedRefs, memo, path.Append(Ref))
		if err != nil {
			return false, false, err
		}
		if !targetCut {
			memo[ref] = result
		}
		return result, targetCut, nil
	}

	if len(schema) == 0 {
		return true, false, nil
	}

	return false, cut, nil
}

// ExpandRef expands a reference
func (v *schemaValidator) ExpandRef(schema SchemaDict, visitedRefs map[string]struct{}, path schemaPath) (SchemaDict, error) {
	if schema == nil || schema[Ref] == nil {
		return schema, nil
	}

	refValue, ok := schema[Ref].(string)
	if !ok {
		return nil, v.context.RaiseErrorWithSimplify("$ref must be a string", path.Append(Ref), SimplifyRemoveRef)
	}

	ref := refValue
	if _, exists := visitedRefs[ref]; exists {
		return schema, nil // Avoid circular references
	}

	visitedRefs[ref] = struct{}{}
	resolved, err := v.utils.ResolveRef(v.context.SchemaRoot, ref, v.context, rootSchemaPath)
	if err != nil {
		return nil, err
	}

	// First expansion
	currentResolved := make(SchemaDict)
	for k, v := range resolved {
		currentResolved[k] = v
	}

	// Keep expanding if only contains $ref and common keywords
	keepKeys := make(SchemaDict)
	currentLayerRef := refValue
	previousLayerRef := ""
	for {
		if currentResolved[Ref] == nil {
			break
		}

		keys := make(map[string]struct{})
		for k := range currentResolved {
			keys[k] = struct{}{}
		}

		// Check if there are other keywords besides common keys and $ref
		hasOtherKeys := false
		for k := range keys {
			if k != Ref && !CommonKeywords[k] {
				hasOtherKeys = true
				break
			}
		}

		if hasOtherKeys {
			break
		}

		nextRef, ok := currentResolved[Ref].(string)
		if !ok {
			return nil, v.context.RaiseErrorWithSimplify("$ref must be a string", path.Append(Ref), SimplifyRemoveRef)
		}

		if _, exists := visitedRefs[nextRef]; exists {
			break
		}

		visitedRefs[nextRef] = struct{}{}
		nextResolved, err := v.utils.ResolveRef(v.context.SchemaRoot, nextRef, v.context, rootSchemaPath)
		if err != nil {
			return nil, err
		}

		// Keep common keywords from current level
		for k := range currentResolved {
			if CommonKeywords[k] {
				if _, exists := keepKeys[k]; exists {
					if v.config.IsUltra() || v.config.IsTest() {
						simplifyPath := path
						outerRef := previousLayerRef
						if outerRef == "" {
							outerRef = currentLayerRef
						}
						if defsPath, err := refToSchemaPath(outerRef); err == nil {
							simplifyPath = defsPath
						}
						return nil, v.context.RaiseErrorWithSimplify(
							fmt.Sprintf(
								`conflicting keywords found after $ref expansion: keyword %q appears at multiple levels in a chained "$ref"; keep it in only one place`,
								k,
							),
							simplifyPath, simplifyFuncForKeywordConflicts([]string{k}),
						)
					}
					continue
				}
				keepKeys[k] = currentResolved[k]
			}
		}

		previousLayerRef = currentLayerRef
		currentLayerRef = nextRef
		currentResolved = nextResolved
	}

	result := make(SchemaDict, len(currentResolved)+len(keepKeys))
	for k, v := range currentResolved {
		result[k] = v
	}
	for k, v := range keepKeys {
		result[k] = v
	}

	return result, nil
}

// CheckRefContext checks if expanded ref schema conflicts with parent schema
func (v *schemaValidator) CheckRefContext(parent SchemaDict, refSchema SchemaDict, path schemaPath) error {
	if refSchema == nil {
		return nil
	}

	// First check for direct keyword conflicts
	parentKeywords := make(map[string]struct{})
	for k := range parent {
		if k != Ref {
			parentKeywords[k] = struct{}{}
		}
	}

	// Contradictory overlaps come first: their conjunction admits no instance at
	// all, so no amount of merging produces a usable schema. Only strict and above
	// reject them; see TraverseSchema for why looser levels let them through.
	if keyword := unsatisfiableOverlap(parent, refSchema); keyword != "" && v.config.IsGreaterThanStrict() {
		return v.context.RaiseErrorWithSimplify(
			fmt.Sprintf(
				"%s conflicts with the referenced schema: the intersection is empty, so no instance can satisfy both",
				keyword,
			),
			path, SimplifyDropContradictingRefSibling,
		)
	}

	var conflicts []string
	for k := range refSchema {
		if _, exists := parentKeywords[k]; exists {
			// Repeating a keyword next to $ref is legal under 2020-12: both
			// assertions apply and the effective constraint is their conjunction.
			// Only the canonicalising levels report it, so that Canonical folds the
			// duplicate away while looser levels accept the schema as written.
			if !(v.config.IsUltra() || v.config.IsTest()) {
				continue
			}
			conflicts = append(conflicts, k)
		}
	}

	if len(conflicts) > 0 {
		sort.Strings(conflicts)
		return v.context.RaiseErrorWithSimplify(
			fmt.Sprintf(
				`conflicting keywords found after $ref expansion: keywords (%s) are defined both alongside "$ref" and in the referenced schema; remove the duplicates`,
				strings.Join(conflicts, ", "),
			),
			path, simplifyFuncForKeywordConflicts(conflicts),
		)
	}

	// Validate if the parent schema is valid after ref expansion
	_, hasTypeInParent := parent[Type]
	_, hasAnyOfInRef := refSchema[AnyOf]
	_, hasTypeInRef := refSchema[Type]
	_, hasAnyOfInParent := parent[AnyOf]

	if (hasTypeInParent && hasAnyOfInRef) || (hasTypeInRef && hasAnyOfInParent) {
		return v.context.RaiseErrorWithSimplify("invalid schema after $ref expansion: (when using anyOf, type should be defined in anyOf items instead of the parent schema)", path, SimplifyRemoveParentSchema)
	}

	// If refSchema contains anyOf, check for conflicts after expansion
	if anyOfValue, ok := refSchema[AnyOf]; ok {
		if anyOfList, ok := anyOfValue.(SchemaList); ok {
			for _, branchInterface := range anyOfList {
				branch, ok := branchInterface.(SchemaDict)
				if !ok {
					continue
				}

				// Check if keywords in each anyOf branch conflict with parent
				branchKeywords := make(map[string]struct{})
				for k := range branch {
					branchKeywords[k] = struct{}{}
				}

				var branchConflicts []string
				for k := range parentKeywords {
					if _, exists := branchKeywords[k]; exists && k != AnyOf {
						if CommonKeywords[k] && !(v.config.IsUltra() || v.config.IsTest()) {
							continue
						}
						branchConflicts = append(branchConflicts, k)
					}
				}

				if len(branchConflicts) > 0 {
					sort.Strings(branchConflicts)
					return v.context.RaiseErrorWithSimplify(
						fmt.Sprintf(
							`conflicting keywords found in anyOf after ref expansion: keywords (%s) are defined alongside "$ref" and inside anyOf in the referenced schema; define them in only one place`,
							strings.Join(branchConflicts, ", "),
						),
						path, simplifyFuncForKeywordConflicts(branchConflicts),
					)
				}
			}
		}
	}

	// Check if ref appears in a valid context
	parts := path.Parts

	if len(parts) >= 1 && v.isInRefAllowedContexts(path.Last()) {
		return nil
	} else if len(parts) >= 2 && parts[len(parts)-2] == Properties {
		return nil
	} else if len(parts) == 1 {
		return nil
	} else {
		return v.context.RaiseErrorWithSimplify("$ref is not allowed in this schema.", path, SimplifyRemoveRef)
	}
}

// Helper function to check if a path part is in the allowed contexts
func (v *schemaValidator) isInRefAllowedContexts(part string) bool {
	allowedContexts := map[string]bool{
		AdditionalProperties: true,
		AnyOf:                true,
		Items:                true,
	}

	if allowedContexts[part] {
		return true
	}

	return strings.HasPrefix(part, AnyOf)
}

func parseSchema(jsonStr string) (Schema, error) {
	var schemaDict SchemaDict
	err := json.Unmarshal([]byte(jsonStr), &schemaDict)
	if err != nil {
		switch e := err.(type) {
		case *json.SyntaxError:
			return nil, NewUnmarshalError(fmt.Errorf("JSON syntax error at offset %d: %s", e.Offset, e.Error()))
		case *json.UnmarshalTypeError:
			return nil, NewUnmarshalError(fmt.Errorf("JSON type error at offset %d: expected %s but got %s",
				e.Offset, e.Type, e.Value))
		default:
			return nil, NewUnmarshalError(err)
		}
	}
	return schemaDict, nil
}