qcborvalue.cpp

Go to the documentation of this file.

// Copyright (C) 2022 Intel Corporation.
// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
 
#include "qcborvalue.h"
#include "qcborvalue_p.h"
#include "qdatastream.h"
#include "qcborarray.h"
#include "qcbormap.h"
 
#if QT_CONFIG(cborstreamreader)
#include "qcborstreamreader.h"
#endif
 
#if QT_CONFIG(cborstreamwriter)
#include "qcborstreamwriter.h"
#endif
 
#include <qendian.h>
#include <qlocale.h>
#include <qdatetime.h>
#include <qtimezone.h>
#include <private/qnumeric_p.h>
#include <private/qsimd_p.h>
 
#include <new>
 
QT_BEGIN_NAMESPACE
 
// Worst case memory allocation for a corrupt stream: 256 MB for 32-bit, 1 GB for 64-bit
static constexpr quint64 MaxAcceptableMemoryUse = (sizeof(void*) == 4 ? 256 : 1024) * 1024 * 1024;
 
// Internal limits to ensure we don't blow up the memory when parsing a corrupt
// (possibly crafted to exploit) CBOR stream. The recursion impacts both the
// maps/arrays we'll open when parsing and the thread's stack, as the parser is
// itself recursive. If someone really needs more than 1024 layers of nesting,
// they probably have a weird use-case for which custom parsing and
// serialisation code would make sense. The limit on element count is the
// preallocated limit: if the stream does actually have more elements, we will
// grow the container.
Q_DECL_UNUSED static constexpr int MaximumRecursionDepth = 1024;
Q_DECL_UNUSED static constexpr quint64 MaximumPreallocatedElementCount =
        MaxAcceptableMemoryUse / MaximumRecursionDepth / sizeof(QtCbor::Element) - 1;
 
using namespace QtCbor;
 
static QCborContainerPrivate *assignContainer(QCborContainerPrivate *&d, QCborContainerPrivate *x)
{
    if (d == x)
        return d;
    if (d)
        d->deref();
    if (x)
        x->ref.ref();
    return d = x;
}
 
static QCborValue::Type convertToExtendedType(QCborContainerPrivate *d)
{
    qint64 tag = d->elements.at(0).value;
    auto &e = d->elements[1];
    const ByteData *b = d->byteData(e);
 
    auto replaceByteData = [&](const char *buf, qsizetype len, Element::ValueFlags f) {
        d->data.clear();
        d->usedData = 0;
        e.flags = Element::HasByteData | f;
        e.value = d->addByteData(buf, len);
    };
 
    switch (tag) {
    case qint64(QCborKnownTags::DateTimeString):
    case qint64(QCborKnownTags::UnixTime_t): {
        QDateTime dt;
        if (tag == qint64(QCborKnownTags::DateTimeString) && b &&
            e.type == QCborValue::String && (e.flags & Element::StringIsUtf16) == 0) {
            // The data is supposed to be US-ASCII. If it isn't (contains UTF-8),
            // QDateTime::fromString will fail anyway.
            dt = QDateTime::fromString(b->asLatin1(), Qt::ISODateWithMs);
        } else if (tag == qint64(QCborKnownTags::UnixTime_t)) {
            qint64 msecs;
            bool ok = false;
            if (e.type == QCborValue::Integer) {
#if QT_POINTER_SIZE == 8
                // we don't have a fast 64-bit qMulOverflow implementation on
                // 32-bit architectures.
                ok = !qMulOverflow(e.value, qint64(1000), &msecs);
#else
                static const qint64 Limit = std::numeric_limits<qint64>::max() / 1000;
                ok = (e.value > -Limit && e.value < Limit);
                if (ok)
                    msecs = e.value * 1000;
#endif
            } else if (e.type == QCborValue::Double) {
                ok = convertDoubleTo(round(e.fpvalue() * 1000), &msecs);
            }
            if (ok)
                dt = QDateTime::fromMSecsSinceEpoch(msecs, QTimeZone::UTC);
        }
        if (dt.isValid()) {
            QByteArray text = dt.toString(Qt::ISODateWithMs).toLatin1();
            if (!text.isEmpty()) {
                replaceByteData(text, text.size(), Element::StringIsAscii);
                e.type = QCborValue::String;
                d->elements[0].value = qint64(QCborKnownTags::DateTimeString);
                return QCborValue::DateTime;
            }
        }
        break;
    }
 
#ifndef QT_BOOTSTRAPPED
    case qint64(QCborKnownTags::Url):
        if (e.type == QCborValue::String) {
            if (b) {
                // normalize to a short (decoded) form, so as to save space
                QUrl url(e.flags & Element::StringIsUtf16 ?
                             b->asQStringRaw() :
                             b->toUtf8String(), QUrl::StrictMode);
                if (url.isValid()) {
                    QByteArray encoded = url.toString(QUrl::DecodeReserved).toUtf8();
                    replaceByteData(encoded, encoded.size(), {});
                }
            }
            return QCborValue::Url;
        }
        break;
#endif // QT_BOOTSTRAPPED
 
#if QT_CONFIG(regularexpression)
    case quint64(QCborKnownTags::RegularExpression):
        if (e.type == QCborValue::String) {
            // no normalization is necessary
            return QCborValue::RegularExpression;
        }
        break;
#endif // QT_CONFIG(regularexpression)
 
    case qint64(QCborKnownTags::Uuid):
        if (e.type == QCborValue::ByteArray) {
            // force the size to 16
            char buf[sizeof(QUuid)] = {};
            if (b)
                memcpy(buf, b->byte(), qMin(sizeof(buf), size_t(b->len)));
            replaceByteData(buf, sizeof(buf), {});
 
            return QCborValue::Uuid;
        }
        break;
    }
 
    // no enriching happened
    return QCborValue::Tag;
}
 
#if QT_CONFIG(cborstreamwriter)
static void writeDoubleToCbor(QCborStreamWriter &writer, double d, QCborValue::EncodingOptions opt)
{
    if (qt_is_nan(d)) {
        if (opt & QCborValue::UseFloat) {
#ifndef QT_BOOTSTRAPPED
            if ((opt & QCborValue::UseFloat16) == QCborValue::UseFloat16)
                return writer.append(std::numeric_limits<qfloat16>::quiet_NaN());
#endif
            return writer.append(std::numeric_limits<float>::quiet_NaN());
        }
        return writer.append(qt_qnan());
    }
 
    if (qt_is_inf(d)) {
        d = d > 0 ? qt_inf() : -qt_inf();
    } else if (opt & QCborValue::UseIntegers) {
        quint64 i;
        if (convertDoubleTo(d, &i)) {
            if (d < 0)
                return writer.append(QCborNegativeInteger(i));
            return writer.append(i);
        }
    }
 
    if (opt & QCborValue::UseFloat) {
        float f = float(d);
        if (f == d) {
            // no data loss, we could use float
#ifndef QT_BOOTSTRAPPED
            if ((opt & QCborValue::UseFloat16) == QCborValue::UseFloat16) {
                qfloat16 f16 = qfloat16(f);
                if (f16 == f)
                    return writer.append(f16);
            }
#endif
 
            return writer.append(f);
        }
    }
 
    writer.append(d);
}
#endif // QT_CONFIG(cborstreamwriter)
 
static inline int typeOrder(QCborValue::Type e1, QCborValue::Type  e2)
{
    auto comparable = [](QCborValue::Type type) {
        if (type >= 0x10000)        // see QCborValue::isTag_helper()
            return QCborValue::Tag;
        return type;
    };
    return comparable(e1) - comparable(e2);
}
 
QCborContainerPrivate::~QCborContainerPrivate()
{
    // delete our elements
    for (Element &e : elements) {
        if (e.flags & Element::IsContainer)
            e.container->deref();
    }
}
 
void QCborContainerPrivate::compact()
{
    if (usedData > data.size() / 2)
        return;
 
    // 50% savings if we recreate the byte data
    QByteArray newData;
    QByteArray::size_type newUsedData = 0;
    // Compact only elements that have byte data.
    // Nested containers will be compacted when their data changes.
    for (auto &e : elements) {
        if (e.flags & Element::HasByteData) {
            if (const ByteData *b = byteData(e))
                e.value = addByteDataImpl(newData, newUsedData, b->byte(), b->len);
        }
    }
    data = newData;
    usedData = newUsedData;
}
 
QCborContainerPrivate *QCborContainerPrivate::clone(QCborContainerPrivate *d, qsizetype reserved)
{
    if (!d) {
        d = new QCborContainerPrivate;
    } else {
        // in case QList::reserve throws
        QExplicitlySharedDataPointer u(new QCborContainerPrivate(*d));
        if (reserved >= 0) {
            u->elements.reserve(reserved);
            u->compact();
        }
 
        d = u.take();
        d->ref.storeRelaxed(0);
 
        for (auto &e : std::as_const(d->elements)) {
            if (e.flags & Element::IsContainer)
                e.container->ref.ref();
        }
    }
    return d;
}
 
