Merge lp:~desrt/indicator-appmenu/hud-performance into lp:indicator-appmenu/0.4

[Allison Lortie]

Improve hud-service performance and search result quality by substantially reworking the core distance algorithm and the needle/haystack assignment algorithm.

[Ted Gould (ted)]

A couple of non-critical comments:

* Next time please use move for things like the schemas as then diffs are tracked on them which makes reviewing them much easier.

* I think the "magic 32" should probably be a #define just so that if someone changes it it will be changed everywhere. For instance, changing it in _new() could cause an assert failure further down the road.

* A comment on hud_token_list_distance_slow () on why the assert isn't insane would be good :-)

* Love the test :-)

review: Approve

[lp:~desrt/indicator-appmenu/hud-performance]

212. By Allison Lortie on 2012-04-03

Adjustments for Ted's review comments.

213. By Allison Lortie on 2012-04-03

HudWindowSource: fix a couple of leaks

 - don't leak icon name while changing windows (fixes lp:972354)

 - don't leak the collector on finalize (which never happens)

=== modified file 'configure.ac'
--- configure.ac	2012-03-28 23:37:14 +0000
+++ configure.ac	2012-04-03 12:30:26 +0000
@@ -222,7 +222,7 @@
 
 GETTEXT_PACKAGE=indicator-appmenu
 
-IT_PROG_INTLTOOL([0.41.0])
+IT_PROG_INTLTOOL([0.50.2])
 
 AM_GNU_GETTEXT([external])
 AM_GNU_GETTEXT_VERSION([0.17])

=== modified file 'data/Makefile.am'
--- data/Makefile.am	2012-01-24 14:24:30 +0000
+++ data/Makefile.am	2012-04-03 12:30:26 +0000
@@ -1,13 +1,8 @@
-
-gsettings_in_files = \
-    com.canonical.indicator.appmenu.gschema.xml.in \
-    com.canonical.indicator.appmenu.hud.gschema.xml.in \
-    com.canonical.indicator.appmenu.hud.search.gschema.xml.in
-
 gsettings_SCHEMAS = \
-	$(gsettings_in_files:.xml.in=.xml)
+    com.canonical.indicator.appmenu.gschema.xml \
+    com.canonical.indicator.appmenu.hud.gschema.xml \
+    com.canonical.indicator.appmenu.hud.search.gschema.xml
 
-@INTLTOOL_XML_NOMERGE_RULE@
 @GSETTINGS_RULES@
 
 dbus_servicesdir = $(DBUSSERVICEDIR)
@@ -18,10 +13,7 @@
 
 EXTRA_DIST = \
 	$(dbus_services_DATA:.service=.service.in) \
-	$(gsettings_in_files)
+	$(gsettings_SCHEMAS)
 
 CLEANFILES = \
-	$(dbus_services_DATA) \
-	$(gsettings_SCHEMAS:.xml=.valid) \
-	$(gsettings_SCHEMAS)
-
+	$(dbus_services_DATA)

=== added file 'data/com.canonical.indicator.appmenu.gschema.xml'
--- data/com.canonical.indicator.appmenu.gschema.xml	1970-01-01 00:00:00 +0000
+++ data/com.canonical.indicator.appmenu.gschema.xml	2012-04-03 12:30:26 +0000
@@ -0,0 +1,18 @@
+<?xml version='1.0' encoding='UTF-8'?>
+
+<schemalist>
+  <enum id='menu-enum'>
+    <value value='0' nick='global'/>
+    <value value='1' nick='locally-integrated'/>
+  </enum>
+
+  <schema path='/com/canonical/indicator/appmenu/' id='com.canonical.indicator.appmenu' gettext-domain='indicator-appmenu'>
+    <key name='menu-mode' enum='menu-enum'>
+      <default>'global'</default>
+      <summary>Where the menus displayed</summary>
+      <description>
+        Controls the menu display location. TODO: add more
+      </description>
+    </key>
+  </schema>
+</schemalist>

=== removed file 'data/com.canonical.indicator.appmenu.gschema.xml.in'
--- data/com.canonical.indicator.appmenu.gschema.xml.in	2012-01-17 17:38:12 +0000
+++ data/com.canonical.indicator.appmenu.gschema.xml.in	1970-01-01 00:00:00 +0000
@@ -1,15 +0,0 @@
-<schemalist>
-	<enum id="menu-enum">
-		<value nick="global" value="0" />
-		<value nick="locally-integrated" value="1" />
-	</enum>
-	<schema id="com.canonical.indicator.appmenu" path="/com/canonical/indicator/appmenu/" gettext-domain="indicator-appmenu">
-		<key name="menu-mode" enum="menu-enum">
-			<default>'global'</default>
-			<_summary>Where the menus displayed</_summary>
-			<_description>
-			  Controls the menu display location.  TODO: add more
-			</_description>
-		</key>
-	</schema>
-</schemalist>

=== added file 'data/com.canonical.indicator.appmenu.hud.gschema.xml'
--- data/com.canonical.indicator.appmenu.hud.gschema.xml	1970-01-01 00:00:00 +0000
+++ data/com.canonical.indicator.appmenu.hud.gschema.xml	2012-04-03 12:30:26 +0000
@@ -0,0 +1,16 @@
+<?xml version='1.0' encoding='UTF-8'?>
+
+<schemalist>
+  <schema path='/com/canonical/indicator/appmenu/hud/' id='com.canonical.indicator.appmenu.hud' gettext-domain='indicator-appmenu'>
+    <key type='b' name='store-usage-data'>
+      <default>true</default>
+      <summary>Whether to store usage data</summary>
+      <description>
+        When the HUD executes operations it stores the execution in order to
+        make the future results better. Some users could choose to not want
+        this data to be stored. If that is the case they should disable this
+        property.
+      </description>
+    </key>
+  </schema>
+</schemalist>

=== removed file 'data/com.canonical.indicator.appmenu.hud.gschema.xml.in'
--- data/com.canonical.indicator.appmenu.hud.gschema.xml.in	2012-01-17 17:38:12 +0000
+++ data/com.canonical.indicator.appmenu.hud.gschema.xml.in	1970-01-01 00:00:00 +0000
@@ -1,14 +0,0 @@
-<schemalist>
-	<schema id="com.canonical.indicator.appmenu.hud" path="/com/canonical/indicator/appmenu/hud/" gettext-domain="indicator-appmenu">
-		<key name="store-usage-data" type="b">
-			<default>true</default>
-			<_summary>Whether to store usage data</_summary>
-			<_description>
-			  When the HUD executes operations it stores the execution in
-			  order to make the future results better.  Some users could choose
-			  to not want this data to be stored.  If that is the case they
-			  should disable this property.
-			</_description>
-		</key>
-	</schema>
-</schemalist>

=== added file 'data/com.canonical.indicator.appmenu.hud.search.gschema.xml'
--- data/com.canonical.indicator.appmenu.hud.search.gschema.xml	1970-01-01 00:00:00 +0000
+++ data/com.canonical.indicator.appmenu.hud.search.gschema.xml	2012-04-03 12:30:26 +0000
@@ -0,0 +1,72 @@
+<?xml version='1.0' encoding='UTF-8'?>
+
+<schemalist>
+  <schema path='/com/canonical/indicator/appmenu/hud/search/'
+          id='com.canonical.indicator.appmenu.hud.search'
+          gettext-domain='indicator-appmenu'>
+    <key type='u' name='indicator-penalty'>
+      <default>50</default>
+      <summary>The penalty given to a menu item being in an indicator</summary>
+      <description>
+        In order to have the application's menu items appear higher in the search results a slight penalty is
+        given to the indicator menu items. This value represents the percentage of that penalty so a value of
+        '50' is a 50% additional to the calculated distance.
+      </description>
+    </key>
+
+    <key type='u' name='add-penalty'>
+      <default>10</default>
+      <summary>Penalty for extra characters added to the search</summary>
+      <description>
+        The penalty for each extra character in the search string that does not appear in the text of a menu
+        item.
+
+        This penalty would be applied if the user typed "fiile" when searching against the menu item "File", for
+        example.
+      </description>
+    </key>
+
+    <key type='u' name='drop-penalty'>
+      <default>10</default>
+      <summary>Penalty applied if a character is dropped</summary>
+      <description>
+        The penalty for each character dropped from the search string, as compared with the text of a menu item.
+        This only applies to missing characters that are not at the end of the search term.
+
+        This penalty would be applied if the user typed "fle" when searching against the menu item "File", for
+        example.
+      </description>
+    </key>
+
+    <key type='u' name='end-drop-penalty'>
+      <default>1</default>
+      <summary>Penalty applied if a character is dropped from the end</summary>
+      <description>
+        The penalty for each missing character at the end of a search term.
+
+        This penalty would be applied if the user typed "fil" when searching against the menu item "File", for
+        example.
+      </description>
+    </key>
+
+    <key type='u' name='swap-penalty'>
+      <default>15</default>
+      <summary>Penalty applied when the characters are not the same</summary>
+      <description>
+        The penalty for each substituted character in the search term.
+
+        The penalty would be applied if the user typed "fike" when searching against the menu item "File", for
+        example.
+      </description>
+    </key>
+
+    <key type='u' name='max-distance'>
+      <default>30</default>
+      <summary>The highest distance value that is shown in the results</summary>
+      <description>
+        After the distances are calculated (including the indicator penalty) then all values above this max are
+        dropped. This means that the history for those entries aren't looked up as well.
+      </description>
+    </key>
+  </schema>
+</schemalist>

=== removed file 'data/com.canonical.indicator.appmenu.hud.search.gschema.xml.in'
--- data/com.canonical.indicator.appmenu.hud.search.gschema.xml.in	2012-03-03 13:39:53 +0000
+++ data/com.canonical.indicator.appmenu.hud.search.gschema.xml.in	1970-01-01 00:00:00 +0000
@@ -1,90 +0,0 @@
-<schemalist>
-	<schema id="com.canonical.indicator.appmenu.hud.search" path="/com/canonical/indicator/appmenu/hud/search/" gettext-domain="indicator-appmenu">
-		<key name="indicator-penalty" type="u">
-			<default>50</default>
-			<_summary>The penalty given to a menu item being in an indicator</_summary>
-			<_description>
-				In order to have the application's menu items appear higher
-				in the search results a slight penalty is given to the indicator
-				menu items.  This value represents then percentage of that penalty
-				so a value of '50' is a 50% additional to the calculated distance.
-			</_description>
-		</key>
-		<key name="add-penalty" type="u">
-			<default>10</default>
-			<_summary>Penalty for extra characters added to the search</_summary>
-			<_description>
-				Penalty applied for extra characters that are added on the end of
-				the string that are not related to the source string.
-			</_description>
-		</key>
-		<key name="add-penalty-pre" type="u">
-			<default>1</default>
-			<_summary>Penalty for extra characters added to the search before the length of the search string</_summary>
-			<_description>
-				Extra characters that occur before the length of the search string
-				could cover them get this penalty.  In the case of "return" and
-				a search string of "turn" the 'r' and the 'e' would get hit with
-				this penalty.
-			</_description>
-		</key>
-		<key name="drop-penalty" type="u">
-			<default>10</default>
-			<_summary>Penalty applied if a character is dropped</_summary>
-			<_description>
-				The penalty applied for characters that were dropped off the end
-				of the search string compared to the tested string.  This is mostly
-				used for seeding and creating a max gradient on the edge of the
-				matrix, as mostly dropped single characters are covered by the
-				'drop-penalty-end' value.
-			</_description>
-		</key>
-		<key name="drop-penalty-end" type="u">
-			<default>10</default>
-			<_summary>Penalty applied if a character is dropped after the search string length</_summary>
-			<_description>
-				Drop penalty that is added to characters that are longer than the
-				current search string.  So for a search string of "add" and a source
-				string of "added" there would be drop end penalties for both 'e' and
-				'd'.
-			</_description>
-		</key>
-		<key name="transpose-penalty" type="u">
-			<default>10</default>
-			<_summary>Penalty applied when characters are transposed</_summary>
-			<_description>
-				When two characters are transposed this penalty is applied.  This is
-				for values like "ea" when the correct value is "ae".  This penalty should
-				be less than twice the swap penalty to have any effect.
-			</_description>
-		</key>
-		<key name="swap-penalty" type="u">
-			<default>10</default>
-			<_summary>Penalty applied when the characters are not the same</_summary>
-			<_description>
-				When two characters don't match at all this is the penalty
-				that is given.  This should probably be the highest penalty
-				in the set of all the values.
-			</_description>
-		</key>
-		<key name="swap-penalty-case" type="u">
-			<default>1</default>
-			<_summary>The swap penalty when the swap is a case change</_summary>
-			<_description>
-				While not strictly a swap, this value allows for penalizing
-				the search slightly when the only difference between the
-				characters is in its case.  For instance, 'c' vs. 'C'.
-			</_description>
-		</key>
-		<key name="max-distance" type="u">
-			<default>30</default>
-			<_summary>The highest distance value that is shown in the results</_summary>
-			<_description>
-				After the distances are calculated (including the indicator
-				penalty) then all values above this max are dropped.  This
-				means that the history for those entries aren't looked up
-				as well.
-			</_description>
-		</key>
-	</schema>
-</schemalist>

