[devhelp/wip/completion] Implement DhCompletion, a basic replacement for GCompletion

[Sébastien Wilmet <swilmet src gnome org>]

commit 1e1901b752ed65b7be1f2c02d9a6ff7604242698
Author: Sébastien Wilmet <swilmet gnome org>
Date:   Fri Jan 5 16:22:52 2018 +0100

    Implement DhCompletion, a basic replacement for GCompletion
    
    With unit tests, for something like this it's better.
    
    With the 2018 copyright it sounds futuristic, maybe it's also because it
    uses a better data structure, and maybe because I'm listening to
    electronic music at the same time.

 docs/reference/devhelp-docs.xml     |    5 +
 docs/reference/devhelp-sections.txt |   20 ++
 po/POTFILES.in                      |    1 +
 src/Makefile.am                     |    2 +
 src/devhelp.h                       |    1 +
 src/dh-completion.c                 |  378 +++++++++++++++++++++++++++++++++++
 src/dh-completion.h                 |   64 ++++++
 unit-tests/Makefile.am              |    3 +
 unit-tests/test-completion.c        |  244 ++++++++++++++++++++++
 9 files changed, 718 insertions(+), 0 deletions(-)
---
diff --git a/docs/reference/devhelp-docs.xml b/docs/reference/devhelp-docs.xml
index ae3647d..900e65d 100644
--- a/docs/reference/devhelp-docs.xml
+++ b/docs/reference/devhelp-docs.xml
@@ -42,6 +42,11 @@
       <title>Assistant</title>
       <xi:include href="xml/dh-assistant-view.xml"/>
     </chapter>
+
+    <chapter id="misc">
+      <title>Misc</title>
+      <xi:include href="xml/dh-completion.xml"/>
+    </chapter>
   </part>
 
   <xi:include href="api-breaks.xml"/>
diff --git a/docs/reference/devhelp-sections.txt b/docs/reference/devhelp-sections.txt
index b7cc7fd..06376db 100644
--- a/docs/reference/devhelp-sections.txt
+++ b/docs/reference/devhelp-sections.txt
@@ -87,6 +87,26 @@ dh_book_tree_get_type
 </SECTION>
 
 <SECTION>
+<FILE>dh-completion</FILE>
+DhCompletion
+dh_completion_new
+dh_completion_add_string
+dh_completion_sort
+dh_completion_complete
+dh_completion_aggregate_complete
+<SUBSECTION Standard>
+DH_COMPLETION
+DH_COMPLETION_CLASS
+DH_COMPLETION_GET_CLASS
+DH_IS_COMPLETION
+DH_IS_COMPLETION_CLASS
+DH_TYPE_COMPLETION
+DhCompletionClass
+DhCompletionPrivate
+dh_completion_get_type
+</SECTION>
+
+<SECTION>
 <FILE>dh-keyword-model</FILE>
 DhKeywordModel
 dh_keyword_model_new
diff --git a/po/POTFILES.in b/po/POTFILES.in
index ebaf576..63e98df 100644
--- a/po/POTFILES.in
+++ b/po/POTFILES.in
@@ -11,6 +11,7 @@ src/dh-assistant.ui
 src/dh-assistant-view.c
 src/dh-book.c
 src/dh-book-tree.c
+src/dh-completion.c
 src/dh-keyword-model.c
 src/dh-link.c
 src/dh-main.c
diff --git a/src/Makefile.am b/src/Makefile.am
index 46cb1be..473a62a 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -15,6 +15,7 @@ libdevhelp_public_headers =           \
        dh-book.h                       \
        dh-book-manager.h               \
        dh-book-tree.h                  \
+       dh-completion.h                 \
        dh-init.h                       \
        dh-keyword-model.h              \
        dh-link.h                       \
@@ -26,6 +27,7 @@ libdevhelp_public_c_files =           \
        dh-book.c                       \
        dh-book-manager.c               \
        dh-book-tree.c                  \
