From adb41bbe00b2b853d4dd26cd9ee77ae5ed541576 Mon Sep 17 00:00:00 2001 From: Andrei Golubev Date: Sun, 25 Apr 2021 22:47:39 +0200 Subject: Add more tests for QList/QString/QBA The major part is stability tests for QList operations, Also added std::shared_ptr to the Custom type. shared_ptr accesses the memory which does not directly belong to QList, so using it inside a passed-to-qlist type is beneficial (e.g. ASan could catch extra issues) Basic prepend-aware cases added to QString/QBA tests Task-number: QTBUG-93019 Pick-to: dev 6.0 6.1 Change-Id: I50e742bdf10ea9de2de66539a7dbb9abc4352f82 Reviewed-by: Lars Knoll --- .../corelib/text/qbytearray/tst_qbytearray.cpp | 53 +++ tests/auto/corelib/text/qstring/tst_qstring.cpp | 73 ++++ tests/auto/corelib/tools/qlist/tst_qlist.cpp | 372 +++++++++++++++++++-- 3 files changed, 471 insertions(+), 27 deletions(-) (limited to 'tests/auto/corelib') diff --git a/tests/auto/corelib/text/qbytearray/tst_qbytearray.cpp b/tests/auto/corelib/text/qbytearray/tst_qbytearray.cpp index 70180bbf3b..8b2a903627 100644 --- a/tests/auto/corelib/text/qbytearray/tst_qbytearray.cpp +++ b/tests/auto/corelib/text/qbytearray/tst_qbytearray.cpp @@ -894,6 +894,27 @@ void tst_QByteArray::append() QByteArray twoChars("ab"); tenChars.append(twoChars); QCOMPARE(tenChars.capacity(), 10); + + { + QByteArray prepended("abcd"); + prepended.prepend('a'); + const qsizetype freeAtEnd = prepended.data_ptr()->freeSpaceAtEnd(); + QVERIFY(prepended.size() + freeAtEnd < prepended.capacity()); + prepended += QByteArray(freeAtEnd, 'b'); + prepended.append('c'); + QCOMPARE(prepended, QByteArray("aabcd") + QByteArray(freeAtEnd, 'b') + QByteArray("c")); + } + + { + QByteArray prepended2("aaaaaaaaaa"); + while (prepended2.size()) + prepended2.remove(0, 1); + QVERIFY(prepended2.data_ptr()->freeSpaceAtBegin() > 0); + QByteArray array(prepended2.data_ptr()->freeSpaceAtEnd(), 'a'); + prepended2 += array; + prepended2.append('b'); + QCOMPARE(prepended2, array + QByteArray("b")); + } } void tst_QByteArray::appendExtended_data() @@ -958,6 +979,38 @@ void tst_QByteArray::insert() ba = "one"; QCOMPARE(ba.insert(1, QByteArrayView(ba)), QByteArray("oonene")); QCOMPARE(ba.size(), 6); + + { + ba = "one"; + ba.prepend('a'); + QByteArray b(ba.data_ptr()->freeSpaceAtEnd(), 'b'); + QCOMPARE(ba.insert(ba.size() + 1, QByteArrayView(b)), QByteArray("aone ") + b); + } + + { + ba = "onetwothree"; + while (ba.size() - 1) + ba.remove(0, 1); + QByteArray b(ba.data_ptr()->freeSpaceAtEnd() + 1, 'b'); + QCOMPARE(ba.insert(ba.size() + 1, QByteArrayView(b)), QByteArray("e ") + b); + } + + { + ba = "one"; + ba.prepend('a'); + const qsizetype freeAtEnd = ba.data_ptr()->freeSpaceAtEnd(); + QCOMPARE(ba.insert(ba.size() + 1, freeAtEnd + 1, 'b'), + QByteArray("aone ") + QByteArray(freeAtEnd + 1, 'b')); + } + + { + ba = "onetwothree"; + while (ba.size() - 1) + ba.remove(0, 1); + const qsizetype freeAtEnd = ba.data_ptr()->freeSpaceAtEnd(); + QCOMPARE(ba.insert(ba.size() + 1, freeAtEnd + 1, 'b'), + QByteArray("e ") + QByteArray(freeAtEnd + 1, 'b')); + } } void tst_QByteArray::insertExtended_data() diff --git a/tests/auto/corelib/text/qstring/tst_qstring.cpp b/tests/auto/corelib/text/qstring/tst_qstring.cpp index 79c4fa4ab0..c962496980 100644 --- a/tests/auto/corelib/text/qstring/tst_qstring.cpp +++ b/tests/auto/corelib/text/qstring/tst_qstring.cpp @@ -2419,6 +2419,36 @@ void tst_QString::insert_special_cases() QCOMPARE(a.insert(1, QLatin1String("BCD")), QString("ABCDEF")); QCOMPARE(a.insert(3, QLatin1String("-")), QString("ABC-DEF")); QCOMPARE(a.insert(a.size() + 1, QLatin1String("XYZ")), QString("ABC-DEF XYZ")); + + { + a = "one"; + a.prepend(u'a'); + QString b(a.data_ptr()->freeSpaceAtEnd(), u'b'); + QCOMPARE(a.insert(a.size() + 1, QLatin1String(b.toLatin1())), QString("aone ") + b); + } + + { + a = "onetwothree"; + while (a.size() - 1) + a.remove(0, 1); + QString b(a.data_ptr()->freeSpaceAtEnd() + 1, u'b'); + QCOMPARE(a.insert(a.size() + 1, QLatin1String(b.toLatin1())), QString("e ") + b); + } + + { + a = "one"; + a.prepend(u'a'); + QString b(a.data_ptr()->freeSpaceAtEnd(), u'b'); + QCOMPARE(a.insert(a.size() + 1, b), QString("aone ") + b); + } + + { + a = "onetwothree"; + while (a.size() - 1) + a.remove(0, 1); + QString b(a.data_ptr()->freeSpaceAtEnd() + 1, u'b'); + QCOMPARE(a.insert(a.size() + 1, b), QString("e ") + b); + } } void tst_QString::append_data(bool emptyIsNoop) @@ -2478,6 +2508,49 @@ void tst_QString::append_special_cases() a.append(QLatin1String("BC")); QCOMPARE(a, QLatin1String("ABC")); } + + { + QString a = "one"; + a.prepend(u'a'); + QString b(a.data_ptr()->freeSpaceAtEnd(), u'b'); + QCOMPARE(a.append(QLatin1String(b.toLatin1())), QString("aone") + b); + } + + { + QString a = "onetwothree"; + while (a.size() - 1) + a.remove(0, 1); + QString b(a.data_ptr()->freeSpaceAtEnd(), u'b'); + QCOMPARE(a.append(QLatin1String(b.toLatin1())), QString("e") + b); + } + + { + QString a = "one"; + a.prepend(u'a'); + QString b(a.data_ptr()->freeSpaceAtEnd(), u'b'); + QCOMPARE(a.append(b), QString("aone") + b); + } + + { + QString a = "onetwothree"; + while (a.size() - 1) + a.remove(0, 1); + QString b(a.data_ptr()->freeSpaceAtEnd() + 1, u'b'); + QCOMPARE(a.append(b), QString("e") + b); + } + + { + QString a = "one"; + a.prepend(u'a'); + QCOMPARE(a.append(u'b'), QString("aoneb")); + } + + { + QString a = "onetwothree"; + while (a.size() - 1) + a.remove(0, 1); + QCOMPARE(a.append(u'b'), QString("eb")); + } } void tst_QString::append_bytearray_special_cases_data() diff --git a/tests/auto/corelib/tools/qlist/tst_qlist.cpp b/tests/auto/corelib/tools/qlist/tst_qlist.cpp index 14c679562f..75da6bcd41 100644 --- a/tests/auto/corelib/tools/qlist/tst_qlist.cpp +++ b/tests/auto/corelib/tools/qlist/tst_qlist.cpp @@ -139,6 +139,7 @@ struct Custom { i = 0; counter.fetchAndAddRelaxed(-1); state = Destructed; + QVERIFY(heapData.use_count() > 0); // otherwise it's double free } bool operator ==(const Custom &other) const @@ -167,6 +168,9 @@ struct Custom { char i; // used to identify orgin of an instance private: Custom *that; // used to check if an instance was moved + // shared_ptr triggers ASan/LSan and can track if double free happens, which + // is convenient to ensure there's no malfunctioning QList APIs + std::shared_ptr heapData = std::shared_ptr(new int(42)); enum State { Constructed = 106, Destructed = 110 }; State state; @@ -355,6 +359,28 @@ private slots: void reinsertToEndInt_qtbug91360() const { reinsertToEnd(); } void reinsertToEndMovable_qtbug91360() const { reinsertToEnd(); } void reinsertToEndCustom_qtbug91360() const { reinsertToEnd(); } + void reinsertRangeToEndInt_qtbug91360() const { reinsertRangeToEnd(); } + void reinsertRangeToEndMovable_qtbug91360() const { reinsertRangeToEnd(); } + void reinsertRangeToEndCustom_qtbug91360() const { reinsertRangeToEnd(); } + // QList reference stability tests: + void stability_reserveInt() const { stability_reserve(); } + void stability_reserveMovable() const { stability_reserve(); } + void stability_reserveCustom() const { stability_reserve(); } + void stability_eraseInt() const { stability_erase(); } + void stability_eraseMovable() const { stability_erase(); } + void stability_eraseCustom() const { stability_erase(); } + void stability_appendInt() const { stability_append(); } + void stability_appendMovable() const { stability_append(); } + void stability_appendCustom() const { stability_append(); } + void stability_insertElementInt() const { stability_insertElement(); } + void stability_insertElementMovable() const { stability_insertElement(); } + void stability_insertElementCustom() const { stability_insertElement(); } + void stability_emplaceInt() const { stability_emplace(); } + void stability_emplaceMovable() const { stability_emplace(); } + void stability_emplaceCustom() const { stability_emplace(); } + void stability_resizeInt() const { stability_resize(); } + void stability_resizeMovable() const { stability_resize(); } + void stability_resizeCustom() const { stability_resize(); } private: template void copyConstructor() const; @@ -384,10 +410,55 @@ private: template void detachThreadSafety() const; template void emplaceImpl() const; template void emplaceConsistentWithStdVectorImpl() const; + template + void reinsert(Reinsert op) const; template - void reinsertToBegin() const; + void reinsertToBegin() const + { + reinsert([](QList &list) { + list.prepend(list.back()); + list.removeLast(); + }); + } + template + void reinsertToEnd() const + { + reinsert([](QList &list) { + list.append(list.front()); + list.removeFirst(); + }); + } + template + void reinsertRangeToEnd() const + { + reinsert([](QList &list) { + list.append(list.begin(), list.begin() + 1); + list.removeFirst(); + }); + } + template + void stability_reserve() const; + template + void stability_erase() const; + template + void stability_append() const; + template + void stability_insert(Insert op) const; + template + void stability_resize() const; + template - void reinsertToEnd() const; + void stability_insertElement() const + { + stability_insert( + [](QList &list, int pos, const T &value) { list.insert(pos, 1, value); }); + } + template + void stability_emplace() const + { + stability_insert( + [](QList &list, int pos, const T &value) { list.emplace(pos, value); }); + } }; @@ -425,6 +496,18 @@ const Custom SimpleValue::Values[] = { 110, 105, 101, 114, 111, 98 }; #define T_DOG SimpleValue::at(4) #define T_BLAH SimpleValue::at(5) +// returns a pair of QList and QList +template +decltype(auto) qlistCopyAndReferenceFromRange(It first, It last) +{ + using T = typename std::iterator_traits::value_type; + QList copy(first, last); + QList reference; + for (; first != last; ++first) + reference.append(std::addressof(*first)); + return std::make_pair(copy, reference); +} + void tst_QList::constructors_empty() const { QList emptyInt; @@ -2700,6 +2783,10 @@ void tst_QList::reserveZero() vec.append(42); QCOMPARE(vec.size(), 1); QVERIFY(vec.capacity() >= 1); + + QList vec2; + vec2.reserve(0); // should not crash either + vec2.reserve(-1); } template @@ -3274,51 +3361,282 @@ void tst_QList::qtbug_90359() const QCOMPARE(actual, expected); } -template -void tst_QList::reinsertToBegin() const +template +void tst_QList::reinsert(Reinsert op) const { QList list(1); - const auto reinsert = [](QList &list) { - list.prepend(list.back()); - list.removeLast(); - }; - // this constant is big enough for the QList to stop reallocating, after // all, size is always less than 3 const int maxIters = 128; for (int i = 0; i < maxIters; ++i) { - reinsert(list); + op(list); } // if QList continues to grow, it's an error qsizetype capacity = list.capacity(); for (int i = 0, enoughIters = int(capacity) * 2; i < enoughIters; ++i) { - reinsert(list); + op(list); QCOMPARE(capacity, list.capacity()); } } template -void tst_QList::reinsertToEnd() const +void tst_QList::stability_reserve() const { - QList list(1); - const auto reinsert = [](QList &list) { - list.append(list.front()); - list.removeFirst(); - }; + // NOTE: this test verifies that QList::constData() stays unchanged when + // inserting as much as requested by the reserve. This is specifically + // designed this way as in cases when QTypeInfo::isRelocatable returns + // true, reallocation might use fast ::realloc() path which may in theory + // (and, actually, in practice) just expand the current memory area and thus + // keep QList::constData() unchanged, which means checks like + // QVERIFY(oldConstData != vec.constData()) are flaky. When + // QTypeInfo::isRelocatable returns false, constData() will always change + // if a reallocation happens and this will fail the test. This should be + // sufficient on its own to test the stability requirements. - // this constant is big enough for the QList to stop reallocating, after - // all, size is always less than 3 - const int maxIters = 128; - for (int i = 0; i < maxIters; ++i) { - reinsert(list); + { + QList vec; + vec.reserve(64); + const T *ptr = vec.constData(); + vec.append(QList(64)); + QCOMPARE(ptr, vec.constData()); } - // if QList continues to grow, it's an error - qsizetype capacity = list.capacity(); - for (int i = 0, enoughIters = int(capacity) * 2; i < enoughIters; ++i) { - reinsert(list); - QCOMPARE(capacity, list.capacity()); + { + QList vec; + vec.prepend(SimpleValue::at(0)); + vec.removeFirst(); + vec.reserve(64); + const T *ptr = vec.constData(); + vec.append(QList(64)); + QCOMPARE(ptr, vec.constData()); + } + + { + QList vec; + const T *ptr = vec.constData(); + vec.reserve(vec.capacity()); + QCOMPARE(ptr, vec.constData()); + vec.append(QList(vec.capacity())); + QCOMPARE(ptr, vec.constData()); + } + + { + QList vec; + vec.prepend(SimpleValue::at(0)); + vec.removeFirst(); + vec.reserve(vec.capacity()); + const T *ptr = vec.constData(); + vec.append(QList(vec.capacity())); + QCOMPARE(ptr, vec.constData()); + } + + { + QList vec; + vec.append(SimpleValue::at(0)); + vec.reserve(64); + const T *ptr = vec.constData(); + vec.append(QList(64 - vec.size())); // 1 element is already in the container + QCOMPARE(ptr, vec.constData()); + QCOMPARE(vec.size(), 64); + QCOMPARE(vec.capacity(), 64); + const qsizetype oldCapacity = vec.capacity(); + vec.append(SimpleValue::at(1)); // will reallocate as this exceeds 64 + QVERIFY(oldCapacity < vec.capacity()); + } + + { + QList vec; + vec.prepend(SimpleValue::at(0)); + vec.reserve(64); + const T *ptr = vec.constData(); + vec.append(QList(64 - vec.size())); // 1 element is already in the container + QCOMPARE(ptr, vec.constData()); + QCOMPARE(vec.size(), 64); + QCOMPARE(vec.capacity(), 64); + const qsizetype oldCapacity = vec.capacity(); + vec.append(SimpleValue::at(1)); // will reallocate as this exceeds 64 + QVERIFY(oldCapacity < vec.capacity()); + } +} + +template +void tst_QList::stability_erase() const +{ + // invalidated: [pos, end()) + for (int pos = 1; pos < 10; ++pos) { + QList v(10); + int k = 0; + std::generate(v.begin(), v.end(), [&k]() { return SimpleValue::at(k++); }); + const auto ptr = v.constData(); + + auto [copy, reference] = qlistCopyAndReferenceFromRange(v.begin(), v.begin() + pos); + + v.remove(pos, 1); + QVERIFY(ptr == v.constData()); + for (int i = 0; i < copy.size(); ++i) + QCOMPARE(*reference[i], copy[i]); + } + + // 0 is a special case, because all values get invalidated + { + QList v(10); + const auto ptr = v.constData(); + v.remove(0, 2); + QVERIFY(ptr != v.constData()); // can do fast removal from begin() + } + + // when erasing everything, leave the data pointer in place (not strictly + // required, but this makes more sense in general) + { + QList v(10); + const auto ptr = v.constData(); + v.remove(0, v.size()); + QVERIFY(ptr == v.constData()); + } +} + +template +void tst_QList::stability_append() const +{ + { + QList v(10); + int k = 0; + std::generate(v.begin(), v.end(), [&k]() { return SimpleValue::at(k++); }); + QList src(1, SimpleValue::at(0)); + v.append(src.begin(), src.end()); + QVERIFY(v.size() < v.capacity()); + + for (int i = 0; i < v.capacity() - v.size(); ++i) { + auto [copy, reference] = qlistCopyAndReferenceFromRange(v.begin(), v.end()); + v.append(SimpleValue::at(i)); + for (int i = 0; i < copy.size(); ++i) + QCOMPARE(*reference[i], copy[i]); + } + } + + { + QList v; + v.reserve(10); + const qsizetype capacity = v.capacity(); + const T *ptr = v.constData(); + v.prepend(SimpleValue::at(0)); + // here we abuse the internal details of QList. since there's enough + // free space, QList should've only rearranged the data in memory, + // without reallocating. + QCOMPARE(capacity, v.capacity()); // otherwise cannot rely on ptr + const qsizetype freeSpaceAtBegin = v.constData() - ptr; + const qsizetype freeSpaceAtEnd = v.capacity() - v.size() - freeSpaceAtBegin; + QVERIFY(freeSpaceAtEnd > 0); // otherwise this test is useless + QVERIFY(v.size() + freeSpaceAtBegin + freeSpaceAtEnd == v.capacity()); + + for (int i = 0; i < freeSpaceAtEnd; ++i) { + auto [copy, reference] = qlistCopyAndReferenceFromRange(v.begin(), v.end()); + QList src(1, SimpleValue::at(i)); + v.append(src.begin(), src.end()); + for (int i = 0; i < copy.size(); ++i) + QCOMPARE(*reference[i], copy[i]); + } + } +} + +template +void tst_QList::stability_insert(Insert op) const +{ + // invalidated: [pos, end()) + for (int pos = 1; pos <= 10; ++pos) { + QList v(10); + int k = 0; + std::generate(v.begin(), v.end(), [&k]() { return SimpleValue::at(k++); }); + v.append(SimpleValue::at(0)); // causes growth + v.removeLast(); + QCOMPARE(v.size(), 10); + QVERIFY(v.size() < v.capacity()); + + auto [copy, reference] = qlistCopyAndReferenceFromRange(v.begin(), v.begin() + pos); + op(v, pos, SimpleValue::at(0)); + for (int i = 0; i < pos; ++i) + QCOMPARE(*reference[i], copy[i]); + } + + for (int pos = 1; pos <= 10; ++pos) { + QList v(10); + int k = 0; + std::generate(v.begin(), v.end(), [&k]() { return SimpleValue::at(k++); }); + v.prepend(SimpleValue::at(0)); // causes growth and free space at begin > 0 + v.removeFirst(); + QCOMPARE(v.size(), 10); + QVERIFY(v.size() < v.capacity()); + + auto [copy, reference] = qlistCopyAndReferenceFromRange(v.begin(), v.begin() + pos); + op(v, pos, SimpleValue::at(0)); + for (int i = 0; i < pos; ++i) + QCOMPARE(*reference[i], copy[i]); + } +} + +template +void tst_QList::stability_resize() const +{ + { + QList v(10); + v.reserve(15); + QVERIFY(v.size() < v.capacity()); + int k = 0; + std::generate(v.begin(), v.end(), [&k]() { return SimpleValue::at(k++); }); + auto [copy, reference] = qlistCopyAndReferenceFromRange(v.begin(), v.end()); + + v.resize(15); + for (int i = 0; i < copy.size(); ++i) + QCOMPARE(*reference[i], copy[i]); + } + + { + QList v(10); + int k = 0; + std::generate(v.begin(), v.end(), [&k]() { return SimpleValue::at(k++); }); + auto [copy, reference] = qlistCopyAndReferenceFromRange(v.begin(), v.end()); + + v.resize(10); + for (int i = 0; i < 10; ++i) + QCOMPARE(*reference[i], copy[i]); + } + + { + QList v(10); + int k = 0; + std::generate(v.begin(), v.end(), [&k]() { return SimpleValue::at(k++); }); + auto [copy, reference] = qlistCopyAndReferenceFromRange(v.begin(), v.end()); + + v.resize(5); + for (int i = 0; i < 5; ++i) + QCOMPARE(*reference[i], copy[i]); + } + + // special case due to prepend: + { + QList v; + v.reserve(20); + const qsizetype capacity = v.capacity(); + const T *ptr = v.constData(); + v.prepend(SimpleValue::at(0)); // now there's free space at begin + v.resize(10); + QVERIFY(v.size() < v.capacity()); + // here we abuse the internal details of QList. since there's enough + // free space, QList should've only rearranged the data in memory, + // without reallocating. + QCOMPARE(capacity, v.capacity()); // otherwise cannot rely on ptr + const qsizetype freeSpaceAtBegin = v.constData() - ptr; + const qsizetype freeSpaceAtEnd = v.capacity() - v.size() - freeSpaceAtBegin; + QVERIFY(freeSpaceAtEnd > 0); // otherwise this test is useless + QVERIFY(v.size() + freeSpaceAtBegin + freeSpaceAtEnd == v.capacity()); + int k = 0; + std::generate(v.begin(), v.end(), [&k]() { return SimpleValue::at(k++); }); + auto [copy, reference] = qlistCopyAndReferenceFromRange(v.begin(), v.end()); + + v.resize(v.size() + freeSpaceAtEnd); + for (int i = 0; i < copy.size(); ++i) + QCOMPARE(*reference[i], copy[i]); } } -- cgit v1.2.3