/* -*- Mode: C; tab-width: 8; indent-tabs-mode: t; c-basic-offset: 8 -*- */

/*

 * gtksourceundomanagerdefault.c

 * This file is part of GtkSourceView

 *

 * Copyright (C) 1998, 1999 - Alex Roberts, Evan Lawrence

 * Copyright (C) 2000, 2001 - Chema Celorio, Paolo Maggi

 * Copyright (C) 2002-2005  - Paolo Maggi

 * Copyright (C) 2014, 2015 - Sébastien Wilmet <swilmet@gnome.org>

 *

 * This library is free software; you can redistribute it and/or

 * modify it under the terms of the GNU Lesser General Public

 * License as published by the Free Software Foundation; either

 * version 2.1 of the License, or (at your option) any later version.

 *

 * This library 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

 * Lesser General Public License for more details.

 *

 * You should have received a copy of the GNU Lesser General Public

 * License along with this library; if not, write to the Free Software

 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA

 */

#include "gtksourceundomanagerdefault.h"

#include <string.h>

#include "gtksourceundomanager.h"

/* unlimited by default */

#define DEFAULT_MAX_UNDO_LEVELS -1

typedef struct _Action		Action;

typedef struct _ActionGroup	ActionGroup;

typedef enum _ActionType

{

	ACTION_TYPE_INSERT,

	ACTION_TYPE_DELETE

} ActionType;

/* A more precise deletion type. But currently it's only a guess, we are not

 * 100% sure of the deletion type. To be sure, we would need to listen to key

 * events on the GtkSourceView widget, which is more complicated than simply

 * listening to the insert-text and delete-range GtkTextBuffer signals.

 */

typedef enum _DeletionType

{

	DELETION_TYPE_SELECTION_DELETED,

	DELETION_TYPE_BACKSPACE_KEY,

	DELETION_TYPE_DELETE_KEY,

	DELETION_TYPE_PROGRAMMATICALLY

} DeletionType;

struct _Action

{

	ActionType type;

	/* Character offset for the start of @text in the GtkTextBuffer. */

	gint start;

	/* Character offset for the end of @text in the GtkTextBuffer. */

	gint end;

	/* Nul-terminated text.

	 * TODO A possible memory optimization is to store the text only when

	 * needed. For an insertion that is located in the history on the undo

	 * side, the text is not needed since it is already present in the

	 * buffer. The same for a deletion on the redo side. But the last action

	 * text is needed for the merging.

	 */

	gchar *text;

	/* Character offsets of the insert and selection bound marks.

	 * They are both -1 or they both match @start or @end.

	 * If the text cursor or the selected text is not related to the action,

	 * the selection is not stored (i.e. -1).

	 * If not -1, when undoing or redoing an action, the insert and

	 * selection bound marks are restored to where they were.

	 * For an insert, @selection_insert and @selection_bound must match

	 * @start, otherwise the selection or cursor position is unrelated to

	 * the insertion.

	 * For a deletion, if @selection_insert and @selection_bound are -1, it

	 * corresponds to DELETION_TYPE_PROGRAMMATICALLY. For all the other

	 * deletion types, the selection is stored.

	 */

	gint selection_insert;

	gint selection_bound;

};

struct _ActionGroup

{

	/* One or several Action's that forms a single undo or redo step. The

	 * most recent action is at the end of the list.

	 * In fact, actions can be grouped with

	 * gtk_text_buffer_begin_user_action() and

	 * gtk_text_buffer_end_user_action().

	 */

	GQueue *actions;

	/* If force_not_mergeable is FALSE, there are dynamic checks to see if

	 * the action group is mergeable. For example if the saved_location is

	 * just after the action group, the action group is not mergeable, so

	 * the saved_location isn't lost.

	 */

	guint force_not_mergeable : 1;

};

struct _GtkSourceUndoManagerDefaultPrivate

{

	/* Weak ref to the buffer. */

	GtkTextBuffer *buffer;

	/* List of ActionGroup's. The most recent ActionGroup is at the end of

	 * the list.

	 */

	GQueue *action_groups;

