path: root/src/partition/jsondbobject.cpp

/****************************************************************************
**
** Copyright (C) 2012 Digia Plc and/or its subsidiary(-ies).
** Contact: http://www.qt-project.org/legal
**
** This file is part of the QtAddOn.JsonDb module of the Qt Toolkit.
**
** $QT_BEGIN_LICENSE:LGPL$
** Commercial License Usage
** Licensees holding valid commercial Qt licenses may use this file in
** accordance with the commercial license agreement provided with the
** Software or, alternatively, in accordance with the terms contained in
** a written agreement between you and Digia.  For licensing terms and
** conditions see http://qt.digia.com/licensing.  For further information
** use the contact form at http://qt.digia.com/contact-us.
**
** GNU Lesser General Public License Usage
** Alternatively, this file may be used under the terms of the GNU Lesser
** General Public License version 2.1 as published by the Free Software
** Foundation and appearing in the file LICENSE.LGPL included in the
** packaging of this file.  Please review the following information to
** ensure the GNU Lesser General Public License version 2.1 requirements
** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
**
** In addition, as a special exception, Digia gives you certain additional
** rights.  These rights are described in the Digia Qt LGPL Exception
** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
**
** GNU General Public License Usage
** Alternatively, this file may be used under the terms of the GNU
** General Public License version 3.0 as published by the Free Software
** Foundation and appearing in the file LICENSE.GPL included in the
** packaging of this file.  Please review the following information to
** ensure the GNU General Public License version 3.0 requirements will be
** met: http://www.gnu.org/copyleft/gpl.html.
**
**
** $QT_END_LICENSE$
**
****************************************************************************/

#include "jsondbobject.h"

#include <QJSValue>
#include <QJSValueIterator>
#include <QStringBuilder>
#include <QStringList>
#include <QCryptographicHash>

#include <qjsondocument.h>

#include "jsondbstrings.h"
#include "jsondbproxy.h"

QT_BEGIN_NAMESPACE_JSONDB_PARTITION

JsonDbObject::JsonDbObject()
{
}

JsonDbObject::JsonDbObject(const QJsonObject &object)
    : QJsonObject(object)
{
}

JsonDbObject::~JsonDbObject()
{
}

QByteArray JsonDbObject::toBinaryData() const
{
    return QJsonDocument(*this).toBinaryData();
}

QUuid JsonDbObject::uuid() const
{
    return QUuid(value(JsonDbString::kUuidStr).toString());
}

QString JsonDbObject::version() const
{
    return value(JsonDbString::kVersionStr).toString();
}

QString JsonDbObject::type() const
{
    return value(JsonDbString::kTypeStr).toString();
}

bool JsonDbObject::isDeleted() const
{
    return value(JsonDbString::kDeletedStr).toBool();
}

void JsonDbObject::markDeleted()
{
    insert(JsonDbString::kDeletedStr, true);
}

struct Uuid
{
    uint    data1;
    ushort  data2;
    ushort  data3;
    uchar   data4[8];
};

// copied from src/client/qjsondbobject.cpp:
static const Uuid JsonDbNamespace = {0x6ba7b810, 0x9dad, 0x11d1, { 0x80, 0xb4, 0x00, 0xc0, 0x4f, 0xd4, 0x30, 0xc8} };

/*!
    Returns deterministic uuid that can be used to identify given \a identifier.

    The uuid is generated using QtJsonDb UUID namespace on a value of the
    given \a identifier.

    \sa QJsonDbObject::createUuidFromString(), QJsonDbObject::createUuid()
*/
QUuid JsonDbObject::createUuidFromString(const QString &identifier)
{
    const QUuid ns(JsonDbNamespace.data1, JsonDbNamespace.data2, JsonDbNamespace.data3,
                   JsonDbNamespace.data4[0], JsonDbNamespace.data4[1], JsonDbNamespace.data4[2],
                   JsonDbNamespace.data4[3], JsonDbNamespace.data4[4], JsonDbNamespace.data4[5],
                   JsonDbNamespace.data4[6], JsonDbNamespace.data4[7]);
    return QUuid::createUuidV3(ns, identifier);
}

