[gtksourceview/wip/search] search: scary implementation overview

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

commit 09ab86a33b331218ec7efddf0a94e6f1f8e66e72
Author: Sébastien Wilmet <swilmet gnome org>
Date:   Fri Jun 21 16:28:13 2013 +0200

    search: scary implementation overview
    
    The last part of the implementation overview is not already implemented,
    it's just an idea.

 gtksourceview/gtksourcesearch.c |   70 +++++++++++++++++++++++++++++++++++++++
 1 files changed, 70 insertions(+), 0 deletions(-)
---
diff --git a/gtksourceview/gtksourcesearch.c b/gtksourceview/gtksourcesearch.c
index 66b70a9..7253b9a 100644
--- a/gtksourceview/gtksourcesearch.c
+++ b/gtksourceview/gtksourcesearch.c
@@ -30,6 +30,76 @@
 /* Maximum number of lines to scan in one batch. */
 #define SCAN_BATCH_SIZE 50
 
+/* Implementation overview:
+ *
+ * When the state of the search changes (the text to search or the flags), we
+ * have to update the highlighting and the properties values (the number of
+ * occurrences). To do so, a simple solution is to first remove all the
+ * found_tag, so we have a clean buffer to analyze. The problem with this
+ * solution is that there is some flickering when the user modifies the text to
+ * search, because removing all the found_tag's can take some time. So we keep
+ * the old found_tag's, and when we must highlight the matches in a certain
+ * region, we first remove the found_tag's in this region and then we highlight
+ * the newly found matches by applying the found_tag to them.
+ *
+ * If we only want to highlight the matches, without counting the number of
+ * occurrences, a good solution would be to highlight only the visible region of
+ * the buffer on the screen. So it would be useless to always scan all the
+ * buffer.
+ *
+ * But we actually want the number of occurrences! So we have to scan all the
+ * buffer. When the state of the search changes, an idle callback is installed,
+ * which will scan the buffer to highlight the matches. To avoid flickering, the
+ * visible region on the screen is put in a higher priority region to highlight,
+ * so the idle callback will first scan this region.
+ *
+ * Why highlighting the non-visible matches? What we want is to (1) highlight
+ * the visible matches and (2) count the number of occurrences. The code would
+ * indeed be simpler if these two tasks are clearly separated (in two different
+ * idle callbacks, with different regions to scan). With this simpler solution,
+ * we would always use forward_search() and backward_search() to navigate
+ * through the occurrences. But we can do better than that!
+ * forward_to_tag_toggle() and backward_to_tag_toggle() are far more efficient.
+ * We must just pay attention to contiguous matches.
+ *
+ * So how to count the number of occurrences then? Remember that the buffer
+ * contents can be modified during the scan, and that we keep the old
+ * found_tag's. Moreover, when we encounter an old found_tag region, in the
+ * general case we can not say how many occurrences there are in this region,
+ * since a found_tag region can contain contiguous matches. Take for example the
+ * found_tag region "aa": was it the "aa" search match, or two times "a"?
+ * The implemented solution is to set occurrences_count to 0 when the search
+ * state changes, even if old matches are still there. Because it is not
+ * possible to count the old matches to decrement occurrences_count (and storing
+ * the previous search text would not be sufficient, because even older matches
+ * can still be there). To update correctly occurrences_count, there are two
+ * maintained regions:
+ *
+ * - The region_not_scanned, which contain the region not already scanned since
+ *   the last search state update. region_not_scanned can potentially contain
+ *   old matches. When we highlight the matches in this region, we first remove
+ *   all the found_tag's, without decrementing occurrences_count, and then we
+ *   search the new matches and increment occurrences_count.
+ *
+ * - The region_to_scan, which can contain subregions already scanned (and thus
+ *   removed from region_not_scanned). If a modification occurs in a buffer
+ *   region not present in region_not_scanned, the modified region will be
+ *   present only in region_to_scan. Such a region can not contain old matches.
+ *   Before the modification occurs, we remove the (good) matches, and we
+ *   decrement occurrences_count. After the modification, the idle callback will
+ *   highlight the matches and will increment occurrences_count.
+ *
+ * Example where forward_to_tag_toggle() is really nice:
+ * <occurrence> [1 GB of text] <next-occurrence>
+ * Once the buffer has been scanned once, switching between the occurrences is
+ * almost instantaneous.
+ *
+ * If the code is too complicated and contains strange bugs, you have two
+ * choices:
+ * - Write more unit tests, understand correctly the code and fix it.
+ * - Rewrite the code to implement the simpler solution explained above :-)
+ */
+
 struct _GtkSourceSearchPrivate
 {
        GtkTextBuffer *buffer;