Implement ranged queries

Summary:
Notes:

- For now, only for QDateTime indexes
- Invalid QDateTimes are stored in the index (subject to change)
- Should be a drop-in replacement from ValueIndexes (except for `In` and `Contains` queries)

Reviewers: cmollekopf

Tags: #sink

Differential Revision: https://phabricator.kde.org/D13105

9 files changed, 274 insertions, 21 deletions

diff --git a/common/domain/typeimplementations.cpp b/common/domain/typeimplementations.cpp
index e65c998..a8f4baf 100644
--- a/common/domain/typeimplementations.cpp
+++ b/common/domain/typeimplementations.cpp
@@ -38,7 +38,7 @@ using namespace Sink::ApplicationDomain;
     MAPPER.addMapping<ENTITYTYPE::PROPERTY, Sink::ApplicationDomain::Buffer::ENTITYTYPE, Sink::ApplicationDomain::Buffer::ENTITYTYPE##Builder>(&Sink::ApplicationDomain::Buffer::ENTITYTYPE::LOWERCASEPROPERTY, &Sink::ApplicationDomain::Buffer::ENTITYTYPE##Builder::add_##LOWERCASEPROPERTY);
 
 typedef IndexConfig<Mail,
-        ValueIndex<Mail::Date>,
+        SortedIndex<Mail::Date>,
         ValueIndex<Mail::Folder>,
         ValueIndex<Mail::ParentMessageId>,
         ValueIndex<Mail::MessageId>,
@@ -64,7 +64,8 @@ typedef IndexConfig<Addressbook,
     > AddressbookIndexConfig;
 
 typedef IndexConfig<Event,
-        ValueIndex<Event::Uid>
+        ValueIndex<Event::Uid>,
+        SortedIndex<Event::StartTime>
     > EventIndexConfig;
 
 typedef IndexConfig<Todo,
diff --git a/common/domain/typeimplementations_p.h b/common/domain/typeimplementations_p.h
index 6f77a2d..fc08048 100644
--- a/common/domain/typeimplementations_p.h
+++ b/common/domain/typeimplementations_p.h
@@ -62,7 +62,7 @@ public:
 };
 
 
-template <typename Property, typename SortProperty>
+template <typename Property, typename SortProperty = void>
 class SortedIndex
 {
 public:
@@ -78,6 +78,22 @@ public:
     }
 };
 
+template <typename SortProperty>
+class SortedIndex<SortProperty, void>
+{
+public:
+    static void configure(TypeIndex &index)
+    {
+        index.addSortedProperty<SortProperty>();
+    }
+
+    template <typename EntityType>
+    static QMap<QByteArray, int> databases()
+    {
+        return {{QByteArray{EntityType::name} +".index." + SortProperty::name + ".sorted", 1}};
+    }
+};
+
 template <typename Property, typename SecondaryProperty>
 class SecondaryIndex
 {
diff --git a/common/index.cpp b/common/index.cpp
index ff87ae2..94b2eea 100644
--- a/common/index.cpp
+++ b/common/index.cpp
@@ -59,3 +59,17 @@ QByteArray Index::lookup(const QByteArray &key)
     lookup(key, [&](const QByteArray &value) { result = QByteArray(value.constData(), value.size()); }, [](const Index::Error &) { });
     return result;
 }
+
+void Index::rangeLookup(const QByteArray &lowerBound, const QByteArray &upperBound,
+        const std::function<void(const QByteArray &value)> &resultHandler,
+        const std::function<void(const Error &error)> &errorHandler)
+{
+    mDb.findAllInRange(lowerBound, upperBound,
+            [&](const QByteArray &key, const QByteArray &value) {
+                resultHandler(value);
+            },
+            [&](const Sink::Storage::DataStore::Error &error) {
+                SinkWarningCtx(mLogCtx) << "Error while retrieving value:" << error << mName;
+                errorHandler(Error(error.store, error.code, error.message));
+            });
+}
diff --git a/common/index.h b/common/index.h
index f16a426..043cc90 100644
--- a/common/index.h
+++ b/common/index.h
@@ -40,6 +40,10 @@ public:
         bool matchSubStringKeys = false);
     QByteArray lookup(const QByteArray &key);
 
