Reading QJsonObject property should not modify the object itself.

Before this change such code:

    QJsonObject o;
    o["blah"];

would create property "blah" and assign null value to it, while
this code:

    const QJsonObject o;
    o["blah"];

would not. The change unifies the confusing behavior. Now reading
a non-existing property, is not causing a property to be added
in any visible way.

Internally QJsonObject stores a special hash of undefined, but
referenced values. Such reference is supposed to not live long,
only to the first compacting or assignment.

Change-Id: Ib022acf74ff49bad88d45d65d7093c4281d468f1
Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
Reviewed-by: Lars Knoll <lars.knoll@digia.com>

5 files changed, 207 insertions, 11 deletions

diff --git a/src/corelib/json/qjson_p.h b/src/corelib/json/qjson_p.h
index 7d0162938d..92330175ba 100644
--- a/src/corelib/json/qjson_p.h
+++ b/src/corelib/json/qjson_p.h
@@ -61,6 +61,8 @@
 #include <qstring.h>
 #include <qendian.h>
 #include <qnumeric.h>
+#include <QtCore/qhash.h>
+#include <QtCore/qmutex.h>
 
 #include <limits.h>
 #include <limits>
@@ -776,6 +778,75 @@ private:
     Q_DISABLE_COPY(Data)
 };
 
+struct ObjectUndefinedKeys
+{
+    static void insertKey(const QJsonObject *object, int index, const QString &key)
+    {
+        QMutexLocker lock(&mutex);
+        keys()[object][index] = key;
+    }
+    static QString takeKey(const QJsonObject *object, int index)
+    {
+        QMutexLocker lock(&mutex);
+        return keys()[object].take(index);
+    }
+    static void removeKeys(const QJsonObject *object)
+    {
+        QMutexLocker lock(&mutex);
+        keys().remove(object);
+    }
+private:
+    typedef QHash<const QJsonObject*, QHash<int, QString> > KeysHash;
+    static KeysHash &keys()
+    {
+        static KeysHash keys;
+        return keys;
+    }
+   static QBasicMutex mutex;
+};
+
+} // namespace QJsonPrivate
+
+struct QJsonValueRef::UnionHelper
+{
+    static inline QJsonObject *untaggedPointer(QJsonObject *object)
+    {
+        const quintptr Mask = ~quintptr(0) << 2;
+        return reinterpret_cast<QJsonObject*>(quintptr(object) & Mask);
+    }
+    static inline QJsonObject *taggedPointer(QJsonObject *object)
+    {
+        const quintptr Mask = 1;
+        return reinterpret_cast<QJsonObject*>(quintptr(object) | Mask);
+    }
+
+    static void setValueAt(QJsonValueRef *ref, QJsonValue value)
+    {
+        using namespace QJsonPrivate;
+        QJsonObject *object = untaggedPointer(ref->o);
+        if (ref->o != object)
+            object->insert(ObjectUndefinedKeys::takeKey(object, ref->index), value);
+        else
+            object->setValueAt(ref->index, value);
+    }
+
+    static QJsonValue valueAt(const QJsonValueRef *ref)
+    {
+        QJsonObject *object = untaggedPointer(ref->o);
+        if (ref->o != object)
+            return QJsonValue::Undefined;
+        return ref->o->valueAt(ref->index);
+    }
+};
+
+/*!
+    \internal
+    Constructor that creates reference to an undefined value in \a object.
+*/
+inline QJsonValueRef::QJsonValueRef(QJsonObject *object, const QString &key)
+    : o(UnionHelper::taggedPointer(object)), is_object(true), index(qHash(key))
+{
+    QJsonPrivate::ObjectUndefinedKeys::insertKey(object, index, key);
 }
 
 QT_END_NAMESPACE