void JsonDbObject::generateUuid()
{
    const QString idStr(QStringLiteral("_id"));
    if (contains(idStr)) {
        QUuid uuid(createUuidFromString(value(idStr).toString()));
        insert(JsonDbString::kUuidStr, uuid.toString());
    } else {
        QUuid uuid(QUuid::createUuid());
        insert(JsonDbString::kUuidStr, uuid.toString());
    }
}

/*!
 * \brief JsonDbObject::computeVersion mostly for legacy reasons.
 *        Same as calling updateVersionOptimistic(*this, &versionWritten)
 *
 * \sa updateVersionOptimistic(), version()
 * \return the new version, which is also written to the object
 */
QString JsonDbObject::computeVersion(bool trackHistory)
{
    QString versionWritten;
    updateVersionOptimistic(*this, &versionWritten, trackHistory);
    return versionWritten;
}

/*!
 * \brief JsonDbObject::updateVersionOptimistic implement an optimisticWrite
 * \param other the object containing the update to be written. Do NOT call computeVersion()
 *        on the other object before passing it in! other._meta.history is assumed untrusted.
 * \param versionWritten contains the version string of the write upon return
 * \param trackHistory whether version history should be tracked or not. Defaults to true.
 * \return true if the passed object is a valid write. As this version can operate
 *         on conflicts too, version() and versionWritten can differ.
 */
bool JsonDbObject::updateVersionOptimistic(const JsonDbObject &other, QString *versionWrittenOut, bool trackHistory)
{
    QString versionWritten;
    // this is trusted and expected to contain a _meta object with book keeping info
    QJsonObject meta = value(JsonDbString::kMetaStr).toObject();

    // an array of all versions this object has replaced
    QJsonArray history = meta.value(QStringLiteral("history")).toArray();

    // all known conflicts
    QJsonArray conflicts = meta.value(JsonDbString::kConflictsStr).toArray();

    // check for in-object override of history tracking
    if (trackHistory && value(JsonDbString::kLocalStr).toBool())
        trackHistory = false;

    QString replacedVersion = other.version();

    int replacedCount;
    QString replacedHash = tokenizeVersion(replacedVersion, &replacedCount);

    int updateCount = replacedCount;
    QString hash = replacedHash;

    // we don't trust other._meta.history, so other._version must be replacedVersion
    // if other.computeVersion() was called before updateVersionOptimistic(), other can at max be a replay
    // as we lost which version other is replacing.
    bool isReplay = !other.computeVersion(replacedCount, replacedHash, &updateCount, &hash);

    bool isValidWrite = false;

    // first we check if this version can eliminate a conflict
    for (QJsonArray::const_iterator ii = conflicts.begin(); ii < conflicts.end(); ii++) {

        JsonDbObject conflict((*ii).toObject());
        if (conflict.version() == replacedVersion) {
            if (!isReplay)
                conflicts.removeAt(ii.i);
            if (!isValidWrite) {
                addAncestor(&history, updateCount, hash);
                versionWritten = versionAsString(updateCount, hash);
            }
            isValidWrite = true;
        }
    }

    // now we check if this version can progress the head
    if (version().isEmpty() || version() == replacedVersion) {
        if (!isReplay)
            *this = other;
        if (!isValidWrite)
            versionWritten = versionAsString(updateCount, hash);
        insert(JsonDbString::kVersionStr, versionWritten);
        isValidWrite = true;
    }

    // make sure we can resurrect a tombstone
    // Issue: Recreating a _uuid must have a updateCount higher than the tombstone
    //        otherwise it is considered a conflict.
    if (!isValidWrite && isDeleted()) {
        if (!isReplay) {
            addAncestor(&history, replacedCount, replacedHash);
        }

        replacedHash = tokenizeVersion(version(), &replacedCount);
        updateCount = replacedCount + 1;
        versionWritten = versionAsString(updateCount, hash);

        *this = other;
        insert(JsonDbString::kVersionStr, versionWritten);
        isValidWrite = true;
    }

    // update the book keeping of what versions we have replaced in this version branch
    if (isValidWrite && !isReplay) {
        addAncestor(&history, replacedCount, replacedHash);

        meta = QJsonObject();

        if (trackHistory && history.size())
            meta.insert(QStringLiteral("history"), history);
        if (conflicts.size())
            meta.insert(JsonDbString::kConflictsStr, history);

        if (!meta.isEmpty())
            insert(JsonDbString::kMetaStr, meta);
        else
            insert(JsonDbString::kMetaStr, QJsonValue::Undefined);
    }

    // last chance for a valid write: other is a replay from history
    if (!isValidWrite && isAncestorOf(history, updateCount, hash)) {
        isValidWrite = true;
        versionWritten = versionAsString(updateCount, hash);
    }

    if (versionWrittenOut)
        *versionWrittenOut = versionWritten;

    return isValidWrite;
}

