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 = wx_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 = wx_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 occurred
 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     // we need the casts because rm_so can be a 64 bit quantity
 320     if ( start )
 321         *start = wx_truncate_cast(size_t, match.rm_so);
 322     if ( len )
 323         *len = wx_truncate_cast(size_t, match.rm_eo - match.rm_so);
 324
 325     return true;
 326 }
 327
 328 size_t wxRegExImpl::GetMatchCount() const
 329 {
 330     wxCHECK_MSG( IsValid(), 0, _T("must successfully Compile() first") );
 331     wxCHECK_MSG( m_nMatches, 0, _T("can't use with wxRE_NOSUB") );
 332
 333     return m_nMatches;
 334 }
 335
 336 int wxRegExImpl::Replace(wxString *text,
 337                          const wxString& replacement,
 338                          size_t maxMatches) const
 339 {
 340     wxCHECK_MSG( text, wxNOT_FOUND, _T("NULL text in wxRegEx::Replace") );
 341     wxCHECK_MSG( IsValid(), wxNOT_FOUND, _T("must successfully Compile() first") );
 342
 343     // the replacement text
 344     wxString textNew;
 345
 346     // attempt at optimization: don't iterate over the string if it doesn't
 347     // contain back references at all
 348     bool mayHaveBackrefs =
 349         replacement.find_first_of(_T("\\&")) != wxString::npos;
 350
 351     if ( !mayHaveBackrefs )
 352     {
 353         textNew = replacement;
 354     }
 355
 356     // the position where we start looking for the match
 357     //
 358     // NB: initial version had a nasty bug because it used a wxChar* instead of
 359     //     an index but the problem is that replace() in the loop invalidates
 360     //     all pointers into the string so we have to use indices instead
 361     size_t matchStart = 0;
 362
 363     // number of replacement made: we won't make more than maxMatches of them
 364     // (unless maxMatches is 0 which doesn't limit the number of replacements)
 365     size_t countRepl = 0;
 366
 367     // note that "^" shouldn't match after the first call to Matches() so we
 368     // use wxRE_NOTBOL to prevent it from happening
 369     while ( (!maxMatches || countRepl < maxMatches) &&
 370             Matches(text->c_str() + matchStart, countRepl ? wxRE_NOTBOL : 0) )
 371     {
 372         // the string possibly contains back references: we need to calculate
 373         // the replacement text anew after each match
 374         if ( mayHaveBackrefs )
 375         {
 376             mayHaveBackrefs = false;
 377             textNew.clear();
 378             textNew.reserve(replacement.length());
 379
 380             for ( const wxChar *p = replacement.c_str(); *p; p++ )
 381             {
 382                 size_t index = (size_t)-1;
 383
 384                 if ( *p == _T('\\') )
 385                 {
 386                     if ( wxIsdigit(*++p) )
 387                     {
 388                         // back reference
 389                         wxChar *end;
 390                         index = (size_t)wxStrtoul(p, &end, 10);
 391                         p = end - 1; // -1 to compensate for p++ in the loop
 392                     }
 393                     //else: backslash used as escape character
 394                 }
 395                 else if ( *p == _T('&') )
 396                 {
 397                     // treat this as "\0" for compatbility with ed and such
 398                     index = 0;
 399                 }
 400
 401                 // do we have a back reference?
 402                 if ( index != (size_t)-1 )
 403                 {
 404                     // yes, get its text
 405                     size_t start, len;
 406                     if ( !GetMatch(&start, &len, index) )
 407                     {
 408                         wxFAIL_MSG( _T("invalid back reference") );
 409
 410                         // just eat it...
 411                     }
 412                     else
 413                     {
 414                         textNew += wxString(text->c_str() + matchStart + start,
 415                                             len);
 416
 417                         mayHaveBackrefs = true;
 418                     }
 419                 }
 420                 else // ordinary character
 421                 {
 422                     textNew += *p;
 423                 }
 424             }
 425         }
 426
 427         size_t start, len;
 428         if ( !GetMatch(&start, &len) )
 429         {
 430             // we did have match as Matches() returned true above!
 431             wxFAIL_MSG( _T("internal logic error in wxRegEx::Replace") );
 432
 433             return wxNOT_FOUND;
 434         }
 435
 436         matchStart += start;
 437         text->replace(matchStart, len, textNew);
 438
 439         countRepl++;
 440
 441         matchStart += textNew.length();
 442     }
 443
 444     return countRepl;
 445 }
 446
 447 // ----------------------------------------------------------------------------
 448 // wxRegEx: all methods are mostly forwarded to wxRegExImpl
 449 // ----------------------------------------------------------------------------
 450
 451 void wxRegEx::Init()
 452 {
 453     m_impl = NULL;
 454 }
 455
 456
 457 wxRegEx::~wxRegEx()
 458 {
 459     delete m_impl;
 460 }
 461
 462 bool wxRegEx::Compile(const wxString& expr, int flags)
 463 {
 464     if ( !m_impl )
 465     {
 466         m_impl = new wxRegExImpl;
 467     }
 468
 469     if ( !m_impl->Compile(expr, flags) )
 470     {
 471         // error message already given in wxRegExImpl::Compile
 472         delete m_impl;
 473         m_impl = NULL;
 474
 475         return false;
 476     }
 477
 478     return true;
 479 }
 480
 481 bool wxRegEx::Matches(const wxChar *str, int flags) const
 482 {
 483     wxCHECK_MSG( IsValid(), false, _T("must successfully Compile() first") );
 484
 485     return m_impl->Matches(str, flags);
 486 }
 487
 488 bool wxRegEx::GetMatch(size_t *start, size_t *len, size_t index) const
 489 {
 490     wxCHECK_MSG( IsValid(), false, _T("must successfully Compile() first") );
 491
 492     return m_impl->GetMatch(start, len, index);
 493 }
 494
 495 wxString wxRegEx::GetMatch(const wxString& text, size_t index) const
 496 {
 497     size_t start, len;
 498     if ( !GetMatch(&start, &len, index) )
 499         return wxEmptyString;
 500
 501     return text.Mid(start, len);
 502 }
 503
 504 size_t wxRegEx::GetMatchCount() const
 505 {
 506     wxCHECK_MSG( IsValid(), 0, _T("must successfully Compile() first") );
 507
 508     return m_impl->GetMatchCount();
 509 }
 510
 511 int wxRegEx::Replace(wxString *pattern,
 512                      const wxString& replacement,
 513                      size_t maxMatches) const
 514 {
 515     wxCHECK_MSG( IsValid(), wxNOT_FOUND, _T("must successfully Compile() first") );
 516
 517     return m_impl->Replace(pattern, replacement, maxMatches);
 518 }
 519
 520 #endif // wxUSE_REGEX