	/* Current location in 'action_groups', where we are located in the

	 * history. The redo steps are on the right of the pointer, and the undo

	 * steps are on the left. In other words, the next redo step is

	 * location->data. The next undo step is location->prev->data. But the

	 * location should not be seen as a node, it should be seen as a

	 * vertical bar between two nodes, like a GtkTextIter between two

	 * characters.

	 */

	GList *location;

	/* A new ActionGroup that is created when some text is inserted or

	 * deleted in the buffer. As long as a user action is running (when

	 * 'running_user_action' is TRUE) the new actions are inserted into

	 * 'new_action_group'. When the user action ends, we try to merge

	 * 'new_action_group' with the previous ActionGroup in 'action_groups'

	 * (the node on the left of 'location'). If the merging fails, a new

	 * node is inserted on the left of 'location'.

	 */

	ActionGroup *new_action_group;

	/* The number of nested calls to

	 * gtk_source_buffer_begin_not_undoable_action().

	 */

	guint running_not_undoable_actions;

	/* Max number of action groups. */

	gint max_undo_levels;

	/* The location in 'action_groups' where the buffer is saved. I.e. when

	 * gtk_text_buffer_set_modified (buffer, FALSE) was called for the last

	 * time.

	 * NULL is for the end of 'action_groups'.

	 * 'has_saved_location' is FALSE if the history doesn't contain a saved

	 * location.

	 */

	GList *saved_location;

	guint has_saved_location : 1;

	guint can_undo : 1;

	guint can_redo : 1;

	/* Whether we are between a begin-user-action and a end-user-action.

	 * Some operations, like undo and redo, are not allowed during a user

	 * action (it would screw up the history).

	 * At the beginning of a user action, a new action group is created. At

	 * the end of the user action, we try to merge the group with the

	 * previous one. So when an insertion or deletion occurs when

	 * running_user_action is TRUE, we don't need to create a new group. But

	 * when running_user_action is FALSE, we need to put the insertion or

	 * deletion into a new group and try to merge it directly with the

	 * previous group.

	 */

	guint running_user_action : 1;

};

enum

{

	PROP_0,

	PROP_BUFFER,

	PROP_MAX_UNDO_LEVELS

};

static void gtk_source_undo_manager_iface_init (GtkSourceUndoManagerIface *iface);

static gboolean action_merge (Action *action,

			      Action *new_action);

G_DEFINE_TYPE_WITH_CODE (GtkSourceUndoManagerDefault,

			 gtk_source_undo_manager_default,

			 G_TYPE_OBJECT,

			 G_ADD_PRIVATE (GtkSourceUndoManagerDefault)

                         G_IMPLEMENT_INTERFACE (GTK_SOURCE_TYPE_UNDO_MANAGER,

                                                gtk_source_undo_manager_iface_init))

/* Utilities functions */

static Action *

action_new (void)

{

	Action *action;

	action = g_slice_new0 (Action);

	action->selection_insert = -1;

	action->selection_bound = -1;

	return action;

}

static void

action_free (Action *action)

{

	if (action != NULL)

	{

		g_free (action->text);

		g_slice_free (Action, action);

	}

}

static ActionGroup *

action_group_new (void)

{

	ActionGroup *group;

	group = g_slice_new (ActionGroup);

	group->actions = g_queue_new ();

	group->force_not_mergeable = FALSE;

	return group;

}

static void

action_group_free (ActionGroup *group)

{

	if (group != NULL)

	{

		g_queue_free_full (group->actions, (GDestroyNotify) action_free);

		g_slice_free (ActionGroup, group);

	}

}

static void

update_can_undo_can_redo (GtkSourceUndoManagerDefault *manager)

{

	gboolean can_undo;

	gboolean can_redo;

	if (manager->priv->running_user_action)

	{

		can_undo = FALSE;

		can_redo = FALSE;

	}

	else if (manager->priv->location != NULL)

	{

		can_undo = manager->priv->location->prev != NULL;

		can_redo = TRUE;

	}

	else

	{

		can_undo = manager->priv->action_groups->tail != NULL;

		can_redo = FALSE;

	}

	if (manager->priv->can_undo != can_undo)

	{

		manager->priv->can_undo = can_undo;

		gtk_source_undo_manager_can_undo_changed (GTK_SOURCE_UNDO_MANAGER (manager));

	}

	if (manager->priv->can_redo != can_redo)

	{

		manager->priv->can_redo = can_redo;

		gtk_source_undo_manager_can_redo_changed (GTK_SOURCE_UNDO_MANAGER (manager));

	}

}