+       dh-completion.c                 \
        dh-init.c                       \
        dh-keyword-model.c              \
        dh-link.c                       \
diff --git a/src/devhelp.h b/src/devhelp.h
index a7596cd..c693914 100644
--- a/src/devhelp.h
+++ b/src/devhelp.h
@@ -25,6 +25,7 @@
 #include "dh-book.h"
 #include "dh-book-manager.h"
 #include "dh-book-tree.h"
+#include "dh-completion.h"
 #include "dh-init.h"
 #include "dh-keyword-model.h"
 #include "dh-link.h"
diff --git a/src/dh-completion.c b/src/dh-completion.c
new file mode 100644
index 0000000..9f0f555
--- /dev/null
+++ b/src/dh-completion.c
@@ -0,0 +1,378 @@
+/* -*- Mode: C; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 8 -*- */
+/*
+ * Copyright (C) 2018 Sébastien Wilmet <swilmet gnome org>
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License as
+ * published by the Free Software Foundation; either version 2 of the
+ * License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, see <http://www.gnu.org/licenses/>.
+ */
+
+#include "dh-completion.h"
+#include <string.h>
+
+/**
+ * SECTION:dh-completion
+ * @Title: DhCompletion
+ * @Short_description: Support for automatic string completion
+ *
+ * #DhCompletion is a basic replacement for #GCompletion. #GCompletion (part of
+ * GLib) is deprecated, and doesn't use a great data structure (a simple
+ * #GList). #DhCompletion uses a #GSequence instead, so once the data is sorted
+ * it should be faster. #DhCompletion works only with strings, and copies the
+ * strings.
+ *
+ * #DhCompletion is add-only, strings cannot be removed. But with
+ * dh_completion_aggregate_complete(), a #DhCompletion object can be removed
+ * from the list.
+ */
+
+struct _DhCompletionPrivate {
+        /* Element types: gchar*, owned. */
+        GSequence *sequence;
+};
+
+typedef struct {
+        const gchar *prefix;
+        gsize prefix_bytes_length;
+        gchar *longest_prefix;
+} CompletionData;
+
+G_DEFINE_TYPE_WITH_PRIVATE (DhCompletion, dh_completion, G_TYPE_OBJECT)
+
+static gint
+compare_func (gconstpointer a,
+              gconstpointer b,
+              gpointer      user_data)
+{
+        const gchar *str_a = a;
+        const gchar *str_b = b;
+
+        /* We rely on the fact that if str_a is not equal to str_b but one is
+         * the prefix of the other, the shorter string is sorted before the
+         * longer one (i.e. the shorter string is "less than" the longer
+         * string). See do_complete().
+         */
+
+        return g_strcmp0 (str_a, str_b);
+}
+
+static void
+completion_data_init (CompletionData *data,
+                      const gchar    *prefix)
+{
+        data->prefix = prefix;
+        data->prefix_bytes_length = strlen (prefix);
+        data->longest_prefix = NULL;
+}
+
+static void
+dh_completion_finalize (GObject *object)
+{
+        DhCompletion *completion = DH_COMPLETION (object);
+
+        g_sequence_free (completion->priv->sequence);
+
+        G_OBJECT_CLASS (dh_completion_parent_class)->finalize (object);
+}
+
+static void
+dh_completion_class_init (DhCompletionClass *klass)
+{
+        GObjectClass *object_class = G_OBJECT_CLASS (klass);
+
+        object_class->finalize = dh_completion_finalize;
+}
+
+static void
+dh_completion_init (DhCompletion *completion)
+{
+        completion->priv = dh_completion_get_instance_private (completion);
+
+        completion->priv->sequence = g_sequence_new (g_free);
+}
+
+/**
+ * dh_completion_new:
+ *
+ * Returns: a new #DhCompletion object.
+ * Since: 3.28
+ */
+DhCompletion *
+dh_completion_new (void)
+{
+        return g_object_new (DH_TYPE_COMPLETION, NULL);
+}
+
+/**
+ * dh_completion_add_string:
+ * @completion: a #DhCompletion.
+ * @str: a string.
+ *
+ * Adds a string to the @completion object.
+ *
+ * After adding all the strings you need to call dh_completion_sort().
+ *
+ * Since: 3.28
+ */
+void
+dh_completion_add_string (DhCompletion *completion,
+                          const gchar  *str)
+{
+        g_return_if_fail (DH_IS_COMPLETION (completion));
+        g_return_if_fail (str != NULL);
+
+        g_sequence_append (completion->priv->sequence, g_strdup (str));
+}
+
+/**
+ * dh_completion_sort:
+ * @completion: a #DhCompletion.
+ *
+ * Sorts all the strings. It is required to call this function after adding
+ * strings with dh_completion_add_string().
+ *
+ * Since: 3.28
+ */
+void
+dh_completion_sort (DhCompletion *completion)
+{
+        g_return_if_fail (DH_IS_COMPLETION (completion));
+
+        g_sequence_sort (completion->priv->sequence,
+                         compare_func,
+                         NULL);
+}
+
+static gboolean
+bytes_equal (const gchar *str1_start_pos,
+             const gchar *str1_end_pos,
+             const gchar *str2_start_pos,
+             const gchar *str2_end_pos)
+{
+        const gchar *str1_pos;
+        const gchar *str2_pos;
+
+        for (str1_pos = str1_start_pos, str2_pos = str2_start_pos;
+             str1_pos < str1_end_pos && str2_pos < str2_end_pos;
+             str1_pos++, str2_pos++) {
+                if (*str1_pos != *str2_pos)
+                        return FALSE;
+        }
+
+        return str1_pos == str1_end_pos && str2_pos == str2_end_pos;
+}
+
+/* cur_str must have data->prefix as prefix. */
+static void
+adjust_longest_prefix (CompletionData *data,
+                       const gchar    *cur_str)
+{
+        const gchar *cur_str_pos;
+        gchar *longest_prefix_pos;
+
+        /* Skip the first bytes, they are equal. */
+        cur_str_pos = cur_str + data->prefix_bytes_length;
+        longest_prefix_pos = data->longest_prefix + data->prefix_bytes_length;
+
+        while (*cur_str_pos != '\0' && *longest_prefix_pos != '\0') {
+                const gchar *cur_str_next_pos;
+                gchar *longest_prefix_next_pos;
+
+                cur_str_next_pos = g_utf8_find_next_char (cur_str_pos, NULL);
+                longest_prefix_next_pos = g_utf8_find_next_char (longest_prefix_pos, NULL);
+
+                if (!bytes_equal (cur_str_pos, cur_str_next_pos,
+                                  longest_prefix_pos, longest_prefix_next_pos)) {
+                        break;
+                }
+
+                cur_str_pos = cur_str_next_pos;
+                longest_prefix_pos = longest_prefix_next_pos;
+        }
+
+        if (*longest_prefix_pos != '\0') {
+                /* Shrink data->longest_prefix. */
+                *longest_prefix_pos = '\0';
+        }
+}
+
+/* Returns TRUE to continue the iteration.
+ * cur_str must have data->prefix as prefix.
+ */
+static gboolean
+next_completion_iteration (CompletionData *data,
+                           const gchar    *cur_str)
+{
+        if (cur_str == NULL)
+                return TRUE;
+
+        if (data->longest_prefix == NULL) {
+                data->longest_prefix = g_strdup (cur_str);
+                /* After this point, data->longest_prefix can only shrink. */
+        } else {
+                adjust_longest_prefix (data, cur_str);
+        }
+
+        /* Back to data->prefix, stop the iteration, the longest_prefix can no
+         * longer shrink.
+         */
+        if (g_str_equal (data->longest_prefix, data->prefix)) {
+                g_free (data->longest_prefix);
+                data->longest_prefix = NULL;
+                return FALSE;
+        }
+
+        return TRUE;
+}
+
+/* Like dh_completion_complete() but with @found_string_with_prefix in
+ * addition, to differentiate two different cases when %NULL is returned.
+ *
+ * Another implementation solution: instead of returning (NULL +
+ * found_string_with_prefix=TRUE), return a string equal to @prefix. But it
+ * would be harder to document (because it's less explicit) and less convenient
+ * to use as a public API (I think for a public API we don't want as a return
+ * value a string equal to @prefix).
+ */
+static gchar *
+do_complete (DhCompletion *completion,
+             const gchar  *prefix,
+             gboolean     *found_string_with_prefix)
+{
+        GSequenceIter *iter;
+        CompletionData data;
+
+        if (found_string_with_prefix != NULL)
+                *found_string_with_prefix = FALSE;
+
+        g_return_val_if_fail (DH_IS_COMPLETION (completion), NULL);
+        g_return_val_if_fail (prefix != NULL, NULL);
+
+        iter = g_sequence_search (completion->priv->sequence,
+                                  (gpointer) prefix,
+                                  compare_func,
+                                  NULL);
+
+        /* There can be an exact match just *before* iter, since compare_func
+         * returns 0 in that case.
+         */
+        if (!g_sequence_iter_is_begin (iter)) {
+                GSequenceIter *prev_iter;
+                const gchar *prev_str;
+
+                prev_iter = g_sequence_iter_prev (iter);
+                prev_str = g_sequence_get (prev_iter);
+
+                /* If there is an exact match, the prefix can not be completed. */
+                if (g_str_equal (prev_str, prefix)) {
+                        if (found_string_with_prefix != NULL)
+                                *found_string_with_prefix = TRUE;
+                        return NULL;
+                }
+        }
+
+        completion_data_init (&data, prefix);
+
+        /* All the other strings in the GSequence that have @prefix as prefix
+         * will be *after* iter, see the comment in compare_func().
+         */
+        while (!g_sequence_iter_is_end (iter)) {
+                const gchar *cur_str = g_sequence_get (iter);
+
+                if (!g_str_has_prefix (cur_str, prefix))
+                        break;
+
+                if (found_string_with_prefix != NULL)
+                        *found_string_with_prefix = TRUE;
+
+                if (!next_completion_iteration (&data, cur_str))
+                        break;
+
+                iter = g_sequence_iter_next (iter);
+        }
+
+        return data.longest_prefix;
+}
+
+/**
+ * dh_completion_complete:
+ * @completion: a #DhCompletion.
+ * @prefix: the string to complete.
+ *
+ * This function does the equivalent of:
+ * 1. Searches the data structure of @completion to find all strings that have
+ *    @prefix as prefix.
+ * 2. From the list found at step 1, find the longest prefix that still matches
+ *    all the strings in the list.
+ *
+ * Returns: (transfer full) (nullable): the completed prefix, or %NULL if a
+ * longer prefix has not been found. Free with g_free() when no longer needed.
+ * Since: 3.28
+ */
+gchar *
+dh_completion_complete (DhCompletion *completion,
+                        const gchar  *prefix)
+{
+        return do_complete (completion, prefix, NULL);
+}
+
+/**
+ * dh_completion_aggregate_complete:
+ * @completion_objects: (element-type DhCompletion) (nullable): a #GList of
+ *   #DhCompletion objects.
+ * @prefix: the string to complete.
+ *
+ * The same as dh_completion_complete(), but aggregated for several
+ * #DhCompletion objects.
+ *
+ * Returns: (transfer full) (nullable): the completed prefix, or %NULL if a
+ * longer prefix has not been found. Free with g_free() when no longer needed.
+ * Since: 3.28
+ */
+gchar *
+dh_completion_aggregate_complete (GList       *completion_objects,
+                                  const gchar *prefix)
+{
+        CompletionData data;
+        GList *l;
+
+        g_return_val_if_fail (prefix != NULL, NULL);
+
+        completion_data_init (&data, prefix);
+
+        for (l = completion_objects; l != NULL; l = l->next) {
+                DhCompletion *cur_completion = DH_COMPLETION (l->data);
+                gchar *cur_longest_prefix;
+                gboolean found_string_with_prefix;
+
+                cur_longest_prefix = do_complete (cur_completion,
+                                                  prefix,
+                                                  &found_string_with_prefix);
+
+                if (cur_longest_prefix == NULL && found_string_with_prefix) {
+                        /* Stop the completion, it is not possible to complete
+                         * @prefix.
+                         */
+                        g_free (data.longest_prefix);
+                        return NULL;
+                }
+
+                if (!next_completion_iteration (&data, cur_longest_prefix)) {
+                        g_free (cur_longest_prefix);
+                        break;
+                }
+
+                g_free (cur_longest_prefix);
+        }
+
+        return data.longest_prefix;
+}
diff --git a/src/dh-completion.h b/src/dh-completion.h
new file mode 100644
index 0000000..ea105b4
--- /dev/null
+++ b/src/dh-completion.h
@@ -0,0 +1,64 @@
+/* -*- Mode: C; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 8 -*- */
+/*
+ * Copyright (C) 2018 Sébastien Wilmet <swilmet gnome org>
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License as
+ * published by the Free Software Foundation; either version 2 of the
+ * License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, see <http://www.gnu.org/licenses/>.
+ */
+
+#ifndef DH_COMPLETION_H
+#define DH_COMPLETION_H
+
+#include <glib-object.h>
+
+G_BEGIN_DECLS
+
+#define DH_TYPE_COMPLETION             (dh_completion_get_type ())
+#define DH_COMPLETION(obj)             (G_TYPE_CHECK_INSTANCE_CAST ((obj), DH_TYPE_COMPLETION, DhCompletion))
+#define DH_COMPLETION_CLASS(klass)     (G_TYPE_CHECK_CLASS_CAST ((klass), DH_TYPE_COMPLETION, 
DhCompletionClass))
+#define DH_IS_COMPLETION(obj)          (G_TYPE_CHECK_INSTANCE_TYPE ((obj), DH_TYPE_COMPLETION))
+#define DH_IS_COMPLETION_CLASS(klass)  (G_TYPE_CHECK_CLASS_TYPE ((klass), DH_TYPE_COMPLETION))
+#define DH_COMPLETION_GET_CLASS(obj)   (G_TYPE_INSTANCE_GET_CLASS ((obj), DH_TYPE_COMPLETION, 
DhCompletionClass))
+
+typedef struct _DhCompletion         DhCompletion;
+typedef struct _DhCompletionClass    DhCompletionClass;
+typedef struct _DhCompletionPrivate  DhCompletionPrivate;
+
+struct _DhCompletion {
+        GObject parent;
+
+        DhCompletionPrivate *priv;
+};
+
+struct _DhCompletionClass {
+        GObjectClass parent_class;
+};
+
+GType           dh_completion_get_type                  (void);
+
+DhCompletion *  dh_completion_new                       (void);
+
+void            dh_completion_add_string                (DhCompletion *completion,
+                                                         const gchar  *str);
+
+void            dh_completion_sort                      (DhCompletion *completion);
+
+gchar *         dh_completion_complete                  (DhCompletion *completion,
+                                                         const gchar  *prefix);
+
+gchar *         dh_completion_aggregate_complete        (GList       *completion_objects,
+                                                         const gchar *prefix);
+
+G_END_DECLS
+
+#endif /* DH_COMPLETION_H */
diff --git a/unit-tests/Makefile.am b/unit-tests/Makefile.am
index 64c029f..665ca92 100644
--- a/unit-tests/Makefile.am
+++ b/unit-tests/Makefile.am
@@ -12,6 +12,9 @@ LDADD = $(top_builddir)/src/libdevhelp-core.la        \
 
 UNIT_TEST_PROGS =
 