diff --git a/src/corelib/json/qjsonobject.cpp b/src/corelib/json/qjsonobject.cpp
index fb975c65e0..94ec9a2818 100644
--- a/src/corelib/json/qjsonobject.cpp
+++ b/src/corelib/json/qjsonobject.cpp
@@ -134,6 +134,7 @@ QJsonObject::~QJsonObject()
 {
     if (d && !d->ref.deref())
         delete d;
+    QJsonPrivate::ObjectUndefinedKeys::removeKeys(this); // ### Qt6 move it to ~QJsonValueRef
 }
 
 /*!
@@ -290,14 +291,9 @@ QJsonValue QJsonObject::operator [](const QString &key) const
  */
 QJsonValueRef QJsonObject::operator [](const QString &key)
 {
-    // ### somewhat inefficient, as we lookup the key twice if it doesn't yet exist
     bool keyExists = false;
     int index = o ? o->indexOf(key, &keyExists) : -1;
-    if (!keyExists) {
-        iterator i = insert(key, QJsonValue());
-        index = i.i;
-    }
-    return QJsonValueRef(this, index);
+    return keyExists ? QJsonValueRef(this, index) : QJsonValueRef(this, key);
 }
 
 /*!
@@ -1001,7 +997,9 @@ void QJsonObject::compact()
 
     detach();
     d->compact();
-    o = static_cast<QJsonPrivate::Object *>(d->header->root());
+    using namespace QJsonPrivate;
+    o = static_cast<Object *>(d->header->root());
+    ObjectUndefinedKeys::removeKeys(this); // ### Qt6 move it to ~QJsonValueRef
 }
 
 /*!
@@ -1038,6 +1036,8 @@ void QJsonObject::setValueAt(int i, const QJsonValue &val)
     insert(e->key(), val);
 }
 
+QBasicMutex QJsonPrivate::ObjectUndefinedKeys::mutex;
+
 #if !defined(QT_NO_DEBUG_STREAM) && !defined(QT_JSON_READONLY)
 QDebug operator<<(QDebug dbg, const QJsonObject &o)
 {
diff --git a/src/corelib/json/qjsonvalue.cpp b/src/corelib/json/qjsonvalue.cpp
index 4c4838d314..1224a24709 100644
--- a/src/corelib/json/qjsonvalue.cpp
+++ b/src/corelib/json/qjsonvalue.cpp
@@ -669,11 +669,10 @@ void QJsonValue::detach()
     However, they are not explicitly documented here.
 */
 
-
 QJsonValueRef &QJsonValueRef::operator =(const QJsonValue &val)
 {
     if (is_object)
-        o->setValueAt(index, val);
+        UnionHelper::setValueAt(this, val);
     else
         a->replace(index, val);
 
@@ -683,7 +682,7 @@ QJsonValueRef &QJsonValueRef::operator =(const QJsonValue &val)
 QJsonValueRef &QJsonValueRef::operator =(const QJsonValueRef &ref)
 {
     if (is_object)
-        o->setValueAt(index, ref);
+        UnionHelper::setValueAt(this, ref);
     else
         a->replace(index, ref);
 
@@ -704,7 +703,7 @@ QJsonValue QJsonValueRef::toValue() const
 {
     if (!is_object)
         return a->at(index);
-    return o->valueAt(index);
+    return UnionHelper::valueAt(this);
 }
 
 #if !defined(QT_NO_DEBUG_STREAM) && !defined(QT_JSON_READONLY)
diff --git a/src/corelib/json/qjsonvalue.h b/src/corelib/json/qjsonvalue.h
index 97e20b574d..a00bc0b72f 100644
--- a/src/corelib/json/qjsonvalue.h
+++ b/src/corelib/json/qjsonvalue.h
@@ -149,6 +149,7 @@ public:
         : a(array), is_object(false), index(idx) {}
     QJsonValueRef(QJsonObject *object, int idx)
         : o(object), is_object(true), index(idx) {}
+    inline QJsonValueRef(QJsonObject *object, const QString &key);
 
     inline operator QJsonValue() const { return toValue(); }
     QJsonValueRef &operator = (const QJsonValue &val);
@@ -188,6 +189,7 @@ private:
     };
     uint is_object : 1;
     uint index : 31;
+    struct UnionHelper;
 };
 
 #if !defined(QT_NO_DEBUG_STREAM) && !defined(QT_JSON_READONLY)
