Home | History | Annotate | Download | only in coregrind
      1 
      2 /*--------------------------------------------------------------------*/
      3 /*--- A simple sequence matching facility.                         ---*/
      4 /*---                                                 m_seqmatch.c ---*/
      5 /*--------------------------------------------------------------------*/
      6 
      7 /*
      8    This file is part of Valgrind, a dynamic binary instrumentation
      9    framework.
     10 
     11    Copyright (C) 2008-2013 OpenWorks Ltd
     12       info (at) 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 #include "pub_core_basics.h"
     33 #include "pub_core_libcassert.h"
     34 #include "pub_core_libcbase.h"    // VG_(strlen)
     35 #include "pub_core_seqmatch.h"    // self
     36 
     37 /* ---------------------------------------------------------------------
     38    A simple sequence matching facility
     39    ------------------------------------------------------------------ */
     40 
     41 /* See detailed comment in include/pub_tool_seqmatch.h about this. */
     42 Bool VG_(generic_match) (
     43         Bool matchAll,
     44         const void* patt,  SizeT szbPatt,  UWord nPatt,  UWord ixPatt,
     45         const void* input, SizeT szbInput, UWord nInput, UWord ixInput,
     46         Bool (*pIsStar)(const void*),
     47         Bool (*pIsQuery)(const void*),
     48         Bool (*pattEQinp)(const void*,const void*,void*,UWord),
     49         void* inputCompleter, Bool (*haveInputInpC)(void*,UWord)
     50      )
     51 {
     52    /* This is the spec, written in my favourite formal specification
     53       language.  It specifies non-greedy matching of '*'s.
     54 
     55       ma ('*':ps) (i:is) = ma ps (i:is) || ma ('*':ps) is
     56       ma ('*':ps) []     = ma ps []
     57 
     58       ma ('?':ps) (i:is) = ma ps is
     59       ma ('?':ps) []     = False
     60 
     61       ma (p:ps)   (i:is) = p == i && ma ps is
     62 
     63       ma (p:ps)   []     = False
     64       ma []       (i:is) = False -- m-all, True for m-prefix
     65       ma []       []     = True
     66    */
     67    Bool  havePatt, haveInput;
     68    const HChar *currPatt, *currInput;
     69   tailcall:
     70    vg_assert(nPatt >= 0 && nPatt  < 1000000); /* arbitrary */
     71    vg_assert(inputCompleter
     72              || (nInput >= 0  && nInput < 1000000)); /* arbitrary */
     73    vg_assert(ixPatt >= 0  && ixPatt <= nPatt);
     74    vg_assert(ixInput >= 0 && (inputCompleter || ixInput <= nInput));
     75 
     76    havePatt  = ixPatt < nPatt;
     77    haveInput = inputCompleter ?
     78       (*haveInputInpC)(inputCompleter, ixInput)
     79       : ixInput < nInput;
     80 
     81    /* No specific need to set NULL when !have{Patt,Input}, but guards
     82       against inadvertantly dereferencing an out of range pointer to
     83       the pattern or input arrays. */
     84    currPatt  = havePatt  ? ((const HChar*)patt) + szbPatt * ixPatt    : NULL;
     85    currInput = haveInput && !inputCompleter ?
     86       ((const HChar*)input) + szbInput * ixInput : NULL;
     87 
     88    // Deal with the complex case first: wildcards.  Do frugal
     89    // matching.  When encountering a '*', first skip no characters
     90    // at all, and see if the rest of the match still works.  Only if
     91    // that fails do we then skip a character, and retry at the next
     92    // position.
     93    //
     94    // ma ('*':ps) (i:is) = ma ps (i:is) || ma ('*':ps) is
     95    //
     96    // If we're out of input, check the rest of the pattern matches
     97    // the empty input.  This really means can only be be empty or
     98    // composed entirely of '*'s.
     99    //
    100    // ma ('*':ps) []     = ma ps []
    101    //
    102    if (havePatt && pIsStar(currPatt)) {
    103       if (haveInput) {
    104          // ma ('*':ps) (i:is) = ma ps (i:is) || ma ('*':ps) is
    105          // we unavoidably have to make a real recursive call for the
    106          // first half of the OR, since this isn't straight tail-recursion.
    107          if (VG_(generic_match)( matchAll,
    108                                  patt, szbPatt, nPatt,  ixPatt+1,
    109                                  input,szbInput,nInput, ixInput+0,
    110                                  pIsStar,pIsQuery,pattEQinp,
    111                                  inputCompleter,haveInputInpC) ) {
    112             return True;
    113          }
    114          // but we can tail-recurse for the second call
    115          ixInput++; goto tailcall;
    116       } else {
    117          // ma ('*':ps) []     = ma ps []
    118          ixPatt++; goto tailcall;
    119       }
    120    }
    121 
    122    // simpler cases now.  Deal with '?' wildcards.
    123    //
    124    // ma ('?':ps) (i:is) = ma ps is
    125    // ma ('?':ps) []     = False
    126    if (havePatt && pIsQuery(currPatt)) {
    127       if (haveInput) {
    128          ixPatt++; ixInput++; goto tailcall;
    129       } else {
    130          return False;
    131       }
    132    }
    133 
    134    // obvious case with literal chars in the pattern
    135    //
    136    // ma (p:ps)   (i:is) = p == i && ma ps is
    137    if (havePatt && haveInput) {
    138       if (!pattEQinp(currPatt,currInput,inputCompleter,ixInput)) return False;
    139       ixPatt++; ixInput++; goto tailcall;
    140    }
    141 
    142    // if we run out of input before we run out of pattern, we must fail
    143    // ma (p:ps)   []     = False
    144    if (havePatt && !haveInput) return False;
    145 
    146    // if we run out of pattern before we run out of input, the
    147    // verdict depends on the matching mode.  If we are trying to
    148    // match exactly (the pattern must consume the entire input)
    149    // then the outcome is failure.  However, if we're merely attempting
    150    // to match some prefix of the input, then we have been successful.
    151    //
    152    // ma []       (i:is) = False -- m-all, True for m-prefix
    153    if (!havePatt && haveInput) {
    154       return matchAll ? False // match-all
    155                       : True; // match-prefix
    156    }
    157 
    158    // finally, if both sequence and input are both completely
    159    // consumed, then we were successful, regardless of matching mode.
    160    if (!havePatt && !haveInput) return True;
    161 
    162    // end of cases
    163    vg_assert(0);
    164 }
    165 
    166 
    167 /* And a parameterization of the above, to make it do
    168    string matching.
    169 */
    170 static Bool charIsStar  ( const void* pV ) { return *(const HChar*)pV == '*'; }
    171 static Bool charIsQuery ( const void* pV ) { return *(const HChar*)pV == '?'; }
    172 static Bool char_p_EQ_i ( const void* pV, const void* cV,
    173                           void* null_completer, UWord ixcV ) {
    174    HChar p = *(const HChar*)pV;
    175    HChar c = *(const HChar*)cV;
    176    vg_assert(p != '*' && p != '?');
    177    return p == c;
    178 }
    179 Bool VG_(string_match) ( const HChar* patt, const HChar* input )
    180 {
    181    return VG_(generic_match)(
    182              True/* match-all */,
    183              patt,  sizeof(HChar), VG_(strlen)(patt), 0,
    184              input, sizeof(HChar), VG_(strlen)(input), 0,
    185              charIsStar, charIsQuery, char_p_EQ_i,
    186              NULL, NULL
    187           );
    188 }
    189 
    190 
    191 // test cases for the matcher (in match-all mode)
    192 // typedef struct { char* patt; char* input; Bool xres; } Test;
    193 //
    194 //static Test tests[] =
    195 //  {
    196 //    { ""          ,""   , True },
    197 //    { "a"         ,""   , False },
    198 //    { "a"         ,"b"  , False },
    199 //    { "a"         ,"a"  , True },
    200 //    { "a"         ,"aa" , False },
    201 //    { "*"         ,""   , True },
    202 //    { "**"        ,""   , True },
    203 //    { "*"         ,"abc", True },
    204 //    { "*a"        ,"abc", False },
    205 //    { "*b"        ,"abc", False },
    206 //    { "*bc"       ,"abc", True },
    207 //    { "a*b"       ,"abc", False },
    208 //    { "a*c"       ,"abc", True },
    209 //    { "*c"        ,"abc", True },
    210 //    { "c*c"       ,"abc", False },
    211 //    { "abc*"      ,"abc", True },
    212 //    { "abc**"     ,"abc", True },
    213 //    { "**abc"     ,"abc", True },
    214 //    { "**a*b*c**" ,"abc", True },
    215 //    { "**a*b*d**" ,"abc", False },
    216 //    { "a?b"       ,"abc", False },
    217 //    { "a?c"       ,"abc", True },
    218 //    { "?"         ,""   , False },
    219 //    { "?"         ,"a"  , True },
    220 //    { "?"         ,"ab" , False },
    221 //    { "abcd"      ,"abc", False },
    222 //    { "ab"        ,"abc", False },
    223 //    { NULL        ,NULL , False }
    224 //  };
    225 //
    226 //int main ( void )
    227 //{
    228 //   Test* t;
    229 //   for (t = tests; t->patt; t++) {
    230 //     printf("%-10s %-6s  %s\n",
    231 //            t->patt, t->input,
    232 //            match_string_all((UChar*)t->patt,(UChar*)t->input,True)
    233 //            == t->xres
    234 //               ? "pass" : "FAIL" );
    235 //   }
    236 //   return 0;
    237 //}
    238 
    239 /*--------------------------------------------------------------------*/
    240 /*--- end                                             m_seqmatch.c ---*/
    241 /*--------------------------------------------------------------------*/
    242