static void

clear_all (GtkSourceUndoManagerDefault *manager)

{

	GList *l;

	if (manager->priv->has_saved_location &&

	    manager->priv->saved_location != manager->priv->location)

	{

		manager->priv->has_saved_location = FALSE;

	}

	for (l = manager->priv->action_groups->head; l != NULL; l = l->next)

	{

		ActionGroup *group = l->data;

		action_group_free (group);

	}

	g_queue_clear (manager->priv->action_groups);

	manager->priv->location = NULL;

	manager->priv->saved_location = NULL;

	action_group_free (manager->priv->new_action_group);

	manager->priv->new_action_group = NULL;

	update_can_undo_can_redo (manager);

}

static void

remove_last_action_group (GtkSourceUndoManagerDefault *manager)

{

	ActionGroup *group;

	if (manager->priv->action_groups->length == 0)

	{

		return;

	}

	if (manager->priv->location == manager->priv->action_groups->tail)

	{

		manager->priv->location = NULL;

	}

	if (manager->priv->has_saved_location)

	{

		if (manager->priv->saved_location == NULL)

		{

			manager->priv->has_saved_location = FALSE;

		}

		else if (manager->priv->saved_location == manager->priv->action_groups->tail)

		{

			manager->priv->saved_location = NULL;

		}

	}

	group = g_queue_pop_tail (manager->priv->action_groups);

	action_group_free (group);

}

static void

remove_first_action_group (GtkSourceUndoManagerDefault *manager)

{

	GList *first_node;

	ActionGroup *group;

	first_node = manager->priv->action_groups->head;

	if (first_node == NULL)

	{

		return;

	}

	if (manager->priv->location == first_node)

	{

		manager->priv->location = first_node->next;

	}

	if (manager->priv->has_saved_location &&

	    manager->priv->saved_location == first_node)

	{

		manager->priv->has_saved_location = FALSE;

	}

	group = g_queue_pop_head (manager->priv->action_groups);

	action_group_free (group);

}

static void

check_history_size (GtkSourceUndoManagerDefault *manager)

{

	if (manager->priv->max_undo_levels == -1)

	{

		return;

	}

	if (manager->priv->max_undo_levels == 0)

	{

		clear_all (manager);

		return;

	}

	g_return_if_fail (manager->priv->max_undo_levels > 0);

	while (manager->priv->action_groups->length > (guint)manager->priv->max_undo_levels)

	{

		/* Strip redo action groups first. */

		if (manager->priv->location != NULL)

		{

			remove_last_action_group (manager);

		}

		else

		{

			remove_first_action_group (manager);

		}

	}

	update_can_undo_can_redo (manager);

}

static void

remove_redo_action_groups (GtkSourceUndoManagerDefault *manager)

{

	while (manager->priv->location != NULL)

	{

		remove_last_action_group (manager);

	}

}

/* Try to merge @new_group into @group. Returns TRUE if merged. It is up to the

 * caller to free @new_group.

 */

static gboolean

action_group_merge (ActionGroup *group,

		    ActionGroup *new_group)

{

	Action *action;

	Action *new_action;

	g_assert (group != NULL);

	g_assert (new_group != NULL);

	if (new_group->actions->length == 0)

	{

		return TRUE;

	}

	if (group->force_not_mergeable ||

	    new_group->force_not_mergeable ||

	    group->actions->length > 1 ||

	    new_group->actions->length > 1)

	{

		return FALSE;

	}

	action = g_queue_peek_head (group->actions);

	new_action = g_queue_peek_head (new_group->actions);

	return action_merge (action, new_action);

}

/* Try to merge the new action group with the previous one (the one located on

 * the left of priv->location). If the merge fails, a new node is inserted into

 * the history.

 */

static void

insert_new_action_group (GtkSourceUndoManagerDefault *manager)