diff --git a/tests/auto/corelib/json/tst_qtjson.cpp b/tests/auto/corelib/json/tst_qtjson.cpp
index a4254cb65c..7f5d438ac2 100644
--- a/tests/auto/corelib/json/tst_qtjson.cpp
+++ b/tests/auto/corelib/json/tst_qtjson.cpp
@@ -92,6 +92,7 @@ private Q_SLOTS:
     void nullObject();
     void constNullObject();
 
+    void undefinedKeys();
     void keySorting();
 
     void undefinedValues();
@@ -136,6 +137,8 @@ private Q_SLOTS:
     void testJsonValueRefDefault();
 
     void valueEquals();
+    void objectEquals_data();
+    void objectEquals();
 
     void bom();
     void nesting();
@@ -713,6 +716,28 @@ void tst_QtJson::testValueRef()
 void tst_QtJson::testObjectIteration()
 {
     QJsonObject object;
+
+    for (QJsonObject::iterator it = object.begin(); it != object.end(); ++it)
+        QVERIFY(false);
+
+    object["undefined"];
+    for (QJsonObject::iterator it = object.begin(); it != object.end(); ++it)
+        QVERIFY(false);
+
+    const QString property = "kkk";
+    object.insert(property, 11);
+    object.take(property);
+    for (QJsonObject::iterator it = object.begin(); it != object.end(); ++it)
+        QVERIFY(false);
+
+    object.insert(property, 11);
+    object["aaa"]; // before "kkk"
+    object["zzz"]; // after "kkk"
+    for (QJsonObject::iterator it = object.begin(); it != object.end(); ++it)
+        QCOMPARE(it.key(), property);
+
+    object = QJsonObject();
+
     for (int i = 0; i < 10; ++i)
         object[QString::number(i)] = (double)i;
 
@@ -986,6 +1011,7 @@ void tst_QtJson::nullObject()
     nonNull.insert(QLatin1String("foo"), QLatin1String("bar"));
 
     QCOMPARE(nullObject, QJsonObject());
+    QCOMPARE(nullObject.size(), 0);
     QVERIFY(nullObject != nonNull);
     QVERIFY(nonNull != nullObject);
 
@@ -1003,8 +1029,27 @@ void tst_QtJson::nullObject()
     QCOMPARE(nullObject.keys(), QStringList());
     nullObject.remove("foo");
     QCOMPARE(nullObject, QJsonObject());
+    QCOMPARE(QJsonValue(nullObject["foo"]), QJsonValue(QJsonValue::Undefined));
     QCOMPARE(nullObject.take("foo"), QJsonValue(QJsonValue::Undefined));
     QCOMPARE(nullObject.contains("foo"), false);
+    QCOMPARE(nullObject, QJsonObject());
+    QCOMPARE(nullObject.size(), 0);
+
+    // There is not way to check if internal temporary storage for QJsonValueRef is removed correctly by
+    // remove, take or compaction but at least we should not crash
+    nullObject["foo"];
+    QCOMPARE(nullObject.size(), 0);
+    nullObject.remove("foo");
+    QCOMPARE(nullObject.size(), 0);
+    nullObject["foo"];
+    QCOMPARE(nullObject.size(), 0);
+    nullObject.take("foo");
+    QCOMPARE(nullObject.size(), 0);
+    QString property("foo");
+    for (int i = 0; i < 128; ++i)
+        nullObject[property + QString::number(i)];
+
+    QCOMPARE(nullObject.size(), 0);
 }
 
 void tst_QtJson::constNullObject()
@@ -1024,6 +1069,16 @@ void tst_QtJson::constNullObject()
     QCOMPARE(nullObject["foo"], QJsonValue(QJsonValue::Undefined));
 }
 
