Problem 582912 · hard · Level 05 Advanced Algorithms & Graphs

Where Does the Data Break Its Type?

py-type-hints · recursion · typing.get_origin · typing.get_args · validation

Type hints are not checked when a program runs, so a configuration file loaded at run time can contain anything. Write mismatch(value, hint), which checks a value against a type hint and returns None if it fits, or the path to the first part that does not fit.

A path starts with value and adds [i] for the item at position i of a list or tuple and [key!r] for the value stored under a dictionary key, for example value[2]['price']. The hints to support, possibly nested:

  • a class such as int, str, bool or list: isinstance(value, cls), except that float also accepts an int (as type checkers do). None (or type(None)) accepts only None. Any accepts everything.
  • list[X] and set[X] / frozenset[X]: the right container, and every item fits X; dict[K, V]: a dict whose keys fit K and whose values fit V. Without arguments (typing.List) the items may be anything.
  • tuple[X, Y, Z]: a tuple of exactly that length with each item fitting its hint; tuple[X, ...]: a tuple of any length whose items all fit X.
  • X | Y, Optional[X] and Union[X, Y]: at least one alternative fits.
  • Literal[a, b]: the value equals one of the options and has the same type (so True does not fit Literal[1]).
  • Callable[...]: the value is callable.

Anything else (for example collections.abc.Iterable[int]) raises TypeError, since it cannot be checked.

Report the first problem in order: list and tuple items by position, dictionary entries in insertion order (for an entry, its key is checked before its value), depth first. The path points at the innermost part that fails, with these exceptions: a union, a set, a wrong container type, a tuple of the wrong length and a dictionary key that does not fit are reported at the path of the whole value (the union, set, container, tuple or dictionary).

The setup imports Any, Literal, Union, Optional, Callable and Iterable for the tests; price_list(n, seed, broken_at=None) generates price records (with one missing price if broken_at is given), and raises(fn, *args) returns the name of the exception a call raises.

Examples

Input:  mismatch([{"name": "oat", "price": 1.5}, {"name": "rye", "price": None}], list[dict[str, float | str]])
Output: "value[1]['price']"

Input:  mismatch({"lr": 0.1, "layers": (64, 32), "act": "relu"}, dict[str, float | tuple[int, ...] | Literal["relu", "tanh"]])
Output: None

Input:  mismatch((1, "a", 2.5), tuple[int, str])
Output: "value"

Constraints

  • Values have at most 10**5 parts in total; nesting is at most 20 levels deep.

Goals

  • Take a type hint apart with `typing.get_origin` and `typing.get_args`
  • Check nested data against a nested hint recursively
  • Report the exact location of the first value that does not fit
Starting Python…