Update re2

third_party/re2/re2/testing/re2_test.cc

 // -*- coding: utf-8 -*-
 // Copyright 2002-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.
 
 // TODO: Test extractions for PartialMatch/Consume
 
-#include <sys/types.h>
-#ifndef WIN32
+#include <errno.h>
+#ifndef _MSC_VER
+#include <unistd.h>  /* for sysconf */
 #include <sys/mman.h>
 #endif
 #include <sys/stat.h>
-#include <errno.h>
+#include <sys/types.h>
 #include <vector>
 #include "util/test.h"
 #include "re2/re2.h"
 #include "re2/regexp.h"
 
-#ifdef WIN32
-#include <stdio.h>
-#define snprintf _snprintf
-#endif
-
 DECLARE_bool(logtostderr);
 
 namespace re2 {
 
 TEST(RE2, HexTests) {
 
   VLOG(1) << "hex tests";
 
 #define CHECK_HEX(type, value) \
   do { \
@@ skipping 139 matching lines @@
     // Check newline handling
     { "a.*a",
       "(\\0)",
       "aba\naba",
       "(aba)\naba",
       "(aba)\n(aba)",
       2 },
     { "", NULL, NULL, NULL, NULL, 0 }
   };
 
-  for (const ReplaceTest *t = tests; t->original != NULL; ++t) {
+  for (const ReplaceTest* t = tests; t->original != NULL; t++) {
     VLOG(1) << StringPrintf("\"%s\" =~ s/%s/%s/g", t->original, t->regexp, t->rewrite);
     string one(t->original);
     CHECK(RE2::Replace(&one, t->regexp, t->rewrite));
     CHECK_EQ(one, t->single);
     string all(t->original);
     CHECK_EQ(RE2::GlobalReplace(&all, t->regexp, t->rewrite), t->greplace_count)
       << "Got: " << all;
     CHECK_EQ(all, t->global);
   }
 }
@@ skipping 172 matching lines @@
   CHECK_EQ(group[3], "9000");
 
   string all, host;
   int port;
   CHECK(RE2::PartialMatch("a chrisr:9000 here", re, &all, &host, &port));
   CHECK_EQ(all, "chrisr:9000");
   CHECK_EQ(host, "chrisr");
   CHECK_EQ(port, 9000);
 }
 
-static void TestRecursion(int size, const char *pattern) {
+static void TestRecursion(int size, const char* pattern) {
   // Fill up a string repeating the pattern given
   string domain;
   domain.resize(size);
-  int patlen = strlen(pattern);
-  for (int i = 0; i < size; ++i) {
+  size_t patlen = strlen(pattern);
+  for (int i = 0; i < size; i++) {
     domain[i] = pattern[i % patlen];
   }
   // Just make sure it doesn't crash due to too much recursion.
   RE2 re("([a-zA-Z0-9]|-)+(\\.([a-zA-Z0-9]|-)+)*(\\.)?", RE2::Quiet);
   RE2::FullMatch(domain, re);
 }
 
 // A meta-quoted string, interpreted as a pattern, should always match
 // the original unquoted string.
 static void TestQuoteMeta(string unquoted,
                           const RE2::Options& options = RE2::DefaultOptions) {
   string quoted = RE2::QuoteMeta(unquoted);
   RE2 re(quoted, options);
-  EXPECT_TRUE_M(RE2::FullMatch(unquoted, re),
-                "Unquoted='" + unquoted + "', quoted='" + quoted + "'.");
+  EXPECT_TRUE(RE2::FullMatch(unquoted, re))
+      << "Unquoted='" << unquoted << "', quoted='" << quoted << "'.";
 }
 
 // A meta-quoted string, interpreted as a pattern, should always match
 // the original unquoted string.
 static void NegativeTestQuoteMeta(string unquoted, string should_not_match,
                                   const RE2::Options& options = RE2::DefaultOptions) {
   string quoted = RE2::QuoteMeta(unquoted);
   RE2 re(quoted, options);
-  EXPECT_FALSE_M(RE2::FullMatch(should_not_match, re),
-                 "Unquoted='" + unquoted + "', quoted='" + quoted + "'.");
+  EXPECT_FALSE(RE2::FullMatch(should_not_match, re))
+      << "Unquoted='" << unquoted << "', quoted='" << quoted << "'.";
 }
 
 // Tests that quoted meta characters match their original strings,
 // and that a few things that shouldn't match indeed do not.
 TEST(QuoteMeta, Simple) {
   TestQuoteMeta("foo");
   TestQuoteMeta("foo.bar");
   TestQuoteMeta("foo\\.bar");
   TestQuoteMeta("[1-9]");
   TestQuoteMeta("1.5-2.0?");
@@ skipping 45 matching lines @@
 
   // Don't want null-followed-by-'1' to be interpreted as '\01'.
   has_null += '1';
   TestQuoteMeta(has_null);
   NegativeTestQuoteMeta(has_null, "\1");
 }
 
 TEST(ProgramSize, BigProgram) {
   RE2 re_simple("simple regexp");
   RE2 re_medium("medium.*regexp");
-  RE2 re_complex("hard.{1,128}regexp");
+  RE2 re_complex("complex.{1,128}regexp");
 
   CHECK_GT(re_simple.ProgramSize(), 0);
   CHECK_GT(re_medium.ProgramSize(), re_simple.ProgramSize());
   CHECK_GT(re_complex.ProgramSize(), re_medium.ProgramSize());
 }
 
+TEST(ProgramFanout, BigProgram) {
+  RE2 re1("(?:(?:(?:(?:(?:.)?){1})*)+)");
+  RE2 re10("(?:(?:(?:(?:(?:.)?){10})*)+)");
+  RE2 re100("(?:(?:(?:(?:(?:.)?){100})*)+)");
+  RE2 re1000("(?:(?:(?:(?:(?:.)?){1000})*)+)");
+
+  map<int, int> histogram;
+
+  // 3 is the largest non-empty bucket and has 1 element.
+  CHECK_EQ(3, re1.ProgramFanout(&histogram));
+  CHECK_EQ(1, histogram[3]);
+
+  // 7 is the largest non-empty bucket and has 10 elements.
+  CHECK_EQ(7, re10.ProgramFanout(&histogram));
+  CHECK_EQ(10, histogram[7]);
+
+  // 10 is the largest non-empty bucket and has 100 elements.
+  CHECK_EQ(10, re100.ProgramFanout(&histogram));
+  CHECK_EQ(100, histogram[10]);
+
+  // 13 is the largest non-empty bucket and has 1000 elements.
+  CHECK_EQ(13, re1000.ProgramFanout(&histogram));
+  CHECK_EQ(1000, histogram[13]);
+}
+
 // Issue 956519: handling empty character sets was
 // causing NULL dereference.  This tests a few empty character sets.
 // (The way to get an empty character set is to negate a full one.)
 TEST(EmptyCharset, Fuzz) {
   static const char *empties[] = {
     "[^\\S\\s]",
     "[^\\S[:space:]]",
     "[^\\D\\d]",
     "[^\\D[:digit:]]"
   };
   for (int i = 0; i < arraysize(empties); i++)
     CHECK(!RE2(empties[i]).Match("abc", 0, 3, RE2::UNANCHORED, NULL, 0));
 }
 
+// Bitstate assumes that kInstFail instructions in
+// alternations or capture groups have been "compiled away".
+TEST(EmptyCharset, BitstateAssumptions) {
+  // Captures trigger use of Bitstate.
+  static const char *nop_empties[] = {
+    "((((()))))" "[^\\S\\s]?",
+    "((((()))))" "([^\\S\\s])?",
+    "((((()))))" "([^\\S\\s]|[^\\S\\s])?",
+    "((((()))))" "(([^\\S\\s]|[^\\S\\s])|)"
+  };
+  StringPiece group[6];
+  for (int i = 0; i < arraysize(nop_empties); i++)
+    CHECK(RE2(nop_empties[i]).Match("", 0, 0, RE2::UNANCHORED, group, 6));
+}
+
 // Test that named groups work correctly.
 TEST(Capture, NamedGroups) {
   {
     RE2 re("(hello world)");
     CHECK_EQ(re.NumberOfCapturingGroups(), 1);
     const map<string, int>& m = re.NamedCapturingGroups();
     CHECK_EQ(m.size(), 0);
   }
 
   {
     RE2 re("(?P<A>expr(?P<B>expr)(?P<C>expr))((expr)(?P<D>expr))");
     CHECK_EQ(re.NumberOfCapturingGroups(), 6);
     const map<string, int>& m = re.NamedCapturingGroups();
     CHECK_EQ(m.size(), 4);
     CHECK_EQ(m.find("A")->second, 1);
     CHECK_EQ(m.find("B")->second, 2);
     CHECK_EQ(m.find("C")->second, 3);
     CHECK_EQ(m.find("D")->second, 6);  // $4 and $5 are anonymous
   }
 }
 
+TEST(RE2, CapturedGroupTest) {
+  RE2 re("directions from (?P<S>.*) to (?P<D>.*)");
+  int num_groups = re.NumberOfCapturingGroups();
+  EXPECT_EQ(2, num_groups);
+  string args[4];
+  RE2::Arg arg0(&args[0]);
+  RE2::Arg arg1(&args[1]);
+  RE2::Arg arg2(&args[2]);
+  RE2::Arg arg3(&args[3]);
+
+  const RE2::Arg* const matches[4] = {&arg0, &arg1, &arg2, &arg3};
+  EXPECT_TRUE(RE2::FullMatchN("directions from mountain view to san jose",
+                              re, matches, num_groups));
+  const map<string, int>& named_groups = re.NamedCapturingGroups();
+  EXPECT_TRUE(named_groups.find("S") != named_groups.end());
+  EXPECT_TRUE(named_groups.find("D") != named_groups.end());
+
+  // The named group index is 1-based.
+  int source_group_index = named_groups.find("S")->second;
+  int destination_group_index = named_groups.find("D")->second;
+  EXPECT_EQ(1, source_group_index);
+  EXPECT_EQ(2, destination_group_index);
+
+  // The args is zero-based.
+  EXPECT_EQ("mountain view", args[source_group_index - 1]);
+  EXPECT_EQ("san jose", args[destination_group_index - 1]);
+}
+
 TEST(RE2, FullMatchWithNoArgs) {
   CHECK(RE2::FullMatch("h", "h"));
   CHECK(RE2::FullMatch("hello", "hello"));
   CHECK(RE2::FullMatch("hello", "h.*o"));
   CHECK(!RE2::FullMatch("othello", "h.*o"));       // Must be anchored at front
   CHECK(!RE2::FullMatch("hello!", "h.*o"));        // Must be anchored at end
 }
 
 TEST(RE2, PartialMatch) {
   CHECK(RE2::PartialMatch("x", "x"));
@@ skipping 133 matching lines @@
   CHECK(RE2::FullMatch("123.4567890123456", "(.*)", (float*)NULL));
 
   // Fail on non-void* NULL arg if the match doesn't parse for the given type.
   CHECK(!RE2::FullMatch("hello", "h(.*)lo", &s, (char*)NULL));
   CHECK(!RE2::FullMatch("hello", "(.*)", (int*)NULL));
   CHECK(!RE2::FullMatch("1234567890123456", "(.*)", (int*)NULL));
   CHECK(!RE2::FullMatch("hello", "(.*)", (double*)NULL));
   CHECK(!RE2::FullMatch("hello", "(.*)", (float*)NULL));
 }
 
-#ifndef WIN32
 // Check that numeric parsing code does not read past the end of
 // the number being parsed.
+// This implementation requires mmap(2) et al. and thus cannot
+// be used unless they are available.
 TEST(RE2, NULTerminated) {
+#if defined(_POSIX_MAPPED_FILES) && _POSIX_MAPPED_FILES > 0
   char *v;
   int x;
   long pagesize = sysconf(_SC_PAGE_SIZE);
 
 #ifndef MAP_ANONYMOUS
 #define MAP_ANONYMOUS MAP_ANON
 #endif
   v = static_cast<char*>(mmap(NULL, 2*pagesize, PROT_READ|PROT_WRITE,
                               MAP_ANONYMOUS|MAP_PRIVATE, -1, 0));
   CHECK(v != reinterpret_cast<char*>(-1));
   LOG(INFO) << "Memory at " << (void*)v;
   CHECK_EQ(munmap(v + pagesize, pagesize), 0) << " error " << errno;
   v[pagesize - 1] = '1';
 
   x = 0;
   CHECK(RE2::FullMatch(StringPiece(v + pagesize - 1, 1), "(.*)", &x));
   CHECK_EQ(x, 1);
+#endif
 }
-#endif
 
 TEST(RE2, FullMatchTypeTests) {
   // Type tests
-  string zeros(100, '0');
+  string zeros(1000, '0');
   {
     char c;
     CHECK(RE2::FullMatch("Hello", "(H)ello", &c));
     CHECK_EQ(c, 'H');
   }
   {
     unsigned char c;
     CHECK(RE2::FullMatch("Hello", "(H)ello", &c));
     CHECK_EQ(c, static_cast<unsigned char>('H'));
   }
@@ skipping 81 matching lines @@
     snprintf(buf, sizeof(buf), "%llu", (long long unsigned)max);
     CHECK(RE2::FullMatch(buf,    "(-?\\d+)", &v)); CHECK_EQ(v, max);
 
     assert(buf[strlen(buf)-1] != '9');
     buf[strlen(buf)-1]++;
     CHECK(!RE2::FullMatch(buf,   "(-?\\d+)", &v));
   }
 }
 
 TEST(RE2, FloatingPointFullMatchTypes) {
-  string zeros(100, '0');
+  string zeros(1000, '0');
   {
     float v;
     CHECK(RE2::FullMatch("100",   "(.*)", &v));  CHECK_EQ(v, 100);
     CHECK(RE2::FullMatch("-100.", "(.*)", &v));  CHECK_EQ(v, -100);
     CHECK(RE2::FullMatch("1e23",  "(.*)", &v));  CHECK_EQ(v, float(1e23));
+    CHECK(RE2::FullMatch(" 100",  "(.*)", &v));  CHECK_EQ(v, 100);
 
     CHECK(RE2::FullMatch(zeros + "1e23",  "(.*)", &v));
     CHECK_EQ(v, float(1e23));
 
     // 6700000000081920.1 is an edge case.
     // 6700000000081920 is exactly halfway between
     // two float32s, so the .1 should make it round up.
     // However, the .1 is outside the precision possible with
     // a float64: the nearest float64 is 6700000000081920.
     // So if the code uses strtod and then converts to float32,
@@ skipping 179 matching lines @@
     CHECK(re.error().empty());  // Must have no error
     CHECK(re.ok());
     CHECK(re.error_code() == RE2::NoError);
   }
 }
 
 TEST(RE2, UTF8) {
   // Check UTF-8 handling
   // Three Japanese characters (nihongo)
   const char utf8_string[] = {
-       0xe6, 0x97, 0xa5, // 65e5
-       0xe6, 0x9c, 0xac, // 627c
-       0xe8, 0xaa, 0x9e, // 8a9e
+       (char)0xe6, (char)0x97, (char)0xa5, // 65e5
+       (char)0xe6, (char)0x9c, (char)0xac, // 627c
+       (char)0xe8, (char)0xaa, (char)0x9e, // 8a9e
        0
   };
   const char utf8_pattern[] = {
        '.',
-       0xe6, 0x9c, 0xac, // 627c
+       (char)0xe6, (char)0x9c, (char)0xac, // 627c
        '.',
        0
   };
 
   // Both should match in either mode, bytes or UTF-8
   RE2 re_test1(".........", RE2::Latin1);
   CHECK(RE2::FullMatch(utf8_string, re_test1));
   RE2 re_test2("...");
   CHECK(RE2::FullMatch(utf8_string, re_test2));
 
@@ skipping 228 matching lines @@
     if (t.match == NULL) {
       EXPECT_FALSE(re.PartialMatch(t.text, re));
     } else {
       StringPiece m;
       EXPECT_TRUE(re.PartialMatch(t.text, re, &m));
       EXPECT_EQ(m, t.match);
     }
   }
 }
 
+// Check that dot_nl option works.
+TEST(RE2, DotNL) {
+  RE2::Options opt;
+  opt.set_dot_nl(true);
+  EXPECT_TRUE(RE2::PartialMatch("\n", RE2(".", opt)));
+  EXPECT_FALSE(RE2::PartialMatch("\n", RE2("(?-s).", opt)));
+  opt.set_never_nl(true);
+  EXPECT_FALSE(RE2::PartialMatch("\n", RE2(".", opt)));
+}
+
 // Check that there are no capturing groups in "never capture" mode.
 TEST(RE2, NeverCapture) {
   RE2::Options opt;
   opt.set_never_capture(true);
   RE2 re("(r)(e)", opt);
   EXPECT_EQ(0, re.NumberOfCapturingGroups());
 }
 
 // Bitstate bug was looking at submatch[0] even if nsubmatch == 0.
 // Triggered by a failed DFA search falling back to Bitstate when
@@ skipping 104 matching lines @@
   EXPECT_EQ(want, have);
 }
 
 TEST(RE2, RegexpToStringLossOfAnchor) {
   EXPECT_EQ(RE2("^[a-c]at", RE2::POSIX).Regexp()->ToString(), "^[a-c]at");
   EXPECT_EQ(RE2("^[a-c]at").Regexp()->ToString(), "(?-m:^)[a-c]at");
   EXPECT_EQ(RE2("ca[t-z]$", RE2::POSIX).Regexp()->ToString(), "ca[t-z]$");
   EXPECT_EQ(RE2("ca[t-z]$").Regexp()->ToString(), "ca[t-z](?-m:$)");
 }
 
