Reason About Nested JSON Schema Validation

Problem Statement

Configuration services and event ingestion pipelines often validate incoming JSON payloads against a predefined schema before processing. Implement a lightweight schema validator that recursively checks a nested JSON-like structure (composed of Python dict, list, str, int, float, bool, and None) against a simplified JSON Schema definition.

Schema Specification

A schema is a dictionary that can contain the following keywords:

• "type": A string specifying the expected type: "object", "array", "string", "number" (accepts both int and float, but not bool), "boolean", or "null".
• "properties": A dictionary mapping property names to sub-schemas (applicable when type is "object"). Note that undeclared properties in the payload are allowed.
• "required": A list of string keys that must exist in an object (applicable when type is "object").
• "items": A sub-schema defining the expected schema for all elements in an array (applicable when type is "array").

Requirements

Write a function validate_schema(instance: Any, schema: dict) -> list[str] that returns a list of error strings. If the instance satisfies the schema, return an empty list [].

Each error message must follow the format "{path}: {message}", where:

• {path} is the dot/bracket notation path from the root. Use "$" for the root object itself, "$.field" for object properties, and "$[index]" (e.g., "$.users[0].name") for array elements.
• {message} must be:
  • "expected , got " for type mismatches (actual types: "object", "array", "string", "number", "boolean", "null").
  • "missing required property ''" if a required property is absent.

Errors should be collected via depth-first search (DFS) traversal in a deterministic order (keys visited in schema definition order; array elements visited from index 0 upward).

Function Signature

def validate_schema(instance: Any, schema: dict) -> list[str]:
    pass

Examples

Example 1

schema = {
    "type": "object",
    "required": ["id", "tags"],
    "properties": {
        "id": {"type": "number"},
        "tags": {
            "type": "array",
            "items": {"type": "string"}
        }
    }
}

payload = {
    "id": "101",
    "tags": ["pinned", 42]
}

# Output:
# [
#   "$.id: expected number, got string",
#   "$.tags[1]: expected string, got number"
# ]

Example 2

schema = {
    "type": "object",
    "required": ["user"],
    "properties": {
        "user": {
            "type": "object",
            "required": ["email"]
        }
    }
}

payload = {"user": {}}

# Output:
# [
#   "$.user: missing required property 'email'"
# ]

Constraints & Edge Cases

• In Python, isinstance(True, int) is True. Ensure booleans are strictly identified as "boolean" and not "number".
• If a parent object fails a type check, do not attempt to validate its properties or required fields.
• An instance value of None maps to JSON type "null".