1  /* $Id: Matching.h 65158 20170105 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) 20062016 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 


34  namespace matching


35  {


36 


37  using namespace std;


38  using namespace com;


39 


40  class ParsedFilter_base


41  {


42  public:


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 zerobased.


55  */


56  size_t errorPosition() const { return mErrorPosition; }


57 


58  protected:


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 


79  class ParsedIntervalFilter_base : public ParsedFilter_base


80  {


81  protected:


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  */


125  template <class T>


126  class 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 


135  public:


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 


172  protected:


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: "truefalseyesno10" or an empty string (any match).


274  */


275 


276  class ParsedBoolFilter : public ParsedFilter_base


277  {


278  public:


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 


303  private:


304 


305  void parse (const Bstr &aFilter);


306 


307  bool mValue : 1;


308  bool mValueAny : 1;


309  };


310 


311  class ParsedRegexpFilter_base : public ParsedFilter_base


312  {


313  protected:


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 


341  private:


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  */


376  template <class Conv, bool aIgnoreCase, size_t aMinLen = 0, size_t aMaxLen = 0>


377  class ParsedRegexpFilter : public ParsedRegexpFilter_base


378  {


379  public:


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 


403  protected:


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  */


420  template <class F1, class F2>


421  class TwoParsedFilters


422  {


423  public:


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 


463  private:


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  */


475  template <class F>


476  class Matchable : public F


477  {


478  public:


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 


519  private:


520 


521  Bstr mString;


522  };


523 


524  } /* namespace matching */


525 


526  #endif // !____H_MATCHING


527  /* vi: set tabstop=4 shiftwidth=4 expandtab: */

