Flatten a sequence of values
(
value: list[Any] | tuple[Any, ...],
json_compat_keys: bool,
seen: set[int],
flatten_formattable_subclasses: bool,
key_formatter: Callable[[Any], Any] | None,
)
| 29 | |
| 30 | |
| 31 | def _flatten_sequence( |
| 32 | value: list[Any] | tuple[Any, ...], |
| 33 | json_compat_keys: bool, |
| 34 | seen: set[int], |
| 35 | flatten_formattable_subclasses: bool, |
| 36 | key_formatter: Callable[[Any], Any] | None, |
| 37 | ) -> FLATTEN_RET_TYPE: |
| 38 | """Flatten a sequence of values""" |
| 39 | base_type: type[list[Any] | tuple[Any, ...]] |
| 40 | if isinstance(value, list): |
| 41 | base_type = list |
| 42 | elif isinstance(value, tuple): |
| 43 | base_type = tuple |
| 44 | else: |
| 45 | raise ValueError("value is not a list or tuple: ", value) |
| 46 | |
| 47 | # Algorithm: |
| 48 | # |
| 49 | # Accumulate a list of flattened pieces and unflattener functions, |
| 50 | # one for each chunk of value. |
| 51 | # |
| 52 | # A chunk is one of the following: |
| 53 | # 1 a sequence (possibly empty) of leaves |
| 54 | # 2 a nested structure |
| 55 | # |
| 56 | # Chunks of type 1 are a base case |
| 57 | # Chunks of type 2 are recursed on using flatten |
| 58 | # |
| 59 | # Implementing chunks of type 1 as a base case significantly decreases |
| 60 | # the recursion stack depth compared to the reference implementation |
| 61 | if not value: |
| 62 | # unflattener returns an empty tuple or empty list |
| 63 | return [], lambda _: base_type() |
| 64 | |
| 65 | lengths = [] |
| 66 | flattened_pieces: list[list[Any]] = [] |
| 67 | unflatteners: list[UNFLATTEN_TYPE] = [] |
| 68 | i = 0 |
| 69 | while i < len(value): |
| 70 | if _is_leaf(value[i]): |
| 71 | # process a chunk of type 1: a sequence of leaves |
| 72 | lengths.append(0) |
| 73 | flattened_pieces.append([]) |
| 74 | while i < len(value) and _is_leaf(value[i]): |
| 75 | flattened_pieces[-1].append(value[i]) |
| 76 | lengths[-1] += 1 |
| 77 | i += 1 |
| 78 | unflatteners.append(lambda x: x) |
| 79 | # if we haven't exhausted the sequence, then we've hit a value that |
| 80 | # is not a leaf |
| 81 | if i < len(value): |
| 82 | assert not _is_leaf(value[i]) |
| 83 | flattened, u = _flatten( |
| 84 | value[i], |
| 85 | json_compat_keys, |
| 86 | seen, |
| 87 | flatten_formattable_subclasses=flatten_formattable_subclasses, |
| 88 | key_formatter=key_formatter, |