=== modified file 'po/POTFILES.in'
--- po/POTFILES.in	2012-03-16 14:48:19 +0000
+++ po/POTFILES.in	2012-04-03 12:30:26 +0000
@@ -1,7 +1,6 @@
-data/com.canonical.indicator.appmenu.gschema.xml.in
-data/com.canonical.indicator.appmenu.hud.gschema.xml.in
-data/com.canonical.indicator.appmenu.hud.search.gschema.xml.in
-src/distance.c
+data/com.canonical.indicator.appmenu.gschema.xml
+data/com.canonical.indicator.appmenu.hud.gschema.xml
+data/com.canonical.indicator.appmenu.hud.search.gschema.xml
 src/dump-app-info.c
 src/gdk-get-func.c
 src/hudappindicatorsource.c
@@ -18,6 +17,7 @@
 src/hudsource.c
 src/hudsourcelist.c
 src/hudstringlist.c
+src/hudtoken.c
 src/hud-verify-app-info.c
 src/hudwindowsource.c
 src/indicator-appmenu.c

=== modified file 'src/Makefile.am'
--- src/Makefile.am	2012-03-21 17:27:26 +0000
+++ src/Makefile.am	2012-04-03 12:30:26 +0000
@@ -99,8 +99,6 @@
 libhud_service_a_SOURCES = \
 	create-db.h \
 	create-db.c \
-	distance.h \
-	distance.c \
 	dump-app-info.h \
 	dump-app-info.c \
 	shared-values.h \
@@ -124,6 +122,8 @@
 	hudsourcelist.c		\
 	hudsource.h		\
 	hudsource.c		\
+	hudtoken.h		\
+	hudtoken.c		\
 	hudquery.h		\
 	hudquery.c		\
 	hudstringlist.h		\

=== removed file 'src/distance.c'
--- src/distance.c	2012-03-29 15:26:51 +0000
+++ src/distance.c	1970-01-01 00:00:00 +0000
@@ -1,415 +0,0 @@
-/*
-Functions to calculate the distance between two strings.
-
-Copyright 2011 Canonical Ltd.
-
-Authors:
-    Ted Gould <[e-mail]>
-
-This program is free software: you can redistribute it and/or modify it 
-under the terms of the GNU General Public License version 3, as published 
-by the Free Software Foundation.
-
-This program is distributed in the hope that it will be useful, but 
-WITHOUT ANY WARRANTY; without even the implied warranties of 
-MERCHANTABILITY, SATISFACTORY QUALITY, 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 <http://www.gnu.org/licenses/>.
-*/
-
-#include "distance.h"
-
-#include <glib-object.h>
-#include <glib/gprintf.h>
-#include <glib/gi18n.h>
-#include <gio/gio.h>
-
-#include "hudsettings.h"
-
-#define ADD_PENALTY         hud_settings.add_penalty
-#define PRE_ADD_PENALTY     hud_settings.add_penalty_pre
-#define DROP_PENALTY        hud_settings.drop_penalty
-#define END_DROP_PENALTY    hud_settings.drop_penalty_end
-#define TRANSPOSE_PENALTY   hud_settings.transpose_penalty
-#define SWAP_PENALTY        hud_settings.swap_penalty
-#define SWAP_CASE_PENALTY   hud_settings.swap_penalty_case
-
-/* Figure out how far off we are from a set of characters, basically
-   whether they match or not */
-static guint
-swap_cost (gunichar a, gunichar b)
-{
-	if (a == b)
-		return 0;
-	if (g_unichar_toupper(a) == g_unichar_toupper(b))
-		return SWAP_CASE_PENALTY; /* Some penalty, but close */
-	return SWAP_PENALTY;
-}
-
-#define MATRIX_VAL(needle_loc, haystack_loc) (penalty_matrix[(needle_loc + 1) + (haystack_loc + 1) * (len_needle + 1)])
-
-/* A function to print out the matrix for debugging purposes.  It is
-   mostly used in the test suite, though it could be used else where if
-   needed */
-static void
-dumpmatrix (const gchar * needle, guint len_needle, const gchar * haystack, guint len_haystack, guint * penalty_matrix)
-{
-#ifndef DUMP_MATRIX
-	return;
-#endif
-	gint i, j;
-
-	g_printf("\n");
-	/* Character Column */
-	g_printf("  ");
-	/* Base val column */
-	g_printf("  ");
-	for (i = 0; i < len_needle; i++) {
-		g_printf("%c ", needle[i]);
-	}
-	g_printf("\n");
-
-	/* Character Column */
-	g_printf("  ");
-	for (i = -1; i < (gint)len_needle; i++) {
-		g_printf("%u ", MATRIX_VAL(i, -1));
-	}
-	g_printf("\n");
-
-	for (j = 0; j < len_haystack; j++) {
-		g_printf("%c ", haystack[j]);
-		for (i = -1; i < (gint)len_needle; i++) {
-			g_printf("%u ", MATRIX_VAL(i, j));
-		}
-		g_printf("\n");
-	}
-	g_printf("\n");
-
-	return;
-}
-
-/* Looks at two individual tokens, builds a matrix and calculates the
-   distance between them by moving through the matrix.
-   If you believe, you can see the matrix, otherwise it looks just like
-   an array.  */
-static guint
-calculate_token_distance (const gchar * needle, const gchar * haystack)
-{
-	// g_debug("Comparing token '%s' to token '%s'", needle, haystack);
-
-	guint len_needle = 0;
-	guint len_haystack = 0;
-
-	if (needle != NULL) {
-		len_needle = g_utf8_strlen(needle, -1);
-	}
-
-	if (haystack != NULL) {
-		len_haystack = g_utf8_strlen(haystack, -1);
-	}
-
-	/* Handle the cases of very short or NULL strings quickly */
-	if (len_needle == 0) {
-		return DROP_PENALTY * len_haystack;
-	}
-
-	if (len_haystack == 0) {
-		return ADD_PENALTY * len_needle;
-	}
-
-	/* Allocate the matrix of penalties */
-	guint * penalty_matrix = g_malloc0(sizeof(guint) * (len_needle + 1) * (len_haystack + 1));
-	gint len_difference;
-	gint penalty;
-	int i;
-
-	/* Take the first row and first column and make them additional letter penalties */
-	penalty = 0;
-	for (i = 0; i < len_needle + 1; i++) {
-		MATRIX_VAL(i - 1, -1) = penalty;
-		penalty += ADD_PENALTY;
-	}
-
-	len_difference = len_haystack - len_needle;
-	penalty = 0;
-	for (i = 0; i < len_difference; i++) {
-		MATRIX_VAL(-1, i - 1) = penalty;
-		penalty += PRE_ADD_PENALTY;
-	}
-	for (; i < len_haystack + 1; i++) {
-		MATRIX_VAL(-1, i - 1) = penalty;
-		penalty += DROP_PENALTY;
-	}
-
-	/* Now go through the matrix building up the penalties */
-	int ineedle, ihaystack;
-	gchar * needle_head, * haystack_head;
-	for (needle_head = (gchar *)needle, ineedle = 0;
-			needle_head[0] != '\0';
-			needle_head = g_utf8_next_char(needle_head), ineedle++) {
-		for (haystack_head = (gchar *)haystack, ihaystack = 0;
-				haystack_head[0] != '\0';
-				haystack_head = g_utf8_next_char(haystack_head), ihaystack++) {
-			gunichar needle_let = g_utf8_get_char(needle_head);
-			gunichar haystack_let = g_utf8_get_char(haystack_head);
-
-			guint subst_pen = MATRIX_VAL(ineedle - 1, ihaystack - 1) + swap_cost(needle_let, haystack_let);
-			guint drop_pen = MATRIX_VAL(ineedle - 1, ihaystack);
-			if (ineedle < ihaystack) {
-				drop_pen += DROP_PENALTY;
-			} else {
-				drop_pen += END_DROP_PENALTY;
-			}
-
-			guint add_pen = MATRIX_VAL(ineedle, ihaystack - 1);
-			if (len_haystack - len_needle - ineedle > 0) {
-				add_pen += PRE_ADD_PENALTY;
-			} else {
-				add_pen += ADD_PENALTY;
-			}
-			guint transpose_pen = drop_pen + 1; /* ensures won't be chosen */
-
-			if (ineedle > 0 && ihaystack > 0 && needle_let == haystack[ihaystack - 1] && haystack_let == needle[ineedle - 1]) {
-				transpose_pen = MATRIX_VAL(ineedle - 2, ihaystack - 2) + TRANSPOSE_PENALTY;
-			}
-
-			MATRIX_VAL(ineedle, ihaystack) = MIN(MIN(subst_pen, drop_pen), MIN(add_pen, transpose_pen));
-		}
-	}
-
-	dumpmatrix(needle, len_needle, haystack, len_haystack, penalty_matrix);
-
-	guint retval = penalty_matrix[(len_needle + 1) * (len_haystack + 1) - 1];
-	g_free(penalty_matrix);
-
-	return retval;
-}
-
-/* Looks through the array of paths and tries to find a minimum path
-   looking up from the needle specified.  This way we can look through
-   all the possible paths */
-guint
-minimize_distance_recurse (guint needle, guint num_needles, guint haystack, guint num_haystacks, guint * distances, guint * matches)
-{
-	gint i;
-
-	/* Put where we are in the array so that we don't forget */
-	matches[needle] = haystack;
-
-	/* First check to see if we've already used this entry */
-	for (i = needle - 1; i >= 0; i--) {
-		if (matches[i] == haystack) {
-			return G_MAXUINT;
-		}
-	}
-
-	/* If we're the last needle, we can return our distance */
-	if (needle + 1 >= num_needles) {
-		return distances[(needle * num_haystacks) + haystack];
-	}
-
-	guint * local_match = g_new0(guint, num_needles);
-	for (i = 0; i < num_needles && i < needle + 1; i++) {
-		local_match[i] = matches[i];
-	}
-
-	/* Now look where we can get the minimum with the other needles */
-	guint min = G_MAXUINT;
-	for (i = 0; i < num_haystacks; i++) {
-		guint local = minimize_distance_recurse(needle + 1, num_needles, i, num_haystacks, distances, local_match);
-
-		if (local < min) {
-			min = local;
-
-			int j;
-			for (j = needle + 1; j < num_needles; j++) {
-				matches[j] = local_match[j];
-			}
-		}
-	}
-
-	g_free(local_match);
-
-	/* Return the min of everyone else plus our distance */
-	if (min < G_MAXUINT) {
-		min += distances[(needle * num_haystacks) + haystack];
-	}
-
-	return min;
-}
-
-/* Figuring out the lowest path through the distance array
-   where we don't use the same haystack tokens */
-guint
-minimize_distance (guint num_needles, guint num_haystacks, guint * distances, guint * matches)
-{
-	guint final_distance = G_MAXUINT;
-	guint * local_matches = g_new0(guint, num_needles);
-
-	guint haystack_token;
-	for (haystack_token = 0; haystack_token < num_haystacks; haystack_token++) {
-		guint distance = minimize_distance_recurse(0, num_needles, haystack_token, num_haystacks, distances, local_matches);
-
-		if (distance < final_distance) {
-			final_distance = distance;
-
-			guint match_cnt;
-			for (match_cnt = 0; match_cnt < num_needles; match_cnt++) {
-				matches[match_cnt] = local_matches[match_cnt];
-			}
-		}
-	}
-
-	g_free(local_matches);
-
-	return final_distance;
-}
-
-/* Dups a specific token in the array of strv arrays */
-gchar *
-find_token (guint token_number, GStrv * haystacks, guint num_haystacks)
-{
-	guint haystack;
-
-	for (haystack = 0; haystack < num_haystacks; haystack++) {
-		guint strvlen = g_strv_length(haystacks[haystack]);
-
-		if (token_number < strvlen) {
-			return g_strdup(haystacks[haystack][token_number]);
-		}
-
-		token_number -= strvlen;
-	}
-
-	return NULL;
-}
-
-/* Normalize a set of strings so that we can compare them
-   without worry about accents and the such */
-static GStrv
-normalize_gstrv (GStrv inlist)
-{
-	/* The identity property */
-	if (inlist == NULL) return NULL;
-
-	guint length = g_strv_length(inlist);
-	GStrv out = g_new0(gchar *, length + 1);
-	gint i;
-
-	for (i = 0; i < length; i++) {
-		out[i] = g_utf8_normalize(inlist[i], -1, G_NORMALIZE_ALL);
-	}
-
-	return out;
-}
-
-#define SEPARATORS " .->"
-
-guint
-calculate_distance (const gchar * needle, GStrv haystacks, GStrv * matches)
-{
-	g_return_val_if_fail(needle != NULL || haystacks != NULL, G_MAXUINT);
-	guint final_distance = G_MAXUINT;
-
-	if (needle == NULL || !g_utf8_validate(needle, -1, NULL)) {
-		return DROP_PENALTY * g_utf8_strlen(haystacks[0], 1024);
-	}
-	if (haystacks == NULL) {
-		return ADD_PENALTY * g_utf8_strlen(needle, 1024);
-	}
-
-	/* Check to make sure we have valid haystacks */
-	gint i;
-	guint num_haystacks = g_strv_length(haystacks);
-
-	for (i = 0; i < num_haystacks; i++) {
-		if (!g_utf8_validate(haystacks[i], -1, NULL)) {
-			return ADD_PENALTY * g_utf8_strlen(needle, 1024);
-		}
-	}
-
-	/* Tokenize all the haystack strings */
-	guint num_haystack_tokens = 0;
-	GStrv * haystacks_array = g_new0(GStrv, num_haystacks);
-
-	for (i = 0; i < num_haystacks; i++) {
-		GStrv split = g_strsplit_set(haystacks[i], SEPARATORS, 0);
-		haystacks_array[i] = normalize_gstrv(split);
-		g_strfreev(split);
-		num_haystack_tokens += g_strv_length(haystacks_array[i]);
-	}
-
-	/* Tokenize our needles the same way */
-	GStrv needle_split = g_strsplit_set(needle, SEPARATORS, 0);
-	GStrv needle_tokens = normalize_gstrv(needle_split);
-	g_strfreev(needle_split);
-	guint num_needle_tokens = g_strv_length(needle_tokens);
-
-	/* If we can't even find a set that works, let's just cut
-	   our losses here */
-	if (num_needle_tokens > num_haystack_tokens) {
-		goto cleanup_tokens;
-	}
-
-	/* We need a place to store all the distances */
-	guint * distances = g_new0(guint, num_haystack_tokens * num_needle_tokens);
-
-	/* Calculate all the distance combinations */
-	gint needle_token;
-	for (needle_token = 0; needle_tokens[needle_token] != NULL; needle_token++) {
-		gchar * ineedle = needle_tokens[needle_token];
-
-		guint haystacks_cnt;
-		guint haystack_token_cnt = 0;
-		for (haystacks_cnt = 0; haystacks_cnt < num_haystacks; haystacks_cnt++) {
-			guint haystack_cnt;
-			for (haystack_cnt = 0; haystacks_array[haystacks_cnt][haystack_cnt] != NULL; haystack_cnt++) {
-				gchar * ihaystack = haystacks_array[haystacks_cnt][haystack_cnt];
-				guint distance = calculate_token_distance(ineedle, ihaystack);
-
-				distances[(needle_token * num_haystack_tokens) + haystack_token_cnt] = distance;
-				haystack_token_cnt++;
-			}
-		}
-	}
-
-	/* Now, try to find a path through the array that results in the
-	   lowest total value */
-	guint * final_matches = g_new0(guint, num_needle_tokens);
-
-	final_distance = minimize_distance(num_needle_tokens, num_haystack_tokens, distances, final_matches);
-
-	/* Set up an array for matches so that we can enter
-	   the items as we go */
-	if (matches != NULL) {
-		GStrv match_array = NULL;
-		match_array = g_new0(gchar *, num_needle_tokens + 1);
-		match_array[num_needle_tokens] = NULL;
-
-		/* Copy the strings that we care about */
-		int i;
-		for (i = 0; i < num_needle_tokens; i++) {
-			match_array[i] = find_token(final_matches[i], haystacks_array, num_haystacks);
-		}
-
-		*matches = match_array;
-	}
-
-	g_free(final_matches);
-	g_free(distances);
-
-cleanup_tokens:
-	g_strfreev(needle_tokens);
-	for (i = 0; i < num_haystacks; i++) {
-		g_strfreev(haystacks_array[i]);
-	}
-	g_free(haystacks_array);
-
-	if (final_distance != G_MAXUINT) {
-		return final_distance / num_needle_tokens;
-	} else {
-		return G_MAXUINT;
-	}
-}

