// Copyright (C) 2021 The Qt Company Ltd.
// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only

#include "qndeffilter.h"
#include "qndefmessage.h"

#include <QtCore/QList>
#include <QtCore/QMap>

QT_BEGIN_NAMESPACE

/*!
    \class QNdefFilter
    \brief The QNdefFilter class provides a filter for matching NDEF messages.

    \ingroup connectivity-nfc
    \inmodule QtNfc
    \since 5.2

    The QNdefFilter encapsulates the structure of an NDEF message and is used for
    matching messages that have a particular structure.

    The following filter matches NDEF messages that contain a single smart poster record:

    \code
    QNdefFilter filter;
    filter.append(QNdefRecord::NfcRtd, "Sp");
    \endcode

    The following filter matches NDEF messages that contain a URI, a localized piece of text and an
    optional JPEG image.  The order of the records must be in the order specified:

    \code
    QNdefFilter filter;
    filter.setOrderMatch(true);
    filter.appendRecord(QNdefRecord::NfcRtd, "U");
    filter.appendRecord<QNdefNfcTextRecord>();
    filter.appendRecord(QNdefRecord::Mime, "image/jpeg", 0, 1);
    \endcode

    The \l match() method can be used to check if a message matches the filter.

    \section1 Matching Algorithms

    The filter behavior depends on the value of \l orderMatch() parameter.

    \note In the discussion below we will consider the filter records to be
    equal if their \c typeNameFormat and \c type parameters match. Joining
    two records means adding their \c minimum and \c maximum values,
    respectively.

    \section2 Unordered Matching

    If the record order is not taken into account, all the equal records in the
    filter can be joined. The resulting filter will contain only unique records,
    each with the updated \c minimum and \c maximum value.

    Consider the following example:

    \code
    QNdefFilter filter;
    filter.appendRecord<QNdefNfcTextRecord>(0, 1);
    filter.appendRecord<QNdefNfcTextRecord>(0, 1);
    filter.appendRecord(QNdefRecord::Mime, "", 1, 1);
    filter.appendRecord<QNdefNfcTextRecord>(1, 1);
    filter.setOrderMatch(false);
    \endcode

    With the unordered matching, the filter will be simplified to the following:

    \code
    QNdefFilter filter;
    filter.appendRecord<QNdefNfcTextRecord>(1, 3);
    filter.appendRecord(QNdefRecord::Mime, "", 1, 1);
    filter.setOrderMatch(false);
    \endcode

    Once the filter contains only the unique records, the matching algorithm
    iterates through the message and calculates the actual amount of records of
    each type. If all the actual amounts fit in the corresponding
    [minimum, maximum] ranges, the matching algorithm returns \c true.

    \section2 Ordered Matching

    If the record order is important, a different approach is applied. In this
    case the equal records can't be simply joined together. However, the
    consecutive equal records can still be joined. Then, the matching
    algorithm iterates through the message, this time also taking the positions
    of the records into account.

    \section2 Handling Empty Type in Filter Record

    It's possible to add a filter record with an empty \c type. In this case
    the empty type will act as a wildcard for any type.

    For example, the filter can be defined as follows:

    \code
    QNdefFilter filter;
    filter.addRecord(QNdefRecord::Mime, "", 1, 1);
    \endcode

    This filter specifies that the message must contain exactly one NDEF record
    with \l {QNdefRecord::}{Mime} \l {QNdefRecord::}{typeNameFormat}(), and any
    \l {QNdefRecord::}{type}().

    \section2 Handling Extra Records in the Message

    If the message contains some records that do not match \e any record in the
    filter, the matching algorithm will return \c false.

    \section2 Filter Examples

    In the table below, each filter record is specified by the following
    parameters (in the given order):

    \list
    \li \c typeNameFormat - contains the \l {QNdefRecord::}{typeNameFormat}() of
    the record.
    \li \c type - contains the \l {QNdefRecord::}{type}() of the record.
    \li \c minimum - contains the minimum amount of occurrences of the record
    in the message.
    \li \c maximum - contains the maximum amount of occurrences of the record
    in the message.
    \endlist

    The filter contains multiple records.

    The message consists of multiple \l {QNdefRecord}s. In the table below, only
    the \l {QNdefRecord::}{typeNameFormat}() and \l {QNdefRecord::}{type}() of
    each record will be shown, because the other parameters do not matter for
    filtering.

    \table
    \header
        \li Filter
        \li Message
        \li Match Result
        \li Comment
    \row
        \li Empty filter
        \li Empty message
        \li Match
        \li
    \row
        \li Empty filter
        \li Non-empty message
        \li No match
        \li
    \row
        \li Non-empty filter
        \li Empty message
        \li No match
        \li
    \row
        \li {1, 2}[(QNdefRecord::NfcRtd, "T", 1, 2),
            (QNdefRecord::Mime, "", 1, 1), (QNdefRecord::Empty, "", 0, 100)]
        \li {1, 2}[(QNdefRecord::Mime, "image/jpeg"), (QNdefRecord::Empty, ""),
            (QNdefRecord::NfcRtd, "T"), (QNdefRecord::Empty, ""),
            (QNdefRecord::NfcRtd, "T")]
        \li Unordered: match
        \li {1, 2} Ordered filter does not match because the message must start
            with a QNdefRecord::NfcRtd record, but it starts with
            QNdefRecord::Mime.
    \row
        \li Ordered: no match
    \row
        \li {1, 2}[(QNdefRecord::NfcRtd, "T", 0, 2),
            (QNdefRecord::Mime, "", 1, 1), (QNdefRecord::NfcRtd, "T", 1, 1)]
        \li {1, 2}[(QNdefRecord::NfcRtd, "T"), (QNdefRecord::NfcRtd, "T"),
            (QNdefRecord::Mime, "image/jpeg")]
        \li Unordered: match
        \li {1, 2} Ordered filter does not match because an QNdefRecord::NfcRtd
            record is expected after QNdefRecord::Mime, but the message does not
            have it.
    \row
        \li Ordered: no match
    \row
        \li {1, 2}[(QNdefRecord::NfcRtd, "T", 0, 2),
            (QNdefRecord::NfcRtd, "T", 1, 1), (QNdefRecord::Mime, "", 1, 1)]
        \li {1, 2}[(QNdefRecord::NfcRtd, "T"),
            (QNdefRecord::Mime, "image/jpeg")]
        \li Unordered: match
        \li {1, 2} Both cases match because the message contains the required
            minimum of records in the correct order.
    \row
        \li Ordered: match
    \endtable

*/