/*!
 * \brief JsonDbObject::updateVersionReplicating implements a replicatedWrite
 * \param other the (remote) object to include into this one.
 * \return if the passed object was a valid replication
 */
bool JsonDbObject::updateVersionReplicating(const JsonDbObject &other)
{
    // these two will be the final _meta content
    QJsonArray history;
    QJsonArray conflicts;

    // let's go thru all version, i.e. this, this._conflicts, other, and other._conflicts
    {
        // thanks to the operator <, documents will sort and remove duplicates
        // the value is just for show, QSet is based on QHash, which does not sort
        QMap<JsonDbObject,bool> documents;

        QUuid id;
        if (!isEmpty()) {
            id = uuid();
            populateMerge(&documents, id, *this);
        } else {
            id = other.uuid();
        }
        if (!populateMerge(&documents, id, other, true))
            return false;

        // now we have all versions sorted and duplicates removed
        // let's figure out what to keep, what to toss
        // this is O(n^2) but should be fine in real world situations
        for (QMap<JsonDbObject,bool>::const_iterator ii = documents.begin(); ii != documents.end(); ii++) {
            bool alive = !ii.key().isDeleted();
            for (QMap<JsonDbObject,bool>::const_iterator jj = ii + 1; alive && jj != documents.end(); jj++)
                if (ii.key().isAncestorOf(jj.key()))
                    alive = false;

            if (ii+1 == documents.end()) {
                // last element, so found the winner,
                // assigning to *this, which is head
                *this = ii.key();
                populateHistory(&history, *this, false);
            } else if (alive) {
                // this is a conflict, strip _meta and keep it
                JsonDbObject conflict(ii.key());
                conflict.remove(JsonDbString::kMetaStr);
                conflicts.append(conflict);
            } else {
                // this version was replaced, just keep history
                populateHistory(&history, ii.key(), true);
            }
        }
    }

    // let's write a new _meta into head
    if (history.size() || conflicts.size()) {
        QJsonObject meta;
        if (history.size())
            meta.insert(QStringLiteral("history"), history);
        if (conflicts.size())
            meta.insert(JsonDbString::kConflictsStr, conflicts);
        insert(JsonDbString::kMetaStr, meta);
    } else {
        // this is really just for sanity reason, but it feels better to have it
        // aka: this branch should never be reached in real world situations
        remove(JsonDbString::kMetaStr);
    }

    return true;
}

bool JsonDbObject::populateMerge(QMap<JsonDbObject,bool> *documents, const QUuid &id, const JsonDbObject &source, bool validateSource, bool recurse) const
{
    // is this the same uuid?
    bool valid = source.uuid() == id;

    if (valid && validateSource) {
        // validate that the version is actually correct
        int count;
        QString hash = tokenizeVersion(source.version(), &count);
        if (count == 0 || source.computeVersion(count, hash, 0, 0))
            valid = false;
    }

    // there is source._meta.conflicts to explore
    if (recurse && source.contains(JsonDbString::kMetaStr)) {
        QJsonArray conflicts = source.value(JsonDbString::kMetaStr).toObject().value(JsonDbString::kConflictsStr).toArray();
        for (int ii = 0; ii < conflicts.size(); ii++)
            if (!populateMerge(documents, id, conflicts.at(ii).toObject(), validateSource, false))
                valid = false;
    }

    if (valid && documents)
        documents->insert(source,true);

    return valid;
}