QCborContainerPrivate *QCborContainerPrivate::detach(QCborContainerPrivate *d, qsizetype reserved)
{
    if (!d || d->ref.loadRelaxed() != 1)
        return clone(d, reserved);
    return d;
}
 
QCborContainerPrivate *QCborContainerPrivate::grow(QCborContainerPrivate *d, qsizetype index)
{
    Q_ASSERT(index >= 0);
    d = detach(d, index + 1);
    Q_ASSERT(d);
    qsizetype j = d->elements.size();
    while (j++ < index)
        d->append(Undefined());
    return d;
}
 
// Copies or moves \a value into element at position \a e. If \a disp is
// CopyContainer, then this function increases the reference count of the
// container, but otherwise leaves it unmodified. If \a disp is MoveContainer,
// then it transfers ownership (move semantics) and the caller must set
// value.container back to nullptr.
void QCborContainerPrivate::replaceAt_complex(Element &e, const QCborValue &value, ContainerDisposition disp)
{
    if (value.n < 0) {
        // This QCborValue is an array, map, or tagged value (container points
        // to itself).
 
        // detect self-assignment
        if (Q_UNLIKELY(this == value.container)) {
            Q_ASSERT(ref.loadRelaxed() >= 2);
            if (disp == MoveContainer)
                ref.deref();    // not deref() because it can't drop to 0
            QCborContainerPrivate *d = QCborContainerPrivate::clone(this);
            d->elements.detach();
            d->ref.storeRelaxed(1);
            e.container = d;
        } else {
            e.container = value.container;
            if (disp == CopyContainer)
                e.container->ref.ref();
        }
 
        e.type = value.type();
        e.flags = Element::IsContainer;
    } else {
        // String data, copy contents
        e = value.container->elements.at(value.n);
 
        // Copy string data, if any
        if (const ByteData *b = value.container->byteData(value.n)) {
            const auto flags = e.flags;
            // The element e has an invalid e.value, because it is copied from
            // value. It means that calling compact() will trigger an assertion
            // or just silently corrupt the data.
            // Temporarily unset the Element::HasByteData flag in order to skip
            // the element e in the call to compact().
            e.flags = e.flags & ~Element::HasByteData;
            if (this == value.container) {
                const QByteArray valueData = b->toByteArray();
                compact();
                e.value = addByteData(valueData, valueData.size());
            } else {
                compact();
                e.value = addByteData(b->byte(), b->len);
            }
            // restore the flags
            e.flags = flags;
        }
 
        if (disp == MoveContainer)
            value.container->deref();
    }
}
 
// in qstring.cpp
void qt_to_latin1_unchecked(uchar *dst, const char16_t *uc, qsizetype len);
 
Q_NEVER_INLINE void QCborContainerPrivate::appendAsciiString(QStringView s)
{
    qsizetype len = s.size();
    QtCbor::Element e;
    e.value = addByteData(nullptr, len);
    e.type = QCborValue::String;
    e.flags = Element::HasByteData | Element::StringIsAscii;
    elements.append(e);
 
    char *ptr = data.data() + e.value + sizeof(ByteData);
    uchar *l = reinterpret_cast<uchar *>(ptr);
    qt_to_latin1_unchecked(l, s.utf16(), len);
}
 
void QCborContainerPrivate::appendNonAsciiString(QStringView s)
{
    appendByteData(reinterpret_cast<const char *>(s.utf16()), s.size() * 2,
                   QCborValue::String, QtCbor::Element::StringIsUtf16);
}
 
QCborValue QCborContainerPrivate::extractAt_complex(Element e)
{
    // create a new container for the returned value, containing the byte data
    // from this element, if it's worth it
    Q_ASSERT(e.flags & Element::HasByteData);
    auto b = byteData(e);
    auto container = new QCborContainerPrivate;
 
    if (b->len + qsizetype(sizeof(*b)) < data.size() / 4) {
        // make a shallow copy of the byte data
        container->appendByteData(b->byte(), b->len, e.type, e.flags);
        usedData -= b->len + qsizetype(sizeof(*b));
        compact();
    } else {
        // just share with the original byte data
        container->data = data;
        container->elements.reserve(1);
        container->elements.append(e);
    }
 
    return makeValue(e.type, 0, container);
}
 
// Similar to QStringIterator::next() but returns malformed surrogate pair
// itself when one is detected, and returns the length in UTF-8.
static auto nextUtf32Character(const char16_t *&ptr, const char16_t *end) noexcept
{
    Q_ASSERT(ptr != end);
    struct R {
        char32_t c;
        qsizetype len = 1;  // in UTF-8 code units (bytes)
    } r = { *ptr++ };
 
    if (r.c < 0x0800) {
        if (r.c >= 0x0080)
            ++r.len;
    } else if (!QChar::isHighSurrogate(r.c) || ptr == end) {
        r.len += 2;
    } else {
        r.len += 3;
        r.c = QChar::surrogateToUcs4(r.c, *ptr++);
    }
 
    return r;
}
 
static qsizetype stringLengthInUtf8(const char16_t *ptr, const char16_t *end) noexcept
{
    qsizetype len = 0;
    while (ptr < end)
        len += nextUtf32Character(ptr, end).len;
    return len;
}
 
static int compareStringsInUtf8(QStringView lhs, QStringView rhs, Comparison mode) noexcept
{
    if (mode == Comparison::ForEquality)
        return lhs == rhs ? 0 : 1;
 
    // The UTF-16 length is *usually* comparable, but not always. There are
    // pathological cases where they can be wrong, so we need to compare as if
    // we were doing it in UTF-8. That includes the case of UTF-16 surrogate
    // pairs, because qstring.cpp sorts them before U+E000-U+FFFF.
    int diff = 0;
    qsizetype len1 = 0;
    qsizetype len2 = 0;
    const char16_t *src1 = lhs.utf16();
    const char16_t *src2 = rhs.utf16();
    const char16_t *end1 = src1 + lhs.size();
    const char16_t *end2 = src2 + rhs.size();
 
    // first, scan until we find a difference (if any)
    do {
        auto r1 = nextUtf32Character(src1, end1);
        auto r2 = nextUtf32Character(src2, end2);
        len1 += r1.len;
        len2 += r2.len;
        diff = int(r1.c) - int(r2.c);       // no underflow due to limited range
    } while (src1 < end1 && src2 < end2 && diff == 0);
 
    // compute the full length past this first difference
    len1 += stringLengthInUtf8(src1, end1);
    len2 += stringLengthInUtf8(src2, end2);
    if (len1 == len2)
        return diff;
    return len1 < len2 ? -1 : 1;
}
 
static int compareStringsInUtf8(QUtf8StringView lhs, QStringView rhs, Comparison mode) noexcept
{
    // CBOR requires that the shortest of the two strings be sorted first, so
    // we have to calculate the UTF-8 length of the UTF-16 string while
    // comparing. Unlike the UTF-32 comparison above, we convert the UTF-16
    // string to UTF-8 so we only need to decode one string.
 
    const qsizetype len1 = lhs.size();
    const auto src1 = reinterpret_cast<const uchar *>(lhs.data());
    const char16_t *src2 = rhs.utf16();
    const char16_t *const end2 = src2 + rhs.size();
 
    // Compare the two strings until we find a difference.
    int diff = 0;
    qptrdiff idx1 = 0;
    qsizetype len2 = 0;
    do {
        uchar utf8[4];      // longest possible Unicode character in UTF-8
        uchar *ptr = utf8;
        char16_t uc = *src2++;
        int r = QUtf8Functions::toUtf8<QUtf8BaseTraits>(uc, ptr, src2, end2);
        Q_UNUSED(r);    // ignore failure to encode proper UTF-16 surrogates
 
        qptrdiff n = ptr - utf8;
        len2 += n;
        if (len1 - idx1 < n)
            return -1;      // lhs is definitely shorter
        diff = memcmp(src1 + idx1, utf8, n);
        idx1 += n;
    } while (diff == 0 && idx1 < len1 && src2 < end2);
 
    if (mode == Comparison::ForEquality && diff)
        return diff;
    if ((idx1 == len1) != (src2 == end2)) {
        // One of the strings ended earlier than the other
        return idx1 == len1 ? -1 : 1;
    }
 
    // We found a difference and neither string ended, so continue calculating
    // the UTF-8 length of rhs.
    len2 += stringLengthInUtf8(src2, end2);
 
    if (len1 != len2)
        return len1 < len2 ? -1 : 1;
    return diff;
}
 
