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

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