=== removed file 'src/distance.h'
--- src/distance.h	2012-03-05 04:46:53 +0000
+++ src/distance.h	1970-01-01 00:00:00 +0000
@@ -1,33 +0,0 @@
-/*
-Functions to calculate the distance between two strings.
-
-Copyright 2011 Canonical Ltd.
-
-Authors:
-    Ted Gould <[e-mail]>
-
-This program is free software: you can redistribute it and/or modify it 
-under the terms of the GNU General Public License version 3, as published 
-by the Free Software Foundation.
-
-This program is distributed in the hope that it will be useful, but 
-WITHOUT ANY WARRANTY; without even the implied warranties of 
-MERCHANTABILITY, SATISFACTORY QUALITY, 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 <http://www.gnu.org/licenses/>.
-*/
-
-#ifndef __DISTANCE_H__
-#define __DISTANCE_H__
-
-#include <glib-object.h>
-
-G_BEGIN_DECLS
-
-guint calculate_distance (const gchar * needle, GStrv haystack, GStrv * matched);
-
-G_END_DECLS
-
-#endif /* __DISTANCE_H__ */

=== modified file 'src/hudappindicatorsource.c'
--- src/hudappindicatorsource.c	2012-03-23 15:35:01 +0000
+++ src/hudappindicatorsource.c	2012-04-03 12:30:26 +0000
@@ -371,9 +371,9 @@
 }
 
 static void
-hud_app_indicator_source_search (HudSource   *hud_source,
-                                 GPtrArray   *results_array,
-                                 const gchar *search_string)
+hud_app_indicator_source_search (HudSource    *hud_source,
+                                 GPtrArray    *results_array,
+                                 HudTokenList *search_tokens)
 {
   HudAppIndicatorSource *source = HUD_APP_INDICATOR_SOURCE (hud_source);
   GSequenceIter *iter;
@@ -382,7 +382,7 @@
 
   while (!g_sequence_iter_is_end (iter))
     {
-      hud_source_search (g_sequence_get (iter), results_array, search_string);
+      hud_source_search (g_sequence_get (iter), results_array, search_tokens);
       iter = g_sequence_iter_next (iter);
     }
 }

=== modified file 'src/huddbusmenucollector.c'
--- src/huddbusmenucollector.c	2012-03-26 15:25:33 +0000
+++ src/huddbusmenucollector.c	2012-04-03 12:30:26 +0000
@@ -290,9 +290,9 @@
 }
 
 static void
-hud_dbusmenu_collector_search (HudSource   *source,
-                               GPtrArray   *results_array,
-                               const gchar *search_string)
+hud_dbusmenu_collector_search (HudSource    *source,
+                               GPtrArray    *results_array,
+                               HudTokenList *search_string)
 {
   HudDbusmenuCollector *collector = HUD_DBUSMENU_COLLECTOR (source);
   GHashTableIter iter;

=== modified file 'src/huddebugsource.c'
--- src/huddebugsource.c	2012-03-23 15:35:01 +0000
+++ src/huddebugsource.c	2012-04-03 12:30:26 +0000
@@ -105,9 +105,9 @@
 }
 
 static void
-hud_debug_source_search (HudSource   *hud_source,
-                         GPtrArray   *results_array,
-                         const gchar *search_string)
+hud_debug_source_search (HudSource    *hud_source,
+                         GPtrArray    *results_array,
+                         HudTokenList *search_string)
 {
   HudDebugSource *source = HUD_DEBUG_SOURCE (hud_source);
 

=== modified file 'src/hudindicatorsource.c'
--- src/hudindicatorsource.c	2012-03-23 15:35:01 +0000
+++ src/hudindicatorsource.c	2012-04-03 12:30:26 +0000
@@ -146,9 +146,9 @@
 }
 
 static void
-hud_indicator_source_search (HudSource   *hud_source,
-                             GPtrArray   *results_array,
-                             const gchar *search_string)
+hud_indicator_source_search (HudSource    *hud_source,
+                             GPtrArray    *results_array,
+                             HudTokenList *search_string)
 {
   HudIndicatorSource *source = HUD_INDICATOR_SOURCE (hud_source);
   gint i;

=== modified file 'src/huditem.c'
--- src/huditem.c	2012-03-23 15:35:01 +0000
+++ src/huditem.c	2012-04-03 12:30:26 +0000
@@ -19,6 +19,7 @@
 #include "huditem.h"
 
 #include "usage-tracker.h"
+#include "hudtoken.h"
 
 /**
  * SECTION:huditem
@@ -52,6 +53,7 @@
 
   gchar *desktop_file;
 
+  HudTokenList *token_list;
   HudStringList *tokens;
   gchar *usage_tag;
   gchar *app_icon;
@@ -68,8 +70,10 @@
   HudItem *item = HUD_ITEM (object);
 
   g_hash_table_remove (hud_item_table, &item->priv->id);
+  hud_token_list_free (item->priv->token_list);
   hud_string_list_unref (item->priv->tokens);
   g_free (item->priv->desktop_file);
+  g_free (item->priv->app_icon);
   g_free (item->priv->usage_tag);
 
   G_OBJECT_CLASS (hud_item_parent_class)
@@ -156,6 +160,7 @@
   item->priv->app_icon = g_strdup (app_icon);
   item->priv->enabled = enabled;
   item->priv->id = hud_item_next_id++;
+  item->priv->token_list = hud_token_list_new_from_string_list (tokens);
 
   g_hash_table_insert (hud_item_table, &item->priv->id, item);
 
@@ -330,3 +335,9 @@
 {
   return g_hash_table_lookup (hud_item_table, &id);
 }
+
+HudTokenList *
+hud_item_get_token_list (HudItem *item)
+{
+  return item->priv->token_list;
+}

=== modified file 'src/huditem.h'
--- src/huditem.h	2012-03-23 15:35:01 +0000
+++ src/huditem.h	2012-04-03 12:30:26 +0000
@@ -21,7 +21,7 @@
 
 #include <glib-object.h>
 
-#include "hudstringlist.h"
+#include "hudtoken.h"
 
 #define HUD_TYPE_ITEM                                       (hud_item_get_type ())
 #define HUD_ITEM(inst)                                      (G_TYPE_CHECK_INSTANCE_CAST ((inst),                     \
@@ -74,5 +74,6 @@
 gboolean                hud_item_get_enabled                            (HudItem       *item);
 guint64                 hud_item_get_id                                 (HudItem       *item);
 HudItem *               hud_item_lookup                                 (guint64        id);
+HudTokenList *          hud_item_get_token_list                         (HudItem       *item);
 
 #endif /* __HUD_ITEM_H__ */

=== modified file 'src/hudmenumodelcollector.c'
--- src/hudmenumodelcollector.c	2012-03-23 15:35:42 +0000
+++ src/hudmenumodelcollector.c	2012-04-03 12:30:26 +0000
@@ -346,9 +346,9 @@
 }
 
 static void