static int compareStringsInUtf8(QStringView lhs, QUtf8StringView rhs, Comparison mode) noexcept
{
    return -compareStringsInUtf8(rhs, lhs, mode);
}
 
QT_WARNING_DISABLE_MSVC(4146)   // unary minus operator applied to unsigned type, result still unsigned
static int compareContainer(const QCborContainerPrivate *c1, const QCborContainerPrivate *c2,
                            Comparison mode) noexcept;
static int compareElementNoData(const Element &e1, const Element &e2) noexcept
{
    Q_ASSERT(e1.type == e2.type);
 
    if (e1.type == QCborValue::Integer) {
        // CBOR sorting order is 0, 1, 2, ..., INT64_MAX, -1, -2, -3, ... INT64_MIN
        // So we transform:
        //  0           ->      0
        //  1           ->      1
        //  INT64_MAX   ->      INT64_MAX
        //  -1          ->      INT64_MAX + 1 = INT64_MAX - (-1)
        //  -2          ->      INT64_MAX + 2 = INT64_MAX - (-2)
        //  INT64_MIN   ->      UINT64_MAX = INT64_MAX - INT64_MIN
        // Note how the unsigned arithmetic is well defined in C++ (it's
        // always performed modulo 2^64).
        auto makeSortable = [](qint64 v) {
            quint64 u = quint64(v);
            if (v < 0)
                return quint64(std::numeric_limits<qint64>::max()) + (-u);
            return u;
        };
        quint64 u1 = makeSortable(e1.value);
        quint64 u2 = makeSortable(e2.value);
        if (u1 < u2)
            return -1;
        if (u1 > u2)
            return 1;
    }
 
    if (e1.type == QCborValue::Tag || e1.type == QCborValue::Double) {
        // Perform unsigned comparisons for the tag value and floating point
        quint64 u1 = quint64(e1.value);
        quint64 u2 = quint64(e2.value);
        if (u1 != u2)
            return u1 < u2 ? -1 : 1;
    }
 
    // Any other type is equal at this point:
    // - simple types carry no value
    // - empty strings, arrays and maps
    return 0;
}
 
static int compareElementRecursive(const QCborContainerPrivate *c1, const Element &e1,
                                   const QCborContainerPrivate *c2, const Element &e2,
                                   Comparison mode) noexcept
{
    int cmp = typeOrder(e1.type, e2.type);
    if (cmp != 0)
        return cmp;
 
    if ((e1.flags & Element::IsContainer) || (e2.flags & Element::IsContainer))
        return compareContainer(e1.flags & Element::IsContainer ? e1.container : nullptr,
                                e2.flags & Element::IsContainer ? e2.container : nullptr, mode);
 
    // string data?
    const ByteData *b1 = c1 ? c1->byteData(e1) : nullptr;
    const ByteData *b2 = c2 ? c2->byteData(e2) : nullptr;
    if (b1 || b2) {
        auto len1 = b1 ? b1->len : 0;
        auto len2 = b2 ? b2->len : 0;
        if (len1 == 0 || len2 == 0)
            return len1 < len2 ? -1 : len1 == len2 ? 0 : 1;
 
        // we definitely have data from this point forward
        Q_ASSERT(b1);
        Q_ASSERT(b2);
 
        // Officially with CBOR, we sort first the string with the shortest
        // UTF-8 length. Since US-ASCII is just a subset of UTF-8, its length
        // is the UTF-8 length. But the UTF-16 length may not be directly
        // comparable.
        if ((e1.flags & Element::StringIsUtf16) && (e2.flags & Element::StringIsUtf16))
            return compareStringsInUtf8(b1->asStringView(), b2->asStringView(), mode);
 
        if (!(e1.flags & Element::StringIsUtf16) && !(e2.flags & Element::StringIsUtf16)) {
            // Neither is UTF-16, so lengths are comparable too
            // (this case includes byte arrays too)
            if (len1 == len2) {
                if (mode == Comparison::ForEquality) {
                    // GCC optimizes this to __memcmpeq(); Clang to bcmp()
                    return memcmp(b1->byte(), b2->byte(), size_t(len1)) == 0 ? 0 : 1;
                }
                return memcmp(b1->byte(), b2->byte(), size_t(len1));
            }
            return len1 < len2 ? -1 : 1;
        }
 
        // Only one is UTF-16
        if (e1.flags & Element::StringIsUtf16)
            return compareStringsInUtf8(b1->asStringView(), b2->asUtf8StringView(), mode);
        else
            return compareStringsInUtf8(b1->asUtf8StringView(), b2->asStringView(), mode);
    }
 
    return compareElementNoData(e1, e2);
}
 
static int compareContainer(const QCborContainerPrivate *c1, const QCborContainerPrivate *c2,
                            Comparison mode) noexcept
{
    auto len1 = c1 ? c1->elements.size() : 0;
    auto len2 = c2 ? c2->elements.size() : 0;
    if (len1 != len2) {
        // sort the shorter container first
        return len1 < len2 ? -1 : 1;
    }
 
    for (qsizetype i = 0; i < len1; ++i) {
        const Element &e1 = c1->elements.at(i);
        const Element &e2 = c2->elements.at(i);
        int cmp = compareElementRecursive(c1, e1, c2, e2, mode);
        if (cmp)
            return cmp;
    }
 
    return 0;
}
 
inline int QCborContainerPrivate::compareElement_helper(const QCborContainerPrivate *c1, Element e1,
                                                        const QCborContainerPrivate *c2, Element e2,
                                                        Comparison mode) noexcept
{
    return compareElementRecursive(c1, e1, c2, e2, mode);
}
 
bool comparesEqual(const QCborValue &lhs,
                   const QCborValue &rhs) noexcept
{
    Element e1 = QCborContainerPrivate::elementFromValue(lhs);
    Element e2 = QCborContainerPrivate::elementFromValue(rhs);
    return compareElementRecursive(lhs.container, e1, rhs.container, e2,
                                   Comparison::ForEquality) == 0;
}
 
int QCborValue::compare(const QCborValue &other) const
{
    Element e1 = QCborContainerPrivate::elementFromValue(*this);
    Element e2 = QCborContainerPrivate::elementFromValue(other);
    return compareElementRecursive(container, e1, other.container, e2, Comparison::ForOrdering);
}
 
bool comparesEqual(const QCborArray &lhs, const QCborArray &rhs) noexcept
{
    return compareContainer(lhs.d.constData(), rhs.d.constData(), Comparison::ForEquality) == 0;
}
 
int QCborArray::compare(const QCborArray &other) const noexcept
{
    return compareContainer(d.data(), other.d.data(), Comparison::ForOrdering);
}
 
bool QCborArray::comparesEqual_helper(const QCborArray &lhs, const QCborValue &rhs) noexcept
{
    if (typeOrder(QCborValue::Array, rhs.type()))
        return false;
    return compareContainer(lhs.d.constData(), rhs.container, Comparison::ForEquality) == 0;
}
 
Qt::strong_ordering
QCborArray::compareThreeWay_helper(const QCborArray &lhs, const QCborValue &rhs) noexcept
{
    int c = typeOrder(QCborValue::Array, rhs.type());
    if (c == 0)
        c = compareContainer(lhs.d.constData(), rhs.container, Comparison::ForOrdering);
    return Qt::compareThreeWay(c, 0);
}
 
bool comparesEqual(const QCborMap &lhs, const QCborMap &rhs) noexcept
{
    return compareContainer(lhs.d.constData(), rhs.d.constData(), Comparison::ForEquality) == 0;
}
 
int QCborMap::compare(const QCborMap &other) const noexcept
{
    return compareContainer(d.data(), other.d.data(), Comparison::ForOrdering);
}
 
bool QCborMap::comparesEqual_helper(const QCborMap &lhs, const QCborValue &rhs) noexcept
{
    if (typeOrder(QCborValue::Map, rhs.type()))
        return false;
    return compareContainer(lhs.d.constData(), rhs.container, Comparison::ForEquality) == 0;
}
 
Qt::strong_ordering
QCborMap::compareThreeWay_helper(const QCborMap &lhs, const QCborValue &rhs) noexcept
{
    int c = typeOrder(QCborValue::Map, rhs.type());
    if (c == 0)
        c = compareContainer(lhs.d.constData(), rhs.container, Comparison::ForOrdering);
    return Qt::compareThreeWay(c, 0);
}
 
