Dir.glob with FNM_EXTGLOB is optimized [Feature #13873]

The order of resulted array is changed in some cases.

git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@60341 b2dd03c8-39d4-4d8f-98ff-823fe69b080e

5 files changed, 90 insertions, 13 deletions

diff --git a/NEWS b/NEWS
index 43a053b521..d9730e0839 100644
--- a/NEWS
+++ b/NEWS
@@ -31,6 +31,8 @@ with all sufficient information, see the ChangeLog file or Redmine
 
   * Dir.glob provides new optional keyword argument, :base.
     [Feature #13056]
+  * Dir.glob with FNM_EXTGLOB is optimized [Feature #13873]
+    The order of resulted array is changed in some cases.
   * Dir.children  [Feature #11302]
   * Dir.each_child  [Feature #11302]
 
diff --git a/dir.c b/dir.c
index 44d309195c..7bc51eb0c7 100644
--- a/dir.c
+++ b/dir.c
@@ -291,6 +291,8 @@ bracket(
 #define UNESCAPE(p) (escape && *(p) == '\\' ? (p) + 1 : (p))
 #define ISEND(p) (!*(p) || (pathname && *(p) == '/'))
 #define RETURN(val) return *pcur = p, *scur = s, (val);
+#define FNMATCH_ALLOC_N(type, n) ((type *)malloc(sizeof(type) * (n)))
+#define FNMATCH_FREE(ptr) free(ptr)
 
 static int
 fnmatch_helper(
@@ -314,8 +316,11 @@ fnmatch_helper(
 
     int r;
 
-    if (period && *s == '.' && *UNESCAPE(p) != '.') /* leading period */
-	RETURN(FNM_NOMATCH);
+    if (period && *s == '.') { /* leading period */
+	int c = *UNESCAPE(p);
+	if (c != '.' && (!(flags & FNM_EXTGLOB) || c != '{')) RETURN(FNM_NOMATCH);
+    }
+
 
     while (1) {
 	switch (*p) {
@@ -349,6 +354,56 @@ fnmatch_helper(
 	    }
 	    goto failed;
 	  }
+
+	  case '{': if (flags & FNM_EXTGLOB) {
+			size_t len = pend - p;
+			char *buf = FNMATCH_ALLOC_N(char, len);
+			const char *rbrace = NULL;
+			while (p < pend) {
+			    const char *t = ++p;
+			    int nest = 0;
+			    while (p < pend && !(*p == ',' && nest == 0)) {
+				if (*p == '{') nest++;
+				if (*p == '}') {
+				    if (nest == 0) {
+					if (!rbrace) rbrace = p;
+					goto rest;
+				    }
+				    nest--;
+				}
+				if (*p == '\\' && escape) {
+				    if (++p >= pend) break;
+				}
+				Inc(p, pend, enc);
+			    }
+			    if (!rbrace) {
+				rbrace = p;
+				while (rbrace < pend && !(*rbrace == '}' && nest == 0)) {
+				    if (*rbrace == '{') nest++;
+				    if (*rbrace == '}') nest--;
+				    if (*rbrace == '\\' && escape) {
+					if (++p >= pend) break;
+				    }
+				    Inc(rbrace, pend, enc);
+				}
+			    }
+rest:
+			    memcpy(buf, t, p-t);
+			    buf[p-t]=0;
+			    strlcpy(buf+(p-t), rbrace+1, len-(p-t));
+			    {
+				const char *pp = buf, *ss = s;
+				r = fnmatch_helper((const char **)&pp, &ss, flags|FNM_DOTMATCH, enc);
+			    }
+			    if (r == 0) {
+				p = buf;
+				FNMATCH_FREE(buf);
+				RETURN(0);
+			    }
+			    if (p >= rbrace) break;
+			}
+			FNMATCH_FREE(buf);
+		    }
 	}
 
 	/* ordinary */
@@ -1429,6 +1484,12 @@ has_magic(const char *p, const char *pend, int flags, rb_encoding *enc)
 	  case '[':
 	    return MAGICAL;
 
+	  case '{':
+	    if (flags & FNM_EXTGLOB) {
+		return MAGICAL;
+	    }
+	    break;
+
 	  case '\\':
 	    if (escape && p++ >= pend)
 		continue;
@@ -2275,6 +2336,13 @@ push_pattern(const char *path, VALUE ary, void *enc)
     rb_ary_push(ary, name);
 }
 
+struct push_glob_args {
+    struct glob_args glob;
+    int flags;
+    int fd;
+};
+static int push_caller(const char *path, VALUE val, void *enc);
+
 static int
 ruby_brace_expand(const char *str, int flags, ruby_glob_func *func, VALUE arg,
 		  rb_encoding *enc, VALUE var)
@@ -2283,7 +2351,7 @@ ruby_brace_expand(const char *str, int flags, ruby_glob_func *func, VALUE arg,
     const char *p = str;
     const char *pend = p + strlen(p);
     const char *s = p;
-    const char *lbrace = 0, *rbrace = 0;
+    const char *lbrace = NULL, *rbrace = NULL;
     int nest = 0, status = 0;
 
     while (*p) {
@@ -2302,9 +2370,18 @@ ruby_brace_expand(const char *str, int flags, ruby_glob_func *func, VALUE arg,
 
     if (lbrace && rbrace) {
 	size_t len = strlen(s) + 1;
-	char *buf = GLOB_ALLOC_N(char, len);
+	char *buf;
 	long shift;
 
+	if (func == push_caller && !strchr(lbrace, '/')) {
+	    /* Now it reaches file basename entry. */
+	    /* Handle braces in glob_helper */
+	    struct push_glob_args *a = (struct push_glob_args *)arg;
+	    a->flags |= FNM_EXTGLOB;
+	    return glob_call_func(func, s, arg, enc);
+	}
+
+	buf = GLOB_ALLOC_N(char, len);
 	if (!buf) return -1;
 	memcpy(buf, s, lbrace-s);
 	shift = (lbrace-s);
@@ -2368,12 +2445,6 @@ ruby_brace_glob(const char *str, int flags, ruby_glob_func *func, VALUE arg)
     return ruby_brace_glob_with_enc(str, flags, func, arg, rb_ascii8bit_encoding());
 }
 
-struct push_glob_args {
-    struct glob_args glob;
-    int flags;
-    int fd;
-};
-
 static int
 push_caller(const char *path, VALUE val, void *enc)
 {
diff --git a/spec/ruby/core/dir/shared/glob.rb b/spec/ruby/core/dir/shared/glob.rb
index d2201cd6cd..11ace13326 100644
--- a/spec/ruby/core/dir/shared/glob.rb
+++ b/spec/ruby/core/dir/shared/glob.rb
@@ -221,12 +221,12 @@ describe :dir_glob, shared: true do
 
   it "respects the order of {} expressions, expanding left most first" do
     files = Dir.send(@method, "brace/a{.js,.html}{.erb,.rjs}")
-    files.should == %w!brace/a.js.rjs brace/a.html.erb!
+    files.sort.should == %w!brace/a.html.erb brace/a.js.rjs!
   end
 
   it "respects the optional nested {} expressions" do
     files = Dir.send(@method, "brace/a{.{js,html},}{.{erb,rjs},}")
-    files.should == %w!brace/a.js.rjs brace/a.js brace/a.html.erb brace/a.erb brace/a!
+    files.sort.should == %w!brace/a brace/a.erb brace/a.html.erb brace/a.js brace/a.js.rjs!
   end
 
   it "matches special characters by escaping with a backslash with '\\<character>'" do
diff --git a/test/ruby/test_dir.rb b/test/ruby/test_dir.rb
index cead4beb93..f12fd13c58 100644
--- a/test/ruby/test_dir.rb
+++ b/test/ruby/test_dir.rb
@@ -155,7 +155,7 @@ class TestDir < Test::Unit::TestCase
     open(File.join(@root, "}}{}"), "wb") {}
     open(File.join(@root, "}}a"), "wb") {}
     assert_equal(%w(}}{} }}a).map {|f| File.join(@root, f)}, Dir.glob(File.join(@root, '}}{\{\},a}')))
-    assert_equal(%w(}}{} }}a b c).map {|f| File.join(@root, f)}, Dir.glob(File.join(@root, '{\}\}{\{\},a},b,c}')))
+    assert_equal(%w(}}{} }}a b c).map {|f| File.join(@root, f)}.sort, Dir.glob(File.join(@root, '{\}\}{\{\},a},b,c}')).sort)
   end
 
   def test_glob_recursive
diff --git a/test/ruby/test_fnmatch.rb b/test/ruby/test_fnmatch.rb
index ca01a28698..2fb8796ab3 100644
--- a/test/ruby/test_fnmatch.rb
+++ b/test/ruby/test_fnmatch.rb
@@ -108,6 +108,10 @@ class TestFnmatch < Test::Unit::TestCase
     feature5422 = '[ruby-core:40037]'
     assert_file.for(feature5422).not_fnmatch?( "{.g,t}*", ".gem")
     assert_file.for(feature5422).fnmatch?("{.g,t}*", ".gem", File::FNM_EXTGLOB)
+
+    assert_file.fnmatch?("{,.}*", ".gem", File::FNM_EXTGLOB)
+    assert_file.not_fnmatch?("{}*", ".gem", File::FNM_EXTGLOB)
+    assert_file.not_fnmatch?("{.}*", ".gem")
   end
 
   def test_unmatched_encoding