void JsonDbObject::populateHistory(QJsonArray *history, const JsonDbObject &doc, bool includeCurrent) const
{
    QJsonArray versions = doc.value(JsonDbString::kMetaStr).toObject().value(QStringLiteral("history")).toArray();

    for (int ii = 0; ii < versions.size(); ii++) {
        QJsonValue hash = versions.at(ii);
        if (hash.isString()) {
            addAncestor(history, ii + 1, hash.toString());
        } else if (hash.isArray()) {
            QJsonArray hashArray = hash.toArray();
            for (QJsonArray::const_iterator jj = hashArray.begin(); jj != hashArray.end(); jj++) {
                if ((*jj).isString())
                    addAncestor(history, ii + 1, (*jj).toString());
            }
        }
    }

    if (includeCurrent) {
        int updateCount;
        QString hash = tokenizeVersion(doc.version(), &updateCount);
        addAncestor(history, updateCount, hash);
    }
}

QString JsonDbObject::tokenizeVersion(const QString &versionIn, int *updateCountOut) const
{
    int updateCount;
    QString hash;

    if (versionIn.isEmpty()) {
        updateCount = 0;
    } else {
        QStringList splitUp = versionIn.split(QLatin1Char('-'));
        if (splitUp.size() == 2) {
            updateCount = qMax(1, splitUp.at(0).toInt());
            hash = splitUp.at(1);
        } else {
            updateCount = 1;
            hash = versionIn;
        }
    }

    if (updateCountOut)
        *updateCountOut = updateCount;

    return hash;
}

QString JsonDbObject::versionAsString(const int updateCount, const QString &hash) const
{
    return QString::number(updateCount) % QStringLiteral("-") % hash;
}


bool JsonDbObject::computeVersion(const int oldUpdateCount, const QString& oldHash, int *newUpdateCount, QString *newHash) const
{
    QCryptographicHash md5(QCryptographicHash::Md5);

    for (const_iterator ii = begin(); ii != end(); ii++) {
        QString key = ii.key();
        if (key == JsonDbString::kUuidStr || key == JsonDbString::kVersionStr || key == JsonDbString::kMetaStr)
            continue;

        md5.addData((char *) key.constData(), key.size() * 2);

        char kar = ii.value().type();
        md5.addData((char *) &kar, 1);

        switch (ii.value().type()) {
        case QJsonValue::Bool:
            kar = ii.value().toBool() ? '1' : '0';
            md5.addData((char *) &kar, 1);
            break;
        case QJsonValue::Double: {
            double value = ii.value().toDouble();
            md5.addData((char *) &value, sizeof(double));
            break;
        }
        case QJsonValue::String: {
            QString value = ii.value().toString();
            md5.addData((char *) value.constData(), value.size() * 2);
            break;
        }
        case QJsonValue::Array: {
            QJsonDocument doc(ii.value().toArray());
            int size;
            const char *data = doc.rawData(&size);
            md5.addData(data, size);
            break;
        }
        case QJsonValue::Object: {
            QJsonDocument doc(ii.value().toObject());
            int size;
            const char *data = doc.rawData(&size);
            md5.addData(data, size);
            break;
        }
        default:;
            // do nothing
        }
    }

    QString computedHash = QString::fromLatin1(md5.result().toHex().constData(), 10);

    if (computedHash != oldHash) {
        if (newUpdateCount)
            *newUpdateCount = oldUpdateCount + 1;
        if (newHash)
            *newHash = computedHash;
        return true;
    }

    return false;
}