-hud_menu_model_collector_search (HudSource   *source,
-                                 GPtrArray   *results_array,
-                                 const gchar *search_string)
+hud_menu_model_collector_search (HudSource    *source,
+                                 GPtrArray    *results_array,
+                                 HudTokenList *search_string)
 {
   HudMenuModelCollector *collector = HUD_MENU_MODEL_COLLECTOR (source);
   GPtrArray *items;

=== modified file 'src/hudquery.c'
--- src/hudquery.c	2012-03-23 15:35:42 +0000
+++ src/hudquery.c	2012-04-03 12:30:26 +0000
@@ -51,6 +51,7 @@
 
   HudSource *source;
   gchar *search_string;
+  HudTokenList *token_list;
   gint num_results;
   guint refresh_id;
 
@@ -100,16 +101,21 @@
 hud_query_refresh (HudQuery *query)
 {
   guint max_usage = 0;
+  guint64 start_time;
+
+  start_time = g_get_monotonic_time ();
 
   g_ptr_array_set_size (query->results, 0);
 
   if (query->search_string[0] != '\0')
-    hud_source_search (query->source, query->results, query->search_string);
+    hud_source_search (query->source, query->results, query->token_list);
 
   g_ptr_array_foreach (query->results, hud_query_find_max_usage, &max_usage);
   g_ptr_array_sort_with_data (query->results, hud_query_compare_results, GINT_TO_POINTER (max_usage));
   if (query->results->len > query->num_results)
     g_ptr_array_set_size (query->results, query->num_results);
+
+  g_debug ("query took %dus\n", (int) (g_get_monotonic_time () - start_time));
 }
 
 static gboolean
@@ -148,6 +154,7 @@
   hud_source_unuse (query->source);
 
   g_object_unref (query->source);
+  hud_token_list_free (query->token_list);
   g_free (query->search_string);
   g_ptr_array_unref (query->results);
 
@@ -206,6 +213,7 @@
   query->source = g_object_ref (source);
   query->results = g_ptr_array_new_with_free_func (g_object_unref);
   query->search_string = g_strdup (search_string);
+  query->token_list = hud_token_list_new_from_string (query->search_string);
   query->num_results = num_results;
 
   hud_source_use (query->source);

=== modified file 'src/hudresult.c'
--- src/hudresult.c	2012-03-12 16:27:09 +0000
+++ src/hudresult.c	2012-04-03 12:30:26 +0000
@@ -21,7 +21,7 @@
 #include <string.h>
 
 #include "hudsettings.h"
-#include "distance.h"
+#include "hudtoken.h"
 
 /**
  * SECTION:hudresult
@@ -48,46 +48,19 @@
   HudItem *item;
 
   guint   distance;
-  gchar **matched;
+  const gchar **matched;
   gchar  *description;
 };
 
 G_DEFINE_TYPE (HudResult, hud_result, G_TYPE_OBJECT)
 
-static guint
-calculate_distance_from_list (const gchar   *search_string,
-                              HudStringList *list,
-                              GStrv         *matched)
-{
-  HudStringList *iter;
-  const gchar **strv;
-  guint distance;
-  gint i = 0;
-
-  for (iter = list; iter; iter = hud_string_list_get_tail (iter))
-    i++;
-
-  strv = g_new (const char *, i + 1);
-  strv[i] = NULL;
-
-  for (iter = list; iter; iter = hud_string_list_get_tail (iter))
-    strv[--i] = hud_string_list_get_head (iter);
-
-  distance = calculate_distance (search_string, (char **) strv, matched);
-
-  g_free (strv);
-
-
-  return distance;
-}
-
 static void
 hud_result_finalize (GObject *object)
 {
   HudResult *result = HUD_RESULT (object);
 
   g_object_unref (result->item);
-  g_strfreev (result->matched);
+  g_free (result->matched);
   g_free (result->description);
 
   G_OBJECT_CLASS (hud_result_parent_class)
@@ -126,16 +99,16 @@
  * Returns: a new #HudResult, or %NULL in event of a poor match
  **/
 HudResult *
-hud_result_get_if_matched (HudItem     *item,
-                           const gchar *search_string,
-                           guint        penalty)
+hud_result_get_if_matched (HudItem      *item,
+                           HudTokenList *search_tokens,
+                           guint         penalty)
 {
   if (!hud_item_get_enabled (item))
     return NULL;
 
   /* ignore the penalty in the max-distance calculation */
-  if (calculate_distance_from_list (search_string, hud_item_get_tokens (item), NULL) <= hud_settings.max_distance)
-    return hud_result_new (item, search_string, penalty);
+  if (hud_token_list_distance (hud_item_get_token_list (item), search_tokens, NULL) <= hud_settings.max_distance)
+    return hud_result_new (item, search_tokens, penalty);
   else
     return NULL;
 }
@@ -212,18 +185,18 @@
  * Returns: the new #HudResult
  **/
 HudResult *
-hud_result_new (HudItem     *item,
-                const gchar *search_string,
-                guint        penalty)
+hud_result_new (HudItem      *item,
+                HudTokenList *search_tokens,
+                guint         penalty)
 {
   HudResult *result;
 
   g_return_val_if_fail (HUD_IS_ITEM (item), NULL);
-  g_return_val_if_fail (search_string != NULL, NULL);
+  g_return_val_if_fail (search_tokens != NULL, NULL);
 
   result = g_object_new (HUD_TYPE_RESULT, NULL);
   result->item = g_object_ref (item);
-  result->distance = calculate_distance_from_list (search_string, hud_item_get_tokens (item), &result->matched);
+  result->distance = hud_token_list_distance (hud_item_get_token_list (item), search_tokens, &result->matched);
   hud_result_format_description (result);
 
   result->distance += (result->distance * penalty) / 100;

=== modified file 'src/hudresult.h'
--- src/hudresult.h	2012-03-05 04:46:53 +0000
+++ src/hudresult.h	2012-04-03 12:30:26 +0000
@@ -31,18 +31,18 @@
 
 GType                   hud_result_get_type                             (void);
 
-HudResult *             hud_result_new                                  (HudItem     *item,
-                                                                         const gchar *search_string,
-                                                                         guint        penalty);
-
-HudResult *             hud_result_get_if_matched                       (HudItem     *item,
-                                                                         const gchar *search_string,
-                                                                         guint        penalty);
-
-HudItem *               hud_result_get_item                             (HudResult   *result);
-guint                   hud_result_get_distance                         (HudResult   *result,
-                                                                         guint        max_usage);
-const gchar *           hud_result_get_html_description                 (HudResult   *result);
+HudResult *             hud_result_new                                  (HudItem      *item,
+                                                                         HudTokenList *search_tokens,
+                                                                         guint         penalty);
+
+HudResult *             hud_result_get_if_matched                       (HudItem      *item,
+                                                                         HudTokenList *search_tokens,
+                                                                         guint         penalty);
+
+HudItem *               hud_result_get_item                             (HudResult    *result);
+guint                   hud_result_get_distance                         (HudResult    *result,
+                                                                         guint         max_usage);
+const gchar *           hud_result_get_html_description                 (HudResult    *result);
 
 
 #endif /* __HUD_RESULT_H__ */

=== modified file 'src/hudsettings.c'
--- src/hudsettings.c	2012-03-07 04:11:28 +0000
+++ src/hudsettings.c	2012-04-03 12:30:26 +0000
@@ -53,20 +53,14 @@
  *   matching result
  * @add_penalty: the penalty incurred by a character in the search term
  *   that does not exist in the item being matched
- * @add_penalty_pre: the penalty incurred by a character in the search
- *   term that does not exist in the item being matched when that
- *   character comes at the beginning of the term
  * @drop_penalty: the penalty incurred by a character missing from the
  *   search string as compared to the item being matched
- * @drop_penalty_end: the penalty incurred by a character missing from
+ * @end_drop_penalty: the penalty incurred by a character missing from
  *   the search string as compared to the item being matched when the
  *   character is at the end of the item (ie: the search term is a
  *   prefix of the item)
- * @transpose_penalty: the penalty incurred for transposed characters
  * @swap_penalty: the penalty incurred for the substitution of one
  *   character for another
- * @swap_penalty_case: the penalty incurred for the substitution of one
- *   character for another when the characters differ only in case
  *
  * This structure contains the value of several tunable parameters that
  * affect the behaviour of various components of the HUD.
@@ -101,19 +95,14 @@
   hud_settings.indicator_penalty = g_settings_get_uint (settings, "indicator-penalty");
   hud_settings.max_distance = g_settings_get_uint (settings, "max-distance");
   hud_settings.add_penalty = g_settings_get_uint (settings, "add-penalty");
-  hud_settings.add_penalty_pre = g_settings_get_uint (settings, "add-penalty-pre");
   hud_settings.drop_penalty = g_settings_get_uint (settings, "drop-penalty");
-  hud_settings.drop_penalty_end = g_settings_get_uint (settings, "drop-penalty-end");
-  hud_settings.transpose_penalty = g_settings_get_uint (settings, "transpose-penalty");
+  hud_settings.end_drop_penalty = g_settings_get_uint (settings, "end-drop-penalty");
   hud_settings.swap_penalty = g_settings_get_uint (settings, "swap-penalty");
-  hud_settings.swap_penalty_case = g_settings_get_uint (settings, "swap-penalty-case");
 
   g_debug ("indicator penalty: %u, max distance: %u",
            hud_settings.indicator_penalty, hud_settings.max_distance);
-  g_debug ("penalties: add:%u add-pre:%u drop:%u drop-end:%u trans:%u swap:%u swap-case:%u",
-           hud_settings.add_penalty, hud_settings.add_penalty_pre, hud_settings.drop_penalty,
-           hud_settings.drop_penalty_end, hud_settings.transpose_penalty, hud_settings.swap_penalty,
-           hud_settings.swap_penalty_case);
+  g_debug ("penalties: add:%u drop:%u end-drop:%u swap:%u", hud_settings.add_penalty,
+           hud_settings.drop_penalty, hud_settings.end_drop_penalty, hud_settings.swap_penalty);
 }
 
 /**

=== modified file 'src/hudsettings.h'
--- src/hudsettings.h	2012-03-07 04:11:28 +0000
+++ src/hudsettings.h	2012-04-03 12:30:26 +0000
@@ -31,12 +31,9 @@
   guint max_distance;
 
   guint add_penalty;
-  guint add_penalty_pre;
   guint drop_penalty;
-  guint drop_penalty_end;
-  guint transpose_penalty;
+  guint end_drop_penalty;
   guint swap_penalty;
-  guint swap_penalty_case;
 };
 
 extern HudSettings hud_settings;

=== modified file 'src/hudsource.c'
--- src/hudsource.c	2012-03-15 18:25:50 +0000
+++ src/hudsource.c	2012-04-03 12:30:26 +0000
@@ -144,9 +144,9 @@
  * function may have changed, at which point you should call it again.
  **/
 void
-hud_source_search (HudSource   *source,
-                   GPtrArray   *results_array,
-                   const gchar *search_string)
+hud_source_search (HudSource    *source,
+                   GPtrArray    *results_array,
+                   HudTokenList *search_string)
 {
   g_debug ("search on %s %p", G_OBJECT_TYPE_NAME (source), source);
 

=== modified file 'src/hudsource.h'
--- src/hudsource.h	2012-03-15 18:25:50 +0000
+++ src/hudsource.h	2012-04-03 12:30:26 +0000
@@ -36,22 +36,22 @@
 {
   GTypeInterface g_iface;
 
-  void (* use)    (HudSource   *source);
-  void (* unuse)  (HudSource   *source);
-  void (* search) (HudSource   *source,
-                   GPtrArray   *results_array,
-                   const gchar *search_string);
+  void (* use)    (HudSource    *source);
+  void (* unuse)  (HudSource    *source);
+  void (* search) (HudSource    *source,
+                   GPtrArray    *results_array,
+                   HudTokenList *search_tokens);
 };
 
 GType                   hud_source_get_type                             (void);
 
-void                    hud_source_use                                  (HudSource   *source);
-void                    hud_source_unuse                                (HudSource   *source);
-
-void                    hud_source_search                               (HudSource   *source,
-                                                                         GPtrArray   *results_array,
-                                                                         const gchar *search_string);
-
-void                    hud_source_changed                              (HudSource   *source);
+void                    hud_source_use                                  (HudSource    *source);
+void                    hud_source_unuse                                (HudSource    *source);
+
+void                    hud_source_search                               (HudSource    *source,
+                                                                         GPtrArray    *results_array,
+                                                                         HudTokenList *search_tokens);
+
+void                    hud_source_changed                              (HudSource    *source);
 
 #endif /* __HUD_SOURCE_H__ */

=== modified file 'src/hudsourcelist.c'
--- src/hudsourcelist.c	2012-03-15 18:25:50 +0000
+++ src/hudsourcelist.c	2012-04-03 12:30:26 +0000
@@ -83,9 +83,9 @@
 }
 
 static void
-hud_source_list_search (HudSource   *source,
-                        GPtrArray   *results_array,
-                        const gchar *search_string)
+hud_source_list_search (HudSource    *source,
+                        GPtrArray    *results_array,
+                        HudTokenList *search_string)
 {
   HudSourceList *list = HUD_SOURCE_LIST (source);
   GSList *node;

=== added file 'src/hudtoken.c'
--- src/hudtoken.c	1970-01-01 00:00:00 +0000
+++ src/hudtoken.c	2012-04-03 12:30:26 +0000
@@ -0,0 +1,394 @@
+/*
+ * Copyright © 2012 Canonical Ltd.
+ *
+ * This program is free software: you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 3, as
+ * published by the Free Software Foundation.
+ *
+ * This program is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranties of
+ * MERCHANTABILITY, SATISFACTORY QUALITY, 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 <http://www.gnu.org/licenses/>.
+ *
+ * Author: Ryan Lortie <[e-mail]>
+ */
+
+#include "hudtoken.h"
+
+#include "hudsettings.h"
+
+#include <string.h>
+
+struct _HudToken
+{
+  guint     length;
+  gchar    *original;
+  gunichar *str;
+};
+
+/* This is actually one greater than the max-length.
+ * Should be power-of-two for best performance.
+ */
+#define TOKEN_LENGTH_LIMIT 32
+
+#if 0
+static void
+hud_token_distance_debug (const HudToken *haystack,
+                          const HudToken *needle,
+                          guint           d[TOKEN_LENGTH_LIMIT][TOKEN_LENGTH_LIMIT])
+{
+  gint i, j;
+
+  g_print (" ");
+  for (j = 0; j <= haystack->length; j++)
+    g_print ("%6lc", (wchar_t) (j ? haystack->str[j - 1] : ' '));
+  g_print ("\n");
+
+  for (i = 0; i <= needle->length; i++)
+    {
+      g_print ("%lc", (wchar_t) (i ? needle->str[i - 1] : ' '));
+      for (j = 0; j <= haystack->length; j++)
+        g_print ("%6u", d[i][j]);
+      g_print ("\n");
+    }
+}
+#endif
+
+#define MIN3(a,b,c) (MIN(MIN((a),(b)),(c)))
+
+/* Keeping in mind the fact that we're matching single words against
+ * single words, we can expect the extremely vast majority of cases to
+ * see needle and haystack both be less than 32 characters in length.
+ *
+ * For the common case we can avoid memory allocation by using a static
+ * array.  By making the array a constant factor-of-two size we can
+ * replace multiplication by a variable with bitshift by a constant.
+ *
+ * Tokens longer than this are expected to be so unlikely that we
+ * simply deal with them by truncation during the normalisation phase.
+ */
+guint
+hud_token_distance (const HudToken *haystack,
+                    const HudToken *needle)
+{
+  static guint d[TOKEN_LENGTH_LIMIT][TOKEN_LENGTH_LIMIT];
+  gunichar h, n;
+  gint result;
+  gint i, j;
+
+  g_assert (haystack->length < TOKEN_LENGTH_LIMIT && needle->length < TOKEN_LENGTH_LIMIT);
+  g_assert (haystack->str[haystack->length] == 0);
+  g_assert (needle->str[needle->length] == 0);
+
+  /* This function only performs memory writes to 'd' and calls no other
+   * functions.  No pointer to 'd' is ever leaked.  Hopefully the
+   * compiler is clever enough to therefore realise that no other memory
+   * will be modified during the running of this function and optimise
+   * aggressively.
+   */
+
+  /* By convention we refer to "add" and "drop" in terms of "mistakes
+   * the user made".  The user's token is the one in "needle".  To give
+   * examples against the menu item "preferences", if the user typed:
+   *
+   *  - "prefereces": this has a dropped character
+   *
+   *  - "prefferences": this has an added character
+   *
+   *  - "prefefences": this has a swap
+   *
+   * We organise the matrix with each column (j) corresponding to a
+   * character in the menu item text ('haystack') and each row (i)
+   * corresponding to a character in the search token ('needle').
+   *
+   * We modify the Levenshtein algorithm in the following ways:
+   *
+   *  - configurable penalties for various mistakes (add, drop,
+   *    swap).  This is done by replacing additions of '1' with
+   *    additions of these configurable values.
+   *
+   *  - a lower penalties for drops that occur at the end of the token
+   *    that the user typed.  For example, "prefer" would be given a
+   *    lower penalty for those 5 missing letters than would occur if
+   *    they were not missing from the end.
+   *
+   *    This is done by special-casing the last row (i == nlen) in the
+   *    matrix, corresponding to the last character in the search
+   *    token.  In this case, we calculate drops at a lower penalty.
+   *
+   * Implementing the first of these two changes is a simple tweak:
+   * instead of adding '1', add the configurable value.
+   *
+   * Implementing the second one is somewhat more difficult: we could
+   * modify the core algorithm, but that would violate the 'pureness' of
+   * the dynamic programming approach.
+   *
+   * Instead, we wait until the 'pure' algorithm is done then instead of
+   * only considering the result for the full menu item text (ie: the
+   * number in the bottom right corner) we consider all prefixes of the
+   * menu item text by scanning the entire bottom row (and adding a
+   * penalty according to the number of characters removed).
+   */
+
+  /* http://en.wikipedia.org/wiki/Levenshtein_distance#Computing_Levenshtein_distance */
+  for (i = 0; i <= needle->length; i++)
+    d[i][0] = i * hud_settings.add_penalty;
+
+  for (j = 0; j <= haystack->length; j++)
+    d[0][j] = j * hud_settings.drop_penalty;
+
+  for (i = 1; (n = needle->str[i - 1]); i++)
+    for (j = 1; (h = haystack->str[j - 1]); j++)
+      if (n == h)
+        d[i][j] = d[i - 1][j - 1];
+
+      else
+        d[i][j] = MIN3(d[i - 1][j - 1] + hud_settings.swap_penalty,
+                       d[i    ][j - 1] + hud_settings.drop_penalty,
+                       d[i - 1][j    ] + hud_settings.add_penalty);
+
+  /* Noe we consider all prefixes of the menu item text to discover
+   * which one gives us the best score.
+   *
+   * If we end up picking a result from a column other than the
+   * rightmost, it will have had the correct multiple of the end-drop
+   * penalty added to it by the time we're done.
+   */
+  result = d[--i][0];
+  for (j = 1; j <= haystack->length; j++)
+    result = MIN (d[i][j], result + hud_settings.end_drop_penalty);
+
+  return result;
+}
+
+HudToken *
+hud_token_new (const gchar *str,
+               gssize       length)
+{
+  HudToken *token;
+  gchar *normal;
+  gchar *folded;
+  glong items;
+
+  token = g_slice_new (HudToken);
+
+  token->original = g_strndup (str, length);
+  normal = g_utf8_normalize (str, length, G_NORMALIZE_ALL);
+  folded = g_utf8_casefold (normal, -1);
+  token->str = g_utf8_to_ucs4_fast (folded, -1, &items);
+  token->length = items;
+  g_free (folded);
+  g_free (normal);
+
+  if (!(token->length < TOKEN_LENGTH_LIMIT))
+    {
+      token->length = 31;
+      token->str[31] = 0;
+    }
+
+  return token;
+}
+
+void
+hud_token_free (HudToken *token)
+{
+  g_free (token->original);
+  g_free (token->str);
+  g_slice_free (HudToken, token);
+}
+
+static const gchar *
+hud_token_get_original (HudToken *token)
+{
+  return token->original;
+}
+
+struct _HudTokenList
+{
+  HudToken **tokens;
+  gint       length;
+};
+
+static HudTokenList *
+hud_token_list_new_consume_array (GPtrArray *array)
+{
+  HudTokenList *list;
+
+  list = g_slice_new (HudTokenList);
+  list->tokens = (HudToken **) array->pdata;
+  list->length = array->len;
+
+  g_ptr_array_free (array, FALSE);
+
+  return list;
+}
+
+#define SEPARATORS " .->"
+static void
+hud_token_list_add_string_to_array (GPtrArray   *array,
+                                    const gchar *string)
+{
+  while (*string)
+    {
+      /* strip separators */
+      string += strspn (string, SEPARATORS);
+
+      if (*string)
+        {
+          gint length;
+
+          /* consume a token */
+          length = strcspn (string, SEPARATORS);
+          g_ptr_array_add (array, hud_token_new (string, length));
+          string += length;
+        }
+    }
+}
+
+static void
+hud_token_list_add_string_list_to_array (GPtrArray     *array,
+                                         HudStringList *list)
+{
+  if (list == NULL)
+    return;
+
+  hud_token_list_add_string_list_to_array (array, hud_string_list_get_tail (list));
+  hud_token_list_add_string_to_array (array, hud_string_list_get_head (list));
+}
+
+HudTokenList *
+hud_token_list_new_from_string (const gchar *string)
+{
+  GPtrArray *array;
+
+  array = g_ptr_array_new ();
+  hud_token_list_add_string_to_array (array, string);
+  return hud_token_list_new_consume_array (array);
+}
+
+HudTokenList *
+hud_token_list_new_from_string_list (HudStringList *string_list)
+{
+  GPtrArray *array;
+
+  array = g_ptr_array_new ();
+  hud_token_list_add_string_list_to_array (array, string_list);
+  return hud_token_list_new_consume_array (array);
+}
+
+void
+hud_token_list_free (HudTokenList *list)
+{
+  gint i;
+
+  for (i = 0; i < list->length; i++)
+    hud_token_free (list->tokens[i]);
+
+  g_free (list->tokens);
+
+  g_slice_free (HudTokenList, list);
+}
+
+guint
+hud_token_list_distance (HudTokenList   *haystack,
+                         HudTokenList   *needle,
+                         const gchar  ***matches)
+{
+  static guint d[32][32];
+  gint i, j;
+
+  if (needle->length > haystack->length)
+    return G_MAXUINT;
+
+  /* Simply refuse to deal with ridiculous situations.
+   *
+   * This only happens when the user has more than 32 words in their
+   * search or the same happens in a menu item.
+   */
+  if (haystack->length > 32 || needle->length > 32)
+    return G_MAXUINT;
+
+  /* unroll the handling of the first needle term */
+  {
+    guint cost;
+
+    /* unroll the handling of the first haystack term */
+    cost = hud_token_distance (haystack->tokens[0], needle->tokens[0]);
+    d[0][0] = cost;
+
+    for (j = 0; j < haystack->length; j++)
+      {
+        guint take_cost;
+
+        take_cost = hud_token_distance (haystack->tokens[j], needle->tokens[0]);
+        cost = MIN (take_cost, cost + 1);
+        d[0][j] = cost;
+      }
+  }
+
+  /* if we have only one needle, this loop won't run at all */
+  for (i = 1; i < needle->length; i++)
+    {
+      guint cost;
+
+      /* unroll the handling of the first haystack term */
+      cost = d[i - 1][i - 1] + hud_token_distance (haystack->tokens[i], needle->tokens[i]);
+      d[i][i] = cost;
+
+      for (j = i + 1; j < haystack->length; j++)
+        {
+          guint prev_cost;
+
+          prev_cost = d[i - 1][j - 1];
+          /* Only do checking of additional terms of it's possible that
+           * we'll come in under the max distance AND beat the cost of
+           * just dropping the term.
+           *
+           * hud_token_distance() could return zero so we need to try it
+           * if:
+           *
+           *   - prev_cost is less than or equal to the max distance
+           *     (because then our result could equal the max distance)
+           *
+           *   - prev_cost is less than or equal to the last cost
+           *     Even if it's equal, skipping has a cost and a perfect
+           *     match has no cost, so we need to try the match.
+           */
+          if (prev_cost <= hud_settings.max_distance && prev_cost <= cost)
+            {
+              guint take_cost;
+
+              take_cost = prev_cost + hud_token_distance (haystack->tokens[j], needle->tokens[i]);
+              cost = MIN (take_cost, cost + 1);
+            }
+          else
+            cost = cost + 1;
+
+          d[i][j] = cost;
+        }
+    }
+
+  /* Discover which terms were matched */
+  if (matches)
+    {
+      *matches = g_new (const gchar *, needle->length + 1);
+
+      j = haystack->length - 1;
+
+      for (i = needle->length - 1; i >= 0; i--)
+        {
+          while (j > i && d[i][j-1] == d[i][j] - 1)
+            j--;
+
+          (*matches)[i] = hud_token_get_original (haystack->tokens[j]);
+          j--;
+        }
+
+      (*matches)[needle->length] = NULL;
+    }
+
+  return d[needle->length - 1][haystack->length - 1];
+}

=== added file 'src/hudtoken.h'
--- src/hudtoken.h	1970-01-01 00:00:00 +0000
+++ src/hudtoken.h	2012-04-03 12:30:26 +0000
@@ -0,0 +1,40 @@
+/*
+ * Copyright © 2012 Canonical Ltd.
+ *
+ * This program is free software: you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 3, as
+ * published by the Free Software Foundation.
+ *
+ * This program is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranties of
+ * MERCHANTABILITY, SATISFACTORY QUALITY, 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 <http://www.gnu.org/licenses/>.
+ *
+ * Author: Ryan Lortie <[e-mail]>
+ */
+
+#ifndef __HUD_TOKEN_H__
+#define __HUD_TOKEN_H__
+
+#include "hudstringlist.h"
+
+typedef struct _HudTokenList HudTokenList;
+typedef struct _HudToken HudToken;
+
+HudToken *              hud_token_new                                   (const gchar      *token,
+                                                                         gssize            length);
+void                    hud_token_free                                  (HudToken         *token);
+guint                   hud_token_distance                              (const HudToken   *haystack,
+                                                                         const HudToken   *needle);
+
+HudTokenList *          hud_token_list_new_from_string                  (const gchar      *string);
+HudTokenList *          hud_token_list_new_from_string_list             (HudStringList    *string_list);
+void                    hud_token_list_free                             (HudTokenList     *list);
+guint                   hud_token_list_distance                         (HudTokenList     *haystack,
+                                                                         HudTokenList     *needle,
+                                                                         const gchar    ***matches);
+
+#endif /* __HUD_TOKEN_H__ */

=== modified file 'src/hudwindowsource.c'
--- src/hudwindowsource.c	2012-03-23 15:35:01 +0000
+++ src/hudwindowsource.c	2012-04-03 12:30:26 +0000
@@ -67,7 +67,7 @@
   BamfWindow *active_window;
   BamfApplication *active_application;
   const gchar *active_desktop_file;
-  const gchar *active_icon;
+  gchar *active_icon;
   HudSource *active_collector;
   gint use_count;
 };
@@ -255,6 +255,7 @@
   g_clear_object (&source->active_collector);
   g_clear_object (&source->active_application);
   g_clear_object (&source->active_window);
+  g_free (source->active_icon);
   source->active_window = g_object_ref (window);
   source->active_application = g_object_ref (application);
   source->active_desktop_file = desktop_file;
@@ -296,9 +297,9 @@
 }
 
 static void