{

	GList *prev_node = NULL;

	ActionGroup *prev_group = NULL;

	ActionGroup *new_group = manager->priv->new_action_group;

	gboolean can_merge = TRUE;

	if (new_group == NULL || new_group->actions->length == 0)

	{

		return;

	}

	remove_redo_action_groups (manager);

	g_assert (manager->priv->location == NULL);

	prev_node = manager->priv->action_groups->tail;

	if (prev_node != NULL)

	{

		prev_group = prev_node->data;

		/* If the previous group is empty, it means that it was not correctly

		 * inserted into the history.

		 */

		g_assert_cmpuint (prev_group->actions->length, >, 0);

	}

	/* If the saved_location is equal to the current location, the two

	 * ActionGroups cannot be merged, to not lose the saved_location.

	 */

	if (manager->priv->has_saved_location &&

	    manager->priv->saved_location == manager->priv->location)

	{

		g_assert (manager->priv->saved_location == NULL);

		can_merge = FALSE;

	}

	if (can_merge &&

	    prev_group != NULL &&

	    action_group_merge (prev_group, new_group))

	{

		/* new_group merged into prev_group */

		action_group_free (manager->priv->new_action_group);

		manager->priv->new_action_group = NULL;

		update_can_undo_can_redo (manager);

		return;

	}

	g_queue_push_tail (manager->priv->action_groups, new_group);

	manager->priv->new_action_group = NULL;

	if (manager->priv->has_saved_location &&

	    manager->priv->saved_location == NULL)

	{

		manager->priv->saved_location = manager->priv->action_groups->tail;

	}

	/* "Archive" prev_group. It will never be mergeable again. If the user

	 * does some undo's to return to this location, a new action won't be

	 * merged with an "archived" action group.

	 */

	if (prev_group != NULL)

	{

		prev_group->force_not_mergeable = TRUE;

	}

	check_history_size (manager);

	update_can_undo_can_redo (manager);

}

static void

insert_action (GtkSourceUndoManagerDefault *manager,

	       Action                      *new_action)

{

	ActionGroup *new_group;

	g_assert (new_action != NULL);

	if (manager->priv->new_action_group == NULL)

	{

		manager->priv->new_action_group = action_group_new ();

	}

	new_group = manager->priv->new_action_group;

	/* Inside a group, don't try to merge the actions. It is needed to keep

	 * them separate so when undoing or redoing, the cursor position is set

	 * at the right place.

	 * For example with the search and replace, we replace all occurrences

	 * of 'a' by '' (i.e. delete all a's). The text "aaba" becomes "b". On

	 * undo, the cursor position should be placed at "a|aba", not "aa|ba"

	 * (but it's a detail).

	 */

	g_queue_push_tail (new_group->actions, new_action);

	/* An action is mergeable only for an insertion or deletion of a single

	 * character. If the text contains several characters, the new_action

	 * can for example come from a copy/paste.

	 */

	if (new_action->end - new_action->start > 1 ||

	    g_str_equal (new_action->text, "\n"))

	{

		new_group->force_not_mergeable = TRUE;

	}

	if (!manager->priv->running_user_action)

	{

		insert_new_action_group (manager);

	}

}

static void

delete_text (GtkTextBuffer *buffer,

	     gint           start,

	     gint           end)

{

	GtkTextIter start_iter;

	GtkTextIter end_iter;

	gtk_text_buffer_get_iter_at_offset (buffer, &start_iter, start);

	gtk_text_buffer_get_iter_at_offset (buffer, &end_iter, end);

	gtk_text_buffer_begin_user_action (buffer);

	gtk_text_buffer_delete (buffer, &start_iter, &end_iter);

	gtk_text_buffer_end_user_action (buffer);

}

static void

insert_text (GtkTextBuffer *buffer,

	     gint           offset,

	     const gchar   *text)

{

	GtkTextIter iter;

	gtk_text_buffer_get_iter_at_offset (buffer, &iter, offset);

	gtk_text_buffer_begin_user_action (buffer);

	gtk_text_buffer_insert (buffer, &iter, text, -1);

	gtk_text_buffer_end_user_action (buffer);

}

static gunichar

