Merge pull request #5177 from vnen/string-subsequence

Add subsequence search to tools

9 files changed, 77 insertions, 8 deletions

diff --git a/core/ustring.cpp b/core/ustring.cpp
index a039ba11cd..309b9e08fa 100644
--- a/core/ustring.cpp
+++ b/core/ustring.cpp
@@ -2752,6 +2752,50 @@ bool String::begins_with(const char* p_string) const {
 
 }
 
+bool String::is_subsequence_of(const String& p_string) const {
+
+	return _base_is_subsequence_of(p_string, false);
+}
+
+bool String::is_subsequence_ofi(const String& p_string) const {
+
+	return _base_is_subsequence_of(p_string, true);
+}
+
+bool String::_base_is_subsequence_of(const String& p_string, bool case_insensitive) const {
+
+	int len=length();
+	if (len == 0) {
+		// Technically an empty string is subsequence of any string
+		return true;
+	}
+
+	if (len > p_string.length()) {
+		return false;
+	}
+
+	const CharType *src = &operator[](0);
+	const CharType *tgt = &p_string[0];
+
+	for (;*src && *tgt;tgt++) {
+		bool match = false;
+		if (case_insensitive) {
+			CharType srcc = _find_lower(*src);
+			CharType tgtc = _find_lower(*tgt);
+			match = srcc == tgtc;
+		} else {
+			match = *src == *tgt;
+		}
+		if (match) {
+			src++;
+			if(!*src) {
+				return true;
+			}
+		}
+	}
+
+	return false;
+}
 
 static bool _wildcard_match(const CharType* p_pattern, const CharType* p_string,bool p_case_sensitive) {
 	switch (*p_pattern) {
diff --git a/core/ustring.h b/core/ustring.h
index e03f74f506..fddb77b040 100644
--- a/core/ustring.h
+++ b/core/ustring.h
@@ -66,6 +66,7 @@ class String : public Vector<CharType> {
 	void copy_from(const char *p_cstr);
 	void copy_from(const CharType* p_cstr, int p_clip_to=-1);
 	void copy_from(const CharType& p_char);
+	bool _base_is_subsequence_of(const String& p_string, bool case_insensitive) const;
 
 
 public:
@@ -122,6 +123,8 @@ public:
 	bool begins_with(const String& p_string) const;
 	bool begins_with(const char* p_string) const;
 	bool ends_with(const String& p_string) const;
+	bool is_subsequence_of(const String& p_string) const;
+	bool is_subsequence_ofi(const String& p_string) const;
 	String replace_first(String p_key,String p_with) const;
 	String replace(String p_key,String p_with) const;
 	String replacen(String p_key,String p_with) const;
diff --git a/core/variant_call.cpp b/core/variant_call.cpp
index cc2d15b88c..94ab93d55c 100644
--- a/core/variant_call.cpp
+++ b/core/variant_call.cpp
@@ -247,6 +247,8 @@ static void _call_##m_type##_##m_method(Variant& r_ret,Variant& p_self,const Var
 	VCALL_LOCALMEM1R(String,matchn);
 	VCALL_LOCALMEM1R(String,begins_with);
 	VCALL_LOCALMEM1R(String,ends_with);
+	VCALL_LOCALMEM1R(String,is_subsequence_of);
+	VCALL_LOCALMEM1R(String,is_subsequence_ofi);
 	VCALL_LOCALMEM2R(String,replace);
 	VCALL_LOCALMEM2R(String,replacen);
 	VCALL_LOCALMEM2R(String,insert);
@@ -1269,6 +1271,8 @@ _VariantCall::addfunc(Variant::m_vtype,Variant::m_ret,_SCS(#m_method),VCALL(m_cl
 	ADDFUNC1(STRING,BOOL,String,matchn,STRING,"expr",varray());
 	ADDFUNC1(STRING,BOOL,String,begins_with,STRING,"text",varray());
 	ADDFUNC1(STRING,BOOL,String,ends_with,STRING,"text",varray());
+	ADDFUNC1(STRING,BOOL,String,is_subsequence_of,STRING,"text",varray());
+	ADDFUNC1(STRING,BOOL,String,is_subsequence_ofi,STRING,"text",varray());
 
 	ADDFUNC2(STRING,STRING,String,replace,STRING,"what",STRING,"forwhat",varray());
 	ADDFUNC2(STRING,STRING,String,replacen,STRING,"what",STRING,"forwhat",varray());
diff --git a/doc/base/classes.xml b/doc/base/classes.xml
index 8a75ba5c87..0d8f7eecdd 100644
--- a/doc/base/classes.xml
+++ b/doc/base/classes.xml
@@ -37271,6 +37271,24 @@ This method controls whether the position between two cached points is interpola
 			If the string is a path to a file or directory, return true if the path is relative.
 			</description>
 		</method>
+		<method name="is_subsequence_of">
+			<return type="bool">
+			</return>
+			<argument index="0" name="text" type="String">
+			</argument>
+			<description>
+			Checked whether this string is a subsequence of the given string.
+			</description>
+		</method>
+		<method name="is_subsequence_ofi">
+			<return type="bool">
+			</return>
+			<argument index="0" name="text" type="String">
+			</argument>
+			<description>
+			Checked whether this string is a subsequence of the given string, without considering case.
+			</description>
+		</method>
 		<method name="is_valid_float">
 			<return type="bool">
 			</return>
diff --git a/tools/editor/create_dialog.cpp b/tools/editor/create_dialog.cpp
index b6137ddac0..5275e1beeb 100644
--- a/tools/editor/create_dialog.cpp
+++ b/tools/editor/create_dialog.cpp
@@ -103,7 +103,7 @@ void CreateDialog::add_type(const String& p_type,HashMap<String,TreeItem*>& p_ty
 		item->set_selectable(0,false);
 	} else {
 
-		if (!*to_select && (search_box->get_text()=="" || p_type.findn(search_box->get_text())!=-1)) {
+		if (!*to_select && (search_box->get_text().is_subsequence_ofi(p_type))) {
 			*to_select=item;
 		}
 
@@ -172,7 +172,7 @@ void CreateDialog::_update_search() {
 			bool found=false;
 			String type=I->get();
 			while(type!="" && ObjectTypeDB::is_type(type,base_type) && type!=base_type) {
-				if (type.findn(search_box->get_text())!=-1) {
+				if (search_box->get_text().is_subsequence_ofi(type)) {
 
 					found=true;
 					break;
@@ -194,7 +194,7 @@ void CreateDialog::_update_search() {
 			const Vector<EditorData::CustomType> &ct = EditorNode::get_editor_data().get_custom_types()[type];
 			for(int i=0;i<ct.size();i++) {
 
-				bool show = search_box->get_text()=="" || ct[i].name.findn(search_box->get_text())!=-1;
+				bool show = search_box->get_text().is_subsequence_ofi(ct[i].name);
 
 				if (!show)
 					continue;
diff --git a/tools/editor/editor_help.cpp b/tools/editor/editor_help.cpp
index ac9feacd46..0b60db5ee3 100644
--- a/tools/editor/editor_help.cpp
+++ b/tools/editor/editor_help.cpp
@@ -453,7 +453,7 @@ void EditorHelpIndex::_update_class_list() {
 			String type = E->key();
 
 			while(type != "") {
-				if (type.findn(filter)!=-1) {
+				if (filter.is_subsequence_ofi(type)) {
 
 					if (to_select.empty()) {
 						to_select = type;
diff --git a/tools/editor/property_editor.cpp b/tools/editor/property_editor.cpp
index 7dfcf88e2c..763734f035 100644
--- a/tools/editor/property_editor.cpp
+++ b/tools/editor/property_editor.cpp
@@ -2812,7 +2812,7 @@ void PropertyEditor::update_tree() {
 			if (capitalize_paths)
 				cat = cat.capitalize();
 
-			if (cat.findn(filter)==-1 && name.findn(filter)==-1)
+			if (!filter.is_subsequence_ofi(cat) && !filter.is_subsequence_ofi(name))
 				continue;
 		}
 
diff --git a/tools/editor/quick_open.cpp b/tools/editor/quick_open.cpp
index 72059c264f..fc2a2241ab 100644
--- a/tools/editor/quick_open.cpp
+++ b/tools/editor/quick_open.cpp
@@ -126,7 +126,7 @@ void EditorQuickOpen::_parse_fs(EditorFileSystemDirectory *efsd) {
 			path+="/";
 		if (path!="res://") {
 			path=path.substr(6,path.length());
-			if (path.findn(search_box->get_text())!=-1) {
+			if (search_box->get_text().is_subsequence_ofi(path)) {
 				TreeItem *ti = search_options->create_item(root);
 				ti->set_text(0,path);
 				Ref<Texture> icon = get_icon("folder","FileDialog");
@@ -138,7 +138,7 @@ void EditorQuickOpen::_parse_fs(EditorFileSystemDirectory *efsd) {
 
 		String file = efsd->get_file_path(i);
 		file=file.substr(6,file.length());
-		if (ObjectTypeDB::is_type(efsd->get_file_type(i),base_type) && (search_box->get_text()=="" || file.findn(search_box->get_text())!=-1)) {
+		if (ObjectTypeDB::is_type(efsd->get_file_type(i),base_type) && (search_box->get_text().is_subsequence_ofi(file))) {
 
 			TreeItem *ti = search_options->create_item(root);
 			ti->set_text(0,file);
diff --git a/tools/editor/scene_tree_editor.cpp b/tools/editor/scene_tree_editor.cpp
index 65e731dd4d..2de6fc5cf2 100644
--- a/tools/editor/scene_tree_editor.cpp
+++ b/tools/editor/scene_tree_editor.cpp
@@ -428,7 +428,7 @@ bool SceneTreeEditor::_add_nodes(Node *p_node,TreeItem *p_parent) {
 		item->set_as_cursor(0);
 	}
 
-	bool keep= ( filter==String() || String(p_node->get_name()).to_lower().find(filter.to_lower())!=-1 );
+	bool keep= (filter.is_subsequence_ofi(String(p_node->get_name())));
 
 	for (int i=0;i<p_node->get_child_count();i++) {