-hud_window_source_search (HudSource   *hud_source,
-                          GPtrArray   *results_array,
-                          const gchar *search_string)
+hud_window_source_search (HudSource    *hud_source,
+                          GPtrArray    *results_array,
+                          HudTokenList *search_string)
 {
   HudWindowSource *source = HUD_WINDOW_SOURCE (hud_source);
 
@@ -311,9 +312,13 @@
 {
   HudWindowSource *source = HUD_WINDOW_SOURCE (object);
 
+  g_assert_cmpint (source->use_count, ==, 0);
+
   /* bamf matcher signals already disconnected in dispose */
+  g_clear_object (&source->active_collector);
   g_clear_object (&source->active_application);
   g_clear_object (&source->active_window);
+  g_free (source->active_icon);
 
   G_OBJECT_CLASS (hud_window_source_parent_class)
     ->finalize (object);

=== modified file 'tests/Makefile.am'
--- tests/Makefile.am	2012-03-27 16:38:41 +0000
+++ tests/Makefile.am	2012-04-03 12:30:26 +0000
@@ -391,6 +391,24 @@
 
 DISTCLEANFILES += test-dbus-message-count.bustle
 
+###################
+# Test Performance
+###################
+
+check_PROGRAMS += \
+	hud-performance
+
+hud_performance_CFLAGS = \
+	-I$(top_builddir)/src		\
+	-I$(top_srcdir)/src		\
+	$(HUD_CFLAGS)
+hud_performance_LDADD = \
+	../src/libhud-service.a		\
+	$(HUD_LIBS)
+hud_performance_SOURCES = \
+	hud-performance.c	\
+	word-list.h
+
 #########################
 # Footer
 #########################

=== added file 'tests/hud-performance.c'
--- tests/hud-performance.c	1970-01-01 00:00:00 +0000
+++ tests/hud-performance.c	2012-04-03 12:30:26 +0000
@@ -0,0 +1,279 @@
+/*
+ * Copyright © 2012 Canonical Ltd.
+ *
+ * This program is free software: you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 3, as
+ * published by the Free Software Foundation.
+ *
+ * This program is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranties of
+ * MERCHANTABILITY, SATISFACTORY QUALITY, 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 <http://www.gnu.org/licenses/>.
+ *
+ * Author: Ryan Lortie <[e-mail]>
+ */
+
+#include "hudsettings.h"
+#include "hudquery.h"
+#include "hudtoken.h"
+#include "hudsource.h"
+
+#include <glib-object.h>
+
+#include "word-list.h"
+
+/* Max nested depth of menu items */
+#define MAX_DEPTH 6
+
+/* Max number of items per submenu */
+#define MAX_ITEMS 20
+
+/* Max number of words per label.
+ * NB: keep MAX_WORDS * MAX_DEPTH under 32
+ */
+#define MAX_WORDS 4
+
+/* Longest word in the word-list (upper bound) */
+#define MAX_LETTERS 20
+
+/* hardcode some parameters for reasons of determinism.
+ */
+HudSettings hud_settings = {
+  .indicator_penalty = 50,
+  .add_penalty = 10,
+  .drop_penalty = 10,
+  .end_drop_penalty = 1,
+  .swap_penalty = 15,
+  .max_distance = 30
+};
+
+typedef struct
+{
+  GObject object;
+
+  GHashTable *items;
+} RandomSource;
+
+typedef GObjectClass RandomSourceClass;
+
+static void random_source_iface_init (HudSourceInterface *iface);
+G_DEFINE_TYPE_WITH_CODE (RandomSource, random_source, G_TYPE_OBJECT,
+                         G_IMPLEMENT_INTERFACE (HUD_TYPE_SOURCE, random_source_iface_init))
+
+static void
+random_source_search (HudSource    *hud_source,
+                      GPtrArray    *results_array,
+                      HudTokenList *search_tokens)
+{
+  RandomSource *source = (RandomSource *) hud_source;
+  GHashTableIter iter;
+  gpointer item;
+
+  g_hash_table_iter_init (&iter, source->items);
+  while (g_hash_table_iter_next (&iter, &item, NULL))
+    {
+      HudResult *result;
+
+      result = hud_result_get_if_matched (item, search_tokens, 0);
+      if (result)
+        g_ptr_array_add (results_array, result);
+    }
+}
+
+static void
+random_source_ignore_use (HudSource *source)
+{
+}
+
+static gchar *
+make_word (GRand *rand,
+           gchar *buffer)
+{
+  const gchar *word;
+  gint choice;
+  gint len;
+
+  choice = g_rand_int_range (rand, 0, G_N_ELEMENTS (word_list));
+  word = word_list[choice];
+
+  while (*word)
+    *buffer++ = *word++;
+
+  return buffer;
+}
+
+static gchar *
+make_words (GRand *rand,
+            gint   n_words)
+{
+  gchar *buffer;
+  gchar *ptr;
+  gint i;
+
+  buffer = g_malloc ((MAX_LETTERS + 1) * n_words);
+
+  ptr = buffer;
+  for (i = 0; i < n_words; i++)
+    {
+      if (i)
+        *ptr++ = ' ';
+
+      ptr = make_word (rand, ptr);
+    }
+
+  *ptr = '\0';
+
+  return buffer;
+}
+
+static HudStringList *
+random_source_make_name (GRand         *rand,
+                         HudStringList *context)
+{
+  HudStringList *name;
+  gchar *label;
+
+  label = make_words (rand, g_rand_int_range (rand, 1, MAX_WORDS + 1));
+  name = hud_string_list_cons (label, context);
+  g_free (label);
+
+  return name;
+}
+
+static void
+random_source_populate_table (GRand         *rand,
+                              GHashTable    *items,
+                              HudStringList *context,
+                              gint           depth)
+{
+  gint n_items;
+  gint i;
+
+  n_items = g_rand_int_range (rand, 1, MAX_ITEMS + 1);
+
+  for (i = 0; i < n_items; i++)
+    {
+      HudStringList *name;
+      gboolean is_submenu;
+      HudItem *item;
+
+      name = random_source_make_name (rand, context);
+
+      if (depth != MAX_DEPTH)
+        /* Decrease the chances of a particular item being a submenu as we
+         * go deeper into the menu structure.
+         */
+        is_submenu = g_rand_int_range (rand, 0, depth + 1) == 0;
+      else
+        /* At the maximum depth, prevent any items from being submenus. */
+        is_submenu = FALSE;
+
+      item = hud_item_new (name, NULL, NULL, !is_submenu);
+      g_hash_table_add (items, item);
+
+      if (is_submenu)
+        random_source_populate_table (rand, items, name, depth + 1);
+
+      hud_string_list_unref (name);
+    }
+}
+
+static void
+random_source_finalize (GObject *object)
+{
+  RandomSource *source = (RandomSource *) object;
+
+  g_hash_table_unref (source->items);
+
+  G_OBJECT_CLASS (random_source_parent_class)
+    ->finalize (object);
+}
+
+static void
+random_source_init (RandomSource *source)
+{
+  source->items = g_hash_table_new_full (NULL, NULL, g_object_unref, NULL);
+}
+
+static void
+random_source_iface_init (HudSourceInterface *iface)
+{
+  iface->use = random_source_ignore_use;
+  iface->unuse = random_source_ignore_use;
+  iface->search = random_source_search;
+}
+
+static void
+random_source_class_init (RandomSourceClass *class)
+{
+  class->finalize = random_source_finalize;
+}
+
+static HudSource *
+random_source_new (GRand *rand)
+{
+  RandomSource *source;
+
+  source = g_object_new (random_source_get_type (), NULL);
+  random_source_populate_table (rand, source->items, NULL, 0);
+
+  return HUD_SOURCE (source);
+}
+
+void
+test_query_performance (void)
+{
+  HudSource *source;
+  HudQuery *query;
+  GRand *rand;
+  gint i;
+
+  rand = g_rand_new_with_seed (1234);
+  source = random_source_new (rand);
+
+  for (i = 1; i <= 6; i++)
+    {
+      guint64 start_time;
+      gchar *search;
+      gint j;
+
+      g_print ("\n");
+
+      search = make_words (rand, i);
+
+      /* simulate the user typing it in, one character at a time */
+      for (j = 1; search[j - 1]; j++)
+        {
+          gchar *part_search = g_strndup (search, j);
+
+          start_time = g_get_monotonic_time ();
+          query = hud_query_new (source, part_search, 1u<<30);
+          g_print ("%-60s: %dus (%d hits)\n", part_search,
+                   (int) (g_get_monotonic_time () - start_time),
+                   hud_query_get_n_results (query));
+          hud_query_close (query);
+          g_object_unref (query);
+          g_free (part_search);
+        }
+
+      g_free (search);
+    }
+
+  g_object_unref (source);
+  g_rand_free (rand);
+}
+
+int
+main (int argc, char **argv)
+{
+  g_type_init ();
+
+  g_test_init (&argc, &argv, NULL);
+  if (g_test_perf ())
+    g_test_add_func ("/hud/query-performance", test_query_performance);
+
+  return g_test_run ();
+}

=== modified file 'tests/test-distance.c'
--- tests/test-distance.c	2012-03-12 18:52:56 +0000
+++ tests/test-distance.c	2012-04-03 12:30:26 +0000
@@ -23,7 +23,7 @@
 #include <glib-object.h>
 
 #include "hudsettings.h"
-#include "distance.h"
+#include "hudtoken.h"
 
 /* hardcode some parameters so the test doesn't fail if the user
  * has bogus things in GSettings.
@@ -31,15 +31,54 @@
 HudSettings hud_settings = {
 	.indicator_penalty = 50,
 	.add_penalty = 10,
-	.add_penalty_pre = 1,
 	.drop_penalty = 10,
-	.drop_penalty_end = 10,
-	.transpose_penalty = 10,
-	.swap_penalty = 10,
-	.swap_penalty_case = 1,
+	.end_drop_penalty = 1,
+	.swap_penalty = 15,
 	.max_distance = 30
 };
 
+static guint
+calculate_distance (const gchar *search, GStrv teststrings, gchar ***matches)
+{
+	HudStringList *list = NULL;
+	HudTokenList *haystack;
+	HudTokenList *needle;
+	guint distance;
+	gint i;
+
+	if (search == NULL || teststrings == NULL) {
+		return G_MAXINT;
+	}
+
+	for (i = 0; teststrings[i]; i++) {
+		HudStringList *tmp;
+
+		tmp = hud_string_list_cons (teststrings[i], list);
+		hud_string_list_unref (list);
+		list = tmp;
+	}
+
+	haystack = hud_token_list_new_from_string_list (list);
+	hud_string_list_unref (list);
+
+	needle = hud_token_list_new_from_string (search);
+	distance = hud_token_list_distance (haystack, needle, (const gchar ***) matches);
+
+	if (matches) {
+		/* These are owned by the tokenlists, so make copies
+		 * before freeing.
+		 */
+		for (i = 0; (*matches)[i]; i++) {
+			(*matches)[i] = g_strdup ((*matches)[i]);
+		}
+	}
+
+	hud_token_list_free (haystack);
+	hud_token_list_free (needle);
+
+	return distance;
+}
+
 /* Ensure the base calculation works */
 static void
 test_distance_base (void)
