[gnome-shell] Optimize subsearches

[Colin Walters <walters src gnome org>]

commit 32ef951fe00e060968bd5fc959399002d6f09491
Author: Colin Walters <walters verbum org>
Date:   Wed Sep 23 16:16:38 2009 -0400

    Optimize subsearches
    
    This is probably not the biggest optimization that needs to be
    made at least for application searching, but we can optimize the
    case where we're going from a search of "fi" to "fire" by just
    re-searching the list of things we already had that matched "fi"
    instead of looping over everything.
    
    https://bugzilla.gnome.org/show_bug.cgi?id=596119

 js/ui/genericDisplay.js |   82 +++++++++++++++++++++++++++++++---------------
 1 files changed, 55 insertions(+), 27 deletions(-)
---
diff --git a/js/ui/genericDisplay.js b/js/ui/genericDisplay.js
index f8dfc56..df6109f 100644
--- a/js/ui/genericDisplay.js
+++ b/js/ui/genericDisplay.js
@@ -17,6 +17,10 @@ const DND = imports.ui.dnd;
 const Link = imports.ui.link;
 const Main = imports.ui.main;
 
+const RedisplayFlags = { NONE: 0,
+                         RESET_CONTROLS: 1 << 0,
+                         SUBSEARCH: 1 << 1 };
+
 const ITEM_DISPLAY_NAME_COLOR = new Clutter.Color();
 ITEM_DISPLAY_NAME_COLOR.from_pixel(0xffffffff);
 const ITEM_DISPLAY_DESCRIPTION_COLOR = new Clutter.Color();
@@ -357,8 +361,14 @@ GenericDisplay.prototype = {
 
     // Sets the search string and displays the matching items.
     setSearch: function(text) {
-        this._search = text.toLowerCase();
-        this._redisplay(true);
+        let lowertext = text.toLowerCase();
+        let flags = RedisplayFlags.RESET_CONTROLS;
+        if (this._search != '') {
+            if (lowertext.indexOf(this._search) == 0)
+                flags |= RedisplayFlags.SUBSEARCH;
+        }
+        this._search = lowertext;
+        this._redisplay(flags);
     },
 
     // Launches the item that is currently selected, closing the Overview
@@ -439,7 +449,7 @@ GenericDisplay.prototype = {
 
     // Load the initial state
     load: function() {
-        this._redisplay(true);
+        this._redisplay(RedisplayFlags.RESET_CONTROLS);
     },
 
     // Should be called when the display is closed
@@ -587,19 +597,23 @@ GenericDisplay.prototype = {
 
     /*
      * Updates the displayed items, applying the search string if one exists.
-     *
-     * resetPage - indicates if the page selection should be reset when displaying the matching results.
-     *             We reset the page selection when the change in results was initiated by the user by  
-     *             entering a different search criteria or by viewing the results list in a different
-     *             size mode, but we keep the page selection the same if the results got updated on
-     *             their own while the user was browsing through the result pages.
+     * @flags: Flags controlling redisplay behavior as follows:
+     *  RESET_CONTROLS - indicates if the page selection should be reset when displaying the matching results.
+     *  We reset the page selection when the change in results was initiated by the user by
+     *  entering a different search criteria or by viewing the results list in a different
+     *  size mode, but we keep the page selection the same if the results got updated on
+     *  their own while the user was browsing through the result pages.
+     *  SUBSEARCH - Indicates that the current _search is a superstring of the previous
+     *  one, which implies we only need to re-search through previous results.
      */
-    _redisplay: function(resetPage) {
+    _redisplay: function(flags) {
+        let resetPage = flags & RedisplayFlags.RESET_CONTROLS;
+        let isSubSearch = flags & RedisplayFlags.SUBSEARCH;
         this._refreshCache();
         if (!this._filterActive())
             this._setDefaultList();
         else
-            this._doSearchFilter();
+            this._doSearchFilter(isSubSearch);
 
         if (resetPage)
             this._list.page = 0;
@@ -643,35 +657,49 @@ GenericDisplay.prototype = {
 
     //// Private methods ////
 
-    _getSearchMatchedItems: function() {
-        let matchedItemsForSearch = {};
+    _getItemSearchScore: function(itemId, terms) {
+        let item = this._allItems[itemId];
+        let score = 0;
+        for (let i = 0; i < terms.length; i++) {
+            let term = terms[i];
+            if (this._isInfoMatching(item, term)) {
+                score++;
+            }
+        }
+        return score;
+    },
+
+    _getSearchMatchedItems: function(isSubSearch) {
         // Break the search up into terms, and search for each
         // individual term.  Keep track of the number of terms
         // each item matched.
         let terms = this._search.split(/\s+/);
-        for (let i = 0; i < terms.length; i++) {
-            let term = terms[i];
-            for (itemId in this._allItems) {
-                let item = this._allItems[itemId];
-                if (this._isInfoMatching(item, term)) {
-                    let count = matchedItemsForSearch[itemId];
-                    if (!count)
-                        count = 0;
-                    count += 1;
-                    matchedItemsForSearch[itemId] = count;
-                }
+        let matchScores = {};
+
+        if (isSubSearch) {
+            for (let i = 0; i < this._matchedItems.length; i++) {
+                let itemId = this._matchedItems[i];
+                let score = this._getItemSearchScore(itemId, terms);
+                if (score > 0)
+                    matchScores[itemId] = score;
+            }
+        } else {
+            for (let itemId in this._allItems) {
+                let score = this._getItemSearchScore(itemId, terms);
+                if (score > 0)
+                    matchScores[itemId] = score;
             }
         }
-        return matchedItemsForSearch;
+        return matchScores;
     },
 
     // Applies the search string to the list of items to find matches,
     // and displays the matching items.
-    _doSearchFilter: function() {
+    _doSearchFilter: function(isSubSearch) {
         let matchedItemsForSearch;
 
         if (this._filterActive()) {
-            matchedItemsForSearch = this._getSearchMatchedItems();
+            matchedItemsForSearch = this._getSearchMatchedItems(isSubSearch);
         } else {
             matchedItemsForSearch = {};
             for (let itemId in this._allItems) {