+void tst_QtJson::undefinedKeys()
+{
+    QJsonObject null;
+    QVERIFY(null.keys().isEmpty());
+
+    // check that an internal udefined doesn't show up
+    null["undefined"];
+    QVERIFY(null.keys().isEmpty());
+}
+
 void tst_QtJson::keySorting()
 {
     const char *json = "{ \"B\": true, \"A\": false }";
@@ -1159,6 +1214,11 @@ void tst_QtJson::toVariantMap()
     QVariantMap map = object.toVariantMap();
     QVERIFY(map.isEmpty());
 
+    // check an empty object with an internal undefined
+    QJsonValueRef unused = object["undefined"];
+    Q_UNUSED(unused);
+    QVERIFY(object.toVariantMap().isEmpty());
+
     object.insert("Key", QString("Value"));
     object.insert("null", QJsonValue());
     QJsonArray array;
@@ -2330,6 +2390,70 @@ void tst_QtJson::valueEquals()
     QVERIFY(QJsonValue("\xc3\xa9") == QJsonValue(QString("\xc3\xa9")));
 }
 
+void tst_QtJson::objectEquals_data()
+{
+    QTest::addColumn<QJsonObject>("left");
+    QTest::addColumn<QJsonObject>("right");
+    QTest::addColumn<bool>("result");
+
+    QTest::newRow("two defaults") << QJsonObject() << QJsonObject() << true;
+
+    QJsonObject object1;
+    object1.insert("property", 1);
+    QJsonObject object2;
+    object2["property"] = 1;
+    QJsonObject object3;
+    object3.insert("property1", 1);
+    object3.insert("property2", 2);
+
+    QTest::newRow("the same object (1 vs 2)") << object1 << object2 << true;
+    QTest::newRow("the same object (3 vs 3)") << object3 << object3 << true;
+    QTest::newRow("different objects (2 vs 3)") << object2 << object3 << false;
+    QTest::newRow("object vs default") << object1 << QJsonObject() << false;
+
+    QJsonObject empty;
+    empty.insert("property", 1);
+    empty.take("property");
+    QTest::newRow("default vs empty") << QJsonObject() << empty << true;
+    QTest::newRow("empty vs empty") << empty << empty << true;
+    QTest::newRow("object vs empty") << object1 << empty << false;
+
+    QJsonObject referencedEmpty;
+    referencedEmpty["undefined"];
+    QTest::newRow("referenced empty vs default") << referencedEmpty << QJsonObject() << true;
+    QTest::newRow("referenced empty vs referenced empty") << referencedEmpty << referencedEmpty << true;
+    QTest::newRow("referenced empty vs object") << referencedEmpty << object1 << false;
+
+    QJsonObject referencedObject1;
+    referencedObject1.insert("property", 1);
+    referencedObject1["undefined"];
+    QJsonObject referencedObject2;
+    referencedObject2.insert("property", 1);
+    referencedObject2["aaaaaaaaa"]; // earlier then "property"
+    referencedObject2["zzzzzzzzz"]; // after "property"
+    QTest::newRow("referenced object vs default") << referencedObject1 << QJsonObject() << false;
+    QTest::newRow("referenced object vs referenced object") << referencedObject1 << referencedObject1 << true;
+    QTest::newRow("referenced object vs object (same)") << referencedObject1 << object1 << true;
+    QTest::newRow("referenced object vs object (different)") << referencedObject1 << object3 << false;
+    QTest::newRow("referenced object vs referenced object (same)") << referencedObject1 << referencedObject2 << true;
+}
+
+void tst_QtJson::objectEquals()
+{
+    QFETCH(QJsonObject, left);
+    QFETCH(QJsonObject, right);
+    QFETCH(bool, result);
+
+    QVERIFY((left == right) == result);
+    QVERIFY((right == left) == result);
+
+    // invariants checks
+    QCOMPARE(left, left);
+    QCOMPARE(right, right);
+    QVERIFY((left != right) != result);
+    QVERIFY((right != left) != result);
+}
+
 void tst_QtJson::bom()
 {
     QFile file(testDataDir + "/bom.json");