+    void rangeLookup(const QByteArray &lowerBound, const QByteArray &upperBound,
+        const std::function<void(const QByteArray &value)> &resultHandler,
+        const std::function<void(const Error &error)> &errorHandler);
+
 private:
     Q_DISABLE_COPY(Index);
     Sink::Storage::DataStore::Transaction mTransaction;
diff --git a/common/query.cpp b/common/query.cpp
index 5f6d095..404a304 100644
--- a/common/query.cpp
+++ b/common/query.cpp
@@ -132,8 +132,8 @@ bool QueryBase::Filter::operator==(const QueryBase::Filter &other) const
 
 bool QueryBase::operator==(const QueryBase &other) const
 {
-    auto ret = mType == other.mType 
-        && mSortProperty == other.mSortProperty 
+    auto ret = mType == other.mType
+        && mSortProperty == other.mSortProperty
         && mBaseFilterStage == other.mBaseFilterStage;
     return ret;
 }
@@ -171,6 +171,14 @@ bool QueryBase::Comparator::matches(const QVariant &v) const
                 return false;
             }
             return value.value<QByteArrayList>().contains(v.toByteArray());
+        case Within: {
+            auto range = value.value<QList<QVariant>>();
+            if (range.size() < 2) {
+                return false;
+            }
+
+            return range[0] <= v && v <= range[1];
+        }
         case Fulltext:
         case Invalid:
         default:
diff --git a/common/query.h b/common/query.h
index f0c1e01..7130116 100644
--- a/common/query.h
+++ b/common/query.h
@@ -36,6 +36,7 @@ public:
             Equals,
             Contains,
             In,
+            Within,
             Fulltext
         };
 
diff --git a/common/typeindex.cpp b/common/typeindex.cpp
index 180343a..589b770 100644
--- a/common/typeindex.cpp
+++ b/common/typeindex.cpp
@@ -21,9 +21,12 @@
 #include "log.h"
 #include "index.h"
 #include "fulltextindex.h"
+
 #include <QDateTime>
 #include <QDataStream>
 
+#include <cmath>
+
 using namespace Sink;
 
 static QByteArray getByteArray(const QVariant &value)
@@ -50,15 +53,34 @@ static QByteArray getByteArray(const QVariant &value)
     return "toplevel";
 }
 
-static QByteArray toSortableByteArray(const QDateTime &date)
+
+static QByteArray toSortableByteArrayImpl(const QDateTime &date)
 {
     // Sort invalid last
     if (!date.isValid()) {
         return QByteArray::number(std::numeric_limits<unsigned int>::max());
     }
-    return QByteArray::number(std::numeric_limits<unsigned int>::max() - date.toTime_t());
+    static unsigned int uint_num_digits = std::log10(std::numeric_limits<unsigned int>::max()) + 1;
+    return QByteArray::number(std::numeric_limits<unsigned int>::max() - date.toTime_t()).rightJustified(uint_num_digits, '0');
 }
 
