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