Update re2

third_party/re2/re2/re2.cc

 // Copyright 2003-2009 The RE2 Authors.  All Rights Reserved.
 // Use of this source code is governed by a BSD-style
 // license that can be found in the LICENSE file.
 
 // Regular expression interface RE2.
 //
 // Originally the PCRE C++ wrapper, but adapted to use
 // the new automata-based regular expression engines.
 
 #include "re2/re2.h"
 
 #include <stdio.h>
 #include <string>
-#ifdef WIN32
-#define strtoll _strtoi64
-#define strtoull _strtoui64
-#define strtof strtod
-#else
-#include <pthread.h>
-#endif
 #include <errno.h>
 #include "util/util.h"
 #include "util/flags.h"
+#include "util/sparse_array.h"
 #include "re2/prog.h"
 #include "re2/regexp.h"
 
 DEFINE_bool(trace_re2, false, "trace RE2 execution");
 
 namespace re2 {
 
 // Maximum number of args we can set
 static const int kMaxArgs = 16;
 static const int kVecSize = 1+kMaxArgs;
 
 const VariadicFunction2<bool, const StringPiece&, const RE2&, RE2::Arg, RE2::FullMatchN> RE2::FullMatch = {};
 const VariadicFunction2<bool, const StringPiece&, const RE2&, RE2::Arg, RE2::PartialMatchN> RE2::PartialMatch = {};
 const VariadicFunction2<bool, StringPiece*, const RE2&, RE2::Arg, RE2::ConsumeN> RE2::Consume = {};
 const VariadicFunction2<bool, StringPiece*, const RE2&, RE2::Arg, RE2::FindAndConsumeN> RE2::FindAndConsume = {};
 
-#define kDefaultMaxMem (8<<20)
-
-RE2::Options::Options()
-  :  encoding_(EncodingUTF8),
-     posix_syntax_(false),
-     longest_match_(false),
-     log_errors_(true),
-     max_mem_(kDefaultMaxMem),
-     literal_(false),
-     never_nl_(false),
-     never_capture_(false),
-     case_sensitive_(true),
-     perl_classes_(false),
-     word_boundary_(false),
-     one_line_(false) {
-}
+// This will trigger LNK2005 error in MSVC.
+#ifndef _MSC_VER
+const int RE2::Options::kDefaultMaxMem;  // initialized in re2.h
+#endif
 
 RE2::Options::Options(RE2::CannedOptions opt)
   : encoding_(opt == RE2::Latin1 ? EncodingLatin1 : EncodingUTF8),
     posix_syntax_(opt == RE2::POSIX),
     longest_match_(opt == RE2::POSIX),
     log_errors_(opt != RE2::Quiet),
     max_mem_(kDefaultMaxMem),
     literal_(false),
     never_nl_(false),
+    dot_nl_(false),
     never_capture_(false),
     case_sensitive_(true),
     perl_classes_(false),
     word_boundary_(false),
     one_line_(false) {
 }
 
 // static empty things for use as const references.
 // To avoid global constructors, initialized on demand.
 GLOBAL_MUTEX(empty_mutex);
@@ skipping 87 matching lines @@
 
   if (!posix_syntax())
     flags |= Regexp::LikePerl;
 
   if (literal())
     flags |= Regexp::Literal;
 
   if (never_nl())
     flags |= Regexp::NeverNL;
 
+  if (dot_nl())
+    flags |= Regexp::DotNL;
+
   if (never_capture())
     flags |= Regexp::NeverCapture;
 
   if (!case_sensitive())
     flags |= Regexp::FoldCase;
 
   if (perl_classes())
     flags |= Regexp::PerlClasses;
 
   if (word_boundary())
@@ skipping 96 matching lines @@
   if (group_names_ != NULL &&  group_names_ != empty_group_names)
     delete group_names_;
 }
 
 int RE2::ProgramSize() const {
   if (prog_ == NULL)
     return -1;
   return prog_->size();
 }
 
+int RE2::ProgramFanout(map<int, int>* histogram) const {
+  if (prog_ == NULL)
+    return -1;
+  SparseArray<int> fanout(prog_->size());
+  prog_->Fanout(&fanout);
+  histogram->clear();
+  for (SparseArray<int>::iterator i = fanout.begin(); i != fanout.end(); ++i) {
+    // TODO(junyer): Optimise this?
+    int bucket = 0;
+    while (1 << bucket < i->second) {
+      bucket++;
+    }
+    (*histogram)[bucket]++;
+  }
+  return histogram->rbegin()->first;
+}
+
+// Returns num_captures_, computing it if needed, or -1 if the
+// regexp wasn't valid on construction.
+int RE2::NumberOfCapturingGroups() const {
+  MutexLock l(mutex_);
+  if (suffix_regexp_ == NULL)
+    return -1;
+  if (num_captures_ == -1)
+    num_captures_ = suffix_regexp_->NumCaptures();
+  return num_captures_;
+}
+
 // Returns named_groups_, computing it if needed.