#if QT_CONFIG(cborstreamwriter)
static void encodeToCbor(QCborStreamWriter &writer, const QCborContainerPrivate *d, qsizetype idx,
                         QCborValue::EncodingOptions opt)
{
    if (idx == -QCborValue::Array || idx == -QCborValue::Map) {
        bool isArray = (idx == -QCborValue::Array);
        qsizetype len = d ? d->elements.size() : 0;
        if (isArray)
            writer.startArray(quint64(len));
        else
            writer.startMap(quint64(len) / 2);
 
        for (idx = 0; idx < len; ++idx)
            encodeToCbor(writer, d, idx, opt);
 
        if (isArray)
            writer.endArray();
        else
            writer.endMap();
    } else if (idx < 0) {
        Q_ASSERT_X(d != nullptr, "QCborValue", "Unexpected null container");
        if (d->elements.size() != 2) {
            // invalid state!
            qWarning("QCborValue: invalid tag state; are you encoding something that was improperly decoded?");
            return;
        }
 
        // write the tag and the tagged element
        writer.append(QCborTag(d->elements.at(0).value));
        encodeToCbor(writer, d, 1, opt);
    } else {
        Q_ASSERT_X(d != nullptr, "QCborValue", "Unexpected null container");
        // just one element
        auto e = d->elements.at(idx);
        const ByteData *b = d->byteData(idx);
        switch (e.type) {
        case QCborValue::Integer:
            return writer.append(qint64(e.value));
 
        case QCborValue::ByteArray:
            if (b)
                return writer.appendByteString(b->byte(), b->len);
            return writer.appendByteString("", 0);
 
        case QCborValue::String:
            if (b) {
                if (e.flags & Element::StringIsUtf16)
                    return writer.append(b->asStringView());
                return writer.appendTextString(b->byte(), b->len);
            }
            return writer.append(QLatin1StringView());
 
        case QCborValue::Array:
        case QCborValue::Map:
        case QCborValue::Tag:
            // recurse
            return encodeToCbor(writer,
                                e.flags & Element::IsContainer ? e.container : nullptr,
                                -qsizetype(e.type), opt);
 
        case QCborValue::SimpleType:
        case QCborValue::False:
        case QCborValue::True:
        case QCborValue::Null:
        case QCborValue::Undefined:
            break;
 
        case QCborValue::Double:
            return writeDoubleToCbor(writer, e.fpvalue(), opt);
 
        case QCborValue::Invalid:
            return;
 
        case QCborValue::DateTime:
        case QCborValue::Url:
        case QCborValue::RegularExpression:
        case QCborValue::Uuid:
            // recurse as tag
            return encodeToCbor(writer, e.container, -QCborValue::Tag, opt);
        }
 
        // maybe it's a simple type
        int simpleType = e.type - QCborValue::SimpleType;
        if (unsigned(simpleType) < 0x100)
            return writer.append(QCborSimpleType(simpleType));
 
        // if we got here, we've got an unknown type
        qWarning("QCborValue: found unknown type 0x%x", e.type);
    }
}
#endif // QT_CONFIG(cborstreamwriter)
 
#if QT_CONFIG(cborstreamreader)
static inline double integerOutOfRange(const QCborStreamReader &reader)
{
    Q_ASSERT(reader.isInteger());
    if (reader.isUnsignedInteger()) {
        quint64 v = reader.toUnsignedInteger();
        if (qint64(v) < 0)
            return double(v);
    } else {
        quint64 v = quint64(reader.toNegativeInteger());
        if (qint64(v - 1) < 0)
            return -double(v);
    }
 
    // result is in range
    return 0;
}
 
static Element decodeBasicValueFromCbor(QCborStreamReader &reader)
{
    Element e = {};
 
    switch (reader.type()) {
    case QCborStreamReader::UnsignedInteger:
    case QCborStreamReader::NegativeInteger:
        if (double d = integerOutOfRange(reader)) {
            e.type = QCborValue::Double;
            qToUnaligned(d, &e.value);
        } else {
            e.type = QCborValue::Integer;
            e.value = reader.toInteger();
        }
        break;
    case QCborStreamReader::SimpleType:
        e.type = QCborValue::Type(quint8(reader.toSimpleType()) + 0x100);
        break;
    case QCborStreamReader::Float16:
        e.type = QCborValue::Double;
        qToUnaligned(double(reader.toFloat16()), &e.value);
        break;
    case QCborStreamReader::Float:
        e.type = QCborValue::Double;
        qToUnaligned(double(reader.toFloat()), &e.value);
        break;
    case QCborStreamReader::Double:
        e.type = QCborValue::Double;
        qToUnaligned(reader.toDouble(), &e.value);
        break;
 
    default:
        Q_UNREACHABLE();
    }
 
    reader.next();
    return e;
}
 
// Clamp allocation to avoid crashing due to corrupt stream. This also
// ensures we never overflow qsizetype. The returned length is doubled for Map
// entries to account for key-value pairs.
static qsizetype clampedContainerLength(const QCborStreamReader &reader)
{
    if (!reader.isLengthKnown())
        return 0;
    int mapShift = reader.isMap() ? 1 : 0;
    quint64 shiftedMaxElements = MaximumPreallocatedElementCount >> mapShift;
    qsizetype len = qsizetype(qMin(reader.length(), shiftedMaxElements));
    return len << mapShift;
}
 
static inline QCborContainerPrivate *createContainerFromCbor(QCborStreamReader &reader, int remainingRecursionDepth)
{
    if (Q_UNLIKELY(remainingRecursionDepth == 0)) {
        QCborContainerPrivate::setErrorInReader(reader, { QCborError::NestingTooDeep });
        return nullptr;
    }
 
    QCborContainerPrivate *d = nullptr;
    {
        // in case QList::reserve throws
        QExplicitlySharedDataPointer u(new QCborContainerPrivate);
        if (qsizetype len = clampedContainerLength(reader))
            u->elements.reserve(len);
        d = u.take();
    }
 
    reader.enterContainer();
    if (reader.lastError() != QCborError::NoError) {
        d->elements.clear();
        return d;
    }
 
    while (reader.hasNext() && reader.lastError() == QCborError::NoError)
        d->decodeValueFromCbor(reader, remainingRecursionDepth - 1);
 
    if (reader.lastError() == QCborError::NoError)
        reader.leaveContainer();
    else
        d->elements.squeeze();
 
    return d;
}
 
static QCborValue taggedValueFromCbor(QCborStreamReader &reader, int remainingRecursionDepth)
{
    if (Q_UNLIKELY(remainingRecursionDepth == 0)) {
        QCborContainerPrivate::setErrorInReader(reader, { QCborError::NestingTooDeep });
        return QCborValue::Invalid;
    }
 
    auto d = new QCborContainerPrivate;
    d->append(reader.toTag());
    reader.next();
 
    if (reader.lastError() == QCborError::NoError) {
        // decode tagged value
        d->decodeValueFromCbor(reader, remainingRecursionDepth - 1);
    }
 
    QCborValue::Type type;
    if (reader.lastError() == QCborError::NoError) {
        // post-process to create our extended types
        type = convertToExtendedType(d);
    } else {
        // decoding error
        type = QCborValue::Invalid;
    }
 
    // note: may return invalid state!
    return QCborContainerPrivate::makeValue(type, -1, d);
}
 
// in qcborstream.cpp
extern void qt_cbor_stream_set_error(QCborStreamReaderPrivate *d, QCborError error);
inline void QCborContainerPrivate::setErrorInReader(QCborStreamReader &reader, QCborError error)
{
    qt_cbor_stream_set_error(reader.d.data(), error);
}
 
extern QCborStreamReader::StringResultCode qt_cbor_append_string_chunk(QCborStreamReader &reader, QByteArray *data);
 
