src/common/regex.cpp

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