get_last_char (const gchar *text)

{

	gchar *pos;

	pos = g_utf8_find_prev_char (text, text + strlen (text));

	if (pos == NULL)

	{

		return '\0';

	}

	return g_utf8_get_char (pos);

}

/* ActionInsert implementation */

static void

action_insert_undo (GtkTextBuffer *buffer,

		    Action        *action)

{

	g_assert_cmpint (action->type, ==, ACTION_TYPE_INSERT);

	delete_text (buffer, action->start, action->end);

}

static void

action_insert_redo (GtkTextBuffer *buffer,

		    Action        *action)

{

	g_assert_cmpint (action->type, ==, ACTION_TYPE_INSERT);

	insert_text (buffer, action->start, action->text);

}

static gboolean

action_insert_merge (Action *action,

		     Action *new_action)

{

	gint new_text_length;

	gunichar new_char;

	gunichar last_char;

	gchar *merged_text;

	g_assert_cmpint (action->type, ==, ACTION_TYPE_INSERT);

	g_assert_cmpint (new_action->type, ==, ACTION_TYPE_INSERT);

	new_text_length = new_action->end - new_action->start;

	g_assert_cmpint (new_text_length, ==, 1);

	new_char = g_utf8_get_char (new_action->text);

	g_assert (new_char != '\n');

	if (action->end != new_action->start)

	{

		return FALSE;

	}

	last_char = get_last_char (action->text);

	/* If I type character by character the text "hello world", there will

	 * be two actions: "hello" and " world". If I click on undo, only

	 * "hello" remains, not the space. The space makes sense only when

	 * a second word is present.

	 * Note that the spaces or tabs at the beginning of a line (for code

	 * indentation) are removed with the first word of the line. For example

	 * if I type character by character "  return FALSE;", there are two

	 * actions: "  return" and " FALSE;". If I undo two times, maybe I still

	 * want the indentation. But with auto-indent, when we press Enter to

	 * create a newline, the indentation is part of the action that adds the

	 * newline, i.e. we have the three actions "\n  ", "return" and

	 * " FALSE;".

	 */

	if ((new_char == ' ' || new_char == '\t') &&

	    (last_char != ' ' && last_char != '\t'))

	{

		return FALSE;

	}

	merged_text = g_strdup_printf ("%s%s", action->text, new_action->text);

	g_free (action->text);

	action->text = merged_text;

	action->end = new_action->end;

	/* No need to update the selection, action->start is not modified. */

	g_assert ((action->selection_insert == -1 &&

		   action->selection_bound == -1) ||

		  (action->selection_insert == action->start &&

		   action->selection_bound == action->start));

	return TRUE;

}

static void

action_insert_restore_selection (GtkTextBuffer *buffer,

				 Action        *action,

				 gboolean       undo)

{

	GtkTextIter iter;

	g_assert_cmpint (action->type, ==, ACTION_TYPE_INSERT);

	/* No need to take into account action->selection_insert and

	 * action->selection_bound, because:

	 * - If they are both -1, we still want to place the cursor correctly,

	 *   as done below, because if the cursor is not moved the user won't

	 *   see the modification.

	 * - If they are set, their values are both action->start, so the undo

	 *   works as expeceted in this case. The redo is also the expected

	 *   behavior because after inserting a character the cursor is _after_

	 *   the character, not before.

	 */

	if (undo)

	{

		gtk_text_buffer_get_iter_at_offset (buffer, &iter, action->start);

	}

	else /* redo */

	{

		gtk_text_buffer_get_iter_at_offset (buffer, &iter, action->end);

	}

	gtk_text_buffer_place_cursor (buffer, &iter);

}

/* ActionDelete implementation */

static void

action_delete_undo (GtkTextBuffer *buffer,

		    Action        *action)

{

	g_assert_cmpint (action->type, ==, ACTION_TYPE_DELETE);

	insert_text (buffer, action->start, action->text);

}

static void

action_delete_redo (GtkTextBuffer *buffer,

		    Action        *action)

{

	g_assert_cmpint (action->type, ==, ACTION_TYPE_DELETE);

	delete_text (buffer, action->start, action->end);

}

static DeletionType

