1 files changed, 95 insertions, 133 deletions

diff --git a/scene/gui/code_edit.cpp b/scene/gui/code_edit.cpp
index d83182c775..efbc067d20 100644
--- a/scene/gui/code_edit.cpp
+++ b/scene/gui/code_edit.cpp
@@ -142,13 +142,12 @@ void CodeEdit::_notification(int p_what) {
 					Point2 match_pos = Point2(code_completion_rect.position.x + icon_area_size.x + theme_cache.code_completion_icon_separation, code_completion_rect.position.y + i * row_height);
 
 					for (int j = 0; j < code_completion_options[l].matches.size(); j++) {
-						Pair<int, int> match = code_completion_options[l].matches[j];
-						int match_offset = theme_cache.font->get_string_size(code_completion_options[l].display.substr(0, match.first), HORIZONTAL_ALIGNMENT_LEFT, -1, theme_cache.font_size).width;
-						int match_len = theme_cache.font->get_string_size(code_completion_options[l].display.substr(match.first, match.second), HORIZONTAL_ALIGNMENT_LEFT, -1, theme_cache.font_size).width;
+						Pair<int, int> match_segment = code_completion_options[l].matches[j];
+						int match_offset = theme_cache.font->get_string_size(code_completion_options[l].display.substr(0, match_segment.first), HORIZONTAL_ALIGNMENT_LEFT, -1, theme_cache.font_size).width;
+						int match_len = theme_cache.font->get_string_size(code_completion_options[l].display.substr(match_segment.first, match_segment.second), HORIZONTAL_ALIGNMENT_LEFT, -1, theme_cache.font_size).width;
 
 						draw_rect(Rect2(match_pos + Point2(match_offset, 0), Size2(match_len, row_height)), theme_cache.code_completion_existing_color);
 					}
-
 					tl->draw(ci, title_pos, code_completion_options[l].font_color);
 				}
 
@@ -2031,7 +2030,7 @@ void CodeEdit::request_code_completion(bool p_force) {
 	}
 }
 
