require-performance-fix.patch - fixed for requires with multiple dots

require-performance-fix.patch

diff --git a/.gitignore b/.gitignore
index 57557c9..7955376 100644
--- a/.gitignore
+++ b/.gitignore
@@ -129,3 +129,4 @@ y.tab.c
 
 # /win32/
 /win32/*.ico
+ext/win32ole/.document
diff --git a/array.c b/array.c
index 9664626..9a1cb85 100644
--- a/array.c
+++ b/array.c
@@ -305,7 +305,7 @@ ary_alloc(VALUE klass)
     return (VALUE)ary;
 }
 
-static VALUE
+VALUE
 ary_new(VALUE klass, long capa)
 {
     VALUE ary;
diff --git a/enc/make_encmake.rb b/enc/make_encmake.rb
index ed36803..8784cb4 100755
--- a/enc/make_encmake.rb
+++ b/enc/make_encmake.rb
@@ -3,10 +3,8 @@
 dir = File.expand_path("../..", __FILE__)
 $:.unshift(dir)
 $:.unshift(".")
-if $".grep(/mkmf/).empty?
-  $" << "mkmf.rb"
-  load File.expand_path("lib/mkmf.rb", dir)
-end
+$:.unshift(dir + '/lib')
+require 'mkmf'
 require 'erb'
 
 CONFIG["MAKEDIRS"] ||= '$(MINIRUBY) -run -e mkdir -- -p'
diff --git a/enumerator.c b/enumerator.c
index 7bb5ecd..b8ce698 100644
--- a/enumerator.c
+++ b/enumerator.c
@@ -1171,6 +1171,4 @@ Init_Enumerator(void)
     id_rewind = rb_intern("rewind");
     id_each = rb_intern("each");
     sym_each = ID2SYM(id_each);
-
-    rb_provide("enumerator.so");	/* for backward compatibility */
 }
diff --git a/ext/extmk.rb b/ext/extmk.rb
index 3aa8154..846c8fa 100755
--- a/ext/extmk.rb
+++ b/ext/extmk.rb
@@ -36,8 +36,8 @@ require 'rbconfig'
 $topdir = "."
 $top_srcdir = srcdir
 
-$" << "mkmf.rb"
-load File.expand_path("lib/mkmf.rb", srcdir)
+$:.unshift(srcdir + '/lib')
+require 'mkmf'
 require 'optparse/shellwords'
 
 def sysquote(x)
diff --git a/file.c b/file.c
index 3746009..65a71b8 100644
--- a/file.c
+++ b/file.c
@@ -1270,7 +1270,7 @@ rb_file_chardev_p(VALUE obj, VALUE fname)
  * Return <code>true</code> if the named file exists.
  */
 
