/[pcsx2_0.9.7]/trunk/3rdparty/wxWidgets/src/common/regex.cpp
ViewVC logotype

Annotation of /trunk/3rdparty/wxWidgets/src/common/regex.cpp

Parent Directory Parent Directory | Revision Log Revision Log


Revision 31 - (hide annotations) (download)
Tue Sep 7 03:24:11 2010 UTC (10 years, 4 months ago) by william
File size: 20124 byte(s)
committing r3113 initial commit again...
1 william 31 ///////////////////////////////////////////////////////////////////////////////
2     // Name: src/common/regex.cpp
3     // Purpose: regular expression matching
4     // Author: Karsten Ballueder and Vadim Zeitlin
5     // Modified by:
6     // Created: 13.07.01
7     // RCS-ID: $Id: regex.cpp 57779 2009-01-02 17:35:16Z PC $
8     // Copyright: (c) 2000 Karsten Ballueder <ballueder@gmx.net>
9     // 2001 Vadim Zeitlin <vadim@wxwindows.org>
10     // Licence: wxWindows licence
11     ///////////////////////////////////////////////////////////////////////////////
12    
13     // ============================================================================
14     // declarations
15     // ============================================================================
16    
17     // ----------------------------------------------------------------------------
18     // headers
19     // ----------------------------------------------------------------------------
20    
21     // For compilers that support precompilation, includes "wx.h".
22     #include "wx/wxprec.h"
23    
24     #ifdef __BORLANDC__
25     #pragma hdrstop
26     #endif
27    
28     #if wxUSE_REGEX
29    
30     #include "wx/regex.h"
31    
32     #ifndef WX_PRECOMP
33     #include "wx/object.h"
34     #include "wx/log.h"
35     #include "wx/intl.h"
36     #endif //WX_PRECOMP
37    
38     // FreeBSD, Watcom and DMars require this, CW doesn't have nor need it.
39     // Others also don't seem to need it. If you have an error related to
40     // (not) including <sys/types.h> please report details to
41     // wx-dev@lists.wxwindows.org
42     #if defined(__UNIX__) || defined(__WATCOMC__) || defined(__DIGITALMARS__)
43     # include <sys/types.h>
44     #endif
45    
46     #include <regex.h>
47    
48     // WXREGEX_USING_BUILTIN defined when using the built-in regex lib
49     // WXREGEX_USING_RE_SEARCH defined when using re_search in the GNU regex lib
50     // WXREGEX_IF_NEED_LEN() wrap the len parameter only used with the built-in
51     // or GNU regex
52     // WXREGEX_CONVERT_TO_MB defined when the regex lib is using chars and
53     // wxChar is wide, so conversion must be done
54     // WXREGEX_CHAR(x) Convert wxChar to wxRegChar
55     //
56     #ifdef __REG_NOFRONT
57     # define WXREGEX_USING_BUILTIN
58     # define WXREGEX_IF_NEED_LEN(x) ,x
59     # define WXREGEX_CHAR(x) x
60     #else
61     # ifdef HAVE_RE_SEARCH
62     # define WXREGEX_IF_NEED_LEN(x) ,x
63     # define WXREGEX_USING_RE_SEARCH
64     # else
65     # define WXREGEX_IF_NEED_LEN(x)
66     # endif
67     # if wxUSE_UNICODE
68     # define WXREGEX_CONVERT_TO_MB
69     # endif
70     # define WXREGEX_CHAR(x) wxConvertWX2MB(x)
71     # define wx_regfree regfree
72     # define wx_regerror regerror
73     #endif
74    
75     // ----------------------------------------------------------------------------
76     // private classes
77     // ----------------------------------------------------------------------------
78    
79     #ifndef WXREGEX_USING_RE_SEARCH
80    
81     // the array of offsets for the matches, the usual POSIX regmatch_t array.
82     class wxRegExMatches
83     {
84     public:
85     typedef regmatch_t *match_type;
86    
87     wxRegExMatches(size_t n) { m_matches = new regmatch_t[n]; }
88     ~wxRegExMatches() { delete [] m_matches; }
89    
90     // we just use casts here because the fields of regmatch_t struct may be 64
91     // bit but we're limited to size_t in our public API and are not going to
92     // change it because operating on strings longer than 4GB using it is
93     // absolutely impractical anyhow
94     size_t Start(size_t n) const
95     {
96     return wx_truncate_cast(size_t, m_matches[n].rm_so);
97     }
98    
99     size_t End(size_t n) const
100     {
101     return wx_truncate_cast(size_t, m_matches[n].rm_eo);
102     }
103    
104     regmatch_t *get() const { return m_matches; }
105    
106     private:
107     regmatch_t *m_matches;
108     };
109    
110     #else // WXREGEX_USING_RE_SEARCH
111    
112     // the array of offsets for the matches, the struct used by the GNU lib
113     class wxRegExMatches
114     {
115     public:
116     typedef re_registers *match_type;
117    
118     wxRegExMatches(size_t n)
119     {
120     m_matches.num_regs = n;
121     m_matches.start = new regoff_t[n];
122     m_matches.end = new regoff_t[n];
123     }
124    
125     ~wxRegExMatches()
126     {
127     delete [] m_matches.start;
128     delete [] m_matches.end;
129     }
130    
131     size_t Start(size_t n) const { return m_matches.start[n]; }
132     size_t End(size_t n) const { return m_matches.end[n]; }
133    
134     re_registers *get() { return &m_matches; }
135    
136     private:
137     re_registers m_matches;
138     };
139    
140     #endif // WXREGEX_USING_RE_SEARCH
141    
142     // the character type used by the regular expression engine
143     #ifndef WXREGEX_CONVERT_TO_MB
144     typedef wxChar wxRegChar;
145     #else
146     typedef char wxRegChar;
147     #endif
148    
149     // the real implementation of wxRegEx
150     class wxRegExImpl
151     {
152     public:
153     // ctor and dtor
154     wxRegExImpl();
155     ~wxRegExImpl();
156    
157     // return true if Compile() had been called successfully
158     bool IsValid() const { return m_isCompiled; }
159    
160     // RE operations
161     bool Compile(const wxString& expr, int flags = 0);
162     bool Matches(const wxRegChar *str, int flags
163     WXREGEX_IF_NEED_LEN(size_t len)) const;
164     bool GetMatch(size_t *start, size_t *len, size_t index = 0) const;
165     size_t GetMatchCount() const;
166     int Replace(wxString *pattern, const wxString& replacement,
167     size_t maxMatches = 0) const;
168    
169     private:
170     // return the string containing the error message for the given err code
171     wxString GetErrorMsg(int errorcode, bool badconv) const;
172    
173     // init the members
174     void Init()
175     {
176     m_isCompiled = false;
177     m_Matches = NULL;
178     m_nMatches = 0;
179     }
180    
181     // free the RE if compiled
182     void Free()
183     {
184     if ( IsValid() )
185     {
186     wx_regfree(&m_RegEx);
187     }
188    
189     delete m_Matches;
190     }
191    
192     // free the RE if any and reinit the members
193     void Reinit()
194     {
195     Free();
196     Init();
197     }
198    
199     // compiled RE
200     regex_t m_RegEx;
201    
202     // the subexpressions data
203     wxRegExMatches *m_Matches;
204     size_t m_nMatches;
205    
206     // true if m_RegEx is valid
207     bool m_isCompiled;
208     };
209    
210    
211     // ============================================================================
212     // implementation
213     // ============================================================================
214    
215     // ----------------------------------------------------------------------------
216     // wxRegExImpl
217     // ----------------------------------------------------------------------------
218    
219     wxRegExImpl::wxRegExImpl()
220     {
221     Init();
222     }
223    
224     wxRegExImpl::~wxRegExImpl()
225     {
226     Free();
227     }
228    
229     wxString wxRegExImpl::GetErrorMsg(int errorcode, bool badconv) const
230     {
231     #ifdef WXREGEX_CONVERT_TO_MB
232     // currently only needed when using system library in Unicode mode
233     if ( badconv )
234     {
235     return _("conversion to 8-bit encoding failed");
236     }
237     #else
238     // 'use' badconv to avoid a compiler warning
239     (void)badconv;
240     #endif
241    
242     wxString szError;
243    
244     // first get the string length needed
245     int len = wx_regerror(errorcode, &m_RegEx, NULL, 0);
246     if ( len > 0 )
247     {
248     char* szcmbError = new char[++len];
249    
250     (void)wx_regerror(errorcode, &m_RegEx, szcmbError, len);
251    
252     szError = wxConvertMB2WX(szcmbError);
253     delete [] szcmbError;
254     }
255     else // regerror() returned 0
256     {
257     szError = _("unknown error");
258     }
259    
260     return szError;
261     }
262    
263     bool wxRegExImpl::Compile(const wxString& expr, int flags)
264     {
265     Reinit();
266    
267     #ifdef WX_NO_REGEX_ADVANCED
268     # define FLAVORS wxRE_BASIC
269     #else
270     # define FLAVORS (wxRE_ADVANCED | wxRE_BASIC)
271     wxASSERT_MSG( (flags & FLAVORS) != FLAVORS,
272     _T("incompatible flags in wxRegEx::Compile") );
273     #endif
274     wxASSERT_MSG( !(flags & ~(FLAVORS | wxRE_ICASE | wxRE_NOSUB | wxRE_NEWLINE)),
275     _T("unrecognized flags in wxRegEx::Compile") );
276    
277     // translate our flags to regcomp() ones
278     int flagsRE = 0;
279     if ( !(flags & wxRE_BASIC) )
280     {
281     #ifndef WX_NO_REGEX_ADVANCED
282     if (flags & wxRE_ADVANCED)
283     flagsRE |= REG_ADVANCED;
284     else
285     #endif
286     flagsRE |= REG_EXTENDED;
287     }
288    
289     if ( flags & wxRE_ICASE )
290     flagsRE |= REG_ICASE;
291     if ( flags & wxRE_NOSUB )
292     flagsRE |= REG_NOSUB;
293     if ( flags & wxRE_NEWLINE )
294     flagsRE |= REG_NEWLINE;
295    
296     // compile it
297     #ifdef WXREGEX_USING_BUILTIN
298     bool conv = true;
299     int errorcode = wx_re_comp(&m_RegEx, expr, expr.length(), flagsRE);
300     #else
301     const wxWX2MBbuf conv = expr.mbc_str();
302     int errorcode = conv ? regcomp(&m_RegEx, conv, flagsRE) : REG_BADPAT;
303     #endif
304    
305     if ( errorcode )
306     {
307     wxLogError(_("Invalid regular expression '%s': %s"),
308     expr.c_str(), GetErrorMsg(errorcode, !conv).c_str());
309    
310     m_isCompiled = false;
311     }
312     else // ok
313     {
314     // don't allocate the matches array now, but do it later if necessary
315     if ( flags & wxRE_NOSUB )
316     {
317     // we don't need it at all
318     m_nMatches = 0;
319     }
320     else
321     {
322     // we will alloc the array later (only if really needed) but count
323     // the number of sub-expressions in the regex right now
324    
325     // there is always one for the whole expression
326     m_nMatches = 1;
327    
328     // and some more for bracketed subexperessions
329     for ( const wxChar *cptr = expr.c_str(); *cptr; cptr++ )
330     {
331     if ( *cptr == _T('\\') )
332     {
333     // in basic RE syntax groups are inside \(...\)
334     if ( *++cptr == _T('(') && (flags & wxRE_BASIC) )
335     {
336     m_nMatches++;
337     }
338     }
339     else if ( *cptr == _T('(') && !(flags & wxRE_BASIC) )
340     {
341     // we know that the previous character is not an unquoted
342     // backslash because it would have been eaten above, so we
343     // have a bare '(' and this indicates a group start for the
344     // extended syntax. '(?' is used for extensions by perl-
345     // like REs (e.g. advanced), and is not valid for POSIX
346     // extended, so ignore them always.
347     if ( cptr[1] != _T('?') )
348     m_nMatches++;
349     }
350     }
351     }
352    
353     m_isCompiled = true;
354     }
355    
356     return IsValid();
357     }
358    
359     #ifdef WXREGEX_USING_RE_SEARCH
360    
361     // On GNU, regexec is implemented as a wrapper around re_search. re_search
362     // requires a length parameter which the POSIX regexec does not have,
363     // therefore regexec must do a strlen on the search text each time it is
364     // called. This can drastically affect performance when matching is done in
365     // a loop along a string, such as during a search and replace. Therefore if
366     // re_search is detected by configure, it is used directly.
367     //
368     static int ReSearch(const regex_t *preg,
369     const char *text,
370     size_t len,
371     re_registers *matches,
372     int eflags)
373     {
374     regex_t *pattern = wx_const_cast(regex_t*, preg);
375    
376     pattern->not_bol = (eflags & REG_NOTBOL) != 0;
377     pattern->not_eol = (eflags & REG_NOTEOL) != 0;
378     pattern->regs_allocated = REGS_FIXED;
379    
380     int ret = re_search(pattern, text, len, 0, len, matches);
381     return ret >= 0 ? 0 : REG_NOMATCH;
382     }
383    
384     #endif // WXREGEX_USING_RE_SEARCH
385    
386     bool wxRegExImpl::Matches(const wxRegChar *str,
387     int flags
388     WXREGEX_IF_NEED_LEN(size_t len)) const
389     {
390     wxCHECK_MSG( IsValid(), false, _T("must successfully Compile() first") );
391    
392     // translate our flags to regexec() ones
393     wxASSERT_MSG( !(flags & ~(wxRE_NOTBOL | wxRE_NOTEOL)),
394     _T("unrecognized flags in wxRegEx::Matches") );
395    
396     int flagsRE = 0;
397     if ( flags & wxRE_NOTBOL )
398     flagsRE |= REG_NOTBOL;
399     if ( flags & wxRE_NOTEOL )
400     flagsRE |= REG_NOTEOL;
401    
402     // allocate matches array if needed
403     wxRegExImpl *self = wxConstCast(this, wxRegExImpl);
404     if ( !m_Matches && m_nMatches )
405     {
406     self->m_Matches = new wxRegExMatches(m_nMatches);
407     }
408    
409     wxRegExMatches::match_type matches = m_Matches ? m_Matches->get() : NULL;
410    
411     // do match it
412     #if defined WXREGEX_USING_BUILTIN
413     int rc = wx_re_exec(&self->m_RegEx, str, len, NULL, m_nMatches, matches, flagsRE);
414     #elif defined WXREGEX_USING_RE_SEARCH
415     int rc = str ? ReSearch(&self->m_RegEx, str, len, matches, flagsRE) : REG_BADPAT;
416     #else
417     int rc = str ? regexec(&self->m_RegEx, str, m_nMatches, matches, flagsRE) : REG_BADPAT;
418     #endif
419    
420     switch ( rc )
421     {
422     case 0:
423     // matched successfully
424     return true;
425    
426     default:
427     // an error occurred
428     wxLogError(_("Failed to find match for regular expression: %s"),
429     GetErrorMsg(rc, !str).c_str());
430     // fall through
431    
432     case REG_NOMATCH:
433     // no match
434     return false;
435     }
436     }
437    
438     bool wxRegExImpl::GetMatch(size_t *start, size_t *len, size_t index) const
439     {
440     wxCHECK_MSG( IsValid(), false, _T("must successfully Compile() first") );
441     wxCHECK_MSG( m_nMatches, false, _T("can't use with wxRE_NOSUB") );
442     wxCHECK_MSG( m_Matches, false, _T("must call Matches() first") );
443     wxCHECK_MSG( index < m_nMatches, false, _T("invalid match index") );
444    
445     if ( start )
446     *start = m_Matches->Start(index);
447     if ( len )
448     *len = m_Matches->End(index) - m_Matches->Start(index);
449    
450     return true;
451     }
452    
453     size_t wxRegExImpl::GetMatchCount() const
454     {
455     wxCHECK_MSG( IsValid(), 0, _T("must successfully Compile() first") );
456     wxCHECK_MSG( m_nMatches, 0, _T("can't use with wxRE_NOSUB") );
457    
458     return m_nMatches;
459     }
460    
461     int wxRegExImpl::Replace(wxString *text,
462     const wxString& replacement,
463     size_t maxMatches) const
464     {
465     wxCHECK_MSG( text, wxNOT_FOUND, _T("NULL text in wxRegEx::Replace") );
466     wxCHECK_MSG( IsValid(), wxNOT_FOUND, _T("must successfully Compile() first") );
467    
468     // the input string
469     #ifndef WXREGEX_CONVERT_TO_MB
470     const wxChar *textstr = text->c_str();
471     size_t textlen = text->length();
472     #else
473     const wxWX2MBbuf textstr = WXREGEX_CHAR(*text);
474     if (!textstr)
475     {
476     wxLogError(_("Failed to find match for regular expression: %s"),
477     GetErrorMsg(0, true).c_str());
478     return 0;
479     }
480     size_t textlen = strlen(textstr);
481     text->clear();
482     #endif
483    
484     // the replacement text
485     wxString textNew;
486    
487     // the result, allow 25% extra
488     wxString result;
489     result.reserve(5 * textlen / 4);
490    
491     // attempt at optimization: don't iterate over the string if it doesn't
492     // contain back references at all
493     bool mayHaveBackrefs =
494     replacement.find_first_of(_T("\\&")) != wxString::npos;
495    
496     if ( !mayHaveBackrefs )
497     {
498     textNew = replacement;
499     }
500    
501     // the position where we start looking for the match
502     size_t matchStart = 0;
503    
504     // number of replacement made: we won't make more than maxMatches of them
505     // (unless maxMatches is 0 which doesn't limit the number of replacements)
506     size_t countRepl = 0;
507    
508     // note that "^" shouldn't match after the first call to Matches() so we
509     // use wxRE_NOTBOL to prevent it from happening
510     while ( (!maxMatches || countRepl < maxMatches) &&
511     Matches(textstr + matchStart,
512     countRepl ? wxRE_NOTBOL : 0
513     WXREGEX_IF_NEED_LEN(textlen - matchStart)) )
514     {
515     // the string possibly contains back references: we need to calculate
516     // the replacement text anew after each match
517     if ( mayHaveBackrefs )
518     {
519     mayHaveBackrefs = false;
520     textNew.clear();
521     textNew.reserve(replacement.length());
522    
523     for ( const wxChar *p = replacement.c_str(); *p; p++ )
524     {
525     size_t index = (size_t)-1;
526    
527     if ( *p == _T('\\') )
528     {
529     if ( wxIsdigit(*++p) )
530     {
531     // back reference
532     wxChar *end;
533     index = (size_t)wxStrtoul(p, &end, 10);
534     p = end - 1; // -1 to compensate for p++ in the loop
535     }
536     //else: backslash used as escape character
537     }
538     else if ( *p == _T('&') )
539     {
540     // treat this as "\0" for compatbility with ed and such
541     index = 0;
542     }
543    
544     // do we have a back reference?
545     if ( index != (size_t)-1 )
546     {
547     // yes, get its text
548     size_t start, len;
549     if ( !GetMatch(&start, &len, index) )
550     {
551     wxFAIL_MSG( _T("invalid back reference") );
552    
553     // just eat it...
554     }
555     else
556     {
557     textNew += wxString(textstr + matchStart + start,
558     *wxConvCurrent, len);
559    
560     mayHaveBackrefs = true;
561     }
562     }
563     else // ordinary character
564     {
565     textNew += *p;
566     }
567     }
568     }
569    
570     size_t start, len;
571     if ( !GetMatch(&start, &len) )
572     {
573     // we did have match as Matches() returned true above!
574     wxFAIL_MSG( _T("internal logic error in wxRegEx::Replace") );
575    
576     return wxNOT_FOUND;
577     }
578    
579     // an insurance against implementations that don't grow exponentially
580     // to ensure building the result takes linear time
581     if (result.capacity() < result.length() + start + textNew.length())
582     result.reserve(2 * result.length());
583    
584     #ifndef WXREGEX_CONVERT_TO_MB
585     result.append(*text, matchStart, start);
586     #else
587     result.append(wxString(textstr + matchStart, *wxConvCurrent, start));
588     #endif
589     matchStart += start;
590     result.append(textNew);
591    
592     countRepl++;
593    
594     matchStart += len;
595     }
596    
597     #ifndef WXREGEX_CONVERT_TO_MB
598     result.append(*text, matchStart, wxString::npos);
599     #else
600     result.append(wxString(textstr + matchStart, *wxConvCurrent));
601     #endif
602     *text = result;
603    
604     return countRepl;
605     }
606    
607     // ----------------------------------------------------------------------------
608     // wxRegEx: all methods are mostly forwarded to wxRegExImpl
609     // ----------------------------------------------------------------------------
610    
611     void wxRegEx::Init()
612     {
613     m_impl = NULL;
614     }
615    
616     wxRegEx::~wxRegEx()
617     {
618     delete m_impl;
619     }
620    
621     bool wxRegEx::Compile(const wxString& expr, int flags)
622     {
623     if ( !m_impl )
624     {
625     m_impl = new wxRegExImpl;
626     }
627    
628     if ( !m_impl->Compile(expr, flags) )
629     {
630     // error message already given in wxRegExImpl::Compile
631     delete m_impl;
632     m_impl = NULL;
633    
634     return false;
635     }
636    
637     return true;
638     }
639    
640     bool wxRegEx::Matches(const wxChar *str, int flags, size_t len) const
641     {
642     wxCHECK_MSG( IsValid(), false, _T("must successfully Compile() first") );
643     (void)len;
644    
645     return m_impl->Matches(WXREGEX_CHAR(str), flags WXREGEX_IF_NEED_LEN(len));
646     }
647    
648     bool wxRegEx::Matches(const wxChar *str, int flags) const
649     {
650     wxCHECK_MSG( IsValid(), false, _T("must successfully Compile() first") );
651    
652     return m_impl->Matches(WXREGEX_CHAR(str),
653     flags
654     WXREGEX_IF_NEED_LEN(wxStrlen(str)));
655     }
656    
657     bool wxRegEx::GetMatch(size_t *start, size_t *len, size_t index) const
658     {
659     wxCHECK_MSG( IsValid(), false, _T("must successfully Compile() first") );
660    
661     return m_impl->GetMatch(start, len, index);
662     }
663    
664     wxString wxRegEx::GetMatch(const wxString& text, size_t index) const
665     {
666     size_t start, len;
667     if ( !GetMatch(&start, &len, index) )
668     return wxEmptyString;
669    
670     return text.Mid(start, len);
671     }
672    
673     size_t wxRegEx::GetMatchCount() const
674     {
675     wxCHECK_MSG( IsValid(), 0, _T("must successfully Compile() first") );
676    
677     return m_impl->GetMatchCount();
678     }
679    
680     int wxRegEx::Replace(wxString *pattern,
681     const wxString& replacement,
682     size_t maxMatches) const
683     {
684     wxCHECK_MSG( IsValid(), wxNOT_FOUND, _T("must successfully Compile() first") );
685    
686     return m_impl->Replace(pattern, replacement, maxMatches);
687     }
688    
689     #endif // wxUSE_REGEX

  ViewVC Help
Powered by ViewVC 1.1.22