dvander@2762: // Copyright (c) 2005, Google Inc.
dvander@2762: // All rights reserved.
dvander@2762: //
dvander@2762: // Redistribution and use in source and binary forms, with or without
dvander@2762: // modification, are permitted provided that the following conditions are
dvander@2762: // met:
dvander@2762: //
dvander@2762: //     * Redistributions of source code must retain the above copyright
dvander@2762: // notice, this list of conditions and the following disclaimer.
dvander@2762: //     * Redistributions in binary form must reproduce the above
dvander@2762: // copyright notice, this list of conditions and the following disclaimer
dvander@2762: // in the documentation and/or other materials provided with the
dvander@2762: // distribution.
dvander@2762: //     * Neither the name of Google Inc. nor the names of its
dvander@2762: // contributors may be used to endorse or promote products derived from
dvander@2762: // this software without specific prior written permission.
dvander@2762: //
dvander@2762: // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
dvander@2762: // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
dvander@2762: // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
dvander@2762: // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
dvander@2762: // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
dvander@2762: // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
dvander@2762: // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
dvander@2762: // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
dvander@2762: // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
dvander@2762: // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
dvander@2762: // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
dvander@2762: //
dvander@2762: // Author: Sanjay Ghemawat
dvander@2762: 
dvander@2762: #ifdef HAVE_CONFIG_H
dvander@2762: #include "config.h"
dvander@2762: #endif
dvander@2762: 
dvander@2762: #include <stdlib.h>
dvander@2762: #include <stdio.h>
dvander@2762: #include <ctype.h>
dvander@2762: #include <limits.h>      /* for SHRT_MIN, USHRT_MAX, etc */
dvander@2762: #include <assert.h>
dvander@2762: #include <errno.h>
dvander@2762: #include <string>
dvander@2762: #include <algorithm>
dvander@2762: 
dvander@2762: #include "pcrecpp_internal.h"
dvander@2762: #include "pcre.h"
dvander@2762: #include "pcrecpp.h"
dvander@2762: #include "pcre_stringpiece.h"
dvander@2762: 
dvander@2762: 
dvander@2762: namespace pcrecpp {
dvander@2762: 
dvander@2762: // Maximum number of args we can set
dvander@2762: static const int kMaxArgs = 16;
dvander@2762: static const int kVecSize = (1 + kMaxArgs) * 3;  // results + PCRE workspace
dvander@2762: 
dvander@2762: // Special object that stands-in for no argument
dvander@2762: Arg RE::no_arg((void*)NULL);
dvander@2762: 
dvander@2762: // This is for ABI compatibility with old versions of pcre (pre-7.6),
dvander@2762: // which defined a global no_arg variable instead of putting it in the
dvander@2762: // RE class.  This works on GCC >= 3, at least.  It definitely works
dvander@2762: // for ELF, but may not for other object formats (Mach-O, for
dvander@2762: // instance, does not support aliases.)  We could probably have a more
dvander@2762: // inclusive test if we ever needed it.  (Note that not only the
dvander@2762: // __attribute__ syntax, but also __USER_LABEL_PREFIX__, are
dvander@2762: // gnu-specific.)
dvander@2762: #if defined(__GNUC__) && __GNUC__ >= 3 && defined(__ELF__)
dvander@2762: # define ULP_AS_STRING(x)            ULP_AS_STRING_INTERNAL(x)
dvander@2762: # define ULP_AS_STRING_INTERNAL(x)   #x
dvander@2762: # define USER_LABEL_PREFIX_STR       ULP_AS_STRING(__USER_LABEL_PREFIX__)
dvander@2762: extern Arg no_arg
dvander@2762:   __attribute__((alias(USER_LABEL_PREFIX_STR "_ZN7pcrecpp2RE6no_argE")));
dvander@2762: #endif
dvander@2762: 
dvander@2762: // If a regular expression has no error, its error_ field points here
dvander@2762: static const string empty_string;
dvander@2762: 
dvander@2762: // If the user doesn't ask for any options, we just use this one
dvander@2762: static RE_Options default_options;
dvander@2762: 
dvander@2762: void RE::Init(const string& pat, const RE_Options* options) {
dvander@2762:   pattern_ = pat;
dvander@2762:   if (options == NULL) {
dvander@2762:     options_ = default_options;
dvander@2762:   } else {
dvander@2762:     options_ = *options;
dvander@2762:   }
dvander@2762:   error_ = &empty_string;
dvander@2762:   re_full_ = NULL;
dvander@2762:   re_partial_ = NULL;
dvander@2762: 
dvander@2762:   re_partial_ = Compile(UNANCHORED);
dvander@2762:   if (re_partial_ != NULL) {
dvander@2762:     re_full_ = Compile(ANCHOR_BOTH);
dvander@2762:   }
dvander@2762: }
dvander@2762: 
dvander@2762: void RE::Cleanup() {
dvander@2762:   if (re_full_ != NULL)         (*pcre_free)(re_full_);
dvander@2762:   if (re_partial_ != NULL)      (*pcre_free)(re_partial_);
dvander@2762:   if (error_ != &empty_string)  delete error_;
dvander@2762: }
dvander@2762: 
dvander@2762: 
dvander@2762: RE::~RE() {
dvander@2762:   Cleanup();
dvander@2762: }
dvander@2762: 
dvander@2762: 
dvander@2762: pcre* RE::Compile(Anchor anchor) {
dvander@2762:   // First, convert RE_Options into pcre options
dvander@2762:   int pcre_options = 0;
dvander@2762:   pcre_options = options_.all_options();
dvander@2762: 
dvander@2762:   // Special treatment for anchoring.  This is needed because at
dvander@2762:   // runtime pcre only provides an option for anchoring at the
dvander@2762:   // beginning of a string (unless you use offset).
dvander@2762:   //
dvander@2762:   // There are three types of anchoring we want:
dvander@2762:   //    UNANCHORED      Compile the original pattern, and use
dvander@2762:   //                    a pcre unanchored match.
dvander@2762:   //    ANCHOR_START    Compile the original pattern, and use
dvander@2762:   //                    a pcre anchored match.
dvander@2762:   //    ANCHOR_BOTH     Tack a "\z" to the end of the original pattern
dvander@2762:   //                    and use a pcre anchored match.
dvander@2762: 
dvander@2762:   const char* compile_error;
dvander@2762:   int eoffset;
dvander@2762:   pcre* re;
dvander@2762:   if (anchor != ANCHOR_BOTH) {
dvander@2762:     re = pcre_compile(pattern_.c_str(), pcre_options,
dvander@2762:                       &compile_error, &eoffset, NULL);
dvander@2762:   } else {
dvander@2762:     // Tack a '\z' at the end of RE.  Parenthesize it first so that
dvander@2762:     // the '\z' applies to all top-level alternatives in the regexp.
dvander@2762:     string wrapped = "(?:";  // A non-counting grouping operator
dvander@2762:     wrapped += pattern_;
dvander@2762:     wrapped += ")\\z";
dvander@2762:     re = pcre_compile(wrapped.c_str(), pcre_options,
dvander@2762:                       &compile_error, &eoffset, NULL);
dvander@2762:   }
dvander@2762:   if (re == NULL) {
dvander@2762:     if (error_ == &empty_string) error_ = new string(compile_error);
dvander@2762:   }
dvander@2762:   return re;
dvander@2762: }
dvander@2762: 
dvander@2762: /***** Matching interfaces *****/
dvander@2762: 
dvander@2762: bool RE::FullMatch(const StringPiece& text,
dvander@2762:                    const Arg& ptr1,
dvander@2762:                    const Arg& ptr2,
dvander@2762:                    const Arg& ptr3,
dvander@2762:                    const Arg& ptr4,
dvander@2762:                    const Arg& ptr5,
dvander@2762:                    const Arg& ptr6,
dvander@2762:                    const Arg& ptr7,
dvander@2762:                    const Arg& ptr8,
dvander@2762:                    const Arg& ptr9,
dvander@2762:                    const Arg& ptr10,
dvander@2762:                    const Arg& ptr11,
dvander@2762:                    const Arg& ptr12,
dvander@2762:                    const Arg& ptr13,
dvander@2762:                    const Arg& ptr14,
dvander@2762:                    const Arg& ptr15,
dvander@2762:                    const Arg& ptr16) const {
dvander@2762:   const Arg* args[kMaxArgs];
dvander@2762:   int n = 0;
dvander@2762:   if (&ptr1  == &no_arg) goto done; args[n++] = &ptr1;
dvander@2762:   if (&ptr2  == &no_arg) goto done; args[n++] = &ptr2;
dvander@2762:   if (&ptr3  == &no_arg) goto done; args[n++] = &ptr3;
dvander@2762:   if (&ptr4  == &no_arg) goto done; args[n++] = &ptr4;
dvander@2762:   if (&ptr5  == &no_arg) goto done; args[n++] = &ptr5;
dvander@2762:   if (&ptr6  == &no_arg) goto done; args[n++] = &ptr6;
dvander@2762:   if (&ptr7  == &no_arg) goto done; args[n++] = &ptr7;
dvander@2762:   if (&ptr8  == &no_arg) goto done; args[n++] = &ptr8;
dvander@2762:   if (&ptr9  == &no_arg) goto done; args[n++] = &ptr9;
dvander@2762:   if (&ptr10 == &no_arg) goto done; args[n++] = &ptr10;
dvander@2762:   if (&ptr11 == &no_arg) goto done; args[n++] = &ptr11;
dvander@2762:   if (&ptr12 == &no_arg) goto done; args[n++] = &ptr12;
dvander@2762:   if (&ptr13 == &no_arg) goto done; args[n++] = &ptr13;
dvander@2762:   if (&ptr14 == &no_arg) goto done; args[n++] = &ptr14;
dvander@2762:   if (&ptr15 == &no_arg) goto done; args[n++] = &ptr15;
dvander@2762:   if (&ptr16 == &no_arg) goto done; args[n++] = &ptr16;
dvander@2762:  done:
dvander@2762: 
dvander@2762:   int consumed;
dvander@2762:   int vec[kVecSize];
dvander@2762:   return DoMatchImpl(text, ANCHOR_BOTH, &consumed, args, n, vec, kVecSize);
dvander@2762: }
dvander@2762: 
dvander@2762: bool RE::PartialMatch(const StringPiece& text,
dvander@2762:                       const Arg& ptr1,
dvander@2762:                       const Arg& ptr2,
dvander@2762:                       const Arg& ptr3,
dvander@2762:                       const Arg& ptr4,
dvander@2762:                       const Arg& ptr5,
dvander@2762:                       const Arg& ptr6,
dvander@2762:                       const Arg& ptr7,
dvander@2762:                       const Arg& ptr8,
dvander@2762:                       const Arg& ptr9,
dvander@2762:                       const Arg& ptr10,
dvander@2762:                       const Arg& ptr11,
dvander@2762:                       const Arg& ptr12,
dvander@2762:                       const Arg& ptr13,
dvander@2762:                       const Arg& ptr14,
dvander@2762:                       const Arg& ptr15,
dvander@2762:                       const Arg& ptr16) const {
dvander@2762:   const Arg* args[kMaxArgs];
dvander@2762:   int n = 0;
dvander@2762:   if (&ptr1  == &no_arg) goto done; args[n++] = &ptr1;
dvander@2762:   if (&ptr2  == &no_arg) goto done; args[n++] = &ptr2;
dvander@2762:   if (&ptr3  == &no_arg) goto done; args[n++] = &ptr3;
dvander@2762:   if (&ptr4  == &no_arg) goto done; args[n++] = &ptr4;
dvander@2762:   if (&ptr5  == &no_arg) goto done; args[n++] = &ptr5;
dvander@2762:   if (&ptr6  == &no_arg) goto done; args[n++] = &ptr6;
dvander@2762:   if (&ptr7  == &no_arg) goto done; args[n++] = &ptr7;
dvander@2762:   if (&ptr8  == &no_arg) goto done; args[n++] = &ptr8;
dvander@2762:   if (&ptr9  == &no_arg) goto done; args[n++] = &ptr9;
dvander@2762:   if (&ptr10 == &no_arg) goto done; args[n++] = &ptr10;
dvander@2762:   if (&ptr11 == &no_arg) goto done; args[n++] = &ptr11;
dvander@2762:   if (&ptr12 == &no_arg) goto done; args[n++] = &ptr12;
dvander@2762:   if (&ptr13 == &no_arg) goto done; args[n++] = &ptr13;
dvander@2762:   if (&ptr14 == &no_arg) goto done; args[n++] = &ptr14;
dvander@2762:   if (&ptr15 == &no_arg) goto done; args[n++] = &ptr15;
dvander@2762:   if (&ptr16 == &no_arg) goto done; args[n++] = &ptr16;
dvander@2762:  done:
dvander@2762: 
dvander@2762:   int consumed;
dvander@2762:   int vec[kVecSize];
dvander@2762:   return DoMatchImpl(text, UNANCHORED, &consumed, args, n, vec, kVecSize);
dvander@2762: }
dvander@2762: 
dvander@2762: bool RE::Consume(StringPiece* input,
dvander@2762:                  const Arg& ptr1,
dvander@2762:                  const Arg& ptr2,
dvander@2762:                  const Arg& ptr3,
dvander@2762:                  const Arg& ptr4,
dvander@2762:                  const Arg& ptr5,
dvander@2762:                  const Arg& ptr6,
dvander@2762:                  const Arg& ptr7,
dvander@2762:                  const Arg& ptr8,
dvander@2762:                  const Arg& ptr9,
dvander@2762:                  const Arg& ptr10,
dvander@2762:                  const Arg& ptr11,
dvander@2762:                  const Arg& ptr12,
dvander@2762:                  const Arg& ptr13,
dvander@2762:                  const Arg& ptr14,
dvander@2762:                  const Arg& ptr15,
dvander@2762:                  const Arg& ptr16) const {
dvander@2762:   const Arg* args[kMaxArgs];
dvander@2762:   int n = 0;
dvander@2762:   if (&ptr1  == &no_arg) goto done; args[n++] = &ptr1;
dvander@2762:   if (&ptr2  == &no_arg) goto done; args[n++] = &ptr2;
dvander@2762:   if (&ptr3  == &no_arg) goto done; args[n++] = &ptr3;
dvander@2762:   if (&ptr4  == &no_arg) goto done; args[n++] = &ptr4;
dvander@2762:   if (&ptr5  == &no_arg) goto done; args[n++] = &ptr5;
dvander@2762:   if (&ptr6  == &no_arg) goto done; args[n++] = &ptr6;
dvander@2762:   if (&ptr7  == &no_arg) goto done; args[n++] = &ptr7;
dvander@2762:   if (&ptr8  == &no_arg) goto done; args[n++] = &ptr8;
dvander@2762:   if (&ptr9  == &no_arg) goto done; args[n++] = &ptr9;
dvander@2762:   if (&ptr10 == &no_arg) goto done; args[n++] = &ptr10;
dvander@2762:   if (&ptr11 == &no_arg) goto done; args[n++] = &ptr11;
dvander@2762:   if (&ptr12 == &no_arg) goto done; args[n++] = &ptr12;
dvander@2762:   if (&ptr13 == &no_arg) goto done; args[n++] = &ptr13;
dvander@2762:   if (&ptr14 == &no_arg) goto done; args[n++] = &ptr14;
dvander@2762:   if (&ptr15 == &no_arg) goto done; args[n++] = &ptr15;
dvander@2762:   if (&ptr16 == &no_arg) goto done; args[n++] = &ptr16;
dvander@2762:  done:
dvander@2762: 
dvander@2762:   int consumed;
dvander@2762:   int vec[kVecSize];
dvander@2762:   if (DoMatchImpl(*input, ANCHOR_START, &consumed,
dvander@2762:                   args, n, vec, kVecSize)) {
dvander@2762:     input->remove_prefix(consumed);
dvander@2762:     return true;
dvander@2762:   } else {
dvander@2762:     return false;
dvander@2762:   }
dvander@2762: }
dvander@2762: 
dvander@2762: bool RE::FindAndConsume(StringPiece* input,
dvander@2762:                         const Arg& ptr1,
dvander@2762:                         const Arg& ptr2,
dvander@2762:                         const Arg& ptr3,
dvander@2762:                         const Arg& ptr4,
dvander@2762:                         const Arg& ptr5,
dvander@2762:                         const Arg& ptr6,
dvander@2762:                         const Arg& ptr7,
dvander@2762:                         const Arg& ptr8,
dvander@2762:                         const Arg& ptr9,
dvander@2762:                         const Arg& ptr10,
dvander@2762:                         const Arg& ptr11,
dvander@2762:                         const Arg& ptr12,
dvander@2762:                         const Arg& ptr13,
dvander@2762:                         const Arg& ptr14,
dvander@2762:                         const Arg& ptr15,
dvander@2762:                         const Arg& ptr16) const {
dvander@2762:   const Arg* args[kMaxArgs];
dvander@2762:   int n = 0;
dvander@2762:   if (&ptr1  == &no_arg) goto done; args[n++] = &ptr1;
dvander@2762:   if (&ptr2  == &no_arg) goto done; args[n++] = &ptr2;
dvander@2762:   if (&ptr3  == &no_arg) goto done; args[n++] = &ptr3;
dvander@2762:   if (&ptr4  == &no_arg) goto done; args[n++] = &ptr4;
dvander@2762:   if (&ptr5  == &no_arg) goto done; args[n++] = &ptr5;
dvander@2762:   if (&ptr6  == &no_arg) goto done; args[n++] = &ptr6;
dvander@2762:   if (&ptr7  == &no_arg) goto done; args[n++] = &ptr7;
dvander@2762:   if (&ptr8  == &no_arg) goto done; args[n++] = &ptr8;
dvander@2762:   if (&ptr9  == &no_arg) goto done; args[n++] = &ptr9;
dvander@2762:   if (&ptr10 == &no_arg) goto done; args[n++] = &ptr10;
dvander@2762:   if (&ptr11 == &no_arg) goto done; args[n++] = &ptr11;
dvander@2762:   if (&ptr12 == &no_arg) goto done; args[n++] = &ptr12;
dvander@2762:   if (&ptr13 == &no_arg) goto done; args[n++] = &ptr13;
dvander@2762:   if (&ptr14 == &no_arg) goto done; args[n++] = &ptr14;
dvander@2762:   if (&ptr15 == &no_arg) goto done; args[n++] = &ptr15;
dvander@2762:   if (&ptr16 == &no_arg) goto done; args[n++] = &ptr16;
dvander@2762:  done:
dvander@2762: 
dvander@2762:   int consumed;
dvander@2762:   int vec[kVecSize];
dvander@2762:   if (DoMatchImpl(*input, UNANCHORED, &consumed,
dvander@2762:                   args, n, vec, kVecSize)) {
dvander@2762:     input->remove_prefix(consumed);
dvander@2762:     return true;
dvander@2762:   } else {
dvander@2762:     return false;
dvander@2762:   }
dvander@2762: }
dvander@2762: 
dvander@2762: bool RE::Replace(const StringPiece& rewrite,
dvander@2762:                  string *str) const {
dvander@2762:   int vec[kVecSize];
dvander@2762:   int matches = TryMatch(*str, 0, UNANCHORED, vec, kVecSize);
dvander@2762:   if (matches == 0)
dvander@2762:     return false;
dvander@2762: 
dvander@2762:   string s;
dvander@2762:   if (!Rewrite(&s, rewrite, *str, vec, matches))
dvander@2762:     return false;
dvander@2762: 
dvander@2762:   assert(vec[0] >= 0);
dvander@2762:   assert(vec[1] >= 0);
dvander@2762:   str->replace(vec[0], vec[1] - vec[0], s);
dvander@2762:   return true;
dvander@2762: }
dvander@2762: 
dvander@2762: // Returns PCRE_NEWLINE_CRLF, PCRE_NEWLINE_CR, or PCRE_NEWLINE_LF.
dvander@2762: // Note that PCRE_NEWLINE_CRLF is defined to be P_N_CR | P_N_LF.
dvander@2762: // Modified by PH to add PCRE_NEWLINE_ANY and PCRE_NEWLINE_ANYCRLF.
dvander@2762: 
dvander@2762: static int NewlineMode(int pcre_options) {
dvander@2762:   // TODO: if we can make it threadsafe, cache this var
dvander@2762:   int newline_mode = 0;
dvander@2762:   /* if (newline_mode) return newline_mode; */  // do this once it's cached
dvander@2762:   if (pcre_options & (PCRE_NEWLINE_CRLF|PCRE_NEWLINE_CR|PCRE_NEWLINE_LF|
dvander@2762:                       PCRE_NEWLINE_ANY|PCRE_NEWLINE_ANYCRLF)) {
dvander@2762:     newline_mode = (pcre_options &
dvander@2762:                     (PCRE_NEWLINE_CRLF|PCRE_NEWLINE_CR|PCRE_NEWLINE_LF|
dvander@2762:                      PCRE_NEWLINE_ANY|PCRE_NEWLINE_ANYCRLF));
dvander@2762:   } else {
dvander@2762:     int newline;
dvander@2762:     pcre_config(PCRE_CONFIG_NEWLINE, &newline);
dvander@2762:     if (newline == 10)
dvander@2762:       newline_mode = PCRE_NEWLINE_LF;
dvander@2762:     else if (newline == 13)
dvander@2762:       newline_mode = PCRE_NEWLINE_CR;
dvander@2762:     else if (newline == 3338)
dvander@2762:       newline_mode = PCRE_NEWLINE_CRLF;
dvander@2762:     else if (newline == -1)
dvander@2762:       newline_mode = PCRE_NEWLINE_ANY;
dvander@2762:     else if (newline == -2)
dvander@2762:       newline_mode = PCRE_NEWLINE_ANYCRLF;
dvander@2762:     else
dvander@2762:       assert(NULL == "Unexpected return value from pcre_config(NEWLINE)");
dvander@2762:   }
dvander@2762:   return newline_mode;
dvander@2762: }
dvander@2762: 
dvander@2762: int RE::GlobalReplace(const StringPiece& rewrite,
dvander@2762:                       string *str) const {
dvander@2762:   int count = 0;
dvander@2762:   int vec[kVecSize];
dvander@2762:   string out;
dvander@2762:   int start = 0;
dvander@2762:   int lastend = -1;
dvander@2762: 
dvander@2762:   while (start <= static_cast<int>(str->length())) {
dvander@2762:     int matches = TryMatch(*str, start, UNANCHORED, vec, kVecSize);
dvander@2762:     if (matches <= 0)
dvander@2762:       break;
dvander@2762:     int matchstart = vec[0], matchend = vec[1];
dvander@2762:     assert(matchstart >= start);
dvander@2762:     assert(matchend >= matchstart);
dvander@2762:     if (matchstart == matchend && matchstart == lastend) {
dvander@2762:       // advance one character if we matched an empty string at the same
dvander@2762:       // place as the last match occurred
dvander@2762:       matchend = start + 1;
dvander@2762:       // If the current char is CR and we're in CRLF mode, skip LF too.
dvander@2762:       // Note it's better to call pcre_fullinfo() than to examine
dvander@2762:       // all_options(), since options_ could have changed bewteen
dvander@2762:       // compile-time and now, but this is simpler and safe enough.
dvander@2762:       // Modified by PH to add ANY and ANYCRLF.
dvander@2762:       if (start+1 < static_cast<int>(str->length()) &&
dvander@2762:           (*str)[start] == '\r' && (*str)[start+1] == '\n' &&
dvander@2762:           (NewlineMode(options_.all_options()) == PCRE_NEWLINE_CRLF ||
dvander@2762:            NewlineMode(options_.all_options()) == PCRE_NEWLINE_ANY ||
dvander@2762:            NewlineMode(options_.all_options()) == PCRE_NEWLINE_ANYCRLF)
dvander@2762:           ) {
dvander@2762:         matchend++;
dvander@2762:       }
dvander@2762:       // We also need to advance more than one char if we're in utf8 mode.
dvander@2762: #ifdef SUPPORT_UTF8
dvander@2762:       if (options_.utf8()) {
dvander@2762:         while (matchend < static_cast<int>(str->length()) &&
dvander@2762:                ((*str)[matchend] & 0xc0) == 0x80)
dvander@2762:           matchend++;
dvander@2762:       }
dvander@2762: #endif
dvander@2762:       if (matchend <= static_cast<int>(str->length()))
dvander@2762:         out.append(*str, start, matchend - start);
dvander@2762:       start = matchend;
dvander@2762:     } else {
dvander@2762:       out.append(*str, start, matchstart - start);
dvander@2762:       Rewrite(&out, rewrite, *str, vec, matches);
dvander@2762:       start = matchend;
dvander@2762:       lastend = matchend;
dvander@2762:       count++;
dvander@2762:     }
dvander@2762:   }
dvander@2762: 
dvander@2762:   if (count == 0)
dvander@2762:     return 0;
dvander@2762: 
dvander@2762:   if (start < static_cast<int>(str->length()))
dvander@2762:     out.append(*str, start, str->length() - start);
dvander@2762:   swap(out, *str);
dvander@2762:   return count;
dvander@2762: }
dvander@2762: 
dvander@2762: bool RE::Extract(const StringPiece& rewrite,
dvander@2762:                  const StringPiece& text,
dvander@2762:                  string *out) const {
dvander@2762:   int vec[kVecSize];
dvander@2762:   int matches = TryMatch(text, 0, UNANCHORED, vec, kVecSize);
dvander@2762:   if (matches == 0)
dvander@2762:     return false;
dvander@2762:   out->erase();
dvander@2762:   return Rewrite(out, rewrite, text, vec, matches);
dvander@2762: }
dvander@2762: 
dvander@2762: /*static*/ string RE::QuoteMeta(const StringPiece& unquoted) {
dvander@2762:   string result;
dvander@2762: 
dvander@2762:   // Escape any ascii character not in [A-Za-z_0-9].
dvander@2762:   //
dvander@2762:   // Note that it's legal to escape a character even if it has no
dvander@2762:   // special meaning in a regular expression -- so this function does
dvander@2762:   // that.  (This also makes it identical to the perl function of the
dvander@2762:   // same name; see `perldoc -f quotemeta`.)  The one exception is
dvander@2762:   // escaping NUL: rather than doing backslash + NUL, like perl does,
dvander@2762:   // we do '\0', because pcre itself doesn't take embedded NUL chars.
dvander@2762:   for (int ii = 0; ii < unquoted.size(); ++ii) {
dvander@2762:     // Note that using 'isalnum' here raises the benchmark time from
dvander@2762:     // 32ns to 58ns:
dvander@2762:     if (unquoted[ii] == '\0') {
dvander@2762:       result += "\\0";
dvander@2762:     } else if ((unquoted[ii] < 'a' || unquoted[ii] > 'z') &&
dvander@2762:                (unquoted[ii] < 'A' || unquoted[ii] > 'Z') &&
dvander@2762:                (unquoted[ii] < '0' || unquoted[ii] > '9') &&
dvander@2762:                unquoted[ii] != '_' &&
dvander@2762:                // If this is the part of a UTF8 or Latin1 character, we need
dvander@2762:                // to copy this byte without escaping.  Experimentally this is
dvander@2762:                // what works correctly with the regexp library.
dvander@2762:                !(unquoted[ii] & 128)) {
dvander@2762:       result += '\\';
dvander@2762:       result += unquoted[ii];
dvander@2762:     } else {
dvander@2762:       result += unquoted[ii];
dvander@2762:     }
dvander@2762:   }
dvander@2762: 
dvander@2762:   return result;
dvander@2762: }
dvander@2762: 
dvander@2762: /***** Actual matching and rewriting code *****/
dvander@2762: 
dvander@2762: int RE::TryMatch(const StringPiece& text,
dvander@2762:                  int startpos,
dvander@2762:                  Anchor anchor,
dvander@2762:                  int *vec,
dvander@2762:                  int vecsize) const {
dvander@2762:   pcre* re = (anchor == ANCHOR_BOTH) ? re_full_ : re_partial_;
dvander@2762:   if (re == NULL) {
dvander@2762:     //fprintf(stderr, "Matching against invalid re: %s\n", error_->c_str());
dvander@2762:     return 0;
dvander@2762:   }
dvander@2762: 
dvander@2762:   pcre_extra extra = { 0, 0, 0, 0, 0, 0 };
dvander@2762:   if (options_.match_limit() > 0) {
dvander@2762:     extra.flags |= PCRE_EXTRA_MATCH_LIMIT;
dvander@2762:     extra.match_limit = options_.match_limit();
dvander@2762:   }
dvander@2762:   if (options_.match_limit_recursion() > 0) {
dvander@2762:     extra.flags |= PCRE_EXTRA_MATCH_LIMIT_RECURSION;
dvander@2762:     extra.match_limit_recursion = options_.match_limit_recursion();
dvander@2762:   }
dvander@2762:   int rc = pcre_exec(re,              // The regular expression object
dvander@2762:                      &extra,
dvander@2762:                      (text.data() == NULL) ? "" : text.data(),
dvander@2762:                      text.size(),
dvander@2762:                      startpos,
dvander@2762:                      (anchor == UNANCHORED) ? 0 : PCRE_ANCHORED,
dvander@2762:                      vec,
dvander@2762:                      vecsize);
dvander@2762: 
dvander@2762:   // Handle errors
dvander@2762:   if (rc == PCRE_ERROR_NOMATCH) {
dvander@2762:     return 0;
dvander@2762:   } else if (rc < 0) {
dvander@2762:     //fprintf(stderr, "Unexpected return code: %d when matching '%s'\n",
dvander@2762:     //        re, pattern_.c_str());
dvander@2762:     return 0;
dvander@2762:   } else if (rc == 0) {
dvander@2762:     // pcre_exec() returns 0 as a special case when the number of
dvander@2762:     // capturing subpatterns exceeds the size of the vector.
dvander@2762:     // When this happens, there is a match and the output vector
dvander@2762:     // is filled, but we miss out on the positions of the extra subpatterns.
dvander@2762:     rc = vecsize / 2;
dvander@2762:   }
dvander@2762: 
dvander@2762:   return rc;
dvander@2762: }
dvander@2762: 
dvander@2762: bool RE::DoMatchImpl(const StringPiece& text,
dvander@2762:                      Anchor anchor,
dvander@2762:                      int* consumed,
dvander@2762:                      const Arg* const* args,
dvander@2762:                      int n,
dvander@2762:                      int* vec,
dvander@2762:                      int vecsize) const {
dvander@2762:   assert((1 + n) * 3 <= vecsize);  // results + PCRE workspace
dvander@2762:   int matches = TryMatch(text, 0, anchor, vec, vecsize);
dvander@2762:   assert(matches >= 0);  // TryMatch never returns negatives
dvander@2762:   if (matches == 0)
dvander@2762:     return false;
dvander@2762: 
dvander@2762:   *consumed = vec[1];
dvander@2762: 
dvander@2762:   if (n == 0 || args == NULL) {
dvander@2762:     // We are not interested in results
dvander@2762:     return true;
dvander@2762:   }
dvander@2762: 
dvander@2762:   if (NumberOfCapturingGroups() < n) {
dvander@2762:     // RE has fewer capturing groups than number of arg pointers passed in
dvander@2762:     return false;
dvander@2762:   }
dvander@2762: 
dvander@2762:   // If we got here, we must have matched the whole pattern.
dvander@2762:   // We do not need (can not do) any more checks on the value of 'matches' here
dvander@2762:   // -- see the comment for TryMatch.
dvander@2762:   for (int i = 0; i < n; i++) {
dvander@2762:     const int start = vec[2*(i+1)];
dvander@2762:     const int limit = vec[2*(i+1)+1];
dvander@2762:     if (!args[i]->Parse(text.data() + start, limit-start)) {
dvander@2762:       // TODO: Should we indicate what the error was?
dvander@2762:       return false;
dvander@2762:     }
dvander@2762:   }
dvander@2762: 
dvander@2762:   return true;
dvander@2762: }
dvander@2762: 
dvander@2762: bool RE::DoMatch(const StringPiece& text,
dvander@2762:                  Anchor anchor,
dvander@2762:                  int* consumed,
dvander@2762:                  const Arg* const args[],
dvander@2762:                  int n) const {
dvander@2762:   assert(n >= 0);
dvander@2762:   size_t const vecsize = (1 + n) * 3;  // results + PCRE workspace
dvander@2762:                                        // (as for kVecSize)
dvander@2762:   int space[21];   // use stack allocation for small vecsize (common case)
dvander@2762:   int* vec = vecsize <= 21 ? space : new int[vecsize];
dvander@2762:   bool retval = DoMatchImpl(text, anchor, consumed, args, n, vec, vecsize);
dvander@2762:   if (vec != space) delete [] vec;
dvander@2762:   return retval;
dvander@2762: }
dvander@2762: 
dvander@2762: bool RE::Rewrite(string *out, const StringPiece &rewrite,
dvander@2762:                  const StringPiece &text, int *vec, int veclen) const {
dvander@2762:   for (const char *s = rewrite.data(), *end = s + rewrite.size();
dvander@2762:        s < end; s++) {
dvander@2762:     int c = *s;
dvander@2762:     if (c == '\\') {
dvander@2762:       c = *++s;
dvander@2762:       if (isdigit(c)) {
dvander@2762:         int n = (c - '0');
dvander@2762:         if (n >= veclen) {
dvander@2762:           //fprintf(stderr, requested group %d in regexp %.*s\n",
dvander@2762:           //        n, rewrite.size(), rewrite.data());
dvander@2762:           return false;
dvander@2762:         }
dvander@2762:         int start = vec[2 * n];
dvander@2762:         if (start >= 0)
dvander@2762:           out->append(text.data() + start, vec[2 * n + 1] - start);
dvander@2762:       } else if (c == '\\') {
dvander@2762:         *out += '\\';
dvander@2762:       } else {
dvander@2762:         //fprintf(stderr, "invalid rewrite pattern: %.*s\n",
dvander@2762:         //        rewrite.size(), rewrite.data());
dvander@2762:         return false;
dvander@2762:       }
dvander@2762:     } else {
dvander@2762:       *out += c;
dvander@2762:     }
dvander@2762:   }
dvander@2762:   return true;
dvander@2762: }
dvander@2762: 
dvander@2762: // Return the number of capturing subpatterns, or -1 if the
dvander@2762: // regexp wasn't valid on construction.
dvander@2762: int RE::NumberOfCapturingGroups() const {
dvander@2762:   if (re_partial_ == NULL) return -1;
dvander@2762: 
dvander@2762:   int result;
dvander@2762:   int pcre_retval = pcre_fullinfo(re_partial_,  // The regular expression object
dvander@2762:                                   NULL,         // We did not study the pattern
dvander@2762:                                   PCRE_INFO_CAPTURECOUNT,
dvander@2762:                                   &result);
dvander@2762:   assert(pcre_retval == 0);
dvander@2762:   return result;
dvander@2762: }
dvander@2762: 
dvander@2762: /***** Parsers for various types *****/
dvander@2762: 
dvander@2762: bool Arg::parse_null(const char* str, int n, void* dest) {
dvander@2762:   // We fail if somebody asked us to store into a non-NULL void* pointer
dvander@2762:   return (dest == NULL);
dvander@2762: }
dvander@2762: 
dvander@2762: bool Arg::parse_string(const char* str, int n, void* dest) {
dvander@2762:   if (dest == NULL) return true;
dvander@2762:   reinterpret_cast<string*>(dest)->assign(str, n);
dvander@2762:   return true;
dvander@2762: }
dvander@2762: 
dvander@2762: bool Arg::parse_stringpiece(const char* str, int n, void* dest) {
dvander@2762:   if (dest == NULL) return true;
dvander@2762:   reinterpret_cast<StringPiece*>(dest)->set(str, n);
dvander@2762:   return true;
dvander@2762: }
dvander@2762: 
dvander@2762: bool Arg::parse_char(const char* str, int n, void* dest) {
dvander@2762:   if (n != 1) return false;
dvander@2762:   if (dest == NULL) return true;
dvander@2762:   *(reinterpret_cast<char*>(dest)) = str[0];
dvander@2762:   return true;
dvander@2762: }
dvander@2762: 
dvander@2762: bool Arg::parse_uchar(const char* str, int n, void* dest) {
dvander@2762:   if (n != 1) return false;
dvander@2762:   if (dest == NULL) return true;
dvander@2762:   *(reinterpret_cast<unsigned char*>(dest)) = str[0];
dvander@2762:   return true;
dvander@2762: }
dvander@2762: 
dvander@2762: // Largest number spec that we are willing to parse
dvander@2762: static const int kMaxNumberLength = 32;
dvander@2762: 
dvander@2762: // REQUIRES "buf" must have length at least kMaxNumberLength+1
dvander@2762: // REQUIRES "n > 0"
dvander@2762: // Copies "str" into "buf" and null-terminates if necessary.
dvander@2762: // Returns one of:
dvander@2762: //      a. "str" if no termination is needed
dvander@2762: //      b. "buf" if the string was copied and null-terminated
dvander@2762: //      c. "" if the input was invalid and has no hope of being parsed
dvander@2762: static const char* TerminateNumber(char* buf, const char* str, int n) {
dvander@2762:   if ((n > 0) && isspace(*str)) {
dvander@2762:     // We are less forgiving than the strtoxxx() routines and do not
dvander@2762:     // allow leading spaces.
dvander@2762:     return "";
dvander@2762:   }
dvander@2762: 
dvander@2762:   // See if the character right after the input text may potentially
dvander@2762:   // look like a digit.
dvander@2762:   if (isdigit(str[n]) ||
dvander@2762:       ((str[n] >= 'a') && (str[n] <= 'f')) ||
dvander@2762:       ((str[n] >= 'A') && (str[n] <= 'F'))) {
dvander@2762:     if (n > kMaxNumberLength) return ""; // Input too big to be a valid number
dvander@2762:     memcpy(buf, str, n);
dvander@2762:     buf[n] = '\0';
dvander@2762:     return buf;
dvander@2762:   } else {
dvander@2762:     // We can parse right out of the supplied string, so return it.
dvander@2762:     return str;
dvander@2762:   }
dvander@2762: }
dvander@2762: 
dvander@2762: bool Arg::parse_long_radix(const char* str,
dvander@2762:                            int n,
dvander@2762:                            void* dest,
dvander@2762:                            int radix) {
dvander@2762:   if (n == 0) return false;
dvander@2762:   char buf[kMaxNumberLength+1];
dvander@2762:   str = TerminateNumber(buf, str, n);
dvander@2762:   char* end;
dvander@2762:   errno = 0;
dvander@2762:   long r = strtol(str, &end, radix);
dvander@2762:   if (end != str + n) return false;   // Leftover junk
dvander@2762:   if (errno) return false;
dvander@2762:   if (dest == NULL) return true;
dvander@2762:   *(reinterpret_cast<long*>(dest)) = r;
dvander@2762:   return true;
dvander@2762: }
dvander@2762: 
dvander@2762: bool Arg::parse_ulong_radix(const char* str,
dvander@2762:                             int n,
dvander@2762:                             void* dest,
dvander@2762:                             int radix) {
dvander@2762:   if (n == 0) return false;
dvander@2762:   char buf[kMaxNumberLength+1];
dvander@2762:   str = TerminateNumber(buf, str, n);
dvander@2762:   if (str[0] == '-') return false;    // strtoul() on a negative number?!
dvander@2762:   char* end;
dvander@2762:   errno = 0;
dvander@2762:   unsigned long r = strtoul(str, &end, radix);
dvander@2762:   if (end != str + n) return false;   // Leftover junk
dvander@2762:   if (errno) return false;
dvander@2762:   if (dest == NULL) return true;
dvander@2762:   *(reinterpret_cast<unsigned long*>(dest)) = r;
dvander@2762:   return true;
dvander@2762: }
dvander@2762: 
dvander@2762: bool Arg::parse_short_radix(const char* str,
dvander@2762:                             int n,
dvander@2762:                             void* dest,
dvander@2762:                             int radix) {
dvander@2762:   long r;
dvander@2762:   if (!parse_long_radix(str, n, &r, radix)) return false; // Could not parse
dvander@2762:   if (r < SHRT_MIN || r > SHRT_MAX) return false;       // Out of range
dvander@2762:   if (dest == NULL) return true;
dvander@2762:   *(reinterpret_cast<short*>(dest)) = static_cast<short>(r);
dvander@2762:   return true;
dvander@2762: }
dvander@2762: 
dvander@2762: bool Arg::parse_ushort_radix(const char* str,
dvander@2762:                              int n,
dvander@2762:                              void* dest,
dvander@2762:                              int radix) {
dvander@2762:   unsigned long r;
dvander@2762:   if (!parse_ulong_radix(str, n, &r, radix)) return false; // Could not parse
dvander@2762:   if (r > USHRT_MAX) return false;                      // Out of range
dvander@2762:   if (dest == NULL) return true;
dvander@2762:   *(reinterpret_cast<unsigned short*>(dest)) = static_cast<unsigned short>(r);
dvander@2762:   return true;
dvander@2762: }
dvander@2762: 
dvander@2762: bool Arg::parse_int_radix(const char* str,
dvander@2762:                           int n,
dvander@2762:                           void* dest,
dvander@2762:                           int radix) {
dvander@2762:   long r;
dvander@2762:   if (!parse_long_radix(str, n, &r, radix)) return false; // Could not parse
dvander@2762:   if (r < INT_MIN || r > INT_MAX) return false;         // Out of range
dvander@2762:   if (dest == NULL) return true;
dvander@2762:   *(reinterpret_cast<int*>(dest)) = r;
dvander@2762:   return true;
dvander@2762: }
dvander@2762: 
dvander@2762: bool Arg::parse_uint_radix(const char* str,
dvander@2762:                            int n,
dvander@2762:                            void* dest,
dvander@2762:                            int radix) {
dvander@2762:   unsigned long r;
dvander@2762:   if (!parse_ulong_radix(str, n, &r, radix)) return false; // Could not parse
dvander@2762:   if (r > UINT_MAX) return false;                       // Out of range
dvander@2762:   if (dest == NULL) return true;
dvander@2762:   *(reinterpret_cast<unsigned int*>(dest)) = r;
dvander@2762:   return true;
dvander@2762: }
dvander@2762: 
dvander@2762: bool Arg::parse_longlong_radix(const char* str,
dvander@2762:                                int n,
dvander@2762:                                void* dest,
dvander@2762:                                int radix) {
dvander@2762: #ifndef HAVE_LONG_LONG
dvander@2762:   return false;
dvander@2762: #else
dvander@2762:   if (n == 0) return false;
dvander@2762:   char buf[kMaxNumberLength+1];
dvander@2762:   str = TerminateNumber(buf, str, n);
dvander@2762:   char* end;
dvander@2762:   errno = 0;
dvander@2762: #if defined HAVE_STRTOQ
dvander@2762:   long long r = strtoq(str, &end, radix);
dvander@2762: #elif defined HAVE_STRTOLL
dvander@2762:   long long r = strtoll(str, &end, radix);
dvander@2762: #elif defined HAVE__STRTOI64
dvander@2762:   long long r = _strtoi64(str, &end, radix);
dvander@2762: #else
dvander@2762: #error parse_longlong_radix: cannot convert input to a long-long
dvander@2762: #endif
dvander@2762:   if (end != str + n) return false;   // Leftover junk
dvander@2762:   if (errno) return false;
dvander@2762:   if (dest == NULL) return true;
dvander@2762:   *(reinterpret_cast<long long*>(dest)) = r;
dvander@2762:   return true;
dvander@2762: #endif   /* HAVE_LONG_LONG */
dvander@2762: }
dvander@2762: 
dvander@2762: bool Arg::parse_ulonglong_radix(const char* str,
dvander@2762:                                 int n,
dvander@2762:                                 void* dest,
dvander@2762:                                 int radix) {
dvander@2762: #ifndef HAVE_UNSIGNED_LONG_LONG
dvander@2762:   return false;
dvander@2762: #else
dvander@2762:   if (n == 0) return false;
dvander@2762:   char buf[kMaxNumberLength+1];
dvander@2762:   str = TerminateNumber(buf, str, n);
dvander@2762:   if (str[0] == '-') return false;    // strtoull() on a negative number?!
dvander@2762:   char* end;
dvander@2762:   errno = 0;
dvander@2762: #if defined HAVE_STRTOQ
dvander@2762:   unsigned long long r = strtouq(str, &end, radix);
dvander@2762: #elif defined HAVE_STRTOLL
dvander@2762:   unsigned long long r = strtoull(str, &end, radix);
dvander@2762: #elif defined HAVE__STRTOI64
dvander@2762:   unsigned long long r = _strtoui64(str, &end, radix);
dvander@2762: #else
dvander@2762: #error parse_ulonglong_radix: cannot convert input to a long-long
dvander@2762: #endif
dvander@2762:   if (end != str + n) return false;   // Leftover junk
dvander@2762:   if (errno) return false;
dvander@2762:   if (dest == NULL) return true;
dvander@2762:   *(reinterpret_cast<unsigned long long*>(dest)) = r;
dvander@2762:   return true;
dvander@2762: #endif   /* HAVE_UNSIGNED_LONG_LONG */
dvander@2762: }
dvander@2762: 
dvander@2762: bool Arg::parse_double(const char* str, int n, void* dest) {
dvander@2762:   if (n == 0) return false;
dvander@2762:   static const int kMaxLength = 200;
dvander@2762:   char buf[kMaxLength];
dvander@2762:   if (n >= kMaxLength) return false;
dvander@2762:   memcpy(buf, str, n);
dvander@2762:   buf[n] = '\0';
dvander@2762:   errno = 0;
dvander@2762:   char* end;
dvander@2762:   double r = strtod(buf, &end);
dvander@2762:   if (end != buf + n) return false;   // Leftover junk
dvander@2762:   if (errno) return false;
dvander@2762:   if (dest == NULL) return true;
dvander@2762:   *(reinterpret_cast<double*>(dest)) = r;
dvander@2762:   return true;
dvander@2762: }
dvander@2762: 
dvander@2762: bool Arg::parse_float(const char* str, int n, void* dest) {
dvander@2762:   double r;
dvander@2762:   if (!parse_double(str, n, &r)) return false;
dvander@2762:   if (dest == NULL) return true;
dvander@2762:   *(reinterpret_cast<float*>(dest)) = static_cast<float>(r);
dvander@2762:   return true;
dvander@2762: }
dvander@2762: 
dvander@2762: 
dvander@2762: #define DEFINE_INTEGER_PARSERS(name)                                    \
dvander@2762:   bool Arg::parse_##name(const char* str, int n, void* dest) {          \
dvander@2762:     return parse_##name##_radix(str, n, dest, 10);                      \
dvander@2762:   }                                                                     \
dvander@2762:   bool Arg::parse_##name##_hex(const char* str, int n, void* dest) {    \
dvander@2762:     return parse_##name##_radix(str, n, dest, 16);                      \
dvander@2762:   }                                                                     \
dvander@2762:   bool Arg::parse_##name##_octal(const char* str, int n, void* dest) {  \
dvander@2762:     return parse_##name##_radix(str, n, dest, 8);                       \
dvander@2762:   }                                                                     \
dvander@2762:   bool Arg::parse_##name##_cradix(const char* str, int n, void* dest) { \
dvander@2762:     return parse_##name##_radix(str, n, dest, 0);                       \
dvander@2762:   }
dvander@2762: 
dvander@2762: DEFINE_INTEGER_PARSERS(short)      /*                                   */
dvander@2762: DEFINE_INTEGER_PARSERS(ushort)     /*                                   */
dvander@2762: DEFINE_INTEGER_PARSERS(int)        /* Don't use semicolons after these  */
dvander@2762: DEFINE_INTEGER_PARSERS(uint)       /* statements because they can cause */
dvander@2762: DEFINE_INTEGER_PARSERS(long)       /* compiler warnings if the checking */
dvander@2762: DEFINE_INTEGER_PARSERS(ulong)      /* level is turned up high enough.   */
dvander@2762: DEFINE_INTEGER_PARSERS(longlong)   /*                                   */
dvander@2762: DEFINE_INTEGER_PARSERS(ulonglong)  /*                                   */
dvander@2762: 
dvander@2762: #undef DEFINE_INTEGER_PARSERS
dvander@2762: 
dvander@2762: }   // namespace pcrecpp