-const map<string, int>&  RE2::NamedCapturingGroups() const {
+const map<string, int>& RE2::NamedCapturingGroups() const {
   MutexLock l(mutex_);
   if (!ok())
     return *empty_named_groups;
   if (named_groups_ == NULL) {
     named_groups_ = suffix_regexp_->NamedCaptures();
     if (named_groups_ == NULL)
       named_groups_ = empty_named_groups;
   }
   return *named_groups_;
 }
 
 // Returns group_names_, computing it if needed.
-const map<int, string>&  RE2::CapturingGroupNames() const {
+const map<int, string>& RE2::CapturingGroupNames() const {
   MutexLock l(mutex_);
   if (!ok())
     return *empty_group_names;
   if (group_names_ == NULL) {
     group_names_ = suffix_regexp_->CaptureNames();
     if (group_names_ == NULL)
       group_names_ = empty_group_names;
   }
   return *group_names_;
 }
@@ skipping 51 matching lines @@
   return max;
 }
 
 bool RE2::Replace(string *str,
                  const RE2& re,
                  const StringPiece& rewrite) {
   StringPiece vec[kVecSize];
   int nvec = 1 + MaxSubmatch(rewrite);
   if (nvec > arraysize(vec))
     return false;
-  if (!re.Match(*str, 0, str->size(), UNANCHORED, vec, nvec))
+  if (!re.Match(*str, 0, static_cast<int>(str->size()), UNANCHORED, vec, nvec))
     return false;
 
   string s;
   if (!re.Rewrite(&s, rewrite, vec, nvec))
     return false;
 
   assert(vec[0].begin() >= str->data());
   assert(vec[0].end() <= str->data()+str->size());
   str->replace(vec[0].data() - str->data(), vec[0].size(), s);
   return true;
 }
 
 int RE2::GlobalReplace(string *str,
                       const RE2& re,
                       const StringPiece& rewrite) {
   StringPiece vec[kVecSize];
   int nvec = 1 + MaxSubmatch(rewrite);
   if (nvec > arraysize(vec))
     return false;
 
   const char* p = str->data();
   const char* ep = p + str->size();
   const char* lastend = NULL;
   string out;
   int count = 0;
   while (p <= ep) {
-    if (!re.Match(*str, p - str->data(), str->size(), UNANCHORED, vec, nvec))
+    if (!re.Match(*str, static_cast<int>(p - str->data()),
+                  static_cast<int>(str->size()), UNANCHORED, vec, nvec))
       break;
     if (p < vec[0].begin())
       out.append(p, vec[0].begin() - p);
     if (vec[0].begin() == lastend && vec[0].size() == 0) {
       // Disallow empty match at end of last match: skip ahead.
       if (p < ep)
         out.append(p, 1);
       p++;
       continue;
     }
@@ skipping 63 matching lines @@
     result += unquoted[ii];
   }
 
   return result;
 }
 
 bool RE2::PossibleMatchRange(string* min, string* max, int maxlen) const {
   if (prog_ == NULL)
     return false;
 
-  int n = prefix_.size();
+  int n = static_cast<int>(prefix_.size());
   if (n > maxlen)
     n = maxlen;
 
   // Determine initial min max from prefix_ literal.
   string pmin, pmax;
   pmin = prefix_.substr(0, n);
   pmax = prefix_.substr(0, n);
   if (prefix_foldcase_) {
     // prefix is ASCII lowercase; change pmin to uppercase.
     for (int i = 0; i < n; i++) {
@@ skipping 51 matching lines @@
                 StringPiece* submatch,
                 int nsubmatch) const {
   if (!ok() || suffix_regexp_ == NULL) {
     if (options_.log_errors())
       LOG(ERROR) << "Invalid RE2: " << *error_;
     return false;
   }
 
   if (startpos < 0 || startpos > endpos || endpos > text.size()) {
     if (options_.log_errors())
-      LOG(ERROR) << "RE2: invalid startpos, endpos pair.";
+      LOG(ERROR) << "RE2: invalid startpos, endpos pair. ["
+                 << "startpos: " << startpos << ", "
+                 << "endpos: " << endpos << ", "
+                 << "text size: " << text.size() << "]";
     return false;
   }
 
   StringPiece subtext = text;
   subtext.remove_prefix(startpos);
   subtext.remove_suffix(text.size() - endpos);
 
   // Use DFAs to find exact location of match, filter out non-matches.
 
   // Don't ask for the location if we won't use it.
@@ skipping 16 matching lines @@
   if (prog_->anchor_start() && prog_->anchor_end())
     re_anchor = ANCHOR_BOTH;
   else if (prog_->anchor_start() && re_anchor != ANCHOR_BOTH)
     re_anchor = ANCHOR_START;
 
   // Check for the required prefix, if any.
   int prefixlen = 0;
   if (!prefix_.empty()) {
     if (startpos != 0)
       return false;
-    prefixlen = prefix_.size();
+    prefixlen = static_cast<int>(prefix_.size());
     if (prefixlen > subtext.size())
       return false;
     if (prefix_foldcase_) {
       if (ascii_strcasecmp(&prefix_[0], subtext.data(), prefixlen) != 0)
         return false;
     } else {
       if (memcmp(&prefix_[0], subtext.data(), prefixlen) != 0)
         return false;
     }
     subtext.remove_prefix(prefixlen);
@@ skipping 220 matching lines @@
   } else {
     vec = new StringPiece[nvec];
     heapvec = vec;
   }
 
   if (!Match(text, 0, text.size(), anchor, vec, nvec)) {
     delete[] heapvec;
     return false;
   }
 
-  if(consumed != NULL)
-    *consumed = vec[0].end() - text.begin();
+  if (consumed != NULL)
+    *consumed = static_cast<int>(vec[0].end() - text.begin());
 
   if (n == 0 || args == NULL) {
     // We are not interested in results
     delete[] heapvec;
     return true;
   }
 
   int ncap = NumberOfCapturingGroups();
   if (ncap < n) {
     // RE has fewer capturing groups than number of arg pointers passed in
     VLOG(1) << "Asked for " << n << " but only have " << ncap;
     delete[] heapvec;
     return false;
   }
 
   // If we got here, we must have matched the whole pattern.
   for (int i = 0; i < n; i++) {
     const StringPiece& s = vec[i+1];
     if (!args[i]->Parse(s.data(), s.size())) {
       // TODO: Should we indicate what the error was?
       VLOG(1) << "Parse error on #" << i << " " << s << " "
-              << (void*)s.data() << "/" << s.size();
+              << (void*)s.data() << "/" << s.size();
       delete[] heapvec;
       return false;
     }
   }
 
   delete[] heapvec;
   return true;
 }
 
 // Append the "rewrite" string, with backslash subsitutions from "vec",
 // to string "out".
 bool RE2::Rewrite(string *out, const StringPiece &rewrite,
                  const StringPiece *vec, int veclen) const {
   for (const char *s = rewrite.data(), *end = s + rewrite.size();
        s < end; s++) {
-    int c = *s;
-    if (c == '\\') {
-      s++;
-      c = (s < end) ? *s : -1;
-      if (isdigit(c)) {
-        int n = (c - '0');
-        if (n >= veclen) {
-          if (options_.log_errors()) {
-            LOG(ERROR) << "requested group " << n
-                       << " in regexp " << rewrite.data();
-          }
-          return false;
+    if (*s != '\\') {
+      out->push_back(*s);
+      continue;
+    }
+    s++;
+    int c = (s < end) ? *s : -1;
+    if (isdigit(c)) {
+      int n = (c - '0');
+      if (n >= veclen) {
+        if (options_.log_errors()) {
+          LOG(ERROR) << "requested group " << n
+                     << " in regexp " << rewrite.data();
         }
-        StringPiece snip = vec[n];
-        if (snip.size() > 0)
-          out->append(snip.data(), snip.size());
-      } else if (c == '\\') {
-        out->push_back('\\');
-      } else {
-        if (options_.log_errors())
-          LOG(ERROR) << "invalid rewrite pattern: " << rewrite.data();
         return false;
       }
+      StringPiece snip = vec[n];
+      if (snip.size() > 0)
+        out->append(snip.data(), snip.size());
+    } else if (c == '\\') {
+      out->push_back('\\');
     } else {
-      out->push_back(c);
+      if (options_.log_errors())
+        LOG(ERROR) << "invalid rewrite pattern: " << rewrite.data();
+      return false;
     }
   }
   return true;
 }
 
-// Return the number of capturing subpatterns, or -1 if the
-// regexp wasn't valid on construction.
-int RE2::NumberOfCapturingGroups() const {
-  if (suffix_regexp_ == NULL)
-    return -1;
-  ANNOTATE_BENIGN_RACE(&num_captures_, "benign race: in the worst case"
-    " multiple threads end up doing the same work in parallel.");
-  if (num_captures_ == -1)
-    num_captures_ = suffix_regexp_->NumCaptures();
-  return num_captures_;
-}
-
 // Checks that the rewrite string is well-formed with respect to this
 // regular expression.
 bool RE2::CheckRewriteString(const StringPiece& rewrite, string* error) const {
   int max_token = -1;
   for (const char *s = rewrite.data(), *end = s + rewrite.size();
        s < end; s++) {
     int c = *s;
     if (c != '\\') {
       continue;
     }
@@ skipping 54 matching lines @@
 bool RE2::Arg::parse_uchar(const char* str, int n, void* dest) {
   if (n != 1) return false;
   if (dest == NULL) return true;
   *(reinterpret_cast<unsigned char*>(dest)) = str[0];
   return true;
 }
 
 // Largest number spec that we are willing to parse
 static const int kMaxNumberLength = 32;
 
-// REQUIRES "buf" must have length at least kMaxNumberLength+1
+// REQUIRES "buf" must have length at least nbuf.
 // Copies "str" into "buf" and null-terminates.
 // Overwrites *np with the new length.
-static const char* TerminateNumber(char* buf, const char* str, int* np) {
+static const char* TerminateNumber(char* buf, int nbuf, const char* str, int* np,
+                                   bool accept_spaces) {
   int n = *np;
   if (n <= 0) return "";
   if (n > 0 && isspace(*str)) {
     // We are less forgiving than the strtoxxx() routines and do not
-    // allow leading spaces.
-    return "";
+    // allow leading spaces. We do allow leading spaces for floats.
+    if (!accept_spaces) {
+      return "";
+    }
+    while (n > 0 && isspace(*str)) {
+      n--;
+      str++;
+    }
   }
 
   // Although buf has a fixed maximum size, we can still handle
   // arbitrarily large integers correctly by omitting leading zeros.
   // (Numbers that are still too long will be out of range.)
   // Before deciding whether str is too long,
   // remove leading zeros with s/000+/00/.
   // Leaving the leading two zeros in place means that
   // we don't change 0000x123 (invalid) into 0x123 (valid).
   // Skip over leading - before replacing.
   bool neg = false;
   if (n >= 1 && str[0] == '-') {
     neg = true;
     n--;
     str++;
   }
 
   if (n >= 3 && str[0] == '0' && str[1] == '0') {
     while (n >= 3 && str[2] == '0') {
       n--;
       str++;
     }
   }
 
   if (neg) {  // make room in buf for -
     n++;
     str--;
   }
 
-  if (n > kMaxNumberLength) return "";
+  if (n > nbuf-1) return "";
 
   memmove(buf, str, n);
   if (neg) {
     buf[0] = '-';
   }
   buf[n] = '\0';
   *np = n;
   return buf;
 }
 
 bool RE2::Arg::parse_long_radix(const char* str,
                                int n,
                                void* dest,
                                int radix) {
   if (n == 0) return false;
   char buf[kMaxNumberLength+1];
-  str = TerminateNumber(buf, str, &n);
+  str = TerminateNumber(buf, sizeof buf, str, &n, false);
   char* end;
   errno = 0;
   long r = strtol(str, &end, radix);
   if (end != str + n) return false;   // Leftover junk
   if (errno) return false;
   if (dest == NULL) return true;
   *(reinterpret_cast<long*>(dest)) = r;
   return true;
 }
 
 bool RE2::Arg::parse_ulong_radix(const char* str,
                                 int n,
                                 void* dest,
                                 int radix) {
   if (n == 0) return false;
   char buf[kMaxNumberLength+1];
-  str = TerminateNumber(buf, str, &n);
+  str = TerminateNumber(buf, sizeof buf, str, &n, false);
   if (str[0] == '-') {
    // strtoul() will silently accept negative numbers and parse
    // them.  This module is more strict and treats them as errors.
    return false;
   }
 
   char* end;
   errno = 0;
   unsigned long r = strtoul(str, &end, radix);
   if (end != str + n) return false;   // Leftover junk
   if (errno) return false;
   if (dest == NULL) return true;
   *(reinterpret_cast<unsigned long*>(dest)) = r;
   return true;
 }
 
 bool RE2::Arg::parse_short_radix(const char* str,
                                 int n,
                                 void* dest,
                                 int radix) {
   long r;
   if (!parse_long_radix(str, n, &r, radix)) return false; // Could not parse
   if ((short)r != r) return false;       // Out of range
   if (dest == NULL) return true;
-  *(reinterpret_cast<short*>(dest)) = r;
+  *(reinterpret_cast<short*>(dest)) = (short)r;
   return true;
 }
 
 bool RE2::Arg::parse_ushort_radix(const char* str,
                                  int n,
                                  void* dest,
                                  int radix) {
   unsigned long r;
   if (!parse_ulong_radix(str, n, &r, radix)) return false; // Could not parse
   if ((ushort)r != r) return false;                      // Out of range
   if (dest == NULL) return true;
-  *(reinterpret_cast<unsigned short*>(dest)) = r;
+  *(reinterpret_cast<unsigned short*>(dest)) = (ushort)r;
   return true;
 }
 
 bool RE2::Arg::parse_int_radix(const char* str,
                               int n,
                               void* dest,
                               int radix) {
   long r;
   if (!parse_long_radix(str, n, &r, radix)) return false; // Could not parse
   if ((int)r != r) return false;         // Out of range
   if (dest == NULL) return true;
   *(reinterpret_cast<int*>(dest)) = r;
   return true;
 }
 
 bool RE2::Arg::parse_uint_radix(const char* str,
                                int n,
                                void* dest,
                                int radix) {
   unsigned long r;
   if (!parse_ulong_radix(str, n, &r, radix)) return false; // Could not parse
   if ((uint)r != r) return false;                       // Out of range
   if (dest == NULL) return true;
   *(reinterpret_cast<unsigned int*>(dest)) = r;
   return true;
 }
 
+#if RE2_HAVE_LONGLONG
 bool RE2::Arg::parse_longlong_radix(const char* str,
                                    int n,
                                    void* dest,
                                    int radix) {
   if (n == 0) return false;
   char buf[kMaxNumberLength+1];
-  str = TerminateNumber(buf, str, &n);
+  str = TerminateNumber(buf, sizeof buf, str, &n, false);
   char* end;
   errno = 0;
   int64 r = strtoll(str, &end, radix);
   if (end != str + n) return false;   // Leftover junk
   if (errno) return false;
   if (dest == NULL) return true;
   *(reinterpret_cast<int64*>(dest)) = r;
   return true;
 }
 
 bool RE2::Arg::parse_ulonglong_radix(const char* str,
                                     int n,
                                     void* dest,
                                     int radix) {
   if (n == 0) return false;
   char buf[kMaxNumberLength+1];
-  str = TerminateNumber(buf, str, &n);
+  str = TerminateNumber(buf, sizeof buf, str, &n, false);
   if (str[0] == '-') {
     // strtoull() will silently accept negative numbers and parse
     // them.  This module is more strict and treats them as errors.
     return false;
   }
   char* end;
   errno = 0;
   uint64 r = strtoull(str, &end, radix);
   if (end != str + n) return false;   // Leftover junk
   if (errno) return false;
   if (dest == NULL) return true;
   *(reinterpret_cast<uint64*>(dest)) = r;
   return true;
 }
+#endif
 
 static bool parse_double_float(const char* str, int n, bool isfloat, void *dest) {
   if (n == 0) return false;
   static const int kMaxLength = 200;
-  char buf[kMaxLength];
-  if (n >= kMaxLength) return false;
-  memcpy(buf, str, n);
-  buf[n] = '\0';
+  char buf[kMaxLength+1];
+  str = TerminateNumber(buf, sizeof buf, str, &n, true);
+  char* end;
   errno = 0;
-  char* end;
   double r;
   if (isfloat) {
-    r = strtof(buf, &end);
+    r = strtof(str, &end);
   } else {
-    r = strtod(buf, &end);
+    r = strtod(str, &end);
   }
-  if (end != buf + n) return false;   // Leftover junk
+  if (end != str + n) return false;   // Leftover junk
   if (errno) return false;
   if (dest == NULL) return true;
   if (isfloat) {
-    *(reinterpret_cast<float*>(dest)) = r;
+    *(reinterpret_cast<float*>(dest)) = (float)r;
   } else {
     *(reinterpret_cast<double*>(dest)) = r;
   }
   return true;
 }
 
 bool RE2::Arg::parse_double(const char* str, int n, void* dest) {
   return parse_double_float(str, n, false, dest);
 }
 
@@ skipping 21 matching lines @@
 DEFINE_INTEGER_PARSERS(int);
 DEFINE_INTEGER_PARSERS(uint);
 DEFINE_INTEGER_PARSERS(long);
 DEFINE_INTEGER_PARSERS(ulong);
 DEFINE_INTEGER_PARSERS(longlong);
 DEFINE_INTEGER_PARSERS(ulonglong);
 
 #undef DEFINE_INTEGER_PARSERS
 
 }  // namespace re2