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