/*!
    \class QNdefFilter::Record
    \brief The QNdefFilter::Record struct contains the information about a
    filter record.

    \ingroup connectivity-nfc
    \inmodule QtNfc
    \since 5.2

    The QNdefFilter::Record struct is used to populate the QNdefFilter object.
    Each record contains the following information:
    \list
    \li \l {QNdefRecord::TypeNameFormat} of the corresponding \l QNdefRecord.
    \li Type of the \l QNdefRecord.
    \li Minimum and maximum amount of the records with such parameters in the
        filter.
    \endlist
*/

/*!
    \fn template<typename T> bool QNdefFilter::appendRecord(unsigned int min, unsigned int max)

    Appends a record matching the template parameter to the NDEF filter.
    The record must occur between \a min and \a max times in the NDEF message.

    Returns \c true if the record was appended successfully. Otherwise returns
    \c false.
*/

class QNdefFilterPrivate : public QSharedData
{
public:
    QNdefFilterPrivate();

    bool orderMatching;
    QList<QNdefFilter::Record> filterRecords;
};

QNdefFilterPrivate::QNdefFilterPrivate()
:   orderMatching(false)
{
}

/*!
    Constructs a new NDEF filter.
*/
QNdefFilter::QNdefFilter()
:   d(new QNdefFilterPrivate)
{
}

/*!
    Constructs a new NDEF filter that is a copy of \a other.
*/
QNdefFilter::QNdefFilter(const QNdefFilter &other)
:   d(other.d)
{
}

/*!
    Destroys the NDEF filter.
*/
QNdefFilter::~QNdefFilter()
{
}

/*!
    Assigns \a other to this filter and returns a reference to this filter.
*/
QNdefFilter &QNdefFilter::operator=(const QNdefFilter &other)
{
    if (d != other.d)
        d = other.d;

    return *this;
}

