1  /* $Id: Matching.h 98103 20230117 14:15:46Z 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) 20062023 Oracle and/or its affiliates.


9  *


10  * This file is part of VirtualBox base platform packages, as


11  * available from https://www.virtualbox.org.


12  *


13  * This program is free software; you can redistribute it and/or


14  * modify it under the terms of the GNU General Public License


15  * as published by the Free Software Foundation, in version 3 of the


16  * License.


17  *


18  * This program is distributed in the hope that it will be useful, but


19  * WITHOUT ANY WARRANTY; without even the implied warranty of


20  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU


21  * General Public License for more details.


22  *


23  * You should have received a copy of the GNU General Public License


24  * along with this program; if not, see <https://www.gnu.org/licenses>.


25  *


26  * SPDXLicenseIdentifier: GPL3.0only


27  */


28 


29  #ifndef MAIN_INCLUDED_Matching_h


30  #define MAIN_INCLUDED_Matching_h


31  #ifndef RT_WITHOUT_PRAGMA_ONCE


32  # pragma once


33  #endif


34 


35  #include <VBox/com/string.h>


36 


37  #include <list>


38  #include <limits>


39  #include <algorithm>


40 


41  // min and max don't allow us to use numeric_limits::min() and max()


42  #if defined (_MSC_VER)


43  #undef min


44  #undef max


45  #endif


46 


47  namespace matching


