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