Upgrade rust/crates/regex to 1.3.9

Test: None
Change-Id: Ic5726cda9566f808b7dd21d8ce9a3045250f8a54
diff --git a/tests/crazy.rs b/tests/crazy.rs
index 8c72273..56f6cad 100644
--- a/tests/crazy.rs
+++ b/tests/crazy.rs
@@ -118,6 +118,18 @@
 matiter!(match_empty9, r"z|()+", "abc", (0, 0), (1, 1), (2, 2), (3, 3));
 matiter!(match_empty10, r"()+|b", "abc", (0, 0), (1, 1), (2, 2), (3, 3));
 matiter!(match_empty11, r"b|()+", "abc", (0, 0), (1, 2), (3, 3));
+matiter!(match_empty12, r"|b", "abc", (0, 0), (1, 1), (2, 2), (3, 3));
+matiter!(match_empty13, r"b|", "abc", (0, 0), (1, 2), (3, 3));
+matiter!(match_empty14, r"|z", "abc", (0, 0), (1, 1), (2, 2), (3, 3));
+matiter!(match_empty15, r"z|", "abc", (0, 0), (1, 1), (2, 2), (3, 3));
+matiter!(match_empty16, r"|", "abc", (0, 0), (1, 1), (2, 2), (3, 3));
+matiter!(match_empty17, r"||", "abc", (0, 0), (1, 1), (2, 2), (3, 3));
+matiter!(match_empty18, r"||z", "abc", (0, 0), (1, 1), (2, 2), (3, 3));
+matiter!(match_empty19, r"(?:)|b", "abc", (0, 0), (1, 1), (2, 2), (3, 3));
+matiter!(match_empty20, r"b|(?:)", "abc", (0, 0), (1, 2), (3, 3));
+matiter!(match_empty21, r"(?:|)", "abc", (0, 0), (1, 1), (2, 2), (3, 3));
+matiter!(match_empty22, r"(?:|)|z", "abc", (0, 0), (1, 1), (2, 2), (3, 3));
+matiter!(match_empty23, r"a(?:)|b", "abc", (0, 1), (1, 2));
 
 // Test that the DFA can handle pathological cases.
 // (This should result in the DFA's cache being flushed too frequently, which
diff --git a/tests/noparse.rs b/tests/noparse.rs
index 62eb5be..8ded1dc 100644
--- a/tests/noparse.rs
+++ b/tests/noparse.rs
@@ -26,6 +26,8 @@
 noparse!(fail_bad_flag, "(?a)a");
 noparse!(fail_too_big, "a{10000000}");
 noparse!(fail_counted_no_close, "a{1001");
+noparse!(fail_counted_decreasing, "a{2,1}");
+noparse!(fail_counted_nonnegative, "a{-1,1}");
 noparse!(fail_unfinished_cap, "(?");
 noparse!(fail_unfinished_escape, "\\");
 noparse!(fail_octal_digit, r"\8");
@@ -41,10 +43,3 @@
 noparse!(fail_range_end_no_begin, r"[a-\A]");
 noparse!(fail_range_end_no_end, r"[a-\z]");
 noparse!(fail_range_end_no_boundary, r"[a-\b]");
-noparse!(fail_empty_alt1, r"|z");
-noparse!(fail_empty_alt2, r"z|");
-noparse!(fail_empty_alt3, r"|");
-noparse!(fail_empty_alt4, r"||");
-noparse!(fail_empty_alt5, r"()|z");
-noparse!(fail_empty_alt6, r"z|()");
-noparse!(fail_empty_alt7, r"(|)");
diff --git a/tests/regression.rs b/tests/regression.rs
index 686fe35..44b9083 100644
--- a/tests/regression.rs
+++ b/tests/regression.rs
@@ -210,3 +210,10 @@
     (4, 7),
     (12, 15)
 );
+
+// See: https://github.com/rust-lang/regex/issues/659
+//
+// Note that 'Ј' is not 'j', but cyrillic Je
+// https://en.wikipedia.org/wiki/Je_(Cyrillic)
+ismatch!(empty_group_match, r"()Ј01", "zЈ01", true);
+matiter!(empty_group_find, r"()Ј01", "zЈ01", (1, 5));
diff --git a/tests/set.rs b/tests/set.rs
index 3e9755c..648feec 100644
--- a/tests/set.rs
+++ b/tests/set.rs
@@ -17,6 +17,17 @@
 matset!(set17, &[".*a"], "a", 0);
 matset!(set18, &["a", "β"], "β", 1);
 
+// regexes that match the empty string
+matset!(setempty1, &["", "a"], "abc", 0, 1);
+matset!(setempty2, &["", "b"], "abc", 0, 1);
+matset!(setempty3, &["", "z"], "abc", 0);
+matset!(setempty4, &["a", ""], "abc", 0, 1);
+matset!(setempty5, &["b", ""], "abc", 0, 1);
+matset!(setempty6, &["z", ""], "abc", 1);
+matset!(setempty7, &["b", "(?:)"], "abc", 0, 1);
+matset!(setempty8, &["(?:)", "b"], "abc", 0, 1);
+matset!(setempty9, &["c(?:)", "b"], "abc", 0, 1);
+
 nomatset!(nset1, &["a", "a"], "b");
 nomatset!(nset2, &["^foo", "bar$"], "bar foo");
 nomatset!(