+// Issue 10131674
+TEST(RE2, Bug10131674) {
+  // Some of these escapes describe values that do not fit in a byte.
+  RE2 re("\\140\\440\\174\\271\\150\\656\\106\\201\\004\\332", RE2::Latin1);
+  EXPECT_FALSE(re.ok());
+  EXPECT_FALSE(RE2::FullMatch("hello world", re));
+}
+
+TEST(RE2, Bug18391750) {
+  // Stray write past end of match_ in nfa.cc, caught by fuzzing + address sanitizer.
+  const char t[] = {
+      (char)0x28, (char)0x28, (char)0xfc, (char)0xfc, (char)0x08, (char)0x08,
+      (char)0x26, (char)0x26, (char)0x28, (char)0xc2, (char)0x9b, (char)0xc5,
+      (char)0xc5, (char)0xd4, (char)0x8f, (char)0x8f, (char)0x69, (char)0x69,
+      (char)0xe7, (char)0x29, (char)0x7b, (char)0x37, (char)0x31, (char)0x31,
+      (char)0x7d, (char)0xae, (char)0x7c, (char)0x7c, (char)0xf3, (char)0x29,
+      (char)0xae, (char)0xae, (char)0x2e, (char)0x2a, (char)0x29, (char)0x00,
+  };
+  RE2::Options opt;
+  opt.set_encoding(RE2::Options::EncodingLatin1);
+  opt.set_longest_match(true);
+  opt.set_dot_nl(true);
+  opt.set_case_sensitive(false);
+  RE2 re(t, opt);
+  CHECK(re.ok());
+  RE2::PartialMatch(t, re);
+}
+
+TEST(RE2, Bug18458852) {
+  // Bug in parser accepting invalid (too large) rune,
+  // causing compiler to fail in DCHECK in UTF-8
+  // character class code.
+  const char b[] = {
+      (char)0x28, (char)0x05, (char)0x05, (char)0x41, (char)0x41, (char)0x28,
+      (char)0x24, (char)0x5b, (char)0x5e, (char)0xf5, (char)0x87, (char)0x87,
+      (char)0x90, (char)0x29, (char)0x5d, (char)0x29, (char)0x29, (char)0x00,
+  };
+  RE2 re(b);
+  CHECK(!re.ok());
+}
+
+TEST(RE2, Bug18523943) {
+  // Bug in bitstate: case kFailInst was merged into the default with LOG(DFATAL).
+
+  RE2::Options opt;
+  const char a[] = {
+      (char)0x29, (char)0x29, (char)0x24, (char)0x00,
+  };
+  const char b[] = {
+      (char)0x28, (char)0x0a, (char)0x2a, (char)0x2a, (char)0x29, (char)0x00,
+  };
+  opt.set_log_errors(false);
+  opt.set_encoding(RE2::Options::EncodingLatin1);
+  opt.set_posix_syntax(true);
+  opt.set_longest_match(true);
+  opt.set_literal(false);
+  opt.set_never_nl(true);
+
+  RE2 re((const char*)b, opt);
+  CHECK(re.ok());
+  string s1;
+  CHECK(!RE2::PartialMatch((const char*)a, re, &s1));
+}
+
+TEST(RE2, Bug21371806) {
+  // Bug in parser accepting Unicode groups in Latin-1 mode,
+  // causing compiler to fail in DCHECK in prog.cc.
+
+  RE2::Options opt;
+  opt.set_encoding(RE2::Options::EncodingLatin1);
+
+  RE2 re("g\\p{Zl}]", opt);
+  CHECK(re.ok());
+}
+
 }  // namespace re2