Elements of AnyStr are difficult to handle

[finite-state-machine]

Consider the following code (which assumes a symbol called AnyStrElem is available):

from __future__ import annotations

from typing import (
        Any,
        AnyStr,
        Dict,
        Generic,
        List,
        Mapping,
        )

from typing_extensions import (
        assert_never,
        )

AnyStrElem = Any  # should be type of an AnyStr element


class ArbitraryRadixDigits(Generic[AnyStr]):
    '''encode integers into arbitrary number bases

    Examples:

        bytes:

            >>> ard_bytes = ArbitraryRadixDigits(b'0123456789')
            >>> ard_bytes.encode_value(1234)
            b'1234'
            >>> ard_bytes.decode_value(b'1234')
            1234

            >>> ard_bytes = ArbitraryRadixDigits(b'0123456789abcdef')
            >>> ard_bytes.encode_value(0xDECAFBAD)
            b'decafbad'
            >>> hex(ard_bytes.decode_value(b'decafbad'))
            '0xdecafbad'

        str:

            >>> ard_str = ArbitraryRadixDigits('0123456789')
            >>> ard_str.encode_value(1234)
            '1234'
            >>> ard_str.decode_value('1234')
            1234

            >>> ard_str = ArbitraryRadixDigits('0123456789abcdef')
            >>> ard_str.encode_value(0xDECAFBAD)
            'decafbad'
            >>> hex(ard_str.decode_value('decafbad'))
            '0xdecafbad'
    '''
    _radix: int
    _fwd: AnyStr
    _rev: Mapping[AnyStrElem, int]

    def __init__(self, digits: AnyStr):

        self._radix = len(digits)
        self._fwd = digits

        rev: Dict[AnyStrElem, int] = {}
        for index, elem in enumerate(digits):
            assert elem not in rev
            rev[elem] = index

        self._rev = rev

    def value_to_digit(self, value: int) -> AnyStrElem:
        assert 0 <= value < self._radix
        return self._fwd[value]

    def digit_to_value(self, digit: AnyStrElem) -> int:
        return self._rev[digit]
 
    def encode_value(self, value: int) -> AnyStr:
        assert value >= 0
        digits: List[AnyStrElem] = []  # little endian

        while value:
            value, digit_value = divmod(value, self._radix)
            assert 0 <= digit_value < self._radix
            digits.append(self.value_to_digit(digit_value))

        digits.reverse()  # make big endian

        # this is convoluted enough:
        if isinstance(self._fwd, bytes):
            return bytes(digits)
        elif isinstance(self._fwd, str):
            return ''.join(digits)
        else:  # pragma: no cover
            assert_never(self._fwd)

    def decode_value(self, digits: AnyStr) -> int:

        ret = 0
        for digit in digits:
            ret *= self._radix
            ret += self.digit_to_value(digit)
        return ret

(Even using this hypothetical facility (AnyStrElem), there's some awkwardness: I'm aware of no interface to str and bytes which can be used to construct an AnyStr from a sequence of AnyStrElems; handling this accounts for about half the length of encode_value().)

Of course, we don't have AnyStrElem, so instead we're forced to write something like this:

from __future__ import annotations

from typing import (
        Any,
        AnyStr,
        cast,
        Dict,
        Generic,
        List,
        Mapping,
        overload,
        Union,
        )

from typing_extensions import (
        assert_never,
        )

#                                                         ──────────────
#                                                          UNCHANGED ->
#                                                         ──────────────

class ArbitraryRadixDigits(Generic[AnyStr]):
    '''encode/decode integers into arbitrary number bases

    Examples:

        bytes:

            >>> ard_bytes = ArbitraryRadixDigits(b'0123456789')
            >>> ard_bytes.encode_value(1234)
            b'1234'
            >>> ard_bytes.decode_value(b'1234')
            1234

            >>> ard_bytes = ArbitraryRadixDigits(b'0123456789abcdef')
            >>> ard_bytes.encode_value(0xDECAFBAD)
            b'decafbad'
            >>> hex(ard_bytes.decode_value(b'decafbad'))
            '0xdecafbad'

        str:

            >>> ard_str = ArbitraryRadixDigits('0123456789')
            >>> ard_str.encode_value(1234)
            '1234'
            >>> ard_str.decode_value('1234')
            1234

            >>> ard_str = ArbitraryRadixDigits('0123456789abcdef')
            >>> ard_str.encode_value(0xDECAFBAD)
            'decafbad'
            >>> hex(ard_str.decode_value('decafbad'))
            '0xdecafbad'
    '''
