Add fuzzy string matching to quick open search

Co-authored-by: sam <samsface@gmail.com>

2 files changed, 148 insertions, 201 deletions

diff --git a/scene/gui/label.cpp b/scene/gui/label.cpp
index 42b4e56b48..7a0e5b8867 100644
--- a/scene/gui/label.cpp
+++ b/scene/gui/label.cpp
@@ -335,6 +335,121 @@ inline void draw_glyph_outline(const Glyph &p_gl, const RID &p_canvas, const Col
 	}
 }
 
+void Label::_ensure_shaped() const {
+	if (dirty || font_dirty || lines_dirty) {
+		const_cast<Label *>(this)->_shape();
+	}
+}
+
+RID Label::get_line_rid(int p_line) const {
+	return lines_rid[p_line];
+}
+
+Rect2 Label::get_line_rect(int p_line) const {
+	// Returns a rect providing the line's horizontal offset and total size. To determine the vertical
+	// offset, use r_offset and r_line_spacing from get_layout_data.
+	bool rtl = TS->shaped_text_get_inferred_direction(text_rid) == TextServer::DIRECTION_RTL;
+	bool rtl_layout = is_layout_rtl();
+	Ref<StyleBox> style = theme_cache.normal_style;
+	Size2 size = get_size();
+	Size2 line_size = TS->shaped_text_get_size(lines_rid[p_line]);
+	Vector2 offset;
+
+	switch (horizontal_alignment) {
+		case HORIZONTAL_ALIGNMENT_FILL:
+			if (rtl && autowrap_mode != TextServer::AUTOWRAP_OFF) {
+				offset.x = int(size.width - style->get_margin(SIDE_RIGHT) - line_size.width);
+			} else {
+				offset.x = style->get_offset().x;
+			}
+			break;
+		case HORIZONTAL_ALIGNMENT_LEFT: {
+			if (rtl_layout) {
+				offset.x = int(size.width - style->get_margin(SIDE_RIGHT) - line_size.width);
+			} else {
+				offset.x = style->get_offset().x;
+			}
+		} break;
+		case HORIZONTAL_ALIGNMENT_CENTER: {
+			offset.x = int(size.width - line_size.width) / 2;
+		} break;
+		case HORIZONTAL_ALIGNMENT_RIGHT: {
+			if (rtl_layout) {
+				offset.x = style->get_offset().x;
+			} else {
+				offset.x = int(size.width - style->get_margin(SIDE_RIGHT) - line_size.width);
+			}
+		} break;
+	}
+
+	return Rect2(offset, line_size);
+}
+
+void Label::get_layout_data(Vector2 &r_offset, int &r_line_limit, int &r_line_spacing) const {
+	// Computes several common parameters involved in laying out and rendering text set to this label.
+	// Only vertical margin is considered in r_offset: use get_line_rect to get the horizontal offset
+	// for a given line of text.
+	Size2 size = get_size();
+	Ref<StyleBox> style = theme_cache.normal_style;
+	int line_spacing = settings.is_valid() ? settings->get_line_spacing() : theme_cache.line_spacing;
+
+	float total_h = 0.0;
+	int lines_visible = 0;
+
+	// Get number of lines to fit to the height.
+	for (int64_t i = lines_skipped; i < lines_rid.size(); i++) {
+		total_h += TS->shaped_text_get_size(lines_rid[i]).y + line_spacing;
+		if (total_h > (get_size().height - style->get_minimum_size().height + line_spacing)) {
+			break;
+		}
+		lines_visible++;
+	}
+
+	if (max_lines_visible >= 0 && lines_visible > max_lines_visible) {
+		lines_visible = max_lines_visible;
+	}
+
+	r_line_limit = MIN(lines_rid.size(), lines_visible + lines_skipped);
+
+	// Get real total height.
+	total_h = 0;
+	for (int64_t i = lines_skipped; i < r_line_limit; i++) {
+		total_h += TS->shaped_text_get_size(lines_rid[i]).y + line_spacing;
+	}
+	total_h += style->get_margin(SIDE_TOP) + style->get_margin(SIDE_BOTTOM);
+
+	int vbegin = 0, vsep = 0;
+	if (lines_visible > 0) {
+		switch (vertical_alignment) {
+			case VERTICAL_ALIGNMENT_TOP: {
+				// Nothing.
+			} break;
+			case VERTICAL_ALIGNMENT_CENTER: {
+				vbegin = (size.y - (total_h - line_spacing)) / 2;
+				vsep = 0;
+
+			} break;
+			case VERTICAL_ALIGNMENT_BOTTOM: {
+				vbegin = size.y - (total_h - line_spacing);
+				vsep = 0;
+
+			} break;
+			case VERTICAL_ALIGNMENT_FILL: {
+				vbegin = 0;
+				if (lines_visible > 1) {
+					vsep = (size.y - (total_h - line_spacing)) / (lines_visible - 1);
+				} else {
+					vsep = 0;
+				}
+
+			} break;
+		}
+	}
+
+	r_offset = { 0, style->get_offset().y + vbegin };
+	r_line_spacing = line_spacing + vsep;
+}
+
 PackedStringArray Label::get_configuration_warnings() const {
 	PackedStringArray warnings = Control::get_configuration_warnings();
 
@@ -361,10 +476,7 @@ PackedStringArray Label::get_configuration_warnings() const {
 	}
 
 	if (font.is_valid()) {
-		if (dirty || font_dirty || lines_dirty) {
-			const_cast<Label *>(this)->_shape();
-		}
-
+		_ensure_shaped();
 		const Glyph *glyph = TS->shaped_text_get_glyphs(text_rid);
 		int64_t glyph_count = TS->shaped_text_get_glyph_count(text_rid);
 		for (int64_t i = 0; i < glyph_count; i++) {
@@ -416,22 +528,17 @@ void Label::_notification(int p_what) {
 				}
 			}
 
-			if (dirty || font_dirty || lines_dirty) {
-				_shape();
-			}
+			_ensure_shaped();
 
 			RID ci = get_canvas_item();
 
 			bool has_settings = settings.is_valid();
 
 			Size2 string_size;
-			Size2 size = get_size();
 			Ref<StyleBox> style = theme_cache.normal_style;
-			Ref<Font> font = (has_settings && settings->get_font().is_valid()) ? settings->get_font() : theme_cache.font;
 			Color font_color = has_settings ? settings->get_font_color() : theme_cache.font_color;
 			Color font_shadow_color = has_settings ? settings->get_shadow_color() : theme_cache.font_shadow_color;
 			Point2 shadow_ofs = has_settings ? settings->get_shadow_offset() : theme_cache.font_shadow_offset;
-			int line_spacing = has_settings ? settings->get_line_spacing() : theme_cache.line_spacing;
 			Color font_outline_color = has_settings ? settings->get_outline_color() : theme_cache.font_outline_color;
 			int outline_size = has_settings ? settings->get_outline_size() : theme_cache.font_outline_size;
 			int shadow_outline_size = has_settings ? settings->get_shadow_size() : theme_cache.font_shadow_outline_size;
@@ -440,98 +547,28 @@ void Label::_notification(int p_what) {
 
 			style->draw(ci, Rect2(Point2(0, 0), get_size()));
 
-			float total_h = 0.0;
-			int lines_visible = 0;
-
-			// Get number of lines to fit to the height.
-			for (int64_t i = lines_skipped; i < lines_rid.size(); i++) {
-				total_h += TS->shaped_text_get_size(lines_rid[i]).y + line_spacing;
-				if (total_h > (get_size().height - style->get_minimum_size().height + line_spacing)) {
-					break;
-				}
-				lines_visible++;
-			}
-
-			if (max_lines_visible >= 0 && lines_visible > max_lines_visible) {
-				lines_visible = max_lines_visible;
-			}
-
-			int last_line = MIN(lines_rid.size(), lines_visible + lines_skipped);
 			bool trim_chars = (visible_chars >= 0) && (visible_chars_behavior == TextServer::VC_CHARS_AFTER_SHAPING);
 			bool trim_glyphs_ltr = (visible_chars >= 0) && ((visible_chars_behavior == TextServer::VC_GLYPHS_LTR) || ((visible_chars_behavior == TextServer::VC_GLYPHS_AUTO) && !rtl_layout));
 			bool trim_glyphs_rtl = (visible_chars >= 0) && ((visible_chars_behavior == TextServer::VC_GLYPHS_RTL) || ((visible_chars_behavior == TextServer::VC_GLYPHS_AUTO) && rtl_layout));
 
-			// Get real total height.
+			Vector2 ofs;
+			int line_limit;
+			int line_spacing;
+			get_layout_data(ofs, line_limit, line_spacing);
+
+			int processed_glyphs = 0;
 			int total_glyphs = 0;
-			total_h = 0;
-			for (int64_t i = lines_skipped; i < last_line; i++) {
-				total_h += TS->shaped_text_get_size(lines_rid[i]).y + line_spacing;
+
+			for (int64_t i = lines_skipped; i < line_limit; i++) {
 				total_glyphs += TS->shaped_text_get_glyph_count(lines_rid[i]) + TS->shaped_text_get_ellipsis_glyph_count(lines_rid[i]);
 			}
-			int visible_glyphs = total_glyphs * visible_ratio;
-			int processed_glyphs = 0;
-			total_h += style->get_margin(SIDE_TOP) + style->get_margin(SIDE_BOTTOM);
-
-			int vbegin = 0, vsep = 0;
-			if (lines_visible > 0) {
-				switch (vertical_alignment) {
-					case VERTICAL_ALIGNMENT_TOP: {
-						// Nothing.
-					} break;
-					case VERTICAL_ALIGNMENT_CENTER: {
-						vbegin = (size.y - (total_h - line_spacing)) / 2;
-						vsep = 0;
-
-					} break;
-					case VERTICAL_ALIGNMENT_BOTTOM: {
-						vbegin = size.y - (total_h - line_spacing);
-						vsep = 0;
-
-					} break;
-					case VERTICAL_ALIGNMENT_FILL: {
-						vbegin = 0;
-						if (lines_visible > 1) {
-							vsep = (size.y - (total_h - line_spacing)) / (lines_visible - 1);
-						} else {
-							vsep = 0;
-						}
 
-					} break;
-				}
-			}
+			int visible_glyphs = total_glyphs * visible_ratio;
 
-			Vector2 ofs;
-			ofs.y = style->get_offset().y + vbegin;
-			for (int i = lines_skipped; i < last_line; i++) {
-				Size2 line_size = TS->shaped_text_get_size(lines_rid[i]);
-				ofs.x = 0;
+			for (int i = lines_skipped; i < line_limit; i++) {
+				Vector2 line_offset = get_line_rect(i).position;
+				ofs.x = line_offset.x;
 				ofs.y += TS->shaped_text_get_ascent(lines_rid[i]);
-				switch (horizontal_alignment) {
-					case HORIZONTAL_ALIGNMENT_FILL:
-						if (rtl && autowrap_mode != TextServer::AUTOWRAP_OFF) {
-							ofs.x = int(size.width - style->get_margin(SIDE_RIGHT) - line_size.width);
-						} else {
-							ofs.x = style->get_offset().x;
-						}
-						break;
-					case HORIZONTAL_ALIGNMENT_LEFT: {
-						if (rtl_layout) {
-							ofs.x = int(size.width - style->get_margin(SIDE_RIGHT) - line_size.width);
-						} else {
-							ofs.x = style->get_offset().x;
-						}
-					} break;
-					case HORIZONTAL_ALIGNMENT_CENTER: {
-						ofs.x = int(size.width - line_size.width) / 2;
-					} break;
-					case HORIZONTAL_ALIGNMENT_RIGHT: {
-						if (rtl_layout) {
-							ofs.x = style->get_offset().x;
-						} else {
-							ofs.x = int(size.width - style->get_margin(SIDE_RIGHT) - line_size.width);
-						}
-					} break;
-				}
 
 				const Glyph *glyphs = TS->shaped_text_get_glyphs(lines_rid[i]);
 				int gl_size = TS->shaped_text_get_glyph_count(lines_rid[i]);
@@ -621,7 +658,7 @@ void Label::_notification(int p_what) {
 						}
 					}
 				}
-				ofs.y += TS->shaped_text_get_descent(lines_rid[i]) + vsep + line_spacing;
+				ofs.y += TS->shaped_text_get_descent(lines_rid[i]) + line_spacing;
 			}
 		} break;
 
@@ -637,102 +674,16 @@ void Label::_notification(int p_what) {
 }
 
 Rect2 Label::get_character_bounds(int p_pos) const {
-	if (dirty || font_dirty || lines_dirty) {
-		const_cast<Label *>(this)->_shape();
-	}
-
-	bool has_settings = settings.is_valid();
-	Size2 size = get_size();
-	Ref<StyleBox> style = theme_cache.normal_style;
-	int line_spacing = has_settings ? settings->get_line_spacing() : theme_cache.line_spacing;
-	bool rtl = (TS->shaped_text_get_inferred_direction(text_rid) == TextServer::DIRECTION_RTL);
-	bool rtl_layout = is_layout_rtl();
-
-	float total_h = 0.0;
-	int lines_visible = 0;
-
-	// Get number of lines to fit to the height.
-	for (int64_t i = lines_skipped; i < lines_rid.size(); i++) {
-		total_h += TS->shaped_text_get_size(lines_rid[i]).y + line_spacing;
-		if (total_h > (get_size().height - style->get_minimum_size().height + line_spacing)) {
-			break;
-		}
-		lines_visible++;
-	}
-
-	if (max_lines_visible >= 0 && lines_visible > max_lines_visible) {
-		lines_visible = max_lines_visible;
-	}
-
-	int last_line = MIN(lines_rid.size(), lines_visible + lines_skipped);
-
-	// Get real total height.
-	total_h = 0;
-	for (int64_t i = lines_skipped; i < last_line; i++) {
-		total_h += TS->shaped_text_get_size(lines_rid[i]).y + line_spacing;
-	}
-
-	total_h += style->get_margin(SIDE_TOP) + style->get_margin(SIDE_BOTTOM);
-
-	int vbegin = 0, vsep = 0;
-	if (lines_visible > 0) {
-		switch (vertical_alignment) {
-			case VERTICAL_ALIGNMENT_TOP: {
-				// Nothing.
-			} break;
-			case VERTICAL_ALIGNMENT_CENTER: {
-				vbegin = (size.y - (total_h - line_spacing)) / 2;
-				vsep = 0;
-
-			} break;
-			case VERTICAL_ALIGNMENT_BOTTOM: {
-				vbegin = size.y - (total_h - line_spacing);
-				vsep = 0;
-
-			} break;
-			case VERTICAL_ALIGNMENT_FILL: {
-				vbegin = 0;
-				if (lines_visible > 1) {
-					vsep = (size.y - (total_h - line_spacing)) / (lines_visible - 1);
-				} else {
-					vsep = 0;
-				}
-
-			} break;
-		}
-	}
+	_ensure_shaped();
 
 	Vector2 ofs;
-	ofs.y = style->get_offset().y + vbegin;
-	for (int i = lines_skipped; i < last_line; i++) {
-		Size2 line_size = TS->shaped_text_get_size(lines_rid[i]);
-		ofs.x = 0;
-		switch (horizontal_alignment) {
-			case HORIZONTAL_ALIGNMENT_FILL:
-				if (rtl && autowrap_mode != TextServer::AUTOWRAP_OFF) {
-					ofs.x = int(size.width - style->get_margin(SIDE_RIGHT) - line_size.width);
-				} else {
-					ofs.x = style->get_offset().x;
-				}
-				break;
-			case HORIZONTAL_ALIGNMENT_LEFT: {
-				if (rtl_layout) {
-					ofs.x = int(size.width - style->get_margin(SIDE_RIGHT) - line_size.width);
-				} else {
-					ofs.x = style->get_offset().x;
-				}
-			} break;
-			case HORIZONTAL_ALIGNMENT_CENTER: {
-				ofs.x = int(size.width - line_size.width) / 2;
-			} break;
-			case HORIZONTAL_ALIGNMENT_RIGHT: {
-				if (rtl_layout) {
-					ofs.x = style->get_offset().x;
-				} else {
-					ofs.x = int(size.width - style->get_margin(SIDE_RIGHT) - line_size.width);
-				}
-			} break;
-		}
+	int line_limit;
+	int line_spacing;
+	get_layout_data(ofs, line_limit, line_spacing);
+
+	for (int i = lines_skipped; i < line_limit; i++) {
+		Rect2 line_rect = get_line_rect(i);
+		ofs.x = line_rect.position.x;
 		int v_size = TS->shaped_text_get_glyph_count(lines_rid[i]);
 		const Glyph *glyphs = TS->shaped_text_get_glyphs(lines_rid[i]);
 
@@ -746,22 +697,19 @@ Rect2 Label::get_character_bounds(int p_pos) const {
 					}
 					Rect2 rect;
 					rect.position = ofs + Vector2(gl_off, 0);
-					rect.size = Vector2(advance, TS->shaped_text_get_size(lines_rid[i]).y);
+					rect.size = Vector2(advance, line_rect.size.y);
 					return rect;
 				}
 			}
 			gl_off += glyphs[j].advance * glyphs[j].repeat;
 		}
-		ofs.y += TS->shaped_text_get_ascent(lines_rid[i]) + TS->shaped_text_get_descent(lines_rid[i]) + vsep + line_spacing;
+		ofs.y += TS->shaped_text_get_ascent(lines_rid[i]) + TS->shaped_text_get_descent(lines_rid[i]) + line_spacing;
 	}
 	return Rect2();
 }
 
 Size2 Label::get_minimum_size() const {
-	// don't want to mutable everything
-	if (dirty || font_dirty || lines_dirty) {
-		const_cast<Label *>(this)->_shape();
-	}
+	_ensure_shaped();
 
 	Size2 min_size = minsize;
 
@@ -798,10 +746,7 @@ int Label::get_line_count() const {
 	if (!is_inside_tree()) {
 		return 1;
 	}
-	if (dirty || font_dirty || lines_dirty) {
-		const_cast<Label *>(this)->_shape();
-	}
-
+	_ensure_shaped();
 	return lines_rid.size();
 }
 
@@ -1104,10 +1049,7 @@ int Label::get_max_lines_visible() const {
 }
 
 int Label::get_total_character_count() const {
-	if (dirty || font_dirty || lines_dirty) {
-		const_cast<Label *>(this)->_shape();
-	}
-
+	_ensure_shaped();
 	return xl_text.length();
 }
 
diff --git a/scene/gui/label.h b/scene/gui/label.h
index e0ebca944a..2576d21c33 100644
--- a/scene/gui/label.h
+++ b/scene/gui/label.h
@@ -91,11 +91,16 @@ private:
 		int font_shadow_outline_size;
 	} theme_cache;
 
+	void _ensure_shaped() const;
 	void _update_visible();
 	void _shape();
 	void _invalidate();
 
 protected:
+	RID get_line_rid(int p_line) const;
+	Rect2 get_line_rect(int p_line) const;
+	void get_layout_data(Vector2 &r_offset, int &r_line_limit, int &r_line_spacing) const;
+
 	void _notification(int p_what);
 	static void _bind_methods();
 #ifndef DISABLE_DEPRECATED