Fix sorting of files/dirs in dialogs

Sorts leading `_` before other characters except `.`.

2 files changed, 97 insertions, 39 deletions

diff --git a/core/string/ustring.cpp b/core/string/ustring.cpp
index a7e12138f2..dbc283946e 100644
--- a/core/string/ustring.cpp
+++ b/core/string/ustring.cpp
@@ -927,52 +927,49 @@ static _FORCE_INLINE_ signed char natural_cmp_common(const char32_t *&r_this_str
 	return 0;
 }
 
-signed char String::naturalcasecmp_to(const String &p_str) const {
-	const char32_t *this_str = get_data();
-	const char32_t *that_str = p_str.get_data();
-
-	if (this_str && that_str) {
-		while (*this_str == '.' || *that_str == '.') {
-			if (*this_str++ != '.') {
+static _FORCE_INLINE_ signed char naturalcasecmp_to_base(const char32_t *p_this_str, const char32_t *p_that_str) {
+	if (p_this_str && p_that_str) {
+		while (*p_this_str == '.' || *p_that_str == '.') {
+			if (*p_this_str++ != '.') {
 				return 1;
 			}
-			if (*that_str++ != '.') {
+			if (*p_that_str++ != '.') {
 				return -1;
 			}
-			if (!*that_str) {
+			if (!*p_that_str) {
 				return 1;
 			}
-			if (!*this_str) {
+			if (!*p_this_str) {
 				return -1;
 			}
 		}
 
-		while (*this_str) {
-			if (!*that_str) {
+		while (*p_this_str) {
+			if (!*p_that_str) {
 				return 1;
-			} else if (is_digit(*this_str)) {
-				if (!is_digit(*that_str)) {
+			} else if (is_digit(*p_this_str)) {
+				if (!is_digit(*p_that_str)) {
 					return -1;
 				}
 
-				signed char ret = natural_cmp_common(this_str, that_str);
+				signed char ret = natural_cmp_common(p_this_str, p_that_str);
 				if (ret) {
 					return ret;
 				}
-			} else if (is_digit(*that_str)) {
+			} else if (is_digit(*p_that_str)) {
 				return 1;
 			} else {
-				if (*this_str < *that_str) { // If current character in this is less, we are less.
+				if (*p_this_str < *p_that_str) { // If current character in this is less, we are less.
 					return -1;
-				} else if (*this_str > *that_str) { // If current character in this is greater, we are greater.
+				} else if (*p_this_str > *p_that_str) { // If current character in this is greater, we are greater.
 					return 1;
 				}
 
-				this_str++;
-				that_str++;
+				p_this_str++;
+				p_that_str++;
 			}
 		}
-		if (*that_str) {
+		if (*p_that_str) {
 			return -1;
 		}
 	}
@@ -980,52 +977,56 @@ signed char String::naturalcasecmp_to(const String &p_str) const {
 	return 0;
 }
 
-signed char String::naturalnocasecmp_to(const String &p_str) const {
+signed char String::naturalcasecmp_to(const String &p_str) const {
 	const char32_t *this_str = get_data();
 	const char32_t *that_str = p_str.get_data();
 
-	if (this_str && that_str) {
-		while (*this_str == '.' || *that_str == '.') {
-			if (*this_str++ != '.') {
+	return naturalcasecmp_to_base(this_str, that_str);
+}
+
+static _FORCE_INLINE_ signed char naturalnocasecmp_to_base(const char32_t *p_this_str, const char32_t *p_that_str) {
+	if (p_this_str && p_that_str) {
+		while (*p_this_str == '.' || *p_that_str == '.') {
+			if (*p_this_str++ != '.') {
 				return 1;
 			}
-			if (*that_str++ != '.') {
+			if (*p_that_str++ != '.') {
 				return -1;
 			}
-			if (!*that_str) {
+			if (!*p_that_str) {
 				return 1;
 			}
-			if (!*this_str) {
+			if (!*p_this_str) {
 				return -1;
 			}
 		}
 
-		while (*this_str) {
-			if (!*that_str) {
+		while (*p_this_str) {
+			if (!*p_that_str) {
 				return 1;
-			} else if (is_digit(*this_str)) {
-				if (!is_digit(*that_str)) {
+			} else if (is_digit(*p_this_str)) {
+				if (!is_digit(*p_that_str)) {
 					return -1;
 				}
 
-				signed char ret = natural_cmp_common(this_str, that_str);
+				signed char ret = natural_cmp_common(p_this_str, p_that_str);
 				if (ret) {
 					return ret;
 				}
-			} else if (is_digit(*that_str)) {
+			} else if (is_digit(*p_that_str)) {
 				return 1;
 			} else {
-				if (_find_upper(*this_str) < _find_upper(*that_str)) { // If current character in this is less, we are less.
+				if (_find_upper(*p_this_str) < _find_upper(*p_that_str)) { // If current character in this is less, we are less.
 					return -1;
-				} else if (_find_upper(*this_str) > _find_upper(*that_str)) { // If current character in this is greater, we are greater.
+				} else if (_find_upper(*p_this_str) > _find_upper(*p_that_str)) { // If current character in this is greater, we are greater.
 					return 1;
 				}
 
-				this_str++;
-				that_str++;
+				p_this_str++;
+				p_that_str++;
 			}
 		}
-		if (*that_str) {
+		if (*p_that_str) {
 			return -1;
 		}
 	}
@@ -1033,6 +1034,54 @@ signed char String::naturalnocasecmp_to(const String &p_str) const {
 	return 0;
 }
 
+signed char String::naturalnocasecmp_to(const String &p_str) const {
+	const char32_t *this_str = get_data();
+	const char32_t *that_str = p_str.get_data();
+
+	return naturalnocasecmp_to_base(this_str, that_str);
+}
+
+static _FORCE_INLINE_ signed char file_cmp_common(const char32_t *&r_this_str, const char32_t *&r_that_str) {
+	// Compare leading `_` sequences.
+	while (*r_this_str && *r_that_str) {
+		// Sort `_` lower than everything except `.`
+		if (*r_this_str != '_' && *r_that_str == '_') {
+			return *r_this_str == '.' ? -1 : 1;
+		}
+		if (*r_this_str == '_' && *r_that_str != '_') {
+			return *r_that_str == '.' ? 1 : -1;
+		}
+		r_this_str++;
+		r_that_str++;
+	}
+
+	return 0;
+}
+
+signed char String::filecasecmp_to(const String &p_str) const {
+	const char32_t *this_str = get_data();
+	const char32_t *that_str = p_str.get_data();
+
+	signed char ret = file_cmp_common(this_str, that_str);
+	if (ret) {
+		return ret;
+	}
+
+	return naturalcasecmp_to_base(this_str, that_str);
+}
+
+signed char String::filenocasecmp_to(const String &p_str) const {
+	const char32_t *this_str = get_data();
+	const char32_t *that_str = p_str.get_data();
+
+	signed char ret = file_cmp_common(this_str, that_str);
+	if (ret) {
+		return ret;
+	}
+
+	return naturalnocasecmp_to_base(this_str, that_str);
+}
+
 const char32_t *String::get_data() const {
 	static const char32_t zero = 0;
 	return size() ? &operator[](0) : &zero;
diff --git a/core/string/ustring.h b/core/string/ustring.h
index 0fb72fccd2..fa904c8200 100644
--- a/core/string/ustring.h
+++ b/core/string/ustring.h
@@ -265,6 +265,9 @@ public:
 	signed char nocasecmp_to(const String &p_str) const;
 	signed char naturalcasecmp_to(const String &p_str) const;
 	signed char naturalnocasecmp_to(const String &p_str) const;
+	// Special sorting for file names. Names starting with `_` are put before all others except those starting with `.`, otherwise natural comparison is used.
+	signed char filecasecmp_to(const String &p_str) const;
+	signed char filenocasecmp_to(const String &p_str) const;
 
 	const char32_t *get_data() const;
 	/* standard size stuff */
@@ -499,6 +502,12 @@ struct NaturalNoCaseComparator {
 	}
 };
 
+struct FileNoCaseComparator {
+	bool operator()(const String &p_a, const String &p_b) const {
+		return p_a.filenocasecmp_to(p_b) < 0;
+	}
+};
+
 template <typename L, typename R>
 _FORCE_INLINE_ bool is_str_less(const L *l_ptr, const R *r_ptr) {
 	while (true) {