VirtualBox

source: vbox/trunk/src/VBox/Main/include/Matching.h@ 67954

Last change on this file since 67954 was 65158, checked in by vboxsync, 8 years ago

Main: doxygen fixes

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 13.9 KB
Line 
1/* $Id: Matching.h 65158 2017-01-05 16:52:22Z vboxsync $ */
2/** @file
3 * Declaration of template classes that provide simple API to
4 * do matching between values and value filters constructed from strings.
5 */
6
7/*
8 * Copyright (C) 2006-2016 Oracle Corporation
9 *
10 * This file is part of VirtualBox Open Source Edition (OSE), as
11 * available from http://www.virtualbox.org. This file is free software;
12 * you can redistribute it and/or modify it under the terms of the GNU
13 * General Public License (GPL) as published by the Free Software
14 * Foundation, in version 2 as it comes in the "COPYING" file of the
15 * VirtualBox OSE distribution. VirtualBox OSE is distributed in the
16 * hope that it will be useful, but WITHOUT ANY WARRANTY of any kind.
17 */
18
19#ifndef ____H_MATCHING
20#define ____H_MATCHING
21
22#include <VBox/com/string.h>
23
24#include <list>
25#include <limits>
26#include <algorithm>
27
28// min and max don't allow us to use numeric_limits::min() and max()
29#if defined (_MSC_VER)
30#undef min
31#undef max
32#endif
33
34namespace matching
35{
36
37using namespace std;
38using namespace com;
39
40class ParsedFilter_base
41{
42public:
43
44 ParsedFilter_base() : mValid (false), mNull (true), mErrorPosition (0) {};
45
46 /**
47 * Returns @c true if the filter is valid, @c false otherwise.
48 */
49 bool isValid() const { return mNull || mValid; }
50 bool isNull() const { return mNull; }
51
52 /**
53 * Returns the error position from the beginning of the filter
54 * string if #isValid() is false. Positions are zero-based.
55 */
56 size_t errorPosition() const { return mErrorPosition; }
57
58protected:
59
60 /**
61 * Returns @c true if current isNull() and isValid() values make further
62 * detailed matching meaningful, otherwise returns @c false.
63 * Must be called as a first method of every isMatch() implementation,
64 * so that isMatch() will immediately return @c false if isPreMatch() returns
65 * false.
66 */
67 bool isPreMatch() const
68 {
69 if (isNull() || !isValid())
70 return false;
71 return true;
72 }
73
74 bool mValid : 1;
75 bool mNull : 1;
76 size_t mErrorPosition;
77};
78
79class ParsedIntervalFilter_base : public ParsedFilter_base
80{
81protected:
82
83 enum Mode { Single, Start, End };
84
85 union Widest
86 {
87 int64_t ll;
88 uint64_t ull;
89 };
90
91 struct Limits
92 {
93 Widest min;
94 Widest max;
95 };
96
97 ParsedIntervalFilter_base() {}
98
99 /**
100 * Called by #parse when a value token is encountered.
101 * This method can modify mNull, mValid and mErrorPosition when
102 * appropriate. Parsing stops if mValid is false after this method
103 * returns (mErrorPosition most point to the error position in this case).
104 */
105 virtual void parseValue (const char *aFilter, size_t aStart, size_t aEnd,
106 Mode aMode) = 0;
107
108 static void parse (const char *aFilter,
109 ParsedIntervalFilter_base *that);
110
111 static size_t parseValue (const char *aFilter, size_t aStart, size_t aEnd,
112 bool aIsSigned, const Limits &aLimits,
113 Widest &val);
114};
115
116/**
117 * Represents a parsed interval filter.
118 * The string format is:
119 * "int:(\<m\>|([\<m\>]-[\<n\>]))|(\<m\>|([\<m\>]-[\<n\>]))+"
120 * where \<m\> and \<n\> are numbers in the decimal, hex (0xNNN) or octal
121 * (0NNN) form, and \<m\> \< \<n\>. Spaces are allowed around \<m\> and \<n\>.
122 *
123 * @tparam T type of values to match. Must be a fundamental integer type.
124 */
125template <class T>
126class ParsedIntervalFilter : public ParsedIntervalFilter_base
127{
128 typedef ParsedIntervalFilter_base Base;
129 typedef numeric_limits <T> Lim;
130
131 typedef std::list <T> List;
132 typedef std::pair <T, T> Pair;
133 typedef std::list <Pair> PairList;
134
135public:
136
137 ParsedIntervalFilter() {}
138
139 ParsedIntervalFilter (const Bstr &aFilter) { Base::parse (Utf8Str (aFilter), this); }
140
141 ParsedIntervalFilter &operator= (const Bstr &aFilter)
142 {
143 mValues.clear();
144 mIntervals.clear();
145 Base::parse (Utf8Str (aFilter), this);
146 return *this;
147 }
148
149 bool isMatch (const T &aValue) const
150 {
151 if (!isPreMatch())
152 return false;
153
154 {
155 typename List::const_iterator it =
156 std::find (mValues.begin(), mValues.end(), aValue);
157 if (it != mValues.end())
158 return true;
159 }
160
161 for (typename PairList::const_iterator it = mIntervals.begin();
162 it != mIntervals.end(); ++ it)
163 {
164 if ((*it).first <= aValue &&
165 aValue <= (*it).second)
166 return true;
167 }
168
169 return false;
170 }
171
172protected:
173
174 struct Limits : public Base::Limits
175 {
176 Limits()
177 {
178 if (Lim::is_signed)
179 {
180 min.ll = (int64_t) Lim::min();
181 max.ll = (int64_t) Lim::max();
182 }
183 else
184 {
185 min.ull = (uint64_t) Lim::min();
186 max.ull = (uint64_t) Lim::max();
187 }
188 }
189
190 static T toValue (const Widest &aWidest)
191 {
192 if (Lim::is_signed)
193 return (T) aWidest.ll;
194 else
195 return (T) aWidest.ull;
196 }
197 };
198
199 virtual void parseValue (const char *aFilter, size_t aStart, size_t aEnd,
200 Mode aMode)
201 {
202 AssertReturn (Lim::is_integer, (void) 0);
203 AssertReturn (
204 (Lim::is_signed && Lim::digits <= numeric_limits <int64_t>::digits) ||
205 (!Lim::is_signed && Lim::digits <= numeric_limits <uint64_t>::digits),
206 (void) 0);
207
208 Limits limits;
209 Widest val;
210 size_t parsed = aEnd;
211
212 if (aStart != aEnd)
213 parsed = Base::parseValue (aFilter, aStart, aEnd,
214 Lim::is_signed, limits, val);
215
216 if (parsed != aEnd)
217 {
218 mValid = false;
219 mErrorPosition = parsed;
220 return;
221 }
222
223 switch (aMode)
224 {
225 /// @todo (dmik): future optimizations:
226 // 1) join intervals when they overlap
227 // 2) ignore single values that are within any existing interval
228 case Base::Single:
229 {
230 if (aStart == aEnd)
231 {
232 // an empty string (contains only spaces after "int:")
233 mValid = false;
234 mErrorPosition = aEnd;
235 AssertReturn (!mValues.size() && !mIntervals.size(), (void) 0);
236 break;
237 }
238 mValues.push_back (limits.toValue (val));
239 break;
240 }
241 case Base::Start:
242 {
243 // aStart == aEnd means smth. like "-[NNN]"
244 T m = aStart == aEnd ? limits.toValue (limits.min)
245 : limits.toValue (val);
246 mIntervals.push_back (Pair (m, m));
247 break;
248 }
249 case Base::End:
250 {
251 // aStart == aEnd means smth. like "[NNN]-"
252 T n = aStart == aEnd ? limits.toValue (limits.max)
253 : limits.toValue (val);
254 if (n < mIntervals.back().first)
255 {
256 // error at the beginning of N
257 mValid = false;
258 mErrorPosition = aStart;
259 break;
260 }
261 mIntervals.back().second = n;
262 break;
263 }
264 }
265 }
266
267 std::list <T> mValues;
268 std::list <std::pair <T, T> > mIntervals;
269};
270
271/**
272 * Represents a boolean filter.
273 * The string format is: "true|false|yes|no|1|0" or an empty string (any match).
274 */
275
276class ParsedBoolFilter : public ParsedFilter_base
277{
278public:
279
280 ParsedBoolFilter() : mValue (false), mValueAny (false) {}
281
282 ParsedBoolFilter (const Bstr &aFilter) { parse (aFilter); }
283
284 ParsedBoolFilter &operator= (const Bstr &aFilter)
285 {
286 parse (aFilter);
287 return *this;
288 }
289
290 bool isMatch (const bool aValue) const
291 {
292 if (!isPreMatch())
293 return false;
294
295 return mValueAny || mValue == aValue;
296 }
297
298 bool isMatch (const BOOL aValue) const
299 {
300 return isMatch (bool (aValue == TRUE));
301 }
302
303private:
304
305 void parse (const Bstr &aFilter);
306
307 bool mValue : 1;
308 bool mValueAny : 1;
309};
310
311class ParsedRegexpFilter_base : public ParsedFilter_base
312{
313protected:
314
315 ParsedRegexpFilter_base (bool aDefIgnoreCase = false,
316 size_t aMinLen = 0, size_t aMaxLen = 0)
317 : mDefIgnoreCase (aDefIgnoreCase)
318 , mIgnoreCase (aDefIgnoreCase)
319 , mMinLen (aMinLen)
320 , mMaxLen (aMaxLen)
321 {}
322
323 ParsedRegexpFilter_base (const Bstr &aFilter, bool aDefIgnoreCase = false,
324 size_t aMinLen = 0, size_t aMaxLen = 0)
325 : mDefIgnoreCase (aDefIgnoreCase)
326 , mIgnoreCase (aDefIgnoreCase)
327 , mMinLen (aMinLen)
328 , mMaxLen (aMaxLen)
329 {
330 parse (aFilter);
331 }
332
333 ParsedRegexpFilter_base &operator= (const Bstr &aFilter)
334 {
335 parse (aFilter);
336 return *this;
337 }
338
339 bool isMatch (const Bstr &aValue) const;
340
341private:
342
343 void parse (const Bstr &aFilter);
344
345 bool mDefIgnoreCase : 1;
346 bool mIgnoreCase : 1;
347
348 size_t mMinLen;
349 size_t mMaxLen;
350
351 Bstr mSimple;
352};
353
354/**
355 * Represents a parsed regexp filter.
356 *
357 * The string format is: "rx:\<regexp\>" or "\<string\>"
358 * where \<regexp\> is a valid regexp and \<string\> is the exact match.
359 *
360 * @tparam Conv
361 * class that must define a public static function
362 * <tt>Bstr toBstr (T aValue)</tt>, where T is the
363 * type of values that should be accepted by #isMatch().
364 * This function is used to get the string representation of T
365 * for regexp matching.
366 * @tparam aIgnoreCase
367 * true if the case insensitive comparison should be done by default
368 * and false otherwise
369 * @tparam aMinLen
370 * minimum string length, or 0 if not limited.
371 * Used only when the filter string represents the exact match.
372 * @tparam aMaxLen
373 * maximum string length, or 0 if not limited.
374 * Used only when the filter string represents the exact match.
375 */
376template <class Conv, bool aIgnoreCase, size_t aMinLen = 0, size_t aMaxLen = 0>
377class ParsedRegexpFilter : public ParsedRegexpFilter_base
378{
379public:
380
381 enum { IgnoreCase = aIgnoreCase, MinLen = aMinLen, MaxLen = aMaxLen };
382
383 ParsedRegexpFilter() : ParsedRegexpFilter_base (IgnoreCase, MinLen, MaxLen) {}
384
385 ParsedRegexpFilter (const Bstr &aFilter)
386 : ParsedRegexpFilter_base (aFilter, IgnoreCase, MinLen, MaxLen) {}
387
388 ParsedRegexpFilter &operator= (const Bstr &aFilter)
389 {
390 ParsedRegexpFilter_base::operator= (aFilter);
391 return *this;
392 }
393
394 template <class T>
395 bool isMatch (const T &aValue) const
396 {
397 if (!this->isPreMatch())
398 return false;
399
400 return ParsedRegexpFilter_base::isMatch (Conv::toBstr (aValue));
401 }
402
403protected:
404};
405
406/**
407 * Joins two filters into one.
408 * Only one filter is active (i.e. used for matching or for error reporting)
409 * at any given time. The active filter is chosen every time when a new
410 * filter string is assigned to an instance of this class -- the filter
411 * for which isNull() = false after parsing the string becomes the active
412 * one (F1 is tried first).
413 *
414 * Both filters must have <tt>bool isMatch(const T&)</tt> methods where T is
415 * the same type as used in #isMatch().
416 *
417 * @tparam F1 first filter class
418 * @tparam F2 second filter class
419 */
420template <class F1, class F2>
421class TwoParsedFilters
422{
423public:
424
425 TwoParsedFilters() {}
426
427 TwoParsedFilters (const Bstr &aFilter)
428 {
429 mFilter1 = aFilter;
430 if (mFilter1.isNull())
431 mFilter2 = aFilter;
432 }
433
434 TwoParsedFilters &operator= (const Bstr &aFilter)
435 {
436 mFilter1 = aFilter;
437 if (mFilter1.isNull())
438 mFilter2 = aFilter;
439 else
440 mFilter2 = F2(); // reset to null
441 return *this;
442 }
443
444 template <class T>
445 bool isMatch (const T &aValue) const
446 {
447 return mFilter1.isMatch (aValue) || mFilter2.isMatch (aValue);
448 }
449
450 bool isValid() const { return isNull() || (mFilter1.isValid() && mFilter2.isValid()); }
451
452 bool isNull() const { return mFilter1.isNull() && mFilter2.isNull(); }
453
454 size_t errorPosition() const
455 {
456 return !mFilter1.isValid() ? mFilter1.errorPosition() :
457 !mFilter2.isValid() ? mFilter2.errorPosition() : 0;
458 }
459
460 const F1 &first() const { return mFilter1; }
461 const F2 &second() const { return mFilter2; }
462
463private:
464
465 F1 mFilter1;
466 F2 mFilter2;
467};
468
469/**
470 * Inherits from the given parsed filter class and keeps the string used to
471 * construct the filter as a member.
472 *
473 * @tparam F parsed filter class
474 */
475template <class F>
476class Matchable : public F
477{
478public:
479
480 Matchable() {}
481
482 /**
483 * Creates a new parsed filter from the given filter string.
484 * If the string format is invalid, #isValid() will return false.
485 */
486 Matchable (const Bstr &aString)
487 : F (aString), mString (aString) {}
488
489 Matchable (CBSTR aString)
490 : F (Bstr (aString)), mString (aString) {}
491
492 /**
493 * Assigns a new filter string to this object and recreates the parser.
494 * If the string format is invalid, #isValid() will return false.
495 */
496 Matchable &operator= (const Bstr &aString)
497 {
498 F::operator= (aString);
499 mString = aString;
500 return *this;
501 }
502
503 Matchable &operator= (CBSTR aString)
504 {
505 F::operator= (Bstr (aString));
506 mString = aString;
507 return *this;
508 }
509
510 /**
511 * Returns the filter string allowing to use the instance where
512 * Str can be used.
513 */
514 operator const Bstr&() const { return mString; }
515
516 /** Returns the filter string */
517 const Bstr& string() const { return mString; }
518
519private:
520
521 Bstr mString;
522};
523
524} /* namespace matching */
525
526#endif // !____H_MATCHING
527/* vi: set tabstop=4 shiftwidth=4 expandtab: */
Note: See TracBrowser for help on using the repository browser.

© 2024 Oracle Support Privacy / Do Not Sell My Info Terms of Use Trademark Policy Automated Access Etiquette