/* -*- 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 UTF-8 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.

 *

 * This function assumes that @prefix and the strings contained in @completion

 * are in UTF-8. If all the strings are valid UTF-8, then the return value will

 * also be valid UTF-8 (it won't return a partial multi-byte character).

 *

 * 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;

}