Add purple_strmatches and move purple_person_matches and purple_contact_info_matches to it

This uses a naive algorithm to do fuzzy matching but appears to be good enough
for now. We can look at something more complicated later if the performance of
this is bad enough.

Testing Done:
Ran the unit tests and tested the search in the contact list.

Bugs closed: PIDGIN-17737

Reviewed at https://reviews.imfreedom.org/r/2212/

7 files changed, 163 insertions, 10 deletions

diff --git a/libpurple/purplecontactinfo.c b/libpurple/purplecontactinfo.c
index 4d73ee3fd2..d158229d45 100644
--- a/libpurple/purplecontactinfo.c
+++ b/libpurple/purplecontactinfo.c
@@ -810,26 +810,20 @@ purple_contact_info_matches(PurpleContactInfo *info, const char *needle) {
 
 	priv = purple_contact_info_get_instance_private(info);
 
-	if(!purple_strempty(priv->id)) {
-		if(strstr(priv->id, needle) != NULL) {
-			return TRUE;
-		}
-	}
-
 	if(!purple_strempty(priv->username)) {
-		if(strstr(priv->username, needle) != NULL) {
+		if(purple_strmatches(needle, priv->username)) {
 			return TRUE;
 		}
 	}
 
 	if(!purple_strempty(priv->alias)) {
-		if(strstr(priv->alias, needle) != NULL) {
+		if(purple_strmatches(needle, priv->alias)) {
 			return TRUE;
 		}
 	}
 
 	if(!purple_strempty(priv->display_name)) {
-		if(strstr(priv->display_name, needle) != NULL) {
+		if(purple_strmatches(needle, priv->display_name)) {
 			return TRUE;
 		}
 	}
diff --git a/libpurple/purplecontactinfo.h b/libpurple/purplecontactinfo.h
index e1bfc3ea7d..e063307a8d 100644
--- a/libpurple/purplecontactinfo.h
+++ b/libpurple/purplecontactinfo.h
@@ -361,6 +361,8 @@ int purple_contact_info_compare(PurpleContactInfo *a, PurpleContactInfo *b);
  * @needle: (nullable): The string to match.
  *
  * This will determine if the alias, display name, or username matches @needle.
+ * The id is ignored because generally it is a UUID or hex string which will
+ * give very confusing results to end users.
  *
  * If @needle is %NULL or empty string, %TRUE will be returned.
  *
diff --git a/libpurple/purpleperson.c b/libpurple/purpleperson.c
index 8545d653e0..571b926747 100644
--- a/libpurple/purpleperson.c
+++ b/libpurple/purpleperson.c
@@ -593,7 +593,7 @@ purple_person_matches(PurplePerson *person, const char *needle) {
 
 	/* Check if the person's alias matches. */
 	if(!purple_strempty(person->alias)) {
-		if(strstr(person->alias, needle) != NULL) {
+		if(purple_strmatches(needle, person->alias)) {
 			return TRUE;
 		}
 	}
diff --git a/libpurple/tests/meson.build b/libpurple/tests/meson.build
index f2d1460749..a38b868872 100644
--- a/libpurple/tests/meson.build
+++ b/libpurple/tests/meson.build
@@ -23,6 +23,7 @@ PROGS = [
     'protocol_xfer',
     'purplepath',
     'queued_output_stream',
+    'str',
     'tags',
     'util',
     'whiteboard_manager',
diff --git a/libpurple/tests/test_str.c b/libpurple/tests/test_str.c
new file mode 100644
index 0000000000..8b382477f4
--- /dev/null
+++ b/libpurple/tests/test_str.c
@@ -0,0 +1,76 @@
+/*
+ * Purple - Internet Messaging Library
+ * Copyright (C) Pidgin Developers <devel@pidgin.im>
+ *
+ * Purple is the legal property of its developers, whose names are too numerous
+ * to list here.  Please refer to the COPYRIGHT file distributed with this
+ * source distribution.
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, see <https://www.gnu.org/licenses/>.
+ */
+
+#include <glib.h>
+
+#include <purple.h>
+
+/******************************************************************************
+ * Tests
+ *****************************************************************************/
+static void
+test_purple_strmatches_null(void) {
+	g_assert_false(purple_strmatches("abc", NULL));
+}
+
+static void
+test_purple_strmatches_adjacent(void) {
+	g_assert_true(purple_strmatches("abc", "abc"));
+	g_assert_true(purple_strmatches("abc", "123abc"));
+	g_assert_true(purple_strmatches("abc", "abcxyz"));
+	g_assert_true(purple_strmatches("abc", "123abcxyz"));
+}
+
+static void
+test_purple_strmatches_sparse(void) {
+	g_assert_true(purple_strmatches("adf", "abcdefg"));
+	g_assert_true(purple_strmatches("jon", "john"));
+	g_assert_true(purple_strmatches("lce", "alice"));
+}
+
+static void
+test_purple_strmatches_iterates_correctly(void) {
+	/* These tests are to make sure that we are iterating both the pattern and
+	 * the string to check properly.
+	 */
+
+	/* since we have 2 e's in the pattern, this test makes sure that we iterate
+	 * past the first matching e in the string we're checking.
+	 */
+	g_assert_false(purple_strmatches("beer", "berry"));
+}
+
+/******************************************************************************
+ * Public API
+ *****************************************************************************/
+gint
+main(gint argc, gchar **argv) {
+	g_test_init(&argc, &argv, NULL);
+
+	g_test_add_func("/strmatches/null", test_purple_strmatches_null);
+	g_test_add_func("/strmatches/adjacent", test_purple_strmatches_adjacent);
+	g_test_add_func("/strmatches/sparse", test_purple_strmatches_sparse);
+	g_test_add_func("/strmatches/iterates_correctly",
+	                test_purple_strmatches_iterates_correctly);
+
+	return g_test_run();
+}
diff --git a/libpurple/util.c b/libpurple/util.c
index def164319e..c4c7660dad 100644
--- a/libpurple/util.c
+++ b/libpurple/util.c
@@ -404,6 +404,68 @@ purple_str_wipe(gchar *str)
 	g_free(str);
 }
 
+gboolean
+purple_strmatches(const char *pattern, const char *str) {
+	char *normal_pattern = NULL;
+	char *normal_str = NULL;
+	char *cmp_pattern = NULL;
+	char *cmp_str = NULL;
+	char *idx_pattern = NULL;
+	char *idx_str = NULL;
+
+	g_return_val_if_fail(pattern != NULL, FALSE);
+
+	/* Short circuit on NULL and empty string. */
+	if(purple_strempty(str)) {
+		return FALSE;
+	}
+
+	normal_pattern = g_utf8_normalize(pattern, -1, G_NORMALIZE_ALL);
+	cmp_pattern = g_utf8_casefold(normal_pattern, -1);
+	g_free(normal_pattern);
+
+	normal_str = g_utf8_normalize(str, -1, G_NORMALIZE_ALL);
+	cmp_str = g_utf8_casefold(normal_str, -1);
+	g_free(normal_str);
+
+	idx_pattern = cmp_pattern;
+	idx_str = cmp_str;
+
+	/* I know while(TRUE)'s suck, but the alternative would be a multi-line for
+	 * loop that wouldn't have the additional comments, which is much better
+	 * IMHO. -- GK 2023-01-24.
+	 */
+	while(TRUE) {
+		gunichar character = g_utf8_get_char(idx_pattern);
+
+		/* If we've reached the end of the pattern, we're done. */
+		if(character == 0) {
+			break;
+		}
+
+		idx_str = g_utf8_strchr(idx_str, -1, character);
+		if(idx_str == NULL) {
+			g_free(cmp_pattern);
+			g_free(cmp_str);
+
+			return FALSE;
+		}
+
+		/* We found the current character in pattern, so move to the next. */
+		idx_pattern = g_utf8_next_char(idx_pattern);
+
+		/* move idx_str to the next character as well, because the current
+		 * character has already been matched.
+		 */
+		idx_str = g_utf8_next_char(idx_str);
+	};
+
+	g_free(cmp_pattern);
+	g_free(cmp_str);
+
+	return TRUE;
+}
+
 /**************************************************************************
  * URI/URL Functions
  **************************************************************************/
diff --git a/libpurple/util.h b/libpurple/util.h
index e08b98f04c..00058c5ea1 100644
--- a/libpurple/util.h
+++ b/libpurple/util.h
@@ -410,6 +410,24 @@ char *purple_str_seconds_to_string(guint sec);
  */
 void purple_str_wipe(gchar *str);
 
+/**
+ * purple_strmatches:
+ * @pattern: The pattern to search for.
+ * @str: The string to check.
+ *
+ * Checks if @pattern occurs in sequential order in @str in a caseless fashion,
+ * ignoring characters in between.
+ *
+ * For example, if @pattern was `Pg` and @str was `Pidgin`, this will return
+ * %TRUE.
+ *
+ * Returns: %TRUE if @pattern occurs in sequential order in @str, %FALSE
+ *          otherwise.
+ *
+ * Since: 3.0.0
+ */
+gboolean purple_strmatches(const char *pattern, const char *str);
+
 /**************************************************************************/
 /* URI/URL Functions                                                      */
 /**************************************************************************/