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 #if defined(__GNUG__) && !defined(NO_GCC_PRAGMA)
  22     #pragma implementation "regex.h"
  23 #endif
  24
  25 // For compilers that support precompilation, includes "wx.h".
  26 #include "wx/wxprec.h"
  27
  28 #ifdef __BORLANDC__
  29     #pragma hdrstop
  30 #endif
  31
  32 #if wxUSE_REGEX
  33
  34 #ifndef WX_PRECOMP
  35     #include "wx/object.h"
  36     #include "wx/string.h"
  37     #include "wx/log.h"
  38     #include "wx/intl.h"
  39 #endif //WX_PRECOMP
  40
  41 // FreeBSD, Watcom and DMars require this, CW doesn't have nor need it.
  42 // Others also don't seem to need it. If you have an error related to
  43 // (not) including <sys/types.h> please report details to
  44 // wx-dev@lists.wxwindows.org
  45 #if defined(__UNIX__) || defined(__WATCOMC__) || defined(__DIGITALMARS__)
  46 #   include <sys/types.h>
  47 #endif
  48
  49 #include <regex.h>
  50 #include "wx/regex.h"
  51
  52 // ----------------------------------------------------------------------------
  53 // private classes
  54 // ----------------------------------------------------------------------------
  55
  56 // the real implementation of wxRegEx
  57 class wxRegExImpl
  58 {
  59 public:
  60     // ctor and dtor
  61     wxRegExImpl();
  62     ~wxRegExImpl();
  63
  64     // return TRUE if Compile() had been called successfully
  65     bool IsValid() const { return m_isCompiled; }
  66
  67     // RE operations
  68     bool Compile(const wxString& expr, int flags = 0);
  69     bool Matches(const wxChar *str, int flags = 0) const;
  70     bool GetMatch(size_t *start, size_t *len, size_t index = 0) const;
  71     size_t GetMatchCount() const;
  72     int Replace(wxString *pattern, const wxString& replacement,
  73                 size_t maxMatches = 0) const;
  74
  75 private:
  76     // return the string containing the error message for the given err code
  77     wxString GetErrorMsg(int errorcode, bool badconv) const;
  78
  79     // init the members
  80     void Init()
  81     {
  82         m_isCompiled = FALSE;
  83         m_Matches = NULL;
  84         m_nMatches = 0;
  85     }
  86
  87     // free the RE if compiled
  88     void Free()
  89     {
  90         if ( IsValid() )
  91         {
  92             regfree(&m_RegEx);
  93         }
  94
  95         delete [] m_Matches;
  96     }
  97
  98     // free the RE if any and reinit the members
  99     void Reinit()
 100     {
 101         Free();
 102         Init();
 103     }
 104
 105
 106     // compiled RE
 107     regex_t     m_RegEx;
 108
 109     // the subexpressions data
 110     regmatch_t *m_Matches;
 111     size_t      m_nMatches;
 112
 113     // TRUE if m_RegEx is valid
 114     bool        m_isCompiled;
 115 };
 116
 117 // ============================================================================
 118 // implementation
 119 // ============================================================================
 120
 121 // ----------------------------------------------------------------------------
 122 // wxRegExImpl
 123 // ----------------------------------------------------------------------------
 124
 125 wxRegExImpl::wxRegExImpl()
 126 {
 127     Init();
 128 }
 129
 130 wxRegExImpl::~wxRegExImpl()
 131 {
 132     Free();
 133 }
 134
 135 wxString wxRegExImpl::GetErrorMsg(int errorcode, bool badconv) const
 136 {
 137 #if wxUSE_UNICODE && !defined(__REG_NOFRONT)
 138     // currently only needed when using system library in Unicode mode
 139     if ( badconv )
 140     {
 141         return _("conversion to 8-bit encoding failed");
 142     }
 143 #else
 144     // 'use' badconv to avoid a compiler warning
 145     (void)badconv;
 146 #endif
 147
 148     wxString szError;
 149
 150     // first get the string length needed
 151     int len = regerror(errorcode, &m_RegEx, NULL, 0);
 152     if ( len > 0 )
 153     {
 154         char* szcmbError = new char[++len];
 155
 156         (void)regerror(errorcode, &m_RegEx, szcmbError, len);
 157
 158         szError = wxConvertMB2WX(szcmbError);
 159         delete [] szcmbError;
 160     }
 161     else // regerror() returned 0
 162     {
 163         szError = _("unknown error");
 164     }
 165
 166     return szError;
 167 }
 168
 169 bool wxRegExImpl::Compile(const wxString& expr, int flags)
 170 {
 171     Reinit();
 172
 173 #ifdef WX_NO_REGEX_ADVANCED
 174 #   define FLAVORS wxRE_BASIC
 175 #else
 176 #   define FLAVORS (wxRE_ADVANCED | wxRE_BASIC)
 177     wxASSERT_MSG( (flags & FLAVORS) != FLAVORS,
 178                   _T("incompatible flags in wxRegEx::Compile") );
 179 #endif
 180     wxASSERT_MSG( !(flags & ~(FLAVORS | wxRE_ICASE | wxRE_NOSUB | wxRE_NEWLINE)),
 181                   _T("unrecognized flags in wxRegEx::Compile") );
 182
 183     // translate our flags to regcomp() ones
 184     int flagsRE = 0;
 185     if ( !(flags & wxRE_BASIC) )
 186 #ifndef WX_NO_REGEX_ADVANCED
 187         if (flags & wxRE_ADVANCED)
 188             flagsRE |= REG_ADVANCED;
 189         else
 190 #endif
 191             flagsRE |= REG_EXTENDED;
 192     if ( flags & wxRE_ICASE )
 193         flagsRE |= REG_ICASE;
 194     if ( flags & wxRE_NOSUB )
 195         flagsRE |= REG_NOSUB;
 196     if ( flags & wxRE_NEWLINE )
 197         flagsRE |= REG_NEWLINE;
 198
 199     // compile it
 200 #ifdef __REG_NOFRONT
 201     bool conv = true;
 202     int errorcode = re_comp(&m_RegEx, expr, expr.length(), flagsRE);
 203 #else
 204     const wxWX2MBbuf conv = expr.mbc_str();
 205     int errorcode = conv ? regcomp(&m_RegEx, conv, flagsRE) : REG_BADPAT;
 206 #endif
 207
 208     if ( errorcode )
 209     {
 210         wxLogError(_("Invalid regular expression '%s': %s"),
 211                    expr.c_str(), GetErrorMsg(errorcode, !conv).c_str());
 212
 213         m_isCompiled = FALSE;
 214     }
 215     else // ok
 216     {
 217         // don't allocate the matches array now, but do it later if necessary
 218         if ( flags & wxRE_NOSUB )
 219         {
 220             // we don't need it at all
 221             m_nMatches = 0;
 222         }
 223         else
 224         {
 225             // we will alloc the array later (only if really needed) but count
 226             // the number of sub-expressions in the regex right now
 227
 228             // there is always one for the whole expression
 229             m_nMatches = 1;
 230
 231             // and some more for bracketed subexperessions
 232             for ( const wxChar *cptr = expr.c_str(); *cptr; cptr++ )
 233             {
 234                 if ( *cptr == _T('\\') )
 235                 {
 236                     // in basic RE syntax groups are inside \(...\)
 237                     if ( *++cptr == _T('(') && (flags & wxRE_BASIC) )
 238                     {
 239                         m_nMatches++;
 240                     }
 241                 }
 242                 else if ( *cptr == _T('(') && !(flags & wxRE_BASIC) )
 243                 {
 244                     // we know that the previous character is not an unquoted
 245                     // backslash because it would have been eaten above, so we
 246                     // have a bare '(' and this indicates a group start for the
 247                     // extended syntax. '(?' is used for extensions by perl-
 248                     // like REs (e.g. advanced), and is not valid for POSIX
 249                     // extended, so ignore them always.
 250                     if ( cptr[1] != _T('?') )
 251                         m_nMatches++;
 252                 }
 253             }
 254         }
 255
 256         m_isCompiled = TRUE;
 257     }
 258
 259     return IsValid();
 260 }
 261
 262 bool wxRegExImpl::Matches(const wxChar *str, int flags) const
 263 {
 264     wxCHECK_MSG( IsValid(), FALSE, _T("must successfully Compile() first") );
 265
 266     // translate our flags to regexec() ones
 267     wxASSERT_MSG( !(flags & ~(wxRE_NOTBOL | wxRE_NOTEOL)),
 268                   _T("unrecognized flags in wxRegEx::Matches") );
 269
 270     int flagsRE = 0;
 271     if ( flags & wxRE_NOTBOL )
 272         flagsRE |= REG_NOTBOL;
 273     if ( flags & wxRE_NOTEOL )
 274         flagsRE |= REG_NOTEOL;
 275
 276     // allocate matches array if needed
 277     wxRegExImpl *self = wxConstCast(this, wxRegExImpl);
 278     if ( !m_Matches && m_nMatches )
 279     {
 280         self->m_Matches = new regmatch_t[m_nMatches];
 281     }
 282
 283     // do match it
 284 #ifdef __REG_NOFRONT
 285     bool conv = true;
 286     int rc = re_exec(&self->m_RegEx, str, wxStrlen(str), NULL, m_nMatches, m_Matches, flagsRE);
 287 #else
 288     const wxWX2MBbuf conv = wxConvertWX2MB(str);
 289     int rc = conv ? regexec(&self->m_RegEx, conv, m_nMatches, m_Matches, flagsRE) : REG_BADPAT;
 290 #endif
 291
 292     switch ( rc )
 293     {
 294         case 0:
 295             // matched successfully
 296             return TRUE;
 297
 298         default:
 299             // an error occured
 300             wxLogError(_("Failed to match '%s' in regular expression: %s"),
 301                        str, GetErrorMsg(rc, !conv).c_str());
 302             // fall through
 303
 304         case REG_NOMATCH:
 305             // no match
 306             return FALSE;
 307     }
 308 }
 309
 310 bool wxRegExImpl::GetMatch(size_t *start, size_t *len, size_t index) const
 311 {
 312     wxCHECK_MSG( IsValid(), FALSE, _T("must successfully Compile() first") );
 313     wxCHECK_MSG( m_nMatches, FALSE, _T("can't use with wxRE_NOSUB") );
 314     wxCHECK_MSG( m_Matches, FALSE, _T("must call Matches() first") );
 315     wxCHECK_MSG( index < m_nMatches, FALSE, _T("invalid match index") );
 316
 317     const regmatch_t& match = m_Matches[index];
 318
 319     if ( start )
 320         *start = match.rm_so;
 321     if ( len )
 322         *len = match.rm_eo - match.rm_so;
 323
 324     return TRUE;
 325 }
 326
 327 size_t wxRegExImpl::GetMatchCount() const
 328 {
 329     wxCHECK_MSG( IsValid(), 0, _T("must successfully Compile() first") );
 330     wxCHECK_MSG( m_nMatches, 0, _T("can't use with wxRE_NOSUB") );
 331
 332     return m_nMatches;
 333 }
 334
 335 int wxRegExImpl::Replace(wxString *text,
 336                          const wxString& replacement,
 337                          size_t maxMatches) const
 338 {
 339     wxCHECK_MSG( text, -1, _T("NULL text in wxRegEx::Replace") );
 340     wxCHECK_MSG( IsValid(), -1, _T("must successfully Compile() first") );
 341
 342     // the replacement text
 343     wxString textNew;
 344
 345     // attempt at optimization: don't iterate over the string if it doesn't
 346     // contain back references at all
 347     bool mayHaveBackrefs =
 348         replacement.find_first_of(_T("\\&")) != wxString::npos;
 349
 350     if ( !mayHaveBackrefs )
 351     {
 352         textNew = replacement;
 353     }
 354
 355     // the position where we start looking for the match
 356     //
 357     // NB: initial version had a nasty bug because it used a wxChar* instead of
 358     //     an index but the problem is that replace() in the loop invalidates
 359     //     all pointers into the string so we have to use indices instead
 360     size_t matchStart = 0;
 361
 362     // number of replacement made: we won't make more than maxMatches of them
 363     // (unless maxMatches is 0 which doesn't limit the number of replacements)
 364     size_t countRepl = 0;
 365
 366     // note that "^" shouldn't match after the first call to Matches() so we
 367     // use wxRE_NOTBOL to prevent it from happening
 368     while ( (!maxMatches || countRepl < maxMatches) &&
 369             Matches(text->c_str() + matchStart, countRepl ? wxRE_NOTBOL : 0) )
 370     {
 371         // the string possibly contains back references: we need to calculate
 372         // the replacement text anew after each match
 373         if ( mayHaveBackrefs )
 374         {
 375             mayHaveBackrefs = FALSE;
 376             textNew.clear();
 377             textNew.reserve(replacement.length());
 378
 379             for ( const wxChar *p = replacement.c_str(); *p; p++ )
 380             {
 381                 size_t index = (size_t)-1;
 382
 383                 if ( *p == _T('\\') )
 384                 {
 385                     if ( wxIsdigit(*++p) )
 386                     {
 387                         // back reference
 388                         wxChar *end;
 389                         index = (size_t)wxStrtoul(p, &end, 10);
 390                         p = end - 1; // -1 to compensate for p++ in the loop
 391                     }
 392                     //else: backslash used as escape character
 393                 }
 394                 else if ( *p == _T('&') )
 395                 {
 396                     // treat this as "\0" for compatbility with ed and such
 397                     index = 0;
 398                 }
 399
 400                 // do we have a back reference?
 401                 if ( index != (size_t)-1 )
 402                 {
 403                     // yes, get its text
 404                     size_t start, len;
 405                     if ( !GetMatch(&start, &len, index) )
 406                     {
 407                         wxFAIL_MSG( _T("invalid back reference") );
 408
 409                         // just eat it...
 410                     }
 411                     else
 412                     {
 413                         textNew += wxString(text->c_str() + matchStart + start,
 414                                             len);
 415
 416                         mayHaveBackrefs = TRUE;
 417                     }
 418                 }
 419                 else // ordinary character
 420                 {
 421                     textNew += *p;
 422                 }
 423             }
 424         }
 425
 426         size_t start, len;
 427         if ( !GetMatch(&start, &len) )
 428         {
 429             // we did have match as Matches() returned true above!
 430             wxFAIL_MSG( _T("internal logic error in wxRegEx::Replace") );
 431
 432             return -1;
 433         }
 434
 435         matchStart += start;
 436         text->replace(matchStart, len, textNew);
 437
 438         countRepl++;
 439
 440         matchStart += textNew.length();
 441     }
 442
 443     return countRepl;
 444 }
 445
 446 // ----------------------------------------------------------------------------
 447 // wxRegEx: all methods are mostly forwarded to wxRegExImpl
 448 // ----------------------------------------------------------------------------
 449
 450 void wxRegEx::Init()
 451 {
 452     m_impl = NULL;
 453 }
 454
 455
 456 wxRegEx::~wxRegEx()
 457 {
 458     delete m_impl;
 459 }
 460
 461 bool wxRegEx::Compile(const wxString& expr, int flags)
 462 {
 463     if ( !m_impl )
 464     {
 465         m_impl = new wxRegExImpl;
 466     }
 467
 468     if ( !m_impl->Compile(expr, flags) )
 469     {
 470         // error message already given in wxRegExImpl::Compile
 471         delete m_impl;
 472         m_impl = NULL;
 473
 474         return FALSE;
 475     }
 476
 477     return TRUE;
 478 }
 479
 480 bool wxRegEx::Matches(const wxChar *str, int flags) const
 481 {
 482     wxCHECK_MSG( IsValid(), FALSE, _T("must successfully Compile() first") );
 483
 484     return m_impl->Matches(str, flags);
 485 }
 486
 487 bool wxRegEx::GetMatch(size_t *start, size_t *len, size_t index) const
 488 {
 489     wxCHECK_MSG( IsValid(), FALSE, _T("must successfully Compile() first") );
 490
 491     return m_impl->GetMatch(start, len, index);
 492 }
 493
 494 wxString wxRegEx::GetMatch(const wxString& text, size_t index) const
 495 {
 496     size_t start, len;
 497     if ( !GetMatch(&start, &len, index) )
 498         return wxEmptyString;
 499
 500     return text.Mid(start, len);
 501 }
 502
 503 size_t wxRegEx::GetMatchCount() const
 504 {
 505     wxCHECK_MSG( IsValid(), 0, _T("must successfully Compile() first") );
 506
 507     return m_impl->GetMatchCount();
 508 }
 509
 510 int wxRegEx::Replace(wxString *pattern,
 511                      const wxString& replacement,
 512                      size_t maxMatches) const
 513 {
 514     wxCHECK_MSG( IsValid(), -1, _T("must successfully Compile() first") );
 515
 516     return m_impl->Replace(pattern, replacement, maxMatches);
 517 }
 518
 519 #endif // wxUSE_REGEX