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