1// Copyright (C) 2021 The Qt Company Ltd.
2// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
3
4#include "qndeffilter.h"
5#include "qndefmessage.h"
6
7#include <QtCore/QList>
8#include <QtCore/QMap>
9#include <QtCore/QVarLengthArray>
10
11QT_BEGIN_NAMESPACE
12
13/*!
14 \class QNdefFilter
15 \brief The QNdefFilter class provides a filter for matching NDEF messages.
16
17 \ingroup connectivity-nfc
18 \inmodule QtNfc
19 \since 5.2
20
21 The QNdefFilter encapsulates the structure of an NDEF message and is used for
22 matching messages that have a particular structure.
23
24 The following filter matches NDEF messages that contain a single smart poster record:
25
26 \code
27 QNdefFilter filter;
28 filter.append(QNdefRecord::NfcRtd, "Sp");
29 \endcode
30
31 The following filter matches NDEF messages that contain a URI, a localized piece of text and an
32 optional JPEG image. The order of the records must be in the order specified:
33
34 \code
35 QNdefFilter filter;
36 filter.setOrderMatch(true);
37 filter.appendRecord(QNdefRecord::NfcRtd, "U");
38 filter.appendRecord<QNdefNfcTextRecord>();
39 filter.appendRecord(QNdefRecord::Mime, "image/jpeg", 0, 1);
40 \endcode
41
42 The \l match() method can be used to check if a message matches the filter.
43
44 \section1 Matching Algorithms
45
46 The filter behavior depends on the value of \l orderMatch() parameter.
47
48 \note In the discussion below we will consider the filter records to be
49 equal if their \c typeNameFormat and \c type parameters match. Joining
50 two records means adding their \c minimum and \c maximum values,
51 respectively.
52
53 \section2 Unordered Matching
54
55 If the record order is not taken into account, all the equal records in the
56 filter can be joined. The resulting filter will contain only unique records,
57 each with the updated \c minimum and \c maximum value.
58
59 Consider the following example:
60
61 \code
62 QNdefFilter filter;
63 filter.appendRecord<QNdefNfcTextRecord>(0, 1);
64 filter.appendRecord<QNdefNfcTextRecord>(0, 1);
65 filter.appendRecord(QNdefRecord::Mime, "", 1, 1);
66 filter.appendRecord<QNdefNfcTextRecord>(1, 1);
67 filter.setOrderMatch(false);
68 \endcode
69
70 With the unordered matching, the filter will be simplified to the following:
71
72 \code
73 QNdefFilter filter;
74 filter.appendRecord<QNdefNfcTextRecord>(1, 3);
75 filter.appendRecord(QNdefRecord::Mime, "", 1, 1);
76 filter.setOrderMatch(false);
77 \endcode
78
79 Once the filter contains only the unique records, the matching algorithm
80 iterates through the message and calculates the actual amount of records of
81 each type. If all the actual amounts fit in the corresponding
82 [minimum, maximum] ranges, the matching algorithm returns \c true.
83
84 \section2 Ordered Matching
85
86 If the record order is important, a different approach is applied. In this
87 case the equal records can't be simply joined together. However, the
88 consecutive equal records can still be joined. Then, the matching
89 algorithm iterates through the message, this time also taking the positions
90 of the records into account.
91
92 \section2 Handling Empty Type in Filter Record
93
94 It's possible to add a filter record with an empty \c type. In this case
95 the empty type will act as a wildcard for any type.
96
97 For example, the filter can be defined as follows:
98
99 \code
100 QNdefFilter filter;
101 filter.addRecord(QNdefRecord::Mime, "", 1, 1);
102 \endcode
103
104 This filter specifies that the message must contain exactly one NDEF record
105 with \l {QNdefRecord::}{Mime} \l {QNdefRecord::}{typeNameFormat}(), and any
106 \l {QNdefRecord::}{type}().
107
108 \section2 Handling Extra Records in the Message
109
110 If the message contains some records that do not match \e any record in the
111 filter, the matching algorithm will return \c false.
112
113 \section2 Filter Examples
114
115 In the table below, each filter record is specified by the following
116 parameters (in the given order):
117
118 \list
119 \li \c typeNameFormat - contains the \l {QNdefRecord::}{typeNameFormat}() of
120 the record.
121 \li \c type - contains the \l {QNdefRecord::}{type}() of the record.
122 \li \c minimum - contains the minimum amount of occurrences of the record
123 in the message.
124 \li \c maximum - contains the maximum amount of occurrences of the record
125 in the message.
126 \endlist
127
128 The filter contains multiple records.
129
130 The message consists of multiple \l {QNdefRecord}s. In the table below, only
131 the \l {QNdefRecord::}{typeNameFormat}() and \l {QNdefRecord::}{type}() of
132 each record will be shown, because the other parameters do not matter for
133 filtering.
134
135 \table
136 \header
137 \li Filter
138 \li Message
139 \li Match Result
140 \li Comment
141 \row
142 \li Empty filter
143 \li Empty message
144 \li Match
145 \li
146 \row
147 \li Empty filter
148 \li Non-empty message
149 \li No match
150 \li
151 \row
152 \li Non-empty filter
153 \li Empty message
154 \li No match
155 \li
156 \row
157 \li {1, 2}[(QNdefRecord::NfcRtd, "T", 1, 2),
158 (QNdefRecord::Mime, "", 1, 1), (QNdefRecord::Empty, "", 0, 100)]
159 \li {1, 2}[(QNdefRecord::Mime, "image/jpeg"), (QNdefRecord::Empty, ""),
160 (QNdefRecord::NfcRtd, "T"), (QNdefRecord::Empty, ""),
161 (QNdefRecord::NfcRtd, "T")]
162 \li Unordered: match
163 \li {1, 2} Ordered filter does not match because the message must start
164 with a QNdefRecord::NfcRtd record, but it starts with
165 QNdefRecord::Mime.
166 \row
167 \li Ordered: no match
168 \row
169 \li {1, 2}[(QNdefRecord::NfcRtd, "T", 0, 2),
170 (QNdefRecord::Mime, "", 1, 1), (QNdefRecord::NfcRtd, "T", 1, 1)]
171 \li {1, 2}[(QNdefRecord::NfcRtd, "T"), (QNdefRecord::NfcRtd, "T"),
172 (QNdefRecord::Mime, "image/jpeg")]
173 \li Unordered: match
174 \li {1, 2} Ordered filter does not match because an QNdefRecord::NfcRtd
175 record is expected after QNdefRecord::Mime, but the message does not
176 have it.
177 \row
178 \li Ordered: no match
179 \row
180 \li {1, 2}[(QNdefRecord::NfcRtd, "T", 0, 2),
181 (QNdefRecord::NfcRtd, "T", 1, 1), (QNdefRecord::Mime, "", 1, 1)]
182 \li {1, 2}[(QNdefRecord::NfcRtd, "T"),
183 (QNdefRecord::Mime, "image/jpeg")]
184 \li Unordered: match
185 \li {1, 2} Both cases match because the message contains the required
186 minimum of records in the correct order.
187 \row
188 \li Ordered: match
189 \endtable
190
191*/
192
193/*!
194 \class QNdefFilter::Record
195 \brief The QNdefFilter::Record struct contains the information about a
196 filter record.
197
198 \ingroup connectivity-nfc
199 \inmodule QtNfc
200 \since 5.2
201
202 The QNdefFilter::Record struct is used to populate the QNdefFilter object.
203 Each record contains the following information:
204 \list
205 \li \l {QNdefRecord::TypeNameFormat} of the corresponding \l QNdefRecord.
206 \li Type of the \l QNdefRecord.
207 \li Minimum and maximum amount of the records with such parameters in the
208 filter.
209 \endlist
210*/
211
212/*!
213 \fn template<typename T> bool QNdefFilter::appendRecord(unsigned int min, unsigned int max)
214
215 Appends a record matching the template parameter to the NDEF filter.
216 The record must occur between \a min and \a max times in the NDEF message.
217
218 Returns \c true if the record was appended successfully. Otherwise returns
219 \c false.
220*/
221
222class QNdefFilterPrivate : public QSharedData
223{
224public:
225 QNdefFilterPrivate();
226
227 bool orderMatching;
228 QList<QNdefFilter::Record> filterRecords;
229};
230
231QNdefFilterPrivate::QNdefFilterPrivate()
232: orderMatching(false)
233{
234}
235
236/*!
237 Constructs a new NDEF filter.
238*/
239QNdefFilter::QNdefFilter()
240: d(new QNdefFilterPrivate)
241{
242}
243
244/*!
245 Constructs a new NDEF filter that is a copy of \a other.
246*/
247QNdefFilter::QNdefFilter(const QNdefFilter &other)
248: d(other.d)
249{
250}
251
252/*!
253 Destroys the NDEF filter.
254*/
255QNdefFilter::~QNdefFilter()
256{
257}
258
259/*!
260 Assigns \a other to this filter and returns a reference to this filter.
261*/
262QNdefFilter &QNdefFilter::operator=(const QNdefFilter &other)
263{
264 if (d != other.d)
265 d = other.d;
266
267 return *this;
268}
269
270/*!
271 \since 6.2
272
273 Returns \c true if the \a message matches the given filter.
274 Otherwise returns \c false.
275
276 See \l {Matching Algorithms} for more detailed explanation of matching.
277*/
278bool QNdefFilter::match(const QNdefMessage &message) const
279{
280 // empty filter matches only empty message
281 if (d->filterRecords.isEmpty())
282 return message.isEmpty();
283
284 bool matched = true;
285 int totalCount = 0;
286
287 if (!d->orderMatching) {
288 // Order is not important. The most reliable way is to merge all the
289 // similar records, and then simply check the amount of occurrences.
290 using MapKey = QPair<QNdefRecord::TypeNameFormat, QByteArray>;
291
292 // Creating a map from the list of filter records.
293 QMap<MapKey, Record> joinedFilterRecords;
294 for (const auto &rec : d->filterRecords) {
295 const auto key = qMakePair(value1: rec.typeNameFormat, value2: rec.type);
296 if (joinedFilterRecords.contains(key)) {
297 joinedFilterRecords[key].minimum += rec.minimum;
298 joinedFilterRecords[key].maximum += rec.maximum;
299 } else {
300 joinedFilterRecords.insert(key, value: rec);
301 }
302 }
303 // Checking the message, calculate occurrences.
304 QMap<MapKey, unsigned int> counts; // current number of occurrences
305 for (const auto &record : message) {
306 const auto key = qMakePair(value1: record.typeNameFormat(), value2: record.type());
307 // Do not forget that we handle an empty type as "any type".
308 const auto emptyTypeKey = qMakePair(value1: record.typeNameFormat(), value2: QByteArray());
309
310 if (joinedFilterRecords.contains(key))
311 counts[key] += 1;
312 else if (joinedFilterRecords.contains(key: emptyTypeKey))
313 counts[emptyTypeKey] += 1;
314 }
315 // Check that the occurrences match [min; max] range.
316 for (auto it = joinedFilterRecords.cbegin(); it != joinedFilterRecords.cend(); ++it) {
317 const auto count = counts.value(key: it.key(), defaultValue: 0);
318 totalCount += count;
319 if (count < it.value().minimum || count > it.value().maximum) {
320 matched = false;
321 break;
322 }
323 }
324 } else {
325 // Order *is* important. Need to iterate the list.
326
327 // Here we need to merge consecutive records with the same parameters.
328 QList<Record> mergedRecords;
329 // we know that filer is not empty here
330 Record currentRecord = d->filterRecords.first();
331 for (qsizetype i = 1; i < d->filterRecords.size(); ++i) {
332 const auto &rec = d->filterRecords.at(i);
333 if (rec.typeNameFormat == currentRecord.typeNameFormat
334 && rec.type == currentRecord.type) {
335 currentRecord.minimum += rec.minimum;
336 currentRecord.maximum += rec.maximum;
337 } else {
338 mergedRecords.push_back(t: currentRecord);
339 currentRecord = rec;
340 }
341 }
342 mergedRecords.push_back(t: currentRecord);
343
344 // The list contains the current number of occurrences of each record.
345 QVarLengthArray<unsigned int> counts(mergedRecords.size(), 0);
346
347 // Iterate through the messages and calculate the number of occurrences.
348 qsizetype filterIndex = 0;
349 for (qsizetype messageIndex = 0; matched && messageIndex < message.size(); ++messageIndex) {
350 const auto &messageRec = message.at(i: messageIndex);
351 // Try to find a filter record that matches the message record.
352 // We start from the last processed filter record, not from the very
353 // beginning (because the order matters).
354 qsizetype idx = filterIndex;
355 for (; idx < mergedRecords.size(); ++idx) {
356 const auto &filterRec = mergedRecords.at(i: idx);
357 if (filterRec.typeNameFormat == messageRec.typeNameFormat()
358 && (filterRec.type == messageRec.type() || filterRec.type.isEmpty())) {
359 counts[idx] += 1;
360 break;
361 } else if (counts[idx] < filterRec.minimum || counts[idx] > filterRec.maximum) {
362 // The current message record does not match the current
363 // filter record, but we didn't get enough records to
364 // fulfill the filter => that's an error.
365 matched = false;
366 break;
367 }
368 }
369 filterIndex = idx;
370 }
371
372 if (matched) {
373 // Check that the occurrences match [min; max] range.
374 for (qsizetype i = 0; i < mergedRecords.size(); ++i) {
375 const auto &rec = mergedRecords.at(i);
376 totalCount += counts[i];
377 if (counts[i] < rec.minimum || counts[i] > rec.maximum) {
378 matched = false;
379 break;
380 }
381 }
382 }
383 }
384
385 // Check if the message has records that do not match any record from the
386 // filter. To do it we just need to compare the total count of records,
387 // detected by filter, with the full message size. If they do not match,
388 // we have some records, that are not covered by the filter.
389 if (matched && (totalCount != message.size())) {
390 matched = false;
391 }
392
393 return matched;
394}
395
396/*!
397 Clears the filter.
398*/
399void QNdefFilter::clear()
400{
401 d->orderMatching = false;
402 d->filterRecords.clear();
403}
404
405/*!
406 Sets the ordering requirements of the filter. If \a on is \c {true}, the
407 filter will only match if the order of records in the filter matches the
408 order of the records in the NDEF message. If \a on is \c {false}, the order
409 of the records is not taken into account when matching.
410
411 By default record order is not taken into account.
412*/
413void QNdefFilter::setOrderMatch(bool on)
414{
415 d->orderMatching = on;
416}
417
418/*!
419 Returns \c true if the filter takes NDEF record order into account when
420 matching. Otherwise returns \c false.
421*/
422bool QNdefFilter::orderMatch() const
423{
424 return d->orderMatching;
425}
426
427/*!
428 Appends a record with type name format \a typeNameFormat and type \a type
429 to the NDEF filter. The record must occur between \a min and \a max times
430 in the NDEF message.
431
432 Returns \c true if the record was appended successfully. Otherwise returns
433 \c false.
434*/
435bool QNdefFilter::appendRecord(QNdefRecord::TypeNameFormat typeNameFormat, const QByteArray &type,
436 unsigned int min, unsigned int max)
437{
438 QNdefFilter::Record record;
439
440 record.typeNameFormat = typeNameFormat;
441 record.type = type;
442 record.minimum = min;
443 record.maximum = max;
444
445 return appendRecord(record);
446}
447
448static bool verifyRecord(const QNdefFilter::Record &record)
449{
450 return record.minimum <= record.maximum;
451}
452
453/*!
454 Verifies the \a record and appends it to the NDEF filter.
455
456 Returns \c true if the record was appended successfully. Otherwise returns
457 \c false.
458*/
459bool QNdefFilter::appendRecord(const Record &record)
460{
461 if (verifyRecord(record)) {
462 d->filterRecords.append(t: record);
463 return true;
464 }
465 return false;
466}
467
468/*!
469 Returns the NDEF record at index \a i.
470
471 \a i must be a valid index (i.e. 0 <= i < \l recordCount()).
472
473 \sa recordCount()
474*/
475QNdefFilter::Record QNdefFilter::recordAt(qsizetype i) const
476{
477 return d->filterRecords.at(i);
478}
479
480/*!
481 Returns the number of NDEF records in the filter.
482*/
483qsizetype QNdefFilter::recordCount() const
484{
485 return d->filterRecords.size();
486}
487
488QT_END_NAMESPACE
489

source code of qtconnectivity/src/nfc/qndeffilter.cpp