Initial revision

1 files changed, 664 insertions, 0 deletions

diff --git a/lib/ephy-autocompletion.c b/lib/ephy-autocompletion.c
new file mode 100644
index 000000000..a3f3348c1
--- /dev/null
+++ b/lib/ephy-autocompletion.c
@@ -0,0 +1,664 @@
+/*
+ *  Copyright (C) 2002  Ricardo Fernández Pascual
+ *
+ *  This program is free software; you can redistribute it and/or modify
+ *  it under the terms of the GNU General Public License as published by
+ *  the Free Software Foundation; either version 2, or (at your option)
+ *  any later version.
+ *
+ *  This program is distributed in the hope that it will be useful,
+ *  but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *  GNU General Public License for more details.
+ *
+ *  You should have received a copy of the GNU General Public License
+ *  along with this program; if not, write to the Free Software
+ *  Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
+ */
+
+#include <string.h>
+#include <stdlib.h>
+
+#include "ephy-autocompletion.h"
+#include "ephy-gobject-misc.h"
+#include "ephy-marshal.h"
+
+#define NOT_IMPLEMENTED g_warning ("not implemented: " G_STRLOC);
+
+//#define DEBUG_MSG(x) g_print x
+#define DEBUG_MSG(x)
+
+//#define DEBUG_TIME
+
+#ifdef DEBUG_TIME
+#include <glib/gtimer.h>
+#endif
+
+/**
+ * Private data
+ */
+
+typedef enum {
+	GAS_NEEDS_REFINE,
+	GAS_NEEDS_FULL_UPDATE,
+	GAS_UPDATED
+} EphyAutocompletionStatus;
+
+typedef struct {
+	EphyAutocompletionMatch *array;
+	guint num_matches;
+	guint num_action_matches;
+	guint array_size;
+} ACMatchArray;
+
+#define ACMA_BASE_SIZE 10240
+
+struct _EphyAutocompletionPrivate {
+	GSList *sources;
+
+	guint nkeys;
+	gchar **keys;
+	guint *key_lengths;
+	gchar **prefixes;
+	guint *prefix_lengths;
+
+	gchar *common_prefix;
+	ACMatchArray matches;
+	EphyAutocompletionStatus status;
+	gboolean sorted;
+	gboolean changed;
+
+	gboolean sort_alpha;
+};
+
+/**
+ * Private functions, only availble from this file
+ */
+static void		ephy_autocompletion_class_init			(EphyAutocompletionClass *klass);
+static void		ephy_autocompletion_init			(EphyAutocompletion *e);
+static void		ephy_autocompletion_finalize_impl		(GObject *o);
+static void		ephy_autocompletion_reset			(EphyAutocompletion *ac);
+static void		ephy_autocompletion_update_matches		(EphyAutocompletion *ac);
+static void		ephy_autocompletion_update_matches_full		(EphyAutocompletion *ac);
+static gboolean		ephy_autocompletion_sort_by_score		(EphyAutocompletion *ac);
+static void		ephy_autocompletion_data_changed_cb		(EphyAutocompletionSource *s,
+									 EphyAutocompletion *ac);
+
+static void		acma_init					(ACMatchArray *a);
+static void		acma_destroy					(ACMatchArray *a);
+static inline void	acma_append					(ACMatchArray *a,
+									 EphyAutocompletionMatch *m,
+									 gboolean action);
+static void		acma_grow					(ACMatchArray *a);
+
+
+static gpointer g_object_class;
+
+/**
+ * Signals enums and ids
+ */
+enum EphyAutocompletionSignalsEnum {
+	EPHY_AUTOCOMPLETION_SOURCES_CHANGED,
+	EPHY_AUTOCOMPLETION_LAST_SIGNAL
+};
+static gint EphyAutocompletionSignals[EPHY_AUTOCOMPLETION_LAST_SIGNAL];
+
+/**
+ * Autocompletion object
+ */
+
+MAKE_GET_TYPE (ephy_autocompletion, "EphyAutocompletion", EphyAutocompletion,
+       ephy_autocompletion_class_init, ephy_autocompletion_init, G_TYPE_OBJECT);
+
+static void
+ephy_autocompletion_class_init (EphyAutocompletionClass *klass)
+{
+	G_OBJECT_CLASS (klass)->finalize = ephy_autocompletion_finalize_impl;
+	g_object_class = g_type_class_peek_parent (klass);
+
+	EphyAutocompletionSignals[EPHY_AUTOCOMPLETION_SOURCES_CHANGED] = g_signal_new (
+		"sources-changed", G_OBJECT_CLASS_TYPE (klass),
+		G_SIGNAL_RUN_FIRST | G_SIGNAL_RUN_LAST | G_SIGNAL_RUN_CLEANUP,
+                G_STRUCT_OFFSET (EphyAutocompletionClass, sources_changed),
+		NULL, NULL,
+		ephy_marshal_VOID__VOID,
+		G_TYPE_NONE, 0);
+}
+
+static void
+ephy_autocompletion_init (EphyAutocompletion *ac)
+{
+	EphyAutocompletionPrivate *p = g_new0 (EphyAutocompletionPrivate, 1);
+	ac->priv = p;
+	p->sources = NULL;
+	p->common_prefix = NULL;
+	acma_init (&p->matches);
+	p->status = GAS_NEEDS_FULL_UPDATE;
+
+	p->nkeys = 1;
+
+	p->keys = g_new0 (gchar *, 2);
+	p->keys[0] = g_strdup ("");
+	p->key_lengths = g_new0 (guint, 2);
+	p->key_lengths[0] = 0;
+
+	p->prefixes = g_new0 (gchar *, 2);
+	p->prefixes[0] = g_strdup ("");
+	p->prefix_lengths = g_new0 (guint, 2);
+	p->prefix_lengths[0] = 0;
+
+	p->sort_alpha = TRUE;
+}
+
+static void
+ephy_autocompletion_finalize_impl (GObject *o)
+{
+	EphyAutocompletion *ac = EPHY_AUTOCOMPLETION (o);
+	EphyAutocompletionPrivate *p = ac->priv;
+	GSList *li;
+
+	ephy_autocompletion_reset (ac);
+
+	for (li = p->sources; li; li = li->next)
+	{
+		g_signal_handlers_disconnect_by_func (li->data,
+						      ephy_autocompletion_data_changed_cb, ac);
+		g_object_unref (li->data);
+	}
+
+	g_slist_free (p->sources);
+
+	g_strfreev (p->keys);
+	g_free (p->key_lengths);
+	g_strfreev (p->prefixes);
+	g_free (p->prefix_lengths);
+
+	G_OBJECT_CLASS (g_object_class)->finalize (o);
+
+}
+
+static void
+ephy_autocompletion_reset (EphyAutocompletion *ac)
+{
+	EphyAutocompletionPrivate *p = ac->priv;
+#ifdef DEBUG_TIME
+	GTimer *timer = g_timer_new ();
+	g_timer_start (timer);
+#endif
+	acma_destroy (&p->matches);
+	g_free (p->common_prefix);
+	p->common_prefix = NULL;
+	p->status = GAS_NEEDS_FULL_UPDATE;
+#ifdef DEBUG_TIME
+	DEBUG_MSG (("AC: %f elapsed resetting\n", g_timer_elapsed (timer, NULL)));
+	g_timer_destroy (timer);
+#endif
+}
+
+EphyAutocompletion *
+ephy_autocompletion_new (void)
+{
+	EphyAutocompletion *ret = g_object_new (EPHY_TYPE_AUTOCOMPLETION, NULL);
+	return ret;
+}
+void
+ephy_autocompletion_add_source (EphyAutocompletion *ac,
+				EphyAutocompletionSource *s)
+{
+	EphyAutocompletionPrivate *p = ac->priv;
+	g_object_ref (G_OBJECT (s));
+	p->sources = g_slist_prepend (p->sources, s);
+	ephy_autocompletion_reset (ac);
+	g_signal_connect (s, "data-changed", G_CALLBACK (ephy_autocompletion_data_changed_cb), ac);
+
+	g_signal_emit (ac, EphyAutocompletionSignals[EPHY_AUTOCOMPLETION_SOURCES_CHANGED], 0);
+}
+
+void
+ephy_autocompletion_set_key (EphyAutocompletion *ac,
+			     const gchar *key)
+{
+	EphyAutocompletionPrivate *p = ac->priv;
+	guint i;
+	guint keylen = strlen (key);
+
+	if (strcmp (key, p->keys[0]))
+	{
+		GSList *li;
+		for (li = p->sources; li; li = li->next)
+		{
+			ephy_autocompletion_source_set_basic_key
+				(EPHY_AUTOCOMPLETION_SOURCE (li->data), key);
+		}
+	}
+
+	if (keylen >= p->key_lengths[0]
+	    && !strncmp (p->keys[0], key, p->key_lengths[0]))
+	{
+		if (!strcmp (key, p->keys[0]))
+		{
+			return;
+		}
+		if (p->status != GAS_NEEDS_FULL_UPDATE)
+		{
+			p->status = GAS_NEEDS_REFINE;
+		}
+		if (p->common_prefix)
+		{
+			if (strncmp (p->common_prefix, key, keylen))
+			{
+				g_free (p->common_prefix);
+				p->common_prefix = NULL;
+			}
+		}
+	}
+	else
+	{
+		p->status = GAS_NEEDS_FULL_UPDATE;
+		g_free (p->common_prefix);
+		p->common_prefix = NULL;
+	}
+
+	for (i = 0; p->prefixes[i]; ++i)
+	{
+		g_free (p->keys[i]);
+		p->keys[i] = g_strconcat (p->prefixes[i], key, NULL);
+		p->key_lengths[i] = keylen + p->prefix_lengths[i];
+	}
+
+}
+
+gchar *
+ephy_autocompletion_get_common_prefix (EphyAutocompletion *ac)
+{
+	EphyAutocompletionPrivate *p = ac->priv;
+	ephy_autocompletion_update_matches (ac);
+	if (!p->common_prefix)
+	{
+		guint common_length = 0;
+		guint i;
+#ifdef DEBUG_TIME
+		GTimer *timer = g_timer_new ();
+		g_timer_start (timer);
+#endif
+		for (i = 0; i < p->matches.num_matches; i++)
+		{
+			EphyAutocompletionMatch *mi = &p->matches.array[i];
+			const gchar *realmatch = mi->title + mi->offset;
+			if (!p->common_prefix)
+			{
+				p->common_prefix = g_strdup (realmatch);
+				common_length = strlen (p->common_prefix);
+				continue;
+			}
+			else if (!strncmp (realmatch, p->common_prefix, common_length))
+			{
+				continue;
+			}
+			else
+			{
+				common_length = 0;
+				while (realmatch[common_length]
+				       && realmatch[common_length] == p->common_prefix[common_length])
+				{
+					++common_length;
+				}
+				g_free (p->common_prefix);
+				p->common_prefix = g_strndup (realmatch, common_length);
+			}
+		}
+#ifdef DEBUG_TIME
+		DEBUG_MSG (("AC: %f elapsed calculating common prefix\n", g_timer_elapsed (timer, NULL)));
+		g_timer_destroy (timer);
+#endif
+	}
+	return g_strdup (p->common_prefix);
+}
+
+const EphyAutocompletionMatch *
+ephy_autocompletion_get_matches (EphyAutocompletion *ac)
+{
+	ephy_autocompletion_update_matches (ac);
+	return ac->priv->matches.array;
+}
+
+const EphyAutocompletionMatch *
+ephy_autocompletion_get_matches_sorted_by_score (EphyAutocompletion *ac,
+						 gboolean *changed)
+{
+	*changed = ephy_autocompletion_sort_by_score (ac);
+	return ac->priv->matches.array;
+}
+
+guint
+ephy_autocompletion_get_num_matches (EphyAutocompletion *ac)
+{
+	ephy_autocompletion_update_matches (ac);
+
+	return ac->priv->matches.num_matches;
+}
+
+guint
+ephy_autocompletion_get_num_action_matches (EphyAutocompletion *ac)
+{
+	return ac->priv->matches.num_matches -
+		ac->priv->matches.num_action_matches;
+}
+
+static void
+ephy_autocompletion_refine_matches (EphyAutocompletion *ac)
+{
+	EphyAutocompletionPrivate *p = ac->priv;
+	ACMatchArray oldmatches = p->matches;
+	ACMatchArray newmatches;
+	guint i;
+	gchar *key0 = p->keys[0];
+	guint key0l = p->key_lengths[0];
+#ifdef DEBUG_TIME
+	GTimer *timer = g_timer_new ();
+#endif
+	DEBUG_MSG (("AC: refining\n"));
+
+#ifdef DEBUG_TIME
+	g_timer_start (timer);
+#endif
+	acma_init (&newmatches);
+
+	p->changed = FALSE;
+
+	for (i = 0; i < oldmatches.num_matches; i++)
+	{
+		EphyAutocompletionMatch *mi = &oldmatches.array[i];
+		if (mi->is_action ||
+		    (mi->substring && g_strrstr (mi->match, p->keys[0])) ||
+		    !strncmp (key0, mi->title + mi->offset, key0l))
+		{
+			acma_append (&newmatches, mi, mi->is_action);
+		}
+		else
+		{
+			p->changed = TRUE;
+		}
+	}
+
+	acma_destroy (&oldmatches);
+	p->matches = newmatches;
+
+#ifdef DEBUG_TIME
+	DEBUG_MSG (("AC: %f elapsed refining\n", g_timer_elapsed (timer, NULL)));
+	g_timer_destroy (timer);
+#endif
+	DEBUG_MSG (("AC: %d matches\n", p->matches.num_matches));
+}
+
+static void
+ephy_autocompletion_update_matches (EphyAutocompletion *ac)
+{
+	EphyAutocompletionPrivate *p = ac->priv;
+	if (p->status == GAS_UPDATED)
+	{
+		return;
+	}
+	if (p->status == GAS_NEEDS_FULL_UPDATE)
+	{
+		ephy_autocompletion_update_matches_full (ac);
+	}
+	if (p->status == GAS_NEEDS_REFINE)
+	{
+		/* FIXME we do full update for now */
+		ephy_autocompletion_refine_matches (ac);
+	}
+
+	g_free (p->common_prefix);
+	p->common_prefix = NULL;
+	p->status = GAS_UPDATED;
+}
+
+static void
+ephy_autocompletion_update_matches_full_item (EphyAutocompletionSource *source,
+					      const char *item,
+					      const char *title,
+					      const char *target,
+					      gboolean is_action,
+					      gboolean substring,
+					      guint32 score,
+					      EphyAutocompletionPrivate *p)
+{
+	if (is_action ||
+	    (substring && g_strrstr (item, p->keys[0])))
+	{
+		EphyAutocompletionMatch m;
+		m.match = item;
+		m.title = title;
+		m.target = target;
+		m.is_action = is_action;
+		m.substring = substring;
+		m.offset = 0;
+		m.score = score;
+		acma_append (&p->matches, &m, is_action);
+	}
+	else
+	{
+		guint i;
+		for (i = 0; p->keys[i]; ++i)
+		{
+			if (!strncmp (item, p->keys[i], p->key_lengths[i]))
+			{
+				EphyAutocompletionMatch m;
+				m.match = item;
+				m.title = title;
+				m.target = target;
+				m.is_action = is_action;
+				m.substring = substring;
+				m.offset = p->prefix_lengths[i];
+				m.score = score;
+				acma_append (&p->matches, &m, is_action);
+			}
+		}
+	}
+}
+
+static void
+ephy_autocompletion_update_matches_full (EphyAutocompletion *ac)
+{
+	EphyAutocompletionPrivate *p = ac->priv;
+	GSList *li;
+#ifdef DEBUG_TIME
+	GTimer *timer = g_timer_new ();
+#endif
+
+	DEBUG_MSG (("AC: fully updating\n"));
+	ephy_autocompletion_reset (ac);
+
+#ifdef DEBUG_TIME
+	g_timer_start (timer);
+#endif
+	for (li = p->sources; li; li = li->next)
+	{
+		EphyAutocompletionSource *s = EPHY_AUTOCOMPLETION_SOURCE (li->data);
+		g_assert (s);
+		ephy_autocompletion_source_foreach (s, p->keys[0],
+						    (EphyAutocompletionSourceForeachFunc)
+						    ephy_autocompletion_update_matches_full_item,
+						    p);
+	}
+#ifdef DEBUG_TIME
+	DEBUG_MSG (("AC: %f elapsed fully updating\n", g_timer_elapsed (timer, NULL)));
+	g_timer_destroy (timer);
+#endif
+
+	p->sorted = FALSE;
+	p->changed = TRUE;
+
+	DEBUG_MSG (("AC: %d matches, fully updated\n", p->matches.num_matches));
+}
+
+static gint
+ephy_autocompletion_compare_scores (EphyAutocompletionMatch *a, EphyAutocompletionMatch *b)
+{
+	/* higher scores first */
+	return b->score - a->score;
+}
+
+static gint
+ephy_autocompletion_compare_scores_and_alpha (EphyAutocompletionMatch *a, EphyAutocompletionMatch *b)
+{
+	if (a->score == b->score)
+	{
+		return strcmp (a->title, b->title);
+	}
+	else
+	{
+		/* higher scores first */
+		return b->score - a->score;
+	}
+}
+
+static gboolean
+ephy_autocompletion_sort_by_score (EphyAutocompletion *ac)
+{
+	EphyAutocompletionPrivate *p = ac->priv;
+#ifdef DEBUG_TIME
+	GTimer *timer;
+#endif
+	gint (*comparer) (EphyAutocompletionMatch *m1, EphyAutocompletionMatch *m2);
+
+	if (p->sort_alpha)
+	{
+		comparer = ephy_autocompletion_compare_scores_and_alpha;
+	}
+	else
+	{
+		comparer = ephy_autocompletion_compare_scores;
+	}
+
+	ephy_autocompletion_update_matches (ac);
+	if (p->changed == FALSE) return FALSE;
+
+	DEBUG_MSG (("AC: sorting\n"));
+#ifdef DEBUG_TIME
+	timer = g_timer_new ();
+	g_timer_start (timer);
+#endif
+	if (p->matches.num_matches > 0)
+	{
+		qsort (p->matches.array, p->matches.num_matches,
+		       sizeof (EphyAutocompletionMatch),
+		       (void *) comparer);
+	}
+
+	p->sorted = TRUE;
+
+#ifdef DEBUG_TIME
+	DEBUG_MSG (("AC: %f elapsed sorting by score\n", g_timer_elapsed (timer, NULL)));
+	g_timer_destroy (timer);
+#endif
+	return TRUE;
+}
+
+static void
+ephy_autocompletion_data_changed_cb (EphyAutocompletionSource *s,
+				     EphyAutocompletion *ac)
+{
+	DEBUG_MSG (("AC: data changed, reseting\n"));
+	ephy_autocompletion_reset (ac);
+
+	g_signal_emit (ac, EphyAutocompletionSignals[EPHY_AUTOCOMPLETION_SOURCES_CHANGED], 0);
+}
+
+void
+ephy_autocompletion_set_prefixes (EphyAutocompletion *ac,
+				  const gchar **prefixes)
+{
+	EphyAutocompletionPrivate *p = ac->priv;
+	guint nprefixes = 0;
+	gchar *oldkey = g_strdup (p->keys[0]);
+	guint i;
+
+	/* count prefixes */
+	while (prefixes[nprefixes])
+	{
+		++nprefixes;
+	}
+
+	nprefixes--;
+
+	g_strfreev (p->keys);
+	g_free (p->key_lengths);
+	g_strfreev (p->prefixes);
+	g_free (p->prefix_lengths);
+
+	p->prefixes = g_new0 (gchar *, nprefixes + 2);
+	p->prefix_lengths = g_new0 (guint, nprefixes + 2);
+	p->keys = g_new0 (gchar *, nprefixes + 2);
+	p->key_lengths = g_new0 (guint, nprefixes + 2);
+
+	p->prefixes[0] = g_strdup ("");
+	p->prefix_lengths[0] = 0;
+	p->keys[0] = oldkey;
+	p->key_lengths[0] = strlen (p->keys[0]);
+
+	for (i = 0; i < nprefixes; ++i)
+	{
+		p->prefixes[i + 1] = g_strdup (prefixes[i]);
+		p->prefix_lengths[i + 1] = strlen (prefixes[i]);
+		p->keys[i + 1] = g_strconcat (p->prefixes[i + 1], p->keys[0], NULL);
+		p->key_lengths[i + 1] = p->prefix_lengths[i + 1] + p->key_lengths[0];
+	}
+
+	p->nkeys = nprefixes;
+}
+
+
+/* ACMatchArray */
+
+static void
+acma_init (ACMatchArray *a)
+{
+	a->array = NULL;
+	a->array_size = 0;
+	a->num_matches = 0;
+}
+
+/**
+ * Does not free the struct itself, only its contents
+ */
+static void
+acma_destroy (ACMatchArray *a)
+{
+	g_free (a->array);
+	a->array = NULL;
+	a->array_size = 0;
+	a->num_matches = 0;
+	a->num_action_matches = 0;
+}
+
+static inline void
+acma_append (ACMatchArray *a,
+	     EphyAutocompletionMatch *m,
+	     gboolean action)
+{
+	if (a->array_size == a->num_matches)
+	{
+		acma_grow (a);
+	}
+
+	a->array[a->num_matches] = *m;
+	a->num_matches++;
+	if (action) a->num_action_matches++;
+}
+
+static void
+acma_grow (ACMatchArray *a)
+{
+	gint new_size;
+	EphyAutocompletionMatch *new_array;
+
+	new_size = a->array_size + ACMA_BASE_SIZE;
+	new_array = g_renew (EphyAutocompletionMatch, a->array, new_size);
+
+	a->array_size = new_size;
+	a->array = new_array;
+}
+
+