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 #ifndef WX_PRECOMP
  31     #include "wx/object.h"
  32     #include "wx/string.h"
  33     #include "wx/log.h"
  34     #include "wx/intl.h"
  35     #include "wx/crt.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 #include "wx/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                   _T("incompatible flags in wxRegEx::Compile") );
 278 #endif
 279     wxASSERT_MSG( !(flags & ~(FLAVORS | wxRE_ICASE | wxRE_NOSUB | wxRE_NEWLINE)),
 280                   _T("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 == _T('\\') )
 339                 {
 340                     // in basic RE syntax groups are inside \(...\)
 341                     if ( *++cptr == _T('(') && (flags & wxRE_BASIC) )
 342                     {
 343                         m_nMatches++;
 344                     }
 345                 }
 346                 else if ( *cptr == _T('(') && !(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] != _T('?') )
 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 = wx_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, _T("must successfully Compile() first") );
 398
 399     // translate our flags to regexec() ones
 400     wxASSERT_MSG( !(flags & ~(wxRE_NOTBOL | wxRE_NOTEOL)),
 401                   _T("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, _T("must successfully Compile() first") );
 448     wxCHECK_MSG( m_nMatches, false, _T("can't use with wxRE_NOSUB") );
 449     wxCHECK_MSG( m_Matches, false, _T("must call Matches() first") );
 450     wxCHECK_MSG( index < m_nMatches, false, _T("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, _T("must successfully Compile() first") );
 463     wxCHECK_MSG( m_nMatches, 0, _T("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, _T("NULL text in wxRegEx::Replace") );
 473     wxCHECK_MSG( IsValid(), wxNOT_FOUND, _T("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(_T("\\&")) != 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 #ifndef WXREGEX_CONVERT_TO_MB
 519             Matches(textstr + matchStart,
 520 #else
 521             Matches(textstr.data() + matchStart,
 522 #endif
 523                     countRepl ? wxRE_NOTBOL : 0
 524                     WXREGEX_IF_NEED_LEN(textlen - matchStart)) )
 525     {
 526         // the string possibly contains back references: we need to calculate
 527         // the replacement text anew after each match
 528         if ( mayHaveBackrefs )
 529         {
 530             mayHaveBackrefs = false;
 531             textNew.clear();
 532             textNew.reserve(replacement.length());
 533
 534             for ( const wxChar *p = replacement.c_str(); *p; p++ )
 535             {
 536                 size_t index = (size_t)-1;
 537
 538                 if ( *p == _T('\\') )
 539                 {
 540                     if ( wxIsdigit(*++p) )
 541                     {
 542                         // back reference
 543                         wxChar *end;
 544                         index = (size_t)wxStrtoul(p, &end, 10);
 545                         p = end - 1; // -1 to compensate for p++ in the loop
 546                     }
 547                     //else: backslash used as escape character
 548                 }
 549                 else if ( *p == _T('&') )
 550                 {
 551                     // treat this as "\0" for compatbility with ed and such
 552                     index = 0;
 553                 }
 554
 555                 // do we have a back reference?
 556                 if ( index != (size_t)-1 )
 557                 {
 558                     // yes, get its text
 559                     size_t start, len;
 560                     if ( !GetMatch(&start, &len, index) )
 561                     {
 562                         wxFAIL_MSG( _T("invalid back reference") );
 563
 564                         // just eat it...
 565                     }
 566                     else
 567                     {
 568 #ifndef WXREGEX_CONVERT_TO_MB
 569                         textNew += wxString(textstr + matchStart + start,
 570 #else
 571                         textNew += wxString(textstr.data() + matchStart +
 572                                             start,
 573 #endif
 574                                             *wxConvCurrent, len);
 575
 576                         mayHaveBackrefs = true;
 577                     }
 578                 }
 579                 else // ordinary character
 580                 {
 581                     textNew += *p;
 582                 }
 583             }
 584         }
 585
 586         size_t start, len;
 587         if ( !GetMatch(&start, &len) )
 588         {
 589             // we did have match as Matches() returned true above!
 590             wxFAIL_MSG( _T("internal logic error in wxRegEx::Replace") );
 591
 592             return wxNOT_FOUND;
 593         }
 594
 595         // an insurance against implementations that don't grow exponentially
 596         // to ensure building the result takes linear time
 597         if (result.capacity() < result.length() + start + textNew.length())
 598             result.reserve(2 * result.length());
 599
 600 #ifndef WXREGEX_CONVERT_TO_MB
 601         result.append(*text, matchStart, start);
 602 #else
 603         result.append(wxString(textstr.data() + matchStart, *wxConvCurrent,
 604                                start));
 605 #endif
 606         matchStart += start;
 607         result.append(textNew);
 608
 609         countRepl++;
 610
 611         matchStart += len;
 612     }
 613
 614 #ifndef WXREGEX_CONVERT_TO_MB
 615     result.append(*text, matchStart, wxString::npos);
 616 #else
 617     result.append(wxString(textstr.data() + matchStart, *wxConvCurrent));
 618 #endif
 619     *text = result;
 620
 621     return countRepl;
 622 }
 623
 624 // ----------------------------------------------------------------------------
 625 // wxRegEx: all methods are mostly forwarded to wxRegExImpl
 626 // ----------------------------------------------------------------------------
 627
 628 void wxRegEx::Init()
 629 {
 630     m_impl = NULL;
 631 }
 632
 633 wxRegEx::~wxRegEx()
 634 {
 635     delete m_impl;
 636 }
 637
 638 bool wxRegEx::Compile(const wxString& expr, int flags)
 639 {
 640     if ( !m_impl )
 641     {
 642         m_impl = new wxRegExImpl;
 643     }
 644
 645     if ( !m_impl->Compile(expr, flags) )
 646     {
 647         // error message already given in wxRegExImpl::Compile
 648         delete m_impl;
 649         m_impl = NULL;
 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, _T("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, _T("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, _T("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, _T("must successfully Compile() first") );
 693
 694     return m_impl->Replace(pattern, replacement, maxMatches);
 695 }
 696
 697 #endif // wxUSE_REGEX