Imported Upstream version 20170401upstream/20170401

Change-Id: I86e4396e08989c845f6f561ed918d9866b55ecb8
Signed-off-by: DongHun Kwak <dh0128.kwak@samsung.com>

6 files changed, 71 insertions, 8 deletions

diff --git a/CMakeLists.txt b/CMakeLists.txt
index 0afdbc7..23e3a2b 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -39,7 +39,7 @@ if(USEPCRE)
   list(APPEND EXTRA_TARGET_LINK_LIBRARIES pcre)
 endif()
 
-include_directories(${CMAKE_SOURCE_DIR})
+include_directories(${CMAKE_CURRENT_SOURCE_DIR})
 
 set(RE2_SOURCES
     re2/bitstate.cc
diff --git a/kokoro/macos-cmake.cfg b/kokoro/macos-cmake.cfg
new file mode 100644
index 0000000..5c459e7
--- /dev/null
+++ b/kokoro/macos-cmake.cfg
@@ -0,0 +1 @@
+build_file: "re2/kokoro/macos-cmake.sh"
diff --git a/kokoro/macos-cmake.sh b/kokoro/macos-cmake.sh
new file mode 100755
index 0000000..dbe94cb
--- /dev/null
+++ b/kokoro/macos-cmake.sh
@@ -0,0 +1,14 @@
+#!/bin/bash
+set -eux
+
+cd git/re2
+
+cmake -D CMAKE_BUILD_TYPE=Debug .
+cmake --build . --config Debug --clean-first
+ctest -C Debug --output-on-failure -E dfa\|exhaustive\|random
+
+cmake -D CMAKE_BUILD_TYPE=Release .
+cmake --build . --config Release --clean-first
+ctest -C Release --output-on-failure -E dfa\|exhaustive\|random
+
+exit 0
diff --git a/re2/prog.cc b/re2/prog.cc
index 0eb1fa9..8dc90f8 100644
--- a/re2/prog.cc
+++ b/re2/prog.cc
@@ -543,10 +543,9 @@ void Prog::ComputeByteMap() {
 // "leaves"), only Alt instructions require their predecessors to be computed.
 //
 // Dividing the Prog into "trees" comprises two passes: marking the "successor
-// roots" and the predecessors; and marking the "dominator roots". Walking the
-// Prog in its entirety causes the "successor roots" to be marked in a certain
-// order during the first pass. Iteration over the "successor roots" occurs in
-// reverse order of their marking during the second pass; by working backwards
+// roots" and the predecessors; and marking the "dominator roots". Sorting the
+// "successor roots" by their bytecode offsets enables iteration in order from
+// greatest to least during the second pass; by working backwards in this case
 // and flooding the graph no further than "leaves" and already marked "roots",
 // it becomes possible to mark "dominator roots" without doing excessive work.
 //
@@ -576,10 +575,13 @@ void Prog::Flatten() {
   MarkSuccessors(&rootmap, &predmap, &predvec, &reachable, &stk);
 
   // Second pass: Marks "dominator roots".
-  for (SparseArray<int>::const_iterator i = rootmap.end() - 1;
-       i != rootmap.begin();
+  SparseArray<int> sorted(rootmap);
+  std::sort(sorted.begin(), sorted.end(), sorted.less);
+  for (SparseArray<int>::const_iterator i = sorted.end() - 1;
+       i != sorted.begin();
        --i) {
-    MarkDominator(i->index(), &rootmap, &predmap, &predvec, &reachable, &stk);
+    if (i->index() != start_unanchored() && i->index() != start())
+      MarkDominator(i->index(), &rootmap, &predmap, &predvec, &reachable, &stk);
   }
 
   // Third pass: Emits "lists". Remaps outs to root-ids.
diff --git a/re2/re2.h b/re2/re2.h
index 49559d5..120a34c 100644
--- a/re2/re2.h
+++ b/re2/re2.h
@@ -878,6 +878,14 @@ MAKE_INTEGER_PARSER(unsigned long long, ulonglong)
 #undef MAKE_INTEGER_PARSER
 
 #ifndef SWIG
+
+// Silence warnings about missing initializers for members of LazyRE2.
+// Note that we test for Clang first because it defines __GNUC__ as well.
+#if defined(__clang__)
+#elif defined(__GNUC__) && __GNUC__ >= 6
+#pragma GCC diagnostic ignored "-Wmissing-field-initializers"
+#endif
+
 // Helper for writing global or static RE2s safely.
 // Write
 //     static LazyRE2 re = {".*"};
diff --git a/re2/testing/compile_test.cc b/re2/testing/compile_test.cc
index 87171d6..99c6dba 100644
--- a/re2/testing/compile_test.cc
+++ b/re2/testing/compile_test.cc
@@ -354,6 +354,44 @@ TEST(TestCompile, Bug35237384) {
             "22+ nop -> 12\n"
             "23. nop -> 18\n",
       forward);
+
+  Dump("((|S.+)+|(|S.+)+|){2}", Regexp::Latin1|Regexp::NeverCapture, &forward, NULL);
+  EXPECT_EQ("3+ nop -> 36\n"
+            "4+ nop -> 31\n"
+            "5. nop -> 33\n"
+            "6+ byte [00-09] -> 8\n"
+            "7. byte [0b-ff] -> 8\n"
+            "8+ nop -> 6\n"
+            "9+ nop -> 29\n"
+            "10. nop -> 28\n"
+            "11+ byte [00-09] -> 13\n"
+            "12. byte [0b-ff] -> 13\n"
+            "13+ nop -> 11\n"
+            "14+ nop -> 26\n"
+            "15. nop -> 28\n"
+            "16+ byte [00-09] -> 18\n"
+            "17. byte [0b-ff] -> 18\n"
+            "18+ nop -> 16\n"
+            "19+ nop -> 36\n"
+            "20. nop -> 33\n"
+            "21+ byte [00-09] -> 23\n"
+            "22. byte [0b-ff] -> 23\n"
+            "23+ nop -> 21\n"
+            "24+ nop -> 31\n"
+            "25. nop -> 33\n"
+            "26+ nop -> 28\n"
+            "27. byte [53-53] -> 11\n"
+            "28. match! 0\n"
+            "29+ nop -> 28\n"
+            "30. byte [53-53] -> 6\n"
+            "31+ nop -> 33\n"
+            "32. byte [53-53] -> 21\n"
+            "33+ nop -> 29\n"
+            "34+ nop -> 26\n"
+            "35. nop -> 28\n"
+            "36+ nop -> 33\n"
+            "37. byte [53-53] -> 16\n",
+      forward);
 }
 
 }  // namespace re2