/*!
    \since 6.2

    Returns \c true if the \a message matches the given filter.
    Otherwise returns \c false.

    See \l {Matching Algorithms} for more detailed explanation of matching.
*/
bool QNdefFilter::match(const QNdefMessage &message) const
{
    // empty filter matches only empty message
    if (d->filterRecords.isEmpty())
        return message.isEmpty();

    bool matched = true;
    int totalCount = 0;

    if (!d->orderMatching) {
        // Order is not important. The most reliable way is to merge all the
        // similar records, and then simply check the amount of occurrences.
        using MapKey = QPair<QNdefRecord::TypeNameFormat, QByteArray>;

        // Creating a map from the list of filter records.
        QMap<MapKey, Record> joinedFilterRecords;
        for (const auto &rec : d->filterRecords) {
            const auto key = qMakePair(rec.typeNameFormat, rec.type);
            if (joinedFilterRecords.contains(key)) {
                joinedFilterRecords[key].minimum += rec.minimum;
                joinedFilterRecords[key].maximum += rec.maximum;
            } else {
                joinedFilterRecords.insert(key, rec);
            }
        }
        // Checking the message, calculate occurrences.
        QMap<MapKey, unsigned int> counts; // current number of occurrences
        for (const auto &record : message) {
            const auto key = qMakePair(record.typeNameFormat(), record.type());
            // Do not forget that we handle an empty type as "any type".
            const auto emptyTypeKey = qMakePair(record.typeNameFormat(), QByteArray());

            if (joinedFilterRecords.contains(key))
                counts[key] += 1;
            else if (joinedFilterRecords.contains(emptyTypeKey))
                counts[emptyTypeKey] += 1;
        }
        // Check that the occurrences match [min; max] range.
        for (auto it = joinedFilterRecords.cbegin(); it != joinedFilterRecords.cend(); ++it) {
            const auto count = counts.value(it.key(), 0);
            totalCount += count;
            if (count < it.value().minimum || count > it.value().maximum) {
                matched = false;
                break;
            }
        }
    } else {
        // Order *is* important. Need to iterate the list.

        // Here we need to merge consecutive records with the same parameters.
        QList<Record> mergedRecords;
        // we know that filer is not empty here
        Record currentRecord = d->filterRecords.first();
        for (qsizetype i = 1; i < d->filterRecords.size(); ++i) {
            const auto &rec = d->filterRecords.at(i);
            if (rec.typeNameFormat == currentRecord.typeNameFormat
                && rec.type == currentRecord.type) {
                currentRecord.minimum += rec.minimum;
                currentRecord.maximum += rec.maximum;
            } else {
                mergedRecords.push_back(currentRecord);
                currentRecord = rec;
            }
        }
        mergedRecords.push_back(currentRecord);

        // The list contains the current number of occurrences of each record.
        QList<unsigned int> counts(mergedRecords.size(), 0);

        // Iterate through the messages and calculate the number of occurrences.
        qsizetype filterIndex = 0;
        for (qsizetype messageIndex = 0; matched && messageIndex < message.size(); ++messageIndex) {
            const auto &messageRec = message.at(messageIndex);
            // Try to find a filter record that matches the message record.
            // We start from the last processed filter record, not from the very
            // beginning (because the order matters).
            qsizetype idx = filterIndex;
            for (; idx < mergedRecords.size(); ++idx) {
                const auto &filterRec = mergedRecords.at(idx);
                if (filterRec.typeNameFormat == messageRec.typeNameFormat()
                    && (filterRec.type == messageRec.type() || filterRec.type.isEmpty())) {
                    counts[idx] += 1;
                    break;
                } else if (counts[idx] < filterRec.minimum || counts[idx] > filterRec.maximum) {
                    // The current message record does not match the current
                    // filter record, but we didn't get enough records to
                    // fulfill the filter => that's an error.
                    matched = false;
                    break;
                }
            }
            filterIndex = idx;
        }

        if (matched) {
            // Check that the occurrences match [min; max] range.
            for (qsizetype i = 0; i < mergedRecords.size(); ++i) {
                const auto &rec = mergedRecords.at(i);
                totalCount += counts[i];
                if (counts[i] < rec.minimum || counts[i] > rec.maximum) {
                    matched = false;
                    break;
                }
            }
        }
    }

    // Check if the message has records that do not match any record from the
    // filter. To do it we just need to compare the total count of records,
    // detected by filter, with the full message size. If they do not match,
    // we have some records, that are not covered by the filter.
    if (matched && (totalCount != message.size())) {
        matched = false;
    }

    return matched;
}

/*!
    Clears the filter.
*/
void QNdefFilter::clear()
{
    d->orderMatching = false;
    d->filterRecords.clear();
}

/*!
    Sets the ordering requirements of the filter. If \a on is \c {true}, the
    filter will only match if the order of records in the filter matches the
    order of the records in the NDEF message. If \a on is \c {false}, the order
    of the records is not taken into account when matching.

    By default record order is not taken into account.
*/
void QNdefFilter::setOrderMatch(bool on)
{
    d->orderMatching = on;
}

/*!
    Returns \c true if the filter takes NDEF record order into account when
    matching. Otherwise returns \c false.
*/
bool QNdefFilter::orderMatch() const
{
    return d->orderMatching;
}

/*!
    Appends a record with type name format \a typeNameFormat and type \a type
    to the NDEF filter. The record must occur between \a min and \a max times
    in the NDEF message.

    Returns \c true if the record was appended successfully. Otherwise returns
    \c false.
*/
bool QNdefFilter::appendRecord(QNdefRecord::TypeNameFormat typeNameFormat, const QByteArray &type,
                               unsigned int min, unsigned int max)
{
    QNdefFilter::Record record;

    record.typeNameFormat = typeNameFormat;
    record.type = type;
    record.minimum = min;
    record.maximum = max;

    return appendRecord(record);
}

static bool verifyRecord(const QNdefFilter::Record &record)
{
    return record.minimum <= record.maximum;
}

/*!
    Verifies the \a record and appends it to the NDEF filter.

    Returns \c true if the record was appended successfully. Otherwise returns
    \c false.
*/
bool QNdefFilter::appendRecord(const Record &record)
{
    if (verifyRecord(record)) {
        d->filterRecords.append(record);
        return true;
    }
    return false;
}

/*!
    Returns the NDEF record at index \a i.

    \a i must be a valid index (i.e. 0 <= i < \l recordCount()).

    \sa recordCount()
*/
QNdefFilter::Record QNdefFilter::recordAt(qsizetype i) const
{
    return d->filterRecords.at(i);
}

/*!
    Returns the number of NDEF records in the filter.
*/
qsizetype QNdefFilter::recordCount() const
{
    return d->filterRecords.size();
}

QT_END_NAMESPACE