#                                                         ──────────────
#                                                          <- UNCHANGED
#                                                         ──────────────
    _radix: int
    _fwd: AnyStr
    __rev: Union[Mapping[str, int], Mapping[int, int]]

    def __init__(self, digits: AnyStr):

        self._radix = len(digits)
        self._fwd = digits

        rev: Dict[Union[str, int], int] = {}
        for index, elem in enumerate(digits):
            assert elem not in rev
            rev[elem] = index

        self.__rev = rev  # type: ignore[assignment]

    @overload
    def value_to_digit(self: ArbitraryRadixDigits[str], value: int) -> str: ...
    @overload
    def value_to_digit(self: ArbitraryRadixDigits[bytes], value: int) -> int: ...

    def value_to_digit(self, value: int) -> Union[str, int]:
        assert 0 <= value < self._radix
        return self._fwd[value]

    @overload
    def digit_to_value(self: ArbitraryRadixDigits[str], digit: str) -> int: ...
    @overload
    def digit_to_value(self: ArbitraryRadixDigits[bytes], digit: int) -> int: ...

    def digit_to_value(self, digit: Union[str, int]) -> int:
        return self._rev()[digit]  # type: ignore[index]

    @overload
    def _rev(self: ArbitraryRadixDigits[str]) -> Mapping[str, int]: ...
    @overload
    def _rev(self: ArbitraryRadixDigits[bytes]) -> Mapping[int, int]: ...

    def _rev(self) -> Union[Mapping[str, int], Mapping[int, int]]:
        return self.__rev

    def encode_value(self, value: int) -> AnyStr:
        assert value >= 0
        digits: List[Union[str, int]] = []  # little endian

        while value:
            value, digit_value = divmod(value, self._radix)
            assert 0 <= digit_value < self._radix
            digits.append(self.value_to_digit(digit_value))

        digits.reverse()  # make big endian

        # this is convoluted enough:
        if isinstance(self._fwd, bytes):
            return bytes(cast(List[int], digits))
        elif isinstance(self._fwd, str):
            return ''.join(cast(List[str], digits))
        else:  # pragma: no cover
            assert_never(self._fwd)

    def decode_value(self, digits: AnyStr) -> int:

        ret = 0
        for digit in digits:
            ret *= self._radix
            ret += self.digit_to_value(digit)
        return ret

The latter is far less readable, quite a bit less safe (more casts, type: ignores, etc.), and almost twice as long by character count.¹ (We could have skipped value_to_digit() and digit_to_value() in the first version, referencing self._fwd and self._rev directly, making the contrast in length even greater.)

Proposal One: AnyStrElem

The simplest fix would be to add AnyStrElem as a special case, as used in the first example above.

Proposal Two: TypeOf

Introduce an operator which sets a TypeAlias to the type of some expression.

This would read something like this:

class ArbitraryRadixDigits(Generic[AnyStr]):
    __dummy_any_str: AnyStr
    AnyStrElem = TypeOf[__dummy_any_str[0]]

This would be more legible (and less polluting of the namespace) with a corresponding ValueOfType operator:

class ArbitraryRadixDigits(Generic[AnyStr]):
    AnyStrElem = TypeOf[ValueOfType[AnyStr][0]]

Discussion

• am I missing a more straight-forward approach?
• is this the right place to be having this discussion?

Thanks for taking the time to consider this problem!

Footnotes

1. about 65% longer after stripping imports, comments, docstrings, common indentation, and converting spaces to tabs ↩

[Daverball]

I don't think there's a very compelling case for AnyStrElem since element access of a generic in AnyStr seems like an exceedingly rare use case, while it is annoying that str and bytes element access is not uniform due to historic reasons it's also not something you generally should do, especially not on bytes, something like a bytearray or memoryview would be far more efficient. Also note that AnyStr isn't anything special, its implementation is literally just TypeVar('AnyStr', str, bytes), so adding a special construct related to that doesn't make much sense.

I don't think it's too big of an ask having to write the latter, sure it's less readable and it's not as type safe for the internals, but there's a way to get most of the way back to the first example by adding a TypeVar('AnyStrElem', str, int) and adding overloads to __init__ to bind the correct string and element type. It will look a little bit more silly as a ArbitraryRadixDigits[str, str] and ArbitraryRadixDigits[bytes, int], but you presumably would not have to contest with that very often due to the overloads on __init__ binding the type vars for you. Some prankster could technically explicitly create ArbitraryRadixDigits[str, int] which would not be legal, so it's not a perfect solution, but it seems good enough to me.

The more general case of TypeOf and ValueOfType is more compelling and could definitely lead to some nice simplifications in generics, but the semantics would have to be fairly strict about what you can use it on, since you are statically inferring types, especially considering the performance penalty if used too broadly. Things can get nasty here pretty quickly once you involve type unions and other more complex typing constructs, it would also be fairly easy to create circular dependencies that cannot be resolved.

[finite-state-machine]

Thanks, David! I really appreciate your thoughts.

Has anything like TypeOf/ValueOfType been proposed, and if so, are you aware of an issue, discussion, or similar I could peruse, and possibly link this thread to?

[Daverball]

There's this older issue which pretty much asks for the same thing: #769

I recall there were also some proposals for something that goes in a similar direction, but would be more geared towards TypedDict and similar structures with a KeyType and ElementType.