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-2013 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   Ditto for input/nInput/szbInput/ixInput.
62
63   pIsStar should return True iff the pointed-to pattern element is
64   conceptually a '*'.
65
66   pIsQuery should return True iff the pointed-to-pattern element is
67   conceptually a '?'.
68
69   pattEQinp takes a pointer to a pattern element and a pointer to an
70   input element.  It should return True iff they are considered
71   equal.  Note that the pattern element is guaranteed to be neither
72   (conceptually) '*' nor '?', so it must be a literal (in the sense
73   that all the input sequence elements are literal).
74
75   input might be lazily constructed when pattEQinp is called.
76   For lazily constructing the input element, the two last arguments
77   of pattEQinp are the inputCompleter and the index of the input
78   element to complete.
79   inputCompleter can be NULL.
80*/
81Bool VG_(generic_match) (
82        Bool matchAll,
83        const void* patt,  SizeT szbPatt,  UWord nPatt,  UWord ixPatt,
84        const void* input, SizeT szbInput, UWord nInput, UWord ixInput,
85        Bool (*pIsStar)(const void*),
86        Bool (*pIsQuery)(const void*),
87        Bool (*pattEQinp)(const void*,const void*,void*,UWord),
88        void* inputCompleter
89     );
90
91/* Mini-regexp function.  Searches for 'pat' in 'str'.  Supports
92   meta-symbols '*' and '?'.  There is no way to escape meta-symbols
93   in the pattern. */
94Bool VG_(string_match) ( const HChar* pat, const HChar* str );
95
96#endif   // __PUB_TOOL_SEQMATCH_H
97
98/*--------------------------------------------------------------------*/
99/*--- end                                      pub_tool_seqmatch.h ---*/
100/*--------------------------------------------------------------------*/
101