void QCborContainerPrivate::decodeStringFromCbor(QCborStreamReader &reader)
{
    if (reader.lastError() != QCborError::NoError)
        return;
 
    qsizetype rawlen = reader.currentStringChunkSize();
    QByteArray::size_type len = rawlen;
    if (rawlen < 0)
        return;                     // error
    if (len != rawlen) {
        // truncation
        setErrorInReader(reader, { QCborError::DataTooLarge });
        return;
    }
 
    Element e = {};
    e.type = (reader.isByteArray() ? QCborValue::ByteArray : QCborValue::String);
    if (len || !reader.isLengthKnown()) {
        // The use of size_t means none of the operations here can overflow because
        // all inputs are less than half SIZE_MAX.
        constexpr size_t EstimatedOverhead = 16;
        constexpr size_t MaxMemoryIncrement = 16384;
        size_t offset = data.size();
 
        // add space for aligned ByteData (this can't overflow)
        offset += sizeof(QtCbor::ByteData) + alignof(QtCbor::ByteData);
        offset &= ~(alignof(QtCbor::ByteData) - 1);
        if (offset > size_t(QByteArray::max_size())) {
            // overflow
            setErrorInReader(reader, { QCborError::DataTooLarge });
            return;
        }
 
        // and calculate the size we want to have
        size_t newCapacity = offset + len;          // can't overflow
        if (size_t(len) > MaxMemoryIncrement - EstimatedOverhead) {
            // there's a non-zero chance that we won't need this memory at all,
            // so capa how much we allocate
            newCapacity = offset + MaxMemoryIncrement - EstimatedOverhead;
        }
        if (newCapacity > size_t(QByteArray::max_size())) {
            // this may cause an allocation failure
            newCapacity = QByteArray::max_size();
        }
        if (newCapacity > size_t(data.capacity()))
            data.reserve(newCapacity);
        data.resize(offset + sizeof(QtCbor::ByteData));
        e.value = offset;
        e.flags = Element::HasByteData;
    }
 
    // read chunks
    bool isAscii = (e.type == QCborValue::String);
    QCborStreamReader::StringResultCode status = qt_cbor_append_string_chunk(reader, &data);
    while (status == QCborStreamReader::Ok) {
        if (e.type == QCborValue::String && len) {
            // verify UTF-8 string validity
            auto utf8result = QUtf8::isValidUtf8(QByteArrayView(data).last(len));
            if (!utf8result.isValidUtf8) {
                status = QCborStreamReader::Error;
                setErrorInReader(reader, { QCborError::InvalidUtf8String });
                break;
            }
            isAscii = isAscii && utf8result.isValidAscii;
        }
 
        rawlen = reader.currentStringChunkSize();
        len = rawlen;
        if (len == rawlen) {
            status = qt_cbor_append_string_chunk(reader, &data);
        } else {
            // error
            status = QCborStreamReader::Error;
            setErrorInReader(reader, { QCborError::DataTooLarge });
        }
    }
 
    // update size
    if (status == QCborStreamReader::EndOfString && e.flags & Element::HasByteData) {
        Q_ASSERT(data.isDetached());
        const char *ptr = data.constData() + e.value;
        auto b = new (const_cast<char *>(ptr)) ByteData;
        b->len = data.size() - e.value - int(sizeof(*b));
        usedData += b->len;
 
        if (isAscii) {
            // set the flag if it is US-ASCII only (as it often is)
            Q_ASSERT(e.type == QCborValue::String);
            e.flags |= Element::StringIsAscii;
        }
 
        // check that this UTF-8 text string can be loaded onto a QString
        if (e.type == QCborValue::String) {
            if (Q_UNLIKELY(b->len > QString::max_size())) {
                setErrorInReader(reader, { QCborError::DataTooLarge });
                status = QCborStreamReader::Error;
            }
        }
    }
 
    if (status == QCborStreamReader::Error) {
        data.truncate(e.value);
    } else {
        elements.append(e);
    }
}
 
void QCborContainerPrivate::decodeValueFromCbor(QCborStreamReader &reader, int remainingRecursionDepth)
{
    QCborStreamReader::Type t = reader.type();
    switch (t) {
    case QCborStreamReader::UnsignedInteger:
    case QCborStreamReader::NegativeInteger:
    case QCborStreamReader::SimpleType:
    case QCborStreamReader::Float16:
    case QCborStreamReader::Float:
    case QCborStreamReader::Double:
        elements.append(decodeBasicValueFromCbor(reader));
        break;
 
    case QCborStreamReader::ByteArray:
    case QCborStreamReader::String:
        decodeStringFromCbor(reader);
        break;
 
    case QCborStreamReader::Array:
    case QCborStreamReader::Map:
        return append(makeValue(t == QCborStreamReader::Array ? QCborValue::Array : QCborValue::Map, -1,
                                createContainerFromCbor(reader, remainingRecursionDepth),
                                MoveContainer));
 
    case QCborStreamReader::Tag:
        return append(taggedValueFromCbor(reader, remainingRecursionDepth));
 
    case QCborStreamReader::Invalid:
        return;                 // probably a decode error
    }
}
#endif // QT_CONFIG(cborstreamreader)
 
QCborValue::QCborValue(const QByteArray &ba)
    : n(0), container(new QCborContainerPrivate), t(ByteArray)
{
    container->appendByteData(ba.constData(), ba.size(), t);
    container->ref.storeRelaxed(1);
}
 
QCborValue::QCborValue(const QString &s) : QCborValue(qToStringViewIgnoringNull(s)) {}
 
QCborValue::QCborValue(QStringView s)
    : n(0), container(new QCborContainerPrivate), t(String)
{
    container->append(s);
    container->ref.storeRelaxed(1);
}
 
QCborValue::QCborValue(QLatin1StringView s)
    : n(0), container(new QCborContainerPrivate), t(String)
{
    container->append(s);
    container->ref.storeRelaxed(1);
}
 
QCborValue::QCborValue(const QCborArray &a)
    : n(-1), container(a.d.data()), t(Array)
{
    if (container)
        container->ref.ref();
}
 
QCborValue::QCborValue(const QCborMap &m)
    : n(-1), container(m.d.data()), t(Map)
{
    if (container)
        container->ref.ref();
}
 
QCborValue::QCborValue(QCborTag tag, const QCborValue &tv)
    : n(-1), container(new QCborContainerPrivate), t(Tag)
{
    container->ref.storeRelaxed(1);
    container->append(tag);
    container->append(tv);
    t = convertToExtendedType(container);
}
 
QCborValue::QCborValue(const QCborValue &other) noexcept
    : n(other.n), container(other.container), t(other.t)
{
    if (container)
        container->ref.ref();
}
 
QCborValue::QCborValue(const QDateTime &dt)
    : QCborValue(QCborKnownTags::DateTimeString, dt.toString(Qt::ISODateWithMs).toLatin1())
{
    // change types
    t = DateTime;
    container->elements[1].type = String;
}
 
#ifndef QT_BOOTSTRAPPED
QCborValue::QCborValue(const QUrl &url)
    : QCborValue(QCborKnownTags::Url, url.toString(QUrl::DecodeReserved).toUtf8())
{
    // change types
    t = Url;
    container->elements[1].type = String;
}
 
#if QT_CONFIG(regularexpression)
QCborValue::QCborValue(const QRegularExpression &rx)
    : QCborValue(QCborKnownTags::RegularExpression, rx.pattern())
{
    // change type
    t = RegularExpression;
}
#endif // QT_CONFIG(regularexpression)
 
QCborValue::QCborValue(const QUuid &uuid)
    : QCborValue(QCborKnownTags::Uuid, uuid.toRfc4122())
{
    // change our type
    t = Uuid;
}
#endif
 
// destructor
void QCborValue::dispose()
{
    container->deref();
}
 
QCborValue &QCborValue::operator=(const QCborValue &other) noexcept
{
    n = other.n;
    assignContainer(container, other.container);
    t = other.t;
    return *this;
}
 
QCborTag QCborValue::tag(QCborTag defaultValue) const
{
    return isTag() && container && container->elements.size() == 2 ?
                QCborTag(container->elements.at(0).value) : defaultValue;
}
 
QCborValue QCborValue::taggedValue(const QCborValue &defaultValue) const
{
    return isTag() && container && container->elements.size() == 2 ?
                container->valueAt(1) : defaultValue;
}
 
QByteArray QCborValue::toByteArray(const QByteArray &defaultValue) const
{
    if (!container || !isByteArray())
        return defaultValue;
 
    Q_ASSERT(n >= 0);
    return container->byteArrayAt(n);
}
 
QString QCborValue::toString(const QString &defaultValue) const
{
    if (!container || !isString())
        return defaultValue;
 
    Q_ASSERT(n >= 0);
    return container->stringAt(n);
}
 
QDateTime QCborValue::toDateTime(const QDateTime &defaultValue) const
{
    if (!container || !isDateTime() || container->elements.size() != 2)
        return defaultValue;
 
    Q_ASSERT(n == -1);
    const ByteData *byteData = container->byteData(1);
    if (!byteData)
        return defaultValue; // date/times are never empty, so this must be invalid
 
    // Our data must be US-ASCII.
    Q_ASSERT((container->elements.at(1).flags & Element::StringIsUtf16) == 0);
    return QDateTime::fromString(byteData->asLatin1(), Qt::ISODateWithMs);
}
 
#ifndef QT_BOOTSTRAPPED
QUrl QCborValue::toUrl(const QUrl &defaultValue) const
{
    if (!container || !isUrl() || container->elements.size() != 2)
        return defaultValue;
 
    Q_ASSERT(n == -1);
    const ByteData *byteData = container->byteData(1);
    if (!byteData)
        return QUrl();  // valid, empty URL
 
    return QUrl::fromEncoded(byteData->asByteArrayView());
}
 
#if QT_CONFIG(regularexpression)
QRegularExpression QCborValue::toRegularExpression(const QRegularExpression &defaultValue) const
{
    if (!container || !isRegularExpression() || container->elements.size() != 2)
        return defaultValue;
 
    Q_ASSERT(n == -1);
    return QRegularExpression(container->stringAt(1));
}
#endif // QT_CONFIG(regularexpression)
 