+UNIT_TEST_PROGS += test-completion
+test_completion_SOURCES = test-completion.c
+
 UNIT_TEST_PROGS += test-link
 test_link_SOURCES = test-link.c
 
diff --git a/unit-tests/test-completion.c b/unit-tests/test-completion.c
new file mode 100644
index 0000000..90d1436
--- /dev/null
+++ b/unit-tests/test-completion.c
@@ -0,0 +1,244 @@
+/* -*- Mode: C; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 8 -*- */
+/*
+ * Copyright (C) 2018 Sébastien Wilmet <swilmet gnome org>
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License as
+ * published by the Free Software Foundation; either version 2 of the
+ * License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, see <http://www.gnu.org/licenses/>.
+ */
+
+#include "devhelp.h"
+
+static void
+test_empty (void)
+{
+        DhCompletion *completion;
+        gchar *result;
+
+        completion = dh_completion_new ();
+        dh_completion_sort (completion);
+
+        result = dh_completion_complete (completion, "daft");
+        g_assert (result == NULL);
+
+        g_object_unref (completion);
+}
+
+static void
+test_empty_string (void)
+{
+        DhCompletion *completion;
+        gchar *result;
+
+        completion = dh_completion_new ();
+        dh_completion_add_string (completion, "daft");
+        dh_completion_sort (completion);
+
+        /* Complete empty string. */
+        result = dh_completion_complete (completion, "");
+        g_assert_cmpstr (result, ==, "daft");
+        g_free (result);
+
+        g_object_unref (completion);
+
+        /* Empty string in DhCompletion. */
+        completion = dh_completion_new ();
+        dh_completion_add_string (completion, "");
+        dh_completion_sort (completion);
+
+        // String not found.
+        result = dh_completion_complete (completion, "a");
+        g_assert (result == NULL);
+        // String found.
+        result = dh_completion_complete (completion, "");
+        g_assert (result == NULL);
+
+        // String found, cannot complete.
+        dh_completion_add_string (completion, "daft");
+        dh_completion_sort (completion);
+        result = dh_completion_complete (completion, "");
+        g_assert (result == NULL);
+
+        // Empty string doesn't have prefix, can complete.
+        result = dh_completion_complete (completion, "d");
+        g_assert_cmpstr (result, ==, "daft");
+        g_free (result);
+
+        g_object_unref (completion);
+}
+
+static void
+test_complete_simple (void)
+{
+        DhCompletion *completion;
+        gchar *result;
+
+        completion = dh_completion_new ();
+
+        dh_completion_add_string (completion, "a");
+        dh_completion_add_string (completion, "ba");
+        dh_completion_add_string (completion, "baa");
+        dh_completion_add_string (completion, "bab");
+        dh_completion_add_string (completion, "c");
+        dh_completion_sort (completion);
+
+        /* Completion possible. */
+        result = dh_completion_complete (completion, "b");
+        g_assert_cmpstr (result, ==, "ba");
+        g_free (result);
+
+        /* Exact match found (among other strings with prefix). */
+        result = dh_completion_complete (completion, "ba");
+        g_assert (result == NULL);
+
+        /* Exact match found (only string with prefix). */
+        result = dh_completion_complete (completion, "bab");
+        g_assert (result == NULL);
+
+        /* No strings with prefix found. */
+        result = dh_completion_complete (completion, "d");
+        g_assert (result == NULL);
+
+        /* Strings with prefix found, but cannot complete. */
+        dh_completion_add_string (completion, "bb");
+        dh_completion_sort (completion);
+        result = dh_completion_complete (completion, "b");
+        g_assert (result == NULL);
+
+        /* Only one string with prefix found. */
+        dh_completion_add_string (completion, "dh_book_new");
+        dh_completion_sort (completion);
+        result = dh_completion_complete (completion, "dh");
+        g_assert_cmpstr (result, ==, "dh_book_new");
+        g_free (result);
+
+        g_object_unref (completion);
+}
+
+static void
+test_utf8 (void)
+{
+        DhCompletion *completion;
+        gchar *result;
+
+        completion = dh_completion_new ();
+
+        /* \300 in octal is the first byte of a 2-bytes UTF-8 char. */
+        dh_completion_add_string (completion, "aa\300\200aa");
+        dh_completion_add_string (completion, "aa\300\200ab");
+        dh_completion_sort (completion);
+
+        result = dh_completion_complete (completion, "a");
+        g_assert_cmpstr (result, ==, "aa\300\200a");
+        g_free (result);
+
+        dh_completion_add_string (completion, "aa\300\201aa");
+        dh_completion_sort (completion);
+
+        result = dh_completion_complete (completion, "a");
+        g_assert_cmpstr (result, ==, "aa"); /* not "aa\300" */
+        g_free (result);
+
+        result = dh_completion_complete (completion, "aa\300\200");
+        g_assert_cmpstr (result, ==, "aa\300\200a");
+        g_free (result);
+
+        result = dh_completion_complete (completion, "aa\300\200a");
+        g_assert (result == NULL);
+
+        result = dh_completion_complete (completion, "aa\300\200aa");
+        g_assert (result == NULL);
+
+        result = dh_completion_complete (completion, "b");
+        g_assert (result == NULL);
+
+        /* 2-bytes char + 3-bytes char. */
+        dh_completion_add_string (completion, "zz\300\200zz");
+        dh_completion_add_string (completion, "zz\340\200\200zz");
+        dh_completion_sort (completion);
+
+        result = dh_completion_complete (completion, "z");
+        g_assert_cmpstr (result, ==, "zz");
+        g_free (result);
+
+        result = dh_completion_complete (completion, "zz");
+        g_assert (result == NULL);
+
+        result = dh_completion_complete (completion, "zz\300\200");
+        g_assert_cmpstr (result, ==, "zz\300\200zz");
+        g_free (result);
+
+        g_object_unref (completion);
+}
+
+static void
+test_aggregate_complete (void)
+{
+        DhCompletion *completion1;
+        DhCompletion *completion2;
+        DhCompletion *completion3;
+        GList *list = NULL;
+        gchar *result;
+
+        completion1 = dh_completion_new ();
+        dh_completion_add_string (completion1, "a");
+        dh_completion_add_string (completion1, "baa");
+        dh_completion_sort (completion1);
+
+        completion2 = dh_completion_new ();
+        dh_completion_add_string (completion2, "ba");
+        dh_completion_sort (completion2);
+
+        completion3 = dh_completion_new ();
+        dh_completion_add_string (completion3, "bb");
+        dh_completion_sort (completion3);
+
+        /* With only completion1. */
+        list = g_list_append (list, completion1);
+        result = dh_completion_aggregate_complete (list, "b");
+        g_assert_cmpstr (result, ==, "baa");
+        g_free (result);
+
+        /* With completion1 and completion2. */
+        list = g_list_append (list, completion2);
+        result = dh_completion_aggregate_complete (list, "b");
+        g_assert_cmpstr (result, ==, "ba");
+        g_free (result);
+
+        /* With the 3 objects. */
+        list = g_list_append (list, completion3);
+        result = dh_completion_aggregate_complete (list, "b");
+        g_assert (result == NULL);
+
+        result = dh_completion_aggregate_complete (list, "ba");
+        g_assert (result == NULL);
+
+        g_object_unref (completion1);
+        g_object_unref (completion2);
+        g_object_unref (completion3);
+        g_list_free (list);
+}
+
+int
+main (int    argc,
+      char **argv)
+{
+        g_test_init (&argc, &argv, NULL);
+
+        g_test_add_func ("/completion/empty", test_empty);
+        g_test_add_func ("/completion/empty_string", test_empty_string);
+        g_test_add_func ("/completion/complete_simple", test_complete_simple);
+        g_test_add_func ("/completion/utf-8", test_utf8);
+        g_test_add_func ("/completion/aggregate_complete", test_aggregate_complete);
+
+        return g_test_run ();
+}