| |
| /*--------------------------------------------------------------------*/ |
| /*--- A simple sequence matching facility. ---*/ |
| /*--- m_seqmatch.c ---*/ |
| /*--------------------------------------------------------------------*/ |
| |
| /* |
| This file is part of Valgrind, a dynamic binary instrumentation |
| framework. |
| |
| Copyright (C) 2008-2011 OpenWorks Ltd |
| info@open-works.co.uk |
| |
| This program is free software; you can redistribute it and/or |
| modify it under the terms of the GNU General Public License as |
| published by the Free Software Foundation; either version 2 of the |
| License, or (at your option) any later version. |
| |
| This program is distributed in the hope that it will be useful, but |
| WITHOUT ANY WARRANTY; without even the implied warranty of |
| MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
| General Public License for more details. |
| |
| You should have received a copy of the GNU General Public License |
| along with this program; if not, write to the Free Software |
| Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA |
| 02111-1307, USA. |
| |
| The GNU General Public License is contained in the file COPYING. |
| */ |
| |
| #include "pub_core_basics.h" |
| #include "pub_core_libcassert.h" |
| #include "pub_core_libcbase.h" // VG_(strlen) |
| #include "pub_core_seqmatch.h" // self |
| |
| /* --------------------------------------------------------------------- |
| A simple sequence matching facility |
| ------------------------------------------------------------------ */ |
| |
| /* See detailed comment in include/pub_tool_seqmatch.h about this. */ |
| Bool VG_(generic_match) ( |
| Bool matchAll, |
| void* patt, SizeT szbPatt, UWord nPatt, UWord ixPatt, |
| void* input, SizeT szbInput, UWord nInput, UWord ixInput, |
| Bool (*pIsStar)(void*), |
| Bool (*pIsQuery)(void*), |
| Bool (*pattEQinp)(void*,void*) |
| ) |
| { |
| /* This is the spec, written in my favourite formal specification |
| language. It specifies non-greedy matching of '*'s. |
| |
| ma ('*':ps) (i:is) = ma ps (i:is) || ma ('*':ps) is |
| ma ('*':ps) [] = ma ps [] |
| |
| ma ('?':ps) (i:is) = ma ps is |
| ma ('?':ps) [] = False |
| |
| ma (p:ps) (i:is) = p == i && ma ps is |
| |
| ma (p:ps) [] = False |
| ma [] (i:is) = False -- m-all, True for m-prefix |
| ma [] [] = True |
| */ |
| Bool havePatt, haveInput; |
| void *currPatt, *currInput; |
| tailcall: |
| vg_assert(nPatt >= 0 && nPatt < 1000000); /* arbitrary */ |
| vg_assert(nInput >= 0 && nInput < 1000000); /* arbitrary */ |
| vg_assert(ixPatt >= 0 && ixPatt <= nPatt); |
| vg_assert(ixInput >= 0 && ixInput <= nInput); |
| |
| havePatt = ixPatt < nPatt; |
| haveInput = ixInput < nInput; |
| |
| /* No specific need to set NULL when !have{Patt,Input}, but guards |
| against inadvertantly dereferencing an out of range pointer to |
| the pattern or input arrays. */ |
| currPatt = havePatt ? ((Char*)patt) + szbPatt * ixPatt : NULL; |
| currInput = haveInput ? ((Char*)input) + szbInput * ixInput : NULL; |
| |
| // Deal with the complex case first: wildcards. Do frugal |
| // matching. When encountering a '*', first skip no characters |
| // at all, and see if the rest of the match still works. Only if |
| // that fails do we then skip a character, and retry at the next |
| // position. |
| // |
| // ma ('*':ps) (i:is) = ma ps (i:is) || ma ('*':ps) is |
| // |
| // If we're out of input, check the rest of the pattern matches |
| // the empty input. This really means can only be be empty or |
| // composed entirely of '*'s. |
| // |
| // ma ('*':ps) [] = ma ps [] |
| // |
| if (havePatt && pIsStar(currPatt)) { |
| if (haveInput) { |
| // ma ('*':ps) (i:is) = ma ps (i:is) || ma ('*':ps) is |
| // we unavoidably have to make a real recursive call for the |
| // first half of the OR, since this isn't straight tail-recursion. |
| if (VG_(generic_match)( matchAll, |
| patt, szbPatt, nPatt, ixPatt+1, |
| input,szbInput,nInput, ixInput+0, |
| pIsStar,pIsQuery,pattEQinp) ) { |
| return True; |
| } |
| // but we can tail-recurse for the second call |
| ixInput++; goto tailcall; |
| } else { |
| // ma ('*':ps) [] = ma ps [] |
| ixPatt++; goto tailcall; |
| } |
| } |
| |
| // simpler cases now. Deal with '?' wildcards. |
| // |
| // ma ('?':ps) (i:is) = ma ps is |
| // ma ('?':ps) [] = False |
| if (havePatt && pIsQuery(currPatt)) { |
| if (haveInput) { |
| ixPatt++; ixInput++; goto tailcall; |
| } else { |
| return False; |
| } |
| } |
| |
| // obvious case with literal chars in the pattern |
| // |
| // ma (p:ps) (i:is) = p == i && ma ps is |
| if (havePatt && haveInput) { |
| if (!pattEQinp(currPatt,currInput)) return False; |
| ixPatt++; ixInput++; goto tailcall; |
| } |
| |
| // if we run out of input before we run out of pattern, we must fail |
| // ma (p:ps) [] = False |
| if (havePatt && !haveInput) return False; |
| |
| // if we run out of pattern before we run out of input, the |
| // verdict depends on the matching mode. If we are trying to |
| // match exactly (the pattern must consume the entire input) |
| // then the outcome is failure. However, if we're merely attempting |
| // to match some prefix of the input, then we have been successful. |
| // |
| // ma [] (i:is) = False -- m-all, True for m-prefix |
| if (!havePatt && haveInput) { |
| return matchAll ? False // match-all |
| : True; // match-prefix |
| } |
| |
| // finally, if both sequence and input are both completely |
| // consumed, then we were successful, regardless of matching mode. |
| if (!havePatt && !haveInput) return True; |
| |
| // end of cases |
| vg_assert(0); |
| } |
| |
| |
| /* And a parameterization of the above, to make it do |
| string matching. |
| */ |
| static Bool charIsStar ( void* pV ) { return *(Char*)pV == '*'; } |
| static Bool charIsQuery ( void* pV ) { return *(Char*)pV == '?'; } |
| static Bool char_p_EQ_i ( void* pV, void* cV ) { |
| Char p = *(Char*)pV; |
| Char c = *(Char*)cV; |
| vg_assert(p != '*' && p != '?'); |
| return p == c; |
| } |
| Bool VG_(string_match) ( const Char* patt, const Char* input ) |
| { |
| return VG_(generic_match)( |
| True/* match-all */, |
| (void*)patt, sizeof(UChar), VG_(strlen)(patt), 0, |
| (void*)input, sizeof(UChar), VG_(strlen)(input), 0, |
| charIsStar, charIsQuery, char_p_EQ_i |
| ); |
| } |
| |
| |
| // test cases for the matcher (in match-all mode) |
| // typedef struct { char* patt; char* input; Bool xres; } Test; |
| // |
| //static Test tests[] = |
| // { |
| // { "" ,"" , True }, |
| // { "a" ,"" , False }, |
| // { "a" ,"b" , False }, |
| // { "a" ,"a" , True }, |
| // { "a" ,"aa" , False }, |
| // { "*" ,"" , True }, |
| // { "**" ,"" , True }, |
| // { "*" ,"abc", True }, |
| // { "*a" ,"abc", False }, |
| // { "*b" ,"abc", False }, |
| // { "*bc" ,"abc", True }, |
| // { "a*b" ,"abc", False }, |
| // { "a*c" ,"abc", True }, |
| // { "*c" ,"abc", True }, |
| // { "c*c" ,"abc", False }, |
| // { "abc*" ,"abc", True }, |
| // { "abc**" ,"abc", True }, |
| // { "**abc" ,"abc", True }, |
| // { "**a*b*c**" ,"abc", True }, |
| // { "**a*b*d**" ,"abc", False }, |
| // { "a?b" ,"abc", False }, |
| // { "a?c" ,"abc", True }, |
| // { "?" ,"" , False }, |
| // { "?" ,"a" , True }, |
| // { "?" ,"ab" , False }, |
| // { "abcd" ,"abc", False }, |
| // { "ab" ,"abc", False }, |
| // { NULL ,NULL , False } |
| // }; |
| // |
| //int main ( void ) |
| //{ |
| // Test* t; |
| // for (t = tests; t->patt; t++) { |
| // printf("%10s %6s %s\n", |
| // t->patt, t->input, |
| // match_string_all((UChar*)t->patt,(UChar*)t->input,True) |
| // == t->xres |
| // ? "pass" : "FAIL" ); |
| // } |
| // return 0; |
| //} |
| |
| /*--------------------------------------------------------------------*/ |
| /*--- end m_seqmatch.c ---*/ |
| /*--------------------------------------------------------------------*/ |