+static QByteArray toSortableByteArray(const QVariant &value)
+{
+    if (!value.isValid()) {
+        // FIXME: we don't know the type, so we don't know what to return
+        // This mean we're fixing every sorted index keys to use unsigned int
+        return QByteArray::number(std::numeric_limits<unsigned int>::max());
+    }
+
+    switch (value.type()) {
+        case QMetaType::QDateTime:
+            return toSortableByteArrayImpl(value.toDateTime());
+        default:
+            SinkWarning() << "Not knowing how to convert a" << value.typeName()
+                          << "to a sortable key, falling back to default conversion";
+            return getByteArray(value);
+    }
+}
 
 TypeIndex::TypeIndex(const QByteArray &type, const Sink::Log::Context &ctx) : mLogCtx(ctx), mType(type)
 {
@@ -72,6 +94,11 @@ QByteArray TypeIndex::indexName(const QByteArray &property, const QByteArray &so
     return mType + ".index." + property + ".sort." + sortProperty;
 }
 
+QByteArray TypeIndex::sortedIndexName(const QByteArray &property) const
+{
+    return mType + ".index." + property + ".sorted";
+}
+
 template <>
 void TypeIndex::addProperty<QByteArray>(const QByteArray &property)
 {
@@ -138,6 +165,22 @@ void TypeIndex::addProperty<ApplicationDomain::Reference>(const QByteArray &prop
 }
 
 template <>
+void TypeIndex::addSortedProperty<QDateTime>(const QByteArray &property)
+{
+    auto indexer = [this, property](bool add, const QByteArray &identifier, const QVariant &value,
+                       Sink::Storage::DataStore::Transaction &transaction) {
+        const auto sortableDate = toSortableByteArray(value);
+        if (add) {
+            Index(sortedIndexName(property), transaction).add(sortableDate, identifier);
+        } else {
+            Index(sortedIndexName(property), transaction).remove(sortableDate, identifier);
+        }
+    };
+    mSortIndexer.insert(property, indexer);
+    mSortedProperties << property;
+}
+
+template <>
 void TypeIndex::addPropertyWithSorting<QByteArray, QDateTime>(const QByteArray &property, const QByteArray &sortProperty)
 {
     auto indexer = [=](bool add, const QByteArray &identifier, const QVariant &value, const QVariant &sortValue, Sink::Storage::DataStore::Transaction &transaction) {
@@ -149,8 +192,8 @@ void TypeIndex::addPropertyWithSorting<QByteArray, QDateTime>(const QByteArray &
             Index(indexName(property, sortProperty), transaction).remove(propertyValue + toSortableByteArray(date), identifier);
         }
     };
-    mSortIndexer.insert(property + sortProperty, indexer);
-    mSortedProperties.insert(property, sortProperty);
+    mGroupedSortIndexer.insert(property + sortProperty, indexer);
+    mGroupedSortedProperties.insert(property, sortProperty);
 }
 
 template <>
@@ -166,10 +209,15 @@ void TypeIndex::updateIndex(bool add, const QByteArray &identifier, const Sink::
         auto indexer = mIndexer.value(property);
         indexer(add, identifier, value, transaction);
     }
-    for (auto it = mSortedProperties.constBegin(); it != mSortedProperties.constEnd(); it++) {
+    for (const auto &property : mSortedProperties) {
+        const auto value = entity.getProperty(property);
+        auto indexer = mSortIndexer.value(property);
+        indexer(add, identifier, value, transaction);
+    }
+    for (auto it = mGroupedSortedProperties.constBegin(); it != mGroupedSortedProperties.constEnd(); it++) {
         const auto value = entity.getProperty(it.key());
         const auto sortValue = entity.getProperty(it.value());
-        auto indexer = mSortIndexer.value(it.key() + it.value());
+        auto indexer = mGroupedSortIndexer.value(it.key() + it.value());
         indexer(add, identifier, value, sortValue, transaction);
     }
     for (const auto &indexer : mCustomIndexer) {
@@ -207,22 +255,60 @@ void TypeIndex::remove(const QByteArray &identifier, const Sink::ApplicationDoma
     updateIndex(false, identifier, entity, transaction, resourceInstanceId);
 }
 
-static QVector<QByteArray> indexLookup(Index &index, QueryBase::Comparator filter)
+static QVector<QByteArray> indexLookup(Index &index, QueryBase::Comparator filter,
+    std::function<QByteArray(const QVariant &)> valueToKey = getByteArray)
 {
     QVector<QByteArray> keys;
     QByteArrayList lookupKeys;
     if (filter.comparator == Query::Comparator::Equals) {
-        lookupKeys << getByteArray(filter.value);
+        lookupKeys << valueToKey(filter.value);
     } else if (filter.comparator == Query::Comparator::In) {
-        lookupKeys = filter.value.value<QByteArrayList>();
+        for(const QVariant &value : filter.value.value<QVariantList>()) {
+            lookupKeys << valueToKey(value);
+        }
     } else {
         Q_ASSERT(false);
     }
 
     for (const auto &lookupKey : lookupKeys) {
         index.lookup(lookupKey, [&](const QByteArray &value) { keys << value; },
-            [lookupKey](const Index::Error &error) { SinkWarning() << "Lookup error in index: " << error.message << lookupKey; }, true);
+            [lookupKey](const Index::Error &error) {
+                SinkWarning() << "Lookup error in index: " << error.message << lookupKey;
+            },
+            true);
+    }
+    return keys;
+}
+
+static QVector<QByteArray> sortedIndexLookup(Index &index, QueryBase::Comparator filter)
+{
+    if (filter.comparator == Query::Comparator::In || filter.comparator == Query::Comparator::Contains) {
+        SinkWarning() << "In and Contains comparison not supported on sorted indexes";
+    }
+
+    if (filter.comparator != Query::Comparator::Within) {
+        return indexLookup(index, filter, toSortableByteArray);
+    }
+
+    QVector<QByteArray> keys;
+
+    QByteArray lowerBound, upperBound;
+    auto bounds = filter.value.value<QVariantList>();
+    if (bounds[0].canConvert<QDateTime>()) {
+        // Inverse the bounds because dates are stored newest first
+        upperBound = toSortableByteArray(bounds[0].toDateTime());
+        lowerBound = toSortableByteArray(bounds[1].toDateTime());
+    } else {
+        lowerBound = bounds[0].toByteArray();
+        upperBound = bounds[1].toByteArray();
     }
+
+    index.rangeLookup(lowerBound, upperBound, [&](const QByteArray &value) { keys << value; },
+        [bounds](const Index::Error &error) {
+            SinkWarning() << "Lookup error in index:" << error.message
+                          << "with bounds:" << bounds[0] << bounds[1];
+        });
+
     return keys;
 }
 
@@ -239,16 +325,27 @@ QVector<QByteArray> TypeIndex::query(const Sink::QueryBase &query, QSet<QByteArr
         }
     }
 
-    for (auto it = mSortedProperties.constBegin(); it != mSortedProperties.constEnd(); it++) {
+    for (auto it = mGroupedSortedProperties.constBegin(); it != mGroupedSortedProperties.constEnd(); it++) {
         if (query.hasFilter(it.key()) && query.sortProperty() == it.value()) {
             Index index(indexName(it.key(), it.value()), transaction);
             const auto keys = indexLookup(index, query.getFilter(it.key()));
             appliedFilters << it.key();
             appliedSorting = it.value();
-            SinkTraceCtx(mLogCtx) << "Sorted index lookup on " << it.key() << it.value() << " found " << keys.size() << " keys.";
+            SinkTraceCtx(mLogCtx) << "Grouped sorted index lookup on " << it.key() << it.value() << " found " << keys.size() << " keys.";
             return keys;
         }
     }
+
+    for (const auto &property : mSortedProperties) {
+        if (query.hasFilter(property)) {
+            Index index(sortedIndexName(property), transaction);
+            const auto keys = sortedIndexLookup(index, query.getFilter(property));
+            appliedFilters << property;
+            SinkTraceCtx(mLogCtx) << "Sorted index lookup on " << property << " found " << keys.size() << " keys.";
+            return keys;
+        }
+    }
+
     for (const auto &property : mProperties) {
         if (query.hasFilter(property)) {
             Index index(indexName(property), transaction);
diff --git a/common/typeindex.h b/common/typeindex.h
index b8b4d52..793dc1e 100644
--- a/common/typeindex.h
+++ b/common/typeindex.h
@@ -38,6 +38,8 @@ public:
 
     template <typename T>
     void addProperty(const QByteArray &property);
+    template <typename T>
+    void addSortedProperty(const QByteArray &property);
     template <typename T, typename S>
     void addPropertyWithSorting(const QByteArray &property, const QByteArray &sortProperty);
 
@@ -54,9 +56,9 @@ public:
     }
 
     template <typename T>
-    void addPropertyWithSorting()
+    void addSortedProperty()
     {
-        addPropertyWithSorting<typename T::Type>(T::name);
+        addSortedProperty<typename T::Type>(T::name);
     }
 
     template <typename Left, typename Right>
@@ -112,14 +114,17 @@ private:
     friend class Sink::Storage::EntityStore;
     void updateIndex(bool add, const QByteArray &identifier, const Sink::ApplicationDomain::ApplicationDomainType &entity, Sink::Storage::DataStore::Transaction &transaction, const QByteArray &resourceInstanceId);
     QByteArray indexName(const QByteArray &property, const QByteArray &sortProperty = QByteArray()) const;
+    QByteArray sortedIndexName(const QByteArray &property) const;
     Sink::Log::Context mLogCtx;
     QByteArray mType;
     QByteArrayList mProperties;
-    QMap<QByteArray, QByteArray> mSortedProperties;
+    QByteArrayList mSortedProperties;
+    QMap<QByteArray, QByteArray> mGroupedSortedProperties;
     //<Property, ResultProperty>
     QMap<QByteArray, QByteArray> mSecondaryProperties;
     QList<Sink::Indexer::Ptr> mCustomIndexer;
     Sink::Storage::DataStore::Transaction *mTransaction;
     QHash<QByteArray, std::function<void(bool, const QByteArray &identifier, const QVariant &value, Sink::Storage::DataStore::Transaction &transaction)>> mIndexer;
-    QHash<QByteArray, std::function<void(bool, const QByteArray &identifier, const QVariant &value, const QVariant &sortValue, Sink::Storage::DataStore::Transaction &transaction)>> mSortIndexer;
+    QHash<QByteArray, std::function<void(bool, const QByteArray &identifier, const QVariant &value, Sink::Storage::DataStore::Transaction &transaction)>> mSortIndexer;
+    QHash<QByteArray, std::function<void(bool, const QByteArray &identifier, const QVariant &value, const QVariant &sortValue, Sink::Storage::DataStore::Transaction &transaction)>> mGroupedSortIndexer;
 };
diff --git a/tests/querytest.cpp b/tests/querytest.cpp
index fa016a2..36b6e90 100644
--- a/tests/querytest.cpp
+++ b/tests/querytest.cpp
@@ -1510,6 +1510,113 @@ private slots:
         }
     }
 
+    void mailsWithDates()
+    {
+        {
+            Mail mail("sink.dummy.instance1");
+            mail.setExtractedDate(QDateTime::fromString("2018-05-23T13:49:41Z", Qt::ISODate));
+            mail.setExtractedMessageId("message1");
+            VERIFYEXEC(Sink::Store::create<Mail>(mail));
+        }
+        {
+            Mail mail("sink.dummy.instance1");
+            mail.setExtractedDate(QDateTime::fromString("2018-05-23T13:50:00Z", Qt::ISODate));
+            mail.setExtractedMessageId("message2");
+            VERIFYEXEC(Sink::Store::create<Mail>(mail));
+        }
+        {
+            Mail mail("sink.dummy.instance1");
+            mail.setExtractedDate(QDateTime::fromString("2018-05-27T13:50:00Z", Qt::ISODate));
+            mail.setExtractedMessageId("message3");
+            VERIFYEXEC(Sink::Store::create<Mail>(mail));
+        }
+        {
+            Mail mail("sink.dummy.instance1");
+            mail.setExtractedMessageId("message4");
+            VERIFYEXEC(Sink::Store::create<Mail>(mail));
+        }
+        {
+            Mail mail("sink.dummy.instance1");
+            mail.setExtractedDate(QDateTime::fromString("2078-05-23T13:49:41Z", Qt::ISODate));
+            mail.setExtractedMessageId("message5");
+            VERIFYEXEC(Sink::Store::create<Mail>(mail));
+        }
+        VERIFYEXEC(Sink::ResourceControl::flushMessageQueue("sink.dummy.instance1"));
+    }
+
+    void testMailDate()
+    {
+        mailsWithDates();
+
+        {
+            Sink::Query query;
+            query.resourceFilter("sink.dummy.instance1");
+            query.filter<Mail::Date>(QDateTime::fromString("2018-05-23T13:49:41Z", Qt::ISODate));
+            auto model = Sink::Store::loadModel<Mail>(query);
+            QTRY_VERIFY(model->data(QModelIndex(), Sink::Store::ChildrenFetchedRole).toBool());
+            QCOMPARE(model->rowCount(), 1);
+        }
+
+        {
+            Sink::Query query;
+            query.resourceFilter("sink.dummy.instance1");
+            query.filter<Mail::Date>(QDateTime::fromString("2018-05-27T13:49:41Z", Qt::ISODate));
+            auto model = Sink::Store::loadModel<Mail>(query);
+            QTRY_VERIFY(model->data(QModelIndex(), Sink::Store::ChildrenFetchedRole).toBool());
+            QCOMPARE(model->rowCount(), 0);
+        }
+
+        {
+            Sink::Query query;
+            query.resourceFilter("sink.dummy.instance1");
+            query.filter<Mail::Date>(QDateTime::fromString("2018-05-27T13:50:00Z", Qt::ISODate));
+            auto model = Sink::Store::loadModel<Mail>(query);
+            QTRY_VERIFY(model->data(QModelIndex(), Sink::Store::ChildrenFetchedRole).toBool());
+            QCOMPARE(model->rowCount(), 1);
+        }
+
+    }
+
+    void testMailRange()
+    {
+        mailsWithDates();
+
+        {
+            Sink::Query query;
+            query.resourceFilter("sink.dummy.instance1");
+            query.filter<Mail::Date>(QueryBase::Comparator(QVariantList{QDateTime::fromString("2018-05-23T13:49:41Z", Qt::ISODate), QDateTime::fromString("2018-05-23T13:49:41Z", Qt::ISODate)}, QueryBase::Comparator::Within));
+            auto model = Sink::Store::loadModel<Mail>(query);
+            QTRY_VERIFY(model->data(QModelIndex(), Sink::Store::ChildrenFetchedRole).toBool());
+            QCOMPARE(model->rowCount(), 1);
+        }
+
+        {
+            Sink::Query query;
+            query.resourceFilter("sink.dummy.instance1");
+            query.filter<Mail::Date>(QueryBase::Comparator(QVariantList{QDateTime::fromString("2018-05-22T13:49:41Z", Qt::ISODate), QDateTime::fromString("2018-05-25T13:49:41Z", Qt::ISODate)}, QueryBase::Comparator::Within));
+            auto model = Sink::Store::loadModel<Mail>(query);
+            QTRY_VERIFY(model->data(QModelIndex(), Sink::Store::ChildrenFetchedRole).toBool());
+            QCOMPARE(model->rowCount(), 2);
+        }
+
+        {
+            Sink::Query query;
+            query.resourceFilter("sink.dummy.instance1");
+            query.filter<Mail::Date>(QueryBase::Comparator(QVariantList{QDateTime::fromString("2018-05-22T13:49:41Z", Qt::ISODate), QDateTime::fromString("2018-05-30T13:49:41Z", Qt::ISODate)}, QueryBase::Comparator::Within));
+            auto model = Sink::Store::loadModel<Mail>(query);
+            QTRY_VERIFY(model->data(QModelIndex(), Sink::Store::ChildrenFetchedRole).toBool());
+            QCOMPARE(model->rowCount(), 3);
+        }
+
+        {
+            Sink::Query query;
+            query.resourceFilter("sink.dummy.instance1");
+            query.filter<Mail::Date>(QueryBase::Comparator(QVariantList{QDateTime::fromString("2018-05-22T13:49:41Z", Qt::ISODate), QDateTime::fromString("2118-05-30T13:49:41Z", Qt::ISODate)}, QueryBase::Comparator::Within));
+            auto model = Sink::Store::loadModel<Mail>(query);
+            QTRY_VERIFY(model->data(QModelIndex(), Sink::Store::ChildrenFetchedRole).toBool());
+            QCOMPARE(model->rowCount(), 4);
+        }
+    }
 };
 
 QTEST_MAIN(QueryTest)