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