// Copyright (c) 2005, Google Inc.

// All rights reserved.

//

// Redistribution and use in source and binary forms, with or without

// modification, are permitted provided that the following conditions are

// met:

//

//     * Redistributions of source code must retain the above copyright

// notice, this list of conditions and the following disclaimer.

//     * Redistributions in binary form must reproduce the above

// copyright notice, this list of conditions and the following disclaimer

// in the documentation and/or other materials provided with the

// distribution.

//     * Neither the name of Google Inc. nor the names of its

// contributors may be used to endorse or promote products derived from

// this software without specific prior written permission.

//

// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS

// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT

// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR

// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT

// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,

// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT

// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,

// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY

// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT

// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE

// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

//

// Author: Sanjay Ghemawat

#ifdef HAVE_CONFIG_H

#include "config.h"

#endif

#include <stdlib.h>

#include <stdio.h>

#include <ctype.h>

#include <limits.h>      /* for SHRT_MIN, USHRT_MAX, etc */

#include <assert.h>

#include <errno.h>

#include <string>

#include <algorithm>

#include "pcrecpp_internal.h"

#include "pcre.h"

#include "pcrecpp.h"

#include "pcre_stringpiece.h"

namespace pcrecpp {

// Maximum number of args we can set

static const int kMaxArgs = 16;

static const int kVecSize = (1 + kMaxArgs) * 3;  // results + PCRE workspace

// Special object that stands-in for no argument

Arg RE::no_arg((void*)NULL);

// This is for ABI compatibility with old versions of pcre (pre-7.6),

// which defined a global no_arg variable instead of putting it in the

// RE class.  This works on GCC >= 3, at least.  It definitely works

// for ELF, but may not for other object formats (Mach-O, for

// instance, does not support aliases.)  We could probably have a more

// inclusive test if we ever needed it.  (Note that not only the

// __attribute__ syntax, but also __USER_LABEL_PREFIX__, are

// gnu-specific.)

#if defined(__GNUC__) && __GNUC__ >= 3 && defined(__ELF__)

# define ULP_AS_STRING(x)            ULP_AS_STRING_INTERNAL(x)

# define ULP_AS_STRING_INTERNAL(x)   #x

# define USER_LABEL_PREFIX_STR       ULP_AS_STRING(__USER_LABEL_PREFIX__)

extern Arg no_arg

