Validate Data Against a Schema

Data from an API arrives as nested dictionaries and lists, and a schema says what it should look like. Write validate(data, schema) that checks the dictionary data against the schema and returns every problem as a sorted list of strings. An empty list means the data is valid.

A schema is a dictionary from field names to types. A type is one of these:

• 'str', 'int', 'float' or 'bool': a value of that Python type. 'int' does not accept True or False, and 'float' accepts any int or float but not a bool.
• A dictionary: a nested object, that is a dict checked against that dictionary as its own schema.
• A list holding one type, such as ['int'] or [{'sku': 'str'}]: a list whose items all have that type.

A field name ending in ? is optional: 'email?' describes the field 'email', which may be missing but must have the right type when it is there. Every other field is required. A field that holds None is there, not missing, and None is the wrong type for every kind.

Report each problem as '<path>: <problem>', where the problem is one of:

• missing for a required field that is not there,
• unexpected for a field the schema does not mention,
• expected <kind> for a value of the wrong type, where <kind> is the type's name, or object for a dictionary type, or list for a list type. A value of the wrong type is not checked any deeper.

A path is the field's name at the top level (age), adds .name for a field inside an object (address.city), and adds [i] for item i of a list (tags[2], orders[0].sku). Sort the problems with Python's normal string order.

Examples

schema = {
    'name': 'str',
    'age': 'int',
    'email?': 'str',
    'address': {'city': 'str', 'zip': 'str'},
    'tags': ['str'],
}
data = {'name': 'Ana', 'age': '31', 'address': {'city': 'Lima'}, 'tags': ['a', 7], 'admin': True}
validate(data, schema)
# returns ['address.zip: missing', 'admin: unexpected', 'age: expected int', 'tags[1]: expected str']

The optional email is missing, which is fine.

Constraints

• Objects are nested at most 50 levels deep, and lists hold up to 50,000 items.
• Field names in data are strings that never end in ?.