[gtksourceview/wip/search] search: transfrom recursive functions into loops

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

commit 6f4c01a2bd3427fe74206852cebad8e11c47ede4
Author: Sébastien Wilmet <swilmet gnome org>
Date:   Sat Jul 6 13:01:53 2013 +0200

    search: transfrom recursive functions into loops
    
    To avoid stack overflows.

 gtksourceview/gtksourcesearch.c |  266 +++++++++++++++++++++++++--------------
 1 files changed, 172 insertions(+), 94 deletions(-)
---
diff --git a/gtksourceview/gtksourcesearch.c b/gtksourceview/gtksourcesearch.c
index 58c8b2a..6b3fe66 100644
--- a/gtksourceview/gtksourcesearch.c
+++ b/gtksourceview/gtksourcesearch.c
@@ -471,11 +471,12 @@ forward_backward_data_free (ForwardBackwardData *data)
        g_slice_free (ForwardBackwardData, data);
 }
 
-static void
-smart_forward_search_async (GtkSourceSearch   *search,
-                           const GtkTextIter *start_at,
-                           GTask             *task,
-                           gboolean           wrapped_around)
+/* Returns TRUE if finished. */
+static gboolean
+smart_forward_search_async_step (GtkSourceSearch *search,
+                                GtkTextIter     *start_at,
+                                GTask           *task,
+                                gboolean        *wrapped_around)
 {
        GtkTextIter iter = *start_at;
        GtkTextIter limit;
@@ -485,32 +486,25 @@ smart_forward_search_async (GtkSourceSearch   *search,
        if (gtk_text_iter_is_end (start_at))
        {
                if (search->priv->text != NULL &&
-                   !wrapped_around &&
+                   !*wrapped_around &&
                    search->priv->wrap_around)
                {
-                       GtkTextIter start_iter;
-                       gtk_text_buffer_get_start_iter (search->priv->buffer, &start_iter);
-
-                       smart_forward_search_async (search, &start_iter, task, TRUE);
-                       return;
+                       gtk_text_buffer_get_start_iter (search->priv->buffer, start_at);
+                       *wrapped_around = TRUE;
+                       return FALSE;
                }
 
                task_data = g_slice_new0 (ForwardBackwardData);
                task_data->found = FALSE;
                task_data->is_forward = TRUE;
-               task_data->wrapped_around = wrapped_around;
+               task_data->wrapped_around = *wrapped_around;
 
                g_task_return_pointer (task,
                                       task_data,
                                       (GDestroyNotify)forward_backward_data_free);
 
                g_object_unref (task);
-               return;
-       }
-
-       if (search->priv->found_tag == NULL)
-       {
-               init_found_tag (search);
+               return TRUE;
        }
 
        if (!gtk_text_iter_has_tag (&iter, search->priv->found_tag))
@@ -546,23 +540,23 @@ smart_forward_search_async (GtkSourceSearch   *search,
                        task_data->match_start = match_start;
                        task_data->match_end = match_end;
                        task_data->is_forward = TRUE;
-                       task_data->wrapped_around = wrapped_around;
+                       task_data->wrapped_around = *wrapped_around;
 
                        g_task_return_pointer (task,
                                               task_data,
                                               (GDestroyNotify)forward_backward_data_free);
 
                        g_object_unref (task);
-                       return;
+                       return TRUE;
                }
 
-               smart_forward_search_async (search, &limit, task, wrapped_around);
-               return;
+               *start_at = limit;
+               return FALSE;
        }
 
        task_data = g_slice_new0 (ForwardBackwardData);
        task_data->is_forward = TRUE;
-       task_data->wrapped_around = wrapped_around;
+       task_data->wrapped_around = *wrapped_around;
        task_data->start_at = gtk_text_buffer_create_mark (search->priv->buffer,
                                                           NULL,
                                                           start_at,
@@ -577,13 +571,40 @@ smart_forward_search_async (GtkSourceSearch   *search,
        search->priv->task_region = region;
 
        install_idle_scan (search);
+
+       /* The idle that scan the task region will call
+        * smart_forward_search_async() to continue the task. But for the
+        * moment, we are done.
+        */
+       return TRUE;
 }
 
 static void
-smart_backward_search_async (GtkSourceSearch   *search,
-                            const GtkTextIter *start_at,
-                            GTask             *task,
-                            gboolean           wrapped_around)
+smart_forward_search_async (GtkSourceSearch   *search,
+                           const GtkTextIter *start_at,
+                           GTask             *task,
+                           gboolean           wrapped_around)
+{
+       GtkTextIter iter = *start_at;
+
+       if (search->priv->found_tag == NULL)
+       {
+               init_found_tag (search);
+       }
+
+       /* A recursive function would have been more natural, but a loop is
+        * better to avoid stack overflows.
+        */
+       while (!smart_forward_search_async_step (search, &iter, task, &wrapped_around));
+}
+
+
+/* Returns TRUE if finished. */
+static gboolean
+smart_backward_search_async_step (GtkSourceSearch *search,
+                                 GtkTextIter     *start_at,
+                                 GTask           *task,
+                                 gboolean        *wrapped_around)
 {
        GtkTextIter iter = *start_at;
        GtkTextIter limit;
@@ -593,32 +614,25 @@ smart_backward_search_async (GtkSourceSearch   *search,
        if (gtk_text_iter_is_start (start_at))
        {
                if (search->priv->text != NULL &&
-                   !wrapped_around &&
+                   !*wrapped_around &&
                    search->priv->wrap_around)
                {
-                       GtkTextIter end_iter;
-                       gtk_text_buffer_get_end_iter (search->priv->buffer, &end_iter);
-
-                       smart_backward_search_async (search, &end_iter, task, TRUE);
-                       return;
+                       gtk_text_buffer_get_end_iter (search->priv->buffer, start_at);
+                       *wrapped_around = TRUE;
+                       return FALSE;
                }
 
                task_data = g_slice_new0 (ForwardBackwardData);
                task_data->found = FALSE;
                task_data->is_forward = FALSE;
-               task_data->wrapped_around = wrapped_around;
+               task_data->wrapped_around = *wrapped_around;
 
                g_task_return_pointer (task,
                                       task_data,
                                       (GDestroyNotify)forward_backward_data_free);
 
                g_object_unref (task);
-               return;
-       }
-
-       if (search->priv->found_tag == NULL)
-       {
-               init_found_tag (search);
+               return TRUE;
        }
 
        if (gtk_text_iter_begins_tag (&iter, search->priv->found_tag) ||
@@ -656,23 +670,23 @@ smart_backward_search_async (GtkSourceSearch   *search,
                        task_data->match_start = match_start;
                        task_data->match_end = match_end;
                        task_data->is_forward = FALSE;
-                       task_data->wrapped_around = wrapped_around;
+                       task_data->wrapped_around = *wrapped_around;
 
                        g_task_return_pointer (task,
                                               task_data,
                                               (GDestroyNotify)forward_backward_data_free);
 
                        g_object_unref (task);
-                       return;
+                       return TRUE;
                }
 
-               smart_backward_search_async (search, &limit, task, wrapped_around);
-               return;
+               *start_at = limit;
+               return FALSE;
        }
 
        task_data = g_slice_new0 (ForwardBackwardData);
        task_data->is_forward = FALSE;
-       task_data->wrapped_around = wrapped_around;
+       task_data->wrapped_around = *wrapped_around;
        task_data->start_at = gtk_text_buffer_create_mark (search->priv->buffer,
                                                           NULL,
                                                           start_at,
@@ -687,6 +701,31 @@ smart_backward_search_async (GtkSourceSearch   *search,
        search->priv->task_region = region;
 
        install_idle_scan (search);
+
+       /* The idle that scan the task region will call
+        * smart_backward_search_async() to continue the task. But for the
+        * moment, we are done.
+        */
+       return TRUE;
+}
+
+static void
+smart_backward_search_async (GtkSourceSearch   *search,
+                            const GtkTextIter *start_at,
+                            GTask             *task,
+                            gboolean           wrapped_around)
+{
+       GtkTextIter iter = *start_at;
+
+       if (search->priv->found_tag == NULL)
+       {
+               init_found_tag (search);
+       }
+
+       /* A recursive function would have been more natural, but a loop is
+        * better to avoid stack overflows.
+        */
+       while (!smart_backward_search_async_step (search, &iter, task, &wrapped_around));
 }
 
 /* Adjust the subregion so we are sure that all matches that are visible or
@@ -842,13 +881,11 @@ smart_forward_search_without_scanning (GtkSourceSearch   *search,
                                       const GtkTextIter *stop_at)
 {
        GtkTextIter iter = *start_at;
-       GtkTextIter limit;
 
        g_assert (start_at != NULL);
        g_assert (stop_at != NULL);
 
-       if (gtk_text_iter_compare (stop_at, start_at) <= 0 ||
-           search->priv->text == NULL)
+       if (search->priv->text == NULL)
        {
                return FALSE;
        }
@@ -858,29 +895,32 @@ smart_forward_search_without_scanning (GtkSourceSearch   *search,
                init_found_tag (search);
        }
 
-       if (!gtk_text_iter_has_tag (&iter, search->priv->found_tag))
+       while (gtk_text_iter_compare (&iter, stop_at) < 0)
        {
-               gtk_text_iter_forward_to_tag_toggle (&iter, search->priv->found_tag);
-       }
+               GtkTextIter limit;
 
-       limit = iter;
-       gtk_text_iter_forward_to_tag_toggle (&limit, search->priv->found_tag);
+               if (!gtk_text_iter_has_tag (&iter, search->priv->found_tag))
+               {
+                       gtk_text_iter_forward_to_tag_toggle (&iter, search->priv->found_tag);
+               }
 
-       if (gtk_text_iter_compare (stop_at, &limit) < 0)
-       {
-               limit = *stop_at;
-       }
+               limit = iter;
+               gtk_text_iter_forward_to_tag_toggle (&limit, search->priv->found_tag);
 
-       if (basic_forward_search (search, &iter, match_start, match_end, &limit))
-       {
-               return TRUE;
+               if (gtk_text_iter_compare (stop_at, &limit) < 0)
+               {
+                       limit = *stop_at;
+               }
+
+               if (basic_forward_search (search, &iter, match_start, match_end, &limit))
+               {
+                       return TRUE;
+               }
+
+               iter = limit;
        }
 
-       return smart_forward_search_without_scanning (search,
-                                                     &limit,
-                                                     match_start,
-                                                     match_end,
-                                                     stop_at);
+       return FALSE;
 }
 
 /* Remove the occurrences in the range. @start and @end may be adjusted, if they
@@ -1220,28 +1260,17 @@ install_idle_scan (GtkSourceSearch *search)
        }
 }
 
-/* Doesn't wrap around. */
+/* Returns TRUE when finished. */
 static gboolean
-smart_forward_search (GtkSourceSearch   *search,
-                     const GtkTextIter *start_at,
-                     GtkTextIter       *match_start,
-                     GtkTextIter       *match_end)
+smart_forward_search_step (GtkSourceSearch *search,
+                          GtkTextIter     *start_at,
+                          GtkTextIter     *match_start,
+                          GtkTextIter     *match_end)
 {
        GtkTextIter iter = *start_at;
        GtkTextIter limit;
        GtkTextRegion *region = NULL;
 
-       if (gtk_text_iter_is_end (start_at) ||
-           search->priv->text == NULL)
-       {
-               return FALSE;
-       }
-
-       if (search->priv->found_tag == NULL)
-       {
-               init_found_tag (search);
-       }
-
        if (!gtk_text_iter_has_tag (&iter, search->priv->found_tag))
        {
                gtk_text_iter_forward_to_tag_toggle (&iter, search->priv->found_tag);
@@ -1269,28 +1298,25 @@ smart_forward_search (GtkSourceSearch   *search,
                        return TRUE;
                }
 
-               return smart_forward_search (search, &limit, match_start, match_end);
+               *start_at = limit;
+               return FALSE;
        }
 
        scan_all_region (search, region);
        gtk_text_region_destroy (region, TRUE);
-
-       return smart_forward_search (search, start_at, match_start, match_end);
+       return FALSE;
 }
 
 /* Doesn't wrap around. */
 static gboolean
-smart_backward_search (GtkSourceSearch   *search,
-                      const GtkTextIter *start_at,
-                      GtkTextIter       *match_start,
-                      GtkTextIter       *match_end)
+smart_forward_search (GtkSourceSearch   *search,
+                     const GtkTextIter *start_at,
+                     GtkTextIter       *match_start,
+                     GtkTextIter       *match_end)
 {
        GtkTextIter iter = *start_at;
-       GtkTextIter limit;
-       GtkTextRegion *region = NULL;
 
-       if (gtk_text_iter_is_start (start_at) ||
-           search->priv->text == NULL)
+       if (search->priv->text == NULL)
        {
                return FALSE;
        }
@@ -1300,6 +1326,28 @@ smart_backward_search (GtkSourceSearch   *search,
                init_found_tag (search);
        }
 
+       while (!gtk_text_iter_is_end (&iter))
+       {
+               if (smart_forward_search_step (search, &iter, match_start, match_end))
+               {
+                       return TRUE;
+               }
+       }
+
+       return FALSE;
+}
+
+/* Returns TRUE when finished. */
+static gboolean
+smart_backward_search_step (GtkSourceSearch *search,
+                           GtkTextIter     *start_at,
+                           GtkTextIter     *match_start,
+                           GtkTextIter     *match_end)
+{
+       GtkTextIter iter = *start_at;
+       GtkTextIter limit;
+       GtkTextRegion *region = NULL;
+
        if (gtk_text_iter_begins_tag (&iter, search->priv->found_tag) ||
            (!gtk_text_iter_has_tag (&iter, search->priv->found_tag) &&
             !gtk_text_iter_ends_tag (&iter, search->priv->found_tag)))
@@ -1329,13 +1377,43 @@ smart_backward_search (GtkSourceSearch   *search,
                        return TRUE;
                }
 
-               return smart_backward_search (search, &limit, match_start, match_end);
+               *start_at = limit;
+               return FALSE;
        }
 
        scan_all_region (search, region);
        gtk_text_region_destroy (region, TRUE);
+       return FALSE;
+}
 
-       return smart_backward_search (search, start_at, match_start, match_end);
+/* Doesn't wrap around. */
+static gboolean
+smart_backward_search (GtkSourceSearch   *search,
+                      const GtkTextIter *start_at,
+                      GtkTextIter       *match_start,
+                      GtkTextIter       *match_end)
+{
+       GtkTextIter iter = *start_at;
+
+       if (search->priv->text == NULL)
+       {
+               return FALSE;
+       }
+
+       if (search->priv->found_tag == NULL)
+       {
+               init_found_tag (search);
+       }
+
+       while (!gtk_text_iter_is_start (&iter))
+       {
+               if (smart_backward_search_step (search, &iter, match_start, match_end))
+               {
+                       return TRUE;
+               }
+       }
+
+       return FALSE;
 }
 
 static void