1 ///////////////////////////////////////////////////////////////////////////////
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
wxRegExMatches(size_t n)87 wxRegExMatches(size_t n) { m_matches = new regmatch_t[n]; }
~wxRegExMatches()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
Start(size_t n) const94 size_t Start(size_t n) const
95 {
96 return wx_truncate_cast(size_t, m_matches[n].rm_so);
97 }
98
End(size_t n) const99 size_t End(size_t n) const
100 {
101 return wx_truncate_cast(size_t, m_matches[n].rm_eo);
102 }
103
get() const104 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
wxRegExMatches(size_t n)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
~wxRegExMatches()125 ~wxRegExMatches()
126 {
127 delete [] m_matches.start;
128 delete [] m_matches.end;
129 }
130
Start(size_t n) const131 size_t Start(size_t n) const { return m_matches.start[n]; }
End(size_t n) const132 size_t End(size_t n) const { return m_matches.end[n]; }
133
get()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
IsValid() const158 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
Init()174 void Init()
175 {
176 m_isCompiled = false;
177 m_Matches = NULL;
178 m_nMatches = 0;
179 }
180
181 // free the RE if compiled
Free()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
Reinit()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
wxRegExImpl()219 wxRegExImpl::wxRegExImpl()
220 {
221 Init();
222 }
223
~wxRegExImpl()224 wxRegExImpl::~wxRegExImpl()
225 {
226 Free();
227 }
228
GetErrorMsg(int errorcode,bool badconv) const229 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
Compile(const wxString & expr,int flags)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 //
ReSearch(const regex_t * preg,const char * text,size_t len,re_registers * matches,int eflags)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
Matches(const wxRegChar * str,int flags WXREGEX_IF_NEED_LEN (size_t len)) const386 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
GetMatch(size_t * start,size_t * len,size_t index) const438 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
GetMatchCount() const453 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
Replace(wxString * text,const wxString & replacement,size_t maxMatches) const461 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
Init()611 void wxRegEx::Init()
612 {
613 m_impl = NULL;
614 }
615
~wxRegEx()616 wxRegEx::~wxRegEx()
617 {
618 delete m_impl;
619 }
620
Compile(const wxString & expr,int flags)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
Matches(const wxChar * str,int flags,size_t len) const640 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
Matches(const wxChar * str,int flags) const648 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
GetMatch(size_t * start,size_t * len,size_t index) const657 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
GetMatch(const wxString & text,size_t index) const664 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
GetMatchCount() const673 size_t wxRegEx::GetMatchCount() const
674 {
675 wxCHECK_MSG( IsValid(), 0, _T("must successfully Compile() first") );
676
677 return m_impl->GetMatchCount();
678 }
679
Replace(wxString * pattern,const wxString & replacement,size_t maxMatches) const680 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
690