comparison mercurial/utils/cborutil.py @ 43076:2372284d9457

formatting: blacken the codebase

This is using my patch to black
(https://github.com/psf/black/pull/826) so we don't un-wrap collection
literals.

Done with:

  hg files 'set:**.py - mercurial/thirdparty/** - "contrib/python-zstandard/**"' | xargs black -S

# skip-blame mass-reformatting only

# no-check-commit reformats foo_bar functions

Differential Revision: https://phab.mercurial-scm.org/D6971

43075:57875cf423c9

SEMANTIC_TAG_FINITE_SET = 258

# Indefinite types begin with their major type ORd with information value 31.
BEGIN_INDEFINITE_BYTESTRING = struct.pack(
    r'>B', MAJOR_TYPE_BYTESTRING << 5 | SUBTYPE_INDEFINITE)
BEGIN_INDEFINITE_ARRAY = struct.pack(
    r'>B', MAJOR_TYPE_ARRAY << 5 | SUBTYPE_INDEFINITE)
BEGIN_INDEFINITE_MAP = struct.pack(
    r'>B', MAJOR_TYPE_MAP << 5 | SUBTYPE_INDEFINITE)

ENCODED_LENGTH_1 = struct.Struct(r'>B')
ENCODED_LENGTH_2 = struct.Struct(r'>BB')
ENCODED_LENGTH_3 = struct.Struct(r'>BH')
ENCODED_LENGTH_4 = struct.Struct(r'>BL')
ENCODED_LENGTH_5 = struct.Struct(r'>BQ')

# The break ends an indefinite length item.
BREAK = b'\xff'
BREAK_INT = 255

def encodelength(majortype, length):
    """Obtain a value encoding the major type and its length."""
    if length < 24:
        return ENCODED_LENGTH_1.pack(majortype << 5 | length)

    elif length < 4294967296:
        return ENCODED_LENGTH_4.pack(majortype << 5 | 26, length)
    else:
        return ENCODED_LENGTH_5.pack(majortype << 5 | 27, length)

def streamencodebytestring(v):
    yield encodelength(MAJOR_TYPE_BYTESTRING, len(v))
    yield v

def streamencodebytestringfromiter(it):
    """Convert an iterator of chunks to an indefinite bytestring.

    Given an input that is iterable and each element in the iterator is

        yield encodelength(MAJOR_TYPE_BYTESTRING, len(chunk))
        yield chunk

    yield BREAK

def streamencodeindefinitebytestring(source, chunksize=65536):
    """Given a large source buffer, emit as an indefinite length bytestring.

    This is a generator of chunks constituting the encoded CBOR data.
    """

    i = 0
    l = len(source)

    while True:
        chunk = source[i:i + chunksize]
        i += len(chunk)

        yield encodelength(MAJOR_TYPE_BYTESTRING, len(chunk))
        yield chunk

        if i >= l:
            break

    yield BREAK

def streamencodeint(v):
    if v >= 18446744073709551616 or v < -18446744073709551616:
        raise ValueError('big integers not supported')

    if v >= 0:
        yield encodelength(MAJOR_TYPE_UINT, v)
    else:
        yield encodelength(MAJOR_TYPE_NEGINT, abs(v) - 1)

def streamencodearray(l):
    """Encode a known size iterable to an array."""

    yield encodelength(MAJOR_TYPE_ARRAY, len(l))

    for i in l:
        for chunk in streamencode(i):
            yield chunk

def streamencodearrayfromiter(it):
    """Encode an iterator of items to an indefinite length array."""

    yield BEGIN_INDEFINITE_ARRAY

        for chunk in streamencode(i):
            yield chunk

    yield BREAK

def _mixedtypesortkey(v):
    return type(v).__name__, v

def streamencodeset(s):
    # https://www.iana.org/assignments/cbor-tags/cbor-tags.xhtml defines
    # semantic tag 258 for finite sets.
    yield encodelength(MAJOR_TYPE_SEMANTIC, SEMANTIC_TAG_FINITE_SET)

    for chunk in streamencodearray(sorted(s, key=_mixedtypesortkey)):
        yield chunk

def streamencodemap(d):
    """Encode dictionary to a generator.

    Does not supporting indefinite length dictionaries.
    """
    yield encodelength(MAJOR_TYPE_MAP, len(d))

    for key, value in sorted(d.iteritems(),
                             key=lambda x: _mixedtypesortkey(x[0])):
        for chunk in streamencode(key):
            yield chunk
        for chunk in streamencode(value):
            yield chunk

def streamencodemapfromiter(it):
    """Given an iterable of (key, value), encode to an indefinite length map."""
    yield BEGIN_INDEFINITE_MAP

        for chunk in streamencode(value):
            yield chunk

    yield BREAK

def streamencodebool(b):
    # major type 7, simple value 20 and 21.
    yield b'\xf5' if b else b'\xf4'

def streamencodenone(v):
    # major type 7, simple value 22.
    yield b'\xf6'

STREAM_ENCODERS = {
    bytes: streamencodebytestring,
    int: streamencodeint,
    pycompat.long: streamencodeint,

    set: streamencodeset,
    bool: streamencodebool,
    type(None): streamencodenone,
}

def streamencode(v):
    """Encode a value in a streaming manner.

    Given an input object, encode it to CBOR recursively.

    if not fn:
        raise ValueError('do not know how to encode %s' % type(v))

    return fn(v)

class CBORDecodeError(Exception):
    """Represents an error decoding CBOR."""

if sys.version_info.major >= 3:
    def _elementtointeger(b, i):
        return b[i]
else:
    def _elementtointeger(b, i):
        return ord(b[i])

STRUCT_BIG_UBYTE = struct.Struct(r'>B')
STRUCT_BIG_USHORT = struct.Struct('>H')
STRUCT_BIG_ULONG = struct.Struct('>L')
STRUCT_BIG_ULONGLONG = struct.Struct('>Q')

SPECIAL_START_INDEFINITE_BYTESTRING = 1
SPECIAL_START_ARRAY = 2
SPECIAL_START_MAP = 3
SPECIAL_START_SET = 4
SPECIAL_INDEFINITE_BREAK = 5

def decodeitem(b, offset=0):
    """Decode a new CBOR value from a buffer at offset.

    This function attempts to decode up to one complete CBOR value

            return False, None, readcount, SPECIAL_NONE

    elif majortype == MAJOR_TYPE_BYTESTRING:
        # Beginning of bytestrings are treated as uints in order to
        # decode their length, which may be indefinite.
        complete, size, readcount = decodeuint(subtype, b, offset,
                                               allowindefinite=True)

        # We don't know the size of the bytestring. It must be a definitive
        # length since the indefinite subtype would be encoded in the initial
        # byte.
        if not complete:

        # We know the length of the bytestring.
        if size is not None:
            # And the data is available in the buffer.
            if offset + readcount + size <= len(b):
                value = b[offset + readcount:offset + readcount + size]
                return True, value, readcount + size + 1, SPECIAL_NONE

            # And we need more data in order to return the bytestring.
            else:
                wanted = len(b) - offset - readcount - size

        # tags, we should probably move semantic tag handling into the caller.
        if tagvalue == SEMANTIC_TAG_FINITE_SET:
            if offset + readcount >= len(b):
                return False, None, -1, SPECIAL_NONE

            complete, size, readcount2, special = decodeitem(b,
                                                             offset + readcount)

            if not complete:
                return False, None, readcount2, SPECIAL_NONE

            if special != SPECIAL_START_ARRAY:
                raise CBORDecodeError('expected array after finite set '
                                      'semantic tag')

            return True, size, readcount + readcount2 + 1, SPECIAL_START_SET

        else:
            raise CBORDecodeError('semantic tag %d not allowed' % tagvalue)

        else:
            raise CBORDecodeError('special type %d not allowed' % subtype)
    else:
        assert False

def decodeuint(subtype, b, offset=0, allowindefinite=False):
    """Decode an unsigned integer.

    ``subtype`` is the lower 5 bits from the initial byte CBOR item
    "header." ``b`` is a buffer containing bytes. ``offset`` points to

        if allowindefinite:
            return True, None, 0
        else:
            raise CBORDecodeError('indefinite length uint not allowed here')
    elif subtype >= 28:
        raise CBORDecodeError('unsupported subtype on integer type: %d' %
                              subtype)

    if subtype == 24:
        s = STRUCT_BIG_UBYTE
    elif subtype == 25:
        s = STRUCT_BIG_USHORT

    if len(b) - offset >= s.size:
        return True, s.unpack_from(b, offset)[0], s.size
    else:
        return False, None, len(b) - offset - s.size

class bytestringchunk(bytes):
    """Represents a chunk/segment in an indefinite length bytestring.

    This behaves like a ``bytes`` but in addition has the ``isfirst``
    and ``islast`` attributes indicating whether this chunk is the first

        self = bytes.__new__(cls, v)
        self.isfirst = first
        self.islast = last

        return self

class sansiodecoder(object):
    """A CBOR decoder that doesn't perform its own I/O.

    To use, construct an instance and feed it segments containing

                # A normal value.
                if special == SPECIAL_NONE:
                    self._decodedvalues.append(value)

                elif special == SPECIAL_START_ARRAY:
                    self._collectionstack.append({
                        'remaining': value,
                        'v': [],
                    })
                    self._state = self._STATE_WANT_ARRAY_VALUE

                elif special == SPECIAL_START_MAP:
                    self._collectionstack.append({
                        'remaining': value,
                        'v': {},
                    })
                    self._state = self._STATE_WANT_MAP_KEY

                elif special == SPECIAL_START_SET:
                    self._collectionstack.append({
                        'remaining': value,
                        'v': set(),
                    })
                    self._state = self._STATE_WANT_SET_VALUE

                elif special == SPECIAL_START_INDEFINITE_BYTESTRING:
                    self._state = self._STATE_WANT_BYTESTRING_CHUNK_FIRST

                else:
                    raise CBORDecodeError('unhandled special state: %d' %
                                          special)

            # This value becomes an element of the current array.
            elif self._state == self._STATE_WANT_ARRAY_VALUE:
                # Simple values get appended.
                if special == SPECIAL_NONE:

                    newvalue = []

                    lastc['v'].append(newvalue)
                    lastc['remaining'] -= 1

                    self._collectionstack.append({
                        'remaining': value,
                        'v': newvalue,
                    })

                    # self._state doesn't need changed.

                # A map nested within an array.
                elif special == SPECIAL_START_MAP:

                    newvalue = {}

                    lastc['v'].append(newvalue)
                    lastc['remaining'] -= 1

                    self._collectionstack.append({
                        'remaining': value,
                        'v': newvalue
                    })

                    self._state = self._STATE_WANT_MAP_KEY

                elif special == SPECIAL_START_SET:
                    lastc = self._collectionstack[-1]
                    newvalue = set()

                    lastc['v'].append(newvalue)
                    lastc['remaining'] -= 1

                    self._collectionstack.append({
                        'remaining': value,
                        'v': newvalue,
                    })

                    self._state = self._STATE_WANT_SET_VALUE

                elif special == SPECIAL_START_INDEFINITE_BYTESTRING:
                    raise CBORDecodeError('indefinite length bytestrings '
                                          'not allowed as array values')

                else:
                    raise CBORDecodeError('unhandled special item when '
                                          'expecting array value: %d' % special)

            # This value becomes the key of the current map instance.
            elif self._state == self._STATE_WANT_MAP_KEY:
                if special == SPECIAL_NONE:
                    self._currentmapkey = value
                    self._state = self._STATE_WANT_MAP_VALUE

                elif special == SPECIAL_START_INDEFINITE_BYTESTRING:
                    raise CBORDecodeError('indefinite length bytestrings '
                                          'not allowed as map keys')

                elif special in (SPECIAL_START_ARRAY, SPECIAL_START_MAP,
                                 SPECIAL_START_SET):
                    raise CBORDecodeError('collections not supported as map '
                                          'keys')

                # We do not allow special values to be used as map keys.
                else:
                    raise CBORDecodeError('unhandled special item when '
                                          'expecting map key: %d' % special)

            # This value becomes the value of the current map key.
            elif self._state == self._STATE_WANT_MAP_VALUE:
                # Simple values simply get inserted into the map.
                if special == SPECIAL_NONE:

                    newvalue = []

                    lastc['v'][self._currentmapkey] = newvalue
                    lastc['remaining'] -= 1

                    self._collectionstack.append({
                        'remaining': value,
                        'v': newvalue,
                    })

                    self._state = self._STATE_WANT_ARRAY_VALUE

                # A new map is used as the map value.
                elif special == SPECIAL_START_MAP:

                    newvalue = {}

                    lastc['v'][self._currentmapkey] = newvalue
                    lastc['remaining'] -= 1

                    self._collectionstack.append({
                        'remaining': value,
                        'v': newvalue,
                    })

                    self._state = self._STATE_WANT_MAP_KEY

                # A new set is used as the map value.
                elif special == SPECIAL_START_SET:

                    newvalue = set()

                    lastc['v'][self._currentmapkey] = newvalue
                    lastc['remaining'] -= 1

                    self._collectionstack.append({
                        'remaining': value,
                        'v': newvalue,
                    })

                    self._state = self._STATE_WANT_SET_VALUE

                elif special == SPECIAL_START_INDEFINITE_BYTESTRING:
                    raise CBORDecodeError('indefinite length bytestrings not '
                                          'allowed as map values')

                else:
                    raise CBORDecodeError('unhandled special item when '
                                          'expecting map value: %d' % special)

                self._currentmapkey = None

            # This value is added to the current set.
            elif self._state == self._STATE_WANT_SET_VALUE:

                    lastc = self._collectionstack[-1]
                    lastc['v'].add(value)
                    lastc['remaining'] -= 1

                elif special == SPECIAL_START_INDEFINITE_BYTESTRING:
                    raise CBORDecodeError('indefinite length bytestrings not '
                                          'allowed as set values')

                elif special in (SPECIAL_START_ARRAY,
                                 SPECIAL_START_MAP,
                                 SPECIAL_START_SET):
                    raise CBORDecodeError('collections not allowed as set '
                                          'values')

                # We don't allow non-trivial types to exist as set values.
                else:
                    raise CBORDecodeError('unhandled special item when '
                                          'expecting set value: %d' % special)

            # This value represents the first chunk in an indefinite length
            # bytestring.
            elif self._state == self._STATE_WANT_BYTESTRING_CHUNK_FIRST:
                # We received a full chunk.
                if special == SPECIAL_NONE:
                    self._decodedvalues.append(bytestringchunk(value,
                                                               first=True))

                    self._state = self._STATE_WANT_BYTESTRING_CHUNK_SUBSEQUENT

                # The end of stream marker. This means it is an empty
                # indefinite length bytestring.
                elif special == SPECIAL_INDEFINITE_BREAK:
                    # We /could/ convert this to a b''. But we want to preserve
                    # the nature of the underlying data so consumers expecting
                    # an indefinite length bytestring get one.
                    self._decodedvalues.append(bytestringchunk(b'',
                                                               first=True,
                                                               last=True))

                    # Since indefinite length bytestrings can't be used in
                    # collections, we must be at the root level.
                    assert not self._collectionstack
                    self._state = self._STATE_NONE

                else:
                    raise CBORDecodeError('unexpected special value when '
                                          'expecting bytestring chunk: %d' %
                                          special)

            # This value represents the non-initial chunk in an indefinite
            # length bytestring.
            elif self._state == self._STATE_WANT_BYTESTRING_CHUNK_SUBSEQUENT:
                # We received a full chunk.

                    # collections, we must be at the root level.
                    assert not self._collectionstack
                    self._state = self._STATE_NONE

                else:
                    raise CBORDecodeError('unexpected special value when '
                                          'expecting bytestring chunk: %d' %
                                          special)

            else:
                raise CBORDecodeError('unhandled decoder state: %d' %
                                      self._state)

            # We could have just added the final value in a collection. End
            # all complete collections at the top of the stack.
            while True:
                # Bail if we're not waiting on a new collection item.
                if self._state not in (self._STATE_WANT_ARRAY_VALUE,
                                       self._STATE_WANT_MAP_KEY,
                                       self._STATE_WANT_SET_VALUE):
                    break

                # Or we are expecting more items for this collection.
                lastc = self._collectionstack[-1]

        l = list(self._decodedvalues)
        self._decodedvalues = []
        return l

class bufferingdecoder(object):
    """A CBOR decoder that buffers undecoded input.

    This is a glorified wrapper around ``sansiodecoder`` that adds a buffering
    layer. All input that isn't consumed by ``sansiodecoder`` will be buffered
    and concatenated with any new input that arrives later.

    TODO consider adding limits as to the maximum amount of data that can
    be buffered.
    """
    def __init__(self):
        self._decoder = sansiodecoder()
        self._chunks = []
        self._wanted = 0

        return available, readcount - oldlen, wanted

    def getavailable(self):
        return self._decoder.getavailable()

def decodeall(b):
    """Decode all CBOR items present in an iterable of bytes.

    In addition to regular decode errors, raises CBORDecodeError if the
    entirety of the passed buffer does not fully decode to complete CBOR

43076:2372284d9457

SEMANTIC_TAG_FINITE_SET = 258

# Indefinite types begin with their major type ORd with information value 31.
BEGIN_INDEFINITE_BYTESTRING = struct.pack(
    r'>B', MAJOR_TYPE_BYTESTRING << 5 | SUBTYPE_INDEFINITE
)
BEGIN_INDEFINITE_ARRAY = struct.pack(
    r'>B', MAJOR_TYPE_ARRAY << 5 | SUBTYPE_INDEFINITE
)
BEGIN_INDEFINITE_MAP = struct.pack(
    r'>B', MAJOR_TYPE_MAP << 5 | SUBTYPE_INDEFINITE
)

ENCODED_LENGTH_1 = struct.Struct(r'>B')
ENCODED_LENGTH_2 = struct.Struct(r'>BB')
ENCODED_LENGTH_3 = struct.Struct(r'>BH')
ENCODED_LENGTH_4 = struct.Struct(r'>BL')
ENCODED_LENGTH_5 = struct.Struct(r'>BQ')

# The break ends an indefinite length item.
BREAK = b'\xff'
BREAK_INT = 255


def encodelength(majortype, length):
    """Obtain a value encoding the major type and its length."""
    if length < 24:
        return ENCODED_LENGTH_1.pack(majortype << 5 | length)

    elif length < 4294967296:
        return ENCODED_LENGTH_4.pack(majortype << 5 | 26, length)
    else:
        return ENCODED_LENGTH_5.pack(majortype << 5 | 27, length)


def streamencodebytestring(v):
    yield encodelength(MAJOR_TYPE_BYTESTRING, len(v))
    yield v


def streamencodebytestringfromiter(it):
    """Convert an iterator of chunks to an indefinite bytestring.

    Given an input that is iterable and each element in the iterator is

        yield encodelength(MAJOR_TYPE_BYTESTRING, len(chunk))
        yield chunk

    yield BREAK


def streamencodeindefinitebytestring(source, chunksize=65536):
    """Given a large source buffer, emit as an indefinite length bytestring.

    This is a generator of chunks constituting the encoded CBOR data.
    """

    i = 0
    l = len(source)

    while True:
        chunk = source[i : i + chunksize]
        i += len(chunk)

        yield encodelength(MAJOR_TYPE_BYTESTRING, len(chunk))
        yield chunk

        if i >= l:
            break

    yield BREAK


def streamencodeint(v):
    if v >= 18446744073709551616 or v < -18446744073709551616:
        raise ValueError('big integers not supported')

    if v >= 0:
        yield encodelength(MAJOR_TYPE_UINT, v)
    else:
        yield encodelength(MAJOR_TYPE_NEGINT, abs(v) - 1)


def streamencodearray(l):
    """Encode a known size iterable to an array."""

    yield encodelength(MAJOR_TYPE_ARRAY, len(l))

    for i in l:
        for chunk in streamencode(i):
            yield chunk


def streamencodearrayfromiter(it):
    """Encode an iterator of items to an indefinite length array."""

    yield BEGIN_INDEFINITE_ARRAY

        for chunk in streamencode(i):
            yield chunk

    yield BREAK


def _mixedtypesortkey(v):
    return type(v).__name__, v


def streamencodeset(s):
    # https://www.iana.org/assignments/cbor-tags/cbor-tags.xhtml defines
    # semantic tag 258 for finite sets.
    yield encodelength(MAJOR_TYPE_SEMANTIC, SEMANTIC_TAG_FINITE_SET)

    for chunk in streamencodearray(sorted(s, key=_mixedtypesortkey)):
        yield chunk


def streamencodemap(d):
    """Encode dictionary to a generator.

    Does not supporting indefinite length dictionaries.
    """
    yield encodelength(MAJOR_TYPE_MAP, len(d))

    for key, value in sorted(
        d.iteritems(), key=lambda x: _mixedtypesortkey(x[0])
    ):
        for chunk in streamencode(key):
            yield chunk
        for chunk in streamencode(value):
            yield chunk


def streamencodemapfromiter(it):
    """Given an iterable of (key, value), encode to an indefinite length map."""
    yield BEGIN_INDEFINITE_MAP

        for chunk in streamencode(value):
            yield chunk

    yield BREAK


def streamencodebool(b):
    # major type 7, simple value 20 and 21.
    yield b'\xf5' if b else b'\xf4'


def streamencodenone(v):
    # major type 7, simple value 22.
    yield b'\xf6'


STREAM_ENCODERS = {
    bytes: streamencodebytestring,
    int: streamencodeint,
    pycompat.long: streamencodeint,

    set: streamencodeset,
    bool: streamencodebool,
    type(None): streamencodenone,
}


def streamencode(v):
    """Encode a value in a streaming manner.

    Given an input object, encode it to CBOR recursively.

    if not fn:
        raise ValueError('do not know how to encode %s' % type(v))

    return fn(v)


class CBORDecodeError(Exception):
    """Represents an error decoding CBOR."""


if sys.version_info.major >= 3:

    def _elementtointeger(b, i):
        return b[i]


else:

    def _elementtointeger(b, i):
        return ord(b[i])


STRUCT_BIG_UBYTE = struct.Struct(r'>B')
STRUCT_BIG_USHORT = struct.Struct('>H')
STRUCT_BIG_ULONG = struct.Struct('>L')
STRUCT_BIG_ULONGLONG = struct.Struct('>Q')

SPECIAL_START_INDEFINITE_BYTESTRING = 1
SPECIAL_START_ARRAY = 2
SPECIAL_START_MAP = 3
SPECIAL_START_SET = 4
SPECIAL_INDEFINITE_BREAK = 5


def decodeitem(b, offset=0):
    """Decode a new CBOR value from a buffer at offset.

    This function attempts to decode up to one complete CBOR value

            return False, None, readcount, SPECIAL_NONE

    elif majortype == MAJOR_TYPE_BYTESTRING:
        # Beginning of bytestrings are treated as uints in order to
        # decode their length, which may be indefinite.
        complete, size, readcount = decodeuint(
            subtype, b, offset, allowindefinite=True
        )

        # We don't know the size of the bytestring. It must be a definitive
        # length since the indefinite subtype would be encoded in the initial
        # byte.
        if not complete:

        # We know the length of the bytestring.
        if size is not None:
            # And the data is available in the buffer.
            if offset + readcount + size <= len(b):
                value = b[offset + readcount : offset + readcount + size]
                return True, value, readcount + size + 1, SPECIAL_NONE

            # And we need more data in order to return the bytestring.
            else:
                wanted = len(b) - offset - readcount - size

        # tags, we should probably move semantic tag handling into the caller.
        if tagvalue == SEMANTIC_TAG_FINITE_SET:
            if offset + readcount >= len(b):
                return False, None, -1, SPECIAL_NONE

            complete, size, readcount2, special = decodeitem(
                b, offset + readcount
            )

            if not complete:
                return False, None, readcount2, SPECIAL_NONE

            if special != SPECIAL_START_ARRAY:
                raise CBORDecodeError(
                    'expected array after finite set ' 'semantic tag'
                )

            return True, size, readcount + readcount2 + 1, SPECIAL_START_SET

        else:
            raise CBORDecodeError('semantic tag %d not allowed' % tagvalue)

        else:
            raise CBORDecodeError('special type %d not allowed' % subtype)
    else:
        assert False


def decodeuint(subtype, b, offset=0, allowindefinite=False):
    """Decode an unsigned integer.

    ``subtype`` is the lower 5 bits from the initial byte CBOR item
    "header." ``b`` is a buffer containing bytes. ``offset`` points to

        if allowindefinite:
            return True, None, 0
        else:
            raise CBORDecodeError('indefinite length uint not allowed here')
    elif subtype >= 28:
        raise CBORDecodeError(
            'unsupported subtype on integer type: %d' % subtype
        )

    if subtype == 24:
        s = STRUCT_BIG_UBYTE
    elif subtype == 25:
        s = STRUCT_BIG_USHORT

    if len(b) - offset >= s.size:
        return True, s.unpack_from(b, offset)[0], s.size
    else:
        return False, None, len(b) - offset - s.size


class bytestringchunk(bytes):
    """Represents a chunk/segment in an indefinite length bytestring.

    This behaves like a ``bytes`` but in addition has the ``isfirst``
    and ``islast`` attributes indicating whether this chunk is the first

        self = bytes.__new__(cls, v)
        self.isfirst = first
        self.islast = last

        return self


class sansiodecoder(object):
    """A CBOR decoder that doesn't perform its own I/O.

    To use, construct an instance and feed it segments containing

                # A normal value.
                if special == SPECIAL_NONE:
                    self._decodedvalues.append(value)

                elif special == SPECIAL_START_ARRAY:
                    self._collectionstack.append(
                        {'remaining': value, 'v': [],}
                    )
                    self._state = self._STATE_WANT_ARRAY_VALUE

                elif special == SPECIAL_START_MAP:
                    self._collectionstack.append(
                        {'remaining': value, 'v': {},}
                    )
                    self._state = self._STATE_WANT_MAP_KEY

                elif special == SPECIAL_START_SET:
                    self._collectionstack.append(
                        {'remaining': value, 'v': set(),}
                    )
                    self._state = self._STATE_WANT_SET_VALUE

                elif special == SPECIAL_START_INDEFINITE_BYTESTRING:
                    self._state = self._STATE_WANT_BYTESTRING_CHUNK_FIRST

                else:
                    raise CBORDecodeError(
                        'unhandled special state: %d' % special
                    )

            # This value becomes an element of the current array.
            elif self._state == self._STATE_WANT_ARRAY_VALUE:
                # Simple values get appended.
                if special == SPECIAL_NONE:

                    newvalue = []

                    lastc['v'].append(newvalue)
                    lastc['remaining'] -= 1

                    self._collectionstack.append(
                        {'remaining': value, 'v': newvalue,}
                    )

                    # self._state doesn't need changed.

                # A map nested within an array.
                elif special == SPECIAL_START_MAP:

                    newvalue = {}

                    lastc['v'].append(newvalue)
                    lastc['remaining'] -= 1

                    self._collectionstack.append(
                        {'remaining': value, 'v': newvalue}
                    )

                    self._state = self._STATE_WANT_MAP_KEY

                elif special == SPECIAL_START_SET:
                    lastc = self._collectionstack[-1]
                    newvalue = set()

                    lastc['v'].append(newvalue)
                    lastc['remaining'] -= 1

                    self._collectionstack.append(
                        {'remaining': value, 'v': newvalue,}
                    )

                    self._state = self._STATE_WANT_SET_VALUE

                elif special == SPECIAL_START_INDEFINITE_BYTESTRING:
                    raise CBORDecodeError(
                        'indefinite length bytestrings '
                        'not allowed as array values'
                    )

                else:
                    raise CBORDecodeError(
                        'unhandled special item when '
                        'expecting array value: %d' % special
                    )

            # This value becomes the key of the current map instance.
            elif self._state == self._STATE_WANT_MAP_KEY:
                if special == SPECIAL_NONE:
                    self._currentmapkey = value
                    self._state = self._STATE_WANT_MAP_VALUE

                elif special == SPECIAL_START_INDEFINITE_BYTESTRING:
                    raise CBORDecodeError(
                        'indefinite length bytestrings '
                        'not allowed as map keys'
                    )

                elif special in (
                    SPECIAL_START_ARRAY,
                    SPECIAL_START_MAP,
                    SPECIAL_START_SET,
                ):
                    raise CBORDecodeError(
                        'collections not supported as map ' 'keys'
                    )

                # We do not allow special values to be used as map keys.
                else:
                    raise CBORDecodeError(
                        'unhandled special item when '
                        'expecting map key: %d' % special
                    )

            # This value becomes the value of the current map key.
            elif self._state == self._STATE_WANT_MAP_VALUE:
                # Simple values simply get inserted into the map.
                if special == SPECIAL_NONE:

                    newvalue = []

                    lastc['v'][self._currentmapkey] = newvalue
                    lastc['remaining'] -= 1

                    self._collectionstack.append(
                        {'remaining': value, 'v': newvalue,}
                    )

                    self._state = self._STATE_WANT_ARRAY_VALUE

                # A new map is used as the map value.
                elif special == SPECIAL_START_MAP:

                    newvalue = {}

                    lastc['v'][self._currentmapkey] = newvalue
                    lastc['remaining'] -= 1

                    self._collectionstack.append(
                        {'remaining': value, 'v': newvalue,}
                    )

                    self._state = self._STATE_WANT_MAP_KEY

                # A new set is used as the map value.
                elif special == SPECIAL_START_SET:

                    newvalue = set()

                    lastc['v'][self._currentmapkey] = newvalue
                    lastc['remaining'] -= 1

                    self._collectionstack.append(
                        {'remaining': value, 'v': newvalue,}
                    )

                    self._state = self._STATE_WANT_SET_VALUE

                elif special == SPECIAL_START_INDEFINITE_BYTESTRING:
                    raise CBORDecodeError(
                        'indefinite length bytestrings not '
                        'allowed as map values'
                    )

                else:
                    raise CBORDecodeError(
                        'unhandled special item when '
                        'expecting map value: %d' % special
                    )

                self._currentmapkey = None

            # This value is added to the current set.
            elif self._state == self._STATE_WANT_SET_VALUE:

                    lastc = self._collectionstack[-1]
                    lastc['v'].add(value)
                    lastc['remaining'] -= 1

                elif special == SPECIAL_START_INDEFINITE_BYTESTRING:
                    raise CBORDecodeError(
                        'indefinite length bytestrings not '
                        'allowed as set values'
                    )

                elif special in (
                    SPECIAL_START_ARRAY,
                    SPECIAL_START_MAP,
                    SPECIAL_START_SET,
                ):
                    raise CBORDecodeError(
                        'collections not allowed as set ' 'values'
                    )

                # We don't allow non-trivial types to exist as set values.
                else:
                    raise CBORDecodeError(
                        'unhandled special item when '
                        'expecting set value: %d' % special
                    )

            # This value represents the first chunk in an indefinite length
            # bytestring.
            elif self._state == self._STATE_WANT_BYTESTRING_CHUNK_FIRST:
                # We received a full chunk.
                if special == SPECIAL_NONE:
                    self._decodedvalues.append(
                        bytestringchunk(value, first=True)
                    )

                    self._state = self._STATE_WANT_BYTESTRING_CHUNK_SUBSEQUENT

                # The end of stream marker. This means it is an empty
                # indefinite length bytestring.
                elif special == SPECIAL_INDEFINITE_BREAK:
                    # We /could/ convert this to a b''. But we want to preserve
                    # the nature of the underlying data so consumers expecting
                    # an indefinite length bytestring get one.
                    self._decodedvalues.append(
                        bytestringchunk(b'', first=True, last=True)
                    )

                    # Since indefinite length bytestrings can't be used in
                    # collections, we must be at the root level.
                    assert not self._collectionstack
                    self._state = self._STATE_NONE

                else:
                    raise CBORDecodeError(
                        'unexpected special value when '
                        'expecting bytestring chunk: %d' % special
                    )

            # This value represents the non-initial chunk in an indefinite
            # length bytestring.
            elif self._state == self._STATE_WANT_BYTESTRING_CHUNK_SUBSEQUENT:
                # We received a full chunk.

                    # collections, we must be at the root level.
                    assert not self._collectionstack
                    self._state = self._STATE_NONE

                else:
                    raise CBORDecodeError(
                        'unexpected special value when '
                        'expecting bytestring chunk: %d' % special
                    )

            else:
                raise CBORDecodeError(
                    'unhandled decoder state: %d' % self._state
                )

            # We could have just added the final value in a collection. End
            # all complete collections at the top of the stack.
            while True:
                # Bail if we're not waiting on a new collection item.
                if self._state not in (
                    self._STATE_WANT_ARRAY_VALUE,
                    self._STATE_WANT_MAP_KEY,
                    self._STATE_WANT_SET_VALUE,
                ):
                    break

                # Or we are expecting more items for this collection.
                lastc = self._collectionstack[-1]

        l = list(self._decodedvalues)
        self._decodedvalues = []
        return l


class bufferingdecoder(object):
    """A CBOR decoder that buffers undecoded input.

    This is a glorified wrapper around ``sansiodecoder`` that adds a buffering
    layer. All input that isn't consumed by ``sansiodecoder`` will be buffered
    and concatenated with any new input that arrives later.

    TODO consider adding limits as to the maximum amount of data that can
    be buffered.
    """

    def __init__(self):
        self._decoder = sansiodecoder()
        self._chunks = []
        self._wanted = 0

        return available, readcount - oldlen, wanted

    def getavailable(self):
        return self._decoder.getavailable()


def decodeall(b):
    """Decode all CBOR items present in an iterable of bytes.

    In addition to regular decode errors, raises CBORDecodeError if the
    entirety of the passed buffer does not fully decode to complete CBOR