  __attribute__((alias(USER_LABEL_PREFIX_STR "_ZN7pcrecpp2RE6no_argE")));

#endif

// If a regular expression has no error, its error_ field points here

static const string empty_string;

// If the user doesn't ask for any options, we just use this one

static RE_Options default_options;

void RE::Init(const string& pat, const RE_Options* options) {

  pattern_ = pat;

  if (options == NULL) {

    options_ = default_options;

  } else {

    options_ = *options;

  }

  error_ = &empty_string;

  re_full_ = NULL;

  re_partial_ = NULL;

  re_partial_ = Compile(UNANCHORED);

  if (re_partial_ != NULL) {

    re_full_ = Compile(ANCHOR_BOTH);

  }

}

void RE::Cleanup() {

  if (re_full_ != NULL)         (*pcre_free)(re_full_);

  if (re_partial_ != NULL)      (*pcre_free)(re_partial_);

  if (error_ != &empty_string)  delete error_;

}

RE::~RE() {

  Cleanup();

}

pcre* RE::Compile(Anchor anchor) {

  // First, convert RE_Options into pcre options

  int pcre_options = 0;

  pcre_options = options_.all_options();

  // Special treatment for anchoring.  This is needed because at

  // runtime pcre only provides an option for anchoring at the

  // beginning of a string (unless you use offset).

  //

  // There are three types of anchoring we want:

  //    UNANCHORED      Compile the original pattern, and use

  //                    a pcre unanchored match.

  //    ANCHOR_START    Compile the original pattern, and use

  //                    a pcre anchored match.

  //    ANCHOR_BOTH     Tack a "\z" to the end of the original pattern

  //                    and use a pcre anchored match.

  const char* compile_error;

  int eoffset;

  pcre* re;

  if (anchor != ANCHOR_BOTH) {

    re = pcre_compile(pattern_.c_str(), pcre_options,

                      &compile_error, &eoffset, NULL);

  } else {

    // Tack a '\z' at the end of RE.  Parenthesize it first so that

    // the '\z' applies to all top-level alternatives in the regexp.

    string wrapped = "(?:";  // A non-counting grouping operator

    wrapped += pattern_;

    wrapped += ")\\z";

    re = pcre_compile(wrapped.c_str(), pcre_options,

                      &compile_error, &eoffset, NULL);

  }

  if (re == NULL) {

    if (error_ == &empty_string) error_ = new string(compile_error);

  }

  return re;

}

/***** Matching interfaces *****/

bool RE::FullMatch(const StringPiece& text,

                   const Arg& ptr1,

                   const Arg& ptr2,

                   const Arg& ptr3,

                   const Arg& ptr4,

                   const Arg& ptr5,

                   const Arg& ptr6,

                   const Arg& ptr7,

                   const Arg& ptr8,

                   const Arg& ptr9,

                   const Arg& ptr10,

                   const Arg& ptr11,

                   const Arg& ptr12,

                   const Arg& ptr13,

                   const Arg& ptr14,

                   const Arg& ptr15,

                   const Arg& ptr16) const {

  const Arg* args[kMaxArgs];

  int n = 0;

  if (&ptr1  == &no_arg) goto done; args[n++] = &ptr1;

  if (&ptr2  == &no_arg) goto done; args[n++] = &ptr2;

  if (&ptr3  == &no_arg) goto done; args[n++] = &ptr3;

  if (&ptr4  == &no_arg) goto done; args[n++] = &ptr4;

  if (&ptr5  == &no_arg) goto done; args[n++] = &ptr5;

  if (&ptr6  == &no_arg) goto done; args[n++] = &ptr6;

  if (&ptr7  == &no_arg) goto done; args[n++] = &ptr7;

  if (&ptr8  == &no_arg) goto done; args[n++] = &ptr8;

  if (&ptr9  == &no_arg) goto done; args[n++] = &ptr9;

  if (&ptr10 == &no_arg) goto done; args[n++] = &ptr10;

  if (&ptr11 == &no_arg) goto done; args[n++] = &ptr11;

  if (&ptr12 == &no_arg) goto done; args[n++] = &ptr12;

  if (&ptr13 == &no_arg) goto done; args[n++] = &ptr13;

  if (&ptr14 == &no_arg) goto done; args[n++] = &ptr14;

  if (&ptr15 == &no_arg) goto done; args[n++] = &ptr15;

  if (&ptr16 == &no_arg) goto done; args[n++] = &ptr16;

 done:

  int consumed;

  int vec[kVecSize];

  return DoMatchImpl(text, ANCHOR_BOTH, &consumed, args, n, vec, kVecSize);

}

bool RE::PartialMatch(const StringPiece& text,

                      const Arg& ptr1,

                      const Arg& ptr2,

                      const Arg& ptr3,

                      const Arg& ptr4,

                      const Arg& ptr5,

                      const Arg& ptr6,

                      const Arg& ptr7,

                      const Arg& ptr8,

                      const Arg& ptr9,

                      const Arg& ptr10,

                      const Arg& ptr11,

                      const Arg& ptr12,

                      const Arg& ptr13,

                      const Arg& ptr14,

                      const Arg& ptr15,

                      const Arg& ptr16) const {

  const Arg* args[kMaxArgs];

  int n = 0;

  if (&ptr1  == &no_arg) goto done; args[n++] = &ptr1;

  if (&ptr2  == &no_arg) goto done; args[n++] = &ptr2;

  if (&ptr3  == &no_arg) goto done; args[n++] = &ptr3;

  if (&ptr4  == &no_arg) goto done; args[n++] = &ptr4;

  if (&ptr5  == &no_arg) goto done; args[n++] = &ptr5;

  if (&ptr6  == &no_arg) goto done; args[n++] = &ptr6;

  if (&ptr7  == &no_arg) goto done; args[n++] = &ptr7;

  if (&ptr8  == &no_arg) goto done; args[n++] = &ptr8;

  if (&ptr9  == &no_arg) goto done; args[n++] = &ptr9;

  if (&ptr10 == &no_arg) goto done; args[n++] = &ptr10;

  if (&ptr11 == &no_arg) goto done; args[n++] = &ptr11;

  if (&ptr12 == &no_arg) goto done; args[n++] = &ptr12;

  if (&ptr13 == &no_arg) goto done; args[n++] = &ptr13;

  if (&ptr14 == &no_arg) goto done; args[n++] = &ptr14;

  if (&ptr15 == &no_arg) goto done; args[n++] = &ptr15;

  if (&ptr16 == &no_arg) goto done; args[n++] = &ptr16;

 done:

  int consumed;

  int vec[kVecSize];

  return DoMatchImpl(text, UNANCHORED, &consumed, args, n, vec, kVecSize);

}

bool RE::Consume(StringPiece* input,

                 const Arg& ptr1,

                 const Arg& ptr2,

                 const Arg& ptr3,

                 const Arg& ptr4,

                 const Arg& ptr5,

                 const Arg& ptr6,

                 const Arg& ptr7,

                 const Arg& ptr8,

                 const Arg& ptr9,

                 const Arg& ptr10,

                 const Arg& ptr11,

                 const Arg& ptr12,

                 const Arg& ptr13,

                 const Arg& ptr14,

                 const Arg& ptr15,

                 const Arg& ptr16) const {

  const Arg* args[kMaxArgs];

  int n = 0;

  if (&ptr1  == &no_arg) goto done; args[n++] = &ptr1;

  if (&ptr2  == &no_arg) goto done; args[n++] = &ptr2;

  if (&ptr3  == &no_arg) goto done; args[n++] = &ptr3;

  if (&ptr4  == &no_arg) goto done; args[n++] = &ptr4;

  if (&ptr5  == &no_arg) goto done; args[n++] = &ptr5;

  if (&ptr6  == &no_arg) goto done; args[n++] = &ptr6;

  if (&ptr7  == &no_arg) goto done; args[n++] = &ptr7;

  if (&ptr8  == &no_arg) goto done; args[n++] = &ptr8;

  if (&ptr9  == &no_arg) goto done; args[n++] = &ptr9;

  if (&ptr10 == &no_arg) goto done; args[n++] = &ptr10;

  if (&ptr11 == &no_arg) goto done; args[n++] = &ptr11;

  if (&ptr12 == &no_arg) goto done; args[n++] = &ptr12;

  if (&ptr13 == &no_arg) goto done; args[n++] = &ptr13;

  if (&ptr14 == &no_arg) goto done; args[n++] = &ptr14;

  if (&ptr15 == &no_arg) goto done; args[n++] = &ptr15;

  if (&ptr16 == &no_arg) goto done; args[n++] = &ptr16;

 done:

  int consumed;

  int vec[kVecSize];

  if (DoMatchImpl(*input, ANCHOR_START, &consumed,

                  args, n, vec, kVecSize)) {

    input->remove_prefix(consumed);

    return true;

  } else {

    return false;

  }

}

bool RE::FindAndConsume(StringPiece* input,

                        const Arg& ptr1,

                        const Arg& ptr2,

                        const Arg& ptr3,

                        const Arg& ptr4,

                        const Arg& ptr5,

                        const Arg& ptr6,

                        const Arg& ptr7,

                        const Arg& ptr8,

                        const Arg& ptr9,

                        const Arg& ptr10,

                        const Arg& ptr11,

                        const Arg& ptr12,

                        const Arg& ptr13,

                        const Arg& ptr14,

                        const Arg& ptr15,

                        const Arg& ptr16) const {

  const Arg* args[kMaxArgs];

  int n = 0;

  if (&ptr1  == &no_arg) goto done; args[n++] = &ptr1;

  if (&ptr2  == &no_arg) goto done; args[n++] = &ptr2;

  if (&ptr3  == &no_arg) goto done; args[n++] = &ptr3;

  if (&ptr4  == &no_arg) goto done; args[n++] = &ptr4;

  if (&ptr5  == &no_arg) goto done; args[n++] = &ptr5;

  if (&ptr6  == &no_arg) goto done; args[n++] = &ptr6;

  if (&ptr7  == &no_arg) goto done; args[n++] = &ptr7;

  if (&ptr8  == &no_arg) goto done; args[n++] = &ptr8;

  if (&ptr9  == &no_arg) goto done; args[n++] = &ptr9;

  if (&ptr10 == &no_arg) goto done; args[n++] = &ptr10;

  if (&ptr11 == &no_arg) goto done; args[n++] = &ptr11;

  if (&ptr12 == &no_arg) goto done; args[n++] = &ptr12;

  if (&ptr13 == &no_arg) goto done; args[n++] = &ptr13;

  if (&ptr14 == &no_arg) goto done; args[n++] = &ptr14;

  if (&ptr15 == &no_arg) goto done; args[n++] = &ptr15;

  if (&ptr16 == &no_arg) goto done; args[n++] = &ptr16;

 done:

  int consumed;

  int vec[kVecSize];

  if (DoMatchImpl(*input, UNANCHORED, &consumed,

                  args, n, vec, kVecSize)) {

    input->remove_prefix(consumed);

    return true;

  } else {

    return false;

  }

}

bool RE::Replace(const StringPiece& rewrite,

                 string *str) const {

  int vec[kVecSize];

  int matches = TryMatch(*str, 0, UNANCHORED, vec, kVecSize);

  if (matches == 0)

    return false;

  string s;

  if (!Rewrite(&s, rewrite, *str, vec, matches))

    return false;

  assert(vec[0] >= 0);

  assert(vec[1] >= 0);

  str->replace(vec[0], vec[1] - vec[0], s);

  return true;

}

// Returns PCRE_NEWLINE_CRLF, PCRE_NEWLINE_CR, or PCRE_NEWLINE_LF.

// Note that PCRE_NEWLINE_CRLF is defined to be P_N_CR | P_N_LF.

// Modified by PH to add PCRE_NEWLINE_ANY and PCRE_NEWLINE_ANYCRLF.

static int NewlineMode(int pcre_options) {

  // TODO: if we can make it threadsafe, cache this var

  int newline_mode = 0;

  /* if (newline_mode) return newline_mode; */  // do this once it's cached

  if (pcre_options & (PCRE_NEWLINE_CRLF|PCRE_NEWLINE_CR|PCRE_NEWLINE_LF|

                      PCRE_NEWLINE_ANY|PCRE_NEWLINE_ANYCRLF)) {

    newline_mode = (pcre_options &

                    (PCRE_NEWLINE_CRLF|PCRE_NEWLINE_CR|PCRE_NEWLINE_LF|

                     PCRE_NEWLINE_ANY|PCRE_NEWLINE_ANYCRLF));

  } else {

    int newline;

    pcre_config(PCRE_CONFIG_NEWLINE, &newline);

    if (newline == 10)

      newline_mode = PCRE_NEWLINE_LF;

    else if (newline == 13)

      newline_mode = PCRE_NEWLINE_CR;

    else if (newline == 3338)

      newline_mode = PCRE_NEWLINE_CRLF;

    else if (newline == -1)

      newline_mode = PCRE_NEWLINE_ANY;

    else if (newline == -2)

      newline_mode = PCRE_NEWLINE_ANYCRLF;

    else

      assert(NULL == "Unexpected return value from pcre_config(NEWLINE)");

  }

  return newline_mode;

}

int RE::GlobalReplace(const StringPiece& rewrite,

                      string *str) const {

  int count = 0;

  int vec[kVecSize];

  string out;

  int start = 0;

  int lastend = -1;

  while (start <= static_cast<int>(str->length())) {

    int matches = TryMatch(*str, start, UNANCHORED, vec, kVecSize);

    if (matches <= 0)

      break;

    int matchstart = vec[0], matchend = vec[1];

    assert(matchstart >= start);

    assert(matchend >= matchstart);

    if (matchstart == matchend && matchstart == lastend) {

      // advance one character if we matched an empty string at the same

      // place as the last match occurred

      matchend = start + 1;

      // If the current char is CR and we're in CRLF mode, skip LF too.

      // Note it's better to call pcre_fullinfo() than to examine

      // all_options(), since options_ could have changed bewteen

      // compile-time and now, but this is simpler and safe enough.

      // Modified by PH to add ANY and ANYCRLF.

      if (start+1 < static_cast<int>(str->length()) &&

          (*str)[start] == '\r' && (*str)[start+1] == '\n' &&

          (NewlineMode(options_.all_options()) == PCRE_NEWLINE_CRLF ||

           NewlineMode(options_.all_options()) == PCRE_NEWLINE_ANY ||

           NewlineMode(options_.all_options()) == PCRE_NEWLINE_ANYCRLF)

          ) {

        matchend++;

      }

      // We also need to advance more than one char if we're in utf8 mode.

#ifdef SUPPORT_UTF8

      if (options_.utf8()) {

        while (matchend < static_cast<int>(str->length()) &&

               ((*str)[matchend] & 0xc0) == 0x80)

          matchend++;

      }

#endif

      if (matchend <= static_cast<int>(str->length()))

        out.append(*str, start, matchend - start);

      start = matchend;

    } else {

      out.append(*str, start, matchstart - start);

      Rewrite(&out, rewrite, *str, vec, matches);

      start = matchend;

      lastend = matchend;

      count++;

    }

  }

  if (count == 0)

    return 0;

  if (start < static_cast<int>(str->length()))

    out.append(*str, start, str->length() - start);

  swap(out, *str);

  return count;

}

bool RE::Extract(const StringPiece& rewrite,

                 const StringPiece& text,

                 string *out) const {

  int vec[kVecSize];

  int matches = TryMatch(text, 0, UNANCHORED, vec, kVecSize);

  if (matches == 0)

    return false;

  out->erase();

  return Rewrite(out, rewrite, text, vec, matches);

}

/*static*/ string RE::QuoteMeta(const StringPiece& unquoted) {

  string result;

  // Escape any ascii character not in [A-Za-z_0-9].

  //

  // Note that it's legal to escape a character even if it has no

  // special meaning in a regular expression -- so this function does

  // that.  (This also makes it identical to the perl function of the

  // same name; see `perldoc -f quotemeta`.)  The one exception is

  // escaping NUL: rather than doing backslash + NUL, like perl does,

  // we do '\0', because pcre itself doesn't take embedded NUL chars.

  for (int ii = 0; ii < unquoted.size(); ++ii) {

    // Note that using 'isalnum' here raises the benchmark time from

    // 32ns to 58ns:

    if (unquoted[ii] == '\0') {

      result += "\\0";

    } else if ((unquoted[ii] < 'a' || unquoted[ii] > 'z') &&

               (unquoted[ii] < 'A' || unquoted[ii] > 'Z') &&

               (unquoted[ii] < '0' || unquoted[ii] > '9') &&

               unquoted[ii] != '_' &&

               // If this is the part of a UTF8 or Latin1 character, we need

               // to copy this byte without escaping.  Experimentally this is

               // what works correctly with the regexp library.

               !(unquoted[ii] & 128)) {

      result += '\\';

      result += unquoted[ii];

    } else {

      result += unquoted[ii];

    }

  }

  return result;

}

/***** Actual matching and rewriting code *****/

int RE::TryMatch(const StringPiece& text,

                 int startpos,

                 Anchor anchor,

                 int *vec,

                 int vecsize) const {

  pcre* re = (anchor == ANCHOR_BOTH) ? re_full_ : re_partial_;

  if (re == NULL) {

    //fprintf(stderr, "Matching against invalid re: %s\n", error_->c_str());

    return 0;

  }

  pcre_extra extra = { 0, 0, 0, 0, 0, 0 };

  if (options_.match_limit() > 0) {

    extra.flags |= PCRE_EXTRA_MATCH_LIMIT;

    extra.match_limit = options_.match_limit();

  }

  if (options_.match_limit_recursion() > 0) {

    extra.flags |= PCRE_EXTRA_MATCH_LIMIT_RECURSION;

    extra.match_limit_recursion = options_.match_limit_recursion();

  }

  int rc = pcre_exec(re,              // The regular expression object

                     &extra,

                     (text.data() == NULL) ? "" : text.data(),

                     text.size(),

                     startpos,

                     (anchor == UNANCHORED) ? 0 : PCRE_ANCHORED,

                     vec,

                     vecsize);

  // Handle errors

  if (rc == PCRE_ERROR_NOMATCH) {

    return 0;

  } else if (rc < 0) {

    //fprintf(stderr, "Unexpected return code: %d when matching '%s'\n",

    //        re, pattern_.c_str());

    return 0;

  } else if (rc == 0) {

    // pcre_exec() returns 0 as a special case when the number of

    // capturing subpatterns exceeds the size of the vector.

    // When this happens, there is a match and the output vector

    // is filled, but we miss out on the positions of the extra subpatterns.