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