VirtualBox

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

Last change on this file since 8155 was 8155, checked in by vboxsync, 17 years ago

The Big Sun Rebranding Header Change

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 13.9 KB
Line 
1/** @file
2 *
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-2007 Sun Microsystems, Inc.
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 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa
19 * Clara, CA 95054 USA or visit http://www.sun.com if you need
20 * additional information or have any questions.
21 */
22
23#ifndef ____H_MATCHING
24#define ____H_MATCHING
25
26#include <VBox/com/string.h>
27
28#include <list>
29#include <limits>
30#include <algorithm>
31
32// min and max don't allow us to use numeric_limits::min() and max()
33#if defined (_MSC_VER)
34#undef min
35#undef max
36#endif
37
38namespace matching
39{
40
41using namespace std;
42using namespace com;
43
44class ParsedFilter_base
45{
46public:
47
48 ParsedFilter_base() : mValid (false), mNull (true), mErrorPosition (0) {};
49
50 bool isValid() const { return mNull || mValid; }
51 bool isNull() const { return mNull; }
52
53 /**
54 * Returns the error position from the beginning of the filter
55 * string if #isValid() is false. Positions are zero-based.
56 */
57 size_t errorPosition() const { return mErrorPosition; }
58
59protected:
60
61 /**
62 * Returns true if current isNull() and isValid() values make further
63 * detailed matching meaningful, otherwise returns false.
64 * Must be called as a first method of every isMatch() implementation,
65 * so that isMatch() will immediately return false if isPreMatch() retuns
66 * false.
67 */
68 bool isPreMatch() const
69 {
70 if (isNull() || !isValid())
71 return false;
72 return true;
73 }
74
75 bool mValid : 1;
76 bool mNull : 1;
77 size_t mErrorPosition;
78};
79
80class ParsedIntervalFilter_base : public ParsedFilter_base
81{
82protected:
83
84 enum Mode { Single, Start, End };
85
86 union Widest
87 {
88 int64_t ll;
89 uint64_t ull;
90 };
91
92 struct Limits
93 {
94 Widest min;
95 Widest max;
96 };
97
98 ParsedIntervalFilter_base() {}
99
100 /**
101 * Called by #parse when a value token is encountered.
102 * This method can modify mNull, mValid and mErrorPosition when
103 * appropriate. Parsing stops if mValid is false after this method
104 * returns (mErrorPosition most point to the error position in this case).
105 */
106 virtual void parseValue (const char *aFilter, size_t aStart, size_t aEnd,
107 Mode aMode) = 0;
108
109 static void parse (const char *aFilter,
110 ParsedIntervalFilter_base *that);
111
112 static size_t parseValue (const char *aFilter, size_t aStart, size_t aEnd,
113 bool aIsSigned, const Limits &aLimits,
114 Widest &val);
115};
116
117/**
118 * Represents a parsed interval filter.
119 * The string format is: "int:(<m>|([<m>]-[<n>]))|(<m>|([<m>]-[<n>]))+"
120 * where <m> and <n> are numbers in the decimal, hex (0xNNN) or octal (0NNN)
121 * form, and <m> < <n>. Spaces are allowed around <m> and <n>.
122 *
123 * @param 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 * The string format is: "rx:<regexp>" or "<string>"
357 * where <regexp> is a valid regexp and <string> is the exact match.
358 *
359 * @param Conv
360 * class that must define a public static function
361 * <tt>Bstr toBstr (T aValue)</tt>, where T is the
362 * type of values that should be accepted by #isMatch().
363 * This function is used to get the string representation of T
364 * for regexp matching.
365 * @param aIgnoreCase
366 * true if the case insensitive comparison should be done by default
367 * and false otherwise
368 * @param aMinLen
369 * minimum string length, or 0 if not limited.
370 * Used only when the filter string represents the exact match.
371 * @param aMaxLen
372 * maximum string length, or 0 if not limited.
373 * Used only when the filter string represents the exact match.
374 */
375template <class Conv, bool aIgnoreCase, size_t aMinLen = 0, size_t aMaxLen = 0>
376class ParsedRegexpFilter : public ParsedRegexpFilter_base
377{
378public:
379
380 enum { IgnoreCase = aIgnoreCase, MinLen = aMinLen, MaxLen = aMaxLen };
381
382 ParsedRegexpFilter() : ParsedRegexpFilter_base (IgnoreCase, MinLen, MaxLen) {}
383
384 ParsedRegexpFilter (const Bstr &aFilter)
385 : ParsedRegexpFilter_base (aFilter, IgnoreCase, MinLen, MaxLen) {}
386
387 ParsedRegexpFilter &operator= (const Bstr &aFilter)
388 {
389 ParsedRegexpFilter_base::operator= (aFilter);
390 return *this;
391 }
392
393 template <class T>
394 bool isMatch (const T &aValue) const
395 {
396 if (!this->isPreMatch())
397 return false;
398
399 return ParsedRegexpFilter_base::isMatch (Conv::toBstr (aValue));
400 }
401
402protected:
403};
404
405/**
406 * Joins two filters into one.
407 * Only one filter is active (i.e. used for matching or for error reporting)
408 * at any given time. The active filter is chosen every time when a new
409 * filter string is assigned to an instance of this class -- the filter
410 * for which isNull() = false after parsing the string becomes the active
411 * one (F1 is tried first).
412 *
413 * Both filters must have <tt>bool isMatch (const T&)</tt>
414 * methods where T is the same type as used in #isMatch().
415 *
416 * @param F1 first filter class
417 * @param F2 second filter class
418 */
419template <class F1, class F2>
420class TwoParsedFilters
421{
422public:
423
424 TwoParsedFilters() {}
425
426 TwoParsedFilters (const Bstr &aFilter)
427 {
428 mFilter1 = aFilter;
429 if (mFilter1.isNull())
430 mFilter2 = aFilter;
431 }
432
433 TwoParsedFilters &operator= (const Bstr &aFilter)
434 {
435 mFilter1 = aFilter;
436 if (mFilter1.isNull())
437 mFilter2 = aFilter;
438 else
439 mFilter2 = F2(); // reset to null
440 return *this;
441 }
442
443 template <class T>
444 bool isMatch (const T &aValue) const
445 {
446 return mFilter1.isMatch (aValue) || mFilter2.isMatch (aValue);
447 }
448
449 bool isValid() const { return isNull() || (mFilter1.isValid() && mFilter2.isValid()); }
450
451 bool isNull() const { return mFilter1.isNull() && mFilter2.isNull(); }
452
453 size_t errorPosition() const
454 {
455 return !mFilter1.isValid() ? mFilter1.errorPosition() :
456 !mFilter2.isValid() ? mFilter2.errorPosition() : 0;
457 }
458
459 const F1 &first() const { return mFilter1; }
460 const F2 &second() const { return mFilter2; }
461
462private:
463
464 F1 mFilter1;
465 F2 mFilter2;
466};
467
468/**
469 * Inherits from the given parsed filter class and keeps the string used to
470 * construct the filter as a member.
471 *
472 * @param F parsed filter class
473 */
474template <class F>
475class Matchable : public F
476{
477public:
478
479 Matchable() {}
480
481 /**
482 * Creates a new parsed filter from the given filter string.
483 * If the string format is invalid, #isValid() will return false.
484 */
485 Matchable (const Bstr &aString)
486 : F (aString), mString (aString) {}
487
488 Matchable (const BSTR aString)
489 : F (Bstr (aString)), mString (aString) {}
490
491 /**
492 * Assings a new filter string to this object and recreates the parser.
493 * If the string format is invalid, #isValid() will return false.
494 */
495 Matchable &operator= (const Bstr &aString)
496 {
497 F::operator= (aString);
498 mString = aString;
499 return *this;
500 }
501
502 Matchable &operator= (const BSTR aString)
503 {
504 F::operator= (Bstr (aString));
505 mString = aString;
506 return *this;
507 }
508
509 /**
510 * Returns the filter string allowing to use the instance where
511 * Str can be used.
512 */
513 operator const Bstr&() const { return mString; }
514
515 /** Returns the filter string */
516 const Bstr& string() const { return mString; }
517
518private:
519
520 Bstr mString;
521};
522
523} /* namespace matching */
524
525#endif // ____H_MATCHING
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