QUuid QCborValue::toUuid(const QUuid &defaultValue) const
{
    if (!container || !isUuid() || container->elements.size() != 2)
        return defaultValue;
 
    Q_ASSERT(n == -1);
    const ByteData *byteData = container->byteData(1);
    if (!byteData)
        return defaultValue; // UUIDs must always be 16 bytes, so this must be invalid
 
    return QUuid::fromRfc4122(byteData->asByteArrayView());
}
#endif
 
QCborArray QCborValue::toArray() const
{
    return toArray(QCborArray());
}
 
QCborArray QCborValue::toArray(const QCborArray &defaultValue) const
{
    if (!isArray())
        return defaultValue;
    QCborContainerPrivate *dd = nullptr;
    Q_ASSERT(n == -1 || container == nullptr);
    if (n < 0)
        dd = container;
    // return QCborArray(*dd); but that's UB if dd is nullptr
    return dd ? QCborArray(*dd) : QCborArray();
}
 
QCborMap QCborValue::toMap() const
{
    return toMap(QCborMap());
}
 
QCborMap QCborValue::toMap(const QCborMap &defaultValue) const
{
    if (!isMap())
        return defaultValue;
    QCborContainerPrivate *dd = nullptr;
    Q_ASSERT(n == -1 || container == nullptr);
    if (n < 0)
        dd = container;
    // return QCborMap(*dd); but that's UB if dd is nullptr
    return dd ? QCborMap(*dd) : QCborMap();
}
 
const QCborValue QCborValue::operator[](const QString &key) const
{
    return QCborContainerPrivate::findCborMapKey(*this, qToStringViewIgnoringNull(key));
}
 
const QCborValue QCborValue::operator[](QLatin1StringView key) const
{
    return QCborContainerPrivate::findCborMapKey(*this, key);
}
 
const QCborValue QCborValue::operator[](qint64 key) const
{
    if (isArray() && container && quint64(key) < quint64(container->elements.size()))
        return container->valueAt(key);
    return QCborContainerPrivate::findCborMapKey(*this, key);
}
 
static bool shouldArrayRemainArray(qint64 key, QCborValue::Type t, QCborContainerPrivate *container)
{
    constexpr qint64 LargeKey = 0x10000;
    if (t != QCborValue::Array)
        return false;
    if (key < 0)
        return false;           // negative keys can't be an array index
    if (key < LargeKey)
        return true;
 
    // Only convert to map if key is greater than array size + 1
    qsizetype currentSize = container ? container->elements.size() : 0;
    return key <= currentSize;
}
 
static void convertArrayToMap(QCborContainerPrivate *&array)
{
    if (Q_LIKELY(!array || array->elements.isEmpty()))
        return;
 
    // The Q_LIKELY and the qWarning mark the rest of this function as unlikely
    qWarning("Using CBOR array as map forced conversion");
 
    qsizetype size = array->elements.size();
    QCborContainerPrivate *map = QCborContainerPrivate::detach(array, size * 2);
    map->elements.resize(size * 2);
 
    // this may be an in-place copy, so we have to do it from the end
    auto dst = map->elements.begin();
    auto src = array->elements.constBegin();
    for (qsizetype i = size - 1; i >= 0; --i) {
        Q_ASSERT(src->type != QCborValue::Invalid);
        dst[i * 2 + 1] = src[i];
    }
    for (qsizetype i = 0; i < size; ++i)
        dst[i * 2] = { i, QCborValue::Integer };
 
    // update reference counts
    assignContainer(array, map);
}
 
static QCborContainerPrivate *maybeGrow(QCborContainerPrivate *container, qsizetype index)
{
    auto replace = QCborContainerPrivate::grow(container, index);
    Q_ASSERT(replace);
    if (replace->elements.size() == index)
        replace->append(Undefined());
    else
        Q_ASSERT(replace->elements.size() > index);
    return assignContainer(container, replace);
}
 
template <typename KeyType> inline QCborValueRef
QCborContainerPrivate::findOrAddMapKey(QCborValue &self, KeyType key)
{
    // we need a map, so convert if necessary
    if (self.isArray())
        convertArrayToMap(self.container);
    else if (!self.isMap())
        self = QCborValue(QCborValue::Map);
    self.t = QCborValue::Map;
    self.n = -1;
 
    QCborValueRef result = findOrAddMapKey<KeyType>(self.container, key);
    assignContainer(self.container, result.d);
    return result;
}
 
template<typename KeyType> QCborValueRef
QCborContainerPrivate::findOrAddMapKey(QCborValueRef self, KeyType key)
{
    auto &e = self.d->elements[self.i];
 
    // we need a map, so convert if necessary
    if (e.type == QCborValue::Array) {
        convertArrayToMap(e.container);
    } else if (e.type != QCborValue::Map) {
        if (e.flags & QtCbor::Element::IsContainer)
            e.container->deref();
        e.container = nullptr;
    }
    e.flags = QtCbor::Element::IsContainer;
    e.type = QCborValue::Map;
 
    QCborValueRef result = findOrAddMapKey<KeyType>(e.container, key);
    assignContainer(e.container, result.d);
    return result;
}
 
QCborValueRef QCborValue::operator[](const QString &key)
{
    return QCborContainerPrivate::findOrAddMapKey(*this, qToStringViewIgnoringNull(key));
}
 
QCborValueRef QCborValue::operator[](QLatin1StringView key)
{
    return QCborContainerPrivate::findOrAddMapKey(*this, key);
}
 
QCborValueRef QCborValue::operator[](qint64 key)
{
    if (shouldArrayRemainArray(key, t, container)) {
        container = maybeGrow(container, key);
        return { container, qsizetype(key) };
    }
    return QCborContainerPrivate::findOrAddMapKey(*this, key);
}
 
#if QT_CONFIG(cborstreamreader)
QCborValue QCborValue::fromCbor(QCborStreamReader &reader)
{
    QCborValue result;
    auto t = reader.type();
    if (reader.lastError() != QCborError::NoError)
        t = QCborStreamReader::Invalid;
 
    switch (t) {
    // basic types, no container needed:
    case QCborStreamReader::UnsignedInteger:
    case QCborStreamReader::NegativeInteger:
    case QCborStreamReader::SimpleType:
    case QCborStreamReader::Float16:
    case QCborStreamReader::Float:
    case QCborStreamReader::Double: {
        Element e = decodeBasicValueFromCbor(reader);
        result.n = e.value;
        result.t = e.type;
        break;
    }
 
    case QCborStreamReader::Invalid:
        result.t = QCborValue::Invalid;
        break;              // probably a decode error
 
    // strings
    case QCborStreamReader::ByteArray:
    case QCborStreamReader::String:
        result.n = 0;
        result.t = reader.isString() ? String : ByteArray;
        result.container = new QCborContainerPrivate;
        result.container->ref.ref();
        result.container->decodeStringFromCbor(reader);
        break;
 
    // containers
    case QCborStreamReader::Array:
    case QCborStreamReader::Map:
        result.n = -1;
        result.t = reader.isArray() ? Array : Map;
        result.container = createContainerFromCbor(reader, MaximumRecursionDepth);
        break;
 
    // tag
    case QCborStreamReader::Tag:
        result = taggedValueFromCbor(reader, MaximumRecursionDepth);
        break;
    }
 
    return result;
}
 
QCborValue QCborValue::fromCbor(const QByteArray &ba, QCborParserError *error)
{
    QCborStreamReader reader(ba);
    QCborValue result = fromCbor(reader);
    if (error) {
        error->error = reader.lastError();
        error->offset = reader.currentOffset();
    }
    return result;
}
 
#endif // QT_CONFIG(cborstreamreader)
 
#if QT_CONFIG(cborstreamwriter)
QByteArray QCborValue::toCbor(EncodingOptions opt) const
{
    QByteArray result;
    QCborStreamWriter writer(&result);
    toCbor(writer, opt);
    return result;
}
 
Q_NEVER_INLINE void QCborValue::toCbor(QCborStreamWriter &writer, EncodingOptions opt) const
{
    if (isContainer() || isTag())
        return encodeToCbor(writer, container, -type(), opt);
    if (container)
        return encodeToCbor(writer, container, n, opt);
 
    // very simple types
    if (isSimpleType())
        return writer.append(toSimpleType());
 
    switch (type()) {
    case Integer:
        return writer.append(n);
 
    case Double:
        return writeDoubleToCbor(writer, fp_helper(), opt);
 
    case Invalid:
        return;
 
    case SimpleType:
    case False:
    case True:
    case Null:
    case Undefined:
        // handled by "if (isSimpleType())"
        Q_UNREACHABLE();
        break;
 
    case ByteArray:
        // Byte array with no container is empty
        return writer.appendByteString("", 0);
 
    case String:
        // String with no container is empty
        return writer.appendTextString("", 0);
 
    case Array:
    case Map:
    case Tag:
        // handled by "if (isContainer() || isTag())"
        Q_UNREACHABLE();
        break;
 
    case DateTime:
    case Url:
    case RegularExpression:
    case Uuid:
        // not possible
        Q_UNREACHABLE();
        break;
    }
}
 