-void CodeEdit::add_code_completion_option(CodeCompletionKind p_type, const String &p_display_text, const String &p_insert_text, const Color &p_text_color, const Ref<Resource> &p_icon, const Variant &p_value) {
+void CodeEdit::add_code_completion_option(CodeCompletionKind p_type, const String &p_display_text, const String &p_insert_text, const Color &p_text_color, const Ref<Resource> &p_icon, const Variant &p_value, int p_location) {
 	ScriptLanguage::CodeCompletionOption completion_option;
 	completion_option.kind = (ScriptLanguage::CodeCompletionKind)p_type;
 	completion_option.display = p_display_text;
@@ -2039,6 +2038,7 @@ void CodeEdit::add_code_completion_option(CodeCompletionKind p_type, const Strin
 	completion_option.font_color = p_text_color;
 	completion_option.icon = p_icon;
 	completion_option.default_value = p_value;
+	completion_option.location = p_location;
 	code_completion_option_submitted.push_back(completion_option);
 }
 
@@ -2063,6 +2063,7 @@ TypedArray<Dictionary> CodeEdit::get_code_completion_options() const {
 		option["insert_text"] = code_completion_options[i].insert_text;
 		option["font_color"] = code_completion_options[i].font_color;
 		option["icon"] = code_completion_options[i].icon;
+		option["location"] = code_completion_options[i].location;
 		option["default_value"] = code_completion_options[i].default_value;
 		completion_options[i] = option;
 	}
@@ -2081,6 +2082,7 @@ Dictionary CodeEdit::get_code_completion_option(int p_index) const {
 	option["insert_text"] = code_completion_options[p_index].insert_text;
 	option["font_color"] = code_completion_options[p_index].font_color;
 	option["icon"] = code_completion_options[p_index].icon;
+	option["location"] = code_completion_options[p_index].location;
 	option["default_value"] = code_completion_options[p_index].default_value;
 	return option;
 }
@@ -2424,9 +2426,14 @@ void CodeEdit::_bind_methods() {
 	BIND_ENUM_CONSTANT(KIND_FILE_PATH);
 	BIND_ENUM_CONSTANT(KIND_PLAIN_TEXT);
 
+	BIND_ENUM_CONSTANT(LOCATION_LOCAL);
+	BIND_ENUM_CONSTANT(LOCATION_PARENT_MASK);
+	BIND_ENUM_CONSTANT(LOCATION_OTHER_USER_CODE)
+	BIND_ENUM_CONSTANT(LOCATION_OTHER);
+
 	ClassDB::bind_method(D_METHOD("get_text_for_code_completion"), &CodeEdit::get_text_for_code_completion);
 	ClassDB::bind_method(D_METHOD("request_code_completion", "force"), &CodeEdit::request_code_completion, DEFVAL(false));
-	ClassDB::bind_method(D_METHOD("add_code_completion_option", "type", "display_text", "insert_text", "text_color", "icon", "value"), &CodeEdit::add_code_completion_option, DEFVAL(Color(1, 1, 1)), DEFVAL(Ref<Resource>()), DEFVAL(Variant::NIL));
+	ClassDB::bind_method(D_METHOD("add_code_completion_option", "type", "display_text", "insert_text", "text_color", "icon", "value", "location"), &CodeEdit::add_code_completion_option, DEFVAL(Color(1, 1, 1)), DEFVAL(Ref<Resource>()), DEFVAL(Variant::NIL), DEFVAL(LOCATION_OTHER));
 	ClassDB::bind_method(D_METHOD("update_code_completion_options", "force"), &CodeEdit::update_code_completion_options);
 	ClassDB::bind_method(D_METHOD("get_code_completion_options"), &CodeEdit::get_code_completion_options);
 	ClassDB::bind_method(D_METHOD("get_code_completion_option", "index"), &CodeEdit::get_code_completion_option);
@@ -2954,6 +2961,7 @@ void CodeEdit::_filter_code_completion_candidates_impl() {
 			option["font_color"] = E.font_color;
 			option["icon"] = E.icon;
 			option["default_value"] = E.default_value;
+			option["location"] = E.location;
 			completion_options_sources[i] = option;
 			i++;
 		}
@@ -2977,6 +2985,7 @@ void CodeEdit::_filter_code_completion_candidates_impl() {
 			option.insert_text = completion_options[i].get("insert_text");
 			option.font_color = completion_options[i].get("font_color");
 			option.icon = completion_options[i].get("icon");
+			option.location = completion_options[i].get("location");
 			option.default_value = completion_options[i].get("default_value");
 
 			int offset = 0;
@@ -3063,7 +3072,7 @@ void CodeEdit::_filter_code_completion_candidates_impl() {
 	}
 
 	/* Filter Options. */
-	/* For now handle only tradional quoted strings. */
+	/* For now handle only traditional quoted strings. */
 	bool single_quote = in_string != -1 && first_quote_col > 0 && delimiters[in_string].start_key == "'";
 
 	code_completion_options.clear();
@@ -3075,23 +3084,16 @@ void CodeEdit::_filter_code_completion_candidates_impl() {
 		return;
 	}
 
-	Vector<ScriptLanguage::CodeCompletionOption> completion_options_casei;
-	Vector<ScriptLanguage::CodeCompletionOption> completion_options_substr;
-	Vector<ScriptLanguage::CodeCompletionOption> completion_options_substr_casei;
-	Vector<ScriptLanguage::CodeCompletionOption> completion_options_subseq;
-	Vector<ScriptLanguage::CodeCompletionOption> completion_options_subseq_casei;
-
 	int max_width = 0;
 	String string_to_complete_lower = string_to_complete.to_lower();
+
 	for (ScriptLanguage::CodeCompletionOption &option : code_completion_option_sources) {
+		option.matches.clear();
 		if (single_quote && option.display.is_quoted()) {
 			option.display = option.display.unquote().quote("'");
 		}
 
-		int offset = 0;
-		if (option.default_value.get_type() == Variant::COLOR) {
-			offset = line_height;
-		}
+		int offset = option.default_value.get_type() == Variant::COLOR ? line_height : 0;
 
 		if (in_string != -1) {
 			String quote = single_quote ? "'" : "\"";
@@ -3104,6 +3106,7 @@ void CodeEdit::_filter_code_completion_candidates_impl() {
 		}
 
 		if (string_to_complete.length() == 0) {
+			option.get_option_characteristics(string_to_complete);
 			code_completion_options.push_back(option);
 			if (theme_cache.font.is_valid()) {
 				max_width = MAX(max_width, theme_cache.font->get_string_size(option.display, HORIZONTAL_ALIGNMENT_LEFT, -1, theme_cache.font_size).width + offset);
@@ -3111,139 +3114,73 @@ void CodeEdit::_filter_code_completion_candidates_impl() {
 			continue;
 		}
 
-		/* This code works the same as:
-
-		if (option.display.begins_with(s)) {
-			completion_options.push_back(option);
-		} else if (option.display.to_lower().begins_with(s.to_lower())) {
-			completion_options_casei.push_back(option);
-		} else if (s.is_subsequence_of(option.display)) {
-			completion_options_subseq.push_back(option);
-		} else if (s.is_subsequence_ofn(option.display)) {
-			completion_options_subseq_casei.push_back(option);
-		}
-
-		But is more performant due to being inlined and looping over the characters only once
-		*/
-
-		String display_lower = option.display.to_lower();
-
-		const char32_t *ssq = &string_to_complete[0];
-		const char32_t *ssq_lower = &string_to_complete_lower[0];
-
-		const char32_t *tgt = &option.display[0];
-		const char32_t *tgt_lower = &display_lower[0];
+		String target_lower = option.display.to_lower();
+		const char32_t *string_to_complete_char_lower = &string_to_complete_lower[0];
+		const char32_t *target_char_lower = &target_lower[0];
 
-		const char32_t *sst = &string_to_complete[0];
-		const char32_t *sst_lower = &display_lower[0];
-
-		Vector<Pair<int, int>> ssq_matches;
-		int ssq_match_start = 0;
-		int ssq_match_len = 0;
-
-		Vector<Pair<int, int>> ssq_lower_matches;
-		int ssq_lower_match_start = 0;
-		int ssq_lower_match_len = 0;
-
-		int sst_start = -1;
-		int sst_lower_start = -1;
-
-		for (int i = 0; *tgt; tgt++, tgt_lower++, i++) {
-			// Check substring.
-			if (*sst == *tgt) {
-				sst++;
-				if (sst_start == -1) {
-					sst_start = i;
-				}
-			} else if (sst_start != -1 && *sst) {
-				sst = &string_to_complete[0];
-				sst_start = -1;
+		Vector<Vector<Pair<int, int>>> all_possible_subsequence_matches;
+		for (int i = 0; *target_char_lower; i++, target_char_lower++) {
+			if (*target_char_lower == *string_to_complete_char_lower) {
+				all_possible_subsequence_matches.push_back({ { i, 1 } });
 			}
+		}
+		string_to_complete_char_lower++;
 
-			// Check subsequence.
-			if (*ssq == *tgt) {
-				ssq++;
-				if (ssq_match_len == 0) {
-					ssq_match_start = i;
+		for (int i = 1; *string_to_complete_char_lower && (all_possible_subsequence_matches.size() > 0); i++, string_to_complete_char_lower++) {
+			// find all occurrences of ssq_lower to avoid looking everywhere each time
+			Vector<int> all_ocurence;
+			for (int j = i; j < target_lower.length(); j++) {
+				if (target_lower[j] == *string_to_complete_char_lower) {
+					all_ocurence.push_back(j);
 				}
-				ssq_match_len++;
-			} else if (ssq_match_len > 0) {
-				ssq_matches.push_back(Pair<int, int>(ssq_match_start, ssq_match_len));
-				ssq_match_len = 0;
 			}
-
-			// Check lower substring.
-			if (*sst_lower == *tgt) {
-				sst_lower++;
-				if (sst_lower_start == -1) {
-					sst_lower_start = i;
+			Vector<Vector<Pair<int, int>>> next_subsequence_matches;
+			for (Vector<Pair<int, int>> &subsequence_matches : all_possible_subsequence_matches) {
+				Pair<int, int> match_last_segment = subsequence_matches[subsequence_matches.size() - 1];
+				int next_index = match_last_segment.first + match_last_segment.second;
+				// get the last index from current sequence
+				// and look for next char starting from that index
+				if (target_lower[next_index] == *string_to_complete_char_lower) {
+					Vector<Pair<int, int>> new_matches = subsequence_matches;
+					new_matches.write[new_matches.size() - 1].second++;
+					next_subsequence_matches.push_back(new_matches);
 				}
-			} else if (sst_lower_start != -1 && *sst_lower) {
-				sst_lower = &string_to_complete[0];
-				sst_lower_start = -1;
-			}
-
-			// Check lower subsequence.
-			if (*ssq_lower == *tgt_lower) {
-				ssq_lower++;
-				if (ssq_lower_match_len == 0) {
-					ssq_lower_match_start = i;
+				for (int index : all_ocurence) {
+					if (index > next_index) {
+						Vector<Pair<int, int>> new_matches = subsequence_matches;
+						new_matches.push_back({ index, 1 });
+						next_subsequence_matches.push_back(new_matches);
+					}
 				}
-				ssq_lower_match_len++;
-			} else if (ssq_lower_match_len > 0) {
-				ssq_lower_matches.push_back(Pair<int, int>(ssq_lower_match_start, ssq_lower_match_len));
-				ssq_lower_match_len = 0;
 			}
-		}
-
-		/* Matched the whole subsequence in s. */
-		if (!*ssq) { // Matched the whole subsequence in s.
-			option.matches.clear();
-
-			if (sst_start == 0) { // Matched substring in beginning of s.
-				option.matches.push_back(Pair<int, int>(sst_start, string_to_complete.length()));
-				code_completion_options.push_back(option);
-			} else if (sst_start > 0) { // Matched substring in s.
-				option.matches.push_back(Pair<int, int>(sst_start, string_to_complete.length()));
-				completion_options_substr.push_back(option);
-			} else {
-				if (ssq_match_len > 0) {
-					ssq_matches.push_back(Pair<int, int>(ssq_match_start, ssq_match_len));
+			all_possible_subsequence_matches = next_subsequence_matches;
+		}
+		// go through all possible matches to get the best one as defined by CodeCompletionOptionCompare
+		if (all_possible_subsequence_matches.size() > 0) {
+			option.matches = all_possible_subsequence_matches[0];
+			option.get_option_characteristics(string_to_complete);
+			all_possible_subsequence_matches = all_possible_subsequence_matches.slice(1);
+			if (all_possible_subsequence_matches.size() > 0) {
+				CodeCompletionOptionCompare compare;
+				ScriptLanguage::CodeCompletionOption compared_option = option;
+				compared_option.clear_characteristics();
+				for (Vector<Pair<int, int>> &matches : all_possible_subsequence_matches) {
+					compared_option.matches = matches;
+					compared_option.get_option_characteristics(string_to_complete);
+					if (compare(compared_option, option)) {
+						option = compared_option;
+						compared_option.clear_characteristics();
+					}
 				}
-				option.matches.append_array(ssq_matches);
-				completion_options_subseq.push_back(option);
 			}
-			if (theme_cache.font.is_valid()) {
-				max_width = MAX(max_width, theme_cache.font->get_string_size(option.display, HORIZONTAL_ALIGNMENT_LEFT, -1, theme_cache.font_size).width + offset);
-			}
-		} else if (!*ssq_lower) { // Matched the whole subsequence in s_lower.
-			option.matches.clear();
 
-			if (sst_lower_start == 0) { // Matched substring in beginning of s_lower.
-				option.matches.push_back(Pair<int, int>(sst_lower_start, string_to_complete.length()));
-				completion_options_casei.push_back(option);
-			} else if (sst_lower_start > 0) { // Matched substring in s_lower.
-				option.matches.push_back(Pair<int, int>(sst_lower_start, string_to_complete.length()));
-				completion_options_substr_casei.push_back(option);
-			} else {
-				if (ssq_lower_match_len > 0) {
-					ssq_lower_matches.push_back(Pair<int, int>(ssq_lower_match_start, ssq_lower_match_len));
-				}
-				option.matches.append_array(ssq_lower_matches);
-				completion_options_subseq_casei.push_back(option);
-			}
+			code_completion_options.push_back(option);
 			if (theme_cache.font.is_valid()) {
 				max_width = MAX(max_width, theme_cache.font->get_string_size(option.display, HORIZONTAL_ALIGNMENT_LEFT, -1, theme_cache.font_size).width + offset);
 			}
 		}
 	}
 
-	code_completion_options.append_array(completion_options_casei);
-	code_completion_options.append_array(completion_options_substr);
-	code_completion_options.append_array(completion_options_substr_casei);
-	code_completion_options.append_array(completion_options_subseq);
-	code_completion_options.append_array(completion_options_subseq_casei);
-
 	/* No options to complete, cancel. */
 	if (code_completion_options.size() == 0) {
 		cancel_code_completion();
@@ -3256,6 +3193,8 @@ void CodeEdit::_filter_code_completion_candidates_impl() {
 		return;
 	}
 
+	code_completion_options.sort_custom<CodeCompletionOptionCompare>();
+
 	code_completion_longest_line = MIN(max_width, theme_cache.code_completion_max_width * theme_cache.font_size);
 	code_completion_current_selected = 0;
 	code_completion_force_item_center = -1;
@@ -3384,3 +3323,26 @@ CodeEdit::CodeEdit() {
 
 CodeEdit::~CodeEdit() {
 }
+
+// Return true if l should come before r
+bool CodeCompletionOptionCompare::operator()(const ScriptLanguage::CodeCompletionOption &l, const ScriptLanguage::CodeCompletionOption &r) const {
+	// Check if we are not completing an empty string in this case there is no reason to get matches characteristics.
+
+	TypedArray<int> lcharac = l.get_option_cached_characteristics();
+	TypedArray<int> rcharac = r.get_option_cached_characteristics();
+
+	if (lcharac != rcharac) {
+		return lcharac < rcharac;
+	}
+
+	// to get here they need to have the same size so we can take the size of whichever we want
+	for (int i = 0; i < l.matches.size(); ++i) {
+		if (l.matches[i].first != r.matches[i].first) {
+			return l.matches[i].first < r.matches[i].first;
+		}
+		if (l.matches[i].second != r.matches[i].second) {
+			return l.matches[i].second > r.matches[i].second;
+		}
+	}
+	return l.display < r.display;
+}