48  {


49 


50  using namespace std;


51  using namespace com;


52 


53  class ParsedFilter_base


54  {


55  public:


56 


57  ParsedFilter_base() : mValid (false), mNull (true), mErrorPosition (0) {};


58 


59  /**


60  * Returns @c true if the filter is valid, @c false otherwise.


61  */


62  bool isValid() const { return mNull  mValid; }


63  bool isNull() const { return mNull; }


64 


65  /**


66  * Returns the error position from the beginning of the filter


67  * string if #isValid() is false. Positions are zerobased.


68  */


69  size_t errorPosition() const { return mErrorPosition; }


70 


71  protected:


72 


73  /**


74  * Returns @c true if current isNull() and isValid() values make further


75  * detailed matching meaningful, otherwise returns @c false.


76  * Must be called as a first method of every isMatch() implementation,


77  * so that isMatch() will immediately return @c false if isPreMatch() returns


78  * false.


79  */


80  bool isPreMatch() const


81  {


82  if (isNull()  !isValid())


83  return false;


84  return true;


85  }


86 


87  bool mValid : 1;


88  bool mNull : 1;


89  size_t mErrorPosition;


90  };


91 


92  class ParsedIntervalFilter_base : public ParsedFilter_base


93  {


94  public:


95  virtual ~ParsedIntervalFilter_base() { /* Make VC++ 14.2 happy */ }


96 


97  protected:


98 


99  enum Mode { Single, Start, End };


100 


101  union Widest


102  {


103  int64_t ll;


104  uint64_t ull;


105  };


106 


107  struct Limits


108  {


109  Widest min;


110  Widest max;


111  };


112 


113  ParsedIntervalFilter_base() {}


114 


115  /**


116  * Called by #parse when a value token is encountered.


117  * This method can modify mNull, mValid and mErrorPosition when


118  * appropriate. Parsing stops if mValid is false after this method


119  * returns (mErrorPosition most point to the error position in this case).


120  */


121  virtual void parseValue (const char *aFilter, size_t aStart, size_t aEnd,


122  Mode aMode) = 0;


123 


124  static void parse (const char *aFilter,


125  ParsedIntervalFilter_base *that);


126 


127  static size_t parseValue (const char *aFilter, size_t aStart, size_t aEnd,


128  bool aIsSigned, const Limits &aLimits,


129  Widest &val);


130  };


131 


132  /**


133  * Represents a parsed interval filter.


134  * The string format is:


135  * "int:(\<m\>([\<m\>][\<n\>]))(\<m\>([\<m\>][\<n\>]))+"


136  * where \<m\> and \<n\> are numbers in the decimal, hex (0xNNN) or octal


137  * (0NNN) form, and \<m\> \< \<n\>. Spaces are allowed around \<m\> and \<n\>.


138  *


139  * @tparam T type of values to match. Must be a fundamental integer type.


140  */


141  template <class T>


142  class ParsedIntervalFilter : public ParsedIntervalFilter_base


143  {


144  typedef ParsedIntervalFilter_base Base;


145  typedef numeric_limits <T> Lim;


146 


147  typedef std::list <T> List;


148  typedef std::pair <T, T> Pair;


149  typedef std::list <Pair> PairList;


150 


151  public:


152 


153  ParsedIntervalFilter() {}


154 


155  ParsedIntervalFilter (const Bstr &aFilter) { Base::parse (Utf8Str (aFilter), this); }


156 


157  ParsedIntervalFilter &operator= (const Bstr &aFilter)


158  {


159  mValues.clear();


160  mIntervals.clear();


161  Base::parse (Utf8Str (aFilter), this);


162  return *this;


163  }


164 


165  bool isMatch (const T &aValue) const


166  {


167  if (!isPreMatch())


168  return false;


169 


170  {


171  typename List::const_iterator it =


172  std::find (mValues.begin(), mValues.end(), aValue);


173  if (it != mValues.end())


174  return true;


175  }


176 


177  for (typename PairList::const_iterator it = mIntervals.begin();


178  it != mIntervals.end(); ++ it)


179  {


180  if ((*it).first <= aValue &&


181  aValue <= (*it).second)


182  return true;


183  }


184 


185  return false;


186  }


187 


188  protected:


189 


190  struct Limits : public Base::Limits


191  {


192  Limits()


193  {


194  if (Lim::is_signed)


195  {


196  min.ll = (int64_t) Lim::min();


197  max.ll = (int64_t) Lim::max();


198  }


199  else


200  {


201  min.ull = (uint64_t) Lim::min();


202  max.ull = (uint64_t) Lim::max();


203  }


204  }


205 


206  static T toValue (const Widest &aWidest)


207  {


208  if (Lim::is_signed)


209  return (T) aWidest.ll;


210  else


211  return (T) aWidest.ull;


212  }


213  };


214 


215  virtual void parseValue (const char *aFilter, size_t aStart, size_t aEnd,


216  Mode aMode)


217  {


218  AssertReturn (Lim::is_integer, (void) 0);


219  AssertReturn (


220  (Lim::is_signed && Lim::digits <= numeric_limits <int64_t>::digits) 


221  (!Lim::is_signed && Lim::digits <= numeric_limits <uint64_t>::digits),


222  (void) 0);


223 


224  Limits limits;


225  Widest val;


226  size_t parsed = aEnd;


227 


228  if (aStart != aEnd)


229  parsed = Base::parseValue (aFilter, aStart, aEnd,


230  Lim::is_signed, limits, val);


231 


232  if (parsed != aEnd)


233  {


234  mValid = false;


235  mErrorPosition = parsed;


236  return;


237  }


238 


239  switch (aMode)


240  {


241  /// @todo (dmik): future optimizations:


242  // 1) join intervals when they overlap


243  // 2) ignore single values that are within any existing interval


244  case Base::Single:


245  {


246  if (aStart == aEnd)


247  {


248  // an empty string (contains only spaces after "int:")


249  mValid = false;


250  mErrorPosition = aEnd;


251  AssertReturn (!mValues.size() && !mIntervals.size(), (void) 0);


252  break;


253  }


254  mValues.push_back (limits.toValue (val));


255  break;


256  }


257  case Base::Start:


258  {


259  // aStart == aEnd means smth. like "[NNN]"


260  T m = aStart == aEnd ? limits.toValue (limits.min)


261  : limits.toValue (val);


262  mIntervals.push_back (Pair (m, m));


263  break;


264  }


265  case Base::End:


266  {


267  // aStart == aEnd means smth. like "[NNN]"


268  T n = aStart == aEnd ? limits.toValue (limits.max)


269  : limits.toValue (val);


270  if (n < mIntervals.back().first)


271  {


272  // error at the beginning of N


273  mValid = false;


274  mErrorPosition = aStart;


275  break;


276  }


277  mIntervals.back().second = n;


278  break;


279  }


280  }


281  }


282 


283  std::list <T> mValues;


284  std::list <std::pair <T, T> > mIntervals;


285  };


286 


287  /**


288  * Represents a boolean filter.


289  * The string format is: "truefalseyesno10" or an empty string (any match).


290  */


291 


292  class ParsedBoolFilter : public ParsedFilter_base


293  {


294  public:


295 


296  ParsedBoolFilter() : mValue (false), mValueAny (false) {}


297 


298  ParsedBoolFilter (const Bstr &aFilter) { parse (aFilter); }


299 


300  ParsedBoolFilter &operator= (const Bstr &aFilter)


301  {


302  parse (aFilter);


303  return *this;


304  }


305 


306  bool isMatch (const bool aValue) const


307  {


308  if (!isPreMatch())


309  return false;


310 


311  return mValueAny  mValue == aValue;


312  }


313 


314  bool isMatch (const BOOL aValue) const


315  {


316  return isMatch (bool (aValue == TRUE));


317  }


318 


319  private:


320 


321  void parse (const Bstr &aFilter);


322 


323  bool mValue : 1;


324  bool mValueAny : 1;


325  };


326 


327  class ParsedRegexpFilter_base : public ParsedFilter_base


328  {


329  protected:


330 


331  ParsedRegexpFilter_base (bool aDefIgnoreCase = false,


332  size_t aMinLen = 0, size_t aMaxLen = 0)


333  : mIgnoreCase (aDefIgnoreCase)


334  , mMinLen (aMinLen)


335  , mMaxLen (aMaxLen)


336  {}


337 


338  ParsedRegexpFilter_base (const Bstr &aFilter, bool aDefIgnoreCase = false,


339  size_t aMinLen = 0, size_t aMaxLen = 0)


340  : mIgnoreCase (aDefIgnoreCase)


341  , mMinLen (aMinLen)


342  , mMaxLen (aMaxLen)


343  {


344  parse (aFilter);


345  }


346 


347  ParsedRegexpFilter_base &operator= (const Bstr &aFilter)


348  {


349  parse (aFilter);


350  return *this;


351  }


352 


353  bool isMatch (const Bstr &aValue) const;


354 


355  private:


356 


357  void parse (const Bstr &aFilter);


358 


359  bool mIgnoreCase : 1;


360 


361  size_t mMinLen;


362  size_t mMaxLen;


363 


364  Bstr mSimple;


365  };


366 


367  /**


368  * Represents a parsed regexp filter.


369  *


370  * The string format is: "rx:\<regexp\>" or "\<string\>"


371  * where \<regexp\> is a valid regexp and \<string\> is the exact match.


372  *


373  * @tparam Conv


374  * class that must define a public static function


375  * <tt>Bstr toBstr (T aValue)</tt>, where T is the


376  * type of values that should be accepted by #isMatch().


377  * This function is used to get the string representation of T


378  * for regexp matching.


379  * @tparam aIgnoreCase


380  * true if the case insensitive comparison should be done by default


381  * and false otherwise


382  * @tparam aMinLen


383  * minimum string length, or 0 if not limited.


384  * Used only when the filter string represents the exact match.


385  * @tparam aMaxLen


386  * maximum string length, or 0 if not limited.


387  * Used only when the filter string represents the exact match.


388  */


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


390  class ParsedRegexpFilter : public ParsedRegexpFilter_base


391  {


392  public:


393 


394  enum { IgnoreCase = aIgnoreCase, MinLen = aMinLen, MaxLen = aMaxLen };


395 


396  ParsedRegexpFilter() : ParsedRegexpFilter_base (IgnoreCase, MinLen, MaxLen) {}


397 


398  ParsedRegexpFilter (const Bstr &aFilter)


399  : ParsedRegexpFilter_base (aFilter, IgnoreCase, MinLen, MaxLen) {}


400 


401  ParsedRegexpFilter &operator= (const Bstr &aFilter)


402  {


403  ParsedRegexpFilter_base::operator= (aFilter);


404  return *this;


405  }


406 


407  template <class T>


408  bool isMatch (const T &aValue) const


409  {


410  if (!this>isPreMatch())


411  return false;


412 


413  return ParsedRegexpFilter_base::isMatch (Conv::toBstr (aValue));


414  }


415 


416  protected:


417  };


418 


419  /**


420  * Joins two filters into one.


421  * Only one filter is active (i.e. used for matching or for error reporting)


422  * at any given time. The active filter is chosen every time when a new


423  * filter string is assigned to an instance of this class  the filter


424  * for which isNull() = false after parsing the string becomes the active


425  * one (F1 is tried first).


426  *


427  * Both filters must have <tt>bool isMatch(const T&)</tt> methods where T is


428  * the same type as used in #isMatch().


429  *


430  * @tparam F1 first filter class


431  * @tparam F2 second filter class


432  */


433  template <class F1, class F2>


434  class TwoParsedFilters


435  {


436  public:


437 


438  TwoParsedFilters() {}


439 


440  TwoParsedFilters (const Bstr &aFilter)


441  {


442  mFilter1 = aFilter;


443  if (mFilter1.isNull())


444  mFilter2 = aFilter;


445  }


446 


447  TwoParsedFilters &operator= (const Bstr &aFilter)


448  {


449  mFilter1 = aFilter;


450  if (mFilter1.isNull())


451  mFilter2 = aFilter;


452  else


453  mFilter2 = F2(); // reset to null


454  return *this;


455  }


456 


457  template <class T>


458  bool isMatch (const T &aValue) const


459  {


460  return mFilter1.isMatch (aValue)  mFilter2.isMatch (aValue);


461  }


462 


463  bool isValid() const { return isNull()  (mFilter1.isValid() && mFilter2.isValid()); }


464 


465  bool isNull() const { return mFilter1.isNull() && mFilter2.isNull(); }


466 


467  size_t errorPosition() const


468  {


469  return !mFilter1.isValid() ? mFilter1.errorPosition() :


470  !mFilter2.isValid() ? mFilter2.errorPosition() : 0;


471  }


472 


473  const F1 &first() const { return mFilter1; }


474  const F2 &second() const { return mFilter2; }


475 


476  private:


477 


478  F1 mFilter1;


479  F2 mFilter2;


480  };


481 


482  /**


483  * Inherits from the given parsed filter class and keeps the string used to


484  * construct the filter as a member.


485  *


486  * @tparam F parsed filter class


487  */


488  template <class F>


489  class Matchable : public F


490  {


491  public:


492 


493  Matchable() {}


494 


495  /**


496  * Creates a new parsed filter from the given filter string.


497  * If the string format is invalid, #isValid() will return false.


498  */


499  Matchable (const Bstr &aString)


500  : F (aString), mString (aString) {}


501 


502  Matchable (CBSTR aString)


503  : F (Bstr (aString)), mString (aString) {}


504 


505  /**


506  * Assigns a new filter string to this object and recreates the parser.


507  * If the string format is invalid, #isValid() will return false.


508  */


509  Matchable &operator= (const Bstr &aString)


510  {


511  F::operator= (aString);


512  mString = aString;


513  return *this;


514  }


515 


516  Matchable &operator= (CBSTR aString)


517  {


518  F::operator= (Bstr (aString));


519  mString = aString;


520  return *this;


521  }


522 


523  /**


524  * Returns the filter string allowing to use the instance where


525  * Str can be used.


526  */


527  operator const Bstr&() const { return mString; }


528 


529  /** Returns the filter string */


530  const Bstr& string() const { return mString; }


531 


532  private:


533 


534  Bstr mString;


535  };


536 


537  } /* namespace matching */


538 


539  #endif /* !MAIN_INCLUDED_Matching_h */


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