-static VALUE
+VALUE
 rb_file_exist_p(VALUE obj, VALUE fname)
 {
     struct stat st;
diff --git a/lib/enumerator.rb b/lib/enumerator.rb
new file mode 100644
index 0000000..b028c83
--- /dev/null
+++ b/lib/enumerator.rb
@@ -0,0 +1,3 @@
+# This class is now defined entirely in enumerator.c and is always available.
+# This file needs to remain here for backwards compatibility, so that `require
+# "enumerator"` will not raise an exception.
diff --git a/load.c b/load.c
index 547c115..3b43343 100644
--- a/load.c
+++ b/load.c
@@ -18,14 +18,73 @@ VALUE ruby_dln_librefs;
 #endif
 
 
-static const char *const loadable_ext[] = {
-    ".rb", DLEXT,
+VALUE rb_f_require(VALUE, VALUE);
+VALUE rb_f_require_relative(VALUE, VALUE);
+static VALUE rb_f_load(int, VALUE *);
+VALUE rb_require_safe(VALUE, int);
+
+static int rb_file_has_been_required(VALUE);
+static int rb_file_is_being_required(VALUE);
+static int rb_file_is_ruby(VALUE);
+static st_table * get_loaded_features_hash(void);
+static void rb_load_internal(VALUE, int);
+static char * load_lock(const char *);
+static void load_unlock(const char *, int);
+static void load_failed(VALUE fname);
+
+void rb_provide(const char *feature);
+static void rb_provide_feature(VALUE);
+
+/* 
+ * These functions are all conceptually related, and could be extracted
+ * into a separate file.
+ */
+static VALUE rb_locate_file(VALUE);
+static VALUE rb_locate_file_absolute(VALUE);
+static VALUE rb_locate_file_relative(VALUE);
+static VALUE rb_locate_file_in_load_path(VALUE);
+static VALUE rb_locate_file_with_extensions(VALUE, VALUE);
+static int rb_path_is_absolute(VALUE);
+static int rb_path_is_relative(VALUE);
+VALUE rb_get_expanded_load_path();
+
+/* 
+ * These functions are all conceptually related, and could be extracted
+ * into a separate file.
+ */
+static VALUE rb_cLoadedFeaturesProxy;
+static void rb_rehash_loaded_features();
+static VALUE rb_loaded_features_hook(int, VALUE*, VALUE);
+static void define_loaded_features_proxy();
+
+VALUE ary_new(VALUE, long);          // array.c
+VALUE rb_file_exist_p(VALUE, VALUE); // file.c
+
+const char *available_extensions[] = {
+  ".rb",
+  DLEXT,
+#ifdef DLEXT2
+  DLEXT2,
+#endif
+  ""
+};
+
+#ifdef DLEXT2
+VALUE available_ext_rb_str[4];
+#else
+VALUE available_ext_rb_str[3];
+#endif
+
+const char *alternate_dl_extensions[] = {
+  DLEXT,
 #ifdef DLEXT2
-    DLEXT2,
+  DLEXT2
 #endif
-    0
 };
 
+#define CHAR_ARRAY_LEN(array) sizeof(array) / sizeof(char*)
+#define VALUE_ARRAY_LEN(array) sizeof(array) / sizeof(VALUE)
+
 VALUE
 rb_get_load_path(void)
 {
@@ -33,6 +92,32 @@ rb_get_load_path(void)
     return load_path;
 }
 
+static st_table *
+get_loaded_features_hash(void)
+{
+    st_table* loaded_features_hash;
+    loaded_features_hash = GET_VM()->loaded_features_hash;
+
+    if (!loaded_features_hash) {
+      GET_VM()->loaded_features_hash = loaded_features_hash = st_init_strcasetable();
+    }
+
+    return loaded_features_hash;
+}
+
+static st_table *
+get_filename_expansion_hash(void)
+{
+    st_table* filename_expansion_hash;
+    filename_expansion_hash = GET_VM()->filename_expansion_hash;
+
+    if (!filename_expansion_hash) {
+      GET_VM()->filename_expansion_hash = filename_expansion_hash = st_init_strcasetable();
+    }
+
+    return filename_expansion_hash;
+}
+
 VALUE
 rb_get_expanded_load_path(void)
 {
@@ -68,185 +153,32 @@ get_loading_table(void)
     return GET_VM()->loading_table;
 }
 
-static VALUE
-loaded_feature_path(const char *name, long vlen, const char *feature, long len,
-		    int type, VALUE load_path)
-{
-    long i;
-
-    for (i = 0; i < RARRAY_LEN(load_path); ++i) {
-	VALUE p = RARRAY_PTR(load_path)[i];
-	const char *s = StringValuePtr(p);
-	long n = RSTRING_LEN(p);
-
-	if (vlen < n + len + 1) continue;
-	if (n && (strncmp(name, s, n) || name[n] != '/')) continue;
-	if (strncmp(name + n + 1, feature, len)) continue;
-	if (name[n+len+1] && name[n+len+1] != '.') continue;
-	switch (type) {
-	  case 's':
-	    if (IS_DLEXT(&name[n+len+1])) return p;
-	    break;
-	  case 'r':
-	    if (IS_RBEXT(&name[n+len+1])) return p;
-	    break;
-	  default:
-	    return p;
-	}
-    }
-    return 0;
-}
-
-struct loaded_feature_searching {
-    const char *name;
-    long len;
-    int type;
-    VALUE load_path;
-    const char *result;
-};
-
-static int
-loaded_feature_path_i(st_data_t v, st_data_t b, st_data_t f)
-{
-    const char *s = (const char *)v;
-    struct loaded_feature_searching *fp = (struct loaded_feature_searching *)f;
-    VALUE p = loaded_feature_path(s, strlen(s), fp->name, fp->len,
-				  fp->type, fp->load_path);
-    if (!p) return ST_CONTINUE;
-    fp->result = s;
-    return ST_STOP;
-}
-
-static int
-rb_feature_p(const char *feature, const char *ext, int rb, int expanded, const char **fn)
-{
-    VALUE v, features, p, load_path = 0;
-    const char *f, *e;
-    long i, len, elen, n;
-    st_table *loading_tbl;
-    st_data_t data;
-    int type;
-
-    if (fn) *fn = 0;
-    if (ext) {
-	elen = strlen(ext);
-	len = strlen(feature) - elen;
-	type = rb ? 'r' : 's';
-    }
-    else {
-	len = strlen(feature);
-	elen = 0;
-	type = 0;
-    }
-    features = get_loaded_features();
-    for (i = 0; i < RARRAY_LEN(features); ++i) {
-	v = RARRAY_PTR(features)[i];
-	f = StringValuePtr(v);
-	if ((n = RSTRING_LEN(v)) < len) continue;
-	if (strncmp(f, feature, len) != 0) {
-	    if (expanded) continue;
-	    if (!load_path) load_path = rb_get_expanded_load_path();
-	    if (!(p = loaded_feature_path(f, n, feature, len, type, load_path)))
-		continue;
-	    expanded = 1;
-	    f += RSTRING_LEN(p) + 1;
-	}
-	if (!*(e = f + len)) {
-	    if (ext) continue;
-	    return 'u';
-	}
-	if (*e != '.') continue;
-	if ((!rb || !ext) && (IS_SOEXT(e) || IS_DLEXT(e))) {
-	    return 's';
-	}
-	if ((rb || !ext) && (IS_RBEXT(e))) {
-	    return 'r';
-	}
-    }
-    loading_tbl = get_loading_table();
-    if (loading_tbl) {
-	f = 0;
-	if (!expanded) {
-	    struct loaded_feature_searching fs;
-	    fs.name = feature;
-	    fs.len = len;
-	    fs.type = type;
-	    fs.load_path = load_path ? load_path : rb_get_load_path();
-	    fs.result = 0;
-	    st_foreach(loading_tbl, loaded_feature_path_i, (st_data_t)&fs);
-	    if ((f = fs.result) != 0) {
-		if (fn) *fn = f;
-		goto loading;
-	    }
-	}
-	if (st_get_key(loading_tbl, (st_data_t)feature, &data)) {
-	    if (fn) *fn = (const char*)data;
-	  loading:
-	    if (!ext) return 'u';
-	    return !IS_RBEXT(ext) ? 's' : 'r';
-	}
-	else {
-	    VALUE bufstr;
-	    char *buf;
-
-	    if (ext && *ext) return 0;
-	    bufstr = rb_str_tmp_new(len + DLEXT_MAXLEN);
-	    buf = RSTRING_PTR(bufstr);
-	    MEMCPY(buf, feature, char, len);
-	    for (i = 0; (e = loadable_ext[i]) != 0; i++) {
-		strlcpy(buf + len, e, DLEXT_MAXLEN + 1);
-		if (st_get_key(loading_tbl, (st_data_t)buf, &data)) {
-		    rb_str_resize(bufstr, 0);
-		    if (fn) *fn = (const char*)data;
-		    return i ? 's' : 'r';
-		}
-	    }
-	    rb_str_resize(bufstr, 0);
-	}
-    }
-    return 0;
-}
-
 int
 rb_provided(const char *feature)
 {
     return rb_feature_provided(feature, 0);
 }
 
-int
-rb_feature_provided(const char *feature, const char **loading)
+
+/* Mark the given feature as loaded, after it has been evaluated. */
+	static void
+rb_provide_feature(VALUE feature)
 {
-    const char *ext = strrchr(feature, '.');
-    volatile VALUE fullpath = 0;
+	int frozen = 0;
+	st_table* loaded_features_hash;
 
-    if (*feature == '.' &&
-	(feature[1] == '/' || strncmp(feature+1, "./", 2) == 0)) {
-	fullpath = rb_file_expand_path(rb_str_new2(feature), Qnil);
-	feature = RSTRING_PTR(fullpath);
-    }
-    if (ext && !strchr(ext, '/')) {
-	if (IS_RBEXT(ext)) {
-	    if (rb_feature_p(feature, ext, TRUE, FALSE, loading)) return TRUE;
-	    return FALSE;
-	}
-	else if (IS_SOEXT(ext) || IS_DLEXT(ext)) {
-	    if (rb_feature_p(feature, ext, FALSE, FALSE, loading)) return TRUE;
-	    return FALSE;
+	if (OBJ_FROZEN(get_loaded_features())) {
+		rb_raise(rb_eRuntimeError,
+				"$LOADED_FEATURES is frozen; cannot append feature");
 	}
-    }
-    if (rb_feature_p(feature, 0, TRUE, FALSE, loading))
-	return TRUE;
-    return FALSE;
-}
 
-static void
-rb_provide_feature(VALUE feature)
-{
-    if (OBJ_FROZEN(get_loaded_features())) {
-	rb_raise(rb_eRuntimeError,
-		 "$LOADED_FEATURES is frozen; cannot append feature");
-    }
-    rb_ary_push(get_loaded_features(), feature);
+	loaded_features_hash = get_loaded_features_hash();
+	st_insert(
+			loaded_features_hash,
+			(st_data_t)ruby_strdup(RSTRING_PTR(feature)),
+			(st_data_t)rb_barrier_new());
+
+	rb_ary_push(get_loaded_features(), feature);
 }
 
 void
@@ -418,34 +350,6 @@ load_unlock(const char *ftptr, int done)
 
 
 /*
- *  call-seq:
- *     require(string)    -> true or false
- *
- *  Ruby tries to load the library named _string_, returning
- *  +true+ if successful. If the filename does not resolve to
- *  an absolute path, it will be searched for in the directories listed
- *  in <code>$:</code>. If the file has the extension ``.rb'', it is
- *  loaded as a source file; if the extension is ``.so'', ``.o'', or
- *  ``.dll'', or whatever the default shared library extension is on
- *  the current platform, Ruby loads the shared library as a Ruby
- *  extension. Otherwise, Ruby tries adding ``.rb'', ``.so'', and so on
- *  to the name. The name of the loaded feature is added to the array in
- *  <code>$"</code>. A feature will not be loaded if its name already
- *  appears in <code>$"</code>. The file name is converted to an absolute
- *  path, so ``<code>require 'a'; require './a'</code>'' will not load
- *  <code>a.rb</code> twice.
- *
- *     require "my-library.rb"
- *     require "db-driver"
- */
-
-VALUE
-rb_f_require(VALUE obj, VALUE fname)
-{
-    return rb_require_safe(fname, rb_safe_level());
-}
-
-/*
  * call-seq:
  *   require_relative(string) -> true or false
  *
@@ -465,92 +369,6 @@ rb_f_require_relative(VALUE obj, VALUE fname)
     return rb_require_safe(rb_file_absolute_path(fname, base), rb_safe_level());
 }
 
-static int
-search_required(VALUE fname, volatile VALUE *path, int safe_level)
-{
-    VALUE tmp;
-    char *ext, *ftptr;
-    int type, ft = 0;
-    const char *loading;
-
-    *path = 0;
-    ext = strrchr(ftptr = RSTRING_PTR(fname), '.');
-    if (ext && !strchr(ext, '/')) {
-	if (IS_RBEXT(ext)) {
-	    if (rb_feature_p(ftptr, ext, TRUE, FALSE, &loading)) {
-		if (loading) *path = rb_str_new2(loading);
-		return 'r';
-	    }
-	    if ((tmp = rb_find_file_safe(fname, safe_level)) != 0) {
-		ext = strrchr(ftptr = RSTRING_PTR(tmp), '.');
-		if (!rb_feature_p(ftptr, ext, TRUE, TRUE, &loading) || loading)
-		    *path = tmp;
-		return 'r';
-	    }
-	    return 0;
-	}
-	else if (IS_SOEXT(ext)) {
-	    if (rb_feature_p(ftptr, ext, FALSE, FALSE, &loading)) {
-		if (loading) *path = rb_str_new2(loading);
-		return 's';
-	    }
-	    tmp = rb_str_new(RSTRING_PTR(fname), ext - RSTRING_PTR(fname));
-#ifdef DLEXT2
-	    OBJ_FREEZE(tmp);
-	    if (rb_find_file_ext_safe(&tmp, loadable_ext + 1, safe_level)) {
-		ext = strrchr(ftptr = RSTRING_PTR(tmp), '.');
-		if (!rb_feature_p(ftptr, ext, FALSE, TRUE, &loading) || loading)
-		    *path = tmp;
-		return 's';
-	    }
-#else
-	    rb_str_cat2(tmp, DLEXT);
-	    OBJ_FREEZE(tmp);
-	    if ((tmp = rb_find_file_safe(tmp, safe_level)) != 0) {
-		ext = strrchr(ftptr = RSTRING_PTR(tmp), '.');
-		if (!rb_feature_p(ftptr, ext, FALSE, TRUE, &loading) || loading)
-		    *path = tmp;
-		return 's';
-	    }
-#endif
-	}
-	else if (IS_DLEXT(ext)) {
-	    if (rb_feature_p(ftptr, ext, FALSE, FALSE, &loading)) {
-		if (loading) *path = rb_str_new2(loading);
-		return 's';
-	    }
-	    if ((tmp = rb_find_file_safe(fname, safe_level)) != 0) {
-		ext = strrchr(ftptr = RSTRING_PTR(tmp), '.');
-		if (!rb_feature_p(ftptr, ext, FALSE, TRUE, &loading) || loading)
-		    *path = tmp;
-		return 's';
-	    }
-	}
-    }
-    else if ((ft = rb_feature_p(ftptr, 0, FALSE, FALSE, &loading)) == 'r') {
-	if (loading) *path = rb_str_new2(loading);
-	return 'r';
-    }
-    tmp = fname;
-    type = rb_find_file_ext_safe(&tmp, loadable_ext, safe_level);
-    switch (type) {
-      case 0:
-	if (ft)
-	    break;
-	ftptr = RSTRING_PTR(tmp);
-	return rb_feature_p(ftptr, 0, FALSE, TRUE, 0);
-
-      default:
-	if (ft)
-	    break;
-      case 1:
-	ext = strrchr(ftptr = RSTRING_PTR(tmp), '.');
-	if (rb_feature_p(ftptr, ext, !--type, TRUE, &loading) && !loading)
-	    break;
-	*path = tmp;
-    }
-    return type ? 's' : 'r';
-}
 
 static void
 load_failed(VALUE fname)
@@ -568,67 +386,6 @@ load_ext(VALUE path)
 }
 
 VALUE
-rb_require_safe(VALUE fname, int safe)
-{
-    volatile VALUE result = Qnil;
-    rb_thread_t *th = GET_THREAD();
-    volatile VALUE errinfo = th->errinfo;
-    int state;
-    struct {
-	int safe;
-    } volatile saved;
-    char *volatile ftptr = 0;
-
-    PUSH_TAG();
-    saved.safe = rb_safe_level();
-    if ((state = EXEC_TAG()) == 0) {
-	VALUE path;
-	long handle;
-	int found;
-
-	rb_set_safe_level_force(safe);
-	FilePathValue(fname);
-	rb_set_safe_level_force(0);
-	found = search_required(fname, &path, safe);
-	if (found) {
-	    if (!path || !(ftptr = load_lock(RSTRING_PTR(path)))) {
-		result = Qfalse;
-	    }
-	    else {
-		switch (found) {
-		  case 'r':
-		    rb_load_internal(path, 0);
-		    break;
-
-		  case 's':
-		    handle = (long)rb_vm_call_cfunc(rb_vm_top_self(), load_ext,
-						    path, 0, path);
-		    rb_ary_push(ruby_dln_librefs, LONG2NUM(handle));
-		    break;
-		}
-		rb_provide_feature(path);
-		result = Qtrue;
-	    }
-	}
-    }
-    POP_TAG();
-    load_unlock(ftptr, !state);
-
-    rb_set_safe_level_force(saved.safe);
-    if (state) {
-	JUMP_TAG(state);
-    }
-
-    if (NIL_P(result)) {
-	load_failed(fname);
-    }
-
-    th->errinfo = errinfo;
-
-    return result;
-}
-
-VALUE
 rb_require(const char *fname)
 {
     VALUE fn = rb_str_new2(fname);
@@ -741,11 +498,456 @@ rb_f_autoload_p(VALUE obj, VALUE sym)
     return rb_mod_autoload_p(klass, sym);
 }
 
+static int
+rb_feature_exists(VALUE expanded_path)
+{
+  return rb_funcall(rb_cFile, rb_intern("file?"), 1, expanded_path) == Qtrue;
+}
+
+static VALUE
+rb_locate_file_with_extension(VALUE base_file_name, VALUE extension) {
+	VALUE file_name_with_extension = rb_str_plus(
+			base_file_name,
+			extension);
+
+	if (rb_feature_exists(file_name_with_extension)) {
+		return file_name_with_extension;
+	} else {
+		return Qnil;
+	}
+}
+
+static VALUE
+rb_locate_file_with_extensions(VALUE base_file_name, VALUE extension) {
+	unsigned int j;
+	VALUE file_name_with_extension;
+	VALUE directory, basename;
+
+	for (j = 0; j < VALUE_ARRAY_LEN(available_ext_rb_str); ++j) {
+		file_name_with_extension = rb_str_plus(
+				base_file_name,
+				available_ext_rb_str[j]);
+
+		if (rb_feature_exists(file_name_with_extension)) {
+			return file_name_with_extension;
+		}
+	}
+
+	if (RSTRING_LEN(extension) != 0 && rb_feature_exists(base_file_name)) {
+		return base_file_name;
+	} else {
+		for (j = 0; j < CHAR_ARRAY_LEN(alternate_dl_extensions); ++j) {
+			// Try loading the native DLEXT version of this platform.
+			// This allows 'pathname.so' to require 'pathname.bundle' on OSX
+			directory = rb_file_dirname(base_file_name);
+			basename  = rb_funcall(rb_cFile, rb_intern("basename"), 2, 
+					base_file_name, extension);
+			basename  = rb_str_cat2(basename, alternate_dl_extensions[j]);
+
+			file_name_with_extension = rb_funcall(rb_cFile, rb_intern("join"), 2, 
+					directory, basename);
+
+			if (rb_feature_exists(file_name_with_extension)) {
+				return file_name_with_extension;
+			}
+
+			// Also try loading 'dot.dot.bundle' for 'dot.dot'
+			file_name_with_extension = rb_str_plus(
+					base_file_name,
+					rb_str_new2(alternate_dl_extensions[j]));
+
+			if (rb_feature_exists(file_name_with_extension)) {
+				return file_name_with_extension;
+			}
+		}
+	}
+	return Qnil;
+}
+
+static VALUE
+rb_file_extension(VALUE path)
+{
+	return rb_funcall(rb_cFile, rb_intern("extname"), 1, path);
+}
+
+static VALUE
+rb_locate_file_absolute(VALUE fname)
+{
+	return rb_locate_file_with_extensions(fname, rb_file_extension(fname));
+}
+
+static VALUE
+rb_locate_file_relative(VALUE fname)
+{
+    VALUE path = rb_file_expand_path(fname, Qnil);
+	return rb_locate_file_with_extensions(path, rb_file_extension(path));
+}
+
+/* This function is only used as an optimization in rb_locate_file_in_load_path */
+static VALUE
+rb_locate_rb_file_in_load_path(VALUE path, VALUE load_path, VALUE sep)
+{
+	long i;
+	VALUE base_file_name;
+	VALUE expanded_file_name;
+	VALUE rb_ext = rb_str_new2(".rb");
+
+	for (i = 0; i < RARRAY_LEN(load_path); ++i) {
+		VALUE directory = RARRAY_PTR(load_path)[i];
+
+		base_file_name = rb_str_plus(directory, sep);
+		base_file_name = rb_str_concat(base_file_name, path);
+
+		expanded_file_name = rb_locate_file_with_extension(base_file_name, rb_ext);
+
+		if (expanded_file_name != Qnil) {
+			return expanded_file_name;
+		}
+	}
+	return Qnil;
+}
+
+static VALUE
+rb_locate_file_in_load_path(VALUE path)
+{
+	long i;
+	VALUE load_path          = rb_get_expanded_load_path();
+	VALUE expanded_file_name = Qnil;
+	VALUE base_file_name     = Qnil;
+	VALUE sep                = rb_str_new2("/");
+	VALUE base_extension     = rb_file_extension(path);
+
+	if (RSTRING_LEN(base_extension) == 0) {
+		/* Do an initial loop through the load path only looking for .rb files.
+		 * This is the most common case, so optimize for it. If not found, fall 
+		 * back so searching all extensions.
+		 */
+		expanded_file_name = rb_locate_rb_file_in_load_path(path, load_path, sep);
+
+		if (expanded_file_name != Qnil) {
+			return expanded_file_name;
+		}
+	}
+
+	for (i = 0; i < RARRAY_LEN(load_path); ++i) {
+		VALUE directory = RARRAY_PTR(load_path)[i];
+
+		base_file_name = rb_str_plus(directory, sep);
+		base_file_name = rb_str_concat(base_file_name, path);
+
+		/* The .rb extension will be checked again in this call, which is redundant
+		 * since it was checked in the loop above. This hasn't been optimized to 
+		 * keep the code cleaner.
+		 */
+		expanded_file_name = rb_locate_file_with_extensions(base_file_name, base_extension);
+
+		if (expanded_file_name != Qnil) {
+			return expanded_file_name;
+		}
+	}
+	return Qnil;
+}
+
+static int
+rb_path_is_relative(VALUE path)
+{
+	const char * path_ptr = RSTRING_PTR(path);
+	const char * current_directory = "./";
+	const char * parent_directory  = "../";
+
+	return (
+			strncmp(current_directory, path_ptr, 2) == 0 ||
+			strncmp(parent_directory,  path_ptr, 3) == 0
+		   );
+}
+
+static int
+rb_file_is_ruby(VALUE path)
+{
+	const char * ext;
+	ext = ruby_find_extname(RSTRING_PTR(path), 0);
+
+	return ext && IS_RBEXT(ext);
+}
+
+static int
+rb_path_is_absolute(VALUE path)
+{
+	// Delegate to file.c
+	return rb_is_absolute_path(RSTRING_PTR(path));
+}
+
+static int
+rb_file_has_been_required(VALUE expanded_path)
+{
+	st_data_t data;
+	st_data_t path_key = (st_data_t)RSTRING_PTR(expanded_path);
+	st_table *loaded_features_hash = get_loaded_features_hash();
+
+	return st_lookup(loaded_features_hash, path_key, &data);
+}
+
+static int
+rb_file_is_being_required(VALUE full_path) {
+	const char *ftptr = RSTRING_PTR(full_path);
+	st_data_t data;
+	st_table *loading_tbl = get_loading_table();
+
+	return (loading_tbl && st_lookup(loading_tbl, (st_data_t)ftptr, &data));
+}
+
+static VALUE
+rb_get_cached_expansion(VALUE filename) 
+{
+	st_data_t data;
+	st_data_t path_key = (st_data_t)RSTRING_PTR(filename);
+	st_table *filename_expansion_hash = get_filename_expansion_hash();
+
+	if (st_lookup(filename_expansion_hash, path_key, &data)) {
+		return (VALUE)data;
+	} else {
+		return Qnil;
+	};
+}
+
+static void
+rb_set_cached_expansion(VALUE filename, VALUE expanded)
+{
+	st_data_t data = (st_data_t)expanded;
+	st_data_t path_key = (st_data_t)RSTRING_PTR(filename);
+	st_table *filename_expansion_hash = get_filename_expansion_hash();
+
+	st_insert(filename_expansion_hash, path_key, data);
+}
+
+static VALUE
+rb_locate_file(VALUE filename)
+{
+	VALUE full_path = Qnil;
+
+	full_path = rb_get_cached_expansion(filename);
+
+	if (full_path != Qnil)
+		return full_path;
+
+	if (rb_path_is_relative(filename)) {
+		full_path = rb_locate_file_relative(filename);
+	} else if (rb_path_is_absolute(filename)) {
+		full_path = rb_locate_file_absolute(filename);
+	} else {
+		full_path = rb_locate_file_in_load_path(filename);
+	}
+
+	if (full_path != Qnil)
+		rb_set_cached_expansion(filename, full_path);
+
+	return full_path;
+}
+
+/* 
+ * returns the path loaded, or nil if the file was already loaded. Raises
+ * LoadError if a file cannot be found. 
+ */
+VALUE
+rb_require_safe(VALUE fname, int safe)
+{
+	VALUE path = Qnil;
+	volatile VALUE result = Qnil;
+	rb_thread_t *th = GET_THREAD();
+	volatile VALUE errinfo = th->errinfo;
+	int state;
+	struct {
+		int safe;
+	} volatile saved;
+	char *volatile ftptr = 0;
+
+	PUSH_TAG();
+	saved.safe = rb_safe_level();
+	if ((state = EXEC_TAG()) == 0) {
+		long handle;
+		int found;
+
+		rb_set_safe_level_force(safe);
+		FilePathValue(fname);
+		rb_set_safe_level_force(0);
+
+		path = rb_locate_file(fname);
+
+		if (safe >= 1 && OBJ_TAINTED(path)) {
+			rb_raise(rb_eSecurityError, "Loading from unsafe file %s", RSTRING_PTR(path));
+		}
+
+		result = Qfalse;
+		if (path == Qnil) {
+			load_failed(fname);
+		} else {
+			if (ftptr = load_lock(RSTRING_PTR(path))) { // Allows circular requires to work
+				if (!rb_file_has_been_required(path)) {
+					if (rb_file_is_ruby(path)) {
+						rb_load_internal(path, 0);
+					} else {
+						handle = (long)rb_vm_call_cfunc(rb_vm_top_self(), load_ext,
+								path, 0, path);
+						rb_ary_push(ruby_dln_librefs, LONG2NUM(handle));
+					}
+					rb_provide_feature(path);
+					result = Qtrue;
+				}
+			}
+		}
+	}
+	POP_TAG();
+	load_unlock(ftptr, !state);
+
+	rb_set_safe_level_force(saved.safe);
+	if (state) {
+		JUMP_TAG(state);
+	}
+
+	if (NIL_P(result)) {
+		load_failed(fname);
+	}
+
+	th->errinfo = errinfo;
+
+	if (result == Qtrue) {
+		return path;
+	} else {
+		return Qnil;
+	}
+}
+
+/*
+ *  call-seq:
+ *     require(string)    -> true or false
+ *
+ *  Ruby tries to load the library named _string_, returning
+ *  +true+ if successful. If the filename does not resolve to
+ *  an absolute path, it will be searched for in the directories listed
+ *  in <code>$:</code>. If the file has the extension ``.rb'', it is
+ *  loaded as a source file; if the extension is ``.so'', ``.o'', or
+ *  ``.dll'', or whatever the default shared library extension is on
+ *  the current platform, Ruby loads the shared library as a Ruby
+ *  extension. Otherwise, Ruby tries adding ``.rb'', ``.so'', and so on
+ *  to the name. The name of the loaded feature is added to the array in
+ *  <code>$"</code>. A feature will not be loaded if its name already
+ *  appears in <code>$"</code>. The file name is converted to an absolute
+ *  path, so ``<code>require 'a'; require './a'</code>'' will not load
+ *  <code>a.rb</code> twice.
+ *
+ *     require "my-library.rb"
+ *     require "db-driver"
+ */
+VALUE
+rb_f_require(VALUE obj, VALUE fname)
+{
+    return rb_require_safe(fname, rb_safe_level()) == Qnil ? Qfalse : Qtrue;
+}
+
+static void
+rb_rehash_loaded_features()
+{
+  int i;
+  VALUE features;
+  VALUE feature;
+
+  st_table* loaded_features_hash = get_loaded_features_hash();
+
+  st_clear(loaded_features_hash);
+
+  features = get_loaded_features();
+
+  for (i = 0; i < RARRAY_LEN(features); ++i) {
+    feature = RARRAY_PTR(features)[i];
+    st_insert(
+      loaded_features_hash,
+      (st_data_t)ruby_strdup(RSTRING_PTR(feature)),
+      (st_data_t)rb_barrier_new());
+  }
+}
+
+static void
+rb_clear_cached_expansions()
+{
+  st_table* filename_expansion_hash = get_filename_expansion_hash();
+  st_clear(filename_expansion_hash);
+}
+
+static VALUE  
+rb_loaded_features_hook(int argc, VALUE *argv, VALUE self)  
+{ 
+	VALUE ret;
+	ret = rb_call_super(argc, argv);
+	rb_rehash_loaded_features();
+	rb_clear_cached_expansions();
+	return ret;
+}
+
+/*
+ * $LOADED_FEATURES is exposed publically as an array, but under the covers
+ * we also store this data in a hash for fast lookups. So that we can rebuild
+ * the hash whenever $LOADED_FEATURES is changed, we wrap the Array class
+ * in a proxy that intercepts all data-modifying methods and rebuilds the
+ * hash.
+ *
+ * Note that the list of intercepted methods is currently non-comprehensive
+ * --- it only covers modifications made by the ruby and rubyspec test suites.
+ */
+static void 
+define_loaded_features_proxy()
+{
+	const char* methods_to_hook[] = {"<<", "push", "clear", "replace", "delete"};
+	unsigned int i;
+
+	rb_cLoadedFeaturesProxy = rb_define_class("LoadedFeaturesProxy", rb_cArray); 
+	for (i = 0; i < CHAR_ARRAY_LEN(methods_to_hook); ++i) {
+		rb_define_method(
+				rb_cLoadedFeaturesProxy,
+				methods_to_hook[i],
+				rb_loaded_features_hook,
+				-1);
+	}
+}
+
+
+/* Should return true if the file has or is being loaded, but should 
+ * not actually load the file.
+ */
+int
+rb_feature_provided_2(VALUE fname)
+{
+	VALUE full_path = rb_locate_file(fname);
+
+	if (
+		full_path != Qnil && 
+		(
+			rb_file_has_been_required(full_path) || 
+			rb_file_is_being_required(full_path)
+		)
+	) {
+		return TRUE;
+	} else {
+		return FALSE;
+	}
+}
+
+/*
+ * Deprecated, use rb_feature_provided_2
+ */
+int
+rb_feature_provided(const char *feature, const char **loading)
+{
+    VALUE fname = rb_str_new2(feature);
+	rb_feature_provided_2(fname);
+}
+
+
 void
 Init_load()
 {
 #undef rb_intern
 #define rb_intern(str) rb_intern2((str), strlen(str))
+	unsigned int j;
     rb_vm_t *vm = GET_VM();
     static const char var_load_path[] = "$:";
     ID id_load_path = rb_intern2(var_load_path, sizeof(var_load_path)-1);
@@ -757,7 +959,10 @@ Init_load()
 
     rb_define_virtual_variable("$\"", get_loaded_features, 0);
     rb_define_virtual_variable("$LOADED_FEATURES", get_loaded_features, 0);
-    vm->loaded_features = rb_ary_new();
+
+    define_loaded_features_proxy();
+
+    vm->loaded_features = ary_new(rb_cLoadedFeaturesProxy, RARRAY_EMBED_LEN_MAX);
 
     rb_define_global_function("load", rb_f_load, -1);
     rb_define_global_function("require", rb_f_require, 1);
@@ -769,4 +974,9 @@ Init_load()
 
     ruby_dln_librefs = rb_ary_new();
     rb_gc_register_mark_object(ruby_dln_librefs);
+
+	for (j = 0; j < CHAR_ARRAY_LEN(available_extensions); ++j) {
+		available_ext_rb_str[j] = rb_str_new2(available_extensions[j]);
+		rb_gc_register_mark_object(available_ext_rb_str[j]);
+	}
 }
diff --git a/test/ruby/test_require.rb b/test/ruby/test_require.rb
index 96b1551..9f9444c 100644
--- a/test/ruby/test_require.rb
+++ b/test/ruby/test_require.rb
@@ -339,4 +339,50 @@ class TestRequire < Test::Unit::TestCase
                       [], /\$LOADED_FEATURES is frozen; cannot append feature \(RuntimeError\)$/,
                       bug3756)
   end
+
+  def test_case_insensitive
+    load_path = $:.dup
+    loaded = $".dup
+    path = File.expand_path(__FILE__)
+    $:.unshift(File.dirname(path))
+    $".push(path) unless $".include?(path)
+    bug4255 = '[ruby-core:34297]'
+    assert_equal(false, $bug4255 ||= false, bug4255)
+    $bug4255 = true
+    f = File.basename(__FILE__, ".*").upcase
+    assert_equal(false, require(f))
+  ensure
+    $:.replace(load_path)
+    $".replace(loaded)
+  end if File.identical?(__FILE__, __FILE__.upcase)
+
+  def test_feature_is_reloaded_from_new_load_path_entry
+    # This is a bit of a weird test, but it is needed to ensure that some
+    # caching optimizations are working correctly.
+    load_path      = $:.dup
+    loaded         = $".dup
+    initial_length = loaded.length
+
+    Dir.mktmpdir do |tmp|
+      Dir.chdir(tmp) do
+        Dir.mkdir "a"
+        Dir.mkdir "b"
+        File.open("a/test.rb", "w") {|f| f.puts '' }
+        File.open("b/test.rb", "w") {|f| f.puts '' }
+
+        $".clear
+        $:.unshift(File.join(tmp, "b"))
+        require 'test.rb'
+        assert $"[0].include?('b/test.rb')
+
+        $".clear
+        $:.unshift(File.join(tmp, "a"))
+        require 'test.rb'
+        assert $"[0].include?('a/test.rb')
+      end
+    end
+  ensure
+    $:.replace(load_path)
+    $".replace(loaded)
+  end
 end
diff --git a/variable.c b/variable.c
index 426d58f..8758375 100644
--- a/variable.c
+++ b/variable.c
@@ -19,6 +19,7 @@
 #include "constant.h"
 #include "internal.h"
 
+VALUE rb_feature_provided_2(VALUE);
 void rb_vm_change_state(void);
 void rb_vm_inc_const_missing_count(void);
 
@@ -1489,10 +1490,9 @@ autoload_delete(VALUE mod, ID id)
 }
 
 static VALUE
-autoload_provided(VALUE arg)
+autoload_provided(VALUE fname)
 {
-    const char **p = (const char **)arg;
-    return rb_feature_provided(*p, p);
+    return rb_feature_provided_2(fname);
 }
 
 static VALUE
@@ -1525,7 +1525,7 @@ autoload_node(VALUE mod, ID id, const char **loadingpath)
     loading = RSTRING_PTR(file);
     safe = rb_safe_level();
     rb_set_safe_level_force(0);
-    if (!rb_ensure(autoload_provided, (VALUE)&loading, reset_safe, (VALUE)safe)) {
+    if (!rb_ensure(autoload_provided, (VALUE)file, reset_safe, (VALUE)safe)) {
 	return load;
     }
     if (loadingpath && loading) {
diff --git a/vm.c b/vm.c
index bddb4dd..a96b006 100644
--- a/vm.c
+++ b/vm.c
@@ -1527,6 +1527,14 @@ rb_vm_mark(void *ptr)
 	    rb_mark_tbl(vm->loading_table);
 	}
 
+	if (vm->loaded_features_hash) {
+	    rb_mark_tbl(vm->loaded_features_hash);
+	}
+
+	if (vm->filename_expansion_hash) {
+	    rb_mark_tbl(vm->filename_expansion_hash);
+	}
+
 	mark_event_hooks(vm->event_hooks);
 
 	for (i = 0; i < RUBY_NSIG; i++) {
diff --git a/vm_core.h b/vm_core.h
index e302e62..d5f5fb7 100644
--- a/vm_core.h
+++ b/vm_core.h
@@ -324,6 +324,9 @@ typedef struct rb_vm_struct {
      * objects so do *NOT* mark this when you GC.
      */
     struct RArray at_exit;
+
+    struct st_table *loaded_features_hash;
+    struct st_table *filename_expansion_hash;
 } rb_vm_t;
 
 typedef struct {