#  if QT_VERSION < QT_VERSION_CHECK(7, 0, 0) && !defined(QT_BOOTSTRAPPED)
void QCborValueRef::toCbor(QCborStreamWriter &writer, QCborValue::EncodingOptions opt)
{
    concrete().toCbor(writer, opt);
}
#  endif
#endif // QT_CONFIG(cborstreamwriter)
 
void QCborValueRef::assign(QCborValueRef that, const QCborValue &other)
{
    that.d->replaceAt(that.i, other);
}
 
void QCborValueRef::assign(QCborValueRef that, QCborValue &&other)
{
    that.d->replaceAt(that.i, other, QCborContainerPrivate::MoveContainer);
}
 
void QCborValueRef::assign(QCborValueRef that, const QCborValueRef other)
{
    // ### optimize?
    that = other.concrete();
}
 
bool QCborValueConstRef::concreteBoolean(QCborValueConstRef self, bool defaultValue) noexcept
{
    QtCbor::Element e = self.d->elements.at(self.i);
    if (e.type != QCborValue::False && e.type != QCborValue::True)
        return defaultValue;
    return e.type == QCborValue::True;
}
 
double QCborValueConstRef::concreteDouble(QCborValueConstRef self, double defaultValue) noexcept
{
    QtCbor::Element e = self.d->elements.at(self.i);
    if (e.type == QCborValue::Integer)
        return e.value;
    if (e.type != QCborValue::Double)
        return defaultValue;
    return e.fpvalue();
}
 
qint64 QCborValueConstRef::concreteIntegral(QCborValueConstRef self, qint64 defaultValue) noexcept
{
    QtCbor::Element e = self.d->elements.at(self.i);
    QCborValue::Type t = e.type;
    if (t == QCborValue::Double)
        return e.fpvalue();
    if (t != QCborValue::Integer)
        return defaultValue;
    return e.value;
}
 
QByteArray QCborValueConstRef::concreteByteArray(QCborValueConstRef self,
                                                 const QByteArray &defaultValue)
{
    QtCbor::Element e = self.d->elements.at(self.i);
    if (e.type != QCborValue::ByteArray)
        return defaultValue;
    return self.d->byteArrayAt(self.i);
}
 
QString QCborValueConstRef::concreteString(QCborValueConstRef self, const QString &defaultValue)
{
    QtCbor::Element e = self.d->elements.at(self.i);
    if (e.type != QCborValue::String)
        return defaultValue;
    return self.d->stringAt(self.i);
}
 
bool
QCborValueConstRef::comparesEqual_helper(QCborValueConstRef lhs, QCborValueConstRef rhs) noexcept
{
    QtCbor::Element e1 = lhs.d->elements.at(lhs.i);
    QtCbor::Element e2 = rhs.d->elements.at(rhs.i);
    return compareElementRecursive(lhs.d, e1, rhs.d, e2, Comparison::ForEquality) == 0;
}
 
Qt::strong_ordering
QCborValueConstRef::compareThreeWay_helper(QCborValueConstRef lhs, QCborValueConstRef rhs) noexcept
{
    QtCbor::Element e1 = lhs.d->elements.at(lhs.i);
    QtCbor::Element e2 = rhs.d->elements.at(rhs.i);
    int c = compareElementRecursive(lhs.d, e1, rhs.d, e2, Comparison::ForOrdering);
    return Qt::compareThreeWay(c, 0);
}
 
bool
QCborValueConstRef::comparesEqual_helper(QCborValueConstRef lhs, const QCborValue &rhs) noexcept
{
    QtCbor::Element e1 = lhs.d->elements.at(lhs.i);
    QtCbor::Element e2 = QCborContainerPrivate::elementFromValue(rhs);
    return compareElementRecursive(lhs.d, e1, rhs.container, e2, Comparison::ForEquality) == 0;
}
 
Qt::strong_ordering
QCborValueConstRef::compareThreeWay_helper(QCborValueConstRef lhs, const QCborValue &rhs) noexcept
{
    QtCbor::Element e1 = lhs.d->elements.at(lhs.i);
    QtCbor::Element e2 = QCborContainerPrivate::elementFromValue(rhs);
    int c = compareElementRecursive(lhs.d, e1, rhs.container, e2, Comparison::ForOrdering);
    return Qt::compareThreeWay(c, 0);
}
 
bool QCborArray::comparesEqual_helper(const QCborArray &lhs, QCborValueConstRef rhs) noexcept
{
    QtCbor::Element e2 = rhs.d->elements.at(rhs.i);
    if (typeOrder(QCborValue::Array, e2.type))
        return false;
    return compareContainer(lhs.d.constData(), e2.container, Comparison::ForEquality) == 0;
}
 
Qt::strong_ordering
QCborArray::compareThreeWay_helper(const QCborArray &lhs, QCborValueConstRef rhs) noexcept
{
    QtCbor::Element e2 = rhs.d->elements.at(rhs.i);
    int c = typeOrder(QCborValue::Array, e2.type);
    if (c == 0)
        c = compareContainer(lhs.d.constData(), e2.container, Comparison::ForOrdering);
    return Qt::compareThreeWay(c, 0);
}
 
bool QCborMap::comparesEqual_helper(const QCborMap &lhs, QCborValueConstRef rhs) noexcept
{
    QtCbor::Element e2 = rhs.d->elements.at(rhs.i);
    if (typeOrder(QCborValue::Array, e2.type))
        return false;
    return compareContainer(lhs.d.constData(), e2.container, Comparison::ForEquality) == 0;
}
 
Qt::strong_ordering
QCborMap::compareThreeWay_helper(const QCborMap &lhs, QCborValueConstRef rhs) noexcept
{
    QtCbor::Element e2 = rhs.d->elements.at(rhs.i);
    int c = typeOrder(QCborValue::Map, e2.type);
    if (c == 0)
        c = compareContainer(lhs.d.constData(), e2.container, Comparison::ForOrdering);
    return Qt::compareThreeWay(c, 0);
}
 
QCborValue QCborValueConstRef::concrete(QCborValueConstRef self) noexcept
{
    return self.d->valueAt(self.i);
}
 
QCborValue::Type QCborValueConstRef::concreteType(QCborValueConstRef self) noexcept
{
    return self.d->elements.at(self.i).type;
}
 
const QCborValue QCborValueConstRef::operator[](const QString &key) const
{
    const QCborValue item = d->valueAt(i);
    return item[key];
}
 
const QCborValue QCborValueConstRef::operator[](const QLatin1StringView key) const
{
    const QCborValue item = d->valueAt(i);
    return item[key];
}
 
const QCborValue QCborValueConstRef::operator[](qint64 key) const
{
    const QCborValue item = d->valueAt(i);
    return item[key];
}
 
#if QT_VERSION < QT_VERSION_CHECK(7, 0, 0) && !defined(QT_BOOTSTRAPPED)
QCborValue QCborValueRef::concrete(QCborValueRef self) noexcept
{
    return self.d->valueAt(self.i);
}
 
QCborValue::Type QCborValueRef::concreteType(QCborValueRef self) noexcept
{
    return self.d->elements.at(self.i).type;
}
 
const QCborValue QCborValueRef::operator[](const QString &key) const
{
    return QCborValueConstRef::operator[](key);
}
 
const QCborValue QCborValueRef::operator[](QLatin1StringView key) const
{
    return QCborValueConstRef::operator[](key);
}
 
const QCborValue QCborValueRef::operator[](qint64 key) const
{
    return QCborValueConstRef::operator[](key);
}
 
QCborValueRef QCborValueRef::operator[](const QString &key)
{
    return QCborContainerPrivate::findOrAddMapKey(*this, qToStringViewIgnoringNull(key));
}
 
QCborValueRef QCborValueRef::operator[](QLatin1StringView key)
{
    return QCborContainerPrivate::findOrAddMapKey(*this, key);
}
 
QCborValueRef QCborValueRef::operator[](qint64 key)
{
    auto &e = d->elements[i];
    if (shouldArrayRemainArray(key, e.type, e.container)) {
        e.container = maybeGrow(e.container, key);
        e.flags |= QtCbor::Element::IsContainer;
        return { e.container, qsizetype(key) };
    }
    return QCborContainerPrivate::findOrAddMapKey(*this, key);
}
#endif // < Qt 7
 
