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 #ifdef __GNUG__
  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 requires this, it probably doesn't hurt for others
  42 #ifdef __UNIX__
  43     #include <sys/types.h>
  44 #endif
  45
  46 #include <regex.h>
  47
  48 #include "wx/regex.h"
  49
  50 // ----------------------------------------------------------------------------
  51 // private classes
  52 // ----------------------------------------------------------------------------
  53
  54 // the real implementation of wxRegEx
  55 class wxRegExImpl
  56 {
  57 public:
  58     // ctor and dtor
  59     wxRegExImpl();
  60     ~wxRegExImpl();
  61
  62     // return TRUE if Compile() had been called successfully
  63     bool IsValid() const { return m_isCompiled; }
  64
  65     // RE operations
  66     bool Compile(const wxString& expr, int flags = 0);
  67     bool Matches(const wxChar *str, int flags = 0) const;
  68     bool GetMatch(size_t *start, size_t *len, size_t index = 0) const;
  69     int Replace(wxString *pattern, const wxString& replacement,
  70                 size_t maxMatches = 0) const;
  71
  72 private:
  73     // return the string containing the error message for the given err code
  74     wxString GetErrorMsg(int errorcode) const;
  75
  76     // free the RE if compiled
  77     void Free()
  78     {
  79         if ( IsValid() )
  80         {
  81             regfree(&m_RegEx);
  82
  83             m_isCompiled = FALSE;
  84         }
  85     }
  86
  87     // compiled RE
  88     regex_t     m_RegEx;
  89
  90     // the subexpressions data
  91     regmatch_t *m_Matches;
  92     size_t      m_nMatches;
  93
  94     // TRUE if m_RegEx is valid
  95     bool        m_isCompiled;
  96 };
  97
  98 // ============================================================================
  99 // implementation
 100 // ============================================================================
 101
 102 // ----------------------------------------------------------------------------
 103 // wxRegExImpl
 104 // ----------------------------------------------------------------------------
 105
 106 wxRegExImpl::wxRegExImpl()
 107 {
 108     m_isCompiled = FALSE;
 109     m_Matches = NULL;
 110     m_nMatches = 0;
 111 }
 112
 113 wxRegExImpl::~wxRegExImpl()
 114 {
 115     Free();
 116
 117     delete [] m_Matches;
 118 }
 119
 120 wxString wxRegExImpl::GetErrorMsg(int errorcode) const
 121 {
 122     wxString msg;
 123
 124     // first get the string length needed
 125     int len = regerror(errorcode, &m_RegEx, NULL, 0);
 126     if ( len > 0 )
 127     {
 128         len++;
 129
 130         (void)regerror(errorcode, &m_RegEx, msg.GetWriteBuf(len), len);
 131
 132         msg.UngetWriteBuf();
 133     }
 134     else // regerror() returned 0
 135     {
 136         msg = _("unknown error");
 137     }
 138
 139     return msg;
 140 }
 141
 142 bool wxRegExImpl::Compile(const wxString& expr, int flags)
 143 {
 144     Free();
 145
 146     // translate our flags to regcomp() ones
 147     wxASSERT_MSG( !(flags &
 148                         ~(wxRE_BASIC | wxRE_ICASE | wxRE_NOSUB | wxRE_NEWLINE)),
 149                   _T("unrecognized flags in wxRegEx::Compile") );
 150
 151     int flagsRE = 0;
 152     if ( !(flags & wxRE_BASIC) )
 153         flagsRE |= REG_EXTENDED;
 154     if ( flags & wxRE_ICASE )
 155         flagsRE |= REG_ICASE;
 156     if ( flags & wxRE_NOSUB )
 157         flagsRE |= REG_NOSUB;
 158     if ( flags & wxRE_NEWLINE )
 159         flagsRE |= REG_NEWLINE;
 160
 161     // compile it
 162     int errorcode = regcomp(&m_RegEx, expr, flagsRE);
 163     if ( errorcode )
 164     {
 165         wxLogError(_("Invalid regular expression '%s': %s"),
 166                    expr.c_str(), GetErrorMsg(errorcode).c_str());
 167
 168         m_isCompiled = FALSE;
 169     }
 170     else // ok
 171     {
 172         // don't allocate the matches array now, but do it later if necessary
 173         if ( flags & wxRE_NOSUB )
 174         {
 175             // we don't need it at all
 176             m_nMatches = 0;
 177         }
 178         else
 179         {
 180             // we will alloc the array later (only if really needed) but count
 181             // the number of sub-expressions in the regex right now
 182
 183             // there is always one for the whole expression
 184             m_nMatches = 1;
 185
 186             // and some more for bracketed subexperessions
 187             const wxChar *cptr = expr.c_str();
 188             wxChar prev = _T('\0');
 189             while ( *cptr != _T('\0') )
 190             {
 191                 // is this a subexpr start, i.e. "(" for extended regex or
 192                 // "\(" for a basic one?
 193                 if ( *cptr == _T('(') &&
 194                      (flags & wxRE_BASIC ? prev == _T('\\')
 195                                          : prev != _T('\\')) )
 196                 {
 197                     m_nMatches++;
 198                 }
 199
 200                 prev = *cptr;
 201                 cptr++;
 202             }
 203         }
 204
 205         m_isCompiled = TRUE;
 206     }
 207
 208     return IsValid();
 209 }
 210
 211 bool wxRegExImpl::Matches(const wxChar *str, int flags) const
 212 {
 213     wxCHECK_MSG( IsValid(), FALSE, _T("must successfully Compile() first") );
 214
 215     // translate our flags to regexec() ones
 216     wxASSERT_MSG( !(flags & ~(wxRE_NOTBOL | wxRE_NOTEOL)),
 217                   _T("unrecognized flags in wxRegEx::Matches") );
 218
 219     int flagsRE = 0;
 220     if ( flags & wxRE_NOTBOL )
 221         flagsRE |= REG_NOTBOL;
 222     if ( flags & wxRE_NOTEOL )
 223         flagsRE |= REG_NOTEOL;
 224
 225     // allocate matches array if needed
 226     wxRegExImpl *self = wxConstCast(this, wxRegExImpl);
 227     if ( !m_Matches && m_nMatches )
 228     {
 229         self->m_Matches = new regmatch_t[m_nMatches];
 230     }
 231
 232     // do match it
 233     int rc = regexec(&self->m_RegEx, str, m_nMatches, m_Matches, flagsRE);
 234
 235     switch ( rc )
 236     {
 237         case 0:
 238             // matched successfully
 239             return TRUE;
 240
 241         default:
 242             // an error occured
 243             wxLogError(_("Failed to match '%s' in regular expression: %s"),
 244                        str, GetErrorMsg(rc).c_str());
 245             // fall through
 246
 247         case REG_NOMATCH:
 248             // no match
 249             return FALSE;
 250     }
 251 }
 252
 253 bool wxRegExImpl::GetMatch(size_t *start, size_t *len, size_t index) const
 254 {
 255     wxCHECK_MSG( IsValid(), FALSE, _T("must successfully Compile() first") );
 256     wxCHECK_MSG( m_Matches, FALSE, _T("can't use with wxRE_NOSUB") );
 257     wxCHECK_MSG( index < m_nMatches, FALSE, _T("invalid match index") );
 258
 259     const regmatch_t& match = m_Matches[index];
 260
 261     if ( start )
 262         *start = match.rm_so;
 263     if ( len )
 264         *len = match.rm_eo - match.rm_so;
 265
 266     return TRUE;
 267 }
 268
 269 int wxRegExImpl::Replace(wxString *text,
 270                          const wxString& replacement,
 271                          size_t maxMatches) const
 272 {
 273     wxCHECK_MSG( text, -1, _T("NULL text in wxRegEx::Replace") );
 274     wxCHECK_MSG( IsValid(), -1, _T("must successfully Compile() first") );
 275
 276     // the replacement text
 277     wxString textNew;
 278
 279     // attempt at optimization: don't iterate over the string if it doesn't
 280     // contain back references at all
 281     bool mayHaveBackrefs =
 282         replacement.find_first_of(_T("\\&")) != wxString::npos;
 283
 284     if ( !mayHaveBackrefs )
 285     {
 286         textNew = replacement;
 287     }
 288
 289     // the position where we start looking for the match
 290     //
 291     // NB: initial version had a nasty bug because it used a wxChar* instead of
 292     //     an index but the problem is that replace() in the loop invalidates
 293     //     all pointers into the string so we have to use indices instead
 294     size_t matchStart = 0;
 295
 296     // number of replacement made: we won't make more than maxMatches of them
 297     // (unless maxMatches is 0 which doesn't limit the number of replacements)
 298     size_t countRepl = 0;
 299
 300     // note that "^" shouldn't match after the first call to Matches() so we
 301     // use wxRE_NOTBOL to prevent it from happening
 302     while ( (!maxMatches || countRepl < maxMatches) &&
 303             Matches(text->c_str() + matchStart, countRepl ? wxRE_NOTBOL : 0) )
 304     {
 305         // the string possibly contains back references: we need to calculate
 306         // the replacement text anew after each match
 307         if ( mayHaveBackrefs )
 308         {
 309             mayHaveBackrefs = FALSE;
 310             textNew.clear();
 311             textNew.reserve(replacement.length());
 312
 313             for ( const wxChar *p = replacement.c_str(); *p; p++ )
 314             {
 315                 size_t index = (size_t)-1;
 316
 317                 if ( *p == _T('\\') )
 318                 {
 319                     if ( wxIsdigit(*++p) )
 320                     {
 321                         // back reference
 322                         wxChar *end;
 323                         index = (size_t)wxStrtoul(p, &end, 10);
 324                         p = end - 1; // -1 to compensate for p++ in the loop
 325                     }
 326                     //else: backslash used as escape character
 327                 }
 328                 else if ( *p == _T('&') )
 329                 {
 330                     // treat this as "\0" for compatbility with ed and such
 331                     index = 0;
 332                 }
 333
 334                 // do we have a back reference?
 335                 if ( index != (size_t)-1 )
 336                 {
 337                     // yes, get its text
 338                     size_t start, len;
 339                     if ( !GetMatch(&start, &len, index) )
 340                     {
 341                         wxFAIL_MSG( _T("invalid back reference") );
 342
 343                         // just eat it...
 344                     }
 345                     else
 346                     {
 347                         textNew += wxString(text->c_str() + matchStart + start,
 348                                             len);
 349
 350                         mayHaveBackrefs = TRUE;
 351                     }
 352                 }
 353                 else // ordinary character
 354                 {
 355                     textNew += *p;
 356                 }
 357             }
 358         }
 359
 360         size_t start, len;
 361         if ( !GetMatch(&start, &len) )
 362         {
 363             // we did have match as Matches() returned true above!
 364             wxFAIL_MSG( _T("internal logic error in wxRegEx::Replace") );
 365
 366             return -1;
 367         }
 368
 369         matchStart += start;
 370         text->replace(matchStart, len, textNew);
 371
 372         countRepl++;
 373
 374         matchStart += textNew.length();
 375     }
 376
 377     return countRepl;
 378 }
 379
 380 // ----------------------------------------------------------------------------
 381 // wxRegEx: all methods are mostly forwarded to wxRegExImpl
 382 // ----------------------------------------------------------------------------
 383
 384 void wxRegEx::Init()
 385 {
 386     m_impl = NULL;
 387 }
 388
 389
 390 wxRegEx::~wxRegEx()
 391 {
 392     delete m_impl;
 393 }
 394
 395 bool wxRegEx::Compile(const wxString& expr, int flags)
 396 {
 397     if ( !m_impl )
 398     {
 399         m_impl = new wxRegExImpl;
 400     }
 401
 402     if ( !m_impl->Compile(expr, flags) )
 403     {
 404         // error message already given in wxRegExImpl::Compile
 405         delete m_impl;
 406         m_impl = NULL;
 407
 408         return FALSE;
 409     }
 410
 411     return TRUE;
 412 }
 413
 414 bool wxRegEx::Matches(const wxChar *str, int flags) const
 415 {
 416     wxCHECK_MSG( IsValid(), FALSE, _T("must successfully Compile() first") );
 417
 418     return m_impl->Matches(str, flags);
 419 }
 420
 421 bool wxRegEx::GetMatch(size_t *start, size_t *len, size_t index) const
 422 {
 423     wxCHECK_MSG( IsValid(), FALSE, _T("must successfully Compile() first") );
 424
 425     return m_impl->GetMatch(start, len, index);
 426 }
 427
 428 wxString wxRegEx::GetMatch(const wxString& text, size_t index) const
 429 {
 430     size_t start, len;
 431     if ( !GetMatch(&start, &len, index) )
 432         return wxEmptyString;
 433
 434     return text.Mid(start, len);
 435 }
 436
 437 int wxRegEx::Replace(wxString *pattern,
 438                      const wxString& replacement,
 439                      size_t maxMatches) const
 440 {
 441     wxCHECK_MSG( IsValid(), -1, _T("must successfully Compile() first") );
 442
 443     return m_impl->Replace(pattern, replacement, maxMatches);
 444 }
 445
 446 #endif // wxUSE_REGEX