include/pub_tool_seqmatch.h

   1
   2 /*--------------------------------------------------------------------*/
   3 /*--- A simple sequence matching facility.                         ---*/
   4 /*---                                          pub_tool_seqmatch.h ---*/
   5 /*--------------------------------------------------------------------*/
   6
   7 /*
   8    This file is part of Valgrind, a dynamic binary instrumentation
   9    framework.
  10
  11    Copyright (C) 2008-2017 OpenWorks Ltd
  12       info@open-works.co.uk
  13
  14    This program is free software; you can redistribute it and/or
  15    modify it under the terms of the GNU General Public License as
  16    published by the Free Software Foundation; either version 2 of the
  17    License, or (at your option) any later version.
  18
  19    This program is distributed in the hope that it will be useful, but
  20    WITHOUT ANY WARRANTY; without even the implied warranty of
  21    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  22    General Public License for more details.
  23
  24    You should have received a copy of the GNU General Public License
  25    along with this program; if not, write to the Free Software
  26    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
  27    02111-1307, USA.
  28
  29    The GNU General Public License is contained in the file COPYING.
  30 */
  31
  32 #ifndef __PUB_TOOL_SEQMATCH_H
  33 #define __PUB_TOOL_SEQMATCH_H
  34
  35 #include "pub_tool_basics.h"   // UWord
  36
  37 /* Perform totally abstractified sequence matching, of an input
  38    sequence against a pattern sequence.  The pattern sequence may
  39    include '*' elements (matches any number of anything) and '?'
  40    elements (matches exactly one element).  '*' patterns are matched
  41    frugally, meaning that they are "assigned" the minimum amount of
  42    input needed to make the match work.
  43
  44    This routine is recursive.  The recursion depth is equal to the
  45    number of '*' elements in the pattern.  There is no guard against
  46    excessive recursion.  This function has no global state and so is
  47    thread-safe and re-entrant.  (It needs to be, since m_errormgr will
  48    effectively construct two simultaneous calls to it, once to match
  49    at the frame level, and whilst that is happening, once at the
  50    function/object-name level.)
  51
  52    When matchAll is True, the entire input sequence must match the
  53    pattern, else the match fails.  When False, it's ok for some tail
  54    of the input sequence to be unused -- so we're only matching a
  55    prefix.
  56
  57    The pattern array is starts at 'patt' and consists of 'nPatt'
  58    elements each of size 'szbPatt'.  For the initial call, pass a
  59    value of zero to 'ixPatt'.
  60
  61    The input sequence can be similarly described using
  62    input/nInput/szbInput/ixInput.
  63    Alternatively, the input can be lazily constructed using an
  64    inputCompleter. When using an inputCompleter, input/nInput/szbInput
  65    are unused.
  66
  67    pIsStar should return True iff the pointed-to pattern element is
  68    conceptually a '*'.
  69
  70    pIsQuery should return True iff the pointed-to-pattern element is
  71    conceptually a '?'.
  72
  73    pattEQinp takes a pointer to a pattern element and a pointer to an
  74    input element.  It should return True iff they are considered
  75    equal.  Note that the pattern element is guaranteed to be neither
  76    (conceptually) '*' nor '?', so it must be a literal (in the sense
  77    that all the input sequence elements are literal).
  78
  79    If inputCompleter is not NULL, the input will be lazily constructed
  80    when pattEQinp is called.
  81    For lazily constructing the input element, the two last arguments
  82    of pattEQinp are the inputCompleter and the index of the input
  83    element to complete.
  84    VG_(generic_match) calls (*haveInputInpC)(inputCompleter,ixInput) to
  85    check if there is an element ixInput in the input sequence.
  86 */
  87 Bool VG_(generic_match) (
  88         Bool matchAll,
  89         const void* patt,  SizeT szbPatt,  UWord nPatt,  UWord ixPatt,
  90         const void* input, SizeT szbInput, UWord nInput, UWord ixInput,
  91         Bool (*pIsStar)(const void*),
  92         Bool (*pIsQuery)(const void*),
  93         Bool (*pattEQinp)(const void*,const void*,void*,UWord),
  94         void* inputCompleter,
  95         Bool (*haveInputInpC)(void*,UWord)
  96      );
  97
  98 /* Mini-regexp function.  Searches for 'pat' in 'str'.  Supports
  99    meta-symbols '*' and '?'.  There is no way to escape meta-symbols
 100    in the pattern. */
 101 Bool VG_(string_match) ( const HChar* pat, const HChar* str );
 102
 103 #endif   // __PUB_TOOL_SEQMATCH_H
 104
 105 /*--------------------------------------------------------------------*/
 106 /*--- end                                      pub_tool_seqmatch.h ---*/
 107 /*--------------------------------------------------------------------*/