get_deletion_type (Action *action)

{

	g_assert_cmpint (action->type, ==, ACTION_TYPE_DELETE);

	if (action->selection_insert == -1)

	{

		g_assert_cmpint (action->selection_bound, ==, -1);

		return DELETION_TYPE_PROGRAMMATICALLY;

	}

	if (action->selection_insert == action->end &&

	    action->selection_bound == action->end)

	{

		return DELETION_TYPE_BACKSPACE_KEY;

	}

	if (action->selection_insert == action->start &&

	    action->selection_bound == action->start)

	{

		return DELETION_TYPE_DELETE_KEY;

	}

	g_assert (action->selection_insert == action->start ||

		  action->selection_insert == action->end);

	g_assert (action->selection_bound == action->start ||

		  action->selection_bound == action->end);

	return DELETION_TYPE_SELECTION_DELETED;

}

static gboolean

action_delete_merge (Action *action,

		     Action *new_action)

{

	gint new_text_length;

	gunichar new_char;

	DeletionType deletion_type;

	DeletionType new_deletion_type;

	g_assert_cmpint (action->type, ==, ACTION_TYPE_DELETE);

	g_assert_cmpint (new_action->type, ==, ACTION_TYPE_DELETE);

	new_text_length = new_action->end - new_action->start;

	g_assert_cmpint (new_text_length, ==, 1);

	new_char = g_utf8_get_char (new_action->text);

	g_assert (new_char != '\n');

	deletion_type = get_deletion_type (action);

	new_deletion_type = get_deletion_type (new_action);

	if (deletion_type != new_deletion_type)

	{

		return FALSE;

	}

	switch (deletion_type)

	{

		/* If the user has selected some text and then has deleted it,

		 * it should be seen as a single action group, not mergeable.  A

		 * good reason for that is to correctly restore the selection.

		 */

		case DELETION_TYPE_SELECTION_DELETED:

			return FALSE;

		/* For memory use it would be better to take it into account,

		 * but the code is simpler like that.

		 */

		case DELETION_TYPE_PROGRAMMATICALLY:

			return FALSE;

		/* Two Backspaces or two Deletes must follow each other. In

		 * "abc", if the cursor is at offset 2 and I press the Backspace

		 * key, then move the cursor after 'c' and press Backspace

		 * again, the two deletes won't be merged, since there was a

		 * cursor movement in between.

		 */

		case DELETION_TYPE_DELETE_KEY:

			/* Not consecutive deletes. */

			if (action->start != new_action->start)

			{

				return FALSE;

			}

			break;

		case DELETION_TYPE_BACKSPACE_KEY:

			/* Not consecutive backspaces. */

			if (action->start != new_action->end)

			{

				return FALSE;

			}

			break;

		default:

			g_assert_not_reached ();

	}

	/* Delete key pressed several times. */

	if (action->start == new_action->start)

	{

		gunichar last_char;

		gchar *merged_text;

		last_char = get_last_char (action->text);

		/* Same as action_insert_merge(). */

		if ((new_char == ' ' || new_char == '\t') &&

		    (last_char != ' ' && last_char != '\t'))

		{

			return FALSE;

		}

		merged_text = g_strdup_printf ("%s%s", action->text, new_action->text);

		g_free (action->text);

		action->text = merged_text;

		action->end += new_text_length;

		/* No need to update the selection, action->start is not

		 * modified.

		 */

		g_assert_cmpint (action->selection_insert, ==, action->start);

		g_assert_cmpint (action->selection_bound, ==, action->start);

		return TRUE;

	}

	/* Backspace key pressed several times. */

	if (action->start == new_action->end)

	{

		gunichar last_char;

		gchar *merged_text;

		/* The last char deleted, but since it's with the Backspace key,

		 * it's the first char in action->text.

		 */

		last_char = g_utf8_get_char (action->text);

		/* Same as action_insert_merge(). */

		if ((new_char != ' ' && new_char != '\t') &&

		    (last_char == ' ' || last_char == '\t'))

		{

			return FALSE;

		}

		merged_text = g_strdup_printf ("%s%s", new_action->text, action->text);

		g_free (action->text);

		action->text = merged_text;