inline QCborArray::QCborArray(QCborContainerPrivate &dd) noexcept
    : d(&dd)
{
}
 
inline QCborMap::QCborMap(QCborContainerPrivate &dd) noexcept
    : d(&dd)
{
}
 
size_t qHash(const QCborValue &value, size_t seed)
{
    switch (value.type()) {
    case QCborValue::Integer:
        return qHash(value.toInteger(), seed);
    case QCborValue::ByteArray:
        return qHash(value.toByteArray(), seed);
    case QCborValue::String:
        return qHash(value.toString(), seed);
    case QCborValue::Array:
        return qHash(value.toArray(), seed);
    case QCborValue::Map:
        return qHash(value.toMap(), seed);
    case QCborValue::Tag: {
        QtPrivate::QHashCombine hash;
        seed = hash(seed, value.tag());
        seed = hash(seed, value.taggedValue());
        return seed;
    }
    case QCborValue::SimpleType:
        break;
    case QCborValue::False:
        return qHash(false, seed);
    case QCborValue::True:
        return qHash(true, seed);
    case QCborValue::Null:
        return qHash(nullptr, seed);
    case QCborValue::Undefined:
        return seed;
    case QCborValue::Double:
        return qHash(value.toDouble(), seed);
    case QCborValue::DateTime:
        return qHash(value.toDateTime(), seed);
#ifndef QT_BOOTSTRAPPED
    case QCborValue::Url:
        return qHash(value.toUrl(), seed);
#  if QT_CONFIG(regularexpression)
    case QCborValue::RegularExpression:
        return qHash(value.toRegularExpression(), seed);
#  endif
    case QCborValue::Uuid:
        return qHash(value.toUuid(), seed);
#endif
    case QCborValue::Invalid:
        return seed;
    default:
        break;
    }
 
    Q_ASSERT(value.isSimpleType());
    return qHash(value.toSimpleType(), seed);
}
 
Q_CORE_EXPORT const char *qt_cbor_simpletype_id(QCborSimpleType st)
{
    switch (st) {
    case QCborSimpleType::False:
        return "False";
    case QCborSimpleType::True:
        return "True";
    case QCborSimpleType::Null:
        return "Null";
    case QCborSimpleType::Undefined:
        return "Undefined";
    }
    return nullptr;
}
 
Q_CORE_EXPORT const char *qt_cbor_tag_id(QCborTag tag)
{
    // Casting to QCborKnownTags's underlying type will make the comparison
    // below fail if the tag value is out of range.
    auto n = std::underlying_type<QCborKnownTags>::type(tag);
    if (QCborTag(n) == tag) {
        switch (QCborKnownTags(n)) {
        case QCborKnownTags::DateTimeString:
            return "DateTimeString";
        case QCborKnownTags::UnixTime_t:
            return "UnixTime_t";
        case QCborKnownTags::PositiveBignum:
            return "PositiveBignum";
        case QCborKnownTags::NegativeBignum:
            return "NegativeBignum";
        case QCborKnownTags::Decimal:
            return "Decimal";
        case QCborKnownTags::Bigfloat:
            return "Bigfloat";
        case QCborKnownTags::COSE_Encrypt0:
            return "COSE_Encrypt0";
        case QCborKnownTags::COSE_Mac0:
            return "COSE_Mac0";
        case QCborKnownTags::COSE_Sign1:
            return "COSE_Sign1";
        case QCborKnownTags::ExpectedBase64url:
            return "ExpectedBase64url";
        case QCborKnownTags::ExpectedBase64:
            return "ExpectedBase64";
        case QCborKnownTags::ExpectedBase16:
            return "ExpectedBase16";
        case QCborKnownTags::EncodedCbor:
            return "EncodedCbor";
        case QCborKnownTags::Url:
            return "Url";
        case QCborKnownTags::Base64url:
            return "Base64url";
        case QCborKnownTags::Base64:
            return "Base64";
        case QCborKnownTags::RegularExpression:
            return "RegularExpression";
        case QCborKnownTags::MimeMessage:
            return "MimeMessage";
        case QCborKnownTags::Uuid:
            return "Uuid";
        case QCborKnownTags::COSE_Encrypt:
            return "COSE_Encrypt";
        case QCborKnownTags::COSE_Mac:
            return "COSE_Mac";
        case QCborKnownTags::COSE_Sign:
            return "COSE_Sign";
        case QCborKnownTags::Signature:
            return "Signature";
        }
    }
    return nullptr;
}
 
#if !defined(QT_NO_DEBUG_STREAM)
static QDebug debugContents(QDebug &dbg, const QCborValue &v)
{
    switch (v.type()) {
    case QCborValue::Integer:
        return dbg << v.toInteger();
    case QCborValue::ByteArray:
        return dbg << "QByteArray(" << v.toByteArray() << ')';
    case QCborValue::String:
        return dbg << v.toString();
    case QCborValue::Array:
        return dbg << v.toArray();
    case QCborValue::Map:
        return dbg << v.toMap();
    case QCborValue::Tag: {
        QCborTag tag = v.tag();
        const char *id = qt_cbor_tag_id(tag);
        if (id)
            dbg.nospace() << "QCborKnownTags::" << id << ", ";
        else
            dbg.nospace() << "QCborTag(" << quint64(tag) << "), ";
        return dbg << v.taggedValue();
    }
    case QCborValue::SimpleType:
        break;
    case QCborValue::True:
        return dbg << true;
    case QCborValue::False:
        return dbg << false;
    case QCborValue::Null:
        return dbg << "nullptr";
    case QCborValue::Undefined:
        return dbg;
    case QCborValue::Double: {
        qint64 i;
        if (convertDoubleTo(v.toDouble(), &i))
            return dbg << i << ".0";
        else
            return dbg << v.toDouble();
    }
    case QCborValue::DateTime:
        return dbg << v.toDateTime();
#ifndef QT_BOOTSTRAPPED
    case QCborValue::Url:
        return dbg << v.toUrl();
#if QT_CONFIG(regularexpression)
    case QCborValue::RegularExpression:
        return dbg << v.toRegularExpression();
#endif
    case QCborValue::Uuid:
        return dbg << v.toUuid();
#endif
    case QCborValue::Invalid:
        return dbg << "<invalid>";
    default:
        break;
    }
    if (v.isSimpleType())
        return dbg << v.toSimpleType();
    return dbg << "<unknown type 0x" << Qt::hex << int(v.type()) << Qt::dec << '>';
}
QDebug operator<<(QDebug dbg, const QCborValue &v)
{
    QDebugStateSaver saver(dbg);
    dbg.nospace() << "QCborValue(";
    return debugContents(dbg, v) << ')';
}
 
QDebug operator<<(QDebug dbg, QCborSimpleType st)
{
    QDebugStateSaver saver(dbg);
    const char *id = qt_cbor_simpletype_id(st);
    if (id)
        return dbg.nospace() << "QCborSimpleType::" << id;
 
    return dbg.nospace() << "QCborSimpleType(" << uint(st) << ')';
}
 
QDebug operator<<(QDebug dbg, QCborTag tag)
{
    QDebugStateSaver saver(dbg);
    const char *id = qt_cbor_tag_id(tag);
    dbg.nospace() << "QCborTag(";
    if (id)
        dbg.nospace() << "QCborKnownTags::" << id;
    else
        dbg.nospace() << quint64(tag);
 
    return dbg << ')';
}
 
QDebug operator<<(QDebug dbg, QCborKnownTags tag)
{
    QDebugStateSaver saver(dbg);
    const char *id = qt_cbor_tag_id(QCborTag(int(tag)));
    if (id)
        return dbg.nospace() << "QCborKnownTags::" << id;
 
    return dbg.nospace() << "QCborKnownTags(" << int(tag) << ')';
}
#endif
 
#ifndef QT_NO_DATASTREAM
#if QT_CONFIG(cborstreamwriter)
QDataStream &operator<<(QDataStream &stream, const QCborValue &value)
{
    stream << QCborValue(value).toCbor();
    return stream;
}
#endif
 
QDataStream &operator>>(QDataStream &stream, QCborValue &value)
{
    QByteArray buffer;
    stream >> buffer;
    QCborParserError parseError{};
    value = QCborValue::fromCbor(buffer, &parseError);
    if (parseError.error)
        stream.setStatus(QDataStream::ReadCorruptData);
    return stream;
}
#endif
 
 
QT_END_NAMESPACE
 
#include "qcborarray.cpp"
#include "qcbormap.cpp"
 
#ifndef QT_NO_QOBJECT
#include "moc_qcborvalue.cpp"
#endif