@@ -185,6 +224,18 @@
 	return;
 }
 
+/* Check to make sure 'Save' matches better than 'Save As...' for "save" */
+static void
+test_distance_extra_terms (void)
+{
+  const gchar *save_as[] = { "File", "Save", "As...", NULL };
+  const gchar *save[] = { "File", "Save", NULL };
+
+  g_assert_cmpint (calculate_distance ("save", (GStrv) save, NULL),
+                   <,
+                   calculate_distance ("save", (GStrv) save_as, NULL));
+}
+
 /* Build the test suite */
 static void
 test_distance_suite (void)
@@ -196,6 +247,7 @@
 	g_test_add_func ("/hud/distance/duplicates",    test_distance_dups);
 	g_test_add_func ("/hud/distance/variety",       test_distance_variety);
 	g_test_add_func ("/hud/distance/french_pref",   test_distance_french_pref);
+	g_test_add_func ("/hud/distance/extra_terms",   test_distance_extra_terms);
 	return;
 }
 

=== added file 'tests/word-list.h'
--- tests/word-list.h	1970-01-01 00:00:00 +0000
+++ tests/word-list.h	2012-04-03 12:30:26 +0000
@@ -0,0 +1,364 @@
+const gchar *word_list[] = {
+  "sap", "sat", "sad", "rat", "rap", "ram", "rag", "nap", "Nat", "mat",
+  "map", "mad", "lap", "lag", "lad", "fat", "fan", "fad", "fin", "fit",
+  "lid", "lip", "lit", "mid", "mitt", "nit", "nip", "rid", "rig", "rim",
+  "rip", "Sid", "sin", "sip", "log", "mom", "mop", "nod", "rod", "Ron",
+  "rot", "sod", "fun", "mud", "mum", "nut", "rug", "rut", "sum", "sun",
+  "fed", "led", "leg", "met", "Ned", "net", "bag", "bad", "bam", "bat",
+  "cap", "cab", "dad", "Dan", "gas", "gag", "ham", "hat", "jab", "jam",
+  "pan", "pat", "tab", "tag", "tan", "tap", "bid", "dig", "dip", "hid",
+  "hit", "hip", "Jim", "jig", "kin", "kid", "pin", "pit", "pig", "tin",
+  "tip", "Tim", "cop", "con", "Don", "dog", "hop", "hog", "job", "jog",
+  "pot", "pop", "top", "Tom", "bug", "bud", "bum", "cup", "cub", "dud",
+  "dug", "Gus", "gun", "hum", "jug", "pup", "tub", "tug", "beg", "bed",
+  "bet", "hen", "jet", "Ken", "pen", "pet", "peg", "pep", "the", "of",
+  "and", "a", "to", "in", "is", "you", "that", "it", "he", "was", "for",
+  "on", "are", "as", "with", "his", "they", "I", "at", "be", "this",
+  "have", "from", "or", "one", "had", "by", "word", "but", "not",
+  "what", "all", "were", "we", "when", "your", "can", "said", "there",
+  "use", "an", "each", "which", "she", "do", "how", "their", "if",
+  "will", "up", "other", "about", "out", "many", "then", "them",
+  "these", "so", "some", "her", "would", "make", "like", "him", "into",
+  "time", "has", "look", "two", "more", "write", "go", "see", "number",
+  "no", "way", "could", "people", "my", "than", "first", "water",
+  "been", "call", "who", "oil", "its", "now", "find", "long", "down",
+  "day", "did", "get", "come", "made", "may", "part", "over", "new",
+  "sound", "take", "only", "little", "work", "know", "place", "year",
+  "live", "me", "back", "give", "most", "very", "after", "thing", "our",
+  "just", "name", "good", "sentence", "man", "think", "say", "great",
+  "where", "help", "through", "much", "before", "line", "right", "too",
+  "mean", "old", "any", "same", "tell", "boy", "follow", "came", "want",
+  "show", "also", "around", "farm", "three", "small", "set", "put",
+  "end", "does", "another", "well", "large", "must", "big", "even",
+  "such", "because", "turn", "here", "why", "ask", "went", "men",
+  "read", "need", "land", "different", "home", "us", "move", "try",
+  "kind", "hand", "picture", "again", "change", "off", "play", "spell",
+  "air", "away", "animal", "house", "point", "page", "letter", "mother",
+  "answer", "found", "study", "still", "learn", "should", "America",
+  "world", "high", "every", "near", "add", "food", "between", "own",
+  "below", "country", "plant", "last", "school", "father", "keep",
+  "tree", "never", "start", "city", "earth", "eye", "light", "thought",
+  "head", "under", "story", "saw", "left", "don't", "few", "while",
+  "along", "might", "chose", "something", "seem", "next", "hard",
+  "open", "example", "begin", "life", "always", "those", "both",
+  "paper", "together", "got", "group", "often", "run", "important",
+  "until", "children", "side", "feet", "car", "mile", "night", "walk",
+  "white", "sea", "began", "grow", "took", "river", "four", "carry",
+  "state", "once", "book", "hear", "stop", "without", "second", "late",
+  "miss", "idea", "enough", "eat", "face", "watch", "far", "Indian",
+  "really", "almost", "let", "above", "girl", "sometimes", "mountain",
+  "cut", "young", "talk", "soon", "list", "song", "being", "leave",
+  "family", "it's", "am", "ate", "best", "better", "black", "blue",
+  "bring", "brown", "buy", "clean", "cold", "done", "draw", "drink",
+  "eight", "fall", "fast", "five", "fly", "full", "funny", "gave",
+  "giving", "goes", "green", "hold", "hot", "hurt", "jump", "laugh",
+  "myself", "pick", "please", "pretty", "pull", "ran", "red", "ride",
+  "round", "seven", "shall", "sing", "sit", "six", "sleep", "ten",
+  "thank", "today", "upon", "warm", "wash", "wish", "yellow", "yes",
+  "act", "ant", "bake", "band", "bank", "bell", "belt", "Ben", "bend",
+  "bent", "Bess", "bike", "bit", "bite", "blast", "bled", "blend",
+  "blimp", "blink", "bliss", "block", "blond", "blot", "bluff", "blunt",
+  "bone", "brag", "brand", "brass", "brat", "bred", "bride", "brig",
+  "brim", "broke", "brunt", "brute", "bump", "bun", "bunt", "bust",
+  "camp", "cane", "can't", "cape", "cast", "cat", "clad", "clam",
+  "clamp", "clan", "clap", "clasp", "class", "cliff", "cling", "clink",
+  "clip", "close", "clot", "club", "clump", "clung", "cone", "crab",
+  "craft", "cram", "cramp", "crib", "crime", "crisp", "crop", "crust",
+  "cure", "cute", "dam", "damp", "den", "dent", "dim", "dime", "dine",
+  "dire", "dive", "dope", "draft", "drag", "drank", "dress", "drift",
+  "drill", "drip", "drop", "drove", "drug", "drum", "dump", "dust",
+  "eve", "fact", "fade", "fell", "felt", "file", "fill", "film", "fine",
+  "fire", "fist", "flag", "flap", "flat", "fled", "fling", "flip",
+  "flop", "flung", "flunk", "frame", "frank", "frill", "frisk", "frog",
+  "frost", "froze", "fume", "gasp", "gaze", "glad", "gland", "glass",
+  "glint", "globe", "glum", "golf", "grab", "grade", "gram", "gramp",
+  "grand", "grant", "grape", "grasp", "grass", "grill", "grim", "grin",
+  "grip", "gripe", "grump", "grunt", "gulp", "gust", "gut", "hate",
+  "held", "hide", "hint", "hire", "hole", "honk", "hope", "hose", "hug",
+  "hung", "hunt", "hut", "ink", "Jan", "Jane", "joke", "junk", "kept",
+  "kit", "kite", "lamp", "lick", "lift", "lime", "limp", "lock", "luck",
+  "lump", "Mack", "mask", "mass", "mast", "mate", "melt", "mend",
+  "Mick", "Mike", "milk", "mill", "mint", "mist", "mite", "mope",
+  "mule", "mute", "neck", "nest", "nine", "nose", "note", "pane",
+  "pant", "pass", "past", "pest", "Pete", "pike", "pile", "pill",
+  "pine", "plan", "plane", "plank", "plate", "plop", "plot", "plug",
+  "plum", "plump", "plus", "poke", "pole", "pomp", "pond", "pope",
+  "prank", "press", "pride", "prime", "print", "prize", "prop", "punk",
+  "pure", "raft", "ripe", "robe", "rock", "rode", "romp", "rope",
+  "rose", "Runs", "runt", "rust", "sack", "sake", "Sam", "sand", "sank",
+  "save", "scab", "scale", "scalp", "scan", "scare", "scat", "scope",
+  "scram", "scrap", "script", "self", "sell", "send", "sent", "sick",
+  "site", "size", "skate", "skid", "skill", "skim", "skin", "skip",
+  "skit", "skunk", "slam", "slang", "slant", "slap", "slat", "slate",
+  "slave", "sled", "slept", "slide", "slim", "sling", "slip", "slob",
+  "slope", "slot", "slug", "slum", "slump", "smack", "smell", "smile",
+  "smog", "smoke", "smug", "snack", "snag", "snake", "snap", "sniff",
+  "snip", "snipe", "snub", "snug", "sock", "soft", "span", "spank",
+  "spat", "sped", "spend", "spent", "spill", "spin", "spine", "spit",
+  "spite", "splat", "splint", "split", "spoke", "spot", "spun", "spunk",
+  "stab", "stack", "stale", "stamp", "stand", "stem", "step", "stiff",
+  "sting", "stink", "stomp", "stone", "stove", "strand", "strap",
+  "strip", "stripe", "struck", "strung", "stuck", "stump", "stun",
+  "suck", "sung", "swam", "swang", "swell", "swift", "swim", "swing",
+  "swung", "tack", "tam", "tame", "tape", "tent", "test", "tide",
+  "tile", "till", "tilt", "trade", "tramp", "trap", "trend", "trick",
+  "trim", "trip", "trot", "trunk", "trust", "twang", "twig", "twin",
+  "twist", "van", "vane", "wave", "weld", "wet", "win", "wind", "wine",
+  "wire", "yoke", "absent", "admit", "album", "ball", "bang", "banging",
+  "basket", "bathtub", "bedbug", "bench", "bib", "bill", "blank",
+  "blasted", "blended", "blush", "bobsled", "box", "branch", "brave",
+  "brush", "bunch", "bus", "camping", "care", "case", "catnip", "cave",
+  "chest", "chill", "chin", "chip", "chipmunk", "chop", "chunk",
+  "clock", "cloth", "contest", "crack", "crash", "crashing", "crept",
+  "cross", "crush", "cuff", "dash", "deck", "dentist", "dish",
+  "disrupt", "disrupted", "dot", "drinking", "dusted", "expanded",
+  "fang", "fib", "finishing", "fish", "fix", "flute", "fog", "fox",
+  "Fran", "fuss", "gift", "goblin", "gum", "hall", "hang", "Hank",
+  "himself", "hotrod", "huff", "hunted", "index", "insisted",
+  "insisting", "insulted", "invent", "invented", "Jack", "jumping",
+  "king", "kiss", "lane", "lapdog", "lasted", "lending", "loft", "lost",
+  "lug", "lunch", "lung", "mall", "mascot", "math", "mess", "mob",
+  "mug", "napkin", "pack", "Pam", "path", "picnic", "pigpen", "pinball",
+  "pinch", "planted", "plastic", "problem", "public", "publishing",
+  "puff", "punishing", "quake", "rake", "rash", "rented", "rest",
+  "rested", "rich", "ring", "ringing", "rub", "safe", "sale", "sang",
+  "sash", "shack", "shed", "shelf", "shell", "shifted", "shine", "ship",
+  "shop", "shrimp", "shrinking", "shrunk", "shut", "sink", "sinking",
+  "sits", "splash", "splashing", "squinted", "standing", "Steve",
+  "stub", "stuff", "stunt", "sub", "sunfish", "sunk", "sunlit",
+  "sunset", "suntan", "swishing", "talented", "tall", "tank", "throne",
+  "thud", "tick", "tilted", "tiptop", "toss", "trusted", "twisted",
+  "upset", "vent", "vest", "wag", "wall", "wax", "whiff", "whip",
+  "whiplash", "wig", "wing", "wink", "wipe", "wise", "yell", "zap",
+  "zigzag", "called", "circle", "friend", "Mr.", "Mrs.", "nothing",
+  "says", "Ann", "Beth", "Bing", "Blanch", "bong", "Buck", "burnt",
+  "Burt", "Carmen", "Cass", "caterpillar", "Chad", "cheer", "chomp",
+  "Chuck", "chuckle", "chug", "Clark", "click", "climb", "clown",
+  "cluck", "coal", "complain", "croak", "crunch", "Curtis", "curve",
+  "darts", "dinner", "diver", "doctor", "doll", "door", "Doris",
+  "Ellen", "fellow", "fiddle", "firm", "fishing", "Fitch", "foam",
+  "forever", "forgot", "forth", "front", "Gert", "gobble", "gone",
+  "gosh", "granddad", "grandpa", "grinned", "grumble", "hatch", "Herb",
+  "hill", "horse", "hush", "insect", "Jeff", "jiggle", "Jill", "Jill's",
+  "Josh", "jumble", "kick", "Kim", "Kirk", "larch", "library", "lived",
+  "lives", "market", "Mitch", "mix", "napper", "nibble", "Nick", "Norm",
+  "Oh", "onto", "owner", "patch", "peck", "perfect", "ping", "Pip",
+  "pong", "quick", "quill", "quilt", "Quinn", "quit", "reward", "Rex",
+  "Rick", "Rivera", "roam", "ruff", "Sanchez", "served", "Seth",
+  "sister", "Sloan", "smash", "snort", "snuggle", "soup", "sparkle",
+  "sprinkle", "squirt", "stick", "sudden", "sunburn", "surprise",
+  "swimmer", "Tad", "tadpole", "Ted", "Tess", "Texas", "tickle", "toad",
+  "Todd", "turf", "twinkle", "twitch", "umbrella", "uncle", "wham",
+  "whirl", "whisper", "whistle", "wiggle", "window", "Winkle",
+  "writing", "yet", "York", "zing", "zip", "able", "ace", "added",
+  "afraid", "afternoon", "age", "ahead", "annoy", "anything", "anyway",
+  "anywhere", "ape", "applaud", "arm", "artist", "attack", "attic",
+  "auto", "avoid", "awesome", "awful", "awning", "babble", "baby",
+  "baffle", "bald", "ballplayer", "bark", "base", "baseball", "basin",
+  "basketball", "batch", "bath", "battle", "beach", "bead", "beam",
+  "bean", "beanstalk", "beast", "beat", "bedtime", "bee", "beef",
+  "beehive", "beet", "begging", "behind", "bird", "birthday", "bleach",
+  "blew", "blind", "bloom", "blow", "blown", "bluebird", "blueprint",
+  "blur", "boast", "boat", "bob", "body", "boil", "bold", "bonnet",
+  "bonus", "boost", "boot", "born", "bottle", "bowl", "brace", "braid",
+  "brain", "brainstorm", "brake", "brawl", "bread", "breakfast",
+  "breath", "brick", "bright", "broil", "broiler", "broom", "bruise",
+  "bubble", "buddy", "built", "bundle", "bunk", "bunny", "burn",
+  "burst", "buses", "butterfly", "button", "buzz", "cabin", "cage",
+  "cake", "camel", "candle", "candy", "careful", "cart", "catch",
+  "cattle", "cell", "cent", "chain", "chalk", "champ", "charge",
+  "chart", "chase", "chat", "check", "cheerful", "cheese", "chess",
+  "chew", "chick", "child", "chime", "chirp", "choice", "chore",
+  "church", "churn", "claim", "classmate", "clay", "clerk", "clever",
+  "clue", "clutch", "coach", "coat", "coax", "coil", "coin", "collect",
+  "colorful", "cool", "core", "cork", "corn", "cowboy", "cozy", "crate",
+  "crawl", "cream", "crew", "crinkle", "crow", "cruise", "cry",
+  "cuddle", "cupcake", "curb", "curl", "dab", "daddy", "dangle",
+  "Danny", "dark", "dart", "date", "dawn", "daylight", "dead", "deaf",
+  "dealt", "decent", "deep", "delight", "desk", "die", "dimple", "dirt",
+  "ditch", "doghouse", "double", "dragon", "dragonfly", "drain",
+  "dread", "dream", "drew", "driveway", "droop", "dry", "duck", "due",
+  "dunk", "dusk", "easel", "easy", "egg", "elbow", "enjoy", "ever",
+  "evergreen", "everyone", "everything", "everywhere", "explore",
+  "fabric", "fail", "faithful", "fame", "fault", "fawn", "feast",
+  "feed", "feel", "fence", "fern", "fetch", "fifty", "fight", "finish",
+  "firefighter", "flagpole", "flash", "flashlight", "flaunt", "flaw",
+  "flight", "float", "flow", "fluffy", "foal", "foil", "fold", "fool",
+  "forest", "forget", "fork", "form", "fort", "fraud", "fray", "free",
+  "fresh", "Friday", "fried", "fright", "frozen", "fruit", "fry", "fur",
+  "game", "garden", "gate", "gel", "gem", "germ", "giggle", "ginger",
+  "giraffe", "gleam", "glean", "glow", "gluestick", "goat", "going",
+  "gold", "goose", "Grace", "graceful", "grain", "grapefruit",
+  "grasshopper", "grateful", "gray", "grew", "groan", "grown",
+  "grown-up", "growth", "gumball", "habit", "hail", "handwriting",
+  "happen", "happy", "harm", "harmful", "harp", "haul", "haunt", "hawk",
+  "hay", "health", "heat", "heavy", "heel", "hello", "helpful",
+  "herself", "hi", "hidden", "highway", "hoist", "homemade", "homework",
+  "hoot", "hopeful", "hopscotch", "horn", "host", "houseboat",
+  "housefly", "huddle", "human", "humid", "hummingbird", "hump",
+  "hungry", "hunk", "hurdle", "hurl", "ice", "inch", "inside",
+  "instead", "itch", "Jake", "jar", "jaw", "Jean", "jeep", "jelly",
+  "jellyfish", "Jen", "jerk", "Jimmy", "jingle", "Jo", "Joan", "join",
+  "joint", "joy", "juggle", "juice", "jungle", "kickball", "kingfish",
+  "kits", "kitten", "kitty", "knack", "knee", "kneecap", "kneel",
+  "knelt", "knew", "knife", "knight", "knit", "knob", "knock",
+  "knockout", "knot", "knothole", "known", "lace", "lack", "lake",
+  "latch", "launch", "law", "lawn", "lay", "lazy", "leap", "leather",
+  "Lee", "lemon", "less", "lie", "lighthouse", "limit", "link",
+  "lipstick", "living", "load", "loaf", "loop", "loose", "lot", "low",
+  "lunchbox", "Mabel", "mail", "main", "mane", "march", "mark", "match",
+  "Matt", "meant", "meat", "meet", "mice", "middle", "mild", "mind",
+  "mine", "mitten", "moan", "model", "moist", "mold", "moment",
+  "Monday", "moo", "mood", "motel", "mow", "munch", "music", "muzzle",
+  "nab", "nail", "nanny", "Nate", "neat", "necktie", "nerve",
+  "newscast", "newspaper", "nice", "nickname", "nighttime", "nips",
+  "noise", "noon", "north", "nowhere", "oak", "oat", "oatmeal",
+  "object", "oink", "ooze", "outside", "ox", "pace", "paddle", "pail",
+  "pain", "painful", "paint", "pal", "pancake", "paperback", "park",
+  "pause", "paw", "pawn", "pay", "peace", "peaceful", "peach", "peak",
+  "peddle", "peep", "pencil", "pennies", "penny", "perch", "piano",
+  "pie", "pillow", "pilot", "pink", "pipe", "pitch", "ploy", "poison",
+  "pony", "pooch", "poodle", "pool", "popcorn", "porch", "port", "post",
+  "poster", "potpie", "pretzel", "price", "proof", "pupil", "puppy",
+  "purple", "purse", "puzzle", "quack", "queen", "quicksand", "rabbit",
+  "race", "rack", "rage", "rail", "rain", "rainbow", "ranch", "rang",
+  "rattle", "raw", "ray", "reach", "ready", "recycle", "refund",
+  "renew", "restful", "return", "ribbon", "rice", "riddle", "rind",
+  "rink", "rise", "road", "roast", "rob", "robin", "robot", "room",
+  "roost", "row", "Roy", "royal", "ruled", "rumble", "runway", "rush",
+  "saddle", "sag", "sail", "sailboat", "salad", "sample", "sandbox",
+  "sandpaper", "sandy", "Saturday", "sauce", "saucer", "scarf", "scold",
+  "scorch", "score", "scrape", "scratch", "scream", "screen", "screw",
+  "scrub", "seal", "seat", "serve", "settle", "shade", "shadow",
+  "shake", "shaking", "shameful", "shape", "share", "shark", "sharp",
+  "sheep", "shipwreck", "shirt", "shore", "short", "shrink", "shrub",
+  "shrug", "shy", "sidewalk", "sigh", "sight", "silence", "silly",
+  "simple", "sips", "sir", "siren", "sky", "slice", "slick", "slight",
+  "slow", "slur", "sly", "smart", "smiling", "smooth", "snail", "sneak",
+  "snooze", "snore", "snow", "snowball", "snowflake", "snowman", "soak",
+  "soap", "sofa", "soil", "someone", "somewhere", "sore", "sort", "soy",
+  "space", "spark", "speak", "splendid", "splotch", "spoil", "spool",
+  "spoon", "sport", "sprain", "sprawl", "spray", "spread", "spring",
+  "sprint", "spruce", "spur", "squawk", "stage", "star", "startle",
+  "stay", "steam", "steep", "stern", "stiffer", "stir", "stool",
+  "store", "stork", "storm", "strain", "strange", "straw", "stray",
+  "stream", "street", "stretch", "strict", "strike", "string", "strong",
+  "stung", "sue", "suit", "suitcase", "sunblock", "Sunday", "sunflower",
+  "sunny", "sunrise", "sunshine", "surf", "sway", "sweat", "sweep",
+  "sweet", "swerve", "swimming", "swirl", "switch", "tablet", "tail",
+  "taps", "tattle", "taught", "tea", "teach", "teacher", "team",
+  "tease", "teeth", "tennis", "thankful", "thick", "thigh", "thimble",
+  "thin", "thinner", "thinnest", "third", "thirst", "thorn", "thread",
+  "threat", "thrill", "throat", "throw", "Thursday", "tie", "tiger",
+  "tight", "tired", "toast", "toil", "told", "tool", "tooth", "topcoat",
+  "torch", "torn", "tot", "tow", "toy", "trace", "traffic", "train",
+  "trash", "travel", "tray", "tread", "treetop", "trouble", "truck",
+  "trumpet", "Tuesday", "tugboat", "tulip", "tumble", "tummy", "turtle",
+  "tusk", "twirl", "ugly", "unzip", "useful", "value", "vanish", "verb",
+  "verse", "vine", "visit", "visitor", "voice", "void", "vote",
+  "waddle", "wage", "wagon", "wait", "wake", "waves", "wealth",
+  "weather", "weave", "web", "Wednesday", "weed", "week", "weekend",
+  "wettest", "whack", "whale", "whatever", "wheat", "wheel", "whenever",
+  "whisk", "whiz", "wide", "wife", "wild", "windmill", "wonderful",
+  "wore", "worn", "wrap", "wreath", "wreck", "wrench", "wriggle",
+  "wrinkle", "wrist", "wristwatch", "written", "wrong", "wrote", "yak",
+  "yard", "yardstick", "yarn", "yawn", "yum", "Zack", "zebra", "zoo",
+  "zoom", "ban", "bar", "winter", "bay", "wear", "bye", "mitten", "aid",
+  "aim", "arc", "art", "ash", "axe", "cog", "cot", "cow", "dew", "ear",
+  "eel", "elf", "elk", "elm", "era", "fee", "fig", "fir", "flu", "gap",
+  "guy", "icy", "inn", "ivy", "Jay", "key", "nag", "oar", "odd", "owe",
+  "owl", "pea", "pod", "rib", "sew", "ski", "sob", "son", "sow", "spa",
+  "spy", "tar", "tax", "toe", "vet", "war", "won", "yap", "zen", "ax",
+  "bait", "barn", "bawl", "beak", "birth", "blab", "blade", "blame",
+  "blaze", "bleed", "bless", "blip", "blurb", "blurt", "bog", "bond",
+  "boo", "books", "booth", "bow", "boys", "brad", "bran", "brawn",
+  "brisk", "brook", "broth", "brother", "card", "cash", "cask", "caw",
+  "cheap", "cheek", "chow", "clack", "clang", "clash", "claw", "cloak",
+  "clod", "coast", "cob", "cod", "code", "cook", "coop", "cord", "cost",
+  "count", "coy", "crane", "crick", "crock", "crook", "crown", "crude",
+  "crumb", "cube", "cue", "dear", "disk", "dock", "doze", "drake",
+  "drape", "drawn", "drive", "dude", "east", "Ed", "faint", "flake",
+  "flame", "flesh", "flick", "flirt", "flit", "flock", "floor", "flour",
+  "flown", "flush", "fond", "foot", "fowl", "Fred", "fret", "frizz",
+  "frying", "fuse", "gang", "glade", "glaze", "glee", "glen", "glide",
+  "glob", "gloss", "goal", "gown", "grate", "greet", "grit", "grouch",
+  "growl", "gruff", "heal", "heap", "hem", "hike", "hood", "hoof",
+  "hook", "hoop", "howl", "huge", "husk", "imp", "intern", "jail",
+  "jib", "June", "jut", "laid", "lame", "leak", "lend", "lent", "lien",
+  "lint", "loan", "loin", "lone", "loot", "lop", "lord", "loud", "lurk",
+  "lute", "maid", "maze", "meal", "mirth", "mock", "mole", "moon",
+  "mouse", "mouth", "murk", "musk", "nook", "nurse", "pad", "paid",
+  "peek", "peel", "pelt", "perk", "plain", "plants", "player", "plod",
+  "plow", "plums", "pork", "prance", "pray", "prayer", "present",
+  "prim", "prince", "probe", "prod", "program", "proud", "prowl", "pry",
+  "punt", "raid", "rant", "real", "rent", "risk", "Rome", "roof",
+  "rude", "rung", "scald", "scar", "scoop", "scoot", "scout", "scowl",
+  "scuff", "scum", "seek", "seen", "shawl", "sheet", "shirk", "shook",
+  "shoot", "shot", "shout", "shown", "sift", "silk", "sixth", "skips",
+  "skirt", "skull", "slash", "slaw", "slay", "slid", "slit", "slop",
+  "smear", "smith", "smock", "smoky", "snare", "snatch", "sneeze",
+  "snob", "snoop", "snuff", "soot", "sour", "south", "speck", "speech",
+  "speed", "spike", "spry", "spud", "spurn", "spurt", "stain", "stall",
+  "Stan", "steal", "stood", "sulk", "swamp", "swan", "swap", "swarm",
+  "swat", "swatch", "swept", "swig", "swine", "swish", "swoop", "sworn",
+  "swum", "tale", "task", "tend", "tenth", "term", "thumb", "tint",
+  "tock", "town", "toys", "track", "trail", "tram", "trek", "tribe",
+  "trod", "Troy", "tune", "tweed", "tweet", "twelve", "twenty", "twice",
+  "twine", "twitter", "urge", "urn", "uses", "vase", "vow", "wade",
+  "wed", "wept", "west", "whine", "whir", "wick", "wilt", "woke",
+  "wood", "woof", "wool", "wove", "wow", "zest", "zone", "against",
+  "American", "among", "asked", "course", "days", "didn't", "during",
+  "eyes", "general", "given", "however", "later", "order", "possible",
+  "president", "rather", "since", "states", "system", "things",
+  "though", "toward", "united", "used", "years", "color", "suddenly",
+  "zipper", "ah", "ho", "Ma", "Pa", "TV", "ago", "baa", "God", "hoe",
+  "I'd", "I'm", "sis", "ill", "O.K", "ache", "aunt", "bare", "bear",
+  "boom", "busy", "dare", "lose", "love", "none", "rule", "sure",
+  "tire", "tube", "copy", "edge", "else", "fizz", "glue", "hair",
+  "half", "hour", "I'll", "I've", "July", "kill", "lady", "lamb",
+  "leaf", "liar", "lion", "mama", "mash", "meow", "mush", "obey",
+  "okay", "ouch", "oven", "papa", "pour", "push", "roll", "shoe",
+  "soda", "tiny", "worm", "TRUE", "U.S.", "agree", "alive", "apple",
+  "April", "awake", "blood", "break", "chair", "cloud", "cough",
+  "cover", "dance", "erase", "phone", "piece", "whole", "whose",
+  "adult", "angry", "belly", "death", "eagle", "empty", "extra",
+  "hurry", "maybe", "money", "movie", "nasty", "party", "pizza",
+  "quiet", "sorry", "stair", "sugar", "table", "taste", "threw",
+  "touch", "towel", "truth", "waist", "waste", "woman", "women",
+  "won't", "worse", "anyone", "arrive", "asleep", "August", "avenue",
+  "behave", "bridge", "carpet", "cereal", "choose", "cookie", "corner",
+  "crayon", "danger", "minute", "banana", "bucket", "carrot", "dollar",
+  "finger", "flower", "gentle", "handle", "listen", "mirror", "monkey",
+  "nickel", "nobody", "orange", "parent", "person", "pocket", "potato",
+  "puppet", "rocket", "search", "secret", "seesaw", "shovel", "shower",
+  "silent", "spider", "sponge", "squash", "squeak", "sticky", "summer",
+  "supper", "they'd", "ticket", "tiptoe", "tissue", "tomato", "tongue",
+  "turkey", "unfair", "wonder", "U.S.A.", "airport", "anybody",
+  "balloon", "bedroom", "bicycle", "brownie", "cartoon", "ceiling",
+  "channel", "chicken", "garbage", "promise", "squeeze", "address",
+  "blanket", "earache", "excited", "good-bye", "grandma", "grocery",
+  "indoors", "January", "kitchen", "lullaby", "monster", "morning",
+  "naughty", "October", "pajamas", "pretend", "quarter", "shampoo",
+  "stomach", "there's", "they'll", "they're", "they've", "tonight",
+  "unhappy", "airplane", "alphabet", "bathroom", "favorite", "medicine",
+  "December", "dinosaur", "elephant", "February", "football",
+  "forehead", "headache", "hospital", "lollipop", "November",
+  "outdoors", "question", "railroad", "remember", "sandwich",
+  "scissors", "shoulder", "softball", "tomorrow", "upstairs",
+  "vacation", "restroom", "astronaut", "beautiful", "bumblebee",
+  "cardboard", "chocolate", "Christmas", "classroom", "cranberry",
+  "drugstore", "furniture", "milkshake", "nightmare", "telephone",
+  "difficult", "everybody", "hamburger", "September", "spaceship",
+  "spaghetti", "stoplight", "underwear", "yesterday", "automobile",
+  "blackboard", "downstairs", "photograph", "strawberry", "television",
+  "toothbrush", "toothpaste", "baby-sitter", "grandfather",
+  "grandmother", "kindergarten", "refrigerator", "Thanksgiving",
+  "hide-and-seek", "pumpkin", "salt", "melted", "handed", "printed",
+  "landed", "wanted", "filled", "showed", "hugged", "tugged", "planned",
+  "jogged", "spilled", "smelled", "grilled", "slammed", "rushed",
+  "spelled", "saved", "baked", "named", "lined", "smiled", "closed",
+  "helped", "jumped", "looked", "clapped", "tapped", "kicked",
+  "dropped", "zipped", "wished", "pitched", "missed", "walked",
+  "worked", "she'll", "you'll", "he'll", "we're", "she's", "he's",
+  "you're", "we're"
+};