diff options
Diffstat (limited to 'lib/ephy-autocompletion.c')
| -rw-r--r-- | lib/ephy-autocompletion.c | 664 |
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; +} + + |