/*!
 * \brief JsonDbObject::isAncestorOf tests if this JsonDbObject contains an ancestor version
 *        of the passed JsonDbObject. It does NOT take _uuid into account, it works on version()
 *        only.
 *
 *        For this method to return a valid answer, the passed object needs to have an intact
 *        _meta object.
 *
 * \param other the object to check ancestorship
 * \return true if this object is an ancestor version of the passed object
 */
bool JsonDbObject::isAncestorOf(const JsonDbObject &other) const
{
    QJsonArray history = other.value(JsonDbString::kMetaStr).toObject().value(QStringLiteral("history")).toArray();

    int updateCount;
    QString hash = tokenizeVersion(version(), &updateCount);

    return isAncestorOf(history, updateCount, hash);
}

bool JsonDbObject::isAncestorOf(const QJsonArray &history, const int updateCount, const QString &hash) const
{
    if (updateCount < 1 || history.size() < updateCount)
        return false;

    QJsonValue knownHashes = history.at(updateCount - 1);
    if (knownHashes.isString())
        return knownHashes.toString() == hash;
    else if (knownHashes.isArray())
        return knownHashes.toArray().contains(hash);
    else
        return false;
}

void JsonDbObject::addAncestor(QJsonArray *history, const int updateCount, const QString &hash) const
{
    if (updateCount < 1 || !history)
        return;

    int pos = updateCount - 1;
    for (int ii = history->size(); ii < updateCount; ii++)
        history->append(QJsonValue::Null);

    QJsonValue old = history->at(pos);
    if (old.isArray()) {
        QJsonArray multi = old.toArray();
        for (int ii = multi.size(); ii-- > 0;) {
            QString oldHash = multi.at(ii).toString();
            if (oldHash == hash) {
                return;
            } else if (oldHash < hash) {
                multi.insert(ii + 1, hash);
                history->replace(pos, multi);
                return;
            }
        }
        multi.prepend(hash);
        history->replace(pos, multi);
    } else if (!old.isString()) {
        history->replace(pos, hash);
    } else {
        QString oldHash = old.toString();
        if (oldHash == hash)
            return;

        QJsonArray multi;
        if (oldHash < hash) {
            multi.append(oldHash);
            multi.append(hash);
        } else if (oldHash > hash) {
            multi.append(hash);
            multi.append(oldHash);
        }
        history->replace(pos, multi);
    }
}

/*!
 * \brief JsonDbObject::operator < only operates based on version number.
 *        Versions are sorted by update count first, then by string comparing
 *        the hash. This operator does NOT sort by _uuid.
 *
 * \sa computeVersion(), version()
 * \param other the JsonDbObject to compare it to.
 * \return bool when left side is considered to be an early version
 */
bool JsonDbObject::operator <(const JsonDbObject &other) const
{
    int myCount;
    QString myHash = tokenizeVersion(version(), &myCount);
    int otherCount;
    QString otherHash = tokenizeVersion(other.version(), &otherCount);

    if (myCount != otherCount)
        return myCount < otherCount;

    return myHash < otherHash;
}

QJsonValue JsonDbObject::valueByPath(const QString &path) const
{
    return valueByPath(path.split(QLatin1Char('.')));
}

QJsonValue JsonDbObject::valueByPath(const QStringList &path) const
{
    Q_ASSERT(!path.isEmpty());
    if (path.size() == 0)
        return QJsonValue(QJsonValue::Undefined);
    if (path.size() == 1)
        return value(path.at(0));
    QJsonValue value(*this);
    for (int i = 0; i < path.size(); ++i) {
        const QString &key = path.at(i);
        // this part of the property is a list
        if (value.isArray()) {
            QJsonArray objectList = value.toArray();
            bool ok = false;
            int index = key.toInt(&ok);
            if (!ok || index < 0 || index >= objectList.size())
                return QJsonValue(QJsonValue::Undefined);
            value = objectList.at(index);
        } else if (value.isObject()) {
            value = value.toObject().value(key);
        } else {
            return QJsonValue(QJsonValue::Undefined);
        }
    }
    return value;
}

QT_END_NAMESPACE_JSONDB_PARTITION