[gtksourceview/wip/search] search: adjust_subregion() that avoids a O(n^2) worst case

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

commit 059abe090d40469f4f04ec487a15d7950c5930fe
Author: Sébastien Wilmet <swilmet gnome org>
Date:   Fri Jun 21 11:22:41 2013 +0200

    search: adjust_subregion() that avoids a O(n^2) worst case

 gtksourceview/gtksourcesearch.c |  131 ++++++++++++++++++++++++++++++++-------
 1 files changed, 109 insertions(+), 22 deletions(-)
---
diff --git a/gtksourceview/gtksourcesearch.c b/gtksourceview/gtksourcesearch.c
index 19bcd4a..c82cb4a 100644
--- a/gtksourceview/gtksourcesearch.c
+++ b/gtksourceview/gtksourcesearch.c
@@ -39,10 +39,7 @@ struct _GtkSourceSearchPrivate
        gint text_nb_lines;
        GtkTextSearchFlags flags;
 
-       /* The region to scan and highlight. If NULL, all the occurrences are
-        * highlighted, i.e. the scan is finished (or a scan was not needed, if
-        * the search is disabled).
-        */
+       /* The region to scan and highlight. If NULL, the scan is finished. */
        GtkTextRegion *region;
 
        /* The region to scan and highlight in priority. I.e. the visible part
@@ -221,19 +218,19 @@ clear_search (GtkSourceSearch *search)
        search->priv->occurrences_count = 0;
 }
 
+/* Adjust the subregion so we are sure that all matches that are visible or
+ * partially visible between @start and @end are highlighted.
+ */
 static void
-highlight_subregion (GtkSourceSearch *search,
-                    GtkTextIter     *start,
-                    GtkTextIter     *end)
+adjust_subregion (GtkSourceSearch *search,
+                 GtkTextIter     *start,
+                 GtkTextIter     *end)
 {
-       GtkTextIter iter;
-       GtkTextIter *limit;
-       gboolean found = TRUE;
+       GtkTextIter initial_start = *start;
+       GtkTextIter initial_end = *end;
 
-       /* Make sure the 'found' tag has the priority over syntax highlighting
-        * tags. */
-       text_tag_set_highest_priority (search->priv->found_tag,
-                                      search->priv->buffer);
+       gtk_text_iter_backward_lines (start, MAX (0, search->priv->text_nb_lines - 1));
+       gtk_text_iter_forward_lines (end, MAX (0, search->priv->text_nb_lines - 1));
 
        if (!gtk_text_iter_starts_line (start))
        {
@@ -245,20 +242,110 @@ highlight_subregion (GtkSourceSearch *search,
                gtk_text_iter_forward_to_line_end (end);
        }
 
-       gtk_text_iter_backward_lines (start, MAX (0, search->priv->text_nb_lines - 1));
-       gtk_text_iter_forward_lines (end, MAX (0, search->priv->text_nb_lines - 1));
+       /* When we are in the middle of a found_tag, a simple solution is to
+        * always backward_to_tag_toggle(). The problem is that occurrences can
+        * be contiguous. So a full scan of the buffer can have a O(n^2) in the
+        * worst case, if we use the simple solution. Therefore we use a more
+        * complicated solution, that checks if we are in an old found_tag or
+        * not.
+        */
 
-       if (gtk_text_iter_has_tag (start, search->priv->found_tag) &&
-           !gtk_text_iter_ends_tag (start, search->priv->found_tag))
+       if (gtk_text_iter_has_tag (start, search->priv->found_tag))
        {
-               gtk_text_iter_forward_to_tag_toggle (start, search->priv->found_tag);
+               if (search->priv->region != NULL)
+               {
+                       GtkTextRegion *region = gtk_text_region_intersect (search->priv->region,
+                                                                          start,
+                                                                          &initial_start);
+
+                       if (is_text_region_empty (region) &&
+                           !gtk_text_iter_ends_tag (start, search->priv->found_tag))
+                       {
+                               /* 'region' has already been scanned, so 'start'
+                                * is in a correct match, we can skip it.
+                                */
+                               gtk_text_iter_forward_to_tag_toggle (start, search->priv->found_tag);
+                       }
+                       else if (!gtk_text_iter_begins_tag (start, search->priv->found_tag))
+                       {
+                               /* 'region' has not already been scanned, so
+                                * 'start' is most probably in an old match that
+                                * must be removed.
+                                */
+                               gtk_text_iter_backward_to_tag_toggle (start, search->priv->found_tag);
+                       }
+
+                       if (region != NULL)
+                       {
+                               gtk_text_region_destroy (region, TRUE);
+                       }
+               }
+               else if (!gtk_text_iter_ends_tag (start, search->priv->found_tag))
+               {
+                       /* All the buffer has been scanned, so 'start' is in a
+                        * correct match, we can skip it.
+                        */
+                       gtk_text_iter_forward_to_tag_toggle (start, search->priv->found_tag);
+               }
        }
 
-       if (gtk_text_iter_has_tag (end, search->priv->found_tag) &&
-           !gtk_text_iter_begins_tag (end, search->priv->found_tag))
+       /* Symmetric for 'end'. */
+
+       if (gtk_text_iter_has_tag (end, search->priv->found_tag))
        {
-               gtk_text_iter_backward_to_tag_toggle (end, search->priv->found_tag);
+               if (search->priv->region != NULL)
+               {
+                       GtkTextRegion *region = gtk_text_region_intersect (search->priv->region,
+                                                                          &initial_end,
+                                                                          end);
+
+                       if (is_text_region_empty (region) &&
+                           !gtk_text_iter_begins_tag (end, search->priv->found_tag))
+                       {
+                               /* 'region' has already been scanned, so 'end'
+                                * is in a correct match, we can skip it.
+                                */
+                               gtk_text_iter_backward_to_tag_toggle (end, search->priv->found_tag);
+                       }
+                       else if (!gtk_text_iter_ends_tag (end, search->priv->found_tag))
+                       {
+                               /* 'region' has not already been scanned, so
+                                * 'end' is most probably in an old match that
+                                * must be removed.
+                                */
+                               gtk_text_iter_forward_to_tag_toggle (end, search->priv->found_tag);
+                       }
+
+                       if (region != NULL)
+                       {
+                               gtk_text_region_destroy (region, TRUE);
+                       }
+               }
+               else if (!gtk_text_iter_begins_tag (end, search->priv->found_tag))
+               {
+                       /* All the buffer has been scanned, so 'end' is in a
+                        * correct match, we can skip it.
+                        */
+                       gtk_text_iter_backward_to_tag_toggle (start, search->priv->found_tag);
+               }
        }
+}
+
+static void
+highlight_subregion (GtkSourceSearch *search,
+                    GtkTextIter     *start,
+                    GtkTextIter     *end)
+{
+       GtkTextIter iter;
+       GtkTextIter *limit;
+       gboolean found = TRUE;
+
+       /* Make sure the 'found' tag has the priority over syntax highlighting
+        * tags. */
+       text_tag_set_highest_priority (search->priv->found_tag,
+                                      search->priv->buffer);
+
+       adjust_subregion (search, start, end);
 
        /*
        g_print ("[%u (%u), %u (%u)]\n", gtk_text_iter_get_line (start), gtk_text_iter_get_offset (start),